無線感測網路(wireless sensor network, WSN)可以在一個帶狀監控區域內形成一個阻障覆蓋(barrier coverage)，以偵測入侵者穿越監控區域事件的發生。而建構阻障覆蓋需要同時考慮覆蓋品質及建構成本。在覆蓋品質方面主要考慮的是：穿越偵測程度(degree) k 及每一對相鄰感測器所形成之偵測線段的偵測機率。在建構成本方面主要考慮的是：啟動的感測器個數及建構過程中所傳遞的訊息量。現有的研究大都以集中式(centralized)建構方法嘗試達成高覆蓋品質或低建構成本。本研究目的為利用分散式(distributed)的建構方法，在給定穿越偵測程度k值的條件下，盡可能地使用最少的感測器在WSN上建構阻障覆蓋，使得每一對相鄰感測器的偵測機率皆在門檻值(λ)之上。我們提出利用地理路由(geographical routing, GR)的路徑建構概念來建構阻障覆蓋的方法，由來源端節點(source node)開始發送建構阻障覆蓋的訊息，在經過一連串的中間節點之後達到目的端節點(destination node)，訊息傳送中的每個節點根據不同的選擇基準(角度、距離等)來選擇barrier中的下一個節點，當訊息抵達目的端時即構成阻障覆蓋。我們針對四種不同的地理路由(greedy routing scheme, most forward within radius routing, compass routing, random select routing)的路徑建構概念求得的阻障覆蓋與利用centralized algorithm求得的最佳覆蓋節點個數進行比較。實驗結果顯示greedy routing與most forward within radius routing在高偵測機率門檻值(λ)的情況下，相當逼近於最佳的節點個數且所產生的訊息量也最低。Some recent research uses a wireless sensor network (WSN) to form barrier coverage to detect intruders crossing a belt-shaped region. Constructing barrier coverage should consider the barrier coverage quality and the construction cost. In point of barrier coverage quality, we should consider the detection degree and the detection probability of the detection line between every pair of neighboring nodes. In point of construction cost, we should consider the number of delivered messages and the number of active nodes. Most research uses centralized algorithm to construct barrier coverage with high coverage quality and low construction cost. In this thesis, we study the optimization problem about how to construct in a distributed manner the barrier coverage with the detection degree of k and the detection quality larger than a threshold λ by using the minimized number of sensor nodes. Four distribution algorithms are proposed on the basis of different geographical routing schemes, which are the greedy routing, the most forward within radius routing, the compass routing, and the random select routing. Simulation experiments are conducted for evaluating the performance of the proposed algorithms in terms of the number of active sensor nodes and the number of delivered messages. The simulation results show the algorithm based on the greedy routing and the algorithm based on the most forward within radius routing both approach the bound of the optimal number of active sensor nodes, derived by a centralized optimization algorithm, and use the minimum number of delivered messages among the four algorithms.
