[發明專利]基于負載均衡的多UAV路徑設計方法

在審

• 申請號: 201910861570.2
• 申請日: 2019-09-12
• 公開（公告）號: CN110634331A
• 公開（公告）日: 2019-12-31
• 發明（設計）人: 劉貴云;林立新;李致富;蔣文俊;彭百豪;張杰釗;唐冬
• 申請（專利權）人: 廣州大學
• 主分類號: G08G5/00
• 分類號: G08G5/00;G08G5/04;H04W4/40;H04W28/08;H04W40/04;H04W40/32
• 代理公司: 44245 廣州市華學知識產權代理有限公司
• 代理人: 林梅繁

本發明涉及無人機技術，具體為基于負載均衡的多UAV路徑設計方法，首先根據分簇效果的輪廓系數確定聚類分簇數；將多個傳感器結點劃分成獨立的、相互之間無重疊的多個簇群；在分簇結果基礎上優化蟻群智能算法；挑選出最多結點數目的簇群，從該簇群內選出與另外簇群的簇心最短路徑的傳感器結點作為可疑結點，動態調整可疑結點的歸屬簇群；建立簇頭負責機制，通過蟻群智能算法挑出使通信路徑最短的傳感器結點作為簇頭，簇頭統一負責所述小簇群內的歸屬結點與外界交流；異構UAV，根據不同UAV所攜帶能量的不同設定其飛行時間。本發明能避免無人機之間相互碰撞，不需要借助多無人機之間大量的信息通信，減小了無人機的能量消耗，提高了系統的性能。

技術領域

本發明涉及無人機技術，具體為基于負載均衡的多UAV路徑設計方法。

背景技術

近幾年無人機UAV由于它的操作性、續航性、價格等方面有較好的優點，得到了世界各國的關注，也成為當今研發的熱點。已經在多個方面，比如軍事、環境保護、搜救行動上有廣泛的應用。

隨著無人機技術的普及，Multi-UAV(多無人機)的問題也逐漸被引起重視，但是大部分文獻的重點在于UAV的路徑如何規劃、障礙物的避免及其無人機的相互通信上，在全面地考慮多無人機的負載均衡問題上的研究是比較缺乏的。如何在傳感器結點隨機的情況下盡可能均衡地分配給無人機進行采集，這一多無人機的負載均衡問題正是本發明要解決的。

現有部分文獻通過對系統中多UAV的劃分，分成了兩派，分別為決策集合部分和成員集合部分。兩者處于不平等的地位，成員集合中UAV的分配調度和任務管理由決策集合里的UAV負責，決策集合里的UAV通過動態調整，調動成員集合中的UAV完成任務，并且兼顧均衡性與總體高效性。這樣雖然可以動態地劃分，使得處理過程更加靈活，但是卻使得通信的開銷加大，而傳感器結點的一次壽命也會因此縮短，而這對傳感器網絡系統是高代價的，會導致系統總的生存時間縮短。

現有部分文獻通過k-means聚類分簇算法提前對系統的結點進行分簇，通過引入聚類指數來評判算法的優劣性。總體來說，這類算法考慮得比較全面，兼顧了負載分配均衡的任務要求。但是實驗模擬場景人為設定過于理想化，結點數為固定不變的，而且實驗開始到結束結點位置也是固定的，所以該算法是否能滿足當初始結點為隨機時的情況仍需深入探索，而大部分實際運用的結點位置是不固定的，因此需要進一步驗證。

發明內容

為解決現有技術所存在的技術問題，本發明提供基于負載均衡的多UAV路徑設計方法，該方法對需要采集信息的任務結點進行分配，將所有結點分成一個個互不干擾的簇，每一個簇內使用蟻群算法，通過多次算法的迭代，計算出單無人機在其負責的簇內的最短路徑，以滿足多無人機負載均衡的要求。

本發明采用以下技術方案來實現：基于負載均衡的多UAV路徑設計方法，包括以下步驟：

S1、根據分簇效果的輪廓系數，確定k-means++聚類分簇算法的聚類分簇數K；

S2、根據k-means++聚類分簇算法，將多個傳感器結點劃分成獨立的、相互之間無重疊的多個簇群；

S3、在步驟S2中k-means++聚類分簇算法的分簇結果基礎上，優化蟻群智能算法；

S4、基于步驟S2中k-means++聚類分簇算法的分簇結果，挑選出最多結點數目的簇群，從該簇群內選出與另外簇群的簇心最短路徑的傳感器結點，作為可疑結點；動態調整可疑結點的歸屬簇群，以滿足多UAV負載均衡的要求；

S5、建立簇頭負責機制，在步驟S2中k-means++聚類分簇算法的分簇結果所劃分好的簇群內，再次將在通信范圍內的傳感器結點歸并到同一小簇群，并通過蟻群智能算法挑出使通信路徑最短的傳感器結點作為簇頭，簇頭統一負責所述小簇群內的歸屬結點與外界交流；

S6、異構UAV，對UAV的飛行時間進行預先確定，根據不同UAV所攜帶能量的不同，設定UAV的飛行時間。