Name
Abstract | ||
|---|---|---|
In this paper, we formalize a general Frequency Domain Packet Scheduling (FDPS) problem for 3GPP LTE Downlink (DL). The DL FDPS problem incorporates the SingleUser Multiple Input Multiple Output (SU-MIMO) technique, and can express various scheduling policies, including the Proportional-Fair metric, the MaxWeight scheduling, etc. For LTE DL SU-MIMO, the constraint of selecting only one MIMO mode (transmit diversity or spatial multiplexing) per user in each transmission time interval (TTI) increases the hardness of the FDPS problem. We prove the problem is MAX SNP-hard, which implies approximation algorithms with constant approximation ratios are the best we can expect. Subsequently, we propose an approximation algorithm of polynomial runtime. The solution is based on a greedy method for maximizing a non-decreasing submodular function over a matroid. The algorithm can solve the general DL FDPS problem with an approximation ratio of 4. We implement the proposed algorithm and compare its performance with other well-known schedulers. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1109/TWC.2013.022113.120678 | IEEE Transactions on Wireless Communications |
Keywords | Field | DocType |
optimisation,matroid,dl,downlink (dl),su-mimo,scheduling,constant approximation ratio algorithm,nondecreasing submodular function,3gpp lte downlink,frequency domain packet scheduling,max snp-hard problem,space division multiplexing,submodular function,singleuser multiple input multiple output technique,optimization algorithm,polynomial approximation,approximation ratio,frequency domain packet scheduling (fdps),computational complexity,fdps,mimo communication,greedy algorithms,3g mobile communication,polynomial runtime,transmission time interval,long term evolution (lte),long term evolution,tti,maxweight scheduling policy,proportional-fair metric,spatial multiplexing,greedy method,transmit diversity,mimo,frequency domain analysis,approximation algorithms,algorithm design and analysis,downlink | Approximation algorithm,Mathematical optimization,Scheduling (computing),Transmission Time Interval,MIMO,Submodular set function,Greedy algorithm,Real-time computing,Mathematics,Spatial multiplexing,Transmit diversity | Journal |
Volume | Issue | ISSN |
12 | 4 | 1536-1276 |
Citations | PageRank | References |
4 | 0.40 | 0 |
Authors | ||
5 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Yinsheng Xu | 1 | 30 | 2.76 |
| Hongkun Yang | 2 | 24 | 1.46 |
| Fengyuan Ren | 3 | 931 | 83.57 |
| Chuang Lin | 4 | 3040 | 390.74 |
| Xuemin Shen | 5 | 15389 | 928.67 |