離散事件系統(tǒng)仿真

講課內(nèi)容系統(tǒng)仿真的一般方法隨機(jī)事件生成仿真結(jié)果統(tǒng)計(jì)計(jì)算并行分布式仿真NS2事件調(diào)度方法1.1連續(xù)系統(tǒng)與離散系統(tǒng)依據(jù)所關(guān)心變量的時(shí)變性根據(jù)計(jì)算方法確定時(shí)變性1.系統(tǒng)仿真的一般方法timetimeStatevariable連續(xù)時(shí)間模型系統(tǒng)的輸入量u(t)，輸出量y(t)，內(nèi)部狀態(tài)變量x(t)，都是時(shí)間的連續(xù)函數(shù)連續(xù)時(shí)間模型表示方式微分方程(組)傳遞函數(shù)權(quán)函數(shù)/沖擊響應(yīng)函數(shù)內(nèi)部狀態(tài)空間描述1.系統(tǒng)仿真的一般方法離散時(shí)間模型系統(tǒng)的輸入量、輸出量及其內(nèi)部狀態(tài)量是時(shí)間的離散函數(shù)，{u(k)}，{y(k)}，{x(k)}也有差分方程，傳遞函數(shù)，權(quán)序列，離散狀態(tài)空間四種模型表示形式實(shí)際上，連續(xù)系統(tǒng)仿真計(jì)算，需從時(shí)間、數(shù)值兩個(gè)方面進(jìn)行離散化，并選擇合適的數(shù)值計(jì)算方法來近似積分運(yùn)算，得到離散模型。1.系統(tǒng)仿真的一般方法圓周率計(jì)算1.系統(tǒng)仿真的一般方法Rhindpapyrus2000BC13.16045Archimedes250BC33.1418TsuCh'ungChi48073.141592920FergusonJan1947710DeskcalculatorReitwiesneretal19492037ENIACKanada,Takahashi1999206158430000劉徽「割圓術(shù)」：「割之彌細(xì)，所失彌少，割之又割，以至於不可割，則與圓周合體而無所失矣?！箖深愑?jì)算方法1.系統(tǒng)仿真的一般方法/4=tan-11=1-(1/3)+(1/5)-(1/7)+…Sc=

a2Sr=4a2

=4(Sc/Sr)2a（1）數(shù)值計(jì)算（2）Monte-Carlo法1.2離散事件系統(tǒng)系統(tǒng)中的狀態(tài)只是在離散時(shí)間點(diǎn)上發(fā)生變化,這些離散時(shí)間點(diǎn)一般是不確定的。1.系統(tǒng)仿真的一般方法timetimeStatevariable隨機(jī)過程T，事件發(fā)生時(shí)間間隔不確定，或隨機(jī)N，單位時(shí)間內(nèi)事件數(shù)不確定Markov：事件發(fā)生無記憶，<T>,<N>一致分布PoissonMMPPGeneric1.系統(tǒng)仿真的一般方法1.3DES仿真時(shí)鐘推進(jìn)事件驅(qū)動(dòng)/調(diào)度法按下一最早發(fā)生事件的發(fā)生時(shí)間推進(jìn)固定增量法按固定周期時(shí)間增長待處理事件假設(shè)發(fā)生在該周期結(jié)束時(shí)間1.系統(tǒng)仿真的一般方法1.4排隊(duì)系統(tǒng)示例1.系統(tǒng)仿真的一般方法到達(dá)過程1.系統(tǒng)仿真的一般方法到達(dá)事件處理1.系統(tǒng)仿真的一般方法算法示例1.系統(tǒng)仿真的一般方法結(jié)果統(tǒng)計(jì)1.系統(tǒng)仿真的一般方法隨機(jī)數(shù)生成是隨機(jī)事件生成的基礎(chǔ)是正確仿真的基礎(chǔ)隨機(jī)性檢驗(yàn)可控制性可移植性快速有效性三種方法：表查找、硬件法、軟件法2.隨機(jī)事件生成2.1LinearCongruential算法2.隨機(jī)事件生成全周期性2.隨機(jī)事件生成“好”的乘子2.隨機(jī)事件生成2.2Uniform分布LCG：x

[1，m-1]0~1:y=x/m0~k:y=xmodka~b:y=a+(b-a)x/mMRG(MultipleRecursiveGenerator)2.隨機(jī)事件生成ns-allinone-2.32\ns-2.32\toolsfxab2.3指數(shù)分布(逆函數(shù)法)2.隨機(jī)事件生成S.A.Teukolskyetal.NumericalRecipesinC.1992.WilliamHPressPoisson分布2.隨機(jī)事件生成txxt-

指數(shù)分布事件的計(jì)數(shù)過程2.4MMPP業(yè)務(wù)源來自多個(gè)（最小2個(gè)）不同強(qiáng)度的Poisson源，系統(tǒng)在這些源之間切換2.隨機(jī)事件生成S1S2

1

1S3

2

2MarkovchainS=S1:p(

)=

1exp(-

1

)S=S2:p(

)=

2exp(-

2

)PoissonProcessModulated2.5Gamma分布拒絕法Gamma:等待a個(gè)指數(shù)分布事件的時(shí)長分布2.隨機(jī)事件生成f(x)p(x)xixf(x)dxp(x)dxp(x)dx=[p(x)/f(x)]f(x)dx對(duì)比函數(shù)例2.隨機(jī)事件生成~\ns-1.32\packmine\pack_HTTP_rng.cc抽樣統(tǒng)計(jì)的作用仿真計(jì)算的輸入和輸出均為數(shù)據(jù)海量數(shù)據(jù)，非做壓縮處理不可二種統(tǒng)計(jì)方式后續(xù)統(tǒng)計(jì)在線統(tǒng)計(jì)3.仿真結(jié)果統(tǒng)計(jì)計(jì)算3.1基本統(tǒng)計(jì)參數(shù)平均值/數(shù)學(xué)期望方差/偏差3.仿真結(jié)果統(tǒng)計(jì)計(jì)算3.2時(shí)間平均統(tǒng)計(jì)3.仿真結(jié)果統(tǒng)計(jì)計(jì)算3.3曲線擬合按預(yù)設(shè)的規(guī)律/曲線，從實(shí)驗(yàn)數(shù)據(jù)分析出參數(shù)，即參數(shù)估計(jì)3.仿真結(jié)果統(tǒng)計(jì)計(jì)算線性擬合3.仿真結(jié)果統(tǒng)計(jì)計(jì)算

(ui–u)=(vi–v)=0線性參數(shù)估計(jì)3.仿真結(jié)果統(tǒng)計(jì)計(jì)算線性參數(shù)估計(jì)3.仿真結(jié)果統(tǒng)計(jì)計(jì)算=0TOEFLvsVerbalGRE3.仿真結(jié)果統(tǒng)計(jì)計(jì)算4.1PADS的優(yōu)點(diǎn)多機(jī)或多處理器參與，可提升效率可支持在線人機(jī)接口冗錯(cuò)能力強(qiáng)4.并行分布式仿真a*b+c*de=a*bf=c*dg=e+fe=a*bf=c*dg=e+f單處理進(jìn)程雙處理進(jìn)程4.2PADS的難點(diǎn)任務(wù)分?jǐn)?實(shí)時(shí)間控制虛擬時(shí)間控制保守同步法搖回同步法4.并行分布式仿真LP1LP2LP3LP1LP2LP1LP24.3pdns基本特點(diǎn)4.并行分布式仿真/computing/compass/pdns/index.html128processors,aspeedupfactor808processors,<1!5.1Scheduler(純虛類)5.NS2事件調(diào)度方法Schedulerinsert(Evnet*)Event*deque()Event*head()Eventdoubletime_...Handler*handler_Event*prev_Event*next_PacketAtEvent5.2ListScheduler5.NS2事件調(diào)度方法Eventdoubletime_...Handler*handler_Event*prev_Event*next_EventEvent5.3CalendarScheduler5.NS2事件調(diào)度方法Eventdoubletime_...Handler*handler_Event*prev_Event*next_EventEventBucket