Abstrakt. Idag finns det många algoritmer och protokoll för att bygga aggregerings- eller spridningsträd för trådlösa sensornätverk som är optimala (för olika begrepp om optimal, d.v.s. Enligt olika kostnadsmått). Men alla dessa system skiljer sig från ett vanligt misslyckande - de konstruerar ett optimalt träd för en given fast delmängd av sensorerna. I de flesta praktiska scenarier, sensorgruppen är kontinuerligt och dynamiskt varierande - överväga till exempel uppsättningen sensorer utspridda i en skog som känner temperaturer över någon angiven tröskel, under en löpeld. Med tanke på de begränsade beräknings- och energiresurserna hos sensornoder är det omöjligt att antingen förlagra det optimala trädet för varje tänkbar grupp eller att dynamiskt generera dem i farten. I detta dokument föreslår vi det nya tillvägagångssättet att bygga ett enda gruppoberoende spanning träd (GIST) T för nätverket och sedan låta någon sensor grupp S använda det underträd som induceras av S på T, TS som sin gruppaggregation träd. Den viktiga frågan är, hur kvaliteten på underträdet TS kan jämföras med det optimala trädet, OP TS, mellan olika grupper S. Vi anser att två väl godkända åtgärder - aggregeringskostnad (summan över alla länkar) och fördröjning (diameter). Vi visar att i polynom tid kan vi konstruera en GIST som samtidigt uppnår O(log n)-ungefärlig aggregeringskostnad och O(1)-ungefärlig fördröjning, för alla grupper S. Så vitt vi vet GIST är den första konstruktionen med en icke-trivial och bevisbar prestanda garanti som fungerar för alla grupper. Vi tillhandahåller ett praktiskt och distribuerat protokoll för att förverkliga GIST som endast kräver lokal kunskap. Vi visar en lägre gräns för allmänt accepterade lösningar såsom MST och SPT (dvs. Det finns en grupp för vilken det inducerade underträdet presterar dåligt) och visar genom simulering att GIST är bra inte bara i värsta fall -det överträffar SPT och MST med mellan 30 och 60 procent i realistiska slumpmässiga scenarier. GIST är en overlay konstruktion och för det speciella fallet av rutnät presenterar vi GRID-GIST, ett fysiskt träd som bara använder rutnät kanter och uppnår samma prestanda gränser.
Jia m.fl. i REF bygga en grupp Independent Spanning Tree Algoritm (GIST) som konstruerar ett överlagrat träd för slumpmässigt utplacerade noder i ett Euclidean 2-dimensionellt plan.
Gist: Group-independent spanning tree for data aggregation in dense sensor networks
{'venue': 'In DCOSS', 'journal': None, 'mag_field_of_study': ['Computer Science']}