在無線感測網路中一項非常重要的議題為覆蓋問題，此問題主要探討要如何認一個特定觀察區域中，保證每個位置都要被至少k個感應節點覆蓋，而當某些特定位置並無法滿足此需求時，即稱為k層盲點。在應用層中，如果有k層盲點產生，則可能會造成無法收集足夠環境資訊而造成誤判，此即為k層盲點覆蓋問題。
因此，我們在此論文中提出了一個可以降低計算量，分散式計算系統，且可以應用於各種感應密度的演算法，其主要的優點如下。(1)提出一個有系統性的盲點偵測演算法, 藉此減少通訊能源的損耗。(2)減少配對鄰節點與交點的計算成本。(3)k層盲點可以藉由我們提出的演算法所計算的交點而被定位出來。(4)憑藉已計算出來的交點，我們可以針對修補盲點之節點作感測半徑調整達到能源的節省效果，
根據實驗的結果可以證實本論文所提出的演算法可以有效減少交點的計算與減少計算成本，這也證實了我們的演算法是一個有系統性的偵測k層盲點演算法。

One of the most important issues in wireless sensor networks is coverage problem, which describes how to guarantee the requirement of sensing degrees in an observing region. Moreover, a k-covered-blind spot indicate an area in the monitored region does not meet the coverage requirement. Blind spots would allow some events occurring within a monitored region without being detected or without sufficient information being collected for the applications. Wireless sensor networks with a coverage problem may lead to failures of applications. This is called the coverage problem with k-covered blind spots.

Thus, we propose an algorithm in this thesis to detect k-covered blind spots and recover these blind spots. The proposed algorithm has the following advantages: (1) A distributed system is proposed to relieve the energy consumption in communication. (2) Reduce the computation cost in pairing up the neighboring nodes and the number of intersection points. (3) The proposed scheme can pinpoint the k-covered blind spots by BSCPs. (4) Reduce the sensing range by BSCPs for energy conservation by using the adjustable sensing range to recover the k-covered blind spot.

Simulations show results in reducing the number of intersection points and taking only half of the computation cost. It reveals that the proposed scheme is a systematical algorithm to detect for the k-covered blind spot.

[1] I. F. Akyildiz, W. Su, Y. Sankarasubramaniam, and E .Cyairci, “A Survey on Sensor Networks,” IEEE Communications Magazine, pp.102-114, August 2002.
[2] S. Adlakha and M. Srivastava, “Critical density thresholds for coverage in wireless sensor networks,” Proceedings of the IEEE Wireless Communications and Networking, vol.3, pp1615-1620, 2003.
[3] X. Bai, S. Kumar, D. Xuan, Z. Yun and T. H. Lai, “Deploying Wireless Sensors to Achieve Both Coverage and Connectivity,” Proceedings of the 7th ACM international symposium on Mobile ad hoc networking and computing MobiHoc '06, pp131-142, May 2006.
[4] X Cheng, D-Z Du, L. Wang, and B. Xu, “Relay Sensor Placement in Wireless Sensor Networks,” Mobile Computing, IEEE Transactions on, 2003.
[5] J. Elson, L. Girod and D. Estrin, “Fine-Grained Network Time Synchronization using Reference Broadcasts,” ACM SIGOPS Operating Systems Review, vol 36, December 2002.
[6] G. Gupta, M. Younis, “Fault-tolerant Clustering of Wireless Sensor Network,” IEEE WCNC, pp.1579-1584, 2003.
[7] J. V. Greunen and J. Rabaey, “Lightweight Time Synchronization for Sensor Networks,” Proceedings of 2nd ACM International Conference on Wireless Sensor Networks and Applications, September 2003.
[8] S. Ganeriwal, R. Kumar and M. B. Srivastava, “Timing-sync Protocol for Sensor Networks,” Proceedings of the 1st International Conference on Embedded Networked Sensor Systems, November 2003.
[9] B. Hao, J. Tang and G. Xue, “Fault-Tolerant Relay Node Placement in Wireless Sensor Networks: Formulation and Approximation,” IEEE Workshop on High Performance Switching and Routing, pp.246-250, 2004.
[10] C. F. Hsin and M. Liu, “Network Coverage Using Low Duty-Cycled Sensors: Random & Coordinated Sleep Algorithms,” Proceedings of the 3rd ACM international symposium on Information processing in sensor networks IPSN '04, pp433-442, April 2004.
[11] C. F. Huang and Y. C. Tseng, “A Survey of Solutions to the Coverage Problems in Wireless Sensor Networks,” Journal of Internet Technology, vol.6, no 1, pp.1-8, 2005.
[12] C. F Huang, Y. C Tseng, “The Coverage Problem in a Wireless Sensor Network,”Mobile Networks and Applications, vol. 10, no 4, pp.519-528, August 2005.
[13] C. F Huang, L. C Lo, and Y.C Tseng, “Decentralized Energy-Conserving and Coverage-Preserving Protocols for Wireless Sensor Networks,” ACM Transactions on Sensor Networks, vol. 2, no 2, pp.182-187, May 2006.
[14] Y-T. Hou, T-C. Lee, B-C. Jeng, and C-M. Chen, “Optimal Coverage Deployment for Wireless Sensor Networks,” Proceedings of ICACT, pp.523-527, February 2006.
[15] S. Kumar, T. H. Lai and A. Arora, “Barrier Coverage With Wireless Sensors,” Proceedings of the 2006 workshop on Dependability issues in wireless ad hoc networks and sensor networks DIWANS '06, pp 284-298, September 2005.
[16] X. Y. Li, P-J. Wan, and O. Frieder, “Coverage in Wireless Ad Hoc Sensor Networks,” IEEE Transactions on Computers, vol.52, no 6, pp.753-763, June 2003.
[17] S. Meguerdichian, F. Koushanfar, G. Qu, M. Potkonjak, “Exposure In Wireless Ad-Hoc Sensor Networks,” Proceedings of the 7th annual internation conference on Mobile computing and networking (ACM MobiCom), pp.139-150, 2001.
[18] S. Meguerdichian, F. Koushanfar, M. Potkonjak, and M. B. Srivastava, “Coverage Problems in Wireless Ad-hoc Sensor Networks,” Proceedings of the 20th IEEE INFOCOM, pp.1380-1387, March 2001.
[19] S. Meguerdichian, F. Koushanfar, M. Potkonjak, and M. B. Srivastava, ”Worst and Best-Case Coverage in Sensor Networks,” IEEE Transactions on Mobile Computing, vol. 4, no. 1, pp.84-92, January 2005.
[20] M. P. Singh and M. M. Gore, “A Solution to Sensor Network Coverage Problem,” Personal Wireless Communications, ICPWC. IEEE International Conference, pp.77 – 80, January 2005.
[21] X. Shan, and J. Tan, “Mobile Sensor Deployment for a Dynamic Cluster-based Target Tracking Sensor Network,” IEEE/RSJ International Conf on Intelligent Robots and Systems, pp.741-746, 2005.
[22] D. Tian and N. D. Georganas, “A Coverage-Preserving Node Scheduling Scheme for Large Wireless Sensor Networks,” Proceedings of the 1st International Workshop on Wireless Sensor Networks and Application, pp.32-41, September 2002.
[23] Y. C Tseng, S. P Kuo, H. W Lee and C. F Hung, “Location Tracking in a Wireless Sensor Network by Mobile Agents and Its Data Fusion Strategies,” The computer journal vol. 47, no. 4, pp.448-460, 2004.
[24] G. Wang, G. Cao, and Tom Laporta, “A Bidding Protocol for Deploying mobile Sensors,” Proceedings of the 11th IEEE International Conference on Network Protocols, 2003.
[25] J. Wu, and S. Yang, “Coverage Issue in Sensor Networks with Adjustable Ranges,” Proceedings of the 23th ICPP Workshops, Montreal, Quebec, CANADA, pp.61-68, August 2004.
[26] P. J. Wan, and C. W. Yi, “Coverage by Randomly Deployed Wireless Sensor Networks,” IEEE Transactions on Information Theory, vol. 52, no 6, pp.2658-2669, June 2006.
[27] W. Wang, V. Srinivasan, B. Wang, and K-C Chua, “Coverage for Target Localization in Wireless Sensor Network” Proceedings of the 5th international conference on Information processing in sensor networks IPSN '06, pp.118-125, April 2006.
[28] X. Wang, G. Xing, Y. Zhang, C. Lu, R. Pless, and C. Gill, “Integrated Coverage and Connectivity Configuration for Energy Conservation in Sensor Networks,” ACM Transactions on Sensor Networks, vol. 1, no. 1, pp.36-72, August 2005.
[29] Y. Xi, J. heidemann, and D. Estrin, “Geography-informed Energy Conservation for Ad Hoc Routing,” In ACM, 7th Annual International Conference on Mobile Computing and Networking, pp.70-84, July 2001.
[30] T. Yan, T. He, John A, “Differentiated Surveillance for Sensor Network,” Proceedings of the 1st international conference on Embedded networked sensor systems, November 2003.
[31] H. Zhang, and J. C. Hou, “Maintaining Sensing Coverage and Connectivity in Large Sensor Networks,” AHSWN_07(Zhang) Ad Hoc & Sensor Wireless Networks, vol. 1, pp.89-124, March 2005.
[32] http://www.cse.nsysu.edu.tw/chinese/wordfile/course/1.pdf