Abstract-Två grundläggande funktioner för sensornoder i ett trådlöst sensornätverk är att känna sin miljö och att överföra känslig information till en basstation. Ett sätt att förlänga livslängden för sensornätverk är att distribuera några relänoder vars huvudsakliga funktion är att kommunicera med sensornoder, andra relänoder och basstationer. Det är önskvärt att använda ett minsta antal relänoder för att uppnå vissa anslutningskrav. I denna uppsats studerar vi fyra relaterade problem med feltoleranta reläknutor, som alla tidigare har studerats endast i någon begränsad form. För var och en av dem diskuterar vi dess beräknings komplexitet och presenterar en polynom tid O(1)-tillnärmning algoritm med en liten approximation förhållande. När problemet minskar till en tidigare studerad form förbättrar vår algoritm antingen den tidigare bästa algoritmen eller minskar till den tidigare bästa algoritmen. Nyckelord: Överlevnadsbar reläplacering, trådlösa sensornätverk. Ett trådlöst sensornätverk (WSN) består av många lågkostnads- och lågeffektsensornoder (SN) [1]. Det har varit omfattande forskning om energi medveten routing [4, 10, 13, 16, 27], förbättring i livslängd [12, 21, 24, 26], och överlevnad [20]. Eftersom energiförbrukningen är proportionell mot d σ för överföring över avstånd d, där σ är en konstant i intervallet [2, 4], är långdistansöverföring i WSN kostsam. För att förlänga nätverkets livslängd samtidigt som man uppfyller vissa nätverksspecifikationer har forskare föreslagit att ett litet antal dyra, men mer kraftfulla relänoder (RNs) vars huvudsakliga funktion är att kommunicera med SNs och andra RNS [2, 5, 9, 12, 14, 18, 19, 23, 26]. Detta är ämnet för denna rapport. Vi går först igenom tidigare arbeten på single-tiered relä node placering, där både SNs och RNS deltar i paket vidarebefordring. Cheng m.fl. [5] föreslog att ett minsta antal RN skulle sättas in i ett WSN så att det mellan varje par av SN:er finns en väg bestående av RN:er och/eller SN:er där varje humle av banan inte är längre än det gemensamma överföringsområdet r > 0 av SN:erna. Detta problem är likvärdigt med Steiner minsta träd med minsta antal Steiner punkter och begränsad kant längd problem (SMT-MSPBEL), definieras av Lin och Xue i studien av förstärkare placering i optiska nätverk [17], där de bevisade problemet är NPhard och presenterade en minsta spännvidd träd (MST) baserad 5- approximation algoritm. År [3], Chen et al. bevisade att Lin-Xue-algoritmen är en 4-ungefärlig algoritm. De presenterade också en 3 approximationsalgoritm. I [5], Cheng et al. presenterade en snabbare 3 approximationsalgoritm. År [2], Bredin m.fl. Extended the relä node placering problem studeras i [3, 5,
Zhang och Misra REF studie fyra relaterade feltolerant relä nod placering problem och erbjuder en konstant polynom tid komplexitet.
Fault-Tolerant Relay Node Placement in Wireless Sensor Networks: Problems and Algorithms
{'venue': 'IEEE INFOCOM 2007 - 26th IEEE International Conference on Computer Communications', 'journal': 'IEEE INFOCOM 2007 - 26th IEEE International Conference on Computer Communications', 'mag_field_of_study': ['Computer Science']}