基于博弈論的頻譜動態管理研究

吳　帆　　　鄭臻哲

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

(fwu@cs.sjtu.edu.cn)

?

基于博弈論的頻譜動態管理研究

吳帆鄭臻哲

(上海交通大學電子信息與電氣工程學院上海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

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

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

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

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

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

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

1) 防策略性(strategy-proofness)

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

2) 信道的空間重用性

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

3) 信道的異質性

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

4) 投標的多樣性

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

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

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

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

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

1國內外研究現狀及發展動態分析

1.1研究背景

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

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

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

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

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

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

2) 博弈論為我們提供了在競爭環境中實現單目標和多目標優化的理論基礎和可行辦法.

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

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

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

1.2頻譜分配激勵機制

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

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

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

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

1.3拍賣機制設計

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

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

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

1.4博弈論概念簡介

在本節中，我們簡要地描述在動態頻譜管理研究中經常使用到的相關博弈論知識.

在博弈論里一個很重要的概念是占優策略.

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

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

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

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

1) 模型失真

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

2) 均衡失判

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

3) 機制失信

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

4) 分布失控

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

3頻譜動態管理中的關鍵學科問題

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4可行的研究方案

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

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

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

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

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

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

5.1問題形式化定義

本節我們將給出異質頻譜拍賣問題的拍賣模型，并提出虛擬信道的概念.通過虛擬信道，我們能夠將異質頻譜拍賣的問題轉化為傳統的組合拍賣問題.

5.1.1拍賣模型

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

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

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

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

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

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

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

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

ui=vi-pi.

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

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

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

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

5.1.2虛擬信道

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

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

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

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

①VC←?，R′←R;

② for eachGk=(Ok,Ek)∈Gdo

③ for each(i,j)∈Ekdo

⑧ end for

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

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

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

5.1.3問題定義

借助上述虛擬信道，我們現在可以將異質信道的動態重分配問題轉化為一個經典的組合拍賣問題.拍賣算法的輸出為獲勝買家的集合和他們被分配到的信道集合.

目標函數：

限制條件：

(1)

(2)

(3)

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

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

5.2異質頻譜拍賣機制

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

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

5.2.1虛擬信道生成

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

VC=V∪{vci|i∈N}

5.2.2獲勝買家的確定

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

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

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

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

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

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

② for eachi∈Ndo

④ end for

⑥ fori=1 tondo

⑧ forl=1 toφido

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

5.2.3支付價格的計算

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

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

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

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

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

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

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

5.3實驗結果

5.3.1仿真方法

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

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

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

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

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

5.3.2SMASHER機制的性能

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

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

Fig. 4　Performance when there are 12 channels.圖4　當信道數量為12時的系統性能

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

Fig. 5　Performance when there are 200 buyers.圖5　當買家數量為200時的系統性能

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

6結束語

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

參考文獻

[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

基金項目：國家“九七三”重點基礎研究發展計劃基金項目(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).