最佳化k-阻障覆蓋問題(optimal k-barrier coverage problem, OKBCP)是探討如何在無線感測網路(wireless sensor network, WSN)之監控區域挑選感測器節點(sensor node)使其形成最高品質之k-阻障覆蓋，使每個穿越WSN監控區域的入侵者，都能被k個以上的偵測節點偵測到。而匯集節點連通性阻障覆蓋最佳化問題(sink-connected barrier coverage optimization problem, SCBCOP)則基於上述問題中加入探討如何選擇最少數量的轉傳節點(forwarding node)，使每個偵測節點(detecting node)皆具有連接至匯集節點之連通性(sink-connectivity)，藉以滿足帶狀監控區域之安全需求。然而，即使已有演算法(如optimal node selection algorithm, ONSA)可以找到具匯集節點連通性之最佳化k-阻障覆蓋，但因為有許多偵測節點會同時發送入侵資訊，因而可能形成大量封包干擾(或碰撞)而無法即時將入侵資訊通報至匯集節點。本論文之目的即為探討如何在最佳化k-阻障覆蓋中達成節點間降低干擾及路由路徑選擇且滿足匯集節點連通之性質。 針對上述問題，本論文提出: 1) 建立多匯集節點轉傳路由樹演算法，藉以滿足路由路徑建立及匯集節點之連通性。 2) 轉傳路由樹多頻道及時槽排程演算法，以進一步減少感測器節點間封包傳輸之干擾。我們使用OPNET模擬器上之IEEE 802.15.4模組來模擬所提出演算法之效能。實驗結果顯示，本研究所建立之演算法能有效減少感測器節點之封包傳輸干擾，因此具有最低封包丟失率、最短封包延遲以及最大網路平均吞吐量。 The optimal k-barrier coverage problem (OKBCP) deals with the selection of sensor nodes in wireless sensor network(WSN). The aim is to have any intruder who goes across monitoring area of the WSN detected by k or more detecting nodes. Based on the above scenario, the sink-connected barrier coverage optimization problem (SCBCOP) discusses how to select a minimal number of forwarding nodes, and ensure every detecting node with sink-connectivity to meet the safety requirements. Although there are algorithm (as optimal node selection algorithm, ONSA) that can be used to find optimal k-barrier coverage with sink-connectivity, the fact that multiple detecting nodes simultaneously transmit intrusion event could cause packet interference(or collision) and prevent intrusion event from being reported to the sink in real time. This study investigates methods for reducing interference and selecting routing paths among the nodes in optimal k-barrier coverage to satisfy sink-connectivity. To address the problems mentioned above, this study proposes the following strategies: 1) a multi-sinks forwarding routing trees algorithm to build routing paths and satisfy sink-connectivity. 2) a multi-channel and time-slot scheduling algorithm to further reduce the interference caused by packet transmission among sensors. This study employed the IEEE 802.15.4 module of OPNET simulator to simulate the performance of the proposed algorithms. Simulation results show that the proposed algorithm effectively reduces packet interference, and provides the lowest packet dropping rate and delay, as well as the highest throughput .
