無線感測網路(Wireless Sensor Network)可以在一段監控區域中感測入侵偵測事件的發生，並將事件傳送到資料匯集節點(sink)。如何在一個以隨機方式佈置的無線感測網路中挑選出適當的感測器節點，以形成一個邊界覆蓋(barrier coverage)來偵測入侵者(intruder)是一個重要的議題。建構邊界覆蓋需要同時考慮偵測程度或品質(degree or quality)以及挑選出的感測節點連接到資料匯集節點的連通性(sink-connected connectivity)。就我們所知，目前沒有任何研究同時探討邊界覆蓋的偵測品質及匯集節點連通性。本計畫的目的即為探討具匯集節點連通性邊界覆蓋最佳化問題(Sink-Connected Barrier Coverage Optimization Problem, SCBCOP)，此問題研究如何選擇感測器節點集合來建構出一個能達到以下二項最佳化目標的邊界覆蓋：(1)偵測程度最佳且進行偵測的節點(簡稱為偵測節點, detecting nodes)數量最少；(2)偵測節點具有匯集節點連通性且執行轉傳入侵事件的節點(簡稱為轉傳節點, forwarding nodes)數量最少數。本計畫嘗試以Edmonds-Karp maximum flow演算法以及Goldberg-Tarjan minimum cost flow演算法來解決SCBCOP問題並預計完成以下目標： 我們將提出一個最佳化節點選擇演算法(Optimized Node Selection Algorithm, ONSA)，來選擇數量最少的偵測節點，以形成穿越偵測程度最大化的邊界覆蓋，並且保證所有的偵測節點都具有連接到匯集節點的連通性(sink connectivity)。 時間複雜度分析: 我們將分析所提出演算法的時間複雜度，以量化其執行成本。 效能評估: 我們預計執行模擬實驗以完成所提出演算法的效能評估，來證實其邊界覆蓋穿越偵測程度、選擇的節點數量、以及其他重要的效能指標。Selecting sensor nodes to construct high-degree sensor barrier coverage for detecting intruders crossing a randomly-deployed wireless sensor network (WSN) is an important problem. To the best of our knowledge, no earlier research addresses the problem with the considerations that the selected nodes are connected to the sink node and that the number of the selected nodes is minimized. In this project, we take both considerations into account to study the Sink-Connected Barrier Coverage Optimization Problem (SCBCOP), which is the problem about how to select a sensor nodes set to reach two optimization goals: (1) to maximize the degree of barrier coverage by the minimum number of detecting nodes (i.e., the nodes for detecting intruders), (2) to make the detecting nodes connected to the sink node(s) by the minimum number of forwarding nodes (i.e., the nodes for forwarding intruder event notifications). The project aims at solving SCBCOP with the help of Edmonds-Karp maximum flow algorithm and Goldberg-Tarjan minimum cost flow algorithm to achieve the following goals. To design an Optimized Node Selection Algorithm (ONSA) for solving the SCBCOP problem. To perform time complexity analysis of the proposed algorithm for measuring the computation cost. To conduct simulation experiments to evaluate the performance of the proposed algorithm in terms of the barrier coverage quality and the number of selected nodes. 研究期間：10008 ~ 10107
