Please use this identifier to cite or link to this item: https://doi.org/10.1109/TNET.2006.882863
Title: Efficient cache placement in multi-hop wireless networks
Authors: Nuggehalli, P.
Srinivasan, V. 
Chiasserini, C.-F.
Rao, R.R.
Keywords: Heuristic optimization
Web cache placement
Wireless multi-hop networks
Issue Date: Oct-2006
Source: Nuggehalli, P., Srinivasan, V., Chiasserini, C.-F., Rao, R.R. (2006-10). Efficient cache placement in multi-hop wireless networks. IEEE/ACM Transactions on Networking 14 (5) : 1045-1055. ScholarBank@NUS Repository. https://doi.org/10.1109/TNET.2006.882863
Abstract: In this paper, we address the problem of efficient cache placement in multi-hop wireless networks. We consider a network comprising a server with an interface to the wired network, and other 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 of the nodes distributed across the network. Caching, however, can imply a considerable overhead cost; for instance, disseminating information incurs additional energy as well as bandwidth burden. Since wireless systems are plagued by scarcity of available energy and bandwidth, we need to design caching strategies that optimally trade-off between overhead cost 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 suboptimal 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 cache placement schemes, and show via extensive simulation that our algorithm consistently outperforms these alternative schemes. © 2006 IEEE.
Source Title: IEEE/ACM Transactions on Networking
URI: http://scholarbank.nus.edu.sg/handle/10635/50909
ISSN: 10636692
DOI: 10.1109/TNET.2006.882863
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

SCOPUSTM   
Citations

24
checked on Dec 14, 2017

WEB OF SCIENCETM
Citations

14
checked on Nov 18, 2017

Page view(s)

32
checked on Dec 10, 2017

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.