Tree-Based Virtual Backbone Construction in Mobile Ad Hoc Networks by Kazuya Sakai A thesis submitted to the Graduate Faculty of Auburn University in partial ful?llment of the requirements for the Degree of Master of Science Auburn, Alabama August 9, 2010 Keywords: virtual backbone, connected dominating set, CDS, ad hoc networks Copyright 2010 by Kazuya Sakai Approved by Wei-Shinn Ku, Chair, Assistant Professor of Computer Science and Software Engineering Alvin Lim, Associate Professor of Computer Science and Software Engineering Xiao Qin, Assistant Professor of Computer Science and Software Engineering Abstract The connected dominating set (CDS) has been extensively used for routing and broad- cast in mobile ad hoc networks. While existing CDS protocols are successful in constructing CDS of small size, they either require localized information beyond immediate neighbors, lack the mechanism to properly handle nodal mobility, or involve lengthy recovery procedure when CDS becomes corrupted. In this paper, we introduce the tree-based CDS protocols, which ?rst elect a number of initiators distributively and then utilize timers to construct a CDS from initiators with the minimum localized information. We demonstrate that our CDS protocols are capable of maintaining CDS in the presence of changes of network topol- ogy. Depending on the number of initiators, there are two versions of our tree-based CDS protocols. The Single-Initiator (SI) works the best when the network diameter is given. On the other hand, the Multi-Initiator version (MI) built on top of SI is a localized CDS protocol and possesses all of the advantages of SI. We evaluate our protocols by both the ns-2 simulation and an analytical model. Compared with the other known CDS protocols, the simulation results demonstrate that both SI and MI produce and maintain CDS of very competitive size. The analytical model shows the expected convergence time and the number of messages required by SI and MI in the construction of CDS, which match closely to our simulation results. This helps to establish the validity of our simulation. In addition to the two tree-based CDS protocols, we proposed the two post optimiza- tion techniques, Fast-Convergence Dominator Tree Construction (FC-DTC) and Extended Mobility Handling (EMH). FC-DTC signi?cantly reduces the convergence time required by SI and MI, and EMH enables SI and MI to adapt to the topology changes more e?ciently. The simulation and analytical studies demonstrate these extensions drastically improve the performance of SI and MI. ii Acknowledgments I would like to thank people who guided and supported me during my study at Auburn University. Without their contributions, this research would not be possible. I appreciate my academic advisor, Dr. Wei-Shinn Ku, for his guidance and assistant. I am also grateful to Dr. Alvin Lim and Dr. Xiao Qin for serving my committee. There were some helps from people outside of Auburn University. I would like to thank Dr. Min-Te Sun at National Central University for his help for my research. Additionally, I would like to show my great appreciation to my mother for her support during my graduate study. iii Table of Contents Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ii Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iii List of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vi List of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viii 1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 2 Related Works . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2.1 Minimum CDS Protocols . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2.1.1 Substraction-based CDS Construction . . . . . . . . . . . . . . . . . 4 2.1.2 Addition-based CDS Construction . . . . . . . . . . . . . . . . . . . . 5 2.2 Energy-Aware CDS Protocols . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.3 k-CDS Protocols . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.4 Directed CDS Protocols . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.5 Metrics to Evaluate CDS Protocols . . . . . . . . . . . . . . . . . . . . . . . 7 3 Tree-Based CDS Construction Protocols . . . . . . . . . . . . . . . . . . . . . . 9 3.1 The Basic Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 3.2 The SI Tree-Based CDS Protocol . . . . . . . . . . . . . . . . . . . . . . . . 10 3.2.1 SI-Initiator Election Phase . . . . . . . . . . . . . . . . . . . . . . . . 10 3.2.2 SI-Tree Construction Phase . . . . . . . . . . . . . . . . . . . . . . . 12 3.2.3 Correctness of the SI Protocol . . . . . . . . . . . . . . . . . . . . . . 14 3.2.4 SI Mobility Handling . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 3.2.5 Example of the SI Protocol . . . . . . . . . . . . . . . . . . . . . . . 19 3.3 The MI Tree-Based CDS Protocol . . . . . . . . . . . . . . . . . . . . . . . . 20 3.3.1 MI-Initiator Election Phase . . . . . . . . . . . . . . . . . . . . . . . 21 iv 3.3.2 MI-Tree Connection Phase . . . . . . . . . . . . . . . . . . . . . . . . 23 3.3.3 Correctness of the MI Protocol . . . . . . . . . . . . . . . . . . . . . 25 3.3.4 MI Mobility Handling . . . . . . . . . . . . . . . . . . . . . . . . . . 26 3.4 Simulations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 3.4.1 Simulation Con?gurations . . . . . . . . . . . . . . . . . . . . . . . . 28 3.4.2 Simulation Results for Static Network Scenario . . . . . . . . . . . . 30 3.4.3 Simulation Results for Mobile Network Scenario . . . . . . . . . . . . 32 3.5 Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 3.5.1 Analytical Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 3.5.2 Theoretical and Simulation Result Comparisons . . . . . . . . . . . . 37 4 Extensions of Tree-Based CDS Protocols . . . . . . . . . . . . . . . . . . . . . . 39 4.1 Fast-Convergence Dominator Tree Construction . . . . . . . . . . . . . . . . 39 4.1.1 The Issue of the Tree Construction . . . . . . . . . . . . . . . . . . . 39 4.1.2 Fast Tree Construction Algorithm . . . . . . . . . . . . . . . . . . . . 41 4.1.3 Mobility Handling . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 4.2 Extended Mobility Handling . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 4.2.1 The Issue of the Mobility Handling . . . . . . . . . . . . . . . . . . . 45 4.2.2 Extended Mobility Handling Algorithms . . . . . . . . . . . . . . . . 46 4.3 Simulations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 4.3.1 Simulation Con?gurations . . . . . . . . . . . . . . . . . . . . . . . . 50 4.3.2 Simulation Results for Static Network Scenario . . . . . . . . . . . . 50 4.3.3 Simulation Results for Mobile Network Scenario . . . . . . . . . . . . 52 4.4 Analytical Model for The Convergence Time . . . . . . . . . . . . . . . . . . 55 5 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 v List of Figures 3.1 An example of the SI protocol. . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 3.2 The number of initiators and CDS size. . . . . . . . . . . . . . . . . . . . . . . . 23 3.3 An example of the MI protocol. . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 3.4 An impossible case at the end of MI tree construction phase. . . . . . . . . . . . 26 3.5 CDS size. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 3.6 Number of messages. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 3.7 Average tra?c (kbps). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 3.8 Convergence time. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 3.9 Percentage of time CDS is alive. . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 3.10 Average CDS size. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 3.11 Number of messages to maintain CDS. . . . . . . . . . . . . . . . . . . . . . . . 34 3.12 Average tra?c to maintain CDS. . . . . . . . . . . . . . . . . . . . . . . . . . . 34 3.13 Delivery rate. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 3.14 End-to-end delay. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 3.15 Number of RREQ packets. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 vi 3.16 Convergence time. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 3.17 Number of messages. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 4.1 An example of a tree construction. . . . . . . . . . . . . . . . . . . . . . . . . . 40 4.2 Original Topology I. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 4.3 Mobility handling of MI on Topology I. . . . . . . . . . . . . . . . . . . . . . . . 45 4.4 Original Topology II. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 4.5 Mobility handling of MI on Topology II. . . . . . . . . . . . . . . . . . . . . . . 46 4.6 Topology with Height-Reduction . . . . . . . . . . . . . . . . . . . . . . . . . . 48 4.7 Mobility handling of MI after Height-Reduction . . . . . . . . . . . . . . . . . . 48 4.8 Topology with Initiator-Reduction. . . . . . . . . . . . . . . . . . . . . . . . . . 50 4.9 CDS size. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 4.10 Convergence time. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 4.11 Number of messages. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 4.12 Average tra?c (bps). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 4.13 Percentage of time CDS is alive. . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 4.14 Average CDS size. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 4.15 Number of messages to maintain CDS. . . . . . . . . . . . . . . . . . . . . . . . 54 4.16 Average tra?c to maintain CDS. . . . . . . . . . . . . . . . . . . . . . . . . . . 54 4.17 Convergence time. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 vii List of Tables 3.1 De?nition of notations. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 3.2 Simulation parameters. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 3.3 Parameters for ns-2. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 4.1 De?nition of notations for FC-DTC and EMH. . . . . . . . . . . . . . . . . . . 41 viii Chapter 1 Introduction Mobile ad hoc networks (MANETs) are well-suited for communications in sensor net- works as well as the battle?eld and rescue missions where a ?xed infrastructure is not readily available [1]. The e?ectiveness of many communication primitives for MANETs, such as routing [2], multicast/broadcast [3], and service discovery [4], rely heavily on the availability of a virtual backbone. A virtual backbone of a wireless network is typically the connected dominating set (CDS) of the graph representation of the network. It is de?ned as a subset of nodes in a network such that each node in the network is either in the set or a neighbor of some nodes in the set, and the induced graph of the nodes in the set is connected. In general, the smaller the CDS is, the less communication and storage overhead the protocols making use of CDS will incur. Hence, it is desired that the size of the CDS for MANETs to be as small as possible. On the other hand, it is known that the problem of ?nding the minimum CDS is NP-hard [5]. The problem becomes even more intriguing when no node has the view of the complete network topology, which is generally the case in most MANETs. As a result, the existing CDS protocols for MANETs [6?19] emphasize on constructing a small CDS distributively with localized information. While these protocols are successful in creating a small CDS, they either lack the mechanism to maintain the CDS transparently when network topology changes from time to time or incur large amount of control overhead. Notice that the topology change can be the result of node mobility, the power outage of some nodes in the network, the deployment of additional nodes to the network, or the combination of the aforementioned cases. The reconstruction of CDS from scratch can keep the CDS from being available for service for an extended period of time. 1 In this paper, we ?rst introduce a tree-based Connected Dominating Set protocol, namely Single-Initiator (SI). In the ?rst phase, SI distributively elects a unique initiator. In the second phase, SI grows a dominator tree from the initiator to form the CDS by using timers. While SI has advantage over the CDS protocols in [6,9?13] in terms of mobility handling, it relies on the availability of the network diameter to function correctly. To re- solve this issue, we introduce the second CDS protocol, namely Multi-Initiator (MI). Unlike SI, MI uses a set of initiators to grow a number of dominator trees and then connect the trees to form the CDS. Since MI uses SI to construct each dominator tree, it inherits the advantages of SI (e.g., mobility handling) and at the same time avoid the need of the global information. The simulation results of both static and mobile ad hoc scenarios validate that our tree-based CDS protocols construct and maintain CDS of competitive size with low overhead. An analytical model of the convergence time and the number of messages required by the SI and MI CDS protocols is presented and the results obtained from the analytical model match well with the results from the simulation. To improve the performance of the proposed tree-based CDS protocols, we further pro- posed two extensions, namely Fast-Convergence Dominator Tree Construction (FC-DTC) and Extended Mobility Handling (EMH). Unlike the original tree construction protocol used in SI and MI, the FC-DTC protocol does not rely on defer timers. It not only signi?cantly reduces the convergence time for CDS construction but also keeps all the advantages of the tree-based CDS protocols, such as small CDS, low overhead, and mobility handling mech- anism. On the other hand, EMH enables SI and MI to adapt to topology changes more e?ciently. It consists of two parts. The ?rst part, namely Height-Reduction (HR), focuses on shortening the recovery time of CDS mobility handling by dynamically adjusting the height of trees; the second part, namely Initiator-Reduction (IR), keeps the competitive size of CDS by controlling the number of initiators while doing mobility handling. Simu- lation results show that the two extensions, FC-DTC and EMH, successfully improve the performance of SI and MI in sense of the convergence time and mobility handling. 2 The rest of this paper is organized as follows. The existing CDS protocols for MANETs are reviewed in Chapter 2. The two tree-based CDS protocols as well as their performance evaluation are described in detail in Chapter 3. To improve the performance of the proposed protocols, two extensions are introduced and evaluated in Chapter 4. Chapter 5 concludes this paper. 3 Chapter 2 Related Works In this chapter, existing CDS protocols for MANETs are reviewed. Although Con- structing the minimum CDS is known to be NP-hard [5], a number of protocols have been proposed to approximate the minimum CDS. Considering the natures of MANETs, the cen- tralized CDS protocols [20?22] are not suitable, as they construct a dominating set under the assumption that the complete network topology is known. Therefore, in this paper, we focus on distributed CDS protocols. A number of distributed CDS protocols have been proposed for di?erent design goals. Depending on design goals, distributed CDS protocols are catego- rized into the minimum CDS protocols, energy-aware CDS protocols, k-CDS protocols, and Directed CDS protocols, and each of them are presented in the following sections. 2.1 Minimum CDS Protocols The most relevant to this paper is the minimum CDS protocols [6?11,13], which are to construct a small CDS based on localized information. Depending on the nature of the approach, these CDS protocols can be classi?ed into substraction-based and addition-based. 2.1.1 Substraction-based CDS Construction The substraction-based CDS protocol begins with the set of all nodes in the network, then systematically removes nodes to obtain the CDS. The best known CDS protocols in this category include Wu?s [6], Dai?s [7], and Stojmenovic?s [8] protocols. All of these CDS protocols consist of two phases. In the ?rst phase, each node collects k-hop neighboring information by exchanging messages with its one-hop neighbors. If a node ?nds that there is a direct link between any pair of its one-hop neighbors, it removes itself from the consideration 4 of the CDS. In the second phase, additional heuristic rules are applied to further reduce the size of the CDS. Wu?s protocol [6] uses Rule 1 and Rule 2 in its second phase, and Dai?s protocol [7] generalizes this second phase by Rule k, in which a node is removed from a CDS if all its neighbors are covered by a connected set of nodes in its k-hop neighbors and its id is the smallest than any node in the set. Note that Rule k requires k-hop neighboring information, and hence the larger value of k is the more control overhead the protocol incurs. Stojmenovic?s protocol [8] further reduces the size of CDS by applying two additional rules, the extended coverage condition and the key reversal techniques. The analysis and implementations presented in [23,24] show that protocols with one hop information results in a large CDS and using more than two hop incurs heavy communication overhead. Therefore, Wu?s, Dai?s, and Stojmenovic?s protocols with two hop information are practical. Since these protocols use two-hop neighbor information, a node needs at least two beacon periods to obtain the latest topology information before it can react to any topology change caused by nodal mobility. 2.1.2 Addition-based CDS Construction The addition-based CDS protocol starts from a subset of nodes (commonly discon- nected), then includes additional nodes to form the CDS. The most famous protocols in this category are Wan [9?11], Chen?s [12], and Li?s [13] protocols. In general, these tree protocols obtain the CDS by expending the Maximal Independent Set (MIS). Their protocols also have two phases. In the ?rst phase, the maximal independent set of the given network topology is constructed distributively by recursively selecting the nodes with the most neighbors locally. The nodes in the MIS become the skeleton of the CDS. Although nodes in the MIS are not connected, the distance between any pair of its complementary subsets is known to be exactly two hops away. Hence, in the second phase, a localized search is used to include additional nodes to connect the nodes in the MIS and form the CDS. The di?erence among [9?13] lies in how nodes in MIS are connected in the second stage (e.g., top-down or bottom-up fashion). 5 2.2 Energy-Aware CDS Protocols In the energy-aware CDS protocols [14,15], the criteria to determine the node in CDS include the energy. Such consideration is very important, as the power constraints is the primary concern in MANETs where nodes do not have power supply. Wu?s energy-aware protocols [14] extends the substraction-based CDS protocols [6,7]. In [14], the energy level of a node is used as a priority to eliminate it from a CDS instead of id. Note that a tie can be broken by id. As a result, nodes with higher energy level have more likely form a dominating set. Kim?s protocol [15] obtains a dominating set starting from a unique initiator. Each node in a tree set a defer timer inversely proportion to the number of uncovered nodes as well as energy level. By incorporating both the number of uncovered nodes and energy level, it prolongs the life time of a CDS with competitive size. 2.3 k-CDS Protocols The protocols in this category are to construct a fault-tolerant k-CDS [16?18], under the assumption that the original graph is k-connected. k-CDS is de?ned as the CDS in which the dominating set is still connected after the removal of any k?1 nodes from the graph, and each node has at least k neighbors in the CDS. In other words, there exist at least k- connected paths through dominating set between any two nodes. Dai?s k-CDS protocol [16] again obtains a CDS by eliminating unnecessary nodes from k-CDS. A node is removed from the dominating set if there exist k independent paths between any pair of nodes in its neighbors. id is used to avoid simultaneous node removal from the dominating set. Li?s k-CDS protocol [17,18] obtains by expending a MIS. First, it generate 1-connected CDS by using an addition-based protocol such as [9], and this 1-CDS is a skeleton of k-CDS. In the second phase, additional nodes are selected to make the CDS k-connected. 6 2.4 Directed CDS Protocols The protocols in this category are for a special hardware setting, where each node in a netowork has di?erent transmission range and is equipped with a directional antenna. Yang?s protocol [19] creates a directional CDS in an arbitrary directed gprah, which is assumed to be strongly connected. Similar to the original substraction-based CDS protocols [6?8], Yang?s protocol[19] obtains adirected CDSbyeliminatingunnecessary nodes and froma dominating set. In the ?rst phase Node Coverage Condition (NCC) is used in which a node is removed from the CDS if any pair of absorbant and dominating neighbors is connected. In their work, the source node of the link is de?ned as an absorbant neighbor for the destination node, and the destination node of the link is de?ned as a dominating neighbor for the source node. In the second phase, Edge Coverage Condition (ECC) is employed where an edge is removed from the subset of edges if there exists a replacement path between the source and sink nodes of the edge. Furthermore, the authors proposed the sector optimization mechanisms to minimize the number of switch-on sectors of directional antennas by adjusting the angle of sectors, and the topology control technique to minimize the transmission power. 2.5 Metrics to Evaluate CDS Protocols Although di?erent types of CDS protocols have di?erent design goals, there are several common metrics to evaluate CDS protocols. The most important metric is the size of CDS. This is because that a small size of CDS generally reduces the size of routing table or decreases the number of retransmissions. This not only alleviates the storage and communication overhead of routing protocols, but also improves the delivery rate and delay. Second, the convergence time to create a CDS is crucial to the availability of a virtual backbone. A MANET frequently experiences topology changes due to nodal mobility. CDS protocols should converge quickly as soon as possible in order to accommodate nodal mobility. Third, a dominating set is desirable to be calculated with less control overhead. A large amount of 7 tra?c to construct and maintain a CDS causes to poor routing performance. Finally, CDS protocols must be able to adapt to topology changes due to nodal mobility or power-o?. Since it takes long time to execute a whole process to reconstruct a CDS when a CDS is corrupted, protocols are required to locally recover corruption of the CDS. 8 Chapter 3 Tree-Based CDS Construction Protocols 3.1 The Basic Design The idea of our proposed protocols is based on a simple greedy strategy: To obtain a smaller dominating set, a node with more neighbors should be included in the set. To reduce the communication overhead, we propose the uses of defer timers in our distributed CDS protocols. By appropriately setting the defer timer at each node, nodes with more neighbors will have higher probability to be included in the CDS. Generally speaking, our proposed tree-based CDS protocols consist of three phases: i) initiator election; ii) tree construction; and iii) tree connection, as illustrated in Algorithm 1. In the initiator election phase, a number of initiators are elected distributively. This is achieved by letting the local minimum among -hop neighbors to be initiators. In the tree construction phase, starting from each initiator, nodes utilize the defer timer to generate disjoint dominator trees. The defer timer is set inversely proportion to the number of uncovered neighbors in order to give higher priority to nodes with more uncovered nodes. In the tree connection phase, additional nodes are identi?ed to connect the disjoint dominator trees. Each initiator collects the information of its neighboring trees from leaf nodes in its tree, and then sends a control message to a border node to connect trees. The initiators, the dominator trees, as well as the nodes that connect the trees altogether form the CDS. Depending on how many initiators are elected, two di?erent ?avors of the tree-based CDS protocols, namely Single-Initiator (SI) and Multi-Initiator (MI), are presented in this paper. We assume each node to have a unique id value, such as its MAC address. In the proto- cols, a node is always in one of the four possible states, i.e., uncovered, covered, dominator, and dominatee. Similar to what is de?ned in IEEE 802.11 wireless LAN speci?cation [25], 9 Algorithm 1 Tree-Based CDS Protocol Skeleton 1: Initiator Election 2: /* Initiators are localized elected */ 3: Tree Construction 4: /* Each initiator grows a dominator tree independently */ 5: Tree Connection 6: /* Additional nodes are included to connect disjoint trees */ each node periodically broadcasts a beacon to its neighbors every beacon period. We assume a node?s beacon contains a number of ?xed-length ?elds, including a type, the node?s id, a color value, the node?s current state, the node?s initiator id, and the node?s dominator id. The announce in the subsequent sections is a beacon with distinct type values. Before the protocol starts, each node sets its initiator id to INIT0, its state to uncovered, and the color value to 0. The additional notations used in the subsequent discussion are summarized in Table 3.1. 3.2 The SI Tree-Based CDS Protocol If the network size (i.e., network diameter) is known in advance, a unique initiator can be elected distributively in the initiator election phase within a prede?ned amount of time. Since only one initiator tree will be generated from the unique initiator at the end of the tree construction phase, the tree connection phase is not required. The subsequent subsections elaborate the initiator election and tree construction phases of the SI CDS protocol. 3.2.1 SI-Initiator Election Phase In the initiator election phase, the id of each node is used as the metric to determine the initiator. When the ITimer expires, if a node ?nds that its initiator id is INIT0, it ?rst sets its initiator to its own id. The reason why an initiator id is initialized by INIT0 is to deal with asynchronous environment where nodes act autonomously (see Lemma 1). When a node receives a beacon, it compares its initiator id with the initiator id in the beacon. If a node ?nds that its initiator id is larger than the beacon?s, it sets its initiator id to the 10 Table 3.1: De?nition of notations. Symbol De?nition id(i) the id of node i initiator(i) the initiator of node i state(i) the current state of node i dominator(i) the dominator of node i color(i) the current color value of node i ITimer the countdown timer for initiator election DTimer the countdown timer that determines if a node is a dominator CTimer the countdown timer that keeps track of a node?s dominator INIT0 a number larger than the id of any node InitMax the maximal value for ITimer Td the defer timer used for DTimer in the tree construction phase td the value used for CTimer to keep tracks of the presence of a node?s dominator Tmax the maximal value for DTimer nuc the number of uncovered neighbors the coe?cient used in the defer timer the threshold for color value between neighbors H(i;j) the number of hops between node i and j n the number of nodes in the network ninit the average number of initiators in the network S the size of the ?eld the network is deployed Diam the diameter of the network r the transmission range of a node ? the average number of neighbors d the average distance between two neighbors the range in number of hops to elect a local minimum 11 initiator id in the beacon. A node can switch its state, if it does not receive beacon from nodes with smaller id than it during the period of twice of InitMax. This duration is long enough so that at the end of the election phase the smallest id among all nodes will be propagated to all nodes in the network. Note that if a new node with the smaller id than any nodes in the network joins during the initiator election phase, it takes trice of InitMax (detail is shown in Lemma 1). Algorithm 2 describes the SI initiator election phase. Note that in the pseudo code, the initiator will send out announce beacon in every beacon period. The primary job ofannounce beacon includes detecting initiator failure and a disruption of a tree. For detecting initiator failure, announce beacons refresh the ITimer of other nodes which expires after twice of the InitMax beacon periods. Because announce beacons are originated from the initiator, if the initiator leaves the network or there is a partition in the network, the ITimer of some node will expire. In this case, the node will wait twice of the InitMax beacon periods to make sure the ITimer of every node in the network expires and restart the initiator election process. For detecting a disruption of a tree, each initiator keeps increasing color value by one at every beacon period and each node in its tree updates color value accordingly. The disconnection caused by nodal movement interrupts the propagation of announce message, which will eventually lead to large color di?erences. When a node receives a beacon signal from its dominator indicating a large color di?erence, it concludes that there is a disconnection with its dominator. 3.2.2 SI-Tree Construction Phase When ITimer expires, a node moves to the tree construction phase. When a node ?nds that it is the initiator, it immediately switches its state to dominator and its initiator to itself. When an uncovered node receives a beacon from a dominator neighbor for the ?rst time, it sets its dominator to that neighbor, its initiator to that neighbor?s initiator, switches 12 Algorithm 2 The SI initiator election 1: /* node i in the network executes the following: */ 2: INITIALIZATION: 3: initiator(i)?INIT0 4: state(i)?uncovered 5: color(i)?0 6: DTimer(i)??1 7: send out announce 8: ITimer(i)?InitMax, start ITimer(i) 9: 10: WHEN NODE i?s ITimer(i) EXPIRES: 11: if initiator(i) = INIT0 then 12: /* initial announcement */ 13: initiator(i)?i 14: send out announce 15: ITimer(i)?2?InitMax, start ITimer(i) 16: else if initiator(i) = i then 17: /* node i is an initiator */ 18: color(i)?color(i) + 1 19: send out announce 20: ITimer(i)?InitMax, start ITimer(i) 21: else if initiator(i)?= i then 22: /* re-elect initiator */ 23: state(i)?uncovered 24: initiator(i)?INIT0 25: color(i)?0 26: ITimer(i)?2?InitMax, start ITimer(i) 27: end if 28: 29: ON RECEIVING announce FROM NODE j: 30: if initiator(i) > initiator(j) then 31: initiator(i)?initiator(j) 32: else if initiator(i) = initiator(j) && color(i)?= color(j) then 33: color(i)?color(j) 34: send out announce 35: ITimer(i)?2?InitMax, start ITimer(i) 36: end if its state to covered, and sets a defer timer Td in inversely proportion to the number of its uncovered neighbors using Equation 3.1. Td = ? ??? ??? Tmax (nuc) if nuc?1 Tmax if nuc < 1 (3.1) As long as > 1, Equation 3.1 allows nodes with more uncovered neighbors to be given a smaller timer value, hence their defer timer will expire earlier. When a node?s defer timer expires, if the node still has uncovered neighbors, it switches its state to dominator to 13 cover them. Otherwise, it switches its state to dominatee. The number of uncovered nodes, denoted as nuc, can be learned from the beacon of one-hop neighbors. Note that the scale of Td is much larger than the beacon periods. Therefore, even if each node sends out its beacon asynchronously, our di?er timer scheme guarantees that a node with more uncovered neighbors has shorter timer in most of cases. At the end of the tree construction phase, all nodes will be in either dominator or dominatee state. The set of dominators forms a tree, which is referred to as the dominator tree. If there is only one initiator and the network is connected, the dominator tree will be the CDS for the entire network. We formalize the SI tree construction phase in Algorithm 3. In Algorithm 3, if a covered node i does not receive a beacon from i?s dominator for td beacon periods, it implies that i?s dominator has left and node i can then switch its state to uncovered. The assignment of td depends on the message error rate. For the 802.11 network, a small value such as 4 is su?cient [26]. CTiemer is used to track the dominator. A node updates CTimer if it receives a beacon from its dominator and the dominator is still in dominator state. If CTimer expires, it implies that its dominator leaves from the network. 3.2.3 Correctness of the SI Protocol In this subsection, we prove that the SI CDS protocol generates a CDS for a given network topology as long as the topology remains connected and stable for a period of time (the time required to construct a CDS) and the value of InitMax is larger than the network diameter. Lemma 1 A unique initiator is elected within 3InitMax in the asynchronous environment where nodes act autonomously, as long as InitMax is larger than the network diameter, Diam, and the topology is stable for a period of time. Proof 1 Assume the network consists of several nodes. Among them, node i has the smallest id. At time t1, some nodes in the network start the initiator election phase. Let node j joins the network at time t2 where t1 < t2. In the case of id(i) ? id(j), each of i?s neighbors 14 Algorithm 3 The SI tree construction 1: /* initiator i executes the following */ 2: NODE i IS ELECTED AS THE INITIATOR: 3: state(i)?dominator 4: color(i)?color(i) + 1 each time before node i sends out beacon 5: 6: /* node i executes the following when it receives a beacon */ 7: ON RECEIVING A BEACON FROM NODE j: 8: if state(j) = dominator then 9: if color(i) < color(j) then 10: color(i)?color(j) 11: end if 12: if state(i) = uncovered then 13: state(i)?covered, dominator(i) = j 14: CTimer(i)?td, start CTimer(i) 15: end if 16: if state(i) = covered||state(i) = dominatee then 17: if dominator(i) = j then 18: CTimer(i)?td, start CTimer(i) 19: end if 20: if ?i?s neighbor k,|color(j)?color(k)|> then 21: state(i)?dominator. dominator(i)?j 22: end if 23: end if 24: end if 25: 26: /* node i executes before it sends out a beacon */ 27: WHEN NODE i IS IN covered OR dominatee STATE: 28: if node i has no uncovered neighbor then 29: state(i)?dominatee 30: else if node i has at least one uncovered neighbor then 31: compute Td 32: if DTimer(i) > Td then 33: DTimer(i)?Td, start DTimer(i) 34: end if 35: end if 36: 37: WHEN NODE i IS IN dominator STATE: 38: if (node i has no covered neighbor) && (node i has at least one dominator neighbor) then 39: state(i)?dominatee, dominator(i)?one of node i?s dominator 40: DTimer(i)??1, stop Dtimer(i) 41: end if 42: 43: /* node i executes when a countdown timer expires */ 44: WHEN DTimer EXPIRES 45: if node i has uncovered neighbors then 46: state(i)?dominator 47: end if 48: 49: WHEN CTimer EXPIRES 50: state(i)?uncovered 15 will set its initiator to i after receiving a beacon from i. Their initiator value will stay as i because id(i) is the smallest among all nodes in the network. In the next round of beacon exchanges, i?s neighbors will propagate their initiator information further to reach nodes two hops away from i, which again will allow more nodes to set i as their initiator. This process is repeated until all nodes in the network set their initiator as i. At the end, node i is elected as the initiator as long as id(i) < id(j) for any additional new node j in InitMax +max 8k H(i;k)?InitMax +Diam?2InitMax. Thus, the above claim is true. In the case of id(i) > id(j), depending on the value of t2, we further break it into the following two subcases. If t2?t1+H(i;j), when node j receives announce from node i at the time t1+InitMax+ H(i;j), initiator(j) is still INIT0 because ITimer(j) has not yet expired. According to the protocol, id(i) < INIT0 so node j set its initiator id to be i?s. In other words, all nodes will set their initiator id to i?s within InitMax +max 8k H(i;k) < 2InitMax. Thus, the above claim is true. If t2 < t1+H(i;j), the ITimer of node j will expire before it receives announce from node i. In this case, node j will send out its own announce message to its neighbors. The nodes that received node i?s announce in the past override their initiator id to be j?s as id(i) > id(j). Node j will be elected as the initiator in t2?t1+Initmax+max 8k H(i;k) < 3InitMax. Therefore, the above claim is true. Lemma 2 A new initiator will be selected by the SI initiator election phase within bounded beacon periods if the original initiator leaves the network assuming the network remains connected and stable. Proof 2 From the pseudo code of the SI initiator election phase, we can see that the initiator will send out announce messages every InitMax beacon periods. Other nodes only forward announce messages if its initiator id is bigger than the initiator?s in the message or the color 16 value is di?erent. If the initiator is active, its color value will change every InitMax beacon periods, the refresh announce will keep the ITimer of other nodes from expiring. When the original initiator leaves the network, the ITimer of all nodes in the network will expire since no more refresh announce message is coming. After ITimer expires, each node sets all the information back to the initial value and the initiator election phase will start over again. According to Lemma 1, a unique initiator will once again be selected. In the following theorem, we prove that our SI protocol successfully obtains the con- nected dominating set for the given network topology. Theorem 3 If the network topology remains connected and stable for a period of time, the collection of all dominator nodes resulted from the SI protocol forms a connected dominating set for the entire network. Proof 3 We claim that if the network topology is connected and unchanged, eventually all the dominator nodes will form a dominating set and the induced graph is connected. We prove by induction on the number of nodes n. Induction base: when n = 1, the only node is the initiator. The initiator enters domina- tor after the initiator election phase, which is a connected dominating set. The above claim is true. Induction hypothesis: Assume when n = k?1, the CDS generated by the SI protocol covers all k?1 nodes. Let us denote the graph with k?1 nodes as G(k?1). Induction step: Now one additional node (node k) joins the network. Let us denote the resulting network as G(k). If one of node k?s neighbors is a dominator, the CDS covering G(k?1) will cover G(k) and is still a CDS. If none of k?s neighbors is a dominator, all neighbors of node k must be covered by some dominators in the CDS of G(k?1). According to the SI protocol, all node k?s neighbors will go through the covered state and set up the defer timer appropriately. When the ?rst one of them has its defer timer expires, that neighbor will enters the dominator state to cover node 17 k. After that, there will be no more uncovered node and therefore we have a dominating set. Since the new dominator node enters the dominator state from the covered state, it must have a dominator neighbor. (A node enters covered state only after it receives a beacon from a dominator neighbor.) In other words, the nodes in the dominating set, after including the additional dominator node, are still connected. The CDS covering G(k?1) plus the new dominator node will be the CDS covering G(k). If a node can not correctly obtain nuc due to the collisions, the size of CDS increases as nodes with fewer uncovered nodes set shorter timer. However, this never a?ects the correctness of the SI protocol. Thus, the SI protocol successfully obtains a CDS, as long as each node has bidirectional links between its neighbors. 3.2.4 SI Mobility Handling Now we would like to show that the SI protocol can adapt to nodal mobility. This is done by showing that the SI protocol successfully maintains the CDS under changes of the network topology, which are composed of the following four cases. 1. The initiator leaves the network. 2. A new node joins the network after the construction of the CDS. 3. A redundant dominator node switches to the dominatee state while still keeping the dominating set connected. 4. A dominator node leaves the network. Case 1 is proved in Lemma 2, and Case 2 is exactly the situation in Theorem 3. From the SI tree construction pseudo code, we can see that if a dominator does not cover any neighbor and has at least one dominator neighbor, it will switch its state to dominatee and set its dominator ?eld as the id of the dominator neighbor. By doing so, the total number 18 of dominator nodes is reduced and we have maintained the CDS under Case 3. This could happen after a series of node movements. Case 4 is handled by the color scheme. From the SI tree construction pseudo code, we can see that a node changes its color only after receiving a larger color value from a dominator neighbor. Since the initiator keeps increasing its color value, if the CDS is intact, the color di?erence of neighbor nodes should be very small. If the CDS is broken into disconnected segments, the segment that contains the initiator will keep increasing its color value while other segments will have the color value unchanged. When a node sees two neighbors with large color di?erence, it concludes that it is a border node between the disconnected segments and enters the dominator state. This process will continue until a CDS is reconstructed. The threshold value of color di?erence (i.e., ) is decided by the moving speed of nodes and the diameter of the network. It should be large enough to distinguish the node movement from network disconnections. 3.2.5 Example of the SI Protocol Figure 3.1 (a) shows the snapshot of a network topology. In Figure 3.1 (a), a dotted circle represents a node in uncovered state and a dotted line represents a link between two nodes. Figure 3.1 (b) shows the result of the initiator election phase. According to the SI protocol, node 1 is elected as the initiator, which is denoted by a shaded square. The neighbors of node 1 that are switched to the covered state are denoted by a double dotted circle. In the next beacon period, node 3 ?nds that it has no uncovered neighbor and then switches to the dominatee state, which is denoted by a circle in Figure 3.1 (c). At the same time, node 2 and 4 set their DTimer and start counting down the timer. Since node 2 has more uncovered neighbors, it has a shorter timer and its timer will expire before node 4?s. As shown in Figure 3.1 (d), node 2 will switch to the dominator state, which is denoted by a gray circle. After that, node 5 and 6 do not have uncovered neighbors and will then switch to the dominatee state. On the other hand, node 7 will start its own DTimer, as shown 19 in Figure 3.1 (e). While node 4 and 7 have the same number of uncovered neighbors, the timer of node 4 expires sooner as it started its DTimer earlier. When the timer of node 4 expires, node 4 will switch to the doinator state to cover node 8, as shown in Figure 3.1 (f). Afterwards, node 7 and 8 ?nd that they do not have uncovered neighbors and switch to the dominatee state, which is shown in Figure 3.1 (g). At the end, the collection of the initiator and dominators form a CDS for the whole network. (a) (b) (c) (d) (e) (f) (g) Figure 3.1: An example of the SI protocol. 3.3 The MI Tree-Based CDS Protocol As discussed in Section 3.2, the SI protocol is able to maintain CDS in the presence of topology changes. However, SI requires the knowledge of the diameter of the network to properly set up the InitMax. Although the network diameter may be estimated by the size of the region the network is deployed and the transmission range of a node, the estimation is not accurate. In addition, while SI is able to recover the CDS locally for most CDS breakdowns, the whole CDS will still have to be reconstructed from scratch should the unique initiator fail. A natural approach to resolve these issues is to elect multiple initiators. Each initiator generates a tree in exactly the same manner the SI protocol does. The tree construction 20 phase completes when all nodes are covered by dominators. This will produce several small disjoint trees and the union of these trees will form a dominating set. To obtain a CDS, we can simply include a few more nodes to connect these dominator trees. This is the basic idea of our Multi-Initiator CDS protocol (MI). If the CDS is constructed this way, the failure of an initiator will only a?ects the corresponding dominator tree. The other part of the CDS will remain intact. In the following sections, we explain how the initiator election phase and the tree connection phase of MI are accomplished e?ectively and distributively in detail. Note that the tree construction phase of MI is omitted because it is basically the same as that of SI described in Section 3.2.2. 3.3.1 MI-Initiator Election Phase The most intuitive idea to elect multiple initiators e?ectively and distributively is to let the local minimum be the initiators. By listening to beacons, a node obtains the ids of its one-hop neighbors without introducing additional messages. If a node ?nds that its id is the smallest among its one-hop neighbors, it sets itself as an initiator. The problem with this approach is that it may produce too many initiators. Given the average number of neighbors to be ?, each node has the opportunity to be an initiator with the probability 1?+1. Let n be the number of nodes uniformly distributed in a region of size S, and r be the transmission radius of each node, the average number of initiators ninit can be obtained by Equation 3.2. ninit = n?( 1? + 1)? S r2 (3.2) For instance, a network of 150 nodes with 150m transmission radius deployed in 1000m? 1000m area will have an average of 14 initiators. Too many initiators will consequently lead to a large CDS due to two reasons. First, all initiators will eventually be included as part of the CDS. Second, after each initiator generates a dominator tree, additional nodes will 21 be added to connect these trees. More initiators means more trees, and thus requires more nodes to connect them. To reduce the number of initiators, the local minimum among -hop neighbors can be elected as the initiators. As an example, to elect the local minimum among two-hop neighbors, each node can further encode the minimal id among its one-hop neighbors in its beacon. A node becomes an initiator only when its id equals to the minimal id of all its one-hop neighbors. With few rounds of beacon exchanges, the local minimum among two-hop neighbors will become the initiator. In this approach, no extra message is needed and the time to elect initiators is much shorter than the time required by the SI protocol in the initiator election phase. Using the same notations, the average distance between two neighbors, d, is obtained by Equation 3.3. d = ? r 0 2 x?x r2 dx = 2 3r (3.3) The average number of two-hop neighbors is n (r+d)2S . Therefore, the average number of initiators ninit can be obtained by 3.4. ninit = n?( 1n (r+d)2 S + 1 )? 925? S r2 (3.4) For instance, the network of 150 nodes with 150m transmission radius deployed in 1000m?1000m area now has an average number of 5 initiators. This signi?cantly reduces the possibility of a large CDS. The multi-hop local minimum idea can be extended to -hop. Since the average number of -hop neighbors is n (r+( 1) d)2S , the expected number of local minimum can be estimated by Equation 3.5. Note that when is equal or larger than the network diameter, only one initiator will be elected in the network and the protocol is reduced to SI. ninit = max{n?( 1n (r+( 1) d)2 S + 1 );1} (3.5) 22 0 5 10 15 20 0 5 10 15 20 0 10 20 30 40 50 60 70 80 Number of initiators CDS size The value of ? Theoretical value; number of initiators Simulation value; number of initiators Simulation value; CDS size Figure 3.2: The number of initiators and CDS size. Figure 3.2 shows the number of initiators and the CDS size with respect to the value of in the network of 150 nodes with 150m transmission radius deployed in 1000m?1000m area. As illustrated in Figure 3.2, the number of initiators as well as the size of CDS decrease as the value of increases. In the case = 2, the size of CDS is competitive and each dominator tree is small and easy to maintain. Therefore, in the rest of the paper, the value of the MI protocol is set to 2. 3.3.2 MI-Tree Connection Phase In this phase, additional nodes are included to connect neighboring dominator trees. If a node has a neighbor belonging to a di?erent initiator, it is referred to as a border node. To connect the dominator trees distributively, the most intuitive idea is to have all the border nodes turn into dominators. Although this approach does not introduce extra messages, it will create a very large CDS as there are possibly many border nodes between each pair of neighboring dominator trees. To limit the size of CDS, it is better that the root of a tree (i.e., initiator) determines what border nodes are utilized to connect the neighboring trees. Since an initiator does not know what neighboring trees it has with only the localized information, extra messages have to be introduced so that the initiator can collect such information from its border nodes. After the defer timer expires, if a node ?nds that it is a border node, it sends a message to its initiator which includes the initiator?s id of the 23 (a) (b) (c) Figure 3.3: An example of the MI protocol. neighboring tree. Figure 3.3 (a) depicts a snapshot of the network after the tree construction phase completes. For example, border node 3 belonging to the tree rooted at the initiator 1 ?nds that its neighbor 8 belongs to the tree rooted at the initiator 2 from node 8?s beacon. Node 3 then sends a message to node 5 containing the id of the initiator 2. Similarly, node 4, 7, 10, 8 sends a message to their initiator containing the initiator id of their neighboring tree. At the ?rst glance, this process seems to introduce many messages. However, when a dominator receives messages from the neighbors it covers about the neighboring trees, it only forwards one copy of the messages if the initiator id contained in the messages are the same. For instance, in Figure 3.3 (b), when node 5 receives messages from node 3 and 4 about the same neighboring dominator tree, it only forwards one copy of the message to its dominator node 1. By doing so, the number of messages can be controlled to O(n?m) where n is the number of nodes in the network and m is the number of neighboring dominator trees. When an initiator learns about its neighboring trees, it can then instruct only border nodes on a particular path to each of its neighboring trees to switch its state to dominator and connect to its neighboring trees. The border nodes that are used to connect the trees are referred to as the bridge nodes. Any metric can be used to elect bridge nodes among border nodes. In this paper, the node with the smallest id is elected as bridge nodes. For example, in Figure 3.3 (c), initiator 2 elects node 8 as a bridge because it has the smallest id among border nodes which connects the neighboring tree 1. Our CDS consists of the dominator nodes in the dominator trees and the bridge nodes that connect the trees. 24 If each initiator tries to connect to each of its neighboring dominator trees, it is likely that there will be two paths between each pair of neighboring dominating trees. In the worst case, at most four border nodes (two for each path) will become dominators. While having two paths between neighboring dominator trees may improve the degree of fault tolerance and system throughput, it will create a larger CDS. To limit the size of a CDS, an initiator makes a connection to a neighboring dominator tree only when the id of the initiator of the neighboring tree is smaller than its own. This roughly reduces the number of the bridge nodes by half. 3.3.3 Correctness of the MI Protocol Since MI is built on top of SI, most of the theorems in Section 3.2.3 directly apply to MI. The only additional issue is whether or not the tree connection phase can successfully connect the dominator trees. Theorem 4 If the network topology remains connected and stable for a period of time, the collection of all dominator nodes resulted from the MI protocol forms a connected dominating set for the entire network. Proof 4 After the initiator election and tree construction phases, a set of the disjoint dom- inator trees will be created. The nodes in these dominator trees together form a dominating set. The neighboring dominator trees will be at most three hops away. It is because if two neighboring dominator trees are more than three hops away, one of the nodes will not be covered by any dominator. For example, in Figure 3.4, the neighboring trees are distanced by four hops. This will leave node 5 to be uncovered. However, this situation should not happen because according to the tree construction protocol, when the DTimer of node 4 and 6 expire, they will ?nd node 5 as an uncovered neighbor and therefore one of them will switch to dominator to cover node 5. In other words, there will be at most two adjacent covered nodes and each of them has a di?erent initiator. These two border nodes will report to their 25 initiators and, according to MI, the initiator with larger id will then initiate the connection to the neighboring tree, providing that the network topology remains connected and stable for a period of time. Figure 3.4: An impossible case at the end of MI tree construction phase. 3.3.4 MI Mobility Handling In MI, each dominator tree is maintained in the same manner as SI. This allows the MI protocol to take advantage of the mobility handling capability of SI inside each of the dominator trees. The root of a dominator tree periodically broadcasts the announce message so that any topology changes due to mobility can be captured and handled in a timely fashion. Therefore, MI can naturally handle the four di?erent mobility cases mentioned in Section 3.2.4. However, since MI will create multiple dominator trees, there are additional mobility cases that involve more than one tree. Notice that most of these new cases can be considered as the combinations of the aforementioned four cases. For instance, if a dominator moves from one tree to another, it can be seen as Case 4 for the ?rst tree plus Case 2 for the second tree. Consequently, most of these new cases can be handled and resolved properly and locally with no change to the protocol. The only new case that needs to be addressed is when a bridge node leaves its dominator tree. Given a bridge node x, assume that it belongs to a dominator tree with root a, and x is used by a to connect to a neighboring dominator tree with the root b. Clearly, both a and b are initiators. If x leaves the tree, the dominator that covers x, say node p, will ?nd out after a couple of beacon periods. In this case, p will ?rst try to ?x the problem locally 26 by querying its neighbors if any of them has a neighbor belonging to the initiator b. If p receives a positive response from some of its border neighbors, it instructs one of them to switch to dominator state i.e., act as the new bridge between two trees. If p does not hear back from its neighbors for a period of time, it sends a message to the initiator a, which will send a tree-wide query down to all its border nodes looking for a possible connection to the neighboring dominator tree rooted at b. The responses sent back from the border nodes are handled similarly to the messages in the tree connection phase. Afterwards, if a receives some responses from the border nodes with neighbors belonging to initiator b, it instructs the border nodes on one of the paths to turn to dominators (i.e., become bridge nodes) to connect two trees. If a does not receive any response, that implies that the dominator tree rooted at b is no longer a neighboring dominator tree for a. In this case, nothing needs to be done by node a. It may seem odd that the dominating set will remain connected if nothing is done after the departure of a bridge node makes two neighboring dominator trees no longer neighbors to each other. If we regard each dominator tree as a big cluster, what the tree connection phase is doing is to create an edge between each neighboring clusters. If two clusters (trees) are no longer neighbors to each other, as long as the whole network remains connected, they should be connected via the other clusters (trees). If the departure of a bridge node partitions the network into components, it will be impossible to create a CDS for the network. However, the MI CDS protocol can still maintain a CDS inside each of the connected components and recover back to a single CDS when the components reconnect to each other. This feature is especially important for MANETs. 3.4 Simulations To evaluate the performance of SI and MI, we implement our protocols in C++ and ns-2 [27] along with the other CDS protocols, including Dai?s with two-hop neighboring 27 Table 3.2: Simulation parameters. Parameters Value Simulation area 1000m?1000m Number of nodes 100 to 450 Transmission range 150m 1 beacon period 1 second Tmax 100 beacon periods 1 InitMax 20 beacon periods 2 Mobility model WWP Percentage of mobile nodes 20% to 80% Node speed up to 5m=s Number of simulations 1000 Table 3.3: Parameters for ns-2. Parameters in ns-2 Value Propagation Two-Ray Ground MAC protocol IEEE 802.11 Data rate 2 Mbps Tra?c CBR Number of ?ows 5 concurrent ?ows Number of packet 5 packets/?ow Inter-arrival time 0.25 second Packet size 128-byte Percentage of mobile nodes 50% or 100% Number of simulations 100 information [7], Stojemenovic?s with two-hop neighboring information [8], and Wan?s [11]. In this section, the simulation results of di?erent CDS protocols are reported and analyzed. 3.4.1 Simulation Con gurations The network topology is randomly generated by placing nodes in a 1000m by 1000m square ?eld according to uniform distribution. If the generated network is partitioned, it is discarded and a new network topology is generated to ensure the connectivity of the whole network. The transmission range of a node is set to be 150m. Two di?erent network scenarios, static networks and mobile networks, are considered and simulated to evaluate the performance of CDS. For a given simulation con?guration, 1000 di?erent network topologies are generated. Static Networks - In this scenario, the average node density changes as we change the total number of nodes. The total number of nodes placed in the ?eld ranges from 100 to 450, which corresponds to the node density ranging from approximately 5 to 30 neighbors per node. For SI and MI, the Tmax and in the tree construction phase are set to be 100 beacon periods and 1. According to [26], the value of InitMax for SI is set to be 20 to accommodate beacon collisions. On the other hand, for MI is set to be 2, i.e., two-hop local minimum will be elected as initiators. 28 Mobile Networks - In this scenario, the average node density is set to be 10 neighbors per node, and some nodes are assumed to be mobile. The percentage of the mobile nodes ranges from 20% to 80% with speed up to 5m=s. The Weighed Way Point (WWP) [28] is adopted as our mobility model. In WWP, the weight of selecting next destination and pause time for a node depends on both current location and time. The value of weights is based on empirical data carried out on the University of Southern California?s campus [29]. For Dai?s, Stojmenovic?s, SI and MI, the corrupted CDS is recovered according to their mobility handling procedures when the topology changes. Each simulation lasts 1000 rounds of beacon periods. In the simulation, if the network topology is partitioned into disjoint connected components, CDS protocols maintain separate CDS within each component. In the limited mobility environment, 50% nodes are mobile with 5m=s, and in the high mobility environment, all nodes are mobile. In AODV with MI, only nodes in a CDS forward a route request (RREQ) packet. The propagation model used in ns-2 routing simulations is the two- ray ground model. IEEE 802.11 is used as the MAC layer protocol, and the data rate is 2 Mbps. For each network realization, 5 pairs of source and destination are randomly selected. A new pair of source and destination will be selected if they are not connected. Each source node generates constant bit-rate (CBR) tra?c ?ows to its destination simultaneously. Each CBR ?ow sends 5 consecutive packets of 128 bytes. The inter-arrival time of packets is set to be 0.25 second. To assess the performance of di?erent CDS protocols, ?ve metrics are used, including the size of CDS, the number of extra messages, the average tra?c, the convergence time, and the percentage of time CDS is alive. To assess the performance of routing with CDS protocols, three metrics are used, including delivery rate, end-to-end delay, and the number of RREQ packets. For MI, the messages in the tree connection phase and query/response messages in the mobility handling are counted as extra messages. For SI, all the information exchanged between nodes are done by beacons. For Dai?s and Stojmenovic?s protocols, beacons are considered as extra messages since the size of the beacon increases in proportion 29 to the node density and is too large when compared with the standard beacon frame. Each protocol changes the beacon frame format to include additional information. For SI, node id, state, color, and dominator id are included in the beacon. MI enlarges the beacon of SI to include the initiator id and the minimal id of one-hop neighbors. The beacon of Dai?s and Stojmenovic?s protocols include node id, state, marker, and the list of ids for one-hop neighbors. For Wan?s protocol, dominator id and color are added to the beacon. The extra bit in the beacon and the size of extra messages for each protocol are counted toward the tra?c (in bps) for CDS construction. The period of time for CDS protocols to complete is de?ned as the convergence time in the number of beacon intervals. For SI, the initiator election is assumed to be completed in 20 rounds of beacon intervals. For MI, the initiator election is done in two rounds of beacon intervals. For the mobile network scenario, the total amount of time CDS is valid divided by the total simulation period is de?ned as the percentage of time CDS is alive. 3.4.2 Simulation Results for Static Network Scenario In this subsection, the simulation results of di?erent CDS protocols in the static network scenario are presented. Figure 3.5 shows CDS size of di?erent protocols with respect to the node density. It is clear that SI consistently generates the smallest CDS and Dai?s consistently generates the largest CDS among all the protocols. Stojemenovic?s protocol creates a smaller CDS than that of Dai?s, but compared with SI and MI it generates a larger CDS. While it is proven that the size of Wan?s CDS is sub-optimal [9], the size of the CDS of MI is smaller than Wan?s and is very close (within few nodes) to SI. In addition, the CDS size in SI and MI remains constant when the node density increases. This suggests that SI and MI are scalable. Figure 3.6 demonstrates the number of extra messages with respect to the node den- sity. As illustrated in Figure 3.6, MI introduces only 30% of the number of extra messages introduced by Dai?s and Stojemenovic?s. Compared with Wan?s, MI reduces the number of 30 extra messages up to 60% when the node density ranges from 5 to 15 neighbors per node. As discussed in Section 3.2, SI does not introduce any extra message. 0 20 40 60 80 100 120 140 5 10 15 20 25 30 CDS size Number of neighbors Dai?sStojmenovic?s Wan?sSI MI Figure 3.5: CDS size. 0 2000 4000 6000 8000 10000 12000 14000 5 10 15 20 25 30 Number of messages Number of neighbors Dai?sStojmenovic?s Wan?sSI MI Figure 3.6: Number of messages. Figure 3.7 shows the average tra?c required for CDS construction with respect to the node density. Obviously, Dai?s and Stojmenovic?s protocols produce the largest tra?c, and the tra?c increases in proportion to the node density. This is because of the inclusion of the neighboring list in the beacon frame. For the other three protocols, the average tra?c is almost the same. It is interesting that for Wan?s and the MI protocols, even the number of messages increases in proportion to the number of neighbors as shown in Figure 3.6, the tra?c remains relatively constant to the node density. This implies that the tra?c is mostly dominated by the extra bits in the beacon. Figure 3.8 presents the convergence time with respect to the node density. As shown in Figure 3.8, the convergence time of SI and MI decreases quickly as the node density increases. This indicates that the convergence time of SI and MI is dominated by the time of the tree construction, in which a node in dense networks is likely to have more uncovered neighbors and will have a smaller defer timer. MI takes longer time to form CDS than SI. This is due to the additional time for the tree connection phase. 31 0 500 1000 1500 2000 5 10 15 20 25 30 Average traffic (bps) Number of neighbors Dai?sStojmenovic?s Wan?sSI MI Figure 3.7: Average tra?c (kbps). 0 50 100 150 200 250 300 350 400 5 10 15 20 25 30 Convergence time (beacon periods) Number of neighbors Dai?sStojmenovic?s Wan?sSI MI Figure 3.8: Convergence time. 3.4.3 Simulation Results for Mobile Network Scenario In this subsection, the simulation results of di?erent CDS protocols in the mobile net- work scenario are presented. Figure 3.9 illustrates the percentage of time that CDS is alive with respect to the percentage of mobile nodes. As can be seen in Figure 3.9, MI has the highest percentage of CDS alive time than other CDS protocols except when the percentage of mobile nodes is more than 60%. Although smaller CDS is generally more vulnerable to topology changes, MI shows excellent mobility adaptation compared with the other protocols. Only when the percentage of mobile nodes is greater than 65% the percentage of time CDS is alive of MI becomes slightly lower than that of Dai?s due to MI?s smaller CDS size. Stojmenovic?s protocol maintains a CDS for fewer percentage of time than MI and Dai?s. As pointed out in [9], the time complexity of mobility recovery at each node of Dai?s is as high as O(?2). While Stojmenovic?s protocol requires O(?) to maintain a CDS, it is vulnerable to nodal mobility as it further reduces the size of CDS than Dai?s protocol. Thus, Dai?s and Stojmenovic?s protocols take more time to recover than MI. SI has smaller percentage of CDS alive time than MI, Dai?s, and Stojmenovic?s. This is because of the possible failure of the unique initiator, which results in the reconstruction of the whole CDS from scratch. 32 Figure 3.10 shows the average CDS size with respect to the percentage of the mobile nodes. As illustrated in Figure 3.10, SI consistently produces the smallest CDS and Dai?s protocol consistently produces the largest CDS. The size of CDS by Stojmenovic?s protocol is larger than MI except when the percentage of mobile nodes is more than 60%. The average CDS size of MI is 5% to 35% higher than Wan?s. However, as can be seen in Figure 3.9, Wan?s protocol is vulnerable to the nodal mobility. 0 20 40 60 80 100 20 30 40 50 60 70 80 Percentage of time CDS is alive Percentage of the mobile nodes (%) Dai?sStojmenovic?s Wan?sSI MI Figure 3.9: Percentage of time CDS is alive. 0 20 40 60 80 100 120 140 20 30 40 50 60 70 80 Average CDS size Percentage of the mobile nodes (%) Dai?sStojmenovic?s Wan?sSI MI Figure 3.10: Average CDS size. Figure 3.11 presents the number of extra messages to maintain CDS with respect to the percentage of the mobile nodes. As illustrated in Figure 3.11, MI requires a low number of extra messages to maintain CDS. The number of messages is only 20% of that of Wan?s and 8% of Dai?s. This demonstrates that MI can handle topology changes e?ciently with only a small number of messages. Figure 3.12 shows the average tra?c required at each node to maintain CDS with respect to the percentage of the mobile nodes. As can be seen in Figure 3.12, the average tra?c of MI and SI are at least 50% lower than that of Dai?s and Stojmenovic?s. Compared with Wan?s and SI, MI has slightly higher tra?c, but the di?erence is not signi?cant. This is because the beacon in MI is slightly larger than that of Wan?s and SI. As we have pointed out in Section 3.4.2, the tra?c is mostly dominated by the extra bits in the beacon frame rather than the extra messages. This again is validated by Figure 3.11 and Figure 3.12. 33 0 20000 40000 60000 80000 100000 120000 140000 160000 20 30 40 50 60 70 80 Number of messages to maintain CDS Percentage of the mobile nodes (%) Dai?sStojmenovic?s Wan?sSI MI Figure 3.11: Number of messages to maintain CDS. 0 200 400 600 800 1000 20 30 40 50 60 70 80 Average traffic to maintain CDS (bps) Percentage of the mobile nodes (%) Dai?sStojmenovic?s Wan?sSI MI Figure 3.12: Average tra?c to maintain CDS. Figure 3.13 depicts the packet delivery rate with respect to the node density. In the case of sparse networks, AODV with MI results in lower delivery rate than the original AODV, AODV with Dai?s, and AODV with Stojmenovic?s. This is because in such low node density the network is often not connected, which leads to the failure of route discovery. However, when the average number of neighbors is more than 15, AODV with MI results in higher delivery rate than AODV, and has the similar delivery rate with AODV with Dai?s and AODV with Stojmenovic?s. Figure 3.14 presents the end-to-end delay with respect to the node density. As can be seen in Figure 3.14, the delay of AODV increases in proportion to the number of neighbors, while that of AODV with MI remains stable. Compared with AODV with Dai?s and AODV with Stojmenovic?s, the delay of AODV with MI is only 50%. It implies that in networks with high density AODV, and AODV with Dai?s and AODV with Stojmenovic?s incur more collisions and take longer time to discover a route. Figure 3.15 shows the number of RREQ packets with respect to the node density. It is clearly shown that AODV with MI introduces lower number of RREQ packets. This is because that only nodes in the CDS forward RREQ packets. On the other hand, AODV with Stojmenovic?s incurs more number of RREQ packets than AODV with MI due to lower disconnections of a CDS. Considering the results presented in Figure 3.13, 3.14, and 3.15, we 34 0 0.2 0.4 0.6 0.8 1 5 10 15 20 25 30 Delivery rate Number of neighbors AODV; Limited MobilityAODV; High Mobility AODV w/Dai?s; Limited MobilityAODV w/ Dai?s; High Mobility AODV w/ Stojmenovic?s; Limited MobilityAODV w/ Stojmenovic?s; High Mobility AODV w/ MI; Limited MobilityAODV w/ MI; High Mobility Figure 3.13: Delivery rate. 0 1 2 3 4 5 6 5 10 15 20 25 30 Delay (second) Number of neighbors AODV; Limited MobilityAODV; High Mobility AODV w/ Dai?s; Limited MobilityAODV w/ Dai?s; High Mobility AODV w/ Stojmenovic?s; Limited MobilityAODV w/ Stojmenovic?s; High Mobility AODV w/ MI; Limited MobilityAODV w/ MI; High Mobility Figure 3.14: End-to-end delay. are con?dent that CDS constructed by our proposed protocols improve routing performance and reduce routing overhead in MANETs. 0 10000 20000 30000 40000 50000 60000 70000 5 10 15 20 25 30 Number of request packets per flow Number of neighbors AODV; Limited MobilityAODV; High Mobility AODV w/ Dai?s; Limited MobilityAODV w/ Dai?s; High Mobility AODV w/ Stojmenovic?s; Limited MobilityAODV w/ Stojmenovic?s; High Mobility AODV w/ MI; Limited MobilityAODV w/ MI; High Mobility Figure 3.15: Number of RREQ packets. 3.5 Analysis In this section, an analytical model to analyze the convergence time and number of messages that SI and MI require during CDS construction is presented and validated. Our analytical models estimate the average performance when nodes are randomly placed in a network in the uniformly distribution. 35 3.5.1 Analytical Model The initiator election phase of SI and MI completes in 2InitMax and beacon periods, respectively. We ?rst consider the convergence time of SI. The convergence time of SI in the tree construction phase is the product of the number of hops from the initiator to the edge of the tree and the average defer time. To formulate this, let us denote the width and height of the simulation region as lx and ly, respectively. The number of hops, denoted by h, will be the distance from the initiator to the edge of the tree divided by the average distance between two nodes. Assuming lx = ly, and S = lx?ly, then the average value of h can be computed by Equation 3.6. h = ? l2x + l2y 2d = 3?2S 4r (3.6) The average defer time of a node is Tmax divided by the average number of uncovered neighbors nuc. Let CA and CB be the coverage area of two neighboring nodes A and B, and d be the distance between them, the additional area that B forwards a message from node A is|CB\CA|= r2?|INTC(r;d)|, where INTC(r;d) is the intersection of two circles of radius r with their centers separated by d. INTC(r;d) = 4 ? r d=2 ?r2?x2dx (3.7) Thus, the average additional coverage area is ? r 0 2 x( r2?INTC(r;x)) r2 dx?0:41 r 2 (3.8) Therefore, the average number of uncovered nodes is 0:41?, where ? is the average number of neighbors. In addition, a node at the edge of the tree will wait Tmax number of beacon intervals before it changes its state to dominatee. Finally, the convergence time of SI is approximately 36 2InitMax + (h?1)? Tmax0:41? + Tmax (3.9) The duration of the tree construction phase in MI can be calculated in the similar fashion. In the case of multi-initiator, the number of hops from an initiator to the edge of its tree, hmi, is hmi = r=dn init r2=S = 32? Sn init r2 (3.10) For the tree connection phase in MI, a border node without any uncovered neighbor will wait Tmax number of beacon intervals before it sends a message to its initiator. The time required for the tree connection phase is bounded by 2hmi +1. Hence, the convergence time of MI is the total time spent on the initiator election phase, the tree construction phase, and the tree connection phase, and can be computed as + (hmi?1)? Tmax0:41? + Tmax + 2hmi + 1 (3.11) MI does not introduce extra messages except in the tree connection phase. In the tree connection phase, all nodes except initiators forward messages from their children as many times as the number of neighboring trees to their initiator. Thus, the number of message required for MI to construct CDS is 0:41??ninit?1n init ?n (3.12) 3.5.2 Theoretical and Simulation Result Comparisons In this subsection, the analytical model are validated by comparing with our simulation results. Figure 3.16 demonstrates the convergence time of SI and MI with respect to the aver- age number of neighbors. The convergence time decreases in proportion to the number of 37 0 50 100 150 200 250 300 350 400 5 10 15 20 25 30 Convergence time (beacon periods) Number of neighbors SI theoretical valueSI simulation value MI theoretical valueMI simulation value Figure 3.16: Convergence time. 0 1000 2000 3000 4000 5000 6000 5 10 15 20 25 30 Number of messages Number of neighbors MI theoretical valueMI simulation value Figure 3.17: Number of messages. neighbors because the defer timer in the tree construction phase decreases in proportion to the number of uncovered nodes. As can be seen in Figure 3.16, the theoretical model and simulation results are very close to each other. Figure 3.17 shows the number of messages with respect to the average number of neigh- bors. In the simulation, the control messages in the tree connection phase are traced. Note that since SI forms only one dominator tree, there will be no control messages for the tree connection. As can be seen in Figure 3.17, analytical model again provides a very accurate estimation. 38 Chapter 4 Extensions of Tree-Based CDS Protocols In this chapter, we introduces two optimization techniques to improve the performance of the tree-based protocols proposed in Chapter 3. To reduce the convergence time of the SI and MI protocols, Fast-Convergence Dominator Tree Construction (FC-DTC) is proposed in Section 4.1. For e?cient mobility handling, Extended Mobility Handling (EMH) is intro- duced in Section 4.2 4.1 Fast-Convergence Dominator Tree Construction 4.1.1 The Issue of the Tree Construction As described in Chapter 3, the tree-based CDS protocols are suitable for MANETs as they tend to result in smaller CDS, introduce less communication overhead, and adapt to nodal mobility. However, they still su?er from slow convergence due to the use of defer timers in their tree construction phase. In the rest of this chapter, the protocol used in the tree construction phase in SI and MI is referred as Timer-Based Dominator Tree Construction (TB-DTC). In TB-DTC, when a node ?nds that one of its neighbors joins the CDS, it sets a defer timer inversely proportional to the number of uncovered neighbors and joins the CDS only if it still has at least one uncovered neighbor when its timer expires. Recall that the defer timer is calculated using Equation 3.1. Since nodes with more uncovered neighbors clearly have a shorter timer, they have a higher probability that at least one of its neighbors will still be uncovered when its timer expires, hence a higher probability to be included in the CDS. The convergence time of dominator tree construction is bounded by h?Tmax, where h is the number of hops from an 39 initiator to the edge of its dominator tree. When the network contains some long chains of nodes, it will take a long time for the protocol to converge. For instance, Figure 4.1 shows the worst scenario of TB-DTC. In Figure 4.1, the shaded square represents an initiator, a shaded circle represents a dominator, an unshaded circle represents a dominatee, and a dotted circle represents a covered or uncovered node. An arrow represents the relationship between the dominator and its dominatee (e.g., node 1 is the dominator of node 2), and a dotted line represents a link between two nodes. Suppose that in the initiator election phase, node 1 is elected as the initiator. Then, node 1 switches its state to dominator and covers node 2. On receiving beacons from its neighbors, node 2 learns that its only uncovered neighbor is node 3. Assuming Tmax = 100 beacon periods, node 2 sets its timer, Td, to 100 beacon periods. This process is repeated until all nodes turn to either dominator or dominatee as illustrated from the top to the bottom in Figure 4.1. The convergence time will be 300 beacon periods for this small chain with only 4 nodes. When the network density is low, this phenomenon will happen frequently, which will result in long CDS convergence time for TB-DTC. Figure 4.1: An example of a tree construction. Another problem of TB-DTC is its poor scalability. In Equation 3.1, Td has an upper bound of Tmax. This is because in case of extremely high network density TB-DTC can not distinguish which node has more uncovered neighbors if each node has more than Tmax number of neighbors. 40 The intuitive solution to slow convergence times is to use a di?erent defer timer function, such as a log timer. If the log timer is upper bounded by a smaller value, the tree construction phase can be completed more quickly. However, this change will make the TB-DTC protocol even less scalable as more nodes will be mapped to the same defer timer value. Hence, it is preferable that the fast tree construction protocol does not rely on defer timers. Therefore, in this section, we proposed a novel dominator tree construction protocol, namely Fast Convergence Dominator Tree Construction (FC-DTC) protocol. By using FC- DTC instead of TB-DTC, the convergence time of the SI and MI CDS protocols can be signi?cantly improved. In the next subsection, we elaborate on the FC-DTC protocol. 4.1.2 Fast Tree Construction Algorithm In addition to Table 3.1, the notations used in this chapter are given in Table 4.1. Just like TB-DTC, in FC-DTC each node encodes its initiator id, state, and dominator id into the beacon frame. In addition, each node also encodes the number of its uncovered nodes into its beacon. A node can be in either dominator, dominatee, covered, or uncovered state. At the beginning, all nodes are uncovered. Similar to what is de?ned in the IEEE 802.11 standard [25], each node periodically broadcasts its beacon. Through the exchange of beacons, a node learns the information of its one-hop neighbors, such as their state and nuc. Table 4.1: De?nition of notations for FC-DTC and EMH. Symbol De?nition N(i) The set of one-hop neighbors of node i N[i] N(i)?{i} flag(i) Set to TRUE if node i is a candidate dominator depth(i) The number of hops from initiator(i) to i 41 Aftertheinitiatorelectionphase, eachinitiatorimmediatelyswitchesitsstatetodominator and sets its initiator to itself. When an uncovered node receives the ?rst beacon from a dom- inator neighbor, it sets its dominator to this neighbor, its initiator to the neighbor?s initiator, and then switches its state to covered. By listening to beacons, each node knows how many uncovered neighbors it has. A boolean variable flag is used at each node to track if a covered node should be switched to dominator state. If a node has the highest value of nuc among its one-hop neighbors, which are in covered state, and belongs to the same dominator tree for at least two beacon periods, it sets its flag to be 1 and waits for one beacon period. In the next beacon period, if it still has the highest value of nuc and it has at least one uncovered node, it switches to dominator state. Otherwise, it sets its flag back to 0 and stays in covered state. In other words, if a node has the highest value of nuc for two beacon periods, it changes its state to dominator. If two nodes have the same value of nuc, the tie can be broken by their id. During the process, if a node does not have any uncovered neighbor, it switches to dominatee state. Eventually, all nodes will switch their state to either dominator or dominatee. The pseudo code of this procedure is given in Algorithm 4. FC-DTC constructs a dominator tree much quicker than TB-DTC. For instance, in Figure 4.1, after node 1 is elected as the initiator, in one beacon period node 2 will know it has the largest nuc from the beacons. It then waits one additional beacon period and switches to dominator state. This process is repeated until all nodes are either dominator or dominatee, which will take only 7 beacon periods. FC-DTC achieves the following two design goals. First, no matter how many neighbors each node has, FC-DTC guarantees that the node with the most uncovered nodes among one- hop neighbors becomes a dominator earlier. This will reduce the size of the CDS. Second, although FC-DTC extends the beacon frame by 8 bits, it still uses only one-hop localized information and does not introduce any extra control messages. In short, FC-DTC reduces the convergence time of CDS construction while at the same time keeping the advantages of TB-DTC. 42 Algorithm 4 FC-DTC pseudo code 1: /* Node i executes following */ 2: Initialization: 3: initiator(i)??1 4: state(i)?uncovered 5: doinator(i)??1 6: nuc(i)??1 7: flag(i)?0 8: Node i detects itself as initiator: 9: initiator(i)?i 10: state(i)?dominator 11: On receiving beacon from dominator node j: 12: if initiator(i) =?1 then 13: initiator(i)?init(j) 14: dominator(i)?j 15: state(i)?covered 16: end if 17: Node i in covered state ?flag(i) = 0: 18: if i = candidate(i;initiator(i);N(i)) then 19: flag(i)?1 20: wait one beacon period 21: end if 22: Node i in covered state ?flag(i) = 1: 23: if i = candidate(i;initiator(i);N(i)) then 24: if ?j?N(i)?state(j) = uncovered then 25: state(i)?dominator 26: else 27: state(i)?dominatee 28: end if 29: else 30: flag(i)?0 31: end if 32: /* return id with the highest value of nnc among N[i] */ 33: Procedure candidate(i, init(i), N(i)): 34: MaxID?i 35: MaxV alue?nuc(i) 36: for all j in N(i) do 37: if initiator(j) = initiator(i)?state(j) = covered?MaxV alue < nuc(j) then 38: MaxID?j, MaxV alue?nuc(j) 39: end if 40: if state(j) = covered?initiator(j) = initiator(i)?MaxV alue = nuc(j)?id(j) < id(i) then 41: MaxID?j, MaxV alue?nuc(j) 42: end if 43: end for 44: return MaxID 4.1.3 Mobility Handling Since the initiator election and the tree connection phases are not changed, the SI and MI protocols that incorporate our FC-DTC protocol can deal with nodal mobility in the 43 similar manner as the original SI and MI protocols. According to Section 3.2.4 and 3.3.4, the corruption of CDS is caused by one or more of the following ?ve di?erent nodal mobility cases. 1. The initiator leaves the network. 2. A new node joins the network after the construction of the CDS. 3. A redundant dominator node switches to the dominatee state while still keeping the dominating set connected. 4. A dominator node leaves the network. 5. A bridge node leaves its dominator tree. It is clear that Case 1, 3, and 5 can be handled in exactly the same manner as the original SI and MI protocols. As discussed in Section 3.2.4, Case 4 can be handled by the color scheme because the color scheme does not rely on timers. Therefore, the only case that needs to be addressed is when a new node joins a dominator tree after the tree is constructed. When a new node, say node j, joins a dominator tree, all its neighbors are in either dominator or dominatee state. If node j can ?nd at least one dominator neighbor, it can be covered by one of its dominator neighbors. If node j cannot ?nd a dominator neighbor, all the dominatee neighbors of node j?s can switch to covered state. Then, the dominator tree construction phase begins again for node j and its neighbors. The pseudo code for handling this mobility case is given in Algorithm 5. Algorithm 5 Additional pseudo code for mobility handling 1: /* Node i executes following */ 2: Node i in dominatee state: 3: if ?j?N(i)?state(j) = uncovered then 4: state(i)?covered 5: flag(i)?0 6: end if 44 4.2 Extended Mobility Handling 4.2.1 The Issue of the Mobility Handling While SI and MI can successfully adapt to topology changes, they su?er from two issues. First, the CDS recovery time may increase after a period of time. It is because when new nodes join the network, the height of the dominator tree may increase. When a bridge node moves away from the network, in the worst case, the initiator of one of the disconnected trees needs to assign a new bridge node by exchanging control messages between the initiator and nodes in the boundary area. The time to complete this recovery process is in proportion to the height of the tree. Note that during the recovery process, the dominating set will not be connected. Hence, to ensure the CDS to be available for a longer period of time, it is important that the height of the dominator tree to be small. Figure 4.2: Original Topology I. Figure 4.3: Mobility handling of MI on Topol- ogy I. For instance, in Figure 4.2, a snapshot of a MANET and its connected dominating set are illustrated. In the ?gure, a square represents an initiator, a shaded circle is a dominator, a circle is a dominatee, and a triangle is a bridge node. The CDS is formed by the initiators, the dominators, and the bridge nodes. An arrow between two nodes indicates their domina- tor/dominatee relationship (e.g., node 3 is the dominator of node 5) and a solid line between two bridge nodes means they are neighbors to each other. Assume that the bridge node 11 runs out of power, according to MI, its dominator, node 10, will ?rst look for an alternative bridge to connect to the neighboring tree. When node 10 fails to ?nd such a node, it sends 45 a control message to its initiator, node 1. Then, node 1 designates a new bridge node, node 12, to connect to the neighboring tree. The control message will traverse 9 hops before a new bridge node can connect to the neighboring tree. This message traversal is illustrated in Figure 4.3. Another issue of SI and MI mobility handling is the possibility of excessive initiators. When a connected network component breaks into multiple pieces due to mobility, each piece will ?nd at least one initiator. When these pieces are merged, all these initiators will become part of the CDS. In addition, since each initiator generates a dominator tree, more initiators imply more trees, thus more bridge nodes will be needed to connect these trees. This further increases the size of CDS. For example, in Figure 4.4, the topology is separated into three pieces, and each piece has its own initiator. After the change of topology, as shown in Figure 4.5, initiator 2 and 3 move to the proximity of the dominator tree rooted at initiator 1. To connect all these dominator trees, the MI protocol will include node 9, 10, and 14 into CDS. Figure 4.4: Original Topology II. Figure 4.5: Mobility handling of MI on Topol- ogy II. 4.2.2 Extended Mobility Handling Algorithms To address the aforementioned issues, we propose the Extended Mobility Handling (EMH) algorithm on top of SI and MI. EMH incorporates two procedures, namely Height- Reduction (HR) and Initiator-Reduction (IR). The following subsections elaborate on each of these procedures. 46 Height-Reduction To control the height of a dominator tree, a node in the tree needs to know its depth, i.e., the minimum number of hops between its initiator and itself. Recall that in both SI and MI to learn the state of the neighboring node, the state of a node is encoded in the beacon. By adding an extra depth ?eld in the beacon, the depth of a node can be obtained without introducing extra messages. When a node receives a beacon from its dominator, it learns and updates its own depth, then encodes its depth plus one to the depth ?eld of its beacon before transmitting it. If a node ?nds a dominator neighbor which belongs to the same dominator tree and the depth of the dominator is smaller than its current dominator, it changes its dominator and updates its depth to reduce the height of the tree. The new dominator is able to know that the node becomes its child in the next beacon period. A dominator node which child changes its dominator may no longer have children. If this situation occurs, the dominator changes it state to dominatee. The pseudo code of the Height-Reduction procedure is given in Algorithm 6. Algorithm 6 Height-Reduction 1: /* Node i executes following */ 2: On receiving a beacon from j 3: /* changes its dominator */ 4: if state(j) = dominator?depth(j) < depth(domintor(i)) then 5: dominator(i)?j 6: depth(i)?depth(j) + 1 7: end if 8: /* eliminate unnecessary dominator */ 9: if state(i) = dominator then 10: if ?j?N(i);dominator(j)?= i then 11: state(i)?dominatee 12: end if 13: end if The following demonstrates how Height-Reduction works for the topology in Figure 4.2. Assume dominator node 3 is also a direct neighbor of node 8. After receiving beacons from node 3, node 8 knows depth(3) = 1 and depth(7) = 2. As node 3 is a dominator and closer to the initiator, node 8 changes its dominator to node 3 and updates its depth. Then, since dominator node 7 no longer has children, it changes its state to dominatee. Similarly, 47 Figure 4.6: Topology with Height-Reduction Figure 4.7: Mobility handling of MI after Height-Reduction assume dominator node 5 is a direct neighbor of node 10. After node 10 ?nds that node 5 has a smaller depth, according to Height-Reduction it will switch its dominator to node 5 and update its depth. After a few beacon periods, the original dominator tree rooted at node 1 in Figure 4.2 will be optimized as shown in Figure 4.6. Now again assume that the bridge node 11 in Figure 4.6 runs out of power. As illustrated in Figure 4.7, the loss of the bridge node is handled in the same manner as in Figure 4.3. As the height of the tree in Figure 4.7 is smaller than that of Figure 4.3, the mobility handling for bridge node 11 can be done more e?ciently. While MI needs to send 9 messages to recover the CDS, MI with Height-Reduction needs only 5. Initiator-Reduction Since each initiator generates a tree, reducing the number of initiators is equivalent to reducing the number of trees. To reduce the number of trees, the small dominator trees can be merged to the large neighboring trees. In essence, if a tree is small, most likely its initiator will also be a boundary node, i.e., the initiator has some neighbor belonging to a di?erent tree. If an initiator ?nds such a neighbor and its id is larger than the initiator id of the neighbor, it changes its state to dominator, its initiator id, and updates its depth. The reason to merge the tree with larger initiator id to the one with smaller initiator id is to avoid the situation that both initiators of neighboring trees try to merge to the other tree simultaneously. After a dominator tree becomes a part of another tree, the children of the 48 merged initiator need to change their state. On receiving beacon from its dominator, if a node detects its dominator?s initiator id is di?erent from its initiator id, it updates its initiator id and depth accordingly. Notice that after Initiator-Reduction procedure is completed, an initiator will not have any neighbor belonging to a di?erent tree. This guarantees that the tree of each initiator including the bridge nodes will be at least two hops in height. The pseudo code of the Initiator-Reduction procedure is provided in Algorithm 7. Algorithm 7 Height-Reduction 1: /* Node i executes following */ 2: /* merge small dominator trees */ 3: if Node i is an initiator then 4: dominator(i)?j 5: initiator(i)?initiator(j) 6: depth(i)?depth(j) + 1 7: if state(j) = dominatee then 8: state(j)?dominator 9: end if 10: end if 11: /* On receiving a beacon from j (change initiator id) */ 12: if dominator(i) = j?initiator(j)?= initiator(i) then 13: initiator(i)?initiator(j) 14: depth(i)?depth(j) + 1 15: end if Figure 4.8 shows how Initiator-Reduction works for the topology in Figure 4.4. Recall that in Figure 4.5, initiator 2 and 3 move to the boundary area. Node 2 is still an initiator, and it has two neighbors 9 and 12 that associate with other initiators. According to the pseudo code, node 2 will change its initiator id and update its depth. Afterwards, node 9 ?nds that node 2 become its child, so it is no longer a bridge node. When Node 11 and 14 ?nd that their dominator changed its initiator id, they will update their initiator id and depth. As can be seen, the size of CDS by the MI protocol?s mobility handling in Figure 4.5 is 8, while by MI with Initiator-Reduction in Figure 4.8 is reduced to 7. 4.3 Simulations To evaluate the performance of SI with FC-DTC, MI with FC-DTC, SI with EMH, and MI with EMH, we implement our protocols in C++ along with the other CDS protocols, 49 Figure 4.8: Topology with Initiator- Reduction. including Dai?s [7], Wan?s [9], the original SI, and the original MI protocols. Notice that the original SI and MI protocols use TB-DTC in the dominator tree construction phase. We do not include Stojmenovic?s protocol [8], as it has similar results to Dai?s. In this section, the simulation results of di?erent CDS protocols are reported and analyzed. 4.3.1 Simulation Con gurations The performance of FC-DTC and EMH is assessed in the static network scenario and mobile network scenario, respectively. The simulation con?gurations and evaluation metrics are the same as Section 3.4.1. Hence, we only describe the con?gurations of FC-DTC and EMH. For FC-DTC, in addition to the original SI and MI, both SI with FC-DTC and MI with FC-DTC enlarge the beacon by adding nuc (8 bits per beacon). For EMH, the only one di?erence is in the beacon frame format. To implement EMH in SI and MI, we extend the beacon of SI and MI by adding depth (4 bits per beacon). 4.3.2 Simulation Results for Static Network Scenario Figure 4.9 shows the CDS size of di?erent protocols with respect to the network density for di?erent protocols. It is clear that SI with FC-DTC consistently generates the smallest CDS and Dai?s consistently generates the largest CDS among all the protocols. In addition, except Dai?s protocol, the size of CDS generated by other protocols is not sensitive to the 50 0 20 40 60 80 100 120 140 5 10 15 20 25 30 CDS size Number of neighbors Dai?sWan?s SI w/ TB-DTCMI w/ TB-DTC SI w/ FC-DTCMI w/ FC-DTC Figure 4.9: CDS size. 0 50 100 150 200 250 300 350 400 5 10 15 20 25 30 Convergence time (beacon period) Number of neighbors Dai?sWan?s SI w/ TB-DTCMI w/ TB-DTC SI w/ FC-DTCMI w/ FC-DTC Figure 4.10: Convergence time. density of the network. In the case of high network density, SI with FC-DTC and MI with FC-DTC result in a slightly smaller size for CDS than the original SI and MI protocols. This is because FC-DTC guarantees that nodes with more uncovered neighbors will be switched to dominator ?rst. This suggests that FC-DTC is more scalable than TB-DTC. While it has been proven that the size of Wan?s CDS is suboptimal [9], both SI with FC-DTC and MI with FC-DTC are able to generate CDS with a smaller size. Figure 4.10 presents the convergence time with respect to the network density for di?er- ent protocols. As shown in Figure 4.10, SI with FC-DTC and MI with FC-DTC signi?cantly reduce the convergence time compared with the original SI and MI protocols. Even at the high network density, SI with FC-DTC and MI with FC-DTC reduce the convergence time by more than 80% compared with their respective TB-DTC counterpart. While the conver- gence time of the original SI and MI protocols are a?ected by the network density, that of SI with FC-DTC and MI with FC-DTC is stable. Notice that MI with FC-DTC creates CDS faster than even Dai?s protocol. Compared with Wan?s protocol, the convergence time of SI with FC-DTC and MI with FC-DTC is almost the same. Figure 4.11 demonstrates the number of extra messages with respect to the network density for di?erent protocols. As illustrated in Figure 4.11, MI with FC-DTC introduces only 30% of the extra messages that Dai?s does. Compared with Wan?s, MI with FC-DTC 51 reduces the number of extra messages up to 60% when the network density ranges from 5 to 15 neighbors per node. Note that both SI with TB-DTC and SI with FC-DTC does not introduce any extra message since they do not have the tree connection phase. Figure 4.12 shows the average tra?c incurred by the CDS construction with respect to the network density for di?erent protocols. Obviously, Dai?s protocol introduces the largest tra?c, and the tra?c increases in proportion to the network density. This is because of the inclusion of the neighboring list in the beacon frame. For the other ?ve protocols, the average tra?c is almost the same. Note that SI with FC-DTC and MI with FC-DTC enlarge the beacon frame of the original SI and MI protocols by only 8 bit. It is interesting that even though the number of messages for MI with FC-DTC, MI with TB-DTC, and Wan?s protocols increase in proportion to the number of neighbors as shown in Figure 4.11, the tra?c remains relatively constant to the network density. This implies that the tra?c is mostly dominated by the extra bits in the beacon frame. 0 2000 4000 6000 8000 10000 12000 14000 5 10 15 20 25 30 Number of messages Number of neighbors Dai?sWan?s MI w/ TB-DTCMI w/ FC-DTC Figure 4.11: Number of messages. 0 500 1000 1500 2000 5 10 15 20 25 30 Average traffic (bps) Number of neighbors Dai?sWan?s SI w/ TB-DTCMI w/ TB-DTC SI w/ FC-DTCMI w/ FC-DTC Figure 4.12: Average tra?c (bps). 4.3.3 Simulation Results for Mobile Network Scenario Figure 4.13 illustrates the percentage of time CDS is alive with respect to the percentage of the mobile nodes. As can be seen in Figure 4.13, MI with EMH almost always has the highest percentage of CDS alive time than other CDS protocols. Although smaller CDS 52 is generally more vulnerable to topology changes, MI with EMH shows excellent mobility adaptation compared with the other protocols. Only when the percentage of mobile nodes is greater than 70% the percentage of CDS alive time of the MI-EMH becomes slightly lower than that of Dai?s due to MI with EMH?s smaller CDS size. As pointed out in [9], the time complexity of mobility recovery at each node of Dai?s is as high as O(?2), where ? is the average number of neighbors. Thus, Dai?s protocol takes more time to recover than MI with EMH. SI with EMH also improves the percentage of CDS alive time by at least 10% compared with SI. This clearly demonstrates that EMH is capable of prolonging the time CDS is available to MANETs. Figure 4.14 shows the average CDS size with respect to the percentage of the mobile nodes. As illustrated in Figure 4.14, SI and SI with EMH consistently produce the smallest CDS and Dai?s protocol consistently produces the largest CDS. While the size of CDS gen- erated by MI increases slowly in accordance with the percentage of mobile nodes, that of MI with EMH is stable. This is because, by merging trees MI with EMH keeps the number of initiators as a constant, and consequently reduce the CDS size. In general, it is desirable that the size of the CDS is as small as possible for MANETs. From Figure 4.13 and Figure 4.14, MI with EMH can quickly adapt to topology changes while keeping CDS size competitive. 0 20 40 60 80 100 20 30 40 50 60 70 80 Percentage of time CDS is alive Percentage of the mobile nodes (%) Dai?sSI MISI w/ EMH MI w/ EMH Figure 4.13: Percentage of time CDS is alive. 0 20 40 60 80 100 120 140 20 30 40 50 60 70 80 Average CDS size Percentage of the mobile nodes (%) Dai?sSI MISI w/ EMH MI w/ EMH Figure 4.14: Average CDS size. 53 Figure 4.15 presents the number of extra messages to maintain CDS with respect to the percentage of the mobile nodes. As illustrated in Figure 4.15, SI does not introduce any extra message. MI with EMH introduces less than 25% of extra messages of Dai?s. In addition, the numbers of extra messages of MI and SI with EMH are roughly the same and are at most 10% of that of Dai?s. Compared with MI, MI with EMH introduces more messages. The same can be said to SI and SI with EMH. Unlike the other protocols, the number of extra message created by MI with EMH decreases as the percentage of the mobile nodes increases. This is because IR can better reduce the number of initiators when more initiators move to the boundary area. By introducing few extra control messages, MI with EMH and SI with EMH become highly adaptive to topology changes, as shown in Figure 4.13. Figure 4.16 shows the average tra?c required at each node to maintain CDS with respect to the percentage of the mobile nodes. As can be seen in Figure 4.16, the average tra?c of Dai?s protocol is at least twice as much as that of any other protocol. The protocol incorporates EMH has slightly higher tra?c than the one without EMH, but the di?erence is not signi?cant. This is primarily because in EMH the beacon is 4 bit larger to include the depth value. Figure 4.15 and Figure 4.16 suggest that the tra?c is mostly dominated by the extra bits in the beacon frame. 0 20000 40000 60000 80000 100000 120000 140000 160000 20 30 40 50 60 70 80 Number of messages to maintain CDS Percentage of the mobile nodes (%) Dai?sSI MISI w/ EMH MI w/ EMH Figure 4.15: Number of messages to maintain CDS. 0 200 400 600 800 1000 20 30 40 50 60 70 80 Average traffic to maintain CDS (bps) Percentage of the mobile nodes (%) Dai?sSI MISI w/ EMH MI w/ EMH Figure 4.16: Average tra?c to maintain CDS. 54 4.4 Analytical Model for The Convergence Time In this section, an analytical model to analyze the convergence time that SI with FC- DTC and MI with FC-DTC require during CDS construction is presented and validated. The one-hop neighbors of an initiator requires one beacon period to become dominator or dominatee, as they have enough information to initiate the protocol during the initiator election phase. Afterwards, it takes two beacon periods to advance one hop from the initiator. Thus, the convergence time in the dominating tree construction of FC-DTC can be calculated by 2?(h?1) + 1 for SI and 2?(hmi?1) + 1 for MI, respectively. In the initiator election phase, it takes at least beacon periods to elect a -hop local minimum. For the original SI protocol, is set to be 20, so h = 3 p2S 4r , where S is the simulation region and r is the transmission range. Hence, SI with FC-DTC, the convergence time is obtained by Equation 4.1. + 2(h?1) + 1 = + 2h?1 (4.1) As described in Section 3.5, the convergence time in the tree connection phase for the original MI protocol is 2hmi +1. And, is set to be 2, so hmi = 32? Sninit r2. Here, ninit is the number of local minimum. When = 2, ninit is approximately 925 ? S r2. Therefore, MI with FC-DTC, the convergence time is estimated by Equation 4.2. + 2(hmi?1) + 1 + 2hmi + 1 = + 4hmi (4.2) Figure 4.17 depicts the values calculated from our analytical model and the results obtained from the simulation. As can be seen in Figure 4.17, our analytical model provides a very accurate estimation in terms of the convergence time for SI with FC-DTC and MI with FC-DTC. Remark: Note that so far we have assumed a node can collect the updated information from all its neighbors within one beacon period. In reality, since the transmission of beacons is 55 0 50 100 150 200 250 300 5 10 15 20 25 30 Convergence time (beacon period) Number of neighbors SI w/ FC-DTC Theoretical ValueSI w/ FC-DTC Simulation Value MI w/ FC-DTC Theoretical ValueMI w/ FC-DTC Simulation Value Figure 4.17: Convergence time. generally done without coordination, there may be collisions between beacon transmissions. To accommodate this issue, each node can wait for a ?xed number of beacon periods, say Twait, after it ?nds it has the highest value of nuc. In this case, the convergence time of the dominator tree construction for SI with FC-DTC and MI with FC-DTC will be (Twait+1)hmi and (Twait+1)(hmi?1)+1, respectively. This increases the convergence time slightly, but the result will still be much faster than SI with TB-DTC and MI with TB-DTC. For instance, when Twait = 3, the convergence time is less than 50 beacon periods for SI with FC-DTC and less than 33 beacon periods for MI with FC-DTC. Even with the highest network density (30 neighbors per node), the convergence time is at least 165 beacon periods for SI with TB-DTC and at least 124 for MI with TB-DTC. 56 Chapter 5 Conclusions While the existing CDS protocols are successful in constructing a CDS of small size, they miss a number of key features that are important in mobile ad hoc networks. In this paper, we introduce two tree-based CDS protocols, namely Single-Initiator (SI) and Multi-Initiator (MI), that not only create a CDS of competitive size with low overhead but also address the shortcomings of the existing protocols. SI utilizes timers to distributively construct and maintains CDS in the presence of changes of network topology. Built on top of SI, MI requires minimum localized information to construct and maintain CDS e?ciently. The performance of the SI and MI protocols are veri?ed by C++ and ns-2 simulations under static/mobile network settings, and an analytical model. Both performance assessments provide very close results, which establishes the validity of our simulations. In addition to the two tree-based CDS protocols, we introduced two extensions to im- prove the performance of SI and MI, namely Fast-Convergence Dominator Tree Construction (FC-DTC) and Extended Mobility Handling (EMH). FC-DTC reduces the convergence time required in constructing a dominator tree by avoiding the use of di?er timers. On the other hand, EMH successfully reduces the recovery time and keeps a CDS competitive size by controlling the size of dominator trees and the number of initiators during mobility pro- cess. Simulation results show that SI and MI incorporating FC-DTC and EMH signi?cantly improve the performance of the original SI and MI protocols. 57 Bibliography [1] J. Blum, M. Ding, A. Thaeler, and X. Cheng, ?Connected Dominating Set in Sensor Networks and MANETs,? Handbook of Combinatorial Optimization, pp. 329?369, 2005. [2] J. Wu, ?Extended Dominating-Set-Based Routing in Ad Hoc Wireless Networks with Unidirectional Links,? IEEE Transaction on Parallel Distributed Systems, vol. 13, no. 9, pp. 866?881, 2002. [3] J. Cartigny, D. Simplot, and I. Stojmenovic, ?Localized Minimum-Energy Broadcasting in Ad-hoc Networks,? in Proceedings IEEE Conference on Computer Communications (INFOCOM), Mar. 2003, pp. 2210?2217. [4] A. Helmy, S. Garg, P. Pamu, and N. Nahata, ?CARD: A Contact-based Architecture for Resource Discovery in Ad Hoc Networks,? ACM Baltzer Mobile Networks and Ap- plications (MONET), vol. 10, no. 1, pp. 99?113, 2004. [5] M. R. Garey and D. S. Johnson, Computers and Intractability; A Guide to the Theory of NP-Completeness, 1990. [6] J. Wu and H. Li, ?On Calculating Connected Dominating Set for E?cient Routing in Ad Hoc Wireless Networks,? in Proceedings of the 3rd International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications (DIALM), Aug. 1999, pp. 7?14. [7] F. Dai and J. Wu, ?An Extended Localized Algorithm for Connected Dominating Set Formation in Ad Hoc Wireless Networks,? IEEE Transaction on Parallel Distributed Systems, vol. 15, no. 10, pp. 908?920, 2004. [8] D. Simplot-Ryl, I. Stojmenovic, and J. Wu, ?Energy-E?cient Backbone Construction, Broadcasting, and Area Coverage in Sensor Networks,? Handbook of Sensor Networks: Algorithms and Archtectures, pp. 343?379, 2006. [9] P. J. Wang, K. M. Alzoubi, and O. Frieder, ?Distributed Construction of Connected Dominating Set in Wireless Ad Hoc Networks,? in Proceedings of IEEE Conference on Computer Communications (INFOCOM), Apr. 2002, pp. 141?149. [10] K. M. Alzoubi, P.-J. Wan, and O. Frieder, ?Message-Optimal Connected Dominating Sets in Mobile Ad Hoc Networks,? in Proceedings of the 3rd ACM International Sympo- sium on Mobile Ad Hoc Networking and Computing (MobiHoc), Jun. 2002, pp. 157?164. 58 [11] P.-J. Wan, L. Wang, and F. Yao, ?Two-Phased Approximation Algorithms for Minimum CDS in Wireless Ad Hoc Networks,? in Proceedings of the International Conference on Distributed Computing Systems (ICDCS), Jun. 2008, pp. 337?344. [12] X. Cheng, M. Ding, D. H. Du, and X. Jia, ?Virtual backbone construction in multihop ad hoc wireless networks: Research articles,? Wireless Communications and Mobile Compututing, vol. 6, no. 2, pp. 183?190, 2006. [13] Y.Li, M.T.Thai, F.Wang, C.-W.Yi, P.-J.Wan, andD.-Z.Du, ?Ongreedyconstruction of connected dominating sets in wireless networks,? Wireless Communicationss and Mobile Compututing, vol. 5, no. 8, pp. 927?932, 2005. [14] J. Wu, F. Dai, M. Gao, and I. Stojmenovic, ?On Calculating Power-Aware Connected Dominating Sets for E?cient Routing in Ad Hoc Wireless Networks,? IEEE/KICS Journal of Communications and Networks, vol. 4, no. 1, pp. 59?70, 2002. [15] B. Kim, J. Yang, D. Zhou, and M.-T. Sun, ?Energy-Aware Connected Dominating Set Construction in Mobile Ad Hoc Networks,? in Proceedings of the 14th IEEE Interna- tional Conference on Computer Communications and Networks, Oct. 2005, pp. 229?234. [16] F. Dai and J. Wu, ?On Constructing k-Connected k-Dominating Set in Wireless Net- works,? in Proceedings of the 19th IEEE International Parallel and Distributed Process- ing Symposium (IPDPS), 2005. [17] Y. Wu, , F. Wang, M. T. Thai, and Y. Li, ?Constructing Algorithms for k-Connected m-Dominating Sets in Wireless Sensor Networks,? in Proceedings of the IEEE Military Communications Conference (MILCOM), Oct. 2007, pp. 29?31. [18] Y. Wu and Y. Li, ?Construction Algorithms for k-Connected m-Dominating Sets in Wireless Sensor Networks,? in Proceedings of the 9th ACM International Symposium on Mobile Ad Hoc Networking and Computing (Mobihoc), May 2008. [19] S. Yang, J. Wu, and F. Dai, ?E?cient Directional Network Backbone Construction in Mobile Ad Hoc Networks,? IEEE Transaction on Parallel Distributed Systems, vol. 19, no. 12, pp. 1601?1613, 2008. [20] D. S. Hochbaum, Ed., Approximation Algorithms for NP-hard Problems. PWS Pub- lishing Co., 1997. [21] S. Guha and S. Khuller, ?Approximation Algorithms for Connected Dominating Sets,? Algorithmica, vol. 20, no. 4, pp. 374?387, 1998. [22] B. S. Baker, ?Approximation algorithms for NP-complete problems on planar graphs,? J. the ACM, vol. 41, no. 1, pp. 153?180, 1994. [23] S. Basagni, M. Mastrogiovanni, A. Panconesi, and C. Petrioli, ?Localized Protocols for Ad Hoc Clustering and Backbone Formation: A Performance Comparison,? IEEE Transactions on Parallel and Distributed Systems, vol. 17, no. 4, pp. 292?306, 2006. 59 [24] S. Basagni, M. Mastrogiovanni, and C. Petrioli, ?A Performance Comparison of Pro- tocols for Clustering and Backbone Formation in Large Scale Ad Hoc Networks,? in Proceedings IEEE Conference on Mobile Ad-hoc and Sensor Systems, Oct. 2004, pp. 70?79. [25] ?IEEE 802.11b Standard,? http://standards.ieee.org/getieee802/ download/802.11b-1999.pdf. [26] D. Zhou, M.-T. Sun, and T. Lai, ?A Timer-based Protocol for Connected Dominating Set Construction in IEEE 802.11 Multihop Mobile Ad Hoc Networks,? in Proceedings of International Symposium on Applications and the Internet (SAINT), Jan. 2005, pp. 2?8. [27] ?The Network Simulator (ns-2),? http://www.isi.edu/nsnam/ns/. [28] W.-J. Hsu, K. Merchant, H.-W. S., C.-H. Hsu, and A. Helmy, ?Weighted Waypoint Mobility Model and its Impact on Ad Hoc Networks,? ACM SIGMOBILE Mobile Com- puting and Communications Review, vol. 9, no. 1, pp. 59?63, 2005. [29] ?Mobilab: Community-Wide Library of Mobility and Wireless Networks Measure- ments,? http://nile.usc.edu/MobiLib/. 60