A Study on Maximizing the Parallelism of Macroscopically Derived Routing Algorithms for WSNs
Chün-chieh Huang, Ren‐Song Ko · The Computer Journal · 2015
The large-scale of massively dense wireless sensor networks (WSNs) brings up many challenges in designing efficient routing algorithms. Since the optimal load-balancing routing problem can be formulated as a set of partial differential equations (PDEs) by ignoring microscopic details, a simpler routing algorithm may be derived based on using WSNs themselves to solve the PDEs numerically. One example is the distributed Gauss–Seidel iteration (DGSI) algorithm which coordinates sensors to solve the PDEs by the Gauss–Seidel iteration in lexicographical order of unknowns. Although the parallelism of DGSI may be improved by using the red-black order, simply replacing the lexicographical order with the red-black order in DGSI may not work well since it cannot collect enough information to better determine the termination of the iteration. We propose the red-black distributed Gauss–Seidel routing (RB-DGSR) algorithm to address this problem. Furthermore, we present the five-color distributed De la Garza routing (FC-DDGR) algorithm for instances in which RB-DGSR may not converge, and theoretically prove that FC-DDGR achieves the optimum degree of parallelism. Our simulation results reveal that RB-DGSR and FC-DDGR significantly improve the parallelism and thus reduce the time to solve the PDEs without too much sacrifice of transmission overhead (in broadcast communication) and accuracy.