吳 淵， 馮 勇， 郭 磊， 楊 心

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

0 引 言

無(wú)線傳感器網(wǎng)絡(luò)中節(jié)點(diǎn)受成本、體積等因素的限制，為其配置的電池容量有限[1，2]，能量問(wèn)題是限制無(wú)線傳感器網(wǎng)絡(luò)生存周期和性能的最主要因素。當(dāng)前發(fā)展的無(wú)線充電技術(shù)被普遍認(rèn)為是突破無(wú)線傳感器網(wǎng)絡(luò)能量限制的最具前景的技術(shù)，無(wú)線可充電傳感器網(wǎng)絡(luò)(wireless rechargeable sensor networks,WRSN)應(yīng)運(yùn)而生，許多卓有成效的方案[3,4]被提出。根據(jù)所采用無(wú)線充電技術(shù)的不同，WRSN能量補(bǔ)充方案可以分為單對(duì)單和單對(duì)多充電兩種類型。單對(duì)單充電方案簡(jiǎn)單靈活，但是一次只能給一個(gè)節(jié)點(diǎn)充電，存在著充電效率不高、充電距離受限等方面的問(wèn)題。單對(duì)多充電方案[5,6]可以同時(shí)給網(wǎng)絡(luò)中多個(gè)節(jié)點(diǎn)充電，且利用諧振中繼器可以實(shí)現(xiàn)多跳充電，可顯著延伸充電距離、提高網(wǎng)絡(luò)的能量補(bǔ)充效率。目前的WRSN單對(duì)多充電方案[9～11]中,每個(gè)傳感器節(jié)點(diǎn)上都配備一個(gè)諧振中繼器，利用移動(dòng)充電裝置(mobile charger,MC)移動(dòng)到合適的位置(即錨點(diǎn))以單跳或多跳方式同時(shí)給多個(gè)傳感器節(jié)點(diǎn)補(bǔ)充能量。

文獻(xiàn)[7]利用相鄰的正六邊形單元格平等分割網(wǎng)絡(luò)，傳感器節(jié)點(diǎn)被覆蓋在單元格內(nèi)，MC周期性移動(dòng)到單元格中心位置來(lái)實(shí)現(xiàn)能量的多跳無(wú)線傳輸。文獻(xiàn)[8]提出了一

種多跳充電模型，證明能量中繼4～5跳可以實(shí)現(xiàn)50 %以上的充電效率。文獻(xiàn)[9]提出了能量可以同時(shí)傳輸給多個(gè)充電請(qǐng)求節(jié)點(diǎn)，證明了MC給多個(gè)節(jié)點(diǎn)充電的總輸出效率比給單個(gè)節(jié)點(diǎn)充電的總輸出效率更高。文獻(xiàn)[10]針對(duì)節(jié)點(diǎn)的稀疏部署和密集部署分別提出了不同的解決方案。節(jié)點(diǎn)稀疏部署的方案是利用虛擬節(jié)點(diǎn)作為無(wú)線能量路由器，運(yùn)用多跳無(wú)線充電方式來(lái)提高能量的傳輸效率。在節(jié)點(diǎn)密集部署的方案中，傳感器節(jié)點(diǎn)以瞄準(zhǔn)線的方式實(shí)現(xiàn)能量的多跳傳輸。

以上多跳能量補(bǔ)充方法都是以傳感器節(jié)點(diǎn)作為中繼器，受節(jié)點(diǎn)部署密度以及MC有效充電距離的限制，網(wǎng)絡(luò)中能夠滿足多跳能量傳輸?shù)墓?jié)點(diǎn)較為有限[11]，這在一定程度上影響了能量補(bǔ)充效率。為了改善以上問(wèn)題同時(shí)兼顧經(jīng)濟(jì)性，本文提出了如何以最少的諧振中繼器實(shí)現(xiàn)對(duì)WRSN中節(jié)點(diǎn)的完全多跳充電覆蓋這一問(wèn)題。在此基礎(chǔ)上，給出了一種包括兩個(gè)步驟的諧振中繼器位置確定策略(repeaters location determination strategy,TRLDS)。首先使用蜂窩六邊形分割網(wǎng)絡(luò)以保證網(wǎng)絡(luò)中節(jié)點(diǎn)的完全多跳充電覆蓋，其次設(shè)計(jì)了一組規(guī)則以減少中繼器數(shù)量并優(yōu)化中繼器位置，以實(shí)現(xiàn)用盡可能少的中繼器對(duì)網(wǎng)絡(luò)中所有節(jié)點(diǎn)的完全多跳充電覆蓋，進(jìn)而有效改善網(wǎng)絡(luò)能量補(bǔ)充效率這一目標(biāo)。

1 網(wǎng)絡(luò)模型與問(wèn)題定義

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

本文將傳感器節(jié)點(diǎn)(sensor node,SN)隨機(jī)分布于二維平面區(qū)域中，傳感器節(jié)點(diǎn)的數(shù)目為N，每個(gè)節(jié)點(diǎn)初始能量為Emax，能量閾值標(biāo)記為Emin。如圖1，整個(gè)網(wǎng)絡(luò)由四種類型的成員組成：諧振中繼器節(jié)點(diǎn)(repeater node,RN)，固定的基站(base station,BS)， MC，傳感器節(jié)點(diǎn)構(gòu)成。假設(shè)MC裝有大容量電池和無(wú)線能量發(fā)送裝置與接收裝置，且具有智能通信、計(jì)算和移動(dòng)的能力。MC可以在BS處通過(guò)休眠狀態(tài)補(bǔ)充自身電量。

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

1.2 充電覆蓋定義

假設(shè)1WRSN區(qū)域V=a×b，a，b為區(qū)域的邊界大??；傳感器節(jié)點(diǎn)集合定義為S={Si│0≤i

假設(shè)2所有諧振中繼器節(jié)點(diǎn)集合定義為R={Rk│0≤k

假設(shè)3Rj的充電覆蓋半徑為L(zhǎng)，傳感器節(jié)點(diǎn)Si被Sj或中繼節(jié)點(diǎn)Rk充電覆蓋的概率為

(1)

式中Si為網(wǎng)絡(luò)區(qū)域中第i個(gè)傳感器節(jié)點(diǎn)；Um=Rk∪Sj，Rk為第k個(gè)中繼器節(jié)點(diǎn)，Sj為第j個(gè)傳感器節(jié)點(diǎn)，j≠i,d(Um,Si)為Si與Rk或Sj之間的距離。

傳感器節(jié)點(diǎn)Si被多個(gè)中繼節(jié)點(diǎn)聯(lián)合覆蓋的概率為ρ(R′,Si)=1-∏(1-ρ(Rk,Si))，R′={Rn-k,Rn-k+1,…,Rn-1,Rn}，R′?R。傳感器節(jié)點(diǎn)Si被多個(gè)中繼節(jié)點(diǎn)聯(lián)合覆蓋時(shí)，Si屬于Rk的充電覆蓋下的概率為

(2)

式中mark(i)為節(jié)點(diǎn)Si被中繼節(jié)點(diǎn)Rk覆蓋的標(biāo)記。

完全多跳充電覆蓋定義在給定的WRSN中，??Si,Sj∈H，Rk,Rc∈R′，Um=Rk∪Sj。均?ρ(Um,Si)=1或ρi(R′,Si)=1,ρJt(Rk,Si)=1恒成立，則稱WRSN是完全多跳充電覆蓋網(wǎng)絡(luò)。

多跳充電覆蓋率定義在WRSN中，?H′={Si,Si+1,…,St}，H′?H。??Sj∈H且Sj?H′，Rk∈Z，其中i,j∈N，Um=Rk∪Sj,?ρ(Um,Si)=1，ρJt(Rk,Si)=1成立，則t-i+2與N的比值稱為多跳充電覆蓋率。

2 諧振中繼器位置的確定

2.1 諧振中繼器均勻部署

為了在網(wǎng)絡(luò)中均勻部署RN，需要研究網(wǎng)絡(luò)中SN之間的連通性。假設(shè)RN的最大充電半徑為R，網(wǎng)絡(luò)中無(wú)線鏈路的邊可以表示為Γ=(U,Z),U=H∪Z，Γ為傳感器網(wǎng)絡(luò)圖，U為網(wǎng)絡(luò)中節(jié)點(diǎn)的個(gè)數(shù)，H為傳感器節(jié)點(diǎn)集合，Z為中繼器節(jié)點(diǎn)集合。

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

(3)

網(wǎng)絡(luò)的連通性[12]為

(4)

基于網(wǎng)絡(luò)的連通性，利用蜂窩六邊形和兩個(gè)SN的中點(diǎn)確定方法來(lái)分割網(wǎng)絡(luò)。通過(guò)將RN均勻部署于正六邊形的中心位置上，一方面考慮部署的公平性，另一方面考慮傳感器網(wǎng)絡(luò)的完全覆蓋。

為了使RN在網(wǎng)絡(luò)中合理部署，本文給出確定RN位置的證明。在WRSN中，為了計(jì)算網(wǎng)絡(luò)中任意相鄰的正六邊形的中點(diǎn)坐標(biāo)，假設(shè)存在任意相鄰的3個(gè)正六邊形，如圖2所示，3個(gè)中點(diǎn)分別為R1=(x1,y1),R2=(x2,y2),R3=(x3,y3)。滿足R1,R2,R3∈S，已知節(jié)點(diǎn)R2=(x2,y2)，目標(biāo)是求解中繼節(jié)點(diǎn)R1,R2的坐標(biāo)。連接3個(gè)頂點(diǎn)可以得到3條邊分別為d1,d2,d3∈E，A為3個(gè)正六邊形的交點(diǎn)，過(guò)點(diǎn)R1畫邊d2的垂線交于點(diǎn)E，連接AR3。

圖2 相鄰正六邊形RN確定

(5)

通過(guò)使用相鄰蜂窩六邊形來(lái)分割網(wǎng)絡(luò)部署RN時(shí)，RN的數(shù)量較多，增加了網(wǎng)絡(luò)的物理成本。該方案中存在RN覆蓋一個(gè)或兩個(gè)SN的情況，相對(duì)RN增加了部署成本的問(wèn)題。由式(4)得，網(wǎng)絡(luò)的連通性是確定RN位置的依據(jù)，同時(shí)決定著RN充電覆蓋SN的數(shù)量。針對(duì)上述問(wèn)題，本文假設(shè)在WRSN中，存在任意兩個(gè)傳感器節(jié)點(diǎn)S1和S2，當(dāng)S1,S2之間的距離d∈[λ,2R](λ為S1,S2距離的閾值)時(shí)，由文獻(xiàn)[13]，將原先覆蓋S1,S2的RN部署在S1,S2的中間位置。該策略可以增加網(wǎng)絡(luò)的連通性，提高RN的整體充電覆蓋率，降低RN的部署成本。

2.2 諧振中繼器具體部署過(guò)程

在WRSN中，多跳充電效率隨著充電距離的增大而衰減，因此多跳充電的距離和跳數(shù)是有限的。通過(guò)部署RN可降低多跳充電的跳數(shù)，延長(zhǎng)充電距離，實(shí)現(xiàn)網(wǎng)絡(luò)的充電全覆蓋。為了詳細(xì)地闡述RN的部署過(guò)程，給出RN部署規(guī)則：

規(guī)則一根據(jù)多跳充電的有效距離，使用蜂窩單元格分割網(wǎng)絡(luò)時(shí)，將RN部署于相鄰單元格的中心位置。

規(guī)則二當(dāng)單元格中僅充電覆蓋兩個(gè)傳感器節(jié)點(diǎn)且兩節(jié)點(diǎn)之間的距離在[λ,2R]范圍內(nèi)，由文獻(xiàn)[13]，規(guī)定將RN位置調(diào)整于兩個(gè)SN的中點(diǎn)位置。

規(guī)則三當(dāng)中繼節(jié)點(diǎn)Ri僅充電覆蓋一個(gè)傳感器節(jié)點(diǎn)Si時(shí)，若Si在相鄰中繼節(jié)點(diǎn)Rk的充電覆蓋范圍則重新標(biāo)記該SN的mark值并刪除冗余中繼節(jié)點(diǎn)Ri。

規(guī)則四當(dāng)中繼節(jié)點(diǎn)Ri僅充電覆蓋一個(gè)傳感器節(jié)點(diǎn)Si時(shí)，若Si與相鄰中繼節(jié)點(diǎn)Rk覆蓋的其他傳感器節(jié)點(diǎn)之間的距離d均小于2R(R為RN的充電覆蓋半徑)，則重新部署Rk于d最大的兩個(gè)傳感器節(jié)點(diǎn)的中點(diǎn)位置并刪除冗余的中繼節(jié)點(diǎn)Ri。

規(guī)則五當(dāng)RN充電覆蓋一個(gè)SN時(shí)，任意兩個(gè)單元格中SN之間的距離小于2R，則部署其中一個(gè)RN于這兩個(gè)SN的中點(diǎn)位置并刪除另一個(gè)單元格的中繼節(jié)點(diǎn)。

規(guī)則六當(dāng)中繼節(jié)點(diǎn)Ri僅充電覆蓋一個(gè)傳感器節(jié)點(diǎn)Si時(shí)，若Si到相鄰中繼節(jié)點(diǎn)Rk覆蓋的傳感器節(jié)點(diǎn)Sj(距離Si最近)之間距離小于2R，則調(diào)整Ri的位置與Si,Sj的中點(diǎn)位置。

根據(jù)上述規(guī)則，結(jié)合圖3給出以下具體RN部署方案。

圖3 諧振中繼器位置確定

1)判斷所有tab=2的RN，根據(jù)規(guī)則二來(lái)調(diào)整RN位置。RN調(diào)整后的位置如圖中五角星點(diǎn)的位置。

2)判斷所有tab=1的RN位置，確定距離平面坐標(biāo)原點(diǎn)最近的Ri(tab=1)。根據(jù)規(guī)則三來(lái)刪除冗余的RN并將傳感器節(jié)點(diǎn)重新標(biāo)記(圖中空心點(diǎn)位置)，否則判斷是否滿足規(guī)則四的調(diào)整方案,若是,則依規(guī)則四來(lái)調(diào)整RN位置，反之,依據(jù)規(guī)則五按照?qǐng)D中所示進(jìn)行調(diào)整RN，若上述調(diào)整方案均不能解決RN覆蓋一個(gè)節(jié)點(diǎn)的問(wèn)題，則根據(jù)規(guī)則六來(lái)調(diào)整RN位置。若上述規(guī)則均不滿足,則對(duì)RN的位置不進(jìn)行任何處理。圖3(e)中的RN位置由五角星點(diǎn)和三角形點(diǎn)組成。圖3(f)中每個(gè)傳感器節(jié)點(diǎn)都被標(biāo)記過(guò)，空心圓為調(diào)整的傳感器節(jié)點(diǎn)。星點(diǎn)為RN調(diào)整之后的位置。圖中虛線為多跳充電覆蓋連接線。

3 仿真與性能評(píng)估

本文通過(guò)仿真對(duì)比TRLDS與Cellular[7]來(lái)說(shuō)明本文所提方案的有效性。本文主要工作是諧振中繼器的位置部署以及優(yōu)化工作，因此從以下指標(biāo)評(píng)估本文所提方法的有效性。默認(rèn)的仿真參數(shù)為：仿真區(qū)域?yàn)?0 m ×30 m，傳感器節(jié)點(diǎn)數(shù)量N為[25,200]，節(jié)點(diǎn)的初始能量E為10 000 units，工作狀態(tài)的能耗Ew為10 units/s，休眠狀態(tài)的能耗Es為1 unit/s，傳感器范圍為3 m，MC移動(dòng)速度為3 m/s，目標(biāo)節(jié)點(diǎn)速度1～ 5 m/s，仿真時(shí)間36 000 s，充電速率200 units/s。

3.1 多跳充電覆蓋率

根據(jù)定義可知，若ρ(Um,S)=1成立，那么RN覆蓋的節(jié)點(diǎn)數(shù)量是不同的。如圖4(a)表示RN在數(shù)量不同下的多跳充電覆蓋率的變化情況。當(dāng)RN的充電覆蓋半徑為2 m時(shí)，可以看出RN數(shù)量在0～14之間變化，多跳充電覆蓋率呈遞增趨勢(shì)。當(dāng)RN數(shù)量為11時(shí)，TRLDS的多跳充電覆蓋率達(dá)到1，而Cellular的多跳充電覆蓋率為0.62。因此，在RN數(shù)量一定條件下，TRLDS的多跳充電覆蓋率更高。如圖4(b)表示RN不同充電覆蓋范圍下的多跳充電覆蓋率的變化情況。當(dāng)RN數(shù)量為8時(shí)，可以看出隨著RN充電覆蓋范圍的變大，多跳充電覆蓋率相繼增大。在相同的條件下，可明顯看出TRLDS的多跳充電覆蓋率更高。

圖4 不同條件下多跳充電覆蓋率的性能對(duì)比

3.2 充電性能評(píng)估

在WRSN中部署RN條件下，圖5(a)中充電成本表示MC為實(shí)現(xiàn)節(jié)點(diǎn)能量補(bǔ)充的總移動(dòng)距離。從圖中看出當(dāng)節(jié)點(diǎn)數(shù)量小于125時(shí)，充電成本呈遞增趨勢(shì)，節(jié)點(diǎn)數(shù)量大于125時(shí)，充電成本呈遞減趨勢(shì)，這是因?yàn)殡S著節(jié)點(diǎn)數(shù)量的增多，節(jié)點(diǎn)死亡率變大，MC來(lái)不及給網(wǎng)絡(luò)中請(qǐng)求充電節(jié)點(diǎn)充電導(dǎo)致移動(dòng)成本降低。從圖中可以看出TRLDS的充電成本更小。圖5(b)中網(wǎng)絡(luò)生存時(shí)間表示無(wú)線可充電傳感器網(wǎng)絡(luò)從開始運(yùn)行到停止運(yùn)行的時(shí)間間隔。從圖中看出節(jié)點(diǎn)數(shù)量從25增加到200時(shí)，網(wǎng)絡(luò)的生存時(shí)間呈遞減趨勢(shì)，這是因?yàn)殡S著節(jié)點(diǎn)數(shù)量的增多，MC來(lái)不及給目標(biāo)節(jié)點(diǎn)充電而導(dǎo)致網(wǎng)絡(luò)停止。通過(guò)對(duì)比說(shuō)明，TRLDS在充電性能方面具有明顯優(yōu)勢(shì)。

圖5 布置算法在不同條件下的充電性能對(duì)比

4 結(jié) 論

本文探討了在WRSN中合理部署諧振中繼器以提高網(wǎng)絡(luò)的充電效率問(wèn)題。由于多跳無(wú)線充電效率受網(wǎng)絡(luò)中RN位置和數(shù)量的影響，本文研究了RN部署問(wèn)題，提出了一種包括兩個(gè)步驟的RN位置確定策略—TRLDS，顯著地延伸了移動(dòng)充電裝置的充電距離，從整體上提高充電效率。仿真結(jié)果表明該策略能夠以一種較低成本的方式有效解決無(wú)線傳感器網(wǎng)絡(luò)中節(jié)點(diǎn)的能量受限問(wèn)題，實(shí)現(xiàn)網(wǎng)絡(luò)的可持續(xù)性運(yùn)行。