異構無線網狀網分布式接口和信道聯合分配的研究

摘 要:研究了無線網狀網絡中分布式分配信道時，接口異構對網絡容量的影響。提出了一種新穎的以射頻鏈路為信道分配對象的接口和信道聯合分配ILP模型，給出了一種自適應于網絡流量變化的分布式貪婪算法。該算法以射頻鏈路為信道分配對象，基于2-hop干擾模型，以隊列長度為權的射頻鏈路吞吐量之和最大為目標，尋找自適應流量變化的分布式分配方案。分析發現，該算法與目前已有的非接口異構的Dist. Greedy算法的時間復雜度相當，仿真結果表明本算法下的網絡性能有明顯提升。

關鍵詞:無線網狀網絡; 異構; 接口和信道聯合分配; 自適應; ILP

中圖分類號:TP393

文獻標志碼:A

文章編號:1001-3695(2010)02-0628-04

doi:10.3969/j.issn.1001-3695.2010.02.062

Distributed joint radios and channels assignment of

heterogeneous wireless mesh network

MA Li1， ZHU Guang-xi1， YIN Bo-yun2

(1.Dept. of Electronics Information Engineering， Huazhong University of Science Technology， Wuhan 430074， China; 2.Hubei Electric Power Survey Design Institute， Wuhan 430024， China)

Abstract:This paper investigated the effect of heterogeneous interface for the capacity of distributed channel-assignment mesh network， presented a new ILP model of joint radio and channel assignment， which considered radio-links as the object of channel-assignment， and proposed a new distributed greedy algorithm. It was an adaptive distributed algorithm， which could get the maximal sum of radio-links throughput with the weight of queue length， based on 2-hop interference model and the load of the network. It found this algorithm has the same time-complex order as Dist. Greedy algorithm with homogeneous interfaces. The simulation result shows that this algorithm can improve the performance of the network efficiently.

Key words:wireless mesh network(WMN); heterogeneous; joint radios and channels assignment; adaptive; ILP

0 引言

單信道無線網狀網絡(WMN)中，鄰近區域的多條鏈路同時傳輸時，會產生干擾并導致網絡傳輸性能下降。為解決這一問題， WMN 使用多個正交信道的接入模式， 節點可以通過多個射頻接口在不同信道上同時傳輸，以提高網絡容量;即使每個節點只有一個接口，節點也可以與鄰居節點在不同信道上傳輸，信道干擾減少，網絡容量也可提升。

然而，在實際的網絡中，各節點配置的接口類型不同，使得接口不能接入網絡提供的所有信道，而且不同接口接入信道的速率也不相同。在以前的多信道分配和調度的研究中，考慮的網絡節點都是配置相同接口。文獻[1]研究了信道速率不同下的路由和信道分配的問題，假設前提是節點配置同類型接口。文獻[2]給出了異構無線網狀網絡的最小干擾模型下的集中式算法，其網絡的異構性體現在節點的接口個數不同，但接口都是同類型的。文獻[3]給出了信道速率不同條件下的多信道多射頻網絡中的調度算法，節點的接口也是同類型的。文獻[4]給出了無線網絡中多種類型接口的存在對網絡容量影響的研究框架。文獻[5]在隨機信道分配的研究中發現，考慮接口異構因素，對于集中式調度不靈活的大范圍網絡，網絡性能有一定改善。

顯然，實現吞吐量最優的信道分配策略需要全網絡信息，如網絡中節點的位置關系和接口配置以及節點的流量需求，解決的是全局最優化問題，這樣的分配策略不適合WMN。 WMN的分布式特性要求簡單的和分布式的信道與接口分配策略。本文解決了配置異構接口的節點組成的多信道WMN中，如何分布式地實現接口與信道聯合分配問題。這里的異構接口是指接口具有的接入信道子集不同，接入信道的速率不同等特性。

本文強調了接口同構與接口異構的網絡之間的差異。由圖1可以看到，在鏈路選擇信道時，由于沒有考慮接口差異而產生鏈路吞吐量的損失。在圖1中，無線鏈路XY可用1、2、3信道，傳輸速率相同為r。節點X、Y分別有三個接口Xa、Xb、Xc、Ya、Yb、Yc。每個接口接入的信道子集如圖1所示。假設節點X有數據包經鏈路XY發送到節點Y。如果選擇接口對(Xa，Yb)在信道1傳輸，鏈路吞吐量為r。顯然，圖1中最優的接口與信道分配為:接口對(Xa，Yb)分配信道2，接口對(Xb，Ya)分配信道3，接口對(Xc，Yc)分配信道1，鏈路吞吐量增加到3r。即使鏈路XY僅分配信道1，選擇接口對(Xc，Yc)進行數據傳輸，也為鏈路實現多信道同時傳輸預留了可用的接口。本文提出了一種以射頻鏈路為信道分配對象的自適應網絡流量變化的分布式貪婪算法，簡稱Hete-RCDG(heterogeneous radios and channels’ distributed greedy)。與文獻[7]的集中式Tube-Based算法和接口同構分布式Dist-Greedy算法進行性能比較，通過仿真實驗表明，本文Hete-RCDG算法與Dist-Greedy算法相比，網絡處于輕負載狀態，網絡吞吐量增加18%，網絡處于重負載狀態，網絡吞吐量提高9.5%。與集中式Tube-Based算法相比，更能適應網絡流量的變化，收斂速度快。

1 系統描述

本文研究的WMN體系結構如圖2所示。無線網狀網中存在三類用戶節點:mesh客戶端、mesh路由器和mesh網關。筆者重點關注mesh路由器構成的無線骨干網中的接口和信道分配問題。文中處理的節點，即mesh路由器，配置異構無線接口，網絡中信道的傳輸速率和傳播特性不同，節點位置可以移動，節點流量和網絡拓撲動態變化。

本文用圖G(μ，{l}，I(l))描述WMN骨干網，包含N個節點和L條直接鏈路。其中:μ表示網絡節點集;{l}表示網絡鏈路集;I(l)表示鏈路l的干擾鏈路集，N=|μ|，L=|{l}|。令C(i)表示節點i可接入信道子集，C=∪C(i)i∈μ表示網絡信道集，它是節點可接入信道子集的并集。本文定義一個鏈路的兩個端節點，互稱為1-hop鄰居節點，如s(l)和d(l)分別表示某鏈路l的端節點，則互為1-hop鄰居節點。E(i)表示以節點i為端節點的鏈路集合。如果兩條鏈路有一個相同的端節點，則互稱為1-hop鄰居鏈路。連接相同1-hop鄰居鏈路的兩條鏈路，互稱為2-hop鄰居鏈路。N1(l)=E(s(l))∪E(d(l))表示l鏈路的1-hop鄰居鏈路集合。鏈路l與其所有1-hop鄰居鏈路N1(l)所覆蓋的物理區域，稱為鏈路l的1-hop鄰域。N2(l)=∪N1(k)k∈N1(1)表示鏈路l的2-hop鄰居鏈路集合。鏈路l與N1(l)∪N2(l)所覆蓋的物理區域，稱為鏈路l的2-hop鄰域。由此，WMN的2-hop干擾模型可定義為，鏈路l與其2-hop鄰域內的任一鏈路同信道同時傳輸，相互干擾。在此干擾模型中，本文假設節點i的1-hop鄰居節點都能偵聽到節點i的傳輸。2-hop干擾模型是IEEE 802.11DCF干擾模型的近似。本文的算法是基于2-hop干擾模型下提出的。

本文假設網絡系統是時隙系統，存在一個全網的公共控制信道用于傳遞公共控制信息，其余信道為數據信道。節點在每個時隙之初競爭信道。在2-hop干擾模型中，如果為某鏈路l分配信道與接口，只需知道其端節點的1-hop鄰居節點信道和接口狀態信息，就可實現。與此同時，如果還能獲得端節點的1-hop鄰居鏈路的待發送隊列長度，那么在不增加網絡開銷情況下，就能實現鏈路l的1-hop鄰域內鏈路的信道與接口資源的公平分配。于是改進了文獻[3]對RTS/CTS消息的修改，在RTS/CTS消息中攜帶1-hop鄰居節點信道接口狀態表和1-hop鄰居鏈路待發送隊列長度，在RTS/CTS/CONFIRM三次握手過程中，由鏈路的接收節點獲得這些信息，并最終實現資源分配。節點定期更新1-hop鄰居節點的狀態信息及鏈路隊列長度來自適應網絡變化。筆者假定節點采用本文改進的IEEE 802.11協議RTS/CTS/CONFIRM三次握手機制來消除隱藏終端和暴露終端問題。

2 分布式多接口多信道分配算法

2.1 射頻鏈路的干擾約束條件

定義1 射頻鏈路。如果位于鏈路l兩端節點的接口Xa、接口Ya，其接入信道集合的交集非空，那么接口Xa和Ya在交集信道上可以互傳數據，稱做存在一條射頻鏈路XaYb。這樣，射頻鏈路XaYb的可分配信道集合就是接口Xa和Ya接入信道集合的交集。

通過圖1的分析得出，對鏈路所用接口的選擇，可以轉換為對鏈路上可用射頻鏈路的選擇，對鏈路的信道分配，也歸結到鏈路上射頻鏈路的信道分配。在2-hop干擾模型中，鏈路l的干擾鏈路集I(l)，是鏈路l的2-hop鄰域內所有鄰居鏈路集合。如果鏈路l與I(l)中鏈路k在信道c上相互干擾，那么，在這兩條鏈路上，至少分別存在一條射頻鏈路同時占有信道c。I(l)表示為

I(l)={l′:c∈C，l′∈N2(l)，lr∈R(l)，

l′r∈R(l′)，op(c，lr)#8226;op(c，l′r)=1}(1)

其中:R(l)表示鏈路l的射頻鏈路集;lr表示其中某射頻鏈路;C(lr)表示射頻鏈路lr可接入信道子集;op(c，lr)=1表示射頻鏈路lr可分配信道c，否則為0。為簡便討論，令I(l)包含鏈路l自身。

如果鏈路l被分配信道c，那么信道一定是分配到此鏈路的某一個射頻鏈路上。否則，若I(l)中的非干擾鏈路子集I′(l)非空，一定是I′(l)中的鏈路分配有信道c，此約束稱為射頻鏈路干擾約束，由式(2)表示。其中Mc表示分配信道c的射頻鏈路集合。

∑k∈I(l)I′(l)≠

∑kr∈R(k)op(c，kr)=1 1kr∈Mc≥1(2)

為射頻鏈路分配信道時，其端節點連接的所有射頻鏈路應分配互不相同的信道，此約束稱為節點處的射頻鏈路干擾約束。式(3)表示在射頻鏈路lr的端節點s(lr)的干擾約束條件。

∑kr∈E(s(lr))∑c∈C(s(kr))op(c，kr)=1 1kr∈Mc=1(3)

2.2 節點接口數對射頻鏈路信道分配的約束條件

WMN中任一節點i，配置m(i)個接口，至多分配m(i)個信道，鏈路l的已分配信道的射頻鏈路集合的度不大于端節點m(s(l))和m(d(l))，可由式(4)表示。

∑lr∈R(l)∑c∈C(lr)op(c，lr)=1 1lr∈Mc≤min(m(s(l))，m(d(l)))(4)

2.3 分布式接口與信道聯合分配數學模型

本文選擇的接口與信道聯合分配目標為，在待分配信道鏈路l的1-hop鄰域內，以隊列長度為權值的射頻鏈路吞吐量之和最大，由式(5)表示。

max∑k∈N2(l)ql∑kr∈R(k)∑c∈C(kr)rckr1kr∈Mc(5)

其中:rckr表示射頻鏈路kr在信道c上的傳輸速率。提出這樣的分配目標基于如下分配原則，讓隊列長的鏈路能夠分得信道和接口的機會更大，以免鏈路阻塞;同時盡量使用速率快的信道，提高吞吐量。對于隊列ql較長的鏈路，因qlrlr相對更大，射頻鏈路很容易被選出;而信道速率rlr很小的射頻鏈路，因為qlrlr相對較小更容易被丟棄。于是，分布式接口與信道聯合分配問題可用整數線性規劃(ILP)定義為

目標函數:max∑k∈N1(l)qk∑kr∈R(k)∑rckrc∈C(kr)1kr∈Mc

約束條件:∑h∈I(k)I′(k)≠k∈N1(l)∑hr∈R(h)op(c，hr)=1 1hr∈Mc≥1

∑kr∈R(k)∑c∈C(kr)op(c，kr)=1 1kr∈Mc≤min(m(s(k))，m(d(k)))

∑hr∈E(s(kr))∑c∈C(s(hr))op(c，hr)=1 1hr∈Mc=1

∑hr∈E(d(kr))∑c∈C(d(hr))op(c，hr)=1 1hr∈Mc=1

2.4 分布式接口與信道聯合分配Hete-RCDG貪婪最大算法

從2.3節模型定義來看，這個ILP問題是NP難問題，采用Hete-RCDG貪婪最大算法得到此問題的次優解。算法基本思路為:a)根據s(l)和d(l)的1-hop鄰居節點的信道和接口信息，在滿足式(3)(4)條件下，得到s(l)、d(l)及其1-hop鄰居節點的可用接口和信道;b)從所有射頻鏈路的qkrkr組成的候選集合中，選出qkrkr值最大的射頻鏈路，并去掉此射頻鏈路的干擾射頻鏈路;然后在候選集剩余的射頻鏈路中，再選出qkrkr值次大的射頻鏈路，并從集合中去掉對應的干擾射頻鏈路，循環往復，直到候選集為空結束。

根據以上分析，設計的Hete-RCDG貪婪最大算法具體步驟如下:

算法1 分布式信道與接口聯合分配Hete-RCDG算法

輸入:

(xij)i∈{s(l)，d(l)}，j≥0:節點狀態向量，其中xij(node_id，radio_id，radio_avail_ch_vec，radio_rate_vec，is_used)表示節點i及鄰居節點的每個接口信息/為方便起見，端節點認為是其自身的鄰居節點/

(nij)i∈{s(l)，d(l)}，i≥0:鏈路l及其N1(l)的隊列向量，其中nij(node_id，queue_len)表示端節點i與其鄰居節點node_id間鏈路的待發送隊列長度queue_len/從節點狀態信息表得到/

輸出:out{lij}i∈{s(l)，d(l)}，j≥0:鏈路l及其N1(l)中已分配接口和信道的射頻鏈路集，其中lij(node_id_1，node_id_2，radio_id_1，radio_id_2，radio_avail_ch_vec，qlen_rate)

begin

a)節點狀態信息的更新。

if{xs(l)p#8226;node_id}∩{xd(l)q#8226;node_id}

then

{根據交集中發送節點s(l)存儲的鄰居節點接口信息xs(l)p，修改接收節點d(l)相同鄰居節點的接口信息xd(l)q}

/鄰居節點交集非空/

b)獲得s(l)、b(l)和1-hop鄰居節點可用接口和信道。

for(每個節點node_id){計算節點已占用的信道向量ch，根據此向量，修改空閑接口的可用信道向量}/接口可用信道滿足約束式(3)(4)/

if(端節點s(l)or d(l)){計算s(l)or d(l)各自鄰居節點已占用的信道向量ch，根據此向量，修改對應端節點空閑接口的可用信道向量}

/使得接口可用信道滿足射頻鏈路干擾約束式(2)，來減少射頻鏈路集中射頻個數/

c)初始化候選射頻鏈路集{lij}i∈{s(l)，d(l)}，j≥0

d)while({lij}非空){

選出lij#8226;qr值最大的射頻鏈路lij;

if(lij滿足接口數約束條件，即式(4)){

加入到集合outlink{lij}中;

根據約束式(2)，去掉集合里lij干擾射頻鏈路;}

else{從集合中去掉lij和與其相同鏈路上的所有射頻鏈路;}

}

end

3 算法分析與仿真結果

3.1 算法復雜度的分析

假設鏈路的1-hop鄰域內的鏈路個數為q，每個射頻鏈路的干擾射頻鏈路集的度為k，所有射頻鏈路的干擾射頻鏈路集的度最大值、最小值和平均值分別為kmax、kmin和k-。定義節點配置的接口數，稱為節點的接口度s。所有節點配置的平均接口數，稱為節點的平均接口度s-。假設初始候選射頻鏈路集中射頻鏈路個數為R，最后一個射頻鏈路被選出時的候選射頻鏈路集中平均射頻鏈路個數為k-1，那么倒數第二個射頻鏈路被選出時的候選集中平均射頻鏈路個數為k1-×k2-，信道分配經過p次循環結束，則循環次數p滿足式(6)。由于鏈路的多個信道分配等同于鏈路上的多個射頻鏈路的選擇，每對接口對應一條射頻鏈路。候選射頻鏈路集的度最多為對應鏈路集的度的s-倍，則算法復雜度最多為o(R log(R)/log k-)=o(qCs- log(qCs-)/log k-)=o(q log q)，與文獻[7]中接口同構的分布式Dist-Greedy算法的復雜度相當。

R=k1-×k2-×…×kp-

p×log kmin≤log(R)=log(k1-×k2-×…×kp-)≤p×log kmax

log(R)/log kmax≤p≤log(R)/log kmin

(6)

3.2 仿真結果

本文采用NS-2仿真研究接口和信道分配對IEEE 802.11協議的WMN吞吐量的影響。以網絡吞吐量為評價指標，對比算法為文獻[7]集中式貪婪Tabu_Based算法和接口同構分布式貪婪Dis. Greedy算法。本文考慮50個節點隨機分布在(1 000×1 000)m2區域內，節點傳輸范圍是250 m，干擾范圍為550 m，信道帶寬24 Mbps，數據分組長為1 KB。每個節點配置3個射頻接口，1個公共控制信道接口配置IEEE 802.11b協議，2個數據接口A和B配置IEEE 802.11a協議，接口A使用IEEE 802.11a的1~8正交信道子集，接口B使用IEEE 802.11a的5~12正交信道子集。本文使用單跳數據流傳輸模式和多跳端到端數據流傳輸模式兩種不同場景。

首先，在單跳數據流傳輸模式下仿真，在此模式下，每個鏈路都有相同的泊松分布數據流，數據流經單個鏈路傳輸后離開網絡。算法的網絡吞吐量與分組到達率之間關系的仿真結果如圖3所示。隨著分組到達率增加，算法的網絡吞吐量增加由快到慢，存在一個增幅拐點，當分組到達率大到6 packet/s后，網絡吞吐量不再隨分組到達率增加而增大，保持不變。Hete-RCDG與Dist. Greedy算法相比，分組到達率小于4 packet/s時，網絡處于輕負載狀態，Hete-RCDG算法的網絡吞吐量增加18%，更接近Tabu-Based算法的網絡吞吐量;分組到達率大于4 packet/s時，網絡處于重負載狀態，Hete-RCDG的網絡吞吐量也比Dist. Greedy算法增加9.5%。當限制網絡中可用信道為802.11a協議的1~6正交信道子集時，每個網絡節點僅單接口A工作，Hete-RCDG算法與文獻[7]分布式Dist. Greedy算法下的網絡吞吐量隨著分組到達率的變化曲線完全相同。

本文在多跳端到端數據流傳輸模式下進行仿真，在此模式中，隨機選擇八對源—目的對采用多跳路由通信，路由采用最小跳數為標準靜態計算得到，并在仿真過程中保持不變。算法的網絡吞吐量與分組到達率之間關系的仿真結果如圖4所示。從圖中看到，本文算法與Dist. Greedy算法相比，網絡吞吐量明顯提高;與Tube-Based算法相比，更能適應網絡流量的變化，收斂速度快。當限制網絡中可用信道為802.11a協議的1~6正交信道子集時，每個節點僅單接口A工作，Hete-RCDG與Dist. Greedy算法下的網絡吞吐量隨分組到達率的變化曲線基本相同。

4 結束語

本文分析了多信道多射頻無線網狀網絡中，接口異構對網絡容量的影響，給出了一個以射頻鏈路為信道分配對象的分布式接口與信道聯合分配問題的ILP數學模型;提出一種隊列長度為權值的射頻鏈路吞吐量之和最大的分布式Hete-RCDG算法。通過仿真實驗表明，本文算法與不考慮接口異構的分布式Dist-Greedy算法相比，網絡吞吐量明顯提高，與集中式Tube-Based算法相比，更能適應網絡流量的變化，收斂速度快。將來的工作集中在研究信道分配與功率分配結合對網絡吞吐量和端到端時延的影響。

參考文獻:

[1]LIN Xiao-jun， ROSOOL S B. Constant-time distributed scheduling policies for Ad hoc wireless network[C]//Proc of the 45th IEEE Conference on Decision and Control.2006:1258-1263.

[2]MA Li， ZHU Guang-xi， YIN Bo-yun. Optimization models of multi-channel assignment in multi-radio wireless mesh networks[C]//Proc of the 4th International Conference on Wireless Communication， Networking and Mobile Computing.2008:1-5.

[3]鄭相全， 郭偉，黃磊.一種新的拓撲無關的按需分配多信道自組網MAC協議[J].計算機科學，2005，32(5):34-40.

[4]BHANDARI V， VAIDYA N H. Heterogeneous multi-channel wireless networks scheduling and routing issues[R].[S.l.]:Illinois University，2007.

[5]BHANDARI V， VAIDYA N H. Capacity of multi-channel wireless networks with random (c，f) assignment[C]//Proc of the 8th ACM International Symposium on Mobile Ad hoc Networking Computing. New York: ACM，2007:229-258.

[6]LIN Xiao-jun， RASOOL S. A distributed joint channel-assignment， scheduling and routing algorithm for multi-channel Ad hoc wireless network[C]//Proc of the 26th IEEE International Conference on Computer Communications.2007: 1118-1126.

[7]SUBRAMANIAN A P，GUPTA H， DAS S R. Minimum interference channel assignment in multi-radio wireless mesh networks[C]//Proc of the 4th Annual IEEE Communications Society Conference on Sensor， Mesh and Ad hoc Communications and Networks.2007: 481-490.