OVSF code assignment strategies with minimal fragmentations for WCDMA systems☆
Introduction
It is expected that higher-bit-rate services such as file transfer and QoS-guaranteed multimedia applications will be supported in the next-generation (3G or beyond) systems. To support these higher and variable data rate services, two transmission schemes are proposed: multicode-CDMA (MC-CDMA) and Orthogonal Variable Spreading Factor CDMA (OVSF-CDMA). In MC-CDMA, multiple Orthogonal Constant Spreading Factor (OCSF) codes can be assigned to a user [12], [13]. The maximum data rate a user can receive depends on the number of transceivers in the device. In OVSF-CDMA, a single OVSF code is assigned to each user. Higher data rates are provided by using lower spreading factors.
OVSF codes can be represented as a binary code tree [1]. The data rates provided by OVSF codes are always powers of two with respect to the lowest basic rate, . Thus, the possible rates that are supported are: , , , , etc. Since the gap becomes larger as the rate increases, in some cases capacity waste is inevitable. For instance, a call requiring a rate of may be given a code where capacity is wasted. The wasted capacity increases as the spreading factor decreases. This is called the internal fragmentation problem [6]. To relieve the internal fragmentation problem and better utilize the scarce wireless bandwidth, one solution is to use multiple (smaller) OVSF codes to support a call. For example, a call requesting rate can be supported by a code and an code. This direction has been explored in [6], [9], [10], [19]. However, using multiple codes implies higher hardware cost. In this paper, we consider another direction: use a single-code and adopt the time-sharing concept to solve the internal fragmentation problem. Time-sharing allows two or more low-rate requests to share a high-rate code. For example, two calls requiring rates of and may share a code without wasting any capacity. If we can choose suitable users to share a large-rate code, capacity waste can be reduced significantly.
Besides the internal fragmentation problem, while connections are arriving and leaving the system, an OVSF code tree may become too fragmented to support new arrival calls even if there are sufficient spaces in the code tree. This is referred to as the external fragmentation problem. A possible solution to this problem requires intelligent code assignment which addresses how to assign code(s) to a new call in the code tree to avoid the tree becoming too fragmented. It is shown in [6], [20] that code assignment plays a very important role in system utilization.
In this paper, we formulate the fragmentation problem to be a “multiple knapsack problem” and propose solutions. When handling internal fragmentation, selecting users to be supported by a single OVSF code can be mapped to a single knapsack problem. When applying code assignment to solve the external fragmentation problem, it turns out to be a multiple knapsack problem since all available codes in the code tree come into play.
The rest of this paper is organized as follows. In Section 2, we introduce our system model. Section 3 defines the problem and presents the proposed code allocation algorithms. Performance analysis is in Section 4. Section 5 shows the simulation results. Conclusions are given in Section 6.
The OVSF code management problems in WCDMA systems have been widely studied. In the literature, solutions to this problem can be classified depending on two factors:
- •
single-code/multicode: whether a user can simultaneously utilize multiple OVSF codes or not.
- •
dedicated/shared: at each transmission time unit1, whether a code can be time-shared by multiple users or not.
In Table 1, we categorize existing solutions and the solutions proposed in this paper based on such classification.
The OVSF code assignment strategy, though playing an important role in system performance, is not explicitly addressed in the current 3G standard. Most works in the literature [3], [7], [8], [11], [14], [15], [16], [20], [21], [23] fall under the single-code, dedicated class. One OVSF code is exclusively assigned to one client at each transmission time unit. Intelligently assigning codes to calls, such as crowded-first strategy [20] and non-rearrangeable compact assignment strategy [23], can reduce code blocking. When the code tree is used for a long time, it is inevitable that the code tree will become fragmented because of calls arriving and leaving the system. In such a situation, code reassignment is a way to increase system utilization. Dynamic Code Assignment (DCA) [16] is the first scheme that is designed for this issue. Whenever a code reassignment is needed, DCA is able to find the minimal-cost branch that produces the least number of code reassignments. A scheduling protocol [14] assigns OVSF codes to users on a time_slot-by-time_slot basis. Each user is initially assigned a leaf code. The scheduling algorithm would allow a user to utilize any ancestor code of his/her assigned code. When multiple users want to use the same code, the user with more credits wins. The problem with this protocol is that it does not consider the changeable link conditions which may prohibit a user from using some ancestor codes. A dynamic code assignment algorithm that aims to improve channel utilization for bursty traffic is proposed in [3]. OVSF codes are allocated to bursty traffic sources according to their peak rates. However, these bursty sources do not always transmit at peak rates. When they have fewer packets to transmit, another type of traffic, best effort traffic, is allowed to utilize the unused bandwidth to increase system utilization. In [3], [14], [16], a call can be moved to a different code. That is, codes can be considered as shared between users from a long-term perspective. However, for each individual time unit, each allocated code is still dedicated to one call and thus, internal fragmentation problem remains.
Some solutions [5], [6], [10], [19], [22] allow a user to occupy multiple but dedicated OVSF codes. Such solutions are more flexible, but have higher hardware costs. The works in [10], [19] discuss the number of codes to be assigned to a requested data rate. However, the exact positions of allocated codes are unspecified. The tradeoff between hardware cost and bandwidth utilization can be found in [6]. Strategies for code placement and replacement are also proposed in this work. In [22], a multicode scheduling scheme to be run on the base station is proposed to fairly share the resources. This fair scheduling scheme does not address the code placement issue. Scheduling algorithms that consider both code placement issue and multistate link conditions can be found in [5]. The results show that, with smart code allocation and scheduling, both rate guarantee and fair access can be achieved even in an environment with time- and location-variant link conditions.
There are solutions in the single-code, shared category. A time multiplexing mechanism to share OVSF codes among different users is proposed in [2]. Each transmission time unit of an OVSF code is partitioned into a number of time slots which can be assigned to different users. The utilization of OVSF codes can be improved through code sharing. However, both code allocation strategy and which users can share a particular code are not addressed in [2]. Moreover, to keep orthogonality, only a single layer of OVSF codes can be shared in this mechanism. This means that all of the allocated codes must have the same data rate. Such inflexibility limits its functionality. Based on the same time-sharing concept, another work that groups users to share codes can be found in [4]. Each group is allocated a subtree such that the data rate of the subtree is no less than that of the summation of the group members. The main task of the work is to find appropriate number of time slots (group cycle time) to support all users in a group. When a group is formed, the authors provide solutions (determining group cycle times) to satisfy all of the group members’ requirements. The deficiencies of the work, such as how to form a group and which code should be shared, are still left unanswered.
In this paper, we seek a total solution for the fragmentation problem. Both code assignment and user selection issues are addressed. When the code and users are selected, the solution proposed in [4] can be adopted to fulfill the slot allocation among users.
Section snippets
System model
In the OVSF-CDMA system, OVSF codes are used to spread the information that multiplies every data bit by an OVSF code to form a spread code sequence. The length of the OVSF code is called the spreading factor (SF). OVSF codes are also used to separate signals from the same base station. The possible OVSF codes can be represented by a code tree as shown in Fig. 1. Each OVSF code is denoted by , where SF and k () are the spreading factor and the branch number, respectively. The number
Challenge and solution
In this section, we first describe the challenge of using time-shared OVSF codes and then define the problem to be solved in this paper. Afterwards, we will present our proposed solutions.
Performance analysis
We established an analytical model to evaluate the performance of the different user selection schemes (i.e., FCFS and best-fit). The metrics are bandwidth utilization and call blocking probability. To simplify our analysis, the users arrive and request for data rates of 1, 2, or 4. Although the maximum transmission rate is set to 4, our analytic results can be easily extended to higher transmission rates. Note that since we analyze the performance of different user selection schemes
Simulation results
We have implemented a simulator wherein more general call patterns with varied channel conditions are applied in order to evaluate the proposed strategies. The max SF of the code tree is set to 256. New calls arrive in a Poisson process. Calls request for rates uniformly distributed between and . Call duration is exponentially distributed with a mean of 4 time units. Using the QPSK modulation, we model the symbol error probability bywhere and
Conclusions
Resource management is an important issue for WCDMA systems since wireless bandwidth is a precious resource. In this paper, we define the fragmentation problem that considers a user’s multistate channel condition. To solve this problem, two issues (code assignment and user selection) must be addressed and we have proposed two algorithms for each issue. From our proposals, the large-code-first code assignment scheme performed well. As to the user selection, the best-fit scheme is better in terms
Acknowledgement
This research is supported by the National Science Council, ROC, under grant NSC96-2221-E-019-015-MY2. The author thanks Shih-Han Wang for collecting part of the simulation results.
Chih-Min Chao received the BS and MS degrees in computer science from Fu-Jen Catholic University and National Tsing-Hua University in 1992 and 1996, respectively, and the PhD degree in computer science and information engineering from National Central University in January of 2004. He was with SENAO International in 1996. He was an assistant professor at the TamKang University, Taiwan, from 2004 to 2005. Since 2005, he has been an assistant professor with the Department of Computer Science and
References (23)
Non-blocking OVSF codes and enhancing network capacity for 3G wireless and beyond systems
Computer Communications
(2003)- et al.
Tree-structured generation of orthogonal spreading codes with different lengths for forward link of DS-CDMA mobile radio
Electron. Lett.
(1997) - Carl E. Fossa, Jr. Dynamic code sharing algorithms for IP quality of service in wideband CDMA 3G wireless networks....
- et al.
Adaptive time-sharing based grouping code assignment in mobile WCDMA networks
IEEE PIMRC
(2005) - et al.
Dynamic bandwidth allocation for multimedia traffic with rate guarantee and fair access in WCDMA systems
IEEE Transactions on Mobile Computing
(2005) - et al.
Reducing internal and external fragmentations of OVSF codes in WCDMA systems with multiple codes
IEEE Transactions on Wireless Communications
(2005) - et al.
Efficient OVSF codes assignment strategy and management architecture in wideband CDMA
IEEE First International Conference on Broadband Networks
(2004) - et al.
A novel code assignment scheme for W-CDMA systems
IEEE VTC 2001 Fall
(2001) - R.-G. Cheng, A code managemant mechanism for WCDMA mobile communication networks, in: International Workshop on Mobile...
- et al.
OVSF code channel assignment for IMT-2000
IEEE VTC 2000 Spring
(2000)
Multiple access protocol for integration of variable bit rate multimedia traffic in UMTS/IMT-2000 based on wideband CDMA
IEEE Journal on Selected Areas in Communications
Cited by (4)
RA-OABC: An Optimal Framework for Resource Assignment in WCDMA Networks Using Oppositional Artificial Bee Colony Algorithm with Repair Strategies
2018, Wireless Personal CommunicationsGraph model for optimal OVSF code placement strategies
2012, International Journal of Ad Hoc and Ubiquitous ComputingReducing wastage capacity in OVSF based CDMA networks using dynamic rake combiners
2011, WSEAS Transactions on CommunicationsGraph model for OVSF code placement
2010, 2010 5th International Conference on Future Information Technology, FutureTech 2010 - Proceedings
Chih-Min Chao received the BS and MS degrees in computer science from Fu-Jen Catholic University and National Tsing-Hua University in 1992 and 1996, respectively, and the PhD degree in computer science and information engineering from National Central University in January of 2004. He was with SENAO International in 1996. He was an assistant professor at the TamKang University, Taiwan, from 2004 to 2005. Since 2005, he has been an assistant professor with the Department of Computer Science and Engineering, National Taiwan Ocean University, Taiwan. His research interests include mobile computing and wireless communication.
- ☆
A preliminary version of this paper has been accepted by IEEE WCNC, 2006.