Supervisor: Kaisa Sere
Download 298.62 Kb.
|
- Navigate this page:
- 8.1 Summary
- 8.1.2Connecting to the Internet
8CONCLUSIONSEvery graph shows that at speeds from 0 to 3 m/s the performance worsen, but at 5 m/s every curve shows improving results up until 8 m/s. It is possible that 5 m/s is a speed at which it is less likely that both the first and retry RQM fails to find the destination. In other words, a node might have connected to new neighbors after the first RQM was sent. Although the MAC layer of the simulator is not realistic, it is not unrealistic to assume that the MAC layer could provide information about neighbors, needed to omit periodical hello messages and updates. If periodical hello messages were used, this simulation would have worse results. Although good results were obtained with respect to the delay characteristic, even smaller delays could be obtained with active route aging and deletion. It is hard to estimate when a route is not functional anymore (without testing the route) and should be deleted so that these routes are not used to answer route queries. There is not a lot of information to base accurate estimates on other than time. There will always be a maximum speed that a mobile node can travel and still stay connected to an ad hoc network. If the delay of the route query is greater than the time a node stays in a neighborhood then the node will never be able to communicate because answers to queries will always be sent to the wrong place. If further test show that TRP is effective and scalable then multicasting will also be implemented. This issue is, however, completely open at the moment. 8.1 Summary8.1.1ScalabilityScalability issues have to be considered especially carefully in ad hoc protocols. Not only will the MAC protocol be under higher strain when there are more nodes in the neighborhood but the network protocol also has to be made capable of handling large amounts of nodes. As the data rate in wireless networks is not yet at the same level as that for fixed networks, we have to take care that these are not flooded with unnecessary control messages while at the same time the need for frequent use of these is greater than in fixed networks due to mobility. As for MAC protocols the medium access method will play a large role in providing better scalability. When contention based protocols are used and the neighborhood of a node grows it is clear that throughput will degrade. It is also clear that at some point the competition for the medium will be so great that no quality of service can be guaranteed. This calls for approaches were nodes can transmit without contention in so-called collision-free protocols. If these are the MAC protocol of the future will be determined, among other things, by how effectively the spreading codes can be distributed. The largest factor behind the Internet’s great scalability is aggregation. The whole Internet is partitioned into autonomous systems (AS) and AS are partitioned into networks. Only the information relevant to finding a host in the right network is propagated outside the network and information relevant to finding the right network is propagated outside the AS (to the backbone). It is harder to provide such aggregation in ad hoc networks, but not impossible (see hierarchical protocols 3.3). If no aggregation methods are used, there will always be a risk that control messages will start consuming so much bandwidth that the network will become unusable. As we saw in chapter 2 (MARCH) and 4 (TCP-BuS) good results were obtained by letting protocols at different layers interact and access information that can make ad hoc networks more scalable. Consequently many believe that this is the way to continue the evolution of ad hoc protocols as almost no negative sides can be found in this approach. It is clear that the complexity of the protocol stack will increase as more communication between modules must occur. This is potentially more error-prone than conventional “isolated” layering as knowledge of different software modules must be possessed. This “vertical” communication between protocols of different layers is not the only combinatory approach. The active networking approach delivers “horizontal” communication between different network protocols on the same layer. This is because, in the philosophy of active networking it is believed that different protocols should be used for different types of traffic having differing constraints This might well be a advantageous approach as long as the routing logic remains manageable. We see great security threats with reprogrammable routing logic as flexibility often implies the possibility of abuse. Proactive protocols for fixed networks do not work well for ad hoc networks. The bandwidth is not sufficient for such protocols and especially distance vector protocols would converge to slowly. Ad hoc distance vector and link state protocols have been developed but it is not clear which class is better. Traffic requiring low initial delay should use proactive protocols and on the other hand traffic requiring that as much of the bandwidth as possible is available for data messages should use reactive protocols16. Active networking could solve this dilemma. For instance, in active networking it is possible to have a proactive backbone and let nodes connect to this backbone and find routes reactively. 8.1.2Connecting to the InternetWhen connecting an ad hoc network to the Internet there are several things that have to be sorted out. It is not enough to connect the mobile node to an intra-ad hoc network and provide an address for that particular network if other nodes on the Internet should be able to contact the node. Additionally, we assume here that the node can roam between subnets. The mobile node can be addressed by any node on the Internet if there is another fixed node (home agent) on the Internet that is constantly informed about the mobile node’s whereabouts. It is also this fixed node that redirects the request to find the mobile node. At the moment this is implemented with Mobile IP, but if textual IP addresses are used, another lookup must also be made, namely at the DNS server in order to translate the text address to numeral. As we mentioned in chapter 4 this could be simplified by removing Mobile IP and letting the DNS server point to the right ad hoc network at all time. This could for instance be done by letting the mobile node first be assigned an address (through propagating DHCP advertisements) and then informing the dynamic DNS about the network address change. This would remove the need for an dedicated Mobile IP home agent and reduce the level of indirection to only one lookup. 1 INTRODUKTION Ad hoc trådlösa nätverk är datornätverk med temporär infrastruktur. De kan organisera denna infrastruktur efter behov när två eller flera datorer befinner sig i samma geografiska område. Datorerna som oftast är handhållna eller bärbara mobildatorer måste kunna känna av varandra och organisera ett optimalt nätverk för stunden. Länkarna som bygger upp infrastrukturen för dataöverföring mellan datorerna kan vara radiovågor eller infrarött ljus. Förutom att upptäcka andra datorer måste nätverket även göra det möjligt för datorer som inte är inom varandras radiovågors räckvidd att kunna kommunicera indirekt. Detta uppnås genom att låta mellanliggande datorer vidarebefordra (eng. forward) meddelanden mellan sådana datorer som inte kan kommunicera direkt. P.g.a. att datorerna är mobila måste varje dator som deltar i framföring vara underrättad om hur nätverkets infrastruktur (topologin) ser ut för tillfället. Detta sker med ett ruttningsprotokoll (eng. routing protocol) som skickar s.k. styrmeddelanden (eng. control messages) för att upptäcka topologin. Varje dator, eller värd som man också brukar benämna dem, kan kommunicera direkt med andra värdar som finns inom räckhåll för deras radiovågor. Dessa värdar kallas för grannar. Traverseringen av en sådan länk kallas för ett ”hopp” på en rutt mellan två värdar. Denna typ av vidarebefordring förutsätter att varje värd i ett ad hoc-nätverk också fungerar som en router och är alltså beredd att framföra paket som är någon annans. En del protokoll tillåter värdar med svaga batterier att delta selektivt i vidarebefordring. 1.1 Problembeskrivning I ad hoc-nätverk är det ytterst viktigt att hålla meddelandekomplexiteten (antalet kontrollmeddelanden) låg, inte bara för att spara bandbredd för användarnas datameddelanden men också för att minska på risken att det sker kollisioner på medieåtkomstnivå (se avsnitt 1.2). Detta skall ske på samma gång som man löser ruttningsproblemet, d.v.s. hur man tillhandahåller rutter åt värdar. I denna pro gradu-avhandling undersöks befintliga protokoll som alla löser dessa problem på olika sätt. Vårt mål var att få en djup insikt i vad det betyder att specificera ett ad hoc nätverksprotokoll och förutom litteraturstudien har vi utvecklat ett protokoll kallat ”Tree Routing Protocol” (TRP, se kapitel 2). Målet med ad hoc-nätverk är att tillhandahålla nätverksaccess där två eller flera datoranvändare strövar. Denna text är ett sammandrag som behandlar mjukvara som gör det möjligt för dylika ad hoc-nätverk att fungera. 1.2 Medieåtkomst När man använder sig av radiosignaler för dataöverföring måste det ske på ett kontrollerat sätt eftersom inte vilket frekvensband som helst kan användas, utan det måste delas av värdar i ett nätverk. Problemet att lösa blir då – hur tillhandahålla turer för datatransmission så att dessa inte kolliderar. I de flesta nätverk som kan indelas enligt OSI-modellen använder ett medium åtkomstprotokoll (eng. Medium Access Control, MAC17 protocol) för att avgöra hur sändningar skall skeduleras. MAC-protokoll kan vara distribuerade eller centraliserade. Bluetooth t.ex. är centraliserat med hjälp av en ”mästare” (eng. master) som håller reda på slavars sändningsturer och utdelar dessa i tur och ordning. IEEE 802.11 [IEEE99] är ett annat MAC-protokoll som använder sig av ett distribuerat kontrollsystem då värdarna är inställda i ad hoc-läge. I 802.11 tävlar värdar om sändningsturer och den som hinner först får skicka. Om två eller flera värdar skickar på en gång kommer en på måfå vald värd att skicka först genom att båda ”lottar” ut en tid de väntar innan de prövar på nytt. 1.3 Nätverksnivån Som i klassiska, statiska nätverk hör ruttningsprotokoll i ad hoc-nätverk till OSI-modellens tredje nivå, den s.k. nätverksnivån. Ett protokoll på denna nivå utför ruttning (upptäcker topologin) och vidarebefordring. Typen av ruttningsprotokoll avgör hur stor del av topologin som måste vara känd för var och av värdarna. Det finns två huvudgrupper av ruttningsprotokoll i ad hoc-nätverk – dessa är proaktiva och reaktiva protokoll. De proaktiva protokollen fungerar enligt samma princip som protokollen i statiska nätverk – varje värd håller reda på rutter till varje annan värd hela tiden. Detta betyder att det kommer att skickas en hel del onödiga styrmeddelanden om inte alla rutter används. Detta har man försökt åtgärda i reaktiva protokoll där man endast upprätthåller rutter till sådana värdar man aktivt skickar packet. Utdata av ruttningsfasen kan sedan användas för att framföra paket. Protokoll kan även indelas enligt den klassiska klassificeringen av ”distance vector” (DV) och ”link state” (LS) protokoll. Protokoll av LS-typ kan inte vara reaktiva. Vi skall nu ta upp ett existerande protokoll. Det är ett DV, reaktivt protokoll kallat ”Ad hoc On-Demand Distance Vector” (AODV). 1.3.1 Ad hoc on-demand distance vector protocol (AODV). En värd (källa) i ett AODV-nätverk [Perkins+99] dränker hela nätverket med styrmeddelanden kallade ”Route Requests” (RREQ) när källan inte känner till en rutt till den värd den söker efter (destination). Dränkningen fungerar genom att källan sänder ett RREQ åt sina grannar och därefter gör grannens grannar det samma o.s.v. Detta betyder att RREQ-meddelandet kommer fram till destinationen såvida den finns i nätverket. Varje mellanliggande värd som framför RREQ-meddelanden noterar vem som skickade den till sig och får då en pekare ”bakåt” mot den värd som är nästa hopp mot källan, d.v.s. den mellanliggande värd som kan föra ett meddelande mot källan. Detta behövs när svaret på RREQen skall ges med en s.k. ”Route Reply” (RREP). När RREQen når fram till destinationen eller en mellanliggande värd med tillräckligt ny rutt (nästa hopp) till destination kan den värden svara med ett RREP och specificera att den kan användas som nästa hopp till destinationen. Då en destination skickar ett svar på en RREQ med RREP genererar den ett sekvensnummer som den lägger i en RREP. Därefter skickar den denna RREP tillbaka till källan längs den rutt som sattes upp då RREQ traverserade mot destinationen. Varje mellanliggande värd som får RREP att vidarebefordra noterar detta sekvensnummer, vilket kommer att läggas i kommande RREQ. När sedan mellanliggande värdar svarar på dessa RREQ-meddelanden måste sekvensnumret i deras ruttabell vara åtminstone lika stort som det som finns i RREQ för att ruttens skall betraktas som tillräckligt ny. Det kan ju hända att två meddelanden har traverserat två olika rutter och i sådant fall får en mellanliggande värd duplikat. Dessa känns igen genom dränknings-ID (ett sekvensnummer) och källans IP-adress. Värdar bör också ignorera meddelanden som har traverserat längre rutter genom att kontrollera antalet hopp som paketet har traverserat (anges i huvuddelen av paketet). På detta sätt kan meddelandekomplexiteten reduceras. Ruttabellerna innehåller poster bestående av destination, nästa hopp mot destinationen och längden (antalet hopp) till destinationen. Dessa rutter har också en ålder associerad som säger när en rutt skall raderas p.g.a. den stora sannolikheten att denna rutt redan är sönder (värden har flyttat utom radio räckhåll) p.g.a. mobilitet. Detta motverkar utbredning av rutter som inte längre finns till. Varje gång en rutt används sätts dennes ålder till noll. För att säkerställa att alla grannar ännu faktiskt är grannar skickar värdar s.k. ”hello- meddelanden” till sina grannar inom vissa intervall. Om ett hello-meddelande inte fås efter vissa specificerade sekunder kommer en värd att deklarera en granne som f.d. granne. I detta fall kan aktiva grannar informeras om detta med ett speciellt RREP-meddelande. 1.3 Kommunikation mellan ändpunkter Liksom ruttningsprotokoll, måste också transportprotokoll (OSI nivå 4) göras om för att vara effektivare. TCP som används som Internets transportprotokoll, fungerar inte bra omodifierat i ad hoc-nätverk. Detta beror på att TCP har en funktion som förebygger trafikstockning, vilken försäkrar att sändaren inte sänder för mycket paket så att mottagaren inte hinner processera dem. Detta märks när inga kvitteringsmeddelanden fås som i sin tur gör att sändaren sänder sina paket långsammare. När en radiolänk bryts kommer inte heller kvitteringsmeddelanden fram, vilket kommer att medföra att sändarens takt görs långsammare även om en ny rutt är funnen. Detta kommer hindra optimal användning av nätet. Transportprotokoll associeras ofta med kommunikation mellan ändpunkter i statiska nätverk, d.v.s. mellanliggande routrar har ingen transportnivå. I ad hoc-nätverk måste denna modell ändras och låta mellanliggande routrar (vanliga värdar) delta i transportprotokollet. T.ex. sker detta genom att skicka kvittering vid varje hopp (mellan mellanliggande värdar) istället för att destinationen kvitterar källan för varje paket. På detta sätt kan källor informeras explicit snabbare än om man låter en väntetid löpa ut hos källan. 2 TREE ROUTING PROTOCOL (TRP) TRP är ett protokoll som utvecklades för denna pro gradu-avhandling i pedagogiskt syfte för att förstå vad det betyder att utveckla ett optimerat ruttningsprotokoll. TRP har också ett sätt att minimera meddelandekomplexiteten. Denna metod går ut på att delvis känna till topologin (delvis proaktivt) och på så sätt göra intelligentare vidarebefordringsbeslut för ”Route Query”-meddelandena (jfr. RREQ i AODV). Detta beslutsfattningssystem baserar sig på att ett nätverk representerad av en graf också kan ses som ett träd om vissa länkar (bågar) tas bort som figur 2–1 visar. 
Fig. 2–1: Olika vyer av nätverket Ett träd uppkommer när en värd startar upp och märker att den inte har några grannar. Då deklarerar den (roten av trädet) ett träd-ID som är det samma som dess ID. Värdar (barn) som därefter kommer nära trädet ansluter sig till det, eller mera exakt till en annan värd (föräldern) i trädet som har den kortaste rutten till roten. Varje värd som ansluter sig kopierar detta trädID vilket senare kan behövas för att identifiera olika träd. Det är då möjligt att värden har kontakt med andra värdar i trädet – dessa länkar kallas då ”extralänkar”. I figur 2-1 är de streckade linjerna extralänkar. Extralänkarna kopplas inte helt bort utan de används vid vidarebefordring av datameddelanden. Varje värd som kopplar sig till ett träd skickar ett uppdateringsmeddelande till föräldern och föräldern adderar sig själv till meddelandet och skickar det till sin förälder. Detta ackumulerande meddelande växer för varje hopp uppåt i trädet och när det kommer fram till roten kommer den att känna till alla värdar i trädet. Dessutom kommer alla värdar att känna till sina barn. I figur 2-1 betyder det att rot 1 känner till alla värdar och att t.ex. värd 2 känner till värd 4. Det att värdar ansluter sig till föräldrar med korta rutter till roten betyder att de kända rutterna är så korta som möjligt. För att känna till andra värdars distans från roten skickas hello-meddelanden när en värds MAC-information indikerar en ändring (nya grannar eller barn). Mottagna hello-meddelande jämförs och en värd ansluter sig till grannen med minst hopp till roten. TRP är speciellt på det sättet att uppdaterings- och hello-meddelanden endast skickas då en ändring i värdens information om sina grannar (indikerat i MAC) eller barn (indikerat i uppdateringsmeddelandet från dess barn) sker. För att minska på storleken på uppdateringsmeddelandet kan man skicka inkrementella meddelanden som endast innehåller ändringen. När två barnvärdar som inte hör till samma träd kommer i kontakt med varandra kan de bilda en s.k. interlänk mellan de två träden. På detta sätt kan värdar i två eller flera olika träd kommunicera med varandra. Om en av värdarna (eller båda) är rot så skall denna inkludera sitt träd med det andra trädet, d.v.s. den ena roten blir ett barn av barnvärden i det andra trädet. Detta är ett sätt att maximera det förstorade trädets rots vetskap om det nya trädet. Hade det bildats en interlänk mellan träden så skulle de två rötterna endast känt till sina egna träd. Figur 2–2 visar en interlänk mellan två olika träd. 
När en värds relativa hastighet är större än de andras kommer den att bryta länkar till sina gamla grannar och förbinda sig till en ny beroende på informationen som fås i hello-meddelanden. 2.1 Ruttupptäckt När en källvärd inte har en rutt till en destinationsvärd kommer den att skicka ett s.k. ”Route Query Message-meddelande” (RQM) till grannar som finns kopplade med extralänkar, interlänkar eller förälderrelation. Dessutom skall RQM skickas till barn som är subrötter för subträd med extralänkar, interlänkar eller innehåller destinationsvärden. RQM-meddelandet skickas inte till sådana barn vars subträd är stängt. I figur 2-3 visar vi vad vi menar med ett stängt subträd. Där är subträdet bestående av värdarna 8, 9 och 0 stängt, ty det har ingen extralänk eller interlänk. Om subträdet dessutom inte innehåller den sökta värden så är det ingen nytta med att vidarebefordra RQM dit. Det är just detta som är den bärande idén bakom TRP, d.v.s. att man kan minska meddelandekomplexiteten genom att tillhandahålla värdar med så mycket information att värdar kan göra intelligenta vidarebefordringsbeslut när man upptäcker rutter. 
Vi tar som exempel nätverket i figur 2–3 och beskriver hur rutter upptäcks med TRP. Om värd 5 vill hitta värd 4 så händer följande: Ett RQM skickas till 3:an som i sin tur skickar det till 6:an för att den har en extralänk samt till 2:an som är dess förälder. Meddelandet som skickades till 2:an kommer att komma fram till rot 1 som känner till en rutt till värd 4 och kan därför kvittera RQMet och skicka det till 5:an. Detta är möjligt för nästa hopps pekare sätts upp på samma sätt som i AODV. När 6:an får samma RQM från 3:an kommer den också att kunna kvittera ty 4:an är dess granne och känner därmed till rutten. För varje hopp som ett RQM traverserar kommer en räknare att höjas med ett och dessutom då en mellanliggande värd kvitterar ett RQM måste den addera den kvarstående rutten till destinationen. Så värd nummer 3 kommer att få två kvitterade RQM tillbaka, en med rutt av längden 4 och en med längden 2. I detta skede raderar värd 3 det meddelande med längre rutt vilket minskar meddelandekomplexiteten. Antalet hopp som registreras i meddelanden kommer att kunna användas som medel att förebygga meddelandecykler. Om en värd registrerar ett RQM med en visst antal hopp traverserade och om den får detta RQM tillbaka efter att det har traverserat en cykel så kommer RQMet att ha ett större antal traverserade hopp. En värd som märker detta kan radera meddelandet. Figur 2-3 är mycket simplifierad. Det är möjligt att lövnoder i trädet skulle ha stora subträd som inte behöver dränkas med RQM-meddelanden och då skulle TRPs inbesparing av meddelandekomplexiteten vara stor. 2.2 Framföring av datameddelanden När ett RQM har traverserat fram och tillbaka mellan en källa och en upphittad destination kan källan börja skicka datameddelanden som följer samma rutt av nästa hopps pekare vilken nyss sattes upp av RQM-meddelandet. Eftersom RQMen inte kan gå i cykler, kan inte heller datameddelanden göra det. Om en värd håller på att föra fram ett datameddelande, men just då märker att rutten har bryts (nästa hopps värden har flyttat utom radioräckhåll), så skall denna värd informera källan om detta. Källan skall då radera den gamla rutten och upptäcka en ny rutt för destinationen. Detta gör den upptäckande värden m.h.a. ett ”destinationen oåtkomlig”-meddelande som också får varje mellanliggande värd på rutten att radera deras nästa hopp för denna destination. 3 SIMULERING Simulatorn som TRP-simuleringarna utfördes på är skriven av oss i programmeringsspråket C. Detta gjordes för operativsystemet Linux och körningarna gjordes på en dator med följande specifikation: processorn var en AMD Athlon med en klockfrekvens på 1GHz och 256 MB RAM. Simulatorn har en nivå struktur som riktiga protokoll. Vi antar att MAC nivån kan ange vilka är en värds grannar och endast det. Nätverksnivån simuleras genom att ha olika processer med angivna UDP portar som de lyssnar på. Portnummret är det samma som processens (värdens) ID nummer. Värdarna i simulatorn kan alltså endast kommunicera genom UDP meddelanden vilket också gäller verkliga ruttningsprotokoll. När simulationen startas väljer de 25 värdarna på måfå en plats i ett 300mx300m stort koordinatsystem (Fig. 3-4). Därefter börjar de börjar de mobilisera med en fart som är angiven för en körning. Riktningen väljs också på måfå antingen i riktning med någondera axlarna eller diagonalt. Samma sker då en värd kommer till gränsen av koordinatsystemet. 
Fig. 3-4: 25 värdar på en 300x300 meters area . De resultat vi väntar oss att få ur simulatorn är de följande: andelen mottagna datameddelanden som kommer fram till destinationen, antalet RQM-meddelanden som måste skickas för att upprätthålla rutter, latenstiden för upptäckning av rutter och antalet framförda styrmeddelanden. Under de 30 sekunder som en körning omspänner, skickar värdarna på måfå datameddelanden till olika värdar med frekvensen 1med./sekund. För varje hastighet gjorde 10 körningar vilkas medeltal är visade i figurerna 3-5 till 3-7. I figurerna finns även standardavvikelsen för körningarna. Download 298.62 Kb. Share with your friends:
|