魏文紅， 秦勇

(東莞理工學(xué)院 計算機學(xué)院, 廣東 東莞 523808)

?

采用多目標(biāo)差分進化的移動Ad Hoc網(wǎng)絡(luò)節(jié)能路由算法

魏文紅， 秦勇

(東莞理工學(xué)院 計算機學(xué)院, 廣東 東莞 523808)

為了在節(jié)點的能量消耗和最優(yōu)路由之間找到一個平衡，根據(jù)多目標(biāo)差分進化算法原理，提出一種基于多目標(biāo)差分進化的移動Ad Hoc網(wǎng)絡(luò)節(jié)能路由算法.該算法把路由代價和網(wǎng)絡(luò)生存時間作為2個優(yōu)化目標(biāo)，采用適應(yīng)值變換的約束處理技術(shù)、非支配排序和擁擠距離技術(shù)進行優(yōu)化.在優(yōu)化過程中，提出適合差分進化算法的變異、交叉和選擇策略.結(jié)果表明：該算法在網(wǎng)絡(luò)生存時間和最優(yōu)路由方面具有較好的優(yōu)勢，并保證了較高的包傳遞率.

多目標(biāo)； 差分進化； 移動Ad Hoc； 路由； 生存時間

移動Ad Hoc網(wǎng)絡(luò)是一種多跳的、自組織的網(wǎng)絡(luò)，每個節(jié)點既是主機，又是路由器，節(jié)點之間的通信通過無線信號覆蓋的多跳路由進行.如果對方節(jié)點不在自己的信號覆蓋范圍內(nèi)，則可借助其他節(jié)點進行轉(zhuǎn)發(fā).移動Ad Hoc網(wǎng)絡(luò)由于搭建容易，被廣泛應(yīng)用于各種領(lǐng)域.在移動Ad Hoc網(wǎng)絡(luò)中，根據(jù)路由表協(xié)議的驅(qū)動方式，可以將路由協(xié)議分為表驅(qū)動路由協(xié)議和按需啟動路由選擇協(xié)議[1-4].按需啟動路由在有節(jié)點需要發(fā)送信息時，才進行路由發(fā)現(xiàn)過程，鑒于移動Ad Hoc網(wǎng)絡(luò)動態(tài)的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，按需路由選擇比表驅(qū)動路由選擇具有更大的優(yōu)勢.許多學(xué)者對各類移動Ad Hoc網(wǎng)絡(luò)路由協(xié)議，特別是基于蟻群算法的移動Ad Hoc網(wǎng)絡(luò)路由協(xié)議進行了廣泛地研究[4-10].近年來，基于遺傳算法和粒子群算法的移動Ad Hoc網(wǎng)絡(luò)的路由算法也受到關(guān)注[11-13]，但利用差分進化算法研究移動Ad Hoc網(wǎng)絡(luò)的節(jié)能路由算法卻未見報導(dǎo).本文基于差分進化算法，利用多目標(biāo)求解技術(shù)，同時考慮節(jié)點能量消耗的約束，提出基于多目標(biāo)差分進化的節(jié)能路由算法(MOR-DE).

1　問題模型

移動Ad Hoc網(wǎng)絡(luò)模型都可以用一個加權(quán)無向圖G=(V,E)表示.其中，V={v1,v2,…,vp}表示網(wǎng)絡(luò)中的節(jié)點集；E={e1,e2,…,eq}表示網(wǎng)絡(luò)中的鏈路集.此外，采用權(quán)值向量w表示鏈路間的代價、時延和帶寬等.

假設(shè)s∈V為路由的源節(jié)點，d∈{V-s}為路由的目標(biāo)節(jié)點，|V|為節(jié)點總數(shù)，|E|為鏈路總數(shù)，R+為正實數(shù)集合，則某一條鏈路e上路由代價、時延和帶寬函數(shù)分別為

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

在路由過程中，假定p(s,d)表示源節(jié)點s到目標(biāo)節(jié)點d的路徑，則整個網(wǎng)絡(luò)的路由代價函數(shù)、時延和帶寬函數(shù)為

(1)

(2)

(3)

再假設(shè)節(jié)點i的度為Degi；剩余能量為Enyi；φi，j表示節(jié)點i到節(jié)點j的數(shù)據(jù)流；θi，j表示節(jié)點i傳輸一個數(shù)據(jù)包到節(jié)點j所消耗的能量.

假定φi，j和θi，j的值在所有的節(jié)點中都相等，則節(jié)點i和j之間能量消耗為Ci，j=φi，j×θi，j.因此，整個網(wǎng)絡(luò)的生存時間表示為

(4)

由式(4)可知：節(jié)點的度越大，節(jié)點的能量消耗也越大.

一般情況下，在移動AdHoc網(wǎng)絡(luò)中，路由代價與網(wǎng)絡(luò)生存時間是2個相互沖突的因素.因此，可以考慮把這2個因素建模為多目標(biāo)優(yōu)化問題，同時，把鏈路上的時延和寬帶考慮成約束條件.最終，目標(biāo)函數(shù)可表示為

(5)

在約束條件中，鏈路中最大的時延應(yīng)該小于或等于時延閾值QD，最小帶寬應(yīng)該大于或等于某條鏈路中的最小帶寬閾值QB.

2　MOR-DE算法

2.1路徑編碼

在移動AdHoc網(wǎng)絡(luò)中，路由是從源節(jié)點到目的節(jié)點的路徑組成.每條路徑可以表示1個種群個體，則所有的路徑集即可表示差分進化算法中的一個種群.由于路由中路徑的長度未必都是相等的，而種群個體的維度卻是相同的，所以對于路徑長度小于個體維度情況，可以采用后面補“0”的方式使路徑長度等于個體的維度.

2.2算法描述

MOR-DE算法采用約束處理技術(shù)、非支配排序、擁擠距離和路徑編碼，基于多目標(biāo)差分進化算法原理實現(xiàn).

1) 種群初始化.對于移動AdHoc網(wǎng)絡(luò)模型G，隨機生產(chǎn)NP條源節(jié)點s到目標(biāo)節(jié)點d的路徑，采路徑編碼方法對這NP條路徑進行編碼，即產(chǎn)生了具有NP個個體的初始種群.

2) 變異策略.差分進化算法中的變異操作是采用差分向量來產(chǎn)生一個變異個體，以rand/1為例介紹變異過程.首先，從種群任意選擇3個個體x1，x2和x3，對于x3，以概率p隨機地選擇1個中間節(jié)點，如sj.然后，沿著x2，從目標(biāo)節(jié)點向源節(jié)點方向，查找相同的節(jié)點sj.如果節(jié)點sj被找到，則把x3中從sj到d的這段路徑與x2中從sj到d的這段路徑交換；如果沒有找到相同的節(jié)點sj，則一直重復(fù)該過程，直到找到為止.經(jīng)過該操作之后，x2和x3就變成2條新的路徑.同理，對于x2，以概率p隨機地選擇一個中間節(jié)點，如si.然后，沿著x1，從目標(biāo)節(jié)點向源節(jié)點方向，查找相同的節(jié)點si.如果節(jié)點si被找到，則把x2中從si到d的這段路徑與x1中從si到d的這段路徑交換；如果沒有找到相同的節(jié)點si，則一直重復(fù)該過程，直到找到為止.經(jīng)過上述2個操作之后，x1，x2和x3就變成3條新的路徑，變異操作完成.當(dāng)所有的路徑不等長時，變異策略同樣適用.

3) 交叉策略.對于交叉策略，以概率CR從種群中選擇2個個體x1和x2，在x1和x2中隨機地選擇2個節(jié)點si和sj作為交叉的起始端點.然后，交換從節(jié)點si和節(jié)點sj之間的路徑.如果在x1和x2中沒有發(fā)現(xiàn)相同的節(jié)點si和sj，則選擇過程就一直持續(xù)，直到發(fā)現(xiàn)為止.

4) 選擇策略.采用約束處理技術(shù)計算父代和子代個體的目標(biāo)函數(shù)值.當(dāng)子代個體支配父代個體，則用子代個體替換父代個體；如果父代個體支配子代個體，則丟棄子代個體；如果父代個體與子代個體之間是非支配的關(guān)系，則父代個體和子代個體同時存檔.

Algorithm1:PseudocodeofMOR-DEalgorithm

搜索網(wǎng)絡(luò)模型G中從源節(jié)點s到目標(biāo)節(jié)點d的路徑集xi(1≤i≤NP);

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

計算種群P0的目標(biāo)函數(shù)適應(yīng)值和約束違反程度;

t=0;∥t表示代數(shù).

repeat

t=t+1;

昨天在魯鎮(zhèn)沒看到“祝?！眱x式的表演，今天就打算到紹興市魯迅故里再去看看。加上魯迅故里的“祝?！眱x式媒體多有報道，所以我今天就更想一睹究竟了。天公作美，久違的太陽出來了。雖然氣溫還低，但陽光讓游客都興致盎然。魯迅故里人山人海，散客、旅游團等操著天南地北不同口音來到了這個江南古鎮(zhèn)的旅游景區(qū)，想一睹這位大文豪生活過的地方。我問了幾個工作人員，才終于找到“祝福”儀式的表演地——魯迅祖居。“祝?！眱x式在德壽堂舉行。初一到初五，每天上下午各兩場，每場持續(xù)15分鐘。

Pt=Pt-1;

for種群Pt中的每一個個體do

運用變異策略求出變異向量;

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

運用選擇策略求出子代;

end

Pi=Pt+1;

計算種群Pt的目標(biāo)函數(shù)適應(yīng)值和約束違反程度;

采用非支配排序和擁擠距離排序技術(shù)從種群Pt中選擇NP個個體組成新的種群Pt;

untilt>Gmax;∥Gmax表示最大的代數(shù).

輸出:種群Pt.

原始差分進化算法的時間復(fù)雜度為O(Gmax·NP·n).其中，Gmax為最大的代數(shù).非支配排序的時間復(fù)雜為O(k·NP2).其中，k為目標(biāo)數(shù).文中，k=2.

由于擁擠距離排序的時間復(fù)雜度O(k·NP·logNP)，故MOR-DE的時間復(fù)雜度為O(Gmax(NP·n+2·NP2+NP·logNP))，即O(Gmax·NP2).

3　實驗結(jié)果分析

為了驗證MOR-DE算法的有效性，將MOR-DE算法與SAMP-DSR[7]，QAMR[9]，ACECR[10]算法進行實驗比較.實驗環(huán)境為Matlab2013b仿真平臺，IntelCoreQuadCPU2.83GHz，4.00GB內(nèi)存.采用Waxman′s隨機生產(chǎn)器構(gòu)建1個隨機的移動AdHoc網(wǎng)絡(luò)結(jié)構(gòu)模型.

3.1參數(shù)設(shè)置

參數(shù)設(shè)置如下：1) 網(wǎng)絡(luò)規(guī)模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) 節(jié)點能量E=40min；6) 鏈路最大時延QD=rand(60,80)ms；7) 鏈路最小帶寬QB=rand(100,150)Kbit·s-1.

3.2結(jié)果分析

由于多目標(biāo)算法求解的結(jié)果1個滿足所有目標(biāo)的折中解集，所以MOR-DE算法與單目標(biāo)算法SAMP-DSR,QAMR和ACECR等在比較過程中，選取了MOR-DE算法解集中的邊界結(jié)果與其進行比較.如果MOR-DE算法解集中的邊界結(jié)果都優(yōu)于那些單目標(biāo)算法的解，那么MOR-DE算法的其他解必定更優(yōu)于其他算法.

MOR-DE算法與SAMP-DSR，QAMR，ACECR算法在路由代價和網(wǎng)絡(luò)生生存時間方面的比較結(jié)果，如表1所示.表1中：t為生存時間.

由表1可知：當(dāng)網(wǎng)絡(luò)節(jié)點數(shù)大于40時，MOR-DE算法獲得所有更優(yōu)的解；當(dāng)網(wǎng)絡(luò)節(jié)點數(shù)小于30時，MOR-DE獲得與QAMR和ACECR算法非支配的解.

表1　算法獲取的最優(yōu)解比較

表2　Friedman測試結(jié)果

對MOR-DE，SAMP-DSR，QAMR，ACECR等4種算法進行Friedman測試及Wilcoxon符號秩檢驗測試[14]，測試結(jié)果如表2，3所示.

由表2可知：無論是對于路由代價目標(biāo)，還是網(wǎng)絡(luò)生存時間目標(biāo)，MOR-DE的排名都處于第一的位置.

由表3可知：MOR-DE獲得的R+值明顯比R-值要大， 這說明MOR-DE算法明顯優(yōu)于SAMP-DSR，QAMR和ACECR算法.

表3　Wicoxon符號秩檢驗測試結(jié)果

為了驗證算法的收斂性，對4種算法的收斂性進行測試，其收斂圖(網(wǎng)絡(luò)節(jié)點為40)，如圖1所示.圖1中：n1為代數(shù).由圖1可知：MOR-DE算法的收斂速度是最快的，說明MOR-DE算法在收斂性方面明顯優(yōu)于其他3種算法.

4種算法的包傳遞率(η)，如圖2所示.由圖2可知：當(dāng)網(wǎng)絡(luò)節(jié)點數(shù)(n2)較小時，4種算法的包傳遞率相差不明顯，但隨著網(wǎng)絡(luò)節(jié)點數(shù)的慢慢增大，MOR-DE算法的優(yōu)勢越加明顯.

(a) 路由代價 (b) 網(wǎng)絡(luò)生存時間　　　　　　　　　　　　　　　　　　　　　　　　　　　圖1　4種算法的收斂圖　　　　　　　　　　　　　　圖2　4種算法的包傳遞率　　　Fig.1　Convergence graph of four algorithms　　　　　　　　　Fig.2　Packet transmission ratio　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　of four algorithms

4　結(jié)束語

提出一種基于多目標(biāo)差分進化算法的移動Ad Hoc網(wǎng)絡(luò)節(jié)能路由算法MOR-DE，修改了差分進化算法的變異、交叉和選擇策略，使算法能夠適應(yīng)問題模型.與SAMP-DSR,QAMR,ACECR算法進行比較，MOR-DE算法在路由代價和網(wǎng)絡(luò)生存時間方面取得一個較好的平衡，且具有較高的包傳遞率.

[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]周少瓊,徐祎,姜麗,等.蟻群優(yōu)化算法在Ad Hoc網(wǎng)絡(luò)路由中的應(yīng)用[J].計算機應(yīng)用,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 路由協(xié)議優(yōu)化[J].小型微型計算機系統(tǒng),2012,33(1):24-27.

[12]朱曉建,沈軍.基于粒子群優(yōu)化的Ad Hoc 網(wǎng)絡(luò)最小能耗多播路由算法[J].通信學(xué)報,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.

(責(zé)任編輯： 錢筠 英文審校： 吳逢鐵)

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-)，男，副教授，博士，主要從事網(wǎng)絡(luò)與并行分布計算、智能優(yōu)化處理的研究.E-mail:weiwh@dgut.edu.cn.

國家自然科學(xué)基金資助項目(61103037, 61300198); 廣東省自然科學(xué)基金資助項目(S2013010011858); 廣東省高?？萍紕?chuàng)新項目(2013KJCX0178)

TP 393

A

1000-5013(2016)05-0654-05