聯合無線充電與數據收集的移動充電裝置多目標路徑規劃算法

韓雨澇，房鼎益

（1.攀枝花學院數學與計算機學院，四川攀枝花 617000；2.西北大學信息科學與技術學院，西安 710127）

（?通信作者電子郵箱183583460@qq.com）

0 引言

收集節點數據是無線傳感器網絡（Wireless Sensor Network，WSN）的基本任務，但由于節點能量耗盡導致WSN無法完整收集后續節點數據，影響數據收集的完整性。而數據完整性是影響數據質量的核心要素［1］。無線充電技術為傳感器節點提供可靠持續的能量補充，受環境因素影響小，具有充電范圍的靈活性和可控性的特點，因此可利用移動充電保證網絡中的節點持久運行采集數據。匯聚節點Sink在移動過程中收集監測區域節點數據，可有效避免“能量空洞”問題，提高WSN 網絡生命期。為此，移動充電裝置（Mobile Charging Device，MCD）結合移動Sink 和無線充電兩種策略，在網絡中移動收集數據同時進行無線充電，從而保證數據收集的完整性。另一方面，數據時效性是影響數據質量的重要因素之一，是大部分WSN 應用需要重點考慮的一個性能指標［2］。如何保證基站在指定延遲完整收集節點數據，從而獲得高質量的感知數據是一個挑戰性問題，這方面的研究工作目前尚少。文獻［3］針對節點能量和存儲容量受限的問題，周期性調度移動設備實現傳感器節點充電和數據收集；但該算法未考慮數據收集時效性問題。文獻［4］提出基于網格的移動裝置調度算法（Mobile Device Scheduling Algorithm and Grid-Based Algorithm，GBA+MDSA），采用網格算法確定訪問點集合，給出了移動設備的調度策略；但該算法時間復雜度較高。文獻［5］將WSN 數據收集和充電問題轉換為網絡效用最大化問題，在保持網絡公平的同時，最大化移動Sink 的數據收集；但未考慮節點存儲空間有限的實際問題，太過理想化。文獻［6］研究基于MCD 的無線充電和數據收集方案，提出了一種面向多目標優化的精英策略蟻群算法；但該算法需提前獲取每個節點位置信息，算法開銷較大。文獻［7］研究WSN 節點能量補充和數據收集問題，無線充電裝置沿預定路徑移動，最小化網絡節點能耗，同時確保傳感器節點及時充電以及數據完整性；但未考慮數據收集時延問題。文獻［8-9］研究并設計基于移動Sink 的節點數據收集和能量補充算法；但數據收集的可靠性得不到保證。文獻［10］采用一對一充電模式，移動充電裝置只能給少部分節點進行充電，增加了移動裝置數量以及網絡成本。文獻［11］使用一對多充電模式，將監測區劃分為多個訪問單元，移動裝置對單元內傳感器節點補充能量，通過優化移動裝置的移動線路完成節點充電時間優化；但未考慮網絡數據收集問題。文獻［12］提出時延受限移動式能量補充算法（Delay-Constrained Mobile Energy Charging algorithm，DCMEC），根據節點能量確定移動裝置線路；但移動裝置大跨度移動加大了數據收集的延遲。文獻［13］提出基于中心點的無線充電車（Wireless Charging Vehicle，WCV）移動調度方案，通過鄰居節點數量和能量確定WCV 訪問路徑；但WCV 成本較高且調度過程不易實現。

本文從數據完整性和時效性兩個方面提高數據收集質量。數據完整性要求MCD 具有良好的充電效率，保證節點可靠運行；數據收集的時效性要求節點產生的數據必須在指定時延內到達基站。本文研究多目標路徑規劃問題，首先建立聯合無線充電和數據收集的MCD 多目標路徑規劃模型，在此基礎上提出了一種基于貪心策略的聯合無線充電和數據收集的MCD 路徑規劃算法（Path Planning algorithm based on Greedy Strategy for MCD jointing wireless charging and data collection，PPGS）。本文主要工作為：

1）MCD 兼有無線充電和數據收集功能，在此基礎上建立保證數據收集完整性和時效性為目標的MCD路徑規劃模型。

2）通過馬爾可夫模型預測節點能量和數據采集量等參數，預估了MCD 錨點最小停留時間（Anchor Minimum Stopping Time，AMST）和錨點最長等待時間（Anchor Maximum Waiting Time，AMWT），保證PPSG 收集的數據具有完整性和時效性。

1 網絡模型

1.1 網絡基本模型

無線可充電傳感器節點在監測區域ζ（A*B）內隨機均勻部署構成無線傳感器網絡，其中，A、B為監測區域的邊長。網絡中包含N個傳感器節點集合N*，多個MCD 兼有無線充電和數據收集功能以及一個基站m0。

1）每個節點具有同型號的可充電電池，電池最大容量為Emax，剩余能量為Eresi，能量最小閾值為Emin。所有節點具有相同的通信能力，通信半徑為Rt。節點狀態分為休眠、感知和通信三種狀態，在感知狀態數據采集率為λi。

2）網絡中具有多個MCD 設備，均從基本m0出發，在每個單元錨點位置mi停留，采用一對多的充電模式為節點充電，同時利用時分多址（Time Division Multiple Access，TDMA）技術收集節點數據，最后返回到基站。假定每個周期MCD 能量和存儲空間足夠用，充電半徑為Rc，充電速率為vc，移動速率為vy，收集節點數據速率為vs，網絡全部錨點集合為B。為保證MCD 充電和數據收集性能，假定Rc≤Rt。MCD 對任意節點Ni按照如下模型進行充電：

其中：P表示節點充電功率；t為節點的充電時間；dist(MCD，Ni)為MCD與節點Ni之間的距離。

3）網絡中包含一個基站m0，MCD 在基站停留時間為Tval，主要負責MCD數據的卸載以及給MCD能量補給。

4）定義節點感知數據到基站接收的最大延遲為td。

1.2 MCD多目標路徑規劃模型

以保證數據收集完整性和時效性為目標的最小化MCD路徑規劃模型定義為：

上述式（2）～（4）反映數據收集完整性目標，分別對應：

式（2）要求MCD 的錨點訪問序列集合應包含全部錨點，實現網絡全部節點數據的收集。mi表示第i個錨點；Bn表示第n個MCD的錨點集合。

式（3）要求任意節點Ni剩余能量在MCD 下一周期訪問前不應低于閾值Emin，否則將成為死亡節點。

式（4）要求任意節點Ni的數據采集量Di在MCD下一周期訪問前不能超過其最大容量Dmax，否則數據將溢出。

而式（5）反映收集數據時效性目標：要求MCD 收集的節點數據從其產生直至到達基站的延遲不能超過td。

下面給出上述MCD 路徑規劃為NP（Non-deterministic Polynomial）難問題的證明。

證明 旅行商問題（Traveling Salesman Problem，TSP）屬于NP 難問題，假定一組城市為C=(C0，C1，…，Cm)，則TSP 表述為從指定城市C0出發遍歷每個城市一次且僅一次，最后返回到C0，要求總的移動距離最小。對該路徑規劃問題特殊處理：任意錨點mi對應一個城市名稱C0，基站m0對應城市C0，限定MCD 移動速率vy為1，錨點最小停留時間AMST為0，MCD 數量n為1，此時的MCD 路徑規劃問題為標準TSP，也就是TSP 為MCD 路徑規劃問題的一個特例，即證明了上述MCD路徑規劃問題屬于NP難問題。

2 PPGS設計

2.1 MCD訪問單元劃分策略

MCD 訪問單元面積過小將產生大量的訪問單元，加大數據收集的延時性；而訪問單元面積太大則影響節點的充電效率和數據收集的可靠性。為了保證MCD 充電效率以及最小化錨點數量，本文在文獻［14］的基礎上基于充電半徑Rc將監測區域ζ劃分為由如圖1所示的無縫銜接的正六邊形構成，正六邊形中心點到每個頂點距離為Rc。

圖1 基于正六邊形單元的監測區域劃分Fig.1 Monitoring area division based on regular hexagon cell

定義x軸貫穿圖1 第1 行每個基本結構的中心點。采用任意二元組(i，j)表示位于坐標系第i行、第j列的正六邊形單元。其中，i為位于坐標系所第i行的正六邊形單元，沿著y軸向上依次為第2 行、第3 行等；j表示當前位于第i行以y軸開始的第j個正六邊形單元。監測區域ζ正六邊形單元最小數η為：

每個正六邊形區域對應一個MCD 訪問單元，將每個單元的中心點定義為錨點位置。因此，上述η為監測區域ζ對應的錨點數|B|。

二元組（1，1）為坐標軸原點的正六邊形單元，故監測區域ζ內任意訪問單元(i，j)的錨點位置坐標為：

2.2 基于馬爾可夫模型的節點能量和數據采集量預測

PPGS需提前預測節點的能量，任意節點Ni的能量為：

其中：表示MCD 在周期Tk訪問節點Ni時的能量；表示節點Ni在=Tk+1-Tk時間隔內的能耗值。由MCD 在周期Tk離開Ni返回到基站的時間間隔、在基站的停留時間Tval以及在下一個周期Tk+1從基站到達Ni的時間間隔組成：

馬爾可夫預測模型［15］誤差值僅為3%，具有很高的可靠性。為此，本文采用馬爾可夫模型預測節點Ni在間隔對應α=個時隙能耗：

其中：μ表示在間隔內節點狀態的數量，休眠和感知兩種狀態設置的休眠狀態計時器和感知狀態計時器分別為Ti和TG。當計時器超時，節點Ni分別以PZ和1-PZ概率進入休眠狀態和感知狀態；表示節點Ni在狀態Z時單位時隙的能耗值；表示節點初始狀態為j，在τ步時隙后轉為狀態Z的概率；表示節點初始狀態為j，在α個時隙內處于狀態Z的時隙個數。

采用馬爾可夫模型預測節點在間隔內的感知數據量。由于節點在內僅在感知狀態下采集數據，因此感知數量為：

其中：g表示節點Ni的感知狀態；λi表示節點Ni在感知狀態下的數據采集率。另外，為了預測節點Ni數據發送最長等待時間和充電最長等待時間，分別采用馬爾可夫模型預測節點Ni從初始狀態到采集數據達到最大容量Dmax對應的時間間隔，以及節點Ni的能量從Emax降到Emin的時間間隔。由于篇幅限制，這里不再贅述。

2.3 訪問單元錨點AMST和AMWT估計與分析

基于節點能量和數據采集量等參數的預測，本節以訪問單元Uj為例，預估了MCD 在錨點位置mj的最小停留時間AMST和最長等待時間AMWT，并分析了其對算法性能的影響。由于節點隨機均勻分布，假定每個單元內節點數量為k。

MCD完成單元Uj內節點充電所需最小停留時間為：

MCD收集單元Uj內節點數據所需最小停留時間為：

綜上，MCD 完成單元Uj內節點充電和數據收集所需最小停留時間AMST為：

分析可知：如果MCD 在錨點停留時間小于AMSTmj，將不能完成Uj節點數據收集或充電，導致數據收集的不完整。

單元Uj內節點等待MCD充電的最長等待時間為：

單元Uj節點等待MCD收集數據最長等待時間為：

綜上，單元Uj節點等待MCD最長等待時間AMWTmj為：

分析可知：當等待時間超過AMWT，存在部分節點在MCD訪問之前能量耗盡或數據溢出的問題，這將影響數據收集的完整性。

2.4 基于貪心策略的PPGS路徑規劃

PPGS 無需提前獲取節點及錨點實際位置，只需按照式（7）計算每個錨點的相對位置坐標。MCD 從基站m0出發，錨點集合初始化為Bn(m0)，依次選擇距離上一停留點最近的錨點mi作為下一訪問單元Uj，當距離上一停留點最近的錨點有多個時，則隨機選擇一個錨點mi，再計算以mi為最后錨點的訪問周期T。

為了保證數據收集的時效性，要求：

為了保證數據收集性能，限定錨點最長等待時間不應超過錨點所在單元最小AMWT：

當上述條件均滿足，則將錨點mi加入到MCD的錨點訪問序列集合Bn，其中n為MCD編號，初始為1。

重復上述過程，當距離當前錨點mq最近的錨點mq+1被預選為MCD 的下一訪問點，但T＞td或者T-AMSTmq+1＞AMWTmq+1，則當前已選錨點序列Bn(m0，mj，mj+1，…，mq)作為第n個MCD 的訪問序列集合。第n=n+1 個MCD 將從基站出發，錨點集合初始化為Bn(m0)，按照上述貪心策略選擇最近錨點作為下一訪問點，重復以上過程直至滿足式（2）約束條件，算法結束。以下給出了PPGS的偽代碼描述。

算法4）～5）行初始化MCD 數量以及MCD 錨點訪問集合；第6）～22）行采用貪心策略確定MCD 數量以及每個MCD 的錨點訪問序列集合，其中：第8）～16）行表示當MCD 訪問周期T滿足延遲和最長等待時間約束，則將預錨點mi加入到當前錨點訪問序列集合Bn中；否則，算法第18）～19）行更新n=n+1，開始確定下一MCD錨點序列集合Bn。

3 PPGS時間復雜度分析

本章分析了PPGS 的時間復雜度。網絡中節點數為N，錨點數量為|B|，由于節點隨即均勻分布，假定每個單元節點數均為k。算法運行包括以下4個階段：

階段2 預測節點能量及感知數據量。該階段時間復雜度與錨點數|B|和單元節點數k有關，時間復雜度為O(|B|k)。

階段3 預估AMST和AMWT。該階段時間復雜度同上，為O(|B|k)。

階段4 確定MCD 路徑規劃。PPGS 使用貪心策略僅考慮錨點間距離因素，因此該階段的時間復雜度為O(|B|)。

綜上所述，PPGS 最壞情況下時間復雜度為O(1) +O(|B|k) +O(|B|k) +O(|B|)，又因|B|k≈N，故最終時間復雜度為O(|B|+N)。

4 仿真實驗與結果分析

本文選擇Matlab 7.0 作為仿真實驗平臺，傳感器節點在100 m×100 m 區域內隨機部署。選取基于訪問單元的一對多充電模式GBA+MDSA［4］和DCMEC［12］與本文PPGS 進行對比，首先比較監測區域所需最小錨點數量、MCD數量以及MCD在監測區域移動總距離，然后對三種算法網絡性能進行比較。仿真實驗部分參數設置見表1。

表1 部分仿真實驗參數Tab.1 Some simulation experiment parameters

4.1 算法所需錨點數、MCD數以及MCD移動總距離

4.1.1 不同充電半徑下最小錨點數

圖2為三種算法在不同MCD充電半徑下所需的最小錨點數。由圖2可以看出，隨著MCD充電半徑的增加，每種算法所需錨點數量降低，這是因為MCD 充電半徑直接決定訪問單元的大小：充電半徑越大則監測區域錨點數越少。另外，PPGS在不同MCD 充電半徑所需錨點數均低于其他兩種算法，這主要是因為：PPGS 的MCD 訪問單元為正六邊形區域，每個單元覆蓋面積達到；而其他兩種算法訪問單元劃分基于正方形區域，覆蓋面積僅均為，具有相同數量錨點，因此對應折線圖相同。

圖2 MCD充電半徑與錨點數量的關系Fig.2 Relationship between MCD charging radius and number of anchors

4.1.2 不同節點數量所需MCD數量

圖3反映了在不同節點數下三種算法所需的MCD數。由圖3 可以看出，隨著網絡中節點數的增加，三種算法所需的MCD 數隨之增加，這是因為監測區域節點數增加，使得每個訪問單元節點數隨之增加，為了完成單元內節點數據收集和充電，MCD 在錨點停留時間增加，使得每個MCD 能夠訪問錨點的數量減少。另外，PPGS 所需MCD 數要低于其他兩種算法，這是因為：第一，在監測區域面積相同情況下，PPGS 基于監測區域的劃分策略產生的錨點數最小。第二，PPGS根據錨點分布規律，使用貪心策略選擇MCD 的下一錨點，減少了因MCD 在監測區域大跨度移動導致的時間浪費，使得每個MCD可以訪問更多的錨點。而DCMEC 和GBA+MDSA 根據節點能量和訪問單元內節點數量選擇下一錨點，存在MCD 移動跨度大、運行效率不高的問題；DCMEC 所需MCD 數量低于GBA+MDSA，這是因為DCMEC 對訪問單元進行了限制，如果一個訪問單元內節點能量足夠使用，MCD 在下一周期不需要訪問該單元，減少了實際訪問單元的數量。

圖3 節點數量與MCD數量的關系Fig.3 Relationship between number of nodes and MCD number

4.1.3 不同充電半徑下MCD移動總距離

MCD 移動總距離與訪問單元數和MCD 移動策略有關。圖4 為不同充電半徑下三種算法的MCD 移動總距離。由圖4可以看出，隨著MCD 充電半徑增加，三種算法移動總距離明顯減少，這是因為充電半徑的增加，減少了監測區域訪問單元數量。同時進一步發現，PPGS 的MCD 移動總距離要小于其他兩種算法，這是因為PPGS 需要最少數量的MCD，減小了訪問單元和基站間往返移動距離。另外，PPGS在監測區域內不存在大跨度移動，也減小了MCD 在監測區域內移動的總距離。

圖4 MCD充電半徑與移動總距離的關系Fig.4 Relationship between MCD charging radius and total travel distance

4.2 網絡性能分析

本節在監測區域面積不變的情況下，分析了不同節點數量下無線傳感器網絡數據收集的完整性、時效性以及節點的充電效率三方面的性能。

4.2.1 數據收集完整性

數據交付率是指節點產生的數據量與基站收集的數據量的比值，能夠反映數據收集的完整性。圖5 為三種算法在不同節點數量下的數據交付率。由圖5 可以看出，隨著節點數量的增加，三種算法的數據交付率均降低，這是因為節點增加導致了無線信道沖突概率的增加，加大了數據丟失的概率。另外，節點數量增加使得一部分節點過早死亡，也降低了數據交付率。本文PPGS 數據交付率稍有降低，但整體仍然較高，最低可達到98.1%。這是因為PPGS 通過增加MCD 的數量保證了每個單元具有更多的停留時間。另外，PPGS收集數據采用的時分復用技術一定程度上也保證了數據收集的完整性。

圖5 節點數量與數據交付率的關系Fig.5 Relationship between number of nodes and data delivery rate

4.2.2 數據收集時效性

節點數據從產生直至到達基站的延遲反映了數據收集的時效性。圖6 為節點個數從100 增加到400，三種算法的數據收集延遲。可以發現，DCMEC 和GBA+MDSA 的數據收集延遲呈現出逐漸增大的趨勢，而本文PPGS數據收集延遲變化不大。這是因為節點數量的增加，雖然增加了MCD 在錨點等待時間，但由于有更多的MCD 并發收集數據，因此數據收集延遲變化不大，且都在數據時效性約束3 s范圍之內。

圖6 節點數量與數據收集延遲的關系Fig.6 Relationship between number of nodes and data collection delay

4.2.3 節點失效率

節點失效率是已死亡節點數量與總節點數量的比值，反映了MCD 的充電性能優劣。圖7 為節點數量從100 增加到400，三種算法的節點失效率。由圖7 可以看出，三種算法節點失效率均呈現出不同程度增加的趨勢。這是因為節點數量的增加導致了更多節點向MCD 提出充電請求，由于MCD 采用一對多電模式，這加重了MCD 的充電服務負擔，當充電負荷超過其充電能力時，部分節點因充電不足將會過早死亡。然而，本文PPGS 節點失效率整體較低，這是因為隨著節點密度增加時，MCD 在錨點具有更長的停留時間，降低了MCD 在單位時間內充電的負擔，極大地減少了節點因不能及時充電而迅速進入死亡的概率。

圖7 節點數量與節點失效率的關系Fig.7 Relationship between number of nodes and failure rate of nodes

5 結語

本文從提高無線傳感器網絡收集的數據質量包括數據完整性和時效性兩個方面入手，構建了MCD 數據收集和無線充電的多目標路徑規劃模型，然后提出了一種基于貪心策略的聯合無線充電和數據收集MCD 路徑規劃算法（PPGS）。實驗結果表明：本文PPGS 能以少量的MCD 保證網絡數據收集的完整性和時效性。與GBA+MDSA 和DCMEC 相比，PPAGS 在降低數據收集延遲的同時，提高了數據收集率，降低了節點失效率。

進一步研究構建節點剩余能量和數據采集量動態變化的隊列模型，以提高節點參數預測的準確性，進而保證數據收集的可靠性和低延遲性能。另外，在保證應用要求的基礎上，進一步研究如何通過優化移動設備的移動路徑以減少移動設備數量的問題。