林宇生，蔣洪磊，董彥磊，耿紀(jì)昭，劉玥霄

(中國電子科技集團(tuán)公司第五十四研究所，河北 石家莊 050081)

基于遺傳算法的通信衛(wèi)星資源動(dòng)態(tài)調(diào)度方法研究

林宇生，蔣洪磊，董彥磊，耿紀(jì)昭，劉玥霄

(中國電子科技集團(tuán)公司第五十四研究所，河北 石家莊 050081)

隨著衛(wèi)星通信技術(shù)的持續(xù)發(fā)展，基于衛(wèi)星通信的實(shí)際應(yīng)用需求也日益復(fù)雜。為了更高效地處理不同體制網(wǎng)系之間的資源競爭，提高通信衛(wèi)星資源的利用率，更大限度地滿足衛(wèi)星通信任務(wù)需求，提出了一種基于遺傳算法的通信衛(wèi)星資源動(dòng)態(tài)調(diào)度方法。介紹了衛(wèi)星資源動(dòng)態(tài)調(diào)度所基于的通信任務(wù)的基本約束，并結(jié)合遺傳算法闡述了資源動(dòng)態(tài)調(diào)度具體實(shí)施過程，通過仿真實(shí)驗(yàn)將通信衛(wèi)星資源的動(dòng)態(tài)調(diào)度使用方式與靜態(tài)分配使用方式進(jìn)行了對比分析。仿真結(jié)果表明，在相同任務(wù)數(shù)和不同任務(wù)數(shù)的條件下，資源動(dòng)態(tài)調(diào)度的使用方式都可以達(dá)到更高的資源利用率。

通信衛(wèi)星資源；動(dòng)態(tài)調(diào)度；遺傳算法

0 引言

近年來，衛(wèi)星通信技術(shù)不但在軍事領(lǐng)域發(fā)揮著重要的作用[1]，其商業(yè)市場的需求也不斷增長[2]。隨著衛(wèi)星資源的日益豐富，使用情況呈現(xiàn)多樣化的特點(diǎn)，對衛(wèi)星通信網(wǎng)的運(yùn)行管理也變得更加復(fù)雜[3]。目前在面向多網(wǎng)系、多任務(wù)共享衛(wèi)星資源實(shí)際需求的條件下，采用何種有效的資源調(diào)度技術(shù)以有限的頻率資源更大限度地滿足通信保障任務(wù)已經(jīng)成為了衛(wèi)星通信中的一個(gè)需要解決的重要問題。

目前通常以通信任務(wù)的形式來對通信衛(wèi)星的資源進(jìn)行調(diào)度管理[4]，通信任務(wù)可以表示為在某一段特定時(shí)間內(nèi)為某一些特定用戶分配一定帶寬的衛(wèi)星頻率資源。當(dāng)前廣泛應(yīng)用的資源靜態(tài)分配(或稱預(yù)規(guī)劃)方式將資源按需地分配給某些任務(wù)[5-6]，對于新增的任務(wù)只能在剩余可用的資源范圍內(nèi)予以分配，而非在全局的角度統(tǒng)一調(diào)度。另外靜態(tài)分配方式缺乏資源回收機(jī)制，資源分配不夠靈活，導(dǎo)致其資源利用率不高。本文采用基于生物學(xué)的遺傳算法研究了一種衛(wèi)星資源動(dòng)態(tài)調(diào)度方法，可有效提高衛(wèi)星頻率資源的利用率。

1 遺傳算法原理

遺傳算法[7]基于模仿生物界遺傳學(xué)的遺傳過程，通過不斷進(jìn)化和迭代尋找問題的最優(yōu)解，主要適用于規(guī)劃類問題如工件排樣[8]、波束成形[9]和路徑規(guī)劃[10]等，以及調(diào)度類問題如資源運(yùn)用[11]、計(jì)劃編制[12]和任務(wù)調(diào)度[13]等的求解。

遺傳算法首先把問題的參數(shù)用基因來表示，把問題的解用染色體來表示，從而得到一個(gè)由具有不同染色體組成的群體。將這個(gè)群體放到特定的問題環(huán)境里進(jìn)行生存競爭，適者有最好的機(jī)會(huì)生存和產(chǎn)生后代，后代隨機(jī)化地繼承父代的最好特征，并也在生存環(huán)境的控制支配下繼續(xù)這一過程。隨著進(jìn)化的不斷進(jìn)行，群體的染色體都將逐漸適應(yīng)環(huán)境，最后收斂到一組最適應(yīng)環(huán)境的染色體，即得到問題的最優(yōu)解。其核心過程可描述如下：① 染色體編碼；② 初始化種群；③ 設(shè)計(jì)適應(yīng)度函數(shù)；④ 選擇；⑤ 交叉；⑥ 變異。遺傳算法的主要流程如圖1所示。

圖1 遺傳算法流程

2 通信衛(wèi)星資源動(dòng)態(tài)調(diào)度方法

2.1 通信任務(wù)約束分析

衛(wèi)星資源的動(dòng)態(tài)調(diào)度是通過在一定的時(shí)間范圍和頻率范圍內(nèi)將通信任務(wù)進(jìn)行有效排列而實(shí)現(xiàn)的[14]。根據(jù)通信任務(wù)的使用特征，可以分析得到其基本約束：時(shí)間約束和頻率約束。

時(shí)間約束：① 任務(wù)所需時(shí)長固定；② 任務(wù)所需時(shí)間范圍連續(xù)；③ 任務(wù)存在最小開始時(shí)間和最晚結(jié)束時(shí)間。最晚結(jié)束時(shí)間和最小開始時(shí)間之差必須大于或等于任務(wù)所需時(shí)長。

頻率約束：① 任務(wù)所需帶寬固定；② 任務(wù)所需頻率范圍連續(xù)。

根據(jù)以上描述，多通信任務(wù)的排列方式可以采用二維坐標(biāo)系的方法予以表征，排列示意如圖2所示。

圖2 通信任務(wù)排列示意

2.2 設(shè)計(jì)思路

在衛(wèi)星通信過程中，由于各通信任務(wù)的時(shí)間需求和帶寬需求各不相同，在有限的時(shí)間和帶寬范圍內(nèi)，它們不同的排列順序會(huì)導(dǎo)致不同的資源利用率。通信衛(wèi)星資源動(dòng)態(tài)調(diào)度是通過制定一系列的最優(yōu)調(diào)度原則來最終得到一組最優(yōu)的通信任務(wù)排列序列。

設(shè)給定的時(shí)間范圍為0～T(此時(shí)T應(yīng)大于或等于所有任務(wù)的最晚結(jié)束時(shí)間中的最大值)，給定的頻率范圍為0～F，則最優(yōu)調(diào)度原則如下：

① 頻率輪廓線表示的頻率值(即任務(wù)排樣圖的最大高度值)應(yīng)該盡量低；

② 時(shí)間輪廓線表示的時(shí)間值(即任務(wù)拍樣圖的最大寬度值)應(yīng)該盡量低；

根據(jù)以上原則，衛(wèi)星資源動(dòng)態(tài)調(diào)度的過程設(shè)計(jì)如下：

① 隨機(jī)初始化一個(gè)有n個(gè)通信任務(wù)的排序序列；

② 按照序列的順序依次取出每個(gè)通信任務(wù)，對于每一個(gè)任務(wù)，設(shè)其最早開始時(shí)間為t0，最晚開始時(shí)間為t1，持續(xù)時(shí)長為t，則在t0～t0+t的時(shí)間段內(nèi)，尋找是否存在空閑的頻率資源支持該任務(wù)。如果存在，則將該任務(wù)塊排列在該時(shí)間段內(nèi)相應(yīng)的頻率范圍內(nèi)上；如果不存在，則將搜索時(shí)間段的起始時(shí)間加一個(gè)偏移量t′，重復(fù)以上搜索過程。如果當(dāng)t0+t′+t>t1時(shí)仍未找到可用的頻率資源，則將該任務(wù)標(biāo)記為不可分配任務(wù)。

③ 計(jì)算所有排入的任務(wù)塊的總面積Area0，計(jì)算排列完成后形成的頻率輪廓線和時(shí)間輪廓線之內(nèi)的面積Area，最終計(jì)算f=Area0/Area。

④ 交換任務(wù)位置，調(diào)整任務(wù)排列，找出f的最大值，并直到f收斂或滿足疊代次數(shù)，輸出f最大時(shí)的任務(wù)排列結(jié)果。

2.3 遺傳算法

從理論上看，提出的衛(wèi)星資源動(dòng)態(tài)調(diào)度問題屬于具有最高計(jì)算復(fù)雜性的優(yōu)化計(jì)算問題——NP完全問題。對于這類問題，在全局空間上搜索最優(yōu)解是很困難的，甚至是不可能的[15]。因此引入遺傳算法來求解任務(wù)排序的最優(yōu)解，該算法可以以最小的計(jì)算代價(jià)最大限度地得到問題的最優(yōu)解，提高計(jì)算效率。下面給出遺傳算法的求解過程。

2.3.1 染色體編碼和群體初始化

采用互換編碼，如1，2，3，4，……，n，這些數(shù)字代表通信任務(wù)的編號，n為任務(wù)數(shù)量。初始化時(shí)，根據(jù)初始群體的大小M，隨機(jī)初始化M個(gè)任務(wù)序列，每一個(gè)序列的表達(dá)式如下所示：

Q={q1,q2,q3,…,qn}。

2.3.2 適應(yīng)度函數(shù)

適應(yīng)度函數(shù)是種群中染色體適應(yīng)能力的衡量標(biāo)準(zhǔn)，適應(yīng)度函數(shù)值越大，解的質(zhì)量就越好。

根據(jù)2.2節(jié)闡述的衛(wèi)星資源動(dòng)態(tài)調(diào)度過程對種群中的每一個(gè)染色體進(jìn)行排列，并根據(jù)最優(yōu)調(diào)度原則確定適應(yīng)度函數(shù)為f=Area0/Area，其中Area0為排入的任務(wù)塊的總面積，Area為排列完成后形成的頻率輪廓線和時(shí)間輪廓線之內(nèi)的面積，f值最大為1。

2.3.3 選擇

選擇操作是根據(jù)適應(yīng)度值的大小將染色體選擇進(jìn)入下一代種群的過程。選擇操作可以避免種群中有用的遺傳信息丟失，從而使得種群慢慢向最優(yōu)染色體種群靠近。

對初始種群中的每一個(gè)染色體，計(jì)算其適應(yīng)度函數(shù)值的大小，之后根據(jù)染色體適應(yīng)度函數(shù)值大小，采用輪盤賭算法進(jìn)行比例選擇運(yùn)算。選擇概率公式為：

2.3.4 交叉

交叉是模擬自然界進(jìn)化的過程中，2條染色體的某些基因位互換，從而形成新的染色體，增加種群多樣性。遺傳算法中的交叉操作就是從某個(gè)位置互換2條染色體的基因位，從而形成新的染色體。交叉操作首先對進(jìn)行了選擇運(yùn)算的群體中的染色體以隨機(jī)的概率兩兩配對，然后選擇單點(diǎn)交叉算子進(jìn)行交叉操作，產(chǎn)生M個(gè)染色體構(gòu)成子輩群體。

基于互換編碼的單點(diǎn)交叉操作的過程如下：設(shè)2個(gè)進(jìn)行交叉的染色體為X和Y，在1～n范圍內(nèi)隨機(jī)生成一個(gè)交叉位b，從X中將位于b之前的元素拷貝至一個(gè)新的子輩染色體newX中作為前面的元素，剩余元素按Y中出現(xiàn)的先后順序拷貝至newX；同樣的方法可以產(chǎn)生另一個(gè)新染色體newY。一種單點(diǎn)交叉操作示例如圖3所示。

圖3 單點(diǎn)交叉操作示例

2.3.5 變異

遺傳算法中的變異是將種群中某個(gè)或幾個(gè)的基因位的值進(jìn)行變換，從而形成新的染色體，變異操作使得種群避免收斂于局部次優(yōu)解，使得算法向更優(yōu)的方向進(jìn)化。

對進(jìn)行了交叉操作的子輩染色體，采用位置變異算子進(jìn)行變異操作。在1～n范圍內(nèi)隨機(jī)生成2個(gè)變異位b1、b2，以較小的概率對子輩的染色體中位于b1、b2的2個(gè)任務(wù)對調(diào)。

2.3.6 精英保留

為了加快算法的收斂速度，引入精英保留策略對該遺傳算法進(jìn)行優(yōu)化[16]。精英保留策略是指為了防止進(jìn)化過程中產(chǎn)生的最優(yōu)解被交叉和變異所破壞，將每一代中的最優(yōu)解原封不動(dòng)地復(fù)制到下一代中。

對于進(jìn)行了變異操作的子輩染色體，依次進(jìn)行排樣并計(jì)算相應(yīng)的適應(yīng)度，然后將子輩染色體中具有最低適應(yīng)度的染色體替換為選擇操作中所記錄的最優(yōu)染色體，得到修正后的子輩種群。

將生成的子輩種群在本遺傳算法中繼續(xù)迭代，循環(huán)這一算法過程直到適應(yīng)度函數(shù)完成收斂或者達(dá)到要求的最大迭代周期。此時(shí)，取出種群中最優(yōu)的染色體作為最終的任務(wù)排列結(jié)果。

3 實(shí)驗(yàn)結(jié)果分析

本文基于上述算法開發(fā)了通信衛(wèi)星資源動(dòng)態(tài)調(diào)度程序，并在相同任務(wù)數(shù)和不同任務(wù)數(shù)的條件下分別模擬仿真了資源靜態(tài)分配過程和資源動(dòng)態(tài)調(diào)度過程，最后對資源靜態(tài)分配方式和動(dòng)態(tài)調(diào)度方式下的資源利用率分別進(jìn)行了對比。

3.1 相同任務(wù)數(shù)

通過在45天的時(shí)間段內(nèi)設(shè)計(jì)35個(gè)具有不同開始時(shí)間和結(jié)束時(shí)間的通信任務(wù)，在65 MHz的頻率帶寬范圍內(nèi)分別仿真了資源靜態(tài)分配過程和資源動(dòng)態(tài)調(diào)度過程，其資源利用率的對比圖如圖4所示。

圖4 相同任務(wù)數(shù)下資源利用率對比曲線

由圖4可以看出，在前期由于運(yùn)行任務(wù)較多，資源使用密集，動(dòng)態(tài)調(diào)度方式的資源利用率會(huì)明顯高出靜態(tài)分配方式；而到了后期由于較多任務(wù)已結(jié)束，正在運(yùn)行的任務(wù)數(shù)變少，靜態(tài)分配方式與動(dòng)態(tài)調(diào)度方式的資源利用率趨于相近。

3.2 不同任務(wù)數(shù)

通過分別隨機(jī)生成5、10、15、20、25、30、35、40、45、50、55、60、65和70個(gè)通信任務(wù)在65 MHz的頻率帶寬范圍內(nèi)仿真了資源靜態(tài)分配過程和資源動(dòng)態(tài)調(diào)度過程，統(tǒng)計(jì)不同任務(wù)數(shù)下的資源利用率得到的對比圖如圖5所示。

圖5 2種方式下資源占有率對比曲線

從圖5中可以看出，靜態(tài)分配的資源利用率整體低于動(dòng)態(tài)分配的資源利用率，當(dāng)任務(wù)數(shù)大于30時(shí)，靜態(tài)分配的資源利用率基本保持在28%左右，而動(dòng)態(tài)分配的資源利用率基本保持在60%左右。

4 結(jié)束語

本文探討了如何在通信任務(wù)的時(shí)間和資源約束下，如何利用遺傳算法進(jìn)行衛(wèi)星資源動(dòng)態(tài)調(diào)度的問題，并且進(jìn)行了設(shè)計(jì)和仿真。遺傳算法的引入對于通信衛(wèi)星的資源使用效能的提高具有很大的現(xiàn)實(shí)應(yīng)用價(jià)值。

另外，本文所提出的衛(wèi)星資源動(dòng)態(tài)調(diào)度方法中考慮的約束因素和優(yōu)化目標(biāo)還可以進(jìn)行進(jìn)一步的細(xì)化和補(bǔ)充，例如考慮任務(wù)優(yōu)先級、頻率質(zhì)量等需求，使衛(wèi)星資源動(dòng)態(tài)調(diào)度方法更符合實(shí)際應(yīng)用環(huán)境。

[1] 王曉杰,羅健欣,鄭成輝,等.基于任務(wù)等級的衛(wèi)星資源分配算法研究[J].計(jì)算機(jī)時(shí)代,2016(2):11-13.

[2] 黃 睿.衛(wèi)星通信技術(shù)的應(yīng)用體會(huì)及未來趨勢展望[J].科技創(chuàng)新與應(yīng)用,2013(20):38-42.

[3] 李斌成.FDMA/DAMA衛(wèi)星通信網(wǎng)資源分配策略研究[J].無線電通信技術(shù),2014，40(6):50-53.

[4] 趙 靜,趙尚弘,李勇軍,等.中繼衛(wèi)星資源調(diào)度問題研究現(xiàn)狀與展望[J].電訊技術(shù),2012，52(11):1 837-1 843.

[5] 于 佳,宗 鵬.中國業(yè)務(wù)模型的建立和低軌衛(wèi)星資源分配的研究[C]∥第七屆衛(wèi)星通信新技術(shù)、新業(yè)務(wù)學(xué)術(shù)年會(huì)論文集.北京:中國通信學(xué)會(huì),2011:195-207.

[6] 李 斗,王 峰.寬帶衛(wèi)星Mesh網(wǎng)多址接入信道預(yù)測分配方案研究[J].電子與信息學(xué)報(bào),2008,30(4):763-767.[7] 王小平,曹立明.遺傳算法—理論、應(yīng)用與軟件實(shí)現(xiàn)[M].西安:西安交通大學(xué)出版社,2002.

[8] 李 明,黃平捷,周澤魁.基于小生境遺傳算法的矩形件優(yōu)化排樣[J].湖南大學(xué)學(xué)報(bào),2009,36(1):46-49.

[9] 申建華,鄭曉冬,趙 麟.基于遺傳算法的波束形成算法研究[J].無線電通信技術(shù),2015,41(3):83-85.

[10] 徐麗佳,蒲海波,蔣宏健.改進(jìn)遺傳算法的路徑規(guī)劃研究[J].微計(jì)算機(jī)信息,2006,2(5):251-253.

[11] 張 航,孟 艷,陳 乾,等.基于遺傳算法的通信衛(wèi)星頻譜資源運(yùn)用研究[J].軍事通信技術(shù),2007,28(3):1-5.[12] 高朝暉,岳群彬,李 偉.遺傳算法在成像衛(wèi)星計(jì)劃編制中的應(yīng)用[J].無線電工程,2013,43(12):37-40.

[13] 劉 偉,李 斌.一種改進(jìn)的基于遺傳算法的測試調(diào)度方法[J].無線電通信技術(shù),2016,42(2):37-40.

[14] 楊 力,吳志濤,王延春.一種解決衛(wèi)星網(wǎng)絡(luò)通信沖突的調(diào)度算法[J].計(jì)算機(jī)工程,2012,38(21):59-62.

[15] 杜立智,陳和平,符海東.NP完全問題研究及前景剖析[J].武漢工程大學(xué)學(xué)報(bào),2015,37(10):73-78.

[16] 黃務(wù)蘭,張 濤.基于改進(jìn)遺傳算法的帶時(shí)間窗車輛路徑問題研究[J].微型機(jī)與應(yīng)用,2016,35(13):21-24.

Research of Dynamic Scheduling Method for CommunicationSatellite Resources Based on Genetic Algorithm

LIN Yu-sheng,JIANG Hong-lei,DONG Yan-lei,GENG Ji-zhao,LIU Yue-xiao

(The54thResearchInstituteofCETC,ShijiazhuangHebei050081,China)

With the continuous development of satellite communication technology,the practical application requirement for satellite communication becomes more and more complex.In order to deal with the resource competition among networks of different communication systems,improve the utilization of satellite resources and satisfy the requirement of satellite communication to a greater extent,a dynamic scheduling method for communication satellite resources based on genetic algorithm is proposed.This paper introduces the basic constraints of communication task which is the basis of satellite resource dynamic scheduling,and describes the specific implementation process of the dynamic scheduling method combined with the genetic algorithm.At last,the dynamic scheduling method is compared with the static scheduling method through simulation experiments.The simulation results show that the dynamic scheduling method achieves higher resource utilization under the conditions of both same number and different number of tasks.

communication satellite resources；dynamic scheduling；genetic algorithm

2017-03-07

國家高技術(shù)研究發(fā)展計(jì)劃(“863”計(jì)劃)基金資助項(xiàng)目(2015AA015701)。

10.3969/j.issn.1003-3106.2017.06.05

林宇生，蔣洪磊，董彥磊，等.基于遺傳算法的通信衛(wèi)星資源動(dòng)態(tài)調(diào)度方法研究[J].無線電工程,2017,47(6):20-23.[LIN Yusheng, JIANG Honglei, DONG Yanlei,et al.Research of Dynamic Scheduling Method for Communication Satellite Resources Based on Genetic Algorithm[J].Radio Engineering,2017,47(6):20-23.]

TN915

A

1003-3106(2017)06-0020-04

林宇生 男，(1978—)，博士，高級工程師。主要研究方向：衛(wèi)星通信。

蔣洪磊 男，(1982—)，博士，高級工程師。主要研究方向：衛(wèi)星通信。