張俊琪 樊軼鋮 劉彥松等

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

關(guān)鍵詞：物聯(lián)網(wǎng)；環(huán)境監(jiān)測；無線充電；充電調(diào)度

中圖法分類號：TP391 文獻標(biāo)識碼：A

１ 引言

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

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

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

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

２ 技術(shù)背景

物聯(lián)網(wǎng)網(wǎng)絡(luò)充電技術(shù)是隨著物聯(lián)網(wǎng)設(shè)備的發(fā)展而興起的一種技術(shù)，主要目的是應(yīng)對物聯(lián)網(wǎng)網(wǎng)絡(luò)中能量管理的挑戰(zhàn)。由于物聯(lián)網(wǎng)設(shè)備節(jié)點具有體積小和易碎性等特點，因此限制了物聯(lián)網(wǎng)網(wǎng)絡(luò)中能量消耗的有效性及其網(wǎng)絡(luò)壽命。因此，如何實現(xiàn)物聯(lián)網(wǎng)節(jié)點的能量管理并延長物聯(lián)網(wǎng)網(wǎng)絡(luò)的壽命成為提升物聯(lián)網(wǎng)網(wǎng)絡(luò)有效性的一項至關(guān)重要的任務(wù)。

相關(guān)研究建議通過讓物聯(lián)網(wǎng)設(shè)備從周圍環(huán)境中收集能量來延長節(jié)點壽命，如太陽能、風(fēng)能等［１～２］ 。

然而，由于周圍環(huán)境的動態(tài)變化，物聯(lián)網(wǎng)設(shè)備的能量收集率低且不穩(wěn)定。例如，相關(guān)研究表明，太陽能收集系統(tǒng)在晴天、陰天和雨天的能量產(chǎn)生率可能相差多達３ 個數(shù)量級［３］ 。這種不可推斷性和間斷性對有效利用收集的能量進行各種監(jiān)測任務(wù)提出了挑戰(zhàn)。

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

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

３ 模型及問題定義

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

３．１ 網(wǎng)絡(luò)模型

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

３．２ 無線充電模型

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

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

５ 實驗

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

由于本文研究的問題是在物聯(lián)網(wǎng)網(wǎng)絡(luò)中部署最小數(shù)量滿足充電時間不超過最大充電時間的充電小車為物聯(lián)網(wǎng)網(wǎng)絡(luò)充電，因此需要部署充電小車的數(shù)量是評估本文算法的重要指標(biāo)。

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

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

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

另外，隨著物聯(lián)網(wǎng)中物聯(lián)網(wǎng)設(shè)備數(shù)量的增多，２ 種算法得到的需部署的充電小車的數(shù)量也在增加，這是因為需要部署更多數(shù)量的充電小車才能維持更大規(guī)模聯(lián)網(wǎng)網(wǎng)絡(luò)的正常工作。

６ 結(jié)束語

部署移動充電小車為物聯(lián)網(wǎng)網(wǎng)絡(luò)中的設(shè)備進行無線充電已經(jīng)是一種通用方法，優(yōu)秀的充電調(diào)度算法不斷產(chǎn)生，能夠更加高效地為更多物聯(lián)網(wǎng)設(shè)備進行合理充電，降低充電成本。

（１）本文研究的物聯(lián)網(wǎng)網(wǎng)絡(luò)部署在２Ｄ 平面上，可進一步研究在３Ｄ 空間物聯(lián)網(wǎng)網(wǎng)絡(luò)中的充電車最小數(shù)量部署問題。

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

（ ３）本文僅僅考慮了一個基站的情況，在具體的應(yīng)用場景中，出發(fā)點可能不唯一，因此可進一步考慮多基站條件下的物聯(lián)網(wǎng)無線充電調(diào)度問題。

（４）本文所探究的物聯(lián)網(wǎng)網(wǎng)絡(luò)中所有節(jié)點位置中的電量都是已知的，可進一步研究節(jié)點信息是未知的情況。

參考文獻：

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

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

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

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

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

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

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

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

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

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