從古至今，城堡外往往圍繞著護城河或是挖掘很深的溝渠來抵禦入侵者；而國與國之間的邊界通常派駐軍隊住紮來保護自己的疆土或以山脈河川做為屏障。將城堡的周圍或是國家的邊界佈置感測器並且達到完整覆蓋整個感測區域，即可利用感應器的感測能力來進行入侵者偵測，取代護城河的功能並且減少防守邊境所需消耗的人力資源。在傳統k-覆蓋能力的研究中，當監控區內的每個位置均被k個感應器的感測範圍所含蓋，稱為k-覆蓋能力，覆蓋數k值越高代表該區塊的偵測的能力越強，然而在護城河用途的無線感測網路中，其k-覆蓋能力定義為在邊界區域中有k個感測器可感應闖入者跨越邊界，由於與傳統無線感測網路有不同的應用場景，其k-覆蓋能力的問題亦應特殊設計及考量。本論文首先分析傳統覆蓋能力 與護城河覆蓋能力的不同點，之後並提出了一個演算法能針對邊界護城問題，找出最少的感應器集合使其可滿足最大覆蓋數，或是針對所指定的k值找出多組無交集的感應器集合，每個集合均滿足k-覆蓋能力以符合使用者的需求。實驗顯示本論文所提出的演算法能夠以較少的感測器個數達到最高的覆蓋數，並能使整個網路的感應器能耗電平衡。 The k-barrier coverage problem is known as the problem of detecting the intruders by at least k sensors when the intruders moving along the crossing paths from one boundary to another. This paper first analyzes the differences between the traditional coverage and barrier coverge problems, and then proposes decentralized algorithms to cope with the k-barrier coverage problem. For a given value k, the proposed algorithm finds out the maximum disjoint sets of sensors such that each set of sensors meets the requirement k-barrier coverage for users. Initially, the network monigoring region is partitioned into severl equal-sized grids based on the corse-grain policy. Then three mechanisms, called Basic, Backtracking, and Branch, are proposed for constructing as more as possible the disjoint sets of sensors that satisfy the requirement of k-barrier coverage. To increase the number of disjoint sets, the propsoed three mechanisms are extended based on the fine-grain policy. Simulation study compares the performance of the proposed mechanisms against the exhausted (optimal) algorithm in terms of the number of disjoint sets and the number of sensors in each set. Performance results reveal that the proposed algorithms achieve near-optimal performance.
