OVSF碼保留分配算法研究

楊愷

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

【關(guān)鍵詞】直接序列擴(kuò)頻碼分多址正交可變長擴(kuò)頻因子保留分配算法

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

一、OVSF碼和保留分配算法

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

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

1.1單一分區(qū)算法

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

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

1.2混合分區(qū)算法

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

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

二、分區(qū)借碼法

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

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

三、算法性能分析

3.1公平性

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

F= （1）

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

參見圖5，四種算法中，系統(tǒng)使用分區(qū)借碼法時(shí)的公平系數(shù)F最接近1，說明分區(qū)借碼法的公平性最好。這是因?yàn)榉謪^(qū)借碼法盡量用阻塞率最小的區(qū)中空閑碼資源借給阻塞率最大的區(qū)，縮小了各類呼叫阻塞率的差距。此外，分區(qū)借碼法比混合分區(qū)法更公平的一個(gè)主要原因是具有動(dòng)態(tài)性，它時(shí)刻統(tǒng)計(jì)著每類呼叫的阻塞率，當(dāng)某一類呼叫阻塞較多時(shí)，其它類呼叫的區(qū)域?qū)⒔璐a給它，這種做法本身就體現(xiàn)了“公平”;而混合分區(qū)法則是在分配前靜態(tài)地劃分碼樹，分配開始后，高速率呼叫可以借用低速率呼叫的資源，而反之則不行，資源調(diào)配的靈活程度相形見絀。

3.2吞吐量和阻塞率

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

四、結(jié)論

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