A Competitive Replica Placement Methodology for Ad Hoc Networks

Authors: Samee Ullah Khan, C. Ardil

Abstract:

In this paper, a mathematical model for data object replication in ad hoc networks is formulated. The derived model is general, flexible and adaptable to cater for various applications in ad hoc networks. We propose a game theoretical technique in which players (mobile hosts) continuously compete in a non-cooperative environment to improve data accessibility by replicating data objects. The technique incorporates the access frequency from mobile hosts to each data object, the status of the network connectivity, and communication costs. The proposed technique is extensively evaluated against four well-known ad hoc network replica allocation methods. The experimental results reveal that the proposed approach outperforms the four techniques in both the execution time and solution quality

Keywords: Data replication, auctions, static allocation.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1076990

References:

[1] D. Barbara and T. Imielinski, "Sleepers and Workaholics: Caching Strategies in Mobile Environments," in ACM SIGMOD, 1994, pp. 1-12.
[2] J. Cay, K. L. Tan and B. C. Ooi, "On Incremental Cache Coherency Schemes in Mobile Computing Environments, in IEEE International Conference on Data Engineering, 1997, pp. 114-123.
[3] M. Crovella and A. Bestavros, "Self-Similarity in World Wide Web Traffic: Evidence and Possible Causes," IEEE/ACM Transactions on Networking, 5(6), pp. 835-846, 1997.
[4] V. Grassi, "Prefetching Policies for Energy Saving and Latency Reduction in a Wireless Broadcast Data Delivery System," in ACM International Workshop on Modeling, 2000, pp. 77-84.
[5] T. Hara, "Effective Replica Allocation in Ad Hoc Networks for Improving Data Accessibility," in IEEE INFOCOM, 2001, pp. 1568- 1576.
[6] T. Hara, "Replica Allocation in Ad Hoc Networks with Data Update," Mobile Networks and Applications, vol. 8, pp. 343-354, 2003.
[7] T. Hara and S. K. Madria, "Dynamic Data Replication Using Aperiodic Updates in Mobile Adhoc Networks," in 9th International Conference on Database Systems for Advance Applications, 2004, pp. 869-881.
[8] Y. Huang, P. Sistla and O. Wolfson, "Data Replication for Mobile Computer," inACM SIGMOD, 1994, pp. 13-24.
[9] J. Jing, A. Elmagarmid, A. Helal and R. Alonso, "Bit-sequences: An Adaptive Cache Invalidation Method in Mobile Client/Server Environments," Mobile Networks and Applications, 2(2), pp. 115-127, 1997.
[10] S. Khan and I. Ahmad, "A Powerful Direct Mechanism for Optimal WWW Content Replication," in 19th IEEE International Parallel and Distributed Processing Symposium, 2005.
[11] E. Pitoura and B. Bhargava, Maintaining Consistency of Data in Mobile Distributed Environments, in IEEE International Conference on Distributed Systems, 1995, pp. 404-413.
[12] S. Saurabh and D. Parkes, "Hard-to-Manipulate VCG-Based Auctions," Technical Report, Harvard University, 2004.
[13] K. L.Wu, P. S. Yu and M. S. Chen, "Energy-efficient Caching for Wireless Mobile Computing, in IEEE International Conference on Data Engineering, 1996, pp. 336-343.
[14] W. Vickrey, "Counterspeculation, Auctions and Competitive Sealed Tenders," Journal of Finance, pp. 8-37, 1961.
[15] G. Zipf, Human Behavior and the Principle of Least-Effort, Addison Wesley, Cambridge, MA, 1949.