2.1.3          Distributed Measurement (DM)

The channel allocation methods in the non-measurement quadrant depend strongly on the compatibility matrix.  However, most publications assume the compatibility matrix is given or that the interference neighbourhood is defined.  In constructing the compatibility matrix, the reuse distance can be found either by measurements or by estimation using an appropriate propagation model.  In a typical network, the cell radius may be different, and hence the interference neighbourhood for each base station may be different and needs to be defined prior to network operation.

If the cell radius is constant in a network as in Figure 1.1 the reuse distance will be the same for all base stations and thus the interference neighbourhood is the same for all base stations.  However, the number of co-channel cells still needs to be considered in order to construct the compatibility matrix and to determine the SIR.  Let B_Cj be the set of K nearest co-channel base stations of b_j in the first ring of interferers.  The worst case SIR (i.e. at the edge of the cell), considering only the first ring of co-channel interferer, is calculated using:

where, P_RX is the received power at b_j from a subscriber at the edge of the cell, P_INT is the total received interference power, P_k is the received power from a subscriber in b_kÎ B_Cj (base station k), R_b is the cell radius, R_u is the reuse distance and z is the path loss exponent.  For example, if K = 6 and z = 3.8, a cluster size N_c = 7 would give a SIR of 17dB.  However, if the cumulative interference from the 2^nd and 3^rd ring of co-channel cells are also considered the SIR may drop by 1dB thereby underestimating the reuse distance .  Shadowing and fast fading may alter the instantaneous received and interference power by up to 10 dB (if no averaging is undertaken).  On the other hand, not all co-channel base stations use the same channel at once.  If there are only 2 co-channel base stations using the same channel, it is possible to use the same channel closer than the worst case reuse distance since the total interference power may still meet the required threshold SIR thereby packing the channels tighter.  Hence, a compatibility matrix considering the worst case (i.e. all 6 co-channel interferers) may have over estimated the reuse distance leading to a bigger interference neighbourhood and an optimal solution requiring a higher C_MIN.  Only FCA using the Tabu Search [24] considers the cumulative interference but the compatibility matrix is still static (i.e. it considers the worst case scenario).  It is shown in [46] using simulation and numerical methods, that the reuse ratio  for a FCA using a static compatibility matrix (i.e. one that caters for the worst case scenario) is higher than that of a DCA method using measurement (e.g. DECT, PHS and CT2).  The reuse ratio also changes according to the traffic pattern giving a different compatibility matrix, which leads to a different optimal solution for each traffic pattern.  The optimal solution for the worse case scenario is hence similar to the optimal solution in the non-measurement methods.

In addition to having a static compatibility matrix, non-measurement methods may not cope in a system operating in an unlicensed band.  The network may satisfy all compatibility matrix requirements but there is no allowance for avoiding an interferer from a foreign network.

Instead of estimating the reuse distance prior to network operation, measurements of the interference power or SIR can be performed by the base station or the subscriber unit to evaluate the interference environment during network operation.  With measurement, the system can judge whether using a particular channel is able to satisfy the required SIR.  Using measurement the network obtains the most current channel usage thereby achieving higher channel packing (i.e. the compatibility matrix is now dynamic) and can avoid interference from a foreign network if the system uses an unlicensed band.  Without any centralisation, the DCA algorithms in this category are simple and easy to implement.  However, measurements cause delay which translates to slow call setup in a voice network or lower data throughput in a data network.  Also since each base station has only local knowledge (via measurements) of the network, it is difficult to achieve the optimum solution and the channel selection is usually used to benefit itself rather than for the network as a whole. 

The accuracy of measurement is not perfect and may be affected by the duration that the measurement is performed on a specific channel, how often it is performed and the quality of the equipment used (e.g. frequency synthesiser switching speed).  A more accurate measurement can be obtained from a synchronised system since specific time slots can be used by the base stations to transmit pilot tones while the subscribers (or other base stations) perform measurements [61].  It is shown in [57], that a synchronous system performs better than an asynchronous system and the difference is higher in a TDD system.  Blind spots  [57] can happen where one unit (e.g. subscriber unit or base station) is performing a measurement and another unit is not transmitting (e.g. the second unit also performing measurement, is switching frequency or is in a guard time slot), thereby causing the first unit to “miss” the second unit.  This may cause the same channel to be selected by both units thereby interfering with each other.

2.1.3.1       Least Interfered (LI) Method

The most popular DCA in this class is the Least Interfered  (LI) method.  This method is used in the DECT [47] and CT2 (cordless telephone equipment) [48] systems.  In LI, the base station or subscriber measures the interference power of all available channels and selects one with the least interference power [49], [50], [52], [53], [56].  In [50] LI is used in a “quasi-fixed” channel assignment, where channel assignment is periodically performed off-line (e.g. at night when traffic is low) or whenever there are changes to the interference environment (e.g. the addition of new cells).  An iterative process is used, where in each iteration, the base stations take turns to measure the interference and select a channel using LI while the others transmit (i.e. only one base station performs measurements at a time).  Using LI, a channel is selected one at a time and a final channel assignment is obtained when no base station changes its channel after two consecutive iterations or when a specified number of iteration is reached.  This process can be automated and is able to achieve an acceptable assignment within five iterations.  Hence, it uses less resource than FCA (using a priori planning) but central coordination is required to ensure only one base station performs measurement at a time.  For a distributed version, the base station performs measurement at a random time and if the measurement is performed quickly, the probability of more than one base station performing a measurement is low.

When a new call uses a channel, it will change the interference environment and may cause interference for existing users, changing their desired SNR especially in a system using power control.  As LI ignores the required SNR, the call admitted using LI might not have an acceptable SNR.  This newly admitted call could also jeopardise the existing calls.  Channel probing is proposed in [51], where a subscriber selects a channel using LI and tests this channel prior to using it.  Here, the base stations are synchronised and power control is used.  The channels are divided into FCA and DCA channels.  A new call will be assigned to an FCA channel, and the subscriber will test a selected channel by transmitting at a specified time.  As the base stations are synchronous, the existing subscribers using this channel can measure the interference change and adapt to it using power control.  The new call will then check to see if the changed interference is acceptable.  The FCA channels are also used as a buffer such that whenever an existing call cannot meet its SNR requirements, it can use a FCA channel while probing for another channel.  Power control also improves the performance of LI and the simulation performed on a one-dimensional network in [66] shows that LI with power control has a lower call blocking probability than one that does not use power control (i.e. pure LI).

2.1.3.2       Threshold Based DCA

LI doesn’t differentiate whether a channel will provide an acceptable SNR, the channel is selected simply if it is the least interfered channel.  There are a group of DCA algorithms that consider whether a call has acceptable SNR.  These DCA algorithms are called threshold based DCAs, where the algorithm selects a channel based on a predefined interference threshold.  The interference threshold is determined from the required SNR and the signal power of a subscriber at the corner of a (hexagonal) cell.  Examples of such algorithms are the Least Interference below Threshold Algorithm (LTA), the Highest Interference below Threshold Algorithm (HTA), the Marginal Interference Algorithm (MIA) and the Lowest Channel below Threshold Algorithm (LCA) [52], [53].  In LTA, the least interfered channel below a threshold is selected to ensure that only tolerable interference is accepted.  HTA selects the highest interfered channel that is below a threshold and this encourage high channel packing as the co-channel base stations are made closer together.  MIA is a hybrid of HTA and LI that tries to achieve higher channel packing and maintain good signal quality.  MIA is same as HTA if the measured interference is below a threshold otherwise it selects the least interfered channel (similar to LI).  LCA selects the lowest numbered channel that is below a threshold and it tries to pack the channel as closely as possible.  In these algorithms, the threshold is important since if the interference threshold is set too low (i.e. high signal quality) more calls will be blocked, since this is difficult to achieve.  On the other hand, if the interference threshold is set too high (i.e. low signal quality), this may result in uneven channel utilisation for a threshold based DCA that encourages channel packing (e.g. HTA, MIA and LCA).  Channel utilisation  is defined as the number of base station using a specific channel and in a highly utilised channel, the base stations/subscribers will experience a higher interference level compared to those in a lower utilised channel.  It is shown in [52], that LI is able to achieve even channel utilisation and in the “quasi-fixed” system using the technique described in [50] (where the base station performs the measurements and they are synchronised) convergence to a stable channel assignment is guaranteed (assuming that each measurement correctly finds the least interfered channel).  LI also consistently performs better – in terms of signal quality (SNR) and call blocking probability – compared to the threshold based DCAs (LTA, HTA, MIA and LCA) in both a quasi-fixed and in a DCA system [52], [53].  The performance of LTA approaches that of LI at a high interference threshold but degrades at a low interference threshold.  The performance of MIA is opposite to that of LTA – performance approaches LI at a low interference threshold and degrades at a high interference threshold.  In light traffic, HTA and LCA have a performance approaching LI at a low interference threshold and degrade at a high interference threshold.  However, in heavy traffic, the performance of HTA and LCA peak at a moderate interference threshold and degrade at both low and high interference thresholds.  The performance of MAXAVAIL is compared with LI in [53] where shadowing, fading and the received signal strength of each call are considered.  In most publications, which evaluate DCA methods in the non-measurement class, the simulation results presented ignore the received signal quality and the propagation model (where shadowing can change the signal strength by 10dB) since they assume that the compatibility matrix will ensure that the SNR threshold is met.  In [53], it is shown that LI performs better than MAXAVAIL and that the MAXAVAIL performance is comparable to LI only at light traffic loading and a high reuse factor (e.g. 19).  Simulations in [53] conclude that DCA methods that try to achieve high channel packing (e.g. HTA, LCA and MAXAVAIL) perform worse than DCA methods that try to minimize interference.

Instead of using interference power as in LI, an estimate of the SIR/SNR can be used.  Using SIR/SNR the system can immediately determine whether a call using a specific channel is acceptable and unlike in an interference threshold based DCA the task of pre-defining an interference threshold is eliminated.  However, SIR/SNR is difficult to estimate.  When a mobile subscriber selects a base station for a call, it measures the signal strength of several base stations and usually selects the base station with strongest signal strength.  In [54] the mobile also measures the interference power of all the channels and using the signal strength from the selected base station, it can compute the downlink SNR.  The mobile requests permission from the base station to use the channel with the highest SNR.  The base station will estimate the uplink SNR and will use this channel if both downlink and uplink SNR are above a threshold.  This is a crude way of estimating the SNR since the signal strength from the base station or mobile also contains interference power and it is difficult to separate interference from the signal.  Apart from SIR and interference power, the error rate in the packets can also be used.  For example, in the Cellular Digital Packet Data (CDPD) used in AMPS to provide a data service, the block error rate (BLER) is used instead of SIR and is continuously monitored [55].

A SIR threshold based DCA (Marginal SIR) similar to the MIA is introduced in [56].  As in MIA, the Marginal SIR selects the highest SIR channel not exceeding a predefined threshold and if the SIR exceeds the threshold, the lowest SIR channel exceeding the threshold is selected.  Marginal SIR is compared with LI and RND using various SIR thresholds for the Marginal SIR algorithm.  The 1-percentile SIR (1% SIR) performance – in the Cumulative Distribution Function (CDF) – shows that RND performs the worst and over a specific range of SIR thresholds, Marginal SIR performs (1% SIR) better than LI.  As described previously, the performance of MIA in [52] and [53] can approach that of LI, albeit that a different performance measurement is used.  Hence a well defined threshold can have a significant effect on the performance of a threshold based DCA.

In a measurement based DCA, the base station has an advantage over the subscriber’s unit in measuring interference.  Firstly, the base station is usually located at a higher position and the interference (from other base stations) measurement will be less likely to be affected by shadowing [50].  Secondly, better equipment can be used at the base station (since it is more costly to put such equipment into every subscriber’s unit).  However, the uplink and downlink may experience different levels of interference especially for a TDD system.  A balanced-DCA method is proposed in [57] whereby the base station and subscriber perform the measurements.  In this method, the base station measures the interference of all the channels and selects N_s lowest interfered channels.  The list of N_s channels is passed to the subscriber unit.  The subscriber measures the interference power of the best channel in the list and estimates its downlink SNR.  If the downlink SNR is above a threshold, the subscriber will transmit a request using this channel to the base station, where the base station will estimate the uplink SNR of the channel.  If both downlink and uplink SNR are above a threshold, the channel is selected otherwise the next channel in the list is considered.  Each channel is given several trials before proceeding to the next channel in the list.  Simulations performed in [57] show the proposed DCA method performs better than a DCA method where either the base station or the subscriber alone performs the measurements.  This method was also compared with a FCA method for both non-uniform and uniform traffic distributions and the results show that the DCA method has lower blocking probability than FCA for a range of offered traffic levels (in Erlangs) [58].  FCA is designed for the worse case scenario and consequently for those calls that are admitted (SIR above threshold) the quality (SIR performance) of these calls are slightly better than those when using DCA.

2.1.3.3       Priority Based DCA

The LI algorithm and the threshold based DCA algorithms described previously require the base station or subscriber units to measure the interference power of all the available channels.   This takes a long time causing delay at the call setup and lowering the data throughput in a data network.  Rather than going through all the channels, the First Available  (FA) DCA [59] takes the first channel in a list that meets the threshold requirement.  Evaluation of the SIR and interference autocorrelation  over time gives a measure of the changes in SIR and interference respectively (e.g. after measurements) and it is found that reducing the call setup delay increases these autocorrelation values [59].  This means that the interference measured at the start of a call will experience greater changes (during the actual call) if the call setup delay is high.  Simulations performed in a packet data network in [59] show that FA has a higher SIR and interference autocorrelation than LI.  However, FA outperforms LI (in SIR performance) only over a range of low SIR values and at higher measuring rates, LI out performs FA.  It is also found that in a circuit switched network, the call setup delay has little effect on the SIR/Interference autocorrelation.  In [62] FA-SIR selects the first channel that has a SIR above a defined threshold.  If all the base stations consider each channel in the same order (e.g. from lowest numbered channel to the highest numbered channel), the lower numbered channels will be highly utilised.  Thus, each base station would have to spend time measuring these highly utilised channels (the lower numbered channels) in order to get to the less utilised channels (i.e. the higher numbered channels).  This can be avoided if each base station considers the channels in a different order. 

A priority based DCA is used to avoid spending time measuring highly utilised channels prior to reaching a good channel (as happens in FA) by assigning a priority (e.g. a value) to each channel.  The channels are ordered according to their priorities, such that the highest priority channel is considered first for assignment.  Each base station keeps a different list of ordered channels and in this way, the problem experienced in FA is avoided.  This idea is similar to that employed in most Non-measurement Centralised (up to interference neighbour) methods such as Simple [32] and Geometric [33] DCAs.  A Channel Segregation (CS)  scheme is introduced in [60] where each base station assigns priorities to the channels through learning from experience.  The base station performs a measurement and selects the first channel in the list that has a measured interference power below a predefined threshold.  No a priori knowledge is required, since the channels are arranged during network operation (the initial order can be random or may follow the channel number).  Each base station maintains an ordered list of channels and the priority of each channel is updated using the following:

Where P_Cj is the priority value of channel j, N_A is the number of times this channel is successfully used and N_T is the number of times this channel is considered for use (i.e. being measured).  However, as each base station has only local information of the network, the system will converge to a sub-optimal ordered channel list.

A different priority based DCA using a staggered frame is introduced in [61], for a TDMA data network where each base station transceiver maintains a priority ordered channel (a time slot and frequency) list.  The base stations are synchronised and grouped so that a staggered frame method is used for the subscribers to estimate the SIR.  TDMA is used where in each time frame only one base station in the group is allowed to assign a channel.  This base station broadcasts a paging signal to its mobile stations and then turns off its transmitter.  This is followed by a pilot tone transmitted by the rest of the base stations in the group.  Pilot tones are transmitted only for channels (i.e. time slot and frequency) that are being used.  The mobile stations use the paging signal and the pilot tone to estimate the downlink SIR for each channel.  This staggered frame method also avoids blind spots in the measurement.  Using a similar method to balanced-DCA [57], the mobile station estimates the downlink SIR of several channels and sends a list of channels that have acceptable quality (downlink SIR above a threshold) to the base station.  The base station assigns the highest priority channel in the list given by the mobile station with acceptable quality to the mobile station.  The channel priority is updated after each channel assignment, where the first channel having an acceptable quality (i.e. downlink SIR > threshold) is swapped with the first channel failing to meet the threshold criteria.  The staggered frame DCA has a better SIR performance than CS but only a comparable SIR performance to that of LI (with subscribers performing interference power measurements).

Channel reassignment is included in a priority based DCA in [62].  Two such methods are proposed namely DCA with Weighted Channel Ordering (DCA-WCHN) and DCA with Weighted Carrier Ordering (DCA-WCAR).  In DCA-WCHN the priority of a channel (time slot and frequency) is proportional to the number of times it has been successfully used in a similar manner to that in CS.  In DCA-WCAR, the priority is given to each carrier (frequency) rather than channel (combination of time slot and frequency) and it is proportional to the number of active time slots in it.  The base station performs the measurement and only acceptable channels are used (i.e. SIR > threshold).  In DCA-WCHN the highest priority channel that is acceptable is selected for use, while in DCA-WCAR the first time slot in the highest priority carrier that is acceptable is selected.  In both methods, channel rearrangement is implemented such that when a call is released, it is the highest priority channel which is released.  This is the opposite of what is done in non-measurement methods and the rational is that the next call will have a higher chance of using a high priority channel.  This method is compared with LI and First Available SIR (FA-SIR).  In a synchronous system, DCA-WCHN has a slightly lower call blocking probability than LI, while FA-SIR has an inferior call blocking probability to LI, with DCA-WCAR having the worst performance.  However, in an asynchronous system, LI has the lowest call blocking probability while DCA-WCHN has the worst call blocking probability.  LI performance is consistent but it has the highest call set up delay.  A DCA method combining LI and priority based DCA (DCA-LSWO – limited search with weight/priority ordering) is introduced in [62] where the number of channel measurements is limited to a specific number and channel priority ordering is used to compensate for the smaller number of measurements.  DCS-LSWO performs marginally better than LI in an asynchronous system.

In [63] a threshold based DCA method is proposed for application to a Packet Reservation Multiple Access (PRMA) protocol in a packet data network.  In this method, the base station estimates the SIR of all unused slots by measuring the interference power of the unused slots and taking the received signal power as that of the reservation packet from the subscriber unit.  Rather than using an ordered channel list, the base station selects a slot out of K slots at random starting from the first unused slot that has a SIR above a predefined threshold.  The value K is decreased if the packet is transmitted successfully otherwise it is increased.  By taking a random slot rather than using the first available slot this method avoids the problem faced by FA where different base stations will all begin by searching the lower numbered slots (or channels) that are highly utilised.

2.1.3.4       Other Methods

A permission probability method is introduced in [64] to allocate timeslots in a Packet Reservation Multiple Access (PRMA) protocol applied to a packet data network for a voice service.  A low permission probability slot will be less likely to be acquired by a subscriber and vice-versa for a high permission probability slot.  The permission probability is dependent upon the interference of the slot and a measure of the traffic intensity.  The measured interference determines the link quality while the traffic intensity determines the number of packet collisions.  The traffic intensity is estimated by measuring the rate of occupied slots.  A high value is given to the permission probability if both interference and traffic intensity are low, while a low value is given if interference and traffic intensity are high.  Fuzzy logic  is used to determine the degree of interference and traffic intensity and the combination of these two functions gives the permission probability.  This Fuzzy-DCA method was compared with RND and LI.  The SIR performance of LI is better than that of Fuzzy-DCA, but Fuzzy-DCA has a lower packet dropping probability (i.e. receiving a packet that has a SIR below a threshold) compared to that in LI.  RND has the worst SIR and packet dropping probabilities.