一個適用於叢集式行動隨意網路的權重式領袖選擇演算法

Abstract

領袖選擇(Leader Election)一直是行動隨意網路(Mobile Ad-hoc Network)中一個重要的議題。隨著終端使用者的設備更新和無線技術的演進，傳統集中式的運算觀念也跟著改變。一個領袖必須處理叢集(Cluster)內的一些重要事務，例如:共享資源的有效運用，設備的同步，或維護路由資訊…等。一個適當的行動隨意網路領袖選擇演算法，應可讓行動隨意網路達到更高的效能。 在這篇論文中，我們修改傳統的暴力法(Bully Algorithm)，提出一個適用叢集式行動隨意網路的權重式(Weight-based)領袖選擇演算法。我們改善了暴力法讓網路附載過高、不符合一致性原則的缺點，並整合了Paxos演算法，讓整個選舉過符合一致性的標準並具備容錯性。從實驗中，我們驗證本論文所提出的演算法藉著更少的選舉階段和權重調配，可以有效減少封包傳送的數據上和領袖重選的次數。

The Leader Election problem is an important research topic in ad-hoc networks. With the advent of wireless communication technology, the concept of centralized computing has been changed due to the mobility of end-user devices. A leader is responsible for making the use of shared resource in an optimal manner, such as synchronization between devices, or maintains the routing information of the cluster. The adaption of suitable and efficient leader election algorithm could achieve better performance in a mobile ad-hoc network. In this paper, we propose a weight-based leader election algorithm which is modified from Bully algorithm. We solve some drawbacks of the Bully algorithm. Moreover, we integrate PAXOS algorithm with the leader election procedure. The proposed algorithm takes both consensus and fault-tolerant into consideration. The proposed algorithm has fewer election stages and weighting function. We examine our algorithm with Bully algorithm together by the amount of packet transfer and leader reelection counts. The proposed algorithm can elect a better leader with fewer redundancies.