基于连通性的动态固定信道分配算法

尹凤杰，梅丙乾，杨 晖，张 颖

(辽宁大学 信息学院，辽宁 沈阳 110036)

基于连通性的动态固定信道分配算法

尹凤杰，梅丙乾，杨 晖，张 颖

(辽宁大学 信息学院，辽宁 沈阳 110036)

随着跳数的增加，无线Mesh网络的延迟开始增大，吞吐量开始降低，QoS难以得到保证.基于多信道多接口的信道分配策略可以很好地解决上述问题，但目前对多信道Mesh网络的研究往往忽视了节点之间的连通性问题.在原有的宽带优先搜索(BFS,Breadth First Search)算法的基础上，针对动态固定信道分配(DFCA,Dynamic Fixed Channel Allocation) 算法进行研究，在保证连通性的前提下，为每个节点动态的分配固定信道，减少了链路之间干扰，提高了传输效率，同时考虑了新加入节点以及失效节点带来的问题.仿真结果表明，在发送速率较大、数据流数较多的情况下，DFCA算法较传统算法在吞吐量方面得到很大提高.

Mesh网络；多信道；多接口；动态分配；固定信道

0 引言

无线Mesh网络(WMN,Wireless Mesh Network)是一种新型的无线网络技术，与传统无线网络相比，WMN具有组网灵活、覆盖率高、容量大、前期投资少等诸多优点，近年来已成为研究的热点.随着WMN的研究与深入，其中的问题也慢慢暴露出来，最严重的问题是随着跳数的增加，WMN的延迟开始增大，吞吐量开始降低，QoS也变得难以得到保证.同时随着用户对WMN传输数据量和传输业务多样化需求的增大，现有的单信道单接口的结构已经满足不了多业务的需求，而多信道多接口的无线Mesh网络节点可以工作在相互之间并不干扰的正交信道上，极大地提高了WMN的传输速率和网络的容量，较好地解决了无线网络中存在的隐藏终端和暴露终端问题[1-2].

对于WMN制定合理的信道分配策略一直是多信道多接口WMN研究的重点，国内外学者做了很多研究工作.文献[3]分析了多信道多接口技术近年来在无线传感器网络中的应用，得出结论利用该技术可以有效地减少干扰并降低信道冲突，增加网络容量.文献[4]提出一种为所有节点分配相同信道的方案(CCA)，这种方案没有充分利用多信道的优势，且带来了很大的干扰.文献[5]提出了一种差异信道的分配方案，为不同节点分配不同的信道，在一定程度上降低了信道之间的干扰，但是该方案中信道的分配是固定的，破坏了网络的连通性.文献[6]在车载自组织网络中合理的实现了多接口多信道，提出了一种基于通信双方车辆节点信道切换队列的动态信道分配方法，较好地解决了车辆节点间通信信道的动态分配以及信道公平接入和分配不合理的问题，但该方案中没有考虑信道的独立性和干扰问题.文献[7]提出一种最小干扰的信道分配策略(MICA)，该方法充分考虑流量、距离、接口数等因素确定节点的优先级，并以此来进行信道的分配.文献[8]将最优信道带宽调制与多信道多接口技术相结合提出分布式流量感知的信道带宽调制，有效增加了频谱使用效率并提高了网络性能，但该方法并没有考虑信道的优化问题.文献[9]将多信道多接口应用到多播信道分配中，可以使无线Mesh网络的干扰程度最小化，并最大化网络吞吐量，但该算法没有考虑在实际无线路由器中可能存在增加、删除和移动以及多播成员可能自由地加入和离开多播组等动态情况，即没有考虑信道重新分配问题.文献[10]从多信道多接口无线Mesh网络传输容量入手，提出拓扑可靠性约束下的逻辑拓扑设计方法，以拓扑可靠性及网络路径跳数为约束条件，以最大容量最小干扰为优化目标，进而得到优化的逻辑拓扑.

针对现有研究存在的问题，本文提出一种基于连通性的动态固定信道分配策略，为节点动态的分配固定信道，固定信道用于数据的接收，备用信道处于“待接收”状态，随时准备用于数据的接收，其余信道为可切换信道，用于数据的发送.同时这三种信道可以在一定条件下相互转换，保障了网路连通性的前提下提高了网络吞吐量，降低了信道之间的干扰，并优化了网络信道的分配.

1 WMN干扰模型及图论模型

1.1 干扰模型

在WMN中由于复杂的无线环境，信道之间的相互干扰十分严重，网络的传输速率往往只能发挥其最大带宽的一部分.此外，WMN中的流量走向具有很大的不确定性，在某一阶段很容易出现某个或某些节点负载过重的问题，形成网络的瓶颈.

WMN中存在各种类型的干扰，根据业务流的不同可划分为流内干扰和流间干扰[11]，本文重点对流内干扰和流间干扰进行研究.

流内干扰(Inter Interference)是指在同一流的传输路径上传输的数据如果工作在同一信道上则由于相互竞争而会产生干扰.流间干扰(Intra Interference)是指不同流的传输路径如果和相邻传输路径工作在同一信道上则两者之间会产生影响.

由于WMN的环境较为复杂，对每个节点的SINR计算也是一个复杂和庞大的工程，同时由于背景噪声的不断变化，每个节点的SINR也处在动态变化之中，尤其是对于临界值的情况很难进行准确的处理，所以在研究中通常不采用物理干扰模型，而是采用协议干扰模型.

假设一个WMN由N个节点组成，现进行如下定义：

ni：WMN中的第i个节点，且1≤i≤N.

di,j：节点i和节点j之间的距离.

Rt：节点的传输距离，是两个节点在没有干扰的情况下能够通信的最大距离.

Ri：节点的干扰距离，是对其他节点带来干扰的有效距离，通常是Rt的2.2倍，默认所有节点的Rt、Ri都是一样的.

Ci：节点i可用的信道.

CUi：节点i正在使用的信道.

则节点j能够接收到节点i发送的数据需要满足以下条件：

di,j≤Rt，即两个节点之间的距离小于节点的传输距离.

∃k∈Ck,k∈Ci且k∈Cj，即两个节点之间存在相同的信道

∃/m≠i,j,CUm=CUi且CUm=CUj，dm,j≤Ri，即不存在节点m，使得m正在使用和i，j相同的信道，且m，j之间的距离小于干扰距离.也就是只有m正在使用和i，j相同的信道且m，j之间的距离小于干扰距离时，m才会对j产生干扰.

协议干扰模型其实就是一种逻辑的是非关系[12]，只要满足上述三个条件节点j能够接收到节点i发送的数据.由于WMN中节点弱移动性的特点，两个节点之间的距离一般是固定的，可能对其产生干扰的节点在不在其干扰范围内也是确定的，在进行算法研究时只需重点考虑信道问题即可，很适合WMN信道干扰问题的研究，如无特殊说明 则本文采用的是协议干扰模型.

1.2 图论模型

采用图论方式为WMN建立模型，通常认为所有节点都处在同一平面上，且各节点的传输距离Rt和干扰距离Ri都是相同的.

假设WMN中有m个可用的正交信道c={1,2,3,4…m}；Ii是节点i处的接口数，且1≤Ii≤m,如果两个节点在彼此的传输距离内，将信道分配给各个节点形成链路以后所有节点和链路就构成了网络拓扑G=(V,E)，其中V表示节点，E表示分配给节点之间的链路，这样就构成了连接图，连接图很好地表明了节点和信道之间的关系，但是节点之间的链路是否产生干扰不易从连接图上看出，如图1就是一个连接图.

在连接图的基础上，可以得到WMN的冲突图G′=(V′,E′)，其中V′表示节点之间的链路，如果两条链路之间存在干扰，则代表两条链路之间存在一条边，这些边组成集合E′.

假设图1连接图中的冲突域为2跳范围，则可以得到图2的冲突图.

冲突图很好地表明了链路之间的干扰关系，很适合WMN信道干扰的研究，结合协议干扰模型，本文采用上述假设，认为冲突域为2跳范围.

2 动态固定信道分配算法

2.1 BFS信道分配算法

当一个多接口多信道的节点A需要通信时，它的邻居节点至少要感知到节点A的一个信道才能正常通信，尤其是对于节点A是新加入节点的情况下.目前国内外研究的重点往往在于人为的将信道分配给两个节点，而两个节点之间如果彼此无法感知到对方的话是无法正常进行信道分配的.

对此文献[13]提出一种基于感知的信道分配算法，为每一个节点分配两种接口，一个用于固定信道传输，其余的用于可切换信道传输，节点对数据的接收是通过固定信道完成的， 具体内容如下：

每个节点维护一个邻居表和信道使用表，邻居表用以记录邻居节点固定信道的使用情况，信道使用表记录2跳以内邻居各个信道使用数量的情况，同时每个信道维护一个如图3所示的包队列.

图1 连接图

图2 冲突图

图3 包队列

每个节点定期的向邻居节点发送一个Hello包，由于使用多信道，在某个信道上发送的Hello包只会被正在使用该信道的节点接收到，所以节点需要在每一个可用信道上发送Hello包.Hello包包含了节点固定信道的使用情况和节点当前的邻居表，当一个节点收到邻居节点发送的Hello包时，节点根据包中邻居节点固定信道使用情况来更新自己的邻居表和信道使用表.当一个新的节点加入时，它不会和其他节点进行通信，直到这个节点在每一个信道上发送了自己Hello包.一个节点A将数据包发送给邻居节点B的具体流程如下：

1)节点A查询并更新自己的邻居表，找到节点B的固定信道使用情况.

2)若找到节点B的固定信道信息则将数据加入到节点B正在使用的固定信道的队列上等待传输.

3)若查找不到节点B的固定信道使用情况则进行等待，若超过设定的阈值则停止本次发送，同时将该数据在队列上清除.若在阈值范围内收到来自节点B的Hello包则进行步骤(2).

4)进行数据的发送，如果数据发送成功则结束本次数据传输，将数据从队列上清除；如果数据发送失败则进行步骤(1)，直至超时；超时则停止本次发送，同时将该数据在队列上清除.

以上算法适合于网络流量比较均衡的情况，但是WMN中存在着中心流量的情况，即某一时刻流量集中流向某个节点或某一时刻流量从某个节点流出，如图4所示当某个节点流量集中流出时，该算法可以充分发挥多信道的优势.假设节点A为中心节点，节点B、C、D、E为邻居节点，节点A、B、C、D、E的固定信道分别为信道a、b、c、d、e，流量是从中心节点流向邻居节点，则根据上述算法，节点A分别使用信道b、c、d、e同时发送数据，极大地提高了传输速率.然而当流量集中流向中心节点时，如图5所示，根据上述算法节点B、C、D、E都使用信道a传输数据，相当于是单信道传输，并没有发挥多信道的优势，基于上述原因，本文提出动态固定信道的信道分配算法DFCA(Dynamic Fixed Channel Allocation Algorithm).

图4 流量从中心节点流出

图5 流量从中心节点流入

2.2 DFCA信道分配算法

在原来的信道分配算法中，每个节点只有一个固定信道，其他节点如果需要向该节点传输数据则使用该节点的固定信道进行传输，当多个节点需要和该节点进行通信时则需要竞争使用信道.本文为节点动态的配置固定信道，设置多个固定信道和一个备用的信道，为节点配备信道的具体算法如下：

1)节点在发送Hello包之前先检查自己备用信道使用情况，并查询自己的信道使用表.如果备用信道正在被使用，则在信道使用表中挑选一个使用数量最少的信道作为自己新的备用信道，原来的备用信道转换为固定信道；如果检查到自己的固定信道存在空闲的情况，将这些信道以及备用信道的使用数进行比较，挑选一个数值最小的作为备用信道，其余信道成为普通的可切换信道，以上信息都会被加入到Hello包中发送出去.

2)如果增加的固定信道数量达到一定的阈值则不再进行增加，同时在固定信道中选择使用数量最少的信道作为备用信道.

图6 DFCA节点分配信道算法流程图

3)节点收到邻居节点发送的Hello包以后，根据包中邻居节点固定信道的使用情况进行查询，并根据其中的信息更新自己的邻居表以及自己的信道使用表.具体算法流程图如图6所示：

需要特别说明的是节点所有的信道都是空闲即没有进行数据传输时候的情况，假设现在某个节点A有一个固定信道正在通信，备用信道空闲，现在数据传输完毕，则在这两个信道当中选择一个信道使用数量少的作为备用信道，这时候节点A的Hello表中只存在一个信道就是节点A的备用信道，而没有任何的固定信道.

同时节点所维护的包队列的结构也发生了相应的改变.当节点正在进行通信，且节点的固定信道数量并未达到阈值时的包队列如图7所示，当节点没有进行通信时的包队列如图8所示，当节点的固定信道达到一定阈值时的包队列如图9所示.

当两个节点之间需要通信，例如节点A向节点B发送数据时，节点A会选择使用节点B的备用信道进行数据传输，具体过程如下：

1)节点A查询并更新自己的邻居表，找到节点B的备用信道使用情况.

2)若找到节点B的备用信道信息则将数据加入到节点B正在使用的备用信道的队列上等待传输.

3)若查找不到节点B的备用信道使用情况则进行等待，若超过设定的阈值则停止本次发送，同时将该数据在队列上清除.若在阈值范围内收到来自节点B的Hello包则进行步骤(2).

图7 包队列情况1

图8 包队列情况2

图9 包队列情况3

4)进行数据的发送，如果数据发送成功则结束本次数据传输，将数据从队列上清除；如果数据发送失败则进行步骤(1)，直至超时；超时则停止本次发送，同时将该数据在队列上清除.

具体算法流程图10所示：

此时节点B由于备用信道被使用，则会将备用信道转为固定信道，同时查询自己的信道使用表，挑选信道使用数最少的信道作为自己新的备用信道直到固定信道数达到一定的阈值，当固定信道数量达到阈值时，从固定信道中挑选信道使用数量最少的做为备用信道.

图10 节点间通信算法流程图

图11 新节点加入算法流程图

当一个新的节点加入到WMN中时，由于该节点并未指定备用信道，Hello包中的信息为空，其余节点无法发现该节点，更无法与之通信.则该节点在发送自己的Hello包之前先进行监听，如果在阈值范围内接收到了来自邻居的Hello包，则说明是加入已有的WMN，节点会根据收到的Hello包建立起自己的邻居表和信道使用表，再根据信道使用表的情况进行备用信道的选择，最后发送自己Hello包加入到网络当中；如果在阈值范围内没有收到任何邻居节点的Hello包，则说明这是一个全新的WMN，这个节点不必等到收到邻居节点的Hello包即开始定期广播自己的Hello包，同时随机选择一个信道作为自己初始的备用信道.具体算法流程图如图11所示：

当一个旧的节点离开或者失效时，这个节点已经不参与WMN的传输，但是该节点还是存在于邻居节点的邻居表中.为了解决节点失效的问题，各个节点再发送自己的Hello包时加入一个时间戳，节点设置一个自己的邻居节点最大存活时间.当节点收到邻居节点发送的Hello包时就更新存活时间，同时在更新自己的邻居表时检查邻居节点的时间戳，如果超过了最大存活时间则认为该节点已经失效了，将该节点从邻居表中删除，再更新自己的邻居表和信道使用表.具体算法流程图如12所示.

图12 节点失效处理流程图

3 仿真与性能分析

仿真实验场景设置为1 000 m×1 000 m的范围内随机分配50个Mesh节点，所有节点物理层采用IEEE 802.11a协议标准.对于DFCA算法，每个节点配置有3个射频接口，采用CBR流量模式，分别测试在发送速率、数据流数不同时与BFS算法及经典的DCA算法的比较.

图13表示CBR发送速率与吞吐量的关系，其中横坐标表示CBR的发送速率，纵坐标表示WMN的吞吐量.通过对比可以看出，当发送速率较小时，DCA、BFS和DFCA算法并无太大区别，当发送速率稍微有所提升时，DCA的吞吐量立刻出现明显的衰退，当发送速率提升至7MBPS时，BFS也开始出现衰退的现象而DFCA算法则直到9MBPS时才会衰退，DFCA在高速率传输时的吞吐量大约比BFS多15%左右.

图13 CBR发送速率与吞吐量的关系

图14 CBR数据流数与吞吐量的关系

图14表示CBR数据流数与吞吐量的关系，其中横坐标表示CBR的数据流数，纵坐标表示WMN的吞吐量.通过对比可以看出，当WMN中的数据流较少时，三种分配算法的吞吐量并无太大差别，但是随着数据流数的增加，DCA算法和BSF算法的吞吐量开始出现衰退，而且BFS算法的衰退程度要明显大于DCA算法，这是因为BFS算法是基于连通性的，当数据流数增大时，中心节点的问题变得突出，吞吐量受到严重限制.而DFCA算法虽然也存在中心节点的问题，但由于其采用了动态固定信道的分配策略，其受影响程度远远小于BFS算法.

4 结论

本文在BFS算法的基础上提出DFCA算法，该算法采用动态固定信道的策略来进行信道的分配，在不改变WMN连通性的前提下灵活动态的分配节点的固定信道，使得节点可以同时使用不同的信道进行数据的接收，很好的解决了中心节点的问题.仿真实验可以看出DFCA算法性能要优于BFS算法和DCA算法，尤其是节点发送速率变大，数据流数增多的情况下.

[1] So J,Vaidya N.Multi-channel MAC for ad hoc networks:handling multi-channel hidden terminals using a single transceiver[C].ACM International Symposium on Mobile Ad Hoc Networking and Computing，2004:222-233.

[2] 任远,董淑福,王耀国.数据链中隐藏终端问题的几种解决方法[J].通信技术，2009,20(5):54-56

[3] Wu Y S,Mihaela Cardei.Multi-channel and cognitive radio approaches for wireless sensor networks[J].Computer Communications,2016，94(94):30-45.

[4] Draves R,Padhye J,Zill B.Routing in multi-radio,multi-hop wireless mesh netws[C].Proceedings of the 10th annual international conference on Mobile computing and networking,2004:114-128.

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

[6] 张民,德敏,金康.一种多接口多信道VANET动态信道分配算法研究[J].计算机应用研究,2014,31(5):1516-1519.

[7] Subramanian A,Gupta H,Das S R.Minimum interference channel assignment in multi-radio wireless mesh networks[J].IEEE Transactions on Mobile Computing,2008,7(12):1459-1473.

[8] 李礼,张春元.多接口多信道无线网状网中流量感知的信道带宽调制算法[J].电子学报,2010,38(4).

[9] 邱振谋,姚国祥,官全龙,等.多信道无线 Mesh网络的多播信道分配算法[J].计算机工程,2011,37(6):107-109.

[10] 包学才,戴伏生,韩卫占.多接口多信道无线Mesh网络的逻辑拓扑设计[J].小型微型计算机系统,2015,36(6):1249-1254.

[11] Sandeep Kour Ahuja.Algorithms for routing and channel assignment in wireless infrastructure networks[D].The university of Arizona.2010.04.

[12] GuPta P,Kumar P.The capacity of wireless networks[J].IEEE Transactions on Information Theory，2010,46(2):388-404.

[13] Kyasanur P,Vaidya N H.Routing and link-layer protocols for multi-channel multi-interface Ad Hoc wireless networks[J].ACM SIGMOBILE Mobile Computing and Communications Review,2010,10(1):31-43.

(责任编辑郑绥乾)

DynamicFixedChannelAllocationAlgorithmBasedonConnectivity

YIN Feng-jie,MEI Bing-qian,YANG Hui,ZHANG Ying

(SchoolofInformation,LiaoningUniversity,Shenyang110036,China)

With the increase of hop,delay of WMN began to increase,throughput began to reduce,and the QoS is also difficult to guarantee.In numerous solutions to solve these problems,the channel allocation strategy based on multi-channel multi-interface technology can well solve the interference and the transmission rate problems in traditional WMN.But at present the study of multi-channel WMN tend to ignore the premise of mutual communication between nodes-connectivity.On the basis of the original breadth first search(BFS) algorithm,this paper put forward the dynamic fixed channel allocation(DFCA) algorithm.On the premise of guarantee connectivity,the algorithm allocated fixed channel for each node dynamically,reduced the interference between links,and improved the transmission efficiency.The condition which nodes are new or failure was also considered.Simulation results demonstrate that the algorithm of DFCA can improve the throughput than traditional algorithms in the case of large sending rate and more data flow.

Mesh network;multi-channel;multi-interface;dynamic allocation;fixed channel

TP 393

A

1000-5846(2017)04-0294-08

2017-09-01

辽宁省教育厅科学研究一般项目资助(项目编号：L2015204)

尹凤杰(1965-)，女，博士，教授，从事无线网络和通信网络优化控制研究；梅丙乾，男，硕士研究生；杨晖，女，硕士，副教授；张颖，女，硕士，讲师.