Optimization Model of Structurally Functional Self- Organization of Multi-Radio Multi-Channel Mesh- Networks Using Hypergraphs Serhii Harkusha1[0000-0002-6186-8351], Oleksandr Lemeshko2[0000-0002-0609-6520], Maryna Yevdokymenko3[0000-0002-7391-3068], Oleksandra Yeremenko4[0000-0003-3721-8188] 1 Poltava University of Economics and Trade, Poltava, 3, Koval St., Ukraine 2,3,4 Kharkiv National University of Radio Electronics, Kharkiv, 14 Nauky Ave., Ukraine 1sergiy.garkusha@gmail.com, 2oleksandr.lemeshko.ua@ieee.org, 3maryna.yevdokymenko@ieee.org, 4oleksandra.yeremenko.ua@ieee.org Abstract. A mathematical model with use hypergraph representation for the op- timization of multi-radio multi-channel mesh networks of standard IEEE 802.11 is proposed. Thanks to the use of hypergraphs, it was possible not only to ana- lyze in detail the configurations of the mesh network together with all its ele- ments, but also to distribute non-overlapping frequency channels when solving the routing problem. Thus, using the hypergraph representation of the mesh network, the problem of distributing non-overlapping frequency channels and streaming routing was consistently solved. Keywords: Optimization, Hypergraphs, Multi-radio multi-channel mesh- network, Flow routing model, Non-overlapping frequency channels 1 Introduction Currently ongoing protocol upgrading in the IEEE 802.11 family of standards is aimed at improving the performance of Wireless Local Access Networks (WLAN). At the same time, active efforts are being made to develop and implement a new IEEE 802.11a standard for constructing WLANs. A significant increase in the per- formance of IEEE 802.11ac networks is achieved due to the use of wider channels, improved modulation efficiency (the method of transmitting data bits by radio- frequency waves) and multi-user connections (Multi-User MIMO). Along with the introduction of new standards in WLAN technology, performance improvements can be achieved using multi-hop wireless mesh networks (WMN) of the IEEE 802.11 standard [1]. The highest result with increasing the performance of a wireless network (up to 2-3 times) can be achieved using Multi-Radio Multi-Channel Wireless Mesh Networks (MR MC WMN) [2-4], which implies implementation of both one and several radio interfaces on each mesh station adjusted to different non- overlapping frequency channels (FCs). The high claimed capabilities of the MR MC WMN of the IEEE 802.11 standard are provided, on the one hand, by efficient solu- tions to the problem of the allocation of non-overlapping FCs, and on the other hand, they impose rigid requirements on the effectiveness of network resource management tools and, in particular, on traffic management and routing protocols. Analysis of known solutions for the allocation of non-overlapping FCs [4-12] and routing [13], it is established that they are all based on using the graphical image of WMN, while not ensuring adequate consideration of their features due to the for- mation of the mesh network domain structure. Thus, when simulation MR MC WMN, must use existing, more effective methods of topological representation of a mesh network [14]. To solve the problems of allocation of non-overlapping FCs and routing in MR MC WMN, the approach based on the hypergraph image of the mesh network has proved itself [15, 16]. Within the framework of a hypergraph image, there is a possibility of MR MC WMN mathematical description from the point of view of solving the distribution problem of non-overlapping frequency channels [17, 19] (structural self-organization) and the routing problem [19] (functional self-organization) using a hypergraph image of the mesh network. It should be noted that these tasks of structural and functional self-organization of MR MC WMN using models [17-19] are solved separately at the data link and network layers of the OSI model, while not ensuring their consistency. However, a rather large source of WMN performance lies in increasing the level of consistency in solving the distribution problems of non-overlapping FCs and routing, which can only be achieved by using a unified mathematical description. Therefore, the actual task is to develop a model of structurally functional self-organization of multi-radio multi-channel mesh-networks using hypergraphs that provide consistent solutions for the allocation of non-overlapping frequency channels and routing. 2 Hypergraph Image of Multi-Radio Multi-Channel WMN Within the hypergraph image, as it has been shown in [17, 18], MR MC WMN is associated with a hypergraph H  I , J ; R  , where I is the set of vertices; J is a set of edges; R is a predicate determining the adjacency of stations with stable transmission   ranges (TRs). I  ni , i  1, N , where ni is the element of the set I modeling the MR MC WMN mesh stations; N is their total number in the mesh network.   J  z j , j  1, Z , where z j is the element of the set J modeling the stable transmis- sion range; Z is their total number in MR MC WMN. The predicate R being the incidentor of the hypergraph determines whether the i th station belongs to the stable transmission range. Therefore, in the case, if the i th mesh station involved in shaping of the j th stable transmission range, then the predicate R  ni ,z j   1 , else R  ni ,z j   0 . Thus, the specification of MR MC WMN can be produced using a  hypergraph H  I , J ; R  composed of a pair of vertex I  ni , i  1, N  and edges  J  z j , j  1, Z  sets together with a binary predicate R  R  n , z  defined for all i j ni  I and z j  J [14-16]. 3 Model of Multi-Radio Multi-Channel WMN Non- Overlapping FCs Allocation Based on the hypergraph image of MR MC WMN (Fig.1 and Fig.2), the initial data for the problem of the allocation of non-overlapping FCs solved using the mathemati- cal model [17-20] are presented as:   1. I  ni , i  1, N is a set of mesh-stations where N is their total number in the mesh-network;   2. T  kt , t  1, K is a set of non-overlapping FCs where k t is an element of the set T modelling the t th non-overlapping FCs; K is their total number depending on the used standard of wireless communication. (according to standard of IEEE 802.11b/g technology only 3 or 4 non-overlapping FCs is available, in IEEE 802.11а – 12 FCs, and in IEEE 802.11ac is up to 19 non-overlapping FCs);   3. J  z j , j  1, Z is a set of stable transmission ranges, where Z is the total num- ber of stable transmission ranges in the mesh network; 4. N ( z j )  N H ( z j )   ni  I / R(ni , z j )  is station size of the j th stable transmis- sion range of the mesh-network, that is the number of mesh stations included into the j th TR; 5. mn*i is an integer parameter characterizing the minimum required number of in- cluded MRs at the i th mesh station. In other words, a station is considered to be working if it has one radio interface enabled, thus, parameter m  1 ; mni is a * ni number of MRs supported on the i th mesh station is equal from 1 to 3. So, mesh- station can work simultaneously on one, two or three radio interfaces, due to its technical characteristics. Fig. 1. An example of a possible configuration of a mesh network z1 n3 n8 n9 z2 n1 n4 n6 n5 n10 z3 n2 n11 n13 n7 n12 n15 n23 n22 n20 n14 n25 n17 n21 n16 n24 n19 n18 z5 z4 Fig. 2. Hypergraph representation of MR MC WMN, shown in Fig. 1 Within the framework of the hypergraph image, it is possible to uniquely formalize the rules for the formation of the matrix of stable transmission ranges (TR) introduced in [17-20] using the hypergraph incidence matrix H AH   a z j ,n , (1) i 1, if ith station is included into the jth TR, i.e. R(ni ,z j )  1;  where az j ,ni   0, otherwise, i.e. R(ni ,z j )  0.  Given the expression (1), the TR-matrix is rectangular, the number of rows of which corresponds to the number of stable transmission ranges J , and the number of col- umns corresponds to the total number of mesh stations I in the network. In the framework of the model, in the process of solving the problem of distribu- tion FCs among mesh stations of the network, it is necessary to ensure computation of the Boolean control variable, xni , kt  0,1 ( i  1, N ; t  1, K ), (2) 1, if the tth FC on the ith mesh station is allocated only to one of the MRs; where xn , k   0, otherwise. i t the result of xni , kt  0,1 solving the problem of the allocation of non-overlapping FCs should be the partitioning of the mesh network and of each stable transmission range into connected collision domains, in which the stations operate on the same FC. 3.1 Conditions of Constraints for Solving the Problem of the Allocation of Non-Overlapping FCs When calculating the desired variables xni , kt in each separately considered j th stable transmission range, it is important to observe a number of important conditions of constraints: 1. The condition of including the i th mesh station in the network: K  x t 1 ni , kt  mn*i ( i  1, N ), (3) where 1  mn*i  mni , tK1 xni , kt is the number of FCs distributed to the interfaces of a  single mesh station. 2. The condition for distributing a number of FCs that does not exceed the number of its MRs to the i th mesh station: K  x t 1 ni , kt  mni ( i  1, N ). (4) 3. The condition of two mesh stations cooperation (within the same stable trans- mission range) in not more than one FC is: K t 1  xni , kt  xns , kt  1 ( i, s  1, N ; R(ni , z j )  R(ns , z j )  1 ; z  1, Z ), (5) which is introduced from unwanted structural redundancy. 4. The condition that any mesh station works with at least one mesh station of its TR on the frequency channel it uses: xni , kt  sN1 xns , kt ( R(ni , z j )  R(ns , z j )  1 ; j  1, Z ; t  1, K ),  (6) s i where sN1 xns , k t is the number of the mesh station in the j th stable transmission range  s i (without consideration of the mesh network analyzed), which operates on the t th FC. 5. The connectivity condition of the mesh network (collision domains) in each sta- ble transmission range: K N   x t 1 i 1 ni , k t  N H ( z j )  K  1  b ( j  1, Z ; R (ni , z j )  1 ), (7)  K  N , if K  INT  N m  / 2 ;  provided b    ni 1 ni      0, otherwise.   The expression INT iN1 mni  / 2 in the restriction condition (7) determines the max-  imum number of non-overlapping FCs that can be worked in the RI of the mesh sta- tions. Fulfillment of the condition (7) ensures that the number of used FCs in the j th stable transmission range can be distributed among the RIs of mesh stations included in its structure. 6. The condition for the absence of the effect of a “hidden station”, i.e. a mesh sta- tion that belongs simultaneously to several stable transmission ranges should not op- erate on the same FC with mesh stations of different stable TRs: az j , ni azq , ni xni , kt R ( n , z ) 1 xns , kt R ( n , z ) 1 xnr , kt  0 ,   (8) s q r q R ( ns , z j )  0 R ( nr , z j )  0 provided i  1, N ; t  1, K ; j, q  1, Z ; j  q ; i  s  r . 7. The condition for operation of one of the sets of mesh stations located at the overlapping of several stable transmission ranges and using at least two FCs with mesh stations of different stable TRs:  N  N    N  N    a z j ,ni a zq ,ni xni ,kt xni ,kh   a z j ,ns xns ,kt   a z j ,ns xns ,kh   a zq ,nr xnr ,kt   a zq ,nr xnr ,kh   0;    s 1 s 1  r 1 r 1  (9)  a z j ,ns a zq ,ns  0;  a z j ,nr a zq ,nr  0;   provided t , h  1, K ; t  h ; j  q ; i  s  r . For example, fulfilling the condition az j , ns azq , ns  0 means that the s th station is not at the overlap between the j th and q th stable transmission ranges. 8. The operation condition for at least one of the many mesh stations located with the overlap of several stable TRs on more than one FC: K N   t 1 i 1 a a z j , ni zq , ni   xni , kt  iN1 az j , ni azq ,ni  1   ( j, q  1, Z ; j  q ), (10)  where tK1 iN1 az j , ni azq , ni xni , kt    is the number of included RIs at the mesh stations that are at the overlap between the j th and q th zones of stable transmission ranges; N i 1 a z j , ni azq , ni  is the number of mesh stations located at the overlap between the j th and q th stable transmission ranges. Fulfillment of the condition (10) together with (7)-(9) guarantees that the number of included RIs taking into account the number of mesh stations and the non- overlapping FCs supported in wireless communication technology will ensure the coherence of the multi-channel mesh network. When choosing the optimality criterion, it is necessary, for example, to minimize the interference level, to increase the connectivity of the mesh network and to elimi- nate the effect of the "hidden" station [13] in order to solve the problem of the alloca- tion of non-overlapping FCs. In [20], an approach was proposed to increase the over- all performance of a wireless mesh network based on minimizing the sum of quadratic forms from the number of stations forming the collision domains within a particular TR, 2 min zZ1 kK1  nN1 xn, k dn, z     (11) taking into account the restriction conditions (2)-(10). The use of this criterion will allow to get rid of redundancy when solving the problem of distributing a FC in a multi-radio multi-channel mesh network. The indicated redundancy is expressed in the distributing of the FC for the RI of mesh stations in the network, which might not be used. Using this optimization criterion allows minimizing the number of stations in the collision domains thereby reducing the level of interference and the probability of the collisions themselves [20]. An example of a mesh network resulting from the solution of the problem of allo- cation of non-overlapping FCs using a model (2)-(11) is shown in Fig. 3, and its hy- pergraph image is given in Fig. 4. Fig. 3. An example of MR MC WMN based on the use of five non-overlapping FCs The configuration of MR MC WMN consists of five stable transmission ranges ( Z  5 ), formed by twenty-five mesh stations ( N  25 ). The indicated configuration of the mesh network corresponds to the hypergraph H  I , J ; R  shown in Fig. 4 with a set of vertices I  n1 , n2 , , n25  , a set of stable transmission rang- es J  z1 , z2 , ,z5  and a predicate R ni ,z j   determining whether a certain station belongs to one of the stable TRs. n3 d5 n5 n4 n8 n10 n1 d2 d3 n6 d1 d4 n2 n11 n7 n9 d6 d12 d7 n12 n25 n13 n23 n22 n15 n20 n17 d13 d11 n24 n14 n16 d8 n21 n18 n19 d10 d9 Fig. 4. The hypergraph image of MR MC WMN as shown in Fig. 3 Thus, the hypergraph image MR MC WMN obtained as a result of solving the distri- bution problem of non-overlapping FCs has allowed describing in more complete and detailed form possible configurations of the whole mesh network in general, as well as of its individual elements represented as vertices and edges of the hypergraph. In addition, the mesh network partitioning into collision domains obtained as a result of solving the distribution problem of non-overlapping FCs can be used as a basis for solving the routing problem. However, when solving the routing problem, it becomes necessary to take into account not only the structural, but also the functional charac- teristics of the multi-radio multi-channel mesh network. Therefore, there is a need to formalize the routing task in MR MC WMN presented as a hypergraph. 4 Conclusion The model of structural and functional self-organization with the consistent solution of the distribution problems of non-overlapping frequency channels and flow routing in MR MC WMN of the IEEE 802.11 standard using hypergraphs is proposed. If in the solutions given above the problem of the allocation of non-overlapping FCs has been oriented to obtaining a connected and balanced by the bandwidths of the mesh network structure, in the framework of the proposed model, the solution of these tasks is subject to a single common goal: to improve the end-to-end quality of service in terms of performance due to the coordinated use of network resources of multi-radio multi-channel mesh-networks, which has been especially manifested with an increase in the degree of overlap between the stable transmission ranges, the number of radio interfaces on mesh stations and the number of supported non-overlapping frequency channels in the network. References 1. Raniwala, A., Gopalan, K., Chiueh, T.: Centralized channel assignment and routing algo- rithms for multi-channel wireless mesh networks. ACM SIGMOBILE Mobile Computing and Communications Review. 8, 50-62 (2004) 2. Shin, D., Bagchi, S.: An optimization framework for monitoring multi-channel multi-radio wireless mesh networks. Ad Hoc Networks. 11, 926-943 (2013) 3. Skalli, H., Ghosh, S., Das, S., Lenzini, L.: Channel Assignment Strategies for Multiradio Wireless Mesh Networks: Issues and Solutions. IEEE Communications Magazine. 45, 86- 95 (2007) 4. Ding, Y., Xiao, L.: Channel allocation in multi-channel wireless mesh networks. Computer Communications. 34, 803-815 (2011) 5. Smith, C., Collins, D.: Wireless networks. McGraw Hill Professional (2013) 6. Methley, S.: Essentials of Wireless Mesh Networking. Cambridge: Cambridge University Press (2010) 7. Saini, J., Sohi, B.: Interference Aware, Topology, Power and Flow Control Channel As- signment Algorithm for Multi-Radio Multi-Channel Wireless Mesh Networks. Internation- al Journal of Computer Sciences and Engineering. 6, 939-947 (2018) 8. Kyasanur, P., Jungmin, S., Chereddi, C., Vaidya, N.: Multichannel mesh networks: chal- lenges and protocols. IEEE Wireless Communications. 13, 30-36 (2006) 9. Gogolieva, M., Garkusha, S., Abed, A.H.: A mathematical model of channel distribution in multichannel mesh networks 802.11. In: 11th International Conference The Experience of Designing and Application, CAD Systems in Microelectronics (CADSM), pp. 71–73 (2011) 10. Sridhar, S., Guo, J., Jha, S.: Channel assignment in multi-radio wireless mesh networks: A graph-theoretic approach. In.: First International Communication Systems and Networks and Workshops, Bangalore, pp. 1-10 (2009) 11. Ding, Y., Pongaliur, K., Xiao, L.: Channel allocation and routing in hybrid multichannel multiradio wireless mesh networks. Mobile Computing, IEEE Transactions 12(2), 206-218 (2013) 12. Tang, X., Huang, T., Liu, X., Li, M.: A channel assignment algorithm for multi-radio mul- ti-channel in wireless mesh networks. In: International Conference on Intelligent Compu- ting and Integrated Systems, Guilin, 902-905 (2010) 13. Shreenidhi, P., Puttamadappa, C.: Distributed Efficient Channel Allocation Technique for Multi-Radio Multichannel Interference-aware Multipath Routing Protocol in Wireless Mesh Networks. International Journal of Engineering Research. 4, 426-432 (2015) 14. Gálvez, J., Ruiz, P.: Efficient rate allocation, routing and channel assignment in wireless mesh networks supporting dynamic traffic flows. Ad Hoc Networks. 11, 1765-1781 (2013) 15. Park, P., Jung, B., Lee, H., Jung, D.: Robust Channel Allocation with Heterogeneous Re- quirements for Wireless Mesh Backbone Networks. Sensors. 18, 2687 (2018) 16. Berge, C.: Hypergraphs: The Theory of Finite Sets. North-Holland, Amsterdam (1989) 17. Garkusha, S., Yevdokymenko, M.: Classification and Analysis of Methods of the Distribu- tion Channels in Multichannel Mesh Networks IEEE 802.11. In: XI International Confer- ence Modern Problems of Radio Engineering, Telecommunications, and Computer Sci- ence (TCSET). pp. 273–274. Lviv (2012) 18. Larjomaa, T., Popa, A.: The Min-Max Edge q-Coloring Problem. Journal of Graph Algo- rithms and Applications. 19, 507-528 (2015) 19. Harkusha, S., Harkusha, O., Ievdokymenko, M.: Hypergraph representations of topological model mesh-network IEEE 802.11. In: International Conference on Modern Problems of Radio Engineering, Telecommunications and Computer Science (TCSET), Lviv, Ukraine, pp. 876-878 (2016) 20. Gogolieva, M.: Mathematical model of distribution of frequency channels in multichannel Mesh-networks. In: International Conference on Modern Problems of Radio Engineering, Telecommunications and Computer Science (TCSET), Lviv, Ukraine, pp. 31-31 (2010)