光纖網(wǎng)絡(luò)實(shí)時(shí)性可調(diào)度算法與多信道分配研究

湯 海

（西安工業(yè)大學(xué)電子信息工程學(xué)院 西安 710021）

1 引言

機(jī)載通信需求的快速增長(zhǎng)促使機(jī)載通信向網(wǎng)絡(luò)化的方向不斷發(fā)展，作為連接衛(wèi)星網(wǎng)絡(luò)和地面網(wǎng)絡(luò)的空中通信重要樞紐，光纖網(wǎng)絡(luò)具有諸多區(qū)別于無(wú)線移動(dòng)網(wǎng)絡(luò)的新特征，包括大尺度三維稀疏分布場(chǎng)景、長(zhǎng)傳輸范圍、移動(dòng)軌跡可預(yù)測(cè)等。此外，光纖網(wǎng)絡(luò)傳輸帶寬需求急劇增加，需要支持例如普通消息、音頻、視頻和多服務(wù)通信等多種通信方式。因此，光纖網(wǎng)絡(luò)的實(shí)時(shí)性可調(diào)度算法和多信道分配架構(gòu)分析成為研究的熱點(diǎn)。國(guó)內(nèi)外文獻(xiàn)在實(shí)時(shí)調(diào)度研究方面做了大量研究，文獻(xiàn)［1～3］均提出對(duì)實(shí)時(shí)調(diào)度領(lǐng)域經(jīng)典算法-速率單調(diào)調(diào)度算法/最早截止期限優(yōu)先調(diào)度算法的改進(jìn)算法，并進(jìn)行了延遲性能比較。文獻(xiàn)［4］證明了單信道輪轉(zhuǎn)調(diào)度可應(yīng)用在強(qiáng)實(shí)時(shí)環(huán)境下，然而帶寬碎片的大量存在導(dǎo)致較低的信道利用率。本文給出了機(jī)載應(yīng)用環(huán)境下的消息調(diào)度模型和實(shí)時(shí)調(diào)度的輪轉(zhuǎn)約束條件，提出一種保證機(jī)載網(wǎng)絡(luò)強(qiáng)實(shí)時(shí)性的加權(quán)輪轉(zhuǎn)調(diào)度算法，根據(jù)確定性網(wǎng)絡(luò)演算理論給出實(shí)時(shí)性能分析和系統(tǒng)能耗模型。

2 機(jī)載網(wǎng)絡(luò)體系結(jié)構(gòu)

機(jī)載航空網(wǎng)絡(luò)的數(shù)據(jù)流可看作是由緊急消息、周期消息、事件消息和大數(shù)據(jù)塊消息組合而成混合消息數(shù)據(jù)集。不同類型消息的數(shù)據(jù)流對(duì)實(shí)時(shí)性要求也不相同。緊急消息用于模擬對(duì)實(shí)時(shí)性要求非常高的關(guān)鍵性數(shù)據(jù)業(yè)務(wù)，如飛行控制、武器發(fā)射指令等；周期消息用于模擬一般關(guān)鍵性的實(shí)時(shí)周期性的數(shù)據(jù)業(yè)務(wù)，如雷達(dá)、傳感器的數(shù)據(jù)采集等；事件消息用于模擬對(duì)實(shí)時(shí)性要求不高的消息，如設(shè)備運(yùn)行狀況等；大數(shù)據(jù)塊消息用于模擬對(duì)實(shí)時(shí)性要求最低的、大量的數(shù)據(jù)傳輸，如視頻數(shù)據(jù)等。消息調(diào)度模型在航空電子系統(tǒng)中，雷達(dá)、電子戰(zhàn)以及通信等不同種類的機(jī)載設(shè)備進(jìn)行周期性數(shù)據(jù)的采集等。由機(jī)載設(shè)備采集的信號(hào)經(jīng)航空電子應(yīng)用程序產(chǎn)生相應(yīng)的消息［5］。如圖1所示，強(qiáng)實(shí)時(shí)信道組(λ1，λ2，…，λm)采用輪轉(zhuǎn)調(diào)度的方式服務(wù)于周期性任務(wù)模型中的各消息。

圖1 消息調(diào)度模型

3 消息可調(diào)度性模型

在航空機(jī)載網(wǎng)絡(luò)中，消息按其類型可分為周期消息和非周期消息。消息的格式和長(zhǎng)度是固定的，且大部分為周期消息，非周期消息也可以確定其發(fā)送的最小時(shí)間間隔。假設(shè)機(jī)載網(wǎng)絡(luò)系統(tǒng)中有n條實(shí)時(shí)消息流形成一個(gè)消息集S=(S1，S2，…，Sn)；采用實(shí)時(shí)通信中的周期性任務(wù)模型，則每條消息流可由一個(gè)四維數(shù)組表示si=(Ci，Pi，Di，?i) ；其中，Ci表示消息流最大長(zhǎng)度；Pi表示消息流的發(fā)送周期［6］，對(duì)于非周期消息，則表示消息產(chǎn)生最小時(shí)間間隔；Di表示消息流的最大允許延遲時(shí)間，一般取Di=Pi，?i表示消息流進(jìn)入系統(tǒng)時(shí)刻，消息流產(chǎn)生周期Pi的最小值用Pmin表示。消息流負(fù)載率定義為

設(shè)TRL為信道輪轉(zhuǎn)周期，M為強(qiáng)實(shí)時(shí)信道數(shù)目，則輪詢權(quán)值約束條件可由下式表示：

其中，TRL取小于Pmin，且為正整數(shù)。

對(duì)于任意時(shí)間間隔t，Xi(t)表示消息i發(fā)送的最小時(shí)間量，則時(shí)限約束條件為

為保證消息發(fā)送的實(shí)時(shí)性，單信道WRR算法中消息i分配的權(quán)值通常取，我們分別?。?方 法 1） 和（方法 2），當(dāng)時(shí)，對(duì)于任意的i，有

同時(shí)，當(dāng)信道資源數(shù)目M和輪轉(zhuǎn)周期TRL的選取滿足輪詢約束條件時(shí)可滿足消息的實(shí)時(shí)發(fā)送。然而，由于輪轉(zhuǎn)長(zhǎng)度TRL、消息周期Pi和消息長(zhǎng)度Ci往往不成比例，這種權(quán)值分配方法分配較大權(quán)值，造成信道利用率的下降。當(dāng)wti=[(Ci*TRL) Pi]時(shí)，對(duì)于任意的i，有：

式（5）不滿足時(shí)限約束條件。也即消息i在周期Pi的消息發(fā)送時(shí)間會(huì)小于Ci，需要在補(bǔ)償信道對(duì)其進(jìn)行權(quán)值補(bǔ)償。將權(quán)值分配不足部分集中到補(bǔ)償信道的做法，大大提高了信道利用率，但同時(shí)增加了系統(tǒng)的復(fù)雜度。

當(dāng)F(TRL)取最小時(shí)，其對(duì)應(yīng)的TRL為此權(quán)值分配方法下的輪轉(zhuǎn)周期最優(yōu)值。此時(shí)，消息分配的權(quán)值有效利用率最高。

與傳統(tǒng)的電信網(wǎng)絡(luò)和數(shù)據(jù)網(wǎng)絡(luò)不同，機(jī)載網(wǎng)絡(luò)要求強(qiáng)實(shí)時(shí)性以保證消息傳輸［9～10］。實(shí)時(shí)性是機(jī)載網(wǎng)絡(luò)的關(guān)鍵性能要求，因而保證機(jī)載網(wǎng)絡(luò)的實(shí)時(shí)性十分必要。實(shí)時(shí)調(diào)度方法是保證機(jī)載網(wǎng)絡(luò)消息傳輸性能的關(guān)鍵。然而，通常的網(wǎng)絡(luò)調(diào)度算法往往側(cè)重于調(diào)度的公平性、系統(tǒng)負(fù)載率和消息的平均延遲等特性，對(duì)實(shí)時(shí)性能的關(guān)注較少。基于輪詢的加權(quán)輪轉(zhuǎn)調(diào)度算法以較低的復(fù)雜度和高度執(zhí)行性非常適合具有強(qiáng)實(shí)時(shí)要求的機(jī)載網(wǎng)絡(luò)系統(tǒng)。在機(jī)載網(wǎng)絡(luò)的設(shè)計(jì)中，通常需要在滿足一定的實(shí)時(shí)性和可靠性的指標(biāo)下，盡可能的提高傳輸有效性。多信道實(shí)時(shí)加權(quán)輪轉(zhuǎn)調(diào)度算法步驟如下：

1）確定信道輪轉(zhuǎn)周期TRL；

2）保證實(shí)時(shí)情況下，根據(jù)權(quán)值分配方法分別計(jì)算每條消息在每輪調(diào)度中需要分配的權(quán)值wti；

3）計(jì)算系統(tǒng)所需信道資源；

4）根據(jù)多信道分配策略將權(quán)值分配到不同的信道資源上；

5）依據(jù)以上參數(shù)進(jìn)行消息發(fā)送。

信道輪轉(zhuǎn)周期的選擇、權(quán)值分配方法和多信道分配策略是多信道實(shí)時(shí)加權(quán)輪轉(zhuǎn)調(diào)度算法設(shè)計(jì)中的重要過(guò)程。輪轉(zhuǎn)調(diào)度周期的選擇是影響系統(tǒng)實(shí)時(shí)傳輸性能的關(guān)鍵之一。權(quán)值分配方法決定了消息分配權(quán)值的大小，并直接影響系統(tǒng)所需分配信道資源數(shù)目。消息拆分將不利于系統(tǒng)對(duì)消息的管理，在盡量減小拆分次數(shù)的前提下，多信道分配策略應(yīng)實(shí)現(xiàn)各信道負(fù)載率的均衡。

4 多信道分配方法

在多信道權(quán)值分配過(guò)程中，當(dāng)單一信道的剩余權(quán)值不足以提供消息預(yù)分配的權(quán)值時(shí)，需要對(duì)消息進(jìn)行拆分，加之消息的排序重組技術(shù)，使得調(diào)度算法更加復(fù)雜。因而，為了簡(jiǎn)化調(diào)度算法，需要盡可能減少消息拆分次數(shù)。論文提出一種多信道分配方法，該方法在遵循盡可能少地減少拆分次數(shù)的原則前提下，盡量平均每個(gè)信道的負(fù)載率。

其分配方法如下：系統(tǒng)中所有的消息組成一個(gè)消息集合；根據(jù)消息所對(duì)應(yīng)的權(quán)值，將消息集合劃分為盡可能多的權(quán)值和恰好等于輪詢周期的互斥集；在同一互斥集內(nèi)的消息分配到同一波長(zhǎng)信道上；將剩余消息所分配權(quán)值和信道空閑帶寬按照從大到小排序；依次選擇剩余消息集合中權(quán)值最大的消息分配到空閑帶寬最大的信道資源上去。若單個(gè)信道剩余帶寬不足，則再進(jìn)行消息流的拆分。每分配完一條消息，更新信道空閑帶寬順序。根據(jù)多信道分配方法，可以達(dá)到每個(gè)信道的負(fù)載率平均的目的。

5 計(jì)算與分析

在式（4）中，所有值的單位都是slot，初始相位是隨機(jī)的。根據(jù)輪轉(zhuǎn)調(diào)度算法函數(shù)和實(shí)時(shí)調(diào)度約束條件，計(jì)算得出了不同權(quán)值分配條件下旋轉(zhuǎn)函數(shù)和TRL之間的關(guān)系，如圖2所示。

圖2

當(dāng)使用第一種權(quán)重分配方法時(shí)，TRL=6時(shí)，輪轉(zhuǎn)函數(shù)的最小值為F(TRL)min=0.7479，所需的硬實(shí)時(shí)信道資源數(shù)是4。使用第二重分配方法時(shí)，TRL=12，輪轉(zhuǎn)函數(shù)的最小值為F(TRL)min=0.2521，所需的硬實(shí)時(shí)信道資源數(shù)是3。

消息延遲時(shí)間率可用作衡量消息實(shí)時(shí)性，表示消息傳輸對(duì)系統(tǒng)的容忍度。計(jì)算了機(jī)載觸發(fā)網(wǎng)絡(luò)每條消息對(duì)應(yīng)的延遲時(shí)間率，結(jié)果如圖3所示。

圖3 不同權(quán)值分配下的平均消息延遲率

消息對(duì)應(yīng)的最大延遲率越小，其容忍度越高，抖動(dòng)等其他影響因素越不易影響機(jī)載觸發(fā)網(wǎng)絡(luò)實(shí)時(shí)性。由圖3可知，雖然所有消息其最大延遲率均不超過(guò)1，滿足系統(tǒng)的實(shí)時(shí)性需求。然而，權(quán)值分配2下的消息最大延遲時(shí)間率均為1（此時(shí)的容忍度為最低），大于權(quán)值分配1下的消息最大延遲時(shí)間率。

計(jì)算分析了不同權(quán)值分配下的信道利用率，如圖4所示。

圖4 不同權(quán)值分配下的信道利用率

由圖4可知，第二種權(quán)值分配方法下的信道利用率優(yōu)于權(quán)值分配方法1，其平均信道利用率分別為0.8333。而采用權(quán)值分配方法2，其補(bǔ)償信道的信道利用率為0.5857。在考慮補(bǔ)償信道情況下，由于兩種分配方法下的實(shí)時(shí)調(diào)度算法的輪轉(zhuǎn)周期和信道資源數(shù)目均相同。因此，兩者的平均信道利用率在理論上是相同的。由以上分析得出，在僅考慮強(qiáng)實(shí)時(shí)信道的情況下，權(quán)值分配方法2對(duì)應(yīng)的信道利用率明顯高于權(quán)值分配1的。但是，若將補(bǔ)償信道考慮在內(nèi)，兩者對(duì)應(yīng)的信道資源及其占用情況一致，并且分配方法1的最大消息延遲率小于分配方法2的。

5 結(jié)語(yǔ)

針對(duì)機(jī)載網(wǎng)絡(luò)的強(qiáng)實(shí)時(shí)性要求，以消息的可調(diào)度性理論模型為基礎(chǔ)，提出了保證機(jī)載光纖網(wǎng)絡(luò)強(qiáng)實(shí)時(shí)性要求的加權(quán)輪轉(zhuǎn)調(diào)度算法，解決了機(jī)載光纖多信道網(wǎng)絡(luò)中消息的實(shí)時(shí)發(fā)送問(wèn)題，并對(duì)影響調(diào)度算法參數(shù)設(shè)計(jì)的三個(gè)重要過(guò)程做了詳細(xì)分析討論。結(jié)果顯示，根據(jù)信道利用率最高時(shí)確定的輪轉(zhuǎn)周期不能保證最優(yōu)的最大消息延遲時(shí)間率；在平均信道利用率相同情況下，權(quán)值分配方法1下的最大消息延遲率優(yōu)于權(quán)值分配方法2的；針對(duì)多信道的應(yīng)用環(huán)境，提出的多信道分配方法有效減少了消息拆分次數(shù)。本文的研究結(jié)果對(duì)機(jī)載光纖網(wǎng)絡(luò)的工程設(shè)計(jì)與優(yōu)化有一定的指導(dǎo)意義。?