ISSN 
下载:
-
无线传感器网络不仅可应用于军事、环境、生态监测、地震和火灾等突发灾难现场的监控，而且可以应用于医疗系统、交通和监控等场景[1]。传感器节点分布密集、范围广泛、链路质量受环境影响很大，节点位置的变化或应用数据的异常都可能造成拥塞。拥塞会降低网络的质量，增加端到端的延时，造成数据丢失或服务响应时间过长，同时严重地浪费网络的带宽。由于传感器节点会不间断地进入到休眠状态，因此网络结构会不断地变化，同时节点由于体积小，其存储能力、计算能力及能量都是非常有限的，拥塞会极度地消耗这些有限的资源。所以使用拥塞检测技术可尽早发现网络中潜在的拥塞现象，提高网络的服务质量 (QoS)，设计拥塞检测和避免的策略使网络尽快恢复到正常的工作状态，成为了当今的研究热点[2-3]。
-
无线传感器的拥塞分为节点级的拥塞和链路级的拥塞。其中节点级拥塞是指节点需要发送的数据包超过了自己的缓存能力，因此新到的分组会被丢弃，而且排队分组的响应时间明显加长。链路级拥塞主要指信道共享，多个相邻的节点同时使用同一条无线信道发送数据，此时会发生链路级拥塞，导致节点发送数据丢失，降低网络整体的吞吐量，同时链路的使用率也会下降。
在拥塞检测方面，文献[4-7]采用判断节点内部数据队列长度来判断网络的拥塞状况，设定一个上限阈值，如果分组的缓存长度超过这个值那么就判定发生了拥塞，但是这类方法的缺点是阈值的大小不好把握，过大的阈值将会导致拥塞现象难以及时发现，导致网络资源的浪费。同时也有基于信道的采样检测方式，拥塞发生的时候，拥塞区域内的无线信道由于不同节点的竞争使用会呈现拥塞状态。文献[8]专门针对分簇的网络来检测拥塞，簇头节点实时检测簇内的流量情况，并计算出簇里的节点缓存溢出的概率从而可计算出一个簇是否发生了拥塞，但是该方法需要底层通信协议的支持，以及增加节点能量的消耗。文献[4]使用sink节点接受传感器节点分组的速率来判断网络拥塞情况，但缺点是应用的场景比较局限，只适用于周期性数据网络，且检测周期较长。
在拥塞避免方面，常用的方法是控制节点的发送速率，通过速率分配或者缓存通告来实现速率的控制。速率分配机制应用于网络结构比较稳定的网络，网络中每个节点的数据产生速率和发送速率都是严格分配计算的，使得网络任何节点的数据产生速率和子节点的数据发送速率小于给节点分配的发送速率，从而网络中的每一个局部区域内的吞吐量高于其网络流量。文献[9]提出的拥塞避免机制使用了轻量级缓存管理，发送节点接收目标节点的缓存信息，只有目标节点有足够的缓存来容纳要接收的数据时，发送节点才会主动去发送数据，这样防止路径中间的节点因为缓存不够而造成拥塞。文献[10]在文献[9]的基础上增加了节点节能的功能。IPD[11]通过队列的长度来检测，当分组的内部排队时间大于分组的内部处理时间，队列就会增加，通过队列长度来计算缓存的占用率。当检测到拥塞发生时，IPD先计算分组的优先级，根据优先级丢弃一定的分组来达到分析和控制拥塞的目的。无线传感器网络是事件驱动的网络，由于拥塞会影响可靠性和负载均衡，拥塞控制经常会结合到路由算法中[12-14]。然而这些算法大都是基于缓存因子来进行拥塞判断与避免，而在传感器网络中需要考虑延时、节点能量等众多因素，而且算法采用丢弃分组的办法来控制拥塞会减少源数据采集量从而牺牲了数据的精度。
在拥塞解除方面，速率控制是最常见手段，当系统检测出拥塞发生时，中间节点降低数据发送速率，抑制了拥塞向下游扩散，并向上游节点发送拥塞发生的情况，上游节点可根据自己的状态调节数据发送速率或者去进一步转发通告消息。TADR[15]采用了空闲或者空载的节点来缓解拥塞，通过在拥塞区域周围的空闲节点的路由路径来传播分组，算法设计通过深度和队列长度构造一个混合虚拟的势场来绕开拥塞造成的网络拥堵最终到达目标节点。COTA[16]采用了基于路径的启发式信息分配流量，避免给热点区域增加负荷。但是其建立的路径中存在节点重复使用的情况，而且没有涉及到网络中数据延迟的现象，同时也没有考虑在分配过程中可能引起的分配流量的波动情况。
针对目前算法存在的不足，本文提出了一种改进的拥塞流量分配算法 (ECOTA)，在分配中避免了路径中由于网络拥塞造成的延迟波动；还提出了一种有效的拥塞检测和缓解算法 (ECODEM)，在网络中出现拥塞情况下能够将拥塞区域的流量分配到非拥塞区域，同时保证网络中的传输延迟最小，合理的利用网络中节点的能量。
-
本文提出的改进型流量分配算法ECOTA，在对路径进行流量分配的基础上，减少了网络中的延迟。ECOTA创建的路径除了源节点与目标节点外，其余的节点均不相同。在传输路径中，多条路径的重合节点最有可能因为自身的缓存溢出造成路径中的数据包丢弃而引起网络拥塞，而ECOTA采用无重复多路径的方法可避免因为几个节点造成的网络拥塞现象。
由于无线网络自身的因素，导致在数据传输的过程中会出现信道失败的情况。针对这种情况，普遍的解决方法是采用建立多条路径的方式来传输数据以增加数据传输的可靠性。假设信道失败率为e，从源到目标的平均跳数为k，为达到期望的可靠性r，至少要建立的路径数目为N：
$$ N = \frac{{\log (1 - r)}}{{\log (1 - {{(1 - e)}^k})}} $$ 当路径的数目小于N时，其中的一些路径就要分担更多的任务，重复传输数据。但如果路径的数目大于N，则采用后续文章中的算法，从这些路径中挑选N条路径来进行传输，在传输的过程中避免了拥塞的发生以及合理控制网络中节点的剩余能量，解决在传输过程中的延迟问题。
在路径建立的初期，先采用RTT (round time of trip) 来计算路径的往返时间，用RTT作为唯一的外部指示，从而实现总流量在N条路径上的动态分配功能。为了防止RTT的波动而引起流量分配的震荡，所以采用下式对RTT进行调整：
$$ {\rm{RT}}{{\rm{T}}_{{p_{_i}}}} = (1 - \alpha ){\rm{RT}}{{\rm{T}}_{{p_{_i}}}}(t - 1) + \alpha {\rm{RT}}{{\rm{T}}_{{p_{_i}}}}(t)\;\;(1 \le {P_i} \le N) $$ 为了准确地控制分配速率$W_{s, {p_i}}^d$(其中，d、s为常量)，将每一条路径都分配一个权重$\alpha $，并为每条路径统计最近t时间段内分配的流量${M_{{p_i}}}$，可得：
$$ W_{s, {p_i}}^d = \frac{{\frac{1}{{{\rm{RT}}{{\rm{T}}_{{p_i}}}}}}}{{\sum\limits_{{p_i} \in P_s^d} {\frac{1}{{{\rm{RT}}{{\rm{T}}_{{p_i}}}}}} }}\frac{{\frac{1}{{{M_{{p_i}}} + 1}}}}{{\sum\limits_{{p_i} \in P_s^d} {\frac{1}{{{M_{{p_i}}} + 1}}} }}\frac{{{E_{{p_i}}}}}{{\sum\limits_{{p_i} \in P_s^d} {{E_{{p_i}}}} }} $$ 式中，${E_{{p_i}}}$为路径pi中能量最小节点能量。
计算得出每一条路径中的分配权重。最后路径上的分配速率为：
$$ \lambda _{s, {p_i}}^d = \frac{{W_{s, {p_i}}^d}}{{\sum\limits_{{p_i} \in P_s^d} {W_{s, {p_i}}^d} }} $$ 则该条路径上分配的流量为：
$$ \lambda _{s, {p_i}}^d = \frac{{W_{s, {p_i}}^d}}{{\sum\limits_{{p_i} \in P_s^d} {W_{s, {p_i}}^d} }}NR $$ 式中，R是数据源的数据发送率；一共构建的路径数量为m；算法复杂度为O(N)。
ECOTA算法
Begin
For ${P_i}$=1 to m
利用RTT来获取路径上${\rm{RT}}{{\rm{T}}_{{p_i}}}$和${E_{{p_i}}}$
End For
If m≥N
选择出路径中$W_{s, {p_i}}^d$最大的N条路径
End If
为N条路径分配流量$\lambda _{s, {p_i}}^d=\frac{{W_{s, {p_i}}^d}}{{\sum\limits_{{p_i} \in P_s^d} {W_{s, {p_i}}^d} }}NR$
End
-
在无线传感器网络中，检测网络中是否出现拥塞状况最普遍的方法是判断缓冲区的占用率 (buffer occupancy, BO) 是否超过某一个阈值，如果节点的占用率超过了阈值则说明在网络中可能出现了拥塞状况。但采用阈值作为网络中出现拥塞的依据并不一定能够真实地反映出网络中的真实状况。另一种普遍的方式是计算节点的报文发送率与接收率之间的比值，此方法可以用来检测当时节点缓冲区的状况，但如果出现高拥塞的情况。缓冲区剩余的空间很小，造成大量的丢包情况，则有可能出现报文的接收率与发送率 (congestion level, CL) 的比值变得很小。本文结合了类似CODEM (cogestion detection and mitigation, ECODEM) 的方法，利用以上的两种技术来判断网络中是否出现拥塞状况，提出了一种ECODEM的方法。由于CODEM在检测拥塞过程中采用的是静态判定方法，仅仅依靠几个固定阈值来判定网络中拥塞是否发生。ECODEM采用梯度的方式来对拥塞的发生进行检测。
通过节点缓冲区的变化幅度 (buffer change, BC) 可以直接预测出节点在下一时刻的状况，并为BO设定阈值${\alpha _1}$和${\alpha _2}$，检测的规则如下：如果预测到在下一时刻有可能会发生拥塞或拥塞解除，则控制节点的发送率为$\rho=\lambda _{s, {p_i}}^d\; (0 \le \rho \le 1)$。
规则1 如果节点的${\rm{BO}} < {\alpha _1}$，且节点收到来自上游拥塞的反馈消息，且${\rm{BC}} > \gamma $，则控制节点的发送速率为$\rho=\lambda _{s, {p_i}}^d$。
规则2 如果节点的缓冲区占用率${\rm{BO}} > {\alpha _1}$，拥塞位被置上，拥塞节点开始发后向压力消息控制上游节点发送数据报文的速率。
规则3 如果节点的缓冲区占用率${\rm{BO}} > {\alpha _2}$，节点开始主动丢包。
规则4 如果节点收到来自前向的拥塞消息，且${\rm{CL}} > \beta $，同规则2。
规则5 如果${\rm{BO}} > {\alpha _1}$且${\rm{CL}} < \beta $，${\rm{BC}} < \gamma $则说明拥塞已缓解，则提高控制节点的发送速率为$\lambda _{s, {p_i}}^d\mu $。
规则6 如果${\rm{BO}} < {\alpha _1}$且${\rm{CL}} < \beta $，则说明拥塞已缓解，此时拥塞位置回0。
如果在网络中出现了拥塞状况，则应该对路径中的流量重新分配，尽可能多地使用那些未使用的路径，同时减少路径中的流量传输。由于ECOTA建立了无重复节点的状况，因此在ECODEM中就可以不用考虑因路径交叉而造成的流量重分配问题。ECODEM的主要思想是在采用无交叉的路径的前提下，把网络中拥塞区域的流量转移到其他非拥塞区域。在判断网络检测拥塞区域的位置时采用CODEM中拥塞深度 (congestion depth, CD) 的方法。而在最终重新分配时仍然会考虑到ECOTA中使用的节点的能量、延迟两个方面的因素，算法复杂度为O(N)。
ECODEM算法
Begin
For ${P_i}$=1 to N
根据后向压力消息获得第${P_i}$条路径的CD值。
End For
If未使用的路径数大于或等于拥塞路径数，则将流量转移到未使用路径上
End If
If未使用的路径数小于拥塞路径数
对于已拥塞的路径
$$ \begin{array}{c} W_{s, {p_i}}^d = \\ \frac{{\frac{1}{{{\rm{RT}}{{\rm{T}}_{{p_i}}}}}}}{{\sum\limits_{{p_i} \in P_s^d} {\frac{1}{{{\rm{RT}}{{\rm{T}}_{{p_i}}}}}} }}\frac{{\frac{1}{{{M_{{p_i}}} + 1}}}}{{\sum\limits_{{p_i} \in P_s^d} {\frac{1}{{{M_{{p_i}}} + 1}}} }}\frac{{{E_{{p_i}}}}}{{\sum\limits_{{p_i} \in P_s^d} {{E_{{p_i}}}} }}{\rm{CD}}_{s, {p_i}}^d\theta \end{array} $$ 重新分配的流量为：
$$ \lambda _{s, pi}^d = \frac{{W_{s, {p_i}}^d}}{{\sum\limits_{{p_i} \in P_s^d} {W_{s, {p_i}}^d} }}NR $$ End If
End
算法中，Q为常量
-
为了验证本文算法的性能，对算法使用NS2仿真器进行仿真。在仿真中，无线传感器网络一共有50个节点随机分布在1个1 000x1 000的空间内，每个节点的传输半径为250，数据传输率为1 Mb/s，节点初始能量为1 000 J，节点在发送数据和接收数据时都有能量消耗。仿真使用了分组递交率和平均端到端延时两种指标来判断算法的性能，每个设置均进行了多次试验来避免误差。仿真中假设网络拓扑中每个目标节点的路由路径都是已知的。
本文使用了两个性能指标来对比ECOTA、ECODEM和传统的COTA、CODEM算法的性能。
1) 分组递交率${P_d}$。该指标表示目的节点在源节点发送的所有分组中成功收到的比例。可以用${P_d}$来反应多路径路由的可靠性程度${P_d}=\frac{{{P_{{\rm{rcv}}}}}}{{{P_{{\rm{sent}}}}}}$，${P_{{\rm{rcv}}}}$表示目标节点成功接收的分组的个数，${P_{{\rm{sent}}}}$表示源节点发送出的分组的个数。
2) 端到端延时。该指标表示分组从源节点到达目标节点的时间。包括路由发现、接口排队、重传和传播时延。其中${T_{{\rm{disv}}}}$表示路由发现时间，${T_{{\rm{que}}}}$表示接口排队时间，${T_{{\rm{tran}}}}$表示重传时延，${T_{{\rm{prop}}}}$表示传播时延。在仿真试验中，对两种算法进行了对比，其中网络的连接数为5。源节点和目标节点在网络中随机选择。网络中的路由使用标准的路由算法，仿真中路由指标为源节点数据发送率的函数。根据结果可以看出当数据传输率为5包/s的时候，两种算法的协议的性能类似。当数据率低的时候，网络不拥塞基本没有发生包丢失的情况。
图 1 分组递交率对比
当数据发送率低的时候两种协议基本的性能基本相同，当数据包发送速率增加为15包/s的时候COTA+CODEM的性能开始急剧下降，而本文提出的ECOTA+ECODEM算法的分组递交率只有缓慢的下降，可以看到拥塞对于发送数据的递交率影响较小，能够达到较大的可靠性。
从图 2中可以看出，随着网络负载的增加，端到端的延时不断增加，在数据传输率为20包/s的时候，两张算法的分组递交率差不多，接着ECOTA+ ECODEM的优势开始显示，算法的端到端延时降低10%左右，网络中报文排队的时间明显减少，用户体验提升。
图 2 端到端延时对比
-
本文针对网络中出现的拥塞现象，提出了一种ECOTA+ECODEM算法，可实现网络中的拥塞避免、检测和缓解的策略。在衡量了路径的能耗与延迟的前提下，合理地分配了路径流量，使得节点能够更快地从拥塞状况中恢复出来。另外，还提出了对于拥塞的预测方法，能够更准确地分析出网络中是否出现拥塞状况。仿真结果表明，本文提出的算法比COTA+CODEM性能提高10%左右，能够有效地提高分组成功递交率和降低端到端延时，从而提高网络的整体性能。
Wireless Sensor Network Traffic Reallocation Congestion Control Algorithm
-
摘要: 基于流量分配与重分配的算法，提出了一种改进的拥塞流量分配 (ECOTA) 和有效的拥塞检测和缓解 (ECODEM) 算法。在衡量了所有路径的能耗与传输延迟之后，选出若干条能耗低、延时短的路径，增加了数据传输的成功率。通过设定阈值与预测的方法对网络中的拥塞区域进行检测，一旦拥塞发生，采用合理重分配流量的方式，使节点能够更快地从拥塞状况中恢复出来，并保证拥塞区域的数据能尽快被转移到非拥塞区域。仿真结果表明，与其他算法相比，该算法能够提高分组成功递交率，降低端到端延时，提升网络的整体性能。Abstract: An enhanced congestion traffic allocation (ECOTA) and an efficient congestion detection and mitigation (ECODEM) algorithm are proposed in this paper, based on the traffic allocation and reallocation algorithm. After measuring the energy consumption and transmission delay of all paths, some low energy consumption and short delay paths are selected to increase the success rate of data transmission. The congested area is detected by methods of setting the threshold and prediction. Once the congestion occurs, nodes can quickly recover from congested situations by using reasonable traffic reallocation. And traffic in the congested area can be transferred to the non-congested area as soon as possible. Simulation results show that compared with other algorithms, the proposed algorithm can improve the success rate of packet delivery, reduce the end to end delay and improve the overall performance of the network.
-
Key words:
- congestion control /
- data transfer /
- traffic reallocation /
- wireless sensor networks
-
[1] AKYILDIZ I F, SU W, SANKARASUBRAMANIAM Y, et al. Wireless sensor networks:a survey[J]. Computer Networks, 2002, 38(4):393-422. doi: 10.1016/S1389-1286(01)00302-4 [2] KAFI M A, DJENOURI D, BEN-OTHMAN J, et al. Congestion control protocols in wireless sensor networks:a survey[J]. IEEE Communications Surveys & Tutorials, 2014, 16(3):1369-1390. https://www.researchgate.net/publication/264937612_Congestion_Control_Protocols_in_Wireless_Sensor_Networks_A_Survey [3] SERGIOU C, ANTONIOU P, VASSILIOU V. A comprehensive survey of congestion control protocols in wireless sensor networks[J]. IEEE Communication Surveys & Tutorials, 2014, 16(4):1839-1859. https://www.researchgate.net/publication/273396298_A_Comprehensive_Survey_of_Congestion_Control_Protocols_in_Wireless_Sensor_Networks [4] SANKARASUBRAMANIAM Y, AKAN O B, AKYIDIZ I F. ESRT:Event to sink reliable transport in wireless sensor networks[C]//Proc of the 4th ACM Int'l Symp on Mobile Ad Hoc Networking and Computing. New York:ACM, 2003:177-188. [5] WAN C Y, EISENMAN S B, CAMPBELL A T. CODA:Congestion detection and avoidance in sensor networks[C]//Proc of the 1st ACM Conf on Embedded Networked Sensor Systems. New York:ACM, 2003:266-279. [6] HU Yue-ming, XUE Yue-ju, LI Bo, et al. SenTCP:a hop-by-hop congestion control protocol for wireless sensor networks[C]//IEEE INFOCOM 2005. Miami, USA:[s.n.], 2005. [7] DRESSL F. Locality driven congestion control in self-organizing wireless sensor networks[C]//The Int'l Workshop on Software Architectures for Self-Organization, and Software Techniques for Embedded and Pervasive Systems. Munich, Germany:[s.n.], 2005. [8] KARENOS K, KALOGERAKI V, KRISHNAMURTHY S V. Cluster-based congestion control for supporting multiple classes of traffic in sensor networks[C]//The 2nd IEEE Workshop on Embedded Networked Sensors. Sydney:[s.n.], 2005. [9] CHEN Shi-gang, YANG Na. Congestion avoidance based on lightweight buffer management in sensor networks[J]. IEEE Trans on Parallel and Distributed Systems, 2006, 17(9):934-946. doi: 10.1109/TPDS.2006.115 [10] WAN C Y, EISENMAN S B, CAMPBELL A T. Energyefficient congestion detection and avoidance in sensor networks[J]. ACM Transactions on Sensor Networks, 2011, 7(4):289-307. https://www.researchgate.net/publication/220442992_Energy-Efficient_Congestion_Detection_and_Avoidance_in_Sensor_Networks [11] CHAKRAVARTHI R, GOMATHY C. IPD:Intelligent packet dropping algorithm for congestion control in wireless sensor network[C]//T Trendz in Information Sciences & Computing (TISC2010). Chennai:IEEE, 2010:222-225. [12] LI Shan-cang, ZHAO Shan-shan. Adaptive and secure load-balancing routing protocol for service-oriented wireless sensor networks[J]. IEEE Systems Journal, 2014, 8(3):858-867. doi: 10.1109/JSYST.2013.2260626 [13] QIAN Peng, DONG En-qing. Multipath routing protocol based on congestion control mechanism implemented by cross-lay design concept for WSN[C]//IEEE 17th International Conference on Computational Science and Engineering.[S.l.]:IEEE, 2014, 378-384. [14] SUN Guan-nan, QI Jian-dong, ZANG Zhe, et al. A reliable multipath routing algorithm with related congestion control scheme in wireless multimedia sensor networks[C]//20113rd International Conference on Computer Research and Development. Shanghai:[s.n.], 2011, 4:229-233. [15] REN Feng-yuan, HE Tao, DAS S, et al. Traffic-aware dynamic routing to alleviate congestion in wireless sensor networks[J]. IEEE Transactions on Parallel and Distributed Systems, 2011, 22(9):1585-1599. doi: 10.1109/TPDS.2011.24 [16] 李姗姗, 廖湘科, 朱培栋, 等.传感器网络中一种拥塞避免、检测与缓解策略[J].计算机研究与发展, 2007, 44(8):1348-1356. doi: 10.1360/crad20070810 LI Shan-shan, LIAO Xiang-ke, ZHU Pei-dong, et al. Congestion avoidance, detection and mitigation in wireless sensor networks[J]. Journal of Computer Research and Development, 2007, 44(8):1348-1356. doi: 10.1360/crad20070810 -
点击查看大图
图(2)
计量
- 文章访问数: 4393
- HTML全文浏览量: 1251
- PDF下载量: 135
- 被引次数: 0
