Acknowledgement based localization method (ALM) to improve the positioning in vehicular ad hoc networks

Published Online November 2018 in MECS

The Vehicular Ad hoc Network is a collection of vehicles which forms a temporary dynamic network topology. Intelligent Transportation System (ITS) plays a major role in vehicular networks to reduce risks in a dangerous or high accident prone area and traffic congestion by controlling travel speeds and traffic flow thereby increasing public safety [1] [2]. The vehicular communication network or VANET is used to increase the performance of safety applications like driving assistance, road traffic information or emergency braking alert etc. [3] [4]. The communication between the vehicles is necessary for vehicular safety and non-safety applications. But before communication, there is a need to find the vehicle's position like where it is located. In the case of dynamic ad hoc network, finding the exact vehicle’s position is a challenging issue.

Location estimation of the vehicles in VANET is a challenging issue today due to the vehicles varying moving speed. There are many techniques to make the positioning system more attractive in this network. The positioning systems are used to increase the public safety services such as Roadside Assistance, Traffic Routing and Real Time Vehicle Scheduling. The real-time position applications are used to track personnel services by Police Officers, Rescue Teams, Fire Brigades, Lost Children, Suspected Criminals, and Stolen Vehicles [5].

Basically VANET localization methods are of two types, namely distributed and centralized methods. In centralized method the computation occurs in the specific central vehicle or the vehicle outside the network. Hence this method suffers from many collisions and contention during communication. In distributed algorithm, each vehicle splits up its task into several ways. For example, each vehicle is responsible only for finding its own coordinates, or computes the locations within its vicinity and shares the message. Proximity, Distance, Time of Arrival (ToA), Time-Difference-of-Arrival (TDoA), Angle of Arrival (AoA) and Received Signal Strength Indication (RSSI) are the most important types of information or measurements used by the localization algorithms to find their neighbors location. For instance, in the RSS method the Received Signal Strength is used as an indicator to determine the distance between vehicles where the RSS could be modeled as a path-loss equation defined in [6] .

The localization algorithm uses two types of messages such as anchor messages and beacon messages to know their neighbor vehicle's position. The anchors messages are sent by dedicated devices called anchors which will periodically transmit signals to the neighbors [7]. It needs infrastructure support through the sensors like GPS and RSU other than from vehicles. The beacon messages are periodically sent by all the vehicles to their neighbors through OBU.

The positioning technique provides an accurate knowledge of the vehicle’s location, which allows the vehicle to find its location in real time continuously [8]. There are several positioning techniques available in the existing literature, but the limitations of many of these techniques provide infeasible results. In real life scenarios, a good positioning technique should provide Accurate, Reliable, Scalable, Lightweight and Inexpensive results. But the existing techniques have not satisfied all the above mentioned requirements [9]. Due to this factor there is a need to propose a new technique to overcome the issues in the existing techniques.

The rest of the paper is organized as follows: Section II of this paper gives the brief details about the localization techniques used in the existing research work. The proposed localization technique is shown in section III. Section IV shows the experimental analysis of RSSI, TOA, DLM and the proposed Acknowledgement based Localization Method (ALM) and section V shows the discussion about the experimental analysis of all the algorithms considered in this paper. Finally, section VI concludes the paper with the future enhancements.

• II.    Related Work

This section discusses about the different localization techniques used by the researchers to find out the exact position or location of the vehicles in vehicular communication. The authors in [10] discuss the following different localization techniques used in VANETs. They are:

• •    Global Positioning System (GPS)

• •    Map Matching

• •    Dead Reckoning

• •    Cellular Localization

• •    Image Video Processing

• •    Localization Services

• •    Ad Hoc Localization

• A.    Localization Techniques

GPS is one of the most common positioning technique for the vehicular ad hoc networks to trace the actual position of the vehicles in real time scenarios [11] [12] [13] . It uses a collection of 24 satellites, four of which monitors the earth region. The satellite is around 20,200 km from earth and completes two orbits every day [14]. GPS also known as ranging system is used to know the positions of the satellite in the space to unknown positions on the land, sea, in air and space [15]. However the target position and distance will be changed rapidly over time and distance due to the dynamic nature of the vehicles. Also other problems like multipath shadowing, sensor imperfections and changes in the propagation properties of the physical layer may cause an incorrect positioning of the vehicles in GPS. An enhanced GPS called as the Differential GPS (DGPS) consisting of expensive ground stations has been devised to improve the accuracy significantly. However, GPS and DGPS are similar techniques and do not work in tunnels, undergrounds, and in dense building areas, because the signal cannot be received or very poor in these areas.

Map Matching (MM) is a method of aligning a sequence of observed vehicle positions with the road network on a digital map. This method is applied to applications such as traffic flow analysis, driving directions and object management. Its goal is to overcome the error of the estimated vehicle position received through GPS [16] [17]. As this technique uses the information from the GPS to estimate the position of the vehicles, it fails to find the exact position of the vehicles [18].

Dead Reckoning (DR) computes the current position of the vehicles based on the vehicle's last identified location through the movement information like distance, time, speed, direction, etc [19]. This can be acquired through GPS receivers or by locating a known reference on a digital map. It is used only for a short time period when the GPS signal is weak or unavailable, but DR accumulates more errors easily over time and distance. Hence DR is only used as a backup method when a GPS is not working in tunnels, etc. For example, when a vehicle is traveling at 100 km/h, a positioning error of between 10m to 20m can occur just 30 seconds after the last position fix. This technique is suitable in highway environments for the vehicle movement can be easily predicted in highways and the speed of vehicles is also stable [20].

Cellular Localization (CL) is based on the cellular infrastructure to find the positions of the vehicles in the urban areas. This technique needs base stations to cover the area and uses different parameters like Signal Strength, Angle and Time of release signal. But CL provides less accuracy due to the changes in the base stations position, the number of base stations used and the localization error between 90m to 250m [21] [22].

Image Video Processing (IVP) uses the video and image sources for localization purpose to work in parking lots and tunnels in which cameras are already installed for security issues. This approach is based on data fusion protocols to analyze and track the vehicle's location [23]. The video and image sources can compute the vehicle's location parameters such as the road's lateral curvature, lane width, and distance of vehicles from lanes, angle of direction, and camera inclination angle as in vision algorithms [24] [25]. This technique does not have synchronization and availability features in localization.

A Localization Service can be implemented using any known infrastructure localization system such as the Cricket Location-Support System, RADAR,Ultra-Wideband Localization, or WiFi Localization.

Ad Hoc Localization uses the local relative position information to estimate the distance between vehicles. Beacon messages are used to share the position information among the neighboring vehicles in this technique. With this information, vehicles can locate their neighbors’ positions. This type of localization is mostly used in sensor and ad hoc networks [26]. Fig. 1 shows the different localization methods used in Vehicular Ad Hoc Networks.

Fig.1. Localization Methods in Vehicular Ad Hoc Networks

• B.    Measurement Technique

All the above mentioned localization methods uses the following measurement techniques. They are classified into the following categories, namely [27]:

• •    Received Signal Strength Indication (RSSI)

• •    Time of Arrival (TOA)

• •    Time Difference of Arrival (TDOA)

• •    Angle of Arrival (AOA)

• •    Distance based method (GPS)

The above said techniques are the most common radio location methods since these methods use only signal measurements to determine the path direction and radio frequency range to find the distance of the neighboring vehicles [28].

This paper considers the three basic measurement techniques such as RSSI, TOA and DLM for the evaluation purpose. The ranging method like RSSI and distance based method like DLM are not accurate and are not suitable for different traffic scenarios since the vehicle movement, direction and path may change dynamically.

The Received Signal Strength Indication (RSSI) [30] [31] is a type of localization technique used to estimate the distance between the neighbors. But this method provides inaccurate measurements and produces errors up to 50% of the measured distance [32]. This technique finds its neighbor through the transmit power and the receiving power of the vehicle within its transmission range. The high signal strength indicates a shorter distance from the source vehicle.

Time of Arrival (TOA) [33] [34] is the time that the radio signal spends from a transmitter to a receiver. Based on the frequency and the speed of the radio signal, the distance between the transmitter and the receiver can be calculated. Besides GPS, many radiolocation systems are based on TOA. The TOA technique uses the absolute time of the signal propagation to measure the distance from a specified base station to the active station. With the two different distances and the location of two base stations, the probable location of the active station can be found at the intersection of two circles, where the center of each circle is the station location and the radius is the distance from it.

Distance based Localization Method (DLM) follows the GPS system to estimate the distance between the neighboring vehicles. The GPS signal will not provide the accurate position information in tunnels and shadowing areas. Hence, these three localization techniques provide incorrect position information, thus reducing the localization accuracy and increasing the localization error.

Due to the limitations in the above mentioned measurement techniques, this paper aims to propose a new Acknowledgement based Localization Method (ALM). The objective of this paper is to improve the accuracy level and to reduce the localization error due to the vehicle’s misdetection factor. In vehicular communication, the vehicles need to share the position information with their neighbors to broadcast Emergency Safety Messages. Among the several localization methods, the most widely used technique is GPS. But it is not cost effective and also not suitable for all types of scenarios like tunnels or bad weather conditions. Hence, the GPS system provides incorrect or false position information at the time of safety or non-safety communications. But the vehicular safety application needs a correct localization technique to find the exact neighbors position information.

Table 1 shows the shortcomings of the major localization techniques used in vehicular ad hoc networks that was discussed in [2]. From table-1 it is clear that none of the technique satisfies all the above mentioned localization requirements. Hence there is a need for fine grained localization technique to provide services anytime and anywhere for the dynamic vehicular ad hoc networks. Compared to the other techniques it is found that ad hoc localization provides good accuracy and availability feature without any infrastructure support. The feasibility of the ad hoc localization method is discussed in most of the papers. Hence this paper chooses the ad hoc localization method [35] to be used for VANET.

• III.    Proposed Acknowledgement based Localization Method (ALM) For VANET

This section describes the proposed ad hoc localization technique named as “Acknowledgement based Localization Method” (ALM) to improve the localization accuracy and to reduce the localization error through simulation. Initially, whenever the source vehicle finds or receives any Emergency Safety Message (ESM), the source vehicle needs to find their neighbor’s position information to communicate with them.

Table 1. Comparison of Localization Techniques in VANET

S. No.	Localization Method	Infrastructure Support	Synchronization Feature	Availability Feature	Accuracy
1.	Global Positioning System (GPS)	√	√	×	×
2.	Differential Global Positioning System (DGPS)	√	√	×	√
3.	Map Matching (MM)	×	×	√	×
4.	Dead Reckoning (DR)	×	×	√	×
5.	Cellular Localization (CL)	√	√	×	×
6.	Image Video Localization (IVL)	√	×	×	√
7.	Localization Services (LS)	√	×	×	√

It is mandatory to find the exact neighbor's position to improve the accuracy level and to reduce the localization error. After finding the exact position of the neighbors, the receivers can easily capture the message for further communication.

The assumptions of this algorithm are as follows. ALM uses Vehicle-to-Vehicle (V2V) communication and position information update at the interval of 1s that was defined in 802.11p facility layer and is based on ETSI standard. All the vehicles are assumed to be equipped with On Board Unit (OBU) for V2V communication.

The objectives of ALM are as follows:

• •    To reduce the Localization Error

• •    To improve the Localization Accuracy

• A . Problem Description

The performance of the existing ad hoc localization degrades both when the node density is less as well as high. When the vehicle density is less, the vehicle has to wait for a long time to receive a beacon message. In case of high density, more beacon messages are received, which will increase the overhead and collision. In this situation there is a requirement to improve the ad hoc localization technique based on range or sector based estimates to give better performance at different vehicle densities to ensure vehicle connectivity and to improve the message reliability.

The proposed ALM algorithm uses an acknowledgement to identify the neighbor’s position. Initially, it is assumed that all the vehicles know its position information beforehand. Upon receiving the message, the source vehicle shares its position information to the neighbors by exchanging its position information and waits for an acknowledgement. After receiving an acknowledgement (ACK) message, the source vehicle calculates the distance between their neighbors using Euclidean distance calculation formula with varying velocity. The ACK message consists of Vehicle IDs, Velocity, X and Y Coordinates of the vehicles. Two types of messages are broadcast in this algorithm, namely Position Information and an Emergency Safety Message. The position information shares the neighbor’s location information and the emergency safety message is the actual safety message that needs to be sent at the time of an accident in the vehicular ad hoc networks.

The proposed algorithm improves the localization accuracy and reduces localization error through an acknowledgement message. The vehicle’s distance is easily calculated without any infrastructure support. ALM is also a simple method since it uses only position information to detect their neighbors within an acceptable time interval (0ms to 10 ms) given in [36].

Table 2. ALM Message Format

I Vehicle ID I Velocity I X-Coordinate I Y-Coordinate

Table 2 shows the message format of the proposed ALM localization method. It consists of four fields such as Vehicle ID, velocity, X and Y coordinates of the vehicles. These four fields are used to find the neighbor’s position.

The following are the notations used in the proposed algorithm:

BCST – Broadcast

ESM – Emergency Safety Message

Vs – Source vehicle that broadcast an emergency message v (i) – The Velocity of the Vehicle

X and Y – Vehicle’s Coordinates

ACK – Acknowledgement

AV – Array of Acknowledged Vehicle IDs

Table 3 shows the algorithm of the proposed ALM algorithm. The beacon messages that are normally used in VANET to update the position information, actually increases the message overhead. If beacon messages are used for sharing neighbor information, the vehicles have to wait for a minimum of one second to update the neighbor list. But in the case of Acknowledgement based Localization Method, the vehicles need not be bothered about the beacons because whenever a vehicle receives an ACK from other vehicles, it is considered to be a part of the network. The emergency message can be sent to the newly joined neighbor.

Table 3. Acknowledgement based Localization Method (ALM)

ACKNOWLEDGEMENT BASED LOCALIZATION METHOD (ALM)
Procedure Acknowledgement Based Localization Method { Initialize all the vehicles {V 1 , V 2 , … , V n }ϵ V For i= 1 to n BEGIN
V s ←BCST MSG (V id ,v,X,Y) to all V i ϵ V	// Source vehicle sends a position information through broadcast message //
IF( V i receives BCST then ACK(V id , v, X,Y)) then V s ← ACK(V i )	// Receiver vehicle transmits an ACK to the sender V s //
AV[] = ACK(V i ) For all AV [i] BEGIN	// Vs Stores the ACK vehicles ID in an array AV[] //
v(i)= [(sqrt((X i +X i+1 )^2)+ (Y i +Y i+1 )^2))] / (T i -T i+1 )	// Velocity of the vehicles //
Distance d(V s ,V i ) = sqrt[((x 2 -x 1 )^2)- ((y 2 -y 1 )^2)]*v(i)	// Distance calculation //
V i ← BCST (V id , v (i), d (i)) } If ((BCST_T>10ms) & (V i ϵ TR(V i )) then	// Broadcast the information to the newly entered vehicle //
BCST ESM END }	// Broadcast Emergency Safety Message (ESM) //

Since ALM uses ACK message to update the position information, there is no need of a beacon message since every vehicle shares position information through ACK message, which itself serves like a beacon, intimating the presence of the vehicles. Table 4 shows the qualitative analysis of RSSI, TOA, DLM and ALM

Table 4. Qualitative Analysis of RSSI, TOA, DLM

S. No.	Localization Method	Accuracy	Localization Error
1	Distance based Localization Method (DLM)	Low	High
2	Received Signal Strength Indication (RSSI)	Medium	High
3	Time of Arrival (TOA)	Low	High
4	Acknowledgement based Localization Method (ALM)	High	Low

• IV.    Performance Evaluation

This section describes the performance evaluation of the proposed Acknowledgementbased Localization Method (ALM). ALM is compared with DLM, RSSI and TOA methods.

• A.    Simulation Setup

This section shows the simulation setup and parameters considered for evaluation purposes. Table 5 shows the simulation parameters. The algorithms are analyzed using NS2 Simulator version 2.34. The proposed algorithm uses the DSRC 802.11p protocol. The length of the road is assumed to be 1Km long in four directions and Two Ray Ground Propagation model is used for MAC and PHY layer implementations. The communication type is V2V this will reduce the cost to install the external devices. All the vehicles are assumed to be installed with OBU through which the communication takes place between the vehicles.

Table 5. Simulation Parameters

Parameters	Value
Road Length	1Kms
Physical Propagation Model	Wireless
Propagation Type	Two Ray Ground
Vehicle Traffic Density	20, 40, 60, 80, 100/ Km
Vehicle Size	2m-6m
Vehicle Moving Speed	60-120 Km/h
Vehicle Mobility Model	Manhattan Mobility Model
Broadcast Packet Size	128 bytes /20 Messages
Position Update Interval	0ms -10 ms
Antenna Type	Omni Directional Antenna
Communication Type	Vehicle to Vehicle (V2V)
Traffic Direction	Bidirectional/ Multidirectional
Simulation Time	200 Seconds

• B.    Simulation Results

This section shows the simulation results with the parameter localization error. The results are analyzed for different vehicle distances ranging from 10m to 90m. These distances denote the inter vehicle distance between the vehicles on the road and the number of vehicles assumed to be 40 to 100 vehicles randomly.

Localization Error

Localization Error (LE) is defined as the difference between the original location and the computed location.

Figures 2, 3 and 4 shows the localization error for techniques considered in this paper. The Localization Error in the case of proposed algorithm is less with respect to inter-vehicle distance, vehicle speed and the transmission range of a vehicle.

Fig.2. Localization Error vs Distance

Fig.4. shows the localization errors of RSSI, TOA, DLM and ALM methods for varying transmission range. As the transmission range increases the number of vehicles in a region is also increasing blocking probability and neighbor hop count. In ALM only selected vehicles at the time of displacement shares location which provides ALM with lesser localization error.

Localization Accuracy

Localization Accuracy is defined as the measure of the degree to which the measured quantity is the same as its actual value.

Figures 5, 6 and 7 shows the localization accuracy of all the algorithms.

Fig. 2 shows the localization errors of RSSI, TOA, DLM and ALM methods for varying vehicle distance. As the distance increases, the number of vehicles also increases, which leads to interrupts in finalizing position information. The interrupt leads to increase in localization error.

Fig.3. Localization Error vs Vehicle Speed

Fig.3. shows the localization errors of RSSI, TOA, DLM and ALM methods for varying vehicle speed. Variable vehicle speeds do not support exact location due to frequent change in position. In ALM the position update is done at the time of location change which shows off less localization error.

Fig.4. Localization Error vs Transmission Range

— ♦ — RSSI

- ■ -TOA

-*— DLM

ALM

Fig.5. Localization Accuracy vs Vehicle’s Distance

Fig.5. shows the localization accuracy of RSSI, TOA, DLM and ALM methods for varying vehicle distance. As the distance increases, the number of vehicles also increases, which leads to more number of vehicles participating in finalizing the position information. This increases the accuracy level.

-•—RSSI

- ■ -TOA

-*-DLM

ALM

Fig.6. Localization Accuracy vs Vehicle Speed

Fig.6. shows the localization accuracy of RSSI, TOA, DLM and ALM methods for varying vehicle moving speed. Similar to LE, the varying vehicle speed increases the changes in position information. But in ALM the position information is updated through an ACK message, thereby increasing the accuracy.

—ф— RSSI ч> TOA -*- DLM

ALM

Fig.7. Localization Accuracy vs Transmission Range

Fig.7. shows the localization errors of RSSI, TOA, DLM and ALM methods for varying transmission range. As the transmission range increases the number of vehicles in a region is also increased, thus improving the availability of the neighbors. In ALM only selected vehicles share the location information which improves localization accuracy.

• V.    Discussion

From figures 2, 3 and 4 it is clearly seen that the proposed algorithm reduces the Localization Error compared to RSSI, TOA and DLM. Figures 5, 6 and 7 show the Localization Accuracy of all the algorithms for varying distance, speed and a transmission range of the vehicles. ALM shows better accuracy in all the cases.

On GPS based system the distance between the vehicles are calculated based on the position information received by the GPS receiver. The GPS receiver in the particular device finds the X, Y coordinates such as latitude and longitude values of all the vehicles. These values are used to calculate the distance using the Euclidean distance calculation method. The GPS, based system assumes that all the vehicles are connected with a GPS receiver. But in real life scenarios, all the vehicles are not always connected with GPS system due to some external factors.

In Received Signal Strength Indication (RSSI) based system, the vehicles share their radio frequency range through the beacon message when it fails to receive the GPS coordinates. The path loss monitor is the important factor while considering the Received Signal Strength Indication. It is the major component in the analysis and design of the communication networks. The free space path loss model calculates the power loss in transmitter and the receiver antenna measure in dB. Gain power, distance and frequency are the three metrics used to calculate the power loss in dB. The signal strength of the vehicles is not always correct because it may be blocked by some obstacles on the road hence the error increased thus reduces the accuracy. Hence, in ALM the vehicles can easily share their position information without any infrastructure support through an ACK message. So the ALM increases the Localization Accuracy as well as decreases the Localization Error in Vehicular Ad Hoc Networks.

• VI.    Conclusion

This paper proposes a new Acknowledgement based Localization Method (ALM) to improve the localization accuracy and to reduce the localization error caused by vehicle’s misdetection factor. The proposed ALM method is compared with well known localization methods such as RSSI, TOA and DLM. From the results it is clearly seen that the proposed algorithm improves the Localization Accuracy and reduces the Localization Error for varying distance, moving speed and transmission range. ALM uses on demand position update to improve the accuracy level and to reduce the error rate. Hence the proposed ALM Localization Method is suitable for Dynamic Ad Hoc Vehicular Networks.

Acknowledgment

This work was supported by University Grants Commission (UGC) under Senior Research Fellowship (SRF), UGC-NEW DELHI.