無線傳感器網絡位置輔助路由算法研究

摘要：介紹了位置輔助路由的設計特點和準則，分析并定性比較了現有位置輔助路由的貪婪轉發策略以及遇到路由空洞時的各類恢復策略，最后指出了需要進一步研究的方向。

關鍵詞：無線傳感器網絡；位置輔助路由；恢復策略

中圖分類號：TP393文獻標志碼：A

文章編號：1001—3695(2007)03—0256—04

MEMS(Micro-Electro-MechanismSystem，微機電系統)、無線通信和數字電子技術的進步孕育出WSN(WirelessSensorNetwork，無線傳感器網絡)[1]。與現存的無線自組網相比，WSN有其自身的特點。如WSN節點數目更為龐大，分布更為密集；節點的能量、帶寬以及計算和存儲能力均非常有限；節點無統一標志，它們依靠廣播和多跳來交換數據[2]。因此在WSN中設計節能高效的路由算法至關重要。

WSN節點通常需要獲取它的位置信息，這樣采集的數據才有意義。因此節點的物理位置很自然地被考慮到路由協議的設計中，而小型廉價的低功耗GPS接收器的出現和定位技術的發展則使位置輔助路由成為可能。如果源節點已知目標節點和鄰居節點的物理位置，那么數據傳送時限制區域的路徑選擇策略將會替代全區域洪泛，從而提高整個網絡的路由效率。因此，有必要對WSN中的位置輔助路由進行研究。

1位置輔助路由的特點以及性能評價準則

WSN位置輔助路由算法的性能直接影響其可用性，如何評價它們是一個需要深入研究的問題。一般意義上的傳感器網絡應用不要求節點具有移動性，所以節點大多靜止，從而降低了相當一部分有關控制通信量的開銷。盡管如此，無線自組網中能量感知的位置輔助路由協議仍然適用于WSN。本文假設WSN中節點位置已知并且精確度較高。下面定性地討論幾個常用的評價算法的標準。

（1）無路由自環。路由算法本身應該無路由自環以避免路由失敗，部分情況下節點移動也會引發臨時自環現象。實踐證明無路由自環是算法可擴展性的有力保證，所以設計無自環行為的路由算法是必要的。

（2）記憶能力。在傳統的最短路徑算法中，每個節點需要維護龐大的路由表來存儲整個網絡的拓撲結構。另外，還需要存儲每個節點的狀態信息，如活動或休眠。鑒于傳感器節點存儲空間有限，路由算法應該盡量簡單高效，避免在每個節點上記憶經過路徑。因此貪婪轉發作為一種無需記錄路由狀態的路由算法，對傳感器網絡而言，是一種比較理想的數據轉發選擇。

（3）可擴展性。WSN節點數龐大且隨機部署，作為路由算法必須具有良好的可擴展性，能夠動態地適應網絡規模和節點個數的變化，保證網絡應用的需求。可擴展性與局部化相關，在可擴展的路由算法中，每個節點僅僅依靠鄰居以及目的節點的位置信息就可以決定下一跳節點。局部網絡中邊和節點的變化并不會立即影響任何一條路由，所以，很明顯地只有局部算法才能提供可擴展方案。在各種與WSN相關的設計中，可擴展性常常作為一條重要的原則被考慮。

（4）路徑選擇策略。包括單路徑、多路徑和泛洪三種策略。可以論證，一個理想的局部算法應該遵循單路徑原則。另一個極端是泛洪，消息被廣播到整個網絡或某個區域。而兩者的折中是多路徑策略。

（5）魯棒性。能量用盡或環境因素造成傳感器節點失效，周圍環境影響無線鏈路的通信質量以及無線鏈路本身的缺點等，這些WSN的不可靠特性要求路由機制具有一定的容錯能力。如果單個中間節點的失效不會影響數據傳輸或者能夠通過重新建立路由完成路由任務，則認為該算法魯棒性較好。

上述五個性能指標不僅是評價WSN位置輔助路由算法的標準，也是其設計和實現的優化目標。當然路由性能評價準則還有多種，如移動性、安全性和QoS支持等。本文著重從無路由自環、記憶能力、可擴展性、路徑選擇策略和魯棒性五個方面來分析和比較現有位置輔助路由算法的性能。

2位置輔助路由的轉發及恢復策略

自1984年Takagi和Kleinrock提出第一個基于距離的轉發策略MFR(MostForwardwithinRadius)[3]以來，越來越多的位置輔助路由算法相繼出現。目前位置輔助路由算法包括限制區域泛洪或貪婪的轉發策略以及遇到路由空洞時的恢復策略等。其中，轉發策略主要基于三種模型，分別是距離限制、矩形受限域和角度限制模型。

2.1轉發策略

傳統的泛洪模型無法擺脫其固有的缺陷，因為每個節點無論是否在最終的轉發路徑上均要轉發報文，使得網絡中充斥了大量的無用報文，也浪費了許多資源。而基于距離限制、矩形受限域和角度限制模型的泛洪或貪婪算法則可以減少報文轉發的盲目性，降低能耗，有效地解決了泛洪模型的缺陷。

2.1.1距離限制模型

MFR[3]和NFP(NearestwithForwardProgress)[4]同為基于前進量(Progress)概念的轉發策略。圖1顯示了節點A和B的前進量，Ab為B相對于A的前進量，同理，Ba為A相對于B的前進量。如圖2所示，MFR方案中，各個節點的前進量定義在S和D的連線上，為實現S到D的路徑發現過程，S選擇前進量最大的鄰居節點即M作為下一跳節點。而NFP則剛好相反，S選擇前進量最小的節點即N作為下一跳。Nelson等人[5]提出隨機選擇具有前進量的節點，然后調整傳輸半徑將數據包傳送給該選中節點。該方法簡單易行，但是要求節點具有可調的傳輸半徑。此外，Nelson等人[5]論證了傳輸成功率p與從節點a到b的前進量f(a，b)成反比，且NFP中數據包傳送的平均前進量p·f(a，b)高于MFR，因此NFP算法中包沖突率明顯較少。此外，Finn[6]還提出了一種基于距離的貪婪算法GRS(GreedyRoutingScheme)。S選擇最接近D的鄰居節點即G作為下一跳節點，前提條件是被選擇節點必須比源節點更靠近目的節點，否則該算法失效。GRS和MFR算法大多數情況下會選擇相同的路徑且無路由自環行為。以跳數作為算法的性能標準，在一次成功的路由任務中，GRS和MFR的路由性能與最短路徑策略相當。

圖1A和B的前進量圖圖2各類貪婪轉發路徑選擇

除了以上基于距離的單路徑轉發策略，多路徑算法EM-GMR(EnergyandMobility-awareGeographicalMultipathRouting)[7]將節點剩余能量和移動性作為參數引入到包的設計中。此方案有效地避免了可能導致的點對點路由失效，適用于移動性較高的WSN。當然，EM-GMR的多路徑策略也實現了可靠的路由傳輸，因為首選節點的失效不會導致當前路由失敗。EM-GMR算法的基本思想是節點之間定時廣播自身信息，其數據結構如圖3所示。進而源節點S選出較自己更接近目的地的節點N個，然后利用設計好的模糊邏輯系統(FLS)從中選出M(M

2.1.2角度限制模型

以角度作為路由決策的轉發算法之一為導航路由(CompassRouting)[8]。如圖2所示，SA偏離SD的角度最小，所以A將成為下一跳節點。角度方向一般采用右手定則確定以避免路由自環行為。

典型的角度域泛洪算法DREAM[9]中，每個節點維護一個位置數據庫，用來存放網絡中其他節點的位置信息。源節點S需要將數據包傳送給位于目標節點D的方向上的所有鄰居節點，而D的方向定義在該點的期望區域上。如圖4所示，源節點S先計算出目標節點D的期望區域，即圍繞D的半徑為r的圓面。由于位置信息隨時間不斷更新，半徑r按照(t₁-t_O)ν_max的規律變化。其中t₁表示當前時間，t_O表示S的位置信息表中關于D的時間戳，ν_max表示節點在網絡中移動的最大速度。既然得到了期望區域，那么D的方向則由S和D的連線以及角決定，如圖4中的虛線區域。S在D的方向上的所有鄰居節點均使用相同的方法確定D的方向并轉發數據包。如果在D的方向上無法找到合適的鄰居節點，則DREAM算法失效。此時需要啟動DREAM算法本身不具備的恢復策略來繼續包傳送。

圖4角度限制模型

角度限制模型與距離限制方案相比，兩者的數據傳輸率大致相同，但前者經過路徑跳數一般高于后者。在節點高密度部署時，距離限制算法的傳輸率較高[10]。

2.1.3矩形受限域模型

以源節點S和目的節點D為頂點總可以構造一個矩形，即本文所討論的RLA(RectangularLimitedArea，矩形受限域)。假定節點的傳輸半徑為R，為了提高路由請求的成功率，可以通過將目的地擴展為一個半徑為r的圓的方法進行優化，r一般不超過R。通過改變r可以改變受限域的大小，而r的設置可以根據節點的稠密程度進行調整。如果節點分布較為稠密，可以將r設置得小一些，因為節點稠密則在優化前的受限域中已有很高的概率找到一條路徑，若再擴大受限域，成功率的提高和增加的路由開銷相比不成比例。如果節點分布比較稀疏，可以將r設置得大一些，這樣可以提高成功率。

LAR(LocationAidedRouting)[11]協議將節點的物理位置引入路由發現過程，改變了傳統的被動路由方式。如圖5所示，LAR與DREAM風格類似，也提出目的節點的期望區域，不同的是LAR采用矩形請求區域，并且該請求區域通常包含期望區域。通過計算到目的節點的距離來判斷是否丟棄包。如果收到發現包的中間節點到目的地的距離小于前一跳到目的地的距離，該中間節點就繼續轉發此包；否則就丟棄。如果鏈路失敗則會在全區域內泛洪。

2.2恢復策略

各種轉發算法不論是基于何種模型，都會不可避免地遇到路由空洞(RoutingVoid)，即算法失效的時候。因為在路由過程中肯定會有找不到更接近目的節點的鄰居節點的情況。為了解決路由空洞問題，位置輔助恢復策略應運而生。最簡單的恢復策略就是泛洪。文獻[10]提出Greedy/Flooding方法，如果節點處于路由空洞狀態，則將消息泛洪到每個鄰居節點且此后拒絕接收類似的數據包，而收到泛洪信息的鄰居節點則采用貪婪方法繼續路由。下面介紹幾種具有代表性的恢復策略。

2.2.1Terminode

Terminode路由[12]是TLR(TerminodeLocalRouting，Terminode局部路由)和TRR(TerminodeRemoteRouting，遠程路由)的綜合體。該方法強調可擴展性、魯棒性、協作和簡易性。TLR機制允許在目的節點位置較近時采取主動式距離矢量方案路由數據包。與此對應，TRR機制則適用于目的節點位置較遠的情況，此時采用位置輔助路由方案。Terminode為了避免遠距離貪婪路由失效，發送節點通過TLR機制了解所有中間節點的大概位置，并且維護該位置數據表。數據包在轉發過程中遍歷數據表中的所有節點即可完成該次路由任務。該算法要求節點具有記憶能力，保存遍歷數據表，增加了節點負載。

2.2.2GEAR

GEAR(GeographicalandEnergyAwareRouting)[13]采用遞歸的貪婪法進行轉發并解決路由空洞問題。GEAR中定義節點傳輸的代價，其值與節點到事件區域的距離還有節點剩余能量相關。路由利用捎帶機制來獲取節點的實際路由代價，借此選擇到事件區域的優化路徑。具體路徑建立過程如圖6所示。

圖5矩形受限域圖6路徑建立過程

S節點在鄰居節點中選擇到事件區域代價最小的節點C作為下一跳，而此時因G，H和I失效，C處于路由空洞。所以C選取鄰居節點中代價最小的節點B作為下一跳，并將自己的代價值設為B的代價加上節點C到節點B一跳通信的代價，同時將這個新代價值通知節點S。當節點S再轉發查詢命令到節點D時就會選擇節點B而不是C作為下一跳節點。可以論證路由代價與節點剩余能量成反比，因此從最佳路由代價的路徑中選擇能耗較低的部分進行路由可以降低路由代價。GEAR路由中假設節點的地理位置固定或變化不頻繁，適用于節點移動性不強的應用環境，且此時該算法的性能與最短加權路徑相當。

2.2.3GPSR

GPSR(GreedyPerimeterStatelessRouting，貪婪周邊無狀態路由)[14，15]在平面圖的基礎上，采用貪婪－面－貪婪的方法進行數據轉發，無需存儲經過路徑。網絡中存在兩點U和V，要使邊UV屬于一個平面圖，當且僅當沒有其他節點在以UV為直徑的圓面中。如圖7所示，平面圖包含直線EF，而不包含AB連線，因為C在以AB為直徑的圓面內。一般采用右手定則遍歷平面圖，這樣才能避免路由自環。某些時候也可以使用左手定則輔以方向角。GPSR使用圖論的最短路徑和連通的概念來發現路由，并且依靠貪婪算法轉發包。如果遇到路由空洞，則轉入邊緣恢復模式，遍歷最接近的平面子圖，直到到達比路由空洞節點更接近于目的地的節點為止，然后繼續貪婪路由。如圖8所示，S到D的路徑為SGH-GFI-MD。從S到H是貪婪路由，由于H節點處于路由空洞，所以轉到恢復模式并采用遍歷平面圖的辦法，逆時針遍歷直到I，此時I比H更接近于D，所以從節點I開始恢復到貪婪模式直到D。

圖7平面圖的定義圖8從S到D的路由

2.2.4BGR

GPSR中，每個節點維護鄰居表，且依靠周期性的廣播消息更新該表，所以GPSR并非完全“無狀態”。基于此，文獻[16—19]提出了四種真正意義上的無狀態路由協議。這四種協議類似，只是在轉發域、定時器功能和恢復策略上略有不同。以BGR(BlindGeographicRouting)[17]為例，BGR中節點無需維護路由表和鄰居表，數據包在轉發過程中并不知道哪個節點將是下一跳，源節點設定一個恢復時間并將數據包連同自己所處轉發域的描述廣播到處于當前轉發域的所有節點，收到數據包的節點設置一個定時器，時間長度依賴某些參數，如到目的節點的距離、剩余能量、負載、使用頻率和隨機數等。定時器第一個到期的節點轉發數據包，同時其余節點關閉定時器并停止當前操作。如果到達恢復時間，而當前轉發域內不存在任何可轉發節點，則此次路由陷入空洞。此時待轉發節點發起恢復策略，將轉發域向左或向右旋轉一定角度，然后重新設定恢復時間并廣播數據。

2.3小結

從以上論述可以看出，各種位置輔助路由協議和轉發策略特性各異，有的簡單高效，有的實現復雜但可靠性高，它們有不同的適用范圍，具體比較如表1所示。

3展望

近年來，WSN定位技術不斷發展，為實現基于物理位置的路由協議奠定了良好的基礎。本文在已知目的節點位置信息的基礎上論述并定性比較了各種位置輔助路由協議中的轉發策略以及恢復策略。目前，該領域的研究還處于起步階段，為各種應用定制最佳的路由協議是今后研究的方向。進一步研究內容包括：①設計高效率的位置服務以適應快速網絡拓撲變化；②貪婪式算法中，如何選擇最佳下一跳以及更有效的恢復機制；③降低節點位置精確度的要求，設計具有安全性和QoS支持的路由協議等。

本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。