離散事件動態系統及其在網絡仿真中的應用

張霖

摘 要：離散事件動態系統已成為控制領域的重要理論基礎。文章著眼于離散事件的理論體系，研究了離散事件動態系統的模型設計和分析方法。根據分析結果，結合工程實例，進行了基于DEDS理論的通信網絡仿真。仿真結果清晰地展示了通信網絡的各項性能指標，從而使離散事件動態系統的特性得以具體化。

關鍵詞：DEDS；系統仿真；模型

離散事件動態系統（Discrete Event Dynamic System，DEDS）是指系統的狀態由于某種事件的驅動而在一些不確定的離散時間點上發生變化，它是控制系統分析、設計和大型復雜信息處理的重要理論基礎。由于其內部機制的復雜性和狀態空間缺乏易操作的運算結構等特點，使得它無法用常規的數學方法來研究，所以計算機仿真實驗就成了最為實用的方法之一。現階段離散事件動態系統的研究目標是運用理論方法結合各種模型，全面反映離散事件動態系統的特性并給出針對實際問題的行之有效的解決方法。

1 離散事件動態系統概述

離散事件動態系統本質上屬于人造系統的范疇，而人造系統的含義是指以高技術為背景的一類按人為機制和人為規則所構成的“非物理型”系統，例如計算機通信網絡、柔性生產線等都是典型的人造系統，所以這些系統也可以稱之為DEDS。

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

2 離散事件系統仿真

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

2.1 基本概念

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

將離散事件系統表示為外部事件（X），輸出事件（Y），序貫狀態（S），狀態轉移描述函數（δ），輸出函數（λ）和時間推進函數（ta）的邏輯集合：

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

2.2 相關模型

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

理論模型是指對所研究的系統的理論描述，簡稱一次建模；它分為概念模型、描述模型、功能模型、約束模型、空間模型等5種基本類型。活動周期圖法、實體流圖法、Petri網法和Euler網法是幾種主要的理論模型建模方法。

仿真模型簡稱二次建模，它建立在理論模型的基礎之上，是一種易于在計算機上編程實現的模型。

將理論模型轉換成仿真模型，且能在計算機上運行，需要完成3個方面的工作：（1）設計仿真策略，確定仿真模型的表達方法和仿真運行的解算機制。（2）構造仿真模型，詳細設計基于某種仿真策略的仿真模型及解算機制。（3）編寫仿真程序，使用程序設計語言實現仿真模型[4]。

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

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

3 基于離散事件動態系統的網絡仿真

3.1 通信網絡中的DEDS理論

通信網絡作為典型的離散事件系統，它充分借鑒了DEDS理論的各項成果。

首先，排隊網理論就成功地運用在網絡建模中。排隊網絡的特點是運用概率和統計的方法對DEDS進行建模，一般是先對網絡特性作基本的假設，然后采用基于狀態穩態概率分布的平均性能分析方法，用以導出表征系統性能的解析表達式。它的優點是能夠很好地描述具有成熟的隨機過程和概率論的理論基礎和常規類型的排隊系統。

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

3.2 基于DEDS理論的AODV模擬

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

AODV是經典的源驅動路由協議，它包含3種消息類型：路由請求（RREQ）、路由回復（RREP）和路由錯誤（RERR）。整個協議分為路由發現和路由維護兩個階段。

AODV的優點是避免了路由環路的產生，并且很容易通過編程來實現。

3.2.1 NS2中的AODV模擬

NS2是一個面向對象的，基于離散事件驅動的網絡仿真軟件。它使用面向對象的編程語言C++和Otcl，其特點是構造模型的自由度高和支持并行化的擴展，比較適合中小規模的網絡模擬。

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

如圖1所示，路由開銷隨著節點停留時間的延長而降低，這是因為網絡拓撲結構的變化不再頻繁所致。圖2表明網絡整體的端到端時延隨節點停留時間的增加而降低。圖3表明分組投遞率隨節點停留時間的增加而提高。如圖4所示，路由發現頻率隨節點停留時間的增加而降低。

3.2.2 OPNET中的AODV模擬

OPNET采用離散事件驅動的模擬機理和混合建模機制，并提供了包括模型設計、仿真和統計量收集、分析的各種研究工具，同時它還引入了面向對象的編程技術。OPNET的特點是建模方便，功能強大，尤其是在大規模網絡模擬中表現卓越。

仿真場景是在一個1 000 m×1 000 m的空間中隨機配置1 000個節點，一個服務器，兩個標準應用業務配Profile Configure和Application Configure，所有節點均采用AODV路由協議，仿真時間設為500 s。根據AODV和MANET的網絡特性，考慮選取端到端時延、負載、吞吐量、丟包數進行分析，結果如圖5—8所示。

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

4 結語

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