領袖選擇演算法在容錯行動無線網路環境之研究

Leader Election Algorithm for Fault-tolerant Mobile Ad Hoc Network

吳佳厚

指導教授 ： 蕭顯勝 ； 林順喜

國立臺灣師範大學/理學院/資訊工程研究所/碩士(2004年)

摘要

隨著網際網路科技的迅速發展，網路拓撲型態也走向無線化。行動無線網路的趨勢使得分散式系統的設計也實行在行動計算之中。現今行動無線網路中有許多應用服務在執行時需要領袖選擇演算法來配合，比如在群組通訊協議之中，當原本的群組協調者發生錯誤無法正常運作時，該群組即需要產生新的協調者。換句話說，領袖選擇在分散式計算中是一個基本問題。然而在無線網路的環境下，分散式系統是極為不安全的，處理器或是無線通訊皆有可能發生錯誤，良好的處理器或是通訊通道可能因此遭受其影響，因此在這個網路環境之下，更需要容錯計算來確保領袖選擇的運作。我們在此提出一個容錯式領袖選擇演算法，該演算法可以容許最多的錯誤單元，並且使用最佳化的通訊複雜度達成所有良好的處理器可以選擇共同的領袖。

關鍵字

拜占庭協議 ； 容錯計算 ； 領袖選擇 ； 行動無線網路

並列摘要

Mobile ad hoc network is new trend of networking system. This technology trends have greatly encouraged distributed system design and practice to support mobile computing. In present, there are a lot of applications for mobile networks need some sort of leader election algorithm for their operation. For example, in the group communication protocols, the election of a new coordinator is required when a group coordinator crashes or departs the system. In other words, leader election is a fundamental problem for distributed computing. However, it is more dangerous under such mobile environment. Processors in mobile network may suffer the influences caused by illegal processors that can intrude this network easily. Besides, the communication in wireless network is transmitted by radio frequency. It is also possible for an unauthorized processor, located within the transmitter’s communication radius, to listen to the communication. Thus, we need fault-tolerant computing under mobile networks to tolerate faulty components and ensure the correct operation of the leader election process. The protocol we proposed is a leader election algorithm for fault-tolerant mobile ad hoc network in this article. The protocol can tolerant maximum faulty components to ensure that all fault-free processors to elect a common leader with optimal communication complexity.

並列關鍵字

Byzantine Agreement ； Fault-tolerant ； Leader Election ； Mobile Ad hoc Network