年伏寶 華江林

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

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

1 節(jié)點(diǎn)發(fā)現(xiàn)并將網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)轉(zhuǎn)化為帶有權(quán)值的有向圖

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

表1 二維矩陣描述網(wǎng)絡(luò)拓?fù)?/p>

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

2 計(jì)算本地節(jié)點(diǎn)到其他節(jié)點(diǎn)的路徑

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

2.1 主體算法結(jié)構(gòu)

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

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

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

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

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

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

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

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

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

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

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

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

4 權(quán)值模型的定義和網(wǎng)絡(luò)拓?fù)涞姆€(wěn)定性

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

W=ρ*(1+r)*P

(1)

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

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

5 改進(jìn)算法的優(yōu)點(diǎn)和不足

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

6 結(jié)束語

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