A Dynamic Probabilistic Broadcasting Scheme based on Cross-Layer design for MANETs

Published Online November 2010 in MECS

Mobile Ad hoc networks (MANETs) are self-organizing mobile wireless networks that do not rely on a preexisting infrastructure to communicate[1]. MANETs has several characteristics. First, the node in the MANETs is self-organizing and self-administrating without deploying any infrastructure. Second, MANET mobile nodes communicate with each other using

This work is supported by Specialized Research Fund for the Doctoral Program of Higher Education of China (Grant No.20050699037) and National Natural Science Foundation of China ( No.60472074 )

multi-hop wireless links. Third, MANET topology changes could occur randomly, rapidly and frequently, so the topology is dynamic [2].This kind of networks are very flexible and suitable for several situations and applications, thus they allow the establishing of temporary communication without preinstalled infrastructure[3]. MANETs are widely used in military, emergency operations, battle-fields, disaster recovery, civil and business operations [4].

In MANETs, broadcasting is a fundamental and effective data dissemination mechanism for route discovery, address resolution and many other network services [5]. Several routing protocols such as Dynamic Source Routing (DSR), Ad Hoc on Demand Distance Vector (AODV)[6], Zone Routing Protocol (ZRP), and Location Aided Routing (LAR) employ broadcasting to detect and maintain routes in a dynamic environment. Currently, these protocols typically rely on simplistic form of broadcasting called flooding, in which each mobile node retransmits every unique received packet exactly once. Although flooding is simple and easy to implement, it often causes unproductive and harmful bandwidth congestion, a phenomenon referred to as the broadcast storm problem[7,8].The problem is characterized by redundant rebroadcast, high contention and collision in the network, which leads to significant network performance degradation.

In this paper, we propose a dynamic probabilistic broadcasting scheme based on cross-layer design for MANETs, named DPBSC. We adopted the cross-layer design, which let the routing layer share the received signal power information of MAC layer. Then, we apply the received signal power information to calculate the additional transmission range, which is applied to dynamically adjust the rebroadcast probability. Simulation results reveal that DPBSC demonstrates better performance than blind flooding and fixed probabilistic flooding at the routing layer and IEEE 802.11 at the MAC layer.

The rest of the paper is organized as follows: In

Section 2, we introduce the related work. We describe the design and implementation of DPBSC in Section 3. The parameters used in the experiments and the performance results and analyses are presented in Section 4.Finally, section 5 concludes the paper and outlines the future work.

• II.    RELATED WORK

In MANETs, flooding is one of the earliest broadcasting mechanisms, where each node in the network rebroadcasts a message to its neighbors upon receiving it for the first time. Although flooding is simple and easy to implement, it can affect the performance of a network. Recently, several improving schemes to mitigate the broadcast storm problem are presented.

Ni et al.[7] have proposed flooding five schemes in MANETs called probabilistic, counter-based, distance-based, location-based and cluster-based broadcasting. In the probabilistic scheme, the node rebroadcasts a message according to fixed and predetermined probability P . The counter-based scheme inhibits the rebroadcast if the message has already been received for more than a fixed number C times. This scheme works on the assumption that the expected additional coverage is so small that rebroadcast would be ineffective when the number of recipient broadcasting messages exceed a certain threshold value. In the distance-based scheme, a node operates depending on a threshold D .Only if the distance between the sender and the receiver is larger than D , the node rebroadcasts the message .In location-based scheme rebroadcasts the message if the additional coverage due to the new emission is larger than abound A . Finally, the counter-based scheme divided the network into number of clusters. Each cluster has one cluster head and a number of memberships. The cluster head is a representative of the cluster whose rebroadcast can cover all hosts in that cluster. Only a cluster head can communicate with other clusters and have responsibilities to disseminate the broadcast message to other memberships. Williams et al.[9] has classified the broadcasting techniques into the following four categories: simple flooding, probability-based, area-based and neighbor knowledge scheme. The simple flooding, probability-based and area-based scheme is similar as the work Ni et al.[7] have done. The neighbor knowledge scheme [9]maintains neighbor node information to decide who should rebroadcast. This method requires mobile nodes to exchange neighborhood information among mobile nodes using one hop periodic hello packets. The neighbor list at the present node is added to every broadcast packet. When the present node receives a packet from the neighbor, it compares its neighbor list with the list recorded in the packet. It rebroadcasts the packet if not all of its own neighbors are included in the list recorded in the packets. The length of the period affects the performance of this approach[1].

Jamal-Deen Abdulai et al. [10] proposed two new probabilistic methods that can significantly reduce the number of RREQ packets transmitted during route discovery operation, which can result in significant performance improvements in terms of routing overhead, MAC collisions and end-to-end delay .The disadvantage of these methods is that they decrease the network performance when the network is sparse. Zhang and Agrawal [11] proposed a Dynamic probabilistic broadcast scheme as a combination of the probabilistic and counter-based approaches, which has the drawback of increases latency. Yassein et al.[12] has analyzed the performance of adjusted probabilistic broadcasting scheme where the forwarding probability p is adjusted by the local topology information. This scheme increases the saved rebroadcast, but led to an extra overhead by constructing one-hop neighbor list. Wang et al.[13] proposed a cross-layer approach for efficient flooding, in which a novel MAC layer access-deferring scheme based on the received signal power is presented. Although this approach has good performance in terms of throughput, average delay and energy efficiency, it leads to network performance decreased when the nodes in the network are moving.

With the broadcasting schemes described above, the probabilistic approaches reduce the number of rebroadcasts, but they decrease the reach ability. Although counter-based algorithms have better reach ability, they cause longer end-to-end delay. Area-based algorithms have the drawback of needing GPS or other location devices. The neighbor-knowledge-based approaches need the hello packets to exchange of neighborhood information, which waste bandwidth and energy. In this paper, we propose a new probabilistic broadcasting scheme based on cross-layer design that dynamically fine-tunes the rebroadcast probability for broadcasting packets. The details of the proposed approach are described in the following section.

• III.    DESIGN AND IMPLEMENTATION OF DPBSC

• A.    Architecture of DPBSC

A strict layered design is not flexible enough to cope with the dynamics of MANETs environments, and will thus prevent performance optimizations[14]. The main drawback of this design is the lack of cooperation among adjacent layers: each layer works in isolation with little information about the network[15]. The cross layer approaches attempt to exploit more interactions among layers to achieve better performance. DPBSC apply cross layer design, which let the routing layer share the received signal power information at MAC layer while still maintaining separation between the two layers. The MAC layer of DPBSC is implemented based on the IEEE802.11 and the routing layer based on the flooding. The architecture of DPBSC is shown as Fig.1.

is very small, there is little additional coverage B ’s rebroadcast can provide. If d is larger, the additional coverage will be larger. In the extreme case, if d = 0, the additional coverage is 0 too. If d = r, the additional coverage will be the largest.

S ( r ) = ( - + ^1) r ² - 0.6090 n r ² (4)

A n B 3 2

From the analysis above, we know that let the nodes with the larger additional coverage rebroadcast the received packet with high probability, which can reduce the redundant retransmission and the chance of the contention and collision. On the other hand, covers more neighbor nodes, which decreases delay that the packets coverage the whole network.

• B.    Theory analysis

MANETs can be modeled as a graph G ( V , E ) , where V = V , V 2 , ^ v n } is the set of nodes and E = {( i , j )| d ( i , j ) <  r } is the set of edges that represent wireless links; d ( i , j ) represents the distance between node V_i and node V_j ; r is the transmission radii of node. A link is assumed to exist between two nodes if and only if the two nodes are within each other’s radio range. Fig. 2 shows an example, in which node A sends a broadcast message, and node B decides to rebroadcast the message. S A _n B ( d ) is the intersection area of the two nodes’ transmission range. The additional area that can benefit from B ’s rebroadcast is denoted as S ( d ) .

A n B

Figure2. Analysis of the additional area benefited from rebroadcast.

According to[7], the intersection area of the two nodes’ transmission range S A _n B ( d ) is given by

S A n B ( d ) = 4 J d /2 V r ² - x ² dx

= n r ² - d r²   2 r² 4

d arcsin

2 r

The additional area SAnB (d) can be computed as follows:

S  (d) = dr2 -d- + 2r2arcsin —(2)

An B               42

We can obtain derivative of (1) as follow:

2 r² - ¹ d²

SAnB'(d) =     ^ > 0

d r -

• C.    Implement of DPBSC

According to[16], the relationship between transmission power and the received signal power in the two-ray ground propagation model can be calculated as follow:

Pr = Pt ( ^Fh" ) 2               (5)

Where Pt is the default transmission power and Pr the received signal power; Gl is the antenna gain; ht and hr are the heights of the antennas, and d is the distance between the sender and the receiver. We assumed that the network is homogeneous that all nodes use the same parameters.

From (7), the d is given by d = 41 PG,(, hAr )2                       (6)

P r

When a node receives a broadcasting packet, it refers to its additional coverage of rebroadcast to determine rebroadcast probability. If the packet is received for the first time, the node applying DPBSC uses its coverage area to determine its rebroadcast probability as follow:

'                 Л I 2 d2 , . 2

с i dxW --+ 2 r arcsin —

SA n B = V 42

p=rn ■"'       (П+т )r2      '(7)

for 0 <  d <  r

0,

[ ford >  r

From (7), we know that DPBSC dynamically calculates the value of rebroadcast probability p at each mobile host according to its additional coverage area benefited from rebroadcast. If the additional coverage area is larger, the rebroadcast probability is higher. The probability is lower when the additional coverage area is smaller. Higher value of p means lower number of redundant rebroadcast. The procedure of DPBSC is shown in Table I.

From (3), we know that S A _n B ( d ) is a monotonically

increasing function. If the distance d between A and B

TABLE I. The procedure of DPBSC

Protocol receiving ()

• 1.    On hearing a broadcast packet m at the MAC layer of node X

• 2.    If wireless channel is busy

• 3.    Collision is detected.

• 4. End if

• 5. Else Get the received signal power P _r

• 6.    On hearing the packet m at the routing layer of node X

• 7.I f packet m received for the first time then

• 8.    Get distance d from the sender according to (6).

• 9.I f d >  r

• 10 .Drop the packet

• 11 .End if

• 12 . Else Get rebroadcast probability p by (7).

• 1 3.If RN <  P

• 14 . Rebroadcasts the packet.

• 15 .End if

• 16 ..Else Drop the packet

• IV. PERFORMANCE ANALYSIS

• A.    Simulation Setup

  We use ns-2 packet level simulator (v.2.31) to simulate a square 1000m by 1000m. Protocol:(1)DPBSC(2) flooding applied at the routing layer ,while IEEE802.11 at the MAC layer (flooding+802.11)(3) probabilistic flooding applied at the routing layer ,while IEEE802.11 at the MAC layer (fp-flooding+802.11). Other simulation parameters that have been used in our experiment are shown in Table II.

TABLE II Simulation Parameters

Simulation Parameter	Value
Simulation time	300s
Transmission range	250m
Traffic type	CBR
Movement model	RWP
Queue length	50
Queue	PriQueue
Propagation Model	TwoRayGround
Antenna	OmniAntenna
Pause time	100s
Bandwidth	2 Mbps

• B.    Performance Metrics

The four performance metrics are defined as flowing:

• 1)    Saved-Rebroadcast SRB

srb = pa r pa f x ioo%              (8)

par

Where pa_r are number of the received non-repetitive packets by the nodes and pa_f the number of the forwarded non-repetitive packets by the nodes.

• 2)    Packet Drop Fraction P_drop

P d

P op = P S-                        (9)

n

Where P_d is the number of packets dropped by the nodes and P_S the number of packets send by the source nodes and n represents the number of nodes in the network.

• 3)    Average number of collisions-This is the average number of collisions at the MAC layer.

4)End-to-end delay-This is the average time difference between the time a data packet is sent by the source node and the time it is successfully received by the destination node.

• 5)    Throughput: is the total number of non-repetitive data packets received at destinations per second.

• C.    Simulation Results

• 1)    Effects of network density simulation

The purpose of the simulations presented in this subsection is to study the effects of different network density (number of nodes) on the performance of the three schemes. The number of nodes is 25, 50, 75,100,125 and 150. The maximum speed 50 m/s is chosen to study the effects of network density in the network with high speed. The numbers of CBR connection that are considered in the experiments is 10.

The simulation parameters of this experiment are set as follows:

• >   Number of nodes: 25, 50, 75,100,125 and 150

nodes.

• >    Maximum speed: 50 m/s.

• >    Packet rate: 10packets/second.

• >   Number of connections: 10.

  
  

  Number of Nodes

  Figure4. Packet Drop Fraction per Node vs. network density

  
  
  

  Figure.6 End-to-End Delay vs. network density

  
  

Fig.3 shows the results of the saved rebroadcast vs. the network density for all the three schemes. The metric is decreased as the network density grows. The three schemes achieve different SRB percentages with increasing network density. Apparently, this figure shows that DPBSC can significantly achieve a higher saved rebroadcast than flooding+802.11 and fp-flooding+802.11.This is because nodes rebroadcast a packet with a dynamic probability value according to the additional transmission range, which significantly reduce the number of the rebroadcast.

Fig.4 shows the results of the packet drop fraction per node vs. the network density for all the three schemes. The metric is increased as the network density grows. This figure displays that DPBSC has lower packet drop fraction per node than flooding+802.11 and fp-flooding+802.11. This is due to that DPBSC let the nodes receive little duplication packet, therefore, reduce the number of dropping packets.

Number of Nodes

Figure.5 Number of collisions vs. network density

Fig.5 shows the results of the number of collisions per node vs. the network density for all the three schemes. The metric is increased as the network density grows. When network density increases, more packets fail to reach the destinations. In these cases, more broadcasting packets are generated, which lead to more collisions. It is evident that CLAPB incurs fewer collisions than flooding+802.11 and fp-flooding+802.11. This is because CLAPB mitigates the contentions and collisions during broadcasting.

Fig.6 shows the results of the end-to-end delay vs. the network density for all the three schemes. The metric is increased as the network density grows. When node density increases, more broadcast packets fail to reach all the nodes due to high probability of packet collision and channel contention caused by excessive redundant retransmission of broadcast packets. Therefore the waiting time of packets in the interface queues increases. As shown in figure 6, DPBSC exhibits lower end-to-end delay than flooding+802.11 and fp-flooding+802.11.This figure shows that DPBSC displays the lower end-to-end delay than flooding+802.11 and fp-flooding+802.11. Since rebroadcast packets collide and content for channel with each other, and the DPBSC incurs the lowest number of rebroadcasts (highest saved-rebroadcast), it should have the lowest latency.

Fig.7 shows the results of throughput vs. the network density for all the three schemes. The metric is increased as the network density grows. When network density increases, the length of the paths between the sources and destinations, the number of the packets failing to reach the destinations is decreased. It is evident that CLAPB suffers from lower throughput than flooding+802.11 and fp-flooding+802.11. This is because CLAPB dynamic adjusts the rebroadcast probability accord to the additional transmission range, which decreases the reach ability.

Number of Nodes

Figure.7 Throughput vs. network density

Figure8. Saved-Rebroadcast vs. traffic load

• 2)    Effects of offered traffic load simulation

The purpose of the simulations presented in this subsection is to study the effects of different traffic load (number of connections) on the performance of the three schemes. The traffic load simulation is done by changing the number of Constant Bit Rate (CBR) connections. The numbers of CBR connections that are considered in the experiments are 5,10,15,20,25,30,35 and 40. The number of nodes is 100.The maximum speed 10 m/s is chosen to study the effects of traffic load in the network.

The simulation parameters of this experiment are set as follows:

• >   Number of nodes: 100nodes.

• >    Maximum speed: 10 m/s.

• >    Packet rate: 6 packets/second.

• >    Number of connections: 5,10,15,20,25,30,35 and 40

connections.

Fig.8 depicts the results of the saved rebroadcast vs. the traffic load for all the three schemes. The metric is increased as the traffic load grows. When the traffic load increased, there exist many connections between the nodes in the network, so the nodes receive more non-repetitive packets. The three schemes achieve different SRB percentages with increasing traffic load. Apparently, this figure shows that DPBSC can significantly achieve a higher saved rebroadcast than flooding+802.11 and fp-flooding+802.11.This is because nodes rebroadcast a packet with a dynamic probability value according to the additional transmission range, which significantly reduce the number of the rebroadcast.

Fig.9 depicts the results of the packet drop fraction per node vs. the traffic load for all the three schemes. The metric is decreased as the traffic load grows. When the traffic load increased, there exist many connections between the nodes in the network, so the source nodes send more data packets. This figure displays that DPBSC has lower packet drop fraction per node than flooding+802.11 and fp-flooding+802.11. This is due to that DPBSC let the nodes receive little duplication packet, therefore, reduce the number of dropping packets.

Figure9. Packet Drop Fraction per Node vs. traffic load

Figure.10 Number of collisions vs. traffic loads.

Figure.11 End-to-End Delay vs. traffic load

Fig.10 depicts the results of the number of collisions per node vs. the traffic load for all the three schemes. The metric is increased as the traffic load grows. When the number of connections between the nodes increases, more packets fail to reach the destinations. In these cases, more broadcasting packets are generated, which lead to more collisions. It is evident that CLAPB incurs fewer collisions than flooding+802.11 and fp-flooding+802.11. This is because CLAPB mitigates the contentions and collisions during broadcasting.

Fig.11 depicts the results of the end-to-end delay vs. the traffic load for all the three schemes. The metric is increased as the traffic load grows. When traffic load increases, more broadcast packets fail to reach all the nodes due to high probability of packet collision and channel contention caused by excessive redundant retransmission of broadcast packets. Therefore the waiting time of packets in the interface queues increases. As shown in figure 6, DPBSC exhibits lower end-to-end delay than flooding+802.11 and fp-flooding+802.11.This figure shows that DPBSC displays the lower end-to-end delay than flooding+802.11 and fp-flooding+802.11. Since rebroadcast packets collide and content for channel with each other, and the DPBSC incurs the lowest number of rebroadcasts (highest saved-rebroadcast), it should have the lowest latency.

Figure.12 Throughput vs. traffic load

Fig.12 shows the results of throughput vs. the traffic load for all the three schemes. The metric is increased as the traffic load grows. When traffic load increases, the number of connections between the sources and destinations is increased. Therefore, the number of the packets reach the destinations is increased. It is obvious that CLAPB suffers from lower throughput than flooding+802.11 and fp-flooding+802.11. This is because CLAPB dynamic adjusts the rebroadcast probability accord to the additional transmission range. If the additional transmission range is small, the rebroadcast probability is low, which decreases the reach ability.

V. CONCLUSION

In this paper, we proposed a dynamic probabilistic broadcasting scheme based on cross-layer design for MANETs (DPBSC) that mitigates the broadcast storm problem associated with flooding. DPBSC adopts the cross-layer design and adjusts the value of the rebroadcast probability dynamically according to its additional transmission range benefited from rebroadcast.

Our simulation results show that DPBSC performs better than the blind flooding and fixed probabilistic flooding applied at routing layer ,while the IEEE802.11 at the MAC layer.

As a continuation of this research in the future, we plan to adjust the rebroadcast probability using the neighbor information and the energy level of the intermediate node in order to improve the performance of the proposed broadcasting scheme.

ACKNOWLEDGMENT

We are grateful to Cheng Wei and Jiang Yi for their valuable suggestions and comments.