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

尹　譯　梁　俊　宋愛民　肖　楠　王　軼

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

?

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

尹譯梁俊宋愛民肖楠王軼

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

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

關鍵詞衛星網絡載波分配裝箱問題利用率時隙組

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引言

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

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

1時隙碎片問題

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

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

圖1　傳統First-Fit載波分配算法示意圖

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

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

2時隙管理模型設計

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

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

(1)

j=mod(k,t)

(2)

(3)

(4)

(z=1,2,…)

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

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

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

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

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

⑤ 時隙組與業務必須確定單對單的服務關系，否則將對時隙組進行拆分。

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

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

(5)

當系統進行帶寬分配時，單個業務連接獲得帶寬：

B=M×64 kbps

(6)

(7)

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

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

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

圖2　業務在兩種管理模型下的實現

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

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

(8)

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

(9)

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

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

3支持時隙調整的First-fit載波分配算法

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

載波中時隙位置的調整必然帶來時隙間相對位置的變動，根據調整行為發生的位置以及對業務產生影響大小，定義以下四種時隙調整行為。

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

圖3　時隙組調整

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

qmax=λ·l

(10)

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

圖4　時隙組內調整

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

圖5　載波間遷移

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

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

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

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

4仿真與性能分析

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

1) 仿真參數設置

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

圖7　仿真網絡拓撲圖

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

2) 性能指標的選擇

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

(11)

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

(12)

3) 仿真過程與分析

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

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

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

圖9　兩種算法的業務拒絕率β

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

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

5結語

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

參考文獻

[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寬帶衛星MAC協議[J].宇航學報,2010,31(3):838-844.

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

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

[5] 董啟甲,張軍,張濤,等.高效MF-TDMA系統時隙分配策略[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].計算機與數字工程,2010,38(11):58-60.

[10] 董啟甲,張軍,張濤.星上MF-TDMA系統信道管理方法[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衛星系統無線資源管理體系架構[J].計算機工程與應用,2010,46(20):71-74.

中圖分類號TN927.23

文獻標識碼A

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

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