基于集合競價置換的雙向動態(tài)頻譜分配算法

劉覺夫，胡 靜，楊 將，朱丙虎

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

在無線電通信網(wǎng)絡中，可用的頻譜資源非常有限。目前廣泛采用基于授權的頻譜資源固定分配策略，將無線頻譜劃分成若干個固定寬度的頻譜段，由政府管理部門分配給授權用戶獨占使用［1］，這種方法嚴重制約了頻譜利用率。認知無線電使無線通訊設備具有發(fā)現(xiàn)閑置頻譜資源的能力，并合理的配置資源，從而有效地提高頻譜使用效率，從根本上解決日益增長的無線通信需求與有限的頻譜資源之間的矛盾［2］。

針對動態(tài)頻譜分配問題，國內(nèi)外專家學者對雙向頻譜拍賣模型進行了廣泛研究。文獻［3］中Wang等人分別在統(tǒng)一價格和差異價格的條件下，設計了基于雙向拍賣的市場局部性頻譜拍賣機制，實現(xiàn)了買方和賣方的優(yōu)化組合。文獻［4］中Wu等人對已有的雙向拍賣模型做出了進一步改進，提出了WTA雙向拍賣算法，提高了頻譜利用率并保證了拍賣參與者的真實性。文獻［5］中Yao等人針對競爭者虛假報價的問題，建立了TDSA雙向拍賣模型，保證了拍賣結果的真實性。文獻［6］中Feng等人提出了基于異構頻譜的雙向拍賣機制TAHS，使認知用戶能夠準確的表達其對頻譜的個人偏好，并且很好地解決了干擾圖變化的問題。結合IEEE802.11e中無線局域網(wǎng)中一種提高QoS的算法［7］，文獻［8］中Huang等人針對拍賣雙方不同的買賣需求設計了多用戶的雙向拍賣方案，構造競價相關的認知用戶組并確定拍賣的贏家策略。文獻［9］中Zhou等人提出了能夠滿足所有經(jīng)濟性能的TRUST機制，采用隨機構成買方集合的方式，使在同一集合中的買方共同使用一個頻段，實現(xiàn)了頻譜的空間復用。

雖然以上算法都能夠完成頻譜分配的任務，但其忽視了拍賣參與者的個體理性和拍賣公平性，使拍賣陷入了一味追求收入最大化的誤區(qū)。為滿足認知用戶的個體理性，保證拍賣的公平性，提高拍賣收益和頻譜成交率，本文提出了基于集合競價置換的雙向動態(tài)頻譜分配算法，并對其進行了理論分析和數(shù)值仿真。

1 雙向拍賣模型

雙向拍賣是一種“多對多”的拍賣結構，有多個買方和賣方，符合雙邊市場次級頻譜拍賣的特點。因此，本文采用雙向拍賣模型。

考慮認知無線網(wǎng)絡場景包含1個代理商，m個主用戶P={p1，p2,…，pm} 和n個次用戶S={s1，s2,…，sn}。拍賣過程以密封競價的方式進行，所有的參與者都采用密封的方式向代理商提交報價。由于實際情況中授權頻譜覆蓋率遠遠高于認知用戶，因此主用戶提供的信道能夠被多個互不干擾的認知用戶共享。系統(tǒng)模型如圖1所示。

圖1 雙向拍賣系統(tǒng)模型Fig.1 System model of double auctions

主用戶作為提供頻譜的賣方，認知用戶作為需要頻譜的買方。假設每個賣方一次只提供一個待售信道，每個買方每次只需占用一個信道。賣方的出價與買方的要價分別表示為每個賣方pj向代理商提交一個價格aj，若買方出價低于aj，代理商將不租賃信道。而每個買方si向代理商提交一個價格bi，若賣方要價高于bi，買方將放棄競價。

將賣方的分配矩陣記為X∈{0 ,1}m，若xi=1，則賣方pi贏得拍賣，且從拍賣商處獲得pis。否則pi輸?shù)襞馁u，且pis=0。買方的分配矩陣記為Y={0 ,1}n×m，若yik=1，則買方si贏得賣方pk的頻譜，并從拍賣商處獲得pbi。否則yik=0，且pbi=0。矩陣X與Y需滿足三個條件：①若si,sj∈εh，則yik+yjk≤1；②對任意一個買方si，；③對任意一個賣方pi，當且僅當時，xk=1。第1個條件表示，若兩個買方位于同一個干擾集合，將不會被分配同一個信道。第2個條件表示一個買方最多只會被分配一個信道。第3個條件確保被分配信道的數(shù)量與拍賣贏家的數(shù)量相同。

假設每個賣方在其信道上擁有的成本為cj，每個買方在任意一個信道上所產(chǎn)生的收益為ri，且買方和賣方擁有相同的時間間隔。則賣方和買方的效用函數(shù)分別為

追求最大拍賣商收益Aopt的頻譜分配問題可以用最優(yōu)化模型描述如下

這是單目標的0-1規(guī)劃問題，采用單純形法進行求解。

1.1 買方集合劃分

代理商通過測量認知用戶之間的累計干擾度degree 來獲得買方干擾關系圖，將得到的圖記為Gr，r∈(1,l)。在買方獨立競價的基礎上，代理商采用measurement-calibrated propogation［10］模型，將有強干擾的買方分配在同一個子集中，將無干擾或弱干擾的買方分配在另一個子集中。由于買方之間的無線干擾情況被抽象為一個干擾集，為了提高獨立集合構造能力，采用譜聚類算法［12］解決這個NP難題。將劃分好的集合記為εh，h∈(1,t) ,t≤n。

1.2 雙向拍賣-SBPA算法

將被劃分形成的買方集合看作一個整體出價，在文獻［9］中，定義了最優(yōu)的買方集合出價，如下

但是按照公式（10）計算出的最優(yōu)集合出價，并不滿足個體理性。

假設頻譜分配問題的最優(yōu)化解為A，具有較優(yōu)的β-競爭性［10］滿足，A≥Aopt/β，且能保證個體理性。不妨假定賣方的要價為a={1.9,1.2,0.9,0.5}，買方的出價為b1=0.9，b2=b3=0.7，b4=0.6，b5=0.4，b6=0.2，b7=0.1。其中，b1,b6∈ε1，b2,b4,b5∈ε2，b3∈ε3，b7∈ε4。則由式（10）可得π1*=0.3，π2*=1.2，π3*=0.7，集合ε2的出價π2* 最大，贏得拍賣。顯然，集合ε1中s1的出價為0.9，是三個集合中出價最高的買方，卻還輸?shù)袅伺馁u。不僅違背了拍賣的公平性，而且減少了拍賣收益。

針對該問題，本文提出了SBPA 集合競價算法。在頻譜拍賣過程中，買方除了向代理商提交出價外，還需提供其期望收益ri。

首先，代理商由式（10）計算出每個買方集合的最優(yōu)集合出價πh*。若存在買方期望收益ri大于買方集合中的平均期望收益ri≥R/ ||εh，則集合中小于平均期望收益的買方贏得拍賣，并將這個期望收益作為買方交給代理商的初始出價pbi*。

然后，算法選擇將集合價格為πi* 的集合映射到集合價格更優(yōu)的πj* 集合上，其中πi*＜πj*，且i,j∈(1,t)。算法采用一個隨機的排列置換c(r)={c(1),c(2),c(3),…,c(|bj|)|c(r)≠r}，將不同的集合進行置換。若大于置換前的集合出價，則置換成功，否則置換失敗。在置換失敗的集合中的買方將會被剔除。在置換成功的集合中，每個買方在其所在集合中平均地承擔置換后的集合價格。

在確定贏得拍賣的集合與拍賣雙方的真實出價后，對每個集合中贏得拍賣的買方按照其出價進行排序，并按賣方的真實出價順序為其分配頻譜，得到每個集合中的頻譜分配結果集合winners。考慮到不同圖之間的不連接性，需要將不同集合中的結果合并。合并過程中，每次選取兩個圖，找到每個圖中累計干擾度最小的買方。如果這兩個買方被分配到相同的信道，則將出價低的買方剔除，否則直接合并，得到最終的分配結果。

具體的算法流程如下：

2 實驗仿真

使用Matlab2010軟件平臺進行仿真，仿真結果均由算法重復運行50次并計算其平均值而獲得。參與拍賣的雙方采用均勻分布方案（Uniform），隨機的分配在1 000 m×1 000 m的范圍內(nèi)。若兩個買方之間的距離小于300 m則產(chǎn)生干擾。為了驗證本文提出算法的有效性，將其與TRUST作了比較。仿真參數(shù)設置如下表：

表1 仿真參數(shù)Tab.1 Simulation parameters

2.1 拍賣雙方的成交情況

圖2 成交用戶數(shù)量隨參與用戶數(shù)量的變化關系Fig.2 Changes of the number of winning users along with the number of participants

如圖2，以買方和賣方的成交數(shù)量作為對比。Wseller 表示贏得拍賣的賣方，Wbuyer表示贏得拍賣的買方。從圖中可以看出，不管是TRUST 還是SBPA，隨著參與者的增加，SBPA 算法的平均成交數(shù)量都大于TRUST。因此，SBPA算法能夠顯著地提高拍賣的成交量。

2.2 β-競爭性仿真及分析

為了度量拍賣的效果，本文引入了文獻［12］中β-競爭性拍賣的概念：如果一個拍賣至少達到最優(yōu)拍賣的1β，則這個拍賣是β-競爭性的，即A(a,b)≥Aopt/β。為了方便表示，令1/β=α。

從圖3中可以看出TRUST算法和SBPA算法的β-競爭性都隨著參與者數(shù)量的增加而增加。但SBPA最高可達到最優(yōu)拍賣的1/2，而TRUST 在最優(yōu)情況下都未能達到最優(yōu)拍賣的1/3。因而，SBPA 算法具有較優(yōu)的β-競爭性。

圖3 β-競爭性隨用戶數(shù)量的變化關系Fig.3 β-competitive changes with the number of participants

2.3 拍賣收益仿真

針對拍賣收益，分別采用Uniform與Cluster分布方案進行仿真，收益變化關系如圖4所示。Cluster方案選取中心買方，使其他的買方均勻隨機的分布在距離中心買方（Cluster）100 m的范圍內(nèi)。

圖4 兩種買方分布下拍賣收益隨買方分布情況的變化關系Fig.4 Revenue changes with two buyer distributions

3 結束語

本文基于認知無線網(wǎng)絡，引用雙邊市場模型，利用雙向拍賣理論，提出了基于集合競價置換的雙向動態(tài)頻譜分配算法。為減少算法復雜度，使買方以集合的形式參與競價。在拍賣過程中，由集合競價置換算法計算出買方集合的出價及拍賣雙方的真實出價后，由代理商為買方與賣方的出價進行排序并確定拍賣結果，最終在買方和賣方之間劃分多對一的映射關系。理論分析證明，該算法能夠在充分保證個體理性的基礎上實現(xiàn)動態(tài)頻譜分配。

仿真實驗結果證明，該算法能夠有效地提高拍賣成交率和拍賣收益，且具有較優(yōu)的β-競爭性。在拍賣參與雙方增多的情況下，可獲得更優(yōu)的拍賣結果。

[1] PAWELCZAK P, NOLAN K, DOYLE L, et al.Cognitive radio: Ten years of experimentation and development[J].Communications Magazine,IEEE,2011,49(3):90-100.

[2] WANG B,LIU K J R.Advances in cognitive radio networks:A survey[J].Selected Topics in Signal Processing,IEEE, 2011,5(1):5-23.

[3] WANG W, LI B C, LIANG B.District: Embracing local market in truthful spectrum double auction[C]//Proc of the 8th Annual IEEE Conf on Sensor,Mesh and Ad Hoc Communications and Networks(SECON 2011).Piscataway,NJ:IEEE,2011:521-529

[4] WU G,REN P,ZHANG C.A waiting-time auction based dynamic spectrum allocation algorithm in cognitive radio networks[C]//Global Telecommunications Conference(GLOBECOM 2011),2011 IEEE.IEEE,2011:1-5.

[5] YAO E, LU L, JIANG W.An efficient truthful double spectrum auction design for dynamic spectrum access[C]//Cognitive Radio Oriented Wireless Networks and Communications (CROWNCOM), 2011 Sixth International ICST Conference on.IEEE, 2011:181-185.

[6] FENG X,CHEN Y,ZHANG J,et al.TAHES:Truthful double auction for heterogeneous spectrums[C]//INFOCOM, 2012 Proceedings IEEE.IEEE,2012:3076-3080.

[7] 湯文亮,李健.IEEE802.11e無線局域網(wǎng)中一種提高QoS的算法[J].華東交通大學學報,2008,25(5):63-66.

[8] HUANG H, SUN Y, XING K, et al.Truthful multi-unit double auction for spectrum allocation in wireless communications[J].Wireless Algorithms,Systems,and Applications,2012,75:248-257.

[9] ZHOU X,ZHENG H.TRUST:A general framework for truthful double spectrum auctions[C]//Proc of IEEE Infocom 2009.Piscataway,IEEE,2009:999-1007.

[10] ZHOU X, ZHANG Z, WANG G, et al.Practical conflict graphs for dynamic spectrum distribution[C]//Proceedings of the ACM Sigmetrics international conference on Measurement and modeling of computer systems.ACM,2013:5-16.

[11] CHAUDHURI K,GRAHAM F C,TSIATAS A.Spectral clustering of graphs with general degrees in the extended planted partition model[C]//COLT.2012:35.1-35.23.

[12] CHEN N, GRAVIN N, LU P.Optimal competitive auctions[C]//Proceedings of the 46th Annual ACM Symposium on Theory of Computing.ACM,2014:253-262.