無人‑有人機編隊信息交互拓撲容錯優化方法及裝置與流程
2023-09-11 17:07:15 2
本發明涉及通信技術領域，尤其涉及一種無人-有人機編隊信息交互拓撲容錯優化方法及裝置。
背景技術：
在起飛巡航階段，無人-有人機編隊中各飛機通常通過點對點的通信連結(communicationlinks)進行信息交互，以形成一定的編隊隊形(formationshape或者formationgeometry)，並保持此編隊隊形繼續朝目標區域飛行。其中所使用的通信連結被稱為編隊的信息交互拓撲(informationexchangetopology)、通信拓撲(communicationtopology)、連接拓撲(connectiontopology)、信息結構(informationstructure)或者信息拓撲(informationtopology)，它們只是無人-有人機編隊中任意兩飛機之間所有可用的通信連結集合中的一部分。為了統一表述，下文採用「信息交互拓撲」這一名稱。同時，將無人-有人機編隊所有可用的通信連結的集合稱為編隊的編隊通信圖(formationcommunicationgraph)。
由於信息交互拓撲中任何兩位置無人機和/或有人機之間的通信距離不同，導致信息交互拓撲中不同飛機之間通信連結具有不同的通信代價並會消耗飛機相應的電池電量或燃料。實際應用中，兩架飛機(無人機，有人機)之間通信連結的通信代價受到很多因素影響，例如，任務要求、通信距離、飛行性能、安全性等。為簡化說明，上述通信代價直接採用通信距離來表示。同時，每架飛機(無人機，有人機)可用的電池電量或燃料又是有限的。此外，編隊飛行過程中某個或多個飛機可能會發生通信故障，使得當前信息交互拓撲中的某些通信連結不能夠被使用，從而導致飛機不能繼續保持編隊隊形，嚴重時甚至會導致飛機碰撞事故。因此，如何通過優化無人-有人機編隊的信息交互拓撲，以避免發生飛機碰撞事故並恢復隊形，同時使得此無人-有人機編隊在繼續保持隊形過程中的編隊通信代價最小成為了亟需解決的技術問題。
技術實現要素：
針對現有技術中的缺陷，本發明提供了一種無人-有人機編隊信息交互拓撲容錯優化方法及裝置，用於在無人-有人機編隊組成的二維持久編隊出現通信故障之後優化此二維持久編隊的信息交互拓撲，以避免發生飛機碰撞事故並恢復隊形，同時使得此二維持久編隊在繼續保持隊形過程中的編隊通信代價最小。
第一方面，本發明實施例提供了一種無人-有人機編隊信息交互拓撲容錯優化方法，所述方法包括：
s1、根據無人-有人機編隊需要組成的二維持久編隊的隊形獲取編隊通信圖；
s2、當所述無人-有人機編隊發生通信故障時，根據所述通信故障的類型在所述編隊通信圖中刪除通信故障弧或通信故障節點以獲取第一重構編隊通信圖；
s3、根據信息交互拓撲重構算法獲取所述第一重構編隊通信圖對應的第一最優重構信息交互拓撲；
s4、根據所述第一最優重構信息交互拓撲、無人-有人機編隊的每個位置配置和所述信息交互拓撲重構算法獲取滿足預設條件n＞|v|！的第二最優重構信息交互拓撲即為所述無人-有人機編隊的重優化信息交互拓撲；
所述位置配置是指無人-有人機編隊中各架飛機在編隊隊形中的位置；通信故障發生之前的位置配置為第一位置配置pr；|v|表示無人-有人機編隊中飛機的數量；n取1、2、……、|v|！。
第二方面，本發明實施例提供了一種無人-有人機編隊信息交互拓撲容錯優化裝置，所述裝置包括：
編隊通信圖獲取模塊，用於根據無人-有人機編隊需要組成的二維持久編隊的隊形獲取編隊通信圖；
第一重構編隊通信圖獲取模塊，用於在所述無人-有人機編隊發生通信故障時，根據所述通信故障的類型在所述編隊通信圖中刪除通信故障弧或通信故障節點以獲取第一重構編隊通信圖；
第一最優重構信息交互拓撲獲取模塊，用於根據信息交互拓撲重構算法獲取所述第一重構編隊通信圖對應的第一最優重構信息交互拓撲；
重優化信息交互拓撲獲取模塊，用於根據所述第一最優重構信息交互拓撲、無人-有人機編隊的每個位置配置和所述信息交互拓撲重構算法獲取滿足預設條件n＞|v|！的第二最優重構信息交互拓撲即為所述無人-有人機編隊的重優化信息交互拓撲；
所述位置配置是指無人-有人機編隊中各架飛機在編隊隊形中的位置；通信故障發生之前的位置配置為第一位置配置pr；|v|表示無人-有人機編隊中飛機的數量；n取1、2、……、|v|！。
由上述技術方案可知，本發明能夠在無人-有人機組成的二維持久編隊發生通信故障之後，優化此二維持久編隊的信息交互拓撲，以避免發生飛機碰撞事故並恢復編隊隊形，同時使得此二維持久編隊在繼續保持隊形過程中的編隊通信代價最小。
附圖說明
為了更清楚地說明本發明實施例或現有技術中的技術方案，下面將對實施例或現有技術描述中所需要使用的附圖作簡單地介紹，顯而易見地，下面描述中的附圖僅僅是本發明的一些實施例，對於本領域普通技術人員來講，在不付出創造性勞動的前提下，還可以根據這些圖獲得其他的附圖。
圖1是本發明實施例提供的無人-有人機編隊信息交互拓撲容錯優化方法的流程示意圖；
圖2(a)～(b)是本發明實施例中3架無人機和2架有人機組成的二維持久編隊的隊形以及相對位置示意圖；有人機fighter1和fighter2分別在隊形的1號和2號位置，無人機uav1、uav2和uav3分別在隊形的3號、4號和5號位置；
圖3為本發明實施例提供的上述無人-有人機編隊無通信故障時的最優信息交互拓撲示意圖；
圖4(a)～(b)是上述無人-有人機編隊中的fighter2發生單播發射機故障時採用圖1方法獲取該無人-有人機編隊的優化信息交互拓撲的主要過程示意圖；
圖5是本發明實施例提供的無人-有人機編隊信息交互拓撲容錯優化裝置框圖。
具體實施方式
下面將結合本發明實施例中的附圖，對本發明實施例中的技術方案進行清楚、完整地描述，顯然，所描述的實施例僅僅是本發明一部分實施例，而不是全部的實施例。基於本發明中的實施例，本領域普通技術人員在沒有做出創造性勞動前提下所獲得的所有其他實施例，都屬於本發明保護的範圍。
圖1為本發明一實施例提供的一種無人-有人機編隊信息交互拓撲容錯優化方法，所述方法包括：
s1、根據無人-有人機編隊需要組成的二維持久編隊的隊形獲取編隊通信圖。
無人-有人機組成的二維持久編隊的編隊控制方法是一種基於距離的編隊控制方法，其基本思想是：編隊中的一架有人機作為編隊領航者(formationleader)按照預定的編隊參考航跡飛行，編隊中的另外一架飛機(有人機或無人機)在飛行過程中只需要保持與編隊領航者的距離恆定，其餘的飛機在飛行過程則需要同時保持與另外兩架飛機之間的距離恆定，從而實現對二維空間的編隊隊形的保持。
假設n架飛機(以下用plane表示，包括有人機或無人機)需要使用二維持久編隊的編隊控制方法來形成和保持一個二維空間的編隊隊形s，s中的n個位置分別編號為{1,2,…,n}，只有有人機可以作為編隊領航者，每架飛機可以通過點對點通信連結和其它任意飛機進行信息交互，每個通信連結的通信代價由其相應的通信距離決定。因此，可以用一個賦權有向圖d＝(v,a,w,p)來表示編隊中飛機之間所有可用的通信連結，並簡稱為編隊通信圖：
(1)v＝{vi},1≤i≤n是圖中的節點集合，其中vi表示planei。
(2)是圖中的弧集合，其中弧aij＝(vi,vj)表示從planei到planej有一個可用的通信連結，使得planei能發送信息給planej，從而planej可以根據接收到的信息來調整自身的運動參數以保持與planei的距離恆定。
(3)w＝{w(aij)},aij∈a是圖中所有弧的權值集合，其中w(aij)表示從planei到planej的通信連結aij的代價。
(4)p＝{pi},1≤i≤n是每個plane在編隊隊形s的具體位置集合，簡稱為plane位置配置。其中將編隊隊形s中的n個位置分別編號為{1,2,...,n}，則1≤pi≤n表示planei在編隊隊形s中的具體位置。
根據前面的描述可知，無人-有人機組成的二維持久編隊中的每架飛機最多只需要從其它兩架飛機接收信息，這意味著不需要使用所有可用的通信連結就可以實現編隊隊形的形成和保持。因此，無人-有人機編隊的信息交互拓撲t＝(v,a*,w*,p)是其編隊通信圖d＝(v,a,w,p)的一個特殊子圖，其中令w(t)表示信息交互拓撲t對應的編隊通信代價，即有無人-有人機組成的二維持久編隊的信息交互拓撲t具有如下兩個特性。
定理1:無人-有人機組成的二維持久編隊的信息交互拓撲t必須是其編隊通信圖d的一個二維持久圖，但是其編隊通信圖d的一個二維持久圖並不一定能作為其信息交互拓撲。
定理2:無人-有人機組成的二維持久編隊的信息交互拓撲t必須是其編隊通信圖d的一個二維持久圖，並且t存在一個入度為0的節點所對應的飛機能夠作為編隊領航者(即為有人機)；反之亦然。
s2、當所述無人-有人機編隊發生通信故障時，根據所述通信故障的類型在所述編隊通信圖中刪除通信故障弧或通信故障節點以獲取第一重構編隊通信圖。
實際應用中，通信故障發生之後，對無人-有人機編隊的信息交互拓撲的容錯優化應儘量是分布式的以獲得更短的執行時間，並且所有plane的計算結果必須保持一致，因此所有plane必須及時地獲知到同樣的通信故障信息。為此，基於現有技術中的方法，假設每個plane都能使用一個廣播通信信道(broadcastcommunicationchannel，bc)來獲得同樣的通信故障信息：(1)每個plane都有一個單播發射機(unicasttransmitter)和一個單播接收機(unicastreceiver)以進行點對點通信，每個plane都有一個廣播發射機(broadcasttransmitter)和一個廣播接收機(broadcastreceiver)以通過bc進行廣播通信。(2)每個plane每隔tactive秒會通過bc上報其狀態。(3)當一個plane檢測到某個通信故障時，它會立即通過bc通知其他plane。
除了現有技術中考慮的四種通信故障外，還考慮另外兩種通信故障：廣播發射機故障(broadcasttransmitterfailure)和廣播接收機故障(broadcastreceiverfailure)。所有六種通信故障類型如表1所示。
表1
當所述無人-有人機編隊發生通信故障時，本發明實施例採用以下通信故障診斷策略來獲取所述通信故障的類型：
(1)當planei發生單播發射機故障、單播接收機故障、單播收發機故障或者廣播接收機故障中的任何一種通信故障時，planei自身能夠檢測到此通信故障，planei將記錄下此通信故障發生時的時間戳並通過bc將此通信故障和相應的時間戳信息通知其他plane。
(2)當planei發生廣播發射機故障時，planei自身能夠檢測到此通信故障但不能通過bc通知其他plane，tactive秒之後，其他plane由於不能收到planei上報的狀態將判定planei出現了廣播發射機故障，並記錄下此通信故障發生時的時間戳。
(3)當從planei到planej的通信連結出現連結中斷並且編隊保持隊形過程中planei需要發送信息給planej，tactive秒之後，如果planej自身沒有發生單播接收機故障並且沒有通過bc收到planei的單播發射機故障信息，planej將判定從planei到planej的通信連結出現了連結中斷，然後planej將記錄此通信故障的時間戳，然後通過bc將此通信故障和相應的時間戳信息通知其他plane。
基於上述的通信故障診斷策略，每個plane能夠及時地獲得通信故障的信息，然後每個plane可以根據所述通信故障的類型在編隊通信圖中刪除通信故障弧或通信故障節點以獲取第一重構編隊通信圖，具體包括：
若所述通信故障的類型為單播發射機故障，則刪除所述編隊通信圖中對應節點的所有出弧；
若所述通信故障的類型為單播接收機故障，則刪除所述編隊通信圖中對應節點的所有入弧；
若所述通信故障的類型為單播收發機故障、廣播發射機故障或者廣播接收機故障，則刪除所述編隊通信圖中對應節點的所有入弧和出弧以及該節點；
或者，
若通信故障的類型為任意兩飛機之間的連結中斷，則刪除所述編隊通信圖中該連結對應的弧。
s3、根據信息交互拓撲重構算法獲取所述第一重構編隊通信圖對應的第一最優重構信息交互拓撲。
為此，本發明實施例中採用一種基於二維最優剛性圖和最小樹形圖(two-dimensionaloptimalrigidgraphandminimumcostarborescence，2dorg_mca)的無人-有人機編隊信息交互拓撲重構算法來獲取所述第一重構編隊通信圖對應的第一最優重構信息交互拓撲。當通信故障發生時每個plane將會執行此算法。以planei為例，當planei通過bc從其他plane接收到一個通信故障通知或者檢測到自身發生通信故障時，它就會運行此算法以得到第一最優重構信息交互拓撲tr。當每個plane執行此算法後，將切換到tr以確保plane的安全並快速恢復編隊隊形。此算法的基本步驟如表2所示。
表2
需要說明的是，表2所提供算法的step2中使用的現有技術中的二維最優剛性圖生成算法，其基本步驟如表3所示，時間複雜度約為o(4×|v|4)。
表3
同時需要說明的是，表2所提供算法的step5和step7中的最小樹形圖(minimumcostarborescence，mca)指的是一個賦權有向圖的最小生成樹，此處使用的是gabow等人提出的最小樹形圖生成算法，其計算複雜度為o(|a|+|v|×log|v|)，其中的|a|和|v|分別為賦權有向圖中弧的數量和節點的數量。
表2所提供算法的時間複雜度主要由step2、step5和step7決定，由於step2的時間複雜度約為o(4×|vr|4)，step5和step7的時間複雜度都約為o(|ar|+|vr|×log|vr|)，所以表2所提供算法的時間複雜度約為o(4×|vr|4+2×(|ar|+|vr|×log|vr|))。
s4、根據所述第一最優重構信息交互拓撲、無人-有人機編隊的每個位置配置和所述信息交互拓撲重構算法獲取滿足預設條件n＞|v|！的第二最優重構信息交互拓撲即為所述無人-有人機編隊的重優化信息交互拓撲。
實際應用中，無人-有人機編隊的飛行速度比較快，首先應該保證該無人-有人機編隊中的飛機之間不發生碰撞事故以保證所有飛機的安全。因此，當有飛機發生通信故障時，該無人-有人機編隊以步驟s4的第一最優重構信息交互拓撲進行飛行。
可理解的是，上述第一最優重構信息交互拓撲可以保證無人-有人機編隊安全飛行，但是此時無法保證無人-有人機編隊的編隊通信代價最小。
為此，本發明實施例提供了一種基於plane位置交換(交換飛機在編隊隊形中的位置或者令某個飛機去填補另外一個退出編隊的飛機所留下的空位)的無人-有人機信息交互拓撲重優化算法，該算法的思路包括：
首先針對每個plane位置配置pn，構建對應滿足「故障約束」的重構編隊通信圖dn。然後求解dn中滿足如下「編隊領航者約束」的二維最優持久圖tn：tn中存在一個入度為0的節點，並且此節點所代表的plane能夠作為編隊領航者，即有人機。最後從所有tn中選擇出編隊通信代價最小的to作為此編隊的重優化信息交互拓撲。
該信息交互拓撲重優化算法的基本步驟如表4所示。
表4
表4所示算法的step3中，每種可行的plane位置配置pn一定是|v|個元素的排列，其中的|v|個元素分別代表編隊隊形中的不同位置，分別是1、2、…、|v|。因此，所有可行的pn的總數是|v|！(符號！表示階乘)。表4所示算法的step6中，plane位置交換所需要的某個plane的移動距離是該plane在編隊隊形中的原有位置和新位置之間的歐式距離。
表4所示算法的核心步驟是step4，而step4的具體步驟和表2所示算法相同，所以表4所示算法的step4的時間複雜度約為o(4×|vr|4+2×(|ar|+|vr|×log|vr|))。同時，從表4中step2可以看出，step4最多會運行|v|！次。因此，表4所示算法的時間複雜度約為o((4×|vr|4+2×(|ar|+|vr|×log|vr|))×|v|！)。又由於|vr|≤|v|和|ar|≤|v|×(|v|-1)，所以表4所示算法的時間複雜度的上界為o((4×|v|4+2×(|v|2-|v|+|v|×log|v|))×|v|！)。
假設一個二維持久編隊由3架無人機(uav1、uav2、uav3)和2架有人機(fighter1、fighter2)組成，其中只有有人機fighter1和fighter2可以作為編隊的領航者。它們需要形成並保持一個如圖2(a)所示的二維空間隊形，其中的所有位置分別編號為{1,2,3,4,5}，其中，fighter1和fighter2分別在隊形的1號和2號位置，uav1、uav2和uav3分別在隊形的3號、4號和5號位置；它們之間的距離如圖2(a)所示；如果以隊形中的4號位置作為平面坐標系的原點，則該無人-有人機編隊的隊形中的每個位置的坐標如圖2(b)所示。當無通信故障時，該無人-有人機編隊使用如圖3所示的最優信息交互拓撲來形成並保持此隊形，其中有人機fighter1作為該無人-有人機編隊的領航者。
當有人機fighter2發生單播發射機故障時，導致編隊之前使用的信息交互拓撲(如圖3所示)中的通信連結a23(從fighter2到uav1的通信連結)、a24(從fighter2到uav2的通信連結)和a25(從fighter2到uav3的通信連結)不能再被使用。因此，首先刪除當前編隊通信圖d＝(v,a,w,p)中v2的所有出弧得到第一重構編隊通信圖dr＝(vr,ar,wr,pr)；然後根據表2提供的信息交互拓撲重構算法獲取所述第一重構編隊通信圖對應的第一最優重構信息交互拓撲，得到的第一最優重構信息交互拓撲如圖4(a)所示，fighter2不再使用通信連結a23、a24和a25發送信息，而只使用通信連結a32(從uav1到fighter2的通信連結)和a42(從uav2到fighter2的通信連結)接收信息，對應的編隊通信代價為5588；再根據表4提供的信息交互拓撲重優化算法獲取此無人-有人機編隊的重優化信息交互拓撲，得到的重優化信息交互拓撲如圖4(b)所示，其中fighter2和uav2在編隊隊形中的位置進行了交換，編隊通信代價從之前的5588降低為4912。
第二方面，本發明實施例還提供了一種無人-有人機編隊信息交互拓撲容錯優化裝置，如圖5所示，所述裝置包括：
編隊通信圖獲取模塊m1，用於根據無人-有人機編隊需要組成的二維持久編隊的隊形獲取編隊通信圖；
第一重構編隊通信圖獲取模塊m2，用於在所述無人-有人機編隊發生通信故障時，根據所述通信故障的類型在所述編隊通信圖中刪除通信故障弧或通信故障節點以獲取第一重構編隊通信圖；
第一最優重構信息交互拓撲獲取模塊m3，用於根據信息交互拓撲重構算法獲取所述第一重構編隊通信圖對應的第一最優重構信息交互拓撲；
重優化信息交互拓撲獲取模塊m4，用於根據所述第一最優重構信息交互拓撲、無人-有人機編隊的每個位置配置和所述信息交互拓撲重構算法獲取滿足預設條件n＞|v|！的第二最優重構信息交互拓撲即為所述無人-有人機編隊的重優化信息交互拓撲；
所述位置配置是指無人-有人機編隊中各架飛機在編隊隊形中的位置；通信故障發生之前的位置配置為第一位置配置pr；|v|表示無人-有人機編隊中飛機的數量；n取1、2、……、|v|！。
可選地，所述重優化信息交互拓撲獲取模塊m4執行以下步驟獲取重優化信息交互拓撲包括：
s41、將所述重優化信息交互拓撲to初始化為所述第一最優重構信息交互拓撲tr，將重優化位置配置po初始化為所述第一位置配置pr；第二最優重構通信拓對應的位置配置為第二位置配置pn，並將符號n初始化為1；
s42、根據第二位置配置pn構建滿足故障約束條件的第二重構編隊通信圖；
s43、根據所述第二重構編隊通信圖和所述信息交互拓撲重構算法計算出所述第二位置配置pn對應的第二最優重構信息交互拓撲tn；
s44、計算所述第二最優重構信息交互拓撲tn的權重值，若該權重值小於所述重優化信息交互拓撲to的權重值，則將所述重優化信息交互拓撲to更新為所述第二最優重構信息交互拓撲tn，將所述重優化位置配置po更新為所述第二位置配置pn；
s45、若該權重值等於所述重優化信息交互拓撲的權重值，則計算從第一位置配置pr切換到所述第二位置配置pn的plane移動距離之和，若該plane移動距離之和小於從第一位置配置pr切換到所述重優化位置配置po的plane移動距離之和，則將重優化信息交互拓撲to更新為所述第二最優重構信息交互拓撲tn，將重優化位置配置po更新為所述第二位置配置pn；
s46、將所述符號n的值增加1，判斷n是否滿足預設條件n＞|v|！，若不滿足轉到步驟s42。
可選地，所述第一重構編隊通信圖獲取模塊m2執行以下步驟獲取第一重構編隊通信圖包括：
若所述通信故障的類型為單播發射機故障，則刪除所述編隊通信圖中對應節點的所有出弧；
若所述通信故障的類型為單播接收機故障，則刪除所述編隊通信圖中對應節點的所有入弧；
若所述通信故障的類型為單播收發機故障、廣播發射機故障或者廣播接收機故障，則刪除所述編隊通信圖中對應節點的所有入弧和出弧以及該節點；
或者，
若通信故障的類型為任意兩飛機之間的連結中斷，則刪除所述編隊通信圖中該連結對應的弧；
在所述編隊通信圖中，若某個無人機的對應節點被刪除或該節點的所有弧被刪除，則所述無人機退出編隊並獨自返回機場；若某個有人機的對應節點被刪除或該節點的所有弧被刪除，則所述有人機退出編隊並在一個不同的飛行高度上跟隨編隊參考航跡飛行。
可選地，所述第一最優重構信息交互拓撲獲取模塊m3執行以下步驟獲取第一最優重構信息交互拓撲包括：
獲取所述第一重構編隊通信圖的二維最優持久圖；
若存在一個有人機在所述二維最優持久圖中對應節點的入度為0，則所述二維最優持久圖即為第一最優重構信息交互拓撲；
否則，通過弧反向操作對所述二維最優持久圖中進行調整，調整後的二維最優持久圖即為第一最優重構信息交互拓撲。
可選地，所述第一最優重構信息交互拓撲獲取模塊m3執行以下步驟獲取所述第一重構編隊通信圖的二維最優持久圖包括：
計算所述第一重構編隊通信圖的二維最優剛性圖；
將所述二維最優剛性圖中每條邊轉換成屬於所述第一重構編隊通信圖的一條弧或者兩條權值相同但方向相反的弧得到第一有向圖；
在所述第一有向圖中增加一個虛擬領航者節點和所述虛擬領航者節點到每個飛機對應節點的出弧得到第二有向圖；
根據所述第二有向圖計算其第一最小樹形圖，並將所述第一最小樹形圖中的虛擬領航者節點和其出弧刪除得到第三有向圖；
從所述第二有向圖中刪除所述第三有向圖中的所有弧及其對應的反向弧得到第四有向圖；
根據所述第四有向圖計算其第二最小樹形圖，並將所述第二最小樹形圖中的虛擬領航者節點和其出弧刪除得到第五有向圖；
合併所述第三有向圖和所述第五有向圖得到第六有向圖及其弧的數量m；
當所述二維最優剛性圖的節點數量為n且m滿足m＝2n-3時，則所述第六有向圖為二維最優持久圖；
當所述二維最優剛性圖的節點數量為n且m滿足m<(2n-3)時，獲取所述二維最優剛性圖中的第l條邊對應的屬於所述第一有向圖中弧集合的一條或者兩條弧，符號l的初始值為1；
若該一條或者兩條弧都不在所述第六有向圖中，獲取第l條邊對應兩節點的入度；
若該第l條邊對應的兩節點的入度不都等於2且其中一個入度小於2的節點的入弧屬於所述第一有向圖中弧集合，則將該入度小於2的節點的入弧添加到所述第六有向圖中得到第七有向圖；
若所述第七有向圖中弧的數量等於(2n-3)，則所述第七有向圖為二維最優持久圖；否則將所述第六有向圖中的數據更新為所述第七有向圖中的數據；
若該第l條邊對應的兩節點的入度都等於2且該第l條邊對應的一條弧屬於所述第一有向圖中弧集合，將該第l條邊對應的一條弧添加到第六有向圖中得到第七有向圖，記該弧指向的節點為第一節點；
在所述第六有向圖中尋找入度小於2的一個第二節點，使得所述第二節點與所述第一節點之間具有最少跳數的路徑，並且所述最少跳數的路徑對應的所有弧的反向弧都在所述第一有向圖中弧集合中，將所述最少跳數的路徑對應的所有弧反向得到第八有向圖；否則從所述第七有向圖中刪除已添加的該第l條邊對應的一條弧，從優化編隊通信圖中刪除該第l條邊對應的兩條弧，重新計算；
若所述第八有向圖中弧的數量m等於(2n-3)時，則所述第八有向圖為二維最優持久圖；否則將所述第六有向圖中的數據更新為所述第八有向圖中的數據；
將所述符號l的值增加1，若符號l小於等於(2n-3)時，則繼續判斷第l條邊對應的一條或兩條弧是否都不在所述第六有向圖中。
需要說明的是，本發明實施例提供的無人-有人機編隊信息交互拓撲容錯優化裝置與上述方法是一一對應的關係，上述方法的實施細節同樣適用於上述裝置，本發明實施例不再對上述系統進行詳細說明。
本發明的各個部件實施例可以以硬體實現，或者以在一個或者多個處理器上運行的軟體模塊實現，或者以它們的組合實現。本領域的技術人員應當理解，可以在實踐中使用微處理器或者數位訊號處理器(dsp)來實現根據本發明實施例的一種瀏覽器終端的設備中的一些或者全部部件的一些或者全部功能。本發明還可以實現為用於執行這裡所描述的方法的一部分或者全部的設備或者裝置程序(例如，電腦程式和電腦程式產品)。這樣的實現本發明的程序可以存儲在計算機可讀介質上，或者可以具有一個或者多個信號的形式。這樣的信號可以從網際網路網站上下載得到，或者在載體信號上提供，或者以任何其餘形式提供。
應該注意的是上述實施例對本發明進行說明而不是對本發明進行限制，並且本領域技術人員在不脫離所附權利要求的範圍的情況下可設計出替換實施例。在權利要求中，不應將位於括號之間的任何參考符號構造成對權利要求的限制。單詞「包含」不排除存在未列在權利要求中的元件或步驟。位於元件之前的單詞「一」或「一個」不排除存在多個這樣的元件。本發明可以藉助於包括有若干不同元件的硬體以及藉助於適當編程的計算機來實現。在列舉了若干裝置的單元權利要求中，這些裝置中的若干個可以是通過同一個硬體項來具體體現。單詞第一、第二、以及第三等的使用不表示任何順序。可將這些單詞解釋為名稱。
最後應說明的是：以上各實施例僅用以說明本發明的技術方案，而非對其限制；儘管參照前述各實施例對本發明進行了詳細的說明，本領域的普通技術人員應當理解：其依然可以對前述各實施例所記載的技術方案進行修改，或者對其中部分或者全部技術特徵進行等同替換；而這些修改或者替換，並不使相應技術方案的本質脫離本發明各實施例技術方案的範圍，其均應涵蓋在本發明的權利要求和說明書的範圍當中。