張冰瑩 程 方 程 渝

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

0 引 言

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

第五代移動(dòng)通信系統(tǒng)測試作為整個(gè)通信產(chǎn)業(yè)鏈的關(guān)鍵一環(huán)，能夠?qū)?G全網(wǎng)設(shè)備以及不斷演進(jìn)的新技術(shù)進(jìn)行驗(yàn)證[3]。在龐大的5G網(wǎng)絡(luò)部署與建設(shè)過程中，5G路測儀表對(duì)開展5G網(wǎng)絡(luò)質(zhì)量評(píng)估、探索新的信號(hào)、場景及拓?fù)浣Y(jié)構(gòu)等方面將提供可靠的海量數(shù)據(jù)源和數(shù)據(jù)分析能力。信令監(jiān)測作為5G路測儀表的關(guān)鍵技術(shù)，不僅是信令網(wǎng)維護(hù)和管理的重要手段之一，還可為其他應(yīng)用系統(tǒng)提供豐富的信令數(shù)據(jù)，在網(wǎng)絡(luò)優(yōu)化、網(wǎng)絡(luò)質(zhì)量分析、用戶感知評(píng)估等方面具有重要支撐作用。對(duì)于5G網(wǎng)絡(luò)空中接口，可通過控制平面監(jiān)測UE和gNB之間的網(wǎng)絡(luò)狀況，對(duì)協(xié)議的功能進(jìn)行評(píng)估測試，并直觀反映所處位置的網(wǎng)絡(luò)環(huán)境指標(biāo)，實(shí)現(xiàn)網(wǎng)絡(luò)運(yùn)行質(zhì)量評(píng)估和網(wǎng)絡(luò)優(yōu)化測試。

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

1 5G網(wǎng)絡(luò)概述

區(qū)別于傳統(tǒng)移動(dòng)通信網(wǎng)絡(luò)采用網(wǎng)絡(luò)實(shí)體或網(wǎng)元來描述系統(tǒng)架構(gòu)，5G網(wǎng)絡(luò)引入了網(wǎng)絡(luò)功能和服務(wù)的概念，完全分離控制平面與用戶平面。控制面利用接入及移動(dòng)性管理功能(Access and Mobility Function，AMF)和會(huì)話管理功能(Session Management Function，SMF)網(wǎng)元代替原LTE網(wǎng)元MME中的移動(dòng)和會(huì)話管理功能；用戶面通過用戶面網(wǎng)元(User Plane Function，UPF)節(jié)點(diǎn)負(fù)責(zé)管理。5G NR作為5G網(wǎng)絡(luò)連接UE和gNB之間的接口，其協(xié)議棧架構(gòu)總體可以概述為“三層兩面”，所謂“三層”是指空口協(xié)議棧按照OSI模型中的邏輯層次進(jìn)行劃分，從下往上依次為物理層、數(shù)據(jù)鏈路層和網(wǎng)絡(luò)層。“兩面”具體指控制平面協(xié)議棧與用戶平面協(xié)議棧，通過識(shí)別數(shù)據(jù)類型屬于控制信令還是用戶數(shù)據(jù)進(jìn)行區(qū)分[9-10]。

(1) 控制平面架構(gòu)。5G NR控制平面協(xié)議棧包括NAS、RRC、PDCP、RLC、MAC及PHY層。NAS層負(fù)責(zé)將PDU會(huì)話管理、終端注冊(cè)/去注冊(cè)、鑒權(quán)及密鑰協(xié)商等相關(guān)過程的信令數(shù)據(jù)傳遞至核心網(wǎng)[11]；RRC子層主要執(zhí)行無線承載控制及移動(dòng)性管理、系統(tǒng)消息的廣播、尋呼、RRC連接管理等功能[12]；PDCP層對(duì)信令數(shù)據(jù)進(jìn)行加密和完整性保護(hù)；RLC、MAC、PHY三層則執(zhí)行數(shù)據(jù)傳輸?shù)南嚓P(guān)功能。協(xié)議?？刂破矫婕軜?gòu)如圖1所示。

圖1 協(xié)議?？刂破矫婕軜?gòu)

(2) 用戶平面架構(gòu)。5G NR用戶平面協(xié)議棧主要包括SDAP、PDCP、RLC、MAC、PHY層。其中，業(yè)務(wù)數(shù)據(jù)適應(yīng)(Service Data Adaptation Protocol,SDAP)層屬于5G NR中新添加的一層協(xié)議，用于實(shí)現(xiàn)數(shù)據(jù)無線承載與QoS流之間的映射，以及在上下行數(shù)據(jù)添加QoS流標(biāo)識(shí)。協(xié)議棧用戶平面架構(gòu)如圖2所示。

圖2 協(xié)議棧用戶平面架構(gòu)

2 信令監(jiān)測系統(tǒng)設(shè)計(jì)

信令監(jiān)測系統(tǒng)以5G路測及數(shù)據(jù)采集技術(shù)作為基礎(chǔ)，完成從采集層面到應(yīng)用層面的全過程系統(tǒng)。按照3GPP及相關(guān)行業(yè)測試規(guī)范要求，根據(jù)不同層次的應(yīng)用需求將5G路測儀信令監(jiān)測系統(tǒng)整體架構(gòu)劃分為三層，依次為信令采集層、數(shù)據(jù)處理層和應(yīng)用層。

各子系統(tǒng)之間采用層次化與模塊化的軟件設(shè)計(jì)思路，獨(dú)自完成模塊具體功能，繼而交給其他模塊繼續(xù)執(zhí)行，大大提高了模塊之間的獨(dú)立性和后續(xù)可擴(kuò)展性。信令監(jiān)測系統(tǒng)框架如圖3所示。

圖3 信令監(jiān)測系統(tǒng)框架圖

2.1 數(shù)據(jù)采集層

信令采集層主要通過信令采集設(shè)備從5G網(wǎng)絡(luò)空中接口的信令鏈路上獲取無線端口用戶的原始信令數(shù)據(jù)與業(yè)務(wù)數(shù)據(jù)，完成接口適配、接口實(shí)時(shí)監(jiān)測等基礎(chǔ)操作，實(shí)現(xiàn)原始信令數(shù)據(jù)的實(shí)時(shí)采集、存儲(chǔ)并在一定時(shí)延要求下高效地轉(zhuǎn)發(fā)給數(shù)據(jù)處理層進(jìn)行信令數(shù)據(jù)分析。

2.2 數(shù)據(jù)處理層

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

表1 信道類型與數(shù)據(jù)類型對(duì)應(yīng)關(guān)系

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

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

圖4 協(xié)議解碼流程

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

圖5 信令合成處理流程

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

表2 協(xié)議關(guān)聯(lián)標(biāo)識(shí)表

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

圖6 業(yè)務(wù)面與信令面CDR關(guān)聯(lián)合成流程

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

2.3 應(yīng)用層

應(yīng)用層主要是基于5G路測儀中信令監(jiān)測系統(tǒng)對(duì)數(shù)據(jù)處理層所統(tǒng)計(jì)的CDR數(shù)據(jù)源信息展開具體分析，該層提供路測分析與用戶感知分析等服務(wù)，其中路測分析模塊針對(duì)監(jiān)測到的CDR數(shù)據(jù)源進(jìn)行網(wǎng)絡(luò)質(zhì)量及優(yōu)化分析；用戶感知分析模塊針對(duì)5G路測統(tǒng)計(jì)的各網(wǎng)絡(luò)關(guān)鍵性能指標(biāo)構(gòu)建5G網(wǎng)絡(luò)指標(biāo)評(píng)估體系并動(dòng)態(tài)評(píng)估網(wǎng)絡(luò)及業(yè)務(wù)質(zhì)量。

3 信令合成算法設(shè)計(jì)

3.1 哈希索引生成算法

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

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

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

(1)

Hi(KEY)=KEYmodN

(2)

Hashed_Addr=Hi(KEY)

(3)

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

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

3.2 哈希平衡二叉樹算法

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

圖7 AVL-HSSA處理沖突時(shí)的哈希表結(jié)構(gòu)

算法具體查找步驟如下：

Step1合成開始時(shí)從協(xié)議解碼器提取信令面關(guān)聯(lián)標(biāo)識(shí)KEY。

Step2關(guān)鍵字KEY通過哈希函數(shù)求得對(duì)應(yīng)的哈希地址Value。

Step3判斷是否發(fā)生哈希沖突，若無沖突執(zhí)行Step 4，出現(xiàn)沖突則執(zhí)行Step 5。

Step4采用開地址哈希表的存儲(chǔ)方式將未出現(xiàn)的關(guān)鍵字KEY(根節(jié)點(diǎn))存儲(chǔ)于哈希表中。

Step5將具有相同哈希地址的關(guān)鍵字KEY插入到對(duì)應(yīng)平衡二叉查找樹，并與根節(jié)點(diǎn)中的KEY值進(jìn)行比較，直至查找到該KEY值對(duì)應(yīng)的CDR緩存；若大于根節(jié)點(diǎn)則與右子樹各節(jié)點(diǎn)進(jìn)行比較，待查詢到對(duì)應(yīng)的CDR緩存后存儲(chǔ)并修改當(dāng)前CDR屬性。

3.3 算法分析

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

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

4 實(shí)驗(yàn)結(jié)果分析與比較

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

在本實(shí)驗(yàn)的測試過程中，以3GPP相關(guān)標(biāo)準(zhǔn)TS38.331和TS24.501協(xié)議為基礎(chǔ)，將5G路測儀從空口采集到的原始信令數(shù)據(jù)按照協(xié)議結(jié)構(gòu)完成數(shù)據(jù)預(yù)處理并解碼，從解碼模塊獲取信令面合成所需要的關(guān)鍵字序列KEY作為本實(shí)驗(yàn)的測試數(shù)據(jù)源。

4.1 查詢時(shí)間分析

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

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

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

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

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

當(dāng)裝填因子為1/2時(shí)，LP-HSSA對(duì)關(guān)鍵字的查找耗時(shí)明顯高于其余兩種算法，查找效率最低。相比之下，AVL-HSSA查詢時(shí)間最短，且裝填因子越大該方法的優(yōu)勢(shì)越明顯，其穩(wěn)定性與適應(yīng)性遠(yuǎn)高于其他兩種哈希算法。上述測試結(jié)果中，針對(duì)不同的裝填因子，改進(jìn)后的AVL-HSSA相對(duì)于LP-HSSA和Chain-HSSA平均耗時(shí)降低了44.0%和29.3%。

4.2 內(nèi)存分析

圖8展示了本文提出的AVL-HSSA同LP-HSSA和Chain-HSSA在信令合成過程占用內(nèi)存大小的對(duì)比?？梢灾庇^地看到AVL-HSSA在內(nèi)存消耗上具有一定優(yōu)勢(shì)，所占用的內(nèi)存最低。LP-HSSA開始創(chuàng)建哈希散列表時(shí)便一次性分配所有表項(xiàng)的內(nèi)存，且當(dāng)信令合成中數(shù)據(jù)源規(guī)模較大時(shí)會(huì)出現(xiàn)內(nèi)存堆積現(xiàn)象，因此該方法消耗內(nèi)存最大。Chain-HSSA在插入哈希表項(xiàng)時(shí)動(dòng)態(tài)申請(qǐng)內(nèi)存，占用內(nèi)存大小隨合成關(guān)鍵字的增加而增加，當(dāng)關(guān)鍵字個(gè)數(shù)增加至8 000個(gè)數(shù)據(jù)時(shí)，Chain-HSSA所消耗的內(nèi)存大小是AVL-HSSA的2.5倍。

圖8 不同信令合成算法占用內(nèi)存對(duì)比

5 結(jié) 語

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