Energy-efficient caching strategies in ad hoc wireless networks

ABSTRACT

In this paper, we address the problem of energy-conscious cache placement in wireless ad hoc networks. We consider a network comprising a server with an interface to the wired network, and some nodes requiring access to the information stored at the server. In order to reduce access latency in such a communication environment, an effective strategy is caching the server information at some nodes distributed across the network. Caching, however, can considerably impact the system energy expenditure; for instance, disseminating information incurs additional energy burden. Since wireless devices have limited amounts of available energy, we need to design caching strategies that optimally trade-off between energy consumption and access latency. We pose our problem as an integer linear program. We show that this problem is the same as a special case of the connected facility location problem, which is known to be NP-hard. We devise a polynomial time algorithm which provides a sub-optimal solution. The proposed algorithm applies to any arbitrary network topology and can be implemented in a distributed and asynchronous manner. In the case of a tree topology, our algorithm gives the optimal solution. In the case of an arbitrary topology, it finds a feasible solution with an objective function value within a factor of 6 of the optimal value. This performance is very close to the best approximate solution known today, which is obtained in a centralized manner. We compare the performance of our algorithm against three candidate caching schemes, and show via extensive simulation that our algorithm consistently outperforms these alternative schemes.

REFERENCES

• 1: Bluetooth core specification. http://www.bluetooth.com/dev/specifications.asp.
• 2: Local and metropolitan area networks: Wireless LAN. ANSI/IEEE Standard 802.11, 1999.
• 3: I. Cidon, S. Kutten, and R. Soffer. Optimal allocation of electronic content. In IEEE INFOCOM 2001, April 2001.
• 4: Brian D. Davison, A Web Caching Primer, IEEE Internet Computing, v.5 n.4, p.38-45, July 2001 [doi>10.1109/4236.939449]
• 5: M. Gerla, R. Bagrodia, L. Zhang, K. Tang, and L. Wang. Tcp over wireless multihop protocols: Simulation and experiments. In IEEE ICC 1999, June 1999.
• 6: M. Grossglauser and D. N. C. Tse. Mobility increases the capacity of ad-hoc wireless networks. In IEEE INFOCOM 2001, pages 1360--1369, 2001.
• 7: Yixiu Huang , Prasad Sistla , Ouri Wolfson, Data replication for mobile computers, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.13-24, May 24-27, 1994, Minneapolis, Minnesota, United States
• 8: David Kotz , Kobby Essien, Analysis of a campus-wide wireless network, Proceedings of the 8th annual international conference on Mobile computing and networking, September 23-28, 2002, Atlanta, Georgia, USA [doi>10.1145/570645.570659]
• 9: B. Li, M. J. Golin, G. F. Ialiano, and X. Deng. On the optimal placement of web proxies in the internet. In IEEE INFOCOM 1999, March 1999.
• 10: P. Mirchandani and R. Francis. Discrete location theory. John Wiley and Sons, New York City, NY, 1990.
• 11: C. E. Perkins and E. M. Royer. Ad hoc on demand distance vector (aodv) routing. pages 90--100, February 1999.
• 12: L. Qiu, V. N. Padmanabhan, and G. M. Voelker. On the placement of web server replicas. In IEEE INFOCOM 2001, pages 1587--1596, 2001.
• 13: 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
• 14: Chaitanya Swamy , Amit Kumar, Primal-Dual Algorithms for Connected Facility Location Problems, Proceedings of the 5th International Workshop on Approximation Algorithms for Combinatorial Optimization, p.256-270, September 17-21, 2002
• 15: Vijay V. Vazirani, Approximation algorithms, Springer-Verlag New York, Inc., New York, NY, 2001
• 16: Jia Wang, A survey of web caching schemes for the Internet, ACM SIGCOMM Computer Communication Review, v.29 n.5, October 1999 [doi>10.1145/505696.505701]
• 17: P. Winter, Steiner problem in networks: a survey, Networks, v.17 n.2, p.129-167, Summer 1987 [doi>10.1002/net.3230170203]
• 18: Z. Xiang, Z. Zhong, and Y. Zhong. A cache cooperation management for wireless multimedia streaming. In IEEE International Conferences on Info-tech and Info-net ICII 2001, pages 328--333, 2001.
• 19: J. Xu, B. Li, and D. L. Lee. Placement problems for transparent data replication proxy services. IEEE Journal on Selected Areas in Communications, 20(7):1383--98, September 2002.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Wireless communication

General Terms:
Algorithms, Performance

Keywords:
ad hoc networks, caching