Efficiently reconfigurable backbones for wireless sensor networks

We present the definition and performance evaluation of a protocol for building and maintaining a connected backbone among the nodes of a wireless sensor networks (WSN). Building backbones first, and then coping with network dynamics is typical of protocols for backbone formation. Rules for building the backbone, however, do not take into account the following network dynamics explicitly. This makes maintaining a connected backbone quite costly, especially in terms of reorganization time, overhead and energy consumption. Our protocol includes in the backbone forming operations a fail-safe mechanism for dealing with the addition and the removal of nodes, which are typical events in a WSN. More specifically, the network is kept partitioned into clusters that are cliques, i.e., nodes in each cluster are directly connected to each others. Therefore, removing a node does not disrupt a cluster, and adding one requires simple operations for checking node admission to the cluster. The protocol, termed CC ("double C", for clique clustering), comprises three phases, each designed to render the operations of the others swift and efficient. The first phase partitions the network into clusters that are cliques. Clusters are then joined to form a backbone that is provably connected. Finally, the third, more on-line phase, maintains the backbone connected in face of node additions and removals. We compare the performance of CC with that of DMAC, a protocol that has been previously proposed for building and maintaining clusters and backbones in presence of network dynamics. Our comparison concerns metrics that are central to WSN research, such as time for clustering and backbone reorganization, corresponding overhead, extent of the reorganization (i.e., number of nodes involved in it), and properties of the resulting backbone, such as its size, backbone route length, number of gateways and nodes per cluster. Our ns2-based simulation results show that the design criteria chosen for CC are effective in producing backbones that can be reconfigured quickly and with remarkably lower overhead. (c) 2007 Elsevier B.V. All rights reserved.