Query distribution estimation and predictive caching in mobile ad hoc networks

ABSTRACT

The problem of data management has been studied widely in the field of mobile ad-hoc networks and pervasive computing. The issue addressed is that finding the data required by a device depends on chance encounter with the source of data. Most existing research has focused on specifying the required data by specifying the user or application intentions. These approaches take the semantics of data into account while caching data onto mobile devices from the wired sources. We propose a scheme by which mobile devices proactively increase the availability of data by pushing and caching the most popular data in the network. It involves a local distributed technique for estimating global query distribution in the network. The devices have a finite sized cache to store the pushed data and use their estimation of queries for prioritizing the data to cache. We implement this technique in the network simulator, Glomosim and show that our scheme improves data availability as well as the response latency.

REFERENCES

• 1: http://dash.net.
• 2: http://mathworld.wolfram.com/RelativeEntropy.html.
• 3: Budiarto, S. Nishio, and M. Tsukamoto. Data management issues in mobile and peer-to-peer environments. Data Knowl. Eng., 41(2--3):183--204, June 2002.
• 4: M. Cherniack, M. J. Franklin, and S. Zdonik. Expressing user profiles for data recharging. Personal Communications, IEEE, 8(4):32--38, August 2001.
• 5: A. Patwardhan, A. Joshi, T. Finin, and Y. Yesha. A data intensive reputation management scheme for vehicular ad hoc networks. 3rd Annual International Conference on Mobile and Ubiquitous Systems - Workshops, pages 1--8, July 2006.
• 6: F. Perich, S. Avancha, D. Chakraborty, A. Joshi, and Y. Yesha. Profile driven data management for pervasive environments. Proceedings of the 13th International Conference on Database and Expert Systems Applications, pages 361--370, September 2002.
• 7: J. Shim, P. Scheuermann, and R. Vingralek. Proxy cache algorithms: Design, implementation, and performance. IEEE Trans. Knowledge and Data Eng., 11(4):549--562, July/August 1999.
• 8: Y.-L. Wu, D. Agrawal, and A. E. Abbadi. Query estimation by adaptive sampling. Proceedings of the ICDE Conference, pages 639--648, February 2002.
• 9: B. Xu and O. Wolfson. Data management in mobile peer-to-peer networks. 2nd International Workshop on Databases, Information Systems, and Peer-to-Peer Computing (DBISP2P'04), August 2004.
• 10: L. Yin and G. Cao. Supporting cooperative caching in ad hoc networks. IEEE Transactions on Mobile Computing, 5(1):77--89, January 2006.
• 11: X. Zeng, R. Bagrodia, and M. Gerla. Glomosim: A library for parallel simulation of large-scale wireless networks. Workshop on Parallel and Distributed Simulation, pages 154--161, July/August 1998.

INDEX TERMS

Keywords:
increase data availability, mobile ad hoc networks, query distribution estimation