基于混合粒子群算法的 Ad Hoc 路由协议研究.doc
《基于混合粒子群算法的 Ad Hoc 路由协议研究.doc》由会员分享,可在线阅读,更多相关《基于混合粒子群算法的 Ad Hoc 路由协议研究.doc(9页珍藏版)》请在三一文库上搜索。
1、基于混合粒子群算法的 Ad Hoc 路由协议研究陈玮 1,饶妮妮 1,廖瑞华 2,王炜华 21 电子科技大学生命科学与技术学院,成都(610054)2 空军装备研究院通信所, 北京(100085)E-mail: 摘要: 针对当前 Ad Hoc 路由协议在动态变化迅速的自组网中存在时延过大问题,本文引入粒子群优化算法,结合遗传算法对其改进,形成了适用于路由问题的混合粒子群算法。研 究基于混合粒子群算法的路由协议,在网络仿真软件 OPNET 上将其实现,并进行仿真实验。 与比较成熟的 Ad Hoc 按需路由协议 AODV 的仿真结果对比表明,新协议减小了网络的端到 端时延,更适合于动态变化大的 A
2、d Hoc 网络。关键词:Ad Hoc 网络;路由协议;混合粒子群算法;AODV;OPNET中图分类号:TP3931引言自组网(Ad Hoc,Wireless Network Without Infrastructure)是一种能够临时快速自动组 网的移动通信技术1。它不需要预设的网络基础设施,具有很强的抗毁性,故被广泛应用于 各种临时通信场合。路由协议是当前自组网技术的研究热点2,目前已有多种路由协议草案 被提出。按照路由建立方式分为主动路由协议和按需路由协议,其中后者适用于大规模,网 络拓扑变化迅速的环境。但是,由于它们大多采用洪泛机制,如 AODV3,使网络性能受到 制约。随着 Ad H
3、oc 技术的迅速发展,迫切需要能使网络性能更加优越的路由算法。粒子群算法(Particle Swarm Optimization, PSO)是一种基于群智能的迭代优化计算技术, 它最早由 Kennedy 和 Eberhart 于 1995 年提出 45,其基本思想源于对鸟群捕食行为的研究。系统初始化为一群随机粒子(随机解),然后通过迭代找到最优解。在每一次迭代中,粒子通 过跟踪全局极值和局部极值来更新自己,使粒子始终跟随最优粒子运动。PSO 流程简单, 参数简洁,被广泛应用于各种目标优化问题6,如决策调度7,图像配准8,天线阵列优化9等。对于路径优化问题,PSO 已被用来解决 TSP10,车辆
4、路由选择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 = (
5、 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 为
6、标量。算法的执行框架如下: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性权重,促进粒子向新空间搜索
7、; c1 , c2 为加速因子,分别表示粒子向局部极值和全 局极值的趋向程度。3) 计算各个粒子新位置的目标函数值。对每个粒子,若新值优于原来的个体极值 pbestk , 设置新值为 pbestk ,否则 pbestk 不变。再从各个粒子的个体极值里选出最优的一个作 为全局极值 gbestk 。4) 检查 gbestk 是否达到要求或迭代次数是否已达最大值。若条件满足,输出 gbestk 及最 优目标函数值;否则返回步骤 2)继续迭代。PSO 主要处理连续性优化问题,通过发挥粒子群体的功能使优化函数很快达到最优值。4适用于Ad Hoc网络环境的混合粒子群算法(HPSO)设计基本粒子群算法适用于
8、连续性优化问题。对于路由选择,由于路径是独立的,相互间无 连续关系,故路由是一个离散性优化问题。同时,路径由它所包含的节点组成,直接利用基 本粒子群算法不能对路径进行加减运算,故需要有一种相对于 PSO 速度及位移公式的等效 形式,才能用 PSO 解决路由问题。因此,本文借鉴遗传算法的思想, 设计了一种混合粒子 群算法,为 Ad Hoc 网络路由设计提供理论依据。4.1 粒子编码设计对于路由问题,路径即为粒子群算法中的粒子,不同的粒子代表不同路径。每个粒子是 一条路径途经节点序列号的集合,序列号的排列基于数据包从源节点出发依次经过中间节点 的顺序。故路径所包含的节点序列号按序排列即为粒子的编码
9、形式。例如:路径(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
10、 跳的部分以-1 填补。如:路径(1,4,6,8,15,3,17,-1,-1,-1)表示数据包从源节点 1依次经过中间节点 4,6,8,15,3,17 到达目的节点 17,共 7 跳。4.2 速度及位移公式的等效形式设计基本粒子群算法速度公式中的相减代表粒子向极值靠近,速度与常系数 c0相乘表示粒子向新空间搜索。这两种运动趋势与遗传算法中交叉和变异的效果颇为相似。在遗传算法中, 交叉是用最优基因片段替代普通基因的相应位置,使普通基因趋近于最优基因;变异让普通 基因具有较大的变化范围,可向更广阔的空间探索。由于以路径为编码的粒子很容易应用交 叉和变异算子,故采用这两个算子等效粒子群算法公式的相应
11、子项。(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 ) 的等效 因为该项表示粒子向局部最优值逼近,故可将其
12、等效为交叉算子。根据对应位交叉的思想,并与粒子和全局极值的交叉操作相区别,将 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=(
13、1 3 7 11 6 13 15 9 10 8) ;变异后, x=(1 13 3 7 11 6 15 9 10 8) 。这种等效表示 普通路径向新空间搜索,以求找到新的路径。(4)加法运算的等效 加法表示几种处理的总和,故粒子群算法各子项的等效处理综合起来即是加法的效果。在加法等效中,前一步处理的输出作为后一步的输入。 运用粒子编码并运用速度位移公式的等效形式后,便可用混合粒子群算法来解决路由问题。混合粒子群算法执行流程与基本粒子群算法的相同,只是粒子更新时采用速度位移公式 的等效形式。另外,为了保护最优路径信息,不对当次迭代运算的最优粒子(最优路径)做 更新处理。若经过计算,非最优粒子的效果
14、好于最优粒子,则效果好的粒子作为最优粒子, 曾经的最优粒子变为普通粒子,可在下一轮迭代运算时进行更新。5基于混合粒子群算法的路由协议的设计思想对于动态变化较快的 Ad Hoc 网络,采用按需路由策略更适合于相应的网络环境。按需 路由是指仅当源节点有发送数据包需求时,才进行相应的路由发现过程,按需建立路由表。 按需路由协议一般包括路由发现和路由修复两部分。本文基于混合粒子群优化算法的按需路 由协议即是从这两方面进行设计的。5.1 路由发现传输数据前,各节点首先初始化自己的属性,预设最大跳数值(本文设置为 10)和跳 数旗帜值(大于 10,避免无环路由)。路由发现步骤如下:(1)源节点有传输数据需
15、求时,向外广播发送路由请求包。(2)中间节点接收到请求包后,从包中提取跳数属性值,它表示该请求包已经历节点 的个数。将中间节点的跳数旗帜值与包中跳数属性值比较后,做如下处理: a.若包中跳数小于等于跳数旗帜值,则令跳数旗帜值等于包中的跳数值,同时将包中的跳数值加 1,并把中间节点的地址加入包中的路由表,将该包继续以广播方式传播。b.若跳数大于中间节点的跳数旗帜值,节点的跳数旗帜值不变,同时注销该请求包, 使其不向其他节点传播。此举可避免路由环路发生。(3)目的节点接收到请求包后,检查已接收请求包数目是否达到预定值。a. 若没有,从包中提取出路由表及请求包传输延时信息,存入目的节点缓存。 注销该
16、包,等待下一个请求包的到达。b. 若达到一定数目,则将所有接收请求包的路由表从缓存中提取出,作为“粒子”, 同时提取出它们的传输延时信息,作为相应“粒子”的适应值。然后根据混合粒 子群算法 (HPSO) 迭代,计算出延时较小的三条路径,其中最小的是最优传输 路径,其余两条为备用路径。(4)目的节点沿三条路径逆向发送确认包回源节点,途经的中间节点将记录下路由表 中相对自己的前一跳和下一跳。(5)源节点接收到确认包后,将沿着最优路径传输数据包到目的节点。 路由发现的流程框图如图 1 所示。图 1 基于 HPSO 的路由发现流程5.2 路由修复(1)链路中断的检测网络内每个节点不断发送 hello
17、包给其邻节点,并接收它们的回复信息。若在规定时间 内没有接收到回复信息,则说明这两个节点之间的链路断开。(2)断链的处理 当节点之间的链路断开时,断链处的上游节点将沿路径逆向传输修复包回源节点,请求采用备用路径进行传输。若三条路径均已失效,则源节点启动新一轮路由发现过程。6仿真实验与结果分析仿真工具选用网络仿真软件 OPNET,在 MAC 层选用 802.11b DCF 协议,网络层是自 己设计的进程模型,用来实现混合粒子群路由协议(HPSO)。仿真场景根据随机位点模型(Random Waypoint Model,RWM),由一些随机放置的可移动节点组成。在相同网络环境 下,分别对 HPSO
18、和 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。这是因为
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 基于混合粒子群算法的 Ad Hoc 路由协议研究 基于 混合 粒子 算法 路由 协议 研究
链接地址:https://www.31doc.com/p-3624211.html