A Quorum-Based Robust and Efficient Routing Protocol for Mobile Ad-Hoc Network

[[abstract]]隨建即連(Ad-hoc)網路是由一群完全分散且具行動能力的裝置所組成，由於其網路拓撲結構隨裝置移動而變動，當兩個裝置想進行通訊時，在傳統有線網路中使用的繞徑協定便無法適用。因此本篇論文提出之QRERP繞徑協定，採用查表Table-Driven及動態建立On-Demand混合的方式運作在分群式(Cluster)網路架構上。在Initialization Phase中，我們採用隨機選擇及廣播的方式建立數個Coterie Tree的Graph來涵括所有裝置，而在 Route Discovery Phase中，當來源裝置欲尋找目的端時，先查詢裝置內之”路徑矩陣”table，或者透過”Coterie Tree 管理”table使用 Quorum機制求得到達目的端之path，然後發出路徑尋找封包，透過不同Mobile Host轉送後，目的端收到路徑尋找封包後整合及計算出此Path之對應”路徑矩陣”，接著進入Route Reply Phase，目的端回傳告知來源端此路徑建立完成，而在目的地沿著路徑回傳”路徑成功建立”給來源端的過程中，我們將此path對應的”路徑矩陣”利用Quorum機制將之分散儲存在周邊臨近Mobile Host中，供下次欲尋找相同路徑或目的地之Mobile Host使用，經過Route Reply Phase建立完路徑後便進入Data Transmission Phase，來源裝置與目的裝置開始通訊及傳遞資料。另外，透過Maintenance在來源與目的地通訊期間，如果其中某連結出現中斷錯誤時，透過內部矩陣計算及Quorum分散式存取，可以直接修補該連結(Link)並找出替代路徑。結果證明，本論文提出之繞徑協定是有效率的且可以滿足在隨建即連無線網路的環境中，任兩個 Mobile Host 快速建立一條通訊路徑之要求，達成移動性管理、減少網路訊息量、局部維護路徑、提供備份路徑及Load Balance功能等目標。[[abstract]]The objective of this paper is to propose a quorum-based robust and efficient routing protocol (QRERP) for mobile ad-hoc network. There are four phases in the proposed QRERP. They are initialization phase, route discovery phase, route reply phase, and data transmission phase. In initialization phase, the entire network is partitioned into several connected subgraph. Each subgraph is represented by a host adjacency matrix (HAM) and a logical coterie tree. A mobile host is called gateway if it participates more than two coterie trees. In the route discovery phase, a route can be discovered by one of local matrix computation, quorum-based route table query or quorum-based flooding mechanism. When a route is established, a packet can be replied from destination to source node and the route information can be distributed to the set of coteries passed through by this routing path. Finally, after the routing path is confirmed by route reply packet, source node can communication with destination. During the data transmission, when route is broken due to factors of mobility or power exhausted, a route maintenance mechanism can be triggered to mainline the robustness of the routing path. The performance of the proposed QRERP is demonstrated by experimental results. From the results, we can conclude that the proposed approach has advantages of backup route, less control overhead, mobility maintenance and route maintenance