کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
433017 689201 2015 16 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Distributed formation of degree constrained minimum routing cost tree in wireless ad-hoc networks
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Distributed formation of degree constrained minimum routing cost tree in wireless ad-hoc networks
چکیده انگلیسی


• We define the degree constrained MRCT (DC-MRCT) problem.
• We prove that DC-MRCT is NP-complete problem.
• We propose a distributed DC-MRCT formation algorithm for wireless ad-hoc networks.

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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Parallel and Distributed Computing - Volume 83, September 2015, Pages 143–158
نویسندگان
, , ,