Ad Hoc and Sensor Wireless Networks: Architectures, Algorithms and Protocols

Indexed in: Scopus, EBSCO, Ulrich's Periodicals Directory

This Ebook brings together the latest developments and studies of Mobile Ad Hoc Networks (MANETs) and Wireless Sensor Networks (WSNs), which should provide a seedbed for new breakthroughs. It focuses ...
[view complete introduction]

US $

*(Excluding Mailing and Handling)

Connected Dominating Sets

Pp. 19-39 (21)

Yiwei Wu and Yingshu Li


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.


Department of Computer Science, Georgia State University