基于定向充電模型的最大化網絡累計充電增益

章 豪，王 然

(杭州電子科技大學 計算機學院,浙江 杭州 310018)

在無線傳感器領域中，無線能量傳輸技術的出現與發展為解決傳感器節點充能問題提供了新的思路，保證了網絡的正常工作。無線能量傳輸技術與從所處環境中得到能量的技術不同[1-3]。無線能量傳輸技術通過在網絡中部署調度移動充電小車對傳感器進行無線充電，能夠更加穩定地為網絡充能，提高了充電效率[4-6]。

隨著技術的進步，將能量傳輸形式抽象為單對單充電和單對多充電兩種模型。單對單充電模型指充電器每次只對單個節點充電，該模型使用電感耦合技術[7-8]，其有效充電距離一般在20 cm以內，需近距離進行能量傳輸。單對多充電模型指充電器同時為多個節點充能，可分為全向無線充電和定向無線充電。全向無線充電采用磁共振耦合技術，不受充電方向限制。文獻[9]通過實驗證明了能量可以在磁共振體之間進行傳輸，并且不需要任何媒介。例如，為2 m外的一盞60 W白熾燈供電的效率可以達到40%。定向無線充電要求節點在一定的距離與角度范圍內，該模型采用電磁波輻射技術，在能量傳輸及接收設備中使用高增益定向天線，提高了能量傳輸效率，使其覆蓋距離更遠，例如毫米波蜂窩網絡[10]。

研究人員對于定向無線充電模型進行了研究與應用。文獻[10]研究了部署固定數量充電器的方式，最大化網絡中節點能夠接收到的充電效率。文獻[11]假設網絡所使用的節點接收能量也受方向限制，節點和充電器必須處于相對方向才能夠進行能量傳輸。該研究解決的問題是不論節點朝著哪個方向都能夠接收到能量，并且接收功率不低于給定閾值。文獻[12～13]將充電器部署在距離網絡一定高度的平面上，通過對該平面進行網格化，確定充電器的最佳部署位置。不同的是，文獻[12]只考慮節點能否被覆蓋到，優化目標是確保每個節點都能被覆蓋到，而文獻[13]加入了對節點能量消耗率和接收率的考慮，優化目標是確保每個節點的能量接收率不小于消耗率。

本文的研究基于定向充電模型，在保證無線可充電傳感器網絡持續運行的情況下，最大化網絡累計充電增益的充電小車優化調度問題。

1 網絡模型與假設

1.1 傳感器節點模型

在基于定向充電的傳感器網絡中隨機拋灑傳感器節點。傳感器節點皆具有數據感應、數據生成和傳輸、能量接受的功能。網絡中傳感器節點可分為可充電節點和匯聚節點。可充電節點負責感應監控環境生成數據，通過多跳路由把感知的數據傳遞給匯聚節點。

環境感應、數據生成與傳輸是傳感器節點的主要能耗方式。假設傳感器節點數據對1 bit數據進行感應，傳輸和接收所需能量為ec，根據文獻[14～ 15]有

(1)

其中，e0表示傳感器用于數據感知、數據編碼和調制的能耗；e1表示單位比特的能量損失系數；dr表示傳感器之間的傳送數據距離；α表示路徑損耗系數(一般為2～4)，本文假設各個節點獲得信息速率相等。

1.2 充電小車模型

(2)

節點的能量接收功率可以基于Friis方程[16]計算

(3)

其中，Pr是能量接受功率；Pout是能量發射功率；L是路徑耗損因子；GT是發射天線增益；GR是接收天線增益；λ是發射波的波長；η是整流器效率；β是用于調整自由方程的參數；d是發射與接收天線之間的距離。

1.3 網絡模型

如圖1所示，在L×L的區域中任意隨機拋灑n個傳感器節點S={s1,s2,…,sn}。網絡中任意節點總容量為Emax，m輛移動充電小車集合為MC={mc1,mc2,…,mcm}，集合中任意小車的總電量為Cmc，其輸出功率為Pmc。靜止基站b位于網絡平面的中心位置。為確保網絡持續運行，充電小車以T為周期對傳感器節點進行周期性充能。

圖1 定向充電傳感器網絡模型Figure 1. Directional charging wireless sensor network model

2 問題定義

無線傳感器網絡中等待充電感器節點集合為S={s1,s2,…,sn}，傳感器節點最高電量Emax記為Cv，剩余電量為Rv，集合中任意節點si∈S的能量接收速率為γi，能耗速率為pi。集合MC={mc1,mc2,…,mcm}為充電小車集合，集合中任意小車mci∈MC的總電量均為Cmc，其輸出功率為Pmc，通過效用函數f(x)模擬傳感器充能，候選停靠點集合A={a1,a2,…,an}，候選停靠點aj∈A對應傳感器節點si∈S的位置。b為基站給小車充能。每個候選停靠點aj∈A的包含的傳感器節點記為Sai，給Sai充電需要消耗Τai的時間。

從基站b出發，充電小車mck∈MC中途停靠在aj∈A，對Sai中的傳感器節點進行定向充電，充電周期為T，完成充能后返回基站b進行充電。在保證傳感器網絡持續運行的前提下，最大化網絡累計充電增益。該問題形式化定義為

(4)

(5)

(6)

ηajyaj>δ,j∈S

(7)

yaj≤ua,j∈S

(8)

(9)

Tpizik=Taγizik,i∈Sa

(10)

Emax-(T-Ta)·pi≥Emin,i∈Sa

(11)

xijk,yia,zik∈{0,1},a∈A,k∈MC

(12)

3 近似算法

3.1 充電方向選擇算法

充電方向選擇是指在當前候選停靠點下選擇充電小車的充電方向，具體過程是：首先充電小車以每個不同的節點為一個邊界逆時針旋轉；然后確定每個朝向覆蓋到的節點集合并計算每個方向的覆蓋效用，如圖2所示。

圖2 定向充電方向選擇過程Figure 2.Process of directional charging direction selection

偽代碼如下：

算法1最大覆蓋效用充電方向選擇算法。

輸入傳感器集合O={o1,o2,…,oN}；充電器位置(cx,cy)；充電器的覆蓋距離D；覆蓋角度為A。

1.OCS=?，i=0；

2.當i

3.計算傳感器Oi與充電小車的歐幾里得距離di，如果di

4.循環結束；

5.如果OCS=?，算法結束，否則繼續第6步；

6.L=len(OCS)；

7.計算集合OCS中的傳感器與充電器位置形成的夾角集合θ={θ1,θ2,…,θL}，并且將集合OCS中的傳感器按照對應的夾角大小升序排序；

8. CU=?，k=0，當i

9.把充電器覆蓋扇形px的始邊擺于OCS[k]；

10.將終邊置于(θk+A)%360；

11. CU=CU∪{CUk}，k=k+1；

12.循環結束。

輸出MCU和Umax。

3.2 停靠點選擇算法

停靠點選擇算法調用了方向選擇算法，將二位傳感網絡劃分為網格，以網格的頂點作為候選停靠點位置。充電小車每次停下來只選擇一個方向進行充電，充電器的覆蓋范圍是一個半徑為D的90°扇形，只有滿足每個扇形可以對網絡全覆蓋的前提下才可能確保沒有節點遺漏。

偽代碼如下：

算法2最大化覆蓋效用總和停靠點選擇算法。

輸入傳感器集合O={o1,o2,…,oN}。包括每個節點的索引值和對應的坐標點；充電器的覆蓋距離為D；覆蓋角度為A。

1.對二維傳感器網絡進行格式化，以網絡交點作為候選停靠點，獲得充電器候選停止位置集合CS={cs1,cs2,…,csi,…,csn}；

2.令最終被選的停止位置集合FCS←?，令其對應的停止位置覆蓋集合為Ns←?；

3.當O≠?并且CS≠?時；

4.AUmax=0，AMCU=?，csmax=?，i=0；

5.當i

6.調用方向選擇算法，得到csi位置最大覆蓋效用值Umax及其最大覆蓋效用節點集合MCU；

7.若Umax>AUmax，則AUmax=Umax，AMCU=MCU，csmax=csi；

8.循環結束；

9.如果AUmax=0，循環結束，否則繼續下一步；

10.FCS=FCS∪{csmax}，Ns=Ns∪{AMCU}，CS=CS-{csmax}，O=O-{oi/oi∈AMCU}

11.循環結束。

輸出FCS和Ns。

3.3 路徑規劃算法

(1)Pj的能耗之和不大于充電小車的最大容量CMC，即

(13)

(2)pj路徑上總的消耗時間小于小車充電周期T，即

(14)

(15)

偽代碼如下：

算法3基于分解TSP的路徑規劃算法。

輸入停靠點集合D，充電小車集合MC，在停靠點a處對節點j的充電效率ηaj，充電小車容量Cmc，服務基站b，充電周期T，TSP路徑p=(b,Π1,Π2,…,Πn,b)。

1.當p≠?時；

4.獲得第j條閉合回路用p=(b,Π1,Π2,…,Πn,b)

5.從TSP路徑中去掉pj包含的停靠點，j←j+1；

6.結束循環。

輸出充電小車mcj的充電路徑pj。

4 網絡規模分析

分析計算網絡對應所需充電小車的數量，首先要對單小車可服務網絡規模進行分析計算。假設小車充電隊列集合為p=(Π0,Π1,Π2,…,Πn,Π0)，集合中Π0是基站位置，Π0i(1≤i≤n)是傳感器si∈S所在位置。在充電隊列p=(Π0,Π1,Π2,…,Πn,Π0)中任意相鄰節點間最大距離為lmax。為了保證傳感器網絡的持久化運行，需要滿足如下要求：

(1)單位充電周期內，充電小車對節點充電的總電量不小于隊列中節點消耗的總電量，即

(16)

其中，v是充電小車的移動速率；T是充電周期；pMC是充電小車充電功率；n是節點數量；c是節點的平均能耗速率，推導得

(17)

(18)

因為pMC≥c，所以f′(t)≥0，即單個充電小車服務的節點數與充電周期時長正相關；

(2)單位充電周期內，所有節點的剩余能量不低于節點正常工作的最低電量。假設節點的初始電量為滿電量Emax，所以周期長度T有

(19)

(20)

5 模擬實驗

在100 m×100 m、200 m×200 m和300 m×300 m的區域中分別多次隨機拋灑50、100、150、200、250、300、350、400、450、500個節點，從網格大小、網絡規模、充電形式等因素來分析其對充電小車能量利用率與累計充電增益的影響。無線充電小車依照前文所述模型和算法對節點進行充電。

在100 m×100 m的區域中多次分別隨機拋灑100、300、500個節點，改變網格大小，分析對充電小車充電效率的影響。

圖3 網格大小對充電效率影響Figure 3. Effect of grid size of charging efficiency

圖3顯示了隨著網格大小的減小，充電小車的充電能量利用率正在提高。當節點數量為100，網格大小由7 m減少到1 m時，充電小車的充電效率提高了近38%。當節點數為300，網格大小由7 m減小到1 m時，充電小車的充電效率提高了近27%。當節點數為500，網格大小由7 m減小到1 m時，充電小車的充電效率提高了近23%。由此可見，隨著節點數的增加，充電效率的提升有所減緩，當前網絡規模下網格大小為1 m時效果最佳。

圖4 網絡規模對于充電累計增益的影響Figure 4. Effect of the size of network on the charging efficiency

由圖4可知，隨著節點數量的增加充電小車的能量利用率在逐漸提高。由于節點的數量增加，因此充電小車每次能夠覆蓋到節點數增加，因此更多的能量被節點接收，能量利用率得到了提高。同時，在節點數量不變區域變大時，充電小車的能量利用率在降低，因為節間的距離變大，充電小車消耗在路上的能量增多，導致充電小車能量利用率降低。

圖5 節點數量對于充電累計增益的影響Figure 5. Effect of the number of nodes on the cumulative charging utility

圖5顯示了在100 m×100 m的區域不同節點數量對于網絡累計充電增益的影響。在相同節點數量下，定向充電的網絡累計充電增益高于全向充電，且隨著節點數量的增加同種充電方式的網絡累計充電增益在增加，在200～250個節點的情況下效果尤為顯著。而當節點數大于250個以后，全向充電的增幅低于定向充電，說明此時全向充電的充能利用率不如無線充電。

6 結束語

本文研究了基于定向充電模型，在保證無線可充電傳感器網絡持久運行的情況下，最大化網絡累計充電增益的優化調度問題。針對該問題，本文提出了近似算法。近似算法包括3個部分：(1)基于最大化覆蓋效用的方向選擇算法；(2)基于方向選擇的最大化覆蓋累計效用的停靠點選擇算法；(3)基于TSP的路徑規劃算法為充電小車規劃移動路徑。通過仿真實驗對比不同的充電策略。實驗結果顯示，相比全向充電，本文提出的充電策略可以明顯提升網絡的累積充電增益。定向充電模型是無線可充電傳感器網絡無線充電領域中新興的模型，基于定向充電模型還有很多新的研究方向，例如如何延長網絡生命周期等。