A distributed routing algorithm for sensor networks derived from macroscopic models

While Greedy Forwarding (GF) has been suggested as a promising scheme for routing in wireless sensor networks (WSNs), inappropriate node deployment may cause a packet to be trapped at a local minimum, in which case GF will fail to deliver the packet. Though many algorithms have been proposed to allow packets to escape the local minimum trap, they commonly result in excess energy consumption of hole boundary nodes, which could lead to more serious hole problems. This paper approaches this problem from a macroscopic perspective, in which the routing paths for load balancing can be formulated as a set of partial differential equations (PDEs). We present a distributed algorithm, the distributed Gauss-Seidel iteration (DGSI), that embeds the finite-difference and Gauss-Seidel iteration methods into WSNs to solve the PDEs, and analyze performance for parallelism and errors. Furthermore, we discuss the limitations of DGSI and present a possible remedy for instances in which DGSI may not converge due to significant variations in node density. Since the proposed approach transforms a routing problem into a linear equation solving problem, we believe this paper will open up a potential research direction toward the application of many existing equation solving strategies for routing problems in WSNs. (C) 2010 Elsevier B.V. All rights reserved.