Routing är ett utmanande problem för trådlösa ad hoc-nätverk, särskilt när noderna är mobila och sprids så brett att i de flesta fall flera humle behövs för att skicka ett meddelande från en nod till en annan. I själva verket är det känt att alla online routing protokoll har en dålig prestanda i värsta fall, i en mening att det finns en fördelning av noder resulterar i dålig routing vägar för det protokollet, även om noderna vet sina geografiska positioner och den geografiska positionen för destinationen för ett meddelande är känd. Anledningen till detta är att radiohål i ad hoc-nätverket kan kräva meddelanden för att ta långa omvägar för att komma till en destination, som är svåra att hitta på nätet. I detta dokument utgår vi ifrån att det trådlösa ad hoc-nätet i begränsad utsträckning kan använda sig av långdistansförbindelser som tillhandahålls av en global kommunikationsinfrastruktur som en mobil infrastruktur eller en satellit för att beräkna en abstraktion av det trådlösa ad hoc-nätet som gör det möjligt att skicka meddelanden längs närmast kortaste vägar i ad hoc-nätet. Vi presenterar distribuerade algoritmer som beräknar en abstraktion av ad hoc-nätverket i O(log 2 n) tid med hjälp av långdistanslänkar, vilket resulterar i c-konkurrenskraftiga routing vägar mellan två noder av ad hoc-nätverket för vissa konstant c om konvexa skrov av radiohål inte skär. Vi visar också att den lagring som behövs för abstraktionen bara beror på antalet och storleken på radiohålen i det trådlösa ad hoc-nätverket och är oberoende av antalet noder, och denna information måste bara vara känd för några noder för routing att fungera. ACM ämnesklassificering C.2.4 distribuerade system
Den lösning som föreslås i REF är att beräkna ett overlay-nät där hål representeras av deras konvexa skrov.
Competitive Routing in Hybrid Communication Networks
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science']}