一种新的基于最大流的无线Mesh网络信道分配算法*

葛志辉，李陶深，韦亚欢

（广西大学计算机与电子信息学院 南宁530004）

1 引言

随着无线技术的发展，无线网络可以让人们摆脱有线的束缚，随时随地进行通信并享受丰富的信息服务，给广大用户提供了极大的便利。无线Mesh网络（wireless mesh network，WMN）融合了移动自组织网 (mobile ad-hoc network，MANET)和无线局域网 (wireless local area network，WLAN)的优势[1]，具有多跳、易扩展、自组织和自恢复等特点，部署成本低，在商业应用中优势明显，如今越来越受到人们的关注。无线网络带宽受限、多跳传输以及无线链路之间的干扰等因素制约了WMN的发展。

目前，在IEEE 802.11系列技术标准中，都提供不同数量的正交信道。多信道技术的引入可以大幅度提升无线网络的空间复用率，但多信道的信道分配、降低信道间的干扰以及实现网络的负载均衡等问题，都给研究人员提出了新的挑战。

[2]中，将信道分配和路由协议相结合，设计了一种基于负载感知的集中式信道分配算法，但需要事先知道端到端的路由路径以及路径上的流量模型等信息。参考文献[3]综合考虑信道分配与路由协议的相互依赖关系，提出了一种联合信道分配、路由选择的静态平衡信道分配算法(BSCA)，在受到公平性约束的条件下，最大限度地提高分配给各流量节点的带宽。Das等人给出了WMN中静态信道分配的最优化模型[4]，将信道分配问题转化成目标最大化时传输的业务流数目的线性规划问题，约束条件为网络全连通、信道数目受限以及潜在干扰边数目受限，然而却没给出实用的多项式时间算法。参考文献[5]提出一种“TiMesh”MC-WMN网络结构，将接口分配、信道分配和路由作为一种联合线性优化问题，较好地解决各流量间的公平性问题。由于它们所采用的算法都是静态分配算法，一旦进行信道分配后将不再改变，因此不能根据业务量的变化动态地调整分配给链路的信道，在实际应用中吞吐量较小，极大地限制了使用多信道的资源和多样性。

参考文献[6]提出基于Hyacinth结构的动态信道分配算法。信道分配通过邻居-接口绑定和接口-信道绑定两个阶段实现，前者能够有效地避免节点信道切换带来的涟漪效应，后者只需搜索具有较高优先级的干扰邻居的信道负载，即可实现信道分配。JARS[7]是一种联合信道分配、路由、调度的信道分配方案，把底层信道分配和调度信息的效率（即逻辑距离）结合到路由度量计算中，使得路由拥有最大的连接空间和频道复用选择，并可根据不同的通信模型（如广播、单播）调整不同的信道分配和调度策略。该方法可以有效地利用多信道多无线接口网络中信道的多样性和空间复用特征，但它没有考虑如何把信道分配和调度策略适应到动态变化的流量模型中。

上述信道分配方案中大多数算法都是假定网络流量模型已知，根据已知的流量信息进行信道分配及网络优化。虽然这些方法对已知流量模型的网络都能进行某种优化工作，但它们并不适合实时动态的网络环境。在实际网络环境中，很多业务是突发且无法预知的，因此本文提出一种基于未知流量模型的信道分配算法。首先利用最大流方法计算网络所能达到的最大吞吐量及在此条件下每条链路承载的不同流量负载，然后以此作为信道分配的依据。在信道分配过程中，同一冲突域中的无线链路应尽量使用不同的正交信道，以减少同信道干扰问题，提高网络传输速率和容量。

2 系统模型与系统假设

2.1 网络模型

用无向图G(V，E)表示多信道无线Mesh网络，其中V表示所有节点的集合，E表示所有无向链路的集合。假设每个节点i配置了R(i)个网卡，网络中可以使用|H|个正交无线信道。对于WMN中的任意两个节点i,j∈V，记d(i,j)为 i、j之间的距离，r表示发射距离。如果 d(i,j)≤r，表示节点在i、j各自的通信范围内，则i和 j之间存在一条无向边，即 ei,j∈E。

2.2 干扰模型

对于物理拓扑 G(V，E)，如果存在两条边 i圮j，m圮n∈E，且 min{d(i,m),d(i,n),d(j,m),d(j,n)}≤r’,其中 r’表示干扰距离，称这两条边为 “潜在”的干扰边。对于任意的e∈E，用PIL(e)表示链路 e的所有潜在干扰链路集合。用χ(e)表示分配给链路e的信道，链路e的所有干扰链路集合可以表示为：

由于在同一冲突区域中，使用信道同时进行通信时会产生干扰。因此，在进行信道分配时，尽量使同一冲突区域内各相关链路使用不同的信道。当网络中所有节点的信道分配结束后，即各链路所使用的信道已确定，那么它的干扰链路集合也可知。此时，对于任意链路e，其干扰度可表示为：

其中，I(χ(e′)= χ(e))表示当“潜在”的干扰链路 e’上分配的信道与链路e相同时，该函数值等于1，否则为0。那么，整个网络的干扰度可表示为：

2.3 业务模型

本文采用参考文献[8]提出的链路流量模型，考虑一个业务，从源端s通过中间路由器转发到达目的端t，在目的端接收到的业务速率为γst。假设该业务在转发过程中通过某条链路eij，定义一个变量ρijst，则有以下约束：

假定链路的流量负载用符号f表示。业务从源端到目的端时，经由链路eij并在该链路上的负载为：

2.4 信道分配

网络流问题在交通运输、容量网络、信息传递等方面有广泛的应用，许多线性规划的实际问题可转化为网络流的模型求解。在WMN中寻求网络最大吞吐量的问题，实质上就是一个典型的最大流问题。因此，提出一种集中式基于最大流的无线Mesh网络信道分配算法（centralized max-flow based channelassignmentalgorithm，CMCA）。CMCA以最小化网络干扰为目标，即：

信道的分配首先根据每条链路的容量，利用最大流方法求解网络中能达到的最大吞吐量及其每条链路的流量负载情况，然后根据每条链路的流量负载情况采用贪心策略依次进行信道分配。

3 性能评价

采用NS2[9]对实验结果进行仿真，网络中布置25个节点，以网格状均匀分布在场景大小为1 000×1 000 m2范围内，传输距离和干扰距离分别为250 m和500 m。每个节点配置两个无线接口，每个业务源的流量取值为0～500 kbit/s，仿真时间为20 s。以吞吐量、端到端时延作为性能评价指标，与LACA算法[2]及公共信道分配算法（CCA）[10]进行对比分析。

图1、2显示了CMCA算法、LACA算法及CCA算法的吞吐量和时延随业务流数目增加的变化情况。

当网络负载较轻时，各个算法所获得的网络吞吐量相差不大；随着网络负载的增加，采用CMCA算法的吞吐量逐渐优于其他两个算法，当业务流数目增加到20条时，采用CMCA算法获得的网络吞吐量可达到LACA算法的1.2倍左右。这是因为CMCA算法在信道分配时以最小干扰为目标，各信道间干扰的降低有效地提高了数据传输率，从而获得较好的网络性能；而LACA算法在进行信道分配时，侧重于各信道间的负载均衡，因此在网络负载不高时，其比CMCA算法的性能稍差。

随着网络负载的加重，LACA算法在业务流数目为25时获得较好的网络性能，但同时由于其基于已知流量模型，在信道分配时需事先预知每条链路上的流量负载，再根据假定的预知值进行信道分配，该算法不能满足实时动态网络业务突发性的要求，因此当网络负载持续加重时，其获得的网络性能反而较差。而CMCA算法基于未知流量模型，利用最大流算法求解网络中能达到的最大吞吐量及其每条链路的流量负载情况，并依次进行信道分配，能较好地适应网络中业务流量的动态变化，因此当网络负载加重时也能获得相对较好的网络性能。CCA算法是一种公共信道分配算法，算法中每个节点的射频信道分配都相同，限制了使用信道的多样性，无法充分利用多信道的资源，因而在整个实验过程中获得的网络吞吐量较低。

4 结束语

本文提出了一种基于最大流的信道分配算法，算法先通过最大流进行计算，得出网络中可达到的最大吞吐量及相关链路可达到的最大负载量，以此作为信道分配的依据。同时，算法充分考虑到网络获得最大吞吐量时每条链路所承载的最大流量负载，优先为流量负载较大的链路分配信道，使网络能够较好地适应各种业务的需求。仿真结果表明，本文算法即使在网络负载较重的情况下，仍能保持较好的网络性能。

参考文献

1 Akyildiz I F,Wang Xudong,Wang Weilin.Wireless mesh networks:a survey.Computer Network Journal(Elsevier),2005,47(4):445～487

2 Raniwala A,Gopalan K,Chiueh T.Centralized channel assignment and routing algorithms for multi-channel wireless mesh networks.Mobile Computing and Communications Review,2004,8(2):50～65

3 Alicherry M,Bhatia R,Li L.Joint channel assignment and routing for throughput optimization in multi-radio wireless mesh networks.In:Proceedings of the ACM MobiCom,2005

4 Das A K,Alazemi H M K,Vijayakumar R,et al.Optimization models for fixed channel assignment in wireless mesh networks with multiple radios.In:Proceedings of IEEE SECON,Santa Clara,CA,2005

5 Mohsenian Rad A H,Wong V W S.Joint logical topology design,interface assignment,channel allocation,and routing for multi-channel wireless mesh networks.IEEE Transactions on Wireless Communications,2007,6(12):4 432～4 440

6 Raniwala A,Chiueh T C.Architecture and algorithms for an IEEE 802.11-based multi-channel wireless mesh network.In:Proceedings of IEEE INFOCOM,2005

7 Xin Wang,Garcia-Luna-Aceves J J.Distributed joint channel assignment,routing and scheduling for wireless mesh networks.Computer Communications,2008(7):1 436～1 446

8 Aoun B,Boutaba R,Kenward G.Analysis ofcapacity improvements in multi-radio wireless mesh networks. In:Proceedings of Vehicular Technology Conference,IEEE 63rd,2006

9 ns-2.http://www.isi.edu/nsnam/ns/

10 Adya A,Bahl P,Padhye J,et al.A multi-radio unification protocol for IEEE 802.11 wireless networks.In:Proceedings of BROADNETS’04,San Jose,California,USA,2004

11 Hejiao Huang,Xiaolu Cao, Xiaohua Jia, et al. Channel assignmentusing block design in wirelessmesh networks.Computer Communication,2009(9):1 148～1 153

12 毕坤,顾乃杰,任开新等.混合式无线mesh网络中信道分配算法研究.小型微型计算机系统,2009,5(5):812～816

13 严军荣，张顺颐，龙华等.基于拓扑分割的无线mesh网络信道分配策略.电子与信息学报，2009,31(7)：1 588～1 593

14 Marina M,Das S R,Subramanian A P.A topology control approach for utilizing multiple channels in multi-radio wireless mesh networks.Computer Networks,2010,54(2):241～256