多信道多接口智能路由協議研究

劉玉梅，葉竹君，欒淵鑫

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

多信道多接口智能路由協議研究

劉玉梅，葉竹君，欒淵鑫

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

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

Ad Hoc網絡；信道分配算法；路由算法；多信道多接口；跨層

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

1 多信道路由協議相關研究

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

2 多信道跨層路由機制設計

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

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

圖1 節點的運動過程

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

2．2 具有環境感知功能的多信道分配機制

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

2．2．1 信道環境感知原理

信道環境的變化會對網絡的性能產生很大影響，信道環境的變化具體體現在信道信干比上，用SINR表示，定義SINR為

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

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

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

2．2．2 基于距離相關的信道分配機制

多信道與單信道相比，最大的優勢在于可以同時通信的數據流數目增加。為了實現這個目標，就需要讓同時通信的收發節點對數最大化。

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

節點A要給節點B發送數據，節點A發送信道請求包給節點B，請求包中攜帶本節點的信道空閑列表和需要的帶寬。節點A的鄰居節點除節點B以外，收到節點A的信道請求包的時候均不做響應。

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

節點A收到節點B的回復后，給節點B發送信道確認信息，并更新本節點的信道狀態列表，然后使用所選定的信道進行數據傳輸。

3 多信道多接口路由協議

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

結合跳數最小原則和穩定性最優原則，給出改進機制的選路的準則如下。

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

4 仿真結果與分析

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

4．1 靜態場景

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

圖2 靜態場景仿真拓撲

表1 靜態場景仿真信道參數表

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

圖3 靜態場景中的吞吐量

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

4．2 動態場景

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

表2 隨運動場景仿真參數表

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

圖4 動態場景中的端到端包到達率

圖5 動態場景中端到端平均延遲

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

5 結束語

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

［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．