WSN低能耗数据收集遗传粒子群算法研究
|
摘要
针对设施农业无线传感器网络节点分布不均匀、能量约束严格的特点,为降低网络总能耗,提出一种改进的遗传粒子群算法,构建一棵树高受限且网络总能耗最小的数据收集树。首先,随机生成连通图网络,采用父节点表示法将生成树编码成粒子;然后,设计一种随机生成数据收集树算法,随机产生满足树高限制的生成树;最后,考虑节点能耗均衡,设计一种粒子单点突变算法,实现对节点能耗最优值的比较。通过粒子单点变异、交叉以及优化新粒子,提高了种群多样性,避免了算法过早陷入局部最优解,在满足时延要求的同时,降低了网络总能耗。实验表明,与有树高约束的DL-DCT算法相比,所提算法降低了7.34%的网络总能耗,延长了网络平均生存期。
Aiming at the problems in green house wireless sensor networks such as uneven nodes distribution,strict energy constraint,etc,an improved genetic particle swarm optimization algorithm was proposed to solve the problem of total energy consumption in data collection of wireless sensor networks.This algorithm uses the parent node representation method to encode the spanning tree into particles.An algorithm for generating random data collection tree was designed,which can satisfy the spanning tree of tree height.A single point mutation algorithm was designed,which makes the spanning tree satisfy the height limit of the tree.The particles get the next iteration by the single point mutation,the extreme value of the individual and the global extreme value time.Under the same number of hops,the simulation results show that the algorithm proposed in this paper reduces 7.34% of the total energy consumption compared with the DL-DCT and it prolongs the average lifetime of network.
Aiming at the problems in green house wireless sensor networks such as uneven nodes distribution,strict energy constraint,etc,an improved genetic particle swarm optimization algorithm was proposed to solve the problem of total energy consumption in data collection of wireless sensor networks.This algorithm uses the parent node representation method to encode the spanning tree into particles.An algorithm for generating random data collection tree was designed,which can satisfy the spanning tree of tree height.A single point mutation algorithm was designed,which makes the spanning tree satisfy the height limit of the tree.The particles get the next iteration by the single point mutation,the extreme value of the individual and the global extreme value time.Under the same number of hops,the simulation results show that the algorithm proposed in this paper reduces 7.34% of the total energy consumption compared with the DL-DCT and it prolongs the average lifetime of network.
引文
[1]ZHANG X W,DAI H P,XU L J,et al.Mobile Assisted data gathering strategies in WSNs[J].Journal of Software,2013,24(2):198-214.(in Chinese)张希伟,戴海鹏,徐力杰,等.无线传感器网络中移动协助的数据收集策略[J].软件学报,2013,24(2):198-214.
[2]FU B J,WANG J H,HE Y,et al.Green house manage-ment model of Internet of things based on mobile Agent[J].Journal of Computer Applications,2012,32(S2):264-266.(in Chinese)付宝君,王建华,贺裕,等.基于移动Agent技术的物联网温室大棚管理模型[J].计算机应用,2012,32(S2):264-266.
[3]IEEE Computer Society.IEEE 802.15.4Standard for Wireless Medium Access Control(MAC)and Physical Layer(PHY)[J].Specifications for Low-Rate Wireless Personal Area Networks(WPANs).2011.
[4]ZHU Y H,XU J,TIAN X Z,et al.Energy-efficient and low-delay Reliable Data Gathering Scheme Applying Simple Reed-Solomon Code for Wireless Sensor Network[J].Chinese Journal of Computers,2015,38(10):2106-2124.(in Chinese)朱艺华,徐骥,田贤忠,等.无线传感器网络应用简单Reed-Solomon编码的低能耗和低时延可靠数据收集方案[J].计算机学报,2015,38(10):2106-2124.
[5]LU X L,WANG Y Y.Data collection algorithm for mobile sink in delay-constrained network[J].Journal on Communications,2014,35(10):107-116.(in Chinese)卢先领,王莹莹.时延受限的移动sink数据收集算法[J].通信学报,2014,35(10):107-116.
[6]GAO X,YUAN M B,RAO D,et al.Research on the Application of the Low-power Sleeping Algorithm for Agricultural Wireless Sensor Network[J].Journal of Shandong Agricultural University,2015(1):101-105.(in Chinese)高霞,袁明波,饶頔,等.农用无线传感器网络低功耗休眠算法应用研究[J].山东农业大学学报(自然科学版),2015(1):101-105.
[7]PENG A P,GUO X S,CAI W,et al.Research on energy management of wireless sensor networks[J].Transducer and Microsystem Technology,2007,26(8):1-5.(in Chinese)彭爱平,郭晓松,蔡伟,等.无线传感器网络能量管理研究[J].传感器与微系统,2007,26(8):1-5.
[8]PENG C,GUO J,PEI L X,et al.Energy-efficiency Strategies in Wireless Sensor Networks[J].Control Engineering of China,2010(3):372-375.(in Chinese)彭晨,郭静,裴灵犀,等.无线传感器网络中的节能策略[J].控制工程,2010,17(3):372-375.
[9]LIANG J B,WANG J X,CHEN J E.A delay-constrained and maximum lifetime data gathering algorithm for wireless sensor networks[C]∥Proc.of 5th International Conference on Mobile Ad-hoc and Sensor Networks(MSN2009).2009:148-155.
[10]TAN H O,KORPEOGLU I.Power efficient data gathering and aggregation in wireless sensor networks[C]∥ACM SIGMOD Record.New York:ACM NY,2003:66-71.
[11]LIANG W F,LIU Y Z.Online data gathering for maximizing network lifetime in sensor networks[J].IEEE Transaction on Mobile Computing,2007,6(1):2-11.
[12]KWON S,KIM J,KIM C.An efficient tree structure for delay sensitive data gathering in wireless sensor networks[C]∥The IFFF 22nd International Conference on Advanced Information Networking and Applications.Washington,DC,USA:IEEE Computer Society,2008:738-743.
[13]WU Y,SONIA F,NESS S.On the construction of a maximum lifetime data gathering tree in sensor networks:NP-completeness and approximation algorithm[C]∥Proc The IEEE 27th Conference on Computer Communications(INFOCOM2008).Washington,DC,USA:IEEE Computer Society,2008:356-360.
[14]XU H,HUANG L,LIU W.Topology control for delay constraint data collection in wireless sensor networks[J].Computer Communications,2009,32(17):1820-1828.
[15]ZHANG S,LI F R,LIN Z H,et al.Delay constraint energy balance data collection tree in wireless sensor network[J].Computer Engineering and Applications,2011,47(9):12-15.(in Chinese)张帅,李凤荣,林振华,等.时延受限能耗均衡的无线传感网数据采集树[J].计算机工程与应用,2011,47(9):12-15.
[16]GUO W Z,CHEN G L.An Efficient Discrete Particle Swarm Optimization Algorithm for Multi-Criteria Minimum Spanning Tree[J].Pattern Recognition and Artificial Intelligence,2009,22(4):597-604.(in Chinese)郭文忠,陈国龙.一种求解多目标最小生成树问题的有效离散粒子群优化算法[J].模式识别与人工智能,2009,22(4):597-604.
[17]SHEN Y Y,LI Y J,ZHU Y H.Maximizing the Lifetime of Unreliable Sensor Networks with Delay Constraint via Genetic Algorithm[C]∥Advances in Wireless Sensor Networks Communications in Computer and Information Science.2013:381-392.
[18]THOMAS C,CHOMAS L,RONALD R,et al.Introduction to Algorithmsl[M].Cambridge:MIT Press,2001:25-28.
[19]LING J B,WANG J X,CHEN J E.On the Construction of a Delay-Constrained Maximum Lifetime Tree in Wireless Sensor Networks[J].Acta Electronica Sinica,2010,38(2):345-351.(in Chinese)梁俊斌,王建新,陈建二.在传感器网络中构造延迟限定的最大化生命周期树[J].电子学报,2010,38(2):345-351.
[2]FU B J,WANG J H,HE Y,et al.Green house manage-ment model of Internet of things based on mobile Agent[J].Journal of Computer Applications,2012,32(S2):264-266.(in Chinese)付宝君,王建华,贺裕,等.基于移动Agent技术的物联网温室大棚管理模型[J].计算机应用,2012,32(S2):264-266.
[3]IEEE Computer Society.IEEE 802.15.4Standard for Wireless Medium Access Control(MAC)and Physical Layer(PHY)[J].Specifications for Low-Rate Wireless Personal Area Networks(WPANs).2011.
[4]ZHU Y H,XU J,TIAN X Z,et al.Energy-efficient and low-delay Reliable Data Gathering Scheme Applying Simple Reed-Solomon Code for Wireless Sensor Network[J].Chinese Journal of Computers,2015,38(10):2106-2124.(in Chinese)朱艺华,徐骥,田贤忠,等.无线传感器网络应用简单Reed-Solomon编码的低能耗和低时延可靠数据收集方案[J].计算机学报,2015,38(10):2106-2124.
[5]LU X L,WANG Y Y.Data collection algorithm for mobile sink in delay-constrained network[J].Journal on Communications,2014,35(10):107-116.(in Chinese)卢先领,王莹莹.时延受限的移动sink数据收集算法[J].通信学报,2014,35(10):107-116.
[6]GAO X,YUAN M B,RAO D,et al.Research on the Application of the Low-power Sleeping Algorithm for Agricultural Wireless Sensor Network[J].Journal of Shandong Agricultural University,2015(1):101-105.(in Chinese)高霞,袁明波,饶頔,等.农用无线传感器网络低功耗休眠算法应用研究[J].山东农业大学学报(自然科学版),2015(1):101-105.
[7]PENG A P,GUO X S,CAI W,et al.Research on energy management of wireless sensor networks[J].Transducer and Microsystem Technology,2007,26(8):1-5.(in Chinese)彭爱平,郭晓松,蔡伟,等.无线传感器网络能量管理研究[J].传感器与微系统,2007,26(8):1-5.
[8]PENG C,GUO J,PEI L X,et al.Energy-efficiency Strategies in Wireless Sensor Networks[J].Control Engineering of China,2010(3):372-375.(in Chinese)彭晨,郭静,裴灵犀,等.无线传感器网络中的节能策略[J].控制工程,2010,17(3):372-375.
[9]LIANG J B,WANG J X,CHEN J E.A delay-constrained and maximum lifetime data gathering algorithm for wireless sensor networks[C]∥Proc.of 5th International Conference on Mobile Ad-hoc and Sensor Networks(MSN2009).2009:148-155.
[10]TAN H O,KORPEOGLU I.Power efficient data gathering and aggregation in wireless sensor networks[C]∥ACM SIGMOD Record.New York:ACM NY,2003:66-71.
[11]LIANG W F,LIU Y Z.Online data gathering for maximizing network lifetime in sensor networks[J].IEEE Transaction on Mobile Computing,2007,6(1):2-11.
[12]KWON S,KIM J,KIM C.An efficient tree structure for delay sensitive data gathering in wireless sensor networks[C]∥The IFFF 22nd International Conference on Advanced Information Networking and Applications.Washington,DC,USA:IEEE Computer Society,2008:738-743.
[13]WU Y,SONIA F,NESS S.On the construction of a maximum lifetime data gathering tree in sensor networks:NP-completeness and approximation algorithm[C]∥Proc The IEEE 27th Conference on Computer Communications(INFOCOM2008).Washington,DC,USA:IEEE Computer Society,2008:356-360.
[14]XU H,HUANG L,LIU W.Topology control for delay constraint data collection in wireless sensor networks[J].Computer Communications,2009,32(17):1820-1828.
[15]ZHANG S,LI F R,LIN Z H,et al.Delay constraint energy balance data collection tree in wireless sensor network[J].Computer Engineering and Applications,2011,47(9):12-15.(in Chinese)张帅,李凤荣,林振华,等.时延受限能耗均衡的无线传感网数据采集树[J].计算机工程与应用,2011,47(9):12-15.
[16]GUO W Z,CHEN G L.An Efficient Discrete Particle Swarm Optimization Algorithm for Multi-Criteria Minimum Spanning Tree[J].Pattern Recognition and Artificial Intelligence,2009,22(4):597-604.(in Chinese)郭文忠,陈国龙.一种求解多目标最小生成树问题的有效离散粒子群优化算法[J].模式识别与人工智能,2009,22(4):597-604.
[17]SHEN Y Y,LI Y J,ZHU Y H.Maximizing the Lifetime of Unreliable Sensor Networks with Delay Constraint via Genetic Algorithm[C]∥Advances in Wireless Sensor Networks Communications in Computer and Information Science.2013:381-392.
[18]THOMAS C,CHOMAS L,RONALD R,et al.Introduction to Algorithmsl[M].Cambridge:MIT Press,2001:25-28.
[19]LING J B,WANG J X,CHEN J E.On the Construction of a Delay-Constrained Maximum Lifetime Tree in Wireless Sensor Networks[J].Acta Electronica Sinica,2010,38(2):345-351.(in Chinese)梁俊斌,王建新,陈建二.在传感器网络中构造延迟限定的最大化生命周期树[J].电子学报,2010,38(2):345-351.