A Branch and Bound Algorithm to Find a Routing Tree Having Minimum Wiener Index in Sensor Networks with High Mobile Base Node 


Vol. 35,  No. 5, pp. 466-473, May  2010


PDF
  Abstract

Several protocols which are based on tree topology to guarantee the important metrics such as energy efficiency in sensor networks have been proposed. However, studies on the effect of topologies in sensor networks, where base node has a high mobility, are very few. In this paper, we propose a minimum Wiener index tree as a suitable topology to the wireless sensor networks with high mobile base node. The minimum Wiener index spanning tree problem which aims to find a tree with minimum Wiener index from a given weighted graph was proved to be NP-hard. We designed a branch and bound algorithm for this problem. To evaluate the performance of proposed tree, the comparisons with minimum spanning tree in terms of transmission distance, energy consumption during one round, and network lifetime was performed by simulations. Our proposed tree outperformed in transmission distance and energy efficiency but underperformed in lifetime.

  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, K. Kim, W. Lee, I. Song, M. Jung, S. Lee, "A Branch and Bound Algorithm to Find a Routing Tree Having Minimum Wiener Index in Sensor Networks with High Mobile Base Node," The Journal of Korean Institute of Communications and Information Sciences, vol. 35, no. 5, pp. 466-473, 2010. DOI: .

[ACM Style]

Seung-Ho Kang, Ki-Young Kim, Woo-Young Lee, Iickho Song, Min-A Jung, and Seong-Ro Lee. 2010. A Branch and Bound Algorithm to Find a Routing Tree Having Minimum Wiener Index in Sensor Networks with High Mobile Base Node. The Journal of Korean Institute of Communications and Information Sciences, 35, 5, (2010), 466-473. DOI: .

[KICS Style]

Seung-Ho Kang, Ki-Young Kim, Woo-Young Lee, Iickho Song, Min-A Jung, Seong-Ro Lee, "A Branch and Bound Algorithm to Find a Routing Tree Having Minimum Wiener Index in Sensor Networks with High Mobile Base Node," The Journal of Korean Institute of Communications and Information Sciences, vol. 35, no. 5, pp. 466-473, 5. 2010.

Search
(IN TITLE, AUTHOR, ABSTRACT,KEYWORDS)

Advanced Search ▼

POPULAR KEYWORDS
(TOP 10 KEYWORDS)

Recent Publications
(LAST 3 YEARS)






pISSN : 1226 - 4717
eISSN : 2287 - 3880