The node updates C of the message
to the minimum value of C or E, and sends the updated incremental cost message to
the next node.
340 Kai-Wei Fan, Sha Liu, and Prasun Sinha
After receiving the incremental cost message, the sink reinforces the neighbors
that send packets with minimum of E or C. When the neighboring node receives
the reinforcement, it reinforces its upstream nodes that send packets with minimum
of E or C. Therefore, a greedy incremental tree can be constructed, allowing nodes
to forward packets to the closest path using minimum energy. The reinforcement of
minimum energy cost to construct a greedy incremental tree is illustrated in Figure
5. In Figure 5, the path from Source 1 to the sink is the first reinforced path. The
protocol reinforces the path with minimum E or C of packets from Source 2, thus
constructing a minimum energy cost path from Source 2 to the existing tree.
(a) (b)
Fig. 5. The path with minimum incremental energy cost is reinforced.
In directed diffusion, multiple paths can be reinforced. Therefore, the sink or the
intermediate nodes may receive an aggregated packet containing the event transmitted
by the same source from multiple reinforced paths. If we can reduce the duplication,
we can reduce the number of transmissions to save energy. However, this is like
a set-covering problem, which is an NP-hard problem [13]. For example, as shown
in Figure 6, The sink receives data A1,B1,C1 from multiple paths via nodes D, E,
and F.
Pages:
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544