退避算法改进及其在矿山物联网应用研究

李敬兆，陈尚凯

(安徽理工大学计算机科学与工程学院，安徽 淮南 232001)

近年来，由于云计算、物联网、人工智能等技术的飞速发展，煤矿生产也逐步走向智能化，智慧矿山已成为煤矿企业新的发展目标。在智慧矿山建设中，煤矿企业通过物联网技术对采集的数据进行传输，但是由于井下网络环境的复杂，数据传输效率不尽如人意。优化矿井数据传输既可以降低企业资源成本，又可以提高企业工作效率和安全性。因此人们对矿井下网络传输速率及稳定性的关注逐渐提升。

矿山物联网信息采集端通常需要部署大量的节点,当节点个数达到一定数量时,由于通信次数和数据量的增加,就会经常出现数据的通信阻塞、丢包和误码等问题。IEEE802.11协议是一种经典的MAC协议,通过BEB算法来减少数据发送中的碰撞，这种算法虽然简单，却无法适应负载较高的网络环境。

文献[6]介绍了一种退避算法，该算法采用控制竞争窗口变化速度的方法来保证数据传输的公平性，但是当网络负载较高时，吞吐量偏低；文献[7]提出一种慢速减小算法，该算法可以有效避免网络拥堵时发生二次碰撞，吞吐量性能提升，不过在网络好转后，不能及时调节竞争窗口值；文献[8]提出一种改进算法，该算法采用预估当前活跃节点数的方法计算竞争窗口理想值，这种方法误差较大并对网络要求较高；文献[9]提出一种基于同级冲突与交叉冲突的改进算法，不过站点较多时，竞争窗口很小，导致产生严重冲突。

针对上述退避算法研究中存在的不公平性、误差大、冲突严重等问题，本文对退避算法进行了改进,使其能够根据矿山物联网的网络环境采取自适应退避策略，保证了矿山物联网具有更高的鲁棒性和更强的灵活性，为智慧矿山建设奠定了基础。

1 典型退避算法分析

(1)BEB算法

IEEE802.11协议中的随机退避机制以二进制指数退避算法BEB为基础。BEB算法的思想是节点一旦产生冲突，就对退避计数器窗口值加倍；节点在发送成功后，会将竞争窗口值变为最小值。

BEB算法作为各协议中最常使用的算法，主要因为它简单容易实现，但是它对于网络环境的考虑不够周全，一旦节点数据成功发送，便将竞争窗口值变为最小值。当网络状况为重负载网络时，不仅没有对网络性能改善，还会加剧冲突产生。

因此可以发现在BEB算法中出现网络性能下降，不公平问题的主要原因是竞争窗口值在成功发送后过快下降。

(2)MILD算法

MILD算法的基本思想是当多个节点竞争同一信道时，在某个节点发送数据失败后，对它的竞争窗口值CW乘以某个系数；在节点发送数据成功后，对其竞争窗口值进行线性递减，从而缓解竞争窗口值的下降速率。

在重负载网络情况下，竞争窗口值下降速率减慢有着更好的适应性。但是即使同一个网络环境中，活跃的节点数也会不断增加或减少。因此，MILD算法同样也缺乏灵活性。它适用于节点数量较多的网络环境，而BEB算法适合节点数量较少的网络环境网络。

不难发现，在MILD算法中也有着不公平的问题，只是在另一种网络环境中。因此，需要一种较高灵活性的退避算法来适应不同的网络环境，改善网络性能。

2 退避算法的改进思想

通过分析BEB算法以及MILD算法，发现这两种算法都缺乏对复杂网络环境的适应能力。较为典型的网络环境就是重负载网络和轻负载网络。

(1) 退避算法的改进步骤

根据前面的分析，本文对退避算法进行了改进，引入了一个介于CWmin与CWmax之间的门限值CWt，通过门限值的大小来判断当前网络环境的竞争激烈程度，如果竞争窗口值CW≤CWt，认为当前网络环境未发生激烈竞争；反之，CW>CWt则表明当前网络环境竞争激烈。针对这两种情况，采取对应的退避策略，主要分为以下步骤：

1)当CW>CWt时，认为当前的网络环境中竞争冲突较多。在这种网络环境下，当数据发送失败，为尽快摆脱网络中的冲突，原竞争窗口值CW以双倍速度进行增加。当节点数据发送成功时，新竞争窗口值为原窗口值的0.8，从而缓解其下降速率，减少了冲突。

2)当CW≤CWt时，认为当前的网络环境未发生较为激烈的竞争。在这种网络环境下，当数据发送产生冲突时，原竞争窗口值CW以双倍速度进行增长。当成功发送时，对竞争窗口值CW进行折半递减再作为新的竞争窗口值。这种方法既避免了网络吞吐量由于过慢降低而使等待发送时间过长的影响，也降低了由于过快下降而引起冲突的概率。

3)上述两个步骤确定了在不同的网络环境下的操作，接下来如何选取一个合适的门限值CWt。根据资料显示，一定的活动节点在进行通信时，每个节点的窗口CW都有一个均值E[CW]，并且退避时间在选取E[CW]的情况下,网络性能最好，系统的吞吐量也是最佳的。

在确定的网络环境中，站点的后续状态不会被之前站点的状态干扰，数据帧之间的长度和时隙之间的长度为倍数关系，且服从几何分布，所以数据帧平均长度

(1)

式中：

t

为时隙时间，

o

为几何分布的概率。假设每个数据帧之间长度的分布概率为

p

，空闲时间Idle和冲突时间Coll都服从几何分布，数据帧长度的分布概率为

(2)

E[CW]是节点由于数据传送的冲突导致退避时间的平均值，即为

(3)

通过式(2)与式(3)可得

(4)

根据这些条件，可以得出一次无冲突地成功传输数据帧的时间

E[T]=

e

+2

d

+SIFS+DIFS+ACK

(5)

式中：DIFS为分布式协调功能帧间隔，ACK为确认字符帧间隔，SIFS为短帧间隔，

d

为无线网络中各个节点间的最大传输时延。

由此可得无线网络吞吐量为

(6)

其中站点数量为

M

，冲突时间Coll的均值为E[Coll]，在一个确定的网络环境中， (e,p,d,T)均为常数参数，因此可以把无线网络吞吐量

S

看作是

p

与

M

的函数。

t

是虚拟传输时间即两次成功传输的时间间隔。但是在实际应用中，站点数量往往难以准确估计，从而对网络运行造成较大的负面影响。

在实际应用中，当矿山网络负载比较重时，假定站点的状态遵循各态遍历性，便可以得到一个比公式(7)更为简洁的吞吐量的公式

(7)

其中，E[N]是一个虚拟传输时间的平均冲突数；E[B]是竞争退避的平均空闲时间。

通过上述的分析， 发现空闲时间段与数据帧冲突是网络吞吐量的主要影响因素。 如果能够降低平均空闲时间E[B]与平均冲突时间E[N]， 网络的吞吐量就能够得到提升。在理想状态下，E[B]=0，E[N]=0，代入公式(8)中可求得吞吐量

S

的极值

S

(8)

因为活跃结点的平均竞争窗口均相同，因此在这里对某个活跃节点X的竞争窗口的平均值进行计算即可。假设每个活跃结点在某个时隙的发送概率不受前面发生碰撞的次数的影响，则结点X在发送数据时与其它结点产生碰撞的概率

P

为

P

=1-(1-

p

)

(9)

则结点X在成功发送一个数据前要经历N次碰撞的概率

P

为

(10)

结点X在接连经历不同的碰撞次数后，会产生多个不同的竞争窗口，再结合全概率定理便可以得到平均竞争窗口值E[CW]。

根据吞吐量的计算公式便能够得到CW的理想均值，从而在活动节点确定的情况下，可以计算出合适的CWt值。

(2)退避算法的改进流程

综合上面三个步骤，提出了改进的退避算法。首先引入了一个介于CWmin与CWmax之间的门限值CWt，借此来区分网络竞争是否激烈。当竞争窗口值CW大于CWt时，则认为该网络竞争比较激烈；否则，认为该网络竞争不是很激烈。

对于这两种情况，采取不同的策略。在网络负载较重情况下，当节点发送数据成功时，新竞争窗口值为原窗口值的0.8倍，减缓竞争窗口值的下降速度；而在网络负载较轻情况下，对竞争窗口值CW进行折半递减再作为新的竞争窗口值，令其以较快的速率下降。在发送失败时，两种情况下的原竞争窗口值CW以2倍速度进行增长，改进退避算法的流程如图1所示。

图1 改进的退避算法流程

3 退避算法在矿山物联网的应用

将改进的退避算法应用于矿山物联网，主要是对煤矿井下区域人环物(设备)进行数据传输的性能优化。该场景应用主要由感控层、网络层和应用层组成。应用场景结构如图2所示。

图2 矿山物联网结构

(1)感控层

感控层是用于采集煤矿井下的现场信息，并将这些现实物理信息自动转换为虚拟数字信息，再通过LoRa无线传输向上级发送。感控层采集的数据大致分为两种：煤矿井下人环物等普通数据和紧急呼叫、报警等突发数据，普通数据通过节点汇总再进行上传，突发数据则直接上传操作。

(2) 网络层

网络层主要负责将感控层采集的现场信息进行整合，通过矿山物联网传输至煤矿集控中心，为感控层、应用层进行数据支持服务。考虑到矿山井下环境复杂复杂，无线传输要求快速、较强的抗干扰、高可靠性等。综合这些要求，并经过大量实验，选择LoRa技术来实现数据传输。

(3) 应用层

应用层是一个综合性的管理平台，有数据查询、数据管理、危险预警以及可视化等不同功能。该层主要负责将上传的矿井数据以用户需要的方式如图表、地图等方式进行显示供领导决策，工作人员通过界面的各个功能来实时监控井下状态。

4 实验与分析

实验的目的在于对比基于矿山物联网环境而提出的改进退避算法与典型的退避算法，保证负载情况不变时，谁的性能更好。通过比较不同的退避算法的数据包投递率与公平性指数，从而评估不同退避算法的网络性能。

(1)数据和参数设置

实验通过对比不同算法的平均端到端时延、数据包投递率以及公平性指数FI来评估改进后退避算法的网络性能。

公式(16)是链路吞吐量网络中的公平性指数，

S

表示节点

i

的饱和吞吐量，

n

代表总计的节点数，FI展示了网络中吞吐量的变化情况。FI的数值越大，网络的公平性就越好。

(11)

实验中的数据来自矿山物联网感知设备对某矿数据的采样，分为6组数据，每组200条数据。将10次实验后的平均值作为实验数据，实验的网络环境为500m×500m，时间均为500秒。实验中网络节点的基本参数如表1所示。

表1 节点参数表

(2)实验分析

为了验证改进的退避算法好于典型的退避算法，以下将对比分析改进退避算法、BEB算法以及MILD算法的平均端到端时延、数据包投递率以及公平性指数。

数据包投递率是衡量网络性能的重要指标之一。图3对比了改进后退避算法、BEB算法和MILD算法这三种算法的数据包投递率，从图3中可以看出，随着网络中的竞争节点数目持续增加，三种不同算法的分组碰撞发生的次数都在随之增多，丢包率不断变大，从而使得数据包投递率越来越低。通过对各个节点的竞争级别进行了调节，改进后的退避算法在竞争节点数相同时，其数据包投递率总是高于MILD算法以及BEB算法。因此可以得出结论，改进后的退避算法在数据包投递率方面优于BEB算法以及MILD算法。

图3 数据包投递率与竞争节点数目的关系

网络的传输时延是指端到端的时延。从图4中可以看出，在节点数量较少时，三种算法的时延都相对较小。随着节点数量增加，网络中节点碰撞变多，三种算法的端到端时延都呈上升趋势，并且BEB算法与MILD算法的时延高于改进的退避算法。这是因为改进的退避算法可以让竞争节点自适应竞争状态的变化，从而有效降低了时延。因此可以得出结论：改进后的退避算法在网络传输时延上优于BEB算法以及MILD算法。

图4 平均端到端时延与竞争节点数目的关系

分析图5可知，当竞争节点数目增加时，BEB算法与MILD算法的公平性指数持续下降，公平性波动较大；与之对比，改进的退避算法能够根据节点负载的情况选择适合的竞争窗口，有效避免节点竞争的情况，所以曲线较为平稳，公平性指数始终在固定范围内变化。因此可以得出结论，改进后的退避算法在公平性指数上优于BEB算法以及MILD算法。

图5 公平性指数与竞争节点数目的关系

(3) 实验结论

通过实验，可以发现BEB算法以及MLID算法都很难应对变化的网络环境；而改进后的退避算法无论是时延、吞吐量以及公平性都有着显著改善。综合三次实验结果：改进后的退避算在矿山物联网中有着更好的网络性能，能够提高数据传输准确性，使得数据更加可靠，有效保障了矿山安全。

5 总结

通过对影响矿山物联网的网络性能的可能因素进行分析、总结，本文对退避算法进行改进并应用到矿山物联网中，该算法通过动态调节竞争窗口值来适应矿山物联网的网络环境。实验结果表明，在时延、吞吐量以及公平性等方面改进的退避算法都优于BEB算法与MILD算法，更适应矿山物联网的网络环境，减少了由于数据传输造成的事故，保障了煤矿生产的安全。