The Vehicular Named Data Networking (VNDN) technology advent promisingly paves the way to tackle challenges of high performing large-scale content distribution provisioning in Internet Protocol (IP)-centric Ad-Hoc Vehicular Networks (VANETs) [1
]. By definition, the IP paradigm cannot both offer users massive content delivery, as well as ensure the requirements of distributed VANET application concerning Quality of Service (QoS) and Quality of Experience (QoE) [2
]. The reason behind the aforementioned IP issues in VANETS arises from the intense vehicle mobility patterns, which result in constant topological dynamics. As a consequence, this ends up generating overload on the network to maintain the particular requirements of the Transmission Control Protocol (TCP)/IP protocol stack, such as neighbor discovery and maintenance, address reallocation, and connection-oriented sessions [5
Named Data Networking (NDN), which implements the Information-Centric Networking (ICN) [8
] communication paradigm, affords VNDN inter-vehicle communication. In NDN, communication happens through exchanging interest and data packets. In contrast to IP-based architectures, interest and data packets harness the content name as the exclusive network identification. Thus, the NDN networking planning steps in the inter-node communication task are two-fold. In the first step, a particular consumer node sends an interest packet carrying the name of the intended content. In the second step, a producer node transmitting a respective data packet returns the requested content to the consumer node. In other words, the producer node who has the searched content in the cache (Content Store (CS)) sends it through a data packet to the consumer node. Because of that, the cache discovery process refers to the search for content on the network. The content delivery rate regards the percentage of vehicles that have successfully received the requested content [9
]. Aside from that, it is worth noting that intermediary nodes operate as both content consumers and producers [10
]. Hence, nodes can function as data mules in the lack of connectivity, so that future requests in content are attended more closely to the consumer nodes.
Therefore, VNDN comes up with the prospecting potential to maximize large-scale content delivery, taking into account both the QoS and QoE requirements of applications distributed in Intelligent Transport Systems (ITS) [11
]. Incidentally, ITS are contemplated as a key technology to enable more efficient and secure traffic management that ranges from cooperative and distributed route planning [14
], traffic and road alerts [18
], and enhanced video distribution [21
], to advisory systems for driving strategy [24
], and autonomous driving capabilities [27
]. Furthermore, the VNDN concept exploits the ICN communication paradigm by changing the ways of requesting and retrieving content from the network, since the content name is the main element of the network and must be globally unique, persistent, secure, and location-independent [30
]. It is noteworthy that cache content is another fundamental element in VNDN, which increases the availability of content on the network with multiple providers. In this way, the original producer can retrieve the content or the intermediate nodes that have a replica of the local cache’s content.
However, the integration of the NDN architecture into VANETs (i.e., VNDN) is not trivial and raises many challenges, especially concerning vehicle mobility, access security, naming, and content storage [10
]. Regarding large-scale content delivery across traditional VNDN, the occurrence of a broadcast storm during a cache discovering process raises the main critical issue that this paper addresses. Such an issue refers to the multiple uncoordinated transmissions of interest packets, which severely jeopardize the underlying communication channel as a consequence of network flooding events [10
This paper proposes OVERT VNDN, a cache discOVEry pRoTocol that harnesses both computational geometry and degree centrality concepts to tackle the broadcast storm problem that arises during inter-vehicle communications efficiently. The OVERT VNDN proposal was designed with the ability to choose the most appropriate relay vehicles to reduce interest packets’ transmission within the VNDN by employing both the convex hull and the degree centrality of the neighbors. It is important to mention that the prime motivation for leveraging VNDN architecture comes from the network cache element that the NDN architecture offers, along with the content-centric inter-vehicle communication approach. Simulation outcomes suggest that OVERT VNDN outperforms the VanillaVNDN-related benchmarking solution in the following Key Performance Indicators (KPIs): (i)successfully mitigates the broadcast storm incidence during inter-vehicle communication, diminishing packet collision rate occurrence beyond 50%, on average; (ii) enhances the content delivery ratio by 58.02% while achieving a high cache hit rate maintenance of more than 43% during the cache discovery process; and (iii) decreasing the interest packets’ transmission by 80.99%.
The remainder of this article is organized as follows. Section 2
surveys the most relevant related works that motivate our solution design. Section 3
introduces the OVERT VNDN proposal in detail, including the functional architecture and embedding mechanisms and functionalities. Section 4
presents a discussion of the simulation results and related insights. Finally, Section 5
wraps up the article with concluding remarks along with the prospects for future works.
2. Related Work
This section examines how recent VNDN approaches tackle the interest broadcast storm problem during a cache discovery process in information-centric VANETs and discusses the impacts on inter-vehicle communications.
Kuai et al. [32
] proposed a neighborhood-prioritization approach called Density-Aware Delay-Tolerant (DADT). DADT uses timers to prioritize nodes in the cache discovery process. To improve the packet delivery ratio, DADT considers the neighboring vehicles (receivers) farthest from the sender vehicle and closest to the producer vehicles. Thus, DADT relies on two factors: (i) periodic beaconing for neighborhood discovery and (ii) the knowledge of data producers’ location. Due to the latter factor, consumers and producers are not fully decoupled, which is one of the drawbacks of current IP-based solutions.
Yu et al. [33
] came up with an Opportunistic Interest Forwarding Protocol (OIFP) to tackle the interest broadcast storm problem in VNDN. To manage redundant interest transmissions, OIFP considers the distance between a current forwarder and its neighboring vehicles. In contrast to DADT [32
], the OIFP protocol does not use the location information of the content provider. The prioritization is accomplished by the use of defer timers, which are related to their distance to the current forwarder vehicle. Thus, the vehicles that are farther from a sender node have a lower interest transmission defer time.
Boukerche et al. [34
] and Sousa et al. [35
] introduced a link stability-based interest-forwarding protocol to deal with the broadcast storm problem. These approaches aim to reduce the number of interest packets and data packets on the network. For this, the strategies control interest packets by prioritizing neighboring nodes with more stable links with the current forwarder (i.e., sender). Its connectivity duration determines the link stability between the vehicles with the existing interest forwarder. Thus, the vehicles with a higher priority transmit first, while the vehicles with a lower priority suppress their transmission of the given interest.
Rondon et al. [9
] designed a cache discovery protocol to mitigate the interest broadcast storm problem, called CDP (Content Discovery Protocol). CDP uses the best geographically positioned vehicles to forward the interest, which avoids redundant transmissions. To choose the best vehicles, CDP first considers the distance of the current transmitter relative to its neighborhood. The best-positioned concept (i.e., sweet spot) is applied to prioritize the highest priority vehicles to continue the cache discovery process. In contrast, the lowest priority vehicles suppress their scheduled interest transmissions. Although CDP is efficient in a topological matrix scenario, such a protocol tends to lose performance in the cache discovery process in radial scenarios. This is due to the angle of the sweet spot that was modeled for matrix scenarios, such as a highway. Furthermore, the strategy for choosing retransmitter vehicles is fixed due to the way the sweet spot was angled. As a result, the cache hit rate and the content delivery rate guarantee are affected.
Arsalan and Rehman [36
] developed a technique to mitigate the broadcast storm issue, called BSAM (Broadcast Storm Avoidance Mechanism). BSAM outlines a counter value that is given for each vehicle by calculating its distances from the sender vehicle. BSAM offers the lowest data packet delay (compared to a traditional VNDN protocol) due to only the farthest sender node from the consumer node having Pending Interest Table (PIT) entries. This means that the BSAM scheme decreases the average number of interest packets transmitted.
Boukerche and Coutinho [37
] presented an architecture to improve the cache discovery process and reduce the broadcast storm problem in intelligent vehicular networks, called LoICen (Location-based and Information-Centric). In LoICen, the receiver vehicles obtain the location of the vehicles that might have an interest packet in their cache. Whenever possible, this location information is available to be used during a cache discovery process. The location-oriented approach employed in LoICen and selecting only the most suitable neighboring vehicle to continue forwarding the interest packet is possible.
Guo et al. [38
] proposed a scheme to mitigate the broadcast storm problem of interest packets, named BRFD (Bayesian-based Receiver Forwarding Decision scheme for the interest packet). In BRFD, the forwarding of an interest packet is decided based on knowledge of network operation conditions learned by the Bayesian decision model. The model considers the distance between a sender node and a receiver node, vehicle speed, and the one-hop neighborhood degree. Thus, BRFD suppresses the interest broadcast storm issue that could flood the VNDN network.
Burhan and Rehman [39
] proposed a strategy called BSMS (Broadcast Storm Mitigation Strategy) to mitigate the broadcast storm problem. BSMS also tackles the issue of the disconnect link by using a receiver timer counter. Moreover, BSMS relies on the distance and speed between receiver and sender vehicles to obtain this timer counter. Thus, the farther vehicle among neighboring vehicles transmits the interest packet by the network. When the interest packet is not received by the requesting vehicle, BSMS uses a forwarder timer counter. The interest broadcast operation is repeated when the forwarder timer counter finishes.
To address the transmission prioritization process, several research studies presented in this section used the forwarding strategies of interest packets based on the distance and link stability between receiver vehicles and the current sender. We also show approaches that consider a timer counter to prioritize the forwarding of interest packets among neighboring vehicles. Unlike these strategies, OVERT VNDN advances the state-of-the-art by using computational geometry and degree centrality concepts to tackle the broadcast storm problem that arises during inter-vehicle communications efficiently, as shown below.
3. OVERT VNDN: Towards an Efficient Cache Discovery Protocol
This section introduces OVERT VNDN, a cache discovery protocol that harnesses both the computational geometry and degree centrality concepts to tackle the broadcast storm problem in VNDN. OVERT VNDN has as its main goal to improve the content delivery ratio while maintaining a high cache hit rate on searching by the content with fewer transmissions of interest packets. The following describes the development of OVERT VNDN, including the problem formulation, the proposed protocol, and its operations.
3.1. Problem Formulation
The broadcast storm problem is critical in ad-hoc wireless networks since it causes inefficient use of network resources. In regards to the VNDN technology, the propagation occurrence of interest packets needs to be done in a controlled manner with the prospect of reducing one of the main challenges in inter-vehicle communications, packet collision incidence. Redundant transmissions of interest packets result in more packet collisions in the network, increasing rates of both content delivery delay and packet losses, and jeopardize VNDN application performance. Figure 1
shows a general VNDN scenario for which the broadcast storm occurs.
From Figure 1
, the consumer vehicle initially transmits an interest packet specifying the content’s name on the network. Then, the neighboring vehicles receive the packet. Since they do not have the corresponding data packet in the cache, all receiver vehicles will simultaneously retransmit the interest packet on the network. The result of these multiple retransmissions is the collision of packets. It is necessary to develop VNDN-tailored interest packet forwarding intelligent solutions, with the ability to reduce excess transmissions and enhance the efficiency in content delivery, in an attempt to mitigate the occurrence of a broadcast storm.
3.2. Proposed VNDN Protocol Model
Based on the problem formulation, the definition of the proposed protocol is described in the following.
We consider an urban VNDN scenario composed of n vehicles. Each vehicle has an ID () and is equipped with a communication interface compatible with the IEEE 802.11p standard. Such vehicles are modeled by a dynamic graph , which represents the asymmetric wireless links between vehicles, where represents the set of vehicles and represents the communication link between neighboring vehicles. Each vehicle knows its position in progress using a Global Positioning System (GPS). Furthermore, the set of neighboring vehicles is composed of neighbors at one hop of . The set represents the communication link between and its neighbors. Finally, let be the set of points containing the vertices of G.
We consider each vehicle continuing to propagate the interest packet as a point p in the convex hull of the set of points Q. For this, we assume that a polygon is convex when there is no straight line between two points inside the polygon that reaches the outside of the polygon. The convex hull of Q consists of the smallest convex polygon such that every point belonging to Q is inside or on the edge of .
OVERT VNDN aims to reduce the number of transmissions of interest packets while maintaining a high cache hit rate and an increase in the content delivery rate. For this purpose, OVERT VNDN is based on the concept of computational geometry and degree centrality to choose the vehicles transmitting interest packets. In this case, the problem of finding the convex hull in a given set Q of points was applied. This was done because the application of the convex hull can be made dynamically and independently of the scenario in question. Next, we present the functioning of OVERT VNDN to propagate interest and data packets.
3.3. OVERT VNDN Operations
To propagate interest packets, each vehicle
transmits periodic beacons containing its identification
and its current position
. The idea is that
contributes to contextual knowledge about its neighbors. Upon receiving a beacon,
saves this information in its list of neighbors
generates a set of points Q
when it needs to transmit the interest packets. Then,
calculates the convex hull
having as a parameter Q
with the Graham scan algorithm, whose time complexity is
]. After applying the Graham scan algorithm, among the vehicles that make up the minimum convex polygon, vehicles with higher degree centrality are selected to propagate the interest packet in the network, as presented in Figure 2
. The degree centrality is the number of vehicles neighboring the receiver vehicle, which is computed based on the beacon message. Degree centrality is an essential metric for understanding the importance of a node in the network [41
]. Next, the receiver vehicle inserts
in the interest packet. When neighboring vehicles receive the interest packet, they check if they are relay vehicles, making sure their
are contained in
. According to its degree centrality, such vehicles are selected to continue the process of retransmitting interest packets. Otherwise, they will discard interest packets.
Algorithm 1 shows the cache discovery mechanism’s operation to continue the transmission of the interest packet. When the packet received is an interest with particular content, it is necessary to check if such the interest is duplicated. For this, a search on the Pending Interest Table (PIT) is done (Line 3). PIT is used to maintain interests that have not yet been served with the corresponding data packets. If the interest is duplicated, it means that the same interest already exists in the PIT, and therefore, the interest received is discarded (Line 23). If there is any transmission scheduled for the interest stored in the PIT, the transmission will be canceled (Lines 21–22). This occurs due to a previous transmission of an interest packet by a neighboring vehicle. If the interest packet is not duplicated, the vehicle will consult the Content Store (CS) for the corresponding data packet (Line 4). CS is used to store the data packets according to the Time-To-Live (TTL) of the content. If the vehicle has the data packet, it means that there was a cache hit. Consequently, the vehicle sends the data packet to the vehicle that requested the content (Line 19). Otherwise, there will be a cache miss. With this, the vehicle inserts the interest in the PIT (Line 5). In the next step, the vehicle checks if it is a relay node (Line 6), checking in the received interest packet whether the appears in the set corresponding to the relay vehicles. If the is contained in , it means that the vehicle is part of the convex hull and, therefore, will transmit the interest packet according to its degree centrality (Lines 12–13).
Algorithm 2 shows the processing of the proposed protocol’s data packet. When a vehicle receives a data packet, it checks if there is any interest related to that content in the PIT (Line 2). If any interests are pending in the PIT, the vehicle checks if there is any schedule for the transmission of these interests. If so, the vehicle cancels such appointments (Lines 3 and 4). In this case, the vehicle transmits the data packet to the vehicles interested in that content and removes such interests from PIT (Lines 5 and 6). Furthermore, in the processing of the data packet, whenever a vehicle receives a data packet, it stores it in the CS (Line 7). With this, the vehicles operate as data mules transporting the content to another region to meet future requests and keep the content closer to potential vehicles interested in that content. This approach is also known as store-carry-forwarding.
It should be noted that the main contribution of the proposed protocol is given by the developed cache discovery strategy, which is based on the convex hull and the degree centrality of the neighbors to choose the best relay vehicles. As a result, it is possible to maximize the spread of interest, maintaining a high cache hit rate in the cache discovery process with fewer transmissions of interest packets, as will be presented in the next section.
|Algorithm 1: Received Interest packet.|
| Input: Interest [Name, Selector(s), NONCE, transmiterVehicles]|
|Algorithm 2: Received DATA packet.|
| Input: DATA [Name, MetaInfo, Content]|
The VNDN technology enables a high performing large-scale content distribution in IP-centric VANETs. There are still many challenges that need to be addressed in this field. This work tackled the negative effect of the broadcast storm during communication between vehicles in the VNDN cache discovery process. OVERT VNDN protocol’s main goal was to minimize the interest packet broadcast storm issue in VNDN. This allowed maximizing the content delivery rate on the network. To accomplish such an objective, OVERT VNDN took advantage of the computational geometry and degree centrality concepts to choose the relay vehicles dynamically. With that, it was possible to tackle the broadcast storm problem that arises during inter-vehicle communications. This process happened regardless of the scenario in question allowing for better propagation of the interest packets on the network. The simulation results showed that the proposed protocol outperformed its competitor. It improved the cache discovery process by 120.47% as well as the content delivery rate by 43%. At the same time, it reduced the number of interest packets by 80.99%.
As further work, we intend to compare OVERT VNDN with other works in the literature. Moreover, a new protocol is going to be developed to improve the data packet forwarding strategy based on the problem of finding the convex hull. The new protocol will disseminate the data packet based on the density of the urban road. Furthermore, a new implementation of the content replacement policies based on its popularity also is going to be proposed, as well as security and privacy issues are going to be considered.