A Multi-Start Local Search Algorithm Finding Minimum Connected Dominating Set in Wireless Sensor Networks 


Vol. 40,  No. 6, pp. 1142-1147, Jun.  2015


PDF Full-Text
  Abstract

As a method to increase the scalability and efficiency of wireless sensor networks, a scheme to construct networks hierarchically has received considerable attention among researchers. Researches on the methods to construct wireless networks hierarchically have been conducted focusing on how to select nodes such that they constitute a backbone network of wireless network. Nodes comprising the backbone network should be connected themselves and can cover other remaining nodes. A problem to find the minimum number of nodes which satisfy these conditions is known as the minimum connected dominating set (MCDS) problem. The MCDS problem is NP-hard, therefore there is no efficient algorithm which guarantee the optimal solutions for this problem at present. In this paper, we propose a novel multi-start local search algorithm to solve the MCDS problem efficiently. For the performance evaluation of the proposed method, we conduct extensive experiments and report the results.

  Statistics
Cumulative Counts from November, 2022
Multiple requests among the same browser session are counted as one view. If you mouse over a chart, the values of data points will be shown.


  Cite this article

[IEEE Style]

S. Kang, M. Jeong, S. R. Lee, "A Multi-Start Local Search Algorithm Finding Minimum Connected Dominating Set in Wireless Sensor Networks," The Journal of Korean Institute of Communications and Information Sciences, vol. 40, no. 6, pp. 1142-1147, 2015. DOI: .

[ACM Style]

Seung-Ho Kang, Min-A Jeong, and Seong Ro Lee. 2015. A Multi-Start Local Search Algorithm Finding Minimum Connected Dominating Set in Wireless Sensor Networks. The Journal of Korean Institute of Communications and Information Sciences, 40, 6, (2015), 1142-1147. DOI: .

[KICS Style]

Seung-Ho Kang, Min-A Jeong, Seong Ro Lee, "A Multi-Start Local Search Algorithm Finding Minimum Connected Dominating Set in Wireless Sensor Networks," The Journal of Korean Institute of Communications and Information Sciences, vol. 40, no. 6, pp. 1142-1147, 6. 2015.

Search
(IN TITLE, AUTHOR, ABSTRACT,KEYWORDS)

Advanced Search ▼

POPULAR KEYWORDS
(TOP 10 KEYWORDS)

Recent Publications
(LAST 3 YEARS)






pISSN : 1226 - 4717
eISSN : 2287 - 3880