基于移動Agent的能量平衡螺旋形路由算法*

楊鄭龍, 張 勝, 吳 卉

(南昌航空大學 信息工程學院，江西 南昌 330063)

基于移動Agent的能量平衡螺旋形路由算法*

楊鄭龍, 張 勝, 吳 卉

(南昌航空大學 信息工程學院，江西 南昌 330063)

針對節點均勻分布的無線傳感器網絡，提出一種基于移動Agent(MA)的能量平衡螺旋形路由(EBSRMA)算法。網絡首先以定向擴散方式建立全網最小跳數梯度環。然后MA從最外環開始，以最短延時策略和優先訪問外環策略為遷移原則，并通過訪鄰、標軌和找源3種方法完成網絡的螺旋形路由。最后MA將遷移過程中收集的全網數據帶回給Sink節點。仿真表明：EBSRMA可以有效平衡網絡能量、延長網絡壽命以及提高數據收集率。與定向擴散(DD)路由算法相比，該路由算法節能效果顯著。

無線傳感器網絡；移動Agent；螺旋路由；能量平衡

0 引 言

無線傳感器網絡(WSNs)計算模式主要分為C/S模式和移動Agent(MA)模式。C/S模式下，網絡能量消耗不均勻，越靠近Sink節點，越容易出現網絡空洞和孤島節點[1]。網絡數據不經過融合處理將產生大量的冗余[2]。而MA模式可以提高網絡的各項性能，運用MA進行數據融合可以減少冗余數據[3]，將MA用于網絡路由可以提高鏈路質量，有效避免數據傳輸沖突和數據重發[4,5]。利用MA的自主性和智能性可以適應網絡動態變化，平衡網絡能量，延長網絡壽命[6]。

目前有許多文獻對MA進行研究和應用。文獻[7]從網絡能耗、時延等方面對MA模式和C/S模式進行比較分析。文獻[8]提出一種蟻群優化多Agent路由算法，采用偽隨機概率選擇MA下一跳節點，并引入一個 值來引導MA尋找目標節點，最后在MA結束任務的同時完成最優最差路徑的全局更新。文獻[9]提出一種基于能量平衡定向擴散(directed diffusion,DD)的MA路由算法，該算法以DD方式建立多向最優傳輸梯度，然后源節點上探測包(exploratory packet,ED)在建立好的梯度中按正比選擇策略構造概率函數Pv(i)，并用輪盤賭法選擇下一跳節點,從而建立源節點之間的路由。此路由算法可以很好延長網絡壽命，但MA只能采集局部區域的節點數據。

本文提出一種基于MA的能量平衡螺旋形路由(EBSRMA)算法，該算法使得MA以螺旋形路由單向不重復的遍歷到網絡所有節點，達到平衡網絡能量、延長網絡壽命的目的。EBSRMA算法主要為查詢全網數據而設計，對于事件網絡，其同樣適用。

1 EBSRMA算法

1.1 網絡模型

網絡由相同型號的節點構成，Sink節點位于網絡中心，成員節點均勻且較密集地分布在Sink節點周圍。網絡中每個節點的通信范圍相同且節點上傳感器感知范圍小于節點通信范圍，所以,一個節點的通信范圍內可能覆蓋多個節點。

1.2 EBSRMA算法思想

Sink節點首先發送網絡探測包，成員節點通過比較包中跳數，記錄最小跳數包的跳數和父節點ID號到本地，建立起自己與Sink節點最少跳數鏈路，并形成最小跳數梯度環。然后Sink節點向最外層環路派發MA。MA由外環到內環，以螺旋形路由逐環巡游并收集節點數據。最后MA將數據帶回給Sink節點。

1.3 EBSRMA算法描述

EBSRMA算法主要包括四部分：建立最小跳數梯度環；Sink節點派發MA；MA在梯度環內遷移與網際巡游；事件網絡。

1.3.1 建立最小跳數梯度環

此過程需要4步進行：

1)Sink節點初始化探測包

網絡探測包包含一個跳數字節HC(hop count)和一個父節點ID字節PNID(parent node ID)，HC初始化值為1,PNID初始化值為Sink節點ID號。

2)Sink節點廣播探測包

Sink節點向周圍廣播探測包:節點A,B,C,D和E都將收到探測包,它們分別將探測包中HC值和PNID值記錄到自身本地LHC(local hop count)和LPNID(local parent node ID)值中，然后將HC值做加1處理，并將自身的ID號寫入PNID。如圖1中,此時節點A本地LHC值為1，LPNID值為Sink節點ID號，而更新的探測包中HC值為2，PNID值為節點A的ID號。節點B,C,D和E情況類似，形成圖1中區域Ⅰ的一跳梯度環。

3)最小跳數選擇

一跳梯度環內的節點向周圍繼續廣播新的探測包，收到探測包的節點進行步驟(2)中的同樣動作，將形成圖1中區域Ⅱ的二跳梯度環。

此過程中會有2個特殊情況：a.同梯度環內節點相互通信;b.一個二跳環內節點收到多個一跳環內的節點探測包。對于第一種情況，設置節點跳數比較機制，本地LHC值和探測包HC值進行比較，如果HC大于LHC，則丟棄探測包；如果HC小于或等于LHC則更新節點本地信息。對于第二種情況，則按照先到先得原則，節點記錄第一個收到的探測包信息，后到的探測包由于具有更長的延時而被丟棄。

4)建立最小跳數梯度環

二跳梯度環內的節點繼續廣播再次更新的探測包，并形成圖1中的三跳梯度環，最終建立起網絡環狀梯度。圖1所示為建立起的最小跳數環狀網絡。

圖1 最小跳數環狀網絡Fig 1 Minimum hop annular network

1.3.2 Sink節點派發MA

Sink節點通過1.3.1建立的最小跳數鏈路，隨機選擇一條鏈路向網絡派發MA，MA根據節點的LHC值尋找最外層環路(即MA將被派發到圖1的區域Ⅲ)。MA的結構如圖2所示。其中：

圖2 MA的結構Fig 2 Structure of MA

Time Stamp ：時間戳(TS),記錄MA在節點間的傳輸延時。

Graded Ring ：梯度環值(GR),記錄MA工作所在的環路梯度值,防止MA在本環工作完成前遷移到其他梯度環內。

Initial Work Node ：起始工作節點(IWN),當MA再次發現IWN，MA將向上一層環路遷移。

Information Correlation ：信息相關度(IC),MA根據IC值判斷事件節點。

Neighbor Nodes Information ：鄰居節點信息(NNI),MA動態記錄其所在節點的當前鄰居信息。

Event Routing Table ：事件路由表(ERT),記錄MA遷移到事件區域的路由信息。

Process Code ：MA自身代碼、遷移策略代碼和融合算法代碼(PC)。

1.3.3 MA在梯度環內遷移與網際巡游

MA在梯度環內遷移與網際巡游主要遵循2個策略：最短延時策略；優先訪問外環策略。

1)最短延時策略

MA向周圍廣播查詢包，并從返回的查詢包時間戳(TS)解析出鄰居節點的延時信息，然后選擇時延最短的節點為下一跳節點。最短延時策略為EBSRMA算法的最基本的遷移策略。

2)優先訪問外環策略

對于網絡的邊緣節點，多數情況下無法組成一個完整的梯度環路。所以，MA在遷移過程中如果發現更外層的環路，其將遷移到外層環收集信息，然后原路返回(即圖3中MA的遷移路徑為A-B-C-D-E-D-C-B-F-G)。圖3中，MA在E節點處查詢不到滿足下一跳的節點，其將返回初始工作節點C，然后從C節點跳向內層環路的B節點，繼而接下來的工作。圖3為優先訪問外環策略遷移路徑。

圖3 優先訪問外環策略遷移路徑Fig 3 Migration path of priority visiting outer ring strategy

MA有序地遍歷網絡所有的節點主要使用3種方法：訪鄰；標軌；找源。

1)訪鄰

MA在遷移過程中總是依據最短延時策略選擇下一跳節點，但是會出現圖4中的漏跳現象(即MA從A-B-C-E而漏跳D節點)。所以,MA會查詢返回的查詢包中鄰居節點信息，當MA訪問完所有鄰居節點，再向周圍廣播下一個查詢包(即MA從B跳向D，在D上廣播查詢包后跳向C和E)。圖4為訪鄰遷移路徑。

圖4 訪鄰遷移路徑Fig 4 Migration path of visiting neighbors

2)標軌

MA在遷移過程中，會在駐留過的節點上留下標志位，避免MA的回跳和回轉現象。如圖5中當MA在B節點時，它不回跳A節點而跳向D節點，然后從D跳向C節點而不是A節點，最后從C節點跳向E節點而不是B節點。圖5為MA回傳和回轉路徑。

圖5 MA回傳和回轉路徑Fig 5 Return and rotation path of MA

3)找源

MA在梯度環內遷移過程中，會判斷下一跳節點是否為起始工作節點，當下一跳節點為起始工作節點時，MA將向上一級梯度環遷移。當MA找不到起始工作節點時，將進行反向路由回到起始工作節點，然后遷移到上一級梯度環。MA在環內遷移路徑和網際巡游路徑如圖6所示。

圖6 MA環內遷移與網際巡游路徑Fig 6 Loop transfer and network parade of MA

1.3.4 事件網絡

當網絡中有事件發生，事件節點會根據1.3.1中建立的最小跳數鏈路將請求包發給Sink節點。Sink節點將向最先到達Sink節點的請求包所在的事件節點派發MA，MA遵循1.3.3中的遷移策略，但在此過程中，MA會將事件節點數據和周圍節點的數據做差值計算，若差值小于信息相關度值(IC)，則認為此節點為事件節點，MA將遷移到此節點并融合數據。若差值大于信息相關度值,MA不對其做處理，然后尋找下一個事件節點。MA在事件網絡中的遷移路徑如圖7所示。

圖7 MA在事件網絡中的遷移路徑Fig 7 Migration path of MA in event network

2 仿真實驗與結果分析

使用Matlab對EBSRMA和DD路由算法進行仿真，假設網絡由1～100個節點組成，Sink節點位于網絡中心，節點均勻且較密集的分布在網絡中。在此規定一次網絡任務的定義為Sink節點接收網絡中所有節點的數據。

1)網絡跳數比較

設定每個節點上有一個數據包，一次網絡任務下，隨著節點個數的增加，2種算法跳數結果如圖8所示。從圖中可以看出：隨著節點的增加DD路由算法網絡跳數快速增加，而EBSRMA算法增加較為緩慢。其主要原因在于DD路由算法容易造成數據沖突和數據重發，越靠近Sink節點，上述現象越嚴重。而EBSRMA算法采用螺旋形路由，在MA遷移過程中，MA對每個節點只訪問一次，所以，EBSRMA算法的網絡跳數增加緩慢。

圖8 節點數變化時的跳數Fig 8 Hop count when node numbers change

設定網絡中有100個節點，每個節點具有相同量的數據包，MA的數據融合比例為0.9。隨著節點上數據包的增加，2種算法網絡跳數結果如圖9所示。從圖中可以看出：隨著每個節點的數據包個數增加，DD路由算法網絡跳數快速增加，而EBSRMA算法網絡總跳數增加十分緩慢，體現了EBSRMA的優越性。

圖9 數據包數變化時的跳數Fig 9 Hop count when data packets change

2)網絡能耗比較

消耗網絡能量的主要原因是節點間的通信能耗。設定節點接收能耗57.6 mW,發送能耗90.94 mW。2種算法能耗如圖10所示。

圖10 2種路由算法能耗Fig 10 Energy consumption of two kinds of routing algorithm

在完成一次網絡任務的情況下，當網絡規模增大時，DD路由算法耗能將快速增加，而EBSRMA算法能耗增加緩慢，其主要原因是MA在網際以螺旋形路線巡游并融合數據，大量減少了各節點的通信能耗，降低了網絡整體能耗。

3)網絡時延比較

網絡延時的計算從Sink節點發送任務到Sink節點接收所有網絡數據為止。設定節點傳輸速率為250 kbps,MA發送的查詢包大小為10 bytes，MA大小為100 bytes，數據大小為500 bytes，節點工作頻率為1 MHz,則節點發送查詢包平均用時為0.000 3 s，節點傳送數據平均用時為0.032 s，節點傳送MA平均用時為0.019 s，MA工作平均用時為0.001 s。2種路由算法的網絡延時結果如圖11所示。

圖11 2種路由算法延時Fig 11 Time delay of two kinds of routing algorithm

從圖中11可以看出:隨著網絡節點量的增加，DD路由算法延時越來越長于EBSRMA，造成DD路由算法延時的主要原因在于數據重傳延時。而EBSRMA算法則克服了這一點，避免了數據重傳造成的延時，對于EBSRMA算法延時的原因在于MA要訪問全網節點后才返回Sink節點。

4)網絡節點能量最大值和最小值之差

設定網絡成員節點隨機分配初始能量位于[9,10]焦耳間的值，節點工作一次消耗0.05 J能量，隨著網絡任務的增加，網絡節點能量最大和最小差值結果如圖12所示。

圖12 成員節點能量差值Fig 12 Energy difference of member nodes

從圖12可以看出:隨著網絡任務數的增加，網絡節點的能量都將減少，但網絡中節點最大最小能量值之差保持不變，說明了此算法具有非常好的能量平衡性。

5)信息收集率比較

信息收集率定義為：網絡數據量/完成一次網絡任務的網絡跳數。設定網絡中每個節點都有一個數據包，則2種算法信息收集率比較結果如圖13所示。

圖13 2種算法信息收集率Fig 13 Information collection rate of two kinds of algorithm

從圖13可以看出:EBSRMA算法的信息收集率在50 %左右，其原因在于MA在遷移過程中每個節點都返回給MA一次查詢信息，造成多余的信息跳數。在EBSRMA下，平均每個節點通信2次，Sink節點就可收到一個數據包。而DD路由算法信息收集率較低，當網絡中有100個節點時，平均每個節點通信10次，Sink才能收到一個數據包。

3 結束語

EBSRMA算法良好的能量平衡效果可有效地延長網絡使用壽命。由于MA要對網絡中每個節點都進行訪問，所以,EBSRMA算法在減少網絡延時方面并不突出，但其網絡延時還是要遠小于DD路由算法。EBSRMA算法以較少的能量代價和延時來收集整個網絡的數據。

[1] 吳小兵，陳貴海．無線傳感器網絡中節點非均勻分布的能量空洞問題[J]．計算機學報，2008，31(2):253-261．

[2] 楊俊剛,史浩山,楊武.無線傳感器網絡CSMA博弈優化算法研究[J].傳感技術學報,2009,30(12):1774-1778.

[3] Qi H,Iyengar S S,Chakrabarty K.Multi-resolution data integration using mobile agents in distributed sensor networks[J].IEEE Trans on Systems Man Cybernet,Part C,2001,31(3):383-391.

[4] 梁振球,陳 雅.無線傳感器網絡移動代理路由算法的仿真研究[J].計算機仿真,2011,28(2):167-170.

[5] 楊少軍,史浩山,黃 睿.線傳感器網絡移動Agent路由算法的研究與仿真[J].系統仿真學報,2007,19(2):388-395.

[6] 胡 寧,張德運.無線傳感器網絡的能量平衡路由[J].西安交通大學學報,2006,40(6):676-671.

[7] 魏永紅,李科杰.移動Agent 計算模式的無線傳感器網絡性能[J].計算機應用研究,2011,28(4):1490-1494.

[8] 王潛平，來梁麗，王 珂，等.蟻群優化的多Agent路由算法及其應用[J].解放軍理工大學學報,2012,13(3):271-275.

[9] 姜 飛，史浩山，徐志燕,等.WSNs中基于能量均衡定向擴散的移動Agent路由算法[J].西北工業大學學報,2010,28(6):898-905.

Energy balanced spiral routing algorithm based on mobile agent*

YANG Zheng-Long, ZHANG Sheng, WU Hui

(School of Information technology，NCHU，Nanchang 330063)

For uniform distributed wireless sensor networks(WSNs),put forward an energy-balanced spiral routing algorithm based on mobile agent(EBSRMA).At first,using directed diffusion method,the minimum hop gradient ring is established.Then,MA works from the outset loop and migrates based on shortest time delay strategy and priority visiting the outer loop strategy,and accomplishes the spiral routing by the way of visiting neighbor,marking trace and finding source.At last,MA will take the whole network data which are collected during migrating back to sink node.Simulation results shows that,by EBSRMA,the energy of network can be balanced effectively,the life of the network can be prolonged and the rate of data collection can be improved.Compared with DD routing algorithm,energy saving effect of EBSRMA is obvious.

wireless sensor networks(WSNs); mobile agent(MA); spiral routing; energy-balanced

10.13873/J.1000—9787(2014)10—0128—05

2014—02—23

國家自然科學基金資助項目(61162002)；江西省教育廳科技項目(GJJ12428)；南昌航空大學2012年研究生創新基金資助項目(YC2012028)

TP 393

A

1000—9787(2014)10—0128—05

楊鄭龍(1988-)，男，河北臨城人，碩士研究生，研究方向為無線傳感器網絡。