基于合作博弈的CPS通信資源分配算法

摘 要： 為了提高信息物理融合系統的通信速率，同時保證各用戶的QoS需求，提出了一種基于合作博弈的CPS通信資源分配算法。將CPS中OFDMA網絡下行鏈路的資源分配過程建模為多用戶間的合作博弈，通過求解納什議價解，實現用戶間的Pareto最優性。仿真結果表明，該算法在系統速率最大化和用戶公平性上獲得了很好的折中，與最大化系統速率算法相比更具有公平性，與最大化最小公平性算法相比速率提高了34%，在一定程度上提高了CPS通信網絡的性能。

關鍵詞： 信息物理融合系統； 合作博弈； 正交頻分復用多址； 資源分配

中圖分類號： TN929.5?34 文獻標識碼： A 文章編號： 1004?373X（2013）20?0020?04

0 引 言

信息物理融合系統（Cyber?Physical Systems，CPS）[1?2]是綜合計算、網絡和物理環境的多維復雜系統，通過3C（Computation，Communication，Control）技術的有機融合與深度協作，實現大型工程系統的實時感知、動態控制和信息服務。正如互聯網改變了人與人之間的溝通方式，CPS將改變大家與周圍物質世界的作用形式。目前，對CPS的研究已經在世界范圍內展開，對其研究主要集中在電力、交通、農業、醫療、制造業、能源、國防、航天和建筑等重要領域[3]。隨著對CPS研究的進行，產生了許多技術難題，這些難題需要來自不同領域的研究者和教育者共同努力解決。

寬帶無線通信系統的現有標準和未來發展趨勢都在朝著基于正交頻分多址（Orthogonal Frequency Division Multiple Access，OFDMA）[4]的資源分配策略方向前進。OFDMA技術也毫無疑問的成為CPS無線通信的關鍵技術。OFMDA系統中，用戶獲得下行鏈路的分集增益的前提是，由基站根據相應的信道條件進行資源（子載波和功率）分配。在CPS無線通信中，有效的OFDMA資源分配算法應該以平衡系統速率最大化和用戶公平性（以最低業務數據速率作為公平性的衡量指標）為目標。文獻[5]針對CPS通信提出了一些新的構思模式和方法，并進行了相應的研究。文獻[6]將貪婪思想引入到系統的子載波分配上，提出了一種能保證系統吞吐量的算法，文獻[7] 通過對迭代注水算法的分析，提出了一種功率分配的新算法，兩種算法都能保證系統吞吐量，卻都損失了公平性。文獻[8]采取權重比例公平性準則，在使各個用戶獲取與自身權重成比例的數據速率的同時，保證系統速率最大化。而文獻[9]采用最大化最小公平性算法，這種情況下，網絡中的所有用戶得到了相同的數據速率，滿足了用戶的公平性。然而，這種方法無法對用戶進行服務質量（Quality of Service，QoS）區分，同時，以系統中最低的用戶速率作為標準，降低了通信資源的利用率。

針對以上問題，筆者利用合作博弈構造系統模型，結合已知功率的動態子載波分配 （Dynamic Sub?carrier Allocation，DSA）算法和已知子載波的自適應功率分配（Adaptive Power Allocation，APA）算法，提出了一種基于合作博弈的CPS通信資源分配算法。通過將本文算法分別與最大化系統速率（max?rate）和最大化最小（max?min）公平性算法的比較，說明了該合作博弈算法有效的平衡了系統速率最大化和用戶公平性，提高了OFDMA網絡下行鏈路的資源利用率，在一定程度上提高了CPS通信網絡的性能。

1 系統模型

在CPS中，以單小區OFDMA系統為模型，假設在其下行鏈路中基站需要將M個子載波分配給N個接入該站的用戶。基站的發送功率為Ptot ，每個用戶的數據可以在多個子載波上傳輸，但是每個子載波只能同時被一個用戶使用。假設系統信道呈頻率選擇性衰落，帶寬為B，系統任意子載波的加性高斯白噪聲表示為[σ2=N0BM。]其中N0表示噪聲功率譜密度。如果任意用戶n（1≤n≤N）在子載波m（1≤m≤M）上的信道增益表示為gn，m ，使用未經信道編碼的多電平正交幅度調制（M?QAM），則用戶n在子載波m上加載的比特數rn，m和發送功率pn，m具有如下關系：

2 合作博弈建模

在CPS無線通信中，OFDMA系統的下行鏈路資源競爭是通過基站協調處理的。基站在滿足用戶的QoS需求（最小速率）的同時要實現系統速率的最大化，而合作博弈算法可以有效地平衡用戶公平性和系統速率的最大化。使用該算法模型進行OFDMA的資源分配，主要是為了求解該博弈的納什議價解（NBS）。NBS具有帕累托最優性（或稱為廣義比例公平性），在其他用戶效用不降低的前提下，使得系統中所有用戶的效用只能通過NBS的資源分配方式獲得提高。

在發送功率一定的情況下，定義G為OFDMA下行鏈路子載波分配的博弈模型，定義N個分布式用戶為博弈的參與者，定義用戶n可獲取的數據速率Rn=Rn（Xn）為它的效用，其中集合Xn ={Qn，m，Pn，m}表示用戶n被分配的子載波和功率集合。[Rminn]表示滿足用戶n的QoS需求的最小數據速率，即用戶n的初始效用。根據納什議價解的存在性與惟一性定理，模型G可建模為由式（3）或式（4）所表述的最優化問題[10]：

采用式（4）作為博弈模型G的優化目標函數，式中Q=[qi，j]N×M為系統的子載波分配矩陣，P=[pi，j]N×M為系統的功率分配矩陣。用戶n在博弈中獲得的凈效用表示為[fnRn=lnRn-Rminn]，博弈的結果應滿足用戶的QoS需求，使其獲得非負的凈效用：fn（Rn）≥0，即：

[Rn≥Rminn+1，?n] （8）

而且fn（Rn）在[Rn∈Rminn+1，+∞]上是連續凸函數。在符合式（8）的情況下，上述問題可最終歸結為非線性約束{0，1}組合優化問題[11]。由于過高的計算復雜度會給基站產生較大的計算負擔，所以需要設計復雜度相對較低的納什議價解求解算法。

根據文獻[12]的解決方法，將求解問題式（4）～式（7）最優值的方法依次分解為如下兩個方法：已知功率的動態子載波分配（DSA）算法和已知子載波的自適應功率分配（APA）算法。

并利用合理的近似處理，減少了 DSA 和 APA算法中的約束參數，得到了式（4）～式（7）的低復雜度近似解的求解方法。

2.1 已知功率的動態子載波分配算法

令每個子載波上分配相同的功率[PtotN]，即用戶功率分配矩陣P已知。

則式（4）～式（7）的優化問題可以簡化為：

由上述約束條件可知，簡化后的問題是一個非線性約束的{0，1}優化問題。用已知功率的DSA算法求解該問題。基本思想是給每個用戶分別分配一個最優的子載波。為減小基站的計算負荷，提高系統的實時性，實際系統中主要考慮用戶在一段時間間隔Tw（Tw>>Ts，Ts為資源分配周期）內的平均速率。算法步驟如下：

步驟1：初始化。在每個子載波上分配等分功率[PtotN]，以滿足用戶QoS的最小數據速率需求。

步驟2：求解目標函數（式（9）），得到瞬時速率下的目標函數全局最優解Q*和子載波分配矩陣Q，以及最優子載波分配算法：

[nm=argmaxl≤n≤Nrn，mRn-Rminn] （12）

式中[nm]表示子載波m分配給用戶[n]。

步驟3：根據用戶n在時刻t的平均速率：

[Rnt=1-ρwRnt-1+ρwRnt] （13）

式中：Rn[t]為瞬時速率；[ρ=TsTw]，化簡目標函數并求解其平均速率動態子載波分配算法：

[nm，t=argmaxl≤n≤Nρwrn，mtRnt-1-Rminn] （14）

式中：rn，m[t]表示t時刻用戶n在子載波m上的瞬時速率；[nm，t]表示在t時刻將子載波m分配給用戶[n]。該算法的計算復雜度為O（KM）。

2.2 已知子載波的自適應功率分配算法

利用DSA算法所求得的子載波分配矩陣Q，式（4）～式（7）可以進一步等效為：

[maxPn=1NlnRn-Rminn] （15）

約束條件：

[n=1Nm=1Npn，m=ptot] （16）

當滿足式（8）時，目標函數式（15）在[Rn∈Rminn+1，+∞]上是連續凸函數，該問題可歸結為線性約束的凸優化問題[11]，其拉格朗日函數為：

[L=n=1NlnRn-Rminn-λn=1Nm=1Mpn，m-Ptot] （18）

式中λ是Lagrange乘子，λ>0，該問題的最優解應滿足：

[?L?pn，m]=0，則最優解為：

[pn，m=1Rn-Rminn BλMln2-1Hn，m] （19）

與最大速率頻域注水定理[13]相比，式（19）可以看作是一種廣義公平性的功率注水定理。

由于實際通信系統中各個子載波所加載的比特數是離散值，所以不符合注水定理加載到各個子載波上的比特數都必須是連續值的要求。離散比特的加載即自適應功率的分配過程，可以通過貪婪算法實現[12]。

由式（1）可得：

[pn，m=2rn，m-1Hn，m] （20）

令Δrn，m是任意用戶n在同一子載波上相鄰兩個調制方式下的可傳輸比特數之差，則傳輸Δrn，m所需的功率增量為：

[Δpn，m=2rn，m+Δrn，m-1Hn，m-2rn，m-1Hn，m=2rn，m+Δrn，m-2rn，mHn，m] （21）

進而產生的系統增量效用為：

[ΔfnRn=fnRn+BMΔrn，m-fnRn] （22）

式中[fnRn=lnRn-Rminn]為最大化整體效用函數。

令[Δfn=ΔfnRnΔpn，m]，則在每次比特加載時，功率分配算法可表示為：

[nm=arg maxn∈NΔfn] （23）

式中：[nm]表示功率增量[Δpn，m]分配給用戶[n]的第m個子載波。算法執行循環迭代，直至將功率Ptot分配完，即Pcur≥Ptot，Pcur表示當前已分配的功率。該算法的復雜度為O（D?M?log2 M），其中D表示迭代次數。

3 算法的仿真與分析

將本文提出的合作博弈算法在兩種不同的仿真條件下進行仿真，并分別與最大化系統速率（max?rate）和最大化最小（max?min）公平性算法進行仿真比較和分析，突出合作博弈算法在系統速率和用戶公平性上的優勢。仿真中采用CPS無線通信系統的單小區OFDMA系統框架，信道模型為六徑瑞利衰落信道，要求最小用戶數據速率為100 Kb/s系統帶寬B=1 MHz，子載波數N=64，噪聲方差σ2=0，系統用戶誤比特率BER=10-3。

3.1 仿真與分析一

在固定用戶數量的情況下（本仿真中只設置兩個用戶），隨著某一用戶的移動，即與基站距離的變化，分別使用本文和上述兩種方法測試各個用戶速率的變化，進而分別分析三種方法的公平性。

為了更好地對仿真進行分析，仿真中只設置了兩個用戶。用戶甲、乙與基站的距離分別設置如下：L1=100，L2={[x10]≤x≤200，x∈R }（單位為m）。即用戶甲在距離基站100 m的位置固定不動，用戶乙在規定范圍內移動。仿真結果圖1和圖2所示。

由圖1可知，隨著L2的逐步增加，最大化系統速率算法中甲的速率逐漸減小，乙的速率逐漸增大。而且在五號很接近10 m和200 m的位置，甲乙兩用戶的速率差距很大。說明此種算法趨向于將資源分配給信道條件相對好的用戶，不符合公平性原則。對于最大化最小公平性算法，兩用戶始終具有同等速率，隨著L2的逐步增加，甲乙速率同時減小。但此種算法以最低用戶速率作為公平性標準速率，降低了系統中其他信道條件好的用戶速率，降低了系統資源利用率。而本文提出的合作博弈算法，在用戶乙移動過程中用戶甲的速率基本保持穩定，用戶乙隨著L2的增大速率逐漸減小，而隨著L2的減小速率逐漸增大。說明對于本文算法，系統中各個用戶的性能由自身信道條件決定，在滿足各自最小速率后，系統將剩余資源按照用戶的不同信道條件按比例分配。

由圖2可知，合作博弈算法獲得的系統速率高于最大化最小公平性算法，低于但無限接近最大化系統速率算法獲得的系統速率。所以本文算法有效的平衡了最大系統速率和用戶公平性，獲得了兩者之間的有效折中。

3.2 仿真與分析二

多用戶情況下，隨著用戶數量的逐步增加，分別用以上三種方法對整個系統的數據速率進行仿真測試，仿真結果如圖3所示。并按照文獻[14]的方法分析三種算法的公平性，結果如圖4所示。

由圖3可知，隨著系統用戶數量的增加，三種算法的系統速率都隨之增大，說明了上述算法都可以獲得多用戶分集增益。本文算法獲得的系統速率介于最大化系統速率和最大化最小公平性算法之間，且無限接近于最大化系統速率算法的最大系統速率。

為了驗證三種算法的公平性，按照文獻[14]的方法，定義公平指數為：

式中：n代表系統用戶數；β→1表示系統公平性較高；β=[1n]則表示系統公平性較差。圖4給出了系統中用戶數量分別增加到8，16，32時，三種算法公平指數。

由圖4可知，最大化最小公平性算法獲得了絕對公平性，合作博弈算法的公平性次之，最大化系統速率算法公平性相對最差。由圖3和圖4可知，第二種仿真環境中的仿真結果再一次說明，本文算法能夠很好的在系統速率最大化和用戶的公平性之間取得折中。

4 結 語

筆者將博弈論和OFDMA網絡下行鏈路的多用戶資源分配算法深度融合，提出了一種合作博弈框架下的CPS通信資源分配算法。通過求解其納什議價解，實現了系統間各個用戶的帕累托最優，在滿足所有用戶公平性后，將剩余資源合理的分配給各個用戶，提高了CPS通信系統的速率。仿真結果表明，該合作博弈算法有效的平衡了系統速率最大化和用戶公平性，在一定程度上提高了CPS通信網絡的性能，進而促進了CPS整體性能的提高。

參考文獻

[1] 溫景容，武穆清，宿景芳.信息物理融合系統[J].自動化學報，2012，38（4）：507?517.

[2] 馬斌，李楠楠.基于人工神經元方式構建的信息物理融合系統[J].沈陽建筑大學學報：自然科學版，2012（3）：375?379.

[3] LEE E A. Cyber physical systems： design challenges [C]// 2008 11th IEEE International Symposium on Object Oriented Real?Time Distributed Computing （ISORC）. Orlando， FL： IEEE， 2008： 363?369.

[4] 劉高星，胡瑞，張欣，等. OFDMA上行鏈路系統的頻偏估計算法[J].現代電子技術，2012，35（17）：1?4.

[5] 王長濤，黃寬，付佳新.基于CPS的通信方法的研究[J].科技廣場，2012（9）：94?97.

[6] JANG Jiho， LEE Kwang Bok. Transmit power adaptation for multiuser OFDM systems [J]. IEEE Journal on Selected Areas in Communications， 2003. 21（2）： 171?178.

[7] 李慶玲，康桂華，李佳珉.OFDMA系統中功率分配新算法研究[J].現代電子技術，2008，31（21）：13?15.

[8] SHEN Zu?kang， ANDREWS J G， EVANS B L. Adaptive resource allocation in multiuser OFDM systems with proportional rate constraints [J]. IEEE Transactions on Wireless Communications， 2005， 4（6）： 2726?2737.

[9] RHEE W， CIOFFI J M. Increase in capacity of multi?user OFDM system using dynamic subchannel allocation[C]// Proceedings of 51st IEEE Vehicular Technology Conference. Piscataway， NJ， USA： IEEE， 2000： 1085?1089.

[10] 張國鵬.基于博弈論的無線網絡資源競爭與協作機制研究[D].西安：西安電子科技大學，2009.

[11] 黃平.最優化理論與方法[M].北京：清華大學出版社，2009.

[12] 艾渤，王勁濤，鐘章隊.寬帶無線通信OFDM系統同步技術[M].北京：人民郵電出版社，2011.

[13] YU W， CIOFFI J M. FDMA capacity of Gaussian multiaccess channels with ISI [J]. IEEE Transactions on Communications， 2002， 50（1）： 102?111.

[14] FANG Zu?yuan， BRAHIM B. Design and implementation of a MAC scheme for wireless Ad Hoc networks based on a cooperative game framework [C]// Proceedings of IEEE International Conference on Communications. Piscataway， NJ， USA： IEEE， 2004： 4034?4038.