一種用于無人機集群發射控制系統調度機制的應用研究

李博, 張盛兵, 張小林, 席博聞, 田云鵬

1.西北工業大學 計算機學院, 陜西 西安 710072;2.西北工業大學 第365研究所, 陜西 西安 710065; 3.空軍駐西安地區軍事代表室, 陜西 西安 710065

當前，集群無人機作戰的理念越來越受到各國軍方的重視。集群無人機作戰不僅能夠增加無人機的打擊力度，也能夠使各個無人機協同配合達到最佳的戰斗性能[1]。集群發射階段是無人機集群作戰的第一階段。快速、有效地將無人機在短時間內發射升空，直接關系無人機系統在戰場上的作戰能力和生存能力，其相關技術是無人機集群作戰裝備研究的重要領域。

本文所研究的無人機集群發射控制系統是一種基于CAN總線的網絡控制系統，下文將其簡稱為發射控制系統。其中指揮控制節點和無人機號位控制節點構成了控制系統的主網絡，各個號位控制節點與系統傳感器、測量傳感器以及執行機構成了子系統。

由于CAN總線數據傳輸是依據仲裁機制進行的[2]，因此在發射控制系統中，各個節點會對網絡帶寬等系統資源進行競爭，從而造成網絡中數據傳輸延時或擁塞，甚至可能將低優先級的數據丟棄，從而影響了系統的正常工作。為此，本文中提出了一種基于SnPWFQ機制的調度方法來解決此問題。

1 發射控制系統工作原理分析

在發射無人機集群過程中，發射控制系統的傳感器會實時測量系統中各個環節當前狀態下的動態數據，并回傳給指揮控制節點。發射控制系統網絡構架如圖1所示。

圖1 發射控制系統網絡構架

在發射控制系統中指揮控制節點用于控制管理各個號位，即向各個號位控制節點發送指令數據、任務數據、采集數據等。每個子系統由本號位控制節點與傳感器、執行機構構成閉環的控制系統。因此，在網絡帶寬給定的情況下，當集群發射的無人機越多，發射控制系統網絡的負擔越重，故在網絡通信中，普遍采用了網絡調度技術。

在發射控制系統中，用于各個子系統自動控制的數據是實時性的，而用于更改系統工作狀態、處理意外狀態時數據是非實時性的。發射控制系統中設置網絡調度機制時，應分別為各種數據分配合適帶寬，以實現調度的公平性。同時，在發射控制系統的實時數據時某些數據是有嚴格的順序性，即發送端應將數據有序發送，否則接收端會認為數據無效而丟棄。

目前常用的隊列調度算法或者動態調度算法[3]，例如WFQ算法[4]、EDF算法[5]及其相關的改進算法等，是以獨立性數據為的假設條件，即前一時刻數據和下一時刻數據相關性為零，發送順序可以顛倒。所以無法直接應用到發射控制系統中。根據發射控制系統中數據的特點，本文提出了一種新的調度機制——SnPWFQ調度機制，以期解決發射控制系統中數據的順序性、實時性和公平性等調度問題。

2 發射控制網絡SnPWFQ調度機制

2.1 調度機制設計

發射控制系統網絡調度機制可分為3部分：狀態監控模塊、動態調度模塊、輸出調度模塊。調度機制的原理如圖2所示：

圖2 發射控制網絡調度機制原理框圖

狀態監控模塊用于接收網絡節點擬發送數據的請求，其參數包括網絡數據的優先級P，數據的截止期DL，數據的順序號Sn，發送節點的ID。在狀態監控模塊中，設置了1個輸入緩存FIFO隊列，用于存儲所接收到的請求發送數據，以避免在調度過程中丟失數據。

數據分類模塊用于將發射控制系統中的數據進行分類，并保存在各自的數據隊列中。在此模塊中設置了4個FIFO隊列，分別存儲4類發射控制網絡數據。4類數據按表1進行分類:

表1 發設控制系統網絡數據分類表

隊列Q1～Q4分別存儲4類優先級的數據,4個隊列長度為l,優先級P1>P2>P3>P4。在保存數據時,為了保證數據的實時性,每個隊列按照截止期DL從小到大的順序保存數據。

輸出調度模塊中設置了輸出緩存FIFO隊列。模塊中FIFO隊列通過SnPWFQ調度算法,將請求數據的ID放入輸出緩存FIFO隊列中,并通過CAN總線發送給所屬的節點。在此模塊中,輸入的參數是各個請求的D和ID,輸出為調度的結果。

2.2 SnPWFQ算法設計

2.2.1 WFQ算法實現方法

WFQ是一個基于虛擬完成時間的調度算法,是對GPS(通用處理器共享)調度算法的模擬實現[6]。雖然GPS 算法的服務原則是絕對公平的[7],但由于它是依據理想流模型把數據包分成無窮小的數據元。在發射控制網絡中,數據傳輸的最小單元是完整的數據幀,因此GPS算法是不可能實現的。WFQ算法是通過對GPS算法的改進,在算法中引入了虛擬時間函數和虛擬時鐘,并按照 GPS處理過程對每一個分組進行處理,是一個基于虛擬完成時間的調度算法。虛擬時間越小,則優先級越高[8-9]。

WFQ算法帶寬分配方法是:假設有事件j,ti表示到達時間,Bj表示通路,事件的權值為φi。V(t)表示虛擬時間,在服務器處于空閑狀態的所有時間均置為0。在任意忙碌周期,虛時間都從V(0)開始。V(t)可定義為:

V(0)=0

V(tj-1+τ)=V(tj-1)+τ∑i∈Bjφi

τ≤tj-tj-1,j=2,3…

(1)

設第i個隊列中的第k個數據在tk時刻到達,數據長度為Li,k。Si,k表示這個數據開始調度的時間,Fi,k表示這個數據結束調度的時間,ωi為調度器服務事件的速率。對所有的i,定義Fi,0=0,則有下面公式

Fi,0=0

Si,k=max{Fi,k-1,V(tk)}

Fi,k=Si,k+Li,kωi

(2)

在WFQ算法情況下對每幀數據所分配的帶寬為

gi=ωi∑Nj=1ωjC

C≥∑Ni=1ωi

(3)

式中,C表示數據調度平均速率。從(2)式、(3)式中可以看出,WFQ算法對數據的調度僅與數據長度和到達時間相關,可以滿足數據發送調度的要求,且能保證公平性。但是,WFQ算法并不考慮當前時刻數據的順序性,因此在實際調度中會將到達的所有數據打亂順序發送,從而無法滿足發射控制網絡中,某些順序性數據發送的需要。并且WFQ是按照各個數據的權值分配帶寬,會增大實時數據的排隊延時。

2.2.2 SnPWFQ算法

SnPWFQ算法是在WFQ算法的基礎上進行改進的產物。在帶寬分配時,將數據的隊列 優先級Pi和順序號Sn作為數據速率ω計算的因子。從而將帶寬分配計算方法從(3)式變為下式。

gi=ωi∑Nj=1ωjC

C≥∑Ni=1ωi

i∈R

(4)

式中，a為Pi的底數,b為Sn的底數。當數據為無序時,Sn=0;當為有序數據時,Sn則表示數據的順序號。

由于在控制系統中,隊列的優先級與數據的實時性級別相對應,所以,從(4)式中可以看出:在改進后的算法中,ωi與數據優先級指數成正比,與順序號指數成反比。如果數據無順序性,則Sn=0時,ωi與順序號無關。因此在隊列Qi中優先級高的數據權值較大,優先級的數據權值較小;在發射控制系統網絡中,實時性高的數據權值較大,實時性低的數據權值較小。同理對有序數據而言,順序號靠后的數據權值較小。于是SnPWFQ機制中,會將實時性較高、順序號靠前的數據分配更多的帶寬。

3 性能分析

3.1 隊列數據的公平性

公平性是發射控制系統調度機制性能的重要指標,本文采用隊列公平性指數來分析[9],即在發射控制系統中,任意2個隊列Qm,Qn在時間段[tk,tk+1]內持續產生等待發送數據,則有:

fi=LiLmin

Si(tk,tk+1)fi-Sj(tk,tk+1)fj≤M

(5)

表明此調度機制具有公平性。其中:Li表示隊列中可被成功發送的數據長度,Lmin表示隊列中可被成功發送數據的最小長度,M表示公平性指數,Si(tk,tk+1)表示在時間[tk,tk+1]內隊列Q發送的數據量。公式(5)的正確性可論證如下。

證明:假設在時間段[tk,tk+1]內隊列Qi發送的數據量為Si(tk,tk+1),令tq為隊列Qi調度一次的時間,由(4)式可知,在調度機制下,數據發送量小于存儲隊列Qi, 則有:

Si(tk,tk+1)≤li+(vout-vin)(tk+1-tk)

(6)

(tk+1-tk)=tk+1-tktqtq≤tk+1-tktq+1tq

(7)

將上式代入(6)式得到

Si(tk,tk+1)≤li+(vout-vin)tk+1-tktq+1tq

(8)

因為tq(vout-vin)=Li,所以

Si(tk,tk+1)≤li+tk+1-tktq+1Li

(9)

因為fi=LiLmin,fi>0所以

tk+1-tktq+1Lmin-Lmaxfj≤Sj(tk,tk+1)fj

(10)

代入(9)式得到

Si(tk,tk+1)fi-Sj(tk,tk+1)fj≤lifi+Lmaxfj+Lmin=M

(11)

3.2 隊列數據的實時性

在本文的調度機制中,根據公平性論證過程可得到一次調度周期的最長時間為:

Tmax=Lmaxvin-vout+lvin-vout+∑2i=1Livout

(12)

式中:Lmaxvin-vout表示隊列Q1中強實時數據的最長調度時間;lvin-vout表示隊列Q2周期性數據中的最長調度時間;Livout表示Q3和Q4中非實時的調度時間。由于在發射控制系統中Lmax≤l,vin-vout≤vout,因此在調度過程中,實時數據的調度時間遠遠小于非實時數據。即

Lmaxvin-vout≤lvin-vout≤∑2i=1Livout

(13)

設D為發射控制系統數據網絡調度延時上限,根據(13)式分析結論可知DQ1

4 仿真實驗

本文中使用的仿真實驗平臺是基于MATLAB/Simulink建立瞬態分析環境,同時加載自定義的目標配置模塊及CAN模塊。通過Simulink 模型生成硬件下可運行的代碼,實現對各個網絡節點的模擬。指揮控制節點計算機操作系統采用Windows+RTX的架構,各個號位控制節點的微處理器采用Freescale公司的MPC82XX系列處理器,操作系統為VxWorks5.5.1。

4.1 實時性仿真

硬件平臺設置如下:共設置10個CAN總線節點,分別模擬了指揮控制節點和9個發射號位節點。CAN總線速率設置為500 kb/s,4類數據長度均為16byte。分別采用本文的調度機制、WFQ算法以及動態EDF算法進行了網絡通信實驗。

實驗方法如下:設置網絡中各個節點時鐘處于同步狀態;在實時性數據報文內容填入節點發送時間tout,最小單位為0.1 ms,接收端接收到數據后在數據報文中填入接收時間tin,仿真軟件根據公式d=tout-tin計算延時。本論文分別取指揮控制節點和第3號位節點的延時數據,對比3種調度算法,結果如下:

圖3 指揮指控節點數據延時對比

圖4 3號位節點數據發送延時對比

圖3、圖4表明在實時數據傳輸時,采用本文方法數據傳輸延時與EDF算法的延時比較接近。而采用WFQ算法,系統延時較大。

4.2 公平性仿真實驗

硬件平臺設置如下:在仿真系統中設置CAN節點共10個,分別模擬了指揮控制節點和9個發射號位節點,設置CAN總線速率為256 kb/s～1Mb/s的變化范圍,網絡中4類數據長度均為8 byte,發送周期為20 ms,分別采用本文方法、WFQ算法以及動態EDF算法進行了網絡通信實驗。通過統計系統數據丟包的情況分析每種算法對公平性的影響。

實驗方法如下:系統工作后,所有節點將發送節點號、接收節點號、順序號和計數周期填入要發送的數據包中;系統工作3分鐘,每個接收節點將接收到數據包的順序號上傳給仿真軟件進行分析。其中發送端的順序號位連續計數,從0計數到255,滿255后從0重新開始計數,計數周期+1。如果數據包未發送成果則仿真軟件無法收到對應的順序號。

丟包率計算公式為r=∑n/∑m×100%,其中r表示丟包率,m表示所有節點發送報文的數量,n表示系統中報文丟失的數量。本實驗中順序性數據的Snmax=20。以指揮控制節點和3號位節點進行統計和分析,結果如下:

圖5 指揮控制節點數據丟失統計分析

從圖中可以看出，當網絡帶寬越高，3種方法法的丟包率越來越小。在帶寬較低的情況下，本文方法與WFQ算法的丟包率相差不大，說明本算法在公平性上與WFQ算法相一致。

圖6 3號位節點數據丟失統計分析

同時在仿真實驗中發現，經WFQ算法和EDF算法調度后的有序數據已無法保持原有的順序性。在實際應用中，這類數據即使成功傳輸給接收端，接收端無法正常執行相關動作，從而導致系統無法正常工作。

5 結 論

本文提出了基于優先級和順序性的SnPWFQ算法，通過理論分析和仿真實驗結果表明，此算法能夠滿足無人機集群發射控制系統中，網絡數據的順序性、公平性和實時性要求，在無人機集群發射應用中有重要意義。但由于本算法是對WFQ算法進行改進而得，因此，仍需要實時更新虛擬時間集合。所以如何簡化虛擬時間計算，仍是作者以后的主要研究方向。

參考文獻：

[1] 牛軼峰,肖湘江,柯冠巖. 無人機集群作戰概念及關鍵技術分析[J]. 國防科技，2013，35(5)：37-43

Niu Yifeng, Xiao Xiangjiang, Ke Guanyan. Operation Concept and Key Techniques of Unmanned Aerial Vehicle Swarms[J]. National Defense Science & Technology, 2013, 35(5)：37-43 (in Chinese)

[2] 徐超,李正平,汪長勤. 基于CSMA/CD的CAN總線訪問的建模與仿真的研究[J]. 儀器儀表學報,2008,29(4):866-869

Xu Chao, Li Zhengping, Wang Changqin. Research on Modeling and Simulation of CAN Bus Access Based on CSMA/CD[J]. Chinese Journal of Scientific Instrument, 2008,29(4): 866-869 (in Chinese)

[3] Hasnaoui S, Bouallegue A. A Proposal Modification of CAN Protocol to Support a Dynamic Priority Policy Being Able to Be Implemented on CAN Fieldbus Controller Components[C]∥Industry Applications Conference, 2000

[4] He Dongzhi , Wang Feiyue, Li Wei. Dynamic Preemption Threshold Scheduling for Specific Real-Time Control Systems[C]∥Proceedings of the 2005 IEEE Networking, Sensing and Control. Tucson Arizona, 2005 :395-400

[5] Magana E, Morato D, Varaiya P. Tuning the Weights in WFQ Schedulers for the Maximization of Carried Best Effort Traffic[C]∥10th International Conference on Telecommunications, 2003: 917-922

[6] 晉曉輝，李建東，劉乃安．WFQ的兩種簡化實現方法及性能分析[J]．西安電子科技大學學報：自然科學版:2002,29(2):178-195

Jin Xiaohui, Li Jiandong, Liu Naian. Two Simple Implementation Algorithms of WFQ and Their Performance Analysis[J]. Journal of Xidian University, 2002,29(2):178-195 (in Chinese)

[7] 王重鋼，隆克平，龔向陽． 分組交換網絡中隊列調度算法的研究及其展望[J]． 電子學報，2001，29(4) : 553-559

Wang Chonggang, Long Keping, Gong Xiangyang. The Study and Perspective of Queue Scheduling Algorithms in Packet Switching Networks[J]. Acta Elecoronica Sinica, 2001，29(4): 553-559 (in Chinese)

[8] 李秉權，張松，王兆偉,等. WFQ與WRR 調度算法的性能分析與改進[J]. 北京理工大學學報,2015，35(3)：316-320

Li Bingquan, Zhang Song, Wang Zhaowei, et al.,Performance Analysis and Improvement about WFQ and WRR Schedule Algorithm[J]. Transactions of Beijing Institute of Technology, 2015，35(3):316-320 (in Chinese)

[9] Shreedhar M, Varghese G. Efficient Fair Queueing Using Deficit Round Robin[C]∥IEEE/ACM Trans on Networksing,1996