Geografisk rutt
Geografisk routing (även kallad georouting eller positionsbaserad routing ) är en routingprincip som bygger på geografisk positionsinformation . Det föreslås främst för trådlösa nätverk och bygger på tanken att källan skickar ett meddelande till destinationens geografiska plats istället för att använda nätverksadressen . Inom området för paketradionät föreslogs idén att använda positionsinformation för routing först på 1980-talet för sammankopplingsnät. Geografisk routing kräver att varje nod kan bestämma sin egen plats och att källan är medveten om platsen för destinationen. Med denna information kan ett meddelande dirigeras till destinationen utan kunskap om nätverkstopologin eller en tidigare ruttupptäckt.
Närmar sig
Det finns olika tillvägagångssätt, såsom enkelvägs-, flervägs- och översvämningsbaserade strategier (se för en undersökning). De flesta enkelvägsstrategier bygger på två tekniker: girig vidarebefordran och ansiktsdirigering . Girig vidarebefordran försöker föra meddelandet närmare destinationen i varje steg med endast lokal information. Varje nod vidarebefordrar alltså meddelandet till den granne som är mest lämplig ur lokal synvinkel. Den mest lämpliga grannen kan vara den som minimerar avståndet till resmålet i varje steg (Girig). Alternativt kan man överväga en annan föreställning om framsteg, nämligen det projicerade avståndet på käll-destinationslinjen (MFR, NFP), eller den minsta vinkeln mellan granne och destination (Compass Routing). Alla dessa strategier är inte loop-fria, dvs ett meddelande kan cirkulera bland noder i en viss konstellation. Det är känt att den grundläggande giriga strategin och MFR är loopfria, medan NFP och Compass Routing inte är det.
Girig spedition kan leda in i en återvändsgränd, där det inte finns någon granne närmare destinationen. Sedan hjälper ansiktsdirigering att återhämta sig från den situationen och hitta en väg till en annan nod, där girig vidarebefordran kan återupptas. En återställningsstrategi som ansiktsdirigering är nödvändig för att säkerställa att ett meddelande kan levereras till destinationen. Kombinationen av girig vidarebefordran och ansiktsdirigering föreslogs först 1999 under namnet GFG (Greedy-Face-Greedy). Det garanterar leverans i den så kallade unit disk graph network modellen. Olika varianter, som föreslogs senare, även för icke-enhetsskivor, är baserade på principerna för GFG.
Ansiktsdirigering beror på en plan subgraf i allmänhet; distribuerad planarisering är dock svårt för riktiga trådlösa sensornätverk och skalas inte bra till 3D-miljöer.
Girig inbäddning
Även om det ursprungligen utvecklades som ett routingschema som använder de fysiska positionerna för varje nod, har geografiska routingalgoritmer också tillämpats på nätverk där varje nod är associerad med en punkt i ett virtuellt utrymme, utan samband med dess fysiska position. Processen att hitta en uppsättning virtuella positioner för noderna i ett nätverk så att geografisk routing med dessa positioner garanterat kommer att lyckas kallas girig inbäddning .