Bin Yang,Rui Chen,*,Bin Li,Changle Li

1 State Key Laboratory of ISN,Xidian University,Xi’an 710071,China

2 Shaanxi Key Laboratory of Integrated and Intelligent Navigation,Xi’an 710068,China

Abstract:As the basis of location-based services(LBS),positioning is one of the most essential parts in intelligent transportation systems(ITS).Although global positioning system(GPS)has been widely used in vehicle positioning,it can not achieve lane level positioning accuracy.Motivated by the mature ranging technologies such as radar and ultra-wideband(UWB),several cooperative positioning(CP)methods have been proposed to enhance the accuracy and robustness of GPS.In this paper,we proposed a twostage CP algorithm that combines multidimensional scaling(MDS)and Procrustes analysis for vehicles with GPS information.Specifically,the optimized MDS based on the scaling by majorizing a complicated function(SMACOF)algorithm is first proposed to get the relative coordinates of vehicles which can tackle measurements of different error distributions,then Procrustes analysis is carried out to transform the relative coordinates of vehicles to their absolute coordinates based on GPS information.All the computations are performed at the mobile edge computing node(MECN)for the request of ultra-reliable and low latency communications(URLLC).Simulation results validate that the proposed algorithm can greatly improve the positioning accuracy and robustness for vehicles.

Keywords:intelligent transportation systems(ITS);Internet of vehicles(IoV);multidimensional scaling(MDS);positioning;Procrustes analysis

I.INTRODUCTION

As one of the three generic services in 5G,ultrareliable and low latency communication(URLLC)[1–3]has attracted a lot of attention in the Internet of vehicles(IoV)[4,5].The development of IoV has greatly promoted the development of the intelligent transportation system(ITS)[6,7].Localization is one of the most essential parts in ITS because it is the basis for implementing a series of location-based services(LBS)such as navigation,fleet management and traffic optimization[8,9].There are a number of localization methods,among which global positioning system(GPS)is most widely used due to its global coverage,convenience and flexibility[10].Although GPS offers an attractive solution,there are two main weaknesses that restrict its applications.On the one hand,GPS is not accurate enough especially for lane level and where-in-lane level localization.For example,even an error of few decimeters can cause accidents to the vulnerable users such as pedestrians and cyclists[8].On the other hand,GPS is not robust for complex vehicle environment.As a line-of-sight(LoS)technology,GPS signal becomes very weak or highly distorted in shadow areas such as tunnels,lower layers of multi-layer bridges,streets beside high buildings and densely vegetated places[11].

Motivated by these two weaknesses,several cooperative positioning(CP)methods[12–14]have been proposed to enhance the accuracy and robustness of GPS.Ansari[12]studies the benefits of a terrestrial communications system complementing dedicated short range communication(DSRC)-based vehicle-to-vehicle(V2V)real-time relative positioning(RRP)and then considers position prediction techniques suitable for V2V RRP.Mahmoudet al.[13]propose a system that employs the cooperative technique to assist the loose integration between the inertial navigation system(INS)and the GPS system by extended Kalman filter(EKF)during partial GPS outages.Soattiet al.[14]present an implicit cooperative positioning(ICP)algorithm that exploits the V2V connectivity in an innovative manner,avoiding the use of explicit V2V measurements such as ranging.However,although these important works have made great efforts to improve the accuracy of vehicle position,there are still challenges in practical applications.In detail,frequent information exchange between vehicles will increase the time cost,which is not suitable for the time-critical positioning of highly dynamic vehicles.Although the deployment of road side unit(RSU)can improve the positioning accuracy,it also brings additional economic cost.Therefore,in this paper we propose a mobile edge computing(MEC)-based vehicle positioning scheme without deploying additional RSU.The vehicles send the measured distances to the base station(BS),and then the BS sends them to the mobile edge computing node(MECN).Assisted by MEC,the time of data transmission and computation is greatly shortened,which provides the possibility of URLLC in intelligent vehicular networks.

As shown in Figure 1,most vehicles are equipped with anti-collision radar[15,16]nowadays,which can accurately measure the distances between them and the surrounding vehicles.However,the ordinary anticollision radar can not carry out a long-distance ranging of several hundred meters.Fortunately,with the development of ultra-wideband(UWB)[17–19]technology in the field of wireless sensor network(WSN),we can use UWB technique to measure long distances that cannot be measured by radar.Although UWB has a certain penetration capability,its ranging performance will also be corrupted by non-line-of-sight(NLoS)[20].In order to reduce the error caused by NLoS,in addition to using the corresponding robust algorithm[21–23],this problem can also be solved by placing devices on the roof or increasing radio frequency(RF)power.In the harsh environment,ranging by the BS may introduce large error to the measurements,so we would not like to apply the BS ranging on the consideration of accuracy.The BS sends the measurements from vehicles to MECN for computation.At the MECN,multidimensional scaling(MDS)[24–26]is used to obtain the relative coordinates of the vehicles by reducing the dimension of the distance matrix.MDS is a dimension reduction technique that originated from mathematical psychology and has been used to obtain the geometrical representation of objects based on their similarity/dissimilarity.

Figure 1.The vehicles equipped with anti-collision radars.

However,classical MDS is suitable for the measurements with the same error distribution but can not deal with measurements with different error distributions.Considering the distances among vehicles are measured by radar and UWB,their measurements have different error distributions and the radar measurements are more accurate.We propose the optimized MDS based on scaling by majorizing a complicated function(SMACOF)algorithm[27].It is worth noting that the SMACOF algorithm has been used in the iterative MDS to solve the distance missing problem[28].In the proposed optimized MDS,we assign different weights to measurements according to their error distributions and the SMACOF algorithm is used to improve the results of MDS based on the assigned weights of measurements.After obtaining the relative coordinates of the vehicles,Procrustes analysis[29]is carried out to transform the relative coordinates of vehicles to their absolute coordinates based on GPS information.For the 2-D scenario of vehicle positioning,three vehicles with GPS information are required to perform coordinate transformation[26].However,GPS is not always available especially in the complex vehicle environment.When the GPS-available vehicles are less than three,only relative positioning can be achieved.

To summarize,the proposed vehicle positioning scheme in this paper has the following advantages:First,it does not need to deploy additonal RSU,etc.,which reduces the cost and is easier for implementation.Second,it can save the time for data transmission and computation by MEC,which is essential for time-critical intelligent vehicular networks.Third,it can greatly improve the positioning accuracy of vehicles in GPS-available scenario,and can achieve relative positioning in GPS-unavailable scenario.

The remainder of the paper is organized as follows.In Section II,the system model of collaborative positioning for vehicles is presented.In Section III,the two-stage CP algorithm is elaborated in detail.In Section IV,the analysis of computational complexity is given.In Section V,numerical simulations and results are illustrated,followed by conclusions in Section VI.

Notations:Bold lowercase letters denote column vectors and bold uppercase letters denote matrices.R represents the set of real numbers.||·||denotes the Frobenius norm,N(µ,σ2)denotes Gaussian distribution with the meanµand the standard deviationσ,(·)⊙mdenotes themth element-wise(Hadamard)power.(·)Tand(·)+denote transpose and Moore-Penrose inverse,respectively.INis theN×Nidentity matrix,1 is the vector of ones,and 0 is the zero vector.eiis a unit vector whoseith element is 1.diag(·)denotes diagonal matrix,and tr(·)denotes trace of matrix.

II.SYSTEM MODEL

Consider the scenario of cooperative positioning for vehicles as shown in Figure 2.Suppose there areNvehicles and the actual coordinate matrix of theseNvehicles is denoted bywhere xi=[ai,bi]Tis the 2-D coordinate vector of theith vehicle,i=1,2,···,N.

Figure 2.The scenario of cooperative positioning for vehicles.

Figure 3.The process of cooperative positioning for vehicles.

2.1 GPS Model

In the current vehicle environment,GPS is still the main way of positioning most vehicles.However,some vehicles are GPS-unavailable due to the blocking of GPS signal by high buildings.Supposen(n ≤N)vehicles are GPS-available ofNvehicles.The GPS error can be decomposed into the systematic error and random error,where the systematic error mainly includes satellite orbit error,satellite clock error,ionospheric delay,tropospheric delay,receiver clock error and receiver position error,and the random error mainly includes multipath effect error and receiver noise[30].The fixed,known position of the BS can provide the positional correction to GPS signal to eliminate the systematic error,which is also known as differential GPS(DGPS)[31,32].The corrective GPS coordinate matrix of thesenvehicles is denoted bywhere gliis the DGPS coordinate vector of thelith vehicle.

2.2 Range Model

In our model,all of the vehicles are equipped with anti-collision radar and UWB module for ranging and the BS only undertakes the task of communication because it has large ranging error relative to radar and UWB.The Euclidean distance matrix(EDM)of theNvehicles is denoted by1,2,···,N,wheredijis the Euclidean distance between theith vehicle and thejth vehicle,i.e.,

It is obvious that D is a square symmetric matrix withdi,j=dj,i,di,i=0,i,j=1,2,···,N.Assume every vehicle can perform ranging with other(N −1)vehicles by UWB.The distances matrix measured by UWB is denoted by,where

2.3 Communication Model

The satellites send the GPS signal to the vehicles and the BS to provide GPS coordinates.The BS broadcasts to all the vehicles within its coverage.After receiving the broadcast signal,each vehicle sends a response message to the BS to establish a communication link.Then,each vehicle sends its distance measurements and GPS coordinate to the BS.The BS assembles the received distance measurements into the estimated distance matrixand correct the GPS coordinates of the vehicles based on its known actual position.After that,the BS sends the estimated distance matrixand corrective GPS coordinate matrix G to the MECN for computation.

The two-stage CP algorithm is run at the MECN to compute the estimated positions.Specifically,the relative coordinates of the vehicles could be obtained fromby MDS.The purpose of MDS is to reduce the dimension ofto generate the relative coordinate matrix,where yiis the relative coordinate vector of theith vehicle.Then Procrustes analysis is carried out to transform the relative coordinate matrix Y to the estimated coordinate matrixbased on G.After computing the estimated coordinate matrix,the MECN sendsto the BS.Finally,the BS distributes the received estimated coordinatesto the corresponding vehicles so that every vehicle has its positions.

The process of cooperative positioning for vehicles is shown in Figure 3 and the main steps are summarized as follows.

Figure 4.The computational complexities of classical MDS and optimized MDS.

Figure 5.The localization errors of GPS,classical MDS and optimized MDS vs.α.

(1)The satellites send the GPS signal to the vehicles so that the vehicles can obtain their GPS coordinates.

(2)The satellites also send the GPS signal to the BS for correction.

(3)The BS broadcasts to all the vehicles within its coverage.

(4)Each vehicle responses to the BS to establish the communication link and then sends ranging measurements along with GPS coordinate to the BS.

(5)The BS sends the estimated distance matrixand DGPS coordinates matrix G to the MECN for computation.

(6)The MECN sends the estimated positionsto the BS.

(7)The BS distributes the estimated positionsto the corresponding vehicles.

Remark 1.For privacy reasons,each vehicle can only get its own position from the BS.In the fleet with special applications,the vehicle can also choose to dis-close its position to the surrounding members for fleet management.

III.THE TWO-STAGE CP ALGORITHM

3.1 The Optimized MDS

The proposed optimized MDS first uses the classical MDS to get the initial relative coordinates Y(0)of the vehicles,and then optimize the obtained initial relative coordinates by an iterative step based on the SMACOF algorithm.

3.1.1 The Classical MDS

To facilitate the illustration,the positive semi-definite symmetric matrixis formed as

where J is the centering matrix and is given as

After being multiplied both on the left and right by the matrix J,the row sums and the column sums ofequal zero,which is also known as the double centering operation.The EDM of Y(0)is denoted aswhereδijis the distance between the relative coordinates of theith vehicle and thejth vehicle,i.e.,

The problem can be solved by using the spectral truncation as follows.First,perform eigenvalue decomposition(EVD)ofas

where Λ=diag(λ1,λ2,···,λN),λ1≥λ2≥···≥λN,is the ordered diagonal eigenvalue matrix,and Q=[q1,q2,···,qN]is the eigenvector matrix containing the corresponding eigenvectors as columns.Second,the initial relative coordinate matrix Y(0)is estimated as

where Λ2=diag(λ1,λ2)is the diagonal matrix of the largest two eigenvalues of B and Q2=[q1,q2]consists of the first two columns of Q.

3.1.2 Optimization Based on the SMACOF Algorithm

After obtaining the initial relative coordinates,the SMACOF algorithm is carried out to optimize the relative coordinates.The optimization problem can be made more precise by defining stressσ(Y)by[27]

whereωijis the weight of the distance measurement and can be assigned as

Remark 2.The assigned weight is inversely proportional to the variance of the distance measurement,which means that the more accurate measurement will be assigned the greater weight.

It is worth noting that we useδij(Y)instead ofδijin(11)to highlight thatδij(Y)is a function of Y.The stressϕ(Y)can be decomposed as

To facilitate the derivation,we denote

It is obvious thatηdis a constant independent of Y andη2(Y)can be derived as

where Aij=(ei −ej)(ei −ej)Twhose elements equal 1 ataii,ajj,-1 ataij,aji,and 0 elsewhere.Furthermore,we define

as the weighted sum of row and column centered matrices Aij,thus we can rewrite

Similarly,we can also rewriteρ(Y)as

with

where

Then,substitute(14),(19)and(20)into(22),we thus have

It can be seen from(23)that the second part is quadratic in Y while the third part is not asf(Y)varies with Y.The SMACOF algorithm changes(23)into a quadratic function about Y by introducing the supporting point denoted by Z.Then,according to the Cauchy-Schwartz inequality,we have

The minimum can be find by

After that,we can get

wherek=1,2,···kmaxandkmaxis the maximum number of iterations.The iteration stops untilϕ(Y(k−1))−ϕ(Y(k))<ξ,whereξis the threshold to control the accuracy.When the iteration stops,Y(k)is returned as the optimized relative coordinates Y of the vehicles.

3.2 Procrustes Analysis

After obtaining the optimized relative coordinates Y,the second stage is to transform the relative coordinates of vehicles to their absolute coordinates based on GPS information.The optimized relative coordinates matrix of thenGPS-available vehicles is denoted as Yl=[yl1,yl2,···,yln],where yliis the relative coordinate of thelith vehicle.Then,Procrustes analysis is carried out to transform the optimized relative coordinates Y to the absolute coordinatesas

First,the mean values of the matrices G and Ylare removed,i.e.,

Algorithm 1.Two-stage CP algorithm.Input:D∈RN×N,G∈R2×n Output:X∈R2×N 1:procedure CP(D,G)2:τ(D)←−1 2JD⊙2J 3:Q,Λ ←decompose τ(D)such that τ(D)=QΛQT 4:Q2 ←[q1,q2],Λ2 ←diag(λ1,λ2)5:Y(0) ←Λ⊙1 2 2 QT2 6:E ←images/BZ_69_440_1358_488_1403.png i

whereµglandµylare defined as

respectively.

where Σ=diag(σ1,σ2)is the diagonal singular value matrix,U and V are 2×2 unitary matrices.

Finally,substitute(33)into(28),then we can obtain the estimated coordinates.

The procedure of our proposed two-stage CP algorithm is summarized in Algorithm 1.

IV.THE COMPUTATIONAL COMPLEXITY

In this section,we compare the computational complexities of the existing classical MDS and the proposed optimized MDS.The dominant computational complexity of classical MDS is performing EVD on the matrix,which has computational complexity of.

As for optimized MDS,the computational complexity lies in two dominant parts.One is to get the initial relative coordinates and the other is to optimize the obtained initial relative coordinates by an iterative step.For the first part,the computational complexity is the same as that of classical MDS.For the second part,the additional iterative step has time complexity ofO(N3+N3/2k)according to[34].

The computational complexities of classical MDS and optimized MDS are shown in Figure 4 intuitively.In Figure 4,it can be observed that computational complexity of classical MDS is only related toN,and it increases exponentially withN.The computational complexity of optimized MDS increases with bothNandk,and is a bit higher than that of classical MDS,which is sacrificed for better localization accuracy.

Figure 6.The localization errors of GPS,classical MDS and optimized MDS vs.σg .

V.NUMERICAL SIMULATIONS AND RESULTS

In the numerical simulations,N=30 vehicles are randomly deployed in the 200m×200m 2-D scenario.The ranging radius of radar isγ=100m.In terms of the ranging accuracy,it is reasonable to assume that the ranging error of vehicles does not exceed 0.1m based on the performance of radar,that is,3σr=0.1m.Considering possible adverse factors of signal occlusion by vehicles,the ranging error of UWB is supposed not to exceed 1m,that is,3σu=1m.The positioning errors of GPS in two dimensions obey Gaussian distribution,and the limits of the positioning errors in longitude and latitude are 3σgm,whereσgis the standard deviation of GPS.Moreover,we define the ratio of the GPS-available vehicles to the total number of the vehicles asα,i.e.,.For fully reflecting not only the average localization errors but also the upper and lower limits and the error ranges of the 50 percent probability,we useboxplotfunction as same as that being adopted in[11]to illustrate the distributions of the localization errors of the algorithms.The whiskers bound the upper and lower limits while the boxes bound the middle 50 percent.The central horizontal lines indicate the medians.In order to make the simulation results ergodic,we simulate 104times at each point and generate the positions of vehicles,ranging measurements with errors and GPS position with errors randomly in each time.

In Figure 5,we show the localization errors of the proposed optimized MDS under different ratiosα,and compare it with GPS and the classical MDS.According to[31,32],we set 3σg=1m here and the thresholdξ=1.As shown in Figure 5,both the classical MDS and the optimized MDS can improve the localization accuracy of the vehicles that rely on GPS solely,and the localization errors decrease withα.Whenαis larger than 0.2,the localization performance of the classical MDS and the optimized MDS are significantly better than that of GPS.Whenαis larger than 0.6,the localization performance changes little withα.In this case,the continuous increase of GPS does not bring more improvements to the localization performance.In addition,the performance of the optimized MDS is better than the classical MDS.

Figure 7.The localization errors of GPS,classical MDS and optimized MDS vs.k.

Then,we investigate the effects of the GPS errors on the localization errors of the classical MDS and the optimized MDS in Figure 6,in whichα=0.5,ξ=1.In general,the localization errors of the classical MDS and the optimized MDS both increase with 3σg.The average localization errors and the 50% boxes of the classical MDS and the optimized MDS are smaller than those of the GPS-only scheme.In particular,when 3σg <1m,the optimized MDS is much better than the classic MDS,and it can achieve centimeter level positioning in most cases.However,when the GPS error is large,the performance of the optimized MDS is equivalent to that of the classical MDS,which means that the additional iterative optimization step are not significant in this situation.

Furthermore,we show the effects of the number of iterations on the localization errors of the optimized MDS in Figure 7,in whichα=0.5,3σg=1m.Since a good initial value(the result of the classical MDS)is selected,it only needs three iterations to achieve good performance.In the applications that cannot afford large computational complexity,only one iteration can also be applied.

VI.CONCLUSIONS

In this paper,we propose a MEC-based cooperative positioning approach for vehicles.In the proposed scheme,all the vehicles only need to communicate with the BS,while MECN is responsible for all the computations.The proposed two-stage CP algorithm combines MDS and Procrustes analysis for vehicles with GPS information,which can improve the positioning accuracy and robustness for the vehicles relying solely on GPS.Compared with the classical MDS,the optimized MDS method improves the positioning accuracy by an additional iterative step.Simulation results validate that only few iterations can achieve good performance.Furthermore,the proposed algorithm can achieve centimeter level positioning with accurate GPS information and can achieve relative positioning in GPS-unavailable scenarios.The source code of this research is made available to public under https://github.com/yangbinxd/vehicle-positioning.git.

ACKNOWLEDGEMENT

This work was supported in part by the National Key Research and Development Program of China(2019YFB1600100),and in part by the Foundation of Shaanxi Key Laboratory of Integrated and Intelligent Navigation under Grant SKLIIN-20190103.