On topology control and non-uniform node deployment in ad hoc networks

Topology control has been established as an efficient technique for improving the properties of wireless multi-hop networks. In this paper we first analyze the impact of non-uniform node placement on the effectiveness of traditional and well established topology control approaches that preserve connectivity with high probability, thus revealing and demonstrating their inefficiency in properly maintaining connectivity in the general case. Then, we propose a randomized topology control approach that provides significant improvements in percentage connectivity guarantees under arbitrary and more realistic node deployments. The proposed approach, referred to as Nearest Random Neighbors (NRN), is compared to the K-Neigh technique, one of the dominant Network layer topology control protocols. As opposed to K-Neigh, the NRN mechanism asserts acceptable network connectivity probabilities, even in cases of highly skewed node distributions, while its performance with respect to the average physical node degree remains stable and close to K-Neigh, even as the network density increases dramatically.