Construction of Self-Stabilizing k Disjoint Sense-Sleep Trees with Application to Sensor Networks

Jun KINIWA 

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences  Vol.E92-A  No.4  pp.1174-1181
Publication Date: 2009/04/01
Online ISSN: 1745-1337
Print ISSN: 0916-8508
Type of Manuscript: PAPER
Category: Algorithms and Data Structures
Keyword: 
sensor network,  sense-sleep trees,  self-stabilization,  dominating k-partition rule,  range adjustment,  simulation, 

Full Text: PDF(210.6KB)

Summary: 
Sensor networks have promising applications such as battlefield surveillance, biological detection, and emergency navigation, etc. Crucial problems in sensor networks are energy-efficiency and collision avoidance in wireless communication. To deal with the problems, we consider a self-stabilizing solution to the construction of k disjoint sense-sleep trees, where range adjustment and the use of GPS are allowed. Each root is determined by its identifier and is distinguished by its color, the identification of a tree. Using a dominating k-partition rule, each non-root node first determines a color irrelevant to the root. Then, the non-root node determines a parent node that is equally colored with minimal distance. If there is no appropriate parent, the range is extended or shrunk until the nearest parent is determined. Finally, we perform a simulation.