Efficient Localized Protocols to Compute Connected Dominating Sets for Ad Hoc Networks

Mobile Ad Hoc networks (MANETs) are gaining increased interest due to their wide range of potential applications in civilian and military sectors. The self-control, self-organization, topology dynamism, and bandwidth limitation of the wireless communication channel make implementation of MANETs a challenging task. Vehicular Ad Hoc Networks (VANETs) are a special kind of MANETs that aims at providing communications among vehicles on the roads. The fact that a vehicle´s movement is predictable and constrained by the road trajectory is a feature that gives VANETs their distinction. The Connected Dominating Set (CDS), a.k.a. virtual backbone or spine, has been proposed to facilitate routing, broadcasting, and establishing a dynamic infrastructure for distributed location databases in MANETs and VANETs. Minimizing the CDS cardinality simplifies the network abstracted topology, allows for using shorter routes, and reduces the number of required retransmissions in broadcasting scenarios. Due to the fact that minimizing the CDS size is NP-complete problem, approximation algorithms and heuristics have been used to reduce the CDS size. Localized CDS creation algorithms proved to run fast and to generate light signaling overhead. Computationally, the simplest localized CDS creation algorithms is Wu and Li algorithm; however, this algorithm is characterized by a relatively high signaling overhead. To reduce the signaling overhead of Wu and Li algorithm, a modified version of the algorithm is proposed; this version is built on the assumption that utilizing the location information of network members reduces the signaling overhead. In this paper, we claim that utilizing location information does not guarantee signaling overhead reduction and it may increase it; moreover, we introduce some modifications that guarantee overhead reductMobile Ad Hoc networks (MANETs) are gaining increased interest due to their wide range of potential applications in civilian and military sectors. Th- - e self-control, self-organization, topology dynamism, and bandwidth limitation of the wireless communication channel make implementation of MANETs a challenging task. Vehicular Ad Hoc Networks (VANETs) are a special kind of MANETs that aims at providing communications among vehicles on the roads. The fact that a vehicle´s movement is predictable and constrained by the road trajectory is a feature that gives VANETs their distinction. The Connected Dominating Set (CDS), a.k.a. virtual backbone or spine, has been proposed to facilitate routing, broadcasting, and establishing a dynamic infrastructure for distributed location databases in MANETs and VANETs. Minimizing the CDS cardinality simplifies the network abstracted topology, allows for using shorter routes, and reduces the number of required retransmissions in broadcasting scenarios. Due to the fact that minimizing the CDS size is NP-complete problem, approximation algorithms and heuristics have been used to reduce the CDS size. Localized CDS creation algorithms proved to run fast and to generate light signaling overhead. Computationally, the simplest localized CDS creation algorithms is Wu and Li algorithm; however, this algorithm is characterized by a relatively high signaling overhead. To reduce the signaling overhead of Wu and Li algorithm, a modified version of the algorithm is proposed; this version is built on the assumption that utilizing the location information of network members reduces the signaling overhead. In this paper, we claim that utilizing location information does not guarantee signaling overhead reduction and it may increase it; moreover, we introduce some modifications that guarantee overhead reduction. we conduct extensive simulations to investigate the correctness of our claim, and we study the impact of using location information on the run time and the size of the CDS.ion. we conduct extensive simulations to investigate the correctness of our claim, and we study the impact of using loc