Chapter 2

Connected Dominating Sets

Yiwei Wu and Yingshu Li

Abstract

Wireless sensor networks (WSNs) are now widely used in many applications. However, routing in WSNs is very challenging due to the inherent characteristics that distinguish these networks from other wireless networks. The concept of hierarchical routing is widely used to perform energy-efficient routing in WSNs. Thus, a Connected Dominating Set (CDS) has been recommended to serve as a virtual backbone for a WSN to reduce routing overhead. Fault tolerance and routing flexibility are necessary for routing since nodes in WSNs are prone to failures. Hence, it is important to maintain a certain degree of redundancy in a CDS. Therefore, the concept of k-connected m-dominating sets (kmCDS) is used to provide these redundancies. In this chapter, we present CDS based routing protocols and focus on how to construct CDS and kmCDS, including both centralized and distributed algorithms.

Total Pages: 19-39 (21)

Purchase Chapter  Book Details

RELATED BOOKS

.Multi-Objective Optimization In Theory and Practice II: Metaheuristic Algorithms.
.Arduino and SCILAB based Projects.
.Arduino meets MATLAB: Interfacing, Programs and Simulink.
.Budget Optimization and Allocation: An Evolutionary Computing Based Model.