  In multi-hop wireless networks, flow demands mean that some nodes have
routing demands of transmitting their data to other nodes with a certain level
of transmission rate. When a set of nodes have been deployed with flow demands,
it is worth to know how to construct paths to satisfy these flow demands with
nodes placed as few as possible. In this paper, we study this flow demands
oriented node placement problem that has not been addressed before. In
particular, we divide and conquer the problem by three steps: calculating the
maximal flow for single routing demand, calculating the maximal flow for
multiple routing demands, and finding the minimal number of nodes for multiple
routing demands with flow requirement. During the above solving procedure, we
prove that the second and third step are NP-hard and propose two algorithms
that have polynomial-time complexity. The proposed algorithms are evaluated
under practical scenarios. The experiments show that the proposed algorithms
can achieve satisfactory results on both flow demands and total number of
wireless nodes.
