Routing in ad hoc networks: a theoretical framework with practical implications

In this paper, information theoretic techniques are used to derive analytic expressions for the minimum expected length of control messages exchanged by proactive routing in a two-level hierarchical ad hoc network. Several entropy measures are introduced and used to bound the memory size necessary for the storage of the routing tables. The entropy rates of the topology sequences are used to bound the communication routing overhead-both the interior routing overhead within a cluster and the exterior routing overhead across clusters. A scalability analysis of the routing overheads with regard to the number of nodes and the cluster size is provided under three different network scaling modes. Finally, practical design issues are studied by providing the optimal cluster sizes that asymptotically minimize (i) the memory requirement for each cluster head; (ii) the total control message routing overhead.