多信道多接口智能路由協(xié)議研究

劉玉梅，葉竹君，欒淵鑫

哈爾濱工程大學信息與通信工程學院，黑龍江哈爾濱 150001

多信道多接口智能路由協(xié)議研究

劉玉梅，葉竹君，欒淵鑫

哈爾濱工程大學信息與通信工程學院，黑龍江哈爾濱 150001

多信道多接口可以降低信道共用的干擾并且提高多跳無線Ad Hoc網(wǎng)絡(luò)的吞吐量。提出一種信道分配與路由選擇相結(jié)合的多信道多接口智能路由協(xié)議DMMR，DMMR綜合考慮了鏈路生存時間、跳數(shù)以及節(jié)點距離。用LP標準，使路由選擇標準在鏈路生存時間和最短路徑之間取得均衡，這樣選擇的信道在移動環(huán)境中更加具有可靠性；用基于距離的信道選擇算法選擇信道，該信道選擇算法首先估算節(jié)點間距離，根據(jù)估算到的距離選擇合適的信道進行數(shù)據(jù)傳輸，從而提高信道的空間復用。和已經(jīng)存在的路由協(xié)議相比，仿真結(jié)果表明在移動多跳Ad Hoc網(wǎng)絡(luò)中該協(xié)議能夠降低平均端到端延遲并且提高網(wǎng)絡(luò)的吞吐量和包到達率。

Ad Hoc網(wǎng)絡(luò)；信道分配算法；路由算法；多信道多接口；跨層

多接口多信道路由協(xié)議是指網(wǎng)絡(luò)中每個節(jié)點配置多個半雙工無線網(wǎng)卡，這樣可以使得節(jié)點同時接收和發(fā)送數(shù)據(jù)，還可以更加有效地傳輸路由控制包。由于硬件技術(shù)的快速發(fā)展，無線網(wǎng)卡的成本越來越低。針對多信道多接口的移動Ad Hoc網(wǎng)絡(luò)研究也越來越多。信道分配是Ad Hoc網(wǎng)絡(luò)中一個重要的研究內(nèi)容，信道分配算法已經(jīng)取得大量研究成果，例如：圖著色算法、整數(shù)線性規(guī)劃方法和本地搜索算法［1-2］等，這些算法大都是以如何最大限度地減少鏈路的干擾來提升網(wǎng)絡(luò)的吞吐量為出發(fā)點合理地分配信道。傳統(tǒng)的路由協(xié)議往往都是以找到路由為目標，沒有考慮到路徑上各個節(jié)點的信道分配。文中將信道分配與路由選擇相結(jié)合，在路由選擇的過程中，綜合考慮鏈路生存時間和跳數(shù)，在信道分配的過程中采用基于距離的信道選擇方法，提高了網(wǎng)絡(luò)的包到達率。

1 多信道路由協(xié)議相關(guān)研究

多信道路由協(xié)議是Ad Hoc網(wǎng)絡(luò)中一個重要的研究內(nèi)容，有許多研究者設(shè)計了Ad Hoc網(wǎng)絡(luò)多信道路由協(xié)議。文獻［3］提出的CA-AODV將信道選擇信息放在路由控制包和路由表中，利用尋路和路由回復為每條路由選擇不同的信道，這樣一個節(jié)點的k個鄰居節(jié)點內(nèi)如果有n條數(shù)據(jù)流就分配n×（k＋1）個正交信道。文獻［4］對CA-AODV協(xié)議進行了擴展，通過引入一個額外的Channel Taken消息為在節(jié)點干擾范圍內(nèi)網(wǎng)絡(luò)的所有不同活動節(jié)點分配不同的信道。這2種協(xié)議在建立路由時完成信道分配，實現(xiàn)簡便。但沒有實時參考MAC層的信道情況，信道分配不夠優(yōu)化。文獻［5］提出一個將分布式信道分配和路由協(xié)議結(jié)合的協(xié)議J-CAR，也是按需地在建立路由時分配信道。該協(xié)議中節(jié)點具有多個收發(fā)器，通過send channel list（S-list）和receive channel list（R-list）協(xié)商信道。該協(xié)議實現(xiàn)復雜，同樣沒有實時地參考MAC層信道狀態(tài)，信道分配不完善。

2 多信道跨層路由機制設(shè)計

2．1 鏈路生存時間估計機制

在許多軍事應(yīng)用中，節(jié)點可以通過一些例如GPS的設(shè)備來獲得自身的位置。假設(shè)每個節(jié)點都有相同的傳輸范圍，當一個節(jié)點在另一個節(jié)點的傳輸范圍內(nèi)時，他們之間就可以進行通信。假設(shè)在計算過程中節(jié)點的相對速度和方向是保持不變的，所以鏈路生存時間的估計過程就如圖1所示，R代表節(jié)點的通信范圍。利用AODV協(xié)議中Hello分組的傳遞來估算收發(fā)節(jié)點間的生存時間，網(wǎng)絡(luò)中的節(jié)點周期性的發(fā)送Hello分組，在Hello分組中寫入當前時刻節(jié)點的位置信息，接收節(jié)點利用先后到達的2個Hello分組中攜帶的位置信息，估算發(fā)送節(jié)點的運動速度與運動方向，從而估算出收發(fā)節(jié)點間的生存時間。

圖1 節(jié)點的運動過程

為了計算2個移動節(jié)點和參考節(jié)點S的鏈路生存時間，等間隔選取3個接收信號強度樣本點，分別為A、D和E，其在時間域內(nèi)滿足Δt1＝Δt2＝Δt。周期發(fā)送的Hello分組可以獲得樣本點的位置（x，y，z），因此di、dj和dk可以被計算出來。使用正余弦公式，鏈路生存時間可以根據(jù)式（1）～（3）被估計出來［6］，就可以算出收發(fā)節(jié)點間生存時間。

2．2 具有環(huán)境感知功能的多信道分配機制

為研究方便，暫不考慮一個網(wǎng)絡(luò)接口在多個信道上切換的情況，也就是說將研究范圍限定在如下情況：網(wǎng)絡(luò)中的節(jié)點具有多個接口，即有多個MAC地址和物理地址，網(wǎng)絡(luò)中可以使用的信道數(shù)為N，使節(jié)點的接口數(shù)等于信道數(shù)N，每一個接口都對應(yīng)一個信道而不需要切換。在某一個信道i上，節(jié)點對應(yīng)的接口i可能處于發(fā)送狀態(tài)、接收狀態(tài)或監(jiān)聽狀態(tài)。為后續(xù)的研究能夠更加深入，假設(shè)網(wǎng)絡(luò)中信道的質(zhì)量可以不相同，即同一時刻，不同信道具有不同的信噪比。

2．2．1 信道環(huán)境感知原理

信道環(huán)境的變化會對網(wǎng)絡(luò)的性能產(chǎn)生很大影響，信道環(huán)境的變化具體體現(xiàn)在信道信干比上，用SINR表示，定義SINR為

式中：Psignal表示有用信號的功率；Pnoise表示信道噪聲功率；Pinterface表示干擾功率，由于同一時刻可能存在多個干擾，所以干擾信號的總功率為多個干擾功率求和。SINR能夠準確反映當前信道的信道狀況。SINR越大，信道環(huán)境越好。SINR本是物理層參數(shù)，在這里借鑒跨層的概念，通過跨層調(diào)用將SINR傳遞到路由層，作為信道分配的依據(jù)。

在AODV路由協(xié)議中，節(jié)點周期性的發(fā)送Hello分組用來維護路由，同樣可使用Hello分組來測量信道質(zhì)量。在AODV協(xié)議中，每個節(jié)點都維護一張鄰居節(jié)點列表，用以記錄通信范圍內(nèi)的節(jié)點的信息，在鄰居節(jié)點列表條目中增加一項名為nb_sinr的記錄。nb_sinr為N維數(shù)組，N為信道數(shù)，nb_sinr［i］表示鄰居節(jié)點使用信道i時的信噪比。當節(jié)點在信道i上接收到某節(jié)點發(fā)送的Hello分組之后，根據(jù)Hello分組接收功率的大小計算當前信道的信噪比SINR，將信噪比寫入鄰居節(jié)點列表中的nb_sinr［i］中。

當節(jié)點需要向某鄰居節(jié)點發(fā)送數(shù)據(jù)分組或者路由應(yīng)答分組時，檢索鄰居節(jié)點列表，找到各信道對應(yīng)的信噪比值，用SINR的值作為選路的重要依據(jù)。但是，當多個節(jié)點需要同時發(fā)送數(shù)據(jù)時，往往會同時選擇信噪比最高的信道，這樣會導致競爭節(jié)點同時在高信噪比信道上傳輸數(shù)據(jù)，從而導致沖突的發(fā)生。為了避免這種情況，采用基于距離相關(guān)的信道分配機制［7］來解決這個問題。

2．2．2 基于距離相關(guān)的信道分配機制

多信道與單信道相比，最大的優(yōu)勢在于可以同時通信的數(shù)據(jù)流數(shù)目增加。為了實現(xiàn)這個目標，就需要讓同時通信的收發(fā)節(jié)點對數(shù)最大化。

基于距離的信道分配機制的基本思想是：距離較近的節(jié)點對在正確接收的前提下使用頻率高的信道，把能夠傳輸較遠的信道留給長距離的節(jié)點對進行通信。在上述的情況下，2個節(jié)點對就能夠同時進行通信，提高了并行傳輸?shù)臄?shù)據(jù)對，從而提高網(wǎng)絡(luò)的性能。

節(jié)點A要給節(jié)點B發(fā)送數(shù)據(jù)，節(jié)點A發(fā)送信道請求包給節(jié)點B，請求包中攜帶本節(jié)點的信道空閑列表和需要的帶寬。節(jié)點A的鄰居節(jié)點除節(jié)點B以外，收到節(jié)點A的信道請求包的時候均不做響應(yīng)。

節(jié)點B收到節(jié)點A的信道請求包S后，獲得節(jié)點A的空閑信道列表List（A），并根據(jù)接收包的功率，估算出節(jié)點A與節(jié)點B的距離dAB，根據(jù)距離dAB移除使用額定功率發(fā)送時，接收信噪比低于信噪比門限的信道，得到信道列表List（A?），根據(jù)List（A?）和本節(jié)點的空閑信道List（B）比較，得出相交的信道列表List（A?，B）。選擇List（A?，B）中信噪比最小的信道i作為選定的信道。

節(jié)點A收到節(jié)點B的回復后，給節(jié)點B發(fā)送信道確認信息，并更新本節(jié)點的信道狀態(tài)列表，然后使用所選定的信道進行數(shù)據(jù)傳輸。

3 多信道多接口路由協(xié)議

傳統(tǒng)的單信道路由協(xié)議例如AODV、DSR選擇最短的路由。 在多信道網(wǎng)絡(luò)中，WCETT［9］、WEED［10］被提出作為靜態(tài)網(wǎng)絡(luò)的協(xié)議。文中提出一種有效的多信道跨層路由協(xié)議DDMR，其中路由選擇標準LP綜合考慮了鏈路生存時間和最短路徑，信道選擇提出基于距離的信道選擇算法。

結(jié)合跳數(shù)最小原則和穩(wěn)定性最優(yōu)原則，給出改進機制的選路的準則如下。

假設(shè)在目的節(jié)點的路由表中儲存了同源的N條路由，用ilifetime表示第i條路由的生存時間，用ihops表示第i條路由的跳數(shù)，那么計算后的準則LP的計算公式為準則LP越大，意味著鏈路的性能越優(yōu)。在計算準則的過程中，首先將跳數(shù)的倒數(shù)和生存時間進行歸一化，之后加權(quán)求和。α代表了選路的權(quán)重，當α＝1時，改進機制退化為以最小跳數(shù)為準則的路由協(xié)議；反之，當α＝0時，意味著完全采用鏈路的穩(wěn)定性作為選路準測。目的節(jié)點根據(jù)這個準則選擇最優(yōu)的路徑作為路由。此準則中利用了節(jié)點間鏈路的生存時間估計，采用跨層的設(shè)計思路，將節(jié)點間鏈路生存時間攜帶在路由消息中進行傳輸，并在傳送過程中進行更新。目的節(jié)點得到最小的鏈路生存時間，即路徑的瓶頸。目的節(jié)點綜合考慮鏈路的穩(wěn)定性和跳數(shù)，選擇最優(yōu)的路徑，并單播回復路由應(yīng)答消息，源節(jié)點收到路由應(yīng)答消息，完成路徑建立過程。然后按照信道環(huán)境感知的多信道分配機制進行數(shù)據(jù)包的傳輸，即把能夠傳輸較遠的信道留給長距離的節(jié)點對進行通信，增加并行傳輸?shù)臄?shù)據(jù)對，從而提高網(wǎng)絡(luò)性能。

4 仿真結(jié)果與分析

在NS2上實現(xiàn)前文提出的信道分配與路由選擇相結(jié)合的多信道多接口智能路由協(xié)議DMMR，進行一系列仿真工作。為了比較不同機制的性能，分別在NS2上實現(xiàn)了Ramon的多信道模型［8］以及DDMR（multi-radio multi-channel routing protocol）。在DDMR中，信道分配方案采用基于距離的多信道分配機制，而多信道路由方案采用具有鏈路穩(wěn)定性感知功能的多信道路由機制。

4．1 靜態(tài)場景

仿真場景拓撲圖如圖2所示。信道參數(shù)配置表如表1所示。

圖2 靜態(tài)場景仿真拓撲

表1 靜態(tài)場景仿真信道參數(shù)表

設(shè)定一個特定場景，在這個場景中節(jié)點只可以和其相鄰的節(jié)點通信。采用不同的隨機種子仿真10次取平均值，吞吐量作為性能指標隨跳數(shù)的增加變化如圖3所示。

圖3 靜態(tài)場景中的吞吐量

結(jié)果表明盡管鏈路生存時間估計沒有被完全利用，但DDMR也適用于靜態(tài)場景。利用基于距離的多信道分配方案可以達到更高的信道利用率。在RAMON信道分配方案中，路由請求在所有信道廣播，節(jié)點隨機的挑選信道，沒有考慮信道的分配，而基于距離的信道分配方案，在考慮了距離的基礎(chǔ)上進行信道分配能夠有效提高并行通信信道數(shù)目，提高網(wǎng)絡(luò)吞吐量。

4．2 動態(tài)場景

信道參數(shù)配置表如表2所示。在20個節(jié)點中隨機選擇4個節(jié)點作為源節(jié)點，隨機選擇4個節(jié)點作為接收節(jié)點，節(jié)點初始位置隨機生成，運動方向和運動速度隨機生成。運動速度v為0～20的隨機值，服從均勻分布。改變v的大小，觀察性能隨之變化情況。

表2 隨運動場景仿真參數(shù)表

采用不同的隨機種子仿真10次取平均值，取包到達率和端到端平均延遲作為性能指標，仿真結(jié)果如圖4、5所示。

圖4 動態(tài)場景中的端到端包到達率

圖5 動態(tài)場景中端到端平均延遲

仿真結(jié)果表明，在移動場景中，文中提出的DDMR協(xié)議的包到達率比AODV提高100%，這是因為DDMR在選路時通過考慮鏈路時間來選擇更加穩(wěn)定的路由，同時利用了基于距離的鏈路選擇算法從而提高了網(wǎng)絡(luò)的包到達率，并且可以看出α的變化對性能影響的趨勢并不明顯。

5 結(jié)束語

結(jié)果表明，在靜態(tài)場景中盡管基于鏈路穩(wěn)定性的路由選擇機制并沒有被完全利用但是DDMR也適用于靜態(tài)場景。利用基于距離的多信道分配方案可以達到更高的信道利用率。在RAMON信道分配方案中路由請求在所有信道廣播，節(jié)點隨機的挑選信道，沒有考慮信道的分配，而基于距離的信道分配方案，在考慮了距離的基礎(chǔ)上進行信道分配能夠有效提高并行通信信道數(shù)目，提高網(wǎng)絡(luò)吞吐量。在移動場景中，DDMR的包到達率比AODV提高100%，這是因為DDMR在選路時通過考慮鏈路時間來選擇更加穩(wěn)定的路由，同時利用了基于距離的鏈路選擇算法從而提高了網(wǎng)絡(luò)的包到達率，在以后的工作中，多信道路由協(xié)議的優(yōu)化可以是在考慮QoS性能的同時進行協(xié)議擴展，在綜合考慮節(jié)點負載、能量和剩余帶寬等因素的情況下對路由判據(jù)進一步優(yōu)化。

［1］ARIKAN E．Some complexity results about packet radio net-works［J］．IEEE Transactions on Information Theory，1984，30（4）：681-685．

［2］BEHZAD A，RUBIN I．Multiple access protocol for power-controlled wireless access nets［J］．IEEE Transactions on Mobile Computing，2004，3（4）：307-316．

［3］GONG M X，EMIDKIFF S．Distributed channel assignment protocols：a cross-layer approach［C］／／IEEE Wireless Communication and Networking Conference．New Orleans，USA，2005：2159-2200．

［4］GONG M X，MIDKIFF S F，MAO Shiwen．Design princi-ples for distributed channel assignment in wireless ad hoc networks［C］／／IEEE International Conference on Commu-nications．Seoul，Korea，2005：3401-3406．

［5］CHIU H S，YEUNG，LUI K L．J-CAR：an efficient joint channel assignment and routing protocol for IEEE 802．11-based multi-channel multi-interface mobile Ad Hoc networks［J］．IEEE Transactions on Wireless Communications，2009，8（4）：1706-1715．

［6］WU Dapeng，ZHEN Yan，XU Chunxiu，et al．On-demand reliable routing mechanism for MANET based on link life-time predicting［C］／／4th International Conference on Wire-less Communications，Networking and Mobile Computing．Dalian，China，2008：1-4．

［7］SALAMEH H A B，KRUNZ M，YOUNIS O．Cooperative a-daptive spectrum sharing in cognitive radio networks［J］．IEEE／ACM Transactions on Networking，2010，18（4）：1181-1194．

［8］CALVO R A，CAMPO J P．Adding multiple interface sup-port in NS-2［EB／OL］．［2013-04-06］．http：／／personales．unican．es／aguerocr／files／ucmultiifacessupport．pdf．

［9］SUBRAMANIAN A P，GUPYA H，DAS S R．A topology control approach for utilizing multiple channels in multi-ra-dio wireless mesh networks［J］．Computer Networks，2010，54（2）：241-256．

［10］SUBRAMANIAN A P，GUPTA H，DAS S R，et al．Mini-mum interference channel assignment in multiradio wireless mesh networks［J］．IEEE Transactions on Mobile Compu-ting，2008，7（12）：1459-1473．

Multi-channel multi-interface intelligent routing protocol

LIU Yumei，YE Zhujun，LUAN Yuanxin
College of Information and Communication Engineering，Harbin Engineering University，Harbin 150001，China

Multi-channel multi-interface can reduce co-channel interference and improve the multi-hop wireless Ad Hoc network throughput．A distance-based multi-radio multi-channel routing protocol（DMMR）is proposed，which combines channel assignment and routing algorithms．The lifetime of the link，the link distance and the number of hops are considered by this protocol．An LP standard is used to make the choice of routing criteria in the link be-tween the lifetime and the shortest path strike a balance．In this way the selected channel in a mobile environment is more reliable．A channel is selected with distance-based channel selection algorithm，which first estimates the distance between nodes，then selects the appropriate channel for data transmission according to the estimation of the distance，thus improving reuse of spatial channel．Compared with existing routing protocols，the simulation results show that the mobile multi-hop Ad Hoc networks can reduce the average end-to-end delay and improve the through-put of the protocol and packet delivery ratio．

Ad Hoc network；channel assignment algorithm；routing algorithm；multi-channel multi-interface；cross-layer

TP393

A

1009-671X（2014）03-0010-05

10．3969／j．issn．1009-671X．201307018

http：／／www．cnki．net／kcms／doi／10．3969／j．issn．1009-671X．201307018．html

2013-07-22．

日期：2014-06-05．

國家自然科學基金資助項目（61102105）．

劉玉梅（1971-），女，副研究員，博士；

葉竹君（1988-），女，碩士研究生．

葉竹君，E-mail：yeahzhujun1988＠sina．com．