Journal
WIRELESS NETWORKS
Volume 10, Issue 2, Pages 169-181Publisher
SPRINGER
DOI: 10.1023/B:WINE.0000013081.09837.c0
Keywords
wireless networks; connectivity; ad hoc networks; transmission range control
Ask authors/readers for more resources
Unlike wired networks, wireless networks do not come with links. Rather, links have to be fashioned out of the ether by nodes choosing neighbors to connect to. Moreover the location of the nodes may be random. The question that we resolve is: How many neighbors should each node be connected to in order that the overall network is connected in a multi-hop fashion? We show that in a network with n randomly placed nodes, each node should be connected to Theta(log n) nearest neighbors. If each node is connected to less than 0.074 log n nearest neighbors then the network is asymptotically disconnected with probability one as n increases, while if each node is connected to more than 5.1774 log n nearest neighbors then the network is asymptotically connected with probability approaching one as n increases. It appears that the critical constant may be close to one, but that remains an open problem. These results should be contrasted with some works in the 1970s and 1980s which suggested that the magic number of nearest neighbors should be six or eight.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available