無線傳感器網絡中基于位置信息的節能方案

摘要：介紹了幾種適合無線傳感器網絡的基于位置信息的典型節能方案，主要集中在如何有效地利用位置信息實現能量高效分組轉發，如何有效地支持節點動態休眠以及數據融合等。討論了這些方案的工作原理、優缺點、存在的問題以及未來的發展方向。

關鍵詞：基于位置信息的路由； 節能； 數據融合； 無線傳感器網絡

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

文章編號：1001－3695(2008)03－0860－03

隨著無線通信、傳感器、嵌入式計算、分布式信息處理、電池等技術的不斷發展，無線傳感器網絡技術也取得了飛速進展。由于其在軍事、工農業、生物醫療等眾多方面的應用前景，無線傳感器網絡得到了越來越多的關注。無線傳感器網絡具有節點數量多、密度大、節點易于失效、拓撲動態變化以及節點能量非常有限等特點，傳統的網絡協議不能夠滿足針對特定功能和應用而設計的傳感器網絡。隨著定位技術的發展，基于地理位置信息的方案設計受到越來越多的關注，在提高能源有效性、可擴展性和健壯性等方面，此類協議有著良好的特性。傳感器節點的位置信息可以通過配備GPS收發器來獲得；當GPS定位不可行或不經濟的情況下，也可以通過一些GPS無關的定位機制[1]。在無線傳感器網絡中，基于位置信息的協議具有先天優勢，這是因為大多傳感器網絡應用本身要求節點在網絡操作和數據匯報過程中具有位置感知能力。

當前，基于位置信息的節能路由協議較多，它們適用于不同的應用場景，包括如何通過節點位置信息（包括自身位置、鄰居位置和信宿位置）以及節點能量信息來確定分組的最佳下一跳；如何通過節點動態睡眠的方式達到節能的目的并保持網絡連通；如何利用位置信息更有效地實現數據融合。

1設計原則

考慮上面提到的無線傳感器網絡的特性，基于位置信息的協議設計需要考慮以下原則：

a)能量有效性。傳感器節點的能源十分有限且常常無法二次充電，因此，提高傳感器網絡協議的能源有效性，顯得十分重要。節能是設計無線傳感器網絡協議的首要原則。

b)可擴展性。網絡協議需要滿足不同網絡規模、不同部署和拓撲結構的傳感器網絡，因此，協議的設計必須考慮能夠確保在大規模傳感器網絡中的良好運行和協議性能?；谖恢眯畔⒌姆纸M轉發機制的無狀態特性使得這類方案具有良好的可擴展性。

c)抗毀性。為了保證可靠的數據傳送，協議設計需要充分考慮抗毀性——這是因為傳感器網絡部署環境常常比較惡劣。例如，當某個或者某一區域的傳感器節點因為能量耗盡、環境干擾或人為破壞而不能正常工作時，路由協議需要能夠快速找到備用路由。基于位置信息的路由協議由于采用分組逐跳轉發方式，當發生拓撲動態（如鏈路中斷或節點失效）時，協議可以迅速地確定新的下一跳節點。

d)自適應性。由于受到能量、環境干擾、外界環境變化、節點加入/退出等影響，無線傳感器網絡的網絡狀態變化較快，集中控制很難實現或效率太低，網絡協議的設計必須能夠自動適應各種網絡狀態變化——最好采用局部操作方式。

其他一些網絡協議評價準則還包括，協議對節點移動的適應性、對分組丟失的響應、對存在非對稱鏈路網絡的考慮、網絡時延特性、節點內存、計算能力等限制因素。

2基于位置信息的節能方案

下面將從能量高效逐跳分組轉發、節能與節點動態休眠、數據融合與位置路由等幾個方面介紹一些典型方案。

2．1能量高效分組轉發機制

能量高效的分組轉發機制需要根據節點的剩余能量（PA）、節點間距離（L）、目的節點（或稱信宿）位置等信息來確定最佳下一跳接收節點。這類方案通常要求每個節點具備其自身位置、相鄰節點位置以及信宿位置信息。這類機制大體可以分為四種。

2．1．1最大PA選擇

在圖1中，節點T（T可以是信源也可以是一個中繼節點）選擇其到信宿的下一跳節點時，它在所有距離信宿比自己近的鄰居中，選擇具有最大PA的節點作為它的下一跳。該過程分為兩個步驟：a)在T的鄰居節點中根據位置信息確定比T距離信宿更近的節點；b)比較這些節點的剩余能量，選擇具有最大剩余能量的節點作為下一跳。如圖1中，T首先選擇距離信宿更近的鄰居節點A、B、C，由于C的剩余能量最大，故選擇C為下一跳。最大PA選擇策略有利于實現網絡中節點間能耗均衡。

注：圖中T是執行分組轉發的節點，Dest是分組的信宿。圍繞T的虛線圓是T的傳輸范圍。

圖1基于位置信息的分組轉發方案示意圖

2．1．2最近鄰選擇

信源（或中繼節點）T從所有距離信宿比T更近的鄰居節點中，選擇距離T最近的鄰居節點作為下一跳[2]。如圖1中，T選擇節點C作為下一跳。在節點具備功率控制能力的情況下，這一策略有利于降低端到端分組轉發帶來的能耗。

2．1．3最接近信宿選擇

在文獻[3]中，節點T從所有距離信宿比T更近的鄰居節點中，選擇距離信宿最近的節點作為下一跳。在圖1中，節點B距離信宿最近，故T選擇B為下一跳。這一策略有利于降低分組延遲。在節點分布比較密集的網絡中，這一策略傾向于返回具有最小跳數的路徑。

在一個靜態網絡（即由靜止節點組成的網絡、且不考慮節點和鏈路失效）中，隨著時間的推移，對于在任意給定兩個節點之間選路，基于最大PA選擇策略得到的路徑可能隨著網絡中節點能量變化（下降）而動態變化；與之相比較，基于最近鄰選擇策略和最接近信宿選擇策略得到的端到端路徑是恒定的。另外值得指出的一點是，已經證明，上述三種策略所得到的路徑均是無環的。

2．1．4基于位置信息的高效節能路由協議

顯然，將分組傳送能耗、節點間能耗均衡等因素有效地結合起來考慮能夠更好地節能、延長網絡壽命。在文獻[2]中，Stojmenovic等人設計了一種將節點剩余能量、鏈路功率值綜合起來考慮的分組轉發策略。通常認為，節點發射、接收單位信息所耗費的能量u與信息發送方和信息接收方之間的距離L具有如下關系，u(d)=Lα+c。其中：α是與傳播環境和硬件相關的常數（通常2≤α≤6）；c則代表節點的收/發電路處于工作狀態時的能耗以及信號處理能耗（這里沒有考慮其他信道干擾，常見的無線信號傳播模型包括自由空間(free space)模型和tworay ground reflection模型）。因此，將信息包經過適當的多跳轉發可以節約能量。另外，在選擇下一跳節點的過程中，文獻[2]中還根據各個備選下一跳節點距離信宿的距離來估計剩余路徑上的能耗，并與前面提到的下一跳鏈路能耗、節點剩余能量結合進來選擇最佳下一跳節點。如圖1中，對于T來說，它對每個鄰居節點的計算過程如下（以鄰居節點A為例進行說明）：T→A的實際鏈路能耗uAr=L3α+c，A→Dest的估計能耗計算方式為uAf=L7×c((α-1)/c)1/α+L7×((α-1)/c)(1-α)/α，將兩者相加，然后除以節點A的剩余能量（作為節點A參與轉發的不情愿指數）就得到了節點A的轉發權重WA=(uAr+uAf)/PAA；按照上述方式對每個備選鄰居進行單獨計算，并從中選擇轉發權重最小的作為其下一跳。具體的下一跳返回值和α及c有關。文獻[4]進一步結合GPSR算法[5]來克服網絡中存在空洞(void)或障礙物時的端到端確保傳輸(guaranteed delivery)問題。

Kuruvila等人[6]考慮每跳轉發所帶來的增益，即較之信宿前進的距離與所耗費能量的比值，從而得到單位前進距離帶來的平均能耗，以此推算虛擬的未來能耗，并依據這一度量進行下一跳選擇。文獻[6]中還給出了如何利用剩余能量與能耗相結合的辦法替代單純的基于能耗的路由算法。

2．2節能與休眠

節點發送、接收、監聽信道都需要耗費較大的能量。節點動態睡眠可以更有效地延長網絡壽命。前面介紹的方案主要針對最小化單個分組的能耗以及如何平衡網絡中節點間的能耗。下面介紹幾個基于位置信息的節點動態休眠協議。

Xu等人[7]提出了將整個網絡部署區域分割成虛擬的格狀結構，如圖2（a）所示。每個方格相當于一個簇，方格內部的節點通過相互協作選出一個節點作為簇頭，其他節點則可以進入睡眠狀態。文獻[7]中證明，對于一個原始連通的網絡，如果小方格的邊長r與傳感器節點最大傳輸半徑R之間的關系為r≤R/5，并且如果每個方格中至少有一個節點，經過上述處理后的網絡仍然連通。相鄰方格間的通信有兩種方式，如圖2（b）和（c）所示。在圖2（b）的方式下，只能保證每個方格中任意位置的節點可以自由地與其上、下、左、右四個相鄰方格內的任意節點進行通信，此時要求r≤R/5；在圖2（c）的方式下，保證每個方格中任意位置的節點與其周圍的八個相鄰的方格中任意位置的節點均可以進行通信，此時要求r≤R/8。

文獻[8]在文獻[7]的基礎上作出了進一步改進——整個網絡部署區域仍然劃分成虛擬的格狀結構，但是在整個網絡區域中維護了一些方格作為連通支配集合(connected dominating set)從而形成一個連通的骨干網絡結構，如圖3、4中，灰色方格表示整個網絡的支配集合。屬于支配集的方格（中的節點）直接沿著整個支配集進行數據傳輸；非支配集中的方格，則先選擇距離自己最近的處于支配集中的鄰居方格，把數據傳輸給這個支配集中的方格，然后沿著整個支配集進行傳輸。同理，如果信宿處于非支配集中的方格內，那么就先傳輸到距離該節點最近的支配集中的方格，從而最終把數據發送至信宿。這樣可以大大降低為保持網絡連通所需要參與的節點（即需要保持喚醒狀態的節點）數量而不損失路由的性能。圖3和4示意了兩種不同的支配集選取方法。

2．3基于位置信息的數據融合

由于在一個區域內的各個傳感器監測到的數據可能具有很大的相似性，進行數據融合可以有效去除冗余的數據，減輕網絡負擔，從而降低網絡的能耗。文獻[9]給出一種基于地理位置信息的數據融合點選取方法：在數據查詢區域內，把距離區域中心最近的傳感器節點作為數據融合點，區域內的其他傳感器節點先將數據發送到這個數據融合點，然后由數據融合點進行數據融合，之后再傳送給sink節點（圖5）。然而，從節能的角度看，查詢區域的中間點未必是最佳數據融合點，如何利用位置信息更有效地選取數據融合點來降低總能耗、提高網絡性能仍是一個值得進一步關注的課題。

3結束語

無線傳感器網絡中基于位置信息的節能方案是目前的一個研究熱點。本文討論了基于位置信息的能量高效路由方案、節點動態休眠方案以及高效數據融合方案等。這些方案在不同的環境下具有較好的節能特性，對于提高網絡性能，延長網絡生命有著較好的促進作用。此外，在基于位置信息的節能機制方面，還有其他一些問題值得關注：

a)跨層路由協議設計。文獻[10]中給出了一個考慮由于信道傳輸誤碼而導致的分組丟失和鏈路層反饋重傳相結合的節能路由方案。除了前面提到的路徑總功率值、路徑上節點的剩余能量，轉發節點選擇還受鏈路丟失率、分組長度、MAC層的一些控制（如鏈路層握手、確認等）開銷等因素影響。

b)基于位置信息的組播。文獻[11]中設計了一個針對組播應用、基于位置信息的信息發布和查詢機制。監測到特定現象的傳感器節點主動在網絡中吸納一些均勻散布在不同地理位置上的信息發布點（即傳感器節點）。對上述信息感興趣的用戶通過一定的查詢方式在信源、信息發布點及不同用戶之間動態維護一棵信息發布樹。該協議主要考慮信息發布和查詢的易實現性而沒有過多關注組播樹的代價特性及能量特性。

c)功率控制與QoS。文獻[12]中研究了在節點具備功率控制能力的傳感器網絡中，分組平均發送半徑、端到端延遲、路徑節能特性三者之間的關系，并在延長網絡壽命和滿足數據的延遲特性之間給出了良好的折中關系。

d）位置服務。在采用一個或多個移動sink的傳感器網絡中，如何能夠有效地在一個低開銷的水平上向傳感器節點提供可能處在移動狀態的sink的位置信息以提高路由協議的性能，是一個值得進一步研究的問題。采用位置信息全網泛洪可行，但無疑不是最佳選擇。

此外，本文中所討論的不同節能策略也可以組合起來運用。組合策略常常會比單個策略的性能有更大的提高，這些問題值得進一步研究。

參考文獻：

[1]HIGHTOWER J， BORRIELLO G. Location systems for ubiquitous computing[J]. IEEE Computer， 2001， 34(11):57－66.

[2]STOJMENOVIC I， LIN Xu. Poweraware localized routing in wireless networks[J]. IEEE Trans on Parallel and Distributed Systems， 2001，12(11):11221133.

[3]FINN G G. Routing and addressing in large metropolitanscale internetworks， ISI Research Report， ISU/RR－87180[R]. California: University of Southern California， 1987.

[4]STOJMENOVIC I， DATTA S. Power and cost aware localized routing with guaranteed delivery in unit graph based Ad hoc networks[J]. Wireless Communications and Mobile Computing， 2004，4(2):175188.

[5]KARP B， KUNG H T. GPSR: greedy perimeter stateless routing for wireless networks[C]//Proc of the 6th Annual International Confe￣rence on Mobile Computing and Networking. Boston， Massachusetts: ACM Press， 2000: 243－254.

[6]KURUVILA J， NAYAK A， STOJMENOVIC I. Progress based loca￣lized power and cost aware routing algorithms for ad hoc and sensor wireless networks[J]. International Journal of Distributed Sensor Networks， 2006，2(2):147159.

[7]XU Ya， HEIDEMANN J， ESTRIN D. Geographyinformed energy conservation for Ad hoc routing[C]//Proc of the 7th Annual International Conference on Mobile Computing and Networking. Rome， Italy: ACM Press， 2001: 70－84.

[8]ZHANG Baoxian， MOUFTAH H T. Efficient gridbased routing in wireless multihop networks[C]//Proc of the 10th IEEE Symposium on Computers and Communications. La Manga del Mar Menor， Cartagena， Spain: IEEE Computer Society， 2005: 367－372.

[9]LIU Yueyang， JI Hong， YUE Guangxin. Routing protocol with optimal location of aggregation point in wireless sensor networks[J]. The Journal of China Universities of Posts and Telecommunications， 2006，13(1):1－5.

[10]KURUVILA J， NAYAK A， STOJMENOUIC I. Hop count optimal position based packet routing algorithms for Ad hoc wireless networks with a realistic physical layer[J]. IEEE Journal of Selected Areas in Communications， 2005，23(6):12671275.

[11]LUO Haiyun， YE Fan， CHENG J， et al. TTDD: twotier data dissemination in largescale wireless sensor networks[J]. Wireless Networks， 2005，11(1－2):161175.

[12]AMMARI H M， DAS S K. Tradeoff between energy savings and sourcetosink delay in data dissemination for wireless sensor networks[C]//Proc of the 8th ACM International Symposium on Modeling， Analysis and Simulation of Wireless and Mobile Systems. Montréal， Quebec， Canada: ACM Press， 2005: 126133.

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