Back to search

Boston University

On the maximum weighted independent set problem with applications in wireless sensor networks

Abstract

dc:description.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, that is, a set of nodes with maximal total weight so that no two nodes in the set are connected by an edge. The MWIS problem arises in many application domains including maximum a posteriori estimation, error-correcting coding, spatial statistics, and communication networks. It has been shown to be combinatorially hard (NP-complete) and there has been extensive work in the literature proposing a variety of heuristics. In this dissertation, we propose a novel, low-complexity and 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 between neighboring nodes. The first phase solves Linear Programming (LP) relaxations of the MWIS problem. We consider two LP relaxations: one involving simple edge constraints and another which is tighter and accounts for all cliques of the graph. The second phase of our algorithm uses the solution of the relaxation and constructs a feasible solution to the MWIS problem. We establish that we always obtain a feasible solution to MWIS and that for special cases of graphs the solution is optimal. More specifically, with the clique-based relaxation we can guarantee an optimal solution for the large class of so called perfect graphs. When using the edge-based relaxation, our algorithm guarantees optimality for bipartite graphs and obtains with high probability near-optimal solutions for general graphs with large weights. We also establish that our algorithms can run in an asynchronous fashion and provide the same optimality guarantees 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.

Degree

thesis:*
Name thesis:degree_name
Doctor of Philosophy
Level thesis:degree_level
doctoral
Discipline thesis:degree_discipline
Systems Engineering
Grantor dc:publisher
Boston University
Year dc:date.issued
2013

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Huang, Fuzhuo

Rights

Language dc:language.iso
en_US

Identifiers

dc:identifier.*
Dc Identifier Other
(ALMA)contemp

Chain of custody

source
Harvested from
Boston University
Base URL
open.bu.edu/oai/request
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
related terms
citation

Huang, Fuzhuo. On the maximum weighted independent set problem with applications in wireless sensor networks. doctoral thesis, Boston University, 2013. https://hdl.handle.net/2144/12785