Vol: 1 Issue: 1
Published In: July 2015
Article No: 2 Page: 2548 doi: https://doi.org/10.13052/ambientcom22463410.112
Read other article: 


Resource Allocation in Wireless Mesh Networks
M. Priesler (Moreno) and A. Reichman
Ruppin Academic Center, Emek Hefer, 40250 Israel
Email: {arier; mirip} @ ruppin.ac.il
Received 23 January 2015; Accepted 5 June 2016;
Publication 25 July 2016
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.
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 lowercost backhaul and may provide coverage in hardtowire areas and greater rangedue to multihop 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 subbands of subcarriers. Methods of dynamic subcarrier assignment in OFDMA WMN are shown in [5–7] using crosslayer 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.
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.
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.
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.
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.
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.
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.
This paper considers the following shared resources:
We define [4] the time frequency separation order (TFSO) λ_{TF} as the number of combinations of time slots and frequency bands which give practical separation among such combinations (not according to frequency subbands). If N_{T} is the number of time slots and N_{FB} is the number of frequency bands, then TFSO is determined by:
$${\lambda}_{T\text{}F}={N}_{T}\xb7{N}_{F\text{}B}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}(1)$$For example, with four time slots and two frequency bands, the TFSO 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 TFSO may be modified to include the space separation. Assuming that for each terminal we have directional antennas that divide the space in N_{sS} sectors, we can extend the TFSO to time, frequency and space separation order (TFSSO) λ_{TFS}, according to the number of combinations of time slots, frequency bands, and angular directions that offer practical separation among such combinations. The TFSSO is determined by:
$${\lambda}_{T\text{}F\text{}S}={N}_{\text{}T}\xb7{N}_{\text{}F\text{}B}\xb7{N}_{\text{}S}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}(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) TFSSO factor with an effective number of sectors N_{S.eff}:
$${\lambda}_{T\text{}F\text{}S.ef\text{}f}={N}_{T}\xb7{N}_{F\text{}B}\xb7{N}_{S.ef\text{}f}.\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}(3)$$In each slot, all frequency bands may be used according to noncollision rules:
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 subbands 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 subbands N_{FSB}, the extended separation order is give by λ_{xTF} = N_{FSB} ⋅ λ_{TF} or λ_{xTFS} = N_{FSB} ⋅ λ_{TFS}.
The separation order defines the number of combinations of time slots, frequency bands, and frequency subbands (and of angular directions). Each such combination is called a resource element (or briefly – elements).
In the remainder of this section, we use graph theory methods and terminology [10–12], 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 antiparallel 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).
The resource elements allocated on the edges of G must obey the following collision rules:
We hence define two edges (u,v), and (x,y), with resource elements f_{1} and f_{2}, respectively, to be mutually undisturbed if and only if they satisfy the following demands:
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 antiparallel 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 antiparallel 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 antiparallel 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 antiparallel 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 antiparallel 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.
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 subbands. In this case, we need to take into consideration an additional noncollision rule:
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 subbands of the same element unless they are both outgoing edges of the same vertex or ingoing 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 subband allocation in the same time slot are nonadjacent, 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 subbands 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 subbands on outgoing 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.
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<\sqrt{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 bidirected transmission on an edge must use two different elements, then we need to allocate eight different resource elements on those four antiparallel edges. Therefore, we need at least eight different elements for every disturbancefree allocation of elements on the grid.
To terminate the proof, we present a collisionfree allocation of one resource element on every edge of the grid in each direction, using eight different resource elements: We set the element
$$\left\Delta i\right\xb7\left[\left(i\frac{\Delta i1}{2}\right)\text{mod}\text{\hspace{0.17em}}\text{4}\right]+\left\Delta j\right\xb7\left[4+\left(j\frac{\Delta j1}{2}\right)\text{mod}\text{\hspace{0.17em}}\text{4}\right]\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}(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 nondisturbing 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 upgoing direction, and the number right to the edge represents the resource element in the downgoing direction.
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 subbands, and limitations must be taken into consideration according to the three noncollision rules.
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 timeslots 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 subbands of the single band. We designate the two resource elements related to an horizontal link i as $\overrightarrow{i}\text{\hspace{0.17em}}\text{and}\overleftarrow{i}$ and the two resource elements related to an vertical link j as $j\text{}\text{}\uparrow \text{\hspace{0.17em}}\text{and}\text{\hspace{0.17em}}j\text{}\text{}\downarrow $.
The proposed allocation with four time slots has four subbands 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:
$$\begin{array}{l}\text{Slot1}\text{.}\overleftarrow{1}\text{\hspace{0.17em}}\text{and}\text{\hspace{0.17em}}\overrightarrow{\text{0}};\overleftarrow{3}\text{\hspace{0.17em}}\text{and}\text{\hspace{0.17em}}\overrightarrow{\text{2}}\\ \text{Slot2}\text{.}\overleftarrow{2}\text{\hspace{0.17em}}\text{and}\text{\hspace{0.17em}}\overrightarrow{\text{1}}\text{;}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\overleftarrow{0}\text{\hspace{0.17em}}\text{and}\text{\hspace{0.17em}}\overrightarrow{\text{3}}\text{\hspace{0.17em}}\\ \text{Slot3}\text{.5}\text{}\text{}\downarrow \text{and}\text{\hspace{0.17em}}\text{\hspace{0.17em}}4\text{}\text{}\uparrow \text{;}\text{\hspace{0.17em}}\text{7}\text{}\text{}\downarrow \text{and}\text{\hspace{0.17em}}6\text{}\text{}\uparrow \\ \text{Slot4}\text{.}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{6}\text{}\text{}\downarrow \text{and}\text{\hspace{0.17em}}\text{\hspace{0.17em}}5\text{}\text{}\uparrow \text{\hspace{0.17em}}\text{;}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{4}\text{}\text{}\downarrow \text{and}\text{\hspace{0.17em}}7\text{}\text{}\uparrow \end{array}$$Each time slot has four subbands that occupy the full band. If all the subbands are equal to one fourth of the band, we can allocate the same sub band to 0in slot 1, to $\overleftarrow{0}\text{\hspace{0.17em}}$ in slot 2, to $4\text{}\text{}\uparrow \text{\hspace{0.17em}}$ in slot 3 and to $4\text{}\text{}\downarrow \text{\hspace{0.17em}}$ ↓in slot 4. Each node is transmitting in two time slots out of the four. For example, the node located at (1,1):
$$\begin{array}{l}\text{Slot1}\text{.Receives}\overleftarrow{\text{3}}\text{\hspace{0.17em}}\text{and}\text{\hspace{0.17em}}\overrightarrow{\text{0}}\text{\hspace{0.17em}}\\ \text{Slot2}\text{.Transmits}\overleftarrow{2}\text{\hspace{0.17em}}\text{and}\text{\hspace{0.17em}}\overrightarrow{\text{1}}\text{\hspace{0.17em}}\\ \text{Slot3}\text{.}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{Receives}\text{\hspace{0.17em}}\text{\hspace{0.17em}}7\text{}\text{}\downarrow \text{and}\text{\hspace{0.17em}}\text{4}\text{}\text{}\uparrow \\ \text{Slot4}\text{.}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{Transmits}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{6}\text{}\text{}\downarrow \text{and}\text{\hspace{0.17em}}5\text{}\text{}\uparrow \end{array}$$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 subbands, according to the allocation in Figure 1. Each time slot has eight subbands, 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 subbands, and red dots are transmitting in the second time slot, using the red subbands.
A perfect triangle grid serves as an additional example of resource allocation. Assuming that the communication range R is $1<R<\sqrt{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 antiparallel 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 x_{0}, x_{1}, x_{2}, x_{3}, x_{4}, x_{5} such that for every 0 ≤ i < 6, there exists a pair of antiparallel directed edges between x_{i} and x_{i+}_{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 x_{i} of v, 0 ≤ i < 5, are mutually disturbed. That defines 16 edges (8 pairs of antiparallel edges), mutually disturbed in pairs, adjacent to v and to, say x_{0}, as described in Figure 3.
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(x_{2},x_{1}) = c(x_{5},x_{0}), and c(x_{5},x_{4}) = c(x_{0},x_{1}) (where their antiparallel edges are obviously set the opposite elements, i.e., c(x_{0},x_{5}) and c(x_{1},x_{0}) respectively). We thus must set c(x_{3},x_{2}) = c(x_{0},x_{1}). Hence c(x_{5},x_{4}) = c(x_{0},x_{1}) = c(x_{3},x_{2}), which means that the mutually disturbed edges (x_{5},x_{4}) and (x_{3},x_{2}) are allocated the same element. The symetric arguments lead to the symetric conclusion that also c(x_{4},x_{5}) = c(x_{1},x_{0}) = (cx_{2},x_{3}). 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 collisionfree 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 antiparallel edge of each edge with element i, is set with the element i′.
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.
Input:
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 e_{1},e_{2} ∈ E,(e_{1},e_{2}) ∈ E′ if and only if e_{1},e_{2} 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.
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 NPhard [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 endvertex 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 collisionfree:
$$\Delta (G)1\le m(G)\le \Delta ({G}^{\prime})+1\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}(5)$$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 nonedges 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, a_{0},a_{1}, …, g_{0},g_{1}. 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.
This chapter deals with the general mesh system approach, such that each band may be divided to subbands.
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 subbands.
Input:
Output: A proper resource allocation of elements 1,2, …, t to G, and a proper allocation of subbands to the band of each element i, 1 ≤ i ≤t.
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 subcarriers.
Lines 1–2 of Algorithm B obey the extra collision rule of subbands. Each of the colours 1,2,…,t stands for a different element. The outgoing edges of each vertex of G, are coloured with subbands of the colour allocated to their vertex. Thus lines 3–4 divide properly the single band of G_{i}′, 1 ≤ i ≤ t, to subbands, according to the collision rules
Notice that Algorithm B may result an allocation with too many subbands. In this case, every element should be divided to more than one element. This is easily done by splitting the set of the subbands of this element i, 1 ≤ i ≤ t, to subsets, and splitting the edges of E_{i} to bands, accordingly.
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 subcolouring of the edges of each subgraph G_{i}′, i = 1,2,3, that actually allocates different subbands 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 subbands.
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.
The authors wish to acknowledge the cooperation and support of the COST Actions IC1004 and IC0906.
[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 MIMOOFDM 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). “Crosslayer optimization for OFDMAbased 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 MultiConference 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 NPcompleteness. 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.
M. Priesler (Moreno) holds B.Sc. (1981), M.Sc. (1990) and Ph.D. (2002) from TelAviv 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.
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.
Journal of Ambientcom, Vol. 1, 25–48.
doi: 10.13052/AMBIENTCOM22463410.112
© 2016 River Publishers. All rights reserved.
1.1 Broadband Wireless Mesh Networks
1.2 Resources Allocation in WMNModelling and Motivation
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
3.3 Solution of the Perfect Triangle Grid Example
4 General Structure Resources Allocation
4.1 Resources Allocation Algorithm for Time Slots and Frequency Bands