臺灣博碩士論文加值系統

在無線感測網路中，如何使用最少的感測器來覆蓋所有的關鍵方格是被稱為關鍵方格覆蓋問題。如何使用有限的感測器來覆蓋權重關鍵方格以得到最大利益值總和是被稱為權重關鍵方格覆蓋問題。這兩個問題都已經被證明為NP-complete問題，也有相對的啟發式演算法被提出來。例如，STBCGC (Steiner-Tree-Based Critical Grid Covering)演算法是用來求解關鍵方格覆蓋問題。Reduction+PB(Reduction+Profit-Based)演算法是用來求解權重關鍵方格覆蓋問題。在本碩士論文中，我們整合了這兩個問題而形成一個新的問題，我們稱為二階層關鍵方格覆蓋問題。二階層關鍵方格覆蓋問題的目標為如何使用有限的感測器來覆蓋所有的關鍵方格，並覆蓋可以得到利益值的權重關鍵方格來得到最大的利益值總和。很明顯地，直接合併STBCGC演算法和Reduction+PB演算法以形成STBCGC+PB演算法是求解二階層關鍵方格覆蓋問題的可能方法之一。在本碩士論文中，基於STBCGC+PB演算法，我們提出了一個新的啟發式演算法來求解二階層關鍵方格覆蓋問題。我們的啟發式演算法改進了STBCGC+PB演算法的三個地方。其中二個改進使得我們的啟發式演算法在進行覆蓋必須被覆蓋的關鍵方格時，也能夠同時先覆蓋一部分的權重關鍵方格，藉此來得到更多的利益值總和。另一個改進使得我們的啟發式演算法在覆蓋權重關鍵方格時，有較大的機會進一步得到較大的利益值總和。最後，在本碩士論文中，我們使用電腦模擬來分析並比較我們的啟發式演算法與STBCGC+PB演算法的效能。電腦模擬結果顯示，相對於STBCGC+PB演算法，我們的啟發式演算法可以得到比較多的利益值總和。

In a wireless sensor network, how to cover all critical square grids with the fewest sensors is called the critical-square-grid coverage problem. How to cover weighted critical square grids with a limited number of sensors to get the maximum sum of profits is called the weighted-critical-square-grid coverage problem. Both of these two problems have been proved to be NP-complete and some related heuristic algorithms have also been proposed. For, the STBCGC (Steiner-Tree-Based Critical Grid Covering) algorithm was designed for solving the critical-square-grid coverage problem. The Reduction+PB (Reduction+Profit-Based) algorithm was designed for solving the weighted-critical-square-grid coverage problem. In this thesis, we have combined these two problems to form a new problem which we call the two-level critical-square-grid coverage problem. The goal of the two-level critical-square-grid coverage problem is to use a limited number of sensors to cover all of the critical square grids and to cover weighted critical square grids where the profits can be obtained to get the maximum sum of the profits. Obviously, a direct combination of the STBCGC algorithm and the Reduction+PB algorithm to form the STBCGC+PB algorithm is one of the possible solutions to the two-level critical-square-grid coverage problem. In this thesis, based on the STBCGC+PB algorithm, we propose a new heuristic algorithm to solve the two-level critical-square-grid coverage problem. Our heuristic algorithm improves three places of the STBCGC+PB algorithm. Two of the improvements allow our heuristic algorithm to cover some weighted critical square grids while it is carried out to cover critical square grids which must be covered such that a larger sum of profits can be obtained. The third improvement creates a greater chance to further obtain a larger sum of profits when our heuristic algorithm is carried out to cover weighted critical square grids. Finally, in this thesis, we use computer simulations to analyze and compare the performance of our heuristic algorithm and the STBCGC+PB algorithm. Computer simulation results show that compared to the STBCGC+PB algorithm, our heuristic algorithm can get a larger sum of profits.

目錄
摘要 i
ABSTRACT ii
目錄 iv
表目錄 v
圖目錄 vii
一、前言 1
1.1無線感測網路之介紹 1
1.2 無線感測網路之覆蓋問題 3
1.3 關鍵方格覆蓋問題 5
1.4 權重關鍵方格覆蓋問題 7
1.5本碩士論文擬研究之問題與主要成果 9
1.6本碩士論文之組織 14
二、文獻回顧 15
2.1 STBCGC演算法之描述 15
2.2 Reduction+PB演算法 33
三、我們所提出的啟發式演算法 51
3.1 STBCGC+PB演算法之描述 51
3.2 我們的啟發式演算法的主要觀念 80
3.2.1計算v_x之權重v_x_weigjt之方法的說明 87
3.2.2 弗洛伊德演算法 90
3.3我們的啟發式演算法之描述 96
3.4我們的啟發式演算法之範例 102
四、電腦模擬 123
五、結論 136
參考文獻 138

參考文獻
[1] 王友群，胡君琪，曾煜棋，“無線感測器網路系統之簡介”，國立交通大學，資訊工程學系，[online]，
http://people.cs.nctu.edu.tw/~wangyc/publications/reports/r001-maganize03-wsn.pdf (December 15, 2017).
[2] 林靖維，“平面環境中目標區域之偵測 - 使用行動感測網路技術”，國立 大學資訊管理研究所碩士論文，7月，2008。
[3] 曾煜棋，林政寬，林致宇，潘孟鉉，無線網路-通訊協定、感測網路、射 頻技術與應用服務，碁峯資訊股份有限公司，7月，2013。
[4] 簡志軒，“使用最少感測器來蓋滿重要區塊無線感測網路的有效率建構方法”，國立清華大學資訊工程研究所碩士論文，1月，2008。
[5]B. N. Clark, C. J. Colbourn, and D. S. Johnson, “Unit Disk Graphs,” Discrete Mathematics, vol. 86, pp. 165-177, 1990.
[6]T. H. Cormen, C. E. Leiserson, and R. L. Rivest, (1990). Introduction to Algorithms (1st ed.). MIT Press and McGraw-Hill.
[7]W. Ke, B. Liu, and M. Tsai, “The Critical-Square-Grid Coverage Problem in Wireless Sensor Networks is NP-Complete,” Computer Networks, vol. 55, no. 9, pp. 2209-2220, June 2011.
[8]W. Ke, B. Liu, and M. Tsai, “Efficient Algorithm for Constructing Minimum Size Wireless Sensor Networks to Fully Cover Critical Square Grids,” IEEE Transactions on Wireless Communications, vol. 10, no. 4, pp. 1154-1164, April 2011.
[9]P. Klein and R. Ravi, “A Nearly Best-Possible Approximation Algorithm for Node-Weighted Steiner Trees,” Journal of Algorithms, vol. 19, no. 1, pp. 104-115, 1995.
[10]B. Liu, N. Nguyen, V. Pham, and W. Wang, “Constrained Node-Weighted Steiner Tree Based Algorithms for Constructing a Wireless Sensor Network to Cover Maximum Weighted Critical Square Grids,” Computer Communications, vol. 81, pp. 52-60, May, 2016.
[11]S. Slijepcevic and M. Potkonjak, “Power Efficient Organization of Wireless Sensor Networks,” Proceedings of the IEEE International Conference on Communications, vol. 2, pp. 472-476, 2001.