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 -