无线传感器网络中的拥塞控制
Bret Hull,Kyle Jamieson,Hari Balakrishnan 麻省理工学院计算机科学与人工智能实验室
The Stata Center,32 Vassar St.,Cambridge,MA 02139
{bwhull,jamieson,hari}@csail.mit.edu
目录
摘要 .................................................................................................................................................. 0 1. 引言.............................................................................................................................................. 0 2. 拥塞控制难题 .............................................................................................................................. 1
2.1 度量标准 ............................................................................................................................ 2 3. 拥塞缓解 ...................................................................................................................................... 3
3.1 逐跳流量控制 .................................................................................................................... 3 3.2 速率限制 ............................................................................................................................ 4 3.3 MAC层优先级化 ............................................................................................................ 4
3.3.1 终端隐藏问题 ......................................................................................................... 5 3.4 应用自适应 ........................................................................................................................ 5 4. 实验评价 ...................................................................................................................................... 5
4.1 定期工作负载 .................................................................................................................... 6
4.1.1 定期工作负载：网络有效性 ................................................................................. 6 4.1.2 定期工作负载：非平衡性 ..................................................................................... 7 4.1.3 定期工作负载：吞吐量和公平性 ......................................................................... 8 4.1.4 定期工作负载：等待时间 ..................................................................................... 8 4.1.5 定期工作负载：损失来源 ..................................................................................... 8 4.1.6 定期工作负载：能量方面的考虑 ......................................................................... 9 4.2 高扇入网络实验 ................................................................................................................ 9
4.2.1 高扇入网络：网络有效性 ................................................................................... 10 4.3 事件相关工作负载 .......................................................................................................... 10
4.3.1 事件相关工作负载：网络有效性 ....................................................................... 10 4.3.2 事件相关工作负载：丢失率 ............................................................................... 11 4.3.3 事件相关工作负载：等待时间 ........................................................................... 11
5. 相关工作 .................................................................................................................................... 11 6. 总结............................................................................................................................................ 12
6.1 未来的工作 ...................................................................................................................... 13 致谢 ................................................................................................................................................ 13 7. 参考文献 .................................................................................................................................... 13
摘要
网络任意点提供的流量负载超过其可用容量时就会出现网络拥塞现象。在WSN中，拥塞会引起整体的信道质量下降及丢失率的上升，导致缓存器溢出、延迟增大（就像在有线网络中一样），并且，对于那些要经过多跳传输数据的节点来说是极其不公平的。
有线网络中的拥塞控制常常使用端到端速率自适应技术和网络层丢失与信令技术共通协作完成。然而，这种方法没有解决无线网络拥塞控制问题，原因是并发的无线电传输在不同的“链路”上会相互作用相互影响，另一个原因是无线信道质量表现出的高度可变性超过了多个时标。我们研究跨越传统协议栈的不同层的三种技术：逐跳流量控制，源流量速率限制，MAC层优先级化协议。我们在用55个节点构建的WSN上实现这些技术并给出实验结果。我们证明了这些技术的融合技术，Fusion，可以在低于实际工作负载情况下通过这三个技术的特点改善网络有效性。
分类和主题描述：C.2.2[计算机通信网络]：网络协议 概述：测量，性能，设计，实验。
关键词：WSN，拥塞控制，流量控制，速率限制，网络性能。
本文是基于国家科学基金会支持完成的，批准号为0205445。同时支持该项工作的还有麻省理工学院氧气项目的合作伙伴英特尔公司，以及斯隆基金会奖学金。
允许这项工作全部或部分的数字或硬拷贝使用于个人或教育，这种的情况下是不收取费用的，前提是拷贝件不能用于以盈利或商业化为目的，拷贝件在其首页需有类似的通知及标注完整的引用。若要以其他方式拷贝，再发行，在服务器上发布或重新分配到列表，均需要事先得到特定的许可或付费。
SenSys'04,November 3.5,2004,Baltimore,Maryland,USA. Copyright 2004 ACM 1-58113-879-2/04/0011...$5.00. 1. 引言 引起突发消息时，更加可能发生拥塞。 在传统的有线网络和蜂窝无线网
提供极少发生拥塞事件的WSN络中，缓存器溢出和时延增大是拥塞是非常困难的。传感器网络交付各种的征兆。在过去的许多年中，研究人
员已经研究了用端到端速率（窗口）类型的流量，从简单周期性报告到不
可预测的、由所感知到的外部事件触自适应技术和网络层丢失与信令技术发的突发消息。即使是已知周期性通的融合来确保有线网络和蜂窝无线网
络不会因为拥塞而崩溃。除了缓存器信模块和简单的网络拓扑的WSN，拥
塞也会发生，原因是无线信道随着时溢出外，WSN拥塞的一个主要征兆是间变化（常常是剧烈变化），且在不同网络其他区域发送的流量增大导致无“链路”上同时进行数据传输会互相线信道质量恶化。因为无线“链路”
不像有线信道或者蜂窝无线链路那样作用、互相影响，从而导致信道质量
不仅与噪声有关而且与流量密度有物理上相互屏蔽、相互隔离，所以传关。此外，传感器的入网或退网，或输通过网络一个给定区域的流量对网
络其他部分的信道质量和丢失率会产者报告速率的改变都会引起网络原先
不拥塞的部分变得拥塞。当感知事件生不利影响。无线信道质量差且具有
时变性，不对称通信信道，隐含终端都会导致调整好的流量难以交付。另外，在流量负载作用下，多跳WSN严重影响分组的多跳传输，导致极大的不公平性。
本文研究这三种拥塞控制技术在传统网络协议栈的不同层中的应用，并表明网络拥塞的不利影响可以在这三种技术的协调作用下得到极大的缓解。第一种技术是逐跳流量控制技术，节点通过后压相互发送本地拥塞信号，防止对在下行节点中被确定为丢弃的分组做无用传输，降低分组丢失率。第二种技术是源速率限制技术，用于减轻对其数据传递必须通过许多转发跳才能到达中心节点的源节点的严重不公平问题。第三种技术是MAC层优先级化技术，使拥塞节点的共享信道访问权优先于非拥塞节点，避免缓存器溢出问题。我们把这三种技术结合成一个名为Fusion的新策略。单独来讲，每一种技术都能在一定程度上减轻拥塞问题，但是将三种综合在一起使用，Fusion可以明显地改善网络有效性、公平性和信道丢失率。这些实验结果，连同上述机制的设计细节，是本文的主要的贡献。
为了研究发展这些技术，我们从前人的工作中汲取了大量的经验和结论。例如，我们的逐跳流量控制方案是从已完成的有线网络工作及将该主意应用于WSN中的近期工作[参考文献22]中受到启发的。我们的源速率限制方案和类似的体制一样都是受前人的工作[参考文献24]启发的。不管怎么样，我们的方案及这些方案协同运作的详细说明，以及这些方案单独或者协同作用时的详细的实验评估都对我们的工作有着至关重要的贡献。我们用一个包含55个节点的室内WSN测试平台来评估每一个方案。在我们的测试平台中，Fusion通过三个因素改善有效性，通过两个以上的因素改善不公平性。
在下一章，我们将展示我们的实验结果，突出WSN中的拥塞问题并描述我们用于评估不同拥塞控制方法的各种性能标准。我们在TinyOSon下开发了一个网络栈，实现了如上所述的三种拥塞控制技术的几个变种；在第3章讨论这几种技术是如何共同运作控制拥塞的。在第4章，我们在不同的通信模式下单独地、共同协作的情况下研究这些拥塞控制机制。第5章给出了与相关工作的详细比较。第6章总结我们主要的研究成果并介绍未来的研究方向。
2. 拥塞控制难题
这一章分析WSN中拥塞崩溃的两个关键症状。以下的结果来自室内Mica2 WSN测试平台，我们会在第4章详细介绍该平台。每个节点以恒定的速率产生数据，其他的传感器通过多跳传递将数据转发中心节点。随着负载的增加，丢失率也迅速增加。图1（左边）表示各种负载下的全网丢失率。我们将无线信道误码引起的丢失率和节点缓存器溢出引起的丢失率分离开。我们发现无线信道误码对丢失率起主导作用，且随着负载的增加而迅速增大。丢失率急剧增大是拥塞崩溃的两个主要症状之一。
图1：信道和缓存器丢失率与每个人节点产
生负载的关系变化（左图）。
拥塞崩溃的第二个主要症状是距
1
离中心节点一跳的节点产生的流量使得网络的大部分饥饿。图1（中间）表示了该现象。假定一个节点产生的分组被中心节点所接收到的百分比为P，那么互补积累分布函数CDF表示至少将其P%的分组交付给中心节点的传感器所占的比例。我们看到随着负载的增加，节点减少，不成比例地占用大部分网络带宽。
2.1 度量标准
图1：每个节点产生的负载被中心节点接收的比列（互补累积分布函数CDF，中间的
图）。
拥塞崩溃对WSN能量有效性带来极端不利的影响，如图1（右边）所示。当负载增大到高于拥塞点后，同样能量下能够发送的比特数很少。从边沿节点发送给中心节点的数据只会被丢弃（无法传递到中心节点），因而造成了能量浪费。我们将这种现象称为活锁（livelock）。
图1：每个单位能量成功发送的全网比特数
（右图）。
2
在这些定量的观测结果的基础
上，我们提出了若干措施来评估传感器网络在拥塞情况下的性能：网络有效性?，节点的非平衡性?，中心节点接收的总吞吐量，网络公平性?以及中央分组的等待时间。
我们定义有效性为：“有效”分组传递的总跳数除以分组在网络中传输经过的总跳数（表1中的表达式1）。一个“有效”分组就是最终能够到达中心节点。有效性测量很重要，因为网络带宽是有限的且在传感器网络中能源又常常是稀缺的。上述的能量使用结果（图1，右边）启示我们，这种说法将以前的链路有效性的观念[参考文献29,§5.3]扩展到了多跳传感器网络设置中。传输总量包括所有的重传及最终被丢弃或损坏的分组的传输。
我们的有效性度量取决于失败的传输，缓存器溢出，丢失确认引起的重传，以及信道损失。有效性在很大程度上取决于被丢弃的分组，该分组需要跨越多跳才能到达中心节点。因此，有效性测量传感器网络的传输分数，即对分组最终能交付给中心节点的贡献值。有效性同样权衡没有被浪费的传输。
与有效性有关的是非平衡性，即对每个节点交付其子节点的分组给其父节点的满意程度的估量。我们在表1的节点i上定义非平衡性?。当节点N 的?=1时，节点N接收从其子节点接收的数据量等于和发送给其父节点的数据量。当?很大时表示节点N从其子节点接收的数据量比其成功发送的数据量多。非平衡性与简单的缓存器溢出计数不同，原因是无线传输损失直接影响它。
有效性和非平衡性表示一个传感器网络如何有效地依据自己的传输机会和能量传递数据，他们不评估整体
的数据传输速率。因此，我们在中心节点估量并报告总吞吐量及每个节点的平均吞吐量。
实现公平性是可取的，因为在许多遥感应用中存在着关于增长传感器报告率的递减边际效应。换句话说，侦听在地理区域上分散的N个传感器低速率通信比侦听一个传感器的高速率通信更重要。在多跳无线网络中实现公平性是困难的，且通常要以减少总吞吐量为代价[参考文献12,15]。我们用表1显示的指标度量公平性?。
中央分组等待时间的测量是很重要的，因为许多应用需要知道感知与报告之间的最小时间间隔。传感器网络中流量超载会使等待时间增大。注意到，增加缓存空间和流量控制有助于缓解拥塞，但同时也增大了每跳的分组排队时延，增加了端到端的等待时间。
3. 拥塞缓解
公平性之间自然需要折中平衡，允许大流量节点发送，则必然以最大程度竞争给这些节点分配带宽。最后，无线信道本身就是有损信道，因此对数据流进行分布式控制更加富有挑战性。
3.1 逐跳流量控制
我们的拥塞控制方案，我们称之为Fusion，融合了三种技术：逐跳流量控制，速率限制，及MAC层优先级 化技术。逐跳流量控制目的在于，如果节点的分组由于下行节点输出队列空间不足注定要被丢弃，则避免这些节点的传输。速率限制度量允许进入网络的流量以防止对于远离中心节点的源节点的不公平性。MAC层优先级化确保拥塞的节点获得优先访问的信道，允许输出队列发送完所有的分组。虽然这些技术没有明确关于网络拓扑的信息，但本文中旨在单一中心节点和生成树拓扑的研究。
我们还注意到，这些技术在无线领域的应用是困难的。首先，发送节点和接收节点同时存在信道竞争问题。在室内，信道竞争也是一个严重的问题，因为无线传播反射引起传播不稳定并导致两个看似不相交节点集之间相互干扰。第二，信道利用率和
逐跳流量控制已经应用于有线局域网和广域网[参考文献14,16,17]，以及WSN[参考文献11,22]。实现方式：每个传感器在其发送的每个分组头部设置一个拥塞比特。利用无线媒介的广播特性，通过每次发送将拥塞信息反馈给相邻区域中的的所有传感器节点。这就意味着拥塞信息反馈不需要使用直接控制消息，而直接拥塞控制消息需要占用一部分带宽。逐跳流量控制由两部分组成：拥塞检测和拥塞缓解。我们首先讨论两种拥塞检测方法：队列占用法和信道采样法。
一个检测拥塞的简单方法就是监视传感器队列的长度：如果输出队列可用空间部分降到高水位线?下（我们的实验中?=0.25），则将输出分组的拥塞比特位置位；否则将输出分组的拥塞比特位清零。这种队列占用法会带来一些额外的开销，我们会在第4章中对其进行评价。
CODA[参考文献22]提出了一个交替的方法来检测拥塞。当一个分组等待发送时，传感器按照固定的时间间隔采样信道状态。根据信道繁忙的时间长度计算利用率因子。如果利用率高于某个门限值，则将输出分组的拥塞比特置位。否则，将输出分组的拥塞比特位清零。这种信道采样法，我们将在第4章对其进行评价，它要求无线广播不断地在共享媒介上检测载波。
拥塞缓解是一种机制。给定相邻区域内的节点利用拥塞缓解抑制自己
3