一種改進的路徑選擇算法研究*

年伏寶 華江林

(安徽新聞出版職業(yè)技術學院 安徽合肥 230601)

無線路由協(xié)議按照其發(fā)現(xiàn)和尋址方式的不同可以分文表驅動路由協(xié)議和按需驅動路由協(xié)議。它們的區(qū)別在于路徑發(fā)現(xiàn)的需求不同，表驅動路由協(xié)議會實時或者定期更新每個節(jié)點的上網(wǎng)絡拓撲表，實時計算該節(jié)點到所有節(jié)點的路徑；而按需路由協(xié)議則是在有業(yè)務傳輸需求是發(fā)起路由發(fā)現(xiàn)請求，尋找傳輸路徑。這兩類路由協(xié)議的原理和實踐表明，表驅動路由會長期占用無線信道帶寬和處理器計算負重，但是實時性好，而按需驅動路由則最大限度的降低帶寬和處理器資源消耗，而實時性就要略遜一籌，所以根據(jù)網(wǎng)絡結構和業(yè)務實時性需求，要適當?shù)倪x取路由協(xié)議。由于網(wǎng)絡節(jié)點功能的差異性和網(wǎng)絡環(huán)境的復雜性，文章研究的是一類基于時分多址(time division multiple access，TDMA)協(xié)議的無線非對稱無中心自組網(wǎng)絡，網(wǎng)絡節(jié)點比較集中，通信(數(shù)據(jù)、視頻和話音業(yè)務)頻繁。該網(wǎng)絡中路由協(xié)議的發(fā)現(xiàn)過程需要定期的在幾個時隙周期里完成，文章的重點在于根據(jù)網(wǎng)絡中各節(jié)點的鄰節(jié)點表為業(yè)務提供路徑信息，以及該鄰節(jié)點表的變化情況，建立一個路由發(fā)現(xiàn)、路徑計算模型，以達到提高帶寬利用率、實時網(wǎng)絡拓撲和降低算法復雜度的目的。

1 節(jié)點發(fā)現(xiàn)并將網(wǎng)絡拓撲結構轉化為帶有權值的有向圖

在TDMA網(wǎng)絡中，各節(jié)點會在自己的發(fā)送時隙將自身的鄰節(jié)點信息以(本地節(jié)點編號、鄰居節(jié)點編號和通信權值)的形式向周邊節(jié)點廣播，并在本地存儲鄰居節(jié)點的信息，直至廣播收斂或到達時間上限。為了加速發(fā)現(xiàn)協(xié)議的收斂，滿足無線網(wǎng)絡中繼需要，路由協(xié)議要求節(jié)點發(fā)現(xiàn)協(xié)議在規(guī)定的時間周期內(有限個TDMA時隙周期)完成，否則鄰節(jié)點信息表可能無法實時的描述當前網(wǎng)絡拓撲信息，特別是節(jié)點運動的無線網(wǎng)絡不止受節(jié)點的通信性能和距離影響，還對網(wǎng)絡所處的信道環(huán)境相對敏感。對于相對穩(wěn)定的(即網(wǎng)絡拓撲在發(fā)現(xiàn)協(xié)議收斂時間相對穩(wěn)定)網(wǎng)絡而言，在發(fā)現(xiàn)協(xié)議收斂之后，各節(jié)點需要根據(jù)其所知道的鄰節(jié)點信息，通過表1所示的二維矩陣來描述該有向圖，該步驟的算法復雜度是0(n2)，根據(jù)文章的描述對象，該矩陣描述的是一個稠密圖，文章所有的算法均以此為基礎。

表1 二維矩陣描述網(wǎng)絡拓撲

表1中，Mij表示節(jié)點j到節(jié)點i的通信權值，權值的定義直接反應了信道模型、通信業(yè)務需求以及節(jié)點功能性能等多方面信息，之后會具體描述。對于有向圖而言，Mij一般不等于Mji。一般來講，在有限次節(jié)點信息廣播之后仍然無法獲取其信息的節(jié)點，本地節(jié)點可以默認為是無法到達的，這些節(jié)點可以通過其他補充路由算法來實現(xiàn)節(jié)點通信。

2 計算本地節(jié)點到其他節(jié)點的路徑

實踐表明，無論是表驅動路由還是按需驅動路由，計算路徑算法的復雜度主要體現(xiàn)在這個步驟上，為了找到最優(yōu)的路徑，幾乎要遍歷整張圖，即時間復雜度為0(n2)。針對研究的網(wǎng)絡模型，文章算法采用基于廣度優(yōu)先搜索的方式，參考按需驅動的方式，將路徑計算分割成幾個部分，在兼顧實時性的同時，在一定程度上降低時間復雜度。

2.1 主體算法結構

(1)根據(jù)表1中描述的網(wǎng)絡拓撲，每一列表示該節(jié)點的直接鄰節(jié)點，其值表示該節(jié)點到鄰節(jié)點的通信權值。算法從源節(jié)點開始，遍歷其所有的直接鄰節(jié)點并將它們納入臨時節(jié)點池(tempNodePool，tNP)，并以結構體(preNode，metric，level，curNode)保存至全局結構體數(shù)組變量(GlobalNodePool，GNP)中，并給其已經(jīng)遍歷過的標識visited。

(2)以臨時節(jié)點池tempNodePool的節(jié)點為遍歷對象，逐個尋找其鄰節(jié)點，計算出到該節(jié)點的通信權值，如果其鄰節(jié)點遍歷標識為unvisited，更新其權值并將其納入GlobalNodePool和tempNodePool，并將其標記為visited；如果該節(jié)點為visited，而且重新計算的權值不小于GlobalNodePool中該節(jié)點的權值，表示該路徑劣于已知路徑；反之，就根據(jù)當前(preNode，metric，level，curNode)結構更新GlobalNodePool中該節(jié)點信息，并將其納入tempNodePool。另外，對于已經(jīng)在GlobalNodePool中的節(jié)點，如果其通信權值不大于tempNodePool中任意節(jié)點的通信權值，并標記其狀態(tài)為nodeReady，表示該節(jié)點的最優(yōu)路徑已經(jīng)找到，之后再遇到該節(jié)點，直接忽略。

(3)重復步驟(2)，直到下列情況發(fā)生時，終止遍歷：①tempNodePool中沒有可以繼續(xù)遍歷的節(jié)點；②遍歷次數(shù)到達網(wǎng)絡要求的中繼級數(shù)上限。

整個遍歷過程圖如圖1所示。對于一般表驅動路由算法而言，其每次網(wǎng)絡更新后，都要計算出到各個節(jié)點的完整路徑。而文章所提算法的主要思想是，將整個路徑算法盡可能分解成多個步驟，結合按需路由算法的低消耗的優(yōu)勢，在實際業(yè)務需求產(chǎn)生時，再計算出完整路徑。如此則在業(yè)務實時性允許的范圍內，降低算法的復雜度。

圖1 廣度優(yōu)先算法流程圖

2.2 主體算法優(yōu)化

從圖1可知，該次計算只是根據(jù)當前的網(wǎng)絡拓撲狀態(tài)以及網(wǎng)絡中繼級數(shù)要求，計算出源節(jié)點能到達所有節(jié)點，而并沒有計算出實際路徑，這是在綜合考慮到文章研究的無線網(wǎng)絡中的業(yè)務需求。經(jīng)過仿真分析，該步驟的算法復雜度小于o(n2)，為了降低遍歷的重復性，該算法提出了兩個規(guī)則：

(1)通過添加節(jié)點狀態(tài)來降低節(jié)點的重復查找次數(shù)。實際上對于稠密圖而言，各個節(jié)點的連通性極高，通信鏈路的可達性導致各節(jié)點會重復計算多次。所以引入節(jié)點在遍歷過程中的狀態(tài)能很大程度降低其遍歷的重復性，特別是對于平穩(wěn)網(wǎng)絡信道而言。

(2)根據(jù)中繼級數(shù)需求，降低遍歷級數(shù)，加速算法收斂。

該步驟在整個網(wǎng)絡結構完成更新時直接更新，以盡可能實時的反映網(wǎng)絡的當前結構，實際上對于通信信道相對穩(wěn)定的網(wǎng)絡而言，這是非常有利的。

3 根據(jù)業(yè)務需求計算路徑信息

上述步驟耗費整個選路算法時間復雜度的大部分時間完成了算法的大部分工作，參考按需路由的特性，文章可以將后期的尋址過程獨立出來，根據(jù)業(yè)務需求完成單播和廣播的尋址，減少一定程度的計算。在有單播業(yè)務需求時，本地節(jié)點從GNP中找到業(yè)務的目的節(jié)點，直接逆向查找，直至找到源節(jié)點，就完成了整個路徑的選取?？梢娺@個算法復雜度是小于o(n)的。至于廣播報文亦是如此，根據(jù)GNP中的level變量，從小到大依此取出，即為源節(jié)點業(yè)務廣播的路徑，以避免成環(huán)。

4 權值模型的定義和網(wǎng)絡拓撲的穩(wěn)定性

一般來講，權值模型是在綜合考慮網(wǎng)絡結構、業(yè)務需求、信道質量等諸多因素之后建立的一個相對穩(wěn)定的參數(shù)模型，其為優(yōu)化網(wǎng)絡通信性能提供了堅實的基礎和可靠的保證。如何建立權值模型不僅是多次實驗室仿真，也是外場試驗的嘗試性設計。文章為了優(yōu)化和簡化權值模型，通過仿真和對比，選取丟包率ρ，路徑級數(shù)L，網(wǎng)絡穩(wěn)定性P來確定一類比較通用的通信權值模型W來描述單跳信道質量，如式1所示：

W=ρ*(1+r)*P

(1)

式中，r代表了路徑級數(shù)等效系數(shù)，即每增加一跳中繼，其權值不僅僅單純增加相鄰兩節(jié)點的通信權值，還有相應的系數(shù)加成，以描述無線通信中減少中繼路徑長度帶來的傳輸穩(wěn)定性和網(wǎng)絡資源的消耗；ρ以系統(tǒng)內部計算為準，例如某一小段時間內的丟包率；P則是通過周期性的節(jié)點信息擴散形成的網(wǎng)路結構矩陣的變化情況來描述網(wǎng)絡的穩(wěn)定性，該值的意義一方面用來參與權值調整，另一方面也為節(jié)點信息擴散周期作為參考，即網(wǎng)絡相對穩(wěn)定時，可以拉長擴散周期，以節(jié)省網(wǎng)絡帶寬和算法計算復雜度，反之則需要縮短擴散周期，以提高網(wǎng)絡拓撲的實時反應。

網(wǎng)絡的穩(wěn)定性定義為網(wǎng)絡連接拓撲隨時間變化情況，主要包括無線信道本身受到電磁環(huán)境、空間遮擋和多徑、多普勒頻移等導致的變化和節(jié)點本身通信性能的改變，算法本身不做任何調整和補償，只是盡可能的實時反應當前的網(wǎng)絡拓撲，已確保計算出的路徑的可靠性。無線網(wǎng)絡信道的時變特性決定了網(wǎng)絡的穩(wěn)定性只是相對的，但是利用這種相對的穩(wěn)定性是可以降低算法復雜度的，所以對于激變的網(wǎng)絡處理才是整個算法的核心。根據(jù)按需路由的原理，激變網(wǎng)絡選取按需路由是可以解決路由問題的，或者減小擴散周期，根據(jù)網(wǎng)絡時變特性的相關性，針對多業(yè)務網(wǎng)絡時，這樣也是更好的辦法。見圖2。

5 改進算法的優(yōu)點和不足

文章以表驅動路由為基礎，結合按需路由中按需方式來一定程序的降低算法的平均復雜度，然后根據(jù)研究對象提出一類相對通用的通信權值模型。在測試工作中，不斷的調整各個模型的參數(shù)以期反應網(wǎng)絡本身的通信特性。試驗還發(fā)現(xiàn)，由于試驗中網(wǎng)絡節(jié)點數(shù)相對少，這種優(yōu)化情況并不明顯，只在仿真結果引入大規(guī)模的網(wǎng)絡節(jié)點時才能顯示一定的性能優(yōu)勢。針對節(jié)點信息擴散周期和權值模型的構建，節(jié)點信息擴散周期是在綜合考慮網(wǎng)絡節(jié)點拓撲的實時性、計算復雜度和擴散的收斂時間等因素決定的，要精確確定該值是需要大量的仿真和試驗測試的。至于通信權值模型則是比擴散周期更為復雜的模型，其受影響因素更多，文章也只是選取幾個模型需求的重要參數(shù)來構建。

6 結束語

綜上所述，文章在解決路徑選擇算法復雜度的問題上，對比按需驅動和表驅動的特性，提取各自的優(yōu)勢是取得了一定的效果的。然而針對這類網(wǎng)絡結構本身提出的擴散周期和權值模型的研究依舊不夠深入，而且針對各類專用無線網(wǎng)絡越來越重要的今天，這類深入研究也更有意義。