TY - JOUR
T1 - The Optimal and the Greedy
T2 - Drone Association and Positioning Schemes for Internet of UAVs
AU - Hammouti, Hajar El
AU - Hamza, Doha
AU - Shihada, Basem
AU - Alouini, Mohamed Slim
AU - Shamma, Jeff S.
N1 - Funding Information:
Dr. Shamma is a recipient of the IFAC High Impact Paper Award, the AACC Donald P. Eckman Award, and the NSF Young Investigator Award, and a past Distinguished Lecturer of the IEEE Control Systems Society. He is currently serving as the Editor-in-Chief for the IEEE TRANSACTIONS ON CONTROL OF NETWORK SYSTEMS. He is a Fellow of IFAC.
Publisher Copyright:
© 2014 IEEE.
PY - 2021/9/15
Y1 - 2021/9/15
N2 - This work considers the deployment of unmanned aerial vehicles (UAVs) over a predefined area to serve a number of ground users. Due to the heterogeneous nature of the network, the UAVs may cause severe interference to the transmissions of each other. Hence, a judicious design of the user-UAV association and UAV locations is desired. A potential game is defined where the players are the UAVs. The potential function is the total sum rate of the users. The agents' utility in the potential game is their marginal contribution to the global welfare or their so-called wonderful life utility. A game-theoretic learning algorithm, binary log-linear learning (BLLL), is then applied to the problem. Given the potential game structure, a consequence of our utility design, the stochastically stable states using BLLL are guaranteed to be the potential maximizers. Hence, we optimally solve the joint user-UAV association and 3-D-location problem. Next, we exploit the submodular features of the sum rate function for a given configuration of UAVs to design an efficient greedy algorithm. Despite the simplicity of the greedy algorithm, it comes with a performance guarantee of $1-1/e$ of the optimal solution. To further reduce the number of iterations, we propose another heuristic greedy algorithm that provides very good results. Our simulations show that, in practice, the proposed greedy approaches achieve significant performance in a few iterations.
AB - This work considers the deployment of unmanned aerial vehicles (UAVs) over a predefined area to serve a number of ground users. Due to the heterogeneous nature of the network, the UAVs may cause severe interference to the transmissions of each other. Hence, a judicious design of the user-UAV association and UAV locations is desired. A potential game is defined where the players are the UAVs. The potential function is the total sum rate of the users. The agents' utility in the potential game is their marginal contribution to the global welfare or their so-called wonderful life utility. A game-theoretic learning algorithm, binary log-linear learning (BLLL), is then applied to the problem. Given the potential game structure, a consequence of our utility design, the stochastically stable states using BLLL are guaranteed to be the potential maximizers. Hence, we optimally solve the joint user-UAV association and 3-D-location problem. Next, we exploit the submodular features of the sum rate function for a given configuration of UAVs to design an efficient greedy algorithm. Despite the simplicity of the greedy algorithm, it comes with a performance guarantee of $1-1/e$ of the optimal solution. To further reduce the number of iterations, we propose another heuristic greedy algorithm that provides very good results. Our simulations show that, in practice, the proposed greedy approaches achieve significant performance in a few iterations.
KW - Binary log-linear learning (BLLL)
KW - UAV-enabled networks
KW - greedy algorithm
KW - potential game
KW - unmanned aerial vehicle (UAV) 3-D placement
KW - users-UAVs association
UR - http://www.scopus.com/inward/record.url?scp=85103760235&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85103760235&partnerID=8YFLogxK
U2 - 10.1109/JIOT.2021.3070209
DO - 10.1109/JIOT.2021.3070209
M3 - Article
AN - SCOPUS:85103760235
SN - 2327-4662
VL - 8
SP - 14066
EP - 14079
JO - IEEE Internet of Things Journal
JF - IEEE Internet of Things Journal
IS - 18
M1 - 9392003
ER -