基于移动飞行器组的目标搜寻算法研究
摘要
随着物联网技术的发展，如何对移动目标进行搜寻并进行准确的定位逐渐引起了人们的关注，一个好的搜寻算法不仅能够使搜寻效率得到很大的提升，使搜寻时间减少，同时作为整个算法系统中重要的一环，对整个算法系统也有着很大的影响。本课题是基于实际应用情形，通过对实际环境进行一些优化，忽略一些不必要的外界条件，进而构建一个与实际环境相符的仿真环境，并在仿真环境下进行算法设计。
本文中按照飞行器的个数分为单飞行器搜寻算法和双飞行器搜寻算法两大部分，每个算法又细分为目标感知和目标定位两部分。通过理论分析证明算法的可行性之后，进行单飞行器搜寻算法的设计，之后进行双飞行器搜寻算法的设计。在所有的搜寻算法完成之后，在Eclipse环境下，用Java语言实现算法，并进行可视化处理，进行仿真实验，记录并分析数据，得到结论。
通过分析仿真数据发现，算法最终定位结果的误差在一个可以接受的范围内，本次设计的算法能够较好的完成搜寻任务。
查看完整论文请+Q: 351916072
关键字:算法设计；搜寻算法；目标定位；Java语言。
目录
第一章 绪论 1
1.1 课题来源与背景 1
1.2 课题的主要工作 1
第二章 基于移动飞行器组的目标搜寻需求分析 2
2.1 实际环境环境分析 2
2.2 算法模拟环境分析 2
2.2.1工作区域模拟分析 3
2.2.2飞行器模拟分析 3
2.2.3目标模拟分析 4
2.2.4其他因素模拟分析： 4
2.3 目标搜寻需求分析 4
2.3.1搜寻准确性分析 4
2.3.2搜寻效率分析 5
第三章 基于移动飞行器组的目标搜寻算法分析与设计 6
3.1 单飞行器搜寻方案的设计与分析 6
3.1.1飞行器感知方案设计 7
3.1.2飞行器定位方案设计 7
3.2 双飞行器距离非恒定搜寻方案设计与分析 10
3.2.1飞行器感知方案设计 10
3.2.2飞行器定位方案设计 10
3.3 双飞行器距离恒定搜寻方案设计与分析 12
3.3.1飞行器感知方案设计 13
3.3.2飞行器定位方案设计 13
3.4 基于工作区域划分的搜寻方案设计与分析 14
3.4.1飞行器感知方案设计 14
3.4.2飞行器定位方案设计 15
3.5 飞行器搜寻方案对比分析 16
3.5.1单飞行器与双飞行器搜寻方案对比分析 16
3.5.2双飞行器搜寻方案对比分析 16
第四章 基于移动飞行器组的目标搜寻算法实现 17
4.1 算法实现知识前提 17
4.1.1随机运动 17
4.1.2仿真可视化处理 17
4.2 核心代码实现及分析 18
4.2.1目标的随机移动 18
4.2.2飞行器的运动 19
4.2.3仿真的可视化处理 20
4.2.4绘制图形 21
4.2.5感知判断 21
4.2.6定位过程 22
4.2.7定位误差： 24
第五章 移动飞行器组的目标搜寻算法仿真分析 25
5.1 单飞行器搜寻算法仿真分析： 25
5.1.1单飞行器搜寻算法仿真图示： 25
5.1.2单飞行器搜寻算法仿真数据分析 26
5.2 双飞行器距离非恒定搜寻方案仿真分析 28
5.2.1双飞行器距离非恒定搜寻方案仿真图示 28
5.2.2双飞行器距离非恒定搜寻算法仿真数据分析 30
5.3 双飞行器距离恒定搜寻方案仿真 31
5.3.1双飞行器距离恒定搜寻方案仿真图示 32
5.3.2 双飞行器距离恒定搜寻方案仿真数据分析 33
5.4 基于工作区域划分的搜寻方案仿真 34
5.4.1基于工作区域划分的搜寻方案仿真图示 34
5.4.2基于工作区域划分的搜寻方案仿真数据分析 35
第六章 总结 37
致谢 38
参考文献 39
附录 40
第一章 绪论
1.1 课题来源与背景
本课题来源于实际中的定位情形，例如在一片深林中，有一个移动的目标，但是却不知道它具体的位置以及它将如何运动，通过使用飞行器要达到找到目标并对其进行定位（获得目标的坐标信息），甚至在找到目标之后进行跟踪。其中飞行器是一种体积较小的电子设备，它能以一定的速度进行运动，并在运动的过程中能够感知周围移动物体的大小、速度和方向等周边环境中多种多样现象的能力。多个飞行器是，飞行器之间也能进行通信，但是这种通信收到距离的限制。飞行器的能量供应为小电池，例如纽扣电池，因此它本身具有的能量是有限的，且会随着飞行器的使用时间的增加减少，导致飞行器自身的运动，通信，感知物体的能力和范围发生变化。在飞行器的整个工作过程中还可能发生飞行器损坏，外界环境影响飞行器间的通信等等异常情况。因此设计一个好的搜寻算法使其可以较好的应用到实际的工作中，并且有着姣好的搜寻结果和较高的搜寻效率是很有必要的。
1.2 课题的主要工作
本课题的主要工作是搜寻算法的设计，包括单飞行器和双飞行器两种情形。其中搜寻算法的基本要求是在有限的时间内能够对找到移动的目标，并且对其进行定位。其次是提高搜寻算法的执行效率，减少搜寻目标所使用的时间。并且在可能的情形下尽量模拟外界的环境的影响，使算法具有较好的鲁棒性。
第二章 基于移动飞行器组的目标搜寻需求分析
2.1 实际环境环境分析
在实际运用中，飞行器组的工作环境与软件仿真环境存在着很大的差异，实际的工作环境也会受到很多其他外在因素的影响。例如：飞行器组工作在一片森林区域，那么那些生长着植物的位置是飞行器组无法经过的，因此有时为了避开这些植物（障碍物），飞行器组的运动轨迹会发生改变，无法保持绝对的直线或者垂直移动，由此可能导致存在无法感测到的位置，甚至导致产生搜寻盲点影响搜寻结果；同时由于障碍物的存在，也会对感测效果产生影响，甚至会导致感知半径减小，由此会对搜寻结果及搜寻效率产生较大的影响。而如果飞行器组工作在一片较空旷的区域，由于飞行器组的体积较小，当有较强的风时，外界因素会强行使飞行器的运动轨迹发生改变，影响搜寻结果及搜寻效率。而在飞行器的工作过程中，也可能出现飞行器损坏，等异常情况；同时由于飞行器的供电是使用电池，当电量不足时，无法保证较好的感测效果；多飞行器时，存在的障碍物会对飞行器间的通信产生影响；飞行器工作区域很难保证绝对的规则图形，可能使边缘部分的感测及搜寻产生较大的误差甚至出现无法感知的区域；目标由于不是机器，因此目标的移动方向无法保证是完全随机，并且目标的移动速度也是在不断发生变化的，而且随着目标运动时间的增加，其速度应该是呈现减小的趋势，等等。外界的因素非常多且复杂，对飞行器的运行及通信都可能产生较大影响，同时由于影响的不可预测性，导致搜寻结果产生了很多不可预测性。然而这些外在条件在进行仿真时是无法全部通过软件实现出来的，过多的外在影响条件不仅会使搜寻算法的设计变得十分复杂，而且可能由于过分注重外在影响条件而忽略搜寻算法最核心的部分。因此，在仿真中会对外在条件进行弱化，更关注算法本身，在有余力的条件下再通过引入一些可控变量来模拟外在环境对飞行器的影响，进而对算法进行优化和微调，增强搜寻算法的可靠性并提高搜寻效率。
2.2 算法模拟环境分析
在进行仿真时，对飞行器的工作环境进行了理想化设置，使飞行器的工作环境更容易处理，同时也更注重搜寻算法的设计而不是过分考虑外在因素的影响，具体如下：
2.2.1工作区域模拟分析
飞行器实际环境中的工作区域一般是不规则图形，并且该区域的边界并不是非常明显。在仿真时，用一片矩形区域代表飞行器的工作区域，同时具有明显的边界，即矩形的四条边。飞行器在搜寻时不能越过矩形区域的边界。同时可以通过修改矩形的长、宽的数值来模拟不同大小的感知区域。并且该矩形中不存在飞行器无法经过的位置，即不存在障碍物，飞行器可以访问矩形内所有的位置，并且能感知飞行器感知半径内所有的位置，即不存在感知盲点。同时由于目标具有一定的大小，不可能是一个质点，因此将矩形区域进行分割，以一为最小单位，将矩形区域分割成长乘以宽个小矩形，矩形的四个角为可能的位置，目标每次的运动也是从一个角运动到附近的另一个角，矩形中间区域用来模拟目标的体积。
2.2.2飞行器模拟分析
飞行器的感知半径为变量R，对于感知范围内，位置不同的目标具有同样的感知效果，即在可感知范围内，感知效果不因目标与飞行器的距离变化而变化。
飞行器在搜寻过程中的能量供给充足，不存在运行过程中没电的情况。当飞行器开始搜寻是，不会因为使用时间的增加导致感知半径的减少或者感知效果的下降。即：感知效果及感知半径不因飞行器运行的时间长短发生变化。在仿真时，飞行器的能量不会减少，对感知没有影响。
飞行器在搜寻是的运行轨迹是直线，由于工作区域是规则的图形，并且不存在障碍物和无法经过的位置，因此飞行器在运行过程中不会发生偏转，也不会在运行轨迹中间某个区域微调或者弯曲。
飞行器的运行速度是可以改变的，但是存在一个最大速度也即极限速度，在仿真时，飞行器的运行速度可以设置为零到极限速度之间的任意值。同时由于飞行器的能量不会减少，因此飞行器的极限速度也不会减少，即在任意时刻飞行器的速度都是可以达到极限速度的。而且与搜寻目标相比，飞行器的移动速度是比较大的。
飞行器的通信半径设为无穷，飞行器间进行通信时也不会产生时延，在多飞行器搜寻时不考虑由于飞行期之间距离增加导致飞行器间无法通信的情况，飞行器的能量充足，因此也不考虑由于能量不足导致的通信距离下降或者无法通信的特殊情况。
2.2.3目标模拟分析
目标的移动速度与比飞行器的速度相比较小，因此在进行仿真时不再设置目标移动速度和飞行器移动速度两个变量，而是将目标移动速度设置为单位速度一，仅调整飞行器的移动速度和工作区域的大小来分别模拟不同速度或者不同移动区域的情形。
目标的初始位置为工作区域中的随机位置，由于对工作的矩形区域进行了分割，因此目标的移动只能是从一个点移动到附近的八个可能的点，但是这八个点的选取是随机的。通过这种方式来模拟目标的随机生成以及目标的随机移动。但是由于目标进行水平或者垂直移动时的距离与进行对角线移动的距离不同，会对结果的计算产生误差，同时也导致目标不再是进行匀速运动，在仿真时，由于工作区域的范围远大于一个单位距离，因此将会忽略由于运动方向不同带来的误差。
2.2.4其他因素模拟分析：
在进行仿真时，并没有把所有的外在因素考虑在内，而是进行了理想化设定，即外在因素对算法的设计仿真运行不存在影响。但是在进行理想化的算法方案设计及仿真后，可以通过添加一些可控制的变量来模拟外在环境的影响，并对理想化的方案进行微调或者优化，使搜寻方案在实际运用时有更好的效果。
2.3 目标搜寻需求分析
在进行目标搜寻时，需要考虑两个因素：搜寻准确性及搜寻效率。其中，搜寻准确性的重要性要高于搜寻效率，搜寻方案的设计应该是在满足搜寻准确性的前提下考虑搜寻效率的问题，并尽可能的提高搜寻效率。
2.3.1搜寻准确性分析
在进行目标搜寻时，分为两个阶段。首先要找到目标，通过飞行器的不断运动并感知不同区域的状态，进而确定目标是否在飞行器的感知范围内，即目标与飞行器直接的距离是否小于或者等于飞行器的感知半径。当满足条件时即可认为飞行器找到了目标。之后要进行的就是在找到目标后的定位工作，通过飞行器进行某种特殊的运动，根据某种计算方法计算得到目标的坐标，对目标进行定位，并尽可能的精确，定位降低误差 。
在进行搜寻时，要保证每次的搜寻最终都能找到目标，并且能进行定位，并且结果是一个合理的结果。
2.3.2搜寻效率分析
目标搜寻效率主要是指在开始搜寻到定位到目标这段过程中所用的时间。所用的时间越小，效率越高。在进行搜寻方案设计时，应该是算法在满足搜寻准确性的前提下尽可能的减少搜寻用的时间，提高搜寻效率。
第三章 基于移动飞行器组的目标搜寻算法分析与设计
理想条件下的设置以及图示如图3.1所示
图3.1理想条件下的仿真环境设置图
矩形ABCD围成的区域为飞行器的活动区域，其中AB与CD间的距离相等为L，AC与BD之间的距离相等，为H。
矩形中的圆形代表飞行器的感知区域，其中飞行器在圆心的位置，即O点处。
飞行器在矩形区域内可以随机运动，只要不超过矩形区域的范围，并且速度可以在零到极限速度直接进行选择。
原文链接：http://www.jxszl.com/dzxx/dzkxyjs/1717.html
