多接口多信道WMN中基于干擾感知的多播路由算法

尹鳳杰，楊小梅

(遼寧大學 信息學院，遼寧 沈陽 110036)

0 引言

無線Mesh網(wǎng)絡(Wireless Mesh Network，WMN)具有組網(wǎng)靈活、易于部署、可靠性高等特點[1]，但由于同信道干擾的存在，網(wǎng)絡容量受到了很大限制，尤其是在多播流量中較為嚴重.為了有效消除干擾，提高無線電資源的利用率，可以為無線Mesh網(wǎng)絡中的路由器配備多個調諧到非重疊信道的無線電接口，這種網(wǎng)絡就叫做多接口多信道無線Mesh狀網(wǎng)絡(Multi-Radio Multi-Channel Wireless Mesh Network，MRMC-WMN).許多研究表明，在無線Mesh網(wǎng)絡中使用定向天線也可以有效減少干擾[2-5]，提升網(wǎng)絡性能.因為與全向天線不同，定向天線幾乎將所有輻射功率集中在主瓣方向上，只有那些位于發(fā)送節(jié)點主瓣內的節(jié)點才會干擾其他的發(fā)送節(jié)點[6-7]，這樣就極大地減少了鏈路之間的同信道干擾，實現(xiàn)了更高的網(wǎng)絡容量，獲得了更好的網(wǎng)絡性能.

近年來已有大量工作致力于將定向天線運用在無線自組網(wǎng)中的研究.文獻[8]研究了使用定向天線對多接口無線Mesh網(wǎng)絡信道分配的影響，提出的信道分配算法能夠在大型拓撲中實現(xiàn)良好的網(wǎng)絡性能.文獻[9]提出了一種使用定向天線并考慮干擾的功率控制方案，且通過實驗證明該方案提高了網(wǎng)絡吞吐量，降低了能耗.文獻[10]證明了MCMT(Minimum Cost Multicast Tree)是一個NP難題，并使用ILP(Integer Linear Programming)模型將其優(yōu)化，提出了WCTB(Wireless Closest Terminal Branching)算法，利用WBA減少多播樹中的傳輸次數(shù)，而且為了減小多播會話之間的干擾，還提出了MIMCR(Minimum Interference Minimum Cost Routing)算法.劉強等[11]針對使用全向天線進行數(shù)據(jù)傳輸時，會產生信號干擾嚴重和網(wǎng)絡收斂較慢等問題，提出了一個基于定向天線的移動自組織網(wǎng)(MANETs)接入控制協(xié)議(DAND-MAC)，統(tǒng)一協(xié)調定向天線與全向天線同步工作，該協(xié)議在端到端延遲、吞吐量和時隙利用率等網(wǎng)絡性能上有顯著的提升.文獻[12]提出了兩種跨層算法：IRMT(Interference and Rate-aware Multicast Tree)算法和IRBT(Interference and Rate-aware Broadcast Tree)算法，減少帶寬消耗.王松[13]提出了一種基于定向天線波束聚合旋轉的分布式算法，該算法能快速構建一個網(wǎng)絡，在滿足節(jié)點度數(shù)限制的同時又使網(wǎng)絡獲得接近最優(yōu)的吞吐量.文獻[14]研究了使用定向天線的無線Mesh網(wǎng)絡中的快速廣播算法的設計問題，提出了基于傳統(tǒng)的流言擴散機制的隨機選擇算法，以及基于貪婪策略的最大差異度優(yōu)先算法.為了解決基于多波束切換的移動自組網(wǎng)鄰居發(fā)現(xiàn)過程中的最優(yōu)通信波束選擇問題，李麗等[15]提出了一種改進的算法，在鄰居發(fā)現(xiàn)過程中增加了接收信號質量評估機制，從而增強了網(wǎng)絡的穩(wěn)定性，提高了網(wǎng)絡吞吐量.以上這些工作都在一定程度上改善了無線Mesh網(wǎng)絡性能，但是對于影響網(wǎng)絡性能的因素考慮得不夠充分.為此，根據(jù)無線Mesh網(wǎng)絡特性，本文綜合運用定向天線技術、WBA和定向節(jié)點同信道干擾(Directional Node Co-Channel Interference，DNCI)判據(jù)，提出了干擾感知波束信道選擇多播(Interference-aware Beam-channel Selection Multicast Routing，IBSMR)路由算法，使無線Mesh網(wǎng)絡的整體性能獲得了提升.

1 系統(tǒng)模型

1.1 定向天線模型

定向天線幾乎將全部功率輻射到主瓣方向上，而向旁瓣方向輻射極少的功率.廣泛使用的定向天線模型有兩種：現(xiàn)實天線(Realistic Antenna)模型和理想天線(Ideal Antenna)模型.圖1(a)為現(xiàn)實天線模型，天線的方向圖由一個主瓣和多個旁瓣組成.圖1(b)為理想天線模型，天線的方向圖近似為波束寬為θ(0≤θ≤2π)的扇形.

為了方便，本文使用理想天線模型，假定每個發(fā)送節(jié)點的天線方向圖僅由一個主瓣構成，主瓣方向即為該發(fā)送節(jié)點的功率輻射方向，旁瓣方向上的發(fā)射功率則為零.此外，本文假定每個接收節(jié)點都使用全向天線，可以接收從任意方向輻射過來的功率.在給定的傳輸功率下，理想天線的傳輸范圍R(θ)通過公式(1)計算：

R(θ)=R0·(2π/θ)1/α

(1)

這里，α為定向天線的波束寬度，β是路徑損失指數(shù)，R0則表示全向天線的傳輸范圍.由公式可知，定向天線的主瓣傳輸范圍與波束寬度和路徑損失指數(shù)成反比，即，R(θ)會隨著θ和α的增大而減小，反之亦然.

1.2 MRMC-WMN網(wǎng)絡模型

用有向圖G=(V，E)來表示多接口多信道無線Mesh網(wǎng)絡，其中，V和E分別代表網(wǎng)絡中的節(jié)點集和無線鏈路集.用(x，y)k表示節(jié)點x與y之間的無線鏈路，且節(jié)點x是發(fā)送節(jié)點，節(jié)點y位于節(jié)點x的主瓣內，兩個節(jié)點之間使用信道k來傳輸數(shù)據(jù).如圖2所示的MRMC-WMN有向網(wǎng)絡圖，每個節(jié)點都配備了三個無線電接口，且都被調諧到三條不同的非重疊信道上，虛線箭頭代表節(jié)點間的無線鏈路，鏈路旁的數(shù)字集合表示該鏈路的所有可用信道.由于使用了定向天線，相互連接的兩個節(jié)點在兩個方向上的可用信道允許不相同.例如，圖中的節(jié)點m向節(jié)點a發(fā)送數(shù)據(jù)時，僅可使用信道1，而節(jié)點a向節(jié)點m發(fā)送數(shù)據(jù)時，既能使用信道1，也能使用信道2.為了更好地理解定向天線的方向性，圖中僅僅畫出了節(jié)點m的三條波束，并假定節(jié)點m被調諧到信道1、信道2和信道5上，并分別通過這些信道的波束覆蓋了節(jié)點集{a，q}、{p，c}和{e}.

圖2 使用定向天線的MRMC-WMN網(wǎng)絡圖

從圖2可知，在使用定向天線的多接口多信道無線Mesh網(wǎng)絡中，由于定向天線的波束只覆蓋了部分節(jié)點，這就大大減少了節(jié)點之間的干擾.但也正是由于定向天線的使用，信道選擇時極大地減小了WBA的影響，增加了網(wǎng)絡的傳輸次數(shù)，造成嚴重的網(wǎng)絡資源浪費.所以，我們需要折中考慮干擾和傳輸次數(shù)，使無線Mesh網(wǎng)絡獲得更好的性能提升.

1.3 干擾模型

在無線Mesh網(wǎng)絡中，經常使用協(xié)議干擾模型(Protocol Interference Model)來計算多播發(fā)送節(jié)點之間的干擾，當一條鏈路的接收節(jié)點位于其他發(fā)送節(jié)點的干擾波束范圍內，該鏈路就是被干擾鏈路.在多播通信中，干擾是由每個發(fā)送節(jié)點和所有樹鏈路來確定的.如圖3所示，有兩棵多播樹T1和T2，多播樹T2中的發(fā)送節(jié)點s在信道5上的干擾范圍為Ir，會干擾多播樹T1上的運行在相同信道5上的鏈路(g，p)，因為鏈路(g，p)的接收節(jié)點p位于節(jié)點s的干擾范圍內.這種情況下，當節(jié)點g在發(fā)送分組時，節(jié)點s就不能發(fā)送分組，必須等到節(jié)點g發(fā)送完畢節(jié)點s才能發(fā)送，這種不必要的等待導致了網(wǎng)絡時延增加，性能下降.

圖3 多播樹無線鏈路間的干擾關系

2 問題及IBSMR算法描述

2.1 問題描述

對于給定的有向網(wǎng)絡圖G=(V，E)，用S(S∈V)表示多播源節(jié)點，R(R?V)表示多播接收節(jié)點.最小開銷多播樹(Minimum Cost Multicast Tree，MCMT)的目的是構建一棵以源節(jié)點S為根，覆蓋R中所有接收節(jié)點的最小開銷多播樹.將多播樹T在波束信道k上的傳輸節(jié)點的集合表示為V(T，k)，根據(jù)文獻[11]中的定義，多播樹T的開銷由公式(2)計算：

Tree_cost(T)=∑k∈K|V(T，k)|

(2)

這里，K為網(wǎng)絡中所有可用信道的集合.另外，通過擴展文獻[11]中的定義，用定向節(jié)點同信道干擾(Directional Node Co-Channel Interference，DNCI)來量化多播樹之間的干擾.那么，與發(fā)送節(jié)點x相關的多播樹集Tset在波束信道k上的干擾可通過公式(3)計算：

DNCI(x，k，Tset)=∑T∈Tset|IL(x，k，T)|

(3)

這里，|IL(x，k，T)|表示多播樹T中被運行在波束信道k上的節(jié)點x的傳輸所干擾的鏈路總數(shù).通過DNCI(x，k，Tset)，就可以通過公式(4)計算出定向樹同信道干擾(Directional Tree Co-Channel Interference，DTCI).

DTCI(T，Tset)=∑k∈K∑x∈V(T，k)DNCI(x，k，Tset)

(4)

通過以上闡述，我們的主要目標就是讓使用定向天線的MRMC-WMN中每棵多播樹的Tree_cost(T)和DTCI(T，Tset)最小，控制多播樹傳輸數(shù)量的同時減小干擾，最終達到改善整個網(wǎng)絡性能的目的.

2.2 IBSMR多播路由算法

本小節(jié)將詳細闡述IBSMR多播路由算法，該算法啟發(fā)式地解決了使用定向天線的多接口多信道無線Mesh網(wǎng)絡中的最小干擾問題.在IBSMR多播樹中，有三種類型的鏈路.第一種是樹鏈路(Tree Link)，如果一條鏈路(x，y)k已經加入當前多播樹T，那么該鏈路就是樹鏈路，在這種鏈路上傳輸新的數(shù)據(jù)分組對于多播樹來說不計算鏈路開銷，因為當該鏈路加入多播樹后，其鏈路開銷就已經變?yōu)榱?第二種是覆蓋鏈路(Covered Link)，這些鏈路還沒有包括在多播樹T中，但已經被T中發(fā)送節(jié)點x的定向波束所覆蓋，因此，這些鏈路的開銷也為零，在這些鏈路上傳輸新的分組時也不計算其開銷.第三種是未覆蓋鏈路(Uncovered Link)，除樹鏈路和覆蓋鏈路之外的鏈路就是未覆蓋鏈路，在這些鏈路上傳輸新的分組時需計算鏈路開銷.對于每一個多播會話請求，IBSMR算法會逐步構建路由樹，每一步都包括兩個階段.

第一階段，首先在全向圖上運行Dijkstra算法找到源節(jié)點S和所有目的節(jié)點R之間的最短路徑，并用DP(S，R)表示這些最短路徑的集合.然后通過公式(5)計算每條路徑p(S，ri)∈DP(S，R)的開銷，并根據(jù)公式(6)選擇開銷最小的一條路徑添加到當前多播樹T中.

cost(p(S，ri))=∑(x，y)∈p(S，ri)W(x，y)

(5)

psel(S，ri)=argminDP(S，R)cost(p(S，ri))

(6)

式中，W(x，y)表示鏈路(x，y)∈p(S，ri)的開銷，路徑p(S，ri)的開銷即為其所有組成鏈路的開銷之和.

第二階段，在最小開銷路徑psel(S，ri)加入多播樹后，開始為該路徑的每條鏈路選擇最佳波束信道，并更新鏈路開銷和接收節(jié)點集.根據(jù)網(wǎng)絡模型，兩個節(jié)點之間的無線鏈路可以采用不同的信道，這里用k(x，y)avi表示鏈路(x，y)的所有可用信道集，在這些信道中選擇一條作為該鏈路的傳輸信道.然而，IBSMR算法面臨著一個挑戰(zhàn)，那就是在所有可行的開銷最低的路徑中選擇最佳路徑，使該路徑的波束所導致的干擾最小.所以，IBSMR算法使用公式(3)中的定向節(jié)點同信道干擾(Directional Node Co-Channel Interference，DNCI)作為判據(jù)，在所有可用波束信道中選擇導致干擾最小的一條.

ksel=argmink(x，y)aviDNCI(x，y，Tset)

(7)

這里，ksel表示所選擇的波束信道.波束信道選擇后，被該波束所覆蓋的所有鏈路的鏈路開銷都被置為零.當路由樹覆蓋了所有接收節(jié)點時，IBSMR算法運行結束.其中，選擇最佳波束信道的具體過程如下：

在為鏈路分配波束信道時，首先判斷該鏈路的類型.若鏈路(x，y)是未覆蓋鏈路，則計算其每條可用波束信道的DNCI判據(jù)，并選擇導致干擾最小的一條波束信道k來傳輸數(shù)據(jù)，隨后，發(fā)送節(jié)點x調諧到波束信道k上的天線的波束自動轉到接收節(jié)點y的方向上，并且波束寬度恰好覆蓋接收節(jié)點y；若鏈路(x，y)是已分配信道k的某條波束的覆蓋鏈路，就為該鏈路選擇信道k作為發(fā)送節(jié)點x的傳輸信道，接著發(fā)送節(jié)點x調諧到波束信道k上的天線的波束自動變寬直到覆蓋接收節(jié)點y；若鏈路(x，y)是一條樹鏈路，則不作任何操作.IBSMR算法描述如下：

輸入：有向網(wǎng)絡圖G

多播源節(jié)點S

多播接收節(jié)點集R

輸出：以S為根的多播樹T

1.for 每一條鏈路(x，y)do

2. 將其鏈路開銷設為1

3.whileR不為空時 do

4. 運行Dijkstra算法計算從源節(jié)點S到所有接收節(jié)點R的最短路徑DP(S，R)

5. for每一條路徑p(S，ri)∈DP(S，R)do

6. 計算其路徑開銷cost(p(S，ri))

7. end for

8. 選擇最小開銷的路徑psel(S，ri)加入當前多播樹

9. for 最小開銷路徑的psel(S，ri)的每一條鏈路(x，y)do

10. if(x，y)是一條未覆蓋鏈路 then

11. (1)計算該鏈路所有可用波束信道的DNCI判據(jù)

12. (2)選擇DNCI判據(jù)最小的信道k作為該鏈路的傳輸波束信道

13. (3)調節(jié)運行在信道k上的發(fā)送節(jié)點x的天線的方向和波束寬度以覆蓋接收節(jié)點y

14. if(x，y)是一條覆蓋鏈路(已被運行在信道k的波束所覆蓋)then

15. (1)選擇信道k作為該鏈路的傳輸波束信道

16. (2)運行在信道k上的發(fā)送節(jié)點x的天線波束變寬直到恰好覆蓋接收節(jié)點y

17. if(x，y)是一條覆蓋鏈路 then

18. 不作任何操作

19. end if

20. 更新鏈路開銷(將所有被波束信道k所覆蓋的鏈路的開銷都置為0)

21. end for

22. 更新接收節(jié)點集

24.end while

3 仿真實驗與結果分析

這部分將通過仿真實驗綜合評估IBSMR算法的性能，比較IBSMR算法與WCTB算法和MIMCR算法[4]的平均傳輸次數(shù)和歸一化干擾.其中，歸一化干擾是指網(wǎng)絡實際干擾與最大干擾的比值.我們的多接口多信道無線Mesh網(wǎng)絡測試平臺由31個Mesh路由器組成，這些路由器隨機分布在1 000 m×1 000 m的正方形區(qū)域中，并且每個路由器都配備三個無線電接口，這些接口被隨機調諧到不同的非重疊信道上.我們假設全向天線的傳輸范圍為300 m，定向天線的傳輸范圍則通過公式(1)來計算.另外，每個節(jié)點的干擾范圍是其傳輸范圍的兩倍，并假定路徑損失指數(shù)α為4.實驗中每個多播會話的源節(jié)點和目的節(jié)點都是隨機選擇的，實驗所涉及的參數(shù)有|K|、N、r和q，其中|K|表示不重疊信道的總數(shù)，N表示網(wǎng)絡中的節(jié)點數(shù)，r表示多播接收節(jié)點數(shù)，q表示多播會話請求數(shù).圖中的每個數(shù)據(jù)點都是50次單獨運行結果的平均值.

圖4的仿真結果顯示了當α不同時IBSMR算法在平均傳輸次數(shù)和歸一化干擾方面的性能.該實驗設定|K|=6，N=31，r和q作為變量.由圖4可知，隨著α的增加，平均傳輸次數(shù)和歸一化干擾也都隨之增加.事實上，參數(shù)α的增加減小了每個波束的傳輸范圍.

圖4 不同α下的平均傳輸次數(shù)和歸一化干擾

圖5的仿真結果顯示了在無線電接口數(shù)不同時，信道數(shù)目的變化對IBSMR算法性能的影響.該仿真設定N=45，r=0，q=30，|K|作為變量.比較圖5(a)和圖5(b)，可以看到，平均傳輸次數(shù)隨著信道數(shù)的增加而增加，歸一化干擾卻隨之增加而減小.開始時，由于可用信道數(shù)小于無線電接口數(shù)，平均傳輸次數(shù)隨著可用信道數(shù)的增加而減少.當可用信道數(shù)大于無線電接口數(shù)時，WBA的影響減弱，所以傳輸次數(shù)增加.另一方面，隨著可用信道數(shù)的增加，提高了網(wǎng)絡的同步傳輸能力，并減小了歸一化干擾.此外，從圖5(a)和圖5(b)可以看出，無線電接口越多，傳輸次數(shù)和歸一化干擾越小.因此，為網(wǎng)絡中的每個發(fā)送節(jié)點配備適當多的無線電接口，能夠有效提升無線Mesh網(wǎng)絡性能.

圖5 不同接口數(shù)下的平均傳輸次數(shù)和歸一化干擾

圖6的仿真結果顯示了傳輸次數(shù)和歸一化干擾隨多播接收節(jié)點數(shù)的變化關系.該實驗設定|K|=6，N=31，q=30，r作為變量.圖6(a)顯示出IBSMR算法與WCTB算法和MIMCR算法的傳輸次數(shù)幾乎相等.圖6(b)顯示出三種算法的歸一化干擾都會隨著多播接收節(jié)點的增加而增加，但IBSMR算法的干擾明顯小很多.因為IBSMR算法在全向圖上找到最短路徑后，定向天線的波束自動地調節(jié)到目的接收節(jié)點的方向上，所以IBSMR算法在傳輸次數(shù)上保持WCTB算法和MIMCR算法性能界限的同時，極大地減少了多播樹間的干擾.

圖6 平均傳輸次數(shù)和歸一化干擾隨多播接收節(jié)點數(shù)的變化關系

圖7的仿真結果顯示了平均傳輸次數(shù)和歸一化干擾隨多播會話數(shù)的變化關系.該實驗設定|K|=6，N=31，r=10，q從1變到30.圖7(a)顯示出IBSMR算法與WCTB算法和MIMCR算法在傳輸次數(shù)上性能相當.圖7(b)顯示出IBSMR算法在減少干擾方面比WCTB算法和MIMCR算法更加有效.在IBSMR算法中，每根天線的波束寬度和方向都是自適應地只覆蓋目標接收節(jié)點，因此大大減少了傳輸節(jié)點的干擾區(qū)域.此外，在IBSMR算法中，源節(jié)點和接收節(jié)點之間選擇的最小開銷路徑是干擾最小的路徑，并在所有可用信道中選擇導致最小干擾的信道作為傳輸信道.因此，IBSMR算法在降低干擾方面具有最佳性能.

圖7 平均傳輸次數(shù)和歸一化干擾隨多播會話數(shù)的變化關系

4 結束語

本文研究了多接口多信道無線Mesh網(wǎng)絡中的多播路由算法，綜合運用定向天線技術、WBA和定向節(jié)點同信道干擾，提出了IBSMR多播路由算法.該算法在多播樹構建期間，每一步都首先選擇最小開銷路徑加入多播樹，這就保證了最終所構建的多播樹的樹開銷最小；在波束信道選擇時，充分考慮了鏈路之間的同信道干擾，利用DNCI判據(jù)為每條鏈路都選擇最佳波束信道來進行數(shù)據(jù)傳輸；定向天線的使用充分利用了WBA優(yōu)勢減少了傳輸次數(shù)，并且發(fā)送節(jié)點的波束只覆蓋接收節(jié)點，大大地減少了干擾.仿真結果也表明，IBSMR算法在傳輸次數(shù)和干擾方面明顯優(yōu)于其他多播路由算法，能夠更加有效地改善MRMC-WMN網(wǎng)絡性能.