Technology Discussion匕-2021.数据通信
尹玲谢志军(宁波大学信息科学与工程学院浙江宁波315211)
摘要：无线可充电传感器网络(WRSNs)由分布在空间内的若干个无线可充电节点组成，在环境监测、动植物 追踪、健康测等一系列应用场景中广受欢迎，然而节点有限的电池容量成为了大规模部署WRSNs的主要挑战之
一。在各种能量捕获的方法中，无线充电以其充电效率高、充电过程可预测等优在，使得各种无线充电算法成为了 研究热在。根据无线充电器为节点提供能量方式的不同，分别从固定充电方式算法和移动充电方式算法综述了最
近几年无线充电算法的研究现状，并简介了无线充电算法必须要解决的挑战及未来研究方向，以进一步发挥WRSNs的优在推进WRSNs的全球化部署。
关键词：无线可充电传感器网络；能量限制；固定充电；移动充电
0引言
为方便部署与携带，一般无线可充电节点体积较小，携带的能量也较少，加上需要连续运作，能量问题成为研究无线可充电传感器网络(Wireless rechargeable sensor networks,WRSNs)的一大约束与挑战。目前研究能量问题的国内外研究工作主要分为三大类：降低节点能耗、从环境中收集能量以及无线充电。降低能耗的方法虽然能够降低节点单位工作时间的耗能、延长网络的生命周期，但“节流”始终是治标不治本的方法，能量总有耗尽的一天。而“开开”的方法则是指给不断地为节点提供能量，理论上WRSNs便能永久运行；从环境中收集能量即把太阳能、振动能和风能等自然界中存在的能量转换为节点可使用的电能，但环境中能量密度低、能量获取过程不可控且难以预测，实际上上难保证能量收集的质量和时效性；无线充电的方法则是利用无线充电器为WRSNs中的节点补充能量，与其他“开开”的方法相计理论可控、实际可验已经有有多关于无线充电算法的研究，大多数集中在能量给部署和充电路径规划上，以较小的网络代价达到较大的网络效用，实现网络生命周期最大化的超管本文从多个角度综述了目前已有的无线充电算法，总结了相关挑战并指出了未来研究方向&
1无线充电算法
无线充电技术是指WRSNs采用合理的规划方方，使用无充电器为网络中无线可充电节点补充能量。
一般可根据无线充电器的行为和功能把无线充电算法分为两种类型：固定充电方式算法和移动充电方式算法&
12固定充电方式
固定充电方式多适用于节点相距较近且充电信号强度能满足要求的场景，如室内或者某些特定结构环境。此种方式下无线充电器固定在几个位置，有各自的充电半径，可为处于充电半径内的节点补充能量，如下图1所示。
关于固定充电方式的研究一般集中在无线充电器的放置上。文献［1］建立了无线充电器到最远节点距离的数学模型，分析了节点个数与最小充电半径之间的关系，提出一种无无充电器部署策略：根据区域内需要充电的节点的位置，采用最小覆盖圆方法，通过欧式投递男孩算法［2］确定无线充电器的最优放置位置。文献［3%中提出了一种具有优化充电效用的无线充电器
Technooogy Doscussoon
数据通信2021.1
O \ O
一
\°无线¥电"/厂
O
1° '
°「
¥
\O
图1固定充电方式
放置方案：给定固定数量的无线充电器和一组处于平
面上的节点，通过研究无线充电器的摆放位置和方向,
使得所有节点的总体预期充电效用最大化，作者首先 建立网络模型并采用一种支配覆盖集提取方法，得到
有限且离散的图的搜索空间，减少性能损失，最后提出
了一种求解该线性化目标的贪婪算法。文献［4］中同
时考虑无线充电器的位置放置与功率分配(<3 )，以在 二维区域中优化无线充电质量，作者证明了 <3为
NP- Ha/问题并设计了 一个近似算法，给定一组无线
充电器的位置，根据功率预算，到与无线充电器位置
相应的功率分配以最大化充电质量&
与以上研究不同的是，文献［5］中通过共同部署无 线充电器与接收节点，有效减少了总部署成本，但无线
充电器的位置部署和接收节点位置部署之间具有强烈
的耦合性，为了将问题解耦为两个独立子问题并转化
成最大流的问题，文章设计了一种基于贪婪的最大流
算法分别在多项式时间内迭代求解两个子问题，进而
优化了系统性能，达到减少总部署成本的目标。类似
的，文献［6］提出了 WRSNs 中节点部署和无线能量传 输调度的联合问题，通过把问题解耦成节点部署和充
电调度两个子问题，再分别给出解决算法，在无线充电 器提供的能量有限的情况下通过在网络中部署多个彼 此接近的冗余节点，这些节点轮流进行感知和通信进
而节省耗能，理论上节能加上供能就能使网络达到永
久运行的效共
除此之外还有一些工作重点在于提高无线充电的 效益，文献［7］设计了一种多通道能量收集器，用于在 多个WiFi 通道上收集能量，文章成功部署了利用WiFi
为设备充电的系统，证明了 WiFi 在传输数据的同时还 可以携带能量而不会降低网络性能。基于以上发现,
文献［8］采用WiFi 波束成形的方法为节点补充能量,
通过改变发射机与接收机天线设置进而改变WiFi 在 各个方向上的信号强度，证明了 WiFi 波束成形技术可
以有效提高能量传输效率。文献［9］设计了一种两步
走双通道能量请求策略! Dual tunnS energy requesting ,
DTER )：第一步计算节点上最优传输速率分布，以最小
化传输数据的能耗，第二步提出一种启发式算法，将节
点的能量请求调度转换为最短路径问题并采用动态规
划算法(Dynamic p/g/mming )来出全局最优解，使
待充电节点能够以最小的能耗从无线充电器中获取
能量。
1.2移动充电方式
当WRSNs 中的节点之间相距较远，其通信距离远 大于充电距离时，选用移动充电方式则更方便接近节
点为其补充能量。这种方式下的研究重点则在于如何
规戈1J 移动充电器! Mobile charger , MC )的行程路径与充
电时间，在满足全部节点能量需求前提下，使需要的
MC 个数最少、充电开销最小。一般可按网络范围大小
采用单个MC 为WRSNs 中的节点补充能量，这方
乐谱架面工作的研究重点在于合理规划MC 的充电路径与充
电时间，使得网络效用最大化或充电代价最小化。文
献［10］中提出了 MC 的预先行程规划与充电关联的问 题(Itinera/ selection and charging association , ISCA ): 给定一组待充电节点和一组MC 候选充电行程，在满
足所有待充电节点的能量需求的情况下尽量减少由于
MC 移动和无线充电引起的能量消耗，文章首先针对致
种MC 行程只能使用一次的情况提出了一种实用启发
式算法，最后提出了一种原对偶模式算法用于行程可
多次使用的一般情况。类似在文献［11］中，目标也是
共同优化MC 的行程规划与充电调度，作者应用马尔 可夫决策过路优化MC 每个时间段行进的路径以及
待充电的节点子集。
Technology Discussion 2021!数据通信
为提咼充电效率，文文［12%首次提出节点的定向放置和MC充电调度策略的联合优化，文章把原优化问题描述为一般凸优化问题：利用区域划分和充电功率离散的方法在划分的网格上构造有限个虚拟节点，当MC的行进路径与网格相交时，网格内所有节点将成功被充电,MC使用近邻规则来访问这些网格，并使用迭代算法进一步缩短MC的行进路径。类似的，有学者发现无线可充电节点具有各向异性能量接收特性，即节点的充电效率不仅取决于MC与节点之间的距离，还与MC和节点之间的角度有关,MC的全向充电方式更容易导致能量浪费。文献［13］实现了如图3所示的MC定向充电的方法，首次建立能量随距离与角度变化的模型，并证明了节点接收的能量随MC与节点之间的距离和角度显著变化。
MC
图3定向充电
女口图所示,A e?是节点的有效接收区域，A"是MC 的有效传输区域，当MC正对节点时（夹角为0", A6A"，当MC与节点夹角为'时，A6A-c asi 二A-"casa，可见当MC与节点正对时传输效率最大。文章基于此现象提出时延最小化问题（Minonal charging delay,MAD"，目标是最小化网络中所有节点的总充电时延，先把目标转化为线性规划问题寻求最优充电方向角，然后采用合并方向角的方法进一步减少搜索空间，降低I十算复杂度&
多MC移动充电
液晶显示器反光采用多个MC为WRSNs中的节点补充能量，指的是多个MC协同合作满足所有节点的能量需求，这方面的研究工作重点在于最小化充电代价，包括最小化MC数量或者最大化MC充电效率。文献［14］提出了一种有效的多MC充电调度算法，用于在大规模WRSNs中调度多个MC为长期监测的节点周期性充电，在满足所有节点的能量需求下，所有MC的移动总行程最小，由于目标问题是NP-Hard问题，文章首先设计了一种近似算法用来解决节点的最大充电周期是固定的情况；接下来分析了最大充电周期不固定的情况，并修改近似算法，开发了一种新的启发式算法。文献［15］则考虑了一种多目标联合优化问题：最大限度提高能量使用效率与节点存活率，文章提出一种全新的联合考虑时间与空间的充电调度策略!Temporal and Spatial coyaborative Charging,mTS"：首先使用K-means算法把传感区域划分成多个簇，每个簇放置一个MC用于处理来自簇内的充电请求，节点发出的充电请求包括时、空两种信息：节点的截止充电时间（充电请求超过截止时间没有被接收则该节点进入休眠状态）、节点
空间位置。mTS将时间优先级与空间优先级组合成一个混合优先级&
时间优先级:
入；2〉（,
入；讥i)6
空间优先级:
[("-+丨>]
[(2-21)|>]
2+-d J_」
(1"
(2"混合优先级！
#（m）（i）二'#"（,7g（#c（,d+1）
（3"
其中N是节点个数，表示最早任务的到达时间、间+表示最新任务的到达时间，d表示第i个节点跟第j个MC之间的距离，d-表示最近节点的距离、d+表示最远节点的距离;MC计算节点的混合优先级，优先为混合优先级高的节点充电。文献［6］则考虑了节能耗不均衡以及MC充电效率会随时间变化而衰减的问题，提出了基于不均匀集的移动充电算法（uneven clustee-based mobile charging,UCMC）以解决上述问题，算法分为三步：1）网络不均匀聚类2）MC充电路径规划;3）能量中继，通过聚类将网络划分成多个簇，选出簇头后,MC每次都移动到簇头附近为簇中所有能量低于阈值的节点充电，当有节点完全充电后它将充当中继节点把能量从MC传输给其他需要充电的节点。
由上述分析可知无线充电技术的发展使得WRSNs理论上可以永久运行，前提是MC的能量不会枯竭，为了彻底摆脱电力束缚，有学者研究了环境能源收集与无线充电相结合的工作，提出了具有多源能量收集与无线充电的WRSNs。文献［17］提出了一种新的框架用来实现多源能量收集的自我可持续传感器网络，文章分为三步来实现所提框架：首先研究了最优的
Technooogy Doscussoon数据通信2021.1
不同类型节点组合问题，使WRSNs的部署成本最低；然后根据环境能源的分布和MC的移动成本研究的部署问题；最后提出一种近似算法来规划MC的行程，以满足每个网格中尽可能多的充电请求，并就近选择为MC自身补充能量&
2挑战与未来研究方向
虽然WRSNs的充电规划问题已经得到广泛而深入的研究，但仍有一些问题值得我们去思考。如文献［18%考虑了节点由于过充而造成能量溢出浪费问题，提出了避免节点过充的算法；文献［19］提出的拒绝充电攻击，当网络中存在恶意节点发出非法充电请求时，将破坏网络功能和可靠性；文献［20］中为了避免充电与通信的冲突，设计了合适的信息与能量同时传送的算法。这些问题在相应的所提解决算法下得到了致定程度的缓解，但都没有完美解决，还需要进一步的探讨与研究&
3结束语
本文主要介绍WRSNs的无线充电算法，按照适用场景不同将其划分为固定充电方式算法与移动充电方式算法。固定充电方式适用于各节点之间相距较近的情况，如室内或者特殊结构环境下，此种方式下的研究重点在于无线充电器的位置部署上；移动充电方式适用于节点的通信距离远大于充电距离的
情况，如户外 监测，此种方式下的研究重点在于最大化网络效用或者最小化移动充电器的移动成本。文章的最后还介绍了当前无充电算法所面临的挑战，相信随着研究的深入与硬件的发展，无线充电算法终将克服困难，使WRSNs能够大规模广范围部署，充分发挥作用&
参考文献
[1]王志方，郑霖，李晓记.无线可充电传感器网质中充电器
的部署优化[J].计算机工程，2018,44(5):83-87,93 [2]Hearn JEW.GeometEcal Solutions for Some Mininiax
Location Problems[J].T/nspoi/gon Science,1972,6
(4):379-394
[3]Dai H,Wang X,Lin AX,e£Optimizing wireless charger
placement for directioncl charging[C]//IEEE INFOCOM
2017-IEEE Conference on Computer Communications,
2017:1-9[4]Zhang S,Qian Z,Kong F,e£al.P3:Joint optimizaVon of
charger placement and power VlocaVon for wii/es s power Eansfe/C]//IEEE INFOCOM2015-IEEE Conferencc on Compuie@Communocaioons,2015:2344-2352
智能电表芯片[5]Li S,Fu L,He S,e£al Necc-OpOmcl Co-Deployment of
Chargers and Sink Stations in Rechargeable Sensor Networks [J].ACM Traysaceons on Embedded CompuEng Systems, 2017,17(1):1-19
[6]Du R,Xiao M,Carlo F.OpOmal Node Deployment and Energy
Provision for Wirelessle Powered Sensor Networks[J].IEEE Jou@naeon Seeecied Aeason Communocaioons,2019,37(2): 407-423
[7]Talla V,Kellogg B,Ransfo/B,et al.Powering ie next Billion
devices with Wi-Fi[C]//Commun.ACM,2017：83-91
[8]T/n V,Mis/A,Xiong J,ee al Can WiFi Beagifbi/ing
Support an Energy-Harvesting Wea/ble?[ C]//The Fibh ACM EnieenaioonaeWoekshop,2017:14-20
[9]Luo Y,Pu L,Zhao Y,e"al Ophmol energy/quesing sEategy
eoeRF-based eneeg[haevesiongwoeeee s communocaioons
[C]//EEEE Coneeeence on Compuiee Communocaioons,
2017:1-9
[10] Zhang S,Qian Z,Wu J,e"a/.Optimizing Itinera/Selection
and Charging AssociaVon for Mobile Chargers[J].IEEE Teansacioonson MoboeeCompuiong,2017,16(10):2833-2846 [11]Fahira S,Yong X,Dusil N,e"a/.Mobile Char/ng in
Woeeee s-Poweeed SensoeNeiwoeks:OpiomaeSchedueongand EtpeeomeniaeEmpeemeniaioon[J].EEEE Teansacioons on VehocueaeTechnoeogy,2017,66(8):7400-7410
[12]Wu T,Yang P,Doi H P,e"al Cha/ing Oriented Sensor
Peacemeniand FeetobeeSchedueongon RechaegeabeeWSNs
[C]//EEEEENFOCOM2019-EEEEConeeeenceon Compuiee
Communocaioons,2019:73-81
[13]Lon C,Zhou Y,MaF,e al.MonomoiongChaegongDeeayeoe
Directionvl Charging in Wireless Rechargeable Sensor Neiwoeks[C]//EEEEENFOCOM2019-EEEEConeeeenceon CompuieeCommunocaioons,2019:1819-1827
[14]Xu W,Liang W,Lin X,et al Efficient Scheduling of Multiple
MoboeeChaegees oe Woeeee s Sensoe Neiwoeks[J].EEEE T/vsactiono on Vehicular Technology,2016,65(9) ：7670-7683 [15]Lon C,WangZ,DengJ,e al.mTS:Tempoae-and Spaioae-
Collaborative Charging for Wireless Rechargeable Sensor N3iwoekswoih MueiopeV3hoces[C]//EEEE ENFOCOM2018
-EEEE Coneenc3on Compuie Communocaioons, 2018：99-107
[16]Han,GJ,Guan,HF,Wu JW,e al.An Un3e3n Ceusie-
Bas3d Moboe ChaegongAegoeoihm eoeWoee s R3chaeg3abe
Technology Discussion匕-2021!数据通信
Sensoe Networks$ J%.IEEE Systems Jouml,2019,13(4)：3747-3758
有筋网
$17%Zhou P Z,Wang C,Yang Y Y.Self-sustenable Sensoe Neeoooksooeh Mueeo-souoceEneogyHaoeeseongand Wooeee s ChxWng$C%// IEEE IDFOCOM2019-IEEE Conferencc on Computer Communications,2019：1828-1836
$18%应岚，林一民，池凯凯.能量捕获无线传感器网络能耗感知的路由方案[J%.计计机工程，2016(2)：108-112
$19%Lin C,Shang Z,Du W,e+al.CoDoC：A Novel Attack foe Wooeee s Rechaogeabee SensooNeeoooksehoough Denoaeoe
Charaa$C%//IEEE IDFOCOM2019-IEEE Conferencc on Computer Communicagons,2019：856-864
$20%KhlfCt N,Perlazz S M.Sonultaneous Informagon and Energy Transmission in the Two-User Gaussian InwWerencc Channel $J%.IEEE Journt on Selected Areas in Communications, 2019,37(1):156-170
作者简介：尹玲(1996-)，女，安徽铜陵人，宁波大学信息科学与工程学院硕士研究生，主要研究方向为能量捕获、无线体域网#■隧道喷浆
(上接第32页)
$5%Wang C L,Ding Y,Wang Z'Design and implemenWXon of mu6-agent neevork managementmodel based on RDF$J%.
Computer Engineeeng&Design,2006
$6%Jiang X,Tan A H.OntoSearch：A Full-Text Search Engine foe the Senianeo Web.$C%//Nagont Conferencc on Artmmm 146X6640and the Eighteenth Innovative Applicagons of ^00x1Intehigence Conference,July16-20,2006,Boston, Ma s achus3e s,Usa.DBLP,2006：1325-1330
$7%Cheng G,Qu Y.Sexching linked objects with Ocons：Approach,implementaXon and evXuaXoc[ntemaXonX JourncI on SemanUo Web and110:)011X04Systemo,2009,5(3)：49-70 $8%
Chirim P A,CosUche S,Nejdl W,et al P-TAG:larae oXe automatic generaXon of peoonaOzed annotation Uys foe We web$C%//of We,Inti.WorU Wide Web Conf.2007：845-854 $9%马浩洋.裁判文书信息提取-l/DI■bugk^llem caopanwenshu/,2020.6.10
$10%TaoQo,Chuhan Wu,FangzhaoWu,Suyu Ge,Junton Lou, Yongeng Huang,Xing Xie:Fast NeuaO Chinese Named Eneoey Recognoeoon woeh Mueeo-head Seeea e eneoon.CCKS 2019：98-110
$11%Chen F,HuangY.Knoweedge-enhanced neuaaeneewoakseoa seneomeneanaeysosoeChoneseaeeoews$J%INeuaocompueong,
2019,368：51-58
$12%Husaon M F,McG eo eh eon JP,Masud MM e"al.Heuaoseocs-based quea pocessing for lxge RDF graphs using cloud computing $J%.IEEE Transactions on Knodedge and DaW Enyneering, 2011,23(9):1312-1327
$13%Zhang X,Chen L,Wang M.TowaOs efficient join pocessing oeeaeaageRDFgaaph usongMapReduce$C%//Paoceedongsoe the28W11600X04x1Conference on Scientido and S w X s C c X Da eabase Managemen eINew Yo ak：ACM,2012：250-259
$14%ZengK,YangJ,WangH e"al.Adoseaobueed gaaph engoneeoa web scXe RDF daW$J%.Pmceedingsof We VLDB,
2013,6(4)：265-276
$15%Apache.Paaquee$OL%I$ 2016-10-6%h e p：//paaqueeI apache.oag/
军用伪装网作者简介：梁鸿翔(1981-)，中国航天科工集团第二研究院，硕士，高级工程师，研究方向：计算法学、知识服务、数据挖掘；E-mail：superlianghx@163；吴肇良(1992-)，中国传媒大学人工智能系，博士研究生，研究方向：人工智能，文本处理，网络媒体分析；杨帅(1993-)，中国航天科工集团第二研究院，硕士，研究方向：知识服务、空间网络#E-mil：704458638@ qq!
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议