问题模型 多队列 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是吞吐最佳的, 但延迟性能不好