王 濤，喻 韜

(北京跟蹤與通信技術(shù)研究所，北京 100094)

0 引言

20世紀(jì)60年代以來(lái)，衛(wèi)星通信技術(shù)迅猛發(fā)展，在各領(lǐng)域都得到了廣泛發(fā)展，衛(wèi)星通信已成為天地通信、無(wú)線信息通信的最重要手段。近年來(lái)，隨著衛(wèi)星通信技術(shù)的不斷發(fā)展，在軌通信衛(wèi)星的數(shù)量和種類均得到不斷增加，可供各個(gè)行業(yè)使用的通信衛(wèi)星資源也日益豐富。因此，如何有效地挖掘通信衛(wèi)星資源使用潛力，實(shí)現(xiàn)衛(wèi)星資源規(guī)劃的不斷優(yōu)化，最大限度地滿足各類資源需求是目前衛(wèi)星通信系統(tǒng)資源管理急需解決的關(guān)鍵問(wèn)題[1-6]。

通過(guò)抽象分析，可將通信衛(wèi)星資源的統(tǒng)一規(guī)劃調(diào)度視為一種在有限的頻域和時(shí)域資源內(nèi)尋找多個(gè)針對(duì)不同用戶需求的通信任務(wù)的組合優(yōu)化問(wèn)題。文獻(xiàn)[7-9]開展了基于遺傳算法的資源動(dòng)態(tài)調(diào)度研究；文獻(xiàn)[10]提出了一種基于遺傳算法的通信衛(wèi)星資源動(dòng)態(tài)調(diào)度方法，并開展了實(shí)驗(yàn)驗(yàn)證；文獻(xiàn)[11]提出了在柵格化信息網(wǎng)環(huán)境下的衛(wèi)星接入資源調(diào)度優(yōu)化問(wèn)題，提出了一種基于貪婪算法(GA)的調(diào)度方法，并給出實(shí)驗(yàn)算例對(duì)算法進(jìn)行了分析驗(yàn)證；文獻(xiàn)[12-13]分別基于粒子群優(yōu)化算法對(duì)云計(jì)算資源調(diào)度問(wèn)題和衛(wèi)星地面站資源調(diào)度問(wèn)題開展了相應(yīng)的策略設(shè)計(jì)和方法研究。本文在上述研究基礎(chǔ)上，提出了一種基于遺傳模擬退火算法的資源規(guī)劃方法，旨在實(shí)現(xiàn)通信衛(wèi)星資源規(guī)劃的進(jìn)一步優(yōu)化，增強(qiáng)衛(wèi)星資源管理能力，提高資源規(guī)劃效率和資源利用效能。

1 通信衛(wèi)星資源規(guī)劃問(wèn)題模型

通信衛(wèi)星的資源統(tǒng)一規(guī)劃是利用有限的可用通信衛(wèi)星資源，根據(jù)各個(gè)通信任務(wù)不同的執(zhí)行時(shí)間需求和頻率帶寬需求，對(duì)各個(gè)任務(wù)進(jìn)行時(shí)間資源和頻率資源進(jìn)行匹配排列的過(guò)程，不同的匹配排列結(jié)果可能會(huì)導(dǎo)致不同的資源利用率。通信衛(wèi)星資源統(tǒng)一規(guī)劃的目標(biāo)在于如何通過(guò)優(yōu)化的算法進(jìn)行任務(wù)排列，在完成衛(wèi)星通信任務(wù)保障的同時(shí)最大限度地爭(zhēng)取通信衛(wèi)星資源的高效利用。

面向多任務(wù)的資源統(tǒng)一規(guī)劃可以采用如圖1所示的二維坐標(biāo)系表征。

圖1 通信任務(wù)二維坐標(biāo)系排列Fig.1 2D coordinate system arrangement of communication tasks

通信衛(wèi)星資源可分為時(shí)間和頻率2個(gè)維度，假設(shè)衛(wèi)星通信任務(wù)數(shù)量為n，其中第i(1≤i≤n)個(gè)任務(wù)的起止時(shí)間分別為Si和Ei，時(shí)間范圍為T1～T2(T1≤min(S1，S2，…，Sn)≤max(E1，E2，…，En)≤T2)，可用頻率范圍為F1～F2，其在二維坐標(biāo)系中形成的圖形面積記為A，n個(gè)任務(wù)排列完成后可排入二維區(qū)域內(nèi)的任務(wù)塊的面積之和記為A0。對(duì)于n個(gè)通信任務(wù)的資源統(tǒng)一規(guī)劃問(wèn)題，則可以抽象為如何找到一種n個(gè)任務(wù)的排列方式使得A0/A值最大的問(wèn)題。

2 遺傳模擬退火算法的基本思想

遺傳算法[14-15]作為一種智能優(yōu)化算法，通過(guò)特定的編碼方式，建立原問(wèn)題的解空間和特定的編碼空間之間的映射關(guān)系，使用選擇操作、交叉操作和變異操作對(duì)種群內(nèi)所有個(gè)體進(jìn)行選擇，擇優(yōu)產(chǎn)生新個(gè)體，重復(fù)進(jìn)行此過(guò)程，直到達(dá)到算法設(shè)定的收斂條件后結(jié)束。通過(guò)對(duì)該編碼空間的不斷搜索，作為對(duì)原問(wèn)題解空間搜索的替代，可以實(shí)現(xiàn)原問(wèn)題的尋優(yōu)和求解。遺傳算法模仿自然界生物遺傳尋優(yōu)的思想解決最優(yōu)解問(wèn)題，其全局搜索能力較強(qiáng)，但局部搜索能力較弱，導(dǎo)致算法的收斂速度較慢。

模擬退火優(yōu)化算法[16-17]最初來(lái)源于對(duì)固體退火過(guò)程的思考與模擬。模擬退火算法可用來(lái)解決多種組合優(yōu)化問(wèn)題，其內(nèi)能E可理解為目標(biāo)函數(shù)f，溫度T可視為控制參數(shù)t。由初始解i和控制參數(shù)初值t開始，對(duì)當(dāng)前解重復(fù)“產(chǎn)生新解→計(jì)算目標(biāo)函數(shù)差→接受或舍棄”的迭代，并逐步衰減t值，算法終止時(shí)的當(dāng)前解即為所得近似最優(yōu)解。退火過(guò)程由冷卻進(jìn)度表控制，包括控制參數(shù)的初值t及其衰減因子Δt、每個(gè)t值時(shí)的迭代次數(shù)L和停止條件S。模擬退火算法局部搜索能力強(qiáng)，具備跳出局部最優(yōu)解的能力，能夠向全局最優(yōu)解快速收斂。

綜上分析，本文通過(guò)將遺傳算法和模擬退火算法相結(jié)合，將遺傳算法的全局搜索能力和模擬退火算法的局部搜索能力進(jìn)行互補(bǔ)，提出了一種混合的改進(jìn)算法，并基于該算法思想完成通信衛(wèi)星資源規(guī)劃的方法設(shè)計(jì)。

3 基于遺傳模擬退火算法的資源規(guī)劃方法

3.1 染色體編碼

本文將每一個(gè)可能的資源分配方案都編碼為一個(gè)染色體，考慮本文解決的是任務(wù)排序問(wèn)題，常規(guī)的二進(jìn)制編碼不適用，采用十進(jìn)制的編碼方式，每一個(gè)染色體有n個(gè)基因，n表示任務(wù)的個(gè)數(shù)，任務(wù)的資源需求包括帶寬、開始時(shí)間和結(jié)束時(shí)間等屬性；衛(wèi)星資源包括頻段、起始頻率和結(jié)束頻率等屬性，基于任務(wù)屬性和衛(wèi)星資源屬性進(jìn)行編碼設(shè)計(jì)，將任務(wù)按照1，2，...，n進(jìn)行編號(hào)，整個(gè)染色體表示每個(gè)任務(wù)的資源分配順序，在進(jìn)行分配時(shí)按照頻率從低到高的規(guī)則依次尋找最先滿足任務(wù)資源需求的資源池空間，并根據(jù)適應(yīng)度函數(shù)進(jìn)行計(jì)算。

3.2 適應(yīng)度函數(shù)設(shè)計(jì)

適應(yīng)度函數(shù)主要依據(jù)資源利用率最高原則進(jìn)行設(shè)計(jì)，計(jì)算過(guò)程如下：

首先設(shè)計(jì)一個(gè)任務(wù)集合X={Wx，TSx，TEx，F(xiàn)Sx，F(xiàn)Ex}，用于表征完成排列的個(gè)體，其中Wx表示任務(wù)x的帶寬，TSx表示任務(wù)x的實(shí)際開始時(shí)間，TEx表示任務(wù)x的實(shí)際結(jié)束時(shí)間，F(xiàn)Sx表示任務(wù)x的實(shí)際起始頻率，F(xiàn)Ex表示任務(wù)x的實(shí)際終止頻率。對(duì)于每一個(gè)個(gè)體SEQi，按照其任務(wù)序列的順序依次取出相應(yīng)的通信任務(wù)，對(duì)于每一個(gè)任務(wù)t，根據(jù)實(shí)際應(yīng)用可假設(shè)其可接受的最早開始時(shí)間為t0，可接受的最晚結(jié)束時(shí)間為t1，任務(wù)持續(xù)時(shí)長(zhǎng)固定為d，任務(wù)需要的頻率帶寬為w，進(jìn)行如下排列：

① 首先在t0～t0+d的時(shí)間段內(nèi)，從起始頻率f0開始，查看f0～f0+w是否空閑，如果不空閑，則加一個(gè)頻率偏移量Δf，繼續(xù)查看f0+Δf～f0+Δf+w是否空閑，直至f0+Δf+w超出了終止頻率f1。如果可以找到空閑頻率，則將該任務(wù)塊排列在t0～t0+d時(shí)間段內(nèi)的相應(yīng)頻率位置上，將該任務(wù)放入集合X，否則繼續(xù)下一步。

② 將起始時(shí)間加一個(gè)偏移量Δt，此時(shí)搜索的時(shí)間段范圍為t0+Δt～t0+Δt+d，在該時(shí)間段內(nèi)重復(fù)步驟①的搜索過(guò)程。如果可以找到空閑資源，則將任務(wù)塊排列在t0+Δt～t0+Δt+d時(shí)間段內(nèi)的相應(yīng)頻率位置上，將該任務(wù)放入集合X，否則繼續(xù)增加偏移量Δt，直至t0+Δt+d﹥t1。如果此時(shí)仍未找到可用的頻率資源，則將該任務(wù)標(biāo)記為不可分配任務(wù)。

③ 將個(gè)體SEQi中所有任務(wù)依次排列完成后，計(jì)算其資源利用率f，即適應(yīng)度函數(shù)：

3.3 遺傳進(jìn)化設(shè)計(jì)

3.3.1 種群初始化

初始種群的產(chǎn)生時(shí)，對(duì)每個(gè)任務(wù)隨機(jī)生成一個(gè)優(yōu)先級(jí)，按照優(yōu)先級(jí)的次序分配，以形成一個(gè)個(gè)體。優(yōu)先級(jí)生成公式如下：

Priority=WightArea×Area+WeightRatio×(L/W),

式中，WightArea是面積的權(quán)重，為隨機(jī)產(chǎn)生的一個(gè)[0,1]的數(shù)；WightArea+WeightRatio=1，Area是帶寬和時(shí)間的乘積，其中帶寬單位為MHz，時(shí)間單位為天；L/W是時(shí)間與帶寬的比值。

循環(huán)m次，生成規(guī)模為m的初始種群{SEQ1，SEQ2，…，SEQm}。種群初始化示意如圖2所示。

圖2 種群初始化示意Fig.2 Schematic diagram of population initialization

3.3.2 選擇退火操作

對(duì)于規(guī)模為m的初始種群G，將種群中的m個(gè)個(gè)體依次進(jìn)行適應(yīng)度評(píng)價(jià)。原則上說(shuō)，個(gè)體適應(yīng)度值越大，該個(gè)體被遺傳到下一代的概率也越大。

選擇退火操作流程如圖3所示。

圖3 選擇退火操作流程Fig.3 Flowchart for selecting annealing operation

為了避免遺傳算法的“早熟”現(xiàn)象，使算法過(guò)早陷入局部最優(yōu)解，本文不選擇傳統(tǒng)的輪盤賭、錦標(biāo)賽等選擇方法，而是引入模擬退火的思想，對(duì)選擇的退火操作過(guò)程設(shè)計(jì)如下：

(1)隨機(jī)選擇初始群體G兩個(gè)個(gè)體pi，pj，計(jì)算個(gè)體適應(yīng)度值f(pi)和f(pj)；

(2)采用模擬退火算法中的概率思想選擇pi，pj其中之一遺傳到下一代，即：

① 如果f(pi)

② 如果f(pi)≥f(pj)，則以概率P選擇pj遺傳到下一代，其中，

(3)重復(fù)(1)、(2)，直到新一代群體中也包含m個(gè)個(gè)體。

3.3.3 交叉退火操作

交叉運(yùn)算是遺傳算法產(chǎn)生新個(gè)體的重要手段，通過(guò)讓2個(gè)父代個(gè)體以某一交叉概率產(chǎn)生新一代的個(gè)體，該方式主要用于保持種群的多樣性，但同時(shí)也導(dǎo)致進(jìn)化后期收斂速度慢的問(wèn)題，因此，在交叉運(yùn)算中考慮引入模擬退火算法，其操作流程如圖4所示。

圖4 交叉退火操作流程Fig.4 Flowchart for cross annealing operation

(1)選擇父代中的一個(gè)個(gè)體pi，記為當(dāng)前個(gè)體S。

(2)隨機(jī)選擇一個(gè)非pi的父代個(gè)體pj，將pi，pj以概率Pc進(jìn)行交叉操作，形成新個(gè)體pn，記為S′，Pc可取值為0.7，交叉運(yùn)算示意如圖5所示。

圖5 交叉運(yùn)算示意Fig.5 Schematic diagram of cross operation

根據(jù)圖5，選擇交叉點(diǎn)，保留pi中交叉點(diǎn)之前的序列(1,3,6,4)，然后將pj中的相應(yīng)任務(wù)刪除，留下的序列(5,8,7,2)拼接到pi的交叉點(diǎn)之后，形成新的個(gè)體pn。

(3)分別計(jì)算個(gè)體S和S′的個(gè)體適應(yīng)值，記作f(S)和f(S′)。

(4)采用模擬退火算法進(jìn)化，設(shè)循環(huán)次數(shù)為k，循環(huán)次數(shù)閾值為L(zhǎng)，則：

① 如果f(S)

② 如果f(S)≥f(S′)，則以概率P設(shè)定S=pn，其中，

(5)循環(huán)(2)～(4),完成對(duì)父代中一個(gè)個(gè)體的交叉運(yùn)算。

(6)循環(huán)(1)～(5)，完成對(duì)所有父代個(gè)體的交叉操作。

3.3.4變異退火操作

變異運(yùn)算是遺傳算法產(chǎn)生新個(gè)體重要的手段，通過(guò)變異的方式將父代的一個(gè)個(gè)體變化為一個(gè)新個(gè)體。同交叉操作一樣，變異操作在一定程度上影響了進(jìn)化后期的收斂速度，因此在變異操作中同樣引入模擬退火算法思想，變異退火操作流程如圖6所示。

圖6 變異退火操作流程Fig.6 Flowchart of variant annealing operation

(1)選擇父代中的一個(gè)個(gè)體pi，記為當(dāng)前個(gè)體S。

(2)以概率Pm對(duì)pi進(jìn)行變異操作，形成新個(gè)體pn，記為S′，Pm可取值0.1，變異運(yùn)算示意如圖7所示。

圖7 變異運(yùn)算示意Fig.7 Schematic diagram of mutation operation

(3)分別計(jì)算個(gè)體S和S′的個(gè)體適應(yīng)值，記作f(S)和f(S′)。

(4)采用模擬退火算法進(jìn)行進(jìn)化，設(shè)循環(huán)次數(shù)為k，循環(huán)次數(shù)閾值為L(zhǎng)，則：

① 如果f(S)

② 如果f(S)≥f(S′)，則以概率P設(shè)定S=pn，其中，

(5)循環(huán)(2)～(4),完成對(duì)父代中一個(gè)個(gè)體的變異運(yùn)算。

(6)循環(huán)(1)～(5)，完成對(duì)所有父代個(gè)體的變異操作。

3.4 算法流程

基于遺傳模擬退火算法的資源規(guī)劃流程如圖8所示。

圖8 基于遺傳模擬退火算法的資源規(guī)劃流程Fig.8 Flowchart of resource planning based on genetic simulated annealing algorithm

(1)創(chuàng)建規(guī)模為m的初始種群；

(2)對(duì)初始種群進(jìn)行選擇退火操作；

(3)對(duì)選擇退火后形成的種群進(jìn)行交叉退火操作；

(4)對(duì)交叉退火后形成的種群進(jìn)行變異退火操作；

(5)生成新的種群，并判斷是否滿足循環(huán)終止條件，一般終止條件為達(dá)到迭代次數(shù)、最優(yōu)解多次迭代無(wú)明顯變化或者最優(yōu)解達(dá)到預(yù)期目標(biāo)；如不滿足則將新的種群作為下一輪迭代的初始種群，循環(huán)(2)～(5)；

(6)循環(huán)結(jié)束后，取出此時(shí)種群中適應(yīng)度值表現(xiàn)最優(yōu)的個(gè)體，作為問(wèn)題的最優(yōu)解。

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

本文對(duì)基于遺傳模擬退火算法的資源規(guī)劃方法進(jìn)行了模擬仿真，并與傳統(tǒng)的基于遺傳算法的資源規(guī)劃方法進(jìn)行對(duì)比。對(duì)比測(cè)試分別在資源利用率和規(guī)劃執(zhí)行效率2個(gè)方面展開。

4.1 資源利用率對(duì)比

分別隨機(jī)生成10,20,30,40,50,60,70,80,90,100個(gè)通信任務(wù)，依次對(duì)2種資源規(guī)劃方式進(jìn)行仿真，其資源利用率對(duì)比結(jié)果如圖9所示。

圖9 2種規(guī)劃方式下資源利用率對(duì)比曲線Fig.9 Comparison curve of resource utilization under two planning modes

由圖9可以看出，基于遺傳模擬退火算法的資源規(guī)劃方法的資源利用率整體要略高于傳統(tǒng)的基于遺傳算法的資源規(guī)劃方法。

4.2 規(guī)劃執(zhí)行效率對(duì)比

分別隨機(jī)生成10,20,30,40,50,60,70,80,90,100個(gè)通信任務(wù)，依次對(duì)2種資源規(guī)劃方式分別仿真，其規(guī)劃任務(wù)完成時(shí)間對(duì)比結(jié)果如圖10所示。

圖10 2種規(guī)劃方式下規(guī)劃執(zhí)行效率對(duì)比曲線Fig.10 Comparison curve of planning execution efficiency under two planning modes

由圖10可以看出，基于遺傳模擬退火算法的資源規(guī)劃方法的規(guī)劃執(zhí)行率整體要優(yōu)于傳統(tǒng)的基于遺傳算法的資源規(guī)劃方法，算法性能更優(yōu)。

5 結(jié)束語(yǔ)

本文通過(guò)對(duì)通信衛(wèi)星資源統(tǒng)一規(guī)劃問(wèn)題進(jìn)行建模，并分析了遺傳算法和模擬退火算法的算法特性，提出了一種基于遺傳模擬退火算法的資源規(guī)劃方法，該方法能夠有效提高通信衛(wèi)星資源規(guī)劃效率，并在一定程度上提升資源利用率，為通信衛(wèi)星資源管理科學(xué)化、智能化水平的進(jìn)一步發(fā)展探索了新的技術(shù)道路。