A Competitive Replica Placement Methodology for Ad Hoc Networks

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




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.