=Paper=
{{Paper
|id=Vol-2386/paper6
|storemode=property
|title=Optimization Model of Structurally Functional SelfOrganization of Multi-Radio Multi-Channel MeshNetworks Using Hypergraphs
|pdfUrl=https://ceur-ws.org/Vol-2386/paper6.pdf
|volume=Vol-2386
|authors=Serhii Harkusha,Oleksandr Lemeshko,Maryna Yevdokymenko,Oleksandra Yeremenko
|dblpUrl=https://dblp.org/rec/conf/momlet/HarkushaLYY19
}}
==Optimization Model of Structurally Functional SelfOrganization of Multi-Radio Multi-Channel MeshNetworks Using Hypergraphs==
https://ceur-ws.org/Vol-2386/paper6.pdf
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
AH 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 , tK1 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 sN1 xns , kt ( R(ni , z j ) R(ns , z j ) 1 ; j 1, Z ; t 1, K ),
(6)
s i
where sN1 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 iN1 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 iN1 az j , ni azq ,ni 1
( j, q 1, Z ; j q ), (10)
where tK1 iN1 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 zZ1 kK1 nN1 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)