27-06-2014, 09:55 AM
Distributed Algorithms for Constructing
Approximate Minimum Spanning Trees
In Wireless Sensor Networks
Distributed Algorithms.doc (Size: 87.5 KB / Downloads: 10)
Abstract:
While there are distributed algorithms for the Minimum Spanning Tree (MST) problem, these algorithms require relatively large number of messages and time, and are fairly involved, making them impractical for resource-constrained networks such as wireless sensor networks. In such networks,a sensor has very limited power,and any algorithm needs to be simple,local and energy efficient. Motivated by these considerations, we design and analyze a class of simple and local distributed algorithms called Nearest Neighbor Tree (NNT) algorithms for energy- efficient construction of an approximate MST in wireless networks. Assuming that the nodes are uniformly distributed, we show provable bounds on both the quality of the spanning tree produced and the energy needed to construct them.We show that while NNT produces a close approximation to the MST, it consumes asymptotically less energy than the classical message-optimal distributed MST algorithm due to Gallagery,Humblet, and Spira. Further, the NNTs can be maintained dynamically with polylogarithmic rearrangements under node insertions/deletions. We also perform extensive simulations,which show that the bounds are much better in practice.Our results, to the best of our knowledge, demonstrate the first tradeoff between the quality of approximation and the energy required for building spanning trees on wireless networks, and motivate similar considerations for other important problems
Existing :
The minimum spanning tree (MST) problem is an important and commonly occurring primitive in the design and operation of data and communication networks . For instance , in ad hoc sensor networks , MST is the optimal routing tree for data aggregation. Traditionally, the efficiency of distributed algorithms is measured by the running time and the number of messages exchanged among the computing nodes , and a lot of research has gone into the design of algorithms that are optimal with respect to such criteria. The classical algorithm due to Gallagery, Humble t, and Spira (hence forth referred to as the GHS algorithm) uses _(n ln n ) jEj) messages , and is essentially optimal with respect to the message complexity . There are distributed algorithms that find the MST and are essentially optimal in terms of time complexity : they run in O(Diam(G) ) n1=2polylog(n)) time, and there are (almost) matching lower bounds. However, these time-optimal algorithms involve a lot of message transfers (much more than GHS). Even for a wireless network modeled by a unit disk graph (UDG) or even a ring, any distributed algorithm to construct an MST needs _(n ln n) messages . Despite their theoretical optimality, these algorithms are fairly involved, require synchronization and a lot of bookkeeping ;such algorithms are impractical for ad hoc and sensor networks .
Proposed :
In this paper, we study a class of simple , local , distributed, approximation algorithms called the Nearest Neighbor Tree (NNT) algorithms that are provably good: they build slightly suboptimal trees with low energy complexity and are easy to maintain dynamically. The NNT algorithms bypass such a step completely by a very simple idea : each node chooses a unique rank, a quantity from a totally ordered set, and a node connects to the nearest node of higher rank. The algorithm consists of exchanging three types of messages : request, available, and connect among the nodes . Each node begins with broadcasting a request for connection message.
Problem Analysis:
THE minimum spanning tree (MST) problem is an important and commonly occurring primitive in the design and operation of data and communication networks. For instance, in ad hoc sensor networks, MST is the optimal routing tree for data aggregation. Traditionally, the efficiency of distributed algorithms is measured by the running time and the number of messages exchanged among the computing nodes, and a lot of research has gone into the design of algorithms that are optimal with respect to such criteria. The classical algorithm due to Gallagery, Humblet, and Spira (henceforth referred to as the GHS algorithm) uses messages, and is essentially optimal with respect to the message complexity. There are distributed algorithms that find the MST and are essentially optimal in terms of time complexity: there are (almost) matching lower bounds. However, these time-optimal algorithms involve a lot of message transfers (much more than GHS). Even for a wireless network modeled by a unit disk graph (UDG) or even a ring, any distributed algorithm to construct an MST.
Despite their theoretical optimality, these algorithms are fairly involved, require synchronization and a lot of bookkeeping; such algorithms are impractical for ad hoc and sensor networks . For example, consider sensor networks—an ad hoc network formed by large numbers of small, battery-powered, wireless sensors. In many applications, the sensors are typically “sprinkled” liberally in the region of interest, and the network is formed in an ad hoc fashion by local self-configuration. Since each sensor usually knows only its neighbors, the network management and communication has to be done in a local and distributed fashion. Additionally, because of battery limitations, energy is a very crucial resource. A distributed algorithm, which exchanges a large number of messages, can consume a relatively large amount of energy (and also time) and is not suitable in an energy-constrained sensor network. This is especially true in a dynamic setting—when the network needs to be reconfigured (e.g., due to mobility or failures) frequently and quickly. Reconfiguration is also necessary to evenly distribute the energy consumption among all nodes and, thus, to increase the network lifetime.
Thus, it is necessary to develop simple local distributed algorithms which are energy efficient, and preferably also time efficient, even at the cost of being suboptimal. This adds a new dimension to the design of distributed algorithms for such networks. Thus, we can potentially trade off optimality of the solution to work done by the algorithm. In a sensor network the total energy required (“energy complexity”) in a distributed algorithm typically depends on the time needed, the number of messages exchanged, and the radiation energy needed to transmit the messages over a certain distance. The radiation energy needed to transmit a message is typically proportional to some work function f (typically square or some small power) of the distance between the
sender and the receiver . Thus, it becomes important to measure efficiency of a distributed algorithm in terms of energy, besides the number of messages. While there has been a lot of recent work on local algorithms for construction of low-weight connected subgraphs in wireless ad hoc networks (motivated by topology control and energy-efficient routing) to the best of our knowledge, there has been little work on localized construction of exact or approximate MSTs, especially in the context of wireless ad hoc networks. A structure is low weight if its total edge length is within a small factor of the total edge length of the MST, but the structure may have cycles. It is easy to show that MST cannot be constructed in a purely localized manner, i.e., each node cannot determine which edge is in the defined structure by using only the information of the nodes within some constant hops. For example, Li et al. proposed a method to build what they call a local minimum spanning tree (LMST), which is guaranteed to be connected and has bounded degree, but is not a low-weight structure. In fact, Li et al. demonstrate the difficulty in constructing an MST and gives a localized algorithm to construct a low-weight connected subgraph (that can have cycles) for topology control in wireless ad hoc networks.
we study a class of simple, local, distributed, approximation algorithms called the Nearest Neighbor Tree (NNT) algorithms that are provably good: they build slightly suboptimal trees with low energy complexity and are easy to maintain dynamically. A fundamental step in all existing algorithms for the MST problem is cycle detection: given an edge, one needs to determine whether the edge would form a cycle with the edges already chosen. This deceptively simple operation leads to a big overhead: a significant amount of bookkeeping and message passing needs to be done in order to maintain the components, and answer such queries. The NNT algorithms bypass such a step completely by a very simple idea: each node chooses a unique rank, a quantity from a totally ordered set, and a node connects to the nearest node of higher rank. Observe that this immediately precludes cycles, and the only information that needs to be exchanged is the rank; also, this information does not need to be updated continuously over the course of the algorithm.
The NNT scheme is closely related to the approximation algorithm for the traveling salesman problem (coincidentally called Nearest Neighbor (NN) algorithm) analyzed in a classic paper by Rosenkrantz et al. Imase and Waxman also used a scheme based on , which can also be considered a variant of the NNT scheme, to show that it can
maintain an approximate Steiner tree dynamically assuming only node additions, but not deletions. These results can easily be used to show that NNT with any ranking of the nodes gives an-approximation to MST on a metric graph, i.e., a complete graph with edge weights satisfying the triangle inequality. In contrast, in this paper, we consider a different graph model (more suitable to model wireless ad hoc networks): a random geometric graph where nodes are distributed uniformly at random in a unit square and show an expected approximation ratio is O(l).
Conclusion:
The NNT paradigm is a simple and local scheme for constructing and maintaining low-cost trees in an ad hoc network setting. It does not require any complex synchronization and is naturally robust. We study various properties, such as quality, degree, and dynamic complexity for different NNTs where the nodes are uniformly distributed in two-dimensional plane, and it shows very promising results.