Research Article - Biomedical Research (2016) Computational Life Sciences and Smarter Technological Advancement

Mesh routers based routing for saving human life in vehicular adhoc network

¹Department of Telecommunication Engineering, Sathyabama University, Chennai, India

²Adhiparasakthi Engineering College, Melmaruvathur, Kanchipuram District, Tamil Nadu, India

*Corresponding Author:

G Mary Valantina
Department of Telecommunication Engineering, Sathyabama University, India

Accepted on August 02, 2016

Abstract

Saving human life is the most important task than anything else. Day to day life faces loss of life due to accidents which can be avoided. Biologically inspired communication on road could save lots of life. A mesh sensor which is developed based on a combination of mesh router and wireless sensor can be used for communication between vehicles in a better way and could save human life. Vehicular Ad hoc Network (Vanet) enhances safety; comfort and entertainment services to human life.Vanet are a super class of Mobile Adhoc Network (MANET) with some unique characteristics. To disseminate traffic warning message to various receivers a multihop broadcast protocol is required. While doing this broadcast message overhead reduction is an important issue since it could directly have an effect on the packet collision probability and MAC layer contention time at each node. Already for VANETs there are some broadcast protocols in existence. But, most of them are designed under the assumption of the presence of the global positioning system (GPS).This paper proposes a broadcast protocol which does not require position information. This protocol includes mesh routers in the network that reduces the broadcast storm problem and increases the dissemination ratio. The efficiency of the proposed protocol is proved over some of the existing protocols in terms of Packet dissemination ratio, End to end delay, Number of packets broadcast and Mac overhead per node.

Keywords

Human life, Collision probability, Broadcast storm, Mesh routers, GPS.

Introduction

Rapid growth in the automobile industry makes a way for communication between vehicles which leads to Intelligent transportation system (ITS). More number of mobile users which is capable of acting as standalone devices are deployed to handle [1] some situations like establishing communication for emergency situations, rescue operations, natural calamities and secured services networks [2]. VANETs are super class of MANETs with some distinctive characteristics. Moving vehicles share information among them confined to the road infrastructure. A vehicle mounted with onboard communication unit can act as a node in the vehicular adhoc network. An accurate estimate of vehicle’s position can be made available through GPS systems or on-board communication unit. Communication in vanets can happen between the vehicles on road or between the vehicles and the road side units [3]. Figure 1 shows the connected car scenario. Communication between Vehicles requesting for nearest gas station, nearby parking lot, restaurant, hospital, multimedia exchange etc. This type of application mostly uses point to point routing protocol. Vehicle to Roadside infrastructure Communication based applications, such as the over speed warning, curve warning, change in the lane warning also uses point to point as well as broadcasting [4-6]. Emergency related messages like a sudden change in diversion of road due to some blockage in the road, accidents, sudden protests, bad weather etc will be broadcasted to all the approaching vehicles [7,8], Both in academia and industry, routing is the current area of research in VANET. Due to frequently disconnecting link nature of the nodes, there arises a need for a routing protocol which provides enhanced information delivery without route breakage [9-13].

Figure 1. Communication in vanets, V2V: Vehicle to Vehicle communication, V2R: Vehicle to Roadside unit communication.

Evaluation of Broadcasting Protocols

Before designing any routing protocol the knowledge about the existing protocol is necessary which will be useful in designing the new one. The existing broadcasting protocols are shown in Figure 2.

Figure 2. Broadcasting protocols of vanet.

To analyse our protocol some of the existing protocols performance are also studied and compared with the proposed one.

Simple flooding

The basic phenomenon for all types of communication [14] in ad hoc networks is achieved by means of broadcasting. The fundamental method of broadcasting is flooding. A typical scenario is shown in Figure 3.

Figure 3. Broadcasting in vanets by simple flooding.

In Figure 3 the vehicle senses the event of collision further transmits to forthcoming vehicle. Upon receiving a broadcast packet, all nodes tries to find out if it has transmitted the packet before. If it understands the packet is not transmitted, then it is resend. Therefore the flooding process stops only after all the vehicles in the network get that packet. Active participation of all the vehicles makes this technique suffer from the problem of Broadcast Storm. Due to repeated transmission the messages can become duplicated in the network further increasing the load on the networks and thereby it requires a method to eradicate that makes the processing complexity high [15,16]. Due to this there occurs a high contention in the MAC layer when trying to send the message to a longer distance because all the neighbouring nodes after receiving the message it tries to rebroadcast the message leads to packet collision and packet gets lost.

Qayyum et al. have a proposed a broadcasting protocol based on multipoint relay (MPR) [17]. Here in this method each and every node selects a set of neighbour nodes as a relay node. Only the node which is selected as the MPR node will forward the message. The nodes which are not in the group of MPR set will not be used for retransmitting the messages. Like this the retransmission of messages are reduced and it provides an efficient method for broadcasting mechanism. The protocol for MPR system is that, first an empty MPR set is assumed then a set of nodes which are the neighbour nodes to next hop neighbour are selected as MPR nodes and if they are not covering the next hop neighbour nodes then the number of nodes is computed. A node which covers the high vicinity of all nodes in the next hop neighbour is included in the MPR set. Therefore instead all the nodes transmitting the messages only the particular set of nodes are transmitting the messages which reduces the network overhead. The disadvantage of this protocol is that it does not consider the vehicle velocity into picture so the node selected as MPR may fail to receive the data packet.

Weighted p-persistence, slotted 1-persistence

Wisitpongphan and Tonguz have proposed a broadcasting mechanism based on probability and time based methods [18,19]. This method insists that all the nodes retransmit with probability 1. In this protocol a probability of p_ij is assigned to node j and it sends with that probability after receiving a packet from node i. In the weighted p-persistence scheme, upon receiving a packet from node i, node j checks the packet ID and rebroadcasts [19] with probability if the node receives the packet for the first time otherwise, the node discards the packet. Denoting the relative distance between nodes i and j by D_ij and the average transmission range by R, the forwarding probability p_ij is calculated on a per packet basis using

In the slotted 1-persistence scheme, upon receiving a packet, a node checks the packet ID and rebroadcasts with probability 1 at the assigned time slot T_Sij if the node receives the packet for the first time and has not received any duplicates before its assigned time slot; otherwise, the node discards the packet. Given the relative distance between nodes i and j, D_ij, and the predetermined number of slots Ns, T_Sij is calculated as

Related Woks

An interesting broadcasting protocol named stochastic broadcast for VANET [20] that may be a combination of distance-based broadcast and stochastic broadcast. Within the paper, each node should decide their own probability for rebroadcasting (the likelihood of being a relay). The paper considered 2 ways one is fixed; another dynamically determined consistent with a one-hop distance. That analysis has the following merits. First, each node determines a probability by itself, which suggests transmission, isn't used except broadcasting and also the relay choice method is significantly safer while not transfer in impact to the performance. This eliminates privacy problems and provides measurability. Second, it uses a percolation study to estimate ultimate connectivity property and calculate the optimum node density to make a connected graph. However, this paper doesn't mention concerning dynamic adjustment of the probability consistent with a network condition changes. This paper, utilizes RSUs to contend with the fast fragmented network. Density-aware reliable broadcasting protocol doesn't need position of the nodes. By beaconing DECA uses only local density data of I-hop neighbours [21]. A node that has the very best local density data is chosen as neighbour to be ensuing beam node. All Other nodes arbitrarily set their waiting timeout. Before the timeout expiration if they are doing not hear anyone rebroadcast the message, they'll rebroadcast the message. The identifiers of the received broadcast messages are enclosed in periodic beacons in order that a node will discover its neighbours, that haven't received the messages and consequently rebroadcast the messages for those neighbours.

Position-aware reliable broadcasting protocol uses adaptive beacon [22] to bring on neighbours’ position and velocity. Once nodes wish to broadcast messages, they'll choose the neighbours in most accepted distance to rebroadcast the message. Waiting timeout is calculated based on the distance between node and precursor node. The chosen node can rebroadcast the message straightaway. Just in case the chosen nodes don't rebroadcast the message, different nodes that have set waiting timeout since they received message can do that task instead the popular distance is predicated on the distance between nodes and selector nodes. POCA conjointly piggybacks the message symbol to beacon to handle intermittent property. BDSC protocol [23] consists of 3 operation layers as given. The primary layer is that the “HELLO packets exchange” layer that infrequently builds and exchanges the HELLO packets. The second is that the "Link Quality Estimation" layer that outputs quantitative estimations portraying the forward link qualities of a given node with all single-hop neighboring nodes. During emergency event, the "Link Selection" layer qualifies/disqualifies links, and thus relay nodes, based on a pre-defined criterion. The thought of link choice criterion adheres to the quantitative values obtained at the “Link Quality Estimation” layer. The “Link Quality Estimation” and "Link Selection" layers are often placed as sub-layers of the network layer consistent with the well-known OSI communication layers mode.

Mesh Deployment in the Network

Mesh routers constantly monitors the network activity and maintains lists of other devices in their locality [2]. If it finds a potential node, it broadcasts its address and relevant details. The mesh routers in the vicinity will receive the broadcast, and change their own lists. Mesh routers constantly analyses the network and the link quality to dynamically construct a best display of paths. The routers find out one another, and establish optimal path selection quickly to the gateways. Each and every mesh routers automatically monitors and adjusts power, delivers maximum capacity that enhances network reliability. If a node broadcasts a request to send data to a particular location, and a router has the details of the receiving node with its list of active devices, then it will compute the path to the destination. If it cannot find a direct path between source and destination, the data is transmitted to another router till a path is found.

Each mesh routers determine the presence of other routers by the following analysis

If M1(x_m1,y_m1) and M2(x_m2,y_m2) are the coordinates of mesh router.

let M1 and M2 are the foci of ellipse given by

→ (1)

Where ϕ, a, b, A, B are given by

(2)

(3)

(4)

S=sizing factor obtained by statistical analysis from the city road map.

(5)

(6)

(7)

(8)

Where X_max, X_min, Y_max, Y_min gives the four corners of the area in which the mesh routers are present as shown in Figure 4.

Figure 4. Area concerned with mesh routers.

The algorithm of M-Broad protocol is shown below and the working of the proposed protocol is as follows.

Algorithm for M-Broad

Initialize

V={V1,V2,……..Vn}//vehicles ID.

S={S₁,S₂,S₃…….S_n}//vehicles speed.

l={l₁,l₂,l₃………l_n}//vehicles location

Cd={X_max, X_min, Y_max, Y_min}//coverage distance

C=counter value

N_T=Node transmitting data.

D_n=Data from nodes other than the mesh router.

D_MR=Data from mesh router.

Begin

For i=1 to n

For j=I to n

C=Cd

Start: If D_n≠D_MRj then

NT=D_n

Increment i

Else

N_T=D_MRj

Decrement c

If C=0 then

Increment I, increment j

N_T=D_n, Go to Start

Else

N_T=D_MRj

End if

End for

End for

End

Since mesh routers are always compatible to their background, the network created is very strong, has greater bandwidth and highly reliable. There are mobile mesh routers also in existence normally a dedicated mesh router will not be mobile. Mostly wireless access points seen in the network are mesh routers only, possibly can be used to create geographically large wireless networks. The advantages of mesh routers are improvisation in throughput of network by choosing optimal routing paths, Improves network performance by rerouting traffic in the occurrence of any interference, or any other disruptions in the network, Supports client mobility without the need for special client hardware, software, or network reconfigurations.

Mesh routers are deployed in the network, as shown in Figure 4. The Algorithm of M-Broad protocol is shown in Figure 5 and the working of the proposed protocol is as follows .When a vehicle encounters accident it floods the message in the network. The nodes start receiving the messages and thereby it reaches the mesh router also. From that moment onwards the mesh routers takes in charge of disseminating the messages. The mesh routers are capable of knowing the existence of other mesh routers in their vicinity also. So it sets the coverage distance as the timing parameter to the counter. The counter decreases the value once the value reaches the zero value the mesh router x stops sending and by this time the next mesh router will take the position to transmit the messages to the forthcoming vehicles. By this way the overhead in the network is greatly reduced. The mesh router does not require any predetermined path between them. Mesh routers are included in the network and they act in real time to find an active route. It dynamically notes down the activity of the network and monitor the nearby devices. Even mobile mesh routers has come into existence which can work at the speed of vehicle.

Figure 5. Mesh deployment in the network.

Simulation

Simulation is done in NS-2 simulator. The NS-2 accepts the input file that has the information of each node and the packets generated by each node. The time information of the packets is also present in that source file. The simulation parameter values are shown in Table 1.

Table 1. Simulation parameters.

Performance Metrics

There are a number of performance metrics such as packet error, packet loss, Network overhead, packet delivery ratios, end-to-end delay, normalized network load [20], which are typically more common for an evaluation of network performance.

Packet dissemination ratio

Figure 6 shows the Packet dissemination ratio for number of nodes. In flooding, the dissemination ratio decreases due to fact that many nodes try to broadcast at the same time and this introduces collisions and a drop in packet dissemination ratio. MPR broadcast provides an efficient mechanism for disseminating messages by reducing the number of transmissions as the node density increases Packet Dissemination Ratio decreases drastically for flooding.

Figure 6. Packet dissemination ratio for number of nodes.

This is caused due to the broadcast storm problems that are present in flooding. In a high-density network the weighted ppersistence and slotted 1-persistence attain improved performance than flooding .It can be observed that for high density network flooding performs poorly. Same situation happens in the slotted 1-persistence scheme due to the fact that the node rebroadcasts with probability 1for an assigned time slot. Therefore, the slotted 1-persistence scheme works similar to the flooding in sparse networks. A node rebroadcasts the packet immediately after the reception of the data packet. Hence, the slotted 1-persistence scheme works exactly same to the flooding. As for the weighted p-persistence and slotted 1- persistence, they behave poor performance in a sparse network because of probabilistic broadcasting. Whereas the mesh router tries to minimize the hop count to reach a receiver. It is not transmitting all at the same time so no collision and packets are correctly received by the receivers. This eventfully increases the packet delivery ratio of the proposed protocol.

Number of packets broadcast

Figure 7 shows the number of messages broadcast for number of nodes. From the figure, When the density of the network increases flooding produces more number of redundant broadcast messages which leads to packet collision.

Figure 7. Number of broadcast for number of nodes.

The Weighted p-persistence and Slotted 1-persistence attains better performance than flooding because it employs a probabilistic method to decrease the redundant rebroadcast. In MPR only selected nodes relay the broadcast so its performance is also better than flooding. Finally M-Broad shows the highest performance because not all the nodes broadcast only the mesh routers broadcast the message. Therefore redundant broadcast is greatly reduced.

End-to-end delay

End-to-end delay is an important parameter to evaluate a broadcast protocol’s performance. Figure 8 shows end-to-end delay for number of nodes.

Figure 8. End to end delay for number of nodes.

The message has to be given to all the concerned receivers within the given fixed time. Therefore the end-to-end delay computation, takes into account only the number of packets delivered successfully. Therefore in flooding it is high because it encounters many redundant rebroadcast. From the figure we conclude that in flooding, the delay increases as the node density increases because of broadcast storm. Increase in the number of nodes increases the rebroadcast also increases therefore too many packets in the network which causes collision that leads to packet loss. Too many rebroadcast increases the contention in the MAC layer. The weighted ppersistence and slotted 1-persistence shows less delay than flooding. As the quantity of nodes raise the weighted ppersistence and slotted 1-persistence shows higher delay because for high density network it behaves like flooding itself. MPR shows the least delay as it selects the relay node to be the distant node. Comparatively M-Broad protocol reduces the delay by reducing the unnecessary rebroadcast by setting the fact that not all the nodes in the network rebroadcast only the mesh router is going to broadcast thereby reducing the number of rebroadcast thereby decreasing the contention time that occurs in the MAC layer.

From the results we can infer that every existing broadcasting protocol has their advantages and disadvantages. Flooding cannot be applied to a network which has high density of nodes due to the fact of Broadcast storm in flooding causes high overhead in the network. Even if the rate of broadcast is reduced MPR did not achieve a high dissemination ratio. This happens mainly due to two reasons. First and foremost reason is that a sender node generally selects the farthest node as a relay node. However, in a fading channel, the farthest node constantly fails to receive the broadcast packet. The second reason is that in MPR, the node mobility is not considered in the relay node selection. Therefore due to the vehicle movement a packet loss occurs at the selected relay node. Figure 9 shows MAC Overhead per packet for various nodes MAC overhead is basically calculated as the number of sent or received MAC layer frames [24]. As shown in Figure 9 the MBroad protocol significantly keeps the MAC overhead at satisfactory level and improves the reliability.

Figure 9. MAC overhead per packet for various nodes.

Conclusion

In this article, a mesh sensor based routing for enhancing the communication between the vehicles thereby saving human life is developed. This mesh sensor routing developed using a protocol called M-Broad a convenient and flexible multi-hop broadcast protocol for vehicular ad hoc networks is proposed. Logical concern about the requirements and constraints imposed by applications, communication, density and vehicular traffic flow are essential for designing a broadcasting protocol Instead of all the nodes acting as a relay nodes MBroad takes the advantage of mesh routers which are in existence. Mesh routers dynamically notes down the activity of the network and monitor the nearby devices. Experiments, confirmed the advantage of M-Broad over other existing alternatives.

Acknowledgment

The authors thank the management of Sathyabama University, Chennai, India, for providing the necessary facilities and encouragement to carry out this work.

References

1. Amusa KA,Nuga OO, Adetomi AA. Design of SMS enabled car security system. Transnat J Sci Technol 2012; 2: 42-50.
2. Valantina GM,Jayashri S. A Novel approach to efficient and reliable Routing in VANETS. 2014 Fifth International Conference on the Applications of the Digital  Information and Web Technologies, Banglore, India.
3. Korkmaz G, Ekici E, Ozguner F. Black-Burst-Based Multihop Broadcast Protocols for Vehicular Networks. IEEE Transact Vehicular Technol 2007; 56: 3159-3167.
4. Al-Sultan S, Al-Doori MM, Al-Bayatti, Zedan H. A comprehensive survey on vehicular Ad Hoc network. J Network Comput App 2014; 37: 380-392.
5. Liu J, Wan J, Wang Q, Deng P, Zhou K, Qiao Y. A survey on position-based routing for vehicular ad hoc networks. Telecom Sys2015; 62: 15-30.
6. Djahel S, Doolan R, Munten GM, Murphy J. A communications-oriented perspective on traffic management systems for smart cities: challenges and innovative approaches. Communicat Surveys Tutorials 2015; 17: 125-151.
7. Omprakash K, Kumar S. Cache agent-based geocasting in VANETs. Int J Informa Communicat Technol2015; 7: 562-584.
8. Liang W, Li Z, Zhang H, Wang S, Bie R. Vehicular ad hoc networks: architectures, research issues, methodologies, challenges, and trends. Int J Distributed Sensor Networks 2015.
9. Di Pietroa R, Guarinoa S, Verdeb NV, Domingo-Ferrerc J.Security in wireless ad-hoc networks-a survey.Comput Communicat 2014; 51: 1-20.
10. Cai X, He Y, Zhao C, Zhu L, Li C. LSGO: link state aware geographic opportunistic routing protocol for VANETs. EURASIP J Wireless Communicat Networking 2014.
11. Jian-Ming C, Chin-Feng L, Han-Chieh C, Zhu R. An energy-efficient geographic routing protocol design in vehicular ad-hoc network. Computing 2014; 96: 119-131.
12. Torrent-Moreno M, Santi P, Hartenstein K. Distributed Fair Transmit Power Adjustment for Vehicular Ad Hoc Networks, Sensor and Ad Hoc Communications and Networks. Reston 2006.
13. Bononi L, Di Felice M, Pizzi S. DBA-MAC: Dynamic Backbone-Assisted Medium Access Control Protocol for Efficient Broadcast in VANETs. J Interconnection Networks 2009; 10: 321-344.
14. Qayyum A, Viennot L, Laouiti A. Multipoint Relaying for Flooding Broad-cast Messages in Mobile Wireless Networks. Proc. 35th Annual Hawaii Intl. Conf. on System Sciences, Big Island, Hawaii, 2002.
15. Duddalwar P, Deshmukh A, Dorle SS. Comparative Study of Routing Protocols in Vehicular Ad-Hoc Networks (VANETS). Int J Adv Studies 2015; 4: 9-14.
16. Yousef-Awwad D, Chih-Wei Y, Stojmenovic I. Forwarding methods in data dissemination and routing protocols for vehicular ad hoc networks. Network, IEEE 2013; 23: 74-79.
17. Wisitpongphan N, Tonguz KO. Broadcast Storm Mitigation Techniques in Vehicular Ad Hoc Networks. IEEE Wireless Communications 2007; 14: 84-94.
18. Kan Z, Zheng Q, Chatzimisios P, Xiang W, Zhou Y. Heterogeneous Vehicular Networking: A Survey on Architecture, Challenges, and Solutions. Communications Surveys Tutorials, IEEE 2015; 17: 2377-2396.
19. Ho YH, Ho AH, Hua KA. Routing protocols for inter-vehicular networks: a comparative study in highmobility and large obstacles environments. Comput Communicat 2008; 31: 2767-2780.
20. Slavik M, Mahgoub I. Stochastic broadcast for VANET, 7th IEEE Consumer Commun Netw Conf 2010.
21. Na N, Rojviboonchai K. DECA: density-aware reliable broadcasting in vehicular ad hoc networks. Electrical Engineering/Electronics Computer Telecommunications and Information Technology (ECTI-CON), 2010 International Conference on. IEEE, 2010.
22. Na K, Rojviboonchai K. POCA: Position-Aware Reliable Broadcasting in Vehicular Ad-Hoc Networks. Proceedings of 2010 Second Asia-Pacific Conference on Information Processing (APCIP 2010). 2010.
23. Rehmana OMH, Bourdoucenb H, Ould-Khaouac M. Forward Link Quality Estimation in VANETs for Sender-Oriented Alert Messages Broadcast. J Network Compute App 2015; 58: 23-41.
24. Wu C, Kumekawa K, Kato T. A Novel Multi-hop Broadcast Protocol for Vehicular Safety Applications. J Informa Process 2010; 18: 930-944.