Construction and Maintenance of a Novel Cluster-based Architecture for Ad Hoc Sensor Networks
Jiro Uchida, A. K. M. Muzahidul Islam, Yoshiaki Katayama, Wei Chen and Koichi Wada
In this paper, we consider the construction and maintenance of a clusterbased architecture for a sensor network, with two atomic operations node-move-in and node-move-out which are performed by appearance and disappearance of a node. In our proposed architecture, a deterministic broadcasting can be done in O(p) rounds, where p is the number of clusters. We present a randomized algorithm for a node-move-in, and a deterministic algorithm for a node-move-out operations. When nodes in the network are organized with total 1-hop data, these operations work in expected O(q) and O(|T|) rounds, respectively, where q is the number of neighbors in the network of the joining node, and T is a subtree of the architecture whose root is the leaving node. We also show that if nodes in the network need only partial 1-hop data (i.e., incomplete knowledge about the neighbors in the network), node-move-in can be done in expected O(log q) rounds and node-move-out can have a similar performance as the case of the total 1-hop data. Finally, we demonstrate some simulation results for the operations, where we show that in our proposed structure the number of clusters increases very slowly w.r.t. the increasing number of nodes in the network.