工程化教學(xué)思想在隨機過程與排隊論課程中的體現(xiàn)

文章編號：1672-5913(2008)18-0140-02

摘要：隨機過程與排對論課程屬于計算機科學(xué)與技術(shù)專業(yè)研究生課程基礎(chǔ)課程。本文介紹了我院是如何將工程化教學(xué)思想應(yīng)用于課程教學(xué)中，從而對學(xué)生理解和掌握隨機過程與排隊論理論，并熟練運用所學(xué)知識起到非常積極的作用。

關(guān)鍵詞：隨機過程；排隊論；工程應(yīng)用

中圖分類號：G642 文獻標(biāo)識碼：B

1引言

當(dāng)前計算機科學(xué)技術(shù)發(fā)展非常迅猛，而計算機科學(xué)的研究也是日新月異。在計算機科學(xué)研究中，一些最基本的研究工具必不可少，例如對算法的推導(dǎo)，優(yōu)化方案設(shè)計等。因此在計算機科學(xué)研究生教學(xué)階段，有必要將科學(xué)研究中需要的一些基礎(chǔ)知識開設(shè)為必修課程。在具體教學(xué)過程中，則體現(xiàn)為一門門的數(shù)學(xué)課程或基本的物理課程。

隨機過程與排隊論作為計算機科學(xué)研究必須的數(shù)學(xué)工具之一，通常被計算機科學(xué)與技術(shù)專業(yè)列為研究生必修課程。它是學(xué)生進一步科學(xué)研究或者前往公司負責(zé)重要的項目設(shè)計的理論基礎(chǔ)。除了作為數(shù)學(xué)課程能訓(xùn)練拔高邏輯思維之外，這門課程從本身理論價值的角度來看，它所涉及的概率知識、馬爾科夫過程知識、隱馬爾科夫過程、生滅過程、以及各類排隊模型和解決方法在信號處理、模式識別、通訊、計算機網(wǎng)絡(luò)設(shè)計、管理科學(xué)等領(lǐng)域都有重要應(yīng)用價值。同時，課程所涉及的一些理論研究方法，證明過程也為學(xué)生將來進一步的科學(xué)研究提供了范本。學(xué)生通過學(xué)習(xí)該門課程將能懂得如何設(shè)計排隊模型，如何設(shè)計以及分析算法性質(zhì)等。

在實際的教學(xué)過程中，許多院校多采用數(shù)學(xué)專業(yè)教師編寫的《隨即過程》和《排隊論》這兩本教材。由于數(shù)學(xué)專業(yè)教師比較重視嚴(yán)謹(jǐn)?shù)睦碚撟C明以及邏輯分析，在書中對這些知識是如何產(chǎn)生，以及在計算機科學(xué)中如何應(yīng)用卻涉及不多。計算科學(xué)與技術(shù)專業(yè)的學(xué)生學(xué)后多感覺目的性不強，也導(dǎo)致對知識理解不深。本文將通過若干具體例子，列舉結(jié)合工程應(yīng)用講述隨機過程與排隊論知識的方法，實際教學(xué)效果表明，結(jié)合工程化應(yīng)用將很大程度地幫助學(xué)生理解并應(yīng)用本門課程知識。

2結(jié)合信號處理講述隨機過程相關(guān)概念

在講述該概念過程中，大多人為構(gòu)造一些隨機過程的例子，計算相關(guān)函數(shù)和互相關(guān)函數(shù)。學(xué)生一般都能理解如何計算相關(guān)函數(shù)和互相關(guān)函數(shù)。此后，隨機課程教學(xué)將轉(zhuǎn)入馬爾科夫過程，此概念就未再涉及。學(xué)生學(xué)習(xí)后，并不了解這個概念的實際意義和如何應(yīng)用這個概念。在教學(xué)中，我們將討論運用去相關(guān)的方法進行盲信號分離。

給定觀察信號x(t)={x1(t)，x2 (t)，…，xn(t)，}，源信號s(t)={s1(t)，s2 (t)，…，sn(t)}和未知非奇異混合矩陣A∈Rnxn，其中x(t)=Rs(t)，盲信號分離即是找到矩陣W∈Rnxn，在未知矩陣A和源信號的情形下，使得y(t)=Wx(t)與源信號相似。盲信號分離在圖像分離、生物信號處理、軍事都有非常重要的應(yīng)用。在這里我們用去相關(guān)的方法從觀察信號中獲得源信號。此處假設(shè)信號自身具有較強相關(guān)性，而信號之間相關(guān)性不強。給定兩個時間s，t，如果矩陣E(y(s)y(t)T) 逼近對角型，則此時的y(t)即為恢復(fù)的源信號。注意到y(tǒng)(t)=Wx(t)，有

F(t)=WE(x(t)x(s) T)WT。

由上，問題轉(zhuǎn)化為對矩陣E(x(t)x(s) T)對角化，即是求矩陣E(x(t)x(s) T)特征值與特征向量。如果存在時間s，t，使得矩陣E(x(t)x(s) T)特征值互不相同，則特征向量矩陣即為我們所尋找的分離矩陣W。

在教學(xué)過程中，我們同時展示以信號處理的試驗，通過工程化應(yīng)用加深了學(xué)生對概念的理解，也使他們更容易運用所學(xué)概念于實際應(yīng)用之中。除此之外，隨機過程的一些基本概念還可以用其它信號處理和工程應(yīng)用講述，在這里不再贅述。

3結(jié)合信息安全講述馬爾科夫過程

例2在隨機過程中有一個重要的概念稱為馬氏鏈[1]。定義如下：設(shè){X(n)，n=0，1，2，…}為隨機序列，狀態(tài)空間E={0，1，2，…}。如果對于任意非負整數(shù)k、n1

P{X(m+k)=im+k|X(n1)=in1，X(n2)=in2，…，X(nj)=inj，X(m)=im}

=P{X(m+k)=im+k|X(m)=im}

成立，則稱{X(n)，n=0，1，2，…}為離散參數(shù)馬爾可夫鏈，簡稱馬氏鏈。設(shè){X(n)，n=0，1，2，…} 為馬氏鏈，E={0，1，2，…}，稱條件概率

pij(m，k)＝P{X(m+k)=j|X(m)=i}

為馬氏鏈{X(n)，n=0，1，…}在m時刻的k步轉(zhuǎn)移概率。特別地，k=1時，

pij(m，1)＝P{X(m+1)=j|X(m)=i}

稱為一步轉(zhuǎn)移概率，簡稱轉(zhuǎn)移概率。其中有一定理：齊次馬氏鏈的有限維分布由初始分布和轉(zhuǎn)移概率確定，且滿足

P{X(n1)=i1，X(n2)=i1，…，X(nk)=ik}

其中P{X(n1)=i1，X(n2)=i2，…，X(nk)=ik}為齊次馬氏鏈的k維概率分布。

在教學(xué)中，我們結(jié)合計算機主機入侵檢測來講述這個概念。通過觀察發(fā)現(xiàn)，正常系統(tǒng)調(diào)用跡中存在大量的有規(guī)律的、重復(fù)出現(xiàn)的系統(tǒng)調(diào)用序列，把這些重復(fù)出現(xiàn)的序列看成一個獨立的基本單位( 宏)可以更精確地刻畫程序的正常行為模式[2]。將每一個宏看成一種在馬爾科夫模型中的狀態(tài)假定在t時刻系統(tǒng)狀態(tài)的隨機狀態(tài)變量為Xt，建立如上所示馬爾可夫鏈模型。則狀態(tài)序列it-k，i2，…，it發(fā)生的概率可由上述定理計算獲得

P(it-k，i2，…，it)= 。

將系統(tǒng)軌跡根據(jù)獨立的基本單位(宏)，按對宏的編號重新組織為一新的序列L，概率P的計算方法如下： Pij= ，Pi= 。這里Nij為在L中觀察到在t處為狀態(tài)i和t+1處在狀態(tài)j的對的個數(shù)。Ni在L中觀察到狀態(tài)為i的個數(shù)，N表示L中所有觀察到的宏的個數(shù)。檢測的依據(jù)就是通過計算t時刻的15個連續(xù)的宏狀態(tài)出現(xiàn)的概率。概率越高者則它越可能屬于正常的宏狀態(tài)序列。

在結(jié)合信息安全中主機入侵檢測工程應(yīng)用講述馬爾科夫鏈后，許多學(xué)生舉一反三思考了將馬爾科夫鏈用于網(wǎng)絡(luò)入侵檢測，金融序列分類等等。從這里可以看出，結(jié)合工程應(yīng)用講述隨機過程，將對于學(xué)生掌握理論知識并靈活運用這些知識有很重要的幫助。

4結(jié)合計算機網(wǎng)絡(luò)講述排隊論

研究排隊現(xiàn)象的目的是：通過對排隊系統(tǒng)中概率規(guī)律的研究，使系統(tǒng)達到最優(yōu)設(shè)計和最優(yōu)控制，以最小費用實現(xiàn)系統(tǒng)的最大效益。

例3 在排隊論中講述了如下圖1所示M/M/c:N/∞/FCFS排隊系統(tǒng)[3]，

設(shè)系統(tǒng)容量為N(N≥c)，當(dāng)系統(tǒng)中的顧數(shù)n＜N時，到達的顧客就進入系統(tǒng)；當(dāng)n=N時，到達的顧客就被拒絕。設(shè)顧客到達的速率為λ，每個服務(wù)臺服務(wù)的速率為μ，服務(wù)能力ρ=λ/cμ。由于系統(tǒng)不會無限止地接納顧客，對ρ不必加以限制。建立了該模型后，我們計算了系列參數(shù)如隊長概率

， .

相應(yīng)地我們能計算平均對長、平均等待對長、平均等待時間、 平均逗留時間等。在傳統(tǒng)的排隊論教材中，再講述了如何計算參數(shù)后，一般都舉一些簡單的例子計算相關(guān)參數(shù)。針對計算機科學(xué)專業(yè)學(xué)習(xí)排隊論重在應(yīng)用的特點，我們講述了該系統(tǒng)在計算機網(wǎng)絡(luò)流量控制模型設(shè)計中的應(yīng)用。

只要存在“Client/Server”的環(huán)境，就可以采用排隊模型進行分析。在一個基于Client/Server模型的計算機應(yīng)用系統(tǒng)中，非常適合采用排隊論M/M/c:N/∞/FCFS模型來進行流量控制，當(dāng)Client請求超過Server設(shè)計容量時，能避免Server的負荷惡性增長，確保系統(tǒng)能提供設(shè)計容量的服務(wù)。如圖2所示[4]。

這樣，當(dāng)業(yè)務(wù)請求書超過最大并發(fā)處理數(shù)c時，可將業(yè)務(wù)請求放入排隊隊列中進行排隊，因排隊過程一般不消耗Server負荷，可以確保Server的平穩(wěn)運行。近似認為Client的請求服從Poisson分布，服務(wù)能力滿足負指數(shù)分布，則完全可以通過排隊論[M/M/c]:[N/∞/FCFS]模型計算出服務(wù)能力、業(yè)務(wù)請求流量、排隊隊列與接通率、平均排隊時間、平均逗留時間的關(guān)系。則：

(1) 在某種業(yè)務(wù)請求流量下，為獲得需要的接通率，我們可以計算出合適的隊列長度。

(2) 在大業(yè)務(wù)量情況下，如果限定逗留時長，可計算出一個合適的排隊隊列長度，當(dāng)排隊長度超過該值時，業(yè)務(wù)請求再繼續(xù)排隊就沒有意義。(比如設(shè)定超時退出機制的環(huán)境)

(3) 對于關(guān)鍵業(yè)務(wù)請求，可以通過增大排隊隊列長度來提高接通率。

在教學(xué)過程中，我們還結(jié)合其他更加復(fù)雜的通信網(wǎng)絡(luò)介紹排隊模型。學(xué)生學(xué)習(xí)后，不在感覺像學(xué)純數(shù)學(xué)一樣枯燥，并對排隊論應(yīng)用于實踐充滿興趣，同時也有同學(xué)嘗試將排隊論知識應(yīng)用于金融和優(yōu)化管理中，取得較好效果。

5小結(jié)

從本文的分析可以看出，在計算機科學(xué)與技術(shù)專業(yè)研究生數(shù)學(xué)教學(xué)中，不能單純地講解數(shù)學(xué)證明和簡單地計算人為構(gòu)造的例子和習(xí)題。簡單的數(shù)學(xué)學(xué)習(xí)學(xué)生并不能很好地了解這些數(shù)學(xué)知識在工程上的來源以及所能解決的具體應(yīng)用問題。在教學(xué)中，我們嘗試將工程化應(yīng)用與數(shù)學(xué)教學(xué)相結(jié)合，一方面使學(xué)生對隨機過程與排隊輪本身知識體系和思維方式有了更深的理解，另一方面使他們更容易找到如何利用所學(xué)數(shù)學(xué)知識進行科學(xué)研究的感覺。很多學(xué)生能做到舉一反三，將所學(xué)知識應(yīng)用到不同情形下的計算機應(yīng)用中。

參 考 文 獻

[1] 劉次華. 隨機過程(第2版)[M]. 武漢:華中科技大學(xué)出版社，2003:23，27.

[2] 徐明，丁宏，陳純. 基于系統(tǒng)調(diào)用宏的馬爾可夫鏈入侵檢測模型[J]. 浙江大學(xué)學(xué)報(工學(xué)版)，2005，(2).

[3] 唐應(yīng)輝，唐小我. 排隊論-基礎(chǔ)與應(yīng)用[M]. 成都:電子科技大學(xué)出版社，1999:65，74.[4] 徐昌彪，鮮永菊. 計算機網(wǎng)絡(luò)中的擁塞控制與流量控制[M]. 北京:人民郵電出版社，2007:211，2

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