EEDTC: Energy-efficient dominating tree construction in multi-hop wireless networks

Motivated by reducing communication overhead and prolonging network lifetime in multi-hop wireless networks, we propose an energy-efficient dominating tree construction (EEDTC  ) algorithm to construct a dominating tree that can serve as a communication backbone in wireless infrastructures. The algorithm uses kk-hop neighbors’ information (k∈[1,DG]k∈[1,DG], where DGDG is the diameter of graph GG). EEDTC   has a theoretical approximation factor of at most 9. When kk is equal to 1, it has O(n)O(n) message complexity and O(⌈n1−1/DG⌉−1)O(⌈n1−1/DG⌉−1) time complexity. Due to the low message complexity, EEDTC performs well on energy consumption. The energy-aware ranking technique that is introduced can also balance energy consumption in the network, and hence reduce the probability of network failures caused by energy depletion of backbone nodes.