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

魏文紅， 秦勇

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

?

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

魏文紅， 秦勇

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

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

多目標(biāo)； 差分進(jìn)化； 移動(dòng)Ad Hoc； 路由； 生存時(shí)間

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

1　問題模型

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

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

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

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

(1)

(2)

(3)

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

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

(4)

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

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

(5)

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

2　MOR-DE算法

2.1路徑編碼

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

2.2算法描述

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

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

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

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

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

Algorithm1:PseudocodeofMOR-DEalgorithm

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

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

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

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

repeat

t=t+1;

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

Pt=Pt-1;

for種群Pt中的每一個(gè)個(gè)體do

運(yùn)用變異策略求出變異向量;

運(yùn)用交叉策略求出交叉向量;

運(yùn)用選擇策略求出子代;

end

Pi=Pt+1;

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

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

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

輸出:種群Pt.

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

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

3　實(shí)驗(yàn)結(jié)果分析

為了驗(yàn)證MOR-DE算法的有效性，將MOR-DE算法與SAMP-DSR[7]，QAMR[9]，ACECR[10]算法進(jìn)行實(shí)驗(yàn)比較.實(shí)驗(yàn)環(huán)境為Matlab2013b仿真平臺(tái)，IntelCoreQuadCPU2.83GHz，4.00GB內(nèi)存.采用Waxman′s隨機(jī)生產(chǎn)器構(gòu)建1個(gè)隨機(jī)的移動(dòng)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) 鏈路代價(jià)C=rand(2,10)；3) 鏈路時(shí)延D=2/3×Cms；4) 鏈路帶寬B=rand(50,200)Kbit·s-1；5) 節(jié)點(diǎn)能量E=40min；6) 鏈路最大時(shí)延QD=rand(60,80)ms；7) 鏈路最小帶寬QB=rand(100,150)Kbit·s-1.

3.2結(jié)果分析

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

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

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

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

表2　Friedman測(cè)試結(jié)果

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

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

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

表3　Wicoxon符號(hào)秩檢驗(yàn)測(cè)試結(jié)果

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

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

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

4　結(jié)束語(yǔ)

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

[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].計(jì)算機(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].小型微型計(jì)算機(jī)系統(tǒng),2012,33(1):24-27.

[12]朱曉建,沈軍.基于粒子群優(yōu)化的Ad Hoc 網(wǎng)絡(luò)最小能耗多播路由算法[J].通信學(xué)報(bào),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ò)與并行分布計(jì)算、智能優(yōu)化處理的研究.E-mail:weiwh@dgut.edu.cn.

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

TP 393

A

1000-5013(2016)05-0654-05