1 引 言
隨著高帶寬、大容量衛(wèi)星激光通信技術(shù)的快速發(fā)展[1-4]，利用星間激光鏈路實(shí)現(xiàn)多星組網(wǎng)與用戶接入的天基激光網(wǎng)絡(luò)成為重要發(fā)展趨勢(shì)[5-6]。近幾年，以歐洲為代表的發(fā)達(dá)國家相繼開展了具有星間激光鏈路的數(shù)據(jù)中繼衛(wèi)星系統(tǒng)(TDRSS)的理論研究和星上演示驗(yàn)證[7-8]；同時(shí)我國也正在開展利用激光鏈路實(shí)現(xiàn)星間組網(wǎng)的論證工作，提出了將導(dǎo)航星座作為空間信息網(wǎng)的核心激光網(wǎng)絡(luò),實(shí)現(xiàn)定位與信息傳輸集成化的設(shè)想[9-10]。
而在這些天基激光網(wǎng)絡(luò)中，用戶的接入調(diào)度是實(shí)現(xiàn)數(shù)據(jù)可靠傳輸和資源高效利用的關(guān)鍵和難點(diǎn)所在。針對(duì)衛(wèi)星資源調(diào)度問題，學(xué)者提出了一系列算法。文獻(xiàn)[11-12]分析了衛(wèi)星通信中任務(wù)調(diào)度的一些基本原則，并通過對(duì)沖突任務(wù)執(zhí)行插空、交換等調(diào)整操作實(shí)現(xiàn)去沖突化，得到任務(wù)調(diào)度初始方案。文獻(xiàn)[13]采用并行機(jī)調(diào)度理論對(duì)中繼星調(diào)度問題進(jìn)行研究，建立了考慮任務(wù)優(yōu)先級(jí)的混合整數(shù)規(guī)劃模型，并采用貪婪隨機(jī)自適應(yīng)搜索算法對(duì)模型進(jìn)行求解，優(yōu)化了調(diào)度方案，但該模型只局限于微波鏈路。文獻(xiàn)[14-17]建立了微波/激光混合鏈路的中繼衛(wèi)星系統(tǒng)資源調(diào)度的多目標(biāo)約束規(guī)劃模型，并利用遺傳算法求解得到優(yōu)化的調(diào)度方案。文獻(xiàn)[18]針對(duì)靜態(tài)調(diào)度方案與實(shí)際應(yīng)用中任務(wù)動(dòng)態(tài)變化之間的矛盾，提出了動(dòng)態(tài)插入快速啟發(fā)式算法，一定程度上解決了激光/微波混合鏈路衛(wèi)星網(wǎng)絡(luò)的動(dòng)態(tài)調(diào)度問題，但這種算法只是在靜態(tài)調(diào)度方案的基礎(chǔ)上，針對(duì)少量任務(wù)變化進(jìn)行再適應(yīng)操作，本質(zhì)上仍為靜態(tài)調(diào)度，不能適應(yīng)任務(wù)隨時(shí)發(fā)起的情況。
可見，當(dāng)前關(guān)于天基網(wǎng)絡(luò)接入調(diào)度問題的研究集中于節(jié)點(diǎn)數(shù)量較少的中繼星系統(tǒng)，調(diào)度算法多為離線集中式算法(OCSA)。這類調(diào)度算法在調(diào)度開始前由控制中心計(jì)算生成調(diào)度方案，調(diào)度周期內(nèi)衛(wèi)星嚴(yán)格執(zhí)行調(diào)度方案中分配的天線資源。當(dāng)節(jié)點(diǎn)數(shù)量較多時(shí)，控制中心計(jì)算工作量大，且任務(wù)信息的收集、調(diào)度表的上傳等具有較高的時(shí)間成本，不具備靈活性和便利性；另外，由于任務(wù)調(diào)度表的計(jì)算具有周期性，算法不能支持實(shí)時(shí)任務(wù)。而在未來天基激光網(wǎng)絡(luò)中，網(wǎng)絡(luò)節(jié)點(diǎn)和任務(wù)數(shù)量都會(huì)大大增加，對(duì)任務(wù)等待服務(wù)的時(shí)延也將提出新的要求，離線集中式接入調(diào)度算法將嚴(yán)重制約任務(wù)執(zhí)行的實(shí)時(shí)性和網(wǎng)絡(luò)資源調(diào)度的靈活、高效性。
基于此，本文對(duì)天基激光網(wǎng)絡(luò)的在線分布式接入調(diào)度算法(ODSA)進(jìn)行研究，通過引入排隊(duì)機(jī)制實(shí)現(xiàn)了算法的在線和分布特性，并利用二維馬爾可夫鏈理論分析模型得到了算法性能參數(shù)。
2 接入調(diào)度問題
未來天基激光網(wǎng)絡(luò)架構(gòu)主要分為骨干網(wǎng)和用戶兩部分，如圖1所示(為方便作圖，圖中只給出了部分典型的激光星間鏈路)。其中跟蹤與數(shù)據(jù)中繼衛(wèi)星系統(tǒng)(TDRSS)、通信衛(wèi)星系統(tǒng)及導(dǎo)航星座中的中軌衛(wèi)星(MEO)等數(shù)量眾多的衛(wèi)星節(jié)點(diǎn)通過激光鏈路連接起來構(gòu)成天基激光網(wǎng)絡(luò)的骨干網(wǎng)，為各類以低軌衛(wèi)星為主體的用戶提供接入與數(shù)據(jù)中繼傳輸服務(wù)。天基激光網(wǎng)絡(luò)接入調(diào)度問題屬于資源調(diào)度類問題，被調(diào)度的資源為激光接入鏈路，調(diào)度目標(biāo)為最小化任務(wù)的等待時(shí)延。天基激光網(wǎng)絡(luò)接入調(diào)度問題具有如下特點(diǎn)：
1) 接入問題具有可見時(shí)間窗口約束。可見時(shí)間窗口是指骨干網(wǎng)節(jié)點(diǎn)對(duì)用戶的覆蓋時(shí)段，即二者可進(jìn)行直接通信的時(shí)間段的集合。用戶只有在可見時(shí)間窗口內(nèi)，才能接入相應(yīng)的骨干網(wǎng)節(jié)點(diǎn)接受服務(wù)，因此可見時(shí)間窗口是接入調(diào)度的一個(gè)重要約束條件。
2) 任務(wù)具有優(yōu)先級(jí)約束。在天基激光網(wǎng)絡(luò)中，任務(wù)可分為實(shí)時(shí)任務(wù)與非實(shí)時(shí)任務(wù)，實(shí)時(shí)任務(wù)對(duì)等待時(shí)延要求高，任務(wù)一經(jīng)發(fā)起就希望馬上得到服務(wù)，如實(shí)時(shí)偵察視頻和圖像數(shù)據(jù)的即時(shí)回傳；非實(shí)時(shí)任務(wù)對(duì)等待時(shí)延要求不高，任務(wù)發(fā)起并等待一段時(shí)間后再接受服務(wù)，如環(huán)境觀測(cè)衛(wèi)星、電子測(cè)繪衛(wèi)星等數(shù)據(jù)的回傳。
3) 骨干網(wǎng)節(jié)點(diǎn)對(duì)用戶形成多重覆蓋。與地面蜂窩移動(dòng)通信網(wǎng)和低軌衛(wèi)星通信網(wǎng)的拼接覆蓋模式不同，天基激光網(wǎng)絡(luò)由于軌道高度較高，對(duì)低軌衛(wèi)星形成多重覆蓋。因此用戶在接入時(shí)需要根據(jù)某種原則從多個(gè)可見接入節(jié)點(diǎn)中做出合理的選擇。
4) 激光鏈路的單址特性和發(fā)散角小的特點(diǎn)使其不具備廣播功能，這對(duì)于由控制中心進(jìn)行鏈路統(tǒng)一調(diào)度的離線集中式調(diào)度算法不會(huì)產(chǎn)生影響，但對(duì)于在線調(diào)度算法，要實(shí)現(xiàn)激光鏈路的自動(dòng)建立和調(diào)度算法的自主運(yùn)行，在鏈路建立之前必須要進(jìn)行必要的握手通信和可見用戶任務(wù)信息的收集，該工作可由具備廣播能力的低速率微波鏈路實(shí)現(xiàn)。在后續(xù)的算法討論中，假設(shè)天基激光網(wǎng)絡(luò)中的所有節(jié)點(diǎn)均具備支持算法實(shí)現(xiàn)的微波鏈路。
3 接入調(diào)度算法
為實(shí)現(xiàn)天基激光網(wǎng)絡(luò)中任務(wù)的在線調(diào)度，受地面蜂窩移動(dòng)通信網(wǎng)中的呼叫接入控制思想[19]啟發(fā)，引入了排隊(duì)模型，任務(wù)發(fā)起后選擇一個(gè)可見的骨干網(wǎng)節(jié)點(diǎn)加入其等待隊(duì)列，避免了控制中心集中規(guī)劃計(jì)算的環(huán)節(jié)。為實(shí)現(xiàn)這一過程，將接入調(diào)度問題分為鏈路調(diào)度子問題和接入選擇子問題。
3.1 鏈路調(diào)度算法
設(shè)網(wǎng)絡(luò)中存在實(shí)時(shí)與非實(shí)時(shí)兩種任務(wù)類型，由于激光接入鏈路為單址鏈路，一個(gè)接入節(jié)點(diǎn)上的實(shí)時(shí)與非實(shí)時(shí)任務(wù)需要共用一個(gè)唯一的信道，屬于單服務(wù)臺(tái)排隊(duì)系統(tǒng)。為保證不同任務(wù)的不同要求，必須要采用合理的調(diào)度策略。
采用具有搶占優(yōu)先權(quán)的鏈路調(diào)度策略，調(diào)度模型如圖2所示。對(duì)于非實(shí)時(shí)任務(wù)，采用排隊(duì)模型進(jìn)行處理：任務(wù)接入某一骨干網(wǎng)節(jié)點(diǎn)后，進(jìn)入隊(duì)列等待接受服務(wù)，若
則任務(wù)服務(wù)失敗，需重新發(fā)起接入請(qǐng)求。式中 Tc(t) 為當(dāng)前時(shí)刻接入節(jié)點(diǎn)對(duì)用戶的剩余覆蓋時(shí)間，Tw(t) 為任務(wù)從當(dāng)前時(shí)刻到被執(zhí)行時(shí)刻所需要的等待時(shí)間，Ts 為任務(wù)執(zhí)行所需的時(shí)間。(1)式的含義為：如果不能在可見時(shí)段內(nèi)完成整個(gè)任務(wù)，則該任務(wù)將被從該隊(duì)列中刪除，并重新選擇接入節(jié)點(diǎn)進(jìn)行排隊(duì)。該策略保證了非實(shí)時(shí)任務(wù)能在一個(gè)接入節(jié)點(diǎn)上完成傳輸，避免了正在傳輸時(shí)因?yàn)椴粷M足可見時(shí)間窗口約束而發(fā)生中斷的情況。
對(duì)于實(shí)時(shí)任務(wù)，任務(wù)發(fā)起后不允許等待，因此應(yīng)賦予其搶占優(yōu)先權(quán)，即任務(wù)到達(dá)后不參加排隊(duì)等待，而是選擇那些正在服務(wù)非實(shí)時(shí)任務(wù)的接入節(jié)點(diǎn)，并搶占其鏈路資源。若所有可見節(jié)點(diǎn)都正在服務(wù)實(shí)時(shí)任務(wù)，則沒有資源可以搶占，接入請(qǐng)求被阻塞。為保證實(shí)時(shí)性，實(shí)時(shí)任務(wù)在接入時(shí)不受(1)式的約束，如果傳輸過程中當(dāng)前節(jié)點(diǎn)不再可見，則需要從當(dāng)前節(jié)點(diǎn)向其他節(jié)點(diǎn)切換。
3.2 接入點(diǎn)選擇算法
在OCSA算法中，用戶接入哪個(gè)骨干網(wǎng)節(jié)點(diǎn)由控制中心統(tǒng)一安排調(diào)度，而在ODSA中，用戶需自主做出接入選擇。通常采用的接入選擇算法有距離優(yōu)先算法、覆蓋時(shí)間優(yōu)先算法、仰角加權(quán)的覆蓋時(shí)間優(yōu)先算法[20]等。距離優(yōu)先算法根據(jù)信號(hào)平均功率強(qiáng)度，在距離最近的衛(wèi)星上尋找空閑信道；覆蓋時(shí)間優(yōu)先算法在呼叫建立時(shí)選取對(duì)當(dāng)前呼叫覆蓋時(shí)間最長的衛(wèi)星優(yōu)先接入，仰角加權(quán)的覆蓋時(shí)間優(yōu)先算法通過對(duì)覆蓋時(shí)間、衛(wèi)星仰角2個(gè)變量分別加權(quán)計(jì)算得到目標(biāo)函數(shù)，作為多星選擇的依據(jù)。這些算法主要針對(duì)近似拼接覆蓋的低軌衛(wèi)星星座，結(jié)合天基激光網(wǎng)絡(luò)多重覆蓋的特點(diǎn)，在這些算法的基礎(chǔ)上提出了覆蓋時(shí)間與隊(duì)列長度相給合的接入選擇算法。
設(shè)天基激光網(wǎng)絡(luò)對(duì)用戶的平均覆蓋重?cái)?shù)(即在任務(wù)發(fā)起時(shí)刻，用戶衛(wèi)星的平均可見骨干網(wǎng)節(jié)點(diǎn)數(shù))為 Z ，覆蓋時(shí)間為 T(i)c ，骨干網(wǎng)節(jié)點(diǎn)上的隊(duì)列長度為 L(i)q ，其中 i = 1,2,?,Z 為接入節(jié)點(diǎn)序號(hào)。對(duì)于非實(shí)時(shí)任務(wù)，接入選擇的目標(biāo)函數(shù) fN(Tc,Lq) 需滿足
上述約束條件保證：1) 用戶會(huì)選擇覆蓋時(shí)間長的衛(wèi)星接入，從而減少任務(wù)因不滿足時(shí)間窗口約束而重新發(fā)起的頻率；2) 用戶會(huì)選擇隊(duì)列長度小的衛(wèi)星接入，從而降低自身的等待時(shí)延并實(shí)現(xiàn)骨干網(wǎng)節(jié)點(diǎn)間的負(fù)載均衡。考慮到非實(shí)時(shí)任務(wù)不允許在執(zhí)行過程中發(fā)生接入節(jié)點(diǎn)間的切換，在接入選擇時(shí)應(yīng)保證覆蓋時(shí)間大于任務(wù)執(zhí)行所需時(shí)間，接入選擇算法可描述為
式中 is 為被選擇的接入節(jié)點(diǎn)。若在任務(wù)發(fā)起時(shí)所有可見接入節(jié)點(diǎn)上隊(duì)列均已滿，則接入請(qǐng)求被阻塞。
對(duì)于實(shí)時(shí)任務(wù)，由于具有搶占優(yōu)先級(jí)，目標(biāo)函數(shù) fR(Tc) 不需要考慮隊(duì)列長度的影響，當(dāng)
實(shí)時(shí)任務(wù)允許發(fā)生節(jié)點(diǎn)間切換，接入時(shí)不需要考慮覆蓋時(shí)間是否大于任務(wù)執(zhí)行時(shí)間，接入選擇算法可描述為
在任務(wù)發(fā)起或發(fā)生切換時(shí)，若所有可見接入節(jié)點(diǎn)都正在服務(wù)實(shí)時(shí)任務(wù)，則接入請(qǐng)求被阻塞。
4 算法性能分析
4.1 ODSA的性能分析
4.1.1 任務(wù)服務(wù)時(shí)間
設(shè) TCR 為實(shí)時(shí)任務(wù)的持續(xù)時(shí)間，為分析方便，假設(shè) TCR 服從期望 E(TCR) =1 μCR 的負(fù)指數(shù)分布；設(shè) TCN 為非實(shí)時(shí)任務(wù)的持續(xù)時(shí)間，服從 E(TCN) =1 μCN 的負(fù)指數(shù)分布；設(shè) Tc 為接入時(shí)骨干網(wǎng)節(jié)點(diǎn)對(duì)用戶衛(wèi)星的覆蓋時(shí)長，服從 E(Tc) =1 μc 的負(fù)指數(shù)分布。
對(duì)于正在接受服務(wù)的實(shí)時(shí)任務(wù)，將一直占用鏈路直至服務(wù)完成或者因?yàn)榕c接入節(jié)點(diǎn)不再可見而切換至另一個(gè)節(jié)點(diǎn)。因此，實(shí)時(shí)任務(wù)在一個(gè)接入節(jié)點(diǎn)上的服務(wù)時(shí)間 TR 是 TCR 與 Tc 中的最小值。由于 TCR 與 Tc 相互獨(dú)立，由指數(shù)分布的無記憶性可知，TR 也服從指數(shù)分布，期望為
對(duì)于未被實(shí)時(shí)任務(wù)搶占的非實(shí)時(shí)任務(wù)，它將一直占用鏈路直至服務(wù)完成，或者因?yàn)椴荒茉诋?dāng)前鏈路上完成任務(wù)而被拒絕，因此，非實(shí)時(shí)任務(wù)在一個(gè)接入節(jié)點(diǎn)上的服務(wù)時(shí)間 TN 與 TCN 相同：
4.1.2 各種任務(wù)的到達(dá)過程
設(shè)整個(gè)網(wǎng)絡(luò)中實(shí)時(shí)與非實(shí)時(shí)任務(wù)的到達(dá)過程是強(qiáng)度分別為 λOR′、λON′的泊松分布，并且位置分布是均勻的，骨干網(wǎng)節(jié)點(diǎn)總數(shù)為 M ，則對(duì)于單個(gè)接入節(jié)點(diǎn)，任務(wù)到達(dá)過程服從 λOR = λOR′ M 和 λON = λON′ M 的泊松分布。
對(duì)于實(shí)時(shí)任務(wù)，如果服務(wù)時(shí)間比覆蓋時(shí)間長，則會(huì)向臨近接入節(jié)點(diǎn)提出切換請(qǐng)求。假設(shè)天基激光網(wǎng)絡(luò)中所有接入節(jié)點(diǎn)均相同，則對(duì)于任意接入節(jié)點(diǎn)來說，單位時(shí)間內(nèi)進(jìn)入該節(jié)點(diǎn)的切換請(qǐng)求平均數(shù)等于離開該節(jié)點(diǎn)的切換請(qǐng)求平均數(shù)。令 λHR 表示切換任務(wù)的到達(dá)強(qiáng)度，易得
式中 E(CR) 為鏈路上實(shí)時(shí)任務(wù)的占用率。
對(duì)于非實(shí)時(shí)任務(wù)，如果隊(duì)列中排隊(duì)等待的任務(wù)在接受服務(wù)之前離開了接入節(jié)點(diǎn)的可見范圍，則該任務(wù)向其他節(jié)點(diǎn)重新發(fā)起接入請(qǐng)求，即被轉(zhuǎn)移到其他接入節(jié)點(diǎn)。對(duì)于任意接入節(jié)點(diǎn)，設(shè)從其他節(jié)點(diǎn)轉(zhuǎn)移過來的非實(shí)時(shí)任務(wù)到達(dá)強(qiáng)度為 λTN ，易得
式中 Lq 是隊(duì)列平均長度。這里假設(shè)上述兩種到達(dá)過程均服從泊松分布。
4.1.3 二維馬爾可夫分析模型
利用非負(fù)整數(shù)對(duì) v = (i,j) 表示接入節(jié)點(diǎn)的狀態(tài)，i 表示系統(tǒng)中實(shí)時(shí)任務(wù)數(shù)，j 表示系統(tǒng)中非實(shí)時(shí)任務(wù)數(shù)（包括正在排隊(duì)的任務(wù)和正在接受服務(wù)的任務(wù)），則 (i,j) 是一個(gè)二維馬爾可夫鏈，狀態(tài)空間 V 為
式中，QD 為隊(duì)列容量。
在ODSA算法中，系統(tǒng)的狀態(tài)轉(zhuǎn)移由以下事件驅(qū)動(dòng)：1) 新發(fā)起的非實(shí)時(shí)任務(wù)到達(dá)；2) 由其他節(jié)點(diǎn)轉(zhuǎn)移到該節(jié)點(diǎn)的非實(shí)時(shí)任務(wù)到達(dá)；3) 新發(fā)起的實(shí)時(shí)任務(wù)到達(dá)；4) 切換到該節(jié)點(diǎn)的實(shí)時(shí)任務(wù)到達(dá)；5) 非實(shí)時(shí)任務(wù)離開；6) 實(shí)時(shí)任務(wù)離開。值得注意的是，3) 和4) 事件可能會(huì)引起非實(shí)時(shí)任務(wù)的中斷，被中斷的非實(shí)時(shí)任務(wù)返回到隊(duì)列中進(jìn)行等待。
為方便起見，做如下定義:
則系統(tǒng)的狀態(tài)轉(zhuǎn)移圖如圖3所示：
針對(duì)每個(gè)狀態(tài)，根據(jù)流入速率等于流出速率的原則可以得到一個(gè)穩(wěn)態(tài)時(shí)的平衡方程，這樣共可得到2QD + 1個(gè)方程。其中，任一方程都可以由其他 2QD 個(gè)表示，任意去掉其中一個(gè)可得到 2QD 個(gè)不相關(guān)的方程。另有狀態(tài)概率歸一化條件：
4.2 OCSA的性能分析
為便于對(duì)比ODSA與OCSA算法的性能，將時(shí)延與阻塞率的概念引入到OCSA算法中。建立OCSA算法時(shí)延與阻塞率分析模型如下：
設(shè)OCSA算法的調(diào)度周期為 T ，任務(wù)到達(dá)過程服從參數(shù)為 λ的泊松分布。算法在每個(gè)調(diào)度周期的開始時(shí)刻收集上一個(gè)周期內(nèi)發(fā)起的任務(wù)信息并計(jì)算生成調(diào)度表，然后開始按調(diào)度表執(zhí)行這些任務(wù)，如圖4所示。
圖中 tk 為任務(wù) k 發(fā)起與上一任務(wù)發(fā)起的時(shí)間間隔，服從1 λ的負(fù)指數(shù)分布。由上述分析可知，任務(wù)的等待時(shí)延 Td 由兩部分構(gòu)成，即任務(wù)發(fā)起時(shí)刻到控制中心開始計(jì)算調(diào)度表時(shí)的等待時(shí)間 Td1 和調(diào)度計(jì)算完成到該任務(wù)被執(zhí)行的等待時(shí)間 Td2 。為便于計(jì)算，將模型作簡(jiǎn)化：Td = Td1 。令 n = λT 為一個(gè)調(diào)度周期內(nèi)平均到達(dá)的任務(wù)總數(shù)，則當(dāng) n μ < T ，即 λ ≤ μ 時(shí)，所有任務(wù)均能在一個(gè)調(diào)度周期內(nèi)完成；否則只能為 nmax = μT 個(gè)任務(wù)安排調(diào)度，因此OCSA算法的時(shí)延與阻塞率分別為
可見，OCSA算法中由于調(diào)度周期 T 的存在，任務(wù)平均等待時(shí)延大大增加，T 一般為小時(shí)量級(jí)，則等待時(shí)間也為小時(shí)量級(jí)，基本不具備實(shí)時(shí)性。
5 仿真及結(jié)果分析
5.1 仿真場(chǎng)景
采用27顆骨干網(wǎng)衛(wèi)星、多顆低軌用戶衛(wèi)星的場(chǎng)景開展仿真實(shí)驗(yàn)，假設(shè)每顆衛(wèi)星上均載有一個(gè)激光接入鏈路和用于傳遞握手信息的低速率微波鏈路。其中骨干網(wǎng)衛(wèi)星包括由24顆中軌衛(wèi)星構(gòu)成的導(dǎo)航星座和由均勻分布在同步軌道上的3顆地球同步衛(wèi)星構(gòu)成的中繼衛(wèi)星星座，軌道參數(shù)如表1所示。利用軌道計(jì)算軟件計(jì)算并統(tǒng)計(jì)得到覆蓋重?cái)?shù) Z = 8 ，平均可見時(shí)間段長度 E(Tc) =1 μc = 1800 s 。
設(shè)實(shí)時(shí)與非實(shí)時(shí)任務(wù)的平均執(zhí)行時(shí)間均為10 min，即 E(TCR) =1 μCR = 600 s ，E(TCN) =1 μCN = 600 s ，接入節(jié)點(diǎn)上隊(duì)列容量 QD = 30 ，離線集中式算法調(diào)度周期 T = 1 h 。另外，定義 ρR = λOR E(TCR) 、ρN = λON E(TCN) (單位為erl，erl是話務(wù)量的單位，話務(wù)量為呼叫次數(shù)與每次呼叫的平均占用時(shí)長的乘積)分別為到達(dá)某一接入點(diǎn)的實(shí)時(shí)與非實(shí)時(shí)業(yè)務(wù)強(qiáng)度，ρ = ρR + ρN 為總業(yè)務(wù)強(qiáng)度。
圖5和圖6分別給出了平均隊(duì)列長度和平均等待時(shí)延隨總業(yè)務(wù)強(qiáng)度的變化曲線。從圖中可以看出，非實(shí)時(shí)任務(wù)在任務(wù)發(fā)起后平均等待不到半小時(shí)的時(shí)間就可得到服務(wù)。另外，當(dāng)業(yè)務(wù)強(qiáng)度增加時(shí)，隊(duì)列長度和等待時(shí)延均隨之增加，其中，業(yè)務(wù)強(qiáng)度中實(shí)時(shí)業(yè)務(wù)的成分越高，隊(duì)列長度和非實(shí)時(shí)任務(wù)的等待時(shí)延就越大。
這是由實(shí)時(shí)業(yè)務(wù)具有搶占優(yōu)先級(jí)造成的，當(dāng)實(shí)時(shí)業(yè)務(wù)增加時(shí)，網(wǎng)絡(luò)中更多的接入節(jié)點(diǎn)被搶占，從而導(dǎo)致非實(shí)時(shí)任務(wù)的等待時(shí)延變長。
圖7給出了網(wǎng)絡(luò)中實(shí)時(shí)任務(wù)和非實(shí)時(shí)任務(wù)的阻塞率隨業(yè)務(wù)強(qiáng)度的變化曲線。圖中顯示，兩種類型任務(wù)的阻塞率均隨業(yè)務(wù)強(qiáng)度的增強(qiáng)而增加，其中實(shí)時(shí)任務(wù)阻塞率在0.1左右，明顯大于非實(shí)時(shí)任務(wù)的阻塞率。因?yàn)閷?shí)時(shí)任務(wù)不參加排隊(duì)，要么被服務(wù)、要么被阻塞，因此更易被阻塞；但實(shí)時(shí)任務(wù)具有搶占優(yōu)先權(quán)，因此受非實(shí)時(shí)任務(wù)強(qiáng)度的影響較小，阻塞率曲線與非實(shí)時(shí)任務(wù)相比更為平緩。
為了突出在線分布式調(diào)度算法在實(shí)時(shí)性上的優(yōu)勢(shì)，分析了離線集中式算法的性能分析模型并將二者進(jìn)行對(duì)比，圖 8和圖 9分別給出了時(shí)延和阻塞率的對(duì)比結(jié)果。結(jié)果顯示，ODSA算法將任務(wù)等待時(shí)延降低了10%以上，阻塞率降低了90%以上。仿真場(chǎng)景中OCSA算法調(diào)度周期設(shè)置為1 h，從實(shí)際操作的角度考慮，這已經(jīng)是非常高的調(diào)度頻率了，實(shí)際應(yīng)用中調(diào)度周期可能會(huì)更長，任務(wù)等待接受服務(wù)的時(shí)間也將大幅增加，此時(shí)在線分布式算法的優(yōu)勢(shì)也就更明顯。
6 結(jié) 論
針對(duì)離線集中式衛(wèi)星資源調(diào)度算法不能有效適應(yīng)未來天基激光網(wǎng)絡(luò)任務(wù)與資源動(dòng)態(tài)變化和不能滿足任務(wù)高實(shí)時(shí)性的問題，提出了在線分布式接入調(diào)度算法。算法利用排隊(duì)模型有效解決了在線接入調(diào)度問題，與傳統(tǒng)的離線集中式算法相比，該算法避免了周期性的計(jì)算任務(wù)調(diào)度表，提高了任務(wù)調(diào)度效率，將任務(wù)等待時(shí)延縮減10%，阻塞率降低90%；該模型引入了實(shí)時(shí)與非實(shí)時(shí)兩種不同的任務(wù)類型，通過賦予實(shí)時(shí)任務(wù)搶占優(yōu)先權(quán)，使其能夠在發(fā)起后馬上得到服務(wù)，保證了實(shí)時(shí)性。在線分布式調(diào)度算法提高了用戶接入調(diào)度的靈活性和實(shí)效性，對(duì)未來天基激光網(wǎng)絡(luò)建設(shè)具有重要意義。下一步的研究將考慮引入調(diào)度優(yōu)化機(jī)制，進(jìn)一步優(yōu)化任務(wù)等待時(shí)延，提高網(wǎng)絡(luò)資源利用率。
參 考 文 獻(xiàn)
1 R J Cesarone, D S Abraham, S Shambayati, et al.. Deep-space optical communications[C]. ICSOS, 2011: 410-423.
2 Zhao Shanghong, Wu Jili, Li Yongjun, et al.. Present status and developing trends of satellite laser communication[J]. Laser & Optoelectronics Progress, 2011, 48(9): 092801.
趙尚弘, 吳繼禮, 李勇軍, 等. 衛(wèi)星激光通信現(xiàn)狀與發(fā)展趨勢(shì)[J]. 激光與光電子學(xué)進(jìn)展, 2011, 48(9): 092801.
3 Zhang Zhen, Sun Jianfeng, Lu Bin, et al.. Costas optical phase lock loop system design in inter- orbit coherent laser communication[J]. Chinese J Lasers, 2015, 42(8): 0805006.
張 震, 孫劍鋒, 盧 斌, 等. 星間相干激光通信中科斯塔斯鎖相系統(tǒng)設(shè)計(jì)[J]. 中國激光, 2015, 42(8): 0805006.
4 S Chan, V W S Chan. Constellation topologies for a space-based information network backbone using optical intersatellite links[C]. MILCOM, 2004: 812-821.
5 Zhao Xin, Song Yansong, Tong Shoufeng, et al.. Dynamic demonstration experiment of acquisition, pointing and tracking system in space laser communications[J]. Chinese J Lasers, 2014, 41(3): 0305005.
趙 馨, 宋延嵩, 佟首峰, 等. 空間激光通信捕獲、對(duì)準(zhǔn)、跟蹤系統(tǒng)動(dòng)態(tài)演示實(shí)驗(yàn)[J]. 中國激光, 2014, 41(3): 0305005.
6 Jiang Huilin, Jiang Lun, Song Yansong, et al.. Research of optical and APT technology in one- point to multi- point simultaneous space laser communication system[J]. Chinese J Lasers, 2014, 42(4): 0405008.
姜會(huì)林, 江 倫, 宋延嵩, 等. 一點(diǎn)對(duì)多點(diǎn)同時(shí)空間激光通信光學(xué)跟瞄技術(shù)研究[J]. 中國激光, 2015, 42(4): 0405008.
7 T Hanada, S Yamakawa, H Kohata. Study of optical inter-orbit communication technology for nest generation space data relay satellite[C]. SPIE, 2011, 7923: 792308.
8 K Bohmer, M Gregory, F Heine, et al.. Laser communication terminals for the European data relay system[C]. SPIE, 2012,8246: 82460D.
9 Chang Qing, Li Xianxu, He Shanbao. Confer on the evolution of earth-space integrated information network of China[J].Journal of Telemetry, Tracking and Command, 2015, 36(1): 1-10.
常 青, 李顯旭, 何善寶. 我國空間信息網(wǎng)發(fā)展探討[J]. 遙測(cè)遙控, 2015, 36(1): 1-10.
10 Zhou Hongbin, Xiao Yongwei, Lu Shan. Development and enlightenment of integrated space-based information system[J].Radio Engineering, 2015, 45(4): 12-15.
周紅彬, 肖永偉, 盧 山. 天基信息系統(tǒng)一體化發(fā)展與啟示[J]. 無線電工程, 2015, 45(4): 12-15.
11 D Stottler. Satellite communication scheduling, optimization, and deconfliction using artificial intelligence techniques[C].AIAA Infotech@Aerospace, 2010: 1-9.
12 Chen Lijiang, Wu Xiaoyue, Li Yunfeng. Scheduling algorithm for relaying satellite based on temporal flexibility[J].Aeronautical Computing Technique, 2006, 36(4): 48-51.
陳理江, 武小悅, 李云峰. 基于時(shí)間靈活度的中繼衛(wèi)星調(diào)度算法[J]. 航空計(jì)算技術(shù), 2006, 36(4): 48-51.
13 S Rojanasoonthon, J Bard. A GRASP for parallel machine scheduling with time windows[J]. Journal on Computing, 2005,17(1): 32-51.
14 Zhao Jing, Zhao Weihu, Li Yongjun, et al.. Multi-objective resources scheduling algorithm for microwave and laser hybrid links data relay satellite based on improved NSGA-II algorithm[J]. Chinese J Lasers, 2013, 40(12): 1205003.
趙 靜, 趙衛(wèi)虎, 李勇軍, 等. 基于改進(jìn)NSGA-II算法的微波/光混合鏈路中繼衛(wèi)星多目標(biāo)資源調(diào)度算法[J]. 中國激光, 2013,40(12): 1205003.
15 Zhao Jing, Zhao Weihu, Li Yongjun, et al.. Schdeuling algorithm for data relay satellite with microwave and laser hybrid links [J]. Chinese J Lasers, 2013, 40(10): 1005005.
趙 靜, 趙衛(wèi)虎, 李勇軍, 等. 微波/光混合鏈路數(shù)據(jù)中繼衛(wèi)星系統(tǒng)資源調(diào)度算法[J]. 中國激光, 2013, 40(10): 1005005.
16 Zhao Weihu, Zhao Jing, Zhao Shanghong, et al.. Resources scheduling for data relay satellite with microwave and optical hybrid links based on improved niche genetic algorithm[J]. Optik, 2014, 125(13): 3370-3375.
17 Zhao Jing, Zhao Weihu, Li Yongjun, et al.. Resources scheduling of data relay satellite with microwave and laser links based on adaptive niche genetic algorithms[J]. Journal of Optoelectronics·Laser, 2014, (1): 76-81.
趙 靜, 趙衛(wèi)虎, 李勇軍, 等. 基于改進(jìn)小生境遺傳算法的微波/光混合鏈路中繼衛(wèi)星資源調(diào)度方法[J]. 光電子·激光, 2014, (1):76-81.
18 Zhao Weihu, Zhao Jing, Zhao Shanghong, et al.. Dynamic schdeuling fast heuristic algorithm for data relay satellite with microwave and laser hybrid links[J]. Chinese J Lasers, 2014, 41(9): 0905007.
趙衛(wèi)虎, 趙 靜, 趙尚弘, 等. 微波與激光混合鏈路中繼衛(wèi)星動(dòng)態(tài)調(diào)度快速啟發(fā)式算法[J]. 中國激光, 2014, 41(9): 0905007.
19 Gong Wenbin, Gan Zhongmin. Call admission control scheme in voice/data integration mobile communication system[J].Journal of China Institute of Communications, 2004, 25(3): 18-25.
龔文斌, 甘仲民. 多業(yè)務(wù)移動(dòng)通信系統(tǒng)中的呼叫接入控制[J]. 通信學(xué)報(bào), 2004, 25(3): 18-25.
20 Zhang Huatao, Sun Fuchun, Xu Fanjiang. Studies on access strategy of layered satellite networks[J]. Computer Engineering and Design, 2005, 26(5): 1121-1124.
張華濤, 孫富春, 徐帆江. 分層衛(wèi)星網(wǎng)絡(luò)中的接入策略研究[J]. 計(jì)算機(jī)工程與設(shè)計(jì), 2005, 26(5): 1121-1124.