以賽局理論為基礎的無線網路資源管理機制

Abstract

次世代無線廣域網路(WWAN)通訊標準，如IEEE制定的802.16 (WiMAX)和3GPP制定的LTE-Advanced標準，由於其承諾將達成由ITU-R所規畫的4G無線網路願境而在近期獲得眾多的關注。然而，在無線網路可用資源日趨虧乏的情況下，這些通訊標準採用了大量新技術以提升資源的使用效率。然而，在現實的各種限制下，這些新技術依然要面臨以有限的計算資源和處理時間內進行資源分配最佳化的挑戰。 無線網路裡的資源管理問題的困難點在於他們牽扯到參與者的自私行為與其之間的競爭關係。在無線網路的資源分配問題裡，由於資源有限，當有一參與者(如手機、平板和基地台等)取得較多資源時，其他參與者往往會失去部分資源。此特性使其問題自然的出現了競爭行為。當參與者受控或本身即為使用者時，我們可假定此類參與者為理性行為者，而理性行為者在競爭環境下往往會表現出自私的行為。此類行為和傳統處理資源分配問題的最佳化解法下假定所有參與者皆為了某共同目標而遵守系統指令相違背。若放任此類自私行為不管，傳統解法往往會面臨參與者行為不符預期且系統效能不彰的問題。近年來，將賽局理論應用於無線網路資源分配理論的相關研究日漸熱門。賽局理論是一套用來分析玩家之間的互動(如競爭行為)的數學理論工具。我們可以從賽局理論的角度來看待傳統的資源分配管理問題，並藉由賽局理論的分析和理論基礎提出嶄新的解決方案。此類方案應保持合理的效能、實作性，並能夠對自私行為進行有效的控管。 在本論文中，我們將探討異質網路、裝置對裝置通訊、以及群體廣播等最新的網路系統，將針對各個系統裡的資源管理問題，提出新穎的以賽局理論為基礎的方法論。我們所探討的系統都存在明顯的競爭環境，並在我們的分析中發現了有害的自私行為。因此，我們根據分析的結果和各個系統的特性，分別提出了可以有效管制自私行為的新穎解決方案。我們透過理論證明或模擬實驗的方式，驗證了這些解決方案在管制自私行為的同時，也保證了合理的系統效能和實作性。 在異質網路中，我們首先探討了微型基地台的涵蓋範圍問題，我們首先觀察到在此類問題中，微型基地台從自私使用者所收集到的資訊可能會有謊報而無法反映系統現況的問題。針對此類自私行為，我們提出了以投票機制為基礎的賽局機制設計，藉此確保自私使用者會選擇誠實回報他們所觀察到的系統狀況。接下來，我們分析在異質網路裡的微型基地台定價問題。我們證明了藉由最佳的差異化合約設計和微型基地台之間的搭配，我們可以有效地提升無線網路系統的服務品質，同時系統服務商的利潤也有顯著的提升。最後，我們探討頻帶集成的最佳規畫與設定問題。我們注意到在此類問題中，基地台一樣需要從使用者收集其心目中的服務質量需求，而自私的使用者一樣有可能會藉由謊報而獲得不正當的利益。針對此問題，我們提出了以拍賣機制為基礎的設計，並以理論證明了自私使用者在此機制下會誠實地回報他們的服務質量需求。 在裝置對裝置通訊系統中，我們觀察到此類系統的點對點傳輸特性讓使用者更容易謊報他們所觀察到的資訊。同時，我們也注意到此類系統的傳輸品質可以藉由簡單的資源交換機制獲得提升。從這兩點出發，我們提出了以交換機制為基礎的賽局機制設計。此設計的運算複雜度低，達到的資源分配結果滿足柏拉圖最適，同時也保證了使用者會誠實地向基地台回報他們所觀察到的資訊。 最後，在群體廣播系統裡，我們首先討論了一個較抽象的社會學習與網路外部性問題。我們提出了一個新的賽局模型：中國餐廳賽局以處理這個問題。藉由分析這個賽局，我們可以預期自私使用者在有網路外部性的網路裡的最佳決策。從這個賽局模型出發，我們探討了在可伸縮編碼群體廣播系統裡的使用者影片訂閱問題。我們認為此類問題其實是一個網路裡的決策問題，並可以使用我們的中國餐廳賽局來分析。以此為出發點，我們提出了一個多維馬爾可夫決策過程來描述此系統的長期效能演進。我們的分析顯示，當我們在系統套用最佳定價時，我們不只最大化系統服務商的利潤，同時也提升了整個系統的社會福利。

Next-generation wireless wide-area network (WWAN) standards, such as IEEE 802.16 and 3GPP LTE-Advanced, raised lots of attentions in these days since they are established for achieving the 4G standard requirements proposed by ITU-R, which illustrates a colorful vision for the future wireless communication. Nevertheless, the resource for wireless networking, such as spectrum, is very limited and difficult to expand. In order to fulfill this vision with limited resource, these new wireless standards introduce numerous advanced techniques to increase the resource utilization efficiency. Most challenges in these techniques can be transformed into resource allocation problems under the resource limitation constraints. The resource management problems in wireless networks are difficult since they involve complex competitions and selfish behaviors from participants in the wireless networks. An operation that increases the participant's allocated resource inevitably reduces the resource for other participants, which results in competitions. Additionally, when the participants are or controlled by real humans, we can fairly assume that these participants are rational and therefore selfish. The competition effect and selfishness of participants in wireless networks imposes an serious threat to all existing solutions which are based on traditional perspectives, which usually inherent an assumption that all participants faithfully follow the orders of the system for some global objective. In recent years, researchers discovered that game theory is suitable for analyzing the wireless networking systems, especially for resource management problems. Game theory is a mathematical tool applied to model and to analyze the outcome of interactions, such as competitions, among multiple decision-makers. It can help analyze and predict the selfish behaviors of participants in wireless networks. It also provides a series of tools to regulate those undesired selfish behaviors and eliminate the performance degradation from the competition effects. By introducing game-theoretic approaches, we can propose novel solutions that are efficient, practical, and robust to the selfish behaviors of participants in wireless networks. In this dissertation, we propose novel game-theoretic approaches to several resource management problems in the state-of-the-art wireless systems, which are heterogeneous networks, D2D communication, and multicasting system. Given the analysis based on game theory, we identify the potential threats from selfishness and propose novel solutions to each problem in order to address the selfish behaviors of participants while keeping reasonable efficiency and practicability. Extensive simulations are also executed for evaluating the performance of each proposed solutions.

In heterogeneous networks, we first study the femtocell coverage control problem. We first identify that the system information collected from them does not necessarily reflect the true status of the system due to the selfish nature of mobile stations. Thus, we design FEmtocell Virtual Election Rule (FEVER), a voting based mechanism that not only is proved to be truthful and has low implementation complexity, but also strikes a balance between efficiency and fairness to meet the different needs. Then, we study the femtocell service price problem in heterogeneous network. Femtocell technology can be used to improve service quality and increase profit by attracting customers. Meanwhile, differentiated contracts for different types of users also show great potential for profit increase. We show that by applying differentiated contracts in femtocell service. The profits of service providers can be significantly increased. Finally, we study the carrier aggregation mechanism in LTE-Advanced system. We observe that selfish users may untruthfully report their QoS requirements in order to manipulate the carrier activation and resource block allocation. Therefore, we propose a truthful auction with a greedy resource allocation algorithm in order to guarantee that all rational UEs truthfully report their QoS requirements. In D2D communication system, we observe that the ad-hoc characteristic of D2D communication poses the truth-telling issue into the system. Additionally, we find out that that the transmission quality in D2D communications can be significantly improved through a proper resource exchange. Based on this observation, we propose a Trader-assisted Resource Exchange (T-REX) mechanism, an exchange-based mechanism that converges in polynomial time and achieves Pareto optimal. We prove that all rational D2D pairs will truthfully report their information when the trader preference functions are properly designed. Finally, in the multicastins system, we first discuss the general social learning problem in a network with exteranlity effects. We propose a game-theoretic framework called Chinese restaurant game. Through analyzing the Chinese restaurant game, we derive the optimal strategy of each agent and provide a recursive method to achieve the optimal strategy. Based on this framework, we analyze the scalable video coding multicasting system, which is an effective solution for video streaming services in wireless networks. We observe that the requests from users in such a system in fact is a social decision making problem and can be formulated with Chinese restaurant game. We propose a stochastic framework based on Multi-dimensional Markov Decision Process (M-MDP) to evaluate the corresponding system efficiency. We show that the optimal pricing strategy, which maximizes the expected revenue of the service provider, also increases the social welfare of the system.