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.