介紹
哈佛大學(xué)的Brad Karp和H. T. Kung在大量的研究分析之后，提出了適合移動自組網(wǎng)的貪婪周邊無狀態(tài)路由協(xié)議 (Greedy Perimeter Stateless Routing)，縮寫GPSR。論文鏈接
?貪婪周邊無狀態(tài)路由協(xié)議主要包括轉(zhuǎn)發(fā)數(shù)據(jù)包的兩類方法:貪婪轉(zhuǎn)發(fā)和周邊轉(zhuǎn)發(fā)。貪婪轉(zhuǎn)發(fā)是該算法的核心部分。簡單來說，貪婪轉(zhuǎn)發(fā)方法就是尋找最接近目的位置的一跳鄰節(jié)點(diǎn)，然后向此節(jié)點(diǎn)轉(zhuǎn)發(fā)數(shù)據(jù)包的方法；周邊轉(zhuǎn)發(fā)方法是在貪婪轉(zhuǎn)發(fā)模式的補(bǔ)充，解決在執(zhí)行貪婪轉(zhuǎn)發(fā)失敗的區(qū)域進(jìn)行數(shù)據(jù)分組轉(zhuǎn)發(fā)的困境。
?GPSR的優(yōu)勢在于，只需要保存一跳鄰節(jié)點(diǎn)的狀態(tài)信息，路由開銷?。徊⑶译S著網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)的增加，比距離向量路由（DV）或鏈路狀態(tài)路由(LS)有更強(qiáng)的擴(kuò)展性。即使網(wǎng)絡(luò)內(nèi)節(jié)點(diǎn)移動頻繁，GPSR協(xié)議都可以基于一跳鄰節(jié)點(diǎn)的信息，迅速找到替代路由。
GPSR用信標(biāo)廣播來傳播本地位置信息。
信標(biāo)廣播
信標(biāo)的基本組成
每個節(jié)點(diǎn)周期性廣播信標(biāo)數(shù)據(jù)包，其中主要組成是唯一標(biāo)識和位置信息。其中位置信息是被編碼為兩個32位的浮點(diǎn)數(shù)，分別表示該節(jié)點(diǎn)的橫（經(jīng)度）、縱（緯度）坐標(biāo)值。信標(biāo)發(fā)送周期默認(rèn)為B。但是為了減少和鄰節(jié)點(diǎn)產(chǎn)生信號沖突，信標(biāo)發(fā)送周期隨機(jī)抖動50%，即信標(biāo)發(fā)送周期將均勻分布在區(qū)間[0.5B，1.5B]。接收到信標(biāo)廣播的鄰節(jié)點(diǎn)，只需要將接收到的標(biāo)識和位置信息保存到路由表。則路由表保存了節(jié)點(diǎn)的一跳鄰居節(jié)點(diǎn)的信息。路由表的數(shù)據(jù)會被用來做下一跳路由決策。
?而路由表內(nèi)的路由信息也會被刪除。當(dāng)沒有收到鄰節(jié)點(diǎn)的路由信息的時間間隔超過T，則可以認(rèn)為此鄰居路由節(jié)點(diǎn)發(fā)送故障或者本節(jié)點(diǎn)已經(jīng)不在此鄰居節(jié)點(diǎn)的信號輻射范圍，則將該鄰居節(jié)點(diǎn)從路由表里面刪除。在GPSR協(xié)議中，T=4.5B，即最大信標(biāo)發(fā)送周期的三倍。
信標(biāo)的局限性
由于節(jié)點(diǎn)的移動性，在信標(biāo)發(fā)送周期中，路由表里的位置信息可能不是最新的。這可能是因為：1.老的節(jié)點(diǎn)可能離開信號覆蓋范圍；2.新的節(jié)點(diǎn)可能進(jìn)入信號覆蓋范圍；3.獲取位置的精準(zhǔn)度可能會下降等等。
?從這些原因來看，節(jié)點(diǎn)間的相對移動速率、節(jié)點(diǎn)的信號輻射范圍決定了路由表是否準(zhǔn)確，也代表了信標(biāo)發(fā)送周期是否合適于此網(wǎng)絡(luò)環(huán)境。數(shù)據(jù)分組轉(zhuǎn)發(fā)需要保證一跳范圍內(nèi)的網(wǎng)絡(luò)拓?fù)錉顟B(tài)是最新的，因為沒有任何可用的路由轉(zhuǎn)發(fā)策略來處理轉(zhuǎn)發(fā)節(jié)點(diǎn)不知道一跳或多跳臨節(jié)點(diǎn)拓?fù)湫畔⒌那闆r。這是數(shù)據(jù)包轉(zhuǎn)發(fā)的最低標(biāo)準(zhǔn)。
信標(biāo)優(yōu)化
在GPSR的實(shí)現(xiàn)中，采取了以下辦法減少信標(biāo)開銷：
?(1) 在節(jié)點(diǎn)轉(zhuǎn)發(fā)的所有數(shù)據(jù)包中附帶了本地節(jié)點(diǎn)的位置信息
?(2) 設(shè)置所有節(jié)點(diǎn)的網(wǎng)絡(luò)接口運(yùn)行在混雜模式
?使用了以上措施，在信號輻射范圍內(nèi)的所有節(jié)點(diǎn)都可以接收到該節(jié)點(diǎn)的位置信息。因為位置信息只需要十二字節(jié)的開銷，所有的數(shù)據(jù)包都可以攜帶信標(biāo)。任何節(jié)點(diǎn)發(fā)送出一個數(shù)據(jù)包后，可以將內(nèi)部信標(biāo)定時器重新開始。這種優(yōu)化策略減少了在網(wǎng)絡(luò)轉(zhuǎn)發(fā)數(shù)據(jù)包區(qū)域內(nèi)的信標(biāo)流量。
GPSR協(xié)議詳解（2）——貪婪轉(zhuǎn)發(fā)
GPSR協(xié)議詳解（3）——周邊轉(zhuǎn)發(fā)
