The Waterhunter Movement problem is similar to the determination of people's opti-
mal travelling plans when lots of airline hubs and stops are available. On the contrary, the
Firehunter Movement problem bears similarity with the planning of hub locations when
airline companies build their global transportation networks with the purpose of providing
more convenience for passengers while reducing the overall system cost. Both problems
are pretty interesting and worthy of rigorous study. However, due to the space limitation,
we focus on finding a nearly optimal solution to the Waterhunter Movement problem in
this dissertation. Our investigation on the Firehunter Movement problem and the general
Resource-Aware Movement problem will be the future work.
3.4 Waterhunter Movement
In this section, we first present a simplified version of the Waterhunter Movement
problem, which is further reduced to a NP-complete distance-constrained least-cost (DCLC)
problem. We then present an efficient heuristic solution. Finally, we propose a routing
delay differentiation mechanism to utilize the benefits resulting from the resource-aware
movement.
3.4.1 Simplified Waterhunter Movement Problem
In the Waterhunter Movement problem, we assume that all the N, nodes are stationary
during the observation period T and are willing to forward packets for other less powerful
B-nodes. For simplicity, we do not dwell on how to place P-nodes to attain the optimal
system performance, which is believed to be a challenging problem itself and is currently
under investigation. Instead, we assume that each B-node knows the locations of all the
P-nodes and its own location at any time, and can as well adjust its moving direction at
will. For the time being, we assume here that all the P-nodes and B-nodes have the same
transmission range TR. We will discuss the case that P-nodes have the larger transmis-
sion range than B-nodes in Section 3.4.4. It is worth pointing out that the findings in this
dissertation can be easily extended to the case that each node has individual transmission
range.