Vi betraktar problemet med topologiigenkänning i trådlösa (radio) nätverk som modellerade som oriktade grafer. Topologiigenkänning är en grundläggande uppgift där varje nod i nätverket måste mata ut en karta över den underliggande grafen, d.v.s. en isomorfisk kopia av den, och placera sig i denna karta. I trådlösa nätverk kommunicerar noderna i synkrona rundor. I varje omgång kan en nod antingen sända ett budskap till alla sina grannar, eller hålla tyst och lyssna. I det mottagande slutet, en nod v hör ett meddelande från en granne w i en given runda, om v lyssnar i denna runda, och om w är dess enda granne som sänder i denna runda. Noder har etiketter som är (inte nödvändigtvis olika) binära strängar. Längden på ett märkningssystem är den största längden på en etikett. Vi koncentrerar oss på trådlösa nätverk modellerade av träd, och vi undersöker två problem. • Vad är det kortaste märkningsschemat som tillåter topologiigenkänning i alla trådlösa trädnätverk med diameter D och maximal grad? • Vad är den snabbaste topologiigenkänningsalgoritmen som fungerar för alla trådlösa trädnätverk av diameter D och maximal grad, med hjälp av ett så kort märkningssystem? Vi är intresserade av deterministiska topologiigenkänningsalgoritmer. För det första problemet, visar vi att den minsta längden av ett märkningssystem som tillåter topologi erkännande i alla träd av maximal grad  på ≥ 3 är  på (logglogg  på). För sådana korta scheman, som används av en algoritm som arbetar för klassen av träd med diametern D ≥ 4 och maximal grad  på ≥ 3, visar vi nästan matchande gränser på tiden för topologiigenkänning: en övre gräns för O (D) och en nedre gräns för  och en lägre gräns (D) för varje konstant < 1. Våra övre gränser bevisas genom att konstruera en topologiigenkänningsalgoritm med hjälp av ett märkningsschema för längd O(log log  på) och med tid O(D). Våra nedre gränser bevisas genom att bygga en klass av träd för vilka någon topologiigenkänningsalgoritm måste använda ett märkningsschema av längd minst  och en klass av träd för vilka någon topologiigenkänningsalgoritm med hjälp av ett märkningsschema av längd O(logglogglogg) måste använda tid minst  och åtminstone  och (D) på något träd i denna klass.
I REF ansåg författarna problemet med topologiigenkänning i trådlösa träd utan kollisionsdetektering.
Short Labeling Schemes for Topology Recognition in Wireless Tree Networks
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science']}