信道分配与负载均衡相结合的多信道路由协议

栾渊鑫，叶竹君

(哈尔滨工程大学 信息与通信工程学院，哈尔滨 150001)

信道分配与负载均衡相结合的多信道路由协议

栾渊鑫，叶竹君

(哈尔滨工程大学 信息与通信工程学院，哈尔滨 150001)

为了降低邻居节点间的信道冲突，最大化并行传输的信道数目，从而提高移动Ad hoc网络的性能，提出了一种信道分配和路由选择相结合的多信道路由协议LBMMR.LBMMR协议在MAC层和路由层间进行实时的信道状态的信息交互，节点根据信道状态列表，在每一跳中始终选择信道干扰指数最小的信道，从而减少与邻居节点的信道干扰和冲突.在路由选择方面，以信道已用带宽和节点接口队列长度作为负载均衡的判据，在全路径范围内找到一条负载均衡且干扰最小的路径.仿真结果表明，与现有的多信道路由协议相比，LBMMR在网络吞吐量、端到端时延等方面具有明显的性能提升.

Ad Hoc网络；信道分配算法；路由算法；多信道多接口；负载均衡

移动Ad hoc网络是由一组具有无线收发装置的移动节点组成的自组织通信网络，节点间不需依赖其他网络基础设施便可以自主的进行通信[1].多信道技术是解决无线网络的干扰性、提高网络容量的最有效、最常用的技术.无线多跳网络中的隐藏和暴露终端，以及无线信道相干性限制了无线网络的容量，采用多信道技术可降低这一影响，多信道技术在信道利用率和网络容量方面都有显著的提高，所以多信道技术成为了当前和未来无线通信领域的一个重要发展方向.

目前在无线自组织网络中多信道技术研究主要集中在多信道路由协议和多信道跨层设计方面[2-3].文献[4]提出了多射频多信道 WMN 网络中的公平带宽分配问题，以网络效用最大化来建立跨层优化，将信道分配作为优化变量，以降低干扰为目的在多信道传输中.文献[5]将信道分配和路由选择联合优化，在路由建立过程中动态分配信道，联合信道分配的跨层优化可以明显提升网络性能.文献[6]提出一种多接口链路质量源路由MR-LQSR，MR-LQSR是DSR协议的改进版本WCETT考虑了路径总时延和瓶颈信道的时延.MCR[7]参考了MR-LQSR的路由度量策略，使用了比信道数少的接口数，能够支持网络拓扑变化.文献[8]提出了基于机会路由的多信道路由协议，综合考虑接口和信道分配、数据流传输调度等问题并提出一个按优先级的机会转发算法以提高网络的吞吐量.

1 J-CAR协议描述

J-CAR[9](Joint Channel Assignment and Routing Protocol)是一个在AODV[10]基础上改进而来的按需式分布多信道路由协议.相邻节点在控制信道上周期性的广播HELLO交换包，用来相互确认.当源节点有数据要发送给目的节点时，它首先在自己的路由列表中查找到目的节点的路由，如果路由存在并有效，则立即开始发送数据；如果没有找到有效路径，节点启动RREQ(路由请求)包，并携带其建议发送和接受的信道用于该路由.每个中间节点会检查所建议信道的可用性，附加自己的信道选择在RREQ中并广播给下一跳节点.当目标节点收到第一个RREQ，它将启动一个定时器用于发现其他不同路径的RREQ包.当定时结束时，目的节点选择最宽路径，并通过反向路径发送一个RREP(路由应答)包给源节点，在确认选择路径的同时，将对应信道分配到各个节点.

1.1 接口分配与信道分配

J-CAR中一个节点配有多个无线网络接口，其中有一个接口被分配到固定的控制信道进行操作，被称为控制接口.它主要用于传播控制信息和广播包.剩下的接口被称为数据接口，用于在不同的数据信道上传输数据.J-CAR在执行所选择的数据信道时采用802.11四次握手机制即RTS-CTS-DATA-ACK.相应的在控制信道的负载会减轻，因为控制信道上只包含路由信息和HELLO包.剩余的容量可以被用于承载数据包来提高信道的利用率.控制信道有一个数据发送概率P：当p=0时，该控制信道不会用来传输任何数据分组；当p=l时，控制信道和其他数据信道一样，有同等的机会被选中传输数据分组.对比预先分配接收信道的机制，J-CAR需要更少的信道数.

在数据传输过程中，节点基于信道干扰指数选择最佳的信道进行通信.J-CAR提出的信道干扰指数不会主动的感知信道，它依赖于定期发送HELLO报文对信道状态进行估计，这使得它可以充分利用数据接口发送分组.由于干扰参数将协议和物理干扰模型考虑在内，相比单一的干扰模型，J-CAR具有更好的信道选择.此外，J-CAR的干扰参数可以使用适当的路径损耗指数适应不同的传播条件.

1.2 长度受限的最宽路径路由

带宽可能是路由最重要的性能指标，但确定无线链路的剩余带宽是不容易的.不同于大多数分布式联合信道分配和路由算法如文献[11-12]，只是简单的寻找最短或者延迟最小的路径.J-CAR使用信道干扰指数为路由的链路带宽做启发式度量.路径带宽是由具有最大参数值(瓶颈)链路来确定.对于一个双向路径，正向路径是由源节点向目的节点发起的连接，而反向路径与正向路径相反.J-CAR可以提供不同的优先级，以找到一个更好的正向/反向路径，J-CAR重点放在寻找带宽最宽的正向路径.

路由过程中，瓶颈链路的干扰指数被记录在RREQ中.由于RREQ是被广播的，多个RREQ包(每个对应一个不同的路径)将先后到达目的节点.当第一个RREQ包到达时，节点不会立即回复RREP，目的节点此时会启动一个delay_RREP定时器来记录随后到达的RREQ包.在定时器超时之后到达的RREQ包将会丢弃，因为它有较长的传播时延.在所有接收到的RREQ包中，用最小跳数-距离(hmin)的路径将会被确认.一般情况下，一个较长跳数-距离的路径分组碰撞的概率较高，容易对其他路径产生更多干扰.为避免选择过长的路径，一个可调节的阈值(TH)被使用.所有路径长度小于hmin+ TH跳数的路径将被作为候选路径.目的节点在候选路径中选择带宽最宽的路径，并发送RREP确认此路径.

值得注意的是，最宽路径选择同样发生在每个中间节点，使得每个节点都只沿最宽路径转发RREQ.这样虽然可以进一步提高路由性能，但同时也会产生一个较大的时延因为中间节点必须等待一定时间来识别该RREQ的最宽路径.

1.3 J-CAR协议存在的不足

J-CAR虽然在很多方面有不错的表现，但仍然存在着不足之处.首先，J-CAR协议的信道分配方式使节点根据链路的干扰参数选择信道，并没有实时地参考MAC层的信道状况，这种信道分配方式是不完善的.其次，由于J-CAR在路径选择方面采用的是长度受限的最短路径策略，由于移动Ad hoc网络具有很强的动态性，路由建立后链路依然有可能发生重大变化，这时协议不能有效的感知变化从而做出相应的调整.最后，J-CAR没有对路径进行负载均衡，原文作者认为J-CAR已经在多跳路径中选择了带宽最宽的路径，便没有必要来消耗额外的资源对所选路径进行负载均衡了.然而一个好的路由选择算法，应该避免某些节点或链路负载过重而另外一些节点或链路出现空闲的情况，如果大量的数据业务集中在某些节点，必然会使这些节点负载过重从而导致网络瓶颈或拥塞，使得网络性能下降.

2 基于节点负载的跨层多信道路由协议

2.1 协议的改进

针对以上问题，本文提出一种新的信道分配与路由选择相结合的多信道路由协议LBMMR(Load Balance Multi-channel Multi-interface Routing)，该协议采用动态的接口分配策略，将接口分为控制接口、发送模式接口和接收模式接口.控制接口用于接收和发送控制信道上的信息，在发送模式下的接口可以切换到不同的数据信道将数据包发送到不同的邻居节点，但它被禁止接受数据包.在接收模式下，接口只能工作在一个单独的数据信道，主要用于数据接收和有限的数据发送.在信道分配策略方面，LBMMR协议在MAC层和路由层间进行信道状态的信息交互，节点在MAC层实时的收集在其通信范围内数据信道的状态信息，并建立信道状态列表.节点根据信道状态列表，在每一跳中始终选择信道干扰指数最小的信道，并通过设计新的MRTS/MCTS框架，在控制信道来完成数据信道的预约，这样有效的避免了多信道隐藏节点问题.最后在路由选择方面，将节点发送接口队列长度和信道可用带宽，作为度量值来衡量节点的负载.信道已用带宽越大，接口队列越长说明节点的负载越重.通过探测机制，收集链路的负载信息，在多条路径间动态的调整负载分配，实现了多路径间的最大程度上的负载均衡.

2.2 基于信道干扰指数的多信道分配机制

LBMMR协议通过MAC层和路由层间进行的信道状态信息交互，节点在MAC层实时的收集在其通信范围内数据信道的状态信息并建立信道状态列表.当一个节点需要跟另一节点相互通信时，它通过广播包将路由层上的路径信息传递给MAC层.广播是Ad hoc网络重要的活动.在LBMMR中我们通过广播信标BB(Broadcast Beacon)来宣布广播包到来的时间.

在数据传输过程中，节点基于信道干扰指数选择最佳的信道进行通信.在不考虑节点感知的情况下，我们定义信道i的干扰指数为：

(1)

k是干扰范围，γ是路径损耗因子，usage(i,j)是信道使用列表.每个节点维持一个信道使用列表usage(i,j)用来记录节点使用信道i在j跳范围内发送的数据量.i∈[0,n-1]，j∈[0,k+1]当j=0，usage(i,j)是节点当前状态下的信道使用情况.每个节点计算它的发送负载，并利用周期性的广播HELLO包来与其相邻节点交换它的发送负载.节点通过广播包上的路径信息，根据式(1)在每一跳中选取信道干扰指数Indexi最小的信道进行通信.并通过设计新的MRTS/MCTS框架，在控制信道上完成信道的竞争和预约.

LBMMR分配了专用的控制信道用于数据信道的竞争和路由信息的广播，图1中C1、C2代表数据信道，C0代表控制信道.本文采用IEEE 802.11 RTS / CTS的握手机制的概念来实现多信道在移动Ad hoc网络中的传输机制.在LBMMR中我们取名为MRTS/MCTS，不同于802.11RTS/CTS握手机制，更多的信息需要被使用来表示其他数据信道的使用情况.

图1 LBMMR数据传输图

图2 MRTS帧格式

MRTS控制帧格式如图2所示，接收地址代表接收节点的序列号，发送地址代表发送节点的序列号，通过数据包信息计算出各个信道的干扰指数Indexi并将干扰指数的数值计入信道可用列表中.当节点收到一个MRTS帧时，它首先比较MRTS信道可用列表中的信道状态，从中挑选出信道干扰指数最小的信道作为数据信道，并将所选信道和信道占用时间等信息放入MCTS包中回复给发送节点，若所选信道在发送方一端也可用则信道分配成功.否则预选信道不能被接受.接收节点将回复CRI，要求延迟twait后重新竞争信道.MCTS和CRI结构如图3所示.

图3 MCTS和CRI的帧结构

2.3 动态负载均衡路由机制

为实现动态的负载均衡，本文采用文献[13]建立的探测机制，新增了一对路由控制报文：LDQ和LDP即负载监测请求包和应答包.他们的作用是用来实时的记录路径上节点的负载信息，LDQ是由发送节点在路由建立后立即发出的请求包，目的节点在收到LDQ包后回复LDP应答包给发送节点，LDQ和LDP在经过中间节点是便会记录各节点的负载信息，并将其传递给发送节点和目的节点.

本文将信道已用带宽和发送接口队列长度作为衡量节点负载的重要参数，他们是通过负载监测包LDQ和LDP得到的数值.信道已用带宽和发送接口队列长度能够准确的反映信道的使用情况，信道已占用带宽越大、发送接口队列长度越大说明节点的负载越重；反之，则越轻.信道的已用带宽定义如下：

(2)

Tbusy是在给定时间T内，信道处于发送、接收和碰撞等繁忙状态的总时间.将两个时间的比值乘以信道理论的最大带宽便是信道的已用带宽.路径A的信道已用带宽为各节点信道已占用带宽的总和即：

(3)

其中:Boccupied(k)表示节点k的已占用信道带宽，路径A的队列接口长度LenlinkA为各节点队列的总长度值：

(4)

由此可得出路径A的总负载状况值LRrouteA由信道已占用总带宽Bload_linkA和队列接口总长度LenlinkA组成的，其计算公式如下：

(5)

其中:α为权重值，α∈[0,1].LR越大，表示链路的负载越重，链路的整体性能越差.在计算LR准则过程中，首先将信道已占用总带宽和队列接口总长度进行归一化，然后进行加权求和.α代表选路权重，当α=1时改进机制退化为完全由信道已用带宽决定.反之，当α=0时意味着完全采用队列接口长度作为选路标准.目的节点综合考虑信道已用带宽和队列接口长度，选择最优路径，并回复REEP消息，源节点收到RREP后完成路径建立过程.通过MAC层和路由层间进行信息交互，将路径信息通过广播包的方式传递给MAC层，在所选路径的每一跳中选择信道干扰值最小的信道进行数据传输并完成信道分配，这样增加了并行传输的数据对，从而提高了网络性能.

3 仿真结果与分析

本文在NS2.34下对LBMMR的性能进行了仿真实验，并且与J-CAR、MCR进行了对比.路径损耗因子γ= 4，用于利用公式(1)确定信道的干扰参数.在MAC层实现了信道分配和MRTS/MCTS冲突回避机制，在路由层建立了基于探测机制的负载均衡，从而实现了动态的调整网络负载.其中参数α=0.7，因为信道已用带宽更能够有效的反映信道当前的状况，节点接口队列长度可能不完全属于同一条路径，但它预示着未来一个阶段链路的负载程度同样不可忽略其影响.

3.1 静态单跳场景

静态单跳仿真场景如下：16个节点随机分布于200 m×200 m的范围内，每个节点有3块网络接口，全网共有4个不重叠的信道，所有UDP产生的CBR业务流为1 000 packet/s，即4 MB/s，信道的传输速率为6 MB/s.仿真场景中共设置7对业务流，仿真时业务流随机的选取发送节点和目的节点，仿真时间为60 s，为了减小随机误差，仿真结果取20次实验结果的平均值.

将LBMMR与J-CAR、MCR在不同业务负载下进行比较，系统的总吞吐量如图4所示.由于在单跳网络中，路由的影响很小，因此网络性能很大程度上取决于信道分配策略.由于MCR采用了信道预分配策略，信道分配是在路由建立之前完的，因此接收节点可能使用相同的信道在接受数据时.相比之下，J-CAR平均分配各信道的数据流，选择信道干扰指数最小的信道使系统性能有所提升，但J-CAR协议仅通过send channel list(S-list)和receive channel list(R-list)来完成信道协商，信道分配机制不够完善.LBMMR协议在MAC层和路由层间进行信道状态的交互，并通过设计新的MRTS/MCTS框架，在控制信道完成数据信道的预约，有效降低了信道间的干扰和冲突，呈现出最佳的网络性能.

图4 静态场景总吞吐量

3.2 动态多跳场景

本节在多跳动态场景中来研究路由选择和信道分配的综合影响，仿真使用3块网络接口和12个不重叠的物理信道，信道的通信距离为250 m.随机放置50个节点在700 m×700 m的区域内.运动方向和速度随机生成，运动速度v为0～25之间的随机值，服从均匀分布，改变v的大小，观察其性能的变化，每次模拟随机产生5条数据流.见图5、6.

图5 动态场景端到端延迟

图6 动态场景总吞吐量

三种协议在不同节点最大移动速度下的平均端到端时延和总吞吐量如图所示.由于网络的动态特性，节点较高的移动速度会导致更多的路径故障，从而使网络中原有的路由逐渐失效.此时发送节点便需要寻找新的路由.LBMMR通过实时的检测网络中各节点的负载，可以使负载较轻的节点及时的接入路由中，这样有效的避开了拥塞程度较高的路径，从而有效的降低了端到端时延.同时由于避开了网络中的拥塞节点，并且保持了路由层和MAC层实时的信道信息交换，采用了动态的信道分配机制，在多个信道中选择信道干扰指数最小的信道避免了信道间的干扰和冲突，提高了网络的总吞吐量.

4 结 语

本文研究了多信道多接口的路由协议.为降低共用信道的干扰，提高网络性能和服务质量.本文在J-CAR协议的基础上改进了多信道分配机制，并建立了具有动态探测机制的路由负载均衡，提出一种新的多信道跨层路由协议LBMMR.仿真结果表明，改进后的LBMMR较J-CAR和MCR在端到端时延和系统总吞吐量性能方面均有了明显的提升.但由于LBMMR协议实时的监测节点的负载情况，导致路由的维护成本增加，另外算法中用到的参数，如路径损耗因子γ，负载参数α都需要进一步的优化.在以后工作中，应考虑改进已有的路由选择算法，降低路由开销，从而进一步提高网络性能.

[1] 于宏毅. 无线移动自组织网[M]. 北京: 人民邮电出版社, 2005.

[2] IEEE Std 802.11. Wireless LAN Medium Access Control (MAC) and Physical Layer(PHY) specifications[C]// NewYork : Institute of Electrical and Electronics Engineers, 1997.

[3] ZHAO C X, WANG R C. Multi-channel Assignment in wireless mesh network [J]. Journal of Nanjing University of Post and Telecommunication, 2010, 30(1): 18-25.

[4] RAD A H M, WONG V W S. Cross-layer fair bandwidth sharing for multi-channel wireless mesh networks[J]. IEEE Transactions on Wireless Communications, 2008, 7(9): 3436-3445.

[5] CHIU H S, YEUNG K L, LUI K. J-CAR: an efficient joint channel assignment and routing protocol for IEEE 802.11-based multi-channel multi-interface mobile ad hoc networks[J].IEEE Transactions on Wireless Communications, 2009, 8(4): 1706-1715.

[6] TARIQUE M, TEPE K. Minimum energy hierarchical dynamic source routing for mobile ad hoc networks[C]// Ad Hoc Networks, 2009: 1125-1135.

[7] 梁文峰. 多信道无线 Ad-Hoc 网络路由协议研究[D]. 成都: 电子科技大学, 2011. 4-22.

[8] CHIU H S, YEUNG K L, LUI K S. J-CAR: An Efficient Joint Channel Assignment and Routing Protocol for IEEE 802.11-BasedMulti-Channel Multi-InterfaceMobile Ad Hoc Networks [J].IEEE Transactions on Wireless Communications, 2009: 1706-1715.

[9] D STAROBINSKI, XIAO W, QIN X,etal. Near- Optimal Data Dissemination Policies for Multi- Channel[C]//Single Radio Wireless Sensor Networks, Proceedings of the IEEE International Conference on Computer Communications, 2007: 955- 963.

[10] 曹 勇. 多信道自组织网络容量和路由协议研究[D]. 西安: 西安电子科技大学, 2008. 7-46.

[11] SHU T, CUI S, KRUNZ M. Medium access control for multi-channel parallel transmission in cognitive radio networks[C]// IEEE GLOBECOM Conference, 2006. 1-5.

[12] ZHEN Y, WU D, SUN B,etal. Parallel Packet RedundancyMechanism Based on Link Lifetime Estimation in MANET[C]// Wireless Communications, Networking and Mobile Computing. 2008. 1-4.

[13] 张理轶, 樊晓平, 廖志芳. 一种适用于移动自组网的多径多信道负载均衡路由协议[J]. 小型微型计算机系统, 2013, 34(8): 1763-1767.

A multi-channel routing protocol for channel assignment and routing algorithm joint

LUAN Yuan-xin, YE Zhu-jun

(School of Information and Communication Engineering, Harbin Engineering University, Harbin 150001, China)

In order to reduce co-channel conflict and maximize the number of parallel transmission, thereby improving the performance of mobile Ad hoc networks, this paper proposed a multi-channel routing protocol LBMMR which combines with channel assignment and routing. The channel state and information can be exchanged between MAC and routing layer in real time. In order to reduce channel interference and conflicts with neighboring nodes, each node according to the channel usage list has always selected the least channel interference index at each hop. To find the least interfered path for network load balancing on a global scale, LBMMR employed occupied channel bandwidth and the length of the node’s interface-queue as the reference of the node routing. Simulation results showed that compared with the existing multi-channel routing protocols, LBMMR provided much higher system total throughputs and shorter end-to-end packet delays.

Ad hoc network; channel assignment; routing; multi-channel multi-radio; load balancing

2014-04-23.

栾渊鑫(1987-)，男，硕士，研究方向：无线通信网络.

TP393

A

1672-0946(2015)05-0583-06