基于動態復合優先級的海上節點網絡選擇算法

張治霖，毛忠陽*，劉傳輝，徐建武，孫 林,魏靖怡

(1.海軍航空大學 航空通信教研室，山東 煙臺 264001;2.山東省信號與信息處理重點實驗室，山東 煙臺 264001；3.中國人民解放軍91876部隊，河北 秦皇島 066206)

0 引言

網絡選擇作為異構網絡資源分配的重要組成部分，直接決定了網絡內節點的通信性能[1]。在海上利益凸顯的時代背景下，海上異構無線網絡(Marine Heterogeneous Wireless Networks,MHWNs)對節點業務傳輸的完成度和多樣性提出了更高的要求，需要綜合性更高、靈活性更高、適應性更強的新網絡選擇算法，實現各種業務類型的動態分配和高效傳輸[2]。這就要求網絡選擇算法必須同時兼顧多屬性決策能力、業務優先級動態分配能力和復雜場景適應能力[3]。針對以上需求，相關領域的專家和學者提出了多種多樣的解決方案。

VIKOR方法是解決復雜系統多屬性決策問題的方法之一，比起TOPSIS方法[4]，VIKOR方法能夠在眾多沖突方案中選出最大化群體利益的方案，即折中方案。節點在海上異構網絡中完成業務傳輸任務需要綜合考慮信號強度、距離、帶寬、丟包率等一系列參數，往往網絡環境中沒有非常完美的傳輸信道，需要在眾多機動站點中選取最大化傳輸效率的節點，符合VIKOR方法的應用范圍。VIKOR方法自1998年被提出后，諸多學者對其做了深入的研究。王堅強等人[5]針對多屬性決策的準則權系數信息不完全確定或多為模糊數的問題，提出了模糊多準則VIKOR方法，拓展了VIKOR方法在模糊數領域的應用范圍，但存在無法對方案進行排序的局限。索瑋嵐等人[6]提出了一種更為復雜的混合型E-VIKOR方法，主要面向具有數值、區間數和模糊數形式信息的混合型多屬性決策問題，其做法是先分別處理數值、區間數和模糊數，再將歸一化結果輸入VIKOR方法計算排序，為VIKOR方法的改進提供了新思路。

節點產生業務傳輸業務時，每個業務對完成時間的需求不盡相同，通常的解決方法是選用業務優先級表示業務的執行緊迫性。圍繞基于業務優先級的網絡接入算法研究[7]，相關領域的專家學者提出了多種算法，最為傳統的是最小空閑時間優先(Least Slack First,LSF)算法[8]、最早截止時間優先級 (Earliest Deadline First,EDF)算法[9-10]和隨機公平隊列(Stochastic Fairness Queueing，SFQ)算法[11]。LSF算法[12]遵循任務所剩的空閑時間越少，就越需要盡快執行規則，所以經常會造成乒乓效應，增大了系統開銷；EDF算法[13]是根據任務的截止時間確定業務的優先級，雖然在一定程度上保證了業務完成率，但是對于高優先級業務的重視程度不夠；SFQ算法遵循高度的公平性，其計算量相對較小，但精確度較差。Lun Zeng等人[14]采用改進的SFQ算法，針對網絡信道狀態和節點拓撲動態變化的問題，用優先級表示業務搶占信道的能力，用權重值影響信道接入，通過綜合考慮優先級和權重值提升網絡性能。陶洋、紀瑞娟等人[15]針對切換造成網絡擁堵的問題，提出一種新的資源分配調度方法，根據業務的剩余價值密度和緊迫性系數動態調整優先級，但仿真環境過于平穩，缺少對惡劣環境適應性的研究。

在分析業務優先級排隊方式的基礎上，針對不同業務時效性不同和波動環境適應性不強的問題，引入環境權重、修改的剩余價值和執行緊迫性組成動態復合優先級，實時優化業務排隊序列，所提算法能有效提高高優先級業務的完成率，從而降低網絡在服務業務時的堵塞率。

1 基于業務優先級的網絡選擇算法

1.1 模型建立

海上作業船舶和飛機在海域上進行的業務多種多樣，每個業務的時效性、緊迫性和優先級各不相同，僅用一種或幾種網絡已經遠遠不能滿足當前網絡發展的需要，因此在需求的牽引下，海上異構網絡通過其覆蓋面廣、網絡種類復雜等優點脫穎而出。在多重網絡覆蓋下的用戶想要完成傳輸任務需要考慮帶寬、距離以及包延遲等參數，這正是網絡選擇算法復雜度高的原因所在。

圖1 MHWNs框架Fig.1 Architecture of MHWNs

本文采用的海上異構無線網絡架構如圖1所示。海上異構網絡的通信信道與陸地不同，遮擋物少使得傳輸收到反射波的影響變大。海上環境雖然比陸地環境空曠，但傳輸環境下由干擾造成的波動性仍然是不可忽視的影響因素，其中干擾包括自然因素和人為因素。因此如何在波動環境中仍能保持較為穩定的傳輸速率和業務完成率是目前亟待解決的問題之一。

1.2 算法描述

由于節點的隨機移動和周圍環境的變化波動，其所在接收范圍內的機動站點和網絡屬性參數在不斷改變。本文采用VIKOR法為移動節點提供合適的實時接入方案，選用環境權重、剩余價值和執行緊迫性作為業務改變優先級的標準，充分考慮業務的類型、初始價值和時效性。根據VIKOR法提供的最佳接入方案，將其選擇的機動站點環境參數轉變成環境權重，提供給優先級函數進行動態更新，根據優先級結果對請求接入業務進行排序和接入。

1.2.1 VIKOR法確立連接方案

機動站點周圍的網絡參數在每時每刻變化著，參數的大小和變化率都是隨機的，VIKOR法能在眾多網絡參數中選擇出效益最大的機動站點，能夠有效地針對環境波動問題為移動節點提供更適合現階段環境傳輸的連接方案。

(1)

(2)

然后根據公式求得Qj[5]：

(3)

其中，S*=minSj，S-=maxSj，R*=minRj,R-=maxRj,v一般取0.5。最后按照Q值降序排列，選取Q值最小的機動站點作為連接方案。

1.2.2 動態復合優先級

業務在等待接入隊列中按照業務優先級進行升序排列，業務優先級越高，在帶寬允許的情況下優先考慮接入。考慮到節點所處的波動環境對業務傳輸的影響，在文獻[15]的剩余價值中加入環境參數權重，使得業務在隊列排序中能盡量將適合現階段環境傳輸的業務優先服務。定義ω(t)為動態復合優先級，其表達式為：

ω(t)=D(t)·φ(t)·Vij(t)，

(4)

式中，D(t)表示剩余價值，φ(t)表示執行緊迫性，Vij(t)表示環境權重。

業務的類型和等級造成了業務時效性的各不相同，其時效性變化規律也有一定差異。對于高優先級會話類業務，其時效性僅保留在產生業務后極短的時間內，而對于高優先級交互類和流媒體類業務，其時效性存在區域相對于同等級的會話類業務而言要寬一些。高優先級的會話類業務和低優先級的會話類業務雖然業務類型相同，但由于優先級的差異導致其時效性存在區域也略有差別。雖然會話類業務時效性區域比交互類業務時效性區域小，但需要動態復合優先級函數給予高優先級交互類業務的優先級能夠利用請求接入的時間差超過低優先級會話類業務優先級的機會，否則會造成業務類型架空業務等級、高優先級交互類和流媒體類業務頻繁被低優先級會話類業務插隊的情況。基于上述考慮，在文獻[15]的基礎上對剩余價值和執行緊迫度函數進行了修改。

在文獻[15]的基礎上根據海上業務時效性強的特點，重新定義了剩余價值D(t)，強化了業務優先級與業務持續時間的對應關系，優化了時間間隔對應的價值差值，其表達式為：

(5)

式中，k表示業務參數，Tr表示相對剩余時間，相對剩余時間定義為業務截止時間與已服務時間的差值，V0表示初始價值。

在文獻[15]基礎上重新定義了執行緊迫度φ(t)，增強了業務類型、業務等級與緊迫性的相關性，平滑了緊迫度曲線，相比于原表達式能夠使同一時間差下的緊迫度變化更加均勻，每一時刻變化下緊迫度的變化更加明顯。其表達式為：

(6)

式中，q表示業務類型和業務等級的乘積，di表示絕對截止時間，t表示實時時間。

定義Vij(t)為根據VIKOR算法提供的接入方案通過歸一化法計算得到的環境權重，其中i表示由VIKOR方法計算出的當前最適合連接的機動站點編號，j表示當前業務類型更側重第j個網絡環境參量。由于不同的業務類型對不同網絡參數有著不同的需求，本文設定會話類業務關注包延遲參數，交互類業務關注丟包率參數，流媒體類業務關注帶寬參數。設第i個機動站點t時刻的網絡參數分別為{α1t,α2t,α3t,...,αnt}，定義歸一化后業務關注的參數為其對應業務的環境權重，則會話類業務的環境權重為:

(7)

式中,i=1,2,…，n。交互類和流媒體類的環境權重以此類推。

1.3 算法流程

為與實際運動更貼合，移動節點采用高斯-馬爾科夫移動模型[16]進行描述，模擬海上作業飛機的連續隨機運動，相較于傳統隨機模型有著運動曲線更平滑的優勢。針對海上通信網絡特征，節點通信信道采用海上通信信道[17]，考慮海面反射和大氣吸收損耗，不考慮惡劣氣候等其他偶然性影響因素。算法的具體流程如圖2所示。

圖2 算法流程Fig.2 Algorithm flow

節點開始運動時，算法同步運行。算法首先檢查業務服務情況：將新產生的業務加入到請求接入排隊序列，對過期的業務進行清除，已經結束的業務釋放帶寬。節點更新路徑范圍內機動站點周圍的環境參數，算法根據輸入參數更新所有序列中業務的動態優先級，根據機動站點的環境參數計算出環境權重。將所有參數輸入到VIKOR法中，VIKOR提供適合現階段環境傳輸的機動站點連接方案。對業務請求接入排隊序列按照動態優先級進行排序，按照排隊順序依次檢查剩余帶寬情況，滿足要求的業務開始服務，不滿足要求的業務重新進入請求接入序列進行排序。若請求接入隊列已滿隊，則新生成的業務與請求接入隊列中動態優先級最小者進行比較，留下動態優先級較大的業務。

2 仿真結果與分析

2.1 參數設置

本文算法的仿真場景設置為海上臨時機動站點環境，機動站點的位置如圖3所示。機動站點在海平面以每小時15節的速度緩慢向x軸正方向移動，移動節點從原點出發，之后的時間內以150 m/s的速度做連續隨機運動，仿真時間800 s。由于仿真使用的是機動站點和海上節點的相對距離，所以機動站點的移動速度相對海上節點來說可以近似為靜止。機動站點的通信范圍是視距范圍，超出通信范圍視為無信號。移動節點的出發起始點設置為坐標原點，以此為例進行蒙特卡洛仿真。

圖3 機動站點位置圖Fig.3 Mobile station location map

在本算法仿真中，移動節點最大帶寬設置為150 kHz，等待隊列和服務隊列最大數量為10，等待隊列和服務隊列都滿隊的情況下，再產生業務接入請求時，定義為網絡堵塞。業務生成間隔滿足參數為3的泊松分布，機動站點的網絡參數波動采用馬爾科夫鏈形式進行模擬，狀態轉移概率為0.5，當前時間的參數只與前一時刻的參數相關，與其他時刻的參數值無關，機動站點網絡參數波動范圍如表1所示。

表1 仿真參數表

業務參數中帶寬參數參考文獻[6]，為方便數值計算，3種業務所需帶寬同時縮小一個數量級，縮小后的數值不影響后續計算步驟的數值大小和意義。初始價值參數參考文獻[7]，并在此基礎上擴展到3種業務類型，按照高優先級價值高于低優先級、會話類高于交互類、交互類高于流媒體類的規則。業務參數設置如表2所示。

表2 業務參數表

業務等級的服務時間和等級數量比重如表3所示，根據統計學原理，3種業務等級服務時間的期望之和近似等于等級二所需的服務時間。業務狀態分為等待、服務和過期3個狀態，過期的業務指的是業務等待時間超過了其k倍的服務時長，根據不同等級業務的時效性將k按照業務等級一、二、三分別設定為0.8、1.2、1.5，過期業務不再進入到請求接入序列中排隊，自動判斷為傳輸業務失敗。

表3 業務等級表

2.2 結果分析

為驗證本文算法的性能，將其與基于距離、時間優先級算法[9]，以及改進的動態優先級控制算法[13]進行對比。基于距離是指基站連接選擇方案按照距離大小進行選擇，時間優先級指按照業務接入請求的發送時間進行排序，改進的動態優先級控制算法是指在文獻[13]的基礎上加入了基于距離選擇連接基站的部分。

將完成的業務除以這段時間產生的所有業務得到業務完成率，用來衡量算法的業務執行情況。某次仿真結束后得到圖4所示的完成率對比圖，可以看到70 s之前兩種算法的完成率是幾乎相同的，這是由于服務序列未完全滿隊，算法之間的差異并不明顯。在服務序列滿隊之后，按照動態優先級排序的隊列業務完成率明顯好于時間優先級的隊列，這是因為高優先級業務的服務時間較少時，將高優先級的業務提前服務，能避免由于大帶寬低優先級的業務長時間占用帶寬致使高優先級業務無法接入最終失效的情況。經過50次蒙特卡羅仿真取平均，復合優先級算法和優先級控制算法相比有0.71%的提升，與時間優先級相比有3.85%的提升，這是因為復合優先級的剩余價值和執行緊迫性函數根據不同業務時效性的特點，增大了有效差異的時效性區域，避免了高優先級由于接入請求發送晚，而被低優先級先發送接入請求的業務一直插隊的情況。

圖4 實時業務完成率對比Fig.4 Comparison of real time business completion rate

圖5為仿真時間內兩種算法不同業務等級完成數量的對比。

圖5 業務等級完成數量對比Fig.5 Comparison of business level completed quantity

在密集業務傳輸需求的情況下，動態復合優先級算法的業務完成總量明顯高于于其他兩種算法，經過50次蒙特卡洛仿真取平均后得到，相對于時間優先級算法，本文算法在業務等級一完成量提升了約136.17%，業務等級二的完成量提升了約27.26%，業務等級三的完成量降低了23%，這是由于算法提高了高優先級的服務優先度，犧牲了一部分帶寬需求較大的低優先級業務，使得隊列快速服務低帶寬需求的業務。與動態優先級控制算法相比，本文算法的業務等級一完成量提升了17.59%，業務等級二完成量提升了5.819%，業務等級三完成量提升了11.76%。動態復合優先級算法主動提高高優先級業務的服務時間，也變相提高了整個排隊序列的通暢度，使得各個優先級的業務完成率都能有所提升。

圖6為不同業務類型完成量對比，業務類型的完成與機動站點的網絡參數還有業務類型的帶寬有關，流媒體類業務由于所需帶寬較大，造成業務完成量較低。通過50次蒙特卡洛仿真后取平均值，相對于時間優先級算法，本文算法在會話類業務完成量提升了約67%，交互類業務的完成量提升了約19.42%，流媒體類業務的完成量降低了21%。會話類業務作為3類業務中帶寬需求最小的，當高優先級會話類業務請求時可以快速接入服務且對請求接入排隊隊列影響最小，所以會話類業務提升最為明顯。同樣，在犧牲大帶寬需求且低優先級流媒體類業務的情況下，才能為高優先級低帶寬需求的業務留出相應的服務位置。與動態優先級控制算法相比，由于高優先級業務完成率的提升，相應業務類型的完成率也有所提升，本文所提算法的會話類業務完成量提升了6.5%，交互類業務完成量提升了5.5%，流媒體類業務完成量提升了3%。

圖6 業務類型完成數量對比Fig.6 Comparison of number of business types completed

環境參數波動是不可控的，算法的環境適應性體現在從大量多變的機動站點網絡參數中提供合適的連接方案，并將連接方案的參數傾向性傳遞到業務請求接入隊列中，因此選用實時的網絡參數對波動環境適應性進行衡量。通過圖7對比可以看出，VIKOR法在帶寬、包延遲、包抖動和丟包率四種沖突參數下，提供的折中方案更傾向于較小的包延遲、包抖動和丟包率，這非常有利于會話類和交互類業務的傳輸，但這種方案的代價是帶寬較小。VIKOR法為業務排序提供了環境權重，能有效促使業務按照適合環境傳輸的順序進行排列。

(a) 實時帶寬參數對比

圖8為3種算法在仿真時間內堵塞率的對比，將請求接入隊列中等候接入的業務數量除以滿隊列的業務數量定義為堵塞率，可以看出，本文算法的實時堵塞率始終處于較低值，其余兩種算法均處于較高值。當算法的堵塞率處于滿狀態時，代表著下一時刻若再生成新的業務，就必定會有業務因網絡堵塞而過期，造成業務完成率下降，所以低堵塞率意味著保證了節點服務隊列的流暢度，能在一定程度上提升整個通信網絡的性能。將圖6～圖8結合來看，在動態復合優先級提高業務完成率的基礎上，結合VIKOR法選擇較優參數的機動站點進行連接，業務服務處于良好的網絡參數環境下，能使業務服務質量有較好的提升。

圖8 實時堵塞率Fig.8 Real time blockage rate

3 結論

針對業務類型和業務等級的時效性特點不突出以及算法對于波動環境適應性不強的問題，本文提出了一種基于VIKOR法和動態優先級的多屬性網絡接入選擇算法。首先用VIKOR法選出合適的網絡接入方案，再把方案站點的網絡環境參數權重傳遞給移動節點的業務連接請求隊列，結合改進的剩余價值和執行緊迫度建立動態復合優先級模型，最后搭建仿真環境對其性能進行仿真。仿真結果表明，在海上波動環境移動節點基于業務優先級的網絡選擇場景下，基于動態復合優先級的算法與時間優先級算法和基于動態優先級控制算法相比，在同樣保證業務優先級需求的基礎上，能夠有效提升業務完成率和隊列流暢度，提高了整體通信網絡的性能。