PAMTree: Partitioned Multicast Tree Protocol for Efficient Data Dissemination in a VANET Environment

Abstract

The way to distribute a wide range of services on Vehicular Ad Hoc Networks is going to be a very interesting research topic, due to the willingness of the investors and the standardization institutions. In fact, the higher the number of available services is, the higher the impact and the market penetration of the considered technology will be. Also governance institutions appreciate the benefits of VANETs, having the possibility to increase safety level along the roads, saving lots of human lives, and reducing the severity of the collisions among vehicles. In this work we propose a multicast protocol, called partitioned multicast tree (PAMTree), which is suitable for spreading several kinds of services, increasing the reliability of the network, and giving the possibility to a higher number of users of having access to those services. The proposed protocol aims to exploit the characteristics of the VANET architecture in order to distribute services along the nodes of the network; owing to the high nodes mobility, several issues have to be faced to supply an optimal distribution, having a look at the quality of service (QoS) satisfaction.

1. Introduction

Nowadays, there have been more significant interests and progresses in the field of Intelligent Transportation System (ITS), from both industry and academia; moreover, the governance is giving a great contribution to spread this technology for several reasons, but the most important is the increase of the road safety. Commonly, ITS applications are organized into safety, transport efficiency, information, and entertainment applications: Vehicular Ad Hoc Networks (VANETs) are emerging as ITS technology, which integrate wireless communications for mobile users. VANETs are a special case of Mobile Ad Hoc Networks (MANETs), where the most important differences consist of the restriction of mobility constraints, the extremely high level of mobility, and time-varying vehicle traffic density. Regarding power consumption, which is one of the most important issues in wireless communications, it is not a major concern in VANET due to the installation of the communication devices. Two communication types are available in the considered infrastructure. (i)

Vehicle to Vehicle (V2V): it refers to communications among On-Board Units (OBUs) of vehicles (in a direct or multihop way).

(ii)

Vehicle to Infrastructure (V2I): it refers to the communication between vehicles and Road Side Units (RSUs).

In Figure 1 an example of Vehicular Ad Hoc Network (VANET) environment has been shown: the network can be exploited to provide wideband access to vehicles or to supply several services in order to enhance traffic management, increasing safety levels of our roads, acting on active and passive safety systems of our vehicles as well. A vehicle, also called node, may assume the role of intermediate router (or relay node), forwarding packets to one or more destinations, which are not in the radio coverage of the sending node.

Figure 1

A typical VANETs example.

Through intervehicle communications, nodes can exchange data with each other, including multimedia contents, in order to distribute the contents in a more efficient way in the network. In this work we present a multicast approach used to disseminate wideband services that require a QoS aware routing protocol. A new multicast routing protocol is proposed for VANET environment, taking the advantage of a dynamic allocation of the Dedicated Short Range Communications (DSRC) spectrum, in order to guarantee a certain level of QoS.

A lot of applications for the VANET technology have been developed, especially in areas where rapid deployment and dynamic reconfiguration are necessary when the wired network is not available. Within a wireless medium, it is even more crucial to reduce the transmission overhead. Multicasting can improve the efficiency of the wireless link when sending multiple copies of messages, by exploiting the inherent broadcast property of wireless transmissions. In VANETs, it is also important to use scalable routing approaches in the protocol design as presented in [1, 2], because in urban environment very dense networks can be formed and it should be handled in the best way. Generally, in an ad hoc environment, there are three basic categories of multicast algorithms. (i)

“A naive approach is to simply flood the network”: every node receiving a message floods it to a list of neighbours.

(ii)

The proactive approach computes paths when the sessions start for all destinations, storing them in routing tables. Database updating is made by sending periodic messages along the network with the main goal to keep routing tables updated.

(iii)

The final approach is to create paths to other hosts on demand. The main idea, that drove this approach, is based on a query-response mechanism or reactive multicast. Once the query reaches the destination, the response phase starts and the path can be established.

In this work we are going to exploit, as background, the Wave Short Message Protocol (WSMP). In order to bring up information about links status and available interconnections among nodes in other words we use the WSMP to gather data about network topology. Taking into account that a RSU and an OBU can be a relay node, we can exploit multicast data distribution along these nodes to improve network performances, avoiding resources wasting during data dissemination. Regarding links allocation and their utilization, we want to exploit the measurement of the interferences and the Link Duration Probability (LDP) of wireless interconnections, in order to assure certain levels of QoS in data distribution.

Table 1 shows the typical signaling messages used to update topology and position information about neighbor nodes. Let us recall that in a VANET environment one of the most important issues is to address the high mobility level of the nodes that belong to the considered network. This can influence the overall quality of the multicast tree bringing a rapid degradation of its performances. The partitioned multicast tree (PAMTree) protocol that we are going to present has the main task to disseminate data along the network in an efficient way, exploiting its characteristics. In order to reduce the management complexity, the protocol performs a network partitioning, achieving several clusters: each cluster is composed of a multicast subtree. The root of the subtree is the cluster head (CH), which is commonly associated with the local Road Side Unit (RSU). The CH has the main role of managing their destinations, allowing or denying multicast joining and managing the whole subtree. More details will be given in the next sections. In Section 2 we present the works related to the multicast protocols and data dissemination in the VANET environment. In Section 3 the reference network is presented as well as its architecture and its abstract representation. In Section 4 we present PAMTree protocol, giving also some brief concepts about QoS that we have considered in order to find the best path. In Section 5 the achieved results will be presented and at last the conclusion and possible extensions will be given.

Table 1

Type of message.

Message	Source	Destination	Type (periodic, on event)
Topology update	Vehicles (OBU)	OBU, RSU	On event

Position update	Vehicles (OBU)	OBU	Periodic

2. Related Work

New recently, the studies related to VANETs are bringing solutions that improve connectivity between entertainment applications (e.g., Social Network or Video Streaming on-demand) and passengers. The key aspects being considered are architectures for routing protocols suitable for multicast applications. In [3], authors proposed a distance node based multicast routing protocol (DBMR) for sparse areas with a small overhead of incorporating multicast group selection. The multicast behavior of the DBMR protocol encounters this issue to provide effective bandwidth utilization. The DBMR protocol uses only the one-hop neighbor information of the current forwarding node which is collected during the neighbor list creation phase. It exhibits unicast behavior when the destination node is within the coverage of the current forwarding node. The distant node selection phase is a heuristic based approach. A distant node is one which has the responsibility of forwarding the data packets using the store-carry-forward approach. Jie et al. in [4] built a trust opportunistic forwarding model based on the selection of the optimal forwarder in trust neighbor forwarding list and devise a trusted unicast (TMCOR) and a multicast routing protocol (TMCOM). In [5], authors presented a more efficient context-aware multicast protocol that disseminates messages only to vehicles involved in dangerous situations. These vehicles can be identified by calculating the interaction among vehicles based on their motion properties. To ensure very quick delivery, the dissemination follows a routing path obtained by computing a minimum delay tree with Dijkstra algorithm. This method improves the wireless channel usage by reducing the number of sent messages as well as the dissemination time by using the least-delay path. Our proposal protocol, on the other hand, uses a tree weighted considering crucial terms regarding the quality of the wireless link, by reducing the number of the retransmissions of messages. In [6], authors designed a cluster-based multisource multicast routing protocol with new cluster head election, path construction, and maintenance techniques. Due to the cluster structure and setting forwarding clusters, the CBMRP protocol is efficient and robust for multisource multicasting. Based on this, for more than one multicast source, CBMRP can prevent the flooding of route request messages. In [7, 8], authors proposed a QoS multicast routing protocol, based on heuristic genetic algorithms. It is applied over a high-altitude platform, satellite platform. They developed also a novel algorithm for a better optimization of the multicast tree cost, aimed at obtaining an algorithm that can consider QoS routing constraints and minimize the overall cost per link of the considered multicast tree. In [9], the authors designed a novel protocol to improve the general problem regarding the end-to-end delay in the shared-tree method as a modification to the existing Multicast Ad Hoc On-Demand Distance Vector (MAODV) routing for MANETs. This protocol uses the n-hop local ring search to establish a new forwarding path and to limit the flooding region and the periodic route discovery message, to improve the network throughput for the high mobility level scenario.

In [10], authors presented a multicast routing strategy for disseminating in cooperative collision warning system. It is one of the safety applications based on the exchange of dedicated messages between cooperative vehicles. This proposed multicast scheme incorporates the concept of adaptive transmission range and utilizes the vehicle interaction graph to identify the receiver nodes. In [11], authors studied the issue of QoS group communication in a heterogeneous network. They designed a new algorithm and provided scalable and stable multicast services on the Internet by introducing a new Delay Variation Estimation Scheme for heterogeneous networks. In [12], authors proposed a two-layer hierarchical synchronized multimedia multicast architecture to improve the single-layer synchronized multimedia multicast algorithm. In this new scheme, each wireless network operator can adapt its own management mechanism such as routing protocol and media access control and further define the range of guarantee region, to ensure different management requirements.

Regarding the composite metric, used in this work to build the multicast tree, we paid attention similar to these works [13, 14], where the authors designed routing protocols based on multiobjective optimization model to provide quality of service.

3. Reference Scenario

In Figure 2, the considered scenario is shown. It consists of some kind of connections, such as V2V that interconnects vehicles. The RSUs are used to allow communications between vehicles and external services such as a multicast services. Moreover, communication among several RSUs is also allowed. In particular, in this work, as external services, we provided to distribute multicast services into the network exploiting RSUs as service gateway. Normally, the vehicles are equipped by GPS sensor. But it is possible to use alternative approaches for the trilateration localization of the mobile nodes in outdoor environment, as discussed in [15]. Regarding multicast services in this work multimedia contents have been considered: they are delivered by Multimedia Content Server (MCS), which not only supplies services for VANET user but may supply the same contents towards other users connected to other types of networks. In the networking some specific entities are involved: (i)

multicast group manager (MGM), which has the aim of managing the MG and the related data flows,

(ii)

border gateway router (BGR), commonly used as border router,

(iii)

relay node (RN) which has the main goal of distributing media to other vehicles and can be an on-board unit (OBU) or a RSU.

Figure 2

Reference architecture, in which two MG send multimedia data flows over the network.

3.1. Network Representation

As known, a communication network can be commonly represented as a graph that is not oriented and weighted. In our cases, graph nodes are RSU and OBU systems. The main goal is to find a multicast tree on which packets are spread respecting some QoS constraints. Therefore the network graph G is composed of the set of the nodes V (OBUs and RSUs) and the set of the edges that connects nodes E; therefore the entire nomenclature of the Graph is $G 〈V, E〉$ . Each edge has associated an array of two weights: the first one is the LDP and the second one is a term related to the interference level among two nodes (Signal to Noise Interference Ratio (SNIR)). Therefore, if a connection can be established among two adjacent nodes (i and j), this can be summarized as herein shown. Therefore we can say that $(i, j) \in V$ , such that $i \neq j$ and $\exists e (i, j) \in E$ in terms of weight; an array can be defined and it is shown in

\begin{matrix} \forall e (i, j) ⟹ W_{i, j} = {[λ, η]}_{i, j} ⟺ i \in V, j \in V, i \neq j . \end{matrix}

(1)

4. Multicasting in Vehicular Ad Hoc Network (VANET)

In this work our main goal is to face with the main issues of multicast routing in the IEEE 802.11p environment, supplying services with a certain level of QoS. Due to the network nature and its main characteristics, it is important to design an easy, feasible, and robust protocol to use in order to avoid high level of messages overhead, considering the high impact of mobility in a VANET environment. Several approaches have been investigated, and we have found that a good mix among proactive and reactive approaches can give us the possibility to increase network performance. The multicast protocol is one of the key factors to reach our goals; however, it is also important to consider an efficient algorithm to find a good multicast tree. The algorithm allows us to find a feasible solution that belongs to the solution space, limited by the QoS constraints that we will better investigate in next sections. The one-to-many multicast paradigm has been considered in this work; however, the proposed protocol can be easily applied to many-to-many paradigm. In many-to-many case, we have to consider an external entity that has to manage the entire multicast group. Commonly, each multicast group has a Multicast Group Manager (MGM) that is associated with it. It provides management of multicast members that join and leave the group, as well as multicast tree maintenance, and avoids degradation of the multicast tree where possible. The MGM is elected at the multicast session start, and its tasks are associated with the RSU that allow connectivity to the multicast services that are considered to come from an external source. A more efficient policy, in terms of MGM election, will be adopted in further works to better search the MGM considering several parameters such as RSU placements, load status, available resources, and distance among member and service supplier.

4.1. Multicast Tree Definition

In order to minimize time and resource wastage and to reduce overhead, a trigger mechanism that can limit search process only to the involved area has been designed. Taking into account that each RSU covers a specific area, called management domain, which can be considered as a subgraph of the original network, the RSU acts as a CH for that management domain. Multicast algorithm is triggered only in this area to rearrange the multicast tree locally. At the end, the whole multicast tree shall be composed of several subtrees optimized for each cluster. A typical partitioned multicast tree, called T, is shown in Figure 3. Therefore, from graph theory, $V_{T}$ and $E_{T}$ are set of nodes and edges, respectively. In this way, the graph related to the network is $G_{T} (V_{T}, E_{T})$ . A multicast tree $(T)$ is also a subgraph of G and the relationship is shown in the following equation:

\begin{matrix} G_{T} 〈V_{T}, E_{T}〉 \subseteq G 〈V, E〉 s . t . V_{T} \in V, E_{T} \in E . \end{matrix}

(2)

Figure 3

Whole multicast tree partitioned with explicit management domains.

4.2. Multicast QoS Constraints

In this subsection, the considered QoS constraints are discussed in detail. In order to define them, it is important to define which kind of services we are going to distribute. Since we consider the distribution of multimedia services, such as video or audio services, we have to consider that they may require many resources to be distributed in an efficient manner. As we know, a network can be represented as a not oriented and weighted graph where the nodes are the routers, gateway, and so on and the connection between them is the edges of the graph. The weights can be dynamically allocated because they change in accordance with the traffic, network conditions, and loads. It is important to recall that in this work the one-to-many paradigm is adopted; thus, the set of the sources is composed only of the source s, $S = {s}$ . As stated before, the weight array is composed of two components: SNIR term called λ and a term related to the LDP called η. Consider

\begin{matrix} W_{i, j} = [λ_{i, j}, η_{i, j}] s . t . e (i, j) \in E_{T}, i \in V, j \in V, i \neq j . \end{matrix}

(3)

Now we define the interference term called SNIR in the following manner:

\begin{matrix} λ_{i, j} = \max_{h} (SNI R_{h}) = P_{t x} \sum_{h = 1}^{6} ‍ \frac{1}{P_{r x, h}}, \end{matrix}

(4)

where

P_{t x}

is the transmission power of the ith node and

P_{r x}

is the receiver power that can be considered as noise on the transmission.

The LDP, also depicted as $η_{i, j}$ , is the probability that a generic link can be persistent for a given period [13]. Its definition is herein shown:

\begin{matrix} η_{i, j} = \frac{1}{2} [1 + \erf (\frac{β_{th, i} - α 10 \log ((ν_{i} \cdot τ_{i}) / L)}{\sqrt{2} \cdot σ_{i}})], \end{matrix}

(5)

where

(i)

α is the evanescence exponent, which depends on the environment (generally $α = 4$ );

(ii)

$β_{th}$ is the sensitivity of the receiver which can be defined through a threshold of the attenuation level;

(iii)

ν is the relative speed of the vehicles;

(iv)

τ is the average time lag between two vehicles;

(v)

L is the number of considered lanes;

(vi)

σ is a fading factor.

In Figure 4, there is an example of metric evaluation to the multicast tree construction to distribute multicast services.

Figure 4

An example of metric evaluation to the multicast tree construction.

4.3. Building Network Topology Exploiting Wave Short Message Protocol (WSMP)

In order to maintain information about network topology, an active monitoring on nodes interconnection is made exploiting WSMP. In order to accomplish this task we add two new messages based on the data structure of the well known Wave Short Message (WSM) format. In particular, the data field of the messages has been used to disseminate information between the nodes. The implemented messages are herein illustrated.

4.4. Position Update Messages and Neighbor Discovery

Since in VANET nodes mobility is an important issue to address, it is needed to maintain updated the position of each vehicle in the network, because link quality may change rapidly. Neighbor discovery is an inner function that gives us the possibility to bring up information about the neighbor vehicles and checking its connectivity as well. These data are picked up by exploiting protocol messages called position update (PosUpdate). The knowledge of the neighbors is made with a classifier algorithm that is performed in order to define which node can be defined as neighbor. Neighbors knowledge can reduce protocol overhead because it is possible to define a neighbor area only for those nodes that are closer to the sender: in this way the total amount of protocol messages that will flood around the network can be heavily reduced. PosUpdate messages contain all information related to the position of a vehicle exploiting inner function of the OBU device that commonly supplies localization services. An example about neighbor discovery function is shown in Figure 5.

Figure 5

Neighbor discovery inner function flow chart.

4.5. Topology Update

Since the PosUpdate message helps us to identify the closer connections between nodes, in order to build the overall topology of the network in the RSU node another type of message has to be used. It is called topology update (topUpdate), which is generated by the vehicles and it is sent towards the local RSU that covers the area of interest of the vehicle that has changed its local topology. When a connection link changes in terms of quality, the related weights are updated and this information has to be sent to the RSU that keeps the knowledge of the low-layer network. RSU has the main goal to collect data, to better spread it along the network, exploiting routing algorithm. In order to evaluate the Interference Metric, the nodes have to perform a computation monitoring about the transmitted and received power on the available channels. In fact, in the topology update, information about metrics that are used to evaluate the feasibility of a link to be part of the multicast tree as chosen branch is also contained. A high level example of topology update procedure implementation is shown in Pseudocode 1.

Pseudocode 1

begin{algorithm}

WaveShortMessage *wsm ;

//Update Data about network topology grabbed by the OBU nodes

tsEdge appo;

senderId ≔ wsm->getSenderAddress();

if (find(MyId, sender) == True){

for { elements in edges } {

tsEdge tmp ≔ Assign current viewed element;

if (tmp.sourceNode == MyId)

and (tmp.destinationNode == senderId) $} {$

appo ≔ tmp;

break loop;

}

$} {$

appo.sourceNode ≔ MyId;

appo.destinationNode ≔ senderId;

$}$

//Update pont-to-point link exploiting Evaluator module

appo.distance ≔ Evaluator.getDistance(MyId, wsm);

appo.metrics(SNIR)

≔ getInterferenceMetric(MyId, Evaluator, appo.distance);

packetDelay ≔ evaluate e2e delay of the packet;

appo.metrics(DELAY) ≔ packetDelay;

//update local db with data in appo ;

updateTopologyData(appo,P2P);

//get new topology grabbing info from incoming message (wsm)

topoTemp ≔ getTopologyData(wsm);

//merge temp topology data with current topology knowledge}

updateTopologyData(topoTemp, ALL);

// Collecting Data on RSU Layer (Root of the multicast sub-tree) ;

∖end{algorithm}

In the algorithm depicted as pseudocode (see the Pseudocode 1), the tsEdge is a structure used to collect data about edges that compose the network. Moreover, we refer to an external module that we called Evaluator, which is used to perform computation for common function such as distance evaluation or SNIR evaluation among two nodes. This module is a inner module of the node and for this reason it is able to know the topology and its characteristics.

5. Protocol Overview: PAMTree

Multicast protocols commonly use two important messages in order to build and manage groups. These messages are known as multicast join and member leave. Some other messages have to be considered in order to perform multicast tree maintenance, such as prune messages. This last message is used to remove death branches of the multicast tree, performing a cleaning of data structure in the relayed nodes as well as the releasing of the allocated resources along those branches. Considering the proposed architecture, already shown in Figure 3, available multicast services are provided from external sources coming from the MCS; therefore, in order to distribute these contents in the VANET layer, we have to connect RSU to a gateway which is indicated with BGR. Since we want to optimize the data dissemination in the VANET layer and since the RSU has access to the external services exploiting their gateway, the resultant multicast tree, in this work, is composed of several levels where the first two levels can be easy found. The first level, which is the root of the multicast tree, is the source of the multicast services MCS; after that we have the BGR that supplies services to the involved RSU: in fact, only the RSUs that are involved in a particular multicast session require access to those services. Starting from the third level, we insert the RSUs that have some covered OBUs that belong to the considered multicast group. Since the RSUs are the CH of the subtree, its branches are built using the multicast algorithm, which is triggered by the root node of the subtree, and hence the CH. As it is easy to understand, we mean that we are going to generate several subtrees, achieving a multicast tree clustering, where the management of the entire multicast group is partitioned among the CH. This allows us to distribute the load of the maintenance among whole RSU that belongs to the considered sessions.

5.1. Road Side Unit (RSU) Tasks

In the designed protocol, the RSU and the OBU systems assume different behaviors in terms of session management. As declared, the local RSU can be viewed as a CH generating a subtree that covers a set of multicast destinations. The RSU has the main task to manage its cluster, allowing users to join at the services and managing resources allocation along the involved branches. A detailed state diagram is shown in Figure 6. Here it is possible to note a scheduler state that has the goal to schedule all further activities of the node, such as periodic messages or multicast tree maintenance activities. In the state diagram, shown in Figure 6, only activities related to the multicast session are reported but, as it is easy to understand, there are also some other background activities to consider, such as topology monitoring. The RSU has the task to manage the multicast sessions in terms of group management; this means that the RSU has to collect multicast join sending acknowledgments to the users that want to initiate a membership. The member leave is another important task to accomplish and this allows users to leave the multicast group, allowing RSU to send prune messages in order to release resources on those branches that are no more useful.

Figure 6

State diagram of Road Side Unit (RSU) in multicast join management.

5.2. On-Board Unit (OBU) Tasks

The OBU interfaces are installed on vehicles and they are used to communicate with other systems of the network. Regarding the multicast protocol, they can assume two different roles. The first one is the role of relay node: the OBU has to disseminate data following instructions sent by the reference RSU that, in a centralized way, performs routing decision, filling routing tables of the child nodes that belong to the multicast tree. Each relay node can receive data from only one upstream interface, but it can send information on several downstream interfaces. In the second case, the node assumes the role of destination: it is a final node of the multicast tree and it can receive data only from one upstream interface. Of course, this kind of consideration has to be made for all multicast sessions that are active on the considered node. Therefore, the routing decisions are made taking into account the multicast group ID (MGID) that is carried by the incoming message.

5.3. Protocol Messages

In this section an overview on protocol signaling packets is given. In particular, several messages are used to perform multicast in order to achieve a better management of resources, group life cycle, monitoring of the quality of the network in terms of multicast tree degradation, and so on. All these messages are supplied exploiting the Wave Short Message (WSM) format, in particular, exploiting the data field of the message. Let us introduce the used messages in the following sections.

5.4. Multicast Service Availability (MSA)

This is an important message used by the RSUs to notice that a new service is available. It is sent at the beginning of the sessions; then it is noticed in a periodic manner, to allow late users to join the multicast group. It is composed of several fields, the most important are the multicast group ID (MGID), the collected backwards path, the service type and a brief description of the service.

5.5. Multicast Join (MJ)

The MJ message is generated by the multicast destination that wants to participate in a particular multicast session identified by the multicast group ID. This message is built in response to a MSA reception. It travels along the backward path in order to reach the RSU that has generated the MSA message. The timing of the whole process is shown in Figure 7. The MJ message carries information about the node destination identification (Node ID) and the MGID. This information, once arrived to RSU, triggers the execution of the multicast algorithm in order to find the best path to reach destination along the multicast tree. Once the path is available, a multicast join acknowledgment (MJAck) is generated and it is sent towards the destination that has requested the join. Starting from this time, the data can be received by the destination because all downstream interfaces are informed about new branches. This allows destination to be covered by the multicast tree.

Figure 7

Timing diagram with the involved systems in the join process.

5.5.1. Multicast Join Acknowledgment (MJAck)

The MJAck (see Figure 9) is an acknowledgment message that is received by all nodes that are involved into distribution path, which is computed by the RSU node. Once received by a relay node, it checks if the multicast group entry is already present into the routing table: if an entry is present it checks if something is changed in the distribution path; otherwise it adds new entry into downstream interfaces and forwards the message in order to reach the final destination. This behaviour is summarized in Figure 8.

Figure 8

Flow chart of MJA in relay node.

Figure 9

Multicast join Ack format of the packet.

5.6. Multicast Member Leave (MML)

This message is generated by those nodes that want to leave from multicast sessions. Once this message is created it is sent along the reverse path in order to reach the RSU. In order to keep the optimality of the multicast tree, it is restructured and a multicast tree update message is sent to build a new multicast tree; the prune message is sent to those nodes that have to prune the oldest branches as well.

5.7. Multicast Tree Update (MTU)

It is created by the RSU because it aims to maintain the optimality of the multicast tree, avoiding packet loss due to change of links metrics. This suggests continuous monitoring of the network exploiting the already explained message topUpdate, in order to keep updated information in the topology stored in the RSU.

5.8. Automatic Prune Mechanism

For maintenance purpose, we decided to insert, into multicast tree management, also the possibility for the relay node to make an auto-delete of the unused branches. In fact, it is possible that some branches are not used at all. In order to release resources, in terms of memory allocation and bandwidth allocation, in some contexts it is possible to prune child branches. The auto-prune mechanism helps us to reduce protocol overhead, because it is not more necessary to send explicit messages to child interfaces.

6. Results

In order to test and validate proposed protocol several simulation campaigns have been performed involving several pc stations and spending a lot of time in campaigns planning.

The whole protocol has been designed and developed using OMNet++ framework [16] for simulation core, regarding VANET components and modules we exploit Veins [17], and, at last, for massive simulation and for traffic modelling we use the well known traffic generator SUMO [18]. In particular, for the simulation that we performed for this work we have taken as reference map some blocks of the Baltimore city as shown in Figure 10. As depicted there are four in-gates as well as four out-gates that guarantee continuous ingoing and outgoing vehicle flows. In order to demonstrate the goodness of our proposal several simulation campaigns have been carried out. In the first campaign, the protocol overhead has been measured in order to verify the scalability of the protocol when the number of joint members of the multicast session increases. As is shown in Figure 11, the trends demonstrate that, by increasing the number of members, the overhead decreases because new branches can be easy initialized, thanks to the distributed management of the multicast tree. It is also important to note that the mobility issues (such as the high speed of the vehicles) do not waste the overall performances of the whole tree. Observing Figure 11, at the beginning the overhead reaches a high level because many messages have to be managed such as joins and MSA messages used to notice the availability of the services along the network.

Figure 10

Map of Baltimore city, used for testing environment.

Figure 11

Overhead percentage versus number of multicast groups into a management domain of a single CH.

In the next simulation campaign, we verified the behaviour of the protocol in terms of waiting time for joining the multicast group; in particular we monitored how many time the join procedure takes to be accomplished. We test it by comparing our proposal with the MAODV protocol [19]. It is possible to note that our proposal performs better in terms of waiting time, allowing users to be served sooner than other protocols (see Figure 12). In this campaign, it has been found that the periodic message used to perform the topology update procedure is an important set-up parameter and it has to be chosen paying a lot of attention, because it can directly influence the protocol overhead and therefore the overall performance of the network. In the depicted figure (Figure 12) we show the join procedure time that it is measured from the start of the request until the first packet of the service is received.

Figure 12

Waiting time of the destination nodes to have access to the requested multicast service with PAMTree and MAODV protocol.

In the following simulation campaign, we have investigated the performance of the multicast protocol when the join requests are coming into the CH: this means that the local RSU has already noticed the availability of a multicast service and it starts to receive the join request, starting to build its multicast subtree. In Figure 13 the number of the not admitted requests is shown; it is important to note that this request is not admitted for this searching round, but it can be reached further with a huge knowledge of the topology. In fact, as shown during the simulation, some requests cannot be accepted, because due to QoS constraints, it is not possible to find a feasible path or it is not possible to find a path to distribute the data flow from the subtree root to the destination. However, with the incoming of the topology update messages, these requests can be satisfied and, as shown in Figure 13, at the end, all join requests can be accepted. Instead, regarding the number of the destinations that the RSU can reach, the related trend is shown in Figure 14: here the incoming requests are shown and it is possible to note some steps in the depicted increasing due to the periodic updating of the known topology.

Figure 13

Number of destination nodes versus simulation time.

Figure 14

Number of destination nodes versus simulation time.

In this last simulation campaign, the trend of the data flow received by the multicast destinations and the trend of the packet received by the involved relay nodes are shown in Figures 15 and 16. How it is possible to note the protocol, using the routing algorithm based on the interference and delay QoS metric, tries to involve a restricted number of nodes to perform the dissemination of the data flow. This is made because the wireless nature of the link is exploited and therefore it is possible to exploit the broadcast of the relay nodes in some restricted areas. Of course, it is important to recall that we have made this simulation in an urban environment where several obstacles can be found; therefore, in a real scenario it is important to consider in the path forwarding the presence of natural obstacles such as trees and buildings that can limit the coverage radius of a normal wireless transmission. However, in this case, the algorithm can take into consideration this event because it considers the power transmission in the SNIR evaluation, as shown in (4).

Figure 15

Total number of received packets per node versus simulation time.

Figure 16

Total number of packets of the relay nodes versus simulation time.

7. Conclusions and Future Works

In this work a novel multicast protocol for VANET network is illustrated; it is called PAMTree and it takes advantages from distributed management of the multicast trees. In fact, for each multicast tree, several subtrees are found and they are managed by the local RSU that can be seen as a CH, which has the main goal to disseminate on its child interfaces multicast data flow that is coming from external sources. In the simulation results section it has been demonstrated that the PAMTree protocol gives the possibility to reduce the waiting time for joining the multicast tree as well as to increase the average number of users that belong to a specific session. Moreover, the waiting time for joining a multicast group has been investigated and, in this case, good results have been found. In the future works a better and deeper analysis about other proposals will be made trying to identify the weakness of the approach proposing a better version of the protocol. In particular, we are approaching with the Steiner Tree Problem formulation because we are going to consider several strict QoS metrics. Moreover, considering the high impact of the mobility we are testing the subtrees degradation during the life cycle of the multicast session. First results have demonstrated that by increasing the dynamics of the multicast groups the degradation of the multicast tree is faster and we found several death branches that have to be removed considering a better prune policy. Another aspect that we want to consider is linked to the spread of electric vehicles. In this kind of scenario it would be useful to develop approaches based on energy savings of the mobile nodes and bioinspired computation for the dissemination of information, as seen in [20].

Footnotes

Conflict of Interests

The authors declare that there is no conflict of interests regarding the publication of this paper.

References

Zhou

Lee

Y.-Z.

Gerla

De Rango

Geo-LANMAR: a scalable routing protocol for ad hoc networks with group motion

Wireless Communications and Mobile Computing 2006 6 7 989 1002

2-s2.0-33751191158

10.1002/wcm.433

De Rango

Gerla

Marano

A scalable routing scheme with group motion support in large and dense wireless ad hoc networks

Computers and Electrical Engineering 2006 32 1–3 224 240

10.1016/j.compeleceng.2006.01.017

2-s2.0-33747486729

Chakraborty

A distant node based multicast routing protocol for sparse area vehicle to vehicle communication

IOSR Journal of Computer Engineering 2012 2 3 49 55

10.9790/0661-0234955

Jie

Huang

Wang

Yang

Chen

Opportunistic unicast and multicast routing protocol for VANET

Journal of Software Engineering and Applications 2013 6 6 319 327

10.4236/jsea.2013.66040

Sebastian

Tang

Feng

Looi

Context-aware multicast protocol for emergency message dissemination in vehicular networks

International Journal of Vehicular Technology 2012 2012 14

905396

10.1155/2012/905396

2-s2.0-84873809786

Selvam

R. P.

Palanisamy

An efficient cluster based approach for multi-source multicast routing protocol in mobile ad-hoc networks

International Journal of Computer Networks and Communications 2011 3 1 154

De Rango

Tropea

Santamaria

A. F.

Marano

Multicast QoS core-based tree routing protocol and genetic algorithm over an HAP-satellite architecture

IEEE Transactions on Vehicular Technology 2009 58 8 4447 4461

10.1109/tvt.2009.2019281

2-s2.0-70350231422

De Rango

Tropea

Santamaria

Marano

An enhanced QoS CBT multicast routing protocol based on genetic algorithm in a hybrid HAP-Satellite system

Computer Communication Journal 2007 30 13 3126 3143

Liu

Gupta

A modified shared-tree multicast routing protocol in ad hoc network

Journal of Computing and Information Technology 2005 13 3 177 194

10.2498/cit.2005.03.02

10.

Sebastian

Tang

Feng

Looi

A multicast routing scheme for efficient safety message dissemination in VANET

Proceedings of the IEEE Wireless Communications and Networking Conference (WCNC '10)

April 2010

Sydney, Austria

10.1109/wcnc.2010.5506245

2-s2.0-77955045403

11.

Belghitha

Aissab

Ben Mnaouer

A novel multicast algorithm for collaborative multimedia applications in heterogeneous networks

Proceedings of the 9th International Conference on Mobile Web Information Systems (MobiWIS '12)

2012

Niagara Falls, Canada

12.

Chang

I.-C.

Hsieh

C.-S.

Chu

C.-H.

HSMM: hierarchical synchronized multimedia multicast for heterogeneous mobile networks

Tamkang Journal of Science and Engineering 2010 13 1 39 51

2-s2.0-77951012295

13.

Fazio

De Rango

Sottile

Santamaria

A. F.

Routing optimization in vehicular networks: a new approach based on multiobjective metrics and minimum spanning tree

International Journal of Distributed Sensor Networks 2013 2013 13

598675

10.1155/2013/598675

2-s2.0-84893902773

14.

Guerriero

De Rango

Marano

Bruno

A biobjective optimization model for routing in mobile ad hoc networks

Applied Mathematical Modelling 2009 33 3 1493 1512

10.1016/j.apm.2008.02.003

MR2478577

2-s2.0-55549128241

15.

Cassano

Florio

De Rango

Marano

A performance comparison between ROC-RSSI and trilateration localization techniques for WPAN sensor networks in a real outdoor testbed

Proceedings of the Wireless Telecommunications Symposium (WTS '09)

April 2009

Prague, Czech Republic

1 8

10.1109/wts.2009.5068988

2-s2.0-77951492332

16.

Varga

Hornig

An overview of the OMNeT++ simulation environment

Proceedings of the 1st International Conference on Simulation Tools and Techniques for Communications, Networks and Systems Workshops

March 2008

17.

Sommer

German

Dressler

Bidirectionally coupled network and road traffic simulation for improved IVC analysis

IEEE Transactions on Mobile Computing 2011 10 1 3 15

10.1109/tmc.2010.133

2-s2.0-84891005070

18.

Krajzewicz

Erdmann

Behrisch

Bieker

Recent development and applications of sumo—simulation of urban mobility

International Journal On Advances in Systems and Measurements 2012 5 3-4 128 138

19.

Dharmaraju

Karir

Baras

J. S.

Das

An implementation study of multicast extensions of AODV

Proceedings of the International Symposium on Performance Evaluation of Computer and Telecommunication Systems (SPECTS '03)

July 2003

Montreal, Canada

20.

De Rango

Lonetti

Marano

MEA-DSR: a multipath energy-aware routing protocol for wireless Ad Hoc Networks

Advances in Ad Hoc Networking 2008 265 215 225

10.1007/978-0-387-09490-8_19

2-s2.0-51149083505