Trådlösa sensornätverk (WSN) växer fram som ett effektivt sätt att övervaka miljön. I detta dokument undersöks en strategi för energieffektiv övervakning i WSN:er som delar upp sensorerna i höljen, och sedan aktiverar höljena iterativt på ett round-robin-sätt. Detta tillvägagångssätt drar nytta av den överlappning som skapas när många sensorer övervakar ett enda område. Vårt arbete bygger på tidigare arbete i [13], där modellen först formuleras. Vi har designat tre approximationsalgoritmer för en variation av SET K-COVER-problemet, där målet är att dela upp sensorerna i täcken så att antalet täcken som inkluderar ett område, summerat över alla områden, maximeras. Den första algoritmen är randomiserad och partitionerar sensorerna, i förväntan, inom ett bråk 1 - 1 e (.63) av det optimala. Vi presenterar två andra deterministiska approximationsalgoritmer. Den ena är en distribuerad girig algoritm med en 12 approximation förhållande och den andra är en centraliserad girig algoritm med en 1-1 e approximation förhållande. Vi visar att det är NP-Complete att garantera bättre än 15 16 av den optimala täckningen, vilket indikerar att alla tre algoritmer presterar bra med avseende på bästa approximation algoritm möjligt i polynom tid, förutsatt att P = N P. Simuleringar visar att i praktiken deterministiska algoritmer utför långt över sina värsta fall gränser, konsekvent täcker mer än 72% av vad som täcks av en optimal lösning. Simuleringar visar också att ökningen av livslängden är proportionell mot mängden överlappningar mellan sensorerna. Algoritmerna är snabba, lätta att använda, och enligt simuleringar, avsevärt öka livslängden för sensornätverk. Särskilt den randomiserade algoritmen verkar ganska praktisk.
Abrams, Goel och Plotkin REF studerar problemet med att dela upp sensorerna i omslag så att antalet omslag som inkluderar ett område, summerat över alla k-områden, maximeras.
Set k-cover algorithms for energy efficient monitoring in wireless sensor networks
{'venue': "IPSN '04", 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}