摘 要：對計(jì)算機(jī)系統(tǒng)與計(jì)算機(jī)網(wǎng)絡(luò)進(jìn)行資源分配以及任務(wù)調(diào)度使用的理論工具是動(dòng)態(tài)優(yōu)化。當(dāng)前，隨著計(jì)算系統(tǒng)以及計(jì)算網(wǎng)絡(luò)的發(fā)展，國內(nèi)外已經(jīng)對計(jì)算機(jī)系統(tǒng)以及計(jì)算機(jī)網(wǎng)絡(luò)中的動(dòng)態(tài)優(yōu)化進(jìn)行深度的研究，以期能夠?qū)?shí)際的應(yīng)用有所幫助。本文通過馬爾可夫決策從模型、求解、應(yīng)用方面對計(jì)算機(jī)系統(tǒng)與計(jì)算機(jī)網(wǎng)絡(luò)展開討論。

關(guān)鍵詞：計(jì)算機(jī)與計(jì)算機(jī)網(wǎng)絡(luò)；動(dòng)態(tài)優(yōu)化；馬爾可夫決策

中圖分類號：TP393.0

目前，隨著計(jì)算機(jī)系統(tǒng)與計(jì)算機(jī)網(wǎng)絡(luò)在人們生活中的普遍使用，計(jì)算機(jī)網(wǎng)絡(luò)以及計(jì)算機(jī)系統(tǒng)不斷延伸拓展到社會各行各業(yè)中，計(jì)算機(jī)使用的廣泛性，使得其業(yè)務(wù)數(shù)量與業(yè)務(wù)種類不停的增加[1]。數(shù)量與種類的不斷增加，使得人們不得不開始思考如何在復(fù)雜的計(jì)算機(jī)網(wǎng)絡(luò)中對有限的資源進(jìn)行合理分配，已達(dá)到提高計(jì)算機(jī)網(wǎng)絡(luò)運(yùn)行效率的目的。在計(jì)算機(jī)網(wǎng)絡(luò)運(yùn)行的過程中，降低計(jì)算機(jī)網(wǎng)絡(luò)運(yùn)行的成本是亟需解決的問題。對資源和任務(wù)進(jìn)行調(diào)度常常使用的理論是優(yōu)化理論。從不同的維度對優(yōu)化理論進(jìn)行分類可以劃分為動(dòng)態(tài)優(yōu)化和靜態(tài)優(yōu)化理論。由于靜態(tài)優(yōu)化理論在實(shí)際的運(yùn)用過程中會存在較多的問題。因此，實(shí)際運(yùn)用中常常使用動(dòng)態(tài)優(yōu)化理論。馬可夫的決策過程（Markov Decision Process，MDP）是動(dòng)態(tài)優(yōu)化理論的基本模型[2]。隨著計(jì)算機(jī)的廣泛應(yīng)用，計(jì)算機(jī)網(wǎng)絡(luò)系統(tǒng)的資源管理方面會出現(xiàn)各種問題，而MDP模型的建立通?？梢员苊庥?jì)算機(jī)網(wǎng)絡(luò)“狀態(tài)空間爆炸”的現(xiàn)象出現(xiàn)。MDP模型有效解決精確結(jié)算法中出現(xiàn)的各種問題。筆者通過本文，對此進(jìn)行分析。

1 馬爾可夫決策過程中動(dòng)態(tài)模型的建立

1.1 馬爾可夫的決策過程

馬爾可夫基本的決策過程步驟主要包括以下幾個(gè)步驟：首先具有一個(gè)描述性的狀態(tài)集合S，通過這個(gè)描述狀態(tài)的集合決策者可以在此集合內(nèi)進(jìn)行相關(guān)的行為，決策者在狀態(tài)空間中的行為具有歸為一個(gè)名為行為集合A。當(dāng)然，決策者在對描述集合內(nèi)進(jìn)行的相關(guān)行為所產(chǎn)生的收益就可以命名為收益函數(shù)R。在整個(gè)馬爾可夫決策的過程中，會逐漸產(chǎn)生一定關(guān)系記錄決策者在描述狀態(tài)下的轉(zhuǎn)移過程，即狀態(tài)轉(zhuǎn)移關(guān)系SM。馬爾可夫的決策過程是根據(jù)下一時(shí)刻的狀態(tài)進(jìn)行決策，而與系統(tǒng)的歷史性無關(guān)。通常情況下，根據(jù)SM的性質(zhì)可以將MDP分為隨機(jī)的MDP和確定的MDP兩類。確定的MDP在一定的狀態(tài)隨著行動(dòng)的轉(zhuǎn)移導(dǎo)致確定的狀態(tài)轉(zhuǎn)移。而隨機(jī)的MDP不僅要根據(jù)當(dāng)前狀態(tài)下決策者的行為，還會受到一定的外部用隨機(jī)變量W的影響。通常情況下，研究馬爾可夫的決策過程，指的是隨機(jī)MDP。其實(shí)在馬爾可夫決策過程中，狀態(tài)集合S到行為集合A中的一個(gè)映射被定義為π[3]。決策者根據(jù)π的具體情況來確定所需要的行為。在實(shí)際決策的過程中，典型的馬爾可夫決策過程如下：首先，決策者觀察所處的決策環(huán)境里面的狀態(tài)S。其次，根據(jù)狀態(tài)將進(jìn)一步確定決策者的決策行為π，將該行為在系統(tǒng)中進(jìn)行轉(zhuǎn)換，然后再重復(fù)前面的步驟，就可以將馬爾可夫的決策過程完成。隨著馬爾可夫系統(tǒng)的演進(jìn)過程，其行為會產(chǎn)生一定的收益序列。將所獲得MDP進(jìn)行比較，將其轉(zhuǎn)換成目標(biāo)函數(shù)J，確定為一個(gè)確定的實(shí)數(shù)值。

1.2 馬爾可夫決策過程的建模與分析

將馬爾可夫決策理論運(yùn)用于實(shí)際中，根據(jù)該理論建立相關(guān)的模型。其具體的運(yùn)用操作包括以下幾個(gè)方面。首先應(yīng)當(dāng)明確馬爾可夫過程建模的目標(biāo)。 在確定馬爾可夫決策的過程中，根據(jù)受益目標(biāo)的不同，運(yùn)行系統(tǒng)的不同其導(dǎo)致的目標(biāo)可能不同。即使是同一系統(tǒng)，由于研究角度的差異也會導(dǎo)致收益函數(shù)和目標(biāo)函數(shù)的不同。以計(jì)算機(jī)網(wǎng)絡(luò)為例，常見的目標(biāo)函數(shù)有能量的消耗、延遲、分組丟失率以及節(jié)點(diǎn)吞吐量。隨機(jī)的MDP，會帶有期望的形式（E）的目標(biāo)函數(shù)。期望函數(shù)中有限的馬爾可夫決策過程和無限的馬爾可夫決策過程形式分別表現(xiàn)為：

有限的馬爾可夫決策形式：

無限的馬爾可夫決策形式：

在系統(tǒng)運(yùn)行的過程中，根據(jù)目標(biāo)函數(shù)和各級函數(shù)的不同，其可以不斷根據(jù)目標(biāo)函數(shù)進(jìn)行最大化和最小化進(jìn)行變化[4]。通過相應(yīng)的操作可以對馬爾可夫進(jìn)行相關(guān)的調(diào)整。其次，根據(jù)運(yùn)行狀態(tài)空間進(jìn)一步確定決策的行為。在馬爾可夫決策過程形成的過程中，系統(tǒng)的狀態(tài)空間和決策行為空的有可能處于游離的狀態(tài)。游離的狀態(tài)下會在一定程度上占用無線電系統(tǒng)的空間。狀態(tài)空間系統(tǒng)以及決策行為的確定可以為用戶確定一定的取值范圍。在對馬爾可夫決策過程分析的過程中，對馬爾可夫決策過程進(jìn)行分類。根據(jù)不同的依據(jù)，馬爾可夫可以分為幾種不同的類型

2 馬爾可夫決策過程的求解

在實(shí)際操作的過程中，馬爾可夫的決策過程通?？梢詺w類為兩種：精確求解算法和近似求解算法。根據(jù)精確求算法可以滿足用戶在折優(yōu)情形下用戶的最優(yōu)解。而近似求解法則是在一個(gè)系統(tǒng)中對資源和數(shù)據(jù)進(jìn)行相關(guān)的調(diào)整以及建立相應(yīng)的數(shù)據(jù)，滿足用戶的需求。這兩種算法在實(shí)際的運(yùn)用過程中，由于使用方式的不同，兩種方法根據(jù)實(shí)際情況各存在不同的分類方法。用戶根據(jù)自己的實(shí)際情況對其進(jìn)行分類運(yùn)用。

3 馬爾可夫決策過程的應(yīng)用

本文在對馬爾可夫應(yīng)用進(jìn)行分析的過程中將一個(gè)可以修復(fù)的系統(tǒng)為例進(jìn)行講解。對該模型進(jìn)行分析。

圖1中的左半部分是一個(gè)可能正常工作、可能失效的隨機(jī)子網(wǎng)，右半部分則為描述決策者的行為。包括對相關(guān)資源的分配。在MDPN的模型中，對相關(guān)的標(biāo)記進(jìn)行改良后可以獲得改善的網(wǎng)絡(luò)。該模型可以很好地處理系統(tǒng)中的對稱性問題?？s小空間中問題。當(dāng)前，基于對計(jì)算機(jī)系統(tǒng)以及計(jì)算機(jī)網(wǎng)絡(luò)的研究和應(yīng)用，分別對馬爾可夫的相關(guān)理論展開分析，有利于計(jì)算機(jī)網(wǎng)絡(luò)以及計(jì)算機(jī)的發(fā)展。將有關(guān)的理論運(yùn)用其中，可以有效解決資源管理中的各項(xiàng)問題。

4 結(jié)束語

計(jì)算機(jī)系統(tǒng)與計(jì)算機(jī)網(wǎng)絡(luò)中的資源和種類極其復(fù)雜，面對對計(jì)算機(jī)系統(tǒng)以及計(jì)算網(wǎng)絡(luò)運(yùn)用如此廣泛的環(huán)境下，運(yùn)用動(dòng)態(tài)理論對系統(tǒng)進(jìn)行建模，并對此進(jìn)行求解，有助于計(jì)算機(jī)系統(tǒng)和計(jì)算機(jī)網(wǎng)絡(luò)的發(fā)展。為計(jì)算機(jī)系統(tǒng)和計(jì)算機(jī)網(wǎng)絡(luò)系統(tǒng)的研究提供了一個(gè)研究方向，將有利于我國科學(xué)技術(shù)的發(fā)展。

參考文獻(xiàn)：

[1]林闖，萬劍雄，向旭東，等.計(jì)算機(jī)系統(tǒng)與計(jì)算機(jī)網(wǎng)絡(luò)中的動(dòng)態(tài)優(yōu)化：模型、求解與應(yīng)用[J].計(jì)算機(jī)學(xué)報(bào)，2012（35）：20-22.

[2] Srivastava Rahul，Koksal Can Emre. Energy optimal trans-mission scheduling in wireless sensor networks. IEEE Trans-actions on Wireless Communications，2010（05）：1550-1560.

[3]王元卓，林闖，程學(xué)旗，方濱興.基于隨機(jī)博弈模型的網(wǎng)絡(luò)攻防量化分析方法[J].計(jì)算機(jī)學(xué)報(bào)，2010（09）：1748-1762.

[4]林闖，王元卓，汪洋.基于隨機(jī)博弈模型的網(wǎng)絡(luò)安全評價(jià)與分析[J].計(jì)算機(jī)學(xué)報(bào)，2011（24）：12.

作者簡介：楊曉慶（1980-），女，陜西鳳翔人，碩士，講師，主要研究方向：計(jì)算機(jī)技術(shù)。

作者單位：河南建筑職業(yè)技術(shù)學(xué)院，鄭州 450007