# Random Walker Coverage Analysis for Information Dissemination in Wireless Sensor Networks
## 3 Analysis  
In this work, the mechanism of the random walker was selected in order to study the information dissemination. A random walker can be seen as an entity, beginning at the initiator node, that chooses randomly (uniformly) to visit a one-hop neighbor of the node where it currently resides. Then, this \"agent\" continues in a similar manner until the entire network is covered (i.e., all nodes are visited by the walker). In order to analytically model network coverage when a random walker is employed, the following assumptions take place. The network nodes are uniformly distributed on a plain area sized \(1\times 1\), that is a unit square. All considered networks are connected (a network is connected when there is a path between every pair of nodes). Each node of the network has the same transmission range \(r_{c}\). The following notation is also used: \(N\) denotes the number of nodes on each network, and \(C(t)\) is a stochastic variable representing the number of nodes who have received at least one visit after \(t\) random walker's steps. Each node has transmission range \(r_{c}\). Hence, the surface covered by its transmissions is (ideally) \(\pi r_{c}^{2}\). Throughout this work, this surface is referred to as the node's radius. Given that nodes are uniformly distributed, the number of network nodes located in an area of region \(\pi r_{c}^{2}\) is (on average) \(N\pi r_{c}^{2}\). Thus, each network node will have on average \(N\pi r_{c}^{2}-1\) neighbors. The random walker's spatial movement (i.e., the euclidean distance covered) on each step is on average \(\frac{2r_{c}}{3}\) (the proof is in Appendix A). This result is also confirmed later through simulations. The mean spatial movement of a random walker from a position after \(t\) steps is given by \(d_{t}=l\sqrt{t}\), where \(l\) is the Euclidean distance covered in each step [46]. Thus, using the average random walker's spatial movement on each step mentioned in the previous paragraphs, it holds that \(l=\frac{2r_{c}}{3}\) and, consequently,  
\[d_{t}=\frac{2r_{c}}{3}\sqrt{t}. \tag{1}\]  
From the above Equation (1), it follows that when \(t\leq 9\), then \(d_{t}\) < 2 \(r_{c}\). Therefore, the neighborhood of the node visited by the random walker before \(t\leq 9\) steps and the neighborhood of the node on which it lies now will overlap, and nodes on the corresponding overlapping surface are neighbors of both (see Figure 1). The number of those nodes is analogous on average to the overlapping surface. The area of this surface \(E_{t}\) is given by the following theorem:  
**Theorem 1**. : _On a random walker acting on a geometric random graph, the neighborhood of the node visited by the random walker before \(t\) time steps (where \(t\leq 9\)) and the neighborhood of the node on which it lies now have an overlapping surface \(E_{t}\):_  
\[E_{t}=2r_{c}^{2}\left(\arccos\left(\frac{\sqrt{t}}{3}\right)-\frac{\sqrt{t(9- t)}}{9}\right) \tag{2}\]  
The proof of Theorem 1 is in Appendix B. In brief, Equation (2) is used to calculate the common neighborhood of the currently visited node with the previously visited ones, choosing at each time step the node that corresponds to the value of \(t\) (i.e., for \(t=1\) the node visited one time step before, for \(t=2\) the node visited two time steps before, and so on). On this basis, each time the random walker chooses the next step node from the current set of neighbor nodes, i.e., \(N\pi r_{c}^{2}-1\) nodes at \(t=0\). Note that the random walker has already visited at least one of these nodes, in particular the previous node, which the random walker visited one time step before. The probability for the node that the random walker visited before \(t\) (where \(t\leq 9\)) steps to belong to this set is proportional to the fraction of the area of the overlapping surface to the node's neighborhood surface \(\frac{E_{t}}{\pi r_{c}^{2}}\) (see Figure 1). Let \(V\) indicate the number of neighboring nodes that have already been visited by the random walker. **Corollary 1**.