尹凤杰，彭永倩

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

0 引言

无线Mesh网络是一种新型的多跳无线网络，具有组网灵活、网络覆盖率高等优点.为充分利用正交信道，提高网络吞吐量和带宽利用率，信道分配已成为无线Mesh网络中的研究热点.根据802.11a和b/g的标准，分别有12个和3个不重叠的正交信道可供使用[1]，因此，对于一个接口来说，可以同时使用多个不重叠的信道.除此之外，还可让一个节点配备多个接口，这就使得每个节点可同时使用多个互不重叠的正交信道，但节点间传输队列过多，将存在信道间相互干扰与负载均衡问题.

在多接口多信道无线Mesh网络中，信道数量可能多于节点接口数量.为了使网络吞吐量达到最大，最佳的信道分配方式应该是在干扰可控范围内允许有最大数量的并发传输存在，然而，这已经被证明是一个NP(Non-deterministic Polynomial)问题[2].同时，信道分配还可能会影响网络的连通性[3]，目前主要是通过使用专用信道和同步信道的分配方式来解决这个问题.但是，同步信道分配需要保持时间同步，当传错率较高且重传机会有限时，将会导致整体性能降低[4].

文献[5]提出的BCMN/A协议用于簇内广播，并且对来自簇的每个数据返回ACK(Acknowledge Characte)确认，以便共同优化生存时间和传输延迟，实验结果表明，该协议可以将网络的生存时间提高8%以上，并且将网络延迟降低25%以上.文献[6]根据无线Mesh网络特点，提出一种基于AODV-MR的AODV-MRCR协议.该协议专门为网关流量保留一个信道列表，将网关流量和本地流量分开处理，因为网关流量具有较高的优先级，所以为它准备较多信道.然而对于本地流量，只保留一个固定信道，当本地流量较高时，这种方法效果并不理想.为了进一步提高效率，急需一种能够均衡网关流量和本地流量的解决方案，因此，本文提出一种基于负载均衡的多接口多信道分配算法DACA-LB，该算法通过选择干扰最小信道，动态接口调整来平衡负载，有效降低了平均排队延迟，实现负载均衡和网络吞吐量最大化.

1 DACA-LB框架结构

在无线Mesh网络中影响多接口利用率的一个重要因素是切换问题[7]，频繁切换会导致信道利用率降低，而静态配置会因流量动态变化导致性能欠佳[8]，本文综合考虑二者的平衡问题，采用动静结合的方式设计DACA-LB框架结构，如图1所示，该结构主要由信道分配、静态接口设置以及动态自适应接口调整3部分组成，其中每个接口都可以在接收模式与发送模式之间转换.

图1 DACA-LB算法框架图

为确保网络连通性[9]，设置2个不同的接口总是分别处在接收模式和发送模式，本文统称为静态接口，它们将使用专用信道进行传输，若传输队列变化大于专用信道所能承受的范围，则需要从预留出来的自适应信道中选择一条受干扰最小的信道进行传输.在选择工作信道之后，信道信息将广播给所有邻居节点[10].邻居节点保存该信息记录，并根据该条信息向邻居节点发送数据包.其中，专用信道是不会改变的，以确保邻居节点之间的连通性.对于信道分配，须遵循2个原则：1)同一节点的接口应尽量选择不同信道，以避免互相干扰；2)在理想情况下，优先选择一个受干扰最小的信道[11].

除静态接口外的其他接口，本文统称为动态自适应接口，其在默认状态下将全部处于发送模式.随着时间的变化，当静态接口负载达到一定阈值后，动态自适应接口将调整为接收模式或继续保持发送模式，从而可以均衡接口之间的负载.

2 算法设计

2.1 干扰计算

本文采用的干扰模型如图2所示，其中Rd、Rtx、Rcsin分别表示发射机和接收机之间的距离、传输范围以及干扰范围，一般情况下干扰范围比传输范围大，本文假设干扰范围以外的并发传输对目标传输的影响是忽略不计的.

图2 干扰模型

图2所示为节点A向节点B发送数据包时，节点C会受到来自节点A的干扰，由于节点D处于节点B的干扰范围内，因此，节点C和节点D应该避免和节点A同时发送，这样就可以消除隐藏终端问题.节点E在节点A和节点B的干扰范围之外，所以节点E和节点A可以同时传输，避免暴露终端的问题.通常，干扰范围内的节点数量大于正交信道的数量，因此，在其干扰范围内，可能找不到空闲信道.

2.2 信道分配

默认情况下，为静态发送/接收接口设置专用传输信道，并为专用传输信道设置一个能够承受的队列数量动态变化范围R∈[2r-1，2r+1](r为常数且r≥1)，当队列的数量变化超出范围R，则队列将切换信道.本文用Numq来表示当前信道中的队列数量，Numq越大，信道越繁忙，干扰可能就越多.当队列离开信道时，信道负载变轻，Numq减1；当有队列加入当前信道，则Numq加1.可以看出信道能够承受的队列数量动态变化范围R的中值为2r，若Numq变化大于2r，则节点切换信道.因此，应根据动态需求，将r设置为一个合适的值来控制信道的切换频率，用于避免队列调整过于频繁.

当一个节点需要切换到与其邻居节点相同的信道时，应优先选择使用次数最少的信道.本节在监听各个接口无线网络活动的基础上计算信道的状态，并通过公式(1)对信道的繁忙时间比P(ch)进行计算[12].

(1)

其中，tactive表示在时间T内信道ch的活动时间.

(2)

假设2个接口之间有n条传输信道，给各信道编号为chj(j=1，2，…，n)，且时间T内各个信道的活动时间用tactive(chj)表示，P(chj)则表示信道chj的繁忙时间比.N(chj)表示所有通过信道chj发送数据包的接口结合，且该集合内的所有接口都处于干扰源的干扰范围内.结合图2所示，假设节点B、C的某个接口均通过信道ch发送数据包，且2个节点均处在节点A的干扰范围内，所以有N(ch)={B、C}.图3给出了信道分配的完整过程，每个接口选择干扰最小的信道chmin传输数据包.

图3 信道分配流程图

2.3 静态接口

对于静态接口，本文采用专用信道来降低发送节点与接收节点之间的协调复杂性，在确保网络连通性的同时降低信道间的切换开销.根据DACA-LB算法的框架结构，静态接口应根据从邻居节点得到的发送(或接收)接口信息来使用信道，在此过程中，确认发送/接收接口尤为关键，若默认的发送/接收接口处理的数据包多于其他接口，不仅导致其他接口的利用率降低，而且吞吐量也会随着冲突率的上升而下降.

节点可以通过交换接口信息，向它们的邻居节点发送其选择的信道列表[15]，邻居节点信息交换过程如图4所示.通过与直接相连的邻居节点交换接口信息，节点A首先收集单跳邻居节点B至E的接口配置信息，节点B至E也会将收到的来自节点A的接口信息并转发给其各自邻居节点，使得节点A在获得其两跳邻居节点F至I接口信息的同时，还可获得三跳邻居节点G至M接口信息，以此类推，获得更多节点信息.

图4 邻居交换信息过程

2.4 自适应接口的调整

动态自适应接口，可用作发送或接收接口，以平衡所有接口间的负载.如果源节点存在大量队列等待发送，则需要更多的自适应接口调整为发送接口，节点收集和聚合信息则需要更多的接收接口.本文通过监听无线网络的活动状态，周期性地从各个节点中收集CPU利用率、内存利用率以及网络利用率，并根据这些参数计算出接口的动态阈值，依据阈值的大小均衡接口负载.本文定义使用接口i传输数据时的最大负载为Loadmax，接口i在为队列q服务时的平均负载值可用公式(3)求得.

(3)

其中，Dataq表示接口要传输的数据大小，ts、tr分别表示数据发送时刻和接收时刻.

根据节点收集到的信息可得到接口i使用信道ch传输数据时能够承担的最大负载利用率MaxU，可用公式(4)求得.

MaxU=Max(Cq，Mq，Nq)

(4)

其中，Cq、Mq、Nq分别表示CPU利用率、内存利用率和网络利用率，规定三者取值为0～1之间.

由公式(3)和公式(4)可得接口i在为队列q服务时能够提供的最大负载Loadmax(i，q)，可通过公式(5)计算.

(5)

假设最多只能有n个队列同时在接口i上工作，则可以通过公式(6)估计接口i传输数据包时的最大负载Loadmax.

(6)

同时假设接口i中正在运行的队列有qk，qk+1，…，qn，根据公式(5)和公式(6)可以计算出下一时间段接口能够承受的负载增量ΔLoad，其公式如下(7)所示.

(7)

根据公式(7)可以得出队列qk+1的最大负载不能超过ΔLoad，则可以把ΔLoad看作一个阈值，如果Loadav(i，qn+1)>ΔLoad，就需要把一个动态的接口调整为接收模式或继续保持发送模式，借此来缓解当前接口的流量负载，否则继续使用当前接口.

2.5 DACA-LB算法的实现总体流程

DACA-LB算法的总体实现流程如图5所示，若节点A向节点B发送数据，节点A中某一队列进入默认发送接口后，将判断队列负载是否超过接口的阈值，若超过则任意选择一个动态自适应接口传输此队列(若为接收过程，则需要将接口调整为接收模式)；若没有超过阈值，则继续使用当前默认发送接口.其次，根据2.2节中提到的方法判断当前队列是否需要切换信道，若需切换，则选择受干扰最小的信道；若无需切换，则保持当前信道即可，并根据最后的接收节点情况选择适合的接口，完成传输任务.

图5 DACA-LB协议整体流程图

3 实验及分析

本文通过在Linux环境下使用NS2-35评估所提DACA-LB算法的整体性能，在此次仿真实验中除了增加MAC状态统计模块外，无需做其他修改，且当接口在进行信道切换时，该接口不能发送或接收任何数据包.IEEE802.11a标准规定了12个可使用的不重叠信道，且在理论上它们之间不存在干扰，然而，由于技术的限制，在相邻不重叠信道上工作的接口也可能相互干扰[16]，因此本文将正交信道的数量设置为5到12.随着仿真时间的增加，节点间的负载也在不断增加，导致信道分配状态不稳定，为了更好地观察各种算法的性能比较，将仿真时间设置为400 s.本实验中接口数设置为2～5之间，小于可用的正交信道数目，其中，所有接口的传输距离为250 m，载波监听范围为500 m，其他仿真参数设置如表1所示.

表1 仿真参数设置

本文结合AODV路由协议从信道数量和接口数量方面对DACA-LB网络吞吐量性能产生的影响进行实验分析，并与现有协议进行对比.分析图6的实验结果可知，在接口数量不变的情况下，信道数量越多，其吞吐量增加越明显，但其增长速度逐渐放缓，原因是链路层协议可以很好地利用信道资源，但是由于接口数量的限制，导致可使用的信道数量有限，所以增长速度变得缓慢.除此之外，信道数量增多将会产生更多的信道切换，从而导致更高的网络开销.对于接口数量而言，当信道数量不变，随着接口数量的增加，其吞吐量越高.由此可见，增加接口和信道数量均可提高网络吞吐量.但是，若信道数量足够多，却没有与之相匹配的接口数量，则不能提高吞吐量，反之亦然.

图6 具有不同信道数和接口数的吞吐量变化

本文通过将DACA-LB算法与不同路由协议相结合，对其性能进行评估，分别是：a)DACA-LB+AODV[17]；b)DACA-LB+WCETT[18]；c)AODV-MR，1种结合链路和路由协议的跨层解决方案.本次模拟实验设置在1 000×1 000 m2的区域中随机分布100个节点，所有节点均配备4个接口，且12个正交信道全部可用.

在所有节点中统一选择源/目的对，并将目的对的数量设置为50～500，以显示不同流量负载下的性能.分析图7的实验结果可知，DACA-LB+AODV与DACA-LB+WCETT的性能表现十分接近，AODV-MR性能表现最差.这是因为AODV-MR算法只是进行简单的信道分配，没有考虑负载平衡问题，所以其性能较差.其次，可知DACA-LB+WECTT组合的吞吐量并没有明显高于DACA-LB+AODV组合的吞吐量，这是因为在WCETT路由协议中并没有考虑信道分布和信道切换的开销，除此之外，随着网络负载增加到一定数值，大多数信道和接口已经被利用，二者的吞吐量趋于一致.

图7 不同随机源/目的对情况下的吞吐量变化

任意选择网络中5个节点，将其设置为具有比其他节点较高流量负载的网关，网络中的其他节点将随机选择附近的网关接入互联网，图8为3种算法随着并发流数目的增加，网络吞吐量变化的趋势图.分析可知，3种算法的吞吐量变化趋势与图7结果相似.由此得出结论，场景DACA-LB+AODV和DACA-LB+WCETT的性能相近，并且二者性能均优于AODV-MR.当并发流数量较少时，三者性能相似，随着流量的增加，DACA-LB 的负载均衡可以大幅度地提高整体性能.图7与图8的2种仿真实验结果表明，本文所提DACA-LB算法能够动态平衡流量负载，获得较高的吞吐量，且能与现有的路由协议实现较好地结合.

图8 5个网关情况下的吞吐量变化

除此之外，本文还通过网络吞吐量和平均丢包率2种性能指标，将DACA-LB算法与ELIA和LBIA-OCA信道分配算法进行对比分析[19]，以验证所提算法的有效性.ELIA和LBIA-OCA算法均是通过选择受干扰最小的信道进行传输，同时考虑节点接口间的负载均衡，但执行方式与本文所提算法不同.在此次对比实验中，将并发流数目范围设置为4～22，报文发送速率为200 Kbps.随着流量的增加，网络吞吐量的变化如图9所示.

图9 不同信道分配算法下的吞吐量变化

分析图9的实验结果可知，性能排序为：DACA-LB最优，ELIA次之，LBIA-OCA最差.在3种算法中，网络吞吐量随着流量的增加几乎呈线性上升趋势，但上升速度逐渐变缓，其中，DACA-LB和ELIA的性能均明显优于LBIA-OCA算法.当网络负载较轻，3种算法产生的网络吞吐量几乎相同，但在LBIA-OCA算法中，随着流量的增加，为相邻队列分配相同信道的可能性随之增加，进而数据包在传输之前必须在缓冲队列中等待较长时间，且可能发生更多回收，这就导致较差的网络性能.由于DACA-LB算法考虑了节点接口间的负载均衡，使得网络并没有随着负载的增加陷入瓶颈，而是继续保持上升趋势.

分析图9和图10的实验结果可知，3种算法的平均丢包率与网络吞吐量是成反比的，即丢包越多，网络吞吐量越低.同时，随着并发流的增加，DACA-LB算法的丢包率明显低于其他2种算法，表现出更佳的性能，这主要得益于DACA-LB算法充分利用信道和接口资源，降低了丢包率.

图10 不同信道分配算法下的平均丢包率变化

4 结束语

本文提出一种基于负载均衡的多接口多信道分配算法DACA-LB，该算法通过平衡负载来使网络吞吐量最大化，从而提高整体性能.通过动态自适应的接口分配方式，在保证用户需求的基础上，提高接口利用率，有效减少请求响应时间；该算法部署在所有节点上，以分布式方式控制数据传输，且上行链路与下行链路数据均由高负载水平汇聚节点的无线接口来接收和发送.仿真结果表明，DACA-LB算法能够在保证平均丢包率较小的情况下实现较大的吞吐量，提高网络性能.但该算法目前只能在接口间平衡接收和发送流量的负载，如何平衡节点间的流量负载将作为下一步研究重点.