物联网充电调度算法研究

张俊琪 樊轶铖 刘彦松等

摘要：近年来，物联网技术飞速发展．物联网被广泛应用于环境监测、三维建模、智慧城市、目标跟踪、数据收集等场景中。在物联网的应用场景中，物联网设备的电量一直是人们关注的焦点。通常情况下．物联网设备的电量若得不到及时补充．将很快失去工作能力。比如，在检测火灾的森林场景中．如果物联网失去工作能力，后果将不堪设想。在传统的物联网网络中，通常为物联网设备安装太阳能充电电池来保证物联网设备持续工作，但是此方法受天气和时间的影响，物联网设备往往不能获得足够的阳光，从而导致电量补充不足的问题。因此，采用移动迅速的无线充电小车为物联网设备补充电量是一种理想的方式。文章阐述了在单基站场景中部署最小数量的无线充电小车并提出它们充电路径的问题。同时，在考虑了无线充电范围（即邻域）的情况下，提出了算法approAlgOncSinkNci。实验表明，对比不考虑邻域的算法approAlgOncSinkNoNci，该算法所得到的充电小车数量大大减少。

关键词：物联网；环境监测；无线充电；充电调度

中图法分类号：TP391 文献标识码：A

１ 引言

物联网（Ｉｎｔｅｒｎｅｔ ｏｆ Ｔｈｉｎｇｓ，ＩｏＴ）是指将各种设备、服务、应用通过网络连接和交互。它实现了各种设备（如手机、车辆、传感器等）之间无缝互联，使不同类型的设备能够相互通信，彼此传递数据。物联网让更多的传感器设备、系统和应用通过互联网连接在一起，从而实现智能家居、智能交通系统等，进而提高生活和工作的效率，为人们提供更加个性化的服务。如今，物联网被应用于环境监测、三维建模、智慧城市、目标跟踪、数据收集等场景中，因此如何持续保证物联网的正常工作是一个至关重要的问题。

针对物联网网络中的无线充电问题（如应用在一个具体监测场景中的物联网网络），为了使物联网网络中的节点随时保持足够的电量正常工作，需要采取高效的方式为物联网网络进行充电。基于此，可以考虑部署多个轻量的无线充电小车为物联网中的设备进行充电，每一个无线充电小车都可以停在离物联网设备较近的某个位置进行无线充电，从而保证物联网网络持续工作。

为了确保充电的高效性，规定每一個充电小车在充电途中所消耗的总时间不超过给定的最大充电时间，其中总时间包括充电小车的移动时间和充电时间。否则，不能保证所有的物联网设备都能得到及时充电。

本文研究了一个新颖的有邻域情况下单基站充电车最小数量部署问题，即确定最小数量的无线充电小车为物联网网络充电，其中充电小车在距离物联网设备一定范围就可以进行无线充电，同时确定每一个充电小车的充电路径，并保证每个充电小车所消耗的总时间不超过最大充电时间，每一个充电小车均从基站出发，最后再回到基站，而且每一个物联网设备都必须被其中一个无线充电小车所充电。为了解决此问题，本文首先提出网络模型和无线充电模型；其次定义有邻域情况下单基站充电车最小数量部署问题；再次提出算法；最后通过在多个模拟数据集上进行仿真实验，并且与已有的算法进行比较，以评估本文算法的性能。

２ 技术背景

物联网网络充电技术是随着物联网设备的发展而兴起的一种技术，主要目的是应对物联网网络中能量管理的挑战。由于物联网设备节点具有体积小和易碎性等特点，因此限制了物联网网络中能量消耗的有效性及其网络寿命。因此，如何实现物联网节点的能量管理并延长物联网网络的寿命成为提升物联网网络有效性的一项至关重要的任务。

相关研究建议通过让物联网设备从周围环境中收集能量来延长节点寿命，如太阳能、风能等［１～２］ 。

然而，由于周围环境的动态变化，物联网设备的能量收集率低且不稳定。例如，相关研究表明，太阳能收集系统在晴天、阴天和雨天的能量产生率可能相差多达３ 个数量级［３］ 。这种不可推断性和间断性对有效利用收集的能量进行各种监测任务提出了挑战。

有研究人员提出了一种创新性的物联网设备电量补充方法［４～５］ ，即将配备具有无线充电功能的小车移动到电量即将耗尽的物联网设备附近，并通过无线能量传输为其充电［６］ 。相较于物联网设备从周围采集能量的方式，该方法的充电效率高且稳定。

部分文献研究了最小数量充电车部署问题，但是这些研究没有考虑邻域条件［７］ 。在实际应用场景中，无线充电小车往往不需要贴近物联网设备就能进行充电。因此，本文考虑在有邻域条件下部署最小数量的充电车为物联网设备进行充电。

３ 模型及问题定义

在网络模型中，本文给出了网络中设备和基站的分布情况。在无线充电模型中，本文描述了无线充电小车如何对每一个物联网设备进行充电，从而保证物联网设备正常工作。在问题定义中，本文用数学语言定义了有邻域情况下单基站充电车最小数量部署问题。

３．１ 网络模型

考虑部署在一个具体真实环境中的物联网网络，即在一个区域中的重要兴趣点部署物联网设备，从而监测该兴趣点周围的环境数据。例如，物联网设备可用于监测环境中的辐射剂量，或者监测环境的温度和湿度。假设在指定监测区域中有一个基站ｓ，所有充电小车均从此基站出发。同时，部署ｍ 个物联网设备ｖ１，ｖ２，…，ｖｍ ，其中ｍ∈Ｎ?。设Ｖ 为ｍ 个物联网设备所构成的集合，即Ｖ ＝｛ｖ１，ｖ２，…，ｖｍ ｝。设备ｖｉ 的坐标为（ｘｉ ，ｙｉ ），其中１≤ｉ≤ｍ。任意２ 个物联网设备节点ｖｉ 和ｖｊ 之间存在１ 条边（ｖｉ ，ｖｊ ），其中１≤ｉ≤ｍ，１≤ｊ≤ｍ 且ｉ≠ｊ，设Ｅ 表为所有的边所构成的集合。因此，此物联网可表示为Ｇ ＝（Ｖ∪｛ｓ｝，Ｅ）。

３．２ 无线充电模型

假设共部署Ｋ 个移动充电小车为ｍ 个物联网设备充电，其中Ｋ 的值是未知的且满足Ｋ∈Ｎ?。将集合Ｖ 划分成Ｋ 个不相交的子集Ｖ１，Ｖ２，…，ＶＫ ，其中充电小车ｋ 为子集Ｖｋ 中的物联网设备充电，则１≤ｋ≤Ｋ。令Ｖｋ ＝｛ｖ１，ｖ２，…，ｖｎｋ ｝，其中ｎｋ ＝ ｜Ｖｋ ｜。用ｅｉ 表示集合Ｖ 中设备ｖｉ 充满电所需的电量。假设每一个充电小车的充电速率均为ｐ，充电效率为α，且充电小车拥有足够电量，其中０＜α＜１。对于设备ｖｉ ，共需花费时间ｔ（ｖｉ ）＝ ｅｉαｐ即可充满电量。最后，令λ 表示充电小车的移动速度。

假设充电小车距离任意一个物联网设备不超过无线充电半径Ｒ 即可进行无线充电。令Ｄ（ｖｉ ）表示充电小车可以为设备ｖｉ 充电的所有位置集合，则Ｄ（ｖｉ ）＝ ｛（ｘ，ｙ） ｜（ｘ－ｘｉ ）２ ＋（ｙ－ｙｉ ）２ ≤Ｒ２｝，其中（ｘｉ ，ｙｉ ）是设备ｖｉ 的坐标。设充电小车ｋ 以ｖ１，ｖ２，…，ｖｎｋ的顺序为集合Ｖｋ 中的设备充电，其中１≤ｋ≤Ｋ。充电小车ｋ 进行充电的移动路径Ｔｋ 定义如下。充电小车ｋ 从基站ｓ 出发，在集合Ｄ（ｖ１ ）中的位置ｌ１ 为设备ｖ１ 充电，接着充电小车前往集合Ｄ（ｖ２）中的位置ｌ２ 为设备ｖ２ 充电，以此类推，直到在集合Ｄ（ｖｎｋ ）中的位置ｌｎｋ为最后一个设备ｖｎｋ充满电，充电小车此时返回基站ｓ 完成一个充电周期。充电小车ｋ 的充电路径是一个闭合回路Ｔｋ ＝ｓ→ｌ１→ｌ２→…→ｌｎｋ→ｓ，其中ｌｉ 是充电小车在集合Ｄ（ｖｉ ）对设备ｖｉ 进行无线充电的停靠点，并且１≤ｋ≤Ｋ，ｖｎｋ是集合Ｖｋ 中设备的个数。

５ 实验

本节针对有邻域情况下单基站充电车最小数量部署问题所提出的算法ａｐｐｒｏＡｌｇＯｎｅＳｉｎｋＮｅｉ 进行了实验验证，并且本文算法ａｐｐｒｏＡｌｇＯｎｅＳｉｎｋＮｅｉ 和不考虑邻域的算法ａｐｐｒｏＡｌｇＯｎｅＳｉｎｋＮｏＮｅｉ 进行了对比分析，以评估算法性能。

由于本文研究的问题是在物联网网络中部署最小数量满足充电时间不超过最大充电时间的充电小车为物联网网络充电，因此需要部署充电小车的数量是评估本文算法的重要指标。

本文采用的模拟实验使用Ｐｙｔｈｏｎ 语言，并且在１台配置为Ｉｎｔｅｒ（Ｒ） Ｃｏｒｅ（ＴＭ） ｉ７ ＣＰＵ （２．６ ＧＨｚ）和３２ＧＢ ＲＡＭ 的服务器上运行。所有数据都是在相同网络规模的５００ 中不同的网络拓扑结构中运行每个算法所得到结果的平均值。

为了评估有邻域情况下单基站充电车最小数量部署问题所提出的算法ａｐｐｒｏＡｌｇＯｎｅＳｉｎｋＮｅｉ，考虑另一个针对无邻域情况下单基站充电车最小数量部署问题提出的算法ａｐｐｒｏＡｌｇＯｎｅＳｉｎｋＮｏＮｅｉ。本文相关数据参考文献［９］ 。

从图１ 可以看出，在物联网设备数量相同的条件下，算法ａｐｐｒｏＡｌｇＯｎｅＳｉｎｋＮｅｉ 得到的充电小车数量大大小于算法ａｐｐｒｏＡｌｇＯｎｅＳｉｎｋＮｏＮｅｉ 得到的充电小车数量。由于考虑了充电邻域，因此充电小车并不需要前往每一个物联网设备的位置即可进行充电，甚至可以在同一位置为多个物联网设备进行充电。这可以大大减少每一个充电小车充电路径的长度，从而在每一个最大充电时间内可以为更多的物联网设备进行充电，因此可以减少充电小车的部署数量。

另外，随着物联网中物联网设备数量的增多，２ 种算法得到的需部署的充电小车的数量也在增加，这是因为需要部署更多数量的充电小车才能维持更大规模联网网络的正常工作。

６ 结束语

部署移动充电小车为物联网网络中的设备进行无线充电已经是一种通用方法，优秀的充电调度算法不断产生，能够更加高效地为更多物联网设备进行合理充电，降低充电成本。

（１）本文研究的物联网网络部署在２Ｄ 平面上，可进一步研究在３Ｄ 空间物联网网络中的充电车最小数量部署问题。

（２）在本文研究的基础上，可以考虑充电小车自身电量有限的情况。在这种情况下，需要更加严格规划小车的路径，使小车在能量耗尽前返回基站补充电量。

（ ３）本文仅仅考虑了一个基站的情况，在具体的应用场景中，出发点可能不唯一，因此可进一步考虑多基站条件下的物联网无线充电调度问题。

（４）本文所探究的物联网网络中所有节点位置中的电量都是已知的，可进一步研究节点信息是未知的情况。

参考文献：

［１］ ＶＯＩＧＴ Ｔ，ＲＩＴＴＥＲ Ｈ，ＳＣＨＩＬＬＥＲ Ｊ．Ｕｔｉｌｉｚｉｎｇ ｓｏｌａｒ ｐｏｗｅｒ ｉｎｗｉｒｅｌｅｓｓ ｓｅｎｓｏｒ ｎｅｔｗｏｒｋｓ ［ Ｃ］ ∥ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ２８ｔｈＡｎｎｕａｌ ＩＥＥＥ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｌｏｃａｌ ＣｏｍｐｕｔｅｒＮｅｔｗｏｒｋｓ，２００３：４１６ – ４２２．

［２］ ＷＡＮＧ Ｃ， ＧＵＯ Ｓ， ＹＡＮＧ Ｙ． Ｅｎｅｒｇｙ?ｅｆｆｉｃｉｅｎｔ ｍｏｂｉｌｅ ｄａｔａｃｏｌｌｅｃｔｉｏｎ ｉｎ ｅｎｅｒｇｙ?ｈａｒｖｅｓｔｉｎｇ ｗｉｒｅｌｅｓｓ ｓｅｎｓｏｒ ｎｅｔｗｏｒｋｓ［Ｃ］∥Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ２０ｔｈ ＩＥＥＥ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎＰａｒａｌｌｅｌ ａｎｄ Ｄｉｓｔｒｉｂｕｔｅｄ Ｓｙｓｔｅｍｓ （ＩＣＰＡＤＳ），２０１４：５５ – ６２．

［３］ ＲＡＨＩＭＩ Ｍ，ＳＨＡＨ Ｈ，ＳＵＫＨＡＴＭＥ Ｇ，ｅｔ ａｌ． Ｓｔｕｄｙｉｎｇ ｔｈｅｆｅａｓｉｂｉｌｉｔｙ ｏｆ ｅｎｅｒｇｙ ｈａｒｖｅｓｔｉｎｇ ｉｎ ａ ｍｏｂｉｌｅ ｓｅｎｓｏｒ ｎｅｔｗｏｒｋ［Ｃ］∥Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ２００３ ＩＥＥＥ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎＲｏｂｏｔｉｃｓ ａｎｄ Ａｕｔｏｍａｔｉｏｎ，２００３：１９ – ２４．

［４］ ＷＡＮＧ Ｃ，ＬＩ Ｊ，ＹＥ Ｆ，ｅｔ ａｌ．Ｉｍｐｒｏｖｅ ｃｈａｒｇｉｎｇ ｃａｐａｂｉｌｉｔｙ ｆｏｒｗｉｒｅｌｅｓｓ ｒｅｃｈａｒｇｅａｂｌｅ ｓｅｎｓｏｒ ｎｅｔｗｏｒｋｓ ｕｓｉｎｇ ｒｅｓｏｎａｎｔ ｒｅｐｅａｔｅｒｓ［Ｃ］∥Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ＩＥＥＥ ３５ｔｈ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅｏｎ Ｄｉｓｔｒｉｂｕｔｅｄ Ｃｏｍｐｕｔｉｎｇ Ｓｙｓｔｅｍｓ，２０１５：１３３ – １４２．

［５］ ＸＩＥ Ｌ，ＳＨＩ Ｙ， ＨＯＵ Ｙ Ｔ， ｅｔ ａｌ． Ｍａｋｉｎｇ Ｓｅｎｓｏｒ ＮｅｔｗｏｒｋｓＩｍｍｏｒｔａｌ：Ａｎ Ｅｎｅｒｇｙ?Ｒｅｎｅｗａｌ Ａｐｐｒｏａｃｈ Ｗｉｔｈ Ｗｉｒｅｌｅｓｓ ＰｏｗｅｒＴｒａｎｓｆｅｒ［Ｊ］∥ＩＥＥＥ／ ＡＣＭ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｎｅｔｗｏｒｋｉｎｇ，２０１２，２０（６）：１７４８?１７６１．

［６］ 刘亮，蒲浩洋．大规模无线传感器网络中高效按需充电规划［Ｊ］．计算机应用研究，２０２２，３９（１）：２３１?２３５．

［７］ ＺＨＡＮＧ Ｑ， ＸＵ Ｗ，ＬＩＡＮＧ Ｗ，ｅｔ ａｌ．Ａｎ ｉｍｐｒｏｖｅｄ ａｌｇｏｒｉｔｈｍｆｏｒ ｄｉｓｐａｔｃｈｉｎｇ ｔｈｅ ｍｉｎｉｍｕｍ ｎｕｍｂｅｒ ｏｆ ｅｌｅｃｔｒｉｃ ｃｈａｒｇｉｎｇｖｅｈｉｃｌｅｓ ｆｏｒ ｗｉｒｅｌｅｓｓ ｓｅｎｓｏｒ ｎｅｔｗｏｒｋｓ ［ Ｊ ］ ∥ ＷｉｒｅｌｅｓｓＮｅｔｗｏｒｋｓ，２０１８：１?１４．

［８］ ＤＵＭＩＴＲＥＳＣＵ Ａ，Ｔ?ＴＨ Ｃ Ｄ．Ｔｈｅ ｔｒａｖｅｌｉｎｇ ｓａｌｅｓｍａｎ ｐｒｏｂｌｅｍｆｏｒ ｌｉｎｅｓ， ｂａｌｌｓ， ａｎｄ ｐｌａｎｅｓ ［ Ｊ ］． ＡＣＭ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎＡｌｇｏｒｉｔｈｍｓ （ＴＡＬＧ），２０１６，１２（３）：１?２９．

［９］ ＺＨＡＮＧ Ｊ，ＬＩ Ｚ， ＸＵ Ｗ， ｅｔ ａｌ． Ｍｉｎｉｍｉｚｉｎｇ ｔｈｅ Ｎｕｍｂｅｒ ｏｆＤｅｐｌｏｙｅｄ ＵＡＶｓ ｆｏｒ Ｄｅｌａｙ?ｂｏｕｎｄｅｄ Ｄａｔａ Ｃｏｌｌｅｃｔｉｏｎ ｏｆ ＩｏＴＤｅｖｉｃｅｓ［Ｃ］ ∥ ＩＥＥＥ ＩＮＦＯＣＯＭ ２０２１?ＩＥＥＥ Ｃｏｎｆｅｒｅｎｃｅ ｏｎＣｏｍｐｕｔｅｒ Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ，２０２１：３３?４２．

作者简介：张俊琪（１９９５—），硕士，助理工程师，研究方向：软件开发与算法设计。