Cross-Layer Design for End-to-End Throughput Maximization and Fairness in MIMO Multihop Wireless Networks

Abstract

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.

(ProQuest: ... denotes non-US-ASCII text omitted.)

Jain-Shing Liu 1 and Chun-Hung Richard Lin 2 and Kuang-Yuan Tung 2

Recommended by A. Lee Swindlehurst

1, Department of Computer Science and Information Engineering, Providence University, 200 Chung Chi Rd., Shalu, Taichung Hsien 43301, Taiwan
2, Department of Computer Science and Engineering, National Sun Yat-Sen University, No. 70, Lienhai Rd., Kaohsiung 80424, Taiwan

Received 12 August 2009; Accepted 7 February 2010

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.

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 V of nodes where each node m∈V is stationary and has a MIMO antenna array with _Km 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 _RT and a uniform interference range _RI ≥_RT . Let E denote the set of all pairs (m,n) of distinct nodes in V such that m and n are within each other's transmission range. An ordered pair of nodes (m,n) in E is said to form a flow f=(m,n)... if node m needs to transmit to node n . f is said to be active if m is currently transmitting to n ; otherwise, f is said to be inactive . Let F denote the set of all flows. Hereafter, the graph G=(V,E,F) 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 N=2 antennas are used at the both ends. To transmit a signal x(t) through a transmit beamformer over the 2-antenna array, the transmitter sends two weighted copies of the signal, one on each antenna. That is, _u1 x(t) is sent over antenna 1, and _u2 x(t) is sent over antenna 2, with u=[_u1 ,_u2^]T called the transmitting weight vector . Then, the two signals are weighted by the receiver with a receiving weight vector v=[_v1 ,_v2^]T and summed to produce y(t) . Let H denote the matrix of channel coefficients between the transmitter and the receiver. The above can thus be written as y(t)=(^uT Hv)x(t) , and the complex gain experienced by x(t) is then a consequence of transmit beamforming, the channel, and receive beamforming of ^uT Hv . Now with appropriate weight vectors u and v , the received signal y(t) can achieve a unit gain (^uT Hv=1 ) if it is received at the desired receiver or a zero gain (^uT Hv=0 ) 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 u if v 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 v is the desired receiver of x(t) and v is fixed, then we could require u to satisfy ^uT Hv=1 so that x(t) can be received with unit gain.

(2 ): If the receiver corresponding to v is already involved in another link, then v is fixed and we could require u to satisfy ^uT Hv=0 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 u , and the receiver corresponding to v wants to receive signals from different transmitter without interference, then we could require v to satisfy ^uT Hv=0 so as to null the contribution of u at the receiver.

Figure 1: Multiantenna wireless channel.

[figure omitted; refer to PDF]

2.3. Transmission Constraints on MIMO Links

Consider the multihop wireless network G=(V,E,F) shown in Figure 2, where V={1,2,3,4} , E={(2,1),(3,2),(4,3)} , and F={_f1 =(2,1)...,_f2 =(4,3)...} . Assume that (1 ) every link has the same _RT and _RI =1.5 _RT , (2 ) the numbers of antennas are _K1 =_K2 =1 and _K3 =_K4 =2 , and (3 ) _f1 and _f2 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., _f1 is active). Let _u2 be the (1 × 1) transmitting weight vector that node 2 is currently using to weight its transmitted signal and let _v1 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 _f1 is currently active, if node 3 wants to receive an interference-free signal from node 4, it must design its receiving weight vector _v3 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 (^u4T_H4,3v3 )=1 and (^u2T_H2,3v3 )=0 , where _u4 =[_u4,1 ,_u4,2^]T is the transmitting weight vector of node 4, and _v3 =[_v3,1 ,_v3,2^]T is the receiving weight vector of node 3. Now, given _u4 , _u2 , _H4,3 and _H2,3 , the system of these two equations would have a unique solution ^v3* because the elements of each of _H4,3 , and _H2,3 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, _f1 and _f2 are always possible to be active simultaneously in this example.

Figure 2: Node topology graph.

[figure omitted; refer to PDF]

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., _f2 is active). With similar considerations for the above, this example can be represented by the equations of (^u2T_H2,1v1 )=1 and (^u2T_H2,3v3 )=0 , but now the objective to be solved becomes _u2 , which is (1 × 1) weight vector. That is, the single variable _u2 involves the system of the two equations associated with _H2,1 and _H2,3 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 (_f1 ,_f2 ) is order dependent. That is, if _f1 is admitted first, then _f2 is possibly admitted. On the contrary, if _f2 is admitted first, then _f1 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 m be the transmitter and node n the receiver, and suppose that there are β streams currently received by nodes located within m 's interference range, and γ streams currently transmitted by nodes located within n 's interference range, where a steam denotes a copy of data signal transmitted by the MIMO system. Suppose further that m wants to transmit an α -stream flow f to n . Then, for interference-free communications in the system, we have the following constraints.

Theorem 1 (transmit DOF constraint).

m can transmit an α -stream flow f to n without interfering with the β streams concurrently received by m 's neighbors if [figure omitted; refer to PDF]

Proof.

Let {_m1 ,_m2 ,...,_mp } denote the set of m 's neighbors that are receiving the β streams and _βi denote the number of streams that node _mi is currently receiving, for all i∈{1,2,...,p} (i.e., ^∑i=1p_βi =β ). Suppose that for each i , m knows the receiving weight vector of _mi , and the channel matrix between it and _mi , for all i . Then, m can transmit its α -stream flow f to n with the weight vectors _um,j , j∈{1,2,...,α} subject to the conditions of _Amum,j =_aj ,∀j , where _aj is the column vector of length α+β defined as [0 0 ...0 1 0 0...0^]T with 1 at the j th position, and _Am is the (α+β)×_Km matrix defined as [_{A...m,n A...m,1 A...m,2} ..._A...m,p^]T with _A...m,n =[_{Hm,nvn,1Hm,nvn,2} ..._Hm,nvn,α ] and _A...m,i =[_{Hm,mivmi ,1Hm,mivmi ,2} ..._{Hm,mivmi ,βi} ] , for all i∈{1,2,...,p} . Because the elements of each H involved would be i.i.d in general, the system of equations _Amum,j =_aj , for all j, with _Am of the size of (α+β)×_Km , would have no solution if (α+β)>_Km .

Theorem 2 (receive DOF constraint).

n can receive an α -stream flow f from m without interfering with the γ streams concurrently transmitted by n 's neighbors if [figure omitted; refer to PDF]

Proof.

Let {_n1 ,_n2 ,...,_nq } denote the set of n 's neighbors that are transmitting the γ streams and _γi denote the number of streams that node _ni is currently transmitting, for all i∈{1,2,...,q} (i.e., ^∑i=1q_γi =γ ). Suppose that for each i∈{1,2,...,q} , n knows the transmitting weight vector of _ni , and the channel matrix between it and _ni , for all i . Then, n can receive its α -stream flow f from m with the weight vectors _vn,j , j∈{1,2,...,α} subject to the conditions of _Bnvn,j =_bj ,∀j , where _bj is the column vector of length α+γ defined as [0 0 ...0 1 0 0...0^]T with 1 at the j th position, and _Bn is the (α+γ)×_Kn matrix defined as [_{B...m,nB...1,nB...2,n} ..._B...q,n^]T with _B...m,n =[^Hm,nT_um,1^Hm,nT_um,2 ...^Hm,nT_um,α ] and _B...i,n =[^{H_ni ,nT}_{uni ,1}^{H_ni ,nT}_{uni ,2} ...^{H_ni ,nT}_{uni ,γi} ] , for all i∈{1,2,...,q} . Because the elements of each H involved would be i.i.d in general, the system of equations _Bnvn,j =_bj , for all j, with _Bn of the size of (α+γ)×_Kn would have no solution if (α+γ)>_Kn .

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 _fi =(_ui ,_vi )... and _fj =(_uj ,_vj )... are said to strongly contend with each other if and only if _uj =_vi or _ui =_vj . Given that, we define _Gstrong (_Vstrong ,_Estrong ) as the strong contention graph , where a vertex in _Vstrong corresponds to a flow in F , and a bidirectional edge in _Estrong denotes the corresponding flows in F strongly contend with each other in the node topology graph G .

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 _Gweak (_Vweak ,_Eweak ) as the weak contention graph . In this graph, a directional edge between a pair of vertices corresponding to _fi =(_ui ,_vi )... and _fj =(_uj ,_vj )... in G arises if any one of the three weak-interference conditions holds: (1 ) _ui =_uj , (2 ) _vi =_vj , and (3 ) there exists a _fk =(_uk ,_vk ) (possibely k=i or k=j ) such that ||_vk -_ui ||≤_RI and/ or ||_vk -_uj ||≤_RI . To be specific, we consider a MIMO network of 8 nodes and 8 flows as an example, showing its node topology graph G in Figure 3(a) and the derived _Gstrong and _Gweak 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 _f3 ), node 2 cannot simultaneously transmit to node 1 (with _f1 ), and vice versa. This is a strong interference, and is denoted by a bidirectional edge between _f1 and _f3 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, _f7 and _f8 will contend with each other. This corresponds to the first weak-interference condition, and is shown by a bidirectional edge between _f7 and _f8 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 _f1 and _f2 interfere with each other. Therefore, there is a bidirectional edge between _f1 and _f2 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 _f3 ), this node can interfere with node 1's receipt of _f2 from node 3. This interference is shown by a directional edge from _f3 to _f2 in Figure 3(c). Besides, the other strong and weak interferences not exemplified in the above can be also observed easily.

An example of weak and strong contentions: (a) the node topology graph G , (b) the corresponding strong contention graph _Gstrong , and (c) the corresponding weak contention graph _Gweak .

(a) [figure omitted; refer to PDF]

(b) [figure omitted; refer to PDF]

(c) [figure omitted; refer to PDF]

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 {_Co } , that contain only weak contentions and can be represented by {_Coweak } . This step is done by finding a valid coloring for _Gstrong with, for example, the greedy algorithm given in [11] that sorts vertices in _Gstrong by decreasing vertex degrees, and according to the order, colors them one by one using a first-fit greedy approach. Then, the flows of G with the same color in _Gstrong compose a _Co , and the corresponding subset of _Gweak composes a _Coweak .

3.1. Transmission Modes

After obtaining {_Co } and {_Coweak } , 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 G that can be active simultaneously. A _tΓ ×_mΓ matrix Γ is used to represent the set of transmission modes, and called scheduling matrix , in which _tΓ denotes the number of transmission modes, and _mΓ denotes the number of flows in G . In the matrix, a row represents a transmission mode _TM , and its element _{ΓTM ,fi} represents the number of traffic streams utilized by flow _fi in this mode. That is, a _TM is a vector denoting a possible set of transmissions from all _mΓ 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 _TM s for constructing a desired Γ . Next, with these modes representing the time slots to be used, they are expected to determine the time fraction _ptm 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 _ptm for every _TM is given, the frame length is then the smallest positive integer I such that _ptm ·I is an integer for every transmission mode, and the number of active times for a _TM is simply its _ptm ·I . Now, given the two aims of the scheduling algorithms, we proceed to develop the transmission mode generating algorithms for _TM s in the next subsection, and leave the methods for determining _ptm 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 {_Km } , the set of destination DOFs {_Kn } , and the set of weak contention graphs {_Coweak } , for the flow components {_Co } obtained previously. For each _Co , the algorithm generates all possible transmission modes _TM s, according to the component's _Km and _Kn . 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, _AO 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 _AO to confirm its validity. For either of the versions, the algorithm requires Step 1 to update α , β , and γ with [figure omitted; refer to PDF] where _fi is the flow in _Go now considered for the proceeding _AO and _TM , and ^NSI (_fi ) is the set of neighbors, in _Go , located within _RI of _fi 's source node, and ^NRI (_fi ) is that for _fi 's destination node.

Algorithm 1: Transmission mode generating Algorithm 1 (TMGA1)

(1 ) INPUT: {_Co } , {_Km } , {_Kn } , {_Coweak } ;

(2 ) for all _Co do

(3 ) Generate all transmission modes, _TM s, for _Co

(4 ) for all _TM do

(5 ) Generate all admission orders, _AO s, for _TM ;

(6 ) for all _AO do

(7) Initialize {α} = ∅ , {β} = ∅ , {γ} = ∅ ;

(8 ) for each _fi sorted with the increasing order of _AO do

(9 ) { Step 1 : update α , β and γ }

(10 ) α(_fi )=_TM (_fi ) ; { Update α}

(11 ) β(_fi )=_{∑∀fj ∈^NSI (fi )} α(_fj ) ; { Update β}

(12 ) γ(_fi )=_{∑∀fj ∈^NRI (fi )} α(_fj ) ; { Update γ}

(13 ) { Step 2 : verify for the Trasmit/Receive DOF constraints}

(14 ) Success(_fi )=1 ;

(15 ) if α(_fi )+β(_fi )>_Km (_fi ) or α(_fi )+γ(_fi )>_Kn (_fi ) then

(16 ) Success(_fi )=0 ;

(17 ) end if

(18 ) end for

(19 ) if Success (_fi ) = 1, ∀i then

(20 ) Success(_AO ) = 1;

(21) end if

(22) end for

(23) if ((Conservative == 1 and Success (_AO ) = 1, ∀ _AO ) or

(Conservative == 0 and Success (_AO ) = 1, ∃ _AO )) then

(24) _Γo =_Γo...TM ;

(25) end if

(26) end for

(27) Reduce _Γo to be that in which [there does not exist]_T...M ,_TM s.t. _T...M (i)≤_TM (i),∀i

(28) end for ;

(29) { Step 3 : merge and output the scheduling matrix}

(30) Merge _Γo s to form a single Γ={_Γ1 ,...,_Γp } , where p=|{_Co }| ;

(31) OUTPUT: Γ=Γ_...TM of ∅ ;

Following that, in Step 2 , these updated values are used to verify whether the α(_fi ) -stream traffic can be established on _fi without interfering with the other flows according to the DOF constrains given in (1) and (2). If all _fi 's in the _AO are verified successfully, the corresponding _TM could then be conservatively or nonconservatively considered to be an element of _Γo (Γ for _Co ). In addition, to reduce the size of _Γo , the _TM 's with their capabilities being subset of the others will not be included. Then, all the reduced _Γo 's are merged to form a single scheduling matrix Γ so that its size (_tΓ ) can be tractable for the cross-layer design. Finally, after added with an empty _TM as the default element for scheduling, the complete Γ is given in Step 3 .

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 _Co ={_f1 ,_f2 } . As already shown, this example has _K1 =_K2 =1 and _K3 =_K4 =2 . However, they are represented here by {_Km }={1,2} and {_Kn }={1,2} to be the inputs of TMGA1 in addition to _Coweak =(_Vweak ,_Eweak ) , where _Vweak ={_f1 ,_f2 } and _Eweak ={_f1f2 ...} . With these inputs, the algorithm generates a set of all possible transmission modes {_TM }={(0,0),(0,1),(0,2),(1,0),(1,1),(1,2)} . Among these, we consider the mode of (1,1) with its two possible admission orders, {_AO }={(_f1 ,_f2 ),(_f2 ,_f1 )} , as before. For the first order, TMGA1 initializes {α}=∅ , {β}=∅ , and {γ}=∅ . Then it updates for _f1 with α(_f1 )=_TM (_f1 )=1 , β(_f1 )=_{∑∀fj ∈^NSI (f1 )} α(_fj )=α(_f2 )=0 , and γ(_f1 )=_{∑∀fj ∈^NRI (f1 )} α(_fj )=0 (since [there does not exist]_fj ∈^NRI (_f1 ) ), and the updated values satisfy the DOF constrains by α(_f1 )+β(_f1 ) (=1)≤_Km (_f1 ) (=1) , and α(_f1 )+γ(_f1 ) (=1)≤_Kn (_f1 ) (=1) . After that, it updates for _f2 with α(_f2 )=_TM (_f2 )=1 , β(_f2 )=_{∑∀fj ∈^NSI (f2 )} α(_fj )=0 (since [there does not exist]_fj ∈^NSI (_f2 ) ), and γ(_f2 )=_{∑∀fj ∈^NRI (f2 )} α(_fj )=α(_f1 )=1 , and these also satisfy the DOF constrains by α(_f2 )+β(_f2 ) (=1)≤_Km (_f2 ) (=2) and α(_f2 )+γ(_f2 ) (=2)≤_Kn (_f2 ) (=2) . Thus, the first order (_f1 ,_f2 ) is valid.

Similarly, after the initialization, the update for the second order will start with _f2 , resulting in α(_f2 )=_TM (_f2 )=1 and β(_f2 )=0 , as before; but now α(_f1 )=0 and thus γ(_f2 )=α(_f1 )=0 . Nevertheless, the above still satisfies the DOF constrains. When then updating for _f1 , it results in α(_f1 )=_TM (_f1 )=1 in addition to α(_f2 )=1 updated previously. Thus β(_f1 )=α(_f2 )=1 instead of 0, while γ(_f1 )=0 without change. Consequently, it can only satisfy the receive DOF constrain by α(_f1 )+γ(_f1 ) (=1)≤_Kn (_f1 ) (=1) , but fails on the transmit DOF constraint since α(_f1 )+β(_f1 ) (=2)[neither < nor =]_Km (_f1 ) (=1) . Finally, with the two _AO s' results, if the nonconservative version (TMGA1-non) is adopted, the transmission mode _TM =(1,1) is accepted; otherwise, if the conservative version (TMGA1-con) is adopted, the mode is rejected.

For the time complexity of TMGA1, we recall f=(u,v)... and denote by ξ(f)=_δin (u)+_δout (v) the number of flows that f has a strong contention with, where _δin (v) and _δout (v) refer to in and out degrees of the node v , respectively. With that, we can let ξ=_{max f} ξ(f) and denote it by ξ=Δ(_Gstrong ) . Then, the number of _Co in the network would be p≤Δ(_Gstrong )+1=ξ+1 if the coloring algorithm in [11] is adopted. Now consider that the j th _Co ={_fi } has the number of transmission modes _nj ∈O(^Πi=1i=_sj |_fi |) , where _sj ∈O(m/ξ) (with m denoting the total number of flows in G ) is the size of this _Co , and |_fi | is the DOF of its element flow _fi . In the _Co , each transmission mode has _oj admission orders, which is the total number of permutations for the _sj elements (flows). With the above, we can show the time complexity of TMGA1 as O(^∑j=1j=p_nj ·_oj ) .

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 _TM 's for each _Co . However, the number of _TM s will grow exponentially with the increase of the size of _Co , 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 _TM 's for each _Co . The central idea of TMGA2 is to consider a _fi ∈_Co as the first flow to be admitted for a S -stream flow, and then randomly choose other _fj 's ∈_Co to see if they could cooperatively construct a valid _TM . Note that the starting _fi is chosen with an increasing order and the following _fj s could be the same of _fi , implying that multiple ...AE; -streams could be established in a single _fi . Furthermore, the seeking process could be repeated several times according to the iteration limit [Lagrangian (script capital L)] . With that, we can control its time complexity to be satisfactory enough while obtaining a good _Γo that can cover all flows in _Co and can evenly distribute the number of times that each flow is included in certain _TM s.

Algorithm 2: Transmission mode generating Algorithm 2 (TMGA2)

(1 ) INPUT: {_Co } , {_Km } , {_Kn } , {_Coweak } , [Lagrangian (script capital L)] , ...AE; ;

(2 ) for all _Co do

(3 ) Initialize {V}=∅ ;

(4 ) for l=1 to l=[Lagrangian (script capital L)] do

(5 ) Initialize {W}=min {{_Km },{_Kn }} , {α} = ∅ , {β} = ∅ , {γ} = ∅ ;

(6 ) for i=1 to i=|_Co | do

(7 ) Initialize {α} = ∅ , {β} = ∅ , {γ} = ∅ , {_TM }=∅ , k = TRUE;

(8 ) α(_fi ) +=...AE; , V(_fi )=random ; W(_fi ) -=...AE; ;

(9 ) while k == TRUE do

(10 ) if W(_fi )≥0 then

(11 ) { Primary update:}

(12 ) W(_fj ) -=...AE;,∀_fj ∈^NSI (_fi )_...^NRI (_fi ) ; { Update W}

(13 ) β(_fi )=_{∑∀fj ∈^NSI (fi )} α(_fj ) ; { Update β #1}

(14 ) γ(_fi )=_{∑∀fj ∈^NRI (fi )} α(_fj ) ; { Update γ #1}

(15 ) { Optional update:}

(16 ) β(_fj ) +=α(_fi ),∀_fj ∈^NRI (_fi ) with α(_fj )>0 ; { Update β #2}

(17 ) γ(_fj ) +=α(_fi ),∀_fj ∈^NSI (_fi ) with α(_fj )>0 ; { Update γ #2}

(18 ) end if

(19 ) Success(_fi )=1 ;

(20 ) { Primary verification:}

(21) if α(_fi )+β(_fi )>_Km (_fi ) or α(_fi )+γ(_fi )>_Kn (_fi ) then

(22) Success (_fi )=0 ;

(23) end if

(24) { Optional verification:}

(25) for all _fj ∈^NSI (_fi )_...^NRI (_fi ) with α(_fj )>0 do

(26) if α(_fj )+β(_fj )>_Km (_fj ) or α(_fj )+γ(_fj )>_Kn (_fj ) then

(27) Success(_fi )=0 ;

(28) end if

(29) end for

(30) if Success (_fi )=0 then

(31) Roll back V , W , α , β , γ , and stamp _fi as failed; { Roll back if _fi is not valid}

(32) end if

(33) Find the next _fi with V(_fi )=min {V} and W(_fi )≥...AE; , among ∀_fi not yet examined and not yet failed;

(34) if no _fi can be found then

(35) k = FALSE;

(36) else

(37) α(_fi ) += ...AE; , V(_fi )=random , W(_fi ) -=...AE; ;

(38) end if

(39) end while

(40) _TM (_fi )=α(_fi ),∀i ;

(41) if [there does not exist]_T...M ∈_Γo ==_TM then

(42) _{Γo ...} ... = _TM ;

(43) end if

(44) end for

(45) end for

(46) Reduce _Γo to be that in which [there does not exist]_T...M ,_TM s.t. _T...M (i)≤_TM (i),∀i ;

(47) end for

(48) Merge _Γo s to form a single Γ={_Γ1 ,...,_Γp } , where p is the number of _Γo found;

(49) OUTPUT: Γ=Γ_...TM of ∅ ;

To fulfill the design aim, we add {V} and {W} in this algorithm in addition to {α} , {β} , and {γ} given previously. More precisely, {V} is the set of values associated with _fi s' chosen probabilities. In the current version, the values are given with uniform random numbers, and TMGA2 chooses the next _fi with the lowest value; that is, it will choose uniformly and randomly among the _fi 's. On the other hand, {W} denotes the set of link capabilities for the flows and is obtained by {W}=min {{_Km },{_Kn }} . In addition, two new update rules are considered for β and γ , respectively, as [figure omitted; refer to PDF] In what mentioned previously, _fi is the flow now considered in _Co . Clearly, each neighbor of _fi 's destination node would consume α(_fi ) DOFs to null its interference at the receiver if it has data to transmit right after _fi . Thus, conservatively it should take _fi 's α into account as a part of its own β and then check the transmit DOF constraint to avoid the interference. Symmetrically, each neighbor of _fi 's source node will be interfered with _fi 's transmission if it wants to concurrently receive its own traffic right after _fi . Hence, by taking _fi '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 ...AE;=1 so that the algorithm will consider 1-stream flow for each admission. With the initial {α}={0,0} and {W}={1,2} , TMGA2 starts by assuming _f1 to be admitted and accordingly updating the related parameters to be {α}={1,0} and {W}={0,2} . In the same time, the neighbor of _f1 , that is, _f2 , should also consume its link capability (DOF) to be interference-free from _f1 's transmission. Thus, {W} is further changed to be {0,1} . In what follows, it updates _f1 's α and β with the equations in (3) as TMGA1 does. If TMGA2-non is considered, the algorithm will proceed to examine the next _fi that has the lowest random value V and has its link capability W equal to or larger than ...AE; (= 1). Now _f2 is the only candidate, and the following process for updating α and β and verifying the DOF constraints is the same as that for TMGA1. Finally, {α}={1,1} found is used to update _TM as (1,1), which is the result of this case. Then, with _f2 as the new start, the process continues to search other valid _TM , and will end after the searching. In fact, the algorithm is designed to repeat the whole process [Lagrangian (script capital L)] times, and with the random nature of V , each of the iterations may lead to a different _TM complying with our design aim.

Now, let us turn out to focus on the conservative version of TMGA2. As shown in the TMGA1 example, _TM =(1,1) is accepted by TMGA1-non but is rejected by TMGA1-con, because the latter considers both _AO s of (_f1 ,_f2 ) and (_f2 ,_f1 ) , 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 _f1 . After checking α and β for _f1 , TMGA2-con must also make the optional checks for _f1 's neighbors. In this case, no _fi is the neighbor of _f1 's destination node, and thus no update for its β is needed. On the other hand, _f2 is the neighbor of _f1 's source node. However, _f2 currently has no established traffic and thus has no need to change its γ . With the unchanged values, the optional verification for _f2 is easily passed, in addition to the primary verification for _f1 . Consequently, TMGA2-con may go to check the next, that is, _f2 , as TMGA2-non would do.

As expected, TMGA2-con first makes the primary update for _f2 , which keeps β(_f2 )=0 and changes γ(_f2 ) to be 1, then it makes the optional update and finds that _f1 is the neighbor of _f2 's destination node and has 1-stream traffic established before. Thus, it changes β(_f1 ) to be 1. Meanwhile, it finds no neighbor of _f2 's source node, and thus it changes nothing. However, since the optional update changes at least one value (β(_f1 ) ), its optional verification may produce nontrivial results. In fact, it has α(_f1 )+β(_f1 ) (=2) [neither < nor =]_Km (_f1 ) (=2) , indicating that _TM =(1,1) is not valid. Clearly, this example shows that while _AO =(_f1 ,_f2 ) is examined by the primary update and verification, _AO =(_f2 ,_f1 ) 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 _Co is O(^{[Lagrangian (script capital L)]2} ·e+[Lagrangian (script capital L)]·^e3 ) , where e denotes the number of edges (flows) in the _Co , that is, e=|_ECo | . Then, considering p≤ξ+1 graph components (_Co s), and denoting by e... the maximal e in the network, that is, e...=_{max e} {e=|_ECo |} , we can have the polynomial time complexity for TMGA2 as O(p·^{[Lagrangian (script capital L)]2} ·e...+p·[Lagrangian (script capital L)]·^e...3 ) .

4. Cross-Layer Schemes

Now, given a network G with MIMO links, the source and destination nodes of K end-to-end communication sessions, and the scheduling matrix Γ obtained previously, in this section we aim to find a rate allocation r specifying the rate _rk for each session k , along with a flow allocation vector ^fk specifying the amount of traffic ^fek of session k routed through link e , and a transmission schedule vector p specifying time fraction _ptm for each transmission mode _TM . 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 r=[_r1 ,_r2 ,...,_rK ] , along with a feasible flow allocation vector and a feasible transmission schedule vector such that the throughput ^∑k=1K_rk is maximized.

Definition 2.

The Proportional fair Rate Allocation (PRA) problem seeks a feasible rate allocation vector r , along with a feasible flow allocation vector and a feasible transmission schedule vector such that the utility function ^∑k=1K log (_rk ) is maximized.

Definition 3.

The Weighted fair Rate Allocation (WRA) problem seeks a feasible rate allocation vector r, along with a feasible flow allocation vector and a feasible transmission schedule vector suchthat _ri /_ψi =_rj /_ψj ,1≤i≠j≤K, where _ψi denotes the positive weight of session i, with the assumption of 1=_ψ1 >_ψ2 ,...,>_ψK >0, and the throughput ^∑k=1K_rk is 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) G , node topology graph of the MIMO network.

(ii) SS , set of session source nodes, where _sk is the source node of session k .

(iii): SD , set of session destination nodes, where _dk is the destination node of session k .

(iv) Γ , scheduling matrix.

Variables

(i) r , rate allocation vector, where _rk is the rate allocated for session k , ∀k .

(ii) ^fk , flow allocation vector for session k , where ^fek is the session k 's traffic routed through link e .

(iii) p , transmission schedule vector, where _ptm is the time fraction for the transmission mode _TM .

Optimize

(i) Maximize the total throughput of sessions [figure omitted; refer to PDF]

Constraint

(i) Flow conservation for source nodes [figure omitted; refer to PDF] where ^{E_sk out} (^{E_sk in} ) denotes the set of outgoing (incoming) edges of source node _sk .

(ii) Flow conservation for intermediate nodes [figure omitted; refer to PDF] where ^Evout (^Evin ) denotes the set of outgoing (incoming) edges of node v∈V\{_sk ,_dk } .

(iii) Bandwidth conservation [figure omitted; refer to PDF] where _cfi is the link capacity or rate of _{ΓTM ,fi} .

(iv) Scheduling constraint [figure omitted; refer to PDF]

(v) Flow rate validity: [figure omitted; refer to PDF]

(vi) Scheduling validity [figure omitted; refer to PDF]

(vii) Session rate validity [figure omitted; refer to PDF]

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 ^fek imply that a session k can be routed through different links, e 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 [figure omitted; refer to PDF] subject to the constraints (6)-(12), and [figure omitted; refer to PDF] 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 [figure omitted; refer to PDF] 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, _rk , and the system throughput, ^∑k=1K_rk , 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, N={1,2,3,4} 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, _f1 =(2,1)... , _f2 =(3,2)... , and _f3 =(4,3)... are so conducted to compose the flow set F , 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 (_s1 = 2, _d1 = 1), (_s2 = 3, _d2 = 1), and (_s3 =4 , _d3 = 1) (where (_sk ,_dk ) denotes the source-destination pair of session k ). Given the above, it is easy to derive _Gstrong showing that _f1 and _f2 strongly contend with each other, and so do _f2 and _f3 . Accordingly, with the coloring algorithm, they are divided into two flow components, _C1 ={_f1 ,_f3 } and _C2 ={_f2 } , containing only weak contentions. For these components, TMGA1 and TMGA2 both can easily produce _Γ1 ={{0,2},{1,1},{2,0}} and _Γ2 ={{2}} . After padding its _TM 's with zeros for the flows not in the component, respectively, the two _Γo 's are merged to be the complete scheduling matrix Γ={{0,0,0},{0,0,2},{1,0,1},{2,0,0},{0,2,0}} , wherein an empty _TM ={0,0,0} is added as the default element for scheduling.

Now, with a DOF to represent a unit of transmission capability, LP1 produces {^fek }={^f11 =2,^f21 =0,^f31 =0,^f12 =0,^f22 =0,^f32 =0,^f13 =0,^f23 =0,^f33 =0} . That is, only by routing session 1 through {_f1 } and sacrificing all other sessions (with _r2 =0 and _r3 =0 ), the system can have the maximum system throughput 2. In addition, it produces {_ptm }={0,0,0,1,0} , saying that only _TM ={2,0,0} 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 LP2 we can achieve the weighted fairness among the sessions while maximizing the aggregated system throughput. More precisely, LP2 produces, for example, {r}={_r1 =0.7692,_r2 =0.3846,_r3 =0.1538} , exactly complying with the given weights {ψ}={_ψ1 =1,_ψ2 =0.5,_ψ3 =0.2} . The corresponding routes are constituted by {^fek }={^f11 =0.7692,^f21 =0,^f31 =0,^f12 =0.3846,^f22 =0.3846,^f32 =0,^f13 =0.1538,^f23 =0.1538,^f33 =0.1538} . For the requirements on link capability, a TDMA-based MAC over the MIMO PHY is scheduled with Γ and {_ptm }={0,0.01,0.1338,0.5869,0.2692} . Accordingly, the link capabilities {_ptm}1×5 ·_Γ5×3 ={1.3076,0.5384,0.1538} can fulfill the requirement of _f1 (0.7692 + 0.3846 + 0.1538 = 1.3076), that of _f2 (0 + 0.3846 + 0.1538 = 0.5384), and that of _f3 (0 + 0 + 0.1538 = 0.1538). Finally, for solving the PRA problem, CP1 produces {r}={_r1 =0.6...,_r2 =0.3...,_r3 =0.2...} 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 (_s1 =6 , _d1 =1 ), (_s2 =7 , _d2 =1 ), and (_s3 =8 , _d3 =1 ) are conducted for the leaf nodes (6, 7, and 8). Given that, LP1 produces {r}={_r1 =0.3781,_r2 =0.3781,_r3 =0.5771} . 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 _f5 [arrow right]_f3 [arrow right]_f1 and that for the second is _f6 [arrow right]_f4 [arrow right]_f2 , in which every single flow contributes the data rate of 0.3781 to its session. On the other hand, LP1 finds two routes for the third session: _f7 [arrow right]_f3 [arrow right]_f1 and _f8 [arrow right]_f4 [arrow right]_f2 . In what mentioned above, each flow provides its rate of 0.2885. Then, by combining the two routes, it can support _r3 =0.5771 . Similarly, by setting _ψi =1,∀i , LP2 can give each session i the same rate allocation _ri =0.4... , 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 n nodes located in a 1000 × 1000 m² region. The transmission range (_RT ) and the corresponding interference range (_RI ) 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 _sj in a _Co is 18, and clearly, the number of permutations for the _sj =18 elements (flows), that is, its _oj , is generally an intractable value for computation.

Figure 4: Random topology for the experiment.

[figure omitted; refer to PDF]

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 [Lagrangian (script capital L)]=1 and [Lagrangian (script capital L)]=10 , respectively. The corresponding rate allocation results are shown in Figure 5. As expected, the MRA scheme can give certain sessions the highest _ri '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 _ψi =1,∀i , the rate allocated to each session i 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.

Rate allocation results for the experimented sessions: (a) [Lagrangian (script capital L)] = 1, and (b) [Lagrangian (script capital L)] = 10.

(a) [figure omitted; refer to PDF]

(b) [figure omitted; refer to PDF]

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 (_TM 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, [Lagrangian (script capital L)]=1 , [Lagrangian (script capital L)]=2 , and [Lagrangian (script capital L)]=10 , are examined for TMGA2. In addition, to quantitatively analyze the fairness performances for these schemes, we let _Si denote the throughput of session i , and let _ψi denote the associated weight, and we use these parameters to obtain the fairness index in [20] as follow: [figure omitted; refer to PDF]

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 [Lagrangian (script capital L)] . That is to say, although a larger [Lagrangian (script capital L)] may lead to a larger number of _TM '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, [Lagrangian (script capital L)] 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 [Lagrangian (script capital L)]=1 or 2 would be enough for most of the schemes. Even so, one may still expect a nonconservative Γ for higher throughputs, despite [Lagrangian (script capital L)] . 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 (_AO 's) recorded to realize the _TM 's in a given nonconservative Γ . On the other hand, with a conservative Γ , every possible _AO would be already considered for a _TM , and thus no such overheads would be involved.

Throughput and fairness results for the experimented sessions: (a) throughput and (b) fairness.

(a) [figure omitted; refer to PDF]

(b) [figure omitted; refer to PDF]

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 _ψi =1,∀i , and its fairness index values are all of 1 in spite of [Lagrangian (script capital L)] . 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 [Lagrangian (script capital L)] 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 [Lagrangian (script capital L)] depending on the performance metric most concerned. Nevertheless, in general, [Lagrangian (script capital L)]=1 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 [Lagrangian (script capital L)]=10 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.

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.

(a) [figure omitted; refer to PDF]

(b) [figure omitted; refer to PDF]

(c) [figure omitted; refer to PDF]

(d) [figure omitted; refer to PDF]

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.

References

[1] S. K. Jayaweera, H. V. Poor, "Capacity of multiple-antenna systems with both receiver and transmitter channel state information," IEEE Transactions on Information Theory , vol. 49, no. 10, pp. 2697-2709, 2003., [email protected]; [email protected]

[2] R. S. Blum, "MIMO capacity with interference," IEEE Journal on Selected Areas in Communications , vol. 21, no. 5, pp. 793-801, 2003., [email protected]

[3] R. Narasimhan, "Spatial multiplexing with transmit antenna and constellation selection for correlated MIMO fading channels," IEEE Transactions on Signal Processing , vol. 51, no. 11, pp. 2829-2838, 2003.

[4] M. Hu, J. Zhang, "MIMO ad hoc networks: medium access control, saturation throughput, and optimal hop distance," Journal of Communications and Networks , vol. 6, no. 4, pp. 317-330, 2004.

[5] K. Sundaresan, R. Sivakumar, M. A. Ingram, T.-Y. Chang, "Medium access control in ad hoc networks with MIMO links: optimization considerations and algorithms," IEEE Transactions on Mobile Computing , vol. 3, no. 4, pp. 350-365, 2004.

[6] L. Chen, S. H. Low, J. C. Doyle, "Joint congestion control and media access control design for ad hoc wireless networks," in Proceedings of the 24th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM '05), vol. 3, pp. 2212-2222, Miami, Fla, USA, March 2005.

[7] X. Wang, K. Kar, "Cross-layer rate control for end-to-end proportional fairness in wireless networks with random access," in Proceedings of the 6th International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc '05), pp. 157-168, Urbana-Champaign, Ill, USA, May 2005.

[8] J. Tang, G. Xue, C. Chandler, W. Zhang, "Link scheduling with power control for throughput enhancement in multihop wireless networks," IEEE Transactions on Vehicular Technology , vol. 55, no. 3, pp. 733-742, 2006., [email protected]; [email protected]; [email protected]; [email protected]

[9] R. Bhatia, L. Li, "Throughput optimization of wireless mesh networks with MIMO links," in Proceedings of the 26th IEEE International Conference on Computer Communications (INFOCOM '07), pp. 2326-2330, Anchorage, Alaska, USA, May 2007.

[10] B. Mumey, J. Tang, T. Hahn, "Joint stream control and scheduling in multihop wireless networks with MIMO links," in Proceedings of IEEE International Conference on Communications (ICC '08), pp. 2921-2925, Beijing, China, May 2008.

[11] S. Ramanathan, "Unified framework and algorithm for channel assignment in wireless networks," Wireless Networks , vol. 5, no. 2, pp. 81-94, 1999.

[12] K. Jain, J. Padhye, V. N. Padmanabhan, L. Qiu, "Impact of interference on multi-hop wireless network performance," in Proceedings of the 9th Annual International Conference on Mobile Computing and Networking (MOBICOM '03), pp. 66-80, San Diego, Calif, USA, [email protected]; [email protected]; [email protected]; [email protected], September 2003.

[13] M. Kodialam, T. Nandagopal, "Characterizing achievable rates in multi-hop wireless networks: the joint routing and scheduling problem," in Proceedings of the 9th Annual International Conference on Mobile Computing and Networking (MOBICOM '03), pp. 42-54, San Diego, Calif, USA, September 2003.

[14] M. S. Bazaraa, J. J. Jarvis, H. D. Sherali Linear Programming and Networks Flows , John Wiley & Sons, New York, NY, USA, 2005., 3rd.

[15] S. Boyd, L. Vandenberghe Convex Optimization , Cambridge University Press, Cambridge, UK, 2004.

[16] M. Grant, S. Boyd, Y. Ye, "CVX: Matlab Software for Disciplined Convex Programming," 2008

[17] V. Gambiroza, B. Sadeghi, E. W. Knightly, "End-to-end performance and fairness in multihop wireless backhaul networks," in Proceedings of the 10th Annual International Conference on Mobile Computing and Networking (MOBICOM '04), pp. 287-301, Philadelphia, Pa, USA, [email protected]; [email protected]; [email protected], September 2004.

[18] J. Lee, W. Liao, M. C. Chen, "An incentive-based fairness mechanism for multi-hop wireless backhaul networks with selfish nodes," IEEE Transactions on Wireless Communications , vol. 7, no. 2, pp. 697-704, 2008., [email protected]; [email protected]; [email protected]

[19] D. S. Johnson, M. Yannakakis, C. H. Papadimitriou, "On generating all maximal independent sets," Information Processing Letters , vol. 27, no. 3, pp. 119-123, 1988.

[20] D. Qiao, K. G. Shin, "Achieving efficient channel utilization and weighted fairness for data communications in IEEE 802.11 WLAN under the DCF," in Proceedings of the 10th International Workshop on Quality of Service (IWQoS '02), pp. 227-236, 2002.