物聯網充電調度算法研究

張俊琪 樊軼鋮 劉彥松等

摘要：近年來，物聯網技術飛速發展．物聯網被廣泛應用于環境監測、三維建模、智慧城市、目標跟蹤、數據收集等場景中。在物聯網的應用場景中，物聯網設備的電量一直是人們關注的焦點。通常情況下．物聯網設備的電量若得不到及時補充．將很快失去工作能力。比如，在檢測火災的森林場景中．如果物聯網失去工作能力，后果將不堪設想。在傳統的物聯網網絡中，通常為物聯網設備安裝太陽能充電電池來保證物聯網設備持續工作，但是此方法受天氣和時間的影響，物聯網設備往往不能獲得足夠的陽光，從而導致電量補充不足的問題。因此，采用移動迅速的無線充電小車為物聯網設備補充電量是一種理想的方式。文章闡述了在單基站場景中部署最小數量的無線充電小車并提出它們充電路徑的問題。同時，在考慮了無線充電范圍（即鄰域）的情況下，提出了算法approAlgOncSinkNci。實驗表明，對比不考慮鄰域的算法approAlgOncSinkNoNci，該算法所得到的充電小車數量大大減少。

關鍵詞：物聯網；環境監測；無線充電；充電調度

中圖法分類號：TP391 文獻標識碼：A

１ 引言

物聯網（Ｉｎｔｅｒｎｅｔ ｏｆ Ｔｈｉｎｇｓ，ＩｏＴ）是指將各種設備、服務、應用通過網絡連接和交互。它實現了各種設備（如手機、車輛、傳感器等）之間無縫互聯，使不同類型的設備能夠相互通信，彼此傳遞數據。物聯網讓更多的傳感器設備、系統和應用通過互聯網連接在一起，從而實現智能家居、智能交通系統等，進而提高生活和工作的效率，為人們提供更加個性化的服務。如今，物聯網被應用于環境監測、三維建模、智慧城市、目標跟蹤、數據收集等場景中，因此如何持續保證物聯網的正常工作是一個至關重要的問題。

針對物聯網網絡中的無線充電問題（如應用在一個具體監測場景中的物聯網網絡），為了使物聯網網絡中的節點隨時保持足夠的電量正常工作，需要采取高效的方式為物聯網網絡進行充電。基于此，可以考慮部署多個輕量的無線充電小車為物聯網中的設備進行充電，每一個無線充電小車都可以停在離物聯網設備較近的某個位置進行無線充電，從而保證物聯網網絡持續工作。

為了確保充電的高效性，規定每一個充電小車在充電途中所消耗的總時間不超過給定的最大充電時間，其中總時間包括充電小車的移動時間和充電時間。否則，不能保證所有的物聯網設備都能得到及時充電。

本文研究了一個新穎的有鄰域情況下單基站充電車最小數量部署問題，即確定最小數量的無線充電小車為物聯網網絡充電，其中充電小車在距離物聯網設備一定范圍就可以進行無線充電，同時確定每一個充電小車的充電路徑，并保證每個充電小車所消耗的總時間不超過最大充電時間，每一個充電小車均從基站出發，最后再回到基站，而且每一個物聯網設備都必須被其中一個無線充電小車所充電。為了解決此問題，本文首先提出網絡模型和無線充電模型；其次定義有鄰域情況下單基站充電車最小數量部署問題；再次提出算法；最后通過在多個模擬數據集上進行仿真實驗，并且與已有的算法進行比較，以評估本文算法的性能。

２ 技術背景

物聯網網絡充電技術是隨著物聯網設備的發展而興起的一種技術，主要目的是應對物聯網網絡中能量管理的挑戰。由于物聯網設備節點具有體積小和易碎性等特點，因此限制了物聯網網絡中能量消耗的有效性及其網絡壽命。因此，如何實現物聯網節點的能量管理并延長物聯網網絡的壽命成為提升物聯網網絡有效性的一項至關重要的任務。

相關研究建議通過讓物聯網設備從周圍環境中收集能量來延長節點壽命，如太陽能、風能等［１～２］ 。

然而，由于周圍環境的動態變化，物聯網設備的能量收集率低且不穩定。例如，相關研究表明，太陽能收集系統在晴天、陰天和雨天的能量產生率可能相差多達３ 個數量級［３］ 。這種不可推斷性和間斷性對有效利用收集的能量進行各種監測任務提出了挑戰。

有研究人員提出了一種創新性的物聯網設備電量補充方法［４～５］ ，即將配備具有無線充電功能的小車移動到電量即將耗盡的物聯網設備附近，并通過無線能量傳輸為其充電［６］ 。相較于物聯網設備從周圍采集能量的方式，該方法的充電效率高且穩定。

部分文獻研究了最小數量充電車部署問題，但是這些研究沒有考慮鄰域條件［７］ 。在實際應用場景中，無線充電小車往往不需要貼近物聯網設備就能進行充電。因此，本文考慮在有鄰域條件下部署最小數量的充電車為物聯網設備進行充電。

３ 模型及問題定義

在網絡模型中，本文給出了網絡中設備和基站的分布情況。在無線充電模型中，本文描述了無線充電小車如何對每一個物聯網設備進行充電，從而保證物聯網設備正常工作。在問題定義中，本文用數學語言定義了有鄰域情況下單基站充電車最小數量部署問題。

３．１ 網絡模型

考慮部署在一個具體真實環境中的物聯網網絡，即在一個區域中的重要興趣點部署物聯網設備，從而監測該興趣點周圍的環境數據。例如，物聯網設備可用于監測環境中的輻射劑量，或者監測環境的溫度和濕度。假設在指定監測區域中有一個基站ｓ，所有充電小車均從此基站出發。同時，部署ｍ 個物聯網設備ｖ１，ｖ２，…，ｖｍ ，其中ｍ∈Ｎ?。設Ｖ 為ｍ 個物聯網設備所構成的集合，即Ｖ ＝｛ｖ１，ｖ２，…，ｖｍ ｝。設備ｖｉ 的坐標為（ｘｉ ，ｙｉ ），其中１≤ｉ≤ｍ。任意２ 個物聯網設備節點ｖｉ 和ｖｊ 之間存在１ 條邊（ｖｉ ，ｖｊ ），其中１≤ｉ≤ｍ，１≤ｊ≤ｍ 且ｉ≠ｊ，設Ｅ 表為所有的邊所構成的集合。因此，此物聯網可表示為Ｇ ＝（Ｖ∪｛ｓ｝，Ｅ）。

３．２ 無線充電模型

假設共部署Ｋ 個移動充電小車為ｍ 個物聯網設備充電，其中Ｋ 的值是未知的且滿足Ｋ∈Ｎ?。將集合Ｖ 劃分成Ｋ 個不相交的子集Ｖ１，Ｖ２，…，ＶＫ ，其中充電小車ｋ 為子集Ｖｋ 中的物聯網設備充電，則１≤ｋ≤Ｋ。令Ｖｋ ＝｛ｖ１，ｖ２，…，ｖｎｋ ｝，其中ｎｋ ＝ ｜Ｖｋ ｜。用ｅｉ 表示集合Ｖ 中設備ｖｉ 充滿電所需的電量。假設每一個充電小車的充電速率均為ｐ，充電效率為α，且充電小車擁有足夠電量，其中０＜α＜１。對于設備ｖｉ ，共需花費時間ｔ（ｖｉ ）＝ ｅｉαｐ即可充滿電量。最后，令λ 表示充電小車的移動速度。

假設充電小車距離任意一個物聯網設備不超過無線充電半徑Ｒ 即可進行無線充電。令Ｄ（ｖｉ ）表示充電小車可以為設備ｖｉ 充電的所有位置集合，則Ｄ（ｖｉ ）＝ ｛（ｘ，ｙ） ｜（ｘ－ｘｉ ）２ ＋（ｙ－ｙｉ ）２ ≤Ｒ２｝，其中（ｘｉ ，ｙｉ ）是設備ｖｉ 的坐標。設充電小車ｋ 以ｖ１，ｖ２，…，ｖｎｋ的順序為集合Ｖｋ 中的設備充電，其中１≤ｋ≤Ｋ。充電小車ｋ 進行充電的移動路徑Ｔｋ 定義如下。充電小車ｋ 從基站ｓ 出發，在集合Ｄ（ｖ１ ）中的位置ｌ１ 為設備ｖ１ 充電，接著充電小車前往集合Ｄ（ｖ２）中的位置ｌ２ 為設備ｖ２ 充電，以此類推，直到在集合Ｄ（ｖｎｋ ）中的位置ｌｎｋ為最后一個設備ｖｎｋ充滿電，充電小車此時返回基站ｓ 完成一個充電周期。充電小車ｋ 的充電路徑是一個閉合回路Ｔｋ ＝ｓ→ｌ１→ｌ２→…→ｌｎｋ→ｓ，其中ｌｉ 是充電小車在集合Ｄ（ｖｉ ）對設備ｖｉ 進行無線充電的停靠點，并且１≤ｋ≤Ｋ，ｖｎｋ是集合Ｖｋ 中設備的個數。

５ 實驗

本節針對有鄰域情況下單基站充電車最小數量部署問題所提出的算法ａｐｐｒｏＡｌｇＯｎｅＳｉｎｋＮｅｉ 進行了實驗驗證，并且本文算法ａｐｐｒｏＡｌｇＯｎｅＳｉｎｋＮｅｉ 和不考慮鄰域的算法ａｐｐｒｏＡｌｇＯｎｅＳｉｎｋＮｏＮｅｉ 進行了對比分析，以評估算法性能。

由于本文研究的問題是在物聯網網絡中部署最小數量滿足充電時間不超過最大充電時間的充電小車為物聯網網絡充電，因此需要部署充電小車的數量是評估本文算法的重要指標。

本文采用的模擬實驗使用Ｐｙｔｈｏｎ 語言，并且在１臺配置為Ｉｎｔｅｒ（Ｒ） Ｃｏｒｅ（ＴＭ） ｉ７ ＣＰＵ （２．６ ＧＨｚ）和３２ＧＢ ＲＡＭ 的服務器上運行。所有數據都是在相同網絡規模的５００ 中不同的網絡拓撲結構中運行每個算法所得到結果的平均值。

為了評估有鄰域情況下單基站充電車最小數量部署問題所提出的算法ａｐｐｒｏＡｌｇＯｎｅＳｉｎｋＮｅｉ，考慮另一個針對無鄰域情況下單基站充電車最小數量部署問題提出的算法ａｐｐｒｏＡｌｇＯｎｅＳｉｎｋＮｏＮｅｉ。本文相關數據參考文獻［９］ 。

從圖１ 可以看出，在物聯網設備數量相同的條件下，算法ａｐｐｒｏＡｌｇＯｎｅＳｉｎｋＮｅｉ 得到的充電小車數量大大小于算法ａｐｐｒｏＡｌｇＯｎｅＳｉｎｋＮｏＮｅｉ 得到的充電小車數量。由于考慮了充電鄰域，因此充電小車并不需要前往每一個物聯網設備的位置即可進行充電，甚至可以在同一位置為多個物聯網設備進行充電。這可以大大減少每一個充電小車充電路徑的長度，從而在每一個最大充電時間內可以為更多的物聯網設備進行充電，因此可以減少充電小車的部署數量。

另外，隨著物聯網中物聯網設備數量的增多，２ 種算法得到的需部署的充電小車的數量也在增加，這是因為需要部署更多數量的充電小車才能維持更大規模聯網網絡的正常工作。

６ 結束語

部署移動充電小車為物聯網網絡中的設備進行無線充電已經是一種通用方法，優秀的充電調度算法不斷產生，能夠更加高效地為更多物聯網設備進行合理充電，降低充電成本。

（１）本文研究的物聯網網絡部署在２Ｄ 平面上，可進一步研究在３Ｄ 空間物聯網網絡中的充電車最小數量部署問題。

（２）在本文研究的基礎上，可以考慮充電小車自身電量有限的情況。在這種情況下，需要更加嚴格規劃小車的路徑，使小車在能量耗盡前返回基站補充電量。

（ ３）本文僅僅考慮了一個基站的情況，在具體的應用場景中，出發點可能不唯一，因此可進一步考慮多基站條件下的物聯網無線充電調度問題。

（４）本文所探究的物聯網網絡中所有節點位置中的電量都是已知的，可進一步研究節點信息是未知的情況。

參考文獻：

［１］ ＶＯＩＧＴ Ｔ，ＲＩＴＴＥＲ Ｈ，ＳＣＨＩＬＬＥＲ Ｊ．Ｕｔｉｌｉｚｉｎｇ ｓｏｌａｒ ｐｏｗｅｒ ｉｎｗｉｒｅｌｅｓｓ ｓｅｎｓｏｒ ｎｅｔｗｏｒｋｓ ［ Ｃ］ ∥ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ２８ｔｈＡｎｎｕａｌ ＩＥＥＥ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｌｏｃａｌ ＣｏｍｐｕｔｅｒＮｅｔｗｏｒｋｓ，２００３：４１６ – ４２２．

［２］ ＷＡＮＧ Ｃ， ＧＵＯ Ｓ， ＹＡＮＧ Ｙ． Ｅｎｅｒｇｙ?ｅｆｆｉｃｉｅｎｔ ｍｏｂｉｌｅ ｄａｔａｃｏｌｌｅｃｔｉｏｎ ｉｎ ｅｎｅｒｇｙ?ｈａｒｖｅｓｔｉｎｇ ｗｉｒｅｌｅｓｓ ｓｅｎｓｏｒ ｎｅｔｗｏｒｋｓ［Ｃ］∥Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ２０ｔｈ ＩＥＥＥ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎＰａｒａｌｌｅｌ ａｎｄ Ｄｉｓｔｒｉｂｕｔｅｄ Ｓｙｓｔｅｍｓ （ＩＣＰＡＤＳ），２０１４：５５ – ６２．

［３］ ＲＡＨＩＭＩ Ｍ，ＳＨＡＨ Ｈ，ＳＵＫＨＡＴＭＥ Ｇ，ｅｔ ａｌ． Ｓｔｕｄｙｉｎｇ ｔｈｅｆｅａｓｉｂｉｌｉｔｙ ｏｆ ｅｎｅｒｇｙ ｈａｒｖｅｓｔｉｎｇ ｉｎ ａ ｍｏｂｉｌｅ ｓｅｎｓｏｒ ｎｅｔｗｏｒｋ［Ｃ］∥Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ２００３ ＩＥＥＥ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎＲｏｂｏｔｉｃｓ ａｎｄ Ａｕｔｏｍａｔｉｏｎ，２００３：１９ – ２４．

［４］ ＷＡＮＧ Ｃ，ＬＩ Ｊ，ＹＥ Ｆ，ｅｔ ａｌ．Ｉｍｐｒｏｖｅ ｃｈａｒｇｉｎｇ ｃａｐａｂｉｌｉｔｙ ｆｏｒｗｉｒｅｌｅｓｓ ｒｅｃｈａｒｇｅａｂｌｅ ｓｅｎｓｏｒ ｎｅｔｗｏｒｋｓ ｕｓｉｎｇ ｒｅｓｏｎａｎｔ ｒｅｐｅａｔｅｒｓ［Ｃ］∥Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ＩＥＥＥ ３５ｔｈ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅｏｎ Ｄｉｓｔｒｉｂｕｔｅｄ Ｃｏｍｐｕｔｉｎｇ Ｓｙｓｔｅｍｓ，２０１５：１３３ – １４２．

［５］ ＸＩＥ Ｌ，ＳＨＩ Ｙ， ＨＯＵ Ｙ Ｔ， ｅｔ ａｌ． Ｍａｋｉｎｇ Ｓｅｎｓｏｒ ＮｅｔｗｏｒｋｓＩｍｍｏｒｔａｌ：Ａｎ Ｅｎｅｒｇｙ?Ｒｅｎｅｗａｌ Ａｐｐｒｏａｃｈ Ｗｉｔｈ Ｗｉｒｅｌｅｓｓ ＰｏｗｅｒＴｒａｎｓｆｅｒ［Ｊ］∥ＩＥＥＥ／ ＡＣＭ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｎｅｔｗｏｒｋｉｎｇ，２０１２，２０（６）：１７４８?１７６１．

［６］ 劉亮，蒲浩洋．大規模無線傳感器網絡中高效按需充電規劃［Ｊ］．計算機應用研究，２０２２，３９（１）：２３１?２３５．

［７］ ＺＨＡＮＧ Ｑ， ＸＵ Ｗ，ＬＩＡＮＧ Ｗ，ｅｔ ａｌ．Ａｎ ｉｍｐｒｏｖｅｄ ａｌｇｏｒｉｔｈｍｆｏｒ ｄｉｓｐａｔｃｈｉｎｇ ｔｈｅ ｍｉｎｉｍｕｍ ｎｕｍｂｅｒ ｏｆ ｅｌｅｃｔｒｉｃ ｃｈａｒｇｉｎｇｖｅｈｉｃｌｅｓ ｆｏｒ ｗｉｒｅｌｅｓｓ ｓｅｎｓｏｒ ｎｅｔｗｏｒｋｓ ［ Ｊ ］ ∥ ＷｉｒｅｌｅｓｓＮｅｔｗｏｒｋｓ，２０１８：１?１４．

［８］ ＤＵＭＩＴＲＥＳＣＵ Ａ，Ｔ?ＴＨ Ｃ Ｄ．Ｔｈｅ ｔｒａｖｅｌｉｎｇ ｓａｌｅｓｍａｎ ｐｒｏｂｌｅｍｆｏｒ ｌｉｎｅｓ， ｂａｌｌｓ， ａｎｄ ｐｌａｎｅｓ ［ Ｊ ］． ＡＣＭ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎＡｌｇｏｒｉｔｈｍｓ （ＴＡＬＧ），２０１６，１２（３）：１?２９．

［９］ ＺＨＡＮＧ Ｊ，ＬＩ Ｚ， ＸＵ Ｗ， ｅｔ ａｌ． Ｍｉｎｉｍｉｚｉｎｇ ｔｈｅ Ｎｕｍｂｅｒ ｏｆＤｅｐｌｏｙｅｄ ＵＡＶｓ ｆｏｒ Ｄｅｌａｙ?ｂｏｕｎｄｅｄ Ｄａｔａ Ｃｏｌｌｅｃｔｉｏｎ ｏｆ ＩｏＴＤｅｖｉｃｅｓ［Ｃ］ ∥ ＩＥＥＥ ＩＮＦＯＣＯＭ ２０２１?ＩＥＥＥ Ｃｏｎｆｅｒｅｎｃｅ ｏｎＣｏｍｐｕｔｅｒ Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ，２０２１：３３?４２．

作者簡介：張俊琪（１９９５—），碩士，助理工程師，研究方向：軟件開發與算法設計。