On the Expected Size of Minimum-Energy Path-preserving Topologies for Wireless Multi-hop Networks

Abstract—Topology Control (TC) algorithms for multi-hop wireless networks create a connected communication subgraph that satisfies some topological properties by assigning appropriate transmission power to each node. A topology is said to be minimum-energy path-preserving if it preserves minimum energy paths between every pair of nodes. Creating minimum-energy path-preserving sparse topologies is a fundamental research problem in TC that has been addressed in several recent research works. Although sparseness is a key metric in comparing the per-formance of such algorithms, none of these prior works provides analytical models to determine the sparseness. In this paper, we provide a generic analytical model for evaluating sparseness of such topologies. The derived analytical expressions are useful in determining topology size without running simulations or prior to the deployment of real systems. Moreover, we demonstrate how to analytically couple sparseness of topologies with the radio transceiver parameters. The analytical expressions are validated through extensive simulation experiments. I