skip to main content


Title: Optimal Scheduling for Unmanned Aerial Vehicle Networks with Flow-Level Dynamics
Unmanned Aerial Vehicle (UAV) Networks have recently attracted great attention as being able to provide convenient and fast wireless connections. One central question is how to allocate a limited number of UAVs to provide wireless services across a large number of regions, where each region has dynamic arriving flows and flows depart from the system once they receive the desired amount of service (referred to as the flow-level dynamic model). In this paper, we propose a MaxWeight-type scheduling algorithm taking into account sharp flow-level dynamics that efficiently redirect UAVs across a large number of regions. However, in our considered model, each flow experiences an independent fading channel and will immediately leave the system once it completes its service, which makes its evolution quite different from the traditional queueing model for wireless networks. This poses significant challenges in our performance analysis. Nevertheless, we incorporate sharp flow-dynamic into the Lyapunov-drift analysis framework, and successfully establish both throughput and heavy-traffic optimality of the proposed algorithm. Extensive simulations are performed to validate the effectiveness of our proposed algorithm.  more » « less
Award ID(s):
1717108 1815563
NSF-PAR ID:
10192386
Author(s) / Creator(s):
; ;
Date Published:
Journal Name:
IEEE Transactions on Mobile Computing
ISSN:
1536-1233
Page Range / eLocation ID:
1 to 1
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. We consider the load-balancing design for forwarding incoming flows to access points (APs) in high-density wireless networks with both channel fading and flow-level dynamics, where each incoming flow has a certain amount of service demand and leaves the system once its service request is complete. The efficient load-balancing design is strongly needed for supporting high-quality wireless connections in high-density areas. In this work, we propose a Joint Load-Balancing and Scheduling (JLBS) Algorithm that always forwards the incoming flows to the AP with the smallest workload in the presence of flow-level dynamics and each AP always serves the flow with the best channel quality. Our analysis reveals that our proposed JLBS Algorithm not only achieves maximum system throughput, but also minimizes the total system workload in the heavy-traffic regime. Moreover, we observe from both our theoretical and simulation results that the mean total workload performance under the proposed JLBS Algorithm does not degrade as the number of APs increases, which is strongly desirable in high-density wireless networks. 
    more » « less
  2. This paper considers a wireless network where multiple flows are delivering status updates about their respective information sources. An end user aims to make accurate real-time estimations about the status of each information source using its received packets. As the accuracy of estimation is most impacted by events in the recent past, we propose to measure the credibility of an information flow by the number of timely deliveries in a window of the recent past, and say that a flow suffers from a loss-of-credibility (LoC) if this number is insufficient for the end user to make an accurate estimation. We then study the problem of minimizing the system-wide LoC in wireless networks where each flow has different requirement and link quality. We show that the problem of minimizing the system-wide LoC requires the control of temporal variance of timely deliveries for each flow. This feature makes our problem significantly different from other optimization problems that only involves the average of control variables. Surprisingly, we show that there exists a simple online scheduling algorithm that is near-optimal. Simulation results show that our proposed algorithm is significantly better than other state-of-the-art policies. 
    more » « less
  3. null (Ed.)

    This paper introduces a hierarchical traffic model for spread measurement of network traffic flows. The hierarchical model, which aggregates lower level flows into higher-level flows in a hierarchical structure, will allow us to measure network traffic at different granularities at once to support diverse traffic analysis from a grand view to fine-grained details. The spread of a flow is the number of distinct elements (under measurement) in the flow, where the flow label (that identifies packets belonging to the flow) and the elements (which are defined based on application need) can be found in packet headers or payload. Traditional flow spread estimators are designed without hierarchical traffic modeling in mind, and incur high overhead when they are applied to each level of the traffic hierarchy. In this paper, we propose a new Hierarchical Virtual bitmap Estimator (HVE) that performs simultaneous multi-level traffic measurement, at the same cost of a traditional estimator, without degrading measurement accuracy. We implement the proposed solution and perform experiments based on real traffic traces. The experimental results demonstrate that HVE improves measurement throughput by 43% to 155%, thanks to the reduction of perpacket processing overhead. For small to medium flows, its measurement accuracy is largely similar to traditional estimators that work at one level at a time. For large aggregate and base flows, its accuracy is better, with up to 97% smaller error in our experiments.

     
    more » « less
  4. With the rapid growth of wireless compute-intensive services (such as image recognition, real-time language translation, or other artificial intelligence applications), efficient wireless algorithm design should not only address when and which users should transmit at each time instance (referred to as wireless scheduling) but also determine where the computation should be executed (referred to as offloading decision) with the goal of minimizing both computing latency and energy consumption. Despite the presence of a variety of earlier works on the efficient offloading design in wireless networks, to the best of our knowledge, there does not exist a work on the realistic user-level dynamic model, where each incoming user demands a heavy computation and leaves the system once its computing request is completed. To this end, we formulate a problem of an optimal offloading design in the presence of dynamic compute-intensive applications in wireless networks. Then, we show that there exists a fundamental logarithmic energy-workload tradeoff for any feasible offloading algorithm, and develop an optimal threshold-based offloading algorithm that achieves this fundamental logarithmic bound. 
    more » « less
  5. With the rapid growth of wireless compute-intensive services (such as image recognition, real-time language translation, or other artificial intelligence applications), efficient wireless algorithm design should not only address when and which users should transmit at each time instance (referred to as wireless scheduling) but also determine where the computation should be executed (referred to as offloading decision) with the goal of minimizing both computing latency and energy consumption. Despite the presence of a variety of earlier works on the efficient offloading design in wireless networks, to the best of our knowledge, there does not exist a work on the realistic user- level dynamic model, where each incoming user demands a heavy computation and leaves the system once its computing request is completed. To this end, we formulate a problem of an optimal offloading design in the presence of dynamic compute-intensive applications in wireless networks. Then, we show that there exists a fundamental logarithmic energy- workload tradeoff for any feasible offloading algorithm, and develop an optimal threshold-based offloading algorithm that achieves this fundamental logarithmic bound. 
    more » « less