無(wú)線傳感器網(wǎng)絡(luò)多徑路由機(jī)制研究

陳良文,李敬兆

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

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

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

1 相關(guān)研究

1.1 多徑路由機(jī)制

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

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

多徑路由機(jī)制通過(guò)泛洪的方式定期更新路由信息并獲取備用鏈路，防止網(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) 各個(gè)節(jié)點(diǎn)可以根據(jù)數(shù)據(jù)鏈路的實(shí)際情況(如節(jié)點(diǎn)剩余能量、數(shù)據(jù)重傳率等)調(diào)整路徑，從而保證網(wǎng)絡(luò)的整體能耗均衡性.

1.2 移動(dòng)代理技術(shù)

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

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

1.3 HEED路由算法的描述

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

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

(1)

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

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

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

(2)

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

簇的建立過(guò)程結(jié)束后，簇頭與Sink節(jié)點(diǎn)間以多跳的方式建立數(shù)據(jù)鏈路，各個(gè)簇頭使用TDMA的方式為簇內(nèi)各個(gè)成員節(jié)點(diǎn)分配時(shí)隙，繼而進(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ú)線傳感器網(wǎng)絡(luò)中，有數(shù)量眾多的傳感器節(jié)點(diǎn)分布在監(jiān)測(cè)區(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ù)鏈路是對(duì)稱的，即2個(gè)節(jié)點(diǎn)間進(jìn)行數(shù)據(jù)通信采用相同的傳輸功率;

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

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

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

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

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

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

(3)

2) 無(wú)線傳感器節(jié)點(diǎn)接收l(shuí) 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ò)初始化、簇頭選舉及簇的建立過(guò)程基于HEED路由算法，在多徑路由的發(fā)現(xiàn)過(guò)程引入移動(dòng)代理技術(shù).

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

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

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

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

Agent_ID：移動(dòng)代理的唯一標(biāo)識(shí)；

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

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

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

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

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

各個(gè)節(jié)點(diǎn)在處理事件信息時(shí)采用以下規(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)會(huì)逐漸接收到來(lái)自多個(gè)鄰居節(jié)點(diǎn)轉(zhuǎn)發(fā)的事件信息，根據(jù)轉(zhuǎn)發(fā)數(shù)據(jù)的先后順序，向各個(gè)鄰居節(jié)點(diǎn)發(fā)送主路徑增強(qiáng)信息.

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

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

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

2) 移動(dòng)代理數(shù)據(jù)包具有路徑增強(qiáng)和否定增強(qiáng)機(jī)制.如節(jié)點(diǎn)A將移動(dòng)代理包向最優(yōu)鄰居節(jié)點(diǎn)B發(fā)送，但此時(shí)節(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)則將移動(dòng)代理包發(fā)送至次優(yōu)鄰居節(jié)點(diǎn)C，并重復(fù)該過(guò)程，直至移動(dòng)代理包傳遞到源節(jié)點(diǎn)；

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

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

5) 多徑數(shù)據(jù)鏈路建立完成之后，網(wǎng)絡(luò)進(jìn)入穩(wěn)定數(shù)據(jù)通信階段，位于監(jiān)測(cè)區(qū)域內(nèi)的無(wú)線傳感器節(jié)點(diǎn)將采集到的環(huán)境信息高速傳遞至Sink節(jié)點(diǎn)，同時(shí)，在備用數(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í)間、數(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ò)生存時(shí)間方面，MAHEED算法由于采用備用數(shù)據(jù)鏈路機(jī)制，當(dāng)主要數(shù)據(jù)鏈路發(fā)生變化時(shí)，立即啟用最優(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)越來(lái)越多，如果網(wǎng)絡(luò)依舊保持較高的自適應(yīng)性，意味著網(wǎng)絡(luò)抗毀性越強(qiáng)、可靠性越高.圖10所示為HEED路由算法與MAHEED算法在網(wǎng)絡(luò)自適應(yīng)率與節(jié)點(diǎn)失效率的關(guān)系.

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

4 結(jié)語(yǔ)

本文基于典型分簇式多路徑路由協(xié)議HEED及移動(dòng)代理技術(shù)(mobile agent)針對(duì)無(wú)線傳感器網(wǎng)絡(luò)在實(shí)際應(yīng)用中對(duì)數(shù)據(jù)鏈路高可靠性的要求，設(shè)計(jì)了一種基于移動(dòng)代理和備用數(shù)據(jù)鏈路的多徑路由機(jī)制MAHEED，通過(guò)移動(dòng)代理在網(wǎng)路中按照一定規(guī)則進(jìn)行移動(dòng)，收集網(wǎng)絡(luò)節(jié)點(diǎn)信息并建立主要數(shù)據(jù)鏈路和備用數(shù)據(jù)鏈路，進(jìn)而確定備用數(shù)據(jù)鏈路的優(yōu)先級(jí)，一旦網(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í)間.本文設(shè)計(jì)的多徑路由機(jī)制在網(wǎng)絡(luò)數(shù)據(jù)鏈路可靠性要求較高的應(yīng)用中具有較強(qiáng)的實(shí)用性，但是，網(wǎng)絡(luò)中節(jié)點(diǎn)間傳輸移動(dòng)代理包會(huì)增加額外開(kāi)銷，如何確保移動(dòng)代理包數(shù)據(jù)量最小以及選舉周期的最佳時(shí)間是下一步研究的方向.

參考文獻(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.