夏榮坤，蔣蓉蓉，胡天水

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

?

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1.4 調(diào)度性分析

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

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

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

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

2 實(shí)驗(yàn)仿真與結(jié)果分析

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

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

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

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

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

2.2 仿真結(jié)果

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

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

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

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

圖4 回路1方波響應(yīng)及控制率

圖5 回路2方波響應(yīng)及控制率

圖6 回路3方波響應(yīng)及控制率

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

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

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

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

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

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

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

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

[14]杜大軍，費(fèi)敏銳，宋 楊，等．網(wǎng)絡(luò)控制系統(tǒng)的簡(jiǎn)要回顧及展望[J]．儀器儀表學(xué)報(bào)，2011，32(3)：713-720.

(責(zé)任編輯 楊黎麗)

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 基金項(xiàng)目：國(guó)家自然科學(xué)基金資助項(xiàng)目(61172131，61203034)；安徽省自然科學(xué)基金資助項(xiàng)目(1308085QF120)

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

夏榮坤，蔣蓉蓉，胡天水.最早截止期優(yōu)先的網(wǎng)絡(luò)控制系統(tǒng)動(dòng)態(tài)調(diào)度研究[J].重慶理工大學(xué)學(xué)報(bào)：自然科學(xué)版，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