基于混合粒子算法的Ad Hoc 路由协议研究
陈玮1，饶妮妮1，廖瑞华2，王炜华2
1 电子科技大学生命科学与技术学院，成都（610054）
2 空军装备研究院通信所， 北京（100085）
E-mail: chenweifly@sohu
摘  要: 针对当前Ad Hoc 路由协议在动态变化迅速的自组网中存在时延过大问题，本文引入粒子优化算法，结合遗传算法对其改进，形成了适用于路由问题的混合粒子算法。研究基于混合粒子算法的路由协议，在网络仿真软件OPNET 上将其实现，并进行仿真实验。与比较成熟的Ad Hoc 按需路由协议AODV 的仿真结果对比表明，新协议减小了网络的端到端时延，更适合于动态变化大的Ad Hoc 网络。
关键词：Ad Hoc 网络；路由协议；混合粒子算法；AODV ；OPNET
中图分类号：TP393
1．引言
自组网（Ad Hoc ，Wireless Network Without Infrastructure ）是一种能够临时快速自动组网的移动通信技术[1]。它不需要预设的网络基础设施，具有很强的抗毁性，故被广泛应用于各种临时通信场合。路由协议是当前自组网技术的研究热点[2]，目前已有多种路由协议草案被提出。按照路由建立方式分为主动路由协议和按需路由协议，其中后者适用于大规模，网络拓扑变化迅速的环境。但是，由于它们大多采用洪泛机制，如AODV [3]，使网络性能受到制约。随着Ad Hoc 技术的迅速发展，迫切需要能使网络性能更加优越的路由算法。
粒子算法(Particle Swarm Optimization, PSO)是一种基于智能的迭代优化计算技术，
它最早由Kennedy 和Eberhart 于1995年提出 [4][5]，
其基本思想源于对鸟捕食行为的研究。系统初始化为一随机粒子(随机解)，然后通过迭代到最优解。在每一次迭代中，粒子通过跟踪全局极值和局部极值来更新自己，使粒子始终跟随最优粒子运动。PSO 流程简单，参数简洁，被广泛应用于各种目标优化问题[6]，如决策调度[7]，图像配准[8]，天线阵列优化[9]等。对于路径优化问题，PSO 已被用来解决TSP [10]，车辆路由选择[11]和Ad Hoc 网络QoS 路由[12][13][14]。
hue trunc函数
本文结合遗传算法，对PSO 进行改进，提出适用于路由问题的混合粒子算法(HPSO ，Hybrid Particle Swarm Optimization)；然后按照按需路由协议机制，设计了一种基于HPSO 的Ad Hoc 路由协议框架。在OPNET 网络仿真软件上将其实现后进行系统级仿真实验，同时在相同网络环境下与AODV 协议进行比较。
2．Ad 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 s P y x e y x e D 达到最小。
3．基本粒子算法（PSO ）
基本粒子算法（PSO ）是基于体和适应度概念，通过“集智能”[15] 求解目标函数f (x )
的最优值问题。该算法能迅速到某个或某些x ，让f (x )达到或接近最优值。其中x 是N 维向量，当N 为1时，x 为标量。算法的执行框架如下：
1） 根据优化目标函数f (x )，在自变量x 的取值范围内随机产生n 个x 值作为初始粒子，同
时随机产生n 个初始速度对应于各粒子。
2） 根据当前的位置和速度，依照下面公式更新每个粒子的速度和位置。
1012()()
(1)k k k k k k v c v c pbest x c gbest x +=+−+− 11(2)k k k x x v ++=+ 其中，k 代表迭代次数，k v 是粒子的速度向量，k x 是当前粒子的位置，k pbest 表
示粒子本身所到的最优解位置，k gbest 为整个体目前到的最优解位置。0c 是惯性权重，促进粒子向新空间搜索；1c ，2c 为加速因子，分别表示粒子向局部极值和全局极值的趋向程度。
3） 计算各个粒子新位置的目标函数值。对每个粒子，若新值优于原来的个体极值k pbest ，
设置新值为k pbest ，否则k pbest 不变。再从各个粒子的个体极值里选出最优的一个作为全局极值k gbest 。
4） 检查k gbest 是否达到要求或迭代次数是否已达最大值。若条件满足，输出k gbest 及最
优目标函数值；否则返回步骤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 速度及位移公式的等效形式设计
基本粒子算法速度公式中的相减代表粒子向极值靠近，速度与常系数0c 相乘表示粒子向新空间搜索。这两种运动趋势与遗传算法中交叉和变异的效果颇为相似。在遗传算法中，交叉是用最优基因片段替代
普通基因的相应位置，使普通基因趋近于最优基因；变异让普通基因具有较大的变化范围，可向更广阔的空间探索。由于以路径为编码的粒子很容易应用交叉和变异算子，故采用这两个算子等效粒子算法公式的相应子项。
（1）)(2k k x gbest c −的等效
因为该项表示粒子向全局最优值逼近，故可将其等效为交叉算子。根据遗传算法中对应位交叉的思想，结合路由问题中的有限跳数及首尾项不能改变的原则（它们分别为源节点和目的节点），用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）)(1k k x pbest c −的等效
因为该项表示粒子向局部最优值逼近，故可将其等效为交叉算子。根据对应位交叉的思
想，并与粒子和全局极值的交叉操作相区别，将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）k v c 0的等效
因为该项表示粒子向新空间拓展，故可将其等效为变异算子。利用遗传算法中的调位变异策略，将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所示。
5.2 路由修复
（1）链路中断的检测
网络内每个节点不断发送hello包给其邻节点，并接收它们的回复信息。若在规定时间内没有接收到回复信息，则说明这两个节点之间的链路断开。
（2）断链的处理
当节点之间的链路断开时，断链处的上游节点将沿路径逆向传输修复包回源节点，请求采用备用路径进行传输。若三条路径均已失效，则源节点启动新一轮路由发现过程。6．仿真实验与结果分析
仿真工具选用网络仿真软件OPNET，在MAC层选用802.11b DCF协议，网络层是自己设计的进程模型，用来实现混合粒子路由协议(HPSO)。仿真场景根据随机位点模型（Random Waypoint Model，RWM)，由一些随机放置的可移动节点组成。在相同网络环境
下，分别对HPSO和AODV进行仿真。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。