基于博弈論的頻譜動態(tài)管理研究

吳　帆　　　鄭臻哲

(上海交通大學電子信息與電氣工程學院　上?！?00240)

(fwu@cs.sjtu.edu.cn)

?

基于博弈論的頻譜動態(tài)管理研究

吳帆鄭臻哲

(上海交通大學電子信息與電氣工程學院上海200240)

(fwu@cs.sjtu.edu.cn)

Game Theory Based Spectrum Dynamic Management

Wu Fan and Zheng Zhenzhe

(SchoolofElectronic,InformationandElectricalEngineering,ShanghaiJiaoTongUniversity,Shanghai200240)

AbstractWith the growing deployment of wireless communication technologies, radio spectrum is becoming a scarce resource. The current static spectrum management leads to low spectrum utilization in the spatial and temporal dimensions. Auction mechanism is believed to be an effective method among the most effective tools to solve or relieve the problem of radio spectrum shortage. However, designing a practical spectrum auction mechanism has to consider five major challenges: strategic behaviors of rational users, channel heterogeneity, channel spatial reusability, preference diversity and social welfare maximization. In this paper, we give a though literature survey about spectrum auction mechanism design, and point out the disadvantage of the existing works. We also present our recent work in heterogeneous spectrum management. We model the problem of heterogeneous spectrum allocation as a combinatorial auction. By jointly considering the five design challenges, we propose an efficient channel allocation mechanism and a price calculation scheme. We also prove that the proposed mechanism satisfies the strategy-proofness, and achieves approximately efficient social welfare.

Key wordswireless network; channel allocation; combinatorial auction; game theory; resource management

摘要隨著無線通信技術的快速發(fā)展，無線頻譜成為越來越緊缺的網(wǎng)絡資源.現(xiàn)有的靜態(tài)頻譜管理機制導致頻譜資源在空間維度和時間維度上的低利用率.拍賣機制被認為是解決頻譜資源稀缺問題的行之有效的方法.然而，設計高效、實際的頻譜拍賣機制需要考慮5個挑戰(zhàn)：理性用戶自私策略行為、信道異質(zhì)特性、信道空間重用特性、用戶偏好多樣性和社會福利的最大化.對頻譜拍賣機制的研究現(xiàn)狀做了全面的綜述，指出現(xiàn)有工作存在的問題，并提出可行的解決方案；展示了在異質(zhì)頻譜管理中的最新研究成果；將異質(zhì)頻譜的重分配問題建模成組合拍賣模型，結(jié)合5個設計難題提出高效的信道分配機制和定價策略.該機制實現(xiàn)了防策略性和近似社會福利最大化.

關鍵詞無線網(wǎng)絡；信道分配；組合拍賣；博弈論；資源管理

過去的20年見證了無線網(wǎng)絡和移動通信技術的快速發(fā)展，然而有限的頻譜資源成為越來越多的無線應用和服務的發(fā)展瓶頸.頻譜動態(tài)分配是移動互聯(lián)網(wǎng)的基礎技術之一.大多數(shù)的國家都有具體的部門來管理頻譜的使用情況，比如美國的聯(lián)邦通訊委員會(FCC)[1]、中國的無線電管理局(RAB)[2].他們靜態(tài)地將頻譜資源以長期和大范圍的形式分配給大型的無線網(wǎng)絡提供商.這一靜態(tài)分配策略造成本已稀缺的頻譜資源不能得到有效的利用，具體體現(xiàn)在2個方面：1)靜態(tài)頻譜分配沒有充分考慮頻譜需求的空間和時間差異性，造成在很多地區(qū)、很多時間段大塊的頻譜資源長期處于閑置狀態(tài)；2)新興的無線網(wǎng)絡應用由于缺乏足夠的頻譜資源而無法發(fā)揮其應用價值.國際通聯(lián)盟(International Telecommuni-cation Union, ITU)發(fā)布的無線電使用報告中反映了這種低效率的頻譜分配機制.現(xiàn)在頻譜分配面臨著如下2個困境：1)很多頻譜擁有者，又稱為主用戶(primary users)愿意將他們空閑的頻譜資源出租以獲得一定的經(jīng)濟利益;2)新興的無線網(wǎng)絡服務商，又稱為次級用戶(secondary users)希望通過租用頻譜資源來支撐其無線服務.所以，為了有效地利用有限的頻譜資源，頻譜資源動態(tài)二次分配變得尤為重要,新興的認知無線電技術使頻譜資源動態(tài)二次分配成為可能.設計和研究基于市場規(guī)律的頻譜分配機制成為了通信網(wǎng)絡領域亟待解決的問題.開放的頻譜拍賣市場，比如Spectrum Bridge[3]，已經(jīng)興起，這些市場通過對頻譜資源的買、賣、出租等多種形式來進一步提高頻譜資源的利用率.

在頻譜分配博弈中，我們將頻譜資源動態(tài)二次分配問題抽象為市場供求關系，并設計激勵機制實現(xiàn)頻譜分配優(yōu)化.一個有效的頻譜分配激勵機制應該具備2方面的功能：1) 讓頻譜資源所有者愿意將其閑置的頻譜資源提供給頻譜資源需求者，并使頻譜資源所有者在出讓資源時可以獲得收益；2) 引導具有自私性的頻譜資源需求者有序、高效地使用可用頻譜資源.

由于所具有的公平性和有效性，拍賣機制被認為是高效的資源分配機制.從1994年開始，F(xiàn)CC已經(jīng)舉辦了一系列的頻譜牌照拍賣，并且從中收取了巨額的收益.在歐洲，政府部門為UMTS[4]和LTE[5]頻譜的使用也舉辦了大規(guī)模的拍賣.但是這些拍賣機制針對的是大型的無線網(wǎng)絡服務提供者，我們的目標針對的是小規(guī)模的無線服務應用提供者，比如社區(qū)或者家庭的無線網(wǎng)絡提供者.

設計一套靈活的、貼近實際的頻譜拍賣機制存在諸多挑戰(zhàn)，現(xiàn)有的頻譜工作主要考慮5個挑戰(zhàn)：

1) 防策略性(strategy-proofness)

第1個主要的挑戰(zhàn)來自于自私用戶的策略行為.在防策略性頻譜拍賣機制中，簡單地提交真實的頻譜需求信息，包括對信道的估值和需求信道集合，能夠最大化信道拍賣參與者的效益.由于拍賣參與者大多是理性和自私的，他們總是希望通過策略性地操縱拍賣來提高他們的收益.在實際的頻譜交易市場中，自私的參與者不僅會謊報他們對信道的估值，也會謊報他們需求的信道集合.當報價和需求的信道集合都是買家私有信息的時候，我們稱這樣的買家為多策略買家.這些自私行為不可避免地會影響到其他參與者的收益，所以，如果頻譜拍賣機制不能保證防策略性，將會極大地打擊真實的買家參與頻譜拍賣市場的積極性.現(xiàn)有的大部分工作并沒有考慮多策略買家的拍賣模型，多策略買家拍賣機制的設計屬于多參數(shù)激勵機制設計的范疇.多參數(shù)激勵機制設計仍然是算法博弈論(algorithmic game theory)領域內(nèi)的開放型研究問題，還不存在行之有效的解決方案.文獻[6-7]給出了在多參數(shù)激勵機制中要滿足防策略性必須要滿足的條件.一些論文也討論了負面的結(jié)果，比如文獻[8-9]指出在普適的多參數(shù)組合拍賣模型中，不存在既能滿足防策略性質(zhì)又能有系統(tǒng)性能保證的組合拍賣機制.

2) 信道的空間重用性

空間重用性使得頻譜資源不同于傳統(tǒng)的拍賣商品.如果2個無線用戶互相不在對方的干擾區(qū)域里，他們就能夠同時使用相同的無線信道.利用頻譜的空間重用性能夠極大地提高頻譜的利用率.

3) 信道的異質(zhì)性

無線頻譜資源的通信特性使得在信道拍賣中的拍賣物品具有異質(zhì)性.頻譜的異質(zhì)性來源于2個方面：空間上的異質(zhì)性和頻率上的異質(zhì)性.一方面，在不同的地區(qū)，信道的可用性和信道的通信質(zhì)量是不同的;另一方面,具有不同中心頻率的信道也具有不同的傳播和穿透特性.

4) 投標的多樣性

無線設備有可能配備多根天線，使得無線設備在同一時刻能夠工作在多個不同的異質(zhì)信道上.因此一個無線用戶根據(jù)他的服務質(zhì)量需求，能夠同時請求多個不同的信道.更進一步地說，由于信道的異質(zhì)性，買家對不同的異質(zhì)信道組合會有多樣化的偏好.比如一個次級網(wǎng)絡用戶有可能對某些成對的信道(用來提供LTE服務)具有較高的估值，對另外非成對的信道(用來提供WiMax服務)有較低的估值.因此，在頻譜拍賣機制中允許買家對不同的信道集合可以有不同的估值.允許買家投標的多樣性，可以提高買家獲得信道的機會，使得頻譜重分配機制更加靈活、高效.

5) 社會福利(social welfare)最大化

拍賣中最基本和普遍的優(yōu)化目標是最大化社會福利，也就是獲勝方對他們所分配物品估值的總和.然而，最大化社會福利通常是NP難的問題，在多項式時間內(nèi)并不能得到最優(yōu)解.

圖1展示了運用組合拍賣的技術來解決電視白頻譜重分配的問題.電視白頻譜具有空間和頻率上的異質(zhì)性，不同地區(qū)的白頻譜設備能夠訪問到不同的電視白頻譜，并且具有不同的最大允許功率、信道干擾強度、信道噪聲強度等.電視頻譜的頻率范圍是54～806 MHz，導致了不同的白頻譜具有不同的頻率特性.

Fig. 1　Heterogeneous TV white space spectrum redistribution based on combinatorial auctions.圖1　基于組合拍賣的異質(zhì)電視白頻譜重分配機制

1國內(nèi)外研究現(xiàn)狀及發(fā)展動態(tài)分析

1.1研究背景

頻譜資源分配問題是移動互聯(lián)網(wǎng)中典型的激勵機制設計問題.在本節(jié)將簡要地回顧移動互聯(lián)網(wǎng)激勵機制的研究背景.通過這個研究背景的介紹，我們能夠更清楚地了解動態(tài)頻譜重分配問題的研究動機和研究意義.

移動互聯(lián)網(wǎng)絡的迅速發(fā)展和廣泛應用已改變了現(xiàn)代人類的生活方式，其高效運行有賴于各組網(wǎng)用戶節(jié)點間的協(xié)同合作.以往的無線通信設備將網(wǎng)絡協(xié)議固化在硬件中，以保證用戶節(jié)點忠實地遵循網(wǎng)絡協(xié)議.但隨著無線通信設備的快速發(fā)展，以及軟件無線電(software defined radio)和智能移動設備(例如智能手機和平板電腦)的廣泛使用，用戶可以越來越靈活地控制他們的無線通信設備.

由于移動互聯(lián)網(wǎng)絡具有分布性和自組性的特點，故其與傳統(tǒng)的分布式自治系統(tǒng)(distributed autonomous system)一樣面臨著用戶節(jié)點的自主協(xié)同問題，即用戶節(jié)點的自私性所引起的網(wǎng)絡整體性能下降.例如，搭便車問題(free-rider problem)，用戶節(jié)點只索取資源或服務而不貢獻資源或服務;逆向選擇問題(adverse selection problem)，用戶節(jié)點通過透露錯誤的信息誤導系統(tǒng)向有利于自己的方向發(fā)展;串謀舞弊問題(collusion problem)，用戶節(jié)點結(jié)成小團體以謀取更大的利益.研究表明，以Gnutella為代表的分布式自治系統(tǒng)中有近70%的搭便車節(jié)點[10].在移動互聯(lián)網(wǎng)絡中，這種自私行為可能損害網(wǎng)絡的連通性，降低網(wǎng)絡的可用性.又如，本文所考慮的無線頻譜資源重分配問題.認知無線電(cognitive radio)技術為有效利用閑置頻譜資源提供了一種有效的途徑，配備認知無線電的移動互聯(lián)網(wǎng)絡節(jié)點可共享檢測到的“頻譜空洞”進行通信.為了獲得更大通信流量，自私的用戶節(jié)點傾向于調(diào)制其認知無線電設備到盡可能寬的通信頻帶，或縮短信道接入時的退避等待時延以獲取更長的信道使用時間.這些自私行為將會增大無線自組網(wǎng)絡中的信號干擾，破壞通信媒介訪問控制協(xié)議的公平性，從而損害移動互聯(lián)網(wǎng)絡的健壯性.

可見，如果沒有有效的機制保證用戶節(jié)點間的協(xié)同合作，那么用戶節(jié)點的自私行為將會使移動互聯(lián)網(wǎng)絡進入無政府的混亂狀態(tài)，導致網(wǎng)絡可用性和健壯性的急劇下降.然而，移動互聯(lián)網(wǎng)絡所特有的高度動態(tài)性和連接間斷性，決定了我們無法簡單地利用分布式自治系統(tǒng)中已有的技術解決新興的移動互聯(lián)網(wǎng)絡中的自主協(xié)同問題.所以，我們需要設計適用于移動互聯(lián)網(wǎng)絡的有效機制，以激勵移動互聯(lián)網(wǎng)絡中的用戶節(jié)點相互協(xié)同合作，保證移動互聯(lián)網(wǎng)絡的高效運行.

移動互聯(lián)網(wǎng)絡中自私用戶節(jié)點之間的相互作用關系可以自然地抽象為博弈模型.所以，本文將以博弈論為主要工具，研究用戶節(jié)點在移動互聯(lián)網(wǎng)絡中的交互行為.博弈論研究多個決策者間競爭的交互關系，以及尋求最優(yōu)行為策略的數(shù)學理論和方法.以博弈論為工具開展移動互聯(lián)網(wǎng)絡合作激勵機制研究具有三大優(yōu)勢：

1) 通過將移動互聯(lián)網(wǎng)絡中的問題形式化為策略博弈模型，我們可以利用豐富的博弈論工具分析用戶節(jié)點的交互行為策略及其對網(wǎng)絡的影響.

2) 博弈論為我們提供了在競爭環(huán)境中實現(xiàn)單目標和多目標優(yōu)化的理論基礎和可行辦法.

3) 包括非合作博弈在內(nèi)的許多策略博弈模型符合移動互聯(lián)網(wǎng)絡分布式動態(tài)決策的特征，其研究成果對我們設計無線網(wǎng)絡合作激勵機制提供了有力的支持.

移動互聯(lián)網(wǎng)用戶協(xié)同激勵機制設計問題自2000年以來得到了國內(nèi)外廣大科研人員越來越高的重視.2008年以來形成了一個高潮，一些一流國際刊物紛紛推出了相關專刊，并涌現(xiàn)出一批由北美和歐洲著名高校和科研機構(gòu)發(fā)起的高水平專門學術會議(例如Gamecomm[11],GameNets[12]和GameSec[13]).多個主流網(wǎng)絡與通信領域的學術會議也紛紛開設相關主題的分會，同時收錄的相關學術論文數(shù)量也呈上升趨勢.

2000—2002年是用戶協(xié)同激勵機制研究的起步階段，所采用的激勵機制以簡單的基于信譽的機制為主，但該領域的研究工作迅速得到了一批頂尖科研人員的關注.在隨后的4年中(2003—2006年)，每年都有較穩(wěn)定數(shù)量的相關論文出現(xiàn)，這期間的研究工作大都集中在路由選擇激勵機制上.2007年以來，由于移動互聯(lián)網(wǎng)和認知無線電的廣泛應用，用戶協(xié)同激勵機制在確保無線網(wǎng)絡正常運行(特別是無線頻譜資源的公平、合理、高效的管理)中的作用也變得更加重要，也受到了更加廣泛的關注.近些年，相關論文數(shù)量的急劇增長，也從一個側(cè)面反映了目前用戶協(xié)同激勵機制研究的重要性.

1.2頻譜分配激勵機制

在本節(jié)中，我們將重點回顧頻譜分配激勵機制.頻譜分配激勵機制主要基于策略博弈(strategic game)和拍賣(auction)2種模型.

1) 基于策略博弈模型的頻譜分配激勵機制.該機制研究開始于對納什均衡(Nash equilibrium)的分析.Halldorsson等人聯(lián)合分析了頻譜分配博弈中形成納什均衡所帶來的無秩序代價(price of anarchy)[14].Felegyhazi等人分析了多個無線應用服務提供商(service provider)競爭使用頻譜資源爭奪用戶的問題[15].Felegyhazi等人又研究了信道分配博弈中納什均衡的存在性問題，并提出了使信道分配博弈收斂到納什均衡的集中式和分布式算法[16].隨后，吳帆等人聯(lián)合提出了一種信道分配激勵機制，使信道分配博弈能夠一步收斂到強占優(yōu)策略均衡(strongly dominant strategy equilibrium)，并最大化此均衡狀態(tài)下整個系統(tǒng)的吞吐量[17-18].王新兵等人提出了一種防串謀性納什均衡，并證明了其在頻譜分配博弈中的存在性[19].張黔等人率先研究了一個三層頻譜分配市場模型中納什均衡的存在性[20].Kasbekar和Sarkar利用重復博弈模型研究了認知無線電網(wǎng)絡中的信道有償轉(zhuǎn)讓問題，并明確給出了納什均衡的構(gòu)造方法[21].2011年吳帆等人提出了一種適應動態(tài)可調(diào)信道的頻譜分配激勵機制[22]，該激勵機制能夠使頻譜分配一步收斂到占優(yōu)策略均衡(dominant strategy equilibrium)，并最大化整個無線網(wǎng)絡的吞吐量.在自私的參與者中進行資源分配問題已經(jīng)在不同的網(wǎng)絡環(huán)境中得到了廣泛的研究，比如無線網(wǎng)狀網(wǎng)絡[23]、OFDMA蜂窩網(wǎng)絡[24]和LTE網(wǎng)絡[25].

2) 基于拍賣模型的頻譜分配激勵機制.該機制以Zhou等人提出的VERITAS[26]和TRUST[27]為代表.VERITAS采用了類似于eBay的拍賣模式，讓網(wǎng)絡節(jié)點競標頻譜資源，并根據(jù)各節(jié)點的出價情況決定得標者及其需支付的費用.VERITAS既保證了頻譜拍賣的防策略性，又在一定程度上提高了頻譜的空間利用率.TRUST創(chuàng)造性地將頻譜分配和復式拍賣(double auction)相結(jié)合，有效防止了頻譜資源出售和需求雙方面的自私行為，但存在頻譜利用率低的問題.隨后，吳帆等人提出了一種新型的保留價頻譜拍賣機制SMALL[28].SMALL既能保證頻譜拍賣的防策略性，又能彌補VERITAS和TRUST頻譜利用率較低的不足.此外，張黔等人提出了一種基于VCG(由Vickrey[29],Clarke[30]和Groves[31]的開創(chuàng)性工作而得名)的頻譜拍賣機制[32].Zhou和Zheng還研究頻譜拍賣中的串謀舞弊問題，并提出Athena[33]為頻譜拍賣提供強度可調(diào)的串謀防控機制.最近，王新兵等人創(chuàng)造性提出了一種基于組合拍賣(combinatorial auction)的信道分配機制[34].除此之外，在信道拍賣上還有一些其他的相關工作，比如在線信道拍賣機制[35]、信道拍賣中的利潤最大化問題[32].考慮到求解最優(yōu)解的較高的時間復雜度，針對不同的信道干擾模型和買家的不同的估值函數(shù)形式，研究人員提出了多種有效的近似算法[36-37].我們在這方面也做了一些創(chuàng)造性的工作，比如異質(zhì)頻譜拍賣算法[38-39]，具有隱私保護功能的頻譜拍賣算法[40].

近年來，研究者開始關注基于在線拍賣(online auction)的頻譜接入激勵機制.美國伊利諾伊理工大學李向陽領導的WINET研究組在在線頻譜拍賣和激勵機制設計上有著深入的研究[41-46].在文獻[42]中作者對單純用戶的頻譜接入行為進行分析，并設計了在線頻譜分配與收費機制，使總社會效益最大化.當用戶到達服從泊松分布時，TODA[41]在線拍賣機制能夠取得線下(off-line)VCG拍賣機制社會效益的80%和頻譜使用率的70%.SALSA[45]在2種用戶到達模型(半隨機到達模型與隨機到達模型)下，取得了社會效益和預期收入的同步近似最大化.SOFA[42]對競標人在到達之后的競標時間和中間拍賣方的決策時間作了限制，并規(guī)定獲勝方只能獲得單個信道，進而在可搶占的情況下使得拍賣系統(tǒng)取得納什均衡.TOFU[43]在SOFA的基礎上，使得自私的用戶不能通過低價競標的方式獲益，且取得總收入相比線下VCG拍賣機制的比例大于95%，他們還考慮了多信道在線拍賣.楊耀宇和龍承念等人在考慮時間和空間可重用的情況下，利用在線市場結(jié)算(online market clearing)方法針對動態(tài)沖突圖(dynamic conflict graph)設計結(jié)算規(guī)則[47].Deek等人設計的Topaz[35]應用了三維打包(3D bin packing)技術，將時間、空間、頻率分布同時考慮進行分配，采用基于臨界值的收費方法，保證媒介接入在線拍賣的可信性.

1.3拍賣機制設計

在本節(jié)中，我們著重回顧了博弈論中拍賣機制設計的相關工作.拍賣機制設計是博弈論中的重要分支，而其中組合拍賣機制又是拍賣機制領域的研究熱點.在過去的10年中，諸多學者針對不同的模型，提出了多種組合拍賣機制.Dobzinski[48]，Buchfuhrer等人[49]和Papadimitriou等人[50]證明了在普適的組合拍賣模型中最優(yōu)社會福利和防策略性不能夠同時達到.Lehmann甚至斷言在多策略的買家模型中，任何貪心的分配算法都無法保證防策略性[51].

考慮到組合拍賣問題的計算復雜性，眾多研究學者提出具有近似比和防策略性的組合拍賣機制[52-54].在文獻[55]中，作者將信道在時間和頻譜維度上分配問題建模成單策略的組合拍賣問題，并且提出了一個基于貪心分配方法來達到近似最優(yōu)社會福利.但是以上所有的組合拍賣機制并沒有考慮頻譜的空間重用性，因此不能直接運用到動態(tài)頻譜分配中.

拍賣機制已經(jīng)被廣泛地運用于各種不同形式的資源分配問題，比如云計算中的資源分配問題[56-57]、移動參與式感知中的任務分配問題[58-59]和社交網(wǎng)絡中的動態(tài)合作問題[60].除了拍賣機制之外，一些強有力的工具，比如契約理論[61]、排隊理論[62]和隨機算法設計[37]，都被運用到了頻譜市場設計的各個方面.

1.4博弈論概念簡介

在本節(jié)中，我們簡要地描述在動態(tài)頻譜管理研究中經(jīng)常使用到的相關博弈論知識.

在博弈論里一個很重要的概念是占優(yōu)策略.

占優(yōu)策略的概念是激勵相容(incentive com-patibility)性質(zhì)的基礎，在直接揭示的拍賣中，激勵相容的性質(zhì)意味著對于任何的買家沒有激勵來使他對他的私有信息進行撒謊，因此真實地反應出他的信息是每個買家的占優(yōu)策略.一個伴隨的概念是個人理性(individual rationality)，這意味著每一個參與游戲的玩家都希望得到的收益能夠不少于他不參加游戲所能得到的收益.我們現(xiàn)在引入防策略性機制(strategy proof mechanism)定義.

定義2. 防策略性機制[65-66].一個機制是防策略性的，當它滿足激勵相容和個人理性.

2目前頻譜拍賣存在的問題

雖然近些年來涌現(xiàn)出不少頻譜資源重分配的研究成果，但我們認為這些工作普遍存在著模型失真、均衡失判、機制失信、分布失控4大問題.

1) 模型失真

博弈模型是開展動態(tài)頻譜資源重分配的基礎，但多數(shù)已有工作為了讓問題可解，在博弈模型的構(gòu)建過程中引入了過多理想化的假設.如假設組網(wǎng)節(jié)點同構(gòu)，具有相同的處理能力、傳輸速率、發(fā)射功耗等；又如，假設通信信道同質(zhì)，具有相同的帶寬、噪聲和干擾強度等.這種讓問題適應解法的研究方式，勢必導致研究成果的實用性大大降低.

2) 均衡失判

多數(shù)已有工作止步于分析納什均衡的存在性，然而給定一個博弈模型，納什均衡往往并不是唯一的，不同納什均衡帶來的系統(tǒng)整體性能往往也是不同的.當有多個納什均衡存在時，如何判別不同納什均衡的優(yōu)劣，有待進一步研究.納什均衡的存在，并不等價于系統(tǒng)能夠在有限時間內(nèi)收斂到納什均衡，從而納什均衡的收斂性也是我們需要研究的問題.

3) 機制失信

納什均衡是博弈論中相對脆弱的解決方案概念(solution concept)，當存在多個納什均衡時，參與者仍然可能通過操縱博弈過程，使系統(tǒng)收斂到對其較有利的納什均衡狀態(tài).然而，能夠達到占優(yōu)策略均衡或防策略性的高強度激勵機制還不多.

4) 分布失控

已有的激勵機制大都依賴于一個可信第三方(或中心控制)來保證機制的可信性，如負責虛擬貨幣結(jié)算的中心銀行和記錄聲譽分數(shù)的信譽中心.這種集中式的控制方式不適用于分布式的網(wǎng)絡環(huán)境，導致在分布式網(wǎng)絡中可行的方案只剩下物物直接交換.顯然，物物交換不利于網(wǎng)絡信息傳播與服務傳遞的靈活性.現(xiàn)有的頻譜拍賣機制大都需要有一個可信的中心節(jié)點來負責拍賣的有序進行.

3頻譜動態(tài)管理中的關鍵學科問題

針對第2節(jié)所述模型失真、均衡失判、機制失信、分布失控4大問題，動態(tài)頻譜管理的研究將緊密圍繞以下關鍵科學問題展開：

1) 準確博弈模型的構(gòu)建(研究模型失真問題)

博弈模型是從現(xiàn)實網(wǎng)絡環(huán)境中高度抽象出來的數(shù)學模型.博弈模型描述了參與者(用戶節(jié)點)的利益趨向和在博弈中的理性行為策略，并決定了參與者的行為策略所產(chǎn)生的最終博弈結(jié)果.構(gòu)建能夠準確反映復雜頻譜管理系統(tǒng)中的博弈模型是研究和設計頻譜拍賣機制的基礎所在.一個博弈模型由參與者效用函數(shù)(payoffutility function)和參與者策略集合(set of strategies)兩個主要部分組成.效用函數(shù)反映了參與者在博弈中的利益趨向；策略集合反映了參與者的行為空間.準確選取效用函數(shù)和策略集合對準確判斷參與者的行為目標、分析博弈均衡狀態(tài)及設計切實有效的激勵機制至關重要.

2) 納什均衡的存在性、唯一性和收斂性(研究均衡失判問題)

給定一個無線網(wǎng)絡博弈問題或者具體的頻譜重分配問題，我們首先關心的是在沒有外界因素影響的條件下該博弈中是否存在納什均衡.如果存在，納什均衡是否唯一.當存在多個納什均衡時，需要判斷各個納什均衡的優(yōu)劣.給定評判標準，是否存在一個最優(yōu)的納什均衡.當存在最優(yōu)納什均衡時，系統(tǒng)如何收斂到一個最優(yōu)納什均衡，以及收斂的時間開銷和通信開銷如何評估將是一個重要的問題.

3) 強激勵機制的存在性與設計(研究機制失信問題)

納什均衡是一種相對較脆弱的解決方案概念，脆弱的原因有3個：

① 納什均衡對某一參與者遵循其均衡策略的激勵作用，建立在所有其他參與者都遵循他們相應的均衡策略的假設基礎上.而當上述假設不能得到保證時，納什均衡則無法對參與者產(chǎn)生任何激勵作用.

② 網(wǎng)絡系統(tǒng)在達到納什均衡時，其性能往往不能達到最優(yōu)化.例如，系統(tǒng)吞吐量沒達到最大化，或路由選擇的路徑非最低功耗路徑.由于網(wǎng)絡系統(tǒng)的納什均衡狀態(tài)往往并不唯一，某些自私節(jié)點為了最大化個人利益，會故意引導網(wǎng)絡系統(tǒng)收斂到對其有利的納什均衡狀態(tài)，導致網(wǎng)絡整體性能受損.

③ 網(wǎng)絡系統(tǒng)收斂到納什均衡的過程往往非常慢長.在某些情況下，網(wǎng)絡系統(tǒng)甚至無法收斂到一個納什均衡狀態(tài)，而在多個狀態(tài)之間來回震蕩.

為了克服納什均衡的弱點，我們將以最優(yōu)化社會效益(social efficiency)為目標，分析各種無線網(wǎng)絡博弈激勵機制在理論上能夠達到的最高強度.例如，常見解決方案概念強度由高到低排序如下：占優(yōu)策略均衡、貝葉斯納什均衡(Bayesian Nash equilibrium)、納什均衡.目前，在激勵機制最高可實現(xiàn)強度方面的研究結(jié)果還存在很大的空白，導致大多數(shù)現(xiàn)有激勵機制的強度是否達到了理論上的最高強度并不明確.本文的研究將填補這一空白.

在激勵機制設計方面，一個高效的、可信的強激勵機制應具備3個特性：①每個參與者的最優(yōu)策略不依賴于任何其他參與者使用的策略;②系統(tǒng)在達到均衡狀態(tài)時，社會效益得到最優(yōu)化;③系統(tǒng)可一步收斂到均衡狀態(tài).

4) 可信第三方的依賴性(研究分布失控問題)

已有的激勵機制大都依賴于一個可信第三方的全程參與，以保證激勵機制達到理想的強度.例如，基于拍賣的動態(tài)頻譜分配激勵機制有賴于一個可信的拍賣商的全程參與.然而，在分布式的無線網(wǎng)絡環(huán)境中，往往不存在一個可信的實體能夠掌握整個網(wǎng)絡的信息，充當拍賣商的角色.所以，一個實用的激勵機制應該適應分布式的無線網(wǎng)絡環(huán)境.

4可行的研究方案

針對現(xiàn)有工作存在的問題，我們認為應該采用策略博弈模型(strategic game model)及擴展博弈模型(extensive game model)來研究動態(tài)頻譜分配中的用戶行為.所用到的主要解決方案概念及其強度關系由圖2所示.需要說明的是，我們將采用的解決方案概念將不局限于本節(jié)所列，將在具體研究過程中選擇合適的解決方案概念作為激勵機制設計的目標.

Fig. 2　The relation of solution concepts.圖2　解決方案概念強度關系

納什均衡和子博弈精煉均衡(subgame perfect equilibrium)是博弈論中強度相對最弱的均衡狀態(tài).在納什均衡狀態(tài)中，給定其他參與人的策略組合，任何參與人都無法通過僅調(diào)整其自身策略實現(xiàn)提高個人收益的目的.給定一個子博弈精煉均衡，在其任何一個子博弈中均是一個納什均衡.

強帕累托最優(yōu)均衡比納什均衡和子博弈精煉均衡的強度略高.在強帕累托最優(yōu)均衡中，不存在另一個策略組合可以在不使任何其他參與者收益變差的前提下使至少一個參與者的收益增加.

5基于組合拍賣的異質(zhì)頻譜重分配機制

基于第4節(jié)所概括的可行研究方案，我們將展示一個具體的頻譜拍賣機制，該機制能達到最高強度的均衡，即(嚴格強)占優(yōu)策略均衡.

5.1問題形式化定義

本節(jié)我們將給出異質(zhì)頻譜拍賣問題的拍賣模型，并提出虛擬信道的概念.通過虛擬信道，我們能夠?qū)愘|(zhì)頻譜拍賣的問題轉(zhuǎn)化為傳統(tǒng)的組合拍賣問題.

5.1.1拍賣模型

我們考慮的是一個靜態(tài)的頻譜拍賣場景，其中有一個主用戶，我們稱之為賣家，想用通過出售他臨時空閑的無線信道資源來獲得一定的收益.同時一些次級用戶(比如WiFi熱點)，我們稱之為買家，想要租借主用戶的空閑信道來提供一定質(zhì)量的無線服務.由于諸多原因，比如背景噪聲、環(huán)境溫度和地形等，信道會產(chǎn)生差異性，所以這里我們采用的是異質(zhì)信道模型.由于我們考慮的是異質(zhì)信道拍賣的場景，用戶對不同的信道會有自己不同程度的偏好.鑒于無線網(wǎng)絡設備能夠配備多根不同的天線，根據(jù)買家的需要，買家能夠請求多于一個的信道.考慮到買家偏好的多樣性和信道的異質(zhì)性，我們允許買家能夠提交多個不同的信道集合，這其中只能有一個信道集合能夠被分配給買家.在本文中，我們假定買家對他們請求的信道集合具有統(tǒng)一的估值.這是因為買家請求的任何一個信道集合都能夠滿足買家的服務需求.不同于傳統(tǒng)物品的拍賣，無線信道具有空間重用性，意味著在空間上離得足夠遠的用戶相互之間不會產(chǎn)生干擾，因此他們能夠同時工作在同一個信道上.

我們將異質(zhì)信道重分配的過程建模成一個組合拍賣模型.買家同時提交報價和信道需求給一個可信的拍賣商，這樣任何一個買家就不能知道其他買家的私有信息.拍賣商根據(jù)提交的報價和信道需求進行信道分配的決策，確定獲勝買家，并計算每個獲勝買家的費用.我們將頻譜市場中用來交易的異質(zhì)且正交的m個信道表示成：C={c1,c2,…,cm}.我們將買家集合表示成：N={1,2,…,n}.我們將組合頻譜拍賣模型用到的主要實體定義如下：

1) 信道需求Ri.每一個買家i∈N提交一個需求的信道集合向量給拍賣商：

2) 估價vi.買家i對于自己的信道集合向量中的任意一個信道集合的估價都相同，記為vi.對信道的估價是買家i的私有信息.買家的估價滿足2個性質(zhì)：覆蓋支配(free disposal)和規(guī)范化(normalization).覆蓋支配表示的是對于任意2個信道集合S和T，如果S?T，則我們有vi(S)≤vi(T)；規(guī)范化指的是對于?買家的估價為0，也就是vi(?)=0.我們表示所有買家的估價為

3) 報價bi.每一個買家i∈N可以向拍賣商提交一個報價bi，表示如果他獲得任意一個需求的信道集合，他愿意為此付不多于bi的價格.在這里，我們注意到買家的報價bi并不一定要等于他的估價vi.我們將所有買家的報價表示為

4) 支付費用pi.拍賣商對每一個獲勝的買家要收取一定的費用，記為pi.輸家不會被收取任何費用.我們用向量

來表示所有買家的支付費用.

5) 收益ui.一個買家的收益被定義為他對獲勝的信道集合的估價和他的支付價格之差.表示為

ui=vi-pi.

我們考慮的拍賣模型是買家是理性的且自私的情況，因此他們的目標是最大化自己的收益.相比于買家的目標，拍賣商的目標是最大化整個市場的社會福利.我們將社會福利定義如下：

定義3. 社會福利.在無線頻譜拍賣中，社會福利被定義為所有獲勝買家對他們競標得到的信道集合的估價的總和，表示為

其中，W是所有獲勝買家的集合.

在本設計中，我們假設所有的買家互相之間并不串謀，并且他們不會欺騙自己需求信道集合，我們將這些開放性的研究問題作為我們的后續(xù)工作.

5.1.2虛擬信道

不同于已有的信道拍賣機制，我們將介紹一個創(chuàng)新性的概念：虛擬信道(virtual channel)，來刻畫買家在信道使用上的沖突情況.通過引入虛擬信道，我們將異質(zhì)信道的拍賣模型轉(zhuǎn)化為傳統(tǒng)的組合拍賣模型.然而傳統(tǒng)的組合拍賣模型仍然存在較高的時間復雜度，所以在接下來的討論中我們將提出滿足防策略性且具有較好近似比的組合拍賣機制，以此來解決異質(zhì)信道的動態(tài)重分配問題.

算法1. 虛擬信道分配算法.

輸入:沖突圖集合G、信道需求向量R；

輸出:虛擬信道集合VC、更新的信道需求向量R′.

①VC←?，R′←R;

② for eachGk=(Ok,Ek)∈Gdo

③ for each(i,j)∈Ekdo

⑧ end for

我們給出虛擬信道的正式定義：

在大多數(shù)已有的信道拍賣的工作中[26-27]，基本都是采用單一的沖突圖來表示買家在信道使用上的沖突關系.但是，在異質(zhì)信道的情況下，每一個信道都會有一個不同的沖突圖.我們用Gk=(Ok,Ek)來表示在信道ck上的沖突圖，這里Ok?N表示的是能夠使用信道ck的所有用戶的集合，每一條邊(i,j)∈Ek表示的是買家i和買家j在信道ck上的沖突關系.我們用G={Gk|ck∈C}來表示所有沖突圖的集合.我們還將所有沖突圖中最大的度記為δ.頻譜拍賣商能夠通過一些實際的測量方法，比如測量校準的方法[68]來獲得每個信道上的沖突圖.我們注意到我們使用的沖突圖的建模方法屬于二元的干擾模型，比如協(xié)議模型.也有另外一些文章考慮的是在物理干擾模型中的無線頻譜重分配問題，更多討論請參見文獻[36-37].

Fig. 3　An example showing the generation of virtual channels.圖3　展示虛擬信道形成的示例

5.1.3問題定義

借助上述虛擬信道，我們現(xiàn)在可以將異質(zhì)信道的動態(tài)重分配問題轉(zhuǎn)化為一個經(jīng)典的組合拍賣問題.拍賣算法的輸出為獲勝買家的集合和他們被分配到的信道集合.

目標函數(shù)：

限制條件：

(1)

(2)

(3)

在這里限制條件式(1)表示了虛擬信道的數(shù)量限制.由于我們已經(jīng)從更新的信道集合中移除了所有的原始信道集合，我們并沒有考慮原始的信道集合.限制條件式(2)表明了每一個買家最多能夠從他需求的信道集合中獲得一個信道集合.限制條件式(3)表明了拍賣商的決策變量的取值.

如果最優(yōu)的社會福利能夠通過解決以上的二元整數(shù)規(guī)劃得到的話，那么我們就可以通過傳統(tǒng)的VCG拍賣機制來計算支付價格，并保證機制的防策略性.但是，以上的二元整數(shù)規(guī)劃問題能夠在多項式時間內(nèi)通過精確覆蓋問題規(guī)約過來，故能夠被證明是NP-Hard的問題.考慮到二元整數(shù)規(guī)劃問題在計算上的時間復雜程度，在5.2節(jié)中，我們將提出一個貪心的信道分配機制來達到近似最優(yōu)社會福利.我們會進一步將貪心分配方法和一個定價機制結(jié)合起來設計具有防策略性和較好近似比的異質(zhì)信道組合拍賣機制.

5.2異質(zhì)頻譜拍賣機制

本節(jié)我們考慮的是不可分的信道拍賣市場，也即信道只能夠以整體的形式分配給沒有沖突的買家，我們并沒有考慮時分復用信道的情況.在5.1節(jié)中，我們知道尋找最優(yōu)的信道分配策略在多項式時間內(nèi)是不能達到的.所以，在本節(jié)中，我們假設買家對他們需求的信道集合的估價是統(tǒng)一的，基于該假設我們提出了一個基于組合拍賣模型的異質(zhì)頻譜拍賣機制，該機制滿足了防策略性，并取得了近似最優(yōu)的社會福利.

我們設計的機制包含了3個主要的部分:虛擬信道的形成、獲勝買家的確定和支付價格的計算.我們先簡要地介紹機制的設計思想：1)我們生成虛擬信道來刻畫買家在無線信道上的使用干擾，并且將無線信道重分配的問題轉(zhuǎn)化為互斥虛擬信道的分配問題；2)我們提出了貪心算法來確定獲勝的買家，該貪心算法能夠獲得較好的近似比；3)我們設計了基于臨界報價的支付價格計算方案來保證頻譜拍賣機制的經(jīng)濟學性質(zhì).

5.2.1虛擬信道生成

虛擬信道的生成過程和算法1是一樣的，我們另外向每個買家i∈N的每個需求的信道集合中添加一個虛擬信道vci.虛擬信道vci是用來確保買家i最多能夠被分配一個需求信道集合.

VC=V∪{vci|i∈N}

5.2.2獲勝買家的確定

信道分配算法將所有的買家根據(jù)他們的虛擬報價進行非升序排列：

對于虛擬報價相等的情況，算法將依據(jù)以報價無關的原則來打破這種情況，比如買家標示符的字典序或者信道編號.根據(jù)L1的排序,算法將按序給每位買家分配最小的信道集合.

算法2. 確定獲勝買家的近似算法.

輸入：更新的信道需求向量R′、報價向量B;

輸出：獲勝買家和被分配的信道集合(W,S).

① (W,S)←(?,?),M←?；

② for eachi∈Ndo

④ end for

⑥ fori=1 tondo

⑧ forl=1 toφido

算法2展示了上述確定獲勝買家過程的偽代碼.在實際頻譜交易場景中，買家的人數(shù)n遠大于參數(shù)Φ，因此算法2的時間復雜度為O(nlogn).

5.2.3支付價格的計算

支付價格的計算基于臨界的虛擬報價，其定義如下：

定義5. 臨界的虛擬報價(virtual critical price).對于買家i∈N，其臨界的虛擬報價cr(i)∈L1被定義為買家i想要獲得需求的信道必須出的最低虛擬報價，也就是說，如果買家出的虛擬報價大于cr(i)，他就會獲勝，反之他就失敗.

我們注意到根據(jù)臨界虛擬報價的定義，無論買家i被分配了哪個具體的信道集合,他的臨界虛擬報價cr(i)始終是一樣的.

1) 如果買家i在拍賣中失敗了，或者臨界虛擬價格cr(i)不存在(用cr(i)=0來表示)，那么他的支付價格就為0.

我們可以證明設計的算法能夠滿足防策略性，并且可以獲得比較好的近似比.給出如下2個定理,具體的證明可以參見文獻[38].

定理1. 針對不可分的異質(zhì)信道重分配問題，我們設計的組合頻譜拍賣機制滿足防策略特性.

定理2. 我們提出的組合頻譜拍賣機制的近似比是O(δm)，其中δ是所有沖突圖中的最大度，m是信道的數(shù)量.

5.3實驗結(jié)果

5.3.1仿真方法

我們實現(xiàn)了機制SMASHER并將它和機制TAHES[67]和CRWDP[34]進行對比.所有的買家被隨機地分布在一個1 000 m×1 000 m的方形里，買家的數(shù)量以20為增量從20增加到400.被分配的信道可以是以下3個值:6,12和24.異質(zhì)信道可以有不同的干擾半徑，從250～450 m.在我們的拍賣過程中，我們允許買家可以具備不同數(shù)量的天線，但是限制最大的需求信道集合為3.我們假設買家對信道的估價是在(0,1]區(qū)間上均勻分布的，我們考慮單需求買家的情形(如Φ=1)和多需求買家的情形，此時買家最多能夠提交3個不同的信道子集(如Φ=3).我們所有的實驗結(jié)果都是取了200次的平均，所有的參數(shù)都可以不同于這里的取值，但是使用不同的參數(shù)所得到的仿真結(jié)果的規(guī)律是類似的.因此，在本文中我們僅僅展示這些參數(shù)下的實驗結(jié)果.

我們衡量如下的3個指標：

1) 社會福利.社會福利是獲勝買家對他們分配到的信道集合的總和.

2) 滿意度.滿意度指的是獲勝用戶的百分比.

3) 信道利用率.信道利用率是每個信道被分配到的天線的平均個數(shù).

5.3.2SMASHER機制的性能

我們將機制SMASHER的性能和2個不同的防策略性異質(zhì)信道拍賣機制TAHES和CRWDP進行比較.我們驗證了機制在單需求用戶(Φ=1)和多需求用戶(Φ=3)下的實驗結(jié)果.我們也驗證了在誤差率為10-4時的最優(yōu)結(jié)果，并把它記為IP-OPT.該最優(yōu)解能夠通過求解0-1整數(shù)規(guī)劃來得到，并把它作為算法的上界.

圖4表示了當有12個拍賣信道時的仿真結(jié)果，買家的人數(shù)是變化的.我們能夠看到，機制SMASHER總是比其他任何2個拍賣機制都優(yōu)，并且逼近最優(yōu)值，特別是當用戶是單需求的情況Φ=1.當買家的數(shù)目小于60時，機制TAHES不能夠形成擁有大量報價的有效的買家分，因此在這些條件下表現(xiàn)比較差；當買家的數(shù)目大于60時，機制CRWDP不是很好，因為機制CRWDP沒有考慮信道的空間重用性，也就是在所有情況下機制CRWDP的信道利用率都是1.圖4也表示了當買家的數(shù)量上升時社會福利和信道的利用率也會上升，但是滿意度下降了.一方面，更多的買家會導致在有限的信道上有更激烈的競爭，因此降低了滿意度；另一方面，機制SMASHER能夠在更多的買家中更有效率地分配信道，因此社會福利和信道利用率會升高.

Fig. 4　Performance when there are 12 channels.圖4　當信道數(shù)量為12時的系統(tǒng)性能

圖5展示了當有200個買家并且拍賣的信道數(shù)量是6，12，24時的實驗結(jié)果.我們可以再一次看到，機制SMASHER總是會比機制TAHES和CRWDP有更好的效果，不管是在單需求買家Φ=1或者是多需求買家Φ=3的情況下.圖5也展示了當拍賣信道的數(shù)量上升時社會福利和滿意度是上升的，但是信道利用率是下降的.原因是更多的交易信道會導致在拍賣中更多的成交量，當買家的數(shù)量固定時社會福利和滿意度就會增加；信道的利用率降低是因為當信道的數(shù)量提升時買家的天線能夠被分配在更多不同的信道上.

Fig. 5　Performance when there are 200 buyers.圖5　當買家數(shù)量為200時的系統(tǒng)性能

從圖4和圖5我們能夠看到,機制SMASHER犧牲了少量的系統(tǒng)性能來保證經(jīng)濟性質(zhì)上的魯棒性.雖然機制IP-OPT能夠達到近似的最優(yōu)社會福利，但是我們并不能直接將其用在信道重分配中，因為機制IP-OPT對經(jīng)濟性質(zhì)沒有任何保證.我們觀察到機制SMASHER在多需求用戶的情況下的系統(tǒng)性能總是會好于機制SMASHER在單需求用戶的情況.這是因為多需求的買家比單需求的買家有更大的機會獲得信道，這會導致在拍賣中更多的交易.因此，允許買家提交多份頻譜需求確實能夠提高拍賣的系統(tǒng)性能.

6結(jié)束語

在本文中，我們從博弈論的角度出發(fā)，對異質(zhì)頻譜重分配的問題進行了系統(tǒng)的調(diào)研和研究，指出現(xiàn)有工作存在的問題，并提出可行的解決方案.在次級頻譜市場中，我們假定無線網(wǎng)絡中的節(jié)點是策略性的玩家，擁有自身的利益，通過相互競爭來獲得有限的頻譜資源.我們采用拍賣機制來設計高效、有序的頻譜分配方案.我們指出一套靈活高效的頻譜拍賣機制需要考慮5個主要的設計難點：用戶自私策略行為、信道的異質(zhì)性、信道的空間重用性、用戶偏好的多樣性和社會福利的最大化.結(jié)合這5個設計挑戰(zhàn)，我們提出了一套高效的信道拍賣機制，證明了該機制滿足防策略性且能夠達到較好的近似比.

參考文獻

[1]Wheeler T. Federal Communications Commission(FCC)[EBOL]. 2000 [2015-10-10]. http:www.fcc.gov

[2]Miao Wei. Radio Administration Bureau (RAB)[EBOL]. 2002 [2015-10-10]. http:wgj.miit.gov.cn

[3]Stanforth P. Spectrum Bridge[EBOL]. 2010 [2015-10-10]. http:www.spectrumbridge.comHome.aspx

[4]Klemperer P. How (not) to run auctions: The European 3G telecom auctions[J]. European Economic Review, 2002, 46(4): 829-845

[5]Taga K. LTE Spectrum and Network Strategies[EBOL]. 2010 [2015-10-10]. http:www.adlittle.comdownloadstx_adlreportsADL_LTE_Spectrum_Network_Strategies.pdf

[6]Archer A, Kleinberg R. Truthful germs are contagious: A local to global characterization of truthfulness[C]Proc of the 9th ACM Conf on Electronic Commerce. New York: ACM, 2008: 340-366

[7]Rochet J C. A necessary and sufficient condition for rationalizability in a quasi-linear context[J]. Journal of Mathematical Economics, 1987, 16(2): 191-200

[8]Dobzinski S. An impossibility result for truthful combinatorial auctions with submodular valuations[C]Proc of the 43rd Annual ACM Symp on Theory of Computing. New York: ACM, 2011: 139-148

[9]Lehmann D, O’allaghan I L, Shoham Y. Truth revelation in approximately efficient combinatorial auctions[J]. Journal of the ACM, 2002, 49(5): 577-602

[10]Adar E, Huberman A B. Free riding on Gnutella[J]. First Monday, 2000, 5(10)

[11]Eduard J. The 4th Int ICST Workshop on Game Theory in Communication Networks (Gamecomm)[EBOL]. 2011 [2015-10-10]. http:www.game-comm.org2011index.shtml

[12]Vasilakos A. The 2nd Int ICST Conf on Game Theory for Networks (GameNets)[EBOL]. 2002 [2015-10-10]. http:gamenets.org2011

[13]Panaousis M. The 6th Conference on Decision and Game Theory for Security (GameSec)[EBOL]. 2015 [2015-10-10]. http:www.gamesec-conf.org

[14]Halldorsson M M, Halpern J Y, Li Li, et al. On spectrum sharing games[C]Proc of the 23rd Annual ACM Symp on Principles of Distributed Computing (PODC 2004). New York: ACM, 2004: 107-114

[15]Felegyhazi M, Hubaux J P. Wireless operators in a shared spectrum[C]Proc of the 25th IEEE Int Conf on Computer Communications (IEEE INFOCOM 2006). Piscataway, NJ: IEEE, 2006: 1-11

[16]Felegyhazi M, Cagalj M, Bidokhti S S, et al. Non-cooperative multi-radio channel allocation in wireless networks[C]Proc of the 26th IEEE Int Conf on Computer Communications (IEEE INFOCOM 2007). Piscataway, NJ: IEEE, 2007: 1442-1450

[17]Wu Fan, Zhong Sheng, Qiao Chunming. Globally optimal channel assignment for non-cooperative wireless networks[C]Proc of the 27th IEEE Int Conf on Computer Communications (IEEE INFOCOM 2008). Piscataway, NJ: IEEE, 2008: 1543-1551

[18]Wu Fan, Zhong Sheng, Qiao Chunming. Strong-incentive, high-throughput channel assignment for noncooperative wireless networks[J]. IEEE Trans on Parallel and Distributed Systems, 2010, 21(12): 1808-1821

[19]Gao Lin, Wang Xinbing. A game approach for multi-channel allocation in multi-hop wireless networks[C]Proc of the 9th ACM Int Symp on Mobile Ad Hoc Networking and Computing. New York: ACM, 2008: 303-312

[20]Jia Juncheng, Zhang Qian. Competitions and dynamics of duopoly wireless service providers in dynamic spectrum market[C]Proc of the 9th ACM Int Symp on Mobile Ad Hoc Networking and Computing. New York: ACM, 2008: 313-322

[21]Kasbekar S G, Sarkar S. Spectrum pricing games with bandwidth uncertainty and spatial reuse in cognitive radio networks[C]Proc of the 11th ACM Int Symp on Mobile Ad Hoc Networking and Computing. New York: ACM, 2010: 251-260

[22]Wu Fan, Singh N, Vaidya N, et al. On adaptive-width channel allocation in non-cooperative, multi-radio wireless networks[C]Proc of the 30th IEEE Int Conf on Computer Communications (IEEE INFOCOM 2011). Piscataway, NJ: IEEE, 2011: 2804-2812

[23]Duarte F B P, Fadlullah M Z, Vasilakos V A, et al. On the partially overlapped channel assignment on wireless mesh network backbone: A game theoretic approach[J]. IEEE Journal on Selected Areas in Communications, 2012 30(1): 119-127

[24]Lopez-Perez D, Chu Xiaoli, Vasilakos V A, et al. Power minimization based resource allocation for interference mitigation in OFDMA femtocell networks[J].IEEE Journal on Selected Areas in Communications, 2014, 32(2): 333-344

[25]Lopez-Perez D, Chu Xiaoli, Vasilakos A V, et al. On distributed and coordinated resource allocation for interference mitigation in self-organizing LTE networks[J]. IEEEACM Trans on Networking, 2013, 21(4): 1145-1158

[26]Zhou Xia, Gandhi S, Suri S, et al. eBay in the sky: Strategy-proof wireless spectrum auctions[C]Proc of the 14th ACM Int Conf on Mobile Computing and Networking (MobiCom 2008). New York: ACM, 2008: 2-13

[27]Zhou Xia, Zheng Haitao. TRUST: A general framework for truthful double spectrum auctions[C]Proc of the 28th IEEE Int Conf on Computer Communications (IEEE INFOCOM 2009). Piscataway, NJ: IEEE, 2009: 999-1007

[28]Wu Fan, Vaidya N. SMALL: A strategy-proof mechanism for radio spectrum allocation[C]Proc of the 30th IEEE Int Conf on Computer Communications (IEEE INFOCOM 2011). Piscataway, NJ: IEEE, 2011: 81-85

[29]Vickrey W. Counterspeculation, auctions, and competitive sealed tenders[J]. Journal of Finance, 1961, 6(1): 8-37

[30]Clarke E. Multipart pricing of public goods[J]. Public Choice, 1971, 11(1): 17-33

[31]Groves T. Incentives in teams[J].Econometrica, 1973, 41(4): 617-663

[32]Jia Juncheng, Zhang Qian, Zhang Qin, et al. Revenue generation for truthful spectrum auction in dynamic spectrum access[C]Proc of the 10th ACM Int Symp on Mobile ad Hoc Networking and Computing (MobiHoc 2009). New York: ACM, 2009: 3-12

[33]Zhou Xia, Zheng Haitao. Breaking bidder collusion in large-scale spectrum auctions[C]Proc of the 11th ACM Int Symp on Mobile Ad Hoc Networking and Computing (MobiHoc 2010). New York: ACM, 2010: 121-130

[34]Dong Mo, Sun Gaofei, Wang Xinbing, et al. Combinatorial auction with time-frequency flexibility in cognitive radio networks[C]Proc of the 31st IEEE Int Conf on Computer Communications (IEEE INFOCOM 2012). Piscataway, NJ: IEEE, 2012: 2282-2290

[35]Deek L, Zhou Xia, Almeroth K, et al. To preempt or not: Tackling bid and time-based cheating in online spectrum auctions[C]Proc of the 30th IEEE Int Conf on Computer Communications (IEEE INFOCOM 2011). Piscataway, NJ: IEEE, 2011: 2219-2227

[36]Hoefer M, Kesselheim T, V?cking B. Approximation algorithms for secondary spectrum auctions[C]Proc of the 23rd Annual ACM Symp on Parallelism in Algorithms and Architectures (SPAA 2011). New York: ACM, 2011: 177-186

[37]Hoefer M, Kesselheim T. Secondary spectrum auctions for symmetric and submodular bidders.[C]Proc of the 13th ACM Conf on Electronic Commerce (EC 2012). New York: ACM, 2012: 9-19

[38]Zheng Zhenzhe, Wu Fan, Chen Guihai. SMASHER: A strategy-proof combinatorial auction mechanism for heterogeneous channel redistribution[C]Proc of the 14th ACM Int Symp on Mobile Ad Hoc Networking and Computing (MobiHoc 2013). New York: ACM, 2013: 305-308

[39]Zheng Zhenzhe, Wu Fan, Tang Shaojie, et al. Unknown combinatorial auction mechanisms for heterogeneous spectrum redistribution[C]Proc of the 15th ACM Int Symp on Mobile Ad Hoc Networking and Computing (MobiHoc 2014). New York: ACM, 2014: 3-12

[40]Huang Qianyi, Tao Yixin, Wu Fan. SPRING: A strategy-proof and privacy preserving spectrum auctionmechanism[C]Proc of the 32nd IEEE Int Conf on Computer Communications (IEEE INFOCOM 2013). Piscataway, NJ: IEEE, 2013: 827-835

[41]Wang Shiguang, Xu Ping, Xu Xiaohua, et al. TODA: Truthful online double auction for spectrum allocation in wireless networks[C]Proc of 2010 IEEE Symp on Dynamic Spectrum Access Networks (DySPAN 2010). Piscataway, NJ: IEEE, 2010: 1-10

[42]Xu Ping, Li Xiangyang. SOFA: Strategyproof online frequency allocation for multihop wireless networks[C]Proc of the 20th Int Symp on Algorithms and Computation (ISAAC 2009). Piscataway, NJ: IEEE, 2009: 311-320

[43]Xu Ping, Li Xiangyang. TOFU: Semi-truthful online frequency allocation mechanism for wireless networks[J].IEEEACM Trans on Networking, 2011, 19(2): 433-446

[44]Xu Ping, Li Xiangyang, Tang Shaojie. Efficient and strategyproof spectrum allocations in multichannel wireless networks[J]. IEEE Trans on Computers, 2011, 60(4): 580-593

[45]Xu Ping, Wang Shiguang, Li Xiangyang. SALSA: Strategyproof online spectrum admissions for wireless networks[J]. IEEE Trans on Computers, 2010, 59(12): 1691-1702

[46]Xu Ping, Xu Xiaohua, Tang Shaojie, et al. Truthful online spectrum allocation and auction in multi-channel wireless networks[C]Proc of the 30th IEEE Int Conf on Computer Communications (IEEE INFOCOM 2011). Piscataway, NJ: IEEE, 2011: 26-30

[47]Yang Yaoyu, Wu Jie, Long Chengnian, et al. Online market clearing in dynamic spectrum auction[C]Proc of 2011 IEEE Global Telecommunications Conf (GLOBECOM 2011). Piscataway, NJ: IEEE, 2011: 1-5

[48]Dobzinski S. An impossibility result for truthful combinatorial auctions with submodular valuations[C]Proce of the 43rd Annual ACM Symp on Theory of Computing (STOC 2011). New York: ACM, 2011: 139-148

[49]Buchfuhrer D, Dughmi S, Fu Hu, et al. Inapproximability for VCG-based combinatorial auctions[C]Proc of the 21st Annual ACM-SIAM Symp on Discrete Algorithms (SODA 2010). New York: ACM, 2010: 518-536

[50]Papadimitriou C, Schapira M, Singer Y. On the hardness of being truthful[C]Proc of the 49th Annual IEEE Symp on Foundations of Computer Science (FOCS 2008). Piscataway, NJ: IEEE, 2008: 250-259

[51]Lehmann D, Oc＇allaghan L I, Shoham Y. Truth revelation in approximately efficient combinatorial auctions[J]. Journal of the ACM, 2002, 49(5): 577-602

[52]Bartal Y, Gonen R, Nisan N. Incentive compatible multi unit combinatorial auctions[C]Proc of the 9th Conf on Theoretical Aspects of Rationality and Knowledge (TARK 2003). New York: ACM, 2003: 72-87

[53]Zurel E, Nisan N. An efficient approximate allocation algorithm for combinatorial auctions[C]Proc of the 3rd ACM Conf on Electronic Commerce (EC 2001). New York: ACM, 2001: 125-136

[54]V?cking B. A universally-truthful approximation scheme for multi-unit auctions[C]Proc of the 23rd Annual ACM-SIAM Symp on Discrete Algorithms (SODA 2012). New York: ACM, 2012: 846-855

[55]Dong Mo, Sun Gaofei, Wang Xinbing, et al. Combinatorial auction with time-frequency flexibility in cognitive radio networks[C]Proc of the 31st IEEE Int Conf on Computer Communications (IEEE INFOCOM 2012). Piscataway, NJ: IEEE, 2012: 2282-2290

[56]Shi Weijie, Zhang Linquan, Wu Chuan, et al. An online auction framework for dynamic resource provisioning in cloud computing[C]Proc of the 2014 ACM Int Conf on Measurement and Modeling of Computer Systems (SIGMETRICS 2014). New York: ACM, 2014: 71-83

[57]Zhang Hong, Li Bo, Jiang Hongbo, et al. A framework for truthful online auctions in cloud computing with heterogeneous user demands[C]Proc of the 32nd IEEE Int Conf on Computer Communications (IEEE INFOCOM 2013). Piscataway, NJ: IEEE, 2013: 1510-1518

[58]Feng Zhenni, Zhu Yanmin, Zhang Qian, et al. TRAC: Truthful auction for location-aware collaborative sensing in mobile crowdsourcing[C]Proc of the 33rd IEEE Int Conf on Computer Communications (IEEE INFOCOM 2014). Piscataway, NJ: IEEE, 2014: 1231-1239

[59]Yang Dejun, Xue Guoliang, Fang Xin, et al. Crowdsourcing to smartphones: Incentive mechanism design for mobile phone sensing[C]Proc of the 18th Annual Int Conf on Mobile Computing and Networking (MobiCom 2012). New York: ACM, 2012: 173-184

[60]Wei Guiyi, Zhu Ping, Vasilakos A V. Cooperation dynamics on collaborative social networks of heterogeneous population

[J]. IEEE Journal on Selected Areas in Communications, 2013, 31(6): 1135-1146

[61]Sheng Shangpin, Liu Mingyan. Profit incentive in a secondary spectrum market: A contract design approach[C]Proc of the 32nd IEEE Int Conf on Computer Communications (IEEE INFOCOM 2013). Piscataway, NJ: IEEE, 2013: 836-844

[62]Jagannathan K, Menache I, Modiano E, et al. Non-cooperative spectrum access: The dedicated vs free spectrum choice[J]. IEEE Journal on Selected Areas in Communications, 2012, 30(11): 2251-2261

[63]Osborne M J, Rubenstein A. A Course in Game Theory[M]. Cambridge, MA: MIT Press, 1994

[64]Fudenberg D, Tirole J. Game Theory[M]. Cambridge, MA: MIT Press, 1991

[65]Mas-Colell A, Whinston M D, Green J R. Microeconomic Theory[M]. Oxford, UK: Oxford Press, 1995

[66]Varian H. Economic mechanism design for computerized agents[C]Proc of USENIX Workshop on Electronic Commerce. Berkeley, CA: USENIX Association, 1995: 13-21

[67]Feng Xiaojun, Chen Yanjiao, Zhang Jin, et al. TAHES: Truthful double auction for heterogeneous spectrums[C]Proc of the 31st IEEE Int Conf on Computer Communications (IEEE INFOCOM 2012). Piscataway, NJ: IEEE, 2012: 3076-3080

[68]Zhou Xia, Zhang Zengbin, Wang Gang, et al. Practical conflict graphs for dynamic spectrum distribution[C]Proc of the ACM SIGMETRICS Int Conf on Measurement and Modeling of Computer Systems. New York: ACM, 2013: 5-16

Wu Fan, born in 1981. Associate professor and PhD supervisor. Member of China Computer Federation. His main research interests include wireless networking and mobile computing, algorithmic game theory and its applications, and privacy preservation.

Zheng Zhenzhe, born in 1989. PhD candidate. His main research interests include algorithmic game theory, resource management in wireless networking and data center (zhengzhenzhe@sjtu.edu.cn).

中圖法分類號TP391

基金項目：國家“九七三”重點基礎研究發(fā)展計劃基金項目(2014CB340303);國家自然科學基金項目(61422208,61472252, 61272443,61133006)；上海市科學技術委員會基金項目(15220721300)

收稿日期：2015-07-13；修回日期：2015-10-26

This work was supported by the National Basic Research Program of China (973 Program) (2014CB340303), the National Natural Science Foundation of China (61422208,61472252,61272443,61133006), and Shanghai Science and Technology Fund (15220721300).