Networking?GPS:Cooperative Vehicle Localizatiioonn Using Commodity GPS in Urban Area

(Department of Computing，Hong Kong Polytechnic University，Hong Kong 999077，China)

Networking?GPS:Cooperative Vehicle Localizatiioonn Using Commodity GPS in Urban Area

Chisheng Zhang,Jiannong Cao,and Gang Yao

(Department of Computing，Hong Kong Polytechnic University，Hong Kong 999077，China)

A challenging issue in intelligent transportation systems(ITS)is to accurately locate moving vehicles in urban area.Considerable efforts have been made to improve the localization accuracy of standalone GPS receivers.However，through empirical study，we found that the latitude and longitude values generated by GPS receivers fluctuate significantly because of the multipath effect in urban areas.The relative distances between neighboring vehicles with similar GPS signal data in terms of satellite sets and signal strength are much more stable in such a scenario.In this paper，we propose a cooperative localization algorithm，Networking?GPS，to improve the accuracy of location information for vehicular networks in urban area using commodity GPS receivers.First，atom redundantly rigid graphs of vehicles are constructed according to the similarity of neighboring GPS data.Then，through rigidity ex?pansion，local accuracy can enforce global accuracy.Extensive simulations based on the real road network and trace data of vehi?cle mobility demonstrate that Networking?GPS can improve the accuracy of the entire system.

vehicular communication;cooperative localization;rigidity formation

1 Introduction

Avehicle localization system for urban areas is very challenging to design because of several rigorous requirements[1].Localization accuracy should be satisfied by the users’applications，and the navi?gation system requires lane?level precision in order to differen?tiate between the different directions of lanes.GPS is the most feasible and robust solution for metropolitan?scale localization systems.However，GPS devices are inaccurate in urban areas because of severe multipath effect[2].

Our goal is to significantly improve the accuracy of localiza?tion information from GPS measurements by using commodity devices.We propose an accurate and cooperative localization algorithm，called Networking?GPS，for public transportation systems in urban areas.Networking?GPS is based on the obser?vation that relative distances between neighboring vehicles with similar GPS signal data(in terms of satellite sets and sig?nal strength)are much more stable.Networking?GPS con?structs the atom redundantly rigid graphs with neighboring ve?hicles according to similarity of GPS data.Then，through rigidi?ty expansion，local accuracy can enforce global accuracy.We have designed Networking?GPS using the commodity GPS de?vices without any modification of built?in GPS algorithms.The contributions of this paper are summarized as follows:

·We conduct experiments on several commodity GPS receiv? ers to explore the relationship between the multipath effect and GPS measurements.We reveal that there are correla?tions between nearby GPS measurements under similar im?pact of multipath effect.

·To safeguard the accuracy of noisy GPS measurements against the multipath effect，we develop a rigid expansion al?gorithm by exploiting the signal similarity and ranging infor?mation from GPS measurements.

·We propose an accurate and cooperative localization algo?rithm，called Networking?GPS，for public transportation sys?tems in urban areas.We run extensive simulations based on a real road network and trace data of vehicle mobility and determine that Networking?GPS improves the accuracy of the entire system.

The remainder of the paper is organized as follows.In sec?tion 2，we discuss related work.In section 3，we analyze the re?sults from field testing and discuss opportunities to improve lo?calization accuracy through neighboring GPS data.In section 4，we present the design of the Networking?GPS.In section 5，we evaluate the performance of Networking?GPS.Section 6 concludes the paper.

2 Related Work

2.1 GPS-Based Positioning Technology

A GPS receiver calculates its position by precisely timing

the signals sent by GPS satellites high above the Earth.Each satellite continually transmits messages that include the time the message was transmitted，precise orbital information(the ephemeris and the general system health，and rough orbits of all GPS satellites(the almanac).The receiver uses the messag?es it receives to determine the transit time of each message and computes the distance to each satellite.These distances，along with the satellites’locations，are used with the possible aid of trilateration，depending on which algorithm is used，to com?pute the position of the receiver.

Three satellites might seem enough for positioning because space has three dimensions，and a position near the Earth’s surface can be assumed.However，a very small clock error multiplied by the speed of light(at which satellite signals prop?agate)results in a large positional error.Therefore，receivers use four or more satellites to calculate the receiver’s location and time.

2.2 Mitigation of Multipath Effect

In urban environments，multipath is the dominant factor con?tributing to inaccuracy[2]-[4].Traditional approaches to mul?tipath mitigation focus on detecting multipath?induced biases and alleviating their influence on the triangulation process. There are two categories of solutions to the multipath effect: Receiver autonomous integrity monitoring and peak separa?tion.However，these two methods often fail to improve accura?cy in urban areas because the model of multipath in the two so?lutions is a single reflection off of a single object.

An alternative approach to dealing with multipath in urban environments is a statistical model that accurately captures be?havior of pseudo?range error distributions observed in real da?ta，such as asymmetry，fat?tails，interdependence among errors，and dependence on multiple observable factors[5].However，complexities associated with an accurate statistical model make estimation computationally challenging.Anti?multipath triangulation[6]is a proprietary technology developed to ad?dress this challenge.However，it is difficult to collect enough data to represent the complex multipath effect.

3 Motivation and Approach

In this section，we present and analyze the experimental re?sults of GPS measurements using different commodity devices. Then，we discuss the opportunities to improve the localization accuracy through neighboring GPS data.

3.1 Preliminary Experiments

In a practical GPS localization system，GPS receivers calcu?late the positions after receiving enough valid GPS signals. When the results are ready，GPS chips write the values in the form of ASCII codes to interfaces such as serial or USB ports. The National Marine Electronics Association(NMEA)stan?dard describes the interface between marine electronic equip? ment and is a common format for GPS result output.The infor?mation given by the GPS receiver includes latitude and longi?tude，altitude，speed，and time.In addition，NMEA allows pro?prietary sentences for private companies，which use these sen?tences as control information or output from GPS.

To examine the effect of multipath on GPS performance，we deployed four GPS receivers in different scenarios.Of the four GPS receivers，two have built?in SiRFstar?III GPS chips，and the other two have MTK GPS chips.After analyzing the GPS output，the SiRFstar?III?based GPS receivers follow the stan?dard NMEA format.However，the MTK?based GPS receivers include some proprietary sentences.For ease of system design，we first reconfigured the MTK?based GPS receivers and con?verted the output format from the proprietary messages to stan?dard NMEA sentences.Then，we fixed the GPS receivers on four corners of a square board.The distance between two GPS receivers can be ignored considering the size of the receiver. We set the sampling rate of GPS receivers to 1 s，which means that every 1 s，devices report their results to the interfaces.

Both stationary and moving scenarios are considered in our experiments.In the stationary scenario，we placed the board in two different locations.First，we carried out the experiment in an open?sky environment，and then we placed the board out?doors near our office building.We collected all the GPS raw re?sults from serial ports for further analysis.In the moving sce?nario，we put the board on the top of a taxi and obtained the GPS output during a round trip in the downtown district.

The results are shown in Fig.1.The average GPS measure?ment errors are plotted against the experiment times.We found that GPS localization is relatively stable in an open?sky envi?ronment;however，the multipath effect severely degrades local?ization built?up environments and moving scenarios in urban areas.Localization errors can be up to hundreds of meters.

3.2 Similarity between GPS Signals

In the raw GPS result output，there is one type of sentence called GPGSV，which means GPS Satellite in View.This shows data about the satellites that the unit might be able to find based on its viewing mask and almanac data.It also shows current ability to track this data.One GPGSV sentence only can provide data for up to four satellites and thus there may need to be 3 sentences for the full information.The message format of GPGSV is $GPGSV,m,n,vv,i1,e1,a1,s1,...,*CS ，whereTis the total number of messages，andMis mes?sage number(1 to 3).In every GPGSV message，there is up to four field group，as i1,e1,a1,s1，which stands for Pseudo Random Noise(PRN)code，Elevation in degrees，Azimuth in degrees and signal to noise ratio(SNR)from the respective satellites.

▲Figure 1.Localization variation with multipath effect.

In the NMEA standard，the field called SNR is often re?ferred to as signal strength.SNR is an indirect but more useful value than raw signal strength.SNR can range from 0 to 99 and is measured in decibels according to the NMEA standard. Zero is a special case and may be shown on satellites that are in view but not being tracked.Much effort needs to be made to reveal the correlation between SNR of GPS signals and the multipath effect.It has been reported that SNR depends on factors，such as GPS satellite transmit power，space loss and at?mospheric attenuation，that are external to the receiver，and factors such as receiving antenna gain，tracking loop design and multipath effect，that are local.However，most of the work still tried to design the GPS algorithm to improve the perfor? mance of standalone GPS receivers.

Here，we utilize raw GPS data，especially SNR data and lo?calization information，from nearby GPS receivers to improve the overall localization of multiple GPS receivers.Through the GPS raw data，we can obtain the corresponding SNR values of GPS signals from different satellites.To capture the spatio?tem?poral similarity in SNR variation from GPS signals，we devise a scalable representation of this information in form of a correla?tion matrix，S(m,n).Each individual column corresponds to an SNR observation from GPS signal in a particular time，includ?ing the SNR values from m GPS satellites sensed by receivers. Each row is an n?element correlation vector，which means the signal variation from one particular GPS satellite in time do?main.We captured the dominant variation patterns by using singular value decomposition(SVD)of the correlation matrix. SVD has the two main advantages:1)it helps to convert high dimensional and high variable data set to lower dimensional space by exposing the internal structure of the original data more clearly;2)it is robust to noisy data and outliers，which fa?cilitates the further data processing.

By SVD，the correlation matrix，S(m,n)，can be represented as a product of three matrices:an orthogonal matrix U，a diago?nal matrix A，and the transpose of an orthogonal matrix V. Therefore，we have S=U A VT，where UTU=I=V VT，and A is a m?by?n matrix with r non?zero entries on its main diagonal containing the square roots of eigen values of matrix S in de?scending order of magnitude.The singular values of A={a1, a2,...,ar}and the percentage of power captured by each eigen vector of matrix S is calculated by

We use the eigen vectors of association matrix S to quantita?tively measure the similarity between SNR values from differ?ent GPS receivers.For example，GPS raw data at two different locations，with respective eigen vectors as X={x1,x2,...,xrx}and Y={y1,y2,...,yry}.The signal similarity can be calculated by the weighted sum of pair wise inner product of their eigen vectors as

Sim(X,Y)is quantitative measure index that shows the close?ness of two GPS observation data in spatio?temporal dimen?sion.The value of similarity lies between 0≤Sim(X,Y)≤1.A higher value is derived from GPS data with similar correlation patterns.According to(2)，we revisited the experiment results and checked the relationship between the similarity of SNR values and the relative distance(Fig.2).

The relative distance has a strong correlation with the sig?nal similarity.In Fig.2a and Fig.2b，relative distance between different static GPS receivers still varies because of severe multipath near tall buildings.However，when the signal simi? larity increases，the relative distance between the considered GPS receivers decreases correspondingly.In Fig.2c，the cumu?lative distribution function(CDF)between GPS signal similari?ty and measurement accuracy are shown through pair?wise comparison from our experiment results.We set the accuracy threshold for relative distance to 0.5 m，and we assume that the relative distance is zero when the calculated relative distance is not greater than 0.5 m.We find that in static scenario，when the similarity reaches to 0.9，the relative distance is almost equal to zero，with the possibility of 75%.From this observa?tion，this method provides an accurate way to achieve local rel?ative localization against the multipath effect based on GPS raw data.

4 Design of Networking?GPS

In this section，we present the cooperative vehicle localiza?tion algorithm，called Networking?GPS，and analyze the impact of the key parameters on the accuracy performance of the pro?posed localization algorithm.

4.1 Overview

The Networking?GPS algorithm can run on a central server or can be executed in each vehicle in a distributed way.We in?vestigate the centralized version of Networking?GPS algorithm in this work，and we will study the distributed version in our fu?ture work.

In a vehicular network，vehicles with Internet connection have commodity GPS receivers for localization or navigation. GPS receivers calculate the positioning information and for?ward the raw GPS data to a central server.The raw GPS data is encapsulated in NMEA format.In the algorithm，we assume that the edge between two GPS receivers is a normal edge if a similarity index between them，calculated using(2)，is greater than a threshold δ.Before describing the algorithm design in detail，we provide some preliminary knowledge about rigidity and redundant rigidity[7].

Definition 1:A rigid graph is an embedding of a graph in a Euclidean space that is structurally rigid.A graph is redun?dantly rigid if it is rigid after one(any one)of its edges is re?moved.

In our Networking?GPS algorithm，based on similarity corre?lation，we first construct the atomic redundantly rigid graphs and then expand the local graphs to a global graph by includ?ing some anchor points.After that，the local positioning infor?mation can be transformed into global localization information.

4.2 Construction of Atomic Redundantly Rigid Graphs

Because GPS signals have significant variation against time and space diversity，it is very difficult to form a global rigid graph for localization.To mitigate the impact of time and space diversity，we have to first construct some atomic redundantly rigid graphs based on the nearby GPS signals.We take four?vertex redundantly rigid graphs as the atomic graphs(Fig.3). The procedure is shown in Algorithm 1.

In the beginning，the similarity between each pair of GPS re?ceivers in the considered grid is calculated using(2).We se?lected the top four receivers according to the sum of similarity values between these receivers.If the similarity of the each pair among the selected four GPS receivers is greater than the thresholdδ，the atomic redundantly rigid graph is found in the considered grid.

▲Figure 3.Rigidity and redundant rigidity.

There are two important implications.First，due to the set?ting of similarity thresholdδ，Algorithm 1 may find no satisfac?tory results for the considered grid.In the performance evalua? tion part，we will discuss the impact of thresholdδto the local?ization accuracy.The other implication is that there may exist more than one atomic redundantly rigid graph in one consid?ered grid and Algorithm 1 only picks one from the existing re?dundantly rigid graphs.

Algorithm 1Construction of atomic redundantly rigid graphs

4.3 Expansion Algorithm of Redundantly Rigidity

After forming atomic redundantly rigid graphs，we can only obtain accurate relative positioning information between sub?sets of the GPS receivers.To map the relative information to global information，we need to expand the atomic redundantly rigid graphs to a larger area to cover some anchor nodes，such as fixed nodes or moving nodes with high localization accuracy.

Before presenting the detailed expansion algorithm，we intro?duce the following theorem[8]，which shows the relationship between redundantly rigid graphs.From another perspective，it also provides an efficient method to do rigidity expansion.

Theorem 1:Let G1=(V1,E1)and G2=(V2,E2)be two re?dundantly rigid graphs with|V1∩V2|>=2.Then，|G1U G2|is redundantly rigid.

Our expansion algorithm is a vertex?based solution that de? termines whether one vertex can be merged into a redundantly rigid graph.If the merged graph is still redundantly rigid，we select the redundantly rigid graph with the maximum cardinali?ty and merge the vertex into the graph.If there is no merged graph that can merge the vertex to a larger redundantly rigid graph，then we define a weight function RW(.)，as shown in(3) to characterize the similarity between the vertex and other re?dundantly rigid graphs.According to the RW values，we can merge those vertexes to weighted redundantly rigid graphs.

The entire algorithm is shown in Algorithm 2.In steps 1 to 4，vertexes are merged into larger existing redundantly rigid graphs.The merging process between redundantly rigid graphs is shown in steps 5 to 11.The weighted redundantly rigid graphs are constructed in steps 12 to 15.

Algorithm 2 Expansion algorithm of redundantly rigidity

5 Performance Evaluation

We evaluate the performance of the Networking?GPS ap?

proach using real GPS samples.In our experiments，we first collected all the GPS raw data from the receivers and then es?tablished a simulation environment for the offline evaluation.

5.1 Raw Data Collection

We still used the two kinds of GPS receivers，as mentioned in section 3，with two different GPS chips.To facilitate data collection in vehicles，we built a small GPS collection box by packaging four functional elements:the GPS receiver，portable power bank，data processing unit and data storage unit.The da?ta processing unit is responsible for receiving the GPS data and converting the raw data into a human?friendly format.

In our experiment，we adopted a small portable router TP?Link TL?WR703N as the data processing unit.TL?WR703N is a low cost 3G travel router and is very popular in developer community due to its open source from hardware to software. We flashed a compatible OpenWrt firmware to the router，which is an open source third?party router firmware system and compiled the necessary USB drivers and software package for the hardware.In our implementation，we utilized the TL?WR703N as the controller to receive and process the GPS raw data，and then forward it to the data storage unit.The key com?ponents of a GPS collection box are shown in Fig.4a.

We mounted our small GPS collection boxes on the top of ve?hicles and recorded the raw GPS trace along the routes.At the end of the experiments，we exported all the data from the stor?age units.In addition，we obtained the ground truth of the lo?calization information;we collected the latitude and longitude values of ten waypoints along the route，as shown in Fig.4b，and the waypoints are numbered from 1 to 10.

5.2 Simulation Results

We ran offline simulations and processed GPS data traces from collection boxes.For ease of comparison，we only consid?ered the GPS data collected around the ten waypoints in Fig. 4b.The accuracy comparison between direct measurements and our proposed Networking?GPS algorithm is shown in Fig. 5a.The blue bar represents the direct measurements from GPS receivers.The other two represent two different simulation re?sults by choosing different threshold δ.The accuracy in terms of direct measurements is reduced because of the multipath ef? fect，and the variations are also great.For example，at waypoint 3，the average localization error is nearly 15 m，and the varia?tion is about 20 m.Networking?GPS provides the high accura?cy and the localization information is much more stable than di?rect measurements.

▲Figure 4.Scenario settings.

In our Networking?GPS algorithm，we have a similarity threshold parameter δ that is involved in both Algorithm 1 and Algorithm 2.To indentify the impact of this parameter，we chose four waypoints to consider:1，3，6，8.Around those way?points，we executed Networking?GPS algorithms under differ?ent thresholds δ，from 0.6 to 0.9 with step size of 0.3.The re?sults are shown in Fig.5b.We found that accuracy at different waypoints may present different trends.Therefore，the thresh?old δ should be adjusted along the entire route to achieve the best accuracy.

▲Figure 5.Simulation evaluation.

6 Conclusion

In this paper，we have developed Networking?GPS，a new co?operative vehicle localization algorithm，that uses commodity GPS in urban area.First，we showed that multipath effect se?verely degrades localization performance of GPS receivers. Then，we identified the correlation between the similarity of

SNR values from different GPS satellites and relative distance between different GPS receivers.Based on the observation，we designed the Networking?GPS algorithm.Our evaluation based on real GPS traces shows that Networking?GPS is highly accu?rate despite the multipath effect.In our future work，we will in?vestigate the distributed version of Networking?GPS and opti?mal parameter adjustment algorithm.

[1]H.Zhu，Y.Zhu，M.Li，and L.Ni，“Hero:Online real?time vehicle tracking in shanghai，”in INFOCOM 2008,The 27th Conference on Computer Communica?tions，Phoenix，AZ，2008，pp.942-950.doi:10.1109/INFOCOM.2008.147.

[2]N.Agarwal，J.Basch，P.Beckmann，P.Bharti，S.Bloebaum，S.Casadei，A. Chou，P.Enge，W.Fong，N.Hathi et al.，“Algorithms for gps operation indoors and downtown，”GPS solutions，vol.6，no.3，pp.149-160，2002.doi:10.1007/s 10291?002?0028?0.

[3]A.Bilich and K.M.Larson，“Mapping the gps multipath environment using the signal?to?noise ratio(snr)，”Radio Science，vol.42，no.6，2007.doi:10.1029/ 2007RS003652.

[4]A.Bilich，K.M.Larson，and P.Axelrad，“Observations of signal?to?noise ratios (snr)at geodetic gps site casa:Implications for phase multipath，”in Proceedings of the Centre for European Geodynamics and Seismology，vol.23，pp.77-83，2004.

[5]W.Sun and M.G.Amin，“Maximum signal?to?noise ratio gps anti?jam receiver with subspace tracking，”in Acoustics,Speech,and Signal Processing,2005.Pro?ceedings.(ICASSP’05).IEEE International Conference on(vol.4)，Philadelphia，PA，2005，pp.iv-1085.doi:10.1109/ICASSP.2005.1416201.

[6]J.Stone and M.Chansarkar，“Anti?multipath triangulation(amt)for positioning in dense urban environments，”inProceedings of the 17th International Techni?cal Meeting of the Satellite Division of The Institute of Navigation(ION GNSS 2004)，Long Beach，CA，2004，pp.1165-1168.

[7]A.Franchi and P.R.Giordano，“Decentralized control of parallel rigid forma?tions with direction constraints and bearing measurements.”in CDC，T Okada，HL Tang，2012，pp.5310-5317.

[8]Z.Yang，L.Jian，C.Wu，and Y.Liu，“Beyond triangle inequality:Sifting noisy and outlier distance measurements for localization，”ACM Transactions on Sen?sor Networks(TOSN)，vol.9，no.2，p.26，2013.doi:10.1145/2422966.2422983.

Manuscript received:February 21，2014

Biograpphhiieess

Chisheng Zhang(cscszhang@comp.polyu.edu.hk)is currently a PhD candidate of the Department of Computing in the Hong Kong Polytechnic University.He re?ceived his B.Sc.and M.Sc.degree in 2005 and 2008 respectively in pattern recogni?tion and intelligent system from Northwestern Polytechnical University in Xi’an，Shaanxi.His research interests include multi?hop wireless networks，vehicular com?munication systems and cooperative communications.

Jiannong Cao(csjcao@comp.polyu.edu.hk)is currently a chair professor and head of the Department of Computing at Hong Kong Polytechnic University.He received his BSc degree in computer science from Nanjing University，China，in 1982.He re?ceived his MSc and PhD degrees in computer science from Washington State Uni?versity in1986 and 1990.His research interests include parallel and distributed computing，computer networks，mobile and pervasive computing，fault tolerance，and middleware.He has co?authored four books，co?edited nine books，and pub?lished more than 300 technical papers in major international journals and confer?ence proceedings.He has directed and participated in numerous research and devel?opment projects and，as a principal investigator，obtained more than HK$25million in grants.He is the chair of Technical Committee on Distributed Computing，IEEE Computer Society;a senior member of IEEE;a member of ACM;and a senior mem?ber of China Computer Federation.He has been an associate editor and member of editorial boards of many international journals.He has been the chair and a member of organizing/program committees for many international conferences.

Gang Yao(csgyao@comp.polyu.edu.hk)is currently is currently a PhD candidate in the Department of Computing，Hong Kong Polytechnic University.He received his BSc degree in computer science from Wuhan University，China.His research inter?ests include seamless communication and mobility management，mobile computing，wireless networks and security.

ZTE Achieves Second Place in World Intellectual Property Organization Patent Table

March 18，2014—ZTE Corporation achieved second place in the World Intellectual Property Organization’s annual ta?ble of patent applicants，strengthening the company’s position as one of the world’s leading technology innovators.

With 2309 filings under the Patent Cooperation Treaty(PCT)，ZTE was second only to Panasonic.In 2011 and 2012，ZTE ranked number one.

“ZTE’s growing portfolio of intellectual property assets is providing strong support to the company’s development of new technologies，”said Guo Xiaoming，chief legal officer at ZTE.“PCT patents are the most valuable IP assets of a compa?ny.ZTE is committing tremendous resources to patent applications，as the company seeks to play a leading role in the glob?al technology industry by shaping the development of essential underlying technologies.”

According to WIPO，the number of patent applications exceeded 200，000 globally for the first time in 2013.China was one of the top three countries making patent applications.

ZTE has now built up strong positions in the development of key technologies such as operating systems，databases，mo?bile devices，applications，security solutions and semiconductors.

ZTE has filed applications for more than 50，000 patents globally，and more than 16，000 of these have been granted.ZTE is a global leader with more than 800 essential patents on 4G LTE standardization.ZTE will continue to strengthen its port?folio of patents to attain the leading position in smart terminals，optical networking，cloud computing，big data and 4G LTE and will invest in next-generation technologies such as 5G.

(ZTE Corporation)