胡 亮,孫楊燕,任 祝

(浙江理工大學(xué) 信息學(xué)院，浙江 杭州 310018)

0 引言

如今，在無(wú)線傳感器網(wǎng)絡(luò)中，電池是傳感器的主要能量來(lái)源[1-2]，但是電池容量限制了傳感器的使用壽命，也影響了傳感器網(wǎng)絡(luò)的整體表現(xiàn)[3]。無(wú)線可充電傳感器網(wǎng)絡(luò)可被視為一種通過(guò)引入無(wú)線能量傳輸技術(shù)的新型傳感器網(wǎng)絡(luò)[4]，其中，充電樁以電磁輻射的形式將能量傳輸?shù)絺鞲衅骶W(wǎng)絡(luò)中，而可充電的傳感器節(jié)點(diǎn)將通過(guò)配置的天線來(lái)接收射頻能量[5]。這種新型傳感器網(wǎng)絡(luò)因?yàn)槠浞奖阋仔泻褪褂脡勖L(zhǎng)已被廣泛使用，包括智能電網(wǎng)[6]、醫(yī)療保健[7]和環(huán)境監(jiān)控[8]等。

目前，研究無(wú)線傳感器網(wǎng)絡(luò)中的靜態(tài)充電樁部署較為稀少，且存在許多限制[9]。例如，文獻(xiàn)[10]研究了如何部署全向充電樁，使得網(wǎng)絡(luò)中靜態(tài)或動(dòng)態(tài)的傳感器節(jié)點(diǎn)能夠獲得足夠的能量維持正常工作，但是其僅僅討論了傳統(tǒng)的等距三角形部署，主要目的是盡可能減小三角形的邊長(zhǎng)；文獻(xiàn)[11]將傳感器區(qū)域劃分為網(wǎng)格，充電樁的覆蓋區(qū)域?yàn)閳A形，文中充電樁僅能放在網(wǎng)格頂點(diǎn)中，但實(shí)際上，充電樁可能部署在傳感器區(qū)域中的任何位置，而且該文中的充電樁覆蓋范圍不合理。在傳感器區(qū)域中傳感器位置固定的情況下，為了盡可能減少部署充電樁的數(shù)量，無(wú)需確保區(qū)域中每個(gè)位置接收到的能量都能滿足傳感器的消耗，只需要保證傳感器所在位置的能量能夠維持傳感器運(yùn)行即可。

本文主要針對(duì)能量受限的無(wú)線傳感器網(wǎng)絡(luò)，利用整數(shù)規(guī)劃研究充電樁的分布問(wèn)題[12]，根據(jù)已有的傳感器位置分布研究如何進(jìn)行充電樁的部署，盡可能用最少數(shù)目的充電樁使得每一個(gè)傳感器都能夠獲得足夠的能量維持自身運(yùn)行，從而優(yōu)化無(wú)線可充電傳感器網(wǎng)絡(luò)。

1 系統(tǒng)模型

假設(shè)無(wú)線可充電傳感器網(wǎng)絡(luò)區(qū)域Ω是一個(gè)二維平面，有M個(gè)可充電傳感器隨機(jī)分布在這塊區(qū)域上，并且用S={s1,s2,…,sm}表示這些傳感器，另外用C={c1,c2,…,cn}表示N個(gè)可用來(lái)部署充電樁的位置。下面需要決定是否在這些位置部署充電樁為該區(qū)域的所有傳感器提供足夠能量，使它們能夠正常持續(xù)的工作。

對(duì)于單個(gè)充電樁對(duì)傳感器的充電模型，用文獻(xiàn)[15]中已經(jīng)得到驗(yàn)證的充電公式來(lái)描述：

(1)

式中，d(si,cj)為傳感器si和充電樁cj的距離，Pr(d)為傳感器接收到的能量。

對(duì)于二維平面區(qū)域Ω的充電樁部署模型，用下面的公式來(lái)描述：

(2)

2 充電樁部署策略

2.1 充電樁位置固定

假設(shè)在可充電傳感器網(wǎng)絡(luò)區(qū)域中，隨機(jī)分布著M個(gè)傳感器用來(lái)采集信息，同時(shí)該區(qū)域中有N個(gè)固定的位置用來(lái)部署充電樁為傳感器提供能量，如圖1所示。目標(biāo)是從N個(gè)充電樁可以部署的位置中找到最佳的位置來(lái)部署充電樁，最大限度地減少整個(gè)區(qū)域中充電樁的數(shù)量并確保所有傳感器正常工作。

圖1 充電樁位置固定示意圖

2.1.1 問(wèn)題轉(zhuǎn)化

對(duì)于任意傳感器si，總共接收到區(qū)域中所有充電樁的能量為：

(3)

(4)

2.1.2 充電樁位置固定部署算法

2.2 充電樁位置不固定且不受限

前面描述了充電樁位置固定的情形，但是一些情況下，充電樁可以部署的位置并不固定。如圖2所示，假設(shè)傳感器區(qū)域中隨機(jī)分布著M個(gè)傳感器，但是并沒(méi)有給出充電樁可以部署的地點(diǎn)，需要在該區(qū)域中部署最少的充電樁來(lái)維持傳感器的正常工作。

因?yàn)槲恢貌还潭ǎ枰獙⒄麄€(gè)區(qū)域進(jìn)行網(wǎng)格化，每個(gè)網(wǎng)格的頂點(diǎn)都可以當(dāng)作一個(gè)部署位置，這樣問(wèn)題將會(huì)轉(zhuǎn)化為充電樁位置固定的問(wèn)題，且隨著劃分的不斷加密，所需要的充電樁個(gè)數(shù)將會(huì)減少到一個(gè)穩(wěn)定的最小值。

圖2 充電樁位置不固定且不受限示意圖

2.2.1 問(wèn)題轉(zhuǎn)化

(5)

2.2.2 充電樁位置不固定且不受限部署算法

2.3 充電樁位置不固定且受限

在實(shí)際環(huán)境中，充電樁的部署可能會(huì)受到區(qū)域限制，即充電樁只能部署在傳感器區(qū)域的某個(gè)地方或不能部署在傳感器區(qū)域的某個(gè)地方，比如，區(qū)域中存在一些建筑物、交通要道或者水域等等。由于這2種限制比較相似，只考慮充電樁不能部署在區(qū)域中的某些地方的這種情形，如圖3所示，A1,A2區(qū)域?qū)⒔共渴鸪潆姌丁?/p>

圖3 充電樁位置不固定且受限示意圖

2.3.1 問(wèn)題轉(zhuǎn)化

得到如下新的目標(biāo)函數(shù)和約束條件：

(5)

(X,Y)?(A1∪A2),

2.3.2 充電樁位置不固定且受限部署算法

3 仿真結(jié)果

3.1 充電樁位置固定

如圖4所示，黑色圓點(diǎn)表示在傳感器區(qū)域中隨機(jī)分布的傳感器，黑色矩形框表示可以部署充電樁的位置，黑色三角形表示需要在該位置部署充電樁。如圖4(a)和圖4(b)所示，2幅圖的傳感器分布一致，由于可以部署的8個(gè)位置不同，需要的充電樁總數(shù)可能不同。在圖4(a)的部署位置分布下，需要至少4個(gè)充電樁才能維持該傳感器網(wǎng)絡(luò)的正常工作，而在圖4(b)的部署位置分布下，只需要3個(gè)充電樁就可以維持傳感器網(wǎng)絡(luò)的正常工作。

圖4 充電樁位置固定時(shí)的最佳部署

3.2 充電樁位置不固定且不受限

對(duì)于充電樁位置不固定且不受限的情形，設(shè)置長(zhǎng)度為30 m的正方形區(qū)域，隨機(jī)分布著20個(gè)傳感器，其余參數(shù)與位置固定時(shí)保持一致，如圖5所示。

圖5 充電樁位置不固定且不受限時(shí)的部署

在圖5(a)中，整個(gè)傳感器網(wǎng)絡(luò)區(qū)域被劃分為5×5的網(wǎng)格，劃分間隔為6 m。在這種劃分情形下，找不到一個(gè)可行解使得所有傳感器能夠持續(xù)正常的工作，即在36個(gè)可以部署充電樁的網(wǎng)格頂點(diǎn)中找不到足夠的位置來(lái)部署充電樁。

在圖5(b)中，將劃分間隔縮小為3 m，即將整個(gè)區(qū)域劃分為10×10的網(wǎng)格。因此可以得到121個(gè)可以用來(lái)部署充電樁的位置。相比于圖5(a)，在這種劃分情形下，可以部署至少16個(gè)充電樁來(lái)為整個(gè)網(wǎng)絡(luò)提供能量。

在圖5(c)中，劃分間隔進(jìn)一步被縮小到1 m。由于劃分更加密集，因此相比于圖5(b)，只用15個(gè)充電樁就可以滿足所有傳感器的能量需求。隨著劃分間隔不斷縮小，整個(gè)網(wǎng)格將近似覆蓋整個(gè)區(qū)域，所需要的充電樁將減少到一個(gè)穩(wěn)定的最小值。

在圖5(d)中，充電樁個(gè)數(shù)已達(dá)到一個(gè)穩(wěn)定的最小值，即隨著劃分密度的增加，充電樁的個(gè)數(shù)將不會(huì)減少，為了便于分析圖中劃分間隔設(shè)為0.5 m，最終整個(gè)區(qū)域所需要的最少充電樁為14個(gè)。與圖5(c)相比，整體的部署趨勢(shì)沒(méi)有發(fā)生改變，在傳感器較密集的地方，所需要的充電樁也會(huì)比較多，一些遠(yuǎn)離群體的節(jié)點(diǎn)將會(huì)單獨(dú)需要一個(gè)充電樁來(lái)滿足自身的能量需求。

3.3 充電樁位置不固定且受限

對(duì)于充電樁位置不固定且受限的情形，同樣設(shè)置一個(gè)長(zhǎng)度為30 m的正方形區(qū)域，但是在左上角存在一個(gè)受限的矩形區(qū)域，右下角存在一個(gè)受限的圓形區(qū)域，整個(gè)正方形區(qū)域隨機(jī)分布著20個(gè)傳感器，分布位置與充電樁位置不固定且不受限時(shí)一致，其余參數(shù)與充電樁位置固定時(shí)相同,如圖6所示。

圖6 充電樁位置不固定且不受限時(shí)的部署

在圖6(a)中，傳感器網(wǎng)絡(luò)區(qū)域任意被劃分成25個(gè)小區(qū)域，而所有的傳感器位置保持不變，左上角矩形區(qū)域和右下角圓形區(qū)域均不能部署傳感器。與圖5(a)相比，在同樣的劃分條件下，部署區(qū)域有了更多的限制，因此，在這種劃分下也找不到一個(gè)可行解。

在圖6(b)中，傳感器網(wǎng)絡(luò)區(qū)域被以間隔為3 m進(jìn)行劃分，在這種劃分情形下，部分頂點(diǎn)落在了左上角和右下角的不可部署區(qū)域內(nèi)。從圖中可以看出，在有限制的條件下，至少需要21個(gè)充電樁才能滿足需要，而圖5(b)在同樣劃分情況下只需要16個(gè)。

在圖6(c)中，劃分間隔被進(jìn)一步縮小到了1 m，因此只需要17個(gè)充電樁就可以滿足傳感器的能量需求，比圖6(b)少了4個(gè)，但是要比圖5(c)多用2個(gè)。

在圖6(d)中，充電樁的數(shù)量已經(jīng)減小到一個(gè)穩(wěn)定值。即整個(gè)有限制區(qū)域最少需要的充電樁的數(shù)量為16個(gè)，比沒(méi)有限制的圖5(d)要多用2個(gè)。觀察分布圖可以發(fā)現(xiàn)，在有限制的區(qū)域，充電樁一般會(huì)沿著限制區(qū)域的邊界進(jìn)行分布。

4 結(jié)束語(yǔ)

針對(duì)無(wú)線可充電傳感器網(wǎng)絡(luò)中的靜態(tài)充電樁的部署，對(duì)于可部署位置無(wú)窮的情況，創(chuàng)新性地利用網(wǎng)格分割方法將傳感器區(qū)域離散化處理，極大地簡(jiǎn)化了充電樁的部署問(wèn)題。然后利用Intlinprog函數(shù)分別給出了在3種情形下的部署算法，并且通過(guò)Matlab仿真顯示，與已有的蜂窩型部署相比，本文方法減少了所需充電樁的數(shù)量。