Expected Routing Overhead for Location Service in MANETs under Flat Geographic Routing

摘要

We study routing overhead due to location information collection and retrieval in mobile ad-hoc networks employing geographic routing with no hierarchy. We first provide a new framework for quantifying overhead due to control messages generated to exchange location information. Second, we compute the minimum number of bits required on average to describe the locations of a node, borrowing tools from information theory. This result is then used to demonstrate that the expected overhead is Omega (n^{1.5} log (n)), where n is the number of nodes, under both proactive and reactive geographic routing, with the assumptions that 1) nodes' mobility is independent, and 2) nodes adjust their transmission range to maintain network connectivity. Finally, we prove that the minimum expected overhead under the same assumptions is Theta (n log (n)).