## 3 PFR - A Probabilistic Forwarding Protocol
### The Protocol  
The PFR protocol is inspired by the probabilistic multi-path design choice for the Directed Diffusion paradigm mentioned in [25]. Its basic idea of the protocol (introduced in [9]) lies in probabilistically favoring transmissions towards the sink within a _thin zone_ of particles around the line connecting the particle sensing the event \(\mathcal{E}\) and the sink (see Figure 4). Note that transmission along this line is energy optimal. However it is not always possible to achieve this optimality, basically because certain sensors on this direct line might be inactive, either permanently (because their energy has been exhausted) or temporarily (because these sensors might enter a sleeping mode to save energy). Further reasons include:  
* physical damage of sensors,
* deliberate removal of some of them (possibly by an adversary in military applications),
* changes in the position of the sensors due to a variety of reasons (weather conditions, human interaction _etc._), and
* physical obstacles blocking communication. The protocol evolves in two phases:  
**Phase 1: The \"Front\" Creation Phase. ** Initially the protocol builds (by using a limited, in terms of rounds, flooding) a sufficiently large \"front\" of particles, in order to guarantee the survivability of the data propagation process. During this phase, each particle having received the data to be propagated, deterministically forwards them towards the sink. In particular, and for a sufficiently large number of steps \(s=180\sqrt{2}\), each particle broadcasts the information to all its neighbors, towards the sink. Remark that to implement this phase, and in particular to count the number of steps, we use a counter in each message. This counter needs at most \(\lceil\log 180\sqrt{2}\rceil\) bits. **Phase 2: The Probabilistic Forwarding Phase. ** During this phase, each particle \(P\) possessing the information under propagation, calculates an angle \(\phi\) by calling the subprotocol \"\(\phi\)-calculation\" (see description below) and broadcasts \(info(\mathcal{E})\) to all its neighbors with probability \(\mathds{P}_{fwd}\) (or it does not propagate any data with probability \(1-\mathds{P}_{fwd}\)) defined as follows:  
\[\mathds{P}_{fwd}=\left\{ \begin{array}{ll}1&\mbox{if }\phi\geq\phi_{threshold}\\ \frac{\phi}{\pi}&\mbox{otherwise}\end{array} \right.\]  
where \(\phi\) is the angle defined by the line \(EP\) and the line \(PS\) and \(\phi_{threshold}=134^{o}\) (the selection reasons of this \(\phi_{threshold}\) can be found in [9]. In both phases, if a particle has already broadcast \(info(\mathcal{E})\) and receives it again, it ignores it. Also the PFR protocol is presented for a single event tracing. Thus no multiple paths arise and packet sizes do not increase with time. Remark that when \(\phi=\pi\) then \(P\) lies on the line \(ES\) and vice-versa (and always transmits). If the density of particles is appropriately large, then for a line \(ES\) there is (with high probability) a sequence of points \"closely surrounding \(ES\)\" whose angles \(\phi\) are larger than \(\phi_{threshold}\) and so that successive points are within transmission range. All such points broadcast and thus essentially they follow the line \(ES\) (see Figure 4). Figure 4: Thin Zone of particles. The \(\phi\)-calculation subprotocol (see Figure 5)  
Let \(P_{prev}\) the particle that transmitted \(info(E)\) to \(P\). (1) When \(P_{prev}\) broadcasts \(info(E)\), it also attaches the info \(|EP_{prev}|\) and the direction \(\overrightarrow{P_{prev}E}\). (2) \(P\) estimates the direction and length of line segment \(P_{prev}P\), as described in the model. (3) \(P\) now computes angle \((\overrightarrow{EP_{prev}P})\), and computes \(|EP|\) and the direction of \(\overrightarrow{PE}\) (this will be used in further transmission from \(P\)). (4) \(P\) also computes angle \((\overrightarrow{P_{prev}PE})\) and by subtracting it from \((\overrightarrow{P_{prev}PS})\) it finds \(\phi\).