Independent and Dominating Sets in Wireless Communication Graphs

Wireless ad hoc networks are advancing rapidly, both in research and more and more into our everyday lives. Wireless sensor networks are a prime example of a new technology that has gained a lot of attention in the literature, and that is going to enhance the way we view and interact with the environment. These ad hoc and sensor networks are modeled by communication graphs which give the communication links between some devices or nodes equipped with wireless transceivers or radios. The nature of wireless transmissions does not lead to an arbitrary network topology, but creates a network with certain properties. These properties include the important structure of bounded growth. In this thesis, we look at the structures and resulting optimization problems of independent and dominating sets in on graphs that model wireless communication networks. Independent and dominating sets are prominently used in the efficient organization of large-scale wireless ad hoc and sensor networks. In a communication graph, an independent set consists of vertices that cannot communicate with one another directly. Such a set is commonly used in clustering strategies, e.g. to obtain a hierarchical view of the network. A dominating set is given by a set of vertices so that every vertex in the graph is either in this set, or adjacent to a vertex from this set. Dominating sets of small cardinality are frequently used for backbone structures in communication networks, e.g. to obtain efficient multi-hop routing protocols. For the optimization problems of seeking independent sets of large cardinality or weight (Maximum Independent Set problem), and seeking dominating sets of small cardinality (Minimum Dominating Set problem) on graphs of polynomially bounded growth, we present and discuss polynomial-time approximation schemes (PTAS). The algorithms presented are robust in the sense that they accept an undirected graph, and return a desired solution or a certificate that shows that the instance does not satisfy the structural properties of a wireless communication graph. Wireless ad hoc and sensor networks usually lack a central control instance. Local, distributed algorithms are designed to operate in such a scenario. We propose a fast local algorithm that constructs a so-called maximal independent set, which is also dominating. We also extend the ideas behind the centrally executed PTAS towards a local approach. This gives a distributed approximation scheme for the Maximum Independent Set and Minimum Dominating Set problems on wireless communication graphs. The second part of the thesis is devoted to an application of independent and dominating sets in a wireless sensor network. We present the design of an energy-efficient communication strategy for low-resource, large-scale wireless networks that is based on an integrated approach stemming over various layers of the communication stack. The transmission of data packets in this scheme is done in a scheduled manner, thus reducing the number of collisions due to simultaneous transmissions. The approach, called EMACs, also includes the creation and maintenance of a connected backbone in the network that is used for implicit sleep-state scheduling of the nodes to conserve additional energy. Some results obtained from a practical implementation of this scheme indicate that the EMACs communication scheme improves the network lifetime compared to existing schemes for wireless sensor networks. This thesis answers and contributes to several open questions from the literature. The characterization of wireless communication graphs by the bounded growth property includes geometrically defined Unit Disk Graphs. By giving a PTAS that does not exploit geometric information for the Maximum Independent and Minimum Dominating Set problems on these graphs, we give a positive answer to the open problem of the existence of a PTAS for Unit Disk Graphs without geometric representation. Local, distributed maximal independent set computation has received a lot of attention in the literature, and a fast, i.e. poly-logarithmic distributed time approach is a longstanding open problem for communication networks in general. At least for wireless communication networks, we present the first such fast, local approach.