在第四代行動網路中以中繼點協助下行廣播服務之資源分配機制

Resource Allocation Mechanisms for Relay-Aided Downlink Broadcast Service in 4G Networks

林政賢(Cheng-Hsien Lin)

指導教授 ： 黃仁竑

國立中正大學/工學院/資訊工程學系/博士(2012年)

摘要

無資料

關鍵字

廣播 ； 接收點數量最大化 ； 資源分配 ； 頻譜資源再利用 ； 無線中繼點網路

並列摘要

In 4G networks, such as LTE-Advanced and 802.16m WiMAX-based wireless networks, the downlink broadcast service is a crucial application. Once a broadcast session is triggered, the network needs to decide not only the transmission paths but the amount of resource that should be reserved for the transmission. Since the resource is scarce and must be shared among multiple network components, it is necessary to utilize the radio resource efficiently for the downlink broadcast service. In this dissertation, we studied two kinds of resource allocation problems in wireless relay networks. The first one is the broadcast recipient maximization (BRM) problem, where a set of recipients (i.e., the mobile stations (MSs)) wishes to receive a multimedia stream, and a fix amount of resource (called the resource budget) is reserved for the transmission of the multimedia stream. A sender (i.e., the base station (BS) or a relay station (RS)) needs sufficient resource in response to the channel condition and successfully transits the streaming data to a specified receiver (i.e., an RS or MS). Due to the broadcast nature of the wireless medium, other nodes having better channel condition than the receiver could also receive the streaming data. Given the channel condition of entire network, the task of BRM is to dispatch the resource budget to the BS and a set of cherry picked RSs such that they can serve as many recipients as possible. The major challenge is that allocating different amounts of resources to the BS and RSs lead to different network topologies. Existing works simply studied BRM over single-level relay networks, and provided solutions that are either inflexible or limited to the pre-defined network topology. The observation motivates us to formalize BRM for the multi-level relay networks and show that the problem is NP-complete. Then a utility-based resource allocation mechanism with a computation reduction (CR) mechanism is presented to resolve the problem for multi-level relay networks. We also present a theoretical result in which the performance of proposed mechanism is bounded by 1/2(1 - 1/e) of the optimal solution. The performance evaluation via a series of simulations shows that the proposed mechanism can serve more recipients than existing methods and the CR mechanism can reduce the running time significantly.
In the second problem, the principal objective is to serve all the designated MSs while minimizing the total amount of allocated resource. We formulate the resource allocation problem as an integer linear programming (ILP) model, which could be solved by a polynomial-time solution called the Resource Diminishing Principle (RDP). However, RDP is likely to allocate more resource than the actual requirement of a sender, thus, an auxiliary rule is proposed to be integrated into RDP (called Enhanced RDP, E-RDP) to improve the overall performance. Theoretical analysis is derived to show that E-RDP is in polynomial time and its result is bounded by HN of the optimal solution. Additionally, we further take the spatial reuse issue into account, and build a new ILP model to represent the Joint Spatial Reuse and Resource Allocation (JSRA) problem. Due to the highly computational complexity of JSRA, we proposed a two-phase solution. More specifically, E-RDP is exploited in the first phase to construct transmission paths connecting the BS and all the MSs and decide the amount of required resource for the BS and the selected RSs. Next, the max-coloring (MXC) algorithm solves the spatial reuse problem by organizing the selected RSs into a set of broadcast groups and assigning a disjoint set of resource to every group. The overall resource utilization can be boosted via the same set of resource reused by the RSs arranged in identical group since they can broadcast data concurrently without causing mutual interference. The performance of proposed solution is evaluated through several sets of simulations. The results show that the combination of E-RDP and MXC can improve the overall performance up to 28%. On the other hand, we noticed that MXC could also be integrated into existing allocation algorithms to improve the overall performance. However, their performance is not as good as that of the combination of E-RDP and MXC. This discovery indicates that the allocation algorithm affects the effect of spatial reuse. The rationale is that the allocation algorithm either tends to overestimates the resource requirement for the selected RSs or picks out the RSs which interrupt other RSs’ transmissions with high possibility.
The contributions of this dissertation are as follows. First, we define a problem model for BRM over multi-level relay networks and propose an efficient allocation mechanism with worst-case performance guarantee for BRM. Next, we investigate the optimization problem that addresses the spatial reuse and resource allocation simultaneously. We build an ILP model for JSRA and show that the overall performance definitely can be improved by the combination of E-RDP and MXC.

並列關鍵字

Broadcast ； recipient maximization ； resource allocation ； spatial reuse ； wireless relay networks

參考文獻

[31] M.-I. Hsieh, E. H. Wu, and M. F. Tsai, “FasterDSP: a faster approximation algorithm for directed Steiner tree problem,” Journal of Information Science and Engineering, vol. 22, no. 6, pp. 1409–1425, 2006.

[1] H. Schwarz, D. Marpe, and T. Wiegand, “Overview of the scalable video coding extension of the H.264/AVC Standard, ” IEEE Transactions on Circuits and Systems for Video Technology, vol. 17, no. 9, pp.1103–1120, 2007.

[5] J. She, F. Hou, P.-H. Ho, and L.-L. Xie, “IPTV over WiMAX: key success factors, challenges, and solutions,” IEEE Communications Magazine, vol. 45, no. 8, pp. 87 – 93, 2007.

[6] O. Oyman, J. Foerster, Y.-J. Tcha, and S.-C. Lee, “Toward enhanced mobile video services over WiMAX and LTE,” IEEE Communications Magazine, vol. 48, no. 8, pp. 68–76, 2010.

[9] Park K, Kang CG, Chang D, Song S, Ahn J, Ihm J. Relay-enhanced cellular performance of OFDMA TDD system for mobile wireless broadband services. Proceedings of IEEE International Conference on Computer Communications and Networks, pp. 430–435, 2007.