Development of Universal Intelligent Positioning System Techniques in Universal Mobile Telecommunications System Networks

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.

Fig. 1:	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.

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.

Fig. 2:	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.

Fig. 3:	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:

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, T_i is total time arrived at the UE as observed from Node B_i and T_i = t_i + t_di

where, t_i is the actual time without delay from Node B_i and t_di is the multipath time delay from Node B_i. Using survey data for the estimated quadrant area pertaining to the cell ID, the stored Node B_i time delay, t_di,, could be subtracted from the total time, T_i.

We can then calculate d_i (distance in meters from UE to Node B) for each Node B_i as d_i = ct_i, where c is the speed of light, 3x10⁸ 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 B₂ and Node B₁ and the second pair is time difference observed between Node B₃ to Node B₁.

The function, f(x) for NR3C is defined by (1) and (2):

(1)

(2)

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.

Fig. 4:	CCC technique

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

Fig. 5:	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.

Table 1:	Performance of enhanced techniques when multipath delay information is not known

Fig. 6:	CDF Plot for UE estimated using NR3C technique

Fig. 7:	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).

(3)

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:

(4)

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.