A Mathematical Solution to the MCDS Problem for Topology Construction in Wireless Sensor Networks

P. M. Wightman, A. Fábregas, M. A. Labrador

Research output: Contribution to journalResearch Articlepeer-review

2 Scopus citations


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.

Original languageEnglish (US)
Article number5993740
Pages (from-to)534-541
Number of pages8
JournalIEEE Latin America Transactions
Issue number4
StatePublished - Jul 2011
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • General Computer Science
  • Electrical and Electronic Engineering


Dive into the research topics of 'A Mathematical Solution to the MCDS Problem for Topology Construction in Wireless Sensor Networks'. Together they form a unique fingerprint.

Cite this