1 Introduction

RFC 6621 [1], simplified multicast forwarding (SMF), has recently been put forward as a technique for flooding messages across MANETs. Additionally, RFC 7367 [2] defines SMF-MIB which includes state and performance information. The protocol proposes a set of methods for flooding, namely, classical flooding (CF), source-based multipoint relay (S-MPR), essential connected dominating set (E-CDS), and multipoint relay connected dominating set (MPR-CDS). While RFC 6621 specifies that S-MPR should follow the flooding techniques used on OLSR (RFC 3626 [3]), OLSR.org’s implementation of OLSR [4] does not follow RFC 3626. This implementation is widely deployed and has been extensively used in research, for example, QualNet used the OLSR.org’s implementation. Therefore, including two variants of S-MPR, SMF allows five flooding algorithms.

Of these algorithms, classical flooding and the OLSR.org variant of S-MPR have been widely explored. CF was introduced nearly 22 years ago [5] and has been used in MANET protocols such as DSR [6,7,8] and AODV [9, 10]. Similarly, since S-MPR is the method used to flood control messages in OLSR (RFC 3626) and OLSRv2 [11], many papers have explored different aspects of its performance. However, the performance of E-CDS and MPR-CDS has not been studied as much as CF and S-MPR. A primary objective of this paper is to compare the performance of these protocols. To this end, we extend the computational performance evaluation method in [12]. This method allows performance evaluation in a wide range of scenarios with much less computational effort than would be required if packet simulations were used.

In the 22 years since CF was introduced, extensive research has focused on flooding [3, 11, 13, 14]. The basic goal is to reduce overhead while ensuring that the packet reaches all nodes in the network. In practice, each method achieves a different trade-off between overhead and coverage, i.e., the average fraction of nodes that receive the message. The overhead and coverage of different methods widely vary. In CF, every node acts as a relay in a network, whereas in MPR-CDS, only a reduced set of nodes (i.e., a subset of MPR nodes), act as relays to reduce the overhead. For point of discussion, let’s assume that CF has better coverage than MPR-CDS but has twice as much overhead in a certain network environment. In this case, for MPR-CDS to achieve better coverage than single message flooding, it could simply flood the same message twice and still have similar overhead as CF. To understand this possibility of proactive retransmissions better, we explore two types of retransmissions, namely, originator-based retransmissions where the originator refloods the message multiple times, and relay-based retransmissions, where each node that has been selected by the protocol to relay the message retransmits the message multiple times. We develop a model of both types of retransmissions and explore the optimal number of retransmissions. Thus, we explore three retransmission schemes, namely, where the message is transmitted once, where the originator refloods the message an optimal number of times, and where each node that relays the message retransmits the message an optimal number of times.

Overhead and coverage are the main flooding performance metrics considered in this paper. Different flooding methods achieve different trade-offs between overhead and coverage, and these trade-offs differ in different scenarios. As a result, it is difficult to select a best method for a given scenario. On the other hand, a key motivation for reducing overhead is to lessen interference. If other aspects of performance are constant when interference is reduced, the network is able to deliver more data packets. With this in mind, we compare the performance of the SMF methods for different flooding message generation rates. The idea is that while a method such as CF generates excessive overhead by all the nodes sending messages too frequently in the network, interference will limit the fraction of nodes that receive messages. Therefore, the SMF methods can be compared by examining the mean fraction of nodes that receive messages as a function of the rate at which messages are generated and flooded. From this perspective, methods that achieve good coverage at the expense of high overhead will show good performance for low message generation rates. On the other hand, methods that use overhead more efficiently might have better coverage as the message generation rate increases. An interesting finding of this work is that when considering coverage as a function of message generation rate, CF with originator-based optimal transmission achieves the highest coverage in lower node densities (around less than 7 neighbors per nodeFootnote 1) and at all message generation rates. However, CF achieves the lowest coverage in higher node densities (around more than 12). Another aspect is the radio rate. Since higher radio rates favor brute force method (i.e., CF), the number of neighbors per node resulting in between CF’s better and worse coverage than other methods may depend on radio rate.

In summary, this paper makes the following key contributions.

  • An efficient performance model of the flooding methods proposed in RFC 6621.

  • A performance model of proactive retransmissions and the relationship of originator-based and relay-based retransmissions.

  • A comprehensive comparison of the performance of the flooding methods based on a wide range of 3,500,000 scenarios.

2 Related work

In [15], an early research on SMF was performed and the protocols, E-CDS and MPR-CDS, were not yet included in their performance comparison. The authors used four fixed example topologies consisting of 1 or 2 hop networks with 10 nodes in their network emulation. In [16], all protocols in RFC 6621 were examined with 25 nodes. Average network nodal connectivity ranged from 24.1 to 25, and hence 1 or 2 hop networks were consisted in their 10 random topologies. Both [15, 16] greatly showed SMF performance comparison with various metrics, but the 1 or 2 hop networks are not enough to understand how these protocols perform in terms of coverage, which is a key performance metric. In [17], several network coding schemes were examined using SMF as one of broadcast protocols. They used only 11–14 nodes and performed 10 simulation runs in the NS-2 network simulator. Lacharit et al. [18] proposed CRC SMF used at a gateway and tested it with 10 nodes on a 4 hop network in a real test bed. Comparison with CF, E-CDS, and MPR-CDS was not considered.

Another way to disseminate flooding messages is a probabilistic rebroadcast [19,20,21,22]. Especially, Saeed et al. [19] derived the optimal rebroadcast probabilities as a function of the node density, the transmission range, and the dissemination distance. However, this paper determines the optimal number of retransmissions as a function of coverage, overhead, flooding message generation rate, and background traffic.

In [23,24,25,26], various flooding/broadcasting methods were well described, categorized (e.g., deterministic/non-deterministic methods), compared, analyzed, or proposed (e.g., Smart-flooding). Either originator-based or relay-based retransmissions of a flooding message was not considered in those methods. However, Wong et al. [27] considered originator-based retransmissions and they called it k -Flooding algorithm. Additionally, originator-based retransmissions were implicitly considered in RFC 3626. OLSR specifies that TC messages are generated periodically, even when there is no change in the data carried in the message. Therefore, the same message is periodically flooded across the network. To the best of our knowledge, proactive relay-based retransmissions of a flooding message have not been investigated as a way to improve flooding.

3 Summary of flooding methods considered

3.1 Classic flooding (CF)

In CF, every node simply participates in packet forwarding and hence all nodes act as relays in a network. Since CF does not consider the subset of nodes in the network as relays, it eliminates the need for the information of neighborhood topology (e.g., from NHDP [RFC6130]) and the selection of relays based on the information.

In flooding, each node that receives a new packet forwards this packet exactly once. The packet propagation will depend on the traffic and go through all possible paths. Thus, this simple routing method will have higher coverage (i.e., the fraction of nodes reached by a single message flooding) than other methods below.

3.2 S-MPR (source-based MPR)

In S-MPR, the subset of nodes is selected as relays based on the neighborhood topology information. Here, each relay is called MPR (multi-point relay). Each node selects its own one-hop MPRs which cover the most two-hop neighbors. The node that selected a MPR is called MPR selector of the MPR. In flooding, packets will pass through only MPRs/relays. This reduces the number of transmissions due to the reduced relay-set forwarding. However, it cannot utilize all possible paths like CF. Especially, if the estimation of neighborhood topology is incorrect, S-MPR will suffer from low coverage, not reaching all nodes. Here, unreliable broadcast was used rather than multiple reliable unicasts.

In S-MPR, the forwarding depends on the source (i.e., one-hop sender) of the received packet. OLSR (RFC 3626) and OLSR.org belong to this method and they forward the packet slightly differently. In both, each node does not forward the packet if the packet source is not MPR selector of the node. OLSR does not forward the packet if it has been seen before from non-MPR selector or MPR selector. However, OLSR.org forwards the packet even if it has been seen before from non-MPR selector. Thus, OLSR.org will have slightly higher coverage than OLSR.

3.3 E-CDS (essential connected dominating set)

In E-CDS, each node decides whether it is a relay or not and forms CDS. This self-election eliminates the forwarding dependency on the source of the received packet. Each node computes its own rank which consists of (Router Priority, Router ID), where Router Priority is an optional nodal metric (e.g., nodal degree) and Router ID is a logical identification used for a tie-breaker. In a self-election process, each node checks that its rank is the highest in symmetric neighbors. If that is the case, the node elects itself to act as a relay. If not, the node checks that the one-hop neighbor with the highest rank among one-hop neighbors can reach all other one-hop neighbors through intermediate neighbors with higher rank than this node. If the path search succeeds, the node does not elect itself as a relay. Otherwise, it does. The success of path search means that one of neighbors will be more likely to be selected as a relay that is more reachable to other nodes than this node.

In flooding, each relay that receives a new packet relays this packet exactly once and each non-relay that receives a new or old packet does not relay this packet.

3.4 MPR-CDS (MPR-based CDS)

In MPR-CDS, each MPR decides whether it is a relay or not and forms CDS. MPRs are selected as in S-MPR and then relays are selected among MPRs. In self-election process, each MPR checks that its rank is highest in one-hop neighbors. If so, the MPR elects itself as a relay. If not, the MPR checks that the one-hop neighbor with the highest rank in one-hop neighbors is the MPR selector of this MPR. If so, the MPR elects itself as a relay. Otherwise, it does not. The flooding method is the same as E-CDS.

4 Definitions

In this paper, we study the performance of different flooding methods. A key performance metric is the fraction of nodes that a flooded message reaches. We refer to this fraction as the reaching probability. In some cases, some nodes are disconnected from the network. In this case, these nodes will never be reached for any flooding method. The fraction of nodes that are disconnected depends on the node density. In this paper, we are not interested in how this fraction of nodes are disconnected, but in how the fraction of connected nodes are reached. Thus, we define the normalized reaching probability to be the average number of nodes that receive the flooded message divided by the maximum number of nodes that could receive the flooded message when classical flooding is used, there is no interference, the nodes have stopped moving (i.e., their locations are frozen), and the message is reflooded a large number of times.

5 Proactive retransmissions

Two methods are investigated. First, we consider the case where the originator refloods the same message multiple times. Second, we investigate the case where nodes selected to relay the message transmit the message multiple times. We refer to these methods as originator-based retransmissions and relay-based retransmissions, respectively. Note that both methods have approximately the same overhead. For example, if CF is used with K retransmissions and each message reaches every node in a network of N nodes, then there are \((K+1)\times N\) packet transmissions.Footnote 2 However, the coverage is considerably different. For example, consider the case of a string topology shown in Fig. 1 where the probability of a successful packet transmission to a neighbor is p. If the originator refloods a message K times, then the probability that a node m hops away will get the message is \(p^{m}\). On the other hand, if each node relays the message \((K+1)\) times whenever it gets the message at least once, then the probability that a node m hops away gets the message is \(( 1-( 1-p) ^{(K+1)}) ^{m}\), where \(p^{m}\) goes to zero much faster than \(( 1-( 1-p) ^{(K+1)}) ^{m}\). For example, the Taylor expansion around \(1-p=0\) of the ratio of these probabilities is

$$\begin{aligned} \frac{\left( 1-\left( 1-p\right) ^{(K+1)}\right) ^{m}}{p^{m}}=1+m\left( 1-p\right) +O\left( 1-p\right) ^{2}, \end{aligned}$$
(1)

which grows linearly with the number of hops from the originator.

Fig. 1
figure 1

The string topology. The probability of successful packet transmission to a neighbor is p

Full size image

5.1 Simulation setup for numerical or packet level approach

This paper presents a comprehensive performance comparison of five flooding methods. Table 1 details the simulation setup. We determine the performance for various number of nodes in two simulated regions and for five different levels of interference, which depend on background traffic. For each different number of nodes, 400 topologies were generated, an originator was selected from the topology at random, and the same topologies and originators are used over different background traffic and flooding methods. One message was flooded and then the same message was reflooded 50 times from the originator or each relay. In each scenario, averages and distributions are derived from these 2000 samples. The total number of scenarios is \(7\times 400\times 50\times 5\times 5=3{,}500{,}000\). Packet level simulation is too computationally complex to evaluate the performance in all these scenarios. Instead, we extend a performance model developed by [28, 29].

Table 1 Numerical or packet level simulation setup
Full size table

The background traffic was distributed uniformly across the network. Specifically, each node broadcasts a packet according to a Poisson process. The size of packets was 200B. For example, if the interference level was 1.25 kbps, each node generated a packet to be broadcast on average once every \((200\times 8)/1250\) s. Random waypoint mobility was used where nodes were distributed according to the stationary distribution [30]. Nodes did not move during the simulation.

Packet simulations with some part of the same scenarios above were used to validate the performance model in Sects. 6 and 8.4. The packet simulation results presented are from QualNet simulations. In packet simulation, originator-based retransmissions are only considered and implemented.

5.2 Performance model of proactive retransmissions

When a message is reflooded multiple times, we expect that a different set of nodes might receive the message for each flood. Hence, the fraction of nodes that received the reflooded message either the first or second time might be larger than the fraction of nodes that received the message only after the first transmission. On the other hand, there might be some nodes that are simply disconnected from the network. In this case, even if the message is retransmitted many times, this disconnected node will not receive the message.

For originator-based retransmissions, we can model the number of messages received by a node as a Binomial distributed random variable. Specifically, for a fixed originator, each node i in a network has a probability \(p_{i}\) of receiving the message. Thus, \(1/p_{i}\) is the mean number of retransmissions required for node i to get the message. If \(p_{i}\) is very small for some nodes, then, on average, these nodes can be reached only after a large number of retransmissions. For example, if \(p_{i}\) is Bernoulli distributed, i.e., \(p_{i}=1\) with probability \(\rho\) and \(p_{i}=0\) otherwise, then retransmissions will have no impact. On the other hand, if \(p_{i}\) follows some other distribution, then retransmissions might be effective. Therefore, assuming this model is accurate, the distribution of \(p_{i}\) is a key indicator of the effectiveness of retransmissions.

Through simulations, we found that for the originator-reflooded messages, \(p_{i}\) is beta distributed. This model of the distribution of \(p_{i}\) held for all five flooding methods. However, the distribution parameters depend on the flooding method. Figure 2 shows the complementary cumulative distribution function (CCDF) of \(p_{i}\) along with a fitted CCDF of a beta distributed random variable. Here S-MPR was used on a network with 123 nodes and different background traffic. As shown in Fig. 2, the distribution depends on the number of hops away from the originator. More specifically, we compute the mean number of hops which a flooded message travels to reach the destination, where we ignore messages that never reach the destination. As expected, when the node is close to the originator, \(p_{i}\) is usually close to 1. However, for nodes further away from the originator, \(p_{i}\) can take a wide range of values. This indicates that for large networks where nodes are far from the originator, proactive retransmissions can be effective in reaching more nodes.

Fig. 2
figure 2

The distribution of a message reaching probability. The distribution per hop is fitted with a beta distribution

Full size image

For relay-based retransmissions, the binomial distribution model used for originator-based retransmission cannot be used. Consider the case where only one transmission is used. In this case, relay-based one transmission is the same as originator-based one transmission. And hence, for one message transmission, the performance of these methods is the same. Now suppose that a very large number of retransmissions is used. In this case again, both methods will reach the same fraction of node. More specifically, for both methods, at least one message will reach every node that is not disconnected. Therefore, both methods reach the same fraction of nodes for one transmission and they reach the same limiting fraction of nodes as the number of retransmissions grows toward infinity. The difference between two methods is that relay-based retransmissions converge to the maximum fraction of reachable nodes faster than originator-based retransmissions.

From simulations, we find that for relay-based retransmissions, the fraction of nodes reached converges to the maximum possible fraction slightly slower than exponentially fast one. Specifically, let \(R_{RB}(k)\) be the normalized fraction of nodes reached after relay-based k retransmissions. Let \(R_{OB}(k)\) be the same quantity, but after originator-based k retransmissions. We found that a good approximation of \(R_{RB}\) is \(\hat{R}_{RB}\) as follows.

$$\begin{aligned} \hat{R}_{RB}(k) :=1-\left( 1-R_{OB}(0) \right) e^{\left( -\left( \frac{k-1}{a}\right) ^{b}\right) }, \end{aligned}$$
(2)

where a and b are parameters used to determine the relationship of the message reaching probabilities between originator-based and relay-based retransmissions. Figure 3 shows several scaled fractions of nodes reached, which are \(\left( R_{RB}(k) -R_{OB}(0) \right) /\left( 1-R_{OB}(0) \right)\) and \((\hat{R}_{RB}(k) -R_{OB}(0))/1-R_{OB}(0)\), for 123 node topology with different background traffic. As can be observed, the rate of convergence does not depend on the background traffic, and hence the curves for different background traffic are indistinguishable.

Fig. 3
figure 3

The scaled fraction of nodes reached for relay-based retransmissions. The approximation of the normalized fraction of nodes reached after relay-based k retransmissions (i.e., \(\hat{R}_{RB})\) has a good fit over all background traffic with parameter \(a=0.75\) and \(b=0.69\) in Eq. (2)

Full size image

These models of \(R_{OB}\) and \(R_{RB}\) provide a clear qualitative and quantitative view of the impact of retransmissions. For example, if \(k \ge \left( \frac{1}{a}\log \left( \frac{1-R_{OB}(0) }{0.05} \right) \right) ^{1/b} + 1\) and relay-based retransmissions are used, then over 95% of nodes are reachable. If a model of the overhead is given, then we can use these models to determine the optimal number of retransmissions. But more importantly, these models show that proactive retransmissions can be an effective way to increase the fraction of nodes that receive a message. These models give motivation to OLSR’s method for retransmitting the same TC message.

6 Performance modeling

This paper seeks to compare the performance of five flooding methods where each method can use originator-based retransmissions or relay-based retransmissions with any number of retransmissions. Moreover, we seek to make this comparison in a wide range of scenarios. In summary, we seek to model performance over a very large parameter space. Consequently, the packet level simulation approach is computationally difficult. Instead, this study extended the models developed by [28, 29]. Briefly, the model utilizes analytic methods and numerical simulation; specifically, analytic methods are used to determine which nodes act as relays, while numerical simulation is used to flood the message. As mentioned in Sect. 3, the methods proposed in RFC 6621 utilize neighbor information in order to determine which nodes relay a message. The broadcast of Hello messages is used to determine neighbors. Specifically, if a Hello message is received and the Hello message includes information that the transmitter also received a Hello message from the receiver, then the receiver declares that the link between the transmitter and the receiver is bidirectional. On the other hand, if a link is bidirectional and yet no Hello message has been received for 3 Hello Periods, then the link is declared to be broken. When transmission error probability is between zero and one, the state of a link is a random variable. A key contribution of [28] is the model of the distribution of this random variable. With this distribution, the set of bidirectional links can be selected. Once the bidirectional links are known, the various flooding methods can be applied to compute which nodes will relay which packets. Then, we can numerically simulate a message being flooded, where the probability of a particular transmission being successful depends on the channel between the transmitter and receiver and on the interference.

It is important to note that while numerical simulation is used to flood the message, no packet simulation of Hello messages is required. It turns out that in packet level simulation, a very large number of Hello messages must be transmitted to get a good estimate of flooding performance. Consequently, eliminating Hello message broadcast in numerical simulation reduces the computational complexity by several orders of magnitude [12].

Fig. 4
figure 4

Comparison of message reaching probabilities between packet simulation and performance model. The data rates of the curves refer to the background traffic

Full size image

Figure 4 compares message reaching probabilities from our performance model and those from packet level simulations for 53 nodes and S-MPR. In most cases, the modeling error is small. Figure 5(a) and (b) give insight into the model performance over a range of scenarios. Specifically, Fig. 5(a) shows the complementary cumulative distribution function (CCDF) of the absolute error for each number of nodes, where the CCDF is over all the flooding methods, all the background traffic, all numbers of originator-based retransmissions (0–50), and 400 sample topologies. Figure 5(b) shows the same information, but one curve for each of the five flooding methods. As can be observed, the mean and the median of the error are quite small. Table 2 details the error statistics.

Fig. 5
figure 5

The complementary cumulative distribution of absolute error between the fractions of nodes reached from packet simulation and that from performance model. The left plot a is based on each different number of nodes and right plot b is based on each different flooding method. The absolute errors are quite small in both cases

Full size image
Table 2 Error statistics for different scenarios
Full size table

7 Comparison of flooding methods for single message delivery

With the performance model discussed in Sect. 6, we can compare the flooding methods. In this initial comparison, we will only consider the performance of a single flooded message. Figure 6 shows the average overhead versus the average normalized fraction of nodes that received the message. For each flooding method, 0–50 retransmissions were used. Hence, for each flooding method, we have a curve where the lowest overhead and reaching probability point correspond to the case where only one transmission (i.e., zero retransmission) is used and the highest overhead and reaching probability point corresponds to when 50 retransmissions are used. Figure 6(a) and (b) shows the performance when originator-based retransmissions are used and Fig. 6(c) and (d) shows the performance for relay-based retransmissions, where each figure shows the trade-off for two levels of interference, namely no background traffic and 9 kbps background traffic.

Fig. 6
figure 6

The relationship between overhead and coverage over all five routing protocols. The first two plots are from the originator-based retransmissions and the others are from the relay-based retransmissions. The plots of a and c are from 0 kbps background traffic and the rest are from 9 kbps. Those plots clearly show different trade-offs between overhead and coverage for two levels of interference (i.e., 0 or 9 kbps) and over all protocols

Full size image

As expected, by varying the flooding method and the number of retransmissions, different trade-offs between overhead and coverage are achieved. For a given method and number of retransmissions, another method and number of retransmission is better if the overhead is lower and the coverage is higher. In other words, the point of the second method (e.g., Point B in Fig. 6b) is to the right of the first method’s point (e.g., Point A) and also below it.

The performance of E-CDS, S-MPR, and OLSR.org is similar, but S-MPR and OLSR.org are slightly better than E-CDS in some regions. When the background traffic is low (i.e., low interference), no method is better than Classical Flooding (CF), but in high background traffic scenarios, CF is similar to the E-CDS, S-MPR, and OLSR.org in some regions. In most cases, MPR-CDS is not better than any other method.

While the number of retransmissions was limited to 50, the trend is clear in that as the number of retransmissions increases from 0 to a small number, the coverage increases significantly. The coverage convergence rate of relay-based retransmissions is faster than originator-based retransmissions. The coverage tends toward an upper limit while the overhead increases toward infinity. The upper limit of the coverage of the more recently developed flooding methods is considerably smaller than the upper limit achieved by CF.

It is important to note that interference between two message floods is not considered here. Thus, if the message is retransmitted many times, these multiple retransmissions are assumed to be spaced in time so that they do not interfere with each other. However, interference is a critical by-product of overhead. Hence, the impact of overhead is considered next.

8 Comparison of flooding methods for message streams

The previous analysis shows how different flooding methods make trade-offs between overhead and coverage. In this section, we seek to compare the methods in their ability to deliver streams of data, specifically where nodes generate messages randomly (i.e., according to a Poisson process). For high message generation rates, message floods originated by different nodes will interfere, possibly limiting the coverage of the flood. Intuitively, for very low message generation rates, floods will never interfere. In this case, the overhead has no impact on performance. As the message generation increases, the overhead will impact performance. Thus, in this section, we compare the coverage as a function of message generation rate.

8.1 Modeling the overhead as interference

The performance of flooding depends on the interference. On the other hand, the amount of interference depends on the performance of the flooding methods. Therefore, there is a feedback between flooding performance and overhead. Let F(I, K) be the fraction of nodes that receive a message when the interference rate is I and there are K retransmissions (\(K=0,1,\ldots ,50\)). I is all traffic generated by a node and its unit is bytes/sec/node. Let O(I) be the overhead generated by a flood when the interference rate is I. The unit of O(I) is bytes/node/flood. In numerical simulation with a set of sample I and K, F(I, K) and O(I) were precomputed numerically. Given I and \(K, F(I,K) =\frac{R}{N}\), where R is the number of nodes that received the flooding message and N is the total number of nodes. Given \(I, O(I) =\frac{M}{N}\times S\), where M is total number of flooding messages and S is the packet size (bytes). If there are K retransmissions, then the overhead is \((K+1)\times O(I)\). Assume that an originator generates a new message to be flooded at a rate of \(\rho\) messages/s. Then, letting T be the total overhead rate, we have \(T=\rho (K+1)O(I) +B,\) where B is background traffic, which we assume is independent of interference. Since overhead causes interference, we have

$$\begin{aligned} I=\rho (K+1)O(I) +B. \end{aligned}$$
(3)

This equation is used to solve for I. Once I is known for K retransmissions, we can compute F(I, K) .

One important metric is power consumption. Power consumption directly depends on the overhead. If we assume that each flooding message requires J watt, the average power consumption is \(J\times \frac{M}{N}\), which is \(\frac{J}{S}\times O(I)\).

8.2 Optimal number of retransmissions

From (3), we clearly see that the interference increases with K. On the other hand, from Sect. 7, we know that the fraction of nodes that receive a message increases with the number of retransmissions. We expect that as the number of retransmissions increases, the overhead will grow so large that it will limit the number of nodes that receive the message. More generally, for a fixed message generation rate, we seek the optimal number of retransmissions.

Note that in the limiting case of when the message generation rate is zero, the retransmissions can be spaced out so that retransmissions do not impact the performance. Indeed, from (3), we see that the flooding method does not contribute to interference when \(\rho =0\). Therefore, in this case, the optimal number of retransmissions is infinite. However, for other values of \(\rho\), we expect that the optimal number of retransmissions is finite, where the optimal value might be very large for small values of \(\rho\), but decreases as \(\rho\) increases.

Figure 7 shows the optimal number of retransmissions for different flooding methods. As expected, the optimal number of retransmissions decreases as the message generation rate increases. Each flooding method has its own best number of retransmissions to achieve maximum coverage.

Fig. 7
figure 7

The optimal number of retransmissions to achieve the maximum coverage at each message generation rate

Full size image

Note that the models and analysis provided in the previous sections allow the computation of the optimal number of retransmissions. However, for this comparison, we computed the optimal number by trying all different numbers of retransmissions and selecting the one that results in the highest coverage.

8.3 Performance comparison

Figure 8 shows the performance for the different flooding methods for zero retransmission (i.e., one transmission), for the optimal number of retransmissions when originator-based retransmissions are used, and for the optimal number of retransmissions when relay-based retransmissions are used. When retransmissions are not used, CF with 123 nodes results in better coverage at all message generation rates. The performance of the different methods seems to converge at high message generation rates. However, the network is highly congested at such a high generation rate. For example, in the case of four messages per second per node, CF is only able to reach around half of the nodes as compared to when the message generation rate is near zero. One hopes that the network is not driving into such a low performing scenario. CF with 300 nodes results in better coverage at the lower message generation rates (less than 1), but the performance gets worse than other methods except OLSR.org as the message generation rate increases.

Fig. 8
figure 8

The fraction of nodes reached for 123 and 300 nodes and three cases; one transmission of a flooding message, the originator-based optimal retransmission, and the relay-based optimal retransmission

Full size image

When originator-based retransmissions are used, CF with 123 nodes still result in the highest fraction of nodes reached. However, the difference between CF and the other methods is much smaller than when retransmissions are not used. Other methods have similar coverage and as the message generation rate increases, their performance is indistinguishable. MPR-CDS with lower node density appears to consistently have lower performance, but it has some higher performance with higher node density. In case of 300 nodes, the curves of other methods become similar to CF at the lower message generation and CF still results in lower performance at the higher message generation rates.

When the optimal number of relay-based retransmissions is used, the situation changes. Here, all methods have similar coverage, when the message generation rate is low. But once the message generation rate grows beyond 1 message per second per node, CF results in lower coverage as compared to all other methods.

It is well known that CF has high coverage and high overhead. Therefore, at low message generation rate, CF will have the highest coverage. However, as the message generation rate increases, the overhead of CF should cause significant self-interference and limit coverage. On the other hand, one might assume that a method which uses overhead more efficiently might have low coverage for low message generation rates, but then better coverage than CF as message generation rate increases. However, this assumption does not consider the robustness of the method. Specifically, as message generation rate increases, interference increases, and therefore, the probability of transmission error increases. This increase in transmission error causes an increase in the error of the local topology information, which is critical to the correct function of efficient flooding methods. Consequently, as the message generation rate increases, efficient flooding methods fail to maintain high coverage. However, as node density increases, one relay covers more nodes and hence the difference of the number of relays or overhead between CF and efficient flooding methods increases. Therefore, efficient flooding methods overcome the error of the local topology information at some point of node density.

Fig. 9
figure 9

The contour of the ratio of the fraction of nodes reached from CF and one from S-MPR, considering a wide range of the number of nodes and message generation rate

Full size image

Figure 9 provides a comprehensive performance comparison between CF and S-MPR. The plots show the ratio of the coverage achieved by CF and the coverage achieved by S-MPR. This ratio is shown for a wide range of the number of nodes and message generation rate. The conclusions are similar to those drawn from Fig. 8. The obvious trend is that CF is better than S-MPR in an area of smaller number of nodes and lower message rates, but the size of the area becomes smaller and smaller and the area is driven into the lower left corner, when sequentially considering one transmission, originator-based optimal retransmission, and relay-based optimal retransmission.

8.4 Packet level simulations

Because of computational complexity, a comprehensive performance comparison such as the one found in Sect. 8.3 is not possible with packet simulation. However, the simulation results from the analytic and numerical approaches need to be validated by using packet level simulations. Because the packet level simulations are time-consuming and requires lots of effort of protocol modifications after thorough understanding of protocol implementations in QualNet, only originator-based retransmissions with 123 nodes is considered, implemented, and simulated in QualNet.

Fig. 10
figure 10

The fraction of nodes reached from the packet simulations over all five protocols. The retransmission clearly increases the fraction at lower message generation rate

Full size image

Figure 10 shows the fraction of nodes that receive a message for different numbers of originator-based retransmissions and for different message generation rates. We can use these plots to select the number of retransmissions that result in the highest coverage. Figure 11 compares the different flooding methods where no retransmissions are used and where the optimal number of retransmissions is used. These packet simulations confirm our performance analysis of Sect. 8.3, specifically that CF with 123 nodes results in better performance over the other methods. Moreover, the performance of the other methods is indistinguishable. As predicted by the model-based results in Sect. 8.3, when originator-based retransmissions are used, the difference between the methods is reduced.

Fig. 11
figure 11

The packet simulation results of the fraction of nodes reached as a function of message generation rate

Full size image

9 Conclusions

This paper presents a summary of work focused on the performance of the flooding methods proposed in RFC 6621, simplified multicast forwarding. Each flooding method achieves a different trade-off between overhead and coverage. To gain further insight, we studied overhead and coverage when messages are generated at different rates. In this case, the overhead of each method causes more interference and limits the coverage. Moreover, as our contributions, we derived the relationship of coverage between originator-based and relay-based retransmissions in (2) and derived the total interference causing with a certain number of retransmissions at a message rate and background traffic rate in (3). Our efficient analytic methods and numerical simulations made it possible to evaluate a wide range of scenarios with much less computational effort. In this paper, 3,500,000 scenarios were evaluated. Packet level simulations with some part of all scenarios were performed to confirm our performance analysis.

We found that CF had better coverage than efficient flooding methods in scenarios where node density and message generation rate are low. However, both originator-based and relay-based optimal retransmissions improved coverage of efficient flooding methods, and we observed that relay-based optimal retransmissions were more effective. When sequentially considering one transmission, originator-based optimal retransmission, and relay-based optimal retransmission, CF coverage becomes lower and lower than those of efficient flooding methods at the higher node density and faster message generation rate.

Many practical applications have their own objectives, depending on a trade-off between overhead and coverage. For example, a critical mission with many soldiers in a battle field requires very high coverage to successfully send an important command to all soldiers. In this case, the relay-based optimal retransmissions method with a relay-set reduced routing protocol will be a good choice. Similarly, our proposed model will provide the best possible communication coverage to an emergency response team for their critical tasks.

Designing a new protocol for the estimation of the optimal number of retransmissions in the real world, implementing the new protocol in a packet-level simulator (e.g., QualNet), comparing the actual and estimated optimal number of retransmissions, and observing the influence of the new protocol on the flooding performance are our future research directions.