鄧蘇 王嶸 王志飛 黃宏斌

目前,世界安全環(huán)境更加復(fù)雜,新軍事變革的方向、趨勢(shì)日趨清晰.從世界發(fā)生的幾場(chǎng)局部戰(zhàn)爭(zhēng)看,一體化聯(lián)合作戰(zhàn)在軍事對(duì)抗中的核心效應(yīng)日益顯現(xiàn).該作戰(zhàn)體系包括情報(bào)、打擊、防護(hù)、保障、動(dòng)員等系統(tǒng)要素,各要素之間相互聯(lián)系、相互影響、相互制約,形成了一個(gè)有機(jī)整體.在信息技術(shù)的支持和一體化信息網(wǎng)絡(luò)系統(tǒng)的支撐下,一體化聯(lián)合作戰(zhàn)構(gòu)建各作戰(zhàn)力量、作戰(zhàn)單元、作戰(zhàn)要素間無(wú)縫鏈接的信息網(wǎng)絡(luò)體系,形成實(shí)時(shí)獲取、高效傳輸、資源共享的信息流程,得以實(shí)時(shí)感知作戰(zhàn)對(duì)象及戰(zhàn)場(chǎng)資源的動(dòng)態(tài)位置及其作戰(zhàn)行動(dòng),最大限度地縮短“發(fā)現(xiàn)—決策—行動(dòng)”的時(shí)間,實(shí)現(xiàn)實(shí)時(shí)一體聯(lián)動(dòng),謀求諸軍、兵種全維整體作戰(zhàn)的優(yōu)勢(shì).

1 問(wèn)題的提出

1.1 軍事需求

一體化聯(lián)合作戰(zhàn)要求各作戰(zhàn)資源實(shí)現(xiàn)實(shí)時(shí)聯(lián)動(dòng)、科學(xué)組合、彼此交融,以達(dá)到結(jié)構(gòu)互補(bǔ)和效能耦合.因此,如何科學(xué)、合理地組織戰(zhàn)場(chǎng)資源,如何有效地管理和調(diào)度資源來(lái)執(zhí)行各種任務(wù),在正確的時(shí)間為不同軍事任務(wù)提供正確的資源,是實(shí)現(xiàn)戰(zhàn)場(chǎng)指揮控制有序、有效、有力的重要保證.

近些年來(lái)隨著戰(zhàn)場(chǎng)傳感器技術(shù)的發(fā)展和武器系統(tǒng)智能化的程度不斷提高,C4ISR系統(tǒng)已經(jīng)發(fā)展到C4KISR系統(tǒng).但是,這些研究更多地停留在概念的層次上,仍有許多關(guān)鍵技術(shù)亟待突破.現(xiàn)有的C4KISR系統(tǒng)并沒(méi)有將信息域與物理域密切融合,信息處理與物理過(guò)程相互隔離,導(dǎo)致了物理過(guò)程和信息處理之間的相互影響被忽視,嚴(yán)重影響了“傳感器到射手”能力的實(shí)現(xiàn),制約一體化聯(lián)合作戰(zhàn)的效能發(fā)揮.

隨著計(jì)算機(jī)技術(shù)、電子與信息技術(shù)、智能控制技術(shù)以及網(wǎng)絡(luò)通信技術(shù)的不斷發(fā)展,人們提出了融合信息處理與物理過(guò)程的智能系統(tǒng)新概念:信息物理融合系統(tǒng)(Cyber physical system,CPS)[1].關(guān)于CPS系統(tǒng)尚未有普遍認(rèn)可的統(tǒng)一定義,但一般是指信息處理和物理過(guò)程緊密融合與協(xié)作的系統(tǒng)[2].中國(guó)科學(xué)院的何積豐院士認(rèn)為CPS強(qiáng)調(diào)“3C”融合,即:計(jì)算(Computation)、通訊(Communication)和控制(Control)的深度融合,將其定義為:在感知的基礎(chǔ)上,深度融合計(jì)算、通信和控制能力的可控、可信、可擴(kuò)展的網(wǎng)絡(luò)化物理設(shè)備系統(tǒng),它通過(guò)計(jì)算進(jìn)程和物理進(jìn)程的相互影響與反饋循環(huán)實(shí)現(xiàn)深度融合和實(shí)時(shí)交互來(lái)增加或擴(kuò)展新功能,以安全、可靠和實(shí)效的方式監(jiān)測(cè)或控制物理實(shí)體[3].以上定義都強(qiáng)調(diào)信息域與物理過(guò)程的深度融合,因此是解決現(xiàn)有C4KISR問(wèn)題的一種有效手段.基于這一現(xiàn)狀,結(jié)合軍事資源特點(diǎn),本文研究提出軍事信息物理系統(tǒng)(Military cyber physical system,MCPS)的概念,并對(duì)其體系架構(gòu)等問(wèn)題進(jìn)行了探討.

1.2 技術(shù)挑戰(zhàn)

作為新一代信息技術(shù)革命的核心技術(shù),CPS的概念一經(jīng)提出就得到了各國(guó)政府、企業(yè)和學(xué)術(shù)界的高度重視.美國(guó)2006年2月發(fā)布的《美國(guó)競(jìng)爭(zhēng)力計(jì)劃》將CPS列為重要的研究項(xiàng)目[4].到了2007年7月,美國(guó)總統(tǒng)科學(xué)技術(shù)顧問(wèn)委員會(huì)(PCAST)在題為《挑戰(zhàn)下的領(lǐng)先–競(jìng)爭(zhēng)世界中的信息技術(shù)研發(fā)》的報(bào)告中列出了8大關(guān)鍵信息技術(shù),其中CPS位列首位[5].同時(shí),CPS的研究得到了美國(guó)多個(gè)機(jī)構(gòu)的支持包括:NSF、DOD/DARPA、DOE、NASA、HSARPA、NIST、NSA、NIH.除美國(guó)外,歐洲,日本和韓國(guó)等也在從事類(lèi)似研究[6],如歐盟啟動(dòng)的ARTEMIS(2007-2013)和EPoSS項(xiàng)目就旨在取得智能電子系統(tǒng)的國(guó)際領(lǐng)先地位,這些項(xiàng)目雖然沒(méi)有明確提出CPS的概念,但已意識(shí)到相關(guān)理論和應(yīng)用的重要性,并已開(kāi)展相關(guān)研究.韓國(guó)的KIPA項(xiàng)目是通過(guò)研究智能嵌入式系統(tǒng)來(lái)獲取CPS相關(guān)技術(shù).目前,很多國(guó)際會(huì)議都開(kāi)設(shè)了CPS專(zhuān)題,2010舉辦了CPS第一屆國(guó)際會(huì)議ICCPS[7].在國(guó)內(nèi),CPS已經(jīng)得到了眾多專(zhuān)家學(xué)者的重視,中科院多位院士在各種學(xué)術(shù)報(bào)告中曾多次提到CPS相關(guān)研究,大連理工大學(xué)成立了首個(gè)CPS研究小組.科技部把CPS的研究列入了863和973指南,最近幾年國(guó)家自然科學(xué)基金也對(duì)CPS的研究予以了資助.

除國(guó)家層面的支持和項(xiàng)目支持外,學(xué)術(shù)界對(duì)CPS也進(jìn)行了深入的研究.文獻(xiàn)[8]提出了一種CPS系統(tǒng)的體系架構(gòu)建立方式,一定程度上支持了CPS中的資源管理,而文獻(xiàn)[9]針對(duì)CPS資源的動(dòng)態(tài)性和實(shí)時(shí)性,提出了一種能夠滿(mǎn)足動(dòng)態(tài)資源管理的體系架構(gòu).文獻(xiàn)[10]從未來(lái)集成系統(tǒng)的角度,對(duì)CPS系統(tǒng)的架構(gòu)進(jìn)行了設(shè)計(jì),認(rèn)為可將目前多種類(lèi)型的信息、物理系統(tǒng)采用集成的方式形成CPS系統(tǒng).更多的技術(shù)攻關(guān)側(cè)重于應(yīng)用領(lǐng)域.在能源應(yīng)用領(lǐng)域,文獻(xiàn)[11]對(duì)數(shù)據(jù)中心的CPS進(jìn)行研究,采用了基于CPS的動(dòng)態(tài)管理方式,使得系統(tǒng)能源控制的有效性大大提高.在擁塞控制領(lǐng)域,文獻(xiàn)[12]對(duì)物理世界中的對(duì)應(yīng)數(shù)據(jù)與CPS網(wǎng)絡(luò)中的傳輸數(shù)據(jù)的估計(jì)精度間的關(guān)系設(shè)計(jì)了新的數(shù)據(jù)擁塞控制策略.在人工智能和機(jī)器人領(lǐng)域,許多學(xué)者開(kāi)始考慮如何“人在回路,Human in the loop”,如何在信息物理融合的過(guò)程中加入人的作用[13].文獻(xiàn)[14]分析了CPS中面臨的挑戰(zhàn),而“人在回路”的實(shí)現(xiàn)和應(yīng)用是CPS系統(tǒng)設(shè)計(jì)和研究的重點(diǎn).文獻(xiàn)[15]對(duì)未來(lái)的“人在回路”CPS系統(tǒng)進(jìn)行了設(shè)計(jì)和展望,提出了一個(gè)初步的解決方案,使得用戶(hù)能夠較好地融入到信息物理回路中.在CPS平臺(tái)和實(shí)驗(yàn)環(huán)境領(lǐng)域,文獻(xiàn)[16?17]分別提出了自己的實(shí)驗(yàn)平臺(tái),從安全、可靠、適用的角度為CPS研究人員的系統(tǒng)驗(yàn)證提供了智能實(shí)驗(yàn)室環(huán)境.

以上文獻(xiàn)從不同方面對(duì)CPS進(jìn)行了研究,但目前仍然缺乏面向軍事資源的CPS系統(tǒng).MCPS仍然面臨許多挑戰(zhàn):

1)戰(zhàn)場(chǎng)資源異構(gòu)且動(dòng)態(tài)變化,使得資源的統(tǒng)一管理極為困難;

2)缺乏一體化的資源服務(wù)模式,從而使得資源的統(tǒng)一配置面臨很大困難;

3)戰(zhàn)場(chǎng)環(huán)境復(fù)雜多變,隨時(shí)都有不可預(yù)料的任務(wù)產(chǎn)生,加上資源的動(dòng)態(tài)性,MCPS的穩(wěn)定性難以得到保障.

基于以上挑戰(zhàn),本文首先提出面向服務(wù)的MCPS體系架構(gòu).接著,研究資源統(tǒng)一建模方法.最后,研究了MCPS穩(wěn)定性分析模型,并得出了穩(wěn)定性條件,為MCPS的長(zhǎng)期有效運(yùn)行提供了技術(shù)支撐.

2 面向服務(wù)的MCPS架構(gòu)

2.1 面向服務(wù)的思想

面向服務(wù)的體系結(jié)構(gòu)(SOA:Service-oriented architecture)旨在建立一種面向服務(wù)的解決方案,促進(jìn)MCPS中異構(gòu)資源之間的重用和互操作.服務(wù)層是SOA的基礎(chǔ),可以直接被應(yīng)用所調(diào)用,從而有效地控制系統(tǒng)中的各種軟硬件資源.除了服務(wù)的動(dòng)態(tài)發(fā)現(xiàn)和服務(wù)接口契約的定義外,服務(wù)還具有以下特征[18]:

1)服務(wù)是模塊化的可嵌套包含;

2)服務(wù)之間可以互操作;

3)服務(wù)是松耦合的;

4)服務(wù)位置透明;

5)服務(wù)由組件組成.

SOA是一種用于構(gòu)建分布式系統(tǒng)的理念,采用SOA構(gòu)建的分布式應(yīng)用程序可以將各功能模塊的功能作為服務(wù)交付給終端用戶(hù),也可以用它來(lái)構(gòu)建其他的服務(wù).MCPS是一種典型的分布式復(fù)雜系統(tǒng).基于SOA的MCPS,對(duì)于用戶(hù)來(lái)說(shuō),并不關(guān)心具體資源的狀態(tài)信息,而只關(guān)心資源所能夠提供的服務(wù),因此,更加高效.

2.2 基于SOA的MCPS體系架構(gòu)

該體系架構(gòu)的基本結(jié)構(gòu)如圖1所示。

從圖1可以看出,MCPS共包含4個(gè)層次,分別如下:

資源層:資源層包含各類(lèi)異構(gòu)戰(zhàn)場(chǎng)資源,如傳感器、雷達(dá)、飛機(jī)等.這些資源通過(guò)各種通信模式(有線(xiàn)或無(wú)線(xiàn))向MCPS注冊(cè).資源注冊(cè)時(shí)將要對(duì)資源進(jìn)行建模,資源統(tǒng)一建模方法將在后面進(jìn)行介紹.

組織管理層:該層是在注冊(cè)的資源描述模型的基礎(chǔ)上對(duì)資源組織管理,如資源存儲(chǔ)、索引構(gòu)建和查詢(xún)檢索等.資源組織管理的基本單位是港(Port),是資源的管理單元,類(lèi)似于數(shù)據(jù)庫(kù)是數(shù)據(jù)的管理單元.整個(gè)MCPS中的資源可以存儲(chǔ)在多個(gè)分布式的港中,這些港通過(guò)多種通信模式互聯(lián),從而形成一個(gè)網(wǎng)絡(luò)化的資源組織管理體系,實(shí)現(xiàn)資源的一體化管控.

服務(wù)層[18]:該層是MCPS中資源能力的抽象層,該層將資源的“能力”包裝成服務(wù)提供給用戶(hù).MCPS與物理環(huán)境交互存在實(shí)時(shí)性和不確定性,因此,該體系框架中任務(wù)產(chǎn)生模式是事件/信息觸發(fā)的.當(dāng)用戶(hù)向服務(wù)層申請(qǐng)服務(wù)時(shí),服務(wù)層首先對(duì)任務(wù)進(jìn)行解析,然后再為用戶(hù)提供相應(yīng)的服務(wù).該層的功能包括:任務(wù)解析、任務(wù)調(diào)度、任務(wù)執(zhí)行、任務(wù)監(jiān)控,服務(wù)描述,服務(wù)查詢(xún)、服務(wù)組合、服務(wù)評(píng)價(jià)等.

應(yīng)用層:該層是MCPS的最頂層,負(fù)責(zé)處理各類(lèi)應(yīng)用請(qǐng)求,并遞交給MCPS.

此外,圖1所示的MCPS體系架構(gòu)還包括用戶(hù)管理、資源建模及其描述語(yǔ)言和安全體系管理等.用戶(hù)管理和安全體系管理目前有專(zhuān)門(mén)的研究,本文不進(jìn)行探討.資源描述語(yǔ)言可以借鑒目前各類(lèi)物聯(lián)網(wǎng)描述語(yǔ)言.因此,下面重點(diǎn)探討資源建模方法.

3 戰(zhàn)場(chǎng)資源建模

3.1 戰(zhàn)場(chǎng)資源分類(lèi)體系

未來(lái)一體化聯(lián)合作戰(zhàn)涉及各種各樣的戰(zhàn)場(chǎng)資源,聯(lián)合戰(zhàn)場(chǎng)中的“資源”與物聯(lián)網(wǎng)中“物”的概念類(lèi)似.“資源”可以有很多種不同的解釋方式,資源既包括傳統(tǒng)意義上的實(shí)體事物,如作戰(zhàn)兵團(tuán)、武器、裝備、儀器、設(shè)備、交通工具等,也可以包括戰(zhàn)場(chǎng)環(huán)境中的山川、河流、道路、橋梁、樹(shù)木、建筑等.簡(jiǎn)單地說(shuō),聯(lián)合戰(zhàn)場(chǎng)中的資源就是指構(gòu)成軍事應(yīng)用的各種實(shí)體,這些實(shí)體是根據(jù)其具有的能力來(lái)發(fā)揮作用的,這些能力包括打擊毀傷能力、探測(cè)識(shí)別能力、通信能力、計(jì)算處理能力等,還包括環(huán)境場(chǎng)景情況(如時(shí)間和空間)等影響因素.按照功能特征,戰(zhàn)場(chǎng)資源可以分為以下4類(lèi):

簡(jiǎn)單節(jié)點(diǎn):這類(lèi)資源是數(shù)量最多的,它們本身不具備計(jì)算和聯(lián)網(wǎng)能力,需要通過(guò)貼上電子標(biāo)簽才能連接到MCPS.這類(lèi)資源可以具有移動(dòng)性,具有被感知能力和少量的數(shù)據(jù)存儲(chǔ)能力.例如貼上電子標(biāo)簽的槍支、彈藥或集裝箱.

通用節(jié)點(diǎn):這類(lèi)資源具有感知能力和聯(lián)網(wǎng)能力,但是不具有計(jì)算能力或只有少量的計(jì)算能力.這類(lèi)資源主要是傳感器資源,它們對(duì)環(huán)境進(jìn)行感知,為聯(lián)合戰(zhàn)場(chǎng)物聯(lián)網(wǎng)提供大量基礎(chǔ)數(shù)據(jù).通用節(jié)點(diǎn)是MCPS獲取基礎(chǔ)數(shù)據(jù)信息的重要部分,它是MCPS中不可缺少的信息采集節(jié)點(diǎn).例如RFID識(shí)讀器、雷達(dá)、可見(jiàn)光傳感器等.

圖1 面向服務(wù)的MCPS體系架構(gòu)

智能終端節(jié)點(diǎn):這類(lèi)資源具有計(jì)算能力、聯(lián)網(wǎng)能力和控制能力,且具有移動(dòng)性.它們是MCPS的核心節(jié)點(diǎn),是提供控制和被控制的主要對(duì)象.例如通訊衛(wèi)星、軍用手機(jī)及其他終端設(shè)備.

Ports節(jié)點(diǎn):這類(lèi)資源具有計(jì)算能力、聯(lián)網(wǎng)能力、數(shù)據(jù)存儲(chǔ)能力,就是圖1中的Ports.Ports節(jié)點(diǎn)是MCPS中的管理中間層,為簡(jiǎn)單節(jié)點(diǎn)、通用節(jié)點(diǎn)和智能終端節(jié)點(diǎn)接入MCPS提供了統(tǒng)一的接口,簡(jiǎn)單節(jié)點(diǎn)、通用節(jié)點(diǎn)和智能終端節(jié)點(diǎn)都是在Ports上進(jìn)行注冊(cè),聯(lián)入MCPS的.

3.2 資源統(tǒng)一建模方法

針對(duì)以上4類(lèi)資源的異構(gòu)性,本文提出了核心(單元屬性狀態(tài)能力)+擴(kuò)展單元的建模方案.且核心單元除定義的核心屬性外,也具有擴(kuò)展能力.其基本功能組成如圖2所示.

圖2 資源建?？蚣?/p>

屬性單元只定義了資源的基本屬性信息,在對(duì)資源進(jìn)行實(shí)例化描述時(shí),可以針對(duì)資源類(lèi)型進(jìn)行擴(kuò)展.屬性單元的核心字段包括:

1)名稱(chēng)(Name):針對(duì)資源的一個(gè)用戶(hù)可理解的命名;

2)標(biāo)識(shí)(ID):資源唯一標(biāo)識(shí);

3)所屬資源庫(kù):該資源隸屬的資源庫(kù);

4)最大使用頻率:資源可使用的最大頻次;

5)說(shuō)明(Comment):對(duì)資源描述內(nèi)容的說(shuō)明.

6)資源類(lèi)型:資源屬于前面所定義的4類(lèi)資源(簡(jiǎn)單節(jié)點(diǎn)、通用節(jié)點(diǎn)、智能終端節(jié)點(diǎn)、ports節(jié)點(diǎn))中的哪一類(lèi).

能力描述的是資源在某一確定狀態(tài)下能夠做出的行為.能力的描述必需相對(duì)于屬性與狀態(tài)而言.能力單元包含如下核心內(nèi)容:

1)2個(gè)全局定義:分別為excmod與cprotocol,excmod是描述資源的入網(wǎng)方式,cprotocol是描述資源控制通信采用的協(xié)議,這兩個(gè)屬性決定了Port對(duì)資源發(fā)送控制命令時(shí)的發(fā)送接口與采用的通信協(xié)議;

2)控制操作節(jié)點(diǎn):主要包含3個(gè)操作控制節(jié)點(diǎn):、、,分別對(duì)應(yīng)了能力模型中的3種控制操作類(lèi)型FSO、DEO、CNO.其中節(jié)點(diǎn)是必需的,節(jié)點(diǎn)與節(jié)點(diǎn)的信息可以為空.

在上述基本內(nèi)容的基礎(chǔ)上,能力單元同樣可以進(jìn)行擴(kuò)展.

狀態(tài)是對(duì)資源當(dāng)前所處狀態(tài)的一種描述,主要包含如下基本內(nèi)容:

1)是否可用:定義了資源當(dāng)前的基本狀態(tài),使得用戶(hù)知道資源能否執(zhí)行應(yīng)有的功能;

2)位置:定義資源當(dāng)前所處的物理空間;

3)開(kāi)關(guān)機(jī)狀態(tài):定義資源開(kāi)關(guān)機(jī)情況.

以上3個(gè)字段定義了資源狀態(tài)的核心內(nèi)容,同樣支持字段的擴(kuò)展.

4 MCPS穩(wěn)定性分析

4.1 穩(wěn)定性分析模型

前面介紹了MCPS的體系架構(gòu),并提出了面向異構(gòu)戰(zhàn)場(chǎng)資源的統(tǒng)一建模方法.基于資源模型,利用各類(lèi)通信模式向MCPS注冊(cè),從而實(shí)現(xiàn)了異構(gòu)資源的統(tǒng)一管理.MCPS作為一個(gè)典型的分布式系統(tǒng),其穩(wěn)定性分析十分重要,決定了該系統(tǒng)能否長(zhǎng)期有效穩(wěn)定運(yùn)行.為此,進(jìn)行MCPS的穩(wěn)定性分析十分有必要.

對(duì)于MCPS來(lái)說(shuō),其目的之一是面向任務(wù)進(jìn)行資源的合理調(diào)配,以支撐作戰(zhàn)行動(dòng)的需要.但是,在不同的任務(wù)調(diào)度算法下,等待任務(wù)的隊(duì)列長(zhǎng)度以及空閑的資源量也不相同.這就意味著任務(wù)調(diào)度方法和系統(tǒng)的穩(wěn)定性是緊密相關(guān)的.

在每個(gè)時(shí)刻t,對(duì)于m類(lèi)型的資源來(lái)說(shuō),假設(shè)其可以處理的任務(wù)數(shù)量為Dm(t),它與調(diào)度策略O(shè)m(t)密切相關(guān).以Am(t)代表時(shí)刻t到達(dá)的任務(wù)數(shù)量,則在該時(shí)刻m類(lèi)型資源所面臨的負(fù)載Um(t)的演化規(guī)律可以表示為[19]:

以U U U(t)代表整個(gè)MCPS在時(shí)刻t的負(fù)載,就可以得到:

基于上述公式,為了保障MCPS的穩(wěn)定性,下述公式必須得到滿(mǎn)足.

在此基礎(chǔ)上,本文針對(duì)搶占式任務(wù)調(diào)度以及非搶占式任務(wù)調(diào)度兩種模式,進(jìn)行穩(wěn)定性分析.

在搶占式調(diào)度模式下,每一個(gè)時(shí)刻的開(kāi)始階段,所有未完成的任務(wù)將返回至隊(duì)列中并根據(jù)當(dāng)前的資源分配方案選擇等待或執(zhí)行.利用率最優(yōu)算法應(yīng)當(dāng)使得系統(tǒng)處理的任務(wù)量即D(t)的值最大,則資源分配策略O(shè)(t)應(yīng)當(dāng)滿(mǎn)足下式:

此外,在資源分配過(guò)程中,使用不同類(lèi)型的資源所需付出的代價(jià)是不同的,即不同類(lèi)型的資源對(duì)CPS資源分配產(chǎn)生影響的權(quán)重是不同的.例如,不同傳感器的靈敏度不同,造價(jià)不同,故使用的代價(jià)也不相同.由于軍事任務(wù)需求的參差不齊,使得其對(duì)不同軍事資源的需求也不相同,利用率最大化算法難以有效滿(mǎn)足此類(lèi)任務(wù).因此,針對(duì)軍事任務(wù)和軍事資源的異構(gòu)性特征,本章加入了參數(shù)ζm來(lái)表示不同類(lèi)別的資源所占的權(quán)重.綜上所述,搶占式模式下的最優(yōu)資源分配問(wèn)題可以表示為下式:

算法1.搶占式方式下的利用率最優(yōu)算法

在每個(gè)時(shí)刻t的開(kāi)始階段,如果server中存在未完成的任務(wù)則將其返回至隊(duì)列中,尋找一個(gè)滿(mǎn)足式(5)和式(6)的資源調(diào)度策略O(shè)(t).

算法1需要在每個(gè)時(shí)刻的開(kāi)始階段重新分配資源,而在很多實(shí)際情況中,任務(wù)在執(zhí)行的過(guò)程中不允許中斷,或者中斷任務(wù)所需的代價(jià)極高.下文將介紹在非搶占式調(diào)度模式下的資源利用率近似最優(yōu)算法.

在時(shí)刻t,CPS資源分配系統(tǒng)保存在t?1時(shí)刻執(zhí)行且未完成的任務(wù),而在t?1時(shí)刻完成的任務(wù)則釋放資源并退出系統(tǒng),釋放的資源則用于t時(shí)刻其他任務(wù)的執(zhí)行.令N0(t)表示t時(shí)刻結(jié)束時(shí)未完成的任務(wù),包括未開(kāi)始的任務(wù).則對(duì)于任務(wù)n∈N0(t),其應(yīng)滿(mǎn)足下式:

算法2.非搶占式方式下的利用率近似最優(yōu)算法在每個(gè)時(shí)刻t的開(kāi)始階段,CPS資源分配系統(tǒng)首先計(jì)算已完成任務(wù)所釋放的資源量,進(jìn)而得到能夠用于資源分配的資源總量,而后尋找一個(gè)滿(mǎn)足式(8)～式(11)的資源調(diào)度策略O(shè)0(t).

此處所給出的算法為近似最優(yōu),這是因?yàn)樵趖?1時(shí)刻未完成的任務(wù)所占用的資源并沒(méi)有釋放.對(duì)于這些任務(wù)來(lái)說(shuō),t?1時(shí)刻的最優(yōu)分配策略在t時(shí)刻并不一定是最優(yōu)的(因?yàn)橐恍┤蝿?wù)釋放了資源),但其對(duì)最終結(jié)果的影響很小,特別是在資源數(shù)量較多的情況下.另外,在非搶占式調(diào)度的一些情況下,其設(shè)定占有資源的任務(wù)本身是不允許釋放資源的,在這種情況下上述算法事實(shí)上為最優(yōu)算法.此外需要注意的是,潛在的資源分配策略的數(shù)量極大,如前所述,達(dá)到2n,其中n為任務(wù)的數(shù)量.尋找最優(yōu)分配策略可以有很多種方法,如貪婪策略、啟發(fā)式算法等,但這些方法并不一定能夠得到最優(yōu)解.為了探討最優(yōu)分配策略與系統(tǒng)穩(wěn)定性之間的關(guān)系,在本章中使用動(dòng)態(tài)規(guī)劃算法來(lái)尋找最優(yōu)分配策略,盡管耗時(shí)較多.

4.2 資源分配策略的穩(wěn)定性條件

在本節(jié)中,將給出算法1和算法2穩(wěn)定性分析和條件,并給出了相關(guān)證明.此外,下文中存在很多向量和0向量之間的對(duì)比,故定義如下的形式:

定義.給定一個(gè)M維的向量x,如果x中的每一個(gè)元素均大于(小于)0,則稱(chēng)x> 0(<0)

算法1在CPS中的穩(wěn)定性質(zhì)由以下定理給出[20].

定理1.給定某個(gè)常數(shù)ε>0,對(duì)于任意的任務(wù)輸入 δ=(ω,χ),若其滿(mǎn)足 (1+ε)δ∈C,則系統(tǒng)在算法 1下是穩(wěn)定的,且下式成立

C是穩(wěn)定性空間集合,證明過(guò)程見(jiàn)文獻(xiàn)[21].此處ε可以作為一個(gè)衡量資源分配策略?xún)?yōu)劣的參數(shù),當(dāng)ε很小時(shí),說(shuō)明系統(tǒng)穩(wěn)定空間很大.

類(lèi)似地,可以得到定理2[20].

定理2.給定某個(gè)常數(shù)ε>0,對(duì)于任意的任務(wù)輸入δ=(ω,χ),若其滿(mǎn)足下式,則系統(tǒng)在算法2下是穩(wěn)定的.

在式(13)中,θ表示任務(wù)對(duì)不同資源的資源數(shù)量需求上限.

5 結(jié)論

首先提出了MCPS體系架構(gòu),并闡述了主要功能.接著,研究提出資源分類(lèi)體系和建模方法.最后,提出了MCPS穩(wěn)定性分析模型和穩(wěn)定性條件.下一步工作是,結(jié)合資源和任務(wù)動(dòng)態(tài)變化特性,研究穩(wěn)定性控制策略.