BROWSE
Detail
Journal Article
Distributed Formation of Degree Constrained Minimum Routing Cost Tree in Wireless Ad-hoc Networks
Cited 5 time in 
Share 
Share
- Authors
- Taehong Kim, Seog Chung Seo, Daeyoung Kim
- Issue Date
- 2015-09
- Citation
- Journal of Parallel and Distributed Computing, v.83, pp.143-158
- ISSN
- 0743-7315
- Publisher
- Elsevier
- Language
- English
- Type
- Journal Article
- Abstract
- During several decades, there have been many researches on approximation algorithms for constructing minimum routing cost tree (MRCT) that minimizes the sum of routing cost of all pairs in a tree topology. Existing algorithms have been mainly studied in the field of graph theory, thus it is difficult to apply them to multi-hop wireless ad-hoc networks due to the theoretical and centralized methodology. In addition, wireless ad-hoc network protocols restrict the maximum degree, which is the maximum number of children a parent may have, in order to prevent excessive concentration of traffic. However, this limitation has not been considered by any existing algorithms. In this paper, we define the degree constrained MRCT (DC-MRCT) problem and extract the characteristics of DC-MRCT by analyzing all possible tree topologies for the given number of nodes. Based on these characteristics that DC-MRCT has the minimum sum of tree level and the maximum square sum of subtree sizes, we propose a distributed DC-MRCT Formation (DC-MRCTF) algorithm that can be applicable to any type of wireless ad-hoc network protocols working on tree topology. Performance evaluation shows that DC-MRCTF gives noticeable benefit for up to 80% of individual communication pair compared with the representative tree formation algorithm in ZigBee as well as significantly reduces the sum of routing cost of all pairs regardless of network density.
- KSP Keywords
- Degree constrained, Distributed Formation, Maximum degree, Minimum routing cost tree, Multi-Hop, Network density, Performance evaluation, Tree formation, Wireless ad-hoc network, approximation algorithms, graph theory