A Hierarchy-Based Fault-Local Stabilizing Algorithm for Tracking in Sensor Networks
A Hierarchy-Based Fault-Local Stabilizing Algorithm for Tracking in Sensor Networks
复制标题
传感器网络中基于层次结构的故障局部稳定跟踪算法
DOI：
10.1007/11516798_22
复制
发表时间：
2004
期刊：
影响因子：
--
通讯作者：
N. Lynch
中科院分区：
文献类型：
--
作者：
M. Demirbas;A. Arora;Tina Nolte;N. Lynch
在本文中，我们介绍了基于层次的故障局部稳定的概念和一种新的自我修复/故障遏制技术，并将它们应用于Stalk。Stalk是一种在传感器网络中进行跟踪的算法，它在网络的底层分层分区之上维护一个数据结构。从一个任意损坏的状态开始，Stalk满足其规范内的时间和通信成本成比例的故障区域的大小，定义在层次结构中发生故障的级别。这种局部稳定是通过减缓信息的传播来实现的，因为作为Stalk基础的层次结构的级别增加了，使得较低级别传播的较新信息能够在错误信息传播超过恒定数量的级别之前覆盖较高级别的错误信息。此外，当不发生故障时，这种稳定性是在不降低数据结构的效率或可用性的情况下实现的：1）找到移动的对象的操作距离d需要O（d）完成时间和通信，2）在对象已经移动了总共d距离之后更新跟踪结构需要O（d* log网络直径）完成的分摊时间和通信，3）被跟踪对象可以重新定位而无需等待Stalk完成由先前移动引起的更新，以及4）移动的对象可以在afindis进行时移动。
In this paper, we introduce the concept ofhierarchy-based fault-local stabilizationand a novel self-healing/fault-containment technique and apply them in Stalk. Stalkis an algorithm for tracking in sensor networks that maintains a data structure on top of an underlying hierarchical partitioning of the network. Starting from an arbitrarily corrupted state, Stalksatisfies its specification within time and communication cost proportional to the size of the faulty region, defined in terms of levels of the hierarchy where faults have occurred. This local stabilization is achieved by slowing propagation of information as the levels of the hierarchy underlying Stalkincrease, enabling more recent information propagated by lower levels to override misinformation at higher levels before the misinformation is propagated more than a constant number of levels. In addition, this stabilization is achieved without reducing the efficiency or availability of the data structure when faults don’t occur: 1) Operations tofindthe mobile object distance d away takeO(d) time and communication to complete, 2) Updates to the tracking structure after the object has moved a total ofddistance takeO(d*lognetwork diameter) amortized time and communication to complete, 3) The tracked object may relocate without waiting for Stalkto complete updates resulting from prior moves, and 4) The mobile object can move while afindis in progress.