Abstract
Topology is one of the most important characteristics for any type of networks because it represents the network’s inherent properties and has great impact on the performance of the network. For wireless sensor networks (WSN), a well-deployed regular topology can help save more energy than what a random topology can do. WSNs with regular topologies can prolong network lifetime as studied in many previous work. However, little work has been done in developing effective routing algorithms for WSNs with regular topologies, except routing along a shortest path with the knowledge of global location information of sensor nodes. In this paper, a new routing protocol based on random walk is proposed. It does not require global location information. It also achieves load balancing property inherently for WSNs which is difficult to achieve by other routing protocols. 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, it is proved that the random walk routing protocol can guarantee high probability of successful transmission from the source to the base station with the same amount of energy consumption as the shortest path routing. 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 thus a viable scheme and can work very efficiently especially in these application scenarios. The random walk routing provides load balancing in the WSN as mentioned, however, the nodes near to the base station are inevitably under heavier burden than those far away from the base station. Therefore, a density-aware deployment scheme is further proposed to guarantee that the heavy-load nodes do not affect the network lifetime even if their energy is exhausted. The main idea is deploying sensors with different densities according to their distance to the base station. It will be shown in this paper that incorporating the random walk routing protocol with the density-aware deployment scheme can effectively prolong the network lifetime.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
Heinzelman W, Kulik J, Balakrishnan H. Adaptive protocols for information dissemination in wireless sensor networks. In Proc. 5th ACM/IEEE MobiCom, Seattle, WA, 1999, pp.174–185.
Kulik J, Heinzelman W, Balakrishnan H. Negotiation-based protocols for disseminating information in wireless sensor networks. Wireless Networks, 2002, 8(2): 169–185.
Hui Tian, Hong Shen. An optimal coverage scheme for wireless sensor networks. In Proc. International Conference on Networking, Reunion Island, April 2005, pp.722–730.
Hui Tian, Hong Shen, Teruo Matsuzawa. Developing energy-efficient topologies and routing for wireless sensor networks. In Proc. IFIP International Conference on Network and Parallel Computing, Beijing, China, Dec. 2005, pp.461–469.
Edoardo S Biagioni, Galen Sasaki. Wireless sensor placement for reliable and efficient data collection. In Proc. The 36th Hawaii International Conference on System Sciences (HICSS), Hawaii, Jan. 2003, p.127b.
Rajagopal Iyengar, Koushik Kar, Suman Banerjee. Low-coordination topologies for redundancy in sensor networks. In Proc. The 6th Mobihoc, Urbana-Champaign, IL, USA, 2005, pp.332–342.
Koushik Kar, Suman Banerjee. Node placement for connected coverage in sensor networks. In Proc. WiOpt, Sophia-Antipolis, France, 2003.
Ayad Salhieh, Jennifer Weinmann, Manish Kochhal, Loren Schwiebert. Power efficient topologies for wireless sensor networks. In Proc. Int. Conf. Parallel Processing, Valencia, Spain, 2001, pp.156–163.
Braginsky D, Estrin D. Roumor routing algorithm for sensor networks. In Proc. The First Workshop on Sensor Networks and Applications (WSNA), Atlanta, GA, Sept. 2002, pp.1–12.
Servetto S, Barrenechea G. Constrained random walks on random graphs: Routing algorithms for large scale wireless sensor networks. In Proc. 1st ACM International Workshop on Wireless Sensor Networks and Applications, Atlanta, GA, 2002, pp.12–21.
Hui Tian, Hong Shen, Teruo Matsuzawa. Random walk routing for wireless sensor network (preliminary version). In Proc. The Sixth PDCAT, Dalian, China, 2005, pp.196–200.
Author information
Authors and Affiliations
Corresponding author
Additional information
This research is supported by the “21st Century COE Program” by Japanese Ministry of Education, Culture, Sports, Science and Technology.
Hui Tian received the B.Eng. and M.Eng. degrees from Xidian University, China and Ph.D. degree from Japan Advanced Institute of Science and Technology. She is currently a Lecturer in Manchester Metropolitan University, UK. Her research interest includes network performance evaluation, telecommunications and wireless sensor networks.
Hong Shen received his B.Eng. degree from Beijing University of Science and Technology, M.Eng. degree from University of Science and Technology of China, Ph.Lic. and Ph.D. degrees from Abo Akademi University, Finland, all in computer science. He is currently a specially-appointed professor in University of Science and Technology of China. Prof. Shen has been a full professor since 2000 in Australia, Japan and UK respectively. His main research interests lie in parallel and distributed computing, algorithms, high performance networks, data mining and multimedia systems. He has published over 200 papers, with more than 80 papers in international journals. He has served on editorial boards of 7 international journals, and chaired several international conferences.
Teruo Matsuzawa received his B.Eng., M.Eng., and Ph.D. (Medicine) degrees from Shinshu University. He joined Japan Advanced Institute of Science and Technology in 1991 and is currently a professor in Center for Information Science. He is specialized in computational fluid dynamics (CFD), and has research interests in bio-fluid dynamics, parallel processing for CFD, flow visualization with computer graphics. He has published widely on the above topics in various international journals and conferences. Prof. Matsuzawa has been actively involved in many professional and social services. He is an editorial member of IPSJ Transactions on High Performance Computing Systems (1999--2004), a member of local organizing committee of JUSIS 2002, program vice chair of PDCAT05 and a member of program committee of PDCAT06.
Rights and permissions
About this article
Cite this article
Tian, H., Shen, H. & Matsuzawa, T. Random Walk Routing in WSNs with Regular Topologies. J Comput Sci Technol 21, 496–502 (2006). https://doi.org/10.1007/s11390-006-0496-8
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/s11390-006-0496-8