离散事件系统仿真

讲课内容系统仿真的一般方法随机事件生成仿真结果统计计算并行分布式仿真NS2事件调度方法1.1连续系统与离散系统依据所关心变量的时变性根据计算方法确定时变性1.系统仿真的一般方法timetimeStatevariable连续时间模型系统的输入量u(t)，输出量y(t)，内部状态变量x(t)，都是时间的连续函数连续时间模型表示方式微分方程(组)传递函数权函数/冲击响应函数内部状态空间描述1.系统仿真的一般方法离散时间模型系统的输入量、输出量及其内部状态量是时间的离散函数，{u(k)}，{y(k)}，{x(k)}也有差分方程，传递函数，权序列，离散状态空间四种模型表示形式实际上，连续系统仿真计算，需从时间、数值两个方面进行离散化，并选择合适的数值计算方法来近似积分运算，得到离散模型。1.系统仿真的一般方法圆周率计算1.系统仿真的一般方法Rhindpapyrus2000BC13.16045Archimedes250BC33.1418TsuCh'ungChi48073.141592920FergusonJan1947710DeskcalculatorReitwiesneretal19492037ENIACKanada,Takahashi1999206158430000劉徽「割圓術」：「割之彌細，所失彌少，割之又割，以至於不可割，則與圓周合體而無所失矣。」两类计算方法1.系统仿真的一般方法/4=tan-11=1-(1/3)+(1/5)-(1/7)+…Sc=

a2Sr=4a2

=4(Sc/Sr)2a（1）数值计算（2）Monte-Carlo法1.2离散事件系统系统中的状态只是在离散时间点上发生变化,这些离散时间点一般是不确定的。1.系统仿真的一般方法timetimeStatevariable随机过程T，事件发生时间间隔不确定，或随机N，单位时间内事件数不确定Markov：事件发生无记忆，<T>,<N>一致分布PoissonMMPPGeneric1.系统仿真的一般方法1.3DES仿真时钟推进事件驱动/调度法按下一最早发生事件的发生时间推进固定增量法按固定周期时间增长待处理事件假设发生在该周期结束时间1.系统仿真的一般方法1.4排队系统示例1.系统仿真的一般方法到达过程1.系统仿真的一般方法到达事件处理1.系统仿真的一般方法算法示例1.系统仿真的一般方法结果统计1.系统仿真的一般方法随机数生成是随机事件生成的基础是正确仿真的基础随机性检验可控制性可移植性快速有效性三种方法：表查找、硬件法、软件法2.随机事件生成2.1LinearCongruential算法2.随机事件生成全周期性2.随机事件生成“好”的乘子2.随机事件生成2.2Uniform分布LCG：x

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

指数分布事件的计数过程2.4MMPP业务源来自多个（最小2个）不同强度的Poisson源，系统在这些源之间切换2.随机事件生成S1S2

1

1S3

2

2MarkovchainS=S1:p(

)=

1exp(-

1

)S=S2:p(

)=

2exp(-

2

)PoissonProcessModulated2.5Gamma分布拒绝法Gamma:等待a个指数分布事件的时长分布2.随机事件生成f(x)p(x)xixf(x)dxp(x)dxp(x)dx=[p(x)/f(x)]f(x)dx对比函数例2.随机事件生成~\ns-1.32\packmine\pack_HTTP_rng.cc抽样统计的作用仿真计算的输入和输出均为数据海量数据，非做压缩处理不可二种统计方式后续统计在线统计3.仿真结果统计计算3.1基本统计参数平均值/数学期望方差/偏差3.仿真结果统计计算3.2时间平均统计3.仿真结果统计计算3.3曲线拟合按预设的规律/曲线，从实验数据分析出参数，即参数估计3.仿真结果统计计算线性拟合3.仿真结果统计计算

(ui–u)=(vi–v)=0线性参数估计3.仿真结果统计计算线性参数估计3.仿真结果统计计算=0TOEFLvsVerbalGRE3.仿真结果统计计算4.1PADS的优点多机或多处理器参与，可提升效率可支持在线人机接口冗错能力强4.并行分布式仿真a*b+c*de=a*bf=c*dg=e+fe=a*bf=c*dg=e+f单处理进程双处理进程4.2PADS的难点任务分摊,实时间控制虚拟时间控制保守同步法摇回同步法4.并行分布式仿真LP1LP2LP3LP1LP2LP1LP24.3pdns基本特点4.并行分布式仿真/computing/compass/pdns/index.html128processors,aspeedupfactor808processors,<1!5.1Scheduler(纯虚类)5.NS2事件调度方法Schedulerinsert(Evnet*)Event*deque()Event*head()Eventdoubletime_...Handler*handler_Event*prev_Event*next_PacketAtEvent5.2ListScheduler5.NS2事件调度方法Eventdoubletime_...Handler*handler_Event*prev_Event*next_EventEvent5.3CalendarScheduler5.NS2事件调度方法Eventdoubletime_...Handler*handler_Event*prev_Event*next_EventEventBucket