J. Cent. South Univ. (2012) 19: 2067-2072 

DOI: 10.1007/s11771-012-1246-4

Offline handover location positioning for map matching of mobile probes

YUAN Yue-ming(袁月明), GUAN Wei(关伟)

Key Laboratory for Urban Transportation Complex System Theory and Technology of Ministry of Education

(Beijing Jiaotong University), Beijing 100044, China

? Central South University Press and Springer-Verlag Berlin Heidelberg 2012

Abstract: Handover location technology was employed for collecting road traffic information in a number of field projects, and the project results demonstrate that it is a supplementary and promising means of road traffic information collection for further traffic supervision and maintenance. Because handover location technology is one kind of pattern matching based location technologies, offline handover location positioning is an essential problem to be studied for successfully matching mobile probes on GIS map. Offline handover location positioning method involves two stages, handover location positioning respectively via two weighted models and an optimized model based on the intermediate results obtained in the first stage. A preliminary field test is conducted on a stretch of freeway in the inner suburban region in Beijing, and performance evaluation results show that the proposed method is superior to standard least square model in location accuracy and location precision, which is an effective method of offline handover location positioning.

Key words: mobile probe; handover location technology; offline handover location positioning

1 Introduction

With the rapid progress of urbanization in China, traffic congestion has become more and more severe and turned into a bottleneck of city development. In order to reduce or alleviate traffic congestion, intelligent transportation system (ITS) has been implemented in many big cities in China. Real-time, accurate and reliable road traffic information collection is regarded as one of key elements in ITS. Besides available road traffic information gathered from fixed sensors or floating car detectors with on-board GPS equipments, mobile phones as probes are proposed to be a supplementary and promising means of traffic information collection with the increase of mobile phone subscribers, and have achieved great attention in the current studies of ITS.

Over the past few years, a number of wireless location technologies have been investigated to collect traffic information, such as Cell-ID, angle of arrival (AOA), time of arrival (TOA), time difference of arrival (TDOA), handover, GPS and AGPS. Evaluation results of many implemented field projects indicated that it was not practically feasible to employ Cell-ID, AOA, TOA or TDOA to collect real-time and area-wide traffic information due to large positioning errors, necessary extra changes on mobile phones or cellular network [1-7]. On the other hand, the most promising evaluation results basically come from the field projects using handover location technology or GPS-based location technology for mobile probe positioning [7-15]. Although handover location technology cannot provide location data of the same quality as GPS-based location technology, handover data of mobile probes can be easily obtained from the current cellular network and handover location technology could not cause great increase on the communication costs between mobile probes and traffic control center (TCC). Therefore, handover location technology is focused on in this work.

Handover is one of mobility management services of mobile phone subscribers in the cellular network, which will be performed when an in-use mobile probe travels from one cell to another cell [5]. From the standpoint of traffic management and monitoring, the consecutive handovers of mobile probes in the cellular network will be available information for reconstructing the moving trajectories of the mobile probes and extracting road traffic information. However, different from GPS data, handover data from the cellular network mainly include three data attributes, From Cell-ID, To Cell-ID and timestamp, not including the position coordinates of handovers. Considering that the cell distribution in the cellular network will not frequently change, an assisted database can be developed for accomplishing map matching of mobile probes via overlapping the cellular network onto the road network [8-9, 18], which not only contains From Cell-ID and To Cell-ID of each handover, but also contains the position coordinates of each handover. Accordingly, handover data of an encrypted sampled mobile probe can be successfully matched onto the GIS map via searching the best-matching handover patterns in the assisted database. In the development of the assisted database, offline positioning handover on the road network is the most significant problem to be solved. In this work, the assisted database is called handover location database and this problem is called offline handover location positioning. As a rule, handovers can firstly be bounded in a zone when the road network is overlapped with the cellular network, and then the position coordinates of handovers can be determined by calculating the average value of several measurements from repeated field tests. However, radio propagation in the actual environments will be influenced by multipath propagation, non-line of sight (NLOS) propagation and other factors. As a result, measurements from repeated field tests are likely to extend beyond the normal scope of handover zones under some circumstances, which cause that the average location positioning method can no longer generate accurate enough data for successful map matching of mobile probes. Therefore, the problem of offline handover location positioning was studied in this work in order to provide accurate and reliable location data for map matching of mobile probes.

2 Offline handover location positioning method

2.1 Problem statements

Handover is one of mobility management services in the cellular network. The common criterion of triggering a handover is the receiving signal strength (RSS) criterion. When an in-use mobile phone travels from one cell to another cell, if the RSS of the current cell is less than that of the target cell minus a predefined threshold value, a handover will be triggered (in Fig. 1). Handover data of anonymously sampled mobile probes can be extracted through monitoring signaling messages in the cellular network [5-7]. Assuming handover data of an anonymously sampled mobile probe extracted from the cellular network are {h₁, h₂, …, h_n}, if we know the locations of handovers {h₁, h₂, …, h_n}, the moving trajectory of the mobile probe can be derived with the aid of GIS map. However, the cellular network does not measure the position coordinates of each handover every time, so the locations of handovers cannot be got from the cellular network and only can be determined in advance so as to accomplish map matching of mobile probes [19].

Fig. 1 Sketch map of handover

Generally, field tests will be repeatedly carried out several times to measure the location of each handover. Assuming that the measurements of the i-th handover are (x_ij, y_ij) (i=1,…, n; j=1, …, n_i), where n and n_i are the number of handovers and the number of measurements of the i-th handover, the distance between the location of the i-th handover and the j-th measurement can be calculated as

                  (1)

where (x_i, y_i) are the location of the i-th handover to be estimated.

Theoretically, the measured distances are modeled as

,                       (2)

where is the normal average distance between repeated measurements and the location of the i-th handover (corresponding to the normal scope of the i-th handover zone); () is measurement noise that is generally considered to be independent and identically distributed.

Based on n_i measurements of the i-th handover, estimating the optimal location of the i-th handover can be solved by standard least squares (SLS) model:

                       (3)

Then, the least squares estimations can be served as the matched location of the i-th handover:

,                    (4)

In this work, the location of the i-th handover solved by SLS model is symbolized as.

Actually, handover operation will be significantly disturbed by path loss, multipath propagation, non-line of sight propagation and other factors. As a result, the measurements of a handover in the repeated field tests sometimes will extend beyond the normal scope of the handover zone. In such circumstances, standard least square model cannot generate reliable data for map matching because standard least square model does not have the advantage of resisting large errors. Considering that handovers with great errors may cause false map matching or failure on map matching of mobile probes, in this work, the problem of offline handover location positioning is to determine the locations of handovers that have enough accuracy for map matching of mobile probes.

2.2 Proposed offline handover location positioning method

In order to improve the accuracy of handover location data for map matching of mobile probes, the proposed offline handover location positioning method involves two stages: weighted offline handover location positioning with RMSE (root mean square error) corrections (WOHLP-RMSE) or GDOP (geometric dilution of precision) corrections (WOHLP-GDOP), and optimized offline handover location positioning by employing chaos optimization algorithm (OOHLP). The schematic diagram of the proposed offline handover location positioning method is shown in Fig. 2.

Fig. 2 Schematic diagram of proposed offline handover location positioning method

In the cellular network, RMSE and GDOP are two common indexes for assessing location accuracy. For repeated measurements of the i-th handover  (), RMSE (E_R) and GDOP (P_G) are separately defined by

        (5)

                        (6)

where are the location of the i-th handover to be estimated; .

The main ideas of two weighted offline handover location positioning models are to determine the location of handovers by the introduction of classification and weighting. Taking WOHLP-RMSE for example, the determination of the i-th handover location are divided into four steps: 1) All raw measurements of the i-th handover are firstly divided into three categories by fuzzy c-means clustering algorithm; 2) RMSE corrections after deleting the raw measurements of the p-th category are calculated by Jackknife resampling method [20-21]; 3) Weights based on RMSE corrections are calculated;  4) The location of the i-th handover according to the determined weights and the position coordinates of the clustering centers are determined.

For the raw measurements of the i-th handover, assuming that the locations of three clustering centers calculated by fuzzy c-means clustering algorithm in the 2D plane are  according to Jackknife resampling method, if we delete one category every time, RMSE and GDOP corrections from the reduced measurements according to Eqs. (5) and (6) can be

;

                   (7)

where (k=1, 2; p=1, 2, 3) denote RMSE and GDOP corrections calculated from the reduced samples with measurements of the p-th category removed, with k=1 for RMSE, and k=2 for GDOP.

For RMSE corrections, weights can be calculated as follows:

                    (8)

                 (9)

For GDOP corrections, weights can be calculated as follows:

                 (10)

                (11)

Thereby, the position coordinates of the i-th handover solved by WOHLP-RMSE and WOHLP-GDOP can be obtained:

          (12)

where() are the i-th handover locations separately calculated by WOHLP-RMSE and WOHLP-GDOP (k=1 for RMSE, and k=2 for GDOP).

In order to achieve the optimized location accuracy of the i-th handover, a combinational model is proposed based on the above intermediate results calculated by WOHLP-RMSE and WOHLP-GDOP:

             (13)

             (14)

where α and β are parameters, , and β=0 or 1.

By comparing the results calculated by the proposed WOHLP-RMSE and WOHLP-GDOP models with those calculated by SLS model, there are four cases, as given in Table 1. For Case IV, the results calculated by SLS model are regarded as the optimal handover location. For Case I-Case III, the ranges of parameter α and the values of parameter β are set in Table 1.

Table 1 Parameters α and β

For Case I-Case III, the problem of offline handover location positioning is converted into the problem of estimating the optimal solution of parameter α. The optimal solution of parameter α of the i-th handover follows two objects: The average square of measurement errors of the i-th handover should be the minimum and the variance of measurement errors of the i-th handover should be the minimum. In the meantime, the optimal solution of parameter α meets the following constraints: The average measurement errors of the i-th handover will be less than those respectively calculated with GDOP and RMSE corrections. Here, the optimized offline handover location positioning (OOHLP) model for the i-th handover is given by

      (15)

                       (16)

where λ is a risk aversion parameter, and λ=0.9 in this work;  is the distance between the j-th measurement and the location of the i-th handover to be estimated, ; is the average distance, ; (k=1, 2), are the average distances separately calculated with GDOP and RMSE corrections.

In order to estimate the location of the i-th handover, the above OOHLP model is converted into an unconstraint minimization model via a penalty function:

              (17)

where M is a large value.

In this work, we apply chaos optimization algorithm to estimate the optimal solution of Eq. (17). The logistic map is used for generating chaos random data:

                       (18)

where μ is a parameter, and in this work μ=4.

The value of parameter α is determined as follows:

                (19)

where and are the upper and lower boundaries of parameter α [22].

The steps of the solution algorithm are explained as follows:

Step 1: Set the maximum iteration times of chaos optimization algorithm N and t=0, and randomly generate an initial value of the chaotic variable z(0)∈  (0, 1);

Step 2: Calculate the position coordinates of the i-th handover by standard least squares model and two weighted least squares models ,  and;

Step 3: Determine the value of parameter β based on the above results;

Step 4: Determine the value of parameter α(t) via substituting z(t) into Eq. (19);

Step 5: Calculateof the i-th handover based on parameters α(t) and β and calculate the object function Eq. (17);

Step 6: If t=0, α^*=α(t), and Q^*=Q(α^*, β), then set t=t+1 and return to Step 4; if 0*=arg min(Q(α(t), β), Q^*), and Q^*=Q(α^*, β), then set t=t+1 and return to Step 4; if t>N, then chaos optimization algorithm stops;

Step 7: Output the final location of the i-th handover.

3 Performance evaluations

In order to evaluate the performances of the proposed offline handover location positioning method, handover data were collected in a preliminary field test on a stretch of inner-suburban freeway in Beijing, China. As one kind of pattern matching based location techniques, handover location technology still has bad performances in the urban center. Therefore, the test car repeatedly ran thirty times on the test path. The length of the test path is about 8 km, including four freeway links, an on-ramp link and an off-ramp link, as given in   Table 2.

Table 2 Surveyed road links

Performance evaluations of the proposed offline handover location positioning involve the studies of location accuracy and location precision. Table 3 lists the statistic results of location accuracy of handovers using the proposed method and SLS model, which indicates that the proposed method can generate handover location data with corresponding higher accuracy than standard least squares model. According to Table 3, the average location accuracy of handovers calculated by the proposed method is 32.43 m, which can substantially guarantee the feasibility of map matching of mobile probes moving on the inner-suburban freeways. Figure 3 shows the histogram of handover location accuracy separately calculated by the proposed method and SLS model. From Fig. 3, the percentage of handovers with location accuracy less than 60 m obtained by the proposed method is about 80.67% and the percentage of handovers with location accuracy larger than 150 m is only 3.36%, which are separately improved by 8.83% and reduced by 1.55% compared with results obtained by SLS model.

Table 3 Statistic results of handover location accuracy

Figure 4 shows the effect of number of raw measurements on the improvement rate of location accuracy. Handovers whose number of raw measurements is less than 3 are not included. From   Fig. 4, it is also understood that handover location data determined by the proposed method have better performances than those determined by SLS model. Moreover, the improvement rates of handovers with small number of raw measurements are greatly larger than those of handovers with large number of raw measurements, which indicates that the proposed method will generate better results for handovers with small number of raw measurements. This also suggests that the proposed method has significant advantages of solving the problem of offline handover location positioning for map matching of mobile probes moving on the inner-suburban freeways, because the number of field tests could not be large in the practical application especially under the consideration of funds.

Fig. 3 Histograms of handover location accuracy separately calculated by proposed method (a) and SLS model (b)

Fig. 4 Relationship between improvement rate and number of raw measurements

4 Conclusions

1) An offline handover location positioning method is proposed for accomplishing map matching of mobile probes, including two stages. Firstly, handover locations are determined by two weighted models using GDOP and RMSE corrections as weights; Then, handover locations are determined by an optimized model by employing the intermediate results obtained in the first stage, which is solved by chaos optimization algorithm. Performance evaluations demonstrate that the proposed method is feasible and effective, and handover location data processed by the proposed method have enough quality for map matching of mobile probes.

2) Next work should be focused on how to develop robust map matching and traffic parameter estimation algorithm especially in the case of handovers with great errors. In addition, it is commonly believed that it is dangerous to make or receive phone calls at high speeds traveling on the freeways, so sample size of handover data actually appears to be insufficient for collecting traffic information of highways at some time. Further studies should also take account of data fusion of multiple traffic data sources to obtain accurate traffic information in the road network.

References

[1] ROSE G. Mobile phones as traffic probes: practices, prospects and issues [J]. Transport Reviews, 2006, 26(3): 275-291.

[2] FONTAINE M D. Improving the effectiveness of wireless location technology-based traffic monitoring: An exploration of system design issues [D]. Charlottesville: University of Virginia, 2005: 61-64.

[3] SMITH B L, FONTAINE M D, BEATON J, DEJARNETTE E, HENDRICKS A, TENNANT L L. Private-sector provision of congestion data [R]. Charlottesville: University of Virginia Center for Transportation Studies, Virginia Transportation Research Council, 2007.

[4] HSIAO W C M, CHANG S K J. Introduction of segment-based traffic information estimation method using cellular network data [J]. Journal of the Eastern Asia Society for Transportation Studies, 2005, 6: 1610-1623.

[5] CACERES N, WIDEBERG J P, BENITEZ F G. Review of traffic data estimation extracted from cellular networks [J]. IET Intelligent Transportation System, 2008, 2(3): 179-192.

[6] STEENBRUGGEN J, BORZACCHIELLO M T, NIJKAMP P, SCHOLTEN H. Real-time data from mobile phone networks for urban incidence and traffic management—A review of applications and opportunities [EB/OL]. http://hdl.handle.net/1871/15715, 2010-02-23.

[7] QIU Z J. Macroscopic traffic state estimation for large scale freeway network using wireless network data [D]. Madison: University of Wisconsin-Madison, 2007: 18-31.

[8] SANKAR R, CIVIL L. Traffic monitoring and congestion prediction using handoffs in wireless cellular communications [C]// 47th IEEE Vehicular Technology Conference. New York: IEEE, 1997: 520-524.

[9] SANKAR R, CIVIL L. Intelligent traffic monitoring system using wireless cellular communications [C]// Proceedings IEEE Southeastcon’97. Engineering the New Century. New York: IEEE, 1997: 210-214.

[10] BAR-GERA H. Evaluation of a cellular phone-based system for measurements of traffic speeds and travel times: A case study from Israel [J]. Transportation Research Part C, 2007, 15(6): 380-391.

[11] GUNDLEGARD D, KARLSSON J M. Handover location accuracy for travel time estimation in GSM and UMTS [J]. IET Intelligent Transportation Systems, 2009, 3(1): 87-94.

[12] HERRERA J C, WORK B D, HERRING R, BAN X G, JACOBSON Q, BAYEN A M. Evaluation of traffic data obtained via GPS-enabled mobile phones: The mobility century field experiment [J]. Transportation Research Part C, 2010, 18(4): 568-583.

[13] VALERIO D, D’ALCONZO A, RICCIATO F, WIEDERMANN W. Exploiting cellular networks for road traffic estimation: a survey and a research roadmap [C]// IEEE 69th VTC Spring. New York: IEEE, 2009: 3171-3175.

[14] VALERIO D, WITEK T, RICCIATO F, PILZ R, WIEDERMANN W. Road traffic estimation from cellular network monitoring: a hands-on investigation [C]// IEEE 20th International Symposium on Personal, Indoor and Mobile Radio Communications. New York: IEEE, 2009: 3035-3039.

[15] QUANG TRAN MINH, KAMIOKA E. Granular quantifying traffic states using mobile probes [C]// IEEE 72nd VTC Fall. New York: IEEE, 2010: 1-6.

[16] ZHAO Y L. Mobile phone location determination and its impact on intelligent transportation systems [J]. IEEE Transactions on Intelligent Transportation Systems, 2000, 1(1): 55-64.

[17] SUN G L, CHEN J, GUO W, LIU K J R. Signal processing techniques in network-aided positioning a survey of state-of-the-art positioning designs [J]. IEEE Signal Processing Magazine, 2005, 22(4): 12-23.

[18] YOO B S, KANG S P, CHON K, KIM S G. Origin-destination estimation using cellular phone BS information [J]. Journal of the Eastern Asia Society for Transportation Studies, 2005, 16: 2574-2588.

[19] YANG Fei, QIU Wei-yi. Mobile phone location based real time traffic data collection technique [J]. Urban Transport of China, 2005, 3(4): 63-68.(in Chinese)

[20] GENTLE J E. Elements of computational statistics (reprint edition) [M]. Beijing: Science Press, 2006: 76-82.

[21] BI Hua, LIANG Hong-li, WANG Jue. Resampling methods and machine learning [J]. Chinese Journal of Computers, 2009, 32(5): 862-877. (in Chinese)

[22] YANG Di-xiong, LI Gang, CHENG Geng-dong. Comparative study on chaos optimization algorithm for nonlinear function [J]. Chinese Journal of Computational Mechanics, 2004, 21(3): 257-262.(in Chinese)

(Edited by YANG Bing)

Foundation item: Projects(71131001, 60874078) supported by the National Natural Science Foundation of China; Project(NCET-08-0718) supported by Program for New Century Excellent Talents in University of China

Received date: 2011-04-19; Accepted date: 2011-06-27

Corresponding author: GUAN Wei, Professor; Tel: +86-10-51688520; E-mail: weig@center.njtu.edu.cn