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

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).

OPEN IN VIEWER

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.

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.

OPEN IN VIEWER

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,

OPEN IN VIEWER

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 ) ∈ V , such that i ≠ j and ∃ e ( i , j ) ∈ E in terms of weight; an array can be defined and it is shown in

∀ e i , j ⟹ W i , j = λ , η i , j ⟺ i ∈ V , j ∈ V , i ≠ j .

(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:

G T V T , E T ⊆ G V , E s . t . V T ∈ V , E T ∈ E .

(2)

OPEN IN VIEWER

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

W i , j = λ i , j , η i , j s . t . e i , j ∈ E T , i ∈ V , j ∈ V , i ≠ j .

(3)

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

λ i , j = max ⁡ h SNI R h = P t x ∑ h = 1 6 ‍ 1 P r x , h ,

(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:

η i , j = 1 2 1 + erf ⁡ β th , i - α 10 log ⁡ ( ν i · τ i ) / L 2 · σ i ,

(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.

OPEN IN VIEWER

Figure 4

An example of metric evaluation to the multicast tree construction.

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.

OPEN IN VIEWER

Figure 5

Neighbor discovery inner function flow chart.

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.

OPEN IN VIEWER

Figure 6

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

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.

OPEN IN VIEWER

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.

OPEN IN VIEWER

Figure 8

Flow chart of MJA in relay node.

OPEN IN VIEWER

Figure 9

Multicast join Ack format of the packet.

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.

OPEN IN VIEWER

Figure 10

Map of Baltimore city, used for testing environment.

OPEN IN VIEWER

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.

OPEN IN VIEWER

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.

OPEN IN VIEWER

Figure 13

Number of destination nodes versus simulation time.

OPEN IN VIEWER

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).

OPEN IN VIEWER

Figure 15

Total number of received packets per node versus simulation time.

OPEN IN VIEWER

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].