Graph Theory is a central component of computer networks and network science. Beyond serving as a useful abstract model in general, many problems in graph theory map directly to real problems in ad hoc and sensor networks. As an example, the problem of choosing which channels can be accessed by which members of an ad hoc network can be mapped directly to the classic NP-Complete problem of Vertex Coloring. In many cases, there are well-known and efficient sequential algorithms that deliver reliable approximate solutions. However, wireless, ad-hoc, and sensor networks are composed of many computers, each of which may have limited information about the overall network. In these cases, it would be beneficial to have efficient distributed algorithms that deliver reliable approximate solutions. Finding distributed algorithms to solve NP-Complete Graph Problems is difficult for three basic reasons. First, as previously mentioned, a single processor in a distributed computer may have limited knowledge about the overall structure of the network. Second, there are real theoretical limitations to how well local information can be used to solve these problems globally.[5] Finally, the solution space for these problems is exponential, so in even moderately dense networks, there may be an extremely large number of local solutions and no clear way to choose between them.[1]
These problems are interrelated. On the one hand, the number of solutions is large, so even with perfect knowledge of the entire network, a single node might not be able to solve the problem quickly. The problem of routing all information to a sink is itself non-trivial. On the other hand, even if a node solves its local problem exhaustively, there is no guarantee that such a solution will be optimal when applied to the network as a whole. Finally, while local solutions may not be optimal, the communication costs might be high enough that strictly local solutions are desirable.
Distributed algorithms for NP-Complete problems with networking applications should take these factors into consideration. Our current work on the Vertex Cover problem employs a variety of strategies to capture reliable approximate solutions in a constant or slowly decreasing number of communication rounds.
Given a graph G(V,E), a vertex cover of that graph is a set V′ ⊂ V | ∀ e(u,v) ∈ E, u ∈ V′ ∨ v ∈ V′. That is, for every edge in G, at least one of its endpoints is in V′. If every vertex has a weight (w(v)) associated with it, then every possible Vertex Cover of the Graph will have some cumulative weight, obtained by summing the weights for all v ∈ V′. The Minimum Weighted Vertex Cover problem is to find the lowest possible cumulative weight out of all covers of G.
The unweighted Vertex Cover problem is related to Target Coverage in sensor networks, that is, any set of sensors that cover any set of targets can be represented as a Vertex Cover. An important problem in sensor networks is the Network Lifetime Problem (NL). Network Lifetime is exactly that, given a set of sensors and set of targets, how long can the sensors cover the targets before too many sensors run out of battery for the targets to be covered? This problem is also NP-Complete, and because of it’s relationship with Vertex Cover, it is probable that it is also not locally computable.
One possible way to attack this problem is to look for covers of minimum cumulative weight. The intuition here is that if the battery lives of the sensors are minimized cumulatively, the targets will be covered efficiently on average. Prasad and Dhawan have shown that finding efficient local covers can extend network lifetime in [7].
In the current work, we focus on finding the relationship, if any, between vertex cover and network lifetime. We also introduce two new distributed algorithms for finding the minimum weighted vertex cover of a graph, one of which runs in constant time on most random graphs.
For purposes of running experiments, we have built a simple network generator and distributed system simulator using the ruby programming language.1. The simulator will execute any stepwise distributed algorithm, provided that the distributed objects meet certain criteria.
Network generators were constructed for creating triangular grids, random networks, and unit-disk networks. Creation of random networks was accomplished using a modification of the Erdos-Renyi algorithm.[6] The major modification was to add a requirement that networks be connected. Random networks were connected using a two-step process: first, a minimum spanning tree was created for each sub-network, second, the MSTs are connected.
The simulation design is described in more detail on the network simulation page.
One major contribution of this work is the development of two new algorithms. Four algorithms in all have been tested. First, the Lifetime Dependency Graph from [2] is modified for MWVC. The distributed algorithm presented in [4] was implemented. Gonzalez presents a sequential, two-approximate, linear time algorithm in [3] which we adapt for distributed computing. Finally, a new approach is taken with the introduction of the Partial Cover Dependency Graph.
This document was translated from LATEX by HEVEA.Contact me with questions:
