前言：中文期刊网精心挑选了路径规划典型算法范文供你参考和学习，希望我们的参考范文能激发你的文章创作灵感，欢迎阅读。
路径规划典型算法范文1
中图分类号：TP306文献标识码：A文章编号：1009-3044(2008)21-30523-02
An Algorithm Based on Improved A* Restrictions on the Path to Search Regional Planning Approach
XU Zhan-peng, LIN Kai
(Qingdao Technical College Information Institute of Qingdao,Qingdao 266555,China)
Abstract: According to A* algorithm has been given an improved optimal path planning method, this algorithm in accordance with the actual situation of the road network of layered LO at the same time, according to the actual network topology of the region to search for reasonable Restrictions experiment proved that the algorithm in the path planning saving time
Key words: Path planning; Search region; A* algorithm
1 引言
路径规划是在车辆行驶前或行驶过程中寻找车辆从起始点到达目的地的最佳行车路线的过程[1], 它属于智能交通
系统中的最短路径问题的一个具体应用。
最短路径规划产生的路径分为两种：距离最短的路径和时间最短路径,其中前者相对比较易于实现，但是它容易忽略路径的具体情况和行车实际环境以及人为因素。因为在实际车辆行驶中要求不但在此路径上行车距离尽可能短，而且路径的行车环境尽可能好，即尽量走道路较宽、路面质量较好、红绿灯较少、红绿灯设置间隔较大、车流量较小的路径，避免走行车环境太差的路径。作者针对最短路径规划存在的不足之处 ,根据已有A*算法，给出了一种改进的最优路径规划算法，此算法在根据道路的实际情况对路网进行分层的同时，根据实际路网的拓扑特性对搜索区域进行合理的限制。
2 A*算法
A*算法是人工智能中一种典型的启发式搜索算法．也是路径规划算法中的常用算法，它通过选择合适的估计函数，指导搜索朝着最有希望的方向前进．以期求得最优解限制搜索区域的多层最优路径规划算法，A*算法评价函数的定义为[2]：
f(n)=g(n)+h(n) （1）
f(n)是从初始点通过节点n 到达目标点的估价函数；
g(n)是在状态空间中从初始节点到n节点的实际代价；
h(n)是从节点n到目标节点最佳路径的估计代价。它决定了搜索的效率和可采纳性。对于几何路网来说，可以取两点间欧氏距离（直线距离）作为估价值，即
其中，(xd,yd)、(xn,yn)分别为节点n 和目标节点在数字地图中的坐标。由于估价值h(n)≤n 到目标节点的距离实际值，算法具有可采纳性，能得到最优解。[3]
3 改进的A*算法球最短路径
本文在三个方面对传统的A*算法进行了更改：1)A*算法提到的权值会根据用户的不同查询条件来调用相对应的计算权值的公式；2) 添加了一个判断过程。当查询下一个临近边的时候首先查询交通控制策略，判断是否有管制信息并将相映的点从v中删除；3) 减少路径搜索的范围，以出发点与目的地点连线的中间点为圆心，以两点之间直线距离的二分之一再加上几公里为半径画圆，在圆范围内的路径参加搜索，在圆范围之外的路径不参加搜索。
具体实现如下：
创建两个表，OPEN表保存所有已生成而未考察的节点，CLOSED表中记录已访问过的节点，设各个点的权值（也称为费用值）为g。遍历当前节点的各个节点，将n节点放入CLOSE中，取n节点的子节点X,计算X的估价值[4]。
1)初始的OPEN表仅包含原节点．其费用值g为0，令CLOSED为空表，设其他节点的费用为∞ 。
2)若OPEN表为空．则宣告失败：否则，选取OPEN表中所有的节点移至CLOSED表，将此CLOSED表作为新的OPEN表。重复第二步，直到深度达到4。
3)对第二步在深度4时形成的OPEN表进行操作，若OPEN表为空．则宣告失败：否则，选取OPEN表中具有最小权值的节点，并叫做最佳节点NEXT．把NEXT从OPEN表移至CLOSED表．判断此NEXT是否是一目标节点。若NEXT为目标节点．转步骤3，若NEXT不是目标节点。则根据地图数据库包含的联接路段属性扩展并生成NEXT的后继节点。对于每一个后继节点n，进行下列过程：
①计算节点n的费用：g(n)= NEXT费用+从NEXT到n的费用
②如果n与OPEN表上的任一节点相同．判断n是否具有最小的g值。若是最低的g值，用n的费用代替OPEN表中相同的节点费用。且建立匹配节点的后向指针指向NEXT
③如果n在CLOSED表中与一节点相匹配。检查节点n是否具有最小的g值，如果n具有最小的g值，则用节点n的费用代替匹配节点的费用。并把匹配节点的后向指针指向NEXT。并把该匹配节点移到OPEN表
④如果n不在OPEN表。也不在CLOSED表上，则把n的后向指针指向NEXT。井把n放入OPEN表中。计算节点n的估价函数：f(n)=g(n)+h(n)
例如图1，为带权的有向图。
根据步骤三，针对图1，算法的具体实现如图2。
4)重复第三步：
若在深度为7的搜索中找到目标结点且仅有一条路径，则该路径为最终路径，返回；
若在若在深度为7的搜索中找到目标结点并且有多条路径则回朔，比较找到的路径费用，取权值最小的作为最终路径；
若在在深度为7的搜索中未找到任何目标点则跳转到第五步。
5)从深度为7的搜索中的所有的NEXT节点回朔，即从NEXT的后向指针一直到原节点遍历节点，最后报告若干条路径，比较个路径费用，取费用最小的前100条路径继续重复第三步、第四步。由于h函数在满足h下限得条件下，愈趋近于h效率愈高，因此实际应用中，我们取的是节点到目的点的直线距离保证满足下限的情况下，尽可能的趋近h。
4 结语
实践表明基于改进A*算法的限制搜索区域的路径规划方法不仅在进行路径规划时节省了时间，而且规划后的路径大部分道路位于高层路网上，路径长度与最短路径长度之比小于1.1,可以被人接受，是行车意义上的最优路径。
参考文献：
[1] 付梦印.限制搜索区域的距离最短路径规划算法[J].北京理工大学学报,2004(10).
[2] 赵亦林.车辆定位与导航系统[M].北京:电子工业出版社,1999:1-7.
[3] 王亚文.智能交通系统中路径规划算法研究与系统设计[D].陕西师范大学,2007.
路径规划典型算法范文2
关键词:移动多智能体;全局规划;局部规划
中图分类号:TP393文献标识码:A文章编号:1009-3044(2010)16-4487-03
Research on Path Planning for Mobile Multi-Agent
CHEN Cui-li, GAO Zhen-wei
(Henan Normal University, Xinxiang 453007,China)
Abstract: A path planning method based on both the benefits of global and local path planners is proposed for mobile Multi-Agent path planning in dynamic and unstructured environments. The global path planner uses A*algorithm to generate a series of sub-goal nodes to the target node, and the local path planner adopts an improved potential field method to smooth and optimize the path between the adjacent sub goal nodes. Taking into full consideration the kinematical constraints of the mobile robot, this method cannot only effectively generate a global optimal path using the known information, but also handle the stochastic obstacle information in time. and is simulated on simulation platform developed by using Visual Studio 2005 software, simulation result presents the validity and utility of the algorithm.
Key words: mobile Multi-Agent; global path; local path
在移动智能体相关技术研究中,路径规划技术是一个重要研究领域。移动智能体路径规划问题是指在有障碍的环境中,寻找一条智能体从起始点到目标点的运动路径,使智能体在运动过程中安全、无碰撞地绕过所有的障碍物。这不同于用动态规划等方法求得最短路径,而是指移动智能体能对静态及动态环境下做出综合性判断,进行智能决策。在以往的研究中,移动智能体路径规划方法大体上可以分为三种类型:其一是基于环境模型的路径规划,它能处理完全已知的环境下的路路径规划。而当环境变化时(出现移动障碍物)时,此方法效果较差,具体方法有:A*方法、可视图法、栅格化和拓扑图法等;其二是基于传感器信息的局部路径规划方法,其具体的方法有:人工势场法、模糊逻辑法和遗传算法等;其三是基于行为的导航行为单元,如跟踪和避碰等,这些单元彼此协调工作,完成总体导航任务。随着计算机、传感器及控制技术的发展,特别是各种新算法不断涌现,移动机器人路径规划技术已经取得了丰硕研究成果。
一个好的路径规划方法需要满足如下性能[1]:合理性、完备性、最优性、适时、环境变化适应性和满足约束。有些方法没有高深的理论,但计算简单,实时性、安全性好,就有存在的空间。如何使性能指标更好是各种算法研究的一个重要方向。
在未知的(或部分已知的),动态的非结构的环境下,多智能体利用传统的路径规划方法很难满足前面的性能要求,本文提出了一种将全局路径规划方法和局部规划方法相结合,将基于反应的行为规划和基于慎思的行为规划相结合的路径规划方法,其思路如下:多智能体分别采用A*算法进行全局路径规划,各自生成到达目标点的子目录节点序列,同时采用改进的人工势能对子目录节点序列中相邻节点进行路径的平滑和优化处理,该方法不但能够充分利用已知环境信息生成全局最优路径,而且还能及时处理所遇到的随机障碍(其它智能体)信息,从而提高了多智能体整体的路径规划的性能。
1 路径规划方法
1.1 相关研究
1) A*算法
在最佳优先搜索的研究中,最广范围应有的方法为A*搜索,其基本思想[2]是:它把到达节点的代价g(n)和从该节点到目标节点的代价h(n)结合起来对节点进行评价:f(n) = g(n) + h(n)(1)。A*算法用于移动多智能体的路径规划时,多智能体分别按照已知的地图规划出一条路径,然后沿着这条生成路径运动,但智能体传感探测到的环境信息和原来的环境信息不一致时,智能体重新规划从当前位置到目标点的路径。如此循环直至智能体到达目标点或者发现目标点不可达[3]。重新规划算法依旧是从当前位置到目标点的全局搜索的过程,运算量较大。而且由于采用A*方法规划出的最优路径并没有考虑到机器人的运动学约束,即使机器人可以采用A*方法规划出一条最优路径,机器人也未必可以沿着这条路径运动。
2) 人工势能法
人工势能法由 Khatib 提出的一种虚拟力法[4]。人工势场方法结构简单,便于低层的实时控制,在实时避障和平滑的轨迹控制方面得到了广泛的应用,但根据人工势场方法原理可知,引力势场的范围比较大,而斥力的作用范围只能局部的,当智能体和障碍物超过障碍物影响范围的时候,智能体就不受来自障碍物引起的排斥势场的影响。所以,势场法只能解决局部空间的避障问题,他缺乏所在的全局信息,,这样就造成产生局部最优解不能进行整体规划,智能于局部最小点的时候,智能体容易产生振荡和停滞不前。
1.2 路径规划方法描述
鉴于A*算法全局路径搜索的全局性与改进人工势场算法局部路径搜索的灵活性,通过一定的方法把两者结合起来,其思路如下:多智能体分别采用A*算法进行全局路径规划,各自生成到达目标点的子目录节点序列,同时采用改进的人工势能对子目录节点序列中相邻节点进行路径的平滑和优化处理,该方法不但能够充分利用已知环境信息生成全局最优路径,而且还能及时处理所遇到的随机障碍(其它智能体)信息,从而提高了多智能体整体的路径规划的性能。由于A*方法采用栅格表示地图,栅格粒度越小,障碍物的表示也就越精确,但是同时算法搜索的范围会按指数增加。采用改进人工势场的局部路径规划方法对A*方法进行优化,可以有效增大A*方法的栅格粒度,达到降低A*方法运算量的目的。
2 环境构造
目前主要有三种比较典型的环境建模方法:构型空间法、自由空间法和栅格法,本文仿真实验采用的环境建模方法是栅格法,栅格法将机器人路径规划的环境划分成二维网格,每格为一个单元,并假设障碍的位置和大小已知,且在机器人运动过程中不会发生变化。栅格法中的网格单元共有三种类型,即障碍网格、自由网格和机器人所在网格。目前常用的栅格表示方法有两种,即直角坐标法和序号法。这两种表示方法本质上是一样的,每个单元格都与(x, y)一一对应。本文采用序号法表示栅格,设栅格的中心点坐标为栅格的直角坐标,则每个栅格编号都与其直角坐标一一对应,地图中任意一点(x,y)与栅格编号N的映射关系为:N=INT(xGs)+xmaxGs×INT(yGs),(1)式中,xmax表示x轴的取值范围,Gs表示栅格尺寸的大小,INT函数表示取整,而栅格中心点的坐标为(xG,yG),它与栅格编号N之间的关系为:xG=(N%M)×Gs+Gs/2,yG=INT(N/M)×Gs+Gs/2,(2)式中,M=xmax/Gs,符号%表示取余操作。本文中根据机器人的尺寸来确定栅格的粒度,假设一个栅格能容纳一个智能体,这里选择栅格的大小为40cm×40cm[5]。本文的仿真环境为800cm×800cm,栅格号N=0~399,机器人的初始位置的栅格号为N=42,目标位置的栅格号为N=314。在Visual Studio 2005中进行仿真,仿真结果如图1所示,长方形和椭圆图形代表障碍物栅格,小圆圈所代表的栅格为机器人的起始栅格和目标栅格,剩下的是自由栅格。在路径规划中机器人可以选择自由栅格作为它的路径点。
建立栅格后,对栅格进行初始化。设置变量G_Obstacle为0表示自由栅格,G_Obstacle为1表示障碍网格包括机器人栅格。若障碍物或智能体占当前位置栅格面积大于1/3则设置变量G_Obstacle为1.
3 数据的采集
对于简单地形,我们将实际地形就行考察并进行测量、量化,转化为平面坐标数据最后转换相应的栅格编号。对于复杂地形在没有航摄资料的情况下,本实验以地图为数据源的DTM数据获取方法在,可利用已有的地形图采集地形数据,用手扶跟踪式数字化仪将平面图形转化为平面坐标数据,最后转换相应的栅格编号。
4 实现过程
第1步:对环境信息进行数据采集并转化成相应的平面坐标数据。
第2步:确定各个智能体的初始位置和目标位置。
第3步:建立栅格,对栅格进行初始化。
第4步:智能体S(i)首先根据已知信息规划出各自的一条目标序列S(i)n。
第5步:智能体S(i)利用测试传感器探测到临界危险区L范围内的信息与原有信息是否一致,当智能体利用传感器探测到临界危险区L范围内的信息与原有信息一致时,利用改进后的人工势能算法搜索相邻目标点之间的轨迹,否则智能体搜索从当前序列点S(i)n到S(i)n+4路径。定义临界危险区L、目标序列点S(i)n(n>=1)。
第6步:智能体一旦移动到达目标栅格,则程序终止;否则返回第5步。系统的工作流程如图2所示。
5 仿真结果及结论
在Visual Studio 2005平台上进行了仿真,,首先根据已知环境信息,进行数据采集量化并进行栅格化处理,设置障碍和智能体的大小及位置(为了简单化,本实验所有障碍都设置为圆形),再进行初始化操作,采用0、1二元信息数组存储栅格化的地形。
智能体运用A*算法进行全局路径规划,图3显示两个智能体的运动过程,显然两个智能体的路径相交可能会发生碰撞,智能体为了避免碰撞应重新规划算法依旧是从当前位置到目标点的全局搜索的过程,运算量较大。而且显然只用A*算法规划出二维路径点序列,相邻两点之间的夹角一定是π/4的整倍数,机器人很难按照所生成的序列点运动。智能体采用改进后的人工势场进行目标序列点之间的局部路径规划,图4显示智能体的运动过程。显然智能体的整条运动轨迹显得比较平滑同时又实现实时避障的目的。
6 总结
本文对多智能体在动态环境下路径规划技术进行了研究探索,提出了一种能够将全局路径规划方法和局部路径规划方法相结合,通过仿真取得了很好的结果,证明A*和人工势场算法的结合可行。
参考文献:
[1] 刘华军,杨静宇,陆建峰,等.移动机器人运动规划研究综述[J].中国工程科学,2006,8(1):85-94.
[2] Nilsson N J. Princip les of Artificial Intelligence[M].Berlin, Ger2 many: Sp ringer,1980.
路径规划典型算法范文3
关键词： B样条曲线； 无人车； 路径规划； 碰撞检测； 最大曲率约束； 最优路径
中图分类号：TP181 文献标识码：A 文章编号：1009-3044（2016）26-0235-03
B-spline Curve based Trajectory Planning for Autonomous Vehicles
QU Pan-rang，LI Lin ， REN Xiao-kun ，JING Li-xiong
（Institute of Aeronautics Computing Technique Research， Xi’an 710065， China）
Abstract：Path planning is an important research topic in the field of the unmanned vehicle motion planning， and it directly affects the performance of unmanned vehicles in a complex traffic environment. Taking the requirement for smoothness into account， this paper proposed a method based on B-spline curve and built a planning model which can be divided into four steps， including path clusters， constraint of maximal curvature， collision detection and optimal path. This method works efficiently and simulation results show efficiency of the method.
Key words：B-spline curve； autonomous vehicle； path planning； collide detection； constraint of maximal curvature
1 引言
近年来，无人驾驶技术备受关注，各大研究机构和企业争相推出各自的无人驾驶平台。无人车作为未来智能交通的主要主体也逐渐融入到我们的日常生活中，比如自主巡航[1]和自动泊车等等。然而，为了使其更好地服务于我们，需要进一步提高其智能化水平，而路径规划作为连接环境感知和运动规划的桥梁，是无人车智能化水平的重要体现[2]。
由于受到自身动力学和运动学模型的约束，车辆的路径规划问题除过要严格满足端点状态约束之外，还要求其中间状态满足运动系统的微分约束。由于实现简单，并且高阶多项式曲线能够很好地满足运动系统的微分约束，生成高阶平滑的路径，所以很多路径规划系统选择使用基于多项式曲线的方法生成路径。B样条曲线是一种典型的多项式曲线，且因为其所有的中间状态均是由控制点加权生成，所以其能够完全满足端点状态约束。综合考虑无人车路径规划的要求和实现复杂度，在仅已知初始位姿和目标位姿的情况下，本文选择B样条曲线生成路径，重点讲述分步规划模型，即路径簇生成、最大曲率约束、碰撞检测以及最优评价四个过程，并通过Matlab仿真对本文方法进行了验证。
2 问题描述
本节分别描述了无人车路径规划问题和B样条曲线。
2.1 路径规划问题描述
路径规划得到的是一条从初始位置到目标位置的路径，即二维平面内一条从初始位置点到目标位置点的曲线，曲线上的每一个点表示车在行驶过程中的一个状态。考虑到实现方便，本文将路径描述成离散点序列[Sstart，S1，???，Sn，Sgoal]，如图1所示，序列中每一个点[Si（xi，yi，θi）]表示车的一个状态，其中[（xi，yi）]表示此时刻车辆的位置，[θi]表示车辆的航向，[Sstart]和[Sgoal]分别表示车辆的初始状态和目标状态。图1中的圆[（xobs1，yobs1，robs1）]表示环境中的障碍物，[（xobs1，yobs1）]表示障碍物的位置信息，[robs1]表示障碍物的半径。
2.2 B样条曲线
如果给定[m+n+1]个控制点[Pi（i=0，1，???，m+n）]，就可以构造[m+1]段[n]次B样条曲线，其可以表示为公式1：
[Pi，n（t）=k=0nPi+k?Fk，n（t） ，t∈[0，1]Fk，n（t）=1n！j=0n-k（-1）j?Cjn+1?（t+n-k-j）n ， t∈[0，1] ， k∈0，1，???，n] （1）
其中，[Pi，n（t）]表示第[i]个[n]次B样条曲线片段，[n]表示B样条曲线的次数，[t]为控制参数，其取值范围为[[0，1]]，[Pi+k]为控制点，[Fk，n（t）]为B样条基。依次连接全部[n]阶B样条曲线段就组成了整条B样条曲线。
3 本文算法
本节重点讲述基于B样条曲线的路径规划方法和基于该方法生成路径的过程。
3.1 基于B样条曲线的路径规划方法
选择三阶B样条曲线生成几何路径，即每四个控制点生成一个路径片段，然后通过片段的拼接就可以实现从初始状态到目标状态的路径规划，下面着重讲述基于六控制点的三阶B样条曲线生成满足车辆端点位姿约束路径的方法，如图2所示。
l 依据初始状态选择控制点[P0，P1，P2]。当[P0，P1，P2]三个控制点共线，并且[P1]为线段[P0P2]的中点时，生成的B样条曲线与线段[P0P2]相切于点[P1]。所以选择无人车的初始位置为控制点[P1]，将控制点[P0]和[P2]选在初始航向角[θstart]所在直线上，并关于控制点[P1]对称。如是，即能满足车辆的初始位姿约束；
l 依据目标状态选择控制点[P3，P4，P5]。当[P3，P4，P5]三个控制点共线，并且[P4]为线段[P3P5]的中点时，生成的B样条曲线与线段[P3P5]相切与点[P4]。所以选择无人车的目标位置为控制点[P3]，将控制点[P3]和[P5]选在目标航向角[θgoal]所在的直线上，并关于控制点[P3]对称。如是，即能满足车辆的目标位姿约束。
（a） 路径簇
（b） 最大曲率约束
（c） 碰撞检测
3.2 分步路径规划
本小节将以图3所给定的场景为例，讲述最优路径生成的过程。
3.2.1 路径簇生成
在选定控制点[P1]和[P4]之后，通过选择不同的控制点[P2]和[P3]，从而得到多组控制点，进而得到多条路径。将控制点选择的极限定为线段[P1P2]、[P3P4]与[P1P4]相等，但是[P1P2]和[P3P4]不能出现交叉。将这个范围等间隔量化，各取四个点，共组成16组控制点，得到16条路径，如图3（a）中的蓝色曲线所示。
3.2.3 最大曲率约束
理论上，车辆的最小转弯半径[Rmin=Lsin（θmax）]是其本身属性[3]，只取决于车辆的轴距[L]和最大前轮转角[θmax]。那么，车辆可行驶路径的最大曲率[κmax=1Rmin]也是固定的，假设无人车可行驶路径的最大曲率[κmax=16]，以此为约束条件，在路径簇中选择满足最大曲率约束的路径，如图3（b）所示，图中绿色曲线表示不满足最大曲率约束的路径。
3.2.4 碰撞检测
碰撞检测的目的是保证车辆在规划路径上行驶而不与障碍物发生碰撞。采取的碰撞检测的方法很简单，因为环境中的障碍物采用圆来描述，所以只要判断路径上每一点到圆心的距离与障碍物半径的关系，就能确定其是否发生碰撞。由两点间距离公式：
[d=（x1-x2）2+（y1-y2）2] （2）
如果[d]大于障碍物半径，则不发生碰撞；如果[d]小于障碍物半径，则发生碰撞。图3（c）中的蓝色曲线表示既满足最大曲率约束，又不与障碍物碰撞的路径。
3.2.2 最优路径
路径要求的侧重点不同，优化的目标函数也可以有多种选择，常用的目标函数有最短和最平滑等。其中，路径最短可以抽象成优化问题：
[traoptimal=arg mintraids] （3）
路径最平滑可以抽象成优化问题：
[traoptimal=arg mintraiκ2] （4）
式中，[traoptimal]为最优路径，[traids]为第[i]条路径的长度，[traiκ2]为第[i]条路径上所有点处的曲率平方之和。图3（d）中的红色曲线即为得到的最短可行驶路径。
如是，就能得到满足车辆运动学约束，并且无碰撞的最优路径。
4 结论
本文选择使用B样条曲线解决无人车路径规划问题，并建立了基于B样条曲线的分步规划模型。仿真结果表明，使用基于B样条曲线的路径规划方法能够很好地解决简单障碍物场景中无人车的路径规划问题，并且因为路径生成过程简单，所以该方法常常表现得十分高效，能够完全满足无人车路径规划系统对算法实时性的要求。
参考文献：
[1] Vahidi A， Eskandarian A. Research advances in intelligent collision avoidance and adaptive cruise control [J]. IEEE Transactions on Intelligent Transportation Systems， 2003， 4（3）：143-153.
路径规划典型算法范文4
中图分类号：TP393文献标识码：A文章编号：1009-3044(2012)12-2708-03
当下，随着我国互联网业务开展的类型越来越多样化，互联网应用的规模也随之扩大，因此互联网技术需要不断地发展变化才能适应新兴互联网业务发展的需要。以往的网络运营与建设模式将逐渐不能够满足新形势下网络融合的需求，新的应用模式与网络协议不断出现，网络虚拟化就是在这种形势下产生的。网络虚拟化主要通过抽象、分配及隔离机制实现在一个物理网络上独立运营多个虚拟网络，以有选择性地开展资源的调度与分配，从而实现物理网络资源利用率的最大化，同时提高网络服务的质量并降低维护与运营成本。该文就网络虚拟化技术中的虚拟网映射问题及其研究现状问题主要介绍了以下几个方面的内容。
1网络虚拟化及分层服务提供模型概述
作为一种有效应对克服当下互联网刚性问题的方法及技术手段，网络虚拟化技术可以被看作是互联网这几年发展与革新的主要趋势。网络虚拟化思想主要是将互联网划分成多个虚拟网络，实现互联网架构的多样化，每个虚拟网络都可以享用同样底层的物理网络资源，但能够实现不同的服务、应用于架构，这样就能达到多样化技术的应用与部署的目的。虚拟网络由虚链路连接的虚节点组成，并且虚节点与虚链路都处于物理网络的映射中。虚拟网络映射通过为不同需求的虚拟网络分配对应的物理资源来实现网络虚拟化，虚拟网络映射作为虚拟网络的基础还包括链路资源与节点资源。合理科学的映射算法既可以实现虚拟网的高效映射，也可以使物理网承载更多的虚拟网。
在网络虚拟化的服务环境中，主要应用分层的模式，通过建构虚拟网来实现各种业务服务。分层模型主要有三层，即应用层模式、服务层模式和资源层模式三层。在三层模式下，每一层的结构与功能彼此影响。SP（服务提供商）主要通过InP（基础设施提供商）提供的借口来管理虚拟网，并能够接入终端用户的虚拟网。在网络虚拟化的服务环境中，终端用户及传统的互联网终端用户一样，只是在虚拟化服务的环境中，每一个终端用户可以通过映射的方式来和多个SP同时建立不同的连接，从而来实现随不同的业务需求获得不同服务的目的。网络虚拟化分层服务所提供的模型如下（图1）所示。
2虚拟网映射问题与研究现状分析
作为构建虚拟网的一个比较重要的过程，虚拟网映射是映射较核心的功能。虚拟网映射主要依据SP的构建需求结合InP的资源状况，通过一定的映射算法在网络资源与构建需求间进行匹配，获取较科学合理的分配方案以进行嵌入，从而形成虚拟网。所以，在虚拟网映射过程中，映射主要实现的三大功能分别是接受并描述InP的资源信息、SP的虚拟网构建请求以及执行映射算法。在此，笔者就虚拟网映射与研究现状问题主要分析了以下几点内容。
1）网络资源概述。对InP的网络信息资源一般能够通过INSADL、NDI、NML等来描述。在对网络资源的描述过程中，任一网络元素就可以代表一个基本组件，例如链路、路径、节点和接口等。每一网络元素还有一个与之相对应的标示符、功能性或者非功能性属性、可用性参数。功能属性主要决定其属性、特征和网络元素的具体功能，非功能属性则主要决定了在虚拟网络中各个网络元素的限制及应满足的标准。节点可分为虚拟节点与物理节点两种，物理节点包含多个虚拟节点，同时一个物理或者虚拟节点可以拥有多个物理或者虚拟接口。其中接口的类型主要包括ATM接口、以太网接口及无线接口等。由于一个物理链路就可以支持一个或多个虚拟链路，因此每一个物理链路包含QoS参数及连接类型两个附加特征。
2）虚拟网的构建需求描述。虚拟网的构建需求与物理网络规划的需求很相似，主要关注的是网络拓扑结构、虚链路的带宽、虚节点的位置、路径的跳数限制、端口的类型以及QoS参数的配置等。虚拟网的构建与拆除，实质上主要是依据业务的需求对物理网络资源进行动态的分配和释放的过程。因此，虚拟网运行的生命周期也是虚拟网在构建需求上的主要参数。
3）虚拟网映射问题模型的描述。对于虚拟网的构建需求中操作系统OS及端口port类型等需求完全可以通过在映射前预先筛选InP所提供的各类资源。虚拟网映射问题的难点是怎样最大程度地实现InP利益。因为虚拟网映射要满足虚拟网构建需求中各个链路和节点资源的要求，而且还要充分地、高效地应用物理网络资源，达到在有限的物理网络资源上形成更多虚拟网，最大程度实现InP利益的目标。但是，虚拟网的物理网络资源有一自身的局限性、虚拟网的构建必须要求呈现出多样化的个性特征和虚拟网的构建请求动态化、即时处理化等特征。这样，虚拟网的映射问题实际的应用中还面对很对急需解决的问题与挑战。
4）映射算法中的各项评价指标。虚拟网映射算法要通过有效地采用提供商所提供的物理网络资源来满足服务提供商提出的构建要求。同时，映射算法的各项评价指标必须要通过网络资源利用率及虚拟网映射成功率等指标的计算来科学衡量。虚拟网映射的成功率是在构建申请中映射成功的虚拟网数，提高虚拟网的映射成功率就是要提高映射成功的虚拟网数。而提高物理网络资源利用率，关键在于如何在满足当下构建需求的前提下，更合理地为后续的虚拟网构建提供资源分布空间，为后续虚拟网的构建提供便利。
5）映射算法研究现状。目前来看，资源分布相对较均衡的物理网络逐渐成为虚拟网映射问题研究的方向。因为这样的物理网络可以提高网络资源的利用率和虚拟网构建的成功率。所以，当下对于映射算法的研究现状主要有以下几种情况：（1）Yong Zhu等研究人员把互联网资源假定为无限的，因此在构建虚拟网时，要综合考虑满足各个构建的具体要求，以便最大化的实现预定目标以最小化的链路承受最大量的负荷。（2）Robert Ricci等研究人员则通过避开物理网络中的各种瓶颈链路的方式来映射虚链路，不断提高虚拟网构建的成功率。（3）Jens Lischka等研究人员利用子图同构检测和回溯的技术把虚链路及虚节点同步映射到物理网络中，以此来提高构建虚拟网的成功率。（4）在虚拟网的映射中，一种W szeto基于多商品流问题而提出的对资源进行预分配的方法技术逐渐被提出来，该方式采用线性规划的方法来对映射问题进行建模求解。这种基于多商品流问题的模型很好地地解决了映射中资源分布均衡性的问题。（5）另外，MinlanYu等人提出了多径映射来提高网络资源的利用率。通过多径映射将虚拟链路映射到多条物理路径上，以此来提高物理网络的负载均衡，并利用多商品流问题的形式建模进行求解。多径映射法与多商品流问题模型的并用可以有效地解决映射中资源分布不均衡的问题，但是难以达到路径跳数的限制，所以一般只能通过单径映射的办法满足业务要求并有延时约束的构建需求。
3虚拟网络映射算法PBMC
1）PBMC算法的设计思路。众所周知，基于多商品流问题模型的虚拟网映射方法不能够解决路径跳数的约束要求问题，因此在多径映射时，虚链路的带宽很难通过路径的路径跳数来确定分配比。因此，在此基础上该文提出PBMC算法，即基于路径集多商品流问题模型的虚拟网映射算法。这种算法主要采用基于有效路径集的多商品流问题模型来规划和求解虚拟网映射问题的。在PBMC算法中，首先要结合各个物理链路的带宽需求和路径跳数的限制条件来计算出有效的物理路径集合。其次将路径的可用带宽视为决策变量，在符合虚链路带宽要求的前提下，运用多径映射的思想建立相应的数学规划，同时采用启发式的算法进行建模求解，最后实现链路的最大负载强度最小化。
2）建立数学规划。链路负载强度是链路上已占用带宽与链路带宽容量之比。PBMC算法的规划目标是建立链路的最大负载强度最小化。PBMC算法的约束条件有三个，分别为物理链路带宽容量约束、虚链路带宽需求约束及带宽占用的正则性要求约束等。
3）模型求解。在PBMC算法中，主要通过采用设计启发式的算法来求得近似最优解的方式进行求解。算法主要分为部分，首先要求证出初始的可行解；其次，对初始可行解迭代从而求解出近似最优解。在这种算法中，更多的考虑了局部的均衡问题，没有对整个虚拟网映射范围进行综合考虑，因此还需要做进一步的优化工作，对初始可行解进行优化。优化的思想主要是找出最大负载强度的链路，将该链路路径上的虚拟网迁移到其他的路径上，以此来降低链路的负载强度。
4）仿真实验。为了很好地与基于单径映射多商品流问题模型算法对比，可以采用基于Matlab的方式对PBMC算法进行仿真与模拟实验。在实验中，对虚拟网链路的带宽、构建请求的虚节点数、虚链路的带宽需求、跳数的限制、虚拟网申请的时间间隔均值以及生命周期均值等进行适当的设置。仿真实验中，要对比和分析的指标除了有构建成功率、资源、利用率外，还含有运营商收益及资源分布的均衡性两个指标。
5）仿真结果分析。
仿真实验中，将物理网络链路负荷的标准差、虚拟网构建的成功率、网络资源的利用率、物理网络运营商所收取的收益等进行综合分析，我们可以发现：基于单径映射多商品流问题模型算法，通过PBMC算法可以使得物理网络上各链路负载强度的标准差更小，因此物理网络资源的分布均衡性将得到更好的优化与实现。并且，通过更高的资源利用率及构建成功率，物理网络运营商才可以获得更多的收益。所以，本次仿真实验结果也说明相对于基于单径映射多商品流问题模型算法来说，PBMC算法不仅可以满足带路径跳数限制约束的虚拟网构建需求，还可以最大程度的优化网络资源分布的均衡性问题，不断提高网络资源的利用率。
4结束语
目前，网络虚拟化技术已经成为解决当下互联网僵化等问题的有效技术途径。在网络虚拟化技术中，虚拟网的映射实现网络虚拟化的基础。虽然对于网络虚拟化技术中的虚拟网映射问题国内外已经有了很大的突破，取得了较大的成绩，但在实际的运用过程中，仍然会出现这样那样的问题。因此，我们还需要不断引进新技术新方法，不断研究新的技术手段，更好地实现物理网络资源分布的均衡性，进一步提高网络资源的使用效率。
参考文献：
[1]汪斌强,邬江兴.下一代互联网的发展趋势及相应对策分析[J].信息工程大学学报,2009（10）.
[2]李文,吴春明,陈键,平玲娣.节点可重复映射和链路可分流的虚拟网映射算法[J].研究与开发.2010（7）.
[3]吕博.网络虚拟化资源管理架构与映射算法研究[D].北京邮电大学,2011.
路径规划典型算法范文5
【关键词】Dijkstra算法 矩阵迭代算法 交通 阻抗
1 引言
随着我国经济发展越来越快，城市交通运输路径也日趋紧张，在我国大中型城市中，普遍存在公共交通结构的不合理状况[1-4]。城市公共交通网络由众多路径及网络节点构成。由于城市人口和城市规模的不断增长，优化交通运输路径，解决交通出行者出行时间最小、服务最大化、线网效率最大等，方便居民出行[5-7]。在城市交通严重堵塞时，要使交通出行者出行便利，则必须对最短交通路径及交通状态信息进行实时全面了解；在一定程度上，这种信息诱导作用能对重点道路的拥堵起到缓解作用[8]。最短路径的算法有多种，对各种算法进行分析、理解、应用，比较这些算法的在实际应用效率，具有非常重要的实用意义[9-11]。通常情况下，典型最短路径问题算法有两种，分别为矩阵迭代算法、Dijkstra算法。本文基于这两种典型算法，对两者在最短路径问题中的差异性进行了对比，方便交通出行者对交通运输路径的选择。
2 最短路径及路网阻抗
在交通流分配中，最基本的算法就是最短路径算法。最短路径是指在一个网络中，已知相邻节点间的线路长度，要在某一起点到某一终点间找出一条长度最短的路线。在交通领域，最短路径研究较多，在路网中，因受道路条件、道路绕行距离、交通条件影响，使得不同交通路径，所需交通费用有一定的差异。在广义上，交通费用包括道路通行时间、通行距离、燃料的使用等；在狭义上，道路通行时间是阻抗，或将影响出行的其它因素进行折算，转化成通行时间，将其作为道路网交通阻抗，交通阻抗最小的路径就是最短路径。图1为路网的阻抗，表1为道路的可用阻抗矩阵。
3 Dijkstra算法和矩阵迭代算法
3.1 Dijkstra算法
最短路径使用最广泛、最基本的算法就是Dijkstra算法，在求网络中某一节点到其他各节点的最短路径时，网络中的节点被Dijkstra算法分成三部分，分别为最短路径节点、临时标记节点、未标记节点。在算法开始时，源点经初始化，转为最短路径节点，其他节点则为未标记节点。在执行算法时，从最短路径节点扩展到相邻节点，非最短路径节点的相邻节点每次都要修改为临时标记节点，对权值是否更新进行判断，权值最小节点从全部的临时标记节点中提取，在修改为最短路径节点后，将其作为下次扩展源，重复前面步骤，在全部的节点做过扩展源后，结束算法。
Dijkstra算法属于比较经典的最短路径算法，它可对一点到网络内所有节点最小阻抗进行计算，并将相应最短路径推算出。Dijkstra算法计算步骤共5步，第一步是将Dijkstra算法起始点进行标号，记为P，且P（o）=0，其余节点标号为T，且除T（0）外，其余节点的T（i）=∞；第二步是将o点相邻点向量r找出，即dor（i）≠∞，对所有标号为T的值进行比较，找出最小值，即P（k），T最小时所在的点为k点；第三步是按照第二步方法，将k作为起始点，满足T（r（j））=minT（r（j）），P（k）+dkr（i），将最小值所在点k/找出，记P（k/）；第四步是迭代第三步，在全部节点被标志为P后，则求出了o点到其余节点的最小阻抗；第五步是根据所需，对目标点进行查询，以目标点d为起始点，将满足式P（j）=dij+P（i）的i点找出，最短路径中j的前一点就是i点，对i点之前的点进行继续搜索，同样根据P（j）=dij+P（i），直到搜索起点o，图2为Dijkstra算法程序流程图。
3.2 矩阵迭代算法
矩阵迭代算法首先要构造距离矩阵，在矩阵中，给出了节点间经过一步到达某一点的距离，见图3，通过距离矩阵的迭代运算，两步到达某一点的最短距离就得到了。因此，使用矩阵迭代算法研究最短路径问题时，各出行节点间最短路线要知道。
在D（4）=D（3）时，具有最短距离矩阵，通过矩阵，可将最短距离计算出。通过反向追踪，对相应最短路线进行确定。
矩阵迭代法指的是从路径集合中进行挑选，将最短路径分步选出来，完成矩阵迭代，则表明可计算出每一对od点间的最短路径。迭代矩阵算法思想类似于Dijkstra，不同的是其采用矩阵形式对最短路径问题的进行思考，也就是在od两点间，尝试性选择中间路径，计算每个可能的中间路径，并将最小节点选出，并进行迭代计算，得出到达该最短路径是要经过几个中间节点。当所有节点最短路径迭代全部求出后，矩阵迭代结果保持稳定，不再变化，这时表明迭代结束。
矩阵迭代算法的计算步骤共4步，第一步是给定od，其阻抗方阵为D，D1=D，按照公式dij（2）=min（di1（1）+d1j，di2（1）+d2j，…，din（1）+dnj），n表示矩阵阶数n，i=1～n，j=1～n。根据此公式，将两步到达目的地最小阻抗计算出，D2为得到的新矩阵。当dik+dkj达到最小时，将k值记为k（1），也就是最短路径中的一点；第二步是根据公式dij（3）=min（di1（2）+d1j，di2（2）+d2j，…，din（2）+dnj），n表示矩阵阶数n，i=1～n，j=1～n，得到D3。最小值对应点记为k（2）；第三步则依次类推，dij（m）=min（di1（m-1）+d1j，di2（m-1）+d2j，…，din（m-1）+dnj），n表示矩阵阶数n，i=1～n，j=1～n，得到Dm，最小值对应点记为k（m-1），直到Dm=Dm-1；第四步是对目标最小阻抗od即dodm进行搜索，i、j两点间最小阻抗表示为dijm。在标志点o，k（1），k（2），…，k（m-1），d中，x取最短路径，为避免某些点会出现重复，按照didm=dik+dkdm的路径顺序原则进行确定，i起始于o点，根据标志点顺序，依次进行检验，最短路径就是符合要求的点向量。图4为矩阵迭代算法程序流程图。
4 两种算法的比较
通过MatLab平台，进行矩阵迭代算法、Dijkstra算法的编程，MatLab能将计算过程及结果显示出来，通过profiler功能，能将计算时间显示出来。
4.1 最短路径收敛性
矩阵迭代算法、Dijkstra算法的收敛特性由路阻矩阵及计算思路特点决定。因此，使用用计算机计算是可行的。在相邻节点，Dijkstra寻找过程中，向目标节点步步靠近，当最后的终止条件满足后，达到查询终点，起始点到其他点的最小路径能计算出。因路阻矩阵特殊性，在矩阵迭代算法中，矩阵对角线位置元素均为零，目标节点就是最终收敛点，矩阵收敛的充要条件是对角线上的零元素。
4.2 两种方法异同点
相比于矩阵迭代算法而言，使用Dijkstra算法，可将一点到其他各点的最小阻抗一次性求得，根据最短路径，最短路径经过的节点可依次得到，在进行最短路径的计算时，需要反复进行，同时不能颠倒起始点到其他各点最小阻抗的计算顺序，按照步骤严格进行，因而，Dijkstra算法计算效率低，收敛速度较慢。相比于Dijkstra算法而言，矩阵迭代算法则非常简洁，要求不苛刻，矩阵迭代计算效率提高的方法有三个比较可行。第1个是在矩阵迭代算法中，每一步只要遵循dij（m）=min（di1（m-1）+d1j，di2（m-1）+d2j，…，din（m-1）+dnj），n表示矩阵阶数n，i=1～n，j=1～n原则，在i，j间，其迭代顺序限制不严格，可并行进行计算，这样就可使计算速度大大提高；第2个是可以同时设计程序，使计算值避免出现∞数据，只对非∞数据与其下标策略进行存取，这样内存空间就得到节约，从而使计算效率得到提高；第3个由于阻抗矩阵属于对称矩阵，在不断进行迭代后，阻抗矩阵仍属于对称矩阵，根据这一特征，每次迭代的计算量可减少。若道路阻抗是负数，则可能Dijkstra算法会出现无效，在矩阵迭代算法中，道路阻抗可为负数，图5为矩阵迭代算法中的道路阻抗。
4.3 计算效率比较
在计算程序中，MatLab内含的程序测试器profiler，具有一定的优越性，因此本研究采用MatLab平台进行Dijkstra算法、矩阵迭代算法的编程，并计算同一路网，在得到相同结果时，对各个计算效率指标进行比较，在计算效率方面，显示Dijkstra算法、矩阵迭代算法的不同。在重庆市路网上随机选取8个终点及起点，对起始点1点到8点的最短路径及阻抗进行计算。在程序算法分析里，时间复杂度是非常重要的内容，时间复杂度通常是指算法中执行基本运算的次数，影响时间复杂度的因素较多，本研究主要对影响时间复杂度的重要因素进行分析，比较Dijkstra算法、矩阵迭代算法的时间复杂度，表2为两种方法计算时间，表3为Dijkstra算法的计算结果，表 4为矩阵迭代算法计算结果。
对起始1点到8点的最小路阻采用Dijkstra算法进行计算，结果为P（8）=5，其相应的最短路径为14568。对起始1点到8点的最小路阻采用迭代矩阵算法进行计算，结果为D1（1，8）=5，其相应的最短路径为14568，结果相同。但Dijkstra算法和迭代矩阵算法的计算效率有一定的差距，从表2可以看出，Dijkstra算法所用时间为0.673s，迭代矩阵算法所用时间为0.501s，矩阵迭代算法的计算速度更快。矩阵迭代法可全部算出路网中两点间的最小阻抗，Dijkstra算法仅能算出起始点到其他各点间的最小路阻；路网中的节点远比8多很多，采用Dijkstra算法要进行上万次的循环，使计算速度大幅降低，使用迭代矩阵算法，则迭代次数远比节点数小，因此，迭代矩阵算法优势更大，同时对于路阻为负的路网，可通过矩阵迭代进行计算，即对于更广泛的最短路径，迭代矩阵算法能适合其计算要求。
基本运算次数与运算所需时间的乘积即就是算法执行时间，为进一步比较Dijkstra算法和迭代矩阵算法的计算效率，本研究将两程序对中取出4×4、6×6、8×8共3个矩阵进行计算，对运算时间进行比较，分别对交通运输路网中任意2点间的最小阻抗进行计算，表5为计算时间参数数据。
从表5可以看出，在矩阵4×4、6×6、8×8中，矩阵迭代算法的运算时间均比Dijkstra算法的运算时间要小，其迭代次数次数也远远小于Dijkstra算法的迭代次数，这进一步表明，矩阵迭代算法的计算效率要比Dijkstra算法的计算效率高。
5 结论
本文基于矩阵迭代算法及Dijkstra算法，对两者在最短路径问题中的差异性进行了对比，得出以下结论：
（1）通过Dijkstra算法，对于一点到其他各点的最小阻抗可一次求得，最短路径经过的节点可依次得到，该算法在进行最短路径的计算时，需要对相点进行反复搜寻，计算效率较低，收敛速度较慢。
（2）矩阵迭代算法是元素间比较、数列间相加的过程，特点是简单快捷。矩阵迭代算法没有严格路径次序限制迭代顺序，可实现算法并行计算，计算速度较高。在阻抗矩阵为对称矩阵时，在经过迭代后，得到的矩阵仍为对称矩阵，这样可使每次迭代的计算量得到减少。
（3）通过在重庆市路网上随机选取8个终点及起点，对起始点1点到8点的最短路径及阻抗进行计算表明，Dijkstra算法所用时间为0.673s，迭代矩阵算法所用时间为0.501s，矩阵迭代算法的计算速度更快。在矩阵4×4、6×6、8×8中，矩阵迭代算法的运算时间均比Dijkstra算法的运算时间要小，其迭代次数次数也远远小于Dijkstra算法的迭代次数，这进一步表明，矩阵迭代算法的计算效率要比Dijkstra算法的计算效率高。
参考文献
[1]张美玉，简b峰，侯向辉，等.Dikstra算法在多约束农产品配送最优路径中的研究应用[J]，浙江工业大学学报，2012，40（03）：321-326.
[2]Niehols，Jolin M.A major urban earthquake： planning for arma-geddon[J]，Landscape and Urban， 2005，73，2：136-154.
[3]刘洪丽，顾铭.矩阵迭代法在物流中心选址中的应用分析[J]，现代商贸工业，2013（20）：64-67.
[4]丁浩，苌道方.基于Dijkstra算法的快递车辆配送路径优化[J]，价值工程，2014（03）：15-18.
[5]郭瑞军，王晚香.基于矩阵迭代法的出租车合乘最短路径选择[J]，大连交通大学学报，2011，32（04）：28-32.
[6]任鹏飞，秦贵和，董劲男，等.具有交通规则约束的改进Dijkstra算法[J]，计算机应用，2015，35（09）：2503-2507.
[7]王树西.改进的Dijkstra最短路径算法及其应用研究[J]，计算机科学，2012，39（05）：223-228.
[8]刘春年，邓青菁.应急决策信息系统最优路径研究-基于路阻函数理论及Dijkstra算法[J]，灾害学，2014（03）：7.
[9]潘若愚，褚伟，杨善林.基于Dijkstra-PD-ACO算法的大城市公交线路优化与评价方法研究[J]，中国管理科学，2015，23（09）：106-116.
[10]王佳，符卓.综合客运枢纽接运公交线路优化设计[J]，系统工程，2012，30（05）：101-106.
[11]高明霞.基于双层规划的交通疏散中车辆出发与交通控制综合优化[J]，中国管理科学，2014，22（12）：65-71.
作者简介
肖鹏（1980-），男，江苏省镇江市人。硕士学位。现为江苏城乡建设职业学院基础部讲师。研究方向为应用数学。
路径规划典型算法范文6
关键词：蚁群算法；无线网络；路由协议；路径选择；性能优化
DOIDOI：10.11907/rjdk.161913
中图分类号：TP393
文献标识码：A文章编号：16727800（2016）010017604
0引言
由于社会发展的需要，传统有线网络无法满足用户更多类型的应用需求，公众对无线通信领域的应用标准不断提高，面向无线通信网络的应用加剧了提升通信效率方面的开发幅度和性能要求，受限的无线媒介与实际应用的需求矛盾逐渐凸显[12]。路由协议是运行于网络层的信息转发策略，性能优越的路由协议能够使消息的传递过程更加顺畅，使通信客户端可以通过最优的路径将信息传递给其它客户端，有效提升了网络的整体性能。无线通信协议的路径选择示意如图1所示，目前针对路由协议的开发仅仅局限在网络层本身，并没有将其与实际的数据应用相结合，通过信息手段将当前网络状况与实际协议开发相结合是目前行业发展的新趋势[34]。
目前，很多专家学者针对无线环境下的路由协议进行了研究。为了解决分布式编码感知路由协议中可能出现的吞吐量降低的问题，王春雨等[5]设计了一个能够进行网络编码的无线通信路由协议，达到了提升系统吞吐量的目的。IP数据包广泛应用于分布式通信网络，迫切需要网络具有自组织能力。由于单通道单一接口模型不满足复杂系统的需求，Jin等[6]建立了一个面向军事应用的分布式网络拓扑结构，并实现了基于ZRP 的多渠道M-ZRP路由协议。仿真结果表明，M-ZRP具有更好的性能。
蚁群算法（Ant Colony Optimization，ACO）是根据蚂蚁群落采集食物的原理被提出和模拟而来，已被应用于诸多领域。与基于梯度的性能优化算法原理不同，蚁群算法通过概率搜索算法来完成[78]。虽然概率搜索算法一般需要采用价函数，但是与传统的梯度演化算法相比，其有诸多比较显著的性能，集中表现在以下方面[911]：①无集中控制约束，不会因个别个体的故障影响整个系统问题的求解，确保了系统更强更稳定的鲁棒性；②以非直接通信形式保证系统的可扩展性；③采用并行分布算法模型和多处理器运行模式；④定义问题的连续性没有限制；⑤算法实现相对比较简单。
OPNET Modeler中的WLAN 、MANET等无线通信节点模型提供了多种成熟的路由协议，包括按需距离向量路由（Ad hoc On Demand Distance Vector，AODV）、动态源路由（Dynamic Source Routing，DSR）、地理路由（Geographic Routing Protocol，GRP）等[1213]。
针对无线网络中存在的问题，本文提出了基于TSP蚁群算法的无线通信路由协议优化设计方法，此优化设计将TSP基本蚁群算法的基本原理和通信路由选择相结合，通过建立系统模型，依靠蚂蚁信息素含量及距离竞争机制为节点选择最优通信路径。同时，本文通过在OPNET Modeler通信仿真软件中建立仿真场景及完成模型构建，对基于TSP蚁群算法的无线通信路由协议进行测试验证，并与其它典型无线路由协议进行对比分析，主要分析指标是传输延时及吞吐量。
1基于TSP蚁群算法的路由协议优化设计
1.1TSP蚁群算法模型
式中，Q为常数，表示蚂蚁寻找路径过程中所释放信息素总量，它在一定程度上影响算法的收敛速度，本文中的Q值通过仿真获得。本文采用的AntCycle模型，其利用的是系统全局信息，此信息更新策略能够使较短路径上对应的信息素逐步增大，保证了算法中整体范围下较短路径的生存能力，提升了信息正反馈性能，加快了系统搜索路径的效率。同时，AntCycle模型的更新规则能够保证残留信息不造成无限积累，如果某条路径没有被选中，则对应节点的信息素含量会随着时间的推移渐渐消失，使节点具备逐步淘汰劣质路径的能力，即使某条路径经常被访问也不至于因为τij（t）的积累，而出现τij≥ηij的情况，使得期望值的作用无法体现。因而，本文的蚁群算法采用AntCycle模型。
1.4路由协议设计与实现
针对求解TSP问题的蚁群算法模型，对此模型进行修改，同时结合无线自组织网络信息传输的特点，完成基于蚁群算法的路由协议设计，简称ACAB（ Ant Colony Algorithm Based）路由协议，具体实现步骤如下：Step1：初始化各通信节点间的距离。此操作通过节点广播信息完成，每个节点被分配不同的ID，作为其在此过程中的唯一标识，广播的数据帧格式如图2所示，包括节点ID属性，当前位置坐标（x，y），是否为源节点或目的节点，如果有数据发送需求，源节点属性值赋值为1，同时将目的节点的ID进行赋值，并对发送序列进行编号，如果没有数据发送需求，则置为0。
Step2：将若干蚂蚁放在不同的通信节点中，每个通信节点维护自身的信息素列表，表中描述了当前节点的信息素含量和此刻与其它节点间的距离。信息列表的具体信息如图4所示。当节点位置移动后，此表中的数据也进行更新。Step3：每只蚂蚁根据各节点至目的节点的距离d和信息素水平τij（t），选择下一通信节点，同时修改禁忌表。Step4：所有蚂蚁完成周游后，更新信息列表中的信息素水平和节点位置信息。Step5：返回Step2，迭代次数d=d+1，直至寻找到源节点与目的节点间的最优路径或者满足结束条件，最优路径的判定标准是路程最短min（Road），摒弃不必要的路径信息。
2仿真实现及分析
通过在OPNET Modeler中建立仿真对比场景，对提出的基于TSP蚁群算法的无线通信路由协议与典型的AODV、DSR路由协议进行对比验证，分析其在传输延时及吞吐量方面的性能表现。
2.1仿真场景建立及模型实现
OPNET Modeler采用离散事件驱动的模拟机理，通过事件驱动器以先进先出的机制对事件列表和事件时间列表进行维护管理[15]。本文设计的仿真场景中包含的通信节点由WLAN节点组成，可以通过设置其属性对其进行控制。仿真范围为1 000m2，仿真时间为30min。仿真过程中通信节点可以随机移动，物理层与数据链路层均采用基本IEEE 802.11协议，通信节点总数初步设为100，数据发送间隔为100ms，基本数据帧大小为100字节，仿真场景如图3所示。
同时，WLAN节点包含完整的OSI协议模型，本文的路由协议设计在IP层自定义完成。通信信息从WLAN收信机进入，依次经过MAC层、数据链路层、IP层、UDP层、路由层、应用层，完成整个消息的通信流程[16]。对消息的处理过程由traf_src进程模型完成，负责应用层相关事务。
2.2基于TSP蚁群算法的路由协议测试验证
为了验证优化后路由协议的通信性能，本文将基于TSP蚁群算法的路由协议优化设计方法与传统的AODV及DSR路由协议进行了对比仿真。在仿真的20分钟内，节点的信息素逐步累积，不同的数据请求序列针对不同的信息素标识，完成数据传输后，对应此路径的信息素被清除，以节省系统容量。由于节点均为随机移动，各节点的平均信息素水平基本相同，体现了本协议优化方法的公平性。
为了更直观地体现通信性能的变化，本文通过传输延时和吞吐量对网络性能进行描述分析。
为了体现系统整体性能，本文统计平均传输延时，假设成功发送N组数据，则计算如下：
=1N・∑Ni=1D（i）（10）
式（10）中，D（i）表示第i个分组的传输延时。网络的吞吐量TH是指在正常情况下系统在单位时间内所有节点正确接收的信息量，单位是bit/s或是M/s。吞吐量描述了网络可以完成通信任务的程度，是衡量自组织网络通信质量的重要指标。
Th（i）m=ΔRp（i，m）ΔT（i，m） （11）
ΔRp（i，m）是指数据分组i到数据分组m被目的节点接收时系统已传输的信息总量，ΔT（i，m）是数据分组i到数据分组m被接收时两者的时间差。若i>m，表示计算从第m个分组到第i个分组的吞吐量，若m=1，则结果是平均吞吐量。
图4的仿真结果表明，在传输延时方面，提出的优化路由协议较AODV协议、DSR协议分别减少了7.5%和9.8%；在吞吐量方面，提出的优化路由协议较AODV协议、DSR协议分别提高了8.4%和7.8%。信息素含量如图5所示，仿真过程中信息素含量基本维持在110单位左右，较稳定。这表明本文设计的基于TSP蚁群算法的无线通信路由协议较经典的协议效果有所改进。优化协议性能突出的原因是通过蚂蚁信息素对路径进行规划和最优化选择，使得劣质路径在选择的过程中被淘汰，但是需要指出的是，前期为了蚂蚁寻找路径而广播的信息也加大了系统负担，隐含在一部分吞吐量数据中，对仿真结果也产生了一定的影响。但总体而言，本文设计的ACAB路由协议效果较为突出。
3结语
通过分析无线网络传输的基本原理及蚁群算法的运算过程，本文提出了基于TSP蚁群算法的无线通信路由协议优化设计方法。此优化设计将TSP基本蚁群算法的基本原理和通信路由选择相结合，通过建立系统模型，依靠蚂蚁信息素含量及距离竞争机制为通信节点选择最优的通信路径。同时，本文在OPNET Modeler通信仿真软件中建立仿真场景并完成模型构建，对基于TSP蚁群算法的无线通信路由协议进行测试验证，并与其它典型无线路由协议进行对比分析。仿真结果表明，在传输延时方面，提出的优化路由协议较AODV协议、DSR协议分别减少了7.5%和9.8%；在吞吐量方面，提出的优化路由协议较AODV协议、DSR协议分别提高了8.4%和7.8%。总之，本文设计的基于TSP蚁群算法的无线通信路由协议优化设计方法效果突出。
同时，本文也存在一定的弊端，例如，蚁群算法必然会增加诸如信息素之类信息维护的额外成本，并且关于模型实现会影响底层协议的运行。笔者将在今后的工作中着重对以上不足之处进行研究改进。
参考文献参考文献：
[1]LOVE D J，HEATH R W，LAU V K N，et al.An overview of limited feedback in wireless communication systems[J]. IEEE Journal on Selected Areas in Communications，2008，26（8）：13411365.
[2]XIE L L，KUMAR P R.A network information theory for wireless communication： scaling laws and optimal operation[J].IEEE Transactions on Information Theory，2004， 50（5）：748767.
[3]SURHONE L M，TENNOE M T，HENSSONOW S F，et al. Wireless routing protocol[M].Betascript Publishing，2010.
[4]王磊，施荣华.无线传感器路由算法中的仿真研究[J].计算机仿真，2011，28（3）：170173.
[5]王春雨，张曦煌.Ad Hoc网络中基于网络编码的无线路由协议研究[J].计算机工程与设计，2013，34（5）：15631567.
[6]JIN H，REN L，DING Y.A hierarchical wireless routing protocol for multichannel multiinterface ad hoc networks[C].2011 7th International Conference on Wireless Communications，Networking and Mobile Computing （WiCOM），2011：14.
[7]SBESTER A，FORRESTER A I J.Ant colony optimization[J].Alpha script Publishing， 2010，28（3）：11551173.
[8]MARTENS D，BACKER M D，HAESEN R，et al.Classification with ant colony optimization[J].IEEE Transactions on Evolutionary Computation，2007，11（5）：651665.
[9]ASIM M，DUNYUE L，MICHAEL C.Analysis and synthesis of an ant colony optimization technique for image edge detection[C].2012 International Conference on Computing Sciences，2012：127131.
[10]BLUM C，DORIGO M.The hypercube framework for ant colony optimization[J].IEEE Transactions on Systems Man & Cybernetics Part B Cybernetics a Publication of the IEEE Systems Man & Cybernetics Society，2004，34（2）：11611172.
[11]YI W，KUMAR A.Ant colony optimization for disaster relief operations[J].Transportation Research Part E Logistics & Transportation Review，2007，43（6）：660672.
[12]任敬安，涂亚庆.基于蚁群优化的AdHoc网络路由协议实现[J].计算机工程，2012，38（21）：114118.
[13]ZAPATA M G，ASOKAN N.Securing ad hoc routing protocols[C].Proceedings of the 1st ACM workshop on Wireless security. ACM，2002：110.
[14]YU B，YANG Z Z，YAO B.An improved ant colony optimization for vehicle routing problem[J]. European Journal of Operational Research，2009，196（1）：171176.
