馮維 馮穗力 丁躍華 劉蘊

(華南理工大學(xué)電子與信息學(xué)院，廣東廣州510640)

近年來，跨層優(yōu)化技術(shù)［1］、基于干擾避免的保序的路由度量參數(shù)的設(shè)計、基于多射頻的多徑路由技術(shù)、各種路由分發(fā)技術(shù)成為無線多跳網(wǎng)絡(luò)路由協(xié)議研究的熱點．現(xiàn)有的無線多跳網(wǎng)絡(luò)路由協(xié)議研究大多著重于改進路由控制消息的分發(fā)機制來提高協(xié)議的可擴展性，或設(shè)計一種路由度量參數(shù)，一般僅獲得了某方面性能的提升．例如，文獻［2］中的路由協(xié)議考慮了路由算法的可擴展性，在節(jié)點定位能力下降時退出反應(yīng)式路由，從而減少路由開銷，但沒有考慮無線網(wǎng)絡(luò)干擾的影響;文獻［3］中的鏈路穩(wěn)定和能量感知路由(LAER)協(xié)議考慮了多徑和干擾，但沒有考慮路由的可擴展性，也沒有利用跨層設(shè)計的優(yōu)點;文獻［4］中算法通過估計信道的狀態(tài)信息來衡量鏈路的穩(wěn)定性，沒有考慮負(fù)載均衡和路由協(xié)議的可擴展性;文獻［5］設(shè)計的路由度量參數(shù)EXT(期望傳輸次數(shù))定義為介質(zhì)訪問控制(MAC)層能成功發(fā)送一個數(shù)據(jù)包所需要的平均次數(shù)，完全沒考慮干擾的影響;文獻［6］中的WCETT(加權(quán)累積期望傳輸時間)權(quán)值通過減少同一路徑內(nèi)使用的相同信道數(shù)來減少流路徑內(nèi)干擾，但該路由判據(jù)不保序;文獻［7］中的MIC(干擾與信道切換)權(quán)值通過評估相互干擾的鄰節(jié)點數(shù)來捕捉流路徑間的干擾，雖然考慮了干擾且路由判據(jù)保序，但不能根據(jù)信號的強弱和變化動態(tài)地捕捉流量負(fù)載;文獻［8］中的IAR(干擾感知路由)權(quán)值通過計算SNR(信噪比)和SINR(信干噪比)的比值來衡量鄰節(jié)點干擾的變化，但該路由判據(jù)仍然不保序;文獻［9］中的INC(干擾鄰節(jié)點數(shù))權(quán)值通過計算相互干擾的鏈路數(shù)來衡量干擾，但該路由判據(jù)只適用于低負(fù)載網(wǎng)絡(luò)，未能完全解決流量均衡問題;文獻［10］中的路由判據(jù)綜合考慮了干擾和負(fù)載均衡，但將負(fù)載均衡與干擾衡量參數(shù)綁定，在沒有任何干擾存在時，路由判據(jù)僅僅為信道切換代價，完全沒有考慮負(fù)載均衡．

為此，文中在最優(yōu)鏈路狀態(tài)路由(OLSR)協(xié)議的基本框架上，結(jié)合模糊視覺鏈路狀態(tài)協(xié)議族中的模糊視覺理論，提出了一種自適應(yīng)的拓?fù)淇刂菩畔⒎职l(fā)機制，以提高網(wǎng)絡(luò)的可擴展性;并在綜合考慮負(fù)載均衡、流路徑間干擾、流路徑內(nèi)干擾因素和權(quán)值保序性等因素的基礎(chǔ)上，設(shè)計了一種跨層的路由判據(jù)，提出了一種適用于大規(guī)模多射頻多信道無線多跳網(wǎng)絡(luò)的自適應(yīng)模糊視覺鏈路狀態(tài)(AHSLS)路由協(xié)議．

1 網(wǎng)絡(luò)模型和問題描述

文中以多射頻多信道無線多跳網(wǎng)絡(luò)系統(tǒng)為研究對象，系統(tǒng)有兩類節(jié)點(固定節(jié)點和可移動節(jié)點)，節(jié)點均配置全向天線．因為節(jié)點的發(fā)送功率決定了節(jié)點的傳輸范圍、干擾范圍及信干噪比．為方便計算，文中假定節(jié)點的發(fā)送功率恒為P．節(jié)點間鏈路均為雙向鏈路，且信道已采用圖著色方式預(yù)先分配．

1．1 干擾模型

干擾模型一般分為協(xié)議干擾模型和物理干擾模型［10］．協(xié)議干擾模型通過設(shè)定節(jié)點的通信范圍和干擾范圍來確定是否存在干擾;物理干擾模型從接收節(jié)點信號干擾噪聲比的角度來確定數(shù)據(jù)是否可以正確接收，考慮了干擾的疊加，更符合實際．文中基于物理干擾模型展開研究．由物理干擾模型可知，節(jié)點u和v之間能夠成功完成數(shù)據(jù)通信的條件是式(1)和(2)同時成立［11］，即

式中，SINRij為節(jié)點i收到來自節(jié)點j的信號時的信干噪比，Pi(j)為節(jié)點i收到來自j的有用信號功率，E'為鏈路(i，j)的干擾鏈路集，(x，y)為干擾鏈路集中的一條鏈路，α為信干噪比的接收門限．

1．2 問題描述

路由協(xié)議的設(shè)計要綜合考慮路由開銷的管理機制和路由判據(jù)的設(shè)計．在路由開銷管理機制上，文中將OLSR協(xié)議的高效分發(fā)(即多點中繼MPR技術(shù))和模糊視覺鏈路狀態(tài)(HSLS)協(xié)議的受限分發(fā)(即模糊視覺技術(shù))相結(jié)合，產(chǎn)生自適應(yīng)的模糊拓?fù)淇刂菩畔⑥D(zhuǎn)發(fā)機制;在路由判據(jù)的設(shè)計上，文中采用跨層優(yōu)化設(shè)計方法，結(jié)合物理層、鏈路層和路由層進行聯(lián)合設(shè)計，以反映網(wǎng)絡(luò)負(fù)載和干擾區(qū)域的變化情況．

1．2．1 多點中繼技術(shù)

OLSR協(xié)議的核心是MPR技術(shù)［12］．多點中繼的思想是通過減少同一區(qū)域內(nèi)相同路由控制分組的重復(fù)轉(zhuǎn)發(fā)次數(shù)來減少路由開銷．網(wǎng)絡(luò)中的每個節(jié)點選取其一跳鄰節(jié)點的一個子集用于轉(zhuǎn)發(fā)該節(jié)點發(fā)送的控制分組，該子集轉(zhuǎn)發(fā)的分組能夠覆蓋節(jié)點所有的兩跳鄰節(jié)點，能滿足此要求的最小子集就是MPR集．具體的MPR技術(shù)可參見文獻［12］．

1．2．2 模糊視覺理論

模糊視覺的基本思想是:兩個節(jié)點離得越遠(yuǎn)，對彼此位置的改變越不敏感［13］．基于此理論，鄰節(jié)點的路由更新要比較迅速頻繁，而遠(yuǎn)處節(jié)點的路由更新可以比較緩慢，這種更新方式導(dǎo)致節(jié)點對本地的拓?fù)漭^清晰，對遠(yuǎn)處的拓?fù)漭^模糊，從而產(chǎn)生次優(yōu)路徑，但不影響路由的可達性．基于模糊視覺的路由算法更加適用于網(wǎng)絡(luò)節(jié)點拓?fù)漕l繁變化的無線多跳網(wǎng)絡(luò)環(huán)境．文中采用最優(yōu)的HSLS協(xié)議，根據(jù)網(wǎng)絡(luò)動態(tài)變化的快慢來控制拓?fù)湎魉偷木嚯x和頻率，以達到減少路由開銷的目的．具體的HSLS協(xié)議實現(xiàn)可參見文獻［13］．

1．2．3 跨層優(yōu)化方法

文中采用了自適應(yīng)跨層優(yōu)化的方法，具體機制如下:

(1)網(wǎng)絡(luò)層中的每個節(jié)點周期為T，路由算法根據(jù)鏈路層隊列占用比、路由層業(yè)務(wù)流速率F和物理層的信道利用率等信息，分布式地更新節(jié)點權(quán)值，并將自身的權(quán)值信息通過路由控制消息傳遞廣播給其他鄰節(jié)點以更新路由表;

(2)鏈路層中的每個節(jié)點以T為周期收集其隊列占用比，并反饋到網(wǎng)絡(luò)層;

(3)物理層中的每個節(jié)點以T為周期收集其信道利用率，并反饋到網(wǎng)絡(luò)層．

2 AHSLS協(xié)議

AHSLS協(xié)議是一種先應(yīng)式的鏈路狀態(tài)路由協(xié)議，采用了新的自適應(yīng)鏈路狀態(tài)信息分發(fā)機制和跨層的基于干擾的路由判據(jù)．

AHSLS協(xié)議中節(jié)點間的交互消息有3種類型:Hello分組、拓?fù)淇刂?TC)分組和多接口申明(MID)分組，文中將這3類消息稱為鏈路狀態(tài)單元(LSUs)，協(xié)議設(shè)計的鄰節(jié)點偵聽過程、路由表計算、鏈路權(quán)值傳遞均依賴于LSUs的傳遞．文中協(xié)議的鄰節(jié)點偵聽、TC分組處理、路由表的維護過程繼承OLSR 協(xié)議［12］．

2．1 LSUs分發(fā)機制

AHSLS融合了OLSR協(xié)議的MPR機制和HSLS中基于模糊視覺理論的LSUs產(chǎn)生機制，以減少網(wǎng)絡(luò)開銷．如圖1所示，路由控制信息到達目標(biāo)節(jié)點的過程可分為三個步驟:LSUs的產(chǎn)生過程、轉(zhuǎn)發(fā)過程和接收處理過程．AHSLS協(xié)議采用SLS和HSLS相結(jié)合的算法來產(chǎn)生LSUs，LSUs的轉(zhuǎn)發(fā)由OLSR協(xié)議中被選為MPRs的節(jié)點負(fù)責(zé)，目的節(jié)點則根據(jù)接收到的LSUs來更新拓?fù)?、計算最短路徑、產(chǎn)生路由表．

圖1 LSUs的產(chǎn)生和轉(zhuǎn)發(fā)過程Fig．1 Generation and forwarding of LSUs

LSUs發(fā)送至目的節(jié)點的步驟如下:

(1)按照OLSR協(xié)議初始化網(wǎng)絡(luò)．所有節(jié)點進入初始化模式，并周期性地廣播3個Hello包，根據(jù)Hello包計算出每個節(jié)點的MPRs;然后周期性地廣播2個生命周期(TTL)為無窮的TC包和MIC包，通過每個節(jié)點的MPRs轉(zhuǎn)發(fā)至全網(wǎng)，開始鄰節(jié)點發(fā)現(xiàn)、射頻端口和信道分配情況收集以及網(wǎng)絡(luò)拓?fù)涓兄冗^程．通過網(wǎng)絡(luò)的初始化，節(jié)點得到所需的數(shù)據(jù)結(jié)構(gòu)，如鄰節(jié)點表、MPR選擇表、TC分組重復(fù)記錄表和完整的拓?fù)浔淼?，并且可根?jù)Suurbarelle算法［10］獲得到達本網(wǎng)絡(luò)最遠(yuǎn)節(jié)點的跳數(shù)d(d反應(yīng)了網(wǎng)絡(luò)的規(guī)模大小)．根據(jù)R＜d≤2R可求出滿足此條件的最大R值，即網(wǎng)絡(luò)動態(tài)變化指示值，該值可用來衡量網(wǎng)絡(luò)動態(tài)變化的快慢．

(2)網(wǎng)絡(luò)初始化后，所有節(jié)點進入模式判斷狀態(tài)．在此狀態(tài)下，鏈路狀態(tài)沒有改變，每隔T0時間節(jié)點的本地計數(shù)器加1．當(dāng)計數(shù)器大于或等于R/2時，節(jié)點認(rèn)為本地鄰節(jié)點處于相對靜止?fàn)顟B(tài)，將本節(jié)點的LSUs發(fā)送模式置為SLS模式，即節(jié)點以R為周期發(fā)送LSUs至全網(wǎng)，網(wǎng)絡(luò)中所有節(jié)點均能感知該節(jié)點周圍的鏈路狀態(tài);反之，當(dāng)計數(shù)器小于R/2時，節(jié)點認(rèn)為本地拓?fù)渥兓容^頻繁，節(jié)點進入HSLS模式，即節(jié)點通過衡量相對運動的頻繁程度來決定LSUs發(fā)送的范圍和頻率．

(3)節(jié)點在SLS模式下，如果鏈路狀態(tài)發(fā)生改變，則在周期T0到來時發(fā)送一個全局LSUs分組，并將節(jié)點的模式重新置為模式判斷狀態(tài)，進行下一輪模式的識別．

(4)節(jié)點在HSLS模式下，計數(shù)器被清0，若鏈路未發(fā)生改變，則節(jié)點每隔T0時間被喚醒一次，計算器加1，并按照如下方法決定何時發(fā)送LSU以及LSU的發(fā)送距離．設(shè)計算器值為Count，則在每個T0時間內(nèi)找出令Count=2i-1N成立的最大的i值，其中N為正奇數(shù)．若在過去的2i-1T0內(nèi)鏈路狀態(tài)發(fā)生過改變，則節(jié)點發(fā)送 TTL=2i的LSU;否則，節(jié)點不發(fā)送LSU．當(dāng)Count=d時，節(jié)點重新進入模式判斷狀態(tài)．若鏈路突然發(fā)生改變，則節(jié)點采用觸發(fā)方式馬上發(fā)送LSU，LSU的TTL值仍然按照上述方法更新．

(5)MPRs轉(zhuǎn)發(fā)由發(fā)送節(jié)點送出的LSUs．發(fā)送節(jié)點將LSUs發(fā)出之后，接收節(jié)點檢查該LSUs的TTL值，若為0則不轉(zhuǎn)發(fā);否則由發(fā)送節(jié)點的MPRs繼續(xù)轉(zhuǎn)發(fā)該LSUs，其他節(jié)點不負(fù)責(zé)轉(zhuǎn)發(fā)該LSUs．

(6)節(jié)點接收到該LSUs后根據(jù)OLSR協(xié)議中的方法來處理該LSUs．因篇幅有限，這里不再贅述．

綜上所述，采用MPR技術(shù)可減少轉(zhuǎn)發(fā)LSUs的節(jié)點數(shù)，進而減少網(wǎng)絡(luò)路由開銷;HSLS協(xié)議中的模糊視覺理論通過感知網(wǎng)絡(luò)動態(tài)變化的快慢來決定何時轉(zhuǎn)發(fā)LSUs，進一步減少了路由開銷．故AHSLS協(xié)議可大大減少路由開銷．HSLS協(xié)議雖然可以減少路由開銷，但因網(wǎng)絡(luò)的動態(tài)變化較快時，LSUs不是全網(wǎng)通發(fā)，導(dǎo)致遠(yuǎn)方的節(jié)點無法得到本地確切的網(wǎng)絡(luò)拓?fù)浜蜋?quán)值等，從而產(chǎn)生次優(yōu)路徑．不過，這對網(wǎng)絡(luò)來說是可接受的，因為節(jié)點本地的下一跳不依賴于遠(yuǎn)方的拓?fù)淝闆r，節(jié)點可以對遠(yuǎn)方的信息不敏感．

2．2 路由判據(jù)設(shè)計

一個合理的路由判據(jù)的設(shè)計需要考慮兩個方面因素:①是否能夠動態(tài)反映目標(biāo)網(wǎng)絡(luò)的物理特性;②是否具有保序性和單調(diào)性［7］．第1個因素保證了路由判據(jù)能運用到目標(biāo)網(wǎng)絡(luò)，第2個因素保證能夠高效地運用Dijkstra或者Bellman-Ford等最短路徑算法求得最優(yōu)鏈路．

2．2．1 路由選擇依據(jù)

文中的路由判據(jù)綜合考慮以下4個因素:信道利用率、緩存占有率、流路徑內(nèi)干擾和流路徑間干擾．信道利用率和緩存占有率表征了鏈路的負(fù)載;流路徑內(nèi)和路徑間干擾表征了無線信道的干擾特征，其中流路徑間干擾可導(dǎo)致某些節(jié)點無法競爭到任何帶寬資源，因為其他路徑上的流競爭該傳輸路徑附近的無線帶寬，而流路徑內(nèi)干擾會降低鏈路吞吐率．文中用能感知流路徑間干擾和鏈路負(fù)載的Lij、信道切換代價CSCi來表征路由判據(jù)Mp．設(shè)(i，j)∈p表示鏈路(i，j)在路由路徑p上，β為可調(diào)因子，則路由判據(jù)Mp可表示為

式中:等號右邊第1項代表流所經(jīng)路徑的負(fù)載感知情況，此部分權(quán)值不隨信道分配而變化;第2項代表路徑p上的信道分集特性，此部分權(quán)值是根據(jù)所選擇的不同路徑動態(tài)變化的．通過調(diào)節(jié)β可在流量負(fù)載和信道分集特性中取得折中，β越大，所選擇的路由越多地考慮路徑的信道分集特性;β越小，所選擇的路由越多地考慮路由區(qū)域內(nèi)的負(fù)載情況．Lij和CSCi的建模過程如下．

(1)Lij的建模

Lij同時表征了流路徑間干擾和流量負(fù)載因素．流路徑間干擾用干擾率IR［6］建模，IR基于物理干擾模型，通過SINR和SNR的比值來描述流路徑之間干擾的特征．定義鏈路l=(i，j)在節(jié)點j處的干擾率IRl(j)為

式中，SINRl(j)=SINRij，SNRl(j)=Pi(j)/N．

一次成功通信意味著鏈路雙方經(jīng)過一次數(shù)據(jù)發(fā)送/確認(rèn)(DATA/ACK)消息傳遞的過程，故可定義鏈路干擾率IRl為節(jié)點i和j中干擾率較小者，即

通常根據(jù)單位時間內(nèi)經(jīng)過節(jié)點的字節(jié)數(shù)來判斷負(fù)載，但由于無線鏈路的帶寬是時變的，故這種方式不再合理，而僅以信道繁忙時間［10］來判斷負(fù)載也不夠全面．為此，文中以信道利用率和隊列占用比來評估整條路徑上的鏈路和節(jié)點的繁忙程度．

信道利用率描述了網(wǎng)絡(luò)流量的大小，通過檢測周期內(nèi)信道被占用的時間與采樣時間的比值來描述，定義為

式中:Tt=T;Tb為信道被占用時間，即物理層在Tt時間內(nèi)計算得到的業(yè)務(wù)占用信道的時間．

隊列占用比描述了節(jié)點流量和節(jié)點處理能力的大小，通過檢測周期內(nèi)隊列被占用的平均長度與隊列平均總長度的比值來描述，定義為

式中，Qin為采樣周期內(nèi)隊列被占用的平均長度，Qt為緩存區(qū)總長度．

綜合考慮信道利用率和隊列占用比，就是既考慮流量負(fù)載因素，又考慮不同節(jié)點處理能力的差別，故能更容易掌握網(wǎng)絡(luò)全局的負(fù)載分布和擁塞情況，較之不考慮節(jié)點處理能力的信道繁忙時間權(quán)值函數(shù)［10］更為合理、全面．

綜上所述，文中將流路徑間干擾和流量負(fù)載感知共同建模為

注意到，當(dāng)鏈路(i，j)沒有受到鄰節(jié)點干擾時，IRij=1，Lij完全由經(jīng)過此鏈路的流量負(fù)載和節(jié)點處理能力決定．當(dāng)存在流路徑間干擾，即0＜IRij＜1時，Lij中鏈路負(fù)載評估部分Cij+Qij被IR-1ij加權(quán)，流路徑間干擾越大，IRij越小，Lij越大，選擇鏈路(i，j)的代價越大;反之，流路徑間干擾越小，Lij越小，選擇鏈路(i，j)的代價越?。摽鐚勇酚膳袚?jù)動態(tài)反映了網(wǎng)絡(luò)流量負(fù)載和路徑間干擾的變化．對于負(fù)載相同的兩跳鏈路，選路取決于干擾;對于負(fù)載不同的鏈路，由負(fù)載和干擾共同構(gòu)成選路標(biāo)準(zhǔn)．

(2)CSCi的建模

CSC［10］主要表征流路徑內(nèi)干擾．CSC的設(shè)計基于如下事實:同一流經(jīng)過路徑上相鄰鏈路使用的相同信道越多，干擾越大，丟包率和時延也越大，網(wǎng)絡(luò)能獲得的信道分集性能越少．文中對CSC的定義如下:若兩條相鄰鏈路使用相同的信道，則為CSC賦予一個大的權(quán)值;若使用不同的正交信道(文中只討論信道相互正交的情況，對于存在部分重疊的信道，可以定義0≤ω1＜ω3＜ω2，為CSC中干擾越大的鏈路賦予越大的權(quán)值)，則為CSC賦予一個小的權(quán)值，即

式中，prev(i)表示路徑p上節(jié)點i的前一個節(jié)點，CH(i)表示節(jié)點i的下一跳使用的信道，CH(prev(i))表示節(jié)點i的上一跳使用的信道．自定義權(quán)值ω1和ω2的目的是為干擾更大的節(jié)點賦予更大的權(quán)值．

綜合上述討論可知，利用流路徑內(nèi)干擾選擇路由，總權(quán)值最小的一條路徑意味著使用相同信道的概率越小，信道分集增益越大，包時延和丟包率越?。?/p>

當(dāng)然，由于干擾范圍的不同，同一路徑上的非相鄰節(jié)點可能產(chǎn)生流路徑內(nèi)干擾，較遠(yuǎn)的路徑也可能產(chǎn)生流路徑內(nèi)干擾．為簡單起見，式(9)中僅定義了路徑內(nèi)兩跳相鄰鏈路之間的干擾，可以進一步擴展．

2．2．2 保序性

保序性和單調(diào)性是運用最短路徑算法得到最小總權(quán)值路徑且保證路由無環(huán)路的充分必要條件［7］．在權(quán)值非保序的情況下，指數(shù)復(fù)雜度的算法才能夠計算出最短路徑，即使是對于規(guī)模較小的網(wǎng)絡(luò)，這種復(fù)雜度產(chǎn)生的時延也是不可以接受的［7］．因為文中提出的權(quán)值Mp為正數(shù)，所以它一定滿足單調(diào)性．進一步，文中證明Mp同時具有保序性．

定義 1(保序性)［7］設(shè)定路徑 a、b、c、c'，路徑c'和c分別為a、b的共同前向路徑和共同后向路徑，⊕代表將兩條路徑串聯(lián)，W(x)為路徑x的路由判據(jù)．當(dāng)路由判據(jù)W(a)≤W(b)時，如果W(a⊕c)≤W(b⊕c)和 W(c'⊕a)≤W(c'⊕b)成立，那么路由判據(jù)W(·)可被認(rèn)為是保序的．

如圖2所示，路徑a的權(quán)值小于路徑b的權(quán)值，路徑a和b同時串聯(lián)另一條路徑c或c'，路徑a串聯(lián)路徑c或c'后的權(quán)值仍然小于路徑b串聯(lián)路徑c或c'后的權(quán)值．

圖2 權(quán)值保序性示例［14］Fig．2 Example of isotonic metric

如圖3所示，A，B，C代表節(jié)點，弧代表節(jié)點間路徑，弧上擴號內(nèi)數(shù)字代表使用的信道，字母表示該路徑的權(quán)值，其中0＜m＜n．用代表A與B之間上弧所代表的路徑代表A與B之間下弧所代表的路徑，則W)代表路徑的權(quán)值，W⊕BC)代表路徑與路徑BC串聯(lián)后的權(quán)值．

圖3 權(quán)值不保序性示例Fig．3 Example of non-isotonic metric

在式(10)中，串聯(lián)路徑使用相同的信道，故總權(quán)值需加上一個ω2;而在式(11)中，由于串聯(lián)路徑使用不同的信道，故總權(quán)值需加上一個ω1．因為0＜m ＜n，所以 m+k＜n+k成立，但 ω2＞ω1＞0，故不能推導(dǎo)出m+k+ω2＜n+k+ω1成立，即路徑和路徑分別串聯(lián)了同一條路徑BC后，雖然W()＜W)，但不能保證W(⊕BC)＜W(⊕BC)，這不符合保序性的定義．因此，直接使用Mp是不保序的，因為這兩條串聯(lián)路徑不是相互獨立的，路由判據(jù)的計算與路徑使用的信道相關(guān)．Yang等［7］已經(jīng)證明:如果權(quán)值的非保序性是由于在已有路徑上增加某一路徑引起的，則可以使用虛擬網(wǎng)絡(luò)分解來解決此問題．據(jù)此，文中在圖3中添加虛擬節(jié)點，進行如圖4所示的虛擬網(wǎng)絡(luò)分解，并證明Mp在虛擬網(wǎng)絡(luò)中的保序性．

圖4 虛擬網(wǎng)絡(luò)分解示例Fig．4 Example of decomposition of virtual network

如圖4所示，在計算路由時相鄰節(jié)點間各增加一條虛擬鏈路B1B3和B2B3，用B1B3和 B2B3來表示因相鄰鏈路之間信道復(fù)用而引入的CSC值，節(jié)點A沒有前向鏈路，節(jié)點C沒有后向鏈路，不存在額外的CSC值，故只需要在節(jié)點B處引入虛擬鏈路．經(jīng)過虛擬網(wǎng)絡(luò)分解后，原來圖3中的權(quán)值就對應(yīng)于圖4中AB1的Mp值，AB的權(quán)值就對應(yīng)于AB2的Mp值．在虛擬網(wǎng)絡(luò)中，每條路徑之間沒有關(guān)聯(lián)，相互獨立，路徑串聯(lián)后的總權(quán)值就等于每條路徑權(quán)值之和．根據(jù)保序性定義，若在虛擬網(wǎng)絡(luò)中某兩條路徑串聯(lián)上第三條路徑之后，權(quán)值的大小、順序仍然保持，則表示該權(quán)值函數(shù)在該網(wǎng)絡(luò)具有保序性．將Mp分解到圖4所示的虛擬網(wǎng)絡(luò)中，因為只有路徑AB1B3和AB2B3才滿足兩條不同路徑分別串聯(lián)上一條共同路徑B3C的條件，所以要證明權(quán)值Mp在虛擬網(wǎng)絡(luò)中是否具有保序性，就是要證明在

成立的情況下(因為 m、n、ω2、ω1均為已知，所以式(12)成立)，

是否一定成立．如果式(13)成立，則表明Mp經(jīng)過虛擬網(wǎng)絡(luò)分解后具有保序性;反之，則不具有保序性．很明顯，路徑AB1⊕B1B3和AB2⊕B2B3串聯(lián)上共同路徑B3C后，由于路徑相互獨立，相當(dāng)于在原來的權(quán)值上分別加上一個正數(shù) k，故若式(12)成立，式(13)也一定成立．即Mp經(jīng)過虛擬網(wǎng)絡(luò)分解到虛擬網(wǎng)絡(luò)后仍然保序．由于引入了虛擬網(wǎng)絡(luò)，因而路由表的計算過程與傳統(tǒng)OLSR協(xié)議有所不同．文獻［14］中已詳細(xì)描述引入CSC后計算路由表的步驟，此處不再贅述．

2．3 多路徑擴展

多徑路由已被證明是一種均衡負(fù)載和獲得網(wǎng)絡(luò)可靠性的有效策略，這是因為從源節(jié)點到目的節(jié)點之間有多條路徑可傳輸數(shù)據(jù)，當(dāng)其中一條路徑的負(fù)載過重或中斷時，可選擇增加另一條路徑的流量或只使用另一條路徑．基于此，文中對AHSLS進行多路徑擴展，將單路徑路由擴展為兩條完全不相交的路徑路由，以提高網(wǎng)絡(luò)的可靠性．在進行多路徑擴展時，路由判據(jù)的不保序性仍然保留，故需要對實際網(wǎng)絡(luò)增加虛擬節(jié)點，進行虛擬網(wǎng)絡(luò)分解后再進行多路徑擴展．

使用Suurballe算法［10］能夠以多項式復(fù)雜度而不是傳統(tǒng)算法的指數(shù)復(fù)雜度有效地找到從源節(jié)點到目的節(jié)點的兩條總權(quán)值最小的不相交路由．因此，文中運用Suurballe算法，結(jié)合權(quán)值Mp的計算，得到從源節(jié)點到目的節(jié)點的兩條相互完全獨立的最優(yōu)與次優(yōu)路徑．如果從源節(jié)點到目的節(jié)點不存在兩條完全獨立的路徑，文中采用Dijkstra算法得到到達目的節(jié)點的單路徑，以保證單路徑可達．

在運用Suurballe算法得到從源節(jié)點到目的節(jié)點的兩條相互完全獨立的最優(yōu)與次優(yōu)路徑后，源節(jié)點將根據(jù)兩條路徑的權(quán)值比率在兩條路徑之間分配流量．如在路徑1權(quán)值為1、路徑2權(quán)值為2、總流量為3的情況下，為路徑1分配的流量為2(3×2/(1+2))，而為路徑2分配的流量為1(3×1/(1+2))，這樣處理的目的是盡量將更多的流量分配到權(quán)值更小的路徑上．而路徑總權(quán)值包含了對路徑總負(fù)載和干擾情況的綜合評估，故根據(jù)路徑的總權(quán)值比率分配流量能更好地實現(xiàn)負(fù)載均衡．

3 數(shù)值仿真和性能分析

以NS2-2．34為仿真平臺，節(jié)點物理層和MAC層采用實驗室開發(fā)的基于IEEE 802．16d構(gòu)建的多射頻多信道無線多跳網(wǎng)絡(luò)仿真系統(tǒng)，該系統(tǒng)在IEEE 802．16d Mesh 仿真平臺［15］基礎(chǔ)上根據(jù) Ramon 方案擴展了多射頻多信道的仿真環(huán)境，具體實現(xiàn)可參考文獻［16］．

具體參數(shù)設(shè)定如下:CBR長度為1kB，OFDM子載波數(shù)為256，控制時隙周期為4，每幀控制時隙數(shù)為8．仿真場景如下:在1500 m×1500 m的空間內(nèi)，有編號為0-16的、通信距離為250m的節(jié)點，其中一個節(jié)點為基站節(jié)點，每個節(jié)點配置3個射頻端口，且假設(shè)存在3個可用正交信道，信道按圖著色方式預(yù)先分配．每個節(jié)點均可移動，設(shè)置節(jié)點以20 m/s速度運動10s后靜止5s，然后繼續(xù)運動．β值可根據(jù)具體的應(yīng)用需求設(shè)置，為簡單起見，文中取β=0．5;參照文獻［14］，取 ω1=3，ω2=5．網(wǎng)絡(luò)內(nèi)共有兩個流向基站的流，每個流的發(fā)送速率為500 kb/s，仿真時間為100s，每個采樣點統(tǒng)計50次，結(jié)果取其平均值．5種協(xié)議(SRSC-SP-OLSR、MRMC-SP-OLSR、SRSC-SPAHSLS、MRMC-SP-AHSLS、CL-MRMC-MP-AHSLS)在不同可用鏈路帶寬(64、128、256、512、64、711、1067、1422、2133、2844、3 200 kb/s)下的網(wǎng)絡(luò)吞吐量、時延、丟包率和路由協(xié)議開銷的統(tǒng)計結(jié)果如圖5所示．其中，SRSC-SP-OLSR是單射頻單信道單徑的OLSR協(xié)議，MRMC-SP-OLSR是多射頻多信道單徑的OLSR協(xié)議，這兩種協(xié)議均將跳數(shù)作為路由判據(jù)，僅使用MPR技術(shù)來減少路由開銷;SRSC-SP-AHSLS是單射頻單信道單徑的AHSLS協(xié)議，MRMC-SP-AHSLS是多射頻多信道單徑的AHSLS協(xié)議，這兩種AHSLS協(xié)議也將跳數(shù)作為路由判據(jù)，聯(lián)合采用MPR技術(shù)和HSLS算法來減少路由開銷;CL-MRMC-MP-AHSLS是使用跨層權(quán)值的多射頻多信道多徑的AHSLS協(xié)議，也聯(lián)合采用MPR技術(shù)和HSLS算法來減少路由開銷．

在物理層可用鏈路帶寬增加的情況下，網(wǎng)絡(luò)由嚴(yán)重?fù)砣綆捜哂?，吞吐量先增大最后保持穩(wěn)定．SRSC-SP-OLSR和SRSC-SP-AHSLS相比，當(dāng)鏈路帶寬小于256kb/s時，由于網(wǎng)絡(luò)處于非常擁塞的狀態(tài)，大量數(shù)據(jù)包丟失，導(dǎo)致吞吐量較小，時延較長，丟包率較高．SRSC-SP-AHSLS是在SRSC-SP-OLSR的基礎(chǔ)上進一步采用HSLS算法來動態(tài)調(diào)整LSU的發(fā)送頻率和發(fā)送范圍，而不是周期性地全網(wǎng)通發(fā)，因而降低了LSU開銷，SRSC-SP-AHSLS占用的帶寬比SRSCSP-OLSR少;在網(wǎng)絡(luò)擁塞時，SRSC-SP-AHSLS的吞吐量比SRSC-SP-OLSR大，平均網(wǎng)絡(luò)時延和丟包率均較小;當(dāng)可用物理鏈路帶寬增加到能滿足流量需求時，SRSC-SP-AHSLS和SRSC-SP-OLSR的吞吐量、網(wǎng)絡(luò)時延和丟包率均趨于相同．

圖5 幾種協(xié)議的性能比較Fig．5 Performance comparison of several protocols

由于MRMC-SP-AHSLS和MRMC-SP-OLSR采用了多射頻多信道，相鄰鏈路可以同時工作在不同信道上，相隔較遠(yuǎn)的鏈路還可以信道復(fù)用，相互間不會產(chǎn)生干擾，故鏈路的可用容量增大，丟包較少，吞吐量、網(wǎng)絡(luò)時延和丟包率均明顯高于單射頻單信道協(xié)議SRSC-SP-OLSR和SRSC-SP-AHSLS．MRMC-SPAHSLS使用HSLS算法來減少路由開銷，故在網(wǎng)絡(luò)帶寬不足情況下的性能優(yōu)于MRMC-SP-OLSR．

CL-MRMC-MP-AHSLS采用了具有干擾意識的跨層路由判據(jù)，選路更合理，同時，多徑的使用使得當(dāng)物理鏈路帶寬增加至256 kb/s時，網(wǎng)絡(luò)帶寬幾乎就能滿足業(yè)務(wù)需求．由于OLSR和沒有使用跨層權(quán)值的AHSLS只根據(jù)跳數(shù)來選路，沒有捕捉鏈路的干擾和實際負(fù)載情況，而且只采用了單路徑傳輸包，因而只有在物理鏈路帶寬增加到遠(yuǎn)超過500 kb/s時，才能滿足源節(jié)點到目的節(jié)點500 kb/s帶寬的需求，導(dǎo)致其性能不及CL-MRMC-MP-AHSLS．

由于MRMC-SP-AHSLS和SRSC-SP-AHSLS采用了自適應(yīng)模糊技術(shù)，故其路由開銷比MRMC-SPOLSR和SRSC-SP-OLSR小30%左右．因為多射頻多信道路由協(xié)議需要將射頻和信道的使用情況通過每個射頻端發(fā)送至全網(wǎng)，所以MRMC-SP-AHSLS和MRMC-SP-OLSR占用的帶寬比SRSC-SP-AHSLS和SRSC-SP-OLSR多．較為特別的是，因為CL-MRMCMP-AHSLS引入了跨層權(quán)值交換的開銷，所以其路由開銷比MRMC-SP-AHSLS和SRSC-SP-AHSLS大，但因為節(jié)點運動頻繁，跨層權(quán)值開銷的增加相對于采用自適應(yīng)模糊技術(shù)節(jié)省的開銷來說較小，因而，相比于MRMC-SP-OLSR和SRSC-SP-OLSR，CL-MRMCMP-AHSLS的路由總開銷要低15%左右．

4 結(jié)語

文中針對多射頻多信道無線多跳網(wǎng)絡(luò)，提出了一種具有干擾意識的模糊自適應(yīng)路由協(xié)議機制．該機制首先采用基于MPR選擇技術(shù)和模糊視覺理論的拓?fù)淇刂菩畔⒎职l(fā)方法發(fā)送路由控制消息，以縮減拓?fù)淇刂崎_銷，然后利用跨層優(yōu)化方法設(shè)計出一種保序的路由判據(jù)，該路由判據(jù)綜合考慮了負(fù)載均衡、流路徑內(nèi)干擾和流路徑間干擾．在此基礎(chǔ)上，文中進一步運用Suurballe算法來實現(xiàn)該路由算法的多路徑擴展．仿真結(jié)果表明:文中所提算法能夠找到當(dāng)前情況下的較優(yōu)路徑，獲得比OLSR更好的網(wǎng)絡(luò)性能．

今后將結(jié)合地理位置信息的檢測，將該路由協(xié)議應(yīng)用到節(jié)點高速運動情景下，以進一步提高協(xié)議的可靠性．

［1］Shin Bongjhin，Choe Jinwoo，Kang Byoungik．Cross-layer resource allocation with multipath routing in wireless multihop and multichannel systems［J］．Journal of Communications and Networks，2011，13(3):221-231．

［2］Al-Rabayah M．A new scalable hybrid routing protocol for VANETs［J］．IEEE Transactions on Vehicular Technology，2012，61(6):2625-2635．

［3］De Rango F．Link-stability and energy aware routing protocol in distributed wireless networks［J］．IEEE Transactions on Parallel and Distributed Systems，2012，23(4):713-726．

［4］Chen Xiaoqin，Jones H M，Jayalath D．Channel-aware routing in MANETs with route handoff［J］．IEEE Transactions on Mobile Computing，2011，10(1):108-121．

［5］Douglas S J，Aguyo D，Bicket J．A high-throughput path metric for multi-hop wireless routing ［J］．Wireless Networks，2005，11(4):419-434．

［6］Draves R，Padhye J，Zill B．Routing in multi-radio multihop wireless mesh networks［C］∥Proceedings of the 10th Annual International Conference on Mobile Computing and Networking．Philadelphia:ACM，2004:114-128．

［7］Yang Y，Wang J，Kravets R．Designing routing metrics for mesh networks［C］∥Proceedings of the IEEE Workshop on Wireless Mesh Networks(WiMesh)．Atlanta:IEEE，2005:675-679．

［8］Subramanian A，Buddhikot M，Miller S．Interference aware routing in multi-radio wireless mesh networks［C］∥Proceedings of the IEEE Workshop on Wireless Mesh Networks(WiMesh)．Atlanta:IEEE，2006:55-63．

［9］Langar R，Bouabdallah N，Boutaba R．Mobility-aware clustering algorithms with interference constraints［J］．Computer Networks，2009，53(1):25-44．

［10］Thulasiraman Preetha，Chen Jiming，Shen Xuemin．Multipath routing and max-min fair QoS provisioning under interference constraints in wireless multi-hop networks［J］．IEEE Transactions on Parallel and Distributed Systems，2011，22(5):716-728．

［11］Park W-H，Bahk S．Resource management policies for fixed relays in cellular networks［J］．Computer Communications，2009，32(4):703-711．

［12］RFC 3626，Optimized link state routing protocol(OLSR)［S］．

［13］Santivanez C，Ramanathan R．Hazy sighted link state(HSLS)routing:a scalable link state algorithm ［R］．Cambridge:Raytheon BBN Technologies，2001．

［14］Yang Y，Wang J，Kravets R．Interference-aware load balancing for multihop wireless networks［R］．Illinois:Department of Computer Science，University of Illinois at Urbana-Champaign，2005．

［15］NIST．Simulation models for NS-2［EB/OL］．(2007-04-30)［2012-12-25］．http:∥www．nist．gov/itl/antd/emntg/ssm_tools．cfm．

［16］鄭堅濤．多射頻多信道無線Mesh網(wǎng)絡(luò)路由算法研究與NS-2仿真實現(xiàn)［D］．廣州:華南理工大學(xué)電子與信息學(xué)院，2011．