Minimizing Aggregate Movements for Interval Coverage
This research addresses the problem of minimizing aggregate movements for interval coverage using sensors to cover a segment with optimal energy efficiency. It explores various scenarios, previous work, and results, offering insights into movement minimization strategies and lower bounds for the problem.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Minimizing the Aggregate Movements Minimizing the Aggregate Movements for Interval Coverage for Interval Coverage Aaron Andrews and Haitao Wang Utah State University WADS 2015
Problem definition Problem definition Input: n intervals of the same length on a line L a segment B on L Goal: move the intervals to cover B such that the sum of the moving distances of all intervals is minimized L B
Mobile sensor barrier coverage Mobile sensor barrier coverage There is a sensor centered at each interval and the interval is the covering interval of the sensor B: the barrier Move sensors to form a coverage of B to minimize the sum of all sensor movements For minimizing the total energy cost of sensors L B
Covering ranges Covering ranges r: the covering range of each sensor 2r: the length of the covering interval |B|: the length of B Assumption: 2r n |B| n sensors are sufficient to cover B r
Previous work and our results Previous work and our results Previous work O(n2) time, Czyzowicz et al. 10 Our result O(n log n) time (n log n) lower bound ---- a reduction from sorting
Related work Related work NP-hard, if sensors have different ranges, Czyzowicz et al. 10 Min-max version: minimize the maximum movement Uniform range: O(n log n) time, Chen et al, 13 Non-uniform range: O(n2log n) time, Chen et al, 13 Min-number version: minimize the number of moving sensors Uniform range: O(n3) Mehrandish et al. 11 Non-uniform range: NP-hard, Mehrandish et al. 11
Three cases Three cases The containing case: all intervals intersect B The one-sided case: intervals that do not intersect B are all on the same side of B The general case
The order preserving property The order preserving property --- --- Czyzowicz Czyzowicz et al. et al. 10 10 There is an optimal solution in which sensors appear in the same order on L as those in the input Due to that sensors have the same covering range
The containing The containing case case Gap: a maximal uncovered sub-segment of B Overlap: a sub-segment of B covered by two adjacent sensors or, a segment of L\B covered by a sensor o o o o g g o To cover B is essentially to use overlaps to cover gaps
The containing The containing case case the algorithm the algorithm Based on the previous O(n2) time algorithm, Czyzowicz et al. 10 There are O(n) operations Each one is preformed in O(n) time An O(n log n) time implementation By designing efficient data structures Each operation is performed in O(log n) time
Attached positions Attached positions o g in attached positions
A greedy algorithm A greedy algorithm The gaps are covered from left to right Consider a gap g Use which overlap to cover g? It s right or left neighboring overlap Defining cost for o1and o2 g o2 o1
Defining cost Defining cost for for o o1 1and and o o2 2 S1: the sensors between g and o1 cost(o1) = |S1| If we shift sensors of S1leftward for a small distance , the total moving distance increases by |S1| cost(o2) = |S2| 2|S2 | S2: the sensors between g and o2 S2 :the sensors of S2that have been moved leftwards multiplicative cost S2 g S1 o2 o1 S2
Covering the gap g Covering the gap g Find o1and o2 Compute cost(o1) and cost(o2) If cost(o1) cost(o2) Shift the sensors of S1leftwards by min{|g|, |o1|} else Shift the sensors of S2rightwards by min{|g|, |o2|, } : the minimum left-shifted distance of the sensors of S2 Why ? After the sensors are moved rightwards by , cost(o2) = |S2| 2|S2 | is changed o2 o1 g
Covering the gap Covering the gap g (cont.) g (cont.) After the shift, g is either fully covered or shrunk proceed on the next gap or the remaining g There are O(n) shift operations in total Previous work: O(n) time for each operation Our improvement: O(log n) time A position tree An overlap tree A left-shift tree
The position tree The position tree Each node maintains a shift value Example: Shift sensors from 2 to 6 rightwards by distance 5 Find O(log n) nodes and increase the shift value of each node by 5 0 0 0 0 0 0 5 0 5 0 5 0 x3 0 x4 0 x5 0 x7 0 0 0 x8 L x1 x2 x6 The current location of any sensor i is xi+ the sum of the shift values at the ancestors of i
The one The one- -sided case sided case Intervals that do not intersect B are on the same side of B Our solution: O(n log n) time Using the algorithm for the containing case Reverse operations
Why the containing case algorithm Why the containing case algorithm not work? not work? The way we defined cost(o1) and cost(o2) not work cost(o2) = 3 (assume |S2 | = 0) cost(o1) = 1 d is an additive cost, not consistent with the multiplicative cost 1 o2 o1 g d
Our solution Our solution SR: the sensors whose intervals do not intersect B SI= S - SR If no sensor of SRis moved in an optimal solution, Applying the containing case algorithm on SI SR
Our solution (cont.) Our solution (cont.) Otherwise r*: the rightmost sensor of S that is moved in an optimal solution SR : the sensors of SRto the left of r* Step 1: move all sensors of SR leftwards until the right endpoint of B Step 2: apply the containing case algorithm on SI U SR The total cost of the above two steps is the optimal cost Correctness: the order preserving property r* SR
How to find r*? How to find r*? A straightforward solution: Consider each sensor of SRas r* and compute the cost; return the one with minimum cost O(n2log n) time Our solution: O(n log n) time
An O(n log n) time algorithm An O(n log n) time algorithm Consider any sensor r of SR SR : the sensors of SRto the left of r Step 1: shift all sensors of SR leftwards the shift cost Step 2: applying the containing case algorithm on SI U SR containing-case-cost(r): the cost returned by the algorithm Total cost for r = the shift cost + containing-case-cost(r) Goal: compute the total cost for all r in SR r SR
Computing containing Computing containing- -case all r of S all r of SR R: : the reverse operations the reverse operations case- -cost(r) for cost(r) for Suppose containing-case-cost(r-1) is known containing-case-cost(r) can be obtained based on containing-case-cost(r-1) and by reverse operations Record all covered gaps and those overlaps that are used to cover these gaps in the containing case algorithm o2 o1 g r-1 o2 o1 g r-1
The general case The general case SR: the intervals to the right of B SL: the intervals to the left of B SI= S SR SL Observation: If there is an optimal solution in which no sensor in SLis moved, then we can apply the one- sided case algorithm on SIU SR SR SL
Our solution Our solution r*: the rightmost sensor of S that is moved in an optimal solution SR : the sensors of SRto the left of r* Step 1: move all sensors of SR leftwards until the right endpoint of B Step 2: apply the one-sided case algorithm on SLU SI U SR The total cost of the above two steps is the optimal cost r* SR
How to find r*? How to find r*? A straightforward solution: Consider each sensor of SRas r* and compute the cost; return the one with minimum cost O(n2log n) time Our solution: O(n log n) time
Finding r* in O(n log n) time Finding r* in O(n log n) time Several cases k: the minimum number of sensors necessary to fully cover B. Case 1: |SI| k Shift sensors of SLrightwards until the left endpoint of B Apply the one-sided case algorithm on S The rightmost sensor of SRmoved in the above solution is r*
Finding r Finding r* * in O(n log n) in O(n log n) time (cont.) time (cont.) Case 2: |SI| < k k*: the number sensors used in an OPT Case 2.1: k* k+1 Compute r* in the same way as Case 1 Case 2.2: k* = k Case 2.2.1: |B| = 2r * k The OPT uses k sensors in attached positions exactly covering B Find an optimal solution by a sweeping algorithm Case 2.2.2: |B| < 2r * k Find an optimal solution by using reverse operations and other techniques k sensors
Case 2.2.2: Case 2.2.2: |B| < 2r * k |B| < 2r * k Try all pairs (l, r) such that there are k sensors between l and r For each pair, compute the containing-case-cost Compute the cost for all O(n) pairs in O(n log n) time k sensors l r
Thank you! Thank you!
