Localized topology generation mechanisms for wireless sensor networks

Authors:

Abstract
The basic topology desired in data-gathering wireless sensor networks is a spanning tree, since the traffic is mainly in the form of many-to-one flows. Nodes in the network can self- configure themselves into such a topology by a two-phase process: a flood initiated by the root node, followed by parent selection by all nodes. We present four localized topology generation mechanisms - earliest-first, randomized, nearest-first, and weighted-randomized parent selection. We also compare the network performance of these mechanisms on the basis of the following metrics: node degree, robustness, channel quality, data aggregation and latency; our study shows how localized self- configuration mechanisms can impact the global network behavior. is a spanning tree. This tree can be constructed by a two-step process: the outward flooding of a discovery message, followed by a phase in which all nodes select a parent based on the messages they received. Note that this simple tree construction process has the benefit of being completely localized, leading to a scalable design. In this paper, we first describe four topology generation mechanisms: earliest-first, randomized, nearest-first, and weighted-randomized. These localized mechanisms differ in the manner in which the parent selection takes place and result in qualitatively different tree structures. We show that one significant graph-level metric that distinguishes these mechanisms is the variance of the node degree. We next evaluate these four mechanisms based on four network performance metrics: robustness, channel quality, data aggregation, and latency. Our primary objective is not finding the "optimal" mechanism, since there is no single strategy that performs equally well for all metrics; rather, our contribution is to analyze and evaluate how the different localized topology generation schemes can impact global network performance. The rest of this paper is organized as follows. Section II discusses some related work. Section III introduces the four mechanisms in constructing the network topology. Section IV discusses the metrics used in the evaluation. Section V provides the setup of simulation and its results. Conclusions and future work are presented in Section VI.