尹 玲謝志軍陳科偉

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

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

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

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

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

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

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

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

1 網(wǎng)絡(luò)模型

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

1.1 問題描述

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

圖1 采用nUCRC 算法的WRSNs 模型

1.2 解決方案

為解決上述問題，本文設(shè)計(jì)的目標(biāo)是在單個充電周期T內(nèi)，MC 的移動路徑最短、節(jié)點(diǎn)存活率δ最高:

式中:d(i，V)表示MC 移動總路徑，Nlive是存活節(jié)點(diǎn)數(shù)，N為節(jié)點(diǎn)總數(shù)。

考慮到MC 攜帶的能量要大于為節(jié)點(diǎn)充電耗費(fèi)的能量，并在一個充電周期T內(nèi)完成為節(jié)點(diǎn)充電和返回BS 處進(jìn)行充電維護(hù)，有如下能量約束和時間約束:

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

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

2 非均勻分簇的實(shí)時充電算法

nUCRC 算法分為兩步實(shí)現(xiàn)以上目標(biāo):非均勻分簇和充電路徑規(guī)劃。

2.1 非均勻分簇

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

2.1.1 簇半徑的計(jì)算

網(wǎng)絡(luò)運(yùn)行初期，N個節(jié)點(diǎn)分別計(jì)算其到BS 的歐式距離di:

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

式中:ε表示預(yù)期的最小簇半徑與最大簇半徑的比值，當(dāng)ε＝0 時表示此時網(wǎng)絡(luò)采用均勻分簇，取ε＝0.5；dmax是節(jié)點(diǎn)距離BS 的最大值；dmin是節(jié)點(diǎn)距離BS 的最小值；R0表示候選簇頭節(jié)點(diǎn)最小簇半徑值。

2.1.2 簇頭節(jié)點(diǎn)的選舉

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

①當(dāng)前剩余能量ei最高；

②截止充電時間Di最大:

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

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

首輪K個簇頭節(jié)點(diǎn)選舉出后，每個簇頭節(jié)點(diǎn)需要維護(hù)一個簇內(nèi)節(jié)點(diǎn)的集合:

圖2 非均勻分簇流程圖

2.2 MC 充電路徑規(guī)劃

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

2.2.1 簇間移動路徑規(guī)劃

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

根據(jù)2.1 節(jié)中構(gòu)建的簇，計(jì)算每個簇的簇中心

式中:｜Ck｜表示簇Ck內(nèi)含有的節(jié)點(diǎn)數(shù)，dCsk-1，Csk表示任意兩個簇中心的歐式距離，V表示簇中心的集合:

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

上式表示當(dāng)集合V為空時，di，BS表示直接返回BS，而當(dāng)V不為空時，整體路徑最短問題就轉(zhuǎn)換為部分路徑最短問題的最優(yōu)求解。

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

MC 在移動過程中靠近BS 時，會返回BS 進(jìn)行充電維護(hù)，維護(hù)完畢會按既定路線繼續(xù)完成充電任務(wù)，當(dāng)遍歷所有簇后返回BS 處，完成一次充電周期。

2.2.2 簇內(nèi)節(jié)點(diǎn)充電順序選擇

當(dāng)MC 移動到簇Ck的中心時，選取簇內(nèi)能量低于電池容量50%的節(jié)點(diǎn)進(jìn)行充電，避免了全充造成較大的充電時延。 無線能量傳輸采用改進(jìn)的適用于WRSNs 的Friis 能量傳輸模型[14]:

式中:PC是簇中節(jié)點(diǎn)從MC 接收能量的功率，P0是MC 的發(fā)射功率；Gs和Gr分別是MC 的發(fā)射天線增益和節(jié)點(diǎn)的接收天線增益；η是整流器的效率；λ表示波長；d是MC 與被充電節(jié)點(diǎn)的充電距離；Lp表示極化損耗；γ是調(diào)整Frris 自由空間方程用于短距離傳輸?shù)膮?shù)。

給單個節(jié)點(diǎn)Si的充電持續(xù)時間TC(Si)由節(jié)點(diǎn)當(dāng)前剩余能量ei、節(jié)點(diǎn)電池總?cè)萘縀N以及能量傳輸模型(12)共同決定:

MC 給節(jié)點(diǎn)Si充電耗費(fèi)的能量則由充電時間和充電耗能共同決定:

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

定義簇頭節(jié)點(diǎn)SCkH的截止充電時間為DCkH，最小的節(jié)點(diǎn)截止充電時間為，最大的節(jié)點(diǎn)截止充電時間為，得到時間優(yōu)先級為:

同樣定義dCkH是簇頭節(jié)點(diǎn)到MC 的距離，距離MC 最近的節(jié)點(diǎn)的距離為，距離MC 最遠(yuǎn)的節(jié)點(diǎn)的距離為，得到空間優(yōu)先級為:

將時間優(yōu)先級和空間優(yōu)先級結(jié)合得到混合優(yōu)先級如下:

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

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

圖3 MC 根據(jù)優(yōu)先級按序?yàn)榇貎?nèi)節(jié)點(diǎn)充電

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

圖4 nUCRC 算法工作流程圖

3 實(shí)驗(yàn)仿真與結(jié)果分析

3.1 參數(shù)設(shè)置

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

表1 實(shí)驗(yàn)參數(shù)設(shè)置

實(shí)驗(yàn)分別將本文所提nUCRC 算法與文獻(xiàn)[8]所提的GSA 算法以及文獻(xiàn)[10]提出的MTC 算法作性能對比，分別從節(jié)點(diǎn)存活率和平均充電時延方面進(jìn)行了對比分析，同時還研究了網(wǎng)絡(luò)規(guī)模對nUCRC算法性能的影響。

3.2 仿真結(jié)果分析

3.2.1 節(jié)點(diǎn)存活率對比

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

圖5 節(jié)點(diǎn)存活率對比

3.2.2 平均充電時延對比

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

圖6 平均充電時延對比

3.2.3 網(wǎng)絡(luò)規(guī)模的影響

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

圖7 網(wǎng)絡(luò)規(guī)模對調(diào)度時間的影響

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

圖8 網(wǎng)絡(luò)規(guī)模對移動路徑長度的影響

4 結(jié)束語

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