Joint Task Offloading and Routing in Wireless Multi-hop Networks Using Biased Backpressure Algorithm

Abstract

A significant challenge for computation offloading in wireless multi-hop networks is the complex interaction among traffic flows in the presence of interference. Existing approaches often ignore these key effects and/or rely on outdated queueing and channel state information. To fill these gaps, we reformulate joint offloading and routing as a routing problem on an extended graph with physical and virtual links. We adopt the state-of-the-art shortest path-biased Backpressure routing algorithm, which allows the destination and the route of a job to be dynamically adjusted at every time step based on network-wide long-term information and real-time states of local neighborhoods. In large networks, our approach achieves smaller makespan than existing approaches, such as separated Backpressure offloading and joint offloading and routing based on linear programming.

Resources

• Preprint available soon
• Source code available soon at https://github.com/zhongyuanzhao/edgeSPBP

Related papers (biased Backpressure routing)

• “Biased Backpressure Routing using Link Features and Graph Neural Networks”
• Delay-aware Backpressure Routing using Graph Neural Networks
• Enhanced Backpressure Routing with Wireless Link Features