- 學位論文
短時段次級頻譜市場之具真實標性質拍賣機制設計
Design of Truthful Auction Mechanism for Short-interval Secondary Spectrum Access Market
摘要
由於可攜式智慧型裝置、無線寬頻接取技術及新興應用服務的發展，對於無線寬頻接取的需求快速地增加，全球行動數據流量預計在短短幾年內將有大於十倍的增長，無線及行動寬頻接取頻譜的短缺因此成為一全球皆面臨的挑戰。然而，許多頻譜量測結果卻顯示許多具執照的頻帶為低度使用或未充分利用。允許頻譜持有者分享頻譜接取權的次級頻譜市場是一能更佳利用無線通訊頻譜資源的潛在方法。鑒於動態頻譜接取及感知無線電技術的發展，本論文研究提出了一短時段次級頻譜接取市場，其允許執照持有者出租未使用或低度使用的頻譜單元給一群彼此競爭的行動虛擬營運商。出租頻譜單元的有效時間空檔為數十分鐘至數小時。 本論文研究首先介紹一短時段次級頻譜市場的設計架構，此架構提供了仲介的服務，包含有改善市場流動性、減輕市場資訊的不對稱及協調分享的過程。考慮到頻譜的短時段有效性，本論文研究了單一回合密封標的拍賣機制，並提出兩個具真實標性質的拍賣機制。第一個設計為以VCG拍賣為設計基礎的具真實標性質單邊拍賣，主要的創新設計有一累計型標單格式及一由頻譜仲介者創造的虛擬競標者，其標單則根據執照擁有者的底價來設定。累計型標單格式提供行動虛擬營運商最多的投標選擇，並允許行動虛擬營運上標得部分的頻道數目。虛擬競標者的導入保有了VCG真實標的性質並進一步達到個別理性及收支平衡。 第二個設計為一具真實標性質的雙邊拍賣，其不但可允許執照擁有者及行動虛擬營運商來分享及租用頻譜單元，更考慮了頻譜單元在空間及頻率上的異質性。為了能在空間維度上充份利用頻譜資源，將彼此不會互相干擾的行動虛擬營運商組成一群，並允許單一群中的行動營運商去共享頻譜資源是一常用的頻譜配置方法。然而，當行動虛擬營運商的需求為多個單元時，此一方法面臨如何決定群體標金及如何使拍賣具真實標性質的難題。所設計的雙邊拍賣具有兩個創新，第一個為依行動虛擬營運商標金所組成的虛擬競標群，一個虛擬競標群代表一群在空間需求上不衝突的行動虛擬營運商，其針對單一執照持有者進行單一頻譜單元的投標，一個虛擬競標群也是選標程序中的一基本實體。第二個創新為行動虛擬營運商間的差別式標金支付模式，對於一獲勝的虛擬競標群，其行動虛擬營運商平均分攤此虛擬競標群的標金做為所需支付的標金。對所有的執照持有者，每出租頻譜單元的營收皆為一相同的清算價格。此兩創新的結合達成在經濟上所需的特性如個體理性、收支平衡、執照持有者對於每單位底價的真實標及行動虛擬營運商對於需求數量及每單位標金的真實標。 除理論分析證明了單邊及雙邊拍賣設計皆達成在經濟上所需的特性，本論文亦提供了大規模的數值實驗分析。數值實驗結果顯示，相較於VCG拍賣，單邊拍賣所產生的單一頻譜單元收益平均高出31.3%。對於行動虛擬營運商，具累計型標單格式的拍賣能盡可能將頻譜單元租出並將行動虛擬營運商贏得單元數的取樣標準差維持在1.5之內。針對一短時段次級頻譜市場具200個行動虛擬營運商在競爭500個同質頻譜單元時，分配演算法的計算可在15秒內完成，驗證了能透過此設計有效利用短時段頻譜空檔的果效。針對雙邊拍賣設計，因允許多個互不衝突的行動虛擬營運商共享頻譜資源，儘管頻譜的租出數目占總幾數的比例皆低於0.6，所產生的收益仍比執照擁有者的期望值高出40%。而多個單邊拍賣及單一雙邊拍賣的分析比較結果顯示，不論是針對執照擁有者或行動虛擬營運商，多個單邊拍賣皆有高於單一雙邊拍賣的使用者效用。相較於雙邊拍賣只有0.568的頻譜租出比例，多個單邊拍賣0.936的租出比例能確實有效利用短時段頻譜空檔，且提高執照擁有者的出租意願。針對一有15個執照擁有者及30個行動虛擬營運商的短時段次級頻譜市場，兩種拍賣機制皆能在一分鐘的計算時間內完成頻譜分配，但多個單邊拍賣的求解時間將會比雙邊拍賣來得長。 此外，本論文採用Windows-Apache-MySQL-PHP (WAMPs)解法堆疊設計並實做一針對短時段次級頻譜市場的線上拍賣平台。此平台架構包含了負責網路間溝通的Apache超文字傳輸協定伺服器、開放原始碼的關聯式資料庫管理系統MySQL以及用以實現所設計拍賣演算法的伺服器端手稿語言PHP。除了展示所設計的拍賣機制具可實際應用性，此平台亦提供了一實驗環境用以測試使用者的真實競標行為。
並列摘要
Demands for mobile broadband access have increased rapidly because of the developments of portable smart devices, wireless broadband access (WBA) technologies and many new applications. Global mobile traffic is expected to have more than tenfold growth over a few years. Deficiency of spectrum availability for wireless and mobile access emerges as a significant challenge to be conquered worldwide. However, various spectrum usage measurements have indicated that most of the licensed spectrums are lowly utilized or not fully utilized. Secondary spectrum markets that allow spectrum owners to share access rights is a promising approach to better utilize spectrum for wireless communications. In view of the development of dynamic spectrum access (DSA) and cognitive radio (CR) techniques, this dissertation proposes a short-interval secondary spectrum (SiSS) access market that allows primary license holders (PLHs) to rent out unused or lowly utilized spectrum units to a few competing Mobile Virtual Network Operators (MVNOs). The availability of spectrum units for renting ranges from tens of minutes to hours. This dissertation first introduces a design of SiSS market framework with brokerage services that improve market liquidity, mitigate information asymmetry and coordinate the sharing process. In view of the short-interval availability of spectrum, we study single-round and sealed bid auction for spectrum sharing between the PLHs and MVNOs and propose two truthful auction mechanisms. The first is a Vickrey-Clarke-Groves (VCG) auction-based unilateral truthful auction. Key innovations are cumulative bidding format (CBF) and a virtual bidder by the spectrum broker, whose bids are based on PLH’s specification of per-unit reserve price. CBF provides MVNOs with maximal bidding options and allows MVNOs to win part of demands. Introduction of virtual bidder exploits the truthfulness of VCG and further achieves individual rationality and budget balance. The second is a bilateral truthful auction that not only supports PLHs and MVNOs to contribute and purchase multiple spectrum units, but also considers the spatial and frequency heterogeneity of spectrum availability. To exploit spectrum availability in the spatial domain, grouping conflict-free MVNOs and allowing them to share one same spectrum unit is a popular approach for spectrum allocation. However, when MVNOs have diverse demand amounts, such an approach encounters a challenge of how to determine the group bid and make the auction truthful. Our designs have two innovations. The first is the formation of virtual bidding group (VBG) based on MVNO bids. A VBG represents a group of spatially-separated MVNOs bidding on one spectrum unit of a PLH and acts as an entity for bid selection. The second is discriminatory payments by MVNOs that obliges MVNOs in a winning VBG to share the VBG bid as payment. All winning PLHs receive a clearing price for each rented spectrum unit. Integration of the two innovations achieve desirable economic properties of individual rationality, budget balance, PLH truthfulness with respect to per-unit reserve price bid and MVNO truthfulness with respect to demand amount and per-unit bid price. In addition to proving the achievement of desirable economic properties, we provide extensive numerical experimentations for both of unilateral and bilateral auction designs. Numerical experimentations show that unilateral auction generates in average 31.3% higher per-unit revenue to the PLH than VCG. For MVNOs, the design with CBF rents as many spectrum units out as possible and keeps the sample standard deviation of winning quantity lower than 1.5. For a SiSS market of 200 MVNOs and 500 homogeneous spectrum units, computation time of clearing an auction is within 15 seconds, which justifies the feasibility of exploiting short-interval spectrum availability. For the bilateral auction, by enabling conflict-free MVNO to share same spectrum units, although spectrum rent-out ratio is below 0.6 in all test instances, the generated spectrum revenue is higher than the expected revenue by PLHs in about 40%. Comparative analysis between multiple unilateral auctions and one bilateral auction of the same set of available spectrum units and players show that, no matter from the perspective of PLHs or MVNOs, multiple unilateral auctions lead to a higher total utility than the bilateral auction. Compared with bilateral auction that has only 0.568 spectrum rent-out ratio, multi-unilateral auction has 0.936 spectrum rent-out ratio and can truly exploit short-interval spectrum availability, which raises PLHs’ willingness for sharing. For a SiSS market of 15 PLHs and 30 MVNOs, computation times of two designs are both less than one minute but the solution time of multiple unilateral auctions will be longer than the time of bilateral auction. Furthermore, this dissertation designs and implements an online auction platform for SiSS market using a solution stack of Windows-Apache-MySQL-PHP (WAMP). The platform consists of an Apache HTTP server that runs in the background and handles the communication over players, an open-source relational database management system, MySQL, and a server-side scripting language, PHP, to implement the auction algorithms. In addition to demonstration of practicality of our design for application, the online auction platform provides an experimental environment for the human decision.