07/11/2005, 17:00 — 18:00 — Sala P3.10, Pavilhão de Matemática
Claude Tadonki, University of Geneva, Switzerland
Integer programming heuristic for the dual power selection problem in wireless network.
We seek an integer programming based heuristic for solving the dual power management problem in wireless sensor networks. For a given network with two possible transmission powers (low and high), the problem is to find a minimum size subset of nodes such that if they are assigned high transmission power while the others are assigned low transmission power, the network will be strongly connected. The main purpose behind this efficient setting is to minimize the total communication power consumption while maintaining the network connectivity. In a theoretical point of view, the problem is known to be difficult to solve exactly. An approach to approximate the solution is to work with a spanning tree of clusters. In our model, a cluster is a strongly connected component in the transmission graph where only the low transmission power is considered. We follow the same approach, and we formulate the node selection problem inside clusters as an integer programming problem which is solved exactly using specialized codes. Experimental results show that our algorithm is efficient both in execution time and solution quality.
