Abstract
We very proud and honored to have been entrusted to be Guest Editors for this special issue. Papers were sought to comprehensively cover the algorithmic issues in the “hot” area of sensor networking. The concentration was on network layer problems, which can be divided into two groups: data communication problems and topology control problems. We wish to briefly introduce the five papers appearing in this special issue. They cover specific problems such as time division for reduced collision, fault tolerant clustering, self-stabilizing graph optimization algorithms, key pre-distribution for secure communication, and distributed storage based on spanning trees and triangulation.
Sekiyama, Kubo, Fukunaga, and Date propose a novel communication timing control for wireless sensor networks. Through local and fully distributed interactions in the communication network, the coupled phase dynamics self-organizes into an efficient time division pattern of the communication so that the network reduces the collision frequency by diffusion of the phase pattern, while it sustains sufficient throughput of the communications.
Younis, Fahmy, and Santi propose REED (Robust Energy-Efficient Distributed clustering) for clustering sensors deployed in hostile environments in an interleaved manner with low complexity. Their primary objective is to construct a k-connected clustered network. Fault tolerance is achieved by selecting k-independent sets of cluster heads so that each node can quickly switch to other cluster heads in case of failures.
Goddard, Hedetniemi, Jacobs, and Srimani propose self-stabilizing algorithms for three graph optimization problems: a minimal total dominating set (where every node must be adjacent to a node in the set) and its generalizations, a maximal k-packing (a set of nodes where every pair of nodes are more than distance, k, apart), and a maximal strong matching (a collection of totally disjoint edges).
Chakrabarthi, Maitra, and Roy analyze key pre-distribution in sensor networks. They concentrate on the schemes where the key pre-distribution strategies are based on transversal design, study the largest clique sizes, and show that the merging of blocks to construct a node provides larger clique sizes than considering a block itself as a node in a transversal design.
Geogiou and Kranakis, et al., show how to extract a triangulated planar spanner, and propose several algorithms to construct spanning trees of the triangulation. A load balanced distributed storage strategy on top of the trees is presented, which spreads replicas of data stored in the hosts in a way that the difference between the number of replicas stored by any two hosts is small.