計算機系統與計算機網絡中的動態優化：模型、求解與應用

孫丹丹

摘要：針對計算機系統在網絡應用中存在主要問題，該文給出了基于動態優化的設計方案，通過對動態優化數學模型的建立與求解，實現了動態優化在計算機系統及其網絡中的應用。對比靜態優化理論，對動態優化中應用馬爾可夫決策過程進行了詳細的討論與分析。依據馬爾可夫決策過程深入的研究討論了計算機系統與計算機網絡中的建模、求解方法和應用實例。

關鍵詞：計算機系統；動態優化；模型解析

中圖分類號：TP311 文獻標識碼：A 文章編號：1009-3044（2017）35-0038-02

近年來，計算機系統和計算機網絡對居民生活所產生的影響越來越大，在各個領域的應用也越來越多，不僅在高端科研實驗中大量應用，而且深入到了人們的日常生活中。在這樣的復雜背景下，想要提高計算機網絡和計算機系統的運行效率，就不得不面對系統資源如何分配、系統數據如何調動等問題，而且為了公眾效益，降低成本也是十分關鍵的問題。

優化理論是研究計算機網絡以及計算機系統的一種常見的方法之一，主要用于處理資源分配還有任務調度等問題。優化理論可以根據時間維度分為靜態優化和動態優化兩種方式。兩種優化方式中的靜態優化系統是不隨時間的變化而改變，也就是說計算機系統中資源的需求量和保有量是不隨時間變化而變化的常量。然而，在實際應用的過程中，計算機系統并不是一成不變的，它不僅可能受到時間變化的影響，而且往往會被外界環境所干擾，這就導致在未來可能發生的變化被靜態優化系統所忽略，從而不能反映出因為決策者的行為，然后對未來可能產生的影響，體現不出系統受時間影響的特性。綜上，本文將以動態優化的處理方法去處理計算機網絡和計算機系統的應用問題。進行動態優化時，關于時間累積量的系統收益是系統的目標函數，對比與靜態優化，動態優化可以更好地體現出系統的時變性，亦能反映出隨時間累積，決策者的決策對目標函數的影響。

馬爾可夫決策過程（MDP）是動態優化的基本理論模型。具體定義為：根據決策者的行為，并依賴時間t的系統狀態，可以推斷出系統在t+1時刻時的狀態轉移情況，且在[0，t+1]的時間段中，決策者的行為對系統狀態不產生影響。對于當前計算機系統和計算機網絡中，動態優化模型一直是解決資源分配、資源整理和任務調度等問題的一個熱點。本文利用馬爾可夫決策過程，從建立模型、找出解答方法及提出應用等角度，論述了動態優化理論的實際應用。

1 動態優化理論模型構建

1.1 馬爾可夫決策過程

馬爾可夫決策過程包含的要素有：

1） 用來描述系統狀態的狀態集合S；

2） 在狀態空間中決策者可能發生的行為，也就是依賴于當前狀態下決策者的行為集合，用A（s）來表示；

3） 收益函數是指決策者發出行為，并且該行為對系統產生了影響，因此而產生效益；

4） 當下一時刻計算機系統的狀態僅受決策者行為和當前狀態影響，即與系統的歷史狀態無關時，將這一特性稱為馬爾可夫決策過程的后效性，它是馬爾可夫決策過程的一個顯著特性。

1.2 馬爾可夫決策流程

馬爾可夫決策過程中決策者當前所需的決策行為一般根據策略π來得到，策略π是一個從狀態集合S到行為集合A的映射。馬爾可夫決策過程一般都具有四個執行流程，分別是：

1） 首先由決策者觀察所處狀態s（當前狀態）；

2） 獲得已知狀態信息后，根據該信息發出決策行為π（s）；

3） 系統狀態可能會因為行決策行為π（s）的發出而發生轉換；

4） 重復流程1中的操作。

系統在執行時，會由MDP生成一個收益序列，引入目標函數J，目的是用來比較MDP中決策者發出的策略的優劣程度，且收益序列將會被映射成一個實數值。

1.3 值函數

值函數是MDP中的非常重要概念之一，用表示。是一個映射，范圍是從π×S到R（實數集）。的含義為：已知策略π，狀態，求得目標函數J的期望，且在無限時間內，MDP滿足遞推方程，即：

（1）

式中，α—折扣因子，根據式（1）不難看出，策略是收益的和。式（1）也可寫為向量形式，即：

（2）

2 馬爾可夫過程數學解

1） 運行目標

首先，對于隨機MDP，目標函數常帶有期望形式（E），一般帶有期望的目標函數分為有限馬爾可夫決策流程和無限馬爾可夫決策流程，具體形式如下：

有限：

（3）

無限：

（4）

（5）

式中，—系統所處狀態，—決策者采取的行為。式（4）位無窮時間折扣情況下的目標函數，式（5）為無窮時間平均情形下的目標函數，通常情況下，最大（小）化上述目標函數J，從而得到運行目標。

2） 狀態空間分析

系統的狀態空間和決策者的行為空間，滿足特定條件時，可能是有聯系的，在無線電系統中，如果用戶設為發射數據的概率為P，則用戶的行為空間就是連續的，行為空間的取值范圍是固定的，為[0，1]

3） 建立Bellman遞推方程

在（3）中，對于一個隨機的MDP，其轉移方程為，轉移頻率為。當狀態轉移頻率，沒有辦法準確得知時，實際操作中經常使用“強化學習”法，去對問題進行求解。用這種方法求最優策略是非常高效且準確的。

4） 以上步驟求解出最優策略。

3 馬爾可夫求解

3.1 值迭代算法

值迭代算法是一個近似算法。為求解最優解，常采用值迭代算法，隨著迭代過程進行，值迭代算法求得的值，將逐漸逼近最優解。算法如下：

算法1：值迭代算法

1） n=0，是初始值；endprint

2） 依據迭代式，求出值迭代算法過程中第n次時，值函數V和策略π；

3） 重復2。

不難證明，算法1在時，收斂于最優值函數，另外還能估計出每一次迭代時的最優解的區間：

當此條件成立時，不再運行算法算法。

3.2 策略迭代計算

使用策略迭代算法，為的是獲得最優解，即，為集合內所有元素的個數。策略迭代算法如算法2所示。

算法2：策略迭代算法

1） n=0，給定初始策略；

2） 求解；

3） 確定，且滿足

4） if，算法終止，設最優策略為，else，轉步驟2。

算法2中，先確定一個初始策略，然后根據求解出值函數，且根據所求得的值函數，改變策略，對比策略，如果結果相等，那么這個就是最優策略，不再進行算法計算。

3.3 近似求解計算

前文中提到，在實際計算機系統中資源種類和數量都非常龐大，使得建立的MDP模型不能利用精確算法去求解，原因包含兩點：①在算法處理中，每個狀態下的值函數都需要存儲，根據現有的技術，當狀態數較多時，無法提供足夠的空間去存儲這些子函數；②進行迭代過程時，所有的狀態都要帶人計算值函數，這就導致迭代的時間過長，從而使算法收斂速度變慢。為解決上述問題，研究者只能使用出MDP的近似求解算法，解出次優解。

4 隨機博弈網的應用

MDP、MDPN以及MDWN模型通常是，用來描述系統內只存在一個決策者的系統，即具有集中式控制設施系統。實際應用時，系統當中，一般會有多個決策者，此時一般的模型沒有辦法去處理相關問題，如果以某一個決策者，針對他的角度去分別建立模型，雖然可以建立模型求出最優解，但是不能體現出決策者們之間的聯系。動態隨機博弈可處理含有多個決策者的系統，并能夠體現出決策者們之間的關系，可以將它看做是馬爾可夫決策過程的一個擴展。決策者們之間的關系有很多，包括：①合作關系，即將所有決策者看作為一個整體，所關心的是總收益，對系統的細粒度，建立模型起到一定的幫助，還能簡化求解。②競爭關系，簡單地說就是每個決策者只希望自己的收益可以最大化。

5 總結

本文計算機系統與計算機網絡中的動態優化及其應用進行了概述。對比與靜態優化理論，動態優化能夠對系統的時變性進行精確地刻畫。文中依據馬爾可夫決策過程深入的研究討論了計算機系統與計算機網絡中的建模、求解方法和應用實例。

參考文獻：

[1] Murugesan S，Sch niter P，Shroff N B.Multiuser scheduling in a Markov-modeled downlink using randomly delayed ARQ feedback.IEEE Transactions on Information Theory，2012，58（2）：1025-1042.

[2] ZHAO Q ET Al.Decentralized cognitive MAC for opportunistic spectrum access in Ad HOC networks ：A POMDP frame-work.IEEE Journal on Selected Areas in Communications，2007，25（3）：589-600.

[3] 浦江，焦炳連.基于Moodle的計算機網絡課程教學平臺的構建與應用[J].徐州工程學院學報：自然科學版，2011（4）：39-42.

[4] Choi Kae Won.Adaptive sensing technique to maximize spectrum utilization in cognitive radio.IEEE Transactions on Vehicular Technology，2010，59（2）：992-998.

[5] 沈進中.對模糊推理算法的一點思考[J].徐州工程學院學報：自然科學版，2016（03）：55-57，81.endprint