3DLS: density-driven data location service for mobile ad-hoc networks

ABSTRACT

Finding data items is one of the most basic services of any distributed system. It is particular challenging in ad-hoc networks, due to their inherent decentralized nature and lack of infrastructure. A data location service (DLS) provides this capability. This paper presents 3DLS, a novel density driven data location service. 3DLS is based on performing biased walks over a density based virtual topography. 3DLS also includes an autonomic dynamic configuration mechanism for adapting the lengths of the walks, in order to ensure good performance in varying circumstances and loads. This is without any explicit knowledge of the network characteristics, such as size, mobility speed, etc. Moreover, 3DLS does not rely on geographical knowledge, its decisions are based only on local information, it does not invoke multi-hop routing, and it avoids flooding the network. The paper includes a detailed performance study of 3DLS, carried by simulations, which compares 3DLS to other known approaches. The simulations results validate the viability of 3DLS.

REFERENCES

• 1: Ittai Abraham , Danny Dolev , Dahlia Malkhi, LLS: a locality aware location service for mobile ad hoc networks, Proceedings of the 2004 joint workshop on Foundations of mobile computing, October 01-01, 2004, Philadelphia, PA, USA [doi>10.1145/1022630.1022643]
• 2: K.N. Amouris, S. Papavassiliou, and M. Li. A Position Based Multi-Zone Routing Protocol for Wide Area Mobile Ad-Hoc Networks. In VTC, pages 1365--1369, July 1999.
• 3: S. Bashir and B. Li. KELOP: Distributed Key-Value Lookup in Wireless Ad Hoc Networks. In ICCCN, pages 471--476, 2003.
• 4: Yatin Chawathe , Sylvia Ratnasamy , Lee Breslau , Nick Lanham , Scott Shenker, Making gnutella-like P2P systems scalable, Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, August 25-29, 2003, Karlsruhe, Germany [doi>10.1145/863955.864000]
• 5: H. Cheng, J. Cao, and H. Chen. GrLS: Group-Based Location Service in Mobile Ad Hoc Networks. In ICC, pages 4734--4740, June 2007.
• 6: T. Clausen, C. Dearlove, and J. Dean. MANET Neighborhood Discovery Protocol (NHDP). IETF draft, July 2008.
• 7: C. Cramer and T. Fuhrmann. ISPRP: A Message-Efficient Protocol for Initializing Structured P2P Networks. IPCCC, pages 365--370, April 2005.
• 8: Roy Friedman , Maria Gradinariu , Gwendal Simon, Locating cache proxies in manets, Proceedings of the 5th ACM international symposium on Mobile ad hoc networking and computing, May 24-26, 2004, Roppongi Hills, Tokyo, Japan [doi>10.1145/989459.989482]
• 9: R. Friedman and G. Kliot. Location Services in Wireless Ad Hoc and Hybrid Networks: A Survey. Technical report, Technion Computer Science, April 2006.
• 10: R. Friedman, G. Kliot, and C. Avin. Probabilistic Quorum Systems in Wireless Ad Hoc Networks. In DSN, July 2008.
• 11: V. Gianuzzi. File Distribution and Caching in MANET. Technical Report DISI-TR-03-03, DISI Tech University of Genova, 2003.
• 12: P. Gupta and P. Kumar. Critical power for asymptotic connectivity in wireless networks. Stochastic Analysis, Control, Optimization and Applications, pages 547--566, October 1998.
• 13: S. Iyer K. Patel and K. Paul. RINGS: Lookup Service for Peer-to-Peer Systems in Mobile Ad-Hoc Networks. In IWDC, pages 27--30, December 2004.
• 14: Vincent Lenders , Martin May , Bernhard Plattner, Service Discovery in Mobile Ad Hoc Networks: A Field Theoretic Approach, Proceedings of the Sixth IEEE International Symposium on World of Wireless Mobile and Multimedia Networks, p.120-130, June 13-16, 2005 [doi>10.1109/WOWMOM.2005.93]
• 15: Jinyang Li , John Jannotti , Douglas S. J. De Couto , David R. Karger , Robert Morris, A scalable location service for geographic ad hoc routing, Proceedings of the 6th annual international conference on Mobile computing and networking, p.120-130, August 06-11, 2000, Boston, Massachusetts, United States [doi>10.1145/345910.345931]
• 16: Christoph Lindemann , Oliver P. Waldhorst, Consistency mechanisms for a distributed lookup service supporting mobile applications, Proceedings of the 3rd ACM international workshop on Data engineering for wireless and mobile access, September 19-19, 2003, San Diego, CA, USA [doi>10.1145/940923.940936]
• 17: Dandan Liu , Xiaohua Jia , Ivan Stojmenović, Quorum and connected dominating sets based location service in wireless ad hoc, sensor and actuator networks, Computer Communications, v.30 n.18, p.3627-3643, December, 2007 [doi>10.1016/j.comcom.2007.07.001]
• 18: Zambonelli F. Mamei M. Location-based and Content based Information Access in Mobile Peer-to-Peer Computing: the TOTA Approach. In AP2PC, pages 162--173, July 2003.
• 19: Ruggero Morselli , Bobby Bhattacharjee , Aravind Srinivasan , Michael A. Marsh, Efficient lookup on unstructured topologies, Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computing, July 17-20, 2005, Las Vegas, NV, USA [doi>10.1145/1073814.1073828]
• 20: Charles E. Perkins, Ad Hoc Networking, Addison-Wesley Professional, 2008
• 21: Himabindu Pucha , Saumitra M. Das , Y. Charlie Hu, Ekta: An Efficient DHT Substrate for Distributed Applications in Mobile Ad Hoc Networks, Proceedings of the Sixth IEEE Workshop on Mobile Computing Systems and Applications, p.163-173, December 02-03, 2004 [doi>10.1109/MCSA.2004.11]
• 22: Sylvia Ratnasamy , Paul Francis , Mark Handley , Richard Karp , Scott Schenker, A scalable content-addressable network, Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, p.161-172, August 2001, San Diego, California, United States
• 23: Antony I. T. Rowstron , Peter Druschel, Pastry: Scalable, Decentralized Object Location, and Routing for Large-Scale Peer-to-Peer Systems, Proceedings of the IFIP/ACM International Conference on Distributed Systems Platforms Heidelberg, p.329-350, November 12-16, 2001
• 24: Françoise Sailhan , Valérie Issarny, Energy-Aware Web Caching for Mobile Terminals, Proceedings of the 22nd International Conference on Distributed Computing Systems, p.820-825, July 02-05, 2002
• 25: I. Sheriff, P.A.K. Acharya, A. Sampath, B.Y. Zhao, and E. Belding--Royer. Integrated Data Location in Multihop Wireless Networks. In COMSWARE, pages 1--10, January 2007.
• 26: 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
• 27: J. Tchakarov and N. Vaidya. Efficient Content Location in Mobile Ad hoc Networks. In MDM, pages 74--85, January 2004.
• 28: L. Yin and G. Cao. Supporting Co-operative Caching in Ad Hoc Networks. In INFOCOM, pages 2537--2547, March 2004.
• 29: T. Zahn and J. Schiller. MADPastry: A DHT substrate for practicably sized MANETs. In ASWN, June 2005.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols

Additional Classification:
  E. Data
  E.0 GENERAL

General Terms:
Performance, Reliability

Keywords:
ad-hoc networks, data location service, virtual topography