無線傳感器網絡數據收集的多無人機調度算法研究

張俊琪

（四川大學計算機學院，成都610065）

0 引言

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

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

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

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

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

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

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

圖1

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

圖2

1 預備知識

1.1 網絡模型

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

1.2 數據收集模型

圖3

圖4

1.3 問題定義

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

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

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

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

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

2 算法描述

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

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

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

3 實驗結果及其分析

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

圖中的實驗數據是在相同數量的傳感器節點和20個不同的網絡拓撲結構中取得的平均值。所有的實驗結果均運行在參數為3.6 GHz 的CPU 和16GB 內存的一臺服務器上，實驗程序運行語言為Python。

圖5

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

我們繼續探究系數α對實驗結果的影響。見圖6。

圖6

實驗結果可以看到，隨著α不斷增大，兩種算法得到的無人機數量均是先減小在增加，特別當α取值接近0.5 時，兩種算法得到的無人機數量最小。因為此時可以認為子圖的數量劃分比較均衡，不存在過多或者過少的情況，所以得到的無人機的數量是最優的。

4 結語

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