劉浩 李劍鋒 曾達(dá)

摘要：考慮到多無人機(jī)可在數(shù)據(jù)采集時(shí)可在傳感器圓周邊界進(jìn)行的情形，將此場景視為一種組合優(yōu)化問題，該無人機(jī)的路徑應(yīng)用問題具有較大解空間特點(diǎn)，在路徑規(guī)劃問題中的經(jīng)典的算法（如n-splitour、RA、APF等算法）無法進(jìn)行多無人機(jī)無交叉路徑優(yōu)化，為此本文以n-splitour算法獲得n條無人機(jī)最短路徑并設(shè)計(jì)消除n條無人機(jī)路徑之間存在交叉可能的方法，同時(shí)尋求局部尋優(yōu)，再通過設(shè)計(jì)對(duì)局部優(yōu)化方法以確定每個(gè)傳感器圓周邊界訪問點(diǎn)的位置，從而可以高效地獲取多個(gè)無人機(jī)的規(guī)劃路徑解。最后通過仿真實(shí)驗(yàn)驗(yàn)證了所設(shè)計(jì)的多無人機(jī)路徑規(guī)劃算法能較為良好地解決多無人機(jī)在傳感器下數(shù)據(jù)采集中的路徑規(guī)劃問題。

引言

從目前實(shí)際應(yīng)用分析，無人機(jī)數(shù)據(jù)采集是無人機(jī)無線網(wǎng)絡(luò)中最重要的工作任務(wù)之一。傳統(tǒng)的無人機(jī)數(shù)據(jù)采集模式首先依賴于各個(gè)傳感器的實(shí)際地理位置進(jìn)行，無人機(jī)數(shù)據(jù)的傳輸和收集得貼近傳感器，才能完成所需數(shù)據(jù)的傳輸。

而在實(shí)際無人機(jī)工作的場景中，經(jīng)常會(huì)存在如下因素影響無人機(jī)感知數(shù)據(jù)的采集：

1） 對(duì)于大量且范圍廣的目標(biāo)監(jiān)控應(yīng)用，通過隨機(jī)噴灑的方式部署傳感器節(jié)點(diǎn)可能本身就會(huì)形成一個(gè)非完全連通的傳感器網(wǎng)絡(luò);

2） 由于傳感器的實(shí)際位置限制、無人機(jī)和傳感器能量損耗過快、航飛時(shí)風(fēng)速過大等原因，無人機(jī)可能無法按時(shí)到達(dá)或根本無法到達(dá)傳感器所在位置，從而影響實(shí)時(shí)的數(shù)據(jù)采集工作;

3）各無人機(jī)在訪問傳感器時(shí)，可能會(huì)因?yàn)樽陨砟芎南拗?，?dǎo)致同一傳感器數(shù)據(jù)頻繁轉(zhuǎn)發(fā)采集，會(huì)造成非必要的數(shù)據(jù)重復(fù)或滯后，就會(huì)造成數(shù)據(jù)采集中的實(shí)時(shí)性和有效性。

針對(duì)上述問題，本文主要研究，如何獲得多無人機(jī)在多傳感器數(shù)據(jù)采集工作任務(wù)中的最短路徑，從而降低傳感器中的數(shù)據(jù)采集延遲或者失效及無人機(jī)航飛時(shí)的能耗的問題。在充分研究了傳感器節(jié)點(diǎn)在傳送數(shù)據(jù)時(shí)確實(shí)有有效的數(shù)據(jù)傳輸范圍之后，本文研究的問題可理解為帶有圓形鄰域（傳感器節(jié)點(diǎn)的數(shù)據(jù)有效傳輸近似范圍）且相鄰數(shù)據(jù)傳輸范圍可相互覆蓋的旅行商問題，目前該問題已經(jīng)被證明為APX-Hard。在實(shí)際無人機(jī)應(yīng)用之中，由于傳感器的數(shù)目非常多，且所在地域較為遼闊，所以該問題的解決和優(yōu)化就顯得更為重要。

本文的數(shù)據(jù)采集路徑規(guī)劃問題研究是基于多無人機(jī)且航飛路徑端點(diǎn)設(shè)在傳感器數(shù)據(jù)傳輸范圍的圓周邊界上的節(jié)點(diǎn)路徑規(guī)劃的問題，該優(yōu)化問題具有解空間大難于求解優(yōu)化的特點(diǎn)，經(jīng)典的n-splitour等算法無法進(jìn)行多無人機(jī)路徑優(yōu)化，而且較大概率會(huì)產(chǎn)生交叉的無人機(jī)低效的路徑解，對(duì)此本研究首先利用n-splitour算法得到n條無人機(jī)路徑，并設(shè)計(jì)了順序交換的局部尋優(yōu)方法，再通過設(shè)計(jì)多無人機(jī)算法確定每個(gè)傳感器數(shù)據(jù)傳輸圓形范圍上訪問點(diǎn)的位置以達(dá)到對(duì)其多無人機(jī)路徑規(guī)劃的局部尋優(yōu)，從而可以高效地獲取近似最優(yōu)的多無人機(jī)的規(guī)劃路徑的解。

1 多無人機(jī)路徑的問題描述

假設(shè)在實(shí)際工作平面上放置了n個(gè)傳感器節(jié)點(diǎn)，其中表示第1至n個(gè)傳感器的所在地理位置，其數(shù)據(jù)通信范圍是一個(gè)標(biāo)準(zhǔn)圓形的區(qū)域，R表示對(duì)應(yīng)的數(shù)據(jù)通信半徑，其中Lbase-station表示基站（無人機(jī)初始位置）位置，Rbase-station=0?，F(xiàn)假設(shè)有x個(gè)無人機(jī)分別由基站出發(fā)，每個(gè)無人機(jī)則會(huì)根據(jù)自己所分配規(guī)劃完成的航飛路徑依次經(jīng)過所在路徑下的傳感器節(jié)點(diǎn)的圓形通信范圍，完成數(shù)據(jù)采集后將再次回到基站，記第p個(gè)無人機(jī)需要訪問的傳感器節(jié)點(diǎn)數(shù)目為mp。將第p條無人機(jī)路徑第一次進(jìn)入到路徑上第q個(gè)傳感器節(jié)點(diǎn)的通信范圍的位置稱為節(jié)點(diǎn)q上的數(shù)據(jù)采集點(diǎn)，記作。在各種可能的無人機(jī)路徑規(guī)劃方案中，讓每一個(gè)無人機(jī)路徑長度中最大的取值最小，減少無人機(jī)的路徑遍歷時(shí)間，從而降低數(shù)據(jù)采集的航飛路徑時(shí)間損耗。多無人機(jī)路徑規(guī)劃問題的公式就可表示為：

上式中，d（x，y）表示x與y兩點(diǎn)間的距離。

2.多無人機(jī)路徑規(guī)劃近似算法

多無人機(jī)路徑如何指派以及各個(gè)無人機(jī)訪問點(diǎn)的位置及順序等如何確定均需要優(yōu)化。為此將上述問題分解為兩個(gè)步驟求解：第一步是基于n-splitour解決多個(gè)無人機(jī)的航飛路徑指派問題，并設(shè)計(jì)出無交叉路徑的局部尋優(yōu)方法，第二步是提出了梯度下降搜索算法解決訪問點(diǎn)的位置優(yōu)化問題，具體多無人機(jī)路徑規(guī)劃算法的設(shè)計(jì)步驟和分析如下。

2.1?n個(gè)無人機(jī)路徑指派問題的求解

通過對(duì)n-splitour算法的研究可發(fā)現(xiàn)，每一條無人機(jī)路徑的開始路勁和結(jié)束路勁，可能與自身規(guī)劃路徑之前的路勁發(fā)生邊邊相交關(guān)系。但是依據(jù)三角不等式，在TSP問題中最優(yōu)解的路徑是一定不會(huì)存在相交邊的情況，為此設(shè)計(jì)交換的方法（TSP問題中2opt或3opt算法）對(duì)無人機(jī)路徑去除邊與邊相交的情況，從而更進(jìn)一步縮短每個(gè)無人機(jī)路徑的長度，則可達(dá)到局部尋優(yōu)的效果。具體設(shè)計(jì)的分為以下四步如下：

1使用現(xiàn)有TSP算法尋找到一條無人機(jī)航飛TSP回路;2采用n-splitour算法得到n個(gè)無人機(jī)的航飛路徑;3檢測各個(gè)無人機(jī)路徑中的起始邊及結(jié)束邊產(chǎn)生的自相交;4若3）檢測到有自相交，則消除各個(gè)無人機(jī)路徑中的起始邊及結(jié)束邊產(chǎn)生的自相交。

2.2?訪問點(diǎn)位置的優(yōu)化

由上述算法可以得到每一個(gè)無人機(jī)航飛的路徑的解，但還需要確定無人機(jī)路徑上在傳感器數(shù)據(jù)傳輸范圍上即圓周邊界上的訪問點(diǎn)的位置。由于無人機(jī)所在的訪問點(diǎn)要求在傳感器通信圓周上。在尋找最短路徑上，每一個(gè)無人機(jī)的訪問點(diǎn)將對(duì)應(yīng)的θ的取值范圍，可以由[0，2π]縮小到由該傳感器數(shù)據(jù)傳輸圓周到下一個(gè)傳感器數(shù)據(jù)傳輸圓周的兩條外切線所包圍的區(qū)間。

為了壓縮搜索范圍，提高求解效率。如下圖所示考慮無人機(jī)通過A、B兩個(gè)傳感器的情形，無人機(jī)從基站出發(fā)，依次訪問傳感器A、B后，再回到基站。傳感器A上訪問點(diǎn)的可行取值區(qū)域位于弧A1A2內(nèi)側(cè)，與弧A3A4內(nèi)側(cè)的交集部分即弧A2A3內(nèi)側(cè)之間，同理傳感器B上的可行區(qū)域在弧B1B3內(nèi)側(cè)之間。對(duì)于有多個(gè)傳感器節(jié)點(diǎn)的情形，每個(gè)傳感器節(jié)點(diǎn)對(duì)應(yīng)弧段的起始范圍可用近似的方法計(jì)算得到。

3?算法仿真

為了驗(yàn)證本文所提出的多無人機(jī)路徑規(guī)劃模型的合理性及其優(yōu)化求解算法的正確性，進(jìn)行了如下仿真實(shí)驗(yàn)。計(jì)算機(jī)的硬件平臺(tái)為英特爾處理器i7-9750H 2.6GHz，8GB內(nèi)存，其軟件平臺(tái)為Matlab2018b。仿真實(shí)驗(yàn)在長寬各500的區(qū)域內(nèi)隨機(jī)拋灑100個(gè)傳感器節(jié)點(diǎn)。實(shí)驗(yàn)隨機(jī)生成了1000個(gè)樣本，統(tǒng)計(jì)結(jié)果見表1，其中計(jì)算時(shí)間為各次計(jì)算的均值。通過實(shí)驗(yàn)結(jié)果，在ρ=π/40時(shí)可取得最短的平均長度，在ρ=π/20時(shí)雖與前者的平均長度接近，但相對(duì)前者計(jì)算時(shí)間有了明顯減少。

下圖顯示了一個(gè)采用了3個(gè)無人機(jī)進(jìn)行路徑規(guī)劃，傳感器節(jié)點(diǎn)通信范圍是均勻分布場景下的路徑規(guī)劃實(shí)例圖。

4結(jié)論

本文將實(shí)際應(yīng)用場景的多無人機(jī)航飛數(shù)據(jù)采集中的路徑規(guī)劃問題建模為路徑端點(diǎn)在傳感器通信圓周之上的組合優(yōu)化問題，并設(shè)計(jì)了求解的近似算法，驗(yàn)證了多無人機(jī)路徑規(guī)劃模型的合理性及其優(yōu)化求解算法的正確性，

參考文獻(xiàn)：

[1]Gupta L.， Jain R.， Vaszkun G. 無人機(jī)通信網(wǎng)絡(luò)中關(guān)鍵技術(shù)研究進(jìn)展[J]。通信學(xué)報(bào)，2016，35（2）：457-461。

[2]Maurice K.，Joseph A.，Chadi A. 無人機(jī)輔助車輛網(wǎng)絡(luò)建模與性能分析[J]。汽車工程學(xué)報(bào)，2019，38（9）：889 - 898。

基金號(hào)：南寧理工學(xué)院2019年度校級(jí)科研項(xiàng)目+基于無人機(jī)在無線傳感網(wǎng)數(shù)據(jù)采集中的路徑規(guī)劃研究+KY200901;

2020年廣西高校中青年教師科研基礎(chǔ)能力提升項(xiàng)目+5050KY58011。

作者簡介：劉浩（1990-），男，漢族，廣西桂林人，桂林理工大學(xué)碩士，講師，研究方向：計(jì)算智能