## 4 Analysis
### Other Effects
#### 4.2.1 Auto-Collisions in First Hop  
For a packet \(p\) flooded over a wireless network, auto-collision is the case of two copies of that packet, \(p\), colliding; in other words, that \(p\) \"collides with its own alter-ego\".  
Consider the network, depicted in Figure 7, in which a router \(S\) floods a packet \(p\) at time \(t=t_{0}\) and in which all of \(N_{1}\), \(N_{2}\),..., \(N_{n}\) are neighbors. This packet is, then, simultaneously received by the \(n\) neighbors of \(S\), \(N(S)=\{N_{1},N_{2},...,N_{n}\}\) and forwarded (retransmitted) with a random jitter value \(T_{j}\), distributed according to the different considered mechanisms. For tractability purposes, retransmissions are modeled in this section as a homogeneous Poisson arrival process. In this scenario, there is an auto-collision of \(p\) in the one-hop neighborhood of \(S\) when at least two neighbors of \(S\) retransmit \(p\) at times \(t_{1}\) and \(t_{2}\), such that the inter-arrival time \(|t_{1}-t_{2}|<L\), where \(L=L(p)\) is the transmission time for packet \(p\).  
In the case of uniform jitter, retransmission times will be distributed within \(t=t_{0}\) and \(t=t_{0}+J_{m}\), where \(J_{m}\) is the upper bound for jitter values; the Poisson rate of retransmissions will be \(\lambda_{\text{uniform}}=\frac{n}{J_{m}}\). When using window jitter, retransmissions of a packet \(p\) received at \(t=t_{0}\) will be confined between \(t_{0}+\alpha J_{m}\) and \(t_{0}+J_{m}\) (\(\alpha\in(0,1)\)), that is, no retransmission will occur before \(t_{0}+\alpha J_{m}\). This implies that the Poisson rate of retransmission will grow to \(\lambda_{\text{window}}=\frac{n}{(1-\alpha)J_{m}}\). Lemma 1 describes the probability that the flooding process of packet \(p\) leads to an auto-collision in the one-hop neighborhood of \(S\), with uniform and window jitter.  
Figure 6: Value of \(P_{W}\equiv Pr(D_{W}^{(n,m)}>0)\), depending on \(\Delta=m-n>0\), for different values of \(n\) (\(\alpha=\frac{1}{2}\)). Traces corresponding to \(\Delta=2\) and \(\Delta=3\) are significantly lower than \(0.01\) and, thus, are not visible in the picture.  
**Lemma 1**.: _If \(S\)'s neighbors use uniform jitter within \([0,J_{m}]\), the probability of auto-collision in the one-hop neighborhood of \(S\) corresponds to Equation (9). If window jitter is used in the same interval, with parameter \(\alpha\), the probability of auto-collision in the one-hop neighborhood of \(S\) corresponds to Equation (10):_  
\[Pr(\text{auto-collision with uniform jitter})=\left(1-e^{-\frac{nL}{J_{m}}} \right)^{n} \tag{9}\]  
\[Pr(\text{auto-collision with window jitter})=\left(1-e^{-\frac{nL}{(1-\alpha)J_{m}}} \right)^{n} \tag{10}\]  
Figure 8 illustrates the probability of auto-collisions in the first hop of the flooding process (_i.e._, when an RREQ is retransmitted by routers one hop away from the source) for different sets of parameters (\(n,J_{m},L\)). Although the specific values for the probability of auto-collision depend on the chosen values, and, in particular, the relation between \(L\) and \(J_{m}\), there are some general trends that can be identified. The use of window jitter leads to more frequent auto-collisions at the first hop, due to the effective reduction of the interval of retransmissions (from \([0,J_{m}]\) to \([\alpha J_{m},J_{m}]\)), which implies a more deterministic retransmissions schedule by one-hop neighbors of \(S\). This effect, however, is specific to the first hop and becomes less relevant in multi-hop flooding, as the network has a bigger diameter and routes grow longer, as shown in further experiments (Sections 5 and 6).  
Figure 8: Probability of auto-collision in the first hop.  
Figure 7: Simple network topology, in which \(S\) is a neighbor with all of \(N_{1}\),..., \(N_{n}\) and where all of \(N_{1}\),..., \(N_{n}\) are neighbors of each other.