[發明專利]多無人機協同編隊中的最優通信拓撲生成方法及裝置

在審

• 申請號: 201710392620.8
• 申請日: 2017-05-27
• 公開（公告）號: CN107094314A
• 公開（公告）日: 2017-08-25
• 發明（設計）人: 羅賀;王國強;胡笑旋;馬華偉;靳鵬;夏維
• 申請（專利權）人: 合肥工業大學
• 主分類號: H04W40/24
• 分類號: H04W40/24;H04L12/751;H04B7/185
• 代理公司: 北京路浩知識產權代理有限公司11002
• 代理人: 王瑩

技術領域

本發明涉及通信技術領域，尤其涉及一種多無人機協同編隊中的最優通信拓撲生成方法及裝置。

背景技術

在起飛巡航階段，所有無人機(UAV)通常通過點對點的通信鏈接(communicationlinks)進行信息交互，以形成一定的編隊隊形(formationshape或者formationgeometry)，并保持此編隊隊形繼續朝目標區域飛行。其中所使用的通信鏈接被稱為多UAV協同編隊的通信拓撲，同時，將UAV之間所有可用的通信鏈接的集合稱為多UAV協同編隊的編隊通信圖(FormationCommunicationGraph)。

由于通信拓撲中任何兩位置UAV之間的通信距離不同，導致通信拓撲中不同UAV之間通信鏈接具有不同的通信代價并會消耗UAV相應的電池電量或燃料。實際應用中，兩個UAV之間通信鏈接的通信代價受到很多因素影響，例如，任務要求、通信距離、飛行性能、安全性等。為簡化說明，上述通信代價直接采用通信距離來表示。

同時，每架UAV可用的電池電量或燃料又是有限的。因此，如何通過優化多無人機協同編隊通信拓撲，降低UAV的電池的電量或燃料的消耗成為了亟需解決的技術問題。

發明內容

針對現有技術中的缺陷，本發明提供了一種多無人機協同編隊中的最優通信拓撲生成方法及裝置，用于三維持久編隊中僅有部分無人機能夠作為該編隊的領航者且所有無人機未發生故障時使得三維持久編隊在保持編隊隊形安全飛行的過程中該編隊通信代價最小。

第一方面，本發明實施例提供了一種多無人機協同編隊中的最優通信拓撲生成方法，所述方法包括：

根據無人機需要組成的三維持久編隊的編隊隊形獲取編隊通信圖及其對應的賦權無向圖；

根據三維最優剛性圖獲取方法計算所述賦權無向圖的三維最優剛性圖；

根據所述三維最優剛性圖和三維最優持久圖獲取方法獲取三維最優持久圖；

若存在一個可作領航者的無人機在所述三維最優持久圖中對應節點的入度為0則所述三維最優持久圖即為該編隊的最優通信拓撲，而該無人機為該編隊的領航者。

可選地，所述方法還包括：

若不存在一個可作領航者的無人機在所述三維最優持久圖中對應節點的入度為0，則判斷是否存在一個可作領航者的無人機在所述三維最優持久圖中對應節點vi的入度為1；若是，則在所述三維最優持久圖中尋找另外一個入度小于3的節點vj，該節點vj與節點vi之間具有一條最少跳數的路；將上述最少跳數的路上所有弧反向后得到新的三維最優持久圖即為該編隊的最優通信拓撲，節點vi對應的無人機為該編隊的領航者；

若否，則判斷是否存在一個可作領航者的無人機在所述三維最優持久圖中對應節點vi的入度為2；

若是，則在所述三維最優持久圖中尋找另外一個入度小于3的節點vj，該節點vj到節點vi之間具有一條最少跳數的路；將上述最少跳數的路上所有弧反向；繼續在所述三維最優持久圖中尋找另外一個入度小于3的節點vk，該節點vk到節點vi之間具有一條最少跳數的路；將上述最少跳數的路上所有弧反向后得到新的三維最優持久圖即為該編隊的最優通信拓撲，節點vi對應的無人機為該編隊的領航者；

若否，則尋找任意一個可作領航者的無人機，該無人機在三維最優持久圖中對應節點vi的入度為3，然后在所述三維最優持久圖中尋找一個入度小于3的節點vj，該節點vj到節點vi之間具有一條最少跳數的路；將上述最少跳數的路上所有弧反向；繼續在所述三維最優持久圖中尋找另外一個入度小于3的節點vk，該節點vk到節點vi之間具有一條最少跳數的路；將上述最少跳數的路上所有弧反向；繼續在所述三維最優持久圖中尋找另外一個入度小于3的節點vl，該節點vl到節點vi之間具有一條最少跳數的路；將上述最少跳數的路上所有弧反向后得到新的三維最優持久圖即為該編隊的最優通信拓撲，節點vi對應的無人機為該編隊的領航者。

可選地，所述三維最優持久圖獲取方法包括：

將所述三維最優剛性圖轉換成第一有向圖；

在所述第一有向圖中增加虛擬領航者節點得到第二有向圖；所述虛擬領航者節點與所述第一有向圖中每個節點之間設置有三條出弧，并且所述虛擬領航者節點的每條出弧的權值相同并大于所述第一有向圖中全部弧的權值之和；

獲取所述第二有向圖的第一最小樹形圖，并刪除所述第一最小樹形圖中所述虛擬領航者節點及其對應的出弧得到第三有向圖T₁；

刪除所述第二有向圖中對應所述第一最小樹形圖中所有弧及其對應的反向弧得到第四有向圖；