多Radio多信道无线Mesh网中信道分配算法的研究

郗剑亮，李金宝

（1.黑龙江大学 计算机科学技术学院，哈尔滨 150080；2.黑龙江省数据库与并行计算重点实验室，哈尔滨 150080）

0 引 言

近年来，随着无线通信技术和移动计算技术的迅猛发展，使得具有大容量、高速率、覆盖范围广的无线Mesh网络在各个领域得到广泛应用[1]。无线Mesh网络又称为无线网格网或者无线网状网，它融合了无线局域网WLAN和Ad-Hoc网络的优势，并且在大量部署方面花费成本较低，是无线接入Internet的一个理想解决方案。

无线Mesh网络是由一些Mesh路由器和Mesh客户端组成的多跳无线网络，主要用于扩张Internet的覆盖范围，在网络边缘为用户提供最后1km的接入服务。

在无线Mesh网络中，通过给节点的Radio分配合适的信道，可以减小网络通信冲突、降低数据传输时延，同时实现多对节点并行收发数据，从而提高网络吞吐量。

1 相关工作

本文主要研究内容为Multi-Radio Multi-Channel（MR-MC）无线Mesh网络中的信道分配问题。目前针对无线网络 Multi-Channel的研究，主要集中在MAC层协议（信道分配）、路由层协议、跨层协议和平台设计上。

现在大多数无线传感器节点配有一个半双工的无线收发器即Single-Radio（SR），半双工的无线收发器可以根据需要转换收发频率使节点处于不同的无线信道，但是在某一时刻该收发器只能使用一种频率，而且频率之间的转换需要一定的时间。近期提出的SR-MC信道分配算法针对不同无线网络的性能指标设计，如网络吞吐量、时间延迟、公平性和能量有效等[2－3]。

随着硬件成本的下降，Multi-Radio通信协议逐渐走入人们的视野。基于Multi-Radio的通信协议在提高网络吞吐量，减少传输时延和避免信道冲突等方面的性能均有进一步提高。以往的文章提出了一些对MR-MC的信道分配算法，其主要是对信道干扰、拓扑控制、链路容量、负载平衡等方面进行研究[4－5]。

2 系统模型和问题定义

2.1 系统模型

整个无线Mesh网络定义为一个无向图G＝（V，E），其中V＝｛v｜v是一个网络中的节点｝，E＝｛l｜l＝（u，v），l是点u与点v之间的一条链路，u，v∈V｝。

每个节点ni有Kni个Radio，每个Radio都可以独立于其它Radio并行收发数据，但是需要有足够的正交信道，故用C＝｛c｜c是一条信道｝来表示一个正交信道的集合。

图1是一个拓扑图，图2是图1的冲突图，图中的节点对应于拓扑图中的边，在原图中如果两条链路之间存在有冲突则在冲突图中对应的两点之间存在有一条边。在冲突图中节点的度越大表明原图中的链路越容易与其它链路发生冲突。

在无向图G中如果两个节点u，v在通信范围之内，则存在有一条边l＝（u，v），l∈E。假设每个Radio的通信范围都是一样的，而且任意两个节点进行通信需要分配相同的信道。若一个节点的可用Radio数为0的话，则称这个节点是个饱和节点。

每次通信可分为T个时槽进行，Ls（l，t）＝1表示链路l在时槽t上被调度，为0则表示未被调度，其中T＝｛1，2，…，t｝，而且假设在整个网络内时槽之间是同步的。

I（l）表示链路l的冲突值，与链路l在冲突图中的度成正比。用一个链路信道分配矩阵（LCM）来记录每条链路所分配的信道，其数值为二进制形式，1表示链路l分配了信道c，0表示未分配。Load（l，c）表示链路l在信道c上的负载，与链路l上的数据传输量成正比。Eload（l）表示链路l的期望负载值，这个值是动态变化的，每当链路l上有数据传输时，Eload（l）的值就会更新。其中：

信道负载矩阵（CLM）用来记录每个节点上的信道负载，与链路的期望负载值Eload（l）相同，CLM的值也是随着网络动态改变的，则有：

2.2 问题定义

定义F＝｛fl｜fl为链路l上的流量｝，W＝｛wl｜wl为链路l的权值，0＜wl≤1｝。

本文的目标是最大化网络吞吐量，即：

其中a，b，c是集合V中的元素，l是集合E中的元素。

式（4）将最大化网络吞吐量的目标公式化，通过计算每条链路流量与其权值的积，然后依次相加，从而得到一个对整个网络吞吐量的近似估计。约束条件（5）说明一条链路上的流量是恒定的。约束条件（6）说明整个网络的流量是守恒的。约束条件（7）说明链路上的流量与期望负载之间存在有一定差距。

3 动态信道分配和链路调度算法

3.1 信道分配

本文提出的算法是一个在线启发式算法（LDCA），为了适应网络中链路负载的动态性，每间隔一定时间算法会自动对网络重新进行一次信道分配。

算法1信道分配算法1 . 输入：G ＝（V，E），Eload（l），I（l），K，C，CLM 2. 输出：链路信道分配矩阵LCM 3 . 初始化：LCM＝0，E′＝E 4. 对E′中的链路按期望负载Eload（l）降序排列，如果负载相同则按链路冲突值I（l）降序排列5 . while E′非空6 . 取出E′中的第一条链路l＝（u，v），E′＝E′－｛l｝7. if节点u和节点v都未达到饱和状态8. 从u，v两个节点的空闲信道集合C中选一条公共空闲信道c分配给该链路9 . Cu＝Cu－｛c｝，Cv＝Cv－｛c｝10. Ku－－，Kv－－11. else if节点u和节点v中有一个节点达到饱和／／假设u节点饱和12. 选出CLM中节点u负载最小的信道c 13. if点v的空闲信道集合Cv中包含有此信道14. 把信道c分配给该链路15 . Cv＝Cv－｛c｝16. else选出CLM中u，v两节点负载和最小的信道c分配给该链路17. end if 18. Kv－－19. else节点u和节点v都已达到饱和状态的话20. 选出CLM中u，v两节点负载和最小的信道c分配给该链路21 . LCMl，c＝122. end if 23.end while 24.Eload＝Eload＊α 25.CLM＝CLM＊β

3.2 链路调度

当算法1根据网络动态需求进行信道分配之后，为了使网络中的资源能够有效利用，需要继续进行链路调度算法。该链路调度算法运用了一种贪心的链路覆盖策略，每次选择调度个数最多且不相互冲突的链路，从而提高了网络的吞吐量。

算法2链路调度算法1 . 输入：G ＝（V，E），I（l），LCM 2. 输出：链路调度结果LS 3. 初始化：E′＝E，时槽数t＝0，Ls（l，t）＝0，A＝空集，B＝空集4. 对E′中的链路按期望负载Eload（l）降序排列，如果负载相同则按链路冲突值I（l）降序排列5 . while E′非空6. A＝空集7. 取出E′中的第一条链路l，E′＝E′－｛l｝，A＝A∪｛l｝8 . for l′ ∈E′9 . if l′与A中的任一链路均不冲突10 . E′＝E′－｛l′｝，A＝A∪｛l′｝11. end if 12. end for 13 . for l′∈A 14 . Ls（l′，t）＝115. end for 16 . for l′∈B 17. if l′不与A中任一链路冲突18 . Ls（l′，t）＝119. end if 20. end for 21. B＝B∪A 22. t＋＋23.end while

4 实验结果与分析

用模拟实验来评估本文提出的在线启发式信道分配算法LDCA。通过与静态信道分配算法（SCA）和动态信道分配算法（DCA）相比较，证明了LDCA算法的优越性以及考虑网络流量动态变化的重要性。

由图3可见，SCA算法与DCA算法传输时延随着网络流量的增加而增加，LDCA算法则是先减小后增加，且LDCA算法和DCA算法的传输时延明显小于SCA算法。这是因为LDCA算法能够动态适应网络中链路需求的变化，从而减少了传输时延。

由图4可见，LDCA算法不存在冲突，因为该算法已经在信道分配和链路调度过程中避免了冲突。DCA算法通过控制信道进行数据信道的分配，有可能存在隐终端问题导致冲突，但是发生概率较低。SCA算法是在数据开始传输之前根据网络拓扑静态对链路进行信道分配，分配之后不能根据网络的现有状况进行调整，所以冲突概率较高。

图6 网络吞吐量与节点个数的关系Fig.6 Relationship between the network throughput and the number of nodes

在图5的实验中采用网格状拓扑结构，主要反映了Radio和信道数量与网络吞吐量之间的关系。随着Radio个数和信道个数的增加，网络的吞吐量呈增长趋势，其中LDCA算法的网络吞吐量增长比较明显。在节点个数固定的情况下，增加Radio和信道数量，能够提高网络并行传输数据的能力，进而增加网络吞吐量。

图6的实验拓扑结构为范围固定的随机拓扑结构，模拟了网络中节点密度对网络吞吐量的影响。由图6可见，随着节点个数的增加，LDCA、DCA和SCA算法的网络吞吐量都有相应的提高。这是因为在一定通信范围内，如果网络中节点个数增加，可用链路数量也会相应增长，从而使得网络吞吐量提高。

5 结 论

本文重点研究了多Radio多信道无线Mesh网络中的信道分配问题，针对这个NP难问题，文章将抽象的变量转化为具体的网络模型，随后提出了一种基于链路权值优先的在线启发式信道分配算法LDCA。该算法在信道分配阶段采用了启发式的思想，能够动态适应链路需求，提高系统容量；在链路调度阶段采用分时的策略，将冲突的可能性降到最低。最后通过模拟实验与分析，得出LDCA算法可以显著减少网络传输时延，增加网络吞吐量，同时降低网络中的冲突。

[1]李建中，李金宝，石胜飞.传感器网络及其数据管理的概念、问题与进展 [J].软件学报，2003，14（10）：1717-1727.

[2]G.Zhou，C.Huang，T.Yan，et al.MMSN：multifrequency media access control for wireless sensor networks[A].INFOCOM 2006.25th IEEE International Conference on Computer Communications [C].Proceedings，2006：1-13.

[3]Yafeng Wu，J.A.Stankovic，Tian He，et al.Realistic and efficient multi-channel communications in wireless sensor networks[A].INFOCOM 2008.The 27th Conference on Computer Communications [C].IEEE，2008：1193-1201.

[4]Hua Yu，Mohapatra P.，Xin Liu.Dynamic channel assignment and link scheduling in multi-radio multi-channel wireless mesh networks[A].Mobile and Ubiquitous Systems：Networking ＆Services，2007.MobiQ-uitous 2007.Fourth Annual International Conference on[C].2007：1-8.

[5]Krishna Ramachandran，Irfan Sheriff，ElizabethM Belding.A multi-radio 802.11mesh network architecture[J].Mobile Networks and Applications，2008，13（4）：132-146.