X36DSI: Zadání projektu č.1

Nadšený ornitolog hodlá v jedné lokalitě odchytit 100 ptáků. Každému chce připevnit na tělo malý komunikátor a poté ptáka vypustit zpět do přírody. Cílem ornitologa je studium zpěvné aktivity vybraných druhů pěvců.

Ornitolog si pro tento účel nechal vyrobit komunikátory, které obsahují vysílač, přijímač, mikropočítač, paměť a další podpůrné obvody a také baterii, která se dobíjí díky tělesné teplotě ptáka. Každý komunikátor je schopen komunikovat s libovolným jiným komunikátorem nebo se základnou ornitologa.

Ornitolog vás nyní žádá o pomoc s návrhem algoritmů pro komunikaci. Žádá, aby mu byla na základnu doručena informace o čase každého zahájení a ukončení zpěvové aktivity ptáka spolu s informací o souřadnicích ptáka. Nelze bohužel dopředu odhadnout, kdy se pták rozhodne zpívat. Pták může být zrovna mimo dosah nejen základny, ale i ostatních komunikátorů. Přesto je třeba v konečném čase informaci doručit, nesmí se ztratit. Využít lze faktu, že ptáci nejsou samotáři a rádi se druží (tj. čas od času lze komunikovat minimálně s jiným komunikátorem, lépe se základnou ornitologa).

Poznámka: Jedná se o oportunistickou ad-hoc síť, v okamžiku odesílání zprávy nemusí být vůbec cílová stanice v dosahu sítě. Přesto bude zpráva směrována a v konečném čase po připojení cílového uzlu i doručena.

Dosah vysílače je 20 metrů.
Vysílač je schopen v kterýkoliv okamžik začít vysílat.
ID komunikátoru má velikost 1 byte (tato hodnota bude shodná s číslem ptáka)
Informace ze senzorů (zahájení či ukončení zpěvu) má délku 8 bytů.
Informace o souřadnicích má 4 byty (2 byty (signed short) pro x + 2 byty pro y)
Informace o časovém razítku má také 4 byty (unsigned int)
Prostředí budeme simulovat jako 2-D plochu se souřadnicemi x a y v intervalu (-500,500), souřadnice jsou vždy celé číslo.
Pták se může nacházet kdekoliv ve čtverci 999×999 metrů (se souřadnicemi v povoleném rozsahu).
Základna ornitologa má souřadnice (0,0). Protože každý komunikátor zná svoji polohu, ví zároveň, zda se nachází v dosahu základny.
Základna ornitologa nemá omezenou energii na svůj provoz.
Základna umí zprávy přijímat i odesílat (potvrzení).
Mikropočítač má paměť, do které lze uložit 100 zpráv (vlastních i od ostatních). Zpráva může být jakkoliv dlouhá, pozor však na ztráty vlivem (pravidelné) chybovosti.
Mikropočítač rozpozná přítomnost jiného komunikátoru pouze tehdy, pokud jiný komunikátor vysílá.
Předpokládá se komunikace pomocí alohy, tj. během vysílání je vlastní přijímač vypnutý a odesílatel nepozná, zda nedošlo ke kolizi s jiným komunikátorem a zda nenastala chyba při přenosu.
Pro jednoduchost se předpokládá taktovaná aloha s taktem 1 sekunda, zpráva je odvysílána během jedné sekundy.
Příjem i vysílání jsou všesměrové.
Kolize nastane při současném příjmu (ve stejné sekundě) alespoň dvou zpráv od vysílačů vzdálených maximálně 20 metrů (včetně) od přijímače. Při kolizi není doručena žádná zpráva, a to ani informace o tom, že někdo vysílal.
Simulační čas bude v sekundách (např. Hold(1) čeká 1 sekundu simulačního času).
Chybovost komunikační linky lze simulovat změnou hodnoty každého tisícího bitu. Zpráva obsahující chybu není doručena (neřešte žádné kontrolní součty). Není doručena ani informace o tom, že někdo vysílal.

*** POZOR, NOVINKA ***

Ornitologa bude sponzorovat firma NuclearPower™ Batteries Ltd., která dodá miniaturní baterie s dlouhou životností. Tím odpadá problém malé kapacity baterie a jejího dobíjení. Nyní lze tedy vysílat neomezenou dobu bez nutnosti dobíjet baterii.

Navrhněte jakýkoliv (funkční) algoritmus pro přenos zprávy na základnu ornitologa. Ověřte tento algoritmus pomocí výukového systému na SHO.

Simulace končí s posledním záznamem v simulačních datech (viz níže).

Zjistěte hodnotu Tmax, kterou lze popsat takto:

v okamžiku Tmax nastala alespoň jedna událost (zahájení či ukončení zpěvové aktivity)
všechny jedinečné události do času Tmax (včetně) byly do konce simulace doručeny na základnu ornitologa

Jinak řečeno, Tmax je doba odpovídající časovému razítku vzniku nejmladší jedinečné informace po skončení simulace, přičemž všechny informace s časovým razítkem starším než je Tmax byly doručeny.

Hodnota Tmax bude zřejmě silně závislá na navrženém algoritmu. Aby byl algoritmus shledán funkčním, musí být Tmax >= délka_simulace / 2.

Spočítejte:

celkový počet událostí (do okamžiku Tmax), které je třeba ohlásit (zahájení a ukončení zpěvové aktivity)
množství jedinečných zpráv předaných na základnu ornitologa, které mají časové razítko menší (nebo rovno) než je okamžik Tmax (mělo by vyjít stejné číslo jako je počet událostí)
minimální, průměrné a maximální množství přenesených bytů mezi vysílačem komunikátoru 0 a přijímači ostatních komunikátorů (do okamžiku Tmax)

Sestavte log přehledně popisující putování jakékoliv jedné jedinečné informace od ptáka k základně ornitologa (s časovou informací).

Výsledky uveďte ve zprávě, kterou odevzdáte ve formátu PDF. Zpráva by měla kromě výše uvedeného obsahovat i popis Vašeho algoritmu a závěr, ve kterém algoritmus a jeho simulaci zhodnotíte.

využijte výukový systém SHO
vybraný algoritmus musí respektovat aktuální topologii ad-hoc sítě a její vlastnosti (včetně simulace ztráty zpráv)
algoritmus musí být funkční a jeho průběh musí být názorně vizualizován
algoritmus musí být spuštěn se zadanými simulačními daty (viz níže)
algoritmus musí být schopen zpracovat jakákoliv jiná podobná simulační data

Simulační data popisují souřadnice každého ptáka v každé sekundě a všechny “zpěvné” události. Data jsou kvůli úspoře místa uložena v poměrně divokém tvaru, doporučuji využít pro jejich načítání přiložený kus zdrojového kódu. Dále je možno využít program pro vizualizaci pohybu ptactva (viz generátor dat).

Poznámka: Simulační data slouží pouze k simulaci chování ptáků, nikoliv k věštění, jak se bude který pták chovat.

simulační data

Data jsou ke stažení zde: ptaci.zip (9890079 bytu, SHA1=56351b3fa54ce926cf9f901ba75e44ffa81d9b29)

ptaci.h

Můžete využít následující soubor, který vám vyřeší čtení simulačních dat: ptaci.h
Stačí vložit do hlavni.cc na začátek řádek: #include “ptaci.h” . Potom můžete využít funkce zjisti_delku_simulace() a nacti_dalsi_zaznamy():

unsigned long zjisti_delku_simulace() vrátí dobu simulace, pro kterou existují simulační data.

int nacti_dalsi_zaznamy() načte záznamy pro další sekundu a uloží je do polí

int ptaci_x[POCETPTAKU]
int ptaci_y[POCETPTAKU]
int ptaci_udalost[POCETPTAKU] (1=udalost, 0=není událost)

Návratová hodnota 1 hlásí úspěch, 0=konec simulace.

template pro úlohu

Můžete využít šablonu, která je upravenou verzí výukového SHO a obsahuje načítání dat pomocí funkcí v souboru ptaci.h. Ke stažení je zde: ptaci_template.tar.bz2

generátor simulačních dat a vizualizátor

K dispozici je i zdrojový kód generátoru simulačních dat, který jsem použil. Součástí je i program zobraz pro vizualizaci pohybu ptáků, doporučuji pro shlédnutí (vyžaduje OpenGL). Ovládá se mezerníkem, backspacem, enterem a klávesou esc.