多收發器無線Mesh網絡的信道分配方案研究

高　杭　向文麗

?

多收發器無線Mesh網絡的信道分配方案研究

高杭1向文麗2

（1.上海交通大學 電子信息與電氣工程學院，上海 200240；2.甲骨文研究開發中心<深圳>有限公司，廣東 深圳 518057）

無線Mesh網絡是一種由無線鏈路連接路由器和終端設備構成的新型寬帶無線接入系統。論文以Mesh網絡中的總干擾量最小為目標，設計了一種集中式和一種分布式的信道分配方案來解決準靜態信道分配問題，并制定了一種半定規劃和線性規劃公式，用于獲取網絡總干擾度的下確界，通過在NS2上的模擬實驗，驗證了論文提出的信道分配方案能進一步地提高網絡的性能。

多收發器無線mesh網絡；信道分配；干擾度；線性規劃

1　引　言

無線Mesh網絡（WMN）是從Ad hoc網絡中分離出來的一種新的寬帶無線網絡，它是一種高速率、高容量的分布式網絡，和傳統的無線網絡相比，無線Mesh網絡中的大多數節點是靜態的，不移動的，不需要電池作為動力，網絡的拓撲變化相比較小；從接入上來看，無線Mesh網絡以多跳方式接入互聯網，網絡中的所有節點都可以相互通信。另外，無線Mesh網絡具有組網靈活，網絡覆蓋面大，投資較少等特點，適合用于寬帶無線接入骨干網，其應用前景非常廣闊，Mesh結構已經被納入到802.16、802.16e和即將制定的802.11s標準中。

論文建立了一種信道分配策略，為了降低網絡干擾，將多收發器網絡環境中的信道分配問題為準靜態信道分配問題，信道分配遵循接口限制，即分配給某條鏈路的信道數最多不超過該鏈路節點上的接口數，利用數學公式的方式來計算最優解的界值，提出相應的啟發式算法，通過仿真表明該啟發式算法有比較好的性能。

2　多收發器多信道WMN中信道分配方案

2.1網絡模型和干擾模型

（1）網絡模型。網絡中有多個靜止的無線路由器，每個路由器有多個收發器（不一定每個路由器的收發器數量相同）。論文對網絡的通信圖建立一個網絡節點集（路由器）的無向圖。通信圖中的邊（i，j）指代一條通信鏈路，表明只要節點i和j之間有一個接口卡，并且有一條公共信道，兩者就可以互相通信。網絡中有一定數量的可利用的信道，且信道是正交的（非干擾的）。

（2）干擾模型。由于無線鏈路的廣播性質，通信鏈路的傳輸（無線節點對之間）可能會與網絡中其他鏈路產生干擾，論文采用一個二態的干擾模型（兩條鏈路干擾或者不干擾）。實際上，兩條鏈路間的干擾水平取決于鏈路的通信量，為了簡化，假定所有鏈路的通信量一致。

2.2主要數據結構定義

（1）符號說明。N表示網絡中的節點集。R表示節點i∈N上收發器的數量。

K={1，2，……，K}表示K個信道的集合。

Vc={lij|（i,j）}為通信鏈路。

Gc(Vc,Ec)是網絡沖突圖。

（2）無向圖。將網絡看成無向圖G，采用圖的鄰接矩陣來表示圖。相關數據結構定義如下。

struct point{

integer x; integer y;

}V[N];//頂點

integer D[N][N];//圖鄰接矩陣

N表示頂點的數目。結構體point表示網絡中的一個節點，x和y分別表示節點的橫縱坐標。二維數組D表示圖的鄰接矩陣，其中D[i][j]為1表示節點i和j相鄰，是一跳鄰居，可以直接通信；D[i][j]為0表示節點i和j不相鄰，不能直接通信。

（3）沖突圖。對于已給定的一個干擾模型，互相干擾的通信鏈路對的集合用沖突圖表示。為了定義沖突圖，對網絡中通信鏈路創建一個集合Vc={ lij|（i,j）}，其中lij|（i，j）表示一條通信鏈路。Gc(Vc,Ec)沖突圖定義為集合Vc，在沖突圖中用于表示兩條鏈路(i，j)和（a，b）間在同一信道時相互干擾的沖突邊（lij，lab）。沖突圖相關數據結構定義如下。

struct edge{

integer p1; integer p2;

integer weight; integer channel;

}E[MAXEDGE];//邊

integer C[MAXEDGE][MAXEDGE];//沖突圖鄰接矩陣

（4）干擾度。定義兩節點u，v∈V間的距離為d（u，v）。對于每個u，v∈V，假定以u為中心，半徑為d（u，v）的圓內，當u向v傳輸時，處于該圓內的節點都會受到干擾。然后，對于給定的拓撲圖G（V，E），對于每個v∈V，節點干擾度I(v)定義為E中能潛在影響在v處接收消息的鏈路的數量。干擾度I(v)為鏈路u1→u2∈E的數量，其中，d(u1,v)≤d(u1,u2)。

2.3信道分配方案

（1）信道分配問題。多收發器無線mesh網絡中的信道分配問題描述如下。

對于多收發器的無線mesh網絡節點，給網絡中的每條鏈路分配不同的信道，使得分配給每條鏈路的信道數量最多不超過鏈路的節點上的收發器數量。假定所有鏈路的通信量一樣，因此給所有的鏈路分配信道后，確定網絡的總干擾量為干擾的通信鏈路對的數量。

（2）優化對象的選擇。自然客觀的信道分配問題將直接最大化整個網絡的吞吐量，事實證明，網絡吞吐量模型分析了隨機存取的介質訪問模型是困難的。假定一個時隙同步介質訪問調度模型為問題的一部分。在一個時隙同步媒介訪問模型中，模型吞吐量相對于基于CSMA的隨機訪問模型盡管顯得較為簡單，但整個模型還是相當復雜，很難將它們用于優化問題的目標函數和有效的解決問題方式。因此，在信道分配問題中，用網絡干擾代替網絡吞吐量，設計了一個目標函數如下。

考慮無線mesh網絡中網絡節點集N。信道分配問題是計算函數，使得在滿足如下的接口限制情況下總的網絡干擾量I(f)最小。

網絡干擾量I(f)：I(f)=|{(u，v)∈Ec|f(u)=f(v)}|

如果將節點的信道分配看作節點的著色問題，則網絡干擾就是頂點著色沖突圖中的單色邊數量，因此信道分配問題簡化為極大k割問題。

2.4信道分配算法

信道分配問題可以看成圖的著色問題。在沖突圖G中，在接口限制和沖突圖中單色的邊的數量最少的情況下，利用K種顏色對V個節點著色。也就是說，信道分配問題是找到一個函數 f：Vc→ K，使得網絡干擾值I(f)最小。

（1）禁忌搜索算法。禁忌搜索算法基本思想是選取一個點作為初始點，從該點出發利用局部搜索算法進行搜索，在搜索過程中，當獲得的最優解符合藐視規則，不考慮其禁忌屬性，使用該解代替當前最優解，并把當前最優解加入到禁忌表中，同時修改禁忌表中各對象的任期；如果沒有符合藐視規則的點時，取非禁忌表中的最優解，作為當前最優解，無論該解是否優于當前最優解，同時將該解加入禁忌表中，如此迭代下去，直到滿足條件為止。

禁忌搜索算法包含兩個階段。第一個階段，在不考慮接口約束的情況下利用禁忌算法找到合適的函數f。第二個階段，在考慮接口約束的情況下找到可行的信道分配函數f。

禁忌搜索第一階段算法描述如下。

輸入: 沖突圖Gc(Vc,Ec)；信道數為K。

輸出: 信道分配函數fbest：Vc→K

由隨機分配函數f0開始; fbest=f0；ibest=i(f0)；T=null；j=0；i=0；

while i(fi)>0 and i

生成fi的隨機鄰居r；

每個鄰居是隨機選取Vc里的一個節點u生成，且 kK ，k≠fi(u)，且(u，k)T，且將fj(u)變為k；

在最小干擾的情況下，使得fj+1為鄰居；

將(u,fj(u))加入T；

如果T滿了, 刪除表中最久以前的信息；

if(i(fj+1)

then ibest= i(fj+1)；fbest= fj+1；i=0；

else i=i+1；

end if；

j=j+1；

end while

RETURN fbest；

（2）分布式貪婪算法。貪婪算法不從整體最優上加以考慮，它所做出的是在某種意義上的局部最優解，通常把求解的問題分成若干個子問題。然后對每一子問題求解，得到子問題的局部最優解，并把子問題的解局部最優解合成原來解問題的一個解。

分布式貪婪算法描述如下。

輸入：局部網絡和沖突圖；選擇信道K。

輸出：節點i上的所有鏈路u∈Vc的信道分配（例如，f（u））

重復執行：

選擇能夠最大降低局部干擾的一條信道；

發送顏色請求（u，k）到節點j，u=（i，j）；

等待節點j的顏色回復消息（u，k）；

如果在一定時間內顏色回復（u，k）消息沒有收到，放棄選擇（u，k）；

Until 局部干擾不能進一步降低，或者所有的（u，k）組合已經被選擇。

When 從節點j收到顏色請求（u，k）消息，u=（i，j）：

f分配顏色k到鏈路u不會引起接口限制干擾：

Then發送顏色回復（u，k）消息給節點j；

When 從節點j收到顏色回復（u，k）消息：f（u）=k，發送顏色更新（u，k）消息給“局部”鄰居；

When 收到顏色更新（u，k）消息：局部更新局部網絡圖中保持的信道分配鏈路；

2.5最優化網絡干擾的界值

這里采用SDP模擬信道分配問題，SDP的標準形式給出如下。

最小化 C.X

信道分配問題在本質上是沖突圖在接口限制條件下的極大k割問題，可以用公式表示為如下整數二次方程式。

信道分配的不約束的SDP給出如下：

最大值 C.X

因此對角線(X)=e

3　仿真結果與分析

3.1仿真方案

性能模擬在兩種環境下進行。第一種是通過圖論性能指標來評估，另一種是采用NS2模擬吞吐量。為了更好的比較基于禁忌搜索的信道分配算法與分布式貪婪算法的性能，加入了另外兩種算法的模擬實驗用作比較。一種算法集中啟發式CLICA算法（CLICA-SCE算法）。另外一種是隨機分配算法，對于每個節點采用隨機分配算法為該節點來分配一個隨機接口來傳輸數據包。通過算法比較發現，文中提出的兩種算法表現良好，有較大的實用性。

3.2圖論性能指標

使用兩種網絡模型，一種是稠密網絡模型，一種是稀疏網絡模型。稠密網絡模型是在500*500的區域內隨機分配50個網絡節點，稀疏網絡模型則是在800*800的區域內隨機分配50個網絡節點。稠密網絡中平均節點度是10左右，稀疏網絡中平均點度則是5左右。每個節點都具有相同的接口數目，使用統一的傳輸工具，其干擾半徑為150米，假定信道是正交的，并且所有鏈路傳輸量一致。如果兩個節點的距離在通信范圍內則把這兩個節點連接起來。同理，對于兩條通信鏈路（i,j）和(g,h)只有當g節點或h節點在i節點或j節點的干擾范圍內時這兩條鏈路才會產生干擾。

對干擾指標比較，采用一種稱為部分干擾性能指標來評估算法性能。對于由算法算出的信道分配函數f，部分網絡干擾定義為網絡干擾率（I(f)），和沖突圖中的邊的總數。相對于單一信道網絡中的沖突量，經過信道分配后這代表沖突數。隨機算法的部分網絡沖突給定為1/R，R是每個節點上的收發器數量。上述性能指標完全是圖論指標，在這次實驗中沒有用到網絡模擬工具。其模擬結果如下圖所示。

圖1.稠密，3條信道

圖2.稠密，12條信道

圖3.稀疏，3條信道

圖4.稀疏，12條信道

總體來看，基于禁忌的搜索算法和分布式貪婪算法的表現比CLICA-SCE算法以及隨機算法要好得多。基于禁忌的搜索算法總是要比DGA算法要好。但當無線接口數目較少時，基于禁忌的集中式算法表現則并不比其它算法有優勢。另外，文中算法的性能和SDP公式得到的界值相比較，說明論文的算法得到了非常好的解決方案，特別是在收發器數量比較大時，禁忌算法和SDP下確界值的性能有大概1%到4%的差距。同時由上圖可以看出，當每個節點的收發器數量增加時，部分干擾降低；然而，當收發器達到一定數目時這種趨勢接近飽和。

3.3 NS2模擬

利用NS2模擬隨機生成的網絡，模擬場景是：在1000m×1000m的區域中隨機分布50個節點，采用802.11bMAC協議，每個包大小為1000bytes。發送速率為11Mbps。傳輸模型采用TwoRayGround，傳輸半徑是250m，干擾半徑是550m。采用NS2默認的收發器數量，信道傳輸數據速率為24M/s。采用三種不同的傳輸模型如下。

①單跳傳輸模型：每條傳輸鏈路是統一的泊松傳輸，用于衡量網絡中所有鏈路負載一樣情況下網絡的性能。

②多跳點對點傳輸模型：使用25個隨機選擇的源目的節點，對采用多跳路由進行傳輸。這些路由采用最短跳數作為判據，且不改變模擬的周期。

③多跳網關傳輸模型：4個隨機節點被選作網關，25個源節點傳輸負載到最近的網關。這種傳輸模型在mesh網絡用做互聯網網關連接時十分常見。

模擬過程中，對于特定數量的收發器和信道，每次增加提供的負載，從一個較低的值開始做起，直到增加提供負載而吞吐量不再增加時停止，模擬結果如下圖所示。

圖5.單跳，12條信道

圖6.多跳點對點，12條信道

圖7.多跳網關，12條信道

這三個圖顯示了上述三種傳輸模型和12條信道情況下的隨著節點收發器變化的飽和吞吐量變化情況。表明了在上述三種傳輸模型中，論文中提出的算法性能非常好。同時也可以觀察到，通過上述圖論性能評估在NS2中轉化非常好。在收發器達到一定數量時，飽和吞吐量和圖論性能模擬中一樣保持不變。同時，NS2模擬中相關的算法性能和在圖論性能中觀察到的性能一致。

4　結束語

論文以獲取網絡最小干擾度為目標，采用集中式和分布式兩種算法來解決信道分配問題，通過半定方式獲得最小網絡干擾的下確界，對最優化算法和近似算法做了比較和分析，證實了近似算法的可行性。并在NS2中做了網絡性能的模擬實驗，實驗結果表明，本文提出的信道分配方案能進一步地提高網絡的性能。

[1]J.Shi,T.Salonidis,and E.Knightly.Starvation Mitigation through Multi-Channel Coordination in CSMA Multi-Hop Wireless Networks[C].Proc.ACM MobiHoc,2008.

[2]A.Raniwala and T.Chiueh.Architechture and Algorithms for an IEEE 802.11-Based Multi-Channel Wireless Mesh Network[C].Proc.IEEE INFOCOM,2005.

[3]M.K.Marina and S.Das.A Topology Control Approach to Channel Assignment in Multi-Radio Wireless Mesh Networks[C].Proc.Second Ann. Int’l Conf.Broadband Networks (Broadnets),2005.

[4]A.Adya,P.Bahl,J.Padhye,A.Wolman,and L.Zhou.A Multi-Radio Unification Protocol for IEEE 802.11 Wireless Networks[C].Proc.First Ann.Int’l Conf.Broadband Networks(Broadnets ’04),Oct.2004.

[5]J.Tang,G.Xue,and W.Zhang.Interference-Aware Topology Control and QoS Routing in Multi-Channel Wireless Mesh Networks[C].Proc.ACM MobiHoc,2005.

[6]J.Robinson,K.Papagiannaki,C.Diot,X.Guo,and L.Krishna-murthy.Experimenting with a Multi-Radio Mesh Network-ing Testbed[C].Proc.Int’l Workshop Wireless.Network Measurements(WiNMee),2005.

[7]V.S.A.Kumar,M.V.Marathe,S.Parthasarathy,and A. Srinivasan.Algorithmic Aspects of Capacity in Wireless Networks[J].Acm Sigmetrics Performance Evaluation Review,2005,(1):133-144.

[8]M.Alichery,R.Bhatia,and L.Li.Joint Channel Assignment and Routing for Throughput Optimization in Multi-Radio Wireless Mesh Networks[C].Proc.ACM MobiCom,2005.

[9]C.Reis,R.Mahajan,M.Rodrig,D.Wetherall,and J.Zahorjan. Measurement-Based Models of Delivery and Interference in Static Wireless Networks[C].Proc.ACM SIGCOMM,2008.

[10]J.Padhye,S.Agarwal,V.Padmanaban,L.Qiu,A.Rao,and B.Zill.Estimation of Link Interference in Static Multi-Hop Wireless Networks[C].Proc.Internet Measurement Conf. (IMC),2005.

[11]M.Gong,S.Midkiff,and S.Mao.A Combined Proactive Routing and Multi-Channel MAC Protocol for Wireless Ad Hoc Networks[C].Proc.Second Ann. Int’l Conf. Broadband Networks (Broadnets),2005.

[12]R.Maheshwari,H.Gupta,and S.R.Das.Mutichannel MAC Protocols for Wireless Networks[C].Proc.Int’l Conf. Sensor and Ad Hoc Comm.and Networks(SECON),2008.

[13]J.So and N.H.Vaidya.Multi-Channel Mac for Ad Hoc Networks:Handling Multi-Channel Hidden Terminals Using a Single Transceiver[C].Proc.ACM MobiHoc,2004.

[14]R.Vedantham,S.Kakumanu,S.Lakshmanan,and R. Sivakumar.Component Based Channel Assignment in Single Radio, Multichannel Ad hoc Networks[C].Proc.ACM MobiCom,2008.

[15]Q.Xue and A.Ganz.Temporal Topology Control in Multi- Channel Multihop Wireless Access Networks[C].Proc. Second Ann.Int’l Conf. Broadband Networks (Broadnets),2005.

[16]A.H.M.Rad and V.Wong.Joint Channel Allocation, Interface Assignment and MAC Design for Multi-Channel Wireless Mesh Networks[C].Proc.IEEE INFOCOM,2008.

（責任編校：張京華，何俊華）

2016－05－23

高杭（1995－），男，上海交通大學電子信息與電氣工程學院學生，研究方向為計算機網絡。向文麗（1986－），女，甲骨文研究開發中心（深圳）有限公司工程師，研究方向為軟件工程。

TP391

A

1673-2219（2016）10-0039-05