2. VEHICULAR NETWORK LOCALIZATION

A vehicular ad hoc network (VANET) is typically a type of wireless, mobile ad hoc network and thus any localization scheme devised for the latter can be applied. For VANETs, three main research challenges have been identified here in order to resolve the localization problem:

• • Devising a ranging technique based on received DSRC signal characteristics e.g. received signal strength, time of arrival, or Doppler frequency.

• • Developing a localization algorithm based on decentralised, sensor/information fusion theories.

• • Formulating a communication protocol for the frequency and range of inter-node communications. The communication protocol should be designed for a particular CP algorithm and ranging technique.

Within the context of DSRC, the localization system is the result of a tight coupling of the ranging technique, localization algorithm and communication protocol. High accuracy ranging with DSRC is an open research problem, and attention to this problem is beyond the scope of this paper. For further information on ranging issues, see (Alam, Balaei, & Dempster, Reference Alam, Balaei and Dempster2009).

A localization algorithm is a computational algorithm that addresses the problem formulation, robustness, estimation accuracy, coordination and computational complexity, given some measurement set and its associated quality. The common theme in VANET localization is the employment of distributed localization algorithms (due to their ad hoc nature); however, a centralized, or hierarchical (i.e. combination of centralized and distributed) algorithm that advocates vehicle to infrastructure communication or even a hybrid/modal algorithm has its own appeal for higher accuracy and greater availability (Costa, Patwari, & Alfred O. Hero, Reference Costa, Patwari, Alfred and Hero2006). According to (Blum, Eskandarian, & Hoffman, Reference Blum, Eskandarian and Hoffman2004), VANETs show frequent fragmentation, rapid topological evolution over time and short link life (e.g. less than a second for vehicles travelling in opposite directions). As such, any localization algorithm must take these factors into account since communication overhead can overwhelm the network and exhaust its channel capacity. A CP algorithm for VANETs must have the following characteristics: it must be real time and very fast; it must be adaptive with respect to the traffic conditions and/or the node density; it must be robust to inter-node connection failure; and it must also be flexible enough to accommodate the communication constraints. For conciseness, all of these issues with the exception of robustness are covered in this paper. Algorithm robustness will be discussed in a subsequent paper.

3. CP PERFORMANCE ANALYSIS VIA CRLB

The CRLB sets the minimum variance of any unbiased estimation of a random variable, and is the inverse of the Fisher Information matrix. Thus, CRLB is a means of estimating the performance of the CP technique as well as benchmarking the performance of any localization algorithm. The CRLB has been derived for Adhoc Networks in general (Savvides, Garber, Adlakha, Moses, & Srivastava, Reference Savvides, Garber, Adlakha, Moses and Srivastava2003). In this section we first derive the CRLB for the general case where there may be fixed position beacons for a static network and then expand it to mobile network localization. Consider a network with n+m nodes where n nodes have unknown or partially known (e.g. to a certain accuracy) position parameters as x={[X _iY _i]}_i=1ⁿ (for localization in a two dimensional plane) and m beacons with perfect position knowledge. Let , with a standard noise e _i,j~N(0, σ_i,j²), be the inter-node range measurements between each pair of n nodes and also between pairs of each of n and m beacons; all stacked in a column matrix δ. Obviously, δ has n×(n−1)+m×n elements. Under the normality assumption f _δ(δ|x) is a normal distribution with σ_i,j²s on its diagonal covariance matrix Σ which underlines the assumption of inter-nodes measurements independence:

(1)

The Fisher Information matrix for the position estimation vector X is as follows:

(2)

where ▽_X denotes the gradient with respect to elements of vector X. The inverse of FI in its current form gives the CRLB for the case when only the range measurements are used without the a priori information about the node locations. In VANETs we assume that all vehicles are equipped with a GPS and are able to communicate their acquired GPS information via the DSRC channel. Thus the network has no beacons (m=0). We also assume that the vehicles perform unbiased ranging by means independent from the GPS information source yet through DSRC channel with a variance of σ_DSRC². A hybrid CRLB for CP can now be introduced as:

(3)

where Σ_P is the a priori covariance matrix of X that is a diagonal matrix with σ_GPS² (about 7 metres) on the diagonal. For the two dimensional case an indicator of CP error can be obtained by Circular Error Probability (CEP):

(4)

Where trace is the sum of the diagonal elements. To evaluate the performance of the CP techniques using the hybrid CRLB for static networks, a simulation scenario was constructed in Matlab™. A variable number of nodes on a disc with a diameter of 250 m (the effective range of DSRC) were randomly allocated. The network was assumed to have no anchor nodes; instead each node had a priori information of their positions with a standard deviation of 7 m equating it to that of stand alone GPS performance. The inter-node range measurements had a variable standard deviation between 1 m and 20 m. The results were averaged over 100 simulation runs.

Figure 1 shows the variation of hybrid CRB-based CEP with respect to number of nodes and relative to inter-nodes range measurement error standard deviation. It suggests a positive effect of increasing node densities on positioning accuracy and the negative effect of increasing inter-nodes range measurement error. The figure also suggests that for smaller range errors the positive effect of node density tends to diminish. This means that the ranging error is a more important contributor to the position accuracy than the node density.

Figure 1.

Effect of node density on hybrid CRLB and best estimate positioning error and its sensitivity to inter-node range measurement error.

For mobile network localization, the motion information of the nodes and their likely routes can be used to refine the position estimates. A computational algorithm that facilitates tracking and fusion of spatial information across time is referred to as a filter. The KF and Particle Filter are two examples of such filters, each with many variants and combinations. By the filtering mechanism the position estimation at each epoch k is refined by the prediction made at time k−1 based on a specified dynamic model. Several dynamic models that facilitate the information fusion across time are discussed in (Gustafsson & Gunnarsson, Reference Gustafsson and Gunnarsson2005). These models are based on uncertainty in mobility (random walk model), uncertainty in velocity (velocity sensor model) and finally uncertainty in acceleration (random force model). In the CP algorithms developed here the velocity sensor model is considered most appropriate as velocity measurements are provided by GPS and can also be read from the vehicle's odometer with relatively high accuracy of about 1% of the actual velocity. The velocity model is:

(5)

where,

(6)

(7)

U is the velocity in X direction and V in Y. T _k is the time interval between measurements. ξ_k is a standard error with zero mean and variance of σ_Vel². Thus the hybrid CRLB for mobile networks where the velocity of nodes is available becomes:

(8)

Where P_k+1 and P_k are the hybrid CRLB matrices at instants k+1and k, T _k is the scalar elapsed time, and Σ_V is the diagonal covariance matrix of the measured average velocity of nodes between the two instants. From Equation (8) it is clear that noisier velocity measurements, thus larger σ_Vel² lead to a smaller contribution from the previous instant's position information and if it is too large filtering has no effect on the accuracy. The hybrid CRLB will be used in Section 5 to benchmark the performance of the proposed KF in the next section.

4. KALMAN FILTER SOLUTION FOR COOPERATIVE POSITIONING USING MAP MATCHING CONSTRAINTS

All in-car navigation systems use map databases from which directional information is provided to the driver (Kealy, Scott-Young, & Collier, Reference Kealy, Scott-Young and Collier2004). These databases possess intelligent information that can either be incorporated as constraints to the KF solution or integrated directly as measurements within the filter (Kealy et al., Reference Kealy, Scott-Young and Collier2004). MM algorithms themselves commonly fall into two categories, termed geometric and topological (Kealy et al., Reference Kealy, Scott-Young and Collier2004). Some MM algorithms use geometric techniques alone (Bétaille & Bonnifait, Reference Bétaille and Bonnifait2000; Taylor, Blewitt, Steup, Corbett, & Car, Reference Taylor, Blewitt, Steup, Corbett and Car2001), while others combine them with topological algorithms (Bernstein & Kornhauser, Reference Bernstein and Kornhauser1996; Greenfeld, Reference Greenfeld2002). In this paper we have used two rules modelled on simple geometric MM techniques.

The first rule makes the assumption that the vehicle is travelling on a road (which is typically the case). This simple constraint can be included in the location solution, immediately improving the accuracy of the computed position of the vehicle. In the next sub-section we apply this rule to the KF solution. The simple algorithm is effective when the nearest road/lane to the estimated position (from GPS or other sources) is in fact the road being travelled. However, when approaching intersections or when two roads are close to each other, the nearest road may not be the road being travelled. In these situations, searching for the nearest road can downgrade the position solution. To overcome this problem, a second MM rule applied in parallel takes into account the direction of the road the vehicle is travelling on. This second rule requires that the nearest road to which the vehicle's position is corrected (using the first MM rule) must have a similar bearing to the direction of travel that is available from GPS. This corrects the problems previously described.

Incorporating these MM algorithms into the KF requires the development of observation equations from the MM rules. The MM observation equations are derived from (Kealy & Scott-Young, Reference Kealy and Scott-Young2005):

• • Rule 1: An estimate of the vehicle's ‘corrected’ position (which lies on a road segment), and

• • Rule 2: An estimate of the vehicle's heading (i.e. the heading of the road segment at the ‘corrected’ position estimated by Rule 1).

These rules have never been applied to network positioning before. The nearest road/lane rule introduces ambiguities particularly at intersections. To resolve these ambiguities, additional parameters can be introduced in the MM algorithm such as search radius, inner intersection exclusion radius, and angular similarity (Kealy et al., Reference Kealy, Scott-Young and Collier2004). We don't elaborate on these details here, however it is worth mentioning that the DSRC information exchange can help resolve these ambiguities even better than before, and we will address these issues in future work.

As stated before, CP is based on position, velocity, and inter-node range matrix information exchange between nodes/vehicles that are in the same cluster, thus within each other's reach. So each vehicle broadcasts the information to its neighbours which are determined by DSRC range. Consider node i in a cluster with n neighbours including itself at time k. The aim is to estimate the self-position and the position of the surrounding vehicles and with an accuracy better than that of GPS. Note that the surrounding vehicles also broadcast the information about their inter-node ranges with their neighbours who are not necessarily node i's neighbours. So node i would also be the recipient of not-its-own-neighbours information. This information which cannot be incorporated in the CP algorithm is discarded.

4.1. Forming the Kalman Equations

KF is an optimal state estimation process applied to a stochastic dynamic system (Chui & Chen, Reference Chui and Chen1987). The KF is a linear, unbiased, and minimum error variance recursive estimation algorithm for the state of a dynamic system that uses noisy measurements taken at discrete real-time intervals (Chui & Chen, Reference Chui and Chen1987). The general formulation for a KF is as follows. Assume a discrete time dependent system with recursive linear model:

(9)

where x_k is the system state vector at the time interval k and A_k is the linear system model. Equation (6) is the state space for network position estimation of the linear system model that was presented in equation (5). The A matrix here is the identity matrix. The process noise ξ_k is zero mean Guassian error with the covariance of:

(10)

σ_Xvel² is the covariance of each of the n nodes' velocity in X direction and σ_Yvel² is the same in Y direction. Apart from velocity as a control parameter no other effective noise can be considered as the system or process noise. The assumption that vehicles move in a two dimensional plane is limiting because, for example, if two vehicles are on a hill then their distance is larger than the map of their distance in the two dimensional horizontal plane. Thus for real world application the state space must contain three dimensional coordinates.

Similar to GPS-INS (Inertial Navigation System) integration by KF, which has two general approaches, CP KF can also be tackled in two different ways. First, the state vector can be regarded as the position(s) of the targets/objects. The second is to have the state vector as the error of the GPS position measurements. The latter is generally a more accepted, and robust method of estimation, especially when the attitude of the object is also estimated (Kealy & Scott-Young, Reference Kealy and Scott-Young2005). Error estimation also leads to more severe state-space nonlinearity, and it is more difficult to implement. Here, we have defined the state vector as the positions rather than the estimated position errors.

A linear relationship between the state vector and a set of measurements v_k with noise sequence described with η_k is necessary for KF:

(11)

where C_k is known as the measurement model. The measurement vector for CP is:

(12)

Where, x _GPS^k is a 1×2n vector containing GPS position estimations at X and Y directions. Note that in reality X and Y are reflected in northing and easting. D _DSRC^k is a 1×n(n−1)/2 vector containing all the range measurements between all the n nodes that are in the neighbourhood of node i. h _map^k, 1×n vector, is the heading of each of n nodes. The covariance matrix of measurement vectors is:

(13)

Where σ_GPS is GPS position error standard deviation at one direction, σ_DSRC is the ranging standard deviation, and ε is a very small number representing the error in heading measurement, which in reality is highly accurate. The following equations are used to describe the relationship between the measurement matrix and state vector:

(14)

(15)

In general when:

(16)

and g_k is nonlinear, through first order linear Taylor expansion approximates, the nonlinear state and measurement equations can be turned into linear forms. From here the matrix C_k can be obtained by calculating the gradient of g_k(x _k) with respect to x _k. Because of the first order expansion assumption, severe state-space non-linearity limits the reliability of extend KF estimations. For severely non-linear systems Particle Filters are used that have the downside of high computational cost. Under the assumption of independency for ξ_k and η_k the Kalman solution is:

(17)

(18)

(19)

Where is the estimated state, P _k|k is the estimated covariance of the state and A _k=I _2n×2n, Γ_k=I _2n×2n. Also note that:

(20)

Equation (17) is known as the prediction equations where the state and its covariance are predicted. In Equation (18) G _k, known as the Kalman gain, is calculated and in (21) the state and covariance are updated by the new measurements.

4.2. Covariance Adjustment

The first rule of MM is applied to the output of KF, . All the KF solutions are compared with the digital map and matched to the nearest road. The effect of snapping to road centre-line will result in a change in the estimated state covariance matrix . If there is only one lane on the road, implementing this rule results in the covariance of each node's estimated position along the axis vertical to the road being effectively very close to zero. When this statement is translated in X and Y directions we have:

(21)

Where are the estimated deviations for each node in the KF, α^k is the angle of the road relative to X direction at the instance k, and are the adjusted deviations. The adjustment is important since is to be used for KF estimation at the k+1 instant, and will lead to unbiased estimation. The off-diagonal entries of can also be adjusted in a similar manner using the two angles for each pair of nodes.

4.3. Implementation of CP Algorithm in DSRC

A typical CP module block diagram is shown in Figure 2. Information exchanges between modules are clearly demonstrated. A simple explanation of the proposed CP procedure is as follows. All the position estimates either received from GPS (self position) or DSRC (others' positions) are sent to the digital map unit for heading calculations. Heading transmission can also be included in the broadcast information which eliminates the need for the latter, although it increases the communication overhead. Power consumption and thus (to some extent) computational capacity are not major problems for vehicular navigation. However, communication overhead in a shared bandwidth of VANETs is a serious constraint, so the trade-off which is repeated several times in this paper should optimize for lower communication usage. In any case the output of the KF will be sent again to the digital map unit for snap-on-the–centreline adjustment. In effect MM rule 2 is implemented prior to rule 1.

Figure 2.

A cooperative positioning module, consisting of positioning device (GPS unit) communication and ranging device (DSRC), computational processor (KF processing unit) and digital map.

To initialize the CP process each node starts with estimating the inter-node ranges in the DSRC board by one of the methods described in section I; note that all these ranging methods require listening to the neighbours' regular DSRC messages. Thus initialization starts with listening to the constant stream of DSRC messages from other vehicles in the neighbourhood. The regular messages are set to be broadcast at 10 Hz frequency (see (Efatmaneshnik, Balaei, & Dempster, Reference Efatmaneshnik, Balaei and Dempster2009) and the references therein). However, positioning cannot be performed at this rate with the present algorithm, simply because at this rate the GPS position estimation is extremely erroneous, with a CEP much higher than 10 m. We assume performing CP at 1 Hz.

The inter-node ranges and a vehicle's own GPS reading are broadcast at the desired frequency. Note that this frequency can be even lower than 1 Hz. This way the CP solutions can be used to reduce the GPS solution bias which is acquired at a higher rate (1 Hz.). The advantage of lower rate CP is lower communication overheads. (see (Efatmaneshnik et al., Reference Efatmaneshnik, Balaei and Dempster2009)). Simultaneous to sending inter-node ranges, each node receives the measured inter-node ranges from the entire neighbourhood, which enables each node to form the measurement vector in the KF unit. Then the state vector, matrix A₀, matrix C₀, R₀ and Q₀ are formed. Inside the KF unit two stages of predicting the state and updating the state are continually performed. Obviously, the estimated state need not be broadcast in its entirety, and only the estimated self position will be sent to the DSRC board. However the entire estimated state needs to be sent to the safety applications unit (after passing through the snap-to-centreline MM algorithm), because these applications need to know the position of other nearby vehicles. In the iteration procedure the KF regularly updates the measurement and state vectors, and matrices A_k, C_k, R_k and Q_k.

After initialization, the KF never stops unless there are no nodes in the neighbourhood. During the KF processing if a node becomes invisible by going out of DSRC range, then the rank of the state and all the associated matrices will reduce. On the other hand if a node joins the cluster of nodes then the rank of the state and all the associated matrices will increase. The important point is the position uncertainty of the recently joined vehicle(s). There are two options here: either the communication protocols are set to transmit the self position uncertainty (estimated by KF); or the position covariance of the recently joined vehicles can be set as the GPS position uncertainty. The latter is less accurate positioning, but saves some of the extra communication costs by lowering the packet size. Although this cost saving might be negligible.

5. SIMULATION AND RESULTS

A simulation study was set up to demonstrate the performance of the KF. The traffic was simulated by Netlogo™ which is an agent based and Java based programming platform. Figure 3 is a snapshot of the traffic network. The length of the horizontal road is approximately 1 km. From this simulation, ground truth values of the vehicles' positions were obtained and the rest of the calculations were performed in the Matlab™ environment. The traffic rate was set at 1200 vehicles/hour representing moderate traffic conditions in a city urban area. The simulations run for about 220 seconds. The ranging standard deviation was set at 3 m and that of GPS (in terms of CEP) was 10 m. The simulation was repeated 500 times. The following metric was used as the overall estimation error:

(22)

Where and are respectively the estimated and true position vectors of given node i, k is the epoch number and s is the number of simulation runs.

Figure 3.

Netlogo simulation environment was used for the traffic simulation.

By using the performance metric of Equation (22), in Figure 4, the performances of KF1, KF2 and KF 3 are compared along with the hybrid CRLB in Equation (8). Figure 4 shows the performance of the KF without any of the MM rules (KF1), the KF with only the first MM rule (KF2), snap-to-the-centreline, and the KF with both MM rules (KF3). KF1 performs just above the hybrid CRLB, yet very close to it. This shows the superior performance of KF for CP. Figure 5 shows the number of neighbouring vehicles to the node i at different epochs. Considering Figures 4 and 5 together one can see that as the number of neighbours increase the error decreases. The performance of KF2 and KF3 are well below the hybrid CRLB, because the MM rules add more information to the estimation process, improving the accuracy of the final estimation so that it is consequently much better than the hybrid CRLB in Equation (8).

Figure 4.

The performance of three KF compared to the hybrid CRLB.

Figure 5.

The number of neighbouring vehicles to node i at each epoch.

Another simulation experiment was set up to demonstrate the effect of traffic condition on the performance of KF1, KF2 and KF3. The road map and the directions are shown in Figure 6. The simulation was performed in Matlab™ environment. The vehicles were deemed to move in the marked three streets in a circular manner, in both directions and could not change lane or direction. There was only one lane at each direction. The traffic rate varied between a minimum of 200 vehicle/h, leading to 10 vehicles circulating the area, and a maximum of 1200 vehicle/h, which leads to 60 vehicles circulating in the marked roads. The simulation was performed for six different traffic rates. The vehicles had a maximum velocity of 60 km/h and a minimum of 40 km/h. The DSRC range was set at 250 m, which is typical. Given this range as shown in Figure 7 the previously mentioned number of vehicles in the system (of roads) leads to each vehicle, on average, having 5 to 30 neighbours. Using the average number of neighbours will effectively make the presented result independent of the DSRC range. The simulations run for 100 seconds. The ranging standard deviation was this time set at 6 m and that of GPS (in terms of CEP) was 10 m. The following metric was used as the overall estimation error:

(23)

Where x ^k and are respectively the estimated and true position vectors of all nodes, n is the total number of nodes in the system, and K is the total number of instances.

Figure 6.

The road map on which the simulation tests was performed. The part of W10 Mile Rd that was used is roughly 900 m long.

Figure 7.

The simulation result shows that KF with both MM rules have better performance than KF with second MM rule only and KF without MM.

6. COMPUTATIONAL COST AND COMMUNICATION OVERHEADS

The computational complexity of the presented KF algorithm at each epoch is O(n) where n is the number of neighbours in the cluster of each node. This is so since the algorithm is not based on iterative improvements. This algorithm is real time and has the ability to respond quickly in the dynamic vehicular environment.

In order to analyse the communication overheads of the CP algorithm, the specific communication protocol must be considered. Location Based Broadcast or Geocast protocols are the most common VANETs communication protocols by which the sender broadcasts messages to all receivers in its communication range. The Geocast protocol for CP is a one-hop communication such as follows with the following requirements (Efatmaneshnik et al., Reference Efatmaneshnik, Balaei and Dempster2009):

1. 1. Communication from vehicle to vehicle

2. 2. Point-to-multipoint communication

3. 3. Allowable latency: 20–200 msec

4. 4. Frequency (update rate): 1–10 Hz

5. 5. Regularity: constant

6. 6. Data to be transmitted and/or received: position, velocity

7. 7. Estimated Packet Size: 200 bits

8. 8. Range of communication: 250 m

The CP protocol requires regular transmission at a certain frequency which is contrary to the safety based vehicular communication that is event based as well as regular. Because of the real-time characteristic of CP in a mobile environment, if the delay in transmission is longer than a threshold (e.g. 0·1 ms) the packet should be discarded at the source. This protocol does not require Unicast.

Using NS-2 software that is widely used to simulate IEEE 802.11 networks (Chen, Jiang, Taliwal, & Delgrossi, Reference Chen, Jiang, Taliwal and Delgrossi2006), the performance of the above protocol was analysed. Figure 8 shows the results first reported in (Efatmaneshnik et al., Reference Efatmaneshnik, Balaei and Dempster2009). The percentage of dropped packets is exactly the failure rate in reception of the packets at a receiving node. The negative amounts indicate that there has been delay in packet delivery; however we ignore the delay for this preliminary analysis. The network topology for this simulation consisted of a single receiving node at the centre and its neighbours (transmitters) located on the periphery of a circle with radius 250 m. The update frequency was 1 Hz.The figure shows that the packet lost starts at when the number of neighbouring vehicles is above 23 and for numbers less than that there are no packet lost.

Figure 8.

Packet reception failure of CP communication protocol, simulated by NS-2 network traffic simulator. Blue dots are the simulation outcome and the red line is a piecewise linear model fitted to the data.

The simulation with Netlogo shows in heavy congested traffic in urban areas (1000 vehicles per hour) the average number of vehicles in the neighbourhood, conditional to the 250 m effective range of DSRC, vary in between 20 to 28 vehicles. This makes the packet loss an almost irrelevant issue for the moderate traffic conditions.