Efficient ARQ algorithms based on majority logic decision
Vladimir Vukovic · 2012
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.