Efficient utilization of mobile databases and gps in wireless networks Paper Presentation

Efficient Utilization of Mobile Databases and GPS in Wireless Networks

                                 Contents

 ·       Introduction

  ·       Overview

Ø Mobile Computing and Databases

Ø Global Positioning System

How does it work?

 ·       Problem Domain

 ·       Proposed Solution

o   Location Dependent Data Management

o   Range Monitoring Queries

o   Spatio Temporal Databases

 ·       Conclusion

 ·       References

Introduction

                        With the rapid advances in the field of Global Positioning Systems many new applications have emerged which require considerable research in the field of mobile databases. Making use of the current state of art it is highly probable to build a push based location dependent application, which hasn’t yet been proposed in the wireless technology. Also, the integration of both GPS and mobile databases hasn’t yet been suggested in any of the papers. The present paper surmises an architecture, which might take shape in the future, and discusses the various design issues to be taken care of while developing a database for this kind of a system. It discusses some key aspects like the usage of the location dependent data, temporal and spatial databases, and range-monitoring queries for continuous monitoring of regions.

Overview

Mobile Computing and Databases:

                        Mobile computing is associated with mobility of hardware, data and software in computer applications. Mobile computing has become possible with convergence of mobile communications and computer technologies, which include mobile phones, personal digital assistants (PDA), handheld and portable computers, wireless local area networks (WLAN), wireless wide area networks and wireless ATMs.

                   Networks enable stand-alone personal computers to participate in distributed systems that allow users anywhere on the network to access shared resources. With access to a wireless network, mobile users can download news or electronic documents, query a remote database, send or receive electronic mail, or even be involved in a real-time video-conference with other users.

                   The technical challenges that mobile computing must resolve are hardly trivial. However, some of the challenges in developing software and hardware for mobile computing systems are quite different from those involved in the design of today’s stationary networked systems.

                   These challenges are discussed below in more detail. Also the implications of host mobility on distributed computations are quite significant. Mobility brings about a new style of computing. It affects both fixed and wireless networks. On the fixed network, mobile users can establish a connection from different locations. Wireless connection enables virtually unrestricted mobility and connectivity from any location within the radio coverage.

                   Mobile user location becomes a dynamically changing piece of data. In this case, the user updates this information, while many others may access it to find out where the mobile user is. In the mobile environment, the location of a user can be regarded as a data item whose value changes with every move. Establishing a connection requires knowledge of the location of the party we want to establish a connection with. This implies that locating a person is the same as reading the location data of that person. Such read operations may involve an extensive search across the whole network as well as a database look up. Writing the location may involve updating the location of the user in the local database as well as in other replicas of this data item.

                   It is easy to notice that current computer applications follow the rapid advancements in the telecommunications industry. Eventually, information systems will be influenced by the rapid evolution of the wireless segment of this industry. Since mobility affects many assumptions upon which today’s distributed systems are based, such systems will have to move to where

tomorrow’s technology can support them. Wireless data technology is foreseen to be a main infrastructure platform for future applications, which are naturally distributed, dynamic and require much flexibility and mobility.

                   In mobile computing systems, the underlying network infrastructure is somewhat different from traditional distributed systems. Designers of mobile information systems have much less control over wireless networks since not only the communication media is provided by telecommunications providers, but also base stations and servers are part of a proprietary wireless network. For example, location of base stations is considered commercial information and is unavailable to application developers.

                   Support for disconnected operations is very important for mobile computing systems as the moving host can frequently disconnect from the network while dropping out of the coverage areas. Unlike traditional distributed systems, this should not be treated as a failure. Implicit support via the OS, or explicit support embedded in the application should enable continued processing on a local file system. Such disconnected processing can also be based on advance caching, when the application is mobility aware and downloads enough data to survive between two successive connection/disconnection cycles. After reconnection, the changes to files are propagated to the file server and client’s updates are synchronized with updates at the server side.

                   Replication is necessary in a distributed mobile file system because of the very nature of a mobile host. Mobile hosts cannot remain connected to the rest of the system all the time. This is mainly due to two reasons, firstly, to save resources on a mobile host and, secondly, a mobile host can go out of a zone of influence thus causing disconnection.

                   Mobile computing, as it stands today, offers many exciting opportunities.However, the challenges that the research community faces are quite significant. These challenges include mobility aspects, power, frequent connections/disconnections, bandwidth limitations, cost factors, resource scheduling and management, advanced concurrency, replication and synchronisation algorithms.

Global Positioning System (GPS):

                        Global Positioning System (GPS) is a worldwide radio navigation system formed from a constellation of 24 satellites and their ground stations. These are positioned at 6 different planes, four in each plane.  It is a framework for identifying the precise location of any object. Recent advances in GPS has led to make measurements about the distance of an object, to better than a centimeter. Given the current trend, the day is not far when every cell phone will be equipped with a GPS for various purposes like destination detection (finding the shortest route to a given place). The requirement is, optimally using the resources of the GPS, which empowers human endurance.

                   It has tremendous potential with a wide variety of avenues for the application of the technology as it offers mind-boggling precision. And to the marvel of the layman, the device is unbelievably small.

                        Global Positioning System uses the wireless network so that the positions of mobile users/vehicles are reported to the central/regional office.

The system requirements are as follows:

·        Firstly, the terminals used for this type of applications are in most cases, vehicle based.

·        Secondly, the data access pattern is two-way communication: GPS data access to the central office, and remote access, updates of the home databases, and order entries into the databases.

·         Thirdly, the performance requirement is that instant response is desired, but the system is not transaction intensive.

·         Fourthly, besides the normal charges, there is likely a cost for GPS equipment.

·         Finally, the transmission medium would either be radio or satellite.

                        The application scenario for emergency response is a special one. Features for such an application area are hard to define since they vary from one situation to another. For example, bushfire control is different from flood control.

 For illustration, we take the example of bushfire control.

1.     The wired network setup is almost impossible although the wired network can be set up in the command center. The terminals needed would be the ones found in the field service applications, terminals installed in the fire fighting vehicles.

2.     The data access is two-way communication as both access and           updates of the distributed databases are necessary.

3.     The system performance requirements are strict: instant response and high volume of data per time unit as maps are accessed and updated frequently.

4.     The cost of using the network is not of priority.

5.     The transmission medium in this case has to be satellite(s) because other media do not cover less populated areas unless a backbone network is also wireless, eg, a wireless ATM.

6.     The network setup should be fast as time is critical.

7.     The GPS functionality is also required for this situation as the positions of all vehicles are reported to the commander center, which can be used to reflect the global picture of the burning forests.

 Three satellite networks are interconnected:

 LEO (Low Earth Orbit) for the communication among fire fighting groups and the communication between the control center and the fire brigades;

GEO (Geo-Stationary Orbit) for the communication between remote databases and the command center; and a special satellite network for GPS.

                        An alternative scenario may involve a heterogeneous wireless network, which may include a satellite link and several wireless LANs.

                        Be it aeroplanes, boats, ships or cars, GPS is the ultimate device that not only tells you where you are, but also guides you to your destination. Some of you who have seen it in cars will realize how useful a tool it can be. The size betrays the sequence of behind the scene activities that quietly determine the position to the accuracy of a meter or so. Navigation was the main idea behind developing GPS. But due to the low cost and size of the GPS devices, sky is the limit for possible applications of the device.
How does it work?
                        When a person tells that he is in Bangalore, we know where the place is located. If we have to drive down to a nearby city, we take the familiar road and use the landmarks on the road to confirm whether we are on the right track.
                   Then man thought; "let's not rely on nature any longer." Why use stars for reference when satellites launched by man can be used as beacons instead? Only that instead of sight, we will have to use radio receivers to "see" the satellite. Why not go one step further and use multiple satellites to determine the position? This is precisely what GPS does.
                   If a person tells that he is 3 miles away from his home, he could be potentially anywhere in the circumference of a circle of radius 3 miles from home. Not enough information? If he also tells that he is 1 mile away from his workplace, does it help us? Yes, but not fully.

 

  He could be at point A or point B. To resolve this ambiguity, we could use one more landmark. Thus, we see that to locate a place on earth, we can use landmarks. To improve the accuracy, we can specify as many landmarks as we please.

                    Do ships and planes have this luxury? How do they keep to their courses? Simple. The earth is divided into imaginary horizontal and vertical lines along the earth's surface (latitudes and longitudes), which uniquely identify every point on earth. Using the compass, we can determine our location and navigate towards the destination.
                   But the compass is a crude tool and hence in the past, sailors used a device called "sextant" which could tell them the latitude and the longitude. It relied on the position of the North Star and the angle of the star to determine the position. This has been the sine qua non for navigation for a long time. Aircrafts used the altimeter (a pressure-based device) along with electronic circuitry for location   determination. The technology not only was far from accurate, but also cumbersome.
                   In fact, using GPS, we can determine the accurate location of any place on earth, be it on land, water or miles above in the air. Sounds too good to be true?

                   In contrast to traditional data, where data are delivered from servers to clients on demand, a wide range of emerging database applications benefit from a broadcast mode for data dissemination. In such applications, the server repetitively broadcasts data to a client population without a specific request. Clients monitor the broadcast channel and retrieve the data item. Such applications typically involve small number of servers and large number of clients.

                   We consider an architecture, which makes use of the GPS and the problem to disseminate data to mobile users while updates concurrently take place at the server.

                   How does GPS use this principle? GPS uses satellites as landmarks in the place of the home and the Office to specify the person’s location. Since satellites are thousands of miles above the earth, we can "see" them from a lot of places on earth. It's not enough if we are able to see just one satellite due to the reason we saw above

 

Problem Domain

                        Recently there has been tremendous research activity involved in applications concerning pulling the data out of a set of servers. The following applications typically demonstrate the case.

·        Request for information regarding a particular place: A user makes a query in his cell phone for information on a tourist place. The query is transferred to a specific server whose result set answers the query

·        Request for a path to a particular destination: A user can make a query for the route to a particular place. The query is transferred to a server like mapquest.com, which reads the query and gives the required output.

                        These are some classic examples of pull based data management. A novel idea is a push based location dependent application, which pushes the data onto all the phones irrespective of whether the user requests or not. For example information regarding traffic blockades on a highway may be broadcast to all cell phones concurrently, located in the areas around the highway.

Another application is the advertisement services. A local company might want to advertise its products, discounts etc to people in that region. Given these two instances, the need is to develop a database, which can handle both these cases.

Proposed Solution:

                        This section deals with the proposed solutions. Let us consider the problem of pushing the data regarding the road blockage and develop our solution. Say, Rd No.635 is blocked due to traffic congestion. The local cop at that place will come to know about the blockage. Every cop will have a local database, which is inherited from a central database at the server. He has a list of all the roads and their status (active or blocked). When the cop encounters a roadblock he updates his local database saying Rd No.635 is blocked. This is reflected in the central database, which transmits a message to all the users of cell phones equipped with GPS saying that the Rd No.635 is blocked, and after searching for an alternate route in another server like mapquest.com   suggests an alternative to the users. This message is flashed to all the users near that region irrespective of whether the user requests or not.

                                                          Architecture

Location Dependent Data Management
Semantic Caching can be used to effectively manage Location Dependent Data (LDD). An LDD query workload is more likely to exhibit a semantic locality in terms of the locations, rather than one defined by the database physical organization. This unique characteristic makes the traditional page or tuple caching inappropriate to the LDD applications in mobile computing. In addition this observation motivates the development of cache replacement strategies built around location and movement.  The idea of semantic caching is that the mobile client maintains both the semantic descriptions and associated answers of previous queries in the cache. If a new query is totally answerable from the cache, no communication with the server is necessary; if it can only be partially answered, the original query is trimmed and the trimmed part is sent to the server to be processed. Semantic caching is by nature an ideal cache scheme for location dependent applications. We have developed a formal semantic caching model suitable for LDD and developed query caching strategies. By binding each location dependent query to a precise location, a location dependent query can be treated as a traditional database query. We have proposed a mobility-based semantic cache replacement policy, Further Away Replace (FAR) . Those segments in the cache which are not in the moving direction and are furthest from the user will be discarded first, as we believe that they won't be visited in the near future.

Range Monitoring Queries

                    The second important thing to be considered here is the way to identify the users within a local region. To identify the position of all the users within a region, range-monitoring queries can be used. Range monitoring queries are continuous and monitor the users within a region. These queries are executed at the server within the base station near the region. Using this, a list of users within the region is maintained at the base station’s database. Each user is associated with a temporal database which has all the information regarding the user and which has a field to store the message (as in Short Message Service) and that, which is being transmitted. So, when a user enters a region with the GPS system he/she is entered into the list of users through range-monitoring queries and tracking systems. As soon as the status field of the rd635 is changed to “blocked” he/she receives the message. Even though his phone is not on at that time, the message will be stored at the temporal database and transmitted when he/she switches it on. When the user departs the region all his data will be eliminated and the temporal database freed, as there is no more need of his data. Thus temporal data optimally encounters the challenge ahead. Also, static databases will co-exist which provide information for user requests.

                        This kind of database also allows many other applications like buddy services, where a person wants to know the location of his friend. This can also be easily handled by using encapsulation techniques, as every user will be in a temporal database of some region. The only thing is that the query should be redirected to the temporal databases of the individual regions. For advertising, local advertisers may store data within the server of the base station. So, whenever a user enters the region he is informed about the products, discounts etc.

                        All the information on the downlink and uplink are transported in the control traffic of the underlying access network. So, mobile nodes need not establish a connection to transfer data.

                        Other important aspects to be considered are elimination of unnecessary data that the user does not want. Suppose that the user want the ads to pop up. He can do it by setting the feature off. As soon as the base station in that region collects the information of the user and identified the option to be off it avoids the pop ups. Another thing is the priority of the messages. Emergency services might be given higher priority than advertisements etc.

Spatio Temporal Databases

Spatiotemporal Database Management Systems (STDBMSs) manage data whose geometry changes over time. There are many applications that create such data, including global change (as in climate or land cover changes), transportation (traffic surveillance data, intelligent transportation systems), social (demographic, health, etc.), and multimedia (animated movies) applications. For simplicity we consider two spatial attributes, the object position and extent, either (or both) of which can change with time. Based on the rate that spatial attributes change, we identify two cases:

 The discrete and the continuous spatiotemporal environments.

We first introduce the basic characteristics and interesting queries for each environment and then present efficient spatiotemporal indexing techniques.

What is a Spatiotemporal Database?

                        Physical objects are characterized by a spatial position (i.e., the object’s location inside some reference space) and spatial extent (i.e., the area or volume the object occupies in the reference space) at any point in time.

                         Examples include: an airplane flying around the globe, a car travelling on a highway, the land covered by a forest as it grows/shrinks over time, or an object that concurrently moves and changes its size in an animated movie. A wide variety of applications manage such space and time referenced objects, termed spatiotemporal objects. In these applications the past, current as well as anticipated future positions and extents of the objects can be queried.

                        Spatiotemporal databases address this need by capturing both the spatial and temporal characteristics of objects.

                   An important temporal feature of spatiotemporal data is the rate by which spatial attributes change. Since the primary goal of a database is to correctly represent reality, the change rate affects how efficiently the database will represent the spatiotemporal environment. We will distinguish between discrete (low change rate) and continuous (high change rate) environments. Traditional databases assume that data stored in the database remains constant until explicitly modified through an update.

                        For example, if a price field is Rs.50, it remains Rs.50 until explicitly updated. While this model serves well many applications where data changes in discrete steps (low change rate), it is not appropriate for applications with continuously changing data.

                   As an example, consider a database that maintains the position of moving objects (like automobiles). Continuous updating about each object’s position leads to serious performance overhead. Updating the database only at given time instants limits query accuracy. The problem is intensified when past object positions (trajectories) are also kept in the database. A better approach would be to represent the position of each moving object as a function of time; then object positions change as time proceeds without the need of explicit updates. Rather, the database is updated only when the function characteristics of the movement change, clearly a manageable rate of changes, while queries can still be answered correctly. This introduces the novel problem of indexing functions. Note also, that if the object movement or extent growth is stored as a function, the database can also address queries about the objects’ anticipated future behavior based on the current information known. In contrast, a discrete environment assumes that current object positions/extents remain unchanged unless explicitly updated.

                   While spatiotemporal applications and data abound the field has only recently attracted the efforts of database researchers. Most of research has concentrated to spatiotemporal database models and query languages.

                    There are also commercial systems that offer support for spatiotemporal data (like the Geodetic DataBlade Module by Informix and the Arc/View Tracking Analyst by ESRI).

Due to the temporal component, spatiotemporal databases need to manage large amounts of data accumulated over long periods of time (historical data). It is thus important to develop efficient access methods (indices) to access such databases. The literature contains several SAMs that have been proposed to manipulate points, arbitrary shaped objects (regions) or raster data, but none considers the time evolution aspect of a spatiotemporal application. As it will be argued later in this chapter, the straightforward approach to treat time as just another attribute of a multi-dimensional index does not lead to efficient solutions for spatiotemporal queries. There have also been work on scientific and earth sciences data but the effort is concentrated on the database requirements for such data and not on indexing the spatiotemporal dimensions. Similarly, there have been many access methods proposed for temporal data but they do not consider spatial objects. Moreover, all of these methods (spatial or temporal) assume the discrete update model.

                   There has also been recent work related to the continuous environment problems in the field of computational geometry focusing on computing boundary functions  on the moving data in main memory. Before describing these approaches in more detail we discuss examples of spatiotemporal queries.

                   A spatiotemporal query specifies spatial/temporal predicates and retrieves all objects that satisfy them. A spatial predicate is defined in terms of a point or an extent while a temporal predicate can involve a time instant or a time interval.

Examples include,

1.     Selection queries: “find all objects contained in a given area Q at a given time t”

2. neighbor queries: “find which object became the closest to a given point              s during time interval T,” or, “find the 5 closest ambulances to an accident position in the next 10

minutes”

3. aggregate queries: “find how many objects passed through area Q during time

interval T,” or, “find the fastest object that will pass through area Q in the next

4. join queries: “given two spatiotemporal relations R1 and R2, find  pairs  of                 objects whose extents intersected during the time interval T,” or “find pairs of    planes that will come closer than 1 mile in the next 5 minutes”

5. similarity queries: “given an area Q find the time instants when there were more than 10 objects in Q”, or, “find objects that moved similarly to the movement of a given object o over an interval T”

                   Traditionally, access methods are designed for selection queries. This is because selections are among the most common queries and can be used as building block for other more complex queries. In addition, neighbor and aggregate queries are usually answered efficiently by facilitating (probably after some appropriate modification) a selection-based index. Join queries are also very important however are not examined here. Since the size of spatiotemporal relations is usually large, we expect that indexed joins (i.e., where at least on of the joined relations has a spatiotemporal index) will benefit us.

                   In query classes (1) through (4) (in discrete or continuous environment) a spatial and temporal predicate are specified and all objects that satisfy them are retrieved. Of importance are also orthogonal queries, where some similarity criterion is specified on the objects and the spatial or temporal components that satisfy this criterion are retrieved. The similarity criterion in query example (5) is “more than 10 objects in area Q” and the “movement of the given object o”. A direct application of similarity queries is in mining spatiotemporal data (where all the times that similar events happened are

retrieved). Previous work from the area of temporal databases indicates that similarity queries are addressed by different techniques than traditional temporal queries

Characteristics of Spatiotemporal Data

                        Depending on the application, we consider reference spaces of up to three spatial dimensions.

                   Objects with zero extent (i.e., objects whose extent is not relevant to the application) are called points.

An example of a point object is an airplane flying around the globe.

                   Objects with non-zero extent are called regions.

A region object may represent the boundary of a forest. Figure 7.1 illustrates two examples in a 2-dimensional reference space (x,y). At each time t an object oi is specified by a record <oid, pi(t), ei(t), t>, where oid is oi’s unique (time invariant) object identity and pi(t) (respectively ei(t)) corresponds to the object’s location (extent) at time t. Moreover, various applications allow for object additions and deletions at any time. This creates a lifetime for each object that starts from the time it was added until the time (if ever) it was deleted. During its lifetime an object is called alive. The state S(t) of the spatiotemporal database at time t contains the records of all objects that are alive at t. We can view S(t) as a snapshot of the object positions/extends at time t. Since a spatiotemporal database records the evolution of spatial objects over time, it conceptually contains all S(t) states and can thus query any S(t). This implies that object deletions are logical, that is, records of deleted objects are still kept in the spatiotemporal database but they are considered non-alive for all times outside their lifetime.

                        Recall that in the field of temporal databases there have been two widely used time dimensions: valid time and transaction time. Valid time is the time when an event occurs in the real world. Transaction time is the time this information is stored in the database. A common characteristic of the transaction-time environment is that changes happen in increasing time order and are

always applied on the current state of the database. A transaction-time database thus keeps the history of an evolution.

So when a change occurs in the real world (valid-time), the database system is updated at the same time (i.e., transaction-time and valid-time coincide).

We also assume that:

– changes to database objects (object additions/deletions, position/extent  changes, or position/extent function changes) are timestamped by the time they occur,

– changes arrive to the database in increasing timestamp order, and,

–        

a change is applied to the most current state of the database (relatively to the change’s timestamp).

As usual, any access method used to organize time-evolving data is characterized by

the space, update processing (the time needed to update the method about changes)

and query time (the time needed to solve a spatiotemporal query) costs. All three costs are functions of the three basic parameters: the answer size k (number of objects reported by the query), the number of changes n (the total number changes in the spatiotemporal evolution) and the page size B. As previously, we are interested in an I/O-based model of computation. The definition of a change depends on whether a discrete or continuous environment is utilized. In a discrete environment, n consists of all the object additions, deletions, and position/extent changes during the evolution. In the continuous environment the position/extent changes are replaced by the changes in the corresponding function that describes the object’s position/extent. Intuitively, n represents the minimal information

needed to keep the spatiotemporal evolution. Since spatiotemporal data tends to increase (due to the time evolution) our solutions should guarantee low space consumption. In addition, in order to be useful on a practical application, update and query times should also be kept minimal.

 Conclusion

                   Technology is one thing that violates the Laws of Gravity by rising high and high day by day.

                   Looking into all the aspects of maintaining the location dependent data with the help of Range Monitoring Queries and Spatio Temporal Databases

It is hopeful to have a better Wireless Networks included with Mobile Databases and GPS that helps in wide range of applications.

                   The System not only helps track the lost people, kids but helps in tracing out various anti-social elements thus supporting a threat free world.