상세정보
학술지
Distributed Formation of Degree Constrained Minimum Routing Cost Tree in Wireless Ad-hoc Networks
- 저자
- 김태홍, 서석충, 김대영
- 발행일
- 201509
- 출처
- Journal of Parallel and Distributed Computing, v.83, pp.143-158
- ISSN
- 0743-7315
- 출판사
- Elsevier
- 협약과제
- 14MI9200, (통합)스마트 네트워킹 핵심 기술 개발, 이병선
- 초록
- 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 제안 키워드
- 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