TY - GEN

T1 - An optimal solution to the MCDS problem for topology construction in wireless sensor networks

AU - Wightman, Pedro M.

AU - Fabregasy, Aldo

AU - Labradorz, Miguel A.

PY - 2010

Y1 - 2010

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=78650556610&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=78650556610&partnerID=8YFLogxK

U2 - 10.1109/LATINCOM.2010.5641018

DO - 10.1109/LATINCOM.2010.5641018

M3 - Conference contribution

AN - SCOPUS:78650556610

SN - 9781424471720

T3 - 2010 IEEE Latin-American Conference on Communications, LATINCOM 2010 - Conference Proceedings

BT - 2010 IEEE Latin-American Conference on Communications, LATINCOM 2010 - Conference Proceedings

T2 - 2010 IEEE Latin-American Conference on Communications, LATINCOM 2010

Y2 - 15 September 2010 through 17 September 2010

ER -