雙向通信無(wú)人機(jī)集群領(lǐng)航頂點(diǎn)選取方法

戴麗

（國(guó)防科技大學(xué) 文理學(xué)院，湖南 長(zhǎng)沙 410073）

多智能體系統(tǒng)控制技術(shù)是人工智能時(shí)代的研究熱點(diǎn)之一[1]，其成果可用于多個(gè)領(lǐng)域，如智能交通、機(jī)器人編隊(duì)，甚至是軍事用途，如無(wú)人機(jī)蜂(狼)群作戰(zhàn)等。無(wú)人機(jī)集群作為一種特殊的多智能體系統(tǒng)，個(gè)體無(wú)需全局通信，僅通過(guò)對(duì)其周?chē)欢ǚ秶鷥?nèi)個(gè)體間的通信、合作和協(xié)調(diào)等就可以表達(dá)集群整體結(jié)構(gòu)和功能。它在自組織能力、推理能力，以及對(duì)未知環(huán)境的適應(yīng)性等方面有很多潛在應(yīng)用。

無(wú)論是地面起飛式無(wú)人機(jī)集群，還是空投式無(wú)人機(jī)集群，其控制技術(shù)的難點(diǎn)都在于隊(duì)形控制，核心在于解決可行性和有效性?xún)蓚€(gè)問(wèn)題[2]：可行性是研究無(wú)人機(jī)集群能不能全局可控，使之形成所有預(yù)定隊(duì)形；有效性則回答了最少需要輸入多少信號(hào)，才能達(dá)到全局可控。最小領(lǐng)航集選取與這2個(gè)問(wèn)題密切相關(guān)。

對(duì)于通信網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)圖為有向圖的領(lǐng)航跟隨網(wǎng)絡(luò)系統(tǒng)，文獻(xiàn)[3]通過(guò)引進(jìn)匹配概念，使有向網(wǎng)絡(luò)的可控性問(wèn)題已得到較好解決。但是，對(duì)于無(wú)向領(lǐng)航跟隨網(wǎng)絡(luò)系統(tǒng)控制而言，正如Kumar等[4]于2019年所指出的那樣：如何選取領(lǐng)航頂點(diǎn)、如何選取最少個(gè)數(shù)的領(lǐng)航頂點(diǎn)都是尚待解決的難題。

目前，無(wú)向網(wǎng)絡(luò)控制技術(shù)已經(jīng)引起人們的廣泛關(guān)注。文獻(xiàn)[5]是一篇較早關(guān)注無(wú)向網(wǎng)絡(luò)可控性的文章，該文通過(guò)Kalman秩條件給出了無(wú)向網(wǎng)絡(luò)可控的充要條件。研究無(wú)向網(wǎng)絡(luò)領(lǐng)航集常用的圖結(jié)構(gòu)有：強(qiáng)制零點(diǎn)集(zero forcing set, ZFS)[4,6-8]、約束匹配(constraint matching, CM)[8-11]和非平凡等價(jià)劃分(nontrivial equitable partition，NEP)[12-15]等。已有的研究成果表明無(wú)向網(wǎng)絡(luò)可控當(dāng)且僅當(dāng)領(lǐng)航集是推廣的ZFS，且Shima等[8,10]發(fā)現(xiàn)了網(wǎng)絡(luò)中ZFS與CM之間具有等價(jià)關(guān)系?；贜EP概念人們給出了網(wǎng)絡(luò)可控的必要條件，同時(shí)也證明了網(wǎng)絡(luò)可控當(dāng)且僅當(dāng)它的每個(gè)連通分支可控。

Ji等[16-17]則是通過(guò)Laplace矩陣的特征向量研究無(wú)向網(wǎng)絡(luò)的可控性，其中文獻(xiàn)[16]給出了無(wú)向網(wǎng)絡(luò)可控的充要條件，文獻(xiàn)[17]則給出DCD、TCD等破壞網(wǎng)絡(luò)可控性的頂點(diǎn)集圖特征。文獻(xiàn)[18-19]證明了高階時(shí)不變系統(tǒng)的可控性等價(jià)于一階(線(xiàn)性)時(shí)不變系統(tǒng)的可控性，通過(guò)Laplace矩陣的特征向量給出了無(wú)向網(wǎng)絡(luò)可控的充要條件，同時(shí)指出了使網(wǎng)絡(luò)可控的2個(gè)方法：增加領(lǐng)航頂點(diǎn)和修改網(wǎng)絡(luò)權(quán)值。

這些研究關(guān)注重點(diǎn)在于從理論上給出領(lǐng)航集的代數(shù)特征或圖論特征，所舉算例規(guī)模較小。對(duì)于僅具有單特征值的無(wú)向網(wǎng)絡(luò)系統(tǒng)，可以從代數(shù)角度給出領(lǐng)航集。理論研究表明，當(dāng)網(wǎng)絡(luò)中個(gè)體數(shù)量趨向無(wú)窮時(shí)，網(wǎng)絡(luò)Laplace矩陣僅具有單特征值的概率趨向1。但是，對(duì)于無(wú)人機(jī)集群系統(tǒng)，個(gè)體數(shù)量大多在幾十至幾百之間，這類(lèi)系統(tǒng)的Laplace矩陣具有多重特征值的可能性很大?，F(xiàn)有的研究很少涉及求解這種規(guī)模無(wú)向網(wǎng)絡(luò)領(lǐng)航集的算法。

復(fù)雜網(wǎng)絡(luò)的相關(guān)研究值得借鑒。Hamdan等[20-21]采用啟發(fā)式算法求復(fù)雜網(wǎng)絡(luò)的領(lǐng)航集，之所以采用啟發(fā)式算法求領(lǐng)航集是因?yàn)檫@一問(wèn)題是NP難問(wèn)題。在無(wú)向復(fù)雜網(wǎng)絡(luò)的可控性研究中，多采用攜帶更多信息的可控性Gramian矩陣[22-23]。Katherine等[24]研究了平均可控性以及可控性與魯棒性的關(guān)系，并給出使樹(shù)圖可控的領(lǐng)航集選取方法。2020年，基于頂點(diǎn)分類(lèi)文獻(xiàn)[25]提出大規(guī)模動(dòng)態(tài)系統(tǒng)的最小領(lǐng)航頂點(diǎn)選取問(wèn)題的算法。

本文針對(duì)具有幾十個(gè)個(gè)體的無(wú)向領(lǐng)航跟隨模式無(wú)人機(jī)集群領(lǐng)航頂點(diǎn)選取問(wèn)題，研究領(lǐng)航頂點(diǎn)的圖特征，解決具有何種圖特征的頂點(diǎn)必須成為領(lǐng)航頂點(diǎn)，以及如何求出最小領(lǐng)航集這2個(gè)問(wèn)題；給出求領(lǐng)航集的算法并用數(shù)值仿真實(shí)驗(yàn)驗(yàn)證算法的有效性，分析無(wú)人機(jī)集群領(lǐng)航集的數(shù)值特征。

1 基本理論

1.1 無(wú)人機(jī)集群通信網(wǎng)絡(luò)的圖論模型

無(wú)人機(jī)個(gè)體間的通信關(guān)系可用圖表示。設(shè)圖G=(V,E) ，其中頂點(diǎn)集V={v1,v2,···,vn}，vi表示第i個(gè)無(wú)人機(jī)個(gè)體，邊vi,vj∈E當(dāng)且僅當(dāng)?shù)趇個(gè)無(wú)人機(jī)與第j個(gè)無(wú)人機(jī)間可通信，G稱(chēng)為通信網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)圖。若無(wú)人機(jī)個(gè)體間的通信關(guān)系是單向的，則G為有向圖；若無(wú)人機(jī)個(gè)體間是雙向通信的，則G為無(wú)向網(wǎng)絡(luò)。

對(duì)于領(lǐng)航跟隨模式的無(wú)人機(jī)集群，接收外界輸入控制信號(hào)的個(gè)體稱(chēng)為領(lǐng)航頂點(diǎn)，其余頂點(diǎn)則稱(chēng)為跟隨頂點(diǎn)。本文考慮有n個(gè)無(wú)人機(jī)個(gè)體的線(xiàn)性時(shí)不變系統(tǒng)，個(gè)體的動(dòng)力學(xué)方程描述為

式中：xi為第i個(gè)無(wú)人機(jī)的狀態(tài)信息；ui為外界輸入控制信息。如圖1，由Kalman秩條件[5]知，取v1或v3作為領(lǐng)航頂點(diǎn)，則系統(tǒng)可控；若取v2作為領(lǐng)航頂點(diǎn)，則系統(tǒng)不可控。

圖1 領(lǐng)航集的選取對(duì)系統(tǒng)可控性影響Fig.1 Influence of leader’s selection on the controllability of the systems

1.2 預(yù)備理論

研究結(jié)果表明，無(wú)向網(wǎng)絡(luò)可控性與Laplace矩陣L的特征值和特征向量有關(guān)。

性質(zhì)1[16-18]設(shè)F為跟隨集，則無(wú)向網(wǎng)絡(luò)線(xiàn)性時(shí)不變系統(tǒng)式(1)可控，當(dāng)且僅當(dāng)L與LF→F沒(méi)有共同特征值。

性質(zhì)2給出領(lǐng)航集的代數(shù)特征。值得注意的是，性質(zhì)2中的特征向量y是Laplace矩陣L的任意一個(gè)特征向量，因此，當(dāng)L有多重特征值時(shí)，并不能僅通過(guò)考察它的所有線(xiàn)性無(wú)關(guān)的特征向量得到領(lǐng)航集，而應(yīng)進(jìn)一步驗(yàn)證全部具有零分量的特征向量。從數(shù)值計(jì)算角度而言，這種驗(yàn)證計(jì)算量大，難以實(shí)現(xiàn)。本文將從領(lǐng)航頂點(diǎn)的圖特征出發(fā)，給出確保系統(tǒng)可控的領(lǐng)航集求解算法。

2 關(guān)鍵集和完美關(guān)鍵集

由性質(zhì)2可知，對(duì)于非空頂點(diǎn)集T，若通信網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)圖G的Laplace矩陣L有一個(gè)特征向量y使得yT=0 ， 則該頂點(diǎn)集T不能作為領(lǐng)航集，也就是說(shuō)，此時(shí)為使無(wú)人機(jī)集群可控，必須將T的補(bǔ)集中某些頂點(diǎn)加入到領(lǐng)航集?；诖?，本文提出關(guān)鍵集的概念。

2.1 關(guān)鍵集

定義1 關(guān)鍵集。設(shè)非空頂點(diǎn)集S?V，L為通信網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)圖G的Laplace矩陣，若存在L的一個(gè)特征向量y使得ySˉ=0，則稱(chēng)頂點(diǎn)集S為關(guān)鍵集(critical set, CS)。若 |S|=k，則稱(chēng)S為k關(guān)鍵集(kcritical set)。

定義2 完美關(guān)鍵集。設(shè)S為關(guān)鍵集，若存在L的一個(gè)特征向量y使得yv≠0(?v∈S)，則稱(chēng)S為完美關(guān)鍵集(perfect critical set, PCS)。若 |S|=k，則稱(chēng)S為k完美關(guān)鍵集(kperfect critical set)。

定義3 最小完美關(guān)鍵集。設(shè)S為關(guān)鍵集，若它的任何真子集都不再是關(guān)鍵集，則稱(chēng)S為最小完美關(guān)鍵集(minimal perfect critical set, MPCS)。若 |S|=k，則稱(chēng)S為k最小完美關(guān)鍵集(kminimal perfect critical set)。

由k關(guān)鍵集的定義可知，k為正整數(shù)且k

定理1n階連通無(wú)向網(wǎng)絡(luò)不存在1關(guān)鍵集。

若S為1關(guān)鍵集，不防設(shè)S={v1}， 則由ysˉ=0 及式(2)可知yS=0， 于是y=0 與y為特征向量矛盾。

由性質(zhì)2及定理1知推論1、2成立。

推論1 設(shè)G為n階連通無(wú)向網(wǎng)絡(luò)，S?V且|S|=n?1，若取S為領(lǐng)航集，則系統(tǒng)可控。

推論2 設(shè)n階無(wú)向網(wǎng)絡(luò)G為非連通圖，則G有1關(guān)鍵集的充要條件是G中有孤立頂點(diǎn)。

由定理1可知，對(duì)于n階連通無(wú)向網(wǎng)絡(luò)的k關(guān)鍵集，必有 2 ≤k≤n?1。

定理2 設(shè)頂點(diǎn)集S?V且 |S|≥2 ，若 ?v∈Sˉ，v要么與S中所有頂點(diǎn)都相鄰，要么與S中所有頂點(diǎn)都不相鄰，則S為關(guān)鍵集。

情況1 若矩陣LS→S?mI|S|只有零特征值。

此 時(shí) 必 有LS→S?mI|S|=0|S|×|S|。 注 意 到 ?v∈Sˉ ，若v與S中頂點(diǎn)都相鄰，則其在矩陣LSˉ→S中對(duì)應(yīng)的行向量Lv→S分量全為1；若v與S中頂點(diǎn)都不相鄰，則其對(duì)應(yīng)的行向量Lv→S分量全為0。 因此，構(gòu)造n階列向量y=[1?|S|1···10···0]，則易見(jiàn)y為L(zhǎng)aplace矩陣L的特征向量。

情況2 若矩陣LS→S?mI|S|有非零特征值。

此 時(shí) 取LS→S?mI|S|的 特 征 值 λ′≠0，令λ=λ′+m，則λ 為L(zhǎng)S→S的特征值且λ ≠m。

設(shè)yS為矩陣LS→S相應(yīng)于特征值 λ (λ≠m) 的特征向量，構(gòu)造n階列向量y=[yS0]，則有

由LS→SyS=λyS知

由定理2可知圖1中的頂點(diǎn)集 {v1,v3} 是關(guān)鍵集，所以v2不能作為領(lǐng)航頂點(diǎn)。

在一定條件下，運(yùn)用定理2判斷一個(gè)頂點(diǎn)子集S是否為關(guān)鍵集時(shí)，可以不考慮Sˉ 中那些與S中頂點(diǎn)都相鄰或者都不相鄰的頂點(diǎn)。

設(shè)特征向量y是與k完美關(guān)鍵集S對(duì)應(yīng)的特征向量，即ySˉ=0 且y的非零分量恰有k個(gè)，于是有引理1。設(shè) [ {v},S] 表示一個(gè)端點(diǎn)為v另一個(gè)端點(diǎn)屬于S的邊集。

引理1 設(shè)S為k完美關(guān)鍵頂點(diǎn)集，則?v∈Sˉ ，有 |[ {v},S]|≠1 且 |[ {v},S]|≠k?1。

證明 設(shè)S={v1,v2,···,vk} 為k完美關(guān)鍵集，存在y=[y1y2···yk0 ···0]T為L(zhǎng)aplace矩陣L的特征向量。由S為k完美關(guān)鍵集知yi≠0(i=1,2,···,k)。

再由式(2)知yk=0, 矛盾。

2.2 2關(guān)鍵集和3關(guān)鍵集的圖特性

由定理1知，2關(guān)鍵集是2完美關(guān)鍵集，也是2最小完美關(guān)鍵集。

證明 由定理2知充分性成立。只須證明必要性。

證明 由定理2知充分性成立。只須證明必要性。

由定理3可知，2關(guān)鍵集實(shí)際上就是文獻(xiàn)[26]給出的twins頂點(diǎn)對(duì)，由此可見(jiàn)，2關(guān)鍵集是twins頂點(diǎn)對(duì)的推廣。但與文獻(xiàn)[17]中所提出的DCD頂點(diǎn)對(duì)不同，DCD頂點(diǎn)對(duì)考慮的是在跟隨集中的2個(gè)頂點(diǎn)，而2關(guān)鍵集考慮的對(duì)象則是所有頂點(diǎn)。

另外，定理3和定理4表明頂點(diǎn)集S能否成為2關(guān)鍵集或3關(guān)鍵集與S中的頂點(diǎn)是否相鄰無(wú)關(guān)。但是，當(dāng)S中頂點(diǎn)數(shù)更多時(shí)，該結(jié)論不一定成立。如圖2中4個(gè)深色頂點(diǎn)構(gòu)成的頂點(diǎn)集S，當(dāng)S中頂點(diǎn)的相鄰關(guān)系如圖(a)時(shí)，它是4關(guān)鍵集；但當(dāng)S中頂點(diǎn)的相鄰關(guān)系如圖(b)時(shí)，它不再是4關(guān)鍵集。

圖2 4關(guān)鍵集與G[S]的關(guān)系Fig.2 Relationship between four critical set an G[S]

2.3 獨(dú)立關(guān)鍵集的圖特征

若S={v1,v2,···,vk} 為獨(dú)立集且為k完美關(guān)鍵集，則Laplace矩陣L有一個(gè)特征向量：

y=[y1y2···yk0 ··· 0]T

yi≠0,i=1,2,···,k

由S為獨(dú)立集知 ?vi∈S有：

即dG(v1)=dG(v2)=···=dG(vk)=λ。亦即當(dāng)S為獨(dú)立集時(shí)，完美關(guān)鍵集S中頂點(diǎn)度均相等?；诖?，定理5給出了獨(dú)立集成為關(guān)鍵集的一個(gè)充分條件。

證明 不防設(shè)S={v1,v2,···,vk} 且S中所有頂點(diǎn)在圖G中的度均為d。若簡(jiǎn)化圖GS為空?qǐng)D，則由定理2知結(jié)論成立，下設(shè)GS非空?qǐng)D。

取y=[x1x2···xk0 ···0]T， λ=d，則有

綜上可知Ly=λy， 即向量y為L(zhǎng)aplace矩陣的特征向量，由于ySˉ=0，故由定義1知S為關(guān)鍵集。

圖3 簡(jiǎn)化圖及其關(guān)鍵集Fig.3 Simplification of graph G and its CS

3 最小領(lǐng)航集

基于關(guān)鍵集的概念，本節(jié)討論如何求出無(wú)人機(jī)集群最小領(lǐng)航集的算法。

3.1 算法理論基礎(chǔ)

由性質(zhì)2及關(guān)鍵集的定義知定理6成立。

定理6 設(shè)F為跟隨集，F(xiàn)為領(lǐng)航集，則雙向通信無(wú)人機(jī)集群線(xiàn)性時(shí)不變系統(tǒng)(見(jiàn)式(1))可控當(dāng)且僅當(dāng)F中不包含關(guān)鍵集。

證明 由性質(zhì)2知系統(tǒng)(見(jiàn)式(1))可控當(dāng)且僅當(dāng)yFˉ≠0 ，其中y是任意一個(gè)特征向量。由定義1知，yFˉ≠0 當(dāng)且僅當(dāng)F不是關(guān)鍵集且不包含任何關(guān)鍵集。

設(shè)S1,S2,···,Sm是無(wú)人機(jī)集群通信網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)圖的所有關(guān)鍵集，構(gòu)造二部圖H=(U,V;E)，頂點(diǎn)集U={u1,u2,···,um} ，其中ui與Si對(duì)應(yīng)；V=V(G)={v1,v2,···,vn}為無(wú)人機(jī)集群通信網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)圖G的頂點(diǎn)集，viuj∈E(H) 當(dāng)且僅當(dāng)vi∈Sj。若viuj∈E(H) 則稱(chēng)頂點(diǎn)vi覆蓋關(guān)鍵集Sj。由定理6可知求最小領(lǐng)航集等價(jià)于求覆蓋所有關(guān)鍵集的最小頂點(diǎn)集T(T?V)。

3.2 最小領(lǐng)航集算法

基于定理6，本節(jié)給出求領(lǐng)航集的算法(critical set algorithm, CSA)：

1)求出無(wú)人機(jī)集群通信網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)圖G的所有k關(guān)鍵集Si(i=1,2,···,m)；

2)構(gòu)造二部圖H=(U,V;E)；

3)求最小頂點(diǎn)集T(T?V) 使T中的頂點(diǎn)覆蓋所有關(guān)鍵集，則T即為最小領(lǐng)航集。

例如，圖4中G來(lái)自文獻(xiàn)[15]，由定理3知它有2關(guān)鍵集S1={v1,v6} 、S2={v2,v3} 、S3={v4,v5}、S4={v7,v8}；由定理4知該圖沒(méi)有3關(guān)鍵集；由于2個(gè)懸掛點(diǎn)v4、v5都與v9相鄰，故由引理1知v9不屬于任何完美關(guān)鍵集；同理，考慮v1和v6這2個(gè)頂點(diǎn)可知v10也不屬于任何關(guān)鍵集。從而，容易知道圖4中不存在5完美關(guān)鍵集；對(duì)于4完美關(guān)鍵集只能是上述4個(gè)Si(i=1,2,3,4) 中每個(gè)集合各取一個(gè)構(gòu)成的集合，容易驗(yàn)證它們都不是關(guān)鍵集。即上述4個(gè)Si(i=1,2,3,4) 是該網(wǎng)絡(luò)的全部最小完美關(guān)鍵集。

圖4 圖G及其關(guān)鍵集Fig.4 Graph G it’s critical set

于是可構(gòu)造二部圖H=(U,V;E) 如圖5所示。從該二部圖中可以看出每個(gè)頂點(diǎn)vi只能覆蓋一個(gè)uj，于是從每個(gè)uj的相鄰頂點(diǎn)任取一個(gè)組成的集合就是圖G的最小領(lǐng)航集，比如可取T={v1,v2,v4,v7}為最小領(lǐng)航集。

圖5 二部圖Fig.5 Bipartite graph

本算例說(shuō)明如何運(yùn)用關(guān)鍵集求出無(wú)人機(jī)集群通信網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)圖的最小領(lǐng)航集。

3.3 CSA算法復(fù)雜性分析

一般地，CSA算法的1)和3)都不是多項(xiàng)式時(shí)間的算法。但是，基于本文給出的定理，求出相應(yīng)特殊的關(guān)鍵集及領(lǐng)航集則是多項(xiàng)式時(shí)間算法，具體的算法流程如圖6所示。

圖6 CSA算法流程Fig.6 Flow chart of CSA

由定理3知，在CSA算法流程圖中找出所有2關(guān)鍵集的算法復(fù)雜性為O(n3)。由定理4知，找所有3關(guān)鍵集的算法復(fù)雜性為O(n4)，因此，圖6所示的CSA算法復(fù)雜性為O(n4)。

3.4 數(shù)值實(shí)驗(yàn)及分析

在實(shí)驗(yàn)中，設(shè)無(wú)人機(jī)集群的初始位置隨機(jī)，經(jīng)過(guò)一段時(shí)間后形成穩(wěn)定的通信網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)圖，并在后續(xù)保持通信關(guān)系不變。在具體的數(shù)值實(shí)驗(yàn)中，程序?qū)⒃?1 0×10 平面區(qū)域內(nèi)隨機(jī)生成n個(gè)頂點(diǎn)，代表n個(gè)無(wú)人機(jī)個(gè)體的初始位置，設(shè)無(wú)人機(jī)個(gè)體的通信半徑為參數(shù)d。圖7是實(shí)驗(yàn)中隨機(jī)生成的3個(gè)通信網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)圖G。

圖7 無(wú)人機(jī)集群的通信網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)Fig.7 Topology of communication network for UAVs

其中，圖7(a)是通信半徑為5時(shí)隨機(jī)生成的具有10個(gè)無(wú)人機(jī)個(gè)體的通信網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)圖，CSA算法求出的領(lǐng)航集為 { 1,2,3}；圖7(b)是通信半徑為7時(shí)隨機(jī)生成的具有10個(gè)無(wú)人機(jī)個(gè)體的通信網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)圖，CSA算法求出的領(lǐng)航集為{1,2,3,4,5}；圖7(c)是70個(gè)無(wú)人機(jī)個(gè)體通信半徑為1.5時(shí)生成的通信網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)圖，CSA算法求出的領(lǐng)航集為 { 1,2,···,8}。

實(shí)驗(yàn)1 代數(shù)方法、圖論方法及CSA算法的對(duì)比實(shí)驗(yàn)。

在代數(shù)方法中，首先對(duì)于單重特征值，先求它的1個(gè)特征向量，若該特征向量的非零分量對(duì)應(yīng)的頂點(diǎn)集不是頂點(diǎn)集V，由定義1知，這些非零分量對(duì)應(yīng)的頂點(diǎn)集是1個(gè)關(guān)鍵集，在該關(guān)鍵集中任取1個(gè)頂點(diǎn)放入領(lǐng)航頂點(diǎn)集；其次，對(duì)于多重特征值，設(shè)它的重?cái)?shù)為m(m≥2)，由于這種特征值對(duì)應(yīng)的特征向量可能具有不同的非零分量集合，因此，這種特征值可能對(duì)應(yīng)多個(gè)不同的MPCS，程序?qū)哂邢嗤橇惴至康奶卣飨蛄窟M(jìn)行識(shí)別并重新認(rèn)定該特征值的重?cái)?shù)m1(m1≤m)。在特征向量的非零分量中任取m1個(gè)對(duì)應(yīng)頂點(diǎn)放入領(lǐng)航頂點(diǎn)集。

在圖論方法中，程序基于本文給出的定理2～5，求出2關(guān)鍵集、3關(guān)鍵集和孤立關(guān)鍵集等一些特殊的關(guān)鍵集。然后，在每個(gè)關(guān)鍵集中任取一個(gè)頂點(diǎn)放入領(lǐng)航頂點(diǎn)集。

CSA算法則是將代數(shù)方法和圖論方法相結(jié)合求關(guān)鍵集。對(duì)于單重特征值，程序用代數(shù)方法求它的關(guān)鍵集；對(duì)于多重特征值，則用圖論方法求出2關(guān)鍵集、3關(guān)鍵集。實(shí)驗(yàn)結(jié)果如圖8所示。

從圖8中可以看出，通過(guò)引入圖論理論求關(guān)鍵集，使得求解效率得到大幅度提高，特別是當(dāng)通信半徑d=1 時(shí)，單純的代數(shù)方法或圖論方法都難以搜索到領(lǐng)航集，但將兩者相結(jié)合的CSA算法仍然使得求解效率在80%以上。實(shí)驗(yàn)表明，代數(shù)方法能找到一部分領(lǐng)航頂點(diǎn)，而圖論方法則可以找出另一部分領(lǐng)航頂點(diǎn)，CSA正是借助關(guān)鍵集概念，將代數(shù)方法和圖論方法統(tǒng)一用于構(gòu)建最小領(lǐng)航頂點(diǎn)集。

圖8 對(duì)比實(shí)驗(yàn)Fig.8 Comparison of experimental results

實(shí)驗(yàn)2 CSA算法的求解效率與無(wú)人機(jī)個(gè)體通信半徑間關(guān)系。

在本實(shí)驗(yàn)中，針對(duì)不同的無(wú)人機(jī)個(gè)體數(shù)目，測(cè)試CSA算法在不同通信半徑條件下的求解效率，實(shí)驗(yàn)結(jié)果如圖9所示。

圖9 CSA算法求解效率與通信半徑的關(guān)系Fig.9 Relationship between the efficiency of CSA and communication radius of UAV

從圖9中可以看出，盡管CSA算法在求解過(guò)程有一定程度的抖動(dòng)，但當(dāng)頂點(diǎn)個(gè)數(shù)小于30時(shí)，求解效率在95%上。一個(gè)有趣的現(xiàn)象是，當(dāng)頂點(diǎn)個(gè)數(shù)大于30時(shí)，若其通信半徑介于3～9，則CSA算法幾乎100%可以找到領(lǐng)航集；若通信半徑小于3或大于9，則CSA算法都出現(xiàn)了不同程度的抖動(dòng)，特別是當(dāng)通信半徑介于0.5～3時(shí)，算法求解效率較差。出現(xiàn)這一現(xiàn)象的原因在于，此時(shí)圖中單重特征值減少而多重特征值增加，這使得同一特征值對(duì)應(yīng)的關(guān)鍵集增加，而基于本文給出的定理2～5，CSA算法只求出2關(guān)鍵集、3關(guān)鍵集和孤立關(guān)鍵集等一些特殊的關(guān)鍵集，從而使得算法難以找到領(lǐng)航集。例如，見(jiàn)圖10，該無(wú)向網(wǎng)絡(luò)的特征值中，除單重特征值外，還有1個(gè)3重特征值、1個(gè)4重特征值和1個(gè)5重特征值，CSA算法難以找到它的領(lǐng)航集。這說(shuō)明，當(dāng)頂點(diǎn)個(gè)數(shù)多且通信半徑較小時(shí)，圖中的關(guān)鍵集情況較復(fù)雜，需要進(jìn)一步從理論上研究k關(guān)鍵集的圖特征。

圖10 復(fù)雜特征值情況的網(wǎng)絡(luò)結(jié)構(gòu)Fig.10 Description of networks with multiple eigenvalues

實(shí)驗(yàn)3 領(lǐng)航頂點(diǎn)個(gè)數(shù)與邊數(shù)關(guān)系。

隨著無(wú)人機(jī)個(gè)體和邊數(shù)的變化，領(lǐng)航頂點(diǎn)的個(gè)數(shù)也會(huì)相應(yīng)地變化，因此，本實(shí)驗(yàn)不考慮領(lǐng)航頂點(diǎn)個(gè)數(shù)的絕對(duì)值，而是考慮“領(lǐng)航頂點(diǎn)個(gè)數(shù)/無(wú)人機(jī)個(gè)體數(shù)量n”與“邊數(shù)/總邊數(shù)(即完全圖中的邊數(shù)n(n?1)/2)”間的關(guān)系。

實(shí)驗(yàn)結(jié)果如圖11所示。從圖11中可以看出，隨著邊數(shù)占比趨于1，領(lǐng)航頂點(diǎn)占比趨于(n?1)/n；隨著邊數(shù)占比趨于0，領(lǐng)航頂點(diǎn)占比趨于1；特別是，領(lǐng)航頂點(diǎn)占比達(dá)最小。從圖11中可以看出，當(dāng)無(wú)人機(jī)個(gè)體數(shù)量為10時(shí)，領(lǐng)航頂點(diǎn)占比達(dá)最小的情況出現(xiàn)在邊數(shù)占比為0.6～0.7；當(dāng)無(wú)人機(jī)個(gè)體的數(shù)量為30時(shí)，領(lǐng)航頂點(diǎn)占比達(dá)最小的情況出現(xiàn)在邊數(shù)占比為 0.4～0.6；當(dāng)無(wú)人機(jī)個(gè)體的數(shù)量為50(70)時(shí)，領(lǐng)航頂點(diǎn)占比達(dá)最小的情況出現(xiàn)在邊數(shù)占比為 0 .1～0.3。也就是說(shuō)，從整體上看，所有“領(lǐng)航頂點(diǎn)占比與邊數(shù)占比”曲線(xiàn)都是下凸曲線(xiàn)，無(wú)人機(jī)個(gè)體數(shù)越多，曲線(xiàn)越向下凸且極小值點(diǎn)越向“左”偏。這一現(xiàn)象說(shuō)明，若用較少個(gè)數(shù)的無(wú)人機(jī)個(gè)體控制整個(gè)無(wú)人機(jī)集群，則通信網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)圖中的邊數(shù)應(yīng)取值于適當(dāng)范圍，實(shí)驗(yàn)3從統(tǒng)計(jì)意義上給出了這個(gè)范圍。

圖11 領(lǐng)航頂點(diǎn)個(gè)數(shù)與邊數(shù)的關(guān)系Fig.11 Relationship between the number of leaders and edges

4 結(jié)束語(yǔ)

本文以幾十架無(wú)人機(jī)構(gòu)成的無(wú)人機(jī)集群為應(yīng)用背景，利用Laplace矩陣的特征向量提出關(guān)鍵集概念，指出領(lǐng)航集所必須具備的圖特征，即領(lǐng)航集需覆蓋所有關(guān)鍵集。給出了2關(guān)鍵集和3關(guān)鍵集的圖特征，從圖論角度給出獨(dú)立集成為關(guān)鍵集的一個(gè)充分條件。數(shù)值實(shí)驗(yàn)表明，基于關(guān)鍵集，CSA算法在大多數(shù)情況下能以90%以上的概率搜索到領(lǐng)航集。

如何刻畫(huà)k(k≥4) 關(guān)鍵集的圖特征是需進(jìn)一步研究的內(nèi)容。這是十分難以解決的問(wèn)題，比如由圖2知4關(guān)鍵集與這4個(gè)頂點(diǎn)的相鄰關(guān)系有關(guān)，全體4階互不同構(gòu)的簡(jiǎn)單圖有11個(gè)，其中邊數(shù)為0、1、2、3、4、5、6的圖的個(gè)數(shù)分別為1、1、2、3、2、1、1。而全體5階互不同構(gòu)的簡(jiǎn)單圖有34個(gè)。隨著k的增加，k(k≥4) 關(guān)鍵集的情況異常復(fù)雜。但是，這又是一個(gè)十分有意義的問(wèn)題。比如，從數(shù)值實(shí)驗(yàn)可以看出，僅依據(jù)本文給出的定理2～5求出有限特殊的關(guān)鍵集，CSA算法就能在大多數(shù)情況下以90%以上的概率搜索到領(lǐng)航集。

另外，從圖論角度給出領(lǐng)航集的充要條件，最小領(lǐng)航頂點(diǎn)數(shù)的上、下界等也都是值得進(jìn)一步研究的問(wèn)題。