楊?lèi)?/p>

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

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

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

一、OVSF碼和保留分配算法

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

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

1.1單一分區(qū)算法

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

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

1.2混合分區(qū)算法

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

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

二、分區(qū)借碼法

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

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

三、算法性能分析

3.1公平性

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

F= （1）

為了找出公平性、吞吐量和阻塞率等方面最好的算法，分別采用單一分區(qū)法、混合分區(qū)法1和混合分區(qū)法2、分區(qū)借碼法共四種保留分配算法，在速率模型A及相應(yīng)的系統(tǒng)負(fù)荷下運(yùn)行，統(tǒng)計(jì)系統(tǒng)的公平系數(shù)、吞吐量和阻塞率，呼叫的到達(dá)和離去均為泊松過(guò)程。在某個(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%。

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

3.2吞吐量和阻塞率

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

四、結(jié)論

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