TY - GEN
T1 - Performance analysis of online matching algorithms for D2D communications
AU - Zorello, Ligia M.M.
AU - Rojas, Marco A.T.
AU - Coupechoux, Marceau
AU - Vaze, Rahul
AU - Carvalho, Tereza C.M.B.
N1 - Publisher Copyright:
© 2017 IEEE.
PY - 2017/12/26
Y1 - 2017/12/26
N2 - In this paper, we consider a Device-To-Device (D2D) cellular network in which idle users can work as relays between cell users and the base station to improve their data rate. The relaying induces a cost for the User Equipment Relays (UER), that should be compensated with a payment from the mobile operator so that UERs accept to offer the service. The problem hence arises for the operator to match cell users and UERs at a reasonable cost and increasing the data rate. In this context, we consider the requirements of truthfulness, budget feasibility and acceptance of online scenarios to compare ON algorithm, which considers all constraints, with other three algorithms that were not built to respect all of them, Hungarian, Threshold and Online Weighted Knapsack (OWK). We observed that ON algorithm is the best in terms of execution time; however, it does not scale well considering the number of matched edges, requiring modifications in its selection criteria. In addition, we noticed that OWK algorithm has appealing properties and, if it were modified to be truthful and to reduce its complexity, it would present the best results.
AB - In this paper, we consider a Device-To-Device (D2D) cellular network in which idle users can work as relays between cell users and the base station to improve their data rate. The relaying induces a cost for the User Equipment Relays (UER), that should be compensated with a payment from the mobile operator so that UERs accept to offer the service. The problem hence arises for the operator to match cell users and UERs at a reasonable cost and increasing the data rate. In this context, we consider the requirements of truthfulness, budget feasibility and acceptance of online scenarios to compare ON algorithm, which considers all constraints, with other three algorithms that were not built to respect all of them, Hungarian, Threshold and Online Weighted Knapsack (OWK). We observed that ON algorithm is the best in terms of execution time; however, it does not scale well considering the number of matched edges, requiring modifications in its selection criteria. In addition, we noticed that OWK algorithm has appealing properties and, if it were modified to be truthful and to reduce its complexity, it would present the best results.
UR - https://www.scopus.com/pages/publications/85046410537
U2 - 10.1109/LATINCOM.2017.8240184
DO - 10.1109/LATINCOM.2017.8240184
M3 - Conference contribution
AN - SCOPUS:85046410537
T3 - 2017 IEEE 9th Latin-American Conference on Communications, LATINCOM 2017
SP - 1
EP - 6
BT - 2017 IEEE 9th Latin-American Conference on Communications, LATINCOM 2017
A2 - Velasquez-Villada, Carlos E.
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 9th IEEE Latin-American Conference on Communications, LATINCOM 2017
Y2 - 8 November 2017 through 10 November 2017
ER -