無線可充電傳感器網絡充電調度算法研究

鄭 翔，孫 霞，許彤彤

(1.安徽理工大學，安徽 淮南 232001；2.阜陽師范大學，安徽 阜陽 236037)

0 引言

隨著物聯網技術的不斷發展，為了保證無線傳感器網絡的工作性能,人們加大了對節點供電的研究力度［1］。文獻［2-4］從無線傳感器網絡自身入手，探究了無線傳感器網絡節點最佳部署方式和最優能量供應方式，但沒有對充電過程做出進一步闡釋。文獻［5］研究了無線可充電傳感器網絡中節點能量消耗問題，提出了不同的避免節點發生故障的充電方案。但從其結果上來看，并沒有將節點故障率降至最低。因為在普通的TSP 模型中，無線充電能力沒有得到充分利用。文獻［6-7］重點探究了無線傳感器網絡中的移動充電設備路徑規劃問題，從而降低移動充電器的移動時延。但其僅僅探究了移動充電設備的行駛路徑，并沒有對其他調度細節做出規劃和設計。當一個無線傳感器網絡節點數較多時，若只部署一個移動充電設備很難完成系統的充電要求。文獻［8-9］研究了多個移動充電設備協同為無線傳感器網絡充電的合理調度問題，但其并沒有平衡移動充電設備數與無線傳感器網絡規模的關系。

本文深入研究了移動充電設備數與節點數之間的關系，并且通過實驗方式實證研究了發送充電請求的能量閾值大小，在python 軟件上驗證該算法。不難看出，此充電系統具有較高的穩定性和較長的網絡生存周期，對于當前無線傳感器網絡的充電方式具有借鑒意義和應用價值。

1 網絡模型

本文提出一種多移動充電設備（Multi-mobile charging device）通過無線充電技術為無線傳感器網絡補充能量的網絡模型。在網絡中心處安置一個維護站，作為MCD完成一次充電調度后的停留地與能量補充點。在一次充電調度中，每個MCD都會為一部分傳感器節點充電，當MCD完成一次充電調度返回維護站時即開始準備下一輪充電調度，這時能量達到警戒閾值的傳感器節點就會向基站發送充電請求，基站發送指令給MCD、MCD 遍歷這些傳感器節點為其充電。假設一次充電調度為Πmpl,i，m為充電調度的輪數，l為MCD 的序號，i為被遍歷的傳感器節點序號。MCD 給一個傳感器節點充電完成后，在其駛向下一個傳感器節點的過程中可以選擇其他沒有發送充電請求但是能量不是很充足的傳感器節點進行充電。圖1為網絡模型圖。

圖1 網絡模型圖

1.1 無線充電模型

MCD 在給傳感器節點充電的過程中遵循（1）式所示模型［10］。

圖2 電氣連接圖

1.2 充電調度

MCD 在一定時間內從維護站出發完成一輪充電調度回到維護站的過程稱為一個充電調度周期。在此期間，MCD 和節點的剩余能量都不得低于某一特定的值。一次充電調度完成到下一次充電調度開始的時間間隔稱為調度間隔［12］。

1.3 傳感器節點與MCD的能量限制

為了保證無線傳感器網絡穩定，必須使傳感器節點是有能量的。若傳感器節點的能量低于閾值Emin，節點即將死亡，因此必須保證傳感器節點能量時刻不低于Emin。（2）式為傳感器節點的能量約束式。MCD 完成一次充電調度需攜帶的能量如（3）式所示，其儲存的能量主要用于MCD在傳感器節點間的行駛和給傳感器節點充電。Em(i)為第m次充電調度開始時傳感器節點i剩余能量，pi為傳感器節點的能量消耗功率，pw為MCD 的移動功率，L為哈密頓環的長度，N為在一次充電調度中遍歷的傳感器節點數，τm(i)為在第m次充電調度中移動充電設備給第i個傳感器節點充電的時間。

2 MMCD優化調度算法

2.1 為無線傳感器網絡分配MCD

在一個較大的無線傳感器網絡中，若只用單個MCD，很難滿足系統的充電需求，并且在此唯一的MCD 發生故障時，無線傳感器網絡得不到及時的能量補充，系統就會崩潰。因此考慮采用MMCD 優化調度算法為無線傳感器網絡充電。但并不意味著MCD 越多越好，設備數過多時會增加不必要的成本，設備數不夠時又不能滿足充電需求。本算法旨在找出滿足系統穩定性的前提下最少的MCD 數。現以一個較大規模無線可充電傳感器網絡為例，假定在一次充電調度中所有節點都需要充電，這時為其調配p個MCD。大的無線傳感器網絡被分成了p個小網，給前p-1 個MCD 分配相同數量的節點，并將剩余節點分配給最后一個MCD，這是為了保證每個MCD 的充電負荷大致相同。因為前p-1 個網具有相同節點數，這里首先確定訪問點順序，然后建立哈密頓環需要強調的是，當MCD運動到哈密頓環中的最后一個節點時，節點剩余能量必須不低于Emin。以此得出關系式（9），該算法涉及到的參數及其含義如表1所示。

表1 算法中涉及的參數及其含義

在第m 次充電調度中，任意一個傳感器節點將剩余能量用至最低所需要的時間，如（4）式所示。

只需知道MCD到達一個傳感器節點的時間，給其充電的時間和向下一個傳感器節點行駛的時間，就可以推算出到達下一個傳感器節點的時間，如（5）式所示。

某一個MCD在其充電調度中，到達哈密頓環中最后一個傳感器節點的時間不得大于最后一個節點能量用盡的時間，如（6）式所示。

以哈密頓環中第一個傳感器節點為例，MCD 從基站行駛到第一個傳感器節點的時間即為到達該傳感器節點的時間，如（7）式所示。

MCD 在哈密頓環中第一個傳感器節點停留的時間即為為其充電的時間，如（8）式所示。

在哈密頓環中，傳感器節點數需與MCD數滿足如（9）式所示的不等關系。

2.2 無線傳感器網絡中充電節點分類

在無線傳感器網絡中存在三種類型的節點：第一類是能量達到預先設定閾值的節點，其剩余能量已經不足以支撐一個完整的充電調度周期，必須為其充電；第二類是能量不夠充足，最好適當給其補充一部分能量；第三類是能量很充足的節點，在當次充電調度中不必為其充電。我們首先要確定將傳感器電池還剩多少能量定為向基站發送充電請求的閾值能量。每一個節點都必須滿足：當節點能量達到閾值預警時，MCD 必須已經到達該節點，并對該節點進行充電。即滿足（10）關系式，此時的警戒閾值稱為第一警戒閾值。

除此之外，還有一種節點也是必須充電的節點，雖然在當次充電調度中這些節點的能量足以支撐到此次充電調度結束，但是在下一次充電調度中，MCD 到來之前，這些節點能量已經耗盡，所以此類節點在當次充電調度中也是必須充電的節點。此類節點滿足的關系式如（11）式所示。這些節點滿足的警戒閾值為第二警戒閾值。式（12）為一個充電調度周期總時間的計算式。

3 仿真實驗與結果分析

3.1 仿真環境與參數設置

實驗采用軟件python3.6 進行仿真和調試，計算機 配 置 為Intel（R）Core（TM）i3 - 4130 CPU@3.40GHz，4.00 GB RAM。100 個節點隨機分布在100m×100m 被監測區域內，基站和維護站均位于（50，50）處。網絡模型如圖3所示。

圖3 網絡模型

實驗參數設置如下：節點電池容量Es=50J，節點能量最低閾值Emin=5J，MCD 運行速度v=0.5m/s，MCD 移動功率pw=6J/m，無線充電線圈發射功率pr=8J/s，節點最小能量消耗功率pimin=0.005J/s。節點最大能量消耗功率pimax=0.015J/s，充電效率η=0.5。

3.2 節點數與充電能量閾值的關系

無線傳感器網絡的節點數與充電能量閾值之間存在一定的關系。當一個MCD 負責充電的節點數變化時，第一警戒閾值和第二警戒閾值會隨之發生變化。

圖4 能量閾值q和q’的變化情況

從仿真結果可以看出，無線傳感器網絡的節點數和充電能量閾值關系如圖4所示。圖中的上面一條線代表第二充電閾值q’隨著網絡規模大小變化時的變化情況，而下面的線代表第一充電閾值q隨著網絡規模大小變化時的變化情況。可以看出隨著無線傳感器網絡規模的增大q’是穩定在q的上方的，這和預期的結果是相同的，可以根據此結果確定發出充電請求的能量閾值。

3.3 網絡規模與充電設備數量的關系

網絡規模和最優移動充電設備數之間的關系，仿真結果如圖5所示。

圖5 網絡規模和最優移動充電設備數之間的關系

根據算法得出網絡規模和最優MCD 數之間的關系，不難發現，從本實驗采用的100個節點的網絡規模來看，最優的MCD數是3個。

圖6 網絡性能測試圖

圖6 是網絡性能測試圖，通過將本文中的MMCD 算法與已有的EDF 算法作對比，不難看出，隨著系統運行時間的增加，無線傳感器網絡中節點存活率更高，存活率高則說明算法更優。從仿真結果可以看出，本文算法和已有算法相比，在提高網絡壽命方面明顯更優。

4 結論

針對當前大規模無線可充電傳感器網絡能量供應方式的不足，綜合考慮了MCD數量和最低充電能量閾值的影響，研究如何調度最少的MCD來給具有生命周期的傳感器節點高效充電的問題。本文提出一種新的近似算法，通過仿真實驗得出結論，不僅證明了該算法具有較好的性能，而且對算法涉及到的核心參數進行了研究。與現有算法相比，本算法具有較長的網絡壽命。