TY - GEN

T1 - DARP

T2 - IEEE INFOCOM 2011

AU - Zhang, Weiyi

AU - Bai, Shi

AU - Xue, Guoliang

AU - Tang, Jian

AU - Wang, Chonggang

PY - 2011/8/2

Y1 - 2011/8/2

N2 - The emerging WiMAX technology (IEEE 802.16) is the fourth generation standard for low-cost, high-speed and long-range wireless communications for a large variety of civilian and military applications. IEEE 802.16j has introduced the concept of mesh network model and a special type of node called Relay Station (RS) for traffic relay for Subscriber Stations (SSs). A WiMAX mesh network is able to provide larger wireless coverage, higher network capacity and Non-Line-Of-Sight (NLOS) communications. This paper studies a Distance-Aware Relay Placement (DARP) problem in WiMAX mesh networks, which considers a more realistic model that takes into account physical constraints such as channel capacity, signal strength and network topology, which were largely ignored in previous studies. The goal here is to deploy the minimum number of RSs to meet system requirements such as user data rate requests, signal quality and network topology. We divide the DARP problem into two sub-problems, LOwer-tier Relay Coverage (LORC) Problem and Minimum Upper-tier Steiner Tree (MUST) Problem. For LORC problem, we present two approximation algorithms based on independent set and hitting set, respectively. For MUST problem, an efficient approximation algorithm is provided and proved. Then, an approximation solution for DARP is proposed and proved which combines the solutions of the two sub-problems. We also present numerical results confirming the theoretical analysis of our schemes as the first solution for the DARP problem.

AB - The emerging WiMAX technology (IEEE 802.16) is the fourth generation standard for low-cost, high-speed and long-range wireless communications for a large variety of civilian and military applications. IEEE 802.16j has introduced the concept of mesh network model and a special type of node called Relay Station (RS) for traffic relay for Subscriber Stations (SSs). A WiMAX mesh network is able to provide larger wireless coverage, higher network capacity and Non-Line-Of-Sight (NLOS) communications. This paper studies a Distance-Aware Relay Placement (DARP) problem in WiMAX mesh networks, which considers a more realistic model that takes into account physical constraints such as channel capacity, signal strength and network topology, which were largely ignored in previous studies. The goal here is to deploy the minimum number of RSs to meet system requirements such as user data rate requests, signal quality and network topology. We divide the DARP problem into two sub-problems, LOwer-tier Relay Coverage (LORC) Problem and Minimum Upper-tier Steiner Tree (MUST) Problem. For LORC problem, we present two approximation algorithms based on independent set and hitting set, respectively. For MUST problem, an efficient approximation algorithm is provided and proved. Then, an approximation solution for DARP is proposed and proved which combines the solutions of the two sub-problems. We also present numerical results confirming the theoretical analysis of our schemes as the first solution for the DARP problem.

KW - WiMAX mesh network

KW - approximation algorithm

KW - hitting set

KW - independent set

KW - relay station placement

UR - http://www.scopus.com/inward/record.url?scp=79960867564&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=79960867564&partnerID=8YFLogxK

U2 - 10.1109/INFCOM.2011.5935014

DO - 10.1109/INFCOM.2011.5935014

M3 - Conference contribution

AN - SCOPUS:79960867564

SN - 9781424499212

T3 - Proceedings - IEEE INFOCOM

SP - 2060

EP - 2068

BT - 2011 Proceedings IEEE INFOCOM

Y2 - 10 April 2011 through 15 April 2011

ER -