Flow Demands Oriented Node Placement in Multi-Hop Wireless Networks

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.

• Publication year

  2015

• Venue

  arXiv.org

• Publication date

  2015-03-29

• Fields of study

  Computer Science

• Identifiers
  arXiv 1503.08396
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Interference coordination in wireless networks: A flow-level perspective

  2013cited by this paper
• A flow-based optimization model for throughput-oriented relay node placement in wireless sensor networks

  2013influential reference
• Providing protection in multi-hop wireless networks

  2013cited by this paper
• Distributed node placement algorithms for constructing well-connected sensor networks

  2012cited by this paper
• Relay Node Placement in Wireless Sensor Networks

  2011cited by this paper
• Topology Control in Wireless Sensor Networks

  2009cited by this paper
• Constrained Relay Node Placement in Wireless Sensor Networks to Meet Connectivity and Survivability Requirements

  2008cited by this paper
• Joint Node Placement and Assignment for Throughput Optimization in Mobile Backbone Networks

  2008cited by this paper
• Energy-aware node placement, topology control and MAC scheduling for wireless sensor networks

  2008cited by this paper
• Fault-Tolerant Relay Node Placement in Heterogeneous Wireless Sensor Networks

  2007cited by this paper
• Gateway Placement for Throughput Optimization in Wireless Mesh Networks

  2007influential reference
• Fault-Tolerant Relay Node Placement in Wireless Sensor Networks: Problems and Algorithms

  2007cited by this paper
• Relay Placement for Higher Order Connectivity in Wireless Sensor Networks

  2006cited by this paper
• Deploying sensor networks with guaranteed capacity and fault tolerance

  2005cited by this paper
• On energy provisioning and relay node placement for wireless sensor networks

  2005cited by this paper
• Prolonging sensor network lifetime with energy provisioning and relay node placement

  2005cited by this paper
• Fault-tolerant relay node placement in wireless sensor networks: formulation and approximation

  2004cited by this paper
• On k-coverage in a mostly sleeping sensor network

  2004cited by this paper
• Topology control for wireless sensor networks

  2003cited by this paper
• Impact of Interference on Multi-Hop Wireless Network Performance

  2003influential reference
• Unreliable sensor grids: coverage, connectivity and diameter

  2003cited by this paper
• Node Placement for Connected Coverage in Sensor Networks

  2003cited by this paper
• RHEINISCH-WESTFÄLISCHE TECHNISCHE HOCHSCHULE AACHEN

  2001cited by this paper
• On Generating All Maximal Independent Sets

  1988cited by this paper

• No citing papers are available for this paper.