計算機系統(tǒng)與計算機網(wǎng)絡(luò)中的動態(tài)優(yōu)化：模型、求解與應(yīng)用

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

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

中圖分類號：TP393.0

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

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

1.1 馬爾可夫的決策過程

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)束語

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

參考文獻：

[1]林闖，萬劍雄，向旭東，等.計算機系統(tǒng)與計算機網(wǎng)絡(luò)中的動態(tài)優(yōu)化：模型、求解與應(yīng)用[J].計算機學報，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]王元卓，林闖，程學旗，方濱興.基于隨機博弈模型的網(wǎng)絡(luò)攻防量化分析方法[J].計算機學報，2010（09）：1748-1762.

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

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

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