本論文期望在無線攝影機感測網路下，設計一個分散式演算法：Cellular-Based Barrier Coverage Algorithm，將所要監測之區域預先切割成多個Grid，並利用Grid之特性減少封包傳遞之次數，以達到節省攝影機感測器之電量，藉此提高攝影機感測器之生命週期（Lifetime），以延長整體無線攝影機感測網路之壽命。本論文所提出的演算法，在建立執行演算法的過程中，無需廣播任何封包給周圍鄰居，只需自己的位置資訊與鄰居之位置資訊即可快速建立多條Barrier Coverage，並且期望能夠利用較少量之攝影機感測器與減少封包之傳遞次數來達到節省攝影機感測器之電力消耗，以延長整體無線攝影機感測網路之生命週期。
最後透過模擬實驗之結果，驗證本論文所提出之演算法Cellular-Based Barrier Coverage Algorithm能夠有效率的減少封包傳遞之次數，並且減少攝影機感測器之數量，使得整體網路之生命週期得以延長。

In the paper, we design a discrete algorithm in wireless camera sensor networks. This algorithm is termed as “Cellular-Based Barrier Coverage Algorithm.” The algorithm divides the sensing area into grids and, by the characteristics of the cellular structure, can decrease the control overhead. Therefore, we can reduce the energy consumptions of camera sensors and prolong the network lifetime. “Cellular-Based Barrier Coverage Algorithm” needs not to flood packets around the network. The proposed algorithm only needs one-hop neighbor location information to construct a barrier line. Moreover, the control overhead can be decreased subsequently and the energy consumption of camera sensors can be saved as well.
Simulation results also show that the number of control packets, the energy consumptions of camera sensors, and the number of active camera sensors are reduced accordingly. Comprehensively, the proposed algorithm, Cellular-Based Barrier Coverage Algorithm, can effectively and efficiently construct a barrier line for wireless camera sensor networks.

第1章 緒論 1
1.1 前言 1
1.2 研究動機與目的 3
1.3 研究方法 5
1.4 論文架構 6
第2章 相關文獻 7
2.1 無線感測網路 9
2.2 無線多媒體感測網路 10
第3章 預備知識 13
3.1 網路架構 13
3.2 以Grid Model建立網路場景模型 14
3.3 相關定義 18
3.4 相關假設 21
第4章 Cellular-Based Barrier Coverage Algorithm 22
4.1 基本想法 22
4.2 問題轉換 25
4.3 如建立Barrier Line 27
4.3.1 大六邊形之解集合分類 28
4.3.2 小六邊形之解集合分類 31
4.4 Cellular-Based Barrier Coverage Algorithm 35
第5章 模擬結果 37
第6章 結論 42
Reference	 43
附錄-英文論文  48

List of Figures
圖 一 具Barrier Coverage之監視區域 2
圖 二 覆蓋示意圖 4
圖 三 覆蓋示意圖 8
圖 四 2-Barrier Coverage示意圖 10
圖 五 場景假設示意圖 14
圖 六 Flooding機制 15
圖 七 三邊形Grid Model 16
圖 八 四邊形Grid Model 17
圖 九 六邊形Grid Model 17
圖 十 入侵方向 18
圖 十一 扇形感測區域示意圖 19
圖 十二 六邊形內的感測連結示意圖 20
圖 十三 完全大六邊形Grid 22
圖 十四 完全小六邊形Grid 23
圖 十五 大小六邊形Grid轉換 24
圖 十六 問題轉換示意圖 26
圖 十七 問題轉換示意圖 26
圖 十八 迷宮路徑示意圖 27
圖 十九（a）SIL-S與（b）SOL-S 28
圖 二十（a）SIL-D與（b）SOL-D 29
圖 二十一 大六邊形之優先權觀察 30
圖 二十二 ISS 31
圖 二十三 OLS 32
圖 二十四 OBS 32
圖 二十五 ORS 33
圖 二十六 OFS 33
圖 二十七 小六邊形之優先權觀察 34
圖 二十八 六邊形Grid之場景示意圖 35
圖 二十九 Algorithm運作之示意圖 36
圖 三十 Barrier line平均使用攝影機感測個數 38
圖 三十一 Barrier line成功率與節點個數之影響 39
圖 三十二 平均一個節點傳送與接收封包的數量 40
圖 三十三 平均每個節點消耗之電量 40
圖 三十四 Barrier line成功率與場景寬度(W)之影響 41

List of Tables
表 1 模擬實驗參數 37

[1]C. F. Huang and Y. C. Tseng, “The Coverage Problem in a Wireless Sensor Network,” in International Workshop on Wireless Sensor Networks and Applications (WSNA), pp.115-121, Sep. 2003.
[2]C. Shen, W. Cheng, X. Liao, S. Peng, “Barrier Coverage with Mobile Sensors,” in Proceedings of the International Symposium on Parallel Architectures, Algorithms, and Networks Parallel Architectures, Algorithm, and Networks (ISPAN08), pp.99-104, May, 2008.
[3]Galstyan, B. Krishnamachari, K. Lerman, S. Pattem, “Distributed Online Location in Sensor Networks Using a Moving Target,” in Proceeding of the ACM/IEEE International Symposium on Information Processing in Sensor Networks (IPSN), pp. 61-70, Apr. 2004.
[4]Ian F. Akyildiz, T. Melodia, Kaushik R. Chowdhury, “A Survey on Wireless Multimedia Sensor Networks,” Computer Networks, pp. 921-960, Mar. 2006.
[5]J. Adriaens, S. Megerian, M. Potkonjak, “Optimal Worst-Case Coverage of Directional Field-of-View Sensor Networks,” 3rd Annual IEEE Communications Society on Sensor and Ad Hoc Communications and Networks (SECON’06), vol.1,no.,pp. 336-345, 28-28, 2006.
[6]J. Ford. “Telecommunications with MEMS devices: An overview,” The 14th annual meeting of the IEEE lasers and Elector-Optics society, vol.2,pp. 415-416, Nov. 2001.
[7]K.-Y. Chow, K.-S. Lui, and E. Y. Lam, “Maximizing Angle Coverage in Visual Sensor Networks,” in Proceedings of the IEEE International Conference on Communications (ICC), pp. 3516-3521, June 2007.
[8]L. Liu, H. Ma, and X. Zhang, “Collaborative Target Localization in Camera Sensor Networks,” in Proceedings of the IEEE Wireless Communications and Networking Conference (WCNC), pp. 2403-2407, Mar. 2008.
[9]L. Liu, H. Ma, and X. Zhang, “Analysis for Localization-Oriented Coverage in Camera Sensor Networks,” in Proceedings of the IEEE Wireless Communications and Networking Conference (WCNC), pp. 2579-2584, 2008.
[10]Ma, H. and Liu, Y. 2007. “Some problem of directional sensor networks”. International Journal of Sensor Networks. Vol 2, no. 1/2, pp. 44-52, 2007.
[11]N. Bulusu, J. Heidemann, and D. Estrin, “GPS-less Low Cost Outdoor Localization for Very Small Devices,” in Proceedings of the IEEE Personal Communications Magazine, vol. 7, no. 5, pp. 28-34, 2000.
[12]S. Kumar, T. H. Lai, and A. Arora, “Barrier Coverage with Wireless Sensors,” in Proceedings of the International Conference on Mobile Computing and Networking, pp. 284-298, Aug. 2005.
[13]S. Kloder and S. Hutchinson, “Barrier coverage for variable bounded range line-of-sight guards,” in Proceedings of the International Conference Robotics and Automation, vol. 1, pp. 391-396, Apr. 2007.
[14]S. Kloder, S. Hutchinson, “Partial barrier coverage: Using game theory to optimize probability of undetected intrusion in polygonal environments,” in Proceedings of the Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), May 2008.
[15]Weifang Cheng, Mo Li, Kebin Liu, Yunhao Liu, Xiangyang Li, and Xiangke, Liao, “Sweep Coverage with Mobile Sensors,” in Proceedings of the IEEE International Parallel & Distributed Processing Symposium (IPDPS), 2008.
[16]Xiaofeng Han, Xiang Cao, Errol L. Lloyd, and Chien-Chung Shen, “Deploying Directional Sensor Networks with Guaranteed Connectivity and Coverage,” in Proceedings of the IEEE Communications Society Conference on Sensor , MESH and Ad Hoc Communications and Networks (SECON), 2008.
[17]Benyuan Liu, Olivier Dousse, Jie Wang, and Anwar Saipulla, “Strong Barrier Coverage of Wireless Sensor Networks,” in Proceedings of the International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc), 2008.
[18]Jehn-Ruey Jiang and Tzu-Ming Sung, “Maintaining Connected Coverage for Wireless Sensor Networks" in The 28th International Conference on Distributed Computing Systems Workshops (ICDCS), 2008.
[19]Glen Takahara, Kenan Xu, and Hossam Hassanein, “Efficient Coverage Planning for Grid-Based Wireless Sensor Networks,” in Proceedings of the IEEE International Conference on Communications (ICC), 2007.
[20]Xueqing Wang, Yongtian Yang and Yibing Song, “Ɛ-Redundant Movement-assisted Sensor Deployment Based on Virtual Rhomb Grid in Wireless Sensor Networks,” in Proceedings of the International Conference on Mechatronics and Automation, June 25 - 28, 2006.
[21]Liang Liu, Xi Zhang, and Huadong Ma , “Minimal Exposure Path Algorithms for Directional Sensor Networks,” in Proceedings of the IEEE Global Telecommunications Conference (GLOBECOM), 2009.
[22]K.-P. Shih, C.-M. Chou, and I-H. Liu , “On Barrier Coverage in Wireless Camera Sensor Networks,” in Proceedings of the IEEE Advanced Information Networking and Applications (AINA), 2010.
[23]URL:http.tinyos.net