基于效用最大化的無線可充電傳感器網絡有向充電調度方案

王 楊 張 鑫 趙傳信 方 群 艾世成

①(安徽師范大學計算機與信息學院 蕪湖241002)

②(東南大學計算機科學與工程學院 南京211189)

1 引言

近年來，物聯網(Internet Of Things,IOT)的發展如火如荼，作為其核心的無線傳感器網絡(Wireless Sensor Networks,WSNs)已廣泛應用于環境監測、目標跟蹤、醫學和科學探索等領域[1]。但是傳統的電池供電方式導致了WSNs壽命受限。

為了解決這一問題，研究人員提出了如下3類解決方案。一是設法提高WSNs的資源利用率，進而減少傳感器節點的能量消耗。例如引入優化路由協議[2]、睡眠調度機制[3]、數據融合處理[4]、網絡分簇聚類[5]等策略。這類工作雖能減少網絡整體能量消耗并延長其壽命，但是難以從根本上解決WSNs的能量受限問題。二是通過能量收集技術收集傳感器周圍環境中的能量實現能量的補給。例如收集太陽能、風能和熱能等[6–8]。但是這種方法具有一定的天然不穩定性。三是通過磁耦合共振的無線能量傳輸技術遠距離對傳感器進行無線充電。如Tong等人[9]通過實驗驗證了無線充電技術在WSNs中應用的可行性。但是在WSNs中如何合理地調度移動充電器進行無線充電成為一個亟待解決的現實問題。

理論上，無線可充電傳感器網絡(Wireless Recharging Sensors Networks,WRSNs)可以永久保持工作狀態。但是，因為充電系統充電能力的局限性，例如：充電器總能量受限[10]，充電周期受限[11]，充電距離的影響[12]等因素，需要結合具體的充電任務進行調度規劃。

根據充電模型劃分，現有研究成果主要分為一對一[13–15]和一對多兩類充電模型[16–18]。前者往往假設移動充電器從基站出發，為沿途的傳感器節點提供一對一充電服務，最后返回基站的充電場景。在之前的工作[13]中，本文主要考慮了一對一充電模式下，從移動充電器調度、傳感器充電時間分配、節點速率控制協同優化來提高網絡性能。而Huong等人[14]則以最小化餓死節點數量為目標，提出了一種基于遺傳算法的充電調度方案。Zhao等人[15]以充電效率最大化為目標，建立了充電調度和充電時間分配的混合整數優化模型。并設計了兼顧充電任務和分配充電時間目標優化的離線算法。一對一充電方式的缺點主要是充電效率較低，并且在實施時受限于具體環境。

為了進一步提高移動充電器的充電效率，一對多充電調度方案應運而生。Liu等人[16]提出了一種多節點的時空域局部充電算法(Multi-node Temporal Spatial Partial Charging,MTSPC)。本算法首先構建一個盡可能滿足充電請求的充電方案，然后采用生成的充電方案來提高能源使用效率。而Zhang等人[17]提出了一種多節點可充電算法(Multi-node Rechargeable Algorithm,MRA)。該算法使用移動充電器定期訪問WRSNs中的每個對接站點并對覆蓋范圍內的節點充電。通過減少停靠點的數量并優化移動充電器的行駛路徑，從而提高充電效率。此外呂增威等人[18]則提出了一種基于多目標優化的WRSNs移動充電和數據收集聯合優化方案。上述方案僅僅假設移動充電器的充電模型為全向覆蓋，并沒有考慮有向天線情形。本文主要在現有研究工作的基礎上提出了一種基于充電效用最大化的有向充電方案。

2 系統模型和問題描述

2.1 網絡系統模型

2維平面中的無線可充電傳感器網絡可以表示為G=(V′,E)，其中V′=(V ∪S)。V是平面內隨機分布的傳感器節點，每個傳感器均配有容量為B的可充電電池，S代表網絡中的Sink節點。本文主要考慮通過一個移動有向充電器為WRSNs中傳感器進行周期性巡游充電的場景。網絡中心處放置一個基站v0，為巡游后的移動充電器補充能量以保證在下一個周期T內能夠完成充電任務。網絡系統模型如圖1。

2.2 充電模型

充電模型中的有向充電器采用一個5元組來描述：C j={(X j,Y j,A,θj,D)|j∈M}。其中Xj,Y j為有向充電器在2維平面中的錨點位置，θj為有向充電器朝向角度，A是有向充電器最大覆蓋角度，D為有向充電器最大充電半徑，M為有向充電器停車錨點集合。同時，采用二進制數Q c j,v i表示網絡中傳感器節點vi是否被Cj覆蓋到，如式(1)

其中，θ(C j,v i)為有向充電器與傳感器vi的夾角，

圖1 網絡系統模型

2.3 問題描述

本文試圖解決的問題是如何通過一個移動的有向充電器為WRSNs中多個傳感器節點同時充電。移動充電器從基站v0出發，沿著一條閉環的巡游路徑行駛，最終回到v0。在巡游過程中可能存在多個停車錨點使移動充電器停止移動，進行無線充電。假設這樣的錨點集合是M，并且據此規劃移動充電器的行駛路線。然后根據每個有向覆蓋集合內節點能量、位置等變量為每個錨點的覆蓋集合分配充電時間τ(t j){j∈M}，目標是使移動充電器充電效用最大化。

3 MUC調度方案

在MUC調度方案中，充電效用最大化問題被分解為3個階段優化：覆蓋集合的提取、覆蓋子集的篩選、充電時間的分配。

圖2 有向充電模型

3.1 覆蓋集合的提取

3.2 覆蓋子集的篩選

圖3 覆蓋集合提取示例圖

為了更直觀看出電池獲能過程，圖4模擬了剩余能量不同的兩個傳感器節點隨時間充電的獲能情況。

圖4分別為電池容量B=10000J，初始節點能量E R=0時，即節點能量從0開始充電的函數圖像；B=10000J, E R=2000J時，即節點能量從 2000 J開始充電的函數圖像。不難發現在相同充電時間下，剩余能量較少的節點充電獲能較多。

在覆蓋子集篩選上，將網絡中充電增益最大的覆蓋集合依次篩選出來直到全覆蓋。式(5)表示單個傳感器在覆蓋范圍內的充電增益

圖4 電池充電獲能圖

3.3 充電時間的分配

當確定了有向覆蓋子集后，需要采用智能算法確定一條最短巡游路徑。假定移動充電器能量有限，且在固定周期T內需要回到基站進行能量補給。因此需要對移動充電器的充電時間進行合理分配。事實上，傳感器充電時間分配問題可以通過式(7)描述

4 實驗及結果分析

本節通過實驗驗證和分析MUC調度方案的性能。

4.1 參數設置

實驗參數如表1所示。

4.2 基線算法

(1)本文采用以下兩種不同充電時間優化算法用于性能比較：

(a)固定能量充電(Fixed Energy Charging,FEC)算法：將有向覆蓋范圍內的所有節點能量充到某個閾值(60%)，隨后移動充電器巡游至下一錨點充電。

(b)平均能量充電(Average Energy Charging,AEC)算法：在能夠巡游覆蓋所有節點的前提下，將可用的充電時間平均分配給每個覆蓋集合。

(2)本文采用以下兩種不同覆蓋子集篩選算法用于性能比較：

(a)最多節點覆蓋(Maximum Node Coverage,MNC)算法：篩選出網絡中有向覆蓋節點最多的集合，直到覆蓋到每個節點。

(b)最大平均增益覆蓋(Maximum Average Gain Coverage,MAGC)算法篩選出網絡中有向覆蓋平均節點增益最大的集合，直到覆蓋到每個節點。

4.3 實驗結果及分析

傳感器節點隨機分布在150 m×150 m范圍內，初始能量隨機分配在0～B之間。

圖5是在不同節點規模下充電算法的充電效用對比圖。MUC算法比AEC算法提高13.7%，比FEC算法提高32.7%。在一定范圍內，MUC算法的充電效用隨節點規模的增加而提高，這是因為節點規模的增加會提高增益覆蓋子集篩選的多樣性。圖6是在不同節點規模下充電算法餓死節點數對比圖。MUC算法在不同節點規模下餓死節點數都明顯少于其他兩種算法。

表1 參數設置

圖7為參數p對充電算法的影響。p是與電池充電相關的參數。在p較大時電池充電效率較高；較小時充電效率較低。從圖7可以看出，在p變化范圍內，MUC算法充電效用優于FEC算法和AEC算法。這是因為MUC算法可以將移動充電器可用充電時間合理分配給傳感器節點。

圖8反映的是不同節點分布對充電算法的影響。在3種節點分布中，密集分布的充電效果最優。這是因為在密集分布的網絡中，巡游的移動充電器停車錨點數較少，移動能耗較低，傳感器可以分配到更多的可用充電能量。

圖5 不同規模下算法充電效用對比圖

圖6 不同節點規模下充電算法餓死節點數對比圖

圖7 參數p 對不同充電算法的影響

圖9為不同覆蓋算法下的覆蓋子集篩選圖。圖9(a)MNC算法試圖尋找網絡中覆蓋節點最多的覆蓋集合，并依次將集合加入覆蓋子集中，直到覆蓋所有節點。因此該算法的停車錨點數最少，路徑能量消耗最低；圖9(b)MUC算法試圖尋找網絡中覆蓋節點充電增益最大的覆蓋集合，直到覆蓋所有的節點。與MNC算法相比，停車錨點數目和移動充電器路徑能量消耗均增加，但是該算法可以更加合理地分配移動充電器的能量；圖9(c)MAGC算法試圖尋找網絡中覆蓋集合內平均節點增益最大的覆蓋集合。該算法在尋找覆蓋集合上趨向于單個節點或幾個節點充電以保證其覆蓋集合內平均節點增益最大。

圖8 不同節點分布對充電算法的影響

圖10為不同節點分布下覆蓋子集篩選圖。50個傳感器節點分別采用圖10(a)隨機分布、圖10(b)均勻分布、圖10(c)密集分布進行MUC覆蓋子集篩選。圖10表明，隨機與均勻分布不僅導致移動充電器移動軌跡較長且停車錨點數較多：分別為14個和19個。而密集分布方式下，不僅移動軌跡較短，而且停車錨點數較少：為11個，同時移動路徑的能耗也較低。

圖11為不同節點規模下子集篩選算法充電效用對比圖。MUC算法相比于MAGC算法提高了35.9%；相比于MNC算法在50節點，80節點時充電效用略低。這是由于在移動充電器行駛與充電過程中，根據真實采樣比例單位時間內行駛能量消耗遠大于單位時間內充電能量消耗。同時MNC算法的停車錨點數也少于其他兩種算法的。如圖9所示，MUC算法是24個停車錨點，MNC算法是22個停車錨點，而MAGC算法是85個停車錨點。所以在網絡規模較小時MNC充電效用最高。當節點規模達到110,140,170時，本文MUC算法充電效用也高于MNC。這是因為網絡中覆蓋子集的多樣性使移動充電器的充電能量最大化，而彌補路徑能量消耗較大的不足，MUC算法平均充電效用比MNC算法提高4.4%。

圖12是3種算法下網絡餓死節點數的對比情況。圖12表明，相比于其他兩種算法，MUC覆蓋算法餓死節點數明顯較少。

圖9 不同覆蓋算法下覆蓋子集篩選圖

圖10 不同節點分布下覆蓋子集篩選圖

圖11 不同節點規模下子集篩選算法充電效用對比圖

圖12 不同節點規模下子集篩選算法餓死節點數對比圖

5 結束語

本文提出了一種基于充電效用最大化的無線可充電傳感網絡有向充電調度方案。該方案首先根據網絡中傳感器節點能量和位置信息進行有向覆蓋子集篩選，然后將覆蓋區域的傳感器作為整體，優化其分配的充電時間以使充電效用最大化。本文算法主要適用于中小規模無線可充電傳感網絡。

在大規模無線可充電傳感網絡中，由于存在多節點同時發出能量請求的情形，此時單移動充電器的部署模式難以滿足現實需求。未來的工作中，將考慮大規模無線可充電傳感器網絡中多充電小車的有向充電調度問題。