Keywords

1 Introduction

Location-Based Services (LBS) are one of the emerging applications among various mobile and wireless based technology. LBS provide context aware information to the client at the right time in the right place. Many of the technological constrains are added to these applications to maintain integrity and consistency of result acquired from LBS-Server. The basic reference architecture of mobile databases contains three entities: fixed hosts, mobile units, and base stations. Mobile units are low power moving object having lesser computational functionality that move around a geographical region. These geographical regions are basically divided into wireless cells i.e. mobile client contains data centric applications and roams between wireless cells. LBSs [1, 2] are gaining popularity in current trends where most of the applications use some context-aware information included with the mobile host. Context-aware information includes time, location, and device identity nearby to a given entity. The potential sources of this information are web browser, camera, microphone, GPS Receiver, a server associated with the given entity. Here, entity can be person, device, or application. Location services can be characterized as services that incorporate a cell phone’s area or position with other data to give enhanced value to user. It answers the location-related queries which are initiated by moving user, where the location is the parameter of the query which are provided to the client either explicitly with query or implicitly using a global positioning system (GPS). Some of the applications [3,4,5,6,7] which are gaining popularity in our daily life can be local information access (Traveler information system, navigation maps, news etc.). Apart from this, user makes some nearest-neighbor queries (show me all nearest hotel, ATM, Saloon).

The rest of this paper is organized as follows. Section 2 explores the issues and research challenges important for the performance of LBS. Sections 3 and 4 describes the contributions, major findings of our experimentations. Section 5 has given conclusion and scope for future works in LBS.

2 Performance Issues and Research Challenges

Numerous research works have been done separately on Predictability & Consistency of LBS. To maintain consistency in nearest-neighbor based applications, system needs to identify the data-item’s valid scope and store it with them in the cache [8,9,10]. Due to the associated valid scope with given data item, the user might reject the received result if user has moved to different places and may ask to the server for reprocessing of the query to get valid result. To improve the performance of the system, there should be some mechanism to obtain fast and accurate answers to issued queries. Very little works has been done to optimize the location dependent query processing [11,12,13,14]. Data replication is employed in any distributed system to improve reliability and reduce communication costs and response time thus to reduce the incurred network traffic. Data replication technique creates various copies of same data and place it to various nodes based on some performance criteria. The problem of replication in LBS is to find the number of replica that system should create, the place where it should be put and maintain the consistency among various replica for better performance of given system [15,16,17]. The bandwidth of downlink communication is much greater than that of the uplink communication. The policy [18] should be designed in such a way that messages sent to the server would be less than message received from server. The order in which the query executed is defined as query scheduling [19,20,21]. Mobility of users makes it more challenging to handle the query scheduling task. One of the limitations in mobile host is its limited battery power. So this is also a considerable issue while making any application for mobile environment as if processing power is restrained; it compromises the capability of every mobile node offering applications and services [22, 23]. Based on previous theoretical studies and concepts, many focused implementations and simulation [24,25,26] has been done. However, none of the previous simulations has complete prototype consisting of all of the functionality for LBS. So, one of the important issues is implementation of complete prototype [27] for consistent location aware system.

2.1 Predictability and Consistency

For Nearest-Neighbor query applications, the cached spatial data result may become invalid because of the client movement. To maintain consistency, system needs to identify the data-item’s valid scope and store it with them in the cache [8,9,10]. The concept of valid scope information was first proposed by Zheng et al. [8], in which it was used to assemble a semantic cache that allows you to reuse the cached data. GPS serves to identification of the location of any mobile device in geometric location model. The ancient policy particularly Polygonal Endpoints and Approximate Circle schemes show poor performance for invalidation information in terms of overhead and imprecision. In [9] Kumar et al. gives a comparison of various methods to find best suitable candidate for valid scope (i.e. best suitable sub polygon of a given polygon). They proposed a generalized algorithm known as CEB_G which improves the caching efficiency in comparison to that of basic CEB algorithm. The CEB_G algorithm adjusts the overhead and accuracy of valid scope. Moreover, to further improve caching efficiency they proposed a new algorithm CEFAB which considers user’s movement pattern and speculation for its future access.

2.2 Cache Replacement Policy

Whenever a query issued, if cache doesn’t contains searched data items then system execute replacement process. The problem is to be addressed and also improve cache-hit ratio [28,29,30,31,32,33,34]. The conventional cache replacement policy such as LFU, LRU, LRU-K [28] have been widely used in various applications in past. The working principle of these policies are that the access pattern shows temporal locality i.e. the future access pattern dependent on only past access pattern rather than spatial information. Furthest Away Replacement policies [29] which considers both clients current location as well as movement direction in replacement policy. The eviction is made sequentially in the order of distance from the client. This policy dismisses the client’s temporal access properties. In the event when mobile clients’ direction updated frequently, then it will make unpredicted effect on membership of objects as it will show frequent switching between the in-direction set (towards valid scope) and the out-direction sets (moving far from valid scope). PAID policy evicts the data having the least cost when cache replacement is performed. PAID (Probability Area Inverse Distance) [30] has the limitation that the priorities for the client’s location nearby data objects in cache and the effect of the size of data object have not been considered. To overcome this limitation, Mobility Aware Replacement Scheme (MARS) [31] came into existence. The data objects updates are considered in this policy. This policy evaluates the various score such as spatial score, temporal score and an object retrieval cost. The update rate in location dependent data is very small as compared to that of temporal data. In deciding cache replacement data item, the anticipated region has major impact. None of the above described cache replacement policies is fit best if there is frequent updation in client’s movement direction because previous schemes consider data distance only and to work with frequent changing direction based location dependent, data the scheme should incorporate functionalities that can predict possible client’s near future region/area. In [32] Kumar et al. proposed Prioritized Predicted Region based Cache Replacement Policy (PPRRP) and compared it against previous cache replacement schemes Euclidean, FAR, Manhattan, LRU, PA and PAID. To improve the system performance predicted region is widely employed in location based services. Kumar et al. have given a scheme PPRRP which finds the predicted region of valid scope for client’s current position and assigns precedence to the closed data items. The client’s movement direction is not considered while assigning priorities to data item. Moreover, using moving interval length (MIc) as radius in this policy has a drawback that system needs to compute the predicted region on the changes in moving client’s direction or velocity.

2.3 Prefetching and Indexing

To answer mobile object database queries, searching each location in database is overwhelming task. It degrades the performance of the overall location dependent information system (LDIS). For better performance we would like to do the spatial indexing [35, 36] of location attributes but this indexing cannot be directly applied in LDIS to answer the queries. The reason behind this, the spatial index needs to be update continuously with changes in locations and which would further increase the work load on the system and communication overhead in excessive amount. To achieve better performance, indexing phenomenon is used in which server pre-computes index information and stores it with data for future queries. Here the question of indexing problem is how can we efficiently index the valid scopes of all data instances of a given query type? It is more difficult to index the geometric location mobile queries in comparison to symbolic location models query. In the spatial indexing, structures such as minimal bounding rectangle are used to map the spatial objects. If the MBR will overlaps to each other, then the search performance would be degraded as the overlapping area searched more than once. In air indexing server pre- computes the index information and broadcast it on the outgoing channel. A mobile client seeking for a query can search for its index and can predict the arrival time of the desired data; it is advantageous for mobile client as it allows going on power saving till the queried records arrive on the requested channel. The disadvantage of this phenomenon is searching for additional indexing data makes broadcast cycle longer.

3 New Direction for Research

The future scope of LBS is very vast and diverse. Meeting the issues and challenges discussed previously from all the characteristics would require more extensive and coordinated research efforts in the specific areas such as new metrics for location aware database, performance and predictability, methods and trade-off between various pairs of parameters etc. From the implementation point of view, the work undertaken will address the problems of Location Aware Information System. The main areas of research are listed below.

  1. 1.

    Development of efficient geometric model for valid scope and cache invalidation policy [8,9,10].

  2. 2.

    Optimization of location dependent query processing and reduce power consumption [11,12,13,14].

  3. 3.

    Development of new algorithms for improvement in cache-hit ratio of replacement policy [28,29,30,31,32,33,34].

  4. 4.

    Defining efficient process for data prefetching and indexing [35, 36].

  5. 5.

    Performance evaluation of above algorithms with reference to database size, cache size, moving/prediction interval, query interval etc.

  6. 6.

    Analyzing the effects of main memory, secondary storage and buffer size on system performance.

  7. 7.

    Development of fault-Tolerant approaches, Recovery Scheme & Schedulable Conditions for LBS.

  8. 8.

    Implementation of complete prototype for consistent location aware system.

4 Our Contributions

In [44], we have presented various research issues of location aware moving object databases. It includes various existing policies in location-aware mobile data management namely cache invalidation and replacement, mobility recommendation, location data map matching, replication and location privacy. Various sub-areas in the directions of location-aware information system are being explored, where there is any possible research scope. The work done by us gives better solutions for some of the listed research directions stated in the previous section.

  1. 1.

    The accuracy of mobility prediction degrades in LDIS when it involves a lot of random movements [37,38,39]. Thus, these random movements must be reduced to get accurate mobility prediction. In [45] a sequential pattern mining method in moving client’s movement histories [40,41,42,43] for the coverage region is employed to find frequent mobility patterns. The paper investigates clustering technique to extract similar mobility behaviors in users moving histories. The SPMC-PRRP model for next location prediction in predicted region was proposed to be used in estimating the distance between data item’s valid scope reference point to the anticipated next location of the client. The cache replacement cost function for eviction of data item uses the next location prediction for effective cost computation of valued data items.

  2. 2.

    In one of paper, a cache replacement policy MPRRP [46] is proposed that consists of weighted cache replacement cost function for eviction of data item when cache becomes full. A normalized negative cosine function which considers present moving direction of client is used to assign weight for replacement cost. The predicted region radius estimation method that was defined in PPRRP has been modified in the proposed MPRRP. The radius of predicted region circle is estimated by root mean square distance in the place of moving interval radius. This leads to reducing the unnecessary computation overhead. The proposed MPRRP policy added the temporal locality factor i.e. frequency of use in addition to spatial score for computation of the replacement cost. MPRRP achieves up to 5% performance improvement in terms of cache hit ratio compared to previous replacement policies [28,29,30,31,32,33,34].

  3. 3.

    In one of the paper [47] mobility rules based on similarities between user’s movements data has be framed to be used in next location prediction. The conditional data distance equation has been revised and being used depending upon whether the data item’s valid scope falls within predicted region or outside the predicted region. The proposed policy achieves significant performance improvement in cache hit ratio on varying outlier ratio, minimum confidence and support threshold.

5 Conclusions

Handling of cache replacement policy is a key issue being studied by us. Despite this, there are many research accomplishments and techniques which have emerged from the area of location bases services. They lead to the increasingly growing interest in the performance mobile distributed database system. Many research accomplishments and techniques, which have emerged from the area of location aware moving database systems. In this research proposal, light has been shed on promising challenges in location aware moving database systems for applying our efforts and resources in a better way to cope up with them. Efforts will also be made to investigate these points for improving the performance for given research area. As for the future work in cache replacement policy, data dissemination schemes, pre-fetching and Hidden Markov Model with Bi-clustering for LDIS can be selected as research area which will overcome the challenges posed by it.