The Number of Neighbors Needed for Connectivity of Wireless Networks

The Number of Neighbors Needed for Connectivity of Wireless Networks

2004 | FENG XUE and P.R. KUMAR *
The paper "The Number of Neighbors Needed for Connectivity of Wireless Networks" by FENG XUE and P.R. KUMAR addresses the critical question of how many neighbors each node in a wireless network should connect to for the network to remain connected. Unlike wired networks, wireless networks do not have pre-established links; instead, nodes must form connections by selecting neighbors. The authors show that in a network with \( n \) randomly placed nodes, each node should be connected to \( \Theta(\log n) \) nearest neighbors. Specifically, if each node connects to fewer than \( 0.074 \log n \) neighbors, the network becomes asymptotically disconnected with probability one as \( n \) increases, while if each node connects to more than \( 5.1774 \log n \) neighbors, the network becomes asymptotically connected with probability approaching one as \( n \) increases. This contrasts with earlier work suggesting that the "magic number" of neighbors should be six or eight. The study also explores the trade-off between network connectivity and capacity, highlighting that while more links can reduce the relaying burden, they also increase interference, which can disconnect the network. The paper provides a detailed proof of the main result and discusses related literature, including studies on random graphs and continuum percolation theory.The paper "The Number of Neighbors Needed for Connectivity of Wireless Networks" by FENG XUE and P.R. KUMAR addresses the critical question of how many neighbors each node in a wireless network should connect to for the network to remain connected. Unlike wired networks, wireless networks do not have pre-established links; instead, nodes must form connections by selecting neighbors. The authors show that in a network with \( n \) randomly placed nodes, each node should be connected to \( \Theta(\log n) \) nearest neighbors. Specifically, if each node connects to fewer than \( 0.074 \log n \) neighbors, the network becomes asymptotically disconnected with probability one as \( n \) increases, while if each node connects to more than \( 5.1774 \log n \) neighbors, the network becomes asymptotically connected with probability approaching one as \( n \) increases. This contrasts with earlier work suggesting that the "magic number" of neighbors should be six or eight. The study also explores the trade-off between network connectivity and capacity, highlighting that while more links can reduce the relaying burden, they also increase interference, which can disconnect the network. The paper provides a detailed proof of the main result and discusses related literature, including studies on random graphs and continuum percolation theory.
Reach us at info@study.space
[slides] The Number of Neighbors Needed for Connectivity of Wireless Networks | StudySpace