王志方,鄭 霖,李曉記

(1.桂林電子科技大學(xué) 信息與通信學(xué)院,廣西 桂林 541004; 2.廣西信息科學(xué)實(shí)驗(yàn)中心,廣西 桂林 541004)

0 概述

無線傳感器網(wǎng)絡(luò)(Wireless Sensor Network,WSN)由部署在監(jiān)測(cè)區(qū)域內(nèi)的大量傳感器節(jié)點(diǎn)和一些匯聚節(jié)點(diǎn)組成,是通過無線通信方式形成的多跳自組織網(wǎng)絡(luò)系統(tǒng)。在WSN中,傳感器節(jié)點(diǎn)協(xié)作地感知、采集和處理網(wǎng)絡(luò)覆蓋區(qū)域中被感知對(duì)象的信息,并發(fā)送給觀察者[1-2],其中傳感器節(jié)點(diǎn)由有限的一次性電池供電且很難更換電池[3],這使得WSN的生命周期受到影響,嚴(yán)重制約其發(fā)展。文獻(xiàn)[4]在實(shí)驗(yàn)中采用磁諧振耦合的技術(shù)驗(yàn)證了無線能量傳輸?shù)目尚行?這為WSN中傳感器節(jié)點(diǎn)的能量補(bǔ)充提供了一個(gè)解決方案。

由無線充電器充電的無線傳感器網(wǎng)絡(luò)也稱為無線可充電傳感器網(wǎng)絡(luò)(Wireless Rechargeable Sensor Network,WRSN)[5-6]。WRSN中一個(gè)關(guān)鍵問題是無線充電器的部署問題。無線充電器很昂貴[7],并且它們的部署需要花費(fèi)很多的時(shí)間和成本,如何有效地部署無線充電器,使得網(wǎng)絡(luò)的充電代價(jià)最小化,是一個(gè)亟待解決的問題。

目前針對(duì)WRSN的研究多數(shù)為對(duì)移動(dòng)充電策略的研究[8-9],而對(duì)固定天線充電器部署問題的研究并不多見。文獻(xiàn)[10]研究在室內(nèi)的環(huán)境下如何部署配有定向天線的無線充電器,使得無線充電器覆蓋全部傳感器節(jié)點(diǎn),并提出了基于節(jié)點(diǎn)的貪心錐選擇算法和基于對(duì)的貪心錐選擇算法。文獻(xiàn)[11]提出一種基于自適應(yīng)對(duì)的貪心錐選擇(APB-GCS)算法,通過迭代以貪婪地選擇覆蓋大多數(shù)傳感器的充電器。文獻(xiàn)[12]中假設(shè)充電器網(wǎng)絡(luò)的布置為等邊三角形,通過研究點(diǎn)配置和路徑配置這兩種形式,使用最少數(shù)量的充電器來確保放置在網(wǎng)絡(luò)任何位置的靜止或移動(dòng)的標(biāo)簽可以獲得足夠的功率用于持續(xù)正常工作。文獻(xiàn)[13]考慮數(shù)據(jù)匯點(diǎn)對(duì)傳感器的影響,提出一種能夠減少所需定向充電器數(shù)量并仍然保持良好充電效果的功率平衡感知部署方法。

上述針對(duì)無線充電器部署的研究忽略了節(jié)點(diǎn)的位置關(guān)系和拓?fù)涮卣?傳感器節(jié)點(diǎn)隨機(jī)地分布在指定區(qū)域中,會(huì)造成傳感器節(jié)點(diǎn)的密度不均勻,使得充電器的數(shù)目增多。為此,本文定義室內(nèi)隨機(jī)非均勻環(huán)境下WSN的充電覆蓋問題,尋找最少數(shù)量的固定無線充電器,其中充電器位于網(wǎng)格頂點(diǎn)處,且充電器的覆蓋區(qū)域被假設(shè)為圓形。為部署傳感器節(jié)點(diǎn)非均勻分布下最少數(shù)目的充電器,根據(jù)文獻(xiàn)[14-15]的啟發(fā),將節(jié)點(diǎn)的位置關(guān)系和拓?fù)涮卣骺紤]到充電器的選擇中,提出利用分割技術(shù)和移位策略的近似算法,并結(jié)合最小包圍圓算法,設(shè)計(jì)基于k-中心點(diǎn)算法的聚類分區(qū)算法。

1 WSN網(wǎng)絡(luò)模型和問題

如圖1所示,給定一個(gè)無線可充電傳感器網(wǎng)絡(luò),其中傳感器節(jié)點(diǎn)隨機(jī)的部署在長(zhǎng)為L(zhǎng)、寬為W的長(zhǎng)方形區(qū)域內(nèi),負(fù)責(zé)為傳感器節(jié)點(diǎn)進(jìn)行充電的充電器位于距離長(zhǎng)方形H的高度處。如圖2所示,無線充電器配備有3D波束成形定向天線。當(dāng)傳感器節(jié)點(diǎn)位于無線充電器的充電圓錐內(nèi),即傳感器節(jié)點(diǎn)位于無線充電器的覆蓋范圍內(nèi),假定傳感器節(jié)點(diǎn)可以接收到無線充電器傳輸?shù)哪芰俊?/p>

圖1 無線可充電傳感器網(wǎng)絡(luò)示意圖

圖2 無線充電器覆蓋模型

充電范圍R是指在無線充電器的范圍內(nèi)使得在傳感器節(jié)點(diǎn)的功率接收率至少超過一個(gè)閾值δ,這里傳感器節(jié)點(diǎn)i的功率接收率用Ui表示。Ui是與距離有關(guān)的參數(shù),隨著節(jié)點(diǎn)i與無線充電器的距離增大而減小,當(dāng)傳感器節(jié)點(diǎn)i與無線充電器的距離大于r0,此處假定其功率接收率過低,使得傳感器節(jié)點(diǎn)的電池磁諧振耦合無法正常工作。rij為傳感器節(jié)點(diǎn)i到無線充電器j的距離,當(dāng)rij≤r0時(shí),節(jié)點(diǎn)i的功率接收率Ui=μ(rij)×UFull,否則Ui=0。這里UFull是無線充電汽車(Wireless Charging Vehicle,WCV)為單個(gè)傳感器節(jié)點(diǎn)滿功率輸出,μ(rij)為無線功率傳輸?shù)男?μ(rij)是關(guān)于rij的減函數(shù),且0≤μ(rij)≤1。本文旨在使用最少數(shù)量的無線充電器對(duì)平面中的所有傳感器節(jié)點(diǎn)進(jìn)行充電,該問題定義如下:

問題1給定位于歐幾里得平面U的目標(biāo)傳感器節(jié)點(diǎn),尋找到最少數(shù)目的充電器,使得充電器能覆蓋全部的傳感器節(jié)點(diǎn),并且每個(gè)傳感器節(jié)點(diǎn)至少被無線充電器覆蓋一次。

2 算法設(shè)計(jì)

圖3 無線充電器充電范圍

2.1 近似算法

假設(shè)Q是覆蓋N中所有點(diǎn)的正方形。用于問題1的分割技術(shù)的思想如下:首先將正方形Q劃分為稱為單元的正方形網(wǎng)格,每個(gè)大小為m×m,其中m為常數(shù)(見圖4);然后解決每個(gè)單元的問題1;最后將所有單元的解的聯(lián)合作為對(duì)原始輸入的解[16]。

圖4 m×m正方形網(wǎng)格

近似算法的具體步驟如下:

步驟1將平面U劃分成正方形,邊長(zhǎng)皆為m(m>2d0),集合Q=F1∪F2∪…∪Fu,其中Fi表示有節(jié)點(diǎn)存在的正方形,u為節(jié)點(diǎn)存在的正方形的數(shù)目。

步驟2對(duì)任一集合Fi,尋找單元格中最少數(shù)目的充電器Fi(c)。

步驟3輸出Q=∪Fi(c)。

因此,在所有非空單元格中,算法總時(shí)間為:

(1)

所有目標(biāo)傳感器節(jié)點(diǎn)隨機(jī)分布在平面U上。本文通過移位策略,移動(dòng)單元格以減少充電器的數(shù)目。

圖5 移位策略示意圖

下面對(duì)近似算法的近似比進(jìn)行分析。每個(gè)單元格為m×m的正方形,這里假設(shè)單元格不包括上、右側(cè)邊界。假定Di為劃分P(i,i)中所有單元格的最少數(shù)目充電器的并集。將劃分P(i,i)中位于水平或垂直格線的所有單元格的集合成為P(i,i)的一個(gè)條塊。用Hi和Vi分別表示D*中與P(i,i)的水平和垂直條塊相交的所有單元格的集合。如果充電器與多個(gè)單元格相交,則它必須屬于Hi或者Vi,且每個(gè)充電器最多與4個(gè)單元格相交,因此,有:

|Di|≤|D*|+|Hi|+2|Vi|

(2)

當(dāng)a≠b時(shí),一個(gè)充電器不可能既屬于Va又屬于Vb,即所有的集合Va,a=0,1,…,m-1都是兩兩不相交的。因此,有:

(3)

同理可得:

(4)

2.2 聚類分區(qū)算法

初始化移動(dòng)位置集合M=?,聚類分區(qū)算法的具體步驟如下:

步驟1令k=1,S=?。

步驟2使用k-中心點(diǎn)算法進(jìn)行分類并計(jì)算出每一類中點(diǎn)的最小包圍圓[17]。

步驟3判斷是否存在半徑ri≤d0,i∈{1,2,…,k}的最小包圍圓。若存在,則將這些聚類儲(chǔ)存到集合S中,并且M=M∪S,然后從節(jié)點(diǎn)集N中去除類中的點(diǎn),即N=N-S,判斷集合S是否為空集,不滿足轉(zhuǎn)到步驟1,滿足轉(zhuǎn)到步驟4;若不存在,k=k+1,轉(zhuǎn)到步驟3。

步驟4輸出集合M。

已知k-中心點(diǎn)算法時(shí)間復(fù)雜度為O(k(n-k)2),而最小包圍圓算法時(shí)間復(fù)雜度是線性的。假設(shè)第1次出現(xiàn)半徑ri≤d0,i∈{1,2,…,k}的最小包圍圓時(shí)k-中心點(diǎn)算法運(yùn)行了k1次,此時(shí)最小包圍圓內(nèi)的節(jié)點(diǎn)數(shù)為n1,則運(yùn)行總時(shí)間為:

O((n- 1)2+2·(n-2)2+…+k1·(n-k1)2)=

(5)

假設(shè)第2次出現(xiàn)半徑ri≤d0,i∈{1,2,…,k}的最小包圍圓時(shí)k-中心點(diǎn)算法運(yùn)行了k2次,此時(shí)最小包圍圓內(nèi)的節(jié)點(diǎn)數(shù)為n2,則運(yùn)行總時(shí)間為:

O((n-n1-1)2+2·(n-n1-2)2+…+

(6)

3 仿真與分析

本節(jié)展示了2種算法的仿真結(jié)果。仿真器以MATLAB和LINGO實(shí)現(xiàn),仿真設(shè)置如表1所示。假設(shè)傳感器節(jié)點(diǎn)隨機(jī)部署在20 m×20 m平面中,其中距離平面2.82 m處的一組網(wǎng)格點(diǎn)間隔為1.414 m,以部署無線充電器。無線充電器的有效充電距離為3 m,即傳感器節(jié)點(diǎn)與充電器的距離在這個(gè)范圍內(nèi)可以有效地補(bǔ)充電量,否則傳感器節(jié)點(diǎn)的充電效率為0。

表1 仿真設(shè)置

圖6和圖7分別展示了當(dāng)平面上隨機(jī)部署傳感器節(jié)點(diǎn)的數(shù)量為100時(shí),2種算法得到的無線充電器的數(shù)量。其中,通過近似算法計(jì)算得到的充電器的數(shù)目為36個(gè),而通過聚類分區(qū)算法計(jì)算得到的充電器的數(shù)目為35個(gè)。由于近似算法在移位策略中,處于左邊界和上邊界的點(diǎn)在移位之后將不再參與分區(qū),因此會(huì)使計(jì)算出的充電器的數(shù)目上有一定的偏差。

圖6 近似算法仿真結(jié)果

圖7 聚類分區(qū)算法仿真結(jié)果

圖8給出了近似算法、聚類分區(qū)算法和APB-GCS算法在選擇充電器數(shù)量方面的比較結(jié)果?？梢钥闯?由近似算法和聚類分區(qū)算法求得的充電器的數(shù)目比APB-GCS算法少得多,而近似算法與聚類分區(qū)算法相差不大。

圖8 本文算法與APB-GCS算法的充電器數(shù)目比較

4 結(jié)束語

本文定義無線可充電傳感器網(wǎng)絡(luò)中的充電覆蓋問題,同時(shí)考慮傳感器節(jié)點(diǎn)隨機(jī)非均勻分布的特點(diǎn),提出2種算法:將網(wǎng)絡(luò)劃分成網(wǎng)格的形式進(jìn)行求解并利用移位策略減少充電器數(shù)目的近似算法,以及基于貪心算法思想的聚類分區(qū)算法。時(shí)間復(fù)雜度分析及仿真結(jié)果表明,聚類分區(qū)算法在減少充電器的數(shù)量方面性能更好,而且具有較低的時(shí)間復(fù)雜度。下一步將對(duì)充電器為傳感器節(jié)點(diǎn)充電的時(shí)間以及WRSN中拓?fù)渎酚蓪?duì)充電的影響等問題進(jìn)行研究。

[1] AKYILDIZ I F,SU W,SANKARASUBRAMANIAM Y,et al.Wireless sensor networks:a survey[J].Computer Networks,2002,38(4):393-422.

[2] RAULT T,BOUABDALLAH A,CHALLAL Y.Energy efficiency in wireless sensor networks:a top-down survey[J].Computer Networks,2014,67(8):104-122.

[3] RAJBA S,RAIF P,RAJBA T,et al.Wireless sensor networks in application to patients health monitoring[C]//Proceedings of IEEE Symposium on Computational Intelligence in Healthcare and E-health.Washington D.C.,USA:IEEE Computer Society,2013:94-98.

[4] KURS A,KARALIS A,MOFFATT R,et al.Wireless power transfer via strongly coupled magnetic resonances[J].Science,2007,317(5834):83-86.

[5] DAI H P,WU X B,XU L J,et al.Practical scheduling for stochastic event capture in wireless rechargeable sensor networks[C]//Proceedings of WCNC’13.Washington D.C.,USA:IEEE Computer Society,2013:986-991.

[6] DAI H P,XU L J,WU X B,et al.Impact of mobility on energy provisioning in wireless rechargeable sensor networks[C]//Proceedings of WCNC’13.Washington D.C.,USA:IEEE Computer Society,2013:962-967.

[7] 戴海鵬,陳貴海,徐力杰,等.一種高效有向無線充電器的布置算法[J].軟件學(xué)報(bào),2015,26(7):1711-1729.

[8] 胡 誠(chéng),汪 蕓,王 輝.無線可充電傳感器網(wǎng)絡(luò)中充電規(guī)劃研究進(jìn)展[J].軟件學(xué)報(bào),2016,27(1):72-95.

[9] 劉 創(chuàng),王 珺,吳 涵.無線可充電傳感器網(wǎng)絡(luò)的移動(dòng)充電問題研究[J].計(jì)算機(jī)技術(shù)與發(fā)展,2016,26(3):162-167.

[10] LIAO J H,JIANG J R.Wireless charger deployment optimization for wireless rechargeable sensor networks[C]//Proceedings of International Conference on Ubi-Media Computing and Workshops.Washington D.C.,USA:IEEE Press,2014:160-164.

[11] LIAO J H,HONG C M,JIANG J R.An adaptive algorithm for charger deployment optimization in wireless rechargeable sensor networks[J].Frontiers in Artificial Intelligence and Applications,2015,274:2080-2089.

[12] HE S B,CHEN J M,JIANG F C,et al.Energy provisioning in wireless rechargeable sensor networks[C]//Proceedings of INFOCOM’11.Washington D.C.,USA:IEEE Computer Society,2011:2006-2014.

[13] LIN T L,LI S L,CHANG H Y.A power balance aware wireless charger deployment method for complete coverage in wireless rechargeable sensor networks[J].Energies,2016,9(9):695-708.

[14] PANG Y,LU Z,PAN M,et al.Charging coverage for energy replenishment in wireless sensor networks[J].IEEE International Conference on Networking,2014,43(3):251-254.

[15] 王繼強(qiáng).集合覆蓋問題的模型與算法[J].計(jì)算機(jī)工程與應(yīng)用,2013,49(17):15-17.

[16] DU D Z,KO K I,HU X.Design and analysis of approximation algorithms[M].Berlin,Germany:Springer,2011:123-136.

[17] WELZL E.Smallest enclosing disks(balls and ellipsoids)[M]//MAURER H.New Results and New Trends in Computer Science.Berlin,Germany:Springer,1991:359-370.