一種基于非均勻分簇的實時充電算法?

尹 玲謝志軍陳科偉

(寧波大學信息科學與工程學院，浙江 寧波315211)

無線傳感器網絡(Wireless Sensor Networks，WSNs)作為當今世界獲取信息的重要途徑之一，由自主分布在空間內若干個固定位置的傳感器節點組成。 隨著數據量的提升，節點有限的電池容量已不足以支撐WSNs 的長久運行。 因此，各種能量補充技術應運而生，越來越多的學者加入了對無線可充電傳感器網絡( Wireless Rechargeable Sensor Networks，WRSNs)的研究。

有學者提出從環境中獲取能量，如把風能、太陽能和熱能等轉化為節點可用的電能[1-3]，但此類能量的獲取過程不受人為控制，難以保證能量收集的效率和時效性。 近幾年興起的無線充電技術以其充電效率高、充電過程可預測等優勢，成為了研究的熱點，其中移動充電方式更加適合本文的研究背景——具有實時性要求的WRSNs，此類網絡由能量有限的移動充電器(Mobile Charger，MC)負責為節點補充能量，如若補充不及時節點便陷入休眠，從而影響WRSNs 的性能。 因此，合理規劃MC 的充電路徑，選擇合適的充電順序和充電時間，對于延長網絡的生命周期至關重要。

考慮到充電成本，目前關于移動充電的研究大部分采用單MC 的方式，以較小的充電代價達到較大的網絡效用。 文獻[4]在給節點定期充電的基礎上，設計了混合粒子群優化遺傳算法來解決周期性充電的問題；文獻[5]設計了一種能量平衡的聯合路由和充電框架，分別針對路由樹和充電路徑提出相應的優化算法。 為提高充電效率，文獻[6-7]采取了定向充電的方式，其中文獻[6]研究了最小充電延遲問題，設計了一種充電功率離散化方法來實現定向充電并減小充電延遲；文獻[7]則設計了一種近似算法來確定充電對接點及充電方向，同時最小化定向充電車對接點的數量并最大化充電覆蓋范圍。 以上研究的重點在于預先規劃好一條最佳路徑，以保證較高的節點存活率和充電效率，適用于靜態路由。

對于復雜可變的WRSNs 來說，按需充電則更加合適。 文獻[8]按需確定節點的最佳充電順序，設計了針對MC 調度問題的線性規劃模型，并提出基于引力搜索算法(Gravitational Search Algorithm，GSA)的解決方案；文獻[9]提出一種基于模糊邏輯的按需充電調度方案:只給能耗高的節點充電，通過共同衡量剩余能量，到MC 的距離和關鍵節點密度等網絡參數來決策MC 的充電路徑；類似地，文獻[10]根據節點到基站的距離和能耗率把WRSNs 中的節點分成兩類并采用不同的充電策略，對于距離基站距離近且能耗高的節點采用一對一充電，相反距離基站距離遠且能耗低的節點采用一對多充電，通過研究節點的充電時隙提出最小移動成本算法(minimum travel cost algorithm，MTC)。

大型WRSNs 還可以使用多個MC 協同充電，文獻[11]首次針對最長延遲最小化問題，設計了一種具有恒定近似比的近似算法；文獻[12]建立數學模型以量化節點的充電條件與具有不同電池容量的MC 的可達性條件之間的關系；考慮到MC 的造價昂貴和協調多個MC 工作的復雜性，文獻[13]研究了最小化MC 數量的問題。

在現有關于WRSNs 充電規劃的研究中，大多在于根據能量、距離和時延等網絡因素預先規劃MC的充電路徑，在靜態網絡中表現良好。 但對于動態變化的WRSNs 來說，節點的能耗差異大，且實際網絡中的不穩定因素多，動態的充電決策更有優勢。本文為合理規劃具有實時性要求的WRSNs 中MC的充電路徑，提出一種基于非均勻分簇的實時充電算法(nUCRC)，首先將網絡作非均勻分簇處理，根據節點的能量狀態和截止充電時間決定簇頭的選舉與輪換，在每個充電周期內MC 依照最短移動路徑原則依次訪問各個簇中心，并根據簇內節點的時間和空間特征有序選擇節點進行充電。 文章的主要創新點總結如下:①為提高基站的管理效率，將網絡作非均勻分簇處理，并根據節點的剩余能量和截止充電時間共同決策簇頭的選舉和輪換；②使用動態規劃算法(Dynamic Programming，DP)決策MC 的最短移動路徑，并根據簇內節點的截止充電時間和到MC 距離的混合優先級決定簇內節點的充電順序。

文章的其余部分安排如下:第1 節介紹了具有實時性要求的WRSNs 模型；第2 節詳細描述了所提的基于非均勻分簇的實時充電算法(nUCRC)；第3節給出了仿真實驗與結果分析；最后在第4 節總結了本文并指出未來研究方向。

1 網絡模型

本節首先介紹了WRSNs 的模型，并給出問題描述與解決方案。

1.1 問題描述

圖1 所示的WRSNs 中隨機分布了若干個具有唯一ID 且位置固定的能量有限的無線可充電傳感器節點，負責監測網絡環境并收集數據，并將收集的數據交由該簇的簇頭節點，簇頭節點則以多跳的形式將從簇內普通節點匯聚的數據傳送給基站，簇頭節點承擔匯集該簇內數據并轉發至BS 的工作，能耗高且重要；一個MC 在每個周期內攜帶有限的能量從基站出發，負責為網絡范圍內的節點充電；一個能量不限且位置固定的基站(Base Station，BS)負責匯聚簇頭節點收集的數據，并為MC 規劃充電路徑；MC 能夠準確定位節點和BS，從而完成充電任務并返回BS 進行充電維護。 BS 需要按照一定的規則規劃MC 的充電路徑，既要優先為能耗大的節點充電，以保證最高的節點存活率，還要盡可能減少MC 的移動路徑長度，保證盡可能低的充電時延。

圖1 采用nUCRC 算法的WRSNs 模型

1.2 解決方案

為解決上述問題，本文設計的目標是在單個充電周期T內，MC 的移動路徑最短、節點存活率δ最高:

式中:d(i，V)表示MC 移動總路徑，Nlive是存活節點數，N為節點總數。

考慮到MC 攜帶的能量要大于為節點充電耗費的能量，并在一個充電周期T內完成為節點充電和返回BS 處進行充電維護，有如下能量約束和時間約束:

式中:T0是MC 自身充滿電需要的時間，si是節點Si開始充電的時間，ti是節點Si結束充電的時間，Pr是MC 從BS 收集能量的速率，Pc是節點從MC 收集能量的速率，Em是MC 的移動耗能，eMC表示MC 的剩余能量，Tm則表示MC 的移動時間，T是MC 的充電周期。

為實現所提目標并滿足約束條件，本文設計了一種基于非均勻分簇的實時充電算法(Real-time Charging algorithm based on non-Uniform Clustering，nUCRC):首先將網絡做非均勻分簇處理，分簇完成后，通過衡量簇內節點的剩余能量以及截止充電時間選舉簇頭，在每個充電周期內，MC 按照最短移動路徑依次訪問各個簇中心，根據節點的時空特征選擇要充電的節點以及充電順序，并在靠近BS 的時候返回BS進行充電，然后繼續按照原定路線訪問剩下的簇，遍歷完所有簇后返回BS 進行充電維護并結束當前充電周期，待充電維護結束開始下一充電周期。 以下的部分詳細描述了所述的nUCRC 算法。

2 非均勻分簇的實時充電算法

nUCRC 算法分為兩步實現以上目標:非均勻分簇和充電路徑規劃。

2.1 非均勻分簇

分簇有利于提升BS 的管理能力，使網絡更加高效、有序地運行。 對于含有單個MC 的WRSNs 來說，假設共有N個節點需要分為K個簇，各節點距離BS 的距離、能耗率都不一樣，由于MC 在一個充電周期內可能會多次返回BS 處進行充電維護，因此靠近BS 的節點被充電的機會更大，為均衡網絡中節點被充電的機會，使靠近BS 的簇內節點數量更多，降低靠近BS 節點的被充電機會，提升遠離BS的節點被充電的機會。 所以本文采用非均勻分簇的方法，使得距離BS 近的簇半徑大、包含的節點數量多，而距離BS 遠的簇半徑小、包含的節點數量少。

2.1.1 簇半徑的計算

網絡運行初期，N個節點分別計算其到BS 的歐式距離di:

式中:xi(1≤i≤N)表示節點Si的位置，xBS表示BS的位置。 根據計算得到的di值決定該節點Si擬加入的簇半徑大小Ri，并且Ri的值與di值成反相關關系。 BS 收到N個節點的di后，分別計算以這N個節點為中心的簇半徑:

式中:ε表示預期的最小簇半徑與最大簇半徑的比值，當ε＝0 時表示此時網絡采用均勻分簇，取ε＝0.5；dmax是節點距離BS 的最大值；dmin是節點距離BS 的最小值；R0表示候選簇頭節點最小簇半徑值。

2.1.2 簇頭節點的選舉

為減少傳送到BS 的數據量，由簇頭節點負責收集來自該簇內普通節點所產生的數據，進行數據融合后經過多跳的形式轉發給BS(即距離BS 遠的簇頭節點匯集的數據將轉發給距離BS 近的簇頭節點，讓其轉交給BS)，其能耗要高于普通節點，因此簇頭節點的選舉對于WRSNs 的長久運行至關重要。開始時各節點競選簇頭的概率ρi＝ρ＝1/N，根據式(4)計算出的簇半徑，當某個節點當選簇頭后，處于其簇半徑內的其他節點就退出簇頭競選，而成為該簇內的普通節點。 首先，各節點在網絡范圍內廣播競爭消息，廣播的消息包括:節點的唯一IDSi、與BS的距離di、簇半徑Ri、當前剩余能量ei和能耗率qi，首輪選擇K個節點當選簇頭，原則如下:

①當前剩余能量ei最高；

②截止充電時間Di最大:

由于當前剩余能量最高的節點不一定是存活最久的節點，還需要考慮節點的能耗率，即計算節點的截止充電時間，當截止充電時間到期后節點還沒充上電，該節點就陷入休眠，因此應當按照剩余能量和截止充電時間的混合優先級決定簇頭的選舉:

式中:α和β表示加權因子，用來衡量能量因素和時間因素影響簇頭選舉的程度，取α＝β＝0.5，表示由節點的剩余能量和截止充電時間公平選舉簇頭；ρi值越大表示節點Si當選簇頭的概率越大，選舉ρi最大的值當選簇頭，當兩個節點的ρi值相等且處于對方的簇半徑內時，節點ID 小的當選簇頭，而另外一個節點成為該簇內普通節點。

首輪K個簇頭節點選舉出后，每個簇頭節點需要維護一個簇內節點的集合:

圖2 非均勻分簇流程圖

2.2 MC 充電路徑規劃

確定了非均勻的成簇方法以及簇頭節點的選擇，還需要確定MC 的簇間移動路徑及簇內節點的充電順序，確保最短的移動路徑長度，使得每個充電周期內能量有限的MC 能將更多的能量用于給節點充電，并盡可能降低充電時延，保證充電的時效性。本文分別從最短路徑規劃和充電順序選擇來實現以上目標。

2.2.1 簇間移動路徑規劃

為確保最短的移動路徑，使得單個充電周期內MC 從BS 出發，遍歷所有簇，且每個簇只經過一次，充電周期結束再回到BS，整個回路總路徑長度最小，這是典型的旅行商(TSP)問題。 對于本文單個MC 的情況，分簇個數不會太多，因此采用DP 算法來解決最短路徑問題。

根據2.1 節中構建的簇，計算每個簇的簇中心

式中:｜Ck｜表示簇Ck內含有的節點數，dCsk-1，Csk表示任意兩個簇中心的歐式距離，V表示簇中心的集合:

令d(i，V)表示從源點BS 出發，經過中各個頂點i一次且僅一次，最后回到BS 的路徑長度:

上式表示當集合V為空時，di，BS表示直接返回BS，而當V不為空時，整體路徑最短問題就轉換為部分路徑最短問題的最優求解。

MC 移動總耗能Em和移動時間Tm分別計算如下，其中，f是MC 以速度v移動d的距離所耗費的能量:

MC 在移動過程中靠近BS 時，會返回BS 進行充電維護，維護完畢會按既定路線繼續完成充電任務，當遍歷所有簇后返回BS 處，完成一次充電周期。

2.2.2 簇內節點充電順序選擇

當MC 移動到簇Ck的中心時，選取簇內能量低于電池容量50%的節點進行充電，避免了全充造成較大的充電時延。 無線能量傳輸采用改進的適用于WRSNs 的Friis 能量傳輸模型[14]:

式中:PC是簇中節點從MC 接收能量的功率，P0是MC 的發射功率；Gs和Gr分別是MC 的發射天線增益和節點的接收天線增益；η是整流器的效率；λ表示波長；d是MC 與被充電節點的充電距離；Lp表示極化損耗；γ是調整Frris 自由空間方程用于短距離傳輸的參數。

給單個節點Si的充電持續時間TC(Si)由節點當前剩余能量ei、節點電池總容量EN以及能量傳輸模型(12)共同決定:

MC 給節點Si充電耗費的能量則由充電時間和充電耗能共同決定:

對于選取的待充電節點，通過考慮該簇內節點的截止充電時間和距離MC 的距離共同決策充電順序，由時間優先級和空間優先級共同定義混合優先級，按照混合優先級從高到低的次序依次為選取的節點充電。

定義簇頭節點SCkH的截止充電時間為DCkH，最小的節點截止充電時間為，最大的節點截止充電時間為，得到時間優先級為:

同樣定義dCkH是簇頭節點到MC 的距離，距離MC 最近的節點的距離為，距離MC 最遠的節點的距離為，得到空間優先級為:

將時間優先級和空間優先級結合得到混合優先級如下:

式中:α和β表示加權因子，與式(6)類似，此處的α和β是衡量時間和空間對于MC 充電順序的權重，加入對數項是為了防止出現重復的混合優先級值。對于簇內所有ei≤EN×50%的節點，計算其混合優先級的值φ(m)(i)，值越小的節點具有更高的優先級，享有優先充電的權利。 當簇內所有符合條件的待充電節點完全充電后，該簇進行簇頭輪換，重新計算簇內所有節點的ρi值，最大的當選新一任簇頭。

圖3 給出了待充電簇內有6 個符合充電條件節點的例子，由式(13)可知，由節點的開始充電時間si和充電完成時間ti可得到節點的充電持續時間，由于MC 同一時刻只能給一個節點充電，計算待充電節點的混合優先級并排序，按混合優先級從高到低依次給節點充電。 MC 在簇內的移動時間相對于充電時間可忽略不計。

圖3 MC 根據優先級按序為簇內節點充電

非均勻分簇的實時充電算法(nUCRC)工作流程如圖4 所示。

圖4 nUCRC 算法工作流程圖

3 實驗仿真與結果分析

3.1 參數設置

本文在Pycharm 平臺采用Python 語言仿真所提的nUCRC 算法，并將結果與當前最新的相關研究工作進行了比較。 在大小為100 m×100 m 的WRSNs 區域內，隨機布置了100 個位置固定的無線可充電傳感器節點，一個能量不限的BS 以及一個能量有限的MC，MC在每個充電周期內遍歷所有簇，并為簇內需要充電的節點按序充電，實驗參數的設置如表1 所示。

表1 實驗參數設置

實驗分別將本文所提nUCRC 算法與文獻[8]所提的GSA 算法以及文獻[10]提出的MTC 算法作性能對比，分別從節點存活率和平均充電時延方面進行了對比分析，同時還研究了網絡規模對nUCRC算法性能的影響。

3.2 仿真結果分析

3.2.1 節點存活率對比

首先對比了幾種算法的節點存活率，圖5 描述了程序運行500 min 期間節點存活率的變化情況?？梢娫谇?00 min 采用三種算法的節點存活率都為100%，程序運行到250 min 時，采用GSA 算法的節點存活率明顯下降；當程序運行到500 min 時，GSA算法的節點存活率已經下降到90%以下，MTC 算法的節點存活率下降較為緩慢，約為95%，而nUCRC算法由于事先采用了非均勻的分簇方法，且在選擇節點進行充電的時候采用了時間和空間的混合優先級，因此有更好的存活率表現，相較于其他兩種算法，節點存活率分別提高約4%和10%。

圖5 節點存活率對比

3.2.2 平均充電時延對比

圖6 分別描述了MC 不同的移動速度和電池容量對平均充電時延的影響。 由(a)圖可見隨MC 移動速度增加，采用nUCRC 算法和MTC 算法的平均充電時延緩慢下降，這是因為nUCRC 算法采用了最短移動路徑思想，所以總體充電時延低于MTC 算法；而采用GSA 算法的平均充電時延則隨移動速度的增加先增大后減小，先小幅度的增大是由于隨速度增加，待處理的充電節點數量增加，MC 往返眾多節點之間，但隨MC 速度的進一步提升，充電時延也隨之下降。 (b)圖描述的是平均充電時延隨MC 電池容量的變化情況，當MC 電池容量僅為5 000 J時，三種算法的平均充電時延都較小，這是因為很多節點都由于能量不足已陷入休眠，隨著電池容量增大，有更多節點等待充電，時延也隨之增大，而本文的nUCRC 算法由于采用了時空混合優先級選擇節點充電，使急需充電的節點的等待時間變短，因而在平均充電時延方面也具有最佳的表現。

圖6 平均充電時延對比

3.2.3 網絡規模的影響

本文還研究了網絡規模對nUCRC 算法性能的影響。 圖7 給出了不同的網絡規模對單個充電周期時間的影響。 隨著網絡規模增大、節點數增多，簇的數量也增多了，MC 充電任務加重，需要訪問更多的簇、為更多的節點充電，完成一次充電周期所花費的時間就更長。 當網絡規模為50 m×50 m，節點數N＝50 時，完成一次充電周期至多需要130 s，最少需要80 s；網絡規模為100 m×100 m，N＝100 時，完成一次充電周期的時間最多為230 s，最少為180 s；而當網絡規模為150 m×150 m，N＝150 時，完成一次充電周期的時間最少也需要600 s 左右，最多需要800 s 左右，說明此時單個MC 已經不能夠滿足此種網絡規模下的實時充電需求了，需要多個MC 才能完成充電任務。

圖7 網絡規模對調度時間的影響

圖8描述了網絡規模對MC 移動路徑長度的影響，網絡規模為50 m×50 m，N＝50 時，MC 具有最短的移動路徑，當網絡規模增大時，節點數量增多導致MC 要往返于更多的簇之間為更多節點充電，因此當網絡規模為150 m×150 m，N＝150 時，MC 每完成一個充電周期要移動8 000 m 左右的距離，顯然單個MC 已經不能滿足此種網絡規模下的需求了。

圖8 網絡規模對移動路徑長度的影響

4 結束語

在本文中，針對具有實時性要求的WRSNs 提出了一種基于非均勻分簇的實時充電算法(nUCRC)，創新之處在于采用非均勻分簇的方法，均衡了網絡中不同位置節點的充電機會，并采用動態規劃的方法找出MC 的最短移動路徑；在選擇簇內節點充電時，采取的是部分充的策略，有效減少了節點的充電等待時間；而在充電順序的選擇上，則采用了時空混合優先級的方法。 通過與最先進的兩種按需充電算法的對比，本文所提算法的節點存活率提升約10%、平均充電時延提升約20%。 另外還對不同網絡規模下nUCRC 算法的性能進行了分析，結果表明本文所提算法適用于小型WRSNs，下一步將對多個MC 協同工作展開研究。