Traditionellt har prestandan hos distribuerade algoritmer mätts i fråga om tid och meddelande komplexitet. Meddelandets komplexitet gäller antalet meddelanden som överförs över alla kanter under algoritmens gång. I energiintensiva radio- eller trådlösa nät (t.ex. sensornätverk) är dock energi en kritisk faktor för att mäta effektiviteten hos en distribuerad algoritm. Sända ett meddelande mellan två noder har en tillhörande kostnad (energi) och dessutom denna kostnad kan bero på de två noderna (t.ex. avståndet mellan dem bland annat). Förutom tids- och meddelande komplexitet, är det därför viktigt att beakta energi komplexitet som står för den totala energi i samband med meddelanden som utbyts bland noderna i en distribuerad algoritm, och design energieffektiv distribuerade algoritmer för energi-fasta nätverk. I detta dokument behandlas problemet med minsta spännvidd (MST), ett viktigt problem i distribuerade datorer. Vi studerar energieffektiva distribuerade algoritmer för Euclidean MST problem antar slumpmässig fördelning av noder. Vi visar en icke-trivial lägre gräns för  ska (log n) om energi komplexiteten i någon distribuerad MST algoritm. Vi ger sedan en distribuerad algoritm som konstruerar en optimal MST med energi komplexitet O(log n) i genomsnitt och O(log n log log n) med hög sannolikhet. Detta är en förbättring jämfört med den tidigare mest kända begränsningen av den genomsnittliga energikomplexiteten hos  och 2 n. Alla ovanstående resultat antar att noderna inte vet deras geometriska koordinater. Om noderna vet sina egna koordinater, då ger vi en algoritm med O(1) energi komplexitet (vilket är det bästa möjliga) som ger en O(1) approximation till MST.  Kategorier och ämnesnätverksmodell. Vi antar att nätverket är modellerat som en viktad oriktad graf G = (V, E, w) där V är uppsättningen av noderna (vertikal) och E är uppsättningen av de (dubbelriktade) kommunikationslänkarna mellan dem och w(e) är vikten av kanten e E. Vikten w(u, v) representerar den energi som är förknippad med att överföra ett meddelande mellan u och v. Grafen G har följande underliggande geometri. Noderna är inställda på  och V = n punkter fördelade slumpmässigt i en enhet kvadrat och två noder är anslutna om de är inom avstånd r av varandra (den inducerade grafen är också känd som en slumpmässig geometrisk graf [11] ). G kan betraktas som en viktad diskkurva per enhet. Detta är en standard geometrisk grafmodell som har använts i stor utsträckning i litteraturen för att modellera kommunikationsnät i ett plan, t.ex. trådlösa och ad hoc-nät. Utan förlust av generalitet, antar vi att r väljs så att G är ansluten. Formellt, energi komplexiteten hos den distribuerade algoritmen definieras som m i=1 wi, där wi är vikten av kanten som ansluter noderna utbyter ith meddelandet, och m är det totala antalet meddelanden utbytta av algoritmen. Vikten på en kant är en funktion av avståndet mellan de två punkterna. Även om våra resultat är generella till en mängd olika viktfunktioner, för betong, antar vi att w (u, v) är proportionell till någon fast effekt (benämns som α) av avståndet mellan u och v, dvs w (u, v) = a(d(u, v)) α där d (u, v) är (Euklidean) avståndet mellan u och v, och a är någon fast konstant. Motiveringen till detta kommer från energibehov i en radio (trådlös) kommunikation paradigm: att överföra ett meddelande över ett avstånd r, den nödvändiga energin är (proportionalitet till) r α, där typiskt α är 2 [7]. I detta dokument, om inte annat anges, antar vi α = 2. (Våra resultat kan generaliseras till andra värden av α också.) Distribuerad datormodell. Varje nod i G är värd för en processor med begränsad initial kunskap. Varje nod har unika identitetsnummer och i början av beräkning, varje vertex v accepterar som inmatning sin egen identitetsnummer. Noder vet inte ens vikten av dess infallande kanter (eller motsvarande avståndet till sina grannar). Vi utgår från att kommunikationen är synkron och sker i diskreta tidssteg. Energin i samband med en dubbelriktad kommunikation mellan grannar u och v är  en (w(u, v) ), dvs, om u vill skicka ett meddelande till v och v svar tillbaka till u 188
Yongwook Choi, & Maleq Khan föreslog i REF minsta spanning träd (MST) problem, genom att anta slumpmässig fördelning av noder över Euclidean avstånd av nätverket.
Energy-optimal distributed algorithms for minimum spanning trees
{'venue': "SPAA '08", 'journal': None, 'mag_field_of_study': ['Computer Science']}