1 UVOD
Brezžična komunikacijska omrežja postajajo čedalje
obsežnejša in bolj kompleksna, zato optimizacija
delovanja in upravljanje s klasičnimi determinističnimi
metodami ni več mogoče. V ta namen se poleg
hevrističnih metod čedalje pogosteje uporablja tudi
teorija iger [1] kot posebno področje uporabne
matematike.
Teorija iger je orodje, s katerim modeliramo
situacije, v katerih je uspeh odločitve entitete odvisen
od odločitev drugih entitet v sistemu. Uporablja se tam
primerih, kjer se interesi ene entitete ali skupine entitet
križajo ali vplivajo na interese drugih entitet. Vsakemu
križanju interesov pravimo konfliktna situacija [2] in
pomeni konflikt med posameznimi entitetami v sistemu.
Obnašanje posameznikov v takšni situaciji je opisano s
pomočjo matematičnega modela, pri katerem se
oblikujejo pravila igre. Pri tem predvidevamo, da se
udeleženci igre obnašajo racionalno [3]. To pomeni, da
se igralec vedno odloča za poteze, ki mu prinašajo
največjo korist, z upoštevanjem mogočih potez drugih
udeležencev in zunanjih okoliščin.
Ker je teorija iger orodje za modeliranje situacij, v
katerih nosilci odločanja pri sprejemanju odločitev
medsebojno vplivajo drug na drugega, je primerna tudi
za uporabo v brezžičnih komunikacijskih sistemih. V
zadnjih zaradi souporabe radijskega kanala pride do
medsebojnega vpliva med posameznimi napravami. S
pomočjo teorije iger je v tem primeru mogoče postaviti
omrežje v stabilno točko obratovanja, kjer vozlišča
omrežja izvedejo svoje samostojne optimalne
prilagoditve.
Namen tega prispevka je prikazati teorijo iger kot
orodje za optimizacijo uporabe radijskih virov v
brezžičnih omrežjih, ob tem pa predstaviti osnovne
pojme, s katerimi se srečamo pri delu s teorijo iger.
Opisana je uporaba teorije iger v brezžičnih omrežjih,
kjer so različnim komponentam teorije iger pripisane
ustrezne komponente brezžičnih omrežij. Prav tako je
opisana povezava med principi v teoriji iger in principi
Prejet 24. november, 2011
Odobren 12. december, 2011
288 PERTOVT, JAVORNIK, MOHORČIČ
v brezžičnih omrežjih. Za kategorijo potencialnih iger,
ki je še posebej primerna za uporabo v brezžičnih
omrežjih, je razvit model za optimizacijo porazdeljene
nastavitve oddajnih moči vozlišč v relejnem brezžičnem
omrežju zbirnih vozlišč brezžičnih senzorskih omrežij.
2 OSNOVNI KONCEPTI TEORIJE IGER
Igre, katerih izid je razen od naključja odvisen tudi od
spretnosti in strategije igralcev, imenujemo strateške
igre [4]. Z njimi se ukvarja teorija iger. Igra je zbirka
pravil in dogovorov, po katerih se ravnajo njeni
udeleženci. Igro opišemo s pomočjo treh komponent: z
množico igralcev, z množico strategij/akcij za vsakega
igralca in z množico preferenc glede mogočih izidov
igre.
Udeleženci igre so igralci, ki izbirajo med svojimi
akcijami v vsaki fazi igre. Izbire igralcev vselej vplivajo
na izid igre vsakega od igralcev in s tem pomenijo
medsebojno interakcijo med vsemi igralci. Vsaki
igralčevi izbiri posamezne akcije pravimo poteza.
Strategija igralca je zbirka pravil, ki opisuje, katere
akcije mora igralec izbrati v vsakem trenutku ali fazi
igre, v skladu: (i) s pravili (omejitvami) igre; (ii) z
vsemi možnostmi, ki se lahko pokažejo v igri; (iii) s
prejšnjimi potezami preostalih igralcev; (iv) z
informacijami, ki postanejo dostopne med igro; (v) s
preferencami igralca glede izidov igre. Preferenca
igralca je predstavljena kot donos, ki ga igralec dobi pri
posameznem izidu igre. Donosi ovrednotijo željnost
posameznih izidov igre s strani igralcev. Večji donosi so
bolj zaželeni kot manjši.
2.1 Predstavitev iger
Igro lahko podamo v različnih oblikah, pri čemer so za
obravnavo različnih iger primerne različne oblike [5],
kot so normalna, ekstenzivna, koalicijska itd. V
nadaljevanju je podrobneje predstavljena normalna
oblika zapisa igre, ki se uporablja tudi pri potencialnih
igrah, katerih primer predstavljamo v zadnjem delu
članka.
Igra je po navadi podana v normalni obliki, ko ima
vsak od igralcev le eno potezo in nobene informacije o
že izvedenih potezah preostalih igralcev, saj igralci
izbirajo akcije sočasno. Strategija igralca je izbira
akcije	� in jo imenujemo čista strategija �. Izbrane
akcije vseh igralcev pomenijo izid igre.
Igra v normalni obliki je podana kot Γ =	 〈�, �, 	〉,
kjer je � = {1,2, … , �} množica n igralcev, � =	×�∈� ��
je akcijski prostor (tj. množica vseh akcijskih profilov
vseh igralcev) in 	 = {��} je niz funkcij donosov oz.
koristnosti vseh igralcev. �� = {��} je končna množica
akcij igralca �, �� pa je funkcija koristnosti oz. donosov
igralca �.
Profil akcij � = (��, ��, … , ��) je vektor akcij, kjer
vsak element vektorja pomeni eno akcijo vsakega od
igralcev. Profil akcij, ki so ga izbrali igralci v igri,
imenujemo izid igre. Pogosto se uporablja zapis
� = (�� , ���), kjer je �� izbrana akcija igralca �, ��� pa
so izbrane akcije preostalih igralcev. Funkcije
koristnosti oz. donosov so funkcije različnih profilov
akcij in opisujejo preference igralcev glede profilov
akcij. Koristnost je pogosto kriterij za določanje donosa.
Donose oz. koristnosti igralcev pri določenem izidu
igre, označene z � = (��(�), ��(�), … , ��(�)),
imenujemo profil donosov oz. koristnosti. Cilj igre je po
navadi maksimirati donose oz. koristnosti igralcev.
V tabeli 1 je prikazana igra z dvema igralcema
� = {1,2}, označenima z �� in 	��, v kateri ima vsak od
igralcev po dve izbiri (� (1), � (2)). �� izbira vrstico, ��
pa stolpec. Koristnosti igralca �� so predstavljene z �� ,
koristnosti igralca �� pa z �� . Tako pri profilu
akcij	� = (��, ��) = (��(1), ��(2)) dobimo profil
koristnosti � = (��(�), ��(�)) = (���, ���) = (0, 3).
Tabela 1: Igra z dvema igralcema v strateški obliki
2.2 Tipi iger
Igre glede na različne lastnosti delimo v različne tipe. V
nadaljevanju so na kratko predstavljeni nekateri osnovni
tipi iger.
2.2.1 Kooperativne in nekooperativne igre
V kooperativnih igrah lahko igralci med seboj
sodelujejo, medtem ko v nekooperativnih ne morejo.
2.2.2 Igre s popolno in nepopolno informacijo
Pri igrah s popolno informacijo igralci poznajo vse
igralce, množice akcij igralcev in vse mogoče funkcije
donosov in koristnosti igralcev. Vse druge igre spadajo
med igre z nepopolno informacijo.
2.2.3 Statične ali strateške igre
Statične igre ustrezajo opisu iz poglavja 2.1. Ko igralec
vedno izbira isto akcijo oz. čisto strategijo, pravimo, da
igra čisto strategijo. Če pa igralec izbira različne akcije
oz. čiste strategije z različnimi verjetnostmi, pravimo,
da igra mešano strategijo. Mešano strategijo za igralca �
označujemo z #� ∈ #(��), kjer je #�(��) verjetnost
izbire akcije �� pri igranju #�, ter ∑ #�(��)%&∈'& = 1 in
#�(��) ≥ 0. Profil # je profil mešanih strategij vseh
igralcev. V primeru #�(��) = 0 za vse akcije �� razen
ene dobimo čisto strategijo.
2.2.4 Dinamične ali ekstenzivne ali sekvenčne igre
Pri dinamičnih igrah ima vsaj eden od igralcev več kot
eno potezo in nekaj informacije o izvedenih potezah
preostalih igralcev. Igralci akcij ne izbirajo sočasno,
temveč sekvenčno, in poznajo akcije, ki so jih že izbrali
drugi igralci. Zaporedje potez je tukaj zelo pomembno.
��
�� ��(1) ��(2)
��(1) ��� = 2, ��� = 2 ��� = 0, ��� = 3
��(2) ��) = 3, ��) = 0 ��* = 1, ��* = 1
UPORABA TEORIJE IGER V BREZŽIČNIH OMREŽJIH 289
Igralec v določeni fazi igre izbere akcijo glede na svojo
prejšnjo izbiro in izbiro drugih igralcev v predhodnih
fazah igre, tj. glede na njegovo trenutno pozicijo v igri.
Strategija igralca v takšni igri je zbirka pravil, ki
opisuje, katere akcije mora igralec izbrati.
2.2.5 Igre s ponavljanjem
Igre s ponavljanjem so razred dinamičnih iger, pri
katerih je ista odločitev igralcev izvedena večkrat
zapovrstjo ob določenih intervalih.
2.2.6 Potencialne igre
Potencialna igra [6] je igra v normalni obliki, ki ima za
funkcijo koristnosti potencialno funkcijo. Ta izraža
spremembo v koristnosti, ki jo povzroči vsak od
igralcev, ko enostransko spremeni svojo strategijo.
Potencialne igre so zanimive, ker lahko z eno funkcijo
predstavimo koristnosti in obnašanje vseh igralcev.
Predvsem so zanimivi primeri, ko se uporabljajo
sebične strategije, saj imajo potencialne igre posebno
lastnost, da pod vsemi sebičnimi strategijami zagotovo
vodijo k Nashevemu ravnovesju [7] (opisanemu v
poglavju 2.3), katerega praviloma dosegajo pri nekaterih
lokalnih optimumih. Razred pogosto obravnavanih
potencialnih iger so ordinalne potencialne igre [6].
Igra v normalni obliki, Γ =	 〈�, �, 	〉, je ordinalna
potencialna igra, če obstaja funkcija +: �	 → 	ℝ (kjer ℝ
pomeni realna števila), da velja ��(�� , ���) −
��(��
∗, ���) > 0 ↔ +(�� , ���) − +(��
∗, ���) > 0, za vse
� ∈ �, vse ��� ∈ ���, ter vse �� , ��
∗ ∈ ��. To pomeni,
da potencialna funkcija naraste (pade), če igralec
pridobi večji (manjši) donos pri enostranski zamenjavi
strategije. Zgornji algoritem ne zahteva, da je igra
končna, kar je še ena dobra lastnost teh iger.
Poleg zgoraj naštetih se uporabljajo še drugi tipi iger,
kot so: koalicijske, stohastične, kombinatorne,
Bayesove,  diferencialne, evolucijske, igre s pogajanji
itd.
2.3 Nashevo ravnovesje in učinkovitost Pareto
V teoriji iger obstajajo različni koncepti, ki določajo,
katere strategije ali akcije naj igralci izberejo, da bodo
uspešno končali igro. Koncept najboljšega odgovora
igralca definira akcijo igralca ��
∗ kot najboljši odgovor
na akcije ���, ki so jih izbrali drugi igralci, če le-ta
maksimira njegov donos oz. koristnost: 	��(��
∗, ���) ≥
��3��
′ , ���4		∀��
′ ≠ ��
∗. Če za vsakega igralca � velja:
��(��
∗, ���
∗ ) ≥ ��3��
′ , ���
∗ 4		∀��
′ , potem profil akcij �∗
pomeni Nashevo ravnovesje (NR). To pomeni, da ne
more noben igralec povečati svojega donosa tako, da bi
enostransko spremenil svojo akcijo. Zato ni razloga, da
bi igralec odstopil od svoje izbire, ob predpostavki, da
tudi preostali igralci ne bodo odstopili od svojih.
Igra ima lahko več NR-jev. Prav tako ni
zagotovljeno, da ustreza vsako NR želenemu izidu igre.
Zato obstajajo različne metode za določanje
učinkovitosti profilov akcij. Ena teh je tudi učinkovitost
Pareto. Profil akcij �∗ je Pareto učinkovit (PU), če ne
obstaja izid igre oziroma profil akcij �′, ki bi pomenil za
vse igralce vsaj enako dobro stanje ter bi vsaj enemu
izmed igralcev izboljšal stanje, torej če velja ��(�
′) ≥
��(�
∗)				∀��
′ . Pravimo, da je �∗ Pareto učinkovito
Nashevo ravnovesje (PUNR).
Pri tabeli 1 pogojem za NR ustreza profil akcij
(��(1), ��(2)), pri katerem oba igralca dosežeta donos
ena.
3 TEORIJA IGER V BREZŽIČNIH OMREŽJIH
V brezžičnih omrežjih je frekvenčni spekter omejen
prenosni vir, ki si ga delijo naprave znotraj omrežja. Z
učinkovito uporabo tega vira je posredno ali neposredno
povezanih veliko drugih virov in obratovalnih
parametrov teh omrežij, prav tako potrebnih za uspešno
komuniciranje. Med te spadajo moč oddajanja, pasovna
širina, čas oddajanja, energija vozlišč itd. Teorija iger se
uporablja kot eno mogočih orodij za optimizacijo rabe
teh virov in parametrov, povezanih z viri v takšnem
porazdeljenem brezžičnem sistemu.
3.1 Povezava med teorijo iger in brezžičnimi
omrežji
Za uporabo teorije iger v brezžičnih omrežjih je treba
pripisati različnim komponentam teorije iger ustrezne
komponente brezžičnih omrežij. Igralce v brezžičnih
omrežjih pomenijo posamezna vozlišča omrežja,
operaterji, uporabniki itd. Akcija ali strategija je izbira
ali odločitev igralca in se nanaša na dodelitev
razpoložljivih virov (moči, spektra, pasovne širine)
znotraj igre, kot so npr. nastavitev oddajne moči signala
na vozliščih, odločanje, ali dostopati do prenosnega
medija ali ne, itd. Funkcija koristnosti je funkcija, ki je
določena za potrebe specifične aplikacije in pomeni
metriko za določanje kakovosti delovanja omrežja ali
storitev. Na podlagi zadnje se odločamo pri izbiri
posamezne strategije oz. akcije. Funkcija koristnosti
stremi k izboljšanju različnih omrežnih kriterijev, kot so
npr. SINR, podatkovni pretok, izraba pasovne širine itd.,
ocena njene koristnosti pa se opravi s pomočjo donosa.
Ocena temelji na metrikah kakovosti storitev.
Pri apliciranju teorije iger v brezžična omrežja je
glavni izziv modeliranje ustrezne igre z upoštevanjem
številnih omejitev brezžičnih omrežij. Temu pravimo
parametrizacija igre. Pri uporabi teorije iger je treba
upoštevati, da ni vsak optimizacijski problem že igra; za
modeliranje igre je treba imeti več vozlišč, ki so
vključena v odločanje. Igralce, akcije in cilje je treba
določiti izjemno previdno. Izbira funkcije koristnosti oz.
donosa je ključnega pomena in najbrž najtežji del
parametrizacije. Z njimi je mogoče analizirati, kako
spremembe strategij igralcev vplivajo na delovanje
posameznega igralca ali sistema kot celote. Če je cilj
igralcev maksimirati učinkovitost delovanja sistema,
mora biti funkcija koristnosti določena tako, da sistem
konvergira k optimalnim razmeram delovanja omrežja v
290 PERTOVT, JAVORNIK, MOHORČIČ
skladu z določenimi cilji. Na primer, kako pomembno je
za uporabnika poslati paket, je odvisno od tega, ali
vsebuje ključno informacijo ali ne. S takšnimi in
podobnimi problemi se ukvarja mehanizem oblikovanja
[8].
Komunikacijska vozlišča imajo načeloma omejeno
količino energije. Pri teoriji iger v brezžičnih omrežjih
pomeni v tem primeru poraba energije ceno (strošek) za
igralca. Pri izbiri določene strategije se vozlišča
odločajo glede na višino cene, ki jo morajo plačati.
Ceno pomeni tudi zakasnitev ali porabljena pasovna
širina itd. Pri modeliranju igre je treba prilagoditi
uporabo omejenih virov ceni, čemur pravimo cenitev, in
je odločilen faktor v funkciji koristnosti. To je izziv, saj
morajo imeti npr. naprave s skoraj praznimi baterijami
drugačen način vrednotenja cene kot naprave s polnimi
baterijami, kar pa je mogoče le s spremenljivo mero
cene. Različne sheme cenitev se uporabljajo za
spodbujanje sodelovanja med vozlišči in preprečevanje
sebičnega obnašanja vozlišč. Sebična vozlišča, ki nočejo
sodelovati z drugimi vozlišči, namreč vodijo do
neoptimalnega ravnovesja. Takšne sheme cenitev se
imenujejo mehanizmi spodbujanja [9]. Obstajajo tudi
drugi tipi spodbujevalnih mehanizmov, ki se na splošno
delijo v dve kategoriji. Prva so mehanizmi na podlagi
izmenjave kreditov, ki temeljijo na (i) nagrajevanju
vozlišč s kreditom pri sodelovanju z drugimi vozlišči ter
(ii) zaračunavanju kreditov pri povpraševanju po
storitvah drugih vozlišč. Druga kategorija pa so
mehanizmi na osnovi ugleda, ki temeljijo na (i) dajanju
pozitivnega mnenja vozliščem pri sodelovanju z
drugimi vozlišči in (ii) dajanju negativnega mnenja
vozliščem, ki se obnašajo sebično, z namenom, da jih
lahko sčasoma izvzamemo iz omrežja.
Predpostavka o racionalnosti igralcev ni primerna za
vsako situacijo, saj ta ne vodi vedno do optimalnega
stabilnega stanja. To upoštevajo tudi tehnike
mehanizmov spodbujanja in pomagajo pri doseganju le-
tega. Prav tako tudi ni mogoče predpostaviti
neskončnosti in popolne informacije znotraj igre v
primerih, ko je treba upoštevati dinamičnost brezžičnih
omrežij, npr. dinamičnost prenosnega medija, ki vnaša
določeno popačenje med opazovane akcije s strani
vozlišč. Pri predpostavki o popolni informaciji se lahko
zgodi, da se določeno vozlišče moti, ko označi drugo
vozliče za sebično, saj je lahko takšen sklep posledica
nepredvidljivega spreminjanja radijskega kanala pri
brezžični komunikaciji. Prav tako je v nekaterih
primerih pomembno, da se določeno vozlišče zaveda
dejstva, da bo izključeno ali celo odstranjeno:
interakcija z drugim igralcem se bo prekinila. V takem
primeru, npr., možnost poslati paket takoj in ne šele
pozneje, je izjemno pomembno in predpostavka o
neskončnosti ni primerna. V takšnih primerih je treba v
igro vpeljati vidik končnosti in nepopolnosti
informacije.
Teorija iger se lahko uporabi za optimizacijo
učinkovitosti na ravni vozlišča in tudi na omrežni ravni
[10]. Z upoštevanjem tega se uporabijo različne
kooperativne in nekooperativne sheme tako za
maksimiranje donosa vozlišč kot tudi omrežja kot
celote. Zaradi narave brezžičnih omrežij, v katerih si
morajo vozlišča deliti omejene skupne vire na
porazdeljen način, veljajo nekooperativne sheme za
obetavnejše od kooperativnih. Pogosto pa se izkaže, da
sodelovanje med vozlišči prinaša boljše rezultate in je
nenadomestljivo. To pa zahteva izmenjavo nujno
potrebnih informacij med vozlišči za sodelovanje med
njimi (signalizacija in sporazumi). Po zgledu iz
socialnih omrežij govorimo o pogajanjih in ustvarjanju
koalicij. Mogoče je kombinirati obe vrsti optimizacije,
in sicer na ravni vozlišča in omrežja, pri čemer pa
moramo biti izjemno previdni, kakšno kombinacijo
shem tvoriti.
Pogosto vključuje optimizacijski proces več kot samo
eno plast OSI-arhitekture in so potrebne različne
medplastne tehnike načrtovanja in optimizacije. S
pomočjo kombinacije različnih pristopov teorije iger na
različnih plasteh v brezžičnih omrežjih in primerno
izbranega akcijskega prostora v teoriji iger lahko v tem
primeru izvedemo medplastno optimizacijo [11].
V prihodnosti pričakujemo, da bodo vozlišča
avtonomni agenti in bodo sama sprejemala določene
odločitve, kot so npr. zamenjava modulacijske sheme
signala, neodvisno od porazdeljenega protokola, ki se
bo izvajal na samih vozliščih. Tudi v tem primeru je
lahko teorija iger uporabljena v optimizacijske namene
takšnega obnašanja vozlišč.
3.2 Uporaba teorije iger v brezžičnih omrežjih
Brezžična omrežja prihodnjih generacij naj bi bila
porazdeljena, samoorganizirajoča, dinamična omrežja,
ki bodo za svoje izvajanje potrebovala različne
mehanizme odločanja in optimizacijske tehnike, med
katerimi bo zagotovo tudi teorija iger. S tem namenom
so v nadaljevanju predstavljene nekatere uporabe teorije
iger, ki jih že danes zasledimo v literaturi kot predmet
raziskav različnih avtorjev.
3.2.1 Brezžična ad hoc/senzorska omrežja
V brezžičnih ad hoc omrežjih in brezžičnih senzorskih
omrežjih je največji problem omejena količina energije
vozlišč. Teorija iger se v tem primeru uporabi za
optimizacijo porabe energije vozlišč.
Na plasti MAC je teorija iger uporabljena za
izvajanje ALOHA in CSMA/CA protokolov dostopa do
kanala.
Pri usmerjanju v več etapah morajo vozlišča
posredovati pakete drugih vozlišč, zato morajo pri tem
sodelovati med seboj. Teorija iger se uporabi kot orodje
za odločanje vozlišč o sodelovanju pri posredovanju
paketov in za osamitev/odstranitev sebičnih vozlišč, ki
nočejo sodelovati pri posredovanju paketov, iz omrežja.
Usmerjanje prometa v brezžičnih ad hoc/senzorskih
omrežjih je drugačno od usmerjanja prometa v navadnih
omrežjih. Ker so vozlišča naprave z omejeno količino
energije in ker je vloga vsakega vozlišča izjemnega
pomena, je poraba energije najpomembnejši dejavnik
UPORABA TEORIJE IGER V BREZŽIČNIH OMREŽJIH 291
pri načrtovanju usmerjevalnih protokolov. Na podlagi
količine energije vozlišč in koristi vozlišč od usmerjanja
se s pomočjo teorije iger modelira igra, v kateri se
odloča o usmerjanju prometa v omrežju.
3.2.2 Radijska dostopovna/celična omrežja
Nadzor nad močjo oddajanja je v brezžičnih omrežjih
nujen za omejevanje interference med različnimi
uporabniki. V tem primeru s pomočjo teorije iger
oblikujemo igro, ki se uporabi za minimizacijo/
dodeljevanje/zaračunavanje oddajnih moči vozlišč v
OFDM in CDMA sistemih radijskih dostopovnih/
celičnih omrežij.
V sistemih MIMO s pomočjo teorije iger opišemo in
nadziramo so-kanalno interferenco različnih povezav
glede na razmerje podatkovne prenosne hitrosti in
potrebne oddajne moči.
Teorijo iger lahko prav tako uporabimo za krmiljenje
dopuščanja zveze v različnih situacijah, kot so npr.
doseganje zahtevane kakovosti storitve, izbira
omrežnega operaterja, preprečevanje/izogibanje
zamašitev, učinkovita izraba omejene pasovne širine itd.
Izbor celice oziroma najprimernejše bazne postaje je
proces, ki zagotavlja storitve mobilnemu terminalu.
Optimalen izbor lahko dosežemo tudi s pomočjo teorije
iger.
3.2.3 Transportna/hrbtenična omrežja
Pri teh omrežjih je še posebej pomembna zmogljivost
omrežja. V tem primeru je mogoče teorijo iger uporabiti
za maksimiranje pretoka prometa. Prav tako lahko
teorijo iger uporabimo za izbor najzanesljivejše poti za
pretok/prenos prometa skozi brezžično zaledno omrežje.
3.2.4 Kognitivna (radijska) omrežja
Koncept kognitivnih komunikacij temelji na
predpostavki, da se naprave zavedajo svoje okolice in
temu ustrezno prilagajajo svoje obratovalne parametre.
Koncept se uvaja v omrežja prihodnjih generacij na
različnih segmentih, od posameznih naprav do
dostopovnih in tudi transportnih omrežij, dejanska
implementacija s strani različnih raziskovalnih skupin
pa pogosto temelji prav na uporabi teorije iger.
Teorija iger se v kognitivnih radijskih omrežjih
uporablja pri dinamičnem dodeljevanju frekvenčnega
spektra sekundarnim uporabnikom, souporabi skupnega
frekvenčnega spektra, nastavljanju oddajnih moči ali
celo spreminjanju prenosnih parametrov in karakteristik,
kot so npr. modulacija, tip kodiranja itd.
4 UPORABA POTENCIALNE IGRE ZA
PORAZDELJENO NASTAVITEV ODDAJNIH MOČI
Pri inženirskih aplikacijah, med katere spada tudi
optimizacija uporabe radijskih virov v brezžičnih
omrežjih, se pogosto uporabljajo potencialne igre [12].
V nadaljevanju je predstavljen primer modela ordinalne
potencialne igre s sebičnimi strategijami.
4.1 Krmiljenje oddajnih moči v relejnem
brezžičnem omrežju
Uporabo modela ordinalne potencialne igre bomo
pokazali na primeru krmiljenja oddajnih moči
oddajnikov v relejnem (posredovalnem) brezžičnem
omrežju, prikazanem na sliki 1. Vsako relejno vozlišče
je hkrati zbirno vozlišče brezžičnega senzorskega
omrežja v svoji bližini.
Po zgledu iz [7] smo v okolju Matlab modelirali
potencialno igro Γ =	 〈�, �, 	〉. Relejni oddajniki/
sprejemniki (Rx/Tx) � = {1,2, … ,9} v verigi
posredujejo promet od � = 1 preko � = 2 vse do
� = 9. Slednji posreduje promet do končnega
sprejemnika (označen z 10), ki je prehodno vozlišče in v
tem primeru ni igralec. � so oddajne moči oddajnikov,
ki jih nastavljamo pri optimizaciji. 	 so potencialne
funkcije igralcev. Vozlišča so med seboj oddaljena en
kilometer. Ker so relejna vozlišča � hkrati tudi zbirna
vozlišča brezžičnih senzorskih omrežij (WSN), se
promet proti prehodnemu vozlišču povečuje. To
pomeni, da relejna vozlišča, ki so bliže prehodnemu
vozlišču, potrebujejo večje razmerje signal šum (8/�).
Pasovna širina posameznih povezav med vozlišči znaša
: = 1	;<=. Za prometno obremenitev iz posameznih
WSN smo privzeli 1	;>�?/�. Slika 2 prikazuje
nastavljanje posameznih oddajnih moči vozlišč
(označena na sliki s številkami od 1 do 9) prek več
iteracij pri pritočni obremenitvi posameznih WSN
1	;>�?/�, ki zahteva zmogljivosti posameznih povezav
@ = 1/2/3/4/5/6/7/8/9	;>�?/�. Potencialne
funkcije igralcev odražajo minimalno zahtevano moč
oddajanja posameznih oddajnikov, ki je potrebna za (i)
premagovanje izgub poti, termičnega šuma in
interference, ki jo povzročajo drugi oddajniki, in (ii)
zadovoljevanje zahtevanega razmerja 8/�. Pri tem
predpostavimo, da imamo »idealno« usmerjene
sprejemne antene tako, da oddajniki povzročajo
interferenco samo na sprejemnikih, ki jim sledijo v
verigi proti prehodnemu vozlišču. Oddajniki nastavljajo
moči enostransko, brez poznavanja oddajnih moči
Slika 1: Krmiljenje oddajnih moči v relejnem brezžičnem omrežju s pomočjo potencialne igre
292 PERTOVT, JAVORNIK, MOHORČIČ
Slika 2: Moči na oddajnikih v posameznih iteracijah
drugih oddajnikov. To pomeni, da se ne ozirajo na
strategije preostalih, kar ustreza definiciji sebičnih
strategij. Moči oddajnikov so na začetku nastavljene na
nič, nato pa se prek iteracij povečujejo v skladu z
vplivom interferenc preostalih oddajnikov v verigi. Če
moči na oddajnikih še ne dosegajo želenih pogojev
omrežja, je koristnost oddajnika, ki jo odraža
potencialna funkcija oddajnika, negativna.  Ko doseže
koristnost vsakega vozlišča vrednost nič, se postavi
omrežje v stabilno točko in oddajne moči vseh
oddajnikov so optimalno nastavljene. Iz slike 2 vidimo,
da doseže omrežje stabilno točko po devetih iteracijah
nastavljanja moči oddajnikov, ki pomenijo PUNR [7].
Devet iteracij je potrebnih zaradi prilagajanja oddajnih
moči premagovanju povečujočih se interferenc vseh
oddajnikov, ki sledijo določenemu oddajniku v verigi.
5 SKLEP
V članku smo predstavili osnovne pojme in lastnosti
teorije iger, ki smo jih v nadaljevanju razširili na
uporabo teorije iger v brezžičnih omrežjih. Posebno
kategorijo teorije iger, t.i. potencialne igre, smo
uporabili pri zasnovi modela za porazdeljeno nastavitev
oddajnih moči vozlišč v brezžičnem relejnem omrežju,
pri čemer smo želeli moči optimalno nastaviti. Slednje
dosežemo v Pareto učinkovitem Nashevem ravnovesju.
Z uvajanjem heterogenih omrežij in koncepta
kognitivnih komunikacij dobiva teorija iger čedalje
večjo veljavo tudi na področju brezžičnih omrežij, saj je
učinkovito orodje za modeliranje, analizo in
optimizacijo. Kot pa prikazujemo v članku, je za
uporabo teorije iger v brezžičnih omrežjih ključnega
pomena izbrati pravi tip igre za dani primer ter določiti
primerne mehanizme spodbujanja sodelovanja in
funkcije donosov posameznih igralcev.