|
|
|
|
Research Article
|
|
Developing a Moving Objects Management System
|
|
Y.E. Ghajary
and
A.A. Alesheikh
|
|
ABSTRACT
|
The aim of this study are to evaluate the current states
of the Moving Objects (MO) systems and extend them to support tracking,
indexing, modeling and visual querying of public transportation buses.
To evaluate the system, the queries posed by fleet management companies
are selected. The results showed its superior functionalities through
text-based and visual queries. This study will contribute to the establishment
of a Moving Objects Management System (MOMS) with modest expenditure and
a short development period and which is independent of the database used.
|
|
|
|
|
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, x1, y1,
t1, x2, y2, t2, 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 (T1, T2, Busid):
Get the travelled distance of a specific bus between time intervals
(T1, T2) |
• |
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 (T1, T2, Busid, Cityid)Boolean |
• |
Enter (T1, T2, Busid)Cityid |
• |
Enter (T1, T2, Cityid)Busids |
• |
Enter (Busid, Cityid)time |
• |
Leave (T1, T2, Busid, Cityid)Boolean |
• |
Leave (T1, T2, Busid)Cityid |
• |
Leave (T1, T2, 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 [T1, T2]. 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.
|
REFERENCES |
Alesheikh, A.A. and F.S.N. Fard, 2007. Design and implementation of a knowledge based system to improve maximum likelihood classification accuracy. Can. J. Remote Sens., 33: 459-467. Direct Link |
Alesheikh, A.A., A.K. Oskouei, F. Atabi and H. Helali, 2005. Providing interoperability for air quality in situ sensors observations using GML technology. Int. J. Environ. Sci. Technol., 2: 133-140. Direct Link |
Amirian, P. and A. Alesheikh, 2008. A service oriented framework for disseminating geospatial data to mobile, desktop and web clients. World Applied Sci. J., 3: 140-153. Direct Link |
Brakatsoulas, S., D. Pfoser and N. Tryfona, 2004. Modeling, storing and mining moving object databases. Proceedings of the 8th International Database Engineering and Application Symposium, July 7-9, 2004, IPC, Coimbra, Portugal, pp: 68-77.
Caduff, D. and M. Egenhofer, 2007. Geo-Mobile query-by-sketch. Int. J. Web Eng. Technol., 3: 157-175. CrossRef | Direct Link |
Erwig, M. and M. Schneider, 2002. Spatio-temporal predicates. IEEE Trans. Knowledge Data Eng., 14: 881-901. CrossRef | Direct Link |
Forlizzi, L., R.H. Güting, E. Nardelli and M. Schneider, 2000. A data model and data structures for moving objects databases. Proceedings of the Sigmod International Conference on Management of Data, May 15-18, 2000, Dallas, Texas, USA., pp: 319-330.
Güting, R., M. Böhlen, M. Erwig, C.S. Jensen, N.A. Lorentzos, M. Schneider and M. Vazirgiannis, 2000. A foundation for representing and querying moving objects. ACM T. Database Syst., 25: 1-42. Direct Link |
Hornsby, K. and M. Egenhofer, 2002. Modeling moving objects over multiple granularities, special issue on spatial and temporal granularity. Ann. Math. Artificial Intell., 36: 177-194. CrossRef | Direct Link |
Hosseinali, F. and A.A. Alesheikh, 2008. Weighting spatial information in GIS for copper mining exploration. Am. J. Applied Sci., 5: 1187-1198. CrossRef | Direct Link |
Kollios, G., D. Gunopulos, V. Tsotras, A. Delis and M. Hadjieleftheriou, 2001. Indexing animated objects using spatio-temporal access methods. IEEE Trans. Knowledge Data Eng., 13: 742-777. Direct Link |
Laplante, A.P., 2004. Real-Time Systems Design and Analysis. 3rd Edn., Wiley-IEEE Press, ISBN: 0471228559.
Lazaridis, I., K. Porkaew and S. Mehrotra, 2002. Dynamic queries over mobile objects. Proceedings of the 8th International Conference on Extending Database Technology, March 25-27, 2002, Prague, Czech Republic, pp: 269-286.
Lema, J.A.C., L. Forlizzi, R.H. Güting, E. Nardelli and M. Schneider, 2003. Algorithms for moving objects databases. The Comput. J., 46: 680-712. CrossRef | Direct Link |
Longley, P.A., M.F. Goodchild, D.J. Maguire and D.W. Rhind, 2005. Geographic Information Systems and Sciences. 2nd Edn., Wiley Publications, England, ISBN: 978-0-470-87001-3.
Meratnia, N. and R.A. de By, 2004. Spatiotemporal compression techniques for moving point objects. Proceedings of the 9th International Conference on Extending Database Technology, LNCS., 2992, March 14-18, 2004, Springer Verlag, Heraklion, Crete, Greece, pp: 561-562.
Pelekis, N., B. Theodoulidis, Y. Theodoridis and I. Kopanakis, 2005. An oracle data cartridge for moving objects. UNIPI-ISL-TR-2005-01. http://isl.cs.unipi.gr/db/pubs/TR/UNIPI-ISL-TR-2007-04.pdf.
Pelekis, N., Y. Theodoridis, S. Vosinakis and T. Panayiotopoulos, 2006. Hermes: A framework for location-based data management. Proceedings of the 10th Internationall Conference on Extending Database Technology, LNCS. 3896, March 26-31, 2006, Munich, Germany, pp: 1130-1134.
Pfoser, D., C.S. Jensen and Y. Theodoridis, 2000. Novel approaches in query processing for moving objects data. Proceedings of the 26th International Conference on Very Large Data Bases, September 10-14, 2000, Morgan Kaufmann Publishers Inc., San Francisco, CA., USA., pp: 395-406.
Pfoser, D., N. Tryfona and C.S. Jensen, 2005. Indeterminacy and spatiotemporal data: Basic definitions and case study. Geoinformatica, 9: 211-236. CrossRef | Direct Link |
Quddus, M.A., W.Y. Ochieng, L. Zhao and R.B. Noland, 2003. A general map matching algorithm for transport telematics applications. GPS Solutions, 7: 157-167. CrossRef | Direct Link |
Safari, A. and A.A. Ardalan, 2007. New cylindrical equal area and conformal map projections of the reference ellipsoid for local applications. Survey Rev., 39: 132-144. CrossRef | Direct Link |
Simonas, S., C.S. Jensen, S.T. Leutenegger and M.A. Lopez, 2000. Indexing the positions of continuously moving objects. SIGMOD Conf. Proc. Dallas Texas USA., 29: 331-342. Direct Link |
Sistla, P., O. Wolfson, S. Chamberlain and S. Dao, 1997. Modeling and querying moving objects. Proceedings of 13th International Conference on Data Engineering (ICDE13), Birmingham, UK.
Tao, Y., C. Faloutsos, D. Papadias and B. Liu, 2004. Prediction and indexing of moving objects with unknown motion patterns. Proceedings of the SIGMOD International Conference on Management of Data, June 13-18, 2004, New York, USA., pp: 611-622.
West, R., 2004. Understanding ArcSDE ArcGIS Edition. 1st Edn., ESRI Press, USA., ISBN-10: 1589480945.
Wolfson, O., A.P. Sistla, S. Chamberlain and Y. Yesha, 1999. Updating and querying databases that track mobile units. Distributed Parallel Databases, 7: 257-387. CrossRef |
Wolfson, O., B. Xu, S. Chamberlain and L. Jiang, 1998. Moving objects databases: Issues and solutions. Proceedings of the 10th International Conference on Scientific and Statistical Database Management, July 1-3, 1998, Capri, Italy, pp: 111-122.
Yeh, A.G.O., P.C. Lai, S.C. Wong and N.H.C. Yung, 2004. The Architecture for a real-time traffic multimedia internet geographic information system. Environ. Plan. B: Plann. Design, 31: 349-366. CrossRef | Direct Link |
|
|
|
 |