基于混合粒子群算法的 Ad Hoc 路由协议研究.doc

基于混合粒子群算法的 Ad Hoc 路由协议研究陈玮 1，饶妮妮 1，廖瑞华 2，王炜华 21 电子科技大学生命科学与技术学院，成都（610054）2 空军装备研究院通信所， 北京（100085）E-mail: chenweiflysohu.com摘要: 针对当前 Ad Hoc 路由协议在动态变化迅速的自组网中存在时延过大问题，本文引入粒子群优化算法，结合遗传算法对其改进，形成了适用于路由问题的混合粒子群算法。研 究基于混合粒子群算法的路由协议，在网络仿真软件 OPNET 上将其实现，并进行仿真实验。 与比较成熟的 Ad Hoc 按需路由协议 AODV 的仿真结果对比表明，新协议减小了网络的端到 端时延，更适合于动态变化大的 Ad Hoc 网络。关键词：Ad Hoc 网络；路由协议；混合粒子群算法；AODV；OPNET中图分类号：TP3931引言自组网（Ad Hoc，Wireless Network Without Infrastructure）是一种能够临时快速自动组 网的移动通信技术1。它不需要预设的网络基础设施，具有很强的抗毁性，故被广泛应用于 各种临时通信场合。路由协议是当前自组网技术的研究热点2，目前已有多种路由协议草案 被提出。按照路由建立方式分为主动路由协议和按需路由协议，其中后者适用于大规模，网 络拓扑变化迅速的环境。但是，由于它们大多采用洪泛机制，如 AODV3，使网络性能受到 制约。随着 Ad Hoc 技术的迅速发展，迫切需要能使网络性能更加优越的路由算法。粒子群算法(Particle Swarm Optimization, PSO)是一种基于群智能的迭代优化计算技术， 它最早由 Kennedy 和 Eberhart 于 1995 年提出 45，其基本思想源于对鸟群捕食行为的研究。系统初始化为一群随机粒子(随机解)，然后通过迭代找到最优解。在每一次迭代中，粒子通 过跟踪全局极值和局部极值来更新自己，使粒子始终跟随最优粒子运动。PSO 流程简单， 参数简洁，被广泛应用于各种目标优化问题6，如决策调度7，图像配准8，天线阵列优化9等。对于路径优化问题，PSO 已被用来解决 TSP10，车辆路由选择11和 Ad Hoc 网络 QoS路由121314。 本文结合遗传算法，对PSO进行改进，提出适用于路由问题的混合粒子群算法(HPSO，Hybrid Particle Swarm Optimization)；然后按照按需路由协议机制，设计了一种基于HPSO的Ad Hoc路由协议框架。在OPNET网络仿真软件上将其实现后进行系统级仿真实验，同时在 相同网络环境下与AODV协议进行比较。2Ad Hoc路由问题的数学描述把网络看成一个赋权无向图 G= (V, E) ，其中 V 是 G 中所有节点的集合；E 为 G 中任 意两相邻节点 x, y 之间链路的集合。对于 E 中每条链路 e = ( x, y) ， x, y V ，均有某种非 负加权函数表示其属性，如 D(e) 描述链路的延时，本文选择延时 D(e) 作为链路的属性。Ad Hoc 路由问题的数学描述为：已知源节点 s V 和目的节点 d V ，寻找路径 P(s, d ) ， 使经过该路径的数据包延时 D(e( x, y) 达到最小。e( x, y )P ( s ,d )3基本粒子群算法（PSO）基本粒子群算法（PSO）是基于群体和适应度概念，通过“群集智能”15 求解目标函数 f(x)- 9 -的最优值问题。该算法能迅速找到某个或某些 x，让 f(x)达到或接近最优值。其中 x 是 N 维向量，当 N 为 1 时，x 为标量。算法的执行框架如下：1） 根据优化目标函数 f(x)，在自变量 x 的取值范围内随机产生 n 个 x 值作为初始粒子，同 时随机产生 n 个初始速度对应于各粒子。2） 根据当前的位置和速度，依照下面公式更新每个粒子的速度和位置。vk +1 = c0vk + c1 ( pbestk xk ) + c2 (gbestk xk ) (1) xk +1 = xk + vk +1(2) 其中，k 代表迭代次数， vk 是粒子的速度向量， xk 是当前粒子的位置， pbestk 表示粒子本身所找到的最优解位置， gbest 为整个群体目前找到的最优解位置。 c 是惯k 0性权重，促进粒子向新空间搜索； c1 ， c2 为加速因子，分别表示粒子向局部极值和全 局极值的趋向程度。3） 计算各个粒子新位置的目标函数值。对每个粒子，若新值优于原来的个体极值 pbestk ， 设置新值为 pbestk ，否则 pbestk 不变。再从各个粒子的个体极值里选出最优的一个作 为全局极值 gbestk 。4） 检查 gbestk 是否达到要求或迭代次数是否已达最大值。若条件满足，输出 gbestk 及最 优目标函数值；否则返回步骤 2）继续迭代。PSO 主要处理连续性优化问题，通过发挥粒子群体的功能使优化函数很快达到最优值。4适用于Ad Hoc网络环境的混合粒子群算法(HPSO)设计基本粒子群算法适用于连续性优化问题。对于路由选择，由于路径是独立的，相互间无 连续关系，故路由是一个离散性优化问题。同时，路径由它所包含的节点组成，直接利用基 本粒子群算法不能对路径进行加减运算，故需要有一种相对于 PSO 速度及位移公式的等效 形式，才能用 PSO 解决路由问题。因此，本文借鉴遗传算法的思想， 设计了一种混合粒子 群算法，为 Ad Hoc 网络路由设计提供理论依据。4.1 粒子编码设计对于路由问题，路径即为粒子群算法中的粒子，不同的粒子代表不同路径。每个粒子是 一条路径途经节点序列号的集合，序列号的排列基于数据包从源节点出发依次经过中间节点 的顺序。故路径所包含的节点序列号按序排列即为粒子的编码形式。例如：路径（1，3，5，7，11，23，6，9，10，17）作为一个粒子，它表示数据包从源 节点 1 依次经过中间节点 3，5，7，11，23，6，9，10 到达目的节点 17。针对节点数目小于 150 的中小规模 Ad Hoc 网络，预设源节点到目的节点的最大路由跳 数为 10，这样可减轻因跳数过大引起的数据包在传输过程中的较大网络开销。基于最大路由跳数限定，数据包传输路径（粒子）有以下三种情况：1） 当传输过程中的跳数大于 10，该路径被废弃。2） 当传输结束后的跳数等于 10，路径为按序排列的节点序列号集合。3） 当传输结束后的跳数小于 10，先按序排列途经的节点序列号，不足 10 跳的部分以-1 填补。如：路径（1，4，6，8，15，3，17，-1，-1，-1）表示数据包从源节点 1依次经过中间节点 4，6，8，15，3，17 到达目的节点 17，共 7 跳。4.2 速度及位移公式的等效形式设计基本粒子群算法速度公式中的相减代表粒子向极值靠近，速度与常系数 c0相乘表示粒子向新空间搜索。这两种运动趋势与遗传算法中交叉和变异的效果颇为相似。在遗传算法中， 交叉是用最优基因片段替代普通基因的相应位置，使普通基因趋近于最优基因；变异让普通 基因具有较大的变化范围，可向更广阔的空间探索。由于以路径为编码的粒子很容易应用交 叉和变异算子，故采用这两个算子等效粒子群算法公式的相应子项。（1） c2 ( gbestk xk ) 的等效 因为该项表示粒子向全局最优值逼近，故可将其等效为交叉算子。根据遗传算法中对应位交叉的思想，结合路由问题中的有限跳数及首尾项不能改变的原则（它们分别为源节点和 目的节点），用 gbest 的第二、三项取代 x 的第二、三项。 例如，gbest=(1 3 7 5 10 15 2 4 6 8) ， x=(1 2 5 6 11 13 3 9 10 8)交叉后，x=(1 3 7 6 11 13 2 9 10 8) 。这种等效表示普通路径向全局最优路径的逼近。（2） c1 ( pbestk xk ) 的等效 因为该项表示粒子向局部最优值逼近，故可将其等效为交叉算子。根据对应位交叉的思想，并与粒子和全局极值的交叉操作相区别，将 x 的第二、三项用 pbest 的第二、三项取代， 第四、五项分别用 pbest 的第五，四项取代。例如，pbest=(1 3 7 6 11 13 15 9 10 8) ， x=(1 2 5 12 14 13 15 9 10 8)交叉后，x=(1 3 7 11 6 13 15 9 10 8) 。这种等效表示普通路径向局部最优路径的逼近。（3） c0 vk 的等效 因为该项表示粒子向新空间拓展，故可将其等效为变异算子。利用遗传算法中的调位变异策略，将 x 的第二项用第六项值替换，原先的二至五项移至三到六项。例如，x=(1 3 7 11 6 13 15 9 10 8) ；变异后， x=(1 13 3 7 11 6 15 9 10 8) 。这种等效表示 普通路径向新空间搜索，以求找到新的路径。（4）加法运算的等效 加法表示几种处理的总和，故粒子群算法各子项的等效处理综合起来即是加法的效果。在加法等效中，前一步处理的输出作为后一步的输入。 运用粒子编码并运用速度位移公式的等效形式后，便可用混合粒子群算法来解决路由问题。混合粒子群算法执行流程与基本粒子群算法的相同，只是粒子更新时采用速度位移公式 的等效形式。另外，为了保护最优路径信息，不对当次迭代运算的最优粒子（最优路径）做 更新处理。若经过计算，非最优粒子的效果好于最优粒子，则效果好的粒子作为最优粒子， 曾经的最优粒子变为普通粒子，可在下一轮迭代运算时进行更新。5基于混合粒子群算法的路由协议的设计思想对于动态变化较快的 Ad Hoc 网络，采用按需路由策略更适合于相应的网络环境。按需 路由是指仅当源节点有发送数据包需求时，才进行相应的路由发现过程，按需建立路由表。 按需路由协议一般包括路由发现和路由修复两部分。本文基于混合粒子群优化算法的按需路 由协议即是从这两方面进行设计的。5.1 路由发现传输数据前，各节点首先初始化自己的属性，预设最大跳数值（本文设置为 10）和跳 数旗帜值（大于 10，避免无环路由）。路由发现步骤如下：（1）源节点有传输数据需求时，向外广播发送路由请求包。（2）中间节点接收到请求包后，从包中提取跳数属性值，它表示该请求包已经历节点 的个数。将中间节点的跳数旗帜值与包中跳数属性值比较后，做如下处理： a.若包中跳数小于等于跳数旗帜值，则令跳数旗帜值等于包中的跳数值，同时将包中的跳数值加 1，并把中间节点的地址加入包中的路由表，将该包继续以广播方式传播。b.若跳数大于中间节点的跳数旗帜值，节点的跳数旗帜值不变，同时注销该请求包， 使其不向其他节点传播。此举可避免路由环路发生。（3）目的节点接收到请求包后，检查已接收请求包数目是否达到预定值。a. 若没有，从包中提取出路由表及请求包传输延时信息，存入目的节点缓存。 注销该包，等待下一个请求包的到达。b. 若达到一定数目，则将所有接收请求包的路由表从缓存中提取出，作为“粒子”， 同时提取出它们的传输延时信息，作为相应“粒子”的适应值。然后根据混合粒 子群算法 (HPSO) 迭代，计算出延时较小的三条路径，其中最小的是最优传输 路径，其余两条为备用路径。（4）目的节点沿三条路径逆向发送确认包回源节点，途经的中间节点将记录下路由表 中相对自己的前一跳和下一跳。（5）源节点接收到确认包后，将沿着最优路径传输数据包到目的节点。 路由发现的流程框图如图 1 所示。图 1 基于 HPSO 的路由发现流程5.2 路由修复（1）链路中断的检测网络内每个节点不断发送 hello 包给其邻节点，并接收它们的回复信息。若在规定时间 内没有接收到回复信息，则说明这两个节点之间的链路断开。（2）断链的处理 当节点之间的链路断开时，断链处的上游节点将沿路径逆向传输修复包回源节点，请求采用备用路径进行传输。若三条路径均已失效，则源节点启动新一轮路由发现过程。6仿真实验与结果分析仿真工具选用网络仿真软件 OPNET，在 MAC 层选用 802.11b DCF 协议，网络层是自 己设计的进程模型，用来实现混合粒子群路由协议(HPSO)。仿真场景根据随机位点模型（Random Waypoint Model，RWM)，由一些随机放置的可移动节点组成。在相同网络环境 下，分别对 HPSO 和 AODV 进行仿真。6.1 仿真参数仿真实验中设置的实验参数如表 1 所示。表 1 仿真实验参数参数名称数值仿真区域2000 米*1500 米 仿真时间180 秒节点数目120节点运动速度5，10，15，20，25，30，35（单位：米/秒） 节点停留时间5，10，20，40，60，80，100（单位：秒） 节点最大通信距离300 米移动模型RWM 随机位点模型6.2 仿真实验结果与分析（1）节点运动速度不同，停留时间相同（实验中分别设为 10 秒和 30 秒两种情况） 实验结果如图 2 和图 3 所示。由两图可知，速度相同时，HPSO 在大多数情况下的端到端延时小于 AODV。这是因为 HPSO 采用多径策略，充分利用群体最优值使每条路径能 够综合自己和全局最优值产生出较好路径（延时小）。随着节点运动速度的增加，HPSO 的 端到端延时小于 AODV 的程度逐渐增大。特别地，当节点运动速度为 35 米/秒时，停留时 间分别为 10 秒和 30 秒的两种情况下，HPSO 的端到端延时均为 AODV 的一半，优势十分 明显。另外，HPSO 的延时随节点运动速度增加的变化趋势较为平缓，稳定性强。所以，基于 HPSO 的协议更适合于动态变化大的 Ad Hoc 网络环境。图 2 停留时间为 10 秒，运动速度不同时的延时 图 3 停留时间为 30 秒，运动速度不同时的延时（2）节点停留时间不同，运动速度相同（实验中分别设为 20 米/秒和 25 米/秒两种情况）实验结果如图 4 和图 5 所示。由两图可知，节点停留时间相同时，HPSO 的端到端延 时在大多数情况下比 AODV 小。因为 HPSO 只保留了少数几条较优路径的信息，数据包沿 它们发送产生的延时小；AODV 则存留了很多较差的路径信息（延时大），源节点会发送更多的数据包沿着它们传输，故会产生偏大的端到端延时。另外，在停留时间较小，即网络拓扑变化迅速的情况下，HPSO 的端到端延时大幅度小于 AODV 的延时。例如，对于节 点运动速度为 25 米/秒的情况，当停留时间分别是 5 秒，10 秒和 20 秒时，HPSO 的端到端 延时均比 AODV 的延时少一半，具有明显优势；在节点运动速度为 20 米/秒，停留时间在5 秒和 10 秒的条件下，HPSO 的端到端延时为 AODV 延时的 75%以下，具有一定优势。因此，HPSO 更适合于动态变化大的 Ad Hoc 网络环境。图 4 速度为 20 米/秒的不同停留时间延时图 5 速度为 25 米/秒的不同停留时间延时（3）节点运动速度为 10 米/秒、停留时间为 10 秒时的协议开销和路由发现时间协议开销是指网络中传输的控制包数目占所有通信包总量的比值。路由发现时间是指源 节点从产生路由请求包到接收路由确认包的时间。该场景具有节点低停留时间和低速运动的特点，网络拓扑变化程度居中，是一种普通的Ad Hoc 网络环境。如图 6 所示，在仿真时间内（大约 3 分钟），HPSO 的协议开销小于 AODV。对于 HPSO， 当最佳路径和备用路径确定后，只有它们均失效时，源节点才发送控制包寻求新路由；但在 AODV 中，源节点不断地发送控制包，将最新的网络信息告知邻居节点。故 HPSO 的协议 开销小于 AODV。如图 7 所示，总体上看，HPSO 的路由发现时间小于 AODV。对于 AODV， 当有路由请求时，源节点将以洪泛的方式在全网内开始路由发现过程，直至路径确认。对于 HPSO，由于采用备用路由机制，路由请求包将沿着备用路径向目的节点传输。如果备用路 径可用，请求包会迅速到达目的节点, 目的节点将逆向回传路由确认包。只有当两条备用路 径全部失效才启动新一轮的路由发现过程。故 HPSO 的路由发现时间会小于 AODV。HPSO 的备用路由机制使协议开销和路由发现时间得到改善，但其改善效果不如延时改 善的效果。图 6 相同速度和停留时间的协议开销对比图 7 相同速度和停留时间的路由发现时间对比7结论针对 Ad Hoc 网络的路由问题，本文提出了一种混合粒子群算法，并基于该算法设计了 一种按需路由协议。与 AODV 的仿真对比实验表明，HPSO 协议减小了端到端延时，更适 用于动态变化大的 Ad Hoc 网络。HPSO 在优化延时的同时，也使其它网络指标有所改善， 比如路由发现时间和协议开销。然而，作为一种新的路由协议，其算法的理论基础尚有待完 善，故需对它做更深入的研究。参考文献1 Chlamtac I, Conti M, Liu J. Mobile ad hoc networking: Imperatives and challenges. Ad Hoc Networks, 2003,1(1): 13-64.2 Mavropodi R, Douligeris C. Multipath routing protocols for mobile ad hoc networks: Security issues andPerformance evaluation. 2nd International IFIP Workshop on Autonomic Communication, 2006: 166-176.3 Okino M, Kato T, Ushijima J, et al. AODV routing protocol well suited to high density ad hoc network environment. IASTED International Conference on Communication Systems and Networks, 2004: 47-52.4 Kennedy J, Eberhart R. Particle Swarm Optimization. IEEE International Conference on Neural Networks,1995: 1942-1948.5 Eberhart R, Kennedy J. New optimizer using particle swarm theory. Sixth International Symposium on MicroMachine and Human Science, 1995: 3943.6 Coello C.A.C, Pulido G.T, Lechuga M.S. A Handling multiple objectives with particle swarm optimization.IEEE Transactions on Evolutionary Computation, 2004, 8(3): 256-279.7 Clerc M. The swarm and the queen: Towards a deterministic and adaptive particle Swarm optimization.Evolutionary Computation, 1999. CEC 99. Proceedings of the 1999 Congress on, 1999: 1951-1957.8 Wachowiak M, Smolikova R, Zheng Y, et al. An approach to multimodal biomedical image registration utilizing particle swarm optimization. IEEE Transactions on Evolutionary Computation, 2004, 8(3): 289-301.9 Zaharis. Z., Kampitaki D, Papastergiou A. Optimal design of a linear antenna array under the restriction ofuniform excitation distribution using a particle swarm optimization based method. WSEAS Transactions onCommunications, 2007, 6(1): 52-59.10 Zhang X.M, Qiu H.G. Improved particle swarm optimization based on k-center and its application in traveling salesman problem. Computer Integrated Manufacturing Systems, CIMS, 2007, 13(1): 99-104.11 Wu B, Zhao Y.W, Ma Y.L, et al. Particle Swarm Optimization method for vehicle routing problem. WorldCongress on Intelligent Control and Automation (WCICA). 2006: 3271-3275.12 Wang X.W, Wang J.W, Wu T.Y, et al. QoS unicast routing algorithm based on particle swarm optimization inNGI. Journal of Northeastern University, 2006, 27(1): 21-24.13 Liu J, Sun J, Xu W.B. QoS multicast routing based on particle swarm optimization. Intelligent DataEngineering and Automated Learning DEAL 2006- 7th International Conference, 2006: 936-943.14 Zhang X.H, Xu W.B. QoS based routing in wireless sensor network with particle swarm optimization. 9thPacific Rim International Workshop on Multi-Agents, 2006: 602-607.15 Venter G, Sobieszczanski S, Jaroslaw. Particle swarm optimization. AIAA Journal, 2003, 41(8): 1583-1589.Hybrid Particle Swarm Optimization Routing AlgorithmFor the Ad Hoc NetworksChen Wei1, Rao Nini1, Liao Ruihua2, Wang Weihua21 Department of Life Science and Technology, University of Electronic Science and Technology ofChina, Chengdu, Sichuan(610054)2 Communication Institute of Air Force Equipment Research Academy, Beijing (100085)AbstractCurrently in the Ad Hoc Network of high mobility, there exists the problem of the long delay. This paper proposed to apply the Particle Swarm Optimization (PSO) strategy to improve this problem.Firstly, we presented a hybrid particle swarm optimization(HPSO) algorithm combining genetic algorithm(GA), which is suitable to be used as routing protocols, and then established the on-demandrouting protocol based on the novel algorithm. Next, we realized this protocol using the networksimulation software OPNET and made simulation experiments. Compared with AODV that is a preferable Ad Hoc on-demand routing protocol, the results indicated that the routing protocol based on HPSO decreases the network delay and is applicable to the Ad Hoc Network of high mobility. Keywords: Ad Hoc Network; routing protocol; HPSO; AODV; OPNET作者简介：陈玮，男，1982 年生，硕士研究生，主要研究方向是基于群智能算法（如粒子 群，蚁群）的 Ad Hoc 路由协议。