Cross Layer Design for Maximizing Network Utility in Multiple Gateways Wireless Mesh Networks

We investigate the problem of network utility maximization in multiple gateways wireless mesh networks by considering Signal to Interference plus Noise Ratio (SINR) as the interference model. The aim is a cross layer design that considers joint rate control, traffic splitting, routing, scheduling, link rate allocation and power control to formulate the network utility maximization problem. As this problem is computationally complex, we propose the Joint dynamic Gateway selection, link Rate allocation and Power control (JGRP) algorithm based on the differential backlog as a sub-optimal solution. This algorithm first constructs the initial network topology, and then in each time slot, determines the generation rate and destination gateway of each traffic flow, simultaneously. The other main task of this algorithm is joint routing, scheduling, links rate allocation and node power allocation in each time slot. Moreover, for improving the fairness, we propose some new parameters instead of the differential backlog in JGRP algorithm. Simulation results show that using the proposed parameters in JGRP algorithm improves fairness from throughput and delay point of views.

I. INTRODUCTION We study the network utility maximization problem by jointly considering rate control, traffic splitting among gateways, routing, scheduling, link rate allocation and power control in multiple gateways wireless mesh networks. Over the past two decades, the mesh structure has been considered as an appropriate solution to increase the coverage area and capacity of wireless networks [1]. Important features of the wireless mesh networks include low cost deployment, distributed communication and robustness. However, the performance of these networks could be degraded, which is mainly due to poor design of network protocols [2], [3].
In recent years, various approaches have been provided to improve the performance of wireless mesh networks, among them is cross layer design which could be performed with various aims, such as improvement of throughput, delay and other network parameters. Another approach is using multiple gateways in these networks. In the following, we briefly review some related works according to these approaches.
First, some researches on cross layer design in wireless mesh networks. In [4], the authors investigated joint routing, channel assignment, power control and rate adaptation to improve the throughput, load balancing and fault-tolerant in multi-radio multi-channel wireless mesh networks. As this problem is NPhard, they proposed a heuristic algorithm with two levels. In the first level, a K-connectivity network topology is created using channel assignment and routing. In the second level, power control, rate adaption and scheduling are jointly considered for maximizing the throughput while K-connectivity network topology is preserved. In order to maximize the capacity of multi-radio mult-channel wireless mesh networks, the authors in [5], considered the link rate allocation, routing and channel assignment. In [6] the scheduling and routing design are performed jointly with the aim of minimizing the superframe length to support any random demand in multi-Tx/Rx wireless mesh networks. The authors of [7] considered joint scheduling and routing in multi-Tx/Rx wireless mesh networks for minimizing the endto-end delays and superframe length. In [8], joint optimization of channel assignment, power control and routing is investigated under the Signal to Interference plus Noise Ratio (SINR) model with the aim of some new parameters instead of the differential backlog to improve the fairness of our JGRP algorithm.
The rest of the paper is organized as follows: In Section II, we describe the network model. In Section III, the network utility maximization problem is formulated. Section IV describes the proposed JGRP algorithm as a sub-optimal solution to solve the network utility maximization problem. In Section V, we attempt to improve the fairness by defining some new parameters. We provide some simulation results in Section VI, and finally Section VII concludes the paper.
II. NETWORK MODEL We consider a wireless mesh network, where we have N mesh nodes and L links. We model the network with directed graph G = (Γ, E), where Γ is the set of mesh nodes and E is the set of links. We assume that there are multiple gateways in this networks and GW ⊂ Γ represents the set of mesh gateways.

A. Interference Model
In order to model the interference, we consider SINR model, where two directed links (p, q),(i, j) could be activated with r i j and r pq rates, simultaneously if and only if these links satisfy the following conditions: where P i j is the transmission power from node i to node j, β(r i j ) is the SINR threshold for acceptable bit error probability, and N 0 is the background noise power. Moreover, G i j denotes the channel gain between nodes i and j and equals G i j = ( where d i j is the distance between nodes i and j, d 0 is the reference distance and α denotes the path loss exponent.

B. Scheduling, Link Rate Allocation and Power Control
Considering the interference model, scheduling specifies which of the links could be activated, simultaneously. We represent the set of feasible schedules with Φ and the vector s m as the m th feasible schedule in which the links with common nodes could not be activated. We denote the element of s m corresponding to link (i, j) with Y m i j which is equal to one if the link (i, j) is activated in this schedule and zero, otherwise. In addition, π m denotes the fraction of time slot when s m is activated. Now, we extend equation (1) for a feasible schedule as follows: where the links may have different transmission rates and powers in nonidentical feasible schedules. Assuming that Y m i j = 1, r m i j is the allocated rate to link (i, j) and P m i j is the transmit power from node i to node j where the transmission rate is equal to r m i j .

C. Traffic and Queueing Model
Traffic Model: We assume that the number of traffic flows in our network is K, where F = {1, 2, ..., K } represents the set of all traffic flows in the network. We show the acceptable amount of traffic for flow f at time slot t by r where s( f ) is the source node of flow f and considering f : ∀i ∈ Γ as a constraint that shows the limitation of each node i in generating traffic. We assume that each of the gateways could be chosen as the destination of the packets of each flow f , where y ( f ) d shows the fraction of the traffic of flow f forwarded to gateway d.
Queening Model: We assume that there are multiple queues in each node, where each queue is corresponding to one of the gateways. The packets corresponding to a gateway lie in the same queue, even if they belong to different flows. We represent the length of the queue in node i corresponding to gateway d at the beginning of time slot t by Q (d) i (t), where the queue of gateway d corresponding to this gateway is assumed empty, i.e., Q (d) d (t) = 0. In addition, we denote the number of packets belong to destination d, which is transmitted over link (i, j) at time slot t by µ (d) i j (t) and the long term average of this parameter by µ (d) i j . Moreover, we represent all traffic on link (i, j) by µ i j . By these definitions, it is clear that the queue evolution is as follows [25]: is the input traffic to node i from upstream nodes and is the generated traffic in node i.

III. PROBLEM FORMULATION
Now, we formulate the network utility maximization problem under the constraints corresponding to scheduling, rate control, link rate allocation and power control. We define r = [r (1) s (1) , r (2) s (2) , . . . , r (K) s(K) ] T as the long-term average traffic vector. The aim is to maximize of the sum of long-term average traffics of all network flows. Moreover, as we would like to have fairness among the flows, log(.) function is considered as the utility function of the problem, which is also considered in [13], [14], [24], d∈GW The constraint (4b) states that the total input traffic rate to the queue of gateway d in node i must be equal to the output traffic rate from this queue. The constraint (4c) ensures that the total traffic of flow f is forwarded to the gateways. The constraint (4d) indicates that the sum rate transmitted over link (i, j) by different destinations must be equal to all traffic rate on the link (i, j). The constraint (4e) means that sum of the fractions of the time slot corresponding to various feasible schedules must be equal to one. The constraint (4f) ensures that the allocated rate and the activation time of the link (i, j) are enough for carrying the desired amount of traffic, where l t and l p represent the duration of each time slot and packet length, respectively. The constraint (4i) shows that each of the nodes in each scheduling could not be connected to more than one of the other nodes. The constraint (4j) limits the transmission power of the nodes.
IV. SUB-OPTIMAL SOLUTION We must note that problem (4) is NP-hard (see e.g. [26]), then in this section, we propose a sub-optimal solution to solve the network utility maximization problem (4). Accordingly, we offer JGRP algorithm which has three parts: • In the first parts, we prune the full mesh network and form an initial network topology to reduce the computational complexity of the third part of the algorithm. • In the second part, we jointly obtain the mechanism of the traffic splitting and rate control. • In the third part, we determine the routing, scheduling, rate allocation to the links and power allocation to the nodes, Simultaneously. We must note that the first part of the algorithm runs at the beginning (before network operation) ; but other parts run repeatedly at the beginning of each time slot.

A. Construction of Initial Network Topology
Assume that the number of links that could be connected to each node is an integer number between N 3 and 2 N 3 , where N is the number of the nodes. Considering the channels between the nodes, we propose Algorithm 1 to form the initial network topology.
Algorithm 1 Constructing the initial network topology. Require: The set of the mesh nodes Γ, The channel gains between nodes i, j ∈ Γ G i j .
1: For each node i, arrange the other nodes decreasingly, according to the channel gains between each of the nodes and node i. 2: Considering the priorities of all the nodes based on ordering in step 1, establish a link between the nodes which are in the first N 3 priority of each other.
For each node i which is not connected to its j th priority node, if the number of the links of the j th priority node of node i is equal to k, establish a link between this node and its j th priority node. 6: end for 7: end for

B. Rate Control and Traffic Splitting
Similar to [24], at the beginning of each time slot t, the rate controller at the source node s( f ) of each flow f ∈ F selects the gateway with the shortest queue length and enters the traffic to the queue as follows: r where V is a constant parameter which controls the trade-off between the network utility and the queue length, d * is the gateway which has the shortest queue in s( f ) and

C. Routing, Scheduling, Link Rate Allocation and Power Control
For each link (i, j), the differential backlog is defined as, This parameter specifies the gateways whose traffic is carried over link (i, j). In addition, the differential backlog is related to the amount of congestion at nodes i and j.
We must note the existed congestion in the nodes and maximization of the network links throughput during the specification of routing, scheduling and the rate allocation to the links and the power allocation to the nodes. In this end, we involve W i j , π m and r m i j in the objective function of the problem to consider the amount of congestion of the nodes and the throughput of the links. So, we formulate the problem as follows: In order to solve the problem (7), we first assume that the variable π m be constant and reformulate the problem as follows: In problem (8) the variables r m i j and β(r m i j ) should be selected from the discrete set of allowable rates and the variable Y m i j is binary. Accordingly, we need a full search to obtain the optimal solution, which is not practical. Hence, we propose a sub-optimal search (Algorithm 2) to solve the problem. As a prerequisite, we rewrite the SINR constraints corresponding to a typical set of links which have not any common nodes denoted by S ⊂ E. In other words, for all values of (i k , j k ) ∈ S and (i n , j m ) ∈ S, we have i m i n , i m j n , j m i n , j m j n . The SINR constraint for link (i k , j k ) would be, By replacing the inequality to equality in the above constraint, we have: Now, by writing (10) for all links, we have: Where matrix A is: Then, in Algorithm 2 after solving problem (8), in finally step of this algorithm, we obtain π 1 , . . . , π M by solving the following problem:s V. IMPROVEMENT OF THE FAIRNESS In Algorithm 2 for link rate allocation and finding the active feasible scheduling in each time slot, we only considered the congestion of the nodes and the total rate of the activated links in each scheduling. Moreover, we allocated more rate to the links with larger W i j . This approach does not lead to an acceptable fairness among the flows from the average delay and throughput point of views. In this section, in order Algorithm 2 Obtaining joint scheduling, routing, power control and link rate allocation. Require: The graph of the network the channels between the nodes i and j ∀i, j, The set of rates in the Standard 802.11a; R = {R 1 , R 2 , . . . , R 8 |R 1 > R 2 · · · > R 8 }, the set of SINRs corresponding to the rates in the set R; β = {β(R 1 ), . . . , β(R 8 )}, the length of queue corresponding to gateway d in node i; Q d i (t). Ensure: The activated schedules, the rates of the links and the power of the nodes, in each time slot.
1: For each link (i, j) ∈ E, compute the differential backlog as: 2: Sort W i j s decreasingly and lie them in the first row of W sort ∈ R 3×L , and set the second and third row of the column of W sort corresponding to W i j , as [i, j] T . Set the rate of the link corresponding to [W sort ] 1q , as R n , set SINR of this link as β(R n ) and set temp r = {R n } ∪ R s m .

11:
Considering the saved rates in temp r , formulate problem (11) for temp and compute the powers; If the power of all nodes in temp were positive and smaller than P max , set r m i j = R n , R s m = temp r , sch m = temp and [W 1 ] q = 1. to improve the fairness among the traffic flows, we define some new parameters to be used in Algorithm 2 instead of W i j . These parameters are explained in the following, 1) Let R (T) i j (t) be sum of the allocated rates to link (i, j) until the beginning of time slot t and define W (r) i j as: By using W (r) i j , the proposed algorithm allocates higher rates to the links to which we allocated less rate before the beginning of time slot t. 2) Let D i j as, By using W (D) i j , we increase the probability of sending the packets which have experienced more delay.
3) In order to have trade-off between the packets delay and the allocated rate to links, we define W (r,D) i j as, 4) Assume d ∈ GW be the gateway corresponding to W i j and R (T,d) i j (t) be the sum of allocated rates to link (i, j) for transmitting the traffic of gateway d until the beginning of time slot t. We define W (r d ) i j as, 5) In order to jointly consider all of the previously defined parameters related to delay, allocated rate to the links and allocated rate to transmit the traffic of the gateways, we define W (r d ,D) i j as, VI. SIMULATION RESULTS In order to evaluate and compare the proposed algorithms some simulation results are provided. the algorithms are implemented using MATLAB. In all simulations, we assume eight flows and two gateways. We set the simulation parameters as shown in Tables I and II.

A. Investigation of the performance of JGRP algorithm
In the simulated network, 10 nodes are distributed in 350m × 350m square area uniformly. By running Algorithm 1, the topology is constructed as shown in Fig. 1. We select two nodes 1 and 10 (which have the maximum distance from each other) as the mesh gateways, and we assume that nodes 2 to node 9 are the sources of traffic flows numbered 1 to 8, respectively. We run JGRP algorithm based on the six parameters W i j , W (r) In Fig. 2, we observe that by using the JGRP algorithm based on W i j , the throughput of different flows are different and therefore there is no fairness among flows. Moreover, we observe that this algorithm based N 0 power of background noise [27] −90 dBm α path loss exponent [28] 3 d 0 reference distance 10 m duration of time slot [29] 625 µs packet length [29] 1470 bytes V [24] 30 R max i [24] 10 P max 20 dBm , the throughput of various flows are close to each other. This is because of the reduction in throughput of the flows which achieve more throughput using parameters W (r) i j , W (D) i j and W (r d ) i j . In Fig. 3, we observe that by using JGRP algorithm based on W i j , the number of packets corresponding to various flows received by the gateways are very different. Moreover, it can be observed that using JGRP algorithm based on W (r) i j increases the number of packets received by the gateways from flows 4 and 5 whose source nodes are not connected directly to the gateways. Furthermore, we observe that using parameters W (r,D)  In Fig. 4, we observe that using W (r) i j improves the delay of all traffic flows which have high delay using W i j parameter. But, using the parameters W (D) i j and W r d (i, j) improves the delay of only some of those flows. Moreover, we observe that using parameters W (r,D) So far we investigated fairness using intuitive metrics. Now, we use the Jain's fairness index to indicate the amount of fairness more accurately. If x 1 , . . . , x n be the samples of random variable X and x i > 0, i = 1, . . . , n, then the Jain's fairness index is defined as [31]: where 0 < JF I ≤ 1 and JF I = 1 indicate the complete fairness. Replacing x i s in equation (19) with the desired parameters, the amount of the fairness corresponding to each of these parameters could be obtained. Here, we would like to investigate the fairness from throughput and delay points of view; then we substitute the parameters such as the throughput of each flow, the average delay of each flow and the ratio of the throughput and the average delay of each flow in (19). Then, we obtain the amount of    Table III. From this table, we observe that Jain's fairness index corresponding to throughput for W (r,D) i j and W (r d ,D) i j is equal to one, which means that employing these parameters, complete fairness will be provided among flows. Comparing JFI corresponding to the average delay of flow packets, we observe that all parameters W (r) i j obtain the most amount of fairness. By considering the ratio of the throughput and the average delay of each flow as the parameter of Jain's fairness index, we can compare the fairness from both of the throughput and delay point of views as shown in the third row of Table III. We observe that parameters W (r,D) i j although improve the fairness in comparison with using W i j parameter, increase the average delay and reduce the aggregate throughput and the number of packets received by the gateways. Therefore, in order to justify the performance of this algorithm, for each flow, , we show the ratio of the number of packets received by each gateway to the number of packets sent to that gateway for each flow in Tables IV and V. In Table IV, we observe that by using W i j , W (r) i j , W (D) i j and W (r d ) i j , gateway 1 almost does not receive the packets of flows which their source nodes is connected directly to gateway 2, but by using W (r,d) i j these packets are received more. This fact is also true for nodes with direct link to gateway 1 as shown in Table V. This is because the mentioned parameters consider the rate of links and the delay of packets simultaneously, and this leads to the result that the intermediate links be activated and all the flows be communicated to all the gateways. Due to the multi-hop distance between the nodes and the non-adjacent gateway, the activation of intermediate links increases the average delay and decreases the aggregate throughput. Now, we investigate the performance of the JGRP algorithm in networks with different sizes by running it based on all the parameters on the networks with 10, 15 and 20 nodes over 2600 time slots. For simulating networks with 15 and 20 nodes, we respectively distribute 15 and 20 nodes in a 450m × 450m and 500m × 500m square areas uniformly. Then, we form the topology of each of the networks using Algorithm 1. In order to obtain the simulation results of the networks with 15 and 20 nodes, we randomly select eight nodes as source nodes of the flows. We compare the simulation results of the networks with 10, 15 and 20 nodes as shown in Tables VI, VII, VIII and IX.
In Table VI, we observe that JGRP algorithm based on W i j obtains the most aggregated throughput in the networks wit all three 10, 15 and 20 nodes. Moreover, we observe that while increasing the number of nodes, the aggregated throughput obtained by JGRP algorithm based on W i j is not reduced. But, in JGRP algorithm based on the other parameters, the aggregated throughput is reduced when the number of the nodes is increased. This subject has two reasons; the first reason is that by using parameters W (r) i j , i j , in each time slot, the packet delay and the total allocated rate to the links are considered to fairly allocate the rates to the links. The second reason is that the number of nodes in the network is more than the number of the flows. These reasons lead to the fact that the links whose nodes are not the sources of the flows or a gateway, are likely to be activated. Then we have more packets remaining in the flow source nodes and consequently the generated traffic is reduced.
In Table VII, we observe that by increasing the number of nodes, the average delay of one packet in the JGRP algorithm based on all parameters increases. This subject is because of that when the number of the nodes is increased, the number of hops between the flow source nodes and the gateways could be increased.
In Table VIII, it can be observed that increasing the number of the nodes in the networks, the number of the packets received by the gateways is reduced for all the parameters, But, this reduction is more pronounced for W (r) . It can also be observed that increasing the number of nodes, the difference between the number of the received packets by the gateways using W i j and the other parameters increases. This subject is because the number of the flows is less than the number of    In Table IX, we observe that increasing or decreasing the fairness does not have any direct relation with the increase in the number of the nodes. The reason is that the factors that affects the fairness are the allocated rate to the links and the number of hops between the source nodes and the gateways.  B. Multi-Radio Multi-Channel JGRP algorithm (MR-MC JGRP) Now, we introduce MR-MC JGRP as an extension of the JGRP algorithm for multi-radio multi-channel networks. In the special case where the number of radios on each node is equal to the number of frequency channels, the extension is very simple. For this purpose, in the 20 th step of Algorithm 2, partition the set of schedules to some subsets and in each of them, use one of the frequency channels. Then solve problem (13) for each of the frequency channels individually.
For simulation, we assume that each network node has two radios and the number of accessible frequency channels equals to the number of radios. Then, we run the JGRP algorithm based on W (r) i j In Fig. 5, we observe that in the JGRP algorithm based on both parameters W (r) i j and W (r,D) i j using two frequency channels doubles the throughput of the flows comparing with the case of one radio one frequency channel.
In Fig. 6, we observe that in the JGRP algorithm based on both parameters W (r) i j and W (r,D) i j using two frequency channels and two radios per node reduces the average delay and improves the fairness from the delay point of view.
VII. CONCLUSION In this paper, we formulated the problem of network utility maximization for multiple gateways wireless mesh networks by considering joint rate control, traffic splitting, scheduling, routing, link rate allocation and power control assuming SINR interference model. In addition, by considering the complexity of this problem, we proposed the JGRP algorithm as a sub-optimal solution. Then, in order to improve the fairness, we defined W (r) i j , W (D) i j , W (r,D) as new parameters to be used in the JGRP algorithm instead of the differential backlog (W i j ). Simulation results illustrate that using parameters W (r) i j and W (r d ) i j in which the sum of the allocated link rates are considered in their definition, improved the fairness from average delay and throughput points of view. Moreover, by using these parameters, the number of packets received by the gateways is not reduced and the average delay is not increased in comparison to W i j parameter . We also showed that using W (r,D) i j and W (r d ,D) i j in which the sum of the allocated link rates and the delay of packets were considered in their definition, not only improves the fairness, but also improves the communication between mesh nodes and gateways. However, its negative effects increase the average delay and decrease the number of packets received by the gateways in comparison with other parameters. Finally, we extended the JGRP algorithm for multi-radio multi-channel networks in which the number of radios per node is equal to the number of accessible frequency channels. We showed that using two frequency channels and radios when W (r) i j and W (r,D) i j are used doubles the throughput of the flows and reduces the average delay in comparison to the single radio single channel case.