基于編隊(duì)控制的自適應(yīng)HELLO更新算法

黃紹城，馬林華，茹 樂，蔡 釗，張 嵩，胡 星

基于編隊(duì)控制的自適應(yīng)HELLO更新算法

黃紹城，馬林華*，茹 樂，蔡 釗，張 嵩，胡 星

（空軍工程大學(xué) 航空航天工程學(xué)院，西安710038）

在無人機(jī)（UAVs）編隊(duì)自組織網(wǎng)絡(luò)中，針對(duì)無人機(jī)之間位置信息更新周欺不合理，從而導(dǎo)致編隊(duì)控制不穩(wěn)定和控制開銷過大的問題，提出一種基于無人機(jī)編隊(duì)控制的自適應(yīng)HELLO更新算法。該算法應(yīng)用編隊(duì)控制穩(wěn)定性理論推導(dǎo)出無人機(jī)組成欺望編隊(duì)的控制延時(shí)上限，結(jié)合該延時(shí)上限和編隊(duì)運(yùn)動(dòng)狀態(tài)自適應(yīng)地設(shè)定HELLO更新周欺。仿真結(jié)果表明，本文提出的算法與固定HELLO更新周欺算法相比，既能保證在組編控制過程的穩(wěn)定性，又能實(shí)時(shí)維護(hù)穩(wěn)定階段的鏈路，并且顯著減少網(wǎng)絡(luò)中不必要的控制開銷。

無人機(jī)（UAVs）編隊(duì)；控制開銷；延時(shí)上限；自適應(yīng)；HELLO

在航空自組織網(wǎng)絡(luò)中，隨著定位裝置和定位算法發(fā)展的成熟，基于地理位置信息的主動(dòng)式路由協(xié)議（Optimized Link State Routing protocol，OLSR）由于能主動(dòng)進(jìn)行周期性鏈路探測和路由維護(hù)而在動(dòng)態(tài)網(wǎng)絡(luò)環(huán)境下展現(xiàn)出較大的優(yōu)勢［1］。其中一個(gè)關(guān)鍵就是個(gè)體之間位置信息的更新和拓?fù)涞木S護(hù)主要通過HELLO消息的交互［2-3］。雖然使用較短的更新周期能較快地維護(hù)鄰居列表和鏈路信息，但是過短的周期則會(huì)增加不必要的控制開銷［4-5］。文獻(xiàn)［6］通過實(shí)際硬件測試發(fā)現(xiàn)，HELLO的更新周期對(duì)整個(gè)網(wǎng)絡(luò)吞吐量性能影響非常大。

標(biāo)準(zhǔn)的OLSR協(xié)議允許不同的節(jié)點(diǎn)具有不同的HELLO更新周期，但是具體的實(shí)現(xiàn)方案和操作過程并沒有給出。Fast-OLSR［7］通過增加短周期HELLO信息類型來適應(yīng)網(wǎng)絡(luò)節(jié)點(diǎn)的高速運(yùn)動(dòng)，主要根據(jù)節(jié)點(diǎn)與鄰居節(jié)點(diǎn)的高速相對(duì)運(yùn)動(dòng)基礎(chǔ)信息來設(shè)定控制信息的更新周期。雖然其在一定程度上減少路由開銷，卻增加了一個(gè)新的HELLO信息類型，而且僅有兩種固定周期并不能很好適應(yīng)鏈路和拓?fù)渥兓闆r。文獻(xiàn)［8］提出的動(dòng)態(tài)自適應(yīng)間隔的OLSR協(xié)議，即IOLSR協(xié)議，其中每個(gè)節(jié)點(diǎn)都能根據(jù)本地的鏈路狀況自適應(yīng)地調(diào)整HELLO周期。雖然這在一定程度上減少了控制開銷，卻沒有適應(yīng)編隊(duì)的拓?fù)浣Y(jié)構(gòu)，即不能很好地適應(yīng)真正的網(wǎng)絡(luò)實(shí)時(shí)需求。文獻(xiàn)［9］提出了基于鏈路中斷概率的自適應(yīng)信標(biāo)交換算法，主要根據(jù)理想運(yùn)動(dòng)模型來預(yù)測鏈路，并不適用于實(shí)際的節(jié)點(diǎn)運(yùn)動(dòng)狀態(tài)。

以上的HELLO更新算法能適應(yīng)一定的移動(dòng)環(huán)境，卻沒有考慮編隊(duì)組網(wǎng)中飛行控制所需要的位置更新需求。目前，無人機(jī)編隊(duì)飛行控制研究主要采用長機(jī)-僚機(jī)控制方法和一致性協(xié)調(diào)控制方法。長機(jī)-僚機(jī)控制方法通過控制長機(jī)，按預(yù)定軌跡飛行，并由長機(jī)對(duì)僚機(jī)下達(dá)命令，使得僚機(jī)跟隨長機(jī)并以固定的編隊(duì)結(jié)構(gòu)一起飛行。該方法易于理解和實(shí)現(xiàn)，但魯棒性較弱，一旦長機(jī)出現(xiàn)故障，則整個(gè)編隊(duì)的控制將失效。一致性協(xié)議是多智能體協(xié)調(diào)控制研究的熱點(diǎn)之一，它是指智能體通過鄰域中其他智能體的狀態(tài)信息決定自身的狀態(tài)，并最終使其狀態(tài)達(dá)到一致的方法［10］。其中位置信息的周期性相互交換是保證其一致性運(yùn)動(dòng)的必要條件。對(duì)于編隊(duì)控制而言，通信上過長的更新周期而導(dǎo)致的位置更新延時(shí)可能會(huì)導(dǎo)致編隊(duì)無法收斂到期望的穩(wěn)定隊(duì)形［11-12］。

針對(duì)以上問題，本文提出了適應(yīng)無人機(jī)編隊(duì)組網(wǎng)運(yùn)動(dòng)狀態(tài)的自適應(yīng)HELLO更新算法（應(yīng)用該算法的OLSR協(xié)議簡稱為AOLSR）。該算法依據(jù)編隊(duì)狀態(tài)將HELLO更新分為兩部分：收斂到期望隊(duì)形所能容忍的最大延時(shí)作為更新周期依據(jù)；穩(wěn)定飛行狀態(tài)下依據(jù)鏈路的變化而自適應(yīng)更新周期。網(wǎng)絡(luò)自適應(yīng)地更新HELLO消息既能滿足一致性協(xié)調(diào)控制的需求，又能在及時(shí)維護(hù)拓?fù)浜玩溌沸畔⒒A(chǔ)上減少網(wǎng)絡(luò)的控制開銷。

本文結(jié)構(gòu)安排如下：第1節(jié)介紹編隊(duì)運(yùn)動(dòng)模型并詳細(xì)推導(dǎo)組成特定穩(wěn)定編隊(duì)所能容忍的最大允許延時(shí)；第2節(jié)根據(jù)編隊(duì)運(yùn)動(dòng)狀態(tài)進(jìn)行HELLO等控制消息的自適應(yīng)更新周期設(shè)計(jì)；第3節(jié)分別對(duì)編隊(duì)控制系數(shù)對(duì)允許延時(shí)的影響和網(wǎng)絡(luò)在自適應(yīng)HELLO算法下的整體性能進(jìn)行仿真分析。

1 編隊(duì)系統(tǒng)模型和延時(shí)上限

1．1 編隊(duì)系統(tǒng)模型

為了表示編隊(duì)控制和通信的關(guān)系，利用圖論知識(shí)定義無向編隊(duì)圖G＝（V，E），其中V為無人機(jī)集合，E?V×V為邊集合，表示個(gè)體之間的信息流，如果（i，j）∈E，說明個(gè)體i和j之間能進(jìn)行通信。定義鄰接矩陣A＝（aij）n×n，如果（i，j）∈E，則令aij＝1，否則令aij＝0；度矩陣Δ＝diag｛d1， d2，…，dn｝∈Rn×n，其中對(duì)角元素圖 G的拉普拉斯矩陣定義為L＝Δ-A。為了方便后續(xù)計(jì)算，定義規(guī)范化鄰接矩陣，則矩陣的每行之和都為1，相應(yīng)的度矩陣和拉普拉斯矩陣為

［13-14］設(shè)計(jì)的多無人機(jī)控制系統(tǒng)模型，每個(gè)無人機(jī)模型最終可以簡化為雙積分動(dòng)態(tài)模型：

根據(jù)一致性理論，控制輸入 ui（t）應(yīng)該是無人機(jī)的相對(duì)位置誤差和相對(duì)速度誤差的函數(shù)，令個(gè)體i和j之間的通信延時(shí)為τij，設(shè)計(jì)第i個(gè)無人機(jī)的反饋控制為

式中：控制系數(shù)c1、c2和c3均為常數(shù)；vd（t）為期望速度；hi為期望位置；Ni為個(gè)體i鄰居集合。假設(shè)vd（t）為常數(shù)vd，且個(gè)體之間的通信延時(shí)一致，均為τ，則個(gè)體i的閉環(huán)控制形式為

式中：hi和hj為無人機(jī)的期望位置。

1．2 收斂至期望隊(duì)形的延時(shí)上限

具有式（3）形式的多無人機(jī)系統(tǒng)能否形成期望隊(duì)形，并以期望速度和穩(wěn)定隊(duì)形向前運(yùn)動(dòng)，不僅與系統(tǒng)拓?fù)浣Y(jié)構(gòu)相關(guān)，同時(shí)取決于控制系數(shù)和延時(shí)的大小，下面求出最大允許延時(shí)的上限。令

則式（3）為

將此系統(tǒng)擴(kuò)展到所有個(gè)體，即令

則有

式中：In和IN分別為n×n階和N×N階的單位矩陣。

存在正交矩陣U，使得UT?AU＝I-λ，其中U和λ分別為的特征向量矩陣和特征值構(gòu)成的對(duì)角矩陣，即λ＝diag（λ1，λ2，…，λn）。因此有坐標(biāo)變換式（5）進(jìn)一步寫成：

再將式（6）的系統(tǒng)分解為 n個(gè)獨(dú)立的子系統(tǒng)，則有

對(duì)式（7）進(jìn)行拉普拉斯變換，得到

式中：ˉXi（s）和ˉVi（s）分別為ˉxi（t）和ˉvi（t）的拉普拉斯變換。

進(jìn)一步可以得到閉環(huán)系統(tǒng)的特征方程：

由穩(wěn)定性理論，編隊(duì)系統(tǒng)漸近穩(wěn)定的充要條件是式（9）除了有一個(gè)0的特征根外，其余特征根都位于左半復(fù)平面。下面求出延時(shí)的上限值：

當(dāng)τ＝0時(shí)，明顯滿足穩(wěn)定條件，不再證明；當(dāng)τ＞0時(shí)，令Fi（s）＝1+Gi（s），其中：

為了滿足系統(tǒng)的穩(wěn)定性，需要證明Fi（s）的零點(diǎn)都在左半復(fù)平面。令s＝j(luò)ω，根據(jù)Nyquist判據(jù)，F(xiàn)i（s）的零點(diǎn)都在左半復(fù)平面的充要條件是：對(duì)于所有的ω∈［0，∞），Gi（jω）的軌跡不包含復(fù)平面的（-1，j0）點(diǎn)。由規(guī)范化的編隊(duì)圖可知圖中頂點(diǎn)最大的度為1，再根據(jù)Gerschgorin圓盤定理可知：拉普拉斯矩陣?L的特征值λi都在以（1，0）為圓心，1為半徑的圓內(nèi)。又因?yàn)??L是實(shí)對(duì)稱矩陣，所以0≤λi≤2，令λ′i＝1-λi，則可以得到由幅值穿越條件 Gi（jω）＝1，得到

1）當(dāng)ki≥0時(shí)，只有當(dāng)λi＝0或λi＝2時(shí)，方程（11）存在解ω＝0，否則方程不存在關(guān)于ω＞0的實(shí)根，即 Gi（jω）＜1恒成立，因此，當(dāng)ki≥0時(shí)，對(duì)于任意延時(shí)τ＞0，當(dāng)ω∈［0，∞），Gi（jω）的軌跡不包含復(fù)平面的（-1，j0）點(diǎn)，即Fi（s）的零點(diǎn)都在左半復(fù)平面。

2）當(dāng)ki＜0且時(shí)，方程不存在關(guān)于ω的實(shí)根，說明 Gi（jω）＜1恒成立，因此，對(duì)于任意延時(shí)τ＞0，當(dāng)ω∈［0，∞），Gi（jω）的軌跡不包含復(fù)平面的（-1，j0）點(diǎn)，即Fi（s）的零點(diǎn)都在左半復(fù)平面。

3）當(dāng)ki＜0且時(shí)，得到方程式（11）的實(shí)根，即可得到穿越頻率：

穩(wěn)定性判據(jù)轉(zhuǎn)化為求穿越頻率 ω下的相位裕度條件：

綜上，對(duì)于任意延時(shí) τ＜τi，當(dāng) ω∈［0，∞），Gi（jω）的軌跡不包含復(fù)平面的（-1，j0）點(diǎn)，即Fi（s）的零點(diǎn)都在左半復(fù)平面。綜上，整個(gè)系統(tǒng)的最大允許通信延時(shí)為τm＝min｛τi｝，若能保證當(dāng)τ＜τm，則以式（3）為控制系統(tǒng)的無人機(jī)編隊(duì)能最終收斂穩(wěn)定。

2 自適應(yīng)HELLO更新策略

在移動(dòng)無人機(jī)編隊(duì)組網(wǎng)中，本文使用基于位置信息的高動(dòng)態(tài)OLSR路由協(xié)議［1］，該協(xié)議通過周期性地交互HELLO消息來感知拓?fù)浜徒粨Q組成期望編隊(duì)過程中所需的地理位置信息。現(xiàn)實(shí)環(huán)境中，編隊(duì)組網(wǎng)與隨機(jī)運(yùn)動(dòng)模型組網(wǎng)存在著較大區(qū)別：編隊(duì)組網(wǎng)在形成期望編隊(duì)過程中需要實(shí)時(shí)提供位置信息并及時(shí)維護(hù)路由，這對(duì)信標(biāo)交換的延時(shí)要求更高，而在形成穩(wěn)定隊(duì)形之后，其拓?fù)洳粫?huì)有太大的變化，因此不需要發(fā)送多余的HELLO等控制消息，頻繁地更新位置信息。編隊(duì)自適應(yīng)HELLO更新算法可根據(jù)運(yùn)動(dòng)的場景自適應(yīng)地調(diào)整HELLO消息更新周期，算法流程如圖1所示（其中α為更新指數(shù)），主要分為兩步：

1）當(dāng)無人機(jī)進(jìn)行組隊(duì)時(shí)，所有個(gè)體在接收到組隊(duì)的指令后，依據(jù)收斂至穩(wěn)定編隊(duì)的最大允許延時(shí)，HELLO消息更新周期設(shè)置為

其中拓?fù)淇刂疲═C）周期和消息有效時(shí)間根據(jù)文獻(xiàn)［8］分別設(shè)定如下：TC周期設(shè)定為TTC＝2.5 tm，消息有效時(shí)間設(shè)定為Ttimeout＝3TTC。

圖1 自適應(yīng)HELLO更新算法的流程圖Fig.1 Flowchart of adaptive HELLO update algorithm

2）當(dāng)編隊(duì)處于穩(wěn)定狀態(tài)時(shí)，對(duì)于位置的實(shí)時(shí)更新要求不高，這時(shí)更注重?cái)?shù)據(jù)信息傳輸?shù)挠行裕瑴p少不必要的通信開銷。因此，本文以網(wǎng)絡(luò)的鏈路狀況來調(diào)整控制信息的更新周期：更新周期以成功接收的相應(yīng)信息包的個(gè)數(shù)呈指數(shù)次方增加，一旦出現(xiàn)統(tǒng)計(jì)失敗，立即恢復(fù)初始化狀態(tài)感知拓?fù)洹?/p>

3 仿真分析

使用NS2仿真分析AOLSR協(xié)議和OLSR協(xié)議在編隊(duì)場景中的性能，仿真參數(shù)設(shè)置如表1所示；設(shè)置標(biāo)準(zhǔn)：OLSR的HELLO周期分別為2 s和4 s，TC周期設(shè)置為5 s和10 s，消息有效時(shí)間設(shè)置為15 s和30 s。編隊(duì)運(yùn)動(dòng)場景設(shè)置為3個(gè)階段：0～400 s隨機(jī)分布于活動(dòng)區(qū)域，400 s到約600 s為組隊(duì)過程，向期望位置組成特定編隊(duì)，600 s后保持隊(duì)形以期望速度2.5m／s恒速前進(jìn)。仿真分為兩部分：檢驗(yàn)并討論控制系數(shù)c1、c2、c3和拉普拉斯矩陣特征值λi與最大允許延時(shí)的關(guān)系；針對(duì)整個(gè)網(wǎng)絡(luò)的吞吐量、交付率、端到端延時(shí)、路由開銷及控制信息等網(wǎng)絡(luò)性能進(jìn)行仿真比較。

表1 仿真參數(shù)Table 1 Sim u lation param eters

3．1 控制參數(shù)與特征值對(duì)允許延時(shí)上限的影響

通過MATLAB計(jì)算可以得到τm與控制系數(shù)c1、c2、c3和拉普拉斯矩陣特征值 λi的關(guān)系，如圖2所示。

圖2 控制系數(shù)和編隊(duì)延時(shí)上限的關(guān)系Fig.2 Relationship between control factors and maximum tolerable delay of formation

由圖2（a）、圖2（b）可以發(fā)現(xiàn)τm與c1、c3成正比，從圖2（c）可以看出，τm與c2成反比。因此，當(dāng)組成編隊(duì)過程中對(duì)實(shí)時(shí)位置信息的更新需求較高時(shí)，可以適當(dāng)選擇較大的c1、c3和較小c2的控制參數(shù)。為了更大范圍的討論τm與特征值λi的關(guān)系，令c1＝0．1，c2＝2，c3＝0．1，如圖2（d）所示，當(dāng)λi＝1時(shí)，τm趨于無窮大，同樣由式（9）可知，當(dāng)λi＝1時(shí)，方程的根與延時(shí)沒有關(guān)系。

3．2 網(wǎng)絡(luò)性能

由初始位置、期望位置和速度計(jì)算出相應(yīng)的規(guī)范化鄰接矩陣?A和相應(yīng)拉普拉斯矩陣 ?L的特征值，并由式（14）和式（15）計(jì)算出編隊(duì)組隊(duì)允許的延時(shí)上限為2.56 s。首先比較AOLSR和2 s HELLO更新周期和4 s HELLO更新周期的標(biāo)準(zhǔn)OLSR協(xié)議（簡稱2sOLSR，4sOLSR）在上述特定運(yùn)動(dòng)狀態(tài)下實(shí)時(shí)控制開銷和實(shí)時(shí)吞吐量。

如圖3所示，給出了仿真時(shí)間下每50 s統(tǒng)計(jì)的路由控制包開銷情況。由圖3可發(fā)現(xiàn)前400 s的控制開銷相對(duì)都較為平穩(wěn)，且2sOLSR開銷要明顯高于AOLSR；在400～600 s的組隊(duì)過程中，AOLSR的控制包數(shù)量明顯增加，而在600 s組隊(duì)完成后控制開銷明顯減少且低于4sOLSR控制開銷，這說明AOLSR能很好地適應(yīng)動(dòng)態(tài)拓?fù)洌芨鶕?jù)鏈路情況調(diào)整HELLO等控制消息的周期來維護(hù)正常通信。原因有：①在組隊(duì)過程允許的延時(shí)上限為2.56 s，根據(jù)本文算法，此階段的HELLO周期設(shè)置為2 s，更新頻率較快；②到達(dá)期望編隊(duì)后，編隊(duì)拓?fù)浠静蛔儯溌废鄬?duì)穩(wěn)定，因此，依據(jù)自適應(yīng)更新算法就會(huì)逐漸加大更新周期，路由的控制開銷也就明顯下降。

圖3 實(shí)時(shí)路由控制包Fig.3 Real time routing control packets

其次，實(shí)時(shí)吞吐量通過成功接收的數(shù)據(jù)包來表示［15］，由圖 4發(fā)現(xiàn)，總體上，在靜止階段（0～400 s）由于是跳數(shù)較多情況，吞吐量相對(duì)于后面組隊(duì)聚集后的穩(wěn)定階段要低（1 000 packets左右）；且三者在組隊(duì)過程中，都出現(xiàn)吞吐量下降的情況，但是AOLSR卻能較快地調(diào)整其HELLO等控制消息的周期，維護(hù)好網(wǎng)絡(luò)的鏈路，其吞吐量能較快地提升上來（約在450 s左右）。雖然另外兩種更新周期的OLSR協(xié)議在500 s左右也開始上升，但這不是自適應(yīng)調(diào)整的結(jié)果，而是組隊(duì)基本結(jié)束才使得鏈路基本穩(wěn)定造成的。

下面主要比較和分析AOLSR和另外兩更新周期的OLSR協(xié)議在不同鏈路突發(fā)錯(cuò)誤條件下控制開銷、吞吐量、延時(shí)及丟包率方面的性能。如圖5所示。

圖5（a）給出路由控制開銷隨鏈路突發(fā)錯(cuò)誤變化的情況。可以很明顯地發(fā)現(xiàn)固定更新周期的OLSR協(xié)議其控制包數(shù)并沒有隨著鏈路的突發(fā)錯(cuò)誤概率的增加而增加。相對(duì)標(biāo)準(zhǔn)OLSR，AOLSR控制包數(shù)量能根據(jù)鏈路情況增加控制包的發(fā)包頻率，其控制開銷要遠(yuǎn)遠(yuǎn)小于2sOLSR協(xié)議，減少約為42.6%。雖然4sOLSR協(xié)議的開銷低于AOLSR，但是其他性能卻無法得到保障，下面通過圖5（b）、圖5（c）及圖5（d）進(jìn)行分析：

1）雖然總體上2sOLSR的吞吐量、丟包率及延時(shí)等方面性能和AOLSR協(xié)議的相差不大，但是因?yàn)闆]有自適應(yīng)的控制消息更新周期導(dǎo)致開銷遠(yuǎn)遠(yuǎn)大于AOLSR。

2）雖然OLSR增大HELLO周期能減少開銷（如圖5（a）），但是由圖5（b）～圖5（d）可以明顯發(fā)現(xiàn)其在吞吐量、丟包率和延時(shí)等方面性能下降比較大，且遠(yuǎn)遠(yuǎn)達(dá)不到AOLSR和2sOLSR相應(yīng)的性能。

3）在鏈路情況較好（突發(fā)錯(cuò)誤概率小于10-4）時(shí)，AOLSR的各方面性能都要比另外兩者好。

圖5 網(wǎng)絡(luò)控制開銷、吞吐量、丟包率和延時(shí)的比較Fig.5 Comparison of network control overhead，throughput，drop rate and delay

4 結(jié) 論

針對(duì)無人機(jī)編隊(duì)網(wǎng)絡(luò)環(huán)境中HELLO消息更新不合理而出現(xiàn)的編隊(duì)不穩(wěn)定和控制開銷過大的問題，在傳統(tǒng)OLSR協(xié)議固定HELLO更新算法基礎(chǔ)上，提出基于編隊(duì)控制的自適應(yīng)HELLO更新算法，仿真結(jié)果表明：

1）AOLSR的自適應(yīng)HELLO更新算法引入了編隊(duì)穩(wěn)定控制機(jī)制，既能為編隊(duì)組網(wǎng)的一致性協(xié)調(diào)控制所需的及時(shí)位置更新提供保障，又能減少不必要的控制開銷，提高網(wǎng)絡(luò)的吞吐量。

2）提出的AOLSR與傳統(tǒng)OLSR相比，可以有效地適應(yīng)動(dòng)態(tài)拓?fù)涞淖儞Q，合理調(diào)整HELLO等控制消息的更新間隔，降低了整個(gè)網(wǎng)絡(luò)控制開銷。

3）在不同的鏈路環(huán)境中，由于AOLSR采用自適應(yīng)更新策略，能及時(shí)維護(hù)中斷鏈路，性能較為理想；AOLSR與大周期更新的OLSR相比，雖然在控制開銷上不理想，但是吞吐量、丟包率和延時(shí)性能很突出；而與小周期更新的OLSR相比，在保持其他性能基本相近的情況下，很大程度上減少了控制開銷。

參考文獻(xiàn)（References）

［1］WANG A，ZHU B.Improving MPR selection algorithm in OLSR protocol based on node localization［J］.Journal of Intelligent＆Robotic Systems，2014，9（7）：1674-1681.

［2］PALANIAMMAL M，LALLI M.Comparative study of routing protocols for MANETs［J］.International Journal of Networked and Distributed Computing，2014，2（2）：118-127.

［3］ERNST R，JOPEN SA，BARTELT T.Reducing MANET neighborhood discovery overhead［C］∥IEEE 39 th Conference on Local Computer Networks.Piscataway，NJ：IEEE Press，2014：374-377.

［4］HAN S Y，LEE D.An adaptive hello messaging scheme for neighbor discovery in on-demand MANET routing protocols［J］.IEEE Communications Letters，2013，17（5）：1040-1043.

［5］ERNST R，MARTINIP.Adaptive HELLO for the neighborhood discovery protocol［C］∥IEEE 37 th Conference on Local Computer Networks.Piscataway，NJ：IEEE Press，2012：470-478.

［6］HIYAMA M，KULLA E，IKEDA M，et al.Investigation of OLSR behavior for different HELLO packets intervals in a MANET testbed［C］∥IEEE 27 th International Conference on Advanced Information Networking and Applications.Piscataway，NJ：IEEE Press，2013：183-188.

［7］BENZAID M，MINET P，ALAGHA K.Analysis and simulation of fast-OLSR［C］∥57 th IEEE Semiannual Vehicular Technology Conference.Piscataway，NJ：IEEE Press，2003，3：1788-1792.

［8］LARSEN E，J FATHAGEN，Y PHAM，L Landmark.iOLSR：OLSR for WSNs using dynamically adaptive intervals［C］∥Proceedings of the 5 th International Conference on Sensor Technologies and App lication.Trondheim：IFSA Press，2011：21-27.

［9］張衡陽，鄭博，陳校平，等.基于鏈路斷開概率的自適應(yīng)信標(biāo)交換算法［J］.計(jì)算機(jī)研究與發(fā)展，2013，50（3）：472-480.

ZHANG H Y，ZHENG B，CHEN X P，et al.An adaptive beacon exchang algorithm baced on link broken probability［J］.Journal of Computer Research and Development，2013，50（3）：472-480（in Chinese）.

［10］PENG Z，WEN G，RAHMANI A，et al.Distributed consensusbased formation control formultiple nonholonomic mobile robots with a specified reference trajectory［J］.International Journal of Systems Science，2015，46（8）：1447-1457.

［11］DONG X，XI J，LU G，et al.Formation control for high-order linear time-invariantmultiagent systems with time delays［J］. IEEE Transactions on Control of Network Systems，2014，1（3）：232-240.

［12］DONG X，YU B，SHI Z，et al.Time-varying formation control for unmanned aerial vehicles：Theories and application［J］. IEEE Transactions on Control of Network Systems，2015，23（1）：340-348.

［13］WANG N，ZHANG T W，XU J Q.Formation control for networked spacecraft in deep space：W ith or without communication delays and with switching topology［J］.Science China Information Sciences，2011，54（3）：469-481.

［14］姜麗梅，張汝波.具有通信延時(shí)的多機(jī)器人編隊(duì)控制［J］.北京郵電大學(xué)學(xué)報(bào)，2012，35（2）：54-58.

JIANG L M，ZHANG R B.Multi-robot formation with communication delay［J］.Journal of Beijing University of Posts and Telecommunications，2012，35（2）：54-58（in Chinese）.

［15］高先明，張曉哲，王寶生，等.面向虛擬路由器的基于歷史轉(zhuǎn)發(fā)開銷的資源調(diào)度算法［J］.電子與信息學(xué)報(bào)，2015，37（3）：686-692.

GAO X M，ZHANG X Z，WANG B S，et al.Historical forwarding overhead based the resource scheduling algorithm for the virtual router［J］.Journal of Electronics＆Information Techonology，2015，37（3）：686-692（in Chinese）.

Tel.：029-84787700

E-mail：malinhua1965＠163.com

茹樂 男，博士，教授。主要研究方向：自組織網(wǎng)絡(luò)、無線通信。Tel.：029-84787700

E-mail：ru_le＠163.com

?功接收數(shù)據(jù)包 Fig.4 Successfully

packets

Form ation control-based adaptive update algorithm of HELLO m essage

HUANG Shaocheng，MA Linhua*，RU Le，CAI Zhao，ZHANG Song，HU Xing

（School of Aeronautics and Astronautics Engineering，Air Force Engineering University，Xi’an 710038，China）

In the unmanned aerial vehicles（UAVs）formation ad hoc network，in order to solve the instability of formation control problem and reduce the large control overhead，both of which are caused by unreasonable update cycle of the position information，a formation control-based adaptive update algorithm of HELLO message is proposed.The algorithm employs the maximum tolerable delay which is deduced by the formation control stability theory for formation control，and combines with the formation stability theory to set an adaptive HELLO update cycle.The simulation results demonstrate that，compared with the fixed HELLO update algorithm，the proposed algorithm not only ensures the stability in the formation forming stage，but also maintains the link availability in the formation stability stage and effectively reduces the unnecessary control overhead.

unmanned aerial vehicles（UAVs）formation；control overhead；maximum tolerable delay；adaptive；HELLO

s：National Natural Science Foundation of China（61472442）；Aeronautical Science Foundation of China（20130596008，20145596025）；Subject Research Project of State Key Laboratory of Integrated Services Networks（ISNI15-13）

TP393.04

A

1001-5965（2016）10-2155-07

黃紹城 男，博士研究生。主要研究方向：自組織網(wǎng)絡(luò)、寬帶通信網(wǎng)絡(luò)。

E-mail：deanhsc＠163.com

馬林華 男，博士，教授，博士生導(dǎo)師。主要研究方向：自組織網(wǎng)絡(luò)、信道編碼技術(shù)及寬帶通信網(wǎng)絡(luò)。

http：∥bhxb.buaa.edu.cn jbuaa＠buaa.edu.cn

DO I：10.13700／j.bh.1001-5965.2015.0645

2015-10-08；錄用日期：2016-01-08；網(wǎng)絡(luò)出版時(shí)間：2016-03-15 14：28

www.cnki.net／kcms／detail／11.2625.V.20160315.1428.003.htm l

國家自然科學(xué)基金（61472442）；航空科學(xué)基金（20130596008，20145596025）；綜合業(yè)務(wù)網(wǎng)理論及關(guān)鍵技術(shù)國家重點(diǎn)實(shí)驗(yàn)室研究課題（ISNI15-13）

*通訊作者：Tel.：029-84787700 E-mail：malinhua1965＠163.com

黃紹城，馬林華，茹樂，等.基于編隊(duì)控制的自適應(yīng)HELLO更新算法［J］.北京航空航天大學(xué)學(xué)報(bào)，2016，42（10）：2155-2161.HUANG SC，MA L H，RU L，et al.Formation control-based adaptive update algorithm of HELLO message［J］.Journal of Beijing University of Aeronautics and Astronautics，2016，42（10）：2155-2161（in Chinese）.

Received：2015-10-08；Accep ted：2016-01-08；Pub lished online：2016-03-15 14：28

URL：www.cnki.net／kcms／detail／11.2625.V.20160315.1428.003.htm l

*Correspond ing au thor.Tel.：029-84787700 E-mail：malinhua1965＠163.com