Abstract

Wireless sensor networks (WSNs) are deployed for monitoring and controlling of systems where human intervention is not desirable or feasible. One typical characteristic of WSNs is the possibility of deploying many nodes in an area to ensure sufficient coverage of an area and/or to have redundancy against node failures. However, in a relatively crowded network, many problems are aggravated: (1) many nodes interfere with each other, (2) there are a lot of possible routes, (3) nodes might needlessly use large transmission power to talk to distant nodes directly, and (4) routing protocols might have to recompute routes even if only a small number of nodes changed their locations. These problems can be overcome by selecting some nodes as a virtual backbone (VB) for a network, in which only the links within this backbone and direct links from other nodes to the backbone nodes are mainly used in the WSN. Usually, we use a dominating set (DS) to serve as a backbone for a WSN, which is a subset of nodes in the network where every node is either in the subset or a neighbor of at least one node in the subset. For a backbone to be useful, it should be connected, namely, by a connected DS (CDS). The nodes in a CDS are called dominators, otherwise dominatees. In a WSN with a CDS as its VB, dominatees only forward their data to their connected dominators. Moreover, the CDS with the smallest size (the number of nodes in the CDS) is called a minimum-sized CDS (MCDS). In this chapter, CDS and VB are used interchangeably.