ABSTRACT

Due to the limit of sensor node in Wireless Sensor Network (WSN), the network will lead to congestion when a lot of data streams aggregate in a node. This situation will result in the loss of large amounts of data packets and the deterioration of Quality-of-Service. It has been a hot topic to limit the rate of data traffic and avoid possible congestion in the WSN. By integrating the rate limiting method of the relaxation technology (RT) and the equitable distribution method of max-min fair (MMF) resource sharing, this paper proposes a novel adaptive rate limiting congestion control (ARLCC) algorithm to solve the congestion in WSN. The experiments show that ARLCC scheme can alleviate the network congestion and ensure the fairness and reliability of data transmission.

Keywords:Wireless Sensor Network, Congestion Control, Relaxation Technology, Max-Min Fairness

基于自适应速率限制的拥塞控制 算法研究

张品，高大冬，王春霞，张洪峰

杭州电子科技大学通信工程学院，浙江 杭州

Email: gddgdd2463@163.com

收稿日期：2015年1月23日；录用日期：2015年2月5日；发布日期：2015年2月10日

摘 要

由于无线传感器网络(WSN)中传感节点的局限性，网络数据流在节点处聚集易引起网络拥塞，造成大量数据包的丢失，从而降低网络的服务质量。如何限制网络数据流的传输速率，对拥塞进行控制一直是无线传感器网络的研究热点之一。为解决无线传感器网络中的拥塞问题，本文结合松弛技术的速率限制方式和最大–最小公平性的资源共享分配方式，提出一种基于自适应速率限制的拥塞控制算法(ARLCC)。仿真实验表明，ARLCC方案不仅能有效缓解拥塞，还保证了数据包传输的可靠性和公平性。

关键词 :无线传感器网络，拥塞控制，松弛技术，最大–最小公平性

1. 引言

微型电子机械系统技术和无线通信技术的快速发展，使得无线传感器网络(WSN)在许多领域中吸引了越来越多的关注。但WSN自身有限的带宽和存储容量，容易使得节点缓存被大量的感知数据所超载，造成大量数据包的丢失，这种直观上称之为拥塞的问题将会降低网络的服务质量。因而，网络拥塞成为了WSN研究领域的一个重要课题[1] 。

目前，基于速率限制的方案已被广泛用于解决WSN拥塞问题。文献[2] 是第一个基于速率调节的拥塞控制方案，该方案通过监测本地缓存占有率并当它超过一定阀值时将通知源节点控制发送速率。文献[3] 通过父节点和子节点的相互协作，使得所有子节点发送速率之和不大于父节点的接收速率。文献[4] 提出一种基于节点级的速率优化拥塞控制方案，通过优化拥塞节点和邻居节点的发送速率，可以减少数据包的丢失，提高网络资源的利用率。而在WSN中假设数据包到达速率等于数据包服务速率不在适用[5] 。CODA (congestion detection and avoidance)中拥塞的发生是通过结合缓存占有率和信道负载条件进行监测的[6] ，一旦最大理论吞吐量的阀值超过80%，一种称之为Back-pressure (BP)的抑制信息将会发送到上游节点以抑制传输，但基于加性增加乘性减少(AIMD)的速率调节方案会导致源速率震荡严重，另外，节点对信道的周期性监测也会消耗额外的能量。

以上研究表明，仅仅通过简单的速率限制并不能解决WSN网络的拥塞问题。另外，传感节点的资源有限(如带宽)，确保多个输入数据流共享中间节点资源的公平性也尤为重要。

目前，解决资源的公平分配问题主要是采用一种称之为最大–最小公平性(Max-Min Fairness, MMF)机制进行解决，该机制能够确保各个共享者所能获得资源的最大分配。文献[7] 利用最大–最小公平性机制解决了交换设备中流量共享拥塞链路的带宽的公平分配。文献[8] 解决了正交频分多址系统中无线资源的分配问题，既保证用户的最小速率要求，同时用户之间满足最小速率的最大化公平性。文献[9] 使用一种分散算法来获得最大–最小公平性。在这种方法中，节点基于两跳以内的拓扑信息来计算将用于传输的概率。文献[10] 中的方案通过为每个数据流设计一个动态权值来确保资源的公平分配。然而，该方案需假设缓存足够大到可以调节所有的输入数据包，显然该假设不切实际，故该方案也不适用于WSN。

为保证数据包传输的可靠性和公平性，本文提出一种自适应的速率限制拥塞控制方案(ARLCC)。ARLCC基于松弛技术(Relaxation Technology, RT)的缓冲机制，在中间节点上根据数据包到达速率和自身容量计算出一个称之为处理水平(Engineering Level, EL)的参数作为数据流的转发速率。一旦EL值超过节点容量，ARLCC将通过最大–最小公平性(Max-Min Fairness, MMF)机制重置输入流的速率为0，然后再以恒值速率增加。当某个输入流速率达到链路限制后，便保持该速率值并以此值持续发送，直到所有的输入流速率不能再有所增加为止。仿真结果表明，ARLCC能够有效避免数据包丢失，实现数据包的可靠传输，保证了共享节点资源的公平性。

2. 系统模型

提出的ARLCC方案系统模型如图1所示，该模型包含两种机制：RT机制和MMF机制。与其他学者之前的研究显著不同，ARLCC通过及时清空节点缓存，为即将到来的数据包腾出空间，从而避免可能发生的数据包溢出。中间节点基于可用资源计算出特定的EL值进行自适应控制数据包的传输速率。在任何一个时刻，如果中间节点上计算的EL值超过节点的可用容量，MMF机制将会自动启动，重置所有输入流的速率，有效控制网络的大数据流，并向所有的竞争数据包提供公平的带宽分配。

3. 拥塞控制算法的分析

3.1. 松弛技术

松弛技术是最先用于权衡系统缓存数量和带宽之间的一种机制[11] 。该机制的新颖之处在于它是对过剩的输入数据包进行松弛，即将它们推迟到任何允许的单位延迟而不会有任何的额外损失或延迟。在本文中，RT机制主要是通过可用资源推导出的EL参数来实现上述功能。EL定义了可以用于传输等待数据包的可用空间，即在每个到达时刻，只有EL个数据包被传输，过量的数据包将会被放入节点缓存中并且至多可缓存个数据包。因而，EL的正确估值对于确保数据包的可靠传输是至关重要的。

在ARLCC方案中，EL的值主要是通过四个参数来获取：数据包到达率，开始时刻，结束时刻和允许的单位延迟，如下所示：

(1)

的值来源于数据包平均到达率，其中。WSN中数据包的到达服从非均匀的泊松分布，故数据包到达率可以表示为[12] 。

当延迟引入系统后，缓存内未完成的数据包可由下式得出，即：

(2)

其中可从平均到达率与数据包到达率的交点来获得。这里可能会存在与交叉在不同的个值，也就会出现个值，为表述方便，本文只考虑有一个交点时的情形。的值由下式可得：

图1. ARLCC方案的系统模型

(3)

则和之间的最大值将在下面等式中进行比较，可得：

(4)

最后，上式(4)中的最大值将会选择作为EL值。接下来，仍然需要检查每次选择的EL值是否满足两个条件和，这两个测试条件可以确认获取的值是否正确，前者表示最大可允许的未完成数据包数应该等于缓存大小；后者确保了传输结束时缓存内无等待的数据包。

实现RT机制的算法过程总结如下：

1) 根据节点输入端的数据包到达速率计算平均到达速率；

2) 根据计算的值(可能会存在多个值)；

3) 根据，计算的值，将和的最大值作为的值；

4) 计算EL的值；

5) 验证EL值的正确性：如果EL满足和，则EL值正确且无拥塞发生和数据包丢失；反之，说明EL值不正确，网络发生拥塞和数据包丢失，重复步骤(2)到(5)重新计算EL的值。

3.2. 松弛技术的局限性

RT机制在处理拥塞网络方面具有独特性，它可以将数据包尽可能地发送。然而，在多节点传送过程中，RT机制将会产生很高的EL值，由于WSN中的资源限制将造成这个EL值不可取。这是因为每个中间节点上多个输入流EL的聚合，再加上当前节点自己所产生的到达速率，将产生很高的EL值。这种情形可以用下面的形式进行解释。

(5)

这里表示数据包到达速率，是传感节点，代表第个传感节点。是中间节点，它接收所有来自上游节点的数据包。因而，产生的EL值具有如下特征：

(6)

由此可知，输入节点数越多中间节点产生的EL值就越大，会出现EL值大于节点带宽的情形，这显然违背了传感器网络资源有限的特征。因此，必须使用一种资源的公平性分配方案来合理调节带宽，消除高EL值带来的影响。

3.3. 最大–最小公平性

本文讨论通过使用最大–最小公平性机制来弥补单独使用RT的局限性。一般来说，MMF适用于这样的情况，即当多用户竞争要求共享一定的资源时，希望获得一个理想的资源公平分配，MMF机制可保证共享者可以获得自身所能获得最大额度的资源分配[13] 。

当网络中的节点产生的EL值大于节点容量时，MMF机制就会自动启动，利用渐进填充算法来处理饱和或拥塞链路情况下资源分配的公平性问题，从而使节点的各个输入数据流之间达到所谓的最大–最小公平性。在本文中该算法的流程可总结如下：

1) 中间节点检查获取的EL值是否大于节点容量C，如果是则跳到步骤(2)，反之，算法结束；

2) 将所有子节点的发送速率。然后，以大小为的恒定速率同时增加所有子节点的发送速率；

3) 继续增加，当某一个或多个链路速率达到限制或饱和时便冻结该速率值，并以此值进行发送；

4) 重复步骤(3)的操作，直至所有链路上的速率没有再增加的可能；

这里。可知，在初始情况下所有的发送速率被设置为，然后同时以大小为的恒定速率增加，直到某个或多个资源达到最大限制速率。可知，这些速率的增加仍受限于节点链路容量，即：

(7)

可知第一个达到的限制速率为。故第一个饱和链路发送速率为：

(8)

为获得其它节点的发送速率，在不饱和链路的情况下，各个节点的速率会持续增加，直到达到下一个限制。这个速率将由下面的公式获得：

(9)

由上式可知，由于初始发送速率已经确定，剩下的链路容量可以继续分配给其它未饱和的链路。在任何情况下，如果资源的数量等于所有链路数，则所有资源获得的速率大小相同，下式能够反映出获得的下一个饱和资源的发送速率。

(10)

4. 仿真结果和分析

为衡量ARLCC的性能，本文在网络仿真工具NS-2的“”框架下模拟WSN环境进行实验分析[14] 。采用分簇的方式将传感器节点分成小组的形式，每个组设定一个称为簇首(CH)的节点，簇首节点将来自其他任何传感节点的数据包转发到Sink节点。该实验基于标准的ZigBee/IEEE 802.15.4协议栈，它具有很小的功耗，带宽与Bluetooth (1 Mps)相比只有250 Kbps。仿真区域大小为500 × 500 m²，20个传感节点随机均匀分布，传输距离为50 m，无线传输信道为二径传输信道。仿真时间为10 s，恒速率增加值为100数据包/秒，数据包大小为30 byte，允许的单位延迟为150毫秒。为了在不同的单位时间创建不同的数据包到达速率，本文将使用随机数产生器产生随机的数据包数量。

在图2中，(a)为数据包丢失数量的比较，可以看出单独的RT机制不能有效处理随着节点增加而增加的高EL值，造成大量数据包的丢失，而结合MMF机制的ARLCC方案可以自适应调节节点输入端的数据流速率，能有效避免高EL值的影响，(b)中端到端延迟的性能比较也有效证实了这一点。

在图3中，本文比较了RT、ARLCC和CODA在不同负载百分比下的性能。(a)为平均能量消耗。当负载大于100%表明将会产生超越可用资源的过量数据包。图(a)中可以观察到，本文提出的ARLCC机制一直比RT和CODA表现更好，具有更小的能量消耗。这是因为ARLCC机制中数据包丢失数和相关延

图2. RT机制和ARLCC的比较。(a) 数据包丢失数量；(b) 平均端到端延迟

图3. 标准RT、ARLCC和CODA的性能比较。(a) 平均能量消耗；(b) 吞吐量

迟的减少，使得重传这些丢失数据包所需的能量也显著减少；(b)为网络吞吐量。在正常的传输场景下，拥塞发生时，吞吐量会骤然地下降。有限资源(带宽和缓存空间)上负载百分比的增加更加触发了数据包间的竞争，大量的数据包将会因为竞争和不充分的缓存空间而丢失，如(b)中圆圈所标注的曲线部分。相比较而言，ARLCC由于采用了MMF和RT的结合，当负载百分比逐渐增加甚至大于100%时并没有出现下降的趋势，而RT和CODA的吞吐量在负载百分比大于80%时都出现了急剧的下降。

5. 结束语

本文提出了一种自适应的速率限制方案(ARLCC)来解决WSN的拥塞问题。ARLCC是一种使用缓存管理和速率限制的新型拥塞避免方法，它结合现有的RT机制和MMF机制来获得性能的优化。ARLCC增强了网络系统避免拥塞的能力，特别是根据RT机制推导出的EL值在给定的链路容量下不能很好地处理网络大流量数据时的情况，它的提出将会更加适用。实验表明，ARLCC能够比单独使用RT机制和CODA机制带来更显著的性能改善，保证了数据包传输的可靠性和共享节点资源的公平性。

致谢

感谢国家自然科学基金资助项目(61271214)。

文章引用

张 品,高大冬,王春霞,张洪峰, (2015) 基于自适应速率限制的拥塞控制算法研究
A Research Based on Adaptive Rate Limiting Congestion Control Algorithm. 无线通信,01,36-42. doi: 10.12677/HJWC.2015.51006

参考文献 (References)