冗余無線傳感網(wǎng)絡(luò)的最小成本部署問題

史文武，王 然

（杭州電子科技大學(xué)，浙江 杭州 310018）

0 引言

無線傳感器網(wǎng)絡(luò)（Wireless Sensor Networks，WSN）被廣泛用于對(duì)自然環(huán)境[1]和基礎(chǔ)設(shè)施[2]的長期監(jiān)視，因此，WSN的存活時(shí)間是一項(xiàng)重要指標(biāo)。降低WSN的能量消耗速率或?yàn)閃SN提供額外的能量，都能提高WSN的存活壽命，然而通過控制數(shù)據(jù)路由和加入睡眠/喚醒機(jī)制降低WSN的能量消耗速率的方式，只能有限延長WSN的壽命。為了讓W(xué)SN永久運(yùn)行，現(xiàn)有文獻(xiàn)主要從兩種途徑來實(shí)現(xiàn)：

（1）通過收集不穩(wěn)定的自然環(huán)境中的能量，如太陽能、風(fēng)能等[3-5]；

（2）通過穩(wěn)定的無線能量傳輸（Wireless Energy Transfer，WET）[6,7]。

然而，由于來自環(huán)境的能量通常很難預(yù)測(cè)[6]，這會(huì)使WSN的監(jiān)視性能隨時(shí)間的推移而不穩(wěn)定。

WET使用專用的能量基站（energy Base Stations，eBS）為無線設(shè)備遠(yuǎn)程充電[8]，由eBS供電的WSN稱為無線供電的傳感器網(wǎng)絡(luò)（Wirelessly Powered Sensor Networks，WPSN）。通過穩(wěn)定的無線能量傳輸，能更好地控制WPSN中的傳感器節(jié)點(diǎn)的能量獲取[9]。通過載有無線充電源的可移動(dòng)載具，按照規(guī)劃的路徑給傳感器節(jié)點(diǎn)充電是一種常用方法[10-12]，但某些野外場(chǎng)景（如森林、山坡）并不適合載具的移動(dòng)。Du等人[13]通過在網(wǎng)絡(luò)中部署冗余節(jié)點(diǎn)，利用能量波束成形技術(shù)[14]，位置固定的eBS同時(shí)向同一區(qū)域內(nèi)彼此靠近的節(jié)點(diǎn)充電，使該區(qū)域單位時(shí)間內(nèi)獲取更多的能量，同時(shí)每個(gè)節(jié)點(diǎn)可以通過休眠/喚醒機(jī)制消耗更少的能量來滿足監(jiān)視需求。這些節(jié)點(diǎn)可以通過輪流工作來節(jié)省能源，這解決了單eBS情況下聯(lián)合節(jié)點(diǎn)部署和無線能量傳輸調(diào)度問題。

現(xiàn)實(shí)情況下，單eBS覆蓋范圍有限，如何在給定待監(jiān)測(cè)的感興趣區(qū)域的條件下聯(lián)合確定基站位置和傳感器數(shù)量，使WPSN在成本最低的情況下保持持續(xù)不斷地監(jiān)測(cè)是一個(gè)重要問題?？紤]如圖1所示的WPSN，有多個(gè)感興趣的區(qū)域要用傳感器節(jié)點(diǎn)進(jìn)行監(jiān)視。eBS將能量傳輸?shù)絺鞲衅鞴?jié)點(diǎn)以監(jiān)測(cè)環(huán)境并上傳測(cè)量結(jié)果。當(dāng)eBS向某一區(qū)域傳輸能量時(shí)，該區(qū)域中部署的多個(gè)傳感器節(jié)點(diǎn)可以同時(shí)收集能量，并且輪流工作以減少能耗。因此，自然會(huì)產(chǎn)生以下問題：

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

（1）傳感器節(jié)點(diǎn)的部署數(shù)量；

（2）基站的部署數(shù)量和位置；

（3）WET調(diào)度，即每個(gè)eBS某時(shí)刻應(yīng)向哪個(gè)區(qū)域傳輸能量。

該問題把傳感器數(shù)量選擇和基站的數(shù)量、位置部署以及WET調(diào)度結(jié)合在一起，在保證網(wǎng)絡(luò)持久運(yùn)行的前提下，最小化傳感器和基站的聯(lián)合成本。

為解決此問題，本文在該問題上添加約束，令待監(jiān)測(cè)區(qū)域僅被固定的某一基站充電，以簡(jiǎn)化充電問題，并設(shè)計(jì)基站最佳覆蓋范圍搜索算法解耦了傳感器部署和基站部署問題，最后用迭代算法求解基站的部署位置，得到簡(jiǎn)化問題的解，并將其作為原問題的近似解決方案。

1 問題定義

在本節(jié)中，首先介紹所采用的網(wǎng)絡(luò)模型和無線充電模型，其次正式給出優(yōu)化問題的形式定義及相關(guān)的約束條件。

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

如圖1中所示的WPSN模型，二維平面內(nèi)有N個(gè)待監(jiān)測(cè)的感興趣區(qū)域，區(qū)域間有一定的距離，單個(gè)區(qū)域中的節(jié)點(diǎn)彼此靠近。eBS通過無線方式為傳感器節(jié)點(diǎn)提供能量，并從節(jié)點(diǎn)收集數(shù)據(jù)。由于能量是由RF承載的，因此會(huì)遭受較高的路徑損耗。從而，eBS使用能量波束成形將能量集中到目標(biāo)[15]。每個(gè)傳感器節(jié)點(diǎn)都使用整流天線從eBS收集RF能量，并將能量存儲(chǔ)到其可充電電池中。

本文使用{li}，i=1,2,…,N表示N個(gè)待監(jiān)視區(qū)域。在每個(gè)區(qū)域li中，部署了xi個(gè)傳感器節(jié)點(diǎn)，x=[x1,x2,…,xN]T表示每個(gè)區(qū)域的傳感器節(jié)點(diǎn)數(shù)量。{bm}，m=1,2,…,M用來表示M個(gè)eBS，W=((u1,v1),(u2,v2),…,(uM,vM))T表示每個(gè)eBS的坐標(biāo)。本文希望找到W和x的最佳值，在確保WPSN監(jiān)視性能的同時(shí)最小化部署網(wǎng)絡(luò)所需成本。部署節(jié)點(diǎn)后，WPSN開始進(jìn)行監(jiān)測(cè)。把時(shí)間劃分為多個(gè)時(shí)隙，每個(gè)時(shí)隙包含能量傳輸和數(shù)據(jù)傳輸兩個(gè)階段。

1.2 能量傳輸階段

在能量傳輸階段，eBS會(huì)形成尖銳的能量束，以對(duì)某個(gè)區(qū)域中的節(jié)點(diǎn)充電。令0-1變量ym(t)=(ym1(t),ym2(t),…,ymn(t))T表示在時(shí)隙t時(shí)，基站bm的充電調(diào)度方案，如果基站bm將能量傳輸?shù)絽^(qū)域li，則ymi(t)=1，否則ymi(t)=0。令P表示eBS的發(fā)射功率。在允許在同一區(qū)域中部署多個(gè)節(jié)點(diǎn)的情況下，該區(qū)域中的所有傳感器節(jié)點(diǎn)都可以同時(shí)收集RF能量，且接收功率相同。而其他區(qū)域中的節(jié)點(diǎn)則無法收集。當(dāng)基站bm向區(qū)域li傳輸能量時(shí)，可以用項(xiàng)αmi來表示充電功率：

除αmi以外，區(qū)域li處的節(jié)點(diǎn)的接收功率還取決于li處的傳感器節(jié)點(diǎn)數(shù)，一個(gè)原因是，在li節(jié)點(diǎn)較少的情況下，eBS可以使用更集中的波束來覆蓋li的所有節(jié)點(diǎn)；另一個(gè)原因是，當(dāng)部署更多節(jié)點(diǎn)時(shí)，節(jié)點(diǎn)間更有可能存在能量束的遮蔽效應(yīng)。因此，本文使用節(jié)點(diǎn)數(shù)g(xi)的函數(shù)來表示由于節(jié)點(diǎn)部署而造成的這種損失[13]。那么，區(qū)域li中的節(jié)點(diǎn)單位時(shí)間所收集的總能量為αmig(xi)ymi(t)。本文假設(shè)這些節(jié)點(diǎn)平均共享總能量，即節(jié)點(diǎn)平均收獲功率為αmig(xi)ymi(t)/xi。g(xi)具有以下特性：g(1)=1且0≤g′(xi)<1，對(duì)于所有大于或等于1的xi，g′(xi)≤0，g(1)=1為基準(zhǔn)。第二個(gè)假設(shè)0≤g′(xi)≤1，g′(xi)≤0是因?yàn)檎诒涡?yīng)，隨著節(jié)點(diǎn)的增加，總收獲的能量在增加，但收益是遞減的。區(qū)域中的節(jié)點(diǎn)收集的總能量不能大于傳輸?shù)哪芰?，即g(xi)應(yīng)該是有界的?；谏鲜黾僭O(shè)，g(xi)/xi是相對(duì)于xi單調(diào)遞減的。這意味著，隨著在同一區(qū)域中部署更多的節(jié)點(diǎn)，每個(gè)傳感器節(jié)點(diǎn)收集到的能量都將減少。函數(shù)g(x)的性質(zhì)如圖2所示。

圖2 函數(shù)g(x)的性質(zhì)

1.3 數(shù)據(jù)傳輸階段

在數(shù)據(jù)傳輸階段，同一區(qū)域的傳感器節(jié)點(diǎn)應(yīng)用休眠/喚醒機(jī)制節(jié)省能量。更具體地，在時(shí)隙t中，每個(gè)區(qū)域有且僅有一個(gè)節(jié)點(diǎn)被喚醒，監(jiān)測(cè)環(huán)境并發(fā)送數(shù)據(jù)，而其他節(jié)點(diǎn)處于休眠狀態(tài)。vij表示區(qū)域li中的第j個(gè)節(jié)點(diǎn)。zi(t)=(zi1(t),zi2(t),…,zixi(t))T表示在時(shí)隙t中區(qū)域li內(nèi)的節(jié)點(diǎn)的激活調(diào)度，其中0-1變量zij(t)是vij在時(shí)隙t的狀態(tài)。假設(shè)監(jiān)視應(yīng)用程序要求區(qū)域li的采樣率為λi，則li中節(jié)點(diǎn)的能量消耗為cizij(t)+c，其中ci為傳輸λi數(shù)據(jù)量所花費(fèi)的能量，c為傳感器的靜態(tài)能耗。設(shè)Eij(t)為節(jié)點(diǎn)vij的剩余能量，所有節(jié)點(diǎn)的電池大小為B，時(shí)隙長度為D，則傳感器節(jié)點(diǎn)的動(dòng)態(tài)能量方程為：

本文假設(shè)電池容量很大，即B>>ci，這意味著傳感器節(jié)點(diǎn)在幾個(gè)時(shí)隙中都不會(huì)很快耗盡能量?？偠灾?，可以將WPSN建模為元組(L,c,A,W,x,Y,Z,E,B,D,g)，其中L=[li]=[(ui,vi)]，c=[c,c1,c2,…,cN]，A=[αmi]，W=[(u′m,v′m)]，x=[xi]，Y=[ymi(t)]，Z=[zij(t)]，E=[Eij(t)]。

1.4 形式化定義

對(duì)于給定的無線充電傳感網(wǎng)絡(luò)WPSN(L,c,A,W,x,Y,Z,E,B,D,g)，在任意時(shí)刻，需要所有區(qū)域的采樣速率滿足給定要求，否則認(rèn)為傳感網(wǎng)失效，由此可以給出網(wǎng)絡(luò)壽命及優(yōu)化問題的定義。

（1）定義1：無線充電傳感網(wǎng)絡(luò)的壽命。無線充電傳感網(wǎng)絡(luò)WPSN(L,c,A,W,x,Y,Z,E,B,D,g)是可永久運(yùn)行的，當(dāng)且僅當(dāng)在任何時(shí)隙t和任何區(qū)域li中的任意傳感器節(jié)點(diǎn)的剩余能量都是非負(fù)的，即Eij(t)≥0。相應(yīng)地，WPSN(L,c,A,W,x,Y,Z,E,B,D,g)的壽命被定義為首次存在一個(gè)傳感器節(jié)點(diǎn)，其Eij(t+1)

（2）定義2：基于冗余傳感器節(jié)點(diǎn)的最小成本部署問題。聯(lián)合傳感器部署、節(jié)點(diǎn)部署和WET調(diào)度問題是找到W,x,Y,Z，使服從WPSN可永久運(yùn)行的約束下，最小化總部署成本。令ps，pB分別表示單個(gè)傳感器節(jié)點(diǎn)和eBS的部署成本，根據(jù)前文定義，可將問題1表述如下：

其中，式（3）意味著最大限度地降低基站和節(jié)點(diǎn)的總成本；約束（4）表示所有節(jié)點(diǎn)都不應(yīng)耗盡能量；約束（7）表示每個(gè)eBS在每個(gè)時(shí)隙中能且只能為一個(gè)區(qū)域的傳感器節(jié)點(diǎn)充電；約束（8）表示對(duì)于每個(gè)時(shí)隙中，每個(gè)區(qū)域有且只有一個(gè)節(jié)點(diǎn)工作。

2 問題求解

解決問題1的困難，不僅在于整數(shù)和0-1約束決策變量，還在于基站部署、傳感器節(jié)點(diǎn)部署以及WET調(diào)度三者之間存在耦合性。為了解決問題1，本文提出了一個(gè)約束條件，得以解耦WET調(diào)度，得到簡(jiǎn)化的問題，使本文可以更多地關(guān)注基站和傳感器節(jié)點(diǎn)的部署。

2.1 添加約束

如圖3所示，本文讓每個(gè)待監(jiān)測(cè)區(qū)域能且只能被某一固定的基站充電。

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

令s=(s1,s2,…,sN)T，其中si=1,2,…,M，si=m表示區(qū)域li歸屬于基站bm。則問題1可改寫為問題2：

其中，約束（16）中的I(si=m)為指示函數(shù)，si=m時(shí)結(jié)果為1，否則為0。

定理1：區(qū)域li應(yīng)歸屬于距離其最近的基站，即：

證明：如圖3所示，為滿足問題2約束的按距離劃分歸屬的一種解決方案，同一填充樣式的區(qū)域?qū)儆谙嗤幕?。不失一般性地，設(shè)某一區(qū)域l1屬于基站b1，則每個(gè)時(shí)隙D內(nèi)，區(qū)域l1接收到的總能量為α11g(x1)D，若保持其他條件（傳感器節(jié)點(diǎn)部署數(shù)量）不變，改變區(qū)域l1的歸屬，使其歸屬于b2，則時(shí)隙D內(nèi)區(qū)域l1的總接收能量為α21g(x1)D。由d11α21，則相同時(shí)間內(nèi)，區(qū)域l1接收到的能量變少，相同的部署情況下，區(qū)域?qū)儆谧罱幕緯r(shí)充電功率最大。

2.2 基站的最佳覆蓋范圍

基站的最佳覆蓋范圍如圖4所示。對(duì)于給定的單個(gè)基站的位置和其要覆蓋的區(qū)域l1,l2,…,lC，可以計(jì)算c和α，并根據(jù)基于貪婪的部署（Greedy Based Deployment，GBD）算法[13]計(jì)算x=(x1,x2,…,xN)T，使∑x最小。對(duì)于同一位置的基站，當(dāng)覆蓋不同數(shù)量的區(qū)域時(shí)，隨著覆蓋區(qū)域數(shù)量的增加，更多的區(qū)域平攤基站成本，因此每個(gè)區(qū)域的充電時(shí)間占比將會(huì)減少。為滿足電量消耗需求，需要在每個(gè)區(qū)域部署更多的傳感器，這會(huì)增加傳感器部署的成本。如圖4，若如最小的圓所示，僅覆蓋3個(gè)區(qū)域，則可能有x=(1,1,1)T；若如中等大小的圓所示，覆蓋7個(gè)區(qū)域，則可能有x=(1,2,3,2,3,3,4)T；若如最大的圓所示，基站覆蓋13個(gè)區(qū)域，則可能有x=(3,4,4,4,5,4,6,5,7,7,8,9,9)T。若傳感器成本與基站成本為1∶15，則3種情況下的每個(gè)區(qū)域平均成本分別為6，33/7和75/13，則在這3種情況下，覆蓋中等大小的圓時(shí)，每個(gè)區(qū)域的平均成本最小。

圖4 基站的最佳覆蓋范圍

那么，當(dāng)給定待監(jiān)測(cè)區(qū)域坐標(biāo)L=[l1,l2,…,lN]=[(u1,v1),(u2,v2),…,(uN,vN)]和基站的坐標(biāo)w=(u,v)時(shí)，如何求解基站覆蓋范圍，能使每個(gè)區(qū)域的平均成本最低？對(duì)于此問題，本文設(shè)計(jì)了基站最佳覆蓋范圍搜索算法，得出最優(yōu)覆蓋范圍C。

2.3 基站的部署

本節(jié)的目標(biāo)是基于定理1和基站最佳覆蓋范圍搜索算法，提出一種迭代式算法，得到問題2的近似解。

圖5展示了迭代過程中可能出現(xiàn)的基站部署位置不合理的典型情況。如圖5所示，對(duì)于3個(gè)基站的當(dāng)前位置，虛線圈為各基站的最佳覆蓋范圍。顯然，左邊的基站與中間的基站有覆蓋范圍的重合。根據(jù)定理1，每個(gè)區(qū)域僅歸屬于距離其最近的基站，被重復(fù)覆蓋的網(wǎng)格填充區(qū)域?qū)嶋H屬于左邊的基站，則中間的基站實(shí)際上僅為其余3個(gè)區(qū)域充電，基站的覆蓋能力未充分利用，徒增了成本。中間基站與右邊基站中間的點(diǎn)狀填充區(qū)域未被任何一個(gè)基站覆蓋，根據(jù)定理1，該區(qū)域?qū)嶋H需要被右側(cè)的基站覆蓋。這超出了右側(cè)基站的最佳覆蓋能力，需要為其覆蓋的所有區(qū)域部署更多的傳感器，以使基站對(duì)各區(qū)域的充電效能更高。圖6列出了迭代過程中可能出現(xiàn)的情況。

圖5 迭代過程局部

圖6 區(qū)域視角的迭代情況

如圖6（a）所示，某一區(qū)域li在多個(gè)基站（n個(gè)基站的最佳覆蓋范圍內(nèi)，則除距離該區(qū)域最近的基站外，其余基站應(yīng)遠(yuǎn)離該區(qū)域，表達(dá)式為：

式中：(ui,vi)為區(qū)域li的坐標(biāo)；lr為步長；I為指示函數(shù)，即當(dāng)i≠j時(shí)I為1，否則I為0。

對(duì)于情況6（b），某一區(qū)域li不在任何基站的最佳覆蓋范圍內(nèi)，則該區(qū)域最鄰近的η（η為可調(diào)參數(shù)）個(gè)基站應(yīng)該靠近該區(qū)域，表達(dá)式為：

圖7所示的整體情況中，如圖7（a），顯然所有基站的最佳覆蓋范圍內(nèi)區(qū)域的總和遠(yuǎn)小于待監(jiān)測(cè)區(qū)域總數(shù)。此時(shí)，若按就近原則分配區(qū)域，會(huì)導(dǎo)致部分基站被分配過多的區(qū)域，使部署傳感器節(jié)點(diǎn)的成本增加，甚至永遠(yuǎn)無法滿足充電需求，對(duì)于這種情況，需要增添新的基站。如圖7（b）所示，所有基站的最佳覆蓋范圍內(nèi)區(qū)域的總和大于待監(jiān)測(cè)區(qū)域總數(shù)。此時(shí)，每個(gè)基站分配到的區(qū)域數(shù)小于最佳覆蓋范圍，導(dǎo)致基站成本未被充分均攤。對(duì)于這種情況，需要?jiǎng)h除多余的基站?？傮w而言，迭代過程中，要保持所有基站的最佳覆蓋范圍內(nèi)區(qū)域的總和與待監(jiān)測(cè)區(qū)域總數(shù)大致相等。

圖7 總體視角的迭代情況

根據(jù)上述區(qū)域視角和總體視角中提出的4種情況，迭代算法的具體步驟由算法2給出。

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

在這一節(jié)中將進(jìn)行大量的仿真實(shí)驗(yàn)，首先針對(duì)提出的算法從動(dòng)態(tài)最小剩余電量、基站和傳感器成本比、采樣率、待監(jiān)測(cè)區(qū)域數(shù)等方面進(jìn)行評(píng)估；其次與貪心策略進(jìn)行對(duì)比。實(shí)驗(yàn)結(jié)果證實(shí)了本文算法的優(yōu)越性。

3.1 參數(shù)設(shè)置

WPSN由N個(gè)部署傳感器的待監(jiān)測(cè)區(qū)域和M個(gè)未知位置的待部署基站組成。默認(rèn)情況下的網(wǎng)絡(luò)參數(shù)設(shè)置：250個(gè)待監(jiān)測(cè)區(qū)域隨機(jī)位于長、寬均為300 m的方形范圍內(nèi)。部署好的基站可向外發(fā)射RF能量，并帶有915 MHz的能量載波。每個(gè)區(qū)域li的采樣率λi服從[25,30]bits/s的均勻分布。單位比特的傳輸能耗為10-6J/bit，則有ci=10-6λi。傳感器節(jié)點(diǎn)的靜態(tài)功耗為c=10-6J/s。函數(shù)g(x)設(shè)置為g(x)=(1-qx)/(1-q)，其中q=0.9?；竞蛡鞲衅鞯牟渴鸪杀颈萺為25。

3.2 不同參數(shù)對(duì)本文算法的影響

3.2.1 模擬充放電過程

首先，對(duì)于算法給出的WPSN部署，模擬傳感器耗電感知環(huán)境和基站充電過程，并基于等式（1）更新傳感器節(jié)點(diǎn)的剩余能量。在每個(gè)時(shí)隙，記錄下所有傳感器的最小剩余能量百分比。圖8為最小剩余能量百分比的動(dòng)態(tài)?？梢钥吹?，在6 000個(gè)時(shí)隙內(nèi)，沒有任何一個(gè)傳感器節(jié)點(diǎn)耗盡其電池能量，并且剩余能量的最小百分比保持在80%以上。通過此算法進(jìn)行基站和傳感器節(jié)點(diǎn)部署，可使WPSN保持持續(xù)不斷地監(jiān)測(cè)。

圖8 所有節(jié)點(diǎn)的最小剩余電量動(dòng)態(tài)

為檢查算法給出的解決方案相對(duì)于節(jié)點(diǎn)的消耗功率和采集功率的變化是否具有魯棒性，在節(jié)點(diǎn)的消耗功率和采集功率上添加噪聲。噪聲遵循零均值高斯分布，其標(biāo)準(zhǔn)偏差分別設(shè)置為0，0.2和0.4。結(jié)果如圖9所示，是某一傳感器節(jié)點(diǎn)的剩余能量百分比動(dòng)態(tài)圖。黑色曲線、深灰色曲線和淺灰色曲線分別對(duì)應(yīng)于σ=0，σ=0.2和σ=0.4的情況?？梢杂^察到，標(biāo)準(zhǔn)差較大的情況下，剩余電量的動(dòng)態(tài)波動(dòng)也較大，但在所有情況下，該傳感器都不會(huì)耗盡能量。這是因?yàn)榛静⒎枪ぷ髟跇O限負(fù)載情況下，而是工作在最佳成本負(fù)載情況下。因此，根據(jù)本文算法的部署方案可抵抗網(wǎng)絡(luò)的外部變化，有很強(qiáng)的健壯性。

3.2.2 基站傳感器成本比

圖10展示了基站/傳感器成本比對(duì)算法給出部署結(jié)果的影響。如圖10（a）所示，隨著基站相對(duì)成本的上升，基站部署數(shù)量先逐漸下降，但當(dāng)成本進(jìn)一步上升后，基站部署數(shù)量的下降速度放緩。經(jīng)分析可知，先逐漸下降是因?yàn)殡S成本的上升，需要更多的待監(jiān)測(cè)區(qū)域均攤基站成本，即單個(gè)基站的最佳負(fù)載在穩(wěn)步上升；之后基站部署數(shù)量持穩(wěn)，是因?yàn)榛矩?fù)載能力存在上限，無法繼續(xù)通過拓展覆蓋領(lǐng)域的方式均攤成本。圖10（b）給出隨基站相對(duì)成本的上升，區(qū)域內(nèi)傳感器數(shù)量的變化情況?？梢钥闯觯S基站負(fù)載范圍的變大，每個(gè)待監(jiān)測(cè)區(qū)域所分到時(shí)間片減少導(dǎo)致其充電效率降低。為應(yīng)對(duì)此情況，增加了區(qū)域內(nèi)傳感器節(jié)點(diǎn)的數(shù)量，使充電效率增加。圖10的變化趨勢(shì)證明了算法1基站最佳覆蓋范圍選擇的有效性。

3.3 算法性能對(duì)比

本文將所提算法的性能與雙圓貪心[16]（Double-Circle Greedy，DCG）算法和基于最大密度優(yōu)先（Maximum Density Priority，MDP）的貪心算法進(jìn)行了比較，分析不同部署策略的差異。DCG算法是一種不受現(xiàn)有算法限制（如需要將基站固定在一些網(wǎng)格點(diǎn)上或其他待選位置上）的基站部署算法。對(duì)于MDP算法，僅考慮將給定的待監(jiān)測(cè)區(qū)域作為基站部署的待選位置，首先根據(jù)算法1計(jì)算所有待選位置的最佳覆蓋范圍；其次依據(jù)貪心思想，每輪在剩下的待選位置中挑選出可覆蓋最多待監(jiān)測(cè)區(qū)域的位置，作為該輪次基站部署的位置。

3.3.1 不同參數(shù)下算法的比較

圖11展示了不同參數(shù)對(duì)各算法部署成本的影響以及不同參數(shù)下各算法的性能比較。

如圖11（a）所示，待監(jiān)測(cè)數(shù)量從150增加到300，兩個(gè)算法的部署成本均逐漸變大；但本文算法中采用了均衡基站覆蓋范圍策略來平衡每個(gè)基站的工作負(fù)載，所以總部署成本優(yōu)于MDP算法10%左右。對(duì)于DCG算法，由于其總是用相同大小的圓來覆蓋目標(biāo)，未考慮不同的位置處，待監(jiān)測(cè)區(qū)域密度也不同，表現(xiàn)較差。同樣地，在圖11（b）中，采樣率的增加使每個(gè)激活的傳感器節(jié)點(diǎn)的能耗都增加了，也需要部署更多的基站和傳感器節(jié)點(diǎn)，但本文算法始終優(yōu)于MDP算法。而DCG算法只考慮待監(jiān)測(cè)區(qū)域的位置關(guān)系，采樣率對(duì)其基站部署沒有影響，且DCG算法中基站負(fù)載能力遠(yuǎn)未得到充分利用，采樣率的增加對(duì)其傳感器部署的影響也較小。圖11（c）中考慮了不同成本比下各算法的總成本，由于DCG算法無法根據(jù)成本比動(dòng)態(tài)地調(diào)整部署策略，其部署總成本隨成本比線性增大。所提迭代算法和MDP算法都利用了基站最佳覆蓋范圍搜索算法，所以成本均小于DCG算法，其中本文所提迭代算法也總優(yōu)于基于貪心的MDP算法。

3.3.2 不同算法的基站/傳感器部署成本組成情況

在其他條件相同的情況下，圖12給出了3種算法成本組成的區(qū)別。如圖12所示，本文算法中傳感器節(jié)點(diǎn)的數(shù)量多于貪心算法，但在基站數(shù)量上比貪心算法有優(yōu)勢(shì)。這是因?yàn)樨澬乃惴枯喆慰偸沁x擇能覆蓋最多待監(jiān)測(cè)區(qū)域的位置，而忽略了基站的相對(duì)位置關(guān)系，使得最后剩余的待監(jiān)測(cè)區(qū)域總是較為分散的，需要更多的基站才能覆蓋。算法2均衡了所有基站的負(fù)載，使基站負(fù)載能力得到充分利用。DCG算法未能動(dòng)態(tài)地考慮不同位置上基站的負(fù)載范圍，總是用較小的圓覆蓋待監(jiān)測(cè)區(qū)域，算法所需部署的基站最多。

圖12 算法部署情況比較

4 總結(jié)

本文研究了定向充電中，在保證網(wǎng)絡(luò)可持續(xù)運(yùn)行的前提下使用冗余傳感器模型降低整個(gè)網(wǎng)絡(luò)成本的問題。其中，基站和傳感器節(jié)點(diǎn)的部署相耦合，同時(shí)還要考慮基站的充電調(diào)度和待監(jiān)測(cè)區(qū)域內(nèi)傳感器的激活調(diào)度。本文的策略是通過求解基站的最佳覆蓋范圍，解耦基站和傳感器節(jié)點(diǎn)的部署，然后通過迭代算法均衡每個(gè)充電基站的工作負(fù)載，使之保持在成本最低的工作負(fù)載附近，降低了整個(gè)網(wǎng)絡(luò)的成本。

此外，本文通過實(shí)驗(yàn)仿真來評(píng)估所提算法的性能。仿真結(jié)果證明了算法中不同步驟的有效性以及整個(gè)網(wǎng)絡(luò)的健壯性，并且與貪心算法相比，本文算法可以將整個(gè)網(wǎng)絡(luò)的成本降低約10%。