在建置稠密感測網路時，主要的挑戰是如何延長整個網路的使用期限，並同時維持較低的感測事件遺失率(sensing coverage loss ratio)，對於延長網路使用期限而言，積極的作為即是關掉冗餘感測節點(redundant nodes)以達到省電的效果，而維持較低的感測事件遺失率是感測網路的主要工作重點，多數的文獻所提的方法，每個感測節點需要精準的定位系統或者方向性天線來支援，因此提高了網路建置成本。另外，有些文獻所提的方法，乃是降低感測事件的獲得率，來達到省電的效果，然而，可能無法取得完整且重要的資訊。因此，如何降低感測事件的遺失率及網路建置成本是一個重要且高難度的課題。本研究提出的分群演算法(cluster-based algorithm)是一個具有彈性、可調整的省電機制，可依據不同的系統需要，達到延長網路使用期限及較低感測事件遺失率的要求，此方法不需額外的定位系統或者方向性天線支援，我們在不提高網路建置成本的前提，亦即低成本且有限能力的感測節點條件之下，模擬結果顯示分群演算法可達到延長網路使用期限，同時兼顧省電及感測事件獲得率。

A major challenge in constructing dense sensor networks is to prolong network lifetime as well as to keep low sensing coverage loss ratio. To prolong network lifetime, it is necessary to turn off redundant nodes to save energy. Moreover, to obtain low sensing coverage loss ratio is an important issue in dense sensor networks. Many off-duty eligibility rules that sensor nodes have expensive GPS (Global Positioning System) and directional antennas support have been proposed to determine redundant nodes. However, the system has high cost in deployment. In addition, some literature presented to sacrifice the sensing area to retrieve better network lifetime. However, this may not acquire completed and important information. Hence, how to reduce sensing coverage loss ratio and cost in deployment becomes an important and critical issue. We propose a cluster-based algorithm that can present a flexible, adjustable and energy-efficient scheme to identify redundant nodes for different requirements of network lifetime and low sensing coverage loss ratio. This algorithm needs without additional GPS and directional antennas support to identify redundant nodes. Our simulation results show that the cluster-based algorithm could save energy consumption under the process of determining redundant nodes for prolonging network lifetime, and achieve low sensing coverage loss ratio.

[1] A. Cerpa, J. Elson, D. Estrin, L. Girod, M. Hamilton, and J. Zhao, “Application Driver for Wireless Communications Technology,” ACM SIGCOMM Workshop on Data Communication in Latin America and Caribbean, San Jose, Costa Rica , vol. 3, no. 2, Apr. 2001, pp. 20–41.
[2] J. Carle and D. Simplot-Ryl, “Energy-efficient area monitoring for sensor networks,” Computer, vol. 37, no. 2, Feb. 2004, pp. 40-46.
[3] A. Mainwaring, D. Culler, J. Polastre, R. Szewczyk and J. Anderson, “Wireless sensor networks for habitat monitoring,” Proceedings of the 1st ACM International Workshop on Wireless Sensor Networks and Applications, Atlanta, Georgia, USA, Sep. 2002, pp. 28.
[4] L. Schwiebert, S. K.S. Gupta and J. Weinmann, “Research challenges in wireless networks of biomedical sensors,” Proceedings of the 7th Annual International Conference on Mobile Computing and Networking, Rome, Italy, Jul. 2001, pp. 151-165.
[5] M. Srivastava, R. Muntz and M. Potkonjak, “Smart Kindergarten: Sensor-based Wireless Networks for Smart Developmental Problem-solving Environments,” The Seventh Annual International Conference on Mobile Computing and Networking, Rome Italy, Jul. 2001, pp. 132-138.
[6] N. Xu, S. Rangwala, K. K. Chintalapudi, D. Ganesan , A. Broad, R. Govindan and D. Estrin, “A wireless sensor network For structural monitoring,” Proceedings of the 2nd International Conference on Embedded Networked Sensor Systems, Baltimore, MD, USA, Nov. 2004, pp. 13-24.
[7] F. Stann and J. Heidemann, “Rmst: Reliable data transport in sensor networks,” Proceedings of the 1st International Workshop on Sensor Net Protocols and Applications Anchorage, Alaska, USA, Apr. 2003, pp.102-112.
[8] T. He, S. Krishnamurthy, J. A. Stankovic, T. Abdelzaher, L. Luo, R. Stoleru, T. Yan, L. Gu, J. Hui and B. Krogh, “Energy-efficient surveillance system using wireless sensor networks,” Proceedings of the 2nd International Conference on Mobile Systems, Applications, and Services, Boston, MA, USA, Jun. 2004, pp. 270–283.
[9] Y. Gao, K. Wu and F. Li, “Analysis on the redundancy of wireless sensor networks,” International Conference on Mobile Computing and Networking Proceedings of the 2nd ACM International Conference on Wireless Sensor Networks and Applications, San Diego, CA, USA, Sep. 2003, pp. 108-114.
[10] J. Lu and T. Suda, “Coverage-aware self-scheduling in sensor networks,” Proceedings of the 18th Annual IEEE Workshop on Computer Communications, Dana Point, California, USA, Oct. 20-21, 2003, pp. 117-123.
[11] D. Tian and N. D. Georganas, “A coverage-preserving node scheduling scheme for large wireless sensor networks,” Proceedings of the 1st ACM International Workshop on Wireless Sensor Networks and Applications, Atlanta, Georgia, USA, Sep. 28, 2002, pp. 32-41.
[12] T. Yan, T. He and J. A. Stankovic, “Differentiated surveillance for sensor networks,” Proceedings of the 1st International Conference on Embedded Networked Sensor Systems, Los Angeles, California, USA, Nov. 05-07, 2003, pp. 51-62.
[13] D. Tian and N. D. Georganas, “Location and calculation-free node-scheduling schemes in large wireless sensor networks,” Elsevier Science: Ad Hoc Networks, Jan. 2004, vol. 2, no. 1, pp. 65-85.
[14] R. Kumar, V. Tsiatsis and M. B. Srivastava, “Computation hierarchy for in-network processing,” Proceedings of the 2nd ACM International Conference on Wireless Sensor Networks and Applications, San Diego, CA, USA, Sep. 2003, pp. 68-77.
[15] J. Hill, R. Szewczyk, A. Woo, S. Hollar, D. Culler and K. Pister, “System architecture directions for networked sensors,” ACM SIGPLAN Notices, vol. 35, no. 11, Cambridge, Massachusetts, USA, Nov. 2000, pp. 93-104.
[16] R. Min, M. Bhardwaj, S. H. Cho, A. Sinha, E. Shih, A. Wang, A. Chandrakasan, “Low Power Wireless Sensor Networks,” Proceedings of VLSI Design, Bangalore, India, Jan. 2001, pp. 205-210.
[17] M. J. Dong, K. G..Yung, W. J. Kaiser, “Low power signal processing architectures for network microsensors,” Proceedings of Low Power Electronics and Design on International Symposium, Aug. 1997, pp. 173-177.
[18] G.. Pottie and W. Kaiser, "Wireless integrated network sensors," Communication, ACM, vol. 43, May 2000, pp. 51--58.
[19] M. A. M. Viera, L. F. M. Viera, L. B. Ruiz, A. A. F. Loureiro, A. O. Fernandes and J. M. S. Nogueira, “Scheduling nodes in wireless sensor networks: A Voronoi Approach,” Proceedings of the 28th Annual IEEE International Conference on Local Computer Networks , Königswinter, Germany, Oct. 20-24, 2003, pp. 423-429.
[20] S. Slijepcevic and M. Potkonjak, “Power efficient organization of wireless sensor networks,” IEEE Int'l Conf. on Communications (ICC), Helsinki, Finland, 2001, pp. 472-476.
[21] C.-F. Huang and Y.-C. Tseng, “The coverage problem in a wireless sensor networks,” Proceedings of the 2nd ACM International Conference on Wireless Sensor Networks and Applications, San Diego, CA, USA, Sep. 2003, pp. 115-121.
[22] F. Ye, G.. Zhong, J. Cheng, S. Lu and L. Zhang, “a robust energy conserving protocol for long-lived sensor networks,” Proceedings of Distributed Computing Systems, May 2003, pp. 28–37.
[23] K. J. Krizman, T. E. Biedka and T. S. Rappaport, “Wireless position location: fundamentals, implementation, strategies and sources of error,” IEEE 47th Vehicular Technology Conference, vol. 2, Phoenix, AZ, USA, May 4-7, 1997, pp. 919-923.
[24] Chatterjee, S. K. Das and D. Turgut, “WCA: a weighted clustering algorithm for mobile ad hoc networks,” ACM Cluster Computing, vol. 5, no. 2, Apr. 2002, pp. 193-204.
[25] S. Bandyopadhyay, E.J. Coyle, “An energy efficient hierarchical clustering algorithm for wireless sensor networks,” INFOCOM: 21th Annual Joint Conference of the IEEE Computer and Communications Societies, vol. 3, Mar.- Apr. 2003 pp. 1713–1723.
[26] G.. Gupta, M. Younis, “Fault-tolerant clustering of wireless sensor networks,” WCNC: Wireless Communications and Networking, vol. 3, Mar. 2003 pp. 1579–1584.
[27] G.. Gupta, M. Younis, “Load-balanced clustering of wireless sensor networks,” ICC: International Conference on Communications, vol. 3, May 2003, pp. 1848–1852.
[28] A. D. Amis, R. Prakash, T. H. P. Vuong, D. T. Huynh, “Max-min d-cluster formation in wireless ad hoc networks,” INFOCOM: Proceedings of 19th Annual Joint Conference of the IEEE Computer and Communications Societies, vol. 1, Mar. 2000, pp.32-41.
[29] S. Bandyopadhyay, E. J. Coyle, “Minimizing communication cost in hierarchically clustered networks of wireless sensors,” WCNC: Wireless Communications and Networking, vol. 2, 16-20 Mar. 2003, pp. 1274-1279.
[30] W. R. Heinzelman, A. Chandrakasan and H. Balakrishnan, “Energy efficient communication protocol for wireless microsensor networks,” Proceedings of the 33rd Annual International Conference on System Sciences, vol. 2, Hawaii, USA, Jan. 4-7, 2000, pp. 10.
[31] S. Chugh, S. Dharia and D. P. Agrawal, “An energy efficient collaborative framework for event notification in wireless sensor networks,” Proceedings of the 28th Annual IEEE International Conference on Local Computer Networks, Königswinter, Germany, Oct. 20-24, 2003, pp. 430-438.
[32] S. Basagni, “Distributed clustering for ad hoc networks,” Proceedings of International Symposium on Parallel Architectures, Algorithms and Networks, Jun. 1999, pp. 310-315.
[33] S. Agarwal, R. H. Katz, S.V. Krishnamurthy, S. K. Dao, “Distributed power control in ad-hoc wireless networks,” 12th IEEE International Symposium on Personal, Indoor and Mobile Radio Communications, vol. 2, Sep.-Oct. 2001, pp. 59-66.
[34] S. Adlakha and M. Srivastava, “Critical density thresholds for coverage in wireless sensor networks,” IEEE Wireless Communications and Networking, vol. 3, New Orleans, Louisiana, USA, Mar. 16-20, 2003, pp. 1615-1620.
[35] V. Kawadia, P. R. Kumar, “Power control and clustering in ad hoc networks,” INFOCOM: 21th Annual Joint Conference of the IEEE Computer and Communications Societies, vol. 1, Mar.-Apr. 2003, pp. 459-469.
[36] A. Muqattash, M. M. Krunz, “1A distributed transmission power control protocol for mobile ad hoc networks,” IEEE Transactions on Mobile Computing, vol. 3, no. 2, Apr.-Jun. 2004, pp. 113-128
[37] K. Sohrabi, J. Gao, V. Ailawadhi and G. J. Pottie, “Protocols for self-organization of a wireless sensor network,” IEEE Personal Communications, vol. 7, no. 5, Oct. 2000, pp. 16-27.
[38] Z. Huang, C.-C. Shen, C. Srisathapornphat and C. Jaikaeo, “Topology control for ad hoc networks with directional antennas,” Proceedings of the 11th International Conference on Computer Communications and Networks, Miami, Florida, USA, Oct. 14-16, 2002, pp. 16-21.
[39] B. Deb, S. Bhatnagar and B. Nath, “A Topology Discovery Algorithm for Sensor Networks with Applications to Network Management,” DCS Technical Report DCS-TR-441, Rutgers University, May 2001.
[40] L. Li, J. Halpern, V. Bahl, Y.-M. Wang and R. Wattenhofer, “Analysis of a cone-based distributed topology control algorithm for wireless multi-hop networks,” Proceedings of the 20the annual ACM Symposium on Principles of Distributed Computing (PODC), Newport, Rhode Island, USA, 2001, pp. 264-273.