Atomic Red-Black Distributed Gauss-Seidel Routing Algorithm for Wireless Sensor Networks
Ren‐Song Ko · 2016
The scalability challenge of many problems in massively-dense wireless sensor networks may be mitigated from a macroscopic perspective. One example is to formulate the optimal load-balancing routing problem as a set of partial differential equations (PDEs) by ignoring microscopic details, the solutions of the PDEs can be then used to route information. Hence, a routing algorithm, the distributed Gauss-Seidel iteration (DGSI) algorithm, was proposed to coordinate sensors to solve the PDEs iteratively. The later improved algorithm, the distributed Multiplicative Schwarz routing (DMSR) algorithm, eliminates the early termination problem of DGSI due to the presence of holes, and thus improves the accuracy of numerical solutions. In this paper, we propose the atomic red-black distributed Gauss-Seidel routing (ARB-DGSR) algorithm to further improve DGSI and DMSR. In addition to a simpler one-phase coordination mechanism, ARB-DGSR allows the values of unknowns to be updated in the red-black order to achieve the maximum degree of parallelism and thus reduce the convergence time. Our simulation results reveal that ARB-DGSR significantly improves the parallelism without too much sacrifice of accuracy.