衛(wèi)星網(wǎng)絡(luò)實(shí)時(shí)分組調(diào)度問(wèn)題研究.pdf

1、近年來(lái)，衛(wèi)星系統(tǒng)技術(shù)日趨成熟，衛(wèi)星系統(tǒng)的運(yùn)行管理越發(fā)變得重要，而衛(wèi)星系統(tǒng)運(yùn)行管理的最主要任務(wù)是在地面站與衛(wèi)星間進(jìn)行數(shù)據(jù)通信的調(diào)度。對(duì)衛(wèi)星網(wǎng)絡(luò)的通信調(diào)度問(wèn)題我們主要采取建模的方式。傳統(tǒng)的SRS(SatelliteRangeScheduling)調(diào)度模型:特點(diǎn)是利用整數(shù)規(guī)劃技術(shù)實(shí)現(xiàn)自動(dòng)調(diào)度，它的調(diào)度周期通常以天為單位，并且衛(wèi)星系統(tǒng)的服務(wù)主要是簡(jiǎn)單的“彎管”模式。隨著衛(wèi)星系統(tǒng)技術(shù)的不斷發(fā)展，星座網(wǎng)絡(luò)已成為下一代衛(wèi)星系統(tǒng)的突出技術(shù)，而星座維護(hù)的

2、一個(gè)關(guān)鍵問(wèn)題是衛(wèi)星系統(tǒng)之間的通信調(diào)度。
　　 星座網(wǎng)絡(luò)的發(fā)展使得衛(wèi)星網(wǎng)絡(luò)有了新的需求。星座網(wǎng)絡(luò)在地面站-衛(wèi)星通信數(shù)據(jù)調(diào)度中引入了星間鏈路的轉(zhuǎn)發(fā)能力，使得衛(wèi)星系統(tǒng)運(yùn)營(yíng)控制中對(duì)地面站的依賴度大為降低;同時(shí)為滿足二代衛(wèi)星系統(tǒng)實(shí)時(shí)控制信息刷新頻繁的需求，提高衛(wèi)星系統(tǒng)的自適應(yīng)能力，需要實(shí)現(xiàn)分鐘級(jí)短周期實(shí)時(shí)調(diào)度。
　　 由于傳統(tǒng)的SRS調(diào)度模型沒(méi)有考慮星間鏈路，并存在周期過(guò)長(zhǎng)等一系列問(wèn)題，因此它的通信任務(wù)的調(diào)度已不再適用于最新的星座

3、網(wǎng)絡(luò)，所以我們必須重新發(fā)掘一種新的星間鏈路調(diào)度模型，于是我們提出了SNRS(SatelliteNetworkRangeScheduling)調(diào)度模型，其優(yōu)點(diǎn)是在星間鏈路的使用，衛(wèi)星網(wǎng)絡(luò)通信模型和傳統(tǒng)衛(wèi)星系統(tǒng)大不相同情況下，能夠?qū)崿F(xiàn)星座網(wǎng)絡(luò)對(duì)其控制任務(wù)的一些新的通信需求。在SNRS調(diào)度模型中，衛(wèi)星通信任務(wù)已不再是簡(jiǎn)單的在目標(biāo)星和地面站之間進(jìn)行，各目標(biāo)星之間可以實(shí)現(xiàn)通信任務(wù)的調(diào)度。為了保障鏈路任務(wù)的調(diào)度可行性以及對(duì)衛(wèi)星系統(tǒng)的控制，我們需要設(shè)

4、計(jì)好的算法來(lái)保證任務(wù)調(diào)度的時(shí)限問(wèn)題。這就是我們將要研究的衛(wèi)星網(wǎng)絡(luò)實(shí)時(shí)分組調(diào)度問(wèn)題。
　　 主要研究?jī)?nèi)容如下:
　　 (1)針對(duì)星座網(wǎng)絡(luò)的新需求，即實(shí)現(xiàn)實(shí)時(shí)信息控制和提高星間鏈路的轉(zhuǎn)發(fā)能力，建立星座網(wǎng)絡(luò)的新調(diào)度模型SNRS。
　　 (2)通過(guò)將整數(shù)等劃分問(wèn)題多項(xiàng)式時(shí)間歸約到SNRS，從而證明了SNRS問(wèn)題是NP完全的。
　　 (3)通過(guò)將Three-Partitioning問(wèn)題多項(xiàng)式時(shí)間歸約到周期任務(wù)調(diào)度問(wèn)

5、題，從而證明周期任務(wù)調(diào)度問(wèn)題是NP完全的。
　　 (4)通過(guò)對(duì)固定優(yōu)先級(jí)的周期任務(wù)調(diào)度問(wèn)題進(jìn)行證明，得出如下結(jié)論:
　　 ①周期不同的兩個(gè)簡(jiǎn)單任務(wù)進(jìn)行不可搶占調(diào)度，在固定優(yōu)先級(jí)中采用短周期任務(wù)優(yōu)先策略調(diào)度為最優(yōu);
　　 ②周期相同的兩個(gè)簡(jiǎn)單任務(wù)進(jìn)行不可搶占調(diào)度，在固定優(yōu)先級(jí)中采用執(zhí)行時(shí)間長(zhǎng)任務(wù)優(yōu)先調(diào)度策略為最優(yōu);
　　 ③相位不同、周期不同的兩個(gè)簡(jiǎn)單任務(wù)進(jìn)行不可搶占調(diào)度，在固定優(yōu)先級(jí)中采用短周期任務(wù)優(yōu)先調(diào)

6、度策略為最優(yōu);
　　 ④相位不同、周期相同的兩個(gè)簡(jiǎn)單任務(wù)進(jìn)行不可搶占調(diào)度，在固定優(yōu)先級(jí)中采用執(zhí)行時(shí)間長(zhǎng)任務(wù)優(yōu)先調(diào)度策略為最優(yōu);
　　 ⑤周期不同的多個(gè)任務(wù)進(jìn)行不可搶占調(diào)度，在固定優(yōu)先級(jí)中采用短周期任務(wù)優(yōu)先調(diào)度策略為最優(yōu);
　　 ⑥周期相同的多個(gè)任務(wù)進(jìn)行不可搶占調(diào)度，在固定優(yōu)先級(jí)中采用執(zhí)行時(shí)間長(zhǎng)任務(wù)優(yōu)先調(diào)度策略為最優(yōu)。
　　 (5)通過(guò)對(duì)靜態(tài)優(yōu)先級(jí)、動(dòng)態(tài)優(yōu)先級(jí)以及SNRS進(jìn)行仿真，得出如下結(jié)論:
　　

7、 ①靜態(tài)優(yōu)先級(jí)調(diào)度下的三種情況:即相位為零、時(shí)限等于周期，相位不為零、時(shí)限等于周期，以及相位為零、時(shí)限不等于周期，這三種情況都采用短周期優(yōu)先調(diào)度策略為最優(yōu);
　　 ②動(dòng)態(tài)優(yōu)先級(jí)調(diào)度下EDF(Earliest-Deadline-First，最早時(shí)限優(yōu)先)調(diào)度策略比LST(Least-Slack-Time-First，最小空閑時(shí)間優(yōu)先)調(diào)度策略相對(duì)較優(yōu);
　　 ③EDF在決定任務(wù)命令階段勝過(guò)隨機(jī)策略且最小距離路徑比隨機(jī)路徑