基于地理位置的無(wú)線傳感器網(wǎng)絡(luò)路由協(xié)議研究進(jìn)展

摘要：在分類總結(jié)近年來(lái)提出的各種具有代表性的基于地理位置信息的路由協(xié)議的基礎(chǔ)上，分析了現(xiàn)有的下一跳節(jié)點(diǎn)選擇策略存在的不足，著重討論了貪婪路由算法中局部最優(yōu)化問(wèn)題的解決方法，指出了目前基于地理位置信息的無(wú)線傳感器網(wǎng)絡(luò)路由協(xié)議亟待解決的問(wèn)題。

關(guān)鍵詞：無(wú)線傳感器網(wǎng)絡(luò)；地理位置；局部最優(yōu)化問(wèn)題；貪婪路由

中圖分類號(hào)：TP393．04文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1001－3695(2008)01－0018－04

無(wú)線傳感器網(wǎng)絡(luò)是由大量集成有信息采集、數(shù)據(jù)處理和無(wú)線通信等功能的節(jié)點(diǎn)通過(guò)無(wú)線通信的方式組成的多跳自組織網(wǎng)絡(luò)。其旨在協(xié)作地感知、采集和處理網(wǎng)絡(luò)覆蓋區(qū)域中感知對(duì)象的信息，讓觀察者知道何時(shí)何地發(fā)生何種事件[1]。無(wú)線傳感器網(wǎng)絡(luò)中，很多應(yīng)用需要用到地理位置信息。例如，在大面積環(huán)境探測(cè)中需要知道感興趣事件發(fā)生的地點(diǎn)；森林火災(zāi)災(zāi)情監(jiān)測(cè)中，需要知道火災(zāi)發(fā)生的地域；在軍事戰(zhàn)場(chǎng)態(tài)勢(shì)監(jiān)測(cè)中，不僅要及時(shí)了解戰(zhàn)場(chǎng)各種事件發(fā)生與否，同時(shí)也要知道該事件發(fā)生的地域，以便迅速采取有效行動(dòng)。無(wú)線傳感器網(wǎng)絡(luò)中所感知的信息具有地域性。地理位置信息服務(wù)具有很重要的作用；同時(shí)地理位置信息作為路由選擇的依據(jù)，對(duì)數(shù)據(jù)的轉(zhuǎn)發(fā)具有很強(qiáng)的導(dǎo)向性。

無(wú)線傳感器網(wǎng)絡(luò)路由協(xié)議負(fù)責(zé)尋找一條傳輸路徑，將數(shù)據(jù)分組從數(shù)據(jù)源節(jié)點(diǎn)通過(guò)網(wǎng)絡(luò)多跳轉(zhuǎn)發(fā)至目標(biāo)節(jié)點(diǎn)。國(guó)內(nèi)外已經(jīng)在這個(gè)方面做了許多工作，并取得了一定的成果，相繼提出了flooding、gossiping[2]、SPIN[3]、directed diffusion[4]、rumor[5]、LEACH[6]及從Ad hoc網(wǎng)繼承過(guò)來(lái)經(jīng)過(guò)改進(jìn)的DSDV[7]、AODV[8]、DSR[9]等協(xié)議。這些協(xié)議大多是通過(guò)路由探測(cè)包獲得網(wǎng)絡(luò)中節(jié)點(diǎn)之間的連接關(guān)系和鏈路特性來(lái)確定路由并存儲(chǔ)路由表。基于鏈路狀態(tài)建立的端到端的路由會(huì)因路由中的一個(gè)或幾個(gè)節(jié)點(diǎn)的失效、移動(dòng)而經(jīng)常中斷，需要不斷地進(jìn)行路由維護(hù)。它不適應(yīng)網(wǎng)絡(luò)拓?fù)鋭?dòng)態(tài)變化快的情況。層次化路由策略是局部的先應(yīng)式路由與全局的反應(yīng)式路由的結(jié)合，以期達(dá)到提高數(shù)據(jù)傳輸效率和網(wǎng)絡(luò)可擴(kuò)展性的目的。但是，盡管融合了上述兩種路由機(jī)制，它仍然需要維護(hù)那些正在使用的端到端的路由信息，所能承受的網(wǎng)絡(luò)動(dòng)態(tài)變化也有限。

基于地理位置信息的路由協(xié)議能夠很好地解決上述問(wèn)題。隨著定位技術(shù)的發(fā)展，節(jié)點(diǎn)可以方便地獲得本身、鄰節(jié)點(diǎn)及目標(biāo)節(jié)點(diǎn)的地理位置信息。節(jié)點(diǎn)利用這些位置信息，避免路由探測(cè)包的盲目泛洪，進(jìn)行有效的路由發(fā)現(xiàn)和路由維護(hù)，甚至可以基于無(wú)狀態(tài)的分布式的非端到端的數(shù)據(jù)轉(zhuǎn)發(fā)。其中以地理位置信息為基礎(chǔ)的貪婪路由算法在整個(gè)數(shù)據(jù)傳輸中不需要建立端到端的基于全局鏈路狀態(tài)的路由，不需要存儲(chǔ)路由信息表，也不需要發(fā)送路由更新信息，只要求網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)準(zhǔn)確地存儲(chǔ)周?chē)徆?jié)點(diǎn)的狀態(tài)信息即可節(jié)省能量的消耗，降低節(jié)點(diǎn)的內(nèi)存、處理要求；同時(shí)能提供很好的數(shù)據(jù)傳輸保證，具有良好的網(wǎng)絡(luò)可擴(kuò)展性和魯棒性。

近年來(lái)，已有一些學(xué)者開(kāi)展了基于地理位置信息的路由協(xié)議方面的研究工作，并取得了一定的進(jìn)展。

1前提條件:位置服務(wù)

基于地理位置路由協(xié)議的實(shí)施要基于以下三個(gè)前提條件：節(jié)點(diǎn)知道自己的地理位置；節(jié)點(diǎn)知道所有一跳鄰節(jié)點(diǎn)的地理位置信息；節(jié)點(diǎn)能夠獲得目標(biāo)節(jié)點(diǎn)的地理位置。一般可以通過(guò)GPS及各種定位算法來(lái)獲得本節(jié)點(diǎn)的地理位置；節(jié)點(diǎn)間通過(guò)信標(biāo)交換可獲得所有一跳鄰節(jié)點(diǎn)的地理位置信息；最后一個(gè)前提條件是整個(gè)基于地理位置信息路由協(xié)議的關(guān)鍵所在，也是難點(diǎn)所在。對(duì)于目標(biāo)節(jié)點(diǎn)靜止的網(wǎng)絡(luò)系統(tǒng)來(lái)說(shuō)，可通過(guò)目標(biāo)節(jié)點(diǎn)的一次性泛洪廣播來(lái)通告所有節(jié)點(diǎn)；對(duì)于目標(biāo)節(jié)點(diǎn)運(yùn)動(dòng)的情況，需要通過(guò)位置服務(wù)來(lái)獲取目標(biāo)節(jié)點(diǎn)的地理位置信息。其中比較典型的位置服務(wù)算法有DREAM[10]、GLS[11]、virtual homezone[12]、quorum based location service[13]。在DREAM算法中，每個(gè)移動(dòng)節(jié)點(diǎn)均要維護(hù)一個(gè)位置信息的數(shù)據(jù)庫(kù)，記錄網(wǎng)絡(luò)中各個(gè)移動(dòng)節(jié)點(diǎn)的位置信息。每個(gè)節(jié)點(diǎn)周期性地接收來(lái)自其他移動(dòng)節(jié)點(diǎn)的hello報(bào)文，更新自己的位置信息數(shù)據(jù)庫(kù)。DREAM的定位性和魯棒性最強(qiáng)，但擴(kuò)展性差，不適用于大規(guī)模的無(wú)線傳感器網(wǎng)絡(luò)。GLS算法是一種新的跟蹤移動(dòng)節(jié)點(diǎn)位置的分布式位置服務(wù)。通過(guò)與地理轉(zhuǎn)發(fā)的結(jié)合，GLS可以很好地?cái)U(kuò)展到大規(guī)模的無(wú)線傳感器網(wǎng)絡(luò)。每個(gè)節(jié)點(diǎn)周期性地向小部分節(jié)點(diǎn)(它的server)發(fā)送更新包，報(bào)告其當(dāng)前位置。由于GLS采用分布式位置服務(wù)器，并不指定特定的節(jié)點(diǎn)作為服務(wù)器，某一節(jié)點(diǎn)出錯(cuò)不會(huì)對(duì)整個(gè)網(wǎng)絡(luò)造成太大影響。GLS也具有很強(qiáng)的擴(kuò)展性。

2地理位置路由協(xié)議分類

根據(jù)節(jié)點(diǎn)在發(fā)送數(shù)據(jù)前是否需要建立路由，可以將基于地理位置信息的路由協(xié)議分為位置輔助路由協(xié)議和基于位置信息的路由協(xié)議兩類。其中基于位置信息的路由協(xié)議又可以分為定向區(qū)域泛洪和貪婪路由算法，如圖1所示。

2．1位置輔助路由協(xié)議

位置輔助路由算法與DSDV、AODV、DSR的區(qū)別在于，路由請(qǐng)求分組的發(fā)送不需要進(jìn)行全面泛洪，而是在地理位置信息的導(dǎo)向下進(jìn)行有限制的區(qū)域性泛洪，增強(qiáng)路由發(fā)現(xiàn)的目標(biāo)性，減少了大量無(wú)用分組的傳遞，是基于路由請(qǐng)求分組全網(wǎng)泛洪協(xié)議的改進(jìn)。其典型算法為L(zhǎng)AR[14]。該算法源節(jié)點(diǎn)S通過(guò)位置服務(wù)獲得目標(biāo)節(jié)點(diǎn)D在t0時(shí)刻的位置L：(Xd，Yd)和平均移動(dòng)速度V，于是可以估計(jì)出t1時(shí)刻D出現(xiàn)的區(qū)域。該區(qū)域是一個(gè)以(Xd，Yd)為中心，以r=v(t1-t0)為半徑的圓，稱為期望域。根據(jù)期望域就可以限制路由搜索在一定的區(qū)域內(nèi)，這個(gè)區(qū)域稱為尋找域。只有尋找域內(nèi)的節(jié)點(diǎn)才轉(zhuǎn)發(fā)路由請(qǐng)求分組，從而減少路由尋找的開(kāi)銷(xiāo)。如果在規(guī)定時(shí)間內(nèi)沒(méi)有找到合適的路徑，S擴(kuò)大尋找域重新發(fā)送路由請(qǐng)求分組。隨著尋找域的擴(kuò)大，路由發(fā)現(xiàn)的可能性相應(yīng)增加，當(dāng)尋找域擴(kuò)大到全網(wǎng)范圍就成了一般的泛洪算法。該算法的關(guān)鍵在于尋找域的限定。過(guò)小的尋找域?qū)⒔档吐酚砂l(fā)現(xiàn)成功的概率，出現(xiàn)無(wú)法建立路由的情況；過(guò)大的尋找域?qū)?huì)帶來(lái)過(guò)大的控制開(kāi)銷(xiāo)。文獻(xiàn)[14]中給出了限定尋找域的兩種方法。方法1的尋找域是由源節(jié)點(diǎn)S和期望區(qū)域確定的矩形，如圖2所示；方法2中，源節(jié)點(diǎn)S到目標(biāo)節(jié)點(diǎn)的距離為DISTs，如果節(jié)點(diǎn)I到目標(biāo)節(jié)點(diǎn)的距離DISTi滿足α(DISTs)+β≥ DISTi(α和β為待定參數(shù))，則節(jié)點(diǎn)I包含在尋找域內(nèi)參與路由發(fā)現(xiàn)，如圖3所示。

該協(xié)議減少了參與路由請(qǐng)求分組轉(zhuǎn)發(fā)的節(jié)點(diǎn)，但仍然是基于鏈路狀態(tài)建立的端到端的路由，對(duì)網(wǎng)絡(luò)拓?fù)鋭?dòng)態(tài)性變化快的網(wǎng)絡(luò)不太適用。

2．2基于位置信息的路由協(xié)議

基于位置信息的協(xié)議節(jié)點(diǎn)在發(fā)送數(shù)據(jù)前不需要尋找路由、不需要保存路由表，節(jié)點(diǎn)直接根據(jù)自己、鄰節(jié)點(diǎn)及目標(biāo)節(jié)點(diǎn)的位置信息制定數(shù)據(jù)轉(zhuǎn)發(fā)策略。根據(jù)轉(zhuǎn)發(fā)策略的不同，可以分為貪婪路由、定向泛洪路由和分層路由三類。在前兩種路由協(xié)議中，源節(jié)點(diǎn)將數(shù)據(jù)分組傳送給一個(gè)（貪婪路由）或多個(gè)（定向區(qū)域泛洪）距離目標(biāo)節(jié)點(diǎn)更近的鄰節(jié)點(diǎn)；分層網(wǎng)絡(luò)結(jié)構(gòu)下，網(wǎng)絡(luò)的不同層次采用不同的路由協(xié)議，在某些層次的路由轉(zhuǎn)發(fā)需要位置信息的支持。 

2．2．1定向區(qū)域泛洪

在定向區(qū)域泛洪路由協(xié)議中，節(jié)點(diǎn)將向目標(biāo)節(jié)點(diǎn)方向的所有鄰節(jié)點(diǎn)轉(zhuǎn)發(fā)數(shù)據(jù)分組。該算法具有很好的魯棒性，但是它將加重網(wǎng)絡(luò)負(fù)載。

DREAM是一種典型的定向區(qū)域泛洪路由協(xié)議。協(xié)議中源節(jié)點(diǎn)和每個(gè)中間節(jié)點(diǎn)分別計(jì)算自己到目標(biāo)節(jié)點(diǎn)的方向。基于目標(biāo)節(jié)點(diǎn)的移動(dòng)信息可以確定期望域，方法與LAR一樣。由期望域就可以確定一個(gè)夾角范圍，稱為轉(zhuǎn)發(fā)域。中間節(jié)點(diǎn)將數(shù)據(jù)分組轉(zhuǎn)發(fā)給轉(zhuǎn)發(fā)域的所有一跳鄰節(jié)點(diǎn)，直到數(shù)據(jù)分組成功遞交給目標(biāo)節(jié)點(diǎn)。該算法的關(guān)鍵就在于轉(zhuǎn)發(fā)域的確定：從S作到期望域的兩條切線，兩條切線內(nèi)即夾角[v-α，v+α]間的區(qū)域就是確定的轉(zhuǎn)發(fā)域，如圖4所示。

DREAM算法能保證無(wú)環(huán)路由，具有較好的魯棒性。每次數(shù)據(jù)分組轉(zhuǎn)發(fā)都是發(fā)送給目標(biāo)節(jié)點(diǎn)方向的多個(gè)節(jié)點(diǎn)，類似于提供了到目標(biāo)節(jié)點(diǎn)的多條路徑，某條鏈路分組的丟棄不會(huì)影響到其他鏈路上的分組。相對(duì)于位置輔助路由算法，DREAM算法控制分組中只有位置更新分組和ACK分組，攜帶信息少，并且位置更新分組發(fā)布的周期依據(jù)節(jié)點(diǎn)的移動(dòng)速度確定，控制分組的數(shù)目和傳播范圍均得到了進(jìn)一步優(yōu)化。但是，雖然限制了到目標(biāo)節(jié)點(diǎn)的泛洪范圍，在節(jié)點(diǎn)數(shù)目多、數(shù)據(jù)量大的網(wǎng)絡(luò)中，數(shù)據(jù)分組在轉(zhuǎn)發(fā)區(qū)域內(nèi)進(jìn)行泛洪，將會(huì)消耗大量的能量。

2．2．2貪婪路由算法

該類算法只需要本節(jié)點(diǎn)、所有鄰節(jié)點(diǎn)及目標(biāo)節(jié)點(diǎn)的地理位置信息，是一種僅需少量存儲(chǔ)的算法。源節(jié)點(diǎn)將數(shù)據(jù)傳給距離目標(biāo)節(jié)點(diǎn)更近的鄰節(jié)點(diǎn)，依此下去，直至目標(biāo)節(jié)點(diǎn)。對(duì)于中間節(jié)點(diǎn)S，通常會(huì)有多個(gè)鄰節(jié)點(diǎn)距離目標(biāo)節(jié)點(diǎn)更近。這些離目標(biāo)節(jié)點(diǎn)更近的鄰節(jié)點(diǎn)集合稱為N（S）。基于不同的度量標(biāo)準(zhǔn)在N（S）中選擇下一跳節(jié)點(diǎn)，所得到的貪婪算法具有不同的性能。目前主要提出的下一跳節(jié)點(diǎn)選擇策略有以下四種：a）Most nearest to destination就是從N（S）中選擇距離D最近的節(jié)點(diǎn)，如圖5中的節(jié)點(diǎn)B，從而可使到達(dá)目標(biāo)節(jié)點(diǎn)的跳數(shù)最少，減少了在節(jié)點(diǎn)中因排隊(duì)、處理而帶來(lái)的時(shí)延。如果信號(hào)能量足夠大，節(jié)點(diǎn)一跳傳輸范圍的半徑將越大。但是半徑越大，節(jié)點(diǎn)相互干擾的可能性越大，同時(shí)也帶來(lái)了較大的能量消耗。由于所選擇節(jié)點(diǎn)處于通信的邊緣，它的移動(dòng)極易造成路由的中斷。b）針對(duì)這一問(wèn)題，文獻(xiàn)[15]提出了另外一種機(jī)制，即most nearest within radius。在這種機(jī)制下，節(jié)點(diǎn)S從N（S）中選擇距離自己最近的鄰節(jié)點(diǎn)作為下一跳節(jié)點(diǎn)，如圖5中的節(jié)點(diǎn)A，從而降低了節(jié)點(diǎn)間相互干擾的可能性。這種算法存在的缺點(diǎn)就是常常出現(xiàn)離中間節(jié)點(diǎn)S非常近的節(jié)點(diǎn)被選中，增加了到目標(biāo)節(jié)點(diǎn)的跳數(shù)。它雖然減少了通信能量消耗，但是大大增加了通信的跳數(shù)。c）Compass routing[16]提出另一種選擇機(jī)制。從N（S）中選擇節(jié)點(diǎn)F，使得∠FSD最小，從而可以縮小數(shù)據(jù)分組傳送的范圍。但該選擇策略會(huì)出現(xiàn)環(huán)路由[17]。d）為了克服這一缺點(diǎn)，文獻(xiàn)[18]提出了一種randomized compass路由算法。該算法將中間節(jié)點(diǎn)與目標(biāo)節(jié)點(diǎn)的連線分為兩側(cè)區(qū)域，隨機(jī)地從N（F）中選取一側(cè)區(qū)域中角度最小的節(jié)點(diǎn)作為下一跳節(jié)點(diǎn)。文獻(xiàn)[19]中所選取的點(diǎn)如圖5中的節(jié)點(diǎn)E，使得向目標(biāo)節(jié)點(diǎn)方向邁進(jìn)的步進(jìn)最大。該算法具有無(wú)環(huán)路的特點(diǎn)。

a）貪婪路由算法的優(yōu)點(diǎn)。無(wú)須維護(hù)全局網(wǎng)絡(luò)的鏈路狀態(tài)信息，每個(gè)節(jié)點(diǎn)只需要知道周?chē)徆?jié)點(diǎn)的位置信息；每一次轉(zhuǎn)發(fā)都是局部決策，可以進(jìn)行無(wú)狀態(tài)的完全分布式的非端到端的數(shù)據(jù)轉(zhuǎn)發(fā)；不需要存儲(chǔ)路由信息表，也不需要發(fā)送路由更新信息，只要求準(zhǔn)確地存儲(chǔ)周?chē)徆?jié)點(diǎn)的狀態(tài)信息即可，不但節(jié)省了能量的消耗，同時(shí)也降低了節(jié)點(diǎn)的內(nèi)存、處理要求；提供很好的數(shù)據(jù)傳輸保證，具有良好的網(wǎng)絡(luò)可擴(kuò)展和魯棒性。

b）貪婪路由算法缺點(diǎn)。在地理環(huán)境因素的影響和網(wǎng)絡(luò)節(jié)點(diǎn)密度低的情況下，會(huì)出現(xiàn)節(jié)點(diǎn)找不到距離目標(biāo)節(jié)點(diǎn)更近的鄰節(jié)點(diǎn)來(lái)作為下一跳節(jié)點(diǎn)的現(xiàn)象，這種情況稱為局部最優(yōu)化問(wèn)題，也稱為通信空洞。第3章將對(duì)該問(wèn)題的解決方法進(jìn)行總結(jié)闡述。目前的下一跳選擇策略所選擇的節(jié)點(diǎn)不一定滿足數(shù)據(jù)傳輸?shù)腝oS要求，同時(shí)能量的消耗也不平衡。改進(jìn)方法是在基于地理貪婪的背景下，通過(guò)概率轉(zhuǎn)發(fā)、隨機(jī)選取、競(jìng)爭(zhēng)轉(zhuǎn)發(fā)等方法選擇下一跳節(jié)點(diǎn)的方法均衡傳輸業(yè)務(wù)，避免擁塞的發(fā)生和能量消耗不平衡的現(xiàn)象。通過(guò)狀態(tài)最佳門(mén)限過(guò)濾，優(yōu)先選擇時(shí)延低、傳輸速率高、能量狀態(tài)好的節(jié)點(diǎn)作為下一跳節(jié)點(diǎn)，保證數(shù)據(jù)分組所經(jīng)歷的路徑具有一定的可靠性和實(shí)時(shí)性。

2．3分層路由算法[20]

分層路由可以減少網(wǎng)格中節(jié)點(diǎn)處理事件的復(fù)雜度，其擴(kuò)展性好，適合大規(guī)模網(wǎng)絡(luò)。典型的基于位置信息的分層路由算法有終端路由和網(wǎng)格路由，這兩種算法都是基于兩層路由。其中一層采用基于位置信息的路由協(xié)議。

2．3．1終端路由(terminodes routing)[20，21]

該協(xié)議結(jié)合了TLR(terminode local routing)和TRR(terminode remote routing)兩種路由算法。 TLR使用距離矢量信息確定路由并轉(zhuǎn)發(fā)數(shù)據(jù)分組，但是分組轉(zhuǎn)發(fā)的范圍(跳數(shù))有限，其上限稱為本地半徑。距離節(jié)點(diǎn)S的跳數(shù)不大于本地半徑的所有節(jié)點(diǎn)都是S的TLR可達(dá)節(jié)點(diǎn)。對(duì)于TLR算法不可到達(dá)的節(jié)點(diǎn)，采用TRR算法轉(zhuǎn)發(fā)數(shù)據(jù)分組。TRR類似于源路由協(xié)議，源節(jié)點(diǎn)給出一個(gè)到目標(biāo)節(jié)點(diǎn)的路由估計(jì)。它由一系列的anchor來(lái)標(biāo)志，在源節(jié)點(diǎn)發(fā)送的每一個(gè)數(shù)據(jù)分組的包頭中攜帶一個(gè)anchor列表。數(shù)據(jù)分組將沿著anchor標(biāo)志的路徑傳輸。通過(guò)結(jié)合TRR和TLR可避免路由環(huán)路。該協(xié)議的分組遞交成功率和路由開(kāi)銷(xiāo)均比DSR協(xié)議有所改進(jìn)。每個(gè)節(jié)點(diǎn)在轉(zhuǎn)發(fā)數(shù)據(jù)分組時(shí)僅依靠本節(jié)點(diǎn)或其他少數(shù)節(jié)點(diǎn)的信息，因此該協(xié)議可擴(kuò)展性好。

2．3．2網(wǎng)格路由(grid routing)[20，22]

在grid中，網(wǎng)絡(luò)的覆蓋區(qū)域被劃分為小的方形區(qū)域，每個(gè)區(qū)域稱為一個(gè)網(wǎng)格。每個(gè)網(wǎng)格中選擇一個(gè)節(jié)點(diǎn)作為該網(wǎng)格所有節(jié)點(diǎn)的群首(leader)，負(fù)責(zé)轉(zhuǎn)發(fā)數(shù)據(jù)分組。在每個(gè)網(wǎng)格中，節(jié)點(diǎn)運(yùn)行群首選擇協(xié)議來(lái)維護(hù)該網(wǎng)格的群首。以往的路由協(xié)議都是逐跳查找路由，grid協(xié)議采用逐網(wǎng)格查找路由的方式。它采用類似于LAR的尋找域來(lái)縮小路由搜索范圍進(jìn)行路由尋找。僅有網(wǎng)格的群首才能轉(zhuǎn)發(fā)路由請(qǐng)求分組。轉(zhuǎn)發(fā)數(shù)據(jù)分組不使用節(jié)點(diǎn)ID標(biāo)志節(jié)點(diǎn)，而是采用網(wǎng)格ID。網(wǎng)格群首的選擇是動(dòng)態(tài)的，當(dāng)原先的群首離開(kāi)該網(wǎng)格時(shí)，就會(huì)選出新的群首，以此來(lái)維護(hù)路由。相對(duì)于DSR、AODV、LAR等協(xié)議所確定的路由中有一個(gè)節(jié)點(diǎn)失效或移動(dòng)而導(dǎo)致整個(gè)路由中斷的情況不同，一個(gè)網(wǎng)格中其他節(jié)點(diǎn)可以作為后備節(jié)點(diǎn)。只要網(wǎng)格中有節(jié)點(diǎn)，經(jīng)歷該網(wǎng)格的路由就不會(huì)因單個(gè)節(jié)點(diǎn)的失效和移動(dòng)而中斷。該算法增加了路由生存時(shí)間，使得路由對(duì)節(jié)點(diǎn)的移動(dòng)不太敏感，降低了路由維護(hù)的控制開(kāi)銷(xiāo)。

3局部最優(yōu)化問(wèn)題及解決方法

在貪婪路由算法中，當(dāng)某一中間節(jié)點(diǎn)按照下一跳選擇策略在鄰節(jié)點(diǎn)中沒(méi)有找到下一跳節(jié)點(diǎn)時(shí)，便出現(xiàn)了局部最優(yōu)化現(xiàn)象，如圖6所示，即所謂的通信空洞。該節(jié)點(diǎn)成了空洞節(jié)點(diǎn)，算法得不到收斂。

為了解決這個(gè)空洞問(wèn)題，已有很多學(xué)者做了許多工作，所采用的方法主要有以下幾種：

a)增大發(fā)射功率。通過(guò)增大發(fā)射功率來(lái)增加鄰節(jié)點(diǎn)以找到符合下一跳選擇策略的下一跳節(jié)點(diǎn)，以解決局部最優(yōu)化問(wèn)題。該方法對(duì)于較小的通信空洞比較有效，但在較大空洞的情況下不能起效，并且將會(huì)消耗該節(jié)點(diǎn)大量的能量，使其過(guò)早地失效。

b）移動(dòng)節(jié)點(diǎn)填補(bǔ)。文獻(xiàn)[23]中指出局部最優(yōu)化問(wèn)題出現(xiàn)時(shí)，對(duì)于具有移動(dòng)節(jié)點(diǎn)的無(wú)線傳感器網(wǎng)絡(luò)可以通過(guò)節(jié)點(diǎn)的移動(dòng)來(lái)填補(bǔ)空洞，建立有效的前向通路。 

c）丟失分組。GEDIR[17]中一旦出現(xiàn)局部最優(yōu)化問(wèn)題，就會(huì)丟棄數(shù)據(jù)分組。該文獻(xiàn)認(rèn)為網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)不斷發(fā)生變化，局部最優(yōu)化問(wèn)題是暫時(shí)的。如果當(dāng)局部最優(yōu)化問(wèn)題出現(xiàn)頻繁，或節(jié)點(diǎn)移動(dòng)性不強(qiáng)、網(wǎng)絡(luò)拓?fù)渥兓⒖斩创嬖诘臅r(shí)間較長(zhǎng)時(shí)，這種方法會(huì)導(dǎo)致數(shù)據(jù)分組的大量丟失。

d)區(qū)域泛洪。當(dāng)節(jié)點(diǎn)遇到局部最優(yōu)化問(wèn)題時(shí)，并不丟棄數(shù)據(jù)分組，而是進(jìn)行區(qū)域性的泛洪。f GEDIR 和c GEDIR便是此類算法。局部最優(yōu)化問(wèn)題在數(shù)據(jù)轉(zhuǎn)發(fā)中出現(xiàn)較早時(shí)，該算法就演變成類似于DREAM定向泛洪算法，使更多的節(jié)點(diǎn)參與了數(shù)據(jù)轉(zhuǎn)發(fā)，數(shù)據(jù)量急劇增加，從而造成能量的大量消耗。 

e)啟動(dòng)路由尋找機(jī)制。GRA[24]啟動(dòng)路由發(fā)現(xiàn)機(jī)制搜索從空洞節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的路由。當(dāng)收到路由回復(fù)消息時(shí)，在路由表中保存該路由條目以減少將來(lái)可能發(fā)生的泛洪。局部最優(yōu)化問(wèn)題在數(shù)據(jù)轉(zhuǎn)發(fā)中出現(xiàn)較早的情況，該方法就演變成與AODV、DSR類似的基于拓?fù)涞乃惴ā＊?/p>

f）面遍歷算法。使用基于右手法則的FACE 1、FACE 2算法可以使數(shù)據(jù)分組在空洞的邊界上進(jìn)行傳送。當(dāng)?shù)竭_(dá)的節(jié)點(diǎn)距離目標(biāo)節(jié)點(diǎn)比發(fā)生局部最優(yōu)化問(wèn)題的節(jié)點(diǎn)距離目標(biāo)節(jié)點(diǎn)更近時(shí)，便恢復(fù)使用貪婪路由算法。其典型的算法有compass routing、GPSR[25]及其改進(jìn)的 GOAFR+[26]。

g）DUA（距離更新算法）。文獻(xiàn)[27]采用反向路由距離更新算法來(lái)繞過(guò)解決局部最優(yōu)化問(wèn)題。通過(guò)增加空洞節(jié)點(diǎn)的虛擬距離來(lái)滿足貪婪算法下一跳節(jié)點(diǎn)選擇策略的條件，走出空洞節(jié)點(diǎn)。

h）反饋避免算法。前面的方法c）~f)都是當(dāng)數(shù)據(jù)分組到達(dá)空洞節(jié)點(diǎn)時(shí)采取方法走出該空洞。如果能事先檢測(cè)出空洞或在傳輸過(guò)程中遇到空洞進(jìn)行標(biāo)記，使得后續(xù)的數(shù)據(jù)分組直接繞過(guò)空洞節(jié)點(diǎn)進(jìn)行傳輸，將具有降低時(shí)延的優(yōu)點(diǎn)。SPEED[28]中采用的壓力反饋路由算法、反向壓力路由變更機(jī)制用來(lái)避免擁塞和路由空洞。

i）空洞檢測(cè)算法。空洞具有邊界性和一定的形狀。無(wú)線傳感器網(wǎng)絡(luò)周期性地進(jìn)行空洞檢測(cè)，將空洞的形狀和邊界節(jié)點(diǎn)的位置信息用鏈表的方法存儲(chǔ)下來(lái)，即每一個(gè)邊界節(jié)點(diǎn)只記憶上游和下游節(jié)點(diǎn)。當(dāng)數(shù)據(jù)分組到達(dá)某一個(gè)邊界節(jié)點(diǎn)時(shí)，便利用這些事先檢測(cè)好的空洞相關(guān)信息沿著邊界繞過(guò)空洞。文獻(xiàn)[29]使用TENT方法檢測(cè)節(jié)點(diǎn)是否是空洞節(jié)點(diǎn)，使用BOUNDHOLE算法來(lái)檢測(cè)空洞邊界并存儲(chǔ)空洞邊界的相關(guān)信息，幫助數(shù)據(jù)分組有效地繞過(guò)空洞。該方法對(duì)于靜止的拓?fù)浣Y(jié)構(gòu)較穩(wěn)定的網(wǎng)絡(luò)比較適用。

4亟待解決和深入研究的問(wèn)題

利用地理位置信息的路由協(xié)議在可擴(kuò)展性、對(duì)動(dòng)態(tài)拓?fù)涞倪m應(yīng)能力和節(jié)省能量方面均優(yōu)于以往的基于鏈路連接性的協(xié)議，應(yīng)用前景廣闊。然而，對(duì)于利用地理位置信息的路由協(xié)議，仍需要進(jìn)一步關(guān)注和研究。

1）定位精度對(duì)協(xié)議性能的影響目前常用的兩種獲取位置信息的方式是GPS和利用信號(hào)強(qiáng)度估計(jì)相對(duì)坐標(biāo)。節(jié)點(diǎn)可通過(guò)GPS接收機(jī)獲得自己當(dāng)前的地理位置信息，但是具有一定的誤差，一般在15 m左右。網(wǎng)絡(luò)中的節(jié)點(diǎn)一跳通信范圍一般是幾十到一兩百米，這樣大的位置誤差會(huì)嚴(yán)重影響路由算法的正確性。同樣，在無(wú)線環(huán)境中，信號(hào)受衰減、噪聲干擾等影響，利用信號(hào)強(qiáng)度估計(jì)節(jié)點(diǎn)相對(duì)坐標(biāo)在實(shí)際應(yīng)用中受到很大限制。因此，需要分析位置誤差對(duì)協(xié)議性能的影響，并改進(jìn)協(xié)議使其能更好地適應(yīng)誤差環(huán)境。

2）信標(biāo)交換的頻率對(duì)鄰節(jié)點(diǎn)狀態(tài)信息的維護(hù)和引入的控制開(kāi)銷(xiāo)的影響目前一般采用信標(biāo)周期性地發(fā)送來(lái)維護(hù)鄰節(jié)點(diǎn)的狀態(tài)信息。這種方法對(duì)于拓?fù)浣Y(jié)構(gòu)穩(wěn)定的網(wǎng)絡(luò)來(lái)說(shuō)是行之有效的方法，但是該方法不能對(duì)動(dòng)態(tài)變化快的網(wǎng)絡(luò)作出及時(shí)準(zhǔn)確的反應(yīng)。為了能在具有移動(dòng)節(jié)點(diǎn)的主動(dòng)式傳感器網(wǎng)絡(luò)中應(yīng)用基于地理位置信息的路由協(xié)議，信標(biāo)交換的頻率應(yīng)該與節(jié)點(diǎn)的移動(dòng)速率、與周?chē)徆?jié)點(diǎn)的距離和狀態(tài)信息的動(dòng)態(tài)變化有關(guān)。如何在盡量減少控制開(kāi)銷(xiāo)的情況下準(zhǔn)確反映鄰節(jié)點(diǎn)的狀態(tài)信息還有待于更深入的研究。

3）在貪婪式路由算法中如何制定最佳的下一跳節(jié)點(diǎn)選擇策略目前提出的下一跳節(jié)點(diǎn)選擇策略存在不足。考慮了減少跳數(shù)來(lái)降低時(shí)延，但沒(méi)有考慮節(jié)省能量；或相反，考慮能量的節(jié)省卻大大犧牲了數(shù)據(jù)傳輸?shù)臅r(shí)延；同時(shí)在能量消耗上也沒(méi)有考慮進(jìn)行均衡，在QoS上沒(méi)有給予支持。如何考慮各因素，權(quán)衡各因素的影響，針對(duì)具體應(yīng)用制定下一跳節(jié)點(diǎn)選擇策略是值得進(jìn)一步研究的內(nèi)容。

4）地理位置信息與QoS相結(jié)合隨著多媒體應(yīng)用的普及，QoS路由已成為無(wú)線傳感器網(wǎng)絡(luò)研究領(lǐng)域的一個(gè)重要課題。由于無(wú)線傳感器網(wǎng)絡(luò)自身的特點(diǎn)，實(shí)現(xiàn)QoS路由是非常困難的。基于地理位置信息的路由中下一跳節(jié)點(diǎn)選擇時(shí)應(yīng)考慮下一跳節(jié)點(diǎn)的傳輸時(shí)延、傳輸帶寬等與QoS相關(guān)的狀態(tài)參量，改善現(xiàn)有QoS路由性能。目前，已提出一些位置輔助的QoS路由協(xié)議，然而在國(guó)內(nèi)外眾多研究中，尚未涉及如何在基于地理位置信息的路由協(xié)議中保證QoS。如何在節(jié)省能量的情況下，保證數(shù)據(jù)包又快又好地傳送至目標(biāo)節(jié)點(diǎn)，有待于深入研究。 

參考文獻(xiàn)：

［1］AKYILDIZ I F，SU W，SANKARASUBRAMANIAM Y，et al.Wireless sensor networks:a survey[J].Computer Networks，2002，38(4):393－422. 

[2]HEDETNIEMI S，LIESTMAN A.A survey of gossiping and broadcas ting in communication networks[J].Networks，1988，18(4):319－349.

[3]HEINZELMAN W，KULIK J，BALAKRISHNAN H.Adaptive protocols for information dissemination in wireless sensor networks[C]//Proc of the 5th Annual ACM/IEEE International Conference on Mobile Computing and Networking.Seattle:ACM Press，1999.

[4]INTANAGONWIWAT C，GOVINDAN R，ESTRIN D.Directed diffusion:a scalable and robust communication paradigm for sensor networks[C]//Proc of the 6th Annual ACM/IEEE International Conference on Mobile Computing and Networking.Boston:ACM Press，2000.

[5]BRAGINSKY D，ESTRIN D.Rumor routing algorithm for sensor networks[C]//Proc of the 1st Workshop on Sensor Networks and Applications (WSNA).Atlanta:[s.n.]，2002.

[6]HEINZELMAN W.CHANDRAKASAN A，BALAKRISHNAN H.Ener gy efficient communication protocol for wireless sensor networks[C]//Proc of International Conference on System Sciences.Hawaii:[s.n.]，2000.

[7]PERKINS C E，BHAGWAT P.Highly dynamic destination sequenced distance vector routing (DSDV) for mobile computers[C]//Proc of ACM SIGCOMM.1994:234－244. 

[8]PERKINS C E，ROYER E M.Ad hoc on demand distance vector (AODV) routing[R].[S.l.]:IETF，2002.

[9]JOHNSON D B，MALTZ D.Dynamic source routing in Ad hoc wireless networks[M]//IMIELINSKI T.Mobile Computing.[S.l.]:Kluwer Academic Publishers，1996:153 181.

[10]BASAGNI S，CHLAMTAC I，SYROTIUK V，et al.A distance routing effect algorithm for mobility (DREAM)[C]//Proc of the 5th Annual International Conference on Mobile Computing and Networking.

Dallas， Texas:[s.n.]，1998.

[11]LI Jin yang，JANNOTTI J，De COUTO D S J，et al.A scalable location service for geographic Ad hoc routing[C]//Proc of ACM MOBICOM.2000.

[12]LIU Dan dan，STOJMENOVI I，JIA Xiao hua.A scalable quorum based location service in Ad hoc and sensor networks[EB/OL].http://www.site.uottawa.ca/~ivan/quorum IJCNDS F prev.pdf.

[13]GIORDANO S，HAMIDI M.Mobility management:the virtual home region，SSC/1999/037[R].Lausanne:EPFL，1999.

[14]KO Y B，VAIDYA N H.Location aided routing (LAR) in mobile Ad hoc networks[C]//Proc ofMOBICOM.1998:66 75.

[15]HOU T C，LI V O K.Transmission range control in multihop packet radio networks[J].IEEE Trans on Communications，1986，34(1):38－44.

[16]KRANAKIS E，SINGH H，URRUTIA J.Compass routing on geometric networks[C]//Proc of the 11th Canadian Conference on Computation Geometry.1999.

[17]STOJMENOVIC I，LIN Xu.Loop free hybrid single path/flooding routing algorithms with guaranteed delivery for wireless networks[J].IEEE Trans on Parallel and Distributed Systems， 2001，12(10):1023 1032.

[18]BOSE P，MORIN P.On line routing in triangulations[C]//Proc of the 10th Annual International Symposium on Algorithms and Computation.1999.

[19]TAKAGI H，KLEINROCK L.Optimal transmission ranges for randomly distributed packet radio terminals[J].IEEE Trans on Communications，1984，32(3):246－257.

[20]于宏毅.無(wú)線移動(dòng)自組織網(wǎng)[M].北京:人民郵電出版社，2005:222－244.

[21]BLAZEVIC L J，GIORDANO S，BOUDEC J YL.Self organized terminode routing， TR DSC/2000/040[R]. Lausanne:Swiss Federal Institute of Technology，2000.

[22]LIAO W H，TSENG Y C，SHEU J P.Grid:a fully location aware routing protocols for mobile Ad hoc networks[C]//Proc of IEEE HICSS.2000.

[23]LI Q，RUS D.Sending messages to mobile users in disconnected Ad hoc wireless networks[C]//Proc of ACM MOBICOM’00.2000.

[24]JAIN R，PURI A，SENGUPTA R.Geographical routing using partial information for wireless Ad hoc networks[J].IEEE Personal Communication，2001，8(1):48－57.

[25]KARP B，KUNG H T.GPSR:greedy perimeter stateless routing for wireless networks[C]//Proc of MOBICOM.2000:243－254.

[26]KUHN F，WATTENHOFER R，ZHONG Y，et al.Geometric Ad hoc routing:theory and practice[C]//Proc of the 23rd ACM Symposium on Principles of Distributed Computing (PODC’03).2003.

[27]CHEN Shi gang，F(xiàn)AN Guang bin，CUI Jun hong.Avoid void in geographic routing for data aggregation in sensor networks[J].International Journal of Ad hoc and Ubiquitous Computing，2006，1(4):169 178.

[28]HE T，STANKOVIC J A，LU C，et al. SPEED:a stateless protocol for real time communication in sensor networks[C]//Proc of Internatio nal Conference on Distributed Computing Systems.2003.

[29]FANG Qing，GAO Jie，GUIBAS L J.Locating and bypassing routing holes in sensor networks[C]//Proc of IEEE INFOCOM’04.2004.

“本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文”