785

6

785

6

34

1

2

34

1

2

1

2

34

1

2

34

5

1

678

2

34

5

1

678

2

34

## Figure 1: Coloring of the grid with 8 colors

doubling. The network-related problems which are solved include metric embeddings [12, 14], distance labeling and compact routing [26], and nearest neighbor search [15]. The doubling dimension has been introduced in [12], however, a similar notion has already been used in [3].

The concept of network decomposition has been intro- duced in [5] in which the authors present a deterministic O(f(n)^{c}) time algorithm for computing an (f(n)^{c}, f(n)^{c})- decomposition, where c is a constant and where f(n) =

n^{√log log n/ log n }

.

## They also showed how their decomposi-

tion algorithm can be used in order to obtain determin- istic O(f(n)^{c}) algorithms for finding a maximal indepen-

dent set or a (

+

1) coloring in G. Building on earlier re-

sults in [6], it was shown in [21] that every graph G admits a (log n, log n)-decomposition. Algorithm [21] gives a ran- domized distributed algorithm with expected running time O(log^{2 }n) that computes such a decomposition. The deter- ministic algorithm of [5] was subsequently improved in [23], yielding a (g(n)^{d}, g(n))-decomposition in time O(g(n)^{d}),

where d is a constant and g(n) = n^{√1/ }^{log n }

. For unit disk

graphs, the fastest known (randomized) algorithm to com- pute a (O(1), O(1))-decomposition is to first compute a MIS in expected time O(log n) using an algorithm by Luby [22], the nodes are then clustered around the MIS nodes which become cluster leaders.

3.

# GLOBAL COORDINATES

In the literature, wireless ad-hoc and sensor networks are often modeled as unit disk graphs. Additionally, many al- gorithms assume that nodes have access to coordinate in- formation [1, 2, 19, 27, 28]. Nodes obtain this information from a positioning system such as GPS either directly or by running a distributed positioning algorithm. In this sec- tion, we will have a closer look at this graph model and give a simple construction of a (O(1), O(1))-decomposition. We assume that nodes know their coordinates in the Euclidean plane and that two nodes can communicate directly if and only if their distance is at most 1 (UDG model). Note that this means that nodes “see” a common global coordinate system.

Having a global coordinate system enables to compute a decomposition as described in Section 1. We use the stan- dard trick of partitioning the plane by a grid into square cells of side length 1/^{√}2. Each square cell defines a cluster of nodes. By checking their coordinates, nodes can decide in which cell they are located and hence to which cluster they belong. Since the length of the diagonal of a single square cell is 1, the induced graph of each cluster is a clique.

A proper coloring of the cluster graph is obtained by glob- ally coloring the grid such that no two cells whose distance is less than 1 are colored with the same color. Figure 1 shows how this can be achieved using 8 colors. Hence, by assigning each cluster the respective color, we obtain a (1, 8)- decomposition.

It is of course not surprising that global information such as coordinates helps devising fast distributed algorithms. The possibility of computing a (O(1), O(1))-decomposition from UDG coordinates alone indicates the power of such coordinate information. It means that unit disk graph coor- dinates suffice to compute essentially everything which can be computed locally in a constant number of rounds. In the next section, we will see that the described simple algorithm for computing a network decomposition can even be applied in some form in absence of global information.

4.

# FRACTIONAL COVERING AND PACK- ING PROBLEMS

In most cases, it is not realistic to assume that there is a positioning system which nodes could use to obtain coor- dinate information. In this section, we show that the main ideas of the last section can be adapted in order to solve many interesting problems in the case where no global in- formation is present.

We again consider the standard unit disk graph model. In addition to knowing the direct neighbors, we merely as- sume that nodes can sense the distances to their neighbors. By exchanging this information for a few rounds, this en- ables the nodes to build up a local coordinate system. That is, distances between nodes can be used to compute angles and to learn about the geometry of the neighborhood. It is however not possible to align all those local coordinate sys- tems, each node has its own local view. Assume for instance that we want to compute a small dominating set. In the presence of global coordinates, we can compute a network decomposition as described in the last section. Choosing one node per cluster (e.g., the node with the largest ID) gives a dominating set which is only by a constant factor larger than an optimal dominating set. If we try to do this with the local coordinate systems, the clusters of different local system will be different. Hence, also the selected nodes (dominating set) will be different in each coordinate system. This can lead to disastruous solutions and does not yield a non-trivial approximation.

While all the local coordinate systems inherently differ from each other, the set of all possible global coordinate sys- tems is the same at every node. Hence, if we computed all dominating sets corresponding to the clusterings of all (in- finitely many) different global coordinate systems, all nodes would come up with their local part of the same (multi- )set of different global dominating sets. It is of course still not possible to globally select one of these dominating sets. However, if we assign values 0 and 1 to non-dominators and dominators, respectively, it is possible to compute the av- erage over all dominating sets. This does not result in a global dominating set, however it does result in a common fractional dominating set solution, that is, we solve the nat- ural LP relaxation of the dominating set problem.

In the following, we present an explicit and more general algorithm for the above intuitive description. We consider fractional covering and packing problems. A covering prob-