Optimization Model of Structurally Functional Self- Organization of Multi-Radio Multi-Channel Mesh- Networks Using Hypergraphs

Abstract

A mathematical model with use hypergraph representation for the optimization 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 analyze in detail the configurations of the mesh network together with all its elements, 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 meshnetwork
• Flow routing model
• Non-overlapping frequency channels

-

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 performance of IEEE 802.11ac networks is achieved due to the use of wider channels, improved modulation efficiency (the method of transmitting data bits by radiofrequency 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 nonoverlapping 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 solutions 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 formation 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 WMN

Image of

Multi-Radio

Multi-Channel

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 transmission 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 ni , z j  defined for all ni  I and z j  J [ 14-16 ]. 3

Model of Multi-Radio

Overlapping FCs Allocation

Multi-Channel WMN Non

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 mathematical 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 kt 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 number of stable transmission ranges in the mesh network; 4. N (z j )  NH (z j )   ni  I / R(ni , z j )  is station size of the j th stable transmission 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 included 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 mni*  1 ; mni is a number of MRs supported on the i th mesh station is equal from 1 to 3. So, meshstation can work simultaneously on one, two or three radio interfaces, due to its technical characteristics. 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   az j,ni , (1) where azj ,ni  0, otherwise, i.e. R(ni , z j )  0.

1, if ith station is included into the jth TR, i.e. R(ni , z j )  1; 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 columns 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 distribution 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 ), tK1 xni ,kt  mn*i ( i  1, N ), tK1 xni ,kt  mni ( i  1, N ).

1, if the tth FC on the ith mesh station is allocated only to one of the MRs; where xni ,kt  

0, otherwise. 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: 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: (2) (3) (4) (5) xni ,kt  sN1 xns ,kt ( R(ni , z j )  R(ns , z j )  1; j  1, Z ; t  1, K ),

si where sN1 xns ,kt 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 stable transmission range: tK1 iN1 xni ,kt  NH (z j )  K 1 b ( j  1, Z ; R(ni , z j )  1 ), (7) K  N , if K  INT  niN1 mni  / 2; provided b  

0, otherwise.

The expression INT  iN1 mni  / 2 in the restriction condition (7) determines the maximum number of non-overlapping FCs that can be worked in the RI of the mesh stations.

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 station that belongs simultaneously to several stable transmission ranges should not operate on the same FC with mesh stations of different stable TRs: az j ,ni azq ,ni xni ,kt R(ns ,zq )1 xns ,kt R(nr ,zq )1 xnr ,kt  0 ,

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: az j ,ni azq,ni xni ,kt xni ,kh  N az j ,ns xns ,kt  N az j ,ns xns ,kh  N azq,nr xnr ,kt  N azq,nr xnr ,kh   0;   s1 s1  r1 r1  az j ,ns azq,ns  0;  az j ,nr azq,nr  0;  provided t, h  1, K ; t  h ; j  q ; i  s  r . For example, fulfilling the condition azj ,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 az j ,ni azq ,ni xni ,kt   N az j ,ni azq ,ni  1 t 1 i1 i1 ( j, q  1, Z ; j  q ), where tK1iN 1azj ,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; iN1azj ,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 nonoverlapping 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 eliminate the effect of the "hidden" station [ 13 ] in order to solve the problem of the allocation of non-overlapping FCs. In [ 20 ], an approach was proposed to increase the overall 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, min Z z1 kK1 nN1 xn,k dn,z  2 (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 allocation of non-overlapping FCs using a model (2)-(11) is shown in Fig. 3, and its hypergraph image is given in Fig. 4. 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 a set of stable transmission ranges J  z1, z2 ,

,z5 and a predicate R  ni , z j  determining whether a certain station belongs to one of the stable TRs.

n1 d1 n23 d13 n3

d2 n2 n24 n25 d12 d11 n22 n21 n4

n5 d3 n7 n20 n18

n6 d10

d4 n12 n17 n19 n8 d5 n9

d6 n15 n16 d9 n10

n11 d8 n14 d7 n13 Thus, the hypergraph image MR MC WMN obtained as a result of solving the distribution 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 characteristics 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 algorithms 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 Assignment Algorithm for Multi-Radio Multi-Channel Wireless Mesh Networks . International Journal of Computer Sciences and Engineering . 6 , 939 - 947 ( 2018 )

8. Kyasanur , P. , Jungmin , S. , Chereddi , C. , Vaidya , N.: Multichannel mesh networks: challenges 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 multi-channel in wireless mesh networks . In: International Conference on Intelligent Computing 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 Requirements 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 Distribution Channels in Multichannel Mesh Networks IEEE 802.11 . In: XI International Conference Modern Problems of Radio Engineering, Telecommunications, and Computer Science (TCSET). pp. 273 - 274 . Lviv ( 2012 )

18. Larjomaa , T. , Popa , A. : The Min-Max Edge q-Coloring Problem . Journal of Graph Algorithms 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 )