مشخصات مقاله | |
عنوان مقاله | On the Distributed Binary Consensus Algorithm in Wireless Sensor Networks |
ترجمه عنوان مقاله | در الگوریتم اجماع دوتایی توزیع شده در شبکه های سنسور بی سیم |
فرمت مقاله | |
نوع مقاله | ISI |
سال انتشار | مقاله سال ۲۰۱۳ |
تعداد صفحات مقاله | ۹ صفحه |
رشته های مرتبط | کامپیوتر و مهندسی فناوری اطلاعات IT |
گرایش های مرتبط | شبکه های کامپیوتری |
دانشگاه | College of Engineering Qatar University, Doha, Qatar |
کلمات کلیدی | الگوریتم توافق باینری، محاسبات توزیع شده، IRIS Motes، Tossim، شبکه حسگر بی سیم، ARQ |
کد محصول | E5145 |
نشریه | نشریه IEEE |
لینک مقاله در سایت مرجع | لینک این مقاله در سایت IEEE |
وضعیت ترجمه مقاله | ترجمه آماده این مقاله موجود نمیباشد. میتوانید از طریق دکمه پایین سفارش دهید. |
دانلود رایگان مقاله | دانلود رایگان مقاله انگلیسی |
سفارش ترجمه این مقاله | سفارش ترجمه این مقاله |
بخشی از متن مقاله: |
I. INTRODUCTION
Distributed computations within wireless sensor networks (WSNs) are currently of great interest to engineers and researchers. The significant challenge in this field is how can we achieve the overall reliability of the whole network in face of faulty nodes. The consensus problem is related to the distributed manipulation of a single data within the nodes of the network [2]–[۴]. In order to accomplish this, it is often required for all nodes in the network to reach agreement on a specific piece of data required for a computation. In [2], Bashir et al. use consensus algorithm to provide a powerful solution for distributed routing failure detection in wireless sensor networks. Indeed, a consensus about suspected node is generated by the collaboration of neighbors node. A simple algorithm for consensus is presented; every neighbor considers a decision factor for every other neighbor in order to generate a unified agreement about the node under suspicion. In their work, the authors analyze and show that their approach performs better for energy conservation and node lifetime better than previously. However, this method is limited to a network with a specific tree around the suspected node, and mechanism is more close to the well known voting method [5]. In [3], the authors proposed a new average consensus algorithm, where each node selects its own weights on the basis of some local information about its neighborhood. The proposed algorithm is tailored for networks having cluster structure. The neighborhood algorithm is designed to identify such links and give them higher weights in order to speed-up information propagation among different parts of the networks. In realistic sensor network topologies, the algorithm shows faster convergence than other existing consensus protocols [5]–[۸]. In their work in [4], the authors present an iterative decentralized consensus algorithm for routing in WSN by considering the minimization of the number of iterations and then ensure the limitation of the energy consumption. Binary consensus algorithm is a subclass of consensus problem and it is applied when there is delimitation on the memory and the processing speed [1], [9]–[۲۰]. In a binary consensus algorithm, all nodes initially compute a TRUE or FALSE answer to a given question (such as whether the current temperature is over 35 degrees) and then attempt to reach agreement on which state the majority of nodes hold. In [9], Mostefaoui et al. proposed a reduced complexity algorithm in asynchronous systems with crash failures. In their algorithm, each process runs a series of binary consensus subroutines, sequentially, in order to solve multivalued consensus. Nevertheless, the number of subroutines necessary to solve one multivariate consensus instance is unlimited and depends on the message delay. Applications of this algorithm include coordination of autonomous agents, estimation, and distributed data fusion in ad-hoc or social networks. In [10], the authors consider the binary consensus problem where each node in the network initially possesses one of two states and the goal is to decide which one of both states was initially held by the majority of nodes. The states considered in their paper is 0 (when the measurement is under 0.5), 1 (when the measurement is over 0.5) and e (for undetermined measurement). The authors show also that extending, both the signaling and memory, by just one state, may improve the reliability and speed to reach the correct consensus. Thus, it has been proved that the probability of error decays exponentially with the number of nodes N. In [11], the authors design quantized average consensus algorithm on arbitrary connected networks. In fact, quantized algorithms cannot produce a real, analog average. Instead, their algorithm reaches consensus on the quantized interval that contains the average. In their work, the authors prove that this consensus in reached in finite time almost surely. In [12], the authors develop and implement a randomized consensus protocol for the contexts where users can frequently remain dispersed over a large area, frequently resulting in sparse patches containing fewer users per unit area. Their work establishes the liveness condition that any ad-hoc network must satisfy for consensus to be solvable using the randomized approach. Performance analysis of the developed protocol show the effects of randomization in speeding up the consensus when network gets sparser. In [13], the authors consider a network that is trying to reach consensus over the occurrence of an event while communicating over additive white Gaussian noise (AWGN) channels. Indeed, the authors characterize the impact of different link qualities and network connectivity on consensus performance. |
ترجمه بخشی از مقاله: |
در اینجا مسئله اجماع دودویی روی شبکه های حسگر بی سیم (WSN) را مد نظر قرار می دهیم که هر گره از شبکه ابتداعاً یکی از دو حالت را مشاهده نموده و هدف هر گره تصمیم گیری در مورد یکی از دو حالت نگه داشته شده توسط اکثریت گره ها می باشد. در این مقاله، میانگین گیری یا مشتق گیری از اندازه گیری در WSN متشکل از N گره را مورد بررسی قرار می دهیم. در اینجا الگوریتم اجماع دودویی توزیع شده را با دستیابی به زمان همگرایی متوسط الگوریتم، مورد ارزیابی قرار می دهیم. از آنجایی که این زمان به صورت نظری برای جنبه های ریاضی مورد ارزیابی قرار گرفته است، در نتیجه این کار را با بررسی محیط زندگی واقعی من جمله پدیده اتلاف بسته و پروتکل درخواست تکرار خودکار (ARQ) بکاررفته در ارسال و انتقال پیام واقعی کامل می کنیم. به علاوه، نتایج تحلیلی جدید را با نتایج بدست آمده با تقلید سخت افزاری از الگوریتم اجماع دودویی تحت TinyOS و TOSSIM مقایسه می کنیم. در جریان ارزیابی عملکرد، تحلیل زمان همگرایی متوسط برای حالت های گره را مورد بررسی قرار می دهیم. درشبیه سازیها، از الگوریتم اجماع دودویی توزیع شده برای توپولوژیهای کاملاً متصل، حلقه ای، مسیر، تصادفی Erdos Reny و ستاره ای شکل استفاده می کنیم. |