無線傳感器網絡多徑路由機制研究

陳良文,李敬兆

(安徽理工大學 計算機科學與工程學院, 安徽 淮南 232001)

無線傳感器網絡路由協議的設計目的是以合理的方式組織無線傳感器節點形成可靠鏈路，并將數據包從源節點正確發送至目標節點，同時提高網絡綜合性能、降低網絡能耗，延長網絡生存時間.無線傳感器節點由于其低成本及微型化要求，決定了其在計算、數據存儲、能源供應和數據傳輸等方面的性能非常有限.各個傳感器節點需要將采集到的數據傳遞給基站(base station)或數據收集中心節點(data collection center)，數據鏈路的可靠性與網絡的綜合性能密切相關.國內外針對提高傳感器網絡數據鏈路可靠性的研究主要分為數據重傳、糾錯碼機制和多路徑方法3個方面[1].

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

1 相關研究

1.1 多徑路由機制

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

多路徑算法通過在源節點與目標節點之間建立多條數據鏈路，有效地提高了數據傳輸的可靠性和容錯性，對于網絡的負載均衡性也有較好的保障.圖2所示為多徑路由的2種形式.

多徑路由機制通過泛洪的方式定期更新路由信息并獲取備用鏈路，防止網絡中因節點失效導致數據鏈路退化，該機制能夠很好地實現網絡負載平衡并提高數據傳輸的可靠性.多徑路由機制具有以下特點[4-5]：

1) 根據不同的應用需求可以提供不同的數據鏈路；

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

3) 各個節點可以根據數據鏈路的實際情況(如節點剩余能量、數據重傳率等)調整路徑，從而保證網絡的整體能耗均衡性.

1.2 移動代理技術

移動代理(mobile agent)[6]是一種能在異構網絡中與其他代理或資源交互的程序，在無線傳感器網絡中，能夠在節點間自主移動并執行特定任務.圖3所示為移動代理的系統模型.

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

1.3 HEED路由算法的描述

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

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

(1)

其中，Cprob為系統設定的初始簇頭比例(通常為5%)，與最終簇頭比例無關；Eresidual表示當前節點的剩余能量；Emax表示當前網絡節點最大參考能量值(即節點的初始能量值).

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

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

(2)

其中，minPi為節點vi與簇頭間數據傳輸的最低功耗；M為簇頭通信范圍內節點的個數.

簇的建立過程結束后，簇頭與Sink節點間以多跳的方式建立數據鏈路，各個簇頭使用TDMA的方式為簇內各個成員節點分配時隙，繼而進入穩定的數據傳輸階段.

圖5所示為基于HEED路由算法的網絡拓撲結構.

2 MAHEED算法的設計與實現

2.1 網絡模型及能量模型[2]

在無線傳感器網絡中，有數量眾多的傳感器節點分布在監測區域，本文采用的網絡模型與HEED路由算法的網絡模型基本一致：

1) 網絡中所有的節點都是同構的；

2) 網絡節點間的數據鏈路是對稱的，即2個節點間進行數據通信采用相同的傳輸功率;

3) 網絡中的節點可以承擔多種任務，這就意味著網絡節點的能耗不完全一致；

4) 各個傳感器節點無法感知自己的地理位置；

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

6) 傳感器節點具有多級傳輸功率，且各個節點能夠自主調節發送功率.

在無線傳感器網絡中，采用的能量模型[4]如下：

1) 無線傳感器節點發送l bit數據消耗的能量:

(3)

2) 無線傳感器節點接收l bit數據消耗的能量

ERX(l,d)=lEelec.

(4)

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

2.2 MAHEED算法設計與實現

本文設計的MAHEED路由算法中的網絡初始化、簇頭選舉及簇的建立過程基于HEED路由算法，在多徑路由的發現過程引入移動代理技術.

移動代理能夠在節點間自由移動，通過收集周邊節點信息，使得節點對局部鏈路信息的認知得以提升，從而建立優化的多徑路由及備用鏈路.

MAHEED路由算法創建多徑路由的步驟如下：

1) 根據HEED路由算法選舉簇頭節點，網絡中其他非簇頭節點根據AMRP值選擇加入合適的簇；

2) 創建移動代理數據包，并將其在網絡節點間傳遞.移動代理數據包(mobile agent packet,MAP)的格式如圖6所示.

Agent_ID：移動代理的唯一標識；

Path_info：區域節點泛洪事件信息得到的路由表；

Path_flag：鏈路發生改變的標識；

Path_hops：數據鏈路的跳數；

Points_sum：數據鏈路的整體能耗.

3) 建立主要數據鏈路.各個源節點以低速率在網絡中試探性泛洪事件信息，通過接收鄰居節點發送的信息建立傳輸梯度[8].當事件信息從各個源節點發送至Sink節點時，就會建立整個網絡的傳輸梯度.

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

按照以上規則處理事件信息能夠防止網絡中出現信息環路(loop).

Sink節點會逐漸接收到來自多個鄰居節點轉發的事件信息，根據轉發數據的先后順序，向各個鄰居節點發送主路徑增強信息.

4) 建立備用數據鏈路.在主要數據鏈路建立的過程中，Sink節點根據鄰居節點轉發事件信息的先后順序確定各個鄰居節點的優先級，Sink節點根據優先級由高向低的順序向鄰居節點發送移動代理包MAP，繼而建立備用數據鏈路.

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

1) Sink節點根據鄰居節點的優先級依次發送移動代理包MAP，各個移動代理包采用Agent_ID唯一標識;

2) 移動代理數據包具有路徑增強和否定增強機制.如節點A將移動代理包向最優鄰居節點B發送，但此時節點B已經位于主要數據鏈路，則B節點采用否定增強機制，向A節點發送否定增強信息，A節點則將移動代理包發送至次優鄰居節點C，并重復該過程，直至移動代理包傳遞到源節點；

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

4) 源節點最終會接收到多個移動代理包，根據移動代理包中的數據，能夠得到多條備用數據鏈路，根據數據鏈路跳數最優、能耗最小的規則就能確定備用數據鏈路的優先級；

5) 多徑數據鏈路建立完成之后，網絡進入穩定數據通信階段，位于監測區域內的無線傳感器節點將采集到的環境信息高速傳遞至Sink節點，同時，在備用數據鏈路上進行低速率數據傳輸，保證備用數據鏈路的可用性.一旦主要數據鏈路失效，就選用最優備用鏈路繼續傳輸數據，保證數據傳輸的可靠性.

3 實驗仿真與性能分析

本文采用Matlab軟件將改進型算法MAHEED與HEED路由算法在網絡生存時間、數據鏈路可靠性等方面的性能進行比較，環境參數如表1.

表1 仿真環境參數

圖8為仿真網絡中Sink節點及簇頭節點的分布情況及數據鏈路的權值.

在仿真環境中，將HEED路由算法與MAHEED算法進行比較，在網絡生存時間方面，MAHEED算法由于采用備用數據鏈路機制，當主要數據鏈路發生變化時，立即啟用最優備用數據鏈路，保證了網絡中各節點的能耗均衡性，因此，網絡生命周期提升約70%.圖9為HEED路由算法與MAHEED算法網絡生命周期的比較.

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

通過比較發現，改進型算法MAHEED隨著網絡節點失效率的提高，網絡自適應率較HEED路由算法有較大提升.

4 結語

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

參考文獻:

[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中多路徑路由協議算法的改進研究[J].計算機技術與發展,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.