Link tải luận văn miễn phí cho ae Kết Nối
Computational Analysis and Efficient Algorithms for Micro and Macro OFDMA Downlink Scheduling
Abstract—Orthogonal frequency-division multiple access
(OFDMA) is one of the most important modulation and access
methods for the future mobile networks. Before transmitting a
frame on the downlink, an OFDMA base station has to invoke an
algorithm that determines which of the pending packets will be
transmitted, what modulation should be used for each of them,
and how to construct the complex OFDMA frame matrix as a
collection of rectangles that fit into a single matrix with fixed
dimensions. We propose efficient algorithms, with performance
guarantee, that solve this intricate OFDMA scheduling problem
by breaking it down into two subproblems, referred to as macro
and micro scheduling. We analyze the computational complexity
of these subproblems and develop efficient algorithms for solving
them.
Index Terms—Orthogonal frequency-division multiple access
(OFDMA), scheduling, wireless.
I. INTRODUCTION
O RTHOGONAL frequency-division multiple access (OFDMA) is one of the most important modulation and
multiple access methods for the future mobile networks. It is
an extension of orthogonal frequency-division multiplexing
(OFDM), which is today the modulation of choice for nonmobile wireless access systems such as IEEE 802.11 (WiFi)
and IEEE 802.16 (WiMax). OFDM divides a single frequency
band into dozens of subcarriers for parallel transmissions by
the same user. This division increases the tolerance to noise
and multipath effects while enabling more efficient use of
bandwidth allocation. OFDMA extends OFDM by dividing the
original band into many subchannels, each comprising a group
of orthogonal carriers. Various modulations and forward error
correction (FEC) techniques are used for each subchannel in
order to provide improved coverage and throughput.
Unlike OFDM, OFDMA has many intricate constraints on its
frame structure. The structure of an OFDMA downlink frame
is depicted in Fig. 1. The frame can be viewed as a two-dimensional matrix, with the -axis indicating the number of subchannels, each consisting of several orthogonal and not necessarily
adjacent frequencies, and the -axis indicating the time. The
frame starts with a frame control header, which contains information about the code rate, modulation level, and the length of
the downlink (DL) and uplink (UL) maps. The data messages
(PDUs) are transmitted in multiple bursts. There are seven bursts
Manuscript received December 25, 2007; revised November 20, 2008, and
March 23, 2009; approved by IEEE/ACM TRANSACTIONS ON NETWORKING
Editor S. Shakkottai. First published September 15, 2009; current phiên bản published February 18, 2010.
The authors are with the Department of Computer Science, Technion—Israel
Institute of Technology, Haifa 32000, Israel (e-mail: [email protected]).
Digital Object Identifier 10.1109/TNET.2009.2022937
Fig. 1. The structure of an OFDMA downlink frame.
shown in Fig. 1. Each burst is transmitted by the base station
using a specific combination of modulation technique, code rate,
and error-correcting codes. Such a combination is referred to
as PHY-profile. Due to OFDMA-related constraints, each data
burst must be allocated a rectangular region within the frame. A
burst may contain one or more PDUs destined for one or more
receivers. To ensure correct decoding of the received signals,
certain PHY-profile information about every burst is required.
This information is included as overhead in the DL burst map.
The DL and UL maps are transmitted using a predetermined and
robust PHY-profile.
This paper studies combinational aspects of scheduling on an
802.16/WiMax downlink OFDMA channel. Before transmitting
a downstream frame, typically once every few milliseconds, the
base station has to invoke a scheduling algorithm that will generate the frame matrix as shown in Fig. 1. To this end, the scheduler needs to address the following decision problems.
• To decide which PHY-profile will be used for each PDU.
There are several dozen potential profiles, each with its
own bandwidth requirement and robustness against transmission errors. It is not possible to use all profiles in one
frame. Moreover, each profile introduces a fixed significant
overhead in the DL map field of the frame, and therefore,
because of throughput considerations, the scheduler should
try to minimize the number of profiles accommodated in
every frame.
• To determine which PDU will be transmitted in the next
frame. This decision has to take into account many factors, such as: a) quality of service (QoS), since some of
the PDUs have a guaranteed upper bound on their maximum delay; b) total throughput maximization, since transmission to some of the hosts is difficult and requires more
bandwidth for reliable delivery, and c) fairness.
Fig. 2. The two approaches studied in this paper: (a) the first approach and (b)
the second approach.
• To decide where exactly in the frame every burst will be
located. Here there are also several constraints, some of
which are: a) power boosting, namely, the ability of the
base station to increase the transmission power used for
some burst while decreasing the power used for other
bursts transmitted at the same time on different subchannels; and b) efficiency, since the requirement that every
PHY-profile will be represented as a rectangle in the frame
matrix may leave some unused space in each rectangle.
There are two kinds of difficulties associated with addressing
these problems. The first is that a solution for each problem depends on the solutions for the other two. This leads to a circular dependency that should be broken. The second difficulty is
that, as shown later, each of these decision problems is NP-hard,
which means that even if the circular dependency is broken,
finding an optimal scheduling algorithm is not possible under
standard assumptions.
In this paper, we address the OFDMA scheduling problem
in two approaches. In the first approach (Sections IV and V),
we assume that the base station determines in advance the
PHY-profile to be used for each PDU and the profit (utility)
gained from transmitting this PDU using its selected PHY-profile. Then, there are two phases. In the first phase, referred
to as macro scheduling, the base station determines which of
the PDUs will actually be selected for transmission. In the
second phase, referred to as micro scheduling, the scheduler
determines how to build the OFDMA matrix from the selected
PDUs. In the second approach, we extend the macro scheduler
such that it also determines the PHY-profile for each PDU. This
is referred to as extended macro scheduling. Fig. 2 summarizes
these two approaches.
The assignment of profit (utility) to PDUs, which is based
on various considerations such as QoS, throughput maximization, fairness, and channel state information, is beyond the scope
of this paper. We address this issue in [5] in the context of
uplink transmission, and similar ideas can be implemented on
the downlink as well. In what follows, we give some examples for the profit assignment considerations discussed in [5].
A delay-sensitive (VoIP) packet is assigned a high profit when
it is received by the scheduler. This priority is reduced during
the time the packet is delayed before transmission. In contrast,
data packets, which are not so much sensitive to delay, are assigned a lower profit, and their profit is only slightly affected by
the time they wait for transmission. A packet whose intended
channel is known to be good is assigned a higher profit than a
similar packet whose intended channel is not as good. A packet
protected by an automatic repeat request protocol is assigned a
higher profit than a nonprotected packet when the two are supposed to be transmitted over a bad channel.
The main contributions of this paper are as follows.
• Breaking the OFDMA scheduling problem into two more
tractable problems, referred to as macro scheduling and
micro scheduling.
• Analyzing the computational complexity of the macro and
micro scheduling problems and providing algorithms with
the best performance guarantee for these problems.
• Developing efficient and practical algorithms for these
NP-hard scheduling problems. Specifically, we provide an
optimal macro scheduling problem and an algorithm with
only 2.5% overhead for the micro scheduling problem.
• Introducing a new concept in which the transmission profile of a PDU is determined not only by the channel condition of the intended receiver but also on the entire system
conditions. To this end, we extend the macro scheduling
problem to include the selection of transmission parameters for each PDU and provide an efficient algorithm for
this extended macro scheduling problem. This algorithm
has the best possible approximation guarantee up to an arbitrary small constant. It provides a significant improvement over the algorithm for the macro scheduling problem,
at the cost of higher running time.
The rest of this paper is organized as follows. In Section II,
we discuss related work. In Section III, we divide the OFDMA
scheduling problem into macro and micro scheduling subproblems, and discuss their computational complexity. In
Section IV, we present efficient algorithms for the macro
scheduling subproblem, and in Section V, we present such
algorithms for the micro scheduling subproblem. Section VI
presents an extension to the macro scheduling problem, which
allows the base station to select a PHY-profile for every PDU
as a part of the scheduling process. This extension is shown
to significantly improve the performance of the scheduler.
Section VII presents an approach for achieving global optimization using the previous algorithms. Section VIII presents a
simulation study, and Section IX concludes this paper.
II. RELATED WORK
While much work has been done on scheduling in wireless
networks, only a few papers address resource allocation in
OFDMA channels. In [2], some variations of the micro scheduling problem are addressed. In these variations, the input
consists of bursts and their sizes. The bursts have priorities and
the objective is to find an efficient allocation with accordance
to these priorities. The main differences between [2] and our
paper are that a) we analyze the computational complexity of
the micro scheduling problem and propose also approximation
algorithms while [2] presents only heuristics; b) we address
not only the micro scheduling problem but also the macro
scheduling problem and the combination of the two; and c) we
consider a more general case, where profit is assigned to each
PDU and not to each burst (a collection of PDUs).
APPENDIX IV
PROOF OF THEOREM 6
We first present the well-known NP-hard Maximum Coverage problem [6].
Instance: A number and a collection of sets
, where .
Objective: Find a subset of sets, such that
and the number of covered elements is maximized.
We now show a reduction from Maximum Coverage to E-MaSP.
Each item in the Maximum Coverage instance is transformed
into a PDU. Each set is transformed into a PHY-profile. For
an item and a set , if , then the profit and size of
the assignment of the corresponding PDU to the corresponding
PHY-profile are one and zero, respectively. If , the profit
and size are zero and , respectively. In addition, the overhead
for every PHY-profile is set to one, and the frame size is set
to .
It is clear that at most PHY-profiles can be scheduled in
the next frame. For the scheduled PHY-profiles, it is clear that
the total profit is not higher than the number of PDUs that can
be assigned to the selected PHY-profiles. Therefore, a schedule
that gains profit of is translated into a maximum coverage solution whose size is that covers at least items. This proves
that an optimal schedule gains no more than optimal maximum
coverage.
On the other hand, a maximum coverage solution of size
that covers elements can be transformed into a schedule
whose size is and that schedules PDUs. This is done by
choosing the corresponding PHY-profiles and assigning a (covered) PDU to one of them. Therefore, an optimal schedule gains
as much as the optimal maximum coverage.
Since an optimal solution for maximum coverage can be
translated (in polynomial time) into an optimal solution for the
specific E-MaSP instance and vice versa, then a) the fact that
Maximum Coverage is NP-hard implies that E-MaSP is also
NP-hard; and b) the fact that Maximum Coverage cannot be
approximated within a factor smaller than 1 , under standard
assumptions [14],3 implies that E-MaSP also cannot be approximated within the same factor.
REFERENCES
[1] A. Azgin and M. Krunz, “Scheduling in wireless cellular networks
under probabilistic channel information,” in Proc. ICCCN, Dallas, TX,
2003, pp. 89–94.
[2] Y. Ben-Shimol, I. Kitroser, and Y. Dinitz, “Two-dimensional mapping
for wireless OFDMA systems,” IEEE Trans. Broadcast., vol. 52, no. 3,
pp. 388–396, Sep. 2006.
[3] C. Chekuri and S. Khanna, “A polynomial time approximation scheme
for the multiple knapsack problem,” SIAM J. Comput., vol. 35, no. 3,
pp. 713–728, 2005.
[4] R. Cohen and L. Katzir, “Computational analysis and efficient algorithms for micro and macro OFDMA scheduling,” Technion—Israel
Inst. of Technol., Tech. Rep. CS-2007–02, 2007.
[5] R. Cohen and L. Katzir, “A generic quantitative approach to the scheduling of synchronous packets in a shared uplink wireless channel,”
IEEE/ACM Trans. Netw., vol. 15, no. 4, pp. 932–943, Aug. 2007.
[6] R. Cohen and L. Katzir, “The generalized maximum coverage
problem,” Inf. Process. Lett., vol. 108, no. 1, pp. 15–22, 2008.
3 , namely, that not all problems in NP can
be solved in for every constant
[7] R. Cohen, L. Katzir, and D. Raz, “An efficient approximation for the
generalized assignment problem,” Inf. Process. Lett., vol. 100, no. 4,
pp. 162–166, 2006.
[8] M. R. Garey and D. S. Johnson, Computers and Intractability; A Guide
to the Theory of NP-Completeness. San Francisco, CA: Freeman,
1979.
[9] A. J. Goldsmith and S. G. Chua, “Variable-rate variable-power
MQAM for fading channel,” IEEE Trans. Commun., vol. 45, no. 10,
pp. 1218–1230, Oct. 1997.
[10] , D. S. Hochbaum, Ed., Approximation Algorithms for NP-Hard Problems. Boston, MA: PWS, 1997.
[11] Local and Metropolitan Area Networks—Part 16: Air Interface for
Fixed Broadband Wireless Access Systems, IEEE Std. 802.16-2004.
[12] A. Israeli, D. Rawitz, and O. Sharon, “On the complexity of sequential
rectangle placement in IEEE 802.16/WiMax systems,” in Proc. ESA,
Perth, Australia, 2007, pp. 570–581.
[13] H. Kellerer, U. Pferschy, and D. Pisinger, Knapsack Problems. New
York: Springer, 2004.
[14] S. Khuller, A. Moss, and J. Naor, “The budgeted maximum coverage
problem,” Inf. Process. Lett., vol. 70, no. 1, pp. 39–45, 1999.
[15] D. Kivanc, G. Li, and H. Liu, “Computationally efficient bandwidth
allocation and power control for OFDMA,” IEEE Trans. Wireless
Commun., vol. 2, no. 6, pp. 1150–1158, Nov. 2003.
[16] S. Lu, V. Bharghavan, and R. Srikant, “Fair scheduling in wireless
packet networks,” IEEE/ACM Trans. Netw., vol. 7, no. 4, pp. 473–489,
Aug. 1999.
[17] S. Nanda, K. Balachandran, and S. Kumar, “Adaptation techniques in
wireless packet data services,” IEEE Commun. Mag., vol. 38, no. 1, pp.
54–64, Jan. 2000.
[18] S. Shakkottai and R. Srikant, “Scheduling real-time traffic with deadlines over a wireless channel,” Wireless Netw. J., vol. 8, no. 1, pp.
13–26, Jan. 2002.
[19] M. Shreedhar and G. Varghese, “Efficient fair queueing using deficit
round-robin,” IEEE/ACM Trans. Netw., vol. 4, no. 3, pp. 375–385, Jun.
1996.
[20] G. Song and Y. Li, “Cross-layer optimization for OFDM wireless networks, Part I: Theoretical framework,” IEEE Trans. Wireless Commun.,
vol. 4, no. 2, pp. 614–624, Mar. 2005.
[21] D. Tse and S. Hanly, “Multiaccess fading channels, Part I: Polymatroid
structure, optimal resource allocation and throughput capacities,” IEEE
Trans. Inf. Theory, vol. 44, no. 7, pp. 2796–2815, Nov. 1998.
[22] P. Viswanath, D. Tse, and R. Laroia, “Opportunistic beamforming
using dumb antennas,” IEEE Trans. Inf. Theory, vol. 48, no. 6, pp.
1277–1294, Jun. 2002.
[23] I. Wong, Z. Shen, J. Andrews, and B. L. Evans, “A low complexity
algorithm for proportional resource allocation in OFDMA systems,” in
Proc. IEEE Int. Signal Process. Syst. Workshop, Austin, TX, Oct. 2004,
pp. 1–6.
Reuven Cohen (M’93–SM’99) received the B.Sc.,
M.Sc., and Ph.D. degrees in computer science from
the Technion—Israel Institute of Technology, Haifa,
completing his Ph.D. studies in 1991.
From 1991 to 1993, he was with the IBM T. J.
Watson Research Center, Yorktown Heights, NY,
working on protocols for high-speed networks. Since
1993, he has been a Professor in the Department of
Computer Science at the Technion. He has also been
a Consultant for numerous companies, mainly in the
context of protocols and architectures for broadband
access networks.
Dr. Cohen has served as an Editor of the IEEE/ACM TRANSACTIONS ON
NETWORKING and the ACM/Kluwer Journal on Wireless Networks. He heads
the Israeli Chapter of the IEEE Communications Society.
Liran Katzir received the B.A., M.A., and Ph.D. degrees in computer science from the Technion—Israel
Institute of Technology, Haifa, in 2001, 2005, and
2008, respectively.
His Ph.D. dissertation was about scheduling in advanced wireless networks. He is now a Member of the
Networking Research Group in the Technion’s Computer Science Department, working on technologies
for the fourth-generation cellular network.
Do Drive thay đổi chính sách, nên một số link cũ yêu cầu duyệt download. các bạn chỉ cần làm theo hướng dẫn.
Password giải nén nếu cần: ket-noi.com | Bấm trực tiếp vào Link để tải:
Computational Analysis and Efficient Algorithms for Micro and Macro OFDMA Downlink Scheduling
Abstract—Orthogonal frequency-division multiple access
(OFDMA) is one of the most important modulation and access
methods for the future mobile networks. Before transmitting a
frame on the downlink, an OFDMA base station has to invoke an
algorithm that determines which of the pending packets will be
transmitted, what modulation should be used for each of them,
and how to construct the complex OFDMA frame matrix as a
collection of rectangles that fit into a single matrix with fixed
dimensions. We propose efficient algorithms, with performance
guarantee, that solve this intricate OFDMA scheduling problem
by breaking it down into two subproblems, referred to as macro
and micro scheduling. We analyze the computational complexity
of these subproblems and develop efficient algorithms for solving
them.
Index Terms—Orthogonal frequency-division multiple access
(OFDMA), scheduling, wireless.
I. INTRODUCTION
O RTHOGONAL frequency-division multiple access (OFDMA) is one of the most important modulation and
multiple access methods for the future mobile networks. It is
an extension of orthogonal frequency-division multiplexing
(OFDM), which is today the modulation of choice for nonmobile wireless access systems such as IEEE 802.11 (WiFi)
and IEEE 802.16 (WiMax). OFDM divides a single frequency
band into dozens of subcarriers for parallel transmissions by
the same user. This division increases the tolerance to noise
and multipath effects while enabling more efficient use of
bandwidth allocation. OFDMA extends OFDM by dividing the
original band into many subchannels, each comprising a group
of orthogonal carriers. Various modulations and forward error
correction (FEC) techniques are used for each subchannel in
order to provide improved coverage and throughput.
Unlike OFDM, OFDMA has many intricate constraints on its
frame structure. The structure of an OFDMA downlink frame
is depicted in Fig. 1. The frame can be viewed as a two-dimensional matrix, with the -axis indicating the number of subchannels, each consisting of several orthogonal and not necessarily
adjacent frequencies, and the -axis indicating the time. The
frame starts with a frame control header, which contains information about the code rate, modulation level, and the length of
the downlink (DL) and uplink (UL) maps. The data messages
(PDUs) are transmitted in multiple bursts. There are seven bursts
Manuscript received December 25, 2007; revised November 20, 2008, and
March 23, 2009; approved by IEEE/ACM TRANSACTIONS ON NETWORKING
Editor S. Shakkottai. First published September 15, 2009; current phiên bản published February 18, 2010.
The authors are with the Department of Computer Science, Technion—Israel
Institute of Technology, Haifa 32000, Israel (e-mail: [email protected]).
Digital Object Identifier 10.1109/TNET.2009.2022937
Fig. 1. The structure of an OFDMA downlink frame.
shown in Fig. 1. Each burst is transmitted by the base station
using a specific combination of modulation technique, code rate,
and error-correcting codes. Such a combination is referred to
as PHY-profile. Due to OFDMA-related constraints, each data
burst must be allocated a rectangular region within the frame. A
burst may contain one or more PDUs destined for one or more
receivers. To ensure correct decoding of the received signals,
certain PHY-profile information about every burst is required.
This information is included as overhead in the DL burst map.
The DL and UL maps are transmitted using a predetermined and
robust PHY-profile.
This paper studies combinational aspects of scheduling on an
802.16/WiMax downlink OFDMA channel. Before transmitting
a downstream frame, typically once every few milliseconds, the
base station has to invoke a scheduling algorithm that will generate the frame matrix as shown in Fig. 1. To this end, the scheduler needs to address the following decision problems.
• To decide which PHY-profile will be used for each PDU.
There are several dozen potential profiles, each with its
own bandwidth requirement and robustness against transmission errors. It is not possible to use all profiles in one
frame. Moreover, each profile introduces a fixed significant
overhead in the DL map field of the frame, and therefore,
because of throughput considerations, the scheduler should
try to minimize the number of profiles accommodated in
every frame.
• To determine which PDU will be transmitted in the next
frame. This decision has to take into account many factors, such as: a) quality of service (QoS), since some of
the PDUs have a guaranteed upper bound on their maximum delay; b) total throughput maximization, since transmission to some of the hosts is difficult and requires more
bandwidth for reliable delivery, and c) fairness.
Fig. 2. The two approaches studied in this paper: (a) the first approach and (b)
the second approach.
• To decide where exactly in the frame every burst will be
located. Here there are also several constraints, some of
which are: a) power boosting, namely, the ability of the
base station to increase the transmission power used for
some burst while decreasing the power used for other
bursts transmitted at the same time on different subchannels; and b) efficiency, since the requirement that every
PHY-profile will be represented as a rectangle in the frame
matrix may leave some unused space in each rectangle.
There are two kinds of difficulties associated with addressing
these problems. The first is that a solution for each problem depends on the solutions for the other two. This leads to a circular dependency that should be broken. The second difficulty is
that, as shown later, each of these decision problems is NP-hard,
which means that even if the circular dependency is broken,
finding an optimal scheduling algorithm is not possible under
standard assumptions.
In this paper, we address the OFDMA scheduling problem
in two approaches. In the first approach (Sections IV and V),
we assume that the base station determines in advance the
PHY-profile to be used for each PDU and the profit (utility)
gained from transmitting this PDU using its selected PHY-profile. Then, there are two phases. In the first phase, referred
to as macro scheduling, the base station determines which of
the PDUs will actually be selected for transmission. In the
second phase, referred to as micro scheduling, the scheduler
determines how to build the OFDMA matrix from the selected
PDUs. In the second approach, we extend the macro scheduler
such that it also determines the PHY-profile for each PDU. This
is referred to as extended macro scheduling. Fig. 2 summarizes
these two approaches.
The assignment of profit (utility) to PDUs, which is based
on various considerations such as QoS, throughput maximization, fairness, and channel state information, is beyond the scope
of this paper. We address this issue in [5] in the context of
uplink transmission, and similar ideas can be implemented on
the downlink as well. In what follows, we give some examples for the profit assignment considerations discussed in [5].
A delay-sensitive (VoIP) packet is assigned a high profit when
it is received by the scheduler. This priority is reduced during
the time the packet is delayed before transmission. In contrast,
data packets, which are not so much sensitive to delay, are assigned a lower profit, and their profit is only slightly affected by
the time they wait for transmission. A packet whose intended
channel is known to be good is assigned a higher profit than a
similar packet whose intended channel is not as good. A packet
protected by an automatic repeat request protocol is assigned a
higher profit than a nonprotected packet when the two are supposed to be transmitted over a bad channel.
The main contributions of this paper are as follows.
• Breaking the OFDMA scheduling problem into two more
tractable problems, referred to as macro scheduling and
micro scheduling.
• Analyzing the computational complexity of the macro and
micro scheduling problems and providing algorithms with
the best performance guarantee for these problems.
• Developing efficient and practical algorithms for these
NP-hard scheduling problems. Specifically, we provide an
optimal macro scheduling problem and an algorithm with
only 2.5% overhead for the micro scheduling problem.
• Introducing a new concept in which the transmission profile of a PDU is determined not only by the channel condition of the intended receiver but also on the entire system
conditions. To this end, we extend the macro scheduling
problem to include the selection of transmission parameters for each PDU and provide an efficient algorithm for
this extended macro scheduling problem. This algorithm
has the best possible approximation guarantee up to an arbitrary small constant. It provides a significant improvement over the algorithm for the macro scheduling problem,
at the cost of higher running time.
The rest of this paper is organized as follows. In Section II,
we discuss related work. In Section III, we divide the OFDMA
scheduling problem into macro and micro scheduling subproblems, and discuss their computational complexity. In
Section IV, we present efficient algorithms for the macro
scheduling subproblem, and in Section V, we present such
algorithms for the micro scheduling subproblem. Section VI
presents an extension to the macro scheduling problem, which
allows the base station to select a PHY-profile for every PDU
as a part of the scheduling process. This extension is shown
to significantly improve the performance of the scheduler.
Section VII presents an approach for achieving global optimization using the previous algorithms. Section VIII presents a
simulation study, and Section IX concludes this paper.
II. RELATED WORK
While much work has been done on scheduling in wireless
networks, only a few papers address resource allocation in
OFDMA channels. In [2], some variations of the micro scheduling problem are addressed. In these variations, the input
consists of bursts and their sizes. The bursts have priorities and
the objective is to find an efficient allocation with accordance
to these priorities. The main differences between [2] and our
paper are that a) we analyze the computational complexity of
the micro scheduling problem and propose also approximation
algorithms while [2] presents only heuristics; b) we address
not only the micro scheduling problem but also the macro
scheduling problem and the combination of the two; and c) we
consider a more general case, where profit is assigned to each
PDU and not to each burst (a collection of PDUs).
APPENDIX IV
PROOF OF THEOREM 6
We first present the well-known NP-hard Maximum Coverage problem [6].
Instance: A number and a collection of sets
, where .
Objective: Find a subset of sets, such that
and the number of covered elements is maximized.
We now show a reduction from Maximum Coverage to E-MaSP.
Each item in the Maximum Coverage instance is transformed
into a PDU. Each set is transformed into a PHY-profile. For
an item and a set , if , then the profit and size of
the assignment of the corresponding PDU to the corresponding
PHY-profile are one and zero, respectively. If , the profit
and size are zero and , respectively. In addition, the overhead
for every PHY-profile is set to one, and the frame size is set
to .
It is clear that at most PHY-profiles can be scheduled in
the next frame. For the scheduled PHY-profiles, it is clear that
the total profit is not higher than the number of PDUs that can
be assigned to the selected PHY-profiles. Therefore, a schedule
that gains profit of is translated into a maximum coverage solution whose size is that covers at least items. This proves
that an optimal schedule gains no more than optimal maximum
coverage.
On the other hand, a maximum coverage solution of size
that covers elements can be transformed into a schedule
whose size is and that schedules PDUs. This is done by
choosing the corresponding PHY-profiles and assigning a (covered) PDU to one of them. Therefore, an optimal schedule gains
as much as the optimal maximum coverage.
Since an optimal solution for maximum coverage can be
translated (in polynomial time) into an optimal solution for the
specific E-MaSP instance and vice versa, then a) the fact that
Maximum Coverage is NP-hard implies that E-MaSP is also
NP-hard; and b) the fact that Maximum Coverage cannot be
approximated within a factor smaller than 1 , under standard
assumptions [14],3 implies that E-MaSP also cannot be approximated within the same factor.
REFERENCES
[1] A. Azgin and M. Krunz, “Scheduling in wireless cellular networks
under probabilistic channel information,” in Proc. ICCCN, Dallas, TX,
2003, pp. 89–94.
[2] Y. Ben-Shimol, I. Kitroser, and Y. Dinitz, “Two-dimensional mapping
for wireless OFDMA systems,” IEEE Trans. Broadcast., vol. 52, no. 3,
pp. 388–396, Sep. 2006.
[3] C. Chekuri and S. Khanna, “A polynomial time approximation scheme
for the multiple knapsack problem,” SIAM J. Comput., vol. 35, no. 3,
pp. 713–728, 2005.
[4] R. Cohen and L. Katzir, “Computational analysis and efficient algorithms for micro and macro OFDMA scheduling,” Technion—Israel
Inst. of Technol., Tech. Rep. CS-2007–02, 2007.
[5] R. Cohen and L. Katzir, “A generic quantitative approach to the scheduling of synchronous packets in a shared uplink wireless channel,”
IEEE/ACM Trans. Netw., vol. 15, no. 4, pp. 932–943, Aug. 2007.
[6] R. Cohen and L. Katzir, “The generalized maximum coverage
problem,” Inf. Process. Lett., vol. 108, no. 1, pp. 15–22, 2008.
3 , namely, that not all problems in NP can
be solved in for every constant
[7] R. Cohen, L. Katzir, and D. Raz, “An efficient approximation for the
generalized assignment problem,” Inf. Process. Lett., vol. 100, no. 4,
pp. 162–166, 2006.
[8] M. R. Garey and D. S. Johnson, Computers and Intractability; A Guide
to the Theory of NP-Completeness. San Francisco, CA: Freeman,
1979.
[9] A. J. Goldsmith and S. G. Chua, “Variable-rate variable-power
MQAM for fading channel,” IEEE Trans. Commun., vol. 45, no. 10,
pp. 1218–1230, Oct. 1997.
[10] , D. S. Hochbaum, Ed., Approximation Algorithms for NP-Hard Problems. Boston, MA: PWS, 1997.
[11] Local and Metropolitan Area Networks—Part 16: Air Interface for
Fixed Broadband Wireless Access Systems, IEEE Std. 802.16-2004.
[12] A. Israeli, D. Rawitz, and O. Sharon, “On the complexity of sequential
rectangle placement in IEEE 802.16/WiMax systems,” in Proc. ESA,
Perth, Australia, 2007, pp. 570–581.
[13] H. Kellerer, U. Pferschy, and D. Pisinger, Knapsack Problems. New
York: Springer, 2004.
[14] S. Khuller, A. Moss, and J. Naor, “The budgeted maximum coverage
problem,” Inf. Process. Lett., vol. 70, no. 1, pp. 39–45, 1999.
[15] D. Kivanc, G. Li, and H. Liu, “Computationally efficient bandwidth
allocation and power control for OFDMA,” IEEE Trans. Wireless
Commun., vol. 2, no. 6, pp. 1150–1158, Nov. 2003.
[16] S. Lu, V. Bharghavan, and R. Srikant, “Fair scheduling in wireless
packet networks,” IEEE/ACM Trans. Netw., vol. 7, no. 4, pp. 473–489,
Aug. 1999.
[17] S. Nanda, K. Balachandran, and S. Kumar, “Adaptation techniques in
wireless packet data services,” IEEE Commun. Mag., vol. 38, no. 1, pp.
54–64, Jan. 2000.
[18] S. Shakkottai and R. Srikant, “Scheduling real-time traffic with deadlines over a wireless channel,” Wireless Netw. J., vol. 8, no. 1, pp.
13–26, Jan. 2002.
[19] M. Shreedhar and G. Varghese, “Efficient fair queueing using deficit
round-robin,” IEEE/ACM Trans. Netw., vol. 4, no. 3, pp. 375–385, Jun.
1996.
[20] G. Song and Y. Li, “Cross-layer optimization for OFDM wireless networks, Part I: Theoretical framework,” IEEE Trans. Wireless Commun.,
vol. 4, no. 2, pp. 614–624, Mar. 2005.
[21] D. Tse and S. Hanly, “Multiaccess fading channels, Part I: Polymatroid
structure, optimal resource allocation and throughput capacities,” IEEE
Trans. Inf. Theory, vol. 44, no. 7, pp. 2796–2815, Nov. 1998.
[22] P. Viswanath, D. Tse, and R. Laroia, “Opportunistic beamforming
using dumb antennas,” IEEE Trans. Inf. Theory, vol. 48, no. 6, pp.
1277–1294, Jun. 2002.
[23] I. Wong, Z. Shen, J. Andrews, and B. L. Evans, “A low complexity
algorithm for proportional resource allocation in OFDMA systems,” in
Proc. IEEE Int. Signal Process. Syst. Workshop, Austin, TX, Oct. 2004,
pp. 1–6.
Reuven Cohen (M’93–SM’99) received the B.Sc.,
M.Sc., and Ph.D. degrees in computer science from
the Technion—Israel Institute of Technology, Haifa,
completing his Ph.D. studies in 1991.
From 1991 to 1993, he was with the IBM T. J.
Watson Research Center, Yorktown Heights, NY,
working on protocols for high-speed networks. Since
1993, he has been a Professor in the Department of
Computer Science at the Technion. He has also been
a Consultant for numerous companies, mainly in the
context of protocols and architectures for broadband
access networks.
Dr. Cohen has served as an Editor of the IEEE/ACM TRANSACTIONS ON
NETWORKING and the ACM/Kluwer Journal on Wireless Networks. He heads
the Israeli Chapter of the IEEE Communications Society.
Liran Katzir received the B.A., M.A., and Ph.D. degrees in computer science from the Technion—Israel
Institute of Technology, Haifa, in 2001, 2005, and
2008, respectively.
His Ph.D. dissertation was about scheduling in advanced wireless networks. He is now a Member of the
Networking Research Group in the Technion’s Computer Science Department, working on technologies
for the fourth-generation cellular network.
Do Drive thay đổi chính sách, nên một số link cũ yêu cầu duyệt download. các bạn chỉ cần làm theo hướng dẫn.
Password giải nén nếu cần: ket-noi.com | Bấm trực tiếp vào Link để tải:
You must be registered for see links