دانلود مقاله ISI انگلیسی شماره 70386
ترجمه فارسی عنوان مقاله

محاسبات توزیع شده از مجموعه تسلط متصل برای شبکه های بی سیم چند هاپ ☆

عنوان انگلیسی
Distributed Computation of Connected Dominating Set for Multi-Hop Wireless Networks ☆
کد مقاله سال انتشار تعداد صفحات مقاله انگلیسی
70386 2015 6 صفحه PDF
منبع

Publisher : Elsevier - Science Direct (الزویر - ساینس دایرکت)

Journal : Procedia Computer Science, Volume 63, 2015, Pages 482–487

ترجمه کلمات کلیدی
الگوریتم توزیع شده - مجموعه تسلط متصل
کلمات کلیدی انگلیسی
Connected Dominating Set; Distributed Algorithm
پیش نمایش مقاله
پیش نمایش مقاله  محاسبات توزیع شده از مجموعه تسلط متصل برای شبکه های بی سیم چند هاپ ☆

چکیده انگلیسی

In large wireless multi-hop networks, routing is a main issue as they include many nodes that span over relatively a large area. In such a scenario, finding smallest set of dominant nodes for forwarding packets would be a good approach for better communication. Connected dominating set (CDS) computation is one of the method to find important nodes in the network. As CDS computation is an NP problem, several approximation algorithms are available but these algorithms have high message complexity. This paper discusses the design and implementation of a distributed algorithm to compute connected dominating sets in a wireless network with the help of network spectral properties. Based on local neighborhood, each node in the network finds its ego centric network. To identify dominant nodes, it uses bridge centrality value of ego centric network. A distributed algorithm is proposed to find nodes to connect dominant nodes which approximates CDS. The algorithm has been applied on networks with different network sizes and varying edge probability distributions. The algorithm outputs 40% important nodes in the network to form back haul communication links with an approximation ratio ≤ 0.04 * ∂ + 1, where ∂ is the maximum node degree. The results confirm that the algorithm contributes to a better performance with reduced message complexity.