摘要：針對衛(wèi)星通信系統(tǒng)高并發(fā)處理需求，文章提出一種多處理器自適應(yīng)負(fù)載均衡方法，該方法對傳統(tǒng)Hash算法進(jìn)行了改進(jìn)，綜合考慮了各處理器處理能力的差異，解決了普通Hash算法存在的Hash不均問題，在處理器數(shù)量發(fā)生變化時整個系統(tǒng)映射關(guān)系的調(diào)整較小。算法在系統(tǒng)容錯性、可擴(kuò)展性和負(fù)載均衡性方面均有較大的改進(jìn)，克服了現(xiàn)有負(fù)載均衡方法的局限性。

關(guān)鍵詞：衛(wèi)星通信；負(fù)載均衡；一致性哈希

中圖分類號：TN92文獻(xiàn)標(biāo)志碼：A

0 引言

衛(wèi)星通信因其業(yè)務(wù)覆蓋廣、系統(tǒng)可靠、傳輸性高、系統(tǒng)不受地面環(huán)境狀態(tài)影響等優(yōu)勢，在各行各業(yè)被越來越廣泛地應(yīng)用。隨著衛(wèi)星通信用戶量越來越多，地面衛(wèi)星通信系統(tǒng)高并發(fā)處理需求也隨之提高，傳統(tǒng)的單進(jìn)程信息處理器很難滿足業(yè)務(wù)通信過程中用戶高并發(fā)請求下信息處理的實時性要求，需要進(jìn)行多進(jìn)程信息處理器負(fù)載均衡［1］。目前，進(jìn)行多進(jìn)程信息處理器負(fù)載均衡的主流方法主要有靜態(tài)負(fù)載均衡和動態(tài)負(fù)載均衡方法。靜態(tài)負(fù)載均衡主要有輪轉(zhuǎn)算法、加權(quán)輪轉(zhuǎn)算法和散列法等；動態(tài)負(fù)載均衡算法主要有最少連接法、最快響應(yīng)法等。其中，輪轉(zhuǎn)算法適合所有節(jié)點(diǎn)的處理能力均相同的情況，請求到來時按照順序分別發(fā)給各個處理器進(jìn)行處理，若節(jié)點(diǎn)處理能力不同，則可能出現(xiàn)不同處理能力的節(jié)點(diǎn)之間負(fù)載分擔(dān)不均問題；加權(quán)輪轉(zhuǎn)算法是普通輪轉(zhuǎn)算法的改進(jìn)，考慮了各個處理器節(jié)點(diǎn)處理能力的差異，根據(jù)處理能力的差異確定權(quán)值，改善了負(fù)載分擔(dān)的均衡性，但處理器故障的容錯性和數(shù)量的擴(kuò)展性較差；散列法的均衡性取決于哈希均勻性，存在哈希不均的問題且當(dāng)處理器數(shù)量增加或因故障減少時，哈希值和處理器之間的映射關(guān)系需要重新調(diào)整；動態(tài)均衡算法主要是動態(tài)檢測處理器當(dāng)前的請求數(shù)和信息處理響應(yīng)時間，根據(jù)各個處理器當(dāng)前的請求數(shù)和響應(yīng)時間動態(tài)調(diào)整請求信令的分配，會增大系統(tǒng)的處理開銷。

針對現(xiàn)有分配方式存在的一些問題，本文提出一種衛(wèi)星通信系統(tǒng)自適應(yīng)負(fù)載均衡方法。該方法將各處理器進(jìn)程使用相同的哈希算法計算哈希值，并將值映射到0～（232-1）組成的閉合哈希圓環(huán)上，進(jìn)行用戶請求分配時，系統(tǒng)根據(jù)用戶請求信息特征值計算對應(yīng)的哈希值，并根據(jù)哈希值在閉合哈希圓環(huán)上順時針尋找最近的滿足處理能力的處理器進(jìn)行處理，如遇到最近的處理器不滿足條件則繼續(xù)遍歷下一個，各處理器共享狀態(tài)存儲模塊的數(shù)據(jù)，實現(xiàn)系統(tǒng)無狀態(tài)處理。該方法綜合考慮了各處理器處理能力的差異以及處理器數(shù)量發(fā)生變化時整個系統(tǒng)映射關(guān)系的最小化調(diào)整問題，在系統(tǒng)容錯性、可擴(kuò)展性和負(fù)載均衡性方面均有較大的改進(jìn)，克服了現(xiàn)有負(fù)載均衡方法的局限性。

1 衛(wèi)星通信系統(tǒng)架構(gòu)

地面衛(wèi)星通信系統(tǒng)包括地球站和通信業(yè)務(wù)控制中心等部分，如圖1所示。本文所述的自適應(yīng)負(fù)載均衡算法主要針對圖示通信業(yè)務(wù)中心模塊中的核心處理器部分，當(dāng)?shù)厍蛘居脩袅枯^多時，同一時間可能會有大量的入網(wǎng)/呼叫請求需要核心處理器處理，此時如果不進(jìn)行負(fù)載均衡則可能導(dǎo)致處理器過載或用戶請求處理時延變長，影響用戶體驗。

為解決上述問題，需要增加核心處理器數(shù)量，并選擇合適的算法進(jìn)行多處理器負(fù)載均衡，將大量的用戶請求信息分發(fā)給多個處理器同時進(jìn)行處理，達(dá)到提升處理速度，優(yōu)化用戶體驗的目的。

2 改進(jìn)負(fù)載均衡算法和系統(tǒng)

2.1 傳統(tǒng)哈希算法

對于多進(jìn)程處理器之間的負(fù)載均衡多采用哈希算法進(jìn)行。傳統(tǒng)哈希算法通常是建立哈希值映射表，將哈希值和處理器之間進(jìn)行循環(huán)映射，根據(jù)待處理信令特征信息計算哈希值，并根據(jù)計算的哈希值查表確定處理器，從而選擇對應(yīng)的處理器進(jìn)行處理。此種算法在處理器數(shù)量新增或者減少時都需要對哈希值映射關(guān)系進(jìn)行重新調(diào)整，降低了系統(tǒng)的穩(wěn)定性和處理效率。

一致性哈希算法針對上述傳統(tǒng)哈希算法存在的問題進(jìn)行了改進(jìn)［2］，將所有哈希值抽象成一個圓環(huán)，比如哈希值范圍為0～（232-1），則抽象的哈希環(huán)0和（232-1）首尾相接構(gòu)成一個圓環(huán)，計算各處理器節(jié)點(diǎn)的哈希值并映射在哈希環(huán)的對應(yīng)位置上，計算用戶請求數(shù)據(jù)的哈希值，根據(jù)哈希值順時針尋找距離最近的處理器節(jié)點(diǎn)作為數(shù)據(jù)處理節(jié)點(diǎn)。此種算法在處理器數(shù)量新增或減少時，哈希值映射不需要重新調(diào)整，但未考慮不同的處理器節(jié)點(diǎn)可能存在的處理能力差異，也未考慮當(dāng)用戶量不夠大時可能存在的負(fù)載分擔(dān)偏移問題。

2.2 改進(jìn)負(fù)載分擔(dān)算法

針對上述傳統(tǒng)算法存在的問題，本文對負(fù)載分擔(dān)算法進(jìn)行改進(jìn)，根據(jù)各處理器節(jié)點(diǎn)的CPU利用率、內(nèi)存利用率、當(dāng)前處理數(shù)量、當(dāng)前流量、響應(yīng)時間等綜合考慮各節(jié)點(diǎn)的處理能力［3］，并計算各處理器節(jié)點(diǎn)的最大處理上限，同時對用戶量不夠大時可能存在的負(fù)載分擔(dān)不均問題進(jìn)行改善，提升系統(tǒng)整體的性能。

改進(jìn)負(fù)載分擔(dān)算法如圖2所示，整體示意圖為抽象成的哈希環(huán)，ServerA到ServerD表示當(dāng)前系統(tǒng)內(nèi)的4個處理器節(jié)點(diǎn)，處理器節(jié)點(diǎn)之間A1、B1等小的節(jié)點(diǎn)表示各處理器服務(wù)節(jié)點(diǎn)的虛擬節(jié)點(diǎn)，通過虛擬節(jié)點(diǎn)可定位對應(yīng)的實際服務(wù)節(jié)點(diǎn)，可解決負(fù)載傾斜的問題；此外，算法實施過程中同時兼顧各節(jié)點(diǎn)的處理能力，并根據(jù)節(jié)點(diǎn)處理能力確定各節(jié)點(diǎn)的最大處理并發(fā)量和選擇權(quán)重。

其中，哈希環(huán)上處理器實體節(jié)點(diǎn)和虛擬節(jié)點(diǎn)的確定方法采用如下斐波那契散列法計算確定［4］。

哈希函數(shù)為：

H（k）=［m×（k×Amod1）］

其中，m=1 000，A=（5-1）/2。

處理器實體節(jié)點(diǎn)和虛擬節(jié)點(diǎn)的算法如下。

實體節(jié)點(diǎn)：H（k）=［m×（k×Amod1）］。

虛擬節(jié)點(diǎn)1：H（k1）=［m×（H（k）×Amod1）］。

虛擬節(jié)點(diǎn)2：H（k2）=［m×（H（k1）×Amod1）］。

依次類推，根據(jù)各個節(jié)點(diǎn)的處理能力確定需要添加的虛擬節(jié)點(diǎn)個數(shù)。

算法的執(zhí)行流程如圖3所示，改進(jìn)負(fù)載分擔(dān)算法的工作流程如下。

（1）利用用戶請求數(shù)據(jù)中的特征數(shù)據(jù)計算哈希值。

（2）根據(jù)哈希值確定在哈希環(huán)上的位置。

（3）順時針查找圓環(huán)上的節(jié)點(diǎn)，根據(jù)找到的實體節(jié)點(diǎn)或虛擬節(jié)點(diǎn)對應(yīng)的服務(wù)節(jié)點(diǎn)確定處理節(jié)點(diǎn)。

（4）若節(jié)點(diǎn)對應(yīng)的服務(wù)節(jié)點(diǎn)當(dāng)前處理能力已經(jīng)到達(dá)上限，則繼續(xù)查找下一節(jié)點(diǎn)。

（5）若用戶量過大導(dǎo)致所有的節(jié)點(diǎn)均已達(dá)到最大處理上限，則根據(jù)節(jié)點(diǎn)的選擇權(quán)重選擇性能最優(yōu)的節(jié)點(diǎn)盡可能保障用戶。

2.3 帶負(fù)載均衡衛(wèi)星通信系統(tǒng)

根據(jù)上述算法的描述，帶負(fù)載均衡的衛(wèi)星通信系統(tǒng)結(jié)構(gòu)如圖4所示。來自地球站的請求信息經(jīng)過負(fù)載均衡處理模塊處理后散轉(zhuǎn)到各個處理器節(jié)點(diǎn)進(jìn)行處理，處理后相關(guān)的狀態(tài)數(shù)據(jù)存儲在同一個數(shù)據(jù)庫中，各節(jié)點(diǎn)共享數(shù)據(jù)，當(dāng)處理器節(jié)點(diǎn)發(fā)生變更導(dǎo)致同一個地球站的請求后續(xù)會被不同的處理器處理時，可維持地球站的狀態(tài)數(shù)據(jù)一致性，提高系統(tǒng)容錯性和穩(wěn)定性［5］。

3 衛(wèi)星通信負(fù)載均衡工作流程

3.1 正常工作流程

衛(wèi)星通信負(fù)載均衡正常工作流程是指所有處理器節(jié)點(diǎn)狀態(tài)均正常的情況下的工作流程，如圖5所示。圖中示意了節(jié)點(diǎn)狀態(tài)正常和有節(jié)點(diǎn)負(fù)載達(dá)到上限狀態(tài)下的節(jié)點(diǎn)選擇情況，節(jié)點(diǎn)狀態(tài)正常的情況以節(jié)點(diǎn)A為例，負(fù)載達(dá)上限的情況以節(jié)點(diǎn)B為例，具體如下：

節(jié)點(diǎn)狀態(tài)正常情況下的流程以圖中請求Q1為例。Q1為地球站請求信令計算出的哈希值在圓環(huán)上的位置，以Q1為起點(diǎn)順時針查找節(jié)點(diǎn)，順時針第一個節(jié)點(diǎn)為虛擬節(jié)點(diǎn)A1，虛擬節(jié)點(diǎn)A1對應(yīng)服務(wù)處理節(jié)點(diǎn)A，因此請求Q1分配給服務(wù)處理節(jié)點(diǎn)A進(jìn)行處理。

節(jié)點(diǎn)負(fù)載達(dá)到上限的情況以圖中請求Q2為例。以Q2為起點(diǎn)順時針查找節(jié)點(diǎn)，順時針第一個節(jié)點(diǎn)為虛擬節(jié)點(diǎn)B1，虛擬節(jié)點(diǎn)B1對應(yīng)服務(wù)處理節(jié)點(diǎn)B，但此時節(jié)點(diǎn)B負(fù)載達(dá)到上限，繼續(xù)順時針查找下一節(jié)點(diǎn)，因此請求Q2分配給服務(wù)處理節(jié)點(diǎn)C進(jìn)行處理。

3.2 節(jié)點(diǎn)數(shù)量變更時工作流程

節(jié)點(diǎn)數(shù)量變更指因故障等問題減少或因處理需要新增節(jié)點(diǎn)的情況，工作流程如圖6所示。節(jié)點(diǎn)數(shù)量減少和新增情況下對用戶請求的分配情況，節(jié)點(diǎn)減少以取消節(jié)點(diǎn)A為例，節(jié)點(diǎn)增加以新增節(jié)點(diǎn)E為例。具體如下：

節(jié)點(diǎn)數(shù)量減少的情況以請求Q3為例，以Q3為起點(diǎn)順時針查找最近的節(jié)點(diǎn)，由于處理器節(jié)點(diǎn)A取消，因此與節(jié)點(diǎn)A關(guān)聯(lián)的所有虛擬節(jié)點(diǎn)均取消，此時最近的節(jié)點(diǎn)為虛擬節(jié)點(diǎn)B2，虛擬節(jié)點(diǎn)B2對應(yīng)服務(wù)處理節(jié)點(diǎn)B，因此請求Q3分配給服務(wù)處理節(jié)點(diǎn)B進(jìn)行處理。

節(jié)點(diǎn)數(shù)量新增的情況以請求Q4為例，新增的節(jié)點(diǎn)為節(jié)點(diǎn)E，以Q4為起點(diǎn)順時針查找最近的節(jié)點(diǎn)，順時針第一個節(jié)點(diǎn)為虛擬節(jié)點(diǎn)E1，對應(yīng)服務(wù)處理節(jié)點(diǎn)E，因此請求Q4分配給服務(wù)處理節(jié)點(diǎn)E進(jìn)行處理。

上述可見，本文算法具有較好的容錯性和擴(kuò)展性，在處理器節(jié)點(diǎn)數(shù)量減少或新增時，可以自適應(yīng)地將新增或者減少的節(jié)點(diǎn)在哈希環(huán)上進(jìn)行標(biāo)識，對用戶請求進(jìn)行分配時，只有發(fā)生新增或者減少的節(jié)點(diǎn)分配受到影響，處理器節(jié)點(diǎn)和請求哈希值之間的映射關(guān)系不需要重新分配，提升了系統(tǒng)的容錯性和擴(kuò)展性。

4 結(jié)語

本文提出了一種地面衛(wèi)星通信系統(tǒng)自適應(yīng)負(fù)載均衡方法，與傳統(tǒng)的衛(wèi)星通信系統(tǒng)負(fù)載均衡方法相比，本方法對負(fù)載均衡時使用的Hash算法進(jìn)行了改進(jìn)［6］，解決了基于普通Hash算法的負(fù)載均衡可能存在的Hash不均導(dǎo)致的分擔(dān)不均問題，解決了傳統(tǒng)負(fù)載分擔(dān)易出現(xiàn)的狀態(tài)不一致問題，改進(jìn)了分擔(dān)效果。

參考文獻(xiàn)

［1］王健，孫建伶，王新宇，等.容錯多處理機(jī)中一種高效的實時調(diào)度算法［J］.軟件學(xué)報，2009（10）：2628-2636.

［2］方堃，武小年.改進(jìn)的一致性哈希算法及應(yīng)用［J］.大眾科技，2015（4）：5-7.

［3］盧建元.高性能哈希技術(shù)及其應(yīng)用的研究［D］.北京：清華大學(xué)，2017.

［4］郭寧，張新.一致性哈希算法在多處理機(jī)進(jìn)程分配的應(yīng)用［J］.計算機(jī)與現(xiàn)代化，2013（9）：71-74.

［5］姚墨涵，謝紅薇.一致性哈希算法在分布式系統(tǒng)中的應(yīng)用［J］.電腦開發(fā)與應(yīng)用，2012（7）：1-2.

［6］張開琦，劉曉燕，王信，等.基于動態(tài)權(quán)重的一致性哈希微服務(wù)負(fù)載均衡優(yōu)化［J］.計算機(jī)工程與科學(xué)，2020（8）：1339-1344.

Research on adaptive load balancing method of the terrestrial satellite communication system

QiuChunrong， YanYingzi

（Nanjing Panda Handa Technology Co.， Ltd.， Nanjing 210000， China）

Abstract： A multi processor adaptive load balancing method is proposed to address the high requirements for concurrent processing in satellite communication systems. This method improves traditional Hash algorithms and takes into account the differences in processing capabilities of each processor. It Solved the problem of Hash unevenness in ordinary Hash algorithms. The adjustment of the entire system mapping relationship is relatively small when the number of processors changes.it has greater improvement in System Error-tolerance， scalability， and load balancing， overcoming the limitations of existing load balancing methods.

Key words： satellite communications; load balance; consistent Hash