ACM通信
无线传感器网络中网络原语的出现
摘要
无线传感器网络社区将网络抽象视为一个开放的问题，随着时间和经验的积累，答案将浮出水面。涓流算法已经成为许多协议和系统中使用的基本机制。涓流使节点快速而有效地达到最终的一致性，同时对网络密度、拓扑和动态的变化保持显著的健壮性。涓流不会让网络充满数据包，而是使用一种“礼貌的八卦”策略来控制发送速率，以便每个节点都能听到足够多的数据包以保持一致。这种简单的机制使Trickle能够扩展到网络密度的1000倍变化，在几秒钟内达到一致性，并且只需要几个字节的状态，却需要每小时发送几个发送的维护成本。涓滴最初设计用于传播新代码，经验表明它具有更广泛的适用性，包括路由维护和邻居发现。本文概述了无线传感器网络面临的研究挑战，描述了涓流算法，并概述了它目前的几种使用方式。
1.无线传感器网络
尽管嵌入式传感应用非常多样化，从栖息地和结构监测到车辆跟踪和射手定位，这些系统使用的软件和硬件架构惊人地相似。典型的体系结构体现在微尘平台上，如所示<一个href="#F1">图1．微控制器提供处理、程序ROM和数据RAM，以及用于传感器输入的模数转换器、用于连接其他设备的数字接口和控制输出。额外的闪存存储程序图像和数据日志。低功率CMOS无线电提供了一个简单的链路层。支持电路允许系统进入低功耗睡眠状态，快速醒来，并对重要事件作出反应。
形成无线嵌入式系统和网络设计的四个基本约束:电源、有限的内存、无人值守操作的需要以及无线通信的有损耗和瞬态行为。电池或采收的典型电源需要600米W平均功耗，1%%的时间花在60mw的有源状态，其余时间花在一个非常低的功率6米W被动状态。
保持较小的内存占用是算法设计的主要要求。低成本、超低功耗设备中的内存不符合摩尔定律。一个迹象是，微控制器RAM的成本比PC SRAM高3个数量级，比PC DRAM高5个数量级。更重要的是，SRAM泄漏电流随着容量的增加而增加，决定了总体待机功耗和寿命。在32位处理器的配合下提供大型ram的设计会花费很大的精力来管理电源。这种节点的一个具体例子是太阳黑子，20.它通过将RAM内容写入闪存进入低功耗睡眠状态。在唤醒时从闪存恢复内存需要大量的电力和相当长的时间。在大多数传感器节点设计中采用的替代方案是只有几千字节的RAM。反过来，这又限制了网络(和其他)协议的存储复杂性，要求路由表、缓冲区和缓存保持较小。货币和能源成本的历史趋势表明，这些限制可能会持续下去。
无线传感器通常嵌入与其应用程序相关的物理环境中。通信连接因环境和电磁因素而异，另外一个限制是，没有人会像手机或笔记本电脑那样将设备引导到更好的设置。节点上的网络程度，即其通信邻域中的节点数量，不是由所需的网络组织决定的，而是由物理设备的放置决定的，这通常是由应用程序需求和物理约束决定的。可能有数千个节点非常接近，也可能只有几个。单个传输可能被多个设备接收，因此任何重传、响应或甚至一个简单的确认都可能导致巨大的争用、干扰和损失。冗余对于可靠性是必不可少的，但它也可能是丢失的主要原因。
最后一点是十年来无线传感器网络网络抽象发展的关键观察结果之一:传感器网络协议必须运行的各种网络拓扑和密度需要一个礼貌的、密度感知的本地重传方案。本文描述了涓流算法，它使用这种通信模式为协议和服务提供最终的一致性机制。在过去的十年中，无线传感器网络社区出现了一个关键的见解，即许多协议问题可以减少到维持最终的一致性。相应地，Trickle已经成为许多传感器网络协议和系统的实用、高效和健壮实现的核心网络原语。然而，在深入研究Trickle的细节之前，我们先回顾一下核心传感器网络协议是如何工作的以及与传统网络协议的不同之处，目的是探索类似Trickle的原语是如何满足它们的一些需求的。
2.网络协议
网络问题是嵌入式传感器网络设计的核心，因为无线电通信的收听、接收和发送支配着有源能量预算，并决定了系统的生命周期。在链路层网格或网络层路由中，多跳协议的标准能量成本度量是通信成本，定义为单个无线电传输和接收的数量。如果一种协议能够以较低的通信成本提供相同的性能(例如吞吐量、延迟、交付比)，那么它就比另一种协议更有效。协议专注于最小化传输，并确保传输的数据包成功到达。
几乎所有传感器网络系统的基本操作都依赖于两个多跳协议集合从网络中提取数据的协议传播通过一个或多个独立节点或出口路由器将数据推入网络的协议。许多高级协议建立在传播和收集的基础上。例如，重新编程服务，如洪水9使用发布来交付更改程序映像的命令。管理层级22和远程源代码级调试器25也使用传播。可靠的传输协议，如RCRT，18以及速率控制协议，如IFRC，19在收集树上操作。点对点路由方案，如S4，16在多个并行集合拓扑上建立覆盖。
虽然收集和传播具有相反的通信模式(all-to-one vs. to-all)和不同的可靠性(不可靠vs.可靠)，但两者最终都在节点之间保持一致的共享状态。本节的其余部分提供这两个协议类的高级概述。它详细介绍了它们引入的具有挑战性的问题，以及如何通过最终的一致性来解决其中一些问题。
2.1.推送数据:传播
传感器网络管理员面临的一个问题是动态地改变网络收集数据的方式，方法是改变采样的传感器、采样率，甚至通过将更改传播到网络中的每个节点来改变节点上运行的代码。我们首先讨论传播协议，因为它们是涓流的原始动力，也是它最简单的应用。
早期的系统使用包洪水来传播更改。泛洪协议重新广播它们收到的数据包。泛洪是非常简单的，通常只是一行或两个co首发有很多问题。首先，洪水是不可靠的。不可避免的是，有些节点没有收到数据包，因此用户通常会重复泛洪，直到每个节点都收到它。其次，在高密度网络中，许多节点最终会同时重广播包。这些信息相互碰撞，导致一种被称为“广播风暴”的网络崩溃。17
第二代传播和网络编程系统，如Xnp3.和TinyDB15使用与协议相结合的自适应泛洪来请求丢失的消息。自适应驱油利用对节点密度的估计来限制驱油速率。缺失消息协议允许节点从它们的邻居请求(希望是少数)缺失消息。不幸的是，让这样的协议很好地工作可能很棘手，特别是在网络密度和对象大小的范围内。
另一种看待传播协议的方式是，它们确保每个节点都有某种共享状态的最终一致版本，例如配置参数或命令的值。数据一致性是指所有节点都具有相同版本的状态，节点通过将邻居更新到新版本来解决不一致问题。归纳地说，这些定义使网络收敛于最新的版本。为了传播命令，系统将其作为新版本安装在一个节点上，并启动一致性协议。
将传播视为数据一致性问题意味着它不能提供完全的可靠性。最终的一致性只承诺向连接的节点交付最新的版本。断开连接的节点可能而且经常会错过更新。然而，在实践中，这种限制很少有问题。修改三次数据报告率的管理员然后添加一些新节点，并期望它们接收最新的报告率，而不是全部三个。类似地，在发送命令时，用户并不期望新节点接收注入到网络中的所有命令的全部历史记录。然而，断开连接几分钟的节点在重新连接时仍然会收到最近的命令。
在泛洪及其衍生产品失败的地方，传播协议取得了成功，因为它们将数据传递的问题转化为保持邻居之间的数据一致性。这使它们能够在没有先验拓扑知识或配置的任意拓扑中提供非常有用的可靠性形式。然而，一个有效的传播协议需要使节点快速更新，同时在每个节点都有最新版本时发送少量数据包:这是对底层一致性机制的相应要求。
2.2.提取数据:收集
由于典型的传感器网络目标是报告对远程环境的观察，因此数据收集是最早和研究最多的一类协议也就不足为奇了。收集协议有许多变体，类似于TCP有许多版本。抛开这些不同，所有常用的收集协议都使用最小成本路由树向收集点提供不可靠的数据报传递。按照第三层协议的一般目标，成本通常以预期传输(ETX)来衡量:2节点按到达收集点所需传输最少的路由发送数据包。
最早的采集协议是定向扩散，提出了基于特定数据节点请求动态建立采集树。10然而，早期使用低功耗无线技术的经验导致许多部署转向更简单、更不通用的方法，其中每个节点为所有转发的数据流量决定单一的下一跳，从而创建到固定收集点的路由树。网络通过建立路由成本梯度来构建这棵树。收集点的代价是0。一个节点计算每个候选下一跳的开销是该节点的开销加上到它的链接的开销。归纳地说，一个节点的开销是其路由中链路开销的总和。<一个href="#F2">图2说明一个示例拓扑。
集合的变化可以归结为它们如何量化和计算链路成本，它们维护的链路数量，它们如何在节点之间传播链路状态的变化，以及它们重新评估链路成本和交换机父节点的频率。早期的协议使用跳数8作为链路成本度量，类似于MANET协议，如AODV和DSDV;第二代协议，如MintRoute24和Srcr2估计使用定期广播在一个链接上的每次传送的传送量;第三代协议，如MultiHopLQI，将物理层信号质量添加到度量中;当前的一代收集协议，如收集树协议(CTP)，统一了这些方法，利用了来自多层的信息。6
大多数集合层操作为任意播放协议。一个网络可以有多个数据收集点，收集会自动路由到最近的一个。由于只有一个目的地，任何集合点，所需的路由状态可以独立于网络密度和规模。大多数协议使用一个小的、固定大小的候选下一跳表。他们还试图在路线稳定性和流失率之间取得平衡，通过不频繁地切换亲本，并使用阻尼机制限制变化的速度，来发现新的、可能更好的亲本。
随着收集协议的改进和更好地选择路线，减少控制流量已成为效率日益重要的组成部分。虽然节点可以在数据包上附加一些控制信息，但它们需要向本地邻居发送链路层广播，以宣传它们的存在和路由成本。选择发送这些广告的频率带来了一种困难的设计张力。较低的速率会带来较低的开销，但会限制树适应故障或链接更改的速度，从而降低数据通信的效率。快的速率会带来更高的开销，但会导致敏捷树能够更准确地找到要使用的最佳路径。
当网络只收集响应事件的数据时，这种压力尤其具有挑战性，因此可能会经历高数据率和低数据率的时期。在低流量时期拥有较高的控制率是非常低效的，而在高流量时期拥有较低的控制率则使树无法对变化作出足够快速的反应。当开始突发传输时，节点可能会发现链路成本发生了很大的变化，因此需要改变路由，并因此发布路由成本。成本的变化需要快速传播，否则拓扑很容易形成路由循环。例如，如果一个链路的开销显著增加，那么一个节点可能会选择它的一个子节点作为下一跳。由于协议状态必须独立于拓扑，节点不能通过简单地枚举其子节点来避免这一点(在密集网络中，将树的程度限制为常数将导致低效的、迂回的拓扑)。
当前协议，如CTP21和ArchRock的路由层，1通过减少作为数据一致性问题的路由梯度来解决这种紧张关系。只要孩子的花费比父母高，这个梯度是一致的。当成本变化到足以违反此约束时，就会出现不一致。只要路由开销稳定，节点就可以假定梯度是一致的，从而避免交换不必要的数据包。
2.3.一个通用的机制
上面的示例描述了两种截然不同的协议如何通过减少维护数据一致性的问题来解决设计紧张问题。这两个例子都对数据一致性机制提出了相同的要求:它需要快速解决不一致，在数据一致时发送很少的数据包，并且需要很少的状态。下一节将讨论的涓流算法满足这三个要求。
3.细流
涓流算法建立了一个密度感知的本地广播，具有一个底层一致性模型，该模型指导节点何时通信。当一个节点的数据与它的邻居不一致时，它会快速通信以解决不一致的问题。当节点同意时，它们会指数级地降低通信速率，这样在稳定状态下，节点每小时最多发送几个包。该算法不会让整个网络充斥着数据包，而是控制发送速率，使每个节点都能听到少量数据包，刚好能保持一致。此外，通过仅依赖本地广播，涓流处理网络重新填充，对网络瞬变、丢失和断开具有健壮性，并且需要非常少的状态(实现使用411字节)。
尽管涓流最初是为重新编程协议(其中数据是正在更新的程序的代码)而设计的，但经验表明，它是一种强大的机制，可以应用于广泛的协议设计问题。例如，路由协议可以使用涓流来确保给定邻居中的节点具有一致的、无环路的路由。当拓扑一致时，节点偶尔会八卦以检查它们是否仍然一致，当拓扑发生变化时，它们会更频繁地八卦，直到它们再次达到一致。
为了清楚地解释Trickle设计背后的原因，本节中所有的实验结果都来自模拟，在某些情况下是非常高级的抽象模拟器。在实践中，涓流的简单性意味着它在更具挑战性和难度的现实世界中表现出色。涓滴最初的论文，13以及洪水9和浸14报告真实网络的实验结果。
3.1.算法
涓流的基本机制是随机的、抑制性的广播。涓涓细流有一定的时间间隔t还有一个冗余常数k。在间隔开始时，节点设置一个计时器t在…范围内
．当该定时器触发时，节点决定是否广播一个包含元数据的包，以检测不一致。这个决定基于节点在t之前的时间间隔内听到的数据包。涓流维持一个计数器c，在每个时间间隔开始时将其初始化为0。每当一个节点听到与它自己的状态一致的涓流广播时，它就会增加c。当它到达时间t,涓滴广播如果c<k．随机化t当节点轮流成为第一个决定是否传输的节点时，将传输负载分散到单跳邻居上。<一个href="#F3">图3总结了细流的参数。
3.2.可伸缩性
传输只有c<k使涓滴密度意识到，因为它限制在网络的一个区域的传输速率的因素k．在实践中，一个节点在一段时间内观察到的传输负载为O(k. log (d)),在那里d是网络密度。该对数的基数取决于丢包率PLR:它是
．
这种对数行为表示单个节点错过多个传输的概率。例如，当丢失率为10%时，节点将有10%的机会错过单个数据包。如果一个节点错过一个数据包，它将进行传输，导致两次传输。相应地，一个节点有1%的机会错过来自其他节点的两个数据包，从而导致三次传输。在100%损失率的极端情况下，每个节点都是独立的:传输是线性扩展的。
3.3.同步
如图所示的比例<一个href="#F4">图4假设所有节点都是同步的，这样它们清醒和收听无线电的间隔就完全一致了。不可避免地，这种时间同步增加了通信，因此增加了能量和开销。虽然一些网络可以为涓流提供时间同步，但其他网络不能。因此，Trickle被设计成在同步存在和不同步的情况下都可以工作。
细流选择t在…范围内
而不是(o,t)，因为后者会导致非同步网络中的传输负载增加
．出现这种不希望出现的缩放是由于听短的问题,在那里，一些微粒在它们的间隔开始后不久就开始闲谈。在其他人有机会发言之前，他们只听了很短的时间。如果所有的时间间隔都是同步的，这就不是问题，因为第一个流言会让其他人安静下来。但是，如果节点没有同步，一个节点可能在另一个节点的广播之后开始它的间隔，导致错过消息和增加传输负载。
不像损失，哪里额外O(日志(d))的传输使遗漏了几个包的最坏情况节点保持最新，由于短侦听问题而产生的额外传输完全是浪费。选择t在…范围内
消除了这个问题:它定义了一个“只听”周期的前半段间隔。监听期通过执行一个简单的约束来提高可伸缩性。如果发送消息保证了一段时间的静默期T这与密度无关，那么发送速率在上面有界(与密度无关)。当微尘传输时，它至少在监听期间抑制所有其他节点。<一个href="#F5">图5展示了如何收听一段时间
将在无损单跳网络中发送的总数限定为2k。在有损耗的情况下，每个间隔的传输规模为0(2k.log(d))，将可伸缩性返回到0(log(d))目标。
3.4.控制t
一个大的t(闲聊时间)通信开销低，但传播速度慢。相反,一个小t增加了更高的通信开销，但传播数据更快。这两个目标，快速传播和低开销，从根本上是不一致的:前者要求频繁通信，而后者要求不频繁通信。
通过动态扩展t涓滴可以以非常小的成本迅速使数据一致。t有一个下界，tl，和一个上界th．当t过期，没有一个节点收到新的更新，t加倍，最多为th．当节点检测到数据不一致时(例如，传播中更新了版本号，收集中违反了梯度约束)，它会重置t是tl．
基本上，当没有什么新东西可说时，尘埃就很少八卦:t被设置为th．然而，一旦尘埃听到新的东西，它就会更频繁地传播，所以那些没有听到新数据的人很快就能接收到。闲聊声就会渐渐平息，就像t从生长tl来th．
通过调整t通过这种方式，涓流可以两全其美:在网络一致的情况下，快速一致性和低开销。每个不一致的成本(减少)t)大约是
额外的发送。对于一个t1是1s和ath在1小时中，这是11个包的成本，从而使检测不一致所需的时间减少3000倍(或者从另一个角度来看，维护开销减少3000倍)。简单的涓流策略，“每隔一段时间发送一次，除非您听到一些其他的传输”，可以用来以低成本维护网络的一致性，以及在出现不一致时快速通知节点。
3.5.案例研究:伴侣
Maté是一个用于无线传感器网络的轻量级字节码解释器。11程序是经过优化的字节码的微小序列。Maté运行时使用Trickle在网络中安装新程序，方法是使所有节点与脚本的最新版本一致。
Maté使用涓流定期广播版本摘要。在所有的实验中，代码例程都适合在一个包中(30字节)。运行时用涓流传播服务注册例程，然后该服务维护所有必要的计时器和广播，在安装新代码时通知运行时。Maté使用非常简单的一致性解决机制。在听到不一致后，它将广播丢失的例程三次:1,3,7秒。
图7显示了Maté在重编程事件期间行为的模拟结果。这些结果来自TOSSIM模拟器，12它模拟了整个传感器网络应用，并在位级模拟无线连接。在这些实验中,tl是1s和th是1分钟。
每个模拟都将400个节点定期放置在一个正方形网格中，节点间距分别为5、10、15和20英尺。通过改变网络密度，我们能够检查Trickle的传播速率如何在不同的损失率和物理密度下扩展。密度范围th节点之间的间距从5英尺到20英尺(网络为95 × 95到380 × 380)。在这些拓扑中跨越网络需要6到40跳。一个完成传播的时间在最密集的网络中从16秒到最稀疏的网络中约70秒不等，分别代表每跳2.7秒和1.8秒的延迟。最小的每跳涓流延迟为
一致性机制在发现不一致后1秒广播一个例程，所以最好的延迟是每跳1.5秒。尽管节点之间几乎完全缺乏协调，但涓流仍然能够使它们高效合作。
一个非常大的th能不能增加发现不一致的时间大约是多少
．然而，只有当两个稳定的子网(t＝th)用不同的代码重新连接。如果引入了新的代码，它会立即触发节点重置t来tl使它们迅速达到一致的状态。
涓流的Maté实现只需要很少的系统资源。它需要大约70个字节的RAM;其中一半是用于传输的消息缓冲区，四分之一是指向代码例程的指针。涓流本身只需要11个字节的计数器;其余的RAM用于内部协调(例如，挂起和初始化标志)。可执行代码是1.8 K(90行代码)。其他实现也有类似的成本。该算法只需要很少的CPU周期，并且可以在非常低的占空比下工作。
3.6.使用和改进
涓流不仅被Maté使用;它和它的衍生物在今天几乎每一个传播协议中都被使用。用于安装新的传感器节点固件的洪水二进制传播协议使用涓流来检测节点是否有不同的固件版本9（tl= 500 ms， = 1.1 h). MNP二进制传播协议(tl= 16 s， = 512 s)调整“涓滴效应”，通过阻止低度节点抑制高度节点，使拥有更多邻居的节点更有可能发送更新。23传感器网络管理系统的滴漏命令层采用滴漏(tl= 100毫秒,th= 32 s)安装命令。22Tenet编程体系结构使用了Trickle (tl= 100毫秒,th= 32秒)安装小型动态代码任务。7
在过去的几年里，随着收集协议的效率提高，他们也开始使用Trickle。CTP, TinyOS操作系统发行版中的标准收集层，21使用涓流计时器(tl= 64毫秒,th= 1 h)为其路由流量。Arch Rock软件中的6LoWPAN IPv6路由层使用Trickle来保持IPv6路由表和ICMP邻居列表一致。1随着协议的不断改进，Trickle的有效性和简洁性将使它被用于更多的协议和系统中。
本文所描述的涓流的一个限制是它的维护成本会增长O (n)数据项的数量，作为节点必须交换版本号。这种增长可能是涓流使用增加的阻碍因素。DIP协议最近的工作通过使用散列树和随机搜索的组合来解决这个问题，使维护成本保持O(1)，同时强制执行aO (log (n))发现成本。14
4.讨论
无线传感器网络与其他ad hoc网络一样，不知道互连拓扑的先验性，通常不是静态的。节点必须通过尝试通信，然后观察通信成功的地方来发现它。此外，通信介质应该是有损耗的。冗余在这样的网络中既是朋友也是敌人，但涓流强化了积极的方面，压制了消极的方面。
涓流借鉴了两个主要的研究领域。第一个领域是用于无线和多播网络的控制、密度感知的泛洪算法。5，17第二种是在分布式系统中保持数据一致性的流行和八卦算法。4尽管这两种技术——广播技术和流行病技术——都有假设，使得它们的纯形式与传感器网络的最终一致性不合适，但它们都是Trickle借鉴的强大技术。涓流抑制机制的灵感来自于可伸缩可靠组播(SRM)中使用的请求/修复算法。5涓滴像受控洪水一样适应本地网络密度，但以类似于流行病算法的方式持续保持一致性。涓流还利用了无线信道的广播特性，使用类似于srm的重复抑制来保存宝贵的传输能量，并扩展到密集的网络。
指数计时器是一种常见的协议机制。例如，以太网使用指数后退来防止冲突。尽管涓流也有一个指数计时器，但它的用途是相反的。以太网默认为最小的时间窗口，只在发生冲突的情况下增加时间窗口，而Trickle默认为最大的时间窗口，只在发生不一致的情况下减少时间窗口。这种逆转表明了超低功耗网络的不同优先级:降低能源消耗，而不是提高性能，通常是更重要的目标。
在传播的情况下，涓流计时器将包响应分散到各个节点，同时允许节点估计它们的程度并设置它们的通信间隔。涓滴效应不仅通过减少碰撞来避免碰撞，还通过抑制不必要的重传输，从而实现了节能、密度感知的传播。
在连接动态变化的多跳网络中，试图对逻辑组的抽象强制抑制可能会变得困难，而涓流抑制的是隐式组:听到广播的附近节点。相应地，涓流不会增加发现和维护逻辑组的开销，并且毫不费力地处理瞬态和有损的无线链接。依靠这种隐式命名，涓流算法保持非常简单:实现可以容纳不到2 K的代码，只需要11个字节的状态。
路由协议的作用是发现其他路由器、交换路由信息、发布探测、建立和拆除链路。所有这些操作都可以由涓流控制。例如，在我们探索无线传感器网络如何在6LoWPAN中采用更多IPv6栈的经验中，Trickle提供了一种支持已建立的ICMP-v6机制的方法，用于无线网络中的邻居发现、重复地址检测、路由器发现和DHCP。其中每一个都涉及到广告和回应。涓滴机制是一个天然的选择:在密度大的地方避免损失，允许及时通知变化，并在配置稳定时适应低能耗。通过采用最终一致性模型，节点可以在本地达到一致状态，而不需要管理员采取任何操作。
涓流最初是为了将新程序分布到无线传感器网络中而开发的:原始论文的标题是“涓流:无线传感器网络中代码传播和维护的自调节算法”。13经验表明，它有更广泛的用途。基于涓滴的通信，而不是泛洪，已经成为发现连接性、数据传播和路由维护的基本多跳网络操作的中心范式。
展望未来，我们期望这类技术的使用在整个无线网络堆栈的上层变得越来越普遍。这样的进步不仅会使现有的协议更加高效，还会使传感器网络能够支持原先认为不可行的层。将协议视为建立和调整分布式数据一致视图的连续过程，是构建健壮的分布式系统的一种有吸引力的方法。
致谢
该研究部分得到了美国国防部高级研究项目局(拨款F33615-01-C-1895和N6601-99-2-8913)、美国国家科学基金会(拨款编号0122599、iss -033017、0615308和0627126)、加州MICRO项目、英特尔公司、DoCoMo资本、基金会资本和斯坦福特曼奖学金的支持。研究基础设施由国家科学基金会提供(资助号:9802069)。我们还要感谢Sylvia Ratnasamy对这项研究早期阶段的宝贵见解，以及Jonathan Hui关于将Trickle应用于新问题的想法。
参考文献
1.拱形岩石公司。无线传感器网络的IPv6网络栈。http://www.archrock.com。
2.Couto, d.d.， Aguayo, d.d.， Bicket, J.和Morris, R.多跳无线路由的高吞吐量路径mMetric。第九届移动计算与网络国际年会论文集，2003.
3.弩,Inc。Mote在网络编程用户参考。http://webs.cs.berkeley.edu/tos/tinyos - 1. x/doc/xnp.pdf。
4.Demers, A.， Greene, D.， Hauser, C.， Irish, W.和Larson, J.用于复制数据库维护的流行算法。在第六届ACM分布式计算原理年会论文集(PODC), 1987年。
5.弗洛伊德，雅各布森，维，麦卡恩，刘，c.g.。，一个nd Zhang, L. A reliable multicast framework for lightweight sessions and application level framing.计算机通信应用、技术、体系结构和协议会议论文集，1995.
6.Fonseca, R.， Gnawali, O.， Jamieson, K.和Levis, P.四比特无线链路估计。第六届网络热点专题研讨会论文集，2007.
7.纳瓦里，奥，格林斯坦，B，张，k - y。，Joki, A., Paek, J., Vieira, M., Estrin, D., Govindan, R., and Kohler, E. The TENET architecture for tiered sensor networks. Proceedings of the Fourth International Conference on Embedded Networked Sensor Systems (Sensys), 2006.
8.Hill, J.， Szewczyk, R.， Woo, A.， Hollar, S.， Culler, D.E，和Pister, K.S.J.网络传感器的系统架构方向。第九届国际编程语言体系结构支持会议论文集操作系统(ASPLOS),2000.
9.Hui, J.W.和Culler, D.用于大规模网络规划的数据传播协议的动态行为。第二届嵌入式网络传感器系统国际会议论文集，2004.
10.Intanagonwiwat, C.， Govindan, R.和Estrin, D.定向扩散:传感器网络的可扩展和健壮的通信范式。第六届移动计算与网络国际年会论文集，2000.
11.李维斯，P，盖伊，D，和卡勒，D主动传感器网络。第二届USENIX/ACM网络系统设计与实现(NSDI)研讨会论文集，2005.
12.Levis, P.， Lee, N.， Welsh, M.和Culler, D. TOSSIM:整个TinyOS应用程序的精确和可扩展模拟。第一届ACM嵌入式网络传感器系统(SenSys)会议论文集，2003.
13.Levis, P.， Patel, N.， Culler, D.和Shenker, S.涓流:用于无线传感器网络中代码维护和传播的自调节算法。第一届USENIX/ACM网络系统设计与实现(NSDI)研讨会论文集，2004.
14.林凯，李维斯，P. DIP的数据发现和传播。第七届传感器网络信息处理国际研讨会论文集，2008.
15.Madden, S.， Franklin, m.j.， Hellerstein, j.m.和Hong, W. Tiny DB:用于传感器网络的获取查询处理系统。数据库系统学报(英文版)，2005.
16.毛宇宇，王芳，邱丽娟，林淑珍，史密斯J. S4:大型无线传感器网络的小状态和小延伸路由协议。第四届USENIX网络系统设计与实现(NSDI)研讨会论文集2007.
17.倪,S.-Y。，Tseng, Y.-C., Chen, Y.-S., and Sheu, J.-P. The broadcast storm problem in a mobile ad hoc network.第五届移动计算与网络国际年会论文集，1999.
18.RCRT:无线传感器网络的速率控制可靠传输。第五届嵌入式网络传感器系统国际会议论文集，2007.
19.Rangwala, S.， Gummadi, R.， Govindan, R.和Psounis, K.无线传感器网络中的干扰感知公平速率控制。学报计算机通信应用、技术、体系结构和协议会议(SIGCOMM)2006.
20.太阳微系统公司实验室。Sun SPOT项目:小型可编程对象技术。http://www.sunspotworld.com/。
21.TinyOS网络协议工作组。step123:集合树协议。http://www.tinyos.net//tinyos - 2. x/doc/txt/tep123.txt, 2007。
22.Tolle G.和Culler D.无线传感器网络应用协同管理系统设计。第二届欧洲无线传感器网络研讨会论文集，2005.
23.MNP:传感器网络的多跳网络重编程服务。第二届嵌入式网络传感器系统国际会议论文集，2004.
24.Woo, A.， Tong, T.和Culler, D.驯服传感器网络中多跳路由的潜在挑战。第一届ACM嵌入式网络传感器系统(SenSys)会议论文集，2003.
25.Yang, J.， Soffa, m.l.， Selavo, L.和Whitehouse, K. Clairvoyant:一种用于无线传感器网络的全面源级调试器。第五届嵌入式网络传感器系统国际会议论文集。2007.
脚注
a.这些跳数值来自计算通过网络损耗拓扑的最小开销路径，其中每条链路的权值为1/1损失，即成功遍历该链路的预期传输数。
DOI: http://doi.acm.org/10.1145/1364782.1364804
数据
图1。EPic, KMote和Telos motes。每个都有一个8MHz的微控制器，10kB的RAM, 48kB的程序闪存和250kbps的收音机。
图2。示例收集树，显示每个链接和节点的成本。节点的开销是它的下一跳开销加上链路的开销。
图4。涓滴每间隔的传输随密度成对数刻度。对数的基数是丢包率(百分比)的函数。
图5。没有一个只听的周期，当间隔不同步时，涓流的传输规模是密度的平方根。只有一段时间可以听t/2时，每间隔的传输渐近于2k。黑线显示当间隔同步时，涓流是如何扩展的。这些结果来自无损网络。
图7。在20 × 20 ToSSIM网格中达到一致性的时间(秒)。每个图例中的跳数值是在考虑损耗的情况下，从一个角到另一个角所需的预期传输数。
©2008 acm 0001-0782/08/0700 $5.00
允许为个人或课堂使用本作品的全部或部分制作数字或硬拷贝，但不得为盈利或商业利益而复制或分发，且副本在首页上附有本通知和完整的引用。以其他方式复制、重新发布、在服务器上发布或重新分发到列表，需要事先获得特定的许可和/或付费。
数字图书馆是由计算机协会出版的。版权所有©2008 ACM, Inc.