I två nivåer trådlösa sensornätverk (WSNs), relä nod placering är en av de viktigaste faktorerna som påverkar nätets energiförbrukning och systemet overhead. I detta dokument föreslås en ny approximationsalgoritm för relä nodplacering i WSNs för att erbjuda ett stort steg framåt i att spara system overhead. I synnerhet introduceras en unik lokal approximationsalgoritm (LSAA) för att lösa problemet med relä node single cover (RNSC). I detta föreslagna LSAA tillvägagångssätt, är sensorn noder fördelade i grupper och sedan ett lokalt set omslag (SC) för varje grupp uppnås med en lokal sökalgoritm. Unionsuppsättningen av alla lokala SCs utgör en SC av RNSC-problemet. Den approximation förhållande och tids komplexiteten i LSAA analyseras av rigorösa bevis. Dessutom har LSAA-metoden utvidgats för att lösa problemet med dubbel täckning av relänoder. Därefter föreslås en reläplatsvalalgoritm (RLSA) för att utnyttja den resulterande SC från LSAA för att kombinera RLSA med minsta spännvidd träd heuristic för att bygga hög nivå anslutning. Som RLSA söker efter en närmaste plats till diskbänk noden för varje relä nod, blir det high-tier nätverk som byggs av RLSA tätare än det av befintliga verk. Som ett resultat av detta kan antalet tillsatta relänoder för att bygga upp anslutningsmöjligheterna för den höggradiga WSN avsevärt sparas. Simuleringsresultat visar tydligt att de föreslagna LSAA överträffar de tillvägagångssätt som rapporteras i litteraturen och den RLSA-baserade algoritmen kan märkbart spara relänoder nyligen utplacerade för hög nivå anslutning. Index Terms-Wireless sensor nätverk, relä nod placering, geometrisk skivomslag, nätverksanslutning, approximation algoritm.
En konnektivitet-medveten metod för relä nod placering föreslogs i REF.
A Connectivity-Aware Approximation Algorithm for Relay Node Placement in Wireless Sensor Networks
{'venue': 'IEEE Sensors Journal', 'journal': 'IEEE Sensors Journal', 'mag_field_of_study': ['Engineering', 'Computer Science']}