Distributed formation of degree constrained minimum routing cost tree in wireless ad-hoc networks

During several decades, there have been many researches on approximation algorithms for constructing minimum touring 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.
Publisher
ACADEMIC PRESS INC ELSEVIER SCIENCE
Issue Date
2015-09
Language
ENG
Citation

JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING, v.83, pp.143 - 158

ISSN
0743-7315
DOI
10.1016/j.jpdc.2015.05.006
URI
http://hdl.handle.net/10203/200598
Appears in Collection
CS-Journal Papers(저널논문)
Files in This Item
There are no files associated with this item.
  • Hit : 111
  • Download : 0
  • Cited 0 times in thomson ci
This item is cited by other documents in WoS
⊙ Detail Information in WoSⓡClick to seewebofscience_button
⊙ Cited 1 items in WoSClick to see citing articles inrecords_button

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0