ABSTRACT:

Location discovery is a fundamental problem in wireless ad hoc networks. Most of the ad hoc routing protocols use some form of flooding to discover the location and route of a mobile node. Despite various optimizations, many messages are propagated unnecessarily. We propose the Optimal Flooding Protocol (OFP), based on a variation of The Covering Problem that is encountered in geometry, to minimize the unnecessary transmissions drastically and still be able to cover the whole region. OFP out-performs other existing variations of flooding. This simple protocol uses up to 65 % to 80% fewer messages than flooding and 50 % fewer messages than gossip-based flooding, which has been proposed as one of the best optimized variation of flooding. OFP is scalable with respect to number of nodes; in fact OFP's performance improves with the number of nodes. Keywords-optimal flooding; flooding; location discovery; routing in ad-hoc networks; ad-hoc network, wireless networks.

Complete paper in Adobe Acrobat format.