基于位置服務器樹的移動匯聚點的位置管理與路由協議*

徐大慶，王 田

(1.長沙大學信息與計算科學系，長沙410003；2.華僑大學計算機科學系，福建廈門 361021)

公共的無線傳感器網(WSN，Wireless Sensor Networks)可以由許多冗余的傳感器節點組成，每個傳感器有一定的計算、存儲與通信能力。其主要應用是感知物理環境，把感知的數據傳給匯聚點。這些節點通過無線收發器有能力相互通信。作為傳感器節點的用戶接口，匯聚點是必須的。匯聚點還可通過衛星網、無線或有線Internet服務傳送數據給用戶。

WSN的地理位置路由協議［1］使用目標節點和前向鄰居節點的位置信息決定路由。每個傳感器節點的發送范圍較小，通過其它中間傳感器，前向轉發包。在每次的前向跳躍中，傳感器節點尋找與目標位置最近的鄰居，直到當前的前向轉發節點的鄰居列表中有目標節點。在最后一跳中，鄰居傳感器節點直接發送數據包給目標節點。這些鄰居節點的路由能夠通過周期性的Hello包交流得到維護。只要傳感器節點是相對靜止，初始化每個傳感器與匯聚點的位置信息，地理路由就能被成功運用。然而這樣的路由協議存在一個普遍的問題，靠近匯聚點的傳感器節點會大大地，很快地減少它們的能量，因為它們需要往前轉發從其它許多節點發過來的給匯聚點的信息，長期這樣，減少了這些傳感器以及整個網絡的壽命。并且，如果匯聚點快速移出下個跳躍點的發送邊界，從源節點到匯聚點的前向轉發就不能正確執行，因為沒有移動匯聚點的位置更新，匯聚點不能收到最后的轉發。這樣產生一些問題，比如，不準確的目標位置產生錯誤的路由和包丟失。如果使用洪泛協議FLUP(Flooding-based Location Update Protocol)，當匯聚點移動時，其新位置必被傳到全部傳感器，對于大規模傳感器網，這樣高負載是沒有效率的。匯聚點頻繁的位置更新導致傳感器節點快速的能源消耗和無線發送沖突增加。文獻［2］推出了一個基于局部更新的路由協議LURP(Local Update Based Routing Protocol)，幫助解決這個問題。當匯聚點在一個局部區域內移動時，它只需對局部區域內的傳感器，傳播它的位置更新信息。

另外與平面路由協議［3－4］等相比，分簇路由協議［5－13］等具有拓撲管理方便、能量利用高效、數據融合簡單等優點，成為當前重點研究的路由技術。傳感器網絡的分簇路由協議的主要缺點是簇劃分算法和簇頭選舉算法比較復雜，因此現有的分簇傳感器網絡路由協議難以被實際應用。為了解決上述問題，我們提出了一個WSN的基于位置服務器樹的位置管理與路由協議LSTLMRP。

1 新協議LSTLMRP描述

假設移動匯聚點沒有能量限制，但傳感器節點有嚴格的能量限制。我們只考慮傳感器節點的能量消耗。并且，與通信相比，計算的能量消耗很小。所以我們只考慮通信的能量消耗。隨著傳感器技術的發展，傳感器的存儲能力，計算能力與通信能力將會提高，能量也將提高，簇內傳感器輪流擔當簇頭將是可行的。利用WSN節點定位機制能夠獲得各節點的位置信息。

在上述條件下，我們設計了一個新的位置管理與路由協議LSTLMRP。通過建立以匯聚點為根的位置服務器樹，接收匯聚點的位置更新，記錄匯聚點的當前位置。位置服務器也擔任簇頭，它收集融合簇內的數據后，沿著位置服務器樹將數據多跳傳給匯聚點。為了減少與平衡網絡通信負載，可以在WSN中設立多個匯聚點，如圖1所示。本文定義每個匯聚點負責一個傳感器組，一個傳感器組是具有某種屬性的相關傳感器簇的集合。每個匯聚點有唯一的標識碼。

圖1 傳感器及簇頭沿SPT傳數據到匯聚點

1.1 位置服務器樹的建立及匯聚點位置更新

(1)預先把WSN部署區域按實際需要劃分成各分區，分區用圓圈表示。傳感器按需要配置，分布在各分區內，每一分區為一簇，如圖1所示。每個簇內有一個簇頭，簇頭同時擔任位置服務器。每個匯聚點配有一個位置服務器集合，并建造相應的以匯聚點為根的最短路徑樹SPT(Shortest Path Tree)來覆蓋此集合［14］，如圖1所示。

(2)為了進一步地減少匯聚點的位置更新的代價，每個匯聚點選擇一個以它為中心的目標區域［2］，如圖2所示的圓型區域。目標區內的每個位置服務器負責管理一個到這個匯聚點的SPT局部路徑，并把收到的包轉發給匯聚點。

(3)當匯聚點在目標區域內移動時，匯聚點只向目標區內的位置服務器沿著SPT局部路徑發送位置更新。對目標區域外的簇頭，不發送位置更新，隱藏匯聚點的短距離移動。

(4)當匯聚點移出目標區域時，它將建立新的目標區域，并且觸發新的位置更新，按照本文定義的簇內的傳感器節點輪流擔任簇頭的法則，該匯聚點所管轄的傳感器組內的位置服務器(簇頭)被全部更新，它的新的位置服務器集合被建立，以匯聚點為根的新位置服務器的SPT也被構造。

(5)匯聚點用以下方式傳播位置更新給SPT上的位置服務器。當一個位置服務器LS從匯聚點S(或從SPT的上流位置服務器)收到一個更新消息，它將首先檢查S是否為它的最近匯聚點，若是最近的，LS必須局部計算以S為根的SPT，如果這個LS是SPT的葉子節點，它將停止傳播過程。否則，LS將局部決定它是否需要沿SPT轉發該更新消息給它的下級鄰居。如果LS以前從一個上級鄰居收到另一個更新消息，并且它知道這個上級鄰居有一個比S更近的匯聚點，LS將不沿樹轉發此更新。當多個匯聚點在同一個簇內時，LS只傳播來自其根的更新消息，其他的被扣押。

(6)如果匯聚點長久留在目標區域，為了平衡傳感器的負載，我們設計一個超時機制。當匯聚點留在目標區域的時間超過設定的時間時，匯聚點強制啟動所有的位置服務器更新。

傳感器節點的能量很受限制，通過匯聚點的隨機移動，網絡中的位置服務器節點隨機變化著成為它的位置服務器鄰居節點，并且簇內位置服務器的輪流擔當避免了在單個節點上過多的能量消耗，均衡了傳感器的能量消耗，延長了整個網絡的壽命。

1.2 向匯聚點傳送數據

(1)簇內路由，如圖1所示，每個傳感器直接地或通過其它節點轉發數據給它的簇頭。基本想法是讓簇內所有傳感器構成一個以簇頭為根的樹。文獻［15］展示了下面幾點:①如果在中間點處理數據融合，最小生成樹(MST，Minimal Spanning Tree)在簇內消耗最少總能量。②如果簇內中間節點沒有數據融合，則SPT消耗最少總能量。

(2)簇間路由，簇頭將數據收集融合后沿著位置服務器的以匯聚點為根的SPT多跳傳送給匯聚點。這樣利用SPT、MST，讓傳感器傳送數據至匯聚點的能耗最小。并且采用多跳傳送均衡了傳感器的能耗。

2 仿真與性能分析

2.1 仿真環境

在這一節我們比較協議LSTLMRP，LURP和FLUP的移動匯聚點位置更新的平均能耗。FLUP每次傳播匯聚點的位置更新到網絡的全部傳感器，LURP有時對一個局部區域，有時對整個網絡，傳播匯聚點的位置更新。而LSTLMRP只對匯聚點的局部或整個位置服務器樹，傳播它的位置更新。這里不要考慮簇頭的更新代價。因為簇頭的更新并不是為了移動匯聚點的位置更新，而是為了均衡傳感器之間的能耗。

我們設置一個傳感器組，由一個移動匯聚點管轄，如圖2所示。其邊長為L，劃分成L2個正方格，每個方格為一簇，簇內設有一個位置服務器(簇頭)，即有L2個位置服務器。整個區域內有N個傳感器節點分布，匯聚點的位置在時間T的周期內改變m次，目標區域的半徑為R。匯聚點移出目標區域所耗用的時間周期為t，n是目標區域內傳感器的個數。h是發送一次位置更新消息所需的平均能耗。k是目標區域內位置服務器的個數，d是傳感器密度。

圖2 LSTLMRP仿真環境

2.2 仿真模型

在時間T的周期內，因為匯聚點的位置已經改變了m次，所以LSTLMRP協議的匯聚點位置更新的平均能耗是

局部更新路由協議(LURP)［2］的位置更新平均能耗是

從上面仿真環境假設可以推知:

因為n/(πR2)=N/L2；k/(πR2)=L2/L2，并且t與R成正比；與v成反比；α是常數。另外，m與T、v成正比，β是常數。將式(3)代入式(1)、式(2)得:

FLUP的平均能耗至少是:

2.3 仿真結果及性能分析

本文采用MATLAB仿真工具作仿真，仿真結果的各圖的公共參數設置如下:T=120 s；h=0.002 J；d=5 個/m2；α=3；β=0.008。為了體現LSTLMRP 協議與LURP協議的全部性能，我們采用了大規模的無線傳感器網作仿真。將式(7)代入式(4)、式(5)、式(6)作仿真可知，LSTLMRP協議的位置更新平均能耗最小，如圖3、圖4與圖5所示。并且位置更新的能耗，隨網絡邊長的增加而增加，如圖4所示(其中R=50 m，L=1 m ～1 000 m，v=2 m/s)，也隨匯聚點移動速度的增加而增加。如圖5所示(其中R=50 m，L=500 m，v=2 m/s～30 m/s)。

LSTLMRP目標區域的大小可以由它的半徑R表示，半徑R是一個重要參數。一方面，如果半徑太小，匯聚點不斷地從一個目標區域轉到另外一個目標區域，位置服務器及其匯聚點位置信息不得不頻繁更新。這樣消耗傳感器太多的能量，另一方面，如果半徑太大，目標區域內的位置服務器將增加，目標區域內的匯聚點的位置更新的能耗將增加。如圖3所示(其中R=10 m～500 m，L=500 m，v=2 m/s)，協議LURP 與協議LSTLMRP都有一個低谷，當R取適當值時，它們在時間周期內的位置更新能量消耗為最小。所以在實際應用中，利用此性能分析模型，能得出最小能耗的R值。

圖3 以R為變量的位置更新能量消耗比較

圖4 以L為變量的位置更新能量消耗比較

圖5 以v為變量的位置更新能量消耗比較

并且容易了解R值與網絡大小的關系。當網絡大小增加時，R值也應該增加。因為網絡大小增加時，匯聚點在整個網絡的位置更新代價將增加，所以要增加R，減少在網絡發送位置更新的次數。

并且，從表達式(1)可以看出新協議LSTLMRP與傳感器密度無關，而LURP與FLUP的位置更新能量隨傳感器密度的增加而增加。所以LSTLMRP很適合于大規模或傳感器密度高的場合。

3 結論

協議LSTLMRP通過建立以匯聚點為根的位置服務器的SPT，記錄移動匯聚點的當前位置；并為匯聚點建立目標區域，這樣大大地減少了移動匯聚點位置更新的平均能耗。傳感器將感知的數據沿簇內SPT或MST先傳給簇頭，簇頭將數據收集融合后，沿位置服務器的SPT多跳傳送到匯聚點。使得傳感器傳送數據至匯聚點的能耗達到最小值，簇內的傳感器輪流擔當簇頭及位置服務器，這樣能取得傳感器之間統一的能源消耗，傳感器能量消耗均勻，延長了整個網絡的壽命。這個協議也很適合大規模或密度高的無線傳感器網。

［1］王殊，閻毓杰，胡富平，等.無線傳感器網絡的理論及應用［M］.北京:北京航空航天大學出版社，2007.73－93.

［2］Wang Guojun，Wang Tian，Jia Weijia，et al.Local Update-Based Routing Protocol in Wireless Sensor Networks with Mobile Sinks［C］//IEEE ICC 2007 proceedings.2007.3094－3099.

［3］Intanagonwiwat C，Govindan R，Estrin D，et al.Directed Diffusion for Wireless Sensor Networking［J］.IEEE/ACM Trans on Networking，2003，11(1):2－16.

［4］Heinzelman Wr，Kulik J，Balakrishnan H.Adaptive Protocols for Information Dissemination in Wireless Sensor Networks［C］//Proc of the ACM MobiCom’99.Seattle:ACM Press，1999:174－185.

［5］Heinzelman W，Chandrakasan A，Balakrishnan H.Energy-Efficient Communication Protocol for Wireless Microsensor Networks［C］//Proc of the 33rd Annual Hawaii Int’l Conf on System Sciences.Maui:IEEE Computer Society，2000.3005－3014.

［6］Manjeshwar A，Grawal D P.TEEN:A Routing Protocol for Enhanced Efficiency in Wireless Sensor Networks［C］//Proc of the 15th Parallel and Distributed ProcessingSymp.San Francisco:IEEE Computer Society，2001.2009－2015.

［7］Younis O，Fahmy S.HEED:A Hybrid，Energy-Efficient Distributed Clustering Approach for Ad-Hoc Sensor Networks［J］.IEEE Trans on Mobile Computing，2004，3(4):660－669.

［8］牟大年，王長山.WSN中一種能量均衡的路由協議［J］.傳感技術學報，2009，22(2):254－257.

［9］盧強，何熊熊，馮遠靜，等.基于競爭機制的無線傳感器網絡分簇路由協議［J］.傳感技術學報，2010，23(2):245－250.

［10］張文祥，馬銀花.基于梯度和剩余能量的WSN路由算法研究［J］.傳感技術學報，2009，22(8):1182－1185.

［11］畢曉君，張艷雙.基于移動代理的無線傳感器網絡路由算法［J］.傳感技術學報，2009，22(7):1007－1012.

［12］王寅，尚鳳軍，任東海.一種基于蟻群系統的傳感器網絡QoS路由算法［J］.傳感技術學報，2010，23(2):239－244.

［13］沈玉龍，徐啟建，裴慶祺，等.基于柵格的無線傳感器網絡路由方法［J］.通信學報，2009，30(11):96－100.

［14］Yan Yan，Zhang Baoxian，Hussein T Mouftah，et al.Hierarchical Location Service for Large Scale Wireless Sensor Networks with Mobile Sinks［C］//IEEE GLOBECOM 2007 proceedings.2007.1222－1226.

［15］Cristescu R，Beferull-Lozano B.Lossy Network Correlated Data Gathering with High-Resolution Coding［C］//IEEE IPSN Proceedings.2005.218－224.