基于地理位置的無線傳感器網絡路由協議

摘要：基于地理位置的路由協議是無線傳感器網絡路由協議研究的一個重要方向。利用位置信息指導路由的發現、維護和數據轉發，能夠優化路徑選擇，減少路由能耗，實現網絡的全局優化。從限制洪泛機制、虛擬分區機制、最優路由確認機制3個方面，可以看出地理位置信息在路由協議中的重要性。

關鍵詞：無線傳感器網絡；路由協議；地理位置；虛擬分區

Abstract: Routing algorithms based on geographical location information is an important research subject in the wireless sensor network. The routing algorithms based on geographical location information can confirm the best routing， reduce the energy consumption， and optimize the whole network. Through three aspects involving the flooding restriction scheme， the virtual area partition scheme and the best routing choice scheme， the importance of location information is seen in the routing algorithm.

Key words: wireless sensor network; routing algorithm; location information; virtual area partition

無線傳感器網絡(WSN)是將大量的具有通信與計算能力的微小傳感器節點設置在無人值守的監控區域，構成的智能自治測控網絡系統。在WSN的實際應用中，尤其是軍事應用中，往往需要實現對傳感器節點的定位，獲取監控區域的地理位置信息，因此，位置信息也很自然地被考慮到WSN路由協議的設計中。基于地理位置的路由協議是當前路由協議研究的一個重要方向，受到了廣泛關注。

基于地理位置的路由協議利用位置信息指導路由的發現、維護和數據轉發，能夠實現信息的定向傳輸，避免信息在整個網絡的洪泛，減少路由協議的控制開銷，優化路徑選擇，通過利用節點位置信息構建網絡拓撲圖，易于進行網絡管理，實現網絡的全局優化。

國內外的學者針對不同的應用背景已經提出了多種基于地理位置的路由協議，如何充分地利用地理信息來實現高效的路由是研究的重點。本文將具體分析地理信息在路由協議中的應用，分別從限制洪泛機制、虛擬分區機制、最優路由確認機制等3個方面進行分析。

1 基于位置信息的限制洪泛機制

傳統的Flooding洪泛路由協議具有簡單性和魯棒性的優點[1]，許多路由協議的設計中都采用了洪泛路由的思想，然而洪泛路由存在著信息重疊和信息“內爆”現象，造成了大量的信息冗余和盲目的資源浪費。利用距離、方位等地理信息來指導和限制路由洪泛，界定洪泛路由搜索區域，能夠大大提高路由搜索的方向性和有效性。當在路由受限區域內沒有合適的路徑時，可以自適應地對洪泛區域進行調整，或采用傳統洪泛的方法繼續進行路由搜索。受限洪泛區域主要有距離受限域、角度受限域和矩形受限域等形式。

1.1 距離洪泛受限域

目的區域的位置不確定時，可以構建一種簡單的距離限制域：路由搜索信息向距離信息發送節點更遠的方向進行洪泛，只有距離信息發送節點更遠的節點收到數據包時才進行轉發，通過這種方式能夠減少信息的冗余。目的區域的位置能夠確定時，可以由距離目的區域更近的節點所在的區域來構成路由請求區域。如位置輔助路由(LAR)協議中確定路由請求區域的其中一種方案，便采用了這種思想[2]。

1.2 角度洪泛受限域

角度限制域是根據某一個角度而確定的受限域，也就是說，位于一定的角度范圍內的中間節點才能作為路由洪泛的中繼轉發節點。限制角度的選取有多種方法，圖1、圖2和圖3分別示意了3種角度選取方法。

圖1中所確定的角度受限域由兩條相交的射線OM和OP所構成[3]，以源節點S和目的節點D為圓心、以RS和RD為半徑構造了兩個界限圓，不妨假設RS >RD，可以得出兩圓的公切線以及它們的交點O，易于算出限制角∠SOM的度數。RS 和RD的大小根據具體應用進行設定。

圖2中所確定的限制角度是變化的，而不是固定不變。S 點為源節點，D點為目的節點，X為一個中轉節點。X所轉發的路由請求包中包含限制角∠DXM，可以根據式(1)計算：

收到X轉發的數據包的節點J和K分別計算∠DXJ和∠DXK，并與∠DXM比較大小。若該角度小于限定角的節點繼續轉發數據包，則節點K丟棄數據包，節點J 將轉發路由請求數據包，并且節點J 將按照上述處理方法更新限定角的大小并繼續轉發數據包。

圖3中源節點的路由請求數據包中包含自身的位置信息和預定的限制角度[4]，中間節點M 收到數據包后，通過三角公式可以得出自己和源節點S、目的節點D間的夾角∠SMD，如果∠SMD大于預定的轉發限制角，則繼續轉發，否則就丟棄數據包。預定的限制角度可以根據具體應用進行設定。

1.3 矩形洪泛受限域

矩形限制域即是通過一定的策略所劃定的矩形洪泛區域，具體給出以下兩種劃分方法。

圖4中的矩形區域即為矩形受限域的一種構造方法。以源節點S 和目的節點D 作為兩個頂點總可以構造矩形區域。為提高路由請求的成功率，可以將目的地擴展為一個半徑為R 的圓形區域進行優化。半徑R一般不超過節點的通信半徑，其設置可以根據節點的稠密程度進行調整，一般情況下，如果節點稠密可以將R 設定得小些，如果節點稀疏則可以將R 設定得大些，以保證路由的成功率。

圖5中給出了另外的一種矩形受限區域[5]，源節點S 和目的節點D分別作為所構造矩形兩條對應邊L1、L2的中心，以與源節點和目的節點所構成的直線所平行的兩條線段L3、L4作為矩形的另外兩條邊。其中w為L1、L2的邊長，其大小可根據具體應用進行設定。

此外，通過對整個區域劃分為網格，進而查詢信息分別在各個矩形網格內進行洪泛，如雙層數據發布(TTDD)協議[6]，也可以理解為矩形限制域的一種構造方法。

2 基于位置信息的網絡虛擬分區機制

基于虛擬分區的路由機制是利用地理位置信息將整個監控區域劃分為若干子區域，進而利用區域的位置信息來設計路由的機制。它適合于大規模網絡，可擴展性強，利用組織結構設計的方法較好地解決了大規模網絡的協同問題；各分區所包含的位置信息利于路由的建立，能夠實現方向性信息傳輸，減少信息傳輸的盲目性，減少信息冗余，便于信息融合和移動節點處理，信息傳輸的實時性好；此外通過對區域內的節點的任務分配和調度，可以使部分節點處于休眠狀態，節省能量，延長網絡壽命。

虛擬分區可以有多種形式，包括規則的幾何網絡分區、虛擬極坐標系統以及由分簇算法形成的不規則分區等。具體實現中，可以考慮將整個網絡均衡地劃分為網格區域；也可以根據節點密度、連通度、網絡規模等信息將網絡非均勻地劃分為若干分區。路由搜索過程中，可分為區域內路由和區域間路由兩個過程分別進行考慮。

2.1 規則網絡區域的劃分

規則網絡分區可以考慮采用包括矩形、正六邊形、三角形、菱形、圓形、扇形區域等多種形式。正六邊形區域是借鑒蜂窩網的小區機制，由于其計算較為復雜，較少采用；圓形區域方法是通過比較分區半徑和節點到分區中心點距離確定節點的所屬分區，在分區的邊界會有重疊；文獻[7]中提出了三角形或菱形區域的分區方法，即是將網絡區域劃分為三角形或菱形的網格分區。文獻[8]中提出了將網絡區域劃分為環帶扇形柵格的分區方法；矩形區域劃分方法不存在重疊區域，實現過程比較簡單，在實際中得到了較多的采用。

方形網格是最常用的矩形分區方法，是較多地采用的一種分區方式，如基于位置的能量感知路由(GAF)[9]、TTDD、基于網格的路由(GRID)、基于網格的分簇路由(GROUP)[10]等協議。本文中將對幾種典型的基于方形網格的路由協議進行分析。

GAF協議中，根據節點的位置信息和通信半徑，將網絡區域劃分成若干虛擬單元格，保證相鄰單元格中的任意兩個節點都能夠直接通信。假設所有節點的通信半徑為R，網格區域劃分的邊長為r，則為了保證任兩個單元格間的通信，需要滿足 。網格內采用讓部分節點進入休眠狀態以減少能量消耗的拓撲控制算法，同時采用節點狀態轉換機制控制節點的狀態。GAF的核心思想是盡量通過使虛擬網格中的每個區域的代表節點總是處于激活狀態模式來保持網絡互聯。

TTDD協議中，當多個節點探測到事件發生時，選擇一個節點作為發送數據的源節點。源節點以自身作為格狀網的一個交叉點構造一個格狀網。其過程是：源節點先計算出4個相鄰交叉點的位置，利用貪婪算法請求最接近交叉點位置的節點成為轉發節點，轉發節點繼續這個過程直至請求任務超時或到達網絡邊緣。轉發節點保存了事件和源節點的信息，是以后進行數據傳輸的參與者。在匯聚節點進行數據查詢時，匯聚點的查詢請求采用洪泛的方式在在交叉點間傳播，直到源節點收到查詢請求，數據反向傳送到匯聚節點。

GRID協議中整個網絡被分成若干固定大小的虛擬網格，路徑由一組特定的虛擬網格組成。每個網格中通過一定的方法選取一個節點作為網關，負責所有經過本網格的數據包的轉發，路由采取從網格到網格的方式。文獻[5]中給出了多種網格邊長的確定方法，其中，若設節點的通信半徑為R，網格邊長為r，則當滿足

時，就能保證對角的相鄰網格間節點的通信暢通，即能滿足八向鄰域網格間的通信。

GROUP協議中，每隔一定的時間，由Sink點選出網格種子節點，進而建立以網格種子節點為基準點的一定寬度的虛擬格子。每個網格中選舉出一個節點作為簇頭節點，簇頭節點一般接近網格交叉點，在簇頭節點周圍一定范圍內的節點都屬于該簇。

2.2 虛擬極坐標系統

虛擬極坐標系統是一種較為特殊的角度分區方式，適用于數據中心存儲方式的地理位置輔助路由(GEM)協議[11]基本思想便是建立一個虛擬極坐標系統來表示實際的網絡拓撲結構。網絡中的節點形成一個以匯聚節點為根的帶環樹，每個節點用到樹根的跳數距離和角度范圍來表示，節點間的路由通過這個帶環樹來表示。虛擬極坐標系統建立過程為：由匯聚點將角度范圍分配給每個子節點，如[0，90]。每個子節點得到的角度范圍正比于以該節點為根的子節點的數目。每個子節點按照同樣的方式將自己的角度范圍分配給它的子節點。這個過程一直持續進行，直到每個葉節點分配到一個角度范圍。這樣，節點可以根據一個統一的規則(如順時針方向)為子節點設定的角度范圍，使得同一級節點的角度范圍順序遞增或遞減，于是到匯聚點跳數相同的節點就形成了一個環形結構，整個網絡則形成一個以匯聚節點為根的帶環樹。其基本的路由過程為：節點發送數據時，若目的位置的角度不在角度范圍內，就向父節點傳遞該消息，父節點也采用同樣的方式處理該消息，直到消息到達了包含目的節點的位置角度的節點。

2.3 基于分簇算法的不規則分區

位置信息在分簇路由中也能夠得到重要的應用，根據不同的分簇算法所形成的各個簇往往同時構成了不規則的網絡虛擬分區。簇頭的產生是簇形成的基礎，簇的位置信息是簇頭選擇算法的一個重要準則，這些地理信息包括節點距簇頭的距離、簇頭距基站的距離、距離能耗比等信息。如基于模糊邏輯的簇頭選舉(CEFL)算法[12]將節點向心性作為一個簇頭選舉的準則，向心性即節點靠近簇中心的程度，用該節點到簇內其它節點的距離平方和來度量。簇頭產生之后，周圍節點根據簇頭的分布選擇所加入的簇，位置信息同樣會得到應用，如在基于能量優先的分簇路由(EECS)協議[13]中，節點確定所加入的簇的通信代價的計算公式中，考慮到了節點到簇頭的距離以及簇頭到基站的距離。

3 基于位置信息的最優路徑確認機制

在網絡多跳轉發節點選擇過程中，往往要依據一定的準則選取最優節點作為下一跳轉發節點。基于地理位置信息的最優路徑確認機制是將角度、距離等位置信息作為一個路徑選擇準則而建立路由。具體列舉幾種典型的路由算法來說明地理信息在最優路徑確認中的作用。

3.1 GPSR協議

貪婪型轉發和沿周邊轉發路由(GPSR) [14]是采用貪婪轉發算法的典型代表協議。當節點需要轉發數據分組時，它首先在鄰節點中選擇距離目標最近的節點作為其下一跳節點，然后將數據分組轉發給該節點。針對貪婪算法引起的局部優化問題，即當找不到滿足條件的下一跳節點的時候，GPSR提出了邊界轉發策略，作為貪婪轉發算法的一個補充，采用在該區域原始網絡圖之上建立平面圖的方法解決路由空洞的問題，即通過圍繞平面圖邊界向目標區繼續轉發的方式恢復路由。完整的GPSR協議結合利用貪婪算法和邊界轉發算法來實現數據向目的節點的轉發。網絡中以貪婪轉發為主，當找不到滿足條件的下一跳節點時，在平面圖中使用邊界轉發算法來決定下一跳。

3.2 GEAR協議

基于地理位置和能量的路由(GEAR) [15]采用查詢的方法來建立從源節點到事件區域的路由。借鑒了GPSR的貪婪算法的思想，利用節點的地理位置信息以及節點能量剩余情況，選擇綜合開銷(節點能量消耗與距離目標遠近的組合)最小的鄰節點進行數據轉發，建立查詢消息到事件區域的路徑。查詢信息到達事件區域后，可以采用迭代地理轉發的策略或受限洪泛的方式發布該數據。

采用迭代地理轉發的策略時，事件區域內首先收到查詢命令的節點將事件區域分為若干的子區域，并向所有子區域的中心位置轉發查詢命令，子區域中最靠近中心位置的節點收到查詢命令，并將自己所在的子區域再次劃分為若干的子區域并向各子區域中心位置轉發查詢命令。該消息傳播過程是一個一次迭代的過程，當節點發現自己是區域內唯一的節點，或子區域內沒有節點時，則停止向該子區域發送查詢命令。當所有子區域轉發過程全部結束時，整個迭代過程終止。遞歸地理轉發機制更為適用于區域節點分布密集的應用環境。

3.3 TBF協議

基于傳輸軌道的路由(TBF) [16]利用參數在數據包頭中指定一條連續的傳輸軌道而不是路由節點序列。節點利用貪婪算法根據其軌道參數和鄰節點的位置，計算出最接近的鄰節點作為下一跳節點。通過指定不同的軌道參數，很容易實現多路徑傳播、廣播和對特定區域的廣播和多播。

3.4 SPAN協議

基于能量協調的地理路由(SPAN) [17]根據節點的位置選取一些節點作為協調者或主管節點，這些選出的主節點形成一個網絡骨干，專門負責轉發消息，不在骨干網上的節點，定期地休眠。網絡中的每個節點能夠以分布式方法，獨立、周期性地判斷自己應該處于休眠狀態還是工作狀態。

4 結束語

地理位置路由協議是路由協議研究的一個重要領域。從長遠來看，可以從以下幾個方面對基于地理位置的路由協議進行進一步研究：

(1)結合定位技術進行路由協議研究。現有的地理路由協議中，大都沒有具體指出獲取節點位置信息的具體方法，多是在假設節點位置信息已知的情況下進行研究，實際上節點的定位技術仍然是當前WSN研究中的一個重點和難點問題，節點定位的過程和精度影響著路由協議的設計。結合定位算法來考慮路由協議的設計，考慮到定位精度對協議性能的影響，能夠提高路由協議的有效性和針對性。不依賴于定位信息的地理位置路由(GRWLI)協議[18]提出了一種只需少量節點精確位置信息就可正確路由的地理路由機制，協議的關鍵是利用少數的信標節點來確定全局坐標系以及其他節點在全局坐標系中的位置。

(2)考慮到地形影響的路由協議研究。實際應用中，WSN往往要受到地貌、地物等地理因素的影響。已有的一些路由往往是基于虛擬的二維地理空間進行考慮，對實際環境的考慮不夠充分。因此，基于實際地理環境進行路由協議研究也是一個需要研究的問題。

(3)基于覆蓋控制的地理位置路由協議研究。路由協議的設計過程中，要考慮到節點連通和網絡覆蓋問題。尤其是在路由設計中考慮到休眠機制時，需要對覆蓋控制問題進行分析。

(4)基于地理位置的安全路由協議研究。許多應用中，尤其在軍事應用中，必須考慮到路由協議的安全性。例如，在文獻[19]中，進行了基于地理位置的密鑰分配的研究。

(5)水下、深空、地下無線傳感器網絡基于地理位置的路由協議的研究。針對這些特殊的應用場合，應開展相應的研究工作。

5 參考文獻

[1] HEDETNIEMI S， LIESTMAN A. A survey of gossiping and broadcasting in communication networks [J]. Networks， 1998， 18(4): 319-349.

[2] KO YOUNG BAE， VAIDYA N H. Location-aided Routing (LAR) in mobile Ad Hoc networks [J]. Wireless Networks， 2000， 6(4):307-321.

[3] 張錦. 傳感器網絡中基于位置信息的路由算法研究[D]. 長沙: 湖南大學， 2004:14-20.

[4] 王軍， 于海斌. 一種兩段式傳感器網絡路由協議[J]. 儀器儀表學報， 2007， 28(5):908-913.

[5] LIAO W H， TENG Y C， SHEU J P. GRID: A fully location-aware routing protocol for mobile Ad Hoc net works [J]. Telecommunication Systems， 2001， 18(1): 37-60.

[6] YE F， LUO H， CHENG J， et al. A two-tier data dissemination model for large-scale wireless sensor networks [J].Wireless Networks， 2005， 11(2): 161-175.

[7] WANG XUEQING， YANG YONGTIAN， ZHANG ZHOUGLIN， et a1. A virtual rhomb grid-based movement-assisted sensor deployment algorithm in wireless sensor networks [C]// Proceedings of the International Multi-symposiums on Computer and Computational Sciences: Vol 1， Apr 20-24， 2006， Hangzhou， China. Piscataway， NJ， USA: IEEE Computer Society， 2006: 491-495.

[8] 孫雨耕， 李桂丹， 武曉光， 等. 基于基站輔助定位的無線傳感器網絡通信協議[J]. 天津大學學報， 2007， 40(1): 98-103.

[9] XU Y， HEIDEMANN J， ESTRIN D. Geography informed energy conservation for Ad-hoc routing [C]//Proceedings of the Seventh Annual ACM/IEEE International Conference on Mobile Computing and Networking， Jul 16-21， 2001. Rome， Italy. 2001: 70-84.

[10] YU LIVANG， WANG NENG， ZHANG WEI. GROUP: a Grid-clustering Routing Protocol for Wireless Sensor Networks[C]// proceedings of International Conference on Wireless Communications， Networking and Mobile Computing， Sep 22-24，2006， Wuhan， China. Piscataway， NJ ，USA:IEEE，2006: 1-5.

[11] NEWSOME J， SONG D. GEM: Graph embedding for routing and data-centric storage in sensor networks without geographic information [C]//Proceeding of 1st ACM Conference on Embedded Networked Sensor Systems， Nov 5-7， 2003， Los Angeles， CA， USA. New York， NY， USA: ACM， 2003: 76-88.

[12] GUPTA I， RIORDAN D. Cluster-head election using fuzzy logic for wireless sensor networks [C]//Proceedings of the 3rd Annual Communication Networks and Services Research Conference， May 16-18， 2005， Halifax， Canada. 2005: 255-260.

[13] YE M， LI C F， CHEN G H， et al. EECS: An energy efficient clustering scheme in wireless sensor networks [C]//Proceeding of the IEEE International Performance Computing and Communications Conference， Apr 7-9， 2005， Phoenix， AZ， USA. New York， NY， USA: IEEE， 2005: 535-540.

[14] Karp B， Kung H. GPSR: Greedy perimeter stateless routing for wireless networks [C]//Proceeding of the 6th Annual International Conference on Mobile Computing and networking， Aug 6-11， 2000， Boston， MA， USA. New York， NY， USA: ACM， 2000: 243-254.

[15] YU Y， GOVINDAN R， ESTRIN D. Geographical and energy aware routing: A recursive data dissemination protocol for wireless sensor networks [R]. UCLA/CSD-TR-01-0023. 2001.

[16] NICULESU D， NATH B. Trajectory based fording and its applications [C]//Proceedings of the 9th Annual International Conference on Mobile Computing and Networking， Sep 14-19， 2003， San Diego， CA， USA. New York， NY， USA: ACM， 2003: 260-272.

[17] CHEN B， JAMIESON K， BALAKRISHNAN H， et a1. SPAN: An energy efficient coordination algorithm for topology maintenance in ad hoc wireless networks [J]. Wireless Networks， 2002， 8(5): 481-494.

[18] RAO A， RATNASAMY S， PAPADIMITRIOU C， et a1. Geographic Routing without Location Information [C]//Proceedings of the 9th Annual International Conference on Mobile Computing and Networking， Sep 14-19， 2003， San Diego， CA， USA. New York， NY， USA: ACM， 2003: 96-108.

[19] 蔡曉， 楊庚， 王江濤. 一種基于位置信息的WSN隨機密鑰預分配方法[J]. 南京郵電大學學報:自然科學版， 2007， 27(1): 20-24.

收稿日期：2008-01-31

作者簡介

鄭鍇，解放軍炮兵學院在讀碩士研究生。研究方向為無線傳感器網絡路由協議。

童利標，解放軍炮兵學院副教授、碩士研究生導師。研究方向為多傳感器信息融合、無線傳感器網絡等。

陸文駿，解放軍炮兵學院講師。研究方向為無線傳感器網絡。