Designing Of Location Monitoring Techniques For Query Processing In Mobile Computing Environment

Introduction

Mobile computing is defined as a computing environment over physical mobility. The users can access data or information from any device in a network, while moving the user from one place to another. This system allows a user to perform a task from anywhere using a computing device. While moving, the preferred device is mobile device whereas while back to home or office, the preferred device is desktop computer. It is used in corporate application, telebanking, GPS-based systems, remote monitoring and maps/navigation guide. In order to recover the sensor data from the network, the query processing technique is used. Location sensitive queries among queries are used to acquire the location of a mobile host, to find out the existence of a mobile host and to gain data accumulated in a mobile host. Query processing in a distributed environment is to form a high level query on a distributed database, which is seen as a single database by the users, into an efficient execution strategy expressed in a low level language on local databases.

Spatial query processing is becoming an integral part of many new mobile applications. Recently, there has been a growing interest in the use of location-based spatial queries, which represent a set of spatial queries that retrieve information based on mobile users’ current locations. In a mobile environment, upstream queries are more resource-consuming than the downstream queries. Hence, there is a requirement to minimize the number of trips made to the server and again coming back. Caching the data items at the client side is the only solution for this issue, as it can minimize communication and hence conserve battery power. Location management is mainly used to keep track of an active mobile station within the cellular network. A mobile station will be in active mode, if the station is powered on. As the exact location of a mobile station must be known to the network during a call, location management is used in tracking the active mobile station between two consecutive phone calls. The services offered by the aggregate location monitoring are density queries, safety control, and resource management. In the continuous query processing, it is very difficult to handle the frequent location updates at the server and to handle the communication channel between the moving object and the server. The limited bandwidth and dynamic topology in wireless network creates frequent mobile-server message exchanges that contain location information for the database engine to maintain up-to-date view of the world. Whenever an object moves, it sends its new location to the server that is wasteful as moving object can be located in an area where it does not affect the query result. The prediction of object movement helps in traffic management applications e. g. it predict congested areas before it takes place. It avoids any kind of delay in location updation and prevents the communication channel from any kind of extra messages accumulated at the server.

Motivations

The process of gathering information about the existing data sources at any point of time is difficult owing to the mobility of devices and data sources. The number of messages which is necessary to fulfill the query is referred to as its efficiency. More messages can enhance the network congestion. Due to mobility and unreliable communication, there is a possibility that queries may fail. Most existing techniques cannot predict accurately when the query time is far away from the current time. This is because all of these prediction methods are based on the object’s recent movements, which may not be of much assistance for a distant time prediction. The major problem in the context of location-based applications influencing the location tracking is the fact of efficiently estimating the moving objects which are close to or not close to each other in a given set. This difficulty is termed as the location constraint matching problem. Many applications require solution to this problem. It is challenging to design algorithms to efficiently monitor the large number of location constraints over a large number of moving objects.

Continuous Monitoring scheme discussed in depends on Broadcast Grid Index (BGI) and it is applicable for both snapshot and continuous queries. This can increase the complexity and endures high overhead for the clients. To overcome the downside of monitoring scheme mentioned above, a technique is needed. In mobile computing environment, the problems associated with the wireless network such as limited resources, bandwidth, and memory space remain the same. An efficient cache management in mobile terminal along with the preprocessing of query and efficient cache maintenance scheme to support location-based service are required.

In the first work, an efficient algorithm has been proposed to predictively evaluate the future matches of the location constraints for the moving objects with given mobility patterns. Movement pattern of the object depends on the information of the clusters it visited through and the time duration it spent in each of them. A location update technique is designed for matching constraints under location position uncertainty. The update technique is based on the maximum speed of the moving object to estimate the next location update time. In the second work, an object movement prediction technique is proposed to predict the movement proactively and reduce the delay of location updation. The prediction algorithm is implemented to pre-compute the movement of object to avoid any kind of delay for location updation. Partition-based Lazy Update algorithm is used to help object in determining all the possible movement of query. In the third work, an efficient caching technique for spatial query processing has been proposed in which a hybrid cache maintenance scheme is used by combining the significance of cache data as well as cache Path to avoid delay and occupation of unreliable data. To maintain the cache efficiently, public minimal boundary rectangle replaces the farthest object and maintain the cache for any reliable data item. In this way, the proposed technique can achieve the success of efficient maintenance of the cache for location dependent data.

Literature Review

Yu-Ling Hsueh, Roger Zimmermann, and Wei-Shinn Ku have proposed two novel efficient location update strategies in a trajectory movement model and an arbitrary movement model, respectively. Adaptive Safe Region (ASR) technique retrieves an adjustable safe region which is continuously reconciled with the surrounding dynamic queries. Also, they designed a framework that supports multiple query types. Partition-based lazy update algorithm elevates this idea by using location information tables which allow each moving object to estimate possible query movements and issue a location update only when it may affect any query results and enable smart server probing that results in fewer messages. They efficiently determine the set of objects that are affected by a query insertion, improving scalability.

Chi-Yin Chow et al have proposed an aggregate location monitoring system in WSN. The network consists of counting sensors that are only capable of reporting aggregate locations, i. e. , their sensing areas along with the number of detected objects residing there in, to a query processor. An adaptive spatio-temporal histogram is used that models the distribution of moving objects and answers aggregate monitoring queries based on aggregate locations. Memorization, locality awareness, and packing techniques are combined together to enhance the histogram accuracy and efficiency by Using both the spatial and temporal features in aggregate locations. However, they have not considered the delay metrics.

Hoyoung Jeung et al have presented a hybrid prediction model to estimate an object’s future locations based on its pattern information and motion functions using the object’s recent movements. An object’s trajectory patterns with ad-hoc forms for prediction are discovered and then indexed by a novel access method for efficient query processing. The query processing techniques can provide accurate results for both near and distant time predictive queries. These techniques are more accurate and efficient than existing forecasting schemes. However, they have not considered the throughput and delay metrics to determine the efficiency of the scheme.

Kwangjin Park and Young-Sik Jeong proposed location-based cache maintenance strategies for wireless broadcast environments where the expected data to be used in future was prefetched by a mobile client and cached and maintained at location nearer to client’s location. In addition, a hierarchical tree-based privacy approach was proposed assisting anonymous location-based queries in wireless mobile data delivery systems. However it takes much tuning time.

Adaptive Cluster-based Location Monitoring (ACLM) Technique for Query Processing in Mobile Computing Environment

Initially, the parameters such as distance, speed and mobility factor of a node are estimated. The two categories of location constraints exists which are defined as n-object constraints and n-object invariable constraints. A set of location constraint assigns the appropriate location relationship among moving objects Z = {z1, z2… zn} which continuously estimates all constraints vj in V that are satisfied. The location limitations reveal that once the continuous queries are submitted to the system, they remain active till they are cancelled explicitly.

Clustering

The steps involved in the cluster formation are as follows. Each object Ni broadcasts a beacon message to indicate its existence to the neighbors. The beacon message contains the object status. Upon receiving the beacon messages, each neighbor object constructs its neighbor list. The weight of each object (W) is computed based on the parameters such as object distance, speed and mobility factor. The object with smallest W is chosen as cluster head. Then the complete objects that are neighboring to the cluster-head are not permitted to take part in the cluster head election process. The above steps are repeated for other objects pending to be chosen as a cluster-head or assigned to a cluster.

ocation Update Technique

The location update technique is triggered on the object side. When any object moves away from its current cluster, it is necessary to update its location information. To track the mobile object and make clustering algorithm work properly, every object should be linked with respective CH according to its position changes. It is verified whether the object is within the same cluster where it was located in. If the object is not present, the remaining clusters are verified for the moved object. When an object Ni moves into a new cluster Ci, the entire constraints related to it has to be re-evaluated as per the cluster information. The location update technique recognizes the objects in a set of objects involved in vj following the cluster formation, computes the smallest circle enclosing all these clusters termed as encircle, and compute the smallest circle intersection of all these clusters termed as intersecting circle. The outcome of many location constraints can be estimated based on the upper and lower bound of the circles built. Both the n-object constraint and n-object invariable constraint are discussed.

Adaptive Location Monitoring and Updation Technique

To monitor and update the objects location, the location monitoring scheme is enhance. The cluster architecture is divided into equally spaced cells of grids with border length α. Each cell includes a cluster group (i. e) a cluster head with its object members. Each cell corresponds to a cluster group. Number of objects in a cell may vary corresponding to its cluster group. Cell informations are included in the packets and create an index table. CH of each cell maintains the information of its member objects. Cardinality (C) of a cell denotes the number of objects in it. In our technique, the value of cardinality is keep tracked by CH.

Close Proximity Neighbor Discovery Algorithm

The CH triggers the close proximity neighbor discovery algorithm. This algorithm discovers all possible best neighbors that exist in the close proximity of CH. Initially, each CH will receive higher level packets of index table from their member objects. In accordance with received higher level packet, the CH estimates upper bound DMAX value considering DistMAX (Cl) and cardinality value. The CH monitors the objects in that cell with DistMIN < DMAX. Objects that have DistMIN > DMAX are omitted. After every step the upper bound value of DMAX is decreased to keep out unnecessary objects from deliberation. The proposed ACLM technique simulated in NS-2 and compared with KNN based approach.

Object Movement Prediction technique for Cluster-based Location Monitoring (OMPCLM) Technique in Mobile Computing Environment

Initially, prediction function is used to predict the future location of large number of objects after a certain interval of time t. After that, Object List (OL) and Space Grid (SG) and Travel Time Grid (TTG) are estimated.

Query Result Computation Phase

This phase consists of two inputs: A predictive query Q which is received either as range, aggregate or k-nearest neighbor and asks about future location after particular time t, and a cell Ci which overlaps with query area of interest S. The output consists of partial answer of Q which is computed from cell Ci. This phase starts by checking whether the query answer at the input cell Ci is already computed or not. If it is already computed, this phase is instantly concluded by updating the query result Q with precomputed answer of Ci. If the answer is not precomputed then it proceeds by calculating the answer of Ci from scratch. A smart time filter is applied to limit the search only to those objects which has the probability to reach cell Ci within the future time t. It utilizes Travel Time Grid (TTG) data structure in order to find a set of cells CR that consist of objects which is reachable to Ci within the time limit t. After that prediction function is calculated for the object that lie within any of the cells in CR and all the object is collected to build the answer result from the cell Ci.

Location Update Table (LUT)

The updation method is described after the result computation phase. The location updation technique uses the Location Update Table which is generated in case of following two events: If any of the existing query in the cell Ci changes its location, or if a new query Q is found in the network. LUT. value for LUTserv (i, j) is used, which stores an integer number and is use to represent safe distance. The safe distance for LUTserver is the minimal linear distance in cells from the LUTserv (i, j) to the nearest query boundary.

While assigning value to the LUTserv (i, j) two cases need to be considered: If LUTserv ( i, j) doesn’t overlap a query boundary, then LUT. value[image: image1. wmf]0 and if LUTserv ( i, j) is covered by a query boundary, then LUT. value = -1. The proposed technique precomputes the movement of object to avoid any kind of delay in the location updation. It also avoids overhead in the network. The proposed OMPCLM technique is simulated in NS-2 and compared with KNN based approach.

Efficient Caching Techniques for Spatial Query Processing (ECTSQP) in mobile computing environment

Initially, the significance of enhanced Grid Partition index are discussed. The index structure for the grid-partition index mainly consists of two levels: The upper level index is built upon the grid-cells and maps a query point to the subsequent grid cell. The lower level index is built upon object linked with each grid cell and eases the access to the object linked with each grid cell. By using grid-partition, the search space can be diminished that can be explained as follows: First, a VD, that means the solution space of NN queries, on the data objects can be build. In next step, solution space is partitioned into a grid cell such that query point can be effectively mapped into grid cell around which nearest object is located. After that, grid-partition stores the objects that are possible NN s of any query within the grid cell. In this approach, adaptive partition is deployed. AP easily partitions the space using a kd-tree partition method. It recursively divides the search space into two balanced subspaces such that number of objects associated with each sub space is almost same.

Hybrid Grid-Index based Caching scheme

Hybrid Grid-Index based Caching Scheme is used to achieve optimal result without any delay. The hybrid scheme mainly combines the significance result of Cache Path and Cache data scheme to avoid any kind of unwanted cache occupation. In Cache Data, the node caches a passing by object Oj in vicinity when it finds that Oj is popular, that means, there were many request for Oj or it has sufficient free cache space. In Cache Path, while saving the path information, a node can save only the destination node information, in spite of saving all the node information along the path. That means, in Cache Path, a node does not required to record the path information all passing-by-data. Especially when a node forwards a data object, it caches the data or path based on some metrics. For a data object Oj, certain heuristics are considered to decide whether to cache data or path.

Cache Maintenance

Efficient cache management is used to avoid any kind of unnecessary information filled inside the cache. For this, public minimal boundary rectangle (PMBR) index tree is used, which is maintained by a client node. Also, a unique cache replacement algorithm known as hierarchical furthest away replacement (HFAR) is implemented that maintain efficient selective tuning and enhance cache hit rates. HFAR is specially designed to select a victim data item that is extremely away from the client node and eliminates it’s based on the location of data or object in the grid index. HFAR technique first chooses the RMBR which is extremely away from the user’s current location C. The farthest SMBR and the object is then successively ejected based on the distance from C. Consider that the client node who releases a query adjust a broadcast channel of site j. Also, client node pre-fetches data objects that are located adjacent to each other in the grid-index for future references if it has the free space to accommodate a new item. As the information transmitted by the server site is successively ordered based on their location, client node can easily pre-fetch adjacent data objects whilst it processes NN or range search on air. The proposed ECTSQP technique is simulated in NS-2 and compared with CSLDQP based approach.

Conclusion and Future Work

In this work, an adaptive cluster based location monitoring technique for query processing in mobile computing environment is proposed in which the object with minimum weight is chosen as cluster head (CH). When any object moves out of its current cluster, its location is updated using location update technique based on the location constraints. An adaptive location monitoring and updation technique is used to monitor and update objects locations dynamically. After that, an object movement prediction technique is used to predict the object movement proactively which avoids any kind of delay for location updation. Location update technique (LUT) is used to determine all possible movement of query that allows location update only if it affects any result and enable a smart server probing technique to avoid any kind of overhead in the network. Finally, an efficient caching technique for spatial query processing is proposed in which an efficient grid-partition index is used to maintain the search space and place the query in the grid cell such that the search of any query becomes easy as it is mapped to nearest neighbor. Simulation results show that the proposed techniques can achieve efficient location updation and cache maintenance for location dependent data along with the reduction in overhead. Semantic caching is an important method to improve the performance of query processing in mobile computing. In this method, the client maintains the results of previous queries as well as their semantic descriptions in its cache. As a future work, we propose to integrate semantic caching techniques with the proposed query processing system in mobile computing environment.