面向差异化覆盖的异构有向传感器节点调度算法

doi:10.11772/j.issn.1001-9081.2020050696

计算机应用 ›› 2020, Vol. 40 ›› Issue (12): 3563-3570.DOI: 10.11772/j.issn.1001-9081.2020050696

面向差异化覆盖的异构有向传感器节点调度算法

李明^1,2, 胡江平², 曹晓莉¹, 彭鹏³

1. 重庆工商大学计算机科学与信息工程学院, 重庆 400067;
2. 电子科技大学自动化工程学院, 成都 611731;
3. 重庆英卡电子有限公司, 重庆 400039

收稿日期:2020-05-25 修回日期:2020-08-17 发布日期:2020-08-26 出版日期:2020-12-10
通讯作者: 李明(1982-),男,山东泗水人,副教授,博士,主要研究方向:无线传感器网络。sshjlm@163.com
作者简介:胡江平(1977-),男,湖北黄梅人,教授,博士,主要研究方向:多智能体系统协调控制、传感器网络;曹晓莉(1970-),女,重庆人,教授,硕士,主要研究方向:物联网应用;彭鹏(1971-),男,重庆人,工程师,硕士,主要研究方向:物联网应用
基金资助:
重庆市社会科学规划项目（2017YBGL142）；重庆教委科学技术研究项目（KJQN201900839，KJ1600627）；重庆工商大学科研平台开放课题（KFJJ2019072，KFJJ2017048）；重庆市教育科学规划项目（2018-GX-023）；智能生态物联网创新创业团队项目（CQYC201903246）。

Heterogeneous directional sensor node scheduling algorithm for differentiated coverage

LI Ming^1,2, HU Jiangping², CAO Xiaoli¹, PENG Peng³

1. School of Computer Science and Information Engineering, Chongqing Technology and Business University, Chongqing 400067, China;
2. College of Automation Engineering, University of Electronic Science and Technology of China, Chengdu Sichuan 611731, China;
3. Chongqing Yingka Electronic Company Limited, Chongqing 400039, China

Received:2020-05-25 Revised:2020-08-17 Online:2020-08-26 Published:2020-12-10
Supported by:
This work is partially supported by the Chongqing Social Science Planning Project （2017YBGL142）， the Science and Technology Research Program of Chongqing Municipal Education Commission （KJQN201900839， KJ1600627）， the Opening Subject of Research Platform of Chongqing Technology and Business University （KFJJ2019072， KFJJ2017048）， the Chongqing Educational Science Planning Project （2018-GX-023）， the Program of Intelligent Ecological Internet of Things Innovation and Entrepreneurship Team （CQYC201903246）.

摘要/Abstract

摘要： 为延长异构有向传感器网络的寿命，提出一种基于改进珊瑚礁优化算法（ECRO）的面向不同监测目标有不同监测要求的节点调度算法。利用ECRO将传感器集合划分成符合覆盖要求的多个集合，通过集合间的调度达到延长网络寿命的目的。对珊瑚礁优化算法（CRO）的改进体现在四个方面：一是在珊瑚礁的雌雄同体繁殖过程中融入生物地理学优化算法中的迁移操作，保留原有种群的优秀解；二是在雌雄同体繁殖过程中采用一种带有混沌参数的差分变异因子，增强子代的优化能力；三是通过对最差个体执行随机反向学习，增强种群的多样性；四是通过CRO与模拟退火算法的结合，增强算法的局部搜索能力。对数值基准函数和节点调度进行了大量的仿真实验。在数值测试方面的结果表明，与遗传算法、模拟退火算法、差分进化算法及其改进算法相比，ECRO的优化能力更强；在传感器网络节点调度方面的结果表明，与贪婪算法、基于学习自动机的差分进化（LADE）算法和未改进的CRO相比，ECRO使网络寿命分别提高了53.8%、19.0%和26.6%，验证了所提算法的有效性。

关键词: 异构有向传感器网络, 覆盖调度算法, 珊瑚礁优化算法, 生物地理学优化算法, 差分变异因子

Abstract: In order to prolong the lifespan of heterogeneous directional sensor network, a node scheduling algorithm based on Enhanced Coral Reef Optimization algorithm (ECRO) and with different monitoring requirements for different monitoring targets was proposed. ECRO was utilized to divide the sensor set into multiple sets satisfying the coverage requirements, so that the network lifespan was able to be prolonged by the scheduling among sets. The improvement of Coral Reef Optimization algorithm (CRO) was reflected in four aspects. Firstly, the migration operation in biogeography-based optimization algorithm was introduced into the brooding of coral reef to preserve the excellent solutions of the original population. Secondly, the differential mutation operator with chaotic parameter was adopted in brooding to enhance the optimization ability of the offspring. Thirdly, a random reverse learning strategy were performed on the worst individual of population in order to improve the diversity of population. Forthly, by combining CRO and simulated annealing algorithm, the local searching capability of algorithm was increased. Extensive simulation experiments on both numerical benchmark functions and node scheduling were conducted. The results of numerical test show that, compared with genetic algorithm, simulated annealing algorithm, differential evolution algorithm and the improved differential evolution algorithm, ECRO has better optimization ability. The results of sensor network node scheduling show that, compared with greedy algorithm, the Learning Automata Differential Evolution (LADE) algorithm, the original CRO, ECRO has the network lifespan improved by 53.8%, 19.0% and 26.6% respectively, which demonstrates the effectiveness of the proposed algorithm.

Key words: heterogeneous directional sensor network, coverage scheduling algorithm, Coral Reef Optimization algorithm (CRO), biogeography-based optimization algorithm, differential mutation operator

中图分类号:

TP393

李明, 胡江平, 曹晓莉, 彭鹏. 面向差异化覆盖的异构有向传感器节点调度算法[J]. 计算机应用, 2020, 40(12): 3563-3570.

LI Ming, HU Jiangping, CAO Xiaoli, PENG Peng. Heterogeneous directional sensor node scheduling algorithm for differentiated coverage[J]. Journal of Computer Applications, 2020, 40(12): 3563-3570.

参考文献

[1] 彭力. 视觉物联网[M]. 北京:电子工业出版社, 2016:6-8. (PENG L. Visual Internet of Things[M]. Beijing:Publishing House of Electronics Industry,2016:6-8.)
[2] CURRY R M,SMITH J C. A survey of optimization algorithms for wireless sensornetwork lifetime maximization[J]. Computers and Industrial Engineering,2016,101:145-166.
[3] 温俊, 蒋杰, 窦文华. 公平的有向传感器网络方向优化和节点调度算法[J]. 软件学报, 2009, 20(3):644-659.(WEN J,JIANG J, DOU W H. Equitable direction optimizing and node scheduling for coverage in directional sensornetworks[J]. Journal of Software, 2009,20(3):644-659.)
[4] 程卫芳, 廖湘科, 沈昌祥. 有向传感器网络最大覆盖调度算法[J]. 软件学报, 2009, 20(4):975-984.(CHENG W F,LIAO X K, SHEN C X. Maximal coverage scheduling in wireless directional sensornetworks[J]. Journal of Software,2009,20(4):975-984.)
[5] 张聚伟, 王宇, 杨挺. 基于数据融合的有向传感器网络全覆盖部署[J]. 传感技术学报, 2017, 30(1):139-145.(ZHANG J W, WANG Y, YANG T. Full coverage deployment algorithm of directional sensornetwork based on data fusion[J]. Chinese Journal of Sensors and Actuators,2017,30(1):139-145.)
[6] SHARMIN S,NUR F N,RAZZAQUE M A,et al. Target coverageaware clustering for directional sensornetworks[C]//Proceedings of the 2017 IEEE International Symposium on Parallel and Distributed Processing with Applications/2017 IEEE International Conference on Ubiquitous Computing and Communications. Piscataway:IEEE,2017:116-120.
[7] WANG H,CHEN Y,DONG S. Research on efficient-efficient routing protocol for WSNs based on improved artificial bee colony algorithm[J]. IET Wireless Sensor Systems,2017,7(1):15-20.
[8] ARORA V K, SHARMA V, SACHDEVA M. A multiple pheromone ant colony optimization scheme for energy-efficient wireless sensornetworks[J]. Soft Computing,2020,24(1):543-553.
[9] NISHA U N, BASHA A M. Triangular fuzzy-based spectral clustering for energy-efficient routing in wireless sensornetwork[J]. The Journal of Supercomputing,2020,76(6):4302-4327.
[10] DONG S, SAREM M, ZHOU W. Distributed data gathering algorithm based on spanning tree[J]. IEEE Systems Journal, 2020(Early Access):1-8.
[11] LIEW S Y,TAN C K,GAN M L,et al. A fast,adaptive,and energy-efficient data collection protocol in multi-channel-multipath wireless sensornetworks[J]. IEEE Computational Intelligence Magazine,2018,13(1):30-40.
[12] SINGH A, ROSSI A, SEVAUX M. Heuristics for lifetime maximization in camera sensornetworks[J]. Information Sciences,2017,385/386:475-491.
[13] 刘人杰, 谢红. 基于优先级的有向传感器网络目标覆盖[J]. 传感器与微系统, 2011, 30(10):8-11.(LIU R J,XIE H. Target coverage of directional sensornetworks based on priority[J]. Transducer and Microsystem Technologies, 2011, 30(10):8-11.)
[14] JIA J,DONG C,HE X,et al. Sensor scheduling for target coverage in directional sensornetworks[J]. International Journal of Distributed Sensor Networks,2017,13(6):1-12.
[15] ALIBEIKI A,MOTAMENI A,MOHAMADI H. A new geneticbased approach for maximizingnetwork lifetime in directional sensornetworks with adjustable sensing ranges[J]. Pervasive and Mobile Computing,2019,52:1-12.
[16] 王力立, 吴晓蓓, 黄成, 等. 基于目标覆盖的异构有向传感器网络分布式节点调度策略[J]. 控制与决策, 2016, 31(12):2140-2146.(WANG L L,WU X B,HUANG C,et al. Node scheduling strategy based on target coverage for heterogeneous directional sensornetworks[J]. Control and Decision,2016,31(12):2140-2146.)
[17] 李明, 胡江平. 异构传感器网络中基于差分进化的调度算法[J]. 计算机工程,2019,45(9):70-75. (LI M,HU J P. Scheduling algorithm based on differential evolution in heterogeneous sensornetwork[J]. Computer Engineering,2019, 45(9):70-75.)
[18] SALCEDO-SANZ S, GALL-MARAZUELA D, PASTORSÁNCHEZ A,et al. Offshore wind farm design with the coral reefs optimization algorithm[J]. Renewable Energy, 2014, 63:109-115.
[19] LI M,MIAO C,LEUNG C. A coral reef algorithm based on learning automata for the coverage control problem of heterogeneous directional sensornetworks[J]. Sensors,2015,15(12):30617-30635.
[20] SIMON D. Biogeography-based optimization[J]. IEEE Transactions on Evolutionary Computation, 2008, 12(6):702-713.
[21] BILAL,PANT M,ZAHEER H,et al. Differential evolution:a review of more than two decades of research[J]. Engineering Applications of Artificial Intelligence, 2020, 90:Article No. 103479.
[22] 龙文, 蔡绍洪, 焦建军, 等. 求解高维优化问题的混合灰狼优化算法[J]. 控制与决策, 2016, 31(11):1991-1997.(LONG W, CAI S H,JIAO J J,et al. Hybrid grey wolf optimization algorithm for high-dimensional optimization[J]. Control and Decision, 2016,31(11):1991-1997.)
[23] 刘怀亮, 刘淼. 一种混合遗传模拟退火算法及其应用[J]. 广州大学学报(自然科学版), 2005, 4(2):141-145.(LIU H L,LIU M. A mixed genetic simulated annealing algorithm and its application[J]. Journal of Guangzhou University(Natural Science Edition),2005,4(2):141-145.)
[24] POTTHURI S,SHANKAR T,RAJESH A. Lifetime improvement in wireless sensornetworks using hybrid Differential Evolution and Simulated Annealing (DESA)[J]. Ain Shams Engineering Journal,2018,9(4):655-663.
[25] ISHIBUCHI H, MURATA T. A multi-objective genetic local search algorithm and its application to flowshop scheduling[J]. IEEE Transactions on Systems,Man,and Cybernetics,Part C (Applications and Reviews),1998,28(3):392-403.
[26] 高鹰, 谢胜利. 基于模拟退火的粒子群优化算法[J]. 计算机工程与应用, 2004, 40(1):47-50.(GAO Y,XIE S L. Particle swarm optimization algorithms based on simulated annealing[J]. Computer Engineering and Applications,2004,40(1):47-50.)

面向差异化覆盖的异构有向传感器节点调度算法

Heterogeneous directional sensor node scheduling algorithm for differentiated coverage

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 1

编辑推荐

Metrics