无线传感器网络分簇路由算法研究与改进
|
摘要
无线传感器网络作为现阶段物联网发展的核心,高度融合了传感器技术、通信技术以及计算机技术。近年来,其在军事、环境监测、医疗卫生、智能交通等领域展现了良好的应用前景。在无线传感器网络中,节点的能量十分有限,如何高效地组织网络结构,最优化的利用节点的能量,成为各路由算法的关注重点。
本文对现有的分簇路由算法以及基于粒子群优化的分簇路由算法进行了详细的阐述,并分析了其研究现状及不足。在此基础上,针对传统的分簇路由算法中簇头选择的随机性,以及网络能量消耗不均衡等问题,本文首先根据传感器网络的簇内节点剩余能量和分布状况,给出了簇内能量密度的定义,在簇头选择中,综合考虑簇头节点剩余能量、信息传输损耗以及簇内能量密度等因素,并且利用二元粒子群优化算法对簇头选择过程进行优化。随后,本文对于自身的算法进行了改进,根据簇内节点的能量分布定义了基于节点剩余能量的簇内加权平均距离,并同时考虑了簇头的能量以及网络的能量损耗,重新定义的适应度函数。
最后,本文使用Matlab对提出的算法及改进算法进行仿真实验,并与LEACH、PSO-C算法进行对比分析。结果表明CCHSA-BPSO算法在本文提出的两种适应度函数下都能够非常高效地均衡网络的能量消耗、延长网络的生存周期。
Wireless sensor network, as the core part of "the internet of things" at present, highly integrate sensor technology, communications technology, and computer technology. In recent years, it shows a good application prospects in military, environmental monitoring, health care, intelligent transportation and other areas. In wireless sensor network, the node energy is limited. To organize the cluster structure and use the node energy effectively, which is the important part for routing algorithm.
In this paper, the existing clustering routing algorithms and the algorithms based on particle swarm optimization is described in detail, and its research status and weaknesses are analyzed. In the traditional clustering algorithm, the cluster head is selected randomly and the energy dissipation of the network is not even. Based on sensor network nodes within the cluster and the distribution of residual energy, we define the energy density for the cluster. In the cluster head selection, considering the residual energy of the cluster head nodes, information transmission loss, as well as the energy density for the cluster and other factors, the binary particle swarm optimization (BPSO) algorithm is applied to optimize the cluster head selection. Subsequently, the proposed algorithm is improved in the paper; Based on energy distribution, energy-weighted average distance is defined. The fitness function is redefined by using energy-weighted.
At last, we simulate the proposed algorithms by Matlab simulator. Results from the simulation indicate that the propose algorithm effectively balances the energy consumption of nodes in the network, and a higher network lifetime is reached compared with LEACH and PSO-C.
本文对现有的分簇路由算法以及基于粒子群优化的分簇路由算法进行了详细的阐述,并分析了其研究现状及不足。在此基础上,针对传统的分簇路由算法中簇头选择的随机性,以及网络能量消耗不均衡等问题,本文首先根据传感器网络的簇内节点剩余能量和分布状况,给出了簇内能量密度的定义,在簇头选择中,综合考虑簇头节点剩余能量、信息传输损耗以及簇内能量密度等因素,并且利用二元粒子群优化算法对簇头选择过程进行优化。随后,本文对于自身的算法进行了改进,根据簇内节点的能量分布定义了基于节点剩余能量的簇内加权平均距离,并同时考虑了簇头的能量以及网络的能量损耗,重新定义的适应度函数。
最后,本文使用Matlab对提出的算法及改进算法进行仿真实验,并与LEACH、PSO-C算法进行对比分析。结果表明CCHSA-BPSO算法在本文提出的两种适应度函数下都能够非常高效地均衡网络的能量消耗、延长网络的生存周期。
Wireless sensor network, as the core part of "the internet of things" at present, highly integrate sensor technology, communications technology, and computer technology. In recent years, it shows a good application prospects in military, environmental monitoring, health care, intelligent transportation and other areas. In wireless sensor network, the node energy is limited. To organize the cluster structure and use the node energy effectively, which is the important part for routing algorithm.
In this paper, the existing clustering routing algorithms and the algorithms based on particle swarm optimization is described in detail, and its research status and weaknesses are analyzed. In the traditional clustering algorithm, the cluster head is selected randomly and the energy dissipation of the network is not even. Based on sensor network nodes within the cluster and the distribution of residual energy, we define the energy density for the cluster. In the cluster head selection, considering the residual energy of the cluster head nodes, information transmission loss, as well as the energy density for the cluster and other factors, the binary particle swarm optimization (BPSO) algorithm is applied to optimize the cluster head selection. Subsequently, the proposed algorithm is improved in the paper; Based on energy distribution, energy-weighted average distance is defined. The fitness function is redefined by using energy-weighted.
At last, we simulate the proposed algorithms by Matlab simulator. Results from the simulation indicate that the propose algorithm effectively balances the energy consumption of nodes in the network, and a higher network lifetime is reached compared with LEACH and PSO-C.
引文
[1]彭明盛智慧地球：下一代的领导议程纽约：外交关系委员会演讲,2008.11.6
[2]http://blog.csdn.net/dengta_snowwhite/archive/2009/12/24/5061168.aspx
[3]孙利民、李建中、陈渝、朱红松,无线传感器网络,北京：清华大学出版社,2005.5
[4]Ten emerging technologies that will change the world. Technology Review. Feb.2003, Vol.106. No.1,PP.22-49
[5]N.Gross,21 ideas for the 21st century [J]. Business Week, Aug.30,1999,78-167.
[6]http://www.techweb.com.cn/data/2009-12-01/484955.shtml
[7]朱红松、孙利民,无线传感器网络技术发展现状,中兴通信技术,2009年第五期
[8]Center for Embedded Networked Sensing [EB/OL], http://research.cens.ucla.edu
[9]http://www.sensornet.cn/cn_Funding.html
[10]G.JPottie, WJ.Kaiser. Wireless Integrated Network Sensors Communications of the ACM 2000, 43(5)51-58
[11]Mobile Ad hoc Networks(MANET), available from http://www.ietf.cnri.va.us/ html.charter/manet-charter.html.
[12]NEMEROFF J, GARCIA L, HAMPLED, et al. Application of sensor network communication.//Military Communications Conference'01[C].336-341.
[13]MAINWARING A, POLASTRE J, SZEWCZYK R, et al. Wireless sensor networks for habitat monitoring[A].In the 2002 ACM International Workshop on Wireless Sensor Networks and Applications[C],2002.
[14]SZEWCZYK R, OSTERWEIL E, POLASTREJ, et al. Habitat monitoring with sensor networks. Communications of the ACM,2004,47(6):34-40.
[15]JAFARI R, ENCARNACAO A, ZAHOORY A, et al. Wireless sensor networks for health monitoring. Mobi Quitous 2005:479-481.
[16]Heimzelman W, Chandrakasan A, Balakrishnan H. Energy efficient Communication Protocol for Wireless Microsensor Networks[C]. Proceeding of the 33rd Annual Hawaii International Conference on System Sciences, Maui, HI,2000:1-10
[17]N. M. Abdul Latiff, C. C. Tsimenidis, B. S. Sharif, "Energy-aware clustering for wireless sensor networks using particle swarm optimization," in IEEE Int. Symp. PIMRC., Athens, Greece, Sept. 2007.
[18]N. M. Abdul Latiff C. C. Tsimenidis, B. S. Sharif, C. Ladha. Dynamic Clustering using Binary Multi-Objective Particle Swarm Optimization for Wireless Sensor Networks. IEEE International Symposium on Personal, Indoor and Mobile Radio Communications, PIMRC,2008,2008 IEEE 19th International Symposium on Personal, Indoor and Mobile Radio Communications, PIMRC 2008
[19]Intanagonwiwat C, Rgovindan, Estrin D Directed diffusion:A scalable and robust communication paradigm for sensor networks[C].The 6th Annual ACM/IEEE Int'l Conf on Mobile Computing and Networking, Boston, MA, August 2000.
[20]Kumar R,Wolenetz M,Agarwalla B,Shin J,Hutto P,Paul A.DFuse.A framework for distributed data-fusion[C].In:Proc 1st ACM Conf on Embedded Networked Sensor Systems.2003,114-125.
[21]Heinzelman W,Kulik J,Balakrishnan H.Adaptive protocols for information dissemination in wireless sensor networks [C].The 5th Annual ACM/IEEE Conf on Mobile Computing and Networking,Boston,MA,1999,174-185.
[22]Xu Y, Heidemann J, Estrin D. Geography-informed energy conservation for ad hoc routing, In: Proc 7th Annual Int'l Conf on Mobile Computing and Networking(MobiCOM), Rome, Italy. July 2001.70-84
[23]A Manjeshwar, DP Agarwal. TEEN:A Routing protocol for enhanced efficiency in wireless sensor networks. The 1st International Workshop on Parallel and Distributed Computing Issues in Wireless Networks and Mobile Computing,2001.2009-2015.
[24]Akkaya K, Younis M. A survey of routing protocols in wireless sensor networks. Ad Hoc Networks, 2005,3(3):325-349.
[25]Al-Karaki JN, Kamal AE. Routing techniques in wireless sensor networks:A survey. IEEE Wireless Communications,2004,11(6):6-28.
[26]沈波,张世永,钟亦平,无线传感器网络分簇路由协议软件学报,Vol.17,No.7,July 2006,pp.1588-1600
[27]郑相全等,无线自组织技术实用教程北京：清华大学出版社
[28]O. Younis,and S.Fahmy. HEED:A Hybrid, Energy-Efficient, Distributed Clustering Approach for Ad Hoc Sensor Networks [J].IEEE Transactions on Mobile Computing,2004,3(4):660-669.
[29]Chan H, Perrig A. ACE:An emergent algorithm for highly uniform cluster formation. In:Proc. of the 1st European Workshop on Wireless Sensor Networks. LNCS 2920, Berlin:Springer-Verlag, 2004.154-171.
[30]杨宁,田辉,张平等,基于博弈理论的无线传感器网络分布式节能路由算法,电子信息与学报,Vol.30 No.5 May 2008
[31]Bao Xi-rong, Zhang Shi, Xue Ding-yu, "Research and Simulation on Genetic Ant Colony Routing in Wireless Sensor Network", IEEE,2008.
[32]Kennedy J, Eberhart R C, Particle swarm optimization. In:Proccedings of the IEEE international Conference on Neural Networks, Piscataway, NJ, IEEE Press, vol.4,1942-1948,1995
[33]Kennedy, J.; Eberhart, R.C. A discrete binary version of the particle swarm algorithm. Systems, Man, and Cybernetics,1997.'Computational Cybernetics and Simulation'.,1997 IEEE International Conference on Volume 5,12-15 Oct.1997 Page(s):4104-4108 vol.5
[34]恩格尔伯里特(Andrice P.Engelbrecht)译者：谭营等,计算群体智能基础(Fundamentals of Computational Swarm Intelligence)清华大学出版社2009.10
[35]邹学玉,曹阳,刘徐迅,高洵等 基于离散粒子群的WSN分簇路由算法武汉大学学报Vol.54No.1 Feb.2008,099-103
[36]Heinzelman W, Chandrakasan A, Balakrishman H. Energy efficient communication protocol for wireless micro-sensor networks. In:Proceedings of the 33rd Hawaii International Conference on System Science. Maui:IEEE Computer Society,200.3005-3014.
[37]T.Rappaport, Wireless Communications:Principles & Practice [M]. Englewood Cliffs, NJ: Prentice-Hall,1996.
[38]Xinguo Wang,Xinming Zhang,Guoliang Chen,Shuang Tian.An adaptive and distributed clustering scheme for wireless sensor networks[C].IEEE 2007 International Conference on Convergence Information Technology. San Francisco:IEEE Computer Society Press,2007:522-527.
[39]Wang A, Heinzelman W, Chandrakasan A, Energy-Scalable Protocols for Battery-Operated Micro-sensor Networks[C]Proc.1999 IEEE Workshop Signal Processing Systems (SiPS'99),Oct. 1999:4832492.
[40]W.B. Heinzelman, A.P. Chandrakasan, and H. Balakrishnan, "An application-specific protocol architecture for wireless microsensor networks," IEEE Trans. Wireless Commun., vol.1, no.4, Oct. 2002, pp.660-70.
[2]http://blog.csdn.net/dengta_snowwhite/archive/2009/12/24/5061168.aspx
[3]孙利民、李建中、陈渝、朱红松,无线传感器网络,北京：清华大学出版社,2005.5
[4]Ten emerging technologies that will change the world. Technology Review. Feb.2003, Vol.106. No.1,PP.22-49
[5]N.Gross,21 ideas for the 21st century [J]. Business Week, Aug.30,1999,78-167.
[6]http://www.techweb.com.cn/data/2009-12-01/484955.shtml
[7]朱红松、孙利民,无线传感器网络技术发展现状,中兴通信技术,2009年第五期
[8]Center for Embedded Networked Sensing [EB/OL], http://research.cens.ucla.edu
[9]http://www.sensornet.cn/cn_Funding.html
[10]G.JPottie, WJ.Kaiser. Wireless Integrated Network Sensors Communications of the ACM 2000, 43(5)51-58
[11]Mobile Ad hoc Networks(MANET), available from http://www.ietf.cnri.va.us/ html.charter/manet-charter.html.
[12]NEMEROFF J, GARCIA L, HAMPLED, et al. Application of sensor network communication.//Military Communications Conference'01[C].336-341.
[13]MAINWARING A, POLASTRE J, SZEWCZYK R, et al. Wireless sensor networks for habitat monitoring[A].In the 2002 ACM International Workshop on Wireless Sensor Networks and Applications[C],2002.
[14]SZEWCZYK R, OSTERWEIL E, POLASTREJ, et al. Habitat monitoring with sensor networks. Communications of the ACM,2004,47(6):34-40.
[15]JAFARI R, ENCARNACAO A, ZAHOORY A, et al. Wireless sensor networks for health monitoring. Mobi Quitous 2005:479-481.
[16]Heimzelman W, Chandrakasan A, Balakrishnan H. Energy efficient Communication Protocol for Wireless Microsensor Networks[C]. Proceeding of the 33rd Annual Hawaii International Conference on System Sciences, Maui, HI,2000:1-10
[17]N. M. Abdul Latiff, C. C. Tsimenidis, B. S. Sharif, "Energy-aware clustering for wireless sensor networks using particle swarm optimization," in IEEE Int. Symp. PIMRC., Athens, Greece, Sept. 2007.
[18]N. M. Abdul Latiff C. C. Tsimenidis, B. S. Sharif, C. Ladha. Dynamic Clustering using Binary Multi-Objective Particle Swarm Optimization for Wireless Sensor Networks. IEEE International Symposium on Personal, Indoor and Mobile Radio Communications, PIMRC,2008,2008 IEEE 19th International Symposium on Personal, Indoor and Mobile Radio Communications, PIMRC 2008
[19]Intanagonwiwat C, Rgovindan, Estrin D Directed diffusion:A scalable and robust communication paradigm for sensor networks[C].The 6th Annual ACM/IEEE Int'l Conf on Mobile Computing and Networking, Boston, MA, August 2000.
[20]Kumar R,Wolenetz M,Agarwalla B,Shin J,Hutto P,Paul A.DFuse.A framework for distributed data-fusion[C].In:Proc 1st ACM Conf on Embedded Networked Sensor Systems.2003,114-125.
[21]Heinzelman W,Kulik J,Balakrishnan H.Adaptive protocols for information dissemination in wireless sensor networks [C].The 5th Annual ACM/IEEE Conf on Mobile Computing and Networking,Boston,MA,1999,174-185.
[22]Xu Y, Heidemann J, Estrin D. Geography-informed energy conservation for ad hoc routing, In: Proc 7th Annual Int'l Conf on Mobile Computing and Networking(MobiCOM), Rome, Italy. July 2001.70-84
[23]A Manjeshwar, DP Agarwal. TEEN:A Routing protocol for enhanced efficiency in wireless sensor networks. The 1st International Workshop on Parallel and Distributed Computing Issues in Wireless Networks and Mobile Computing,2001.2009-2015.
[24]Akkaya K, Younis M. A survey of routing protocols in wireless sensor networks. Ad Hoc Networks, 2005,3(3):325-349.
[25]Al-Karaki JN, Kamal AE. Routing techniques in wireless sensor networks:A survey. IEEE Wireless Communications,2004,11(6):6-28.
[26]沈波,张世永,钟亦平,无线传感器网络分簇路由协议软件学报,Vol.17,No.7,July 2006,pp.1588-1600
[27]郑相全等,无线自组织技术实用教程北京：清华大学出版社
[28]O. Younis,and S.Fahmy. HEED:A Hybrid, Energy-Efficient, Distributed Clustering Approach for Ad Hoc Sensor Networks [J].IEEE Transactions on Mobile Computing,2004,3(4):660-669.
[29]Chan H, Perrig A. ACE:An emergent algorithm for highly uniform cluster formation. In:Proc. of the 1st European Workshop on Wireless Sensor Networks. LNCS 2920, Berlin:Springer-Verlag, 2004.154-171.
[30]杨宁,田辉,张平等,基于博弈理论的无线传感器网络分布式节能路由算法,电子信息与学报,Vol.30 No.5 May 2008
[31]Bao Xi-rong, Zhang Shi, Xue Ding-yu, "Research and Simulation on Genetic Ant Colony Routing in Wireless Sensor Network", IEEE,2008.
[32]Kennedy J, Eberhart R C, Particle swarm optimization. In:Proccedings of the IEEE international Conference on Neural Networks, Piscataway, NJ, IEEE Press, vol.4,1942-1948,1995
[33]Kennedy, J.; Eberhart, R.C. A discrete binary version of the particle swarm algorithm. Systems, Man, and Cybernetics,1997.'Computational Cybernetics and Simulation'.,1997 IEEE International Conference on Volume 5,12-15 Oct.1997 Page(s):4104-4108 vol.5
[34]恩格尔伯里特(Andrice P.Engelbrecht)译者：谭营等,计算群体智能基础(Fundamentals of Computational Swarm Intelligence)清华大学出版社2009.10
[35]邹学玉,曹阳,刘徐迅,高洵等 基于离散粒子群的WSN分簇路由算法武汉大学学报Vol.54No.1 Feb.2008,099-103
[36]Heinzelman W, Chandrakasan A, Balakrishman H. Energy efficient communication protocol for wireless micro-sensor networks. In:Proceedings of the 33rd Hawaii International Conference on System Science. Maui:IEEE Computer Society,200.3005-3014.
[37]T.Rappaport, Wireless Communications:Principles & Practice [M]. Englewood Cliffs, NJ: Prentice-Hall,1996.
[38]Xinguo Wang,Xinming Zhang,Guoliang Chen,Shuang Tian.An adaptive and distributed clustering scheme for wireless sensor networks[C].IEEE 2007 International Conference on Convergence Information Technology. San Francisco:IEEE Computer Society Press,2007:522-527.
[39]Wang A, Heinzelman W, Chandrakasan A, Energy-Scalable Protocols for Battery-Operated Micro-sensor Networks[C]Proc.1999 IEEE Workshop Signal Processing Systems (SiPS'99),Oct. 1999:4832492.
[40]W.B. Heinzelman, A.P. Chandrakasan, and H. Balakrishnan, "An application-specific protocol architecture for wireless microsensor networks," IEEE Trans. Wireless Commun., vol.1, no.4, Oct. 2002, pp.660-70.