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

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

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

中圖分類號：TP39文獻標識碼：A文章編號：1672-3198（2008）06-0321-01

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

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

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

2 建立隨機模型分析的方法

2.1隨機過程概述

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

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

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

2.2排隊模型理論

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

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

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

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

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

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

通過前面的分析我們可以看出，采用排隊模型的方法來進行計算機網(wǎng)絡(luò)的性能分析只能刻畫網(wǎng)絡(luò)的基本行為，無法精確的刻畫網(wǎng)絡(luò)中的某些既隨機又相關(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，也稱為庫所、狀態(tài))元素、變遷(Transition)元素和連接它們的弧(arc)。把基本的Petri網(wǎng)模型中的變遷元素和時間隨機變量關(guān)聯(lián)起來就形成了隨機Petri網(wǎng)模型。總的來說，隨機Petri網(wǎng)具有下列特點:

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

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

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

3 結(jié)束語

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

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

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

參考文獻

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

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

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