不完全信息下交通网络最短路径关键边问题

因各种突发事件（交通事故、自然灾害等）造成道路中断的现象普遍存在，车辆在行驶的过程中并不具有道路中断的完全信息，只有行进到中断处时才获得道路中断的信息。本文就不完全信息（道路中断信息）下的变通网络最短路径关键边问题进行研究，首先定义了不完全信息下最短路径关键边的概念．其次给出了求解不完全信息下最短路径关键边的有效算法厦其时间复杂性分析，然后结合城市道路网络给出了实际算例，比较分析了最短路径关键边、最长绕行路关键边和不完全信息下的最短路径关键边问题，指出了不完全信息下的最短路径关键边问题更具有实际意义。     

基于XOR选择重传ARQ的网络编码多播路由算法

针对XOR选择重传ARQ协议,提出了一种基于网络编码的多播路由算法,有效地恢复链路传输错误。该算法分为两种情况：一是信源发送正常的数据包,在信源节点与各接收节点之间建立多播路径族,并考虑不同路径族之间链路的共享;二是信源发送XOR数据包,搜索信源节点到各接收节点的最短路径,并考虑最短路径之间的链路共享。仿真结果表明,该算法有效地提高了网络吞吐量,在资源消耗方面较传统的多播路由算法有更好的表现,非常接近基于网络编码的最小费用多播算法。数学分析表明,该算法的复杂度远小于最小费用多播算法。     

传感器网络中基于链路层服务的最短路由算法

无线传感器网络中,链路通信质量随时空变化很大,并且有5%-15%的非对称链路存在。链路层服务不但可以发现邻居传感器节点,测量和预测邻居节点间的链路通信质量,而且还提供链路数据转发机制来减轻单向链路对其它协议的影响。利用链路层服务,采用分布式最短路由路径建立算法,为每个传感器节点建立了到汇聚节点的最短路由路径,然后从理论上分析了该算法的性能,最后在无线传感器网络模拟器TOSSIM上进行了模拟。实验结果表明,基于链路层服务的最短路由路径建立算法,不仅可以有效地避免建立断路由路径,还可以充分利用单向链路来建立更短的路由路径,有多于15%的传感器节点建立了更短的路由路径,路由跳数也减少了14%-100%。     

不完全信息下交通网络的关键路径问题

在交通运输中．车辆总是选择最短路径行驶。然而因各种突发事件（交通事故、自然灾害等）造成道路中断的现象普遍存在．车辆在行驶的过程中并不具有道路中断的完全信息．只有行进到中断处时才获得道路中断的信息．此时原来的最短路径就很可能失去其最优性．从而增加交通运输的成本。为了解决这一问题．本文提出了不完全信息下交通网络的关键路径问题．给出了相应的求解算法．并分析了其时间复杂性。然后结合实际交通网络给出算例．最后指出这对提高交通运输的效率更具有实际意义。     

基于加权路由策略的复杂网络拥塞控制研究

复杂网络的最短路由策略易导致网络吞吐量低,流量分布不均,在关键节点处产生拥塞.本文提出一种基于加权路由策略的拥塞控制机制,用节点的介数作为节点边的权重,将网络变成加权网络,数据包按加权网络最短路径路由.介数的计算采用基于区域中心节点近似估算法,降低了介数计算的复杂度.仿真结果表明,加权路由策略能有效避开拥塞程度严重的节点,克服了介数较大节点成为网络传输瓶颈的问题,显著改善了网络的拥塞情况,提高了网络的吞吐量和传输能力.     

基于区域不相交的无线传感网任播路由算法

在无线传感器网络(wireless sensor networks, WSN)中采用任播技术可以均衡数据流及能耗。传统算法常采用节点不相交路由策略,但隐终端问题仍会造成任播路径间的传递碰撞。针对该问题,提出基于区域不相交策略的WSN任播路由算法。该算法采用扇形通道技术和基于不同时隙的区域不相交发送策略以减少任播路径传递碰撞问题。仿真实验数据表明,相比较节点不相交路由策略和最短路径优先区域不相交路由策略,本文算法在分组投递成功率和节点平均能耗上具有较好的性能优势,从而提高网络生存期。     

无人机自组网中基于蚁群优化的多态感知路由算法

无人机自组织网络具有节点移动性强、网络拓扑变化快、数据交互频繁、应用环境复杂等特点, 采用传统的路由算法会使该网络在传输延时、丢包率、路由开销等方面性能均较差, 以至于无法为多无人机协同执行任务提供有效的通信保障。为了解决该问题, 提出一种基于蚁群优化的多态感知路由(ant colony optimization based polymorphism-aware routing, APAR)算法。该算法将蚁群算法与动态源路由算法相结合, 通过感知路径长度、路径拥塞度和路径稳定性, 计算出由路由发现过程得到路径的信息素水平, 并将其作为选路标准, 经过改进的信息素挥发机制也被引入该算法。同时, 根据无人机编队的变化做出合适的调整, 以保证其网络性能不下降。仿真结果表明, 与其他经典算法相比, APAR算法提高了数据包成功传输率, 降低了平均端到端延时, 减少了路由开销, 且在战场环境下有较高的可靠性。     

无人机协同中继过程中的路径规划与通信优化

通信网络是保证无人机在协同搜索时获取更多的战场信息,发挥协同作战优势的基础。主要研究多无人机完成通信中继任务过程中的搜索路径规划和通信性能优化问题。搜索路径规划的目的是确定未知地面移动人员具体方位并对其组网,以便无人机执行中继任务;而通信优化问题则是针对无人机中继过程中可能出现的通信中断、失真等问题,分析通信网络信息传输的路由选择,选取通信延时为性能指标,通过改变无人机的路径选择来提高通信网络的性能。仿真结果表明了本文实现通信中继和通信网性能提高的有效性。     

基于位置感知的大规模LEO星座分布式路由算法

针对传统星座路由算法应用在大规模低地球轨道(low earth orbit, LEO)星座中, 存在鲁棒性差、资源开销大、路由效率低等缺点。根据卫星运行时的位置可预测特性, 提出了基于位置感知的分布式路由算法。考虑卫星资源受限, 大规模LEO星座具有卫星节点多、动态性大等特点, 基于位置感知提出一种路径预选机制, 初步确定数据包的传输路径。在此基础上, 考虑业务服务质量(quality of service, QoS)需求, 基于状态和传播矢量函数提出一种路径收敛机制, 无重合确定数据包传输主路径和备用路径。理论和仿真结果证明, 相比于传统路由算法, 所提算法降低了路由存储和开销, 随着中断概率的增大, 提高了星座的吞吐量, 降低了端到端时延。     

卫星ATM网络自适应最小阻塞路由策略

提出适合面向连接的卫星ATM网络的、动态自适应最小阻塞路由策略;在全球业务量统计模型下,采用全新的适合Walker delta星座的业务区域划分方式,根据每条链路的业务负担情况,选择阻塞概率最小的最优路径。分析该路由策略同最短路径路由的服务质量的不同,比较轨道高度不同的LEO网络同MEO网络在相同业务模型下的性能差异。仿真结果表明,该策略能够提高通信的可靠性———减小路径阻塞概率,同时保证通信的有效性。     

两种策略下的最短路径并行算法研究与实现

随着智能交通运输系统的研究与应用,对在大规模交通网络上求解最短路径的实时性提出了更高的要求。为了找出适用于实际交通网络的高效最短路径并行算法,首先选取了3种最短路径标号串行算法,以此为基础分别实现了网络复制及网络分割两种策略下求解最短路径的并行算法。最后,从基于G IS的交通规划软件T ransCAD中提取了实际交通路网数据,同时还随机产生了不同规模的稀疏格网,在这些网络中对并行算法的性能进行了测试和分析。结果表明,在8台机器上求解含5 181个节点的实际交通网络中32个源点的最短路径时,基于网络分割的双队列标号修正并行算法的加速比可达到6.32,在其他网络中也表现出较好的加速比及可扩展性。     

典型城市路网中的椭圆最短路径算法

提出了一种高效可靠的限制搜索区域的最优路径算法．该算法是基于典型城市路网的共同特征, 而不是某个特定城市的统计信息提出的, 它可以应用在不同的城市路网中．针对从源站点到目的站点不同的欧式距离, 算法分别在两类不同大小的椭圆内搜索最短路径．理论计算和实验结果都表明, 当源站点和目的站点相距较远时, 与椭圆限制搜索区域算法相比, 该算法可以降低33%-47%的时间复杂度, 而不会影响查询结果的准确性．     

考虑节点中断和需求波动的可靠供应链网络设计问题

本文研究了一个包含供应点、中转点和需求点的三级可靠供应链网络设计问题(RSCNDP).文章同时考虑了供应端的不确定性(节点中断的可能性)和需求端的不确定性(需求量的波动性),针对这些因素,采用情景的方法描述,并结合p-鲁棒模型的优点提出了一个新的混合整数规划模型.在模型中,α,β两参数分别表示决策者对节点中断和需求波动的风险偏好,优化的目标是在给定的风险偏好下最小化设施的固定成本和产品的运输成本.文章提出了一个由最短增广链法和遗传算法的相结合的混合智能算法来求解该模型,并结合实际进行了相应的数值分析.结论显示决策者的风险偏好对可靠供应链网络的设计会产生重大的影响,而在面临风险时,可靠的供应链网络表现要优于确定型的供应链网络,这些为企业的供应链管理决策提供了理论支撑.     

Path Optimization of Stochastic Transportation Network Based on Frequency-Domain Spanning Graph Model

Because of the uncertainty, openness, and complexity of modern transportation system, the path optimization becomes a challenge in most cases. To address this challenge, we propose a Frequency-domain Spanning Graph (FSG) method for searching the optimal path of stochastic transportation network in terms of various probability distribution function of path optimization problem. Furthermore, we design an improved algorithm to achieve the FSG model based on generalized adjacency matrix. By using FSG method to execute the mutual transformation of probability function between time-domain and frequency-domain, the quantitative analysis for the dynamic process of pass rate (probability) between node couple O-D (origin node and destination) can be obtained directly, and continuous probability distribution and discrete probability distribution can be handled. In addition, the algorithm is highly effective, and easy to be realized with low complexity. To demonstrate the performance of our method, a detailed example is implemented, and the results show that our method has the feasibility and effectiveness when compared with traditional method.     

最短路树的计数、产生和优化问题

首先给出了在非负网络中构造最短路网络的算法，然后将树形图的计数算法到最短路网络中，设计出了最短路树计数问题的算法，将Gabow算法应用到最短路网络中，设计出了产生全部最短路树的算法，最后研究了最短路树的优化问题。     

一个时延约束的动态组播路由算法

分析了时延约束的动态最小代价组播路由问题，然后基于贪婪思想设计了一个动态组播树生成算法DCDG（Delay—Constrained Dynamic Greedy Algorithm），用于在动态环境下构造时延约束的低代价组播树。该算法通过节点动态贪婪地选择满足时延约束的最短路径加入组播树来降低代价；若时延不满足要求，则通过合并DDSP（Destination-Driven Shortest Path Algorithm）最小时延路径来产生一个满足时延约束的低代价组播树。仿真实验表明：DCDG算法动态生成的组播树代价较低、性能稳定，而计算复杂度仅为O（n）；在严格的时延约束下会话成功率高。     

无向正权网络最短路模型的建立和理论分析

路径问题是运筹学的重要分支, 更是图论学科成立的奠基问题.针对无向网络中的路径问题, 首先, 建立了无向正权网络最短路模型, 提出一些能够反映无向网络中节点、边和路线规律性的参数概念, 包括点参数和边参数, 用这些参数代替边的权数描述无向正权网络; 其次, 通过对模型进行理论分析, 推导出与各参数相关的结论, 利用参数揭示了点、边、路线以及无向正权网络之间的关系, 并初步体现了该模型的用途; 第三, 利用该模型求解了与无向正权网络相关的几类基本路径问题; 最后, 通过应用举例, 阐述了该模型的部分应用. 需注意的是, 该模型也适用于带回路的有向正权网络.     

多源多目标网络下基于包聚合的选择协作方法

针对实际应用中广泛存在的源-目节点不等的无线传感网,提出一种基于包聚合的选择协作方法,以提升传输可靠性。首先,通过建立源-目节点间的关联矩阵将多源多目标传感网分解为多个多源单目标传感网;其次,将包聚合策略引入协作传输中,对多源单目标网络实施基于包聚合的选择协作通信;再次,考虑传输顺序对各源节点的影响,将3种调度方法引入选择协作方法中;最后,在保证系统传输可靠性的前提下,为方便系统的多目标优化,提出了3种中继选择策略。仿真结果表明,所提选择协作方法不仅能提高系统传输可靠性且能满足不同的网络需求。     

A Multipath Routing Assignment Model for Multi-Traffic Class Networks

1　IntroductionRoutingisakeytechnologyformoderndatanetworksandtherehavebeentremendousroutingalgorithms[1]～[5].MostoftheroutingalgorithmssuchasOSPFandRIP[5]arebasedontheshortestpathassignmentmodel,inwhicheveryrouterisonlyatransitionnode.Futurerouterisdestinationorientedandshouldhavetheabilitytosplittrafficloadovermulti-pathtoutilizethenetworkinfrastructureinanefficientway.Withthenetworktrafficincreasingmuchfaster,howtorealizeloadbalancinginthenetworkbecomesahotresearchtopic[2].UndertheOSP…