Random walk routing for wireless sensor networks

Topology is important for any type of networks because it has great impact on the performance of the network. For wireless sensor networks (WSN), regular topologies, which can help to efficiently save energy and achieve long networking lifetime, have been well studied in [1, 4, 5, 7, 9]. However, little work is focused on routing in patterned WSNs except the shortest path routing with the knowledge of global location information. In this paper, we propose a routing protocol based on random walk. It doesn't require global location information. Moreover, the random walk routing achieves load balancing property inherently for WSNs which is difficult to achieve for other routing protocols. We also prove that the random walk routing consumes the same amount of energy as the shortest path routing in the scenarios where the message required to be sent to the base station is in comparatively small size with the inquiry message among neighboring nodes. Since in many applications of WSNs, sensor nodes often send only beep-like small messages to the base station to report their status, our proposed random walk routing is a viable scheme. Though the random walk routing provides load balancing in the WSN, the nodes near to the base station (BS) are inevitably under heavier burden than the nodes far from the base station. Therefore we further propose a density-aware deployment scheme to guarantee that the heavy-load nodes do not affect the network lifetime even if they are exhausted.