在寬頻多重分碼存取環境中(Wideband Code Division Multiple Access；WCDMA)，為了提供使用者不同速率頻寬的服務，使用正交可變展頻因子(Orthogonal Variable Spreading Factor；OVSF)碼。正交可變展頻因子碼在分配的過程中可能會產生碎裂問題，包含內部碎裂(Internal fragmentation)與外部碎裂(External fragmentation)；本篇文章處理內部碎裂的問題。當分配出去的傳輸率比要求的速率還要高時，會產生內部碎裂，為降低內部碎裂，一般是以多重碼(Multi-Code)的方式解決，即同一時間用許多較小的碼來支援進來的要求，本篇在解決內部碎裂問題時使用的是單一碼(Single-Code)的方式，將要求的速率分割成數個二的指數次方之速率，這些分割好的速率分別在不同的時間裡被服務，並且因此達到降低內部碎裂的效果。本論文提出最短切割與動態切割兩種方式；最短切割將每個呼叫以最少的切割數分好；動態切割則視碼樹上可被分配碼的情況來使用。模擬結果顯示，比較各種解決內部碎裂的方法，最短切割和動態切割在內部碎裂指數與平均完成時間上的表現較佳。

The use of OVSF codes in WCDMA systems can provide variable data rates to flexibly support applications with different bandwidth requirements. The data rates provided by the OVSF codes are exponentially quantized since the spreading factors are exponentially decreased. One important issue when using the OVSF codes is the internal fragmentation problem which happens when the provided data rate is larger than what is requested. The precious wireless bandwidth is wasted if there is internal fragmentation. In this paper, we try to solve the internal fragmentation problem using one single OVSF code per connection. If the amount of the requested data rate is known, we can partition the request into several subrequests which can be exactly served by OVSF codes. This eliminates the internal fragmentation completely. We also consider the time issue when solving the internal fragmentation problem. To guarantee that every user can meet his/her deadline, a scheduling mechanism is needed. We proposed several partition, code assignment and scheduling schemes in this paper. The goal is to remove internal fragmentation for delay-sensitive services. Simulation results verify that the proposed schemes avoid internal fragmentation and reduce user’s waiting time concurrently.

1	緒論	1
1.1	研究動機	1
1.2	研究目的	3
1.3	各章提要	4
2	背景知識與問題陳述	5
2.1	正交可變展頻因子碼	5
2.2	問題陳述	11
3	頻寬速率切割法	13
3.1	切割次數	13
3.2	允入控制(Admission control)	14
3.3	服務使用者的方法	15
3.3.1	最短切割	15
3.3.2	動態切割	20
4	效能分析	25
4.1	模擬結果	30
5	結論	39

圖目錄
圖一 正交可變展頻因子碼樹的二元樹結構圖..............................6
圖二 使用(a)FCFS與(b)Best-fit方法之比較..........................................9
圖三 五層的正交可變展頻因子碼樹圖..............................................18
圖四 傳輸速率總和至32R的呼叫之狀態圖.......................................26
圖五 各方法的(a)內部碎裂指數(b)平均完成時間(c)平均更動頻率32
圖六 呼叫速率偏小的(a)內部碎裂指數(b)平均完成時間(c)平均更動
頻率...........................................................................................33
圖七 呼叫速率偏大的(a)內部碎裂指數(b)平均完成時間(c)平均更動
頻率..............................................................................................35
表目錄
表一 最短切割處理排程表 ..................................................................20
表二 動態切割處理排程表........................................................24
表三 不同的總頻寬速率之下狀態的個數..........................................27
表四 四種方法的比較.......................................................29

[1]	A. Rouskas and D. Skautas. “OVSF code assignment and reassignment at the faward link of W-CDMA 3G systems.” In Proc. of IEEE PNRC 2002, vol. 5. pp. 2404-2408.
[2]	C.-M. Chao and S.-H. Wang. “Joint Code/Time Assignment Strategies with Minimal Fragmentations for CDMA Systems”. WCNC, 2006.
[3]	C.-M. Chao, Y.-C. Tseng, and L.-C. Wang. “Dynamic Bandwidth Allocation for Multimedia Traffic with Rate Guarantee and Fair Access in WCDMA Systems”. IEEE Trans. on Mobile Computing, 4(5):420–429, 2005.
[4]	C.-M. Chao, Y.-C. Tseng, and L.-C. Wang. “Reducing internal and external fragmentations of OVSF codes in WCDMA systems with multiple codes”. IEEE Trans. On Wireless Communications, 4(4):1516 – 1526, 2005.
[5]	E. Dahlman, B. Gudmundson, M. Nilsson, and J. Skold, “UMTS/IMT-2000 Based on Wideband CDMA,” IEEE Comm. Magazine, vol. 36, pp. 70-80, Sept. 1998.
[6]	F. Adachi, M. Sawahashi, and H. Suda, “Wideband DS-CDMA for Next-Generation Mobile Communications Systems,” IEEE Comm. Magazine, vol. 36, pp. 56-69, Sept. 1998.
[7]	F. Adachi, M. Sawahashi, and K. Okawa, “Tree-Structured Generation of Orthogonal Spreading Codes with Different Lengths for Forward Link of DS-CDMA Mobile Radio,” Electronic Letters, vol. 33, pp. 27-28, Jan. 1997.
[8]	H. Holma and A. Toskala, WCDMA for UMTS. John Wiley & Sons, 2000.
[9]	J.G. Proakis, Digital Communications. McGraw-Hill, 1995.
[10]	Third Generation Partnership Project, Technical Specification Group Radio Access Network, Spreading and Modulation (FDD), http://www.3gpp.org, 1999.
[11]	T. Minn, K.Y. Si" “Dynamic Assignment of Orthogonal Variable Spreading Factor Codes in W-CDMA”. IEEE Journal an Selected Areas in Communications, Val. 18, No. 8, August 2000, pages 1429-1440.
[12]	T.S. Rappaport, Wireless Communications: Principles and Practice. Prentice Hall, 1996.
[13]	V.K. Garg, IS-95 CDMA and cdma2000. Prentice Hall, 2000.
[14]	Y.-C. Tseng and C.-M. Chao. “Code Placement and Replacement Strategies for Wideband CDMA OVSF Code Tree Management”. IEEE Trans. on Mobile Computing, 1(4):293–302, Oct.-Dec. 2002.