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

Pedro M. Wightman, Miguel A. Labrador

Producción científica: Contribución a una revistaArtículo de Investigaciónrevisión exhaustiva

20 Citas (Scopus)


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.

Idioma originalInglés estadounidense
Páginas (desde-hasta)1997-2010
Número de páginas14
PublicaciónJournal of Network and Computer Applications
EstadoPublicada - nov. 2011
Publicado de forma externa

Áreas temáticas de ASJC Scopus

  • Hardware y arquitectura
  • Informática aplicada
  • Redes de ordenadores y comunicaciones


Profundice en los temas de investigación de 'A family of simple distributed minimum connected dominating set-based topology construction algorithms'. En conjunto forman una huella única.

Citar esto