The sink can get A1,B1,C1 from D and F only, without packets from E.
Therefore, by truncating the path from E, more energy can be saved.
Fig. 6. The weighted set-covering problem.
Chapter 13 Data Aggregation in Wireless Sensor Networks 341
The problem is the weighted set-covering problem (The regular set-covering
problem is a special case of the weighted set-covering problem with all weights equal
to 1). Each incoming packet is associated with a weight, i.e., energy cost. To find a
set of paths that transmit packets from all sources with minimum energy cost is to
find the covering set with minimum weight.
The protocol uses a greedy heuristic method to find an energy inefficient path,
and uses negative reinforcement to truncate them. The greedy heuristic is to select
a subset that covers uncovered elements with the lowest cost ratio, or the cost per
element, until all elements are covered. As in Figure 6, nodes D, E, and F have
aggregated packets containing A1,B1, B1, and B1,C1, and their weights are 3, 3, 4
respectively. The greedy approach first calculates the cost ratio for each set. Therefore
the cost ratio for set S1 is w1/|S1| = 1.5, for set S2 is w2/|S2| = 3, and for
set S3 is w3/|S3| = 2. Therefore the greedy heuristic selects set S1 first. At second
step, because B1 is already covered, the uncovered elements in set S2 is 0, therefore
the cost ratio for S2 is 1 (actually we can eliminate sets with 0 uncovered elements
immediately since including them does not increase the covered elements).
Pages:
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545