增加分散式高斯賽德爾繞送演算法之平行度於無線感測網路

To Increase Parallelism Of Distributed Gauss-Seidel Routing Algorithm For Wireless Sensor Networks

黃俊傑(Huang,Chunchieh)

指導教授 ： 柯仁松

國立中正大學/工學院/資訊工程學系/碩士(2012年)

摘要

在高密度 (massive-dense) 的無線感測網路 (Wireless Sensor Network，WSN)
中，繞送路徑可以視為連續的線段，我們可以使用宏觀參數來重新描繪 WSN，
定義出一個地理空間 (geographic space) 的宏觀模型取代傳統的圖論模型，進而
避免大量節點所產生的繁瑣細節。在宏觀模型下，我們可以把負載平衡的繞送問
題描述成一組偏微分方程式(PDEs)，經有限差分法 (finite different method，FDM)
轉換成線性聯立方程式後，繞送問題便轉換成解聯立方程式，再以高斯賽德爾迭
代法 (Gauss-Seidel iteration method，GSI) 來求解，其解即為 WSN 中的繞送方向。

然而在密度差距過大的 WSN 中，高斯賽德爾迭代法會發生無法收斂的情況，
而戴拉葛薩迭代法 (De la Garza Iteration method，DLGI) 可以解決這個問題，但
是需要耗費的相當可觀回合數，因此我們提出一個平行度更高的演算法
Color-Grouping Method，將相同回合中能夠更新的格子點，根據其距離的特性區
分出來，再將這些格子點分成同組，依組別順序來進行迭代運算，可以大幅減少
GSI 及 DLGI 收斂所需的回合數。

關鍵字

無線感測網路 ； 分散式演算法 ； 負載平衡 ； 戴拉葛薩迭代法 ； 高斯賽德爾迭代法 ； 平行度 ； 著色問題

並列摘要

In massive-dense Wireless Sensor Network (WSN), routing paths can be
considered as continuous lines. We could re-describe WSN by macroscopic
parameters, defining macroscopic models of geographic space to replace traditional
graphic models, and then it can avoid the complicated details produced by large
number of nodes. In macroscopic models, the routing problem of load balance can
described as a sort of partial differential equations (PDEs), after transforming it into
linear equations by use of finite difference method (FDM). The routing problem now
is transformed into solve this equations, and we can solve it by Gauss-Seidel iteration
method (GSI) which solutions is routing direction in WSN.

However, GSI cannot converge in some special WSN which node density varies
significantly. De la Garza Iteration method (DLGI) can solve this problem, but it needs
considerable rounds. Thus we design Color-Grouping Method to increase parallelism
of these algorithms, which method group grid points which updates in same round
according to property of distance, and this method will do iteration in grouping order,
it can substantially reduce the number of convergence rounds of GSI and DLGI.

並列關鍵字

Wireless sensor network ； Distributed algorithm ； Load balance ； De La Garza algorithm ； Gauss-Seidel algorithm ； parallelism ； coloring problem

參考文獻

recursive data dissemination protocol for wireless sensor networks, UCLA

sensor networks, cornell university library, 2011.

Consumption in Large Scale Wireless Sensor Network, 2011 Third International

[1] R.F. Erbacher, S. Hutchinson, Distributed Sensor Objects for Intrusion Detection

Systems, in: Proceedings of 2012 Ninth International Conference on Information