Una Solucion Matematica al Problema del MCDS para Control de la Topologia en Redes Inalambricas de Sensores (A Mathematical Solution to the MCDS Problem for Topology Construction in Wireless Sensor Networks)

Pedro Wightman (pwightman@uninorte.edu.co)1, Aldo Fabregas (fabregas@cutr.usf.edu)2, Miguel Labrador (labrador@cse.usf.edu)2


1Universidad del Norte
2University of South Florida

This paper appears in: Revista IEEE América Latina

Publication Date: July 2011
Volume: 9,   Issue: 4 
ISSN: 1548-0992


Abstract:
Topology Construction (TC) is a very well-known technique to save energy and extend the lifetime of wireless sensor networks. One common approach to implement TC is to select a small subset of nodes that can accomplish the global objective of the network and put the rest of the nodes in a low energy consumption mode to use their energy in the future. One way to select this subset of nodes is by solving the Minimum Connected Dominating Set problem (MCDS). This paper presents a Mixed Integer Programming (MIP) formulation that finds the optimal solution to this problem. The formulation is proposed as a benchmarking tool to compare the performance of existing and new heuristics that approximate the solution to the same problem. In fact, the paper compares the performance of three well-known CDS-based topology construction protocols versus the MIP-MCDS formulation. The results show that, in terms of the size of the CDS, the distance between the optimal and the approximate solutions increases with the communication radius and the number of nodes. In terms of the solution time, for low density and high node degree topologies the mathematical programming formulation is comparable, and sometimes better, to that of the heuristics. However, in topologies with low node degree and high node density the heuristic solutions outperform the mathematical programming solution.

Index Terms:
Topology control, topology construction, Atarraya, critical transmission range, connected dominating set.   


Documents that cite this document
This function is not implemented yet.


[PDF Full-Text (555)]