Brief announcement: (more) efficient pruning of ad-hoc wireless networks

ABSTRACT

To what extent can one "prune" the links in a wireless network while retaining (almost) the same connectivity achieved when each node is connected to all nodes within its communication radius? In a nutshell, if each node explores a portion of its neighborhood sufficient to reach ≈ log(1/ε) other nodes in expectation, w.h.p. all but a fraction ε of the network joins the same connected component. Each node can then "locally" choose to maintain (at most) 4 links, and the network still retains w.h.p. essentially the same level of connectivity.

REFERENCES

• 1: http://www.dei.unipd.it/~enoch/papers/pruning.pdf
• 2: P. Crescenzi, C. Nocentini, A. Pietracaprina, G. Pucci, and C. Sandri. On the connectivity of bluetooth-based ad hoc networks. In Proc. of Euro-Par, pp. 960--969, 2007.
• 3: D. Dubhashi , C. Johansson , O. Häggström , A. Panconesi , M. Sozio, Irrigating ad hoc networks in constant time, Proceedings of the seventeenth annual ACM symposium on Parallelism in algorithms and architectures, July 18-20, 2005, Las Vegas, Nevada, USA [doi>10.1145/1073970.1073986]
• 4: M. Penrose. Random geometric graphs. Oxford Un. Press, 2003.
• 5: Roberto Di Pietro , Luigi V. Mancini , Alessandro Mei , Alessandro Panconesi , Jaikumar Radhakrishnan, Redoubtable Sensor Networks, ACM Transactions on Information and System Security (TISSEC), v.11 n.3, p.1-22, March 2008 [doi>10.1145/1341731.1341734]
• 6: E.D. Santis, F. Grandoni, and A. Panconesi. Fast low degree connectivity of ad-hoc networks via percolation. In Proc. of ESA, pp. 206--217, 2007.
• 7: E. Vergetis, R. Guerin, S. Sarkar, and J. Rank. Can Bluetooth succeed as a large-scale ad hoc networking technology? IEEE J. on Sel. Areas in Commun., 23(3), pp. 644--656, 2005.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Network topology

General Terms:
Reliability, Theory

Keywords:
ad-hoc, connectivity, pruning, wireless