ETRI-Knowledge Sharing Plaform

KOREAN
논문 검색
Type SCI
Year ~ Keyword

Detail

Journal Article Distributed Formation of Degree Constrained Minimum Routing Cost Tree in Wireless Ad-hoc Networks
Cited 5 time in scopus Share share facebook twitter linkedin kakaostory
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
DOI
https://dx.doi.org/10.1016/j.jpdc.2015.05.006
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