Scalable Information Systems. 4th International ICST Conference, INFOSCALE 2009, Hong Kong, June 10-11, 2009, Revised Selected Papers

Research Article

Local vs. Global Scalability in Ad Hoc and Sensor Networks

Download
434 downloads
  • @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
András Faragó1,*
  • 1: The University of Texas at Dallas
*Contact email: farago@utdallas.edu

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.