基于改进离散果蝇优化算法的WSN广播路由算法

doi:10.11772/j.issn.1001-9081.2017.04.0965

计算机应用 ›› 2017, Vol. 37 ›› Issue (4): 965-969.DOI: 10.11772/j.issn.1001-9081.2017.04.0965

基于改进离散果蝇优化算法的WSN广播路由算法

徐同伟, 何庆, 吴意乐, 顾海霞

贵州大学大数据与信息工程学院, 贵阳 550025

收稿日期:2016-08-30 修回日期:2016-12-24 出版日期:2017-04-10 发布日期:2017-04-19
通讯作者: 何庆
作者简介:徐同伟(1991-),男,山东滕州人,硕士研究生,主要研究方向:无线传感网络、认知无线网络、群智能优化算法;何庆(1982-),男,贵州瓮安人,副教授,博士,主要研究方向:无线网络、群智能优化算法、数据分析;吴意乐(1991-),男,江苏苏州人,硕士研究生,主要研究方向:无线传感网络、群智能优化算法;顾海霞(1993-),女,江苏泰州人,硕士研究生,主要研究方向:无线传感网络、群智能优化算法、数据分析。
基金资助:
贵州省教育厅项目基金资助项目（黔教合KY字[2016]124）；贵州省科技厅项目基金资助项目（黔科合LH字[2014]7628）；贵州大学博士项目基金资助项目（贵大人基合字[2010]010）；贵州大学研究生创新基金资助项目（研理工2016066）。

Broadcast routing algorithm for WSN based on improved discrete fruit fly optimization algorithm

XU Tongwei, HE Qing, WU Yile, GU Haixia

College of Big Data and Information Engineering, Guizhou University, Guiyang Guizhou 550025, China

Received:2016-08-30 Revised:2016-12-24 Online:2017-04-10 Published:2017-04-19
Supported by:
This work is partially supported by the Guizhou Provincial Education Department' Project (KY[2016]124), the Guizhou Provincial Science and Technology Department' Project (LH[2014]7628), the Doctoral Foundation of Guizhou University ([2010]010), the Graduate Innovation Foundation of Guizhou University (2016066).

摘要/Abstract

摘要：

为解决无线传感网络（WSN）节点能量限制和广播路由的能耗问题，提出一种基于改进离散果蝇优化算法（DFOA）的WSN广播路由算法。首先，将交换子和交换序引入到果蝇优化算法（FOA）中，得到DFOA，拓展FOA的应用领域；然后，利用莱维（Lévy）飞行对果蝇随机探索的步长进行控制，增加DFOA的样本多样性，并用轮盘赌选择对种群的位置更新策略进行改进，避免算法陷入局部最优；最后利用改进DFOA对WSN路由能耗寻优，找到能耗最小的广播路径。仿真结果表明，改进DFOA获得的广播能耗更低，在不同的网络规模下，均优于对比算法（原DFOA、模拟退火遗传算法（SA-GA）、蚁群优化（ACO）算法和粒子群优化（PSO）算法）。改进DFOA能增加种群多样性，增强跳出局部最优的能力，提高网络性能。

关键词: 无线传感网络, 广播路由, 离散果蝇优化算法, 莱维飞行, 轮盘赌选择

Abstract:

In Wireless Sensor Network (WSN), to deal with the energy limitation of nodes and the energy consumption of broadcast routing, a new WSN broadcast routing algorithm based on the improved Discrete Fruit fly Optimization Algorithm (DFOA) was proposed. Firstly, the swap and swap sequence were introduced into the Fruit fly Optimization Algorithm (FOA) to obtain DFOA, which expands the applications field of FOA. Secondly, the step of fruit fly was controlled by the Lévy flight to increase the diversity of the samples, and the position updating strategy of population was also improved by the roulette selection to avoid the local optimum. Finally,the improved DFOA was used to optimize the broadcast routing of WSN to find the broadcast path with minimum energy consumption. The simulation results show that the improved DFOA reduces the energy consumption of broadcast and has better performance than comparison algorithms including the original DFOA, Simulated Annealing Genetic Algorithm (SAGA), Ant Colony Optimization (ACO) and Particle Swarm Optimization (PSO) in different network. The improved DFOA can increase the diversity of the samples, enhance the ability of escaping from local optimum and improve the network performance.

Key words: Wireless Sensor Network (WSN), broadcast routing, Discrete Fruit fly Optimization Algorithm (DFOA), Lévy flight, roulette selection

中图分类号:

TP301.6

徐同伟, 何庆, 吴意乐, 顾海霞. 基于改进离散果蝇优化算法的WSN广播路由算法[J]. 计算机应用, 2017, 37(4): 965-969.

XU Tongwei, HE Qing, WU Yile, GU Haixia. Broadcast routing algorithm for WSN based on improved discrete fruit fly optimization algorithm[J]. Journal of Computer Applications, 2017, 37(4): 965-969.

参考文献

[1] 孙利民, 李建中, 陈渝, 等. 无线传感器网络[M]. 北京:清华大学出版社, 2005.(SUN L M, LI J Z, CHEN Y, et al. Wireless Sensor Networks[M]. Beijing: Tsinghua University Press, 2005.)
[2] GOLDBERG D E, SASTRY K. Genetic Algorithms[M]. Berlin: Springer, 2015.
[3] HABIB S J, MARIMUTHU P N. Restoring coverage area for WSN through simulated annealing[J]. International Journal of Pervasive Computing & Communications, 2011, 7(3):205-219.
[4] AROLKAR H A, SHETH S P, TAMHANCE V P. Ant colony based approach for intrusion detection on cluster heads in WSN[C]//ICCCS 2011: Proceedings of the 2011 International Conference on Communication, Computing & Security. New York: ACM, 2011:523-526.
[5] TANG T, GUO Q, YANG M. Support vector machine based particle swarm optimization localization algorithm in WSN[J]. Journal of Convergence Information Technology, 2012, 7(1):497-503.
[6] KARABOGA D, AKAY B. A comparative study of artificial bee colony algorithm[J]. Applied Mathematics & Computation, 2009, 214(1):108-132.
[7] 潘文超. 果蝇最佳化演算法[M]. 台北:沧海书局, 2011.(PAN W-T. Fruit Fly Optimization Algorithm[M]. Taipei: Tsang Hai Book Publishing, 2011.)
[8] PAN W-T. A new fruit fly optimization algorithm: taking the financial distress model as an example[J]. Knowledge-Based Systems, 2012, 26(2):69-74.
[9] 白舸. 无线传感器广播路由算法研究[D]. 洛阳:河南科技大学, 2013.(BAI K. Research of wireless sensor network broadcast routing algorithm[D]. Luoyang: Henan University of Science and Technology, 2013.)
[10] 吴意乐, 何庆. 基于改进遗传模拟退火算法的WSN路径优化算法[J]. 计算机应用研究, 2016, 33(10):2959-2962.(WU Y L, HE Q. WSN path optimization based on improved genetic simulated annealing algorithm[J]. Application Research of Computers, 2016, 33(10):2959-2962.)
[11] 苏锦, 张秋红, 杨新锋. 改进蚁群算法的无线传感器网络路径优化[J]. 计算机仿真, 2012, 29(8):112-115.(SU J, ZHANG Q H, YANG X F. Path optimization of wireless sensor network based on improved ant colony algorithm[J]. Computer Simulation, 2012, 29(8):112-115.)
[12] 袁浩. 基于粒子群算法的WSN路径优化[J]. 计算机工程, 2010, 36(4):91-92.(YUAN H. Wireless sensor network path optimization based on particle swarm algorithm[J]. Computer Engineering, 2010, 36(4):91-92.)
[13] 秦智超, 周正, 赵小川. 利用粒子群优化的WSN环状簇路由协议[J]. 北京邮电大学学报, 2012, 35(5):26-30.(QIN Z C, ZHOU Z, ZHAO X C. A ring-based clustering routing protocol for WSN using particle swarm optimization[J]. Journal of Beijing University of Posts and Telecommunications, 2012, 35(5):26-30.)
[14] 郑振华. 基于人工蜂群算法的组播路由优化与仿真[D]. 济南:山东大学, 2012.(ZHENG Z H. Multicast routing optimization and simulation based on artificial bee colony algorithm[D]. Jinan: Shandong University, 2012.)
[15] 唐勇, 周明天. 无线传感器网络中最小化能量广播算法[J]. 通信学报, 2007, 28(4):80-86.(TANG Y, ZHOU M T. Minimum energy broadcasting algorithm in wireless sensor networks[J]. Journal on Communications, 2007, 28(4):80-86.)
[16] WANG K-P, HUANG L, ZHOU C-G, et al. Particle swarm optimization for traveling salesman problems[C]//Proceedings of the 2003 International Conference on Machine Learning and Cybernetics. Piscataway, NJ: IEEE, 2003, 3:1583-1585.
[17] 马晓慧, 王红. 改进的PSO在TSP中的应用[J]. 计算机与现代化, 2011(9):5-7.(MA X H, WANG H. Application of improved PSO in TSP[J]. Computer and Modernization, 2011(9):5-7.)
[18] 霍慧慧. 果蝇优化算法及其应用研究[D]. 太原:太原理工大学, 2015.(HUO H H. Research om fruit fly optimization algorithm and its applications[D]. Taiyuan: Taiyuan University of Technology, 2015.)
[19] YANG X-S, DEB S. Cuckoo search via Levy flights[C]//NaBIC 2009: Proceedings of the 2009 World Congress on Nature & Biologically Inspired Computing. Piscataway, NJ: IEEE, 2010:210-214.
[20] YANG X-S, DEB S. Engineering optimisation by cuckoo search[J]. International Journal of Mathematical Modelling & Numerical Optimisation, 2010, 1(4):330-343.
[21] 王李进, 尹义龙, 钟一文.逐维改进的布谷鸟搜索算法[J]. 软件学报, 2013, 24(11):2687-2698.(WANG L J, YIN Y L, ZHONG Y W. Cuckoo search algorithm with dimension by dimension improvement[J]. Journal of Software, 2013, 24(11):2687-2698.)

基于改进离散果蝇优化算法的WSN广播路由算法

Broadcast routing algorithm for WSN based on improved discrete fruit fly optimization algorithm

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	贾鹤鸣, 李瑶, 姜子超, 孙康健. 基于改进共生生物搜索算法的林火图像多阈值分割[J]. 计算机应用, 2021, 41(5): 1465-1470.
[2]	张争万, 张春炯, 李洪兵, 谢涛. 基于免疫连通模型的多路径传输选择算法[J]. 计算机应用, 2020, 40(12): 3571-3577.
[3]	韩司, 郑宝昆, 曹奇敏. 基于逻辑密钥树的无线传感网络密钥管理方案[J]. 计算机应用, 2019, 39(5): 1378-1384.
[4]	郑延斌, 席鹏雪, 王林林, 樊文鑫, 韩梦云. 基于人工势场法的多智能体编队避障方法[J]. 计算机应用, 2018, 38(12): 3380-3384.
[5]	谢小军, 于浩, 陶磊, 张信明. 可充电无线传感网络能量均衡路由算法[J]. 计算机应用, 2017, 37(6): 1545-1549.
[6]	甘峰浩, 牛玉刚, 贾廷纲. 基于模糊压缩感知的无线传感网络拥塞控制算法[J]. 计算机应用, 2015, 35(9): 2430-2435.
[7]	董跃华, 戴玉倩. 混合粒子群算法的软件测试数据自动生成[J]. 计算机应用, 2015, 35(2): 545-549.
[8]	王培崇高文超钱旭苟海燕汪慎文. 应用精英反向学习的混合烟花爆炸优化算法[J]. 计算机应用, 2014, 34(10): 2886-2890.
[9]	刘明珠许士涛陈光. 基于自适应更新的无线传感网络MAC协议[J]. 计算机应用, 2012, 32(12): 3508-3511.
[10]	任秀丽韩静晶. 基于无线传感网的海洋监测节点定位算法[J]. 计算机应用, 2012, 32(10): 2692-2695.
[11]	陈庆奎周利珍. 基于HBase的大规模无线传感网络数据存储系统[J]. 计算机应用, 2012, 32(07): 1920-1923.
[12]	张斌毛剑琳李海平陈波. 群混合算法应用于异构传感网络节点的优化部署[J]. 计算机应用, 2012, 32(05): 1228-1231.
[13]	周运詹华伟. 无线传感网络中有向性传感节点的覆盖问题[J]. 计算机应用, 2011, 31(12): 3200-3203.
[14]	张永强赵春燕. 利用核局部保持映射分析到达时间定位问题[J]. 计算机应用, 2011, 31(10): 2876-2879.
[15]	曹莹莹于建江朱立才孙家军万小霞. 本地多行栅栏覆盖节点活跃调度协议[J]. 计算机应用, 2011, 31(04): 918-921.