# Adaptive Probabilistic Broadcasting over Dense Wireless  Ad Hoc Networks

Authors: Victor Gau; Jenq-Neng Hwang
Journal: International Journal of Digital Multimedia Broadcasting
 (2010)

---

## Abstract

We propose an idle probability-based broadcasting method,iPro, which employs an adaptive probabilistic mechanism to improve performance of data broadcasting over dense wireless ad hoc networks.  In multisource one-hop broadcast scenarios, the modeling and simulation results of the proposed iPro are shown to significantly outperform the standard IEEE 802.11 under saturated condition.  Moreover, the results also show that without estimating the number of competing nodes and changing the contention window size, the performance of the proposed iPro can still approach the theoretical bound.  We further apply iPro to multihop broadcasting scenarios, and the experiment results show that within the same elapsed time after the broadcasting, the proposed iPro has significantly higher Packet-Delivery Ratios (PDR) than traditional methods.


---

## Body

## 1. Introduction

Classical performance analyses for multihop broadcast mostly focus on single-source sporadic broadcasting over network topologies with appropriate network densities.  In the paper, we examine the scenarios that two or more sources continuously broadcast over the network at the same time, and observe that the packet-delivery performance  of traditional methods degrades along with the increases of the network density and the number of broadcast sources.  To improve the broadcast performance, we propose an adaptive probabilistic mechanism,iPro, which operates atop standard IEEE 802.11 with constant contention window-size.  The proposed method was first analyzed in one-hop saturated scenarios, where the modeling and ns2 simulation results show that the proposed iPro approaches theoretical throughput maximum.  After that, the proposed iPro integrating with counter-based scheme  is further applied to multihop broadcast scenarios, where the performance of the proposed method is also significantly better than existing methods.A wireless ad hoc network consists of a set of nodes where the data delivery among nodes does not depend on any infrastructure; instead, nodes self-organize and relay messages among one another.  A Mobile ad hoc Network (MANET) is a kind of wireless ad hoc network with mobility.  Typically, a node in MANETs does not have fixed mobility patterns, and the power of the node would be limited.  A Vehicular ad hoc Network (VANET) is a special case of MANET, with less concern on power consumption, intended for vehicles to communicate with other vehicles or with the road side infrastructures.Broadcast is a common communication operation in wireless ad hoc networks.  In proactive routing, a node needs to exchange information with neighbors by using one-hop broadcasting, also called beaconing, to update its routing table.  In reactive routing, a node commonly broadcasts a routing request packet across multiple hops to the destination node to build a route.  In VANETs, one-hop broadcasting is also used to exchange vehicular information like position and speed of each other to achieve cooperative awareness, and multihop broadcasting is also used for emergency warning message delivery.  In battle fields or disaster recovery scenarios, broadcasting can be used to deliver messages or even voice information among nodes to further assist the cooperation for different tasks.In ad hoc networks, especially in VANETs, the densities of the networks vary a lot.  In rural areas, it is likely that there are only intermittent connections via nearby cars since the network density is very low.  In urban areas, the network density is relatively higher.  In an extreme case of a congested highway, assuming there are four lanes and there is one vehicle every 20 m with a radio range of 300 m, theoretically every node has 120 vehicles within its transmission range [1].  With the increase of the density, it is more likely the network will work under a saturated condition, that is, the condition that all nodes have packets queued for transmission.  As the VANETs are getting  more and more deployed, it is foreseeable that the ad hoc network will be easily saturated and results in excessive contentions and collisions that makes the network unreliable.  Therefore, it is important to design a method that improves the overall performance when the network density increases and the network condition becomes congested.A recent experimental study, where a many-to-many broadcast scenario in a single-hop 802.11 network with up to 100 nodes, was conducted over the ORBIT test-bed [2]. The experiments first considered a periodic vehicular safety message broadcasting scenario, where each node generated and transmited 10 packets per second, with each packet of size 128 bytes. With the transmission rate at 6 Mbps, most nodes could successfully receive and decode the 100 streams of messages with the mean packet-delivery ratio (PDR) of 95%, where the PDR denotes the percentage of packets that are successfully transmitted. When the network scenario was further stretched to a saturation workload, where each node generated and transmitted packets at the maximum possible rate, the mean throughput dropped to 56%, since almost all frames were involved in collisions. This implies that a better broadcast scheme for dense and congested wireless networks is critically needed.The performance degradation of IEEE 802.11 in broadcasting over congested networks is due to one of the characteristics of IEEE 802.11, that is, the contention window-size does not change in broadcasting.  Since the source node does not know if the message is encountering collisions or not, there is no exponential backoff in broadcasting when collisions happen.  There have been adaptive contention window-size methods proposed in literature; however, the minimum and maximum contention window-sizes in the current IEEE 802.11 standard are hardwired in the PHY layer and cannot make adaptive in response to the number of competing nodes [3].In this paper, we propose an idle probability-based broadcasting method,iPro, which employs adaptive probabilistic mechanism to improve performance of data broadcasting over wireless ad hoc networks.  The proposed method operates atop IEEE 802.11 with constant contention window-size; therefore, least change of IEEE 802.11 MAC layer is made to realize our method.  The modeling and ns2 simulation results show that the proposed method significantly outperforms standard IEEE 802.11 in one-hop and multihop broadcasting in dense wireless ad hoc networks.The rest of the paper is organized as follows: Section2 presents related works.  Section 3 introduces our proposed iPro method.  Section 4 presents the modeling and simulation results.  Finally, Section 5 concludes this paper.


## 2. Related Works

The most common technique used for multihop broadcasting is simple flooding, where all the nodes that receive a new packet will schedule the rebroadcast of the packet; and thus, redundant messages cause serious resource consumption, channel contention, and collision—the so-called broadcast storm problem [4].  In literature, almost all methods for broadcast storm mitigation in a multihop scenario are based on heuristics, lacking  rigorous mathematical reasoning.  In contrast to heuristic-based multihop broadcasting, mathematical modeling has been introduced to assess the throughput performance of nodes within each other’s one-hop broadcast range.  To simplify the modeling, the channel is usually assumed to be ideal, that is, without packet loss and hidden node problems; and, the collisions are caused by the same backoff time.  In this section, we review the heuristic-based multisource multihop broadcast methods and mathematically analyze multisource one-hop broadcast methods.


### 2.1. Multihop Broadcasting

Ni et al. [4] analyzed the broadcast storm problems based on redundant rebroadcast, contention, and collision.  Several simple mitigation techniques were introduced, including counter-based, probabilistic, distance-based, location-based, and cluster-based schemes.  A counter-based scheme sets a predefined counter value Cth.  Once a node that receives the same packet for greater than or equal to Cth times, it stops rebroadcasting the packet, otherwise it continues to schedule the rebroadcasting.  Similarly, a probabilistic scheme also sets a predefined probability value Pth.  Once a node that receives a new packet, it rebroadcasts the packet based on Pth, that is, generate a random number Pr, if Pr>Pth, then stop rebroadcasting, otherwise schedule the rebroadcast.  Simple flooding is a special case of probabilistic scheme with Pth=1.  Similarly, in distance-based scheme, a distance threshold Dth is defined and used to judge if rebroadcasting is required.  In a location-based scheme, the position information based on Global Positioning Systems (GPS) or other positioning devices is further used to judge if rebroadcasting is required.  In a cluster-based scheme, the nodes are organized into clusters, for example, Cluster Based Routing Protocol (CBRP) [5], a gateway is chosen to deliver messages to cluster members, so that the redundant transmissions can be minimized.  It was concluded in [4] that the counter-based scheme can eliminate many redundant rebroadcasts efficiently in a dense network.  If the location information is available for the nodes, for example, nodes have GPS capabilities, then a location-based method is the best choice to eliminate even more redundant rebroadcasts without compromising the amount of nodes receiving the message.In addition to Ni et al.’s approaches, Williams and Camp  [6] compared several neighbor knowledge-based schemes in details by examining the performances of these methods in congested networks, mobile networks, and so on.  The idea of neighbor knowledge-based schemes is to rebroadcast data based on neighbor information, which can be collected by periodic exchanging of “Hello” messages among neighbors.  Once the neighbor information is collected, different algorithms can be applied to reduce the broadcast storm based on the neighbor information.  In general, all these methods need to jitter the scheduling of rebroadcasting packets to reduce the probability of collisions.  Most methods adopt a “Random Assessment Delay (RAD)” timer and keep the packets in the network layer before RAD expires.  Once RAD expires, the packets are sent to MAC layer for broadcasting. RAD is a random delay uniformly distributed on [0,Tmax].  The RAD can range up to 0.1 second depends on the network configuration.  Based on the comparative simulation results, it was concluded in [6] that the increased network density can disproportionately hurt the performance of probabilistic and counter-based methods in terms of saved rebroadcasts.  The schemes utilize RAD need to adaptively adjust RAD to avoid suffering from congestive networks.  In mobile environment, some neighbor knowledge-based schemes can also suffer from outdated neighbor information and result in performance degradation.One of the most popular neighbor knowledge-based methods is called Scalable Broadcast Algorithm (SBA) [7].  The basic idea of SBA is that if all of a node’s one-hop neighbors have received the broadcast message, then the node does not need to rebroadcast the message.  The SBA consists of two phases: local neighborhood discovery and data broadcasting.  The nodes first exchange “Hello” messages with its neighbors.  All nodes encapsulate their neighbors’ information into the “Hello” message, so that each node can collect neighbor’s information within two-hops.  Every time when a node receives a broadcast packet, it updates the covered set table according to the sender.  Once the node finds out that all of its neighbors have been covered, it stops rebroadcasting the message.There have been several subsequent researches, which proposed methods to adaptively adjust the broadcast probability-based on the neighbors’ information.  Zhang and Agrawal  [8] proposed an adaptive probabilistic approach that the broadcast probability was adjusted based on a packet counter, which counts the number of times the same packet is received to infer the density of the neighborhood.  Hanashi et al. [9] proposed an adaptive method that the broadcast probability is updated based on the number of the neighbors, n.  To be more specific, when n>0, the rebroadcast probability p is set to max(Pmin,Pmaxn) with (Pmin,Pmax) being empirically set as (0.4,0.9).


### 2.2. One-Hop Broadcasting in a Saturated Condition

It has been shown [10, 11] that, in an 802.11-based wireless local area network (WLAN), the throughput drops significantly along with the increase of the network density in a saturated condition.  As pointed out in [12, 13] that the 802.11 standard, due to the use of different network configuration, can achieve the performance very far from the theoretical throughput limit, and an appropriate tuning of the backoff algorithm by changing contention window-size can significantly increase the throughput.Bianchi et al. [10, 11] introduced a discrete Markov model to model IEEE 802.11 CSMA/CA mechanism under a unicast scenario.  The transmission probability in a steady state of a saturated condition was derived, and the dynamics among multiple nodes contending for the same channel was also modeled.  Further, an adaptive contention window approach to maximizing the throughput of a WLAN was proposed.  To calculate the optimal contention window-size, the number of competing nodes needs to be estimated.There have been several approaches proposed to estimate the number of competing nodesn.  In [10], the number of busy slots was used to infern.  In [14], the number of competing nodes n was expressed as a function of the collision probability encountered on the channel.  An extended Kalman filter equipped with a change detection mechanism was proposed to estimate the number of competing nodes.  In [15], a Bayesian approach was proposed to optimize the backoff parameters of the distributed coordination function (DCF) based on the predictive distribution of the number of competing nodes.Due to the difficulty and complexity of estimating the number of competing nodes,n, alternative methods without explicitly estimating the number of competing nodes have been proposed.  In [16], the authors pointed out that when n≥4, the productn·p0* could be very close to an asymptotic value, with  p0* being  the optimal transmission probability that achieves maximized throughput.  It was also shown thatn·p0* is a tight upper bound of slot utilization (SU), which is defined as the ratio of the number of busy slots to the number of available slots.  Based on this observation, Asymptotically Optimal Backoff (AOB) was proposed.  The basic idea of AOB contains two steps: the first step is to estimate the SU, the broadcast transmission of the node is enabled in the second step only when SU is less than or equal to n·p0*.In addition to the theoretical analysis done for unicast behavior in WLANs, Ma and Chen  [12] extend Bianchi’s discrete Markov model  and apply it to the ad hoc one-hop broadcasting scenario.    Two discrete Markov models, one with and one without consecutive freeze process (CFP) [12, 17], were compared and discussed in the paper.   It is pointed out that if the contention window-size is small compared to the number of the stations in the network, the CFP cannot be ignored in the analytical model.  Also, if the CFP effect is neglected, the optimal contention window-size could be calculated based on n and Tσ where n is the number of competing nodes and Tσ is the packet duration measured in slots.In summary, the goal of broadcast storm mitigation methods in multihop broadcasting scenarios is to regulate the number of nodes that need to rebroadcast the packets, and at the same time maintain or improve the reliability of the broadcasting.  As pointed out previously, the methods proposed for mitigating broadcast storms in ad hoc networks are mostly based on heuristics with little theoretical foundation.  On the other hand, the theoretical analyses derived for multisource one-hop broadcasting are mostly limited to applications that all nodes are within each other’s one-hop transmission range, and cannot be directly applied to multihop scenarios, since the assumption of ideal channels, that is, no packet loss and hidden node problems, is violated in multihop scenarios.  In addition, in order to achieve the maximized throughput in one-hop broadcast scenario, an reliable estimation of the number of competing nodes,n, is inevitable.  However, the method for estimating the number of competing nodes can be complicated and difficult to be applied in throughput maximization algorithms.  Therefore, in the following section, we introduce a heuristic-based method that can be effectively applied to both one-hop and multihop scenarios; and at the same time, we also verify the throughput performance of the proposed method with the theoretical bound in a one-hop broadcast scenario under saturated conditions so as to theoretically validate the advantages of the proposed method in both one-hop and multihop scenarios.


## 2.1. Multihop Broadcasting

Ni et al. [4] analyzed the broadcast storm problems based on redundant rebroadcast, contention, and collision.  Several simple mitigation techniques were introduced, including counter-based, probabilistic, distance-based, location-based, and cluster-based schemes.  A counter-based scheme sets a predefined counter value Cth.  Once a node that receives the same packet for greater than or equal to Cth times, it stops rebroadcasting the packet, otherwise it continues to schedule the rebroadcasting.  Similarly, a probabilistic scheme also sets a predefined probability value Pth.  Once a node that receives a new packet, it rebroadcasts the packet based on Pth, that is, generate a random number Pr, if Pr>Pth, then stop rebroadcasting, otherwise schedule the rebroadcast.  Simple flooding is a special case of probabilistic scheme with Pth=1.  Similarly, in distance-based scheme, a distance threshold Dth is defined and used to judge if rebroadcasting is required.  In a location-based scheme, the position information based on Global Positioning Systems (GPS) or other positioning devices is further used to judge if rebroadcasting is required.  In a cluster-based scheme, the nodes are organized into clusters, for example, Cluster Based Routing Protocol (CBRP) [5], a gateway is chosen to deliver messages to cluster members, so that the redundant transmissions can be minimized.  It was concluded in [4] that the counter-based scheme can eliminate many redundant rebroadcasts efficiently in a dense network.  If the location information is available for the nodes, for example, nodes have GPS capabilities, then a location-based method is the best choice to eliminate even more redundant rebroadcasts without compromising the amount of nodes receiving the message.In addition to Ni et al.’s approaches, Williams and Camp  [6] compared several neighbor knowledge-based schemes in details by examining the performances of these methods in congested networks, mobile networks, and so on.  The idea of neighbor knowledge-based schemes is to rebroadcast data based on neighbor information, which can be collected by periodic exchanging of “Hello” messages among neighbors.  Once the neighbor information is collected, different algorithms can be applied to reduce the broadcast storm based on the neighbor information.  In general, all these methods need to jitter the scheduling of rebroadcasting packets to reduce the probability of collisions.  Most methods adopt a “Random Assessment Delay (RAD)” timer and keep the packets in the network layer before RAD expires.  Once RAD expires, the packets are sent to MAC layer for broadcasting. RAD is a random delay uniformly distributed on [0,Tmax].  The RAD can range up to 0.1 second depends on the network configuration.  Based on the comparative simulation results, it was concluded in [6] that the increased network density can disproportionately hurt the performance of probabilistic and counter-based methods in terms of saved rebroadcasts.  The schemes utilize RAD need to adaptively adjust RAD to avoid suffering from congestive networks.  In mobile environment, some neighbor knowledge-based schemes can also suffer from outdated neighbor information and result in performance degradation.One of the most popular neighbor knowledge-based methods is called Scalable Broadcast Algorithm (SBA) [7].  The basic idea of SBA is that if all of a node’s one-hop neighbors have received the broadcast message, then the node does not need to rebroadcast the message.  The SBA consists of two phases: local neighborhood discovery and data broadcasting.  The nodes first exchange “Hello” messages with its neighbors.  All nodes encapsulate their neighbors’ information into the “Hello” message, so that each node can collect neighbor’s information within two-hops.  Every time when a node receives a broadcast packet, it updates the covered set table according to the sender.  Once the node finds out that all of its neighbors have been covered, it stops rebroadcasting the message.There have been several subsequent researches, which proposed methods to adaptively adjust the broadcast probability-based on the neighbors’ information.  Zhang and Agrawal  [8] proposed an adaptive probabilistic approach that the broadcast probability was adjusted based on a packet counter, which counts the number of times the same packet is received to infer the density of the neighborhood.  Hanashi et al. [9] proposed an adaptive method that the broadcast probability is updated based on the number of the neighbors, n.  To be more specific, when n>0, the rebroadcast probability p is set to max(Pmin,Pmaxn) with (Pmin,Pmax) being empirically set as (0.4,0.9).


## 2.2. One-Hop Broadcasting in a Saturated Condition

It has been shown [10, 11] that, in an 802.11-based wireless local area network (WLAN), the throughput drops significantly along with the increase of the network density in a saturated condition.  As pointed out in [12, 13] that the 802.11 standard, due to the use of different network configuration, can achieve the performance very far from the theoretical throughput limit, and an appropriate tuning of the backoff algorithm by changing contention window-size can significantly increase the throughput.Bianchi et al. [10, 11] introduced a discrete Markov model to model IEEE 802.11 CSMA/CA mechanism under a unicast scenario.  The transmission probability in a steady state of a saturated condition was derived, and the dynamics among multiple nodes contending for the same channel was also modeled.  Further, an adaptive contention window approach to maximizing the throughput of a WLAN was proposed.  To calculate the optimal contention window-size, the number of competing nodes needs to be estimated.There have been several approaches proposed to estimate the number of competing nodesn.  In [10], the number of busy slots was used to infern.  In [14], the number of competing nodes n was expressed as a function of the collision probability encountered on the channel.  An extended Kalman filter equipped with a change detection mechanism was proposed to estimate the number of competing nodes.  In [15], a Bayesian approach was proposed to optimize the backoff parameters of the distributed coordination function (DCF) based on the predictive distribution of the number of competing nodes.Due to the difficulty and complexity of estimating the number of competing nodes,n, alternative methods without explicitly estimating the number of competing nodes have been proposed.  In [16], the authors pointed out that when n≥4, the productn·p0* could be very close to an asymptotic value, with  p0* being  the optimal transmission probability that achieves maximized throughput.  It was also shown thatn·p0* is a tight upper bound of slot utilization (SU), which is defined as the ratio of the number of busy slots to the number of available slots.  Based on this observation, Asymptotically Optimal Backoff (AOB) was proposed.  The basic idea of AOB contains two steps: the first step is to estimate the SU, the broadcast transmission of the node is enabled in the second step only when SU is less than or equal to n·p0*.In addition to the theoretical analysis done for unicast behavior in WLANs, Ma and Chen  [12] extend Bianchi’s discrete Markov model  and apply it to the ad hoc one-hop broadcasting scenario.    Two discrete Markov models, one with and one without consecutive freeze process (CFP) [12, 17], were compared and discussed in the paper.   It is pointed out that if the contention window-size is small compared to the number of the stations in the network, the CFP cannot be ignored in the analytical model.  Also, if the CFP effect is neglected, the optimal contention window-size could be calculated based on n and Tσ where n is the number of competing nodes and Tσ is the packet duration measured in slots.In summary, the goal of broadcast storm mitigation methods in multihop broadcasting scenarios is to regulate the number of nodes that need to rebroadcast the packets, and at the same time maintain or improve the reliability of the broadcasting.  As pointed out previously, the methods proposed for mitigating broadcast storms in ad hoc networks are mostly based on heuristics with little theoretical foundation.  On the other hand, the theoretical analyses derived for multisource one-hop broadcasting are mostly limited to applications that all nodes are within each other’s one-hop transmission range, and cannot be directly applied to multihop scenarios, since the assumption of ideal channels, that is, no packet loss and hidden node problems, is violated in multihop scenarios.  In addition, in order to achieve the maximized throughput in one-hop broadcast scenario, an reliable estimation of the number of competing nodes,n, is inevitable.  However, the method for estimating the number of competing nodes can be complicated and difficult to be applied in throughput maximization algorithms.  Therefore, in the following section, we introduce a heuristic-based method that can be effectively applied to both one-hop and multihop scenarios; and at the same time, we also verify the throughput performance of the proposed method with the theoretical bound in a one-hop broadcast scenario under saturated conditions so as to theoretically validate the advantages of the proposed method in both one-hop and multihop scenarios.


## 3. Proposed Method

In this section, we propose an idle probability-based broadcasting scheme,iPro, which adaptively adjusts rebroadcast threshold based on idle probability to approach throughput maximum in a multisource one-hop broadcast scenario.


### 3.1. Idle Probability-Based Broadcasting, iPro

The channel idle probability,P̃idle(u), is defined as the percentage of no radio transmission among all nodes at a particular time.  Intuitively, if P̃idle(u) is high, it is less likely that broadcasting the packet can cause collision.  On the other hand, if P̃idle(u) is low, broadcasting a packet is more likely to cause collisions.  Therefore, we can adaptively adjust the transmission/broadcast probability-based on the channel idle probability to improve the performance of standard IEEE 802.11.  More specifically, the approach that we employ to adjust transmission probability is to use  P̃idle(u)  as a broadcast threshold.  When a node finishes backoff countdown, it draws a random number pr and compares with the threshold.  If pr is less than the threshold, the node will broadcast the packet.  Otherwise, the node will enter another round of backoff countdown by using the same contention window-size.  In our implementation, the idle probability (P̃idle(u)) is estimated as
(1)P̃idle(u)=T̃idle(u)T̃idle(u)+T̃busy(u),
where T̃idle(u) denotes average idle period and T̃busy(u) denotes average busy period.T̃idle(u) and T̃busy(u) can further be empirically approximated as
(2)T̃idle(u)=(1-α)⋅T̃idle(u-1)+α⋅Tidle(u),T̃busy(u)=(1-β)⋅T̃busy(u-1)+β⋅Tbusy(u),
where α and β denote smoothness coefficient, Tidle(u) is the uth measure of the idle duration, and Tbusy(u) is the uth measure of the busy duration (as shown in Figure 1).Figure 1
The conceptual diagram of idle and busy durations.Once the channel idle probabilityP̃idle(u) is available, a simple while effective broadcast mechanism, iPro, is described  in Figure 2, where the contention window-size in each node is set to be a constant, W, without binary exponential backoff.  When a node finishes backoff countdown in a normal CSMA/CA, it draws another random number pr over [0,1].  If the random number is less than the broadcast threshold (i.e., the empirically approximated idle probability), the node will broadcast; otherwise, the node will enter another backoff based on the same contention window-size, W.  Therefore, each node would continuously enter into rebackoff stages which result in a longer total backoff time (a similar effect as the exponential increase of  W  in CSMA/CA of standard 802.11); thus, an equivalently lower transmission probability is generated to reduce the collision probability.Figure 2
The conceptual diagram ofiPro.The pseudo code foriPro algorithm is as in Algorithm 1.Algorithm 1:
Periodically update channel idle probabilityP̃idle(u)based on (1).On Backoff timer expires:Generate a random numberpr over [0,1]ifpr<P̃idle(u)transmit the packetelseentering rebackoffendNote that, in the rebackoff process, the node enters another backoff stage with the same contention window-size.


### 3.2. Modeling iPro in a One-Hop Saturated Condition

To better understand the theoretical foundation of the proposediPro, in this subsection we will analytically model the throughput performance of iPro in a one-hop saturated condition.  Let us assume the channel is ideal, that is, the channel is error free and there is no hidden node problem. The consecutive freeze process (CFP) is also neglected in the modeling.  In a broadcast scenario, a node has a fixed contention window, W, without retransmission, nor exponential backoff.Given a wireless ad hoc network, where all then competing nodes are within one-hop neighboring range, the probability of no transmission, Px(n)=P{nt=0}, and the probability of at least one transmission, Ptr(n)=P{nt≥1}, where nt is the number of transmitting nodes, in a given slot can be calculated by(3)Px(n)=P{nt=0}=(1-p)n,(4)Ptr⁡(n)=P{nt≥1}=1-(1-p)n,
where p is the transmission probability of a node.The probability that a node successfully transmits a packet,Ps(n)=P{nt=1}, can be calculated as follows:
(5)Ps(n)=P{nt=1}=np(1-p)n-1.The probability that a node experiences a collision,Pc(n)=P{nt>1}, can be expressed as(6)Pc(n)=P{nt>1}=1-Px(n)-Ps(n).Letσ denote the time for one slot of backoff counting down, Ts denote the average time the channel is sensed busy by each node during a successful transmission, and Tc denote the average time the channel is sensed busy because of a collision.  Ts and Tc are measured in the unit of σ.  The throughput (S), which is defined as the ratio between total number of bits of successfully delivered packets and the time elapsed for the transmission, can be expressed as [10],
(7)S=P{nt=1}⋅PLP{nt=0}σ+P{nt=1}Ts+P{nt>1}Tc,
where PL is the payload size in bytes.  Since we assume that the channel is ideal and no hidden node problem is present,   the collisions are only due to the same backoff time; therefore, Ts=Tc=T.The normalized throughput that is often used as a performance metric in literature [10] is then defined as
(8)S′=P{nt=1}⋅PL/RcP{nt=0}σ+P{nt≥1}T,
where Rc is the transmission rate of each 802.11 node.  In our modeling and simulation, we assume Rc equals 1 Mbps.  Also, the Packet-Delivery Ratio (PDR), which is often used as a performance metric, can be calculated as
(9)PDR(n)=P{nt=1}∑i=1ni⋅P{nt=i}=np(1-p)n-1np=(1-p)n-1.As discussed previously that Bianchi et al. [10] employed a discrete Markov model to model the CSMA/CA backoff mechanism in a saturated condition with binary exponential backoff turned off.  In their derivation, at any time slot, a node has a transmission probability of p=p0=2/(W+1), where W is the contention window-size.  Once the contention window-size is decided and fixed, the transmission probability is fixed even when the network density increases in a saturated condition.  It is obvious that when the network density increases, and all nodes are still transmitting with the same probability, the possibility of collision will increase along with the increase of the network density.IniPro, due to the use of repeated backoff process governed by the channel idle probability, the transmission probability P0(n,t), which determines whether a node can transmit/broadcast the data at time t, with n competing nodes, can thus be expressed as
(10)P0(n,t)=p0⋅P̂idle(n,t),
where p0=2/(W+1) is the original transmission probability after contention window-size is chosen, and the weighting term P̂idle(n,t) represents an exponential moving average of the modeled value, Pidle(n,t), of the measured channel idle probability at each time instant, that is,
(11)P̂idle(n,t)=(1-ξ)⋅P̂idle(n,t-1)+ξ⋅Pidle(n,t),
where ξ is a smoothness control factor.Equation (1) shows that the channel idle probability is defined as the ratio of T̃idle(u) and (T̃idle(u)+T̃busy(u)). T̃busy(u) can be approximated by T, that is, the packet duration, as shown in Figure 3, in a one-hop broadcasting scenario.  And, T̃idle(u) is the average number of consecutive idle slots, as shown in Figure 4.Figure 3
Structure of a transmission period of the broadcast packet.Figure 4
The idle duration consists of several consecutive idle slots.Therefore,T̃idle(u) can be approximated by the mean (T̅idle) of a geometric distribution as shown in (12)
(12)T̅idle=∑i=0∞i⋅P{nt=0}i(1-P{nt=0})=P{nt=0}1-P{nt=0}⋅σ.Thus,Pidle can be modeled as
(13)Pidle=P{nt=0}/(1-P{nt=0})⋅σP{nt=0}/(1-P{nt=0})⋅σ+T=P{nt=0}⋅σP{nt=0}⋅σ+(1-P{nt=0})⋅T.Therefore, the measured channel idle probability can be theoretically and recursively approximated byPidle(n,t) in
(14)Pidle(n,t)=Px′(n,t)σPx′(n,t)σ+Ptr⁡′(n,t)T,
where T denotes the packet duration, as shown in Figure 3.  The theoretical channel idle and busy probabilities, Px′(n,t) and Ptr′(n,t), can be inferred from (3) and (4), that is,
(15)Px′(n,t)=(1-P0(n,t))n,Ptr⁡′(n,t)=1-(1-P0(n,t))n.Notice thatP̃idle(u) is the channel idle probability calculated by the average values of measured idle and busy durations, Tidle(u) and Tbusy(u), Pidle in (13) is the expected channel idle probability when p is given, and  P̂idle(n,t) is the modeled channel idle probability.  The modeling of iPro is based on (10)–(15) where different n values are plugged in the equation to calculate the throughput and PDR; however, in actual implementation, the idle probability is continuously calculated from the ratio of the measured idle and busy duration of the channel according to (1), and a node is not necessary to know the number of competing nodes, n, for the calculation of the channel idle probability.


### 3.3. Applying iPro to Multihop Broadcasting Scenarios

As mentioned earlier in Section2, basically a broadcast storm mitigation approach consists of two techniques, that is, reducing redundancies and avoiding collisions, to improve the reliability and efficiency of the broadcasting.  iPro can be viewed as a method to avoid collisions by adaptively adjusting rebroadcast threshold.  Therefore, to further mitigate the broadcast storm in multihop scenarios, we incorporate the counter-based scheme with iPro to reduce redundancies of packet transmission.The pseudocode foriPro is listed in Section 3.1, and the pseudocode of counter-based algorithm, to be integrated with iPro, for multihop broadcasting is as in Algorithm 2.Algorithm 2:
On Initialization:Cth= 3On receiving a packetdi:ifdi is a new packetputdi into queuesetCi=1elseCi=Ci+1endifCi≥CthdropdiendNotice thatCi is initialized to 1 when a node receives its ith packet for the first time.


## 3.1. Idle Probability-Based Broadcasting, iPro

The channel idle probability,P̃idle(u), is defined as the percentage of no radio transmission among all nodes at a particular time.  Intuitively, if P̃idle(u) is high, it is less likely that broadcasting the packet can cause collision.  On the other hand, if P̃idle(u) is low, broadcasting a packet is more likely to cause collisions.  Therefore, we can adaptively adjust the transmission/broadcast probability-based on the channel idle probability to improve the performance of standard IEEE 802.11.  More specifically, the approach that we employ to adjust transmission probability is to use  P̃idle(u)  as a broadcast threshold.  When a node finishes backoff countdown, it draws a random number pr and compares with the threshold.  If pr is less than the threshold, the node will broadcast the packet.  Otherwise, the node will enter another round of backoff countdown by using the same contention window-size.  In our implementation, the idle probability (P̃idle(u)) is estimated as
(1)P̃idle(u)=T̃idle(u)T̃idle(u)+T̃busy(u),
where T̃idle(u) denotes average idle period and T̃busy(u) denotes average busy period.T̃idle(u) and T̃busy(u) can further be empirically approximated as
(2)T̃idle(u)=(1-α)⋅T̃idle(u-1)+α⋅Tidle(u),T̃busy(u)=(1-β)⋅T̃busy(u-1)+β⋅Tbusy(u),
where α and β denote smoothness coefficient, Tidle(u) is the uth measure of the idle duration, and Tbusy(u) is the uth measure of the busy duration (as shown in Figure 1).Figure 1
The conceptual diagram of idle and busy durations.Once the channel idle probabilityP̃idle(u) is available, a simple while effective broadcast mechanism, iPro, is described  in Figure 2, where the contention window-size in each node is set to be a constant, W, without binary exponential backoff.  When a node finishes backoff countdown in a normal CSMA/CA, it draws another random number pr over [0,1].  If the random number is less than the broadcast threshold (i.e., the empirically approximated idle probability), the node will broadcast; otherwise, the node will enter another backoff based on the same contention window-size, W.  Therefore, each node would continuously enter into rebackoff stages which result in a longer total backoff time (a similar effect as the exponential increase of  W  in CSMA/CA of standard 802.11); thus, an equivalently lower transmission probability is generated to reduce the collision probability.Figure 2
The conceptual diagram ofiPro.The pseudo code foriPro algorithm is as in Algorithm 1.Algorithm 1:
Periodically update channel idle probabilityP̃idle(u)based on (1).On Backoff timer expires:Generate a random numberpr over [0,1]ifpr<P̃idle(u)transmit the packetelseentering rebackoffendNote that, in the rebackoff process, the node enters another backoff stage with the same contention window-size.


## 3.2. Modeling iPro in a One-Hop Saturated Condition

To better understand the theoretical foundation of the proposediPro, in this subsection we will analytically model the throughput performance of iPro in a one-hop saturated condition.  Let us assume the channel is ideal, that is, the channel is error free and there is no hidden node problem. The consecutive freeze process (CFP) is also neglected in the modeling.  In a broadcast scenario, a node has a fixed contention window, W, without retransmission, nor exponential backoff.Given a wireless ad hoc network, where all then competing nodes are within one-hop neighboring range, the probability of no transmission, Px(n)=P{nt=0}, and the probability of at least one transmission, Ptr(n)=P{nt≥1}, where nt is the number of transmitting nodes, in a given slot can be calculated by(3)Px(n)=P{nt=0}=(1-p)n,(4)Ptr⁡(n)=P{nt≥1}=1-(1-p)n,
where p is the transmission probability of a node.The probability that a node successfully transmits a packet,Ps(n)=P{nt=1}, can be calculated as follows:
(5)Ps(n)=P{nt=1}=np(1-p)n-1.The probability that a node experiences a collision,Pc(n)=P{nt>1}, can be expressed as(6)Pc(n)=P{nt>1}=1-Px(n)-Ps(n).Letσ denote the time for one slot of backoff counting down, Ts denote the average time the channel is sensed busy by each node during a successful transmission, and Tc denote the average time the channel is sensed busy because of a collision.  Ts and Tc are measured in the unit of σ.  The throughput (S), which is defined as the ratio between total number of bits of successfully delivered packets and the time elapsed for the transmission, can be expressed as [10],
(7)S=P{nt=1}⋅PLP{nt=0}σ+P{nt=1}Ts+P{nt>1}Tc,
where PL is the payload size in bytes.  Since we assume that the channel is ideal and no hidden node problem is present,   the collisions are only due to the same backoff time; therefore, Ts=Tc=T.The normalized throughput that is often used as a performance metric in literature [10] is then defined as
(8)S′=P{nt=1}⋅PL/RcP{nt=0}σ+P{nt≥1}T,
where Rc is the transmission rate of each 802.11 node.  In our modeling and simulation, we assume Rc equals 1 Mbps.  Also, the Packet-Delivery Ratio (PDR), which is often used as a performance metric, can be calculated as
(9)PDR(n)=P{nt=1}∑i=1ni⋅P{nt=i}=np(1-p)n-1np=(1-p)n-1.As discussed previously that Bianchi et al. [10] employed a discrete Markov model to model the CSMA/CA backoff mechanism in a saturated condition with binary exponential backoff turned off.  In their derivation, at any time slot, a node has a transmission probability of p=p0=2/(W+1), where W is the contention window-size.  Once the contention window-size is decided and fixed, the transmission probability is fixed even when the network density increases in a saturated condition.  It is obvious that when the network density increases, and all nodes are still transmitting with the same probability, the possibility of collision will increase along with the increase of the network density.IniPro, due to the use of repeated backoff process governed by the channel idle probability, the transmission probability P0(n,t), which determines whether a node can transmit/broadcast the data at time t, with n competing nodes, can thus be expressed as
(10)P0(n,t)=p0⋅P̂idle(n,t),
where p0=2/(W+1) is the original transmission probability after contention window-size is chosen, and the weighting term P̂idle(n,t) represents an exponential moving average of the modeled value, Pidle(n,t), of the measured channel idle probability at each time instant, that is,
(11)P̂idle(n,t)=(1-ξ)⋅P̂idle(n,t-1)+ξ⋅Pidle(n,t),
where ξ is a smoothness control factor.Equation (1) shows that the channel idle probability is defined as the ratio of T̃idle(u) and (T̃idle(u)+T̃busy(u)). T̃busy(u) can be approximated by T, that is, the packet duration, as shown in Figure 3, in a one-hop broadcasting scenario.  And, T̃idle(u) is the average number of consecutive idle slots, as shown in Figure 4.Figure 3
Structure of a transmission period of the broadcast packet.Figure 4
The idle duration consists of several consecutive idle slots.Therefore,T̃idle(u) can be approximated by the mean (T̅idle) of a geometric distribution as shown in (12)
(12)T̅idle=∑i=0∞i⋅P{nt=0}i(1-P{nt=0})=P{nt=0}1-P{nt=0}⋅σ.Thus,Pidle can be modeled as
(13)Pidle=P{nt=0}/(1-P{nt=0})⋅σP{nt=0}/(1-P{nt=0})⋅σ+T=P{nt=0}⋅σP{nt=0}⋅σ+(1-P{nt=0})⋅T.Therefore, the measured channel idle probability can be theoretically and recursively approximated byPidle(n,t) in
(14)Pidle(n,t)=Px′(n,t)σPx′(n,t)σ+Ptr⁡′(n,t)T,
where T denotes the packet duration, as shown in Figure 3.  The theoretical channel idle and busy probabilities, Px′(n,t) and Ptr′(n,t), can be inferred from (3) and (4), that is,
(15)Px′(n,t)=(1-P0(n,t))n,Ptr⁡′(n,t)=1-(1-P0(n,t))n.Notice thatP̃idle(u) is the channel idle probability calculated by the average values of measured idle and busy durations, Tidle(u) and Tbusy(u), Pidle in (13) is the expected channel idle probability when p is given, and  P̂idle(n,t) is the modeled channel idle probability.  The modeling of iPro is based on (10)–(15) where different n values are plugged in the equation to calculate the throughput and PDR; however, in actual implementation, the idle probability is continuously calculated from the ratio of the measured idle and busy duration of the channel according to (1), and a node is not necessary to know the number of competing nodes, n, for the calculation of the channel idle probability.


## 3.3. Applying iPro to Multihop Broadcasting Scenarios

As mentioned earlier in Section2, basically a broadcast storm mitigation approach consists of two techniques, that is, reducing redundancies and avoiding collisions, to improve the reliability and efficiency of the broadcasting.  iPro can be viewed as a method to avoid collisions by adaptively adjusting rebroadcast threshold.  Therefore, to further mitigate the broadcast storm in multihop scenarios, we incorporate the counter-based scheme with iPro to reduce redundancies of packet transmission.The pseudocode foriPro is listed in Section 3.1, and the pseudocode of counter-based algorithm, to be integrated with iPro, for multihop broadcasting is as in Algorithm 2.Algorithm 2:
On Initialization:Cth= 3On receiving a packetdi:ifdi is a new packetputdi into queuesetCi=1elseCi=Ci+1endifCi≥CthdropdiendNotice thatCi is initialized to 1 when a node receives its ith packet for the first time.


## 4. Modeling and Simulation Results

The proposediPro is simulated in two different scenarios: multisource one-hop broadcasting and multisource multihop broadcasting.  In the first scenario, we compare the modeling and simulation results of our proposed method with the standard IEEE 802.11, the optimal contention window-size method [10], and the adaptive contention window-size method in a saturated condition [10].  The modeling results are based on the derivation in Section 3.2.  In the second scenario, we compare the broadcast efficiency and reliability of our proposed method with simple flooding, counter-based broadcasting, and Scalable Broadcast Algorithm (SBA) [7].Both scenarios were simulated overns2.  The first scenario was simulated over a 50 × 50 m2 network topology, while the second one over 500 × 500 m2 topology. All the nodes were uniformly distributed inside the network topology.  The numbers of nodes in the first scenario range from 10 to 100 with increments of 10, while they range from 100 to 500 with increments of 50 in the second scenario.  The transmission range is set to 100 meters and the carrier sensing range is set to 250 meters.  The capture effect was turned off, and the extended interframe space (EIFS) was disabled.  The contention window-size (W) was set to 32 and 64 in the simulations, respectively.  The payload size was set to 128 bytes, and the broadcast was performed at an 802.11 node transmission rate of 1 Mbps.  The smoothness coefficients, that is, α, β, and ξ, were empirically set to 0.1 in the modeling and simulations.Notice that in the first scenario, all the nodes on the network topologies always have packets queued for broadcast and they do not rebroadcast packets after receiving them from other nodes.  On the contrary, in the second scenario, there are at most four broadcast sources; however, nodes will rebroadcast the packets accordingly after receiving them from other nodes.  Table1 shows the parameters used in the simulation.Table 1
Parameters used in thens2 simulation.
Scenario 1Scenario 2Number of nodes10–100100–500Number of sources10–1001–4Map size (m2)50×50500×500Transmission range (m)100100Carrier sense range (m)250250Contention window size32, 6432, 64Data rate (Mbps)11Payload size (bytes)128128Packets per second (PPS)50010The performance metrics used in the simulations are as follows.(i)
Packet-Delivery Ratio (PDR): average number of packets received in each receiver node.(16)PDR=1Nr∑i=1Nrnp(i)Np,
where Nr is the total number of the nodes, np(i)is total number of packets received by the ith receiver node, and Np is the total number of the packets transmitted from the sources.(ii)
Normalized Throughput (S′):
(17)S′=Ns⋅PL⋅8Te⋅Rc,
where Te is the simulation time, Rc is the transmission rate used for broadcasting, that is, 1 Mbps, PL is the payload size in bytes, and Ns is the total number of successful transmissions.


### 4.1. Multisource One-Hop Broadcasting

In this simulation, the packet arrival rate to a node was set to 500 packets per second (pps) to guarantee that all nodes consistently have packets queued for transmission.  The nodes start broadcasting at 0.1 second and the simulation ends at 20 seconds.  The data were collected and analyzed after 20 seconds.  Four methods are compared in the simulations: standard IEEE 802.11, optimal contention windows size method, adaptive contention window-size method, andiPro. The optimal contention window-size used in the modeling and simulation is based on (13) in [10] with n given in advance, and the adaptive contention window-size method in the simulation is based on (1)–(4) from [10].Figure5 shows the modeling results and the ns2 simulation results.  The curves for different methods are listed in the legend.  The ns2 simulation results are shown to be very consistent with the modeling results.  The slight difference of the PDR performance between modeling and simulation for standard IEEE 802.11 is believed to be caused by the consecutive freeze process.  And the slight difference of the PDR performance for the proposed method is believed to be due to the fluctuation of the measured channel idle probability.  The differences are also observed in the normalized throughput.PDR and normalized throughput for payload equal 128 bytes.
(a)
PDR(b)
Normalized throughputBoth modeling andns2 simulation results show that by simply feeding back the channel idle probability, the results can be improved significantly, especially when the network density becomes higher.  When the number of neighbor nodes is 100, the PDR of the proposed method is more than seven times of the default IEEE 802.11 method; moreover, the normalized throughput of the proposed method is very close to the theoretical bounds, as shown in Figure 5(b).


### 4.2. Multisource Multihop Broadcasting

In this scenario, the packet arrival rate of a node was set to 10 packets per second (pps).  Four methods were compared in this scenario: simple flooding, counter-based flooding, Scalable Broadcast Algorithm (SBA), and the proposediPro with counter-based method.  The nodes start broadcasting for 5 seconds at 7.5 second; and the simulation ends when all nodes finish broadcasting.  In SBA, the neighbor information were exchanged every 5 seconds; and the 7.5 second initial waiting time is intended for SBA to effectively collecting neighbor information before broadcast starts. The simulations were conducted with one to four sources broadcast over a 500 × 500 m2 network topology.Figure6 shows the PDR of different number of sources broadcast at the same time.  When only one source is broadcasting over a moderate dense topology, the PDR appears to be close to 1, as shown in Figure 6(a).  However, when the network density becomes higher, the packet-delivery ratio starts to drop.  Figures 6(b)–6(d) show that, for traditional methods, when there are more than one source broadcasting together, PDRs are further degraded by the cross traffic.  In the simulation, the proposed method consistently outperforms traditional methods when network density or number of sources increase.  When all other methods have PDRs lower than 50%, the proposed method still maintains more than 85% PDR.PDRs of multisource multihop broadcasting scenario whenW=32.
(a)(b)(c)(d)Figure7 shows the simulation results with the same experiment setting as Figure 6 except that the contention window-size was set to 64, and it shows very similar results to Figure 6.  Notice that, with larger contention window-size, the PDR of traditional methods are actually improved; however, with the improvement, the performance of the traditional methods is still much worse than the proposed iPro method.PDRs of multisource multihop broadcasting scenario whenW=64.
(a)(b)(c)(d)By only comparing PDRs, we cannot have a conclusive performance evaluation of a method, since PDR can be increased by sacrificing throughput and latency performance, for example, making the contention window-size to a very big value will increase PDR but would degrade the performance of throughput.  Therefore, we further compare the latencies versus PDRs of the methods, as shown in Figures8 and 9 with contention window-size equals 32 and 64 respectively.  Latency is defined as the time differences between the receiving time of a packet by a node and the sending time of the corresponding packet from the source, and plotting PDRs versus latencies shows on average how many percentages of nodes have received a packet at a given time after the packet has been sent out from the source.  The results is plotted by setting the number of nodes to 300, which represents the median density in our simulations.  Figures 8(b)–8(d) show that when more than one source are broadcasting, the proposed method significantly outperforms other compared methods.  In Figure 8(b), all methods quickly reach saturated PDR values within 0.3 seconds, and within the same amount of time, the proposed method delivers near 85% of packets to all nodes, while other methods can only deliver about 50% to 60% of packets to all nodes.Latencies versus PDRs in multisource multihop broadcast scenario.
(a)(b)(c)(d)Latencies versus PDRs in multisource multihop broadcast scenario.
(a)(b)(c)(d)Figure9 shows similar results to Figure 8.  With the increase of contention window-size, the performance of traditional methods is improved slightly, while iPro with counter-based method maintains at the same performance level; however, iPro still significantly outperforms the traditional methods in latencies and PDRs performance.


## 4.1. Multisource One-Hop Broadcasting

In this simulation, the packet arrival rate to a node was set to 500 packets per second (pps) to guarantee that all nodes consistently have packets queued for transmission.  The nodes start broadcasting at 0.1 second and the simulation ends at 20 seconds.  The data were collected and analyzed after 20 seconds.  Four methods are compared in the simulations: standard IEEE 802.11, optimal contention windows size method, adaptive contention window-size method, andiPro. The optimal contention window-size used in the modeling and simulation is based on (13) in [10] with n given in advance, and the adaptive contention window-size method in the simulation is based on (1)–(4) from [10].Figure5 shows the modeling results and the ns2 simulation results.  The curves for different methods are listed in the legend.  The ns2 simulation results are shown to be very consistent with the modeling results.  The slight difference of the PDR performance between modeling and simulation for standard IEEE 802.11 is believed to be caused by the consecutive freeze process.  And the slight difference of the PDR performance for the proposed method is believed to be due to the fluctuation of the measured channel idle probability.  The differences are also observed in the normalized throughput.PDR and normalized throughput for payload equal 128 bytes.
(a)
PDR(b)
Normalized throughputBoth modeling andns2 simulation results show that by simply feeding back the channel idle probability, the results can be improved significantly, especially when the network density becomes higher.  When the number of neighbor nodes is 100, the PDR of the proposed method is more than seven times of the default IEEE 802.11 method; moreover, the normalized throughput of the proposed method is very close to the theoretical bounds, as shown in Figure 5(b).


## 4.2. Multisource Multihop Broadcasting

In this scenario, the packet arrival rate of a node was set to 10 packets per second (pps).  Four methods were compared in this scenario: simple flooding, counter-based flooding, Scalable Broadcast Algorithm (SBA), and the proposediPro with counter-based method.  The nodes start broadcasting for 5 seconds at 7.5 second; and the simulation ends when all nodes finish broadcasting.  In SBA, the neighbor information were exchanged every 5 seconds; and the 7.5 second initial waiting time is intended for SBA to effectively collecting neighbor information before broadcast starts. The simulations were conducted with one to four sources broadcast over a 500 × 500 m2 network topology.Figure6 shows the PDR of different number of sources broadcast at the same time.  When only one source is broadcasting over a moderate dense topology, the PDR appears to be close to 1, as shown in Figure 6(a).  However, when the network density becomes higher, the packet-delivery ratio starts to drop.  Figures 6(b)–6(d) show that, for traditional methods, when there are more than one source broadcasting together, PDRs are further degraded by the cross traffic.  In the simulation, the proposed method consistently outperforms traditional methods when network density or number of sources increase.  When all other methods have PDRs lower than 50%, the proposed method still maintains more than 85% PDR.PDRs of multisource multihop broadcasting scenario whenW=32.
(a)(b)(c)(d)Figure7 shows the simulation results with the same experiment setting as Figure 6 except that the contention window-size was set to 64, and it shows very similar results to Figure 6.  Notice that, with larger contention window-size, the PDR of traditional methods are actually improved; however, with the improvement, the performance of the traditional methods is still much worse than the proposed iPro method.PDRs of multisource multihop broadcasting scenario whenW=64.
(a)(b)(c)(d)By only comparing PDRs, we cannot have a conclusive performance evaluation of a method, since PDR can be increased by sacrificing throughput and latency performance, for example, making the contention window-size to a very big value will increase PDR but would degrade the performance of throughput.  Therefore, we further compare the latencies versus PDRs of the methods, as shown in Figures8 and 9 with contention window-size equals 32 and 64 respectively.  Latency is defined as the time differences between the receiving time of a packet by a node and the sending time of the corresponding packet from the source, and plotting PDRs versus latencies shows on average how many percentages of nodes have received a packet at a given time after the packet has been sent out from the source.  The results is plotted by setting the number of nodes to 300, which represents the median density in our simulations.  Figures 8(b)–8(d) show that when more than one source are broadcasting, the proposed method significantly outperforms other compared methods.  In Figure 8(b), all methods quickly reach saturated PDR values within 0.3 seconds, and within the same amount of time, the proposed method delivers near 85% of packets to all nodes, while other methods can only deliver about 50% to 60% of packets to all nodes.Latencies versus PDRs in multisource multihop broadcast scenario.
(a)(b)(c)(d)Latencies versus PDRs in multisource multihop broadcast scenario.
(a)(b)(c)(d)Figure9 shows similar results to Figure 8.  With the increase of contention window-size, the performance of traditional methods is improved slightly, while iPro with counter-based method maintains at the same performance level; however, iPro still significantly outperforms the traditional methods in latencies and PDRs performance.


## 5. Conclusions

In this paper, we proposed an idle probability-based broadcasting approach,iPro, that simply feedbacks the channel idle condition as a reference for transmitting a packet.  Without estimation the number of competing nodes, n, and without changing the contention window-size, W, the proposed iPro approaches the throughput maximum in one-hop broadcast scenarios; and the PDR and throughput performance of iPro significantly outperform standard IEEE 802.11.  In multihop broadcast scenarios, the proposed counter-based integrated iPro scheme effectively avoid collisions and reduce redundancies; and thus, it significantly outperforms traditional probabilistic and neighbor knowledge-based schemes, especially when several sources broadcast in the network at the same time.



---

*Source: 741792-2010-12-02.xml*