基于模拟进化计算的高密度WSN网络分簇覆盖控制研究
|
摘要
无线传感器网络是集成了传感器技术、微电子技术、网络通信技术而形成的全新的信息获取和处理技术,是多学科交叉的前沿研究课题,在军事、工业、医疗、交通和民用等诸多方面潜在着巨大应用价值。虽然近年来国内外取得了一些研究成果,但仍然有很多的问题需要解决。
本文对高密度传感器网络分簇覆盖问题进行了深入研究,包括对网络分簇规模、目标覆盖率、簇状网能耗、算法性能的优化。在对三跳簇状网进行分析的基础上,根据其特点建立网络、数学、能量模型,并在此基础上讨论几个主要网络参数与网络能耗之间的关系,并均衡、优化这些参数。以最小化网络能耗为目标,对簇状网逻辑拓扑的优化是一个NP-难问题。本文以模拟进化计算算法的基本思想为基础,改进了简单遗传算法,应用并行免疫遗传算法和自适应遗传算法对网络分簇问题进行求解,从而提高算法的运算效率。仿真结果表明,本文提出的并行免疫遗传算法和自适应遗传算法较简单遗传算法和粒子群算法都有更大的优势,能够得到更优的网络分簇方案及簇头位置。
针对已有分簇算法中收敛速度过慢、极易陷入局部最优解的缺陷,本文提出了并行免疫遗传算法和自适应遗传算法来解决网络分簇的难题。并行免疫遗传算法通过引入并行计算与人体免疫的机理,避免了传统的遗传算法具有收敛速度慢,容易出现未成熟收敛的状况。自适应遗传算法通过自主调节交叉、变异概率,实现对简单遗传算法的改进。仿真结果表明,并行免疫遗传算法相比简单遗传算法能够更快的搜索到全局最优解,自适应遗传算法相比粒子群算法,能够加快算法收敛速度。两种改进的模拟进化计算均能使高密度传感网的网络分簇覆盖控制问题得到更好地解决。
本文针对高密度无线传感器网络提出的两种改进的遗传算法-并行免疫遗传算法和自适应遗传算法,利用图论的知识建立能量模型,构造了适应度函数,用matlab进行仿真,分析了节点通信半径R、簇头数p对网络能耗的影响关系,继而分别应用并行免疫遗传算法与自适应遗传算法对无线传感网分簇数及簇头节点的确定进行了优化,从而得出最佳分簇拓扑结构。仿真结果表明,感知区域较大的高密度无线传感网络,节点数量较多,并行免疫遗传算法能够并行处理多个子种群,进而较快速得到最优收敛结果,使得网络能耗达到最低；而感知区域较小的高密度无线传感网节点数量相对较少,采用自适应遗传算法即可很快得到收敛结果,既比简单遗传算法得到的优化结果单论网络能耗低,又比并行免疫遗传算法开销小。因此,在面对两种不同的高密度无线传感网时,本文提出的两种分簇算法均能达到快速收敛、单轮能耗最低、避免局部最优解的设计目标。
The wireless sensor network is the new information acquisition and processing technology which integrated sensor technology, micro-electronic technology and network communication technology. Now, it is the multidisciplinary and cutting-edge research topics and has potential enormous value in many aspects, such as military, industry, medical, transportation and civil.
In this paper, the high-density sensor network clustering coverage has been studied deeply, including optimization of network clustering scale, target coverage rate, clustered network energy consumption and performance of the algorithm.
Sensor node energy is non-renewable, so how to improve performance to maximize the lifetime is the first problem of wireless sensor network. So far, it is widely used cluster-based network to improve the operating efficiency. Triple jump clustered network is analyzed, and the model of network, mathematics and energy are been built based on its character. The relationship between Several key network parameters and network energy consumption is been discussed on this basis, and balanced these parameters to minimize the network energy consumption.
To minimize the network energy consumption, the optimization of tufted network logical topology is an NP-hard problem. The paper improves simple genetic algorithm based on the idea of simulation evolution of computing algorithm. Application of parallel immune genetic algorithm and adaptive genetic algorithm to solve the network clustering problem to improve the operation efficiency of the algorithm. The simulation results show that the parallel immune genetic algorithm and adaptive genetic algorithm proposed in the paper are better than the simple genetic algorithm and particle swarm algorithm in the aspects of network clustering solution and cluster head position.
This paper presents a parallel immune genetic algorithm and adaptive genetic algorithm to solve the problem of the network clustering, such as the convergence rate is too slow and easily fall into local optimal solution of the defects in existing clustering algorithm. Parallel immune genetic algorithm by introducing parallel computing with the body's immune mechanism, to avoid the traditional genetic algorithm with slow convergence, prone to premature convergence condition. Adaptive genetic algorithm realizes simple genetic algorithm improvements through self-regulation cross and mutation probability. The simulation results show that the parallel immune genetic algorithm has a faster search the global optimal solution than the simple genetic algorithm, while compared to particle swarm algorithm,adaptive genetic algorithm can accelerate the convergence rate. The two improved analog evolutionary computation could effectively solve the network clustering coverage control problem of the high-density sensor network.
Parallel immune genetic algorithm and adaptive genetic algorithm use graph theory to establish the energy model and the fitness function. And then analysis the relationship of communication radius R, clusters and network energy consumption. Simulation results show that, parallel immune genetic algorithm is suitable for large sensors because of its parallel computing ability, and adaptive genetic algorithm is suitable for smaller number of sensors. Both of them can get fast convergence, the lowest energy consumption and avoid the local optimal solution.
本文对高密度传感器网络分簇覆盖问题进行了深入研究,包括对网络分簇规模、目标覆盖率、簇状网能耗、算法性能的优化。在对三跳簇状网进行分析的基础上,根据其特点建立网络、数学、能量模型,并在此基础上讨论几个主要网络参数与网络能耗之间的关系,并均衡、优化这些参数。以最小化网络能耗为目标,对簇状网逻辑拓扑的优化是一个NP-难问题。本文以模拟进化计算算法的基本思想为基础,改进了简单遗传算法,应用并行免疫遗传算法和自适应遗传算法对网络分簇问题进行求解,从而提高算法的运算效率。仿真结果表明,本文提出的并行免疫遗传算法和自适应遗传算法较简单遗传算法和粒子群算法都有更大的优势,能够得到更优的网络分簇方案及簇头位置。
针对已有分簇算法中收敛速度过慢、极易陷入局部最优解的缺陷,本文提出了并行免疫遗传算法和自适应遗传算法来解决网络分簇的难题。并行免疫遗传算法通过引入并行计算与人体免疫的机理,避免了传统的遗传算法具有收敛速度慢,容易出现未成熟收敛的状况。自适应遗传算法通过自主调节交叉、变异概率,实现对简单遗传算法的改进。仿真结果表明,并行免疫遗传算法相比简单遗传算法能够更快的搜索到全局最优解,自适应遗传算法相比粒子群算法,能够加快算法收敛速度。两种改进的模拟进化计算均能使高密度传感网的网络分簇覆盖控制问题得到更好地解决。
本文针对高密度无线传感器网络提出的两种改进的遗传算法-并行免疫遗传算法和自适应遗传算法,利用图论的知识建立能量模型,构造了适应度函数,用matlab进行仿真,分析了节点通信半径R、簇头数p对网络能耗的影响关系,继而分别应用并行免疫遗传算法与自适应遗传算法对无线传感网分簇数及簇头节点的确定进行了优化,从而得出最佳分簇拓扑结构。仿真结果表明,感知区域较大的高密度无线传感网络,节点数量较多,并行免疫遗传算法能够并行处理多个子种群,进而较快速得到最优收敛结果,使得网络能耗达到最低；而感知区域较小的高密度无线传感网节点数量相对较少,采用自适应遗传算法即可很快得到收敛结果,既比简单遗传算法得到的优化结果单论网络能耗低,又比并行免疫遗传算法开销小。因此,在面对两种不同的高密度无线传感网时,本文提出的两种分簇算法均能达到快速收敛、单轮能耗最低、避免局部最优解的设计目标。
The wireless sensor network is the new information acquisition and processing technology which integrated sensor technology, micro-electronic technology and network communication technology. Now, it is the multidisciplinary and cutting-edge research topics and has potential enormous value in many aspects, such as military, industry, medical, transportation and civil.
In this paper, the high-density sensor network clustering coverage has been studied deeply, including optimization of network clustering scale, target coverage rate, clustered network energy consumption and performance of the algorithm.
Sensor node energy is non-renewable, so how to improve performance to maximize the lifetime is the first problem of wireless sensor network. So far, it is widely used cluster-based network to improve the operating efficiency. Triple jump clustered network is analyzed, and the model of network, mathematics and energy are been built based on its character. The relationship between Several key network parameters and network energy consumption is been discussed on this basis, and balanced these parameters to minimize the network energy consumption.
To minimize the network energy consumption, the optimization of tufted network logical topology is an NP-hard problem. The paper improves simple genetic algorithm based on the idea of simulation evolution of computing algorithm. Application of parallel immune genetic algorithm and adaptive genetic algorithm to solve the network clustering problem to improve the operation efficiency of the algorithm. The simulation results show that the parallel immune genetic algorithm and adaptive genetic algorithm proposed in the paper are better than the simple genetic algorithm and particle swarm algorithm in the aspects of network clustering solution and cluster head position.
This paper presents a parallel immune genetic algorithm and adaptive genetic algorithm to solve the problem of the network clustering, such as the convergence rate is too slow and easily fall into local optimal solution of the defects in existing clustering algorithm. Parallel immune genetic algorithm by introducing parallel computing with the body's immune mechanism, to avoid the traditional genetic algorithm with slow convergence, prone to premature convergence condition. Adaptive genetic algorithm realizes simple genetic algorithm improvements through self-regulation cross and mutation probability. The simulation results show that the parallel immune genetic algorithm has a faster search the global optimal solution than the simple genetic algorithm, while compared to particle swarm algorithm,adaptive genetic algorithm can accelerate the convergence rate. The two improved analog evolutionary computation could effectively solve the network clustering coverage control problem of the high-density sensor network.
Parallel immune genetic algorithm and adaptive genetic algorithm use graph theory to establish the energy model and the fitness function. And then analysis the relationship of communication radius R, clusters and network energy consumption. Simulation results show that, parallel immune genetic algorithm is suitable for large sensors because of its parallel computing ability, and adaptive genetic algorithm is suitable for smaller number of sensors. Both of them can get fast convergence, the lowest energy consumption and avoid the local optimal solution.
引文
[1]王殊,周毓杰,胡富平等,无线传感器网络的理论及应用[M],北京航空航天大学出版社,2007.1-8.
[2]吴琼,范菁,张翠,郝俊锋,基于簇首轮替的高密度无线网状传感器网络中能耗均衡休眠调度方案,计算机科学,2011.38(10A)：394-398.
[3]Saukh, Olga, Sauter, Robert; Gauger, Matthias; Marron, Pedro Jose Source. On Boundary recognition without location information in wireless sensor networks, ACM Transactions on Sensor Networks 6:3 (2010) 67-86.
[4]吴明娟,黄河清,沈杰,王营冠,分簇式无线带状传感网负载均衡路由协议,华中科技大学学报,2010,38(9)：63-67.
[5]Merico Davide, Tracking with high-density, large-scale wireless sensor networks, Journal of Ambient Intelligence and Smart Environments 2:4 (2010) 441-442.
[6]Raja, P. Dept. of ECE, Pondicherry Eng. Coll., Pondicherry, India Dananjayan, P. Game theory based ETDMA for intra-cluster wireless sensor network, 2012: 272-276。
[7]Zhang Shu-Dong, Cao Yuan-Da, Sun Li-Min, Optimization of wireless senser network time synchronization in high density deployment environment, Transaction of Beijing Institute of Technology 2009.29 (4):328-331.
[8]Jugen Nie,Deshi Li,Yanyan Han,Shikun Xie. The optimized method of cluster-head deployment based on GA-WCA in Wireless Sensor Networks, Communication, Networking & Broadcasting; Computing & Processing (Hardware/Software),2010.12:449-452.
[9]Heinzelman Wj Chandrakasan A, Balakrishnan H. Energy-Efficient communication protocol for wireless microsensor networks. In:Proc. of the 33rd Annual Hawaii Int'1 Conf.on System Sciences. Maui:IEEE Computer Society,2000.3005-3014.
[10]Wendi B. Heinzelman, Anantha P. Chandrakasan, Hari Balakrishnan. An application specific protocol architecture for wireless microsensor networks[J], IEEE Transactions on WirelessCommunications,2002.1(4):660-670.
[11]周玉,景博,杨洲,一种基于遗传算法的无线传感器网络LEACH路由协议的改进算法,计算机研究与发展,2010.47：175-179.
[12]王桂凤,王勇,陶晓玲,基于蚁群的无线传感器网络分簇路由算法,计算机工程,2010.36(18)：73-75.
[13]李洪兵,余成波,闫俊辉,李彦林,基于改进粒子群聚类的无线传感器网络能量均衡分簇策略,2011.28(2)：657-660.
[14]Sunil Jardosh, Prabhat Ranjan. A Survey:Topology Control for Wireless Sensor Networks[C]. IEEE-International Conference on Signal processing, Communications and Networking.
[15]Heinzelman W.Chandrakasan A Balakrishnan. Energy Effieient Communication Protocol for Wireless Microsensor Networks. Los Alamitos,CA:IEEE Computer Society,2002:3005-3014.
[16]李雅卿,李腊无,WSN中LEACH路由协议的改进与仿真,计算机工程,2009.5(10)：104-106.
[17]Xuhui Chen,Peiqiang Yu.Research on Hierarchical Mobile Wireless Sensor Network Architecture with Mobile Sensor Nodes[C].3rd International Conference on Biomedical Engineering and Informatics. Yantai, Oct.16-18, 2010:2863-2867. Chennai,India,Jan.4-6,2008:422-427.
[18]Shangwei Duan,Xiaobu Yuan.Exploring Hierarchy Architecture for Wireless Sensor Networks Management[C].IFIP International Conference on Wireless and Optical Communications Networks.Bangalore,2006:6-11.
[19]孙利民,李建中,陈渝等,无线传感器网络,北京：清华大学出版社,2005.
[20]杨琴,孙李.基于最小跳数的无线传感器网络路由协议[J],计算机工程,2008.34(22)：129-131.
[21]Lee J J, Krishnamachari B, Kuo C J. Aging analysis in large-scale wireless sensor networks[J]. Ad Hoc Networks,2008,6(7):117-133.
[22]吴明娟,黄河清,沈杰,王营冠.分簇式无线带状传感网负载均衡路由协议,华中 科技大学学报,2010.38(9)：63-67.
[23]吴明娟,张宝贤,黄河清,王海林,刘海涛.基于点割集的无线带状传感网分布式寿命预测算法,电子与信息学报,2010.32(11)：2599-2605.
[24]Wendi B. Heinzelman, Anantha P. Chandrakasan, Hari Balakrishnan. An application specific protocol architecture for wireless microsensor networks[J]. IEEE Transactions on WirelessCommunications,2002.1 (4):660-670.
[25]Ossama Younis,Sonia Fahmy.Distributed clustering in ad-hoc sensor networks:A hybrid,energy-efficient approach[C].Twenty-third Annual Joint Conference of the IEEE Computer and Communications Societies.Hong kong,Mar.7-11,2004.
[26]Ying Wang,Mudi Xiong.Monte Carlo Simulation of LEACH Protocol for Wireless Sensor Networks[C].Proceedings of the Sixth International Conference on Parallel and Distributed Computing, Applications and Technologies. Dalian, Dec 5-8,2005:85-88.
[27]郑明,刘桂霞,周春光,王晗,郑小红,李艳文,基于并行免疫遗传算法基因表达数据的动态模糊聚类,吉林大学学报,2009.1：63-68.
[28]李广强,赵洪伦,靳慧,并行混合免疫遗传算法及其应用,计算机工程与应用,2005：31-33.
[29]洪俊,杨淑莹,任翠池,基于图像分割的伪并行免疫遗传算法聚类设计,天津理工大学学报,2006.22(5)：83-85.
[30]刘学增,周敏,改进的自适应遗传算法及其工程应用,同济大学学报,2009.37(3)：303-307.
[31]Gui Yang, Yujun Lu, Ren-wang Li, Jin Han. Adaptive genetic algorithms for the Job-Shop Scheduling Problems. Intelligent Control and Automation,2008. WCICA 2008.7th World Congress on,2008.4501-4505.
[32]W.B.Heinzelman,A.P.Chandrakasan and H.Balakrishnan.An application-specific protocol architecture for wireless microsensor networks. IEEE Trans. on Wireless Comm,2002.1(4):660-670.
[33]J.A.邦迪,U.S.R.默蒂,图论及其应用,科学出版社,1984.
[34]M.R.加里,D.S.约翰逊.计算机和难解性NP完全性理论导引,计算科学出版 社,1987.
[35]Christofides N,Viola P. The optimum location of multi-centres on a graph, Quarterly,1971.22(2):145-154.
[36]陈森发,朱玉全.网络多中心问题的一种算法及其应用,东南大学学报,1991.
[37]李广强,赵洪伦,靳慧.并行混合免疫遗传算法及其应用,计算机工程与应用,2005.31-33.
[38]王小平,曹立明.遗传算法理论应用与软件实现,西安交通大学出版社,2002.
[2]吴琼,范菁,张翠,郝俊锋,基于簇首轮替的高密度无线网状传感器网络中能耗均衡休眠调度方案,计算机科学,2011.38(10A)：394-398.
[3]Saukh, Olga, Sauter, Robert; Gauger, Matthias; Marron, Pedro Jose Source. On Boundary recognition without location information in wireless sensor networks, ACM Transactions on Sensor Networks 6:3 (2010) 67-86.
[4]吴明娟,黄河清,沈杰,王营冠,分簇式无线带状传感网负载均衡路由协议,华中科技大学学报,2010,38(9)：63-67.
[5]Merico Davide, Tracking with high-density, large-scale wireless sensor networks, Journal of Ambient Intelligence and Smart Environments 2:4 (2010) 441-442.
[6]Raja, P. Dept. of ECE, Pondicherry Eng. Coll., Pondicherry, India Dananjayan, P. Game theory based ETDMA for intra-cluster wireless sensor network, 2012: 272-276。
[7]Zhang Shu-Dong, Cao Yuan-Da, Sun Li-Min, Optimization of wireless senser network time synchronization in high density deployment environment, Transaction of Beijing Institute of Technology 2009.29 (4):328-331.
[8]Jugen Nie,Deshi Li,Yanyan Han,Shikun Xie. The optimized method of cluster-head deployment based on GA-WCA in Wireless Sensor Networks, Communication, Networking & Broadcasting; Computing & Processing (Hardware/Software),2010.12:449-452.
[9]Heinzelman Wj Chandrakasan A, Balakrishnan H. Energy-Efficient communication protocol for wireless microsensor networks. In:Proc. of the 33rd Annual Hawaii Int'1 Conf.on System Sciences. Maui:IEEE Computer Society,2000.3005-3014.
[10]Wendi B. Heinzelman, Anantha P. Chandrakasan, Hari Balakrishnan. An application specific protocol architecture for wireless microsensor networks[J], IEEE Transactions on WirelessCommunications,2002.1(4):660-670.
[11]周玉,景博,杨洲,一种基于遗传算法的无线传感器网络LEACH路由协议的改进算法,计算机研究与发展,2010.47：175-179.
[12]王桂凤,王勇,陶晓玲,基于蚁群的无线传感器网络分簇路由算法,计算机工程,2010.36(18)：73-75.
[13]李洪兵,余成波,闫俊辉,李彦林,基于改进粒子群聚类的无线传感器网络能量均衡分簇策略,2011.28(2)：657-660.
[14]Sunil Jardosh, Prabhat Ranjan. A Survey:Topology Control for Wireless Sensor Networks[C]. IEEE-International Conference on Signal processing, Communications and Networking.
[15]Heinzelman W.Chandrakasan A Balakrishnan. Energy Effieient Communication Protocol for Wireless Microsensor Networks. Los Alamitos,CA:IEEE Computer Society,2002:3005-3014.
[16]李雅卿,李腊无,WSN中LEACH路由协议的改进与仿真,计算机工程,2009.5(10)：104-106.
[17]Xuhui Chen,Peiqiang Yu.Research on Hierarchical Mobile Wireless Sensor Network Architecture with Mobile Sensor Nodes[C].3rd International Conference on Biomedical Engineering and Informatics. Yantai, Oct.16-18, 2010:2863-2867. Chennai,India,Jan.4-6,2008:422-427.
[18]Shangwei Duan,Xiaobu Yuan.Exploring Hierarchy Architecture for Wireless Sensor Networks Management[C].IFIP International Conference on Wireless and Optical Communications Networks.Bangalore,2006:6-11.
[19]孙利民,李建中,陈渝等,无线传感器网络,北京：清华大学出版社,2005.
[20]杨琴,孙李.基于最小跳数的无线传感器网络路由协议[J],计算机工程,2008.34(22)：129-131.
[21]Lee J J, Krishnamachari B, Kuo C J. Aging analysis in large-scale wireless sensor networks[J]. Ad Hoc Networks,2008,6(7):117-133.
[22]吴明娟,黄河清,沈杰,王营冠.分簇式无线带状传感网负载均衡路由协议,华中 科技大学学报,2010.38(9)：63-67.
[23]吴明娟,张宝贤,黄河清,王海林,刘海涛.基于点割集的无线带状传感网分布式寿命预测算法,电子与信息学报,2010.32(11)：2599-2605.
[24]Wendi B. Heinzelman, Anantha P. Chandrakasan, Hari Balakrishnan. An application specific protocol architecture for wireless microsensor networks[J]. IEEE Transactions on WirelessCommunications,2002.1 (4):660-670.
[25]Ossama Younis,Sonia Fahmy.Distributed clustering in ad-hoc sensor networks:A hybrid,energy-efficient approach[C].Twenty-third Annual Joint Conference of the IEEE Computer and Communications Societies.Hong kong,Mar.7-11,2004.
[26]Ying Wang,Mudi Xiong.Monte Carlo Simulation of LEACH Protocol for Wireless Sensor Networks[C].Proceedings of the Sixth International Conference on Parallel and Distributed Computing, Applications and Technologies. Dalian, Dec 5-8,2005:85-88.
[27]郑明,刘桂霞,周春光,王晗,郑小红,李艳文,基于并行免疫遗传算法基因表达数据的动态模糊聚类,吉林大学学报,2009.1：63-68.
[28]李广强,赵洪伦,靳慧,并行混合免疫遗传算法及其应用,计算机工程与应用,2005：31-33.
[29]洪俊,杨淑莹,任翠池,基于图像分割的伪并行免疫遗传算法聚类设计,天津理工大学学报,2006.22(5)：83-85.
[30]刘学增,周敏,改进的自适应遗传算法及其工程应用,同济大学学报,2009.37(3)：303-307.
[31]Gui Yang, Yujun Lu, Ren-wang Li, Jin Han. Adaptive genetic algorithms for the Job-Shop Scheduling Problems. Intelligent Control and Automation,2008. WCICA 2008.7th World Congress on,2008.4501-4505.
[32]W.B.Heinzelman,A.P.Chandrakasan and H.Balakrishnan.An application-specific protocol architecture for wireless microsensor networks. IEEE Trans. on Wireless Comm,2002.1(4):660-670.
[33]J.A.邦迪,U.S.R.默蒂,图论及其应用,科学出版社,1984.
[34]M.R.加里,D.S.约翰逊.计算机和难解性NP完全性理论导引,计算科学出版 社,1987.
[35]Christofides N,Viola P. The optimum location of multi-centres on a graph, Quarterly,1971.22(2):145-154.
[36]陈森发,朱玉全.网络多中心问题的一种算法及其应用,东南大学学报,1991.
[37]李广强,赵洪伦,靳慧.并行混合免疫遗传算法及其应用,计算机工程与应用,2005.31-33.
[38]王小平,曹立明.遗传算法理论应用与软件实现,西安交通大学出版社,2002.