基于定位輔助的超寬帶自組網路由算法

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

1.2 網絡拓撲和路由表信息更新

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

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

1.3 路由選擇和分組轉發

對節點距離信息和網絡拓撲信息定期更新時，節點利用本地鏈路狀態信息計算去往網絡中其他節點的路由表，路由表中的每個表項都保存了到達其他節點的整條路徑信息。當節點有分組要發送到目的節點時，將本地路由表中到達目的節點的所有中轉節點的地址信息封裝在數據分組，采用源路由的方式將分組發送到下一跳鄰居節點。中轉節點接收到該數據分組時，首先檢查分組中封裝的下一跳鄰居節點地址是否為本節點地址，如果是，記錄本節點信息并向目的節點繼續發送該分組。由于當前網絡拓撲結構發生變化或其他原因導致從源節點到目的節點的路由不可達時，使用源路由維護機制維護到目的節點的路由。

1.4 位置信息對算法的優化

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

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

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