Xiangdong Song

January 2010
Scheduled Multiple Access Control For Wireless Sensor Networks
Committee Members: Advisor: Ioannis Paschalidis, SE/ECE; Christos Cassandras, SE/ECE; Pirooz Vakili, SE/ME; Thomas Little, SE/ECE

Abstract: This thesis treats the problem of efficiently transferring large amounts of data from the nodes of a wireless sensor network to a set of selected gateways. The main principle advanced is the use of transmission scheduling as a way to eliminate energy wasteful collisions and retransmissions encountered by traditional random multi-access schemes. The problem is considered in a cross-layer optimization framework according to which scheduling, routing, and power control decisions that are usually confined to different layers are now taken jointly. Throughout the thesis, a protocol-based physical layer model is assumed which specifies that only non-interfering transmissions are successful. Interference includes primary (node-exclusion) interference, as well as, secondary interference among transmission pairs in close proximity.

First, the thesis considers arbitrary network topologies and develops a centralized algorithm for solving the problem using decomposition ideas from mathematical programming. The resulting policy involves time-sharing among a number of feasible transmission schemes. The algorithm uses a dual cutting-plane method and a set of novel approaches are proposed to generate dual cuts. These involve the dual separation problem and include: (i) its relaxation into a maximum weighted matching problem, and (ii) solving it approximately through a polynomial-time approximation scheme. The latter scheme is improved by using a randomization approach.

Second, the thesis develops distributed algorithms for special network topologies including stars and trees. For a star topology, a theorem is established according to which the optimal solution can be searched over a much smaller space, making the problem polynomially solvable. For a tree network the problem can also be solved in polynomial time. For some special cases, an analytical solution can be obtained.

Third, the thesis considers arbitrary topologies and develops distributed heuristics. These heuristics are based on distributed message-passing algorithms for solving relaxations of the maximum weighted independent set problem. A message-passing algorithm is proposed in the literature which has been shown to be exact in some special cases and under an assumption that requires the optimal solution to be unique. A new approach is proposed to address the limitations introduced by such a uniqueness assumption.