OVSF碼保留分配算法研究

楊愷

【摘要】提出1種為每類呼叫預留資源的信道化碼分配算法。將新算法與已有的單一分區法、混合分區法1、混合分區法2等保留算法進行比較,計算機仿真表明,分區借碼法在公平性和碼阻塞率方面最好,是公平和吞吐量最好的保留算法。該算法簡單、有效和公平，可應用于以OVSF碼作為信道化碼的各種DS-CDMA系統。

【關鍵詞】直接序列擴頻碼分多址正交可變長擴頻因子保留分配算法

直接序列擴頻碼分多址是當今移動通信系統空中接口的重要技術，是實現無線多媒體通信的關鍵。它采用正交可變擴頻因子（OVSF）碼作為信道化碼，正交性的限制與碼資源有限導致了碼阻塞[1]現象。碼阻塞降低了碼資源的利用率，還使大部分碼資源被低速率呼叫搶奪，使分配過程對高速率呼叫不公平。對用戶而言，碼分配算法應對各種速率的呼叫都公平對待。現有的單一分區法中全部的碼資源由各類呼叫獨立占用，發生阻塞時各區域剩余的資源不能共享;混合分區法中資源的共享程度不夠充分，且總有利于高速率呼叫。本文提出的分區借碼法可以將“最空閑”的資源分配給“最有需要”的呼叫，吞吐量更大，分配更公平。

一、OVSF碼和保留分配算法

如圖1所示，碼樹的每個節點表示1個OVSF碼。1個OVSF碼可以用其所在層的層號k（k=0，1，2，…K）和層中所處的位置號n（n=1，2，…N）完全確定，記為（k，n）。若碼a是由上層的碼b派生的，則a是b的子碼，b是a的父碼。由上層某個碼派生的本層相鄰的2個碼互為兄弟碼。被分配出去的碼稱為忙碼。因其父碼或子碼是忙碼而不能被分配的碼稱為禁碼。其余的稱為空碼。有時系統的容量足以支持新呼叫請求的速率，但由于被占用的碼分布較分散，被禁用的碼較多，無法找到與呼叫請求的速率對應的碼，不得不阻塞此呼叫，這種阻塞稱為碼阻塞。碼阻塞降低了碼資源的利用率，造成系統資源浪費。

按照算法的目的分類，可分為①以減少碼阻塞為目的（從系統的角度）的單碼分配算法和多碼分配算法；②以公平分配為目的（從用戶的角度）的保留分配算法。

1.1單一分區算法

按照各速率呼叫的發生概率，將碼樹分為無重疊的若干區域，每個區支持一種速率，區數等于速率類型數,使所有速率的呼叫的阻塞率趨同。例如，對于各速率呼叫的個數比為1R:2R:4R:8R=8:4:2:1，稱之為速率模型A，容量比為1:1:1:1，對碼樹進行等容量分區[2]，各區的碼個數之比為8:4:2:1，如圖2。

但是，單一分區法下碼樹并不總能精確地按照各速率呼叫的發生概率來劃分，并且分配過程中各速率呼叫的發生概率比例會有變化，事先劃分好的每個區域不能與之匹配。因此，單一分區法很不靈活。

1.2混合分區算法

參考各速率呼叫的發生概率，將碼樹分為有部分重疊的若干區域，區數等于速率類型數。每個區支持兩種以上的速率，重疊區域允許兩種速率的呼叫共享，每種速率的呼叫在本區域中沒有可空碼時有權使用下層相鄰重疊區域中的碼。例如，當高速率業務比重較大時，將一個5層碼樹進行混合分區，如圖3。圖中，為2R、4R和8R保留的區域大小比單一分區大了一倍，速率為iR的呼叫不但可以被分配對應區域中的碼，還能被分配iR/2區域中的碼。這種混合策略稱為混合分區法1[2]。如果重疊區域允許三種速率的呼叫共享,速率為iR的呼叫可以被分配iR/2和iR/4對應區域中的碼，這種策略稱為混合分區法2[2]， 如圖4所示。

單一分區法和混合分區法都預先將碼樹劃區，每區的碼只分給對應的呼叫，分配過程中各區域范圍不變。

二、分區借碼法

每類呼叫的阻塞率相互間越接近，則系統分配時對各類呼叫越公平。本文從碼阻塞率切入，提出一種分區借碼算法，其思路是將阻塞率低的那類呼叫的碼資源借給阻塞率最大的那類呼叫。

算法步驟如下碼所述：①用第1節中三種碼樹分區法的任何一種（如采用單一分區法）將碼樹分區；②分配過程中更新記錄所有類呼叫的阻塞率，并按從小到大排序； ③當一個第j類呼叫在對應區找不到空碼時，則判斷該類呼叫的阻塞率PB（j）在所有類呼叫的阻塞率中是否最大，若是跳到④，否則跳到⑤；④按阻塞率從小到大依次向其它類呼叫對應的區借碼，該區有碼可借則跳到⑥。否則，發生阻塞，分配失敗，退出；⑤發生阻塞，分配失敗，退出；⑥將該區中借得的碼分配給該呼叫，分配成功，退出。

三、算法性能分析

3.1公平性

本文采用公平系數來衡量算法對系統公平性的影響，F（0≤F≤1）越接近1 表示系統越“公平”，即各種速率請求的接入成功率越接近。式（1）中，PB ( j ) 為第j（0≤j≤j-1）類請求的阻塞率。阻塞率是所有被系統阻塞的請求數與總請求數之比，包括容量阻塞和碼阻塞。

F= （1）

為了找出公平性、吞吐量和阻塞率等方面最好的算法，分別采用單一分區法、混合分區法1和混合分區法2、分區借碼法共四種保留分配算法，在速率模型A及相應的系統負荷下運行，統計系統的公平系數、吞吐量和阻塞率，呼叫的到達和離去均為泊松過程。在某個保留區域內尋找空碼時均采用極左單碼分配算法[3]。系統負荷分別取GA={2.1，4.1，6.2，8.2，10.3}。其中，10.3是公平性最好的借碼分區法在阻塞率為10%時的系統負荷值,其它值是它們的20%、40%、60%和80%。

參見圖5，四種算法中，系統使用分區借碼法時的公平系數F最接近1，說明分區借碼法的公平性最好。這是因為分區借碼法盡量用阻塞率最小的區中空閑碼資源借給阻塞率最大的區，縮小了各類呼叫阻塞率的差距。此外，分區借碼法比混合分區法更公平的一個主要原因是具有動態性，它時刻統計著每類呼叫的阻塞率，當某一類呼叫阻塞較多時，其它類呼叫的區域將借碼給它，這種做法本身就體現了“公平”;而混合分區法則是在分配前靜態地劃分碼樹，分配開始后，高速率呼叫可以借用低速率呼叫的資源，而反之則不行，資源調配的靈活程度相形見絀。

3.2吞吐量和阻塞率

四種算法中，分區借碼法的吞吐量最大，阻塞率最小，說明同等條件下分區借碼法能接入最多的呼叫。單一分區法中全部碼資源由各類呼叫獨立占用，發生阻塞時各區域空閑的資源不能共享互借；混合分區法中資源的共享程度不夠充分，且總有利于高速率呼叫。分區借碼法根據當前各類呼叫的阻塞情況充分共享碼資源，將“最空閑”的資源分配給“最有需要”的呼叫，所以吞吐量更大。

四、結論

已有的三種保留分配算法僅根據業務構成的先驗知識，在分配開始之前就已劃分好資源，因此應付不了變化的實際業務。分區借碼算法是對已有的保留分配算法的改進，它先按已有的算法為每類呼叫預留資源，在分配過程中根據每類呼叫的阻塞率的變化，協調空閑的碼資源，盡量將阻塞率最低的那類呼叫的碼資源借給阻塞率最大那類呼叫，使各類呼叫的阻塞率趨于一致，實現公平分配，同時接入了更多的呼叫。因此，分區借碼法是最公平、吞吐量最大、阻塞率最小的保留分配算法。