The success factor of Location Based Services (LBS) heavily depends
on the accuracy of Location Determining Technology to predict mobile users`
location (Zeimpekis et al., 2002) and the response time to get
information (nearest restaurants, nearest shopping). In general, there
should be a core LBS gateway, to be located in Telecommunication Company
(Telco) environment, to process huge traffic requests, to store or to
retrieve large numbers of relevant area information and to respond information
to mobile users within acceptable Quality of Service (QoS). In the US,
FCC (Federal Communication Commissions) has produced standards for Wireless
Network Operator (Telco) to comply to location accuracy and reliability
(Anonymous, 2005), that 67% of emergency calls that dial in to 911 numbers,
to be within 100 meters (error of real location compared to estimated
location) and 95% of the calls to be estimated within 300 m of accuracy.
The performance benchmark of 67 and 95% of error (accuracy in meters between
real User Equipment (UE) and estimated UE) has been widely used by researchers
to describe LDT (location techniques or methods) performance.
Some of the network based LDTs used for positioning are Cell Identification,
Enhanced Observed Time Difference of Arrival (E-OTD) for GSM, Observed
Time Difference of Arrival (OTDOA) for UMTS, uTDOA (uplink Time Difference
of Arrival) (3GPP TS25.305 V8.0.0, 2007), Assisted Global Positioning
System (A-GPS) and Database Correlation Method (DCM). Cell ID method is
the simplest and the cheapest method as it uses the serving cell information
to estimate the user`s position. OTDOA and E-OTD are timing method based
on triangulation (Spirito, 2001). DCM (Laitinen et al., 2001) is
basically a signal matching technique where specialized multipath analysis
receivers are placed at BTS or Node B. The transmitters` signal data will
then be matched with the constructed multipath database to determine the
position of the mobile phone.
Almost every household has a mobile phone. 85.1 out of 100 population
of Malaysia owns a mobile phone (MCMC, 2007). And like the utility companies
(electricity and water), mobile phones have become a basic need.
||Architecture of UIPS for GSM, UMTS and beyond network
Although Content Providers (CP) are ready to provide LBS contents, but
Telcos are careful to safeguard their mobile user`s privacy. At the same
time Telcos want assurance that any new service will not congest their
voice and data network resulting from heavy LBS signalling queries. Therefore,
the introduction of a new concept called UIPS was explained by Singh and
Ismail (2004) to interconnect Telco`s network with LBS contents. Figure
1 shows the architecture of UIPS.
The objective of this study is to describe the LDT Module development
for UIPS. The development of each technique or enhanced technique will
be related to accuracy level in known LOS or unknown LOS conditions.
MATERIALS AND METHODS
Data collection in UMTS Environment: Here we will develop
location estimation techniques to be simulated in real UMTS (3G) network.
The simulated network is based on data collected through drive test of
urban roads in Kuala Lumpur, Malaysia. Figure 2 shows
an example of urban route to be used as part of the simulation.
Kuala Lumpur is the capital city of Malaysia. The buildings and environment
are very unique where there are more of 3 storey shop and offices in comparison
to tall buildings, like Kuala Lumpur City Center (one of the tallest structure
in the world).
The equipments used for data collection were commercial software for
Drive Test installed in a laptop, connected to one UMTS phone and one
GPS outdoor receiver (fitted to rooftop of Telco`s vehicle). The UMTS
phone was set on active dedicated voice call mode. The objective is to
grab as much information (measurements) as possible pertaining to serving
Node B and Neighbors Node B along the route.
||Drive test route urban Kuala Lumpur
This route was repeated 3
times in order to thoroughly analyze the samples and to reuse the learned samples
for building UIPS simulation testbed. UMTS network samples were collected
from July 2006 till November 2007 for metropolitan Kuala Lumpur, urban
Kuala Lumpur, major roads around Kuala Lumpur, highways, suburban, rural
and Universiti Kebangsaan Malaysia`s campus.
The data collected on the urban road as in Fig. 2 will
be classified as known LOS case (multipath delays are known) and other
data collected within this urban area will be classified as unknown LOS
environment. In general, multipath delays are caused by unwanted time
delays added to the observed time measured (time from Node B to UE). Multipath
delays occur when UE is not in the line of sight of Node B (Node B downlink
signals blocked by buildings or structures travel through different and
longer paths to reach UE).
Development of simulator and LDT tester: After data was collected,
it was analyzed and finally a simulation model to test LDT based on OTDOA
time measurements parameters (Küpper, 2005) in UMTS network was completed.
The completed data is simulated as the network measurement report (NMR).
Heine (1999) provides NMR examples for cellular network. The simulated
NMR data, coordinates of the Node B (in meters), scrambling code, Cell
ID, RNC code and other information are passed to LDT (technique) to be
converted to range distances of each Node B (the distance in meters from
each Node B to UE) and then calculating the estimated mobile position
(Fig. 3). If the CDF (Cumulative Distribution Function
of Error Estimation) does not meet the E-911 accuracy requirements, the LDT technique is analyzed and improved.
Process flow to analyze Drive test data, to develop
simulator to simulate data and test LDT (technique) until it is fully
ready to be integrated into UIPS LDT Module
Once the standard
is accepted as per the 95% error and 67% error requirements, we will then
integrate the LDT technique into UIPS LDT module.
The LDT techniques developed for time triangulation (downlink time measurements
arriving at UE from at least 3 base stations) are as following:
||Close Circle Correlation (CCC)
||Newton Raphson 3 Circles (NR3C)
Newton Raphson 3 circles (NR3C) technique: Timing triangulation
is based on solving non linear three circles equations (time of arrival
at UE from at least three Node B time transmissions) or also known as
2 pair of hyperbolic equation (Kupper, 2005). According to Aatique (1997)
and Thomas (2001) there are few methods to solve these equations and is
not straightforward. Furthermore, time errors due to multipath already
exist in the environment and the actual distance could already be added
with range errors. Thomas (2001) proposes using Taylor Series and Weighed
Least Square Estimator, or using Chan`s Method or Cramer Rao Lower Bound
Method. From experience, faster response (processing time) to user`s request
is very important and therefore we decided to use a method called Newton
Raphson. It is efficient in solving non linear equations with its faster
convergence characteristics (Coleman and Li, 1994). With this method we
could solve any non linear triangulation problems such as E-OTD, OTDOA
or uTDOA. Kiusalaas (2005) and Yang et al. (2005) explain the derivation
of Newton Raphson equations.
Newton Raphson`s method requires guessing an initial point for it to
converge fast. We therefore define our technique called Newton Raphson`s
3 circles (NR3C) to be used for triangulation when 3 Node B`s measurements
are detectable. From each of the Node B`s Location Measurement Unit (LMU),
(3GPP TS25.305 V8.0.0, 2007) we can extract the time observed.
Lets say, Ti is total time arrived at the UE as observed from
Node Bi and Ti = ti + tdi
where, ti is the actual time without delay from Node Bi
and tdi is the multipath time delay from Node Bi.
Using survey data for the estimated quadrant area pertaining to the cell
ID, the stored Node Bi time delay, tdi,, could be
subtracted from the total time, Ti.
We can then calculate di (distance in meters from UE to Node
B) for each Node Bi as di = cti, where
c is the speed of light, 3x108 m sec-1.
Now we define the 2 pair of hyperbolic equations. The first pair is the
time difference (time multiply with c produces distance in meters) between
Node B2 and Node B1 and the second pair is time
difference observed between Node B3 to Node B1.
The function, f(x) for NR3C is defined by (1) and (2):
||x coordinate of Node Bi (m)
||y coordinate of Node Bi (m)
With 2 Eq. 2 unknowns, the final estimated location of UE = (x,y) in
meters could be obtained. Initial points of x = 0 and y = 0 will be used
as first guess for NR3C. Maximum iteration is set at 60 and tolerance
is set at 2.2204x10-12. Iteration is terminated if either tolerance
limit is reached first or maximum iteration is completed.
Close Circle Correlation (CCC) technique: Close Circle Correlation
(CCC) technique is based on finding the best convergence point or the
closest (minimum) points between Circle 1 to 2, Circle 2 to 3 and Circle
1 to 3. The center of each circle represents the actual location of each
of the Node B (X and Y coordinates in meters), while the radius of the
circle represents the distance of each Node B (synchronized time of arrival
at UE from LMU of each Node B) to UE (Singh and Ismail, 2005). Figure
4 shows the usage of CCC in a real environment where circles might
not converge as expected due to Non LOS delays or multipath time errors.
The algorithm for CCC technique is as following:
Step 1: Find minimum distance (each point on diameter Circle 1,
each point on diameter Circle 2). Intersection of Circles 1 and 2 will
produce two points (A and B)
Step 2: Find minimum distance (each point on diameter Circle 2,
each point on diameter Circle 3). Intersection of Circles 2 and 3 will
produce two points (C and D)
Step 3: Find minimum distance (each point on diameter Circle 1,
each point on diameter Circle 3). Intersection of Circles 1 and 3 will
produce two points (E and F)
Step 4: Find the best point (along Circle 1 or Circle 2 or Circle
3 that is the closest point to the pairs of points obtained from Step
1, Step 2 and Step 3 above).
In Fig. 4, point G is the best convergence point. It
is the nearest point to B, C and E.
Timing Technique for unknown LOS conditions (time delay data from
each Node B are unavailable): In normal case, we will store all survey
data (Cong and Zhuang, 2005) pertaining to each area (LMU details, time
of delays observed within each grid, environment details, road networks
starting and ending points that passes through the area). Each area is
segmented into grid size of 100x100 m as shown in Fig. 5.
LMU at Node B, like uTDOA based LMU (uplink time of arrival at each Node
B from UE), are able to extract time delays information from each Node
B by comparing (matching) the reference snapshot of serving Node B (site
1) signal`s to each of the observed uplink`s signal of other Node Bs (neighbor
site 2 and 3). Time delays could be obtained from the first strongest
received signal peak (Jativa and Vidal, 2002) along with the time delays
from other multipath peaks of the same Node B (Ahonen and Eskelinen, 2003).
This RMS (Root Mean Square) time delay spread could be subtracted from
the total observed time of arrival at that particular Node B. The actual
time (without delay) from all 3 Node B will then be processed by NR3C
or CCC to estimate UE location.
When there is unknown LOS condition (unknown RMS delay spread information or
unknown multipath delay information for the corresponding LMU per grid area),
averaging technique will be utilized to estimate location.
The averaging technique for NR3C:
Step 1: UIPS instructs simultaneous transmission of timing from
3 Node B (repeated for 3 consecutive times using the same 3 Node B)
Step 2: Use NR3C to calculate the 3 times location estimate for
the same UE
||Average (mean) the 3 estimated location of the same UE. This
process is called First Mean Averaging Estimator of NR3C
||Randomly scan within the boundary of the 3 estimated location of the
same UE as obtained in Step 2.
||UIPS data module will store each area`s information
Basically this method randomly searches for a new mean within
the minimum and maximum boundary of the same estimated UE based on the
3 estimated samples (a square boundary is created based on the 3 times
location estimate). About 5000 iterations are set to randomly search for
a new UE mean estimate. If the average spread is too large and calculation
for UE mean estimate goes outside from the defined boundary, warning will
be sent to the UIPS administrative module, notifying the clocks are not
synchronized or to check the input parameters. This enhanced technique
is called Random Search Averaging Estimator of NR3C.
The averaging technique for CCC:
Step 1: UIPS instructs simultaneous transmission of timing from
3 Node B (repeated for 3 consecutive times using the same 3 Node B)
Step 2: Use CCC to calculate the 3 times location estimate for
the same UE
Step 3: Average the 3 estimated location of the same UE. This
averaging technique is referred to as Averaging Estimator of CCC
For the case of unknown LOS (unknown time delay spread) simulation environment
in urban Kuala Lumpur, each LMU of Node B, will be randomly added with
time delay spread (between 0 and 33 μsec), assuming multipath time
delay reaching the UE are produced by different combination of the ray
(Tranter et al., 2004).
NR3C technique on urban road with known LOS: The Cumulative
Distribution Function (CDF) plot for NR3C technique on urban drive test
route with known LOS conditions is shown in Fig. 6.
Please note that x used here in the CDF plot is the magnitude comparison
of Euclidean distance between UE estimated and UE real and not the same
as the previously used x and y coordinates of UE estimated.
NR3C produced 67% estimated location error at 0, 95% estimated location
error at 1.7 nm and maximum location error of 6.74 nm. Processing time
for one location estimation is 4.22 m sec.
CCC technique on urban road with known LOS: The CDF plot for CCC
technique is shown in Fig. 7 for UMTS network on the
same drive test urban route.
Performance of enhanced techniques when multipath delay
information is not known
||CDF Plot for UE estimated using NR3C technique
||CDF plot for estimated UE using CCC technique
CCC technique produced 67% estimated location error at 2.04 m, 95% location
error at 3.2 m and maximum location error of 17.93. Processing time for
one estimated UE is 1.38 sec.
Timing Technique for unknown LOS conditions (time delay information
from Node B are not known): When multipath time delay data are unavailable,
averaging of NR3C and averaging of CCC will be used. Table
1 shows the CDF performance (simulation of urban Kuala Lumpur data
classified as unknown LOS) comparison between the averaging techniques
at 67%, 95% and maximum error of estimated location.
NR3C provides better estimation accuracy, with maximum error of
6.74 nm (Fig. 6) when compared to CCC, with maximum
error of 17.93 meters (Fig. 7), in known LOS urban environment.
NR3C processes one UE location estimate in 4.22 m sec and is much faster
than CCC, which takes 1.38 sec to process an estimate. NR3C converges
faster than any optimization algorithm like Genetic Algorithm (GA) or
Pattern Search. GA takes several seconds to converge and sometimes cannot
find accurate minimum for the intersections.
In cases when there is unknown multipath delay information (unknown LOS
environment), averaging CCC technique works well and is reliable. Averaging
(averaging 3 location estimates for the same UE) for CCC technique produced
67% estimated location error at 50.67 m and 95% estimated location error
at 218 m while First Mean Averaging of NR3C produced 67% error at 54 m
and 95% error at 233 m. Random Search Averaging of NR3C produced 67% error
at 52 m and 95% error at 427 m. Random Search Averaging 67% error is slightly
better than First Mean Averaging of NR3C, but Random Search Averaging
is the worst at 95% error.
From the results, we can assign the highest QoS level (UIPS accuracy
of position on LBS request and Emergency search) for NR3C when time delay
is known and assign the highest level to CCC averaging technique when
LOS information is not known. But if UIPS database contains more than
25% of the unknown LOS environments for all Node Bs, than First Mean Averaging
will be assigned as the highest QoS due to faster processing time of 0.065
sec (per each location estimate) compared to the Averaging of CCC, which
takes 4.128 sec.
In either case UIPS QoS should not only depend on timing technique`s
accuracy as a final confidence check but to use other benchmark such as
Propagation Loss data (Lhomme et al., 2006). Prior calculations
should be done and stored as thresholds for each Node B, where through
statistical estimation we could estimate the propagation losses from each
station and further calculate the (Received Signal Strength Indicator
versus distance related to the propagation loss) distance of UE from the
Node B (McGuire et al., 2003). This estimated RSSI (Received
Signal Strength Indicator) value could be compared to the real RSSI obtained
via NMR. Maximum power level and maximum distances should also be stored
in the UIPS Database for each cell even though for UMTS, this information
is not so straightforward. For example if there is a new construction
of building in the location area causing a lot of RF shielding and reflection
where the user is requesting for LBS, the time delay for assumption in
known LOS areas would falsify the estimates as being far (far in distance)
due to longer delay. In the real world scenario, not all area information
could be stored in the database and therefore some measure of confidence
check and rule based decision need to be implemented for UIPS as in (3).
||Known LOS distance after time delay correction
||Calculated non linear fitted distances based on propagation
loss information for each NB
||Maximum cell distance (size) of ith Node B cell used
for timing calculations
Equation 3 should also be used for unknown LOS check in order to avoid
overly predicting longer delays of time.
Also as another check, distance difference (time difference of arrival
from 2 Node B) should not be larger than the actual distance between the
2 Node Bs.
Finally, another threshold used to accept or reject the timing based
LDT before another LDT is applied, is by using angle check:
||Directional angle of Cell ID (Primary Scrambling
Code) for the Node B
||Azimuth angle from Node B directional antenna
to estimated UE
||Average scale multiplier for the Beamwidth
From our experiments based on 3 sector cell, we will use k = 2 as a buffer
to compensate spill over coverage from Node B`s directional antenna (for
coverage outside its beamwidth). This happens when intra or inter Node
B`s neighbours are not as dominant as the directional signal`s beam of
the serving Node B.
Location based services, navigation and emergency callers` locations
are a few examples of how important estimation of mobile user`s location
really is. The aim of this research is to develop efficient computing
techniques or LDT based on time measurements for known and unknown LOS
environments in UMTS networks. In this research we have developed NR3C
and CCC techniques for triangulation based on time measurements obtained
from 3 or more Node B. Based on simulation results, NR3C technique in
known LOS (assuming ideal environment, synchronized time measurements
and accurate calibration of Node Bs` coordinates), produced maximum error
of 6.74 nm and CCC produced maximum error of 17.93 m. NR3C is based on
non linear numerical computations while CCC is based on geometrical computations.
The processing time for each location estimate is 4.22 milliseconds using
NR3C and 1.38 sec using CCC. For huge LBS requests NR3C is excellent and
is assigned as the highest QoS. But when time delay is not known or cannot
be calculated by LMU, then averaging of a few estimates is performed.
In unknown multipath time delay conditions, averaging of CCC method is
reliable, with 95% error at 218 m. First Average estimator of NR3C produced
95% error at 233 m and Random Search Estimator of NR3C produced 95% error
at 413 m. Due to its longer processing time, CCC averaging should only
be used in unknown LOS to accommodate for less frequent LBS request traffic
and First Mean Averaging of NR3C should be used for huge requests of location
estimation in unknown LOS conditions. Finally all LDT/techniques need
to be verified through acceptance thresholds (RSSI, propagation loss vs.
distance, road networks map matching, cell size, Node B Directional Antenna
Angle) before final location based services are provided to user. For
future work, we are developing a hybrid technique using signal strength
matching with time triangulation techniques.
We would like to thank the Ministry of Science Technology and Innovation,
Malaysia for supporting the development of LBS testbed in cellular environments
under Grant 01-01-02-SF0344.