main-content

## Swipe to navigate through the articles of this issue

Published in:

09-02-2022 | Original Paper

# Novel cluster partitioning models for visible light communication networks

Published in: Photonic Network Communications | Issue 1/2022

## 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.
Literature
1.
Adasme, P., Seguel, F., Dehghan, Firoozabadi, A.: On a clustering partitioning approach for wireless visible light communication networks. In: 2020 IEEE Latin-American Conference on Communications (LATINCOM), pp. 1–6, (2020). https://​ieeexplore.​ieee.​org/​document/​9282330
2.
Adasme, P., Dehghan, F.A.: Degree-constrained k -minimum spanning tree problem. Complex 2020, 7628105:1-7628105:25 (2020). https://​doi.​org/​10.​1155/​2020/​7628105
3.
Adasme, P., Dehghan, F.A.: Facility location with tree topology and radial distance constraints. Complex 2019, 9723718:1-9723718:29 (2019). https://​doi.​org/​10.​1155/​2019/​9723718
4.
Adasme, P.: p-Median based formulations with backbone facility locations. Appl. Soft Comput. 67, 261–275 (2018). https://​doi.​org/​10.​1016/​j.​asoc.​2018.​03.​008 CrossRef
5.
Adasme, P., Andrade, R., Leung, J., Lisser, A.: Improved solution strategies for dominating trees. Expert Syst. Appl. 100, 30–40 (2018). https://​doi.​org/​10.​1016/​j.​eswa.​2018.​01.​031 CrossRef
6.
Adasme, P.: Optimal sub-tree scheduling for wireless sensor networks with partial coverage. Comput. Stand. Interfaces 61, 20–35 (2019). https://​doi.​org/​10.​1016/​j.​csi.​2018.​04.​002 CrossRef
7.
Adasme, P.: Visible light communication networks under ring and tree topology constraints. Comput. Stand. Interfaces 52, 10–24 (2017). https://​doi.​org/​10.​1016/​j.​csi.​2016.​12.​004 CrossRef
8.
Adasme, P., Andrade, R., Lisser, A.: Minimum cost dominating tree sensor networks under probabilistic constraints. Comput. Netw. 112, 208–222 (2017). https://​doi.​org/​10.​1016/​j.​comnet.​2016.​11.​011 CrossRef
9.
Biswas, K., Muthukkumarasamy, V., Sithirasenan, E.: Maximal clique based clustering scheme for wireless sensor networks. In: 2013 IEEE Eighth International Conference on Intelligent Sensors, Sensor Networks and Information Processing, Melbourne, Australia, pp. 237–241 (2013). https://​ieeexplore.​ieee.​org/​document/​6529795
10.
Biswas, K., Muthukkumarasamy, V., Sithirasenan, E., Usman, M.: An energy efficient clique based clustering and routing mechanism in wireless sensor networks. In: 2013 9th International Wireless Communications and Mobile Computing Conference (IWCMC), Sardinia, pp. 171–176 (2013). https://​ieeexplore.​ieee.​org/​document/​6583554
11.
Chu, D., Deshpande, A., Hellerstein, J., M., Hong, W.: Approximate data collection in sensor networks using probabilistic models. In: 22nd International Conference on Data Engineering (ICDE’06), Atlanta, USA, (2006). https://​ieeexplore.​ieee.​org/​document/​1617416
13.
Fortet, R.: Applications de lálgebre de boole en recherche operationelle. Revue Francaise d’Automatique, d’Informatique et de Recherche operationelle. 4, 17–26 (1960)
14.
Ghassemlooy, Z., Popoola, W., Rajbhandari, S.: Optical Wireless Communications: System and Channel Modelling with MATLAB. CRC Press, Inc., (2013)
16.
Melouki, Y., Omari, M.: Simulated annealing approach for clustering in wireless sensor networks. In: 2020 2nd International Conference on Mathematics and Information Technology (ICMIT), pp. 18–19 (2020). https://​ieeexplore.​ieee.​org/​document/​9047029
17.
Oosten, M., Rutten, J., Spieksma, F.: The clique partitioning problem: facets and patching facets. Networks 38, 209–226 (2001). https://​doi.​org/​10.​1002/​net.​10004
18.
Stankovic, J., Wood, A., He, T.: Realistic applications for wireless sensor networks. In: Nikoletseas, S., Rolim, J. (eds.) Theoretical Aspects of Distributed Computing in Sensor Networks. Monographs in Theoretical Computer Science. An EATCS Series. Springer, Berlin, Heidelberg (2011). https://​doi.​org/​10.​1007/​978-3-642-14849-1_​25 CrossRef
19.
Tosun, M., Dagdeviren, O.: New heuristic methods for balanced clustering problem in wireless sensor networks. In: 2019 4th International Conference on Computer Science and Engineering (UBMK), Samsun, Turkey, (2019). https://​ieeexplore.​ieee.​org/​abstract/​document/​8907134
20.
Weitz, R., Lakshminarayanan, S.: An empirical comparison of heuristic methods for creating maximally diverse groups. J. Oper. Res. Soc. 49, 635–646 (1998). https://​doi.​org/​10.​1057/​palgrave.​jors.​2600510
21.
Zhou, Y., Shi, J., Wang, Z., Zhang, J., Huang, X., Chi, N.: Maximization of visible light communication capacity employing quasi-linear preequalization with peak power limitation. Math. Probl. Eng. (2021). https://​doi.​org/​10.​1155/​2016/​6902152 CrossRef
Title
Novel cluster partitioning models for visible light communication networks
Authors
Fabián Seguel
Publication date
09-02-2022
Publisher
Springer US
Published in
Photonic Network Communications / Issue 1/2022
Print ISSN: 1387-974X
Electronic ISSN: 1572-8188
DOI
https://doi.org/10.1007/s11107-022-00963-1

Go to the issue