Energi är ofta den mest begränsade resursen för batteridrivna trådlösa enheter, och större delen av energin används ofta för transceiveranvändning (dvs. överföring och mottagande paket) snarare än beräkning. I den här artikeln studerar vi de grundläggande problemens energikomplexitet i flera modeller av trådlösa radionät. Det visar sig att energi komplexitet är mycket känslig för om enheterna kan generera slumpmässiga bitar och deras förmåga att upptäcka kollisioner. Vi överväger fyra modeller för kollisionsdetektering: Stark-CD (där sändare och lyssnare upptäcker kollisioner), Sender-CD (där endast sändare upptäcker kollisioner), Mottagar-CD (där endast lyssnare upptäcker kollisioner) och No-CD (där ingen upptäcker kollisioner). Uttagsbudskapet från våra resultat är ganska förvånande. För randomiserade algoritmer finns det en exponentiell klyfta mellan energikomplexiteten hos Sender-CD och Mottagar-CD: och för deterministiska algoritmer finns det en annan exponentiell klyfta i energikomplexitet, men i omvänd riktning: Exakt är den randomiserade energikomplexiteten hos Leader-Valet  och (log * n) i Sender-CD men (log(log * n)) i Mottagar-CD, där n är antalet enheter, som är okänt för enheterna i början; den deterministiska komplexiteten i Leader-Valet är  och N i Mottagar-CD, men  till (log log log N ) i Sender-CD, där N är storleken på ID-utrymmet. Det finns en kompromiss mellan tid och energi. Vi tillhandahåller en ny övre gräns på tid-energiavräkningskurvan för randomiserade algoritmer. En kritisk komponent i denna algoritm är en ny deterministisk Leader Valalgoritm för täta instanser, när n =  till (N ), med omvänd Ackermann energi komplexitet. - CD. Varje sändare och lyssnare får en av tre signaler: λ S (tystnad, om inga enheter överför), λ N (buller, om ≥ 2 enheter sänder) eller ett meddelande m  på M (om en enhet sänder). Avsändare-CD. (Ofta kallas "No-CD" [27]) Varje sändare och lyssnare får en av två signaler: λ S (noll eller ≥ 2 enheter sänder), eller ett meddelande m  på M (om en enhet sänder). Observera att Sender-CD-modellen inte har någon explicit kollisionsdetektering men fortfarande tillåter smygande kollisionsdetektering: om en avsändare hör λ S, kan det sluta sig att det fanns minst en annan avsändare. Mottagare-CD. Sändarna får ingen signal. Varje lyssnare får en av tre signaler: λ S (tystnad, om ingen anordning överför), λ N (buller, om ≥ 2 enheter sänder) eller ett meddelande m  på M (om en enhet sänder). Inte-CD. Sändarna får ingen signal. Lyssnare får en av två signaler: λ S (noll eller ≥ 2 enheter överför) eller ett meddelande m  på M. Var och en av de fyra modellerna finns i både randomiserade och deterministiska varianter. En nyckelfråga är att bryta symmetrin. Medan randomiserade modeller lätt åstadkomma detta genom att ha enheter vända oberoende slump mynt, deterministiska modeller är beroende av att ha pre-tilldelade unika ID för att bryta symmetri. Slumpmässig modell. I den randomiserade modellen, alla n enheter börjar i exakt samma tillstånd och kan bryta symmetri genom att generera privata slumpmässiga bitar. Numret n är okänt och obundet. Den högsta tillåtna felsannolikheten för en randomiserad algoritm är högst 1/poly(n). I en misslyckad körning, enheter kan förbruka obegränsad energi och aldrig stanna [8, 28, 29]. Deterministisk modell. Alla n enheter har unika ID i intervallet Leader Val. Exakt en enhet betecknar sig själv ledaren och alla andra betecknar sig själva följare. Av tekniska skäl kräver vi att beräkningen avslutas när ledaren skickar ett meddelande medan varje följare lyssnar på kanalen. Ungefärlig räkning. I slutet av beräkningen kommer alla enheter överens om en uppskattning av nätstorleken n sådan attñ =  på (n). Folkräkning. I slutet av beräkningen, någon enhet tillkännager en lista över ID för alla enheter. Vi studerar bara detta problem i den deterministiska modellen. Lägg märke till att varje deterministisk algoritm som löser Census också kan lösa Leader Val och ungefärlig räkning med samma körtid och energikostnad. I den randomiserade modellen, visar vi att energi komplexiteten i Leader Val och ungefärlig räkning är  och (log * n) i Sender-CD och No-CD men, (log(log * n)) i Strong-CD och Mottagare-CD. De nedre gränserna gäller också för problem med tvistelösning, och detta visar att det senaste O-protokollet (log(log * n)) om lösning av tvister mellan Bender, Kopelowitz, Pettie och Young [7] är optimalt. Våra övre gränser erbjuder en tids-energi-avsättning. Se tabell 1 för energikostnaden för vår algoritm under olika drifttidsbegränsningar. För Leader Val fastställer vi matchande gränser i alla deterministiska modeller. I Strong-CD och Sender-CD, Leader Val kräver  och O (log log N ) energi även när n = 2, och Census kan lösas med O (log log N ) energi och O (N ) tid, för alla n ≤ N. Men i No-CD och mottagare-CD, energi komplexiteten av dessa problem hoppar till  på (logg N) [29]. Slutligen bevisar vi att när inmatningen är tät i ID-utrymmet, vilket betyder n = N (N ), Census faktiskt kan beräknas med endast O (α (N )) energi och O (N ) tid, även i No-CD. Enligt vår kunskap är detta första gången invers-Ackermann-typ rekursion har dykt upp i distribuerad dator. Jurdzinski m.fl. [27] studerade den deterministiska energi komplexiteten i Leader Val i Sender-CD-modellen. De bevisade att täta instanser n =  på (N ) kan lösas med O (log * N ) energi och hävdade att komplexiteten i de glesa instanserna är mellan  och ACM transaktioner på Algoritmer, Vol. -Femton, tack. Denna förordning träder i kraft den tjugonde dagen efter det att den har offentliggjorts i Europeiska unionens officiella tidning. Publiceringsdatum: oktober 2019. 49:4 Y.-J. Chang och Al. O (log ε N ). Även om den nedre gränsen är korrekt, är den algoritm som presenteras i referensen [27] inte det. 1 Den mest effektiva publicerade algoritmen använder O ( log N ) energi, även på grund av Jurdzinski et al. Detta beslut riktar sig till Konungariket Spanien. Samma författare [28] gav en minskning från slumpmässig Sender-CD Ungefärlig räkning till deterministisk Leader Val över ID utrymme N = O (log n), vilket, med hjälp av referens [30], leder till en O (logg n) energialgoritm för Ungefärliga räkning. I referens[29] gav författarna en metod för att simulera Sender-CD-protokoll i No-CD-modellen och bevisade att deterministiska No-CD Leader Val tar  och (log N ) energi. Nakano och Olarius [40] visade att n-enheter i Sender-CD-modellen kan tilldela sig olika ID i {1,...., n} med O (logga n) energi i förväntan. Nyligen, Bender et al. [7] gav en metod för kretssimulering i Strong-CD-modellen, som ledde till slumpvis ungefärlig räkning och Leader Valprotokoll med hjälp av O (log(log * n) energi och n o (1) tid. En tidigare algoritm av Kardas et al. [32] löser Leader Val i Strong-CD-modellen i O (log ε n) tid med hjälp av O (log log n) energi, i förväntan men inte med hög sannolikhet. Det mesta av det tidigare arbetet i radionätsmodellen har handlat om tid, inte energi. Willard [46] visade att O (log log n) tid är nödvändig och tillräcklig för en enhet att framgångsrikt överföra i Strong-CD-modellen med konstant sannolikhet; se referens [41] för avvägningar mellan tid och framgång sannolikhet. I Sender-CD-modellen kräver detta problem tid att lösa (log 2 n), med sannolikhet 1 − 1/poly(n) [20, 31, 42]. Greenberg och Winograd [26] visade att om alla enheter behöver skicka ett meddelande, är tiden (n log n (N)) nödvändig och tillräcklig i den deterministiska Strong-CD-modellen. I multi-hop radionät, Leader Val och dess relaterade problem (t.ex., sändningar och skvaller) har studerats i stor utsträckning, där gränserna normalt beror på både diameter och storlek på nätverket, om det är riktat, och om randomisering och kollisionsdetektering är tillgängliga. Se t.ex. 9, 12, 13, [15] [16] [17] 21, [35] [36] [37]. Schneider och Watterhofer [44] undersökte användningen av kollisionsdetektering i multihopradionät vid lösning av arketypiska problem som MIS, (Δ + 1)-färgning och sändning. Deras resultat visade att värdet av kollisionsdetektering beror på att problemet är löst. Cornejo och Kuhn [14] introducerade pipmodellen, där inga meddelanden sänds; de enda signalerna är λ N och λ S: buller och tystnad. Komplexiteten i ungefärlig räkning studerades i referens [8] och "stat komplexiteten" i Leader Val studerades i referens [25]. I kontradiktoriska inställningar kan en störning störa kommunikationen. Se hänvisningarna [18, 38] för presidentvalprotokoll som är motståndskraftiga mot störning. I ett protokoll om resurskonkurrens [6] är energikostnaden för apparaterna en del av energikostnaden för stören. Se referens [5] för resurskonkurrenskraftig tvistelösning och hänvisningar [24, 34] för resurskonkurrenskraftiga protokoll från punkt till punkt för kommunikation och sändning.
I den randomiserade halva duplex-modellen har båda problemen energikomplexitet (log(log * n)) och  till (log * n), i CD respektive No-CD, för poly(n)-tidsalgoritmer som lyckas med sannolikhet 1 − 1/poly(n) REF.
Exponential Separations in the Energy Complexity of Leader Election
{'venue': 'TALG', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}