Mobile Intelligence

2.4 AREA-BASED CDS FORMATION ALGORITHM

2.4.1 Overview

A well-known method for building connected dominating set is to construct an MIS first, which is also a dominating set, and then add some connectors to guarantee the connectivity. This method was utilized by Alzoubi et al. [14, 15]. The algorithms in Ref. [14] were implemented by first electing a leader r among the nodes, which was going to be the root of a spanning tree T. The approximation ratios of these algorithms are attractive; however, the message complexity O(n log n), which is bounded by the distributed leader election, is quite high in real practice [6]. Moreover, they are not localized algorithms. The algorithm presented in Ref. [15] has an optimal message complexity O(n), but it connects any pair of dominators (at most three hops away) by adding one or two connectors. Consequently, the resultant CDS has a relative large size with some redundant connectors.

Our main objective of this Area algorithm is to reduce the size of CDS. We use the most-valued nodes as the metric to select the nodes among all nodes in the graph for the CDS. The value of a node is a performance-related characteristic such as node ID, node degree, or remaining battery life. In this chapter, we define two kinds of most-valued nodes, one is the nodes with the minimum ID among all the candidates of dominators or connectors (the resulting Area algorithm is called Min ID) and the other is the nodes with the maximum degree among all the candidates ...