Maximizing Support for Dense Machine-to-Machine Wireless Networks Through Optimized Cluster Formation and Resource Management

Clustering of machines for better spatial reuse has been considered as one key technology for supporting machine-to-machine (M2M) communications with a large number of communicating devices. Most related work, however, focuses on developing distributed clustering algorithms and protocols with simple or no wireless interference models, and thus they can not be applied for interference-limited M2M communications with high machine density. In this thesis, we consider a scenario where clustered machines through proper transmission power control are allowed to reuse the spectrum occupied by human devices and we investigate the optimization problem that jointly handles cluster formation and resource management for all machines in the network. To maximize the number of machines that can communicate without violating the data rate constraints of human devices and machines themselves, we formulate a mixed-integer non-linear programming (MINLP) problem. Since the MINLP problem becomes too complex when the number of machines increases, we propose an algorithm that transforms the problem into a coalition structure generation sub-problem embedded with a resource allocation sub-problem. The proposed algorithm is an anytime algorithm and hence the length of the running time can be arbitrarily controlled while still yielding a feasible solution with non-decreasing quality. Compared with other approaches of solving the original MINLP problem, we show through numerical results that the proposed algorithm can e ectively solve the joint cluster formation and resource management problem in the target scenario. Evaluation results also show the benefits of joint optimization with an increase in the number of supported machines up to 70% for a dense network with a large number of clusters. We conclude that clustering formation should take power control and resource allocation into consideration for e ectively supporting M2M communications with high density.