離散系統(tǒng)仿真基礎(chǔ)

1、3.離散系統(tǒng)仿真基礎(chǔ),離散事件動態(tài)系統(tǒng)(DEDS: Discrete Event Dynamic System)是指受事件驅(qū)動、系統(tǒng)狀態(tài)跳躍式變化、系統(tǒng)狀態(tài)遷移發(fā)生在一串離散時間點上的動態(tài)系統(tǒng)。,3.1 術(shù)語介紹,系統(tǒng)——按照某些規(guī)律結(jié)合起來的，互相作用、相互依存的所有元素的集合。實體——是對實際系統(tǒng)構(gòu)成仿真模型所必須的、不可略去的各種系統(tǒng)（元素）的抽象。（實體）屬性——能描述該實體狀態(tài)的一些量。它們可以是時間的函數(shù)，也可以不隨

2、時間變化。系統(tǒng)狀態(tài)——系統(tǒng)中全部實體的屬性在某時刻t所取量值的集合S(t)定義為“系統(tǒng)狀態(tài)”。,事件——當(dāng)t在T上按某種序列{t1,t2,…}取值的過程中，系統(tǒng)狀態(tài)發(fā)生了變化，就定義系統(tǒng)發(fā)生了某一“事件”。并把此時的ti值定義為“事件時刻”。活動——任何引起系統(tǒng)狀態(tài)改變的過程稱為“活動”。因此“活動”的結(jié)果使系統(tǒng)發(fā)生“事件”。而兩個相鄰“事件時刻”，可以看成是某一“活動”的過程。,離散系統(tǒng)按照時間和事件關(guān)系的分類 :,時間離散—

3、—系統(tǒng)本身可能連續(xù)，但只在一些特定的時刻，即T={ t1,t2,…}上被考察。通常為了方便，各時間間隔選定為整常數(shù)。,S(t)S(t6)S(t1) 0 t1 t2 t6 t時間離散系統(tǒng),時間連續(xù)而有離散事件——這時，系統(tǒng)狀態(tài)的變化，即事件時刻是不連續(xù)的，跳躍式的。,,S(t)1（亮）

4、 0 t1 t2 t3 t4 t5 t6 t人工控制的紅綠燈系統(tǒng),離散系統(tǒng)例子,不同實體可以分成兩類：,靜態(tài)實體——這類實體在系統(tǒng)中往往處于被動地位。它們?yōu)閯討B(tài)實體提供服務(wù)。因而起設(shè)備作用。描述這類實體的最常見的屬性有：忙、閑、數(shù)量、地點、速度、設(shè)備號、服務(wù)時間等。動態(tài)實體——這類實體在系統(tǒng)中總是要求得到

5、某些設(shè)備的服務(wù)。在系統(tǒng)的運行中，它們不斷得以某種到達(dá)率“生成”。當(dāng)從某一設(shè)備得到服務(wù)后，又流向其他設(shè)備以求服務(wù)。,,系統(tǒng)環(huán)境——能對系統(tǒng)產(chǎn)生影響的，屬于系統(tǒng)以外的元素集合。仿真目的——指仿真者希望通過仿真所獲取系統(tǒng)的哪些性能，信息。仿真模型——由系統(tǒng)數(shù)學(xué)模型根據(jù)仿真工具（語言）的特點，進(jìn)行必要的結(jié)構(gòu)變換，建立的合適算法。對同一系統(tǒng)，仿真的目的不同，所建的模型也將不同。,3.2 排隊系統(tǒng),在日常生活中，人們常常會見到各種各樣

6、的服務(wù)系統(tǒng)。例如：到食堂去買飯，炊事員和買飯人員構(gòu)成一個服務(wù)系統(tǒng)；在公共汽車服務(wù)系統(tǒng)，由汽車、乘客和車站組成。服務(wù)系統(tǒng)的主要特征是出現(xiàn)排隊。因此也稱其為“排隊系統(tǒng)”。,用于研究排隊系統(tǒng)的理論基礎(chǔ)是“排隊論”,排隊論最早由A. K. Erlang 于1918 年提出,在管理通訊和各類服務(wù)系統(tǒng)中有著廣泛的應(yīng)用,但是采用排隊論方法來為DEDS 建模服務(wù)卻是近二十年來的事。以排隊論為基礎(chǔ)的網(wǎng)絡(luò)模型是離散事件系統(tǒng)仿真中最常用的模型。,隨機(jī)排隊系統(tǒng)

7、的三個組成部分：,到達(dá)模式——指含個類型的動態(tài)實體按怎樣的規(guī)律到達(dá)。服務(wù)機(jī)構(gòu)——指同一時刻有多少服務(wù)設(shè)備可以接納動態(tài)實體；對它們的服務(wù)需要多少時間。排隊規(guī)則——到達(dá)的動態(tài)實體將按怎樣的次序接受服務(wù)。,離散仿真要解決的基本問題,如何通過已知的到達(dá)模式和服務(wù)時間的概率分布，研究排隊系統(tǒng)的隊列長度和服務(wù)設(shè)備“忙”或“閑”的程度，就是離散仿真要解決的基本問題。,幾種常見的排隊系統(tǒng)的結(jié)構(gòu)：,,動態(tài)實體到達(dá)離去一線一服

8、務(wù)設(shè)備排隊系統(tǒng)結(jié)構(gòu),動態(tài)實體到達(dá) 離去：：一線并聯(lián)服務(wù)設(shè)備排隊系統(tǒng)結(jié)構(gòu),3.3 到達(dá)模式,確定型到達(dá)模式——顧客有規(guī)則地按照一定的間隔時間到達(dá)。泊松到達(dá)模式——滿足4個條件平穩(wěn)性：在[a, a+t]時間內(nèi)有k個顧客到來的概率與a無關(guān)，只與t, k有關(guān)。記此概率為：Vk(t)——在t時間間隔內(nèi)到達(dá)k個顧客的概率。(P(k,λt))無后效性：不相交區(qū)間內(nèi)到達(dá)的顧客數(shù)是相互獨

9、立的。[t1,t2]到達(dá)數(shù)與[t0,t1]的到達(dá)數(shù)無關(guān)。普通性：令ψ(t)表示在長度為t的區(qū)間內(nèi)至少到達(dá)兩個顧客的概率，則ψ(t)=0 當(dāng)t->0；有限性：在任意有限時間區(qū)間內(nèi)到達(dá)有限個顧客的概率之和為1。,,,其中λ>0為常數(shù)。令第i個顧客到達(dá)的時刻為τi(I=1,2,…)，τ1=0，且ti=τi-τi-1（i=1,2,…），則顧客相繼到達(dá)的間隔t是相互獨立相同分布的。其到達(dá)間隔的分布為指數(shù)分布。,,指數(shù)分布：,泊松分

10、布到達(dá)模式實際上是指：到達(dá)間隔時間為指數(shù)分布的到達(dá)模式。,,,平均到達(dá)間隔時間Ta——在考慮模型的總時間T中，共到達(dá)了n個“顧客”的情況下的比值T/n。平均到達(dá)率λ——單位時間內(nèi)到達(dá)的“顧客”數(shù)。λ=1/Ta。 到達(dá)間隔的分布函數(shù)A0(t)——到達(dá)間隔時間大于t的概率。,A0(t) 1 F (t)

11、 A0(t) 0t,3.2.2 服務(wù)時間,定長分布——這是最簡單的情況。對每個動態(tài)實體的服務(wù)時間都是常數(shù)a，其分布函數(shù)為：指數(shù)分布——當(dāng)服務(wù)時間完全是隨機(jī)的情況，可以用指數(shù)分布來表示。其分布函數(shù)：,,,正態(tài)分布——在服務(wù)時間近似于常數(shù)的情況下，因多種隨機(jī)因素的影響，使服務(wù)時間圍

12、繞這些常數(shù)值隨機(jī)波動的情況。其中：σ>0，a——均值。F(x) 記為：N(a, σ2)。當(dāng)a=0，σ=1時，N(0,1)稱為“標(biāo)準(zhǔn)正態(tài)分布”。,,3.4 排隊規(guī)則和隊列的度量,排隊規(guī)則——動態(tài)實體應(yīng)依一定的次序和規(guī)則接受服務(wù)。損失制——動態(tài)實體到達(dá)時，如所有的服務(wù)設(shè)備均被占，則該實體就自動消失，永不再來。等待制——動態(tài)實體到達(dá)時，如所有的服務(wù)設(shè)備均被占，則它們就排成隊伍，等待服務(wù)。服務(wù)次序可以采用下列各種規(guī)則：

13、先到先服務(wù)先到后服務(wù)隨機(jī)服務(wù)優(yōu)先權(quán)服務(wù),排隊規(guī)則,在優(yōu)先權(quán)服務(wù)時，必須考慮當(dāng)一個比現(xiàn)在正接受服務(wù)的實體具有更高優(yōu)先權(quán)級別的動態(tài)實體到達(dá)之后，系統(tǒng)將會做出怎樣的處理：優(yōu)先權(quán)僅決定動態(tài)實體的排隊先后。立即停止當(dāng)前服務(wù)，為新到的高優(yōu)先權(quán)的實體服務(wù)。,排隊規(guī)則,3. 混合制——隊長有限制等待時間有限制逗留時間,隊列的度量,設(shè)Ta為動態(tài)實體的平均到達(dá)間隔時間，λ=1/Ta為平均到達(dá)速度Ts是設(shè)備的平均服務(wù)時間，μ=1/Ts

14、是平均服務(wù)速度。定義：業(yè)務(wù)量強(qiáng)度——在已知平均到達(dá)速度λ和平均服務(wù)速度μ，業(yè)務(wù)量強(qiáng)度：u=λ/μ=Ts/Ta設(shè)備利用率——得到服務(wù)的動態(tài)實體的到達(dá)速率λ’與服務(wù)速度之比：ρ=λ’/μ,對隊列進(jìn)行度量通?？疾靸蓚€量：,隊列長度排隊時間,3.5 設(shè)備利用率和服務(wù)質(zhì)量,對系統(tǒng)做假設(shè)：動態(tài)實體數(shù)量是無限的，其到達(dá)速率不受排隊長度的影響，并且所到達(dá)的實體不會中途離去；到達(dá)模式為泊松分布，服務(wù)設(shè)備利用率ρ<1時，

15、服務(wù)系統(tǒng)的動態(tài)實體平均數(shù)(L)為: 服務(wù)時間為常數(shù)分布L=ρ(2-ρ)/(2(1-ρ))服務(wù)時間為指數(shù)分布L=ρ/(1-ρ)隊列平均長度： Lw=1-ρ,通過改變 ρ來控制系統(tǒng)性能的方法：,改變動態(tài)實體的到達(dá)速度改變服務(wù)設(shè)備的服務(wù)速度改變服務(wù)設(shè)備的數(shù)量,系統(tǒng)的服務(wù)質(zhì)量的衡量標(biāo)準(zhǔn)：,能夠立即得到服務(wù)的動態(tài)實體占到達(dá)實體總數(shù)的百分比。等待時間小于等于一個給定值T的動態(tài)實體占到達(dá)實體總數(shù)的百分比。用Pw

16、(t)表示等待時間大于一時間長度(t)的概率。對泊松到達(dá)，指數(shù)服務(wù)的單服務(wù)設(shè)備系統(tǒng)有： 其中：t——指定的時間長度，ρ——設(shè)備利用率，μ平均服務(wù)速度。,,,例：對某個系統(tǒng)，平均服務(wù)時間為10秒，規(guī)定服務(wù)質(zhì)量：在4個請求中至少有一個請求應(yīng)立即給予響應(yīng)而且等待時間超過30秒的請求不應(yīng)超過請求總數(shù)的20%。分析：對第一個要求Pw(0)=0.75 => ρ≤0.75 對第二個要求如平均服務(wù)時間為

17、10秒 => μ=1/10=0.1,,Pw(t) 1.00.8 ρ=0.80.6 ρ=0.60.4 ρ=0.40.2 ρ=0.2 0 1 2 3 4 5

18、 6 μt,t=30秒 => μt=3。查曲線得 Pw(3) ≤0.2 =>ρ≤0.6如果用更小的利用率ρ，則會得到更低的概率。所以要求ρ≤0.6。綜合兩個要求，可取ρ≤0.6。為了使ρ=0.6就要求顧客的平均到達(dá)時間Ta=Ts/ρ=10/0.6=16.7（秒）。同樣：對給定了到達(dá)間隔時間Ta時，也可求得Ts以達(dá)到滿意的服務(wù)質(zhì)量。,3.6 排隊系統(tǒng)建模,（1）以排隊論方法為基礎(chǔ)的仿真模型設(shè)計技術(shù)主要

19、適用于帶時標(biāo)的隨機(jī)DEDS 系統(tǒng)。對排隊系統(tǒng)來說，它只有兩個基本的操作：“入隊”和“離隊”操作。排隊模型的確切形式取決于服務(wù)設(shè)備的數(shù)量和排隊線的數(shù)量。,YN （時間） 入隊操作,Y N

20、 離隊操作,(2) Petri 網(wǎng)絡(luò)模型 Petri網(wǎng)模型最早在1962年 Carl Adam Petri的博士論文中提出來，主要特性是具有較強(qiáng)的對并行、不確定性、異步和分布的描述能力和分析能力。Petri網(wǎng)是一個模型化的工具，它是設(shè)想來用于模型化某一類問題：即有同時平行事件的離散事件的系統(tǒng)的問題。Petri網(wǎng)模型化了系統(tǒng)，特別是系統(tǒng)的兩個方面（事件和條件）及它們之間的關(guān)

21、系。,(3)有限狀態(tài)自動機(jī)模型 離散事件系統(tǒng)自動機(jī)及形式語言理論最早是由P. J .Ramadge 和W.M.Wonbarn 等人八十年代中期提出的,現(xiàn)已成為DEDS 研究的重要方法之一?！　∮邢逘顟B(tài)自動機(jī)模型描述方法主要適用于邏輯定性模型和無時標(biāo)確定性模型的建模。建立有限狀態(tài)自動機(jī)模型的關(guān)鍵是,基于適當(dāng)?shù)姆抡娌呗赃x用相應(yīng)狀態(tài)集合,建立正確的轉(zhuǎn)移關(guān)系函數(shù)和輸出關(guān)系函數(shù)。,4. 離散事件仿真策略與結(jié)構(gòu)模型,仿真過程的運行調(diào)度

22、控制（特別是在用高級語言編程時），是通過所謂的“仿真策略”來實現(xiàn)的。 例：對一個含有一些出納員，一些顧客和對應(yīng)每個出納員的銀行（多）排隊線的系統(tǒng)。設(shè)：出納員 數(shù)量5 服務(wù)速度 N(3,1) 顧客到達(dá)[0.2, 0.8]統(tǒng)計隊列長度（平均，最大，最小，方差）出納員利用率（平均，最大，最小，方差）顧客在銀行的時間（平均，最大，最小，方差）,可以畫出仿真程序的結(jié)構(gòu)框圖如下：,N

23、YN 到達(dá)事件Y N Y,這是種“面向時間”的時鐘(TIME)處理。通過多次運行程序（試驗）統(tǒng)計得到結(jié)果。程序每做一次循環(huán)，就增加一個時間單位。此時不論系統(tǒng)是否有時間發(fā)生，程序總是要查詢系統(tǒng)狀態(tài)，如發(fā)現(xiàn)沒有時間發(fā)生就跳過該事件的處理程序。這種方法的特點是：能和連續(xù)模型（進(jìn)行時間離散）

24、混合仿真。當(dāng)事件子程序均能在一個時間單位內(nèi)處理完成，則TIME的+1操作可以在機(jī)器硬件時鐘的控制下執(zhí)行，即仿真程序可以實時的（與機(jī)器時鐘同步）運行。缺點是：計算機(jī)做了很多不必要的空操作。因為在兩個相鄰事件時刻之間，系統(tǒng)沒有活動需要計算機(jī)處理。目前很少使用此方法。人們在研究了各種（離散）仿真調(diào)度方法的基礎(chǔ)上，總結(jié)出三種通用的仿真策略，即：事件預(yù)定，活動掃描和進(jìn)程互配。,4.1 面向事件結(jié)構(gòu)模型,面向事件結(jié)構(gòu)模型是按事件獨立預(yù)定

25、策略組建成的。對上述的銀行系統(tǒng)為例，其仿真程序結(jié)構(gòu)框圖：,產(chǎn)生第一個顧客到達(dá)，填入事件表 N Y 到達(dá)事件…… 事務(wù)完成,事件表結(jié)構(gòu)：,面向事件結(jié)構(gòu)模型,在這里，仿真時鐘TIME是根據(jù)當(dāng)前事件的發(fā)生時刻進(jìn)行離散變化

26、的?！笆录A(yù)定策略”強(qiáng)調(diào)：預(yù)定全部事件。事件將按顯式調(diào)度。“事件功能”由事件程序?qū)崿F(xiàn)。事件的調(diào)度是通過把事件按“事件標(biāo)志”放在事件表中的方法來達(dá)到的。,4.2 活動掃描結(jié)構(gòu)模型,當(dāng)事件的發(fā)生不僅與時間有關(guān)，而且與其它條件也有關(guān)，即：只有在滿足某些條件時發(fā)生。在這種情況下，由于活動持續(xù)時間的不確定性，無法預(yù)定活動的開始或終止時間。所以不易采用面向事件的結(jié)構(gòu)模型。而活動掃描結(jié)構(gòu)模型就是針對具有這種特點的系統(tǒng)的。,活動掃描結(jié)構(gòu)模型,活動

27、掃描結(jié)構(gòu)要求對事件隱式調(diào)度。在這里，狀態(tài)的轉(zhuǎn)換被表示成一組稱之為“活動”的函數(shù)。每次轉(zhuǎn)換，由一個活動條件和一個動作組成。在每個（由預(yù)定事件生成時刻確定的）時間上，按某種（總體狀態(tài)的）順序掃描這些條件，如果出現(xiàn)一個條件是真，則立即執(zhí)行與它聯(lián)系的“動作”段；繼續(xù)掃描，測試和執(zhí)行，直到滿足條件的活動都進(jìn)行完。這是再按下一預(yù)定事件生成時刻向前推進(jìn)模型的時鐘。,活動掃描結(jié)構(gòu)模型,按某種（總體狀態(tài)）順序掃描這些任務(wù)（包括檢測小于當(dāng)前時間應(yīng)發(fā)生

28、，但因條件未滿足而延時發(fā)生的“以前”事件）。在使用活動掃描策略時，需要借助事件預(yù)定策略進(jìn)行時間（鐘）管理。事件預(yù)定策略不但要按預(yù)定事件的生成時刻向前推進(jìn)仿真時鐘，而且還按預(yù)定生成時刻激發(fā)事件（條件將在處理中測試）,活動掃描表結(jié)構(gòu)：,4.3 進(jìn)程互配模型結(jié)構(gòu),進(jìn)程是一系列互相排斥的活動互配（在一個進(jìn)程中，一次只能激活一個活動，進(jìn)程中的活動間的連接關(guān)系：一個活動的結(jié)束，可以使該進(jìn)程中的另一個活動的開始。不同的進(jìn)程間會有重疊。（一

29、個進(jìn)程的活動需要取決于另一個進(jìn)程中的活動的結(jié)束）。進(jìn)程互配方法強(qiáng)調(diào)了這些進(jìn)程之間的相互關(guān)系。,進(jìn)程 到達(dá) 等待 離去 事件： 顧客4 排隊

30、 服務(wù)離去 等待顧客3 排隊 服務(wù) 到達(dá)顧客2 服務(wù) 活動：排隊顧客1

31、服務(wù)空閑出納2空閑 空閑 忙 空閑出納1 E1 E2 E3 E4 E5 E7

32、 E9 E10 時間（t） E6 E8進(jìn)程運行時間示意圖,,,,,,,進(jìn)程互配模型結(jié)構(gòu),面向進(jìn)程的結(jié)構(gòu)適用于處理結(jié)構(gòu)的仿真模型。它的設(shè)計特點是：為每一個實體（如銀行系統(tǒng)的顧客/出納員）建立一個進(jìn)程（一個運行程序），該進(jìn)程的可能的活動將反映一個（動態(tài)）

33、實體的建立開始到結(jié)束為止所經(jīng)歷的一條路徑。由于顧客的到達(dá)、出納員對事務(wù)處理的時間隨機(jī)性，就會出現(xiàn)有多個進(jìn)程并存于仿真程序中運行。（在E5，E6時刻有4個顧客的進(jìn)程并存于系統(tǒng)）在銀行系統(tǒng)中，要建立的進(jìn)程有兩類：一類是動態(tài)實體——顧客，另一類是起設(shè)備作用的實體——出納員。,初始化 初始化

34、 Y N N Y 排隊 服務(wù)死循環(huán)掛起（中斷進(jìn)程，由進(jìn)程調(diào)度啟動） 排隊等待 服務(wù)等待離去,面向進(jìn)程的結(jié)構(gòu)，除了含有上述的進(jìn)程部分之外，還有主程序及