基于位置服務(wù)器樹的移動匯聚點(diǎn)的位置管理與路由協(xié)議*

徐大慶，王 田

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

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

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

另外與平面路由協(xié)議［3－4］等相比，分簇路由協(xié)議［5－13］等具有拓?fù)涔芾矸奖恪⒛芰坷酶咝?、?shù)據(jù)融合簡單等優(yōu)點(diǎn)，成為當(dāng)前重點(diǎn)研究的路由技術(shù)。傳感器網(wǎng)絡(luò)的分簇路由協(xié)議的主要缺點(diǎn)是簇劃分算法和簇頭選舉算法比較復(fù)雜，因此現(xiàn)有的分簇傳感器網(wǎng)絡(luò)路由協(xié)議難以被實(shí)際應(yīng)用。為了解決上述問題，我們提出了一個(gè)WSN的基于位置服務(wù)器樹的位置管理與路由協(xié)議LSTLMRP。

1 新協(xié)議LSTLMRP描述

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

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

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

1.1 位置服務(wù)器樹的建立及匯聚點(diǎn)位置更新

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

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

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

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

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

(6)如果匯聚點(diǎn)長久留在目標(biāo)區(qū)域，為了平衡傳感器的負(fù)載，我們設(shè)計(jì)一個(gè)超時(shí)機(jī)制。當(dāng)匯聚點(diǎn)留在目標(biāo)區(qū)域的時(shí)間超過設(shè)定的時(shí)間時(shí)，匯聚點(diǎn)強(qiáng)制啟動所有的位置服務(wù)器更新。

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

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

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

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

2 仿真與性能分析

2.1 仿真環(huán)境

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

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

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

2.2 仿真模型

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

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

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

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

FLUP的平均能耗至少是:

2.3 仿真結(jié)果及性能分析

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

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

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

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

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

并且容易了解R值與網(wǎng)絡(luò)大小的關(guān)系。當(dāng)網(wǎng)絡(luò)大小增加時(shí)，R值也應(yīng)該增加。因?yàn)榫W(wǎng)絡(luò)大小增加時(shí)，匯聚點(diǎn)在整個(gè)網(wǎng)絡(luò)的位置更新代價(jià)將增加，所以要增加R，減少在網(wǎng)絡(luò)發(fā)送位置更新的次數(shù)。

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

3 結(jié)論

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

［1］王殊，閻毓杰，胡富平，等.無線傳感器網(wǎng)絡(luò)的理論及應(yīng)用［M］.北京:北京航空航天大學(xué)出版社，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］.傳感技術(shù)學(xué)報(bào)，2009，22(2):254－257.

［9］盧強(qiáng)，何熊熊，馮遠(yuǎn)靜，等.基于競爭機(jī)制的無線傳感器網(wǎng)絡(luò)分簇路由協(xié)議［J］.傳感技術(shù)學(xué)報(bào)，2010，23(2):245－250.

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

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

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

［13］沈玉龍，徐啟建，裴慶祺，等.基于柵格的無線傳感器網(wǎng)絡(luò)路由方法［J］.通信學(xué)報(bào)，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.