Investigations on Client –Side Data Caching Policies for Location Dependent Data in Mobile Environments

Abstract

The explosive growth of wireless communication technologies, wireless portable devices, mobile application standards and supporting software technologies has led to larger usage of mobile data services. However, various constraints such as limited wireless bandwidth client resources remain barriers to the complete utilization of mobile data services. Data management is a key issue in mobile computing and has aroused much attention since it is challenging to process information on the move, to cope with resource limitations, and to deal with heterogeneity. Among the applications of mobile data management, Location Based Services (LBS) have been identified as one of the most promising area of research and development. These services integrate geographical location and end-user context dynamically to deliver the necessary information. Thus, sophisticated data management and resource management techniques are needed for the enhancement of the performance of these data services. A key characteristic of LBS is that the same service request may need to be answered with complete different results as the user changes his location or as the targets move. Because of the highly dynamic nature of the problem, traditional information management techniques are not well suited for LBS. Caching techniques specially tailored for LBS or mobile computing environments have also been a major research area. The effect of cache is more dramatic in a mobile computing environment because contacting the iv server for data is very expensive in wireless networks and may be impossible if the mobile client is disconnected. This work attempts to address some of the performance issues by applying advanced client data caching techniques. This research work addresses three key issues namely, cache invalidation, cache replacement and cache prefetch under the constraints of location-dependent data. Caching is a data replication mechanism in which copies of data are brought to a mobile unit as a response to a query and retained at the cache for possible use by subsequent queries. In LBS, some query results may have an extremely low likelihood of being used in the near future due to mobility and spatiotemporal constraints. The ability of identifying such items and replacing them can greatly increase the cache hit ratio and improve the overall cache performance. Thus, there is a need for efficient cache replacement algorithms to find out suitable subset of data items for eviction from cache. The issues of cache replacement for location-dependent data under a geometric location model are studied and a cache replacement policy (RAAR) has been proposed by taking into account the spatial and temporal parameters. The fundamental requirement of the cache replacement policy is to retain all items that will potentially be requested by subsequent queries thereby increasing cache hits. The set of critical factors to be considered in making the cache replacement decision has been studied and incorporated into the replacement policy. Cache hit ratio is employed as the primary performance metric. A series of experiments are conducted to evaluate the proposed replacement policy. v The idea behind prefetching is to transfer information, which the user might need in the future, into the client cache before it is requested. Prefetching is an attempt to reduce communication cost so that upcoming requests could be answered from cache. The strategy is to pre-fetch the most likely item to be accessed in near future by considering the semantic and spatial adjacency and to store them in advance so that future queries could be answered from client cache. The items to be pre-fetched are determined from history by using association rules. Prefetching and replacement are intertwined, and cannot be studied in isolation and hence a cache replacement algorithm to suit the pre-fetching environment has been proposed. Experimental analysis and results show a significant increase in cache hit ratio of mobile clients. An attempt is made to reduce the wastage of prefetched items. The objective is to prefetch and replace judiciously, keeping the number of wasted prefetched items to a minimum. This is achieved by logically partitioning the client by recording dual Valid Scopes for invalidation. This scheme shows improvements with respect to cache hit ratio and prefetch wastage A semantic caching mechanism to answer nearest neighbour and range queries from the cache is proposed. The possibility of clients issuing a combination of range and NN queries has been taken into consideration. Valid scopes and dummy objects are used to record the invalidation information. The performance of this proposed model is tested with LRU, FAR and RAAR replacement polices. Cache hit ratio is used as metric for performance evaluation. Simulation studies showed that RAAR outperforms the traditional policies.