一種改進的First-fit載波分配算法

尹　譯　梁　俊　宋愛民　肖　楠　王　軼

(空軍工程大學信息與導航學院　陜西 西安 710077)

?

一種改進的First-fit載波分配算法

尹譯梁俊宋愛民肖楠王軼

(空軍工程大學信息與導航學院陜西 西安 710077)

摘要針對MF-TDMA衛(wèi)星網(wǎng)絡中利用First-fit算法進行載波分配時出現(xiàn)的時隙碎片問題，構(gòu)建出支持時隙調(diào)整的載波時隙管理模型，并在模型基礎上提出一種改進的支持時隙調(diào)整的First-fit載波分配算法。在該算法中，載波在首次分配失敗后將對空閑時隙進行位置調(diào)整，構(gòu)建與業(yè)務相匹配的時隙組，最終實現(xiàn)接納業(yè)務的目的。仿真結(jié)果表明，該算法能有效提升載波剩余容量利用率，降低新到達業(yè)務的被拒絕率。

關(guān)鍵詞衛(wèi)星網(wǎng)絡載波分配裝箱問題利用率時隙組

AN IMPROVED FIRST-FIT CARRIER ALLOCATION ALGORITHM

Yin YiLiang JunSong AiminXiao NanWang Yi

(School of Information and Navigation, Air Force Engineering University, Xi’an 710077，Shaanxi,China)

AbstractCarrier allocation with traditional First-fit algorithm will easily produce slot fragments in MF-TDMA satellite communication network when system accepts new services. To solve this problem, we built a carrier slots administration model supporting slots adjustment. Based on this model, we presented an improved First-fit algorithm which allows the adjustment of slots. In this improved algorithm, carrier will adjust the positions of idle slots after the failure in first allocation, and the system will try to build a new slots group matching the services, and finally achieves the goal of service admission. Simulation result indicated that the adjustment-allowed algorithm could efficiently raise the use ratio of carriers’ residual capacity and decreased the rejecting possibility of newly-arrived services.

KeywordsSatellite networkCarrier allocationBin packing problemUse ratioSlots group

0引言

隨著衛(wèi)星通信技術(shù)的不斷發(fā)展，業(yè)務傳輸質(zhì)量與有限通信資源的矛盾日益突出。作為解決該矛盾的關(guān)鍵技術(shù)之一，衛(wèi)星資源管理技術(shù)在DVB、IP和ATM衛(wèi)星通信系統(tǒng)中均得到廣泛應用。衛(wèi)星資源管理主要研究如何充分地利用現(xiàn)有通信資源，為用戶提供盡可能高的服務質(zhì)量。目前衛(wèi)星資源管理技術(shù)的研究熱點主要集中在帶寬分配上，文獻[1]提出了一種比例公平注水迭代算法，能夠最大程度保證用戶間的公平性，但是帶寬利用率偏低。文獻[2]針對動態(tài)帶寬分配問題，利用流量預測對帶寬需求進行估計，提升了鏈路使用效率。文獻[3]在帶寬分配中引入經(jīng)濟學中效用的概念，建立起基于效用函數(shù)的帶寬動態(tài)分配模型，求解出最大效用的帶寬分配方案，改善了DVB-RCS衛(wèi)星網(wǎng)中吞吐量偏低的問題。文獻[4]提出了一種基于令牌桶的改進帶寬分配算法，將用戶按照優(yōu)先級和權(quán)值進行劃分，實現(xiàn)了按照用戶重要性對帶寬的二次分配。

在MF-TDMA衛(wèi)星通信體制中，帶寬分配實質(zhì)上可劃分為載波分配和時隙分配兩步進行[5]。某條載波被分配給業(yè)務的條件是空閑容量必須與業(yè)務需求相匹配，否則系統(tǒng)將為業(yè)務選擇其余載波。為解決如何分配載波的問題，文獻[6]將載波分配抽象為一維裝箱問題[7]，提出了一種First-fit載波分配算法。但是該算法在分配后存在時隙碎片的問題，阻礙了載波剩余容量利用率的提高。為解決時隙碎片問題，本文對First-fit載波分配算法進行了改進，構(gòu)建出支持載波內(nèi)時隙調(diào)整的管理模型，并在該模型的基礎上設計了支持時隙調(diào)整的First-fit載波分配算法，允許系統(tǒng)在載波內(nèi)進行業(yè)務時隙位置的調(diào)整，使載波能夠容納更多業(yè)務，提高了載波的利用率。

1時隙碎片問題

在MF-TDMA衛(wèi)星網(wǎng)絡中，時隙分配分解為兩步完成：第一步為業(yè)務分配載波；第二步在載波內(nèi)進行具體時隙劃分。在第一步中，載波被分配給業(yè)務的前提是載波中空閑時隙的數(shù)目、位置能分別滿足業(yè)務對時延和時延抖動要求。用戶業(yè)務類型不同，對時隙數(shù)量和分布均勻性的要求也不同，例如高速數(shù)據(jù)傳輸僅需要滿足時隙數(shù)目要求，而語音、視頻等對時延敏感的業(yè)務還關(guān)注時隙分布均勻程度。由于載波中空閑時隙分布呈現(xiàn)隨機性，剩余時隙的均勻性可能難以滿足新到達業(yè)務對時延抖動的要求[5]。因此在設計載波分配算法時，需要同時考慮時隙數(shù)目和分布兩個因素的約束。

裝箱模型是統(tǒng)籌學中的典型NP-Hard問題[8]，其主要解決的問題是如何利用最少的箱子裝下大小不同的貨物，這與載波分配問題在本質(zhì)上是相同的。文獻[6]中提出將載波分配轉(zhuǎn)化為帶時隙均勻性約束的一維裝箱問題，并利用裝箱問題中的First-fit算法[9]進行解決。 First-fit算法是一維裝箱問題中的經(jīng)典算法，其基本思想是：對箱子依次進行編號，始終將新到達的貨物裝入編號最小且能夠容納其的箱子中，若已有非空箱子都無法容納貨物，則啟用新箱子裝載貨物。First-Fit載波分配算法遵從上述思想，將載波、業(yè)務分別抽象為箱子和貨物，結(jié)合業(yè)務的具體需求判別和選擇承載載波，具體過程如圖1所示。

圖1　傳統(tǒng)First-Fit載波分配算法示意圖

上述載波分配算法根據(jù)業(yè)務所需時隙數(shù)目對所有已用載波依次進行遍歷。若找到時隙數(shù)目符合要求的載波，則進一步考察載波中空閑時隙分布均勻性是否能滿足業(yè)務要求，在判定時隙分布均勻性符合要求后，系統(tǒng)選擇該載波承載業(yè)務。若所有載波都不能同時滿足時隙數(shù)目和均勻性要求時，系統(tǒng)判定對已有的載波進行分配失敗，將啟用新的空載波傳輸業(yè)務。該算法存在的主要問題是在剩余時隙數(shù)目足夠的條件下，部分載波的時隙分布均勻性達不到業(yè)務要求導致分配失敗，遺留下大量空閑的“時隙碎片”，不利于載波利用率的提高。

為消除空閑的時隙碎片，必須在載波中調(diào)整時隙碎片的位置，以適應新到達業(yè)務的需求，這是本文改進算法的出發(fā)點。為實現(xiàn)上述時隙調(diào)整過程，首先需構(gòu)建一種支持時隙調(diào)整的管理模型，對載波空閑時隙的數(shù)目和分布進行建模管理，以明確當前載波所能提供的時隙資源現(xiàn)狀。然后在載波分配過程中設計合理的調(diào)整機制以改變空余時隙的分布狀態(tài)，使其盡量能與業(yè)務需求相匹配，以期望利用最少的載波容納下最多的業(yè)務。

2時隙管理模型設計

時隙管理模型是進行時隙分配的前提，其任務是描述載波中時隙可用狀態(tài)及分布，并將結(jié)果傳遞給資源管理器，由資源管理器決定具體為連接請求分配哪些時隙。傳統(tǒng)的時隙管理方式是按幀中順序?qū)r隙進行編號，并以幀為基本單位[5]對時隙進行統(tǒng)計和分配，實現(xiàn)起來簡單方便。這種離散的時隙管理模型雖然能夠清晰標識出空閑時隙，但是在時隙分布均勻程度的表示和帶寬分配的靈活性上遇到困難，不利于時隙調(diào)整的必要性判斷和執(zhí)行方案的制定。本文設計一種基于時隙組的管理模型，從時隙管理的基本單位出發(fā)解決了上述問題。

以幀中包含n個時隙的載波為例，首先按傳統(tǒng)的編號方式對連續(xù)m幀的時隙進行編號s1,s2,…，sn×m，對于編號為k的時隙，根據(jù)如下過程生成在矩陣中對應的位置(i,j)：

(1)

j=mod(k,t)

(2)

(3)

(4)

(z=1,2,…)

將滿足上述條件的等距時隙構(gòu)建為時隙組，作為資源管理的基本單位。由于時隙組內(nèi)的時隙遵從相對均勻分布，占用時隙組的業(yè)務將獲得良好的時延性能[10]，能有效避免出現(xiàn)大的時延抖動?？紤]到α、β取值的特殊性，構(gòu)建過程中可能會出現(xiàn)時隙重復劃分的現(xiàn)象，例如某方陣中對角線時隙組和第一列時隙組均包含s11，而星上資源管理器不可能將s11同時分配給兩個連接請求。為避免該問題，約定以下時隙組構(gòu)建規(guī)則：

① 時隙不能同時劃分給多個時隙組；

② 模型初始化過程中，時隙組的成員時隙必須來源于同一列；

③ 同列的時隙組成員間必須具有相等列間距；

④ 在滿足②、③的基礎上，允許時隙組進行合并或等分；

⑤ 時隙組與業(yè)務必須確定單對單的服務關(guān)系，否則將對時隙組進行拆分。

上述準則可保證構(gòu)建完畢后每列剩余時隙仍可構(gòu)成時隙組，同時允許時隙組根據(jù)業(yè)務需求對時隙組進行合并或拆分。下面對如何確定時隙組包含時隙數(shù)量進行討論。

傳統(tǒng)時隙管理模型將時隙作為提供帶寬的基本單位，分配給業(yè)務的帶寬必須是基本帶寬的整數(shù)倍。以文獻[11]中MF-TDMA系統(tǒng)參數(shù)為例，管理模型的單位帶寬：

(5)

當系統(tǒng)進行帶寬分配時，單個業(yè)務連接獲得帶寬：

B=M×64 kbps

(6)

(7)

如表1所示(假定矩陣中每幀組成一行)。

表1　基于時隙組的管理模型單位帶寬

表1中隨著矩陣包含幀數(shù)越大，載波提供的單位帶寬越小。一方面，相比于式(6)中缺乏靈活性的整數(shù)倍帶寬分配，基于時隙組的管理模型中單位帶寬較小，允許系統(tǒng)每隔n幀分配一個時隙，提高了時隙分配的“精度”，使系統(tǒng)更加自由地分配和調(diào)整業(yè)務占用時隙位置成為可能。例如某業(yè)務需要192 kbps帶寬，其在兩種管理模型下的實現(xiàn)如圖2所示。

圖2　業(yè)務在兩種管理模型下的實現(xiàn)

圖2中，傳統(tǒng)管理模型需要在每幀中尋找3個空閑時隙提供給業(yè)務，否則將選擇其他載波。而在基于時隙組的管理模型中，由于系統(tǒng)以時隙組為單位進行時隙管理，只需在矩陣中提供任意包含12個時隙的時隙組(圖中分配編號為1、2、3、4的時隙組)，仍然能滿足業(yè)務的帶寬需求，提高了時隙分配的靈活性。

另一方面，在不同的資源管理模型下，相同連接請求所需的時隙數(shù)目是不同的，其中傳統(tǒng)資源管理模型所需的時隙為：

(8)

而基于時隙組的管理模型為：

(9)

對比式(8)、式(9)，可以證明降低單位帶寬確實能避免資源浪費，提高時隙的利用率。

對于GEO衛(wèi)星網(wǎng)絡而言，地面用戶在計算時隙組大小N′后，向星上資源管理器提出帶寬申請[12]，衛(wèi)星將結(jié)合業(yè)務時隙均勻性要求和現(xiàn)有空余時隙組分布判斷載波分配的結(jié)果并傳回地面。由于星地時延的存在，申請到返回結(jié)果的時延將略大于270 ms。

3支持時隙調(diào)整的First-fit載波分配算法

根據(jù)接入業(yè)務對時隙分布均勻性要求不同，可將業(yè)務劃分為嚴格要求、有限要求和無要求三類。嚴格均勻性要求業(yè)務是指部分高質(zhì)量傳輸服務，對時延抖動要求十分苛刻，分配的時隙組必須遵從完全均勻分布。有限均勻性要求業(yè)務的傳輸質(zhì)量、時延抖動要求都有所降低，時隙的分布只需滿足近似均勻即可。無均勻性要求業(yè)務只對時隙數(shù)目有要求，在分配時不考慮時隙是否均勻分布。

載波中時隙位置的調(diào)整必然帶來時隙間相對位置的變動，根據(jù)調(diào)整行為發(fā)生的位置以及對業(yè)務產(chǎn)生影響大小，定義以下四種時隙調(diào)整行為。

1) 時隙組調(diào)整時隙組調(diào)整是指由于某些時隙組構(gòu)建的需要，將現(xiàn)有時隙組進行整體性移動，如圖3所示，時隙組內(nèi)成員的相對位置不變，不會影響業(yè)務時隙的均勻性分布。此類位置調(diào)整對業(yè)務無任何顯著影響，適用于所有類型的業(yè)務。

圖3　時隙組調(diào)整

2) 時隙組內(nèi)調(diào)整為新業(yè)務構(gòu)建時隙組時，某些條件下必須對時隙組內(nèi)部進行位置調(diào)整，如圖4所示，導致時隙組內(nèi)部分布均勻性發(fā)生變化。為衡量原業(yè)務對上述調(diào)整的容忍程度，設定參數(shù)qmax衡量單個時隙允許調(diào)整的最大位移：

qmax=λ·l

(10)

其中l(wèi)表示在調(diào)整前時隙組內(nèi)時隙間距；λ表示業(yè)務對調(diào)整容忍程度，根據(jù)業(yè)務的不同存在差異，一般條件下嚴格均勻性要求業(yè)務λ=0，有限均勻性要求業(yè)務取值為0<λ≤0.3，無均勻性要求業(yè)務λ=∞。業(yè)務的qmax越大，表明時隙調(diào)整對其影響越小。

圖4　時隙組內(nèi)調(diào)整

3) 載波間遷移時隙位置調(diào)整中允許改變承載業(yè)務的載波，即業(yè)務由原載波遷移到另一目標載波，如圖5所示。對業(yè)務進行載波間遷移需滿足以下兩個條件：(1)原載波在構(gòu)建新時隙組時需要使用業(yè)務已占用的時隙。(2)目標載波存在滿足相應需求的空閑時隙組以接納業(yè)務。若無法同時滿足上述條件，則時隙調(diào)整失敗，不能在原載波中構(gòu)建新時隙組。在業(yè)務載波間遷移時，由于目標載波的時隙組分布均勻性存在差異，可能伴隨著1)和2)的發(fā)生，系統(tǒng)在業(yè)務遷移前必須考慮式(10)的約束是否得到滿足。在調(diào)整后，業(yè)務將在新的載波上繼續(xù)運行，對業(yè)務的影響與2)相同。

圖5　載波間遷移

4) 無序調(diào)整無序調(diào)整是指破壞已有業(yè)務時隙組，將業(yè)務無序分布到新的空閑時隙組中。這類時隙調(diào)整不關(guān)注時隙的均勻性，只要求新的時隙組能夠接納業(yè)務，對時隙組的選擇存在隨意性，僅適用于無均勻性要求業(yè)務。

在時隙數(shù)目達到要求的條件下，系統(tǒng)的時隙調(diào)整行為允許載波重新整合自身的空閑時隙，構(gòu)建出滿足新業(yè)務需求的時隙組。將上述時隙調(diào)整行為引入First-Fit載波分配算法中進行改進，利用載波時隙的“可調(diào)整”特性提高載波中時隙利用率，改進算法的具體過程如圖6所示。

圖6　支持時隙調(diào)整的First-fit載波分配算法示意圖

在上述載波分配過程中，在剩余時隙組與業(yè)務需求的匹配失敗后，系統(tǒng)將進入時隙調(diào)整階段，以生成與新業(yè)務相匹配的時隙組為目標執(zhí)行調(diào)整。若成功生成目標時隙組，進行業(yè)務分配并結(jié)束，否則將繼續(xù)與其余載波進行匹配比較。當遍歷完所有載波仍未完成分配，則啟用新的空載波承載業(yè)務。

4仿真與性能分析

為驗證支持時隙調(diào)整的First-Fit載波分配算法的對載波利用率的改進效果，構(gòu)建基于STK/MATLAB軟件的網(wǎng)絡仿真環(huán)境，以模擬業(yè)務到達后被載波接納的情況。其中STK模擬衛(wèi)星的軌道位置、傳輸時延和信噪比等參數(shù)，MATLAB計算業(yè)務時隙需求和載波剩余容量。

1) 仿真參數(shù)設置

假定MF-TDMA衛(wèi)星系統(tǒng)包含16條載波，載波中每幀包含64個時隙。一共設置8個業(yè)務源，通過地面信關(guān)站進行集中的時隙申請，網(wǎng)絡拓撲結(jié)構(gòu)如圖7所示。衛(wèi)星選取同步軌道衛(wèi)星(雙向時延270 ms)，信道中信噪比設置為18~20 dB，保證信關(guān)站與衛(wèi)星之間能夠順利完成信息交互。

圖7　仿真網(wǎng)絡拓撲圖

在用戶端的設置如下：業(yè)務到達的過程服從泊松分布，且以概率P=0.5出現(xiàn)對時隙均勻性的要求；每個業(yè)務請求的時隙數(shù)目在[0,16]上呈均勻分布，調(diào)整容忍程度λ=0.25。為了簡化仿真過程，規(guī)定業(yè)務在被載波接納后不會結(jié)束服務，意味著被業(yè)務占據(jù)的時隙在仿真中不會釋放。

2) 性能指標的選擇

為合理檢驗算法載波分配過程中載波利用率的改進，需分別從載波時隙和業(yè)務接納的角度進行考察。選取載波平均利用率α用于衡量載波時隙的使用情況，其定義為：

(11)

選取業(yè)務拒絕率β衡量算法對新到業(yè)務的接納能力，其定義為：

(12)

3) 仿真過程與分析

為對照檢驗改進算法性能的提升，在仿真中設置實驗組A和對照組B，分別采用支持時隙調(diào)整的First-fit載波分配算法和傳統(tǒng)的First-fit載波分配算法，其余仿真環(huán)境與前述1)中配置相同。

仿真中對每項到達業(yè)務的狀態(tài)進行監(jiān)測，確定其是否被系統(tǒng)接納，并據(jù)此計算出相應α和β值變化。當系統(tǒng)不再接納業(yè)務時表明系統(tǒng)容量已經(jīng)飽和，中止仿真并記錄結(jié)果。仿真結(jié)果如圖8、圖9所示。

圖8　兩種算法的載波利用率α

圖9　兩種算法的業(yè)務拒絕率β

圖8中在業(yè)務申請數(shù)較少時，載波中時隙資源相對充足，曲線只隨業(yè)務的時隙需求變化，無時隙碎片產(chǎn)生，兩種算法的載波利用率曲線重疊。隨著業(yè)務申請的增加，傳統(tǒng)的First-fit載波分配算法的載波利用率將低于改進的分配算法，這是因為在高業(yè)務到達率的條件下，空閑時隙的非均勻分布會導致時隙碎片的產(chǎn)生，傳統(tǒng)First-fit載波分配算法無法處理這些碎片，造成資源浪費；而引入調(diào)整機制的改進算法中，系統(tǒng)能主動對載波內(nèi)空閑時隙的位置進行調(diào)整，以構(gòu)建出能夠接納業(yè)務的新時隙組，減少了時隙碎片的產(chǎn)生，改善了載波的利用效率。

在圖9中，F(xiàn)irst-Fit載波分配算法存在較高的業(yè)務拒絕率，而改進后載波分配算法的業(yè)務拒絕率要顯著低于原算法。這種差異的原因在于兩種算法拒絕接納業(yè)務的條件不同，原算法在尋找能夠接納業(yè)務的時隙組失敗后就拒絕接納；而改進算法在無法找到時隙組時會嘗試構(gòu)建新時隙組，在尋找和構(gòu)建均失敗后才進行拒絕，這樣后者能夠顯著提升載波接納業(yè)務的能力，降低業(yè)務被拒絕的概率。

5結(jié)語

針對MF-TDMA衛(wèi)星網(wǎng)絡中利用First-fit算法進行載波分配時出現(xiàn)的時隙碎片問題，本文構(gòu)建出支持時隙調(diào)整的載波時隙管理模型，并在模型基礎上提出一種改進的支持時隙調(diào)整的First-fit載波分配算法。在該算法中，系統(tǒng)以匹配新業(yè)務為目標進行載波調(diào)整，盡量使業(yè)務選擇利用率已經(jīng)較高的載波，最大程度上對剩余空閑時隙進行了利用，在考慮時隙數(shù)目和位置的基礎上，提高了原算法的載波利用率，降低了新業(yè)務的被拒絕概率。但是，本文在設計和仿真中未考慮載波的調(diào)整運算的復雜性對系統(tǒng)性能帶來的影響，有待于在以后的研究中進行完善。

參考文獻

[1] Morell A, Seco-Granados G, Vazquesz-Castro M. Cross-layer design of dynamic bandwidth allocation in DVB-RCS [J].IEEE Systems Journal, 2008,2(1):62-73.

[2] 秦勇,張軍,張濤.基于帶寬按需分配的DVB-RCS寬帶衛(wèi)星MAC協(xié)議[J].宇航學報,2010,31(3):838-844.

[3] 高鑫,王祖林.基于效用最大化的DVB-RCS跨層動態(tài)帶寬分配[J].宇航學報,2011,32(4):857-862.

[4] 張文波,譚小波.一種改進的無線通信網(wǎng)絡帶寬分配方法[J].宇航學報,2012,33(12):1762-1767.

[5] 董啟甲,張軍,張濤,等.高效MF-TDMA系統(tǒng)時隙分配策略[J].航空學報, 2009,30(9):1718-1725.

[6] Park J M, Savagaonkar Y, Chong E K P, et al. Allocation of Qos connections in MF-TDMA satellite systems: a two-phase approach [J]. IEEE Transactions on Vehicular Technology,2005,54(1):177-190.

[7] 劉林浩,楊鼎強,王晨.一種帶脆度的尺寸可變裝箱問題[J].計算機工程與應用,2013,49(12):263-266.

[8] Poothokaran D, Shimakawa Y. A study on evaluation of multi-objective Bin Packing Problems[C]//Computers and Industrial Engineering(CIE), 2010 40thInternational Conference on. IEEE, 2010:1-6.

[9] 張雪,倪桂強,金鳳林,等. MF-TDMA信道分配研究[J].計算機與數(shù)字工程,2010,38(11):58-60.

[10] 董啟甲,張軍,張濤.星上MF-TDMA系統(tǒng)信道管理方法[J].電子與信息學報,2009,31(10):2378-2384.

[11] Celandroni N, Secchi R .Suitability of DAMA and contention-based satellite access schemes for tcp traffic in mobile DVB-RCS[J]. IEEE Transactions on Vehicular Technology,2009,58(4):1836-1845.

[12] 秦勇,張軍,張濤.DVB-RCS衛(wèi)星系統(tǒng)無線資源管理體系架構(gòu)[J].計算機工程與應用,2010,46(20):71-74.

中圖分類號TN927.23

文獻標識碼A

DOI:10.3969/j.issn.1000-386x.2016.02.027

收稿日期：2014-09-09。陜西省自然科學基金面上項目(2012JM 8004)。尹譯，碩士生，主研領域：衛(wèi)星資源管理。梁俊，教授。宋愛民，高級實驗師。肖楠，博士生。王軼，講師。