物联网充电调度算法研究

2023-07-14 18:10张俊琪樊轶铖刘彦松等
计算机应用文摘 2023年12期
关键词:无线充电物联网环境监测

张俊琪 樊轶铖 刘彦松等

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

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

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

1 引言

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

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

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

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

2 技术背景

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

相关研究建议通过让物联网设备从周围环境中收集能量来延长节点寿命,如太阳能、风能等[1~2] 。

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

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

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

3 模型及问题定义

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

3.1 网络模型

考虑部署在一个具体真实环境中的物联网网络,即在一个区域中的重要兴趣点部署物联网设备,从而监测该兴趣点周围的环境数据。例如,物联网设备可用于监测环境中的辐射剂量,或者监测环境的温度和湿度。假设在指定监测区域中有一个基站s,所有充电小车均从此基站出发。同时,部署m 个物联网设备v1,v2,…,vm ,其中m∈N?。设V 为m 个物联网设备所构成的集合,即V ={v1,v2,…,vm }。设备vi 的坐标为(xi ,yi ),其中1≤i≤m。任意2 个物联网设备节点vi 和vj 之间存在1 条边(vi ,vj ),其中1≤i≤m,1≤j≤m 且i≠j,设E 表为所有的边所构成的集合。因此,此物联网可表示为G =(V∪{s},E)。

3.2 无线充电模型

假设共部署K 个移动充电小车为m 个物联网设备充电,其中K 的值是未知的且满足K∈N?。将集合V 划分成K 个不相交的子集V1,V2,…,VK ,其中充电小车k 为子集Vk 中的物联网设备充电,则1≤k≤K。令Vk ={v1,v2,…,vnk },其中nk = |Vk |。用ei 表示集合V 中设备vi 充满电所需的电量。假设每一个充电小车的充电速率均为p,充电效率为α,且充电小车拥有足够电量,其中0<α<1。对于设备vi ,共需花费时间t(vi )= eiαp即可充满电量。最后,令λ 表示充电小车的移动速度。

假设充电小车距离任意一个物联网设备不超过无线充电半径R 即可进行无线充电。令D(vi )表示充电小车可以为设备vi 充电的所有位置集合,则D(vi )= {(x,y) |(x-xi )2 +(y-yi )2 ≤R2},其中(xi ,yi )是设备vi 的坐标。设充电小车k 以v1,v2,…,vnk的顺序为集合Vk 中的设备充电,其中1≤k≤K。充电小车k 进行充电的移动路径Tk 定义如下。充电小车k 从基站s 出发,在集合D(v1 )中的位置l1 为设备v1 充电,接着充电小车前往集合D(v2)中的位置l2 为设备v2 充电,以此类推,直到在集合D(vnk )中的位置lnk为最后一个设备vnk充满电,充电小车此时返回基站s 完成一个充电周期。充电小车k 的充电路径是一个闭合回路Tk =s→l1→l2→…→lnk→s,其中li 是充电小车在集合D(vi )对设备vi 进行无线充电的停靠点,并且1≤k≤K,vnk是集合Vk 中设备的个数。

5 实验

本节针对有邻域情况下单基站充电车最小数量部署问题所提出的算法approAlgOneSinkNei 进行了实验验证,并且本文算法approAlgOneSinkNei 和不考虑邻域的算法approAlgOneSinkNoNei 进行了对比分析,以评估算法性能。

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

本文采用的模拟实验使用Python 语言,并且在1台配置为Inter(R) Core(TM) i7 CPU (2.6 GHz)和32GB RAM 的服务器上运行。所有数据都是在相同网络规模的500 中不同的网络拓扑结构中运行每个算法所得到结果的平均值。

为了评估有邻域情况下单基站充电车最小数量部署问题所提出的算法approAlgOneSinkNei,考虑另一个针对无邻域情况下单基站充电车最小数量部署问题提出的算法approAlgOneSinkNoNei。本文相关数据参考文献[9] 。

从图1 可以看出,在物联网设备数量相同的条件下,算法approAlgOneSinkNei 得到的充电小车数量大大小于算法approAlgOneSinkNoNei 得到的充电小车数量。由于考虑了充电邻域,因此充电小车并不需要前往每一个物联网设备的位置即可进行充电,甚至可以在同一位置为多个物联网设备进行充电。这可以大大减少每一个充电小车充电路径的长度,从而在每一个最大充电时间内可以为更多的物联网设备进行充电,因此可以减少充电小车的部署数量。

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

6 结束语

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

(1)本文研究的物联网网络部署在2D 平面上,可进一步研究在3D 空间物联网网络中的充电车最小数量部署问题。

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

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

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

参考文献:

[1] VOIGT T,RITTER H,SCHILLER J.Utilizing solar power inwireless sensor networks [ C] ∥ Proceedings of the 28thAnnual IEEE International Conference on Local ComputerNetworks,2003:416 – 422.

[2] WANG C, GUO S, YANG Y. Energy?efficient mobile datacollection in energy?harvesting wireless sensor networks[C]∥Proceedings of the 20th IEEE International Conference onParallel and Distributed Systems (ICPADS),2014:55 – 62.

[3] RAHIMI M,SHAH H,SUKHATME G,et al. Studying thefeasibility of energy harvesting in a mobile sensor network[C]∥Proceedings of the 2003 IEEE International Conference onRobotics and Automation,2003:19 – 24.

[4] WANG C,LI J,YE F,et al.Improve charging capability forwireless rechargeable sensor networks using resonant repeaters[C]∥Proceedings of the IEEE 35th International Conferenceon Distributed Computing Systems,2015:133 – 142.

[5] XIE L,SHI Y, HOU Y T, et al. Making Sensor NetworksImmortal:An Energy?Renewal Approach With Wireless PowerTransfer[J]∥IEEE/ ACM Transactions on Networking,2012,20(6):1748?1761.

[6] 刘亮,蒲浩洋.大规模无线传感器网络中高效按需充电规划[J].计算机应用研究,2022,39(1):231?235.

[7] ZHANG Q, XU W,LIANG W,et al.An improved algorithmfor dispatching the minimum number of electric chargingvehicles for wireless sensor networks [ J ] ∥ WirelessNetworks,2018:1?14.

[8] DUMITRESCU A,T?TH C D.The traveling salesman problemfor lines, balls, and planes [ J ]. ACM Transactions onAlgorithms (TALG),2016,12(3):1?29.

[9] ZHANG J,LI Z, XU W, et al. Minimizing the Number ofDeployed UAVs for Delay?bounded Data Collection of IoTDevices[C] ∥ IEEE INFOCOM 2021?IEEE Conference onComputer Communications,2021:33?42.

作者简介:张俊琪(1995—),硕士,助理工程师,研究方向:软件开发与算法设计。

猜你喜欢
无线充电物联网环境监测
环境监测系统的数据分析与处理
大气污染问题的环境监测
解决Qi标准中关于手机无线充电断充的方法
无线充电观赏鱼的设计
基于高职院校物联网技术应用人才培养的思考分析
中国或成“物联网”领军者
对环境监测数据造假必须零容忍
便携式GC-MS在环境监测中的应用
基于QI标准线圈的磁谐振无线充电系统仿真研究