X hits on this document





2 / 9

which are simpler on UDGs than on general graphs. On the one hand, it can be shown that all non-isolated nodes of a UDG form a 2-approximation for minimum vertex cover. On the other hand, it is shown in [17] that Ω(plog n/ log log n) rounds are needed on general graphs.

The goal of this paper is to improve this situation by giv- ing fast algorithms for all of the discussed problems for the UDG and interesting generalizations of the UDG. For our algorithms, we assume that each node can learn the dis- tances to all its neighbors. Our main result (Section 5) is formulated for the following generalization of the UDG model which we call unit ball graph (UBG). Assume that nodes are points in some metric space. Two nodes are con- nected by an edge if and only if their distance is at most 1. Each node knows the distances to all its direct neighbors. Our result for UBGs depend on the doubling dimension of the underlying metric; they are particularly strong if we have a doubling metric (constant doubling dimension). We define the doubling dimension of a metric as the smallest ρ such that every ball can be covered by at most 2ρ balls of half the radius. Note that this definition is up to constants equivalent to alternative definitions which have been used in the literature. 1

Besides that the described extension of UDGs towards general metric spaces makes our results stronger, it is mainly interesting for two reasons. First, although in theory the UDG model is widely used, describing ad hoc and sensor networks as UDGs is usually far from reality. On the other hand, a realistic graph model should comprise the geomet- ric properties of wireless network graphs. While having a distance metric which is doubling certainly keeps many of the good properties real wireless networks have, many of the too idealized assumptions are dropped. The second reason for looking at networks which are based on metric spaces of small doubling dimension is that growth restrictions are a natural assumption in many other networks such as peer-to- peer networks or the Internet. It is for example commonly assumed that the distance metric induced by Internet laten- cies is doubling. Hence, from that perspective, this paper proves strong upper bounds on the locality of many prob- lems in the Internet.

All our algorithms and results apply to the standard syn- chronous message passing model where time is divided in rounds. In every round, each node can send a message to all of its neighbors. Although we give upper bounds on message sizes at some places, we generally assume that message size is unbounded and that there is no restriction to local com- putations. Note that we assume that each node can send a different message to each neighbor while in wireless net- works, it is often assumed that a node can only send the same message to all neighbors (local broadcast). As long as there is no assumption on the maximum message size, the two models are equivalent because a node can pack the in- formation for all neighbors into one large message which is then locally broadcasted.



The paper has two main results. In Section 4 we show that in the described UDG model, an arbitrary covering or packing linear program (LP) can be approximated with a

1In fact it is even sufficient that all nodes know the dis- tances to their neighbors up to a constant factor and that the triangle inequality holds up to a constant factor.

constant factor in a constant number of rounds. The frac- tional versions of many important problems such as mini- mum dominating set, maximum matching, or certain flow problems fall into this category. The result is especially in- teresting in light of recent lower bounds for fractional cover- ing and packing problems which show that on general graphs for a constant approximation, at least Ω(plog n/ log log n) rounds are required [16, 17].

In Section 5, we give a deterministic algorithm which com- putes an (O(1), O(1))-decomposition in O(logn) rounds on a UBG if the underlying metric is doubling. A (d(n), c(n))- network decomposition of a graph G = (V, E) is a partition of V in disjoint clusters, such that the subgraph induced by each cluster is connected, the diameter of each cluster is in d(n), and the chromatic number of the resulting clus- ter graph is in c(n), where the cluster graph is obtained by contracting each cluster into a single node [5]. A network decomposition is a very basic structure which can be used as the basis of distributed algorithms for a huge number of problems. For instance, given a (d(n), c(n))-decomposition a maximal independent set (MIS) or a + 1-graph coloring can be computed in time d(n) · c(n) ( is the largest degree of the graph). First all clusters of the first color compute a MIS/coloring in parallel in time d(c). Subsequently, the clusters of the next colors add their contributions to the MIS/coloring. In a similar way, a c(n)-approximation for minimum dominating set can be computed in time d(n). Here, the clusters of different colors do not have to wait for each other. Another essential application of network decom- position is the synchronization of asynchronous systems as introduced by Awerbuch [4]. Note that the time complexity O(logn) of our decomposition algorithm is asymptotically optimal due to the matching Ω(logn)-lower bound for com- puting a MIS on a ring [20].

All our algorithms are formulated for the synchronous message passing model. Time is divided in rounds. In each round, each node can send a message to each of its neigh- bors.

The rest of the paper is organized as follows. Section 2 discusses related work. The technical results are presented in Sections 3, 4, and 5. The paper is concluded in Section 6



Unit disk graphs have been used in a great number of pa- pers on ad hoc and sensor networks. Especially interesting in the context of the present paper are local distributed ap- proximation algorithms for problems such as the minimum dominating set problem which is used in order to cluster wireless networks [2, 10]. Also closely related to our work are distributed algorithms which locally construct sub-graphs of the UDG with certain desirable properties (spanner, pla- nar, etc.), a task which is usually called topology control [28, 27]. In ad hoc and sensor networks, nodes are often assumed to know the distances to their neighbors or even their coordinates. In [8], distances are used to construct lo- cal coordinate systems which can then for instance be used for routing. Other applications such as geometric routing [19] or location services [1] build on the fact that nodes even know their coordinates in the plane.

Bounded growth metrics in general and doubling metrics in particular have found quite a lot of attention recently [12, 14, 15, 24, 26]. It is proposed that latencies of many real networks such as peer-to-peer networks or the Internet are

Document info
Document views14
Page views14
Page last viewedSun Jan 10 09:35:55 UTC 2016