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.
As a matter of fact, the above problem has not been studied in previous research. Some of existing studies @cite_4 @cite_6 @cite_10 on node placement address the throughput issue. These studies mainly focus on placing nodes to optimize the network throughput. The scenario of collecting all node transmissions towards sink nodes is considered in @cite_4 . A grid-based relay nodes placement method is used to optimize the network throughput in @cite_6 . Two objectives are studied in @cite_10 . The one is to maximize the minimum throughput for any relay node, and the other is to maximize the total throughput of the network. However, the throughput optimization of the whole network is not equal to the issue of satisfying the flow requirements of some nodes, and also, the flow requirements of different nodes may be different, which should be with differential treatment. The flow requirements cannot be satisfied within throughput optimization framework. Besides, the wireless interference, an intrinsic characteristic of wireless channel, among nodes is also seldom considered in these studies. We study the flow demands oriented node placement problem to fill this blank.
@cite_10 @cite_4 @cite_6
1989193160 2015222956 2128199885
We study the novel hierarchical architecture of Mobile Backbone Networks. In such networks, a set of Mobile Backbone Nodes (MBNs), which are envisioned to be airborne, are deployed to provide an end-to-end communications capability for the terrestrial Regular Nodes (RNs). We address the joint problem of placing a fixed number K MBNs, and assigning each RN to exactly one MBN, using two optimization objectives. The first is the Maximum Fair Placement and Assignment (MFPA) problem in which the objective is to maximize the minimum throughput obtained by any RN. The second is the Maximum Throughput Placement and Assignment (MTPA) problem, in which the objective is to maximize the aggregate throughput of the RNs. We develop an optimal polynomial time algorithm for the MFPA problem for any K, and an optimal polynomial time algorithm for the MTPA problem for K≤ 2. We also develop lower complexity approximation algorithms and present simulation results comparing the performance of the various algorithms. This work addresses the relay node placement problem in wireless sensor networks. We consider a scenario in which all sensor nodes stream data towards sink nodes. Additional relay nodes can be placed with the aim of optimizing overall network performance in terms of data throughput. We formalize the problem with a linear, mixed integer mathematical programming model. We include a number of constraints and penalties to closely model the wireless environment. When relay nodes can be placed anywhere, we define their possible locations using a discrete grid. Model solutions specify both where to place the relays and the paths for routing. Through extensive simulation experiments, we compare model solutions against a state-of-the-art dynamic routing protocol to assess the quality of the routes, and against a relay node placement heuristic to evaluate relay positioning. To tackle the computational complexity, we also propose and study the effect of different strategies for determining the grid resolution. Additionally, an experimental validation carried out in a real testbed shows that the computed solutions clearly increase network performance by enabling the reception of larger number of data packets at the sinks and determining a fair QoS distribution among the nodes. Finally, we propose an on-line application, in which the model is built and solved on-demand, to adapt to changes in traffic patterns induced by external events, and the results are rapidly spread throughout the network and used to modify relay node positioning and routing paths. In this paper, we address the problem of gateway placement for throughput optimization in multi-hop wireless mesh networks. Assume that each mesh node in the mesh network has a traffic demand. Given the number of gateways to be deployed (denoted by k) and the interference model in the network, we study where to place exactly k gateways in the mesh network such that the total throughput is maximized while it also ensures a certain fairness among all mesh nodes. We propose a novel grid-based gateway deployment method using a cross-layer throughput optimization, and prove that the achieved throughput by our method is a constant times of the optimal. Simulation results demonstrate that our method can effectively exploit the available resources and perform much better than random and fixed deployment methods. In addition, the proposed method can also be extended to work with multi-channel and multi-radio mesh networks under different interference models.