基于圖論的網絡控制系統動態調度策略研究

梅志慧，魏利勝，王家才

（安徽工程大學 電氣工程學院，安徽 蕪湖 241000）

網絡控制系統（Networked Control Systems，NCSs）是計算機網絡技術、工業控制技術及通信技術等學科理論的交叉、滲透和融合的產物，它可以滿足高產量和高生產率的業務需求，給實際工業控制和經營決策提供了一種新的解決途徑，在促進國家經濟、社會、國防等領域的信息化發展中發揮著特殊的作用[1].但是，由于NCSs的控制器與被控對象之間嵌入了通信網絡，導致其性能分析和系統設計變得非常復雜和困難，因此，如何從通信的角度研究NCSs調度策略，通過合理分配和管理網絡資源以保證NCSs服務質量和控制質量，已成為一些從事NCSs科研工作者們努力的方向，并取得了初步研究成果.王艷[2]等提出了一種基于通信網絡的動態調度器，實時調節控制系統的采樣周期；陳文穎[3]等設計了一種適合網絡環境的狀態觀測器，對數據丟包和時延進行了適當補償；李金娜[4]等基于Lyapunov方法和圖論理論，提出了一種新的穩定性判據，給出非線性離散和連續網絡控制系統漸近穩定的充分條件，獲得保持這兩類系統穩定的最大允許時延界；另外，游科友[1]等提出了基于圖論的控制系統研究，為網絡控制系統調度策略的研究開辟了新的方向.

本文將在以上研究成果的基礎上，進一步將圖論中的網絡流理論與調度策略相結合，引入到NCSs的路徑規劃中，并采用EDF優化網絡帶寬的分配，降低網絡誘導時延和數據流量，以獲取更好的網絡服務質量和通信性能.

1 基于圖論的NCSs路徑優化

網絡可以定義為具有兩個不同的特定頂點x和y的加權連通圖（D，w），記為N＝（Dxy，w），其中x和y分別代表發射點和接收點[5-9]，D代表權值，Dxy為頂點x和頂點y之間連線的權值，w為容量函數，假設w為非負的容量函數c，則網絡N＝（Dxy，c）被稱為容量網絡，其中c在邊a上的值c（a）稱為邊a的容量.如果對任何a∈E（D），c（a）都是非負整數，則成N為整容量網絡.為使進、出網絡節點的數據所經過的傳輸距離最短，滿足數據對網絡“實時性”的需求，同時實現現有網絡動態分配的使用效率達到最大化，我們將采用網絡流理論優化網絡資源的配置[10-11].

某時間段內網絡節點的傳輸數據匯總情況如表1所示.考慮到網絡數據傳輸過程中，節點發送或接收所占比例甚多，則網絡中節點發送、接收數據路徑最短的實施步驟具體如下：

步驟1：按照節點使用時間的先后順序，將網絡節點之間由左到右進行有向連線，方向為數據傳輸開水時間從早到晚，從而形成由節點和箭頭組成的網絡圖，從起點到終點的每一條有向路徑上的節點都可以作為傳輸同一數據的節點組合.節點一次編號網絡圖如圖1所示.

表1 假設某一時間段內網絡中各節點傳輸數據匯總

步驟2：在圖1基礎上，按照各節點的時間順序進行二次編號N（A，B），N表示編號，A表示N的前一個編號（若為起始點，則其編號為本身），B表示傳輸速率的累計，即前一個節點A的傳輸速率與本節點B傳輸速率之和.需要注意的是，如果A前有兩個或多個已編號的節點，則選擇B最大的那個節點，作為N的前一個編號.節點二次編號網絡圖如圖2所示.

步驟3：假設圖2中每個節點的傳輸速率代表節點的傳輸流量，傳輸速率越快，傳輸流量越大，從終點開始逆向尋找一個至起點傳輸速率最快的路徑，并把這條路徑上的節點安排給優先級最高的數據使用.在圖2中，01-04-07即為該網絡圖中傳輸流量最大的網絡節點組合，可以將這個節點組合按照節點開始時間的先后順序分配給優先級最高的數據源使用.

步驟4：在網絡圖上去掉01-04-07的節點及其相關的箭頭，再從新的起點開始尋找一條至終點傳輸速率最快的路徑，并把這條路徑上的節點安排給次優先級的數據使用.節點三次編號網絡圖如圖3所示.由圖3可知，02-06-08即為該網絡圖中傳輸流量最大的網絡節點組合，可以將這3個節點按照節點數據傳輸開始時間的先后順序分配給次優先級最高的數據源使用.

步驟5：重復以上步驟，此時網絡圖中僅剩下03和05網絡節點，可依據傳輸流量的大小再次進行優先級的分配，直至所有節點分配完成.

圖1 節點一次編號網絡圖

圖2 節點二次編號網絡圖

圖3 節點三次編號網絡圖

2 EDF調度策略

EDF（Earliest Deadline First）調度算法又稱為最早時限優先調度算法[12]，該算法根據任務距離時限要求的大小來分配任務的優先級，距離時限越小的任務獲得的優先級越高，反之越低.在這種調度算法的調度下，任務的優先級是不斷變化的，因此它是一種動態調度算法，能夠動態地調節信息的優先級.在信息負載較重的情況下，能夠使得有限的資源得到更加合理分配，從而使得某些軟實時系統在不可調度情況下，同樣能夠獲得期望的性能.一組n個相互獨立實時周期信息，用EDF調度算法的可調度條件：

3 仿真實驗

在Matlab／Simulink仿真環境下，構建一個由4個網絡控制子系統、1個干擾源和1個有線網絡組成的網絡控制系統[13-14]，如圖4所示.其中子系統的內部結構如圖5所示.仿真參數設置如下：

（1）被控對象傳遞函數.

（2）所有傳感器節點均采用時間驅動方式對過程進行周期性采樣，采樣周期設為h＝0.001 s.

圖4 NCSs仿真模型

圖5 子系統內部結構圖

（3）所有控制器節點采用離散的PⅠD控制算法.

其中，r（k）為讀取的輸入參考值，通過調用系統函數tt AnalogIn（1）從信號發生器中獲??；y（k）為讀取的傳感器傳輸的采樣值，通過調用系統函數tt Get Msg獲??；h＝0.001 s為采樣周期；k＝1.5為比例系數；Ti＝0.12為積分系數；Td＝0.035為微分系數；以上參數均在傳感器及控制器的初始化程序中完成.

（4）采樣值首先通過網絡發送到控制器節點，控制器接收到采樣值后首先計算控制信號，然后將計算結果發送到執行器節點，執行器節點隨后執行該控制信號，工作方式是事件驅動，并將其傳送到傳感器節點，傳感器節點收到執行器節點傳送來的信號后做出回應，將信號向相應網絡節點發送.

（5）執行器接收并執行控制器傳過來的任務信號，因為仿真中采用的是EDF算法，所以對于執行器截止時間并不做嚴格限制，這里設置默認其一直處于工作狀態.

（6）在仿真中引入了一個干擾源，具有高優先級，它發送的信號通過在計算機節點中執行，來模擬網絡通信中的干擾，干擾周期設置為0.001 s，干擾數據速率設置為100 bit／s.

（7）網絡模型選用CAN總線，其網絡數據傳輸速率為20 Mbit／s，其帶寬資源配置方式需進行初始化設置，使其在每次執行傳輸任務的同時，重新對帶寬資源進行計算并重新分配.

4 仿真分析

建模時，每個子系統的時延、任務優先級、任務周期、傳輸速率、調度策略等參數的設置均不相同，并設置干擾信號占用了網絡20%的帶寬資源，系統的采樣時間取為0.01 s，傳感器到控制器的傳輸時延為0.002～0.005 s不等，控制器本身的計算時延為0.005 s，控制器到執行器的傳輸時延為0.002～0.005 s不等.通過以上設置，來模擬一個存在網絡時延和網絡丟包的通信環境[15].

在通信環境中加入干擾信號后，不同對象輸出在經過網絡傳輸后，其跟蹤參考輸入r（k）的變化曲線也不盡相同，信號振蕩幅度表明了在網絡傳輸過程中對信號造成的影響（包括時延、丟包、誤差等）.當系統存在網絡干擾造成延時時，在調度策略的影響下，所有任務均能夠在其截至日期之前結束.但是，系統的品質明顯變差.如果時延繼續增大，系統就有可能不穩定，并且，如果加大干擾所占帶寬資源的比例，其對網絡傳輸造成的影響也將是致命的.

為解決這一問題，根據本文給出的方法來解決網絡資源的協議問題，對有限的帶寬資源進行最大化利用，不僅可以提高傳輸的效率，且省去了對調度算法的再次復雜編程，從而解決外部干擾對信號傳輸造成的影響.因此，這里對網絡初始化模塊中的出、入口函數重新進行定義之后，得到不一樣的響應曲線，改進前和改進后兩種調度方法得出的響應曲線的比較圖如圖6所示.其中，實線方波代表參考信號r（k），虛線代表在EDF調度策略的響應曲線，點線代表基于圖論的動態調度策略的響應曲線.從圖6中可以更為直觀地觀察兩種算法的運行效果.以上仿真結果驗證了改進后的調度策略優勢所在，采用新的資源分配方式大大提高了信號傳輸的可靠性，同時也提高了系統的穩定性，因此改進后的調度策略具有很好的可行性.

圖6 兩種調度策略結果的比較圖

5 結論

本文在EDF調度策略研究的基礎上引入圖論思想，構建了節點的網絡分配模型，并利用Matlab仿真環境建立仿真模型，驗證了圖論思想在網絡動態調度中應用的可行性.說明Matlab可以為研究控制與通信網絡的復雜系統提供一個良好的實驗平臺，并具有一定的指導意義.

[1]游科友，謝立華.網絡控制系統的最新研究綜述[J].自動化學報，2013，39（2）：101-118.

[2]王艷.網絡控制系統的控制與調度研究[D].南京：南京理工大學，2006：56-68.

[3]陳文穎.網絡控制系統的穩定性研究及調度策略[D].北京：華北電力大學，2010.

[4]李金娜，張慶靈，于海斌.網絡控制系統穩定性的圖理論[J].控制理論與應用，2009，11：1 309-1 315.

[5]方富貴.圖論的算法和應用研究[J].計算機與數字工程，2012，2：115-117，132.

[6]許培，陳其工，葛愿.具有隨機丟包的無線網絡控制系統仿真研究[J].安徽工程大學學報：自然科學版，2013，28（3）：59-61.

[7]田中大，高憲文，史美華，等.資源受限網絡控制系統的模糊反饋調度[J].電機與控制學報，2013，1：94-101.

[8]張水艦，劉學軍，楊洋.動態隨機最短路徑算法研究[J].物理學報，2012，16：1-10.

[9]程遠.網絡最短路徑的一種更新策略[J].計算機應用與軟件，2013，1：171-175.

[10]王晶，戴君.不確定交通網絡中可靠路徑選擇模型與算法[J].統計與決策，2014，6：21-24.

[11]黃冠利，呂江毅，廉詩陽.動態路徑優化交通流控制及其仿真實現[J].測控技術，2014，1：148-152.

[12]袁暋，檀明.EDF調度算法可調度性分析方法的改進研究[J].計算機應用研究，2013，8：2 429-2 431.

[13]王萬良，蔣一波，李祖欣，等.網絡控制與調度方法及其應用[M].北京：科學出版社，2009.

[14]劉興光.網絡控制系統中的優化調度方法仿真[J].計算機仿真，2013，12：269-272.

[15]TIPSUWAN Y，KAMONSANTIROJ S，SRISABYE J，etal.An auction-based dynamic bandwidth allocation with sensitivity in a wireless networked control system[J].Computers ＆Industrial Engineering，2009，57：114-124.