This implies the following
constraint in the dual space:
163
Ren-Shiou Liu, Lifeng Sang, and Prasun Sinha
Fig. 9. A set of sensors and a shadow edge.
Fig. 10. The dual-space representation of the sensors and the shadow edge in Figure
9.
l > pi.
Similarly, any sensor pj with a 1 reading is below the shadow edge and
implies another constraint in the dual space:
l < pj .
By linear programming, a point at the cell boundary can be found by
solving the set of all inequalities. And finally, starting from that point, the
cell can be found by walking along the boundaries of the cell which satisfy the
set of constraints. Besides the simplicity of finding frontier nodes in the dual
space, the movement of the shadow edge can be tracked easily as well. Again,
take Figure 9 as an example; if the shadow edge moves toward the direction
164
Chapter 6 Boundary Detection for Sensor Networks
Fig. 11. The trace of the shadow in the dual space.
of P2 and eventually covers it, as shown in Figure 11, its dual representation
l will cross line segment B. It is intuitively clear that the new cell will be {B,
D, F, E}. And it can be obtained by flipping the constraint on line s2 and
walking through the line segments that satisfy the new constraint set.
Though the dual-space is simple and elegant, it has its limitations. Since
it is based on the dual-space transform of points and lines, it can not be
used to detect or track boundaries with randomly shaped curves.
Pages:
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283