徐大慶，王 田

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

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

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

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

1 新協(xié)議LSTLMRP描述

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

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

圖1 傳感器及簇頭沿SPT傳數(shù)據(jù)到匯聚點

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

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

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

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

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

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

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

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

1.2 向匯聚點傳送數(shù)據(jù)

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

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

2 仿真與性能分析

2.1 仿真環(huán)境

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

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

圖2 LSTLMRP仿真環(huán)境

2.2 仿真模型

在時間T的周期內(nèi)，因為匯聚點的位置已經(jīng)改變了m次，所以LSTLMRP協(xié)議的匯聚點位置更新的平均能耗是

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

從上面仿真環(huán)境假設可以推知:

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

FLUP的平均能耗至少是:

2.3 仿真結果及性能分析

本文采用MATLAB仿真工具作仿真，仿真結果的各圖的公共參數(shù)設置如下:T=120 s；h=0.002 J；d=5 個/m2；α=3；β=0.008。為了體現(xiàn)LSTLMRP 協(xié)議與LURP協(xié)議的全部性能，我們采用了大規(guī)模的無線傳感器網(wǎng)作仿真。將式(7)代入式(4)、式(5)、式(6)作仿真可知，LSTLMRP協(xié)議的位置更新平均能耗最小，如圖3、圖4與圖5所示。并且位置更新的能耗，隨網(wǎng)絡邊長的增加而增加，如圖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目標區(qū)域的大小可以由它的半徑R表示，半徑R是一個重要參數(shù)。一方面，如果半徑太小，匯聚點不斷地從一個目標區(qū)域轉到另外一個目標區(qū)域，位置服務器及其匯聚點位置信息不得不頻繁更新。這樣消耗傳感器太多的能量，另一方面，如果半徑太大，目標區(qū)域內(nèi)的位置服務器將增加，目標區(qū)域內(nèi)的匯聚點的位置更新的能耗將增加。如圖3所示(其中R=10 m～500 m，L=500 m，v=2 m/s)，協(xié)議LURP 與協(xié)議LSTLMRP都有一個低谷，當R取適當值時，它們在時間周期內(nèi)的位置更新能量消耗為最小。所以在實際應用中，利用此性能分析模型，能得出最小能耗的R值。

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

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

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

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

并且，從表達式(1)可以看出新協(xié)議LSTLMRP與傳感器密度無關，而LURP與FLUP的位置更新能量隨傳感器密度的增加而增加。所以LSTLMRP很適合于大規(guī)?；騻鞲衅髅芏雀叩膱龊稀?/p>

3 結論

協(xié)議LSTLMRP通過建立以匯聚點為根的位置服務器的SPT，記錄移動匯聚點的當前位置；并為匯聚點建立目標區(qū)域，這樣大大地減少了移動匯聚點位置更新的平均能耗。傳感器將感知的數(shù)據(jù)沿簇內(nèi)SPT或MST先傳給簇頭，簇頭將數(shù)據(jù)收集融合后，沿位置服務器的SPT多跳傳送到匯聚點。使得傳感器傳送數(shù)據(jù)至匯聚點的能耗達到最小值，簇內(nèi)的傳感器輪流擔當簇頭及位置服務器，這樣能取得傳感器之間統(tǒng)一的能源消耗，傳感器能量消耗均勻，延長了整個網(wǎng)絡的壽命。這個協(xié)議也很適合大規(guī)?；蛎芏雀叩臒o線傳感器網(wǎng)。

［1］王殊，閻毓杰，胡富平，等.無線傳感器網(wǎng)絡的理論及應用［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，F(xiàn)ahmy 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中一種能量均衡的路由協(xié)議［J］.傳感技術學報，2009，22(2):254－257.

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

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

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

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

［13］沈玉龍，徐啟建，裴慶祺，等.基于柵格的無線傳感器網(wǎng)絡路由方法［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.