Resource Allocation Using Load Matrix Concept For Wireless Cellular Systems

Resource Allocation Using Load Matrix Concept For Wireless Cellular Systems

P. P. Wagp, N. M. Kazi2, S. R. Suralkar3

(SSBTs College of Engineering and Technology, Bambhori, Jalgaon, Maharashtra, India)

Abstract

The demand of higher bandwidth and data rates has been increased substantially during recent years. This has made it important for future mobile cellular systems to implement an efficient resource allocation scheme to achieve the current demands. In order to achieve efficient resource utilization in all sorts of deployment scenarios and QoS requirements in the future wireless cellular systems, new resource allocation methods must be developed. The resource allocation has to provide optimum or near optimum, for practical reasons, utilization of the available radio spectrum in the next generation of cellular wireless systems regardless of deployment scenarios and conditions. A variety of resource allocation strategies and schemes, mainly for downlink, is developed in past. A system with multiple traffic classes was considered and resource allocations were based on the specific characteristics of traffic flows resulting in minimization of power consumption or maximization of system capacity. Under mixed service traffic including both real-time and non- real time services, efficient resource allocation from a shared resource pool is a challenging task due to varied and stringent QoS requirements.

Several interference reduction techniques have been suggested in past and proved to be effective in reducing the interference to some extent and thereby increase system capacity. But, in a highly loaded system, the problem of intercellular interference remains an important issue. Thus, the intercellular interference problem of scheduling process is to be overcome by introducing a new and efficient resource allocation strategy called Load Matrix (LM). The proposed algorithm is to evaluated with existing resource allocation for performance evaluation. The suggested algorithm is to be developed on Matlab tool for its realization.

Key words :QoS, Load matrix

1. Introduction

   The importance of resource scheduling was appreciated with the support of high data rate services in the evolution of UMTS standard to High Speed Downlink Packet Access (HSDPA) and Enhanced Uplink [2]. A variety of resource allocation strategies and schemes, mainly for downlink, can be found in references [3]-[8].A system with multiple traffic classes was considered and resource allocations were based on the specific characteristics of traffic flows resulting in minimization of power consumption or maximization of system capacity.

   Under mixed service traffic including both real-time and non-real time services, efficient resource allocation from a shared resource pool is a challenging task due to varied and stringent QoS requirements. In [4], a fixed resource partitioning method in which total resource pool was partitioned between different service classes and independent resource schedulers were responsible for each resource partition whereas in [5], scheduling was more unified and partitioning was dynamic to enhance spectral efficiency. Another approach towards resource allocation, called utility based approach, tries to maximize the total network utility and thereby enhancing resource allocation. For example, pricing is a well-known utility function used in for resource allocation. In QoS is used as users utility function and then convert the resource allocation problem into a non-cooperative game where each user tries to maximize its own utility. A downlink resource allocation method based on dynamic pricing was proposed in [8] aiming to maximize the summation of users utility. On the link level, adaptive transmission is one of the most recent technologies being investigated for enhancing the spectral efficiency in future cellular systems [9].Fast scheduling together with adaptive modulation-coding, facilitates exploitation of channel variations resulting in multi-user diversity gains. This approach takes advantage of instantaneous channel conditions of different users where the channel fading are relatively independent. Adaptive transmissions are more effective for low mobility users compared with fast moving users channel.

   Uplink resource allocation methods can be categorized as centralized or decentralized in terms of the network location/ node in which scheduling takes place.In Universal Mobile Telecommunications System (UMTS), if the scheduler resides in Radio Network Controller (RNC),it is called centralized and if it resides in base station it is called decentralized.

2. Problem outline

   In an UMTS, the uplink cell capacity is basically limited by the total received uplink power at the base station due to the transmit power limitation of user terminals. In decentralized scheduling, each base station assigns radio resources to its users on a priority basis until the estimated Rise over Thermal noise (RoT) level reaches a pre-defined target. Recent studies in Enhanced Uplink UTRA (HSUPA),shows that the decentralized scheduling has better performance compared with centralized one [2].In the performance of centralized packet scheduler of the UMTS system is evaluated while in the performance of a decentralized scheduling is evaluated and compared with the centralized one in. The basic advantage of decentralized over centralized approach is due to its fast response to dynamic and fast varying environment of mobile systems for resource allocation. But, the decentralized scheduling algorithms have an inherent shortcoming, due to their vulnerability to intercell interference. In other words, considerable proportion of RoT at the base station is made up from multiple access intercell interference which the base station has little knowledge about or control upon. This in turn may lead the system to interference outage and poor resource utilization particularly when interfering cells have similar traffic load variations. Antenna beam forming, and their combinations have been extensively proved to be effective in mitigating interference to some extent and thereby increase system capacity.

   In a highly loaded system, the problem of intercell interference remains an important issue and MUD with Minimum Mean Square Error (MMSE) detection MMSE-MUD is recognised as an effective interference suppression technique for increasing the system capacity. But it has been demonstrated that MMSE-MUD performs approaches that of a single user band in a fully loaded system. Although intercell interference problem is more severe in decentralized scheduling, it is also present in centralized scheduling due to the fact that the intercell interference impact of a scheduled user is not known and therefore has not been considered by the central scheduler. In this intercell interference problem of scheduling process addressed by introducing a new and efficient resource allocation

   strategy called Load Matrix (LM). In order to prove the concept, HSUPA system is used as a case study.

   It should be noted that although HSUPA system is used to demonstrate the performance of the Load Matrix, the concept is generic for single- carrier spread spectrum based systems where cell RoT is widely used as a good load indication directly linked to cell load. In multi-carrier systems, the load on subcarriers can differ significantly and therefore RoT (averaged) is no longer a good measure for load over all subcarriers.The introduction of effective SINR in multicarrier systems to provide a better and more accurate link system mapping.

3. Wireless communication

   <>The current and emerging wireless communication systems make use of diversity in their design: a classic and well-known concept that has been used is multipath fading. To increase the overall signal- to-noise ratio (SNR), is one of the greatest potential for radio link performance improvement to many of the current and future wireless technologies. There are several ways in which one can provide the receiver with a L-order diversity as follows:

   1. Space diversity

      This technique can be easily implemented at the base stations, and does not require extra radio spectrum occupancy.

   2. Frequency diversity

      This form of diversity is obtained by sending the same signal over different frequency carriers, whose separation should be larger than the coherence bandwidth of the channel.

   3. Time diversity

      The same information bearing signals are transmitted in different time slots separated by an interval longer than the coherence time of the channel, time diversity can be obtained.

4. Load matrix concept

   One of the main challenges in resource allocation in multicell system is the control of intercell interference. In uplink scheduling, the basic problem is to assign appropriate transmission rate and time to all active users in such a way that result in maximum radio resource utilization across the network whilst satisfying the QoS requirements of all the users. Amongst other constraints, another important factor in the resource allocation is the users transmit power. For network of M users and N cells the constraints to be satisfied are Cnst1 : For each active user i in the network, its transmit power Pi must be maintained in an acceptable region defined as

   0 Pi P,max I {1,.,M} (I)

   Pi,max is the maximum transmission power available to the user due to hardware limitation and any other restrictions. Cnst2 : The total received power at base station should be kept below a certain threshold for all N base stations in the network (as a load control measure in a single-carrier Spread Spectrum system). We use Rise over Thermal noise (RoT) as defined in HSUPA to represent the interference constraints. RoTj is the total in-band received power at the base station j BSj) over thermal noise. Let N_ be the receiver noise power in a BS, Pi be the transmission power of user i and Gi,j be the channel gain from user i to BS j. For M active users in the network, RoTj can be written as

   ROTi (II)

   In this case Cnst2 can be formulated as

   RoTj RoT target J {1,.,N} (III)

   where RoTtarget is assumed to be a fixed target value set by the network operator to maintain the uplink interference level. Cnst3 : For each user, depending on its channel type (e.g. pedestrian, vehicular) and speed, each rate k has a minimum required SINR called SINRtarget,k. SINRtarget,k is the signal to noise plus interference ratio required at the serving base station j if rate k is being assigned to the user in order to achieve a given block/frame error rate. Rate k . {1, · · ·,K} is the highest rate acceptable (and therefore is the preferred rate) for user i with serving base station j if SINRtarget,k is the highest that can be achieved under both Cnst1 and Cnst2

   SINR i,j SINRtarget,k i {1,.,M}, k {1,,K} (IV)

   Load Matrix (LM) can be regarded as a database containing the load factors of all active users in the network. LM scheduling can be implemented in both centralized and decentralized strategies. In a decentralized LM scheduling, each base station should implement identical LM database. For simplicity, it only present the centralized LM scheduling where a central scheduler entity assigns radio resources to all the users in the network.

   Here assume the averaged channel gain (over the scheduling period) from users to base stations is known to scheduler prior to rate assignment. In a network of M users and N cells, LMi, j is the load factor contributed by user i at BS j

   LM i,j = (V)

   From the LMi,j values stored in column j of LM database, RoT of cell j can be written as

   RoTj (VI)

   Note that RoTj obtained from (VI) is identical to RoTj definition given in (II). Let BS j be the serving base station for user i which controls users transmission power and Gi, be the total channel gain from user i to BS j averaged over scheduling period. SINRi, j can be written as

   SINRi,j = (VII)

   Let pi,k be the required transmit power for user i should it be assigned the rate . Starting with the highest applicable rate from the set (i.e. k = K), for rate k to be assigned to user i, (IV) must be satisfied. Therefore the minimum required SINRi, j is SINRtarget,k . Also recall the aim of LM rate assignment to keep RoTj always as close as possible (ideally equal) to RoTtarget. By rearrangement of (VII), replacing SINRi,j with SINRtarget,k, Pi with pi,k , and RoTj with RoTtarget, required transmit power for user i (should it be assigned rate k) can be found as

   Pi,k (VIII)

   However, rate k and consequently pi,k is acceptable if and only if all three constraints are satisfied. First of all, pi,k obtained from (VIII) must satisfy Cnst1 which states the maximum users transmit power. Cnst3 constraint is already satisfied by considering SINRtarget,k. as SINRi, j. Additionally, pi,k must satisfy the Cnst2 which takes into account the impact of assigning rate k to user i on the intercell interference. This ensures the intercell interference caused by user i in other cell does not increase other cells RoT above RoTtarget. In order to check this, next step is to update LMi,n for all the elements in row i of Load Matrix. LMi,n is the load factor imposed by user i in cell n using rate k defined as

   LMi,n = (IX)

   From (VI) one can estimate the new RoT for all other cells and check if the Cnst2 constraint has been satisfied. If so the rate k is the highest acceptable rate for user i and will be assigned, otherwise the same process is repeated for the rate k-1 and so on. If at the end, none of the rates k . {1,

   • · ·,K} can satisfy the three constraints, user i will not be scheduled for transmission at this scheduling instant and will be given higher priority for the following scheduling instant. After the first round of rate assignment to all users, LM elements are updated and new RoT is calculated for each cell using (VI). This is necessary because (VIII) and

   (IX) are valid only if RoT is close to the RoTtarget. Since the rate assignment is an NP-complete problem (see section 5), it is not possible to exactly achieve RoTtarget in all cells in the first round of rate assignment. This requires additional rounds (which we refer to it as iterations) of rate/power adjustments in order to minimize the difference between a cell RoT and its RoTtarget. In other words, at each scheduling instant, pi,k is iteratively adjusted in (VIII) and then (IX) by replacing RoTtarget with updated RoT from LM in (VI) after each round of rate assignment. This check is an important step ensuring low probability of interference outage by keeping RoT below RoTtarget and at the same time increasing resource utilization with highest cell RoT possible (i.e. RoT close to RoTtarget). Obviously the number of iterations depends on the difference between RoT and RoTtarget at the end of each scheduling process. However, the simulation results presented in section V are with no iteration and yet the difference between RoT and RoTtarget was found to be negligible. It should be noted that if a user is not in the full buffer status, the maximum rate index K in (IV) is limited to a rate that would result in emptying the buffer at the next scheduling instant. Cell or network throughput per bandwidth (bps/Hz/cell) is often taken as resource utilization measure. However, there is a trade off between maximum cell throughput and fairness amongst users (VIII). Priority functions are used to rank users in the scheduling process and make a balance between cell throughput and fairness. Commonly used pririty functions are Round Robin, DL SINR, Max C/I on the other hand, ranks users in terms of their channel quality and aiming for maximizing cell throughput at the expense of fairness. Both Proportional Fair and Score-based functions performance are better than Round Robin in terms of throughput and better than Max C/I in terms of fairness. Load Matrix concept, provides a generic solution for resource scheduling that does not preclude any priority function and can be combined with any of them. The priority function has major impact on overall system performance for any

   scheduling algorithm including the LM. Here a priority function is introduced based on a users load vector that includes intra and intercell impact on the network. It is evident that giving priority to a user with better channel condition increases the cell throughput but in a multicell network could have severe impact on the throughput of other cells. Here it is considered by defining Global Proportional Priority function as

   Priorityi = (X)

   where Gi,j is the total channel gain from user i to BS j averaged over the scheduling period. The LM approach tries to maximize network capacity through inter and intracell interference management. The first step of LM algorithm is initialization where all the LM elements are set to zero and also users in each cell are sorted according to the priority function in (X). The LM allocation process simultaneously increases allocated resources in each cell to avoid interference imbalance amongst the cells. The process consists of a number of assignment rounds equal to the maximum number of users per cell (e.g. 10 rounds for 10 users per cell). In each round, the LM assigns rates to the highest priority user in each cell, updates LM elements and performs capacity checking. Capacity Check (CC) function calculates RoT as in (VI) and compares with RoTtarget making sure (III) is always satisfied. Passing this check means assigned rates are valid and will not cause interference outage. If CC fails, scheduler attempts the next available rate and continues until CC is satisfied. Then the user is considered scheduled and will be removed from the user priority list of its serving cell. The scheduling process continues until all the users are processed

5. Resource allocation strategy

   The aim of resource allocation in wireless cellular system is to assign radio resources to individual users in a way to achieve maximum system capacity whilst meeting the required quality of service. In this section, the resource allocation problem in wireless cellular system formulated and show that it is an NP-hard problem [13]. A resource allocation is used to assign transmission rate and time to individual users with the objective of throughput maximization. To analyze the problem, begin with the single cell scenario and then extend the conclusion to the multi-cell case. Without loss of generality, assume that transmission rates are chosen from a limited set of rates. Let Si,1 denote Candidate Rate Set (CRS) of user i, which includes

   all the allowed transmission rates for the user to choose from rate 0 is always included in Si,1, and will be chosen if the user is not scheduled to transmit in the current scheduling instant. The transmission rates in different CRSs as different items even if they have the same rate value:

   Si,1 S j,1 = (XII)

   Let S1 denote the union of all the CRSs from Si,1 to SM1,1, and M1 is the total number of users in the cell sharing the radio resource pool. Choose an element t from set S1 is an assignment action, which means allocating a specific transmission rate to a particular user. Each assignment action generates a certain amount of throughput while consumes some amount of the cell capacity. Use binary variable xt to indicate whether element t is chosen or not (1 for Yes and 0 for No). pt and ct,1 denote the generated throughput and consumed cell capacity respectively if element t is chosen. pt is equal to the transmission rate, whereas ct,1 can be interpreted differently, e.g. as consumed BS transmit power or generated load factor [12], depending on the system type. Using above terms and definitions, the Single Cell Radio Allocation Problem (SCRAP) can be described as follows: a particular system given(cell capacity, user location, propagation and traffic status etc.), how to choose elements from set S1 in each scheduling instant so as to achieve maximum system throughput, subject to the following two constraints: C1 : The aggregated cell capacity consumption of all the chosen elements from S1 should be less than the total available cell capacity Cap1. C2 : for each CRS (S1,1 , SM1,1), only one element is chosen. Mathematically, SCRAP can be formulated as follows:

   Maximize: p = pt xt (XIII)

   t s1

   subject to :

6. Design approach

   In this thesis consider 3 users communicating with the base station. The base station transmitter receives the digital message data of all the users asynchronously and process it for transmission. After this block, the message data will be transferred to the channel. We will consider this channel as an AWGN. At the receiver end the data will be processed through demodulator and MUD blocks and the actual message data will be retrieved at the end of the receiver.

7. Result observations

   The result for different offered load at different channel characteristic was observed. The quality metrics such as throughput, communication delay, and power allocation are evaluated. The obtained observation illustrated that the developed methodology for resource allocation based on the channel raise of thermal can improve the performance of the suggested system as compared to the existing method. The performances were observed to be improved and the evaluation is carried out for different level of system load.

   Figure1. : Throughput value in first evaluation

   Figure2.:Throughput value in second evaluation

   Figure 4. : Plot of power alloction

   Figure 3.: Throughput value in third evaluation

   Figure 5.: Plot of system throughput

8. Conclusion

   For the implemented design the simulation were performed for different case study. The result for different offered load at different channel characteristic was observed. The quality metrics such as throughput, communication delay, and power allocation are evaluated. The obtained observation illustrated that the developed methodology for resource allocation based on the channel raise of thermal can improve the

   performance of the suggested system as compared to the existing method. The performances were observed to be improved and the evaluation is carried out for different level of system load. The observation illustrates that as the number of users added where the conventional method takes larger time for computation and processing, due to network overhead, the proposed method improves the performances for different offered load.

9. Future scope

   This work focus on the development of a resource allocation algorithm for wireless channel based on the raise of thermal (RoT), this work can be incorporated with the other scheduling scheme such as frequency and time slotting for the efficient usage of the resource in the channel.

10. References

1. Mohammad Abaii, Yajian Liu, and Rahim Tafazolli,

   An Efficient Resource Allocation Strategy for Future Wireless Cellular Systems, IEEE Transactions on wirelwss communications, Vol. 7, No. 8, AUGUST 2008.

2. 3GPP TR 25.896, Feasibility Study of Enhanced Uplink for UTRAFDD V6.0.0, Mar. 2004.

3. I. B. Kim and M. L. Honig, Resource allocation for multiple classes of DS-CDMA traffic, IEEE Trans. Veh. Technol., vol. 45, no. 6, pp. 506-519, May 2000.

4. M. Ono, Y. Matsunaga, M. Momona, K. Okanoue,

   A proposal of all-IP mobile wireless network architecture QoS packet scheduler for base stations, Tech Rep. IEICE, MoMuC2002-3, 002-05.

5. S.Abedi, Efficient radio resource management for wireless multimedia communications: a multidimensional QoS-based packet scheduler, IEEE Trans. Wireless Commun., vol. 4, no. 6, pp. 28112822, Nov. 2005.

6. Joon Bae Kim, Student Member,IEEE, and Michael

L. Honig, Fellow, IEEE Transactions on Vehicular technology, Vol. 49, NO. 2, MARCH 2000.

[7]A. Florea and H. Yanikomeroglu, On the optimal number of hops in infrastructure-based fixed relay networks," in Proc. IEEE Globecom, St. Louis, MO, Nov. 2005.

[8]M. Shabany, K. Navaie, E. S . Soma, Downlink resource allocation for data traffic in heterogenous cellular CDMA networks, in Proc. ISCC 2004, vol. 1, pp. 436441, July 2004.

1. M. Sternad, S. Falahati, T. Svensson, D. Aronsson,

   Adaptive TDMA/OFDMA for wide-area coverage and vehicular velocities, in Proc. 14th IST Mobile & Wireless Communications Summit, Dresden,Germany, June 2005.

2. M. Shabany, K. Navaie, E. S . Soma, Downlink resource allocation for data traffic in heterogenous cellular CDMA networks, in Proc. ISCC 2004, vol. 1, pp. 436441, July 2004.

[11]T.S. Rappaport, Wireless Communications Principles and Practice, 2nd edition. Prentice Hall PTR, 2002.

1. H. Holma and A. Toskala, WCDMA for UMTS: Radio Access for Third Generation Mobile

   Communications, second edition. John Wiley & Sons, 2002.

2. M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP- Completeness. New York: Freeman.

3. Hannes Ekström, Anders Furuskär, Jonas Karlsson, Michael Meyer, Stefan Parkvall, Johan Torsner, and Mattias Wahlqvist, Ericsson The High Speed Packet Data Evolution of WCDMA, Proc. IEEE PIMRC 2001, vol. 2, Sept. 2001, pp. G27-31.

4. T. Ottosson and A. Svensson, Multi-rate schemes in DS/CDMA systems, in Proc. IEEE VTC, vol. 2, Chicago, IL, July 1995, pp. 10061010.

5. 3GPP R1-031004, Example of Rel-99 TFC control algorithm, Qualcomm Europe, www.3gpp.org, Oct. 2003.

6. Hannes Ekstr/:om et al., Technical solutions for the 3G long-term evolution, IEEE Commun. Mag., pp. 3845, Mar. 2006.

[18]Y. Ofuji, S. Abeta, A. Morimoto,and M. Swahashi,Comparison ofpacket scheduling algorithms focusing on user throughput in high speed downlink cketaccess,IEICETrans. Commun.,vol. E86-B, no. 1,pp.132139,Jan.2003.

[19]On the performance of hybrid genetic packet scheduling andchannel assignment under imperfect reporting conditions in HSDPAsystem, in Inf. Society Technologies (IST) Summit, Aveiro, Portugal,2003, pp. 10991103.

[20]A genetic approach for downlink packet scheduling in HSDPASystem, Soft Comput. J., Special Issue on Soft Computing Applicationsto CDMA Power Control Optimization, vol. 9, no. 2, pp. 116127,Feb. 2005.

1. T.-H. Wu and E. Geraniotis, CDMA with multiple chip rates for multi-media communications, in Proc. Information Science and Systems, Princeton, NJ, 1994, pp. 992997.

2. D. Imbeni and M. Karlsson, Quality of service management for mixed services in WCDMA, in IEEE Vehicular Technology Conf. (VTC)Fall,Boston, MA, 2000, vol. 2, pp. 565572.

3. 3GPP TR 25.848, Physical layer aspects of UTRA High Speed Downlink Packet Access V4.0.0, Mar. 2001.

4. Mikael Sternad*, Sorour Falahati*, Tommy Svensson, and Daniel Aronsson Adaptive TDMA/OFDMA for Wide-Area Coverage and Vehicular Velocities Signals and Systems, Uppsala University,

PO Box 528,SE-751 20 Uppsala, Sweden.