多信道多接口智能路由协议研究

刘玉梅，叶竹君，栾渊鑫

哈尔滨工程大学信息与通信工程学院，黑龙江哈尔滨 150001

多信道多接口智能路由协议研究

刘玉梅，叶竹君，栾渊鑫

哈尔滨工程大学信息与通信工程学院，黑龙江哈尔滨 150001

多信道多接口可以降低信道共用的干扰并且提高多跳无线Ad Hoc网络的吞吐量。提出一种信道分配与路由选择相结合的多信道多接口智能路由协议DMMR，DMMR综合考虑了链路生存时间、跳数以及节点距离。用LP标准，使路由选择标准在链路生存时间和最短路径之间取得均衡，这样选择的信道在移动环境中更加具有可靠性；用基于距离的信道选择算法选择信道，该信道选择算法首先估算节点间距离，根据估算到的距离选择合适的信道进行数据传输，从而提高信道的空间复用。和已经存在的路由协议相比，仿真结果表明在移动多跳Ad Hoc网络中该协议能够降低平均端到端延迟并且提高网络的吞吐量和包到达率。

Ad Hoc网络；信道分配算法；路由算法；多信道多接口；跨层

多接口多信道路由协议是指网络中每个节点配置多个半双工无线网卡，这样可以使得节点同时接收和发送数据，还可以更加有效地传输路由控制包。由于硬件技术的快速发展，无线网卡的成本越来越低。针对多信道多接口的移动Ad Hoc网络研究也越来越多。信道分配是Ad Hoc网络中一个重要的研究内容，信道分配算法已经取得大量研究成果，例如：图着色算法、整数线性规划方法和本地搜索算法［1-2］等，这些算法大都是以如何最大限度地减少链路的干扰来提升网络的吞吐量为出发点合理地分配信道。传统的路由协议往往都是以找到路由为目标，没有考虑到路径上各个节点的信道分配。文中将信道分配与路由选择相结合，在路由选择的过程中，综合考虑链路生存时间和跳数，在信道分配的过程中采用基于距离的信道选择方法，提高了网络的包到达率。

1 多信道路由协议相关研究

多信道路由协议是Ad Hoc网络中一个重要的研究内容，有许多研究者设计了Ad Hoc网络多信道路由协议。文献［3］提出的CA-AODV将信道选择信息放在路由控制包和路由表中，利用寻路和路由回复为每条路由选择不同的信道，这样一个节点的k个邻居节点内如果有n条数据流就分配n×（k＋1）个正交信道。文献［4］对CA-AODV协议进行了扩展，通过引入一个额外的Channel Taken消息为在节点干扰范围内网络的所有不同活动节点分配不同的信道。这2种协议在建立路由时完成信道分配，实现简便。但没有实时参考MAC层的信道情况，信道分配不够优化。文献［5］提出一个将分布式信道分配和路由协议结合的协议J-CAR，也是按需地在建立路由时分配信道。该协议中节点具有多个收发器，通过send channel list（S-list）和receive channel list（R-list）协商信道。该协议实现复杂，同样没有实时地参考MAC层信道状态，信道分配不完善。

2 多信道跨层路由机制设计

2．1 链路生存时间估计机制

在许多军事应用中，节点可以通过一些例如GPS的设备来获得自身的位置。假设每个节点都有相同的传输范围，当一个节点在另一个节点的传输范围内时，他们之间就可以进行通信。假设在计算过程中节点的相对速度和方向是保持不变的，所以链路生存时间的估计过程就如图1所示，R代表节点的通信范围。利用AODV协议中Hello分组的传递来估算收发节点间的生存时间，网络中的节点周期性的发送Hello分组，在Hello分组中写入当前时刻节点的位置信息，接收节点利用先后到达的2个Hello分组中携带的位置信息，估算发送节点的运动速度与运动方向，从而估算出收发节点间的生存时间。

图1 节点的运动过程

为了计算2个移动节点和参考节点S的链路生存时间，等间隔选取3个接收信号强度样本点，分别为A、D和E，其在时间域内满足Δt1＝Δt2＝Δt。周期发送的Hello分组可以获得样本点的位置（x，y，z），因此di、dj和dk可以被计算出来。使用正余弦公式，链路生存时间可以根据式（1）～（3）被估计出来［6］，就可以算出收发节点间生存时间。

2．2 具有环境感知功能的多信道分配机制

为研究方便，暂不考虑一个网络接口在多个信道上切换的情况，也就是说将研究范围限定在如下情况：网络中的节点具有多个接口，即有多个MAC地址和物理地址，网络中可以使用的信道数为N，使节点的接口数等于信道数N，每一个接口都对应一个信道而不需要切换。在某一个信道i上，节点对应的接口i可能处于发送状态、接收状态或监听状态。为后续的研究能够更加深入，假设网络中信道的质量可以不相同，即同一时刻，不同信道具有不同的信噪比。

2．2．1 信道环境感知原理

信道环境的变化会对网络的性能产生很大影响，信道环境的变化具体体现在信道信干比上，用SINR表示，定义SINR为

式中：Psignal表示有用信号的功率；Pnoise表示信道噪声功率；Pinterface表示干扰功率，由于同一时刻可能存在多个干扰，所以干扰信号的总功率为多个干扰功率求和。SINR能够准确反映当前信道的信道状况。SINR越大，信道环境越好。SINR本是物理层参数，在这里借鉴跨层的概念，通过跨层调用将SINR传递到路由层，作为信道分配的依据。

在AODV路由协议中，节点周期性的发送Hello分组用来维护路由，同样可使用Hello分组来测量信道质量。在AODV协议中，每个节点都维护一张邻居节点列表，用以记录通信范围内的节点的信息，在邻居节点列表条目中增加一项名为nb_sinr的记录。nb_sinr为N维数组，N为信道数，nb_sinr［i］表示邻居节点使用信道i时的信噪比。当节点在信道i上接收到某节点发送的Hello分组之后，根据Hello分组接收功率的大小计算当前信道的信噪比SINR，将信噪比写入邻居节点列表中的nb_sinr［i］中。

当节点需要向某邻居节点发送数据分组或者路由应答分组时，检索邻居节点列表，找到各信道对应的信噪比值，用SINR的值作为选路的重要依据。但是，当多个节点需要同时发送数据时，往往会同时选择信噪比最高的信道，这样会导致竞争节点同时在高信噪比信道上传输数据，从而导致冲突的发生。为了避免这种情况，采用基于距离相关的信道分配机制［7］来解决这个问题。

2．2．2 基于距离相关的信道分配机制

多信道与单信道相比，最大的优势在于可以同时通信的数据流数目增加。为了实现这个目标，就需要让同时通信的收发节点对数最大化。

基于距离的信道分配机制的基本思想是：距离较近的节点对在正确接收的前提下使用频率高的信道，把能够传输较远的信道留给长距离的节点对进行通信。在上述的情况下，2个节点对就能够同时进行通信，提高了并行传输的数据对，从而提高网络的性能。

节点A要给节点B发送数据，节点A发送信道请求包给节点B，请求包中携带本节点的信道空闲列表和需要的带宽。节点A的邻居节点除节点B以外，收到节点A的信道请求包的时候均不做响应。

节点B收到节点A的信道请求包S后，获得节点A的空闲信道列表List（A），并根据接收包的功率，估算出节点A与节点B的距离dAB，根据距离dAB移除使用额定功率发送时，接收信噪比低于信噪比门限的信道，得到信道列表List（A∗），根据List（A∗）和本节点的空闲信道List（B）比较，得出相交的信道列表List（A∗，B）。选择List（A∗，B）中信噪比最小的信道i作为选定的信道。

节点A收到节点B的回复后，给节点B发送信道确认信息，并更新本节点的信道状态列表，然后使用所选定的信道进行数据传输。

3 多信道多接口路由协议

传统的单信道路由协议例如AODV、DSR选择最短的路由。 在多信道网络中，WCETT［9］、WEED［10］被提出作为静态网络的协议。文中提出一种有效的多信道跨层路由协议DDMR，其中路由选择标准LP综合考虑了链路生存时间和最短路径，信道选择提出基于距离的信道选择算法。

结合跳数最小原则和稳定性最优原则，给出改进机制的选路的准则如下。

假设在目的节点的路由表中储存了同源的N条路由，用ilifetime表示第i条路由的生存时间，用ihops表示第i条路由的跳数，那么计算后的准则LP的计算公式为准则LP越大，意味着链路的性能越优。在计算准则的过程中，首先将跳数的倒数和生存时间进行归一化，之后加权求和。α代表了选路的权重，当α＝1时，改进机制退化为以最小跳数为准则的路由协议；反之，当α＝0时，意味着完全采用链路的稳定性作为选路准测。目的节点根据这个准则选择最优的路径作为路由。此准则中利用了节点间链路的生存时间估计，采用跨层的设计思路，将节点间链路生存时间携带在路由消息中进行传输，并在传送过程中进行更新。目的节点得到最小的链路生存时间，即路径的瓶颈。目的节点综合考虑链路的稳定性和跳数，选择最优的路径，并单播回复路由应答消息，源节点收到路由应答消息，完成路径建立过程。然后按照信道环境感知的多信道分配机制进行数据包的传输，即把能够传输较远的信道留给长距离的节点对进行通信，增加并行传输的数据对，从而提高网络性能。

4 仿真结果与分析

在NS2上实现前文提出的信道分配与路由选择相结合的多信道多接口智能路由协议DMMR，进行一系列仿真工作。为了比较不同机制的性能，分别在NS2上实现了Ramon的多信道模型［8］以及DDMR（multi-radio multi-channel routing protocol）。在DDMR中，信道分配方案采用基于距离的多信道分配机制，而多信道路由方案采用具有链路稳定性感知功能的多信道路由机制。

4．1 静态场景

仿真场景拓扑图如图2所示。信道参数配置表如表1所示。

图2 静态场景仿真拓扑

表1 静态场景仿真信道参数表

设定一个特定场景，在这个场景中节点只可以和其相邻的节点通信。采用不同的随机种子仿真10次取平均值，吞吐量作为性能指标随跳数的增加变化如图3所示。

图3 静态场景中的吞吐量

结果表明尽管链路生存时间估计没有被完全利用，但DDMR也适用于静态场景。利用基于距离的多信道分配方案可以达到更高的信道利用率。在RAMON信道分配方案中，路由请求在所有信道广播，节点随机的挑选信道，没有考虑信道的分配，而基于距离的信道分配方案，在考虑了距离的基础上进行信道分配能够有效提高并行通信信道数目，提高网络吞吐量。

4．2 动态场景

信道参数配置表如表2所示。在20个节点中随机选择4个节点作为源节点，随机选择4个节点作为接收节点，节点初始位置随机生成，运动方向和运动速度随机生成。运动速度v为0～20的随机值，服从均匀分布。改变v的大小，观察性能随之变化情况。

表2 随运动场景仿真参数表

采用不同的随机种子仿真10次取平均值，取包到达率和端到端平均延迟作为性能指标，仿真结果如图4、5所示。

图4 动态场景中的端到端包到达率

图5 动态场景中端到端平均延迟

仿真结果表明，在移动场景中，文中提出的DDMR协议的包到达率比AODV提高100%，这是因为DDMR在选路时通过考虑链路时间来选择更加稳定的路由，同时利用了基于距离的链路选择算法从而提高了网络的包到达率，并且可以看出α的变化对性能影响的趋势并不明显。

5 结束语

结果表明，在静态场景中尽管基于链路稳定性的路由选择机制并没有被完全利用但是DDMR也适用于静态场景。利用基于距离的多信道分配方案可以达到更高的信道利用率。在RAMON信道分配方案中路由请求在所有信道广播，节点随机的挑选信道，没有考虑信道的分配，而基于距离的信道分配方案，在考虑了距离的基础上进行信道分配能够有效提高并行通信信道数目，提高网络吞吐量。在移动场景中，DDMR的包到达率比AODV提高100%，这是因为DDMR在选路时通过考虑链路时间来选择更加稳定的路由，同时利用了基于距离的链路选择算法从而提高了网络的包到达率，在以后的工作中，多信道路由协议的优化可以是在考虑QoS性能的同时进行协议扩展，在综合考虑节点负载、能量和剩余带宽等因素的情况下对路由判据进一步优化。

［1］ARIKAN E．Some complexity results about packet radio net-works［J］．IEEE Transactions on Information Theory，1984，30（4）：681-685．

［2］BEHZAD A，RUBIN I．Multiple access protocol for power-controlled wireless access nets［J］．IEEE Transactions on Mobile Computing，2004，3（4）：307-316．

［3］GONG M X，EMIDKIFF S．Distributed channel assignment protocols：a cross-layer approach［C］／／IEEE Wireless Communication and Networking Conference．New Orleans，USA，2005：2159-2200．

［4］GONG M X，MIDKIFF S F，MAO Shiwen．Design princi-ples for distributed channel assignment in wireless ad hoc networks［C］／／IEEE International Conference on Commu-nications．Seoul，Korea，2005：3401-3406．

［5］CHIU H S，YEUNG，LUI K L．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］WU Dapeng，ZHEN Yan，XU Chunxiu，et al．On-demand reliable routing mechanism for MANET based on link life-time predicting［C］／／4th International Conference on Wire-less Communications，Networking and Mobile Computing．Dalian，China，2008：1-4．

［7］SALAMEH H A B，KRUNZ M，YOUNIS O．Cooperative a-daptive spectrum sharing in cognitive radio networks［J］．IEEE／ACM Transactions on Networking，2010，18（4）：1181-1194．

［8］CALVO R A，CAMPO J P．Adding multiple interface sup-port in NS-2［EB／OL］．［2013-04-06］．http：／／personales．unican．es／aguerocr／files／ucmultiifacessupport．pdf．

［9］SUBRAMANIAN A P，GUPYA H，DAS S R．A topology control approach for utilizing multiple channels in multi-ra-dio wireless mesh networks［J］．Computer Networks，2010，54（2）：241-256．

［10］SUBRAMANIAN A P，GUPTA H，DAS S R，et al．Mini-mum interference channel assignment in multiradio wireless mesh networks［J］．IEEE Transactions on Mobile Compu-ting，2008，7（12）：1459-1473．

Multi-channel multi-interface intelligent routing protocol

LIU Yumei，YE Zhujun，LUAN Yuanxin
College of Information and Communication Engineering，Harbin Engineering University，Harbin 150001，China

Multi-channel multi-interface can reduce co-channel interference and improve the multi-hop wireless Ad Hoc network throughput．A distance-based multi-radio multi-channel routing protocol（DMMR）is proposed，which combines channel assignment and routing algorithms．The lifetime of the link，the link distance and the number of hops are considered by this protocol．An LP standard is used to make the choice of routing criteria in the link be-tween the lifetime and the shortest path strike a balance．In this way the selected channel in a mobile environment is more reliable．A channel is selected with distance-based channel selection algorithm，which first estimates the distance between nodes，then selects the appropriate channel for data transmission according to the estimation of the distance，thus improving reuse of spatial channel．Compared with existing routing protocols，the simulation results show that the mobile multi-hop Ad Hoc networks can reduce the average end-to-end delay and improve the through-put of the protocol and packet delivery ratio．

Ad Hoc network；channel assignment algorithm；routing algorithm；multi-channel multi-interface；cross-layer

TP393

A

1009-671X（2014）03-0010-05

10．3969／j．issn．1009-671X．201307018

http：／／www．cnki．net／kcms／doi／10．3969／j．issn．1009-671X．201307018．html

2013-07-22．

日期：2014-06-05．

国家自然科学基金资助项目（61102105）．

刘玉梅（1971-），女，副研究员，博士；

叶竹君（1988-），女，硕士研究生．

叶竹君，E-mail：yeahzhujun1988＠sina．com．