Portal de Periódicos da CAPES

VRDD: vehicular relevance‐based data dissemination in a vehicular ad hoc network

2019; Institution of Engineering and Technology; Volume: 13; Issue: 12 Linguagem: Inglês

10.1049/iet-its.2019.0294

1751-9578

Debanjan Roy Chowdhury, Vinod Kumar Jain,

Opportunistic and Delay-Tolerant Networks

IET Intelligent Transport SystemsVolume 13, Issue 12 p. 1792-1803 Research ArticleFree Access VRDD: vehicular relevance-based data dissemination in a vehicular ad hoc network Debanjan Roy Chowdhury, Debanjan Roy Chowdhury orcid.org/0000-0002-8422-7768 Department of Computer Science and Engineering, PDPM – Indian Institute of Information Technology, Design and Manufacturing Jabalpur, Dumna Airport Road, P.O. Khamaria, Jabalpur, Madhya Pradesh, IndiaSearch for more papers by this authorVinod Kumar Jain, Corresponding Author Vinod Kumar Jain vkjain@iiitdmj.ac.in orcid.org/0000-0002-5725-4998 Department of Computer Science and Engineering, PDPM – Indian Institute of Information Technology, Design and Manufacturing Jabalpur, Dumna Airport Road, P.O. Khamaria, Jabalpur, Madhya Pradesh, IndiaSearch for more papers by this author Debanjan Roy Chowdhury, Debanjan Roy Chowdhury orcid.org/0000-0002-8422-7768 Department of Computer Science and Engineering, PDPM – Indian Institute of Information Technology, Design and Manufacturing Jabalpur, Dumna Airport Road, P.O. Khamaria, Jabalpur, Madhya Pradesh, IndiaSearch for more papers by this authorVinod Kumar Jain, Corresponding Author Vinod Kumar Jain vkjain@iiitdmj.ac.in orcid.org/0000-0002-5725-4998 Department of Computer Science and Engineering, PDPM – Indian Institute of Information Technology, Design and Manufacturing Jabalpur, Dumna Airport Road, P.O. Khamaria, Jabalpur, Madhya Pradesh, IndiaSearch for more papers by this author First published: 21 November 2019 https://doi.org/10.1049/iet-its.2019.0294Citations: 1AboutSectionsPDF ToolsRequest permissionExport citationAdd to favoritesTrack citation ShareShare Give accessShare full text accessShare full-text accessPlease review our Terms and Conditions of Use and check box below to share full-text version of article.I have read and accept the Wiley Online Library Terms and Conditions of UseShareable LinkUse the link below to share a full-text version of this article with your friends and colleagues. Learn more.Copy URL Share a linkShare onFacebookTwitterLinkedInRedditWechat Abstract Safety message (SM) dissemination in vehicular ad hoc network needs to be fast as it allows vehicles to become alert and avoid adverse situations. An SM usually gets disseminated within a topology by multi-hop broadcast technique. Existing protocols have proposed various controlled flooding mechanisms to address the issues of broadcast storm and network partition. However, no work has been done to take care the direction of message dissemination. In a real scenario, all vehicles within an area of interest (AOI) are not equally affected by an emergency incident. The vehicles of the road where the incident happened, or the vehicles of roads which are connected to incident location by nearby junctions, are most affected and hence are more relevant to receive the SM as fast as possible. Hence, this study proposes a novel method to predict the relevance of vehicles using a distributed algorithm and heuristically tries to disseminate SM toward the relevant vehicles. The authors have compared their work with three state of-the-art algorithms and found that vehicular relevance-based data dissemination is compatible with the existing algorithms on the metrics of packet loss and dissemination delay, but clearly leading in the metric of relevant dissemination. 1 Introduction Vehicular ad hoc network (VANET) has become a wide area of research to provide vehicles safety and infotainment services recognised by intelligent transportation systems [1]. Vehicles are pre-installed with a radio device named 'onboard unit' by which they communicate among themselves and also communicate with static roadside infrastructure named 'roadside unit'. VANET can form both infrastructure network as well as ad hoc network. Hence, there are two types of communications possible in VANET, namely 'vehicle to infrastructure (V2I)' and 'vehicle to vehicle (V2V)'. Although some protocols [2, 3] rely on V2I communication for data dissemination, RSU deployment is costly and may be unavailable in many places. So, we rely on infrastructure less ad hoc V2V communication only for dissemination of safety messages (SMs). V2V communications within vehicles can be of three types, namely one to many (e.g. advertising the availability of a service by a vehicle), many to many (e.g. disseminating an SM among vehicles) and one to one (e.g. availing Internet service or other infotainment services). In many-to-many communication, multi-hop broadcast technique is used to disseminate an important message to as many vehicles as possible within an area of interest (AOI). Multi-hop broadcast usually suffers from some well known problems such as broadcast storm and network partition. In existing works, one or both of the challenges have been addressed by applying different techniques. Broadcast storm problem is usually handled by controlled flooding, where few vehicles are chosen for rebroadcasting to propagate the message. Network partition problem is handled by choosing vehicle(s), which is predicted to have minimum delay to meet a vehicle from another network fragment. 1.1 Motivation Existing algorithms for handling broadcast storm problem rely on parameters such as the location of the vehicle, distance from the sender, channel congestion, number of neighbours etc. to choose next vehicle for rebroadcasting an SM. However, in an urban scenario, an SM can get propagated toward any direction within AOI which may not be an important or relevant direction for the incident location. Vehicles travelling along the roads and heading toward incident location are more relevant to the SM than the vehicles which are travelling on different roads or moving away from the incident location. So, if an irrelevant vehicle is chosen as next hop to rebroadcast, it further propagates the SM toward irrelevant direction, whereas some important directions may get ignored which will cause some relevant vehicles to remain uninformed about the incident. This is illustrated in Fig. 1. After V1 and V2 met with an accident, observer vehicle V5 originates an SM and broadcasts it. As V3 and V5 are most affected by the incident, SM needs to propagate along the travel paths of V3 and V5 with highest priority so that other vehicles along these paths can be aware of the incident. Vehicle V7 is partially relevant because it is currently not on the affected road, but it is likely to meet the affected location soon. V4 will remain unaffected with the incident because, as based on its current travel direction, it may be predicted that the road it is travelling on will meet the affected road in a far distant location from the incident location. V8 is also unaffected because it is moving away from the incident location. As V8 is one of the most distant vehicles for the communication radius of observer V5, it may get selected as the next rebroadcast node by existing algorithms. Hearing the redundant SM from V8, relevant vehicle V6 and partially relevant vehicle V7 will cancel their rebroadcast and hence the SM may not get propagated along the paths of V5 and V7 and instead will get propagated along the irrelevant direction of V8 which is clearly unacceptable. Fig. 1Open in figure viewerPowerPoint Illustration of vehicle relevance 1.2 Novelty The novelty of our proposed protocol named 'vehicular relevance-based data dissemination in VANET (VRDD)' is that it aims to disseminate an SM toward the direction of relevant vehicles with higher priority with minimised delay and packet loss (PL). A heuristic method has been used in VRDD to predict the relevance of vehicles and to choose a suitable relevant vehicle for next rebroadcast. As mobility of vehicles are bounded by the road topology, we have assumed that if a road is not too much irregular, the travel direction of a vehicle on that road will match with the travel direction of other nearby vehicles on that same road and will differ with the travel direction of vehicles travelling on different roads. Depending on the deviation of travel direction between sender and receiver vehicles, the algorithm predicts how likely it is for a vehicle to reach nearby the immediate sender's location. If it is predicted that the receiver vehicle is unlikely to reach immediate sender's nearby location, the receiving vehicle is not relevant to that SM and will not be chosen as next-hop rebroadcast node. SM is disseminated along relevant directions with higher priority and broadcast storm problem is mitigated because only a few relevant vehicles are selected as next-hop rebroadcast node. In VRDD, network partition problem is handled along each road, where the last vehicle of each road waits until it meets a new vehicle along that road to rebroadcast the SM. The performance of the proposed VRDD is measured in one type of highway topology and two types (irregular and grid) of urban topology with the metrics of 'packet loss', 'packet redundancy' (PR), 'dissemination delay' (DD), 'vehicle coverage ratio' (VCR) and 'relevant vehicle penetration ratio' (RVPR). The effectiveness of the proposed algorithm is evaluated and compared with some benchmark state-of-the-art algorithms such as 'traffic adaptive data dissemination (TrAD)' [4], 'DRIVE' [5] and 'DV-CAST' [6]. The results show that the proposed VRDD algorithm effectively solves the broadcast storm and network partitioning problem of many-to-many communication in VANET and delivers SM to most of the relevant vehicles with lesser delay and PL. Rest of this paper is organised as follows: in Section 2, we have briefly discussed the IEEE standard 'wireless access in vehicular environment (WAVE)' for VANET communication and some challenges in VANET data dissemination. Section 3 focuses on some benchmark works done to mitigate the challenges of multi-hop broadcasting in VANET. In Section 4, we have described our proposed VRDD algorithm and its methodologies in details. Section 5 contains comparative performance analysis of simulation results with some benchmark algorithms. Finally, in Section 6, the conclusions and future extendibility of VRDD are discussed. 2 Background This section briefly highlights the IEEE 1609 'WAVE' standard and key challenges of data dissemination in the following two sections. 2.1 IEEE standard for VANET Radio communication among vehicles in VANET uses the standard WAVE defined in IEEE 1609 [7]. WAVE recommends the use of seven radio channels of 10 MHz bandwidth (ranges from 5.855 to 5.925 GHz) for 'WAVE short message' packet transmission. The channels are numbered from 172 to 184, where channel 178 (5.89 GHz) is the control channel (CCH) used for timing advertisement, WAVE service advertisement (WSA) etc. and channel 172 (5.86 GHz) is used for exchanging SMs. Other channels are used for providing infotainment services as advertised by WSA in CCH. So a vehicle needs to monitor in CCH for any new WSA of its interest even while it is participating in an ongoing service in one of the service channels (SCHs). The multi-hop broadcast V2V data dissemination faces few challenges, which are described in the next section. 2.2 Data dissemination challenges in VANET SM disseminating within AOI of VANET using V2V multi-hop broadcast is challenging due to the highly dynamic nature of the network topology. Owing to the high velocity, vehicles frequently leave one network and join another by changing roads. In case of traffic congestion, the density of vehicles becomes very high and forms a very dense network, whereas in case of light traffic, vehicles are too far apart from each other to form a well-connected network. This section describes some major challenges faced in SM dissemination in both highly dense and sparse scenarios: Challenges in dense scenario : In a dense scenario, after receiving an SM, if all vehicles try to rebroadcast it simultaneously, most of the packets will collide with each other and will be lost. This phenomenon is called broadcast storm problem (as illustrated in Fig. 2). To mitigate this challenge, various algorithms apply different techniques to desynchronise the rebroadcast schedule within nearby vehicles. Challenges in sparse scenario : In the sparse scenario, vehicles are fragmented into number of disconnected networks. Hence, an SM generated for an emergency incident fails to propagate from one fragment to another. This is described as network partition problem and is also shown in Fig. 2. Various algorithms choose one or more suitable vehicles and assign the role to carry forward the SM from one network fragment to another. Fig. 2Open in figure viewerPowerPoint Illustration of the broadcast storm and network partition problem 3 Related work This section describes various algorithms proposed to mitigate the challenges mentioned in the above section in case of V2V ad hoc network. Controlled flooding or broadcast suppression techniques for mitigation of broadcast storm problem in V2V multi-hop data dissemination in VANET has been broadly classified into two classes, namely 'sender-oriented schemes (SOSs)' and 'receiver-oriented schemes (ROSs)' [8]. There are certain merits and demerits in both the schemes, which are discussed as follows. In SOS, the SM sender vehicle chooses one or more vehicles among its neighbours and assigns a rebroadcast task to them. 'Urban multi-hop broadcast' [9] and 'smart broadcast (SB)' [10] are examples of SOS, where a handshaking mechanism is used to establish a connection between sender and farthest receiver(s) and the sender vehicle explicitly delegates the rebroadcast task to the connected receiver(s). However, the connection is not stable as the farthest vehicles can move out of communication range or some obstacle may disrupt the connection before handshaking process can take place. In this case, the sender vehicle again establishes new connection to another vehicle(s), which causes extra delay in SM propagation. Another SOS algorithm 'the TrAD' [4] does not establish any connection with receivers. Instead, it implicitly selects vehicles as next hop by calculating priority for all of its neighbours and appending the priority rank list along with the rebroadcast packet of SM. Receiving an SM, all vehicles check their rank in the attached list and assign rebroadcast delay proportional to its rank. SOS algorithms perform well for PL, as only the selected vehicles get chance to rebroadcast. However, in highly dense scenario, the sender vehicle gets overburdened with heavy computation which increases delay. In ROS, all the receiving vehicles decide for themselves in a distributive manner whether to rebroadcast an SM, and if yes it also decides a wait time or delay before rebroadcast. ROS algorithms can be further categorised into two subclasses called 'probability based' and 'delay based' as mentioned in [11]. Vehicles in probability-based algorithms [12-16] rebroadcast an SM with some calculated probability. As not all the vehicles decide to rebroadcast every time, flooding is avoided. 'DV-CAST' [6] is an example of probability-based algorithm proposed concerning only for highway scenario uses 'p-persistence' method for broadcast suppression. Clustering and probabilistic broadcasting (CPB) [13] is another probability-based algorithm applicable to highway scenario. In CPB, suitable vehicles depending on their position and travel direction form clusters and a cluster head (CH) is elected within each cluster. Each vehicle relays a received message to CH with calculated probability depending on the local vehicular density. In delay-based algorithms, vehicles calculate their own rebroadcast delay in a purely distributive manner based on some parameters such as location of the vehicle, distance from the sender, channel congestion, number of neighbours etc. The vehicle with minimum delay rebroadcasts the SM, and if neighbouring vehicles of the sender receive this duplicate SM, then they cancel their rebroadcast schedule to avoid flooding. 'UV-CAST' [14] algorithm is a delay-based algorithm, which has been proposed for the two-dimensional urban scenario. 'UV-CAST' gives priority to the vehicles, which are near any of the junction within AOI. Thus, it requires to know all the junction points in prior which may not be available in few situations. Both in DV-CAST and UV-CAST, vehicles are aware of their local topology by exchanging beacon message (BM) and maintain a neighbour list. SEAD [17] is a hybrid algorithm which applies both delay-based and probability-based techniques, but is not applicable for irregular urban scenarios. DRIVE [5] algorithm works on both highway and urban scenario and does not require vehicles to know their local topology. Here, the communication area of the sender vehicle is divided into four quadrants and some area within each quadrant is assumed as 'sweet spot'. Receiving vehicles calculate whether it belongs to any of the sweet spots for sender's location, and if yes it assigns shorter delay for itself compared with the vehicles not situated in any of the sweet spots. Within the vehicles in sweet spots, the vehicles which are far apart from the sender vehicle get higher priority for rebroadcast. ICARUS algorithm [18] has used the same sweet spot concept for controlling flooding, and additionally, proposed the method named 're-routeing' to find alternative path in case of traffic congestion. ROS algorithms usually have shorter DD compared with SOS as the rebroadcast delay computation is distributive, but in highly dense scenario, it suffers from more PL compared with SOS algorithms as many vehicles can end up calculating similar rebroadcast delay for themselves. Network partition issue has been handled by DV-CAST algorithm [6] for highway scenario only. With the help of periodic BM, vehicles categorise their neighbours into three groups, namely network bridge (NB)_FRONT (neighbours moving ahead in the same direction), NB_BACK (neighbours following in the same direction) and NB_OPPOSITE (neighbours moving in the opposite direction). Depending on the cardinality of these sets, each vehicle defines its connectivity state with the help of three flags named message direction connectivity (MDC), opposite direction connectivity (ODC) and destination flag (Dflg). On the basis of the flag combination, it determines whether to perform the role of relay node. TrAD algorithm [4] handles network partition issue by selecting one or more store carry forward (SCF) agent(s). In TrAD, a vehicle takes up the role of SCF agent if either of it is near to any of the junction points or it is moving in the message forwarding direction and is the farthest from the sender. However, here the disadvantage is that the algorithm needs to know the list of all junction points of an AOI in prior which may not be feasible in all cases. UV-CAST algorithm [14] detects the border vehicles by its proposed 'gift-wrapping' algorithm and selects them as SCF agents. However, none of the algorithms ensures that the vehicles selected as SCF agent or NB vehicle will meet a relevant vehicle to rebroadcast the SM so that it gets further disseminated among other relevant vehicles of another network fragment. 3.1 Drawbacks in existing methods and the proposed solution Existing algorithms measure the candidature of a vehicle for becoming a next-hop node by primarily focusing on location (distance from sender, distance from any junction point, sweet spot etc.) or by the help of randomness. However, none of them has tried to measure the candidature by relevance of vehicles and has not targeted the dissemination of SM toward the directions of relevant vehicles. If an irrelevant vehicle gets higher priority for rebroadcast than a relevant vehicle, a relevant vehicle may cancel its rebroadcast schedule hearing duplicate SM rebroadcast from irrelevant vehicle. Hence, SM will not be propagated along the path of relevant vehicles, and thus, SM may fail to serve its purpose. The situation is described in Section 1.1. To solve this issue, in [19], we have proposed the 'TAFDRV' (first of its kind) algorithm, where a simple approach is used to predict the relevance of a vehicle by the use of its travel angle. The arc-tangent value between a vehicle's current and recent past location is measured as 'travel angle' of the vehicle at a particular moment. This calculated travel angle of vehicles is compared to determine whether they are on the same road or different. Vehicles travelling on same road are given more priority as next-hop node than others. However, this algorithm of relevance calculation has a few major limitations which are enlisted below: It cannot distinguish whether two vehicles are travelling along the same road or they are travelling along two parallel roads. It does not take into account whether a vehicle is moving toward the incident location or moving away from the location. These issues have been addressed in the enhanced algorithm VRDD, which is discussed in the next section. A feature wise comparison among existing algorithms and VRDD are shown in Table 1. Table 1. Comparative study among existing algorithms and VRDD Algorithm Type Computation overhead PL Network partition Supported topology Relevant dissemination SB centralised (SOS) moderate low not supported urban no TrAD centralised (SOS) high low supported urban/highway no DV-CAST distributed (ROS) moderate moderate supported highway no DRIVE distributed (ROS) low high supported urban/highway no VRDD distributed (ROS) moderate low supported urban/highway yes 4 Proposed VRDD algorithm When an emergency incident happens within AOI of VANET, some vehicles, depending on their travel path and the incident location, need to respond quickly to the incident, whereas some vehicles can ignore the incident. An example of this scenario has been described in Section 1.1. In VRDD, we present a heuristic method to predict the affectedness or relevance of a vehicle and calculate desynchronised rebroadcast delay to control flooding. The detailed methodology of VRDD involving various steps, namely (i) travel path line (TPL) estimation, (ii) vehicle relevance prediction, (iii) suitability index and rebroadcast delay calculation, (iv) NB vehicles selection and (v) data dissemination challenges handling are described in the following sections. 4.1 TPL estimation In the proposed VRDD, each vehicle at any moment keeps track of its last five global positioning system positions, which is maintained in a queue of size five. The position sample frequency is proportional to its current velocity such that a vehicle can generate five samples within a distance of ∼200 m which means one position sample is taken in every 40 m of travel distance. When a vehicle receives an SM, it applies the well known 'least-squares' method on its stored last five positions to get the best fit line which represents the TPL of that vehicle at the time of receiving the SM. By this method, path estimation error due to steering movement along a road for lane change or to avoid obstacle can be minimised. Slope M and Y -intercept C of TPL is calculated as shown in Algorithm 1 (see Fig. 3). By empirical analysis with several topologies, we have found that the direction of a road usually does not change much in a span of 40 m. So, more sample points will unnecessarily result increased computation overhead in the least-square method to estimate TPL. On the other hand, if we try to accumulate more samples for TPL estimation by increasing the span of sampling distance >200 m, it will be too much of generalisation for TPL estimation so that TPL of two different roads will tend to be similar. Fig. 3Open in figure viewerPowerPoint Algorithm 1: 'least-square' method used for calculating slope M and Y-intercept C of TPL 4.2 Predicting relevance We define the relevance (R) of a vehicle by its likelihood of reaching nearer to its immediate previous-hop vehicle of SM. The value of R ranges from 0 to 1, where 1 denotes the highest relevance. The relevance R depends on the acute angle between the TPLs of its immediate previous-hop sender vehicle and itself, where is calculated by the following equation: (1) and of (1) are the tangent (M) of sender's TPL and receiver's TPL, respectively, and is calculated by Algorithm 1. After receiving an SM when a receiver vehicle calculates , it sets the value of with its own calculated M and obtains readily from the SM which is provided by the sender. The relevance also depends on the Y -intercept difference . As shown in Algorithm 1, if two neighbour vehicles are travelling along the same road, they will have similar TPLs, and the acute angle between them will be below a threshold angle tolerance . In the case when two vehicles are travelling along different roads which are nearly parallel to each other, produced between them will be below , but the difference between Y -intercepts or will be higher than a threshold . The detailed procedure to calculate R is given in Algorithm 2 (see Fig. 4). As per the algorithm, the receiver vehicles travelling along with the sender vehicle's road will have . If they are on different roads and their travel paths are near to be perpendicular to each other, we assume that the roads on which the vehicles are travelling are going to intersect in a nearby location. In that case, if the vehicle is moving toward the sender vehicle's location, the algorithm assigns higher R value to it than a vehicle moving away from the sender vehicle. Vehicles travelling along roads which are almost parallel to the sender's road, are assigned lowest R by the algorithm. Fig. 4Open in figure viewerPowerPoint Algorithm 2: algorithm for calculating relevance R in VRDD The method mentioned above has a limitation in case of sharp bend or U-turn. In this case, vehicles on same road will have very different TPLs from each other and will assume themselves to be on different roads. However, we are becoming optimistic here by a realistic assumption that there will be very less number or no sharp bending and U-turn inside the AOI of SM generation place, and even if one is observed only a very few vehicles at that moment will cross those sharp bends. As only few vehicles will make their calculations wrong and as every vehicle's calculation is independent of each other, these few wrong calculations will have minimal effect on this algorithm. To disseminate an SM toward relevant vehicles, the vehicles with higher R needs to be selected as next-hop rebroadcast nodes. However, it may happen that the vehicles which are closer to the sender are always selected as next-hop vehicles. This makes the dissemination slow, as in each hop, SM is traversing only a small distance. For faster dissemination, farthest vehicle needs to be selected as rebroadcasting node in each hop. To balance the trade off relevance and fastness of, we have defined a new parameter named 'suitability index' combining relevance factor and fastness factor. VRDD algorithm uses this suitability index to calculate rebroadcast delay for each vehicle, by which they contest among themselves to get chance to rebroadcast the SM. The procedures of calculating suitability index and rebroadcast delay are described in the following section. 4.3 Suitability index and rebroadcast delay calculation 'Suitability index' () of a vehicle ranges from 0 to 1, denotes how much suitable a vehicle is to be the next rebroadcast node of an SM. Each vehicle calculates its own independently as given below: (2) of (2) is the normalised distance for the communication radius () between sender and receiver vehicles, which ranges in [0–1]. We balance between relevance and fastness of dissemination by using two tuning variables and such that . If we want to give priority to relevance of dissemination, we need to set higher value of . However, that can make dissemination process slow because nearby vehicles from sender may be selected in each hop for dissemination. To increase the fastness of dissemination of message, we need to set higher value of which may cost losing the relevance of dissemination. The is used to calculate the 'rebroadcast delay' (T) for a vehicle and is calculated in the following steps: (i) Normalised neighbour count calculation : Neighbour count (N) of a vehicle is normalised for a value (maximum neighbour count) to get 'normalised neighbour count' () which ranges from 0 to 1 and used to measure the network density surrounding a vehicle. With the help of received periodic BM, a vehicle keeps track of its current neighbour count. The value of is proportional with the transmission power of the vehicles. Greater value of transmission power causes a vehicle receiving beacons from more vehicles and hence increases . The value of is calculated as (3) (ii) Density factor calculation : Density factor () is used to adjust the rebroadcast delay of a vehicle depending on the current density of topology surrounding that vehicle. The vehicles with higher calculate shorter rebroadcast delays for themselves in comparison with the vehicles with lower . However, if the topology becomes too dense, many nearby vehicles will have almost same and hence will calculate same rebroadcast delay for themselves which will result in packet collision. So to desynchronise their rebroadcast delay, we apply density factor while calculating 'rebroadcast delay'. The equation for calculating is given below: (4) The term in (4) is delay tolerance per hop which denotes the max time [in milliseconds (ms)] a vehicle is allowed to wait before rebroadcasting an SM. The value of the can be set depending on how criti