05-02-2013, 03:45 PM
Benefit-Based Data Caching in Ad-hoc Networks
1Benefit-Based Data.doc (Size: 242.5 KB / Downloads: 22)
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 non-trivial when network nodes have limited memory.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 one-fourth (one-half 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,and demonstrate that it significantly outperforms another existing caching technique in all important performance metrics. The performance differential is particularly large in more challenging scenarios, such as higher access frequency and smaller memory.
INTRODUCTION
AD hoc networks are multi hop wireless networks of small computing devices with wireless interfaces. The computing devices could be conventional computers (for example, PDA, laptop, or PC) or backbone routing platforms or even embedded processors such as sensor nodes. The problem of optimal placement of caches to reduce overall cost of accessing data is motivated by the following two defining characteristics of ad hoc networks. First, the adhoc networks are multi hop networks without a central base station. Thus, remote access of information typically occurs via multi hop routing, which can greatly benefit from caching to reduce access latency. Second, the network is generally resource constrained in terms of channel band width or battery power in the nodes. Caching helps in reducing communication, which results in savings in band width, as well as battery energy. The problem of cache placement is particularly challenging when each network node has a limited memory to cache data items. In this paper, our focus is on developing efficient caching techniques in ad hoc networks with memory limitations.
Research into data storage, access, and dissemination techniques in ad hoc networks is not new. In particular, these mechanisms have been investigated in connection with sensor networking, peer-to-peer networks, mesh networks, world wide Web, and even more general ad hoc networks. However, the presented approaches have so far been somewhat “ad hoc” and empirically based, without any strong analytical foundation. In contrast, the theory literature abounds in analytical studies into the optimality properties of caching and replica allocation problems. However, distributed implementations of these techniques and their performances in complex network settings have not been investigated. It is even unclear whether these techniques are amenable to efficient distributed implementations. Our goal in this paper is to develop an approach that is both analytically tractable with a provable performance bound in a centralized setting and is also amenable to a natural distributed implementation. In our network model, there are multiple data items each data item has a server, and a set of clients that wish to access the data item at a given frequency. Each node carefully chooses data items to cache in its limited memory to minimize the overall access cost. Essentially, in this article, we develop efficient strategies to select data items to cache at each node.
EXISTING SYSTEM
Ad hoc networks are multi hop wireless networks of small computing devices with wireless interfaces. The computing devices could be conventional computers (e.g., PDA, laptop, or PC) or backbone routing platforms, or even embedded processors such as sensor nodes. The problem of optimal placement of caches to reduce overall cost of accessing data is motivated by the following two defining characteristics of ad hoc networks. Firstly, the ad hoc networks are multi hop networks without a central base station. Thus, remote access of information typically occurs via multi-hop routing, which can greatly benefit from caching to reduce access latency. Secondly, the network is generally resource constrained in terms of channel bandwidth or battery power in the nodes. Caching helps in reducing communication, which results in savings in bandwidth as well as battery energy. The problem of cache placement is particularly challenging when each network node has limited memory to cache data items.