摘要
无线传感器网络是由部署在监测区域内的传感器节点通过无线通信方式形成的一个多跳自组织网络,具有低功耗、低成本及易于部署的特性,在军事安全、环境监测、远程医疗等诸多领域有很好的应用前景。构成网络的传感器节点能量有限,难以满足网络长期稳定运行的应用需求,限制了传感器网络的应用。用能量有限的节点实现期望的网络生命期,成为传感器网络研究中最关心的问题。目前最常见也是最直接的解决方法就是节点休眠调度策略:利用网络部署的冗余性,通过保持冗余节点休眠,节省节点能耗,延长网络系统的生存期。
本文基于IEEE 802.11 MAC协议,针对如何在满足应用需求的同时,提高网络生存期,开展了以下研究工作:
针对目前缺少兼顾网络区域覆盖、网络连通和节点保护的节点调度策略,提出一种基于分布式节点冗余性判定机制的节点休眠调度策略——ECNS算法。ECNS中,节点通过局部通讯获取局部拓扑信息,并利用该信息独立地判定其冗余性;冗余节点进入休眠状态,其余节点则处于活跃状态,感知并传输数据。通过关闭冗余节点,ECNS可以在满足网络覆盖、连通以及节点自我保护的同时,有效的延长网络生存期。ECNS可以有效地平衡网络中节点的负载和能耗,具有分布式的实现方式和低通讯代价及低计算复杂度。通过与分簇式的路由协议LEACH相结合,对ECNS的性能进行了评估,仿真实验表明,与未使用ECNS的LEACH协议相比,ECNS可有效降低节点能耗,延长网络生存期。
针对多孤立目标连续监控的传感器网络,本文提出一种分布式的节点休眠调度策略——CTMNS算法,以提高该类网络的节点能量利用率,延长网络生存期。该算法可以对网络中多个孤立目标提供连续监控,允许不同的目标有不同的期望覆盖度。在CTMNS中,每个传感器节点都关联一个与节点分布和剩余能量相关的权值,节点可以独立地计算其关联权值大小,并通过局部通信计算权值在临近节点中的排序,利用节点冗余性判定机制,节点根据排序结果判定其冗余性,冗余性为真的节点关闭电源处于休眠状态,其余节点进一步利用CTMNS决定是否保持活跃,以满足对目标的监控需求。仿真结果表明, CTMNS可将对目标的有效监控时间提高到无节点休眠调度策略的目标监控算法的2.7倍。
Wireless sensor network is a multi-hop ad hoc network consisting of a large number of sensors deployed in the monitoring region. Sensor network has promising prospects in many areas such as military monitoring, environment surveillance and telemedicine, since it is easy to deploy and operates with low cost and low power. Due to the severe energy constraint of the sensor nodes, wireless sensor network can hardly satisfy the long-term operation demand. How to use the resource limited sensor nodes to achieve the desired network lifetime is a fundamental problem of wireless sensor network. Node scheduling scheme is the most frequently used approach in literature; by putting redundant nodes into sleep mode and keeping only a subset of sensors active, node scheduling scheme can reduce the energy consumption and prolong the network lifetime effectively.
Based on IEEE 802.11 MAC protocol, this thesis focuses on extending network lifetime while satisfying application demand. Specifically, the following problems are studied in this paper.
An energy efficient coverage based node scheduling algorithm Energy aware Coverage based Node Scheduling scheme (ECNS) is proposed to prolong network lifetime while maintaining network coverage, network connectivity and sensor self-protection. ECNS enables each node to decide whether it is eligible to turn off to conserve energy through local information exchange with its neighbors. ECNS is characteristic of its fully distributed manner, low overhead and load balance. The cluster-based routing algorithm, LEACH, is implemented to evaluate the performance of ECNS; simulation results show that ECNS can improve the network performance with respect to energy conservation, load balance and network lifetime.
Considering the lack of node scheduling algorithm based on continuous monitoring of isolated targets, a novel distributed node scheduling algorithm, Continuous Target Monitoring based Node Scheduling scheme (CTMNS) is put forward in this thesis. To improve the energy efficiency and extend the network lifetime for isolated targets monitoring applications, CTMNS activates only a subset of sensors in the network to provide desired coverage level for multiple isolated targets. In CTMNS, each sensor is associated with a location-and-energy dependent weight, which evaluates the sensor’s significance in terms of target monitoring. Each sensor calculates its associated weight individually and determines its redundancy eligibility through local communication with its neighbors based on the Redundancy Eligibility Rule. By turning off redundant nodes, CTMNS prolongs network lifetime while providing differentiated coverage for multiple targets. Simulation results show that CTMNS prolongs the network lifetime to 2.7 times that of non-scheduled target monitoring scheme.
引文
[1] Gajbhiye P, Mahajan A. A Survey of Architecture and Node Deployment in Wireless Sensor Network[C]. 1st International Conference on the Applications of Digital Information and Web Technologies, ICADIWT 2008, 426-430, 2008.
[2] Jain S, Srivastava S. A Survey and Classification of Distributed Scheduling Algorithms for Sensor Networks [C]. Proceedings of International Conference on Sensor Technologies and Applications SENSORCOMM, 2007, 88-93.
[3] Singh C P, Vyas O P, Tiwari M K. A Profound Survey of Sensor Networks & Related Routing Protocols[C]. 2008 International Conference on Wireless Communications, Networking and Mobile Computing, WiCOM 2008.
[4] Lu J, Wang J S, Suda T. Scalable Coverage Maintenance for Dense Wireless Sensor Networks[C]. 3rd Annual IEEE Communications Society on Sensor and Ad Hoc Communications and Networks (SECON '06), IEEE Press, Reston, VA, USA, September 2006, 651-660.
[5] Tian D, Georganas N D. A Coverage-Preserving Node Scheduling Scheme for Large Wireless Sensor Networks [C], Proceedings of the 1st ACM International Workshop on Wireless Sensor Networks and Applications, ACM Press, Atlanta, Georgia, USA, 2002, 32-41.
[6] Mainwaring A, Polastre J, Szewczyk R et al. Wireless sensor networks for habitat monitoring. In ACM International Workshop on Wireless Sensor Networks and Applications, Atlanta, GA, 2002.
[7]彭刚,刘戎,王方年等。无线传感器网络研究概述[J]。广西科学院学报,2007,23(4):369-372。
[8]孙利民,李建中,孙渝等。无线传感器网络[M]。清华大学出版社,北京:2005
[9] Iyengar R, Kar K, Banerjee S. Low-coordination Topologies For Redundancy In Sensor Networks[C]. Proceedings of ACM International Symposium on Mobile Ad Hoc Networking and Computing, 332-342, 2005.
[10]于继明。2008。无线传感器网络基于分簇的多路径路由算法研究[D]:博士。南京:南京理工大学,1-9。
[11] Ghosh A, Givargis T. LORD: A Localized, Reactive and Distributed Protocol for Node Scheduling in Wireless Sensor Networks[C]. Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE’05).
[12]李建中,高宏。无线传感器网络的研究进展[J]。计算机研究与发展,2008,45(1):1-15。
[13] Lu K Z, Huang L S, Wan Y Y. Energy-Efficient Data Gathering in Large Wireless Sensor Networks[C]. Proceedings of the Second International Conference on Embedded Software and Systems (ICESS’05).
[14] Kim H, Seok Y, Choi N et al. Optimal multi-sink positioning and energy-efficient routing in wireless sensor networks. Lecture Notes in Computer Science (LNCS), Springer-Verlag, Number 3391: 264-274, 2005.
[15] Gandham S R, Dawande M, Prakash R et al. Energy efficient schemes for wireless sensor networks with multiple mobile base stations[C]. Proceedings of the IEEE Global Telecommunications Conference (GLOBECOM), 2003, 377-381.
[16] Bi Y Z, Niu J W, Sun L M. Moving Schemes for Mobile Sinks in Wireless Sensor Networks[C]. Proceedings of the IEEE International Performance, Computing, and Communications Conference (IPCCC 07), 2007, 101-108.
[17] Lewis F L. Wireless sensor networks [M]. In D.J. Cook and S.K. Das, editors, Smart Environments: Technologies, Protocols, and Applications, John Wiley, New York, 2004.
[18] Cui L, Ju H L, Miao Y et al. Overview of wireless sensor networks [J]. Journal of Computer Research and Development, 2005, 42(1):163-174.
[19] IEEE. IEEE Standard 802.11. Part II: Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications. Washington: IEEE Computer Society Press, 1999, 70-79.
[20] Sheng M, Li J D, Li W Y. A New Multiple Access Protocol for the Ad Hoc Network [J]. Journal of Xidian University, 2002, 29(6): 713-715.
[21] Ren F Y, Huang H N, Lin C. Wireless sensor networks [J]. Journal of Software, 2003, 14(7):1282-1291.
[22] Holger K, Andreas W. A short survey of wireless sensor networks. TKN Technical Report TKN-03-018, Technical University Berlin, October 2003.
[23] Hill J, Szewczyk R, Woo A et al. System architecture directions for networked sensors [C]. Proceedings of the 9th International Conference on Architectural Support for Programming Languages and Operating Systems, Cambridge, MA, November 2000.
[24] Min R, Bhardwaj M, Cho S et al. An architecture for a power aware distributed microsensor node [C]. Proceedings of the IEEE Workshop on signal processing systems (SIPS), October 2000.
[25] Hwang S F, Su Y Y, Lin Y Y. A Cluster-Based Coverage-Preserved Node Scheduling Scheme in Wireless Sensor Networks [C]. International Conference on Mobile and Ubiquitous Systems, 2006.
[26] Kumar H, Sarma D, Kar A. Security Threats in Wireless Sensor Networks[C]. Proceedings of 40th Annual IEEE International Carnahan Conferences on Security Technology, October 2006: 243-251.
[27] Jia X Y, Wang C. The Security Routing Research for WSN in the Application of Intelligent Transport System[C]. Proceedings of the 2006 IEEE International Conference on Mechatronics and Automation, 2006.
[28] Akyildiz I, Su W, Sankarasubramaniam Y et a1.Wireless sensor networks: A survey [J]. Computer Networks: The International Journal of Computer and Telecommunications Networking, 2002, 38(4):393-422.
[29] Wan P J, Yi C W. Coverage by Randomly Deployed Wireless Sensor Networks [J]. IEEE Transactions on Information Theory, 2006, 52(6): 2658-2669.
[30] Huang C F, Tseng Y C, Wu H L. Distributed Protocols for Ensuring Both Coverage and Connectivity of a Wireless Sensor Network [J]. ACM Transactions on Sensor Networks, Vol. 3, No. 1, Article 5, 2007.
[31] Ma M, Yang Y Y. Clustering and Load Balancing in Hybrid Sensor Networks with Mobile Cluster Heads [C]. ACM International Conference Proceeding Series - Proceedings of the 3rd International Conference on Quality of Service in Heterogeneous Wired/Wireless Networks. Vol. 191, Article No. 16, 2006.
[32] Du X J, Lin F J. Improving Sensor Network Performance by Deploying Mobile Sensors[C]. Conference Proceedings of the 24th IEEE International Performance, Computing, and Communications Conference, IPCCC 2005, 67-71, 2005.
[33] Lu J, Suda T. Differentiated Surveillance for Static and Random Mobile Sensor Networks [J]. IEEE Transactions on Wireless Communications, 2008, 7(11):4411-4423.
[34] Chatzigiannakis I, Kinalis A, Nikoletseas S. Sink Mobility Protocols for Data Collection in Wireless Sensor Networks[C]. Proceedings of the 2006 ACM International Workshop on Mobility Management and Wireless Access, v 2006: 52-59, 2006.
[35] Chatzigiannakis I, Kinalis A, Nikoletseas S et al. Fast and Energy Efficient Sensor Data Collection by Multiple Mobile Sinks[C]. Proceedings of the 5th ACM international workshop on Mobility management and wireless access. Chania, Crete Island, Greece. 2007: 25-32.
[36] Kalidindi R, Kannan R, Iyengar S et al. Distributed Energy Aware MAC Layer Protocol For Wireless Sensor Networks[C]. Proceedings of the International Conference on Wireless Networks, ICWN 03: 282-286, 2003.
[37] Ji P, Wu C D, Zhang Y Z et al. Research of an energy-aware MAC protocol in Wireless Sensor Network[C]. Chinese Control and Decision Conference, 2008, CCDC 2008:4686-4690.
[38] Goyeneche M, Villadangos J, Astrain J J. A distributed data gathering algorithm for wireless sensor networks with uniform architecture[C]. International Workshop on Modeling Analysis and Simulation of Wireless and Mobile Systems, Proceedings of the 3rd ACM international workshop on Performance evaluation of wireless ad hoc, sensor and ubiquitous networks. Terromolinos, Spain, 2006: 162-166.
[39] Krishnamachari B, Estrin D, Wicker S. Modeling data-centric routing in wireless sensor networks[C]. Proceedings of 21st Annual Joint conference of the IEEE Computer and communications Societies, June 2002.
[40] Intanagonwiwat C, Govindan R, Estrin D. Directed Diffusion: A Scalable and Robust Communication Paradigm for Sensor Networks[C]. ACM/IEEE International Conference on Mobile Computing and Networks (MobiCom 2000), August 2000, Boston, Massachusetts.
[41] Krishnamachari B, Estrin D, Wicker S B. The impact of data aggregation in wireless sensor networks[C]. ICDCSW’02: Proceedings of the 22nd International Conference on Distributed Computing Systems. Washington, DC, USA: IEEE Computer Society, 2002: 575–578.
[42] Zhang H, Hou J C. Maintaining sensing coverage and connectivity in large sensor networks [J]. Ad Hoc &Sensor Wireless Networks, 2003, 1(1): 89-124.
[43] Xing G L, Wang X R, Zhang Y F et al. Integrated coverage and connectivity configuration for energy conservation in sensor networks [J]. ACM Transaction on Sensor Networks (TOSN), Aug. 2005, 1(1): 36-72.
[44] Yener B, Malik M I, Sivrikaya F. Joint problem of power optimal connectivity and coverage in wireless sensor networks [J]. Wireless Networks, 13(4): 537-550, August 2007.
[45]叶驰,孙利民,廖勇.传感器网络的能量管理[J].计算机工程与应用. 2004, (8):196-198.
[46] Lindsey S, Raghavendra C S. PEGASIS: Power-efficient gathering in sensor information systems[C]. Proceedings of the IEEE Aerospace Conference. Piscataway, NJ, USA: IEEE, 2002:1125-1130.
[47] LAN MAN Standards Committee of the IEEE Computer Society, Wireless LAN medium access control (MAC) and physical layer (PHY) specification, IEEE, New York, USA, IEEE Std 802.11 - 1997 edition, 1997.
[48] Jung S M, Han Y J, Chung T M. The Concentric Clustering Scheme for Efficient Energy Consumption in the PEGASIS[C]. 9th International Conference on Advanced Communication Technology, ICACT2007, v 1, 260-265.
[49] Jamal N. Al-Karaki, Ahmed E. K. Routing Techniques in Wireless Sensor Networks: A survey [J]. IEEE Wireless Communications, 2004, 11(6): 6-28.
[50] Wen Y F, Yeong F, Sung L, Kuo W C. A tree-based energy-efficient algorithm for data-centric wireless sensor networks [C]. Proceedings of the 21st International Conference on Advanced Information Networking and Applications, AINA 2007: 202-209.
[51] Moh M, Dumont M, Moh T S. Evaluation of Dynamic Tree-based Data Gathering Algorithms for Wireless Sensor Networks[C]. Proceedings of the Fifth IEEE International Symposium on Signal Processing and Information Technology, v 2005, 170-175, 2005.
[52] Heinzelman W B, Chandrakasan A P, Balakrishnan H. An application-specific protocol architecture for wireless microsensor networks [J]. IEEE Transactions on Wireless Communications, October 2002, 1(4): 660-670.
[53] Mandala D, Dai F, Du X J. Load Balance and Energy Efficient Data Gathering in Wireless Sensor Networks[C]. IEEE International Conference on Mobile Adhoc and Sensor Systems (MASS), 2006: 586-591.
[54] Chen J R, Kher S, Somani A K. Energy Efficient Model for Data Gathering in Structured Multiclustered Wireless Sensor Networks[C]. Proceedings of the IEEE International Performance, Computing, and Communications Conference, IPCCC 2006 ,v 2006: 381-388, 2006.
[55] Perrig A, Szewczyk R, Wen V. SPINS: Security protocols for sensors networks [C]. The 7th Annual International Conference on Mobile Computing and Networks. Rome, Italy, 2001
[56] Karlof C, Sastry N, Wagner D. TinySec: A link layer security architecture for wireless sensor networks [C]. ACM Conference on Embedded Networked Sensor Systems (SENSYS’04), Maryland, USA, 2004
[57] Huang C F, Tseng Y C. The coverage problem in a wireless sensor network [J], Mobile Networks and Applications. August 2005, 10(4): 519– 528.
[58] Siqueira I G, Ruiz L B, Loureiro A A F et al. Coverage area management for wireless sensor networks [J]. International Journal of Network Management, Jan. 2007, 17(1): 17-31
[59] Liu J X, Gu N J, He S S. An Energy-Aware Coverage Based Node Scheduling Scheme for Wireless Sensor Networks [C]. Proceedings of the 9th International Conference for Young Computer Scientists, 2008: 462-468.
[60] Chen B, Jamieson K, Balakrishnan H. Span: An energy-efficient coordination algorithm for topology maintenance in ad hoc wireless networks[C]. Proceedings of the Seventh Annual ACM/IEEE International Conference on Mobile Computing and Networking (ACM MobiCom), Rome, Italy, 2001: 85–96.
[61] Wang D, Zhang Q, Liu J C. The self-protection problem in wireless sensor networks [J]. ACM Transactions on Sensor Networks, 2007, 3(4): 1-24.
[62] Liu H, Jia X, Wan P J et al. Maximizing lifetime of sensor surveillance systems [J]. IEEE/ACM Transactions on Networking, 2007, 15(2): 334–345.
[63] Qi X, Aura G. Maximizing sensor network lifetime: Analysis and design guidelines[C]. Proceedings– IEEE Military Communications Conference MILCOM, v2, MILCOM 2004 - 2004 IEEE Military Communications Conference. 2004: 1144-1150
[64] Bhardwaj M, Garnett T, Chandrakasan A P. Upper Bounds on the Lifetime of Sensor Networks[C]. IEEE International Conference on Communications, 2001, vol. 3: 785-790.
[65] Wang Q, Abu-Rgheff M A. Cross-Layer Signalling for Next-Generation Wireless Systems[C]. Proceedings of IEEE Wireless Communications and Networking Conference 2003 (IEEE WCNC 2003), New Orleans, USA, 2003, Vol. 2: 1084-1089.
[66] Dragos N. Communication Paradigms for Sensor Networks [J]. IEEE Communications Magazine, 43(3):116-122, March 2005.
[67] Yan T, He T, Stankovic J A. Differentiated Surveillance for Sensor Networks [C]. First ACM Conference on Embedded Networked Sensor Systems(SenSys 2003), 2003.
[68] Megerian S, Koushanfar F, Potkonjak M et al. Worst and best-case coverage in sensor networks [J]. IEEE Transactions on Mobile Computing, 4(1): 84–92, 2005.
[69] Patawari N, Hero III A O. Location Estimation Accuracy in Wireless Sensor Networks[C].Conference Record of the Thirty-Sixth Asilomar Conference on Signals, Systems and Computers, IEEE Press, Pacific Grove, California, USA, November 2002: 1523-1527.
[70] Peng R, Sichitiu M L. Angle of Arrival Localization for Wireless Sensor Networks[C]. Third Annual IEEE Communications Society Conference on Sensor and Ad Hoc Communications and Networks, IEEE Press, Reston, VA, USA, September 2006: 374-382.
[71] Zhang Q G, Huang J W, Wang J H et al. A Two-Phase Localization Algorithm for Wireless Sensor Network[C]. Proceedings of the 2008 IEEE International Conference on Information and Automation, ICIA 2008:59-64, 2008.
[72] Elson J, Girod L, Estrin D. Fine-Grained Network Time Synchronization using Reference Broadcasts[C]. Proceedings of the Fifth Symposium on Operating Systems Design and Implementation (OSDI 2002), Boston, MA.
[73] Garey M R, Johnson D S. Computers and Intractability: A Guide to the Theory of Np-Completeness [M]. W. H. Freeman: New York, 1979.
[74] Slijepcevic S, Potkonjak M. Power Efficient Organization of Wireless Sensor Networks[C]. IEEE International Conference on Pervasive Computing and Communications, 406-410, March 2005.
[75] Gupta H, Das S R, Gu Q. Connected sensor cover: Self-organization of sensor networks for efficient query execution[C]. In Proceedings of the ACM International Symposium on Mobile Ad Hoc Networking and Computing (MOBIHOC), 189–200, 2003.
[76] Meguerdichian S, Potkonjak M. Low Power 0/1 Coverage and Scheduling Techniques in Sensor Networks. UCLA Technical Report 030001, January 2003.
[77] Mhatre V, Rosenbert C, Kofman D et al. A minimum cost heterogeneous sensor network with a lifetime constraint [J]. IEEE Transactions on Mobile Computing, 2005, 4(1): 4–15.
[78] Miluzzo E, Lane N D, Campbell A T. Virtual sensing range[C]. Proceedings of the 4th international conference on Embedded networked sensor systems (SenSys '06), ACM Press, Boulder, Colorado, USA, October 2006, 397-398.
[79]李石坚,徐从富,吴朝晖等。面向目标跟踪的传感器网络布局优化及保护策略[J]。电子学报,2006,34(1):71-76。
[80] Rappaport T. Wireless Communications: Principles & Practice [M]. Englewood Cliffs, NJ: Prentice-Hall, 1996.
[81] Lim J C, Wong K D. Exploring Possibilities for RSS-Adaptive Power Control in MICA2-based Wireless Sensor Networks[C]. Proceedings of the 9th International Conference on Control, Automation, Robotics and Vision (ICARCV '06), IEEE Press, Singapore, December 2006, 1-6.
[82] Kershner R. The Number of Circles Covering a Set [J]. American Journal of Mathematics, 1939, 665–671.