Hop Count Distribution for Minimum Hop-Count Routing in Finite Ad Hoc Networks

Hop count distribution (HCD), generally formulated as a discrete probability distribution of the hop count, constitutes an attractive tool for performance analysis and algorithm design. This paper devotes to deriving an analytical HCD expression for a finite ad hoc network under the minimum hop-count routing protocols. Formulating the node distribution with binomial point process, the network is provided as a bounded area with all nodes randomly and uniformly distributed. Considering an arbitrary pair of source node (SN) and destination node, an innovative and straightforward definition is presented for HCD. In order to derive HCD out, an original mathematical framework, named as the equivalent area replacement method (EARM), is proposed and verified. Under the EARM, HCD is derived by first considering the special case where SN locates at the network center and then extending to the general case where SN is randomly distributed. For each case, the accuracy of our HCD model is evaluated by simulation comparison. Results show that our model matches well with the simulation results over a wide range of parameters. Particularly, the derived HCD outperforms the existing formulations in terms of the Kullback Leibler divergence, especially when SN is randomly distributed.