Пропорционально-справедливое планирование

Пропорционально-справедливое планирование основанный на компромиссе — это алгоритм планирования, . Он основан на поддержании баланса между двумя конкурирующими интересами: попытка максимизировать общую пропускную способность сети (проводной или нет), в то же время предоставляя всем пользователям хотя бы минимальный уровень обслуживания. Это делается путем назначения каждому потоку данных скорости передачи данных или приоритета планирования (в зависимости от реализации), который обратно пропорционален ожидаемому потреблению ресурсов. ^[1]^[2]

Взвешенная справедливая организация очередей

Пропорционально справедливое планирование может быть достигнуто с помощью взвешенной справедливой организации очереди (WFQ), путем установки весов планирования для потока данных. $i$ к $w_{i}=1/c_{i}$ , где стоимость $c_{i}$ — количество потребляемых ресурсов на один бит данных. Например:

В сотовых сетях CDMA с расширенным спектром затратой может быть требуемая энергия на бит при управлении мощностью передачи (повышенный уровень помех).
В беспроводной связи с адаптацией линии связи стоимость может заключаться в необходимом времени для передачи определенного количества битов с использованием необходимой для этого схемы модуляции и кодирования ошибок. Примером этого являются сети EVDO , где заявленное соотношение сигнал/шум используется в качестве основного фактора стоимости.
В беспроводных сетях с быстрым динамическим распределением каналов ценой может быть количество близлежащих базовых станций, которые не могут использовать один и тот же частотный канал одновременно, чтобы избежать помех внутри канала.

Приоритеты пользователей

Другой способ планирования передачи данных, который приводит к аналогичным результатам, — использование коэффициентов приоритезации. ^[3] Здесь мы планируем канал для станции, имеющей максимум функции приоритета:

$P={\frac {T^{\alpha }}{R^{\beta }}}$

$T$ обозначает скорость передачи данных, потенциально достижимую для станции в текущем временном интервале.
$R$ - это историческая средняя скорость передачи данных этой станции.
$\alpha$ и $\beta$ настройте «справедливость» планировщика.

Регулируя $\alpha$ и $\beta$ в приведенной выше формуле мы можем настроить баланс между более частым обслуживанием лучших мобильных телефонов (тех, которые находятся в лучших условиях канала) и достаточно частым обслуживанием дорогостоящих мобильных телефонов, чтобы они имели приемлемый уровень производительности.

В крайнем случае( $\alpha =0$ и $\beta =1$ ) планировщик действует по принципу «пакетного» циклического перебора и обслуживает все мобильные телефоны один за другим (но не одинаково часто по времени), без учета потребления ресурсов и так, что каждый пользователь получает одинаковый объем данных. ( $\alpha =0$ и $\beta =1$ ) планировщик можно было бы назвать «планировщиком максимальной справедливости» (например, для обеспечения равноправия голосовых пользователей). Если $\alpha =1$ и $\beta =0$ тогда планировщик всегда будет обслуживать мобильный телефон с лучшими условиями канала. Это позволит максимизировать пропускную способность канала, в то время как станции с низким $T$ не обслуживаются вообще. ( $\alpha =1$ и $\beta =0$ ) планировщик можно было бы назвать планировщиком «максимальной скорости». ^[2] С использованием $\alpha \approx 1$ и $\beta \approx 1$ даст алгоритм пропорционального справедливого планирования, используемый в сетях 3G. ^[3] ( $\alpha =1$ и $\beta =1$ ) планировщик может быть реализован путем предоставления одинакового количества времени и спектра для каждого пользователя, независимо от желаемого размера пакета, качества канала и используемой скорости передачи данных (MCS). Пропорциональная справедливость ( $\alpha =1$ и $\beta =1$ ) планировщик можно было бы назвать «планировщиком равных усилий» или «планировщиком циклического перебора времени/спектра».

Этот метод можно дополнительно параметризовать с помощью «константы памяти», которая определяет период времени, в течение которого усредняется скорость передачи данных станции, используемая при вычислении функции приоритета. Увеличение константы обычно увеличивает пропускную способность за счет снижения краткосрочной справедливости.

См. также

Планирование (вычисление) – введение в общую тему планирования.
Круговое планирование — другой алгоритм планирования.
Правило пропорционально-справедливости — более общее правило выбора среди различных альтернатив, основанное на том же принципе баланса эффективности и справедливости.

Ссылки

^ Кушнер, HJ; Уайтинг, Пенсильвания (июль 2004 г.), «Сходимость алгоритмов пропорционального справедливого распределения в общих условиях», IEEE Transactions on Wireless Communications , 3 (4): 1250–1259, CiteSeerX 10.1.1.8.6408 , doi : 10.1109/TWC.2004.830826 , S2CID 6780351 .
^ Jump up to: ^а ^б Гуован Мяо , Йенс Зандер, Ки Вон Сунг и Бен Слиман, «Основы сетей мобильной передачи данных», издательство Кембриджского университета, ISBN 1107143217 , 2016.
^ Jump up to: ^а ^б Цзи Ян; Чжан Ифань; Ван Ин; Чжан Пин (2004), «Механизм обновления средней скорости в пропорциональном справедливом планировщике для HDR», Глобальная телекоммуникационная конференция IEEE, 2004. GLOBECOM '04 , vol. 6, стр. 3464–3466, номер документа : 10.1109/GLOCOM.2004.1379010 , ISBN. 0-7803-8794-5

Дальнейшее чтение

Эндрюс, Мэтью (сентябрь 2004 г.), «Нестабильность алгоритма пропорционального справедливого планирования для HDR», IEEE Transactions on Wireless Communications , 3 (5): 1422–1426, CiteSeerX 10.1.1.73.4092 , doi : 10.1109/TWC.2004.833419 , S2CID 34595035 .
Эндрюс, Мэтью ; Кумаран, К.; Раманан, К.; Стояр, А.; Уиттинг, Фил (февраль 2001 г.), «Обеспечение качества обслуживания через общий беспроводной канал», IEEE Communications , 39 (2): 150–154, doi : 10.1109/35.900644 .
Паррука, Дональд; Грисла, Мариус; Горцен, Саймон; Гросс, Джеймс (2013), «Аналитическая модель пропорционального справедливого планирования в сетях OFDMA/LTE с ограниченными помехами», 78-я конференция IEEE по автомобильным технологиям (VTC Fall), 2013 г. , стр. 1–7, arXiv : 1303.1778 , Bibcode : 2013arXiv1303.1778P , doi : 10.1109/VTCFall.2013.6692106 , ISBN 978-1-4673-6187-3 , S2CID 8236469

[Kushner-1] Кушнер, HJ; Уайтинг, Пенсильвания (июль 2004 г.), «Сходимость алгоритмов пропорционального справедливого распределения в общих условиях», IEEE Transactions on Wireless Communications , 3 (4): 1250–1259, CiteSeerX 10.1.1.8.6408 , doi : 10.1109/TWC.2004.830826 , S2CID 6780351 .

[Zander-2] Jump up to: ^а ^б Гуован Мяо , Йенс Зандер, Ки Вон Сунг и Бен Слиман, «Основы сетей мобильной передачи данных», издательство Кембриджского университета, ISBN 1107143217 , 2016.

[Yang-3] Jump up to: ^а ^б Цзи Ян; Чжан Ифань; Ван Ин; Чжан Пин (2004), «Механизм обновления средней скорости в пропорциональном справедливом планировщике для HDR», Глобальная телекоммуникационная конференция IEEE, 2004. GLOBECOM '04 , vol. 6, стр. 3464–3466, номер документа : 10.1109/GLOCOM.2004.1379010 , ISBN. 0-7803-8794-5

[1]

[2]

[3]