Cluster-based design for two-hop cellular networks.

1. Introduction

Some of today's key challenges in the design of wireless systems are to provide high peak data rates as well as to provide a network architecture that allows for an efficient utilization of the scarce spectrum resources while the power consumption of the network is minimized. Currently deployed single-hop cellular networks as a stand-alone technology are handicapped by numerous limitations, viz., inability to cover dead zones, high attenuation of signals, high shadowing, inefficient use of energy, etc. A direct evolution of the existing cellular network architecture are multihop hybrid cellular networks, where the communication between the mobile station (MS) and the base station (BS) takes place in multiple hops [1]. One can envisage a multihop hybrid cellular network as a means to enable sharing of information between possibly mobile sensor nodes or gathering of sensed information toward query points on a wireline network [2]. Alternatively, one can view multihop cellular network models as a method to extend the communication coverage and provide higher data rate for an infrastructure-based cellular network [3]. Such a hybrid network model aims at providing global connectivity. At the same time, it seeks to mitigate interference, and to maximize the system capacity of the network while achieving a frequency reuse of one. This is the target being aimed for the development of 4th generation, or IMT-Advanced, wireless networks. These systems are primarily based on orthogonal frequency division multiplexing (OFDM), time division multiple access (TDMA), frequency division multiple access (FDMA) and time division duplexing (TDD) [4].

In recent years, there has been extensive research work in the direction of capacity scaling for multihop hybrid wireless networks. It is shown in [5] that having the infrastructure based BS component over the multihop ad hoc network drastically increases the connectivity of the network. For a multihop hybrid cellular network with n nodes and m BSs, the results in [6] show that if m grows asymptotically slower than [square root of n] , the benefit of adding BSs on capacity is insignificant. However, if m grows faster than [square root of n], the system capacity increases linearly with the number of BSs providing an effective improvement over the multihop ad hoc network. Therefore, in order to achieve non-negligible capacity gain, the investment in the wired infrastructure should be high enough. It has been shown through outage analysis in [1] that an integration of cellular and multihop communication models results in better relaying and avoids traffic congestion. Deploying relays can clearly help improve the performance of the users near the edges of the cell and has the potential to solve the coverage problems for high data rates in macrocells [7]. TDD is the enabling technology for the multihop design [8]. Hence, by having simultaneous transmission by both BSs and relays, capacity gains can also be achieved in the cellular network. However, a multihop hybrid cellular design also requires extra radio resources for relaying hops and is sensitive to the quality of relaying routes. Therefore, multihop hybrid cellular networks require a well-designed radio resource allocation strategy in order to secure performance gains. A hybrid architecture, viz., mobile assisted data forwarding (MADF) is proposed in [9], wherein, a multihop relaying system is overlaid on the existing cellular networks. The main objective of this system is to dynamically divert the traffic load from a hot cell (highly loaded cell) to cooler cells (lightly loaded) in its neighborhood. Similarly, a multihop cellular network (MCN) architecture is investigated in detail in [10,11,12], wherein, the end-to-end communication is always between the MS and BS, like in a traditional single-hop cellular network. There has been considerable research work in finding different routing techniques for multihop cellular networks, viz., base assisted ad hoc routing (BAAR), base-driven multihop bridge routing (BMBP), [13] single-interface multihop cellular network routing protocol (SMRP) [14], for different kinds of traffic patterns. These techniques effectively utilize the ad hoc relaying in presence of fixed infrastructure in order to achieve enhanced network capacity. However, it has been shown in [15] that optimum resource allocation in multihop cellular networks, with the objective of throughput maximization with radio resource allocation (TM-RRA) is an NP-hard problem. In fact, the well-known multiple choice knapsack problem, (MCKP), which is proved to be NP-hard [16], is shown to be a restricted version of TM-RRA [15]. Hence, researchers across the scientific community have worked towards designing suboptimal but efficient heuristic algorithms and architecture designs.

In this paper, a multihop cellular network model is designed such that all communication between the source and destination nodes is routed through the BS. All the mobile nodes communicate with the BS in either single-hop or two hops. However, the focus of this paper is on designing a novel cluster-based architecture for a two-hop cellular network. Section 2 presents the system model and the underlying mechanism of the cluster-based design. Section 3 explains how the system capacity is calculated for such a design. A deterministic cluster-based technique is described in Section 4 and a semi-analytical model is presented for calculating the different interferences and the carrier-to-interference ratio, [gamma]. In addition, the capacity bounds for the semi-analytical model and the confidence interval due to lognormal shadowing are also calculated in Section 4. The simulation model and the results of the cluster-based design are presented in Section 5 and Section 6 respectively, along with a performance comparison with other benchmark algorithms. Finally, conclusions are provided in Section 7.

2. System Model

A multi-cellular system, with a BS at the center of each cell, is considered in the network design. The maximum distance between the BS and the edge of the cell is given by, r. There are 19 hexagonal cells in the coverage area. These 19 cells are arranged such that a center cell is surrounded by six cells in the 1st tier and twelve cells in the 2nd tier. A Protocol Model [17] is considered in the system design in order to reduce the interference. According to this model, a circular exclusion region is defined around every communicating receiver, such that no other transmitter apart from the desired transmitter communicates in this exclusion region. The radius of this circular exclusion region, [r.sub.c], is given by the following equation.

[r.sub.c] = (1 + [DELTA])[d.sub.c] (1)

In the literature [17], [r.sub.c] is also sometimes termed as the exclusion range. In Equation (1) above, [d.sub.c] is the distance between the transmitter and receiver of any communicating pair, and [DELTA] [greater than or equal to] 0 is the spatial protection margin, that indicates the ratio of increase of the exclusion range distance to the transmission range distance. Hence, at any time instant in a TDMA system, all receivers of the simultaneously communicating pairs are inherently separated from the unintended transmitters, by at least, the exclusion range distance, i.e., the minimum distance between any receiver and an unintended transmitter is at least (1+ [DELTA]) times the transmission distance of the desired communication pair. It is shown in [18] that under the Protocol Model, the system capacity is maximized when the spatial protection margin of the Protocol Model is around [DELTA] =1.0. Hence, a spatial protection margin of [DELTA] =1.0 is considered throughout this work, while designing the cluster-based architecture for the two-hop cellular network.

The proposed cluster-based design is based on the formation of multiple clusters in every cell. Each cell is initially divided into two layers, viz., inner layer and outer layer.

1) Inner Layer: This is the circular area contiguous to the BS; and the MS in this zone communicate to the BS directly using a single-hop. The distance between the MS and BS in the inner layer is always less than or equal to half the cell edge length, i.e., r/2.

2) Outer Layer: This circular region is located around the inner zone, and the MSs located in this region communicate to the BS in two hops. This area is further divided into several clusters. The MSs within any of the clusters would communicate to the BS via a cluster-head node, called the gateway (GTW). The GTWs are located on the boundary adjoining the inner and outer layer, i.e., at a distance of r/2 from the BS. Since the radius of the hexagonal cell is r, the maximum distance between the GTW and the MSs in the outer layer would be r/2. Hence, the maximum transmission distance in the cell, i.e., between BS and GTW (inner layer), or between MS and GTW (outer layer) is r/2.

The MSs located in the outer layer are grouped into several clusters. A single cell scenario depicting the schematic of a cluster-based two-hop cellular architecture is shown in Figure 1. There are six circular clusters in each cell. For each of the clusters, a wireless terminal located at the boundary of the inner and outer layer of the cell is selected as a cluster-head node, alternatively known as GTWs. There are six GTWs/cell, each of them located at a distance of r/2 from the BS. Cluster-heads [GTW.sub.1a] and [GTW.sub.1b] are diametrically opposite to each other and are separated by a distance of r, i.e., twice the transmission distance, r/2. The same holds for the cluster-heads [GTW.sub.2a] and [GTW.sub.2b], and for [GTW.sub.3a] and [GTW.sub.3b]. In practice, the GTWs could be fixed relay stations (RSs), located on the street lamps/roof tops, or, MSs/wireless terminals with their own traffic. In case of fixed RSs/GTWs, they could probably be placed at exactly r/2 from the BS.

However, if the MSs are selected as relays, then the exact location of the relay node would depend on the distribution and the density of the mobile terminals. Hence, the selected GTW node could be located at a distance slightly less or greater than r/2 from the BS, and also, the GTWs would not be equidistant to each other. There would be a small yet noticeable difference in the system performance due to fixed/mobile GTWs, and is explained later in Section 6. In addition, a deterministic cluster-based design is considered in the semi-analytical model, later in this paper, where the six GTWs in the cell are assumed to be both equidistant to each other, located exactly at a distance of half the cell radius from the BS, and most importantly, the MSs in the outer-layer of the cell are assumed to be at a maximum distance of r/2 from the cluster-head GTWs. An important point to be noted is that the number of clusters per cell in the cluster-based design need not be always six. It could be two, four, six, eight, ten or even higher. The only condition is that the number of clusters per cell has to be an even number, due to the basic principle of simultaneous transmission of communication pairs located in the diametrically opposite clusters in the cell. However, in practice there is a limitation that as the number of clusters per cell is increased, the amount of resources that could be given to one cluster decreases. In a very recent work, it is shown [19] that for a cellular network, with six BSs surrounding the central BS, the optimum number of GTWs in each cell that maximizes the system capacity is six.

[FIGURE 1 OMITTED]

[FIGURE 2 OMITTED]

This justifies the selection of six GTWs in the cluster-based two-hop cellular design. The variation of system capacity for different number of GTWs per cell is shown in Section 6. In addition, the cell region could be divided such that the radius of the inner layer is [tau][tau] where 0 < [tau] 1 is the ratio of the inner layer radius to the radius of the cell [20]. In that case, the maximum transmission distance would no longer be restricted to r/2. However, the cluster-based design would be still valid, as would be observed later when the GTWs are selected from the MSs.

In order to understand the complete working mechanism, a conceptual model of the cluster-based two-hop cellular network with six clusters/cell and equidistant GTWs at a fixed distance of r/2 from the BS is considered, and the underlying principle of the synchronized resource reuse technique is described as follows:

1) As shown in Figure 1, SH0 is the inner-layer (single-hop region) and [MH.sub.1a], [MH.sub.1b], ... [MH.sub.3b] are the two-hop clusters in the outer layer. In addition, [GTW.sub.1a], [GTW.sub.1b] ... [GTW.sub.3b] are the respective cluster-heads for [MH.sub.1a], [MH.sub.1b] ... [MH.sub.3b]. Each cluster contains a number of MSs. In case of downlink communication between BS and a wireless terminal located in any of the clusters, the BS would communicate to the cluster-head GTW in the 1st hop, and in the 2nd hop, the GTW would communicate to the MSs associated with the corresponding clusters. Similarly, in the uplink, the MSs in any of the clusters communicate with the BS in two hops, wherein, the MS communicates to the GTW in the 1st hop, and the GTW communicates to the BS in the 2nd hop.

2) A TDD/TDMA scheme is considered for the cluster-based two-hop network. For a multihop system with number of hops per link, M [greater than or equal to] 1, the signal for any hop can be transmitted only for T/M time slot duration, where T is the TS period. Hence, the TS is divided into two minislots for the two-hop links. However, for a wireless node located in the inner layer ([SH.sub.0]), the communication between the wireless terminal and the BS would take place in single-hop, for the full duration of one TS.

3) The reusability of the resources is increased by allowing two multihop clusters in any cell to occupy the same TS at the same frequency. As shown in Figure 1, the clusters MH1a and MH1b are located at diametrically opposite sides of the BS. The synchronized TDD frame structure for both uplink and downlink is shown in Figure 2. In the downlink, [GTW.sub.1a] can download to the MS in its cluster in a particular time slot. At the same time instant, the BS could download to [GTW.sub.1b] in the opposite cluster of the same multihop cell. It should be noted that both these simultaneously communicating pairs are outside the exclusion region of each other. Similarly, in the next time slot, the [GTW.sub.1b] [right arrow] MS and BS [right arrow] [GW.sub.1a] communication takes place simultaneously.

4) In the uplink, the transmitters and receivers of the cluster-based model are reversed, as seen in Figure 2, but the governing principle of the resource reuse technique remains the same. It can be therefore noted that the reuse of the resources can be done independently for both uplink and downlink, using the synchronized resource reuse technique. Hence, this cluster-based design remains valid even for asymmetric traffic, as long as the traffic asymmetry remains the same for all the cells.

5) The given TS resource is also allotted to each of the hexagonal cells in the system. As shown in Figure 3, for both uplink and downlink, the transmitters of all the concurrently communicating pairs in the adjacent cells are beyond the exclusion region of the desired receiver in the intended cell. Hence, as shown in Figure 4, a given TS resource is not only used by two simultaneously communicating pairs in any cell, but also, the same TS resource is reused in every cell. However, it is to be noted that a TS resource given to a communicating pair in a two-hop network is only half the time slot period given to an equivalent single-hop network, as shown in Figure 2. Due to using a resource twice within a cell, however, the cluster-based design effectively results in a frequency reuse factor of one.

6) The GTWs can be considered to be equidistant and located at approximately r/2 from the BS if they are fixed terminals. However, if the GTWs are not fixed, and are selected from the distributed MSs, then, the wireless terminal located at either half the cell radius or closest to half the cell radius (either in the inner-layer or in the outer-layer) is selected as a GTW. Irrespective of whether the selected GTW is in the inner layer or outer layer, the transmission distance of the communicating pair between the BS and GTW would be then different from r/2. Correspondingly, the transmission distance of the GTW MS pair would also vary.

[FIGURE 3 OMITTED]

3. Capacity Calculation

All the wireless terminals in any cell are assumed to transmit their signals with the same power, [P.sub.T]. If [d.sub.c] is the transmission distance between any communicating pair, then the power received, [P.sub.R], using a general propagation model is given by:

[P.sub.R] = [P.sub.T] - ([k.sub.1] + 10[alpha][log.sub.10]([d.sub.c]) + [[xi].sub.c] [dB] (2)

where [k.sub.1] is a constant that depends on the propagation environment (indoor/urban/suburban), a is the path loss exponent and [[xi].sub.c] is the shadowing factor across the transceiving pair. In a multi-cell scenario, the given radio resource is utilized by all the cells in the system. The transmitters of all simultaneously communicating pairs in the seven-cell scenario are marked and shown in Figure 4 along with the interference calculation at the receiver gateway (i.e., the receiver of BS [right arrow] GTW pair) of the center cell (cell 0). The thick arrows in Figure 4, from BS [right arrow] GTW and GTW [right arrow] MS in all the cells represent the simultaneous communicating pairs. A reference line (dotted line in the figure) is considered that connects the BS of cell 0, cell 1 and cell 4. The dashed lines from the transmitting BSs and GTWs of cell 2 and cell 3, to the Rx GTW in the center cell indicates the distance of the Rx GTW from other interfering transmitters in cell 2 and cell 3.

[FIGURE 4 OMITTED]

In all, the Rx GTW in cell 0 would experience interference from thirteen interferers: two interferers from each of the six adjacent cells and one transmitting GTW (of GTW . MS pair) from cell 0.

For any communicating pair, the inter-cell interference only across six adjacent cells, i.e., the 1st tier of cells is considered. The transmitting interferers from the 2nd tier of cells are very far from the intended receiver, and hence, the interference generated from these transmitters is assumed to be negligible. Therefore, for any communicating pair in this cluster-based model, there is one interferer from own cell and two interferers from each of the adjacent cells. The carrier-to-interference ratio is therefore calculated as follows:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (3)

where [d.sub.i] is the distance of the desired receiver from the ith interfering entity and NI is the total number of interfering entities for any receiver in a cluster-based model. [[xi].sub.i] x accounts for shadowing between the desired receiver and the ith interfering transmitter. The capacity in bps/Hz/cell is calculated by finding the system capacity independently over seven cells (center cell and six cells in the 1st tier), as shown in Figure 4, and averaging over them. Each cell in the 1st tier is surrounded by six cells out of which three cells belong to the 2nd tier. The traffic in the twelve cells of the 2nd tier only contribute for the intercell interference calculation for the 1st tier of cells. This 2nd tier of cells is necessary to remove the boundary effects while calculating g for the 1st tier of cells, and hence, the Shannon bound is not calculated for the twelve cells in the 2nd tier. As shown in Figure 2, the data across each communicating pair is transmitted for only half the time slot period in a two-hop system. As a consequence, the Shannon capacity has to be scaled by a factor of 1/2. Also, in each of the seven cells, there are two simultaneously communicating pairs, and depending on the distance of the interfering transmitters the receivers of these two communicating pairs would have different values of g. Therefore, the system capacity (of only the two-hop links) is calculated from the Shannon equation as:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (4)

where [[gamma].sub.ij] is the carrier-to-interference ratio of the jth communicating pair in the ith cell. [N.sub.l] is the number of concurrently communicating pairs in the outer layer that use the same radio resource, in any single cell. For a cluster-based design, two pairs located diametrically opposite to each other communicate simultaneously, i.e., [N.sub.l] =2. [N.sub.C] =7 is the number of cells over which the system capacity is calculated. In order to calculate the average per-cell system capacity, the Shannon capacity equation in Equation (4) is summed up over all [N.sub.c] cells and averaged over them.

4. Semi-Analytical Model

In order to assess the performance of the synchronized resource reuse technique for the cluster-based design, a semianalytical model is developed for a deterministic cluster-based two-hop network. In this deterministic cluster-based model, the GTWs are fixed and located exactly at a distance of r/2 from the BS. Also, the GTWs are equidistant from each other. Hence, the six GTWs in the cell represent the six vertices of a regular hexagon, with a side length of r/2. In addition, the MSs in the outer layer are assumed to be always located at a distance of r/2 from their respective GTWs; and also, the MSs are assumed to be uniformly distributed between [0[degrees],360[degrees]] across the outer layer of the cell. Hence, the distance between the BS and GTW, and also the distance between the MS and its corresponding GTW is fixed. This simplifies the analysis for numerically calculating the Shannon capacity of the cluster-based two-hop network. However, the precise location of the GTW in the cell is determined from the angle made by the BS - GTW pair with the reference line, as shown in Figure 5. [q.sub.11] indicates the angle made by the 1st communication pair, BS [right arrow] GTW, in the intended cell (cell 0 in this case) with the reference line of cell 1, whereas, q11 indicates the angle made by the 2nd communication pair, GTW [right arrow] MS, in the intended cell (cell 0 in this case) with the reference line of cell 1. Similarly, x11 and x12 indicates the angles made by the 1st interfering communication pair, BS [right arrow] GTW, and the 2nd interfering communication pair, GTW [right arrow] MS, (both) in cell 1 with the reference line of cell 1. The precise location of any MS is determined by the angle made by the line joining the MS and its corresponding GTW with the reference line. At the same time, in the deterministic cluster-based model, the trans- mission distance is always the maximum possible value, r/2.

[FIGURE 5 OMITTED]

In Section 6, the capacity results obtained from the deterministic cluster-based model are compared with the simulation model. For both uplink and downlink, this Semi-analytical model first calculates the distance of the intended receiver from all simultaneously communicating intended transmitters. A downlink schematic for a seven-cell cluster-based two-hop model is shown in Figure 4. It should be noted from Figure 4 that only the locations of the BSs are fixed. The distance between two BSs is [square root of 3] r. Since the transmission distance, [d.sub.c] =r/2, for the cluster-based model, the distance between two BSs can also be written as 2[square root of 3[d.sub.c]] . In Figure 4, all the transmitters in the seven cells are shaded with gray background. The black circle in the center cell marks one of the desired receivers which would experience interference from other unintended transmitters. The distance between the black circle (desired receiver) and all the gray colored circles (interfering transmitters from the own cell and all the adjacent cells) marks the distance of the different interfering entities. Hence, as shown in Figure 4, the total interference experienced by a receiver depends on the relative distance between this receiver and all its interfering transmitters.

4.1. Carrier-To-Interference Calculation for Downlink.

In the downlink, the communication takes place from BS [right arrow] GTW and from GTW [right arrow] MS. Figure 5 (both, case a and case b) shows the simultaneously communicating pairs in cell 0 and cell 1 in the downlink scenario. As seen in Figure 5, there are two simultaneously communicating pairs per cell, i.e., the BS [right arrow] GTW pair and GTW [right arrow] MS pair. The receivers of cell 0 would experience interference not only from its own cell, but also from the simultaneously communicating pairs from other cells. The interference experienced by the communicating pairs in cell 0 are calculated as follows:

1) BS [right arrow] GTW Communication in the Intended Cell: When the gateway in the intended cell is the desired receiver (say, GTW1a in cell 0 in Figure 5), the distance between this gateway and the interfering transmitters of the adjacent cell are calculated as shown in Figure 5(a). There are two cells, cell 0 and cell 1. Using basic trigonometry, the distance of the communicating receiver in cell 0 from the interfering transmitters in cell 1 is computed. As shown in Figure 5(a), the distance of receiving gateway at cell 0, GTW1a, from the BS of cell 1 is given by:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (5)

whereas the distance of the unintended transmitting gateway of the cell 1, GTW2b, to the desired gateway receiver in cell 0 is given by:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (6)

The angle, [q.sub.11], is formed between the line joining the communicating pairs, BS[right arrow]GTW1a in cell 0 with the reference line of cell 1. Similarly, [x.sub.12] is the angle between the line joining the communicating pairs, GTW2b [right arrow] MS in cell 1, with the reference line of cell 1. The above equations, Equation (5) and Equation (6) could be generalized to calculate the interference coming from the transmitters of all the six adjacent cells into the desired receiver, i.e., the GTW of the intended cell. By changing the reference line for each of the six adjacent cells, the distance of the interfering transmitters from the ith cell can be calculated as follows:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (7)

=13 [d.sub.c.sup.2] - 4 [square root of 3[d.sub.c.sup.2] cos ([[theta].sub.i1] (8)

whereas the distance of the unintended transmitting GTW to the desired GTW receiver is given by:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (9)

= 14[d.sub.c.sup.2] + 4[square root of 3[d.sub.c.sup.2] (cos ([[phi].sub.i2]) - cos ([[theta].sub.i1])) - 2[d.sub.c.sup.2] cos [[phi].sub.i2] - [[theta].sub.i1]) (10)

Here,

[[theta].sub.i1] = [q.sub.i1] + 60(i - 1) (11)

is the angle in degrees made by the BS [right arrow] GTW communicating pair in the intended cell with the reference line of the ith cell, and

[[phi].sub.i2] = [x.sub.i2] + 60(i - 1) (12)

is the angle in degrees made by the GTW[right arrow]MS in the ith cell with the reference line of the ith cell (Figure 5(a) shows the angle [x.sub.12] made by the GTW2b [right arrow] MS communicating pair in cell 1, with the reference line of cell 1). It should be noted that all [theta] and [phi] vary uniformly from [0[degrees], 360[degrees]]. In addition, the distance of the intra-cell interfering transmitter is, [d.sub.owncell]=2[d.sub.c]. The carrier-to-interference value at the receiver of any communication pair is therefore given by:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (13)

[FIGURE 6 OMITTED]

Dividing the numerator and denominator by [d.sub.c.sup.-a] results in:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (14)

where

[[beta].sub.(BS)i.sup.2] = 13 - 4[square root of 3]cos ([[theta].sub.i1]) (15)

[[beta].sub.(GTW)i.sup.2] = 14 - 4[square root of 3]cos ([[phi].sub.i2]) - cos[[theta].sub.i1])) -2cos ([[phi].sub.i2] - [[theta].sub.i1]) (16)

If the orientation of the GTW is fixed with respect to the BS, then the interference and the capacity of the BS [right arrow] GTW pair in the semi-analytical model varies only with the location of all the interfering transmitters from own cell and adjacent cell. Hence, the best and worst case for the capacity of BS [right arrow] GTW pair in the intended cell can be calculated by considering all the interferers to be located at the maximum and minimum distance from the intended receiving GTW of the BS [right arrow] GTW pair.

Upper bound for capacity:

As can be seen from Figure 6(a), the own-cell interferer (transmitting GTW from the diametrically opposite cluster) is at a fixed distance of r from the intended receiver (GTW of cell 0). Similarly, the interfering transmitters of the adjacent cell (BS and GTW) are at a distance of [d.sub.BS] = [square root of 3r + r/2 [approximately equal to] 2.232r and [d.sub.GTW] = [square root of 3r + r [approximately equal to] 2.732r respectively from the intended receiver. It should be observed that these intercell interferers are at a maximum possible distance from the intended receiver; and hence, causes the least interference to the intended communicating pair. The carrier power at the receiver of the BS [right arrow] GTW pair is given by

[P.sub.R] = [P.sub.T] - ([k.sub.1] + 10[alpha]log10(r/2)) (17)

For a multi-cellular network with r=217m, a propagation model [21] with [k.sub.1]=37, [alpha]=4, and assuming a transmit power of 1W, i.e., 0 dBW, the received power, [P.sub.R], would be -118.4 dBW. The BS [right arrow] GTW pair in the intended cell would experience interference from six adjacent cells. Hence, the upper bound for the capacity of the BS [right arrow] GTW communicating pair is obtained by substituting the values of these interferences distances into Equation (13) for calculating the resulting interference. The upper bound of the capacity for the BS [right arrow] GTW communicating pair is then obtained by substituting the resulting interference into Equation (4). The total interference power experienced by the receiving GTW node would be -129.2 dBW. The upper bound for the capacity of BS [right arrow] GTW pair would be 3.68 bps/Hz.

Lower bound for capacity:

The lower bound for the capacity of GTW [right arrow] MS pair is obtained by considering the minimum distance of the inter-cell interfering entities. As can be observed from Figure 6(b), the minimum distance of the interfering transmitters (BS and GTW) from the adjacent cell are [d.sub.BS] = [square root of 3] r - r/2 [approximately equal to] 1.232r and [d.sub.GTW] = [square root of 3] r-r [approximately equal to] 0.732r respectively from the intended receiver. The resulting lower bound for the capacity of BS [right arrow] GTW pair is 0.72 bps/Hz.

2) GTW [right arrow] MS Communication Pair in the Intended Cell:

For the 2nd active communication pair, GTW [right arrow] MS, in the downlink of cell 0, the maximum distance of the intended receiver, i.e., the MS of the GTW [right arrow] MS pair, from the BS is twice the transmission distance. Therefore, as seen in Figure 5, the MS in cell 0 is located at a distance of d = [2d.sub.c] = r from the BS, and is distributed uniformly from [0[degrees], 360[degrees]]. The distance of the interfering BS and the interfering GTW from the cell 1 is calculated from basic trigonometry as:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (18)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (19)

This equation for calculating the distances of the interfering transmitters from other cells could be written in a generalized form as:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (20)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (21)

where, [[theta].sub.i2] = [q.sub.i2]+60(i-1) is the angle in degrees made by the GTW [right arrow] MS pair in the intended cell with the reference line of the ith cell (Figure 5(b) shows the angle [q.sub.12] between the communicating pair, GTW1b [right arrow] MS with the reference line of cell 1). Equation (20) is simplified and the corresponding equations for [[beta].sub.(BS)] and [[beta].sub.(GTW)] are given as:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (22)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (23)

It should be noted that the equation for [gamma] remains the same as given in Equation (14).

[FIGURE 7 OMITTED]

Upper bound for capacity:

In the semi-analytical model, the MS in the GTW [right arrow] MS pair is assumed to be at a maximum distance of r/2 from the GTW. The own-cell interferer is the transmitter from the diametrically opposite cluster. Hence, the own cell interferer is at a distance of r from the desired receiver. It can be observed from Figure 7 that the maximum distance of the interferers from an adjacent cell are [d.sub.BS] = [square root of 3]r + 3r/2 [approximately equal to] 2.732r and [d.sub.GTW] = [square root of 3] r + 3r/2 [approximately equal to] 3.232r respectively. Hence, substituting these values into Equation (13) and Equation (4) results in the upper bound for the capacity of the GTW [right arrow] MS communicating pair, which is 3.91 bps/Hz.

Lower bound for capacity:

Similarly, the lower bound for the capacity of the GTW [right arrow] MS pair is calculated by knowing the distance of all the interfering entities. The own cell interferer is at a distance of r, whereas the minimum distance of the interferers from any adjacent cell are 0.5r and r, as is shown in Figure 7. Hence, the lower bound of the capacity for the communicating pair is 0.21 bps/Hz.

3) Capacity Bounds for End-to-End Link: In a two-hop system, the capacity of the end-to-end link is limited by the lower value of the capacity of any of the two-hops of the link, i.e., if the capacity of the 1st hop of the link is less than the capacity of the 2nd hop of the link, then the capacity of the end-to-end link is limited by the capacity of the 1st hop of the link [22]. Hence, the capacity of the end-to-end link in the downlink scenario in the cluster-based design is limited by the lesser of the capacity values of BS [right arrow] GTW pair and GTW [right arrow] MS pair. Hence, the lower and upper bounds of the capacity for the cluster-based two-hop design is limited by the capacity values of the BS [right arrow] GTW pair, and is equal to 0.21 bps/Hz/cell and 3.68 bps/Hz/cell respectively.

It should be noted at this stage that the upper bound of the GTW [right arrow] MS pair would be higher than 3.91 bps/Hz/cell if the distance between the GTW and MS is less than r/2. However, since the upper bound of the downlink capacity for the cluster-based design is limited by the lesser of the capacity values of BS [right arrow] GTW and GTW [right arrow] MS pair, the higher values of the capacity obtained by the GTW [right arrow] MS pair does not change the capacity result of the cluster-based design.

4) Effect of Lognormal Shadowing on Capacity Bounds: In presence of lognormal shadowing, the bounds for the system capacity would vary. The amount of variation would depend on the standard deviation of the lognormal shadowing. Due to the summation of lognormal variables in the calculation of the interference power (as shown in Equation (3)), it is very difficult to find an exact expression that would reflect the effect of lognormal shadowing on the system capacity. Instead, the effect of lognormal shadowing on the capacity bounds is computed in this paper. Lognormal shadowing with zero mean and standard deviation of 4 dB is considered throughout the analysis [23]. The received power for the carrier signal would vary within a value of 2[zeta], i.e., 8 dB, for a confidence measure of 95% [24].

Effect on upper bound of capacity:

The upper bound of the capacity in case of downlink communication is 3.68 bps/Hz/cell, achieved for the BS [right arrow] GTW communication. The corresponding value of the carrier power and total interference power are -118.4 dBW and -129.2 dBW respectively, resulting in a [gamma] of 10.8dB. An 8 dB variation in the signal strength implies that the carrier power would be between -110.4 dBW and -126.4 dBW for 95% of the cases, i.e., a variation of 6.75% on either side of -118.4 dBW. There are thirteen transmitters that would interfere with the intended communicating pair and the resulting interfering power would be a summation of all these interferers. If the same confidence measure of 95% is to remain for both the carrier signal and the resulting interference signal, then a higher confidence measure should be assumed for each of the interfering entities. A confidence measure of 99.6% for the power received from each of the thirteen independent interfering transmitters would result in a confidence measure of 95% ([0.996.sup.13] = 0.95) for the resulting interferers [25]. However, a confidence measure of 99.6% for each of the interfering entities implies that the total interference power would vary by 6[zeta], i.e., 24 dB. Hence, the total interference power would be between -105.2 dBW and -153.2 dBW for 95% of the cases, i.e., a variation of 18.55% on either side of -129.2 dBW. Therefore, [gamma], would experience a variation of 25.3% (6.75+18.5) around 10.8 dB (-118.4+129.2). Hence, the system capacity would vary between 2.75 bps/Hz/cell and 4.61 bps/Hz/cell for 90% of the cases, due to lognormal shadowing. It should be noted that the multiplication of the confidence measures for the carrier power (95%) and for the interference power (95%) results in a confidence measure of 90% for the values of . and the system capacity.

A significant inference that can be derived from the above calculation is that even for a shadowing with a zero mean and 4 dB standard deviation, the upper bound of the system capacity would vary by 25.3% around its mean, for 90% of the cases. If the environment causes a much higher shadowing, the variation in the upper bound of the system capacity would be still higher. This shows the significance of taking the shadowing into considerations while allocating the resources in a wireless network.

Effect on lower bound of capacity:

The lower bound of the capacity in case of downlink communication is 0.21 bps/Hz/cell, achieved for the GTW [right arrow] MS communication. The corresponding value of the carrier power and total interference power are -118.4 dBW and - 110.3 dBW respectively, resulting in a [gamma] of -8.1 dB. Similar to the upper bound case, a confidence measure of 95% implies a variation of 6[zeta] = 24 dB in the interference power. Hence, the total interference power would be between -86.3 dBW and -134.3 dBW for 95% of the cases, i.e., a variation of 21.75% on either side of -110.3 dBW. Given that the carrier power would experience a variation of 6.75% on either side of -118.4 dB, the value of [gamma] and the system capacity would experience a variation of 28.5% (21.75% + 6.75%) around 0.21 bps/Hz/cell, for 90% of the cases. Hence, for a lognormal shadowing with zero mean and a standard deviation of 4 dB, the lower bound of the system capacity would vary between 0.15 bps/Hz/cell and 0.27 bps/Hz/cell for 90% of the cases. It can be observed that the absolute effect of lognormal shadowing on the lower bound of the capacity value is not a significant issue, since the lower bound of the system capacity is already a very small value.

4.2. Carrier-to-Interference Calculation for Uplink

In the case of an uplink as well, there exist two simultaneously communicating pairs in the cluster-based model: the MS [right arrow] GTW and the GTW [right arrow] BS pairs located at the diametrically opposite clusters. In the case of an uplink, both the transmitters in the cluster-based design: the GTW and the MS, are not fixed, whereas, the receiver of one of the communicating pairs, i.e., the BS of GTW [right arrow] BS pair is located in a fixed position. This results in a slightly modified expression for [beta] in case of uplink, as compared to the downlink scenario:

1) MS [right arrow] GTW Communication Pair in the Intended Cell:

For the MS [right arrow] GTW pair communication, the expression for [beta] is given by:

[[beta].sub.(MS)i.sup.2] = 17 + 4 [square root of 3] (2 cos([[theta].sub.i2] - cos([[phi].sub.i2])) -4 cos([[phi].sub.i2] -[[theta].sub.i2])(24)

[[beta].sub.(GTW)i.sup.2] = 14 + 4 [square root of 3] (2 cos([[phi].sub.i1] - cos([[theta].sub.i2])) -4 cos([[phi].sub.i1] -[[theta].sub.i2])(25)

where [[phi].sub.i2] and [[theta].sub.i2] are same, as defined for the BS [right arrow] GTW communication pair in the semi-analytical model; xi2 is the angle made by the [GTW.sub.2b] [right arrow] MS communicating pair in the ith cell with the reference line of the ith cell; and [[phi].sub.i1] = [x.sub.i1] +60(i-1), is the GTW [right arrow] BS communicating pair in the ith cell with the reference line of the ith cell.

2) GTW [right arrow] BS Communication Pair in the Intended Cell:

Similarly, for the GTW [right arrow] BS communication in the intended cell, the corresponding [beta] values are:

[[beta].sub.(MS)i] = [square root of 16 + 8 [square root of 3] cos([[phi].sub.i2])] (26)

[[beta].sub.(GTW)i] = [square root of 13 + 4 [square root of 3] cos([[phi].sub.i1])] (27)

3) Capacity Bounds for End-to-End Link: The lower and the upper capacity bounds for the two communicating pairs in the uplink, GTW . BS pair, and MS [right arrow] GTW pair can be calculated in a similar manner as is done for downlink. The maximum distance of the inter-cell interferers from the receiver of the GTW [right arrow] BS pair are 1.732r and 2.732r, resulting in a maximum capacity of 3.32 bps/Hz for the GTW [right arrow] BS communicating pair. Similarly, the minimum distance of the inter-cell interferers from the receiver of the GTW [right arrow] BS pair are 0.732r and 1.366r, which results in a minimum capacity value of 0.74 bps/Hz. The minimum and the maximum capacity values for the MS [right arrow] GTW pair, assuming a constant distance of r/2 between the MS and GTW, are 0.88 bps/Hz and 3.71 bps/Hz respectively. Hence, the upper and lower bounds for the system capacity in the uplink scenario are 3.32 bps/Hz/cell and 0.74 bps/Hz/cell respectively.

4) Effect of Lognormal Shadowing on Capacity Bounds: Similar to the downlink scenario, the lognormal shadowing causes a variation in the bounds of the system capacity in the uplink scenario as well. The upper bound of the system capacity for the uplink scenario (3.32 bps/Hz/cell) experiences a variation of 25.3% for 90% of the cases in presence of lognormal shadowing of 4 dB standard deviation. Similarly, the lower bound of the system capacity (0.74 bps/Hz/cell) would vary by 27.25% for 90% of the cases.

5. Simulation Model

A simulation model for the cluster-based two-hop cellular network is developed in Matlab. An airport or a campus environment, with a total coverage area of 1 [km.sup.2] is considered in the system design. There are 19 cells within a coverage area of 1 [km.sup.2]. Hence, the distance from the centrally located BS to the edge of the cell, r, is around 130 meters. A propagation model with [k.sub.1] = 37 and a = 4 has been considered in the simulation model. 1000 MSs are uniformly distributed around this network coverage area and each cell is designed to have six clusters. All the MSs that are located in the outer layer of the cell are assigned to any one of the six clusters. This assignment is done depending on the closest distance (lowest path loss, in the presence of lognormal shadowing) of the respective MS to the six GTWs in the cell. This results in a system where there are, on an average, eight MSs per cluster. The GTWs are selected from among the MSs. The MSs selected as GTWs are located at nearly half the cell radius. The exact position of the GTW depends on the distribution of the MSs. A TDMA time frame with 16 TSs has been considered in the simulator design. The simulation model calculates the value of [gamma] and the system capacity for seven cells independently and then takes an average over these seven cells. The network is simulated for two different scenarios. In the 1st case, it is assumed that there is no shadowing. Hence, for this case, [zeta] = 0 in Equation (2). In the 2nd case, a lognormal shadowing with a zero mean and a standard deviation of 4 dB is considered [23].

For different locations of the GTWs and the MSs (with respect to the reference line), the distance of the desired receiver from the interfering transmitters would vary, which in-turn would vary the [gamma] experienced at the receiver of the communicating pair. The synchronized resource reuse technique ensures that all the interfering transmitters are spatially well-separated in distance. The exact value of [gamma], and thereby the system capacity value, however, depends on the relative distance between the receiver and other transmitting GTWs and MSs. Hence, the system capacity is plotted as cumulative distribution function (cdf) as can be seen from Section 6. The Shannon capacity obtained from the cluster-based two-hop cellular architecture is compared with the following systems:

1) A single-hop cellular network with no relaying:

There are no relays in this design. In every hexagonal cell, the BS and the MS communicate with each other in single hop, irrespective of whether the MS is located in the inner layer or outer layer.

2) A benchmark relaying algorithm for a two-hop cellular network:

The benchmark algorithms for the two-hop cellular design, introduced in [26], provides three efficient methods for finding the wireless terminals that could act as relays in order to maximize the system capacity. These benchmark algorithms could be either distance-based or path loss-based, as explained below. The path loss based algorithms take the random effects, arising due to shadowing, into account. Hence, in the presence of lognormal shadowing, the path loss based algorithms are superior to distance-based algorithms.

5.1. Distance-Based Benchmark Algorithm

In the two-hop design based on benchmark algorithms, the MSs located in the outer layer of the cell communicate to the BS in two hops, as is the case with the cluster-based model. The GTWs/ relay nodes are selected from the mobile nodes available in the network. Suppose, there are N possible two-hop routes, between the BS and the MS in the outer layer. Then, the selected route, rs, is determined, depending on the transmission distance between the BS and the relay node [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and between the relay node and the MS, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], for each of the n [member of] N routes. The three selection schemes of the standard benchmark algorithm for two-hop network [26] are given as follows:

a) shortest total distance (STD) selection scheme:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

b) least longest hop (LLH) selection:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

c) shortest relaying hop distance (SRD) selection:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

5.2. Path Loss-based Benchmark Algorithm

In addition to the distance-based benchmark algorithms, [26] also introduced the path loss-based benchmark algorithms. Let [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] denote the path losses in dB associated with the first hop (BS and relay node), and second hop (relay node and MS of the outer layer) respectively, along the nth route where n [member of] N. Then, the selected route is determined as follows:

a) minimum total path loss (MTP) selection scheme:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

b) least maximum path loss (LMP) selection:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

c) minimum relaying hop path loss (MRP) selection:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

In order to have a fair comparison, the source MSs in case of uplink (or the destination MSs in case of downlink) remain the same in all the methods, viz., the cluster-based two-hop design, the three standard benchmark two-hop schemes, and the single-hop non-relaying technique. Also, an interference avoidance model, with an optimum spatial protection margin of [DELTA] = 1.0, is considered for all the different methods. In addition, it should be noted that, in the simulation model, the increase in the overhead due to additional signaling is not considered in any of the two-hop cellular designs. This increase in the overhead in the two-hop design would cause some reduction in the capacity gain with respect to the single-hop cellular network. However, this paper focuses on the different two-hop schemes, and comparing the performance of the two-hop schemes with the single-hop design is not the main focus of this work. Also, it is expected that, the cluster-based architecture with an intelligent resource allocation technique, would require less or same amount of overhead signaling as compared to the benchmark algorithms, for the two-hop cellular network. Hence, the capacity results obtained in this work for the two-hop networks, viz., the cluster-based design and the three benchmark algorithms are directly comparable. In addition, the MSs in the inner-layer of the cluster-based design are not considered in the simulation, for any of the two-hop methods, as well as for the single-hop design. This is because, in both the cluster-based design and the three standard benchmark algorithms, the wireless terminals located in the inner-layer will communicate with the BS directly in single-hop, as in case of single-hop cellular networks. Hence, all these two-hop methods would use the same amount of radio resource for the inner-layer, and hence, the inner-layer design is not considered in this study.

[FIGURE 8 OMITTED]

6. Results

Figure 8 shows the system capacity of the cluster-based two-hop design (average of uplink and downlink results) for different values of clusters per cell. It can be observed that the system capacity shows an increase with an increase in the number of clusters per cell. However, the step size of this increase reduces with an increase in the number of clusters/cell. For example, when the number of clusters per cell is increased from two to four, the expected value of the system capacity is increased from 1.44 bps/Hz/cell to 1.85 bps/Hz/cell, an increase of 0.41 bps/Hz/cell. However, when the number of clusters/cell is increased from four to six, and six to eight, the increase in the expected value of the system capacity is only 0.378 bps/Hz/cell and 0.23 bps/Hz/cell respectively. It should be noted that this increase in the capacity value does not take into account the capacity losses arising due to the increased overhead, as the number of clusters/cell increases. Hence, in all further part of analysis, six clusters/cell are considered, as is also done in [27,28].

[FIGURE 9 OMITTED]

[FIGURE 10 OMITTED]

[FIGURE 11 OMITTED]

Figure 9 and Figure 10 shows the simulation results of the cdf of the system capacity for uplink and downlink scenarios of all different two-hop design methods, in the absence of any lognormal shadowing. The GTWs are selected from among the distributed MSs in the network. Hence, the GTWs are not located at exactly half the cell radius. It is observed in Figure 10 that in case of downlink in the two-hop cluster-based design, the median of the system capacity (2.71 bps/Hz/cell) is 2.5 times that obtained from the single-hop cellular system with no relaying (1.11 bps/Hz/cell). Similarly, the expected value of the cluster-based design is 2.52 bps/Hz/cell, which is more than twice that obtained from the single-hop cellular network value of 1.12 bps/Hz/cell. More significantly, the cluster-based design shows a superior performance over all three standard benchmark techniques for two-hop cellular network. The capacity behavior of the STD and SRD schemes are nearly similar to each other and their expected values are 1.89 bps/Hz/cell and 1.77 bps/Hz/cell respectively. Hence, the expected value of the system capacity in the cluster-based design is 0.63 bps/Hz/cell and 0.75 bps/Hz/cell better than that obtained from STD and SRD algorithms. The LLH technique provides the best performance out of the three standard benchmark techniques. The expected value of the system capacity for the LLH method is 2.05 bps/Hz/cell, which is higher than the expected value of the capacity obtained from the STD and SRD schemes, but less than the expected value obtained for the cluster-based technique by 0.47 bps/Hz/cell. Similarly, in case of an uplink as well, the expected value of the system capacity for the cluster-based design (1.82 bps/Hz/cell) is greater than the LLH method (1.36 bps/Hz/cell) by 0.46 bps/Hz/cell. In the LLH method, the node that has the minimum value among all longest hops (both between, MS and GTW node, and GTW node and BS) among all possible relay nodes is selected as a relay. Hence, a node located in the vicinity of half the cell radius is selected as a relay, which results in more than one pair utilizing the given resource simultaneously, in any cell. It should be noted that this is similar to the cluster-based design introduced in this paper. However, the significant improvement in the system capacity observed in the cluster-based design is due to the synchronized resource reuse technique proposed in this work that ensures a reuse of the radio resource in every cell. The cluster-based design provides a maximum improvement of 0.8 bps/Hz/cell over the LLH method; and up to 1.4 bps/Hz/cell improvement over the STD algorithm. Figure 11 shows the probability density function (pdf) of the mobile GTWs in the cluster-based design and that of the mobile relay nodes for the benchmark two-hop algorithms. It can be observed from Figure 11 that the pdf of the STD algorithm is almost a straight line, in the range from 0.28r to 0.74r. The SRD algorithm selects the relay that is more towards the cell edge, than at the center of the cell. Hence, the pdf of the SRD algorithm has a non-zero value only after 0.38r. A significant observation that can be made from Figure 11 is that, in case of the LLH method, the mean of the pdf is at 0.5r, same as that of the cluster-based design. Hence, the LLH method outperforms STD and SRD benchmark algorithms. However, the variance of the LLH method is 0.28r, which is twice more than that of the cluster-based design, which has a variance of 0.13r. This implies that in case of LLH method, there is a greater probability of relay nodes being not located in the vicinity of r/2, which results in only one pair in the cell being able to utilize the given resource. It should be noted that if the GTWs are selected from among the MS, then the GTW selection would depend on the distribution of MS. But still, the pattern of the GTWs would remain the same for the different benchmark methods and cluster-based design. Hence, the cluster-based two-hop model, with resource reuse in every cell, gives the best performance in terms of system capacity, as compared to the single-hop non-relaying scenario and the benchmark algorithms for the two-hop cellular network.

[FIGURE 12 OMITTED]

The performance of the cluster-based design with MSs as GTWs is then compared with the path loss-based benchmark algorithms, in the presence of lognormal shadowing. It is observed from Figure 12 and Figure 13 that, even in the presence of lognormal shadowing, the performance of the cluster-based two-hop network is superior to all three benchmark techniques, for both uplink and downlink. For example, the expected value of the system capacity for the cluster-based design is 2.18 bps/Hz/cell in case of downlink, and is 0.25 bps/Hz/cell better than LMP (the best performing algorithm among all three benchmark algorithms). Similarly, in case of uplink, the expected value of the cluster-based design is 1.98 bps/Hz/cell, and is 0.09 bps/Hz/cell better than the LMP technique. It should however be noted that, in the presence of lognormal shadowing, the performance of the LMP scheme comes close to the performance of the cluster-based design. This is because, the relays are selected not on the basis of distance measurement, but on the basis of path loss measurement, which vary with lognormal shadowing. The presence of lognormal shadowing results in MSs that are far from half the cell radius, r/2, to be selected as GTWs. As seen from the pdf of the GTW location in Figure 14, in the presence of lognormal shadowing, there is a non-zero probability for a node located beyond 0.8r, to be selected as a GTW. In the absence of lognormal shadowing, the distribution of the GTW is almost symmetric with a mean value of 0.5r. However, in the presence of lognormal shadowing, the pdf of the GTW selection exhibits a long tail, resulting in an expected value of 0.58r. This results in a situation in the cluster-based design, where the exclusion region of a communicating pair in one cell extends to the other cell, and hence, prevents the simultaneous communication of another pair in the adjacent cell. This, in turn, results in a reduction in the gain in the system capacity.

Figure 15 and Figure 16 compare the results of the cluster-based design independently for uplink and downlink, when fixed GTWs are used instead of mobile GTWs. When there is no lognormal shadowing, the expected value of the system capacity, in case of fixed GTWs, is 2.09 bps/Hz/cell (uplink) and 2.76 bps/Hz/cell (downlink) and is greater than the expected value of that obtained from the mobile GTWs by 0.27 bps/Hz/cell and 0.24 bps/Hz/cell for uplink and downlink respectively. The results observe a similar pattern even in the presence of lognormal shadowing. For example, the expected value of the system capacity in case of uplink is 2.24 bps/Hz/cell for fixed GTWs, and is greater than that of the expected value of the system capacity for mobile GTWs (1.98 bps/Hz/cell) by 0.26 bps/Hz/cell. In addition, it can be observed from Figure 15 (uplink) and Figure 16 (downlink), that the cdf obtained from the semi-analytical model shows a close match with that obtained from the simulation results for cluster-based design with fixed GTWs. The expected values of the system capacity for the semi-analytical model are 2.16 bps/Hz/cell (uplink) bps/Hz/cell for fixed GTWs, and is greater than that of the expected value of the system capacity for mobile GTWs (1.98 bps/Hz/cell) by 0.26 bps/Hz/cell. In addition, it can be observed from Figure 15 (uplink) and Figure 16 (downlink), that the cdf obtained from the semi-analytical model shows a close match with that obtained from the simulation results for cluster-based design with fixed GTWs. The expected values of the system capacity for the semi-analytical model are 2.16 bps/Hz/cell (uplink) and 2.69 bps/Hz/cell (downlink), and is very close to that obtained from the simulation results for fixed GTWs: 2.09 bps/Hz/cell for uplink and 2.76 bps/Hz/cell for downlink respectively. This is primarily because, in case of semi-analytical model, not only all the GTWs are fixed at a distance of r/2 from the center of the cell, but also all the MSs in the cluster are at the maximum distance of r/2 from the cluster-head GTWs, whereas in the simulation model for fixed GTWs, only the GTWs are fixed at a distance of r/2. Hence, the distance between the cluster-head GTW and the MSs could be any value less than or equal to r/2.

[FIGURE 13 OMITTED]

[FIGURE 14 OMITTED]

[FIGURE 15 OMITTED]

[FIGURE 16 OMITTED]

In a significant observation, the upper and lower bounds for the system capacity obtained from the simulation results is quite close to those obtained from the semi-analytical model where all the MSs were assumed to be distributed at a location of r/2 from the GTW. In downlink mode, the lower bound for capacity under the semi-analytical model is 0.21 bps/Hz/cell whereas that obtained from the simulations is 0.22 bps/Hz/cell. The upper bound for the system capacity under the semi-analytical model is 3.68 bps/Hz/cell whereas that obtained from the simulations is 2.91 bps/Hz/cell. Similarly, in the uplink mode, the lower and upper bound for the system capacity under the semi-analytical model is 0.74 bps/Hz/cell and 3.32 bps/Hz/cell respectively; whereas that obtained from the simulations is 0.82 bps/Hz/cell and 2.91 bps/Hz/cell respectively. Hence, it can be concluded that the lower and upper bound results obtained from the simulation model closely match with the results of the semi-analytical model, thereby validating the performance of cluster-based two-hop model.

7. Summary and Conclusions

In this paper, a novel resource allocation mechanism has been proposed for a two-hop cellular network. The new scheme, known as cluster-based architecture, is designed using a synchronized resource reuse technique. As per this design, each hexagonal cell is divided into two layers, the inner layer and outer layer. All MSs in the inner layer communicate with the BS in single hop, whereas, the MSs in the outer layer communicate with the BS in two hops, using a GTW terminal as relay node. This architecture design, developed under an interference avoidance Protocol Model, results in a frequency reuse ratio of one, whereby, the given resource is used twice in every cell in the system, but for only half the duration of a time slot period. This work, first, shows that the system spectral efficiency of a cellular network can be increased significantly by allowing two-hop communication. Second, it has been found that a hierarchical, co-ordinated approach which essentially means to limit the degrees of freedom for forming the two-hop links does not lower the capacity, but in fact gives higher capacity than compared to state-of-the-art two-hop algorithms. This means that the complexity of the routing problem in such two-hop communication systems can be significantly reduced while the system performance does not have to be compromised.

8. References

[1] H. Wu, C. Qao, S. De, and O. Tonguz, "Integrated cellular and ad hoc relaying systems," IEEE Journal on Selected Areas in Communication, Vol. 19, No. 10, pp. 2105-2115, October 2001.

[2] A. Zemlinanov and G. Veciana, "Capacity of ad hoc wireless networks with infrastructure support," IEEE Journal on Selected Areas in Communications, Vol. 23, No. 3, pp. 657-667, March 2005.

[3] H. Venkataraman, H. Haas, S. Yun, Y. Lee, and S. McLaughlin, "Performance analysis of hybrid wireless networks," in Proceedings of IEEE International Symposium on Personal Indoor and Mobile Radio Communications (PIMRC'05), Berlin, Germany, Vol. 3, pp. 1742-1746, 11-14 September 2005.

[4] H. W. Chen and M. Guizani, "Next generation wireless systems and networks," in John Wiley & Sons, 2006.

[5] O. Dousse, P. Thiran, and M. Hasler, "Connectivity in ad hoc and hybrid networks," in Proceedings of IEEE International Conference on Computer Communications (INFOCOM), Vol. 2, pp. 1079-1088, 23-27 June 2002.

[6] B. Liu, Z. Liu, and D. Towsley, "On the capacity of hybrid wireless networks," in Proceedings of IEEE International Conference on Computer Communications (INFOCOM), San Francisco, USA, Vol. 2, pp. 1543-1552, 30 March-3 April 2003.

[7] H. Vishwanathan and S. Mukherjee, "Performance of cellular networks with relays and centralized scheduling," in Proceedings of IEEE Vehicular Technology Conference (VTC Fall'03), Orlando, Florida, USA, Vol. 3, pp. 1923-1928, 6-9 October 2003.

[8] H. Haas and S. McLaughlin, Eds., "Next generation mobile access technologies: Implementing TDD," Cambridge University Press, ISBN: 13: 9780521826228, pp. 420, January 2008.

[9] X. Wu, S. H. G. Chan, and B. Mukherjee, "MADF: A novel approach to add an adhoc overlay on a fixed cellular infrastructure," in Proceedings of IEEE Wireless Communications and Networking Conference (WCNC'00), Chicago, USA, pp. 549-554, 23-28 September 2000.

[10] Y. D. Lin and Y. Hsu, "Multihop cellular: A new architecture for wireless communications," in Proceedings of IEEE International Conference on Computer Communications (INFOCOM) Tel Aviv, Israel, pp. 1273-1282, 26-30 March 2000.

[11] R. Ananthapadmanabha, B. S. Manoj, and C. S. R. Murthy, "Multihop cellular networks: The architecture and routing protocol," in Proceedings of IEEE International Symposium on Personal Indoor Mobile Radio Communications (PIMRC'01), San Diego, USA, Vol. 2, pp. 78-82, 30 September-3 October 2001.

[12] H. Li, D. Yu, and H. Chen, "New approach to multihop cellular based multihop network," in Proceedings of IEEE International Symposium on Personal Indoor and Mobile Radio Communications (PIMRC'03), Beijing, China, Vol. 2, pp. 1629-1633, 7-11 September 2003.

[13] Y. D. Lin, Y. C. Hsu, K. W. Oyang, T. C. Tsai, and D. S. Yang, "Multihop wireless IEEE 802.11 LANs: A prototype implementation," Journal of Communications and Networks, Vol. 2, No. 4, December 2000.

[14] V. Sekar, B. S. Manoj, and C. S. R. Murthy, "Routing for a single interface MCN architecture and pricing schemes for data traffic in multi-hop cellular networks," in Proceedings of IEEE International Conference on Communications (ICC'03), Alaska, USA, Vol. 2, pp. 969-973, 11-15 May 2003.

[15] Y. Liu, R. Hoshyar, X. Yang, and R. Tafazolli, "Integrated radio resource allocation for multihop cellular networks with fixed relay stations," IEEE Journal on Selected Areas in Communications, Vol. 24, No. 11, pp. 2137-2146, November 2006.

[16] S. Mertello and P. Torth, "Knapsack Problems, Algorithms and Computer Implementation," NewYork: Wiley, 1990.

[17] P. Gupta and P. R. Kumar, "The capacity of wireless networks," IEEE Transactions on Information Theory, Vol. 46, No. 2, pp. 388-404, February 2000.

[18] H. Venkataraman, S. Sinanovic, and H. Haas, "Variation of spatial protection margin in multihop wireless networks," in Proceedings of IEEE International Symposium on Personal Indoor Mobile Radio Communications (PIMRC'07), Athens, Greece, 3-6 September 2007.

[19] H. Venkataraman, S. Nainwal, and P. Shrivastava, "Optimum number of gateways in cluster-based two-hop cellular networks," AEU Journal of Electronics and Communications, Submitted and under review, http://nextgenwireless.daiict.ac.in/Sub_Papers/AEU_May _2008_Hrishikesh_Venkataraman.pdf, 2008.

[20] S. D. Z. Dawy and I. Oikonomidis, "Coverage and capacity enhancement of CDMA cellular systems via multihop transmission," in Proceedings of IEEE Global Communication Conference (GLOBECOM), San Fransisco, USA, pp. 1147-1151, 1-5 December 2003.

[21] 3rd Generation Partnership Project (3GPP), Technical Specification Group Radio Access Network, "Selection procedures for the choice of radio transmission technologies of the UMTS," 3GPP TR 30.03U, May 1998. Retrieved November 30, 2006, from: http://www.3gpp.org/ftp/Specs/htmlinfo/3003U.htm.

[22] J. Cho and Z. Haas, "On the throughput enhancement of the downstream channel in cellular radio networks through multihop relaying," IEEE Journal on Selected Areas in Communications, Vol. 2, No. 7, pp. 1206-1219, September 2004.

[23] IST-2003-507581 WINNER, "D7.6 winner system concept description," Retrieved July 15, 2007, from https://www.istwinner.org/DeliverableDocuments, October 2005.

[24] R. A. Fisher, "Statistical methods and scientific inference," in Oliver and Boyd, Edinburgh, 1956.

[25] I. Hacking, "Logic of statistical inference," in Cambridge University Press, Cambridge, 1965.

[26] V. Sreng, H. Yanikomeroglu, and D. D. Falconer, "Relay selection strategies in cellular networks with peer-to-peer relaying," in Proceedings of IEEE Vehicular Technology Conference (VTC Fall'03), Orlando, USA, Vol. 3, pp. 1949-1953, 4-9 October 2003.

[27] P. li, M. Rong, T. Liu, and D. Yu, "Interference modeling and analysis in two-hop cellular network with fixed relays in FDD mode," in Proceedings of IEEE Wireless Communications, Networking and Mobile Computing (WiMob), Montreal, Canada, pp. 177-182, 22-24 August 2005.

[28] T. Liu, M. Rong, H. Shi, D. Yu, Y. Xue, and E. Schulz, "Reuse partitioning in fixed two-hop cellular relaying network," in Proceedings of IEEE Wireless Communications Networking Conference (WCNC), Las Vegas, USA, pp. 177-182, 3-6 April 2006.

Hrishikesh VENKATARAMAN (1), Sinan SINANOVIC (2), Harald HAAS (2)

(1) School of Engineering and Science, Jacobs University Bremen, Germany

(2) Institute for Digital Communications, University of Edinburgh, UK

Email: [e-mail], {s.sinanovic, h.haas}@ed.ac.uk

Received April 22, 2008; revised September 1, 2008; accepted September 7, 2008