On maximizing the lifetime of distributed information in ad-hoc networks with individual constraints

ABSTRACT

Ad-Hoc Networks and in particular sensor networks are networks of nodes with limited battery and limited processing capacity. As such, a single node carries an incentive to limit the amount of data it contains. This leads to the expiration of the data carried by the node after a period of time, due for instance, to a re-boot after an off period in the duty cycle, or to older information being "pushed" out by new data received by the mobile node. On the other hand, some data is critical to the functioning of the whole network. For instance, the existence and position of a gateway towards the infrastructure network should be kept somewhere in the network, so that nodes are able to recover this information when needed. In this paper, we study the trade-off between the finite lifetime of a piece of information at each node, and the survival of this information indefinitely within the network. We consider a simple dissemination process for the information akin to an AODV-based information request/reply mechanism. We show that the maximum number of hops in a request is a critical parameter to ensure the survivability indefinitely of any information within the network. We identify the parameter which minimizes the load on the network, for two typical ad-hoc network topologies: a square lattice, which accurately models the distribution of the nodes in a fixed and organized ad hoc or sensor network, and a n-ary tree, which models ad hoc networks for which routing is constructed so as to have no routing loops.

REFERENCES

• 1: Benjie Chen , Kyle Jamieson , Hari Balakrishnan , Robert Morris, Span: an energy-efficient coordination algorithm for topology maintenance in ad hoc wireless networks, Wireless Networks, v.8 n.5, p.481-494, September 2002 [doi>10.1023/A:1016542229220]
• 2: Gilbert E. Random Plane Networks J. Soc. Industrial Applied Mathematics, Vol. 9, No. 4, 1961, pp.533--43.
• 3: Handjani S. Survival of Threshold Contact Processes Journal of Theoretical Probability 10 (3): 737--746, July 1997.
• 4: Harris T.E. Contact Interactions on a Lattice in Annals of Probability, 1974, Vol.2, No. 6, 969--988.
• 5: Koodli R., Perkins C. Service Discovery in On-Demand Ad Hoc Networks IETF Manet Working Group, Internet Draft draft-koodli-manet-servicediscovery-00.txt, 9/2002.
• 6: Liggett T. Stochastic Interacting Systems Springer, 1999.
• 7: Pemantle R. The Contact Process on Trees Ann. Probab., 20, 2089 -- 2116 (1992)
• 8: Charles E. Perkins , Elizabeth M. Royer, Ad-hoc On-Demand Distance Vector Routing, Proceedings of the Second IEEE Workshop on Mobile Computer Systems and Applications, p.90, February 25-26, 1999
• 9: C. Greg Plaxton , Rajmohan Rajaraman , Andréa W. Richa, Accessing nearby copies of replicated objects in a distributed environment, Proceedings of the ninth annual ACM symposium on Parallel algorithms and architectures, p.311-320, June 23-25, 1997, Newport, Rhode Island, United States [doi>10.1145/258492.258523]
• 10: Ion Stoica , Robert Morris , David Karger , M. Frans Kaashoek , Hari Balakrishnan, Chord: A scalable peer-to-peer lookup service for internet applications, Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, p.149-160, August 2001, San Diego, California, United States
• 11: Wagner A., Anantharam V. Designing a Contact Process : The Piecewise-Homogeneous Process on a Finite Set with Applications. Stochastic Processes and their Applications (to appear, available from http://www.eecs.berkeley.edu/~ananth/).

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Stochastic processes

Additional Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Modeling techniques

  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval

General Terms:
Performance, Theory

Keywords:
ad-hoc networks, contact process, peer-to-peer systems, sensor networks