張俊琪

（四川大學(xué)計算機(jī)學(xué)院，成都610065）

0 引言

目前，物聯(lián)網(wǎng)技術(shù)已取得巨大發(fā)展。物聯(lián)網(wǎng)設(shè)備例如無線傳感器被廣泛應(yīng)用于智慧城市、智能交通、森林火災(zāi)檢測，軍用、民用領(lǐng)域的監(jiān)控等。其中，在智慧城市的應(yīng)用場景中，我們可以在城市的若干交通要道部署傳感器設(shè)備，這些傳感器設(shè)備可以實時監(jiān)控路段情況，并且分析數(shù)據(jù)，進(jìn)而可以規(guī)劃出合理的路徑從而避免交通事故。在森林火災(zāi)監(jiān)測的應(yīng)用場景中，我們可以在森林的關(guān)鍵位置部署若干傳感器，這些傳感器可以實時監(jiān)控森林關(guān)鍵點的溫度、濕度情況，一旦溫度和濕度達(dá)到臨界值，那么啟用報警處理，通知相關(guān)工作人員及時處理，避免森林大火。

在有一定規(guī)模的無線傳感器所構(gòu)成的網(wǎng)絡(luò)中，每一個傳感器采用電池供電的方式，由于傳感器電池容量有限，因此及時為傳感器進(jìn)行充電是傳感器網(wǎng)絡(luò)持續(xù)工作的重要措施。傳統(tǒng)的方法有兩種，第一是無線傳感器能夠采集周圍環(huán)境的能量，例如太陽能充電。但是此方法對周圍的環(huán)境有嚴(yán)格的要求，例如太陽光照強(qiáng)度在一天之內(nèi)早晚比較低，在雨天、陰天太陽光也比較少。因此，此方法采集到的能量很不穩(wěn)定。第二是部署一個或者多個移動充電設(shè)備去給無線傳感器網(wǎng)絡(luò)中節(jié)點充電[3]，此法能有效解決前者能量不穩(wěn)定且過度依賴環(huán)境的問題。

傳感器具有一定的儲存和計算能力，可以收集周圍環(huán)境一定范圍內(nèi)的數(shù)據(jù)，例如溫度、濕度、風(fēng)速、氣體含量、地表元素含量等。在傳統(tǒng)的無線傳感器網(wǎng)絡(luò)中，傳感器感知周圍環(huán)境的數(shù)據(jù)，并且采取“多跳”的方式，將數(shù)據(jù)不斷傳給下一跳傳感器，最終傳向基站，然后基站進(jìn)行后續(xù)的數(shù)據(jù)處理和分析。然而傳統(tǒng)的“多跳”的方式存在很大的缺點。一是處于不同位置的傳感器節(jié)點的數(shù)據(jù)轉(zhuǎn)發(fā)負(fù)載分布不均衡導(dǎo)致能量消耗不均衡。靠近基站的節(jié)點的轉(zhuǎn)發(fā)次數(shù)更加頻繁，往往會消耗更多的能量，這些節(jié)點也會更快的死亡，造成傳感器網(wǎng)不能正常工作。二是如果網(wǎng)絡(luò)規(guī)模比較大，邊緣傳感器所收集數(shù)據(jù)傳到基站所耗費的時間往往很大，不利于實時數(shù)據(jù)的監(jiān)控分析。

無人機(jī)具有廉價、低能耗、易部署的特點，因此，我們可以考慮將無人機(jī)應(yīng)用于無線傳感器網(wǎng)絡(luò)的工作中。無人機(jī)主要應(yīng)用于運輸物品、目標(biāo)跟蹤、數(shù)據(jù)收集，以及無線充電[1-2]。

近年來，為了解決傳統(tǒng)傳感器網(wǎng)絡(luò)中存在的問題，現(xiàn)階段有采取移動基站去收集傳感器網(wǎng)絡(luò)數(shù)據(jù)的方式。但是，可移動基站往往只能在地面上移動，無法規(guī)避地面上的障礙物如河流、山川、懸崖等。也有一些工作采取部署單無人機(jī)去收集傳感器網(wǎng)絡(luò)的數(shù)據(jù)，但是一個無人機(jī)很難應(yīng)對大型傳感器網(wǎng)絡(luò)。

本文采取部署多無人機(jī)的方式去收集無線傳感器網(wǎng)絡(luò)的數(shù)據(jù)。本文涉及到兩種場景，第一種是無鄰域的場景，就是無人機(jī)必須靠近每一個無線傳感器才能接收到數(shù)據(jù)；另一種場景是有鄰域的情況，就是無人機(jī)只需要落入距離以無線傳感器為中心，一定距離為半徑的圓形鄰域內(nèi)，即可收集到傳感器的數(shù)據(jù)。其中第一種場景適用于打卡式傳感器，即無人機(jī)攜帶的ID 卡必須接觸無線傳感器的讀卡器，才能進(jìn)行數(shù)據(jù)傳輸。第二種情況適用于無人機(jī)或者傳感器可以利用信道進(jìn)行數(shù)據(jù)傳輸，無人機(jī)只需要在距離無線傳感器一定距離范圍內(nèi)即可完成數(shù)據(jù)傳輸。為了保證數(shù)據(jù)的實時性以及考慮滿足無人機(jī)最大飛行時間的要求，我們部署的每一個無人機(jī)的總飛行時間不得超過一個規(guī)定的時間。

在如下場景中，見圖1，部署了兩架無人機(jī)搜集一定范圍內(nèi)的無線傳感器的數(shù)據(jù)。由于無人機(jī)覆蓋范圍比較大，因此在考慮鄰域的情況下，可以同時收集一定范圍內(nèi)的傳感器數(shù)據(jù)。

圖1

下面對比有鄰域和無鄰域兩種情況下無人機(jī)收集傳感器網(wǎng)絡(luò)數(shù)據(jù)，見圖2。由此可以看出，在考慮有鄰域時，無人機(jī)不需要靠近傳感器（傳感器B）就可以收集到傳感器數(shù)據(jù)，因此相比傳感器A，無人機(jī)飛行距離大大降低，可以節(jié)約更多的時間從而收集其他更多無線傳感器節(jié)點的數(shù)據(jù)。

圖2

1 預(yù)備知識

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

考慮在一個傳感網(wǎng)絡(luò)中，有ns數(shù)量的傳感器，以及基站r，隨機(jī)均勻分布在網(wǎng)絡(luò)中。將傳感器網(wǎng)絡(luò)簡化為一個無向圖G=(Vs∪{r},Es)，Vs∪{r}是節(jié)點的集合，其中Vs={v1,v2,…,vn}，n為傳感器節(jié)點的個數(shù)，所有的結(jié)點都是同一種型號的無線傳感器。Es為邊的集合，任意兩個節(jié)點u和v之間存在一條邊(u,v),d(u,v)表示兩節(jié)點之間的歐氏距離，用Di表示節(jié)點vi的數(shù)據(jù)量，由于無人機(jī)飛行速度遠(yuǎn)大于無線傳感器的數(shù)據(jù)收集速度，因此我們可以假定在一次多無人機(jī)調(diào)度中所有傳感器節(jié)點的所采集到的數(shù)據(jù)量保持不變，其中1 ≤i≤n，ρv表示無人機(jī)數(shù)據(jù)收集速率。節(jié)點i的坐標(biāo)(xi,yi) ，通信鄰域半徑為R，若不考慮通信鄰域，則R=0。

1.2 數(shù)據(jù)收集模型

圖3

圖4

1.3 問題定義

假設(shè)無人機(jī)的數(shù)量為K，無人機(jī)的停靠坐標(biāo)為(x,y)，在不考慮鄰域的情況下本問題可定義為：

其中公式（1）限制每個無人機(jī)所走的路徑花費的時間不超過最大時間限制T0，公式（2）表示所有傳感器必須被K個無人機(jī)所訪問。

在考慮鄰域的情況下本問題可定義為：

公式（5）表示無人機(jī)必須停靠在以(xi,yi)為圓心，以R為半徑的圓形鄰域內(nèi)，此問題本質(zhì)上是一個優(yōu)化問題。

針對這兩個場景下的問題，本文提出兩個算法來解決。

2 算法描述

在算法一中，我們解決在沒有考慮鄰域的情況。設(shè)想問題中的無線傳感網(wǎng)規(guī)模很大，如果對整個圖進(jìn)行迭代構(gòu)造，在某些極端情況如網(wǎng)絡(luò)分布不均勻，最后劃分出來的數(shù)量可能并不是最優(yōu)的，因此我們采用一種分區(qū)域處理的策略。基于此，我們先將完全圖按照一定閾值τ進(jìn)行圖劃分，切分所有邊權(quán)重大于τ的邊。為了使劃分成若干子圖的數(shù)量合理，令τ=α?max{w(e1) ,w(e2),…,w(em)}，其中0<α<1，m為圖中邊的個數(shù)，w(ei)為邊ei的權(quán)重，其中1 ≤i≤m。然后在每個子圖中采用近似算法構(gòu)建出若干TSP 路徑，最后求得的總的路徑數(shù)量即為所求的K。

在算法二中，為了利用我們算法一的成果，我們對初始的完全圖進(jìn)行修改得到G'，任意兩個節(jié)點的距離等于初始距離減去鄰域直徑，即d'(u,v)=d( )u,v-2R，如果圓環(huán)相交則距離為0。然后在新的圖G'中調(diào)用算法一，則最終求得的數(shù)量則為無人機(jī)的數(shù)量。

因為本問題是一個TSP 問題的特殊形式，因此本問題是一個NP 難問題，即難以找到多項式時間對問題進(jìn)行求解。本文提出的兩個算法均通過迭代的方式劃分出無人機(jī)的最佳路徑。

3 實驗結(jié)果及其分析

本文在這一小節(jié)采取模擬仿真實驗對提出的兩個算法進(jìn)行驗證。在100m×100m的二維平面內(nèi)隨機(jī)均勻部署10-50 個傳感器節(jié)點，無人機(jī)最大運行時間T0=30 min，鄰域半徑為10m，無人機(jī)速度為10m/s。

圖中的實驗數(shù)據(jù)是在相同數(shù)量的傳感器節(jié)點和20個不同的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)中取得的平均值。所有的實驗結(jié)果均運行在參數(shù)為3.6 GHz 的CPU 和16GB 內(nèi)存的一臺服務(wù)器上，實驗程序運行語言為Python。

圖5

實驗結(jié)果可以看到，節(jié)點數(shù)量從10 增加到50 的過程中，隨著需要訪問的節(jié)點數(shù)增加，需要部署無人機(jī)的數(shù)量增大，在同一網(wǎng)絡(luò)規(guī)模的條件下，考慮鄰域的情況所需要部署的無人機(jī)數(shù)量明顯小于不考慮鄰域的情況下無人機(jī)的數(shù)量。因為考慮了鄰域，無人機(jī)不需要靠近傳感器節(jié)點，因此無人機(jī)飛行的距離減少，所耗費的能量也減少，大大減少了無人機(jī)數(shù)量。

我們繼續(xù)探究系數(shù)α對實驗結(jié)果的影響。見圖6。

圖6

實驗結(jié)果可以看到，隨著α不斷增大，兩種算法得到的無人機(jī)數(shù)量均是先減小在增加，特別當(dāng)α取值接近0.5 時，兩種算法得到的無人機(jī)數(shù)量最小。因為此時可以認(rèn)為子圖的數(shù)量劃分比較均衡，不存在過多或者過少的情況，所以得到的無人機(jī)的數(shù)量是最優(yōu)的。

4 結(jié)語

本文提出了在有鄰域和無鄰域兩種情況下無人機(jī)最佳數(shù)量的路徑規(guī)劃算法，在模擬數(shù)據(jù)集上進(jìn)行了仿真實驗，并且對比了兩種算法，發(fā)現(xiàn)有鄰域情況下大大節(jié)省了無人機(jī)的數(shù)量。傳統(tǒng)傳感器網(wǎng)絡(luò)數(shù)據(jù)收集采取多跳方式，移動基站收集的方式，以及單無人機(jī)的方式，本文采取了多無人機(jī)的方式，巧妙解決了傳統(tǒng)傳感器網(wǎng)絡(luò)中數(shù)據(jù)收集的相關(guān)問題。未來工作可以考慮在三維的場景下進(jìn)行無人機(jī)路徑規(guī)劃，使用不同的鄰域半徑，并且考慮節(jié)點的能耗問題。算法也可以繼續(xù)改進(jìn)，例如劃分的標(biāo)準(zhǔn)更加量化準(zhǔn)確，得到的子圖數(shù)量也更加合理。