基于定位輔助的超寬帶自組網(wǎng)路由算法

1.3 路由選擇和分組轉(zhuǎn)發(fā)

對節(jié)點距離信息和網(wǎng)絡(luò)拓?fù)湫畔⒍ㄆ诟聲r，節(jié)點利用本地鏈路狀態(tài)信息計算去往網(wǎng)絡(luò)中其他節(jié)點的路由表，路由表中的每個表項都保存了到達(dá)其他節(jié)點的整條路徑信息。當(dāng)節(jié)點有分組要發(fā)送到目的節(jié)點時，將本地路由表中到達(dá)目的節(jié)點的所有中轉(zhuǎn)節(jié)點的地址信息封裝在數(shù)據(jù)分組，采用源路由的方式將分組發(fā)送到下一跳鄰居節(jié)點。中轉(zhuǎn)節(jié)點接收到該數(shù)據(jù)分組時，首先檢查分組中封裝的下一跳鄰居節(jié)點地址是否為本節(jié)點地址，如果是，記錄本節(jié)點信息并向目的節(jié)點繼續(xù)發(fā)送該分組。由于當(dāng)前網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)發(fā)生變化或其他原因?qū)е聫脑垂?jié)點到目的節(jié)點的路由不可達(dá)時，使用源路由維護(hù)機(jī)制維護(hù)到目的節(jié)點的路由。

1.4 位置信息對算法的優(yōu)化

在全網(wǎng)節(jié)點位置信息計算的基礎(chǔ)上，算法使用位置信息限制請求分組的發(fā)送范圍以降低控制開銷。本算法只允許在源節(jié)點所定義的容許轉(zhuǎn)發(fā)區(qū)域內(nèi)（請求區(qū)）的中間節(jié)點對路由請求分組進(jìn)行轉(zhuǎn)發(fā)，減少了路由請求分組洪泛的區(qū)域。請求區(qū)的定義需要在兩方面進(jìn)行權(quán)衡：(1) 較小的請求區(qū)導(dǎo)致較低的路由開銷，因為較少數(shù)量的節(jié)點被容許轉(zhuǎn)發(fā)路由請求分組；(2) 較大的請求區(qū)會增加到達(dá)目的節(jié)點的路徑，特別是在網(wǎng)絡(luò)節(jié)點稀疏的情況下。本文采用了錐形和圓形兩種請求區(qū)。(1) 錐形請求區(qū)定義為一個以源節(jié)點位置為定點、大到足夠可以包含路由請求分組應(yīng)該到達(dá)的網(wǎng)絡(luò)區(qū)域(期望區(qū))的錐形區(qū)域，該定義減小了請求區(qū)，因此減小了路由發(fā)現(xiàn)開銷，如圖5所示。(2) 圓形請求區(qū)定義為一種基于距離信息的區(qū)域。在路由請求分組中，包含源節(jié)點S和目標(biāo)節(jié)點D之間的距離dSD以及目標(biāo)節(jié)點的位置(XD,Y)。收到路由請求分組的節(jié)點I檢查dDID≤dSD+δ這個條件是否被滿足。設(shè)dID是節(jié)點I與D之間的距離；δ是一個給定的常數(shù)，如果dID≤dSD+δ，節(jié)點I就轉(zhuǎn)發(fā)路由請求分組；否則分組被丟棄。對于δ=0，只有離目標(biāo)節(jié)點的距離比源節(jié)點離目標(biāo)節(jié)點的距離還小的節(jié)點容許轉(zhuǎn)發(fā)路由分組，請求區(qū)是一個以(XD,YD)為圓心、d為半徑的圓形區(qū)域；當(dāng)δ>0，請求區(qū)增大為以(XSDD,YD)為圓心、dSD+δ為半徑的圓形區(qū)域，如圖6所示。

圖5 錐形請求區(qū)示意圖 圖6 圓形請求區(qū)示意圖
路由查找過程中，雖然使用位置信息進(jìn)行了路由期望區(qū)的限制，但如果本地節(jié)點的路由表中保存有到目的節(jié)點的路徑，則不需要進(jìn)行位置判斷；只有當(dāng)本地節(jié)點路由表中沒有到目的節(jié)點的路由的情況下，才會發(fā)起按需路由維護(hù)的過程，中轉(zhuǎn)節(jié)點接收到請求分組后判斷本節(jié)點是否位于期望區(qū)域內(nèi)，如果在期望區(qū)域內(nèi)，則轉(zhuǎn)發(fā)分組請求。另外，本算法將路由查找限制在5跳以內(nèi)，有利于減少路由發(fā)現(xiàn)的時間。

?基于定位輔助按需拓?fù)渚S護(hù)的超寬帶自組網(wǎng)路由算法