海上無人集群聯(lián)合軌跡設(shè)計(jì)方法

胡鈺林 吳 鵬 原曉鵬 李 博 江 昊 羅 威

①(武漢大學(xué)電子信息學(xué)院 武漢 430072)

②(哈爾濱工業(yè)大學(xué)(威海)信息科學(xué)與工程學(xué)院 威海 264209)

③(中國艦船研究設(shè)計(jì)中心 武漢 430000)

1 引言

海洋大數(shù)據(jù)的快速積累為海洋可持續(xù)發(fā)展起到了重要作用。傳感器存儲(chǔ)的水文、大氣、生物活動(dòng)等數(shù)據(jù)為海洋開發(fā)和保護(hù)提供了豐富的決策信息[1]。然而，如何有效地收集傳感器的數(shù)據(jù)是一個(gè)關(guān)鍵性問題，尤其是在海況不可控的海域，控制中心無法直接通過無線傳輸進(jìn)行設(shè)備數(shù)據(jù)收集[2,3]。因此，為該類型海域研究新的數(shù)據(jù)收集方法意義重大。

得益于無人機(jī)通信技術(shù)的高速發(fā)展，利用無人機(jī)前往危險(xiǎn)區(qū)域收集設(shè)備數(shù)據(jù)成為一種有效的解決策略[4]。在無線網(wǎng)絡(luò)中，無人機(jī)可作為移動(dòng)基站，組成多層異構(gòu)網(wǎng)絡(luò)，與蜂窩網(wǎng)絡(luò)無法覆蓋的用戶進(jìn)行數(shù)據(jù)傳輸[5–7]。由于續(xù)航較差，無人機(jī)需要定時(shí)飛回基地充電，但在遼闊的海面，無人機(jī)無法像在陸地一樣飛回基地進(jìn)行能量補(bǔ)給和數(shù)據(jù)卸載，因此，在海上使用無人機(jī)收集數(shù)據(jù)需要采用新的補(bǔ)給方案。綜合無人機(jī)的高機(jī)動(dòng)性和高可控性、無人船的運(yùn)載和續(xù)航能力，本文提出“無人船+多無人機(jī)”的集群形式，無人船作為移動(dòng)平臺(tái)，無人機(jī)從無人船起飛前往任務(wù)海域收集設(shè)備數(shù)據(jù)，并在需要時(shí)刻返回?zé)o人船進(jìn)行補(bǔ)給。

由于無人機(jī)具有高機(jī)動(dòng)性，可以為整個(gè)通信系統(tǒng)引入更多自由度[8]，通過優(yōu)化無人機(jī)的部署位置和飛行軌跡可以與用戶設(shè)備建立更高質(zhì)量的通信鏈路以實(shí)現(xiàn)更高速率更低誤碼率的數(shù)據(jù)傳輸。為了提高數(shù)據(jù)收集的效率，對(duì)無人機(jī)集群和無人船軌跡的設(shè)計(jì)成為關(guān)鍵問題。文獻(xiàn)[9,10]研究一種基于強(qiáng)化學(xué)習(xí)的無人機(jī)軌跡動(dòng)態(tài)優(yōu)化方法，該方法側(cè)重根據(jù)輸入環(huán)境的變化動(dòng)態(tài)調(diào)整軌跡，無法得到事前最優(yōu)軌跡，并沒有徹底解決無人機(jī)最優(yōu)軌跡優(yōu)化問題。為了獲得無人機(jī)的最優(yōu)軌跡，文獻(xiàn)[11]提出將無人機(jī)的軌跡離散化求解的方法以實(shí)現(xiàn)較優(yōu)的任務(wù)軌跡，但存在計(jì)算復(fù)雜度過大的問題。為了降低軌跡優(yōu)化的復(fù)雜度，文獻(xiàn)[12]忽略無人機(jī)速度限制，通過優(yōu)化多個(gè)懸停點(diǎn)來確定無人機(jī)的軌跡，該方案只能實(shí)現(xiàn)一個(gè)次優(yōu)解。文獻(xiàn)[13,14]在考慮到無人機(jī)最大速度限制情況下，分別在1維和2維場景實(shí)現(xiàn)了低復(fù)雜度的最優(yōu)軌跡設(shè)計(jì)并通過連續(xù)凸近似的方法得到了一個(gè)性能較好的次優(yōu)解，但文章中的方法不能直接應(yīng)用于2維協(xié)作的場景。本文將針對(duì)包含無人船和無人機(jī)在內(nèi)的無人集群協(xié)同軌跡設(shè)計(jì)這一開放性問題，首次提出基于用戶分組和SHF結(jié)構(gòu)的低復(fù)雜度軌跡優(yōu)化算法，并獲得高效的聯(lián)合軌跡解。

本文結(jié)構(gòu)如下：第2節(jié)構(gòu)建一個(gè)海上無人機(jī)集群通信模型，提出原始的聯(lián)合軌跡優(yōu)化問題；第3節(jié)將初始問題分解為用戶分組和單無人機(jī)軌跡設(shè)計(jì)兩個(gè)子問題，在解決子問題的基礎(chǔ)上進(jìn)行問題的重組，并針對(duì)重組問題的非凸性，提出連續(xù)凸近似的高效迭代求解方法；第4節(jié)仿真驗(yàn)證算法的有效性和相對(duì)其他算法的優(yōu)勢；第5節(jié)總結(jié)全文。

2 系統(tǒng)模型

圖1為一個(gè)海上無人機(jī)集群數(shù)據(jù)收集系統(tǒng)，該系統(tǒng)包括N架無人機(jī)，K個(gè)傳感器用戶以及一艘無人船。無人船在從起始點(diǎn)(xα,yα)到目標(biāo)點(diǎn)(xβ,yβ)航行過程中放飛無人機(jī)收集傳感器的數(shù)據(jù)，并在每個(gè)無人機(jī)的飛行終點(diǎn)回收無人機(jī)。無人機(jī)飛行高度固定為H，最大飛行速度為V，無人船最大速度為Vp，傳感器位置已知，記第k 個(gè)用戶位置為(wx,k,wy,k)，其需要卸載的數(shù)據(jù)量為Dk。

圖 1 海洋無人機(jī)通信系統(tǒng)

具體而言，對(duì)無人機(jī)i，其在τi時(shí)刻從無人船起飛收集用戶數(shù)據(jù)，總飛行時(shí)間為Ti即無人船于τi+Ti時(shí)刻回收該無人機(jī)。在該無人機(jī)飛行過程中，考慮在有限載波資源下情況存在用戶調(diào)度問題，引入對(duì)用戶k的調(diào)度參數(shù)ai,k，有

約束式(3b)表示收集完所有用戶數(shù)據(jù)這一約束，約束式(3c)表示無人機(jī)起飛前和回收后與無人船位置應(yīng)該相同，約束式(3d)為無人船起止點(diǎn)約束，約束式(3e)為無人船和無人機(jī)速度約束。注意到約束式(3b)是個(gè)非凸約束，該問題其余式子為凸，因此該問題為非凸問題。并且，該問題包含連續(xù)時(shí)間上的無窮個(gè)變量(xi(t),yi(t))，這使得該問題的直接求解十分復(fù)雜。有必要對(duì)問題進(jìn)行分解和重組。

3 問題分解與重組求解

原問題的求解難點(diǎn)在于該問題是對(duì)連續(xù)時(shí)間上無窮個(gè)位置變量求解的非凸問題，并且存在任務(wù)調(diào)度問題。因此問題的分解目標(biāo)在于明確無人機(jī)的服務(wù)的用戶以及實(shí)現(xiàn)低復(fù)雜度的無人機(jī)軌跡優(yōu)化。本節(jié)將原問題分解為基于用戶分布的用戶分組和單無人機(jī)軌跡優(yōu)化兩個(gè)子問題，首先引入分組方法K-means，明確無人機(jī)的服務(wù)用戶，消除無人機(jī)之間任務(wù)約束問題。然后針對(duì)單無人機(jī)的軌跡設(shè)計(jì)，通過引入連續(xù)懸停飛行結(jié)構(gòu)SHF，將連續(xù)時(shí)間上無窮個(gè)位置變量的優(yōu)化問題轉(zhuǎn)化為有限個(gè)無人機(jī)懸停點(diǎn)的求解問題，降低了軌跡求解難度。最后將分解的兩個(gè)子問題進(jìn)行重組，針對(duì)重組問題的非凸性，采用連續(xù)凸近似的方法，最終實(shí)現(xiàn)復(fù)雜度較低的軌跡迭代算法。

3.1 用戶分組

3.2 單無人機(jī)軌跡重構(gòu)

圖2 用戶分組

在任務(wù)分配的基礎(chǔ)上，為獲得第i(i=1,2,...,N)個(gè)無人機(jī)的最優(yōu)軌跡，考慮如圖3所示含有Ki個(gè) 用戶的單無人機(jī)服務(wù)場景。

圖3 單無人機(jī)服務(wù)場景示例

令懸停時(shí)間矢量為ti，即第j個(gè)懸停點(diǎn)(xi,j,yi,j)上懸停時(shí)間為ti,j，無人機(jī)起止點(diǎn)和懸停點(diǎn)將無人機(jī)軌跡劃分為Ki+1條弧線，令第j條弧li,j的長為

表1 K-means算法流程

圖4 SHF結(jié)構(gòu)下無人機(jī)軌跡示例

那么，以起飛時(shí)刻作為計(jì)時(shí)起點(diǎn)，無人機(jī)i的軌跡可表示為

圖5 考慮到轉(zhuǎn)折點(diǎn)的SHF結(jié)構(gòu)軌跡示例

3.3 問題重組與求解

3.3.1 問題重組

3.3.2 連續(xù)凸近似

3.3.3 軌跡初始化和軌跡迭代算法

4 軌跡仿真

利用計(jì)算機(jī)對(duì)算法進(jìn)行仿真，系統(tǒng)參數(shù)：無人船的出發(fā)點(diǎn)為(0, 0)，終點(diǎn)為(3000, 3000) m，無人船速度5 m/s，無人機(jī)數(shù)目為3，飛行高度為30 m，飛行速度為9 m/s，轉(zhuǎn)折點(diǎn)數(shù)目為1，用戶節(jié)點(diǎn)射頻功率10 dBW，噪聲功率–60 dBW，信道增益為–30 dB，用戶數(shù)目為15，數(shù)據(jù)量從0到100的均勻分布中取值，用戶隨機(jī)分布在任務(wù)海域中，圖6展示了根據(jù)聚類算法實(shí)現(xiàn)的用戶分組效果圖。

圖6 用戶分組示例

表2 軌跡迭代算法

圖7展示了無人機(jī)和無人船的聯(lián)合軌跡，無人船的軌跡為無人機(jī)的起止點(diǎn)確定的折線段，無人機(jī)軌跡由懸停點(diǎn)和轉(zhuǎn)折點(diǎn)確定。注：考慮到圖例數(shù)目過多問題，在表述無人機(jī)軌跡、懸停點(diǎn)、轉(zhuǎn)折點(diǎn)和起止點(diǎn)時(shí)，圖例中都用的黑色表示。但在途中用的每架無人機(jī)對(duì)應(yīng)的顏色。由于離用戶越近，無線傳輸速率越快，無人機(jī)的懸停點(diǎn)趨向于在用戶附近分布，可以看出無人機(jī)的懸停點(diǎn)幾乎與用戶位置重合。值得注意的是，放大圈中部分可以發(fā)現(xiàn)，雖然懸停點(diǎn)與用戶位置距離很近，但兩者并不重合，原因如文獻(xiàn)[12]所述，無人機(jī)的懸停點(diǎn)為原問題拉格朗日方程中對(duì)所有用戶傳輸速率總和最大的點(diǎn)，而不是對(duì)單一用戶傳輸速率最大的點(diǎn)，因此無人機(jī)的懸停點(diǎn)不在用戶正上方。

圖7 聯(lián)合軌跡優(yōu)化示例

圖8比較了不同無人機(jī)速度下的軌跡。首先圖8(a)和圖8(b)左側(cè)大圖對(duì)兩種速度下，軌跡的大致形狀進(jìn)行比較。無人機(jī)速度改變時(shí)，軌跡的大致形狀并不發(fā)生變化，無人機(jī)的懸停點(diǎn)依然在用戶附近，這是因?yàn)榭紤]對(duì)具體某個(gè)用戶的數(shù)據(jù)傳輸速率，無人機(jī)總是傾向于在該用戶附近懸停，改變無人機(jī)的速度并不會(huì)導(dǎo)致軌跡發(fā)生巨大變化。圖8(a)和圖8(b)右側(cè)小圖對(duì)不同速度下的局部軌跡進(jìn)行比較。無人機(jī)速度越大，懸停點(diǎn)的位置越靠近用戶。這是因?yàn)樵谝欢ǖ娜蝿?wù)時(shí)間內(nèi)，增加無人機(jī)的速度能增加無人機(jī)向用戶的位移。因此，可以通過增加無人機(jī)的速度使無人機(jī)懸停點(diǎn)更靠近用戶，在懸停點(diǎn)獲得對(duì)該用戶更大的數(shù)據(jù)傳輸速率，但注意，在該懸停點(diǎn)其他用戶的數(shù)據(jù)傳輸速率不一定增加，因此整個(gè)任務(wù)時(shí)間不一定減小，圖9體現(xiàn)了這一變化趨勢。

圖8 不同無人機(jī)速度下聯(lián)合軌跡比較

圖9給出本算法與TSP方法的性能對(duì)比，TSP方法通過求解旅行商問題獲得通過所有用戶節(jié)點(diǎn)的最短路徑，并在此基礎(chǔ)上優(yōu)化無人機(jī)在用戶上方的懸停時(shí)間。無人機(jī)和無人船任務(wù)時(shí)間分別隨無人機(jī)速度變化如圖9(a)所示，隨著無人機(jī)速度增加，本算法下無人機(jī)和無人船的任務(wù)時(shí)間波動(dòng)下降，基于TSP算法的無人機(jī)和無人船的任務(wù)時(shí)間線性下降，并且本算法無人機(jī)的任務(wù)時(shí)間小于TSP算法無人機(jī)的任務(wù)時(shí)間，而兩種算法無人船的任務(wù)時(shí)間幾乎一致。TSP方法優(yōu)化過程中，無人機(jī)與無人船軌跡不變，只優(yōu)化無人機(jī)懸停時(shí)間的情況下，問題為凸優(yōu)化問題所求的即是該方案下的最優(yōu)解，因此任務(wù)時(shí)間與無人機(jī)速度呈現(xiàn)線性關(guān)系，而由于本算法在求解過程中采用了連續(xù)凸近似的方法，最終獲得的聯(lián)合軌跡為該方案下的一個(gè)次優(yōu)解，因此任務(wù)時(shí)間與無人機(jī)的速度并不呈現(xiàn)線性關(guān)系，這并非為算法穩(wěn)定性差所致。由于本算法同時(shí)優(yōu)化無人機(jī)軌跡和懸停時(shí)間，比TSP方法更接近于全局最優(yōu)解，因此本方法下無人機(jī)的任務(wù)時(shí)間遠(yuǎn)小于TSP方法下無人機(jī)的任務(wù)時(shí)間。由于TSP方法下無人船的軌跡比本方法短，因此無人船的運(yùn)動(dòng)時(shí)間比本方法短，但由于TSP方法下無人機(jī)的任務(wù)時(shí)間更長，無人船的等待時(shí)間更長，因此兩種方法下無人船的任務(wù)時(shí)間相差不大。圖9(b)展示了總?cè)蝿?wù)時(shí)間與無人機(jī)速度的關(guān)系，本算法的任務(wù)時(shí)間隨無人機(jī)速度變化雖然存在波動(dòng)，但明顯優(yōu)于TSP優(yōu)化方法。

圖9 本算法與TSP算法任務(wù)時(shí)間對(duì)比

5 結(jié)束語

本文考慮了一個(gè)無人機(jī)集群與無人船平臺(tái)聯(lián)合數(shù)據(jù)收集系統(tǒng)，在無人機(jī)最大速度限制下研究了一個(gè)旨在最小化任務(wù)時(shí)間的聯(lián)合軌跡設(shè)計(jì)問題。本文首先考慮到用戶任務(wù)分配問題，通過分組算法k-means進(jìn)行用戶分組。其次，本文描述了無人機(jī)軌跡的2維結(jié)構(gòu)，在此基礎(chǔ)上引入SHF結(jié)構(gòu)，將連續(xù)時(shí)間上無限個(gè)軌跡點(diǎn)的優(yōu)化問題轉(zhuǎn)化為有限懸停點(diǎn)和轉(zhuǎn)折點(diǎn)的求解問題。在此基礎(chǔ)上，將原問題重構(gòu)為一個(gè)低復(fù)雜度的問題。并引入連續(xù)凸近似的方法將非凸問題轉(zhuǎn)化為可高效求解的凸問題。最后通過仿真驗(yàn)證了本方法的有效性。值得一提的是，雖然本文研究的是海洋數(shù)據(jù)收集場景下的無人機(jī)和無人船的軌跡，所提出的無人船(或移動(dòng)補(bǔ)給臺(tái))與無人機(jī)的聯(lián)合軌跡設(shè)計(jì)思想、問題解構(gòu)和子問題求解方法都可以拓展到其他(如無線能量傳輸?shù)?需要無人集群協(xié)同工作的聯(lián)合軌跡設(shè)計(jì)問題。值得注意的是，在無線能量傳輸場景下為無人機(jī)向空間輻射射頻能量，而本文考慮的無線數(shù)據(jù)收集場景為用戶上行傳輸數(shù)據(jù)，但在軌跡設(shè)計(jì)層面兩者的實(shí)質(zhì)都相同，無人機(jī)的最優(yōu)軌跡都滿足連續(xù)懸停飛行結(jié)構(gòu)。