Research Article
Local vs. Global Scalability in Ad Hoc and Sensor Networks
@INPROCEEDINGS{10.1007/978-3-642-10485-5_3, author={Andr\^{a}s Farag\^{o}}, title={Local vs. Global Scalability in Ad Hoc and Sensor Networks}, proceedings={Scalable Information Systems. 4th International ICST Conference, INFOSCALE 2009, Hong Kong, June 10-11, 2009, Revised Selected Papers}, proceedings_a={INFOSCALE}, year={2012}, month={5}, keywords={Scalability network topology connectivity node degrees}, doi={10.1007/978-3-642-10485-5_3} }
- András Faragó
Year: 2012
Local vs. Global Scalability in Ad Hoc and Sensor Networks
INFOSCALE
Springer
DOI: 10.1007/978-3-642-10485-5_3
Abstract
We address large, random network topologies that are typical in ad hoc and sensor networks. In these systems we need at least two different types of scalability. First, we want that with growing network size the topology remains connected, so that communication is possible between nodes. Second, it is also necessary that the individual nodes can operate with limited energy and complexity, which requires that the number of neighbors of any node remains bounded. Unfortunately, these global vs. local scalability requirements conflict with each other, as it is known, under very general conditions, that full connectivity can only be achieved with infinitely growing node degrees. Therefore, it is important to quantify how large part of the random topology can be still expected to belong to a connected component if the nodes are confined to some bounded degree. We investigate this issue in a model that is more general than previously investigated random wireless network topology models. In our general model we derive an asymptotically optimal trade-off between node degrees and the fraction of nodes that form a connected component.