Controlling-topology-in-flat-networks-Power-control (1)

Page 1: Controlling Topology in Flat Networks

Overview

  • Title: Controlling topology in flat networks - Power control

  • Authors: Naman, Naveen Thakur, Nikhileshwar Katoch

Page 2: Introduction

Topology Control

  • Definition: Managing which nodes communicate with each other.

  • Flat Topology: All nodes are active, performing the same functions.

  • Power Control: Adjusting the transmission power of nodes.

Page 3: Key Complexity Results in Topology Control

Complexity of Power Control

  • The power control problem has many variations, leading to complexity.

Problem Description

  • Defined by a four-tuple (M, P, O, I):

    • M: Graph type (directed or undirected)

    • P: Desired graph property (e.g., connectivity)

    • O: Objective function (e.g., minimize power)

    • I: Additional information (e.g., node positions)

Complexity Examples

  • NP-hard: Minimizing total power for basic connectivity.

  • Efficient Solutions:

    • Minimizing maximum power for basic connectivity.

    • Minimizing maximum power for easily testable properties.

Additional Notes

  • Approximation Algorithms: Exist for NP-hard total power problems.

  • Polynomial-time Algorithms: Available for creating "spanner graphs" to approximate original graphs with constant stretch factors.

Page 4: Are There Magic Numbers?

Bounds on Critical Parameters

Transmission Range

  • Overview: Ensuring connectivity by focusing on each node's transmission range.

  • Power Control Influence: Adjusting transmission power directly influences the distance a node can transmit.

  • Goal: Create a connected network by establishing links within a specific radius.

  • Optimization: Finding minimum transmission range while conserving energy.

Number of Neighbors (k)

  • Approach: Controlling the number of neighbors each node connects to, optimizing throughput and energy efficiency.

  • Magic Numbers: Suggested numbers for k (e.g., k ≈ 8) often maximize progress per hop but do not guarantee connectivity.

  • Dynamic Algorithms: Required to adjust k based on network topology.

Relationship Between Approaches

  • Complexities: Transmission range can correlate with the number of neighbors, but the relationship depends on topology and optimization goals (connectivity vs. throughput).

Page 5: Controlling Transmission Range

Importance of Transmission Range

  • Adjusting power changes how far devices in a network can communicate.

  • Connectivity: Too small of a transmission range reduces connectivity; a larger range increases connectivity but uses more energy— creating a trade-off.

Research Insights

  • Bettstetter's Study: Provided formula estimating connectivity likelihood based on device density.

  • Computational Complexity: Finding optimal transmission range can be complex; approximation methods exist.

  • Key Focus: Minimum range for connectivity across various dimensions (1D, 2D, 3D).

Real-world Implications

  • Calculations are often simplified. Real networks can be unpredictable, and factors like device movement complicate connectivity, potentially reducing required ranges with short disconnections.

Page 6: Controlling the Number of Neighbors

Direct Control of Neighbors

  • Offers a pragmatic approach to managing topology and resource consumption.

Insights from Research

  • Logarithmic Relationship: Between neighbors and network connectivity as found by Xue and Kumar.

  • Critical Neighbor Count: Fewer than 0.074 log |V| leads to disconnection; more than 5.1774 log |V| ensures connectivity.

  • Link Symmetry: Results hold even with strictly asymmetric links, emphasizing practical relevance.

Practical Challenges

  • Maintaining a large number of neighbors increases complexity and overhead.

  • Suggests the need for newer protocols to achieve connectivity with fewer neighbors.

Page 7: Example Constructions and Protocols

Key Topology Control Methods

  • Relative Neighborhood Graph (RNG): Removes longest edge in any triangle, preserving connectivity but might increase energy use.

  • Gabriel Graph (GG): Connects nodes if their defining circle is empty, enhancing energy efficiency but possibly increasing distances.

  • Delaunay Triangulation: Connects nodes with touching Voronoi regions.

  • Spanning Tree-Based Construction: Maintains connectivity while allowing for minimal connections.

Additional Protocols

  • Relay Regions and Enclosures: Minimize energy through defined regions.

  • Cone-Based Topology Control: Directs power increase to maintain neighbor count within angle constraints.

  • Common Power Protocol (COMPOW): Assumes finite levels of power, maintaining overall connectivity.

  • K-NEIGH Protocol: Ensures k neighbors per node through data collection and mutual selection.

Page 8: Further Reading on Flat Topology Control

Suggested Topics

  1. Further Sparsing Constructions: Explore Yao-Yao and similar graphs for network performance.

  2. Hardness Results: Study challenges in minimizing power while maintaining connectivity.

  3. Percolation Theory: Analyze topology control in random networks as power increases.

  4. Distributed Power Control: Compare neighborhood count control methods and their efficiency.

  5. Asymmetric Maximum Power: Study minimal power techniques for varied link ranges.

  6. Power Control and Mobility: Investigate routing protocols under mobile conditions.

  7. Power Control and IEEE 802.11: Adjust power techniques for network efficiency.

  8. Power Control and Code Assignment: Understand optimization challenges.

  9. Impact on Performance Metrics: Examine how power control affects network functionalities.

  10. Cross-layer Aspects: Explore how combining strategies can enhance network performance.