基于運動預測與動態通信能量調整的移動WSN路由選擇算法*

李 巍，韓九強，鐘德星

(西安交通大學智能網絡與網絡安全教育部重點實驗室電信學院自動化研究所，西安 710049)

無線傳感器網絡［1］(Wireless Sensor Network，WSN)是由多個節點構成的復雜網絡，網絡內部通過多跳近距離無線通信完成節點間數據交換、數據采集、網絡配置管理等各項工作，由于其獨特的工作特點，導致WSN具有通信拓撲復雜、拓撲變換頻繁的特點。WSN應用范圍廣闊，具體應用模式各有差異，但如果按照節點在目標區域內完成初始布置后，節點位置是否發生變化來歸納，則可將其劃分為兩大類:節點固定的靜態WSN與節點可移動的移動WSN。兩種類型的WSN在學術研究上各有側重，難點不同，從網絡通信拓撲復雜度及網絡拓撲動態性角度看移動WSN的研究難度要超過靜態WSN，動態節點運動會引起網絡通信拓撲大幅變化，進而導致網絡通信效率下降、能耗增高，故需要在通信協議方面做出優化以提高網絡性能、延長網絡壽命，而路由協議受網絡動態拓撲變換影響最為明顯，所以移動WSN路由協議成為一個研究的熱點、難點。

由于WSN中節點一般均采用資源受限的電池供電方式進行數據采集、傳輸的工作，所以伴隨著節點失效，網絡不斷發生拓撲變化，所以即使在靜態WSN中，路由協議也需要考慮網絡的動態拓撲特性［2］，為了應對網絡拓撲變換，Perkins［3－4］等人提出了基于路由表選擇的路由協議:AWDS、DFR、DBF、DSDV［3］等，此類基于路由表協議對于網絡拓撲變化反應較慢；而 BSR［5］、AODV、DSR、DYMO 等按需路由協議能夠在有效降低網絡開銷的同時適應網絡動態拓撲變化，但總體來說協議開銷隨網絡拓撲動態變化程度提升而增大；在已建立路由基礎上進行路由建立的協議如IERP、LBR、PLBR等，若無法提供網絡特性的先驗信息時，其在高動態拓撲情況下，協議性能仍舊不理想；基于分層的路由協議如LEACH［6－7］、FSR［8］、DDR［9］等在高動態拓撲情況下性能較為理想，但此類協議性能依賴于協議層次深度的劃分及子編碼尋址，協議參數選擇對性能影響較為明顯；針對高移動WSN提出的利用節點位置信息輔助路由的 TSG［10］、VDCH、GEOTORA［11］等協議在應對高動態拓撲網絡時，如果對路由開銷控制較好的狀態下，網絡整體性能隨動態拓撲提高，性能下降較不明顯。

從網絡性質角度出發，移動WSN與靜態WSN網絡的基本特質相同，但移動WSN中使用的路由協議應根據網絡節點運動情況采取針對網絡高動態拓撲的措施以提高路由成功率；節點運動是其路由協議設計的挑戰，但節點運動信息也是應對這一挑戰最有利的工具，借鑒利用節點位置輔助路由的靜態WSN路由協議思想，本文針對移動WSN高動態拓撲的特性，通過利用節點的運動信息，輔助路由工作，提出基于節點運動估計的路由選擇算法NMEBRP。

1 節點收發功率動態優化模型

WSN中節點能量消耗的最主要部分是由節點無線通信模塊數據收發帶來的，而多節點共享通信介質的WSN中，一般采用的無線信道模型有自由空間模型、雙路徑地面反射模型、陰影模型等［12］，從模型準確度和仿真復雜度角度考慮，本文采用雙路徑地面反射模型作為無線信道模型，在雙路徑地面反射模型中，距離發射節點距離為d處的信號功率Pr(d)用下式進行計算:

其中，Pt為發送信號節點的發射功率；Gt和Gr分別為發送節點和接收節點的天線增益；L(L≥1)是系統的系統損耗；ht和hr分別為發送節點和接收節點的天線高度。

由于無線信號在空間中成距離的高次冪函數衰減，故節點間采取多跳轉發能夠較好的節省無線通信能量，節點需要根據各自位置關系判斷是否針對特定數據包進行轉發。將式(1)中常數合并化簡為:

用有序實數對表示從前一個節點到下一個節點間的無線數據收發，如(1，2)表示從節點1到節點2的通信。節點保證能夠與需要進行通信的目標節點通信的必要條件是在目標節點處的接收功率Pr(d)大于節點能夠監聽到的信號門限Pthreshold，則1、2節點間存在轉發節點需滿足:

且

若節點間均以監聽信號功率門限為信號功率水平下限，則有:

Pthreshold在仿真實驗環境中即為固定參數，則信號能量發送功率需滿足的式(2)即能寫為僅與相關節點間距離有關的不等式:

節點1、2通過計算可以得到存在轉發節點的范圍，其邊界滿足的參數方程如下式:

2 基于節點運動估計的動態路由選擇算法

對于節點大量隨機運動帶來的網絡拓撲變換頻繁的問題，引入輔助信息手段來幫助各層網絡協議進行性能優化是一個直接有效的解決辦法。本文中，基于這一思路，使用節點的位置信息幫助網絡中的獨立節點進行路由選擇，在使用節點位置信息輔助路由協議時，需要注意以下兩個問題:

(1)使用位置信息進行判斷的可信度的方向性。獲取的位置信息僅僅包括其自身的實時位置信息和其鄰居節點的過去某時間段內的位置信息。出于保證網絡通信功能和網絡實際應用效果的根本要求，運動估計獲得網絡通信狀況、拓撲變化改善的可信度應低于網絡狀況惡化的可信度，以降低由于運動估計帶來的網絡性能誤判導致的額外路由協議開銷。

(2)位置信息采用的回溯時間長度。對于節點及其鄰居節點未來時刻的位置估計是建立在已有過去某長度時間段節點位置變化情況的分析的基礎上的，所以回溯的時間段長度非常重要，合適的回溯時間段長度能夠很好的體現相應節點位置變化情況，還可以提高估計的可信度。

2.1 算法描述

對于布置在目標區域的一組無線傳感器網絡節點，將節點構成的集合記為:

節點的工作區域為二維平面S，其面積為L1×L2，節點部署方式為上節中的均勻隨機部署，節點最大通信半徑為Rradio。對于某時刻節點的位置記為:

其中i∈V。

網絡中節點間位置信息的交換是通過將位置信息附加在每個發送或者轉發的數據包末尾，附加的信息有節點本身的位置信息，也有節點自身已經獲得的過去某一時刻目標節點的位置信息。無線傳感器網絡中的數據包的收發從分析的角度看，是在時間域內發生的離散事件，對于在t時刻收到的數據包中得到的節點i的位置信息記為post(i)的話，對于由上一個數據包中得到的節點i的位置信息記為post－1(i)，對于未來節點位置的估計記為 post+1，網絡中的數據包的發送和接受同時都帶有節點發出和收到的時刻信息，所以將收到兩個相鄰的數據包的時間間隔記為:

這一時間間隔ΔT對于收集到的信息的采信度評估有關。

對于節點i，其所有鄰居節點對其位置預測采用如下方式:鄰居節點根據過去某一時間段收到的k個數據包，獲得節點i的k個過去時間點的位置信息記為:

對于某時刻節點的速度記為:

其中l=0，1，…，k。

對于節點的速度的預測值Velot+1(i)根據以下算式計算:

其中 α0+α1+…+αk－1=1。

α0，α1，…，αk－1的計算采用如下方法，其中輔助變量βm為:

其中m=0，1，…，k－1。則有:

在算法中單個節點對鄰居節點進行位置估計的運算所需要的時間復雜度并不高，綜合式(4)～式(6)，位置估計的復雜度基本為O(c*k)其中c為常數。所以對于估計鄰居節點位置信息時，縮小k的取值在降低節點運算復雜度上并不能帶來顯著的效果，因此從這個角度出發降低k值的意義并不大。討論k的合理取值的意義在于如何能夠合理選擇信息回溯時間長度，使得節點的運動估計既能夠及時反映節點變化趨勢，又能夠使估計的結果具有相對的穩定性。

基于節點運動估計的路由選擇算法仿真的主要步驟:(1)在滿足網絡目標區域覆蓋要求的前提下，對于網絡進行初始布置時，節點通信半徑設置需使網絡滿足連通性條件。(2)從網絡運行開始，網絡中的源數據發送節點通過廣播方式尋找網絡中目標節點。(3)目標節點接收到源節點包含其位置信息的路由建立請求數據包后，根據其中的源節點位置信息發送附帶有其位置信息的數據包進行響應。同時節點中其他節點通過發送生存周期TTL=1的廣播包以期建立起各自的鄰居節點表。(4)源節點發送的數據包依據目標節點位置信息進行路由，網絡中的中間轉發節點如有目標節點較新的位置信息可根據其信息對數據包進行修改，使數據包向目標節點位置方向傳送。(5)節點在網絡中一旦建立起鄰居節點列表后，可自行根據本文第二章中的中間節點選擇關系來修改本地路由表和節點無線收發功率，此過程由節點分布自主執行。(6)根據節點運動估計，對于鄰居節點中在未來時間段內可能移動出節點最大無線通信范圍的節點數目進行計算，如果小于節點鄰居數目最小門限值Neighborthre(i)，節點i則通過最大通信距離發送新的TTL=1的廣播數據包建立本地鄰居表。

以上為路由選擇的主要步驟框架，本文提出的路由協議的最大特點就是路由的發現、建立、判斷使用和后期維護都是建立在對與網絡中節點的具體地理位置信息的利用上，所有節點收發數據包時都要進行位置信息的附加以及提取。基于得到的位置信息，需要根據這些信息進行鄰居節點數目判斷以適應MWSN的高拓撲動態性。

3 仿真實驗

本文利用Network Simulator 2(NS2)進行網絡仿真實驗，實驗的主要部分為模擬了在1 200 m×1 200 m的實驗范圍內，節點總數為500的MWSN網絡能量消耗、網絡壽命等問題。實驗的主要參數如下表所示。

表1 仿真參數

為了進行網絡性能分析對比，本文主要采用了兩種用于無線傳感器網絡的較為典型的協議和NMEBRP協議進行對比。其中一種路由協議為Ad hoc On-Demand Distance Vector Routing(AODV，RFC3561)，AODV［13］是一種使用在無線傳感器網絡或者移動無線傳感器網絡中的具有一定代表性和通用性的路由協議。另外一種為Distance Routing Effect Algorithm for Mobility(DREAM)［14］，這是一種利用節點位置信息進行路由決策的路由協議，在由于節點運動導致的高動態拓撲的網絡中具有比較好的性能。

本文研究主要針對移動WSN中節點運動造成路由協議開銷增大、網絡壽命縮短情況下，路由協議的性能改進，節點隨機運動造成的拓撲變化頻繁是造成網絡性能下降的主要原因，故仿真實驗主要考察在不同節點運動幅度下，參考協議與本文提出協議的性能對比。

從圖1中可以看出網絡中隨著節點隨機移動的幅度增加，網絡中節點能量耗盡的過程加快，用90%節點能量耗盡表示的網絡壽命呈下降趨勢，AODV協議在這種情況下應對節點的隨機運動所付出的代價要遠高于其他兩種協議，NMEBRP性能好于DREAM協議，但在節點運動速度較快時，兩種協議性能較為接近，說明兩種協議對于節點運動情況適應能力的上限近似。

圖1 網絡中90%節點能量耗盡出現的時間

網絡中路由協議開銷會消耗一定量的能量，圖2反映了三種協議的通信開銷大小。由于在節點移動速度較快情況下，AODV協議需要發送大量數據包進行路由維護工作，所以導致其單位數據包傳送能耗較高。DREAM協議根據網絡中節點移動速度變化，需要更加頻繁的更新網絡內的節點位置信息，但相對來說通信開銷隨網絡中節點移動速度增大的增長幅度還是可以接受的，但是當網絡中節點處于運動速度較慢的情況時，其開銷仍然較大。NMEBRP協議能夠取得較低的單位數據包功耗的主要原因是，即使節點移動速度較快情況下，節點調整了數據收發的功率，但是網絡中節點在滿足建立路由的前提下，依然進行本地傳送能量優化、路由調整工作，通過本地轉發，使得傳送數據包的平均能耗得以下降。

圖2 網絡中成功傳送單個數據包的平均能耗

圖3中在不同節點運動速度下，AODV協議在節點隨機移動速度取值上限為12 m/s時，數據收發受到明顯影響。但當節點運動速度再進一步增大時，由于節點隨機運動程度劇烈，網絡中節點相對位置變化快，導致部分數據包可以憑借節點的運動能力得到成功傳送的機會，所以收發數據包的比例又有所上升。而DREAM協議對于節點移動的應對要相對穩定，隨著節點運動程度的加劇，性能便相對較緩慢下降，整個過程沒有出現明顯收發比例下降的階段。提出的NMEBRP協議在數據收發比例方面取得較好的效果，主要原因是當節點運動速度增加時，單位時間內根據協議算法，離開節點通信范圍的現有鄰居節點數目會明顯減少，而并不根據節點運動情況估計鄰居節點數目增加的情況，節點在這種情況下會主動調整數據收發功率，能夠增加成功通信的幾率。

圖3 網絡中成功接收的數據包與發送數據包比值

在圖4中，NMEBRP的平均hop大，說明在仿真實驗中，提出的協議能夠按照構想思路，將單跳距離較長的節點間通信，分解為多個節點間較短距離的通信，圖4說明NMEBRP協議延長網絡壽命的主要途徑與協議的初衷一致。圖4也反映NMEBRP在網絡性能方面的提升是需要付出通信跳數增加，網絡延遲增加的代價。

圖4 網絡中成功傳送單個數據包所經過的平均跳數

4 小結

節點隨機運動造成移動WSN比靜態WSN的網絡拓撲變化更加頻繁，網絡內節點間通信效率隨通信路徑增長而明顯降低；由此導致節點在通信路徑修復及重建的過程中消耗了大量能量，從而顯著影響了網絡壽命。本文針對移動WSN的特點，在分析不同節點間存在優化能量轉發節點的限定條件的基礎上，確定了節點間本地通信轉發的觸發范圍，進而提出了一種用于移動WSN的基于節點運動判斷的路由選擇算法NMEBRP，算法中節點依靠通信過程中收集到的臨近節點位置信息，進行完全分布式的基于臨近節點運動預測的動態路由調整。提出的算法計算復雜度較低，適合應用于節點計算能力受限的各種WSN應用。本文在節點運動速度均值不同的多種實驗場景下進行了大量仿真實驗，實驗結果說明相比參考協議，NMEBRP協議傳遞單位數據包的平均能耗較低，且網絡內用于路由修復及重建的數據包比例低，說明提出的算法將更多節點能量用于傳輸應用數據包，提高了移動WSN的能量利用效率，有效延長了移動WSN網絡壽命。

移動WSN的網絡拓撲高動態性特點使得針對其設計的路由層算法能夠明顯改善網絡性能，但從本質上提高此類網絡的應用效果，從通信協議角度考慮，還需要從數據鏈路層至傳輸層均結合節點運動特性進行跨層優化設計，提出完全適用于移動WSN的跨層通信協議。在本文NMEBRP算法的基礎上，作者計劃進行深入研究，希望能夠提出完全針對移動WSN的跨層通信協議。

［1］Yick J，Mukherjee B，Ghosal D.Wireless Sensor Network Survey［J］.Computer Networks，2008，52(12):2292－2330.

［2］李少春，程良倫.一種自適應的混合型無線傳感器網絡拓撲控制算法［J］.傳感技術學報，2010，23(3):428－433.

［3］Perkins C E，Bhagwat P.Highly Dynamic Destination-Sequenced Distance-Vector Routing(DSDV)for Mobile Computers［J］.Computer Communications Review，1994，24(4):234－234.

［4］Chen J，Zhou H，Lee Y Z，et al.AODV-DFR:Improving Ad Hoc Routing Scalability to Mobility and Load［C］//Vancouver，BC，Canada:Institute of Electrical and Electronics Engineers Computer Society，2007.550－553.

［5］Guo S，Yang O.Effects of Backup Routes and Cache Timeout Mechanism on ReliableSourceRoutingin MobileAd-Hoc Networks［C］//Hong Kong，China:Institute of Electrical and Electronics Engineers Computer Society，2005.361－365.

［6］Heinzelman W R，Chandrakasan A，Balakrishnan H.Energy-Efficient Communication Protocol for Wireless Microsensor Networks［C］//Maui，USA:IEEE，2000.223－231.

［7］張震，閆連山，潘煒，等.基于LEACH和PEGASIS的簇頭成鏈可靠路由協議研究［J］.傳感技術學報，2010，23(8):1173－1178.

［8］Guangyu P，Gerla M，Tsu-Wei C.Fisheye State Routing:A Routing Scheme for Ad Hoc Wireless Networks［C］//New Orleans，LA，US.ICC 2000:70－74.

［9］Al-Fares M S，Sun Z L，Cruickshank H.A Hierarchical Routing Protocol for Survivability in Wireless Sensor Network(WSN)［C］//Hong Kong，China.Imecs 2009.2009:262－268.

［10］Ok C S，Lee S，Mitra P，et al.Distributed Energy Balanced Routing for Wireless Sensor Networks［J］.Computers ＆ Industrial Engineering，2009，57(1):125－135.

［11］Ko Y B，Vaidya N H.GeoTORA:A Protocol for Geocasting in Mobile Ad Hoc Networks［C］//Osaka，Jpn:IEEE，2000:240－250.

［12］Rappaport T S.Wireless Communications:Principles and Practice［M］.Upper Saddle River:Prentice Hall PTR，2002.

［13］Charles E P.Ad-Hoc On-Demand Distance Vector Routing［C］//New Orleans LA，US.Proceedings of the 2nd IEEE Workshop on Mobile Computing Systems and Applications.1999:90－90.

［14］Camp T，Boleng J，Williams B，et al.Performance Comparison of Two Location Based Routing Protocols for Ad Hoc Networks［C］//New York，NY，United States:Institute of Electrical and Electronics Engineers Inc.，2002:1678－1687.