The motivation for the above definition of the edge energy cost is as follows. Whenever a
B-node moves into the transmission range TR of a P-node, it is capable of forwarding to
the P-node packets destined for other nodes so as to conserve energy. At one extreme, if
a B-node moves along an edge not (partially) covered by any P-node, all the packets from
this B-node would be forwarded to other energy-constrained B-nodes, which is the most
unfavorable situation. At the other extreme, if a B-node moves along an edge completely
covered by one or several P-nodes, all the packets from this node could be forwarded to the
P-node(s), which is the most desirable situation. Notice that the energy cost function given
above can well capture this effect. Though there might exist other meaningful metrics, we
believe the chosen one is very simple and tractable.
We also define the non-negative delay and cost functions for any path p as
dist(p) = dist(e)
etp
and
cost(p) = costle).
etp
Given the above definitions, the DCLC routing problem is to find a path p from s to d
such that min~cost(p), p E Pd} is achieved, where Pd is the set of all feasible paths from
s to d satisfying the distance constraint Imax, that is, dist(p) < Imax. Moreover, we define
Pra(s, d) as the path with the least distance from s to d, and Ple(s, d) as the path with the
least cost from s to d. Apparently, with the above definition of dist(e), Pla(S, d) is the
straight path directly connecting s and d.
It has been shown in [72] that the DCLC routing problem is NP-complete even for
undirected networks. In the following section we will propose an efficient heuristic algo-
rithm to provide a suboptimal solution to this DCLC problem and hence to the original
Waterhunter Movement problem.