Modeling sparsity of planar topologies for wireless multi-hop networks

Topology Control (TC) is a fundamental research problem where the goal is to determine a set of wireless links such that the composed topology satisfies some desirable properties. Some of the achievable properties are connectivity, symmetricity, planarity, minimal use of energy, sparseness, bounded maximum node degree etc. A topology is said to be planar if there is no link crossing in the topology. Planar topologies are heavily used by several protocols lying on different layers of the protocol stack. Several TC algorithms generating planar topologies have been proposed recently. Although sparseness is a key metric in evaluating performance of such topologies, none of the prior algorithms provide any mathematical model to determine sparseness of the topology. In this paper, we provide a generic analytical model for evaluating sparseness of planar topologies. The derived analytical expressions can be used in determining average node degree, topology size etc., without running simulations or prior to the deployment of real systems. The analytical expressions are validated through extensive simulation experiments.