无线互联网 Handout04(续) OFDMA-TDMA Cellular 王晟 博士教授博导 2020年秋季无线互联网 1
OFDMA-TDMA Cellular 王晟 博士 教授 博导 无线互联网 Handout 04(续) 2020年秋季 无线互联网 1
NOTES ®这部分内容来自以下参考书： Bo Ji,Xiaojun Lin,and Ness B.Shroff Advances in Multi-Channel Resource Allocation:Throughput,Delay,and Complexity "synthesis lectures on communication networks",Morgan Claypool,2016 Chapter 2:Intra-Cell Scheduling 2020年秋季 2/62 无线互联网
NOTES 2020年秋季 2 / 62 无线互联网 这部分内容来自以下参考书: Bo Ji, Xiaojun Lin, and Ness B. Shroff Advances in Multi-Channel Resource Allocation: Throughput, Delay, and Complexity “synthesis lectures on communication networks”, Morgan & Claypool, 2016 Chapter 2: Intra-Cell Scheduling
CONTENT LTE/OFDM小区内信道调度问题 2 MaxWeight策略及直觉性改进 3 RFDO及其充分条件 4 TO及其充分条件 5 同时达到RFDO和TO的调度算法 6 小结与展望 2020年秋季 3/62 无线互联网
CONTENT 2020年秋季 3 / 62 无线互联网 1 2 3 4 LTE/OFDM 小区内信道调度问题 MaxWeight策略及直觉性改进 RFDO及其充分条件 TO及其充分条件 5 同时达到RFDO和TO的调度算法 6 小结与展望
LTE单小区下行通信 Hundreds of UEs UE1 PRBs Allocation Q UE2 PRB UEn Time LTE eNodeB Scheduling Cycle (a)LTE base-station (eNodeB) (b)PRBs allocation 四下行分组按用户分别缓存. 四基站：每个TT开始时，在用户之间分配PRB,以满足下行需求 ◆TTl:Transmission Time Interval..调度周期（短至1ms). ◆PRB:Physical Resource Blocks.最小资源单位(I2个子载波)， 四12个子载波看作一个“信道”，1个TTI看作一个“时隙” →调度问题可以定义为：每个时隙为用户UE分配信道. 2020年秋季 4/62 无线互联网
LTE单小区下行通信 2020年秋季 4 / 62 无线互联网 */53"$&-- 4$)&%6-*/( TDIFEVMJOH DZDMF " 13# DPOTJTUT PG DPOTFDVUJWF TVCDBSSJFST BOE JT UIF TNBMMFTU FMFNFOU PG SFTPVSDF BMMPDBUJPO BTTJHOFE CZ UIF CBTFTUBUJPO TDIFEVMFS "O FYBNQMF PG UIF 13#T BMMPDBUJPO JT JMMVTUSBUFE JO 'JH C Hundreds of UEs LTE eNodeB UE 1 UE 2 UE n Q1 Q2 Qn B -5& CBTFTUBUJPO F/PEF# PRBs Allocation PRB Time Scheduling Cycle Frequency C 13#T BMMPDBUJPO 'JHVSF " NPUJWBUJOH FYBNQMF UIF EPXOMJOL TDFOBSJP PG B TJOHMFDFMM -5& TZTUFN ɩF TDIFEVMJOH QSPCMFN IFSF JT UP EFDJEF XIJDI 13#T BSF BMMPDBUFE UP XIJDI VTFST JO FBDI TDIFEVMJOH DZDMF /PUF UIBU JO FBDI TDIFEVMJOH DZDMF B 13# JT UIF TNBMMFTU TDIFEVMJOH VOJU BOE DBO POMZ CF BMMPDBUFE UP POF VTFS CVU B VTFS DBO HFU NVMUJQMF 13#T BU UIF TBNF UJNF %VF UP GBEJOH BOE VTFS NPCJMJUZ UIF DIBOOFM DPOEJUJPO CFUXFFO UIF VTFS BOE UIF CBTFTUBUJPO DPVME CF UJNFWBSZJOH 'PS B HJWFO VTFS JU UZQJDBMMZ FYQFSJFODFT nBU GBEJOH PO UIF DIBOOFM PG FBDI JOEJWJEVBM 13# CVU BDSPTT 13#T UIF DIBOOFM DPOEJUJPOT BSF EJĊFSFOU EVF UP NVMUJQBUI GBEJOH ɩVT XIFO UIF PWFSBMM DIBOOFM DPOEJUJPO PG UIF VTFS JT HPPE JU XJMM TFF B MBSHFS OVNCFS PG 13#T JO HPPE DPOEJUJPOT )PXFWFS FWFO JG UIF PWFSBMM DIBOOFM DPOEJUJPO JT QPPS UIF VTFS XJMM TUJMM MJLFMZ TFF HPPE DIBOOFM DPOEJUJPOT PO B GFX 13#T )FODF UIJT DIBOOFM EJWFSTJUZ PĊFST B HSFBU PQQPSUVOJUZ PG EFTJHOJOH IJHIQFSGPSNBODF TDIFEVMJOH QPMJDJFT UIBU DBO BDIJFWF MPX EFMBZ XJUIPVU TBDSJmDJOH BOZ UISPVHIQVU 0O UIF PUIFS IBOE UIJT BMTP TVCTUBOUJBMMZ JODSFBTFT UIF EFTJHO TQBDF XIJDI NBLFT UIF TDIFEVMJOH QSPCMFN NVDI NPSF DIBMMFOHJOH *O BEEJUJPO UP UIJT NBKPS SFTFBSDI HPBM BOPUIFS TJHOJmDBOU DIBMMFOHF JO UIF -5& TZTUFN JT UIBU UIF TDIFEVMJOH DZDMFT BSF WFSZ TIPSU FH POF NJMMJTFDPOE BOE IVOESFET PG PSUIPHPOBM DIBOOFMT BOE IVOESFET PG VTFST OFFE UP CF TDIFEVMFE BU UIF TBNF UJNF DzFSFGPSF BT EJTDVTTFE JO $IBQUFS UIF HPBM PG UIF TDIFEVMJOH QSPCMFN JT UISFFGPME UP NBYJNJ[F UIF UISPVHIQVU UP NJOJNJ[F UIF BNPVOU PG UJNF UIBU BOZ QBDLFU TQFOET JO UIF CVąFS BU UIF CBTFTUBUJPO BOE UP FOTVSF UIBU UIF EFTJHOFE TDIFEVMJOH QPMJDJFT BSF PG MPX DPNQVUBUJPOBM DPNQMFYJUZ " 4*.1-& 4:45&. .0%&- *O UIJT TFDUJPO XF QSFTFOU B TJNQMF NPEFM PG B NVMUJRVFVF NVMUJTFSWFS TZTUFN XJUI TUPDIBTUJD DPOOFDUJWJUZ BT TIPXO JO 'JH ɩF LFZ JTTVFT PG UIF TJOHMFDFMM NVMUJDIBOOFM TZTUFN XF EF 下行分组按用户分别缓存. 基站: 每个TTI开始时, 在用户之间分配PRB, 以满足下行需求. TTI: Transmission Time Interval. 调度周期(短至1ms). PRB: Physical Resource Blocks. 最小资源单位(12个子载波). 12个子载波看作一个“信道”, 1个TTI看作一个“时隙”. è调度问题可以定义为: 每个时隙为用户/UE分配信道
下行调度问题 根据LTE标准： 四20MHz系统带宽可分成100个信道.)1个TTI内有100个PRB可供分配. 四每个用户可以分配任意的k(0≤k≤100)个信道 总体来看信道条件差的用户，也有机会在少数PRB上得到服务. 即使需求很不均匀，也有机会都得到满足. OFDM的Channel Diversity+资源分配灵活性 四一方面，为提升用户体验带来了巨大机会： s另一方面，给调度算法的设计带来了挑战：巨大的Design Space. 我们的目标：找到理想的调度策略/算法 ⊙A、 吞吐最大（尽量满足用户需求）； 四B、延迟最小（尽量减小分组排队延迟）； 四C、低复杂度（在极短时间内给出调度方案）. 2020年秋季 5/62 无线互联网
下行调度问题 2020年秋季 5 / 62 无线互联网 根据LTE标准: 20MHz系统带宽可分成100个信道.è1个TTI内有100个PRB可供分配. 每个用户可以分配任意的k(� ≤ � ≤ ���)个信道. 总体来看信道条件差的用户, 也有机会在少数PRB上得到服务. 即使需求很不均匀, 也有机会都得到满足. OFDM的Channel Diversity+资源分配灵活性 一方面, 为提升用户体验带来了巨大机会. 另一方面, 给调度算法的设计带来了挑战: 巨大的Design Space. 我们的目标: 找到理想的调度策略/算法. A、吞吐最大 (尽量满足用户需求); B、延迟最小 (尽量减小分组排队延迟); C、低复杂度 (在极短时间内给出调度方案)
问题模型 多队列 Q1 OS1 四每个用户单独排队；FFO, 22 S2 多服务员 : 四每个信道对应一个服务员. ◆ ◆ 随机连接 n 四服务员与队列的连接是时变的 两个假设： 四服务员与队列的数目都是n. ◆只是为了推导方便.可以扩展到更一般的情形： 四随机连接的二元信道假设， ◆只有ON-OFF两种状态.（例如以SINR门限为依据） 2020年秋季 6/62 无线互联网
问题模型 2020年秋季 6 / 62 无线互联网 " 4*.1-& 4:45&. .0%&- TDSJCFE JO UIF QSFWJPVT TFDUJPO DBO CF DBQUVSFE JO UIJT NPEFM 8F BTTVNF UIBU UIFSF BSF n DIBOOFMT FBDI PG XIJDI JT SFQSFTFOUFE CZ B TFSWFS 8F BMTP BTTVNF UIBU UIFSF BSF n VTFST FBDI PG XIJDI JT BTTPDJBUFE XJUI B TFQBSBUF 'JSTU*O 'JSTU0VU '*'0 EBUB RVFVF 'PS FBTF PG QSFTFOUJOH UIF LFZ JEFBT UIF OVNCFS PG VTFST JT BTTVNFE UP CF FRVBM UP UIF OVNCFS PG DIBOOFMT DzF BQQSPBDIFT XF QSFTFOU JO UIJT DIBQUFS XJMM TJNJMBSMZ DBSSZ UISPVHI JG UIF OVNCFS PG VTFST TDBMFT MJOFBSMZ XJUI UIF OVNCFS PG DIBOOFMT FH TFF 8F BTTVNF B TJNQMF CJOBSZ DIBOOFM NPEFM *G UIF DIBOOFM TUBUF JT BCPWF B DFSUBJO RVBMJUZ UISFTIPME FH B TJHOBMUPJOUFSGFSFODFQMVTOPJTF SBUJP PS 4*/3 UISFTIPME UIFO XF TBZ UIBU UIF DIBOOFM JT 0/ PUIFSXJTF UIF DIBOOFM JT BTTVNFE UP CF 0'' ɩSPVHIPVU UIF SFTU PG UIJT DIBQUFS XF XJMM JOUFSDIBOHFBCMZ VTF UIF UFSNT iVTFSw BOE iRVFVFw TJNJMBSMZ GPS UIF UFSNT iDIBOOFMw BOE iTFSWFSw 8F BTTVNF B UJNFTMPUUFE TZTUFN *O FBDI UJNFTMPU B TFSWFS DBO CF BMMPDBUFE UP POMZ POF RVFVF CVU B RVFVF DBO HFU TFSWJDF GSPN NVMUJQMF TFSWFST ɩF DPOOFDUJWJUZ CFUXFFO RVFVFT BOE TFSWFST JT UJNFWBSZJOH JF JU DBO DIBOHF CFUXFFO 0/ BOE 0'' GSPN UJNF UP UJNF 8F BTTVNF UIBU QFSGFDU DIBOOFM TUBUF JOGPSNBUJPO JF XIFUIFS FBDI DIBOOFM JT 0/ PS 0'' GPS FBDI VTFS JO FBDI UJNFTMPU JT LOPXO BU UIF CBTFTUBUJPO Q1 Q2 S2 Sn S1 Qn q 'JHVSF 4ZTUFN NPEFM ɩF DPOOFDUJWJUZ CFUXFFO FBDI QBJS PG RVFVF Qi BOE TFSWFS Sj JT 0/ EFOPUFE CZ B TPMJE FEHF XJUI QSPCBCJMJUZ q BOE 0'' EFOPUFE CZ B EBTIFE FEHF PUIFSXJTF ɩF CBTJD OPUBUJPOT VTFE JO UIJT DIBQUFS BSF BT GPMMPXT 8F MFU Qi EFOPUF UIF '*'0 RVFVF BU UIF CBTFTUBUJPO BTTPDJBUFE XJUI UIF iUI VTFS BOE MFU Sj EFOPUF UIF j UI TFSWFS 8F BTTVNF BO JOmOJUF CVĊFS GPS BMM UIF RVFVFT -FU Ai.t / EFOPUF UIF OVNCFS PG QBDLFU BSSJWBMT UP RVFVF Qi JO UJNFTMPU t 0UIFS UFDIOJDBM BTTVNQUJPOT PO UIF BSSJWBM QSPDFTTFT UIBU BSF TQFDJmDBMMZ OFFEFE GPS EFMBZ BOBMZTJT BOE UISPVHIQVU BOBMZTJT XJMM CF QSFTFOUFE MBUFS JO 4FDUJPOT BOE SFTQFDUJWFMZ 'PS DPODSFUFOFTT XF BTTVNF UIBU QBDLFU BSSJWBMT PDDVS BU UIF CFHJOOJOH PG FBDI UJNFTMPU BOE UIBU QBDLFU EFQBSUVSFT PDDVS BU UIF FOE PG FBDI UJNFTMPU #Z TMJHIUMZ BCVTJOH UIF OPUBUJPOT XF VTF Qi.t / UP EFOPUF UIF MFOHUI PG RVFVF Qi BU UIF CFHJOOJOH PG UJNFTMPU t JNNFEJBUFMZ BGUFS QBDLFU BSSJWBMT "MTP MFU Zi;l.t / EFOPUF UIF EFMBZ JF XBJUJOH UJNF JO UIF RVFVF PG UIF lUI QBDLFU PG RVFVF Qi BU UIF CFHJOOJOH PG UJNFTMPU t XIJDI JT NFBTVSFE TJODF UIF UJNF XIFO UIF QBDLFU BSSJWFE UP RVFVF Qi VOUJM UIF CFHJOOJOH PG UJNFTMPU t /PUF UIBU BU UIF FOE PG FBDI UJNFTMPU UIF QBDLFUT TUJMM QSFTFOU JO UIF TZTUFN XJMM IBWF UIFJS EFMBZT JODSFBTFE CZ POF EVF UP UIF FMBQTFE 多队列 多服务员 随机连接 每个用户单独排队; FIFO. 每个信道对应一个服务员. 服务员与队列的连接是时变的. 两个假设: 服务员与队列的数目都是n. 只是为了推导方便. 可以扩展到更一般的情形. 随机连接的二元信道假设. 只有ON-OFF两种状态. (例如以SINR门限为依据)
CONTENT LTE/OFDM小区内信道调度问题 2 MaxWeight?策略及直觉性改进 3 RFDO及其充分条件 4 TO及其充分条件 5 同时达到RFDO和TO的调度算法 6 小结与展望 2020年秋季 7/62 无线互联网
CONTENT 2020年秋季 7 / 62 无线互联网 1 2 3 4 LTE/OFDM 小区内信道调度问题 MaxWeight策略及直觉性改进 RFDO及其充分条件 TO及其充分条件 5 同时达到RFDO和TO的调度算法 6 小结与展望
MaxWeight策略 多队列调度中有一个非常著名的MaxWeight策略. L.Tassiulas and A.Ephremides,"Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks",/EEE Trans. on Automatic Control,37(12):1936-1948,Dec.1992. 最早是针对单Server系统的.但人们应用于多Server系统时，发现 仍能保持最佳的吞吐性能。 吞吐最佳 回Throughput Optimal(To)的定义我们后面会给出. 四不妨简单理解为：只要是可行的到达过程，该策略都能保证队列稳定 “只要吞得进来，都能吐出去.” 既然吞吐最佳是我们的目标之一，不妨先看一下该策略。 2020年秋季 8/62 无线互联网
MaxWeight策略 2020年秋季 8 / 62 无线互联网 多队列调度中有一个非常著名的MaxWeight策略. L. Tassiulas and A. Ephremides, “Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks”, IEEE Trans. on Automatic Control, 37(12): 1936-1948, Dec. 1992. 最早是针对单Server系统的. 但人们应用于多Server系统时, 发现 仍能保持最佳的吞吐性能. 吞吐最佳 Throughput Optimal(TO)的定义我们后面会给出. 不妨简单理解为: 只要是可行的到达过程, 该策略都能保证队列稳定. “只要吞得进来, 都能吐出去.” 既然吞吐最佳是我们的目标之一, 不妨先看一下该策略
Q-MWS和D-MWS MaxWeight Scheduling(MWS)的基本原理： 四每个Server独自安排/调度. 回在与该Server连通的队列中，将“权重最大”的队列选为服务对象. Q-MWS:以队列长度为权重； D-MWS:以HOL延迟为权重. 示例： 36 S1 24 Q2 S2 ©请注意与匹配 36 的不同之处： Q3 S3 24 Q-MWS 一个队列可以 36 同时被多个信 D-MWS Q1 S1 Q3 S3 道服务. 24 Q2 S> Q3 S3 2020年秋季 9/62 无线互联网
Q-MWS和D-MWS 2020年秋季 9 / 62 无线互联网 MaxWeight Scheduling(MWS)的基本原理: 每个Server独自安排/调度. 在与该Server连通的队列中, 将“权重最大”的队列选为服务对象. Q-MWS: 以队列长度为权重; D-MWS: 以HOL延迟为权重. 1*5'"--4 0' 5)& $-"44*$"- ."98&*()5 10-*$: Q1 Q2 Q3 S1 S2 S3 3 6 1 2 4 5 Q1 Q2 Q3 S1 S2 S3 3 6 1 2 4 5 Q1 Q2 Q3 S1 S2 S3 3 6 1 2 4 5 Q-MWS D-MWS 'JHVSF "O FYBNQMF PG UIF TDIFEVMFT HFOFSBUFE CZ 2.84 BOE %.84 'PS JOTUBODF UIF EFMBZT PG UIF UXP QBDLFUT JO Q1 BSF 6 BOE 3 SFTQFDUJWFMZ ɩF )0- EFMBZT PG UIF UISFF RVFVFT BSF Œ6; 4; 5! 6OEFS 2.84 FBDI TFSWFS XJMM CF BMMPDBUFE UP B DPOOFDUFE RVFVF UIBU IBT UIF MBSHFTU RVFVF MFOHUI 'PS JOTUBODF UXP RVFVFT JF Q1 BOE Q2 BSF DPOOFDUFE UP TFSWFS S1 TFSWFS S1 JT BMMPDBUFE UP Q2 TJODF Q2 IBT B MBSHFS RVFVF MFOHUI UIBO Q1 4FSWFST S2 BOE S3 BSF BMMPDBUFE JO B TJNJMBS NBOOFS *O UIJT QBSUJDVMBS FYBNQMF BMM UISFF TFSWFST BSF BMMPDBUFE UP Q2 VOEFS 2.84 4JNJMBSMZ VOEFS %.84 FBDI TFSWFS XJMM CF BMMPDBUFE UP B DPOOFDUFE RVFVF UIBU IBT UIF MBSHFTU )0- EFMBZ 'PS JOTUBODF S1 JT BMMPDBUFE UP Q1 TJODF Q1 IBT B MBSHFS )0- EFMBZ UIBO Q2 *O UIJT QBSUJDVMBS FYBNQMF BMM UISFF TFSWFST BSF BMMPDBUFE UP Q1 VOEFS %.84 8IJMF CPUI 2.84 BOE %.84 BDIJFWF UISPVHIQVU PQUJNBMJUZ JO PVS NVMUJDIBOOFM TFUUJOH UIFZ NBZ JODVS MBSHF QFSVTFS EFMBZT 5P TFF UIJT MFU VT DPOTJEFS UIF GPMMPXJOH FYBNQMF GPS 2.84¤ UIFSF BSF 100 VTFST BOE 100 DIBOOFMT UIF DPOOFDUJWJUZ QSPCBCJMJUZ JT q D 0:9 JO B HJWFO UJNFTMPU UIF RVFVF MFOHUIT BSF Q1 D 100 Q2 D 99 BOE Q3 D Q4 D !!! D Q100 D 50 /PUF UIBU SPVHIMZ 90 TFSWFST BSF DPOOFDUFE UP Q1 )FODF VOEFS 2.84 BMM PG UIFTF 90 TFSWFST XJMM CF BMMPDBUFE UP Q1 SFHBSEMFTT PG UIFJS DPOOFDUJWJUJFT XJUI UIF PUIFS RVFVFT CFDBVTF Q1 IBT UIF MBSHFTU RVFVF MFOHUI "NPOH UIF SFNBJOJOH 10 TFSWFST SPVHIMZ 9 PG UIFN BSF DPOOFDUFE UP Q2 BOE XJMM CF BMMPDBUFE UP Q2 GPS UIF TBNF SFBTPO ɩF SFNBJOJOH POF TFSWFS XJMM CF BMMPDBUFE UP POF PG UIF SFNBJOJOH 98 RVFVFT 6OEFS UIJT BTTJHONFOU BU UIF FOE PG UIJT UJNFTMPU Q2 XJMM IBWF UIF MBSHFTU RVFVF MFOHUI PG 90 BDDPVOUJOH GPS UIF BMMPDBUFE TFSWJDFT )PXFWFS B CFUUFS BTTJHONFOU XPVME CF UP BMMPDBUF 50 TFSWFST UP Q1 49 TFSWFST UP Q2 BOE 1 TFSWFS UP POF PG UIF SFNBJOJOH 98 RVFVFT ɩJT BTTJHONFOU XJMM SFTVMU JO UIF MBSHFTU RVFVF MFOHUI PG 50 XIJDI JT TVCTUBOUJBMMZ TNBMMFS UIBO UIBU VOEFS 2.84 *O QBSUJDVMBS UIF RVFVF MFOHUI BOE UIVT UIF EFMBZ PG Q2 XJMM CF ESBNBUJDBMMZ SFEVDFE ¤ɩJT FYBNQMF JT TJNJMBS UP UIBU JO 4JNJMBS FYBNQMFT DBO BMTP CF DPOTUSVDUFE GPS %.84 示例: 请注意与匹配 的不同之处: 一个队列可以 同时被多个信 道服务
延迟性能 ®考虑一个实例（以Q-MWS为例）： 四100个队列，100个信道，q=0.9. 四某时隙开始时，Q1=100,Q2=99,Q3=Q4=…=Q100=50 Q-MWS调度的结果是：有90个信道被安排给Q1,剩下的10个信道 中有9个被安排给Q2,最后一个信道被安排给Q3~100中的某个. 该时隙结束时，Q1降到10，但Q2为90. 四从用户延迟到角度看，更好的调度是： 50个信道安排给Q1,49个信道安排给Q2,剩下的一个信道给Q3~100 该时隙结束时，最大队长为50，远小于90. 虽然MWS是吞吐最佳的，但延迟性能不好. 2020年秋季 10/62 无线互联网
延迟性能 2020年秋季 10 / 62 无线互联网 考虑一个实例(以Q-MWS为例): 100个队列, 100个信道, � = �. �. 某时隙开始时, �� = ���, �� = ��, �� = �� = ⋯ = ���� = �� Q-MWS调度的结果是: 有90个信道被安排给��, 剩下的10个信道 中有9个被安排给��, 最后一个信道被安排给��~���中的某个. 该时隙结束时, ��降到10, 但��为90. 从用户延迟到角度看, 更好的调度是: 50个信道安排给��, 49个信道安排给��, 剩下的一个信道给��~���. 该时隙结束时, 最大队长为50, 远小于90. 虽然MWS是吞吐最佳的, 但延迟性能不好