陳良文,李敬兆

(安徽理工大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院, 安徽 淮南 232001)

無線傳感器網(wǎng)絡(luò)路由協(xié)議的設(shè)計(jì)目的是以合理的方式組織無線傳感器節(jié)點(diǎn)形成可靠鏈路，并將數(shù)據(jù)包從源節(jié)點(diǎn)正確發(fā)送至目標(biāo)節(jié)點(diǎn)，同時提高網(wǎng)絡(luò)綜合性能、降低網(wǎng)絡(luò)能耗，延長網(wǎng)絡(luò)生存時間.無線傳感器節(jié)點(diǎn)由于其低成本及微型化要求，決定了其在計(jì)算、數(shù)據(jù)存儲、能源供應(yīng)和數(shù)據(jù)傳輸?shù)确矫娴男阅芊浅Ｓ邢?各個傳感器節(jié)點(diǎn)需要將采集到的數(shù)據(jù)傳遞給基站(base station)或數(shù)據(jù)收集中心節(jié)點(diǎn)(data collection center)，數(shù)據(jù)鏈路的可靠性與網(wǎng)絡(luò)的綜合性能密切相關(guān).國內(nèi)外針對提高傳感器網(wǎng)絡(luò)數(shù)據(jù)鏈路可靠性的研究主要分為數(shù)據(jù)重傳、糾錯碼機(jī)制和多路徑方法3個方面[1].

本文針對無線傳感器網(wǎng)絡(luò)路由機(jī)制及可靠數(shù)據(jù)鏈路展開研究，在多徑路由算法[2](hybrid energy-efficient distributed clustering approach，HEED)的基礎(chǔ)上，提出一種基于移動代理的多路徑發(fā)現(xiàn)算法 (HEED with mobile agent technology，MAHEED).該算法采用備用鏈路的思想并對其進(jìn)行優(yōu)化，能夠有效提高網(wǎng)絡(luò)的可靠性及生存時間.

1 相關(guān)研究

1.1 多徑路由機(jī)制

無線傳感器路由協(xié)議根據(jù)數(shù)據(jù)傳輸路徑的方式可以分為單徑路由協(xié)議(如DD、Rumor、GBR、Gossiping、LEACH、PEGASIS等)和多徑路由協(xié)議[3](如HEED、Flooding、SPIN、HREEMR等).單徑路由算法相對簡單，傳感器節(jié)點(diǎn)通常直接與基站或中心節(jié)點(diǎn)進(jìn)行數(shù)據(jù)通信，能夠有效節(jié)省存儲空間、減少數(shù)據(jù)通信量，但是，網(wǎng)絡(luò)的能耗均衡性、穩(wěn)定性、可擴(kuò)展性和容錯性差，一旦某些關(guān)鍵性節(jié)點(diǎn)失效，就很容易導(dǎo)致網(wǎng)絡(luò)中出現(xiàn)盲區(qū).圖1所示為單徑路由的2種形式.

多路徑算法通過在源節(jié)點(diǎn)與目標(biāo)節(jié)點(diǎn)之間建立多條數(shù)據(jù)鏈路，有效地提高了數(shù)據(jù)傳輸?shù)目煽啃院腿蒎e性，對于網(wǎng)絡(luò)的負(fù)載均衡性也有較好的保障.圖2所示為多徑路由的2種形式.

多徑路由機(jī)制通過泛洪的方式定期更新路由信息并獲取備用鏈路，防止網(wǎng)絡(luò)中因節(jié)點(diǎn)失效導(dǎo)致數(shù)據(jù)鏈路退化，該機(jī)制能夠很好地實(shí)現(xiàn)網(wǎng)絡(luò)負(fù)載平衡并提高數(shù)據(jù)傳輸?shù)目煽啃?多徑路由機(jī)制具有以下特點(diǎn)[4-5]：

1) 根據(jù)不同的應(yīng)用需求可以提供不同的數(shù)據(jù)鏈路；

2) 為同一種類型的服務(wù)能夠提供多條數(shù)據(jù)鏈路，保證資源利用率及數(shù)據(jù)傳輸質(zhì)量；

3) 各個節(jié)點(diǎn)可以根據(jù)數(shù)據(jù)鏈路的實(shí)際情況(如節(jié)點(diǎn)剩余能量、數(shù)據(jù)重傳率等)調(diào)整路徑，從而保證網(wǎng)絡(luò)的整體能耗均衡性.

1.2 移動代理技術(shù)

移動代理(mobile agent)[6]是一種能在異構(gòu)網(wǎng)絡(luò)中與其他代理或資源交互的程序，在無線傳感器網(wǎng)絡(luò)中，能夠在節(jié)點(diǎn)間自主移動并執(zhí)行特定任務(wù).圖3所示為移動代理的系統(tǒng)模型.

移動代理具有以下特征[7]：①具有智能性、自治性、移動性；②具有在不同主機(jī)或資源執(zhí)行特定任務(wù)的能力；③移動代理能夠保持自身狀態(tài)，且執(zhí)行過成功是可持續(xù)的.其執(zhí)行周期如圖4.

1.3 HEED路由算法的描述

HEED(a hybrid, energy-efficient, distributed clustering approach for ad hoc sensor networks)是Younis等[2]提出的一種混合式的分布式成簇路由算法，作為一種典型的分層式多徑路由算法，不僅具有良好的可擴(kuò)展性和實(shí)用性，同時，對于降低網(wǎng)絡(luò)中節(jié)點(diǎn)能耗及數(shù)據(jù)通信量也能起到良好效果.該算法指出，無線傳感器網(wǎng)絡(luò)的3個基本需求為可擴(kuò)展性、負(fù)載平衡和延長網(wǎng)絡(luò)生命周期.HEED路由算法可以分為簇的建立階段TCP和穩(wěn)定數(shù)據(jù)傳輸TNO2個階段，但必須確保TNO遠(yuǎn)遠(yuǎn)長于TCP.

簇的建立過程又分為網(wǎng)絡(luò)初始化階段和路徑建立階段，經(jīng)多次迭代完成.首先，網(wǎng)絡(luò)初始化階段，根據(jù)公式(1)計(jì)算各個節(jié)點(diǎn)當(dāng)選為簇頭的概率CHprob，并與生成的隨機(jī)數(shù)Random(0,1)比較，確定該節(jié)點(diǎn)是否能當(dāng)選為臨時簇頭[2].

(1)

其中，Cprob為系統(tǒng)設(shè)定的初始簇頭比例(通常為5%)，與最終簇頭比例無關(guān)；Eresidual表示當(dāng)前節(jié)點(diǎn)的剩余能量；Emax表示當(dāng)前網(wǎng)絡(luò)節(jié)點(diǎn)最大參考能量值(即節(jié)點(diǎn)的初始能量值).

然后，在迭代選舉簇頭階段，通過將CHprob加倍并與1比較，直到CHprob的值等于1，迭代過程結(jié)束，簇頭選舉完成.

最后，在普通節(jié)點(diǎn)選擇簇頭階段，各個非簇頭節(jié)點(diǎn)再根據(jù)最小傳輸功耗least_cost(SCH)選擇并加入簇頭.簇內(nèi)成員節(jié)點(diǎn)與簇頭之間的通信通過AMRP (average minimum reach-ability power)[2]進(jìn)行衡量：

(2)

其中，minPi為節(jié)點(diǎn)vi與簇頭間數(shù)據(jù)傳輸?shù)淖畹凸?；M為簇頭通信范圍內(nèi)節(jié)點(diǎn)的個數(shù).

簇的建立過程結(jié)束后，簇頭與Sink節(jié)點(diǎn)間以多跳的方式建立數(shù)據(jù)鏈路，各個簇頭使用TDMA的方式為簇內(nèi)各個成員節(jié)點(diǎn)分配時隙，繼而進(jìn)入穩(wěn)定的數(shù)據(jù)傳輸階段.

圖5所示為基于HEED路由算法的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu).

2 MAHEED算法的設(shè)計(jì)與實(shí)現(xiàn)

2.1 網(wǎng)絡(luò)模型及能量模型[2]

在無線傳感器網(wǎng)絡(luò)中，有數(shù)量眾多的傳感器節(jié)點(diǎn)分布在監(jiān)測區(qū)域，本文采用的網(wǎng)絡(luò)模型與HEED路由算法的網(wǎng)絡(luò)模型基本一致：

1) 網(wǎng)絡(luò)中所有的節(jié)點(diǎn)都是同構(gòu)的；

2) 網(wǎng)絡(luò)節(jié)點(diǎn)間的數(shù)據(jù)鏈路是對稱的，即2個節(jié)點(diǎn)間進(jìn)行數(shù)據(jù)通信采用相同的傳輸功率;

3) 網(wǎng)絡(luò)中的節(jié)點(diǎn)可以承擔(dān)多種任務(wù)，這就意味著網(wǎng)絡(luò)節(jié)點(diǎn)的能耗不完全一致；

4) 各個傳感器節(jié)點(diǎn)無法感知自己的地理位置；

5) 傳感器節(jié)點(diǎn)一旦部署就無法置換，也無法更換電池或其它部件；

6) 傳感器節(jié)點(diǎn)具有多級傳輸功率，且各個節(jié)點(diǎn)能夠自主調(diào)節(jié)發(fā)送功率.

在無線傳感器網(wǎng)絡(luò)中，采用的能量模型[4]如下：

1) 無線傳感器節(jié)點(diǎn)發(fā)送l bit數(shù)據(jù)消耗的能量:

(3)

2) 無線傳感器節(jié)點(diǎn)接收l bit數(shù)據(jù)消耗的能量

ERX(l,d)=lEelec.

(4)

其中，l為數(shù)據(jù)包的大小，d為節(jié)點(diǎn)間的距離，Eelec為節(jié)點(diǎn)收發(fā)數(shù)據(jù)產(chǎn)生的電路損耗，Efs和Emp為功率放大器分別在不同的工作模型下的能耗，d0為傳感器節(jié)點(diǎn)采用自由空間模型與多路衰減模型的臨界距離.

2.2 MAHEED算法設(shè)計(jì)與實(shí)現(xiàn)

本文設(shè)計(jì)的MAHEED路由算法中的網(wǎng)絡(luò)初始化、簇頭選舉及簇的建立過程基于HEED路由算法，在多徑路由的發(fā)現(xiàn)過程引入移動代理技術(shù).

移動代理能夠在節(jié)點(diǎn)間自由移動，通過收集周邊節(jié)點(diǎn)信息，使得節(jié)點(diǎn)對局部鏈路信息的認(rèn)知得以提升，從而建立優(yōu)化的多徑路由及備用鏈路.

MAHEED路由算法創(chuàng)建多徑路由的步驟如下：

1) 根據(jù)HEED路由算法選舉簇頭節(jié)點(diǎn)，網(wǎng)絡(luò)中其他非簇頭節(jié)點(diǎn)根據(jù)AMRP值選擇加入合適的簇；

2) 創(chuàng)建移動代理數(shù)據(jù)包，并將其在網(wǎng)絡(luò)節(jié)點(diǎn)間傳遞.移動代理數(shù)據(jù)包(mobile agent packet,MAP)的格式如圖6所示.

Agent_ID：移動代理的唯一標(biāo)識；

Path_info：區(qū)域節(jié)點(diǎn)泛洪事件信息得到的路由表；

Path_flag：鏈路發(fā)生改變的標(biāo)識；

Path_hops：數(shù)據(jù)鏈路的跳數(shù)；

Points_sum：數(shù)據(jù)鏈路的整體能耗.

3) 建立主要數(shù)據(jù)鏈路.各個源節(jié)點(diǎn)以低速率在網(wǎng)絡(luò)中試探性泛洪事件信息，通過接收鄰居節(jié)點(diǎn)發(fā)送的信息建立傳輸梯度[8].當(dāng)事件信息從各個源節(jié)點(diǎn)發(fā)送至Sink節(jié)點(diǎn)時，就會建立整個網(wǎng)絡(luò)的傳輸梯度.

各個節(jié)點(diǎn)在處理事件信息時采用以下規(guī)則：①若接收到新的事件信息，則將該事件信息轉(zhuǎn)發(fā)到鄰居節(jié)點(diǎn)；②接收到的事件信息與之前轉(zhuǎn)發(fā)的事件信息一致，則只記錄轉(zhuǎn)發(fā)該事件信息的鄰居節(jié)點(diǎn)而不再轉(zhuǎn)發(fā)給鄰居節(jié)點(diǎn).

按照以上規(guī)則處理事件信息能夠防止網(wǎng)絡(luò)中出現(xiàn)信息環(huán)路(loop).

Sink節(jié)點(diǎn)會逐漸接收到來自多個鄰居節(jié)點(diǎn)轉(zhuǎn)發(fā)的事件信息，根據(jù)轉(zhuǎn)發(fā)數(shù)據(jù)的先后順序，向各個鄰居節(jié)點(diǎn)發(fā)送主路徑增強(qiáng)信息.

4) 建立備用數(shù)據(jù)鏈路.在主要數(shù)據(jù)鏈路建立的過程中，Sink節(jié)點(diǎn)根據(jù)鄰居節(jié)點(diǎn)轉(zhuǎn)發(fā)事件信息的先后順序確定各個鄰居節(jié)點(diǎn)的優(yōu)先級，Sink節(jié)點(diǎn)根據(jù)優(yōu)先級由高向低的順序向鄰居節(jié)點(diǎn)發(fā)送移動代理包MAP，繼而建立備用數(shù)據(jù)鏈路.

圖7所示為改進(jìn)型路由算法MAHEED多徑鏈路建立的過程.具體過程如下.

1) Sink節(jié)點(diǎn)根據(jù)鄰居節(jié)點(diǎn)的優(yōu)先級依次發(fā)送移動代理包MAP，各個移動代理包采用Agent_ID唯一標(biāo)識;

2) 移動代理數(shù)據(jù)包具有路徑增強(qiáng)和否定增強(qiáng)機(jī)制.如節(jié)點(diǎn)A將移動代理包向最優(yōu)鄰居節(jié)點(diǎn)B發(fā)送，但此時節(jié)點(diǎn)B已經(jīng)位于主要數(shù)據(jù)鏈路，則B節(jié)點(diǎn)采用否定增強(qiáng)機(jī)制，向A節(jié)點(diǎn)發(fā)送否定增強(qiáng)信息，A節(jié)點(diǎn)則將移動代理包發(fā)送至次優(yōu)鄰居節(jié)點(diǎn)C，并重復(fù)該過程，直至移動代理包傳遞到源節(jié)點(diǎn)；

3) 移動代理包在傳遞的過程中，需將鏈路中的節(jié)點(diǎn)信息存儲在Path_info單元，若節(jié)點(diǎn)已經(jīng)在其他主要數(shù)據(jù)鏈路或備用鏈路中，則通過Path_flag標(biāo)識位進(jìn)行標(biāo)識.Path_hops用于記錄Sink節(jié)點(diǎn)與各個節(jié)點(diǎn)之間的跳數(shù).Points_sum用于記錄路徑的能量消耗；

4) 源節(jié)點(diǎn)最終會接收到多個移動代理包，根據(jù)移動代理包中的數(shù)據(jù)，能夠得到多條備用數(shù)據(jù)鏈路，根據(jù)數(shù)據(jù)鏈路跳數(shù)最優(yōu)、能耗最小的規(guī)則就能確定備用數(shù)據(jù)鏈路的優(yōu)先級；

5) 多徑數(shù)據(jù)鏈路建立完成之后，網(wǎng)絡(luò)進(jìn)入穩(wěn)定數(shù)據(jù)通信階段，位于監(jiān)測區(qū)域內(nèi)的無線傳感器節(jié)點(diǎn)將采集到的環(huán)境信息高速傳遞至Sink節(jié)點(diǎn)，同時，在備用數(shù)據(jù)鏈路上進(jìn)行低速率數(shù)據(jù)傳輸，保證備用數(shù)據(jù)鏈路的可用性.一旦主要數(shù)據(jù)鏈路失效，就選用最優(yōu)備用鏈路繼續(xù)傳輸數(shù)據(jù)，保證數(shù)據(jù)傳輸?shù)目煽啃?

3 實(shí)驗(yàn)仿真與性能分析

本文采用Matlab軟件將改進(jìn)型算法MAHEED與HEED路由算法在網(wǎng)絡(luò)生存時間、數(shù)據(jù)鏈路可靠性等方面的性能進(jìn)行比較，環(huán)境參數(shù)如表1.

表1 仿真環(huán)境參數(shù)

圖8為仿真網(wǎng)絡(luò)中Sink節(jié)點(diǎn)及簇頭節(jié)點(diǎn)的分布情況及數(shù)據(jù)鏈路的權(quán)值.

在仿真環(huán)境中，將HEED路由算法與MAHEED算法進(jìn)行比較，在網(wǎng)絡(luò)生存時間方面，MAHEED算法由于采用備用數(shù)據(jù)鏈路機(jī)制，當(dāng)主要數(shù)據(jù)鏈路發(fā)生變化時，立即啟用最優(yōu)備用數(shù)據(jù)鏈路，保證了網(wǎng)絡(luò)中各節(jié)點(diǎn)的能耗均衡性，因此，網(wǎng)絡(luò)生命周期提升約70%.圖9為HEED路由算法與MAHEED算法網(wǎng)絡(luò)生命周期的比較.

網(wǎng)絡(luò)自適應(yīng)性(networks adaptability)與網(wǎng)絡(luò)整體性能具有較密切的關(guān)系，隨著網(wǎng)絡(luò)中失效的傳感器節(jié)點(diǎn)越來越多，如果網(wǎng)絡(luò)依舊保持較高的自適應(yīng)性，意味著網(wǎng)絡(luò)抗毀性越強(qiáng)、可靠性越高.圖10所示為HEED路由算法與MAHEED算法在網(wǎng)絡(luò)自適應(yīng)率與節(jié)點(diǎn)失效率的關(guān)系.

通過比較發(fā)現(xiàn)，改進(jìn)型算法MAHEED隨著網(wǎng)絡(luò)節(jié)點(diǎn)失效率的提高，網(wǎng)絡(luò)自適應(yīng)率較HEED路由算法有較大提升.

4 結(jié)語

本文基于典型分簇式多路徑路由協(xié)議HEED及移動代理技術(shù)(mobile agent)針對無線傳感器網(wǎng)絡(luò)在實(shí)際應(yīng)用中對數(shù)據(jù)鏈路高可靠性的要求，設(shè)計(jì)了一種基于移動代理和備用數(shù)據(jù)鏈路的多徑路由機(jī)制MAHEED，通過移動代理在網(wǎng)路中按照一定規(guī)則進(jìn)行移動，收集網(wǎng)絡(luò)節(jié)點(diǎn)信息并建立主要數(shù)據(jù)鏈路和備用數(shù)據(jù)鏈路，進(jìn)而確定備用數(shù)據(jù)鏈路的優(yōu)先級，一旦網(wǎng)絡(luò)中的數(shù)據(jù)鏈路發(fā)生變化，隨即啟用最優(yōu)備用數(shù)據(jù)鏈路.仿真實(shí)驗(yàn)顯示，改進(jìn)型路由算法MAHEED較HEED路由算法，有效提高了網(wǎng)絡(luò)自適應(yīng)率、數(shù)據(jù)鏈路可靠性和網(wǎng)絡(luò)生存時間.本文設(shè)計(jì)的多徑路由機(jī)制在網(wǎng)絡(luò)數(shù)據(jù)鏈路可靠性要求較高的應(yīng)用中具有較強(qiáng)的實(shí)用性，但是，網(wǎng)絡(luò)中節(jié)點(diǎn)間傳輸移動代理包會增加額外開銷，如何確保移動代理包數(shù)據(jù)量最小以及選舉周期的最佳時間是下一步研究的方向.

參考文獻(xiàn):

[1] SHIH H C, HO J H, LIAO B Y, et al. Fault node recovery algorithm for a wireless sensor network[J].IEEE SENSORS JOURNAL, 2013,13(7): 2683-2689.

[2] YOUNIS O, FAHMY S. HEED: a hybrid, energy-efficient, distributed clustering approach for ad hoc sensor networks[J].Mobile Computing, IEEE Transactions on, 2004, 3(4): 366-379.

[3] CHEN Yun-xia, ZHAO Qing. On the lifetime of wireless sensor networks[J]. IEEE Communication Letters, 2005, 9(11): 976-978.

[4] HEINZELMAN W B, CHANDRAKASAN A P, BALAKRISHNAN H. An application-specific protocol architecture for wireless microsensor networks[J].Wireless Communications, IEEE Transactions on, 2002, 1(4): 660-670.

[5] 宗平,龔瑜.WSN中多路徑路由協(xié)議算法的改進(jìn)研究[J].計(jì)算機(jī)技術(shù)與發(fā)展,2012,22(8):34-38.

[6] MINAR N, KRAMER K H, MAES P. Cooperating mobile agent for dynamic network routing[J].Software Agent for Future Communications Systems, 2004,3(4):366-378.

[7] MATSUO H, MORI K. Accelerated ants routing in dynamic networks[C]//2nd Int. Conf. on Software Engineering, Artificial Intelligence, Networking and Parallel/Distributed Computing. 2001:333-339.

[8] DORIGO M, CARO G D. The ant colony optimization meta-heuristic[C]//New Ideas in Optimization. London: MoGraw Hill, 1999:11-32.