Stochastic Routing in Wireless Sensor Networks

We propose a new location-based stochastic routing approach that is well-suited for wireless sensor networks deployed for public safety applications such as emergency evacuations or search and rescue operations. We first introduce a new modeling and evaluation framework based on Markov chains for randomized routing. Based on this evaluation framework, we study the load balancing and routing performance aspects of i) a near-optimal solution using the complete topology information, ii) a heuristic algorithm that uses only local neighborhood information. Numerical studies using the evaluation framework show that our heuristic routing approach scales well with both network size and density, considering the combined problem of routing and load balancing.