Statistically assisted routing algorithms (SARA) for hop count based forwarding in wireless sensor networks

The main goal of this paper is to provide routing–table-free online algorithms for wireless sensor networks (WSNs) to select cost (e.g., node residual energies) and delay efficient paths. As basic information to drive the routing process, both node costs and hop count distances are considered. Particular emphasis is given to greedy routing schemes, due to their suitability for resource constrained and highly dynamic networks. For what concerns greedy forwarding, we present the Statistically Assisted Routing Algorithm (SARA), where forwarding decisions are driven by statistical information on the costs of the nodes within coverage and in the second order neighborhood. By analysis, we prove that an optimal online policy exists, we derive its form and we exploit it as the core of SARA. Besides greedy techniques, sub–optimal algorithms where node costs can be partially propagated through the network are also presented. These techniques are based on real time learning LRTA algorithms which, through an initial exploratory phase, converge to quasi globally optimal paths. All the proposed schemes are then compared by simulation against globally optimal solutions, discussing the involved trade–offs and possible performance gains. The results show that the exploitation of second order cost information in SARA substantially increases the goodness of the selected paths with respect to fully localized greedy routing. Finally, the path quality can be further increased by LRTA schemes, whose convergence can be considerably enhanced by properly setting real time search parameters. However, these solutions fail in highly dynamic scenarios as they are unable to adapt the search process to time varying costs. Michele Rossi was born in Ferrara, Italy on October 30th, 1974. He received the Laurea degree in Electrical Engineering (with honors) and the Ph.D. degree in Information Engineering from the University of Ferrara in 2000 and 2004, respectively. Since 2000 he has been a Research Fellow at the Department of Engineering of the University of Ferrara. During 2003 he was on leave at the Center for Wireless Communications (CWC) at the University of California San Diego (UCSD), where he did research on wireless sensor networks. In November 2005 he joined the Department of Information Engineering of the University of Padova, Italy, where he is currently an Assistant Professor. Michele Rossi is currently part of the EU funded Ambient Networks and eSENSE projects. His research interests include: TCP/IP protocols over wireless networks, performance analysis of link layer retransmission techniques, routing and access selection in heterogeneous wireless networks and MAC/routing algorithms for wireless sensor networks. Michele Zorzi was born in Venice, Italy, in 1966. He received the Laurea degree and the Ph.D. degree in Electrical Engineering from the University of Padova, Italy, in 1990 and 1994, respectively. During the Academic Year 1992/93, he was on leave at the University of California, San Diego (UCSD), attending graduate courses and doing research on multiple access in mobile radio networks. In 1993, he joined the faculty of the Dipartimento di Elettronica e Informazione, Politecnico di Milano, Italy. After spending three years with the Center for Wireless Communications at UCSD, in 1998 he joined the School of Engineering of the University of Ferrara, Italy, and in 2003 joined the Department of Information Engineering of the University of Padova, Italy, where he is currently a Professor. His present research interests include performance evaluation in mobile communications systems, random access in mobile radio networks, ad hoc and sensor networks, and energy constrained communications protocols. Dr. Zorzi from 2003 to 2005 was the Editor-In-Chief of the IEEE Wireless Communications Magazine, and currently serves on the Editorial Boards of the IEEE Transactions on Communications, the IEEE Transactions on Wireless Communications, the IEEE Transactions on Mobile Computing, the Wiley Journal of Wireless Communications and Mobile Computing and the ACM/URSI/Kluwer Journal of Wireless Networks. He was also guest editor for special issues in the IEEE Personal Communications Magazine (Energy Management in Personal Communications Systems) and the IEEE Journal on Selected Areas in Communications (Multi-media Network Radios). Ramesh R. Rao was born in Sindri, India, where he completed his undergraduate work at the Regional Engineering College of the University of Madras in Tiruchirapalli, obtaining a BE (Honors) degree in Electronics and Communications in 1980. He completed his graduate work at the University of Maryland, College Park, Maryland where he received his M.S. and Ph.D. Professor Rao is currently a Professor at the University of California, San Diego (UCSD) at the department of Electrical and Computer Engineering in the Irwin and Joan Jacobs School of Engineering, where he has been a member of the faculty since 1984. Professor Rao is the former director of UCSD’s Center for Wireless Communications (CWC), and currently serves as the Qualcomm Endowed Chair in Telecommunications and Information Technologies, and as the Director of the San Diego Division of the California Institute of Telecommunications and Information Technology Cal-(IT)²]. As Director of the San Diego Division of Cal-(IT)², he leads several interdisciplinary and collaborative projects. His research interests include architectures, protocols and performance analysis of computer and communication networks, and he has published extensively on these topics. Since 1984, Professor Rao has authored over 100 technical papers, contributed book chapters, conducted a number of short courses and delivered invited talks and plenary lectures. He is currently supervising both masters and doctoral students.