TTDD：大规模无线传感器网络中的两层数据分发

发表在ACM Journal of Mobile Networks and Applications（MONET），ACM MOBICOM特刊，2003年1TTDD：大规模无线传感器网络中的两层数据分发罗海云，叶凡，程智，卢松武，张丽霞加州大学洛杉矶分校计算机科学系洛杉矶，CA 900095-1596{hluo，yefan，chengje，slu，lixia} @ cs.ucla.edu摘要Sink移动性给大型传感器网络中的数据传播带来了新的挑战。它建议有关每个移动sink的位置的信息被不断propa-门在整个传感器领域，以保持所有传感器的转发未来的数据报告的方向通知。不幸的是，来自多个接收器的频繁位置更新在本文中，我们描述了TTDD，一个两层的数据传播的方法，提供可扩展的和有效的数据传递到多个，移动汇。TTDD中的每个数据源主动构建一个网格结构，通过仅在本地小区内泛洪查询，使TTDD我们通过分析和广泛的模拟来评估TTDD我们的研究结果表明，TTDD处理汇移动有效的性能可比的站- ary汇。1介绍超大规模集成电路、微处理器和无线通信技术的最新进展使得大规模传感器网络的设计和部署成为可能，在大规模传感器网络中，数千甚至数万个小型传感器分布在广阔的区域内，以获得细粒度、高精度的传感数据[10，11，15]。 这些传感器通常由电池供电，并通过无线信道相互通信。本文研究了大规模传感器网络中从潜在的多个源到潜在的多个移动接收器的可扩展和有效的数据分发问题。在这项工作中，源是指生成感测数据以报告有关刺激的传感器节点，该刺激是目标或感兴趣的事件。接收器是收集这些数据这项工作得到了DARPA SensIT计划的部分支持，合同号为DABT63 -99-1-0010。Lu还获得了NSF CA-REER奖（ANI-0093484）的支持。图1：传感器网络示例。士兵们使用传感器网络来探测坦克的位置。来自传感器网络的报告。刺激和汇的数量都可能随着时间的推移而变化。例如，在图1中，一组士兵从部署在战场上的传感器网络收集坦克移动信息。坦克周围的传感器检测到它并相互协作以汇总数据，其中一个生成数据报告[20]。士兵们收集这些数据报告。在本文中，我们考虑一个网络的固定传感器节点，而汇可能会改变他们的位置动态。在上面的示例中，士兵可以四处移动，但必须能够连续接收数据报告Sink移动性给大规模传感器网络的数据分发带来了新的挑战虽然近年来已经提出了几种传感器网络的数据传播协 议 ， 如 定 向 扩 散 [11] ， 声 明 式 路 由 协 议 [5] 和GRAB[20]，但它们都建议每个移动sink需要在整个传感器场中连续传播其位置信息，以便所有传感器节点都被告知发送未来数据报告的方向。然而，来自多个接收器的频繁位置更新可能导致无线传输中的冲突增加和传感器有限电池电源的快速功耗现有的方法中没有一种提供了针对该问题的可扩展且有效的解决方案。在本文中，我们描述了TTDD，一个两层的数据分发方法，以解决多个，移动汇问题，源A体3沉2水池1源B2lem. TTDD使用网格结构，使得只有位于网格点的传感器需要获取转发信息，而不是将查询消息从每个sink传播到所有传感器以更新在检测到刺激时，而不是被动地等待来自接收器的数据查询-大多数现有工作所采用的方法-数据源主动地在整个传感器场中构建网格结构，并在最接近网格点的传感器处设置转发信息（此后称为传播节点）。有了这种网格结构，来自接收器的查询将遍历两层到达源。较低的层位于接收器当前位置的本地网格正方形内接收器在单元格内泛洪其查询。当所请求的数据的最近的传播节点接收到查询时，它将查询转发到其朝向源的上游传播节点，该上游传播节点又进一步转发查询，直到它到达源或已经从源接收数据的传播节点（例如，在来自其他宿的请求时）。此查询转发过程提供到接收器的路径信息，以使来自源的数据能够遍历与查询相同的两个层，但顺序相反。TTDD的设计利用了传感器节点是固定的和位置感知的这一事实。由于传感器被假设知道它们的位置以便标记感测数据[1，9，18]，并且由于传感器通过每个数据源的网格结构，来自多个移动接收器的查询仅被限制在它们的本地小区内，从而避免了由多个接收器引起的全局洪泛引起的过度能量消耗和网络过载。 当接收器从其先前位置移动超过单元大小时，它执行将到达新的传播节点的数据查询的另一个本地洪泛。在向源的过程中，此查询将在已经从源接收数据的传播节点处停止。然后，该传播节点将数据向下游转发到接收器。这样，即使接收器连续移动，高层数据转发也会逐渐改变，并且接收器可以在不中断的情况下接收数据。此外，由于只有网格点上的那些传感器（用作传播节点）参与数据传播，因此其他传感器免于维持状态。因此，TTDD可以扩展到大量的源和汇。本文的其余部分组织如下。第二部分介绍了系统的主要设计，包括网格的构建、两层查询和数据转发以及网格的维护.第三节分析了TTDD的通信开销和状态复杂度，并与其他面向sink的数据分发方案进行了比较仿真结果在第4节中提供，以评估我们的解决方案的有效性和设计参数的影响。我们讨论了几个重要的-并与第六节的相关工作进行比较。第七节是论文的结论。2双层数据分发本节介绍TTDD的基本设计，它可与以下网络设置配合使用：大量同质的传感器节点通过短距离无线电进行通信远程数据传输是通过跨多跳转发数据来实现的。每个传感器都知道自己的位置（例如，通过接收GPS信号或通过[1]等技术）。然而，移动接收器可能知道或可能不知道它们自己的位置。一旦刺激出现，其周围的传感器集体处理信号，其中一个成为生成数据报告的源[20]。Sink（用户）查询网络以收集传感数据。在传感器场中可以有多个接收器四处移动，并且接收器的数量可以随时间而变化。上述假设与正在构建的真实传感器的模型一致，例如UCLA ARMNG 节 点 [15] ， SCADDS PC/104 [4] 和Berkeley Motes [10]。此外，TTDD设计假设传感器节点知道它们的任务（例如，以要观察的每种潜在类型的刺激的签名的形式）。每个任务代表传感器网络的一个感知任务。在图1的坦克检测的示例中，传感器网络的任务是收集并返回坦克的当前位置在传感器网络任务可能偶尔发生变化的情况下，新的任务可以通过现场洪水到达所有传感器节点。在本文中，我们不讨论如何管理传感器网络的任务。然而，我们假设一个传感器网络的任务变化很少，因此任务传播的开销相比，传感器数据传输是可以忽略不计的一旦数据源生成数据，它就开始通过构建网格结构为数据传播做准备。源以其自身的位置作为网格的一个交叉点开始，并向其四个相邻交叉点中的每一个发送数据通告消息。每个数据通告消息最终在最接近消息中指定的交叉点的传感器节点上停止。节点存储源信息，并进一步将消息转发到其相邻的交叉点，除了它从其接收消息的那个交叉点之外。数据通告消息的这种递归传播通知最接近交叉位置的那些传感器成为给定源的传播节点····3×BS图2：一个源B和一个汇S一旦为指定的源构建了网格，接收器就可以在本地单元内泛洪其查询以接收数据。查询将由网格上最近的传播节点接收，然后通过其他传播节点向上游向源传播查询请求的数据将以相反的方向向下流到接收器。上述看似简单的TTDD操作提出了几个研究挑战。例如，假设传感器的位置是随机的，不一定在网格的交叉点上，那么网格点附近的传感器如何决定哪个传感器应该作为传播节点？一旦数据流开始流动，如何使它跟随接收器的移动以确保连续的传输？鉴于单个传感器可能会出现意外故障，一旦构建完成，如何本节的其余部分将详细讨论这些问题。我们从2.1节中的网格构造开始，并在2.2节中介绍两层查询和数据转发。电网维护在第2.3节中描述。2.1电网建设为了简化演示，我们考虑一个二维传感器场。源将场划分为单元格网格。每个单元格都是一个α α正方形。源本身位于网格的一个交叉点处。它将数据通告传播到网格上的所有其他交叉点（称为传播点）。对于位置Ls=（x，y）处的特定源，传播点位于Lp=（xi，yj）处，使得：{xi=x+i·α，yj=y+j·α;i，j=±0，±1，±2，···}源在给定其位置（x，y）和单元大小α的情况下计算其四个相邻传播点的位置。对于四个传播点Lp中的每一个，源使用简单的贪婪地理转发向Lp发送数据通知消息，即，它将消息转发到具有到Lp的最小距离的邻居节点。类似地，邻居节点继续转发数据通告消息，直到消息在比它所有的邻居都更接近Lp。如果该节点在数据通告消息在到指定传播点的距离大于α/2的节点处停止的情况下，节点简单地丢弃消息。传播节点存储用于网格结构的几条信息，包括数据通告消息、它所服务的传播点Lp和上游传播节点然后，它进一步将消息传播到网格上的相邻传播点，除了它从其接收通知的上游传播点数据通告消息递归地传播通过整个传感器场，使得网格上的每个传播点由传播节点服务。来自不同相邻传播点的广播通知消息由通知中携带的序列号标识，并且简单地丢弃。图2显示了源B的网格及其虚拟网格。网格的每个交叉点周围的黑色节点是传播节点。2.1.1网格结构由于上述网格构建过程不需要任何关于汇的潜在位置的先验知识，因此它构建了一个均匀的网格，其中所有传播点都以距离α规则地间隔开，以便尽可能均匀地分发数据公告。在任何节点上都不需要全局拓扑的知识;每个节点仅基于其局部邻域的信息来行动。在TTDD中，传播点在选择传播节点时充当参考位置。选择尽可能靠近传播点的传播节点，使得传播节点形成几乎统一的网格基础设施。然而，传播节点不需要在全局上最接近传播点。严格地说，TTDD确保传播节点在局部上最接近传播点，但由于拓扑结构的不规则性，不一定在全局上最接近传播点。这不会影响TTDD的正确操作。原因是每个传播节点在其另外的数据通告消息中包括其自己的位置（而不是传播点的位置）。这样，下游传播节点将仍然能够将将来的查询转发到该传播节点，即使该传播节点不是全局最接近理想网格中的传播点 我们将在2.2.1节中进一步讨论。通过设置节点成为传播节点的距离阈值α/2，使网格构建停止在网络边界。例如，在图3中，传感器节点B接收到去往P的数据通告，该数据通告在4BP图3：边界上的终止传感器领域。由于节点不知道全局传感器场拓扑，因此它们无法判断位置是否在网络之外。与α/2的比较为节点提供了一个简单的规则来决定是否应该终止传播当一个传播点落入一个没有任何传感器节点的空白区域时，数据通告传播可能会停止在空白区域的边界但是传播可以沿着网格的其他路径继续，并且绕过空白区域，因为每个传播节点将数据通知转发到所有其他三个传播点。只要网格没有分区，数据通知就可以通过其他路径绕过空白。我们选择在每个源的基础上构建网格，以便不同的源招募不同的传播节点集。这种设计选择增强了可伸缩性，并提供了负载平衡和更好的鲁棒性。当有许多源时，只要它们的网格不重叠，传播节点仅具有关于一个或几个源的状态。这使得TTDD可以扩展到大量的源。我们将在3.3节中分析状态复杂度。此外，单源网格有效地在不同传感器之间分配数据分发负载，以避免瓶颈.这是由每个传感器是能量受限的并且其无线电通常具有有限带宽的事实所每个源的网格结构也增强了系统的鲁棒性，在节点故障的网格单元尺寸α是一个关键参数。正如我们在下一节中看到的，设置单元大小的一般指导原则是将sink移动性的影响局限在单个单元中，以便更高层的网格转发保持稳定。α的选择影响能量效率和状态复杂度。 将在第3节中进一步分析，并在第4节中进行评价。2.2双层查询和数据转发2.2.1查询转发我们的两层查询和数据转发是基于虚拟网格基础设施，以确保可扩展性和效率。当接收器需要数据时，它会在本地区域内泛洪查询，小区大小大到可以发现附近的传播节点。接收器在查询中指定了最大距离，因此洪泛会在距离接收器最大距离的节点处停止。一旦查询到达本地传播节点（其被称为接收器的立即传播节点），它就在网格上被转发到上游传播节点，该立即传播节点从该上游传播节点接收数据通知。上游节点又将查询进一步向上游转发到源节点，直到查询最终到达源节点。在上述过程中，每个传播节点存储它从其接收查询的下游传播节点的位置。此状态用于稍后将数据定向回接收器（有关说明，请参见图4）。有了网格基础设施，查询洪泛可以被限制在一个单元大小的区域内。它节省了大量的能源和带宽的计算，泛洪查询在整个传感器领域。此外，在两层转发期间采用两级查询聚合1以进一步减少开销。在单元内，从不同接收器接收对相同数据的查询的立即传播节点聚集这些查询。它只以上游更新的形式向其上游传播节点发送一个副本。类似地，如果网格上的传播节点从不同的下游邻居接收到多个上游更新，则它仅进一步转发其中的一个。例如，在图4中，传播节点G从信宿S1所在的小区和信宿S2所在的小区接收查询，并且G仅向源发送一个上行更新消息。当上游更新消息遍历网格时，它在分发节点中暂停软状态以将数据流引导回宿。除非更新，否则这些状态仅在一定时间内有效。传播节点周期性地向上游发送这样的消息，以便连续地接收数据;当它不再需要数据时，例如当接收器停止发送查询或移出本地区域时，它停止发送这样的更新消息。上游传播节点在软状态到期之后自动停止转发数据。在我们当前的设计中，这些软状态定时器的值被选择为比数据消息之间的间隔高一个数量级。此设置平衡了生成定期上游更新消息的开销和将数据发送到不再需要它们的地方的开销。两级聚合随接收器的数量而扩展。查询转发路径上的传播节点仅维护关于三个相邻传播节点的状态1为了简单起见，我们在这里不考虑语义聚合[11]，它可以用于进一步提高不同数据分辨率和类型的聚合增益5√S2低层查询泛洪高层查询网格转发轨迹数据转发更高层的数据网格转发低层数据轨迹转发一GS1PA图4：源A和接收器S1、S2之间的双层查询和数据转发。汇点S1开始于将其查询用其主代理PA的位置洪泛到其直接传播节点D1。DS记录PA的位置并将查询转发到其上游分发节点，直到查询到达A.数据沿着查询遍历的路径返回到D。Ds将数据转发到PA，并最终转发到宿S1。类似的过程适用于汇点S2，除了其查询在网格上的传播节点G处停止。节点需要数据。一个直接的传播节点保持另外的状态，位于约一个单一的细胞大小的本地区域内的汇。不参与查询或数据转发的传感器不保持关于接收器或源的任何状态。我们在3.3节中详细分析了状态复杂度。2.2.2数据转发一旦源从其相邻传播节点之一接收到查询（以上游更新的形式），它就向该传播节点发送数据，该传播节点随后将数据转发到它接收查询的地方，如此等等，直到数据到达每个宿的直接传播节点。如果传播节点聚合了来自不同下游传播节点的查询，则它向每个下游传播节点发送数据副本。 例如，在图4中，传播节点G将向S1和S2发送数据。一旦数据到达接收器通过上述两层转发，查询和数据可能采用全局次优路径，因此与沿着最短路径转发相比引入了额外的成本。例如，在图4中，如果接收器S1和S2各自将其查询泛洪到整个传感器场中，则它们可以遵循到源的直线路径然而，通过两层转发，消息在snk和源之间行进的路径至多是直线的长度的2我们认为，次优性是值得的可扩展性的增益详细分析见第图5：经由主代理PA和直接代理IA从直接传播节点Ds到移动信宿S1的轨迹转发。直接代理IA与S1相距一跳。它直接将数据重新发送到接收器S1.当S1移出其当前IA的一跳传输范围时，它从其相邻节点中挑选新的IA。S1然后向其PA和旧IA发送更新以中继数据。只要S1与PA保持一定距离，PA就保持不变.3.2.2.3轨迹转发采用轨迹转发将数据从其直接传播节点中继到移动信宿。在轨迹转发中，每个sink与两个传感器节点相关联：一个主代理和一个直接代理。信宿选择相邻传感器作为其主代理，并在其查询中包括主代理的位置。其直接分发节点将数据发送到主代理，主代理将数据转发到接收器。最初，主代理和直接代理是相同的传感器节点。当接收器将要移出其当前直接代理的范围时，它挑选另一个相邻节点作为其新的直接代理，并且将新的直接代理的位置发送到其主代理，使得将来的数据被转发到新的直接代理。为了避免丢失已经发送到旧的直接代理的数据，位置也被发送到旧的直接代理（参见图5）。新的直接代理的选择可以通过从接收器广播请求消息来完成，然后接收器选择以最强信噪比应答的节点。主代理在接收器的直接传播节点处表示移动接收器，使得接收器的移动性对其直接传播节点是透明的。直接代理在接收器的主代理处表示接收器，使得接收器可以在不断移动的同时连续地接收数据。不知道自己位置的用户仍然可以从网络收集数据。当接收器移出一定距离时（例如，小区大小），它挑选一个新的主代理，并在本地洪泛查询，以发现新的传播节点即时代理（IA）更新1DsPASIADs6可能更近。为了避免从其旧的主代理接收重复数据，TTDD让每个主代理一旦其定时器超时，该定时器被设置为近似于移动接收器保持在小区中的持续时间，到期。旧的即时代理以类似的方式超时，除了它具有较短的计时器，该计时器大约是接收器保持在一跳距离内的持续时间。如果接收器示例如图4所示。当直接传播节点Ds处的软状态到期时，Ds停止发送上游更新，因为它不具有请求数据的任何其他宿或相邻下游传播节点。过了一会儿，如果S2仍然需要数据，则在G处转发的数据消息仅去往宿S2这样，由接收器在网格上和旧代理中的旧查询构建的所有状态都将被清除。通过轨迹转发，使得在小范围内（大致为小区大小）的宿移动性对更高层网格转发透明。涉及新的传播节点发现的超出小区大小距离的移动性可能影响网格上的某些上游传播节点。由于信宿发现的新传播节点可能在相邻小区中，因此对网格转发的调整通常仅影响几个附近的传播节点。2.3网格维护为了避免将网格状态无限期地保存在传播节点上，当源发送数据通告消息以构建网格时，源在数据通告消息中包括网格生存期如果生存期过去并且网格上的传播节点没有接收到任何进一步的数据通告来更新生存期，则它们清除它们的状态并且网格不再存在。合适的网格生命周期值取决于数据可用性周期和传感器网络的任务在图1的示例中，如果任务是返回如果tank停留的时间比原始估计的时间长，则源可以发送新的数据公告以延长网格的寿命。对于任何结构，重要的是处理意外的组件故障的鲁棒性。为了保存传感器的稀缺能量供应，我们在其寿命期间不定期刷新网格。相反，我们采用了一种称为上游信息复制的机制，其中每个传播节点在其邻居中复制其上游传播节点。当该传播节点发生故障2时，来自其需要数据的下游传播节点的上游更新消息将在这些邻居之一处停止然后，根据所存储的信息将更新消息转发到上游传播节点。当数据稍后来自上游时，新的传播节点将遵循与源最初构建网格相同的规则。由于这个新的传播节点不知道哪个下游传播节点邻居需要数据，所以它简单地将数据转发到所有其他三个传播点。需要数据的下游传播节点将继续发送上游更新消息以重新建立转发状态;而不需要数据的下游传播节点丢弃数据并且不发送任何上游更新，使得未来的数据报告将不会流向它。注意，该机制还处理多个传播节点沿转发路径同时发生故障的场景即时传播节点的故障通过接收器处的超时来检测。当接收器停止接收数据一段时间时，它重新泛洪查询以定位新的dissem- ination节点。主代理或直接代理的故障由类似的超时检测，并将选择新的超时。这些技术提高了TTDD对意外节点故障的鲁棒性。我们的网格维护由正在进行的查询或上游更新按需触发。与周期性的网格刷新相比，它以更少的能量消耗换取更大的处理开销，我们认为这是无线传感器网络中更关键的资源。我们在4.4节中通过模拟展示了网格维护的性能。3管理费用分析在本节中，我们将分析TTDD的效率和可伸缩性。我们测量两个指标：通信开销的一些汇检索一定量的数据从源，和复杂的状态，保持在传感器节点的数据传播。我们研究了固定和移动汇的情况下。我们比较TTDD与面向sink的数据分发方法（以下简称SODD），其中每个sink首先泛洪整个网络，在所有传感器节点上安装数据转发状态，然后源作出反应，以提供数据。定向扩散[11]，DRP[5]和GRAB[20]都采用这种方法，尽管每个都采用不同的优化技术，如数据聚合和查询聚合，以减少传递的消息数量因为两2.邻居可以通过MAC层机制（例如，当可用时的应答）或者通过明确地请求应答（如果它在某个时间段内没有偷听到传播节点）来检测传播节点的故障。7nMMMCOSODD=k·m·Nl+C Nc N）m对于k聚合技术也适用于TTDD，我们在执行开销分析时不考虑这些聚合。相反，我们专注于每个协议的最坏情况下的通信开销。目标是保持分析简单，易于遵循，同时捕捉TTDD和SODD之间的基本差异我们会-=kmnl+kc（ml+d）×2N加上传感器网络任务更新的开销N1和构建网格的开销N4N1，TTDD的通信开销（CO）变为：在分析传感器状态维护的复杂性时考虑聚集的影响4NCOTTDD=Nl+Kmnl+kc（ml+d）2个N（1）3.1型号和符号我们考虑一个面积为A的正方形传感器场，其中N个传感器节点均匀分布，使得在每一侧都有在SODD中，每次sink泛洪整个网络时，它都会接收到d个数据包。数据通过直线路径到达接收器。同样，在不考虑聚合的情况下，通信开销为：大约有N个传感器节点。 有k个水槽，传感器领域。它们以平均速度v移动，同时在时间段T期间从源接收d个数据分组。每个数据分组具有单位大小，并且查询和数据通告消息都具有可比较的大小l。淹没一个区域的通信开销是成比例的传感器节点的数量。通信Nl+（c<$N）dM对于k个移动汇点，总的最坏情况开销为：.. √ΣdΣM通过贪婪地理路径发送消息的成本CAL转发与路径中传感器节点的数量成比例在传感器节点的无线通信范围内的邻居的平均数量在TTDD中，源将传感器场划分为单元;每个单元=kmNl+kcdN请注意，这里我们不计算更新传感器网络任务的开销，因为SODD可能在接收器泛洪其查询时更新任务。面积为α2。 有n =Nα2 每个传感器节点小区和在小区的每个A上的n个 每一个宿侧为了比较TTDD和SODD，我们有：遍历m个单元，并且m的上界为1 +vT。为固定汇，m=1。αCOTTDDCOSODD1however，41 +100Nn，.d2002年M3.2通信开销我们首先分析了TTDD和SODD的最坏情况下的通信开销。我们假设在TTDD和SODD中，信宿更新其位置m次，并且在两次连续的位置更新之间接收d个在TTDD中，sink通过在本地洪泛查询来更新其位置，以到达即时传播节点，查询从该即时传播节点沿着网格被进一步转发到源在不考虑潜在的查询聚合的情况下，查询到达源的开销为：因此，在大规模传感器网络中，随着传感器网络规模（N）、汇点数量（k）或汇点移动性（由m表征）的增加，TTDD与SODD方法相比具有渐近更低的例如，传感器网络由N=10，000个传感器节点组成，在TTDD网格单元中有n= 100个传感器节点。假设c= 1且l= 1，为了传送d= 100个数据分组：CO0. 024m +1。四一加一。414nl+ 2002年（c）N）lTTDDCOSODD=kM+1其中，nl是本地洪泛开销，并且c_N是平均开销。沿直线路径的传感器节点的年龄数，对于固定汇的情况，m = 1，假设我们有四个汇k =4，COTTDD= 0。89岁当汇的流动性源到汇（0

下载后可阅读完整内容，剩余1页未读，立即下载