一個用於支持長期演進多媒體廣播多播服務與設備對設備服務的賽局理論方法

Abstract

第三代合作夥伴項目（3GPP）的兩個主要目標是展開長期演進（LTE）多媒體廣播多播服務與商業設備對設備（D2D）近端服務（ProSe）。因為行動通訊市場已經接近飽和狀態，加上可買的頻譜少之又少，所有行動服務業著（SPs）已經開始在尋找新的額外收入來源。 目前MBMS與D2D服務皆缺乏應用在廣大地區可行的經濟模式。在此論文裡， 我們提出兩個可行的經濟模式（一個是和MBMS有關，另外一個是和商業D2D服務有關），兩個都是用來解決資源分配的問題，而頻譜即是被上述服務所分配的資源，這些服務都是由廣告公司支持的。 無線網路資源分配的問題通常是組合最佳化的問題，也被視為非確定性多項式難題（NP-hard），其可透過窮舉搜尋法來解答問題。進一步說，當想獲取資源的主體有理性時，他們可能自私地回報假的私人信息以來操縱資源分配機制進而最大化自身被分配到的資源或最小化其所需付出的錢，結果即是所謂資源分配的問題變得更為複雜。傳統資源分配方法都需要主體真實地回報私人信息，但當考慮到主體的理性時，就有可能遭遇到無法做有效資源分配的情況。依賽局理論的 分析，我們識別主體的自私行為及提出新的解決方法來鼓勵主體真實地回報私人信息，加上以模擬結果來分析解決方法的效率。 首先，我們看到最近公開的LTE MBMS，那就是第十四LTE版本，即增 強MBMS（FeMBMS），其對MBMS服務可佔用更多細胞容量提供更多可能性，更有跨行動網路服務業的基地台雙連技術（Inter-MNO Dual Connectivity），動態MBMS，與非簽署顧客接收MBMS服務。此外，還可以共有MBMS網絡（SEN）分發共享內容，以及內容提供商也能決定分發內容的方法（單播或多播）。 對於即時串流影像，既快又有效率的資源分配是必須的，因此即時影像可利用基於需求要之MBMS運行（MooD）。為了在介質訪問控制層（MAC層）做MBMS資源分配，可以用正數線性規劃（ILP）來最佳化多個影像流資源分配，而ILP也被理解為NP-hard。我們觀察MAC層的資源分配，完整傳輸一個影像幀需佔用多種MAC分配時段，進而發現到基於梯度的資源分配方式能達到ILP類似的效果，就運算複雜度而言，不像ILP，我們提出的基於梯度的資源分 配方式只花費多項式時間（P-time）。 關於MBMS服務，我們提出一個行動電視系統，其中廣告業者支持這個行動電視服務。我們首先研究分析電視台收視如何影響到電視台的頻寬與每一個廣告業對電視台的計價。透過機制設計，我們設計一套鼓勵真誠投票的機制以準確得知每一個行動用戶在收看什麼電視台，因為每一個電視台分配的頻寬是根據目前對串流視頻的資源需求與收視率統計。基於預測的收視率與分配給電視台的頻寬， 我們設計一個鼓勵真價拍賣機制來分配每一塊廣告時段給廣告業，從而以分配廣告塊來支持所謂的MBMS服務。 最後，針對商業D2D服務，我們發現到SPs有機會'貨幣化'無法充分利用的頻譜。我們調查研究可被歸於子分區的商業D2D服務如何可利用SP控制的無法充分利用的頻譜。這個無法充分利用頻譜資源分配的問題可視為分配SP控制傳輸空間（Gaps）的問題，其用於商業D2D服務。因D2D的傳數據距離有限，所以在同一個地區裡一個Gap可分給幾個D2D基地台（一個D2D基地台即是一個傳播D2D服務的UE）。根據每一個D2D基地台的通道狀態，相關的頻寬是拍賣給對本地化 市場有興趣的廣告公司。為了在合理的時間內完成頻寬分配，我們設計一個只有P-time複雜度的鼓勵真實拍賣機制，而其利潤表現與理論最佳化的VCG拍賣機制結果類似。

Abstract Two of the goals of the 3rd Generation Partnership Project (3GPP) are to deploy Long Term Evolution (LTE) Multimedia Broadcast/Multicast Service (MBMS) and commercial Device to Device (D2D) Proximity Services (ProSe). As the mobile market is nearing saturation, and additional spectrum is scarce, Service Providers (SPs) are searching for additional sources of revenue. Currently, both MBMS and D2D services lack feasible economic models for wide-spread deployment. We present two economically feasible models for MBMS and commercial D2D services. Both of these models can be viewed as solving resource allocation problems, where the bandwidth is the resource being allocated by each of the aforementioned services and the advertisers are the sponsors of said service. Wireless Networking Resource Allocation problems are often combinatorial optimization problems, which are considered NP-hard and are solvable via an exhaustive search. Furthermore, when the players interested in acquiring resources exhibit rationality, they may try to manipulate the resource allocation mechanism by acting selfishly and misreport their private information in order to increase their resource allocation / reduce their costs. As such, these resource allocation problems are considered complex due to the rationality of the players and the combinatorial optimization. Based on a game-theoretic analysis, we identify the selfish behaviors of the players and propose novel solutions to incentivize the players to truthfully reveal their private information in a tractable computational complexity. Simulations are presented for evaluating the performance of each of the proposed solutions. We first study the most recent release of LTE MBMS, i.e. LTE Rel’14 FeMBMS. LTE FeMBMS opens the possibilities for a higher percentage of cell capacity to be allocated for MBMS services, in addition to inter-Mobile Network Operator dual connectivity, dynamic MBMS, and non-subscriber reception of MBMS services. Furthermore, shared content distribution is enabled via shared eMBMS networks (SEN) and the content provider can determine the method of content delivery, be it unicast or multicast. For streaming real-time video, fast and efficient resource allocation is necessary. Real-time video is expected to make use of MBMS operation On-Demand (MooD). For MBMS resource allocation at the MAC-layer, integer linear programming (ILP) can be used to achieve an optimal resource allocation among multiple video streams. Yet ILP is known to be NP-hard. We observe that for resource allocation at the MAC-layer, where multiple MAC allocation periods are required for the complete transmission of a video frame, a gradient-based resource allocation approach can achieve similar performance to that of ILP. Unlike ILP, in terms of computational complexity, our proposed gradient-based approach runs in P-time. For the MBMS services, we present a mobile TV system where the advertisers sponsor the TV service. We first study how the impact of viewership of a TV station and its associated bandwidth affects each advertiser’s valuation. By using mechanism design, we design a truthful voting mechanism to accurately capture each viewer’s current TV channel they are watching. The bandwidth allocated to each TV station is dependent on the current resource demands of the streaming videos and the viewership statistics. Based on the projected viewership and bandwidth allocated to each TV station, we design a truthful auction to allocate each advertisement slot to the set of advertisers interested in broadcasting their advertisements and consequently sponsoring said MBMS service. Finally, for commercial D2D services, we observe that SPs most likely have underutilized spectrum they are looking to monetize. We investigate how commercial D2D services, which can be limited to sub-sectors, can make use of SP controlled underutilized spectrum. The under-utilized spectrum allocation problem is formulated as an SP-controlled gap allocation problem; gaps are used by commercial D2D services. As D2D has a limited range, the gaps can be allocated to multiple D2D stations (UEs transmitting D2D services) within a sector. Based on the channel conditions of each D2D station, the associated bandwidth is auctioned off to advertisers who are interested in broadcasting their advertisements to the associated localized area. To perform the bandwidth allocation in a reasonable time, we derive a truthful auction which has a computational complexity in P-time and has a similar profit performance to the theoretically optimal VCG auction.