Self-stabilizing Wireless Connected Overlays
Self-stabilizing Wireless Connected Overlays
复制标题
自稳定无线连接覆盖层
DOI：
10.1007/11945529_30
复制
发表时间：
2006
期刊：
影响因子：
--
通讯作者：
M. Potop
中科院分区：
文献类型：
--
作者：
Vadim Drabkin;R. Friedman;M. Potop
我们提出了无线网络连接覆盖的第一个自稳定结构的正确性证明和复杂性分析。基于连通支配集（CDS）计算的无线传感器网络。其基本思想是构建一个包含少量节点的覆盖层，仅依靠局部的信息和知识交换，但仍能获得网络的完全连通性。我们采用了两种构建方法：第一种方法由两个并行任务组成，即计算最大独立集（MIS），然后在MIS节点之间添加桥接节点。第二种方法计算连通支配集，利用支配体是不共享相同邻域的节点之间的桥梁这一观察结果。
We propose the correctness proofs and the complexity analysis for the first self-stabilizing constructions of connected overlays for wireless networks (eg. MANETs, WSN) based on the computation of Connected Dominating Set (CDS). The basic idea is to construct an overlay that contains a small number of nodes, but still obtain full connectivity of the network while only relying on local exchanges of information and knowledge. We adopt two methodologies of construction: the first methodology consists of two parallel tasks, namely, computing a maximal independent set (MIS) and then adding bridge nodes between the MIS nodes. The second methodology computes a connected dominating set using the observation that a dominator is a bridge between nodes that do not share the same neighborhood.
The proposed algorithms are fully decentralized and are designed in a self-stabilizing manner in order to cope with transient faults, mobility and nodes join/leave. In particular, they do not need to be (re)initialized after a fault or a physical topology change. That is, whatever the initial configuration is, the algorithms satisfy their specification after a stabilization period. The convergence time of our algorithms is linear in the size of the network and they use only one extra bit of memory. We also present an optimization of our algorithms that reduces the number of nodes in the cover. However, the optimization increases the convergence time with a constant factor.