نیمه ناهمزمان و الگوریتم های مجموعه غالب متصل وزن توزیع شده برای شبکه های حسگر بی سیم
|کد مقاله||سال انتشار||مقاله انگلیسی||ترجمه فارسی||تعداد کلمات|
|67572||2015||14 صفحه PDF||سفارش دهید||10125 کلمه|
Publisher : Elsevier - Science Direct (الزویر - ساینس دایرکت)
Journal : Computer Standards & Interfaces, Volume 42, November 2015, Pages 143–156
Energy-efficient backbone construction is one of the most important objective in a wireless sensor network (WSN) and to construct a more robust backbone, weighted connected dominating sets can be used where the energy of the nodes are directly related to their weights. In this study, we propose algorithms for this purpose and classify our algorithms as weighted dominating set algorithms and weighted Steiner tree algorithms where these algorithms are used together to construct a weighted connected dominating set (WCDS). We provide fully distributed algorithms with semi-asynchronous versions. We show the design of the algorithms, analyze their proof of correctness, time, message and space complexities and provide the simulation results in ns2 environment. We show that the approximation ratio of our algorithms is 3ln(S) where S is the total weight of optimum solution. To the best of our knowledge, our algorithms are the first fully distributed and semi-asynchronous WCDS algorithms with 3ln(S) approximation ratio. We compare our proposed algorithms with the related work and show that our algorithms select backbone with lower cost and less number of nodes.