An Optimization Algorithm for the Minimum Connected Dominating Set Problem in Wireless Sensor Network


Namsu Ahn and Sungsoo Park




One of the critical issues in wireless sensor network is the design of a proper routing protocol.

One possible approach is utilizing a virtual infrastructure, which is a subset of sensors to connect all the sensors in the network.

Among the many virtual infrastructures, the connected dominating set is widely used.

Since a small connected dominating set can help to decrease the protocol overhead and energy consumption, it is preferable to find a small sized connected dominating set.

Although many algorithms have been suggested to construct a minimum connected dominating set, there have been few exact approaches.

In this paper, we suggest an improved optimal algorithm for the minimum connected dominating set problem, and extensive computational results showed that our algorithm outperformed the previous exact algorithms.

Also, we applied our optimal algorithm to the maximum lifetime coverage problem that requests a schedule of the sensors which maximizes the network lifetime, and the results showed that our algorithm is capable of finding good quality solutions in a reasonable amount of time.


KEYWORDS: Wireless sensor network, minimum connected dominating set, optimal algorithm, integer programming, network lifetime.


Contact Address :


Sungsoo Park, Professor,

Department of Industrial Engineering

Korea Advanced Institute of Science and Technology (KAIST)

373-1 Gusung-Dong, Yusong-Gu, Taejon 305-701, Korea

PHONE : +82-42-350-3121

FAX : +82-42-350-3110

E-mail :