最早截止期優(yōu)先的網絡控制系統(tǒng)動態(tài)調度研究

夏榮坤，蔣蓉蓉，胡天水

(1.安徽工程大學，安徽 蕪湖 241000；2.安徽檢測技術與節(jié)能裝置省級實驗室，安徽 蕪湖 241000)

?

最早截止期優(yōu)先的網絡控制系統(tǒng)動態(tài)調度研究

夏榮坤1,2，蔣蓉蓉1,2，胡天水1,2

(1.安徽工程大學，安徽 蕪湖 241000；2.安徽檢測技術與節(jié)能裝置省級實驗室，安徽 蕪湖 241000)

網絡控制是涉及計算機技術、自動控制技術、通信技術和最優(yōu)化理論等的綜合學科，網絡調度對網絡控制系統(tǒng)性能的影響是近年來國際學術界研究的熱點。介紹了網絡控制系統(tǒng)的基本組成和可調度性分析方法，提出一種由實時任務調度理論改進的網絡動態(tài)調度理論——最早截止期優(yōu)先(EDF)動態(tài)調度算法，并在控制器局域網絡下采用Truetime與Simulink仿真工具共同構建了多回路的網絡控制系統(tǒng)。仿真實驗結果表明：最早截止期優(yōu)先動態(tài)調度算法可以在不確定的網絡環(huán)境下使各回路控制器性能達到最優(yōu)。

網絡控制系統(tǒng)；網絡調度；最早截止期優(yōu)先

網絡控制系統(tǒng)(network control system,NCS)是一種通過共享通信或控制網絡實現(xiàn)空間分布的各個節(jié)點(傳感器、控制器和執(zhí)行器)之間的信息傳輸，從而對被控對象進行反饋控制的系統(tǒng)[1]。由于各個節(jié)點共同競爭網絡資源，且網絡資源的承受負載節(jié)點能力和帶寬資源有限，這使得信息交互過程中任務信息的屬性總是不確定的，網絡中的節(jié)點在發(fā)送數(shù)據(jù)信息和發(fā)生碰撞時，必然存在信息傳輸?shù)南群蟠涡騿栴}。在這種情況下，引入有效的調度策略解決信息傳輸時發(fā)生的碰撞問題可改善網絡問題對控制系統(tǒng)性能的影響[2]。

本文以CAN總線為網絡環(huán)境，采用最早截止期優(yōu)先[3](earliest deadline first,EDF)調度算法來處理任務執(zhí)行過程中任務屬性和網絡環(huán)境的不確定問題。通過對網絡可調度性和動態(tài)調度策略的分析，采用TrueTime與Matlab-Simulink仿真工具對網絡控制系統(tǒng)仿真，分析調度策略改善網絡環(huán)境的狀態(tài)。仿真結果顯示EDF調度能有效地改善網絡控制系統(tǒng)的運行性能。

1 最早截止期優(yōu)先的動態(tài)調度算法

1.1 網絡控制系統(tǒng)調度

NCS網絡調度和CPU實時調度相似，均存在有限共享資源的限制，同時均需為并發(fā)任務分配共享資源、周期性激發(fā)任務以及滿足任務截止期要求[4]。在網絡調度中，各個節(jié)點對網絡資源的競爭與CPU實時任務調度的CPU內存資源相對應，控制局域網絡中多節(jié)點向網絡上傳的消息與CPU處理器中被調度的多個待處理的進程。 研究分析網絡控制系統(tǒng)動態(tài)調度理論可參照CPU實時調度理論，利用該理論研究信息在網絡傳輸過程中的調度問題[5]。

1.2 網絡傳輸任務參數(shù)

1) 接收結束時刻ai：打包好的信息，開始進入等待發(fā)送隊列的時刻。

2) 發(fā)送起始時刻si：待發(fā)送的信息打包后，開始發(fā)送的時刻。

4) 網絡傳輸時間ci：經網絡傳輸，數(shù)據(jù)包經源地址傳輸?shù)侥康牡刂匪脮r間，取決于網絡介質的速率和數(shù)據(jù)包大小等因素。

5) 完成時刻fi：數(shù)據(jù)包經網絡傳輸?shù)竭_目的地址的時間點。

6) 網絡傳輸時延τi：待發(fā)送的信息開始打包到傳輸?shù)男畔?shù)據(jù)包到達目標節(jié)點所需的時間。

7) 網絡傳輸時限(截止期)di：為確保網絡控制系統(tǒng)的穩(wěn)定運行，包含控制信息的數(shù)據(jù)包在網絡傳輸過程中人為設定一個時限，如發(fā)送超時、響應超時等。這些超時時間稱之為時限，一般為了簡化數(shù)學分析，假設di=ai+hi。

圖1 網絡傳輸任務時間參數(shù)

1.3EDF動態(tài)調度算法

針對計算機實時系統(tǒng)，由Liu和Layland提出的搶占式EDF算法[6]給出了可調度性判斷，具體如下：在計算機實時系統(tǒng)中，CPU內存資源固定不變，各個內部進程包含不同的實時任務，CPU根據(jù)調度算法得出的優(yōu)先級實時有序地處理各個進程任務。其中：CPU根據(jù)任務距離截止期di的長短動態(tài)分配任務的優(yōu)先級；當任務距離截止期時長越短時，該任務具有較高的優(yōu)先級；相反，距離截止期越長的任務其優(yōu)先級越低。將該理論推廣到網絡控制系統(tǒng)的研究中，得出基于網絡控制系統(tǒng)的EDF調度算法[7]。應用研究表明該算法是最優(yōu)的動態(tài)優(yōu)先級調度算法。

引理[8-9]在網絡控制系統(tǒng)中，有n個非搶占優(yōu)先的周期采樣任務(根據(jù)任務優(yōu)先級遞減排序，i=1 表示優(yōu)先級最高，i=N表示優(yōu)先級最低)。如果對于所有的i=1,2,…,N滿足：

1.4 調度性分析

非搶占優(yōu)先EDF算法可調度定理分析[10-11]：設T={T1,T2,…Tn} 是存在的n個傳輸任務，其中，一系列該任務集Ti(ci,hi)按周期遞增順序排列，ci為網絡傳輸任務的傳輸時間，即傳輸時延，di為傳輸任務Ti的截止期(di=hi)，則當且僅當以下條件成立時，在非搶占優(yōu)先EDF調度算法下這組任務集可調度：

設多回路網絡控制系統(tǒng)有4個回路，傳輸任務的時間屬性(單位：ms)如下：

令t=hi-1,t′=1，則網絡利用率為

下面列出當i取不同值時任務集的時間需求關系：

2 實驗仿真與結果分析

2.1 網絡控制系統(tǒng)仿真平臺的構建

Truetime是由The Lund University和Anton Cervin、Dan Henriksson等學者共同開發(fā)的一種網絡控制系統(tǒng)仿真工具箱，它能夠支持實時控制與網絡調度的仿真，并可以對網絡傳輸時延、網絡參數(shù)對控制系統(tǒng)性能的影響等進行仿真研究，從而為網絡控制系統(tǒng)的研究提供了一個仿真依據(jù)[12]。

利用Simulink和Truetime工具箱搭建一個三控制回路的網絡控制系統(tǒng)仿真平臺。仿真模型如圖2所示。

圖2 網絡控制系統(tǒng)仿真模型

圖2中，3個相同的直流電機模型與對應的PID控制器在同一CAN網絡環(huán)境下?？刂破?、執(zhí)行器、調度器均采用事件驅動方式，其中調度器由內部的3個周期采樣模塊驅動，其采樣周期分別為h1=2 ms,h2=5 ms,h3=7 ms。

2.2 仿真結果

EDF動態(tài)調度策略下干擾節(jié)點和調度器、控制器等節(jié)點的調度情況如圖3所示。干擾節(jié)點動態(tài)地占用了網絡帶寬，其優(yōu)先級最高。調度器節(jié)點、控制器節(jié)點以及執(zhí)行器節(jié)點并不是在網絡空閑時依次發(fā)送數(shù)據(jù)，而是按照不同控制回路的數(shù)據(jù)發(fā)送距離截止時限的長度來對它們的發(fā)送優(yōu)先級進行動態(tài)調整。

圖3 3個回路EDF策略調度圖

圖3中，調度器中采樣模塊的數(shù)據(jù)傳輸時序圖的尖刺是由于該節(jié)點與優(yōu)先級較高的節(jié)點同時爭用網絡發(fā)送權造成的。

網絡控制系統(tǒng)中3個控制回路的方波響應以及相應的控制率ui如圖4～6所示。從圖可以看出：在網絡資源受限且不穩(wěn)定時，EDF動態(tài)調度考慮不同回路數(shù)據(jù)的緊急程度，故能使系統(tǒng)性能得到較大的改善。

圖4 回路1方波響應及控制率

圖5 回路2方波響應及控制率

圖6 回路3方波響應及控制率

3 結束語

網絡調度在很大程度上影響著網絡控制系統(tǒng)性能的優(yōu)劣[13,14]，即在網絡環(huán)境下，多個控制回路中的節(jié)點共同占用有限的網絡資源，合理地分配網絡資源以及如何決定數(shù)據(jù)包發(fā)送的優(yōu)先級是網絡控制系統(tǒng)面臨的主要問題。本文將實時調度理論運用到網絡控制系統(tǒng)中，給出了一種最優(yōu)的動態(tài)優(yōu)先級調度算法——最早截止期優(yōu)先動態(tài)調度算法。該算法在實際應用中可以根據(jù)調度任務距離截止期的長短動態(tài)分配任務優(yōu)先級，具有較強的環(huán)境適應性。仿真結果表明在網絡控制系統(tǒng)中，該算法可以明顯提高網絡控制系統(tǒng)運行的穩(wěn)定性。

[1] Antsaklis P,Baillieul J.Special issue on technology of networked control systems[C]//Proceedings of IEEE Special Issue on the Emerging Technology of Networked Control Systens.USA:[s.n.]，2007,95(1):5-8.

[2] 李祖欣，王萬良，雷必成.網絡控制系統(tǒng)中的調度問題[J].計算機工程與應用，2007，43(16)：241-245.

[3] Jeffek K,Stanat D F,Martel C U.On non-preemptive scheduling of periodic and sporadic tasks[C]//Proc of the 12thReal-time System Symposium.Washington DC:IEEE Computer Socity,1991:129-139.

[4] 陳惠英.資源受限網絡控制系統(tǒng)控制與調度方法研究[D].杭州：浙江工業(yè)大學，2008.

[5] Velasco M.A control approach to bandwidth management in networked control systems [C]//Proceedings of the 30th IEEE Annual Conference on Industrial Electronics Society.New York:[s.n.],2004:2343-2348.

[6] Liu C L,Layland J W.Scheduling algorithms for multiprogramming in a hard real-time environment[J].Journal of the ACM,1973,20(1):46-61.

[7] 王素青，姜維福.基于Truetime的網絡控制系統(tǒng)調度算法的仿真研究[J].工業(yè)控制計算機，2008，21(12)：46-48.

[8] 陸軍，楊明.不同驅動方式下網絡控制系統(tǒng)的建模與分析[J] .信息技術，2008，3(2)：48-50.

[9] 王巖，孫增圻.網絡控制系統(tǒng)分析與設計[D] .北京：清華大學出版社，2009，47-58.

[10]彭軍，吳敏.CAN總線中EDF調度算法的研究與改進[J].計算機測量與控制，2008，16(11):1678-1681.

[11]張杰，陽富民.EDF實時調度算法中的關鍵問題求解[J].華中科技大學學報:自然科學版，2009,37(10):134-136.

[12]張湘,肖建.網絡控制系統(tǒng)的TrueTime分析與仿真[J]．蘭州交通大學學報，2010，29(3):104-107.

[13]邢群科，郝紅衛(wèi).兩種經典實時調度算法的研究與實現(xiàn)[J].計算機工程與設計，2006，27(1):117-120.

[14]杜大軍，費敏銳，宋 楊，等．網絡控制系統(tǒng)的簡要回顧及展望[J]．儀器儀表學報，2011，32(3)：713-720.

(責任編輯 楊黎麗)

Research on Earliest Deadline First Network Control System Dynamic Scheduling

XIA Rong-kun1,2, JIANG Rong-rong1,2, HU Tian-shui1,2

(1.Anhui Polytechnic University, Wuhu 241000, China; 2.Anhui Key Laboratory of Detection Technology and Energy Saving Devices, Wuhu 241000, China)

Networked control system is a comprehensive subject of integrated computer technology, automatic control, communication technology, optimization theory, and so on. The effect of network scheduling on the property of network control system is a hot issue in the research of international academic circles in recent years. This paper introduced the basic composition and network control system schedulability analysis method, and put forward a network dynamic scheduling theory improved by real-time scheduling theory- Earliest Deadline First (EDF) dynamic scheduling algorithm, and constructed multi loop networked by using Truetime and Simulink toolbox under CAN network. Simulation results show that the first dynamic scheduling algorithm of earliest deadline can make the optimal performance of each loop controller in the uncertain network environment.

Network control system; Network scheduling; earliest deadline priority

2014-11-27 基金項目：國家自然科學基金資助項目(61172131，61203034)；安徽省自然科學基金資助項目(1308085QF120)

夏榮坤(1989—)，男，安徽蕪湖人，碩士研究生，主要從事網絡控制系統(tǒng)方面研究。

夏榮坤，蔣蓉蓉，胡天水.最早截止期優(yōu)先的網絡控制系統(tǒng)動態(tài)調度研究[J].重慶理工大學學報：自然科學版，2015(3):105-109.

format：XIA Rong-kun, JIANG Rong-rong, HU Tian-shui.Research on Earliest Deadline First Network Control System Dynamic Scheduling[J].Journal of Chongqing University of Technology:Natural Science,2015(3):105-109.

10.3969/j.issn.1674-8425(z).2015.03.020

TP301.6

A

1674-8425(2015)03-0105-05