Journal of Ambient Wireless Communications and Smart Environments (AMBIENTCOM)

Vol: 1    Issue: 1

Published In:   July 2015

Resource Allocation in Wireless Mesh Networks

Article No: 2    Page: 25-48    doi: https://doi.org/10.13052/ambientcom2246-3410.112    

Read other article:
1 2

Resource Allocation in Wireless Mesh Networks

M. Priesler (Moreno) and A. Reichman

Ruppin Academic Center, Emek Hefer, 40250 Israel

E-mail: {arier; mirip} @ ruppin.ac.il

Received 23 January 2015; Accepted 5 June 2016;
Publication 25 July 2016

Abstract

A wireless network with a mesh topology works reliably and offers redundancy. In modern broadband wireless mesh networks using MIMO and OFDMA techniques, the problems of time, frequency, and space resource allocations, synchronization, and routing, are not only different from a cellular system, they are more complicated due to system architecture and distributed control and management. This paper focuses on OFDMA wireless mesh network systems and the problem of time/frequency resource allocation, particularly with regard to subcarriers.

The term of separability order is defined. For simple topologies such as the square grid configuration, the allocations are relatively simple, and optimal solutions can be demonstrated, but in an arbitrary architecture advanced graph theory tools are required in order to present an algorithmic solution to resource allocation and allow frequency reuse.

Keywords

  • Wireless mesh networks
  • OFDMA
  • resource allocation
  • sub- carrier allocation
  • graph colouring
  • graph theory
  • graph algorithms

1 Introduction

1.1 Broadband Wireless Mesh Networks

A wireless mesh network (WMN) [1, 2] is a communications network made up of radio nodes (hops) organized in a mesh topology, usuallycomposed of mesh clients, mesh routers, and gateways. Wireless Sensors Networks is a special kind of WMN in which many of the nodes are connected to sensors, and the sensors' information must be passed to other nodes or transferred to a concentrator for central processing. The WMN enables rapid deployment with lower-cost backhaul and may provide coverage in hard-to-wire areas and greater rangedue to multi-hop forwarding. Interest in this type of network increases in parallel to the developments of cellular systems, and it has its own merit. A~wireless network with a mesh topology is reliable and redundant. When one node can no longer operate, the rest of the nodes can still communicate with each other, directly or through one or more intermediate nodes.

Modern broadband networks use multiple antennas at both transmitter and receiver (MIMO – multiple input multiple output) and multicarrier transmission techniques (OFDMA – orthogonal frequency division multiple access) [3, 4]. Wireless mesh networks can be implemented with various wireless technology, including 802.11, 802.16, cellular technologies, or combinations of several types.

This paper focuses on the resource allocation problem of the OFDMA wireless mesh networks system The problems of time, frequency, and space resource allocations, synchronization, and routing, are not only different from a cellular system, they are more complicated due to system architecture and distributed control and management. The allocation of frequency resources in OFDMA WMN has unique characteristics due to WMN spatial architecture, which differs from cellular network spatial architecture, and because the OFDMA channel can be split into sub-bands of subcarriers. Methods of dynamic subcarrier assignment in OFDMA WMN are shown in [57] using cross-layer optimization, taking into account interference among links, adaptive power allocation, and admission control. In [8, 9] a different approach is taken: the authors used graph theory for allocation of time and frequency resources. In this paper, the concepts are reviewed and new methods and results are added.

1.2 Resources Allocation in WMN-Modelling and Motivation

The design of WMN consists of multitude of topics at all layers of communication and control. The approach taken in this paper is based on the following assumptions.

  1. Resource allocation and routing.

    In a meshed system, the packet transfer is based on various processes of resource allocation and routing. We assume that the links variations are slower than the rapid requirements of packets routing, and therefore we propose the approach of managing the processes of resource allocation and routing separately; the routing will be done on a network with links, which have resource allocations.

  2. Centralized versus distributed resource allocation algorithm.

    Although the centralized approach is less practical than a distributed algorithm, it does give bounds to the performance that can be obtained by a distributed algorithm.

  3. Communication and interference among links

    We assume that connection between two nodes is possible if the signal of noise and interference ratio, SNIR is above a minimal level (threshold). After resources are allocated to a specific link, the spectral efficiency of the link can be adapted to the variations of SNIR by using more effective coding and modulations schemes for higher SNIR links. It is possible that a signal received with a SNIR is bellow threshold may interfere with other signals with the same resource allocated. In this paper we assume that a signal below threshold does not interfere.

  4. Perfect grid and general grids.

    We refer to networks of general topography; however, we refer to networks of specific topologies such as perfect grids of squares and triangles, even if they do not have practical importance, in order to illustrate the relation between the resource requirements and the connectivity of a network. The regular grid is also a initial tool to cover areas in a similar way a generic cellular system is represented by hexagonal cell. For square and triangle grids, optimal solutions are shown in the paper.

    For general networks, algorithms provide tools for global solutions. The algorithms are novel, and their advantage is their ability to obtain an assessment of the resources required globally in the system.

  5. Synchronization.

    The topic of synchronization in WMN is treated in [14] where solutions are proposed.

In Section 2, we present the resource allocation problem in OFDMA WMN, define separability and give the rules for allocation. In Section 3, square grid and triangle grid solutions are given for regular WMN structures, proving that these solutions are optimal. In Section 4, two algorithms are given: one for allocations without splitting bands into subcarriers, and one that includes allocation of subcarriers.

2 Resource Allocation

2.1 Resources and Separation Order

This paper considers the following shared resources:

  • Time: The system may operate with time slots division, requiring network synchronization.
  • Frequency: The frequency division can be among different OFDMA bands, inter-band, or among different subcarriers in the same OFDMA band, intra-band. A group of subcarriers dedicated to a certain purpose, such as transmission for a specific user, forms a sub-band.
  • Space: Frequency reuse can be made using spatial separation:
    • Among geographically separated links.
    • Among different transmission directions using MIMO or directional antennas.
    • Among different reception directions using MIMO or directional antennas.

We define [4] the time frequency separation order (TF-SO) λTF as the number of combinations of time slots and frequency bands which give practical separation among such combinations (not according to frequency sub-bands). If NT is the number of time slots and NFB is the number of frequency bands, then TF-SO is determined by:

λTF=NT·NFB(1)

For example, with four time slots and two frequency bands, the TF-SO is λTF = 8.

With multiple antennas, the spatial domain can be used to create additional degrees of freedom for communications. Utilizing multiple antennas may result in additional spatial channels. The TF-SO may be modified to include the space separation. Assuming that for each terminal we have directional antennas that divide the space in NsS sectors, we can extend the TF-SO to time, frequency and space separation order (TFS-SO) λTFS, according to the number of combinations of time slots, frequency bands, and angular directions that offer practical separation among such combinations. The TFS-SO is determined by:

λTFS=NT·NFB·NS(2)

However, since the number of angular directions of each terminal is not fixed, the separation varies with time. Therefore, we must find an effective (average) TFS-SO factor with an effective number of sectors NS.eff:

λTFS.eff=NT·NFB·NS.eff.(3)

2.2 Separation Rules and Separation Order Extension

In each slot, all frequency bands may be used according to non-collision rules:

  • A node may not transmit and receive in the same time slot in the same frequency band.
  • All transmissions from one node to other nodes in the same time slot and same frequency band should have different frequency sub-bands.
  • All receptions at a node from other nodes in the same time slot and same frequency band should have different frequency sub-bands. This includes intentional transmissions to this node as well as interferences, i.e., transmissions from another node’s area of reception not intended for this node.

The intraband division does not give the same level of separation as different time slots and different frequency bands due to the additional constraints imposed. The extension of the notion of separation order that includes the effect of the sub-bands is denoted as extended separation order of time and frequency λxTF, or time, frequency and space λxTFS. For example, in cases where each band has the same number of sub-bands NFSB, the extended separation order is give by λxTF = NFSB ⋅ λTF or λxTFS = NFSB ⋅ λTFS.

The separation order defines the number of combinations of time slots, frequency bands, and frequency sub-bands (and of angular directions). Each such combination is called a resource element (or briefly – elements).

2.3 Formal Resource Allocation Problem

In the remainder of this section, we use graph theory methods and terminology [1012], where each terminal having a transmitter and a receiver becomes a vertex and the links become edges.

If V is a set of topologically allocated vertices, and R is an upper bound on the distance between any two communicating vertices (that is, the distance between any two vertices does not exceed R) then they can communicate, and thus we connect them by a pair of anti-parallel edges.

Therefore, the set of vertices, V, and the upper bound on the distance, R, induce a directed graph G = (V,E(V,R)) where E denotes the set of edges connecting the vertices V within the distance R.

A resource allocation on G defines a set of λTFS combinations of time slots and frequency bands, denoted by “resource elements” (or simply “elements”), such that every edge of G uses one resource element of the set. Therefore, a resource element can be represented as pairs of the type (time, band).

2.4 Resource Allocation Constraints

The resource elements allocated on the edges of G must obey the following collision rules:

  1. For every vertex vV , all the simultaneous broadcasting from v, and to v, are mutually disturbing.
  2. Moreover, if a vertex x transmits to a vertex y, then y is disturbed by the transmissions of x to other vertices, and such transmissions may disturb y’s reception of transmission from other vertices. Therefore, transmissions from x and transmissions to y should be allocated by different resource elements.

We hence define two edges (u,v), and (x,y), with resource elements f1 and f2, respectively, to be mutually undisturbed if and only if they satisfy the following demands:

  • Vertices u, v, x, and y are all distinct, and
  • Edges (x,v), (u,y) do not exist in G.

It follows that if directed edges (u,v) and (x,y) are not mutually undisturbed, then they are mutually disturbed, and every pair of transmissions set on this pair of edges is also mutually disturbed.

A proper allocation is defined as a setting of resource elements on all edges of G, such that no two edges of G are mutually disturbed. Our goal is to set a proper allocation on the edges of G using as few different resource elements as possible.

According to topological conditions, for every two vertices (x,y) of the graph G, the directed edge (x,y) belongs to G if and only if its anti-parallel edge (y,x) belongs to G. Therefore, according to the given resources allocation conditions, for every two directed edges (x,y),(z,w) of the graph G, the edges (x,y),(z,w) are mutually disturbed if and only if their anti-parallel edges (y,x),(w,z) are mutually disturbed.

This means that we do not have to track all of the directed edges of G. Instead, we can set one element on one of the directed edges of every anti-parallel pair of edges of G. Afterward, we can double every used resource element by defining for every used element c a new supplement element c′, and then for every used element c, to set the element c′ on every directed edge (x,y) such that its anti-parallel edge (y,x) was set to the element c.

Practically speaking, for the rest of our discussion, a resources allocation description of G may include the resource element allocation of exactly one directed edge of every anti-parallel pair of edges of G, such that for every used couple of an element and its supplement, (c,c′), the description includes all the directed edges that are set by one of these elements (c,c′), and none of the edges that are set by its supplement element.

In the following sections, we present algorithms for solving this problem that use as few resources elements as possible.

2.5 Resource Allocation Constraints with One Frequency Band

Often, practical considerations restrict us to only one frequency band. According to the previous solution, we need to use many time slots (λTFS to be precise). In order to reduce the number of required time slots, we should use a subdivision of the band into sub-bands. In this case, we need to take into consideration an additional non-collision rule:

  1. No vertex can receive and transmit with the same band in the same time slot, even if it uses different sub-bands of that band.

This means that every two edges that are mutually disturbed according to collision rules 1 and 2 (Section 2.4), may not be set by sub-bands of the same element unless they are both out-going edges of the same vertex or in-going edges of the same vertex. A proper allocation is defined as the setting of resource elements on all edges of G such that no two edges of G are mutually disturbed according to the three collision rules. It also means that all the vertices with the same sub-band allocation in the same time slot are non-adjacent, i.e., they perform an independent set of G. Since G contains at least one edge, then according to the third rule, the solution with several sub-bands requires at least two such independent sets of G, i.e., at least two different time slots. A solution to the problem may be regarded as partitioning the vertices of G into distinct independent sets, and allocating the sub-bands on out-going edges of the vertices of every such independent set: the union of the allocations of all independent sets is obviously a proper allocation on the edges of G.

3 Solution of Resource Allocation in Perfect Grids

3.1 Solution of the Perfect Square Grid Example

A perfect square grid serves as an example of resource allocation. We designate the vertex coordinates as (i,j), where i and j are integers.

According to the definition of a graph in Section 2.3, the communication range R is 1<R<2; only the four closest neighbors can communicate directly in a perfect grid graph.

Lemma:The minimum number of resource elements to be allocated on the edges of the square grid, without causing disturbances, is λxTF = 8.

Proof: First observe any vertex of the grid and the four edges adjacent to it. If any pair of these edges is allocated to the same resource element, then these two edges will be in disturbance. To avoid disturbances, we need to set different resource elements on those four edges. Since every bi-directed transmission on an edge must use two different elements, then we need to allocate eight different resource elements on those four anti-parallel edges. Therefore, we need at least eight different elements for every disturbance-free allocation of elements on the grid.

To terminate the proof, we present a collision-free allocation of one resource element on every edge of the grid in each direction, using eight different resource elements: We set the element

|Δi|·[ (iΔi12)mod4 ]+|Δj|·[ 4+(jΔj12)mod4 ](4)

on each edge of the grid, going from vertex (i,i′) to vertex (j,j′), where Δi = i′-i, and Δj = j′- j.

More precisely:

Allocation of elements on horizontal edges : For the directed edges connecting the vertices (i, j) and (i + 1, j), we set the element (i mod 4), and on the directed edges connection the vertices (i, j) and (i- 1, j), we set the element ((i + 1) mod 4).

Allocation of elements on vertical edges: For the directed edges connecting the vertices (i, j) and (i, j + 1), we set the element (4 + (j mod 4)), and on the directed edges connection the vertices (i, j) and (i, j - 1), we set the element (4 + (j + 1) mod 4)).

It is easy to verify that no pair of edges is in disturbance on this allocation with four resource element pairs, and thus, if the number of resource elements per edge is doubled, one for each direction, we get a non-disturbing allocation of eight resource elements on the edges of the grid.

The resources for a square grid are shown in Figure 1. The numbers 0 to 7 represent resource elements, one for each direction. On the horizontal edges, the number above the edge represents the resource element in the direction to the right, and the number below the edge represents the resource element in the direction to the left. On the vertical edges, the number left of the edge represents the resource element in the up-going direction, and the number right to the edge represents the resource element in the down-going direction.

3.2 Solution of the Perfect Square Grid Example for One Frequency Band

Often practical considerations require a restriction to one frequency band. Therefore, we must use different time slots and may use subdivision of the band into sub-bands, and limitations must be taken into consideration according to the three non-collision rules.

Figure 1 Optimal resource allocation for a square grid.

As explained in Section 2.5, every proper allocation should use at least two time slots. On the other hand, since there exists a proper allocation of the grid with eight elements (Section 3.1), then there exists a proper allocation of the grid with eight time-slots and one band: in this case, each of the numbers 0–7 of Figure 1 represents a different time slot. Therefore, we need only to regard the allocation of the grid using at least two but no more than seven time slots.

Following are solutions with two time slots and four time slots

The solution for four time slots is based on the resources allocation of Figure 1. In this case, the numbers 0–7 do not represent different bands or different slots, as on the previous section; they represent sub-bands of the single band. We designate the two resource elements related to an horizontal link i as iandi and the two resource elements related to an vertical link j as jandj.

The proposed allocation with four time slots has four sub-bands in each time slot. The active transmissions in each one of the four time slots are on either horizontal edges or vertical edges, while the directions of the edges alternate, that is:

Slot 11and0;3and2Slot 22and1;0and3Slot 3.  5and4;7and6Slot 4.6and5;4and7

Each time slot has four sub-bands that occupy the full band. If all the sub-bands are equal to one fourth of the band, we can allocate the same sub band to 0in slot 1, to 0 in slot 2, to 4 in slot 3 and to 4in slot 4. Each node is transmitting in two time slots out of the four. For example, the node located at (1,1):

Slot 1.  Receives3and0Slot 2.  Transmits 2and1Slot 3.Receives7and4Slot 4.Transmits6and5

According to the links connected to each node, there are 16 types of nodes, and each node type has a different template of operation.

We propose another example of a single frequency band with two time slots and eight sub-bands, according to the allocation in Figure 1. Each time slot has eight sub-bands, which share the full band:

Slot 1. Transmission from all vertices (i,j) of the grid, such that i+j is even.

Slot 2. Transmission from all vertices (i,j) of the grid, such that i+j is odd.

The allocation of the two time slots is presented in Figure 2 according to the allocation presented in Figure 1. Blue dots are transmitting in the first time slot, using the blue sub-bands, and red dots are transmitting in the second time slot, using the red sub-bands.

images

Figure 2 Blue and red time slot allocations.

3.3 Solution of the Perfect Triangle Grid Example

A perfect triangle grid serves as an additional example of resource allocation. Assuming that the communication range R is 1<R<3, then only the six closest neighbors can communicate directly, which defines a perfect triangle grid graph.

Lemma:The minimum number of resource elements, to be allocated on the edges of the perfect triangle grid graph, without causing collisions, is λxTF = 18.

Proof: First regard any vertex v of the grid and the six anti-parallel couples of directed edges adjacent to it. According to the collision constraints, they all must be allocated by different elements. Define the neighbours of v by x0, x1, x2, x3, x4, x5 such that for every 0 ≤ i < 6, there exists a pair of anti-parallel directed edges between xi and xi+1(mod6). It is easy to verify that every directed edge between any two neighbours of v is mutually disturbed with every directed edge that is adjacent to v. Moreover, the edges adjacent to any neighbour xi of v, 0 ≤ i < 5, are mutually disturbed. That defines 16 edges (8 pairs of anti-parallel edges), mutually disturbed in pairs, adjacent to v and to, say x0, as described in Figure 3.

images

Figure 3 Eight pairs of edges, mutually disturbed, in pairs.

For every edge e of G, let c(e) denote the resource element allocated on the edge e. In order to avoid the use of more than the eight element couples, we must set c(x2,x1) = c(x5,x0), and c(x5,x4) = c(x0,x1) (where their anti-parallel edges are obviously set the opposite elements, i.e., c(x0,x5) and c(x1,x0) respectively). We thus must set c(x3,x2) = c(x0,x1). Hence c(x5,x4) = c(x0,x1) = c(x3,x2), which means that the mutually disturbed edges (x5,x4) and (x3,x2) are allocated the same element. The symetric arguments lead to the symetric conclusion that also c(x4,x5) = c(x1,x0) = (cx2,x3). Therefore, in order to allocate the elements properly on the triangle grid, we must use at least nine couples of different resource elements.

To terminate the proof, we present a collision-free allocation of one resource element on every edge of the grid, using nine different couples of resource elements: elements 1, 2, 3 on horizontal edges, elements 4, 5, 6 on edges set on lines parallel to the line Y = X of the plain, and elements 7, 8, 9 on edges set on lines parallel to the line Y = –X of the plain. The solution is described in Figure 4, such that the anti-parallel edge of each edge with element i, is set with the element i′.

images

Figure 4 Resource allocation description for a triangle perfect grid.

4 General Structure Resources Allocation

4.1 Resources Allocation Algorithm for Time Slots and Frequency Bands

In this chapter, the case of a general mesh system is approached. The following algorithm A uses the graph theory concept of “vertex coloring” to set the same element only on edges that are “far enough” from each other. Its main idea is to use the given directed graph in order to build an undirected graph, such that a proper colouring of that graph is equivalent to a proper solution of the original graph.

4.1.1 Description of Algorithm A

Input:

  • A set V of topologically allocated vertices V
  • An upper bound on the distance R
  • A set F of elements (assume that F is large enough)

    Step 1. Build the directed graph G = (V,E) from V according to R (as suggested in the problem description).

    Step 2. Build the graph G′ = (E,E′) from G such that for every e1,e2 ∈ E,(e1,e2) ∈ E′ if and only if e1,e2 are mutually disturbed.

    Step 3. Colour the edges of E by using as few colours as possible, such that the end vertices of every edge of G′ are coloured differently.

    Step 4. The colours of E in G′ are the colours of E in G.

Output: A proper resource allocation of G.

4.1.2 Discussion of Algorithm A

A proper colouring of a graph is setting colours on its vertices, such that the end vertices of every edge of the graph are set with different colours. Obviously, if the graph G′ is properly coloured by the minimum number of colours, then the algorithm sets as few elements as possible to the edges of G. Unfortunately, the problem of properly colouring the vertices of an undirected graph with the minimum number of colours is known to be NP-hard [13]; that is, mathematicians believe that no polynomial time algorithm exists for solving this problem. Therefore, we must settle for the random colouring of the vertices of G′, as suggested above.

While randomly colouring the vertices of a graph G, the neighbours of any vertex x of G may use d(x) different colours, where d(x) is the number of the neighbours of x, so the vertex x may need an extra colour. That ensures the use of no more than Δ(G′) + 1 colours to colour the vertices of G′ properly, when Δ(G′) is the maximum degree among all vertices of G′. On the other hand, every edge e of G with an end-vertex v of degree Δ(G), is incident with at least all other Δ(G) – 1 edges of v, and thus that edge e represents in G′ a vertex with at least Δ(G) – 1 neighbours. Therefore, at least Δ(G) – 1 colours are required to colour G′ properly. Those two bounds result the following inequation for the minimum number of resource elements (colours), m(G), required to be allocated on the edges of G such that all transmissions are collision-free:

Δ(G)1m(G)Δ(G)+1(5)

4.1.3 Example of Algorithm A

Below are figures illustrating how Algorithm A (Example 1) runs on a given undirected graph. Figure 5 illustrates Step 1 of the algorithm of building the given graph, and Figures 6 and 7 illustrate Step 2 of the algorithm of naming the edges E of the graph to build the graph G′, such that the edges E of G serve as the vertices of G′. Figure 8 illustrates Step 3 of the algorithm of randomly colouring E in G′. Since the number of edges of G′ in this example is too big, for the simplicity of the figures, we preferred to draw the complement graph of G′ instead of G′ itself (i.e., the non-edges of G′), which is a smaller graph. We also painted the edges of this graph with 3 different paints so that it would be easier to keep tracking of its edges. Notice that the random colouring of the vertices E of G′ in this example, is done by the alphabetic order, a0,a1, …, g0,g1. Finally Figure 9 illustrates Step 4 of the algorithm, which is the colours of E in G and the final result. In this example the colouring turns to be optimal, and uses the minimum number of 10 colours to colour E properly.

images

Figure 5 Algorithm A, Step 1: The given graph G = (V,E).

images

Figure 6 Algorithm A, Step 2: Naming the edges of G.

images

Figure 7 Algorithm A, Step 2: The complement graph of G′.

images

Figure 8 Algorithm A, Step 3: Colouring E in G′ randomly – 10 colours are required.

images

Figure 9 Algorithm A, Step 4: The resulting allocation – optimal colouring of E in G.

4.2 Resources Allocation Algorithm for Sub-Bands

This chapter deals with the general mesh system approach, such that each band may be divided to sub-bands.

We thus present the following Algorithm B that imitates Algorithm A to allocate as few elements as possible to the edges of the given graph G, such that each band of every element may be divided to sub-bands.

4.2.1 Description of Algorithm B

Input:

  • A set V of topologically allocated vertices V,
  • An upper bound on the distance R
  • A set F of elements (Assume that F is large enough)
    • Step 1. Build the directed graph G = (V,E) from V according to R (as suggested on the problem description).
    • Step 2. Colour the vertices V of the underlying graph of G, arbitrarily, with as few colours as possible, i.e., colour each vertex in turn, with a colour that differs from its neighbours. If possible, use an existing colour. If not, add a new colour and use it to colour the vertex. Denote the number of required colours by t. Each colour stands for a different element.
    • Step 3. For each colour i, build an undirected graph Gi′ = (Xi, Ei) such that Xi consists of all the outgoing edges of vertices of G that are coloured i, and the edges of Ei are built according to the collision rules.
    • Step 4. For each colour i, colour the vertices Xi of the graph Gi with as few colours as possible. Each colour stands for a different sub-band of the element i.

Output: A proper resource allocation of elements 1,2, …, t to G, and a proper allocation of sub-bands to the band of each element i, 1 ≤ it.

4.2.2 Discussion of Algorithm B

A proper allocation to the edges of G is a proper allocation of elements to G, followed by a proper division of each band in each time slot (i.e., each element) to sub-carriers.

Lines 1–2 of Algorithm B obey the extra collision rule of sub-bands. Each of the colours 1,2,…,t stands for a different element. The outgoing edges of each vertex of G, are coloured with sub-bands of the colour allocated to their vertex. Thus lines 3–4 divide properly the single band of Gi, 1 ≤ it, to sub-bands, according to the collision rules

Notice that Algorithm B may result an allocation with too many sub-bands. In this case, every element should be divided to more than one element. This is easily done by splitting the set of the sub-bands of this element i, 1 ≤ it, to subsets, and splitting the edges of Ei to bands, accordingly.

4.2.3 Example of Algorithm B

The following figures illustrate how Algorithm (B) runs on the undirected graph of Example (1). In this case, the starting point of the illustration (Step 1) begins with the graph G of Figure 6.

Figure 10 illustrates Step 2 of Algorithm B that colours the vertices of the graph G with t = 3 colours. Figures 11, 12 and 13 present the sub-colouring of the edges of each sub-graph Gi, i = 1,2,3, that actually allocates different sub-bands to the outgoing edges of each vertex of G with the band element colour i. Finally, the resulting allocation is represented in Figure 14, where three bands (colours) are divided to sub-bands.

images

Figure 10 Algorithm B, Step 2: Colouring the vertices of G with t = 3 colours.

images

Figure 11 Algorithm B, Steps 3–4: Colouring the vertices of G1′.

images

Figure 12 Algorithm B, Steps 3–4: Colouring the vertices of G2′.

images

Figure 13 Algorithm B, Steps 3–4: Colouring the vertices of G3′.

images

Figure 14 Algorithm B, Results: The division of the t = 3 bands (colours) to sub-bands.

5 Conclusions

This paper focused on time and frequency resource allocations in WMN. We separated the resource allocation process from the routing. In the first step, on which the paper focused, the links that connects the nodes are established and resource elements of time slots, frequency bands, and subcarriers are allocated. The process can be continued, in further research, to adapt the link data rates to its SNIR. Numerous existing routing methods can run on the WMN.

The separation order of a system is defined and optimal solutions are shown for perfect grids. Two centralized algorithms of resource allocation process based on graph theory are shown; one for allocation of time slots and frequency bands not specific for OFDM, and the second algorithm that enables allocation of OFDM subcarriers, as well.

6 Acknowledgements

The authors wish to acknowledge the cooperation and support of the COST Actions IC1004 and IC0906.

References

[1] Akyildiz, F., Wanga, X. (2005). Survey on wireless mesh networks. IEEE Radio Commun. 43, S23–S30. doi: 10.1109/MCOM.2005.1509968

[2] Oyman, Ö., Laneman, J. N., Sandhu, S. (2007). Multihop relaying for broadband wireless mesh networks: from theory to practice. IEEE Commun. Mag., 45, 116–122. doi: 10.1109/MCOM.2007.4378330

[3] Niyato, D., and Hossain, E. (2007). Radio resource management in MIMO-OFDM based wireless infrastructure mesh networks: issues and approaches. IEEE Commun. Mag. 45, 100–107. doi: 10.1109/MCOM.2007.4378328

[4] Reichman, A., and Czylwik, A. (2011). Broadband wireless mesh networks. IEEE COMCAS 2011, 1–6, Tel Aviv.

[5] Karakayali, K., Kang, J. H., Kodialam, M., and Balachandran, K. (2007). “Cross-layer optimization for OFDMA-based wireless mesh backhaul networks,” in IEEE Wireless Communications and Networking Conference, 276–281.

[6] Ali, S. H., Lee, K., and Leung, V. C. M. (2007). Dynamic resource allocation in OFDMA wireless metropolitan area networks’, [Radio Resource Management and Protocol Engineering for IEEE 802.16]. IEEE Wireless Commun. 14, 6–13.

[7] Thulasiraman, K., and Shen, P. X. (2009). “Interference aware subcarrier assignment for throughput maximization in OFDMA wireless relay mesh networks”, in IEEE International Conference on Communications, 1–6, Dresden.

[8] Reichman, A., Priesler, M., and Czylwik, A. (2012). “Time and freq- uency resource allocation in OFDMA wireless mesh networks,” in The 17th International OFDM Workshop (InOWo’12), 1–6, Essen, Germany.

[9] M. Priesler, and Reichman, A. (2013). “Time and frequency resource allocation using graph theory in OFDMA wireless mesh networks,” in The 6th International Multi-Conference on Engineering and Technological Innovation, IMETI 2013, July 9–12, 2013, Orlando, Florida, USA.

[10] Jensen, and T. R. Toft, B. (1994). Graph Coloring Problems. New York, NY: Wiley.

[11] Diestel, R. (1991). Graph Theory. Germany: Springer.

[12] Cormen, T. H., Leiserson, C. E., and Rivest, R. L. (1994). Introduction to Algorithms. Cambridge, MA: MIT Press.

[13] Garey, M. R., and Johnson, D. S. (1979). Computers and Intractability: A Guide to the Theory of NP-completeness. San Francisco: W. H. Freeman and Company.

[14] Reichman, A., Priesler M., and Wayer I. S. (2015). “Distributed network synchronization”, in IEEE International Conference on Microwaves, Communications, Antennas and Electronic Systems, COMCAS 2015, 1–4, Tel Aviv, 2–4 November 2015.

Biographies

images

M. Priesler (Moreno) holds B.Sc. (1981), M.Sc. (1990) and Ph.D. (2002) from Tel-Aviv University, Faculty of Exact Sciences, School of Mathematical Sciences. She is now a Senior Lecturer at Ruppin Academic Center, School of Engineering, Computer Hardware and Software Engineering Department.

She has more than 25 years of teaching experience at academic institutes in courses such as Computability and Complexity, Computational Models, Algorithms, Data Structures, Set Theory, Discrete Mathematics, Computing in C++, Mathematical Thinking and much more. She received excellence rewards for teaching at Ruppin Academic Center and at Tel Aviv University.

Her main research is in Combinatorics and Discrete Mathematics in the area of Graph Theory and in system optimization. She publishes her work in refereed articles in scientific journals and in conferences proceedings.

images

A. Reichman is an expert in wireless communication with more than 40 years of experience in industry and academy. He was cofounder of Shiron Satellite Communications and developed core technologies of high tech companies. He was the initiator and held leading positions in several R&D consortia under the auspices of Chief Science of Ministry of Industry and Trade, e.g. he held the position of scientific and technical leader of REMON the 4G Wireless Communication Israeli consortium. He received the prestigious Israeli Security Prize.

Now he is a senior lecturer at Ariel University in Samaria and at Ruppin Academic Center and in the management committees on European COST programs on Ambient Assisted Living and on Inclusive Radio Communication Networks for 5G and beyond. Also he serves as the Chief Scientist at Ayecka Communication Systems. He holds B.Sc. (1971) and M.Sc. (1975) from Technion, Israel Institute of Technology and Ph.D. (1984) from University of Southern California, all in Electrical Engineering.

He wrote more than 50 articles in refereed journals and in conference proceedings and 5 patents.

Abstract

Keywords

1 Introduction

1.1 Broadband Wireless Mesh Networks

1.2 Resources Allocation in WMN-Modelling and Motivation

2 Resource Allocation

2.1 Resources and Separation Order

2.2 Separation Rules and Separation Order Extension

2.3 Formal Resource Allocation Problem

2.4 Resource Allocation Constraints

2.5 Resource Allocation Constraints with One Frequency Band

3 Solution of Resource Allocation in Perfect Grids

3.1 Solution of the Perfect Square Grid Example

3.2 Solution of the Perfect Square Grid Example for One Frequency Band

images

images

3.3 Solution of the Perfect Triangle Grid Example

images

images

4 General Structure Resources Allocation

4.1 Resources Allocation Algorithm for Time Slots and Frequency Bands

4.2 Resources Allocation Algorithm for Sub-Bands

images

images

images

images

images

images

images

images

images

images

5 Conclusions

Acknowledgment

References

Biographies