章 豪，王 然

(杭州電子科技大學(xué) 計(jì)算機(jī)學(xué)院,浙江 杭州 310018)

在無線傳感器領(lǐng)域中，無線能量傳輸技術(shù)的出現(xiàn)與發(fā)展為解決傳感器節(jié)點(diǎn)充能問題提供了新的思路，保證了網(wǎng)絡(luò)的正常工作。無線能量傳輸技術(shù)與從所處環(huán)境中得到能量的技術(shù)不同[1-3]。無線能量傳輸技術(shù)通過在網(wǎng)絡(luò)中部署調(diào)度移動(dòng)充電小車對傳感器進(jìn)行無線充電，能夠更加穩(wěn)定地為網(wǎng)絡(luò)充能，提高了充電效率[4-6]。

隨著技術(shù)的進(jìn)步，將能量傳輸形式抽象為單對單充電和單對多充電兩種模型。單對單充電模型指充電器每次只對單個(gè)節(jié)點(diǎn)充電，該模型使用電感耦合技術(shù)[7-8]，其有效充電距離一般在20 cm以內(nèi)，需近距離進(jìn)行能量傳輸。單對多充電模型指充電器同時(shí)為多個(gè)節(jié)點(diǎn)充能，可分為全向無線充電和定向無線充電。全向無線充電采用磁共振耦合技術(shù)，不受充電方向限制。文獻(xiàn)[9]通過實(shí)驗(yàn)證明了能量可以在磁共振體之間進(jìn)行傳輸，并且不需要任何媒介。例如，為2 m外的一盞60 W白熾燈供電的效率可以達(dá)到40%。定向無線充電要求節(jié)點(diǎn)在一定的距離與角度范圍內(nèi)，該模型采用電磁波輻射技術(shù)，在能量傳輸及接收設(shè)備中使用高增益定向天線，提高了能量傳輸效率，使其覆蓋距離更遠(yuǎn)，例如毫米波蜂窩網(wǎng)絡(luò)[10]。

研究人員對于定向無線充電模型進(jìn)行了研究與應(yīng)用。文獻(xiàn)[10]研究了部署固定數(shù)量充電器的方式，最大化網(wǎng)絡(luò)中節(jié)點(diǎn)能夠接收到的充電效率。文獻(xiàn)[11]假設(shè)網(wǎng)絡(luò)所使用的節(jié)點(diǎn)接收能量也受方向限制，節(jié)點(diǎn)和充電器必須處于相對方向才能夠進(jìn)行能量傳輸。該研究解決的問題是不論節(jié)點(diǎn)朝著哪個(gè)方向都能夠接收到能量，并且接收功率不低于給定閾值。文獻(xiàn)[12～13]將充電器部署在距離網(wǎng)絡(luò)一定高度的平面上，通過對該平面進(jìn)行網(wǎng)格化，確定充電器的最佳部署位置。不同的是，文獻(xiàn)[12]只考慮節(jié)點(diǎn)能否被覆蓋到，優(yōu)化目標(biāo)是確保每個(gè)節(jié)點(diǎn)都能被覆蓋到，而文獻(xiàn)[13]加入了對節(jié)點(diǎn)能量消耗率和接收率的考慮，優(yōu)化目標(biāo)是確保每個(gè)節(jié)點(diǎn)的能量接收率不小于消耗率。

本文的研究基于定向充電模型，在保證無線可充電傳感器網(wǎng)絡(luò)持續(xù)運(yùn)行的情況下，最大化網(wǎng)絡(luò)累計(jì)充電增益的充電小車優(yōu)化調(diào)度問題。

1 網(wǎng)絡(luò)模型與假設(shè)

1.1 傳感器節(jié)點(diǎn)模型

在基于定向充電的傳感器網(wǎng)絡(luò)中隨機(jī)拋灑傳感器節(jié)點(diǎn)。傳感器節(jié)點(diǎn)皆具有數(shù)據(jù)感應(yīng)、數(shù)據(jù)生成和傳輸、能量接受的功能。網(wǎng)絡(luò)中傳感器節(jié)點(diǎn)可分為可充電節(jié)點(diǎn)和匯聚節(jié)點(diǎn)?？沙潆姽?jié)點(diǎn)負(fù)責(zé)感應(yīng)監(jiān)控環(huán)境生成數(shù)據(jù)，通過多跳路由把感知的數(shù)據(jù)傳遞給匯聚節(jié)點(diǎn)。

環(huán)境感應(yīng)、數(shù)據(jù)生成與傳輸是傳感器節(jié)點(diǎn)的主要能耗方式。假設(shè)傳感器節(jié)點(diǎn)數(shù)據(jù)對1 bit數(shù)據(jù)進(jìn)行感應(yīng)，傳輸和接收所需能量為ec，根據(jù)文獻(xiàn)[14～ 15]有

(1)

其中，e0表示傳感器用于數(shù)據(jù)感知、數(shù)據(jù)編碼和調(diào)制的能耗；e1表示單位比特的能量損失系數(shù)；dr表示傳感器之間的傳送數(shù)據(jù)距離；α表示路徑損耗系數(shù)(一般為2～4)，本文假設(shè)各個(gè)節(jié)點(diǎn)獲得信息速率相等。

1.2 充電小車模型

(2)

節(jié)點(diǎn)的能量接收功率可以基于Friis方程[16]計(jì)算

(3)

其中，Pr是能量接受功率；Pout是能量發(fā)射功率；L是路徑耗損因子；GT是發(fā)射天線增益；GR是接收天線增益；λ是發(fā)射波的波長；η是整流器效率；β是用于調(diào)整自由方程的參數(shù)；d是發(fā)射與接收天線之間的距離。

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

如圖1所示，在L×L的區(qū)域中任意隨機(jī)拋灑n個(gè)傳感器節(jié)點(diǎn)S={s1,s2,…,sn}。網(wǎng)絡(luò)中任意節(jié)點(diǎn)總?cè)萘繛镋max，m輛移動(dòng)充電小車集合為MC={mc1,mc2,…,mcm}，集合中任意小車的總電量為Cmc，其輸出功率為Pmc。靜止基站b位于網(wǎng)絡(luò)平面的中心位置。為確保網(wǎng)絡(luò)持續(xù)運(yùn)行，充電小車以T為周期對傳感器節(jié)點(diǎn)進(jìn)行周期性充能。

圖1 定向充電傳感器網(wǎng)絡(luò)模型Figure 1. Directional charging wireless sensor network model

2 問題定義

無線傳感器網(wǎng)絡(luò)中等待充電感器節(jié)點(diǎn)集合為S={s1,s2,…,sn}，傳感器節(jié)點(diǎn)最高電量Emax記為Cv，剩余電量為Rv，集合中任意節(jié)點(diǎn)si∈S的能量接收速率為γi，能耗速率為pi。集合MC={mc1,mc2,…,mcm}為充電小車集合，集合中任意小車mci∈MC的總電量均為Cmc，其輸出功率為Pmc，通過效用函數(shù)f(x)模擬傳感器充能，候選?？奎c(diǎn)集合A={a1,a2,…,an}，候選?？奎c(diǎn)aj∈A對應(yīng)傳感器節(jié)點(diǎn)si∈S的位置。b為基站給小車充能。每個(gè)候選?？奎c(diǎn)aj∈A的包含的傳感器節(jié)點(diǎn)記為Sai，給Sai充電需要消耗Τai的時(shí)間。

從基站b出發(fā)，充電小車mck∈MC中途?？吭赼j∈A，對Sai中的傳感器節(jié)點(diǎn)進(jìn)行定向充電，充電周期為T，完成充能后返回基站b進(jìn)行充電。在保證傳感器網(wǎng)絡(luò)持續(xù)運(yùn)行的前提下，最大化網(wǎng)絡(luò)累計(jì)充電增益。該問題形式化定義為

(4)

(5)

(6)

ηajyaj>δ,j∈S

(7)

yaj≤ua,j∈S

(8)

(9)

Tpizik=Taγizik,i∈Sa

(10)

Emax-(T-Ta)·pi≥Emin,i∈Sa

(11)

xijk,yia,zik∈{0,1},a∈A,k∈MC

(12)

3 近似算法

3.1 充電方向選擇算法

充電方向選擇是指在當(dāng)前候選?？奎c(diǎn)下選擇充電小車的充電方向，具體過程是：首先充電小車以每個(gè)不同的節(jié)點(diǎn)為一個(gè)邊界逆時(shí)針旋轉(zhuǎn)；然后確定每個(gè)朝向覆蓋到的節(jié)點(diǎn)集合并計(jì)算每個(gè)方向的覆蓋效用，如圖2所示。

圖2 定向充電方向選擇過程Figure 2.Process of directional charging direction selection

偽代碼如下：

算法1最大覆蓋效用充電方向選擇算法。

輸入傳感器集合O={o1,o2,…,oN}；充電器位置(cx,cy)；充電器的覆蓋距離D；覆蓋角度為A。

1.OCS=?，i=0；

2.當(dāng)i

3.計(jì)算傳感器Oi與充電小車的歐幾里得距離di，如果di

4.循環(huán)結(jié)束；

5.如果OCS=?，算法結(jié)束，否則繼續(xù)第6步；

6.L=len(OCS)；

7.計(jì)算集合OCS中的傳感器與充電器位置形成的夾角集合θ={θ1,θ2,…,θL}，并且將集合OCS中的傳感器按照對應(yīng)的夾角大小升序排序；

8. CU=?，k=0，當(dāng)i

9.把充電器覆蓋扇形px的始邊擺于OCS[k]；

10.將終邊置于(θk+A)%360；

11. CU=CU∪{CUk}，k=k+1；

12.循環(huán)結(jié)束。

輸出MCU和Umax。

3.2 停靠點(diǎn)選擇算法

?？奎c(diǎn)選擇算法調(diào)用了方向選擇算法，將二位傳感網(wǎng)絡(luò)劃分為網(wǎng)格，以網(wǎng)格的頂點(diǎn)作為候選?？奎c(diǎn)位置。充電小車每次停下來只選擇一個(gè)方向進(jìn)行充電，充電器的覆蓋范圍是一個(gè)半徑為D的90°扇形，只有滿足每個(gè)扇形可以對網(wǎng)絡(luò)全覆蓋的前提下才可能確保沒有節(jié)點(diǎn)遺漏。

偽代碼如下：

算法2最大化覆蓋效用總和?？奎c(diǎn)選擇算法。

輸入傳感器集合O={o1,o2,…,oN}。包括每個(gè)節(jié)點(diǎn)的索引值和對應(yīng)的坐標(biāo)點(diǎn)；充電器的覆蓋距離為D；覆蓋角度為A。

1.對二維傳感器網(wǎng)絡(luò)進(jìn)行格式化，以網(wǎng)絡(luò)交點(diǎn)作為候選停靠點(diǎn)，獲得充電器候選停止位置集合CS={cs1,cs2,…,csi,…,csn}；

2.令最終被選的停止位置集合FCS←?，令其對應(yīng)的停止位置覆蓋集合為Ns←?；

3.當(dāng)O≠?并且CS≠?時(shí)；

4.AUmax=0，AMCU=?，csmax=?，i=0；

5.當(dāng)i

6.調(diào)用方向選擇算法，得到csi位置最大覆蓋效用值Umax及其最大覆蓋效用節(jié)點(diǎn)集合MCU；

7.若Umax>AUmax，則AUmax=Umax，AMCU=MCU，csmax=csi；

8.循環(huán)結(jié)束；

9.如果AUmax=0，循環(huán)結(jié)束，否則繼續(xù)下一步；

10.FCS=FCS∪{csmax}，Ns=Ns∪{AMCU}，CS=CS-{csmax}，O=O-{oi/oi∈AMCU}

11.循環(huán)結(jié)束。

輸出FCS和Ns。

3.3 路徑規(guī)劃算法

(1)Pj的能耗之和不大于充電小車的最大容量CMC，即

(13)

(2)pj路徑上總的消耗時(shí)間小于小車充電周期T，即

(14)

(15)

偽代碼如下：

算法3基于分解TSP的路徑規(guī)劃算法。

輸入?？奎c(diǎn)集合D，充電小車集合MC，在?？奎c(diǎn)a處對節(jié)點(diǎn)j的充電效率ηaj，充電小車容量Cmc，服務(wù)基站b，充電周期T，TSP路徑p=(b,Π1,Π2,…,Πn,b)。

1.當(dāng)p≠?時(shí)；

4.獲得第j條閉合回路用p=(b,Π1,Π2,…,Πn,b)

5.從TSP路徑中去掉pj包含的?？奎c(diǎn)，j←j+1；

6.結(jié)束循環(huán)。

輸出充電小車mcj的充電路徑pj。

4 網(wǎng)絡(luò)規(guī)模分析

分析計(jì)算網(wǎng)絡(luò)對應(yīng)所需充電小車的數(shù)量，首先要對單小車可服務(wù)網(wǎng)絡(luò)規(guī)模進(jìn)行分析計(jì)算。假設(shè)小車充電隊(duì)列集合為p=(Π0,Π1,Π2,…,Πn,Π0)，集合中Π0是基站位置，Π0i(1≤i≤n)是傳感器si∈S所在位置。在充電隊(duì)列p=(Π0,Π1,Π2,…,Πn,Π0)中任意相鄰節(jié)點(diǎn)間最大距離為lmax。為了保證傳感器網(wǎng)絡(luò)的持久化運(yùn)行，需要滿足如下要求：

(1)單位充電周期內(nèi)，充電小車對節(jié)點(diǎn)充電的總電量不小于隊(duì)列中節(jié)點(diǎn)消耗的總電量，即

(16)

其中，v是充電小車的移動(dòng)速率；T是充電周期；pMC是充電小車充電功率；n是節(jié)點(diǎn)數(shù)量；c是節(jié)點(diǎn)的平均能耗速率，推導(dǎo)得

(17)

(18)

因?yàn)閜MC≥c，所以f′(t)≥0，即單個(gè)充電小車服務(wù)的節(jié)點(diǎn)數(shù)與充電周期時(shí)長正相關(guān)；

(2)單位充電周期內(nèi)，所有節(jié)點(diǎn)的剩余能量不低于節(jié)點(diǎn)正常工作的最低電量。假設(shè)節(jié)點(diǎn)的初始電量為滿電量Emax，所以周期長度T有

(19)

(20)

5 模擬實(shí)驗(yàn)

在100 m×100 m、200 m×200 m和300 m×300 m的區(qū)域中分別多次隨機(jī)拋灑50、100、150、200、250、300、350、400、450、500個(gè)節(jié)點(diǎn)，從網(wǎng)格大小、網(wǎng)絡(luò)規(guī)模、充電形式等因素來分析其對充電小車能量利用率與累計(jì)充電增益的影響。無線充電小車依照前文所述模型和算法對節(jié)點(diǎn)進(jìn)行充電。

在100 m×100 m的區(qū)域中多次分別隨機(jī)拋灑100、300、500個(gè)節(jié)點(diǎn)，改變網(wǎng)格大小，分析對充電小車充電效率的影響。

圖3 網(wǎng)格大小對充電效率影響Figure 3. Effect of grid size of charging efficiency

圖3顯示了隨著網(wǎng)格大小的減小，充電小車的充電能量利用率正在提高。當(dāng)節(jié)點(diǎn)數(shù)量為100，網(wǎng)格大小由7 m減少到1 m時(shí)，充電小車的充電效率提高了近38%。當(dāng)節(jié)點(diǎn)數(shù)為300，網(wǎng)格大小由7 m減小到1 m時(shí)，充電小車的充電效率提高了近27%。當(dāng)節(jié)點(diǎn)數(shù)為500，網(wǎng)格大小由7 m減小到1 m時(shí)，充電小車的充電效率提高了近23%。由此可見，隨著節(jié)點(diǎn)數(shù)的增加，充電效率的提升有所減緩，當(dāng)前網(wǎng)絡(luò)規(guī)模下網(wǎng)格大小為1 m時(shí)效果最佳。

圖4 網(wǎng)絡(luò)規(guī)模對于充電累計(jì)增益的影響Figure 4. Effect of the size of network on the charging efficiency

由圖4可知，隨著節(jié)點(diǎn)數(shù)量的增加充電小車的能量利用率在逐漸提高。由于節(jié)點(diǎn)的數(shù)量增加，因此充電小車每次能夠覆蓋到節(jié)點(diǎn)數(shù)增加，因此更多的能量被節(jié)點(diǎn)接收，能量利用率得到了提高。同時(shí)，在節(jié)點(diǎn)數(shù)量不變區(qū)域變大時(shí)，充電小車的能量利用率在降低，因?yàn)楣?jié)間的距離變大，充電小車消耗在路上的能量增多，導(dǎo)致充電小車能量利用率降低。

圖5 節(jié)點(diǎn)數(shù)量對于充電累計(jì)增益的影響Figure 5. Effect of the number of nodes on the cumulative charging utility

圖5顯示了在100 m×100 m的區(qū)域不同節(jié)點(diǎn)數(shù)量對于網(wǎng)絡(luò)累計(jì)充電增益的影響。在相同節(jié)點(diǎn)數(shù)量下，定向充電的網(wǎng)絡(luò)累計(jì)充電增益高于全向充電，且隨著節(jié)點(diǎn)數(shù)量的增加同種充電方式的網(wǎng)絡(luò)累計(jì)充電增益在增加，在200～250個(gè)節(jié)點(diǎn)的情況下效果尤為顯著。而當(dāng)節(jié)點(diǎn)數(shù)大于250個(gè)以后，全向充電的增幅低于定向充電，說明此時(shí)全向充電的充能利用率不如無線充電。

6 結(jié)束語

本文研究了基于定向充電模型，在保證無線可充電傳感器網(wǎng)絡(luò)持久運(yùn)行的情況下，最大化網(wǎng)絡(luò)累計(jì)充電增益的優(yōu)化調(diào)度問題。針對該問題，本文提出了近似算法。近似算法包括3個(gè)部分：(1)基于最大化覆蓋效用的方向選擇算法；(2)基于方向選擇的最大化覆蓋累計(jì)效用的停靠點(diǎn)選擇算法；(3)基于TSP的路徑規(guī)劃算法為充電小車規(guī)劃移動(dòng)路徑。通過仿真實(shí)驗(yàn)對比不同的充電策略。實(shí)驗(yàn)結(jié)果顯示，相比全向充電，本文提出的充電策略可以明顯提升網(wǎng)絡(luò)的累積充電增益。定向充電模型是無線可充電傳感器網(wǎng)絡(luò)無線充電領(lǐng)域中新興的模型，基于定向充電模型還有很多新的研究方向，例如如何延長網(wǎng)絡(luò)生命周期等。