基于自然计算的WSN路由技术研究
|
摘要
无线传感器网络具有节点尺寸小,能够感知、处理数据,低功耗、低花费等特点,利于在复杂环境下采集、处理大量数据,但其存在硬件资源和电池容量有限,网络拓扑结构复杂,不易更换电池的缺陷,为解决这一问题,目前提出了许多高能效的信息融合算法和网络通信协议,其中,自然计算是以自然界机理为设计基础的算法,适用于解决那些难以建立有效的形式化模型而无法处理的问题,在大规模复杂系统的优化设计、优化控制等领域具有广阔的应用前景。
本论文主要对无线传感器的网络模型进行建模,并应用自然计算的方法进行仿真优化设计,具体研究内容如下:
(1) WSN路由模型研究。首先介绍对WSN的基本体系结构和网络覆盖形式,然后阐述了WSN中具有代表性的路由协议,并研究了链状和簇状路由模型。对于这两种路由模型,从能量的角度进行了分析和建模,建立了能量优化公式,提出解决方案。
(2)自然计算(NC)技术研究。主要对群智能算法和云智能进行研究,对于蚁群算法和粒子群算法存在的不足进行相应改进。对于链状路由模型,提出了基于自适应蚁群算法(SA-ACO)算法的无线传感器网络能量的优化方法,它包括动态概率选择、优化信息素矩阵和遗传变异等过程;对于簇状路由模型,提出了基于云自适应粒子群算法(CAPSO)的无线传感器网络能量的优化方法,它主要包括网络分簇、网络能量模型建立、云PSO算法迭代优化等过程。
(3)基于自然计算的WSN仿真设计研究。基于SA-ACO算法的路由算法,以自适应的方法优化信息素参数,通过对链状路由模型的仿真,表明其降低了WSN节点的网络能耗,提高了网络节点的生存能力,并且引入一定得变异规则,从而提高了算法的搜索能力,防止了节点陷入局部最优解,通过与传统ACO算法比较,该算法网络能耗和节点死亡率较低。基于CAPSO算法的路由算法,结合了云智能模糊性和随机性相结合的特点,改变了基本PSO算法惯性权重固定取值的方法,将粒子根据不同的适应度情况采用不同的惯性权重,并应用云模型进行优化,结果表明CAPSO算法有效降低了网络能耗和网络延时。
Wireless sensor networks(WSN) can sense, process data and has low power, low cost, nodes of small size,which conducive to collecting and processing large amounts of data in the complex environment. But it has some shortcomings, such as limited hardware resources and battery capacity, complex network topology and difficult to replace the battery. To solve this problem, many of energy-efficient data fusion algorithm and network communication protocols have been proposed. Natural Computation(NC) is based on natural mechanism for solving those difficult to establish effective formal model and deal with it. In large-scale optimization of complex systems design, optimal control and other fields, it has broad application prospects.
This thesis focuses on WSN modeling, and applying the method of natural computation for simulation and optimization design.The specific contents are as follows:
(1)Research on WSN routing model. Firstly, the basic architecture of the WSN and the form of the network coverage are introduced.Secondly, representative WSN routing protocols is elaborated, and the chain and cluster routing model are studied. For the two routing model, from the point of view of energy analysis and modeling, energy optimization formula is established and solutions is proposed.
(2) Research on Natural Computing(NC).The swarm intelligence algorithm, and cloud intelligent algorithms are mainly studied and shortcomings of the ant colony algorithm and particle swarm algorithm are improved. For the chain Routing model, an optimal approach for WSN is proposed based on self-adaptive ant colony optimization (SA-ACO) energy optimization,which includes the dynamic probability selection, optimizing pheromone matrix and genetic variation of combining process;for the cluster Routing model, an optimal approach for WSN is proposed, based on the Cloud Adaptive Particle Swarm Optimization (CAPSO) algorithm, which includes network clustering, network modeling, iteration optimization with CAPSO algorithm, and so on.
(3) Research on WSN Model with Natural Computation. The routing algorithm based on SA-ACO optimizes pheromone parameters through adaptive approach. The simulation for chain routing model prove that WSN node energy consumption is reduced, the viability of network nodes is increased. And the introduction of a certain variation of the rules is to improve the search ability of the algorithm to prevent the node into a local optimal solution. Compared with the traditional ACO algorithms, the algorithm has a lower energy consumption and node mortality. The routing algorithm based on CAPSO combined with fuzziness and randomness of cloud intelligent algorithms, change the basic PSO algorithm which has a fixed value of inertia weight. According to the fitness of different particles, the algorithm uses different inertia weight, and is optimized by the cloud model. Results show that, CAPSO reduces energy consumption and network delay.
本论文主要对无线传感器的网络模型进行建模,并应用自然计算的方法进行仿真优化设计,具体研究内容如下:
(1) WSN路由模型研究。首先介绍对WSN的基本体系结构和网络覆盖形式,然后阐述了WSN中具有代表性的路由协议,并研究了链状和簇状路由模型。对于这两种路由模型,从能量的角度进行了分析和建模,建立了能量优化公式,提出解决方案。
(2)自然计算(NC)技术研究。主要对群智能算法和云智能进行研究,对于蚁群算法和粒子群算法存在的不足进行相应改进。对于链状路由模型,提出了基于自适应蚁群算法(SA-ACO)算法的无线传感器网络能量的优化方法,它包括动态概率选择、优化信息素矩阵和遗传变异等过程;对于簇状路由模型,提出了基于云自适应粒子群算法(CAPSO)的无线传感器网络能量的优化方法,它主要包括网络分簇、网络能量模型建立、云PSO算法迭代优化等过程。
(3)基于自然计算的WSN仿真设计研究。基于SA-ACO算法的路由算法,以自适应的方法优化信息素参数,通过对链状路由模型的仿真,表明其降低了WSN节点的网络能耗,提高了网络节点的生存能力,并且引入一定得变异规则,从而提高了算法的搜索能力,防止了节点陷入局部最优解,通过与传统ACO算法比较,该算法网络能耗和节点死亡率较低。基于CAPSO算法的路由算法,结合了云智能模糊性和随机性相结合的特点,改变了基本PSO算法惯性权重固定取值的方法,将粒子根据不同的适应度情况采用不同的惯性权重,并应用云模型进行优化,结果表明CAPSO算法有效降低了网络能耗和网络延时。
Wireless sensor networks(WSN) can sense, process data and has low power, low cost, nodes of small size,which conducive to collecting and processing large amounts of data in the complex environment. But it has some shortcomings, such as limited hardware resources and battery capacity, complex network topology and difficult to replace the battery. To solve this problem, many of energy-efficient data fusion algorithm and network communication protocols have been proposed. Natural Computation(NC) is based on natural mechanism for solving those difficult to establish effective formal model and deal with it. In large-scale optimization of complex systems design, optimal control and other fields, it has broad application prospects.
This thesis focuses on WSN modeling, and applying the method of natural computation for simulation and optimization design.The specific contents are as follows:
(1)Research on WSN routing model. Firstly, the basic architecture of the WSN and the form of the network coverage are introduced.Secondly, representative WSN routing protocols is elaborated, and the chain and cluster routing model are studied. For the two routing model, from the point of view of energy analysis and modeling, energy optimization formula is established and solutions is proposed.
(2) Research on Natural Computing(NC).The swarm intelligence algorithm, and cloud intelligent algorithms are mainly studied and shortcomings of the ant colony algorithm and particle swarm algorithm are improved. For the chain Routing model, an optimal approach for WSN is proposed based on self-adaptive ant colony optimization (SA-ACO) energy optimization,which includes the dynamic probability selection, optimizing pheromone matrix and genetic variation of combining process;for the cluster Routing model, an optimal approach for WSN is proposed, based on the Cloud Adaptive Particle Swarm Optimization (CAPSO) algorithm, which includes network clustering, network modeling, iteration optimization with CAPSO algorithm, and so on.
(3) Research on WSN Model with Natural Computation. The routing algorithm based on SA-ACO optimizes pheromone parameters through adaptive approach. The simulation for chain routing model prove that WSN node energy consumption is reduced, the viability of network nodes is increased. And the introduction of a certain variation of the rules is to improve the search ability of the algorithm to prevent the node into a local optimal solution. Compared with the traditional ACO algorithms, the algorithm has a lower energy consumption and node mortality. The routing algorithm based on CAPSO combined with fuzziness and randomness of cloud intelligent algorithms, change the basic PSO algorithm which has a fixed value of inertia weight. According to the fitness of different particles, the algorithm uses different inertia weight, and is optimized by the cloud model. Results show that, CAPSO reduces energy consumption and network delay.
引文
[1] BALLARD H D.Introduction to Natural Computation[M].Cambridge: The MIT Press,1997.
[2] Ian F.Akylldiz,et al.Wireless sensor networks:a survey[J].Computer Networks,2002,38(4): 393-422.
[3] Jason Lester Hill.System architecture for wireless sensor networks[D].USA:UC berkeley,2003.
[4]王雪.无线传感网络测量系统[M].北京:机械工业出版社,2007.
[5] Furuhashi T,Miyata Y,Nakaoka K,et al. A new approach to genetic based machine learning for efficient improvement of locaportions of chromosomes[A]. Emerging Technologies and Factor Automation ETFA,IEEE Symposium[C].1994. 458-465.
[6] Choi C,Lee J J.Chaotic local search algorithm[J].Artificial Life and Robotics,1998,2(1):41-47.
[7]高尚,杨静宇.群智能算法及其应用[M].北京:中国水利水电出版社,2006.
[8] Stützle T,Hoos H.MAX-MIN Ant System[J].Journal of Future General Computer System,2001,16(8):889-914.
[9] Shi Y, Eberhart R C.Empirical Study of Particle Swarm Optimizer[A].Proceedings of Congress on Evolutionary Computation[C],Washington DC,USA,1999,3:1945-1950.
[10]陈杨,王茹,林辉.Matlab6.0版本中神经网络工具箱训练算法的使用与比较[J].电脑与信息技术科技.2002,10(3):1-6.
[11]苏高利,邓芳萍.论基于MATLAB语言的BP神经网络的改进算法[J].科技通报.2003,19(2):130-135.
[12]朱中,杨兆升.实时交通流量人工神经网络预测模型[J].中国公路学报.1998,11(4):89-92.
[13] Barenco A,Deutsch D,Ekert A and Jozsa R.Conditional quantum dynamics and logic gates[J].Phys.Rev.Lett. 1995,74(20):4083-4086.
[14]朱筱蓉.量子遗传算法及其在组合优化问题中的应用[D].南京工业大学博士学位论文,2006-11
[15]张兰.量子粒子群算法及其应用[D].西北大学硕士学位论文,2010-6.
[16]陈岩.蚁群优化理论在无人机战术控制中的应用研究[D].国防科学技术大学博士学位论文.2007-4.
[17]涂亚平.基于车辆路径问题的蚁群算法参数的优化[J].计算机时代.2010,3:21-23.
[18]章春芳,陈崚,陈娟.用自适应的多种群蚁群算法求解频率分配问题[J].计算机应用.2005,25(7):1641-1644.
[19]高晓光,赵欢欢,任佳.基于蚁群优化的贝叶斯网络学习[J].系统工程与电子技术.2010,7:1509-1512.
[20]赵玲,刘三阳.基于几何结构的求解旅行商问题的蚁群算法[J].苏州科技学院学报.2005,22(3):34-39.
[21]崔莉,鞠海玲,苗勇等.无线传感器网络研究进展[J].计算机研究与发展,2005,42(1):263-174.
[22] Dietzel A,Berger R.Trends in hard disk drive techology[C].Proc. VDE World Microtechnol.Cong.,New York:IEEE Press,2000.
[23] Linden D.Handbook of Batteries.[M].New York:McGraw-Hill,1995.
[24] Rabaey J M, Ammer M J, Patel D, et al.PicoRadio supports ad hoc ultra-low power wireless networking[J].Computer.2000.
[25] G.Asad,et al. Wireless Integrated network sensors:low Power systems on a chip[C],IEEE ESSCIRC’98,1998:9-16.
[26] G.J.Pottie and W.J.Kaiser,wireless integrated network sensors[J],Communications of the ACM,2000,43(5):51-58.
[27] Benton H.Calhoun,et al.Design considerations for ultra-low energy wireless microsensor nodes[J],IEEE Transactions on Computers,2005,54(6):727-740.
[28] Akyildig I F.A Suvrey on Sensor Netwokrs[J].IEEE Communications Magazine,2002,8: 725-734.
[29] Meguerdichian S,Koushanfar F,Potkonjak M,et al.Coverage problems in wirelesss ad-hoc sensor networks[C].IEEE INFOCOM,New York:IEEE Press,2001,1380-1387.
[30] RaghunathanV,Schurgers C,Park S,et al.Energy-aware wireless microsensor networks[J].IEEE Signal Process.Mag,2001,19(3):40-50.
[31] Guangyang H,Xiaowei L.Energy-efficiency analysis of cluster-based routing protocol in wireless sensor network[C].IEEE Aerospace Conference, Beijing:Chinese Acad. of Sci Press,2006,8.
[32] Younis O, Fahmy S.Distributed clustering in ad-hoc sensor:a hybrid,energy-efficient approach[C].Proc.IEEE Transactions on Mobile Computing,2004.366-379.
[33] Bandyopadhyay S and Edward J Coyle,“An Energy Efficient Hierarchical Clustering Algorithm for Wireless Sensor Networks”[C],In:Fred Bauer,JimRoberts,NessShroff,eds.Proc.of Infocom2003.INFOCOM.New York:IEEE Press,2003,1713-1723.
[34] Kulik J,Heinzelman WR,Blakarishnan H.Negotiation-based Protocols for Disseminating Information in Wireless Sensor Networks[J].Wireless Networks,2004,8(8):169-185.
[35] Intanagonwiwat C, Govindan R,and Tstrin D.Directed Diffusion:a Scalable and Robust Communication Paradigm for Sensor Networks[C].In:Proceedings of ACM MobiCom'00,Qoston,MA,2000.56-67.
[36] Heinzelman W,Chandrakasan A,Balakrishnan H.Energy-Efficient Communication Protocol for Wireless Microsensor Nelworks[C].In:Proc.of Hawaii Conf.System Scienees,Jan.2000.
[37] Colomi A, Dorigo M, Maniezzo V. Distributed optimization by antcolonies[C] //In Proceedings of the First European Conference on Artificial Life. Elsevier Publishing,Paris,France,1991,134-142.
[38]龚纯,王正林.精通Matlab最优化计算[M].北京:电子工业出版社,2009.
[39] YaoJung Yang, Chuni Wu. An attribute-based ant colony system for adaptive learning[J]. Science Direct, 2009,2(36): 3034–3047.
[40]余建军,孙树栋,褚崴.自适应蚁群算法及其在多约束多目标柔性Job-Shop调度中的应用[J].数学的实践与认识,2007,37(17):42-52.
[41]李德毅,刘常昱.论正态云模型的普适性[J].中国工程科学, 2004, 6(8): 28-34.
[42] Zhu Yunfang,Dai Chaohua,Chen Weirong,et al.Adaptive probabilities of crossover and mutation ingenetic algorithm based on cloud generators[J].Journal of Computational Information Systems,2005,1(4):671-678.
[43]李士勇.工程模糊数学及应用[M].哈尔滨:哈尔滨工业大学出版社,2004,70-81.
[44]叶宁,王汝传.基于蚁群算法的无线传感器网络数据聚合路由算法[J].南京邮电大学学报,2008,28(2):63-68.
[2] Ian F.Akylldiz,et al.Wireless sensor networks:a survey[J].Computer Networks,2002,38(4): 393-422.
[3] Jason Lester Hill.System architecture for wireless sensor networks[D].USA:UC berkeley,2003.
[4]王雪.无线传感网络测量系统[M].北京:机械工业出版社,2007.
[5] Furuhashi T,Miyata Y,Nakaoka K,et al. A new approach to genetic based machine learning for efficient improvement of locaportions of chromosomes[A]. Emerging Technologies and Factor Automation ETFA,IEEE Symposium[C].1994. 458-465.
[6] Choi C,Lee J J.Chaotic local search algorithm[J].Artificial Life and Robotics,1998,2(1):41-47.
[7]高尚,杨静宇.群智能算法及其应用[M].北京:中国水利水电出版社,2006.
[8] Stützle T,Hoos H.MAX-MIN Ant System[J].Journal of Future General Computer System,2001,16(8):889-914.
[9] Shi Y, Eberhart R C.Empirical Study of Particle Swarm Optimizer[A].Proceedings of Congress on Evolutionary Computation[C],Washington DC,USA,1999,3:1945-1950.
[10]陈杨,王茹,林辉.Matlab6.0版本中神经网络工具箱训练算法的使用与比较[J].电脑与信息技术科技.2002,10(3):1-6.
[11]苏高利,邓芳萍.论基于MATLAB语言的BP神经网络的改进算法[J].科技通报.2003,19(2):130-135.
[12]朱中,杨兆升.实时交通流量人工神经网络预测模型[J].中国公路学报.1998,11(4):89-92.
[13] Barenco A,Deutsch D,Ekert A and Jozsa R.Conditional quantum dynamics and logic gates[J].Phys.Rev.Lett. 1995,74(20):4083-4086.
[14]朱筱蓉.量子遗传算法及其在组合优化问题中的应用[D].南京工业大学博士学位论文,2006-11
[15]张兰.量子粒子群算法及其应用[D].西北大学硕士学位论文,2010-6.
[16]陈岩.蚁群优化理论在无人机战术控制中的应用研究[D].国防科学技术大学博士学位论文.2007-4.
[17]涂亚平.基于车辆路径问题的蚁群算法参数的优化[J].计算机时代.2010,3:21-23.
[18]章春芳,陈崚,陈娟.用自适应的多种群蚁群算法求解频率分配问题[J].计算机应用.2005,25(7):1641-1644.
[19]高晓光,赵欢欢,任佳.基于蚁群优化的贝叶斯网络学习[J].系统工程与电子技术.2010,7:1509-1512.
[20]赵玲,刘三阳.基于几何结构的求解旅行商问题的蚁群算法[J].苏州科技学院学报.2005,22(3):34-39.
[21]崔莉,鞠海玲,苗勇等.无线传感器网络研究进展[J].计算机研究与发展,2005,42(1):263-174.
[22] Dietzel A,Berger R.Trends in hard disk drive techology[C].Proc. VDE World Microtechnol.Cong.,New York:IEEE Press,2000.
[23] Linden D.Handbook of Batteries.[M].New York:McGraw-Hill,1995.
[24] Rabaey J M, Ammer M J, Patel D, et al.PicoRadio supports ad hoc ultra-low power wireless networking[J].Computer.2000.
[25] G.Asad,et al. Wireless Integrated network sensors:low Power systems on a chip[C],IEEE ESSCIRC’98,1998:9-16.
[26] G.J.Pottie and W.J.Kaiser,wireless integrated network sensors[J],Communications of the ACM,2000,43(5):51-58.
[27] Benton H.Calhoun,et al.Design considerations for ultra-low energy wireless microsensor nodes[J],IEEE Transactions on Computers,2005,54(6):727-740.
[28] Akyildig I F.A Suvrey on Sensor Netwokrs[J].IEEE Communications Magazine,2002,8: 725-734.
[29] Meguerdichian S,Koushanfar F,Potkonjak M,et al.Coverage problems in wirelesss ad-hoc sensor networks[C].IEEE INFOCOM,New York:IEEE Press,2001,1380-1387.
[30] RaghunathanV,Schurgers C,Park S,et al.Energy-aware wireless microsensor networks[J].IEEE Signal Process.Mag,2001,19(3):40-50.
[31] Guangyang H,Xiaowei L.Energy-efficiency analysis of cluster-based routing protocol in wireless sensor network[C].IEEE Aerospace Conference, Beijing:Chinese Acad. of Sci Press,2006,8.
[32] Younis O, Fahmy S.Distributed clustering in ad-hoc sensor:a hybrid,energy-efficient approach[C].Proc.IEEE Transactions on Mobile Computing,2004.366-379.
[33] Bandyopadhyay S and Edward J Coyle,“An Energy Efficient Hierarchical Clustering Algorithm for Wireless Sensor Networks”[C],In:Fred Bauer,JimRoberts,NessShroff,eds.Proc.of Infocom2003.INFOCOM.New York:IEEE Press,2003,1713-1723.
[34] Kulik J,Heinzelman WR,Blakarishnan H.Negotiation-based Protocols for Disseminating Information in Wireless Sensor Networks[J].Wireless Networks,2004,8(8):169-185.
[35] Intanagonwiwat C, Govindan R,and Tstrin D.Directed Diffusion:a Scalable and Robust Communication Paradigm for Sensor Networks[C].In:Proceedings of ACM MobiCom'00,Qoston,MA,2000.56-67.
[36] Heinzelman W,Chandrakasan A,Balakrishnan H.Energy-Efficient Communication Protocol for Wireless Microsensor Nelworks[C].In:Proc.of Hawaii Conf.System Scienees,Jan.2000.
[37] Colomi A, Dorigo M, Maniezzo V. Distributed optimization by antcolonies[C] //In Proceedings of the First European Conference on Artificial Life. Elsevier Publishing,Paris,France,1991,134-142.
[38]龚纯,王正林.精通Matlab最优化计算[M].北京:电子工业出版社,2009.
[39] YaoJung Yang, Chuni Wu. An attribute-based ant colony system for adaptive learning[J]. Science Direct, 2009,2(36): 3034–3047.
[40]余建军,孙树栋,褚崴.自适应蚁群算法及其在多约束多目标柔性Job-Shop调度中的应用[J].数学的实践与认识,2007,37(17):42-52.
[41]李德毅,刘常昱.论正态云模型的普适性[J].中国工程科学, 2004, 6(8): 28-34.
[42] Zhu Yunfang,Dai Chaohua,Chen Weirong,et al.Adaptive probabilities of crossover and mutation ingenetic algorithm based on cloud generators[J].Journal of Computational Information Systems,2005,1(4):671-678.
[43]李士勇.工程模糊数学及应用[M].哈尔滨:哈尔滨工业大学出版社,2004,70-81.
[44]叶宁,王汝传.基于蚁群算法的无线传感器网络数据聚合路由算法[J].南京邮电大学学报,2008,28(2):63-68.