Benefit-Based Data Caching in Ad Hoc Networks
- 22 January 2008
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Mobile Computing
- Vol. 7 (3), 289-304
- https://doi.org/10.1109/tmc.2007.70770
Abstract
Data caching can significantly improve the efficiency of information access in a wireless ad hoc network by reducing the access latency and bandwidth usage. However, designing efficient distributed caching algorithms is nontrivial when network nodes have limited memory. In this article, we consider the cache placement problem of minimizing total data access cost in ad hoc networks with multiple data items and nodes with limited memory capacity. The above optimization problem is known to be NP-hard. Defining benefit as the reduction in total access cost, we present a polynomial-time centralized approximation algorithm that provably delivers a solution whose benefit is at least 1/4 (1/2 for uniform-size data items) of the optimal benefit. The approximation algorithm is amenable to localized distributed implementation, which is shown via simulations to perform close to the approximation algorithm. Our distributed algorithm naturally extends to networks with mobile nodes. We simulate our distributed algorithm using a network simulator (ns2) and demonstrate that it significantly outperforms another existing caching technique (by Yin and Cao [33]) in all important performance metrics. The performance differential is particularly large in more challenging scenarios such as higher access frequency and smaller memory.Keywords
This publication has 26 references indexed in Scilit:
- Benefit-based Data Caching in Ad Hoc NetworksPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2006
- Energy-conserving data placement and asynchronous multicast in wireless sensor networksPublished by Association for Computing Machinery (ACM) ,2003
- Improved combinatorial algorithms for the facility location and k-median problemsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- Heat and Dump: competitive distributed pagingPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Primal-Dual Algorithms for Connected Facility Location ProblemsLecture Notes in Computer Science, 2002
- Proactive power-aware cache management for mobile computing systemsIEEE Transactions on Computers, 2002
- Web caching and Zipf-like distributions: evidence and implicationsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1999
- A performance comparison of multi-hop wireless ad hoc network routing protocolsPublished by Association for Computing Machinery (ACM) ,1998
- An O(pn2) algorithm for the p-median and related problems on tree graphsOperations Research Letters, 1996
- Highly dynamic Destination-Sequenced Distance-Vector routing (DSDV) for mobile computersPublished by Association for Computing Machinery (ACM) ,1994