孫 奧，郭 磊，馮 勇?

(1.昆明理工大學(xué)云南省計算機(jī)技術(shù)應(yīng)用重點(diǎn)實(shí)驗(yàn)室，昆明650500；2.云南藝術(shù)學(xué)院學(xué)生工作部(處)，昆明650500)

目前，隨著無線可充電傳感器網(wǎng)絡(luò)(WRSN)的發(fā)展，涌現(xiàn)出許多卓有成效的無線充電方案[1-3]。在WRSN中傳感器節(jié)點(diǎn)是通過自身攜帶的電池來提供能量。由于電池的儲能容量有限，所以WRSN的壽命有限。因此，如何延長網(wǎng)絡(luò)的生存時間一直是提升網(wǎng)絡(luò)性能瓶頸的關(guān)鍵因素之一。

在實(shí)際應(yīng)用時，尋找MC的移動路徑使得MC移動距離最短并且能給更多的節(jié)點(diǎn)充電十分重要。由于多跳無線能量傳輸技術(shù)的傳輸效率提高受中繼器位置的影響，因此本文主要研究在WRSN中的諧振中繼器位置確定問題。其中，諧振中繼器由低成本的銅線圈制造[4]，能量經(jīng)過5～6跳到達(dá)目的節(jié)點(diǎn)時，充電效率可達(dá)到50%～70%[5]。通過在網(wǎng)絡(luò)中合理地部署中繼節(jié)點(diǎn)(RN)，其能量可透過周圍空間的幾何體來給目標(biāo)節(jié)點(diǎn)補(bǔ)充能量或給有距離限制的目標(biāo)節(jié)點(diǎn)補(bǔ)充能量[6]。文獻(xiàn)[7]利用正六邊形單元分割網(wǎng)絡(luò)，能量以多跳的方式給每個單元格內(nèi)的傳感器節(jié)點(diǎn)補(bǔ)充能量。該方法沒有考慮RN的放置問題，增加了MC的充電成本，為了解決該問題，本文通過參考文獻(xiàn)[8]，提出利用三角形外接圓性質(zhì)來解決RN位置確定問題并在WRSN中合理部署RN來給具有相同諧振頻率的多個傳感器補(bǔ)充能量[9]。

本文其他部分組織如下，第一部分介紹相關(guān)工作。第二部分概述了網(wǎng)絡(luò)模型。第三節(jié)中詳細(xì)描述了基于諧振中繼器的多跳充電算法。第四部分通過模擬實(shí)驗(yàn)來評估TMWRN的性能。最后是本文的總結(jié)。

1 相關(guān)工作

本部分簡要介紹WRSN中單對單充電方案和單對多充電方案。

單對單充電方案，指每次只對一個傳感器節(jié)點(diǎn)充電。文獻(xiàn)[10]提出基于最小支撐樹的TSP方法確定MC的充電路徑，最大化系統(tǒng)吞吐量。Lin等人[11]提出在按需充電體系結(jié)構(gòu)中使用時空調(diào)度算法(TSCA)，但沒有考慮將因得不到能量補(bǔ)充而失效的節(jié)點(diǎn)插回路徑。

單對多充電方案，合理布置MC的充電位置對RN充電范圍內(nèi)的多個節(jié)點(diǎn)充電。文獻(xiàn)[4]提出了一種混合數(shù)據(jù)采集策略，并提供理論分析。文獻(xiàn)[8]通過合并分布式波束提高無線能量傳輸效率。文獻(xiàn)[12]同時考慮了數(shù)據(jù)傳輸、流量選擇、無線電功率傳輸?shù)纫蛩?，并將其歸納為能量補(bǔ)充優(yōu)化問題，開發(fā)一種啟發(fā)式算法解決NP-hard問題。

單對單充電方案存在著充電效率不高、充電距離受限和網(wǎng)絡(luò)生存時間短等問題。多跳能量補(bǔ)充方法大多以傳感器節(jié)點(diǎn)作為中繼器，受傳感器節(jié)點(diǎn)部署密度以及MC有效充電距離的限制。因此本文提出在網(wǎng)絡(luò)中部署一定數(shù)量的廉價的諧振中繼器以增加傳感器節(jié)點(diǎn)獲得多跳無線充電的機(jī)會。

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

如圖1所示，WRSN由諧振中繼器節(jié)點(diǎn)(RN)，固定的基站(BS)，移動充電裝置(MC)，傳感器節(jié)點(diǎn)(SN)構(gòu)成。每個SN產(chǎn)生的數(shù)據(jù)信息經(jīng)過多跳路徑路由到BS。本文假設(shè)MC裝有大容量電池和無線能量發(fā)送裝置與接收裝置，并且具有智能通信、計算和移動的能力，MC可以在BS處補(bǔ)充電量。BS擁有足夠的電量，同時它能夠給MC傳遞信息。RN的充電范圍設(shè)定為R(R＝3 m)。

本文假設(shè)，MC在給SN充電過程中不能被搶斷。初始標(biāo)記(mark＝-1)表示孤立節(jié)點(diǎn)，當(dāng)mark＝k(k表示RN下標(biāo))表示第k個SN在RNk的充電范圍內(nèi)。MC在充電過程中可以接收來自基站匯總的節(jié)點(diǎn)充電請求。如果SN的能量值低于設(shè)定的能量閾值，SN直接發(fā)送數(shù)據(jù)給BS。BS和MC直接可以直接通訊。MC從當(dāng)前位置開始計算，以v(m/s)的速度移動到距離它最近的SN位置。MC在給SN充電過程中能量以多跳的方式給多個SN同時進(jìn)行充電。其中，SN的功率接收速率為ε，閾值為α。在充電的過程中，SN的ε不能小于α，ε隨著充電距離的增大而減小。每次充電完成后，MC選擇距離它最近的充電請求節(jié)點(diǎn)進(jìn)行充電。

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

3 基于諧振中繼器的多跳充電算法

本部分首先研究了中繼節(jié)點(diǎn)位置確定問題，然后基于中繼節(jié)點(diǎn)在網(wǎng)絡(luò)中的部署提出多跳充電算法。

3.1 中繼節(jié)點(diǎn)位置確定

假設(shè)RN在二維平面的原點(diǎn)位置，RN的最大充電半徑為R。網(wǎng)絡(luò)中的RN和SN以及無線鏈路的邊表示為:

式中:Ψ表示網(wǎng)絡(luò)中的圖，U表示網(wǎng)絡(luò)中所有節(jié)點(diǎn)的集合，E表示網(wǎng)絡(luò)中節(jié)點(diǎn)之間通信的邊，S表示傳感器節(jié)點(diǎn)集合，Z表示中繼器節(jié)點(diǎn)集合。

網(wǎng)絡(luò)中Eij滿足以下條件:

式中:R是RN的最大充電半徑，Lij表示節(jié)點(diǎn)i到節(jié)點(diǎn)j之間的距離。存在恒成立。

網(wǎng)絡(luò)的連通性可以用如下公式[13]計算:

為了提高網(wǎng)絡(luò)中RN的充電覆蓋率，本文結(jié)合三角形外接圓的性質(zhì)和兩節(jié)點(diǎn)的中點(diǎn)性質(zhì)來劃分二維平面并確定RN的位置。

3.1.1 三個節(jié)點(diǎn)可構(gòu)成三角形

在WRSN中，將RN部署在三角形的外心位置可以使網(wǎng)絡(luò)中節(jié)點(diǎn)覆蓋率[14]達(dá)到最大。

如圖2所示，假設(shè)任意的三個節(jié)點(diǎn)坐標(biāo)為UN1＝(x1，y1，-1)，UN2＝(x2，y2，-1)，UN3＝(x3，y3，-1)，并有(UN1，UN2，UN3∈S，-1 表示該節(jié)點(diǎn)不屬于任何中繼充電范圍)，三邊分別為 d1，d2，d3∈E，中繼節(jié)點(diǎn)為RNi，由歐幾里德距離公式可得:

圖2 任意三角形的外接圓

并且存在

為了計算任意三角形的外接圓半徑，本文給出以下證明:

在二維平面內(nèi)，存在任意的一個三角形UN1＆UN2＆UN3，三條邊長分別為 d1，d2，d3，存在角α，β，外接圓圓心為 RNi＝ (xi，yi)，外接圓的半徑為r。

由余弦定理可得:

依據(jù)海倫公式化簡可得，令

式中:s表示三角形的面積。

本文主要目標(biāo)是中繼器的充電范圍能覆蓋盡可能多的SN，換言之，就是尋找r最接近R的三角形外接圓，即

該問題轉(zhuǎn)化為計算函數(shù)gf(l)的最接近于1的值，從而可以確定三角形的三個節(jié)點(diǎn)坐標(biāo)。因此，任意三角形的外接圓圓心計算如下:

根據(jù)三角形外接圓的圓心到三角形的三個頂點(diǎn)距離 相 等 可 知:線 段 UN1＆RNi＝ UN2＆RNi＝UN3＆RNi，可得

三角形的外接圓圓心坐標(biāo)(RN的位置)為RNi＝(xi，yi):

3.1.2 三個節(jié)點(diǎn)不可構(gòu)成三角形

若三個節(jié)點(diǎn)不能構(gòu)成的三角形外接圓半徑r＞R，則將RN部署在兩節(jié)點(diǎn)的中點(diǎn)位置，另一個節(jié)點(diǎn)為孤立點(diǎn)。

由于式(3)是一個離散函數(shù)。由文獻(xiàn)[15]可得，將離散函數(shù)轉(zhuǎn)換為連續(xù)函數(shù)，并對連續(xù)函數(shù)進(jìn)行平滑操作來確定中繼器的最大充電位置。我們定義平滑性能函數(shù)是連續(xù)的并且具有平滑的特性[13]，同時考慮節(jié)點(diǎn)的覆蓋率和節(jié)點(diǎn)之間的通信，具體函數(shù)定義為:

式中:ψ′表示從第i個SN開始尋找網(wǎng)絡(luò)中的最大邊，ψ′i表示從 i到 j的最大邊的倒數(shù)，函數(shù) φ(ψ′)表示重定義的網(wǎng)絡(luò)圖ψ′:

函數(shù)φ(ψ′)是對離散函數(shù)Φ(Ψ)做了連續(xù)平滑操作，提高確定中繼器的位置信息準(zhǔn)確率。由文獻(xiàn)[16]可得，本文考慮 r＝R，在 d1＋d2≤2R 時，我們將RN在UN1與 UN2的中間位置；d1＋d2＞2R 時，將距離上一個RN最近的節(jié)點(diǎn)孤立，以另外一個節(jié)點(diǎn)作為參照點(diǎn)繼續(xù)確定RN的位置。其中，孤立節(jié)點(diǎn)不屬于任何中繼器充電范圍。若SN的電量低于設(shè)置的閾值時，MC直接給低電量節(jié)點(diǎn)充電。

3.1.3 中繼節(jié)點(diǎn)位置確定算法

如圖3(a)所示，在30 m×30 m的區(qū)域隨機(jī)散列50個SN，BS位于原點(diǎn)位置，MC從BS位置移動。則RN位置確定算法描述如下:

①在U中確定距離MC最近的傳感器節(jié)點(diǎn)A(A∈U)，確定距離A最近的節(jié)點(diǎn)傳感器節(jié)點(diǎn)B(B∈U)，計算U中除A、B以外，其他節(jié)點(diǎn)分別與邊AB構(gòu)成的三角形是否滿足式(14)。若滿足，則三角形外接圓的圓心坐標(biāo)為RN部署的位置，并將RN充電范圍內(nèi)的傳感器節(jié)點(diǎn)標(biāo)記(mark＝i，i為該RN下標(biāo))，若不滿足則跳轉(zhuǎn)步驟2；

②判斷AB的長度d是否大于2R，若成立則跳轉(zhuǎn)步驟3，若不成立則將RN部署在AB的中點(diǎn)位置，并標(biāo)記該RN充電范圍內(nèi)的SN(mark＝i，i為該RN下標(biāo))。

③將節(jié)點(diǎn)A孤立(mark＝-1)，以節(jié)點(diǎn)B為參照點(diǎn)，重復(fù)步驟1直到網(wǎng)絡(luò)中所有的傳感器節(jié)點(diǎn)都被訪問過為止。

圖3 算法描述

3.2 多跳充電算法描述

在多跳無線能量補(bǔ)充算法中，為了減少M(fèi)C的充電成本，傳感器節(jié)點(diǎn)可以中繼能量給它的鄰居節(jié)點(diǎn)。因?yàn)闊o線充電效率隨中繼次數(shù)衰減，并且隨著中繼距離增大，效率急劇下降[4]，因此本文能量補(bǔ)充算法設(shè)計如下:

Step 1 在無線可充電傳感器網(wǎng)絡(luò)區(qū)域部署中繼節(jié)點(diǎn)。

Step 2 計算服務(wù)池S中，MC移動到每個請求節(jié)點(diǎn)i的時間TMC→i和最大充電延遲Ti(t)，

式中:v為MC的移動速度，Ei(ts)為節(jié)點(diǎn)i在ts時刻的剩余能量，ri為節(jié)點(diǎn)i的能量消耗速率。

若TMC→i＞Ti(t)，則節(jié)點(diǎn)失效并從S中刪除該節(jié)點(diǎn)請求信息。

若 TMC→i＜Ti(t)，將該請求節(jié)點(diǎn) i存入充電集合G中，同時檢查節(jié)點(diǎn)i的mark值是否為-1，若是則重復(fù)Step 2；否則計算出節(jié)點(diǎn)i所屬的中繼節(jié)點(diǎn)k，繼續(xù)檢查服務(wù)池 S中 mark值為 k的節(jié)點(diǎn)，將其加入集合Ki中。直到遍歷完S中所有的請求節(jié)點(diǎn)。

Step 3 若充電集合G為空，結(jié)束；若不為空，首先選擇G中距離MC最近的請求節(jié)點(diǎn)i作為充電目標(biāo)；其次，檢查集合Ki是否為空，若為空，MC直接對節(jié)點(diǎn)i充電；若不為空，MC對節(jié)點(diǎn)i充電，然后節(jié)點(diǎn)i通過諧共振將能量轉(zhuǎn)發(fā)到它所屬的中繼節(jié)點(diǎn)k；最后中繼節(jié)點(diǎn)將能量轉(zhuǎn)發(fā)給Ki內(nèi)的其他請求節(jié)點(diǎn)。重復(fù)Step 3。

4 仿真實(shí)驗(yàn)

本部分，本文通過在C＋＋仿真平臺上與Cellular MWRN[7]和NJNP[17]對比來說明TMWRN算法的有效性。主要從平均覆蓋節(jié)點(diǎn)數(shù)、錨點(diǎn)個數(shù)，充電成本，節(jié)點(diǎn)失效率進(jìn)行對比分析。

假設(shè)基站(BS)和100個傳感器節(jié)點(diǎn)(SN)隨機(jī)地部署在30 m×30 m的區(qū)域中，MC部署在基站處，其中MC的移動速度為v＝3 m/s，所有的SN和RN具有相同的數(shù)據(jù)接受能力，RN的轉(zhuǎn)發(fā)能量范圍為R＝3 m的圓，每個SN的初始能量為10 000 units/s，當(dāng)能量低于閾值時，節(jié)點(diǎn)發(fā)送充電請求。SN的轉(zhuǎn)發(fā)能量范圍為r＝3 m。表1列出了具體的仿真參數(shù)。

表1 仿真參數(shù)

4.1 平均覆蓋節(jié)點(diǎn)數(shù)

圖4表示節(jié)點(diǎn)數(shù)量增多，單元格平均覆蓋的節(jié)點(diǎn)數(shù)量呈線性增加趨勢。圖中反映出本文所提TMWRN覆蓋的節(jié)點(diǎn)更多。

圖4 節(jié)點(diǎn)數(shù)量vs平均覆蓋節(jié)點(diǎn)數(shù)

4.2 充電成本

圖5(a)反映了當(dāng)節(jié)點(diǎn)數(shù)量小于125時，充電成本呈遞增趨勢，節(jié)點(diǎn)數(shù)量大于125時，充電成本呈遞減趨勢，這是因?yàn)殡S著節(jié)點(diǎn)數(shù)量的增多，節(jié)點(diǎn)死亡率變大，MC來不及給網(wǎng)絡(luò)中節(jié)點(diǎn)充電而導(dǎo)致移動成本降低。從圖中可以看出TMWRN的充電成本小于算法Cellular MWRN。圖5(b)反映了隨著充電速率的增大，網(wǎng)絡(luò)的充電成本呈遞增趨勢。在充電速率一定的條件下，本文所提TMWRN的充電成本更低。

4.3 節(jié)點(diǎn)失效率

圖6(a)表示隨著節(jié)點(diǎn)數(shù)量的增多，MC充電負(fù)擔(dān)加重，使節(jié)點(diǎn)失效率增大。圖6(b)表示三種算法的節(jié)點(diǎn)失效率隨著充電速率的增加呈遞減趨勢，但是遞減的程度有所不同。這是因?yàn)殡S著充電速率增大，增大MC的充電能力，使節(jié)點(diǎn)失效率降低。從圖看出，TMWRN性能更好。

圖6 節(jié)點(diǎn)失效率對比

圖7 網(wǎng)絡(luò)生存時間對比

4.4 網(wǎng)絡(luò)生存時間

本文設(shè)置當(dāng)節(jié)點(diǎn)失效率達(dá)到一定的閾值就停止網(wǎng)絡(luò)工作并計算網(wǎng)絡(luò)的生存時間。圖7(a)表示隨著節(jié)點(diǎn)數(shù)量的增多，網(wǎng)絡(luò)的生存時間呈遞減趨勢。圖7(b)反映了隨著充電速率的增大網(wǎng)絡(luò)生存時間呈遞增趨勢?？梢钥闯鯰MWRN有明顯的優(yōu)勢。

5 總結(jié)

本文研究了無線傳感器網(wǎng)絡(luò)能量補(bǔ)充問題，提出了一種基于諧振中繼的可充電傳感器網(wǎng)絡(luò)移動能量補(bǔ)充方法(TMWRN)。該方案在考慮充電成本的前提下，利用基于三角形外接圓的中繼器部署方案實(shí)現(xiàn)單對多在線充電，使得MC更加公平的響應(yīng)傳感器節(jié)點(diǎn)充電請求。大量仿真實(shí)驗(yàn)表明，TMWRN可以有效地降低MC的充電成本和節(jié)點(diǎn)失效率，達(dá)到了延長網(wǎng)絡(luò)壽命的目的。