考虑3G/4G网络特性的多无人机环保监测任务调度

doi:10.11772/j.issn.1001-9081.2016.03.871

计算机应用 ›› 2016, Vol. 36 ›› Issue (3): 871-877.DOI: 10.11772/j.issn.1001-9081.2016.03.871

考虑3G/4G网络特性的多无人机环保监测任务调度

欧阳秋萍, 李杰, 沈林成

国防科学技术大学机电工程与自动化学院, 长沙 410073

收稿日期:2015-08-05 修回日期:2015-09-15 出版日期:2016-03-10 发布日期:2016-03-17
通讯作者: 欧阳秋萍
作者简介:欧阳秋萍(1989-),女,湖南长沙人,硕士研究生,主要研究方向:环保无人机、无人机任务规划;李杰(1984-),男,湖南长沙人,讲师,博士,主要研究方向:任务规划、多机协同;沈林成(1965-),男,江苏吴江人,教授,博士生导师,博士,主要研究方向:飞行器任务规划、无人机自主协同控制、仿生机器人与智能控制。

Multiple-unmanned aerial vehicle environmental monitoring task schedule considering 3G/4G network feature

OUYANG Qiuping, LI Jie, SHEN Lincheng

College of Mechatronical Engineering and Automation, National University of Defense Technology, Changsha Hunan 410073, China

Received:2015-08-05 Revised:2015-09-15 Online:2016-03-10 Published:2016-03-17

摘要/Abstract

摘要： 针对采用传统视距链或图传电台的无人机环保监测距离受限、在线传输数据量受限,以及大功率数据链无法搭载于小型环保无人机等问题,提出了一种基于3G/4G网络的多无人机环保监测任务调度的方法。首先,将3G/4G网络的时间特性与多无人机环保监测任务调度相结合,将多无人机任务调度问题建模为带时间窗的团队定向问题(TOPTW);然后,针对TOPTW求解中存在计算量大、易陷入局部最优的问题,提出一种局部迭代搜索(ILS)算法来优化求解TOPTW;其次,使用大量测试集检验该算法的可行性和运算性能,与现有的蚁群算法(ACA)比较结果的平均收益与计算时间;最后设计了3G/4G网络下典型的双机环保监测任务调度环境,并将ILS算法应用其中。仿真结果表明,与蚁群算法相比,ILS所得收益大部分都要低于ACA所得收益,所有算例收益的平均Gap为1.09%,最大值为10.8%,其中也有部分结果要优于ACA结果;计算时间平均缩减至千分之一。实验结果表明,ILS算法能快速得到多无人机任务调度序列,有效减少了计算时间而实验收益结果在可接受范围内。

关键词: 3G/4G网络, 环保监测, 时间窗, 团队定向问题, 迭代局部搜索, 无人机

Abstract: Focused on the limitation of monitoring distance, restriction of online transmission, large amount of information and that high-power data-link is disable to board small environment monitoring Unmanned Aerial Vehicle (UAV), a multiple-UAV environment monitoring task scheduling method considering 3G/4G network features was proposed. First, the time characteristic of 3G/4G network and the multiple-UAV environment monitoring task scheduling were combined, and this issue was modeled as Team Orienteering Problem with Time Window (TOPTW). Secondly, since the problem of huge computation and easily falling into local optimum, an Iterated Local Search (ILS) algorithm was proposed to get the optimization solution. Thirdly, a large amount of test data sets were applied into experiments to verify the feasibility and computing performance, and the comparative result between ILS and Ant Colony Algorithm (ACA) about the average profit and computing time were proposed. Last, the algorithm was applied in typical two UAV environment monitoring task scheduling under 3G/4G network. The results show that, the most profits received from ILS were worse than those from ACA. The average Gap of all test data sets was 1.09% and the largest was 10.8%. There were some results better than those in ACA. And the computing time of ILS was nearly reduced to a thousandth of the computing time of ACA. The experimental results show that ILS algorithm can fast solve the issue of multi-UAV environment monitoring task scheduling and effectively reduce the computing time with profit results in an acceptable scope.

Key words: 3G/4G network, environmental monitoring, time window, team orienteering problem, iterated local search, Unmanned Aerial Vehicle (UAV)

中图分类号:

TP391.9

欧阳秋萍, 李杰, 沈林成. 考虑3G/4G网络特性的多无人机环保监测任务调度[J]. 计算机应用, 2016, 36(3): 871-877.

OUYANG Qiuping, LI Jie, SHEN Lincheng. Multiple-unmanned aerial vehicle environmental monitoring task schedule considering 3G/4G network feature[J]. Journal of Computer Applications, 2016, 36(3): 871-877.

参考文献

[1] 朱京海,梁婷,徐光,等.无人机遥感技术在环境保护领域中的应用进展[J].环境保护科学,2013,39(4):97-100.(ZHU J H, LIANG T, XU G, et al. Application progress of uav remote sensing technology in the field of environmental protection [J]. Environmental Protection Science, 2013,39(4):97-99.)
[2] 朱京海,徐光,刘家斌.无人机遥感系统在环境保护领域中的应用研究[J].环境保护与循环经济,2011,31(9):45-48.(ZHU J H, XU G, LIU J B. Application research of UAV remote sensing technology in the field of environmental protection [J]. Environmental Protection and Circular Economy, 2011,31(9):45-48.)
[3] 谢涛,刘瑞,胡秋红,等.基于无人机遥感技术的环境监测研究进展[J].环境科技,2013,26(4):56-60.(XIE T, LIU R, HU Q H, et al. A critical review on unmanned aerial vehicle remote sensing technology in the field of environmental monitoring [J]. Environmental Science and Technology, 2013,26(4):56-60.)
[4] 李桂花.外军无人机数据链的发展现状与趋势[J].电讯技术,2014(6):851-856.(LI G H. Status and trend of foreign military data link for unmanned aerial vehicles [J]. Telecommunication Engineering, 2014(6):851-856.)
[5] CHAO I M, GOLDEN B L, WASIL E A. The team orienteering problem [J]. European Journal of Operational Research, 1996,88(3):464-474.
[6] VANSTEENWEGEN P, SOUFFRIAU W, OUDHEUSDEN D V. The orienteering problem: a survey [J]. European Journal of Operational Research, 2011,209(1):1-10.
[7] LAPORTE G, MARTELLO S. The selective travelling salesman problem [J]. Discrete Applied Mathematics, 1990,26(2/3):193-207.
[8] KATAOKA S, MORITO S. An algorithm for single constraint maximum collection problem [J]. Journal of the Operations Research Society of Japan, 1988,31(4):515-531.
[9] SCHILDE M, DOERNER K F, HARTL R F, et al. Metaheuristics for the bi-objective orienteering problem [J]. Swarm Intelligence, 2009,3(3):179-201.
[10] CHAO I M, GOLDEN B L, WASIL E A. A fast and effective heuristic for the orienteering problem [J]. European Journal of Operational Research, 1996,88(3):475-489.
[11] BUTT S E, CAVALIER T M. A heuristic for the multiple tour maximum collection problem [J]. Computers and Operations Research, 1994,21(1):101-111.
[12] LIN S W. Solving the team orienteering problem using effective multi-start simulated annealing [J]. Applied Soft Computing, 2013,13(2):1064-1073.
[13] LABADIE N, MANSINI R, MELECHOVSKY J, et al. The team orienteering problem with time windows: an LP-based granular variable neighborhood search [J]. European Journal of Operational Research, 2012, 220(1):15-27.
[14] SOUFFRIAU W, VANSTEENWEGEN P, BERGHE G V, et al. A path relinking approach for the team orienteering problem [J]. Computers and Operations Research, 2010,37(11):1853-1859.
[15] VANSTEENWEGEN P, SOUFFRIAU W, BERGHE G V. Iterated local search for the team orienteering problem with time windows [J]. Computers and Operations Research, 2009,36(12):3281-3290.
[16] MONTEMANNI R, GAMBARDELLA L M. An ant colony system for team orienteering problems with time windows [J]. Foundations of Computing and Decision Sciences, 2009,34:287-306.

考虑3G/4G网络特性的多无人机环保监测任务调度

Multiple-unmanned aerial vehicle environmental monitoring task schedule considering 3G/4G network feature

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	李舒仪, 韩晓龙. 海铁联运港口混合作业模式下轨道吊与集卡协同调度[J]. 计算机应用, 2021, 41(5): 1506-1513.
[2]	马子玉, 何明, 刘祖均, 顾凌枫, 刘锦涛. 无人机协同控制研究综述[J]. 计算机应用, 2021, 41(5): 1477-1483.
[3]	焦海林, 郭玉英, 朱正为. 基于加速度补偿的无人机吊挂飞行抗摆控制[J]. 计算机应用, 2021, 41(2): 604-610.
[4]	钟莎, 黄玉清. 基于孪生区域候选网络的无人机指定目标跟踪[J]. 计算机应用, 2021, 41(2): 523-529.
[5]	黄书召, 田军委, 乔路, 王沁, 苏宇. 基于改进遗传算法的无人机路径规划[J]. 计算机应用, 2021, 41(2): 390-397.
[6]	王岱巍, 徐高潮, 李龙. 无人机辅助的移动边缘计算中的任务分配策略[J]. 计算机应用, 2021, 41(10): 2928-2936.
[7]	黄巨挺, 高宏力, 戴志坤. 基于编码解码结构的移动端电力线语义分割方法[J]. 计算机应用, 2021, 41(10): 2952-2958.
[8]	张驰, 李铸洪, 刘舟, 沈未名. 基于场景图划分的无人机影像定位算法[J]. 计算机应用, 2021, 41(10): 3004-3009.
[9]	张凌浩, 王胜, 周辉, 陈一凡, 桂盛霖. 基于MAVLink协议的无人机系统安全通信方案[J]. 计算机应用, 2020, 40(8): 2286-2292.
[10]	卫文乐, 金国栋, 谭力宁, 芦利斌, 陈丹琪. 利用惯导测量单元确定关键帧的实时SLAM算法[J]. 计算机应用, 2020, 40(4): 1157-1163.
[11]	张庆华, 吴光谱. 带时间窗的同时取送货车辆路径问题建模及模因求解算法[J]. 计算机应用, 2020, 40(4): 1097-1103.
[12]	任娜, 张楠, 崔妍, 张融雪, 庞新富. 面向无人机电力巡检的语义实体构建及航迹控制方法[J]. 计算机应用, 2020, 40(10): 3095-3100.
[13]	杨正清, 周朝荣, 袁姝. 移动群智感知系统中基于离散布谷鸟搜索算法的任务分配[J]. 计算机应用, 2019, 39(9): 2778-2783.
[14]	宋婷, 陈矛, 吴超, 张龚钊. 基于多类迭代局部搜索的自动化排课算法[J]. 计算机应用, 2019, 39(6): 1760-1765.
[15]	张午阳, 章伟, 宋芳, 龙林. 基于深度学习的四旋翼无人机单目视觉避障方法[J]. 计算机应用, 2019, 39(4): 1001-1005.