MIMO links can significantly improve network throughput by supporting multiple concurrent data streams between a pair of nodes and suppressing wireless interference. In this paper, we study joint rate control, routing, and scheduling in MIMO-based multihop wireless networks, which are traditionally known as transport layer, network layer, and MAC layer issues, respectively. Our aim is to find a rate allocation along with a flow allocation and a transmission schedule for a set of end-to-end communication sessions so as to maximize the network throughput and also to achieve the proportional or weighted fairness among these sessions. To this end, we develop Transmission Mode Generating Algorithms (TMGAs), and Linear Programming- (LP-) and Convex Programming- (CP-) based optimization schemes for the MIMO networks. The performances of the proposed schemes are verified by simulation experiments, and the results show that the different schemes have different performance benefits when achieving a tradeoff between throughput and fairness.
1. Introduction
Recent advances in wireless communications and computing technologies enable a broad range of network applications. To facilitate these applications for the fast-growing number of mobile users and services, the communication society intensifies the interest in the development of novel approaches that can increase the overall network capacity. With the enlarged requirement, future multihop wireless networks such as wireless backhaul networks (WBNs) and wireless mesh networks (WMNs) are conducted to support various data and multimedia transmissions that are usually bandwidth-consumed. In such networks, the Multiple-Input Multiple-Output (MIMO) antenna system, which can offer multiple Degree of Freedom (DOFs) for communications in a node while reducing interference and improving network throughput, is one of the technologies to this end, and attracts much attention of recent research on communication [1‐3]. However, when considered with networking, it is still in its early stage. For example, in [4], the authors devise a MIMO-based MAC protocol and develop analytical methods to characterize the corresponding saturation throughput and study the impact of MIMO MAC on routing. As another example, the authors in [5] give their key optimization considerations such as spatial multiplexing for MAC layer design in ad hoc wireless networks.
On the other hand, cross-layer schemes have been proposed to improve throughput and fairness for multihop wireless networks. For example, in [6, 7], the joint rate control and scheduling problems have been studied for wireless ad hoc networks with either a scheduling-based MAC [6] or an Aloha-based MAC [7], in which routes are assumed to be given a prior, however. In [8], the authors propose Integer Linear Programming formulations and a heuristic algorithm to solve the joint scheduling and power control problems in WMNs. Nevertheless, they consider only the wireless networks without MIMO links. In addition, the authors in [9] also present a centralized algorithm to solve the corresponding joint routing, scheduling, and stream control problem for WMNs. With MIMO links, the authors provide a three-step approach to this end, but they do not explicitly consider the problem of providing different object functions of fairness for each session in the network. Similarly, a cross-layer optimization for solving the joint stream control and scheduling problem for MIMO-based wireless networks is proposed in [10]. In this work, the authors aim to seek a stream control solution and a transmission schedule with minimum frame length to satisfy traffic demands of links, and pay no attention to the issue of supporting service differentiation for different traffic sessions.
Anzeige
In this paper, we aim to develop cross-layer optimization schemes for multihop wireless networks with MIMO to provide end-to-end throughput optimization among different sessions and support service differentiation for these sessions with proportional or weighted fair share. To this end, we first divide communication flows into components containing only weak contentions. Then, we use Transmission Mode Generating Algorithms (TMGAs, including TMGA1 and TMGA2) to generate a TDMA-based scheduling matrix for these components to be scheduled without interference. As expected, generating all transmission modes for a network (with, e.g., TMGA1) would be time consuming. Thus, we design a polynomial time heuristic (TMGA2) to compute a subset of transmission modes with time efficiency. Given the scheduling matrix, we conduct the cross-layer optimization schemes to address joint network routing, link scheduling, and rate control in such networks with a scheduling-based MAC, which are traditionally known as transport layer, network layer, and MAC layer issues, respectively. In particular, with Linear Programming (LP) and Convex Programming (CP), we seek a rate allocation along with a flow allocation and a transmission schedule such that the network throughput can be maximized and the desired fairness can be achieved. The performances of the proposed schemes are verified by simulation experiments, and their impacts on throughput and fairness for the networks are evaluated. The numerical results show that the proposed schemes can satisfy our design aims and can provide their unique performance benefits when achieving a tradeoff between throughput and fairness. The results also show that TMGA2 can achieve nearly the same performance gains with only a few numbers of iterations and can be very time efficient, when compared with TMGA1 that generates all transmission modes.
The rest of this paper is organized as follows. In Section 2, we summarize the system model for MIMO links. Following that, in Section 3, we introduce our flow scheduling algorithms for the system. In Section 4, we present the cross-layer optimization schemes for the throughput maximization and fairness problem. Finally, these schemes are examined with experiments in Section 5, and conclusions are drawn in Section 6.
2. System Model
2.1. Node Topology Graph
In this work, we consider a multihop wireless network that consists of a finite set of nodes where each node is stationary and has a MIMO antenna array with elements or DOFs for each node to transmit and receive signals. All nodes transmit at the same fixed power level in a signal common channel, and each node has a uniform transmission range and a uniform interference range . Let denote the set of all pairs of distinct nodes in such that and are within each other's transmission range. An ordered pair of nodes in is said to form a flow if node needs to transmit to node . is said to be active if is currently transmitting to ; otherwise, is said to be inactive. Let denote the set of all flows. Hereafter, the graph defined above is referred to as node topology graph.
2.2. Overview of MIMO Antenna Array Processing
Figure 1 illustrates the transmitter and receiver antenna array and the MIMO channel for the case when antennas are used at the both ends. To transmit a signal through a transmit beamformer over the 2-antenna array, the transmitter sends two weighted copies of the signal, one on each antenna. That is, is sent over antenna 1, and is sent over antenna 2, with called the transmitting weight vector. Then, the two signals are weighted by the receiver with a receiving weight vector and summed to produce . Let denote the matrix of channel coefficients between the transmitter and the receiver. The above can thus be written as , and the complex gain experienced by is then a consequence of transmit beamforming, the channel, and receive beamforming of . Now with appropriate weight vectors and , the received signal can achieve a unit gain () if it is received at the desired receiver or a zero gain () if it is received at a nondesired receiver. In other words, we can ensure that the signal is received with a certain gain or is perfectly nulled by appropriately choosing the weight vectors if no power limit on a node's receiving capacity. In general, we could design if is given, and vice versa. Thus, by considering whether the transmitter and the receiver are a desired communication pair or potentially interference with one another, we have the following beamforming conditions.
(1)
If the receiver corresponding to is the desired receiver of and is fixed, then we could require to satisfy so that can be received with unit gain.
(2)
If the receiver corresponding to is already involved in another link, then is fixed and we could require to satisfy so that the transmitter does not create interference at this receiver.
(3)
If the transmitter is communicating with a different user by using a fixed , and the receiver corresponding to wants to receive signals from different transmitter without interference, then we could require to satisfy so as to null the contribution of at the receiver.
Anzeige
Figure 1
Multiantenna wireless channel.
×
2.3. Transmission Constraints on MIMO Links
Consider the multihop wireless network shown in Figure 2, where , , and . Assume that () every link has the same and , () the numbers of antennas are and , and () and are the only two flows in the network. With the above, we consider the example that node 4 wants to transmit to node 3 while node 2 is currently transmitting to node 1 (i.e., is active). Let be the (1 1) transmitting weight vector that node 2 is currently using to weight its transmitted signal and let be the (1 1) receiving weight vector that node 1 is currently using to weight the signal received from node 2. In this case that is currently active, if node 3 wants to receive an interference-free signal from node 4, it must design its receiving weight vector to suppress the interference caused by node 2's transmission while assuring an acceptable gain of its intended signal coming form node 4. In terms of equations, the above can be written as and , where is the transmitting weight vector of node 4, and is the receiving weight vector of node 3. Now, given , , and , the system of these two equations would have a unique solution because the elements of each of , and are i.i.d in general. That is, if there is no power limit on node 3's receiving capacity, it is always possible for node 3 to receive one interference-free flow from node 4 concurrently with the signals from node 2. In other words, and are always possible to be active simultaneously in this example.
Figure 2
Node topology graph.
×
By reserving the admission order of these flows, we now consider another example in which node 2 wants to transmit to node 1 while node 4 is currently transmitting to node 3 (i.e., is active). With similar considerations for the above, this example can be represented by the equations of and , but now the objective to be solved becomes , which is (1 1) weight vector. That is, the single variable involves the system of the two equations associated with and that are i.i.d in general. Obviously, the over-determined system has no solution.
By summarizing these examples, we can find that the admission of () is order dependent. That is, if is admitted first, then is possibly admitted. On the contrary, if is admitted first, then could not be admitted without inference. Clearly, these could be verified with the beamforming conditions given previously. However, to be specific, we define the transmission constraints as follows. Let node be the transmitter and node the receiver, and suppose that there are streams currently received by nodes located within 's interference range, and streams currently transmitted by nodes located within 's interference range, where a steam denotes a copy of data signal transmitted by the MIMO system. Suppose further that wants to transmit an -stream flow to . Then, for interference-free communications in the system, we have the following constraints.
Theorem 1 (transmit DOF constraint).
can transmit an -stream flow to without interfering with the streams concurrently received by 's neighbors if
(1)
Proof.
Let denote the set of 's neighbors that are receiving the streams and denote the number of streams that node is currently receiving, for all (i.e., ). Suppose that for each , knows the receiving weight vector of , and the channel matrix between it and . Then, can transmit its -stream flow to with the weight vectors subject to the conditions of , where is the column vector of length defined as with 1 at the th position, and is the matrix defined as with and , for all . Because the elements of each involved would be i.i.d in general, the system of equations with of the size of , would have no solution if .
Theorem 2 (receive DOF constraint).
can receive an -stream flow from without interfering with the streams concurrently transmitted by 's neighbors if
(2)
Proof.
Let denote the set of 's neighbors that are transmitting the streams and denote the number of streams that node is currently transmitting, for all (i.e., ). Suppose that for each , knows the transmitting weight vector of , and the channel matrix between it and , for all . Then, can receive its -stream flow from with the weight vectors subject to the conditions of , where is the column vector of length defined as with 1 at the th position, and is the matrix defined as with and , for all . Because the elements of each involved would be i.i.d in general, the system of equations with of the size of would have no solution if .
3. Flow Scheduling Algorithms
In this section, we present our flow scheduling algorithms for MIMO networks. As the first step to this end, we divide the flow contentions in a MIMO system into two categories: strong interference and weak interference, similar to that given in [10]. The strong interference denotes that an incoming flow into a node cannot be scheduled in the same time slot with any outgoing flow from the same node and vice versa. This is because a node in wireless networks is usually half-duplexing and thus it cannot simultaneously transmit and receive. In other words, any two flows and are said to strongly contend with each other if and only if or . Given that, we define as the strong contention graph, where a vertex in corresponds to a flow in , and a bidirectional edge in denotes the corresponding flows in strongly contend with each other in the node topology graph .
On the other hand, the weak interference denotes that a pair of flows would contend for resources but they could be scheduled in the same time slot if the related DOFs can be properly arranged. Similarly, we define as the weak contention graph. In this graph, a directional edge between a pair of vertices corresponding to and in arises if any one of the three weak-interference conditions holds: () , () , and () there exists a (possibely or ) such that andor . To be specific, we consider a MIMO network of 8 nodes and 8 flows as an example, showing its node topology graph in Figure 3(a) and the derived and in Figures 3(b) and 3(c), respectively. For example, we can see in Figure 3(a) that when node 4 is transmitting to node 2 (with ), node 2 cannot simultaneously transmit to node 1 (with ), and vice versa. This is a strong interference, and is denoted by a bidirectional edge between and in Figure 3(b). Similarly, we can also see in Figure 3(a) that when node 8 simultaneously transmits to node 4 and node 5, and will contend with each other. This corresponds to the first weak-interference condition, and is shown by a bidirectional edge between and in Figure 3(c). In addition, the second weak-interference condition is exemplified by the scenario in Figure 3(a) that nodes 2 and 3 simultaneously send to node 1, and thus and interfere with each other. Therefore, there is a bidirectional edge between and in Figure 3(c). Finally, the third weak-interference condition can be found in Figure 3(a) that when node 4 transmits to node 2 (with ), this node can interfere with node 1's receipt of from node 3. This interference is shown by a directional edge from to in Figure 3(c). Besides, the other strong and weak interferences not exemplified in the above can be also observed easily.
Figure 3
An example of weak and strong contentions: (a) the node topology graph , (b) the corresponding strong contention graph , and (c) the corresponding weak contention graph .
×
Clearly, the flows strongly contending with each other cannot be scheduled at the same time. Thus, the first step of our algorithms is to divide the flows into a set of components, say , that contain only weak contentions and can be represented by . This step is done by finding a valid coloring for with, for example, the greedy algorithm given in [11] that sorts vertices in by decreasing vertex degrees, and according to the order, colors them one by one using a first-fit greedy approach. Then, the flows of with the same color in compose a , and the corresponding subset of composes a .
3.1. Transmission Modes
After obtaining and , we now proceed to find an interference-free scheduling for each of the components with a scheduling-based MAC. To this end, we define transmission mode as the flows in that can be active simultaneously. A matrix is used to represent the set of transmission modes, and called scheduling matrix, in which denotes the number of transmission modes, and denotes the number of flows in . In the matrix, a row represents a transmission mode , and its element represents the number of traffic streams utilized by flow in this mode. That is, a is a vector denoting a possible set of transmissions from all flows in a time slot. By definition, all flows with traffic streams in a transmission mode can be activated simultaneously. However, the concurrent flows may interfere with each other in the MIMO network. Thus, the scheduling algorithms should firstly generate interference-free s for constructing a desired . Next, with these modes representing the time slots to be used, they are expected to determine the time fraction for every transmission mode or time slot to compose a TDMA frame that can satisfy the scheduling target. Accordingly, the scheduling algorithms should secondly find the frame length and the number of active time slots of each transmission mode in one frame. This can be done by considering that if the value of for every is given, the frame length is then the smallest positive integer such that is an integer for every transmission mode, and the number of active times for a is simply its . Now, given the two aims of the scheduling algorithms, we proceed to develop the transmission mode generating algorithms for s in the next subsection, and leave the methods for determining s till Section 4.
3.2. Transmission Mode Generating Algorithm 1
To obtain the transmission modes for MIMO networks, we design Transmission Mode Generating Algorithm 1, or shortly TMGA1. As shown in Algorithm 1, the inputs of TMGA1 include the set of source DOFs , the set of destination DOFs , and the set of weak contention graphs , for the flow components obtained previously. For each , the algorithm generates all possible transmission modes s, according to the component's and . Then, each of the modes is examined for its validity conservatively or nonconservatively. Two different versions of TMGA1, namely, TMGA1-con and TMGA1-non, are conducted here according to Section 2.3 revealing that the admission of flows is order dependent. In TMGA1-con, a transmission mode is considered to be valid if and only if all its admission orders, s, can lead to the mode. On the contrary, in TMGA1-non, the mode is said to be valid if there exists at least one to confirm its validity. For either of the versions, the algorithm requires Step to update , , and with
(3)
where is the flow in now considered for the proceeding and , and is the set of neighbors, in , located within of 's source node, and is that for 's destination node.
() for each sorted with the increasing order of do
() Step : update , and
() ; Update
() ; Update
() ; Update
() Step : verify for the Trasmit/Receive DOF constraints
() Success;
() if or then
() Success;
() end if
() end for
() if Success () = 1, then
() Success() = 1;
(21) end if
(22) end for
(23) if ((Conservative == 1 and Success () = 1, ) or
(Conservative == 0 and Success () = 1, )) then
(24) ;
(25) end if
(26) end for
(27) Reduce to be that in which s.t.
(28)end for;
(29)Step : merge and output the scheduling matrix
(30)Merge s to form a single , where ;
(31)OUTPUT: of;
Following that, in Step , these updated values are used to verify whether the -stream traffic can be established on without interfering with the other flows according to the DOF constrains given in (1) and (2). If all 's in the are verified successfully, the corresponding could then be conservatively or nonconservatively considered to be an element of ( for ). In addition, to reduce the size of , the 's with their capabilities being subset of the others will not be included. Then, all the reduced 's are merged to form a single scheduling matrix so that its size () can be tractable for the cross-layer design. Finally, after added with an empty as the default element for scheduling, the complete is given in Step .
To be clear, let us review the example in Figure 2. Obviously, this example presents no strong contention and thus TMGA1 only needs to consider a single flow component . As already shown, this example has and . However, they are represented here by and to be the inputs of TMGA1 in addition to , where and . With these inputs, the algorithm generates a set of all possible transmission modes . Among these, we consider the mode of with its two possible admission orders, , as before. For the first order, TMGA1 initializes , , and . Then it updates for with , , and (since ), and the updated values satisfy the DOF constrains by , and . After that, it updates for with , (since ), and , and these also satisfy the DOF constrains by and . Thus, the first order is valid.
Similarly, after the initialization, the update for the second order will start with , resulting in and , as before; but now and thus . Nevertheless, the above still satisfies the DOF constrains. When then updating for , it results in in addition to updated previously. Thus instead of 0, while without change. Consequently, it can only satisfy the receive DOF constrain by , but fails on the transmit DOF constraint since . Finally, with the two s' results, if the nonconservative version (TMGA1-non) is adopted, the transmission mode is accepted; otherwise, if the conservative version (TMGA1-con) is adopted, the mode is rejected.
For the time complexity of TMGA1, we recall and denote by the number of flows that has a strong contention with, where and refer to in and out degrees of the node , respectively. With that, we can let and denote it by . Then, the number of in the network would be if the coloring algorithm in [11] is adopted. Now consider that the th has the number of transmission modes , where (with denoting the total number of flows in ) is the size of this , and is the DOF of its element flow . In the , each transmission mode has admission orders, which is the total number of permutations for the elements (flows). With the above, we can show the time complexity of TMGA1 as .
Although the time complexity could be high as shown in what mentioned above, TMGA1 is the only way to explore all possible transmission modes that are feasible according to the transmit DOF constraint and receive DOF constraint for the MIMO networks. In fact, designing interference-free scheduler for multihop wireless networks is considered to be a hard problem in the literature, and recent works have shown that it is in fact NP complete [12, 13]. Thus, as a rule of thumb, if one has no time to find all the modes with an algorithm such as TMGA1, a possible solution is using a polynomial time heuristic such as the algorithm (TMGA2) shown in what follows to generate a subset of these modes satisfactory enough, within a reasonable time limit.
3.3. Transmission Mode Generating Algorithm 2
In what mentioned before, TMGA1 can find all 's for each . However, the number of s will grow exponentially with the increase of the size of , which would be intractable when it is relatively large. Therefore, we propose here a polynomial time heuristic algorithm, namely, Transmission Mode Generating Algorithm 2, or shortly, TMGA2, that can generate a good subset of 's for each . The central idea of TMGA2 is to consider a as the first flow to be admitted for a -stream flow, and then randomly choose other 's to see if they could cooperatively construct a valid . Note that the starting is chosen with an increasing order and the following s could be the same of , implying that multiple -streams could be established in a single . Furthermore, the seeking process could be repeated several times according to the iteration limit . With that, we can control its time complexity to be satisfactory enough while obtaining a good that can cover all flows in and can evenly distribute the number of times that each flow is included in certain s.
(31) Roll back , , , , , and stamp as failed; Roll back if is not valid
(32) end if
(33) Find the next with and , among not yet examined and not yet failed;
(34) if no can be found then
(35) = FALSE;
(36) else
(37) , , ;
(38) end if
(39) end while
(40) ;
(41) ifthen
(42) = ;
(43) end if
(44) end for
(45) end for
(46) Reduce to be that in which s.t. ;
(47) end for
(48) Merge s to form a single , where is the number of found;
(49) OUTPUT: of;
To fulfill the design aim, we add and in this algorithm in addition to , , and given previously. More precisely, is the set of values associated with s' chosen probabilities. In the current version, the values are given with uniform random numbers, and TMGA2 chooses the next with the lowest value; that is, it will choose uniformly and randomly among the 's. On the other hand, denotes the set of link capabilities for the flows and is obtained by . In addition, two new update rules are considered for and , respectively, as
(4)
In what mentioned previously, is the flow now considered in . Clearly, each neighbor of 's destination node would consume DOFs to null its interference at the receiver if it has data to transmit right after . Thus, conservatively it should take 's into account as a part of its own and then check the transmit DOF constraint to avoid the interference. Symmetrically, each neighbor of 's source node will be interfered with 's transmission if it wants to concurrently receive its own traffic right after . Hence, by taking 's into account as a part of its own for the receive DOF constraint, it could be interference-free in the situation.
In TMGA2, if the optional update and the optional verification (as shown in lines 16 to 17, and lines 25 to 29 in Algorithm 2, resp.) are considered, the algorithm is operated conservatively, and called TMGA2-con. On the other hand, if these optional parts are not involved, then it is TMGA2-non. Obviously, the two versions correspond to those of TMGA1, and their performances will be compared in the experiments.
Let us use Figure 2, again, as our example and set so that the algorithm will consider 1-stream flow for each admission. With the initial and , TMGA2 starts by assuming to be admitted and accordingly updating the related parameters to be and . In the same time, the neighbor of , that is, , should also consume its link capability (DOF) to be interference-free from 's transmission. Thus, is further changed to be . In what follows, it updates 's and with the equations in (3) as TMGA1 does. If TMGA2-non is considered, the algorithm will proceed to examine the next that has the lowest random value and has its link capability equal to or larger than (= 1). Now is the only candidate, and the following process for updating and and verifying the DOF constraints is the same as that for TMGA1. Finally, found is used to update as (1,1), which is the result of this case. Then, with as the new start, the process continues to search other valid , and will end after the searching. In fact, the algorithm is designed to repeat the whole process times, and with the random nature of , each of the iterations may lead to a different complying with our design aim.
Now, let us turn out to focus on the conservative version of TMGA2. As shown in the TMGA1 example, is accepted by TMGA1-non but is rejected by TMGA1-con, because the latter considers both s of and , and finds the second order to be unacceptable. In TMGA2-con, this is done implicitly. To see why, let us reconsider the above process started with . After checking and for , TMGA2-con must also make the optional checks for 's neighbors. In this case, no is the neighbor of 's destination node, and thus no update for its is needed. On the other hand, is the neighbor of 's source node. However, currently has no established traffic and thus has no need to change its . With the unchanged values, the optional verification for is easily passed, in addition to the primary verification for . Consequently, TMGA2-con may go to check the next, that is, , as TMGA2-non would do.
As expected, TMGA2-con first makes the primary update for , which keeps and changes to be 1, then it makes the optional update and finds that is the neighbor of 's destination node and has 1-stream traffic established before. Thus, it changes to be 1. Meanwhile, it finds no neighbor of 's source node, and thus it changes nothing. However, since the optional update changes at least one value (), its optional verification may produce nontrivial results. In fact, it has , indicating that is not valid. Clearly, this example shows that while is examined by the primary update and verification, is also verified by the optional counterpart in TMGA2-con.
For the time complexity of TMGA2, we note that the time complexity for a single is , where denotes the number of edges (flows) in the , that is, . Then, considering graph components (s), and denoting by the maximal in the network, that is, , we can have the polynomial time complexity for TMGA2 as .
4. Cross-Layer Schemes
Now, given a network with MIMO links, the source and destination nodes of end-to-end communication sessions, and the scheduling matrix obtained previously, in this section we aim to find a rate allocation specifying the rate for each session , along with a flow allocation vector specifying the amount of traffic of session routed through link , and a transmission schedule vector specifying time fraction for each transmission mode . More precisely, we want to solve the following optimization problems.
Definition 1.
The Maximum throughput Rate Allocation (MRA) problem seeks a feasible rate allocation vector , along with a feasible flow allocation vector and a feasible transmission schedule vector such that the throughput is maximized.
Definition 2.
The Proportional fair Rate Allocation (PRA) problem seeks a feasible rate allocation vector , along with a feasible flow allocation vector and a feasible transmission schedule vector such that the utility functionis maximized.
Definition 3.
The Weighted fair Rate Allocation (WRA) problem seeks a feasible rate allocation vector, along with a feasible flow allocation vector and a feasible transmission schedule vector suchthat, wheredenotes the positive weight of session , with the assumption of, and the throughputis maximized.
For these problems, we propose our cross-layer schemes with the same basic steps. First, we identify all possible transmission modes or a subset of transmission modes by means of TMGA1 or TMGA2 given previously. Second, we formulate the problems as Linear Programming problems (LP)s and Convex Programming problems (CPs) based on the transmission modes found in above. More precisely, we have the following.
Linear Programming 1 (LP1): MRA
Given
(i)
, node topology graph of the MIMO network.
(ii)
, set of session source nodes, where is the source node of session .
(iii)
, set of session destination nodes, where is the destination node of session .
(iv)
, scheduling matrix.
Variables
(i)
, rate allocation vector, where is the rate allocated for session , .
(ii)
, flow allocation vector for session , where is the session 's traffic routed through link .
(iii)
, transmission schedule vector, where is the time fraction for the transmission mode .
Optimize
(i)
Maximize the total throughput of sessions
(5)
Constraint
(i)
Flow conservation for source nodes
(6)
where () denotes the set of outgoing (incoming) edges of source node .
(ii)
Flow conservation for intermediate nodes
(7)
where () denotes the set of outgoing (incoming) edges of node .
(iii)
Bandwidth conservation
(8)
where is the link capacity or rate of .
(iv)
Scheduling constraint
(9)
(v)
Flow rate validity:
(10)
(vi)
Scheduling validity
(11)
(vii)
Session rate validity
(12)
Remark 1.
(i)
Constraint (6) ensures that the net amount of traffic going out of the source node of a session is equal to that of the end-to-end session rate.
(ii)
Constraint (7) ensures that the amount of traffic of a session entering any intermediate node is equal to that existing the intermediate node.
(iii)
Constraint (8) ensures that the total traffic on a link is no more than the average link transmission rate.
(iv)
Constraint (9) ensures that the summation of all elements in a transmission schedule vector is equal to 1.
(v)
Constraints involving imply that a session can be routed through different links, s. That is, a session can go through several different routes towards its destination, which is called traffic splittable.
Linear Programming 2 (LP2): WRA
We have
(13)
subject to the constraints (6)–(12), and
(14)
When compared with the objective of LP1 that only maximizes the network throughput and involves no consideration for fairness, LP2 has the extra constraint (14) for the weighted fairness among the session traffics. That is, LP2 aims to maximize the throughput while preserving the weighted fair shares in the sessions.
On the other hand, the PRA problem can be formulated as a convex program because it has the same linear constraints as the MRA problem and the objective is to maximize a concave utility function. That is,
Convex Programming 1 (CP1): PRA
We have
(15)
subject to the constraints (6) to (12).
There are efficient algorithms for solving LPs and CPs [14, 15]. In our experiments, we use MATLAB to solve the LPs, and its CVX package [16] to solve the CPs. Their results are given in the following section.
5. Experiment Results
In this section, we report on simulation experiments made in order to verify the cross-layer schemes designed previously. To this end, different sets of experiments are conducted to exhibit their distinct performances on different network topologies frequently used. In addition, we take into account that throughput is in fact affected by link capability or rate. Thus, to focus on the schemes' correctness and compare their performance, we assume that each antenna (DOF) in the MIMO system has the same capability (of 1). The rate allocated to each session, , and the system throughput, , are normalized by the capability to provide their values independent of a certain system.
5.1. Wireless Backhaul Network
A wireless backhaul network (WBN) is considered as a collection of access points (APs), along with the uplink (to the Internet) and downlink (from the Internet) demands for each AP. The MAC layer adopted is usually assumed to schedule data to multiple receivers across timeslots using a TDMA-based scheme, which complies with our scenarios. For the network, we consider only uplink traffics conveyed with a common wireless channel shared by the MIMO links. In addition, we consider also that access traffic from the users to their respective APs is transmitted in a separate frequency band, and does not interfere with the wireless backhaul traffic considered here. For WBNs, the cross-layer schemes can be used to schedule the MIMO links without interference, and to maximize the system throughput according to the traffic demands form APs.
5.1.1. Topology 1
Let's re-examine the topology in Figure 2, and regard it as a backhaul network as follows. That is, now represents the set of APs, each with DOF of 2, and node 1 denotes the AP connecting to the Internet, which is usually referred to as Transit Access Point (TAP). With these APs, , , and are so conducted to compose the flow set , reasonably representing that all uplink traffics are destined to the wired Internet. Clearly, every AP has its own traffic toward TAP, and thus the three sessions involved would be = 2, = 1), = 3, = 1), and , = 1) (where denotes the source-destination pair of session ). Given the above, it is easy to derive showing that and strongly contend with each other, and so do and . Accordingly, with the coloring algorithm, they are divided into two flow components, and , containing only weak contentions. For these components, TMGA1 and TMGA2 both can easily produce and . After padding its 's with zeros for the flows not in the component, respectively, the two 's are merged to be the complete scheduling matrix , wherein an empty is added as the default element for scheduling.
Now, with a DOF to represent a unit of transmission capability, produces . That is, only by routing session 1 through and sacrificing all other sessions (with and ), the system can have the maximum system throughput 2. In addition, it produces , saying that only should be scheduled in the MIMO network. In other words, the system throughput is dominated by the APs closet to TAP. The unfairness problem has also been reported in [17, 18]. However, unlike the previous works, we address here joint rate control, routing, and scheduling for the MIMO-based wireless backhaul networks with a scheduling-based (TDMA-based) MAC. To be specific, with we can achieve the weighted fairness among the sessions while maximizing the aggregated system throughput. More precisely, LP2 produces, for example, , exactly complying with the given weights . The corresponding routes are constituted by . For the requirements on link capability, a TDMA-based MAC over the MIMO PHY is scheduled with and . Accordingly, the link capabilities can fulfill the requirement of (0.7692 + 0.3846 + 0.1538 = 1.3076), that of (0 + 0.3846 + 0.1538 = 0.5384), and that of (0 + 0 + 0.1538 = 0.1538). Finally, for solving the PRA problem, CP1 produces and improves the fairness problem when compared with LP1. However, it lacks the capability of achieving weighted fairness, and it would inevitably sacrifice the system throughput as LP2 may do.
5.1.2. Topology 2
Let us now consider the example in Figure 3. In principle, it can be also regarded as a wireless backhaul network with node 1 as TAP and other nodes as APs. With the more complex topology, our aim is to show how the cross-layer schemes can find multiple routes for a session to fulfill their specific maximization goals. To this end, three sessions , ), , ), and , ) are conducted for the leaf nodes (6, 7, and 8). Given that, produces . To support these session rates, a single route to TAP (node 1) is allocated to the first two sessions, respectively. That is, the route for the first session is and that for the second is , in which every single flow contributes the data rate of 0.3781 to its session. On the other hand, finds two routes for the third session: and . In what mentioned above, each flow provides its rate of 0.2885. Then, by combining the two routes, it can support . Similarly, by setting , can give each session the same rate allocation , with the same routes obtained in what mentioned above. Finally, CP1 also finds the same equal rate allocation as LP2, and thus, it has the same implication on the fairness in this case.
5.2. Wireless Mesh Network
In this set of experiments, we randomly generate wireless mesh networks (WMNs) with nodes located in a 1000 1000 m2 region. The transmission range () and the corresponding interference range () are set to 400 m and 600 m, respectively. In addition, these networks are so conducted to ensure their connectivity of the resulting topologies. Then, the cross-layer schemes are examined on these networks to provide their performances on rate allocated to each session, throughput, and weighted fairness. In particular, the sessions are sorted in the increasing order of their rate values to clearly show their performance differences.
As the first part of this experiment set, we examine our cross-layer schemes on a network with 15 nodes, as shown in Figure 4. In the network, we equip each node with 2 antennas and generate 10 communication sessions with their source and destination nodes to be randomly generated so that no two sessions have the same sources and destinations. Note that, in this example, the maximum number of flows in a is 18, and clearly, the number of permutations for the elements (flows), that is, its , is generally an intractable value for computation.
Figure 4
Random topology for the experiment.
×
A similar situation also happens to the problem of finding Maximal Independent Sets (MISs). Although the algorithm in [19] can be used to find all MISs, it is still intractable that the number of MISs will grow exponentially with the increase of the graph size, and this is the reason why we need to develop TMGA2. In the experiment, TMGA2 is used to generate transmission modes with and , respectively. The corresponding rate allocation results are shown in Figure 5. As expected, the MRA scheme can give certain sessions the highest 's, but it also results in a severe unfairness on the rate allocation. This can be seen in the figure that the first several sessions sorted have their rates equal to zero but the latter ones obtain very high values. On the contrary, the WRA scheme performs best in terms of fairness. In fact, with , the rate allocated to each session is the same. Note that the WRA scheme has the capability to achieve arbitrary weighted fairness among the sessions. However, in the experiments, we simply show the equal weight results. Between the two extremes, the PRA scheme is much better than the MRA scheme on the fairness, but it cannot achieve an absolutely even distribution, and certainly it cannot achieve the weighted fairness. Finally, it could be seen that with the conservative generating approach, labeled with "(con)," the three schemes tend to have their rate allocations lower than those with the nonconservative counterparts, labeled with "(non)." This trend is further verified in the following experiments.
Figure 5
Rate allocation results for the experimented sessions: (a) = 1, and (b) = 10.
×
In the second part of the experiments, we aim to compare the conservative and the nonconservative transmission mode generating approaches in TMGA1 and TMGA2 and to evaluate the efficiency of TMGA2. In fact, TMGA1 is used here as a benchmark because it can generate all possible transmission modes (s) and can give the cross-layer schemes the most complete scheduling matrix (). However, to be numerically tractable for TMGA1, we run the experiments on a smaller network that has 6 nodes and 6 sessions with the same setting given previously. In this network, each node is randomly equipped with 1 or 2 antennas, and three numbers of iteration limit, , , and , are examined for TMGA2. In addition, to quantitatively analyze the fairness performances for these schemes, we let denote the throughput of session , and let denote the associated weight, and we use these parameters to obtain the fairness index in [20] as follow:
(16)
The results are shown in Figure 6, wherein "All" denotes that for TMGA1. With this figure, we summarize our observations from the following two aspects. First, from the throughput aspect in Figure 6(a), we can see that the MRA scheme achieves the highest values in spite of . That is to say, although a larger may lead to a larger number of 's in , it does not affect MRA's throughput performance here. This is because MPA could always maximize a single session while sacrificing all other sessions with s obtained, as indicated in Section 5.1. Similarly, does not affect much PRA and WRA with conservative 's. However, if given nonconservative 's, it has stronger impacts on the two schemes. This is because a larger resulted may open more opportunities for these schemes to optimize their target functions, and the nonconservative 's found would have their sizes larger than the conservative counterparts. Apart from these differences, we note also that the 's resulted from or 2 would be enough for most of the schemes. Even so, one may still expect a nonconservative for higher throughputs, despite . However, the higher throughputs are obtained with the costs of providing a more strict admission control that can correctly admit its sessions with the admission orders ('s) recorded to realize the 's in a given nonconservative . On the other hand, with a conservative , every possible would be already considered for a , and thus no such overheads would be involved.
Figure 6
Throughput and fairness results for the experimented sessions: (a) throughput and (b) fairness.
×
As the second aspect, we consider the fairness results in Figure 6(b). Clearly, it is shown that the WRA scheme perfectly achieves the weighted fairness of , and its fairness index values are all of 1 in spite of . On the other hand, the PRA scheme has its values ranging from 0.7 to 0.9, and the MRA scheme does not exceed 0.52. In addition, similar trends for the throughput results also hold here. For example, the nonconservative 's usually provide better performances than the conservative counterparts. However, we note that a higher improves most the PRA scheme on the throughput, but it improves most the MRA scheme on the fairness. Thus, it is suggested that one may choose depending on the performance metric most concerned. Nevertheless, in general, or 2 could satisfy these schemes with low time complexity, as indicated previously.
As the final part of the experiments, we examine TMGA2 with more topologies to know its effectiveness. To be specific, we let and conduct two sets of experiments that are numerically tractable for this aim. Specifically, by randomly deploying 6 nodes and 6 sessions in the network, we conduct 30 different topologies as the first set of experiments. Note that although this set has the same numbers as the above, with the variation it actually results in very different topologies and traffic conditions to be considered. With the same way, we conduct another 30 topologies as the second set of experiments, but now there are 10 nodes and 8 sessions randomly deployed to reasonably represent the different numbers of nodes and sessions that may involve.
The throughput and fairness results for the first set are given in Figures 7(a) and 7(b), respectively. From these figures, we can easily see that the two performance metrics are significantly varied by the different topologies, as expected. However, for each single topology, the relative relationships among the results of these schemes have the same trend as Figure 6 has shown. Clearly, this trend can be also observed in Figures 7(c) and 7(d) for the results of the second set. With the above, it could be said that the proposed schemes in TMGA2 are able to generate the transmission modes that can efficiently fulfill the design aim of solving the MRA, PRA, and WRA problems in spite of the topologies with the different numbers of nodes and sessions.
Figure 7
Throughput and fairness results for the different network scenarios: (a) throughput for the 6-node topologies, (b) fairness for the 6-node topologies, (c) throughput for the 10-node topologies, and (d) fairness for the 10-node topologies.
×
6. Conclusion
In this work, we take into account the fact that for fully realizing the potential of MIMO technology, higher layer must be designed to be cognizant of the MIMO link capability. To this end, instead of simply translating the achievable gain for individual MIMO links into end-to-end gain in the network, we present a mathematical framework that can express the cross-layer gain on throughput as a function of network routing, link scheduling, and stream control in the presence of interference. With that, we propose Transmission Mode Generating Algorithms (TMGAs) to generate TDMA-based scheduling matrices and give our Linear Programming- (LP-) based and Convex Programming- (CP-) based schemes to maximize the network throughput, and to achieve certain fairness (such as weighted fairness, in particular) at the same time. The simulation experiments' results show that the proposed schemes are all capable on achieving our design aims, and every scheme has its own unique performance benefit and tradeoff between throughput and fairness.
Open AccessThis article is distributed under the terms of the Creative Commons Attribution 2.0 International License (https://creativecommons.org/licenses/by/2.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
of nodes where each node
is stationary and has a MIMO antenna array with
elements or DOFs for each node to transmit and receive signals. All nodes transmit at the same fixed power level in a signal common channel, and each node has a uniform transmission range
and a uniform interference range
. Let
denote the set of all pairs
of distinct nodes in
such that
and
are within each other's transmission range. An ordered pair of nodes
in
is said to form a flow
if node
needs to transmit to node
.
is said to be active if
is currently transmitting to
; otherwise,
is said to be inactive. Let
denote the set of all flows. Hereafter, the graph
defined above is referred to as node topology graph.
antennas are used at the both ends. To transmit a signal
through a transmit beamformer over the 2-antenna array, the transmitter sends two weighted copies of the signal, one on each antenna. That is,
is sent over antenna 1, and
is sent over antenna 2, with
called the transmitting weight vector. Then, the two signals are weighted by the receiver with a receiving weight vector
and summed to produce
. Let
denote the matrix of channel coefficients between the transmitter and the receiver. The above can thus be written as
, and the complex gain experienced by
is then a consequence of transmit beamforming, the channel, and receive beamforming of
. Now with appropriate weight vectors
and
, the received signal
can achieve a unit gain (
) if it is received at the desired receiver or a zero gain (
) if it is received at a nondesired receiver. In other words, we can ensure that the signal is received with a certain gain or is perfectly nulled by appropriately choosing the weight vectors if no power limit on a node's receiving capacity. In general, we could design
if
is given, and vice versa. Thus, by considering whether the transmitter and the receiver are a desired communication pair or potentially interference with one another, we have the following beamforming conditions.
is the desired receiver of
and
is fixed, then we could require
to satisfy
so that
can be received with unit gain.
is already involved in another link, then
is fixed and we could require
to satisfy
so that the transmitter does not create interference at this receiver.
, and the receiver corresponding to
wants to receive signals from different transmitter without interference, then we could require
to satisfy
so as to null the contribution of
at the receiver.
shown in Figure 2, where
,
, and
. Assume that (
) every link has the same
and
, (
) the numbers of antennas are
and
, and (
)
and
are the only two flows in the network. With the above, we consider the example that node 4 wants to transmit to node 3 while node 2 is currently transmitting to node 1 (i.e.,
is active). Let
be the (1
1) transmitting weight vector that node 2 is currently using to weight its transmitted signal and let
be the (1
1) receiving weight vector that node 1 is currently using to weight the signal received from node 2. In this case that
is currently active, if node 3 wants to receive an interference-free signal from node 4, it must design its receiving weight vector
to suppress the interference caused by node 2's transmission while assuring an acceptable gain of its intended signal coming form node 4. In terms of equations, the above can be written as
and
, where
is the transmitting weight vector of node 4, and
is the receiving weight vector of node 3. Now, given
,
,
and
, the system of these two equations would have a unique solution
because the elements of each of
, and
are i.i.d in general. That is, if there is no power limit on node 3's receiving capacity, it is always possible for node 3 to receive one interference-free flow from node 4 concurrently with the signals from node 2. In other words,
and
are always possible to be active simultaneously in this example. 
is active). With similar considerations for the above, this example can be represented by the equations of
and
, but now the objective to be solved becomes
, which is (1
1) weight vector. That is, the single variable
involves the system of the two equations associated with
and
that are i.i.d in general. Obviously, the over-determined system has no solution.
) is order dependent. That is, if
is admitted first, then
is possibly admitted. On the contrary, if
is admitted first, then
could not be admitted without inference. Clearly, these could be verified with the beamforming conditions given previously. However, to be specific, we define the transmission constraints as follows. Let node
be the transmitter and node
the receiver, and suppose that there are
streams currently received by nodes located within
's interference range, and
streams currently transmitted by nodes located within
's interference range, where a steam denotes a copy of data signal transmitted by the MIMO system. Suppose further that
wants to transmit an
-stream flow
to
. Then, for interference-free communications in the system, we have the following constraints.
can transmit an
-stream flow
to
without interfering with the
streams concurrently received by
's neighbors if
denote the set of
's neighbors that are receiving the
streams and
denote the number of streams that node
is currently receiving, for all
(i.e.,
). Suppose that for each
,
knows the receiving weight vector of
, and the channel matrix between it and
. Then,
can transmit its
-stream flow
to
with the weight vectors
subject to the conditions of
, where
is the column vector of length
defined as
with 1 at the
th position, and
is the
matrix defined as
with
and
, for all
. Because the elements of each
involved would be i.i.d in general, the system of equations
with
of the size of
, would have no solution if
.
can receive an
-stream flow
from
without interfering with the
streams concurrently transmitted by
's neighbors if
denote the set of
's neighbors that are transmitting the
streams and
denote the number of streams that node
is currently transmitting, for all
(i.e.,
). Suppose that for each
,
knows the transmitting weight vector of
, and the channel matrix between it and
, for all
. Then,
can receive its
-stream flow
from
with the weight vectors
subject to the conditions of
, where
is the column vector of length
defined as
with 1 at the
th position, and
is the
matrix defined as
with
and
, for all
. Because the elements of each
involved would be i.i.d in general, the system of equations
with
of the size of
would have no solution if
.
and
are said to strongly contend with each other if and only if
or
. Given that, we define
as the strong contention graph, where a vertex in
corresponds to a flow in
, and a bidirectional edge in
denotes the corresponding flows in
strongly contend with each other in the node topology graph
.
as the weak contention graph. In this graph, a directional edge between a pair of vertices corresponding to
and
in
arises if any one of the three weak-interference conditions holds: (
)
, (
)
, and (
) there exists a
(possibely
or
) such that
and
or
. To be specific, we consider a MIMO network of 8 nodes and 8 flows as an example, showing its node topology graph
in Figure 3(a) and the derived
and
in Figures 3(b) and 3(c), respectively. For example, we can see in Figure 3(a) that when node 4 is transmitting to node 2 (with
), node 2 cannot simultaneously transmit to node 1 (with
), and vice versa. This is a strong interference, and is denoted by a bidirectional edge between
and
in Figure 3(b). Similarly, we can also see in Figure 3(a) that when node 8 simultaneously transmits to node 4 and node 5,
and
will contend with each other. This corresponds to the first weak-interference condition, and is shown by a bidirectional edge between
and
in Figure 3(c). In addition, the second weak-interference condition is exemplified by the scenario in Figure 3(a) that nodes 2 and 3 simultaneously send to node 1, and thus
and
interfere with each other. Therefore, there is a bidirectional edge between
and
in Figure 3(c). Finally, the third weak-interference condition can be found in Figure 3(a) that when node 4 transmits to node 2 (with
), this node can interfere with node 1's receipt of
from node 3. This interference is shown by a directional edge from
to
in Figure 3(c). Besides, the other strong and weak interferences not exemplified in the above can be also observed easily.
, (b) the corresponding strong contention graph
, and (c) the corresponding weak contention graph
.
, that contain only weak contentions and can be represented by
. This step is done by finding a valid coloring for
with, for example, the greedy algorithm given in [11] that sorts vertices in
by decreasing vertex degrees, and according to the order, colors them one by one using a first-fit greedy approach. Then, the flows of
with the same color in
compose a
, and the corresponding subset of
composes a
.
and
, we now proceed to find an interference-free scheduling for each of the components with a scheduling-based MAC. To this end, we define transmission mode as the flows in
that can be active simultaneously. A
matrix
is used to represent the set of transmission modes, and called scheduling matrix, in which
denotes the number of transmission modes, and
denotes the number of flows in
. In the matrix, a row represents a transmission mode
, and its element
represents the number of traffic streams utilized by flow
in this mode. That is, a
is a vector denoting a possible set of transmissions from all
flows in a time slot. By definition, all flows with traffic streams in a transmission mode can be activated simultaneously. However, the concurrent flows may interfere with each other in the MIMO network. Thus, the scheduling algorithms should firstly generate interference-free
s for constructing a desired
. Next, with these modes representing the time slots to be used, they are expected to determine the time fraction
for every transmission mode or time slot to compose a TDMA frame that can satisfy the scheduling target. Accordingly, the scheduling algorithms should secondly find the frame length and the number of active time slots of each transmission mode in one frame. This can be done by considering that if the value of
for every
is given, the frame length is then the smallest positive integer
such that
is an integer for every transmission mode, and the number of active times for a
is simply its
. Now, given the two aims of the scheduling algorithms, we proceed to develop the transmission mode generating algorithms for
s in the next subsection, and leave the methods for determining
s till Section 4.
, the set of destination DOFs
, and the set of weak contention graphs
, for the flow components
obtained previously. For each
, the algorithm generates all possible transmission modes
s, according to the component's
and
. Then, each of the modes is examined for its validity conservatively or nonconservatively. Two different versions of TMGA1, namely, TMGA1-con and TMGA1-non, are conducted here according to Section 2.3 revealing that the admission of flows is order dependent. In TMGA1-con, a transmission mode is considered to be valid if and only if all its admission orders,
s, can lead to the mode. On the contrary, in TMGA1-non, the mode is said to be valid if there exists at least one
to confirm its validity. For either of the versions, the algorithm requires Step
to update
,
, and
with
is the flow in
now considered for the proceeding
and
, and
is the set of neighbors, in
, located within
of
's source node, and
is that for
's destination node.
) INPUT:
,
,
,
;
)for all
do
) Generate all transmission modes,
s, for
) for all
do
) Generate all admission orders,
s, for
;
) for all
do
=
,
=
,
=
;
) for each
sorted with the increasing order of
do
)
Step
: update
,
and
)
;
Update
)
;
Update
)
;
Update
)
Step
: verify for the Trasmit/Receive DOF constraints
) Success
;
) if
or
then
) Success
;
) end if
) end for
) if Success (
) = 1,
then
) Success(
) = 1;
) = 1,
) or
) = 1,
)) then
;
to be that in which
s.t.
Step
: merge and output the scheduling matrix
s to form a single
, where
;
of
;
, these updated values are used to verify whether the
-stream traffic can be established on
without interfering with the other flows according to the DOF constrains given in (1) and (2). If all
's in the
are verified successfully, the corresponding
could then be conservatively or nonconservatively considered to be an element of
(
for
). In addition, to reduce the size of
, the
's with their capabilities being subset of the others will not be included. Then, all the reduced
's are merged to form a single scheduling matrix
so that its size (
) can be tractable for the cross-layer design. Finally, after added with an empty
as the default element for scheduling, the complete
is given in Step
.
. As already shown, this example has
and
. However, they are represented here by
and
to be the inputs of TMGA1 in addition to
, where
and
. With these inputs, the algorithm generates a set of all possible transmission modes
. Among these, we consider the mode of
with its two possible admission orders,
, as before. For the first order, TMGA1 initializes
,
, and
. Then it updates for
with
,
, and
(since
), and the updated values satisfy the DOF constrains by
, and
. After that, it updates for
with
,
(since
), and
, and these also satisfy the DOF constrains by
and
. Thus, the first order
is valid.
, resulting in
and
, as before; but now
and thus
. Nevertheless, the above still satisfies the DOF constrains. When then updating for
, it results in
in addition to
updated previously. Thus
instead of 0, while
without change. Consequently, it can only satisfy the receive DOF constrain by
, but fails on the transmit DOF constraint since
. Finally, with the two
s' results, if the nonconservative version (TMGA1-non) is adopted, the transmission mode
is accepted; otherwise, if the conservative version (TMGA1-con) is adopted, the mode is rejected.
and denote by
the number of flows that
has a strong contention with, where
and
refer to in and out degrees of the node
, respectively. With that, we can let
and denote it by
. Then, the number of
in the network would be
if the coloring algorithm in [11] is adopted. Now consider that the
th
has the number of transmission modes
, where
(with
denoting the total number of flows in
) is the size of this
, and
is the DOF of its element flow
. In the
, each transmission mode has
admission orders, which is the total number of permutations for the
elements (flows). With the above, we can show the time complexity of TMGA1 as
.
's for each
. However, the number of
s will grow exponentially with the increase of the size of
, which would be intractable when it is relatively large. Therefore, we propose here a polynomial time heuristic algorithm, namely, Transmission Mode Generating Algorithm 2, or shortly, TMGA2, that can generate a good subset of
's for each
. The central idea of TMGA2 is to consider a
as the first flow to be admitted for a
-stream flow, and then randomly choose other
's
to see if they could cooperatively construct a valid
. Note that the starting
is chosen with an increasing order and the following
s could be the same of
, implying that multiple
-streams could be established in a single
. Furthermore, the seeking process could be repeated several times according to the iteration limit
. With that, we can control its time complexity to be satisfactory enough while obtaining a good
that can cover all flows in
and can evenly distribute the number of times that each flow is included in certain
s.
) INPUT:
,
,
,
,
,
;
)for all
do
) Initialize
;
) for
to
do
) Initialize
,
=
,
=
,
=
;
) for
to
do
) Initialize
=
,
=
,
=
,
,
= TRUE;
)
,
;
;
) while
== TRUE do
) if
then
)
Primary update:
)
;
Update
)
;
Update
#1
)
;
Update
#1
)
Optional update:
)
with
;
Update
#2
)
with
;
Update
#2
) end if
) Success
;
)
Primary verification:
or
then
;
Optional verification:
with
do
or
then
;
then
,
,
,
,
, and stamp
as failed;
Roll back if
is not valid
with
and
, among
not yet examined and not yet failed;
can be found then
= FALSE;
,
,
;
;
then
=
;
to be that in which
s.t.
;
s to form a single
, where
is the number of
found;
of
;
and
in this algorithm in addition to
,
, and
given previously. More precisely,
is the set of values associated with
s' chosen probabilities. In the current version, the values are given with uniform random numbers, and TMGA2 chooses the next
with the lowest value; that is, it will choose uniformly and randomly among the
's. On the other hand,
denotes the set of link capabilities for the flows and is obtained by
. In addition, two new update rules are considered for
and
, respectively, as
is the flow now considered in
. Clearly, each neighbor of
's destination node would consume
DOFs to null its interference at the receiver if it has data to transmit right after
. Thus, conservatively it should take
's
into account as a part of its own
and then check the transmit DOF constraint to avoid the interference. Symmetrically, each neighbor of
's source node will be interfered with
's transmission if it wants to concurrently receive its own traffic right after
. Hence, by taking
's
into account as a part of its own
for the receive DOF constraint, it could be interference-free in the situation.
so that the algorithm will consider 1-stream flow for each admission. With the initial
and
, TMGA2 starts by assuming
to be admitted and accordingly updating the related parameters to be
and
. In the same time, the neighbor of
, that is,
, should also consume its link capability (DOF) to be interference-free from
's transmission. Thus,
is further changed to be
. In what follows, it updates
's
and
with the equations in (3) as TMGA1 does. If TMGA2-non is considered, the algorithm will proceed to examine the next
that has the lowest random value
and has its link capability
equal to or larger than
(= 1). Now
is the only candidate, and the following process for updating
and
and verifying the DOF constraints is the same as that for TMGA1. Finally,
found is used to update
as (1,1), which is the result of this case. Then, with
as the new start, the process continues to search other valid
, and will end after the searching. In fact, the algorithm is designed to repeat the whole process
times, and with the random nature of
, each of the iterations may lead to a different
complying with our design aim.
is accepted by TMGA1-non but is rejected by TMGA1-con, because the latter considers both
s of
and
, and finds the second order to be unacceptable. In TMGA2-con, this is done implicitly. To see why, let us reconsider the above process started with
. After checking
and
for
, TMGA2-con must also make the optional checks for
's neighbors. In this case, no
is the neighbor of
's destination node, and thus no update for its
is needed. On the other hand,
is the neighbor of
's source node. However,
currently has no established traffic and thus has no need to change its
. With the unchanged values, the optional verification for
is easily passed, in addition to the primary verification for
. Consequently, TMGA2-con may go to check the next, that is,
, as TMGA2-non would do.
, which keeps
and changes
to be 1, then it makes the optional update and finds that
is the neighbor of
's destination node and has 1-stream traffic established before. Thus, it changes
to be 1. Meanwhile, it finds no neighbor of
's source node, and thus it changes nothing. However, since the optional update changes at least one value (
), its optional verification may produce nontrivial results. In fact, it has
, indicating that
is not valid. Clearly, this example shows that while
is examined by the primary update and verification,
is also verified by the optional counterpart in TMGA2-con.
is
, where
denotes the number of edges (flows) in the
, that is,
. Then, considering
graph components (
s), and denoting by
the maximal
in the network, that is,
, we can have the polynomial time complexity for TMGA2 as
.
with MIMO links, the source and destination nodes of
end-to-end communication sessions, and the scheduling matrix
obtained previously, in this section we aim to find a rate allocation
specifying the rate
for each session
, along with a flow allocation vector
specifying the amount of traffic
of session
routed through link
, and a transmission schedule vector
specifying time fraction
for each transmission mode
. More precisely, we want to solve the following optimization problems.
, along with a feasible flow allocation vector and a feasible transmission schedule vector such that the throughput
is maximized.
, along with a feasible flow allocation vector and a feasible transmission schedule vector such that the utility function
is maximized.
, along with a feasible flow allocation vector and a feasible transmission schedule vector suchthat
, where
denotes the positive weight of session
, with the assumption of
, and the throughput
is maximized.
, node topology graph of the MIMO network.
, set of session source nodes, where
is the source node of session
.
, set of session destination nodes, where
is the destination node of session
.
, scheduling matrix.
, rate allocation vector, where
is the rate allocated for session
,
.
, flow allocation vector for session
, where
is the session
's traffic routed through link
.
, transmission schedule vector, where
is the time fraction for the transmission mode
.
(
) denotes the set of outgoing (incoming) edges of source node
.
(
) denotes the set of outgoing (incoming) edges of node
.
is the link capacity or rate of
.
imply that a session
can be routed through different links,
s. That is, a session can go through several different routes towards its destination, which is called traffic splittable.
, and the system throughput,
, are normalized by the capability to provide their values independent of a certain system.
now represents the set of APs, each with DOF of 2, and node 1 denotes the AP connecting to the Internet, which is usually referred to as Transit Access Point (TAP). With these APs,
,
, and
are so conducted to compose the flow set
, reasonably representing that all uplink traffics are destined to the wired Internet. Clearly, every AP has its own traffic toward TAP, and thus the three sessions involved would be
= 2,
= 1),
= 3,
= 1), and
,
= 1) (where
denotes the source-destination pair of session
). Given the above, it is easy to derive
showing that
and
strongly contend with each other, and so do
and
. Accordingly, with the coloring algorithm, they are divided into two flow components,
and
, containing only weak contentions. For these components, TMGA1 and TMGA2 both can easily produce
and
. After padding its
's with zeros for the flows not in the component, respectively, the two
's are merged to be the complete scheduling matrix
, wherein an empty
is added as the default element for scheduling.
produces
. That is, only by routing session 1 through
and sacrificing all other sessions (with
and
), the system can have the maximum system throughput 2. In addition, it produces
, saying that only
should be scheduled in the MIMO network. In other words, the system throughput is dominated by the APs closet to TAP. The unfairness problem has also been reported in [17, 18]. However, unlike the previous works, we address here joint rate control, routing, and scheduling for the MIMO-based wireless backhaul networks with a scheduling-based (TDMA-based) MAC. To be specific, with
we can achieve the weighted fairness among the sessions while maximizing the aggregated system throughput. More precisely, LP2 produces, for example,
, exactly complying with the given weights
. The corresponding routes are constituted by
. For the requirements on link capability, a TDMA-based MAC over the MIMO PHY is scheduled with
and
. Accordingly, the link capabilities
can fulfill the requirement of
(0.7692 + 0.3846 + 0.1538 = 1.3076), that of
(0 + 0.3846 + 0.1538 = 0.5384), and that of
(0 + 0 + 0.1538 = 0.1538). Finally, for solving the PRA problem, CP1 produces
and improves the fairness problem when compared with LP1. However, it lacks the capability of achieving weighted fairness, and it would inevitably sacrifice the system throughput as LP2 may do.
,
),
,
), and
,
) are conducted for the leaf nodes (6, 7, and 8). Given that,
produces
. To support these session rates, a single route to TAP (node 1) is allocated to the first two sessions, respectively. That is, the route for the first session is
and that for the second is
, in which every single flow contributes the data rate of 0.3781 to its session. On the other hand,
finds two routes for the third session:
and
. In what mentioned above, each flow provides its rate of 0.2885. Then, by combining the two routes, it can support
. Similarly, by setting
,
can give each session
the same rate allocation
, with the same routes obtained in what mentioned above. Finally, CP1 also finds the same equal rate allocation as LP2, and thus, it has the same implication on the fairness in this case.
nodes located in a 1000
1000 m2 region. The transmission range (
) and the corresponding interference range (
) are set to 400 m and 600 m, respectively. In addition, these networks are so conducted to ensure their connectivity of the resulting topologies. Then, the cross-layer schemes are examined on these networks to provide their performances on rate allocated to each session, throughput, and weighted fairness. In particular, the sessions are sorted in the increasing order of their rate values to clearly show their performance differences.
in a
is 18, and clearly, the number of permutations for the
elements (flows), that is, its
, is generally an intractable value for computation.
and
, respectively. The corresponding rate allocation results are shown in Figure 5. As expected, the MRA scheme can give certain sessions the highest
's, but it also results in a severe unfairness on the rate allocation. This can be seen in the figure that the first several sessions sorted have their rates equal to zero but the latter ones obtain very high values. On the contrary, the WRA scheme performs best in terms of fairness. In fact, with
, the rate allocated to each session
is the same. Note that the WRA scheme has the capability to achieve arbitrary weighted fairness among the sessions. However, in the experiments, we simply show the equal weight results. Between the two extremes, the PRA scheme is much better than the MRA scheme on the fairness, but it cannot achieve an absolutely even distribution, and certainly it cannot achieve the weighted fairness. Finally, it could be seen that with the conservative generating approach, labeled with "(con)," the three schemes tend to have their rate allocations lower than those with the nonconservative counterparts, labeled with "(non)." This trend is further verified in the following experiments. 
= 1, and (b)
= 10.
s) and can give the cross-layer schemes the most complete scheduling matrix (
). However, to be numerically tractable for TMGA1, we run the experiments on a smaller network that has 6 nodes and 6 sessions with the same setting given previously. In this network, each node is randomly equipped with 1 or 2 antennas, and three numbers of iteration limit,
,
, and
, are examined for TMGA2. In addition, to quantitatively analyze the fairness performances for these schemes, we let
denote the throughput of session
, and let
denote the associated weight, and we use these parameters to obtain the fairness index in [20] as follow:
. That is to say, although a larger
may lead to a larger number of
's in
, it does not affect MRA's throughput performance here. This is because MPA could always maximize a single session while sacrificing all other sessions with
s obtained, as indicated in Section 5.1. Similarly,
does not affect much PRA and WRA with conservative
's. However, if given nonconservative
's, it has stronger impacts on the two schemes. This is because a larger
resulted may open more opportunities for these schemes to optimize their target functions, and the nonconservative
's found would have their sizes larger than the conservative counterparts. Apart from these differences, we note also that the
's resulted from
or 2 would be enough for most of the schemes. Even so, one may still expect a nonconservative
for higher throughputs, despite
. However, the higher throughputs are obtained with the costs of providing a more strict admission control that can correctly admit its sessions with the admission orders (
's) recorded to realize the
's in a given nonconservative
. On the other hand, with a conservative
, every possible
would be already considered for a
, and thus no such overheads would be involved. 
, and its fairness index values are all of 1 in spite of
. On the other hand, the PRA scheme has its values ranging from 0.7 to 0.9, and the MRA scheme does not exceed 0.52. In addition, similar trends for the throughput results also hold here. For example, the nonconservative
's usually provide better performances than the conservative counterparts. However, we note that a higher
improves most the PRA scheme on the throughput, but it improves most the MRA scheme on the fairness. Thus, it is suggested that one may choose
depending on the performance metric most concerned. Nevertheless, in general,
or 2 could satisfy these schemes with low time complexity, as indicated previously.
and conduct two sets of experiments that are numerically tractable for this aim. Specifically, by randomly deploying 6 nodes and 6 sessions in the network, we conduct 30 different topologies as the first set of experiments. Note that although this set has the same numbers as the above, with the variation it actually results in very different topologies and traffic conditions to be considered. With the same way, we conduct another 30 topologies as the second set of experiments, but now there are 10 nodes and 8 sessions randomly deployed to reasonably represent the different numbers of nodes and sessions that may involve.