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

夏榮坤，蔣蓉蓉，胡天水

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

?

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

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

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

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

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

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

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

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

1.1 網(wǎng)絡控制系統(tǒng)調(diào)度

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

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

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

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

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

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

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

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

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

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

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

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

1.4 調(diào)度性分析

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

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

令t=hi-1,t′=1，則網(wǎng)絡利用率為

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

2 實驗仿真與結(jié)果分析

2.1 網(wǎng)絡控制系統(tǒng)仿真平臺的構(gòu)建

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

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

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

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

2.2 仿真結(jié)果

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

圖3 3個回路EDF策略調(diào)度圖

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

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

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

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

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

3 結(jié)束語

網(wǎng)絡調(diào)度在很大程度上影響著網(wǎng)絡控制系統(tǒng)性能的優(yōu)劣[13,14]，即在網(wǎng)絡環(huán)境下，多個控制回路中的節(jié)點共同占用有限的網(wǎng)絡資源，合理地分配網(wǎng)絡資源以及如何決定數(shù)據(jù)包發(fā)送的優(yōu)先級是網(wǎng)絡控制系統(tǒng)面臨的主要問題。本文將實時調(diào)度理論運用到網(wǎng)絡控制系統(tǒng)中，給出了一種最優(yōu)的動態(tài)優(yōu)先級調(diào)度算法——最早截止期優(yōu)先動態(tài)調(diào)度算法。該算法在實際應用中可以根據(jù)調(diào)度任務距離截止期的長短動態(tài)分配任務優(yōu)先級，具有較強的環(huán)境適應性。仿真結(jié)果表明在網(wǎng)絡控制系統(tǒng)中，該算法可以明顯提高網(wǎ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] 李祖欣，王萬良，雷必成.網(wǎng)絡控制系統(tǒng)中的調(diào)度問題[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] 陳惠英.資源受限網(wǎng)絡控制系統(tǒng)控制與調(diào)度方法研究[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的網(wǎng)絡控制系統(tǒng)調(diào)度算法的仿真研究[J].工業(yè)控制計算機，2008，21(12)：46-48.

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

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

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

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

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

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

[14]杜大軍，費敏銳，宋 楊，等．網(wǎng)絡控制系統(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—)，男，安徽蕪湖人，碩士研究生，主要從事網(wǎng)絡控制系統(tǒng)方面研究。

夏榮坤，蔣蓉蓉，胡天水.最早截止期優(yōu)先的網(wǎng)絡控制系統(tǒng)動態(tài)調(diào)度研究[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