離散事件動態(tài)系統(tǒng)及其在網(wǎng)絡(luò)仿真中的應(yīng)用

張霖

摘 要：離散事件動態(tài)系統(tǒng)已成為控制領(lǐng)域的重要理論基礎(chǔ)。文章著眼于離散事件的理論體系，研究了離散事件動態(tài)系統(tǒng)的模型設(shè)計和分析方法。根據(jù)分析結(jié)果，結(jié)合工程實例，進(jìn)行了基于DEDS理論的通信網(wǎng)絡(luò)仿真。仿真結(jié)果清晰地展示了通信網(wǎng)絡(luò)的各項性能指標(biāo)，從而使離散事件動態(tài)系統(tǒng)的特性得以具體化。

關(guān)鍵詞：DEDS；系統(tǒng)仿真；模型

離散事件動態(tài)系統(tǒng)（Discrete Event Dynamic System，DEDS）是指系統(tǒng)的狀態(tài)由于某種事件的驅(qū)動而在一些不確定的離散時間點上發(fā)生變化，它是控制系統(tǒng)分析、設(shè)計和大型復(fù)雜信息處理的重要理論基礎(chǔ)。由于其內(nèi)部機(jī)制的復(fù)雜性和狀態(tài)空間缺乏易操作的運(yùn)算結(jié)構(gòu)等特點，使得它無法用常規(guī)的數(shù)學(xué)方法來研究，所以計算機(jī)仿真實驗就成了最為實用的方法之一?，F(xiàn)階段離散事件動態(tài)系統(tǒng)的研究目標(biāo)是運(yùn)用理論方法結(jié)合各種模型，全面反映離散事件動態(tài)系統(tǒng)的特性并給出針對實際問題的行之有效的解決方法。

1 離散事件動態(tài)系統(tǒng)概述

離散事件動態(tài)系統(tǒng)本質(zhì)上屬于人造系統(tǒng)的范疇，而人造系統(tǒng)的含義是指以高技術(shù)為背景的一類按人為機(jī)制和人為規(guī)則所構(gòu)成的“非物理型”系統(tǒng)，例如計算機(jī)通信網(wǎng)絡(luò)、柔性生產(chǎn)線等都是典型的人造系統(tǒng)，所以這些系統(tǒng)也可以稱之為DEDS。

自從對DEDS理論研究以來，先后出現(xiàn)了不同類型的DEDS模型，如：有限狀態(tài)自動機(jī)模型、時序邏輯模型和排隊網(wǎng)絡(luò)模型等[1]。雖然這些模型并不通用，但是從現(xiàn)有模型的形成過程來看，在離散事件動態(tài)系統(tǒng)的建模過程中，常用的方法主要有排隊網(wǎng)絡(luò)法、攝動分析法和離散事件系統(tǒng)仿真法等。本文主要介紹離散事件系統(tǒng)仿真法及其在通信網(wǎng)絡(luò)中的應(yīng)用。

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

由于DEDS固有的離散性和內(nèi)部機(jī)制的復(fù)雜性，往往難以用常規(guī)的差分方程、微分方程等數(shù)學(xué)模型來描述，同時關(guān)于系統(tǒng)動態(tài)過程的解析表達(dá)也很難得到，而離散事件系統(tǒng)仿真則能借助仿真的方式很好地描述DEDS各方面的性能，因此，它是目前研究DEDS最為流行的方法之一。

2.1 基本概念

DEDS是指對系統(tǒng)狀態(tài)隨時間發(fā)生的所有變化建模，離散事件系統(tǒng)的狀態(tài)變化發(fā)生在離散的時間點上，它通過產(chǎn)生一系列系統(tǒng)映像來表示系統(tǒng)隨時間的演變。一個給定某個時刻（CLOCK=t）的映像不僅包括時刻t的系統(tǒng)狀態(tài)，也包括推進(jìn)中當(dāng)前所有活動的表和每一個類似的活動即將結(jié)束的時間、所有實體和所有集合當(dāng)前成員的狀態(tài)，還有累積統(tǒng)計和計數(shù)器的當(dāng)前值以用于仿真結(jié)束時的總統(tǒng)計[2]。DESS的仿真機(jī)制的核心是時鐘推進(jìn)和事件調(diào)度機(jī)制，它能在不影響實際系統(tǒng)的情況下客觀評價系統(tǒng)的運(yùn)行性能，并給出合理可行的運(yùn)行方案，同時，Zeigler提出的DEVS形式化理論能夠構(gòu)成層次化和模塊化的抽象仿真器概念，成了仿真系統(tǒng)軟件開發(fā)和仿真建模的理論基礎(chǔ)，定義如下[3]：

將離散事件系統(tǒng)表示為外部事件（X），輸出事件（Y），序貫狀態(tài)（S），狀態(tài)轉(zhuǎn)移描述函數(shù)（δ），輸出函數(shù)（λ）和時間推進(jìn)函數(shù)（ta）的邏輯集合：

M=< X，Y，S，δ，λ，ta>

2.2 相關(guān)模型

DESS主要包含了系統(tǒng)的理論模型和仿真模型兩部分。

理論模型是指對所研究的系統(tǒng)的理論描述，簡稱一次建模；它分為概念模型、描述模型、功能模型、約束模型、空間模型等5種基本類型?；顒又芷趫D法、實體流圖法、Petri網(wǎng)法和Euler網(wǎng)法是幾種主要的理論模型建模方法。

仿真模型簡稱二次建模，它建立在理論模型的基礎(chǔ)之上，是一種易于在計算機(jī)上編程實現(xiàn)的模型。

將理論模型轉(zhuǎn)換成仿真模型，且能在計算機(jī)上運(yùn)行，需要完成3個方面的工作：（1）設(shè)計仿真策略，確定仿真模型的表達(dá)方法和仿真運(yùn)行的解算機(jī)制。（2）構(gòu)造仿真模型，詳細(xì)設(shè)計基于某種仿真策略的仿真模型及解算機(jī)制。（3）編寫仿真程序，使用程序設(shè)計語言實現(xiàn)仿真模型[4]。

無論采用哪一種仿真策略，都可以從以下3方面設(shè)計仿真模型：（1）設(shè)計總控程序；（2）設(shè)計基本模型單元的處理程序；（3）編寫公共子程序。

DEDS的仿真模型主要有面向事件、面向活動和面向進(jìn)程3種，它們各有不同特點，我們可根據(jù)不同需要選擇合適的仿真模型。仿真模型實現(xiàn)的有效方法之一是建立仿真函數(shù)庫。它的優(yōu)點在于建模者可以專注于模型的邏輯關(guān)系而不必?fù)?dān)心模型實現(xiàn)的細(xì)節(jié)，因此，仿真函數(shù)庫的建立需要足夠靈活，以保證其適用于各類系統(tǒng)的建模。它的基本功能模塊包括：隨機(jī)數(shù)生成、實體建模、運(yùn)行調(diào)度、隊列建模、仿真結(jié)果收集和分析。仿真函數(shù)庫首先應(yīng)有調(diào)用子程序或函數(shù)的能力，并且是通過參數(shù)傳遞來實現(xiàn)。其次，要有實時生成動態(tài)數(shù)據(jù)對象的能力和能夠支持應(yīng)用預(yù)編譯模塊構(gòu)成的庫[4]。

3 基于離散事件動態(tài)系統(tǒng)的網(wǎng)絡(luò)仿真

3.1 通信網(wǎng)絡(luò)中的DEDS理論

通信網(wǎng)絡(luò)作為典型的離散事件系統(tǒng)，它充分借鑒了DEDS理論的各項成果。

首先，排隊網(wǎng)理論就成功地運(yùn)用在網(wǎng)絡(luò)建模中。排隊網(wǎng)絡(luò)的特點是運(yùn)用概率和統(tǒng)計的方法對DEDS進(jìn)行建模，一般是先對網(wǎng)絡(luò)特性作基本的假設(shè)，然后采用基于狀態(tài)穩(wěn)態(tài)概率分布的平均性能分析方法，用以導(dǎo)出表征系統(tǒng)性能的解析表達(dá)式。它的優(yōu)點是能夠很好地描述具有成熟的隨機(jī)過程和概率論的理論基礎(chǔ)和常規(guī)類型的排隊系統(tǒng)。

其次，研究通信網(wǎng)絡(luò)的另一種有效工具就是仿真分析法。由于通信網(wǎng)絡(luò)中固有的隨機(jī)性和離散性，純粹用數(shù)學(xué)方法已很難解決問題，所以仿真分析法就成為分析通信網(wǎng)絡(luò)性能的有效方法，其中具有代表性的就是攝動分析法（Perturbation Analysis，PA）[5]。它既有理論計算，又有仿真試驗，吸取了兩者的優(yōu)點，很容易對DEDS的統(tǒng)計性能進(jìn)行優(yōu)化分析。所以，PA方法是排隊網(wǎng)理論和計算機(jī)仿真分析的創(chuàng)造性結(jié)合。

3.2 基于DEDS理論的AODV模擬

本文將使用網(wǎng)絡(luò)仿真軟件NS2和OPNET去仿真一個無線AD hoc網(wǎng)絡(luò)中經(jīng)典的路由協(xié)議—無線自組網(wǎng)按需平面距離向量路由協(xié)議（Ad hoc On-demand Distance Vector Routing，AODV），進(jìn)而通過實驗來闡述DEDS理論在網(wǎng)絡(luò)仿真中的實際應(yīng)用。

AODV是經(jīng)典的源驅(qū)動路由協(xié)議，它包含3種消息類型：路由請求（RREQ）、路由回復(fù)（RREP）和路由錯誤（RERR）。整個協(xié)議分為路由發(fā)現(xiàn)和路由維護(hù)兩個階段。

AODV的優(yōu)點是避免了路由環(huán)路的產(chǎn)生，并且很容易通過編程來實現(xiàn)。

3.2.1 NS2中的AODV模擬

NS2是一個面向?qū)ο蟮模陔x散事件驅(qū)動的網(wǎng)絡(luò)仿真軟件。它使用面向?qū)ο蟮木幊陶Z言C++和Otcl，其特點是構(gòu)造模型的自由度高和支持并行化的擴(kuò)展，比較適合中小規(guī)模的網(wǎng)絡(luò)模擬。

本文采用的仿真場景是在1 000 m×600 m的空間中隨機(jī)配置100個移動節(jié)點，最大移動速度為15 m/s，仿真總時間設(shè)定為500 s。節(jié)點的運(yùn)動采用Random Waypoint模型，每個節(jié)點將會以給定的速度移至目的地，停留一段時間后，再向下一個隨機(jī)選取的目的地移動，所有節(jié)點均采用AODV路由協(xié)議。仿真中采用了7個不同的暫停時間：0 s，50 s，100 s，200 s，300 s，400 s，500 s，然后取7次仿真結(jié)果的平均值。為了評估AODV協(xié)議的性能，考慮選取歸一化路由開銷（Normalized Routing Overhead）、端到端時延（End To End Delay）、分組投遞率（Packet Delivery Ratio）和路由發(fā)現(xiàn)頻率（Initiated Routing Frequency）這幾個統(tǒng)計量作為評價的指標(biāo)[6]。實驗中首先使用NS2得出數(shù)據(jù)，然后用Matlab繪圖，結(jié)果如圖1—4所示。

如圖1所示，路由開銷隨著節(jié)點停留時間的延長而降低，這是因為網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的變化不再頻繁所致。圖2表明網(wǎng)絡(luò)整體的端到端時延隨節(jié)點停留時間的增加而降低。圖3表明分組投遞率隨節(jié)點停留時間的增加而提高。如圖4所示，路由發(fā)現(xiàn)頻率隨節(jié)點停留時間的增加而降低。

3.2.2 OPNET中的AODV模擬

OPNET采用離散事件驅(qū)動的模擬機(jī)理和混合建模機(jī)制，并提供了包括模型設(shè)計、仿真和統(tǒng)計量收集、分析的各種研究工具，同時它還引入了面向?qū)ο蟮木幊碳夹g(shù)。OPNET的特點是建模方便，功能強(qiáng)大，尤其是在大規(guī)模網(wǎng)絡(luò)模擬中表現(xiàn)卓越。

仿真場景是在一個1 000 m×1 000 m的空間中隨機(jī)配置1 000個節(jié)點，一個服務(wù)器，兩個標(biāo)準(zhǔn)應(yīng)用業(yè)務(wù)配Profile Configure和Application Configure，所有節(jié)點均采用AODV路由協(xié)議，仿真時間設(shè)為500 s。根據(jù)AODV和MANET的網(wǎng)絡(luò)特性，考慮選取端到端時延、負(fù)載、吞吐量、丟包數(shù)進(jìn)行分析，結(jié)果如圖5—8所示。

如圖5所示，AODV過程的端到端時延隨仿真時間的延長而略有增加，但整體還是比較穩(wěn)定的，這是因為節(jié)點在一個固定的區(qū)域內(nèi)移動，節(jié)點的通信距離覆蓋了區(qū)域的大部分，使得路由緩存不會輕易地發(fā)生更新所致。圖6和7表明隨著路由緩存的建立，網(wǎng)絡(luò)的負(fù)載和吞吐量逐漸增加，但經(jīng)過一段時間后，隨之趨于穩(wěn)定的狀態(tài)。如圖8所示，丟包數(shù)在不同的時間點上均保持在個位數(shù)，這說明AODV協(xié)議不僅具有良好的穩(wěn)定性，而且具有極高的傳輸效率。

4 結(jié)語

從以上實驗可看出，無論是在中小規(guī)模網(wǎng)絡(luò)仿真領(lǐng)域見長的NS2，還是在大規(guī)模網(wǎng)絡(luò)仿真領(lǐng)域表現(xiàn)卓越的OPNET，對于復(fù)雜的AODV協(xié)議都能做到全面而精確的仿真，當(dāng)然對于其他的網(wǎng)絡(luò)協(xié)議也同樣能夠做到。而它們都用到了DEDS理論的精華，像建模中的排隊論，仿真分析中的攝動分析法，以及數(shù)據(jù)統(tǒng)計中的概率分布、數(shù)學(xué)期望和方差、曲線擬合、似然比等。由此表明，DEDS理論無論是在中小規(guī)模還是在大規(guī)模網(wǎng)絡(luò)仿真領(lǐng)域都有非常普遍的應(yīng)用，因此，它的價值得以充分體現(xiàn)，同時這也為它在其他領(lǐng)域的應(yīng)用提供了充分的理論依據(jù)和豐富的實踐經(jīng)驗。