1、小 型 微 型 计 算 机 系 统 ：年 月 第 期 收稿日期：收修改稿日期：基金项目：国家自然科学基金项目（）资助；安徽建筑大学智能建筑与建筑节能安徽省重点实验室开放课题项目（）资助 作者简介：王杨，男，年生，博士，教授，会员，研究方向为可充电传感网、机器学习、系统优化；单天乐，男，年生，硕士研究生，研究方向为无线可充电传感网；赵传信，男，年生，博士，教授，研究方向为物联网技术与无线可充电传感网；陈 鹏，男，年生，博士，讲师，研究方向为机器学习；艾世成，男，年生，硕士，助教，研究方向为网络优化无人机辅助的无线可充电传感网充电路径规划方案王 杨，单天乐，赵传信，陈 鹏，艾世成（安徽师范大学 计
2、算机与信息学院，安徽 芜湖）（安徽建筑大学 智能建筑与建筑节能安徽省重点实验室，合肥）（东南大学 计算机科学与工程学院，南京）：摘 要：针对传统无线可充电传感网（）存在传感器节点较为分散导致的充电效率低问题，提出了一种基于对 进行分簇的无人机（）充电路径优化方案（，）方案首先将目标区域根据聚类算法划分为不大于充电器最大可覆盖范围的子区域并称其为簇；然后确定各簇区域锚点以及优先级并对充电最优路径进行选择；最后借助无人机给所有簇内传感器节点充能并返回充电中心（，）仿真实验验证了方案的可行性，实验结果与、方案相比，方案的充电效率分别提高了约 、，平均饿死节点数分别降低 、个 与、方案相比，的飞行长度
3、与充电时长都有明显缩短关 键 词：无线可充电传感网；簇优先级；最优充电路径规划；最大可覆盖范围；无人机中图分类号：文献标识码：文 章 编 号：（），（，）（，）（，）：（），（，）；，（），：；引 言针对无线可充电传感网的节点能量补充问题，国内外学者进行了很多研究和实践，其中最常用的是利用移动充电小车（，）对 进行能量补充 然而，充电小车在一些条件受限和环境恶劣的地区，比如自然灾区、战争地区等，难以发挥其作用 即便在常规环境，也可能因障碍物较多使其路径规划失败为了解决此问题，本文提出了无人机辅助的基于分簇的 充电路径规划 文中无人机指携带充电装置、可进行无线充电的飞行器 其优点包括：速度快、灵
4、活性强、可以轻松越过一般障碍物以及定点悬停等 所以，本文所提出的借助 的基于分簇无线充电策略，可以弥补 的不足之处现有无线充电技术主要基于 大原理：）电磁感应技术，生活中很多设备都利用这一技术实现无线充电，例如手机、电动汽车等，它具有技术成熟且简单、一对一式充电、效率较低等特点；）磁耦合谐振技术，相比电磁感应充电技术，它支持更大的空间范围内的能量传输，具有可以一对多式充电、距离较短（米左右）等特点；）无线电波技术，它具有充电范围更广（几十公里）、要求较高、安全性不够高等特点 本文采用磁耦合谐振技术对网络进行充电，比较符合中小范围内无线充电的要求根据充电器锚点的选择进行划分，现有研究成果主要分为
5、以传感器节点位置为锚点和以传感器网络各区块的重心为锚点两大类 前者通常假设 从充电中心出发，遍历沿途的传感器节点为它们进行一对一式或者一对多式充电，锚点选择在传感器节点的位置上 如 等人以效用最大化为目标，提出了一种一对多有向充电调度方案等人以尽可能降低节点饿死率为目标，提出了基于饥饿避免的在线充电策略，该策略始终选择使其他待充电节点饥饿数最少的传感器节点作为锚点以尽量避免节点陷入能量饥饿状态 等人通过达到某一项性能的最优制定对应的移动充电策略，对低能量的节点进行能量补充 以传感器节点位置为锚点的好处是不用另外寻求合适的位置作为锚点，其缺点主要是由于位置固定可能不是最佳充电位置，并且会增加锚点
6、数量和充电时间为了减少充电时间与提高充电效率，等人提出了采用非均匀分簇的多跳路由协议选择各簇区域的簇头节点并且只对簇头节点进行充电与收集簇内节点的能量信息的调度方案，大大减少了在每个簇区域停留充电的时间从而减少了能耗 等人提出了改进型的 聚类算法，用在网络中选取合适的簇头节点，使得簇头节点能够均匀的分布在网络中，此外还保证了选区的簇头节点更好地兼顾簇内外的平衡 更有 等提出了基于非均匀分簇的无线充电和数据收集算法 通过分析网络中节点能耗和充电车的移动特性，采用蚁群算法求解节点的最佳路由路径，在延长网络寿命的基础上均衡节点能耗，提高网络内能量利用率本文的总体思路是先对中小型 进行非均匀分簇并且以
7、簇区域的圆心作为无人机悬停充电时所处的水平位置，同时以簇区域大小来设置 最佳悬停高度，最后依据簇优先级将区域内的各锚点进行巡游遍历并且找寻最短路径作为规划 此方案考虑的是在中小范围内、无人机能源有限的情况下，如何尽可能地节省路径消耗来提高充电消耗占总功耗的比值问题 比起其他方案，本方案利用网络分簇并借助，既可以减少悬停充电的次数也可以避免与地面障碍物碰撞，大大提高了能量利用率 问题描述和系统模型 问题与方案描述传统的传感器节点一般为电池供电，有限的能量限制了无线传感网的整体寿命 通过无线能量传输技术可以解决这一问题 本文做法是通过分簇并借助 对目标 进行高效充电 假设 从充电中心出发，沿簇优先
8、级顺序直线飞行并在锚点处适时悬停给簇中各节点充能，完成充电任务后返回至充电中心 研究的是在 电量充足、传感器节点随机分布的中小型 中单体 的充电路径优化最后各种实验环境下（包括 的规模、节点的个数和节点的分布情况等方面）进行与、方案对比实验，再从充电周期等方面与、进行对比 网络分簇模型本文的网络分簇模型如图 所示二维平面上的 可以通过改进的 算法进行自适应分簇，此算法首先以一定规则随机产生簇头节点并告知网络此结果，在簇的建立阶段，非簇头节点根据自身与簇头节点的距离来选择加入哪个簇，并告知该簇头 最后形成一图 网络分簇模型 个个簇区域，簇的多少与簇的大小成负相关 本文以簇最外围传感器节点为圆弧切
9、点作一个包括整个簇区域的圆，并且以其圆心作为锚点利用 对每个簇区域内节点进行无线充电 无人机充电空间模型三维空间中的无人机充电网络可以表示为 （，），其中 （，），（，）是无人机无线充电时悬停的位置，用坐标、表示，并称其为锚点、确定地理位置，为无人机悬停高度，为其飞行速度，由此进行合理的能量传输 表示传感器节点的信息，为电池信息，表示其所剩电量的百分比，为传感器所处的地理位置图 无人机充电空间模型 采用二进制数（，）表示网络中传感器节点 能否被 覆盖到 如公式（）所示：（，），（，），（）其中 为最大充电距离，为最大充电范围（这里为一个圆域），为充电半径（，）为传感器距离圆心的距离，为传感器距
10、离无人机的空间距离，另外有向充电器的充电角度用表示 取值为 度 无人机充电空间模型如图所示 无线充电功率当传感器节点处在充电辐射范围内，无人机与地面节点的信道功率增益在时刻 可表示为：，（）其中 表示距离为 时的参考信道功率增益，主要与负载频率和天线增益有关（，）表示 时刻无人机与地面设备的距离 网络中无线能量的传输功率如公式（）所示：，（）式中，为传感器节点接收到的充电功率；为传感器节点与充电器之间的距离；为传输效率；是无人机能量发 小 型 微 型 计 算 机 系 统 年送功率 表示 可实现充电的最远距离 充电工作基本流程图 为 算法的充电流程图 在一次充电工作开始前，会将所有簇的簇头节点按
11、优先级顺序进行规划路径 从 出发按照已规划好的充电路径遍历每个簇进行悬停充电，并收集簇内节点信息 然后判断整个簇的电量是否充满，确定充满后飞至下一处进行同样工作否则继续充电 最图 充电流程图 后结束前检查是否遍历所有的锚点，是的话充电结束，否的话继续遍历直至所有簇区电量充足 文中假设 在新的一轮充电开始时携带充足的量，可满足一次调度中的充电需求和自身消耗，并且 从充电中心出发前已获知待充电节点的位置信息和电量信息 充电路径优化方案 在充电路径优化过程中，关键的 个问题分别为：簇的划分与优先级的描述、飞行高度的确定、飞行路径的选取 簇的划分与优先级的描述在具有 个传感器节点中小型 中，选取（表示
12、可同时充电的最大节点数）个分布均匀的传感器节点作为簇头，将传感器按照与簇头节点的距离大小分类，同一类的形成一个区域称为簇并用 表示 因节点分布不均所以进行的是非均匀分簇，具体过程如算法 所示算法 改进的 聚类分簇算法（）输入：随机的组与其簇头节点集合、初始的 值、传感器节点集合输出：非均匀的簇区域集合 （）（）步骤 中距离度量标准是欧几里得距离的平方：（，）（）（）其中 和 表示不同的两个样本，为 悬停高度，表示样本维度（节点的数量）图 聚类分簇示意 图 为聚类分簇示意图，共有 个传感器节点，采用 聚类算法进行分簇，这里 的取值为，即把 个对象分成 组 圆心作为锚点，边缘传感器与锚点的距离作为
13、覆盖半径，得到 个簇区域 簇 与 为最大簇，灰色的节点为噪声节点 其中簇区域优先级的描述如算法 所示算法 簇优先级描述（）输入：每个节点的初始能量、各簇 所含节点信息、簇优先级划分 输出：每个簇的优先级 ，（）：飞行高度的确定无人机进行充电时，其飞行高度的变化会改变覆盖范围的大小以及充电速率的快慢 由公式（）可知，在覆盖范围内时 与传感器节点之间的距离越远，无线充电的效率大大降低，而距离越近时覆盖的节点越少，因此必然存在合理的高度范围假设无线充电装置的最大覆盖角度为 度，那么当无人机飞行高度 时，其在地面形成的覆盖半径 ，此区域（称为）内所有节点与 的距离在 之间；当无人机飞行高度 时，其在地
14、面形成的覆盖半径 ，此区域（称为）内所有节点与 期 王 杨 等：无人机辅助的无线可充电传感网充电路径规划方案 的距离在 之间，如图 所示图 不同高度下充电覆盖范围 图中两个三角形为相似三角形，可以得到：（）假定充电最大角度为 度，这是在硬件选择时确定的根据三角函数可得：（）充电节点与 的距离最近为，最大为斜边等于，因充电速率与距离的平方成负相关，所以只需考虑边缘节点充电情况 将 ()代入式（），得到：（）（）边缘节点的充电功率为：（）（）式（）中只有 为变量 可以依据每个簇区域充电时间长短作为判断悬停高度合适与否的标准并进行如下计算 时，边缘节点 与 之间的夹角为，（），此 时 充 电 时 间
15、，其中 令，有，由此可以计算出各个高度下的边缘节点充电时间来代表簇充电时间，得到高度与充电时间关系如图 所示图 悬停高度与充电时间关系 从图 可以看出充电时间随悬停高度增加呈指数上升，当 超过 时充电时间为 的 倍以上，此时充电时间已超出所能接受范围，所以最佳高度应不大于 且 ，其中 为簇半径 飞行路径的选取对每个簇优先级进行从高到低排序以此作为初始序列并开始充电，然后采取动态优先级判决算法 对初始序列进行更新直至找到最优路径 将本文所提改进的 聚类分簇算法 和簇优先级描述算法 结合起来，能得到完整的最优充电路径规划（，），算法执行流程如算法 所示算法 基于动态优先级的充电路径规划（）输入：中
16、所有传感器节点集合（包括每个节点位置坐标与剩余能量信息）；输出：最优充电路径 执行 聚类分簇算法，将节点集合 分类为分簇集合 ，并求出锚点集合 ，根据集合 与 得到 给簇区域充电的充电地点 由 算法得到充电顺序关系，先对优先级最高的簇进行充电 执行动态优先级判决算法得到动态的充电路径规划，最终得到最优充电路径 其中 算法详细如算法 所示 动态优先级与簇内紧急节点个数（的节点个数）、相对距离 以及簇初始优先级 有关 这里的，其中 为无人机至簇心的距离，为无人机至其余所有簇心的距离之和 经过模拟实验测试，得到当动态优先级为 时，可以达到充电总时间、充电效率及路径长度的综合最优算法 动态优先级判决算法 输入：簇优先级、锚点 位置信息、位置信息、各簇区域、簇内紧急节点个数 输出：下一个充电锚点位置 （！）、当 给某一节点充电后自动记录，不会重复充电，且对于大面积下的飞行轨迹可以忽略飞行高度进行平面路径规划 路径选择阶段如图 所示 图（）中，锚点 因初始优先级最高被选作第一个悬停充电地点 充电结束前获取 与其它各节点之间的距离，以作为动态优先级进行比较，拥有最高优先级的作为下一个充电地点 计算得
