6.Self-pruning broadcasting for information dissemination

International Journal of Emerging Researches in Engineering Science and Technology, Volume 1, Issue 1 November’14
Self-pruning broadcasting for information dissemination in
vehicular ad hoc networks
Sabaresan V
Department Of Computer Science and Engineering
Assistant Professor, Kalaivani College of Technology
Coimbatore-641 105, Tamil Nadu, India
[email protected]
Abstract- Vehicular Ad-hoc Networks (VANETs) is a sub division schemes [3], information about neighbors is not necessary to be
of Mobile Ad-hoc Networks (MANETs) and VANETs have extra maintained by the each node but it is very complex to develop
dynamic nature compared to MANETs due to the fast moving analytical models of these protocols. In adaptive and
nature of the vehicles. During the last few years, several decentralized approach make a decision based on the
broadcasting scheme, such as counter and distance based scheme rebroadcasting decision algorithm and based on this approach,
has been adopted. In probabilistic based schemes, information each node can dynamically regulate the values of its limited
about neighbors need not be maintained by the each node. To
factor using information from nearest nodes. This paper focuses
Maintaining a good latency and reach-ability while minimizing
redundant messages is a difficult task. In this paper, we propose on probabilistic based broadcasting schemes and introduces an
self pruning broadcasting model to deal with the information enhanced scheme, called Scalable Broadcasting Algorithm
dissemination problem in VANETs. Simulations results show that (SBA) with timer suppression mechanism to reduce the amount
the proposed Scalable Broadcasting Algorithm (SBA) with timer of any extra efforts. SBA [4] is an instance of self-pruning
suppression mechanisms have a better performance over protocol that sets the broadcast timer of a node based on the
probabilistic based schemes.
number of neighbours it has. In particular, this research is
Keywords: VANETs/MANETs, information dissemination,
broadcasting protocols, Scalable broadcasting algorithm.
I. INTRODUCTION
The main aim of the inter vehicle communication is to
increase the vehicle safety or driver comfort by relaying
necessary information from vehicle to vehicle. Two types of
applications can be distinguished, comfort applications and
safety applications. The comfort application can improve
passengers comfort by updating them about route optimization
and increase the traffic efficiency e.g., weather information, gas
station or other location, etc. Whereas safety applications
increase the safety of passengers by exchanging safety data via
inter vehicle communication [1]. For example, a vehicle
detecting a freezing road could inform other vehicles intending
to use the affected route. Thus drivers could be notified that
they are proceeding toward a spot where an accident has
occurred.
VANET has unique characteristics like high mobility with
the constraint of road topology, limitless network size,
communications support that make different it from MANETs
[2]. Therefore, more and more researchers have concentrated on
proposing suitable broadcasting protocols to deal with the
highly dynamic nature (such as high dynamic topology
supports, mobility modelling and frequently connected) of
VANET. Broadcasting protocols may perform in a different
way than MANET due to the following reasons. Since vehicles
are treated as VANETs nodes, these entities can move too
quickly as compared to normal MANETs nodes. In VANETs,
the network topology changes frequently since vehicles can
regularly leave and join the network.
Information dissemination in VANETs can be performed
based on several broadcasting schemes. In Probabilistic based
ISSN: 2393-9184
encouraged by Scalable Broadcasting Algorithm (SBA) with
timer suppression mechanisms to prioritize broadcasting of
messages such that node with most exposed neighbours
rebroadcast first [5].Simulations are conducted and obtained
results show that SBA with simple timer suppression
mechanisms outperforms the major probabilistic based
broadcasting schemes.
The rest of this paper is prepared as follows. Section II
presents a categorization of existing broadcasting protocols with
a brief account of most important approaches. Section III
presents the proposed broadcasting method. Performance
analysis of SBA with timer suppression mechanism using
simulation is presented in this section IV. Conclusions are
presented in Section V.
II. RELATED WORKS
Broadcasting is one of the fundamental primitive in network
communication. Its goal is to transmit a message from one node
of the network called the source to all other nodes. Remote nodes
get the source message via intermediate nodes along paths in the
networks. A broadcasting protocol for a given network prescribes
in which steps which nodes transmit. Number of broadcasting
protocols for information dissemination has been recently
proposed.
Proba
bilisti
c
Broad
castin
g
Proto
col
Determi
Distan
ce
Based
Location
Based
Count
er
Based
Ad-hoc
Cluster
Based
Simpl
Fig. 1. Broadcasting methods e
floodi
ng
Based
nistic
36
International Journal of Emerging Researches in Engineering Science and Technology, Volume 1, Issue 1 November’14
These broadcasting protocols mainly classified into two
types: probabilistic and deterministic protocol. The first
approach is probabilistic broadcast [6]. In a probabilistic
broadcast
protocol, the forwarding set is selected in a
probabilistic approach. At what time a node receives a broadcast
message, it will forward the message with several probability.
The forwarding probability is also statically or dynamically
computed locally at each node based on each node‟s
surroundings. A probabilistic broadcast protocol usually causes
unnecessary retransmissions, which incurs relatively additional
overhead and possible packet collisions. Proper use of a
probabilistic broadcasting method can reduce the number of
rebroadcasts, and thus reduce the chance of contention and
collision among neighboring nodes.
The probabilistic broadcasting protocols are further classified
into counter, distance and location based. In counter based
broadcasting, a message will be rebroadcast no more than if the
amount of received copies at a host is smaller than a threshold
after RDT [7].when a broadcast begins, some nodes will
rebroadcast the same packet, and so one node will receive the
same packet a number of times. Every node will count the
number of time that a packet is received during a random
period, and then nodes will compare the number with
predetermined thresholds to decide whether rebroadcast the
same packet or drop. The advantage of this scheme is that nodes
don‟t need to identify the structure of the network and don‟t
need to exchange neighbor‟s knowledge, which suits VANETs
temporary environment. But if counter based scheme is used in
VANTEs, every node should wait a period and the delay will be
increased; on the other hand, the threshold relates to the density
network and it is difficult to select a suitable threshold value.
The counter based scheme alone cannot effectively prevent
packet collisions which frequently occur in dense VANETs.
Distance based scheme is a broadcast scheme that uses the
distance between sender and receiver to make the decision
whether to rebroadcast or not. The signal power from the packet
received is a parameter that can be used to calculate the
distance. GPS can also be used for that purpose. In [8], authors
have described a distance based scheme for broadcasting in ad
hoc networks. In this scheme, nodes use the relative distance to
make the decision. The longer the distance between receiving
nodes whose distances to the sender are bigger than the
threshold will rebroadcast the received packets.
Previous we have used the number of times that a broadcast
message has been heard or the distances to transfer hosts as our
rebroadcasting metrics. If we can obtain the locations of those
broadcasting hosts, it is even possible to estimate the additional
coverage more accurately. Such an approach may be supported
by positioning devices such as receivers. We note that location
information was also used to make easy route discovery in a
MANET. In [9], authors have described a location based
scheme for broadcasting in ad hoc networks. In this scheme,
node evaluate additional coverage area based on their location,
if the additional area is less than a threshold, node will not
rebroadcast the packets and vice versa. The distance and
location methods are feasible in VANETs because vehicles are
the nodes of VANETs and by equipping GPS; it is easy to get
ISSN: 2393-9184
vehicles geography information. However, the determination of
threshold is difficult too. If the value is too small, the effect is not
obvious; if the value is too big, the reliability can‟t guaranteed.
Another sub-class of broadcasting protocols is called
deterministic broadcast [10].
In a deterministic broadcast protocol, the set of relay nodes is
selected deterministically to cover the overall environment. At
what time a node receives a broadcast message, it will make a
decision deterministically whether to send the message or not.
The advantages of deterministic broadcast schemes are low
broadcast overhead and little possible packet collisions.
However, deterministic broadcast schemes are flat to node
mobility, as the deterministic system relies strongly on
attachment information, will serve no purpose as node speed
increases.
The deterministic broadcasting protocols are further classified
into ad-hoc, cluster-based and simple flooding. In [9], authors
have described an ad-hoc Broadcasting Protocol for broadcasting
in ad hoc networks. In this approach, only nodes selected as
gateway nodes and a broadcast message header are allowed to
rebroadcast the message. The approach is described as follow,
1.
Place all two hop neighbours that able to only be
reached by a single hop neighbour. Choose these single
hop neighbours as gateways.
2. Compute the cover set that will take delivery of the
message from the present gateway position.
3. In support of the neighbours not so far in the gateway
position, locate the one that would cover the majority
two hop neighbours not in the cover position. Set this
single hop neighbour as a gateway.
4. Do again process 2 and 3 pending all two hop
neighbours are covered.
5. At what time a node receives a message and is a
gateway, this node determines which of its neighbours
by now received the message in the same transmission.
These neighbours are measured already covered and are
dropped from the neighbour used to select the next hop
get-ways.
Clustering is the method of grouping nodes together into
clusters or groups. An agent of each cluster is called the clusterhead. A cluster encompasses all nodes within a cluster-head‟s
broadcast range. Nodes that belong to a cluster, but are not the
cluster-head, are called normal nodes. Frequently nodes may
belong to more than one cluster. These nodes are called gateway
nodes. Only cluster-head nodes and entry nodes are in charge for
propagating messages. The process of forming clusters may be
moreover active or passive. Ordinary node broadcasts a message,
that message is received by cluster-head node and is relayed to all
nodes within its broadcast range. Gateway Node is receives the
message from cluster-head and rebroadcasts the message.
Cluster-head node receives the message and rebroadcasts it to its
neighbouring nodes [11]. A cluster method is classified into
following two types. In active clustering, nodes must cooperate in
order to elect cluster-heads. This is achieved through periodic
exchange of control information. In passive clustering, cluster
formation is dependent on background data traffic. Therefore,
passive clustering will not form clusters until there is background
traffic. In passive clustering, the flow of data traffic is used to
37
International Journal of Emerging Researches in Engineering Science and Technology, Volume 1, Issue 1 November’14
spread cluster control information and collect neighbour
information through lot of different packet reception.
In [12], authors have described a simple flooding approach
for broadcasting in ad hoc networks. In this approach to perform
broadcast is by flooding. In this method, a vehicle sends a
message to all of its neighbours and its neighbours in return
send message to its neighbours. This process continues until all
the vehicles get the same message.
In self-pruning broadcasting protocol [4], each node
maintains the knowledge of its neighbors by periodically
exchanging the Hello messages. The receiving node first
compares its neighbors list to that of sender‟s list, and
rebroadcast the message only if the receiving set can cover
additional nodes.
III. PROPOSED MODEL
In Scalable Broadcasting Algorithm (SBA) with timer
suppression mechanism, each node sends a message to their
neighbour based higher priority (i.e., which node has more
uncovered neighbours is proceed first). The following figure
shows time suppression mechanism; there are 14 nodes in figure
2 with V1 as the source node. From the source node the
information is transferred to its corresponding neighbour node
and the information is broadcasted based on high priority. In
this figure 2 vehicle V2 and V3 will start their receptive delay
timer to broadcast the message from vehicle V1. Node V3 has
more uncovered neighbour compared to node V2 therefore node
C preferred first for rebroadcast information.
Now node V6 and V7 are opposite each other to rebroadcast.
Since the timer of the node V2 has taking place, it will have the
priority to broadcasts earlier even through node V7 has
additional uncovered neighbours, thereby the broadcasting by
making vehicle V2 as a redundant node. Become aware of that
this problem could be solved by preventing node V2 from
sending earlier than node V7. Therefore in SBA with timer
suppression mechanism, we propose to restart the timer of node
V2. Whenever a low priority node receives a broadcast message
then the delay timer can be restarted depending up on new
uncovered neighbour information. Finally from the node V7 has
more neighbour than node V2, it will cover nodes V8, V9, V10,
V11, V12, V13 and V14, thus saving the broadcasting by V2.
V
13
V
8
V
14V
V
9
V
6
V
V 7
2
V
11
10
V
12
V
5
V
3
V
4
V
1
Fig. 2. VANET with 14 nodes
For example any node says B, that receives a broadcast message
M from sender A, will perform the following steps.
1. If set of immediate neighbour of node B is the subset of
immediate neighbour of node A and set of A, then no
need to perform broadcast process since all neighbour of
ISSN: 2393-9184
B has been covered by A.
2. The occurring later or after duplicate message will be
discarded.
3. If the message M is received for the first time, then the
covered set S is to store all covered nodes or more
formally set of node B and message is equal to immediate
neighbour of node A and set of A, Based on updated level
of node B.
4. During timer the countdown, any duplicate message will
be discarded and covered nodes set will be updated. i.e.
set of node B and message is equal to immediate
neighbour of node A and set of A, combination set of node
B and message. Delay timer will be reset according to the
recent uncovered neighborhood information.
5. After the delay timer expires and set of immediate
neighbour of node B subset of node B and message,
node B is overly retained from rebroadcast. Otherwise the
message is rebroadcast.
In addition to overly retained all the features of SBA
introduces a timer suppression method that waits the
rebroadcasting of nodes with lesser priority to enable the nodes
that rebroadcast earlier to cover as many nodes as possible
(including uncovered neighbours of suppressed nodes). However
not all suppressed nodes will be relieved from rebroadcasting.
Assume node V6 of Fig. 2 is not within range of node V7. Node
V2 will be suppressed by nodeV6 and will finally timeout to
cover node V6.
IV. PERFORMANCE EVALUATION
In this part, the performance evaluation of the proposed
scheme not in favor of counter based and distance based schemes
by the network simulator, ns2 (Network Simulator NS 2.34), is
presented. Parameters associated to mobility and traffic scenarios
are initial described. Performance metrics at the same time with
simulation results are then reported and analyzed.
The performance of the proposed scheme are measured and
compared with probabilistic based schemes mainly, Counter
based, and Distance based, under several node speeds and
densities. Several threshold values for these schemes are used as
follows: for Counter based scheme, the counter threshold is fix to
3 and 5, and for Distance based scheme, the distance threshold is
fix to 50 and 100m. The simulation parameter described in table
1.The following performance metrics have been used to estimate
each scheme [3, 4, and 7].
a. Saved ReBroadcast (SRB): is the ratio between the
numbers of hosts really rebroadcasting and the numbers of
host receiving a message.
b. Awareness: usually called Reach-ability is the condition
or capacity to see or to be aware of an event. Within the
range of VANETs, awareness is defined as a driver‟s view
and connected with thinking response to a condition or
event. Awareness is directly connected to the reach-ability
of the information to be disseminated.
c. Latency: the interval from time the broadcast was
initiated to the time the last host finished its rebroadcasting.
38
International Journal of Emerging Researches in Engineering Science and Technology, Volume 1, Issue 1 November’14
SIMULATION PARAMETER
VALUE
Bandwidth
2 Mbps
Network range
800 meter square
Transmission range
200 meter
Number of nodes
50, 100, 150
Nodes speed
1, 15, 25(Km/hr)
Simulation duration
100 seconds
Hello interval
1 second
Message size
1000 bytes
Speed 50km/hr
100
Counter=5
60
Distance=50
40
Distance=100
20
SRB(%)
Speed 10km/hr
SBA
80
Counter=3
60
Counter=5
40
Distance=50
20
Distance=100
0
50
100
150
Number of Vehicle
SBA
Counter=3
80
SRB(%)
It includes queuing, retransmission, and propagation
delays. Suitable latency is an important metric to figure out
the efficiency of a protocol to delay sensitive applications
like safety applications.
Table 1
Simulation parameters
0
50
100
150
Number of Vehicle
(iii)
Fig 3. SRB VS Number of vehicle: (i) with low speed (10Km/hr), (ii)
medium speed (30Km/hr), and (iii) high speed (50Km/hr)
Figure 3 plots the SRB evaluation of the SBA timer
suppression mechanism with the two common probabilistic based
broadcasting schemes (distance based and counter based) as a
role of network road density within the variety from 50 to 150
nodes where node speed is fixed to 10, 30, and 50 km/hr,
correspondingly. We can study that SRB increases proportionally
with the increase in the quantity of nodes for the all schemes. The
results show that in a dense network the counter and distance
based schemes exhibit lower SRB. Under different nodes density
and speed, the SBA with timer suppression mechanism has
important SRB as compared to the other broadcasting schemes.
We can see that SBA timer suppression mechanism has better
SRB over measured schemes. For example, in a network of 50
vehicles with a speed fixed to 10 km/hr, SBA with timer
suppression mechanism is better than counter based scheme and
better than distance based scheme. These results give good reason
for the value of the proposed scheme, i.e., without using any
extra affect such as fixed threshold, over counter and distance
based schemes.
(i)
Speed 10km/hr
100
SRB(%)
80
0.5
Counter=3
Counter=3
0.4
Counter=5
Counter=5
60
Distance=50
40
Distance=100
20
0
50
100
150
Number of Vehicle
SBA
SBA
Latency
Speed 30km/hr
0.3
Distance=50
0.2
Distance=100
0.1
0
50
100
150
Number of Vehicle
(i)
(ii)
ISSN: 2393-9184
39
International Journal of Emerging Researches in Engineering Science and Technology, Volume 1, Issue 1 November’14
0.12
0.1
0.08
0.06
0.04
0.02
0
SBA
Speed 10km/hr
SBA
Counter=3
120
Counter=3
Counter=5
100
Counter=5
Distance=50
Distance=100
Awareness
Latency
Speed 30km/hr
80
Distance=50
60
Distance=100
40
20
50
100
150
Number of Vehicle
0
50
100
150
Number of Vehicle
(ii)
(i)
(iii)
(ii)
Fig 4. Latency VS Number of vehicle: (i) with low speed (10Km/hr), (ii)
medium speed (30Km/hr), and (iii) high speed (50Km/hr)
Figure 4 shows the broadcast latency at a variety of network
densities with low, medium, and high vehicles speed. When
number of vehicles increases, there transmission of messages
increases, and therefore, resulting in decreasing latency. SBA
with timer suppression mechanism scheme is a more efficient
alternative protocol because it increases the number of saved
rebroadcast and the network becomes less congested. We can
make out that counter and distance based schemes have higher
latency values due to higher redundant rebroadcasts. For
example, in a network of 50 vehicles with a speed fixed to10
km/hr, threes is no or minute development compared to counter
scheme and distance scheme.
Following figure 5 shows the awareness (i.e., reach-ability)
comparison of SBA with timer suppression mechanism
scheme against the counter and distance based schemes. We
can see that in dense networks, all broadcasting schemes prove
the same strength in term of awareness among different
vehicles speed. SBA with timer suppression mechanism
scheme improves a number of the awareness, compared to
counter and distance based schemes.
ISSN: 2393-9184
(iii)
Fig 5. Awareness VS Number of vehicle: (i) with low speed (10Km/hr), (ii)
medium speed (30Km/hr), and (iii) high speed (50Km/hr)
V CONCLUSION
In this paper, we first review of broadcast protocols that have
been proposed for MANETs. Self-Pruning Broadcasting for
information Dissemination in VANETs is then presented. In this
scheme, further ensuring nodes with additional uncovered
neighbors rebroadcast first, a timer suppression mechanism to
wait the rebroadcasting of nodes with low priority. These are
useful to achieving the primary goals of dropping the number of
rebroadcasting nodes and make high packet delivery ratio
neighboring nodes without requiring any extra effort, such as
distance capacity, fixed upper/lower bounds, or accurate number
40
International Journal of Emerging Researches in Engineering Science and Technology, Volume 1, Issue 1 November’14
of neighboring nodes. The performance of the proposed scheme
is evaluated with NS2 under several mobility and traffic
scenarios. The simulation results are compared with major
Probabilistic based broadcasting protocols with respect to the
vehicle‟s speeds and under several network density scenarios.
The results show that SBA with timer suppression mechanism
is the most efficient with respect to SRB in conditions of
network density and nodes mobility. It provides a close to best
solution in conditions of highest SRB and average latency while
maintaining good reach-ability.
REFERENCES
[1] K. Dar, M. Bakhouya, J. Gaber, M. “Towards a decentralized architecture
for information dissemination in inter-vehicles networks”. Wireless
communication technologies for ITS applications. IEEE Communications
Magazine 2010; 48(5):156–62.
[2] Jagadeesh Kakarla, S Siva Sathya, B Govinda Laxmi, Ramesh Babu B.
“A Survey on Routing Protocols and its Issues in VANET”, International
Journal of Computer Applications (0975 – 8887) Volume 28– No.4,
August 2011.
[3] M. Bakhouya, J.Gaber, P.Lorenz. An adaptive approach
for
information dissemination in Vehicular Ad hoc
Networks .In: Journal
of Network and Computer Applications and science direct; 2011.p 1-8.
[4] Woon W, Yeung KL. “Self-pruning broadcasting for
mobile ad
hoc networks”. In: procedures of the 28th
IEEE
conference
on Global telecommunications
(GlobeCom‟09); 2009.
[5] Wei Peng Xi-Cheng Lu. On the Reduction of Broadcast Redundancy in
Mobile Ad Hoc Networks. IEEE Transaction on Mobile Computing, v.1
n.2, p.111-123, April 2002.
[6] M. Bani Yassein, M. Bani Khalaf. “A Performance Comparison of Smart
Probabilistic Broadcasting of Ad hoc Distance vector (AODV)”. Online:
www.comp.leeds.ac.uk/ukpew09/papers/15.pdf.
[7] Sze-Yao Ni, Yu-Chee Tseng, Yuh-Shyan Chen, and Jang- Ping Sheu.
“The Broadcast Storm Problem in a Mobile Ad
Hoc Network”, in:
Mobicom „99 Seattle Washington
USA copyright ACM 1999 158113-142.
[8] L.Zhou, G.Cui, H.Liu, Z.Wu and D.Luo. “NPPB: A broadcast scheme in
dense VANETs”; information Technology journal 9(2): 247-256, 2010.
[9] Demetres Kouvatsos and Is-Haka Mkwawa. Broadcasting Methods in
Mobile Ad Hoc Networks: An Overview. Proceedings of the HetNet, UK;
2005.
[10] Thadpong Pongthawornkamol, Klara Nahrstedt, Guijun Wang.
HybridCast: A Hybrid Probabilistic/Deterministic Approach for
Adjustable Broadcast Reliability in Mobile Wireless Ad Hoc Networks.
[11] Justin Lipman, Hai Liu, and Ivan Stojmenovic. Broadcast in Ad Hoc
Networks. Computer Communications and Networks, DOI 10.1007/9781-84800-328-6_6, Springer-Verlag London Limited 2009.
[12] Aneel Rahim, Fahad bin Muhaya, Zeeshan Shafi Khan. Enhanced
Relevance-Based Approach for Network Control. Informatica 34 (2010)
223–22.
ISSN: 2393-9184
41

Download Report