大規(guī)模無(wú)線傳感器網(wǎng)絡(luò)中高效按需充電規(guī)劃

摘 要： 隨著無(wú)線充電技術(shù)的日趨成熟，特別是磁共振無(wú)線充電技術(shù)的發(fā)展，利用移動(dòng)充電車和無(wú)線充電技術(shù)給無(wú)線傳感器補(bǔ)充能量，以保證無(wú)線傳感器網(wǎng)絡(luò)持續(xù)運(yùn)轉(zhuǎn)，成為新的研究熱點(diǎn)。為此，主要介紹在大規(guī)模的無(wú)線傳感器網(wǎng)絡(luò)中，如何調(diào)度多個(gè)充電車給網(wǎng)絡(luò)中的待充電傳感器補(bǔ)充能量。為了均衡多個(gè)充電車的充電任務(wù)，縮小整個(gè)充電任務(wù)的完成時(shí)間，提出了充電總耗時(shí)最短問(wèn)題，希望能為多個(gè)充電車找到各自的充電路徑，使得多個(gè)充電車中耗時(shí)最長(zhǎng)的任務(wù)完成時(shí)間最短。因?yàn)槌潆娍偤臅r(shí)最短問(wèn)題是一個(gè)NP難問(wèn)題，難以在多項(xiàng)式時(shí)間內(nèi)找到最優(yōu)解，所以針對(duì)該問(wèn)題提出了一個(gè)近似比為5的近似算法。最后用模擬實(shí)驗(yàn)證明了算法的性能，實(shí)驗(yàn)表明該算法的實(shí)際近似比不足2。

關(guān)鍵詞： 無(wú)線傳感器網(wǎng)絡(luò)； 磁共振無(wú)線充電； 按需充電； 大規(guī)模網(wǎng)絡(luò)； 任務(wù)完成時(shí)間最短

中圖分類號(hào)： TP393"" 文獻(xiàn)標(biāo)志碼： A

文章編號(hào)： 1001-3695（2022）01-040-0231-05

doi：10.19734/j.issn.1001-3695.2021.05.0227

Efficient on-demand charging scheduling in large scale wireless sensor networks

Liu Liang， Pu Haoyang

（School of Cyber Science amp; Engineering， Sichuan University， Chengdu 610207， China）

Abstract： With the increasing maturity of wireless charging technology， especially the development of magnetic resonance wireless charging technology， the employment of mobile charging vehicles and wireless charging technology to replenish sensors’ energy to ensure the continuous operation of wireless sensor networks has become a new research hotspot. This paper focused on how to schedule multiple charging vehicles to replenish energy to the sensors in a large-scale wireless sensor network. In order to balance the charging tasks of multiple charging vehicles and reduce the completion time of the whole charging task， the paper proposed the charging task completion time minimization problem， hoping to find K closed charging circles for K charging vehicles， so that the longest completion time among these K vehicles was the shortest. Since the charging task completion time minimization problem was an NP-hard problem and it was difficult to find an optimal solution in polynomial time， this paper proposed an approximation algorithm with a ratio of 5 for this problem. Finally， it demonstrated the performance of the algorithm by simulation experiments， and the experiments show that the actual approximation ratio of the proposed algorithm is less than 2.

Key words： wireless sensor networks; magnetic resonance wireless charging; on-demand charging; large-scale networks; charging task completion time minimization

0 引言

近幾十年，隨著計(jì)算機(jī)技術(shù)的高速發(fā)展，無(wú)線傳感器網(wǎng)絡(luò)越來(lái)越多地出現(xiàn)在各種應(yīng)用場(chǎng)景中，如環(huán)境監(jiān)測(cè)、交通控制、醫(yī)療健康［1～5］。傳統(tǒng)的傳感器網(wǎng)絡(luò)中的傳感器通常由電池供電，電池存在體積大、能量密度低的缺點(diǎn)，其有限的能量成為傳感器網(wǎng)絡(luò)發(fā)展的一大瓶頸。有部分的傳感器通過(guò)轉(zhuǎn)換周圍環(huán)境中的能量，如太陽(yáng)能、風(fēng)能、電能給自身供電，維持設(shè)備的正常運(yùn)轉(zhuǎn)［6，7］，但是從周圍環(huán)境中獲取能量的充電方式存在著穩(wěn)定性不強(qiáng)的特點(diǎn)，供電功率受周圍環(huán)境因素影響大［8］。傳感器一旦因?yàn)楹谋M電量而無(wú)法工作，會(huì)導(dǎo)致數(shù)據(jù)無(wú)法正常收集。隨著無(wú)線充電技術(shù)，特別是磁共振技術(shù)的問(wèn)世，有研究提出使用充電車給傳感器進(jìn)行電量補(bǔ)充［9～15］。因此，規(guī)劃充電車給無(wú)線傳感器網(wǎng)絡(luò)中的傳感器進(jìn)行電量補(bǔ)充是一個(gè)非常有意義的問(wèn)題。

文獻(xiàn)［16］研究了分布在一維場(chǎng)景中傳感器的多充電車協(xié)作移動(dòng)充電，對(duì)網(wǎng)絡(luò)中的傳感器進(jìn)行周期式充電。在該充電模式中，兩個(gè)可移動(dòng)的充電車之間可以互相傳輸能量。文中研究了在保證傳感器不會(huì)因?yàn)槟芰肯拇M而停止工作的條件下，如何調(diào)度多個(gè)充電車以實(shí)現(xiàn)最大化載荷能量和浪費(fèi)能量比率的目標(biāo)。文獻(xiàn)［17］研究了使用單量充電車對(duì)網(wǎng)絡(luò)中的傳感器進(jìn)行周期性充電，并在此過(guò)程中收集傳感器的數(shù)據(jù)。但是以上研究都是對(duì)所有傳感器進(jìn)行電量補(bǔ)充，而處于不同位置的不同傳感器感知數(shù)據(jù)，接收和轉(zhuǎn)發(fā)數(shù)據(jù)的量不同，消耗數(shù)據(jù)的速率也不同［11～13］。可能存在某些傳感器剩余能量富裕，但是另外一些傳感器的能量所剩無(wú)幾的情況［14，15］。給這部分電量較多的傳感器補(bǔ)充電，需要充電車行駛更長(zhǎng)的距離，行駛過(guò)程中也要消耗充電車的能量，并且給電量較多的傳感器補(bǔ)充電能也是需要消耗時(shí)間的。這無(wú)疑增加了其余傳感器等待被充電的時(shí)間，可能造成一些電量較少的傳感器來(lái)不及被充電而停止工作。文獻(xiàn)［18］研究了二維場(chǎng)景中分布的傳感器充電問(wèn)題，用了請(qǐng)求式充電模式，并提出了一個(gè)primary and passer-by sche-duling （P2S）算法，旨在不增加原有待充電傳感器死亡時(shí)間的基礎(chǔ)上，添加一些離原有電路徑很近的傳感器也作為待充電傳感器，從而提高充電車的整體充電效率。以上算法都不適用于大規(guī)模網(wǎng)絡(luò)場(chǎng)景中，大規(guī)模網(wǎng)絡(luò)中通常需要派遣多輛充電車對(duì)網(wǎng)絡(luò)中的傳感器充電，如何使得多輛充電車協(xié)同工作，同時(shí)能實(shí)現(xiàn)成本最低和任務(wù)完成時(shí)間最短，具有重大的研究意義。因此本文旨在針對(duì)大規(guī)模網(wǎng)絡(luò)中使用多輛充電車對(duì)部分電量較少的傳感器進(jìn)行能量補(bǔ)充的場(chǎng)景，提出了一個(gè)充電總耗時(shí)最短問(wèn)題。本文使用了一種請(qǐng)求式按需充電的方法，盡可能在較短的行駛距離內(nèi)給傳感器補(bǔ)充更多的電量。這種充電方式減少了充電車的行駛長(zhǎng)度，提高了充電車的能量利用效率，文獻(xiàn)［10，13］皆采用類似的設(shè)定。

本文研究了大規(guī)模網(wǎng)絡(luò)場(chǎng)景中，派遣多輛充電車同時(shí)給網(wǎng)絡(luò)中需要充電的傳感器進(jìn)行電量補(bǔ)充，提出了一個(gè)充電總耗時(shí)最短問(wèn)題，目標(biāo)在均衡多輛傳感器的充電任務(wù)，使得總的任務(wù)完成時(shí)間最短。為了解決充電總耗時(shí)最短問(wèn)題，提出了一個(gè)多項(xiàng)式時(shí)間內(nèi)近似比為5的算法。

4 結(jié)束語(yǔ)

因?yàn)閠reeAlg算法的近似比為7，而本文ApproAlg算法的近似比為5，從理論上ApproAlg得到的結(jié)果應(yīng)該比treeAlg更優(yōu)秀，實(shí)驗(yàn)也證明了這一點(diǎn)。從實(shí)驗(yàn)結(jié)果可以看出，對(duì)比treeAlg、最優(yōu)值下限算法和ApproAlg在實(shí)際運(yùn)行中得到結(jié)果，可以得到treeAlg和ApproAlg算法實(shí)驗(yàn)結(jié)果的近似比，比理論分析的近似比要低，并且ApproAlg能得到更好的結(jié)果。對(duì)比最優(yōu)值下限算法可以得到，本文算法的實(shí)際近似比不足2，遠(yuǎn)小于實(shí)際分析的近似比5。

實(shí)驗(yàn)證明，本文算法得到的任務(wù)完成時(shí)間更短。任務(wù)的完成時(shí)間越短，意味著充電車的行駛耗時(shí)減少，節(jié)約了充電車的能耗，更快速地補(bǔ)充了傳感器的電能。傳感器網(wǎng)絡(luò)中，傳感器主要耗能在監(jiān)測(cè)周圍環(huán)境和轉(zhuǎn)發(fā)數(shù)據(jù)。一旦網(wǎng)絡(luò)中有不可預(yù)測(cè)的突發(fā)事件，部分傳感器的電量消耗速度可能大大增加，而傳感器耗盡電量而死亡，將導(dǎo)致該片區(qū)域的數(shù)據(jù)丟失。因此快速地補(bǔ)充傳感器的電量，可以減小可能出現(xiàn)的傳感器電量耗盡的概率，維護(hù)了網(wǎng)絡(luò)的穩(wěn)健性。在同樣的環(huán)境中本文算法完成任務(wù)的時(shí)間短，意味著充電車移動(dòng)的距離短，充電車的耗能更少，因此可以得出結(jié)論，本文算法性能優(yōu)秀。

參考文獻(xiàn)：

[1]Cheng Xiangjin， Yang Ning， Shi Yikai， et al. Design of radiation detection system with WSN［C］//Proc of Cross Strait Quad-regional Radio Science amp; Wireless Technology Conference. Piscataway，NJ： IEEE Press，2011：946-949.

［2]IEC White Paper.Internet of Things： wireless sensor networks［EB/OL］.http：//www.iec.ch/whitepaper/pdf/iecWP-internetofthings-LR-en.pdf.

［3]王楊，張?chǎng)危w傳信，等.基于效用最大化的無(wú)線可充電傳感器網(wǎng)絡(luò)有向充電調(diào)度方案［J］.電子與信息學(xué)報(bào)，2021，43（5）：1331-1338.（Wang Yang， Zhang Xin， Zhao Chuanxin， et al. A utility maximization based forward charging scheduling scheme for wireless rechargeable sensor networks［J］.Journal of Electronics and Information，2021，43（5）：1331-1338.）

［4]水九生，徐向華.一種基于多節(jié)點(diǎn)充電模型的按需順帶充電方案［J］.電子學(xué)報(bào)，2021，49（2）：346-352.（Shui Jiusheng， Xu Xianghua. An on-demand by-pass charging scheme based on a multi-node charging model［J］.Acta Electronica Sinica，2021，49（2）：346-352.）

［5]Yu Liyang， Wang Neng， Meng Xiaoqiao. Real-time forest fire detection with wireless sensor networks［C］//Proc of International Confe-rence on Wireless Communications， Networking and Mobile Computing.Piscataway，NJ：IEEE Press，2005：1214-1217.

［6]Voigt T， Ritter H， Schiller J. Utilizing solar power in wireless sensor networks［C］//Proc of the 28th Annual IEEE International Confe-rence on Local Computer Networks. Piscataway，NJ：IEEE Press，2003：416-422.

［7]Wang Cong， Guo Songtao，Yang Yuanyuan. Energy-efficient mobile data collection in energy-harvesting wireless sensor networks［C］//Proc of the 20th IEEE International Parallel amp; Distributed Processing Symposium.Piscataway，NJ：IEEE Press，2014：55-62.

［8]Rahimi M， Shah H， Sukhatme G， et al. Studying the feasibility of energy harvesting in a mobile sensor network［C］//Proc of IEEE International Conference on Robotics and Automation.Piscataway，NJ：IEEE Press，2003：19-24.

［9]呂增威，魏振春，韓江洪，等.基于多目標(biāo)優(yōu)化的無(wú)線傳感器網(wǎng)絡(luò)移動(dòng)充電及數(shù)據(jù)收集算法［J］.電子與信息學(xué)報(bào)，2019，41（8）：1877-1884.（Lyu Zengwei， Wei Zhenchun， Han Jianghong， et al. Multi-objective optimization-based mobile charging and data collection algorithm for wireless sensor networks［J］.Journal of Electronics and Information，2019，41（8）：1877-1884.）

［10]朱金奇，馮勇，孫華志，等.無(wú)線可充電傳感器網(wǎng)絡(luò)中能量饑餓避免的移動(dòng)充電［J］.軟件學(xué)報(bào)，2018，29（12）：3868-3885.（Zhu Jinqi， Feng Yong， Sun Zhihua， et al. Mobile charging for energy starvation avoidance in wireless rechargeable sensor networks［J］.Journal of Software，2018，29（12）：3868-3885.）

［11]Liang Weifa， Xu Wenzheng， Shi Jiugen， et al. Approximation algorithms for charging reward maximization in rechargeable sensor networks via a mobile charger［J］.IEEE/ACM Trans on Networking，2017，25（5）：3161-3174.

［12]Xu Wenzheng， Liang Weifa， Jia Xiaohua， et al. Maximizing sensor lifetime with the minimal service cost of a mobile charger in wireless sensor networks［J］.IEEE Trans on Mobile Computing，2018，23（2）：2564-2577.

［13]Zou Tao， Xu Wenzheng， Liang Weifa， et al. Improving charging ca-" """pacity for wireless sensor networks by deploying one mobile vehicle with multiple removable chargers［J］.Ad hoc Networks，2017，63：79-90.

［14]Guo Qing， Xu Wemzjemh， Liu Tang， et al. Towards low-cost yet high-performance sensor networks by deploying a few ultra-fast battery powered sensors［J］.Journal of Sensors，2018，18（9）：2771.

［15]Xu Wenzheng， Liang Weifa， Lin Xiaola， et al. Towards perpetual sensor networks via deploying multiple mobile wireless chargers［C］//Proc of Brazilian Conference on Intelligent Systems.Washington DC：IEEE Computer Society，2014：80-89.

［16]Zhang Sheng， Wu Jie， Lu Sanglu. Collaborative mobile charging for sensor networks［C］//Proc of the 9th IEEE International Conference on Mobile Ad hoc and Sensor Systems.Washington DC：IEEE Computer Society，2012：84-92.

［17]丁煦，韓江洪，石雷，等.可充電無(wú)線傳感器網(wǎng)絡(luò)動(dòng)態(tài)拓?fù)鋯?wèn)題研究［J］.通信學(xué)報(bào)，2015，36（1）：179-188.（Ding Xu， Han Jianghong， Shi Lei， et al. Research on dynamic topology of rechargeable wireless sensor networks［J］.Journal of Communications，2015，36（1）：179-188.）

［18]Lin Chi， Han Ding， Deng Jing， et al. A primary and passer-by scheduling algorithm for on-demand charging architecture in wireless rechargeable sensor networks［J］.IEEE Trans on Vehicular Technology，2017，66（9）：8047-8058.

［19]Arkin E M， Hassin R， Levin A. Approximations for minimum and min-max vehicle routing problems［J］.Journal of Algorithms，2006，59（1）：1-18.

［20]Frederickson G N， Hecht M S， Kim C E. Approximation algorithms for some routing problems［C］//Proc of the 17th Annual Symposium on Foundations of Computer Science. Washington DC：IEEE Compu-ter Society，1976： 216-227.

［21]Xu Zhou， Xu Dongsheng， Zhu Wenbin. Approximation results for a min-max location-routing problem［J］.Discrete Applied Mathema-tics，2012，160（3）：306-320.

［22]Yu Wei， Liu Zhaohui. Better approximability results for min-max tree/cycle/path cover problems［J］.Journal of Combinatorial Optimization，2018，37（2）：563-578.

［23]Xu Wenzheng， Liang Weifa， Lin Xiaola. Approximation algorithms for minmax cycle cover problems［J］.IEEE Trans on Computers，2015，64（3）：600-613.