采用多目标差分进化的移动Ad Hoc网络节能路由算法

魏文红， 秦勇

(东莞理工学院 计算机学院, 广东 东莞 523808)



采用多目标差分进化的移动Ad Hoc网络节能路由算法

魏文红， 秦勇

(东莞理工学院 计算机学院, 广东 东莞 523808)

为了在节点的能量消耗和最优路由之间找到一个平衡，根据多目标差分进化算法原理，提出一种基于多目标差分进化的移动Ad Hoc网络节能路由算法.该算法把路由代价和网络生存时间作为2个优化目标，采用适应值变换的约束处理技术、非支配排序和拥挤距离技术进行优化.在优化过程中，提出适合差分进化算法的变异、交叉和选择策略.结果表明：该算法在网络生存时间和最优路由方面具有较好的优势，并保证了较高的包传递率.

多目标； 差分进化； 移动Ad Hoc； 路由； 生存时间

移动Ad Hoc网络是一种多跳的、自组织的网络，每个节点既是主机，又是路由器，节点之间的通信通过无线信号覆盖的多跳路由进行.如果对方节点不在自己的信号覆盖范围内，则可借助其他节点进行转发.移动Ad Hoc网络由于搭建容易，被广泛应用于各种领域.在移动Ad Hoc网络中，根据路由表协议的驱动方式，可以将路由协议分为表驱动路由协议和按需启动路由选择协议[1-4].按需启动路由在有节点需要发送信息时，才进行路由发现过程，鉴于移动Ad Hoc网络动态的网络拓扑结构，按需路由选择比表驱动路由选择具有更大的优势.许多学者对各类移动Ad Hoc网络路由协议，特别是基于蚁群算法的移动Ad Hoc网络路由协议进行了广泛地研究[4-10].近年来，基于遗传算法和粒子群算法的移动Ad Hoc网络的路由算法也受到关注[11-13]，但利用差分进化算法研究移动Ad Hoc网络的节能路由算法却未见报导.本文基于差分进化算法，利用多目标求解技术，同时考虑节点能量消耗的约束，提出基于多目标差分进化的节能路由算法(MOR-DE).

1　问题模型

移动Ad Hoc网络模型都可以用一个加权无向图G=(V,E)表示.其中，V={v1,v2,…,vp}表示网络中的节点集；E={e1,e2,…,eq}表示网络中的链路集.此外，采用权值向量w表示链路间的代价、时延和带宽等.

假设s∈V为路由的源节点，d∈{V-s}为路由的目标节点，|V|为节点总数，|E|为链路总数，R+为正实数集合，则某一条链路e上路由代价、时延和带宽函数分别为

Cost(e):E→R+，Delay(e):E→R+，Bandwidth(e):E→R+.

在路由过程中，假定p(s,d)表示源节点s到目标节点d的路径，则整个网络的路由代价函数、时延和带宽函数为

(1)

(2)

(3)

再假设节点i的度为Degi；剩余能量为Enyi；φi，j表示节点i到节点j的数据流；θi，j表示节点i传输一个数据包到节点j所消耗的能量.

假定φi，j和θi，j的值在所有的节点中都相等，则节点i和j之间能量消耗为Ci，j=φi，j×θi，j.因此，整个网络的生存时间表示为

(4)

由式(4)可知：节点的度越大，节点的能量消耗也越大.

一般情况下，在移动AdHoc网络中，路由代价与网络生存时间是2个相互冲突的因素.因此，可以考虑把这2个因素建模为多目标优化问题，同时，把链路上的时延和宽带考虑成约束条件.最终，目标函数可表示为

(5)

在约束条件中，链路中最大的时延应该小于或等于时延阈值QD，最小带宽应该大于或等于某条链路中的最小带宽阈值QB.

2　MOR-DE算法

2.1路径编码

在移动AdHoc网络中，路由是从源节点到目的节点的路径组成.每条路径可以表示1个种群个体，则所有的路径集即可表示差分进化算法中的一个种群.由于路由中路径的长度未必都是相等的，而种群个体的维度却是相同的，所以对于路径长度小于个体维度情况，可以采用后面补“0”的方式使路径长度等于个体的维度.

2.2算法描述

MOR-DE算法采用约束处理技术、非支配排序、拥挤距离和路径编码，基于多目标差分进化算法原理实现.

1) 种群初始化.对于移动AdHoc网络模型G，随机生产NP条源节点s到目标节点d的路径，采路径编码方法对这NP条路径进行编码，即产生了具有NP个个体的初始种群.

2) 变异策略.差分进化算法中的变异操作是采用差分向量来产生一个变异个体，以rand/1为例介绍变异过程.首先，从种群任意选择3个个体x1，x2和x3，对于x3，以概率p随机地选择1个中间节点，如sj.然后，沿着x2，从目标节点向源节点方向，查找相同的节点sj.如果节点sj被找到，则把x3中从sj到d的这段路径与x2中从sj到d的这段路径交换；如果没有找到相同的节点sj，则一直重复该过程，直到找到为止.经过该操作之后，x2和x3就变成2条新的路径.同理，对于x2，以概率p随机地选择一个中间节点，如si.然后，沿着x1，从目标节点向源节点方向，查找相同的节点si.如果节点si被找到，则把x2中从si到d的这段路径与x1中从si到d的这段路径交换；如果没有找到相同的节点si，则一直重复该过程，直到找到为止.经过上述2个操作之后，x1，x2和x3就变成3条新的路径，变异操作完成.当所有的路径不等长时，变异策略同样适用.

3) 交叉策略.对于交叉策略，以概率CR从种群中选择2个个体x1和x2，在x1和x2中随机地选择2个节点si和sj作为交叉的起始端点.然后，交换从节点si和节点sj之间的路径.如果在x1和x2中没有发现相同的节点si和sj，则选择过程就一直持续，直到发现为止.

4) 选择策略.采用约束处理技术计算父代和子代个体的目标函数值.当子代个体支配父代个体，则用子代个体替换父代个体；如果父代个体支配子代个体，则丢弃子代个体；如果父代个体与子代个体之间是非支配的关系，则父代个体和子代个体同时存档.

Algorithm1:PseudocodeofMOR-DEalgorithm

搜索网络模型G中从源节点s到目标节点d的路径集xi(1≤i≤NP);

生成初始种群P0=(x1,x2,…,xNP);

计算种群P0的目标函数适应值和约束违反程度;

t=0;∥t表示代数.

repeat

t=t+1;

昨天在鲁镇没看到“祝福”仪式的表演，今天就打算到绍兴市鲁迅故里再去看看。加上鲁迅故里的“祝福”仪式媒体多有报道，所以我今天就更想一睹究竟了。天公作美，久违的太阳出来了。虽然气温还低，但阳光让游客都兴致盎然。鲁迅故里人山人海，散客、旅游团等操着天南地北不同口音来到了这个江南古镇的旅游景区，想一睹这位大文豪生活过的地方。我问了几个工作人员，才终于找到“祝福”仪式的表演地——鲁迅祖居。“祝福”仪式在德寿堂举行。初一到初五，每天上下午各两场，每场持续15分钟。

Pt=Pt-1;

for种群Pt中的每一个个体do

运用变异策略求出变异向量;

运用交叉策略求出交叉向量;

运用选择策略求出子代;

end

Pi=Pt+1;

计算种群Pt的目标函数适应值和约束违反程度;

采用非支配排序和拥挤距离排序技术从种群Pt中选择NP个个体组成新的种群Pt;

untilt>Gmax;∥Gmax表示最大的代数.

输出:种群Pt.

原始差分进化算法的时间复杂度为O(Gmax·NP·n).其中，Gmax为最大的代数.非支配排序的时间复杂为O(k·NP2).其中，k为目标数.文中，k=2.

由于拥挤距离排序的时间复杂度O(k·NP·logNP)，故MOR-DE的时间复杂度为O(Gmax(NP·n+2·NP2+NP·logNP))，即O(Gmax·NP2).

3　实验结果分析

为了验证MOR-DE算法的有效性，将MOR-DE算法与SAMP-DSR[7]，QAMR[9]，ACECR[10]算法进行实验比较.实验环境为Matlab2013b仿真平台，IntelCoreQuadCPU2.83GHz，4.00GB内存.采用Waxman′s随机生产器构建1个随机的移动AdHoc网络结构模型.

3.1参数设置

参数设置如下：1) 网络规模N=10,20,30,40,50,60,70,80,90,100；2) 链路代价C=rand(2,10)；3) 链路时延D=2/3×Cms；4) 链路带宽B=rand(50,200)Kbit·s-1；5) 节点能量E=40min；6) 链路最大时延QD=rand(60,80)ms；7) 链路最小带宽QB=rand(100,150)Kbit·s-1.

3.2结果分析

由于多目标算法求解的结果1个满足所有目标的折中解集，所以MOR-DE算法与单目标算法SAMP-DSR,QAMR和ACECR等在比较过程中，选取了MOR-DE算法解集中的边界结果与其进行比较.如果MOR-DE算法解集中的边界结果都优于那些单目标算法的解，那么MOR-DE算法的其他解必定更优于其他算法.

MOR-DE算法与SAMP-DSR，QAMR，ACECR算法在路由代价和网络生生存时间方面的比较结果，如表1所示.表1中：t为生存时间.

由表1可知：当网络节点数大于40时，MOR-DE算法获得所有更优的解；当网络节点数小于30时，MOR-DE获得与QAMR和ACECR算法非支配的解.

表1　算法获取的最优解比较

表2　Friedman测试结果

对MOR-DE，SAMP-DSR，QAMR，ACECR等4种算法进行Friedman测试及Wilcoxon符号秩检验测试[14]，测试结果如表2，3所示.

由表2可知：无论是对于路由代价目标，还是网络生存时间目标，MOR-DE的排名都处于第一的位置.

由表3可知：MOR-DE获得的R+值明显比R-值要大， 这说明MOR-DE算法明显优于SAMP-DSR，QAMR和ACECR算法.

表3　Wicoxon符号秩检验测试结果

为了验证算法的收敛性，对4种算法的收敛性进行测试，其收敛图(网络节点为40)，如图1所示.图1中：n1为代数.由图1可知：MOR-DE算法的收敛速度是最快的，说明MOR-DE算法在收敛性方面明显优于其他3种算法.

4种算法的包传递率(η)，如图2所示.由图2可知：当网络节点数(n2)较小时，4种算法的包传递率相差不明显，但随着网络节点数的慢慢增大，MOR-DE算法的优势越加明显.

(a) 路由代价 (b) 网络生存时间　　　　　　　　　　　　　　　　　　　　　　　　　　　图1　4种算法的收敛图　　　　　　　　　　　　　　图2　4种算法的包传递率　　　Fig.1　Convergence graph of four algorithms　　　　　　　　　Fig.2　Packet transmission ratio　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　of four algorithms

4　结束语

提出一种基于多目标差分进化算法的移动Ad Hoc网络节能路由算法MOR-DE，修改了差分进化算法的变异、交叉和选择策略，使算法能够适应问题模型.与SAMP-DSR,QAMR,ACECR算法进行比较，MOR-DE算法在路由代价和网络生存时间方面取得一个较好的平衡，且具有较高的包传递率.

[1]MURTHY J J,GARCIA L A.A routing protocol for packet radio networks[C]∥1st Annual ACM International Conference on Mobile Computing and Networking.New York:ACM Press,1995:86-95.

[2]JOHNSON D B,MALTZ A D,BROCH J.The dynamic source routing protocol for multi-hop wireless Ad Hoc networks[M].New York:ACM Press,2001:139-172.

[3]PERKINS C E,ROYER E M.Ad hoc on demand distance vector (AODV) routing[C]∥2nd IEEE Workshop on Mobile Computing Systems and Applications.Piscataway:IEEE Press,1999:90-100.

[4]SHOKRANI H,SAM J.A survey of ant-based routing algorithms for mobile Ad-Hoc networks[C]∥The International Conference on Signal Processing Systems.Piscatawa:IEEE Press,2009:323-329.

[5]WANG Jianping,OSAGIE E,THULASIRAMAN P,et al.A hybrid ant colony optimization routing algorithm for mobile Ad Hoc network[J].Ad Hoc Networks,2009,7(4):690-705.

[6]周少琼,徐祎,姜丽,等.蚁群优化算法在Ad Hoc网络路由中的应用[J].计算机应用,2011,31(2):332-334.

[7]KHOSROWSHAHI-ASL E,MAJID N,ATIEH S P.A dynamic ant colony based routing algorithm for mobile Ad-Hoc networks[J].Journal of Information Science and Engineering,2011,27(5):1581-1596.

[8]CHATTERJEE S,SWAGATAM D.Ant colony optimization based enhanced dynamic source routing algorithm for mobile Ad-Hoc network[J].Information Sciences,2015,295:67-90.

[9]KRISHNA P V,SARITHA V,VEDHA G,et al.Quality-of-service-enabled ant colony-based multipath routing for mobile Ad Hoc networks[J].IET Communications,2012,6(1):76-83.

[10]ZHOU Jipeng,WANG Xuefeng,TAN Haisheng,et al.Ant colony-based energy control routing protocol for mobile Ad Hoc networks[C]∥Wireless Algorithms, Systems, and Applications.Berlin:Springer,2015:845-853.

[11]詹思瑜,李建平.基于遗传算法的Ad Hoc 路由协议优化[J].小型微型计算机系统,2012,33(1):24-27.

[12]朱晓建,沈军.基于粒子群优化的Ad Hoc 网络最小能耗多播路由算法[J].通信学报,2012,33(3):52-58.

[13]DEEPALAKSHMI P,SHANMUGASUNDARAM R.An ant colony-based multi objective quality of service routing for mobile Ad Hoc networks[J].EURASIP Journal on Wireless Communications and Networking,2011,2011(1):1-12.

[14]DERRAC J,GARCLA S,MOLINA D,et al.A practical tutorial on the use of nonparametric statistical tests as a methodology for comparing evolutionary and swarm intelligence algorithms[J].Swarm and Evolutionary Computation,2011,1(1):3-18.

(责任编辑： 钱筠 英文审校： 吴逢铁)

Energy Efficient Routing Optimization Algorithm for MANET Based Multi-Objective Differential Evolution

WEI Wenhong, QIN Yong

(School of Computer, Dongguan University of Technology, Dongguan 523808, China)

To find a balance between energy consumption and optimal routing, according to the principle of multi-objective differential evolution algorithm, an energy efficient routing algorithm for MANET based on multi-objective differential evolution. In this algorithm, the shortest routing paths and network lifetime are considered as two objectives, and the fitness transformation, non-dominated sorting and crowding distance technologies are adopted to optimize the above objectives. In the optimization process, the modified mutation, crossover and selection operations in differential evolution are proposed for. Compared with other routing optimization algorithms, this algorithm can achieve better result between network lifetime and optimal routing, and provide higher packet transmission.

multi-objective; differential evolution; mobile Ad Hoc; routing; lifetime

10.11830/ISSN.1000-5013.201605026

2016-02-03

魏文红(1977-)，男，副教授，博士，主要从事网络与并行分布计算、智能优化处理的研究.E-mail:weiwh@dgut.edu.cn.

国家自然科学基金资助项目(61103037, 61300198); 广东省自然科学基金资助项目(S2013010011858); 广东省高校科技创新项目(2013KJCX0178)

TP 393

A

1000-5013(2016)05-0654-05