無線可充電傳感器網(wǎng)絡(luò)中的充電樁部署

胡 亮,孫楊燕,任 祝

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

0 引言

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

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

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

1 系統(tǒng)模型

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

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

(1)

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

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

(2)

2 充電樁部署策略

2.1 充電樁位置固定

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

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

2.1.1 問題轉(zhuǎn)化

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

(3)

(4)

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

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

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

因為位置不固定，需要將整個區(qū)域進(jìn)行網(wǎng)格化，每個網(wǎng)格的頂點都可以當(dāng)作一個部署位置，這樣問題將會轉(zhuǎn)化為充電樁位置固定的問題，且隨著劃分的不斷加密，所需要的充電樁個數(shù)將會減少到一個穩(wěn)定的最小值。

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

2.2.1 問題轉(zhuǎn)化

(5)

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

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

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

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

2.3.1 問題轉(zhuǎn)化

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

(5)

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

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

3 仿真結(jié)果

3.1 充電樁位置固定

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

圖4 充電樁位置固定時的最佳部署

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)束語

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