TY - GEN

T1 - Capacitated kinetic clustering in mobile networks by optimal transportation theory

AU - Ni, Chien Chun

AU - Su, Zhengyu

AU - Gao, Jie

AU - David Gu, Xianfeng

N1 - Publisher Copyright:
© 2016 IEEE.

PY - 2016/7/27

Y1 - 2016/7/27

N2 - We consider the problem of capacitated kinetic clustering in which n mobile terminals and k base stations with respective operating capacities are given. The task is to assign the mobile terminals to the base stations such that the total squared distance from each terminal to its assigned base station is minimized and the capacity constraints are satisfied. This paper focuses on the development of distributed and computationally efficient algorithms that adapt to the motion of both terminals and base stations. Suggested by the optimal transportation theory, we exploit the structural property of the optimal solution, which can be represented by a power diagram on the base stations such that the total usage of nodes within each power cell equals the capacity of the corresponding base station. We show by using the kinetic data structure framework the first analytical upper bound on the number of changes in the optimal solution, i.e., its stability. On the algorithm side, using the power diagram formulation we show that the solution can be represented in size proportional to the number of base stations and can be solved by an iterative, local algorithm. In particular, this algorithm can naturally exploit the continuity of motion and has orders of magnitude faster than existing solutions using min-cost matching and linear programming, and thus is able to handle large scale data under mobility.

AB - We consider the problem of capacitated kinetic clustering in which n mobile terminals and k base stations with respective operating capacities are given. The task is to assign the mobile terminals to the base stations such that the total squared distance from each terminal to its assigned base station is minimized and the capacity constraints are satisfied. This paper focuses on the development of distributed and computationally efficient algorithms that adapt to the motion of both terminals and base stations. Suggested by the optimal transportation theory, we exploit the structural property of the optimal solution, which can be represented by a power diagram on the base stations such that the total usage of nodes within each power cell equals the capacity of the corresponding base station. We show by using the kinetic data structure framework the first analytical upper bound on the number of changes in the optimal solution, i.e., its stability. On the algorithm side, using the power diagram formulation we show that the solution can be represented in size proportional to the number of base stations and can be solved by an iterative, local algorithm. In particular, this algorithm can naturally exploit the continuity of motion and has orders of magnitude faster than existing solutions using min-cost matching and linear programming, and thus is able to handle large scale data under mobility.

UR - http://www.scopus.com/inward/record.url?scp=84983251051&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84983251051&partnerID=8YFLogxK

U2 - 10.1109/INFOCOM.2016.7524476

DO - 10.1109/INFOCOM.2016.7524476

M3 - Conference contribution

AN - SCOPUS:84983251051

T3 - Proceedings - IEEE INFOCOM

BT - IEEE INFOCOM 2016 - 35th Annual IEEE International Conference on Computer Communications

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 35th Annual IEEE International Conference on Computer Communications, IEEE INFOCOM 2016

Y2 - 10 April 2016 through 14 April 2016

ER -