Huang Fuzhuo

January 2013
On The Maximum Weighted Independent Set Problem With Applications in Wireless Sensor Networks
Committee Members: Advisor: Ioannis Paschalidis, SE/ECE; Christos Cassandras, SE/ECE; Pirooz Vakili, SE/ME; Venkatesh Saligrama, SE/ECE; Appointed Chair: Prakash Ishwar, SE/ECE

Abstract: The Maximum Weighted Independent Set (MWIS) Problem considers a graph with weights assigned to the nodes and seeks to discover the “heaviest” independent set (i.e., so that no two nodes in the set are connected by an edge). The MWIS problem is closely related to a number of topics in information theory, such as maximum a posteriori estimation, error-correcting coding, spatial statistics and network communication. This problem has been shown to be NP-complete and there has been extensive work in the literature proposing a variety of heuristics. In this dissertation, we will propose a novel, low-complexity and fully distributed algorithm that yields high-quality feasible solutions to this problem. Our proposed algorithm consists of two phases, each of which requires only local information and is based on message passing. The first phase solves the linear programming (LP) relaxations of the MWIS problem via the dual gradient projection method. We consider two LP relaxations: one involving simple edge constraints and another which is tighter and accounts for all cliques of the graph. With the clique-based relaxation, the gradient projection method solves the MWIS problem optimally if the graph is perfect and the optimal solution is unique. Moreover, the gradient projection method runs in pseudo-polynomial time. The second phase of our algorithm uses the solution of the relaxation and constructs a feasible solution to the MWIS problem via deterministic or stochastic estimation. The deterministic estimation solves the node conflicts via a coloring algorithm, while the stochastic estimation introduces Glauber dynamics, where the idea is to simulate a Markov chain whose states are independent sets based on Glauber dynamics. We show that our algorithm always outputs an optimal solution to the MWIS problem for bipartite graphs using the deterministic estimation method, and provides a probabilistic performance guarantee for general graphs with heavy weights using the stochastic estimation algorithm. We also establish that our algorithms can run in an asynchronous fashion and provide the same optimal guarantee as the synchronous version. We apply our algorithms to two different applications in wireless sensor networks. The first application concerns the problem of efficiently “emptying” a wireless sensor network that has accumulated a large amount of data at its nodes and seeks to relay them to designated gateways so as to maximize a concave function of achievable transmission rates. The other application is the problem of scheduling wireless networks with stochastic packet arrivals on the links and constant transmission rates. In both cases we show that our algorithms lead to significant performance gains over the current state-of-the art.