Local algorithms for dominating and connected dominating sets of unit disk graphs with location aware nodes Conference Paper uri icon

abstract

  • Many protocols in ad-hoc networks use dominating and connected dominating sets, for example for broadcasting and routing. For large ad hoc networks the construction of such sets should be local in the sense that each node of the network should make decisions based only on the information obtained from nodes located a constant number of hops from it. In this paper we use the location awareness of the network, i.e. the knowledge of position of nodes in the plane to provide local, constant approximation, deterministic algorithms for the construction of dominating and connected dominating sets of a Unit Disk Graph (UDG). The size of the constructed set, in the case of the dominating set, is shown to be 5 times the optimal, while for the connected dominating set 7.453∈%2b∈ε the optimal, for any arbitrarily small ε>∈0. These are to our knowledge the first local algorithms whose time complexities and approximation bounds are independent of the size of the network. © 2008 Springer-Verlag Berlin Heidelberg.

publication date

  • 2008-01-01