Minimum-Cost QoS-Constrained Deployment and Routing Policies for Wireless Relay Networks of Maximal Ratio Combining Capacities

Recently, broadband wireless networks have become greatly popular and among these, IEEE 802.16j, which is a developing standard, is attracting considerable interests. The concept of adopting relays, which is the main focus of 802.16j, has two major advantages. Firstly, relays can serve as inter-mediums between base stations (BSs) and mobile stations (MSs) to repeat signals on both directions for the purpose of coverage extensions. Secondly, cooperatively relaying techniques are exploited in 802.16j to achieve superior reliabilities of communications using gain combining approaches like maximal ratio combining (MRC).
In this thesis, we propose a solution for decisions on where and how many relays should be deployed in a design of 802.16j wireless network to minimize the total development cost. During the procedure, we derive a multicast tree routing algorithm to fulfill the QoS and throughput requirements on both down-link (DL) and up-link (UL) communications.
The solution approach is based on Lagrangean relaxation in conjunction with novel optimization-based heuristics. With the exceptional properties of Lagrangean relaxation we expect to efficiently and effectively solve this complicated optimization problem. Computational experiments will be conducted to evaluate the performance of the proposed algorithm.