Abstrakt. I detta dokument studerar vi en uppsättning problem relaterade till effektiv energihantering för övervakning av tillämpningar i trådlösa sensornätverk. Vi studerar flera generaliseringar av ett grundläggande problem som kallas Set k-Cover. Problemet kan beskrivas på följande sätt: vi får en uppsättning sensorer och en uppsättning regioner som ska övervakas. Varje region kan övervakas av en delmängd av sensorerna. För att öka livslängden för sensornätverket, skulle vi vilja partitionera sensorerna till k-uppsättningar (eller tidslotter), och aktivera varje uppsättning sensorer i en annan tidsrymd, vilket utökar batteritiden för sensorerna med en faktor av k. Målet är att hitta en partitionering som maximerar den totala täckningen av regionerna för en given k. Detta problem är känt för att vara N P -hard. Vi utvecklar en förbättrad approximationsalgoritm för detta problem med hjälp av en reduktion till Max k-Cut. Dessutom kan vi visa att denna algoritm är praktisk och ger nästan optimala lösningar i praktiken. Vi överväger också generaliseringar av detta problem i flera olika riktningar. Först låter vi varje sensor vara aktiv i α olika uppsättningar (time-slots). Detta innebär att batteriets livslängd förlängs med en faktor k α, och möjliggör ett rikare utrymme av lösningar. Vi överväger också olika täckningskrav, till exempel att kräva att alla regioner, eller åtminstone ett visst antal regioner, ska omfattas av varje tidsrymd. I formuleringen Set k-Cover finns det inget krav på att en region ska övervakas över huvud taget, eller i något antal tider. Vi utvecklar en randomiserad avrundningsalgoritm för detta problem. Vi överväger också förlängningar där varje sensor kan övervaka endast ett begränsat antal regioner i någon time-slot, och inte alla regioner som gränsar till den. Denna typ av problem kan uppstå när en sensor har en riktad kamera, eller någon annan fysisk begränsning kan hindra den från att övervaka alla angränsande regioner även när den är aktiv. Vi utvecklar de första approximationsalgoritmerna för detta problem.
Senare, Deshpande et al. studera flera generaliseringar av Set K-Cover problem, och utveckla en approximation algoritm baserad på en minskning till Max K-Cut REF.
Energy efficient monitoring in sensor networks
{'venue': 'IN LATIN 2008: THEORETICAL INFORMATICS, 8TH LATIN AMERICAN SYMPOSIUM, BÚZIOS, BRAZIL, APRIL 7-11, 2008, PROCEEDINGS', 'journal': None, 'mag_field_of_study': ['Computer Science']}