基于VCG 機制的動態頻譜分配算法

劉覺夫，朱丙虎，王華鋒

（華東交通大學 信息工程學院，江西 南昌330013）

0 引 言

認知無線網絡［1］頻譜共享分為兩種方式：Underlay頻譜共享和Overlay頻譜共享［2］。由于認知用戶具有自私、理性的特性，在動態頻譜分配過程中，認知用戶頻譜選擇策略時總是以最大化自己的收益為目的，導致頻譜資源過度占用。

為了解決上述問題，提升無線網絡性能，眾多學者和專家使用博弈論方法對動態頻譜分配問題進行了研究［3］。其中，VCG （vickrey－clarke－groves）機制是有效的，激勵相容的，并且還是個人理性的［4］；Kelly－VCG 機制可以保證用戶之間分配資源的公平性［5］；文獻 ［6］提出了基于VCG 機制的合作博弈模型，用于解決Overlay頻譜共享技術下頻譜分配問題；文獻 ［7］提出一種基于VCG 的非合作博弈模型，用于解決Underlay頻譜共享技術下頻譜分配問題，但其效用函數較為復雜，而且沒有給出頻譜分配算法的具體流程。

本文針對Underlay 頻譜共享方式下動態頻譜分配問題，提出了一種分布式動態頻譜分配算法，最大化網絡系統效用，同時保證用戶的公平性。首先，將頻譜分配問題建立成一種非合作博弈模型，并設計其效用函數，然后運用VCG 機制設計收益函數，并提出一種動態頻譜分配算法，在滿足主用戶的數據傳輸速率需求和誤碼率限制的條件下，最大化網絡系統吞吐量，同時保證認知用戶的公平性。

1 系統模型

考慮如下場景：系統中存在N 個認知用戶傳輸進程ST ，M 個主用戶傳輸進程PT ，C個可用信道和一個公共控制信道。每個傳輸進程都有一個發射端，一個接收端。網絡結構如圖1所示。所有用戶都可以在公共信令信道上廣播和接收信息。假定每個主用戶傳輸進程占用一個可用信道，認知用戶在對主用戶的傳輸質量不產生干擾的情況下以Underlay方式共享可用信道。不妨假定所有的主用戶、認知用戶均能夠自適應調制，擁有固定的誤碼率。

圖1 網絡結構

對于認知用戶傳輸進程STn，n ∈［1，N］，信道c，c∈［1，C］有

對于STn，n∈［1，N］，設計效用函數un，表示認知用戶的效用。在本文中，認知用戶的效用是其數據傳輸速率。由于數據傳輸速率取決于選擇的信道，那么效用函數un取決于xn，c。

系統中所有用戶的效用之和為

式中：X——xn，c組成的矩陣。

可以將該問題建立成一個非合作博弈模型，其中ST 是參與者，策略為可用信道的選擇及其在所選信道上的傳輸功率。對于每個信道，ST 的傳輸功率各不相同。那么，就要求每一個參與者選擇自己的策略最大化自己的效用同時最大化網絡的吞吐量。本文采用VCG 機制解決該問題，其詳細介紹見第3節。

2 效用函數設計

主用戶、認知用戶均能夠自適應調制，那么對于QAM（quadrature amplitude modulation）［8］，單輸入單輸出高斯信道的誤碼率BER 可通過式 （3）近似表示

式中：kn，c——該調制方式下的頻譜利用率，γn，c——STn占用信道c 時的信干噪比 （SINR）。STn的頻譜利用率可以表示為

其中，BERtarn表示STn誤碼率的上限。SINR 對于主用戶和認知用戶都至關重要，文獻 ［9］給出了計算方法如下

其中，n∈［1，N］，c∈［1，C］，m ∈［1，M］，ppt和pst分別對應PT 和ST 的發射功率，Gptmm′c和Gstnn′c分別對應PT 和ST 在信道c 上的增益。

本文中，只考慮簡單信道模型，即信道增益僅與距離有關

不失一般性，如果主用戶傳輸進程的數目等于信道的數目 （M ＝C），不妨假定每個主用戶使用一個固定信道。如果M ＜C，則假定信道分成兩部分：一部分被C 個PT固定占用，另一部分 （M－C 個信道）未被占用。那么可得

因此，STn占用信道c 的香農容量為

式中：Bc——信道c的頻譜帶寬。

不失一般性，設每個信道的帶寬相同，那么STn的效用函數為

3 基于VCG 機制的動態頻譜分配

3.1 動態頻譜分配模型

在動態頻譜分配過程中，每個參與者都是單獨參與博弈，總是以最大化自己的收益為目的。那么就要求為每個參與者制定合理的策略最大化自身收益同時最大化網絡整體效用。本文采用VCG 機制解決該問題，VCG 機制是有效的，激勵相容的，并且是個人理性的。這就意味著采用VCG 機制能夠最大化系統效用；在VCG 機制中說真話是一個弱占優策略；個人理性指的是每個知道自己估價的局中人都愿意參與這個VCG 機制。本文中，應用VCG 機制旨在：①針對認知用戶的動態頻譜分配問題，做公平可靠的社會決策；②計算每個認知用戶的轉移支付τn。

轉移支付表示STn占用信道傳輸對其他認知用戶所造成影響的補償。VCG 機制使用每個用戶遞交的效用函數來決策。在本文中，每個認知用戶使用第2節定義的效用函數。社會決策是為了最大化所有認知用戶的效用之和即最大化網絡吞吐量。

網絡系統中的約束條件如下所示：

（1）干擾溫度限制；

（2）滿足認知用戶的速率需求；

（3）認知用戶只能選擇一個信道；

（4）發射功率限制在一定范圍內。

該系統的頻譜分配可以由下面的最優化問題來表示

認知用戶的功率取決于主用戶的傳輸功率。針對每個PTm滿足其速率需求，保證其誤碼率小于其誤碼率上限，則在其占用的信道上允許的最大干擾可以表示為

那么，認知用戶的發射功率滿足

該模型給出了認知用戶在可用信道上的頻譜分配方案，使得認知用戶使用頻譜時不對主用戶傳輸產生影響，最大化系統整體效用。

考慮認知用戶異步的做決策，定義xoptn為STn的最優策略。定義x－n＝｛x1，…，xn－1，xn＋1，…，xN｝，xi∈［1，C］∪｛0｝，且i≠n。若STn沒有分配到頻譜，則xoptn＝0。則轉移支付的計算方法如下

轉移支付表示STn參與頻譜分配時對其他用戶造成影響的補償。其中，前一項表示當STn參加博弈達到最優分配時，其他用戶的效用之和。后一項表示，STn不參與博弈其他用戶達到最優分配時的效用之和。

由于τn≤0，可以定義STn的收益函數如下

當每個認知用戶都如實報告自己的需求，則收益函數等于效用函數即vn＝un。那么，對于認知用戶在博弈中的占優策略是報告自己真實需求。每個次級用戶都盡力減少轉移支付的值。理想情況下，τn＝0意味著STn不對其他認知用戶的頻譜分配收益產生任何影響。因此，可以得出結論STn占優策略是如實報告自己的需求。

綜上所述，當每個認知用戶報告真實的傳輸速率需求，最小化轉移支付，則系統可以得到最優解即達到納什均衡，并且是帕累托最優的。

3.2 信令的設計

在上述認知無線網絡場景中，沒有中心控制節點的存在，在認知用戶迭代地調整選擇信道和功率的策略的過程中，認知用戶之間必須采用信令來傳遞決策所需的各種參數。本文參考文獻 ［10］設計了信令握手協議，設定公共信令信道，并定義START，START ＿CK 和ACK ＿START＿CK 這3種信令消息。

START 信令包含：認知用戶在其可用信道上對其他認知用戶的增益及對主用戶的增益 （由信道狀態表和記錄的增益矩陣可得），及其下一階段通信需求 （主要是數據傳輸速率和最大誤碼率），及其發射功率限制。START＿CK 信令消息包含：數據傳輸進程的接收端所選定的信道，及所需的發射功率。ACK ＿START ＿CK 信令消息包含確認信息。

每個認知用戶都會維護用戶增益矩陣、用戶發射功率向量和信道狀態表 （CST），記錄待選信道上的使用情況。

3.3 算法設計

實用計算納什均衡的方法是序貫博弈，其中每一個參與者依次選擇最大化自身效用的策略而其他參與者的策略不變［11，12］。當設計了效用函數、收益函數等，設計認知用戶動態策略調整規則成為動態頻譜分配的關鍵。設計算法流程如下：

4 實驗仿真

針對基于VCG 的動態頻譜分配算法，本文在matlab7.6環境下，進行實驗仿真。認知無線網絡場景為：在500m×400m 的范圍內，隨機分布8個認知用戶傳輸進程，4個主用戶傳輸進程，可用信道數為4個。認知無線網絡具體分布如圖2所示。不失一般性，假定所有用戶的最大誤碼率相同即BER ＝10－4，背景噪聲功率n0＝－3dB 。所有主用戶的傳輸速率需求為0.4bit/s/hz，認知用戶的傳輸速率需求為0.15bit/s/hz。認知用戶的最大發射功率為20dB，所有主用戶使用同樣的發射功率為30dB。

圖2 認知無線網絡分布

4.1 收斂性分析

圖3為基于VCG 的動態頻譜分配算法的系統整體效用的收斂情況。橫坐標表示迭代次數，縱坐標表示網絡系統的效用。可以看出，在執行了約40個算法周期后，系統的吞吐量不再改變，達到納什均衡狀態。

圖3 系統效用收斂

圖4為基于VCG 的動態頻譜分配算法中認知用戶策略的收斂情況。橫坐標表示迭代次數，縱坐標表示策略即信道的編號。可以看出，在執行了約40個算法周期后，所有認知用戶的策略不再改變，整個系統達到納什均衡狀態，驗證了算法的收斂性。

圖4 認知用戶策略收斂

圖5為基于VCG 的動態頻譜分配算法中每個認知用戶的效用收斂情況。橫坐標表示迭代次數，縱坐標表示認知用戶的效用。可以看出，在執行了約40個算法周期后，每個用戶的效用不再改變，整個系統達到納什均衡狀態，驗證了算法的收斂性。

圖6為基于VCG 的動態頻譜分配算法中信道的效用收斂情況。橫坐標表示迭代次數，縱坐標表示每個信道的效用。可以看出，在執行了約40個算法周期后，所有信道的效用不再改變，整個系統達到納什均衡狀態，驗證了算法的收斂性。

圖5 認知用戶效用收斂

圖6 信道效用收斂

4.2 公平性分析

為了對認知無線網絡中頻譜資源分配的公平性進行量化，本文采用了Jain公平系數和Gini公平系數［13］，其具體定義如下

圖7 為基于VCG 的動態頻譜分配算法中認知用戶的Jain公平系數和Gini公平系數的收斂情況。橫坐標表示迭代次數，縱坐標表示公平系數。可以看出，在執行了約40個算法周期后，公平系數不再改變，系統達到納什均衡。Jain公平系數達到95%以上，Gini公平系數達到20%以下，可以驗證該算法具有較好的公平性。

5 結束語

圖7 系統公平系數收斂

本文針對在Underlay頻譜共享方式下的認知無線網絡動態頻譜分配問題，提出了一種分布式動態頻譜分配算法，最大化認知無線網絡的吞吐量，同時保證公平性。在滿足主用戶的服務質量 （QoS）的前提下，建立了一種非合作博弈模型，并設計效用函數，在借鑒VCG 機制的基礎上，設計相應的收益函數。實驗仿真結果表明，在執行了約40個算法周期后，系統吞吐量、用戶的策略、用戶的效用、信道的效用不再改變，達到納什均衡，驗證算法的收斂性。引入Jain公平系數和Gini公平系數衡量該算法的公平性，實驗結果表明，Jain公平系數到95%以上，Gini公平系數達到20%以下，可以驗證該頻譜分配算法具有良好的公平性。

［1］Badoi C I，Prasad N，Croitoru V，et al.5Gbased on cognitive radio ［J］.Wireless Personal Communications，2011，57 （3）：441－464.

［2］Bansal G，Hossain M J，Bhargava V K，et al.Subcarrier and power allocation for OFDMA－based cognitive radio systems with joint overlay and underlay spectrum access mechanism ［J］.IEEE Transactions on Vehicular Technology，2013，62 （3）：1111－1122.

［3］Ni Qiufen，Zhu Rongbo，Wu Zhenguo，et al.Spectrum allocation based on game theory in cognitive radio networks ［J］.Journal of Networks，2013，8 （3）：712－722.

［4］ZHAO Yaohua，PU Yongjian.Game theory and economic modeling ［M］.Beijing：China Renmin University Press，2010：312－340 （in Chinese）.［趙耀華，蒲勇建.博弈論與經濟模型 ［M］.北京：中國人民大學出版社，2010：312－340.］

［5］Jain R.Network market design part I：Bandwidth markets［J］.Communications Magazine，IEEE，2012，50 （11）：78－83.

［6］Rajasekharan J，Eriksson J，Koivunen V.Cooperative gametheoretic approach to spectrum sharing in cognitive radios［J］.arXiv Preprint arXiv，2011：1112.1520.

［7］El Ferkouss O，Ajib W.Game theory based resource allocation for cognitive radio networks ［C］//Global Communications Conference.IEEE，2012：1174－1179.

［8］Xie R，Yu F R，Ji H.Dynamic resource allocation for heterogeneous services in cognitive radio networks with imperfect channel sensing ［J］.IEEE Transactions on Vehicular Technology，2012，61 （2）：770－780.

［9］Attar A，Nakhai M R，Aghvami A H.Cognitive radio game for secondary spectrum access problem ［J］.IEEE Transactions on Wireless Communications，2009，8 （4）：2121－2131.

［10］LI Xiaolin，LIU Haitao.Spectrum allocation algorithm of cognitive radio based on supermodel game ［J］.Journal of Chongqing University of Posts and Telecommunications（Natural Science Edition），2010 （2）：151－155 （in Chinese）.［李校林，柳海濤.基于超模博弈的認知無線電頻譜分配算法 ［J］.重慶郵電大學學報 （自然科學版），2010 （2）：151－155.］

［11］SONG Zhiqun，LIU Yutao，WANG Jingning.Cognitive radio technology and its applications ［M］.Beijing：National Defense Industry Press，2012：82－120 （in Chinese）. ［宋志群，劉玉濤，王荊寧.認知無線電技術及其應用 ［M］.北京：機械工業出版社，2012：82－120.］

［12］YANG Guang，JIANG Junmin，SHI Yuanying.Cognitive radio spectrum allocation based on potential game ［J］.Modern Electronics Technique，2011 （13）：41－45 （in Chinese）.［楊光，蔣軍敏，施苑英.基于潛在博弈的認知無線電頻譜分配研究 ［J］.現代電子技術，2011 （13）：41－45.］

［13］Shi H，Prasad R V，Onur E，et al.Fairness in wireless networks：Issues，measures and challenges ［J］.Communications Surveys ＆Tutorials，IEEE，2014，16 （1）：5－24.