A Survey of Channel Allocation Algorithms for Wireless Local Loops

INTRODUCTION

In delivering telecommunication services, a telecommunication provider must overcome the notorious “last mile” problem, which is the final leg of delivering connectivity from a local exchange to its telecommunication subscribers. Telecommunication providers today are under mounting pressure as more subscribers are demanding services such as high-speed and high-quality Internet access, video on demand, online gaming and fast multimedia file transfer. Wireline networks intrinsically lack flexibility, making them too time-consuming and cost prohibitive to upgrade. As such, the existing wireline local loop infrastructure is unable to meet the increased service demand, causing a bottleneck in the “last mile” (Clark, 1999). Moreover, there are roughly four billion people in the world earning less than $2000.00 USD annually and living in rural or remote areas (Gao et al., 2004). Deploying the conventional wireline network for them is economically unfeasible.

A Wireless Local Loop (WLL) connects customer premise equipment to a local exchange on the Public Switched Telephone Network (PSTN) using radio signals rather than copper wires or fiber-optic cables (Hung et al., 2004; Stavroulakis, 2003; Xiao et al., 2006). A typical WLL consists of a base station, a base station controller and one or multiple subscriber terminals, as shown in Fig. 1 (Hung et al., 2004; Zhang et al., 2007). A base station, combined with a base station controller, can serve multiple subscriber terminals that are within its radio coverage (Zhang et al., 2007). Each base station has multiple radio channels which serve as the communication channels. The base station controller handles the allocation of the radio channels; it is also responsible for transcoding the source code in the wireline network and in the air-interface (Satahack and Chayawan, 2004). Each customer premise equipment has a dedicated subscriber terminal, which is responsible for the wireless communication between the customer premise equipment and its corresponding base station (Hung et al., 2004; Zhang et al., 2007).

WLL offers several advantages over the wireline local loop. First, WLL takes less time to install and deploy as there is no need for digging ducts, setting up poles, or laying wires (Lee, 1998; Lin, 1997; Noerpel and Lin, 1998). Second, WLL is less costly to operate and maintain (Arora and Maskara, 2001). Third, WLL has greater flexibility both in terms of bandwidth allocation and geographically (Stavroulakis, 2003). Finally, WLL can be easily extended, reconfigured, redeployed, adapted and is distance insensitive (Lee, 1998; Lin, 1997; Sampson, 1996; Woo, 1999). With these advantages, the WLL has the potential to be an important alternative to its wireline counterpart, especially in developing, rural, or remote areas (Xiao et al., 2006).

There are numerous channel allocation algorithms for WLLs. These channel algorithms include no repacking, always repacking, repacking on demand-random, repacking on demand-least load and repacking on demand-subscriber terminal (Zhang et al., 2007).

Fig. 1:	A typical WLL architecture (Hung et al., 2004; Zhang et al., 2007)

Choosing the channel allocation algorithm that provides the best fit from these available algorithms is one of the most important considerations for a WLL. The choice will have a significant impact not only on the WLL’s implementation complexity but also on its performance (Hung et al., 2004; Xiao et al., 2006). The purpose of this study is to provide an overview of the channel allocation algorithms for WLLs, to review related studies and to recommend future research directions. We think that the algorithm overview, the research review and the future research directions will be both informative and useful to Information Systems (IS) and Computer Science (CS) professionals.

WLL CONFIGURATION AND OPERATIONS

Here, we first briefly describe the WLL configuration. We then explain the two important operations of WLLs: overflow and repacking.

WLL configuration: The WLL divides its service area into cells; each cell is served by a base station and each base station, together with its base station controller, manages multiple radio channels (Xiao et al., 2006). A WLL can be single-tier, two-tier (e.g., macrocell and microcells), or three-tier (e.g., macrocell, microcells and picocells), based on the configuration of the cells within it (Xiao et al., 2006) and the way the base stations are populated (Hung et al., 2004). In a single-tier WLL, no two cells fully overlap each other; therefore, each subscriber terminal can be served by only one base station. In contrast, a two-tier WLL overlays every macrocell (a cell with a higher power base station) with several microcells (cells with lower power base stations); as such, a subscriber terminal in a microcell can be served either by the base station in the microcell or by the base station in the macrocell, as shown in Fig. 2 (Zhang et al., 2007).

Fig. 2:	A two-tier WLL configuration (Zhang et al., 2007)

A three-tier WLL adds another tier to a two-tier WLL by further overlaying each microcell with several picocells; as such, a subscriber terminal in a picocell can be served by the base station in the picocell or by the base station in the corresponding microcell or by the base station in the macrocell, as shown in Fig. 3 (Zhang et al., 2008).

Fig. 3:	A three-tier WLL configuration (Zhang et al., 2008)

Fig. 4:	Overflow and repacking in two-tier WLLs (Zhang et al., 2007)

WLL operations: overflow and repacking: A multi-tier (i.e., two-tier and up) WLL incorporates two new operations: overflow and repacking (Hung et al., 2004; Xiao et al., 2006). Overflow is an operation that hands off a call from a lower-tier cell to the corresponding higher-tier cell and repacking is an operation that hands off a call from a higher-tier cell to the corresponding lower-tier cell (Zhang et al., 2007, 2008). In a two-tier WLL, overflow is call handoff from a microcell to the macrocell and repacking is call handoff from the macrocell to a microcell (Fig. 4).

In a three-tier WLL, overflow is either call handoff from a picocell to the corresponding microcell or call handoff from a microcell to the macrocell and repacking is either call handoff from the macrocell to the microcell or call handoff from a microcell to the picocell (Fig. 5). In both repacking scenarios, the picocell is the cell from which the call has originated and the microcell is the corresponding cell that is overlaid by this picocell.

Fig. 5:	Overflow and repacking in three-tier WLLs (Xiao et al., 2006)

Note that a multi-tier WLL may or may not be able to perform repacking (Hung et al., 2004; Xiao et al., 2006; Zhang et al., 2007). For a WLL to be able to perform repacking, at least one repacking candidate should be available (Xiao et al., 2006). In a two-tier WLL, a repacking candidate is a call that: (1) occupies a radio channel of the macrocell and (2) the microcell of the call has an idle channel (Hung et al., 2004; Xiao et al., 2006; Zhang et al., 2007). In a three-tier WLL, a repacking candidate is either a call that: (1) occupies a radio channel of the macrocell and (2) the microcell of this call has an idle channel or a call that: (1) occupies a radio channel of the microcell channel and (2) the picocell of this call has an idle channel.

CHANNEL ALLOCATION ALGORITHMS

The channel allocation algorithms for muti-tier (e.g., two-tier and three-tier) WLLs include No Repacking (NR), Always Repacking (AR) and Repacking on Demand (RoD). Depending upon the way a WLL handles its repacking candidates in RoD (Hung et al., 2004), RoD can be further divided into three subcategories, including RoD-random (RoDR), RoD-least load (RoDL) and RoD- subscriber terminal (RoDST).

All three algorithms (NR, AR and RoD) perform overflow. A WLL with NR scheme doesn’t perform repacking (Hung et al., 2004; Rappaport and Hu, 1994). A WLL with AR scheme always performs repacking as soon as a repacking candidate becomes available (Beraldi et al., 1996; Maheshwari and Kumar, 2000; Steele et al., 1990). In contrast, a WLL with RoD scheme only performs repacking when it is necessary (Hung et al., 2004; Xiao et al., 2006). Each of the three subcategories of RoD, i.e., RoDR, RoDL and RoDST, handles the repacking candidates differently.

Here, we study channel allocation algorithms for two-tier and three-tier WLLs by applying a decision-tree approach. A decision-tree approach is both appropriate and useful. It is appropriate because a WLL has to make conditional decisions when performing call overflow or repacking (Xiao et al., 2006). It is also useful because: (1) the generated decision-trees can help us better understand these channel allocation algorithms and (2) we can use the generated decision-trees in the construction of the simulation model and the implementation of the simulation program to evaluate the performance of the different algorithms (Xiao et al., 2006).

No Repacking (NR): A WLL with an NR scheme performs overflow, but does not perform repacking (Hung et al., 2004; Rappaport and Hu, 1994). When a new call arrives, a multi-tier WLL with an NR scheme always tries to allocate an idle channel in the lowest-tier cell (e.g., a microcell for two-tier WLLs or a picocell for three-tier WLLs) to the call. If some idle channels are found, the WLL assigns one of the idle channels to serve the call. Otherwise, the call overflows to the next adjacent higher-tier cell and so on. Finally, if the WLL cannot find an idle channel for the overflowed call at the highest-tier cell (e.g., the macrocell for both two-tier and three-tier WLLs), then the call is blocked (Fig. 6, 7) (Xiao et al., 2006; Zhang et al., 2007).

Always Repacking (AR): A WLL with an AR scheme performs both overflow and repacking. More precisely, a WLL with an AR scheme always performs repacking as soon as a repacking candidate becomes available (Beraldi et al., 1996; Maheshwari and Kumar, 2000; Steele et al., 1990).

Fig. 6:	No repacking scheme for two-tier WLLs (Zhang et al., 2007)

A multi-tier WLL with an AR scheme always hands off a call in the higher-tier cell back to the next adjacent lower-tier cell as soon as an idle channel becomes available in the corresponding lower-tier cell (Hung et al., 2004; Xiao et al., 2006; Zhang et al., 2007). In doing so, AR maintains the maximum number of idle channels in the higher-tier cells (e.g., the macrocell for two-tier WLLs and the macrocell and microcells for three-tier WLLs).

An interesting finding is that the decision-tree for AR scheme is the same as that for the NR scheme. The reason for this is surprisingly simple. When an overflowed call cannot find an idle channel in the higher-tier cells (e.g., the macrocell for two-tier WLLs), repacking will not succeed because if there were repacking candidates available at higher-tier cells at that very moment, the WLL itself, due to its use of an AR scheme, would have already performed the repacking. Intuitively, compared with a WLL with an NR scheme, a WLL with an AR scheme is expected to have a lower blocking rate but a higher handoff rate (Lagrange, 1997).

Repacking on Demand (RoD): Similar to AR, a WLL with a RoD scheme also performs both overflow and repacking. However, unlike AR, which performs repacking as soon as a repacking candidate becomes available, RoD performs repacking only right before a new call is to be blocked (Hung et al., 2004).

The overflow process of a WLL with a RoD scheme is identical to a WLL with an NR or AR scheme. The difference is that the WLL will try to perform repacking when the WLL cannot find an idle channel for the overflowed call at the highest-tier cell (i.e., the macrocell for both two-tier and three-tier WLLs). Repacking in a two-tier WLL is straightforward. If repacking candidates exist, the WLL will hand off one of the repacking candidates back to its corresponding microcell from the macrocell.

Fig. 7:	No repacking scheme for three-tier WLLs (Xiao et al., 2006)

Fig. 8:	Repacking-on-demand scheme for two-tier WLLs (Zhang et al., 2007)

Then the reclaimed macrocell channel is used to serve the new call. Otherwise, the new call will be blocked (Fig. 8) (Hung et al., 2004; Zhang et al., 2007).

Repacking in a three-tier WLL, however, is rather complex. According to Hung et al. (2004) and Xiao et al. (2006), the repacking steps are as follows. First, the WLL checks whether there are repacking candidates in the macrocell. If so, the macrocell picks one of the repacking candidates and hands it off to its corresponding microcell. The reclaimed macrocell channel is used to serve the new call. Second, if the macrocell fails to find a repacking candidate, the WLL checks whether there are repacking candidates in the corresponding microcell of the call. If so, the microcell of the call will perform repacking and the reclaimed microcell channel is used to serve the new call. Third, if the corresponding microcell of the new call fails to find a repacking candidate, the WLL checks whether there are repacking candidates among other microcells that also have call(s) being served by the macrocell channel(s). If so, the WLL performs repacking first at that microcell, then at the macrocell and finally allocates the reclaimed macrocell channel to serve the new call. Finally, if all the above steps have failed to locate an idle channel, the new call is blocked (Fig. 9).

Fig. 9:	Repacking-on-demand scheme for three-tier WLLs (Xiao et al., 2006)

The decision-trees of RoDR, RoDL and RoDST are the same. The only difference between RoDR, RoDL and RoDST is the way they choose the repacking candidates. However, this difference does not impact the appearance of the decision-tree as shown in Fig. 9. With RoDR, the base station controller randomly selects a repacking candidate for handoff; with RoDL, the base station controller selects the repacking candidate whose microcell (or picocell) has the least traffic load and with RoDST, subscriber terminals make the repacking candidate selection and handoff decision, upon a repacking request from the macrocell (Hung et al., 2004; Xiao et al., 2006). Note that more than one call may be handed off in RoDST. In this case, one of the released channels is chosen to serve the new call (Xiao et al., 2006).

PAST STUDIES

In the last decade, there have been numerous studies on the WLL and its channel allocation algorithms (Arora and Maskara, 2001; Gao et al., 2004; Hung et al., 2004; Lin, 1997; Noerpel and Lin, 1998; Stavroulakis, 2003; Woo, 1999; Xiao et al., 2006; Zhang et al., 2007, 2008). We concentrate on two recent studies which represent the latest research on this subject. One is Hung et al. (2004)’s analytic model and simulation study of the channel allocation algorithms for two-tier WLLs; the other is Xiao et al. (2006)’s simulation study of the channel allocation algorithms for three-tier WLLs.

In their study, Hung et al. (2004) first developed an analytic model and then a simulation model to compare the performance of the different channel allocation algorithms (i.e., NR, AR and RoD) in terms of the blocking probability Pb (defined as the number of blocked calls / [the number of successful calls + the number of blocked calls]) and handoff probability Ph (defined as the number of call handoffs / [the number of successful calls + the number of call handoffs]). They showed, with both the computation from their analytic model and results from their simulation experiments, that (1) RoD has the same Pb as AR, (2) AR and RoD have lower Pb but higher Ph than NR, (3) RoD has much lower Ph than AR when the WLL is engineered at Pb = 2% and (4) RoDL has the lowest Ph among the three subgroups of RoD (i.e., RoDR, RoDL and RoDST).

In their study, Xiao et al. (2006) first presented and then analyzed channel allocation algorithms for the three-tier WLL by using a decision-tree approach. They then investigated the blocking probability Pb and the handoff probability Ph of these algorithms by simulation. Their study showed that (1) given the same set of simulation parameters, NR has the highest Pb, AR has the lowest Pb and the Pb of RoD falls in between, (2) compared with NR, both AR and RoD reduce Pb at the cost of a higher handoff rate and (3) among RoDR, RoDL and RoDST, RoDST has the lowest Pb but the highest Ph.

FUTURE DIRECTIONS

Drawing upon the overview of channel allocation algorithms for WLLs and the review of the related studies, we propose the following three future research directions, including (1) a comparison study, (2) a quest for optimal N and (3) an impact analysis of mobile subscriber terminals.

A comparison study: Hung et al. (2004) performed a simulation study of the channel allocation algorithms for two-tier WLLs. Xiao et al. (2006) performed a simulation study of the channel allocation algorithms for three-tier WLLs. It would be interesting to do a performance comparison study of the different channel allocation algorithms between two-tier and three-tier WLLs.

A quest for optimal N: A two-tier WLL can be obtained by overlaying the cells in a single-tier WLL. Similarly, a three-tier WLL can be obtained by overlaying the cells in a two-tier WLL. Using the same technique, an N-tier WLL can be obtained by overlaying an (N-1)-tier WLL. The promise of multi-tier WLL is more efficient channel utilization (Hung et al., 2004). However, when N gets larger, the complexity of WLL implementation may overtake the benefits that a multi-tier WLL can offer. An interesting research question is which value of N will provide optimal performance for an N-tier WLL.

An impact analysis of mobile subscriber terminals: Although, the WLL typically provides fixed-to-fixed connections (Woo, 1999), some argue that demand for mobility may become greater once initial demand for basic fixed service has been fulfilled (Swasey, 1998). It would be interesting to study the impact on the performance of the WLL with the different channel allocation algorithms given that all subscriber terminals are mobile. For instance, they can move in all directions at a variety of speeds crossing different cells. This will further complicate call handoffs as well as call overflow and repacking, which will impact the performance of WLLs.