Abstrakt. Vi studerar lågkostnadssensorplacering på ett avgränsat 3D-sensorfält, R, som består av ett antal diskreta punkter som kanske eller kanske inte är rutnätspunkter. Antag att vi har l typer av sensorer tillgängliga med olika sensorintervall och olika kostnader. Vi vill hitta, med tanke på ett heltal σ ≥ 1, ett urval av sensorer och en del av punkter för att placera dessa sensorer så att varje punkt i R täcks av minst σ sensorer och den totala kostnaden för sensorerna är minimal. Detta problem är känt för att vara NP-hård. Låt k i betecknar det maximala antalet punkter som kan täckas av en sensor av ith-typen. Vi presenterar i detta papper en polynom-tids approximation algoritm för detta problem med en bevisad approximation förhållande γ = È l i=1 k i −σ +1. I tillämpningar där avståndet mellan två punkter har en fast positiv lägre gräns, är varje k i en konstant, och så har vi en polynom-tids approximation algoritmer med en konstant garanti. Även om γ kan vara stor, vi noterar att det är bara en värsta fall övre gräns. I praktiken är den faktiska approximationen liten, även på slumpmässigt genererade punkter som inte har ett fast positivt minsta avstånd mellan dem. Vi ger ett antal numeriska resultat för att jämföra approximeringslösningar och optimala lösningar, och visar att de faktiska approximationsgraderna i dessa exempel alla är mindre än 3, även om γ är betydligt större.
Även i REF, Wang och Zhong föreslå en polynom-tid approximation algoritm för att hitta en lösning på problemet med att distribuera minsta antal sensorer på ett avgränsat 3D-fält.
Efficient point coverage in wireless sensor networks
{'venue': 'Journal of Combinatorial Optimization', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}