Random Walk Routing in WSNs with Regular Topologies

Topology is one of the most important characteristics for any typeof networks because it represents the network's inherent properties andhas great impact on the performance of thenetwork. For wireless sensor networks (WSN), a well-deployed regulartopology can help save more energy than what a random topology cando. WSNs with regular topologies can prolong network lifetime asstudied in many previous work. However, little work has been done indeveloping effective routing algorithms for WSNs with regulartopologies, except routing along a shortest path with the knowledgeof global location information of sensor nodes. In this paper,a new routing protocol based on random walk is proposed. It does notrequire global location information. It also achieves load balancingproperty inherently for WSNs which is difficult to achieve by otherrouting protocols. In the scenarios where the message required to besent to the base station is in comparatively small size with theinquiry message among neighboring nodes, it is proved that the randomwalk routing protocol can guarantee high probability of successfultransmission from the source to the base station with the sameamount of energy consumption as the shortest path routing. Since inmany applications of WSNs, sensor nodes often send only beep-likesmall messages to the base station to report their status, ourproposed random walk routing is thus a viable scheme and can workvery efficiently especially in these application scenarios.The random walk routing provides load balancing in the WSN asmentioned, however, the nodes near to the base station areinevitably under heavier burden than those far away from the basestation. Therefore, a density-aware deploymentscheme is further proposed to guarantee that the heavy-load nodes do notaffect thenetwork lifetime even if their energy is exhausted. The main idea isdeploying sensors with different densities according to theirdistance to the base station. It will be shown in this paper thatincorporating the random walk routing protocol with thedensity-aware deployment scheme can effectively prolong the networklifetime.