Developing a Moving Objects Management System

INTRODUCTION

Many applications such as Location Based Services (LBS), Emergency Response (ER), tracking and air quality controlling systems must deal with spatial objects whose position or extension change continuously over time, called Moving Objects (MO) (Alesheikh et al., 2005). Taxis, buses, ships, airplanes, are examples of moving objects that facilitate the human daily life. As such, managing MO is a necessity in optimizing human activities. New technologies provide a potential foundation to develop MO applications (Amirian and Alesheikh, 2008). However, existing systems are not well equipped to handle continuously changing data, because there is a critical set of capabilities that has to be integrated, adapted and built on top of the existing functionalities. These capabilities could be classified in several categories like data modeling, data structure and operation, query processing, indexing, data visualization and uncertainty/imprecision management (Meratnia and De By, 2004; Wolfson et al., 1998; Pfoser et al., 2005; Hornsby and Egenhofer, 2002; Alesheikh and Fard, 2007; Hosseinali and Alesheikh, 2008). In this research a system is developed to address the above issues with the exception of uncertainty/imprecision management. In order to efficiently answer the queries about MO, storage of spatial data must be optimized (Kollios et al., 2001). Hence, a spatio-temporal data model is developed to map the motions of MO in real world to a Database Management System (DBMS) properly. A key issue in handling MO queries is how to model the location of moving objects and enable a GIS to predict the future location of moving objects (Lazaridis et al., 2002; Yeh et al., 2004). Therefore, trajectories are introduced to handle temporal queries. Visual queries can ease up the system use as such the developed system addresses such queries. The system has been developed for a public bus company in Iran and the initial results are promising. Although, a Moving Objects Management System (MOMS) consists of at least three main components: positioning, communication and GIS, this paper addresses the GIS issues. Hence the positions of the buses are the system input.

Various researches have been performed to model spatio-temporal databases using the concept of Abstract Data Types (ADT) for moving objects. Güting et al. (2000) have proposed such types along with a set of operations on moving points and moving regions. The model was probably the first attempt to work with continuous motion, while Forlizzi et al. (2000) defined discrete representations of ADTs in a Moving Objects Database (MOD). Lema et al. (2003) presented a comprehensive, systematic study of the algorithms for a subgroup of the operations introduced by Güting et al. (2000) and Wolfson et al. (1998) proposed Moving Objects Spatio-Temporal (MOST) data model for databases with dynamic attributes. The attributes, without being explicitly updated, changes continuously as a function of time (Wolfson et al., 1999; Sistla et al., 1997). Erwig and Eshnider (2002) have introduced the concept of Spatio-Temporal prediction as an extension to the abstract model proposed by Güting et al. (2000) and Pelekis et al. (2005) have introduced a rich type system of time-varying geometries that changes continuously and/or in discrete steps. A rich set of object methods is implemented by Pelekis that expresses all the interesting spatio-temporal phenomena and processes. New operations describing the buffer, the convex hull, the centre of gravity and points on the surface of moving geometries are also proposed by Pelekis. HERMES Type System introduced new objects like Moving_Circle, Moving_Rectangular, Moving_ Collection and Moving_Object (Pelekis et al., 2006).

This study deviates from previous researches in a way that no new data types are introduced. Instead, available data types in SQLServer™ are used. A novel hybrid indexing method is proposed. Spatial data is stored in the DBMS through ArcSDE™ functionalities. ArcSDE™ is used to handle the geometries of MO while SQLServer™ manages much of the attribute data handling processes. Using available resources made the system development efficient. Since both software remains in the market for a while, it can be assumed that the developed system is reliable and stable. Trajectories together with trip information are used to predict the future locations of MOs. Another contribution of the study is its visual query builder. Earlier study on MOMS was mainly focused on text-based query (Pelekis et al., 2006; Wolfson et al., 1998). Operators in this case study are developed using VB.NET™ programming language and ArcObjects™ components.

Moving objects: Characteristics and relations: Two types of spatio-temporal objects may be distinguished, namely; discretely moving objects and continuously moving objects. Objects that change position or extent continuously are pervasive. However, they are much more difficult to deal with in database than the discretely changing objects. If only the position of an object changes, it will be a moving point. Moving regions are the objects that their locations, sizes and shapes are changing. This research concerned mainly on managing public buses, therefore, moving points are the focus of this study.

Trajectories are used to represent dynamic attributes of moving objects, including the historic, current and future location information. One way to track the trajectory is to update moving objects position continuously. Moreover, moving objects need to submit their future moving plans to the system for trajectory estimation. Each trajectory consists of several segments. The segments closely approximate road networks.

In this research, a segment is assumed to be a straight line and objects are moving in a constant velocity.


Fig. 1:	Relationships between a trajectory and its spatial environment

Therefore, the position of an object could always be computed using a linear spatial interpolation. A predefined travel path helped to resolve the positional ambiguity if several candidate segments exist. The common properties of trajectories that were considered are (Brakatsoulas et al., 2004):

•	Speed of the movement (indicated by the slope of the segment)
•	Orientation, showing the direction of the vehicle,
•	Covered area, indicating the area the vehicle covered during its trip
•	Traveled distance and
•	Traveled time

Trajectories have relationships with spatial objects such as city boundaries and other trajectories. Relations between trajectories and their spatial environment as shown in Fig. 1 are:

•	Stay within, when the trajectory is in the range of interest all the time
•	Leave, when the trajectory leaves the area of interest
•	Enter, when the trajectory enters the area of interest
•	Cross, when the trajectory crosses the area of interest
•	Bypass, when the trajectory passes by the area of interest

Relations among trajectories as shown in Fig. 2 are:

•	Intersect: indicating that two trajectories intersect
•	Meet: showing that two trajectories touch at one point
•	Equal: when two trajectories coincide
•	Near: when two trajectories are close to each other based on definitions on what close means
•	Far: when two trajectories are away from each other


Fig. 2:	Relations among trajectories (Brakatsoulas et al., 2004)

METHODOLOGY USED

Developing a MOMS is more than simply buying the appropriate hardware and software. Several strategies have been proposed to provide successful implementation (Laplante, 2004). The implementation strategies have been scientifically assessed and modified so that the requirement of this project can be met with minimum cost and time. Figure 3 shows the development steps, which is described in terms of 6 major activities starting with the requirement analysis and ending with on-going use and maintenance of the system.

The requirement analysis step has been performed through interviewing potential users while analysing similar systems. This step produced two critical pieces of information: a list of functions that is needed and a master list of available/needed data. Two types of data are categorized in this research: spatial and attribute. Bus, gas station, road segment, city, city center, province, police station, restaurant and mosque, are among spatial entities. Attribute information describes spatial entities.

Once the required data has been identified, the data model that identifies the entities and their relationships were designed. Saving trajectory data of moving objects and their constraints for each segment is the basis of this model. Figure 4 shows the conceptual data model (Entity-relationship diagram) developed for this study.

Entities are represented as rectangles, relationships as diamonds and attributes as ellipses. The cardinality numbers that establish the relationship types are presented by numbers. Due to its importance and space limits, only a limited number of entities are shown in Fig. 4. Other entities such as Parks, Hotels and Mosques are removed from the diagram.

The trajectory information is stored in the database; hence, the two main entities are Trajectory and Traj_Segment that are saved in the following tables:


Fig. 3:	MOMS development steps

•	Trajectory (TrajectoryID, BusID)

Traj_segment (Traj_seg_ID, TrajectoryID, x₁, y₁, t₁, x₂, y₂, t₂, Az, Road_seg_ID)

Due to the fact that each trajectory might be composed of several segments, the cardinality of the two entities is 1: n. Since communication channels may be interrupted, Bus and Trajectory has a 1: n relationship. The Bus schema is defined as:

•	Bus (Busid, company_name, path, origin, destination)

Iranian road information is organized in the following tables:

•	Road_segment (Road_seg_id, NodeID_from, NodeID_to, CityCenterID_from, CityCenterID_to)
•	Node (NodeID)

Choosing the types of entity representation (discrete objects-point, line and polygon-or field) has profound implications on MO applications; therefore, vector model is used in this study (Longley et al., 2005). The GIS/DBMS software to be used dictates most of the logical/physical database design, as the structure and format of the data in a GIS, like ArcGIS™, has already been determined by vendors.

Selecting suitable software environment is an important step in a successful implementation, since all the future developments will be based on this step. Software was evaluated on functionality, performance, simplicity and independent of the hardware and operating system. With respect to the required functions, cost, familiarity and time constraint SQLServer™, ArcGIS™, ArcSDE™, VB.NET™ and ArcObjects™ has been selected in this project.

Once all the spatial and attribute data is gathered and loaded in the database, all the components are integrated to make sure they work as expected and to initiate all procedures necessary to use the GIS.


Fig. 4:	Conceptual model of MO database

The initial requirement analysis contained some applications of a complex spatio-temporal nature that cannot be implemented using the basic functionality of the GIS software. Hence, they have been programmed. Ease of use, user-friendliness and reducing the volume of data transfer were the critical issues considered in the development. Figure 5 shows the initial user interface.

The main functionalities of the developed system are classified into queries, operators and indexing.

Query facilities: A query in a spatio-temporal database is a predicate over the database history (Pfoser et al., 2000). The system is able to answer to more than 20 types of query. Each query can be posed graphically or textually and in present, past and future (Caduff and Egenhofer, 2007). The queries are classified into five categories:

•	Simple queries: Queries that do not have a temporal parameter, or only the present time is of interest. (Example: show all the buses of company No. 1 which are inside the city of Tehran)
•	Point queries: Queries which have only one temporal parameter. (Example: what were the position, speed and azimuth of bus No. 2, 30 min ago)
•	Range queries: Queries which have two temporal parameters. (Example: how many kilometers is the traveled distance of bus No. 3 from 1 to 2 h ago)
•	K-nearest queries: Queries that find the k nearest moving or stationary objects to a specific bus. (Example: what is the nearest gas station to bus No. 4 in the next 20 min)
•	Complex queries: Queries which consist of a combination of the other queries. (Example: show all the buses of company No. 5 that have traveled 35 to 40 km from 30 min ago up to now and are moving toward South-East at the moment and will exit the city of Tehran 30 min later)


Fig. 5:	The initial user interface

Spatio -temporal operators: In this research, operators are functions that have been developed using Visual Basic.NET™ programming language and ArcObjects™ components. Each query calls for one or several operators to execute.

Input/output arguments of these operations can be the number of some moving or stationary spatial objects, a point of time, a range of time and/or the Boolean values. The system operators are classified based on:

Location-temporal operations

•	Position (T, Busid): Get the (x, y) coordinates of a specific bus at a point of time
•	Speed (T, Busid): Get the speed of a specific bus at a point of time

Orientation-temporal operations

•	Azimuth (T, Busid): Get the azimuth of a specific bus at a point of time
•	Turn (T, Busid): Get the rate of change of the angle between the x axis and the bus at a specific point of time

Metric-temporal operations

•	Travelled distance (T₁, T₂, Busid): Get the travelled distance of a specific bus between time intervals (T₁, T₂)
•	DistanceMM (T, Busid1, Busid2): Get the distance between two buses (Busid1 and Busid2) at a point of time
•	DistanceMS (T, Busid, Soid): Get the distance between a specific bus (Busid) and a particular static object (Soid) such as gas station at a point of time
•	NearestMo (T, Busid): Get the nearest bus to a specific bus (Busid) at a point of time
•	NearestSo (T, Busid): Get the nearest static object such as a gas station to a specific bus (Busid) at a point of time

Topological-temporal operations

•	Enter (T₁, T₂, Busid, Cityid)Boolean
•	Enter (T₁, T₂, Busid)Cityid
•	Enter (T₁, T₂, Cityid)Busids
•	Enter (Busid, Cityid)time
•	Leave (T₁, T₂, Busid, Cityid)Boolean
•	Leave (T₁, T₂, Busid)Cityid
•	Leave (T₁, T₂, Cityid)Busids
•	Leave (Busid, Cityid)Time
•	Within (T, Busid, Cityid)Boolean
•	Within (T, Busid)Cityid
•	Within (T, Cityid)Busids
•	Within (Busid, Cityid)length of period

There are 3 main operations in this class which are: Enter, Leave and Within. Every operation has 4 states that vary based on its input parameters. For example, the first state of Enter operation determines that whether or not a specific bus (Busid) has entered into the specific town (Cityid) in the time interval [T₁, T₂]. The returning value of this operation is a Boolean value.

Checking operations

•	Check_NewSeg (Busid, Currentx, Currenty, T) Boolean
•	Check_NewTraj (Busid, Currentx, Currenty, T) Boolean

Check-NewSeg operation, determines whether the bus has deviated from straight direction. Check-NewTraj operation, determines whether the connection of Global Positioning System (GPS) to the MOMS has been interrupted. The interruption may be due to signal loss or mobile network malfunction.

Indexing: In this case study, spatio-temporal data are voluminous. The data includes all Iranian roads and several hundreds of bus positions. Therefore, the index structure must result in optimum system performance. The indexing method which has been proposed in this system is spatio-temporal indexing (Simonas et al., 2000; Tao et al., 2004). The implemented indexing method is a combination of spatial indexing, that ArcSDE™ provides and the descriptive data indexing (time will be saved in a descriptive way), that is carried out by programming a series of functions written in VB.NET™, ArcObjects™ and SQL™. In fact, descriptive indexing caused the spatial indexing to be executed on a more limited number of geometric objects. Details of descriptive indexing can be found in various literatures (West, 2004; Longley et al., 2005; Forlizzi et al., 2000). Depending on the used database, ArcSDE™ offers several spatial indexing methods. In this case study, SQLServer2005™ manages the descriptive data; therefore, Multi-Level Grid indexing is used.

SYSTEM ARCHITECTURE

Figure 6 shows the architecture of the implemented system. The system consists of the following components:

•	Data Pre-Processing
•	Moving Object Database (MOD)
•	Query Processing and
•	Graphical User Interface (GUI)

What stored in database are the trajectory data of buses and their georeferenced coordinates together with segment constraints.

Taking into consideration that Iran is covered with four Universal Transverse Mercator (UTM) zones, a pair of Cartesian coordinates measured by GPS, may be represented in false locations. So, the system input must be in geodetic coordinate system. The best map projection system to fit the entire country is Lambert Conformal Conic (LCC) (Safari and Ardalan, 2007). As such the geographic coordinates (Φ, λ) of buses are transformed and stored in LCC coordinates first.

Mapping the positions of the busses onto the roads is erroneous, since both GPS measurements and road maps are imprecise. Moreover, trajectories are the discrete representation of continuous bus movements, hence, such assumption further deteriorate the error magnitudes. In order to reduce the displacements of roads and positional measurements map matching is applied. The point-to-curve method that is proposed by Quddus et al. (2003) is applied in this research. Point to curve method is matching the estimated position of the bus (point) on the road network (curve).


Fig. 6:	The MOMS architecture


Fig. 7:	An example of added GUIs to ArcGIS (range query)


Fig. 8:	The result of a complex spatio-temporal query

Bus coordinates are then entered into the Check-NewTraj operation. If the returning value of the above operation is true, the connection of GPS receiver with MOMS is interrupted. If the returning value is false, the Check-NewSeg operation runs to test the validity of new segments.

When the database is populated, users can introduce new queries and observe their results through GUI. The query processing component receives parameters from GUI and returns the results with embedded operations (Caduff and Egenhofer, 2007). To access various GUI`s and establish queries, a menu called SMOTIS is added to ArcGIS™ environment (Fig. 5). An example of range query form is shown in Fig. 7.

The final results can be presented visually (in ArcMap™) and/or textually (in various forms). As an example, Figure 8 shows the results of a complex query: Show all the buses that entered to Tehran City one and half hour ago and left the city 15 min later.

The final step of this project is to put the system to use. With system integration and testing completed and all applications available for use, the system will be released for further tests by companies.

CONCLUSION AND FUTURE WORKS

This study presents a new moving objects management system. Spatio-temporal trajectories are modeled and stored to answer various queries of past, present and future states of public buses. The model supports various types of queries including simple, point, region, k-nearest neighbor and complex queries. In order to efficiently develop the system, efforts have been made to use the available resources rather than introducing new data types and functionalities. Therefore, ArcGIS™ is used to generate several GUI`s. The user friendly GUI`s facilitate the posing of various queries visually and textually. The results of the query can also be presented visually that makes the data interpretation much meaningful.

A new spatio-temporal indexing has also been proposed. ArcSDE™ is used to handle the geometries of MO while SQLServer™ manages much of the attribute data handling processes. Using ArcSDE™ separates the developed MOMS from DBMS type, therefore, other DBMS`s like Informix™, Oracle™ and DB2™ can be connected to the system without any noticeable changes.

In order to assess the performance of the system, a prototype is developed for Iranian bus transportation system. A series of experiments have been performed, that shows promising performance.

This research is a part of a larger research project, focusing on the development of technologies for making a bus information system. Further attempt is planned to manage the data on the internet. The uncertainty and imprecision issues are some other aspects of MOMS which are considered for future works. Traffic data could also be added to the system, to enhance the prediction of the future position of the bus.