# Random Walker Coverage Analysis for Information Dissemination in Wireless Sensor Networks
## 1 Introduction  
During the last two decades, numerous wireless sensor networks (WSN) have been deployed for various activities [1; 2; 3; 4; 5; 6]. Due to the continuous technological progress in electronics [7], reasonably inexpensive small nodes with high capabilities are now available [8; 9]. In particular, the appearance on the market of small nodes with capabilities of energy harvesting (i.e., nodes capable of recharging their battery by acquiring energy from external sources) caused a revisit of fundamental networking problems (such as routing, medium access control, information dissemination, facility placement) from a new perspective [10; 11; 12]. WSN with energy-harvesting capabilities have lost their inherent deterministic reliability provided by batteries and need to operate in the uncertainty of the availability of natural resources. This trade-off of power over efficiency is more and more observed in technological advances; therefore there is a need for further investigation and reconsideration of traditional approaches in order to keep up with this progress. The stochastic nature of these modern networks challenges the application of the most widely-used methods for the dissemination (and similarly the collection) of information (e.g., flooding). New mechanisms have been developed and used for this purpose [13], one being the random walker [14; 15; 16; 17]. Information propagation in various networks is crucial in order to perform a computational task, especially in the case of WSN where nodes are at a distance from each other, and therefore, they areobligated to communicate with one or more of the rest of the network nodes. Nowadays, technology has enabled the application of such devices in many fields. Taking into account the cost of energy and time for the proper operation of these networks, there is a strong need for efficient methods and approaches regarding the spread of information among the network's nodes. One of the known advantages of the random walker method is that during the process, it makes multiple revisits to the nodes at different times, until it fully covers the network. This fact increases the probability of a node to accept the visit of a random walker during the time period that it operates in active mode. In this study, the network topology is represented as random geometric graphs, since this graph category is considered suitable for modeling wireless sensor networks [18]. The topologies of geometric random graphs are also found in real-world systems, such as the thalamo-cortical system of the cat [19] and, in general, in the cortical system of living organisms [20; 21]. In this work, the focus is on information dissemination using random walks. A random walker probabilistically chooses the next neighboring node to visit, independently of any previous visits. The probabilistic nature of this mechanism is suitable for dealing with the problem of nodes operating or not from time to time due to the energy availability. This mechanism is expected to probabilistically cover the whole network (i.e., reach all network nodes) using significantly less messages (one random walker movement corresponds to one message) in comparison to the use of deterministic flooding at the expense of increased termination time [22]. In the following sections, a novel analytical approach is proposed, showing how coverage is developed in relation to the number of random walker's steps. First, the probability of a random walker approaching a node for the first time at each step is calculated. This probability is subsequently, used to calculate the number of nodes that had been visited by the random walker at least once, depending on the number of steps. The analytical results indicate that the evolution of the network coverage is independent of its density of connections. Only in marginally-sparse topologies, there is a significant time lag, as provided by the aforementioned analysis of this work. Extended simulations provide results that sufficiently support the analytical expectations.