WRSN中多MC協同的一對多能量補充策略*

唐 拓馮 勇李英娜錢 謙付曉東

(昆明理工大學云南省計算機技術應用重點實驗室，云南 昆明 650500)

物聯網(Internet of Things)的飛速發展離不開無線傳感網絡(WSNs)提供的技術支持，無線傳感器網絡是現代社會應用最廣泛的信息采集技術，被廣泛應用于醫療健康、基礎設施狀態監測、智能交通、生態環境監測以及軍事攻擊監測等領域[1]。WSN中的傳感器由于受到自身尺寸與成本的限制，通常使用電池進行供電，運行時間受限于電池的容量。得益于無線能量補充技術的發展，利用無線充電技術延長無線傳感網絡的生存時間已得到廣泛的研究，無線可充電傳感網絡(Wireless Rechargeable Sensor Networks，WRSNs)正在興起。在WRSNs中使用配備有無線移動充電設備的移動裝置(Mobile Charger，MC)為傳感器節點提供可靠的能量補充，能夠有效減少節點的充電等待時間，成為解決傳感器電池能量受限問題的有效解決方案[2-3]。由于WRSNs中的傳感器節點失效會導致數據丟失、鏈接斷開甚至網絡癱瘓等嚴重問題，如何調度MC高效地為網絡中的傳感器節點補充能量是WRSNs充電策略的關鍵問題。

WRSNs往往布置在極端或較復雜的環境，MC接近傳感器節點進行充電有一定困難且效率較低，基于磁耦合諧振充電技術的一對多充電方式允許MC在充電范圍內同時對多個傳感器節點進行能量補充，不僅使MC可在安全地區對傳感器進行能量補充，擴展了WRSNs的應用場景，同時提高了充電效率。磁耦合諧振充電技術[4-5]是目前廣泛應用于WRSNs中的能量傳輸技術。通過在MC和傳感器上分別安裝發射線圈與接收線圈，調節成相同頻率，能量通過強諧振耦合在線圈之間發生傳遞，可在一定范圍內實現一對多無線能量補充。文獻[6]利用相鄰的正六邊形單元格平等分割網絡，傳感器節點被覆蓋在單元格內，MC周期性移動到單元格中心位置通過磁耦合諧振充電技術來實現能量的無線傳輸。但是該方法未考慮MC充電成本以及距離對諧振充電能量傳輸的影響，算法性能較低。

隨著對WRSNs的規模需求不斷提高，使用單MC進行充電已無法達到網絡的需求，這是由于MC無法攜帶足夠的能量在一個充電循環中為大規模WRSN中的每個請求節點進行充電，MC在給一部分傳感器節點充電后需要返回基站補充自身能量。這種方式不僅充電效率極低而且傳感器節點常常由于得不到及時的能量補充而失效。此時需要部署多個MC為網絡中的傳感器節點充電，但是MC往往價格昂貴，出于成本考慮應使MC數量盡量少。

設計了一種高效的多MC協同充電策略，通過相交圓算法將網絡中的傳感器節點劃分為若干個節點簇，利用最短距離原則確定各個簇的MC充電駐點，之后根據能量約束平衡條件確定網絡需要的MC數量，最后通過優先級分配算法使多個MC能夠協作對網絡進行充電，提高充電效率與能量利用率。

本文第一節介紹了相關工作。第二節概述了網絡模型與問題公式。第三節中詳細描述了MTORN算法的設計步驟與理論分析。第四節通過仿真實驗對比分析所提方案的性能。第五節總結全文。

1 相關工作

本部分簡要介紹WRSNs中的能量補充技術。

一對一充電模式中，MC只能在同一時間給一個傳感器節點充電。He等[7]提出一種最近節點優(NJNP)原則來解決充電節點的選擇問題，但是該方案忽視了響應充電請求的公平性，低電量節點易失效死亡。Dai等[8]考慮了候選充電節點的選擇與每個節點的充電時間，之后根據傳感器接收到的能量來調度MC的移動規劃，最大限度地提高網絡的充電效用。文章將問題形式化為最大QoM充電和調度問題(MQCSP)，但是如何獲得MQCSP的精確解卻未給出較好的解決方案。

一對多充電模式的出現極大地提高了充電效率，更適用于大規模WRSNs中。Kurs等[4]首次提出一對多能量傳輸技術，允許多個接收器通過單個電源同時充電，有效地解決了單對單充電模式的可擴展性問題，并提高了整體能量傳輸效率。但是該方法未考慮MC充電駐點的規劃，系統充電效率還有極大提高空間。文獻[9]研究了在線模式下的多節點充電問題，作者提出了一個充電規劃算法來最大化可充電的傳感器數量，并指示充電位置，以降低MC移動能耗。但是該方法增加了節點的充電等待時間且未考慮充電的均衡性。

為了進一步提高充電效率，學者們開始研究多個MC充電的方式。在文獻[10]中，作者假設所有傳感器具有相同的恒定能量消耗率。通過規劃MCs的路徑，以找到MCs的最小數量，從而延長網絡的運行時間。然而由于環境的隨機性，傳感器能耗往往具有較大波動性，該方法無法適應WRSNs的實際應用情況。在文獻[11]中，作者提出了一種稱為PushWait的調度算法，MCs不僅可以給傳感器充電，還允許它們相互充電。為最大化充電效率，該算法平衡MC充電功耗與移動功耗，同時保證網絡中傳感器的能量充足。該方法優化了網絡的能量利用率，但隨著傳感器節點數量的增加，所需MC的數量會急劇增加，導致成本過高。

可以看出，現有的充電策略存在對充電均衡性考慮不足以及難以得到最優解等缺陷。由于WRSNs充電優化問題的NP-Hard特性，許多啟發式算法也同樣面對著在網絡規模較大時無法高效解決WRSN充電優化問題的挑戰。

為了解決上述問題，提出了MTORN充電算法。以按需充電的模式，在WRSNs中部署多個MC通過一對多充電的方式協同為網絡提供及時且穩定的能量補充。同時，引入優先級分配算法來提高動態WRSN中的充電均衡性。

2 網絡模型與問題公式

2.1 網絡模型

系統模型如圖1所示。本文的無線可充電傳感網絡模型主要由三個部分組成:(1)配備有無線能量接收器的若干個傳感器節點(sensor node)(S i＝S1，S2，…S n)；(2)配備有無線充電器的多個MC(M j＝M1，M2，…M m)，MC具有自主移動、計算和通信的能力；(3)基站(BS)，負責收集和處理傳感器節點傳輸的數據，監控整個網絡的狀態，同時為MC補充能量。所有傳感器節點隨機部署在二維地圖上，節點位置可以精確地確定，傳感器節點在自身剩余能量下降到預先設定的閾值lr時主動地向MC發送充電請求，MC可以在區域內自由移動，MC通過無線充電的方式同時為多個傳感器節點充電，并在自身電量過低時返回基站為自身補充電量。

圖1 網絡模型圖

MC具有4種狀態，分別為空閑、移動、充電和返回基站狀態，如圖2所示，空閑狀態表示MC當前未接收到任何充電請求；移動狀態說明MC已確定候選充電簇并向其移動；充電狀態表示MC正在為節點簇進行充電；返回基站狀態表示MC已完成充電任務或自身能量較低，返回基站補充能量。

圖2 MC狀態轉移圖

2.2 問題公式

本節描述系統中能量消耗、能量補充的模型。

2.2.1 能量消耗模型

對于每個傳感器，其能量消耗主要由兩部分組成:監測任務和數據傳輸。因此可以根據傳感器節點的監測效率和數據傳輸率來預測各個傳感器節點的功耗范圍和剩余能量。節點S i(1≤i≤n)的能量消耗速率P i可表示為:

式中:j為節點S i接收數據的源節點，G j，i(t)表示節點S i接收到的信息總和，k為節點S i轉發數據的目的節點，G k，i(t)表示節點S i轉發的信息總和；α為信號放大器能耗率；d i，j，d i，k分別表示節點S i與節點S j，S k的距離；ρ為接收1 bit信息所消耗的能量。σ為傳感器進行監測任務的能耗率，G i(t)為節點S i的監測信息總和。

節點S i在t時刻的能量消耗為:

2.2.2 能量補充模型

MC可以在其范圍內的對多個傳感器節點進行無線充電。對于節點S i，接收充電的功率為:

式中:d S i，MC是MC和節點S i之間的距離，P c為充電時的源功率，β為調整短距離傳輸的弗里斯方程參數。G S為發射增益參數，G R為接收增益參數，L P為偏振損耗，σ為整流器效率，λ為波長。

為了提高充電效率和網絡生存時間，我們需要盡可能增大簇內每個節點的能量接收功率P S i。

3 MTORN策略設計與實現

3.1 MC充電駐點的位置確定

當MC的充電范圍為R時，MC能夠通過無線能量傳輸給以MC為圓心，半徑為R的范圍內多個傳感器節點充電。為MC確定充電駐點目的在于使MC在每個充電駐點能夠同時為更多的傳感器節點充電。駐點位置的確定分兩步實現，第一步通過相交圓算法對節點進行分簇，第二步根據最短距離原則確定各個簇的充電駐點。相交圓駐點選擇算法具體步驟如圖3所示。

圖3 相交圓駐點選擇算法示例圖

相交圓駐點選擇算法:對于一組傳感器節點S＝{S1，S2，…，Sn1}，給定每個傳感器節點S i(1≤i≤n1)都有一個以S i為圓心，半徑為R(MC充電范圍半徑)的圓，由此可以得到一組相應的圓集合C(｜C｜＝｜N｜)。如果兩個或多個圓存在公共交集區域，具有上述特點的傳感器節點可劃分為一個簇。這個公共交集區域，就是充電駐點的可選部署區域。例如Ci與圓C j以及Ck相交，則三個節點S i、S j、Sk的重疊區域表示為Aijk，將Aijk中所有的坐標點放入一個集合VTijk＝{VT1，VT2，…，VTn2}，充電駐點的位置Pm便從VTijk中選擇。

由于無線充電功率隨著距離增大而減小，因此采用駐點與簇內各節點總距離最短原則確定駐點位置。假設P m，VTm，S i，S j，S k的二維坐標為(x P m，y P m)，(x Tm，y Tm)，(x Si，y Si)，(x Sj，y Sj)，(x Sk，y S k)，其中(1≤m≤n2，1≤i，j，k≤n1)。可以得到下式:

根據上式可以得到距離簇內各個傳感器節點總距離最短的駐點二維坐標位置。

確定MC的充電駐點位置之后，將傳感器節點i，j，k加入簇C m中。按照該方法可將整個網絡劃分為若干個節點簇。對于孤立節點(即與其他節點圓沒有公共交集區域的節點)MC需要對其單獨充電。

3.2 確定最優MC數量

本節的目標為確定能夠滿足網絡電量需求的最優MC數量。MC價格高昂，在區域中部署過多的MC不符合現實要求，同時MC面臨無線充電技術本身的能量損耗以及移動產生的能量損耗問題。因此網絡中部署的MC需要使網絡整體能耗保持平衡，即m個MC輸出的能量要維持自身移動能耗同時滿足網絡的能量需求。根據以上約束建立能耗平衡約束條件:

假設在一個范圍固定的WRSN中，隨機部署有n個傳感器節點，節點按3.1的方法被劃分為L個節點簇，C i表示第i個部署有節點的簇，網絡中有m個可以響應充電請求的MC，MC為節點充電的效率為P S i。MC在兩個節點簇之間移動的距離為:

式中:L代表節點簇的個數，d C i，C j代表兩個節點簇中心之間的歐氏距離，d代表充電簇中心之間的平均歐式距離。假設MC在網絡中兩個節點簇之間的移動距離為d，則m個MC總的的移動能耗為:

式中:P T代表MC移動能耗率。當網絡中所有發起充電請求的節點能量需要被充滿時，網絡的能量需求為:

ESN為傳感器節點的電池容量，E0為發起充電請求的電量閾值，P S i為節點接收充電的功率，n q為網絡中發起充電請求的傳感器節點個數。

m個MC能補充的電量為:

EMC為MC電池容量，ETH為能夠維持MC返回基站補充能量的電量閾值，m為MC個數。

綜上，為使網絡的整體能耗保持平衡，需滿足:

即:

對上式兩邊同乘m，移項可得:

轉化為一元二次等式求解，由于EMC-ETH＞0，因此式(11)相應的數學模型是開口向上且過零點的拋物線，易知一元二次等式的兩個解分別為0和m，0不符合要求應被舍棄，確定另一個根m的邊界值向上取整即可得到網絡最優的MC個數。

3.3 多MC協同充電算法

本節的目標為處理多MC充電系統的協同合作關系。本文引入簇的優先級分配充電算法，多個MC接收充電請求，并每隔T時間檢查服務池內的充電請求信息集合，這些信息主要包括簇中節點的剩余能量R s以及簇的充電駐點位置。

初始時MC的狀態設為空閑，并位于網絡的中心位置。當接收到節點的充電請求時MC會更新服務池，并計算相應簇的優先級ψ(C m)。ψ(C m)表示簇C m的充電優先級，反映了該節點簇需要充電的緊迫程度，是MC進行充電決策的重要依據。其計算公式如下:

式中:Eresidual為簇C m內所有傳感器節點的平均剩余能量，Nrequest為發起充電請求的節點個數，N C m為簇C m內的所有節點個數。推導過程如下:

ωN為節點因子，與簇內發起充電請求的節點數量有關。簇內發起充電請求的節點數量Nrequest越多，簇內節點的平均剩余能量Eresidual越低，與MC的距離越近，簇的優先級越高。即簇的優先級與節點因子成正相關，與距離因子和能量因子成負相關，從而有:

綜合式(13)～式(16)可得式(12)。

在MTORN中，為了保證網絡的充電均衡性，收到充電請求超過其服務能力的MC可以向當前充電可用性較大(即相對空閑)的MC發送幫助消息，將充電任務分配給網絡中的其他MC。接下來給出MC當前充電可用性的定義以及計算公式:

式中:E j為移動充電器m j的剩余能量，ωn為MC的任務因子，N j表示移動充電器m j接收到的充電請求數量，N r為網絡中所有的充電請求數。在某一時間，MC需要處理的充電請求較少，與簇的距離較近，自身剩余能量較大，則該MC的充電可用性也較大。即MC的充電可用性與任務因子ωn和距離因子ωd成負相關，與能量因子ωe成負相關，因此可以得到:

式中:ωse為能量因子，表示簇內平均剩余能量。

綜合式(18)、(19)可得式(17)。通過對充電任務的合理分配，不僅可以均衡網絡中MC的能耗，還可以避免網絡中節點因電量過低而失效。

多MC協同充電算法偽代碼如算法1所示。

算法1 輸入參數:執行3.1得到的充電簇c1，c2…cn，多個MC輸出結果:各個MC的充電序列

1. 初始化MC參數{ωN，ωe，ωd}2. for all MC i do 3. if MC接收到充電請求then 4. add充電請求into S 5. 計算簇的D(Ci，mj)min以及E residual＝E1＋E2＋…＋EN 6. 計算簇優先級ψ(Cm)7. ψ(C m)max簇為候選充電簇8. else //MC無法處理過多的充電請求9. 計算其他MC的U(mj)10. 向U(m j)較大的MC發送幫助消息11. 由U(mj)較大的MC處理對應優先級較高的充電任務12. end if 13.end for

3.4 充電序列規劃

充電序列規劃的目標就是根據所得到的節點簇的優先級來決定MC的充電路線(即確定的充電次序)，使多個MC給節點簇補充能量時盡可能地減少自身移動能耗，用有限的能量為傳感器補充更多的能量。從而減少失效節點數量、MC移動距離，提高充電均衡性，延長網絡生命周期，。

當一個MC接收到多個充電請求時，首先將充電請求放入自身的充電服務池中，之后對充電請求進行解析并計算其所在節點簇的優先級。最后MC將各自要處理的充電請求與其對應的優先級保存在充電序列S q中，每次從序列中選取優先級最大的節點簇C m作為候選充電簇，之后各個MC前往不同節點簇的充電駐點通過無線能量傳輸對簇中所有節點進行充電。多MC充電序列規劃結果如圖4所示。

圖4 多MC協同充電序列規劃示例圖

3.5 算法描述

本文提出的MTORN算法具體流程如圖5所示。

圖5 算法框架圖

總之，MTORN策略主要通過以下3個步驟達到多個MC協同對網絡進行充電的目標:首先，MTORN通過相交圓算法對網絡中的傳感器節點進行分簇，再利用最短距離原則為各個充電簇設置最優的充電駐點；其次，根據網絡的能耗以及MC自身移動能耗合理估計網絡需要的MC數量，部署最優數量的MC為多MC協同充電策略提供了基礎；最后，MC在接收到充電請求后根據節點簇的平均剩余能量以及距離劃分出請求簇的優先級，每次選擇候選充電簇時，均選擇優先級最高的節點簇，以最小化網絡中由于電量較低而失效的節點數量。另外，當某個MC的充電任務超過其服務能力時，可以向其他相對空閑的MC發送幫助信息，提高充電的均衡性。

4 仿真

本文構建了一個無線可充電傳感器網絡仿真環境，建立100 m×100 m的區域，并隨機部署50個～300個傳感器，MC在自身電量不足時回到基站處補充自身能量。實驗仿真參數如表1所示。

表1 仿真參數

文使用Python實現了MTORN算法，并與HCCA[12]算法和Cellular[6]算法進行性能對比和評估。HCCA算法是一種WRSN混合聚類充電算法(HCCA)，采用分層聚類和K-means聚類實現位置和能量感知，之后將充電行為形式化為任務，通過任務分割算法HCCA-TS調度MC進行充電。Cellular算法利用相鄰的正六邊形單元格平等分割網絡，MC周期性移動到單元格中心位置對范圍內節點進行充電。

4.1 移動成本

本組實驗討論各算法在不同節點數量和MC電池容量下的MC平均移動成本情況，移動成本是MC移動的總路程。如圖6(a)所示，隨著節點數量的增多，三種算法的MC移動成本均增加，這是因為隨著節點數量增加，充電請求會增加，MC需消耗更多能量移動，從而使得移動成本增加。可以看出MTORN方案的移動成本始終低于其他兩種方案。圖6(b)可以看出MC的移動成本隨電池容量的增大而增加，這是因為更大的電池容量會使MC在一個充電周期內的移動時間延長，從而可以進行更多的移動。

圖6 移動成本對比

4.2 節點死亡率

節點死亡率表示未及時得到能量補充而失效的節點占總節點的百分比。如圖7(a)所示，節點失效率隨著節點數量的增多而呈升高趨勢，這是由于節點數量增多時，向MC發送的充電請求也會增多，超過MC的服務能力時，死亡節點數量將會增加。可以看出本文提出的MTORN方案的節點死亡率要低于HCCA和Cellular算法，這是由于本策略提出一種優先級充電算法，MC會優先選擇剩余電量較低的節點進行充電，極大地避免了節點失效死亡。圖7(b)所示，MC電池容量較大時，MC可以在一個充電輪次中為更多節點補充能量，因此MC電池容量越大，節點死亡率越低。

圖7 節點死亡率對比

4.3 網絡生存時間

網絡生存時間指WRSN從開始運行到結束的時間，當網絡中失效節點達到設定的閾值時，剩余的節點不足以組成連通的網絡，網絡停止運行并計算生存時間。由圖8(a)可以看出，三種算法的網絡生存時間隨著節點數量的增加而降低。原因是節點數較高超過了MC的服務能力，MC無法滿足所有充電請求，使得失效節點數量增加，最終導致了網絡生存時間降低。在圖8(b)中，由于MC電池容量的增大能有效減少節點死亡率，因此網絡生存時間也相應延長。可以看到HCCA和Cellular算法的網絡生存時間始終低于MTORN。

圖8 網絡生存時間對比

4.4 MC數量

本組實驗討論不同MC數量下的MC充電成本以及節點死亡率。如圖9(a)所示，MC數量增加，各個MC的移動成本相應降低。這是因為當MC數量增加時，多個MC可以協作完成充電任務，減少了移動開銷。在圖9(b)中，隨著MC數量增加，節點死亡率降低，這是因為當MC數量增加時，每個MC能共同處理更多的充電任務，更及時地為節點充電，因此節點死亡率下降。

圖9 MC數量變化情況

5 總結

本文提出了一種WRSNs中多MC協同的一對多充電策略，適用于具有密集節點的大規模WRSNs。本文目標為，使多個MC在一對多充電方式下，協作完成對WRSNs的能量補充，最大化充電效率，降低節點死亡率。本文首先通過相交圓算法將WRSN中的傳感器節點劃分為若干個簇，利用最短距離原則確定各個簇的充電駐點位置。再通過能量約束平衡條件確定網絡需要的MC數量，之后MC根據簇的平均剩余能量和距離劃分優先級，每個MC根據優先級前往不同的簇并對簇內多個傳感器節點同時進行充電。仿真實驗結果表明，與現有的一對多充電方案相比，MTORN方案能夠有效降低節點死亡率與MC移動成本，延長網絡生存時間。