A family of simple distributed minimum connected dominating set-based topology construction algorithms

This paper considers the problem of topology construction to save energy in wireless sensor networks. The proposed topology construction mechanisms build reduced topologies using the Connected Dominating Set approach in a distributed, efficient, and simple manner. This problem is very challenging because the solution must provide a connected network with complete coverage of the area of interest using the minimum number of nodes possible. Further, the algorithms need to be computationally inexpensive and the protocols simple enough in terms of their message and computation complexity, so they do not consume more energy creating the reduced topology than the energy that they are supposed to save. In addition, it is desirable to reduce or completely eliminate the need of localization mechanisms since they introduce additional costs and energy consumption. To this end, we present the family of A3 distributed topology construction algorithms, four simple algorithms that build reduced topologies with very low computational and message complexity without the need of localization information: A3, A3Cov, A3Lite and A3CovLite. The algorithms are compared in sparse and dense networks versus optimal theoretical bounds for connected-coverage topologies and two distributed heuristics found in the literature using the number of active nodes and the ratio of coverage as the main performance metrics. The results demonstrate that there is no clear winner, and rather, trade offs exist. If coverage is not as critical as energy (network lifetime), it would be better to use A3Lite, as it needs fewer number of nodes and messages. If coverage is very important for the application, then the A3CovLite is the best option mostly because of the lower message complexity.