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

尹鳳杰，楊小梅

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

0 引言

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

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

1 系統模型

1.1 定向天線模型

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

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

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

(1)

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

1.2 MRMC-WMN網絡模型

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

圖2 使用定向天線的MRMC-WMN網絡圖

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

1.3 干擾模型

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

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

2 問題及IBSMR算法描述

2.1 問題描述

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

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

(2)

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

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

(3)

這里，|IL(x，k，T)|表示多播樹T中被運行在波束信道k上的節點x的傳輸所干擾的鏈路總數.通過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)最小，控制多播樹傳輸數量的同時減小干擾，最終達到改善整個網絡性能的目的.

2.2 IBSMR多播路由算法

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

第一階段，首先在全向圖上運行Dijkstra算法找到源節點S和所有目的節點R之間的最短路徑，并用DP(S，R)表示這些最短路徑的集合.然后通過公式(5)計算每條路徑p(S，ri)∈DP(S，R)的開銷，并根據公式(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)加入多播樹后，開始為該路徑的每條鏈路選擇最佳波束信道，并更新鏈路開銷和接收節點集.根據網絡模型，兩個節點之間的無線鏈路可以采用不同的信道，這里用k(x，y)avi表示鏈路(x，y)的所有可用信道集，在這些信道中選擇一條作為該鏈路的傳輸信道.然而，IBSMR算法面臨著一個挑戰，那就是在所有可行的開銷最低的路徑中選擇最佳路徑，使該路徑的波束所導致的干擾最小.所以，IBSMR算法使用公式(3)中的定向節點同信道干擾(Directional Node Co-Channel Interference，DNCI)作為判據，在所有可用波束信道中選擇導致干擾最小的一條.

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

(7)

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

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

輸入：有向網絡圖G

多播源節點S

多播接收節點集R

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

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

2. 將其鏈路開銷設為1

3.whileR不為空時 do

4. 運行Dijkstra算法計算從源節點S到所有接收節點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判據

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

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

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

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

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

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

18. 不作任何操作

19. end if

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

21. end for

22. 更新接收節點集

24.end while

3 仿真實驗與結果分析

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

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

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

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

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

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

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

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

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

4 結束語

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