无线Mesh网络中转发节点的选择算法

张旭平 夏景明

摘  要： 稳定路由是无线Mesh网络（WMNs）的重要性能指标，不稳定路由会引起数据包丢失率和高的传输时延。为此，提出基于熵函数的节点稳定路由（ESR）协议。ESR利用熵函数估计节点稳定度。具体而言，ESR协议收集链路质量，并计算链路稳定值，再依据稳定值估计节点熵。同时，将熵信息载入路由表，并与邻居节点交互。一旦接收此消息，节点就存储于路由表，然后选择具有最大熵的节点作为下一跳节点。实验数据表明，与基于干扰和信道切换（MIC）、基于期望传输次数（ETX）和基于加强学习的连通网关的最佳路径（RLBDR）路由协议相比，提出的ESR协议在吞吐量、时延和数据包丢失率方面均具有较好的性能。

关键词： 无线Mesh网络; ESR; 路由协议; 链路质量指标; 节点选择; 熵信息载入

中图分类号： TN915.05?34; TP393                   文献标识码： A                  文章编号： 1004?373X（2019）13?0023?05

Forwarding node selection algorithm in wireless Mesh networks

ZHANG Xuping， XIA Jingming

（School of Electronic and Information Engineering， Nanjing University of Information Science &Technology， Nanjing 210044， China）

Abstract： The stability route is a key performance index in wireless mesh networks （WMNs）， but the instability route may cause the high packet loss rate and transmission delay. Therefore， the entropy?node stability?based routing （ESR） protocol is proposed， which can estimate the node stability by using entropy function. More specifically， the ESR protocol collects the link quality， then computes the stable value of the link， and estimate the node entropy according to stable value. At the same time， the entropy information is loaded into routing table， and interacted with neighbor nodes. Once this information is received， the node is stored into the routing table， and then the node with maximum entropy is selected as the next hop node. The experimental data shows that， in comparison with the protocols based on interference and channel switching， and expected transmission count （ETX）， as well as reinforcement learning?based best path to best gateway （RLBDR） protocol， the ESR protocol has higher performances in the aspects of throughput capacity， delay and packet loss rate.

Keywords： wireless mesh network; ESR; routing protocol; link quality metric; node selection; entropy information loading

0  引  言

无线网状网络（Wireless Mesh Networks，WMNs）被认为是下一代无线网络最有前景的技术[1]。与多跳移动自组织网络（Multi?hop Mobile Ad?Hoc Network，MANET）不同，WMNs具有相对静止结构、低移动特点。WMNs是有线和无线网络的结合体，且以无线Mesh路由（MRs）作为主干网，移動点为用户。MRs扮演着消息转发角色。通常MRs向网关（GWs）传输流量，其中GWs用于连通Internet，如图1所示。

图1  典型的无线网状网络WMNs结构

在WMN中干扰和GWs拥塞会提高数据包丢失，并增加时延。为了提高WMNs性能，研究人员提出了不同的方案，如文献[1]提出基于方向和智能天线策略，文献[2]提出了多输入多输出系统（Multiple Input Multiple Output，MIMO）策略，文献[3]提出多信道多频率技术，文献[4]提出了合作通信技术。

实际上，路由策略对网络性能有重要的影响。路由的目的就是依据具体路由指标选择最优路由。为了获取好的路由性能，路由指标应当：不降低网络稳定性;隐含Mesh网络的特性;避免转发循环[5]。

网络稳定是多数网络的主要性能指标。当网络不稳定，重建路由的频率就会增加。这个增加是由于多条链路质量过低导致的。即低质量的链路导致路由翻转，最终降低网络性能。

现存WMNs的路由[6?10]可分为反应式、先应式和混合式。文献[6?7]分别提出了按需距离矢量路由、动态源路由，它们均属于反应式路由。而文献[8?9]分别提出的优化链路状态路由、移动Mesh路由均属于先应式路由。这些路由中的每个节点维持隐含网络拓扑信息的路由表。此外，文献[10]提出TORA的混合路由。在路由发现时，TORA先从已存的部分路由表中搜索路由表，如果没有可选路由，就利用反应式方式再搜索路由。

然而，这些路由并没有充分考虑WMNs的网络特性、节点间的相互干扰以及导致长时延和高的数据包丢失率的原因。为此，提出基于熵函数的节点稳定路由（Entropy?node Stability?based Routing，ESR）协议。ESR协议先估计链路质量指标，再计算节点的稳定度，并计算节点的熵，然后选择具有最大熵的节点作为下一跳转发节点。实验数据表明，提出的ESR协议能够有效地控制传输时延，降低数据包丢失率。

1  网络模型

考虑多跳WMNs将节点分为MRs和GWs两类。MRs形成多跳无线主干网，完成用户与Internet间的流量传输。为了将流量传输至Internet，引用网关作中间转发节点。每个MR配备了多个无线接口，且每个接口上具有多个信道。假定MR的接口有多个不同的信道。

将主干WMN模拟为一个图论[G=V，E]，其中，[V]为节点集（MRs和GWs），[E]为链路集。令[?ij]表示两个MRs（[υi]，[υj]）间的链路，且[υi]，[υj∈V]。此外，通过GWs连通Internet。

2  ESR协议

2.1  链路质量指标和节点稳定度

2.1.1  链路质量指标

链路质量指标（Link Quality Metric，LQM）是反映链路特性的参数。LQM定义为两个参数的权重函数：干扰率（Interference Ratio，IR）和拥塞等级（Congestion Level，CL）。IR包含了信噪比（Signal to Noise Ratio，SNR）和信干扰比（Signal to Interference plus Noise Ratio，SINR）。假定从节点[υ]至节点[u]的链路[?]的IR定义为：

2.2  基于节点稳定的路由

通常是利用链路的历史信息和当前信息估计链路的稳定指标。如果链路的LQM低于预定门限值，则该链路认为是可接受的，否则认为不可接受。显然，如果链路在可接受和不可接受间波动也是不可接受的。因为这种波动会导致网络性能振动，进而导致链路的不稳定。

本文提出基于稳定指标算法SIA，并利用接受与不可接受间的链路波动、链路持续力估算链路稳定性。计算链路稳定性过程，如下所示。假定链路[?]在时刻[t+1]的稳定值为[St+1?]。每个节点执行SIA算法估计链路稳定值。再利用稳定值选择下一跳转发节点，进而实现ESR，即ESR是利用SIA算法计算链路的稳定值。

如果链路[?]不是新链路，即[?∈RTti]，则判断链路[?]在时刻[t]至[t+1]间的链路是否变化。如果[LQM?t+1-LQM?t≤η]，则表明链路没有发生变化，其中[η]为控制参数，且[η∈0，1]。在这种情况下，[St+1?=St?+1]。

如果[LQM?t+1-LQM?t>η]，说明链路发生变化。在这种情况下，判断链路是朝好的方向（优化），还是下降（惡化）。如果[LQM?t+1

2.3  下一跳节点的选择

式中[Ni=RTt+1i]表示节点[υi]的路由表的节点数。熵值越高，表明节点越稳定。在选择下一跳节点时，节点先依据式（11）计算自己的熵，然后向自己的一跳邻居节点广播。节点一旦接收到此信息，就将此信息存入路由表，然后选择最稳定的节点转发数据包。

综上所述，转发节点的选择过程如图2所示。先计算LQM，然后利用SIA算法计算链路稳定值，然后，再计算自己的熵，并将熵信息存于路由表。通过交互路由表信息，邻居节点就能获取一跳邻居节点的熵信息，并选择具有最大熵的节点作为下一跳转发节点。

图2  选择下一跳节点框图

2.4  路由更新及维护

每个节点周期地广播自己的熵，且周期[T]设定为1 min，即节点每隔[T]更新熵信息。若发现邻居节点存在具有更大熵的节点，就将此节点作为下一跳转发节点。此外，当已选择的下一跳节点离开邻居范围，就必须在邻居节点集内重新选择一个节点作为自己的转发节点，重新构建路由，进而实现路由维护的目的。

3  仿真及分析

利用NS2软件建立仿真平台，具体的仿真参数如表1所示。考虑16个MRs随机分布于[1  000×1  000]区域，且区域内有三个网关（即节点1，2，3）。以IEEE 802.11作为MAC层协议。

表1  仿真參数设置

为了更好地分析ESR，选择基于加强学习的连通网关的最佳路径RLBDR（Reinforcement Learning?based Best Path To Best Gateway）[11]，干扰和信道切换MIC（Metric of Interference and Channel）[12]、期望传输次数ETX（Expected Transmission Count）[13]路由协议作为参照。同时，分析它们的网络平均吞吐量、数据包丢失率以及端到端传输时延。其中，平均吞吐量是指在给定时间内成功接收的数据字节数;数据包丢失率是指丢失的数据包数与已发送的数据包数之比。而端到端传输时延是指将CBR数据包从源节点传输至网关所需的平均时延。

首先分析平均吞吐量随数据率的变化情况，且数据率从1 000～3 000 Kb/s变化，实验数据如图3所示。

图3  平均吞吐量随数据率的变化情况

从图3可知，随着数据率的增加，平均吞吐量也呈增加趋势。原因在于数据率的增加，加大了网络传输的数据量，必然增加了平均吞吐量。与RLBDR，MIC，ETX相比，提出的ESR吞吐量得到有效地提高，且分别比RLBDR，MIC，ETX的吞吐量提高了近7%，17%，36%。

然后，分析数据包丢失率随数据率的变化情况，实验数据如图4所示。

图4  数据包丢失率随数据率的变化曲线

从图4可知，数据率的增加提高了数据包丢失率。原因在于：当数据率增加到一定程度，会导致网络拥塞，这必然增加了数据包丢失率。然而，与RLBDR，MIC和ETX相比，提出的ESR的数据包丢失率得到有效地控制，并且随数据率的增加，控制效果越好。

最后，分析了端到端传输时延随数据率的变化曲线，实验数据如图5所示。

图5  端到端传输时延随数据率的变化

从图5可知，提出的ESR的传输时延低于RLBDR，MIC和ETX。在数据率为1 000 Kb/s时，ESR比MIC，ETX的时延下降了31%，29%。然而，当数据率在1 000～2 000 Kb/s区间时，RLBDR的端到端传输时延低于ESR，且下降了约25%。原因在于：ESR不是从传输跳数角度选择路由，而是从稳定角度选择路由。因此，在低速区时，RLBDR的传输时延较低。然而，对于高速时区（数据率大于2 500 Kb/s），ESR的传输时延优于RLBDR。例如，在数据率为2 500 Kb/s时，ESR的时延降低了49%;当数据率为3 000 Kb/s时，时延降低为25%。

4  结  语

针对WMNs网络的路由问题，提出基于熵函数的节点稳定路由ESR。ESR路由先构建链路质量指标LQM，再计算节点的熵。熵越大，节点越稳定。因此，选择具有最大熵的节点传输数据包，从而建立稳定的路由。实验数据表明，提出的ESR有效地提高了数据包传输率，降低了传输时延。

参考文献

[1] STINE J A. Exploiting smart antennas in wireless mesh networks using contention access [J]. IEEE wireless communications magazine， 2016， 13（2）： 38?49.

[2] SHIN J， LEE H， NA J， et al. Load balancing among internet gateways in Ad Hoc networks [C]// Proceedings of the 62nd Vehicular Technology Conference. Dallas： IEEE， 2015： 1677?1680.

[3] KYASANUR P， VAIDYA N H. Capacity of multi?channel wireless networks： impact of number of channels and interfaces [EB/OL]. [2005?11?21]. https：//www.ics.forth.gr/mobile/Bibliography/LoadBalancing/LB/Capacity_MChannel_WLANs.pdf.

[4] CAO B， FENG G LLI Y， et al. Cooperative media access control with optimal relay selection in error?prone wireless networks [J]. IEEE transactions on vehicular technology， 2014， 63（1）： 252?265.

[5] YANG Y， WANG J. Designing routing metrics for Mesh networks [J]. IEEE wireless Mesh networks， 2015， 6（8）： 35?61.

[6] PAN X， ZENG H Y. Improved Ad Hoc on?demand distance vector routing based on bandwidth [C]// 2010 International Conference on Computational Problem?Solving. Lijiang： IEEE，  2016： 238?245.

[7] JOHNSON D B， MALTZ D A， BROCH J. DSR： the dynamic source routing protocol for multi?hop wireless Ad Hoc networks [M]// Anon. Ad Hoc Networking. Boston： Addison?Wesley， 2016： 56?67.

[8] CLAUSEN T， JACQUET P. Optimized link state routing protocol （OLSR） [M]. US： RFC， 2016： 23?32.

[9] LIAO G L， CHEN C Y， HSU S W， et al. Adaptive situation?aware load balance scheme for mobile wireless mesh networks [C]// 2011 IEEE Conference on Computer Communications Workshops. Shanghai： IEEE， 2016： 391?396.

[10] ATER F J， VINAGRE J J， MORGADO E. A low energy and adaptive architecture for efficient routing and robust mobility management in wireless sensor networks [C]// Proceedings of the 2011 31st International Conference on Distributed Computing Systems Workshops. Minneapolis： IEEE， 2011： 172?181.

[11] BOUSHABA M， HAFID A， BELBEKKOUCHE A. Reinforcement learning based routing in wireless mesh networks [J]. Wireless networks， 2015， 19（8）： 2079?2091.

[12] LI D， LIU H. Comparative analysis of protocols in wireless Ad networks [J]. Ambient intelligent wireless networks， 2014， 4（7）： 23?31.

[13] DE COUTO D S， AGUAYO D， CHAMBERS B A， et al. Performance of multihop wireless networks： shortest path is not enough [J]. ACM SIGCOMM computer communication review， 2014， 33（1）： 83?88.