无线Mesh网络中基于活跃节点数估计的自适应接入机制

摘要

本发明提出一种无线Mesh网络中基于活跃节点数估计的自适应接入机制，以改善网络吞吐量和节点接入信道的公平性受限的情况。本发明引入“活跃节点”？，通过侦测信道的空闲时隙来估算网络中的活跃节点数，由此推导网络达到饱和吞吐量时节点的最优传输概率，再通过动态调节初始竞争窗口值来提高网络吞吐量；当发生冲突时，引入重传调整因子来改善节点间的公平性，根据活跃节点数和重传次数计算重传因子，再通过重传因子合理地设置重传竞争窗口值以减少数据包的丢失，从而提高了重传接入的成功率。本方法能够有效地改善无线Mesh网络的吞吐量、公平性以及丢包率等方面的性能，是一种无线Mesh网络切实可行的接入控制方法。

说明书

技术领域

本发明涉及无线通信领域，尤其涉及一种无线Mesh网络中基于活跃节点数 估计的自适应接入机制。

背景技术

无线Mesh网络(WMN，WirelessMeshNetwork)通常也被称为无线网状 网，是一种由多个无线链路连接设备和Mesh路由器结点构成的，集自组织、自 修复、多跳级联等特点于一身的新型宽带无线网络。无线Mesh网络结合了无线 局域网(WLAN)和移动自组织网(MANET)的优点，依靠其高伸缩性、高健 壮性和便利性，成为未来建设无线智慧城市的关键网络类型之一。

无线Mesh网络中有许多的关键技术和协议标准，其中的媒体接入控制 (MAC，MediaAccessControl)协议决定了如何在众多的通信节点之间分配有 限的无线信道资源，使这些资源能够合理充分地被利用，在时延、吞吐量和公 平性等网络性能指标上尽量达到最优。因此如何合理地设计媒体接入控制协议 是无线Mesh网络研究人员需要重点考虑的问题。

当前无线Mesh网络的媒体接入控制协议可以划分为单信道协议和多信道 协议。对于单信道情况下节点之间的数据传输，存在传统的隐藏/暴露终端问题， 因此有较多的无线Mesh网络中的MAC协议，都采用基于IEEE802.11标准的 分布式协调功能(DistributedCoordinationFunction，DCF)机制让节点去竞争信 道资源。DCF机制采用了载波侦听多址访问/冲突避免(CarrierSenseMultiple AccesswithCollisionAvoidance，CSMA/CA)机制来侦听信道并降低网络冲突， 同时引入发送/允许发送(RequestToSend/ClearToSend，RTS/CTS)交互方式来 解决隐藏终端问题。但是DCF机制仍有许多不足之处，例如节点难以根据网络 拥塞程度选择合理的退避时间，导致信道资源浪费，网络的自适应性差；竞争 窗口在发送失败后呈指数倍增或发送成功后减小为零的变化，会导致严重的公 平性问题。

在DCF机制的改进上，文献“ASimpleandEffectiveBack-offSchemeforthe IEEE802.11MACProtocol”(ChatzimisiosP,BoucouvalasAC,etal.2nd InternationalConferenceonCyberneticsandInformationTechnologies,Systemsand Applications,CITSA2005,11thInternationalConferenceonInformationSystems AnalysisandSynthesis,ISAS2005,2005,1:48-53)提出了DIDD(DoubleIncrement DoubleDecrement)竞争窗口调节机制。DIDD算法使得竞争窗口的变化趋于平 缓，对网络的吞吐量起到了一定的优化作用。其缺点在于仍然不能根据网络的 实时情况进行自适应地调节。

文献“ANewBack-offAlgorithmfortheIEEE802.11DistributedCoordination Function”(DengJ,VarshneyPK,HaasZ.InCommunicationNetworks,Distributed SystemsModelingandSimulation,2004:215-225.)提出了一种竞争窗口调节方法 LMILD(Linear/MultiplicativeIncreaseandLinearDecrease)，当信道发送冲突时， 引起冲突的节点竞争窗口值将呈乘性增长，周围侦听到冲突的节点都将竞争窗 口值线性增加一定的值。LMILD是一种无需对网络的信息进行收集的较为简单 的算法，但是因为周围侦听到冲突的节点都会把自身的竞争窗口值线性增大， 直接影响节点接入信道的概率，这种网络公平性的提升以牺牲了一定的吞吐量 为代价。

总之，目前一些针对DCF机制进行改进的算法和协议，都在一定程度上依 据节点的发送成败和信道的忙闲，如何在上述基础上，再结合信道的拥塞程度 自适应地调节竞争窗口，成为设计MAC协议的要点之一。

发明内容

针对现有协议的不足，本发明提出了一种无线Mesh网络的媒体接入控制机 制，该机制能够使节点有效地自适应接入信道，提高网络吞吐量并改善网络公 平性。

为了实现该目的，本发明以活跃节点(指当前参与信道竞争的无线Mesh网 络节点)的数目作为指标来反映网络当前的拥塞程度。节点需要侦测信道的空 闲时隙数来估算网络中的活跃节点数，通过建立一个二维马尔科夫模型，推导 出节点的传输概率是初始竞争窗口与活跃节点数的函数，再利用传输概率与竞 争窗口的关系动态调节初始竞争窗口值；当发生冲突时，根据活跃节点数和重 传次数调整重传因子，合理设置重传窗口值，从而有效地提升网络吞吐量和公 平性。

本发明通过以下技术方案实现，本发明包括如下步骤：

步骤1：节点处于侦听期，通过节点内部增设的计数器NUM_IDLE和 NUM_LISTEN分别统计侦听期信道空闲时隙数目r和总时隙数目T；

步骤2：节点准备发送数据，首先侦听信道是否空闲，确认空闲时长为DIFS 后进入退避期；根据内部计数器统计结果估算网络活跃节点数N_esti，并设置初始 竞争窗口值CW₀；

步骤3：在退避期，节点根据竞争窗口值选择随机退避时间；信道空闲时长 为SlotTime，则退避计数器的值减1，当退避计数器的值减为0时，节点接入 信道，进入传输期；

步骤4：在传输期内，发生冲突使数据发送失败，则需要进行重传；当重传 次数i达到限制，则丢弃数据，等待下一次发送数据；当前节点的重传次数i没 有超过最大重传次数，增设重传调整因子θ，根据重传调整因子θ设置重传竞争 窗口值，然后跳至步骤3。

其中活跃节点N_esti指当前参与竞争信道资源的节点，其数目反映网络当前的 拥塞程度，活跃节点越多，说明网络竞争激烈，拥塞程度高；通过计数器 NUM_IDLE和NUM_LISTEN获取相应的时隙信息估计当前网络中的活跃节点 数目。活跃节点数可通过计算，其中r和T为节点计数 器NUM_IDLE和NUM_LISTEN的实际统计值。

其中重传调整因子θ，其值大于等于1；重传因子的取值与网络中的活跃节 点数N和重传次数i有关：

$\theta ={\log }_2{N}_{esti}-\frac{i}{3}$

活跃节点数少，减小竞争窗口值，活跃节点数多，增大竞争窗口值；重传 次数多的节点优先接入信道；采用对数函数值随变量缓慢的性质控制竞争窗口 的变化率，对数函数的底数控制重传调整因子θ的变化幅度，本发明中底数的 取值2。

其中重传竞争窗口的取值与重传调整因子θ和最大竞争窗口CWmax有关：

CW_i＝int(min[θ*CW_i,CW_max])

CWi为第i次重传时的竞争窗口值，如果θ*CWi的值大于竞争窗口的最大 门限值CWmax，则重传竞争窗口的取值等于最大门限值，否则取值为θ*CWi。

当节点进入退避期前需设置初始竞争窗口CW₀，选择退避时间；根据估算出 来的活跃节点数目N_esti，求得饱和吞吐量情况下的节点最佳传输概率：

通过建立马尔科夫模型得到传输概率τ与初始竞争窗口CW₀、活跃节点数 N_esti之间的关系：

$\left(\begin{array}{c}{\tau }_{opt}=\frac{2(1-2p)}{(1-2p)({\mathrm{CW}}_0+1)+{\mathrm{pCW}}_0[1-{\left(2p\right)}^m]}\\ p=1-{(1-{\tau }_{opt})}^{N_{esti}-1}\end{array}\right)$

依据CW₀＝int(max[CW_min，CW₀])计算初始竞争窗口CW₀；最终节点根据初始 竞争窗口选择随机退避时间。

其中侦听期内节点没有数据发送，不需竞争信道，只对周围状况进行侦听； 当节点完成一次传输后将会进入侦听期，先将内部的两个计数器NUM_IDLE和 NUM_LISTEN清零，并开始分别统计侦听期内监测到的信道空闲时隙数目和总 的时隙数目；当节点准备发送数据时，两个计数器停止统计，准备进入退避期。

退避期内节点处于有数据需要发送，但需要竞争信道资源的时间段；当信 道空闲且节点的退避计时器不为零，则该退避计时器递减，当递减过程中信道 被占用，则退避计时器冻结，暂停退避过程；当再次侦听到信道空闲后，退避 计时器恢复工作，当退避计时器减小为零时，节点接入信道，进入传输期进行 数据传输。

随机退避时间内节点选取的一个时间进行退避以延迟信道接入，退避时间 的选择依据

Back-offTime＝Random()×SlotTime

其中Random()是位于[0,CWi]区间上服从均匀分布的伪随机整数，slottime为时 隙时间，与物理层的特征有关。

与现有技术相比，本发明的优点如下：

(1)本发明描述的机制引入两个计数器统计时隙数，较IEEE802.11DCF原有 机制更好地利用了网络的拥塞程度来分配信道资源；

(2)本发明描述的机制并未精确地测量当前网络中的活跃节点数目，而是采 用一种估计算法，简单有效，并未增加过多的系统开销；

(3)引入了重传调整因子，改善了公平性；并且该因子的取值可以根据网络 规模改变，较灵活；

(4)相比IEEE802.11DCF更适合复杂多变的无线Mesh网络。

附图说明

图1本发明协议流程图

图2节点在不同发包速率下的吞吐量

图3节点在不同发包速率下的公平性

图4节点在不同发包速率下的丢包率

具体实施方式

以下将结合图1和仿真示例图2-4对本发明作进一步的描述。

本发明选择50个节点的随机拓扑场景进行说明，节点的覆盖范围均为 250m，依然沿用了IEEE802.11中的RTS-CTS-DATA-ACK消息交互序列，选 取吞吐量、公平性、丢包率作为评价指标。网络中传输的数据包长度设为512byte， 传输层采用用户数据报协议UDP代理，采用恒定比特率CBR(ConstantBitRate) 的流量产生器产生数据。其余主要的参数如表1所示：

表1仿真实施参数

RTS 160bits DIFS_Time 128μs CTS 112bits SIFS_Time 28μs ACK 112bits Slot_Time 28μs 最大重传次数 6 最大移动速度 0.01m/s

节点首先进行初始化。

网络进入稳定时刻，各节点采用RTS-CTS-DATA-ACK消息交互序列进行 传输。

节点内部维持一个侦听机制，首先会确定自身是否正在发送或退避，若不 处于上述状态则启动侦听机制，开始检测当前信道的状态。在一个时隙当中， 若当前信道空闲，将计数器NUM_IDLE和NUM_LISTEN计数器分别加1，若 信道忙碌，则只有NUM_LISTEN增加1。下一个时隙循环执行上述过程直至侦 听期结束，根据计数器估算活跃节点数N_esti，并将计数器清零等待下一次侦听期。

节点对要发送的数据包会根据是RTS和DATA进行相应类型的封装，然后 暂存等待发送时机。之后节点检测自身是否处于退避期，若是则等待退避计时 器结束后便可接入信道，否则要转入退避状态进一步检测信道是否空闲。此时 分为几种情况：

情况一是信道空闲，并且延迟接入计时器DeferTimer正在工作，表明节点 仍需延迟接入，直到DeferTimer减为0后再设置竞争窗口退避；

情况二是信道空闲，但DeferTimer未工作，此时根据传输概率τ与初始竞 争窗口CW₀、估算出的活跃节点数N_esti之间的关系：

$\left(\begin{array}{c}{\tau }_{opt}=\frac{2(1-2p)}{(1-2p)({\mathrm{CW}}_0+1)+{\mathrm{pCW}}_0[1-{\left(2p\right)}^m]}\\ p=1-{(1-{\tau }_{opt})}^{N_{esti}-1}\end{array}\right)$

依据CW₀＝int(max[CW_min，CW₀])计算初始竞争窗口CW₀，得到随机退避时间；

情况三是信道非空闲，有其它节点接入或发生冲突，则节点冻结退避计时 器直到信道恢复空闲。

节点发送RTS包过程中发生冲突或其他因素导致未能在限定时间内收到接 收节点回传的CTS，需要重传RTS。接着判断节点是否正在退避，一旦退避则 将报文重传次数增加1，然后判断是否超过了设定的最大重传次数。如果超过则 直接丢弃报文放弃重发，如果未超过则确定重传调整因子θ，重新设置竞争窗口 进行退避。在这里描述的场景中θ的计算公式为：其中对数函数 的底数取值为2，N_esti为估算出的活跃节点数，i为当前的重传次数且i应该小于 允许的最大重传次数。

节点发送DATA包过程中发生冲突或其他因素导致未能在限定时间内收到 接收节点回传的ACK包，同样会判断是否需要重传。首先将重传次数增加1， 若未超过重传限制，节点将按照本发明描述的算法，确定重传因子根据重传因子θ设置重传竞争窗口，计算公式为CW_i＝int(min[θ*CW_i,CW_max])，随 机选择一个0到当前竞争窗口值之间的整数作为退避计数器的值，才能接入信 道；若超过重传限制则放弃本次传输，等待下一次数据发送。

下面评价仿真得出的性能指标。如图2所示(所有图示中ANNE-ADCF均 代表本发明机制)，在网络吞吐量方面，随着节点发送数据包速率的上升，本 发明描述的机制要优于DCF和DIDD机制，原因在于本发明通过调整竞争窗口 值使节点的传输概率更逼近最佳值从而提高了吞吐量。

在公平性方面，随着发包速率的增加，一个明显的结果是网络中的节点间 公平性均会下降。如图3所示，本发明机制公平性最优，DCF机制的公平性下 降趋势更加明显。这是由于网络负载和信道冲突随着发包速率增大而增大，DCF 中发送失败的节点倍增竞争窗口的机制使其更难接入信道，而本发明中重传次 数多的节点会设置更小的重传调整因子，优先使其接入信道，减少不公平现象。

在丢包率方面，网络负载和信道冲突随着发包速率增大而增大，导致重传 次数也增大，达到重传限制后便会丢弃数据包。相比DCF和DIDD机制，本发 明机制的丢包率更低，原因在于本发明会在当前网络活跃节点数较多时，避免 节点频繁接入信道，降低了数据冲突概率；同时在优先让重传次数多的节点接 入信道，减少了因超过重传限制而丢弃数据包的现象。