基于單頻段多贏家拍賣的動態頻譜分配

張文柱，王凌云

（西安電子科技大學 綜合業務網理論和關鍵技術國家重點實驗室，陜西 西安 710071）

1 引言

隨著科學技術的不斷進步以及人們對于通信要求的不斷提高，無線通信技術的種類越來越多，使用這些技術進行無線通信的用戶也越來越多，使得無線頻譜日益成為緊缺的資源。傳統的頻譜管理體制限定某一頻段內的頻譜只有該頻段的授權用戶可以使用，造成某些頻段的頻譜利用率很低，存在大量頻譜空洞[1]。認知無線電技術通過實時感知，在不干擾授權用戶正常通信的前提下，允許認知用戶動態接入授權用戶的空閑頻段，有效提高了頻譜利用率，已成為當前無線通信領域的研究熱點[2]。

基于競價拍賣的頻譜分配模型以其較少的信息需求和良好的分配效果被認為是解決認知無線電網絡頻譜分配問題的有效方法[3]。該領域已經產生了一系列研究成果，例如，文獻[4]提出了一個實時頻譜拍賣算法來實現對大規模拍賣的無沖突頻譜分配，有效地提高了拍賣收益和頻譜利用率；文獻[5]運用漸進式博弈的方法，通過觀察價格和QoS的變化，研究了授權用戶與次級用戶的相互影響；文獻[6]提出了一個基于拍賣的頻譜管理策略框架來同時滿足4種拍賣參與者的要求；文獻[7]提出了一個基于拍賣的Q學習算法，用于次級用戶競爭有限的、時變的頻譜機會。

已有的基于競價拍賣的頻譜分配方案在提高頻譜分配效率上取得了較好的成效，但是仍然存在一些缺陷亟待解決。首先，多數文獻沒有重視頻譜拍賣與傳統的物品拍賣之間的區別。在物品拍賣中，一件物品最終只能被一個贏家所獲得；然而頻譜資源是干擾受限的，而不是數量受限的，也就是說，如果多個次級用戶在地理位置上相距足夠遠，那么單個頻段的頻譜就可以同時被多個贏家所共同使用。其次，盡管少數文獻，如文獻[8]認識到了干擾受限的問題，但該文獻所提出的算法復雜度偏高，可行性低，并且沒有考慮到次級用戶的自私性。

針對上述問題，作者提出了一種基于單頻段多贏家拍賣的動態頻譜分配算法，區別于傳統的單頻段單贏家拍賣算法，該算法使得相互之間無干擾或干擾足夠小的多個次級用戶可以同時使用同一信道進行通信。該算法復雜度低，并且能夠獲得較高的拍賣收益以及良好的抗共謀性能。

2 系統模型和問題描述

圖1 認知無線電網絡模型

考慮由一個頻譜經紀人和N個次級用戶組成的認知無線電網絡，如圖1所示。其中次級用戶可以是任何裝備有認知無線電技術的通信設備。授權用戶在獲得頻譜使用權時繳納了相應的費用，因此頻譜的使用具有一定的成本，授權用戶希望在成本價格之上以盡可能高的價格出租自己的空閑頻段。而次級用戶希望在自己的預期收益之下以盡可能低的價格租用空閑頻段來滿足自己的通信要求。

假設頻譜經紀人現有M個單位的互不重疊且不可再分的空閑信道可以用來拍賣，且這些信道的性質（帶寬、調制方式等）是完全相同的，即次級用戶只關心有沒有獲得信道而不會關心獲得的是哪一條信道。同時，假設每個次級用戶在一個拍賣周期內只需使用一個空閑信道。為簡便起見，先考慮M=1的情況，在每個拍賣周期T開始時，N個次級用戶通過認知能力得到其對于頻譜的估價v=[v1, v2,…,vN]，其中，vi為第i個次級用戶的估價。然后，向頻譜經紀人遞交他們的報價b=[b1, b2,…,bN],bi≤vi，其中bi為第i個次級用戶的報價。頻譜經紀人需要在使系統效用最大化的前提下決定哪些用戶競標成功以及競標成功用戶的實際應付價格，即產生分配向量x=[x1, x2,…,xN],xi∈｛0,1｝和價格向量p=[p1, p2,…,pN],pi≥pc。其中，xi=1表示第i個次級用戶競標成功，反之，則失敗；pi為第i個次級用戶的實際應付價格，pc為每段頻譜的成本價格或保留價格，系統效用定義為

系統效用表示一次拍賣過程中整個拍賣模型獲得的總收益。系統效用越高，代表拍賣算法的頻譜分配效率越高。

為了表示次級用戶間的干擾情況，構造一個N×N的干擾矩陣C，Cij∈｛0,1｝，Cij=1表示第i個次級用戶和第j個次級用戶相互之間存在干擾，不能同時使用同一信道，反之，Cij=0則表示相互之間無干擾。

追求系統效用最大化的拍賣算法通過如下目標函數決定分配向量x：

當M＞1時，定義系統效用為

此時拍賣算法有如下目標函數：

其中，xm是第m個信道的分配向量，=1表示第i個次級用戶競標第m個信道成功，反之，則表示競標失敗。

式(4)問題的求解是一個NP-hard問題，用枚舉法求解理論上能得到最優解。鑒于枚舉法的計算復雜度是指數級的，當問題規模較大時，會因計算量過大而無法實現。因此，需要尋找一種快速簡單的贏家判決算法。

另一方面，要求解式(4)的值，需要知道每個次級用戶對頻譜的真實估價vi，即令bi=vi。但是網絡中的次級用戶是自私的和理性的[9]，每個用戶都設法使自己的利益最大化，如果可以獲得更高的利益，它們會選擇謊報估價。為了解決這一問題，傳統的單頻段單贏家拍賣模型中常用VCG(vickeryclarke-grove)機制[10]來進行價格判決。假設贏家判決所求得的最優分配向量為x*，那么其所對應的最優系統效用為=Uv(x*)。假設第i個次級用戶競標成功，定義v-i=[v1, v2,…,vi-1,vi+1,…,vN]，那么該次級用戶的實際應付價格為

VCG機制具有占優策略激勵兼容特性，最大限度地激勵次級用戶遞交其真實估價，有效地確保了整個系統的公平性。但是對于本模型來說，VCG機制使得頻譜經紀人的收益相當低，賣家收益過低會產生相當嚴重的轉租共謀[11]，因此作者提出的拍賣算法對VCG機制進行了改進。

3 單頻段多贏家拍賣算法

3.1 贏家判決階段

貪婪算法是求解NP-hard問題的一種近似算法，它的優點是計算復雜度低、速度快，但是結果的優度不夠理想。作者首先給出了綜合考慮報價和干擾約束的貪婪準則，然后在原始貪婪算法的基礎之上，增加了多重貪婪策略，通過增大解的搜索空間來彌補原始貪婪算法的不足，提高結果的優度。

一個單頻段多贏家拍賣市場POBMW由一個七元組構成，POBMW={S, F, v, pc,C,Ri, Ai}，其中變量表示含義如下。

1) S={s1, s2,…,sN}是N個次級用戶組成的集合，F={f1,f2,…,fM}是M個待拍賣信道組成的集合。

2) v=[v1, v2,…,vN]是次級用戶的估價向量，pc是單個信道的成本價格。

3) C是干擾矩陣，Ri是第i個次級用戶的干擾用戶集。

4) Ai是第i個次級用戶的可用信道集。初始化時，若vi＜pc，Ai=?；若vi≥pc，Ai=F且所有信道優先級等級設為0。

具體的判決流程如下。

① 頻譜經紀人廣播出租信息，包括信道數目M、單個信道成本價格cp等。

② 次級用戶向頻譜經紀人遞交競價信息，包括估價iv、地理位置或鄰節點等。

③ 頻譜經紀人根據收集到的信息，構造干擾矩陣C，為每個次級用戶分配集合iR和iA，并初始化。

④ 按照式(6)從次級用戶集S中選出一個贏家ks：

為sk分配Ak中優先級最高的信道fm，若存在多個優先級相同的信道，則選擇序號m最小的信道，若Ak=?，則丟棄sk。

⑤ 更新次級用戶集S：S=S-{sk}。

⑥ 更新每個次級用戶si的可用信道集Ai：對比干擾矩陣C，若sk是si的干擾用戶，則將fm從Ai中刪除，若不是，則將Ai中fm的優先級提高一位。

⑦ 返回步驟④，直至S=?。至此，得到貪婪算法的解：X={x1, x2,…,xM}。

⑧ 多重貪婪：從解X的每一個分量xm中隨機選擇r%的次級用戶，連同被丟棄的次級用戶，重新放入集合S中，并將它們上一次競價成功所獲得的信道從各自的可用信道集中刪除，再次應用貪婪算法，即重復步驟④～步驟⑦，得到新的解Y。通過式(3)求得解X與Y所對應的系統效用，若新解Y的系統效用更高，則用新解代替原來的解。

⑨ 重復步驟⑧t次，得到最終優化解。

3.2 價格判決階段

原始的VCG機制依次對每一個競價成功的次級用戶使用式(5)計算其應付價格，這種方法不適用于單個頻段有多個贏家的拍賣模型。為此，作者將同時獲得某一信道使用權的所有次級用戶定義為一個虛擬競價人，此人對信道的估價等于其內部所有次級用戶估價的總和。對每個虛擬競價人使用式(5)求出總的應付價格，再分解到單個次級用戶上，即可求出完整的價格向量。映射到本模型中，設W={sn}為信道f1的贏家集合，即?sn∈W,=1。W就是一個虛擬競價人，其估價，對于信道f1而言，，代入到式(5)可得W的總的應付價格：

因此，序號為m的信道的價格向量mp可用如下方法求得。

①將前m個信道的所有贏家集合從系統中去除，通過一次贏家判決求出一個贏得拍賣的虛擬競價人，根據式(7)，這個虛擬競價人的總估價即為第m個信道的虛擬競價人的總的應付價格。

②根據比例公平準則，通過式(8)求得第m個信道的每個贏家的實際應付價格ip。

4 性能分析

4.1 算法的復雜度

運用枚舉法求式(4)時，由于每個xi都有0、1兩種可能解，需要遍歷2MN種情況，每種情況需要做MN-1次加法運算以計算對應的系統效用，最后需要做2MN次比較以找到最優的分配向量。所以枚舉法總共需要做2MNMN次加法運算，其時間復雜度為Ο(2MNN)。

運用原始貪婪算法求解時，根據步驟④，先要做N次加法運算和N次除法運算得到式(6)中貪婪準則所要比較的值，然后做N-1次比較得到k值，做M次比較為sk分配信道，再由步驟⑦，需要循環求出N個k值，每次循環N的值都減1。所以貪婪算法總共需要做N次除法運算和N( N+1)/2+MN次加法運算，其時間復雜度為Ο(N2)。

運用多重貪婪算法求解時，步驟⑧需要重新求解大約r%×N個k值，循環t次，忽略與M或N無關的常數次運算，可以求得，多重貪婪算法僅比原始貪婪算法多出t×r%×N( r%×N-1)/2+tr%MN次加法運算，其時間復雜度仍為Ο(N2)。

可見，多重貪婪算法的時間復雜度僅略高于原始貪婪算法，但明顯低于枚舉法的時間復雜度，特別是當M和N較大時，該算法能夠節約大量的拍賣交易時間。

4.2 抗共謀性能

本算法在價格判決階段，對于每一個虛擬競價人使用VCG機制計算支出，對于單個次級用戶遵循比例公平準則分配收益，最大限度地激勵虛擬競價人和單個次級用戶均遞交其最高報價，即其真實估價，繼承了VCG機制占優策略激勵兼容特性的同時，避免了直接使用VCG機制時贏家應付價格過低可能會產生的轉租共謀。同時，保留價格的設定抑制了共謀團體的低價策略，可以有效防止圍標共謀的發生[12]。

5 算法仿真

仿真環境設定：在一個100 100×的矩形區域中，隨機分布有一個頻譜經紀人和N個次級用戶。頻譜經紀人擁有5個空閑信道等待拍賣，每個空閑信道的成本價格為15。每個次級用戶的覆蓋半徑均為25，即如果2個次級用戶的距離小于50，則認為它們互相干擾，次級用戶對頻譜的估價均勻分布在[10,30]之間。多重貪婪策略中每次移除50%的次級用戶，重復10次。次級用戶數N從10逐漸遞增到30，在每個次級用戶數下進行100輪次仿真。

圖2比較了當次級用戶數為20時，傳統單頻段單贏家 (OBOW, one-band one-winner) 算法、原始貪婪 (greedy) 算法及作者提出的單頻段多贏家(OBMW, one-band multi-winner)算法3種算法的系統效用，通過50次仿真，模擬了50種網絡拓撲結構。可以看出OBOW算法由于贏家數很少，系統效用相當低；OBMW算法的系統效用均要高于greedy算法，并且不會產生某一種網絡拓撲環境下系統效用特別低的情況，說明經過優化的OBMW算法能更好地適應各種不同的網絡拓撲。

圖2 次級用戶數為20時系統效用的比較

圖3比較了不同次級用戶數情況下3種算法的系統效用。可以看出，當次級用戶數較少時，greedy算法和OBMW算法都能得到最優解，當用戶數逐漸增多，2種算法的差值逐漸增大。實驗結果表明，與greedy算法相比，OBMW算法得到的系統效用平均要高8%～12%。

圖3 不同次級用戶數情況下系統效用的比較

圖4比較了不同次級用戶數情況下3種算法的頻譜分配效率，即實際系統效用與最優值的比值。可以看出，OBMW 算法的分配效率均要高于其他算法，并且分配效率不低于90%。

圖4 不同次級用戶數情況下頻譜分配效率的比較

圖5比較了空閑信道數分別為2、3、4，次級用戶數分別為10、20的簡單網絡環境下OBMW算法的頻譜分配效率。可以看出，空閑信道數越多，算法的頻譜分配效率越高。

圖5 不同空閑信道數情況下頻譜分配效率的比較

圖6比較了不同次級用戶數情況下3種價格判決算法對應的頻譜經紀人的收益。可以看出，如果直接將 VCG機制用于單頻段多贏家拍賣模型中，頻譜經紀人收益將特別小，甚至在很多情況下低于OBOW算法，而OBMW算法則能大幅度地提高賣家收益，滿足拍賣要求。

圖6 頻譜經紀人的收益的比較

圖7 可被轉租的系統效用的比較

圖7比較了不同次級用戶數情況下可被轉租的系統效用占實際系統效用的百分比，其中avg-VCG表示100輪次仿真結果的平均值，max-VCG表示100輪次仿真結果中的最大值。實驗結果表明，如果直接將VCG機制用于單頻段多贏家拍賣模型中，10%～20%的系統效用可能會被轉租，最壞情況下甚至超過50%，而OBMW算法則具有更好的抗共謀性能，平均可轉租率均小于10%。

6 結束語

提出了一種適用于認知無線網絡的基于單頻段多贏家拍賣的動態頻譜分配算法。該算法在原始貪婪算法的基礎上增加了多重貪婪策略，以較低的計算復雜度得到了優化的解；提出了虛擬競價人概念，將VCG機制很好地應用于單頻段多贏家拍賣模型中，提高了賣家的收益，抑制共謀的發生。仿真結果表明，該算法的頻譜分配效率接近最優分配效率，提高了拍賣的經濟收益，有效解決了認知無線網絡中的動態頻譜分配問題。

[1] MITOLA J. Cognitive radio: making software radios more personal[J].IEEE Personal Communications, 1999, 6(4):13-18.

[2] AKYILDIZ I F, LEE W Y, VURAN M C, et al. A survey on spectrum management in cognitive radio networks[J]. IEEE Communications Magazine, 2008,46(4):40-48.

[3] ZHOU X, GANDHI S, SURI S, et al. eBay in the sky: strategy-proof wireless spectrum auctions[A]. Proceedings of the 14th ACM International Conference on Mobile Computing and Networking[C]. New York, USA, 2008. 2-13.

[4] GANDHI S, BURAGOHAIN C, CAO L, et al. A general framework for wireless spectrum auctions[A]. The 2nd IEEE International Symposium on New Frontiers in Dynamic Spectrum Access Networks[C].Dublin, Ireland, 2007. 22-33.

[5] NIYATO D, HOSSAIN E, HAN Z. Dynamics of multiple-seller and multiple-buyer spectrum trading in cognitive radio networks: a game-theoretic modeling approach[J]. IEEE Transactions on Mobile Computing, 2009, 8(8):1009-1022.

[6] CHANG H B, CHEN K C. Auction-based spectrum management of cognitive radio networks[J]. IEEE Transactions on Vehicular Technology, 2010, 59(4):1923-1935.

[7] TENG Y L, ZHANG Y, NIU F. et al. Reinforcement learning based auction algorithm for dynamic spectrum access in cognitive radio networks[A]. 2010 IEEE 72nd Vehicular Technology Conference Fall[C]. Ottawa, Canada, 2010. 1-5.

[8] CHEN L, IELLAMO S, COUPECHOUX M. An auction framework for spectrum allocation with interference constraint in cognitive radio networks[A]. 2010 Proceedings IEEE INFOCOM[C]. San Diego,USA, 2010. 1-9.

[9] HAN Z, ZHENG R, POOR H V. Repeated auctions with bayesian nonparametric learning for spectrum access in cognitive radio networks[J]. IEEE Transactions on Wireless Communications, 2011,10(3):890-900.

[10] 劉志新, 申妍燕, 關新平. 一種基于 VCG 拍賣的分布式網絡資源分配機制[J]. 電子學報, 2010, 38(8):1929-1934.LIU Z X, SHEN Y Y, GUAN X P. A VCG auction based distributed mechanism for network resource allocation[J]. Acta Electronica Sinica,2010, 38(8):1929-1934.

[11] WU Y L, WANG B B, LIU K, et al. A multi-winner cognitive spectrum auction framework with collusion resistant mechanisms[A].DySPAN 2008[C]. Chicago, USA, 2008. 1-9.

[12] HUANG S H, LIU X, DING Z. Optimal sensing-transmission structure for dynamic spectrum access[A]. IEEE INFOCOM 2009[C]. Rio de Janeiro, Brazil, 2009. 2295-2303.