无线传感器网络中节点定位及覆盖控制算法的研究
摘要
自20世纪90年代发展起来的无线传感器网络(Wireless Sensor Networks, WSN)已被广泛应用在环境、医疗及军事等领域中。在许多相关理论和应用研究中,节点定位技术和覆盖控制技术,是WSN网络的重要支撑技术。
论文对定位算法QUAD进行了认真分析,针对其仅能在静态拓扑结构中实现节点定位的缺陷,给出了改进算法IQUAD。改进算法以节点更新比为判断标准,借助“重定位机制”分两种情况,在保证网络拓扑真实性的前提下,灵活的实现了动态拓扑中的网络节点定位。
论文分析了现有的覆盖控制算法LDCC,针对其仅考虑单一节点能耗的缺点,给出了改进算法ILDCC。改进算法以IQUAD通信协议为基础,综合考虑整个网络的能耗,增加了能量权重判断及合理化的冗余判断。
论文分别设计了基于Matlab的仿真实验,分析了具体实验步骤。实验结果表明,改进后的定位算法在动态拓扑结构情况下节点的定位误差降低了10%左右,有效地提高了定位的精度。改进后的覆盖控制算法比原算法提高了网络覆盖率,延长了网络的生存时间20%左右。
Science 1990s, this technology has been applied to environmentalology, medicine, military and other fields. In many related theory and application research, nodes localization and coverage control technology is the importance support technology of WSN.
This thesis makes an analysis on QUAD first, brings forward IQUAD which focuses on the nodes localization in dynamic net topology. IQUAD is based on the relocation mechanism, distinguishes the localization process as two parts by the update ratio of net nodes, keeps the flexibility and facticity of the result compared with real net topology.
As the significant way to saving nodes energy, coverage control improved coverage ratio and prolong survival time of the networks. This thesis analyses LDCC first, brings forward the improved algorithm-ILDCC, which is based on communication protocol of IQUAD, considers energy consumption of the whole networks instead of a single node, adds the judgment of energy weight and a rational redundancy estimate.
The simulation experiment is based on Matlab, thesis analyses the specific experimental procedure, and the results show that the location precision is advanced 10% and the networks survival time is prolonged 20%.
论文对定位算法QUAD进行了认真分析,针对其仅能在静态拓扑结构中实现节点定位的缺陷,给出了改进算法IQUAD。改进算法以节点更新比为判断标准,借助“重定位机制”分两种情况,在保证网络拓扑真实性的前提下,灵活的实现了动态拓扑中的网络节点定位。
论文分析了现有的覆盖控制算法LDCC,针对其仅考虑单一节点能耗的缺点,给出了改进算法ILDCC。改进算法以IQUAD通信协议为基础,综合考虑整个网络的能耗,增加了能量权重判断及合理化的冗余判断。
论文分别设计了基于Matlab的仿真实验,分析了具体实验步骤。实验结果表明,改进后的定位算法在动态拓扑结构情况下节点的定位误差降低了10%左右,有效地提高了定位的精度。改进后的覆盖控制算法比原算法提高了网络覆盖率,延长了网络的生存时间20%左右。
Science 1990s, this technology has been applied to environmentalology, medicine, military and other fields. In many related theory and application research, nodes localization and coverage control technology is the importance support technology of WSN.
This thesis makes an analysis on QUAD first, brings forward IQUAD which focuses on the nodes localization in dynamic net topology. IQUAD is based on the relocation mechanism, distinguishes the localization process as two parts by the update ratio of net nodes, keeps the flexibility and facticity of the result compared with real net topology.
As the significant way to saving nodes energy, coverage control improved coverage ratio and prolong survival time of the networks. This thesis analyses LDCC first, brings forward the improved algorithm-ILDCC, which is based on communication protocol of IQUAD, considers energy consumption of the whole networks instead of a single node, adds the judgment of energy weight and a rational redundancy estimate.
The simulation experiment is based on Matlab, thesis analyses the specific experimental procedure, and the results show that the location precision is advanced 10% and the networks survival time is prolonged 20%.
引文
[1]He T, Huang CD, Blum BM, et al. Range-Free localization schemes in large scale sensor networks[C]. Proc.of the 9th Annual Int Conf on Mobile Computing and Networking. San Diego:ACM Press,2003,81-95.
[2]Ye W, Heidemann J, Estrin D. An energy-efficient MAC protocol for wireless sensor networks[J]. In:Kermani P, ed. Proceedings of the 21st International Annual Joint Conference of the IEEE Computer and Communications Societies. Piscataway: IEEE Press,2002.91～100.
[3]Kemal Akkaya, Fatih Senel, Brian McLaughlan Clustering of wireless sensor and actor networks based on sensor distribution and connectivity [J]. Parallel Distrib. Comput,2009.69:573-587.
[4]Tarng, Jenn-Hwan, Chuang, Bing-Wen, a relay node deployment method for disconnected wireless sensor networks:applied in indoor environments[J]. Journal of Network & Computer Applications,2009,32(3):625-659.
[5]May Wong, Demet Aksoy. QUAD:Quadrant-based relative location estimates for representative topologies in wireless sensor networks[J]. Computer Networks, 2009,53(12):1967-1979.
[6]Koen Langendoen, Niels Reijers. Distributed localization in wireless sensor networks:a quantitative comparison[J]. Computer Networks,2003,43(3):499-518.
[7]A. Savvides, H. Park, M. Srivastava, The bits and flops of the N-hop multilateration primitive for node localization problems, in:First ACM International Workshop on Wireless Sensor Networks and Application (WSNA), Atlanta, GA,2002, pp. 112-121.
[8]M. Ratto, R. B. Shapiro, T. M. Truong, and W. G. Griswold, "The ActiveClass Project:Experiments in Encouraging Classroom Participation", Computer Support for Collaborative Learning 2003, Kluwer, pp.477-486, June 2003.
[9]Nobuo Kawaguchi, Cogma:A Middleware for Cooperative Smart Appliances for Ad hoc Environment, Proceedings of International Conference on Mobile Computing and Ubiquitous, Networking (ICMU2004), pp.146-151,2004.
[10]Sukhyun Yun, Jaehun Lee. A soft computing approach to localization in wireless sensor networks, Expert Systems with Applications[J],36 (2009):552-7561.
[11]Yun, S., Lee, J., Chung, W.,& Kim, E. (2008). Centroid localization method in wireless sensor networks using TSK fuzzy modeling. In International symposium on advanced intelligent systems, Sokcho, Korea, September (pp.971-974).
[12]Teemu Roos, Petri MyllymaE ki, A Statistical Modeling Approach to Location Estimation[J]. In:Kermani P, ed. Proceedings of the 21st International Annual Joint Conference of the IEEE Computer and Communications Societies. Piscataway:IEEE Press,2002.78-82.
[13]D. Li, K.D. Wong, Y.H. Hu, and A.M. Sayeed, "Detection, classification, and tracking of targets", IEEE Signal Processing Magazine, pp.17-29, Mar.2002.
[14]D. Niculescu, "Positioning in ad-hoc sensor networks", IEEE Networks, pp.24-29, Jul./Aug.2004.
[15]K. Martinez, J.K. Hart, and R. Ong, "Environmental sensor networks", Computer, pp.50-56, Aug.2004.
[16]X. Li, "RSS-based location estimation with unknown pathloss model for wireless sensor networks", submitted for publication, Jan.2005.
[17]M.A. Spirito, "On the accuracy of cellular mobile station location estimation", IEEE Trans. on Vehicular Technology, vol.50, no.3, pp.674-685, May 2001.
[18]M. Perillo, W. Heinzelman, DAPR:a protocol for wireless sensor networks utilizing an application-based routing cost, in:Proceedings of the IEEE Wireless Communications and Networking Conference (WCNC'04),2004.
[19]M. Qin, R. Zimmermann, An energy-efficient voting-based clustering algorithm for sensor networks, in:Proceedings of the Sixth International Conference on Software Engineering, Artificial Intelligence, Networking and Parallel/Distributed Computing and First ACIS International Workshop on Self-Assembling Wireless Networks (SNPD/SAWN),2005.
[20]M. Chatterjee, S.K. Das, D. Turgut, WCA:a weighted clustering algorithm for mobile ad hoc networks, Cluster Computing 5 (2) (2007) 193-204.
[21]W. Heinzelman, A. Chandrakasan, H. Balakrishnan, An applicationspecific protocol architecture for wireless microsensor networks, IEEE Transactions on Wireless Communications 1 (4) (2008).
[22]M.J. Handy, M. Haase, D. Timmermann, Low energy clustering hierarchy with deterministic cluster head selection, in:Proceedings of IEEE MWCN,2006.
[23]S. Bandyopadhyay, E.J. Coyle, An energy efficient hierarchical clustering algorithm for wireless sensor networks, in:Proceedings of the 22nd Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM), 2007.
[24]O. Younis, S. Fahmy, Distributed clustering in ad-hoc sensor networks:a hybrid, energy-efficient approach, IEEE Transactions on Mobile Computing 3 (4) (2009).
[25]T. Shu, M. Krunz, S. Vrudhula, Power balanced coverage-time optimization for clustered wireless sensor networks, in:Proceedings of MobiHoc'05,2005.
[26]S. Soro, W. Heinzelman, Prolonging the lifetime of wireless sensor networks via unequal clustering, in:Proceedings of the Fifth International Workshop on Algorithms for Wireless, Mobile, Ad Hoc and Sensor Networks (IEEE WMAN'05),2005.
[27]H. Chan, A. Perrig, ACE:an emergent algorithm for highly uniform cluster formation, in:Proceedings of EWSN,2004.
[28]V. Kawadia, P.R. Kumar, Power control and clustering in ad hoc networks, in: Proceedings of INFOCOM,2003.
[29]R. Virrankoski, A. Savvides, TASC:topology adaptive spatial clustering for sensor networks, in:Proceedings of the 2nd IEEE International Conference on Mobile Ad Hoc and Sensor Systems (MASS'05),2005.
[30]Y. Xu, J. Heidemann, D. Estrin, Geography-informed energy conservation for ad hoc routing, in:Proceedings of the Seventh Annual ACM/IEEE International Conference on Mobile Computing and Networking,2001.
[31]Y. Xu, J. Heidemann, D. Estrin, Energy conservation by adaptive clustering for ad-hoc networks, in:Proceedings of MobiHoc,2002.
[32]J. Deng, Y. Han, W. Heinzelman, P. Varshney, Scheduling sleeping nodes in high density cluster-based sensor networks, ACM/Kluwer MONET Special Issue on Energy Constraints and Lifetime Performance in Wireless Sensor Networks, vol. 10, No.6, December 2005, pp.825-835.
[33]J. Deng, Y.S. Han, W. Heinzelman, P. Varsney, Balanced-energy sleep scheduling scheme for high density cluster-based sensor networks, Elsevier's Computer Communications Journal (2005).
[34]K. Bae, H. Yoon, Autonomous clustering scheme for wireless sensor networks using coverage estimation self-pruning, IEICE Transaction on Communications E88-B (3) (2005).
[35]W. Choi, S.K. Das, A framework for energy-saving data gathering using two-phase clustering in wireless sensor networks, in:Proceedings of MobiQuitous Networking Conference,2004.
[36]M.T. Thai, F. Wang, D. Du, Coverage problems in wireless sensor networks-designs and analysis, International Journal of Sensor Networks, Special Issue on Coverage Problems in Sensor Networks,2005.
[37]S. Meguerdichian, F. Koushanfar, M. Potkonjak, M.B. Srivastava, Coverage problems in wireless ad-hoc sensor networks, in:Proceedings of IEEE Infocom, 2001.
[38]M. Cardei, J. Wu, Energy-efficient coverage problems in wireless adhoc sensor networks, Computer Communications Journal (Elsevier) 29 (4) (2006) 413-420.
[39]M. Cardei, D.Z. Du, Improving wireless sensor network lifetime through power aware organization, ACM Wireless Networks 11 (3) (2005). [23] F. Ye, G. Zhong, J. Cheng, S. Lu, L. Zhang, PEAS:a robust energy conserving protocol for long-lived sensor networks, in:Proceedings of IEEE International Conference on Distributed Computing Systems (ICDCS 2003),2003.
[40]D. Tian, N.D. Georganas, A coverage-preserving nodescheduling scheme for large wireless sensor networks, in:Processing of ACM Wireless Sensor Network and Application Workshop,2002.
[41]H. Zhang, J. Hou, Maintaining coverage and connectivity in large sensor networks, in:Proceedings of International Workshop on Theoretical and Algorithmic Aspects of Sensor, Ad hoc Wireless and Peer-to-Peer Networks,2004.
[42]S. Soro, W.Heinzelman, Camera selection in visual sensor networks, in: Proceedings of IEEE International Conference on Advanced Video and Signal-Based Surveillance,2007.
[43]Konstantinos Kalpakis, Koustuv Dasgupta, Parag Namjoshi, Efficient algorithms for maximum lifetime data gathering and aggregation in wireless sensor networks [J], Computer Networks,42 (2005) 697-716.
[44]亨塞尔曼利特菲尔德著,朱仁峰译.精通Matlab7[M].清华大学出版社.2006年5月1日.
[45]王福豹,史龙,任丰原.无线传感器网络中的自身定位系统和算法[J].软件学报,2005,16(5)：857-868.
[46]陈积明,林瑞仲,孙优贤.无线传感器网络通信体系研究[J].传感技术学报,2006,19(4)：1290-1295.
[47]孙利民,李建中,陈渝,朱红松.无线传感器网络[M].第一版北京,清华大学出版社,2005,5.
[48]唐勇,周明天,张欣.无线传感器网络路由协议研究进展[J].软件学报,2006,17(3)：410-421.
[49]任丰原,黄海宁,林闯,无线传感器网络[J].软件学报,2003,14(7)：1282-1291.
[50]王压明,顾超,钱莉,无线传感网之能量篇[J].计算机应用与软件,2007,89-90+107.
[51]刘燕,基于能量效率的无线传感器网络关键技术的研究[D],山东大学硕士学位论文,2008.
[2]Ye W, Heidemann J, Estrin D. An energy-efficient MAC protocol for wireless sensor networks[J]. In:Kermani P, ed. Proceedings of the 21st International Annual Joint Conference of the IEEE Computer and Communications Societies. Piscataway: IEEE Press,2002.91～100.
[3]Kemal Akkaya, Fatih Senel, Brian McLaughlan Clustering of wireless sensor and actor networks based on sensor distribution and connectivity [J]. Parallel Distrib. Comput,2009.69:573-587.
[4]Tarng, Jenn-Hwan, Chuang, Bing-Wen, a relay node deployment method for disconnected wireless sensor networks:applied in indoor environments[J]. Journal of Network & Computer Applications,2009,32(3):625-659.
[5]May Wong, Demet Aksoy. QUAD:Quadrant-based relative location estimates for representative topologies in wireless sensor networks[J]. Computer Networks, 2009,53(12):1967-1979.
[6]Koen Langendoen, Niels Reijers. Distributed localization in wireless sensor networks:a quantitative comparison[J]. Computer Networks,2003,43(3):499-518.
[7]A. Savvides, H. Park, M. Srivastava, The bits and flops of the N-hop multilateration primitive for node localization problems, in:First ACM International Workshop on Wireless Sensor Networks and Application (WSNA), Atlanta, GA,2002, pp. 112-121.
[8]M. Ratto, R. B. Shapiro, T. M. Truong, and W. G. Griswold, "The ActiveClass Project:Experiments in Encouraging Classroom Participation", Computer Support for Collaborative Learning 2003, Kluwer, pp.477-486, June 2003.
[9]Nobuo Kawaguchi, Cogma:A Middleware for Cooperative Smart Appliances for Ad hoc Environment, Proceedings of International Conference on Mobile Computing and Ubiquitous, Networking (ICMU2004), pp.146-151,2004.
[10]Sukhyun Yun, Jaehun Lee. A soft computing approach to localization in wireless sensor networks, Expert Systems with Applications[J],36 (2009):552-7561.
[11]Yun, S., Lee, J., Chung, W.,& Kim, E. (2008). Centroid localization method in wireless sensor networks using TSK fuzzy modeling. In International symposium on advanced intelligent systems, Sokcho, Korea, September (pp.971-974).
[12]Teemu Roos, Petri MyllymaE ki, A Statistical Modeling Approach to Location Estimation[J]. In:Kermani P, ed. Proceedings of the 21st International Annual Joint Conference of the IEEE Computer and Communications Societies. Piscataway:IEEE Press,2002.78-82.
[13]D. Li, K.D. Wong, Y.H. Hu, and A.M. Sayeed, "Detection, classification, and tracking of targets", IEEE Signal Processing Magazine, pp.17-29, Mar.2002.
[14]D. Niculescu, "Positioning in ad-hoc sensor networks", IEEE Networks, pp.24-29, Jul./Aug.2004.
[15]K. Martinez, J.K. Hart, and R. Ong, "Environmental sensor networks", Computer, pp.50-56, Aug.2004.
[16]X. Li, "RSS-based location estimation with unknown pathloss model for wireless sensor networks", submitted for publication, Jan.2005.
[17]M.A. Spirito, "On the accuracy of cellular mobile station location estimation", IEEE Trans. on Vehicular Technology, vol.50, no.3, pp.674-685, May 2001.
[18]M. Perillo, W. Heinzelman, DAPR:a protocol for wireless sensor networks utilizing an application-based routing cost, in:Proceedings of the IEEE Wireless Communications and Networking Conference (WCNC'04),2004.
[19]M. Qin, R. Zimmermann, An energy-efficient voting-based clustering algorithm for sensor networks, in:Proceedings of the Sixth International Conference on Software Engineering, Artificial Intelligence, Networking and Parallel/Distributed Computing and First ACIS International Workshop on Self-Assembling Wireless Networks (SNPD/SAWN),2005.
[20]M. Chatterjee, S.K. Das, D. Turgut, WCA:a weighted clustering algorithm for mobile ad hoc networks, Cluster Computing 5 (2) (2007) 193-204.
[21]W. Heinzelman, A. Chandrakasan, H. Balakrishnan, An applicationspecific protocol architecture for wireless microsensor networks, IEEE Transactions on Wireless Communications 1 (4) (2008).
[22]M.J. Handy, M. Haase, D. Timmermann, Low energy clustering hierarchy with deterministic cluster head selection, in:Proceedings of IEEE MWCN,2006.
[23]S. Bandyopadhyay, E.J. Coyle, An energy efficient hierarchical clustering algorithm for wireless sensor networks, in:Proceedings of the 22nd Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM), 2007.
[24]O. Younis, S. Fahmy, Distributed clustering in ad-hoc sensor networks:a hybrid, energy-efficient approach, IEEE Transactions on Mobile Computing 3 (4) (2009).
[25]T. Shu, M. Krunz, S. Vrudhula, Power balanced coverage-time optimization for clustered wireless sensor networks, in:Proceedings of MobiHoc'05,2005.
[26]S. Soro, W. Heinzelman, Prolonging the lifetime of wireless sensor networks via unequal clustering, in:Proceedings of the Fifth International Workshop on Algorithms for Wireless, Mobile, Ad Hoc and Sensor Networks (IEEE WMAN'05),2005.
[27]H. Chan, A. Perrig, ACE:an emergent algorithm for highly uniform cluster formation, in:Proceedings of EWSN,2004.
[28]V. Kawadia, P.R. Kumar, Power control and clustering in ad hoc networks, in: Proceedings of INFOCOM,2003.
[29]R. Virrankoski, A. Savvides, TASC:topology adaptive spatial clustering for sensor networks, in:Proceedings of the 2nd IEEE International Conference on Mobile Ad Hoc and Sensor Systems (MASS'05),2005.
[30]Y. Xu, J. Heidemann, D. Estrin, Geography-informed energy conservation for ad hoc routing, in:Proceedings of the Seventh Annual ACM/IEEE International Conference on Mobile Computing and Networking,2001.
[31]Y. Xu, J. Heidemann, D. Estrin, Energy conservation by adaptive clustering for ad-hoc networks, in:Proceedings of MobiHoc,2002.
[32]J. Deng, Y. Han, W. Heinzelman, P. Varshney, Scheduling sleeping nodes in high density cluster-based sensor networks, ACM/Kluwer MONET Special Issue on Energy Constraints and Lifetime Performance in Wireless Sensor Networks, vol. 10, No.6, December 2005, pp.825-835.
[33]J. Deng, Y.S. Han, W. Heinzelman, P. Varsney, Balanced-energy sleep scheduling scheme for high density cluster-based sensor networks, Elsevier's Computer Communications Journal (2005).
[34]K. Bae, H. Yoon, Autonomous clustering scheme for wireless sensor networks using coverage estimation self-pruning, IEICE Transaction on Communications E88-B (3) (2005).
[35]W. Choi, S.K. Das, A framework for energy-saving data gathering using two-phase clustering in wireless sensor networks, in:Proceedings of MobiQuitous Networking Conference,2004.
[36]M.T. Thai, F. Wang, D. Du, Coverage problems in wireless sensor networks-designs and analysis, International Journal of Sensor Networks, Special Issue on Coverage Problems in Sensor Networks,2005.
[37]S. Meguerdichian, F. Koushanfar, M. Potkonjak, M.B. Srivastava, Coverage problems in wireless ad-hoc sensor networks, in:Proceedings of IEEE Infocom, 2001.
[38]M. Cardei, J. Wu, Energy-efficient coverage problems in wireless adhoc sensor networks, Computer Communications Journal (Elsevier) 29 (4) (2006) 413-420.
[39]M. Cardei, D.Z. Du, Improving wireless sensor network lifetime through power aware organization, ACM Wireless Networks 11 (3) (2005). [23] F. Ye, G. Zhong, J. Cheng, S. Lu, L. Zhang, PEAS:a robust energy conserving protocol for long-lived sensor networks, in:Proceedings of IEEE International Conference on Distributed Computing Systems (ICDCS 2003),2003.
[40]D. Tian, N.D. Georganas, A coverage-preserving nodescheduling scheme for large wireless sensor networks, in:Processing of ACM Wireless Sensor Network and Application Workshop,2002.
[41]H. Zhang, J. Hou, Maintaining coverage and connectivity in large sensor networks, in:Proceedings of International Workshop on Theoretical and Algorithmic Aspects of Sensor, Ad hoc Wireless and Peer-to-Peer Networks,2004.
[42]S. Soro, W.Heinzelman, Camera selection in visual sensor networks, in: Proceedings of IEEE International Conference on Advanced Video and Signal-Based Surveillance,2007.
[43]Konstantinos Kalpakis, Koustuv Dasgupta, Parag Namjoshi, Efficient algorithms for maximum lifetime data gathering and aggregation in wireless sensor networks [J], Computer Networks,42 (2005) 697-716.
[44]亨塞尔曼利特菲尔德著,朱仁峰译.精通Matlab7[M].清华大学出版社.2006年5月1日.
[45]王福豹,史龙,任丰原.无线传感器网络中的自身定位系统和算法[J].软件学报,2005,16(5)：857-868.
[46]陈积明,林瑞仲,孙优贤.无线传感器网络通信体系研究[J].传感技术学报,2006,19(4)：1290-1295.
[47]孙利民,李建中,陈渝,朱红松.无线传感器网络[M].第一版北京,清华大学出版社,2005,5.
[48]唐勇,周明天,张欣.无线传感器网络路由协议研究进展[J].软件学报,2006,17(3)：410-421.
[49]任丰原,黄海宁,林闯,无线传感器网络[J].软件学报,2003,14(7)：1282-1291.
[50]王压明,顾超,钱莉,无线传感网之能量篇[J].计算机应用与软件,2007,89-90+107.
[51]刘燕,基于能量效率的无线传感器网络关键技术的研究[D],山东大学硕士学位论文,2008.