# Adapting Probabilistic Flooding in Energy Harvesting Wireless Sensor Networks
## 4 Probabilistic Information Dissemination  
Let \(s\) denote the node that plans to disseminate an information message to the network nodes (i.e., _initiator node_) using PF. Nodes that receive the particular message for the first time decides whether to forward this to their neighbors according to a fixed _forwarding probability_\(q\). Any redundant messages received by the nodes are discarded. For the sake of simplicity, it is assumed that the dissemination process takes place in discrete time steps. Let the _coverage_ (i.e., the fraction of covered nodes by PF) at time step \(t\) be denoted by \(C(t)\). Obviously, \(C(0)=\frac{1}{n}\) since only node \(s\) has the particular message at the beginning. In addition, let \(\mathcal{T}\) denote the termination time of the PF. The main objective here is to archive _global outreach_ (i.e., cover all the nodes of the network) when the dissemination process finishes i.e., \(C(\mathcal{T})=1\). Due to its probabilistic nature, global outreach under PF is guaranteed with high probability and not deterministically. A large amount of studies (e.g., [4, 36, 37, 63]) focuses on the particular value of \(q\) allowing for global outreach and at the same time the amount of messages kept minimized i.e., _threshold probability_, \(\hat{q}\). The benefits obtained by this policy vary according to the value of the forwarding probability. If the value of \(q\) is smaller than \(\hat{q}\), then coverage is small (i.e., \(C(t)<1\)). If \(q\) is larger than \(\hat{q}\), although the coverage is sightly increased compared to the case of \(q=\hat{q}\), the amount of messages may be significantly increased. This work aims to shed further light on the efficiency of PF in the presence of energy harvesting. Figure 2 depicts a network where a bottleneck exists between nodes \(u\) and \(v\). Let the nodes be operating under the previously mentioned energy harvesting environment and assume that node \(s\) plans to disseminate an information message to the network under PF. At time step \(t=0\), node \(s\) forwards the particular message to its neighbors according to a forwarding probability sufficient to provide full coverage (i.e., \(q\geq\hat{q}\)) under the assumption that all nodes are operating. However, when the energy  
Figure 1: Node state Markov chain. \begin{table}
\begin{tabular}{c c c} \hline \hline
**Operational State** & **Charging** & **Discharging** \\ \hline Operating & ON-C & ON-D \\ \hline Non-Operating & OFF-C & OFF-D \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Node states. is exhausted in either of nodes \(u\) or \(v\), the nodes within the dotted area do not receive the particular message, even though the energy harvesting mechanism may replenish their batteries later. Based on this observation, it follows that, in order to adapt PF into energy harvesting environments, the nodes' operational states should be taken into account. Consequently, under the proposed mechanism, each node that receives the information message for the first time selects a subset of its neighbors according to the forwarding probability regardless of their operational state. Subsequently, the node forwards the information message to the operating nodes and waits for the non-operating ones to become available and receive the particular message. If a node that plans to forward an information message to its neighbors runs out of energy, it suspends its operation and resumes as soon as the energy harvesting process replenishes its battery. The proposed mechanism called _Robust Probabilistic Flooding_ (RPF) is presented in Algorithm 1. Let \(S_{u}\) denote the set of neighbors of node \(u\), \(R_{u}\) the subset of \(S_{u}\) that remains to be covered under the proposed mechanism and \(L_{u}\) the subset of \(S_{u}\) that is operational at a particular time. It follows that \(R_{u}\subseteq S_{u}\) and \(L_{u}\subseteq S_{u}\). It is assumed that every node periodically transmits beacons frames to inform the neighbor nodes about its presence.