# Random Walker Coverage Analysis for Information Dissemination in Wireless Sensor Networks
## 3 Analysis
: _The expected value of \(V\) is approximately equal to 2.838._  
The proof is in Appendix C.  
Given the analysis so far, it is evident that the number of neighbors not visited in the first nine steps is \(N\pi r_{c}^{2}-1-V\). This also holds when applied for any arbitrary starting point (i.e., \(t\geq 0\)) of the random walker and not necessarily for \(t=0\). Simulation results presented later support this claim. Therefore, the probability \(P(r_{c})\) for the random walker to select a node that has not been visited during the last nine steps is given by the following equation:  
\[P(r_{c})=\frac{N\pi r_{c}^{2}-1-2V}{N\pi r_{c}^{2}-1}=\left(1-\frac{2V}{N\pi r _{c}^{2}-1}\right). \tag{3}\]  
Equation (3) is the basis to calculate \(C(t)\). In particular, the number of network nodes that have received at least one random walker visit after \(t\) steps is equal to the number of nodes that have been visited on the previous step, i.e., \(C_{t-1}\) plus the probability that the next node to be visited has not been visited before. As shown in Appendix D, the analytical expression of \(C(t)\) is given by Equation (4):  
\[C(t)=P(r_{c})+C(t-1)\left(1-\frac{P(r_{c})}{N}\right). \tag{4}\]  
The following corollary expresses \(C(t)\) as a discrete function of the time step \(t\) with parameters the transmission range \(r_{c}\) and the number of nodes \(N\). **Corollary 2**. : _Network coverage \(C(t)\) is given by:_  
\[C(t)=N-\left(\frac{N-1}{N}-\frac{2V}{N^{2}\pi r_{c}^{2}-1}\right)^{t}(N-1). \tag{5}\]  
The proof can be found in Appendix D.  
Figure 1: Common neighborhood surfaces of nodes sequentially visited by the random walker. Eventually, the random walker’s steps are not straight as in the figure; the Euclidean distance from the original node \(A\) is given by Equation (1). The colored gray area is still the overlapping surface for \(t=8\). The ratio \(R(t)\) of the network nodes that have been visited so far by the random walker over the total number of network nodes after every time step is calculated using Equation (5). \[R(t)=\frac{C(t)}{N}=1-\frac{N-1}{N}\left(\frac{N-1}{N}-\frac{2V}{N^{2}\pi r_{c} ^{2}-1}\right)^{t}. \tag{6}\]  
Figure 2 depicts the evolution of \(C(t)\) for a geometric random graph network of \(N=1000\) and various values of \(r_{c}\). For \(r_{c}=0.06\), the network is marginally connected (i.e., the smallest value of \(r_{c}\) for which all nodes belong to the network with high probability) with the average number of links per node being \(\approx 10\); thus, the curve is the lowest one (depicted with the red color). This is explained since \(P(r_{c})\) in Equation (4) is much smaller than one. In all other cases where the average number of links per node is much greater (100, 500 and 1000), \(P(r_{c})\approx 1\), and the relevant curves are close to the results presented in [25] i.e., Equation (7). \[C(t)=R(t)N=N\left(1-\mathrm{e}^{-\frac{t}{N}}\right). \tag{7}\]  
Equation (7) refers to a fully-connected network. **Theorem 2**. : _Equation (5) is equivalent to Equation (7) for the case of a fully-connected network._  
The proof for this theorem can be found in Appendix E.  
Given Equation (5), it is observed that network coverage \(C(t)\) evolves almost independently of the network's density of connections, since the square of the radius \(r_{c}\) is taken into account, which also lies in the denominator of the fraction. Only on marginally sparse networks, there is a distinct time lag, since in this case, the value of \(r_{c}\) is the minimum one. The analysis in this section resulted in Equations (5) and (6), which demonstrate the evolution of the network coverage using a random walker in relation to time (a walker's step corresponds to a single time unit). These results are experimentally examined in the next section. Figure 2: This figure depicts the evolution of \(C(t)\) (i.e., network coverage) over time for a geometric random graph of 1000 nodes using the random walker mechanism.