基于免疫连通模型与Dijkstra算法的垃圾桶区域化管理控制系统∗

陈 立 鹿顺航 曾志辉∗

(1.江西工业工程职业技术学院信息工程学院，江西 萍乡 337000；2.河南理工大学电气工程与自动化学院，河南 焦作 454003)

在日常生活中，垃圾桶的身影无处不在，垃圾桶的广泛应用在带来便捷、环境保护的同时也带来了很多麻烦，在社区诸多地方垃圾桶因垃圾装满后没有得到及时处理而造成环境二次污染，尤其是不可回收垃圾、有害垃圾，虽然目前很多智能垃圾桶的出现解决了这些问题，但由于其信息传输慢，功耗大，特别是在复杂的环境中，会出现信号丢失、软件错误等故障，并不能很好地对垃圾桶实现监测和管理。为了解决这一问题，设计一种基于免疫连通模型与Dijkstra 算法的垃圾桶区域化管理控制系统。

该系统主要由子系统节点、总站节点和系统管理后台组成。子系统利用人体感应模块检测垃圾桶周围是否有人，利用超声波传感器测距检测垃圾桶内部剩余多少空间、利用红外线传感器检测垃圾桶是否装满、通过电机驱动模块实现对压缩板以及对垃圾盖的控制。利用LoRa 组网技术，构建了一种垃圾桶区域化管理控制系统。

汪华斌等[1]采用ZigBee 技术实时监控城市的垃圾信息，但没有设计垃圾桶的防溢出功能，且并没有考虑传输距离的问题，范晨阳等[2]提出了利用NB-lot技术解决传输距离问题，并设计了垃圾桶的防溢出功能，但并没有实现对垃圾车的调度。基于以上考虑，为了解决垃圾桶装满后没有得到及时处理而造成环境二次污染的问题，提出一种基于免疫连通模型与Dijkstra 算法的垃圾桶区域化管理控制系统，利用系统管理后台来监视城市垃圾桶垃圾，并设计了垃圾桶的防溢出功能，有效地解决了垃圾桶垃圾溢出问题，并利用LoRa 技术实现垃圾桶的区域化管理，合理地调度垃圾车，有效地节约垃圾车资源。

1 系统总体框架设计

垃圾桶区域化管理控制系统共包括3 部分，即子系统节点、总站节点和系统管理后台。系统框架图如图1 所示。

图1 系统总体框架

LoRa 节点与垃圾桶连接构成子系统节点，子系统节点利用多传感器技术，采集垃圾桶内部的剩余容量信息，并通过电机驱动模块实现垃圾桶防溢出、垃圾盖自动开闭等功能，通过无线LoRa 技术发送至LoRa 总站；LoRa 总站与微处理器连接构成总站节点，起监视、合理派送垃圾车的作用。垃圾桶的模型图如下图所示:

系统管理后台和总站节点设置在垃圾站，总站节点将信息处理后上传至系统管理后台，系统管理后台通过JAVA 技术开发实现数据监控、系统报表、数据分析和满溢提醒等功能。系统的具体结构如图2 所示。

图2 系统具体结构图

2 基于免疫连通模型的Dijkstra 算法设计

2.1 信号采集

系统利用多传感器技术采集信息，其中人体感应模块检测垃圾桶周围是否有人、红外检测模块检测垃圾桶是否装满、超声波测距模块用于检测垃圾桶内部剩余多少空间。信息处理模块对采集的信息进行处理并发送至LoRa 子站主控板，LoRa 子站主控板控制根据信息处理模块发送的信息控制电机驱动模块，并对垃圾桶内部的剩余容量信息进行处理后发送至总站节点。

2.2 Dijkstra 算法设计

Dijkstra(迪杰斯特拉)算法常用来寻找带权有向图中节点之间的最短路径。针对本系统，本系统可利用Dijkstra 算法减少垃圾站与垃圾桶之间信息传递所消耗的能量。

利用Dijkstra 算法求解最短路径，简要步骤如下:

(1)设未确定的最短路径节点集合、已确定的最短路径节点集合分别为X和Y，并设起始点到其他所有节点的最短路径值为T，并利用权图的邻接矩阵对T进行过初始化。

(2)若起始点s到点i的最短路径的长度为T[i]，把i从X放到Y中。

(3)利用节点i更新数组T中起始点s到数组Y中的节点k对应的路径值。

(4)重复步骤1、2 直至找到起始点s到所有节点的最短路径值。

路径质量常用来评估传输稳定性和可靠性，当路径质量低于阙值时，表示节点发生故障。将子系统节点Ni和总站节点T之间的路径质量Q定义为子系统节点和总站节点剩余能量与距离的归一化权重和，定义为:

式中:λ为权重系数，满足λ1＋λ2＝1；Ei表示子系统节点Ni的剩余能量；Esi表示节点的初始能量；Di表示子系统节点Ni与总站节点的路径长度。

2.3 区域化免疫连通模型设计

目前，对免疫连通模型运用在无线传感器网络的研究有:运用遗传样本优化和蒙特卡洛评价函数最大化传输效率，基于二进制和概率模型的集中免疫泰森多路径优化传输[3]，多目标免疫协同进化算法[4]，泰森盲区多边形传输控制[5]，基于免疫连通模型的多路径传输选择算法[6]。基于以上考虑，区域化免疫连通模型构建如下:

抗体:垃圾桶与垃圾站之间的连通路径保证网络连通性和传输可靠性。

抗原:垃圾站监控区域内所有的垃圾桶。

抗体抗原亲和力评价函数f:垃圾桶与垃圾站之间网络传输可靠性的保证能力。单条路径质量评价函数定义为式(2)。

式中:pi为第i条传输路径，qi为该路径链的质量，w为路径链的数量。相应的M条传输路径的质量评价函数为式(3)。

抗体编码规则:垃圾站检测区域内的所有的垃圾桶以二进制编码，二进制编码位数为垃圾桶数量的最小值。

抗原/抗体(基因)变异规则:二进制数0 随机变为1，二进制数1 随机变为0，抗原变异后的节点须在上一节点的射频覆盖范围内，抗体的变异须在垃圾站和垃圾桶之间保持连通性，没有连通的抗体无效。

变异种群设置:最初随机建立w个有效抗体，保持垃圾站和垃圾桶之间的连通性。抗体的变异按照自适应遗传算法[7]中交叉概率Pc与变异概率Pm进行变异生成新的抗体群，Pc和Pm由式(4)和式(5)给出。

式中:fmax为抗体中路径的最大值，favg为抗体中路径质量的平均值，fd为变异抗体的评价值，fc为耦合交叉抗体的评价值，k1，k2，k3，k4为常数。

2.4 基于免疫连通模型的Dijkstra 算法

利用Dijkstra 算法选择最短路径传输，子系统节点和总站节点容易产生多条最短路径，通过免疫机制来选择合适的最短路径，还有效弥补了Dijkstra 算法中剩余节点能量对通信的影响，以及解决了节点意外故障对数据传输的影响。算法执行流程图如图3 所示。

图3 基于免疫连通模型的Dijkstra 算法

算法执行步骤如下:

首先，算法根据垃圾桶数，垃圾桶位置，通信距离和检测区域大小，建立能量矩阵，建立初始抗体群，对抗原抗体进行二进制编码。子系统节点根据式(1)判断节点的通信质量，选择从垃圾桶到垃圾站的w条传输路径作为w个抗体。

用式(2)对所有的抗体成员进行评价，挑选出a个抗体作为初始抗体成员群，即C＝{p(1)，p(2)，…，p(a)}。用式(3)对选择出的路径进行评价，筛选出满足条件的路径，并对这些路径进行Dijkstra 算法求解，选出新的路径组成优秀抗体群。

判断优秀抗体群的剩余能量是否小于节点剩余能量最小值，选出满足条件的抗体节点，并对选出的抗体节点进行抗体节点变异，根据抗体节点变异的规则，对抗体群里的节点按照式(4)、式(5)进行变异。用式(3)变异后的新抗体进行评价，评价后与原抗体混合比较，选择全局最优的路径，并循环执行上述步骤直至迭代次数超过预先设计值。

子系统节点利用该算法对发送的信息进行处理后发送至总站节点，可有效地解决节点意外故障对数据传输的影响，达到信息最优化传输和减少节点能耗的目的。

3 垃圾桶防溢出功能设计

垃圾桶经常存在垃圾溢出现象，因此需要给垃圾桶设计防溢出功能，即利用垃圾桶内部的LoRa 子站主控板根据信息检测系统检测到的信息控制电机驱动系统完成压缩板自动压缩和垃圾盖自动关闭。

垃圾桶防溢出设计的流程图如图4 所示。

图4 垃圾桶防溢出流程图

具体实施过程如下:

步骤1 人体感应传感器及电机驱动模块在垃圾桶的顶部，人体感应传感器检测到垃圾桶周围1 m 有人且时间持续3 s 以上时，电机驱动模块控制垃圾盖打开。

步骤2 人体感应模块检测到垃圾桶周围1 m没人且时间持续4 s 以上时，电机驱动模块控制垃圾盖关闭，反之执行步骤1。

步骤3 红外传感器位于垃圾桶的入口处，当垃圾盖关闭后，判断垃圾桶入口处红外传感器是被遮住，被遮住后执行步骤5，否之，执行步骤1。

步骤4 入口处的红外传感器被遮住后，电机驱动模块控制垃圾桶顶部压缩板自动下压后上升。

步骤5 当垃圾桶入口处红外传感器再次被遮住时，垃圾盖保持关闭，否之执行步骤1。

步骤6 当垃圾桶内部的垃圾被回收后，系统将被复位。

4 实验结果与分析

4.1 实验设置

为了验证该系统能够实现信息最优化传输和减少节点能耗以及是否能够合理节约垃圾车资源，进行相关实验验证，对运用该算法的区域化管理系统与普通的区域化管理系统进行了实验对比。

实验将子系统节点随机部署在1 000 m∗1 000 m的模拟区域内，并将节点初始能量设置成E0＝2 J；网络延迟值设置为5；节点密度为200；速度为15 m/s。实验分别从网络寿命、传输延迟和垃圾车利用率三方面验证。其中实验制作的垃圾桶模型图如图5(a)、5(b)所示。

图5 垃圾桶模型图

系统的实物图如图6、图7 所示。

图6 子系统节点实物图

图7 总站节点实物图

4.2 数据收集及分析

(1)网络寿命

通过计算存活节点的数量从而得出网络的效率，获得子系统节点的平均通信轮回次数，当75%的子系统节点能量耗完时，网络可认为完全死亡。

图8 显示了本系统和普通的区域化管理系统的平均轮回次数的对比，根据图8 可知，本系统的平均轮回次数比普通区域化管理系统的次数多，即本系统比普通系统的网络寿命更长。

图8 网络寿命

(2)传输延迟

传输延迟是指包的接收时间与发送时间差，包括路由延迟以及数据传输延迟的平均值。

图9 显示了本系统和普通的区域化管理系统的平均传输延迟的对比，根据图9 可知，本系统的平均延迟时间比普通区域化管理系统的时间短。

图9 传输延迟

(3)垃圾车利用率

假设每个子系统节点即垃圾桶装满垃圾需要10 s，设置同样的垃圾桶数量，比较普通系统和本系统使用垃圾车的数量，使用垃圾车的数量越少，垃圾车的利用率越高，

图10 显示了本系统和普通区域化管理系统的垃圾车利用率对比，根据图10 可知垃圾车利用率随子系统节点数的增加而升高，无论子系统节点少或者多，本系统的传垃圾车利用率比普通系统高。

图10 传输可靠性

5 结语

所提出的一种基于免疫连通模型与Dijkstra 算法的垃圾桶区域化管理控制系统，不仅可以解决在社区诸多地方垃圾桶因垃圾装满后没有得到及时处理的问题，还可以提高信息最优化传输以及减少节点的能耗，合理地使用垃圾车资源，实现垃圾站对垃圾桶准确监测和管理。