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

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

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

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)實體提供服務。因而起設備作用。描述這類實體的最常見的屬性有：忙、閑、數(shù)量、地點、速度、設備號、服務時間等。動態(tài)實體——這類實體在系統(tǒng)中總是要求得到

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

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

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

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

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

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

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

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

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

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

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

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

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就要求顧客的平均到達時間Ta=Ts/ρ=10/0.6=16.7（秒）。同樣：對給定了到達間隔時間Ta時，也可求得Ts以達到滿意的服務質量。,3.6 排隊系統(tǒng)建模,（1）以排隊論方法為基礎的仿真模型設計技術主要

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

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

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

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

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

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

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

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

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

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

29、個進程的活動需要取決于另一個進程中的活動的結束）。進程互配方法強調了這些進程之間的相互關系。,進程 到達 等待 離去 事件： 顧客4 排隊

30、 服務離去 等待顧客3 排隊 服務 到達顧客2 服務 活動：排隊顧客1

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

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

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

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