Novel cluster partitioning models for visible light communication networks

Abstract

In this paper, we consider the problem of clustering nodes in a wireless visible light communication (VLC) network while simultaneously forming a spanning tree backbone. More precisely, let $G=(V,E)$ be a complete Euclidean input graph instance with a set of wireless node devices V and connection links E representing the VLC network. We consider the problem of partitioning $k \le |V|$ nodes into disjoint cliques of the size of at most $\lfloor \frac{k}{t}\rfloor +1$ nodes where $t \le k$ $(k, t \in \mathbb {Z}_+)$ in such a way that a unique vertex of each clique is used to form a spanning tree backbone. The underlying idea is to form clusters of nodes while simultaneously providing connectivity between them. Thus, we maximize the total power received and total residual energy of the k chosen nodes of the network for such a structure. We also consider the simplified version of the problem in which no backbone structure is required. Recall that clustering the nodes of a wireless network allows handling efficiently problems related to scalability and routing. In order to achieve the grouping task optimally, we propose mixed-integer linear and quadratic programming models based on classical combinatorial optimization problems. In order to compare our proposed models, we assume that every node in the network can communicate through a direct-line-of-sight VLC channel. Our numerical results indicate that the linearized quadratic models are preferable as they allow solving to optimality most of the tested instances and in less computational effort.