Abstrakt. Vi anser att n mobila sensorer ligger på en linje som innehåller en barriär som representeras av en ändlig linjesegment. Sensorerna bildar ett trådlöst sensornätverk och kan röra sig inom linjen. En inkräktare som passerar barriären kan upptäckas endast när den är inom avkänningsintervallet för minst en sensor. Sensornätverket etablerar barriärtäckning av segmentet om ingen inkräktare kan tränga igenom barriären från någon riktning i planet utan att upptäckas. Med utgångspunkt från godtyckliga inledande positioner av sensorer på linjen är vi intresserade av att hitta slutliga positioner av sensorer som etablerar barriärtäckning och minimerar det maximala avstånd som passeras av någon sensor. Vi skiljer flera varianter av problemet, baserat på (a) om sensorerna har identiska intervall, (b) om fullständig täckning är möjlig eller inte och (c) när fullständig täckning är omöjlig, oavsett om maximal täckning krävs för att vara sammanhängande eller inte. För n-sensorer med samma räckvidd, när fullständig täckning är omöjlig, ger vi linjär tid optimala algoritmer som uppnår maximal täckning, både för sammanhängande och icke sammanhängande fall. När fullständig täckning är möjlig, ger vi en O(n 2 ) algoritm för en optimal lösning, ett linjär tid approximationsschema med approximation faktor 2, och en (1 + ) PTAS. När sensorerna har ojämlika intervall visar vi att en variation av problemet är NP-komplett och identifierar några fall som kan lösas med våra algoritmer för sensorer med ojämlika intervall.
När sensorerna är på linjen av barriären, visas 1D-LBC-problemet optimalt lösbar i O(n 2 ) tid för enhetliga radier i papper REF.
On minimizing the maximum sensor movement for barrier coverage of a line segment
{'venue': 'In proceedings of 8th International Conference on Ad Hoc Networks and Wireless', 'journal': None, 'mag_field_of_study': ['Computer Science']}