Performance Analysis of Adjusted Probabilistic Broadcasting in Mobile Ad Hoc Networks

Broadcasting in Mobile Ad Hoc Networks (MANETs) is a fundamental data dissemination mechanism with a number of important applications in, e.g., route discovery, address resolution. However, broadcasting induces what is known as the “broadcast storm problem” which causes severe degradation in network performance due to excessive redundant retransmission, collision, and contention. Broadcasting in MANETs has traditionally been based on flooding, which simply swamps the network with large number of rebroadcast messages in order to reach all network nodes. Although probabilistic flooding has been one of the earliest suggested schemes to broadcasting, there has not been so far any attempt to analyse its performance behaviour in a MANET environment. In an effort to fill this gap, this paper investigates using extensive ns-2 simulations the effects of a number of important system parameters in a typical MANET, including node speed, pause time, traffic load, and node density on the performance of probabilistic flooding. The results reveal that most of these parameters have a critical impact on the reachability and the number of saved rebroadcast messages achieved by probabilistic flooding.

Introduction

Mobile Ad Hoc Networks (MANETs) consist of a set of wireless mobile nodes which communicate with one another without relying on any pre-existing infrastructure in the network. The distributed, wireless, and self-configuring nature of MANETs make them suitable for a wide variety of applications [1]. These include critical military operations, rescue and law enforcement missions as well as and disaster recovery scenarios [2,3]. Other potential applications of MANETs are in data acquisition in hostile territories, virtual classrooms, and temporary local area networks.

Broadcasting is a fundamental operation in MANETs whereby a source node transmits a message that is to be disseminated to all the nodes in the network. In the one-to-all model, transmission by each node can reach all nodes that are within its transmission radius, while in the one-to-one model, each transmission is directed towards only one neighbour using narrow beam directional antennas or separate frequencies for each node [4]. Broadcasting has often been studied in the literature mainly for the one-to-all model [5], and most of this study is devoted to this model; it is worth nothing that the one-to-many model can also be considered, where fixed or variable angular beam antennas could be used to reach several neighbours at once [6].

Broadcasting has many important uses and several protocols in MANETs assume the availability of an underlying broadcast service [4,7]. Applications which make use of broadcasting include LAN emulation, paging a particular node, or sending an alarm signal thereby establishing unicast routes in proactive protocols [4]. It is also used for route discovery in reactive protocols. For instance, a number of routing protocols such as Dynamic Source Routing (DSR) [8], Ad Hoc on Demand Distance Vector (AODV) [8], Zone Routing Protocol (ZRP) [9, 10], and Location Aided Routing (LAR) [11] use broadcasting or one of its derivatives to discover and establish routes. Broadcasting also serves as the last resort for other group communication operations such as multicast.

One of the earliest broadcast mechanisms proposed in the literature is simple or “blind” flooding [6] where each node receives and then re-transmits the message to all its neighbours. The only ‘optimisation’ applied to this technique is that nodes remember broadcast messages received and do not act if they receive repeated copies of the same message [12]. However, a straightforward flooding of the network with broadcast messages is usually costly and results in serious redundancy and collisions in the network; such a scenario has often been referred to as the broadcast storm problem [5,6,13], and has generated many challenging research issues [5,6,13]. A number of researchers have identified this problem by showing how serious it is through analyses and simulations e.g. see the study of [5,6,13].

A probabilistic approach to flooding has been suggested in [5,12,14] as a means of reducing redundant rebroadcast messages and alleviating the detrimental effects of the broadcast storm problem. In the probabilistic scheme, when receiving a message for the first time, a node rebroadcasts the message with a pre-determined probability p; every node has the same probability to rebroadcast the message. When the probability is 100%, this scheme reduces to simple flooding. The studies of [12,14] have shown that probabilistic broadcast incurs significantly lower overhead compared to blind flooding while maintaining a high degree of propagation for the broadcast messages. However, when analysing the performance of probabilistic flooding, these studies have not taken into consideration a number of important factors that could greatly impact the performance of a typical MANET. Such factors include node mobility, network density, and injected traffic load. In an effort to gain a deep understanding and clear insight into the behaviour of probabilistic flooding in a MANET environment, this paper investigates the effects of mobility on the operation and effectiveness of probabilistic flooding. Two important metrics, notably reachability and saved rebroadcasts, are used to assess network performance. Moreover, the well-known random waypoint model [15,16] is used to analyse through extensive simulations the impact of varying node pause times and speeds on the performance of probabilistic flooding. The effects of varying node density, i.e. the number of network nodes per unit area for a given transmission range, and varying the traffic load, i.e. the number of broadcast request injected into the network per second are also studied. The results presented below reveal that node speed, pause time, and density have a critical impact on the reachability achieved by probabilistic flooding, and also have great impact on the saved rebroadcast messages.

The rest of the paper is organised as follows. Section 2 provides an overview of previous work on broadcasting in MANETs. Section 3 briefly describes the probabilistic flooding method and then presents the simulation model and the parameters used in the experiments. Section 4 presents the performance results and analysis of the behaviour of the broadcasting algorithm. Finally, Section 5 concludes by a recount of the obtained results and suggestions for future work.

Related Work

One of the earliest broadcast mechanisms in both wired and wireless networks is flooding, where every node in the network retransmits a message to its neighbours upon receiving it for the first time. Although flooding is simple and easy to implement, it can be costly in terms of network performance, and may lead to a serious problem, often known as the broadcast storm problem [4–6] which is characterised by high redundant message retransmissions, network bandwidth contention and collision. Ni et al. [5] have studied the flooding protocol analytically and experimentally. Their obtained results have indicated that rebroadcast could provide at most 61% additional coverage and only 41% additional coverage in average over that already covered by the previous broadcast attempt. As a result, they have concluded that rebroadcasts are very costly and should be used with caution. The authors in [5] have also classified existing broadcasting schemes into five categories with respects to their ability to reduce redundancy, contention, and collision. The categories include probabilistic, counter-based, distance-based, location-based and cluster-based. A brief description for each of these categories is provided in the sequel.

In the probabilistic scheme, a mobile node rebroadcasts messages according to a certain probability. In the counter-based scheme, a node determines whether to rebroadcast a message or not by counting how many identical messages, it has received during a random time period. The counter-based scheme assumes 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.

The distance-based scheme uses the relative distance between a mobile node and the previous sender to make a decision as to whether to rebroadcast a message or not. In the location-based scheme, the additional coverage concept [5] is used to decide whether to perform a rebroadcast. Additional coverage is acquired by the locations of the broadcasting nodes using the geographical information of a MANET [5].

The cluster-based scheme divides the ad hoc network into a number of clusters or subsets of mobile nodes. Each cluster has one cluster head and several gateways. The cluster head is a representative of the cluster whose rebroadcast can cover all hosts in that cluster. Only gateways can communicate with other clusters and have responsibilities to propagate the broadcast message to other clusters [17].

An alternative classification for broadcasting techniques could also be found in [4]. This study has classified the broadcasting techniques into the following four categories: simple flooding, probability-based, area-based, and neighbour knowledge schemes. In the flooding scheme, every node retransmits to its neighbours as a response to every newly received message. The probability-based scheme is a simple way of controlling message floods. In that each node rebroadcasts with a predefined probability p [12]. Obviously when p=1 this scheme resembles simple (blind) flooding. In the area based scheme, a node determines whether to rebroadcast a message or not by calculating and using its additional coverage area [5]. The neighbour knowledge scheme [4] maintains neighbour node information to decide who should rebroadcast. To use the neighbour knowledge method, each node has to explicitly exchange neighbourhood information among mobile hosts using periodic “hello” messages. The length of the period affects the performance of this scheme. Short periods could cause collision or contention while long periods may degrade the protocol’s ability to cope with mobility [18–20].

Probabilistic Flooding

The simple flooding scheme [12] is a straightforward broadcasting approach that is easy to implement with guaranteed message dissemination. In this scheme, a source broadcasts messages to every neighbour who in turn rebroadcasts received messages to its neighbours and so on. This process continues until all reachable nodes have received and rebroadcast the message once. Figure 1 provides a brief outline of the simple flooding scheme.

Fig. 1.

An outline of the simple flooding algorithm for broadcasting in MANETs.

Of course, the naïve flooding approach has its obvious shortcoming redundancy and message contention. The probabilistic scheme [12] is one of the alternative approaches that aim at reducing redundancy through rebroadcast timing control in an attempt to alleviate the broadcast storm problem. In this scheme, when receiving a broadcast message for the first time, a node rebroadcasts the message with a pre-determined probability p so that every node has the same probability to rebroadcast the message, regardless of its number of neighbours. In dense networks, multiple nodes share similar transmission range. Therefore, these probabilities control the frequency of rebroadcasts and thus could save network resources without affecting delivery ratios. It should be noticed that in sparse networks there is much less shared coverage; thus some nodes will not receive all the broadcast messages unless the probability parameter is high. Figure 2 provides a brief outline of this scheme (see Sasson et al. [12] for more details).

Fig. 2.

An outline of the probabilistic flooding algorithm for broadcasting in MANETs.

Performance Analyses

We have used the ns-2 packet level simulator (v.2.27) [21] to conduct extensive experiments to evaluate the performance behaviour of probabilistic flooding. The network considered for the performance analysis of the rebroadcast probability vs. density has been varied from 25 nodes up 100 placed randomly on 600× 600 m², with each node engaging in communication transmitting within 250 m radius and having bandwidth of 2 Mbps. The retransmission probabilities have been varied from 0.1 to 1.0% with 0.1% increment per trial. The random waypoint model [15,16] has been used to simulate 25 mobility patterns. In this mobility model, nodes that follow a motion-pause recurring mobility state, where each node at the beginning of the simulation remains stationary for pause_time seconds, then chooses a random destination and starts moving towards it with speed selected from a uniform distribution (0, max_speed]. After the node reaches that destination, it again stands still for a pause time interval (pause_time) and picks up a new destination and speed. This cycle repeats until the simulation terminates. The maximum speeds (max_speed) of 1, 5, 10, 20 m/s and pause times of 0 s are considered for the purposes of this study. It is worth noting that the simulation parameters used in this study have been widely adopted in existing performance evaluation studies of MANETs [15, 16], and are summarised below in Table I.

Table I. Summary of the parameters used in the simulation experiments

The performance of broadcast protocols can be measured by a variety of metrics [4–6]. A commonly used metric is the number of message re-transmissions with respect to the number of nodes in the network [6]. In this work, we use rebroadcast savings, which is a complementary measure as defined below. The other important metric is reachability, which is defined in terms of the ratio of nodes that received the broadcast message out of all the nodes in the network. The formal definitions of these two metrics are given below, following [6].

Saved ReBroadcasts (SRB): Let r be the number of nodes that received the broadcast message and let t be the number of nodes that actually transmitted the message. The saved rebroadcast is then defined by (r−t)/r.

Reachability (RE): is the percentage of nodes that received the broadcast message to the total number of nodes in the network. For useful information, the total number of nodes should include those nodes that are part of a connected component in the network. For disconnected networks this measure should be applied to each of the components separately [5].

Effect of Speed and Node Pause Time

The results for saved rebroadcasts achieved by probabilistic flooding are depicted in Figure 3 for continuous (i.e., 0 s pause time) and non-continuous mobility. For each pause time, the maximum node speed has been varied from 1, 5, 10, to 20 m/s. As the results show, the node speed has critical impact on the observed saved rebroadcast value since for each probability value, as the mean node speed increases the saved rebroadcast increases. Figure 4 shows the rebroadcast probability against reachability across four different maximum node speeds, and the reachability achieved in the case of continuous mobility . Overall, across the different broadcast probabilities, reachability increases as the mean node speed increases.

Fig. 3.

Impact of speed on saved rebroadcast using probabilistic flooding with no pause time and different node speeds 1, 5, 10, and 20 m/s.

Fig. 4.

Impact of speed on reachability with no node pause time and different node speeds 1, 5, 10, and 20 m/s.

The saved rebroadcasts and reachability have also been examined as a function of the rebroadcast probability across different node pause times. In general, the longer the average pause time is, the less the node movement is within the network. The saved rebroadcast achieved by probabilistic flooding is shown in Figures 5–8 for continuous mobility (0 and 20 s pause time). For each pause time, the maximum speed of the nodes has been varied from 1, 5, 10 to 20 m/s. For each probability value, as the node pause time increases the amount of saved rebroadcasts increases. Figure 9 shows the rebroadcast probability against reachability across two different maximum node speed values (5 and 20 m/s). The reachability achieved for continuous mobility (0 and 20 s pause time) is shown in Figure 9. Reachability exhibits improvement as the mean node pause time increases across the different probability values.

Fig. 5.

Impact of pause time on saved rebroadcast with speed 1 m/s and different node pause time 0, 20 s.

Fig. 6.

Impact of pause time on saved rebroadcast with node speed 5 m/s and different node pause time 0, 20 s.

Fig. 7.

Impact of pause time on saved rebroadcast with node speed 10 m/s and different node pause time 0, 20 s.

Fig. 8.

Impact of pause time on saved rebroadcast with node speed 20 m/s and different node pause time 0, 20 s.

Fig. 9.

Impact of pause time on reachability with node speed 10 m/s and different node pause time 0, 20 s.

Effects of Mobility and Density

Figures 10–12 depicts the degree of reachability achieved when the rebroadcast probability is increased. The figures show reachability with four different node densities and four different node speeds. Figure 10 suggests that reachability using probabilistic flooding for continuous mobility increases with higher density. The trend in the figures also suggests that the reachability increases as the node speed increases.

Fig. 10.

Impact of density on reachability for different network densities with node speed 1 m/s.

Fig. 11.

Impact of density on reachability for different network densities with node speed 5 m/s.

Fig. 12.

Impact of density on reachability for different network densities with node speed of 10 m/s.

Reachability improves with higher density and faster nodes for the following reason. As the density of the nodes increases, the number of nodes covering a particular area also increases. As the probability of re-broadcast is fixed for every node, this implies that there are more candidates for transmission in each “coverage” area. Hence, there is a greater chance that a broadcast re-transmission occurs, resulting in increased reachability. Moreover, for a given transmission range, as density increases the connectivity of the network increases. As a result, a small broadcasting probability, p, is sufficient to achieve high reachability. However, a larger p is required if the node distribution is sparse, the amount of reachability increases, proportionally to p, as p increases. In addition as node speed increases connectivity increases then the probability of partitioning decreases, leading to a higher degree of reachability.

Figures 13–16 demonstrate the effects of speed and density on the saved rebroadcasts using 16 combinations of node densities and speeds. As can be seen in the figures, the saved rebroadcast increases with higher nodes speeds and densities. The amount of saved rebroadcasts increases as the density of the nodes increases, i.e. as the number of nodes covering a particular area increases. As the probability of the transmission is fixed for every node, this implies that there are more candidates for broadcast re-transmission in each “coverage” area, and consequently, there is a higher chance that a re-transmission occurs, increasing the number of saved rebroadcast messages at the level of each probability. Further note that the saved rebroadcast value decreases as p increases. Moreover, as the node speed increases, network connectivity increases as the probability of partitioning decreases, which in turn results in increased saved rebroadcasts.

Fig. 13.

Impact of density on saved rebroadcast for different network densities with node speed 1 m/s.

Fig. 14.

Impact of density in saved rebroadcast for different network densities with node speed 5 m/s.

Fig. 15.

The impact of density in saved rebroadcast for different node density for node speed 10 m/s.

Fig. 16.

Impact of density on rebroadcast for different node density with node speed 20 m/s.

Effects of Mobility and Traffic Load

Figures 17–20 show reachability results when rebroadcast probability is varied for different mean node speeds and traffic loads. While the node speed has been varied as in the above simulation setups, the load has been varied by increasing the rate of broadcast messages generated at a given source nodes from 1 to 4 broadcast messages per second. Figure 17 suggests that the achieved reachability for continuous mobility (0 pause time) increases at moderate node speed. Furthermore, the trend in the following four figures suggest that the reachability increases as the node load increases.

Fig. 17.

Impact of load on reachability at one broadcast/s with different node speed 1, 5, 10, and 20 m/s.

Fig. 18.

Impact of load on reachability at two broadcasts for different node speeds 1, 5, 10, and 20 m/s.

Fig. 19.

Impact of load on reachability at 3 messages/s for different node speeds 1, 5, 10, and 20 m/s.

Fig. 20.

Impact of load in reachability at four broadcasts/second for different node speeds 1, 5, 10, and 20 m/s.

The rational for the fact that the reachability improves with higher load traffic and faster nodes is as follows. As the load of the nodes increases, the number of nodes covering a particular area also increases. As the probability of the transmission is fixed for every node this implies that these are more candidates for transmission in each “coverage” area. Hence, there is greater chance that a transmission will occur, thus reachability increases. In addition to that, for given transmission range, as load increases the connectivity of the network increases then a small probability p is sufficient to achieve high reachability. But larger p is needed if the node distribution is sparse, the amount of reachability (RE) increases, proportionally to p, as p increases in addition as node speed increases the connectivity increases then the probability of partitioning decreases thus reachability increase.

The remaining simulation results give an indication on the effect of speed and traffic load of the saved rebroadcasts. Figures 21–24 demonstrate this effect using 16 combinations of node traffic load and speed. As can be observed from the figures, the saved rebroadcast increases with higher nodes speeds and traffic load. The amount of saving (SRB) increases as the traffic load of the nodes increases, the number of nodes covering a particular area also increases. As the probability of the transmission is fixed for every node this implies that these are more candidates for transmission in each “coverage” area. Hence, there is greater chance that a transmission will occur, thus (SRB) increases at the level each probability. In addition to that, (SRB) decreases as p increases in addition as node speed increases the connectivity increases then the probability of partitioning decreases thus (SRB) increases (Figure 24).

Fig. 21.

Impact of load on saved rebroadcast at 1 message/s for different node speed 1, 5, 10, and 20 m/s.

Fig. 22.

Impact of load on saved rebroadcast at 2 messages/second for different node speeds 1, 5, 10, and 20 m/s. Reachability at four broadcasts.

Fig. 23.

Impact of load on saved rebroadcast at 3 messages/s for different node speeds 1, 5, 10, and 20 m/s.

Fig. 24.

Impact of load on saved rebroadcast at 4 messages/s for different node speeds 1, 5, 10, and 20 m/s.

Improving the Performance of Probabilistic Flooding

The above results show that most of the important system parameters considered in our analysis, e.g. node mobility, density, and traffic load, have a great impact on network performance. In MANETs, where the topology changes frequently, the rebroadcast probability at each node must be dynamically adjusted to account for a given node’s surroundings in order to achieve high saved rebroadcast and high reachability. As a rule of thumb, the rebroadcast probability should be set high at the nodes located in sparse areas and low for nodes located in dense areas. A straightforward method for estimating network density involves the periodic exchange of HELLO messages between neighbours to construct a 1-hop neighbour list at each node. A high (low) a number of neighbours implies that the node in a dense (sparse) area. We propose a simple scheme which increases the rebroadcast probability if the number of neighbours is low, which indirectly causes the probability at neighbouring nodes to be increased. In a similar fashion, the rebroadcast probability decreases if the number of neighbours is high. This adaptation causes a dynamic stability between rebroadcast probabilities and number of local neighbours among the nodes.

The adjusted probabilistic flooding algorithm operates as follows. On hearing a broadcast message m at node X, the node rebroadcast a message according to a high probability if the message is received for the first time, and the number of neighbours of node X is less than average number of neighbours typical of its surrounding environment. Hence, if node X has a low degree (in terms of the number of neighbours), retransmission should be likely. Otherwise, if X has a high degree its rebroadcast probability is set low.

We have compared the two versions of probabilisitc flooding, namely the fixed probability and the dynamically adjustable probability; the results for blind flooding have been added for the sake of completeness. Figure 25 shows that adjusting the re-broadcast probability significantly improves the number of saved rebroadcast when the probability ranges from 0.5 to 1.0 with 0.1% increment per trial for a network with 50 nodes and maximum speed 10 m/s and 0 pause time. Figure 26 explores the saved rebroadcast of the fixed probabilistic and the adjusted probability algorithm for various network densities. The saved rebroadcast when the broadcast probability is adjusted is 40% in low density networks (e.g., 25 nodes) and 50% in high density networks (e.g., 150 nodes). Reachability is above 95% in all cases regardless of the network density. The saved rebroadcast of the fixed probabilistic flooding when the probability is set at 0.7 is around 30% irrespective of the network density.

Fig. 25.

The saved rebroadcast against the rebroadcast probability with node speed 10 m/s.

Fig. 26.

Saved rebroadcast of three broadcast schemes against network density with node speed 10 m/s.

Figure 27 shows the results of reachability. This figure reveals that reachability increases when network density increases, regardless of what kind of the algorithms is used. The flooding algorithm has the best performance in reachability, reaching nearly 1. The performance of adjusted probability shows that the reachability is above 95% in any density of the network. In all network densities, the reachability of our Algorithm performs better than the probabilistic scheme with the probability assigned to 0.7. In higher density networks, i.e., 120 hosts and above, the reachability of our approach and flooding are very close. The reachability is close to 100%.

Fig. 27.

The reachability of three broadcast algorithms against the network size.

Conclusions

This paper has analysed the effects of node speed and pause time on the performance of the probabilistic approach to flooding (or broadcasting) in MANETs. Results from extensive ns-2 simulations have revealed that mobility and pause times have a substantial effect on the reachability and saved rebroadcast metrics. The results have shown that for different rebroadcast probabilities, as the node speed increases, reachability and saved rebroadcast increases. Moreover, as the pause time increases saved rebroadcast increases. Similar performance trends have been observed when the other important system parameters, notably node density and traffic load, have examined in that they have been found to have a great impact on the degree of reachability and the number of saved rebroadcasts achieved by the probabilistic broadcasting scheme.

This study highlights the great need for a new broadcasting strategy that can dynamically adjust the broadcast probability to take into account the current state of the node in two hopes in order to ensure a certain level of control over re-broadcasting, and thus helps to improve reachability and saved rebroadcasts. Another possible area for improving includes investigating the effect of nodes transmission ranges on the rebroadcast probability.

Muneer Masadeh Bani-Yassein

received his B.Sc. degree in Computing Science and Mathematics from Yarmouk University, Jordan in 1985 and M. Sc. in Computer Science, from Al Al-bayt University, Jordan in 2001. He is currently a Ph.D. candidate at the Department of Computing Science, University of Glasgow, U.K. His current research interests include networking protocol development and analysis the performance probabilistic flooding in mobile ad hoc networks.

Mohamed Ould-Khaoua

received his BSc degree from the University of Algiers, Algeria, in 1986, and the MAppSci and PhD degrees in Computer Science from the University of Glasgow, U.K., in 1990 and 1994, respectively. He is currently a Reader in the Department of Computing Science at the University of Glasgow, U.K. His research focuses on applying theoretical results from stochastic processes and queuing theory to the quantitative study of hardware and software architectures. Dr. Ould-Khaoua serves on the editorial board of IEEE Transactions on Parallel & Distributed Systems, International Journal of Parallel, Emergent and Distributes Systems, International Journal of Computers & Applications, and International Journal of High-performance Computing & Networking. He is the Guest Editor of 11 special issues related to performance modelling and evaluation of computer systems and networks in the Journal of Computation and Concurrency: Practice & Experience, Performance Evaluation, Supercomputing, Journal of Parallel & Distributed Computing, IEE-Proceedings-Computers & Digital Techniques, International Journal of High Performance Computing & Networking, and Cluster Computing. He is the Co-Chair of the international workshop series on performance modelling, evaluation, and optimisation of parallel and distributed systems (PMEO-PDS) and ACM Workshop on Performance Evaluation of Wireless Ad Hoc, Sensor, and Ubiquitous Networks (PE-WASUN), and International Workshop on Networks for Parallel, Cluster, and Grid Systems (PEN-PCGCS). He has served on the program committees of many international conferences and workshops. Dr. Ould-Khaoua’s current research interests are performance modelling/evaluation of wired/wireless communication networks and parallel/distributed systems.

Lewis M. Mackenzie

graduated with a B.Sc. in Mathematics and Natural Philosophy from the University of Glasgow, U.K., in 1980. He was awarded the PhD in 1984, also at the University of Glasgow, for his work in the development of multicomputers for use in nuclear physics. He is now a senior Lecturer at the Department of Computing Science at the University of Glasgow, which he joined in 1985. His current research interests include multicomputers, high-performance networks, and simulation.

Stylianos Papanastasiou

received his combined B.Sc. degree in Computing Science and Mathematics from the University of Glasgow, UK in 2002. He is currently a Ph.D. candidate at the Department of Computing Science, University of Glasgow, U.K. His current research interests include networking protocol development and analysis, and the study of protocol interaction in mobile ad hoc networks.