- 學位論文
An Efficient Convex Hull-Based Flooding Scheme for Mobile Ad Hoc Networks
無線行動隨意網路中基於Convex-Hull之泛播機制
摘要
在無線隨意行動網路環境中，許多通訊協定會使用泛播作為傳送訊息的方法，因此有效率的泛播機制對於在無線網路中的訊息傳送是相當重要的。在此我們提出了一個基於凸包演算法所設計的泛播機制，我們提出的泛播機制只需要收集單躍傳輸範圍中鄰居節點資訊即可有效的發送泛播訊息。藉由凸包的概念所提出的泛播機制可以有效的避免無線網路中產生過多重複的泛播訊息，同時達到將訊息完整傳遞至網路中所有節點的要求，此外我們的泛播機制也具有低時間複雜度的優勢。我們更進一步的指出現有泛播演算法會產生的區域最佳化問題，進而改善我們的泛播機制去降低此問題所帶來的影響。實驗結果指出我們提出的泛播機制不僅可以有效的減少重複廣播的次數，同時維持良好的訊息傳達率。
並列摘要
Flooding is an essential and commonly used operation in mobile ad hoc networks. This paper proposes a convex hull-based flooding scheme that uses only 1-hop neighbor infor- mation to e±ciently disseminate flooding messages. Using the concept of convex hull, the proposed flooding scheme avoids excessive and redundant rebroadcastings during mes- sage dissemination with a time complexity of only O(n log h), where n is the number of a node's 1-hop neighbors and h is the number of forwarding nodes selected by a sender. The proposed flooding scheme guarantees full delivery. Further, this study addresses the local-optimal problem that commonly occurs in the sender-based flooding algorithms and modifies the proposed flooding scheme to alleviate the effects of this problem. Simulation results indicate that, compared with representative flooding schemes in the literature, the proposed flooding scheme more efficiently reduces the number of broadcasting nodes while still maintaining excellent message deliverability.