UNIVERZITET U BEOGRADU ELEKTROTEHNIČKI FAKULTET Vladimir D. Vuković EFIKASNI ARQ ALGORITMI BAZIRANI NA MAJORITETNOJ LOGICI doktorska disertacija Beograd, 2012 i UNIVERSITY OF BELGRADE SCHOOL OF ELECTRICAL ENGINEERING Vladimir D. Vuković EFFICIENT ARQ ALGORITHMS BASED ON MAJORITY LOGIC DECISION Doctoral Dissertation Belgrade, 2012 ii Informacije o mentoru i članovima komisije Mentor: 1. dr Aleksandra Smiljanić, vanredni profesor Elektrotehnički fakultet Univerziteta u Beogradu Članovi komisije: 2. dr Predrag Ivaniš, docent Elektrotehnički fakultet Univerziteta u Beogradu 3. dr Ljiljana Trajković, redovni profesor School of Engineering Science, Simon Fraser University, Vancouver, British Columbia, Canada Datum odbrane: _________________ Datum promocije: _________________ iii Zahvalnica Veliko hvala svima koji su imali razumevanja svih ovih godina. Veliko hvala mojoj dragoj profesorki Aleksandri Smiljanić. Veliko hvala mojoj dragoj profesorki Ljiljani Trajković. Veliko hvala mom dragom profesoru Grozdanu Petroviću. iv REZIME Naslov disertacije: Efikasni ARQ algoritmi bazirani na majoritetnoj logici Primena diverziti tehnike i majoritetnog kombinovanja paketa predstavlja jednostavno i atraktivno rešenje za kontrolu grešaka u bežičnim telekomunikacionim sistemima. Ove tehnike su posebno interesantne u paketski orijentisanim mrežama sa višestrukim putanjama i kooperativnim mrežama sa jednom ili više predajnih i prijemnih antena. Tipičan primer su bežične senzorske mreže koje često rade u ekstremno otežanim uslovima prenosa, pri čemu zahtevi za pouzdanim prenosom imaju veći prioritet od zahteva za racionalnim korišćenjem komunikacionih kapaciteta. Teorijski i aproksimativni izrazi za verovatnoću pogrešnog prenosa paketa u slučaju proizvoljnog broja kanala sa različitim verovatnoćama grešaka predstavljaju ključne parametre za procenu energetske efikasnosti senzorskih čvorova. Cilj rada: U okviru ove problematike, u tezi su postavljeni sledeći ciljevi: (i) da se dobiju teorijski izrazi za verovatnoću pogrešnog prenosa paketa u slučaju primene selektivnog i majoritetnog odlučivanja, u uslovima kada su verovatnoće grešaka različite na različitim putanjama i kada je broj mogućih paralelnih putanja proizvoljan; analitički izrazi su veoma bitni prilikom odreĎivanja optimalnog broja putanja u senzorskoj mreži sa ciljem maksimalne uštede potrošnje energije u senzorskim čvorovima, (ii) da se analizira efikasnost hibridne ARQ šeme imajući u vidu različita scenarija pristizanja paketa u odredišni čvor; naime, prisustvo prostornih putanja pri kojima su na pojedim putanjama uslovi prenosa loši, ne obezbeĎuje garantovano prepoznavanje paketa i prenos po svim putanjama, tako da se uslovi za majoritetno odlučivanje mogu obezbediti posle jedne ili više retransmisija; zbog toga, realni scenario je kombinacija prostornog i vremenskog diverzitija u korist jednog ili drugog scenarija, (iii) da se sagleda mogućnost implementacije imajući u vidu korišćenje poznatih standarda i postojećih hardverskih i softverskih rešenja koja se koriste u senzorskim mrežama; posebno težište je bilo dato modifikaciji rešenja neohodnih za implementaciju korekcije grešaka na bazi majoritetnog kombinovanja paketa. OdreĎivanje izraza za verovatnoću retransmisije predstavlja izazovni problem, posebno složen kada je broj nezavisnih putanja proizvoljan. To je bio osnovni razlog da su gotovo svi autori u objavljenim istraživanjima usvajali nerealnu pretpostavku da su kanalne verovatnoće grešaka (Bit Error Rate, BER) po nezavisnim putanjama brojčano jednake. Čak i pri tim uslovima, većina autora se ograničava na razmatranje samo tri putanje. Izuzetak predstavljaju radovi Carsona Lama i koautora u kojima se daju opšta rešenja za proizvoljni broj putanja (kanala). Za razliku od ovog pristupa, postavljen je cilj da se izvede opšta formula kako za proizvoljan broj nezavisnih putanja, tako i za različite vrednosti kanalnih verovatnoća. v Postojanje nezavisnih transmisionih putanja obezbeĎuje prijem više kopija istog okvira. U normalnim okolnostima, uprkos postojanju grešaka na pojedinim bitskim pozicijama, pretpostavimo da će prisustvo svih okvira biti ispravno detektovano. U tom slučaju, na prijemnoj strani će postojati potpun komplet okvira, tako da će se, ukoliko je potrebno, primeniti majoritetno kombinovanje. MeĎutim, takoĎe je realna mogućnost da se ne prepozna prisustvo prenetog okvira. To će imati za posledicu “deficit” paketa, koji se mora nadoknaditi tokom narednih retransmisija. Mogući su veoma različiti scenariji prikupljanja paketa za majoritetno odlučivanje, od toga da se problem reši posle prve retransmisije, do slučaja kada broj retransmisija mora biti jednak ili veći od broja nezavisnih putanja. TakoĎe, posle pojedinih retransmisija, može doći do “suficita” paketa koji se mogu koristiti za majoritetno odlučivanje, tako da se u takvim prilikama javlja problem izbora pogodnih “kandidata” za ovo odlučivanje. U svakom slučaju, potreba za retransmisijom utiče na smanjenje efikasnosti primenjene metode, pa je od interesa da se ovaj problem detaljnije ispita. Sa ciljem dobijanja okvirnog uvida u propusnost, odabrana su tri karakteristična scenarija od kojih dva daju granične slučajeve, jedan koji odgovara čisto prostornom diverzitiju, i drugi, koji odgovara čisto vremenskom diverzitiju. Analiza je bila zasnovana na modelovanju procesa retransmisije posredstvom odgovarajućih Markovljevih modela koji su poslužili za odreĎivanje propusnosti na bazi srednje vrednosti trajanja retransmisionih ciklusa. Atraktivnost primene hibridne ARQ tehnike sa majoritetnim kombinovanjem zasniva se na većoj jednostavnosti realizacije u poreĎenju sa drugim hibridnim metodama. To nikako ne znači da je problem trivijalan ili krajnje jednostavan. Da bi se obezbedila uspešna realizacija, potrebno je sprovesti opsežnu analizu raspoloživih komponenti i modifikaciju dostupnih rešenja koja se koriste u bežičnim senzorskim mrežama. Pri tome, polazni okvir je bio: (i) da se utvrdi pogodna topološka i komunikaciona postavka senzorske mreže; (ii) da se razmotre i predlože izmene i modifikacije funkcija postojećeg protokola koje se odnose na kontrolu grešaka u okviru drugog sloja referentnog modela; (iii) da se sagledaju neophodne modifikacije primopredajnika dostupnih na komercijalnom tržištu; i (iv) da se bliže odrede hardverska i softverska rešenja koja omogućuju implementaciju majoritetnog kombinovanja. Metode istraživanja: Svakom od navedenih otvorenih pitanja pristupalo se kao zasebnim tematskim celinama, pri čemu su korišćeni posebni prikladni telekomunikacioni modeli i usvajane specifične pretpostavke kako bi se kompletno razmatranje učinilo jasnim i celishodnim. Kombinovane su metode teorijske i simulacione analize. Matematička analiza je vršena na bazi teorijskih modela uzimajući u obzir izvesna ograničenja koja podrazumevaju idealnu sinhronizaciju na nivou bita i okvira, sporopromenljivi kanal u odnosu na dužinu trajanja okvira, poznatu dužinu okvira i dr.. Kao pomoćno sredstvo prilikom računanja opšteg izraza za verovatnoću pogrešnog prenosa paketa u slučaju diverziti prenosa sa proizvoljnim brojem putanja, korišćeni su udžbenici iz kombinatorike, i to teorema uključivanja i isključivanja. Teorijski rezultati su verifikovani simulacijom realnih modela na računaru. vi Rezultati i zaključci: U tezi su izvršena značajna teorijska i praktična istraživanja koja su rezultirala sledećim doprinosima: (i) izveden je izraz u zatvorenom obliku za verovatnoću pogrešnog prenosa paketa za tri i pet kanala sa različitim kanalnim verovatnoćama, (ii) izveden je izraz za verovatnoću pogrešnog prenosa za proizvoljan broj kanala sa različitim kanalnim verovatnoćama; uraĎen je programski paket koji na bazi opšteg izraza računa verovatnoću pogrešnog prenosa paketa za proizvoljan broj kanala, različite dužine paketa i različite kanalne verovatnoće; uporedna analiza je pokazala da dodatna primena majoritetnog kombinovanja može značajno da smanji verovatnoću pogrešnog prenosa u odnosu na selektivno kombinovanje. (iii) razvijeni su pogodni aproksimativni izrazi koji omogućuju lakše sagledavanje uticaja pojedinih parametara kao što su broj kanala i dužina paketa, na verovatnoću pogrešnog prenosa, (iv) uveden je pojam ekvivalentne kanalne verovatnoće koja se može koristiti kao dobar reprezent kanala sa različitim verovatnoćama grešaka čiji značaj nije samo u pojednostavljenju složenog izraza za verovatnoću pogrešnog prenosa paketa, već i u jednodimenzionalnoj grafičkoj predstavi funkcije više promenljivih; pokazano je da se verovatnoća pogrešnog prenosa paketa relativno malo menja bez obzira na velike odnose pojedinih kanalnih verovatnoća, (v) razvijeni su modeli tri karakteristična scenarija prenosa paketa od izvornog do odredišnog čvora i izvedeni izrazi za propusnost na bazi retransmisionih ciklusa; analiziran je uticaj ključnih parametara kao što su broj kanala, dužina paketa i normalizovano kružno kašnjenje, (vi) rezultati istraživanja su ilustrovani na primeru jedne hipotetičke senzorske mreže; dat je predlog modifikacije standarda koji reguliše razmenu podataka u bežičnim senzorskim mrežama malog protoka; predloženo je da okvir sadrži dva posebna CRC polja koja nezavisno kontrolišu MAC heder i informacioni sadržaj okvira. Dalji razvoj: Buduća istraživanja se sagledavaju u dva pravca, teorijski i praktični. Kod teorijskih istraživanja, primenjena metodologija bi mogla da se proširi i na druge “tvrde” postupke kao što su generalizovano kombinovanje paketa i adaptivne varijante kombinovanja različitih postupaka. U praktičnim istraživanjima ima mogućnosti za detaljniju razradu hardverskih i softverskih rešenja u cilju realizacije pojedinih modula i funkcije majoritetnog kombinovanja paketa u okviru odgovarajućih standarda. Na kraju, napomenimo da posebno interesantnu oblast primene predstavljaju ne samo senzorske mreže, već i drugi tipovi mreža i telekomunikacionih sistema. Ključne reči: automatska retransmisija paketa, bežične senzorske mreže, diverziti, majoritetno kombinovanje, selektivno kombinovanje, propusnost, retransmisioni ciklus, verovatnoća greške po bitu, verovatnoća retransmisije. Naučna oblast: digitalne telekomunikacije. Uža naučna oblast: računarske mreže i protokoli. UDK broj: __________________. vii SUMMARY Dissertation title: Efficient ARQ algorithms based on majority logic decision The application of diversity technique and majority packet combining is a simple and attractive solution for error control in wireless telecommunication systems. These techniques are especially interesting in packet-oriented multipath and cooperative networks with one or more transmitting and receiving antennas. A typical example is wireless sensor network which often operates in extremely harsh conditions, where requirements for reliable packet transmission have a higher priority than requirements for efficient usage of communication capacities. Theoretical and approximate expressions of packet error probabilities in the case of an arbitrary number of channels with distinct channel error probabilities are key parameters for estimation of the energy efficiency of sensor nodes. Goal of research: As part of this problem, the thesis sets the following objectives: (i) to obtain theoretical expressions for packet error probability in the case of application of selective and majority decision when the number of parallel channels is arbitrary and channel error probabilities are distinct; analitical expressions are very important in determining the optimal number of paths in a sensor network in order to achieve maximum saving of energy in sensor nodes, (ii) to analyze the throughput efficiency of a hybrid ARQ scheme, considering various scenarios of packet receiving in the destination node; namely, the presence of spatial paths, with poor transmission conditions in certain paths, does not provide guaranteed detection and transmission of frame copies via all paths, so that the conditions for majority combining may be provided after one or more retransmissions; therefore, the real scenario is a combination of space and time diversity in favor of one or the other scenario, (iii) to examine the possibility of implementation of majority combining, having in mind the known standards and the usage of existing hardware and software solutions in sensor networks; the particular focus was given to the modification of solutions required for the implementation of error correction, based on majority packet combining. Determining an expression for the retransmission probability is a challenging problem, especially complex when the number of independent paths is arbitrary. It was the main reason why almost all authors of published research papers adopted an unrealistic assumption that channel error probabilities in independent paths are numerically equal. Even under such conditions, most authors have limited their research to only three paths. The exceptions are papers by Carson Lam and co-authors, in which general solutions for the arbitrary number of paths (channels) are given. In contrast to this approach, our goal was to derive the general expression that takes into account both the arbitrary number of paths and distinct values of channel probabilities. viii The existence of independent transmission paths enables the reception of more frame copies. Under normal circumstances, despite the errors in certain bit positions, let us assume that the presence of all frame copies will be properly detected. In that case, a complete set of frame copies will be available at the receiving side, so that, if necessary, majority combining can be applied. However, there is a real possibility that it does not recognize the presence of any transmitted frame copies. This will result in a “deficit” of frame copies, which must be compensated for by subsequent retransmissions. Various scenarios of packet collecting for majority decision are possible, such as the case of solving the problem after the first retransmission, or the case of solving the problem when the number of retransmissions must be equal or greater than the number of independent paths. Furthermore, after certain retransmissions, a “surplus” of frame copies can appear. In such circumstances, the surplus will create the problem of choosing a suitable “candidate” for majority decision-making. In any case, the need for retransmission will reduce the efficiency of the applied method, and it is of interest to investigate this problem further. In order to obtain an insight in the throughput, three typical scenarios are selected. Two of them represent extreme cases: one corresponds to pure space diversity, whereas the other one corresponds to pure time diversity. The analysis was based on the modeling of the retransmission process, by using appropriate Markov models to determine the throughput efficiency based on the mean duration of retransmission cycles. The attractiveness of applying hybrid ARQ with majority combining scheme lies in higher simplicity of realization in comparison with other hybrid methods. This definitely does not mean that the problem is trivial or extremely simple. To ensure effective implementation, it requires extensive analysis of available components and modification of available solutions used in wireless sensor networks. In addition, the initial framework was: (i) to determine the suitable topological and communication setup of the sensor network; (ii) to consider and propose modifications to the functions of valid protocols related to error control in the second layer of the reference model, (iii) to consider the necessary modifications to transceivers available on the commercial market; and (iv) to specify in detail the hardware and software solutions that enable the implementation of majority combining. Research methods: Each of these outstanding issues have been approached as a separate topic, using special appropriate telecommunication models and making specific assumptions to ensure the clarity and relevance of the entire consideration. Theoretical and simulation methods have been combined. Mathematical analysis has been performed based on theoretical models, taking into account certain constrains that imply perfect bit and frame synchronization, slowly time-varying channel in relation to frame duration, known frame length, etc. As an aid in derivation of the general expression for packet error probability in the case of diversity transmission with an arbitrary number of paths, the principle of inclusion and exclusion from the combinatorics has been used. Theoretical results have been verified by computer simulation of realistic models. ix Results and conclusions: The thesis has included important theoretical and practical research, which resulted in the following contributions: (i) the close-form expression is derived for the packet error probability for three and five channels with distinct channel error probabilities, (ii) an expression is derived for the packet error probability in the case of an arbitrary number of channels with distinct channel error probabilities; a software package based on the general expression has been created to calculate the packet error probability for arbitrary number of paths, various frame lengths and distinct channel error probabilities; the comparative analysis has shown that an additional application of majority combining can significantly reduce the transmission error probability compared to selective combining. (iii) suitable approximate expressions have been developed, allowing for easier understanding of the effect of certain parameters, such as the number of channels and frame length, on the transmission error probability, (iv) the concept of equivalent channel probability has been introduced, which can be used as a good representation of channels with distinct error probabilities, whose importance is not only in the simplification of a complex expression for the packet error probability, but also in the one-dimensional graphics representation of a function of several variables; it has been illustrated that packet error probability changes a little irrespective of the relations between individual channel error probabilities, (v) models of three typical scenarios of packet transmission from a source to a destination node have been developed and expressions for the throughput efficiency based on retransmission cycles have been derived; the effect of key parameters, such as the number of channels, packet length and normalized round trip delay have been analyzed, (vi) research results have been illustrated in a hypotetical sensor network; the proposal for modification of the standard that regulates the exchange of data in low rate wireless sensor networks has been given; it has been proposed that a frame should contain two separate CRC fields which independently control MAC header and data payload fields. Further development: The future research is envisaged in two directions - theoretical and practical. In theoretical research, the applied methodology could be extended to other “hard” procedures, such as generalized packet combining and the adaptive versions of various combining procedures. In practical research, there are possibilities for more detailed elaboration of hardware and software solutions, with a view to implementing individual modules and functions of majority packet combining under appropriate standards. Finally, it is fair to say that particularly interesting area of application are not only sensor networks, but also other types of networks and telecommunication systems. Key words: automatic repeat request, wireless sensor networks, diversity, majority packet combining, selective packet combining, throughput, retransmission cycles, bit error probability, retransmission probability. Scientific area: Digital telecommunications. Sub-scientific area: Computer networks and protocols. UDC number: _________________. 1 UNIVERZITET U BEOGRADU ELEKTROTEHNIĈKI FAKULTET EFIKASNI ARQ ALGORITMI BAZIRANI NA MAJORITETNOJ LOGICI – Doktorska disertacija – Kandidat: Mentor: Vladimir Vuković prof. dr Aleksandra Smiljanić Beograd, 2012. 2 SADRŽAJ SADRŽAJ .......................................................................................................................................................................... 2 1. UVOD ....................................................................................................................................................................... 4 1.1. MREŢNO OKRUŢENJE ........................................................................................................................................ 5 1.2. TELEKOMUNIKACIONI MODEL .......................................................................................................................... 6 1.3. MOTIV I ORGANIZACIJA TEZE ........................................................................................................................... 7 2. VEROVATNOĆA RETRANSMISIJE ............................................................................................................... 10 2.1. TEORIJSKI MODEL SC+MC PROCEDURE ......................................................................................................... 10 2.2. SC+MC PROCEDURA ZA TRI KANALA ............................................................................................................. 13 2.2.1. Egzaktni izraz za verovatnoću retransmisije ............................................................................................. 13 2.2.2. Aproksimativni izrazi za verovatnoću retransmisije ................................................................................. 16 2.2.3. Uticaj rasejavanja kanalnih verovatnoća ................................................................................................. 19 2.3. SC+MC PROCEDURA ZA PET KANALA ............................................................................................................ 21 2.3.1. Egzaktni izraz za verovatnoću retransmisije ............................................................................................. 21 2.3.2. Aproksimativni izrazi za verovatnoću retransmisije ................................................................................. 24 2.4. SC+MC PROCEDURA ZA OPŠTI BROJ KANALA ................................................................................................ 26 2.4.1. Metodologija za računanje verovatnoće retransmisije ............................................................................. 26 2.4.2. Preliminarne definicije, oznake i pomoćne veličine .................................................................................. 28 2.4.3. Izraz za verovatnoću retransmisije za opšti broj kanala ........................................................................... 31 2.5. EFIKASNOST SC+MC PROCEDURE ................................................................................................................. 35 2.5.1. Uporedni pregled SC i SC+MC procedura .............................................................................................. 36 2.5.2. Analiza doprinosa MC procedure ............................................................................................................. 40 2.5.3. Analiza dobitka MC procedure ................................................................................................................. 43 3. ANALIZA PROPUSNOSTI ................................................................................................................................. 45 3.1. KARAKTERISTIĈNI SCENARIJI ......................................................................................................................... 45 3.2. ANALIZA SCENARIJA B1 ................................................................................................................................. 48 3.2.1. Opis procedure ......................................................................................................................................... 48 3.2.2. Matematički model .................................................................................................................................... 49 3.2.3. Simulacioni model ..................................................................................................................................... 52 3.2.4. Rezultati analize ........................................................................................................................................ 56 3.3. ANALIZA SCENARIJA B2 ................................................................................................................................. 56 3.3.1. Opis procedure ......................................................................................................................................... 56 3.3.2. Matematički model .................................................................................................................................... 58 3.3.3. Simulacioni model ..................................................................................................................................... 61 3.3.4. Rezultati analize ........................................................................................................................................ 63 3.4. ANALIZA SCENARIJA B3 ................................................................................................................................. 63 3.4.1. Opis procedure ......................................................................................................................................... 63 3.4.2. Matematički model .................................................................................................................................... 65 3.4.3. Simulacioni model ..................................................................................................................................... 68 3.4.4. Rezultati analize ........................................................................................................................................ 70 3.5. UPOREDNA ANALIZA ...................................................................................................................................... 70 3.5.1. Analiza uticaja broja kanala ..................................................................................................................... 71 3.5.2. Analiza uticaja dužine okvira .................................................................................................................... 72 3.5.3. Analiza uticaja kružnog kašnjenja ............................................................................................................ 73 3 4. ELEMENTI IMPLEMENTACIJE ..................................................................................................................... 74 4.1. MODIFIKACIJA IEEE 802.15.4 STANDARDA ................................................................................................... 74 4.2. PRIMER HIPOTETIĈKE MREŢE .......................................................................................................................... 77 4.3. OPIS PROCEDURE ............................................................................................................................................ 78 4.4. PREDLOG IMPLEMENTACIJE ............................................................................................................................ 81 5. ZAKLJUĈAK ........................................................................................................................................................ 83 LITERATURA ................................................................................................................................................................ 86 A. OPIS PROGRAMSKOG PAKETA .................................................................................................................... 89 A.1. PRIPREMA KODA ............................................................................................................................................. 89 A.2. LISTINZI PROGRAMA ....................................................................................................................................... 91 B. RAĈUNANJE PRELAZNIH VEROVATNOĆA ............................................................................................. 101 B.1. PRELIMINARNE DEFINICIJE I OZNAKE ............................................................................................................ 101 B.2. RAĈUNANJE PRELAZNIH VEROVATNOĆA ...................................................................................................... 102 C. SPISAK SKRAĆENICA..................................................................................................................................... 114 D. SPISAK SIMBOLA ............................................................................................................................................ 115 E. SPISAK SLIKA ................................................................................................................................................... 116 F. SPISAK TABELA ............................................................................................................................................... 118 4 1. UVOD U savremenim beţiĉnim telekomunikacionim sistemima se primenjuju tri osnovne tehnike za kontrolu grešaka na liniji: automatska retransmisija paketa (Automatic Repeat reQuest – ARQ), korekcija grešaka unapred (Forward Error Control – FEC) i diverziti (Diversity) [1] – [5]. ARQ tehnike se zasnivaju na ponavljanju prenosa u uslovima postojanja grešaka na liniji. Po prijemu paketa iz mreţnog sloja OSI (Open Systems Interconnection) referentnog modela, u sloju veze se formira okvir tako što se paketu pored kontrolnih polja u zaglavlju (header), dodaje i CRC (Cyclic Redundancy Check) polje za detekciju grešaka na prijemu. Kada okvir stigne u prijemnik, najpre se vrši provera CRC bita, i ako je okvir ispravan, izdvojeni paket se prosleĊuje sloju mreţe, a predajniku se preko povratnog kanala šalje pozitivna potvrda prijema (Acknowledgement, ACK). U suprotnom, ukoliko je prenos pogrešan, prijemnik moţe, a ne mora, da šalje negativnu potvrdu prijema (NAK) koja inicira retransmisiju okvira. Postupak retransmisije se ponavlja sve dok prijemnik ne primi ispravnu poruku. Postoje tri osnovna tipa ARQ protokola: “stani i ĉekaj” (Stop- and-Wait, SW), “vrati se za N” (Go-Back-N, GBN) i “selektivno ponavljanje” (Selective Repeat, SR) koji su detaljno opisani u literaturi [1]. FEC tehnike su znatno sloţenije. Pored informacionih bita, prenosi se i odreĊeni broj redudantnih bita koji sluţe za korekciju grešaka u prenosu. Paket se isporuĉuje korisniku bez obzira na uspešnost korekcije greške. Na taj naĉin, FEC tehnike obezbeĊuju konstantnu propusnu efikasnost, dok pouzdanost opada sa porastom verovatnoće greške. Treba dodati da ova tehnika ne zahteva pomoćni kanal, tako da je u sluĉaju jednosmernog kanala, jedino moguće rešenje. Svaka od prethodno opisanih tehnika ima svoje prednosti i nedostatke. ARQ sistemi su jednostavni za implementaciju i nude veliku efikasnost pri malim verovatnoćama grešaka u kanalu. MeĊutim, pri velikim verovatnoćama grešaka i pri velikoj duţini paketa, ovi sistemi postaju neefikasni zbog velikog broja retransmisija u prenosu. Za razliku od ARQ sistema, u FEC sistemima nema retransmisija, tako da je efikasnost sistema konstantna i odreĊena kodnim koliĉnikom, bez obzira na uslove prenosa u kanalu. Ovo svakako predstavlja prednost u odnosu na ARQ sisteme, ali je pouzdanost i sloţena implementacija zaštitnog koda još uvek veliki nedostatak FEC sistema. Pogodnom kombinacijom ARQ i FEC postupaka, dobija se veća efikasnost od ARQ sistema i veća pouzdanost od FEC sistema. Ove tehnike se nazivaju hibridne (Hybrid Automatic Repeat reQuest, HARQ) procedure. Diverziti tehnike se zasnivaju na višestrukom ponavljanju paketa i mekom i tvrdom odluĉivanju (soft ili hard decision bit combining) u zavisnosti od toga da li se obrada signala vrši pre ili posle odluĉivaĉa. Meki kombajner se realizuje na fiziĉkom sloju, neposredno ispred odluĉivaĉa i zasniva se na ĉinjenici da je srednja vrednost aditivnog Gausovog šuma jednaka nuli. Za svaki od kanala, na izlazu demodulatora se vrši kvantizacija superponiranog korisnog signala i šuma u ritmu bitske uĉestanosti. Dobijene vrednosti za iste bitske pozicije se sabiraju kako bi se izvršilo potiskivanje šuma iz korisnog signala. Tvrdi kombajner se realizuju na sloju veze, neposredno iza odluĉivaĉa. Osnovna ideja je u višestrukom emitovanju kopija istog okvira i selektivnom ispitivanju ispravnosti svake kopije. Na ovaj jednostavan metod, prirodno se nadovezuje naredni korak, da se primljene kopije iskoriste i za korekciju grešaka primenom vrlo 5 jednostavnih mehanizama baziranih na sabiranju po modulu 2 ili većinskom kriterijumu odluĉivanja pre nego što se utvrdi potreba za retransmisijom [6] – [8]. Diverziti tehnika u sprezi sa majoritetnom logikom predstavlja jednostavan, ali ujedno i moćan alat za kontrolu grešaka u beţiĉnim telekomunikacionim sistemima. Osnovna ideja leţi u korišćenju višestrukog prenosa kopija istog okvira i ako je potrebno, eventualnom kombinovanju pogrešnih kopija kako bi se regenerisao ispravni okvir. Ovo rešenje se realizuje kao deo hibridnog ARQ protokola sa ciljem da se poveća pouzdanost prenosa, a sa smanjenjem broja retransmisija, i efikasnost sistema. Dekoder na bazi majoritetnog odluĉivanja prvi je uveo Irving S. Reed, davne 1954. godine [9], da bi ga detaljno razradio J. L. Massey, 1963. godine [2]. Široka primena leţi u veoma jednostavnoj realizaciji dekodera koja se sastoji od par serijsko-paralelnih šift registara i nekoliko logiĉkih kola. U literaturi su predloţene razliĉite šeme sa tvrdim kombinovanjem paketa: xor kombinovanje (xor combining) [10] – [11], majoritetno kombinovanje (majority combining) [12] – [13], kao i šeme nastale njihovom modifikacijom koje su oznaĉene kao generalizovano [13], agresivno [14], i ponderisano majoritetno kombinovanje [15]. Prvu kombinacionu šemu, oznaĉenu kao xor kombinovanje je predloţio Sindhu [6]. Radi se o vrlo jednostavnoj tehnici detekcije jednostrukih grešaka baziranoj na sabiranju po modulu 2 sadrţaja na istim bitskim pozicijama u dve pogrešne kopije okvira. Ukoliko je broj detektovanih grešaka manji od neke unapred zadate vrednosti koja je odreĊena raspoloţivim vremenom obrade, sledi postupak korekcije grešaka. Bira se jedna od mogućih kombinacija grešaka koja se sabira po modulu 2 (inverzija uslovno pogrešnih bita) sa jednom od dve pogrešne kopije okvira. Posle svake inverzije bita vrši se provera ispravnosti novonastalog okvira. Postupak se ponavlja sve dok se ne dobije okvir bez greške ili dok se ne “proĊe” kroz sve kombinacije grešaka. Ukoliko je regenerisana kopija ispravna, prenos se proglašava uspešnim. U suprotnom, ukoliko je broj detektovanih grešaka veći od dozvoljene vrednosti, ili ako se na nekoj od bitskih pozicija pojavila dvostruka greška, zahteva se retransmisija okvira. Drugu kombinacionu šemu, oznaĉenu kao majoritetno kombinovanje je predloţio Wicker [8]. Zasniva se na većinskom kriterijumu odluĉivanja na istoj bitskoj poziciji u proizvoljnom broju kopija okvira i proveri ispravnosti tako nastalog okvira. Ukoliko je regenerisana kopija ispravna, prenos se proglašava uspešnim i odgovarajući paket se prosleĊuje korisniku. U suprotnom, ukoliko je rezultujuća kopija neispravna, prenos se proglašava neuspešnim i zahteva se retransmisija novog okvira. Za razliku od xor kombinovanja, majoritetno kombinovanje nema ograniĉenja u pogledu vremena obrade. 1.1. Mrežno okruženje Diverziti tehnike za kontrolu grešaka su posebno interesantne u mreţama sa višestrukim putanjama i kooperativnim mreţama koje koriste linkove sa jednom ili više predajnih i prijemnih antena. Na slici 1.1 je prikazana topologija jedne tipiĉne mreţe sa višestrukim putanjama [16]. Ova mreţa se sastoji od velikog broja ĉvorova koji u komunikacionom smislu mogu biti izvorni (Source Node, SN), relejni (Relay Node, RN) ili odredišni (Destination Node, DN). U cilju obezbeĊenja pouzdanog prenosa informacija, do odredišta stiţu kopije istog okvira što omogućuje primenu kombinovanih tehnika za detekciju i korekciju grešaka na prvom i drugom sloju referentnog modela. Klasiĉan pristup podrazumeva primenu mekog kombinovanja koje se realizuje na fiziĉkom sloju. Postoji više razliĉitih tehnika koje su u literaturi oznaĉene kao Selection Combining, Threshold Combining, Equal-Gain Combining i Maximal-Ratio Combining, koja je svakako i najpoznatija [17]. Iako daje dobre rezultate, ovakav pristup se ne moţe uvek primeniti, pogotovo u paketski orijentisanim mreţama koje su realizovane komercijalnim primopredajnicima. Tipiĉan primer su beţiĉne senzorske mreţe koje koriste integrisana ulazno-izlazna kola koja rade u skladu sa IEEE 802.15.4 i ZigBee standardima [18]. Ove mreţe su našle primenu u velikom broju industrijskih, nauĉnih, medicinskih, i drugih aplikacija. Njihova masovna primena je uticala da 6 konstruktori posebnu paţnju obrate na dimenzije senzorskog ĉvora, malu potrošnju i nisku cenu proizvodnje, a potreba za visokom pouzdanošću prenosa je uslovila primenu postupaka za detekciju i korekciju grešaka baziranih na tehnikama tvrdog kombinovanja koje se realizuju na sloju veze kao deo hibridnih ARQ šema [19] – [20]. Relejni čvoroviIzvorni čvor Odredišni čvor p1 p2 pm m Slika 1.1. Topologija jedne tipiĉne mreže sa višestrukim putanjama. Generalno, sam proces istraţivanja je veoma sloţen i obuhvata ĉitav niz otvorenih tema posebno onih koje se odnose na realizaciju funkcija prva tri sloja komunikacione arhitekture. Tu se podrazumevaju pitanja vezana za modele propagacije akustiĉkog ili elektromagnetnog signala, primene pogodnih postupka modulacije i kodovanja, postupaka sinhronizacije na nivou nosioca, bita i okvira, zatim pitanja vezana za adresiranje, rutiranje i realizaciju relejnih funkcija i sl.. Odgovore na ova pitanja moţemo sagledati kroz telekomunikacione modele koji se odnose na rešavanje pojedinaĉnih problema usvajajući idealizovano okruţenje. 1.2. Telekomunikacioni model U tezi je usvojen pojednostavljeni telekomunikacioni model ARQ šeme sa majoritetnim kombinovanjem prikazan na slici 1.2. Predajni i prijemni delovi modela su povezani sa m meĊusobno nezavisnih kanala sa razliĉitim verovatnoćama grešaka po bitu, kk qp 1 , ),,2,1( mk  . Predajni deo se sastoji od ARQ bloka i predajnika. Zadatak ARQ bloka je da obezbedi formiranje okvira FT (HT, IT) i sve funkcije neohodne za njegovu retransmisiju. Svaki od m kanala se koristi za prenos identiĉne kopije okvira koja se na predajnoj strani sastoji od korisniĉkog paketa (IT) i zaglavlja (HT) sa CRC bitima za detektovanje grešaka pri prenosu paketa. Zaglavlje HT sadrţi podatke koji nose informaciju o poĉetku, duţini i rednom broju okvira, kao i sopstvene kontrolne i zaštitne bite potrebne za korekciju grešaka. Svi ovi podaci su neophodni za pouzdano prepoznavanje i identifikaciju kopije okvira na prijemnoj strani. Prijemni deo se sastoji od m prijemnika i bafera sa registrima R1, R2,..., i Rm u koje se privremeno smešta najviše m uzastopnih kopija istog okvira. Prijem okvira se odvija u dve faze. U prvoj fazi se vrši detekcija, identifikacija i memorisanje okvira. Sa ciljem da se korisniku na prijemnoj strani prosledi verna replika IR paketa IT, u drugoj fazi prijema se vrši detekcija i korekcija postojećih grešaka primenom metode kombinovanog odluĉivanja. Ovo kombinovano 7 odluĉivanje se sastoji od dva koraka. U prvom koraku, nazvanom selektivno kombinovanje (ili kratko SC), primenom CRC procedure se vrši pojedinaĉno ispitivanje prenetih kopija F1, F2, …, Fm onim redosledom kako pristiţu. Ukoliko se u nekom od kanala detektuje okvir bez greške, ukupni prenos se proglašava uspešnim, predajnoj stanici se šalje ACK, a odgovarajući paket se prosleĊuje korisniku. Drugi korak, nazvan majoritetno kombinovanje (ili kratko MC), se primenjuje ukoliko otkaţe SC. U tom sluĉaju, prvo se primenom majoritetnog odluĉivanja na nivou bita (ML) regeneriše kopija okvira FML koja se zatim proverava na bazi regenerisane CRC sekvence. Ukoliko nema detektovanih grešaka, prenos se proglašava uspešnim, predajnoj stanici se šalje ACK, a regenerisani paket se prosleĊuje korisniku. U suprotnom, okvir se odbacuje, prenos se proglašava neuspešnim, predajniku se šalje NAK ĉime se aktivira zahtev za retransmisiju. Procedura se dalje nastavlja prijemom nove generacije okvira, sledeći opisane korake. ML SC+MC kombajner F1 F2 Fm FML IR CRC potvrda prijema Tx FTIT ARQ pm p1 Rx Rx R1 R2 RmRx p2 Sl. 1.2. Pojednostavljeni model ARQ šeme sa majoritetnim kombinovanjem paketa. U našem modelu pretpostavljamo da se kanali mogu modelovati kao kvaziostacionarni, meĊusobno nezavisni, binarni simetriĉni kanali. Pojam kvazistacionarnosti podrazumeva da se verovatnoća greške pri prenosu bita ne menja tokom prenosa okvira, a pojam nezavisnosti podrazumeva da su greške u razliĉitim kanalima u opštem sluĉaju meĊusobno razliĉite. Na osnovu definicije binarnog simetriĉnog kanala sledi da su greške pri prenosu bita u posmatranom kanalu meĊusobno nezavisne sluĉajne veliĉine. Krajnji rezultat napred iznetih pretpostavki je da na izlazima kanala postoje sekvence bita koje sadrţe okvire sa sluĉajno rasporeĊenim greškama na pojedinim pozicijama. Teorijski, broj grešaka po okviru se kreće u opsegu od nula do iznosa koji je brojĉano jednak polovini duţine okvira što je ekvivalentno promeni verovatnoće greške po bitu u granicama od 0 do 0.5. 1.3. Motiv i organizacija teze Primena tehnika za korekciju grešaka na bazi hibridne ARQ procedure sa majoritetnim kombinovanjem paketa predstavlja jednostavno, ekonomiĉno i atraktivno rešenje. Ove tehnike su posebno interesantne u senzorskim mreţama u kojima se zahteva mala potrošnja. Teţište istraţivanja u ovoj tezi ima za cilj dobijanje odgovora na sledeća pitanja:  Kako razliĉite verovatnoće grešaka u pojedinim kanalima utiĉu na verovatnoću pogrešnog prenosa u sluĉaju primene diverziti tehnike sa majoritetnim kombinovanjem paketa? 8  Kako mogući scenariji odvijanja toka retransmisije u okviru primenjene hibridne ARQ procedure utiĉu na propusnost?  Šta je bitno sa stanovišta realizacije imajući u vidu raspoloţive komponente i dostupna hardverska i softverska rešenja koja se primenjuju u savremenim senzorskim mreţama? OdreĊivanje izraza za verovatnoću retransmisije u okviru prvog postavljenog pitanja predstavlja izazovni problem, posebno sloţen kada je broj nezavisnih putanja proizvoljan. To je bio osnovni razlog da su gotovo svi autori u objavljenim istraţivanjima usvajali nerealnu pretpostavku da su kanalne verovatnoće grešaka (bit error rate, BER) po nezavisnim putanjama brojĉano jednake. Ĉak i pri tim uslovima, većina autora se ograniĉava na razmatranje samo tri putanje. Izuzetak predstavljaju radovi Lam-a i koautora [21] – [23] u kojima se daju opšta rešenja za proizvoljni broj kanala. Za razliku od ovog pristupa, u drugom poglavlju teze, postavljen je cilj da se izvede opšta formula kako za proizvoljan broj nezavisnih putanja (kanala), tako i za proizvoljne vrednosti verovatnoća. Postojanje nezavisnih transmisionih putanja obezbeĊuje prijem više kopija istog okvira. U normalnim okolnostima, uprkos postojanju grešaka na pojedinim bitskim pozicijama, pretpostavimo da će prisustvo svih okvira biti ispravno detektovano. U tom sluĉaju, u prijemnom ĉvoru će postojati potpun komplet okvira, tako da će se, ukoliko je potrebno, primeniti majoritetno kombinovanje. MeĊutim, takoĊe je realna mogućnost da se ne prepozna prisustvo prenetog okvira. To će imati za posledicu “deficit” paketa, koji se mora nadoknaditi tokom narednih retransmisija. Mogući su veoma razliĉiti scenariji prikupljanja paketa za majoritetno odluĉivanje, od toga da se problem reši posle prve retransmisije, do sluĉaja kada broj retransmisija mora biti jednak ili veći od broja nezavisnih putanja. TakoĊe, posle pojedinih retransmisija, moţe doći do “suficita” paketa koji se mogu koristiti za majoritetno odluĉivanje, tako da se u takvim prilikama javlja problem izbora pogodnih “kandidata” za ovo odluĉivanje. U svakom sluĉaju, potreba za retransmisijom utiĉe na smanjenje efikasnosti primenjene metode, pa je od interesa da se ovaj problem detaljnije ispita. Ova problematika se razmatra u trećem poglavlju teze tako što se analizira propusnost za tri karakteristiĉna scenarija. Analiza se zasniva na modelovanju procesa retransmisije posredstvom odgovarajućih Markovljevih modela, koji dalje sluţe za odreĊivanje propusnosti na bazi srednje vrednosti trajanja retransmisionih ciklusa. Atraktivnost primene hibridne ARQ tehnike sa majoritetnim kombinovanjem zasniva se na većoj jednostavnosti realizacije u poreĊenju sa alternativnim metodama. To nikako ne znaĉi da je problem trivijalan ili krajnje jednostavan. Da bi se obezbedila uspešna realizacija, potrebna je opseţna analiza koja ukljuĉuje traţenje odgovora na naše treće pitanje koje se razmatra u ĉetvrtom poglavlju teze, a odnosi se na raspoloţive komponente i modifikaciju dostupnih rešenja koja se koriste u beţiĉnim senzorskim mreţama. Pri tome, polazni okvir je bio: (i) da se utvrdi pogodna topološka i komunikaciona postavka senzorske mreţe; (ii) da se razmotre i predloţe izmene i modifikacije funkcija postojećeg protokola koje se odnose na korekciju grešaka u okviru drugog sloja referentnog modela; (iii) da se sagledaju neophodne modifikacije primopredajnika dostupnih na komercijalnom trţištu; i (iv) da se bliţe odrede hardverska i softverska rešenja koja omogućuju implementaciju majoritetnog kombinovanja. Svakom od navedenih otvorenih pitanja pristupalo se kao zasebnim tematskim celinama, pri ĉemu su korišćeni posebni prikladni telekomunikacioni modeli i usvajane specifiĉne pretpostavke kako bi se kompletno razmatranje uĉinilo jasnim i celishodnim. Objedinjavanje celokupne problematike u svrsishodnu celinu dato je u zakljuĉnom petom poglavlju u kome je ujedno ukazano i na moguće pravce daljeg istraţivanja. 9 U organizacionom smislu, disertacija pored naslovne strane i sadrţaja, obuhvata pet poglavlja, pregled referentne literature i šest priloga. U uvodnom delu su identifikovane tri osnovne tehnike za kontrolu grešaka na liniji: automatska retransmisija paketa (ARQ), korekcija grešaka unapred (FEC) i diverziti (Diversity). Imajući u vidu dobro poznate prednosti i nedostatke ARQ i FEC postupaka u pogledu jednostavnosti realizacije, efikasnosti i pouzdanosti, u tezi se predlaţe i analizira kombinacija diverziti tehnike i majoritetnog kombinovanja koja predstavlja jednostavan, ali ujedno i moćan alat za kontrolu grešaka. Osnovna ideja se zasniva na korišćenju višestrukog prenosa istog okvira i eventualnom kombinovanju pogrešnih kopija kako bi se na prijemu regenerisao ispravni okvir. Ovo rešenje se realizuje na drugom sloju referentnog modela kao deo hibridnog postupka (HARQ). Drugo poglavlje teze se bavi izvoĊenjem izraza za verovatnoću retransmisije ili verovatnoću pogrešnog prenosa paketa kao jednog od kljuĉnih parametara za analizu propusnosti predloţenih hibridnih šema. OdreĊivanje ovog izraza postaje priliĉno sloţeno u sluĉaju proizvoljnog broja kanala sa razliĉitim verovatnoćama grešaka. To je bio osnovni razlog da su gotovo svi autori usvajali nerealnu pretpostavku, da se prenos vrši preko tri nezavisne putanje i da su kanalne verovatnoće meĊusobno jednake. Za razliku od ovakvog pristupa, u tezi će biti izvedeni egzaktni i aproksimativni izrazi za verovatnoću retransmisije za razliĉite kanalske verovatnoće, najpre za tri putanje, pa za pet putanja, i na kraju, za proizvoljan neparan broj putanja. Koristeći dobijene izraze, biće analiziran uticaj razliĉitih klasa rasejavanja kanalskih verovatnoća, broja kanala i duţine okvira. U trećem poglavlju se vrši analiza propusnosti tri moguća scenarija multikopijskog prenosa na bazi srednjeg vremena trajanja retransmisionih ciklusa koji su modelovani pomoću Markovljevih lanaca. Identifikovana su dva graniĉna sluĉaja, jedan, koji se zasniva na “prostornom” diverzitiju i jednovremenom prijemu kopija istog okvira, i drugi, koji se zasniva na “vremenskom” diverzitiju, sa sekvencijalnim prijemom kopija. Za razliku od prva dva scenarija gde se majoritetno odluĉivanje vrši nad nezavisnim setom pogrešno primljenih kopija istog okvira, majoritetno odluĉivanje kod trećeg scenarija se odvija nad tekućom kopijom i kopijama iz prethodnog seta. Za svaki od predloţenih scenarija su izvedeni egzaktni teorijski izrazi za propusnost. Pored teorijske analize, vršeni su i simulacioni eksperimenti kako bi se potvrdila ispravnost dobijenih teorijskih rezultata. Na kraju je data komparativna analiza predloţenih scenarija u zavisnosti od kljuĉnih parametara kao što su broj kanala, duţina okvira i kruţno kašnjenje. U ĉetvrtom poglavlju se analizirana mogućnost primene predloţenog hibridnog rešenja u jednoj hipotetiĉkoj senzorskoj mreţi. Obzirom da se rešenja sa majoritetnim kombinovanjem paketa ne mogu direktno primeniti prema postojećim standardima, dat je predlog modifikacije standarda koji reguliše razmenu podataka u beţiĉnim senzorskim mreţama i komercijalnih primopredajnika koji se koriste u odredišnom ĉvoru. Na kraju, je razmotren predlog hardverske i softverske realizacije primopredajnika i procesorskog bloka u odredišnom ĉvoru. U petom poglavlju je dat zakljuĉak sa kratkim osvrtom na ono šta je uraĊeno u tezi, koji su doprinosi i pravci daljeg razvoja. Na kraju teze, je navedena literatura i prilozi sa listinzima programa za raĉunanje izraza za verovatnoću retransmisije u sluĉaju proizvoljnog broja kanala sa razliĉitim kanalskim verovatnoćama, izvoĊenje izraza za prelazne verovatnoće, kao i spisak skraćenica, simbola, slika i tabela koje se pominju u tezi. 10 2. VEROVATNOĆA RETRANSMISIJE Jedan od kljuĉnih parametara za analizu performansi ARQ algoritama je verovatnoća retransmisije. U našem sluĉaju, to je verovatnoća pogrešnog multikopijskog prenosa paketa posle primene selektivnog i majoritetnog kombinovanja (odluĉivanja). Problem odreĊivanja verovatnoće retransmisije nije nov i poslednjih dvadeset godina je razmatran od strane više autora, u razliĉitim postavkama diverziti i ARQ modela prenosa [6] – [26]. Tako su, Liang and Chakraborty razmatrali diverziti sistem sa dve grane i xor kombinovanjem paketa [11]. Evaluaciju izraza su vršili pod pretpostavkom da su svi kanali identiĉni. Sliĉan rad istih autora, samo za tri identiĉna kanala i majoritetno kombinovanje je prezentovan u [12]. U ovom radu je dat izraz za verovatnoću pogrešnog prenosa paketa u otvorenom obliku, u vidu trostruke sume. Za razliku od prethodnih autora, Z. Zhou, Z. Peng i J. –H. Cui raĉunajući energetsku efikasnost jedne podvodne senzorske mreţe sa višestrukim putanjama, daju analitiĉki izraz za verovatnoću pogrešnog prenosa paketa uzimajući u obzir proizvoljan broj putanja i razliĉite verovatnoće grešaka u kanalu [26]. Mehanizam za korekciju grešaka je zasnovan na majoritetnom kombinovanju paketa. Sam izraz je više empirijski. Vredan rezultat u pogledu raĉunanja verovatnoće pogrešnog prenosa paketa u sluĉaju diverziti prenosa sa proizvoljnim brojem kanala je dao Carson Lam [21] – [23]. Lam razmatra ukupno šest tipiĉnih šema koje se koriste kao deo ARQ protokola i za svaku šemu raĉuna verovatnoću pogrešnog prenosa i propusnost pod pretpostavkom da su svi kanali identiĉni. Za razliku od pristupa poznatih iz dostupne literature, primarni zadatak u ovom poglavlju je izvoĊenje egzaktnih i aproksimativnih analitiĉkih izraza za verovatnoću retransmisije u sluĉaju proizvoljnog broja kanala sa razliĉitim verovatnoćama grešaka. Izloţena materija je podeljena u pet potpoglavlja. U prvom je opisan teorijski model razmatranog sistema i ukazano je na bitne pretpostavke. U sledeća dva potpoglavlja se analiziraju pojedinaĉni sluĉajevi sa tri i pet kanala, pri ĉemu se detaljno analizira sluĉaj sa tri kanala. U ĉetvrtom potpoglavlju se izlaţe izvoĊenje izraza za proizvoljan broj kanala. U petom potpoglavlju se diskutuju teorijski aspekti doprinosa SC+MC procedure u odnosu na SC proceduru. Na kraju, u prilogu A se daju listinzi programa za raĉunanje verovatnoće retransmisije. 2.1. Teorijski model SC+MC procedure Analiza će biti zasnovana na teorijskom modelu prikazanom na slici 2.1. U ovom modelu istaknute su funkcije polaznog modela opisanog u prvom poglavlju (videti sliku 1.2) koje se odnose na postupke: (i) kodovanja, (ii) prenosa i (iii) dekodovanja, zasnovanog na sukcesivnoj primeni selektivnog i majoritetnog odluĉivanja (SC+MC). Predajni deo prikazanog modela je predstavljen kao koder sistematskog cikliĉnog koda [5] koji informacionu reĉ (paket IT) transformiše u kodnu reĉ (okvir FT). Ovaj okvir se zatim prenosi posredstvom m paralelnih kanala, tako da do prijemnog dela stiţe m njegovih kopija iRF ),,1( mi  . Budući da kanali ne obezbeĊuju idealni prenos, ove kopije se mogu razlikovati od “originala” FT. Prema tome, osnovni zadatak prijemnog dela je da izvrši 11 korekciju nastalih grešaka ili da aktivira mehanizam retransmisije okvira ukoliko je korekcija grešaka bila neuspešna. Kao što je ranije spomenuto, korekcija pogrešnog prenosa okvira TF se odvija posredstvom sukcesivnog delovanja dve procedure, SC i MC. Procedura SC se zasniva na pojedinaĉnoj proveri cikliĉne redudanse (CRC) sa ciljem detektovanja kopije koja ne sadrţi greške. Ako sve prenete kopije sadrţe detektovane greške, sledi aktiviranje MC procedure. U ovoj proceduri se primenom majoritetnog odluĉivanja formira “pomoćna” kopija nad kojom se takoĊe vrši provera cikliĉne redudanse. Ako i ova kopija sadrţi detektovane greške, aktivira se mehanizam retransmisije. Ukoliko se kod prenetih kopija ili kod pomoćne kopije okvira ne pronaĊe greška, postupak korekcije grešaka se smatra uspešnim, izdvaja se informaciona reĉ (tj. paket IR) i prosleĊuje korisniku. SC+MC kombajner IRFTIT Cikliĉni koder Predajni deo Prijemni deo E1 Kanal 1 E2 Kanal 2 Em Kanal m 1 FR 2 FR m FR CRC Slika 2.1. Teorijski model za detekciju i korekciju grašaka posredstvom SC+MC procedure Postupak odreĊivanja verovatnoće retransmisije zasnivaćemo na sledećim formalnim postavkama. Smatraćemo da je okvir na izlazu predajnika predstavljen kodnim vektorom duţine L bita: ],...,,...,,[ 21 Ll aaaaTF , (2.1.1) a da su greške nastale u i-tom kanalu predstavljene pomoću vektora greške: ],...,,...,,[ 21 i L i l ii eeeeiE . (2.1.2) Binarni element ile ),,1( Ll  oznaĉava prisustvo greške ukoliko ima vrednost 1, a odsustvo greške, ukoliko je njegova vrednost 0. Saglasno tome, okvir na izlazu i-tog kanala se moţe predstaviti kao kodni vektor: ],...,,...,,[ 21 i L i l ii bbbb iT i R EFF . (2.1.3) Binarni operator  oznaĉava sabiranje po modulu 2. Imajući u vidu da elementi kodnog vektora FT dobijaju vrednosti iz skupa {0, 1}, vredi: illl i ll i l eaaeab  )21( , Llmi ,...,1;,...,1  (2.1.4) 12 Saglasno izloţenom, rad SC+MC kombajnera se zasniva na proveri cikliĉne redudanse redova kodne matrice:                                             Ll m L m l mm Ll Ll cccc bbbb bbbb bbbb ,,,,, ,...,,...,, ,...,,...,, ,...,,...,, 21 21 222 2 2 1 111 2 1 1   C F F F M m R 2 R 1 R R , (2.1.5) pri ĉemu provera prvih m redova pripada SC proceduri, a provera 1m –vog reda, MC proceduri. Sa C je oznaĉen kodni vektor koji predstavlja “pomoćnu” kopiju okvira dobijenu majoritetnim odluĉivanjem. U skladu sa tim, elementi kodnog vektora C se mogu predstaviti na sledeći naĉin:                  m i i l m i i l l mb mb c 1 1 2/jeako,1 2/jeako,0 . (2.1.6) Polazeći od jednaĉina (2.1.4) i (2.1.6), vredi:                  m i i ll m i i ll l mea mea c 1 1 2/jeako,1 2/jeako, . (2.1.7) Imajući u vidu prethodne izraze, zakljuĉujemo da se funkcionisanje SC+MC kombajnera moţe formalno pratiti posredstvom matrice:                       Ll m L m l mm Ll Ll dddd eeee eeee eeee ,,,,, ,,,,, ,,,,, ,,,,, 21 21 222 2 2 1 111 2 1 1      EM , (2.1.8) pri ĉemu su elememti dl odreĊeni izrazom:                  m i i l m i i l l me me d 1 1 2/jeako,1 2/jeako,0 . (2.1.9) 13 Do istog zakljuĉka moţe se doći i bez izvoĊenja, kada se ima u vidu da funkcionisanje SC+MC kombajnera ne zavisi od sadrţaja kodnog vektora FT, već iskljuĉivo od sadrţaja meĊusobnog rasporeda elemenata pojedinaĉnih vektora kanalnih grešaka. Primera radi, naglasimo da se matrica ME dobija direktno iz matrice MR stavljajući da su svi elementi kodnog vektora FT jednaki nuli. Naravno, budući da kanalne greške na mestu prijema nisu poznate, matrica ME nema praktiĉni znaĉaj. MeĊutim, kada je u pitanju odreĊivanje verovatnoće retransmisije, matrica ME omogućuje jasno povezivanje ove veliĉine i verovatnoća pojavljivanja kanalnih grešaka. U daljem razmatranju, matrica ME posluţiće za jednostavno, ali aproksimativno, utvrĊivanje rezultata CRC provere. Naime smatraćemo da ova provera nije ispunjena ako najmanje jedan element vektora greške ima vrednost 1. Oĉigledno, ovakva odluka biće pogrešna u sluĉaju kada vektor greške pripada skupu kodnih vektora. MeĊutim, kada su Hemingove distance izmeĊu kodnih vektora dovoljno velike, što je uslov dobrog izbora generišućeg polinoma [1], uticaj ove greške na dobijeni rezultat se moţe smatrati zanemarljivim. Druga bitna pretpostavka odnosi se na definisanje kanala. Naime, pretpostavićemo da se kanali mogu modelovati kao kvaziostacionarni, meĊusobno nezavisni, binarni simetriĉni kanali. Pojam kvazistacionarnosti podrazumeva da se verovatnoća greške po bitu ne menja tokom prenosa okvira, a pojam meĊusobne nezavisnosti podrazumeva da ove verovatnoće u razliĉitim kanalima u opštem sluĉaju imaju razliĉite vrednosti. Na osnovu definicije binarnog simetriĉnog kanala sledi da su greške pri prenosu bita u posmatranom kanalu meĊusobno nezavisne sluĉajne veliĉine. Na kraju navedimo bitnu pretpostavku usvojenu pri definisanju modela na slici 2.1. To je pretpostavka da kanalne greške ne utiĉu na funkciju prepoznavanja poĉetka i trajanja okvira, kao i elemenata koji ga identifikuju (tip okvira, sekvencijalni broj, adresa izvora, adresa odredišta). 2.2. SC+MC procedura za tri kanala U ovom potpoglavlju razmatramo šemu u kojoj se korekcija greške ostvaruje posredstvom tri-kopijske SC+MC procedure. Naš osnovni cilj je da odredimo egzaktni izraz za verovatnoću retransmisije, pogodne aproksimativne analitiĉke izraze, kao i uticaj rasejavanja kanalnih verovatnoća. 2.2.1. Egzaktni izraz za verovatnoću retransmisije Imajući u vidu pretpostavku da je uprkos postojanju grešaka pri prenosu kopija, na prijemnoj strani obezbeĊeno njihovo idealno prepoznavanje i memorisanje, naš prvi zakljuĉak je da se obe procedure (i SC i MC) mogu primeniti nezavisno jedna od druge. Kao što je već naglašeno, u predloţenoj šemi, prvo se primenjuje SC procedura, pa ukoliko ona ne obezbedi uspešan rezultat, aktivira se MC procedura. Budući da se u pogledu korekcije grešaka, ove procedure meĊusobno i preklapaju i dopunjuju, suština problema izvoĊenja izraza za verovatnoću retransmisije je odreĊivanje “doprinosa” MC procedure posle neuspešne primene SC procedure. U našim naporima da taj doprinos jasno i jednostavno formulišemo nismo imali uspeha. Sa druge strane, intuitivno je jasno da se krajnji ishod u pogledu korekcije grešaka ne menja ukoliko bi se izmenio redosled aktiviranja procedura, tj. ukoliko bi se prvo primenila MC procedura, pa zatim, ako izostane uspešna korekcija, SC procedura. Imajući u vidu naš cilj, suština problema se sada svodi na odreĊivanje doprinosa SC procedure posle neuspešne primene MC procedure. Pokazalo se da je u ovom sluĉaju moguće dobiti relativno jednostavne izraze za odreĊivanje traţenog doprinosa. Polazeći od prethodne kljuĉne konstatacije, u nastavku je izloţen postupak izvoĊenja egzaktnog izraza za verovatnoću retransmisije kod tri-kopijske SC+MC procedure [27] – [29]. 14 Opšti izraz za PSC+MC: Na osnovu obrazloţenja u uvodnom delu, izraz za verovatnoću retransmisije, PSC+MC, se moţe predstaviti u sledećem opštem obliku: )(1 / MCSCMCMCSC QQP  , (2.2.1) pri ĉemu je QMC verovatnoća uspeha u sluĉaju da je prvo aktivirana MC procedura, a QSC/MC, pridruţena verovatnoća uspeha pošto je SC aktivirana posle neuspeha MC. Verovatnoća QMC: Uslov da MC procedura bude uspešna jeste da se po prijemu tri kopije istog okvira dobije matrica ME u kojoj ni u jednoj koloni (tj. bitskoj poziciji) ne postoji dvostruka ili trostruka greška. Kako su verovatnoće grešaka u pojedinim kanalima meĊusobno nezavisne, to je verovatnoća trostruke greške na istoj bitskoj poziciji jednaka 321 ppp . Verovatnoća ispravnog prenosa bita u k-tom kanalu )3,2,1( k uz istovremeni pogrešan prenos u preostala dva kanala, jednaka je kk ppppq 321 . Prema tome, odgovarajuća verovatnoća QMC se moţe izraziti kao: L kk kMC p ppp qpppQ            321 3 1 3211 . (2.2.2) Verovatnoća QSC/MC: Sada ćemo razmotriti matrice u kojima se aktiviranjem SC procedure koriguju pogrešno preneti biti, uprkos ĉinjenici da prethodna primena MC procedure nije bila uspešna. Uslovi da se takvi dogaĊaji dese su: (i) da prenos kopije u k-tom kanalu )3,2,1( k bude ispravan, i (ii) da u preostale dve kopije postoje dve greške na najmanje jednoj od L bitskih pozicija. Verovatnoća da bude ispunjen uslov (i) iznosi Lkq , a verovatnoća ispunjenja uslova (ii) je L kpppp )1(1 321 . Uzimajući u obzir sva tri kanala, verovatnoću QSC/MC moţemo predstaviti izrazom:                    3 1 321 / 11 k L k L kMCSC p ppp qQ . (2.2.3) Verovatnoća PSC+MC: Direktnom smenom (2.2.2) i (2.2.3) u (2.2.1) dobijamo traţeni izraz za verovatnoću retransmisije PSC+MC:                              3 1 321321 3 1 321 1111 k L k L k L kk kMCSC p ppp q p ppp qpppP . (2.2.4) Ukoliko izvršimo smenu kk pq 1 )3,2,1( k , dobijamo sledeću alternativnu formulu:      LL LL LL L MCSC ppp ppp ppp pppppppppP )1(1)1( )1(1)1( )1(1)1( )21(1 213 132 321 321133221     . (2.2.4a) Kao što smo i oĉekivali, verovatnoća retransmisije PSC+MC ne zavisi od redosleda oznaĉavanja kanala. Naime, zamenom indeksa koji oznaĉava redni broj kanala, ĉitav izraz se neće promeniti. 15 Specijalni sluĉaj: U sluĉaju kada je ispunjen uslov pppp  321 , formula (2.2.4) dobija oblik: ])1(1[3)31(1 223 LLLS MCSC pqqppP  , (2.2.5) Imajući u vidu poznate jednakosti: 3122133 33)(1 pqpqpqqp  i 2)(1 qp  2112 2 pqpq  , izraz (2.2.5) postaje: ])2(1[3 ])3(1[ 2 23 LL LS MCSC pqqq pqqP   . (2.2.5a) Prethodni izraz takoĊe moţemo napisati u obliku:                                        * 0 * 0 1)1( m i L jim m j jiLiS MCSC qp j im q i m P , (2.2.5b) pri ĉemu je 3m i   12/ *  mm . Ilustrativni primer: Koristeći izraz (2.2.4), na konkretnom primeru moţemo ilustrovati doprinos SC+MC procedure u odnosu na SC proceduru. Kao prvo, pretpostavljajući da posmatramo prenos binarno fazno modulisanog signala (BPSK) po meĊusobno nezavisnim kanalima sa Rayleigh-ovim fedingom, simuliraćemo mogući vremenski tok promene verovatnoća grešaka po bitu, kp )3,2,1( k u kanalima. Usvajajući da se ove verovatnoće praktiĉno ne menjaju za vreme prenosa jednog okvira, moţemo dalje da izraĉunamo verovatnoće grašaka po okviru Pf1, Pf2 i Pf3 u pojedinim diverziti granama koristeći formulu ])1(1[ Lkkf pP  , )3,2,1( k . Jedan mogući primer za sluĉaj duţine okvira 128L predstavljaju tri meĊusobno isprepletena grafika na gornjem delu slike 2.2. Preostala dva grafika na ovoj slici predstavljaju verovatnoću retransmisije za sluĉaj da je primenjena samo SC procedura (grafik u sredini) i za sluĉaj SC+MC procedure (grafik u donjem delu slike). Prvi od prethodna dva grafika odreĊen je posredstvom formule 321 fffSC PPPP  , a drugi, za MCSCP  , na osnovu izraza (2.2.4). Normalizacija vremena je izvršena u odnosu na duţinu trajanja okvira, Tf. 16 b) PSC c) PSC+MC a) Pf1, Pf2, Pf3 Normalizovano vreme, t/Tf V er o v a tn o ća , P fk , P S C , P S C + M C Slika 2.2. Ilustrativni primer: (a) verovatnoće pogrešnog prenosa okvira u tri individualna kanala; (b) verovatnoća retransmisije posle SC procedure, i (c) verovatnoća retransmisije posle SC+MC procedure. Kao što se sa slike 2.2 vidi, vremenske sekvence za SC i SC+MC procedure imaju pribliţno iste oblike, pri ĉemu je verovatnoća PSC+MC u proseku 40 puta manja od verovatnoće retransmisije PSC. Kako se sliĉnost talasnih oblika i njihov odnos ne moţe jednostavno naslutiti iz izraza za verovatnoće retransmisija, u narednom odeljku ćemo pokušati da odredimo njihove aproksimativne izraze tako da odnosi izmeĊu ovih verovatnoća budu oĉigledni. 2.2.2. Aproksimativni izrazi za verovatnoću retransmisije Mada je formula (2.2.4) relativno jednostavna za numeriĉko izraĉunavanje, ona ne pruţa jasan uvid u doprinos kljuĉnih parametara kao što su duţina okvira L i verovatnoće grešaka u pojedinim kanalima kp )3,2,1( k . Iz tog razloga ćemo razmotriti pogodne aproksimativne izraze za verovatnoću retransmisije. Pri tome, vodiće se raĉuna o sledećim kriterijumima kao što su: domen primene, jednostavnost i preglednost dobijene aproksimacije i realna ograniĉenja. Kriterijum malog proseĉnog broja grešaka po paketu: Polazni argumenti za dobijanje aproksimativnih izraza su sledeći. Prvo, da bi se obezbedio visok stepen iskorišćenosti kanala, duţina informacionog dela okvira L treba da bude znatno veća od duţine zaglavlja (u praksi je to 30L ). Drugo, da bi se osigurala pouzdana CRC detekcija grešaka, opravdano je da se uvede ograniĉenje da proseĉan broj grešaka po paketu kpL  )3,2,1( k ne bude veći od jedan. Naime, tada moţemo da pišemo: )(1)21( 133221321133221 ppppppLppppppppp L  )3,2,1(, 2 )( 1)1( 2    k pL pLp kk L k . (2.2.6) )3,2,1,(,1)1(  jkppLpp jk L jk 17 Posle zamene u (2.2.4), nalazimo: )]( 6 1 1[ 3 321321 LpLpLpLpLpLp L P A MCSC  . (2.2.7) Na osnovu ovog rezultata zakljuĉujemo, da je u sluĉaju dugaĉkih paketa )1( L i malog proseĉnog broja grešaka po paketu )1(  kpL , verovatnoća retransmisije PSC+MC:  inverzno proporcionalna duţini paketa L, ukoliko je proseĉan broj grešaka po paketu fiksan;  direktno proporcionalna proizvodu proseĉnog broja grešaka u sve tri kopije prenetog okvira. Na osnovu izraza (2.2.7), takoĊe moţemo da zakljuĉimo da PSC+MC dostiţe maksimalnu vrednost kada je 321 ppp  , a pod uslovom da se proizvod 321 ppp odrţava konstantnim (pravilo kvadra minimalnog obima pri datoj zapremini). Pod istim uslovima, u sluĉaju SC procedure, verovatnoća retransmisije se moţe predstaviti sledećim aproksimativnim izrazom:        )( 2 1 1 321321 LpLpLpLpLpLpP A SC . (2.2.8) Odavde vidimo da je u sluĉaju dugaĉkih paketa i pri malom proseĉnom broju grešaka po paketu, verovatnoća SCP direktno proporcionalna proseĉnom broju grešaka po paketu kpL  . Izrazi (2.2.7) i (2.2.8) potvrĊuju da vremenski tokovi verovatnoća PSC i PSC+MC imaju pribliţno isti oblik, kao što je to naznaĉeno na slici 2.2. Budući da vredi 3// LPP MCSCSC  , takoĊe potvrĊujemo da pri 128L , odnos verovatnoća retransmisije za SC i SC+MC iznosi pribliţno 40. Gornja granica: Neposredno iz postavke SC procedure, a time ujedno i iz postavke SC+MC procedure, sledi da će verovatnoća retransmisije biti jednaka nuli ukoliko je prenos u bilo kom od tri kanala idealan, tj. bez pogrešno prenetih bita. Potvrda ovog zakljuĉka takoĊe sledi iz aproksimativne formule (2.2.7). Naime, ukoliko je bar jedna kanalna verovatnoća kp jednaka nuli, direktno sledi 0MCSCP . Na osnovu predhodnog, zakljuĉujemo da se izraz za PSC+MC takoĊe moţe napisati u opštem obliku: )],,(1[ 321321 pppFpppKP MCSC  . (2.2.9) Ovde je K konstanta, a ),,( 321 pppF predstavlja polinom stepena 1L po promenjivoj kp )3,2,1( k . Imajući u vidu aproksimaciju (2.2.7), neposredno sledi da je 23 LK  , a da polinom ),,( 321 pppF ima pozitivnu vrednost koja teţi nuli kada bar jedna kanalna verovatnoća teţi nuli. Pod tim uslovima verovatnoću 321 23 pppLPU MCSC  , (2.2.10) moţemo smatrati “gornjom granicom” verovatnoće retransmisije. Ovakva kvalifikacija je potvrĊena velikim brojem numeriĉkih provera u kompletnom opsegu dozvoljenih vrednosti kanalnih verovatnoća, tj. za sve vrednosti za koje je 5.0kp . 18 Ekvivalentna kanalna verovatnoća: Prethodni rezultati, posebno ĉinjenica da verovatnoća U MCSCP  predstavlja “tesnu” gornju granicu pri malim vrednostima kanalnih verovatnoća, ukazuju na hipotezu da se dobra aproksimacija moţe oĉekivati ako se u izrazu (2.2.5), kanalne verovatnoće kp )3,2,1( k zamene njihovom geometrijskom srednjom vrednošću: 3 321 ppppE  . (2.2.11) U daljem izlaganju, ovu verovatnoću ćemo nazivati ekvivalentnom kanalnom verovatnoćom. Za ovako definisanu aproksimaciju koristićemo oznaku E MCSCP  . Saglasno izrazu (2.2.5b), sledi:                                        * 0 * 0 )1(1)1()1( m i L jim E m j j E iL E iE MCSC pp j im p i m P , (2.2.12) pri ĉemu je u konkretnom sluĉaju 3m i 1* m . U narednim odeljcima pokazaćemo da formula (2.2.5b) vredi za proizvoljnu, neparnu vrednost m, a saglasno tome razmatraće se i generalizacija aproksimacije (2.2.12). Uporedna analiza predloženih aproksimacija: Sa ciljem jasnijeg sagledavanja “dometa” uvedenih aproksimacija na slici 2.3 su prikazani grafici taĉnog MCSCP  (2.2.4) i aproksimativnih izraza A MCSCP  (2.2.7), U MCSCP  (2.2.10) i E MCSCP  (2.2.12) za verovatnoću retransmisije u funkciji ekvivalentne kanalne verovatnoće Ep . Pretpostavljeno je da su pojedinaĉne kanalne verovatnoće odreĊene jednaĉinama: EEE pxppxppxp  332211 ,, , (2.2.13) pri ĉemu 1x , 2x i 3x predstavljaju koeficijente “rasejavanja”. To su pozitivni racionalni brojevi koji ujedno ispunjavaju uslov 1321  xxx . U prikazanom primeru usvojeno je 10/11 x , 12 x i 103 x . PSC+MC U PSC+MC A PSC+MC E PSC+MC L = 50 L = 2000 Ekvivalentna kanalna verovatnoća, pE V er o v a tn o ća r et ra n sm is ij e, P S C + M C Slika 2.3. Komparacija taĉne i aproksimativnih formula za verovatnoću retransmisije ( 50L i 2000L , 3m ; 10/11 x , 12 x i 103 x ). 19 Na osnovu prikazanih grafika zakljuĉujemo da sve razmatrane aproksimacije daju veoma dobre rezultate pri uslovu 1.0 EpL , i to nezavisno od duţine paketa L koja se menja u granicama od nekoliko desetina bita do nekoliko hiljada bita. PotvrĊuje se da U MCSCP  predstavlja solidnu gornju granicu verovatnoće retransmisije, a E MCSCP  odliĉnu aproksimaciju pri uslovu 10 EpL , gde je L duţina paketa, a Ep ekvivalentna kanalna verovatnoća. 2.2.3. Uticaj rasejavanja kanalnih verovatnoća Prethodno razmatranje upućuje na sledeće pitanje: u kojoj meri “rasejavanje” kanalnih verovatnoća utiĉe na verovatnoću retransmisije, ukoliko se pretpostavi fiksna vrednost ekvivalentne kanalne verovatnoće. Budući da postoji neograniĉeni broj razliĉitih raspodela koeficijenata rasejavanja, moguće je dati samo okvirni odgovor na ovo pitanje. Do tog odgovora se moţe doći numeriĉkim putem tako što će se pretpostaviti karakteristiĉne klase raspodela. Primera radi, na slici 2.4 prikazano je sledećih pet klasa za sluĉaj kada se vrednost parametra D menja u granicama od 1 do 100:  SC1: 11  Dx , 2/12 Dx  , 2/1 3 Dx  ;  SC2: 11  Dx , 4/12 Dx  , 4/3 3 Dx  ;  SC3: 11  Dx , 12 x , Dx 3 ;  SC4: 4/31  Dx , 4/12  Dx , Dx 3 ;  SC5: 2/11  Dx , 2/12  Dx , Dx 3 ; Konkretne vrednosti koeficijenata rasejavanja pripadaju zrakastom snopu linija prikazanim i oznaĉenim na desnoj ivici okvira slike. Klase rasejavanja birane su tako da u prva tri sluĉaja, jedan kanal ima D puta manju vrednost, a u poslednja tri, D puta veću vrednost kanalne verovatnoće u odnosu na ekvivalentnu verovatnoću. 3, 4, 5 2 2 1, 1 3 4, 4 1, 2, 3 5 5 Parametar D K o ef ic ij en ti r a se ja v a n ja , x k (k = 1 , 2 , 3 ) Slika 2.4. Klase raspodela koeficijenata rasejavanja (Brojevi uz desnu stranicu okvira ukazuju na skup zrakastih linija ĉije taĉke pripadaju odgovarajućoj klasi). 20 Za svaku datu vrednost parametra D i za svaku posmatranu klasu rasejavanja analizirano je relativno odstupanje definisano izrazom: 1 11001 )(      DMCSC DMCSCDMCSC MCSC P PP DP . (2.2.13) Rezultati su prikazani na slici 2.5 i odnose se na sledeće fiksne vrednosti ekvivalentnih kanalnih verovatnoća: 5x10-5, 5x10-4 i 5x10-3. R el a ti v n a p ro m en a v er o v a tn o će P S C + M C Parametar D (a) Parametar D R el a ti v n a p ro m en a v er o v a tn o će P S C + M C (b) 21 Parametar D R el a ti v n a p ro m en a v er o v a tn o će P S C + M C (c) Slika 2.5. Relativna promena verovatnoće retransmisije PSC+MC u sluĉaju odabranih klasa koeficijenata rasejavanja (a) pE = 5x10 -5 , (b) pE = 5x10 -4 i (c) pE = 5x10 -3 (m = 3, L = 500) Prikazani rezultati pokazuju da se u opštem sluĉaju relativno odstupanje na kompleksan naĉin menja sa povećanjem parametra D. Pri tome, sa smanjivanjem referentnih vrednosti kanalne verovatnoće, maksimalni iznos odstupanja opada, a samo odstupanje postaje negativno. Ovo je u skladu sa pravilom kvadra koji je spomenut kada je komentarisan aproksimativni izraz (2.2.7). Na osnovu prikazanih rezultata, kao i na osnovu šire sprovedene analize, pokazuje se da se verovatnoća retransmisije, PSC+MC, relativno malo menja (manje od 100%) ĉak i u sluĉajevima kada odnos vrednosti pojedinih kanalnih verovatnoća premašuje iznos 1:1000. Pri tome, promene su utoliko manje ukoliko je ekvivalentna kanalna verovatnoća manja. Iz ovoga sledi bitan zakljuĉak, da ekvivalentnu kanalnu verovatnoću moţemo koristiti kao pogodnu veliĉinu pri analizi SC+MC procedure. 2.3. SC+MC procedura za pet kanala Metodologiju iz prethodnog potpoglavlja proširićemo na sluĉaj SC+MC procedure za 5m kopija. 2.3.1. Egzaktni izraz za verovatnoću retransmisije Opšti izraz za PSC+MC: Budući da se vrednost verovatnoće pogrešnog prenosa neće promeniti ukoliko SC i MC procedure zamene redosled aktiviranja, polazni izraz za verovatnoću retransmisije moţemo napisati u sledećem obliku: )(1 / MCSCMCMCSC QQP  . (2.3.1) 22 Ovde QMC oznaĉava verovatnoću uspeha MC procedure, a QSC/MC je doprinos uspešne korekcije greške kao posledica aktiviranja SC procedure posle otkaza MC procedure. U sluĉaju pet–kopijskog prenosa, verovatnoća QSC/MC se moţe predstaviti kao zbir dva sabirka: MC2MC1MCSC QQQ ///  . (2.3.2) Prvi ĉlan, Q1/MC, oznaĉava doprinos SC procedure u uslovima uspešnog prenosa samo jedne kopije, dok je drugi ĉlan, Q2/MC, posledica uspešnog prenosa dve kopije, posle otkaza MC procedure. Verovatnoća QMC: Da bi procedura MC bila uspešna, potrebno je da se po prijemu kopija dobije matrica ME u kojoj na svakoj od L kolona (tj. bitskih pozicija) ima najmanje tri ispravno preneta bita. Verovatnoća ovog kompleksnog dogaĊaja se moţe napisati kao: L i i ij ji ji i iMC qq qqqqq pp q qqqqq pqqqqqQ               5 1 4 1 5 1 5432154321 54321 , (2.3.3) ili, L i i ij ji ji i i MC qq pp q p QQ                       5 1 4 1 5 1 1 , (2.3.3a) pri ĉemu je uvedena smena 54321 qqqqqQ  . Drugim reĉima, MC procedura će uspešno korigovati greške nastale u prenosu, ukoliko ni na jednoj od L kolona nema više od dva pogrešno preneta bita. Saglasno tome moţemo da pišemo: L i i jiij ji i iMC pp ppppp qq p ppppp qpppppQ             5432154321 543211 . (2.3.4) Oĉigledno, drugi, treći i ĉetvrti ĉlan u zagradi predstavljaju verovatnoće da u istoj koloni bude redom pet, ĉetiri ili tri greške. Formula (2.3.4) moţe se napisati i u sledećem ekvivalentnom obliku: L i ij ji ji i i i MC pp qq p q PQ                    11 . (2.3.4a) pri ĉemu je uvedena smena 54321 pppppP  . Napomenimo da su u prethodna dva izraza demonstrirana dva ekvivalentna naĉina predstavljanja istih domena sumiranja. U nastavku izlaganja koristićemo naĉin koji je prezentovan u formuli (2.3.4a). 23 Verovatnoća Q1/MC: U ovom sluĉaju reĉ je o dogaĊaju koji se odnosi na uspešan prenos samo jedne kopije posle otkaza MC procedure. Po prijemu kopija dobija se matrica ME koju karakteriše sledeće: (i) jedna kopija je bez grešaka, a (ii) ostale kopije sadrţe greške, pri ĉemu bar na jednoj od L kolona postoje najmanje tri ili najviše ĉetiri greške koje obezbeĊuju neuspeh MC procedure. Saglasno tome, verovatnoća ovog kompleksnog dogaĊaja se moţe predstaviti izrazom:                                                 ij L ji L j L ij ji j ii L iMC pp P q pp P q p P qQ 1111/1 . (2.3.5) Prvi ĉinilac u sumi, Liq , predstavlja verovatnoću dogaĊaja pod (i), a ĉinilac u vitiĉastoj zagradi verovatnoću dogaĊaja pod (ii). Kao što vidimo, drugi ĉinilac se sastoji od dva sabirka. Prvi sabirak oznaĉava verovatnoću dogaĊaja kod koga se ne iskljuĉuje pojavljivanje još jedne (dodatne) kopije bez grešaka, pa je bilo neophodno da se to kompezuje drugim sabirkom. Izraz (2.3.5) moţe da se napiše i u obliku:                                       i ij L ji L j L i L ij ji j ii L iMC pp P qq pp P q p P qQ 1111/1 , (2.3.5a) iz koga se jasnije vidi iskljuĉivanje dogaĊaja sa dve ispravne kopije. Verovatnoća Q2/MC: U ovom sluĉaju reĉ je o dogaĊaju koji se odnosi na uspešan prenos dve kopije posle otkaza MC procedure. Po prijemu kopija dobija se matrica ME koju karakteriše sledeće: (iii) dve kopije su primljene bez grešaka, a (iv) ostale kopije sadrţe greške, pri ĉemu bar na jednoj od L kolona postoje tri greške koje obezbeĊuju neuspeh MC procedure. Verovatnoća ovog kompleksnog dogaĊaja moţe se predstaviti izrazom:                    i ij L ji L j L iMC pp P qqQ 11/2 . (2.3.6) Prvi ĉinilac u dvostrukoj sumi, Lj L i qq odgovara dogaĊaju pod (iii), a ĉinilac u uglastoj zagradi, dogaĊaju pod (iv). Verovatnoća QSC/MC: QSC/MC predstavlja verovatnoću uspeha SC procedure pod uslovom da je MC procedura bila neuspešna. Saglasno izrazu (2.3.2), ova verovatnoća je jednaka zbiru verovatnoća Q1/MC i Q2/MC. Budući da vredi:                                     i ij L ji L j L i i ij L ji L j L i pp P qq pp P qq 11211 , (2.3.7) dobijamo,                                       i ij L ji L j L i L ij ji j ii L iMCSC pp P qq pp P q p P qQ 1111/ . (2.3.8) 24 Verovatnoća PSC+MC: Zamenujući (2.3.4a) i (2.3.8) u (2.3.1), nalazimo:                                                                i ij L ji L j L i L ij ji j ii L i L i i jiij ji i iMCSC pp P qq pp P q p P q pp P qq p P qPP 11 11 11 , (2.3.9) što predstavlja konaĉni rezultat. Specijalni sluĉaj: U posebnom sluĉaju, kada su kanalne verovatnoće meĊusobno jednake, tj. kada je pppppp  54321 (i konsekventno 544321 qqqqqq  pq  1 ), izraz (2.3.9) postaje:      LL LL LS MCSC pq qppq qpqppP )1(110 )41(15 )1051(1 32 34 2345      . (2.3.10) Imajući u vidu poznate jednakosti: 51423324155 510105)(1 pqpqpqpqpqqp  , 4)(1 qp  41322314 464 pqpqpqpq  i 3)(1 qp  312213 33 pqpqpq  , izraz (2.3.10) postaje:      LL LL LS MCSC qppqqq qppqqq qppqqP )33(110 )64(15 )105(1 12232 2234 3245      . (2.3.11a) Prethodni izraz, kao i u sluĉaju 3m moţemo napisati u obliku:                                        * 0 * 0 1)1( m i L jim m j jiLiS MCSC qp j im q i m P , (2.3.11b) gde je 5m i   22/ *  mm . 2.3.2. Aproksimativni izrazi za verovatnoću retransmisije Kao i u sluĉaju šeme sa tri nezavisna kanala i ovde je verovatnoća retransmisije jednaka nuli ako je bilo koja od kanalnih verovatnoća jednaka nuli. Saglasno tome, u uslovima kada kanalne verovatnoće dobijaju veoma male vrednosti, verovatnoću retransmisije moţemo da predstavimo u obliku: )],,,,(1[ 54321 5 pppppFpKP EMCSC  , (2.3.12) 25 pri ĉemu je K konstanta, ),,,,( 54321 pppppF polinom stepena 1L po promenljivoj kp )5,,2,1( k , a verovatnoća 5 1 54321 )( ppppppE  , (2.3.13) ekvivalentna kanalna verovatnoća. Razvijanjem izraza (2.3.11) nalazimo da vredi: LLLK  61510 23 . (2.3.14) Numeriĉke provere pokazuju da je vrednost polinoma ),,,,( 54321 pppppF nenegativna i da teţi nuli kada kanalne verovatnoće teţe nuli. Na osnovu ovog moguće su dve hipoteze:  u uslovima kada je za svako k )5,,2,1( k proizvod kpL  manji od 1, izraz (2.3.11), pri uslovu Epp  , predstavlja pogodnu aproksimativnu formulu za procenu kanalne verovatnoće. Kao i u sluĉaju 3m , ovaj aproksimativni izraz ćemo oznaĉiti sa E MCSCP  ;  u uslovima kada je L veće od 20, (a u praksi je L > 40), izraz 54321 310 pppppLPU MCSC  , (2.3.15) predstavlja gornju granicu verovatnoće retransmisije MCSCP  . Na slici 2.6 predstavljena je provera prethodne dve hipoteze za sluĉaj kada koeficijenti rasejavanja imaju sledeće vrednosti: kx {1/10, 1/3, 1, 3, 10}. Vidimo da veće odstupanje izmeĊu tri grafika postoji tek kada proizvod duţine okvira i ekvivalentne kanalne verovatnoće, EpL  , premašuje vrednost 0.5. Ekvivalentna kanalna verovatnoca, pE V er o v a tn o c a r et r a n sm is ij e, P S C + M C PSC+MC U PSC+MC E PSC+MC L = 50 L = 2000 Slika 2.6. Prikaz gornje granice, aproksimativne i egzaktne vrednosti verovatnoće retransmisije u funkciji ekvivalentne kanalne verovatnoće, (L=50 i L=2000, m = 5; x1 = 1/10, x2 = 1/3; x3 = 1; x4 = 3 i x5 = 10). 26 2.4. SC+MC procedura za opšti broj kanala OdreĊivanje verovatnoće retransmisije u prethodna dva sluĉaja imalo je za cilj nalaţenje pojedinaĉnih rešenja za 3m i 5m kanala. Primenjena metodologija ukazala je na znatno povećanje kompleksnosti izvoĊenja u sluĉaju 5m u odnosu na sluĉaj 3m bez jasnog sagledavanja kako da se problem reši kada je m veće od 5. Iz tog razloga odustalo se od partikularnog pristupa i traţena je nova metodologija. Rešenje je naĊeno u modifikaciji i proširenju metode koju su primenili R. Cam, C Leung i C. Lam [21] – [23] razmatrajući sluĉaj kombinovane SC i MC procedure sa proizvoljnim brojem kanala. MeĊutim, njihovo rešenje je primenljivo samo kada su kanalne verovatnoće meĊusobno jednake, dok je suštinski zahtev u ovoj tezi da ove verovatnoće budu razliĉite. Izlaganje u ovom potpoglavlju je podeljeno na tri odeljaka. U prvom odeljku izloţene su osnovne postavke predloţene metodologije za raĉunanje verovatnoće retransmisije u sluĉaju proizvoljnog broja kanala. Drugi odeljak sadrţi objašnjenje pojmova i veliĉina potrebnih za izvoĊenje opšteg izraza. Sam postupak izvoĊenja je dat u trećem odeljku. 2.4.1. Metodologija za računanje verovatnoće retransmisije Kao prvo, oznaĉimo sa A i B dogaĊaje koji redom predstavljaju uspehe SC i MC procedura. Tada uspeh kombinovane procedure matematiĉki moţemo predstaviti kao dogaĊaj “A ili B”, što ćemo oznaĉiti sa B . Verovatnoća retransmisije je jednaka verovatnoći suprotnog dogaĊaja dogaĊaju B , što se moţe napisati posredstvom izraza:    BABAP CMCSC  Pr1)(Pr , (2.4.1) pri ĉemu smo sa  XPr oznaĉili verovatnoću dogaĊaja X, a sa XC, dogaĊaj suprotan (komplementaran) dogaĊaju X. Koristeći poznate jednakosti AABBBAB CC  )()( i imajući u vidu da su dogaĊaji )( CYX  i Y meĊusobno iskljuĉivi, izraz (2.4.1) moţemo prepisati u obliku:        CCCMCSC BABBABP  PrPrPrPr1 , (2.4.2) odnosno u obliku:        CCCMCSC ABAABAP  PrPrPrPr1 . (2.4.3) U izrazu (2.4.2),  CBPr oznaĉava verovatnoću retransmisije u sluĉaju u kome bi bila primenjena samo MC procedura, a  CBAPr “doprinos” usled dodatne primene SC procedure. Obrnuto, u jednaĉini (2.4.3),  CAPr oznaĉava verovatnoću retransmisije u sluĉaju kada bi bila primenjena samo SC procedura, a  CABPr “doprinos” usled dodatne primene MC procedure. Budući da dogaĊaj A predstavlja uniju m meĊusobno nezavisnih dogaĊaja Ai ),,1( mi  , tj. mAAAA  21 , (2.4.4) pri ĉemu je sa Ai oznaĉen dogaĊaj uspešnog prenosa okvira u i-tom kanalu, procenjujemo da je jednostavnije da dalje razmatranje zasnivamo na izrazu (2.4.2). Saglasno tome, u nastavku izlaganja prvo ćemo paţnju posvetiti razvijanju izraza za verovatnoću  CBAPr . 27 Imajući u vidu jednakost )()()()( 2121 C m CCC m BABABABAAA   i uvodeći smenu i C i ZBA  , moţemo pisati:   }Pr{Pr 21 mC ZZZBA   . (2.4.5) Na osnovu “generalizovanog pravila uključivanja i isključivanja” [31] – [33], sledi:   }Pr{)1( }Pr{)1( }Pr{}Pr{Pr 21 1 1 1 11 21 21 21 211 1 m m iii miii k ii mii m i i C ZZZ ZZZ ZZZBA k k               , (2.4.6) odnosno, u ekvivalentnom obliku:   }Pr{)1(Pr 21 2111 1 k k iii miii m k kC ZZZBA        . (2.4.7) Budući da vredi jednakost Ck C k CC BAAABABABA  )()()()( 2121  moţemo da pišemo: })Pr{(}Pr{ 2121 C kk BAAAZZZ   . (2.4.8) Odavde sledi: )}/(Pr{)}Pr{(}Pr{ 212121 k C kk AAABAAAZZZ   . (2.4.9) Budući da su dogaĊji Ai meĊusobno nezavisni, vredi: )}/(Pr{}Pr{}Pr{ 21 21 11 21 kj k iii C k j i miii k AAABAZZZ       , (2.4.10) tako da izraz (2.4.7) postaje:   )}/(Pr{}Pr{)1(Pr 21 21 111 1 kj k iii C k j i miii m k kC AAABABA        (2.4.11) Ako sa A0 oznaĉimo dogaĊaj “ni jedna kopija nije preneta bez grešaka”, moţemo formalno da uvedemo sledeću definiciju:  CkiiiC k j i miii BAAABA kj k Pr)}/(Pr{}Pr{ 0 11 21 21        . (2.4.12) Obzirom da vredi    BBC Pr1Pr  , izraz (2.4.2) dobija opšti oblik: )}/(Pr{}Pr{)1( 21 21 110 kj k iii C k j i miii m k k MCSC AAABAP        . (2.4.13) 28 Na ovom mestu treba istaći da )}/(Pr{ 21 kiii C AAAB   oznaĉava verovatnoću dogaĊaja “neuspeh MC procedure posle prijema k ispravnih kopija sa rednim brojevima i1, i2,…,ik”. Potpuno je jasno da je verovatnoća ovog dogaĊaja jednaka nuli ukoliko je broj ispravno primljenih kopija veći od m*. Stoga sledi: )}/(Pr{}Pr{)1( 21 21 11 * 0 kj k iii C k j i miii m k k MCSC AAABAP        . (2.4.14) U našem daljem razmatranju smatraćemo da ovaj izraz predstavlja opštu polaznu formulu za izraĉunavanje verovatnoće retransmisije za proizvoljnu neparnu vrednost broja kanala m pri ĉemu je  2mm / *  . Napomenimo da se izraz (2.4.13) moţe iskoristiti za odreĊivanje verovatnoće retransmisije u sluĉaju kada se primenjuje iskljuĉivo procedura SC. Naime, posledica ĉinjenice da procedura MC nije aktivna, ekvivalentna je neuspehu ove procedure nezavisno od broja ispravno primljenih kopija. Saglasno tome, u ovom sluĉaju, verovatnoća )}/(Pr{ 21 kiii C AAAB   je jednaka 1 za sve vrednosti indeksa k i sve kombinacije ispravno primljenih kopija. Izraz (2.4.13) tada postaje:     k j i miii m k k SC j k AP 110 }Pr{)1( 21   , (2.4.15) što je u stvari razvijena forma izraza: )}Pr{1( 1    m j jSC AP . (2.4.15a) koji predstavlja verovatnoću retransmisije u sluĉaju SC procedure. 2.4.2. Preliminarne definicije, oznake i pomoćne veličine Sada ćemo definisati niz pomoćnih veliĉina i uvešćemo posebne oznake sa ciljem da omogućimo relativno jednostavno dalje razvijanje opštih matematiĉkih izraza za verovatnoću retransmisije za SC+MC proceduru. U tu svrhu na slici 2.7 šematski je prikazan niz od m registara u kojima su smeštene kopije istog okvira. Sa ciljem da se predstavi jedna karakteristiĉna “konfiguracija”, registri su poreĊani jedan ispod drugog i podeljeni u dve podgrupe. Prvu podgrupu ĉini niz od k meĊusobno razdvojenih registara. Ćelije ovih registara su osenĉene zelenom bojom ukazujući time na ĉinjenicu da one sadrţe ispravno prenete bite. Druga podgrupa se sastoji od m-k registara koji sadrţe pogrešno prenete kopije. Budući da se kod ove grupe okvira postojeće greške mogu korigovati samo posredstvom MC procedure primenjene nad bitima koji se nalaze na istim pozicijama u razliĉitim kopijama, registri su u ovom sluĉaju predstavljeni u okviru matriĉne šeme (sa m-k redova i L kolona), a kao karakteristiĉna, istaknuta je l-ta “pozicija” (kolona). Pretpostavljeno je da prvih m-k-s registara na ovoj poziciji sadrţe ispravno prenete bite, a da su biti u poslednjih s registara neispravni (što je oznaĉeno crvenom bojom). Ostale ćelije na slici su osenĉene ţutom bojom, što znaĉi da je neizvesno da li te ćelije sadrţe ispravno ili neispravno prenete bite. Za potrebe naše analize nije bitno samo da se utvrdi karakteristiĉna “konfiguracija”, već takoĊe i broj sluĉajeva u kojima se pojavljuje posmatrana karakteristiĉna konfiguracija. Imajući to u vidu, a referišući se na sliku 2.7, definisaćemo niz kolekcija dogaĊaja i odredićemo verovatnoće njihovog “pojavljivanja”. 29 r[m] i1 i2 ik greška  kivm 1 Ll nema greške j1 j2 js  sj vw km ,   Cvm ki  kivm Slika 2.7. Prikaz memorisanih kopija i ilustracija podskupova ][kivm i ][ , sj vw km . Definicija 2.4.1. Pod skupom prenetih kopija podrazumevaćemo sadrţaj registra prikazanog na slici 2.7, posle prijema i memorisanja svih m kopija emitovanog okvira, nezavisno od broja grešaka u informacionom i CRC delu. Ovaj skup ćemo matematiĉki oznaĉiti sa },...,2,1{][ mmr  , pri ĉemu smo umesto oznake Fi za prenetu kopiju u i-tom kanalu, koristili oznaku i. Budući da je pretpostavljena pouzdana identifikacija okvira na prijemu, memorisanje skupa ][mr smatraćemo sigurnim dogaĊajem. Ta pretpostavka će matematiĉki biti iskazana izrazom 1]}[Pr{ mr . Definicija 2.4.2. Pod kombinacijom klase k podrazumevaćemo kolekciju },,{][ 2,1 v k vvv m iiiki  skupa ][mr , pri ĉemu vui )1( ku  predstavlja kopiju prenetog okvira, a v,        k m v1 , redni broj kolekcije. U specijalnom sluĉaju, kada je k = 0, podskup ][kivm je prazan, a u slucaju k = m, kolekcija ][ki v m ima samo jedan ĉlan koji je ujedno jednak kompletnom skupu prenetih kopija, tj. v = 1 i ][][1 mrkim  . Generalno, podrazumevamo da su elementi kolekcije ][1 kim ureĊeni po veliĉini rednog broja kanala, tj. kiii  21 . Definicija 2.4.3. Pod komplementarnim podskupom podrazumevaćemo podskup ][\][][ kimrki vm Cv m  Njegove elemente ĉini m-k kopija koje istovremeno pripadaju skupu ][mr i ne pripadaju kolekciji ][kivm . Definicija 2.4.4. Pod kombinacijom klase s nad komplementarnim podskupom podrazumevaćemo kolekciju kopija },...,,{][ ,,2 , 1 , vw s vwvwvw km jjjsj  koje pripadaju podskupu Cv m ki ][ . Indeks s ispunjava uslov kms0  , a indeks w,         s km w1 oznaĉava redni broj kolekcije. I u sluĉaju ovog podskupa podrazumevamo ureĊenost elemenata, tj. vws vwvw jjj ,,2 , 1   . 30 Definicija 2.4.5. Pod skupom “pomoćnih” verovatnoća podrazumevaćemo kolekciju verovatnoća bez obaveznog konkretnog “fiziĉkog” znaĉenja, koje ne moraju biti neposredno u skladu sa postavkama na slici 2.7. To su:     m i ipP 1 , (2.4.16a)     m i iqQ 1 , ii p1q  , (2.4.16b)  ),( vkPi – verovatnoća da na poziciji l )1( Ll  sve kopije iz klase ][ki v m sadrţe pogrešno preneti bit.           ][ 0, 0,1 ),( kiu ui v m kzap kza vkP (2.4.17)  ),( vkQi – verovatnoća da na poziciji l )1( Ll  sve kopije iz klase ][ki v m sadrţe ispravno preneti bit.           ][ 0za, 0za,1 ),( kiu ui v m kq k vkQ (2.4.18)  ),,,( svwkP j – verovatnoća da na poziciji l )1( Ll  sve kopije iz klase ][ , sj vw km sadrţe pogrešno preneti bit.           0za, 0za,1 ),,,( ][, sp s wsvkP sju uj vw km (2.4.19)  ),,,( svwkQ j – verovatnoća da na poziciji l )1( Ll  sve kopije iz klase ][ , sj vw km sadrţe ispravno preneti bit.           0za, 0za,1 ),,,( ][, sq s wsvkQ sju uj vw km (2.4.20) Verovatnoća dogaĊaja sa najviše h grešaka: Posmatrajmo komplementarni podskup sa ciljem da odredimo verovatnoću dogaĊaja da na bilo kojoj poziciji ima najviše h grešaka. Tu verovatnoću oznaĉićemo sa )][/(]1[ Cv mL kihP  . Rešavajući postavljeni zadatak, prvo ćemo definisati verovatnoću da na poziciji l ( Ll 1 ) kopije iz klase ][, sj vw km sadrţe pogrešno preneti bit, a preostale kopije iz skupa Cv m ki ][ , ispravno preneti bit. Koristeći definicije (2.4.16b), (2.4.18), (2.4.19) i (2.4.20), ovu verovatnoću moţemo da izrazimo preko formule: ),,,( ),,,( ),( ])[( , wsvkQ wsvkP vkQ Q sjP j j i vw kml  . (2.4.21) 31 U narednom koraku odredićemo verovatnoću da kopije iz skupa Cvm ki ][ imaju na poziciji l najviše h grešaka. Ta verovatnoća glasi:             h s s km w j j i Cv ml wsvkQ wsvkP vkQ Q kihP 0 1 ),,,( ),,,( ),( )][/( . (2.4.22a) Moţe se pokazati da za sve vrednosti kmh0  vredi: 1 ),,,( ),,,( ),(),,,( ),,,( ),( 1 0 10 1                       hkm s s km w j j i h s s km w j j i wsvkP wsvkQ vkP P wsvkQ wsvkP vkQ Q , (2.4.23) tako da se za verovatnoću )][/( Cvml kihP  dobija alternativna formula:              1 0 1 ),,,( ),,,( ),( 1)][/( hkm s s km w j j i Cv ml wsvkP wsvkQ vkP P kihP . (2.4.22b) Specijalno, u sluĉaju kada je kmh  , imamo: 1)][/)(()][/(   Cv mlkmh Cv ml kikmPkihP . (2.4.22c) Budući da su greške na razliĉitim pozicijama meĊusobno nezavisne, verovatnoća da kopije iz podskupa Cvm ki ][ na bilo kojoj poziciji imaju najviše h grešaka, iznosi LCvml Cv mL kihPkihP )]][/([)][/(]1[  . (2.4.24) Saglasno (2.4.22c), ako je kmh  , ova verovatnoća postaje jednaka 1. 2.4.3. Izraz za verovatnoću retransmisije za opšti broj kanala Koristeći pojmove i oznake uvedene u prethodnom odeljku, u ovom odeljku biće izvedena formula za verovatnoću retransmisije. U postupku koji sledi poĉinjemo od višestruke sume u izrazu (2.4.14). Izdvajajući proizvoljnu kombinaciju ispravno prenetih kopija },...,,{][ vk v 2 v 1 v iiiki m  , ovu višestruku sumu moţemo predstaviti u ekvivalentnom obliku: }/Pr{}Pr{ )}/(Pr{}Pr{ ][1 ][ 11 21 21    kiu u C k m v kiu u iii C k j i miii v m v m kj k ABA AAABA                 . (2.4.25) Imajući u vidu definiciju (2.4.18) uveravamo se da vredi: Li kiu u vkQA v m )],([}Pr{ ][   . (2.4.26) 32 Pored toga, imajući u vidu rezultat (2.4.24), moţemo da pišemo: )][/*(}/Pr{ ][ ][ Cv mL1 kiu u C kimP1AB v m     . (2.4.27) Naime, da bi MC procedura bila neuspešna, neophodno je da bar na jednoj bitskoj poziciji bude više od *m grešaka, što je eksplicitno iskazano desnom stranom izraza (2.4.27). Nizom uzastopnih smena, prvo (2.4.27) i (2.4.26) u (2.4.25), a zatim (2.4.25) u (2.4.14), dobijamo: )]][/*(1[)],([)1( ]1[ 1 * 0 Cv mL k m v L i m k k MCSC kimPvkQP            . (2.4.28) Oblik traţene formule za izraĉunavanje verovatnoće retransmisije zavisi sada od izraza kojim će biti predstavljena verovatnoća )][/*(]1[ Cv mL kimP  . Ukoliko se koristi izraz (2.4.22a) dobijamo:                                               L m s s km w j j i k m v L i m k k MCSC wsvkQ wsvkP vkQ Q vkQP * 0 11 * 0 ),,,( ),,,( ),( 1)],([)1( , (2.4.29a) a ukoliko se koristi izraz (2.4.22b) sledi:                                                L km s s km w j j i k m v L i m k k MCSC wsvkP wsvkQ vkP P vkQP * 0 11 * 0 ),,,( ),,,( ),( 11)],([)1( . (2.4.29b) Imajući u vidu definicije (2.4.17) – (2.4.20) prethodna dva izraza za verovatnoću retransmisije moţemo redom predstaviti na sledeći naĉin:                                    L m s jj jj iijj mjjii L ii mii m k k MCSC s s ks sk k k qq pp qq Q qqP * 0 ,,,, 11 * 0 1 1 11 11 1 1 1)()1(        , (2.4.30a) odnosno, u drugom obliku,                                     L km s jj jj iijj mjjii L ii mii m k k MCSC s s ks sk k k pp qq pp P qqP * 0 ,,,, 11 * 0 1 1 11 11 1 1 11)()1(        , (2.4.30b) uz napomenu da kod višedimenzionalnih suma proizvod verovatnoća uiii qqq  21 dobija vrednost 1 ukoliko je indeks u jednak nuli. Izrazi (2.4.30a) i (2.4.30b) predstavljaju jednu od mogućih traţenih formula za izraĉunavanje verovatnoće retransmisije. One vrede za proizvoljne vrednosti kanalnih verovatnoća, proizvoljnu duţinu paketa i proizvoljni neparan broj kanala (diverziti grana) koji je veći od 1. 33 Specijalni sluĉaj: U posebnom sluĉaju, kada su kanalne verovatnoće meĊusobno jednake, tj. kada je ppk  i pqqk  1 za sve vrednosti indeksa k, izraz (2.4.30a) postaje:                                      * 0 * 0 1)1( m k L skm m s skLkS MCSC qp s km q k m P , (2.4.31) uz uslov  2/ * mm  . Napomenimo da smo isti izraz dobili u dva navrata ranije, kada smo razmatrali sluĉajeve 3m i 5m , (videti (2.2.5b) i (2.3.11b)). Ilustrativni primer: Kao i u sluĉaju egzaktnih izraza za tri i pet ponavljanja kopija, vidimo da su izrazi (2.4.30a) i (2.4.30b) za verovatnoću retransmisije kompleksni i kao takvi ne mogu posluţiti za brzo sagledavanje uticaja pojedinih parametara kao što su broj kanala m, verovatnoće u pojedinim kanalima kp ),...,1( mk  i duţina okvira L. Iz tog razloga ćemo razmotriti pogodne aproksimativne izraze za verovatnoću retransmisije u funkciji ekvivalentne kanalne verovatnoće. Na slici 2.8 dat je skup grafika koji prikazuju zavisnost verovatnoće retransmisije u funkciji ekvivalentne kanalne verovatnoće za sluĉajeve: (i) broj kanala, m = 7 (slika pod a), m = 9 (slika pod b) i m = 11 (slika pod c); (ii) duţina okvira, L = 72 i L = 1024, i (iii) koeficijenti rasejavanja, 0.11 x i )1(/110  mkx , ),...,2( mk  . Pored korišćenja egzaktne formule (2.4.30a), prikazani su i rezultati dobijeni posredstvom aproksimativne formule:                                      * 0 * 0 )1(1)1()1( m k L skm E m s s E kL E kE MCSC pp s km p k m P , (2.4.32) kao i rezultati dobijeni posredstvom formule: mE mmU MCSC pL m m P         * * . (2.4.33) Prethodne dve formule dobijene su sa istim obrazloţenjem kao u prvom odeljku potpoglavlja 2.3. To znaĉi da je prva od njih izvedena iz izraza (2.4.31) tako što je promenljiva p zamenjena sa pE. Druga je dobijena prostom generalizacijom za 3m i 5m kanala. U oba sluĉaja ekvivalentna kanalna verovatnoća definisana je kao geometrijska srednja vrednost pojedinaĉnih kanalnih verovatnoća, tj. kao: mm k kE pp 1 1            . (2.4.34) 34 V er o v a tn o c a r et r a n sm is ij e, P S C + M C Ekvivalentna kanalna verovatnoca, pE PSC+MC U PSC+MC E PSC+MC L = L = 1024 72 (a) V er o v a tn o c a r et r a n sm is ij e, P S C + M C Ekvivalentna kanalna verovatnoca, pE PSC+MC U PSC+MC E PSC+MC L = L = 1024 72 (b) 35 Ekvivalentna kanalna verovatnoca, pE L = 1024 L = PSC+MC U PSC+MC E PSC+MC 72 V er o v a tn o c a r et r a n sm is ij e, P S C + M C (c) Slika 2.8. Prikaz gornje granice, egzaktne i aproksimativne vrednosti verovatnoće retransmisije u funkciji ekvivalentne kanalne verovatnoće za: (a) m = 7, (b) m = 9, i (c) m = 11 (SC1, L = 72 i L = 1024). Na osnovu prikazanih grafika zakljuĉujemo da sa povećanjem duţine okvira L, broja paralelnih kanala m i ekvivalentne kanalne verovatnoće pE, opada “kvalitet” uvedenih aproksimativnih izraza. MeĊutim, kako se ovim aproksimacijama ne menja oblik, priroda i meĊusobni odnos grafika za razliĉite vrednosti parametra m, ove aproksimacije se mogu koristiti u preliminarnim analizama u kojima je cilj da se dobije gruba, ali pregledna ocena razmatranih modela. 2.5. Efikasnost SC+MC procedure U ovom potpoglavlju razmotrićemo efikasnost SC+MC procedure sa stanovišta procene u kojoj meri MC procedura doprinosi smanjenju verovatnoće retransmisije u odnosu na SC proceduru. Pri tome, imaćemo u vidu sluĉaj beţiĉnih senzorskih mreţa u kojima se duţina okvira kreće u granicama od nekoliko desetina bita do nekoliko hiljada bita, a iznos kanalnih verovatnoća moţe biti veoma razliĉit, od relativno malih vrednosti reda 10-5 pa do maksimalne moguće vrednosti 0.5. U prvom koraku, razmatranje efikasnosti SC+MC procedure ima za cilj uporedni pregled grafiĉkog prikaza familija verovatnoća retransmisije za SC i SC+MC procedure. U drugom koraku koristiće se kvantitativni pokazatelji kao što su doprinos i dobitak. U oba sluĉaja, ocena efikasnosti će se vršiti u funkciji ekvivalentne kanalne verovatnoće pri ĉemu se koeficijenti rasejavanja kreću u granicama 0.1 – 10. 36 2.5.1. Uporedni pregled SC i SC+MC procedura U ovom odeljku će biti razmotreni uticaji: (i) rasejavanja kanalnih verovatnoća, (ii) broja kanala i (iii) duţine okvira, na verovatnoću retransmisije za SC i SC+MC procedure. Efekat rasejavanja: U pregledu koji sledi odabrano je pet klasa rasejavanja kanalnih verovatnoća, oznaĉenih sa SC1 – SC5, za koje smatramo da predstavljaju dobre reprezente za realnu procenu kompletnog uticaja na verovatnoću retransmisije. Konkretno, klase su definisane na sledeći naĉin:  koeficijenti rasejavanja )(ix klase SC1 odabrani su saglasno izrazu (2.5.1a) i na logaritamskoj skali su ravnomerno rasporeĊeni u opsegu 1/D – D. SC1: miD D x i m i ,,1, 1 1 1 2             , (2.5.1a)  u sluĉaju klase SC2, jedna kanalna verovatnoća je jednaka ekvivalentnoj, a ostale su podeljene u dve jednako brojne grupe, pri ĉemu su u jednoj grupi kanalne verovatnoće D puta veće, a u drugoj D puta manje od ekvivalentne kanalne verovatnoće. Prema tome, vredi: SC2:                 2,,2,1, 1 12,1 ,,22, mi D mi mmiD xi   , (2.5.1b)  klasa SC3 je izabrana tako da jedan kanal ima D puta manju, a jedan D puta veću vrednost, a svi ostali, jednaku vrednost ekvivalentnoj kanalnoj verovatnoći. Saglasno tome, vredi: SC3:            1, 1 1,1 , i D mi miD xi , (2.5.1c)  u sluĉaju klase SC4, jedan kanal je dobar i ima D puta manju kanalnu verovatnoću od ekvivalentne, a svi ostali kanali su loši i sa jednakim kanalnim verovatnoćama. Koeficijenti rasejavanja su dati izrazom: SC4:           miD i Dx m i ,,3,2, 1, 1 1 1  , (2.5.1d)  konaĉno, klasa SC5 je “reciproĉna” klasi SC4, pri ĉemu je jedan kanal loš, a svi ostali su podjednako dobri. Prema tome, vredi: SC5:          miD iD x m i ,,3,2, 1, 1 1  . (2.5.1e) Napomenimo da koeficijenti rasejavanja ispunjavaju uslov 121  mxxx  . 37 Na slici 2.9 je ilustrovan efekat rasejavanja na verovatnoću retransmisije u sluĉajevima kada broj kanala iznosi m = 3 (slika pod a), m = 7 (slika pod b) i m = 11 (slika pod c). Ostali parametri su L = 1024 i D = 10. Ekvivalentna kanalna verovatnoća, pE V er o v a tn o ća r et ra n sm is ij e, P S C , P S C + M C PSC PSC+MC (a) PSC PSC+MC Ekvivalentna kanalna verovatnoća, pE V er o v a tn o ća r et ra n sm is ij e, P S C , P S C + M C (b) 38 PSC+MC PSC Ekvivalentna kanalna verovatnoća, pE V er o v a tn o ća r et ra n sm is ij e, P S C , P S C + M C (c) Slika 2.9. Efekat rasejavanja na verovatnoće retransmisije u funkciji ekvivalentne kanalne verovatnoće, (a) m = 3, (b) m = 7, i m = 11, (L = 1024, D = 10, SC1 klasa je oznaĉena zvezdicom) Opšti zakljuĉak, koji se moţe izvesti je da je efekat rasejavanja veći kod SC procedure nego kod SC+MC procedure pri istim uslovima, da raste sa porastom ekvivalentne kanalne verovatnoće, i da je utoliko veći ukoliko je broj kanala veći. U sluĉajevima kada je ekvivalentna kanalna verovatnoća mala, pri malom broju kanala i maloj vrednosti parametra D, efekat rasejavanja je mali tako da se umesto razliĉitih kanalnih verovatnoća, verovatnoća retransmisije moţe analizirati preko ekvivalentne kanalne verovatnoće. To posebno vaţi za SC+MC proceduru kada je m = 3 ili 5, D manje od 10, a pE manje od 10 -2 i L manje od 1024. Efekat broja kanala: Na slici 2.10 su prikazane verovatnoće retransmisije SC (slika pod a) i SC+MC (slika pod b) procedura u funkciji ekvivalentne kanalne verovatnoće pE za L = 1024 bita, gde je parametar broj kanala. Pretpostavljeno je da je funkcija rasejavanja definisana prema Klasi 1, pri ĉemu je vrednost parametra D jednaka 10. 39 Ekvivalentna kanalna verovatnoća, pE V er o v a tn o ća r et ra n sm is ij e, P S C (a) Ekvivalentna kanalna verovatnoća, pE V er o v a tn o ća r et ra n sm is ij e, P S C + M C (b) Slika 2.10. Verovatnoća retransmisije u funkciji ekvivalentne kanalne verovatnoće, (a) SC procedura, (b) SC+MC procedura, (L = 1024 i m = 3, 5, 7, 9 i 11). Kao što se i oĉekivalo, verovatnoća retransmisije u obe procedure, SC i SC+MC, raste sa porastom kanalne verovatnoće pE i smanjuje se sa povećanjem broja kanala m. U graniĉnim sluĉajevima, nezavisno od broja kanala, verovatnoće retransmisija imaju istu vrednost, nula, kada je pE = 0 i pribliţno jedan, kada je pE = 0.5. Pri tome, konveksnost grafika je izraţenija kod SC procedure što ima za posledicu oĉekivani rezultat da je izmeĊu graniĉnih sluĉajeva PSC veće od PSC+MC. 40 Efekat dužine okvira: Generalno, sa povećanjem duţine okvira raste verovatnoća retransmisije. Priroda povećanja je ilustrovana na slici 2.11 na kojoj su zbog preglednosti prikazani grafici za m = 3 i m = 11 kanala. Sa slike moţemo da zakljuĉimo da se razlika izmeĊu verovatnoća retransmisije povećava sa povećanjem broja kanala. V er o v a tn o ća r et ra n sm is ij e Dužina okvira, L Slika 2.11. Verovatnoća retransmisije u funkciji dužine okvira, (pE = 10 -2 i m = 3 i 11). Na osnovu prethodnih slika zakljuĉujemo da je izborom parametara m i L moguće kontrolisati vrednosti verovatnoća retransmisije u širokim granicama. Oĉekuje se da u praktiĉnim realizacijama m neće imati veću vrednost od 5, a sve preko toga ima akademski znaĉaj. 2.5.2. Analiza doprinosa MC procedure Pod doprinosom MC procedure u ovoj tezi podrazumevamo kvantitativnu ocenu koja pokazuje u kojoj meri je primenom SC+MC procedure smanjena verovatnoća retransmisije u odnosu na SC proceduru. U tom smislu koristićemo dve definicije:  doprinos u apsolutnom smislu, ./ |)( constpMCSCSCSCMC EPPQ  , (2.5.2)  doprinos u relativnom smislu, .// |)/log(10 constpMCSCSCMCSCMC EPQq  [dB]. (2.5.3) Iz ovih definicija se vidi da apsolutni doprinos QMC/SC predstavlja meru “za koliko” se smanjuje verovatnoća retransmisije kada se SC procedura “dopuni” MC procedurom. Za one vrednosti kanalnih verovatnoća za koje je PSC dosta veće od PSC+MC , relativni doprinos qMC/SC se moţe tumaĉiti kao mera (izraţena u dB) koja pokazuje “koliko puta” je verovatnoća retransmisije manja kod SC+MC nego kod SC procedure. 41 Na slici 2.12 prikazana je zavisnost apsolutnog (slika pod a) i relativnog (slika pod b) doprinosa u funkciji ekvivalentne kanalne verovatnoće pE. Korišćeni su isti parametri kao na slici 2.10. Vidimo da grafici koji predstavljaju „apsolutni“ doprinos imaju “zvonasti” oblik, pri ĉemu se sa povećanjem m, poloţaji maksimuma pomeraju ka većim vrednostima verovatnoće pE i njihova vrednost raste sa porastom m. Dopunskom analizom, pokazuje se da se sa povećanjem L, poloţaji maksimuma pomeraju ka manjim vrednostima verovatnoće pE. Ekvivalentna kanalna verovatnoća, pE A p so lu tn i d o p ri n o s, Q M C /S C (a) Ekvivalentna kanalna verovatnoća, pE R el a ti v n i d o p ri n o s, q M C /S C [ d B ] * * *** * * * * * * ***** * * * ** *** * (b) Slika 2.12. Iznos (a) “apsolutnog” i (b) “relativnog” doprinosa u funkciji ekvivalentne kanalne verovatnoće (L = 1024 i m = 3, 5, 7, 9 i 11). Horizontalne linije predstavljaju graniĉne vrednosti (asimptote) za uslov kada pE teži nuli. 42 Zvonasti oblik grafika „apsolutnog“ doprinosa je posledica ograniĉenja: SCMCSCSCSCMC PPPQ  / , (2.5.4) MCMCSCMC P1QQ / , (2.5.5) što je ilustrativno prikazano na slici 2.13. Ilustracija se odnosi na šemu sa tri kanala, pri ĉemu duţina okvira iznosi L = 1024. Sliĉni oblici (sa razliĉitim konkretnim vrednostima ) dobijeni su i u ostalim analiziranim sluĉajevima. Ograniĉenje zvonaste krive QMC/SC sa leve strane je posledica (2.5.4). Naime, budući da su sve tri veliĉine pozitivne, u uslovima kada je verovatnoća PSC+MC veoma mala, QMC je neznatno manje od PSC. Granica sa desne strane je posledica (2.5.5) koja se zasniva na ĉinjenici da doprinos majoritetne logike posle neuspešne SC procedure ne moţe biti veći od doprinosa kada se primenjuje samo MC procedura. Drugim reĉima, pri malim vrednostima kanalnih verovatnoća, MC procedura praktiĉno uspeva da koriguje sve zaostale greške SC procedure, tako da QMC/SC “prati” krivu PSC. Sa daljim povećanjem pE, slabi sposobnost majoritetne logike da koriguje greške i QMC/SC ne moţe više da prati krivu PSC. i poĉinje da pada zajedno sa QMC. Ekvivalentna kanalna verovatnoća, pE G ra n iĉ n e v re d n o st i za Q M C /S C Slika 2.13. Dijagrami koji ilustruju ograniĉenja za QMC/SC. Grafici “relativnog” doprinosa ukazuju na interesantnu ĉinjenicu da relativni doprinos raste sa opadanjem ekvivalentne kanalne verovatnoće i u graniĉnim sluĉaju dostiţe asimptotske vrednosti: ]dB[1 * log10log10lim * 0 max /                                              mm m L P PP q mm MCSC MCSCSC p SCMC E . (2.5.6) Istaknimo još jednom da je u opsegu “od posebnog interesa” (tj. gde je 3107 Ep ) verovatnoća retransmisije PSC+MC znatno manja od verovatnoće PSC, tako da „relativni“ doprinos praktiĉno predstavlja faktor smanjenja verovatnoće retransmisije (iskazan u dB) usled primene dopunske MC procedure. Taj faktor opada sa porastom verovatnoće pE i utoliko je veći ukoliko je broj kanala veći. 43 2.5.3. Analiza dobitka MC procedure Alternativna karakteristika koja se ĉesto koristi pri odredjivanju performansi postupaka korekcije grešaka pri prenosu informacija je dobitak. U standardnom obliku, ova veliĉina predstavlja iznos promene (smanjenja) odnosa signal-šum (iskazan u dB) koji obezbeĊuje da se postupkom korekcije odrţi zadata referentna vrednost verovatnoće greške [5]. Kao referenca se koristi odgovarajući postupak bez primene korekcije grešaka. Na slici 2.14 dat je ilustrativni primer verovatnoće retransmisije za SC i SC+MC proceduru u funkciji odnosa snaga signal-šum, za duţinu okvira L = 1024 i m = 3 i 11 kanala. Odnos snaga signal-šum, gb [dB] V er o v a tn o ća r et ra n sm is ij e Pref = 1.0E-3 Pref = 1.0E-6 Pref = 1.0E-9 Slika 2.14. Verovatnoća retransmisije u funkciji odnosa snaga signal-šum, (parametri: L = 1024 i m = 3 i 11). U našem sluĉaju koristićemo standardnu definiciju dobitka, s tim što ćemo za referencu koristiti krive dobijene za SC proceduru pod istim uslovima (broj kanala i duţina okvira). Smatraćemo da vredi sledeća relacija izmeĊu odnosa snaga signal–šum po bitu, bg i ekvivalentne kanalne verovatnoće pE:         g  22 1 b E erfcp . (2.5.7) Ovo je poznata formula za verovatnoću greške po bitu pri koherentnoj demodulaciji QAM signala u prisustvu aditivnog Gausovog šuma [5]. Napomenimo da (2.5.7) treba prihvatiti uslovno, budući da pE predstavlja proseĉnu vrednost koja je definisana kao geometrijska srednja vrednost kanalnih verovatnoća. To oteţava da se na jednostavan naĉin u razmatranje uvede kao parametar odnos snaga signal–šum. Sa druge strane, veza izmeĊu verovatnoće greške po bitu i odnosa snaga signal– šum je monotona funkcija, pa stoga ne oĉekujemo da će doći do suštinskog “promašaja” u oceni dobitka. Na slici 2.15 prikazan je dobitak u funkciji broja paralelnih kanala. Primer je dat za dve duţine okvira, L = 1024 i L = 72, i tri referentne verovatnoće retransmisije naznaĉene na slici 2.14. 44 Broj kanala, m D o b it a k , G [d B ] (a) Broj kanala, m D o b it a k , G [d B ] (b) Slika 2.15. Dobitak u zavisnosti od broja kanala; (Parametri: dužina okvira (a) L = 1024 i (b) L = 72; referentna vrednost verovatnoće retransmisije Pref = 10 -3 , 10 -6 i 10 -9 ). Sa slike vidimo da je dobitak srazmeran broju paralelnih kanala i duţini okvira. Na primer, u sluĉaju L = 1024 i m = 9 dobitak se kreće u granicama od 2.1 dB (kada je Pref = 10 -9 ) do 3.4 dB (kada je Pref = 10 -3 ). Ako broj paralelnih kanala iznosi m = 3, pri istim uslovima, vrednosti dobitka su 0.7 – 1.4 dB. Sa druge strane, kada duţina okvira iznosi L = 72, dobitak je manji i znatno sporije raste sa porastom broja kanala. 45 3. ANALIZA PROPUSNOSTI IzvoĊenje izraza za verovatnoću retransmisije u prethodnom poglavlju zasnivalo se na pretpostavci da se postupci detekcije i identifikacije prenetih kopija odvijaju bez grešaka. MeĊutim, u realnim uslovima, uvek je moguće da u jednom ili u više kanala ovi postupci otkaţu, što ima za posledicu da se potreban broj kopija za aktiviranje MC procedure obezbeĊuje posle jedne ili više dodatnih retransmisija iste kopije okvira. Teorijski, moguć je veliki broj razliĉitih scenarija “prikupljanja” potrebnog broja kopija, što detaljnu analizu ĉini sloţenom. Sa ciljem dobijanja okvirnog uvida, odabrana su tri karakteristiĉna scenarija, a ukupni efekat utvrĊen je na bazi analize propusnosti. U literaturi postoji više definicija propusnosti [34] – [37]. Prema [37], propusnost linije za zadati ARQ mehanizam se definiše kao koliĉnik vremena potrebnog za emitovanje okvira i proseĉne vrednosti trajanja retransmisionih ciklusa potrebnih za njegov uspešan prenos. U suštini, prenos okvira se sastoji od sekvence retransmisionih ciklusa, pri ĉemu retransmisioni ciklus predstavlja niz dogaĊaja koji vode od poĉetnog inicijalnog stanja, preko tranzijentnih stanja koja nastaju usled uticaja grešaka u kanalu, do završnog inicijalnog stanja koje rezultuje uspešnim prenosom okvira. Imajući u vidu ĉinjenicu da se prelazi izmeĊu stanja ne odvijaju u jednakim vremenskim intervalima, nameće se potreba za uvoĊenjem parametra koji opisuje vremensku dimenziju prelaza. To znaĉi da je svaki prelaz izmeĊu dva stanja opisan verovatnoćom prelaza i trajanjem prelaza. Izlaganje je podeljeno na pet potpoglavlja. U prvom potpoglavlju, imajući u vidu prošireni ekvivalentni model kompletnog ARQ mehanizma, predstavljena su tri karakteristiĉna scenarija od kojih dva odgovaraju ekstremnim situacijama, dok je izbor trećeg imao za cilj da se ukaţe na kompleksnost analize propusnosti, ĉak i u uslovima kada broj kanala iznosi tri, a kanalne verovatnoće imaju istu vrednost. U narednim potpoglavljima, za svaki od predloţenih scenarija, izvedeni su egzaktni teorijski izrazi za propusnost. Izrazi su posluţili za grafiĉko predstavljanje propusnosti u funkciji ekvivalentne kanalne verovatnoće. TakoĊe, u ovim potpoglavljima su detaljno opisani simulacioni eksperimenti koji su potvrdili dobijene teorijske rezultate. U petom potpoglavlju izvršena je komparativna analiza odabranih scenarija i ukazano je na realne domete SC+MC procedure. IzvoĊenje izraza za prelazne verovatnoće u dijagramima stanja koji opisuju retransmisione mehanizme pojedinih scenarija je dato u prilogu B. 3.1. Karakteristiĉni scenariji U cilju jasnog definisanja pojedinih scenarija, na slici 3.1 je predstavljen ekvivalentni model za raĉunanje propusnosti ARQ šeme sa SC+MC procedurom. Predajna i prijemna strana su povezane sa m meĊusobno nezavisnih kanala sa razliĉitim kanalnim verovatnoćama p1, p2, ..., pm. Svaki od m kanala se koristi za prenos identiĉne kopije okvira koja se na predajnoj strani sastoji od korisniĉkog paketa (IT) i zaglavlja (HT) sa CRC bitima za detekciju grešaka pri prenosu. Predajni deo ĉine ARQ blok i predajnik. Zadatak ARQ bloka je da obezbedi formiranje okvira FT i sve 46 funkcije neohodne za njegovu retransmisiju. Prijemni deo se sastoji od m prijemnika i bafera sa registrima R1, R2,..., i Rm u koje se privremeno smešta najviše m kopija istog okvira. Zadatak prekidaĉa je da na istoj slici omogući predstavljanje tri karakteristiĉna scenarija. Prvi scenario (B1) je karakteristiĉan za “prostorni” diverziti (prekidaĉ je u poloţaju 1), a drugi (B2) i treći scenario (B3) za “vremenski” diverziti (prekidaĉ je u poloţaju 2). Koristeći rezultate iz prethodnog poglavlja, umesto pojedinaĉnih kanalnih verovatnoća p1, p2, ..., pm, analizu propusnosti ćemo vršiti svoĊenjem ovih verovatnoća na jednu vrednost p, koja je jednaka ekvivalentnoj kanalnoj verovatnoći pE. ML SC+MC kombajner F1 F2 Fm FML IR CRC potvrda prijema Tx FTIT ARQ pm p1 Rx Rx R1 R2 Rm Rx p2 (2)(1) (2)(1) Sl. 3.1. Ekvivalentni model za raĉunanje propusnosti ARQ šeme sa SC+MC procedurom Scenario B1: Ovaj scenario se odvija na sledeći naĉin, u prijemnik istovremeno stiţe m kopija istog okvira F1, F2, ..., i Fm koje se smeštaju u registre R1, R2, ..., i Rm. Ukoliko je kopija F1 primljena bez detektovane greške, prenos se proglašava uspešnim i predajniku se šalje pozitivna potvrda prijema (ACK), a odgovarajući paket IR se isporuĉuje korisniku. U suprotnom, ukoliko je okvir pogrešan, ispituje se ispravnost kopije F2. Ukoliko je kopija ispravna, prenos se proglašava uspešnim, šalje se pozitivna potvrda prijema i odgovarajući paket se prosleĊuje korisniku. U suprotnom, ukoliko je i ova kopija pogrešna, isti postupak se ponavlja i za naredne kopije. Ako je i poslednja, m-ta kopija neispravna, aktivira se korekcioni mehanizam baziran na kombinovanju okvira i majoritetnom odluĉivanju. Ukoliko je korekcija grešaka uspešna, predajniku se šalje pozitivna potvrda prijema. MeĊutim, ukoliko se bar na jednoj bitskoj poziciji pojavilo više od  2m / grešaka, korekcioni mehanizam postaje neefikasan, prenos se proglašava neuspešnim i predajniku se šalje negativna potvrda prijema (NAK). Procedura se dalje nastavlja odbacivanjem prethodnih m kopija okvira i prijemom novih, sledeći opisane korake. Ovaj scenario je oznaĉen sa B1 i njegov vremenski dijagram za m = 3 kopije je prikazan na slici 3.2. S C M C /S C S C M C /S C S C M C /S C S C M C /S C S C M C /S C S C M C /S C Vremenski slot 1 Vremenski slot 2 Vremenski slot 3 Vremenski slot 4 Vremenski slot 5 Vremenski slot 6 Kopija_1 Kopija_2 Kopija_3 Kopija_1 Kopija_2 Kopija_3 Kopija_1 Kopija_2 Kopija_3 Kopija_1 Kopija_2 Kopija_3 Kopija_1 Kopija_2 Kopija_3 Kopija_1 Kopija_2 Kopija_3 Slika 3.2. Vremenski dijagram za scenario B1 (m = 3) 47 Scenario B2: Ovaj scenario se odvija na sledeći naĉin, najpre se emituje prva kopija okvira, F1 koja se smešta u registar R1. Ukoliko je primljena bez detektovane greške, prenos se proglašava uspešnim i predajniku se šalje pozitivna potvrda prijema (ACK), a odgovarajući paket IR se isporuĉuje korisniku. U suprotnom, ukoliko je okvir pogrešan, predajniku se šalje negativna potvrda prijema (NAK) i predajnik šalje novu kopiju okvira F2 koja se smešta u registar R2. Ukoliko je ova kopija ispravna, prenos se proglašava uspešnim, predajniku se šalje pozitivna potvrda prijema i odgovarajući paket se prosleĊuje korisniku. Postupak je potpuno isti i u sluĉaju narednih kopija. Ako je i poslednja, m-ta kopija pogrešna, aktivira se korekcioni mehanizam baziran na kombinovanju paketa i majoritetnom odluĉivanju. Ukoliko je korekcija grešaka uspešna, predajniku se šalje pozitivna potvrda prijema. MeĊutim, ukoliko se bar na jednoj bitskoj poziciji pojavilo više od  2m / grešaka, korekcioni mehanizam postaje neefikasan, prenos se proglašava neuspešnim i predajniku se šalje negativna potvrda prijema. Procedura se dalje nastavlja odbacivanjem prethodnih m kopija okvira i prijemom novih, sledeći opisane korake. Ovaj scenario je oznaĉen sa B2 i njegov vremenski vremenski dijagram za m = 3 kopije je prikazan na slici 3.3. M C /S C S C S C S C M C /S C S C S C S C Vremenski slot 1 Vremenski slot 2 Vremenski slot 3 Vremenski slot 4 Vremenski slot 5 Vremenski slot 6 Kopija_1 Kopija_2 Kopija_3 Kopija_1 Kopija_2 Kopija_3 Slika 3.3. Vremenski dijagram za scenario B2 (m = 3) Scenario B3: Treći scenario je gotovo identiĉan prethodnom. Jedina razlika je u tome što se nakon m pogrešnih kopija okvira i neuspešne primene korekcionog mehanizma, cikliĉno odbacuje po jedna kopija, a preostalih m-1-na kopija se kombinuju sa novom, ukoliko je i ona pogrešna. Drugim reĉima, korekcioni mehanizam baziran na kombinovanju paketa i majoritetnom odluĉivanju se primenjuje nakon svake pogrešne emisije, odnosno prijema pogrešne kopije okvira. Ovaj scenario je oznaĉen sa B3 i njegov vremenski dijagram za m = 3 kopije je prikazan na slici 3.4. M C /S C S C S C S C M C /S C S C S C S C M C /S C M C /S C Vremenski slot 1 Vremenski slot 2 Vremenski slot 3 Vremenski slot 4 Vremenski slot 5 Vremenski slot 6 Kopija_1 Kopija_2 Kopija_3 Kopija_1 Kopija_2 Kopija_3 Slika 3.4. Vremenski dijagram za B3 scenario (m = 3) 48 3.2. Analiza scenarija B1 U ovom potpoglavlju će biti dat opis procedure, matematiĉki model, simulacioni model i rezultati analize scenarija B1 za tri kopije okvira. Pored toga, biće izveden i izraz za propusnost u sluĉaju proizvoljnog broja kopija. 3.2.1. Opis procedure Dijagram toka aktivnosti scenarija B1 za tri kopije okvira je prikazan na slici 3.5. Sa i je oznaĉena pozicija bita u okviru, a sa k, redni broj kopije. Sa N je oznaĉeno normalizovano kruţno kašnjenje. Normalizacija je izvršena u odnosu na duţinu trajanja okvira Tf. Blokovi koji se ponavljaju su obeleţeni slovom A. U svakom bloku se istovremeno vrši prijem i memorisanje tri kopije okvira, provera njihove ispravnosti i korekcija grešaka bazirana na majoritetnom odluĉivanju. Najpre se ispituje prva kopija. Ukoliko je ispravna, predajniku se šalje pozitivna potvrda prijema (ACK) i sa normalizovanim kašnjenjem delay = 1 prelazi na obradu sledećeg okvira. U suprotnom, ukoliko je prva kopija pogrešna, bez slanja negativne potvrde prijema, sa kašnjenjem delay = 0 se ispituje druga kopija. Ukoliko je ispravna, predajniku se šalje pozitivna potvrda prijema i sa normalizovanim kašnjenjem delay = 1 prelazi na obradu sledećeg okvira. U suprotnom, ukoliko je druga kopija pogrešna, takoĊe bez slanja negativne potvrde prijema, sa kašnjenjem delay = 0 ispituje se treća kopija. Ukoliko je ispravna, predajniku se šalje pozitivna potvrda prijema i sa normalizovanim kašnjenjem delay = 1 prelazi na obradu sledećeg okvira. U suprotnom, ukoliko je i treća kopija pogrešna, takoĊe bez slanja negativne potvrde prijema, sa kašnjenjem delay = 0 vrši se korekcija grešaka bazirana na majoritetnom odluĉivanju. Ukoliko na svakoj bitskoj poziciji postoji najviše jedna greška, prenos se proglašava ispravnim, predajniku se šalje pozitivna potvrda prijema i sa normalizovanim kašnjenjem delay = 1 prelazi na obradu sledećeg okvira. U suprotnom, ukoliko se na bar jednoj bitskoj poziciji nalazi dvostruka ili trostruka greška, prenos se proglašava neuspešnim, predajniku se šalje negativna potvrda prijema (NAK) i sa kašnjenjem delay = N prima novi blok od tri kopije okvira. Procedura se dalje nastavlja sve dok se ne primi ispravna kopija okvira. 49 start k=0, i=0 k=k+1 Block A L0 da ne da ne da ne da ne i=1:n correct *copy Ck is ML[R0(i),R1(i), R2(i)] delay=N NAK ,,, Ck correct copy is store copy in register R2 ,,, Ck correct copy is ”Ck correct copy is ’Ck H1 Block A delay=N NAK H2 Block A stop ACKdelay=1 NAKdelay=N store copy in register R0’Ck store copy in register R1”Ck Slika 3.5. Dijagram toka aktivnosti scenarija B1 (m = 3) 3.2.2. Matematički model Na slici 3.6. je prikazan dijagram stanja scenarija B1 koji odgovara radu prijemnika sa majoritetnim kombinovanjem paketa prikazanog na slici 3.5. Dijagram se sastoji od dve grupe stanja oznaĉenih sa L i H. Retransmisioni ciklus zapoĉinje iz inicijalnog stanja L0 emitovanjem prve kopije okvira, a završava se posle uspešnog prenosa u krajnjem inicijalnom stanju, koje predstavlja poĉetno inicijalno stanje za sledeći retransmisioni ciklus [38] – [40]. Drugu grupu ĉine tranzijentna stanja u koja sistem dolazi nakon neuspelog prenosa i ova stanja su oznaĉena sa H1, H2, itd.. 50 Prelazima izmeĊu stanja dodeljena su dva parametra, prvi koji oznaĉava verovatnoću prelaza, i drugi, normalizovano trajanje prelaza. Normalizacija je izvršena u odnosu na trajanje okvira Tf. Prelazi koji završavaju u inicijalnom stanju L0, opisani su parovima ]1;1[ fp , ili ]1;1[ mp , itd, a prelazi koji vode u tranzijentna stanja, sa ]0;[ fp ili ];[ Npm , uz pretpostavku da je vreme obrade zanemarljivo u odnosu na duţinu trajanja okvira. Sa fp je oznaĉena verovatnoća pogrešnog prenosa jedne kopije okvira, a sa mp verovatnoća pogrešnog prenosa tri kopije okvira umanjena za vrednost korekcionog faktora. [pf;0] [pf;0] [pm;N] 0L 0L 0L [1 -p f;1 ] [pf;0] 0L [1 -p h ;1 ] 0L [1 -p f;1 ] [1 -p f;1 ] H1 1H ’ 1H ” L0 0 L ’ 0L ” 0L [1 -p f;1 ] 1H ,,, 0L ,,, [pf;0] [pm;N] [1 -p f;1 ] [pf;0] 0L [1 -p f;1 ] 0L H2 2H ’ 2H ” 0L [1 -p m ;1 ] [pf;0] [pm;N] ~ ~ 0L [1 -p m ;1 ] [pf;0] [1 -p f;1 ] 0L ,,,, 0L [1 -p m ;1 ] 1H ,,,, 0L [1 -p f;1 ] [pf;0] 2H ,,, [pf;0] 2H ,,,, Sl. 3.6. Dijagram stanja scenarija B1 Na istoj slici su isprekidanom linijom obeleţena stanja koja se mogu zameniti samo jednim stanjem, vodeći raĉuna da vreme prelaza bude jednako. Tako su stanja '0L , '' 0L , ''' 0L i '''' 0L zamenjena stanjem 0L , stanja ' 1H , '' 1H , ''' 1H i '''' 1H zamenjena stanjem 1H , a stanja ' 2H , '' 2H , ''' 2H i '''' 2H , stanjem 2H , i tako redom. Komprimovani dijagram stanja je prikazan na slici 3.7., pri ĉemu je mfM ppp  3 . [pM;N] [pM;N] 0L 0L 0L 1H ~~ [1 -p M ;1 ] 2H 0L [pM;N] [1 -p M ;1 ] [1 -p M ;1 ] Sl. 3.7. Komprimovani dijagram stanja scenarija B1 Analitiĉki izraz za propusnost: Na slici 3.7. se uoĉavaju retransmisione putanje L0L0 i L0H1...H1L0 koje su date na slici 3.8: [pM;N] 0L [1 -p M ;1 ] 0L [1 -p M ;1 ] 0L [pM;N] 1H Sl. 3.8. Retransmisioni ciklusi scenarija B1 51 Izraz za srednje vreme trajanja retransmisionih ciklusa glasi:   f f k M k M TSNS TppNkT               21 0 )1()1( , (3.2.1) pri ĉemu su sa S1 i S2 oznaĉene sume: (i) 1)1( 0 1    k k MM ppS , (3.2.2) (ii) M M k k MM p p pkpS      1 )1( 0 2 . (3.2.3) Sumiranjem izraza (3.2.1) i smenom mfM ppp  3 , izraz za srednje vreme trajanja svih retransmisionih ciklusa postaje: f mf mf T pp pp NT             3 3 1 1 . (3.2.4) Izraz za propusnost scenarija B1 sada glasi: 1 3 3 1 1 1             mf mff B pp pp N T T S . (3.2.5) Na bazi prethodne analize, moguće je odrediti i propusnost scenarija B1 za proizvoljan broj kopija m. U tom sluĉaju, izraz za srednje vreme trajanja retransmisionih ciklusa glasi: 1 1 1 1             m m f m m ff B pp pp N T T S . (3.2.6) Raĉunanje prelaznih verovatnoća: Pri definisanju dijagrama stanja koji je dat na slici 3.6, pretpostavljeno je da se prenos okvira ostvaruje preko tri kanala i da se kanalne verovatnoće ne menjaju za vreme trajanja retransmisionog ciklusa. Uvaţavajući ove pretpostavke, sada ćemo odrediti verovatnoće pf i pm koje su neophodne za raĉunanje propusnosti. a) Verovatnoća pf: Ako sa p oznaĉimo kanalnu verovatnoću (verovatnoću greške po bitu), a sa n broj bita u okviru, verovatnoća pogrešnog prenosa okvira je data izrazom: nf qp 1 , (3.2.7) gde pq 1 predstavlja verovatnoću ispravnog prenosa bita. 52 b) Verovatnoća pm: Verovatnoću pm moţemo predstaviti kao koliĉnik )( )( '''' 0 ' 1 LP HP pm  . (3.2.8) pri ĉemu )( '1HP i )( '''' 0LP oznaĉavaju verovatnoće stanja ' 1H i '''' 0L (vidi sliku 3.6). Verovatnoća )( ''''0LP predstavlja verovatnoću dogaĊaja da prva, druga i treća kopija budu pogrešne, tako da je: )()( '''' 0SC0 LPPLP  , (3.2.9) gde je 3fSC pP  , verovatnoća neuspeha SC procedure, a 1LP 0 )( , verovatnoća inicijalnog stanja. Stanje '1H je posledica neuspešne korekcije greške bazirane na primeni SC+MC procedure. Saglasno tome vredi )()( 0 ' 1 LPPHP MCSC   . (3.2.10) Imajući u vidu izraz (2.2.5a) za PSC+MC u sluĉaju tri kopijskog prenosa (m = 3), kombinovanjem izraza (3.2.7) – (3.2.10), izraz za pm postaje: 3 2 )1( ])1(1[3)21(1 n nnnnn SC MCSC m q pqqpq P P p      , (3.2.11) U opštem sluĉaju za proizvoljan broj kopija m (videti izraz (2.2.5b)), gde je m neparan broj, izraz za verovatnoću retransmisije pm glasi:    mn m i n jim m j jini SC MCSC m q qp j im q i m P P p )1( 1)1( 2 0 2 0                                          . (3.2.12) 3.2.3. Simulacioni model Procena propusnosti se moţe izvršiti simulacijom modela prikazanog na slici 3.9 uz pomoć raĉunara. Za potrebe simulacione analize, formiran je programski paket za koji su karakteristiĉni sledeći koraci:  uĉitavanje ulaznih parametara: p, n, nf; N ;  generisanje sekvenci sa greškama [e0], [e1] i [e2];  simulacija rada prijemnika;  procena propusnosti. 53 [pf;0] [pf;0] [1-pf;1] [1-pf;1] [1-pf;1] [1-pm;1] [pf;0] [1-pf;1] [pf;0] 0L ” 0L ,,, [pm;N] 0L ,,,, 1H ’0L ’ Sl. 3.9. Model za procenu propusnosti scenarija B1 Pri analizi propusnosti predloţenog modela, usvajaju se uobiĉajena pojednostavljenja. Smatra se da predajnik emituje “prazne” okvire (sve nule), da prijemnik detektuje sve emitovane okvire, da su svi zaštitni biti preneti ispravno, da su svi okviri iste duţine, da su greške u kanalu nezavisne i uniformno raspodeljene, da dodatna logika u prijemniku moţe da koriguje sve jednostruke greške, da je zanemarljivo vreme obrade grešaka u prijemnoj stanici u odnosu na trajanje okvira i da je prenos potvrde o uspešnoj ili neuspešnoj potvrdi prijema okvira idealan. Tok simulacije je prikazan na slici 3.10 i sastoji se iz tri faze: ulaz: n: dužina okvira nf : broj simulacionih slotova N: normalizovano kružno kašnjenje p: verovatnoća greške po bitu 1. faza: generisanje vektora greške [e0, e1, e2] = call pn_gen (p, n, nf ) 2. faza: scenario B1 [br_ack, br_mak]=call B1 (n, nf , N, e0, e1, e2) grafiĉki prikaz rezultata 3. faza: raĉunanje propusnosti SB1 = (br_ack + br_mak)/nf Slika 3.10. Dijagram toka simulacionog postupka za scenario B1 U prvoj fazi simulacionog postupka se pozivom funkcijskog potprograma pn_gen iz MATLAB biblioteke generišu tri nezavisne sekvence grešaka [e0], [e1] i [e2] verovatnoće p i duţine nf x n bita, gde nf oznaĉava ukupan broj simulacionih slotova, a n duţinu okvira u bitima. 54 U drugoj fazi se vrši simulacija rada prijemnika [41]. Dijagram toka ove faze je prikazan na slici 3.11. Algoritam se sastoji u prebrojavanju grešaka (“jedinica”) unutar jedne kopije okvira. Ukoliko je broj grešaka jednak nuli, smatra se da je prenos uspešan. Sadrţaj brojaĉa pozitivnih potvrda br_ack se uvećava za jedan i prelazi se na prvu kopiju narednog okvira. Ako su sve tri uzastopne kopije istog okvira pogrešne, pristupa se proceduri detekcije i korekcije greške. Ova procedura se sastoji u “sabiranju” binarnih elemenata koji se nalaze na istim bitskim pozicijama u kopijama okvira. Prenos se smatra uspešnim ukoliko je vrednost svakog “zbirnog” elementa manja ili jednaka jedan. Ukoliko zbirni okvir zadovoljava prethodni uslov, sadrţaj brojaĉa pozitivnih potvrda prijema br_mak koji su posledica delovanja majoritetne logike za korekciju greške se uvećava za jedan i prelazi se na obradu narednog okvira. U suprotnom, ukoliko je korigovani okvir neispravan, ignoriše se N narednih kopija, gde je sa N oznaĉeno normalizovano kruţno kašnjenje od predajne do prijemne stanice i nazad (round trip delay). Procedura se dalje nastavlja sve dok redni broj kopije ne preĊe zadati broj simulacionih slotova nf. U trećoj fazi se raĉuna propusnost. Propusnost 1BSˆ se procenjuje kao koliĉnik ukupnog broja pozitivnih potvrda (br_ack + br_mak) i ukupnog broja simulacionih slotova nf . Saglasno tome, izraz za propusnost glasi: ff B n makbr n ackbr S __ˆ 1  . (3.2.13) 55 inicijalizacija: k = 1 br_ack = 0 br_mak = 0 da 0)( 1   iR n i 0 fnk  ne start ulaz: n, nf , N, e0, e1, e2 da ne Rm(i)=0 Rm(i)=1 ml logika   inke0iR0  1)( nifor :1 0)( 1   iR n i 1 0)( 1   iR n i m ne k=k+N 1)( 0   iR 2 j j    inke1iR1  1)( nifor :1 ne 0)( 1   iR n i 2   inke2iR2  1)( nifor :1 ne nifor :1 return da ne fnk  0)( 1   iR n i 0 da ne br_ack=br_ack+1 k=k+1   inke0iR0  1)( nifor :1 dabr_mak=br_mak+1 k=k+1 dabr_ack=br_ack+1 k=k+1 dabr_ack=br_ack+1 k=k+1 return ne dabr_ack=br_ack+1 k=k+1 Slika 3.11. Dijagram toka za drugu fazu simulacionog postupka scenarija B1 56 3.2.4. Rezultati analize Na na slici 3.12 je prikazana propusnost scenarija B1 u funkciji ekvivalentne kanalne verovatnoće dobijena na osnovu izraza (3.2.5). Razmatran je sluĉaj u kome je duţina okvira iznosila n = 100 bita i normalizovano kašnjenje N = 4. Na istoj slici su prikazani i simulacioni rezultati za propusnost (markirani zvezdicom). Za verovatnoću greške po bitu izmeĊu 10-4 i 5x10-1, generisana je sekvenca greške duţine nf x n bita (nf = 3.000 simulacionih slotova, n = 100 bita). Slaganje analitiĉkih i simulacionih rezultata je oĉigledno. UporeĊenja radi, na slici je prikazana i propusnost SC procedure koja je dobijena kada se u izraz (3.2.5) stavi pm = 1. Za dati primer, sa slike se vidi znaĉajno povećanje propusnosti pri vrednostima p > 5x10-3. SSC+MC SSC Ekvivalentna kanalna verovatnoća P ro p u sn o st s ce n a ri ja B 1 teorija simulacija Slika 3.12. Propusnost scenarija B1 u funkciji ekvivalentne kanalne verovatnoće (m = 3, n = 100 i N = 4). 3.3. Analiza scenarija B2 Analizu scenarija B2 vršićemo po istoj metodologiji kao i u sluĉaju scenarija B1. Na bazi analize za tri kopije, dat je izraz za propusnost u sluĉaju proizvoljnog broja kopija. 3.3.1. Opis procedure Dijagram toka aktivnosti scenarija B2 za tri kopije okvira je prikazan na slici 3.13. Oznake su iste kao kod scenarija B1. Jedina razlika je u redosledu aktiviranja pojedinih blokova. U bloku A se vrši prijem, memorisanje i provera ispravnosti pojedinaĉnih kopija okvira, a u bloku B je implementiran korekcioni algoritam baziran na majoritetnom odluĉivanju. 57 stop ACKdelay=1 NAKdelay=N da ne delay=N NAK delay=0 i=1:n Block A Block B correct *copy Ck is delay=N NAK Block A ML[R0(i),R1(i), R2(i)] delay=N Block A NAK Block A NAKdelay=N delay=0 Block B Block A NAKdelay=N H1 ’H2 ”H2 H3 H4 ’H5 ”H5 start k=0, j=0 store copy Ck in register Rj k=k+1 Block A L0 da ne correct copy Ck is j=(j+1)mod 3 Slika 3.13. Dijagram toka scenarija B2 (m = 3) 58 3.3.2. Matematički model Na slici 3.14 je prikazan dijagram stanja scenarija B2 za tri kopije okvira. Saglasno oznakama na slici 3.13, retransmisioni ciklus zapoĉinje iz poĉetnog inicijalnog stanja L0 emitovanjem prve kopije okvira, a završava se posle uspešnog prenosa u krajnjem inicijalnom stanju. Kroz tranzijentna stanja, sistem prolazi nakon neuspelog prenosa okvira. U zavisnosti od broja retransmisija, ova stanja su oznaĉena sa H1, H2, H3, itd.. Prelazi koji završavaju u inicijalnom stanju L0, opisani su parovima ]1;1[ fp , odnosno, ]1;1[ mp , a prelazi koji vode u tranzijentna stanja, sa ];[ Np f ili ]0;[ fp , odnosno ];[ Npm . Sa fp je oznaĉena retransmisiona verovatnoća pogrešnog prenosa jedne kopije okvira, a sa mp , retransmisiona verovatnoća pogrešnog prenosa tri kopije okvira umanjena za vrednost korekcionog faktora. Vrednosti normalizovanog trajanja prelaza su jednake odgovarajućim vrednostima kašnjenja na slici 3.13. [pf;N] [pf;0] [pm;N] 0L 0L 0L 0L 2H ’ 2H ” [1 -p f;1 ] [pf;0] 0L [1 -p m ;1 ] 5H ’ 5H ” 0L [1 -p m ;1 ] [1 -p f;1 ] [1 -p f;1 ] H2 H5 ~~ [1 -p f;1 ] 3H 0L [pf;N] [1 -p f;1 ] 1H 0L [pf;N] [1 -p f;1 ] 4H 0L [pf;N] Slika 3.14. Dijagram stanja scenarija B2 (m = 3) Na istoj slici su isprekidanom linijom obeleţena stanja koja se mogu zameniti samo jednim stanjem, vodeći raĉuna da trajanje prelaza bude jednako. Tako su stanja '2H i '' 2H zamenjena stanjem 2H , a stanja '5H i '' 5H , stanjem 5H , i tako redom. Komprimovani dijagram stanja je prikazan na slici 3.15, pri ĉemu je mfM ppp  . [pf;N] 0L 0L [1 -p f;1 ] ~~ [1 -p f;1 ] 1H 0L [pf;N] [pM;N] 0L 2H [1 -p M ;1 ] [pf;N] 0L [1 -p f;1 ] [1 -p f;1 ] 4H 0L [pf;N] [pM;N] 0L 5H [1 -p M ;1 ] 3H Slika. 3.15. Komprimovani dijagram stanja scenarija B2 (m = 3) 59 Analitiĉki izraz za propusnost: U postupku odreĊivanja vrednosti trajanja retransmisionih ciklusa, pogodno je da dijagram stanja prikazan na slici 3.15 dekomponujemo u tri celine prikazane na slici 3.16. Svaku od ovih celina karakterišu specifiĉne retransmisione putanje. [pf;N] 0L ~~ 1H [pf;N] [pM;N] 2H [pf;N] 4H [pf;N] [pM;N] 5H3H 0L [1 -p f;1 ] [1 -p f;1 ] 0L a) 0L [1 -p f;1 ] [1 -p f;1 ] 0L [pf;N] 0L ~~ 1H [pf;N] [pM;N] 2H [pf;N] 4H [pf;N] [pM;N] 5H3H b) 0L [1 -p M ;1 ] 0L [1 -p M ;1 ] [pf;N] 0L ~~ 1H [pf;N] [pM;N] 2H [pf;N] 4H [pf;N] [pM;N] 5H3H c) Sl. 3.16. Retransmisioni ciklusi scenarija B2 U nastavku, za svaku od retransmisionih putanja biće odreĊeno srednje vreme trajanja odgovarajućih retransmisionih ciklusa jT ( j = 1, 2, 3). a) retransmisione putanje: L0L0, L0H1H2H3L0, ...   fff f k f k Mff TSpNSp TppppNkT               21 0 1 )1(3)1( )1()()13( , (3.3.1) b) retransmisione putanje: L0H1L0, L0H1H2H3H4L0, ...   fffff f k f k fMff TSppNSppN TpppppNkNT               21 0 2 )1(3)1()1( )1()()13( , (3.3.2) 60 c) retransmisione putanje: L0H1H2L0, L0H1H2H3H4 H5L0 , ...   fMfMf f k M k ffMff TSppNSppN TppppppNkNT               2 2 1 2 0 3 )1(3)1()12( )1()()132( , (3.2.3) pri ĉemu su sa S1 i S2 oznaĉene sume: (i) Mfk k Mf pp ppS     2 0 2 1 1 1 )( ; (3.3.4) (ii) 22 2 0 2 2 )1( )( Mf Mf k k Mf pp pp ppkS      (3.3.5) Sumiranjem izraza (3.3.1), (3.3.2) i (3.3.3), i smenom mfM ppp  , izraz za ukupno srednje vreme trajanja svih retransmisionih ciklusa postaje: f mm mff ll f mf T S ppp S p pp TTTT                )1 1 1 322 33 21 , (3.3.6) gde su 1 1 1            f f ll p p NS i 1 1 1             mf mf mm pp pp NS . Izraz za propusnost scenarija B2 sada glasi: 1 322 32 )1 1 1                        mm mff ll f mf f B S ppp S p ppT T S . (3.3.7) Na bazi prethodne analize, moguće je odrediti i propusnost scenarija B2 za proizvoljan broj kopija m. Izraz za srednje vreme trajanja pojedinih retransmisionih ciklusa se moţe napisati kao:                      mjTpppppNmkNm mjTppppNmkNj T k fmf k m m f m f k ff k m m f j f j ;)1()(1)1( 1,...,2,1;)1()(1)1( 0 1 0 1 , (3.3.8) odnosno,             mjTSpppNmTSpppNm mjTSppNmTSppNj T fmf m ffmf m f ff j fff j f j ;)1()1(1)1( 1,...,2,1;)1()1(1)1( 4 1 3 1 4 1 3 1 , (3.3.9) pri ĉemu su sa S3 i S4 oznaĉene sume: 61 (i) m m fk k m m f pp ppS     1 1 )( 0 3 ; (3.3.10) (ii) 2 0 4 )1( )( m m f m m f k k m m f pp pp ppkS      (3.3.11) Ukupno srednje vreme se dobija sumiranjem srednjih vremena trajanja pojedinih retransmisionih ciklusa jT ):1( mj  . Prema tome, izraz za propusnost scenarija B2 sada glasi:    m j j ff B T T T T S 1 2 . (3.3.12) Raĉunanje prelaznih verovatnoća: U sluĉaju scenarija B2, prelazne verovatnoće pf i pm su identiĉne odgovarajućim verovatnoćama koje su dobijene prilikom razmatranja scenarija B1, tako da se pf raĉuna prema izrazu (3.2.7), a pm, prema izrazu (3.2.12). 3.3.3. Simulacioni model Procena propusnosti se moţe izvršiti simulacijom modela prikazanog na slici 3.17. Za potrebe simulacione analize, formiran je programski paket za koji su karakteristiĉni sledeći koraci:  uĉitavanje ulaznih parametara: p, n, nf, N;  generisanje sekvence sa greškama [e];  simulacija rada prijemnika;  procena propusnosti. [pf;N] [1-pf;1] [1-pf;1] [1-pm;1] [1-pf;1] [pm;N] 0L [1-pf;1] [pf;0][pf;N] [pf;N] 2H ”2H ’1H 3H Sl. 3.17. Model za procenu propusnosti scenarija B2 Tok simulacionog postupka je identiĉan toku prikazanom na slici 3.10 sa razlikom što je u drugoj fazi aktivirana procedura prikazana na slici 3.18. 62 inicijalizacija: k = 1 br_ack = 0 br_mak = 0 da 0)( 1   iR n i 0 fnk  ne start ulaz: n, nf , N, e da ne Rm(i)=0 Rm(i)=1 ml logika   inkeiR0  1)( nifor :1 0)( 1   iR n i 1 0)( 1   iR n i m ne k=k+N 1)( 0   iR 2 j j    inkeiR1  1)( nifor :1 ne da k=k+N da fnk  0)( 1   iR n i 2   inkeiR2  1)( nifor :1 ne k=k+N da fnk  dabr_ack=br_ack+1 k=k+1 nifor :1 da 0)( 1   iR n i 0 fnk  ne   inkeiR0  1)( nifor :1 k=k+N br_mak=br_mak+1 k=k+1 dabr_ack=br_ack+1 k=k+1 return ne return ne return ne dabr_ack=br_ack+1 k=k+1 return ne dabr_ack=br_ack+1 k=k+1 Slika 3.18. Dijagram toka za drugu fazu simulacionog postupka scenarija B2 63 3.3.4. Rezultati analize Na slici 3.19 je prikazana propusnost scenarija B2 u funkciji ekvivalentne kanalne verovatnoće dobijena na osnovu izraza (3.3.7). Razmatran je sluĉaj u kome je duţina okvira iznosila n = 100 bita, a normalizovano kruţno kašnjenje N = 4. Na istoj slici su prikazani i simulacioni rezultati za propusnost (markirani zvezdicom). Za verovatnoću greške po bitu izmeĊu 10-4 i 5x10-1, generisana je sekvenca greške duţine nf x n bita (nf = 3.000 simulacionih slotova, n = 100 bita). Slaganje analitiĉkih i simulacionih rezultata je oĉigledno. UporeĊenja radi, na slici su prikazane propusnosti u sluĉaju kada je pri istim uslovima primenjena samo SC ili samo MC procedura. Rezultati su dobijeni tako što su u izrazu (3.3.7) zamenjeni 1mp za SC proceduru, odnosno 1fp i nm pqqp )3(1 23  za MC proceduru. Vidi se da je pri malim kanalnim verovatnoćama SC+MC procedura bliska SC proceduri, a pri velikim verovatnoćama, MC proceduri. Kao što smo i oĉekivali, ukupni rezultat je bolji od rezultata pojedinaĉnih procedura. SMC SSC+MC SSC teorija simulacija Ekvivalentna kanalna verovatnoća P ro p u sn o st s ce n a ri ja B 2 Slika 3.19. Propusnost scenarija B2 u funkciji ekvivalentne kanalne verovatnoće (m = 3, n = 100 i N = 4). 3.4. Analiza scenarija B3 Za razliku od scenarija B1 i B2 u kojima se majoritetno odluĉivanje vrši nad zasebnim grupama pogrešno prenetih okvira, kod scenarija B3, majoritetno odluĉivanje se odvija nad tekućom kopijom i (m–1)–nom kopijom iz prethodne generacije (seta). Iz tog razloga, postoji meĊuzavisnost izmeĊu genercija kada je u pitanju primena majoritetnog odluĉivanja što se posebno manifestuje na sloţenost odreĊivanja retransmisionih verovatnoća. Saglasno tome, ovom problemu će biti posvećena posebna paţnja. 3.4.1. Opis procedure Dijagram toka aktivnosti scenarija B3 za tri kopije okvira je prikazan na slici 3.20. Kao i u sluĉaju scenarija B2, postoje dva tipa blokova koji se aktiviraju u izmenjenom redosledu u odnosu na scenario B2, kao i razlike u kašnjenjima prilikom aktiviranja pojedinih blokova tipa A. 64 stop ACKdelay=1 NAKdelay=N start k=0, j=0 da ne delay=N NAK store copy Ck in register Rj k=k+1 delay=0 i=1:n Block A Block A Block B L0 correct *copy Ck is delay=N NAK Block A ML[R0(i),R1(i), R2(i)] delay=N Block A NAK Block B delay=0 Block B Block A NAKdelay=N delay=0 H1 ’H2 ”H2 ”H4 ”H3 ’H3 ’H4 da ne correct copy Ck is j=(j+1)mod 3 Sl. 3.20. Dijagram toka scenarija B3 65 3.4.2. Matematički model Na slici 3.21 je prikazan dijagram stanja scenarija B3 koji odgovara radu prijemnika sa majoritetnim kombinovanjem paketa prikazanog na slici 3.20. Dijagram se sastoji od dve grupe stanja oznaĉenih sa L i H. U inicijalno stanje L0 sistem dolazi posle uspešnog prenosa, odnosno prijema pozitivne potvrde. Drugu grupu ĉine tranzijentna stanja u koja sistem dolazi nakon neuspelog prenosa i ova stanja su oznaĉena sa H1, H2, H3, H4, itd.. Prelazi koji završavaju u inicijalnom stanju L0, opisani su parovima ]1;1[ fp , ili ]1;1[ mp , ]1;1[ hp , ]1;1[ up , itd, a prelazi koji vode u tranzijentna stanje, sa ];[ Np f ili ]0;[ fp , ];[ Npm , ];[ Nph , ];[ Npu , itd., uz pretpostavku da je vreme obrade zanemarljivo u odnosu na duţinu trajanja okvira. Sa fp je oznaĉena verovatnoća pogrešnog prenosa jedne kopije okvira, a sa mp , hp , up , ..., verovatnoće pogrešnog prenosa tri kopije okvira umanjene za vrednost korekcionog faktora. [pf;N] [pf;0] [pm;N] 0L 0L 0L 0L 2H ’ 2H ” [1 -p m ;1 ] [1 -p f;1 ] [1 -p f;1 ] H2 ~~ [1 -p f;1 ] 1H 0L [pf;N] [pf;0] 0L 0L 3H ’ 3H ” [1 -p h ;1 ] [1 -p f;1 ] H3 [pf;0] 0L 0L 4H ’ 4H ” [1 -p u ;1 ] [1 -p f;1 ] H4 [ph;N] [pu;N] Sl. 3.21. Dijagram stanja scenarija B3 Na istoj slici su isprekidanom linijom obeleţena stanja koja se mogu zameniti samo jednim stanjem, vodeći raĉuna da trajanje prelaza bude jednako. Tako su stanja '2H i '' 2H , zamenjena stanjem 2H , a stanja ' 3H i '' 3H , stanjem 3H , i tako redom. Komprimovani dijagram stanja je prikazan na slici 3.22, pri ĉemu su sa mfM ppp  , hfH ppp  ,…, prikazane ekvivalentne verovatnoće pogrešnog prenosa nastale spajanjem pomenutih stanja. U analizi koja sledi, zbog sliĉnosti scenarija, pretpostavićemo da je verovatnoća pu, i sve naredne koje su posledica ponavljanja dogaĊaja, jednake verovatnoći ph. [pf;N] 0L 0L [1 -p f;1 ] ~~ [1 -p f;1 ] 1H 0L [pf;N] [pM;N] 0L 2H [1 -p M ;1 ] [pH;N] 0L 3H 0L 4H [1 -p U ;1 ] [1 -p H ;1 ] [pH;N] Sl. 3.22. Komprimovani dijagram stanja scenarija B3 66 Analitiĉki izraz za propusnost: U postupku odreĊivanja vrednosti trajanja retransmisionih ciklusa pogodno je da dijagram stanja prikazan na slici 3.22 dekomponujemo u tri celine prikazane na slici 3.23. Svaka od ovih celina karakteriše specifiĉne retransmisione putanje. 0L [1 -p f;1 ] [pf;N] 0L 1H 0L [1 -p f;1 ] [pf;N] [pf;N] 0L 1H 2H [1 -p M ;1 ] 0L [pf;N] [pf;N] 0L 1H 2H [pM;N] [1 -p H ;1 ] 0L [pH;N] 3H a) b) c) Sl. 3.23. Retransmisioni ciklusi scenarija B3 U nastavku, za svaku od retransmisionih putanja biće odreĊeno srednje vreme trajanja odgovarajućih retransmisionih ciklusa jT ( j = 1, 2, 3). a) retransmisione putanje: L0L0 i L0H1L0 )1()1(1 )1()1( 1 0 1 fff ff i i f ppNp TppNiT              . (3.4.1) b) retransmisione putanje: L0H1H2L0 fMf TppNT  )]1()12[( 2 2 . (3.4.2) c) retransmisione putanje: L0H1H2H3 ... H3L0 f H H MfMf f k k HHMf k k HHMf f k H k HMff T p p ppNppN TpkpppNppppN TpppppNkNT                                     1 )13( )1()1()13( )1()13( 22 0 2 0 2 0 3 . (3.4.3) Sumiranjem izraza (3.4.1), (3.4.2) i (3.4.3), i smenom mfM ppp  i hfh ppp  , izraz za ukupno srednje vreme trajanja svih retransmisionih ciklusa postaje: f hh mf mm mff ll f T S pp S ppp S p TTTT                3322 321 1 , (3.4.4) 67 gde su 1 1 1            f f ll p p NS , 1 1 1             mf mf mm pp pp NS i 1 1 1             hf hf hh pp pp NS . Izraz za propusnost scenarija B3 sada glasi: 1 3322 3 1                hh mf mm mff ll ff B S pp S ppp S p T T S . (3.4.5) Raĉunanje prelaznih verovatnoća: Pri definisanju dijagrama stanja koji je dat na slici 3.22, pretpostavljeno je da se prenos okvira vrši preko jednog kanala i da se kanalne verovatnoće ne menjaju za vreme trajanja retransmisionog ciklusa. Prema tome, verovatnoće pf i pm su iste kao kod scenarija B1, (videti sekciju 3.2.2) i iznose: nf qp 1 , (3.4.6) i    mn m i n jim m j jini SC MCSC m q qp j im q i m P P p )1( 1)1( 2 0 2 0                                          . (3.4.7) Kao što smo rekli na poĉetku sekcije, posebna paţnja biće posvećena raĉunanju verovatnoće ph. Imajući u vidu dijagram na slici 3.23, verovatnoća ph predstavlja koliĉnik verovatnoća stanja ' 4H i '' 3H , tj.: )( )( '' 3 ' 4 HP HP ph  . (3.4.8) Sa )( ''3HP je oznaĉena verovatnoća dogaĊaja da prva, druga, treća i ĉetvrta kopija okvira budu pogrešne i da na prve tri kopije postoji bar jedna bitska pozicija sa dvostrukom ili trostrukom greškom. Ova verovatnoća se moţe napisati u obliku proizvoda: )()( '3 '' 3 HPpHP f  . (3.4.9) Kako je )()( ' 0MCSC3 LPPHP   , gde je 1)( 0 LP verovatnoća inicijalnog stanja, u sluĉaju m = 3 (videti (2.2.5), izraz za )( ''3HP postaje:  ])1(1[3)21(1)1()( 2''3 nnnnnn pqqpqqHP   . (3.4.10) Verovatnoća )( '4HP je posledica neuspešne korekcije greške bazirane na majoritetnom kombinovanju prve tri, odnosno druge tri kopije okvira. Drugim reĉima, prenos je pogrešan, ako su sve kopije pogrešne, i ako na prvoj, drugoj i trećoj kopiji, i na drugoj, trećoj i ĉetvrtoj kopiji okvira, istovremeno postoji bar po jedna bitska pozicija sa dvostrukom ili trostrukom greškom. 68 OdreĊivanje verovatnoće )( '4HP je sloţeno. Zbog preglednosti, izvoĊenje izraza je dato u prilogu B, na kraju teze. Imajući u vidu izraze za )( '4HP i )( '' 3HP , izraz za verovatnoću hp postaje:  ])1(1[3)21(1)1( )1(])1(2)1(6)21()21(21[41 2 32 nnnnnn nnnnnnnn h pqqpqq pqpqppqpqq p      . (3.4.11) 3.4.3. Simulacioni model Procena propusnosti se moţe izvršiti simulacijom modela prikazanog na slici 3.24 uz pomoć raĉunara. Za potrebe simulacione analize, formiran je programski paket za koji su karakteristiĉni sledeći koraci:  uĉitavanje ulaznih parametara: p, n, nf; N;  generisanje sekvence sa greškama [e];  simulacija rada prijemnika;  procena propusnosti. [pf;N] [pf;0] [1-pf;1] [1-pf;1] [1-pf;1] [1-pm;1] [pf;N] [ph;N] [1-pf;1] [pf;0] [1-ph;1] [pm;N] [pf;0] 3H ”3H ’ [ph;N] [1-pf;1] [1-ph;1] 2H ’ 2H ”0L 1H 4H ’ 4H ” [pf;0] 5H ’ 5H ” [ph;N] [1-pf;1] [1-ph;1] Sl. 3.24. Model za procenu propusnosti scenarija B3 Simulacija se vrši prema dijagramu na slici 3.10 pri ĉemu je faza 2 detaljno prikazana na slici 3.25. 69 return inicijalizacija: k = 1 br_ack = 0 br_mak = 0 da ne 0)( 1   iR n i 0 fnk  da ne br_ack=br_ack+1 k=k+1 start ulaz: n, nf , N, e da ne Rm(i)=0 Rm(i)=1 ml logika   inkeiR0  1)( nifor :1 0)( 1   iR n i 1 0)( 1   iR n i m da ne k=k+N 1)( 0   iR 2 j j    inkeiR1  1)( nifor :1 0)( 1   iR n i 1 da ne br_ack=br_ack+1 k=k+1   inkeiR1  1)( nifor :1 br_ack=br_ack+1 k=k+1 br_mak=br_mak+1 k=k+1 da ne A A return da ne fnk  0)( 1   iR n i m da ne br_mak=br_mak+1 k=k+1 k=k+N k=k+N return da ne fnk  0)( 1   iR n i 2   inkeiR2  1)( njfor :1 br_ack=br_ack+1 k=k+1 da ne k=k+N return da ne fnk  nifor :1 ml logika 0)( 1   iR n i 2 da ne br_ack=br_ack+1 k=k+1   inkeiR2  1)( nifor :1 return da ne fnk  0)( 1   iR n i m da ne br_mak=br_mak+1 k=k+1 k=k+N ml logika 0)( 1   iR n i 0 da ne br_ack=br_ack+1 k=k+1   inkeiR0  1)( nifor :1 return da ne fnk  0)( 1   iR n i m da ne br_mak=br_mak+1 k=k+1 k=k+N ml logika Slika 3.25. Dijagram toka za drugu fazu simulacionog postupka scenarija B3 70 3.4.4. Rezultati analize Na slici 3.26 je prikazana propusnost scenarija B3 koja je dobijena na osnovu izraza (3.4.5), u funkciji ekvivalentne kanalne verovatnoće. Razmatran je sluĉaj u kome je duţina okvira iznosila n = 100 bita, a normalizovano kruţno kašnjenje N = 4. Na istoj slici su prikazani i simulacioni rezultati za propusnost (markirani zvezdicom). Za verovatnoću greške po bitu izmeĊu 10-4 i 5x10-1, generisana je sekvenca greške duţine nf x n bita (nf = 3.000 simulacionih slotova, n = 100 bita). Slaganje analitiĉkih i simulacionih rezultata je oĉigledno. Ekvivalentna kanalna verovatnoća P ro p u sn o st B 3 s ce n a ri ja SSC teorija simulacija SSC+MC Sl. 3.26. Propusnost scenarija B3 u funkciji ekvivalentne kanalne verovatnoće (m = 3, n = 100 i N = 4). 3.5. Uporedna analiza U ovom potpoglavlju je data uporedna analiza scenarija B1, B2 i B3 i uticaj broja kanala, duţine okvira i kruţnog kašnjenja na propusnost. Scenario B1 se odnosio na “prostorni” diverziti, pri ĉemu u prijemnik istovremeno pristiţe set od m kopija istog okvira, a scenario B2, na “vremenski” diverziti, sa sekvencijalnim prijemom kopija. U oba sluĉaja, ukoliko su sve kopije pogrešne, aktivira se mehanizam za korekciju grešaka baziran na majoritetnoj logici. Ukoliko je i rezultujući okvir pogrešan, prenos se proglašava neuspešnim i predajniku se šalje negativna potvrda prijema. Scenario B3 se takoĊe odnosio na “vremenski” diverziti, sa sekvencijalnim prijemom kopija. Za razliku od scenarija B1 i B2 u kojima se majoritetno odluĉivanje vrši nad nezavisnim setom od m pogrešno primljenih kopija istog okvira, kod scenarija B3, majoritetno odluĉivanje se odvija nad tekućom kopijom i (m–1)–nom kopijom iz prethodnog seta. 71 Na slici 3.27 je prikazana propusnost scenarija B1, B2 i B3 u funkciji ekvivalentne kanalne verovatnoće. Kao što se oĉekivalo, najbolji rezultati se dobijaju za scenario B1, a najmanja propusnost se ostvaruje kod scenarija B2. TakoĊe je potvrĊeno da scenario B3 daje rezultate koji su izmeĊu rezultata za scenarija B1 i B2. Isto se oĉekuje i od drugih scenarija koji nisu razmatrani. Prema tome, scenariji B1 i B2 daju graniĉne vrednosti za propusnost, tako da ćemo u daljoj analizi razmatrati samo ove graniĉne sluĉajeve. Ekvivalentna kanalna verovatnoća P ro p u sn o st s ce n a ri ja B 1 , B 2 , B 3 B2 B1 B3 Slika 3.27. Propusnost scenarija B1, B2 i B3 u funkciji ekvivalentne kanalne verovatnoće (m = 3, n = 400, N = 4) 3.5.1. Analiza uticaja broja kanala Na slici 3.28 ilustrovan je uticaj broja kopija na propusnost ARQ šeme u sluĉaju scenarija B1 i B2. Kod scenarija B1, propusnost raste sa brojem kanala. U sluĉaju scenarija B2, sa povećanjem broja kanala, pri manjim kanalnim verovatnoćama propusnost opada, a pri većim verovatnoćama raste. Ovo je posledica ĉinjenice da pri malim kanalnim verovatnoćama dominira SC procedura, a pri većim, MC procedura koja je utoliko efikasnija ukoliko je broj kanala veći. Prema tome, gabaritna zona u kojoj se moţe oĉekivati realna vrednost propusnosti je šira kada je broj kanala veći. 72 P ro p u sn o st s ce n a ri ja B 1 i B 2 Ekvivalentna kanalna verovatnoća B1 B2 Slika 3.28. Propusnost scenarija B1 i B2 u funkciji ekvivalentne kanalne verovatnoće pri razliĉitom broju kopija (n = 400, N = 4, m = 3, 5 i 7) 3.5.2. Analiza uticaja dužine okvira Na slici 3.29 ilustrovan je uticaj duţine okvira na propusnost ARQ šeme u sluĉaju scenarija B1 i B2. Kod oba scenarija, propusnost opada sa porastom duţine okvira. Ovaj rezultat se moţe tumaĉiti ĉinjenicom da sa porastom duţine okvira pri istoj verovatnoći greške raste proseĉan broj grešaka po okviru, pa samim tim se smanjuje mogućnost korekcije grešaka. Sa povećanjem duţine okvira dolazi do pomeranja gabaritnih zona tako da je realno oĉekivati da će se sa kraćim okvirima postići veća propusnost. P ro p u sn o st sc en a ri ja B 1 i B 2 Ekvivalentna kanalna verovatnoća B1 B2 Slika 3.29. Propusnost scenarija B1 i B2 u funkciji ekvivalentne kanalne verovatnoće pri razliĉitim dužinama okvira (m = 3, N = 4, n = 10, 100 i 1000) 73 3.5.3. Analiza uticaja kružnog kašnjenja Na slici 3.30 ilustrovan je uticaj normalizovanog kruţnog kašnjenja na propusnost ARQ šeme u sluĉaju scenarija B1 i B2. Dobijeni rezultati su oĉekivani s obzirom da sa porastom kruţnog kašnjenja propusnost opada. Interesantno je da je opadanje znatno izraţenije kod scenarija B2 nego kod scenarija B1. Uticaj kruţnog kašnjenja na scenario B2 se akumulira pošto prati svaku pojedinaĉnu kopiju i povećava ukupno vreme retransmisije do trenutka delovanja MC procedure. P ro p u sn o st s ce n a ri ja B 1 i B 2 Ekvivalentna kanalna verovatnoća B2 B1 Slika 3.30. Propusnost scenarija B1 i B2 u funkciji ekvivalentne kanalne verovatnoće pri razliĉitim vrednostima kružnog kašnjenja (m = 3, n = 400, N = 1, 4 i 10) 74 4. ELEMENTI IMPLEMENTACIJE U ovom poglavlju će biti dat predlog konkretne realizacije jedne senzorske mreţe sa implementacijom majoritetnog kombinovanja u odredišnom ĉvoru. Rešenja sa majoritetnim logikom se ne mogu direktno primeniti u praksi jer zahtevaju izvesne modifikacije kako u samom standardu IEEE 802.15.4 koji reguliše razmenu podataka u beţiĉnim senzorskim mreţama, tako i na radio primopredajnicima koji se trenutno koriste. Primopredajnik treba da ima mogućnost da ne odbacuje pogrešne kopije okvira, već da ih zajedno sa sadrţajem CRC polja prosleĊuje procesoru, što je bitan preduslov za primenu majoritetnog kombinovanja paketa [48] – [50]. 4.1. Modifikacija IEEE 802.15.4 standarda Razmena podataka u beţiĉnim senzorskim mreţama malog protoka (Low Rate Wireless Personal Area Network, LR-WPAN) je definisana standardom IEEE 802.15.4 [42]. Prva verzija standarda je završena u oktobru 2003., a revizija, krajem 2006. godine. Standard definiše karakteristike fiziĉkog sloja (Physical Layer, PHY) i podsloja za kontrolu pristupa medijumu (Medium Access Control, MAC) u sloju veze (Data Link Layer) referentnog modela, uvaţavajući zahteve trţišta u pogledu niske cene, male potrošnje i visoke pouzdanosti prenosa. Sa druge strane, u decembru 2004. godine, ZigBee asocijacija, sastavljena od osam vodećih proizvoĊaĉa logiĉkih kola, predloţila je nadgradnju postojećeg IEEE 802.15.4 standarda zakljuĉno sa aplikacionim slojem referentnog modela [43], koji je prikazan na slici 4.1. Referentni model se sastoji od fiziĉkog sloja, sloja veze, sloja mreţe i sloja aplikacija. IEEE 802.15.4 868/915 MHz Fiziĉki sloj IEEE 802.15.4 2.4 GHz Fiziĉki sloj Sloj veze IEEE 802.15.4 MAC podsloj Sloj mreţe IE E E 8 0 2 .1 5 .4 Z ig B ee Sloj aplikacija Slika 4.1. Referentni IEEE 802.15.4/ZigBee model za bežiĉne senzorske mreže 75 Fiziĉki sloj je odgovoran za prenos podataka preko fiziĉkog medijuma. U ovom sloju se izvršavaju sledeće aktivnosti [42]:  aktivacija i deaktivacija radio primopredajnika,  detekcija energije u kanalu (Energy Detection, ED),  merenje kvaliteta veze (Link Quality Indication, LQI),  procena zauzetosti kanala (Clear Channel Assessment, CCA) bazirana na CSMA-CA mehanizmu,  izbor frekvencijskog kanala (868–868.6 MHz, 902–928 MHz, 2400–2483.5 MHz),  izbor modulacionog postupka (BPSK, OQPSK),  predaja i prijem podataka. Sloj veze je odgovoran za formiranje okvira fiziĉko adresiranje, upravljanje protokom, kontrolu grešaka u prenosu i kontrolu pristupa medijumu. Mreţni sloj je generalno zaduţen za usmeravanje paketa, a aplikacioni sloj vodi raĉuna o pruţanju usluga. Standard IEEE 802.15.4 definiše ĉetiri vrste okvira ĉija je struktura prikazana na slici 4.2:  beacon frame, koji se koristi za komunikaciju izmeĊu koordinatora u mreţi,  data frame, za prenos informacionog sadrţaja,  acknowledgement frame, za potvrdu uspešnog prijema okvira, i  MAC command frame, za upravljanje i kontrolu na MAC podsloju. U predajnom smeru, nakon prijema paketa iz sloja mreţe, na MAC podsloju veze se formira okvir (MAC Protocol Data Unit – MPDU) tako što se ispred i iza MAC Service Data Unit–a (MSDU) dodaju dva polja, MAC Header (MHR) i MAC Footer (MFR). MHR se sastoji od kontrolnog polja (Frame Control Field, FCF), rednog broja okvira (Data Sequence Number, DSN) i adresnog polja sa izvornom i odredišnom adresom (Address Field). MFR sadrţi kontrolnu sekvencu (Frame Check Sequence, FCS) koja predstavlja ostatak deljenja generišućim CRC polinomom nad MPDU poljem. MPDU polje se prosleĊuje fiziĉkom sloju kao PHY Data Frame Payload, odnosno PSDU. Ovo polje, zajedno sa Synchronization Header–om (SHR) i PHY Header–om, formira PHY Data Packet, ili PPDU. Synchronization Header (SHR) se sastoji od preambule (Preambule Sequence, PS) koja omogućuje bitsku sinhronizaciju na prijemu i delimitera (Start of Frame Delimiter, SFD) koji oznaĉava poĉetak okvira. U okviru PHY hedera se nalazi Frame Length polje koje oznaĉava duţinu okvira. U gornjem delu slike je data struktura kontrolnog polja duţine dva okteta, prva tri bita se odnose na tip okvira (Acknowledgment, Data, MAC Command ili Beacon). Peti bit se odnosi na Acknowledgment Request. Ukoliko je ovaj bit setovan na “jedan”, predajnik oĉekuje povratnu informaciju u vidu pozitivne potvrde prijema. Ova informacija se prosleĊuje preko Acknowledgment okvira koji sadrţi isti sekvencijalni broj kao i primljeni Data ili MAC Command okvir. U suprotnom, ukoliko je Acknowledgment Request bit setovan na “nulu”, prijemnik ne šalje potvrdu prijema bez obzira da li je okvir ispravan ili pogrešan. 76 MAC Header (MHR) MAC Footer (MFR) Preamble Sequence Start of Frame Delimiter (SFD) Frame Length Bytes: 4 1 1 5 + (0 20) + n PHY Service Date Unit (PSDU) MAC Protocol Data Unit (MPDU) Synchronisation Header (SHR) PHY Header (PHR) PHY Layer Data payload Frame Control Field (FCF) Frame Check Sequence (FCS) Bytes: 2 1 4 20 n-2 2 Frame Control Field (FCF) Frame Check Sequence (FCS) MHR MFR Bytes: 2 1 2 Acknowledgment Frame MAC Service Data Unit (MSDU) MAC Sublayer MAC Sublayer Data Sequence Number (DNS) Data Sequence Number (DNS) Address Field (AF) Frame Command / Beacon / Data / Frame Check Sequence (FCS) 2 Frame Type Security Enabled Frame Pending Ack. Request Intra- PAN Reserved Dest. Address Node Reserved Source. Address Node Bits: 0 2 3 4 5 6 10 117 9 14 1512 13 11 + (0 20) + n PHY Protocol Date Unit (PPDU) Slika 4.2. Struktura okvira u IEEE 802.15.4 standardu. Na poĉetku ovog poglavlja smo rekli smo da je memorisanje pogrešnih kopija jednog istog okvira bitan preduslov za korišćenje majoritetnog kombinovanja. U odredišnom ĉvoru se mogu naći ne samo kopije razliĉitih okvira koji potiĉu iz istog izvora, već i kopije koje potiĉu iz razliĉitih izvora. Prema tome, za selekciju pogrešnih kopija nije dovoljan samo redni broj kopije, već i identifikacija izvornog ĉvora. To podrazumeva da u odredišnom ĉvoru treba obezbediti pouzdan prijem sekvencijalnog broja i adrese, odnosno MAC hedera, bez obzira na ispravnost MSDU polja. Trenutno, standard je takav da na osnovu CRC sekvence koja pokriva MAC heder i MSDU polje, proverava da li je kompletan okvir ispravan ili nije, ne vodeći raĉuna gde se dogodila greška. To znaĉi da IEEE 802.15.4 standard nije direktno primenljiv za majoritetno kombinovanje paketa i da je potrebno izvršiti odreĊene modifikacije koje povlaĉe izmene i na radio primopredajnicima koji se koriste u senzorskim mreţama. U literaturi postoji više predloga za izmenu standarda [48] – [50]. Jedan od njih [49], koji su predloţili A. Willig i E. Uhlemann, se odnosi na uvoĊenje dodatnog CRC polja koje kontroliše ispravnost MAC hedera, pri ĉemu se zadrţava CRC polje u MAC futeru koje kontroliše kompletan okvir, uz ograniĉenje, da primopredajnik ne odbacuje pogrešne okvire. To znaĉi da primopredajnik najpre ispituje ceo okvir (MPDU), pa kad ustanovi da je okvir pogrešan, ispituje MAC heder da bi se eventualno primenilo majoritetno kombinovanje ukoliko je MAC heder korektan. Ovakav predlog traţi neznatne izmene u standardu, pa i u samoj realizaciji primopredajnika, pri ĉemu dodatno CRC polje MAC hedera moţe da se realizuje ĉisto softverski u procesoru, zajedno sa MAC hederom. Naš predlog je sliĉan, ali je sa stanovišta eksploatacije znatno efikasniji jer u startu ne troši procesorsko vreme za ispitivanje kompletnog okvira, već samo jednog njegovog dela, zaglavlja. Na bazi toga se donosi odluka da li će obrada biti prekinuta ili će se nastaviti sa daljim ispitivanjem, MAC futera. Kao i Willig, i mi predlaţemo uvoĊenje dodatnog CRC polja koje kontroliše MAC heder i koje se nalazi neposredno iza MAC hedera. TakoĊe, zadrţavamo i CRC polje koje se nalazi u MAC futeru, neposredno iza MSDU polja. Osnovna razlika je da ovaj heder ne kontroliše kompletan okvir, već samo MSDU polje. Prilikom prijema okvira, najpre se proverava MAC heder, ukoliko je pogrešan, zaustavlja se dalje procesiranje i okvir se odbacuje ne ĉekajući proveru CRC polja u MAC futeru. MeĊutim, ukoliko je MAC heder ispravan, sledi provera adrese i 77 sekvencijalnog broja. Ako je adresa pogrešna, ili ako postoji greška u redosledu pristizanja okvira, prekida se dalja obrada okvira i okvir se odbacuje. U suprotnom, ukoliko postoji uparenost na nivou adrese i sekvencijalnog broja, vrši se provera MSDU polja. Ukoliko je MSDU polje ispravno, prenos okvira se proglašava ispravnim. MeĊutim, ako je MSDU polje pogoĊeno greškom, okvir se smešta u memorijski bafer procesora zajedno sa pogrešnim kopijama istog okvira, vodeći raĉuna o sekvencijalnom broju i adresi. Majoritetno kombinovanje se sprovodi nad kopijama sa istim sekvencijalnim brojem i adresom, ali samo nad MSDU poljem i CRC poljem u MAC futeru. Na istoj slici je dat predlog nove strukture okvira sa FCS poljem MAC hedera (crveno polje) prema IEEE 802.15.4 standardu. 4.2. Primer hipotetiĉke mreže Na slici 4.3 je prikazana topologija jedne beţiĉne senzorske mreţe koja se sastoji od senzorskih ĉvorova SN, relejnih stanica RN, i odredišta DN. U osnovi svakog senzorskog ĉvora je neki davaĉ koji prikuplja informacije iz okruţenja, analogno-digitalni konvertor, primopredajnik i procesor sa memorijom u kome je realizovana samo SC procedura. Svi senzorski ĉvorovi rade na istoj predajnoj i prijemnoj uĉestanosti fs. Zbog male izlazne snage, koja je posledica ograniĉene potrošnje, u blizini senzorskih ĉvorova se nalaze relejne stanice. Njihov zadatak je da prihvate signal uĉestanosti fs koji dolazi od senzora i da ga konvertuju na uĉestanost fi kako bi se obezbedilo više spojnih puteva izmeĊu senzorskog ĉvora i odredišta. Isto tako, relejne stanice treba da izvrše i konverziju signala u suprotnom smeru, od odredišta prema senzoru, sa uĉestanosti fi, na uĉestanost fs. U tom sluĉaju podatke će primati i deo senzorskih ĉvorova za koje okviri nisu namenjeni. MeĊutim, ovi okviri će biti odbaĉeni zbog neadekvatne adrese. f1 f2 f3 fs fs fs fs fs RN1 RN2 RN3 SN3 SN2 SN1 SN4 SN5 DN Slika 4.3. Primer jedne hipotetiĉke senzorske mreže Odredišni ĉvor, DN se sastoji od m (m = 3) primopredajnika i procesora sa memorijom u kome je realizovana SC+MC procedura. Svaki od primopredajnika radi na istoj predajnoj i prijemnoj uĉestanosti fi (i = 1, 2 i 3). Obrade signala u prijemnicima se mogu posmatrati kao m nezavisnih procesa koji se odvijaju istovremeno ili sa nekim vremenskim kašnjenjem u zavisnosti od propagacije na pojedinim trasama. TakoĊe, mogući su i prekidi u prenosu signala, ili situacije u kojima prijemnik ne detektuje poĉetak okvira usled grešaka u prenosu. 78 Komunikacija izmeĊu ĉvorova se zasniva na IEEE 802.15.4 standardu sa modifikacijama koje se odnose na ubacivanje posebnih CRC polja koja kontrolišu MAC heder i MSDU. Vodeći raĉuna o energetskoj ograniĉenosti senzorskog ĉvora, usvojeno je da senzor ne generiše pozitivnu potvrdu prijema (ACK okvir), odnosno da se prenos poruka od odredišta prema senzorskom ĉvoru vrši bez ARQ procedure. Ovakav pristup ima opravdanja jer se ACK okvir prosleĊuje znatno većom snagom preko odgovarajuće relejne stanice, tako da se oĉekuje da senzorski ĉvorovi ispravno primaju ovaj okvir. Naravno, okvir je minimalne duţine (5 okteta), ĉime se obezbeĊuje pouzdani prenos i pri verovatnoćama grešaka u kanalu reda 10-2. U nekim sistemima za detekciju pozitivne potvrde je dovoljno da prijemnik senzorskog ĉvora detektuje snagu prijemnog signala koja potiĉe od emisije ACK okvira. S obzirom da se majoritetno kombinovanje implementira samo u odredišnom ĉvoru, u narednom potpoglavlju će biti dat opis kompletne SC+MC procedure odredišnog ĉvora uzimajući u obzir predloge za izmenu IEEE 802.15.4 standarda. 4.3. Opis procedure Na slici 4.4. je dat dijagram toka SC+MC procedure implementirane u odredišnom ĉvoru. Dijagram obuhvata ĉetiri stanja: IDLE, TRANSMIT (Tx), RECEIVE (Rx) i TRANSMIT_ACK (Tx_ACK). Posle inicijalizacije koja podrazumeva ukljuĉivanje internog regulatora napona, procesor preko I/O porta generiše reset signal RES koji postavlja kompletnu logiku primopredajnika u poĉetno stanje. Ukljuĉivanjem lokalnog oscilatora, primopredajnik prelazi u IDLE mod. Pretpostavimo da odredišni ĉvor treba da pošalje podatke odreĊenom senzorskom ĉvoru. Odredišni ĉvor iz IDLE moda prelazi u Tx mod. Na MAC podsloju se izvršavaju sledeće aktivnosti:  generiše se MAC heder koji obuhvata kontrolno polje, sekvencijalni broj i adresu odredišnog i izvornog ĉvora;  za MAC heder se izraĉunava CRC sekvenca;  uĉitava se MAC data payload iz višeg sloja;  za MAC data payload se izraĉunava CRC sekvenca;  vrši se odreĊivanje duţine okvira;  okvir se prenosi u TxFIFO bafer samo jednog od primopredajnika;  zauzimanje kanala se vrši na osnovu CSMA-CA algoritma [42];  ukoliko je kanal slobodan, najpre se šalje preambula, a zatim, delimiter,  iza delimitera sledi slanje okvira maksimalne duţine 128 okteta;  posle završenog slanja okvira, predajnik prelazi u IDLE mod. Sada pretpostavimo da odredišni ĉvor treba da primi podatke od senzorskog ĉvora. Odredišni ĉvor iz IDLE moda prelazi u Rx mod. U prijemnicima se izvršavaju sledeće aktivnosti:  dolazni signal se najpre demoduliše, a zatim vodi u ekstraktor takta i odluĉivaĉ,  nakon detekcije poĉetka okvira, podaci se smeštaju u prijemni RxFIFO bafer, vodeći raĉuna o duţini okvira. Procesoru se signalizira da je primljen novi okvir i procesor preko SPI (Serial Pheripheral Interface) interfejsa inicijalizuje redom, po redosledu pristizanja okvira, svaki od prijemnika i prihvata podatke iz bafera. 79  na MAC podsloju se najpre proverava ispravnost MAC hedera koji se odnosi na kontrolno polje, sekvencijalni broj i adresu. Ukoliko su svi MAC hederi neispravni, kopije se odbacuju, a primopredajnici prelaze u stanje ponovnog prijema nove generacije okvira.  u suprotnom, ukoliko je bar jedan MAC heder ispravan, proverava se njegova adresa i sekvencijalni broj. Ako adresa nije sa adresne liste, ili ako postoji greška u redosledu pristizanja okvira, prekida se dalja obrada i okvir se odbacuje. Ukoliko postoji uparenost na nivou adrese i sekvencijalnog broja, vrši se provera MAC payload polja. Ukoliko je i drugi deo okvira ispravan, paket se isporuĉuje korisniku, a procesor generiše pozitivnu potvrdu prijema u vidu ACK okvira koji sadrţi isti sekvencijalni broj kao i primljeni okvir. Treba naglasiti da se pozitivna potvrda prijema šalje po istom kanalu po kome je i primljen ispravni okvir, posle vremena tACK. ACK okvir se prosleĊuje preko odgovarajuće relejne stanice znatno većom snagom, tako da se oĉekuje da senzorski ĉvorovi ispravno primaju ovaj okvir. Posle predaje paketa korisniku, brišu se sadrţaji odgovarajućih registara MC procedure. Ukoliko sve kopije sa istom adresom i sekvencijalnim brojem imaju pogrešna MAC payload polja, kopije se ne odbacuju, već se smeštaju u registre MC procedure. Kada se u memoriji naĊu tri kopije okvira sa istom adresom i sekvencijalnim brojem, pristupa se proceduri majoritetnog kombinovanja koja obuhvata samo MAC payload i njegovo CRC polje. Ukoliko je broj kopija istog okvira manji od tri, ĉeka se sledeća generacija kopija sve dok se u memoriji ne naĊu tri kopije okvira. Ako je rezultujući okvir ispravan, paket se isporuĉuje korisniku, a procesor generiše pozitivnu potvrdu prijema u vidu ACK okvira koji sadrţi isti sekvencijalni broj kao i dolazni okvir koji se šalje po kanalu po kojem je primljena poslednja kopija okvira. Ukoliko je rezultujući okvir pogrešan, primopredajna stanica prelazi u reţim prijema. Ako i sledeća generacija kopija sa istom adresom i sekvencijalnim brojem sadrţi pogrešna MAC payload polja, u memoriju se upisuju nove kopije i to na pozicije najstarijih kopija iz prethodne generacije. 80 Slanje preambule Slanje okvira # Formiranje MAC hedera Kanal# je zauzet ? DA NE Računanje CRC MAC hedera Učitavanje MSDU Računanje CRC MSDU OdreĎivanje dužine okvira Prenos okvira MEMTxFIFO# Slanje SFD Podešavanje predajnikaTx# STXON# sa CCA PredajaPrijem Podešavanje Rx 1 2 3 Detekcija SFD ? SFD# detektovan Dužina okvira ? Prijem okvira u Rx FIFO bafer 1 2 3 1 2 3 1 2 3 CRC provera MAC hedera 1 2 3 CRC# = 1 (OK) Provera ADR & DSN 1 2 3 ADR & DSN# = 1 (OK) CRC provera MSDU 1 2 3 CRC# = 1 (OK) Majority combining Prenos okvira RxFIFO  MEM 1 2 3 CRC provera MSDU CRC1 = 0 CRC2 = 0 CRC3 = 0 CRC = 1 (OK) C R C 1 = 0 & C R C 2 = 0 & C R C 3 = 0 (A D R & D S N 1 = 0 ) & ( A D R & D S N 2 = 0 ) & ( A D R & D S N 3 = 0 ) C R C = 0 Generisanje ACK# okvira Podešavanje predajnikaTx# STXON# bez CCA Slanje ACK# okvira Brisanje MC registara Tx mod Rx mod Tx_ACK mod IDLE Slika 4.4. Dijagram toka SC+MC procedure u odredišnom ĉvoru 81 4.4. Predlog implementacije Funkcionalna šema odredišnog ĉvora je prikazana na slici 4.5. Sastoji se od šest osnovnih modula: tri identiĉna radio primopredajnika, procesorskog bloka, napajanja i korisniĉkog bloka koji obuhvata aplikacione i korisniĉke servise. Osnovni podsklopovi radio primopredajnika su antenska skretnica, sklopovi prijemnog lanca, sklopovi predajnog lanca, sintezator uĉestanosti i upravljaĉki blok. Prijemni lanac ĉine malošumni pojaĉavaĉ, analogni RF prijemnik, digitalni demodulator sa ekstraktorom takta i odluĉivaĉem i prijemnim Rx FIFO baferom. Predajni lanac ĉine predajni Tx FIFO bafer, digitalni modulator, analogni RF predajnik i pojaĉavaĉ snage. FIFO baferi su kapaciteta 128 okteta. Saglasno standardu IEEE 802.15.4, modulacija moţe biti BPSK ili OQPSK. Sintezator u predajnom smeru obezbeĊuje generisanje nosioca, a u prijemnom smeru, pored generisanja nosioca, i fazno usaglašavanje sa dolaznim signalom. Svaki od tri primopredajnika radi na zadatoj uĉestanosti fi koja se definiše pri postavljanju sistema ili specijalnim upravljaĉkim procedurama za koje je odgovoran sloj aplikacija. MAC funkcije su realizovane i hardverski i softverski, mada granica izmeĊu hardvera i softvera moţe fleksibilno da se pomera. Primera radi, hardverski je moguće vršiti detekciju poĉetka okvira i CRC proveru u prijemnom smeru i generisanje poĉetka okvira i CRC sekvence u predajnom smeru. U tom sluĉaju, softverski, u prijemnom smeru treba realizovati sledeće funkcije: detekciju duţine okvira, detekciju sadrţaja kontrolnog polja, detekciju sekvencijalnog broja i detekciju sadrţaja adresnog polja, kao i utvrĊivanje njihove validnosti. U predajnom smeru treba generisati duţinu okvira i MAC heder. U upravljaĉkom bloku se generišu sve komandne funkcije neophodne za rad svih sklopova u primopredajniku, kao što su ukljuĉivanje i iskljuĉivanje predajnika i prijemnika, ukljuĉivanje i iskljuĉivanje oscilatora, itd. Komunikacija izmeĊu primopredajnika i procesora se vrši preko serijskog interfejsa SPI i statusnih signala [44] – [47]. Procesorski blok se realizuje standardnim procesorom sa internom memorijom dovoljnog kapaciteta da prihvati kopije okvira i izvši funkciju majoritetnog kombinovanja (MC). Prema svakom primopredajniku treba obezbediti mogućnost selekcije i prihvatanje statusnih signala. Bitno je da procesor moţe da obavi funkciju generisanja i provere FCS polja bilo na hardverskom ili softverskom nivou. TakoĊe, procesor treba da obezbedi komunikaciju sa krajnjim korisnikom bilo da on predstavlja izvor ili odredište. Funkcije preostalih blokova su jednostavne i i neće biti razmatrane. 82 IEEE 802.15.4 Radio primopredajnik Tx / Rx svič Sintezator učestanosti Pojačavač snage Malošumni pojačavač Digitalni modulator Digitalni demodulator Serijski interfejs Blok za procesiranje Serijski interfejs Hardver za MAC podršku Softver za MAC podršku Analogni RF predajnik Analogni RF prijemnik MC Rx FIFO Tx FIFO Hardver za MAC podršku SPI CCA SFD RES Upravljački blok Korisnički blok Blok za napajanje MEM Slika 4.5. Funkcionalna šema odredišnog ĉvora 83 5. ZAKLJUČAK U tezi je izvršena analiza hibridne ARQ šeme zasnovane na selektivnom i majoritetnom kombinovanju paketa. Poslednjih godina, ova problematika je posebno interesantna za senzorske mreţe. U takvim mreţama, ukoliko se pouzdan prenos informacija ostvaruje primenom diverziti tehnike, metode kombinovanja na bazi majoritetnog odluĉivanja se pokazuju kao efikasno rešenje. U okviru ove problematike, u tezi su postavljeni sledeći ciljevi:  da se dobiju teorijski izrazi za verovatnoću pogrešnog prenosa paketa u sluĉaju primene selektivnog i majoritetnog odluĉivanja, u uslovima kada su verovatnoće grešaka razliĉite na razliĉitim putanjama i kada je broj mogućih paralelnih putanja proizvoljan. Analitiĉki izrazi su veoma bitni prilikom odreĊivanja optimalnog broja putanja u senzorskoj mreţi sa ciljem maksimalne uštede potrošnje energije u senzorskim ĉvorovima.  da se analizira efikasnost hibridne ARQ šeme imajući u vidu razliĉita scenarija pristizanja paketa u odredišni ĉvor. Naime, prisustvo prostornih putanja pri kojima su na pojedim putanjama uslovi prenosa loši, ne obezbeĊuje garantovano prepoznavanje paketa i prenos po svim putanjama tako da se uslovi za majoritetno odluĉivanje mogu obezbediti posle jedne ili više retransmisija. Zbog toga, realni scenario je kombinacija prostornog i vremenskog diverzitija u korist jednog ili drugog scenarija.  da se sagleda mogućnost implementacije imajući u vidu korišćenje poznatih standarda i postojećih hardverskih rešenja koja se koriste u senzorskim mreţama. Posebno teţište je bilo dato modifikaciji rešenja neohodnih za implementaciju korekcije grešaka na bazi majoritetnog kombinovanja paketa. IzvoĊenje teorijskih izraza za verovatnoću pogrešnog prenosa paketa je obraĊeno u drugom poglavlju. Najpre je definisan pojednostavljeni teorijski model i navedene su osnovne postavke na kojima se zasnivala analiza. Zatim su zasebno razmatrani sluĉajevi sistema sa tri i pet kanala (kopija). Kanali su modelovani kao kvazistacionarni, meĊusobno nezavisni binarni simetriĉni kanali sa razliĉitim verovatnoćama grešaka. U izvoĊenju se krenulo od opravdane pretpostavke da se ukupni efekat pouzdanog prenosa ne menja ako se zameni redosled postupaka za korekciju grešaka, tako što će se prvo primeniti majoritetno, a zatim selektivno kombinovanje paketa. Zahvaljujući tome, izvedeni su izrazi u konaĉnom obliku. Proširujući metodologiju primenjenu za tri i pet kopija, i usvajajući Lam-ov pristup, izveden je opšti izraz za verovatnoću pogrešnog prenosa u sluĉaju proizvoljnog broja kanala sa razliĉitim verovatnoćama grešaka. Uvodeći pojam ekvivalentne kanalne verovatnoće, izvedena su dva aproksimativna izraza od kojih jedan predstavlja pojednostavljenu opštu formulu sa jednakim verovatnoćama, a drugi tesnu gornju granicu. Dobijeni izrazi su korišćeni za ilustraciju više karakteristiĉnih sluĉajeva kao i za analizu efikasnosti sa stanovišta doprinosa majoritetnog kombinovanja u odnosu na selektivno kombinovanje paketa. U 84 prilogu je dat listing programa koji omogućava numeriĉko odreĊivanje verovatnoće pogrešnog prenosa paketa u sluĉaju kada je broj kanala manji ili jednak 11. Analiza propusnosti pri razliĉitim scenarijima je razmatrana u trećem poglavlju. Prvo su predstavljena tri karakteristiĉna scenarija, od kojih dva daju graniĉne sluĉajeve, jedan koji odgovara ĉistom prostornom, i drugi, koji odgovara ĉisto vremenskom diverzitiju. Za sva tri scenarija razvijeni su teorijski modeli koji omogućavaju raĉunanje propusnosti na bazi retransmisionih ciklusa. Na osnovu ovih modela kao i na osnovu rezultata za verovatnoće pogrešnog prenosa paketa dobijenih u drugom poglavlju teze, izvedeni su zatim analitiĉki izrazi za propusnost. Pored teorijskih modela, dati su i simulacioni modeli sa detaljnim dijagramima toka za sprovoĊenje simulacionih eksperimenata. Za svaki od scenarija, simulacioni rezultati su dali dobro poklapanje sa odgovarajućim teorijskim rezultatima. Na osnovu izvedenih izraza za propusnost, izvršena je komparativna analiza u kojoj je ispitivan uticaj kljuĉnih parametara kao što su: broj kopija, duţina okvira i kruţno kašnjenje. Problem razliĉitih kanalnih grešaka, prevaziĊen je tako što je analiza propusnosti vršena u funkciji ekvivalentne kanalne verovatnoće. Rezultati su pokazali da primena majoritetnog kombinovanja omogućava efikasan prenos pri ĉemu stepen efikasnosti u najvećoj meri zavisi od broja raspoloţivih putanja i dominirajuće vrste diverzitija (prostorni ili vremenski). Generalno, kada dominira prostorni diverziti, bolje reziltate daje veći broj putanja, meĊutim kada je u pitanju vremenski diverziti, veći broj kanala (vremenskih slotova) ne garantuje veću propusnost. Osnovni elementi implementacije majoritetnog kombinovanja paketa u sklopu beţiĉnih senzorskih mreţa posebne konfiguracije zasnovanih na primeni IEEE 802.15.4 standarda, su razmatrani u ĉetvrtom poglavlju. Specifiĉnost predloţene mreţe je korišćenje jednostavnih senzorskih ĉvorova sa malom potrošnjom. Nasuprot senzorskim ĉvorovima, u relejnim i odredišnim ĉvorovima nema ograniĉenja u pogledu potrošnje što omogućuje da se paketi emituju većom snagom kao i da se implementiraju dopunski mehanizmi bazirani na majoritetnoj logici koji povećavaju pouzdanost prenosa, a samim tim smanjujući broj retransmisija, povećavaju energetsku efikasnost senzorskih ĉvorova. Posebna paţnja je posvećena detekciji i identifikaciji okvira sa ciljem da se obezbedi dominantnost prostornog diverzitija. Zbog toga je predloţena dopunska zaštita hedera okvira uvoĊenjem zaštitnih bita ne samo za detekciju, već i za korekciju grešaka. Pri tome, ovi zaštitni biti nisu sastavni deo mehanizama baziranih na CRC proveri kompletnog okvira. Drugim reĉima, okvir sadrţi dva CRC polja, jedno polje koje kontroliše sadrţaj hedera, i drugo, koje kontroliše informacioni deo okvira. Majoritetno kombinovanje se primenjuje samo nad informacionim delom ukljuĉujuĉi njemu pridruţeno CRC polje. TakoĊe je predloţena procedura koja se primenjuje u razliĉitim scenarijima prijema okvira. Konaĉno, dat je i predlog softverske i hardverske realizacije primopredajnika i procesorskog modula u odredišnom ĉvoru. Teorijski rezultati dobijeni u drugom i trećem poglavlju omogućuju procenu efikasnosti predloţene implementacije posebno vodeći raĉuna o realnim uslovima koje karakterišu razliĉite verovatnoće grešaka duţ razliĉitih putanja. Sumirajući prethodni pregled razmatranih problema ukazujemo na sledeće kljuĉne doprinose teze:  izveden je izraz u zatvorenom obliku za verovatnoću pogrešnog prenosa paketa za tri kanala sa razliĉitim verovatnoćama grešaka; ovaj rezultat je objavljen u referenci [29];  izveden je izraz u zatvorenom obliku za verovatnoću pogrešnog prenosa paketa za pet kanala sa razliĉitim verovatnoćama grešaka;  izveden je izraz za verovatnoću pogrešnog prenosa paketa za proizvoljan broj kanala sa razliĉitim verovatnoćama grešaka; 85  izvršena je komparativna analiza kojom je pokazano da dodatna primena majoritetnog kombinovanja paketa moţe znaĉajno da smanji verovatnoću pogrešnog prenosa paketa u odnosu na selektivno kombinovanje; izbor broja kanala pruţa veliku fleksibilnost rešavanja problema pouzdanog prenosa;  razvijeni su pogodni aproksimativni izrazi koji omogućuju pregledniju i jednostavniju optimizaciju izbora putanja koje dovode do ekonomiĉne potrošnje u senzorskim mreţama;  pokazano je da se ekvivalentna kanalna verovatnoća moţe koristiti kao dobar jedinstveni reprezent kanala sa razliĉitim verovatnoćama grešaka;  razvijeni su modeli karakteristiĉnih scenarija prenosa paketa imajući u vidu problem njihovog prepoznavanja;  izvedeni su izrazi za propusnost koristeći metodu retransmisionih ciklusa [38];  na osnovu izvedenih izraza, izvršena je komparativna analiza uticaja kljuĉnih parametara, kao što su broj kanala, duţina okvira i kruţno kašnjenje, na propusnost;  predloţena je detekcija i korekcija grešaka zaglavlja paketa u cilju njegovog prepoznavanja i identifikacije u prijemniku,  predloţeni su bitni elementi manipulacije paketima kako bi se obezbedila funkcija majoritetnog kombinovanja u odredišnom ĉvoru;  predloţene su modifikacije hardverskih i softverskih rešenja primopredajnika i procesorskog modula u odredišnom ĉvoru koje obezbeĊuje implementaciju majoritetnog kombinovanja paketa. Buduća istraţivanja se sagledavaju u dva pravca, teorijski i praktiĉni. Kod teorijskih istraţivanja, primenjena metodologija bi mogla da se proširi i na druge “hard” postupke kao što su generalizovano kombinovanje paketa i adaptivne varijante kombinovanja razliĉitih postupaka. U praktiĉnim istraţivanjima ima mogućnosti za detaljniju razradu hardverskih i softverskih rešenja u cilju realizacije pojedinih modula i funkcije majoritetnog kombinovanja paketa u okviru odgovarajućih standarda. Na kraju, napomenimo da posebno interesantnu oblast primene predstavljaju ne samo senzorske mreţe, već i drugi tipovi mreţa i telekomunikacionih sistema. Pre svega se misli na mreţe u kojima su ekstremno oteţani uslovi prenosa, kao što je sluĉaj kod kosmiĉkih i podvodnih istraţivanja, pri ĉemu zahtevi za pouzdanim prenosom imaju veći prioritet nad zahtevima za racionalnim korišćenjem komunikacionih kapaciteta. 86 LITERATURA [1] A. S. Tanenbaum, Computer Networks, Englewood Cliffs, Prentice-Hall, 1982. [2] J. L. Massey, Threshold Decoding, Cambridge, MA: M.I.T. Press, 1963. [3] M. Schwarz, Telecommunication Networks: Protocols, Modeling and Analysis, Addison- Wesley Publishing Company, 1987. [4] N. Benvenuto and G. Cherubini, Algorithms for Communications Systems and their Applications, London, John Wiley & Sons, March 2003. [5] D. Drajić i P. Ivaniš, Uvod u teoriju informacija i kodovanje, Akademska misao, Beograd, 2009. [6] P. S. Sindhu, “Retransmission error control with memory,” IEEE Trans. Commun., vol. COM–25, no. 5, pp. 473–479, May 1977. [7] S. Lin, D. J. Costello, and M. J. Miller, “Automatic repeat request error-control schemes,” IEEE Communications Magazine, vol. 22, pp. 5-17, December 1984. [8] S. B. Wicker, “Adaptive rate error control through the use of diversity combining and majority-logic decoding in a hybrid-ARQ protocol,” IEEE Trans. Commun., vol. 39, no. 3, pp. 380–385, March 1991. [9] I. S. Reed, “A class of multiple-error-correcting codes and the decoding scheme,” IEEE Trans. Inf. Theory, vol. IT-4, pp. 38-49, 1954. [10] S. S. Chakraborty, E. Yli-Juuti, and M. Liinaharja, “An ARQ scheme with packet combining,” IEEE Commun. Lett., vol. 2, no. 7, pp. 200–202, July 1998. [11] S. S. Chakraborty, M. Liinaharja, and K. Ruttik, “Diversity and packet combining in Rayleigh fading channels,” IEE Proc. Commun., vol. 152, no. 3, pp. 353–356, June 2005. [12] Y. Liang and S. S. Chakraborty, “ARQ and packet combining with post-reception selection,” in Proc. IEEE VTC 2004-Fall, Los Angeles, CA, USA, Sept. 2004, vol. 3, pp. 1835–1857. [13] E. Masala, A. Servetti, and J. C. de Martin, “Standard compatible error correction for multimedia transmissions over 802.11 WLAN,” in Proc. IEEE, ICME 2005, Amsterdam, The Netherlands, July 2005, pp. 880–883. [14] Y. –W Leung, “Aggressive packet combining for error control in wireless networks,” IEICE Trans. Commun., vol. E83–B, no. 2, Feb. 2000. [15] K. Ishioka, H. Takanashi, and T. Tanaka, “Improved throughput characteristics by ARQ with weighted majority decision,” in Forth IEEE Int. Conf. on Universal Personal Communications Record, Tokyo, Japan, Nov. 1995, pp. 467–471. [16] H. Okada, N. Koie, N. Nakagawa, T. Yamazato, and M. Katayama, “A study on error correcting and diversity combiner scheme on multiple routes in wireless multi-hop networks,” in Wireless Communication Systems, 2004, 1st International Symposium on, Sept. 2004., pp. 183–187. 87 [17] S. Valentin, D. H. Woldegebreal, T. Volkhausen, and H. Karl, “Combining for cooperative WLANs – A reality check based on prototype measurements,” in Communications Workshops 2009. ICC Workshops 2009. IEEE International Conference on, Dresden, June 2009., pp. 1–5. [18] D. O’Rurke, “Practical packet combining for use with cooperative and non-cooperative ARQ schemes in wireless sensor networks,” Ph. D. thesis, School of Electrical Engineering, Faculty of Engineering and Design, Dublin City University, Sep. 2009. [19] E. Uhlemann and A. Willig, “Joint design of relay and packet combining schemes for wireless industrial networks”, in Proc. IEEE Vehicular Technology Conference (VTC), Spring 08, Marina Bay, Singapore, May 2008. [20] E. Uhlemann and A. Willig, “Hard decision packet combining methods for industrial wireless relay networks,” in Proc. Second International Conference on Communications and Electronics (HUT-ICCE 2008), HoiAn, Vietnam, June 2008. [21] R. Cam, C. Leung, and C. Lam, “Performance analysis of some hard-decision combining schemes”, IEEE Transactions on Communications, Vol. 42, No 9, September 1994, pp. 2650–2653. [22] C. Y. H. Lam, Multiple copy combining schemes for the additive white Gaussian noise channel, University of Britisch Columbia, July 1992. [23] R. Cam, C. Leung, and C. Lam, “A performance comparison of some combining schemes for finite-buffer ARQ systems in a Rayleigh-fading channel,” ICWC ’92, pp. 88–92. [24] E. J. Weldon, “An improved selective-repeat ARQ strategy,” IEEE Transactions on Communications, Vol.30, No 3, March 1982. pp. 480-486. [25] C. –X. Wang, M. Pätzold, and D. Yuan, “Accurate and efficient simulation of multiple uncorrelated Rayleigh fading waveforms,” IEEE Trans. Wireless Commun., vol. 6, no. 3, Mar. 2007. [26] Z. Zhou, Z. Peng, J.–H. Cui, and Z. Shi, “Efficient multipath communication for time- critical applications in underwater acoustic sensor networks,” IEEE/ACM Trans. Netw., vol. 19, no. 1, pp. 28–41, Feb. 2011. [27] V. Vuković, G. Petrović, and Lj. Trajković, “Verovatnoća pogrešnog prenosa kod tri- kopijskog modela sa majoritetnom logikom,” XIII Telekomunikacioni forum TELFOR 2005, Beograd, Sava Centar, 22. – 24.11.2005. godine. [28] V. Vuković, G. Petrović, and Lj. Trajković, “Packet error probability in three-copy transmission scheme with majority combining,” in Proc. ETRAN 2009, Vrnjaĉka Banja, Serbia, June 2009. [29] V. Vuković, G. Petrović, and Lj. Trajković, “Packet error probability in a three-branch diversity system with majority combining,” IEEE Commun. Lett., vol. 15, no. 1, pp. 7–9, January 2011. [30] V. Vuković, “An analysis of five-copy transmission with majority combining,” XV Telecommunication forum TELFOR 2007, Beograd, Sava Centar, 20. – 22.11.2007. godine. [31] J. E. Freund, Mathematical Statistics, Prentice Hall, 1999. [32] J. A. Anderson, Discrete Mathematics with Combinatorics, Pearson Education, Inc., 2004. [33] D. Stevanović, M. Ćirić, S. Simić, V. Baltić, Diskretna matematika: osnove kombinatorike i teorija grafova, Društvo matematiĉara Srbije, 2008., [Online] http://alas.matf.bg.ac.rs/~mi10103/predavanja/_ds2/DiscreteMath.pdf [34] Y. –D. Yao, “An effective Go-Back-N ARQ scheme for variable-error-rate channels,” IEEE Trans. Commun., vol. 43, pp.20-23, No.1, January 1995. 88 [35] H. Minn, M. Zeng, and V. K. Bhargava, “On ARQ scheme with adaptive error control,” IEEE Trans. Veh. Technol., vol. 50, no. 6, pp.1426-1436, November 2001. [36] R. Vojinović and Z. Petrović, “A novel three-state ARQ scheme for variable error-rate channels,” AEUE – International Journal of Electronics and Communications, vol. 56, no. 6, pp 389–395, 2002. [37] R.Vojinović, G. Petrović, Z. Petrović: “The analysis of the adaptive three-mode ARQ GBN scheme using retransmission cycles mechanism”, AEUE – International Journal of Electronics and Communications, vol. 60, no. 2, pp. 190–198, 2006. [38] V. Vuković, R. Vojinović, Z. Petrović i G. Petrović, “Analiza propusnosti generalizovanog GBN ARQ modela pomoću retransmisionih ciklusa”, XLIX Konferencija ETRAN-a, vol. 2, pp. 140 – 143, Budva, 5. – 10. juna 2008. godine. [39] V. Vuković, R. Vojinović i G. Petrović, “Propusnost adaptivne dvomodne GBN ARQ šeme sa majoritetnom logikom,” LII Konferencija ETRAN-a, Palić, 8. – 12. juna 2008. godine. [40] V. Vuković and R. Vojinović, “On throughput analysis of an adaptive error – control scheme in satellite networks, ” Microwave Review, ISSN 14505835, vol. 14, no. 2, pp. 8– 11, December 2008. [41] V. Vuković, G. Petrović, and Lj. Trajković, “Simulacija multikopijske go–back–N ARQ procedure sa majoritetnom logikom,” INFOTEH-JAHORINA, vol. 4, ref. B–II–6, pp.113– 116, Mar. 2005. [42] LAN/MAN Standards Committee of the IEEE Computer Society, IEEE Standard for Information technology – Telecommunications and information exchange between systems – Local and metropolitan area networks – Specific requirements – Part 15.4: Wireless Medium Access Control (MAC) and Physical Layer (PHY) Specifications for Low Rate Wireless Personal Area Networks (LR-WPANs), Sept. 2006, revision of 2006., [Online] http://standards.ieee.org/about/get/802/802.15.html [43] ZigBee Standards Organization, ZigBee Specification, Dec. 2006., [Online] http://www.medialab.ch/labor/cc2430/Z-Stack/054024r01ZB_AFG-ZigBee-Specification- 2006-Download.pdf [44] Cipcon, CC2420 2.4 GHz IEEE 802.15.4 / ZigBee-ready RF Transceiver, Chipcon Products from Texas Instruments, 2004., [Online] http://focus.ti.com/lit/ds/symlink/cc2420.pdf [45] Microchip, MRF24J40, Data Sheet, IEEE 802.15.4™ 2.4 GHz RF Transceiver, Microchip Technology Inc. 2008., [Online] http://ww1.microchip.com/downloads/en/DeviceDoc/DS-39776b.pdf [46] Atmel, AT86RF231 – Low Power 2.4 GHz Transceiver for ZigBee/IEEE 802.15.4/6LoWPAN ISM Applications, [Online] http://www.atmel.com/dyn/resources/prod_documents/doc8111.pdf [47] Intersil, SPI Protocol and Bus Configuration of Multiple DCPs, Application note AN1340.0, August 20, [Online] http://www.intersil.com/data/an/an1340.pdf [48] Willig, K. Matheus, and A. Wolisz, “Wireless technology in industrial networks,” in Proceedings of the IEEE, vol. 93, no. 6, pp. 1130–1151, 2005. [49] Willig and E. Uhlemann, “PRIOREL-COMB: A protocol framework supporting relaying and packet combining for wireless industrial networking,” in Proc. 7th IEEE International Workshop on Factory Communication Systems (WFCS), Dresden, Germany, May 2008. [50] Willig, “Memory-efficient segment-based packet-combining schemes in face of deadlines,” IEEE Trans. Industrial Informatics, vol. 5, no. 3, pp. 338–350, Aug. 2009. 89 A. OPIS PROGRAMSKOG PAKETA Programski paket za raĉunanje verovatnoće retransmisije u sluĉaju SC i SC+MC procedura je uraĊen u MATLAB alatu. A.1. Priprema koda Formiranje programa za raĉunanje verovatnoće retransmisije se zasniva na izrazu (2.4.30a)                                          L jj jj m s iijj mjjii L ii m k mii k MCSC s s ks sk k k qq pp qq Q qqP        1 1 11 11 1 1 2/ 0 ,,,, 1 2/ 0 1 1)(1 , (A.1.1) koji se moţe predstaviti u sledećem obliku:                                          2/ 0 2/ 0 ,,,, 111 1 1 11 11 1 1 )(1 m k L jj jj m s iijj mjjmii L ii mii k MCSC s s ks sk k k qq pp QqqP      . (A.1.2) Inverzijom redosleda sabiranja, prethodni izraz postaje:                                          2/ 0 2/ 0 ,,,, 111 1 1 11 11 1 1 )(1 m k L jj jj m s iijj mjjmii L ii mii k MCSC qq pp QqqP s s ks sk k k      , (A.1.3) odnosno, napisan u razvijenom obliku: 90                                                                                                                          m ii Lm suma m ii mm i ii m ii L i m ii L i mm i ii L i m m ii Lk suma m ii km i ii m ii L i m ii L i km i ii L i k m ii L suma m i ii m ii L i m i ii L i m i ii L suma m i ii L i L sumaMCSC HQqqq HQqqq HQqq HQq HQP m mm m mm m k kk k kk k 1 2/ 1 1 12/ 0 11 1 1 12/ 0 1 2/ 1 1 1 1 0 11 1 1 1 0 1 1 2 1 0 11 1 0 1 2 0 1 1 0 1 1 00 2132 12/ 12/2/21 1 32 2 12/ 12/2/ 2/ 2132 1 121 1 32 2 1 1 21 3 3221 1 3 32 2 2 21 2 21 1 )()1( )()1( )()1( )()1( ])(1[)1(     , (A.1.4) gde je    m i iqQ 1 . Sa ksumaH (  2/,,0 mk  ) je oznaĉena suma:                                       m jj j j j m jj j j j mm j jj j j j m jj j j j m jj j j j sm j jj j j j m jj j j j m j jj j j j m j jj j j j k suma q p a q p a q p a q p a q p a q p a q p a q p a q p aH m mm m m m s ss s s s 1 1 1 12/ 0 1 1 1 1 1 0 11 1 0 1 0 1 21 1 1 1 32 2 2 2 12/ 12/2/ 2/ 2/ 2/ 21 1 1 1 32 2 2 2 1 121 1 1 1 3 32 2 2 2 2 21 1 1 1 1   (A.1.5) gde su koeficijenti sj a , (  2/,,1 ms  ) jednaki: 1 sj a , , za 0k (A.1.6) odnosno:       ks ks j iiij iiij a s ,,,,1 ,,,,0 21 21   , za  2/,,1 mk  (A.1.7) 91 A.2. Listinzi programa Programski paket za raĉunanje verovatnoće retransmisije SC i SC+MC procedure se sastoji iz glavnog programa i pet potprograma. U glavnom programu M_m_copy.m se najpre definišu koeficijenti rasejavanja prema SC1 scenariju i kanalne verovatnoće, a zatim se raĉunaju verovatnoće retransmisije pozivom dva potprograma, F_m_copy.m i F_formula.m. Potprogram F_m_copy.m raĉuna verovatnoću retransmisije na bazi izraza (A.1.4). Prvi ĉlan u k-tom redu se raĉuna pomoću potprograma F_suma_RP.m, a drugi ĉlan, koristeći potprogram F_suma_RS.m. Izraz (A.1.5) se raĉuna sumiranjem parcijalnih suma koje se dobijaju pozivom potprograma F_suma_H.m. Svi potprogrami za raĉunanje suma su rešeni iterativnim postupkom. U potprogramu F_formula.m se vrši provera rezultata na bazi izraza (2.4.31) za sluĉaj jednakih kanalnih verovatnoća. Program M_m_copy.m % Program M_m_copy % racuna verovatnoce retransmisije SC i SC+MC procedure u slucaju % proizvoljnog broja kanala u funkciji verovatnoce greske po bitu %--------------------------------------------------------------------------------------------------------------- % ulaz: % m ................ broj kanala % n ................. duzina okvira % p ................. verovatnoca greske po bitu %--------------------------------------------------------------------------------------------------------------- % izlaz: % Psc .............. verovatnoca retransmisije u slucaju SC procedure % Psc+mc …... verovatnoca retransmisije u slucaju SC+MC procedure % Ph ............... verovatnoca retransmisije u slucaju SC+MC procedure % sa jednakim kanalnim verovatnocama %--------------------------------------------------------------------------------------------------------------- % clear all; % m=input('Broj kanala m = '); n=input('Duzina okvira u bitima n = '); % format long e % % definisanje koeficijenata rasejavanja SC1 C=10; for ij=1:m x(ij)=1/C*(C^(2/(m-1)))^(ij-1); end % pmin=1.0e-6; % pocetna verovatnoca greske po bitu pmax=1.0e-0; % krajnja verovatnoca greske po bitu % dp=10^(1/10); % prirastaj verovatnoce greske po bitu 92 p=pmin/dp; % for j=1:61 p=p*dp; % verovatnoca greske po bitu y(j)=p; q=1-p; % verovatnoca ispravnog prenosa bita pf=1-(1-p)^n; % % odredjivanje kanalnih verovatnoca for ij=1:m % x(ij)=1; pp(ij)=min(x(ij)*p,0.5); % kanalne verovatnoce end % [Psc,Psc_mc]=F_m_copy(m,n,pp); Psc_m(j)=Psc; % Psc za razlicite kanalne verovatnoce / - crna / Psc_mc_m(j)=Psc_mc; % Psc+mc za razlicite kanalne verovatnoce / -o crvena / Psc_mc; % [Ph]=F_formula(m,n,p); % Psc+mc za iste kanalne verovatnoce / * plava / Ph_m(j)=Ph; Ph; % end % % crtanje grafika figure; loglog(y,Psc_m,'-k',y,Psc_mc_m,'-or',y,Ph_m,'*b'); axis([pmin pmax 1.0e-10 1]); grid on; xlabel('Bit error probability'); ylabel('Transmission error probability'); 93 Potprogram F_m_copy.m % Potprogram F_m_copy % racuna verovatnocu retransmisije SC i SC+MC procedure u slucaju % razlicitih kanalnih verovatnoca u funkciji verovatnoce greske po bitu %--------------------------------------------------------------------------------------------------------------- % ulaz: % m ............. broj kanala % n .............. duzina okvira izrazena u bitima % pp ............ vektor sa kanalnim verovatnocama %--------------------------------------------------------------------------------------------------------------- % pomocne velicine: % i ............... vektor i [i1,i2,i3,...,i ceo deo od m/2] % j ............... vektor j [j1,j2,j3,...,j ceo deo od m/2] %--------------------------------------------------------------------------------------------------------------- % izlaz: % Psc ........... verovatnoca retransmisije u slucaju SC procedure % Psc+mc .... verovatnoca retransmisije u slucaju SC+MC procedure %--------------------------------------------------------------------------------------------------------------- % function [Psc,Psc_mc]=F_m_copy(m,n,pp); % % verovatnoca ispravnog prenosa bita u pojedinim kanalima for ij=1:m qq(ij)=1-pp(ij); end % % proizvod kanalnih verovatnoca ispravnog prenosa bita Q=1; for ij=1:m Q=Q*qq(ij); end % % racunanje verovatnoce retransmisije u slucaju SC procedure Psc=1; for ij=1:m Psc=Psc*(1-qq(ij)^n); end % % inicijalizacija pomocnih vektora % for ij=1:fix(m/2) i(ij)=0; S(ij)=0; RP(ij)=0; RS(ij)=0; end % 94 % % % racunanje verovatnoce retransmisije u slucaju SC+MC procedure % NULTI RED (kv=0) % racunanje horizontalnih suma kh=1:ceo deo od m/2 for kh=1:fix(m/2) j(kh+1)=0; [S]=F_suma_H(i,j,kh,m,pp,S); SS(kh)=S(kh); end % zbir horizontalnih suma Hsuma=1+sum(SS); % RR0=1-(Q*Hsuma)^n; % % racunanje vertikalnih suma kv=1:ceo deo od m/2 kh=0; for kv=1:fix(m/2) i(kv+1)=0; [RP]=F_suma_RP(i,kv,m,n,pp,RP); [RS]=F_suma_RS(i,j,kv,kh,m,n,pp,RS); % R(kv)=RP(kv)-RS(kv); % RR(kv)=(-1)^kv*R(kv); end % % zbir vertikalnih suma Psc_mc=RR0+sum(RR); % return 95 Potprogram F_suma_H.m % Potprogram F_suma_H % racuna k-tu pojedinacnu horizontalnu sumu %--------------------------------------------------------------------------------------------------------------- % ulaz: % i ....... vektor i [i1,i2,i3,...,i ceo deo od m/2] % j ....... vektor j [j1,j2,j3,...,j ceo deo od m/2] % k ...... red sume % m ..... broj kanala % n ...... duzina okvira izrazena u bitima % pp .... vektor sa kanalnim verovatnocama % S ..... vrednost (k-1)-ve pojedinacne sume %--------------------------------------------------------------------------------------------------------------- % izlaz: % S ..... vrednost k-te pojedinacne sume %--------------------------------------------------------------------------------------------------------------- % function [S]=F_suma_H(i,j,k,m,pp,S); % S(k)=0; jmin=j(k+1)+1; jmax=m-k+1; for jj=jmin:jmax j(k)=jj; qq(jj)=1-pp(jj); pq(jj)=pp(jj)/qq(jj); % a(jj)=1; for ii=1:fix(m/2) if jj==i(ii) a(jj)=0; end end % kk=k-1; if kk==0 S(k)=S(k)+a(jj)*pq(jj); else [S]=F_suma_H(i,j,kk,m,pp,S); S(k)=S(k)+a(jj)*pq(jj)*S(kk); end end % return 96 Potprogram F_suma_RP.m % Potprogram F_suma_RP % racuna prvi clan u kv redu %--------------------------------------------------------------------------------------------------------------- % ulaz: % i ....... vektor i % kv ...... pozicija reda % m ....... broj kanala % n ....... duzina okvira izrazena u bitima % pp ...... vektor sa kanalnim verovatnocama %--------------------------------------------------------------------------------------------------------------- % izlaz: % RP ...... vrednost prvog clana u kv redu %--------------------------------------------------------------------------------------------------------------- % function [RP]=F_suma_RP(i,kv,m,n,pp,RP); % RP(kv)=0; imin=i(kv+1)+1; imax=m-kv+1; for ii=imin:imax i(kv)=ii; qq(ii)=1-pp(ii); % kkv=kv-1; if kkv==0; RP(kv)=RP(kv)+qq(ii)^n; else [RP]=F_suma_RP(i,kkv,m,n,pp,RP); RP(kv)=RP(kv)+qq(ii)^n*RP(kkv); end end % return 97 Potprogram F_SUMA_RS.m % Potprogram F_SUMA_RS % racuna drugi clan u kv redu %--------------------------------------------------------------------------------------------------------------- % ulaz: % i ......... vektor i % j ......... vektor j % kv ...... pozicija reda % kh ...... red pojedinacne horizontalne sume % m ....... broj kanala % n ........ duzina okvira izrazena u bitima % pp ...... vektor sa kanalnim verovatnocama %--------------------------------------------------------------------------------------------------------------- % izlaz: % RS ...... vrednost drugog clana u kv redu %--------------------------------------------------------------------------------------------------------------- % function [RS]=F_suma_RS(i,j,kv,kh,m,n,pp,RS); % % verovatnoca ispravnog prenosa bita u pojedinim kanalima for ij=1:m qq(ij)=1-pp(ij); end % % proizvod verovatnoca ispravnog prenosa bita Q=1; for ij=1:m Q=Q*qq(ij); end % RS(kv)=0; imin=i(kv+1)+1; imax=m-kv+1; for ii=imin:imax i(kv)=ii; qq(ii)=1-pp(ii); % kkv=kv-1; if kkv==0; % racunanje horizontalnih suma for ij=1:fix(m/2) S(ij)=0; end for kh=1:fix(m/2) j(kh+1)=0; [S]=F_suma_H(i,j,kh,m,pp,S); SH(kh)=S(kh); 98 end % % zbir horizontalnih suma Hsuma=1+sum(SH); % RS(kv)=RS(kv)+(Q*Hsuma)^n; % else [RS]=F_suma_RS(i,j,kkv,kh,m,n,pp,RS); RS(kv)=RS(kv)+RS(kkv); end end % return 99 Potprogram F_formula.m % Potprogram F_formula % racuna verovatnocu retransmisije SC+MC procedure u slucaju % jednakih kanalnih verovatnoca u funkciji verovatnoce greske po bitu %--------------------------------------------------------------------------------------------------------------- % ulaz: % m ...... broj kanala % n ....... duzina okvira izrazena u bitima % p ....... verovatnoca greske po bitu %--------------------------------------------------------------------------------------------------------------- % izlaz: % Ph ..... verovatnoca retransmisije %--------------------------------------------------------------------------------------------------------------- % function [Ph]=F_formula(m,n,p) % q=1-p; % verovatnoca ispravnog prenosa bita % suma1=0; for i=0:fix(m/2) % racunanje m nad i m1=m; if i==0 m1_nad_i=1; else m1_nad_i=1; for k=1:i m1_nad_i=m1_nad_i*(m1-i+k)/k; end end % suma2=0; for j=0:fix(m/2) % racunanje m-i nad j m2=m-i; if j==0 m2_nad_j=1; else m2_nad_j=1; for k=1:j m2_nad_j=m2_nad_j*(m2-j+k)/k; end end suma2=suma2+m2_nad_j*p^j*q^(m-i-j); end suma1=suma1+(-1)^i*m1_nad_i*q^(n*i)*(1-suma2^n); end 100 % Ph=suma1; % return 101 B. RAČUNANJE PRELAZNIH VEROVATNOĆA U ovom prilogu je dato izvoĊenje izraza za prelazne verovatnoće za sluĉaj scenarija B3 sa 3m kanala. IzvoĊenje je vršeno pod pretpostavkom da su sve tri kanalne verovatnoće meĊusobno jednake [27] – [28]. B.1. Preliminarne definicije i oznake Posmatrajmo m prenetih kopija istog okvira koje su poreĊane jedna ispod druge. Oznaĉimo sa ),( jiE indikator greške na proizvoljnoj bitskoj poziciji koji ima vrednost 1, ako je bit pogrešan, ili 0, ako je bit ispravan. Pri tome, indeks j oznaĉava redni broj kopije, a indeks i, redni broj elementarnog dogaĊaja. Pod elementarnim dogaĊajem Si podrazumevamo jednu od mogućih kombinacija grešaka koje se mogu pojaviti na istoj bitskoj poziciji u prenetim kopijama okvira. Ako sa p oznaĉimo verovatnoću greške po bitu, verovatnoća pojavljivanja elementarnog dogaĊaja iS je data izrazom: )12,:0(,)1( ),(1 1 ),(     mjiE m j jiE i MMipps . (B.1.1) Svaki prenos od m kopija jednog okvira moţe se posmatrati kao sloţeni dogaĊaj },,,,{ Mi10 kkkk  u kome se elementarni dogaĊaji Si ponavljaju ki puta. Podrazumeva se da je ispunjen uslov nkkk M10   . Verovatnoća ovog sloţenog dogaĊaja je data izrazom: MkM kk M ssskkkC   10 1010 ),,,( , (B.1.2) a verovatnoća unije ovih sloţenih dogaĊaja ima polinomijalnu raspodelu i moţe se napisati u sledećem obliku: MkM kk M M sss kkk n kkkG       10 10 10 10 !!! ! ),,,( . (B.1.3) Sumiranjem izraza (B.1.3) po svim mogućim vrednostima ki, dobija se:    0 10 1)( !!! ! 1010 10k k n M k M kk M M M ssssss kkk n    . (B.1.4) 102 B.2. Raĉunanje prelaznih verovatnoća U ovom odeljku biće odreĊeni izrazi za verovatnoće pf, pm i ph. Verovatnoća pf: Ako sa p oznaĉimo verovatnoću greške po bitu, a sa n broj bita u okviru, verovatnoća pogrešnog prenosa okvira je data izrazom: nf qp 1 , (B.1.5) gde je pq 1 verovatnoća ispravnog prenosa bita. Verovatnoća pm: Verovatnoća pm predstavlja koliĉnik verovatnoća )( ' 3HP i )( '' 2HP koje odgovaraju stanjima '3H i '' 2H (vidi sliku 3.23). )( )( '' 2 ' 3 HP HP pm  . (B.1.6) Verovatnoća )( ''2HP predstavlja verovatnoću dogaĊaja da prva, druga i treća kopija budu pogrešne, tako da je: 3''2 )( fpHP  . (B.1.7) Zamenom (B.1.5) u (B.1.7), prethodni izraz postaje: 3''2 )1()( nqHP  . (B.1.8) DogaĊaj '3H je posledica neuspešne korekcije greške bazirane na majoritetnom kombinovanju tri uzastopne kopije okvira. Prenos je pogrešan ukoliko su sve tri kopije pogrešne i ukoliko postoji bar jedna bitska pozicija sa dvostrukom ili trostrukom greškom. U tabeli B.1 su dati elementarni dogaĊaji Si (i=0:7) koji predstavljaju jednu od mogućih kombinacija grešaka koje se mogu pojaviti na istoj bitskoj poziciji u prve tri kopije okvira. Ovi dogaĊaji se mogu specificirati pomoću indikatora greške ),( jiE ( j=1:3). Tabela B.1. Specifikacija elementarnih dogaĊaja Si ( i = 0:7) DogaĊaj Si Indikator greške  grešaka E(i,1) E(i,2) E(i,3) 0 0 0 0 0 1 1 0 0 1 2 0 1 0 1 3 1 1 0 2 4 0 0 1 1 5 1 0 1 2 6 0 1 1 2 7 1 1 1 3 *0 i 1 oznaĉavaju redom pogrešan i ispravan prenos bita. 103 Pod pretpostavkom da indikator greške ),( jiE ima vrednost 1, ako je bit pogrešan, ili 0, ako je bit ispravan, verovatnoća is (i=0:7) elementarnog dogaĊaja iS je data izrazom: ),(),( )( jiE1 3 1j jiE i p1ps    . (B.1.9) U cilju dalje analize, uvedimo sledeće oznake: (i) )()0(),()0(),()0( 0  iiiiii kGkGkGkGkGkG ; (B.1.10) (ii) )()()( 0  iii kGkGkG ; (B.1.11) gde ki ( i= 0:7) predstavlja broj pojavljivanja elementarnog dogaĊaja Si. NaĊimo sada analitiĉki izraz za verovatnoću pogrešnog prenosa )( '3HP . Polazeći od pretpostavke da vrednost izraza za verovatnoću pogrešnog prenosa ostaje nepromenjena ako zamenimo redosled koraka u izvršavanju procedure, moţemo pisati: )(1)( / ' 3 MCSCMC QQHP  , (B.1.12) gde QMC predstavlja verovatnoću uspešnog prenosa ukoliko se MC izvršava u prvom koraku, a QSC/MC, verovatnoću uspešnog prenosa kada se SC aktivira posle neuspešne MC procedure. Verovatnoća QMC: Pod pretpostavkom da se u prijemniku izvršava samo MC procedura, prenos će biti uspešan ukoliko na bilo kojoj bitskoj poziciji ima najviše jedna greška. Saglasno tabeli 3.1, izraz za verovatnoću QMC se moţe napisati: n MC ssss kkkkkkkkGQ )( ),,,,,,,( 4210 0 7 0 6 0 54 0 3210   . (B.1.13) Verovatnoća QSC/MC: NaĊimo sada verovatnoću ispravnog prenosa pod uslovom da je MC procedura bila neuspešna. Ovo je ekvivalentno sluĉaju da je jedna kopija okvira ispravna, a da se u preostala dve pojavila bar jedna bitska pozicija sa dvostrukom greškom. Izraz za verovatnoću QSC/MC se moţe napisati u obliku sume: 321/ RRRQ MCSC  , (B.1.14) gde su R1, R2 i R3 parcijalne verovatnoće ispravnog prenosa prve, druge i treće kopije okvira, pod uslovom da preostale dve kopije imaju bar po jednu bitsku poziciju sa dvostrukom greškom. Saglasno tabeli 3.1, izrazi za parcijalne verovatnoće ispravnog prenosa su redom: ),,,,,,,( 076 0 54 0 32 0 101 kkkkkkkkGR  , (B.1.15) ),,,,,,,( 07 0 654 0 3 0 2102 kkkkkkkkGR  , (B.1.16) ),,,,,,,( 07 0 6 0 5 0 432102 kkkkkkkkGR  . (B.1.17) S obzirom da vaţi: (i) )()()( 0iii kGkGkG   , (B.1.18) 104 zamenom (B.1.15) – (B.1.17) u (B.1.14), izraz za verovatnoću QSC/MC postaje: ),,,,,,,(),,,,,,,( ),,,,,,,(),,,,,,,( ),,,,,,,(),,,,,,,( 0 7 0 6 0 5 0 4 0 3210 0 7 0 6 0 5 0 43210 0 7 0 6 0 54 0 3 0 210 0 7 0 654 0 3 0 210 0 7 0 6 0 54 0 32 0 10 0 76 0 54 0 32 0 10/ kkkkkkkkGkkkkkkkkG kkkkkkkkGkkkkkkkkG kkkkkkkkGkkkkkkkkGQ MCSC    , (B.1.19) odnosno: nn nn nn MCSC sssssss sssssss sssssssQ )()( )()( )()( 2103210 4105410 4206420/    . (B.1.20) Uzimajući u obzir (B.1.9) i zamenom (B.1.13) i (B.1.20) u (B.1.12), izraz za verovatnoću pogrešnog prenosa )( '3HP postaje: ])2(1[3 )3(1)( 2 23' 3 nn n pqqq pqqHP   , (B.1.21) odnosno, ])1(1[3)21(1)( 2'3 nnnnn pqqpqHP   (B.1.22) Najzad, zamenom izraza (B.1.8) i (B.1.22) u (B.1.6), verovatnoća pogrešnog prenosa pm se moţe napisati kao: 3 2 )1( ])1(1[3)21(1 n nnnnn m q pqqpq p     . (B.1.23) Verovatnoća ph: Verovatnoća ph predstavlja koliĉnik verovatnoća )( ' 4HP i )( '' 3HP koje odgovaraju stanjima '4H i '' 3H (vidi sliku 3.23). )( )( '' 3 ' 4 HP HP ph  . (B.1.24) Verovatnoća )( ''3HP predstavlja verovatnoću dogaĊaja da prva, druga, treća i ĉetvrta kopija okvira budu pogrešne i da na prve tri kopije postoji bar jedna bitska pozicija sa dvostrukom ili trostrukom greškom. Ova verovatnoća se moţe napisati u obliku proizvoda: )()( '3 '' 3 HPpHP f  . (B.1.25) Zamenom izraza (B.1.5) i (B.1.22) u (B.1.25), izraz za )( ''3HP postaje:  ])1(1[3)21(1)1()( 2''3 nnnnnn pqqpqqHP   . (B.1.26) 105 Verovatnoća )( '4HP je posledica neuspešne korekcije greške bazirane na majoritetnom kombinovanju prve tri, odnosno druge tri kopije okvira. Drugim reĉima, prenos je pogrešan, ako su sve kopije pogrešne, i ako na prvoj, drugoj i trećoj kopiji, i na drugoj, trećoj i ĉetvrtoj kopiji okvira, istovremeno postoji bar po jedna bitska pozicija sa dvostrukom ili trostrukom greškom. Verovatnoća )( '4HP se moţe predstaviti na sledeći naĉin: )()()( '4 '' 3 ' 4 HQHPHP  , (B.1.27) gde je )( '4HQ verovatnoća uspešnog prenosa druge tri kopije okvira. U datim uslovima, prenos druge tri kopije okvira je uspešan ako na ovim kopijama nema bitske pozicije sa dvostrukom ili trostrukom greškom. Da bismo odredili verovatnoću )( '4HQ , neophodno je odrediti kako pojedine kombinacije grešaka doprinose verovatnoći pogrešnog prenosa )( ''3HP . U tabeli B.2 su dati elementarni dogaĊaji Si (i=0:15) koji predstavljaju jednu od mogućih kombinacija grešaka koje se mogu pojaviti na istoj bitskoj poziciji u prve tri i druge tri kopije okvira. Ovi dogaĊaji se mogu specificirati pomoću indikatora greške ),( jiE ( j=1:4). Tabela B.2. Specifikacija elementarnih dogaĊaja Si ( i = 0:15) DogaĊaj Si  grešaka Indikator greške  grešaka E(i,1) E(i,2) E(i,3) E(i,4) 0 0 0 0 0 0 0 1 1 1 0 0 0 0 2 1 0 1 0 0 1 3 2 1 1 0 0 1 4 1 0 0 1 0 1 5 2 1 0 1 0 1 6 2 0 1 1 0 2 7 3 1 1 1 0 2 8 0 0 0 0 1 1 9 1 1 0 0 1 1 10 1 0 1 0 1 2 11 2 1 1 0 1 2 12 1 0 0 1 1 2 13 2 1 0 1 1 2 14 2 0 1 1 1 3 15 3 1 1 1 1 3 *0 i 1 oznaĉavaju redom pogrešan i ispravan prenos bita. Pod pretpostavkom da indikator greške ),( jiE ima vrednost 1, ako je bit pogrešan, ili 0, ako je bit ispravan, verovatnoća is (i=0:15) elementarnog dogaĊaja iS je data izrazom: ),(1 4 1 ),( )1( jiE j jiE i pps    . (B.1.28) 106 U cilju dalje analize, uvedimo sledeće oznake: (i) )()0(),()0(),()0( 0  iiiiii kGkGkGkGkGkG ; (B.1.29) (ii) )()()( 0  iii kGkGkG ; (B.1.30) gde ki (i = 0:15) predstavlja broj pojavljivanja elementarnog dogaĊaja Si. Polazeći od pretpostavke da vrednost izraza za verovatnoću pogrešnog prenosa ostaje nepromenjena ako zamenimo redosled u izvršavanju SC i MC procedura, izraz za verovatnoću pogrešnog prenosa )( ''3HP se moţe napisati kao: )(1)( / '' 3 MCSCMC QQHP  , (B.1.31) gde QMC predstavlja verovatnoću uspešnog prenosa ukoliko se MC izvršava u prvom koraku, a QSC/MC, verovatnoću uspešnog prenosa kada se SC aktivira posle neuspešne MC procedure. Verovatnoća QMC: Pod pretpostavkom da se u prijemniku izvršava samo MC procedura, prenos će biti uspešan ukoliko na bilo kojoj bitskoj poziciji u prve tri kopije ima najviše jedna greška. Saglasno tabeli B.2, izraz za verovatnoću QMC se moţe napisati: n MC ssssssss kkkkkkkkkkkkkkkkGQ )( ),,,,,,,,,,,,,,,( 1210984210 0 15 0 14 0 1312 0 111098 0 7 0 6 0 54 0 3210   . (B.1.32) Verovatnoća QSC/MC: NaĊimo sada verovatnoću uspešnog prenosa pod uslovom da je MC procedura bila neuspešna. Prenos je uspešan ukoliko je bar jedna od ĉetiri kopije ispravna i ako na prve tri kopije postoji bar jedna bitska pozicija sa dvostrukom ili trostrukom greškom. To znaĉi da postoje dve grupe dogaĊaja koje ispunjavaju dati uslov u zavisnosti od toga da li je ispravna samo jedna kopija ili postoje dve ispravne kopije. Saglasno tome, izraz za verovatnoću QSC/MC se moţe napisati u obliku sume: BAMCSC QQQ / , (B.1.33) gde QA i QB oznaĉavaju verovatnoće dva meĊusobno iskljuĉiva dogaĊaja koji odgovaraju gore pomenutim sluĉajevima pri kojima je prenos okvira uspešan. Verovatnoća QA predstavlja verovatnoću dogaĊaja koji obuhvataju sluĉajeve ispravnog prenosa samo jedne kopije okvira, sa dvostrukom ili trostrukom greškom na prve tri kopije okvira. U zavisnosti od toga koja je kopija ispravna, razlikujemo ĉetiri parcijalne verovatnoće uspešnog prenosa oznaĉene sa R1, R2, R3 i R4. NaĊimo sada izraz za verovatnoću uspešnog prenosa prve kopije okvira R1. Prenos je uspešan ako postoji takva kombinacija elementarnih dogaĊaja Si (i = 0:15) koja obezbeĊuje bar jednu dvostruku grešku na istoj bitskoj poziciji u drugoj i trećoj kopiji i bar jednu grešku na bilo kojoj poziciji u ĉetvrtoj kopiji. 107 U cilju dalje analize, uvedimo sledeće oznake: ),,,,,,,(),,,,,,,,,,,,,,,( 14121086420 0 1514 0 1312 0 1110 0 98 0 76 0 54 0 32 0 10 kkkkkkkkGkkkkkkkkkkkkkkkkG  , B.1.34) 1414121086420 ),,,,,,,( VkkkkkkkkG   , (B.1.35) ),,,,,,,(),,,,,,,( 014 0 12 0 10 0 864206 0 14121086420 kkkkkkkkGVkkkkkkkkG   , (B.1.36) gde V14 i V6 predstavljaju parcijalne verovatnoće uspešnog prenosa prve kopije okvira. Verovatnoća ),,,,,,,( 014 0 12 0 10 0 86420 kkkkkkkkG  predstavlja verovatnoću uspešnog prenosa i prve i ĉetvrte kopije okvira, sa bar jednom bitskom pozicijom sa dvostrukom greškom na drugoj i trećoj kopiji, što se moţe smatrati “neuspehom” imajući u vidu da se traţila samo verovatnoća uspešnog prenosa prve kopije. Polazeći od izraza ),,,,,,,( 14121086420 kkkkkkkkG , moţemo pisati: 141 14121086420 0 1412108642014121086420 ),,,,,,,(),,,,,,,(),,,,,,,( VA kkkkkkkkGkkkkkkkkGkkkkkkkkG    .(B.1.37) S obzirom da drugi sabirak V14 ispunjava kriterijum da prva kopija bude pogrešna, da postoji bar jedna dvostruka greška na drugoj i trećoj kopiji i da ĉetvrta kopija bude pogrešna, nastavimo sa daljim rastavljanjem prvog sabirka: 2 0 1412108 0 6420 0 14121086420 0 1412108 0 6420 0 141210864201 ),,,,,,,( ),,,,,,,(),,,,,,,(),,,,,,,( AkkkkkkkkG kkkkkkkkGkkkkkkkkGkkkkkkkkGA    . (B.1.38) Saglasno (B.1.30), drugi sabirak u izrazu (B.1.38) se moţe dalje rastaviti: ),,,,,,,(),,,,,,,( 014 0 12 0 10 0 864206 0 141210864202 kkkkkkkkGVkkkkkkkkGA   . (B.1.39) Prema tome, imajući u vidu (B.1.37) – (B.1.39), verovatnoća uspešnog prenosa prve kopije okvira je jednaka sumi parcijalnih verovatnoća uspešnog prenosa, V14 i V6: ),,,,,,,( ),,,,,,,( ),,,,,,,( 0 1412108 0 6420 0 14 0 12 0 10 0 86420 14121086420 6141 kkkkkkkkG kkkkkkkkG kkkkkkkkG VVR      . (B.1.40) S obzirom da vaţi: (i) )()()( 0iii kGkGkG   , (B.1.41) izraz (B.1.40) se moţe napisati kao: ),,,,,,,( ),,,,,,,(),,,,,,,( ),,,,,,,( 0 1412108 0 6420 0 14 0 12 0 10 0 8 0 6420 0 14 0 12 0 10 0 86420 14121086420 6141 kkkkkkkkG kkkkkkkkGkkkkkkkkG kkkkkkkkG VVR     . (B.1.42) 108 Na sliĉan naĉin dolazimo do izraza za verovatnoće uspešnog prenosa druge, treće i ĉetvrte kopije: ),,,,,,,( ),,,,,,,(),,,,,,,( ),,,,,,,( 0 131298 0 5410 0 13 0 12 0 9 0 8 0 5410 0 13 0 12 0 9 0 85410 1312985410 5132 kkkkkkkkG kkkkkkkkGkkkkkkkkG kkkkkkkkG VVR     , (B.1.43) ),,,,,,,( ),,,,,,,,(),,,,,,,( ),,,,,,,( 0 111098 0 3210 0 11 0 10 0 9 0 8 0 63210 0 11 0 10 0 9 0 83210 1110983210 3113 kkkkkkkkG kkkkkkkkkGkkkkkkkkG kkkkkkkkG VVR     , (B.1.44) ),,,,,,,( ),,,,,,,(),,,,,,,( ),,,,,,,(),,,,,,,( ),,,,,,,(),,,,,,,( ),,,,,,,( 0 7 0 6 0 54 0 3210 0 7 0 6 0 5 0 4 0 3210 0 7 0 6 0 5 0 43210 0 7 0 6 0 54 0 3 0 210 0 7 0 654 0 3 0 210 0 7 0 6 0 54 0 32 0 10 0 76 0 54 0 32 0 10 76543210 35674 kkkkkkkkG kkkkkkkkGkkkkkkkkG kkkkkkkkGkkkkkkkkG kkkkkkkkGkkkkkkkkG kkkkkkkkG VVVVR       . (B.1.45) Imajući u vidu (B.1.28), izrazi (B.1.42) – (B.1.45) postaju: n nn n ssssss sssssss ssssssssR )( )()( )( 12108420 4206420 141210864201    , (B.1.46) n nn n ssssss sssssss ssssssssR )( )()( )( 1298410 4105410 13129854102    , (B.1.47) n nn n ssssss sssssss ssssssssR )( )()( )( 1098210 2103210 11109832103    , (B.1.48) n nn nn nn n ssss sssssss sssssss sssssss ssssssssR )( )()( )()( )()( )( 4210 2103210 4105410 4206420 765432104      . (B.1.49) 109 Verovatnoća QB predstavlja verovatnoću dogaĊaja koji obuhvataju sluĉajeve ispravnog prenosa dve kopije okvira, sa dvostrukom greškom na prve tri kopije okvira. To znaĉi da je ĉetvrta kopija uvek ispravna. U zavisnosti od toga koja je kopija ispravna, razlikujemo tri parcijalne verovatnoće uspešnog prenosa oznaĉene sa R14, R24 i R34 koje su date redom: )0,,,(),,,( ),,,( 4206420 642014 kkkGkkkkG kkkkGR    , (B.1.50) )0,,,(),,,( ),,,( 4105410 541024 kkkGkkkkG kkkkGR    , (B.1.51) )0,,,(),,,( ),,,( 2103210 321034 kkkGkkkkG kkkkGR    . (B.1.52) Imajući u vidu (B.1.28), izrazi (B.1.50) – (B.1.52) postaju: nn sssssssR )()( 420642014  , (B.1.53) nn sssssssR )()( 410541024  , (B.1.54) nn sssssssR )()( 210321034  . (B.1.51) Prema tome, sumiranjem parcijalnih verovatnoća uspešnog prenosa (B.1.46) – (B.1.49) i (B.1.53) – (B.1.55), izraz za verovatnoću uspešnog prenosa posle neuspešne MC procedure, QSC/MC postaje: n n n n n nn nn nn n n n MCSC ssss ssssssss ssssss ssssss ssssss sssssss sssssss sssssss ssssssss ssssssss ssssssssQ )( )( )( )( )( )()( )()( )()( )( )( )( 4210 76543210 1098210 1298410 12108420 2103210 4105410 4206420 1110983210 1312985410 14121086420/            . (B.1.56) 110 Zamenom (B.1.32) i (B.1.56) u (B.1.31), izraz za verovatnoću pogrešnog prenosa )( ''3HP glasi: n n n n n nn nn nn n n n n ssss ssssssss ssssss ssssss ssssss sssssss sssssss sssssss ssssssss ssssssss ssssssss ssssssssHP )( )( )( )( )( )()( )()( )()( )( )( )( )(1)( 4210 76543210 1098210 1298410 12108420 2103210 4105410 4206420 1110983210 1312985410 14121086420 1210984210 '' 3             . (B.1.57) Uzimajući u obzir (B.1.28), izraz za verovatnoću pogrešnog prenosa )( ''3HP postaje: ])2(1[3])3(1[ ])23(1[3)34(1)( 2223 2232234'' 3 nnnn nnn pqqqpqqq qppqqqqppqqHP    , (B.1.58) odnosno, ])1(1[3])21(1[ ])1(1[3)21(1)( 22 2'' 3 nnnnnn nnnnn pqqpqq pqqpqHP     . (B.1.59) Nije teško pokazati da su vrednosti izraza (B.1.26) i (B.1.59) jednake, što potvrĊuje ĉinjenicu da je postupak za nalaţenje analitiĉkog izraza za verovatnoću )( ''3HP korektan. Odredimo sada verovatnoću uspešnog prenosa druge tri kopije okvira )( '4HQ . Prenos je uspešan ukoliko nema dvostrukih i trostrukih grešaka na bilo kojoj bitskoj poziciju. Saglasno tome, moţemo pisati 015141312111076  kkkkkkkk . Ako dati uslov primenimo u izrazu (B.1.57) vodeći raĉuna da prvi ĉlan u izrazu više nije jednak 1)( 1514131211109876543210  nssssssssssssssss , već 543210( ssssss  nss )98  , izraz za verovatnoću uspešnog prenosa druge tri kopije okvira postaje: 111 nn nnn nn nn nn n ssssss ssssssssssss ssssssssss ssssssssssss ssssssssssss ssssssssHQ )()( )()()( )()( )()( )()( )()( 210410 421032105410 9841098210 543210983210 985410984210 98543210 ' 4       , (B.1.60) odnosno imajući u vidu (B.1.28), moţemo pisati: nnnnnnn nnnn nn pqpqqpqq pqpqq pqHQ )21()1(2])1(1[2 )1(3)21( )21()( 322 22 2' 4       . (B.1.61) Zamenom (B.1.59) i (B.1.61) u (B.1.27), a zatim (B.1.59) i (B.1.27) u (B.1.24), dolazimo do konaĉnog izraza za verovatnoću pogrešnog prelaza hp .  ])1(1[3)21(1)1( )1(])1(2)1(6)21()21(21[41 2 32 nnnnnn nnnnnnnn h pqqpqq pqpqppqpqq p      . (B.1.62) Treba napomenuti da postoji i drugi naĉin za raĉunanje izraza za verovatnoću uspešnog prenosa druge tri kopije okvira )( '4HQ pod uslovom da su sve ĉetiri kopije pogrešne i da na prvoj i drugoj i/ili prvoj i trećoj kopiji postoji bar jedna bitska pozicija sa dvostrukom greškom. Prenos druge tri kopije okvira je uspešan ako na ovim kopijama nema bitske pozicije sa dvostrukom ili trostrukom greškom. Saglasno tome, moţemo pisati 015141312111076  kkkkkkkk . U cilju dalje analize, uvedimo sledeću oznaku: ),,,,,,,(),,,,,,,,,,,,,,,( 98543210 0 15 0 14 0 13 0 12 0 11 0 1098 0 7 0 6543210 kkkkkkkkGkkkkkkkkkkkkkkkkG  , (B.1.63) NaĊimo sada analitiĉki izraz za verovatnoću uspešnog prenosa druge tri kopije okvira )( '4HQ Polazeći od verovatnoće ),,,,,,,( 98543210 kkkkkkkkG , moţemo pisati redom: 21 9854321098 0 54321098543210 ),,,,,,,(),,,,,,,(),,,,,,,( AA kkkkkkkkGkkkkkkkkGkkkkkkkkG    , (B.1.64) 31 98 0 54321098 0 54 0 321098 0 5432101 ),,,,,,,(),,,,,,,(),,,,,,,( AU kkkkkkkkGkkkkkkkkGkkkkkkkkGA    , (B.1.65) 54 985432109854 0 3210985432102 ),,,,,,,(),,,,,,,(),,,,,,,( AA kkkkkkkkGkkkkkkkkGkkkkkkkkGA    , (B.1.66) 62 98 0 54321098 0 5 0 4321098 0 5432103 ),,,,,,,(),,,,,,,(),,,,,,,( AU kkkkkkkkGkkkkkkkkGkkkkkkkkGA    , (B.1.67) 112 73 9854 0 32109854 0 3 0 2109854 0 32104 ),,,,,,,(),,,,,,,(),,,,,,,( AU kkkkkkkkGkkkkkkkkGkkkkkkkkGA    , (B.1.68) 18 98543210 0 98543210985432105 ),,,,,,,(),,,,,,,(),,,,,,,( VA kkkkkkkkGkkkkkkkkGkkkkkkkkGA    , (B.1.69) 29 98 0 543210 0 98 0 54321098 0 5432106 ),,,,,,,(),,,,,,,(),,,,,,,( VA kkkkkkkkGkkkkkkkkGkkkkkkkkGA    ,(B.1.70) 310 9854 0 3210 0 9854 0 32109854 0 32107 ),,,,,,,(),,,,,,,(),,,,,,,( VA kkkkkkkkGkkkkkkkkGkkkkkkkkGA    ,(B.1.71) 44 0 98543210 0 9 0 8543210 0 985432108 ),,,,,,,(),,,,,,,(),,,,,,,( VU kkkkkkkkGkkkkkkkkGkkkkkkkkGA    ,(B.1.72) 55 0 98 0 543210 0 9 0 8 0 543210 0 98 0 5432109 ),,,,,,,(),,,,,,,(),,,,,,,( VU kkkkkkkkGkkkkkkkkGkkkkkkkkGA    ,(B.1.73) 66 0 9854 0 3210 0 9 0 854 0 3210 0 9854 0 321010 ),,,,,,,(),,,,,,,(),,,,,,,( VU kkkkkkkkGkkkkkkkkGkkkkkkkkGA    ,(B.1.74) gde 61 VV  predstavljaju parcijalne verovatnoće uspešnog prenosa druge tri kopije okvira pod uslovom da su sve kopije pogrešne i da se na prvoj i drugoj i/ili prvoj i trećoj kopiji desila bar jedna dvostruka greška. Prema tome, imajući u vidu (B.1.64) – (B.1.74), verovatnoća uspešnog prenosa )( '4HQ se moţe izraziti kao zbir parcijalnih verovatnoća ispravnog prenosa 61 VV  ili preko parcijalnih verovatnoće pogrešnog prenosa 61 UU  : )(),,,,,,,()( 65432198543210 ' 4 UUUUUUkkkkkkkkGHQ  , (B.1.75) odnosno, ),,,,,,,( ),,,,,,,( ),,,,,,,( ),,,,,,,( ),,,,,,,( ),,,,,,,( ),,,,,,,()( 0 9 0 854 0 3210 0 9 0 8 0 543210 0 9 0 8543210 9854 0 3 0 210 98 0 5 0 43210 98 0 54 0 3210 98543210 ' 4 kkkkkkkkG kkkkkkkkG kkkkkkkkG kkkkkkkkG kkkkkkkkG kkkkkkkkG kkkkkkkkGHQ             . (B.1.76) S obzirom da vaţi: (i) )()()( 0iii kGkGkG   , (B.1.77) (ii) ),( ),(),( ),(),( 00 00 ji jiji jiji kkG kkGkkG kkGkkG    , (B.1.78) 113 izraz (B.1.76) se moţe napisati kao: ),,,,,,,( ),,,,,,,(),,,,,,,( ),,,,,,,( ),,,,,,,( ),,,,,,,(),,,,,,,( ),,,,,,,( ),,,,,,,( ),,,,,,,(),,,,,,,( ),,,,,,,( ),,,,,,,(),,,,,,,( ),,,,,,,(),,,,,,,( ),,,,,,,( ),,,,,,,()( 0 9 0 8 0 54 0 3 0 210 0 9 0 854 0 3 0 210 0 9 0 8 0 54 0 3210 0 9 0 854 0 3210 0 9 0 8 0 5 0 4 0 3210 0 9 0 8 0 54 0 3210 0 9 0 8 0 5 0 43210 0 9 0 8 0 543210 0 9 0 8 0 54 0 3210 0 9 0 854 0 3210 0 9 0 8 0 543210 0 9 0 8543210 98 0 54 0 3 0 2109854 0 3 0 210 98 0 5 0 4 0 321098 0 5 0 43210 98 0 54 0 3210 98543210 ' 4 kkkkkkkkG kkkkkkkkGkkkkkkkkG kkkkkkkkG kkkkkkkkG kkkkkkkkGkkkkkkkkG kkkkkkkkG kkkkkkkkG kkkkkkkkGkkkkkkkkG kkkkkkkkG kkkkkkkkGkkkkkkkkG kkkkkkkkGkkkkkkkkG kkkkkkkkG kkkkkkkkGHQ              . (B.1.79) Primenom sliĉnih matematiĉkih transformacija, dobija se izraz za verovatnoću uspešnog prenosa )( '4HQ koji je identiĉan izrazu (B.1.61). 114 C. SPISAK SKRAĆENICA Oznaka Znaĉenje ACK Positive Acknowledgement ARQ Automatic Repeat Request BER Bit Error Rate BPSK Binary Phase Shift Keying CCA Clear Channel Assessment CRC Cyclic Redudancy Check CSI Channel State Information CSMA-CA Carrier Sense Multiple Access with Collision Avoidance DN Destination Node DSN Data Sequence Number FCF Frame Control Field FCS Frame Check Sequence FEC Forward Error Correction GBN Go-Back-N HARQ Hybrid Automatic Repeat Request IP Internet Protocol LR-WPAN Low Rate Wireless Personal Area Network LQI Link Quality Indication MFR MAC Footer MHR MAC Header MPDU MAC Protocol Data Unit MSDU MAC Service Data Unit NAK Negative Acknowledgement OQPSK Offset Quadrature Phase Shift Keying OSI Open Systems Interconnection PDU Packet Data Unit PPDU PHY Protocol Data Unit PSDU PHY Data Service Unit RN Relay Node SDU Service Data Unit SFD Start of Frame Delimiter SHR Synchronization Header SN Source Node SNR Signal to Noise Ratio SR Selective Repeat SW Stop and Wait WSN Wireless Sensor Networks 115 D. SPISAK SIMBOLA Oznaka Znaĉenje L Duţina okvira u bitima m Broj putanja (kanala) / broj kopija N Normalizovano kruţno kašnjenje nf Broj kopija / slotova u simulacionom postupku pE Ekvivalentna kanalna verovatnoća pk Kanalna verovatnoća Pf Verovatnoća pogrešnog prenosa okvira S Propusnost Sˆ Procenjena vrednost propusnosti SCP Verovatnoća retransmisije u sluĉaju primene SC procedure A SCP Aproksimativni izraz za verovatnoću retransmisije u sluĉaju primene SC MCSCP  Verovatnoća retransmisije u sluĉaju primene kombinovane procedure A MCSCP  Aproksimativni izraz za verovatnoću retransmisije u sluĉaju primene kombinovane SC+MC procedure E MCSCP  Aproksimativni izraz za verovatnoću retransmisije u funkciji ekvivalentne kanalne verovatnoće u sluĉaju primene kombinovane SC+MC procedure S MCSCP  Aproksimativni izraz za verovatnoću retransmisije za jednake kanalne verovatnoće u sluĉaju primene kombinovane SC+MC procedure U MCSCP  Aproksimativni izraz za gornju granicu verovatnoće retransmisije u sluĉaju primene kombinovane SC+MC procedure MCQ Verovatnoća uspeha MC procedure SCMCQ / Verovatnoća uspeha MC procedure posle otkaza SC procedure MCSCQ / Verovatnoća uspeha SC procedure posle otkaza MC procedure T Srednje vreme trajanja retransmisionih ciklusa Tf Trajanje okvira  x Celobrojni deo od x SC Selektivno kombinovanje (odluĉivanje) MC Majoritetno kombinovanje (odluĉivanje) SC+MC Kombinovano odluĉivanje 116 E. SPISAK SLIKA R.b. Naziv Str. 1.1. Topologija jedne tipiĉne mreţe sa višestrukim putanjama..................................... 6 1.2. Pojednostavljeni model ARQ šeme sa majoritetnim kombinovanjem paketa ....... 7 2.1. Teorijski model za detekciju i korekciju grašaka posredstvom SC+MC procedure ............................................................................................................... 11 2.2. Ilustrativni primer: (a) verovatnoće pogrešnog prenosa okvira u tri individualna kanala; (b) verovatnoća retransmisije posle SC procedure, i (c) verovatnoća retransmisije posle SC+MC procedure ………………………………………….. 16 2.3. Komparacija taĉne i aproksimativnih formula za verovatnoću retransmisije (L=50 i L=2000, m = 3; x1 = 1/10, x2 = 1 i x3 = 10) ……..………………………. 18 2.4. Klase raspodela koeficijenata rasejavanja 19 2.5. Relativna promena verovatnoće retransmisije PSC+MC u sluĉaju odabranih klasa koeficijenata rasejavanja (a) pE = 5x10 -5 , (b) pE = 5x10 -4 , (c) pE = 5x10 -5 (m = 3, L = 500) ………………………………….…………..………………….. 20 21 2.6. Prikaz gornje granice, aproksimativne i egzaktne vrednosti verovatnoće retransmisije u funkciji ekvivalentne kanalne verovatnoće, (L=50 i L=2000, m = 5; x1 = 1/10, x2 = 1/3; x3 = 1; x4 = 3 i x5 = 10) ..................... 25 2.7. Prikaz memorisanih kopija i ilustracija podskupova ][kivm i ][ , sj vw km …..……….. 29 2.8. Prikaz gornje granice, egzaktne i aproksimativne vrednosti verovatnoće retransmisije u funkciji ekvivalentne kanalne verovatnoće (a) m = 7, (b) m = 9, (c) m = 11, (SC1, L = 72 i L = 1024) .................................... 34 35 2.9. Efekat rasejavanja na verovatnoće retransmisije u funkciji ekvivalentne kanalne verovatnoće (a) m = 7, (b) m = 9, (c) m = 11, (L = 1024, SC1 klasa je oznaĉena zvezdicom)....................................................... 37 38 2.10. Verovatnoća retransmisije u funkciji ekvivalentne kanalne verovatnoće, (a) SC procedura, (b) SC+MC procedura, (L = 1024 i m = 3, 5, 7, 9 i 11) …...…. 39 2.11. Verovatnoća retransmisije u funkciji duţine okvira, (pE = 10 -2 i m = 3 i 11) ….… 40 2.12. Iznos (a) “apsolutnog” i (b) “relativnog” doprinosa u funkciji ekvivalentne kanalne verovatnoće (L = 1024 i m = 3, 5, 7, 9 i 11) ………………..………....... 41 2.13. Dijagrami koji ilustruju ograniĉenja za QMC/SC ..................................................... 42 2.14. Verovatnoća retransmisije u funkciji odnosa snaga signal-šum, (L = 1024 i m = 3 i 11) …………………………………………………………… 43 2.15. Dobitak u zavisnosti od broja kanala (a) L = 1024 i (b) L = 72; (referentna vrednost verovatnoće retransmisije Pref = 10 -3 , 10 -6 i 10 -9) ……………………... 44 117 3.1. Ekvivalentni model za raĉunanje propusnosti ARQ šeme sa SC+MC procedurom 46 3.2. Vremenski dijagram za scenario B1 (m = 3) ......................................................... 46 3.3. Vremenski dijagram za scenario B2 (m = 3) ......................................................... 47 3.4. Vremenski dijagram za scenario B3 (m = 3) ......................................................... 47 3.5. Dijagram toka aktivnosti scenarija B1 (m = 3) ………………………………….. 49 3.6. Dijagram stanja scenarija B1 ................................................................................. 50 3.7. Komprimovani dijagram stanja scenarija B1 ........................................................ 50 3.8. Retransmisioni ciklusi scenarija B1 …………………………………………….. 50 3.9. Model za procenu propusnosti scenarija B1 ……………………………………. 53 3.10. Dijagram toka simulacionog postupka za scenario B1 ......................................... 53 3.11. Dijagram toka za drugu fazu simulacionog postupka scenarija B1…………….... 55 3.12. Propusnost scenarija B1 u funkciji ekvivalentne kanalne verovatnoće (m = 3, n = 100 i N = 4) ......................................................................................... 56 3.13. Dijagram toka scenarija B2 (m = 3) ………………………………………..…… 57 3.14. Dijagram stanja scenarija B2 (m = 3) …………………………………………… 58 3.15. Komprimovani dijagram stanja scenarija B2 (m = 3) …………………………… 58 3.16. Retransmisioni ciklusi scenarija B2……………………………………………… 59 3.17. Model za procenu propusnosti scenarija B2 61 3.18. Dijagram toka za drugu fazu simulacionog postupka scenarija B2 ……………... 62 3.19. Propusnost scenarija B2 u funkciji ekvivalentne kanalne verovatnoće (m = 3, n = 100 i N = 4) ......................................................................................... 63 3.20. Dijagram toka scenarija B3 ……………………………………………………… 64 3.21. Dijagram stanja scenarija B3 …………………………………………………..... 65 3.22. Komprimovani dijagram stanja B3 scenarija ……………………………………. 65 3.23. Retransmisioni ciklusi scenarija B3 ……………………………………………... 66 3.24. Model za procenu propusnosti scenarija B3 …………………………………….. 68 3.25. Dijagram toka za drugu fazu simulacionog postupka scenarija B3 ...................... 69 3.26. Propusnost scenarija B3 u funkciji ekvivalentne kanalne verovatnoće (m = 3, n = 100 i N = 4) ......................................................................................... 70 3.27. Propusnost scenarija B1, B2 i B3 u funkciji ekvivalentne kanalne verovatnoće (m = 3, n = 400, N = 4) .......................................................................................... 71 3.28. Propusnost scenarija B1 i B2 u funkciji ekvivalentne kanalne verovatnoće pri razliĉitom broju kopija (n = 400, N = 4, m = 3, 5 i 7) ...................................... 72 3.29. Propusnost scenarija B1 i B2 u funkciji ekvivalentne kanalne verovatnoće pri razliĉitim duţinama okvira (m = 3, N = 4, n = 10, 100 i 1000) ....................... 72 3.30. Propusnost scenarija B1 i B2 u funkciji ekvivalentne kanalne verovatnoće pri razliĉitim vrednostima kruţnog kašnjenja (m = 3, n = 400, N = 1, 4 i 10) ...... 73 4.1. Referentni IEEE 802.15.4/ZigBee model za beţiĉne senzorske mreţe .................. 74 4.2. Struktura okvira u IEEE 802.15.4 standardu ......................................................... 76 4.3. Primer jedne hipotetiĉke senzorske mreţe ............................................................. 77 4.4. Dijagram toka SC+MC procedure u odredišnom ĉvoru ........................................ 80 4.5. Funkcionalna šema odredišnog ĉvora .................................................................... 82 118 F. SPISAK TABELA R.b. Naziv Str. B.1. Specifikacija elementarnih dogaĊaja Si (i = 0:7) ................................................... 102 B.2. Specifikacija elementarnih dogaĊaja Si (i = 0:15) .................................................. 105 Biografija autora Mr Vladimir Vuković je roĎen 1961. godine u Obrenovcu gde je završio osnovnu školu i Gimnaziju prirodnomatematičkog smera. Na Elektrotehnički fakultet u Beogradu, odsek Elektronike, upisao se 1981. godine, a diplomirao je 1986. sa diplomskim radom pod nazivom “Hardver za brzu FFT”. Poslediplomske studije na Katedri za telekomunikacije, smer Digitalni prenos informacija, upisao je 1987. godine. Magistarski rad pod nazivom “5B6B koder i dekoder za prenos po svetlovodima digitalnog signala protoka 140 Mb/s” odbranio je u januaru 1991. godine pod mentorstvom profesora dr Grozdana Petrovića. Nakon diplomiranja, zaposlio se kao stručni saradnik na Katedri za telekomunikacije Elektrotehničkog fakulteta u Beogradu, gde ostaje do kraja avgusta 1990. godine radeći na projektima fakulteta koje su vodili profesori dr Grozdan Petrović i dr Dušan Drajić. Od januara 1991. godine, pa sve do 2000. godine, na istoj Katedri je angažovan kao spoljni saradnik na sledećim projektima i radnim zadacima:  projektovanje i realizacija sklopova sinhronog multipleksa za prenos digitalnog signala protoka 2048, 1024, 512 i 256 kbps, sinfazna petlja na 20.480 MHz sa dedžiterizatorom, bitska sinhronizacija, sinhronizacija okvira i sl.;  simulacija Rummler-ovog modela kanala sa fedingom pomoću računara,  projektovanje i realizacija sklopova za on line nadgledanje grešaka na liniji korišćenjem redudanse u multipleksnom kanalu;  projektovanje i realizacija pojedinih sklopova optičkog linijskog terminala (5B6B koder i dekoder u ECL tehnologiji) simulacija rada 5B6B kodera i dekodera na računaru, sinhronizacija 5B6B dekodera, sinfazne petlje na 139.264 MHz i 167.11MHz (Projekat Republičke zajednice za nauku – Optički linijski terminal na 139 MHz)  projektovanje i realizacija 160 kbps sinhronog multipleksa do četiri ulazna kanala i linijskim interfejsima za priključivanje računara, telefonskog aparata, induktorskog telefona i mikrotelefonske kombinacije;  projektovanje i realizacija NT1 mrežnog završetka;  projektovanje i realizacija digitalnog kodnog kanala sa uniformnom i pseudoslučajnom raspodelom grešaka;  sinteza učestanosti, frekvencijsko skakanje. Objavio je veći broj radova iz oblasti predložene teme. Prvi koautor je jednog rada u prestižnom meĎunarodnom časopisu sa IMPACT faktorom (IEEE Communications Letters). TakoĎe, prvi koautor je jednog rada u domaćem časopisu meĎunarodnog značaja (Microwave Review). Pored toga, kandidat je autor ili prvi koautor još šest radova na domaćim konferencijama (Telfor, Etran, Infoteh). Objavljeni radovi iz oblasti disertacije MeĎunarodni časopisi sa IMPACT faktorom: - V. Vuković, G. Petrović, and Lj. Trajković, “Packet error probability in a three-branch diversity system with majority combining,” IEEE Commun. Lett., vol. 15, no. 1, pp. 7–9, January 2011. Radovi u domaćim časopisima meĎunarodnog značaja: - V. Vuković and R. Vojinović, “On throughput analysis of an adaptive error – control scheme in satellite networks,” Microwave Review, ISSN 14505835, vol. 14, no. 2, pp. 8- 11, december 2008. Radovi na domaćim konferencijama: - V. Vuković, G. Petrović, and Lj. Trajković, “Simulation of multicopy go-back-n ARQ scheme with majority-logic decoding,” INFOTEH 2005, Jahorina, vol. 4, ref. B-II-6, pp. 113-116, Mar. 2005. - V. Vuković, R. Vojinović, Z. Petrović, and G. Petrović, “Throughput analysis of adaptive two-mode GBN ARQ scheme with retransmission cycles,” XLIX Konferencija ETRAN-a, Budva, 5.-10. juna 2005. godine. - V. Vuković, G. Petrović, and Lj. Trajković, “Influence of majority decision on reducing block error rate in three-copy transmission,” XIII Telekomunikacioni forum TELFOR 2005, Beograd, Sava Centar, 22.- 24.11.2005. godine. - V. Vuković, “An analysis of five-copy transmission with majority combining”, XV Telecommunication forum TELFOR 2007, Beograd, Sava Centar, 20.- 22.11.2007. godine. - V. Vuković, R. Vojinović, and G. Petrović, “Propusnost adaptivne dvomodne GBN ARQ šeme sa majoritetnom logikom,” LII Konferencija ETRAN-a, Palić, 8.-12. juna 2008. godine. - V. Vuković, G. Petrović, and Lj. Trajković, “Packet error probability in transmission scheme with three-copy majority combining,” LIII Konferencija ETRAN-a, Vrnjačka Banja, 15.-18. juna 2009. godine. Prilog 1. Izjava o autorstvu Potpisani: Vladimir D. Vuković broj indeksa: _____________ Izjavljujem da je doktorska disertacija pod naslovom: Efikasni ARQ algoritmi bazirani na majoritetnoj logici  rezultat sopstvenog istraživačkog rada,  da predložena disertacija u celini ni u delovima nije bila predložena za dobijanje bilo koje diplome prema studijskim programima drugih visokoškolskih ustanova,  da su rezultati korektno navedeni, i  da nisam kršio autorska prava i koristio intelektualnu svojinu drugih lica. U Beogradu, 30.04.2012.godine Potpis doktoranta _________________________ Vladimir D. Vuković Prilog 2. Izjava o istovetnosti štampane i elektronske verzije doktorskog rada Ime i prezime autora: Vladimir D. Vuković Broj indeksa: _______________________ Studijski program: ___________________ Naslov rada: Efikasni ARQ algoritmi bazirani na majoritetnoj logici Mentor: prof. dr Aleksandra Smiljanić, dipl. inž. el. Potpisani: ____________________________________ Izjavljujem da je štampana verzija mog doktorskog rada istovetna elektronskoj verziji koju sam predao za objavljivanje na portalu Digitalnog repozitorijuma Univerziteta u Beogradu. Dozvoljavam da se objave moji lični podaci vezani za dobijanje akademskog zvanja doktora nauka, kao što su ime i prezime, godina i mesto roĎenja i datum odbrane rada. Ovi lični podaci mogu se objaviti na mrežnim stranicama digitalne biblioteke, u elektronskom katalogu i u publikacijama Univerziteta u Beogradu. U Beogradu, 30.04.2012.godine Potpis doktoranta _________________________ Vladimir D. Vuković Prilog 3. Izjava o korišćenju Ovlašćujem Univerzitetsku biblioteku „Svetozar Marković“ da u Digitalni repozitorijum Univerziteta u Beogradu unese moju doktorsku disertaciju pod naslovom: Efikasni ARQ algoritmi bazirani na majoritetnoj logici koja je moje autorsko delo. Disertaciju sa svim prilozima predao sam u elektronskom formatu pogodnom za trajno arhiviranje. Moju doktorsku disertaciju smeštenu u Digitalnom repozitorijumu Univerziteta u Beogradu mogu da koriste svi koji poštuju odredbe sadržane u odabranom tipu licence Kreativne zajednice (Creative Commons) za koju sam se odlučio. 1. Autorstvo 2. Autorstvo – nekomercijalno 3. Autorstvo – nekomercijalno – bez prerade 4. Autorstvo – nekomercijalno – deliti pod istim uslovima 5. Autorstvo – bez prerade 6. Autorstvo – deliti pod istim uslovima (Molimo da zaokružite samo jednu od šest ponuĎenih licenci, kratak opis licenci dat je na poleĎini lista). U Beogradu, 30.04.2012.godine Potpis doktoranta _________________________ Vladimir D. Vuković 1. Autorstvo - Dozvoljavate umnožavanje, distribuciju i javno saopštavanje dela, i prerade, ako se navede ime autora na način odreĎen od strane autora ili davaoca licence, čak i u komercijalne svrhe. Ovo je najslobodnija od svih licenci. 2. Autorstvo – nekomercijalno. Dozvoljavate umnožavanje, distribuciju i javno saopštavanje dela, i prerade, ako se navede ime autora na način odreĎen od strane autora ili davaoca licence. Ova licenca ne dozvoljava komercijalnu upotrebu dela. 3. Autorstvo - nekomercijalno – bez prerade. Dozvoljavate umnožavanje, distribuciju i javno saopštavanje dela, bez promena, preoblikovanja ili upotrebe dela u svom delu, ako se navede ime autora na način odreĎen od strane autora ili davaoca licence. Ova licenca ne dozvoljava komercijalnu upotrebu dela. U odnosu na sve ostale licence, ovom licencom se ograničava najveći obim prava korišćenja dela. 4. Autorstvo - nekomercijalno – deliti pod istim uslovima. Dozvoljavate umnožavanje, distribuciju i javno saopštavanje dela, i prerade, ako se navede ime autora na način odreĎen od strane autora ili davaoca licence i ako se prerada distribuira pod istom ili sličnom licencom. Ova licenca ne dozvoljava komercijalnu upotrebu dela i prerada. 5. Autorstvo – bez prerade. Dozvoljavate umnožavanje, distribuciju i javno saopštavanje dela, bez promena, preoblikovanja ili upotrebe dela u svom delu, ako se navede ime autora na način odreĎen od strane autora ili davaoca licence. Ova licenca dozvoljava komercijalnu upotrebu dela. 6. Autorstvo - deliti pod istim uslovima. Dozvoljavate umnožavanje, distribuciju i javno saopštavanje dela, i prerade, ako se navede ime autora na način odreĎen od strane autora ili davaoca licence i ako se prerada distribuira pod istom ili sličnom licencom. Ova licenca dozvoljava komercijalnu upotrebu dela i prerada. Slična je softverskim licencama, odnosno licencama otvorenog koda.