Abstract
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.