On random routing in wireless sensor grids: A mathematical model for rendezvous probability and performance optimization

Random routing protocols in Wireless Sensor Networks (WSNs) forward packets to randomly selected neighbors. These packets are ‘agents’ carrying information about events or ‘queries’ seeking such information. A novel mathematical framework is proposed for analyzing random routing protocols. Exact probability of a packet visiting a given node within a given hop count as well as the rendezvous probability of agents and queries meeting at a given node in a 2-D grid-based WSN are derived. The basic relationship needed for extending the models to a 3-D grid topology is provided. Exact probabilities of agents meeting queries are derived while ignoring physical boundary effects and packet losses, under two different strategies for forwarding the packet to a neighbor: (a) with equal probability, and (b) self-avoiding forwarding. We then extend the model to account for packet losses by considering the case where a packet is forwarded to a neighbor with equal probability. Also provided is the extension of the analysis for a network with rectangular boundaries. The exact solutions presented, unlike existing models relying on asymptotic behavior, are also applicable to small and medium scale networks. They can be used to set parameters and optimize performance of several classes of random routing protocols. All the models are validated using Monte Carlo simulations. Simulation results indicate that the model is also a good approximation for sparse arrays with 75% or higher node density. Finally, the utility of the model is demonstrated by determining the protocol parameters to optimize the performance of rumor routing protocol under a fixed energy budget.

Research highlights
► A model for evaluating rendezvous probability of two random walks on a grid.
► A model for optimizing number of agents and queries in random routing.
► Performance of rumor routing on a 2-D grid-based wireless sensor network.