從古至今，城堡外往往圍繞著護城河或是挖掘很深的溝渠來抵禦入侵者；而國與國之間的邊界通常派駐軍隊住紮來保護自己的疆土或以山脈河川做為屏障。將城堡的周圍或是國家的邊界佈置感測器並且達到完整覆蓋整個感測區域，即可利用感應器的感測能力來進行入侵者偵測，取代護城河的功能並且減少防守邊境所需消耗的人力資源。在傳統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.

目    錄	I
圖 目 錄	III
表 目 錄	V
第一章、緒論	1
第二章、網路環境與問題敘述	6
2.1 網路環境與注釋	6
2.2 問題敘述	6
2.3 本論文擬克服的困難	11
第三章、Analyze on Curve Coverage and Sensor Selections	13
第四章、Coarse-Grain Problem Formulation and Its Solution to K-Coverage Problem	17
4.1 Network Initialization	17
4.2 Approaches to K-Barrier Coverage Problem	19
4.2.1 CGA-Coarse Grain Approach	19
4.2.2 FGA-Fine Grain Approach	34
4.2.3 GA-Gridless Approach	39
第五章、模擬實驗	41
5.1 Simulation Model	41
5.2 實驗結果	41
第六章、結論	51
參考文獻	52
附錄─英文論文 54
圖 目 錄
圖(一)：    Crossing paths和Not crossing paths。	7
圖(二)：    單一管狀之防禦曲線。	8
圖(三)：    形成分枝之防禦曲線。	8
圖(四)：    1-cover示意圖。	9
圖(五)：    0-cover表示圖。	10
圖(六)：    三種不同3-coverage的連線方式，(a)一條3-coverage曲線，(b)2-coverage加1-coverage曲線，(c) 三條1-coverage圖曲線。	13
圖(七)：    (a)以直線方式擺放sensors而 (b)以斜線方式擺放sensors，直線方式所需的sensor nodes個數較斜線來的少。	14
圖(八)：    (a)sensors的sensing range均相切較而(b)sensor的sensing range無相切，sensing range相切所需的sensor nodes個數較無相切來的少。	15
圖(九)：    三種coverage放置方法對於3-coverage的點數比較圖。	16
圖(十)：    CGA網路拓墣圖。	18
圖(十一)：  CGA網路大小示意圖。	18
圖(十二)：  CGA網路資訊圖。	19
圖(十三)：  網格優先權順序表示圖。	21
圖(十四)：  Forwarding Only Rule遇到的狀況。	23
圖(十五)：  Backtracking Rule表示圖。	26
圖(十六)：  削減多餘的sensor nodes以減少電量消耗。	28
圖(十七)：  局部Branch mechanism示意圖。	33
圖(十八)：  Top Down方式進行Branch Mechanism的網格優先權順序圖。	33
圖(十九)：  完整的Branch mechanism示意圖。	34
圖(二十)：  網格縮小示意圖。	35
圖(二十一)：封包格式示圖。	36
圖(二十二)：FGA網格資訊圖。	36
圖(二十三)：FGA第一條限制表示圖。	38
圖(二十四)：FGA第二條限制表示圖。	38
圖(二十五)：GA示意圖。	40
圖(二十六)：MDP之control overhead。	43
圖(二十七)：論文場景圖。	44
圖(二十八)：在不同sensor數量下各機制所能滿足2-coverage之組數。	46
圖(二十九)：在不同sensor數量下各機制所能滿足3-coverage之組數。	47
圖(三十)：  網路生存期比較圖。	48
圖(三十一)： Coarse Grain下不同sensor數量及作法排序所滿足2-coverage之組數。	49
圖(三十二)：Fine Grain(5m)下不同sensor數量及作法排序所滿足3-coverage之組數。	50
表 目 錄
表(一)：    各符號定義。	7
表(二)：    實驗參數表。	41
表(三)：    Coverage能力和sensor數量比較表。	45

[1]	C. F. Huang and Y. C. Tseng, ”The Coverage Problem in a Wireless Sensor Network,” in International Conference on Wireless Sensor Networks and Applications (WSNA),  pp. 115-121, Sandiago, CA, 2003.
[2]	B. Y. Liu, P. Brass, O. Dousse, P. Nain, and D Towsley, “Mobility Improves Coverage of Sensor Networks,” in Proceedings of the 6th ACM International Symposium on Mobile Ad Hoc Networking and Computing, pp. 300-308, 2005. 
[3]	A. Gallais, J. Carle, and David Simplot-Ryl, “Localized Sensor Area Coverage With Low Communication Overhead,” in Internation Conference on Pervasive Computing and Communications (PerCom),  pp. 2006. 
[4]	Y. Shang, and H. Shi, “Coverage and Energy Tradeoff in Density Control on Sensor Networkd,” in International Conference on Parallel and Distributed Systems (ICPADS), pp. 2005.
[5]	S. Kumar, T. H. Lai, and A. Arora, “Barrier Coverage with Wireless Sensors,” in Proceedings of the 11th annual International Conference on Mobile Computing and Networking (MobiCom), pp. 284-298, 2005. 
[6]	A. Schrijver. ”Combinatorial Optimization,” Springer, 2003.
[7]	S. Kumar, T. H. Lai, and K. Balogh. “On k-coverage in a mostly sleeping sensor network,” in International Conference on Mobile Computing and Networking (MobiCom), pp. 144-158, Philadelphia, PA, 2004.
[8]	Y. Zou and K. Chakrabarty, “A Distributed Coverage- and Connectivity- Centric Technique for Selecting Active Nodes in Wireless Sensor Networks,” IEEE Transaction on Computers, vol. 54, Issue 8, pp. Aug. 2005.
[9]	M. Cardi and J. Wu, “Energy-Efficient coverage problems in Wireless Ad Hoc Sensor Networks,” Computer Communication, vol. 29, issue 4, pp. 413-420, Feb. 2006.
[10]	M. Cardi and D.-Z. Du, “Improving Wireless Sensor Network Lifetime through Power Aware Organization,” Wireless Networks, 11(3), vol. 11, No. 3, pp.333-340, May, 2005.
[11]	Q. Zhao and M. Gurusamy, “Maximizing Network Lifetime for Connected Target Coverage in Wireless Sensor Networks,” in IEEE International Conference on Wirless and Mobile Computing, Networking and Communications (WiMob), pp.94-101, 2006.
[12]	M. Cardi, T. Thai, Y. Li and W. Wu, “Energy-Efficient Target Coverage in Wirless Sensor Networks,” in Proceedings of IEEE INFOCOM, vol. 3, pp. 1976-1984, 2005.
[13]	H. Yu, J. Iyer, H. Kim, E. J. Kim, K. H. Yum, P. S. Mah, “Assuring K-Coverage in the Presence of Mobility in Wireless Sensor Networks,“ in IEEE Global Telecommunications Conference (GlobeCom), pp, 1-5, 2006.
[14]	C. T. Vu, S. Gao, W. P . Deshmukh, Y. Li, “Distributed Energy-Efficient Scheduling Approach for K-Coverage in Wireless Sensor Networks,” in IEEE Military Communications Conference (MILCOM), pp. 1-7, 2006.