A bridge between theory and practice for critical wireless radius/power design
Summary
Wireless sensor and ad hoc network design involves a key question: what is the critical radius/power each node should use or the critical link quality each link should maintain to keep the network connected? In a Bernoulli graph that consists of N nodes where edges are chosen independently and with probability p, the critical p ensuring a connected graph is Pc=[logN+c(N)]/N [1]. In a unit area containing N nodes, each having the same communication radius r, the critical r ensuring a connected graph is Rc=[logN+c(N)]/N [2]. However those c(N) expressions are not determinate, which challenges network designers in how to apply the above-mentioned theoretical results to guide network parameter design in practice. Our latest result [3] provides determinate bounds for the critical radius/power in one dimensional line network, such as wireless sensor networks for bridge monitoring aplications: In a unit length containing N nodes, each having the same communication radius r, the critical r ensuring a connected graph is Rc where lnN/N =< Rc <= 2lnN/N. This result helps bridge the gap between theory and practice.
A chronological list of related work
Connectivity in a Bernoulli graph:
Pc=[logN+c(N)]/N, 1985
Connectivity in a 2D wireless network:
Rc=[logN+c(N)]/N, 1998
Connectivity in a 1D wireless network:
our result lnN/N =< Rc <= 2lnN/N, 2011
Reference
[1] Bela Bollobas, Random Graphs, Cambridge University Press, 1985.
[2] Gupta and Kumar, Critical power for asymptotic connectivity in wireless networks, Stochastic Analysis, Control, Optimization and Applications, 1998.
[3] Li and Cheng, Determinate Bounds of Design Parameters for Critical Connectivity in Wireless Multi-hop Line Networks, IEEE WCNC 2011.