У математичкој теорији вероватноће, метод одузимања-плус-казне се користи за оптимизацију мрежа редова чекања и других стохастичких система.
Техника служи за стабилизацију мреже редова чекања истовремено минимизирајући временски просек функције казне мреже. Може се користити за оптимизацију перформансних циљева као што су временски просечна снага, пропусна моћ и користност пропусне моћи. У специјалном случају када не постоји казна која би се минимизирала, и када је циљ дизајнирати политику стабилног усмеравања у вишескочној мрежи, метод се своди на пузајуће усмеравање. Метод одузимања-плус-казне такође може да се користи за минимизацију временског просека стохастичког процеса уз услове временског просека за збир других стохастичких процеса. Ово се постиже дефинисањем одговарајућег скупа виртуелних редова. Такође се може користити за добијање решења временског просека за проблеме конвексне оптимизације.
Методологија
Метод одузимања-плус-казне се примењује на системе редова чекања који раде у дискретном времену са временским слотовима t у {0, 1, 2, ...}. Прво, дефинише се не-негативна функција L(t) као скаларна мера стања свих редова у времену t. Функција L(t) се обично дефинише као збир квадрата величина свих редова у времену t, и зове се Љапунова функција. Љапуново одузимање се дефинише као:
Сваки временски слот t, посматра се тренутно стање редова и предузимају се контролне акције да се похлепно минимизира граница следећег израза одузимања-плус-казне:
где је p(t) функција казне и V је не-негативна тежина. Параметар V се може изабрати тако да временски просек p(t) bude произвољно близак оптималном, са одговарајућим компромисом у просечној величини реда. Као и код пузаћег усмеравања, ова метода обично не захтева познавање расподела вероватноћа за доласке послова и мобилност мреже.
Порекло и примене
Када је метод се своди на похлепно минимизирање Љапуновог одузимања. Ово резултује алгоритмом пузаћег усмеравања који су првобитно развили Тасиулас и Ефремидис (такође назван и максимална тежина алгоритам). Члан је изразу одузимања додао Нили и Нили, Модијано, Ли за стабилизацију мреже истовремено максимизирајући функцију корисности пропусне моћи. За ово, казна је дефинисана као пута награда освојена у слоту Ова техника одузимања-плус-казне је касније коришћена за минимизацију просечне снаге и оптимизацију других метрика казне и награде.
Теорија је првенствено развијена за оптимизацију комуникационих мрежа, укључујући бежичне мреже, ad-hoc мобилне мреже и друге рачунарске мреже. Међутим, математичке технике се могу примењивати на оптимизацију и контролу других стохастичких система, укључујући алоцирање обновљиве енергије у паметним енергетским мрежама и контролу инвентара за системе монтаже производа.
Како ради
Овај одељак показује како се метод одузимања-плус-казне користи за минимизацију временског просека функције p(t) уз услове временског просека за збир других функција. Анализа испод се заснива на материјалу из.
Стохастички проблем оптимизације
Размотримо систем са дискретним временом који се развија у нормализованим временским слотовима t у {0, 1, 2, ...}. Дефинишимо p(t) као функцију чији временски просек треба минимизовати, названу функција казне. Претпоставимо да се минимизација временског просека p(t) мора извршити уз услове временског просека за збир K других функција:
Сваки слот t, контролер мреже посматра нови случајни догађај. Затим предузима контролну акцију на основу знања о овом догађају. Вредности p(t) и y_i(t) се одређују као функције случајног догађаја и контролне акције у слоту t:
Мала слова p(t), y_i(t) и велика слова P(), Y_i() се користе да би се разликовале вредности казне од функције која одређује ове вредности на основу случајног догађаја и контролне акције за слот t. Случајни догађај се претпоставља да узима вредности у неком апстрактном скупу догађаја . Контролна акција се претпоставља да се бира унутар неког апстрактног скупа који садржи контролне опције. Скупови и су произвољни и могу бити коначни или бесконачни. На пример, може бити коначна листа апстрактних елемената, небројиво бесконачан (и могуће неконвексан) скуп вектора реалних вредности, и тако даље. Функције P() и Y_i() су такође произвољне и не захтевају претпоставке о континуитету или конвексности.
Као пример у контексту комуникационих мрежа, случајни догађај може бити вектор који садржи информације о доласку за слот t за сваки чвор и информације о стању канала за слот t за сваку везу. Контролна акција може бити вектор који садржи одлуке о усмеравању и преносу за сваки чвор. Функције P() и Y_i() могу представљати потрошњу енергије или пропусну моћ повезану са контролном акцијом и стањем канала за слот t.
За поједностављење излагања, претпоставимо да су функције P() и Y_i() ограничене. Даље претпоставимо да процес случајних догађаја је независно и идентично дистрибуиран (н.и.д.) преко слотова t са неком могуће непознатом расподелом вероватноће. Циљ је дизајнирати политику за доношење контролних акција током времена да би се решио следећи проблем:
Прихвата се да је овај проблем изводљив. То је, претпоставља се да постоји алгоритам који може да задовољи свих K жељених ограничења.
Горњи проблем поставља свако ограничење у стандардном облику временског просека очекивања апстрактног процеса y_i(t) да буде не-позитиван. При овом приступу нема губитка општности. На пример, претпоставимо да се жели да временски просек очекивања неког процеса a(t) буде мањи или једнак датој константи c. Тада се може дефинисати нова функција казне y(t) = a(t) − c, и жељено ограничење је еквивалентно временском просеку очекивања од y(t) да буде не-позитивно. Слично, претпоставимо да постоје два процеса a(t) и b(t) и да се жели да временски просек очекивања од a(t) буде мањи или једнак временском просеку од b(t). Ово ограничење се пише у стандартном облику дефинисањем нове функције казне y(t) = a(t) − b(t). Горњи проблем тражи да се минимизује временски просек апстрактне функције казне p(t). Ово се може користити за максимизацију временског просека неке жељене функције награде r(t) дефинисањем p(t) = −r(t).
Виртуелни редови
За свако ограничење i у {1, ..., K}, дефиниши виртуелни ред са динамиком преко слотова t у {0, 1, 2, ...} на следећи начин:
Иницијализуј Qi(0) = 0 за сва i у {1, ..., K}. Једначина ажурирања је идентична оном за виртуелни ред са дискретним временом са залихом Q_i(t) и са y_i(t) који представља разлику између нових долазака и нових прилика за сервисирање у слоту t. Интуитивно, стабилизација ових виртуелних редова осигурава да су временски просеци функција ограничења мањи или једнаки нули, тако да су жељена ограничења задовољена. Да би се ово прецизно видело, приметимо да (Једн. 1) имплицира:
Стога:
Сабирањем горњег преко првих t слотова и коришћењем закона телескопских сума имплицира:
Дељењем са t и узимањем очекивања имплицира:
Стога су жељена ограничења проблема задовољена кад год важи следеће за сва i у {1, ..., K}:
Ред Q_i(t) који задовољава горњу једначину границе се каже да је просечно стабилан по стопи.
Израз одузимања-плус-казне
Да би се стабилизовали редови, дефиниши се Љапунова функција L(t) као мера укупне заосталости реда у слоту t:
Квадрирањем једначине реда (Једн. 1) добија се следећа граница за сваки ред i у {1, ..., K}:
Стога,
Из тога следи
Сада дефиниши B као позитивну константу која ограничава први члан на десној страни горње неједнакости. Таква константа постоји јер су вредности y_i(t) ограничене. Тада:
Додавањем Vp(t) на обе стране добија се следећа граница на израз одузимања-плус-казне:
Алгоритам одузимања-плус-казне (дефинисан испод) доноси контролне акције сваки слот t које похлепно минимизирају десну страну горње неједнакости. Интуитивно, преузимање акције која минимизира само одузимање било би корисно у погледу стабилности реда, али не би минимизирало временски просек казне. Преузимање акције која минимизира само казну не би нужно стабилизовало редове. Дакле, преузимање акције за минимизацију пондерисаног збира интегрише оба циља: стабилност реда и минимизацију казне. Тежина V се може подесити да би се ставио већи или мањи нагласак на минимизацију казне, што резултује компромисом у перформансама.
Алгоритам одузимања-плус-казне
Нека буде апстрактни скуп свих могућих контролних акција. Сваки слот t, посматрај случајни догађај и тренутне вредности редова:
Дата ова посматрања за слот t, похлепно одабери контролну акцију да би се минимизирао следећи израз (решавајући изједначења произвољно):
Затем ажурирај редове за свако i у {1, ..., K} према (Једн. 1). Понови ову процедуру за слот t+1.
Примети да случајни догађај и заосталости редова посматрани у слоту t делују као дате константе приликом избора контролне акције за минимизацију у слоту t. Дакле, сваки слот укључује детерминистичку претрагу за минимизирајућом контролном акцијом преко скупа A. Ключна карактеристика овог алгоритма је што не захтева познавање расподеле вероватноће процеса случајних догађаја.
Приближно планирање
Горњи алгоритам укључује проналажење минимума функције преко апстрактног скупа A. У општим случајевима, минимум можда не постоји или је тешко наћи. Стога је корисно претпоставити да се алгоритам имплементира на приближан начин на следећи начин: Дефиниши C као не-негативну константу, и претпостави да за све слотове t, контролна акција се бира у скупу A да би задовољила:
Таква контролна акција се назива C-адитивна апроксимација. Случај C = 0 одговара тачној минимизацији жељеног израза у сваком слоту t.
Анализа перформанси
Овај одељак показује да алгоритам резултује временским просеком казне који је у оквиру O(1/V) оптималног, са одговарајућим O(V) компромисом у просечној величини реда.
Анализа просечне казне
Дефиниши -only политику као стационарну и рандомизовану политику за одабир контролне акције на основу посматраног само. То јест, -only политика спецификује, за сваки могући случајни догађај , условна расподела вероватноће за избор контролне акције дат да је . Таква политика доноси одлуке независно од тренутне заосталости реда. Претпоставимо да постоји -only политика која задовољава следеће:
Очекивања изнад су у односу на случајну променљиву за слот и случајну контролну акцију изабрану у слоту након посматрања . Таква политика се може показати да постоји кад год је жељени проблем контроле изводљив и када су простор догађаја за и простор акција за коначни, или када су задовољена блага својства затварања.
Нека представља акцију коју предузима C-адитивна апроксимација алгоритма одузимања-плус-казне из претходног одељка, за неку не-негативну константу C. За поједностављење терминологије, ову акцију ћемо назвати акција одузимања-плус-казне, уместо C-адитивна приближна акција одузимања-плус-казне. Нека представља -only одлуку:
Претпоставимо да се акција одузимања-плус-казне користи у сваком слоту. Према (Једн. 2), израз одузимања-плус-казне под овом акцијом задовољава следеће за сваки слот
где последња неједнакост следи зато што акција долази унутар адитивне константе минимизирања претходног израза преко свих других акција у скупу укључујући Узимањем очекивања горње неједнакости добија се:
Примети да акција никада није стварно имплементирана. Њено постојање је коришћено само у сврхе поређења да би се стигло до коначне неједнакости. Сабирањем горње неједнакости преко првих слотова добија се:
Дељењем горњег са добија се следећи резултат, који важи за све слотове
Дакле, временски просек очекиване казне може бити произвољно близак оптималној вредности избором довољно великог . Може се показати да су сви виртуелни редови просечно стабилни по стопи, и да су сва жељена ограничења задовољена. Параметар утиче на величину редова, која одређује брзину са којом се временски просек функција ограничења конвергира ка не-позитивном броју. Детальнија анализа величине редова дата је у следећем пододељку.
Анализа просечне величине реда