Target Coverage是無線感測網路(Wireless Sensor Networks)重要的議題之一，當鄰近監控目標(target point)的Target Covering Sensors感測到事件發生時，必須立即將感測的資料回傳至主控中心(sink node)，進而對發生的事件進行即時性的處理。因此，Target Covering Sensors在偵測監控目標的同時，保持主控中心與監控目標間通訊上的連通性，是Target Coverage不可或缺的條件。本論文針對一隨機佈建的無線感測網路，提出有效的醒睡排程(ESAS)協定，以達到延長網路生命期、物體監控與維持網路通訊連通性的多重目的。為了方便尋找連通路徑以及電量的計算，我們在網路初始階段，整個無線感測區域依位置資訊劃分為許多Hexagons，並在此六角座標網路環境中探討共享通訊路徑及網路連通性等特性。根據這些特性，我們安排多組同時醒來或睡眠的Sensor Sets，並依時間的變化輪替醒睡狀態，以達到回傳資料的同時能維持網路連通性，並兼顧平均分散各相異路徑間電量消耗之要求，進而延長整體的網路生命期。

Target Coverage refers to the problem that finds the least number of sensors to cover a set of predefined target points in a Wireless Sensor Network (WSN). In the target coverage problem, the network connectivity should be maintained so that the sensors that cover the target point are able to report the target information from themselves to the sink node in a multi-hop manner. Since each sensor is battery powered, a sleep-awake scheduling for a target coverage application should take into consideration both network connectivity and energy conservation. This paper proposes an Efficient Sleep-Awake Scheduling (ESAS) mechanism to prolong the network lifetime as well as maintain the network connectivity for a given WSN. According to the target locations and path sharing requirement, the proposed ESAS mechanism partitions the sensors into a number of sets and each of them will wake up in turn to maintain the network connectivity and share the work load required for monitoring target points and communication tasks. As a result, several alternative paths that connect target regions and the sink node will be constructed with the property that different target regions can share the same path for minimizing the number of awaken sensors. Finally, performance study also reveals that the proposed approach considering the number of active sensors, least-hop sharing paths, and the energy conservation intro- and inter-cells outperforms the method without allowing for the energy consumption of idle listening.

Table of Contents
I. Introduction 1
II. Network Environment and Problem Formation 4
　2.1 Network Environment 4
　2.2 Problem Formation 4
III. Efficient Sleep-Awake Scheduling (ESAS) 8
　3.1 Network Partitioning Phase 9
　3.2 Sharing path discovery phase 12
IV. Improved ESAS (I-ESAS) 21
　4.1 Hexagonal agent in each cell 21
　4.2 Operation across cellular hops 21
V. Analysis of The Number of Deployed Sensors 23
VI. Performance 25
VII. Conclusion 29
References 30

List of Figures
Fig. 1: Hexagonal coordinate system in the WSN. 9
Fig. 2: Sensed data from two different Ct are transmitted by Cf and through the different sharing paths from Cb to Cs. 11
Fig. 3: Hexagonal length h decided by the sensing range and the communication range. 12
Fig. 4: Shortest-path discovery on Cartesian coordinate system. 13
Fig. 5: Unit vectors in hexagonal coordinate system. 14
Fig. 6: Three relaying paths Pij from Ci to Cj. 17
Fig. 7: Reducing the number of active sensors by discovering the share path. 18
Fig. 8: Relaying zone Rij means the union of all the possible paths. 19
Fig. 9: Discovery of sharing paths. 20
Fig.10 : Covering across cellular hops. 22
Fig. 11: Communicating across cellular hops. 22
Fig. 12: Active times of hexagons between relaying zones. 23
Fig. 13: Active times of hexagon Ck depends on both the source and destination cells Ci and Cj. 24
Fig. 14: Network lifetime vs. Number of deployed sensors. 26
Fig. 15: Network lifetime vs. Number of target points. 27
Fig. 16: Different number of sensors in relaying zones. (Random vs. Active times) 28

[1] H. Zhang and J. C. Hou, “Maintaining Sensing Coverage and Connectivity in Large Sensor Networks,” Ad Hoc & Sensor Wireless Networks, vol. 1, no. 1–2, March 2005, pp. 89–124.
[2] Y. Shang and H. Shi, “Coverage and Energy Tradeoff in Density Control on Sensor Networks,” in Proceedings of the IEEE International Conference on Parallel and Distributed Systems (IEEE ICPADS), July 2005.
[3] Y. C. Chen and C. Y. Chang, “On-Supporting Energy Balanced K-Barrier Coverage in Wireless Sensor Networks,” Workshop on Wireless, Ad Hoc, and Sensor Networks (WASN), September 2007.
[4] W. H. Teng, C. J. Yang, Y. C. Chen, and C. Y. Chang, “Energy Efficient Decentralized Maintenance Protocols for K-Barrier Coverage in Mobile WSNs,” Workshop on Wireless, Ad Hoc, and Sensor Networks (WASN), September 2008.
[5] K. Chakrabarty, S. Iyengar, H. Qi, and E. Cho, “Grid Coverage for Surveillance and Target Location in Distributed Sensor Networks,” IEEE Transactions on Computers, vol. 51, no. 12, December 2002, pp. 1448–1453.
[6] W. Wang, V. Srinivasan, B. Wang, and K. C. Chua, “Coverage for Target Localization in Wireless Sensor Networks,” IEEE Transactions on Wireless Communications, vol. 7, no. 2, February 2008, pp. 667–676.
[7] G. J. Fan, F. Liang, and S. Y. Jin, “An Efficient Approach for Point Coverage Problem of Sensor Network,” in Proceedings of the International Symposium on IEEE Electronic Commerce and Security, August 2008.
[8] M. Cardei and D. Z. Du, “Improving Wireless Sensor Network Lifetime through Power Aware Organization,” ACM Wireless Networks, vol. 11, no. 3, May 2005, pp. 333–340.
[9] M. Cardei, M. T. Thai, Y. Li, and W. Wu, “Energy-Efficient Target Coverage in Wireless Sensor Networks,” in Proceedings of the 24th Annual Joint Conference of the IEEE Computer and Communications Societies (IEEE INFOCOM), March 2005.
[10] M. Cardei, J. Wu, M. Lu, and M. O. Pervaiz, “Maximum Network Lifetime in Wireless Sensor Networks with Adjustable Sensing Ranges,” in Proceedings of the IEEE International Conference on Wireless and Mobile Computing, Networking and Communications (IEEE WiMob), August 2005.
[11] Hao Li, Huifang Miao, Li Liu, Lian Li, and Heping Zhang, “Energy Conservation in Wireless Sensor Networks and Connectivity of Graphs,” Theoretical Computer Science, ELSEVIER, vol. 393, no. 1-3, March 2008, pp. 81-89.
[12] M. Lu, J. Wu, M. Cardei, and M. Li, “Energy-Efficient Connected Coverage of Discrete Targets in Wireless Sensor Networks,” Lu, X., Zhao, W. (eds.): ICCNMC 2005, LNCS, vol. 3619, Springer, Heidelberg (2005), pp. 43–52.
[13] S. Cho, K. Kanuri, J. W. Cho, J. Y. Lee, S. D. June, “Dynamic Energy Efficient TDMA-based MAC Protocol for Wireless Sensor Networks,” IEEE Joint International Conference on Networking and Services (IEEE ICAS), 2005.
[14] He Chenguang, Sha Xuejun, “An Energy-Efficient Message Passing Approach in MAC Design for Wireless Sensor Networks,” IEEE ICCSC, 2008.
[15] Peng Sun, Xinming Zhang, Zhenzhong Dong, Yi Zhang, “A Novel Energy Efficient Wireless Sensor MAC Protocol,” IEEE NCM, 2008.
[16] Tahar Ezzedine, Mohamed Miladi and Ridha Bouallegue, “An Energy-Latency-Efficient MAC Protocol for Wireless Sensor Networks,” International Journal of Electronics, Communications and Computer Engineering, 2009.
[17] Yu-Chia Chang and Jang-Ping Sheu, “An Energy Conservation MAC Protocol in Wireless Sensor Networks,” Wireless Personal Communications, vol. 48, no.2 , January 2009.