自适应路由优化（精选7篇）
自适应路由优化 篇1
0 引言
大规模并行处理机(MPP)系统性能的发挥极大程度上依赖于网络的通信性能。互联网络路由器是网络的关键部件,其性能优劣直接影响系统性能,因而对其如何高效、简洁地设计和实现对整个系统起着关键作用。路由器根据其所采用的路由算法可分为确定性和自适应两种,前者不受网络状态影响,实现简单,已在很多商用MPP中采用,但阻塞严重、网络利用率低;后者灵活性好、网络的通道利用率高、网络容错能力强,正逐步为新一代的MPP系统所采用,但其工程实现难度较大,目前仅在少数商用MPP系统中得以实现。路由器设计的中心问题是路由算法、切换技术和流控策略。本文主要讨论Option Red系统上的路由问题,介绍一种自适应的路由算法。
1 问题背景
Option Red是由Intel可扩展系统公司和Sandia国家实验室联合开发的MPP系统。它是一个分布式存储器MPP,系统共使用三种类型结点:系统结点、服务结点、计算结点和I/O结点。这些结点间由一个内部互连设备(Interconnection Facility,ICF)相连,ICF使用了两平面网格拓扑。从任意结点发出的消息借助路由通过任一平面送至另一个结点。
如图1所示的两平面(two-mesh)网格拓扑结构:每个MRC有六个双口端口,分别和上、下、左、右的MRC连接,还有两个端口,一个用于平面间的MRC连接,另一个用于和节点板连接。
2 路由算法
2.1 此路由算法基于以下假设:
(1)每个MRC都知道自己的6个端口的状态,即处于忙(0)还是空闲状态(1)。
(2)每个MRC之间并不知道相互间的端口状态。
(3)每个MRC的坐标点按如下规律设定:对于每一层平面,按行优先,从左到右的排列,每个MRC都有唯一的坐标,上一层为M[i][j],下一层为MM[i][j],且MM[i][j]的正上方是M[i][j]。
2.2 基本思想
假设源点是M[0][0],目的地是Mdestine。算法的基本思想是:从M[0][0]出发,向四周搜索,并且记下所有经过的MRC的坐标点M[0][1],M[1][0],MM[0][0];然后依次从M[0][1],M[1][0],MM[0][0]出发,记下第二步所有经过的MRC的坐标点,依次进行下去,直至到达目的地Mdestine。然后从Mdestine沿搜索路径回溯直至M[0][0]。这样就找到了从源到目的地的一条最短路径。此时,建立了源到目的地的一个虚连接,紧接着数据开始发送,直至发送完毕将一直占有该通道。
2.3 具体实现
该算法具体实现还要解决以下问题:
(1)如何从某一点出发搜索四周的邻点。先不考虑边界的MRC,每个均有六个端口,其中一个端口通向结点板。不妨设从MRC[i][j]出发搜索的六个方位顺序是从正北起沿顺时针方向进行,将这6个方位上的x和y坐标的增量预先依次放在一个结构数组Way[5]里。该数组的每个分量有两个域x和y。于是,只要令方向值从0增至5,就可以通过下面的计算得到从MRC[i][j]出发搜索到的每一个相邻点。
其中,如果是到结点板,则x,y不变化。如果是到另一层,则x,y同时增加1,此时要把结点名字改过来,即为MM,同时再把x,y减1。
(2)存储搜索路径。由于先到达的点先被搜索出来,故选用一个“先进先出”的队列来保存已到达的坐标点。用一个结构数组Sq[n]作为该队列的存储空间,每一个结构有三个域x,y和pre,其中x和y分别记下搜索过程中达到的每个点的行、列坐标,pre记下到达该点的出发点在Sq中的名称。
(3)防止重复到达某坐标点。一旦到达某坐标点后,就将达到该点的端口设置为-1。
3 进一步的思考
上述的算法思想主要是通过在源点和目的地点之间建立一条虚通道,然后传输数据。但是,由于需要较多的虚通道,可能导致控制逻辑更为复杂,增大了路由器的延迟和周期时间,故虚通道数并非越多越好。在今后,还需要进一步的改进。
参考文献
[1]陈国良.并行计算—结构、算法、编程[M].北京:高等教育出版社,1999.
[2]Ayse Yasemin Seydim.Wormhole Routing in ParallelComputers[M].School of Engineering and Applied Sciences,Southern Methodist University,1998.
[3]黄铠,徐志伟.可扩展并行计算技术、结构与编程[M].北京:机械工业出版社,1999.
自适应路由优化 篇2
将粒子群优化的BP神经网络作为模型,参考自适应控制系统的控制器,把参考模型输出与系统实际输出的均方误差作为PSO-BP神经网络的适应函数,通过PSO算法强大的搜索性能使自适应控制系统的`均方误差最小化.仿真实例结果表明,基于粒子群优化算法的BP神经网络自适应控制系统收敛快、精度高,有较好的网络的泛化和适应能力,能够很好地控制系统的输出跟随参考模型的输出.
作 者：陈聆 闫海波 毛万标 CHEN Ling YAN Hai-bo MAO Wan-biao 作者单位：陈聆,CHEN Ling(成都理工大学信息管理学院,数学地质四川省重点实验室,成都,610059)
闫海波,YAN Hai-bo(新疆财经学院,乌鲁木齐,830012)
毛万标,MAO Wan-biao(西昌卫星发射中心技术部,四川,西昌,615000)
自适应路由优化 篇3
在国内外研究人员的积极努力下, 针对无线传感器网络节点能量有限的问题, 提出了许多能量高效的路由协议, 其中地理路由协议由于简单和良好的扩展性备受关注[1]。地理路由协议, 以地理信息为基础来有效地进行路由选择, 在路由建立的过程中, 某一节点不需要知道整个网络中的所有节点的地理位置信息, 只知道其邻居节点以及目标节点的地理位置信息的;通过计算其诸多邻居节点和目标节点的距离来选择下一跳节点;这样就将路由选择的范围只限定在邻居节点范围, 从而大大降低了网络流量, 节约电池电量[2]。其中, 典型的地理位置路由协议为无状态的贪婪周边路由协议GPSR[3]。本文将结合无线网络能耗模型和邻居节点数量, 基于GPSR路由协议提出了一种自适应的三维地理路由机制。
一、能耗模型
为了研究无线传感器网络, Heinzelman提出First Order射频模型[6]。发射机和接收机工作时的电路损耗为Eelec=50n J/b it, 发射机发射放大器损耗为着amp=100p J/b it/m2。对于发射机来说, 发送k bit信息, 传输距离为d, 消耗能量为:Es (k, d) =Eelec (k) +Eamp (k, d) , 则有:Es (k, d) =Eelec*k+着amp*k*d2;对于接收机, 接收kbit信息, 消耗能量为:ER (k, d) =Eelec (k) =Eelec*k。对于传感器节点来说, 发送和接收的能耗都和数据包的大小有关, 降低数据包发送的频率, 减小数据包的长度可以有效的降低单个节点的能耗。
二、基于邻居数量的自适应三维地理路由策略
2.1能耗分析与平衡机制
因为无线传感器网络是以数据为中心的, 传感信息的采集有着规律性, 这里可以假设节点数据采集的时间间隔为Ts, 节点更新状态信息的时间间隔为TM。
另外, 由于无线节点存储空间有限, 因此进一步考虑能量平衡机制是必要的[7]。设无线节点仅能保存窗口时间Twin时间段内的数据量记录, 用指数加权移动平均法来衡量一个节点的数据量:P (i) = (1-琢) P (i) +琢Pwin (i) , 式中Pwin (i) 表示Twin时间内数据量多少, 琢为权重因子, 反映了节点数据量的实时变化程度。P (i) 表示节点i在网络中对于数据包传输的重要性, P (i) 越大, 就需要为节点i预留更多的能量, 以防止节点失效造成数据包传输的能耗增加。用下面的公式来表述节点i的能耗平衡情况:W (i) =E (i) /P (i) , 选择W (i) 最大的节点u作为下一跳转发节点。
2.2基于邻居数量的自适应地理路由策略
(a) 邻居节点数目与自适应转发选择机制
当网络中的一些节点以为电量耗完或其他原因失效, 节点密度变得稀疏, 就开始采用基于区域的转发策略。每个节点都维护着一个邻居节点集合N (i) , 每当收到邻居节点的Hello信息, 节点都会自动的更新这张表, 与此同时更新邻居度:
(b) 基于邻居数量的自适应地理路由算法
当无线传感网络启动, 各节点的位置信息初始化并且稳定后。开始进行数据包的接发工作。下面给出基于邻居数量的自适应地理路由策略, 源节点S发送信息给目标节点D, 如图1所示, 并以此为顶点建立一个次极小椭球, 并绕SD旋转成为次极小椭球。算法的具体执行如下:
Step1:初始化, i=S, N (i) 。
Step2:i查看自己的邻居节点, 如果D是自己的邻居节点, 直接发送给D。
三、结论
本文针对传感器节点能量的有限性, 综合考虑了能量与通信量平衡的策略, 并结合邻居节点数量和次极小椭球机制, 提出了一种基于邻居数量的自适应三维地理路由选择方法。该方法对于研究更加高效的无线传感器网络节能机制和路由策略, 延长网络生命周期, 具有重要的现实意义。
参考文献
[1]杨冕, 秦前清.基于无线传感器网络的路由协议[J].计算机工程与应用, 2004, 32 (3) :130-131.
[2]张衡阳, 李莹莹, 刘云辉.基于地理位置的无线传感器网络路由协议研究进展倡[J].计算机应用研究, 2008, 25 (1) .
[3]Karp B, Kung H T.GPSR:Greedy Perimeter Stateless Routing for wireless networks[C].In:MOBICOM 2000, 2000.243-254.
[6]Heinzelman W R, Chandrakasan A, Balakrishnan H.Energy-efficient communication protocol for wireless microsensor networks[C].In:33rd Annual Hawaii International Conference on System Sciences, 2000.10-12.
[7]陈衡, 钱德沛, 伍卫国, 等.传感器网络基于邻居信息量化的能量平衡路由[J].西安交通大学学报, 2012, 46 (4) :1-6.
自适应路由优化 篇4
随着高速网络技术的发展, 与多媒体相关的实时业务应用大量兴起[1], 而有效的组播路由[2]是实现多媒体通信的关键技术。传统的组播通信大多采用“尽力而为”, 没有很好地考虑服务质量QoS (Quality of Service) [3]。随着网络的发展, 多媒体通信对网络的服务质量QoS提出了越来越高的要求, QoS组播路由问题应运而生。QoS组播路由问题是指在分布的网络中寻找最优路径[4], 要求从源节点出发, 历经所有的目的节点, 找到一条满足网络路由中延时、带宽、丢包率等约束条件且花费最小的网络路径。Wang Z 等学者已经证明了包含两个及以上约束条件的QoS网络路由是一个NP完全问题[5]。
蚁群算法 (Ant Colony Algorithm, ACA) 是上世纪90年代意大利学者 M.Dorigo和V.Maniezzo等人通过模拟自然界蚂蚁寻径的行为提出的一种全新启发式算法, 它被广泛用于解决各种NP完全问题[6]。现利用一种基于自适应蚁群优化算法, 提出考虑网络链路利用率的QoS多约束条件下组播路由解决方法。
1 基本蚁群算法
蚁群算法是一种新近发展起来的、模拟蚂蚁群体觅食行为的仿生优化算法。蚂蚁在寻找食物的运动过程中, 能在其经过的路径上分泌一定数量具有气味的称为信息素的物质进行信息传递, 并指导自己的运动方向。某一路径上走过的蚂蚁越多, 此路径上蚂蚁留下的信息素轨迹也越多, 则后来蚂蚁选择该路径的概率也越大, 从而更增加了该路径被选择的可能性。同时, 路径上的信息素也会随着时间的流逝而不断地挥发, 这种机制所得蚂蚁不完全受过去经验的约束, 有利于蚂蚁向新的路径搜索。随着时间的推移, 蚂蚁就会找到由蚁巢到食物源的最优路径。该算法采用了正反馈并行自催化机制, 具有较强的鲁棒性、优良的分布式计算机制、易于与其他方面结合等优点。
蚁群算法利用随机策略, 使得进化速度较慢, 收敛速度不理想;利用正反馈强化性能较好的解, 但导致当前不被选用的路径, 往后被选用的概率越来越小, 使算法在某些局部最优解附近徘徊, 出现停滞现象, 而且挥发系数ρ的存在会使那些从未搜索到的路径上的信息素量逐渐减少到0, 从而降低算法的全局搜索能力。若ρ过大, 会使以前搜索过的路径被再次选择的可能性过大, 影响算法的全局搜索能力, 易于陷入局部最优解;若ρ过小, 虽然可以提高算法的全局搜索能力, 但会使算法的收敛速度降低。1996年Gambardella和Dorigo提出了一种修正的蚁群算法 (ACS) [7], 该算法对信息素的更新策略作了相应的改进, 即使用:
(1) 局部信息更新, 蚂蚁从城市i转移到城市j后, 路径上的信息素按式 (1) 进行更新:
undefined
式中:ξ∈ (0, 1) , τo为常数。
采用局部信息更新策略减小了已选择过的路径再次被选择的概率, 提高了算法的全局搜索能力。
(2) 全局信息更新, 针对全局最优解所属边按式 (2) 进行信息素更新:
τij (t+n) = (1-ρ) τij (t) +ρΔτundefined (t) , ρ∈ (0, 1) (2)
式中:Δτundefined (t) =1/Lgb;Lgb为当前全局最优解的路径长度。采用全局信息更新策略, 增强了全局最优解路径上的信息素, 加强了算法的正反馈作用, 从而加快算法的收敛速度。
2 QoS网络路由模型
2.1 QoS组播路由问题的基本概念和网络模型定义
就组播路由而言, 网络通常表示成一个带权图G= (V, E) , 其中V代表节点集合;E代表网络中双向链路集合, 关联每条链路的参数就是该链路的QoS度量。在此, E表示网络中双向链路的集合[8];S为源节点, S∈V;M∈{V-{S}}为目的节点集, S, M组成组播树T (s, M) 。对于任一链路e∈E, 可定义某些属性:延时函数:delay (e) :E∈R+;费用函数cost (e) :E∈R+;带宽函数bandwidth (e) :E∈R+。对于任一网络节点n∈V, 定义某些属性:延迟函数delay (n) :V∈R+;费用函数cost (n) :V∈R+, 由此存在如下关系:
undefined
式中:pT (s, t) 为组播树T (s, M) 上源点s到终点t的路径。
QoS组播路由问题是要寻找一颗组播树T (s, M) 满足:
延时约束:
undefined
带宽约束:
undefined
式中:B表示带宽约束;Dt表示延时约束。
费用函数 (目标函数) 可描述为在所有满足条件的组播树中, cost (T (s, M) ) 最小。
2.2 网络负载和链路利用率
为考虑链路利用率的情况, 将链路代价定义为[9]:
undefined
E中的每条边对应网络中的一条链路ei, j, 其中i表示上游路由器;j表示下游路由器。ei, j具有三个属性:Maximum Bandwidth (MB) , Reserved Bandwidth (RB) , Unreserved Bandwidth (UB) 。因此有对任意e∈E, ∃MB (i, j) , RB (i, j) 和UB (i, j) , 并且MB (i, j) =RB (i, j) +UB (i, j) 。在式 (8) 的基础上, 定义式 (9) , 用来计算图G中每条链路的代价。
undefined
由式 (9) 可知, 剩余带宽越大, 链路代价越小;反之, 链路代价越大。
3 自适应蚁群算法的QoS组播问题实现
3.1 适应度函数
适应度函数是蚁群进行路径选择的依据, 也就是蚂蚁从初始路径集Ωi中选择第j条路径的概率:
undefined
式中: phepj (s, Di) 是路径pj (s, Di) 上的分泌物强度, 它表明某条路径上的分泌物强度越大, 该路径被选中的概率也就越大。初始状态时各条路径上的分泌物强度相同。
3.2 蚂蚁的信息素调整
蚂蚁寻找路径时, 按以下规则进行信息素调整:
(1) 对蚂蚁所经过的路径进行分泌物强度调整。其中a是常量参数;cost (e) 为该路径的代价;phepi (s, Di) 为源节点S到目的节点Di的路径上的分泌物强度。调整后, 有:
undefined
上述公式与文献[10]不同, 信息素的调整不是固定值, 而是根据所选择路径的代价来调整的, 并且路径代价受带宽影响, 是根据链路利用率来确定的。增加信息调整的自适应性, 同时也加快了收敛速度。
(2) 当蚂蚁都走完一条路径时, 对所有路径进行分泌物挥发调整。其中ρ是挥发度;Δ为各条路径上的初始信息强度。
undefined
(3) 当蚂蚁都找到所有目的节点, 组成一颗组播树时, 再按式 (13) 进行信息素调整, 即:
undefined
式中:B为常量参数;cost (T) 为该组播树的代价;pi (s, Di) 是被选路径。
3.3 算法步骤
Step 1:生成初始路径集。找出从源节点S到每个目的节点Di∈D (i=1, 2, …, m) 满足延时约束的有效路径, 并组成初始路径集Ωi。
Step 2:初始化α, β, B, ANTn和初始集中各条路径上的信息强度Δ。
Step 3:从源节点发出ANTn只蚂蚁, 按式 (10) 计算路径集Ωi中每条路径的适应度, 每只蚂蚁再按赌轮旋转规则从中选择一条路径, 再按式 (11) 进行分泌物强度调整。
Step 4:当每只蚂蚁都完成一条路径选择后, 按式 (12) 进行分泌物挥发性调整。
Step 5:重复执行Step 3和Step 4, 直到蚂蚁找到所有目的节点的路径, 每只蚂蚁寻找到的路径各组成一颗组播树。计算各组播树的代价 (相同链路的代价只计算一次) , 判断是否大多数蚂蚁收敛于同一组播树, 如果是, 则该组播树为最优路径, 退出程序;否则, 用代价最小的组播树替代代价最大的组播树, 转执行Step 6。
Step 6:蚂蚁按原路返回, 并按式 (13) 调整返回路径上的分泌物强度, 再转Step 3执行。
4 实验仿真和算法分析
本文采用改进的Waxman网络拓扑仿真模型[11], 利用Matlab 7.0进行仿真, 其特点是每对节点之间按概率p (u, v) =βexp (-d (u, v) /2an) 相连, 其中d (u, v) 为u, v两节点之间的距离, 并且按照Salama和Reeves在Waxman基础上的网络生成算法使平均节点度达到指定值。参数α, β分别控制网络中长边和短边的比例以及边的密度, n为网络节点个数。参数的选取如表1所示。表2列出了30个节点的网络仿真试验中, 两种不同算法在不同延时约束条件下的组播树代价。每次试验分别进行20次, 其中代价值分别是20次试验得到的平均值。从表2容易看出, 算法IAAC比算法AAC在相同延时条件下生成组播树的代价要小。图1描述了两种算法在30个网络节点的网络仿真中, 组播树的代价随迭代次数的变化情况。从图中可以看出, IAAC算法在收敛速度上要优于AAC算法, 并且在最优组播树的代价上也要优于AAC算法。图2显示了两种算法在随着网络节点数变化时, 组播树代价的变化情况。随着网络节点数的增加, IAAC算法所得最优组播树的代价低于AAC算法所得最优组播树的代价, 并且最优组播树的代价增加比AAC算法得到最优组播树代价的增加速度要慢。通过仿真试验, 本文改进的自适应蚁群算法能以更快的收敛速度得到最优组播树, 并且最优组播树的代价相对原有自适应蚁群算法要更优。
5 结 语
本文提出了一种应用自适应蚁群算法并结合实际网络的链路利用率的多约束QoS组播路由算法。将链路利用和网络负载考虑到组播路由中, 使得网络路由问题的研究更符合实际网络的需求。在运用自适应蚁群时, 结合信息素更新的特点, 将链路代价考虑到其中, 使得信息调整的自适应性加强, 同时收敛速度得到改善。
摘要：结合多约束QoS组播路由的特点, 应用一种自适应蚁群优化算法解决组播路由问题。考虑到实际通信中链路利用率对网络的影响, 将网络中链路的带宽转化为链路的代价问题, 并在蚁群算法中根据蚂蚁所选路径的代价进行信息素更新, 增加了信息素调整的自适应性, 同时加快了算法的收敛速度, 使得组播路由算法在考虑网络QoS约束的基础上进一步贴合实际网络的需求。
关键词：QoS,蚁群算法,自适应,链路利用率
参考文献
[1]Chockler G V, et al.Group Communication Specifications:AComprehensive Study[J].ACM Computing Surveys, 2001, 33 (4) :1-43.
[2]Wang B, Hou C J.A Survey on Multicast Routing and ItsQoS Extensions:Problems, Algorithms and Protocols[J].IEEE Network Magazine, 2000, 14 (1) :22-36.
[3]Xiao X P, Ni L M.Internet QoS:the Big Picture[J].IEEENetwork Magazine, 1999, 13 (2) :1-13.
[4]邹德莉, 郝应光.基于非精确状态信息的QoS组播路由算法[J].微电子学与计算机, 2006, 23 (9) :66-72.
[5]Wang Zheng, Crowcroft J.Quality of Service Routing for-Supporting Multimedia Applications[J].IEEE Journal onSelected Areas in Communications, 1996, 14 (7) :1 228-1 234.
[6]Dorigo M, Maniezzo V, Colorni A.Ant System:Optimizationby a Colony Cooperating Agents[J].IEEE Trans.on Sys-tems, Man, and Cybernetics-bart B:Cybernetics, 1996, 26 (1) :29-41.
[7]李昌兵.基于计算智能的多播QoS路由技术研究[D].重庆:重庆大学, 2007.
[8]王应征, 石冰心.基于遗传算法的时延受限代价最小组播路由选择方法[J].通信学报, 2002, 23 (3) :112-117.
[9]Cisco.OSPF Design Guide[EB/OL].http://www.cisco.com/warp/public/104/1.html, 2004-02.
[10]李生红, 刘泽民.基于蚁群算法的组播路由调度方法[J].计算机工程, 2001, 27 (4) :63-65.
[11]Waxman B M.Routing of Multiple Connections[J].IEEEJournal on Selected Area in Communications, 1986, 6 (9) :1622-1 671.
自适应路由优化 篇5
WSN是具有数 据融合、 通信和计 算等特定 功能的节点 以自组织 的形式关 联在一起 的网络体 系 ,能够实时 监测、感知 和采集周 围环境的 相关信息 , 并把信息 经过处理后 通过路由 协议传输 给终端计 算机[1]。WSN在环境监测 、智能交通 等领域得 到了广泛 的应用[2,3]。
由于三维 空间的路 由协议更 符合实际 的应用环 境 ,近年来其 成为WSN研究的热 点。Li等人在文 献[4]中提出3D-SAEAR算法 ,通过迭代 分簇方法 一定程度 上平衡了网 络的能耗 , 但是簇首 死亡时才 发动选举 , 造成节点过 早死亡。Ke等人在文 献[5] 中提出了 三维胞元 空间模型和3D-CSR算法 , 建立了完 整的分层 路由体系 , 提出了自适 应选举机 制 ,但是采用 贪婪路由 方式选择 邻居胞父节 点中到目 的节点的 距离最短 的作为下 一跳节点 (此节点为邻 居最优胞 父 ), 没有建立 有效的能 量模型来 优化传输路 径 ,导致平均 能耗较多 。
3D-SAEAR算法和3D-CSR算法均存在簇首负担较大的问题, 本文在三维胞元空间模型的基础上, 提出了3DSMEER算法。该算法引入协同节点协助最优胞父转发消息包,减少了总的路径损耗,降低了网络的能耗;建立协同节点选举机制,保护了能量较低的节点,提高了能量利用率。
1 算 法模型
1 . 1 能 耗 模 型
当传输g bit字节时 ,总能耗Es表达式如 下所示[6]:
其中l表示节点 之间的距 离 ,Eelec表示发送1 bit字节时 ,启动电路 能耗 ,εamp为放大电 路能耗 ,γ为路径 损耗指数。 本文假设 在自由空 间模型下 ,取γ=2。
1 . 2 协 同 节 点 选 择 模 型
Bhardwaj等 [7]提出当采 用最佳传 输距离Lideal转发消息包 时 ,通过最佳 跳数Hideal, 能耗达到 最低 , 由Lideal确定的转发 位置称为 理想转发 节点位置 ,Lideal和Hideal表达式分别为 :
WSN中一般达 不到转发 节点相互 距离为Lideal的要求 ,因此提出协 同节点代 替理想转 发节点多 跳传输的 模型。
基于协同 节点的多 跳模式的 基本思想 为 : 首先在贪婪 策略下确 定邻居最 优胞父 ,根据Lideal确定理想 转发节点位 置Mi; 然后以Mi为球心 , 作半径为r的球体 , 球体内的节 点称为候 选协同节 点 ;最后根据 协同节点 的选择原则 进行选举 :
( 1 ) 低剩余能 量保护原 则 : 低剩余能 量保护系数 为β (0<β<1), 节点的初 始能量为Eini, 如果节点 剩余能量Eres< βEini, 则该节点 不能作为候 选协同节 点。
( 2 ) 重复选择 避免机制 : 球体半径r值增大时相 邻球体出 现相离、相 切与相交 的三种关系 ,若某节点 被选中为 协同节点 后不能作 为另外球 体的候选协 同节点。
( 3 ) 胞父优先 原则 : 球体中有 胞父节点 , 则优先选 择胞父作为 协同节点 。
( 4 ) 能耗节省 原则 : 同类型的 节点比较 时 , 优先考虑与 理想节点 位置距离 最短的节 点为协同 节点。
LEN ( A , B ) 表示节点A与节点B之间的距 离。图1为通过协同节点转发的示意图,其中LEN(C,M1)=LEN(M1,M2) = Lideal, d表示胞元 的边长 , 当前胞元 ( XI, YI, ZI)C中胞父节点C确定的邻 居最优胞 父P位于胞元 (XJ, YJ, ZJ)C内。球M1内有胞父 节点 , 由原则 (3) 选择胞父 为协同节点 ; 球M2内无胞父 节点 , 由原则 (4) 选择距离 理想转发节 点最近的 胞子为协 同节点。
2 3D - SMEER算法
该算法根 据自适应 多跳机制 决定传输 方式 , 利用协同节 点选择机 制选出转 发节点协 助当前胞 父传输消息 包。
2 . 1自适应多 跳机制
由公式(3)知 ,当前胞父 和邻居最 优胞父的 距离L与最佳传输 距离Lideal的关系决 定了最佳 跳数Hideal。图2 ( a )中当L<Lideal时 , 采用单跳 的方式到 达邻居最 优胞父 ;图2 ( c ) 中当L > 2Lideal时 , 由公式 (3) 得Hideal≥2, 即采用多 跳方式把消 息包传输 给邻居最 优胞父 ; 图2 (b) 中当Lideal<L < 2Lideal时 ,比较二者 传输消息 包的能耗 , 协同节点 位于M1处时 ,根据公式(1)计算比较 两跳能耗E2h和单跳能 耗E1h得 :当L>1.5 Lideal时 ,E1h> E2h, 即多跳能 耗更小。 但是理想转 发位置处 一般不存 在节点 ,所以采用 协同节点 进行多跳的最小距离为Lmin= 准Lideal( 1 . 5 < 准 < 2 ) , 即当L < Lmin时直接传输 ,否则选择 协同节点 转发传输 。
2 . 2协同节点 选择机制
选择协同 节点时需 要确定协 同节点的 选择范围 , 即球体的位 置和半径r。
2 . 2 . 1 球 体 半 径 r 的 确 定
理想转发 节点空间 坐标即为 球心位置 , 在图1中设邻居最 优胞父节 点为P, 其坐标为 (XP, YP, ZP) , 同时令当前 胞元(XI,YI,ZI)C中胞父为M0, 其坐标为 (XM0,YM0,ZM0) ,理想转发 位置处球 心Mi的坐标为 (XMi, YMi, ZMi) 。以Mi的X轴坐标XMi为例 ,表达式为 :
其中i∈N且[1,Hideal- 1 ] 。
对于节点 密度较小 的网络 ,r值过小 ,球体内找 不到协同节 点 ;反之 ,会增加传 输路径。 假设存在rmax使r<rmax时 ,通过协同 节点进行 多跳比单 跳能耗更 少。为了 求得rmax考虑一种 极限情况 , 即所有的 球体内只 存在一个 协同节点 , 且位于球 体边缘 , 即图3 (b) 是由图3 (a) 投影到XOZ平面所得 。在图3(a) 中 , 节点C为当前胞 父 , 协同节点J位于球M1的边缘处 ,节点P为邻居最 优胞父 ,α = ∠CM1J , d表示LEN ( C , P ) , d1表示LEN (C ,J) ,d2表示LEN ( J , P ) , 通过节点J传输和直 接传输的 能耗分别为 :
当cosα=1时 ,即节点J位于W点处时E2h取得最大值 ,此时可得 到rmax表达式为 :
考察式 (7) 得 ,0.5 Lideal< rmax< Lideal, 实际情况 中选择球 体半径r=φrmax( 0 . 5 < φ < 1 ) , 其中φ称 为球体半 径调整系 数。
2 . 2 . 2 协 同 节 点 的 竞 选 法 则
协同节点 的区域确 定后 , 由低剩余 能量保护 原则和重复 选择避免 机制确定 候选协同 节点。结 合协同节点 选择原则 , 提出候选 协同节点G的竞选权 重( Election Weight , EW ) , 其表达式 为 :
其中G表示当前 候选协同 节点 ,n表示候选 协同节点 总数 ,K[j] 表示球体 中第j个候选协 同节点 ,LEN(K[j],Mi)表示球体Mi中第j个候选协 同节点与 球心Mi的距离 ,Eres ( K[ j ] )表示第j个候选协 同节点的 剩余能量 ,权重系数 λ和η的关 系为 :λ+η=1(0≤λ≤1,0≤η≤1)。其中θ 的取值遵循 以下原则 :当球体内 候选协同 节点是同 类型的节点 , 即都是胞 子或者胞 父节点时 θ =1; 否则 , 胞父节点θ = 1 , 胞子节点 θ = 0。
协同节点 竞选法则 : 将球体内 每个候选 节点的剩 余能量和空 间位置带 入式(8)中 ,按照上述 原则比较 球体内候选 节点的EW, 最后选择 出EW值最大的 作为本球 体的协同节 点。
2 . 3 3D - SMEER算法的具 体过程
结合自适 应多跳机 制和协同 节点选择 机制 , 总结出基于 协同节点 多跳路由 的步骤为 :
( 1 ) 根据贪婪 策略 , 判断出邻 居最优胞 父P , 并计算LEN ( C , P ) 。
( 2 ) 由自适应 多跳机制 判断采用 多跳或者 单跳 , 如果结果为 单跳则直 接把消息 包传递给 邻居最优 胞父P, 否则进入步 骤(3)。
(3) 利用协同节点选择机制确定球心的空间位置和协同节点的选择范围,然后根据低剩余能量保护原则和重复选择避免机制确定是否存在候选协同节点,若不存在则直接把消息包传递给邻居最优胞父P,否则进入步骤(4)。
( 4 ) 依据候选 节点的EW选择出协 同节点 , 将消息包通 过协同节 点转发给 邻居最优 胞父P。
具体流程 如图4所示。
3 仿真实验
3 . 1 仿 真 环 境 及 参 数 设 置
仿真是在OMNet++ V4.1平台上进 行的 , 节点分布在 体积为400 m×400 m×400 m的立方体 内。与3D-CSR和3D-SAEAR进行仿真 结果比较 时 ,为了使仿 真结果更有 可比性 ,假定消息 包只按照 贪婪模式 进行传输 。参数设定 如表1所示。
3 . 2 仿 真 结 果 分 析
仿真结果 将通过平 均能耗和 节点存活 率进行对 比。平均能 耗 (average energy consumption) 为传输k条消息包所 消耗的总 能耗与k的比值 ; 节点存活 率 (Alive rate) 为传递k条消息包 后存活节 点占总节 点数的百 分比。
3D - SMEER , 3D - SAEAR与3D - CSR的平均能 耗曲线如图5所示。3D-SAEAR与3D-CSR相比增加 了角度机制 ,所以其平 均能耗比3D-CSR略有减少 。3D-SMEER通过协同 节点转发 消息包 , 相比3D-SAEAR与3D-CSR有效降低 了平均能 耗。图5(a) 和图5(b) 中每个胞 元的节点个 数N分别为2和4, 随着N的增加 ,3D-SMEER增加了中 间协同节 点的个数 , 使得传输 能耗减少 , 所以图5(a) 和图5(b) 中3D-SMEER的平均能 耗是逐渐 降低的 ,而3D-SAEAR与3D-CSR的平均能 耗基本不 变。
三者的节 点存活率 与消息包 的关系如 图6所示。图6 ( a ) 和图6 ( b ) 中胞元的 节点数N分别为2和4 , 3D - CSR通过自适 应胞父选 举平衡了 网络的能 耗 , 所以3D-CSR与3D-SAEAR相比提高 了节点的 存活率 , 并且随着 胞元内节点 数N的增多 , 选举机制 能够发挥 更好的作 用 ;3D - SMEER与3D - CSR相比 , 通过协同 节点转发 消息包 , 降低了邻 居最优胞 父的传输 负担 , 从而提高 了网络节点 的存活率 , 当网络的 节点密度 增加时 , 增加了其 他节点参加 传输消息 包的概率 ,所以提高 了存活率 。
4 结 论
自适应路由优化 篇6
路由拓扑更新是设计无线自组织网络时的重要考虑因素[1,2]。由于频繁变化的无线自组织网拓扑结构需要有效的路由协议支持,所以对无线自组网路由协议拓扑更新规则的研究是很有必要的。文献[3]分析了路由拓扑更新策略对MANET路由协议性能的影响。文献[4]分析了AODV协议在不同节点移动速度下的路由性能。
MIL-STD-188-220D协议标准( 简称220D协议) 是无线自组网络技术的典型应用成果。它是美军CNR( 战斗网无线电台)的标准的最新版,我国高端军用和民用电台设计时也参考了220 系列协议。因此,对220D无线自组网路由拓扑更新的分析与优化具有广泛的意义。
220D路由协议采用的是源路由选择算法,使用稀疏路由树来交换拓扑结构信息,并定义了“最小网络拓扑更新时间间隔”( 简称最小时间间隔) 来防止节点过于频繁地发送拓扑更新消息,以节约无线频率资源。但当“最小网络拓扑更新时间间隔”设置较大时,会使拓扑更新消息得不到及时发送; 设置较小时,则使拓扑更新消息与数据分组竞争无线信道导致数据因碰撞而丢失,进而影响网络性能。针对此问题,本文提出一种自适应改变最小时间间隔的路由拓扑更新优化方法。仿真结果显示该方法可以改善220D及同类自组织网络性能。
1 220D路由拓扑更新分析
220D无线自组网协议采用的是源定向路由选择算法,节点入网时就要维护一张到网内其他节点的路由表,由事件触发拓扑更新。每个节点周期性地向邻居节点广播拓扑更新包,用于交互拓扑信息。
1. 1 最小网络拓扑更新时间间隔
为了防止网络拓扑剧烈变化时拓扑信息交换过于频繁,减小路由对无线信道的竞争,220D协议围为0 ~ 255,且只能取整数,单位为分钟。220D规定拓扑更新消息在每个最小时间间隔内发送不得超过一次,拓扑更新请求消息在每MIN_UPDATE_PER /2 内最多发送一次。将其置0 则可以禁止拓扑更新消息的发送与传输,即使网络中某个节点不移动也不能将其MIN_UPDATE_PER设置为0。因为当其检测到其他节点移动导致链路变化时也要发送拓扑更新消息。
1. 2 源定向路由
源定向中继方式为一种简单地从源节点到目的节点的非动态的中继过程。源节点需要发送分组时,首先从自己的路由表中查找、计算出经过内部网到达目的节点的路径,然后将路由信息编码进内部网报头,这就是表驱动路由协议的特点。其优点是节点发送报文时可以获得准确度较高的路由,能避免路由环路的发生,时延较小。
1. 3 拓扑更新
220D网络依靠节点间积极地交换拓扑信息来保证网络的正常通信。为此,220D协议专门定义了其拓扑更新数据结构,如图1 所示。其中节点1 的状态字节描述的是节点1 的前驱节点和源节点之间的链路状态。
如果网络在拓扑更新时,交换的是完整路由表,就会产生数据量很大的拓扑更新包,交互时就会占用很大的带宽,不适用于资源有限的ad hoc网络。因此,220D协议规定,只在相邻两个节点之间传递完整路由树的较小副本,即稀疏路由树。220D协议根据以下规则删除节点间的重复路径:
1) 只保留从根节点到其他节点的最短路径;
2) 根节点到另一节点之间长度相同的路径,最多保留两条。
假设两相邻两节点A与C的路由树如图2 所示。如果节点A与C之间交换完整的路由树,节点A就会把节点C的路由树保存到其自己的路由树里,如图3 所示。如果按照220D规定的交互规则,A与C之间只交换完整路由树的较小副本,那么交互后节点A的路由树如图4 所示。可以看出相邻节点之间交换稀疏路由树可以减少节点存储的路由树的数据量。
图 3 节点 A 的包括冗余路径的路由树
图 4 节点 A 的稀疏路由树
220D规定网络拓扑更新由以下条件触发,采用全网通播地址专门发送。(1) 节点A检测到一条失败的链路; (2) 节点A检测到一条新的链路; (3) 节点A检测到一条链路质量发送变化的链路; (4) 节点A收到了一条改变了其稀疏路由树的拓扑更新消息; (5) 节点A改变了其静默模式,并希望通告全网这一变化; (6)节点A改变了其中继能力; (7) 节点A收到拓扑更新请求。
2 基于NS2 的220D路由协议扩展
2. 1 NS2 仿真器介绍
NS2( Network Simulator,version 2) ,是一款开源的、离散事件驱动的网络环境模拟器,主要用于解决网络研究方面的问题[6]。NS模拟分两个层次: 一是只需编写Otcl脚本,利用NS已有的网络模块实现模拟; 另一层次是基于C ++ 和Otcl编程,对NS进行扩展,添加自己要模拟的模块[7]。
2. 2 220D路由协议扩展
由于NS2 现有仿真库中不包括220D路由协议模块,需要添加C ++ 类以实现220D路由协议。本文在添加220D路由协议的编程过程中参考了NS2 下的DSDV和DSR路由协议源代码。为了减少拓扑更新的数据量,220D定义了稀疏路由树,类设计代码如下所示:
NS2中的Agent代表生成和消耗网络层数据分组的端点,同时被用于实现不同网络层次的协议[4],其主要功能是在源节点与目的节点之间创建一条端到端的连接。其他路由协议Agent类的实现要继承父Agent类。220D路由协议Agent类部分代码如下所示:
3 220D路由协议性能分析
为了判断和衡量某种路由协议的性能高低,需要通过定性和定量的评估指标来度量[8]。本节主要仿真220D网络cbr流发送速率随着节点停留时间的增大时对网络分组传输成功率的影响。节点停留时间能表征网络拓扑变化的快慢,节点停留时间越短,网络拓扑变化越快,节点停留时间较长时,网络拓扑变化较慢。分组传输成功率指目的节点成功接收到的分组数与发送节点发送的分组数的比值。当节点来不及更新变化较快的网络拓扑时,或者网络负载较大分组之间竞争无线信道时,分组就会丢失,所以分组传输成功率能反映路由协议性能的好坏。
3. 1 仿真场景
由于本文主要研究220D路由协议,所以在仿真时采用NS2缺省的其他各层协议。设置了如下的仿真场景: 在800 m ×800 m区域内均匀放置20 个节点,业务是cbr流,每包512 字节,网络中节点的最大移动速度为20 m/s,移动方向随机,节点停留时间手动设置,仿真时间为600 s。
3. 2 CBR发送速率对220D网络性能影响
cbr流发送速率( 单位为kbps) 可以表征网络负载,是影响网络性能的重要因素。cbr发送速率越大,说明网络负载越大,网络负载过大时,会导致分组在MAC层碰撞而丢失,使网络性能下降。图5 为cbr流发送速率分别取4、8、12 和16 kpbs时,网络的分组传输成功率情况。
从图5 中可以看出,cbr发送速率不变时,网络分组传输成功率大致随节点停留时间的增加而增大; 节点停留时间不变时,网络分组传输成功率大致随cbr发送速率的增大而减少。
4 220D路由拓扑更新优化
220D协议标准定义了最小时间间隔来减小拓扑更新频率,但当最小时间间隔取值较小时,拓扑更新发送过于频繁,和cbr流竞争无线信道,导致用户数据分组因碰撞而丢失。而当其值取值太大时,节点就不能及时获取网络拓扑结构,使用过期的路由信息发送或传递分组,会使分组不可达,进而降低了220D网络性能。对于真实的无线自组织网络,特别是在战术环境中,节点移动速度和网络负载都不确定,无法根据这两项参数设置合适的MIN_UPDATE_PER值。因此,如何在节点移动速度和网络负载动态、无规律变化的情况下,既能及时更新网络拓扑信息,又不会占用大量的网络资源导致分组冲突,是220D路由协议需要解决的问题。
针对以上问题,本文提出了一种通过自适应改变最小时间间隔来提高网络性能的方法。对于优化前的网络,当节点需要发送拓扑更新信息时,要等待当前的MIN_UPDATE_PER时间结束后才能发送。本文做如下优化: 在每个节点上设定一个队列缓冲区,节点需要拓扑更新时,首先检查更改了的拓扑更新信息是否涉及正在使用的路由信息; 如果是,则不需要等待当前最小时间间隔结束,而是立刻发送拓扑更新; 否则将拓扑更新包缓存到缓冲区,等待新的最小时间间隔周期到来时,节点从缓存区取出第一条拓扑信息发送出去。当缓存区里的拓扑更新包大于两条时,节点就自动将当前最小时间间隔值减1,即增大拓扑更新频率; 相反,如果缓存区里拓扑更新包为0 条时,说明节点没有检测到链路变化,就不需要广播拓扑更新包,节点就自动将当前最小时间间隔值加1。
对上述的优化,本文进行了如下仿真和比较。对优化前的网络将最小时间间隔值( 图中用per表示) 设置为1 和3 分钟( per = 1 或3 min) ; 优化后的网络最小时间间隔自适应改变,优化前后的网络cbr流发送速率都为8 kbps,仿真并统计优化前后的网络分组传输成功率,仿真结果如图6 所示。
从仿真结果可以看出,对优化前的网络,拓扑变化较快时,最小时间间隔为1 min时的网络性能优于最小时间间隔为3 min时的; 拓扑变化较慢时,最小时间间隔为3 min时的网络性能稍优于最小时间间隔为1 min时的。优化后的网络分组传输功率跟优化前的相比较高,即网络性能更好,且优化后的网络分组传输成功率上下波动较小,即网络性能更加稳定。
5 结语
本文主要在分析220D无线自组网路由拓扑更新的基础上,针对拓扑更新参数“最小网络拓扑更新时间间隔”设置不合适时,会影响网络性能的问题,提出了一种自适应改变最小时间间隔的220D路由拓扑更新优化方法。基于NS2 仿真平台对优化前后的网络进行了仿真对比,结果显示该方法可以改善220D网络性能。本文可为研究其他无线自组网路由拓扑更新或220D路由协议提供一定的参考价值。
参考文献
[1]周鑫.自组网中一种基于能量均衡的选择性洪泛路由算法[J].计算机应用与软件,2014,31(7):101-104.
[2]刘军,孙茜,王英梅.支持网络编码的认知无线自组网拓扑控制算法[J].通信学报,2013,34(5):136-142.
[3]Mohapatra S,Kanungo P.Performance analysis of AODV,DSR,OLSR and DSDV Routing Protocols using NS2 Simulator[J].Procedia Engineering,2012,30(7):69-76.
[4]Ismail Z,Hassan R.A performance study of various mobility speed on AODV routing protocol in homogeneous and heterogeneous MANET[C]//Communications(APCC),2011 17th Asia-Pacific Conference on.IEEE,2011:637-642.
[5]MIL-STD-188-220D.Department of Defense Interface Standard Digital Message Transfer DEVICE Subsystems[S].2005.
[6]于斌,孙斌,温暖,等.NS2与网络模拟[M].北京:人民邮电出版社,2007.
[7]Li Baiping,Zhang Xiaoqin.Rsearch of development in wireless sensor network routing protocols based on NS2[C]//Electronic and Mechanical Engineering and Information Technology(EMEIT),2011:1913-1916.
自适应路由优化 篇7
Qo S路由(Quality of Service Routing)是Internet提供有效网络服务质量的关键技术之一[1]。动态Qo S路由指Internet动态环境下,为不同业务接入Internet时选择满足其各个度量参数要求的传输路径,同时优化网络资源。然而,在Internet动态环境下,Internet尽力而为服务模式并不能为不同业务选择满足其Qo S要求的有效路径。主要原因是Internet度量参数不断变化,尽力而为服务模式容易造成路径过期无效问题。其中,度量参数包括加性参数、乘性参数及凹性参数。
当前在研究动态Internet环境下Qo S路由方面,文献[2]从概率统计学角度提出基于不精确度量参数的路径选择算法。文献[3]从模糊度角度考虑了基于不精确度量参数的多约束路径选择算法。文献[4]主要讨论了非精确参数环境下移动互联的Qo S路径选择过程。以上算法虽然都考虑了Internet度量参数不断变化对Qo S路由的影响,但是依然不能解决路径过期无效问题。
针对此,本文基于反向学习的思想,提出一种自反学习粒子群优化算法(Self-Opposition-based Learning based on PSO,SOLPSO),SOLPSO算法相对当前传统粒子群算法[5]主要优点是,在Internet动态环境下,通过自反学习策略可以有效扩大粒子搜索范围,使得算法能时刻动态追逐有效解,同时克服传统粒子群无法在动态环境下收敛问题,进而提高算法搜索性能。
1 问题描述
根据动态Qo S路由定义,本文从多目标优化角度对动态Qo S路由问题建模。
设G=(V,E,t)表示网络,其中V为节点集合,E为链路集合,t为时间。每条链路e∈E上都拥有一组参数k(k=1,2,…),且链路上参数具有动态时变性,现给定一组参数约束值Ck,k=1,2,…,在时间t内以及满足约束条件下,寻找一组非劣解x,使得总体目标函数F最优:
其中,fk(x),k=1,2,…表示子参数目标函数,X(t)表示时间函数。
2 算法描述
SOLPSO算法主要思想:每个粒子在搜索解过程中,当探测到解发生动态变化时,通过自反学习策略计算其反向点,根据反向点扩大其搜索范围,从而使得算法能始终动态得追逐有效解,同时使得算法能在动态环境下快速收敛。
2.1 传统粒子群算法
粒子群优化算法是一种群体智能优化[5],主要思想来源于仿生大自然生物系统中鸟群寻找食物的群体社会行为。在粒子群优化过程中,每个粒子主要通过飞行速度、当前个体极值点(pl)及全局极值点(pg)来更新自己当前的位置:
其中,vik-1,vik分别表示飞行速度,c1,c2分别表示权重系数,rand∈(0,1)表示随机函数,xik-1,xik分别表示前一时刻及后一时刻位置。根据公式(2)、(3)最终使得当前粒子不断向具有食物的最佳位置靠近,也即搜索到最优解。
2.2 自反学习策略
文献[6]-[7]首次提出基于反向学习(Opposition-based Learning,OBL)的群体智能方法。该方法认为,在动态环境下粒子在搜索有效解时可能会偏离全局最优,从而容易陷入局部最优。但是,如果通过反向学习策略,可能使得粒子重新靠近全局最优,从而提高群体智能搜索性能。
自反学习思想:当粒子探测到当前解发生动态变化时,通过一种映射策略,使得当前粒子能够映射到其相反位置,也即反向点。然后粒子在其反向位置继续搜索有效解,最后分别比较在原位置搜索到的有效解及在反向点搜索到的有效解,并保存较优的有效解。
反向点(Opposition Point,OP):假设空间为D维,s=(s1,s2,…,sD)表示空间一点,且sj∈[smin,smax],其中smin,smax分别表示下界及上界。设映射函数[OP],使得,则s*=(s1*,s2*,…,sD*)表示s的反向点,且映射函数[OP][8,9]及s*分别描述为:
其中,χ∈(0,1)表示参数,k表示迭代次数。
2.3 SOLPSO算法实现
Step1初始化群体规模N、粒子的初始位置、初始速度及其评估函数,设置数组变量bw,设定最大迭代次数dmax,转入Step2。
Step2每个粒子探测当前解是否发生变化,如果发生变化转入Step3;否则转入Step4。
Step3根据公式(4)、(5)计算其反向点,并记录保存,转入Step4。
Step4计算每个粒子包括其反向点粒子的个体极值pl及当前群体的全局极值pg,并且每个粒子包括其反向粒子根据公式(2)、(3)来更新其对应的位置,转入Step5。
Step5 bw记录当前群体最优位置,判定dmax是否满足条件,如果满足则转入Step6;否则转入Step2。
Step6保存退出。
3 实验与分析
仿真环境:服务器配置为:CPU为AMD皓龙4122,内存2G,硬盘100G,操作系统为SUSE Linux Enterprise Server 10,测试软件工具NS2。
参数设置:参数C1、C2分别为2,N=[500,1000],rand∈(0.8,1),dmax∈[300,500]。
网络结构:根据NS2模拟结果,分别构建了不同的网络拓扑结构,其节点个数在100~200之间,链路条数在160~280之间,并且每条链路上有n个度量参数,每个度量参数的约束及其值随机产生。
实验1:测试在不同网络结构中,算法SOLPSO与当前经典算法MP-POC[2]和MOPP[3]之间Qo S满意度比较,Qo S满意度=服务成功数/服务总数。
如图1所示,横坐标表示节点数,纵坐标表示Qo S满意度。在100~150个节点情况下,SOLPSO算法,MP-POC算法和MOPP满意度分别为92.85%、90.05%和89.5%;在150~200个节点情况下,SOLPSO算法,MP-POC算法和MOPP满意度分别为89.55%、86.25%和85.7%。总体而言,SOLPSO算法Qo S满意度相对较高。
实验2:测试在不同网络结构中,算法SOLPSO与当前经典算法MP-POC[2]和MOPP[3]之间服务延迟率比较,服务延迟率=服务延迟时间/服务正常时间。
如图2所示,横坐标表示节点数,纵坐标表示服务延迟率。在100~150个节点情况下,SOLPSO算法,MP-POC算法和MOPP服务延迟率分别为19.75%、22.9%和23.25%;在150~200个节点情况下,SOLPSO算法,MP-POC算法和MOPP服务延迟率分别为24.8%、28.9%和29.15%。总体而言,SOLPSO算法服务延迟率相对较低。
实验3:测试在不同网络结构中,算法SOLPSO与传统PSO算法搜索到解的有效率性能比较。
如图3所示,横坐标表示节点数,纵坐标表示解的有效率。在100个节点下,SOLPSO算法和PSO算法解的有效率分别为95%和91.1%,提高4.1%;在150个节点下,SOLPSO算法和PSO算法解的有效率分别为91%和87%,提高5%;在200个节点下,SOLPSO算法和PSO算法解的有效率分别为87.5%和80%,提高9.375%。
4 结束语
本文提出一种自反学习粒子群优化算法,通过引入自反学习策略计算反向点,并进一步基于反向点扩大搜索范围,从而使得算法快速收敛。实验表明,该算法在动态环境下搜索具有较好性能。
参考文献
[1]熊轲,裘正定,张煜,等.多加性Qo S约束下的链路分离路由算法[J].通信学报,2010,31(6):127-135.
[2]田菁,郑彦兴.基于不精确信息的Pareto最优路径搜索[J].通信学报,2007,28(3):68-77.
[3]张品,李乐民,王晟.运用模糊数解决非确定环境下的路由问题[J].电子学报,2003,31(12):1861-1866.
[4]戴慧珺,曲桦,赵季红.利用非精确参数的移动互联网业务感知多目标优化Qo S路由算法[J].西安交通大学学报,2014,48(2):86-92.
[5]王兴伟,王军伟,吴铁艳,等.NGI中一种基于粒子群优化的Qo S单播路由算法[J].东北大学学报,2006,27(1):21-24.
[6]Tizhoosh H.Opposition-based learning:A new scheme for machine intelligence[C]∥Proceedings of the International Conference on Computational Intelligence for Modeling Control and Automation,2005:695-701.
[7]Rahnamayan S,Tizhoosh H,Salama M M.Opposition-based differential evolution[J].IEEE Transactions on Evolutionary Computation,2008,12(1):64-79.
[8]Tizhoosh H,Malisia A R.Applying Opposition-based ideas to the ant colony system[C].Proceedings of IEEE Swarm Intelligence Symposium,2007:79-87.