基于全向無線充電模型的動態(tài)調(diào)度優(yōu)化方法

陳路 陳凜 馬輝

摘? 要： 如何延長網(wǎng)絡(luò)壽命是無線傳感網(wǎng)絡(luò)中一個關(guān)鍵問題，為此提出了基于全向無線充電模型的動態(tài)調(diào)度優(yōu)化方法，目標(biāo)是最大化網(wǎng)絡(luò)壽命。文章對充電小車的停止點選擇進(jìn)行了分析，根據(jù)全向無線充電模型的覆蓋范圍確定了充電小車的停止區(qū)域，再以最大化節(jié)點接收功率之和為優(yōu)化目標(biāo)確定每個區(qū)域內(nèi)的最佳停止點。實驗結(jié)果表明，所提出的方法能夠延長網(wǎng)絡(luò)壽命，與MRCR（Multi-node Renewable based on Charging Range）算法相比，可延長網(wǎng)絡(luò)壽命約3%～113%。

關(guān)鍵詞： 無線可充電傳感網(wǎng)絡(luò); 全向無線充電模型; 移動調(diào)度; 停止點選擇; 網(wǎng)絡(luò)壽命

中圖分類號：TP393? ? ? ? ? 文獻(xiàn)標(biāo)志碼：A? ? ?文章編號：1006-8228（2019）09-20-04

A dynamic scheduling method based on omnidirectional wireless charging model

Chen Lu， Chen Lin， Ma Hui

（Hangzhou Dianzi University， Hangzhou， Zhejiang 310018， China）

Abstract： How to extend network life is a key issue in wireless sensor networks. In order to solve this problem， a dynamic scheduling strategy based on the omnidirectional wireless charging model is proposed， with the goal of maximizing network lifetime. In this paper， the selection of stop point of charging car is analyzed， and according to the coverage of omnidirectional wireless charging model， the stop area of charging car is determined， and then the optimal stop point in each area is determined by maximizing the sum of receiving power of nodes. The experiment results show that the proposed method can prolong the network lifetime， which is about 3%～113% longer than MRCR （Multi-node Renewable Based on Charging Range） algorithm.

Key words： wireless rechargeable sensor network; omnidirectional wireless charging model; mobile scheduling; stop point selection; network life

0 引言

無線傳感器網(wǎng)絡(luò)通常由大量微傳感器節(jié)點、匯聚節(jié)點和基站組成。節(jié)點通常配備監(jiān)測模塊、信息處理模塊以及信息收發(fā)模塊[1-2]。傳統(tǒng)的節(jié)點使用電池供電，電池容量嚴(yán)重限制了節(jié)點壽命[3]。為了解決能量有限問題[4，6]，隨著無線能量傳輸技術(shù)的出現(xiàn)與發(fā)展，可以利用該技術(shù)給節(jié)點提供穩(wěn)定的能量。

據(jù)我們了解，Xie等人[7]是第一個把無線能量傳輸技術(shù)應(yīng)用到無線傳感網(wǎng)絡(luò)中的。作者將全向無線充電模型抽象為正六邊形，并且將二維傳感網(wǎng)絡(luò)劃分為若干個相鄰的正六邊形，六邊形的邊長即為充電器的最大覆蓋距離，充電小車只需要停止在六邊形的中心即可對蜂窩內(nèi)的所有節(jié)點進(jìn)行充電。針對同樣的問題，Wu等人[8]給出了更靈活的劃分方法即首先將全向無線充電模型抽象為圓形，然后以各個圓形相交區(qū)域的頂點為候選停止點，最后以最短化小車的移動路徑為優(yōu)化目標(biāo)從候選停止點中選出最終的停止點。

然而，從充電的角度研究該問題，我們會發(fā)現(xiàn)，更好的解決辦法不僅要考慮節(jié)點是否在充電器的最大覆蓋范圍內(nèi)，還應(yīng)該考慮由充電器與節(jié)點之間的距離產(chǎn)生的能量衰減問題。所以，在我們的解決辦法中，還會考慮最小化節(jié)點與充電器間的距離和，從而最大化節(jié)點接收到的總能量。

1 問題描述

全向無線充電模型，如圖1所示，基于的無線充電原理是磁共振耦合，功率衰減模型如式⑴所示。

[Prd=Pout?（-0.0985?d2-0.0377?d+1）]? ?（1）

其中，[Prd]表示節(jié)點的接收功率值，[d]表示節(jié)點和充電小車間的距離，[Pout]表示充電小車的輸出功率。假設(shè)[Pout=5W]，節(jié)點接收功率的最小閾值為[1W]，那么充電小車的能量最大傳輸距離[D]約為[2.7m]，只要節(jié)點與充電器的距離不大于[D]，充電器就可以同時對多個節(jié)點進(jìn)行充電。

假設(shè)每一個節(jié)點的電池容量為[Bmax]，節(jié)點電池能量低于一個最小閾值[δ]即停止工作，有一個節(jié)點停止工作則整個網(wǎng)絡(luò)壽命終止。為了公式化這個問題，以下將節(jié)點表示為[O={o1，o2，…oN}]，節(jié)點[oi]的位置表示為[（oxi，oyi）]。假設(shè)充電小車的停止點集合為[S=s1，s2，…sM，]，第[k]停止點[sk]的位置為[（sxk，syk）]，在這個位置可以充電的節(jié)點集合為[SN（sk）]，那么當(dāng)[oi∈SN（sk）]時，假設(shè)節(jié)點[oi]和充電小車停止位置[sk]的距離為[dk，i]，可以根據(jù)式⑴得出相應(yīng)的接收功率為[Pr（dk，i）]。進(jìn)一步假設(shè)，節(jié)點[oi]在[t]時刻的能量為[ei（t）]，為了保證充電的有效性，每次給節(jié)點充電至少要使得節(jié)點的電量達(dá)到一個最小值[Bmin]。那么每個節(jié)點的充電時間[ti]要滿足式⑵。

[max 0，Bmin-ei（t）Pr（dk，i）≤ti≤Bmax-ei（t）Pr（dk，i）] （2）

充電小車在停止點[sk]能夠覆蓋到的節(jié)點集合為[SN（sk）]，那么充電小車在這個停止點的停留時長要滿足該集合內(nèi)所有節(jié)點的能量需求。假設(shè)充電小車在停止點[sk]的停留時長為[?Tk]，那么[?Tk]要滿足式⑶。

[ （3）]

直觀地，充電小車在每個位置停留的時間越長，節(jié)點接收到的能量越多，也就能夠最大限度的延長該區(qū)域內(nèi)節(jié)點的壽命，但是可能會導(dǎo)致后面還沒有充電的節(jié)點由于能量太低而停止工作，因此充電小車在每個位置的停留時間也不能太長。下面用[L]表示充電路徑的長度，[v]表示充電小車移動的速度，[ωi]表示節(jié)點[oi]的能量消耗率。至此，本文給出最大化網(wǎng)絡(luò)壽命的優(yōu)化公式：

[maxk=1M?Tk+Lv]? ?（4）

[（5）]

[Prdk，i=（-0.0985dk，i2-0.0377dk，i+1）Pout]? （6）

[dk，i=（sxk-oxi）2+（syk-oyi）2]? ?（7）

[δ≤eit≤Bmax，oi∈SN（sk）]? （8）

式⑸計算充電小車在每個停止點停留時間的上限和下限，式⑹和式⑺計算每個節(jié)點的能量接收功率，式⑻確保每個節(jié)點的剩余能量值大于閾值。對于一個連續(xù)的二維無線傳感網(wǎng)絡(luò)，充電小車能夠停止在任意位置，如果充電小車的停止位置不事先確定，式⑺的距離無法確定，相應(yīng)的式⑹中的充電功率也就無法確定，最終導(dǎo)致無法得出式⑷的解。下面對停止的選擇進(jìn)行分析給出近似算法。

2 停止點選擇分析

基于全向無線充電模型，只要節(jié)點和充電器間的距離不大于[D]，二者就能量進(jìn)行能量傳輸。以節(jié)點為圓心，以[D]為半徑作圓，充電小車只要停止在這些圓的相交區(qū)域內(nèi)就可以同時對圓心處的節(jié)點進(jìn)行充電。如圖2所示，以節(jié)點[o1]、[o2]和[o3]為圓心，以[D]為半徑作圓，那么圖中可以對節(jié)點充電的區(qū)域有四個，分別為[a1]、[a2]、[a3]以及[a4]，充電小車只需要停在區(qū)域[a2]和[a4]即可實現(xiàn)對所有節(jié)點的充電。

當(dāng)網(wǎng)絡(luò)中有大量的節(jié)點時，這些圓的相交區(qū)域的數(shù)量可能也會很多，如果充電小車在每個相交區(qū)域都停止一次，那么不僅會導(dǎo)致充電小車的移動路線過長，造成能量浪費，還可能會導(dǎo)致后面的節(jié)點由于沒有及時的得到能量補(bǔ)充而耗盡能量。為了盡量避免這樣的問題出現(xiàn)，本文考慮以最少的停止次數(shù)覆蓋到網(wǎng)絡(luò)中的所有節(jié)點。下面給出最少化停止次數(shù)的非線性規(guī)劃公式如式⑼。

[[mink=1numαk βk]

[fi，k=1，如果節(jié)點oi∈SN（ak）0，如果節(jié)點oi?SN（ak）]? ? ? ⑼ ]

公式⑼中，[ak]表示第[k]個停止區(qū)域，[SN（ak）]表示區(qū)域[ak]能覆蓋到的節(jié)點集合;[fi，k]表示節(jié)點[oi]是否屬于第[k]個停止區(qū)域的充電集合;[βk]表示是否選擇第[k]個候選停止位區(qū)域，[βk=1]表示選擇，相反則表示不選擇;[num]表示總的候選區(qū)域個數(shù)。[num]個不等式確保每個節(jié)點至少屬于一個被選擇的停止區(qū)域。

假設(shè)停止次數(shù)確定為[M]個，停止區(qū)域集合確定為[Area=a1，a2，…，aM]，[ak]能覆蓋到的節(jié)點集合為[SN（ak）]。但是在[ak]內(nèi)充電小車的停止點仍然是無數(shù)個，需要在[ak]內(nèi)確定一個最佳的停止點[sk]。在[ak]內(nèi)的最佳停止點[sk]是指，最佳停止點定義為區(qū)域內(nèi)所有節(jié)點的能量接收功率之和最大的點，這樣能夠最大化節(jié)點接收到的能量。[Area]中的每個停止區(qū)域都對應(yīng)于一個最佳停止點，停止點集合記為[Stop={s1，s2，…，sM}]。由于節(jié)點接收功率是隨著距離增加而衰減的，充電功率和最大也就是距離和最小，因此本文將問題轉(zhuǎn)化為求距離和最小的點，公式化如式⑽。通過式⑽就能夠確定在每個停止區(qū)域的停止點[sk]，以及覆蓋到的節(jié)點集合[SN（sk）]。

[[minoi∈SN（ak）dk，i]

[s.t. dk，i=（sxk-oxi）2+（syk-oyi）2]? ? ? ⑽ ]

該問題的一個特例是最小覆蓋問題，因為最小集合覆蓋問題為一個NP難問題，那么該問題也是一個NP難問題。

3 停止點選擇算法設(shè)計

由于停止點選擇問題是一個NP難問題，本文提出一個近似算法，即“停止點選擇”進(jìn)行求解，算法步驟為：

步驟1 輸入節(jié)點集合為[O={o1，o2，…oN}]、節(jié)點[oi]的位置[ （oxi，oyi）]以及充電小車最遠(yuǎn)覆蓋距離[D];

步驟2 以每個節(jié)點為圓心，以[D]為半徑畫圓;

步驟3 確定每個圓的相交區(qū)域;

步驟4 確定每個相交區(qū)域覆蓋到的節(jié)點集合;

步驟5 通過最小集合覆蓋算法確定最少的停止區(qū)域，能夠覆蓋到所有的節(jié)點，最終的停止區(qū)域集合為[Area=a1，a2，…，aM];

步驟6 在每個停止區(qū)域內(nèi)通過求解公式（10）確定最佳的停止點，輸出停止點集合為[Stop={s1，s2，…，sM}]。

4 仿真實驗

4.1 確定充電小車停止點

在25*25的網(wǎng)絡(luò)中隨機(jī)拋灑50個節(jié)點，得到的充電器停止位置如圖3所示，從圖中可以看出沒有節(jié)點被遺漏，并且充電小車能夠盡可能停止在距離節(jié)點較近的位置。

4.2 網(wǎng)絡(luò)壽命

在25*25的網(wǎng)絡(luò)中拋灑60～140個節(jié)點，分別使用本文提出的停止點選擇算法和MRCR算法[15]確定充電小車停止點的坐標(biāo)，計算并記錄停止點選擇算法相較于MRCR算法對網(wǎng)絡(luò)壽命的延長提升的百分比，結(jié)果如圖4所示。從圖4中可以看出對于網(wǎng)絡(luò)壽命的延長，使用停止點選擇算法相較于使用MRCR算法，對于網(wǎng)絡(luò)壽命延長提升了約3%～113%。

5 結(jié)束語

本文提出的基于全向無線充電模型的動態(tài)調(diào)度優(yōu)化方法，目標(biāo)是最大化網(wǎng)絡(luò)壽命，實驗結(jié)果表明本文所提出調(diào)度方法能夠延長網(wǎng)絡(luò)壽命，并且相對于MRCR算法網(wǎng)絡(luò)壽命的延長效果有所提升。將該充電策略應(yīng)用于無線可充電傳感網(wǎng)絡(luò)中能夠最大限度的延長網(wǎng)絡(luò)工作時長，未來我們將進(jìn)一步研究基于全向無線充電模型的動態(tài)調(diào)度策略，目標(biāo)是在確保網(wǎng)絡(luò)無限運(yùn)行的前提下最大化充電小車的能量利用率。

參考文獻(xiàn)（References）：

[1] 黃鋒，劉士興，顧勤東.無線傳感器網(wǎng)絡(luò)節(jié)點概述[J]. 合肥工業(yè)大學(xué)學(xué)報，2008.31（8）：1208-1212

[2] 繆海星.無線傳感器網(wǎng)絡(luò)的移動數(shù)據(jù)收集及充電規(guī)劃研究[D].華僑大學(xué)，2016.

[3] 丁煦.可充電無線傳感器網(wǎng)絡(luò)能耗模型及充電策略研究[D].合肥工業(yè)大學(xué)，2015.

[4] Erol-Kantarci M，Mouftah H T.Suresense： Sustainable wireless rechargeable sensor networks for the smart grid[J]. IEEE Wireless Communications，2012.19（3）：30-36

[5] He Shibo，Chen Jiming，Jiang Fachang，et al. Energy provisioning in wireless rechargeable sensor networks[C]. Shanghai： IEEE INFOCOM，2011.

[6] He Tengjiao，Chin K W，Soh S.On using wireless power transfer to increase the max flow of rechargeable wireless sensor networks[C].Singapore：IEEE Tenth International Conference on Intelligent Sensors，2015.

[7] Xie Liguang，Shi Yi，Hou Y T，et al.Multi-Node Wireless Energy Charging in Sensor Networks[J].IEEE/ACM Transactions On Networking，2015.23（2）：437-450

[8] Wu Guowei，Lin Chi，Li Ying， et al.A Multi-node Renewable Algorithm Based on Charging Range in Large-Scale Wireless Sensor Network[C].Blumenau： International Conference on Innovative Mobile and Internet Services in Ubiquitous Computing， 2015.