INTRODUCTION
As a promising approach for next generation wireless networks, multihop technology
has been attracting much interest. The fundamental principal is that multihop
relay nodes are exploited to relay information from source station to another
in a distributed manner until the message is received by the receiver. Multihop
relay can increase system throughput, improve fairness performance and enhance
network coverage (Le and Hossain, 2007).
In last few years, multiple antenna techniques have been studied and applied
to multihop networks. In these networks, multihop relay nodes can function as
a virtual antenna array. The resulting MultipleInput MultipleOutput (MIMO)
spatial diversity gain can be used to reduce power consumption and increase
capacity. There is already an extensive literature on MIMO multihop systems
(Bölcskei et al., 2006; Dohler
et al., 2006; Roh and Paulraj, 2002). In
particular, a detailed analysis of multiantenna multihop communication schemes
is presented by Pabst et al. (2004). They show
that MIMO relay technology can both reduce infrastructure deployment costs and
combat shadow fading especially. And, the outage capacity of multihop networks
employing terminals with multiple antennas is studied by Fan
and Thompson (2005).
In multihop networks, wireless resource allocation is a key design issue. There
have been many studies on this open topic (Sadr et al.,
2007; Ahmed and Yanikomeroglu, 2006). And, the fairness
consideration on resource allocation is one of the most important design goals
since some multihop relay nodes achieve more radio resource (e.g., bandwidth)
and inevitably starve others. A hierarchical radio resource allocation scheme
for multihop mesh networks, which fairly assign subcarriers and power to multiple
mesh clients, is studied by Lee and Leung (2006). A
distributed and fair access (DFA) Medium Access Control (MAC) protocol for multihop
wireless networks is proposed by Suliman et al. (2005).
This design can offer stations more transmission opportunities without incurring
extra overhead to the current data transmission.
In this study, we consider to design a decodeandforward MIMOOFDMA multihop transmission mechanism and an orthogonal relay channel construction method. Over frequencyselective Nakagamim fading channels, a lowcomplexity timesubcarrier resource allocation algorithm is derived. Besides, the long term fairness consideration on the resource allocation is also discussed. And, two multihop resource allocation schemes are proposed and compared. One is for the fair resource assignment and another is for the throughput maximization. The fairness index and throughput performance are evaluated in various MIMO multihop relay scenarios and channel conditions.
MULTIHOP SYSTEM DESCRIPTION
The general OFDMAbased MIMO multihop network model is described here. And, a halfduplex decodeandforward multihop transmission mechanism is designed.
System description: The multihop relay network architecture is depicted
in Fig. 1. The Base Station (BS), relay nodes and the destination
Subscriber Station (SS) constitute the multihop system, which is divided into
T hop stages. At each hop stage, relay nodes are grouped into clusters to form
a multiantenna transmitter and a multiantenna receiver. Thus, a virtual MIMO
antenna array channel is formed by these relay nodes and used to connect the
BS and SS. The spatial diversity of the MIMO array can increase system throughput,
decrease communication error and adjust system fairness performance. Here, in
this study, we consider the transmission in the downlink (left to right) direction.
Orthogonal relay channel construction: To avoid complicated interhop interference cancellation processing of multihop networks, in this study, the resources allocated for different hop stages must be orthogonal. By using the OFDMA technique in MIMO multihop systems, we can exploit the twodimensional timefrequency resource to build up a multihop relay channel, as shown in Fig. 2.
In Fig. 2a, the MIMO multihop system comprises a set of hop stages, e.g., T_{stage} {1,2,..., t..., T_{hop}}, where, t is referred as the t^{th} hop stage number. And, T_{hop} is the t^{th} hop stage number. In this study, the system is assumed to have an even number of hop stages. The extension to an odd number of hop stages is obvious.
Figure 2b illustrates the timefrequency resource allocation for constructing an orthogonal multihop relay hannel. And, the subset of OFDM subcarriers allocated to one hop stage is referred as a subchannel. For each hop stage, the transmission scenario may be different. Therefore, the number of subcarriers assigned to each stage is variable and adjustable to maximize the entire multihop system throughput.
Multihop transmission mechanism: Since all relay nodes operate in a halfduplex mode, the multihop transmission procedure for the downlink is separated into two time periods.
Transmission in first time period: In the first time period, all odd
number hop stages 1,3,..., (T_{hop}1) are in operation. For example,
in the 1st hop stage, BS transmits its data to the relay nodes in the firstcluster,
while subchannel U_{1} is used for the 1st hop stage as shown in Fig.
2b. Based on the proposed resource allocation criteria and long term fairness
performance consideration, we do not address the complicated physical subcarrier
permutation scheme for each subchannel.

Fig. 1: 
OFDMAbased
MIMO multihop network under consideration 

Fig. 2: 
Multihop
transmission model, (a) multihop relay mechanism, (b) subcarrier/time
allocation for orthogonal relay channel 
So, we assume consecutive physical subcarriers:
are assigned to subchannel U_{1}, where, N_{c}^{(1)} is the number of subcarriers allocated in the 1st hop stage. Next, the firstcluster nodes receive signals from BS and decode the received information.
For other odd numbered hop stages, the transmission operates in a similar manner. However, only remaining subcarriers can be employed, that causes S_{PHY} (U_{j})∩S_{PHY} (U_{i}) = Ø, where, j ≠ i for j, i ∈ {1,3,5...(T1}. The amount of subcarriers and transmission time allocated to each stage should be calculated according to various multihop transmission scenarios. In this study, we will investigate how to optimally assign the timesubcarrier resource to maximize the mean throughput of entire multihop system.
Transmission in second time period: In the second time period, all even
number hop stages operate in a similar manner. For example, in the 2nd hop stage,
the firstclusters relay nodes regenerate and transmit forward the decoded information
of the 1st hop stage. After the T^{th} hop stage, the destination SS
will receive the BS information. And, the similar design is also studied in
our previous work (Zhou et al., 2009).
RESOURCE ALLOCATION SCHEME
Here, we focus on studying the multihop resource allocation algorithm for throughput maximization. The fairness consideration on multihop resource allocation is also investigated.
System throughput analysis: According to information theory, the endtoend
throughput of multihop system, depicted in Fig. 1, can be
given by Dohler et al. (2006):
where, denotes
the endtoend throughput of entire multihop system. The unit of is
defined as bits/s/Hz. is
the throughput of t^{th} hop stage, which can be determined by:
where, C^{(t)} is the ergodic capacity of t^{th} hop stage. T_{1} is the transmission time of the first relay period. T_{2} is the time of the second relay period. And:
Note that, in this study, for fair comparison with a traditional direct transmission scheme, θ_{norm} is the normalization factor for halfduplex multihop transmission mode. According to the proposed multihop transmission scheme:
because multihop transmission is divided into two time periods.
Then, the throughput of the halfduplex multihop system can be obtained as follows:
subject to
In the above, 1
and 2 describe the limited subcarriers resource
constrains. N_{c}^{(t)} is the number of subcarriers assigned
to the relay nodes at the t^{th} hop stage. N_{c} is the total
subcarrier number of the OFDM system. And, 3 corresponds
to the time resource constrains. 4 is the transmit
power constrain. P_{Tx}^{(t)} is the transmit power for the
t^{th} hop stage. P_{total} stands for the total transmit power.
For subcarrier resource constraints:
and
can also be expressed as:
where, Ψ_{c}^{(t)} is the ratio of subcarrier number of t^{th} hop stage to all OFDM subcarrier number.
Resource allocation for throughput maximization: Here, we study the resource allocation algorithm to achieve the throughput maximization.
Here, the channel is assumed quasistatic in time, remaining constant within the duration of a data block. And, the OFDM cyclic prefix is longer than the delay spread of the channel. The transmission power is distributed equally across all antennas and OFDM subcarriers. Then, the ergodic capacity C^{(t)} of t^{th} stage is given by:
where, S_{PHY} (U_{t}) denotes the subcarriers for the t^{th}
hop stage. is
the channel transfer matrix in the frequency domain of t^{th} hop stage.
And:
Here, addresses the smallscale
fading, following a Nakagamim probability density function (pdf).
The pdf of the amplitude of each entry
is given by:
where, Γ(m) is the gamma function, m is the fading parameter with m≥½ and
is the mean power.
And we also define and
.
Then, the corresponding channel capacity of one hop becomes:
where, is
the eigenvalue of
at the k^{th} subcarrier of t^{th} hop stage.
The MIMO capacity approximation over Nakagami channels is (Zhong
et al., 2009):
Our objective is to optimize the allocation of timesubcarrier resource to ensure that the throughput of each hop stage is equal to others, that is:
where,
Based on (11), (12) and (13), the resource allocation scheme can be shown as follows:
This numerical calculation has low complexity using standard softwares like Mathmatica and Matlab. The expression reveals the impacts of system parameters and channel condition, such as Nakagami fading severity parameter m, MIMO antennas deployment, etc. on the resource allocation for throughput maximization. Evaluation in the next section shows that this algorithm has good agreement with Monte Carlo simulation results.
From Eq. 5 and 14, we can obtain the subcarrier
allocation ratio and transmission time. This multihop resource allocation scheme
for throughput maximization is referred as MaxRate Scheme.
Long term fairness consideration: Fairness is an important design objective in wireless networks, which can help users efficiently utilize the limited radio resources. Based on Eq. 14, the resource allocation strategy can obtain the optimized endtoend system throughput. However, this scheme needs to know the system topological structure, cooperative relay nodes information and update channel state information of each hop stage. Moreover, this scheme may cause the unevenness of radio resource assignment among relay nodes. Some relay nodes would suffer from the starvation of resource allocation, which impacts on the system parameters, such as OFDMA subchannel size, maximum payload block length and power allocation, etc.
To quantify the fairness performance of the proposed radio resource allocation
scheme, we use the Jain’s fairness index (Jain, 1991),
that is:
where, .
And, x_{n} is the amount of resource to n^{th} user. N_{node}
is the total number of relay nodes. Ψ_{c}^{(n)} is the
subcarrier resource ratio assigned for n^{th} relay node. T^{(n)}
is the time resource for n^{th} relay node. And, we let X_{n}
= Ψ_{c}^{(n)} T^{(n)}, which represents the OFDMA
timesubcarrier resource block shared to n^{th} relay node, depicted
as Fig. 2b. For simplicity, the amount of resource assigned
to each relay node of one cluster is the same in one hop stage.
Here, we define a Fairness Index = 1 Scheme, which evenly provides the timesubcarrier
among all relay nodes with .
It has several advantages, such as preventing the severe starvation problem
on multihop resource assignment, avoiding excessive control signaling for multihop
resource allocation. This scheme is also useful with lack of MIMO channel information.
Clearly, this scheme provides a simple and fair sharing of radio resource. However, with limited radio resource, increasing the system throughput and maintaining the fairness are always conflicting. Fairness Index = 1 Scheme is at the expense of system throughput.
PERFORMANCE EVALUATION
Here, the system throughput and the fairness performance are evaluated under the proposed MIMOOFDMA multihop network.

Fig. 3: 
Simulation
scenario 
The simulation scenario is depicted in Fig. 3, where, d_{ref}
is the reference distance for the traditional direct transmission scheme. Figure
3b shows a twohop relay scheme. And, the general multihop scheme is illustrated
in Fig. 3c. Here, the propagation path loss exponent is 4.
The number of multipath is 6. And, in all simulations, we set the exponent
of power delay profile to 0.4. In the remainder, the MIMO scheme adopted in
the multihop system is referred as:
For example, (1x4) and (4x1) denotes a twohop system. The 1st hop stage has
(1x4) MIMO antenna deployment and the 2nd hop stage adopts a (4x1) MIMO scheme.
Simulation 1: Throughput performance is compared for various multihop schemes. The accuracy of proposed resource allocation analytical algorithm is also investigated with simulation results. The simulation scenario is conducted with twohop, fourhop, sixhop and direct transmission schemes. The related MIMO deployments are (1x1), (1x2) and (2x1), (1x2) and (2x1), (4x2) and (2x1), (1x1) and (1x2) and (2x4), (4x8) and (8x4) and (4x2) and (2x1).
Figure 4 shows that the analytical algorithm is in good agreement with Monte Carlo simulation results. And, Fig. 4 also shown that, in low SNR region, the system throughput is improved with increment of multihop stage number. For instance, when the throughput is 2 bits/s/Hz, the twohop scheme has 4.1 dB SNR gain compared with the direct transmission scheme.

Fig. 4: 
Throughput
comparison for various multihop schemes (m = 0.5) 
And, the 2.7 dB SNR gain is between fourhop and twohop scheme. However, in high SNR region, the throughput of onehop direct transmission scheme grows gradually and exceeds those of multihop schemes.
Simulation 2: The effect of Nakagamim fading on system throughput is evaluated in Fig. 5. And, the simulation scenarios are twohop systems. Here, case 1 corresponds to (1x1) and (1x1) scheme. (1x2) and (2x1) is case 2.(1x3) and (3x1) is case 3. And, (1x4) and (4x1) is case 4. Results show that the system throughput degrades with decreasing fading parameter m. Moreover, such degradation becomes more significant in low parameter m region, which represents the severe fading environment. But, Fig. 5 shows degradation can be eliminated by increasing the relay nodes number. For instance, when fading parameter m is 0.5, case 4 can achieve 0.97 bits/s/Hz throughput enhancement compared with case 1.
Besides, Fig. 5 also shows that the difference between analytical
results and simulation is inappreciable. From Fig. 4, 5,
it is indicated that the proposed analytical algorithm is efficient and can
be used as a reasonable reference to the multihop system performance.
Simulation 3: The impact of relay nodes on the system throughput and long term fairness performance is examined. This simulation scenario is in fourhop network. The received SNR is 10 dB. Here, the relay nodes in each hop cluster are the same, that is:
Figure 6a shows that, with increment of relay node number,
the system throughput is increased. But, on the contrary, the fairness index
performance decreases significantly, shown in Fig. 6b.

Fig. 5: 
Impact
of Nakagamim fading parameter on system throughput 

Fig. 6: 
Impact
of relay nodes on system performance (m = 0.5) 
The reason is that, by increasing the relay nodes number, more spatial diversity
gain can be obtained in the middle relay stage. But, due to antennas deployment
restriction, the diversity gain at destination SS is limited. To achieve throughput
maximization, the subcarrier and time resource can not be evenly assigned according
to Eq. 14, which causes the unfairness. The more spatial
diversity gain in the relay stage, the worse fairness performance becomes. This
simulation reveals that, by adjusting relay nodes number, we can achieve the
tradeoff between system throughput and fairness performance. Figure
6 also shows the system throughput and fairness performance can be improved
by increasing the antennas number on BS and SS, that is N_{Rx}^{(1)}
and M_{Rx}^{(4)}.
Simulation 4: The starvation problem on unfair subcarrier allocation of relay nodes is analyzed. Two application cases are analyzed for sixhop system. Case 1 is that each hop stage has the same distance interval, that is
Case 2 is for the system with unequal distance interval as d_{i} =
2d_{2} = 4d_{3} = 4d_{4} = 2d_{5} = d_{6}.
Here, sixhop MIMO scheme is (1x2) and (2x4) and (4x8) and (8x4) and (4x2) and
(2x1). And, the reference received SNR is 10 dB.
Firstly, to case 1, the simulation results are illustrated in Fig. 7a. If the odd hop stages in the first time period is examined, it shows that 1st hop occupies the largest amount of subcarriers and that subcarriers for the 3rd hop are least. And, this causes the starvation problem on subcarriers assignment. The reason is that the ergodic capacity of a (1x2) MIMO deployment is less than that of (4x8) and (4x2) MIMO deployment. And, more subcarriers are required so that the throughput of 1st hop is same as that of other hop stages.
Secondly, to case 2, Fig. 7b shows that the starvation problem becomes worse compared with case 1. The reason is that 3rd hop has the shortest transmission distance. And, lowest subcarriers assignment is required for 3rd hop to obtain the same throughput as that of other hops. We know that the starvation problem has influence on system parameters, such as the OFDMA subchannel size, payload length, etc. And, these can be solved by properly adjusting transmission power and MIMO deployment, etc., which will be addressed in further study.
Simulation 5: The throughput of two resource allocation schemes, that are MaxRate Scheme and Fairness Index = 1 Scheme, is compared. Twohop, fourhop and sixhop system scenarios are considered respectively. The related MIMO schemes are (1x3) and (3x1), (1x3) and (3x6) and (6x3) and (3x1), (1x3) and (3x6) and (6x9) and (9x6) and (6x3) and (3x1).
Figure 8 shows that, based on the flexible resource allocation method, MaxRate Scheme can achieve higher throughput than Fairness Index = 1 Scheme. Moreover, with increment of multihop stage number, the throughput of MaxRate Scheme is increased. For instance, if received SNR is 2 dB, there is 0.57 bits/s/Hz throughput gain between fourhop and twohop scheme. And, the throughput of six hop has 0.28 bits/s/Hz performance gain compared with that of fourhop scheme.
According to Fig. 8b, to Fairness Index = 1 Scheme, it is worth noting that the system throughput degrades greatly with increase of multihop stage number in high

Fig. 7: 
Impact
of distance interval on subcarrier allocation (m = 0.5) 

Fig. 8:  Throughput
comparison for two allocation schemes (m = 1.0) 
SNR region. The reason is that Fairness Index = 1 Scheme does not satisfy the optimal resource allocation criteria. But, Fairness Index = 1 Scheme has several advantages, such as avoiding excessive control signaling and having no starvation problem. So, the tradeoff between MaxRate scheme and Fairness Index = 1 Scheme is quite necessary. And, these simulation results give reference to the tradeoff design in multihop systems.
CONCLUSIONS
This study investigated a decodeandforward MIMOOFDMA multihop system. The relay transmission strategy, system throughput, long term fairness performance was considered. We derived a lowcomplexity analytical algorithm for multihop timesubcarrier allocation over Nakagamim channels. We also proposed two multihop radio resource allocation schemes. One is for the fair resource assignment and another is for the throughput maximization. Monte Carlo simulations demonstrated the effectiveness of the proposed resource allocation algorithm. Besides, the multihop system throughput and fairness index performance was evaluated over various scenarios and channel conditions. Numerical results have confirmed that the proposed technique can bring benefits of high throughput, good fairness performance and flexible network deployment to multihop systems.
ACKNOWLEDGMENTS
This study is supported by the National Natural Science Foundation of China under Grant No. 60802011 and the Specialized Research Fund for Doctoral Program of Higher Education of China under Grant No. 200802461141.