5G路測儀信令合成算法的研究與實現

張冰瑩 程 方 程 渝

(重慶郵電大學通信與信息工程學院 重慶 400065) (重慶重郵匯測電子技術研究院有限公司 重慶 401121)

0 引 言

為了適應海量的數據流量增長、設備連接，加快各類新業務應用場景發展需求，第五代移動通信網絡(The fifth generation mobile communication network，5G)應運而生[1]。5G相比于過去幾代通信網絡，其開放性與靈活性的特點將滿足移動數據日益增長的需求。面對5G網絡復雜的通信場景和龐大的性能指標，無論是網絡運維還是優化工作的開展都需要專業化的測試產品用于5G網絡的技術試驗、網絡維護和優化[2]。

第五代移動通信系統測試作為整個通信產業鏈的關鍵一環，能夠對5G全網設備以及不斷演進的新技術進行驗證[3]。在龐大的5G網絡部署與建設過程中，5G路測儀表對開展5G網絡質量評估、探索新的信號、場景及拓撲結構等方面將提供可靠的海量數據源和數據分析能力。信令監測作為5G路測儀表的關鍵技術，不僅是信令網維護和管理的重要手段之一，還可為其他應用系統提供豐富的信令數據，在網絡優化、網絡質量分析、用戶感知評估等方面具有重要支撐作用。對于5G網絡空中接口，可通過控制平面監測UE和gNB之間的網絡狀況，對協議的功能進行評估測試，并直觀反映所處位置的網絡環境指標，實現網絡運行質量評估和網絡優化測試。

近年來，許多學者針對移動通信網絡不同接口或協議中的信令展開研究。蔣洋[4]針對LTE網絡Uu接口層三信令監測的研究中提出運用二次探測再散列法完成CDR合成，這種方法可避免產生沖突的散列元素聚集在某一塊區域，但會相應增加查詢時間，導致CDR合成效率降低。Han等[5]通過研究LTE網絡S6a接口信令，提出一種有效的監測方案，運用哈希表代替二叉樹存儲CDR鍵值對以提升合成效率。彭佩等[6]針對LTE-A網絡NAS協議信令完成監測，李雷等[7]針對LTE-A網絡多協議關聯進行研究，且二者均提出采用哈希鏈地址法完成CDR合成，這種方法相比于哈希開放地址法能減少哈希沖突時爭奪同一地址的堆積現象，但順序查詢單鏈表上記錄將消耗大量時間頻繁訪問內存。王京[8]采用雙鏈表結構記錄CDR鍵值對之間的時間先后順序，查詢關鍵字時無須遍歷全表，有效減少了查詢時間。然而以上方案均針對LTE/LTE-A網絡中的信令流程進行研究，難以適應5G網絡架構下的信令分析，并且上述方法在進行呼叫詳細記錄(Calling Detail Record，CDR)信令合成中采用的算法在解決哈希沖突時存在合成效率低下、平均遍歷時間復雜度高等缺點。基于以上分析，本文將提出一種適用于5G網絡的信令監測系統實現對5G空口數據的實時監測及解析，并在傳統哈希信令合成算法基礎上提出一種基于平衡二叉查找樹的動態哈希查找算法以存儲沖突節點，解決傳統信令合成算法查詢時間長、索引效率低下等問題，實現5G網絡海量用戶數據下信令消息的高效快速處理，從而全面、準確地進行呼叫信令合成。分析結果表明，將本文所提出的信令合成算法應用到5G路測儀中，通過外場真實數據采集處理，獲取信令合成數據源并利用改進的哈希動態合成算法進行測試，能夠顯著提升CDR合成效率、減少內存消耗，驗證了該方案的實時性和可行性。

1 5G網絡概述

區別于傳統移動通信網絡采用網絡實體或網元來描述系統架構，5G網絡引入了網絡功能和服務的概念，完全分離控制平面與用戶平面?？刂泼胬媒尤爰耙苿有怨芾砉δ?Access and Mobility Function，AMF)和會話管理功能(Session Management Function，SMF)網元代替原LTE網元MME中的移動和會話管理功能；用戶面通過用戶面網元(User Plane Function，UPF)節點負責管理。5G NR作為5G網絡連接UE和gNB之間的接口，其協議棧架構總體可以概述為“三層兩面”，所謂“三層”是指空口協議棧按照OSI模型中的邏輯層次進行劃分，從下往上依次為物理層、數據鏈路層和網絡層?！皟擅妗本唧w指控制平面協議棧與用戶平面協議棧，通過識別數據類型屬于控制信令還是用戶數據進行區分[9-10]。

(1) 控制平面架構。5G NR控制平面協議棧包括NAS、RRC、PDCP、RLC、MAC及PHY層。NAS層負責將PDU會話管理、終端注冊/去注冊、鑒權及密鑰協商等相關過程的信令數據傳遞至核心網[11]；RRC子層主要執行無線承載控制及移動性管理、系統消息的廣播、尋呼、RRC連接管理等功能[12]；PDCP層對信令數據進行加密和完整性保護；RLC、MAC、PHY三層則執行數據傳輸的相關功能。協議棧控制平面架構如圖1所示。

圖1 協議?？刂破矫婕軜?/p>

(2) 用戶平面架構。5G NR用戶平面協議棧主要包括SDAP、PDCP、RLC、MAC、PHY層。其中，業務數據適應(Service Data Adaptation Protocol,SDAP)層屬于5G NR中新添加的一層協議，用于實現數據無線承載與QoS流之間的映射，以及在上下行數據添加QoS流標識。協議棧用戶平面架構如圖2所示。

圖2 協議棧用戶平面架構

2 信令監測系統設計

信令監測系統以5G路測及數據采集技術作為基礎，完成從采集層面到應用層面的全過程系統。按照3GPP及相關行業測試規范要求，根據不同層次的應用需求將5G路測儀信令監測系統整體架構劃分為三層，依次為信令采集層、數據處理層和應用層。

各子系統之間采用層次化與模塊化的軟件設計思路，獨自完成模塊具體功能，繼而交給其他模塊繼續執行，大大提高了模塊之間的獨立性和后續可擴展性。信令監測系統框架如圖3所示。

圖3 信令監測系統框架圖

2.1 數據采集層

信令采集層主要通過信令采集設備從5G網絡空中接口的信令鏈路上獲取無線端口用戶的原始信令數據與業務數據，完成接口適配、接口實時監測等基礎操作，實現原始信令數據的實時采集、存儲并在一定時延要求下高效地轉發給數據處理層進行信令數據分析。

2.2 數據處理層

(1) 數據預處理模塊。該模塊通過主控驅動接口接收來自信令采集層的原始信令數據，通過數據預處理轉化為系統可識別的二進制碼流等數據結構，包括數據剔除、協議識別、分發存儲三個單元。數據剔除是通過檢查并剔除原始信令數據中與后續解碼合成無關的底層協議數據，避免5G網絡下海量的數據流量影響后續解碼合成的效率；協議識別是通過識別數據包接口中包頭所包含的信道類型來判斷該消息屬于控制面數據還是用戶面數據，再通過數據分發存儲操作將其分發到控制面和用戶面數據的隊列尾部進行緩存，供協議解碼模塊調用。其中，控制面數據主要由RRC與NAS協議以及SIB(System Information Block)、MIB(Master Information Block)、SRB0、SRB1、SRB2等無線信令承載組成，用戶面數據主要包括PDCP、SDAP及其承載的IP、HTTP等協議簇。數據包接口中的邏輯信道類型與數據類型的對應關系如表1所示，其中DTCH為用戶面數據專用邏輯信道。

表1 信道類型與數據類型對應關系

(2) 協議解碼模塊。協議解碼模塊屬于5G路測儀中信令監測與分析處理的基礎，包括對各層協議關鍵字段的提取、詳細比特內容的解析及信令合成參數的提供。該模塊按解碼粒度進行區別，包含基礎解碼和詳細解碼單元，可實現信令的簡單解碼、合成解碼及詳細解碼功能。其中，簡單解碼是通過將原始信令碼流進行消息構造與解碼，最終獲取基本信令消息中的消息類型、長度、基本內容等信息；合成解碼的目的是為后續CDR合成提供基礎數據支撐，針對同一CDR呼叫流程的信令解析出后續關聯合成所需要的信元和參數；詳細解碼利用層層遞歸的解碼方法，將原始信令消息按照協議要求從下往上逐條逐層次進行解析。

信令面解碼是針對承載在PDCP協議之上的RRC和NAS協議的解碼，基于3GPP對RRC和NAS協議制定的標準，RRC解碼模塊在解碼時首先采用開源的ASN.1編譯器生成RRC協議各消息的解碼函數，再對簡單解碼和詳細解碼進行二次開發；NAS解碼模塊是對RRC消息所承載的NAS消息進行解析，從二進制碼流中獲取直觀有效的信息并解析成具有邏輯意義的結果字段。用戶面解碼是指對IP、TCP、UDP、HTTP、DNS等用戶平面的協議進行解析，根據對應的端口號識別上層協議并逐層遞歸解碼，直至待解碼數據為空則解碼完成。具體解碼流程如圖4所示。

圖4 協議解碼流程

(3) 關聯合成模塊。關聯合成模塊主要完成同一用戶在同一通信流程下處于不用平面、不同層級的協議消息相關聯，將其有用信息生成CDR，從而形成完整的用戶消息，屬于數據處理層的核心模塊。整個信令合成過程主要包含新建、修改、存儲和刪除四步。開始信令流程解析前，需要從協議解碼結果中提取信令合成所需要的關鍵信息字段，包括協議類型、CDR創建事件、CDR完成事件、關聯主鍵及取值等。當從解碼模塊接收到某條信令消息時，首先對此條消息進行超時查詢，一旦超時則進行超時處理并刪除該條消息中關聯主鍵KEY值對應的節點，退出合成；若未超時則判斷該KEY值對應的CDR結構體是否存在，若存在則將該條消息置入對應的CDR結構隊列末尾，并修改相關屬性對應信息；若不存在則通過識別該條消息是否屬于CDR創建事件，是則創建新的CDR并將其屬性值置入該CDR結構體緩存中。重復執行以上流程直至后續信息全部關聯合成到已創建的CDR記錄中并存儲于數據庫中，識別到CDR完成事件則代表信令合成流程結束。具體的實現流程如圖5所示。

圖5 信令合成處理流程

協議關聯是將處于不同平面和不同層級協議中的數據流關聯起來，得到有效的CDR數據源供后續模塊使用。在協議關聯過程中，關聯回填的目的是接收到控制面及用戶面協議消息的CDR后，對各CDR選取合適的字段形成關聯關系表，關聯各表并將數據匹配到缺省參數字段，最后把真實的字段值填入目標字段中，從而使信令面與業務面流程整合起來形成完整的用戶信息。協議解碼模塊解析出的協議關聯標識如表2所示。

表2 協議關聯標識表

信令面關聯標識主要是通過解析層三中的RRC和NAS協議獲取，其中RRC協議的關聯標識主要包括由5G全球唯一臨時標識(5G-Globally Unique Temporary Identifier，5G-GUTI)關聯獲得的國際移動用戶識別碼(International Mobile Subscriber Identification Number，IMSI)、C-RNTI、CellID和Transaction ID等，NAS協議關聯的標識包括IMSI、AMFID、5G-TMSI和SUCI等，一般選取IMSI、C-RNTI和CellID作為二者間的關聯標識來獲取信令面CDR；業務面關聯標識由MAC協議、RLC協議和PDCP協議解析而來，通過選取相同的UEID、邏輯信道Identifier和C-RNTI可以建立MAC協議數據流、RLC協議數據流及PDCP協議數據流之間的映射關系，從而關聯出業務面CDR。通過判斷信令面CDR和業務面CDR中是否具有相同的C-RNTI關聯標識可進一步說明來自不同層面的流程是否屬于同一用戶。業務面與信令面CDR的關聯合成流程如圖6所示。

圖6 業務面與信令面CDR關聯合成流程

(2) 統計出表模塊。統計模塊負責收集空口協議相關流程和信令，通過將消息按照業務類型、過程類型和特定消息類型進行分類統計，由此分類構成集合從而計算出協議消息個數和各種原因值出現情況等統計指數，便于用戶實時監測并反查異常數據、打印錯誤信息。由于該模塊是針對信令關聯合成相關信息的統計，因此統計功能器的觸發歸并到關聯合成模塊中CDR的接口函數里實現。出表模塊檢驗到有效的CDR后將其放入緩存中，再通過socket接口發送到服務器端并將關聯合成后的CDR按不同類型對出表文件進行劃分，生成csv文件存儲后供上層應用使用。

2.3 應用層

應用層主要是基于5G路測儀中信令監測系統對數據處理層所統計的CDR數據源信息展開具體分析，該層提供路測分析與用戶感知分析等服務，其中路測分析模塊針對監測到的CDR數據源進行網絡質量及優化分析；用戶感知分析模塊針對5G路測統計的各網絡關鍵性能指標構建5G網絡指標評估體系并動態評估網絡及業務質量。

3 信令合成算法設計

3.1 哈希索引生成算法

5G網絡中任意時刻都存在著海量的信令數據，為了提高信令關聯合成效率，需要對收到的每條信令消息按照一定規則建立哈希索引并實現關聯主鍵KEY與哈希表的一一映射。哈希索引生成算法的基本思想是從協議關聯標識中選取關鍵字KEY值作為自變量,通過設定的哈希函數求得函數值Value，對于同一信令流程中的關聯主鍵KEY構造出來的Value值必須始終相同且唯一[13]。當呼叫合成對散列表進行查詢操作時，首先通過哈希算法定位哈希表項，然后比較哈希關鍵字KEY并讀取對應的Value值，將KEY值映射到哈希散列表訪問CDR合成記錄，最終實現信令的快速查找操作。

哈希索引生成算法在構建Hash表時需要完成Hash函數的設計和KEY值的選取。目前存在的哈希函數構造方法包括除留余數法、直接尋址法、平方取中法和數字分析法等[14]。由于信令監測系統在呼叫合成過程中需要計算的Hash數值較大，且數值內部缺乏規律性，因此本文選擇除留余數法來構造哈希函數可以快速均勻地分布數據，實現相互映射。通過分析各協議主要關聯標識可知，信令面CDR的KEY值生成基于IMSI、C-RNTI和CellID參數。哈希函數的具體構造說明如下：

KEY=KEYi.IMSI+KEYi.C-RNTI+KEYi.CellID

(1)

Hi(KEY)=KEYmodN

(2)

Hashed_Addr=Hi(KEY)

(3)

式中：N為哈希表長；KEYi為某條待合成的信令消息對應的關鍵字；Hi(KEY)為關鍵字KEY對應的Value值(即哈希地址)。

在進行哈希查找時，當待查詢的關鍵字個數遠遠大于哈希表長時，不可避免地會出現哈希沖突，即不同的關鍵字搶奪相同哈希地址的現象[15]。目前解決沖突的哈希算法包括開放地址法、鏈地址法和再哈希法。發生哈希沖突時，開放地址法使用特定算法探尋下一個合適的地址。該方法實現簡單，未出現沖突時插入和查找速度快；缺點是一旦發生哈希沖突，會出現不同記錄在探測時爭奪同一后續哈希地址的堆積現象，從而增加查找時間，消耗大量內存。相比之下，鏈地址法則是將具有相同哈希地址的關鍵字節點鏈接在同一個單鏈表中，哈希表中只存儲每個單鏈表的頭指針。該方法優點在于無堆積現象，處理沖突簡單，刪除節點操作易于實現；缺點則是鏈地址法查找過程采用順序查找，當單鏈表上記錄過多時，將消耗大量時間頻繁訪問內存，導致算法性能降低[16]。

3.2 哈希平衡二叉樹算法

為了提高哈希表查找效率，本文在傳統哈希信令合成算法(Hash Signaling Synthesis Algorithm，HSSA)基礎上提出一種哈希平衡二叉樹算法(AVL Hash Signaling Synthesis Algorithm，AVL-HSSA)，將哈希散列表與平衡二叉查找樹相結合，旨在利用樹形結構以減少鏈地址法在哈希表中搜索數據所花費的時間。該算法的基本思想是：未出現哈希沖突時，采用開地址哈希表的存儲方式將樹的根節點存放于哈希表中，有快速訪問的優點；一旦出現沖突，則采用哈希平衡二叉查找樹結構來存儲哈希節點，將節點插入到對應二叉查找樹中，樹中每個節點含有用來指向左右子樹的指針、用作節點大小比較的關鍵值KEY和一個衡量左右子樹高度差的平衡因子。各節點均滿足平衡二叉樹存儲結構，左子樹上各節點對應的關鍵值KEY均小于根節點的值，右子樹上各節點對應的KEY值均大于根節點的值，且滿足左右子樹高度差不大于1[17]。AVL-HSSA處理沖突時的哈希表結構如圖7所示。

圖7 AVL-HSSA處理沖突時的哈希表結構

算法具體查找步驟如下：

Step1合成開始時從協議解碼器提取信令面關聯標識KEY。

Step2關鍵字KEY通過哈希函數求得對應的哈希地址Value。

Step3判斷是否發生哈希沖突，若無沖突執行Step 4，出現沖突則執行Step 5。

Step4采用開地址哈希表的存儲方式將未出現的關鍵字KEY(根節點)存儲于哈希表中。

Step5將具有相同哈希地址的關鍵字KEY插入到對應平衡二叉查找樹，并與根節點中的KEY值進行比較，直至查找到該KEY值對應的CDR緩存；若大于根節點則與右子樹各節點進行比較，待查詢到對應的CDR緩存后存儲并修改當前CDR屬性。

3.3 算法分析

信令合成過程利用Hash索引技術的高效性和可行性，建立一張以特定關鍵字為索引、CDR記錄為映射值的數據結構存儲模式，通過提取同一用戶信令流程中的關聯標識映射到哈希表，并對已有的CDR緩存比較查詢，最終實現同一用戶在同一信令流程中所有消息數據的關聯合成。在信令合成的查找過程中主要涉及關鍵字的比較操作，往往利用平均遍歷時間復雜度或平均查找長度(ASL)來衡量查找算法性能的優劣[18]。如表3所示，分別分析了Chain-HSSA和本文提出的AVL-HSSA在成功查詢到關鍵字時各指標的大小。

Chain-HSSA采用順序查找的方式依次與單鏈表中每一個關鍵字進行比較，直至查詢到相同關鍵字KEY結束。由于采用線性搜索方式，該算法的平均查找長度ASL為(n+1)/2，平均遍歷時間復雜度為O(n)，當單鏈表上記錄過多時，將消耗大量時間用于比較CDR緩存，導致查詢效率較低。而本文提出的AVL-HSSA突破了原有的存儲結構，使得AVL查找樹在哈希表中得以運用，在進行關鍵字的查詢過程中利用平衡二叉樹進行查找，每次查詢過程無須順序遍歷，平均查找長度為log2(n+1)-1，避免因線性結構導致查詢時間過長而使CDR合成效率降低。AVL-HSSA算法在執行插入、查詢操作時遍歷時間復雜度均為O(logn)。

4 實驗結果分析與比較

為了評價本文提出的AVL-HSSA在信令合成中的性能，我們與傳統哈希信令合成算法中的線性探測法(LP-HSSA)和鏈地址法(Chain-HSSA)進行了對比實驗。本文的實驗環境為Windows 10操作系統，Visual Studio 2017編譯器運行環境，Python 3.8環境下Matplotlib繪圖數據庫，硬件配置為64位操作系統，處理器為Inter(R) Core(TM) i5-8500 CPU 3.00 GHz。

在本實驗的測試過程中，以3GPP相關標準TS38.331和TS24.501協議為基礎，將5G路測儀從空口采集到的原始信令數據按照協議結構完成數據預處理并解碼，從解碼模塊獲取信令面合成所需要的關鍵字序列KEY作為本實驗的測試數據源。

4.1 查詢時間分析

裝填因子可定義為哈希散列表中存在的關鍵字個數除以哈希表長，是衡量哈希散列表裝滿程度的標志因子。當裝填因子為1的情況下，分別選取數據源中的1 000、2 000、3 000、4 000、5 000、6 000、7 000和8 000個數據通過LP-HSSA、Chain-HSSA和AVL-HSSA進行測試，測試結果如表4所示。

表4 三種哈希查找算法耗時(α=1) 單位：ms

從表4可見，在相同數據個數情況下對關鍵字進行查找，LP-HSSA所消耗的查詢時間最多、效率最低，Chain-HSSA消耗的查詢時間低于LP-HSSA，但仍高于AVL-HSSA；且當數據個數越大，三種算法所需要的查詢時間對比越明顯。上述測試結果中，改進后的AVL-HSSA相對于LP-HSSA和Chain-HSSA平均耗時降低了49.3%和33.1%。

從數據源中選取8 000個測試數據在不同裝填因子α下分別采用三種算法進行實驗，對關鍵字查找成功所消耗的時間如表5所示?？梢钥闯?，當裝填因子為1/10時，哈希表長遠大于查找關鍵字的個數，發生哈希沖突概率較小。此時對于LP-HSSA而言，當查詢到哈希表中存在待查詢關鍵字緩存，可通過哈希函數定位到哈希表項直接訪問關鍵字KEY，則查詢時間最短，為269.7 ms；AVL-HSSA在定位哈希表項時與LP-HSSA相同，不同之處在于讀取平衡二叉樹中數據時需要占用一定的內存訪問時間，因此導致AVL-HSSA查詢速度比LP-HSSA稍慢，查詢時間為276.4 ms。相比之下，Chain-HSSA在讀取表項并進行關鍵字比較時采用順序查找的方式，因此Chain-HSSA耗費更多的內存訪問時間，需要306.7 ms。

表5 不同α下三種哈希查找算法耗時 單位：ms

當裝填因子為1/2時，LP-HSSA對關鍵字的查找耗時明顯高于其余兩種算法，查找效率最低。相比之下，AVL-HSSA查詢時間最短，且裝填因子越大該方法的優勢越明顯，其穩定性與適應性遠高于其他兩種哈希算法。上述測試結果中，針對不同的裝填因子，改進后的AVL-HSSA相對于LP-HSSA和Chain-HSSA平均耗時降低了44.0%和29.3%。

4.2 內存分析

圖8展示了本文提出的AVL-HSSA同LP-HSSA和Chain-HSSA在信令合成過程占用內存大小的對比?？梢灾庇^地看到AVL-HSSA在內存消耗上具有一定優勢，所占用的內存最低。LP-HSSA開始創建哈希散列表時便一次性分配所有表項的內存，且當信令合成中數據源規模較大時會出現內存堆積現象，因此該方法消耗內存最大。Chain-HSSA在插入哈希表項時動態申請內存，占用內存大小隨合成關鍵字的增加而增加，當關鍵字個數增加至8 000個數據時，Chain-HSSA所消耗的內存大小是AVL-HSSA的2.5倍。

圖8 不同信令合成算法占用內存對比

5 結 語

通過研究5G網絡空中接口協議棧，提出了一種適用于5G路測儀的信令合成監測系統，采用層次化與模塊化相結合的軟件設計思想，大大提升了模塊間的獨立性及后續可擴展性。具體分析了信令解碼和信令合成詳細實現流程，并針對傳統信令合成中存在CDR合成效率低下、平均遍歷時間復雜度高等問題，提出了一種將哈希散列表與平衡二叉查找樹相結合的動態哈希信令合成算法，旨在利用樹形結構來減少鏈地址法在哈希表中搜索數據所花費的時間。通過對5G路測儀采集到的空口數據進行測試，驗證了改進算法的實時性與可行性，為5G海量用戶數據背景下構建新型信令監測方案及網絡優化測試提供了重要的理論基礎和參考意義。