跨層自適應(yīng)模糊視覺(jué)鏈路狀態(tài)路由協(xié)議*

馮維 馮穗力 丁躍華 劉蘊(yùn)

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

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

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

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

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

1．1 干擾模型

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

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

1．2 問(wèn)題描述

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

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

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

1．2．2 模糊視覺(jué)理論

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

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

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

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

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

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

2 AHSLS協(xié)議

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(1)Lij的建模

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

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

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

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

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

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

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

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

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

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

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

(2)CSCi的建模

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

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

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

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

2．2．2 保序性

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

定義 1(保序性)［7］設(shè)定路徑 a、b、c、c'，路徑c'和c分別為a、b的共同前向路徑和共同后向路徑，⊕代表將兩條路徑串聯(lián)，W(x)為路徑x的路由判據(jù)．當(dāng)路由判據(jù)W(a)≤W(b)時(shí)，如果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同時(shí)串聯(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é)點(diǎn)，弧代表節(jié)點(diǎn)間路徑，弧上擴(kuò)號(hào)內(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)值需加上一個(gè)ω2;而在式(11)中，由于串聯(lián)路徑使用不同的信道，故總權(quán)值需加上一個(gè)ω1．因?yàn)?＜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是不保序的，因?yàn)檫@兩條串聯(lián)路徑不是相互獨(dú)立的，路由判據(jù)的計(jì)算與路徑使用的信道相關(guān)．Yang等［7］已經(jīng)證明:如果權(quán)值的非保序性是由于在已有路徑上增加某一路徑引起的，則可以使用虛擬網(wǎng)絡(luò)分解來(lái)解決此問(wèn)題．據(jù)此，文中在圖3中添加虛擬節(jié)點(diǎn)，進(jìn)行如圖4所示的虛擬網(wǎng)絡(luò)分解，并證明Mp在虛擬網(wǎng)絡(luò)中的保序性．

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

如圖4所示，在計(jì)算路由時(shí)相鄰節(jié)點(diǎn)間各增加一條虛擬鏈路B1B3和B2B3，用B1B3和 B2B3來(lái)表示因相鄰鏈路之間信道復(fù)用而引入的CSC值，節(jié)點(diǎn)A沒(méi)有前向鏈路，節(jié)點(diǎn)C沒(méi)有后向鏈路，不存在額外的CSC值，故只需要在節(jié)點(diǎn)B處引入虛擬鏈路．經(jīng)過(guò)虛擬網(wǎng)絡(luò)分解后，原來(lái)圖3中的權(quán)值就對(duì)應(yīng)于圖4中AB1的Mp值，AB的權(quán)值就對(duì)應(yīng)于AB2的Mp值．在虛擬網(wǎng)絡(luò)中，每條路徑之間沒(méi)有關(guān)聯(lián)，相互獨(dú)立，路徑串聯(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ò)中，因?yàn)橹挥新窂紸B1B3和AB2B3才滿足兩條不同路徑分別串聯(lián)上一條共同路徑B3C的條件，所以要證明權(quán)值Mp在虛擬網(wǎng)絡(luò)中是否具有保序性，就是要證明在

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

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

2．3 多路徑擴(kuò)展

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

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

在運(yùn)用Suurballe算法得到從源節(jié)點(diǎn)到目的節(jié)點(diǎn)的兩條相互完全獨(dú)立的最優(yōu)與次優(yōu)路徑后，源節(jié)點(diǎn)將根據(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)值包含了對(duì)路徑總負(fù)載和干擾情況的綜合評(píng)估，故根據(jù)路徑的總權(quán)值比率分配流量能更好地實(shí)現(xiàn)負(fù)載均衡．

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

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

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

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

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

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

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

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

4 結(jié)語(yǔ)

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

今后將結(jié)合地理位置信息的檢測(cè)，將該路由協(xié)議應(yīng)用到節(jié)點(diǎn)高速運(yùn)動(dòng)情景下，以進(jìn)一步提高協(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］鄭堅(jiān)濤．多射頻多信道無(wú)線Mesh網(wǎng)絡(luò)路由算法研究與NS-2仿真實(shí)現(xiàn)［D］．廣州:華南理工大學(xué)電子與信息學(xué)院，2011．