Random Walks on Sensor Networks

We consider the mobile data gathering problem in large-scale wireless sensor networks with static sensor nodes and a mobile patrol node. Based on the assumptions that (a) the sensor positions are unknown and (b) the network may not be entirely connected, we formulate the problem as one of random walks in random geometric graphs and derive analytical bounds for the node coverage, i.e. the number of queried sensor nodes within a given time frame. Based on this metric, we propose an algorithm that improves the data gathering performance by generating constrained random walks, in which the probability mass function at each step reflects the available side information (e.g. the memory of past visited sites).