Vi tar itu med ett klassiskt problem som rör energieffektivitet i sensornätverk. I synnerhet överväger vi problemet med att maximera livslängden för täckning av mål i ett trådlöst sensornätverk med batteribegränsade sensorer. Vi visar först att problemet inte kan approximeras inom en faktor mindre än ln n av någon polynom tid algoritm, där n är antalet mål. Detta ger stängning till det långvariga öppna problemet att visa optimalitet av tidigare kända ln n approximation algoritmer. Vi kommer också fram till en ny tillnärmning till problemet genom att visa att den n n approximationen till det därmed sammanhängande problemet med maximalt osammanhängande skydd. Vi visar att detta tillvägagångssätt har många fördelar jämfört med algoritmer i litteraturen, inklusive en enkel och optimal förlängning som löser problemet med flera täckningsbegränsningar. För 1-D-nätverkstopologin, där sensorer kan övervaka sammanhängande linjesegment av möjligen olika längder, visar vi att den optimala täckningstiden kan hittas i polynomtid. Slutligen, för 2-D topologin där täckning regioner är enhet kvadrater, kombinerar vi de befintliga resultaten för att härleda en 1 + approximation algoritm för problemet. Omfattande simuleringsexperiment validerar våra teoretiska resultat, vilket visar att våra algoritmer inte bara har optimala sämsta fall-garantier utan också matchar prestandan hos de befintliga algoritmerna på speciella nätverkstopologier. Dessutom, våra algoritmer kör ibland storleksordningar snabbare än den befintliga state of the art.
Den andra kategorin av relaterade arbeten är maximal separat uppsättning täckning problem REF.
Optimally Approximating the Coverage Lifetime of Wireless Sensor Networks
{'venue': 'TNET', 'journal': None, 'mag_field_of_study': ['Computer Science']}