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

1.1 算法設計思想
算法主要利用節(jié)點的位置信息將路由查找的范圍限制在一定的區(qū)間內(nèi)，以減小算法的開銷，并基于節(jié)點的位置信息產(chǎn)生網(wǎng)絡拓撲和路由表，完成分組的路由選擇和轉(zhuǎn)發(fā)過程。算法由位置信息的交換獲取和路由表的形成階段、路由選擇和分組轉(zhuǎn)發(fā)階段、路由維護階段共三部分構(gòu)成。在節(jié)點頻繁移動的情況下，節(jié)點的位置頻繁變化，導致鏈路斷開時常發(fā)生。算法利用周期更新的距離位置交換分組(DAP)信息獲得網(wǎng)絡的拓撲信息，在得到節(jié)點位置的同時維護本地網(wǎng)絡拓撲表，并根據(jù)拓撲表計算到達全網(wǎng)其他節(jié)點的最短路由。分組的轉(zhuǎn)發(fā)首先基于本地路由表中的路由信息，使用源路由轉(zhuǎn)發(fā)的模式。當鏈路變化太快，使得通過DAP實現(xiàn)網(wǎng)絡拓撲更新的速度跟不上鏈路的變化速度或其他原因?qū)е路纸M中的源路由斷開時，算法基于已有位置信息采用按需方式重新進行限制搜索范圍的路由發(fā)現(xiàn)，以減少算法開銷。由于使用UWB技術得到的是節(jié)點之間的距離信息，將其轉(zhuǎn)換為位置信息所需要進行的計算和控制消息發(fā)布會引入一定的控制開銷。

1.2 網(wǎng)絡拓撲和路由表信息更新

節(jié)點定位信息可以采用文獻[3]中所述方法獲得，包括本地路由表、網(wǎng)絡拓撲表和節(jié)點位置信息表三種信息表，分別如圖1、圖2和圖3所示。每個節(jié)點都周期廣播一張包含網(wǎng)絡中每個節(jié)點到其他鄰居節(jié)點的距離信息集的截短表－DAP表，以實現(xiàn)位置信息的交換和更新，如圖4所示。圖4中，分組長度以字節(jié)為單位；“N_鄰居1”為第1個目的節(jié)點的鄰居數(shù)；鄰居地址N_鄰居1為第一個目的節(jié)點的第N個鄰居節(jié)點。

周期性主動廣播的過程如下：(1) 網(wǎng)絡初始化時，節(jié)點間通過不斷與鄰節(jié)點交換彼此的信息以得到周圍的鏈路狀態(tài)信息。當獲得全網(wǎng)節(jié)點的拓撲連接關系以及所有相鄰節(jié)點之間的距離后，使用最小距離算法計算本地路由表。計算本節(jié)點全局坐標系坐標時，以ID號最小的節(jié)點為網(wǎng)絡的中心參考節(jié)點。(2) 節(jié)點首先將拓撲更新信息中每一項的目的節(jié)點序列號加1，節(jié)點將本節(jié)點已知的最新距離和拓撲信息廣播到鄰居節(jié)點。(3) 節(jié)點收到來自一跳鄰居節(jié)點的DAP信息后，根據(jù)分組中攜帶的距離信息和拓撲信息更新自己的本地位置信息表。若DAP信息中的目的節(jié)點序列號大于本地拓撲表中的目的節(jié)點序列號，則使用DAP信息中的相應表項更新本地拓撲表中的相應表項；否則，不更新。之后，該鄰居節(jié)點再將所知道的最新網(wǎng)絡拓撲連接和節(jié)點位置信息向其鄰居節(jié)點廣播。通過充分的信息交換后，所有節(jié)點就能夠獲得全網(wǎng)的拓撲連接和節(jié)點間的距離。節(jié)點本地拓撲表每次更新后都將重新計算本地路由表，以保證路由表中信息對拓撲變化的收斂。

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

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

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

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

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

?基于定位輔助按需拓撲維護的超寬帶自組網(wǎng)路由算法