計(jì)算機(jī)網(wǎng)絡(luò)建模數(shù)學(xué)工具的分析與比較

摘 要：論述了目前用于計(jì)算機(jī)網(wǎng)絡(luò)建模的幾種主要的數(shù)學(xué)工具，并且從網(wǎng)絡(luò)建模和模型求解之間存在的矛盾角度出發(fā)對(duì)這幾種數(shù)學(xué)工具進(jìn)行了分析和比較。對(duì)研究計(jì)算機(jī)網(wǎng)絡(luò)建模有一定的指導(dǎo)作用。

關(guān)鍵詞：計(jì)算機(jī)網(wǎng)絡(luò)；網(wǎng)絡(luò)建模；數(shù)學(xué)模型；隨機(jī)變量；概率

中圖分類號(hào)：TP39文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：1672-3198（2008）06-0321-01

1 計(jì)算機(jī)網(wǎng)絡(luò)的性能分析建模特點(diǎn)

計(jì)算機(jī)網(wǎng)絡(luò)研究與應(yīng)用的重要理論基礎(chǔ)和支撐技術(shù)是性能分析。要對(duì)網(wǎng)絡(luò)進(jìn)行性能分析必須先對(duì)要分析的網(wǎng)絡(luò)建立一個(gè)適當(dāng)?shù)哪Ｐ停缓笄蟪瞿Ｐ偷母黜?xiàng)性能指標(biāo)，以便對(duì)系統(tǒng)進(jìn)行性能分析。但是由于計(jì)算機(jī)網(wǎng)絡(luò)具有下列特點(diǎn):首先，計(jì)算機(jī)網(wǎng)絡(luò)內(nèi)部的任何一點(diǎn)上，基本數(shù)據(jù)單元的到達(dá)時(shí)間均為隨機(jī)變量。其次，組成網(wǎng)絡(luò)的各個(gè)單元之間相互作用，使得網(wǎng)絡(luò)中的數(shù)據(jù)流存在很強(qiáng)的相關(guān)性。因此既隨機(jī)又相關(guān)是計(jì)算機(jī)網(wǎng)絡(luò)中的數(shù)據(jù)流具有的特點(diǎn)。而網(wǎng)絡(luò)中數(shù)據(jù)流的本質(zhì)和特點(diǎn)又是我們?cè)趯?duì)計(jì)算機(jī)網(wǎng)絡(luò)進(jìn)行性能分析時(shí)所關(guān)心的。

在以往的性能分析工作中，一般都采用先建立網(wǎng)絡(luò)的分析模型，通過模型求解得出精確解或者是數(shù)值解;然后，再用模擬或者采用構(gòu)造系統(tǒng)測(cè)量的方法來驗(yàn)證得出的結(jié)果。但是在通過分析進(jìn)行性能評(píng)價(jià)的過程中，給系統(tǒng)建模和對(duì)模型求解一直是一對(duì)相互矛盾的過程。建立的系統(tǒng)模型越精確，則模型必然就越復(fù)雜，相應(yīng)的求解就越困難;反之，模型越簡(jiǎn)單，則求解就越容易，但結(jié)果的精確性也就越差。因此，我們?cè)趯?duì)計(jì)算機(jī)網(wǎng)絡(luò)進(jìn)行性能分析的過程中，始終考慮系統(tǒng)建模和模型求解之間的矛盾，兼顧建模的精確性和求解的可行性。因此，也將從這個(gè)角度來比較計(jì)算機(jī)網(wǎng)絡(luò)建模的各種數(shù)學(xué)工具。

2 建立隨機(jī)模型分析的方法

2.1隨機(jī)過程概述

隨機(jī)過程是定義在給定的概率空間上的一族隨機(jī)變量{X(t)，t T}，T表示參數(shù)空間。隨機(jī)變量x(t)是定義在概率空間上的實(shí)函數(shù)，x(t)所取的值表示隨機(jī)過程在時(shí)刻t的狀態(tài)，函數(shù)所有可能值的集合構(gòu)成了隨機(jī)過程的狀態(tài)空間。隨機(jī)變量的概率描述可以由概率分布函數(shù)F(X；t)=P{X（t ）＜x}和概率密度函數(shù)f（x；t）=F（x;t）x來表示。若考慮離散狀態(tài)的隨機(jī)過程，則概率分布函數(shù)為:Px(t)（k）=P{ X（t）=k}，∑allkPx(t)（k）=1 。包含n個(gè)隨機(jī)變量Xi（i=1，2.....，n）的隨機(jī)變量X的概率模型可由如下的單個(gè)隨機(jī)變量的聯(lián)隨機(jī)變量的概率特征的重要性在于它是一種將包含隨機(jī)變量本身的問題形式化的工具，可以通過在任意時(shí)刻抽取任意數(shù)目的隨機(jī)變量組成的任何隨機(jī)向量來刻畫一個(gè)隨機(jī)過程的完整概率特征。但是從求解的角度來說這是不可能實(shí)現(xiàn)的。

馬爾可夫過程(Markovproeess)是一類重要的隨機(jī)過程。它的狀態(tài)空間是有限的或是可數(shù)有限的，經(jīng)過一段時(shí)間系統(tǒng)從一個(gè)狀態(tài)轉(zhuǎn)移到另一個(gè)狀態(tài)的這種進(jìn)程只依賴于當(dāng)前出發(fā)時(shí)的狀態(tài)而與以前的歷史無關(guān)。這種特性稱為馬爾可夫特性，也就是也就是說馬爾可夫過程具有無記憶的特點(diǎn)。馬爾可夫過程廣泛的應(yīng)用于離散事件系統(tǒng)，具有離散狀態(tài)空間的馬爾可夫過程叫做馬爾可夫鏈，如果時(shí)間是連續(xù)的，則稱為連續(xù)時(shí)間馬爾可夫鏈。

如何恰當(dāng)?shù)亩x系統(tǒng)的狀態(tài)是直接在連續(xù)時(shí)間馬爾可夫鏈的層次上建模存在的主要困難。為了解決這個(gè)問題，又有一些更為抽象的概率模型被提了出來。

2.2排隊(duì)模型理論

排隊(duì)模型作為運(yùn)籌學(xué)研究的一種有力手段，在計(jì)算機(jī)網(wǎng)絡(luò)性能分析中占有相當(dāng)重要的地位，它是在隨機(jī)過程基礎(chǔ)之上發(fā)展起來的一種數(shù)學(xué)方法。

在現(xiàn)實(shí)生活中，排隊(duì)現(xiàn)象是隨處可見的。因?yàn)橘Y源總是有限的，而對(duì)資源的需求則是隨機(jī)的，因此從排隊(duì)現(xiàn)象中得到抽象的物理模型，并繼而建立數(shù)學(xué)模型的一整套理論就是所謂的排隊(duì)論了。典型的排隊(duì)系統(tǒng)如圖所示: 

從上面的圖中可以看出隊(duì)列和服務(wù)員是組成排隊(duì)系統(tǒng)的兩個(gè)基本要素。使用排隊(duì)模型對(duì)計(jì)算機(jī)網(wǎng)絡(luò)進(jìn)行建模時(shí)，服務(wù)員通常是由現(xiàn)實(shí)對(duì)象系統(tǒng)中的某一個(gè)獨(dú)立的功能部件(如:節(jié)點(diǎn)機(jī)、終端、線路或者是某一層次上的通信協(xié)議)所抽象出來的;而隊(duì)列所描述的是在現(xiàn)實(shí)對(duì)象系統(tǒng)中所有待處理的對(duì)象(通常稱為顧客)之間的序列關(guān)系。由于在現(xiàn)實(shí)系統(tǒng)中待處理對(duì)象是隨機(jī)發(fā)生的，因此它們到達(dá)隊(duì)列的分布可以用概率分布來刻畫，通常假定顧客到達(dá)或到達(dá)時(shí)間的間隔為相互獨(dú)立的且遵從同一分布的隨機(jī)變量。

排隊(duì)模型和馬爾可夫鏈之間存在著密切的聯(lián)系。通常的系統(tǒng)并不是孤立的排隊(duì)，實(shí)際上我們經(jīng)常遇到多個(gè)互連排隊(duì)的問題如顧客流的分開與合并等。而單個(gè)的排隊(duì)模型則是通過采用較為復(fù)雜的到達(dá)時(shí)間間隔和服務(wù)時(shí)間分布的概率密度函數(shù)來刻畫現(xiàn)實(shí)對(duì)象系統(tǒng)，這樣就需要引入多個(gè)服務(wù)員或者引入依賴于負(fù)載的服務(wù)率，分析求解超過了連續(xù)時(shí)間馬爾可夫鏈的能力。這一缺點(diǎn)的根本原因在于將特定系統(tǒng)的特征隱含在概率密度函數(shù)中所造成的模型復(fù)雜化。而排隊(duì)網(wǎng)絡(luò)正是解決這個(gè)問題而引入的。

排隊(duì)網(wǎng)絡(luò)是對(duì)現(xiàn)實(shí)對(duì)象系統(tǒng)的一個(gè)直接映射。典型的排隊(duì)網(wǎng)絡(luò)是一個(gè)有向圖G=(V，E)，其中v代表節(jié)點(diǎn)集合，而E=v x v代表一組弧。其中的每個(gè)節(jié)點(diǎn)代表一個(gè)服務(wù)站，表示實(shí)際系統(tǒng)中的某些主動(dòng)的資源，如:節(jié)點(diǎn)可以模擬通信系統(tǒng)中的交換機(jī)或者路由器等網(wǎng)絡(luò)節(jié)點(diǎn)。服務(wù)站包含一個(gè)隊(duì)列和一個(gè)或者多個(gè)服務(wù)員。E所代表的弧的集合則定義了網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，表示顧客流的可能通路。因而排隊(duì)網(wǎng)絡(luò)模型和單個(gè)的排隊(duì)模型相比更能夠刻畫系統(tǒng)對(duì)單個(gè)資源的共享。而在求解時(shí)就可以把網(wǎng)絡(luò)中的每個(gè)隊(duì)列都看成是一個(gè)獨(dú)立的因子，因而就可以通過這些獨(dú)立因子的乘積求出整個(gè)系統(tǒng)的性能。通常情況下，采用排隊(duì)模型的方法對(duì)計(jì)算機(jī)網(wǎng)絡(luò)進(jìn)行性能分析時(shí)所求解的都是信息穿過網(wǎng)絡(luò)的平均延遲時(shí)間。為了方便分析就需要引入獨(dú)立性假設(shè)。只有在此基礎(chǔ)上分析過程才能十分直接，否則求解過程將變得非常困難。

Jackson在1957年和1963年的發(fā)表的論文中給出了Jackson網(wǎng)絡(luò)模型，它給排隊(duì)網(wǎng)絡(luò)分析帶來了突破。Jackson網(wǎng)絡(luò)的穩(wěn)定狀態(tài)概率具有乘積形式的解，非常完美。但是Jackson網(wǎng)絡(luò)的結(jié)論是基于這樣的假設(shè): 首先，在任何網(wǎng)絡(luò)節(jié)點(diǎn)中的顧客的數(shù)量與其它任何節(jié)點(diǎn)中顧客的數(shù)量無關(guān)；其次，在任何網(wǎng)絡(luò)節(jié)點(diǎn)中顧客所經(jīng)歷的服務(wù)時(shí)間獨(dú)立于任何其它節(jié)點(diǎn)中顧客所經(jīng)歷的服務(wù)時(shí)間。而實(shí)際上這一假設(shè)并不成立。盡管在許多特定環(huán)境下的模擬和測(cè)量結(jié)果表明根據(jù)這一假設(shè)求解有很高的近似程度。

通過前面的分析我們可以看出，采用排隊(duì)模型的方法來進(jìn)行計(jì)算機(jī)網(wǎng)絡(luò)的性能分析只能刻畫網(wǎng)絡(luò)的基本行為，無法精確的刻畫網(wǎng)絡(luò)中的某些既隨機(jī)又相關(guān)的特性。

2.3petri網(wǎng)(PNs)理論

petri網(wǎng)(PNs)理論是1962年CarlAdamPetri博士在他的博士論文中首先提出來的。Petri網(wǎng)能夠?qū)哂胁⑿小⒉l(fā)、同步、資源共享等特性的系統(tǒng)建立模型，并且使之形象化。Petri網(wǎng)作為一種圖形化和形式化的建模工具，它包括位置(plaee，也稱為庫(kù)所、狀態(tài))元素、變遷(Transition)元素和連接它們的弧(arc)。把基本的Petri網(wǎng)模型中的變遷元素和時(shí)間隨機(jī)變量關(guān)聯(lián)起來就形成了隨機(jī)Petri網(wǎng)模型。總的來說，隨機(jī)Petri網(wǎng)具有下列特點(diǎn):

(1)基本的隨機(jī)Petri網(wǎng)模型可以很方便的描述網(wǎng)絡(luò)中的相關(guān)時(shí)間，描述網(wǎng)絡(luò)中的同步、競(jìng)爭(zhēng)、碰撞和擁塞等行為。

(2)隨機(jī)Petri網(wǎng)中的時(shí)間變遷元素和時(shí)間隨機(jī)變量相關(guān)聯(lián)，可以很好的描述計(jì)算機(jī)網(wǎng)絡(luò)事件的隨機(jī)性。

(3)隨機(jī)Petri網(wǎng)可以同構(gòu)于相應(yīng)的馬爾可夫隨機(jī)過程，從而可以在隨機(jī)過程的層次上進(jìn)行模型求解。

3 結(jié)束語(yǔ)

綜上所述，我們介紹了目前用于計(jì)算機(jī)網(wǎng)絡(luò)性能分析的數(shù)學(xué)工具，并且從系統(tǒng)建模和模型求解之間存在的相互矛盾角度出發(fā)對(duì)各種模型工具進(jìn)行了分析和比較。

隨機(jī)過程是各種性能分析工具的基礎(chǔ)，也就是計(jì)算機(jī)網(wǎng)絡(luò)性能分析的基礎(chǔ)。但是，對(duì)于計(jì)算機(jī)網(wǎng)絡(luò)來說，在隨機(jī)過程層次上直接建立網(wǎng)絡(luò)模型的主要困難在于怎樣恰當(dāng)?shù)膶?duì)網(wǎng)絡(luò)系統(tǒng)的狀態(tài)進(jìn)行定義。排隊(duì)論是在隨機(jī)過程基礎(chǔ)之上發(fā)展起來的一種數(shù)學(xué)建模工具，在實(shí)際中有著廣泛的應(yīng)用。但使用排隊(duì)模型只能描述網(wǎng)絡(luò)系統(tǒng)的基本行為，難以精確的分析和描述網(wǎng)絡(luò)的既隨機(jī)又相關(guān)的特性。

近年來，隨著Petri網(wǎng)理論的不斷發(fā)展，其應(yīng)用范圍也越來越廣，它是計(jì)算機(jī)網(wǎng)絡(luò)系統(tǒng)性能分析中一個(gè)很有吸引力的數(shù)學(xué)工具。它在一定程度上可以緩解系統(tǒng)建模和模型求解之間存在的矛盾。在未來它將成為研究的主流方向。

參考文獻(xiàn)

［1］施仁杰.馬爾可夫鏈基礎(chǔ)及應(yīng)用［M］.西安：電子科技大學(xué)出版社，1992.

［2］唐應(yīng)輝，唐小我.排隊(duì)論一基礎(chǔ)與應(yīng)用［M］.西安：電子科技大學(xué)出版社，2000.

注：“本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文。”