Minimum Overhead Beamforming and Resource Allocation in D2D Edge Networks

Junghoon Kim, Taejoon Kim, Morteza Hashemi, David J. Love, Christopher G. Brinton

TL;DR

This paper tackles the challenge of minimizing the combined time and energy overhead for distributed computing in Device-to-Device (D2D) edge networks. They introduce a novel optimization framework that jointly considers network topology, task assignment, CPU allocation, subchannel selection, and MIMO beamforming, proposing two algorithms to solve this complex problem. Their "efficient alternate optimization" method offers significant overhead reductions compared to local processing and scales well for large networks.

What Problem Does This Paper Address?

The proliferation of data-intensive applications and the limitations of centralized cloud computing are driving a shift towards edge computing. D2D networks, where devices communicate directly, are a promising architecture for this distributed edge computing. However, efficiently managing the diverse communication and computation resources across these numerous devices to meet processing demands is a significant challenge. This paper addresses the problem of minimizing the total overhead (defined as a weighted sum of time and energy) incurred by processing tasks in D2D edge networks, considering the complex interplay between network topology, resource allocation, and communication parameters.

Methods

The authors formulate a comprehensive optimization problem to minimize total D2D network overhead. This problem involves several decision variables:

  • Task Assignment: Deciding whether a task is processed locally or offloaded to another device.
  • CPU Allocation: Assigning processing power to tasks on each device.
  • Subchannel Selection: Choosing communication channels for data transmission.
  • Beamforming Design: Optimizing MIMO transmit and receive signals to manage interference.

To solve this non-convex mixed-integer program, they propose two methods:

  1. Semi-Exhaustive Search Optimization: This method explores a large number of possible task assignments and subchannel selections, then solves for the remaining continuous variables. It aims for optimality but has exponential complexity.
  2. Efficient Alternate Optimization: This is a more computationally tractable approach that iteratively optimizes different subsets of variables. A key component is their novel Minimum Communication Overhead Beamforming (MCOB) algorithm, which is derived to optimize beamformers for a specific MMSE receiver characteristic.

Datasets

Not discussed in the paper. The experiments utilize simulated data based on common parameters for mobile computing environments and cellular networks.

Key Insights and Ideas

  • Joint Optimization is Crucial: Optimizing communication and computation resources together with network topology and task assignment yields significantly better results than optimizing subsets of these factors.
  • D2D's Unique Challenges: D2D networks introduce complexities beyond traditional Mobile Edge Computing (MEC) due to their dynamic topology and multi-directional offloading, requiring a more holistic optimization approach.
  • MCOB for Efficient Beamforming: The proposed MCOB algorithm effectively minimizes communication overhead by considering both time and energy, going beyond traditional sum-rate objectives.
  • Trade-offs are Manageable: The framework allows for adjusting the balance between time and energy objectives using an "overhead demand factor" (β), demonstrating flexibility for different application needs.
  • Robustness to Imperfect CSI: The proposed methods show resilience to imperfect channel state information, a realistic scenario in wireless networks.

Key Results

  • Significant Overhead Reduction: The proposed "efficient alternate optimization" method achieved overhead reductions of 19% to 27% compared to local computation for small D2D networks.
  • Scalability: The efficient alternate optimization algorithm scales well with the number of nodes, demonstrating polynomial complexity (approximately K^2.4 in practice, compared to theoretical K^3), making it suitable for large networks.
  • Performance Comparison: The efficient alternate optimization achieved performance comparable to the semi-exhaustive search (which is computationally infeasible for larger networks) and significantly outperformed baselines that used only partial optimization (e.g., equal CPU allocation or WMMSE for beamforming).
  • Interference Management Benefits: Increasing the number of subchannels (S) and antennas (N) further reduced communication overhead, with MCOB showing substantial improvements over WMMSE.
  • Dynamic Scenario Viability: The framework was shown to be applicable to dynamic task generation scenarios, achieving overhead reductions of 15% to 30% over multiple optimization frames.

Limitations and Future Work

  • Quasi-Static Assumption: The current model assumes quasi-static network conditions and fixed channels within a time period. Future work could extend this to fully dynamic scenarios.
  • Centralized Control: The current methodology relies on a centralized operator (e.g., BS) for optimization. Future work could explore decentralized or distributed implementations.
  • Task Result Return: The paper does not consider the overhead of returning the processed task result to the source node, assuming it's negligible.
  • Future Directions:
    • Extending the model to dynamic task generation over a long-term horizon using stochastic optimization.
  • Developing fully distributed implementations of the optimization algorithms.
  • Incorporating additional overhead components like waiting latency and handover latency.
  • Investigating the impact of imperfect CSI more deeply.
  • Optimizing the frame rate for dynamic scenarios.

Summary updated

Abstract

Device-to-device (D2D) communications is expected to be a critical enabler of distributed computing in edge networks at scale. A key challenge in providing this capability is the requirement for judicious management of the heterogeneous communication and computation resources that exist at the edge to meet processing needs. In this paper, we develop an optimization methodology that considers the network topology jointly with device and network resource allocation to minimize total D2D overhead, which we quantify in terms of time and energy required for task processing. Variables in our model include task assignment, CPU allocation, subchannel selection, and beamforming design for multiple-input multiple-output (MIMO) wireless devices. We propose two methods to solve the resulting non-convex mixed integer program: semi-exhaustive search optimization, which represents a “best-effort” at obtaining the optimal solution, and efficient alternate optimization, which is more computationally efficient. As a component of these two methods, we develop a novel coordinated beamforming algorithm which we show obtains the optimal beamformer for a common receiver characteristic. Through numerical experiments, we find that our methodology yields substantial improvements in network overhead compared with local computation and partially optimized methods, which validates our joint optimization approach. Further, we find that the efficient alternate optimization scales well with the number of nodes, and thus can be a practical solution for D2D computing in large networks.
BibTeX
@article{kim2022minimum,
  author = {Junghoon Kim and Taejoon Kim and Morteza Hashemi and David J. Love and Christopher G. Brinton},
  title = {{Minimum Overhead Beamforming and Resource Allocation in D2D Edge Networks}},
  journal = {IEEE/ACM Trans. Networking},
  year = {2022},
  url = {https://openreview.net/forum?id=obGpuLWRNC},
}
Figure