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.
Energy-Efficient Caching Strategies in Ad Hoc Wireless Networks / P. NUGGEHALLI; V. SRINIVASAN; CHIASSERINI C.F.; R.R. RAO. - STAMPA. - (2003), pp. 25-34. ((Intervento presentato al convegno ACM MobiHoc 2003 nel Giugno [10.1145/778415.778419].
Titolo: | Energy-Efficient Caching Strategies in Ad Hoc Wireless Networks | |
Autori: | ||
Data di pubblicazione: | 2003 | |
Abstract: | In this paper, we address the problem of energy-conscious cache placement in wireless ad hoc netw...orks. 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. | |
ISBN: | 1581136846 | |
Appare nelle tipologie: | 4.1 Contributo in Atti di convegno |
File in questo prodotto:
File | Descrizione | Tipologia | Licenza | |
---|---|---|---|---|
MobiHoc_2003.pdf | 2. Post-print / Author's Accepted Manuscript | Non Pubblico - Accesso privato/ristretto | Administrator Richiedi una copia |
http://hdl.handle.net/11583/1408802