基于遗传算法与WiFi聚类算法结合的北斗农机精准调度

王 涛，刘 飞，高羽佳，胡 楠，张友华

(1.安徽农业大学 信息与计算机学院，安徽 合肥 230036；2.安徽农业大学 安徽省北斗精准农业信息工程实验室，安徽 合肥 230036)

随着农业规模化的种植，单靠人力去解决农田的播种、施肥、采收等农事作业显然已不能适应规模化种植的要求.

现如今导航定位加农机已渐渐成为一种趋向，而我国农机装备上大多采取GPS导航系统进行定位辅助，作为美国自主研发的导航卫星，用在我国的农机装备上对农业信息安全及长久发展有着潜在的信息安全隐患，不利于我国信息化农业的发展[1].利用我国自主研发的北斗卫星导航系统中的全天候性导航定位特点，无论在作业效率还是信息安全方面都为我国的农业机械如虎添翼.随着计算机技术和通讯技术的不断发展，北斗卫星导航系统的不断完善，加上采用遗传算法模拟分析农机与农田的最佳匹配关系，以及无信号环境下的定位信息获取，进而推算出最佳农机调度方案，使农业生产中的耕地、起垄、播种、施肥、洒药、收获等各个环节的工作效率得到大幅度提高.

1 总体技术框架

基于遗传算法与WiFi聚类算法结合的北斗农机精准调度依靠物联网技术、北斗定位技术、地理信息技术相结合，从农田墒情到地理规划，最优化解决调取农机路径，最终通过遗传算法与WiFi聚类算法模拟分析出最佳的调度方案，指派农机按照规定的路线前往农田进行农事作业，总体技术框架如图1所示.

图1 总体技术框架图

2 技术设计

基于遗传算法与WiFi聚类算法结合的北斗农机精准调度技术将物联网技术、北斗定位技术、地理信息技术相结合应用于农机设备上，通过遗传算法对农机调度进行模拟分析，并解决在无信号环境下的定位信息获取问题，最终以最佳调度方案进行农机调度[2].使用北斗导航系统，通过三频定位精确定位作业田地及农机位置；运用物联网设备来获取田间作物生长、土地温湿度及田间天气气候等一系列土壤墒情信息；通过地理信息技术来规划农田地图，进而快速确定作业面积，编号作业地块，测算最佳路径轨迹方便进行农机任务.

2.1 需求分析

在我国，田地是粮食之源，同时也是农民之本.发展我国农业，不仅仅是靠简单的人力和机械，更重要的是要做好农机在田地上的合理利用.物联网加农机的发展可在同一系统中将分散各地的农机规划整合到一起进行统筹管理，使农田面积、农机运行状态监测及土地种植情况得到有效的理论及方法支持[3].同时基于我国自主研发的北斗导航定位系统遗传算法与WiFi聚类算法分析，可以解决无信号环境下农机的定位获取问题，快速调配所需农机进行作业.

2.2 设计流程操作

基于遗传算法与WiFi聚类算法结合的北斗农机精准调度操作的流程示意图如图2所示.首先通过土壤墒情监测设备采集农田内各农作物的长势情况及相应土壤的温湿度等信息，将信息自动上传到电脑终端[4]；接着通过我国自主研发的北斗导航卫星获取农田位置信息，将位置信息发送给农机上的北斗接收机，再通过 GPRS 数据服务器进行处理后将信息发送给电脑终端[5]；当电脑终端收集到农田作业信息时，通过 GIS 地图和遗传算法与WiFi聚类算法分析规划出最佳调度路径后将所有信息发送给北斗农机，随后农机手查看信息并开往任务农田进行农事作业操作.

图2 调度操作示意图

3 硬件设备

3.1 北斗导航接收机

将北斗导航接收机安装在农机设备上具有两种安装应用，即车载型与机载型.车载型用于具有智能化体系的农机设备，载有 GNSS 外置精细化北斗导航接收机，主要完成精细播种、作物收割等功能[6]；机载型则搭建北斗B1双模北斗导航接收机[7]，适用于大面积农田的精细化农事作业.使用不同的北斗导航接收机对规模不同的农田进行作业，从而有针对性地服务于农机田间作业.

3.2 田间监测传感器

通过使用田间墒情监测传感器可以快速地了解到作业田地上更多的环境变化，然后将设备感受到的环境变化相关信息，通过内部变化转化成电信号或其他信号进行传送，最终传达到数据接收终端，最后结合农田实际情况快速地监测并分析出农田的作物状况，从而能够进行信息的传输、处理、存储、显示、记录和控制，方便进行农田作物的合理规划，提高产值.

3.3 农 机

农机在我国的使用，无论从机种还是性能都有着各自不同的作用，耕整、植保、排灌、种植、收获等操作全部都有相应的农机进行农事作业.同时农业用地占据着我国国土的很大部分，现如今农民种植已成规模化，在田间作业上，单靠人力已远远不足，使用农机进行农田作业已成为农田作业中不可缺少的劳动力.而农业机械作为田间农事作业的主要载体，对农业的发展起到重大作用.

4 功能模块设计

4.1 北斗导航系统模块

利用北斗导航系统模块可以根据三频定位获取农田信息，同时经过短报文通信实现农机与农机站之间的信息通讯，更好地服务于农机[8]，北斗信号传输过程如图3所示.

图3 北斗信号传输过程

采用北斗信号接收机、GPRS 通讯模块以及车载显示器这3个功能模块共同定位调度所需农机，可使北斗信号接收机接收卫星信号确定本农机的经纬度和时间信息，同时相应的数据按一定的时间间隔通过 GPRS 通讯模块传回 GPRS 数据服务器，GPRS 数据服务器再通过网络把数据传回到中央监控中心.从中央监控中心下行的信息通过 GPRS 数据服务器再发送到农机终端，再通过信息显示屏显示出来，使农机手更好地了解农机作业任务.

4.2 监测传感器模块

作物生长状况监测如图4所示.由于不同种类的农作物的生长时节以及生产速度有所不同，农田所需的农机调度时间也随之不同，因此可利用农田监测设备实时了解作物长势状况，有助于对农作物的播种，病害的预防以及收获做出相应的农事安排，同时在需要农机作业时可为农机调度时间安排提供完整合理的规划.

图4 实时监测田间作物生长状况

土壤温湿度监测如图5-6所示.农作物在土壤中生长，其长势好坏的重要决定性因素之一便是土壤的温湿度变化，且不同时期对农作物所种植在土壤上的温湿度要求也略有不同.土壤中温湿度的变化对肥料使用的高效性和对营养的吸收性都对农作物的长势有着重要的影响，因此监测土壤温湿度对农作物的生长有着关键性的作用，从而使农机对农作物在不同温湿度环境的生长有着合理的规划调度使用.

图6 土壤湿度监测

农作物的长势状态不仅仅依靠着土壤作为营养来源，天气状况的好坏同时也影响着作物的长势变化，对天气进行预警监测不仅能够让农作物避免气候灾害所带来的颗粒无收[9]，同时也能够调度农机在合理的时间进行田间作业，对农民来说既防患未然又丰收增产.

4.3 GIS地图模块

GIS地图模块主要运用位置动态信息实时显示的方式，将在农机车载显示器上展现，主要运用北斗定位接收器接收任务农机的经纬度信息，当农机在农田进行农事作业行驶时，农机上的接收器不间断接收卫星信号并实时记录农机的经纬度变化，然后将接收机收集的经纬度位置信息转换成大地坐标上传至电脑终端进行整合分析，通过计算可确定农机耕作面积同时对作业田地进行编号，进而能够合理规划农机路径[10].

5 遗传算法分析

5.1 条件分析

农机调度属于目标优化问题，遗传算法可以很好地解决这类问题[11],按照农户的农田位置，面积以及需要完成的作业时间等要求来规划出合理的农机调度，后台电脑再根据农户所需要求、当前农机工作状态以及农机所在地理位置等条件通过调度算法分析出最优化方案派遣农机到指定农田进行所需农事作业，且尽量减少调度成本.

根据以上农机调度处理可以得出以下信息：① 已知各农机站所具有的农机数量，随着工作量的增加，农机的作业状态会发生改变，因此在一定时间内所调度的农机需要重新评定.② 每日任务会随着时间变化进行更新，其对应的作业农田点的位置及数量也在随之改变.③ 待作业任务中记录的农田位置、面积、所需完成时间和农机作业效率、农机所处农田点、完成任务速度等因素可作为重新进行调度的评定依据[12].

5.2 条件假设

根据之前农机调度处理信息可进行条件假设：① 当一台农机作业于一个任务农田点时，其农机农事作业任务完成之前不可再次调用前往其他任务农田点进行工作.② 单位时间内的农机进行农事作业的效率相同且在前往作业点所耗费的成本相同.③ 每块作业田地只需一辆农机进行农事作业.

5.3 建立模型

在农机前往作业点完成作业任务的同时减少调度过程中的成本损耗，对农机的调度算法建立相应的数学模型：设在农机站中具有某种类型农机m台，分别为M1,M2,…,Mm.当在t时刻的所有任务中所需完成的任务农田点为n，编号为F1,F2,…,Fn；将北斗导航定位终端安装在每台任务农机上，通过短时间间隔不断发送农机位置信息到调度中心；在农机前往任务点路程中所损耗的成本相同，设为C，可设为常量，每次调度农机所耗费成本与农机从当前位置前往作业农田点的时间TC直接相关，而根据 GIS 地图模块可提供 API 接口用于计算农机在两点间的路程和时间，所以在计算调度损耗时可将农机实时经纬度信息替换为 GIS 地图中的位置坐标后再调用 GIS 地图 API 进行计算.

设农机在单位时间内的工作效率为W，因同种型号的农机工作效率相同，可将工作效率W作为常量进行计算.由任务农田点的实际作业面积S、农机忙碌当前完成时间T0、最迟完成时间Ts以及农机作业效率可得到完成任务农田所需要时间Te，且Te=Ts+S/W.

设在t时刻任务农田点x的未完成作业的面积为Sta，确立目标函数如下:

(1)

式中：minR为目标函数的农机耗损成本总量最小值；Cij表示农机单位时间耗损量；TCij表示农机前往作业点所用时间.

约束条件如下：

Cij∈{0,1}，

(2)

(3)

T0+TCij+Sta/W

(4)

式(2)表示任务农田点是否有农机被调度前往，若农机被调度则农机有成本耗损，否则成本耗损为 0；式(3)表示每个任务农田点仅调度一台农机前往农事作业；式(4)表示农机完成当前作业任务时间加上调度前往到下一任务农田点时间及其任务农田点完成所需时间应小于下一任务农田点要求的最迟完成时间.

5.4 仿真分析

根据以上建立的数学模型将农田面积设置X和Y轴坐标进行表示，划定一定区域表示某一地区的农田总数，然后将农田用红圈表示，忙碌农机用x，空闲农机用三角进行表示，可得到如图 7 的示意图，并通过假设 10 组数据进行推演，筛选出非忙碌农机进行算法演练.

图7 构建算法示意图及模拟数据

接下来，根据约束条件：

T0+TCij+Sta/W

可以计算出农机当前任务的完成时间加上到达时间以及下一任务完成时间需要小于任务中所要求的最迟完成时间，从而筛选出符合条件的农机，结果如图8所示.

图8 设置约束条件及判断结果

通过建立的目标函数，生产染色体及矩阵进行运算，如图9所示，图中染色体编码表示几号农田有农机正在工作，例如：9号农田有农机在工作.同时随机生成1 000个染色体样本并计算适应度，选出其中的最优解作为对比.

图9 生成染色体矩阵与对比值

此时，通过初始化种群，生成100个样本进行筛选，如图10所示.按照适应度进行排序，得到一组染色体序列矩阵，为下面遗传演化提供数据[13].

图10 初始化种群进行样本筛选

通过上面得到的一组染色体矩阵作为遗传演化的父代染色体，通过交叉、变异得到子代染色体矩阵同时算出距离度量及农机到农田的最小距离，如图11所示.

图11 父代染色体交叉、变异进行遗传演化

根据遗传算法进行重复迭代演化(见图12)，将迭代 1 000 次的距离最小值提取出来，得到一个趋于最小值的稳定值，如图 13 所示，可以明显看出当进行大量迭代时，最小值趋于平稳状态，从而通过交叉、变异遗传算法可得出农机到作业农田的最短距离，进而规划出最优方案[14].

图12 重复迭代演化

图13 对比值与迭代最小值比较

在农机设备上安装的北斗信号接收模块，可根据北斗卫星实时了解到农机所在位置的准确经纬度，在空闲状态的农机根据遗传算法调度分配任务，前往作业田地进行正常农事作业；当有农机处于忙碌状态时可自动跳过遗传算法分析，继续作业当前任务，直到忙碌状态的农机完成当前农机作业时可重新规划进行调度安排.

6 WiFi聚类算法分析

现如今农机站分配农机或私有农机前往农事作业时，有时由于经过涵洞、高压线区域或前往偏远山区等无信号环境进行作业时，农机站无法掌握派遣农机的定位信息以及自身农机的具体位置状况，这使得农机定位领域还不太完善，因此利用WiFi聚类算法分析农机在无信号下获取定位信息，为农机进行北斗精准调度提供支持.

6.1 算法原理

该类方法主要由由WiFi信号收发模块、WiFi 终端、农机、K-means++聚类算法构成，即通过WiFi信号发射模块不间断发射无线信号帧至农机上的WiFi终端；WiFi 终端主要接收WiFi信号发射模块的无线信号帧，收集所在位置信号形成信号库；农机主要进行农事作业；K-means++聚类算法对信号库中的大量无线信号帧筛选聚类质点，分析，迭代，得出所划分K个区域中各个空间区域的中心点位置.WiFi 信号发射模块通过发射大量无线信号帧到农机上的WiFi终端上，与终端连接的聚类算法模块通过 K-means++算法分析出农机所在的三维信息，获取农机位置信息，进而达到定位的功能.

6.2 分析过程

1)选取一片无信号环境下的农田，模拟出此块农田的空间图形，如图14所示，并将此空间划分为K个小空间(K>0)，如图 15 所示.

图14 模拟农田空间结构

图15 等间隔划分K个小空间

2)在这片区域的中心点树立一个WiFi信号发射模块，用于发射无线信号帧，并确定此固定位置的三维坐标，坐标设为A(X0，Y0，Z0)，如图16所示.

图16 建立WiFi信号发射模块

3)在作业农机设备上安装WiFi终端，负责不间断接收WiFi信号发射模块的无线信号帧.

4)由于WiFi信号发射模块具有 MAC 地址唯一性的特点，在WiFi终端设备上筛选出WiFi信号发射模块的无线信号帧，滤除其他无用无线信号帧.

5)在划分出来的各个小空间内筛选WiFi终端通过信号发射模块获取的所有无线信号帧，建立信号库.

6)采用聚类算法中的K-means++算法将信号库中的大量无线信号帧选取聚类质点并进行分析，即可将每个小空间定位为一个具体的位置信息点，同时定位的每个位置信息点同步到WiFi终端上，如图17所示.

图17 模拟聚类分析及位置信息点

7)根据每个小区间的定位信息结合已知WiFi信号发射模块的具体三维定位信息即可得到农机的三维定位信息B(X1，Y1，Z1).

8)根据WiFi终端接收从WiFi信号发射模块发射出来的无线信号帧的 RSSI 值大小可分析出作业农机的路径轨迹，同时将终端定位连接到农机操作系统设备上，可进一步判断农机故障点位置，方便进行农机维护管理.

6.3 算法流程图

K-means++算法流程图如图 18 所示，即在每个空间选取无线信号帧作为聚类质点，并设定相互之间的距离竟可能远，再采用欧式距离计算每个空间剩余无线信号帧到聚类质点的距离，若有质点发生较大变化则重复更新每个空间聚类质点位置，直到没有或有很少聚类质点发生改变则结束K-means++算法过程.

图18 K-means++算法流程图

7 结 论

基于遗传算法与WiFi聚类算法结合的北斗农机精准调度是利用国内自主研发的定位系统着眼于解决我国农业大规模种植所需农机合理分配调度的问题，并依靠高效的遗传算法与WiFi聚类算法结合分析出调度的最优解决方案，能够有效地利用农业物联网监测技术，全方位地服务于大规模田间作业.通过物联网监测技术收集到的田间数据通过通讯模块传输到中央服务器上，根据监测数据调度农机，同时依靠GIS地图模块来规划出农机行径路线以及根据北斗定位系统确认作业田地，从而方便农机在任务作业田完成作业.

在使用基于北斗定位的农机调度设计的时候，需要提前依据GIS地图规划好该地区所涉及的大规模作业田地，使农田能够在农机车载显示器上完美地显示出来，从而为北斗定位提供帮助.一方面，这解决了我国大规模种植农户面对农事作业时可采取最高效的农机调度措施进行田间作业问题；另一方面，在无信号环境下的农田也可调度农机进行农事作业，使我国农机不再受信号环境影响而无法作业，促进各地农机站内的农机得到合理高效的利用，最终使农田增产丰收，农民的收益得到最大化.