唐 拓馮 勇李英娜錢 謙付曉東

(昆明理工大學(xué)云南省計(jì)算機(jī)技術(shù)應(yīng)用重點(diǎn)實(shí)驗(yàn)室，云南 昆明 650500)

物聯(lián)網(wǎng)(Internet of Things)的飛速發(fā)展離不開(kāi)無(wú)線傳感網(wǎng)絡(luò)(WSNs)提供的技術(shù)支持，無(wú)線傳感器網(wǎng)絡(luò)是現(xiàn)代社會(huì)應(yīng)用最廣泛的信息采集技術(shù)，被廣泛應(yīng)用于醫(yī)療健康、基礎(chǔ)設(shè)施狀態(tài)監(jiān)測(cè)、智能交通、生態(tài)環(huán)境監(jiān)測(cè)以及軍事攻擊監(jiān)測(cè)等領(lǐng)域[1]。WSN中的傳感器由于受到自身尺寸與成本的限制，通常使用電池進(jìn)行供電，運(yùn)行時(shí)間受限于電池的容量。得益于無(wú)線能量補(bǔ)充技術(shù)的發(fā)展，利用無(wú)線充電技術(shù)延長(zhǎng)無(wú)線傳感網(wǎng)絡(luò)的生存時(shí)間已得到廣泛的研究，無(wú)線可充電傳感網(wǎng)絡(luò)(Wireless Rechargeable Sensor Networks，WRSNs)正在興起。在WRSNs中使用配備有無(wú)線移動(dòng)充電設(shè)備的移動(dòng)裝置(Mobile Charger，MC)為傳感器節(jié)點(diǎn)提供可靠的能量補(bǔ)充，能夠有效減少節(jié)點(diǎn)的充電等待時(shí)間，成為解決傳感器電池能量受限問(wèn)題的有效解決方案[2-3]。由于WRSNs中的傳感器節(jié)點(diǎn)失效會(huì)導(dǎo)致數(shù)據(jù)丟失、鏈接斷開(kāi)甚至網(wǎng)絡(luò)癱瘓等嚴(yán)重問(wèn)題，如何調(diào)度MC高效地為網(wǎng)絡(luò)中的傳感器節(jié)點(diǎn)補(bǔ)充能量是WRSNs充電策略的關(guān)鍵問(wèn)題。

WRSNs往往布置在極端或較復(fù)雜的環(huán)境，MC接近傳感器節(jié)點(diǎn)進(jìn)行充電有一定困難且效率較低，基于磁耦合諧振充電技術(shù)的一對(duì)多充電方式允許MC在充電范圍內(nèi)同時(shí)對(duì)多個(gè)傳感器節(jié)點(diǎn)進(jìn)行能量補(bǔ)充，不僅使MC可在安全地區(qū)對(duì)傳感器進(jìn)行能量補(bǔ)充，擴(kuò)展了WRSNs的應(yīng)用場(chǎng)景，同時(shí)提高了充電效率。磁耦合諧振充電技術(shù)[4-5]是目前廣泛應(yīng)用于WRSNs中的能量傳輸技術(shù)。通過(guò)在MC和傳感器上分別安裝發(fā)射線圈與接收線圈，調(diào)節(jié)成相同頻率，能量通過(guò)強(qiáng)諧振耦合在線圈之間發(fā)生傳遞，可在一定范圍內(nèi)實(shí)現(xiàn)一對(duì)多無(wú)線能量補(bǔ)充。文獻(xiàn)[6]利用相鄰的正六邊形單元格平等分割網(wǎng)絡(luò)，傳感器節(jié)點(diǎn)被覆蓋在單元格內(nèi)，MC周期性移動(dòng)到單元格中心位置通過(guò)磁耦合諧振充電技術(shù)來(lái)實(shí)現(xiàn)能量的無(wú)線傳輸。但是該方法未考慮MC充電成本以及距離對(duì)諧振充電能量傳輸?shù)挠绊?，算法性能較低。

隨著對(duì)WRSNs的規(guī)模需求不斷提高，使用單MC進(jìn)行充電已無(wú)法達(dá)到網(wǎng)絡(luò)的需求，這是由于MC無(wú)法攜帶足夠的能量在一個(gè)充電循環(huán)中為大規(guī)模WRSN中的每個(gè)請(qǐng)求節(jié)點(diǎn)進(jìn)行充電，MC在給一部分傳感器節(jié)點(diǎn)充電后需要返回基站補(bǔ)充自身能量。這種方式不僅充電效率極低而且傳感器節(jié)點(diǎn)常常由于得不到及時(shí)的能量補(bǔ)充而失效。此時(shí)需要部署多個(gè)MC為網(wǎng)絡(luò)中的傳感器節(jié)點(diǎn)充電，但是MC往往價(jià)格昂貴，出于成本考慮應(yīng)使MC數(shù)量盡量少。

設(shè)計(jì)了一種高效的多MC協(xié)同充電策略，通過(guò)相交圓算法將網(wǎng)絡(luò)中的傳感器節(jié)點(diǎn)劃分為若干個(gè)節(jié)點(diǎn)簇，利用最短距離原則確定各個(gè)簇的MC充電駐點(diǎn)，之后根據(jù)能量約束平衡條件確定網(wǎng)絡(luò)需要的MC數(shù)量，最后通過(guò)優(yōu)先級(jí)分配算法使多個(gè)MC能夠協(xié)作對(duì)網(wǎng)絡(luò)進(jìn)行充電，提高充電效率與能量利用率。

本文第一節(jié)介紹了相關(guān)工作。第二節(jié)概述了網(wǎng)絡(luò)模型與問(wèn)題公式。第三節(jié)中詳細(xì)描述了MTORN算法的設(shè)計(jì)步驟與理論分析。第四節(jié)通過(guò)仿真實(shí)驗(yàn)對(duì)比分析所提方案的性能。第五節(jié)總結(jié)全文。

1 相關(guān)工作

本部分簡(jiǎn)要介紹WRSNs中的能量補(bǔ)充技術(shù)。

一對(duì)一充電模式中，MC只能在同一時(shí)間給一個(gè)傳感器節(jié)點(diǎn)充電。He等[7]提出一種最近節(jié)點(diǎn)優(yōu)(NJNP)原則來(lái)解決充電節(jié)點(diǎn)的選擇問(wèn)題，但是該方案忽視了響應(yīng)充電請(qǐng)求的公平性，低電量節(jié)點(diǎn)易失效死亡。Dai等[8]考慮了候選充電節(jié)點(diǎn)的選擇與每個(gè)節(jié)點(diǎn)的充電時(shí)間，之后根據(jù)傳感器接收到的能量來(lái)調(diào)度MC的移動(dòng)規(guī)劃，最大限度地提高網(wǎng)絡(luò)的充電效用。文章將問(wèn)題形式化為最大QoM充電和調(diào)度問(wèn)題(MQCSP)，但是如何獲得MQCSP的精確解卻未給出較好的解決方案。

一對(duì)多充電模式的出現(xiàn)極大地提高了充電效率，更適用于大規(guī)模WRSNs中。Kurs等[4]首次提出一對(duì)多能量傳輸技術(shù)，允許多個(gè)接收器通過(guò)單個(gè)電源同時(shí)充電，有效地解決了單對(duì)單充電模式的可擴(kuò)展性問(wèn)題，并提高了整體能量傳輸效率。但是該方法未考慮MC充電駐點(diǎn)的規(guī)劃，系統(tǒng)充電效率還有極大提高空間。文獻(xiàn)[9]研究了在線模式下的多節(jié)點(diǎn)充電問(wèn)題，作者提出了一個(gè)充電規(guī)劃算法來(lái)最大化可充電的傳感器數(shù)量，并指示充電位置，以降低MC移動(dòng)能耗。但是該方法增加了節(jié)點(diǎn)的充電等待時(shí)間且未考慮充電的均衡性。

為了進(jìn)一步提高充電效率，學(xué)者們開(kāi)始研究多個(gè)MC充電的方式。在文獻(xiàn)[10]中，作者假設(shè)所有傳感器具有相同的恒定能量消耗率。通過(guò)規(guī)劃MCs的路徑，以找到MCs的最小數(shù)量，從而延長(zhǎng)網(wǎng)絡(luò)的運(yùn)行時(shí)間。然而由于環(huán)境的隨機(jī)性，傳感器能耗往往具有較大波動(dòng)性，該方法無(wú)法適應(yīng)WRSNs的實(shí)際應(yīng)用情況。在文獻(xiàn)[11]中，作者提出了一種稱為PushWait的調(diào)度算法，MCs不僅可以給傳感器充電，還允許它們相互充電。為最大化充電效率，該算法平衡MC充電功耗與移動(dòng)功耗，同時(shí)保證網(wǎng)絡(luò)中傳感器的能量充足。該方法優(yōu)化了網(wǎng)絡(luò)的能量利用率，但隨著傳感器節(jié)點(diǎn)數(shù)量的增加，所需MC的數(shù)量會(huì)急劇增加，導(dǎo)致成本過(guò)高。

可以看出，現(xiàn)有的充電策略存在對(duì)充電均衡性考慮不足以及難以得到最優(yōu)解等缺陷。由于WRSNs充電優(yōu)化問(wèn)題的NP-Hard特性，許多啟發(fā)式算法也同樣面對(duì)著在網(wǎng)絡(luò)規(guī)模較大時(shí)無(wú)法高效解決WRSN充電優(yōu)化問(wèn)題的挑戰(zhàn)。

為了解決上述問(wèn)題，提出了MTORN充電算法。以按需充電的模式，在WRSNs中部署多個(gè)MC通過(guò)一對(duì)多充電的方式協(xié)同為網(wǎng)絡(luò)提供及時(shí)且穩(wěn)定的能量補(bǔ)充。同時(shí)，引入優(yōu)先級(jí)分配算法來(lái)提高動(dòng)態(tài)WRSN中的充電均衡性。

2 網(wǎng)絡(luò)模型與問(wèn)題公式

2.1 網(wǎng)絡(luò)模型

系統(tǒng)模型如圖1所示。本文的無(wú)線可充電傳感網(wǎng)絡(luò)模型主要由三個(gè)部分組成:(1)配備有無(wú)線能量接收器的若干個(gè)傳感器節(jié)點(diǎn)(sensor node)(S i＝S1，S2，…S n)；(2)配備有無(wú)線充電器的多個(gè)MC(M j＝M1，M2，…M m)，MC具有自主移動(dòng)、計(jì)算和通信的能力；(3)基站(BS)，負(fù)責(zé)收集和處理傳感器節(jié)點(diǎn)傳輸?shù)臄?shù)據(jù)，監(jiān)控整個(gè)網(wǎng)絡(luò)的狀態(tài)，同時(shí)為MC補(bǔ)充能量。所有傳感器節(jié)點(diǎn)隨機(jī)部署在二維地圖上，節(jié)點(diǎn)位置可以精確地確定，傳感器節(jié)點(diǎn)在自身剩余能量下降到預(yù)先設(shè)定的閾值lr時(shí)主動(dòng)地向MC發(fā)送充電請(qǐng)求，MC可以在區(qū)域內(nèi)自由移動(dòng)，MC通過(guò)無(wú)線充電的方式同時(shí)為多個(gè)傳感器節(jié)點(diǎn)充電，并在自身電量過(guò)低時(shí)返回基站為自身補(bǔ)充電量。

圖1 網(wǎng)絡(luò)模型圖

MC具有4種狀態(tài)，分別為空閑、移動(dòng)、充電和返回基站狀態(tài)，如圖2所示，空閑狀態(tài)表示MC當(dāng)前未接收到任何充電請(qǐng)求；移動(dòng)狀態(tài)說(shuō)明MC已確定候選充電簇并向其移動(dòng)；充電狀態(tài)表示MC正在為節(jié)點(diǎn)簇進(jìn)行充電；返回基站狀態(tài)表示MC已完成充電任務(wù)或自身能量較低，返回基站補(bǔ)充能量。

圖2 MC狀態(tài)轉(zhuǎn)移圖

2.2 問(wèn)題公式

本節(jié)描述系統(tǒng)中能量消耗、能量補(bǔ)充的模型。

2.2.1 能量消耗模型

對(duì)于每個(gè)傳感器，其能量消耗主要由兩部分組成:監(jiān)測(cè)任務(wù)和數(shù)據(jù)傳輸。因此可以根據(jù)傳感器節(jié)點(diǎn)的監(jiān)測(cè)效率和數(shù)據(jù)傳輸率來(lái)預(yù)測(cè)各個(gè)傳感器節(jié)點(diǎn)的功耗范圍和剩余能量。節(jié)點(diǎn)S i(1≤i≤n)的能量消耗速率P i可表示為:

式中:j為節(jié)點(diǎn)S i接收數(shù)據(jù)的源節(jié)點(diǎn)，G j，i(t)表示節(jié)點(diǎn)S i接收到的信息總和，k為節(jié)點(diǎn)S i轉(zhuǎn)發(fā)數(shù)據(jù)的目的節(jié)點(diǎn)，G k，i(t)表示節(jié)點(diǎn)S i轉(zhuǎn)發(fā)的信息總和；α為信號(hào)放大器能耗率；d i，j，d i，k分別表示節(jié)點(diǎn)S i與節(jié)點(diǎn)S j，S k的距離；ρ為接收1 bit信息所消耗的能量。σ為傳感器進(jìn)行監(jiān)測(cè)任務(wù)的能耗率，G i(t)為節(jié)點(diǎn)S i的監(jiān)測(cè)信息總和。

節(jié)點(diǎn)S i在t時(shí)刻的能量消耗為:

2.2.2 能量補(bǔ)充模型

MC可以在其范圍內(nèi)的對(duì)多個(gè)傳感器節(jié)點(diǎn)進(jìn)行無(wú)線充電。對(duì)于節(jié)點(diǎn)S i，接收充電的功率為:

式中:d S i，MC是MC和節(jié)點(diǎn)S i之間的距離，P c為充電時(shí)的源功率，β為調(diào)整短距離傳輸?shù)母ダ锼狗匠虆?shù)。G S為發(fā)射增益參數(shù)，G R為接收增益參數(shù)，L P為偏振損耗，σ為整流器效率，λ為波長(zhǎng)。

為了提高充電效率和網(wǎng)絡(luò)生存時(shí)間，我們需要盡可能增大簇內(nèi)每個(gè)節(jié)點(diǎn)的能量接收功率P S i。

3 MTORN策略設(shè)計(jì)與實(shí)現(xiàn)

3.1 MC充電駐點(diǎn)的位置確定

當(dāng)MC的充電范圍為R時(shí)，MC能夠通過(guò)無(wú)線能量傳輸給以MC為圓心，半徑為R的范圍內(nèi)多個(gè)傳感器節(jié)點(diǎn)充電。為MC確定充電駐點(diǎn)目的在于使MC在每個(gè)充電駐點(diǎn)能夠同時(shí)為更多的傳感器節(jié)點(diǎn)充電。駐點(diǎn)位置的確定分兩步實(shí)現(xiàn)，第一步通過(guò)相交圓算法對(duì)節(jié)點(diǎn)進(jìn)行分簇，第二步根據(jù)最短距離原則確定各個(gè)簇的充電駐點(diǎn)。相交圓駐點(diǎn)選擇算法具體步驟如圖3所示。

圖3 相交圓駐點(diǎn)選擇算法示例圖

相交圓駐點(diǎn)選擇算法:對(duì)于一組傳感器節(jié)點(diǎn)S＝{S1，S2，…，Sn1}，給定每個(gè)傳感器節(jié)點(diǎn)S i(1≤i≤n1)都有一個(gè)以S i為圓心，半徑為R(MC充電范圍半徑)的圓，由此可以得到一組相應(yīng)的圓集合C(｜C｜＝｜N｜)。如果兩個(gè)或多個(gè)圓存在公共交集區(qū)域，具有上述特點(diǎn)的傳感器節(jié)點(diǎn)可劃分為一個(gè)簇。這個(gè)公共交集區(qū)域，就是充電駐點(diǎn)的可選部署區(qū)域。例如Ci與圓C j以及Ck相交，則三個(gè)節(jié)點(diǎn)S i、S j、Sk的重疊區(qū)域表示為Aijk，將Aijk中所有的坐標(biāo)點(diǎn)放入一個(gè)集合VTijk＝{VT1，VT2，…，VTn2}，充電駐點(diǎn)的位置Pm便從VTijk中選擇。

由于無(wú)線充電功率隨著距離增大而減小，因此采用駐點(diǎn)與簇內(nèi)各節(jié)點(diǎn)總距離最短原則確定駐點(diǎn)位置。假設(shè)P m，VTm，S i，S j，S k的二維坐標(biāo)為(x P m，y P m)，(x Tm，y Tm)，(x Si，y Si)，(x Sj，y Sj)，(x Sk，y S k)，其中(1≤m≤n2，1≤i，j，k≤n1)。可以得到下式:

根據(jù)上式可以得到距離簇內(nèi)各個(gè)傳感器節(jié)點(diǎn)總距離最短的駐點(diǎn)二維坐標(biāo)位置。

確定MC的充電駐點(diǎn)位置之后，將傳感器節(jié)點(diǎn)i，j，k加入簇C m中。按照該方法可將整個(gè)網(wǎng)絡(luò)劃分為若干個(gè)節(jié)點(diǎn)簇。對(duì)于孤立節(jié)點(diǎn)(即與其他節(jié)點(diǎn)圓沒(méi)有公共交集區(qū)域的節(jié)點(diǎn))MC需要對(duì)其單獨(dú)充電。

3.2 確定最優(yōu)MC數(shù)量

本節(jié)的目標(biāo)為確定能夠滿足網(wǎng)絡(luò)電量需求的最優(yōu)MC數(shù)量。MC價(jià)格高昂，在區(qū)域中部署過(guò)多的MC不符合現(xiàn)實(shí)要求，同時(shí)MC面臨無(wú)線充電技術(shù)本身的能量損耗以及移動(dòng)產(chǎn)生的能量損耗問(wèn)題。因此網(wǎng)絡(luò)中部署的MC需要使網(wǎng)絡(luò)整體能耗保持平衡，即m個(gè)MC輸出的能量要維持自身移動(dòng)能耗同時(shí)滿足網(wǎng)絡(luò)的能量需求。根據(jù)以上約束建立能耗平衡約束條件:

假設(shè)在一個(gè)范圍固定的WRSN中，隨機(jī)部署有n個(gè)傳感器節(jié)點(diǎn)，節(jié)點(diǎn)按3.1的方法被劃分為L(zhǎng)個(gè)節(jié)點(diǎn)簇，C i表示第i個(gè)部署有節(jié)點(diǎn)的簇，網(wǎng)絡(luò)中有m個(gè)可以響應(yīng)充電請(qǐng)求的MC，MC為節(jié)點(diǎn)充電的效率為P S i。MC在兩個(gè)節(jié)點(diǎn)簇之間移動(dòng)的距離為:

式中:L代表節(jié)點(diǎn)簇的個(gè)數(shù)，d C i，C j代表兩個(gè)節(jié)點(diǎn)簇中心之間的歐氏距離，d代表充電簇中心之間的平均歐式距離。假設(shè)MC在網(wǎng)絡(luò)中兩個(gè)節(jié)點(diǎn)簇之間的移動(dòng)距離為d，則m個(gè)MC總的的移動(dòng)能耗為:

式中:P T代表MC移動(dòng)能耗率。當(dāng)網(wǎng)絡(luò)中所有發(fā)起充電請(qǐng)求的節(jié)點(diǎn)能量需要被充滿時(shí)，網(wǎng)絡(luò)的能量需求為:

ESN為傳感器節(jié)點(diǎn)的電池容量，E0為發(fā)起充電請(qǐng)求的電量閾值，P S i為節(jié)點(diǎn)接收充電的功率，n q為網(wǎng)絡(luò)中發(fā)起充電請(qǐng)求的傳感器節(jié)點(diǎn)個(gè)數(shù)。

m個(gè)MC能補(bǔ)充的電量為:

EMC為MC電池容量，ETH為能夠維持MC返回基站補(bǔ)充能量的電量閾值，m為MC個(gè)數(shù)。

綜上，為使網(wǎng)絡(luò)的整體能耗保持平衡，需滿足:

即:

對(duì)上式兩邊同乘m，移項(xiàng)可得:

轉(zhuǎn)化為一元二次等式求解，由于EMC-ETH＞0，因此式(11)相應(yīng)的數(shù)學(xué)模型是開(kāi)口向上且過(guò)零點(diǎn)的拋物線，易知一元二次等式的兩個(gè)解分別為0和m，0不符合要求應(yīng)被舍棄，確定另一個(gè)根m的邊界值向上取整即可得到網(wǎng)絡(luò)最優(yōu)的MC個(gè)數(shù)。

3.3 多MC協(xié)同充電算法

本節(jié)的目標(biāo)為處理多MC充電系統(tǒng)的協(xié)同合作關(guān)系。本文引入簇的優(yōu)先級(jí)分配充電算法，多個(gè)MC接收充電請(qǐng)求，并每隔T時(shí)間檢查服務(wù)池內(nèi)的充電請(qǐng)求信息集合，這些信息主要包括簇中節(jié)點(diǎn)的剩余能量R s以及簇的充電駐點(diǎn)位置。

初始時(shí)MC的狀態(tài)設(shè)為空閑，并位于網(wǎng)絡(luò)的中心位置。當(dāng)接收到節(jié)點(diǎn)的充電請(qǐng)求時(shí)MC會(huì)更新服務(wù)池，并計(jì)算相應(yīng)簇的優(yōu)先級(jí)ψ(C m)。ψ(C m)表示簇C m的充電優(yōu)先級(jí)，反映了該節(jié)點(diǎn)簇需要充電的緊迫程度，是MC進(jìn)行充電決策的重要依據(jù)。其計(jì)算公式如下:

式中:Eresidual為簇C m內(nèi)所有傳感器節(jié)點(diǎn)的平均剩余能量，Nrequest為發(fā)起充電請(qǐng)求的節(jié)點(diǎn)個(gè)數(shù)，N C m為簇C m內(nèi)的所有節(jié)點(diǎn)個(gè)數(shù)。推導(dǎo)過(guò)程如下:

ωN為節(jié)點(diǎn)因子，與簇內(nèi)發(fā)起充電請(qǐng)求的節(jié)點(diǎn)數(shù)量有關(guān)。簇內(nèi)發(fā)起充電請(qǐng)求的節(jié)點(diǎn)數(shù)量Nrequest越多，簇內(nèi)節(jié)點(diǎn)的平均剩余能量Eresidual越低，與MC的距離越近，簇的優(yōu)先級(jí)越高。即簇的優(yōu)先級(jí)與節(jié)點(diǎn)因子成正相關(guān)，與距離因子和能量因子成負(fù)相關(guān)，從而有:

綜合式(13)～式(16)可得式(12)。

在MTORN中，為了保證網(wǎng)絡(luò)的充電均衡性，收到充電請(qǐng)求超過(guò)其服務(wù)能力的MC可以向當(dāng)前充電可用性較大(即相對(duì)空閑)的MC發(fā)送幫助消息，將充電任務(wù)分配給網(wǎng)絡(luò)中的其他MC。接下來(lái)給出MC當(dāng)前充電可用性的定義以及計(jì)算公式:

式中:E j為移動(dòng)充電器m j的剩余能量，ωn為MC的任務(wù)因子，N j表示移動(dòng)充電器m j接收到的充電請(qǐng)求數(shù)量，N r為網(wǎng)絡(luò)中所有的充電請(qǐng)求數(shù)。在某一時(shí)間，MC需要處理的充電請(qǐng)求較少，與簇的距離較近，自身剩余能量較大，則該MC的充電可用性也較大。即MC的充電可用性與任務(wù)因子ωn和距離因子ωd成負(fù)相關(guān)，與能量因子ωe成負(fù)相關(guān)，因此可以得到:

式中:ωse為能量因子，表示簇內(nèi)平均剩余能量。

綜合式(18)、(19)可得式(17)。通過(guò)對(duì)充電任務(wù)的合理分配，不僅可以均衡網(wǎng)絡(luò)中MC的能耗，還可以避免網(wǎng)絡(luò)中節(jié)點(diǎn)因電量過(guò)低而失效。

多MC協(xié)同充電算法偽代碼如算法1所示。

算法1 輸入?yún)?shù):執(zhí)行3.1得到的充電簇c1，c2…cn，多個(gè)MC輸出結(jié)果:各個(gè)MC的充電序列

1. 初始化MC參數(shù){ωN，ωe，ωd}2. for all MC i do 3. if MC接收到充電請(qǐng)求then 4. add充電請(qǐng)求into S 5. 計(jì)算簇的D(Ci，mj)min以及E residual＝E1＋E2＋…＋EN 6. 計(jì)算簇優(yōu)先級(jí)ψ(Cm)7. ψ(C m)max簇為候選充電簇8. else //MC無(wú)法處理過(guò)多的充電請(qǐng)求9. 計(jì)算其他MC的U(mj)10. 向U(m j)較大的MC發(fā)送幫助消息11. 由U(mj)較大的MC處理對(duì)應(yīng)優(yōu)先級(jí)較高的充電任務(wù)12. end if 13.end for

3.4 充電序列規(guī)劃

充電序列規(guī)劃的目標(biāo)就是根據(jù)所得到的節(jié)點(diǎn)簇的優(yōu)先級(jí)來(lái)決定MC的充電路線(即確定的充電次序)，使多個(gè)MC給節(jié)點(diǎn)簇補(bǔ)充能量時(shí)盡可能地減少自身移動(dòng)能耗，用有限的能量為傳感器補(bǔ)充更多的能量。從而減少失效節(jié)點(diǎn)數(shù)量、MC移動(dòng)距離，提高充電均衡性，延長(zhǎng)網(wǎng)絡(luò)生命周期，。

當(dāng)一個(gè)MC接收到多個(gè)充電請(qǐng)求時(shí)，首先將充電請(qǐng)求放入自身的充電服務(wù)池中，之后對(duì)充電請(qǐng)求進(jìn)行解析并計(jì)算其所在節(jié)點(diǎn)簇的優(yōu)先級(jí)。最后MC將各自要處理的充電請(qǐng)求與其對(duì)應(yīng)的優(yōu)先級(jí)保存在充電序列S q中，每次從序列中選取優(yōu)先級(jí)最大的節(jié)點(diǎn)簇C m作為候選充電簇，之后各個(gè)MC前往不同節(jié)點(diǎn)簇的充電駐點(diǎn)通過(guò)無(wú)線能量傳輸對(duì)簇中所有節(jié)點(diǎn)進(jìn)行充電。多MC充電序列規(guī)劃結(jié)果如圖4所示。

圖4 多MC協(xié)同充電序列規(guī)劃示例圖

3.5 算法描述

本文提出的MTORN算法具體流程如圖5所示。

圖5 算法框架圖

總之，MTORN策略主要通過(guò)以下3個(gè)步驟達(dá)到多個(gè)MC協(xié)同對(duì)網(wǎng)絡(luò)進(jìn)行充電的目標(biāo):首先，MTORN通過(guò)相交圓算法對(duì)網(wǎng)絡(luò)中的傳感器節(jié)點(diǎn)進(jìn)行分簇，再利用最短距離原則為各個(gè)充電簇設(shè)置最優(yōu)的充電駐點(diǎn)；其次，根據(jù)網(wǎng)絡(luò)的能耗以及MC自身移動(dòng)能耗合理估計(jì)網(wǎng)絡(luò)需要的MC數(shù)量，部署最優(yōu)數(shù)量的MC為多MC協(xié)同充電策略提供了基礎(chǔ)；最后，MC在接收到充電請(qǐng)求后根據(jù)節(jié)點(diǎn)簇的平均剩余能量以及距離劃分出請(qǐng)求簇的優(yōu)先級(jí)，每次選擇候選充電簇時(shí)，均選擇優(yōu)先級(jí)最高的節(jié)點(diǎn)簇，以最小化網(wǎng)絡(luò)中由于電量較低而失效的節(jié)點(diǎn)數(shù)量。另外，當(dāng)某個(gè)MC的充電任務(wù)超過(guò)其服務(wù)能力時(shí)，可以向其他相對(duì)空閑的MC發(fā)送幫助信息，提高充電的均衡性。

4 仿真

本文構(gòu)建了一個(gè)無(wú)線可充電傳感器網(wǎng)絡(luò)仿真環(huán)境，建立100 m×100 m的區(qū)域，并隨機(jī)部署50個(gè)～300個(gè)傳感器，MC在自身電量不足時(shí)回到基站處補(bǔ)充自身能量。實(shí)驗(yàn)仿真參數(shù)如表1所示。

表1 仿真參數(shù)

文使用Python實(shí)現(xiàn)了MTORN算法，并與HCCA[12]算法和Cellular[6]算法進(jìn)行性能對(duì)比和評(píng)估。HCCA算法是一種WRSN混合聚類充電算法(HCCA)，采用分層聚類和K-means聚類實(shí)現(xiàn)位置和能量感知，之后將充電行為形式化為任務(wù)，通過(guò)任務(wù)分割算法HCCA-TS調(diào)度MC進(jìn)行充電。Cellular算法利用相鄰的正六邊形單元格平等分割網(wǎng)絡(luò)，MC周期性移動(dòng)到單元格中心位置對(duì)范圍內(nèi)節(jié)點(diǎn)進(jìn)行充電。

4.1 移動(dòng)成本

本組實(shí)驗(yàn)討論各算法在不同節(jié)點(diǎn)數(shù)量和MC電池容量下的MC平均移動(dòng)成本情況，移動(dòng)成本是MC移動(dòng)的總路程。如圖6(a)所示，隨著節(jié)點(diǎn)數(shù)量的增多，三種算法的MC移動(dòng)成本均增加，這是因?yàn)殡S著節(jié)點(diǎn)數(shù)量增加，充電請(qǐng)求會(huì)增加，MC需消耗更多能量移動(dòng)，從而使得移動(dòng)成本增加。可以看出MTORN方案的移動(dòng)成本始終低于其他兩種方案。圖6(b)可以看出MC的移動(dòng)成本隨電池容量的增大而增加，這是因?yàn)楦蟮碾姵厝萘繒?huì)使MC在一個(gè)充電周期內(nèi)的移動(dòng)時(shí)間延長(zhǎng)，從而可以進(jìn)行更多的移動(dòng)。

圖6 移動(dòng)成本對(duì)比

4.2 節(jié)點(diǎn)死亡率

節(jié)點(diǎn)死亡率表示未及時(shí)得到能量補(bǔ)充而失效的節(jié)點(diǎn)占總節(jié)點(diǎn)的百分比。如圖7(a)所示，節(jié)點(diǎn)失效率隨著節(jié)點(diǎn)數(shù)量的增多而呈升高趨勢(shì)，這是由于節(jié)點(diǎn)數(shù)量增多時(shí)，向MC發(fā)送的充電請(qǐng)求也會(huì)增多，超過(guò)MC的服務(wù)能力時(shí)，死亡節(jié)點(diǎn)數(shù)量將會(huì)增加?？梢钥闯霰疚奶岢龅腗TORN方案的節(jié)點(diǎn)死亡率要低于HCCA和Cellular算法，這是由于本策略提出一種優(yōu)先級(jí)充電算法，MC會(huì)優(yōu)先選擇剩余電量較低的節(jié)點(diǎn)進(jìn)行充電，極大地避免了節(jié)點(diǎn)失效死亡。圖7(b)所示，MC電池容量較大時(shí)，MC可以在一個(gè)充電輪次中為更多節(jié)點(diǎn)補(bǔ)充能量，因此MC電池容量越大，節(jié)點(diǎn)死亡率越低。

圖7 節(jié)點(diǎn)死亡率對(duì)比

4.3 網(wǎng)絡(luò)生存時(shí)間

網(wǎng)絡(luò)生存時(shí)間指WRSN從開(kāi)始運(yùn)行到結(jié)束的時(shí)間，當(dāng)網(wǎng)絡(luò)中失效節(jié)點(diǎn)達(dá)到設(shè)定的閾值時(shí)，剩余的節(jié)點(diǎn)不足以組成連通的網(wǎng)絡(luò)，網(wǎng)絡(luò)停止運(yùn)行并計(jì)算生存時(shí)間。由圖8(a)可以看出，三種算法的網(wǎng)絡(luò)生存時(shí)間隨著節(jié)點(diǎn)數(shù)量的增加而降低。原因是節(jié)點(diǎn)數(shù)較高超過(guò)了MC的服務(wù)能力，MC無(wú)法滿足所有充電請(qǐng)求，使得失效節(jié)點(diǎn)數(shù)量增加，最終導(dǎo)致了網(wǎng)絡(luò)生存時(shí)間降低。在圖8(b)中，由于MC電池容量的增大能有效減少節(jié)點(diǎn)死亡率，因此網(wǎng)絡(luò)生存時(shí)間也相應(yīng)延長(zhǎng)?？梢钥吹紿CCA和Cellular算法的網(wǎng)絡(luò)生存時(shí)間始終低于MTORN。

圖8 網(wǎng)絡(luò)生存時(shí)間對(duì)比

4.4 MC數(shù)量

本組實(shí)驗(yàn)討論不同MC數(shù)量下的MC充電成本以及節(jié)點(diǎn)死亡率。如圖9(a)所示，MC數(shù)量增加，各個(gè)MC的移動(dòng)成本相應(yīng)降低。這是因?yàn)楫?dāng)MC數(shù)量增加時(shí)，多個(gè)MC可以協(xié)作完成充電任務(wù)，減少了移動(dòng)開(kāi)銷。在圖9(b)中，隨著MC數(shù)量增加，節(jié)點(diǎn)死亡率降低，這是因?yàn)楫?dāng)MC數(shù)量增加時(shí)，每個(gè)MC能共同處理更多的充電任務(wù)，更及時(shí)地為節(jié)點(diǎn)充電，因此節(jié)點(diǎn)死亡率下降。

圖9 MC數(shù)量變化情況

5 總結(jié)

本文提出了一種WRSNs中多MC協(xié)同的一對(duì)多充電策略，適用于具有密集節(jié)點(diǎn)的大規(guī)模WRSNs。本文目標(biāo)為，使多個(gè)MC在一對(duì)多充電方式下，協(xié)作完成對(duì)WRSNs的能量補(bǔ)充，最大化充電效率，降低節(jié)點(diǎn)死亡率。本文首先通過(guò)相交圓算法將WRSN中的傳感器節(jié)點(diǎn)劃分為若干個(gè)簇，利用最短距離原則確定各個(gè)簇的充電駐點(diǎn)位置。再通過(guò)能量約束平衡條件確定網(wǎng)絡(luò)需要的MC數(shù)量，之后MC根據(jù)簇的平均剩余能量和距離劃分優(yōu)先級(jí)，每個(gè)MC根據(jù)優(yōu)先級(jí)前往不同的簇并對(duì)簇內(nèi)多個(gè)傳感器節(jié)點(diǎn)同時(shí)進(jìn)行充電。仿真實(shí)驗(yàn)結(jié)果表明，與現(xiàn)有的一對(duì)多充電方案相比，MTORN方案能夠有效降低節(jié)點(diǎn)死亡率與MC移動(dòng)成本，延長(zhǎng)網(wǎng)絡(luò)生存時(shí)間。