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模型中的逻辑层次进行划分，从下往上依次为物理层、数据链路层和网络层。“两面”具体指控制平面协议栈与用户平面协议栈，通过识别数据类型属于控制信令还是用户数据进行区分[9-10]。

(1) 控制平面架构。5G NR控制平面协议栈包括NAS、RRC、PDCP、RLC、MAC及PHY层。NAS层负责将PDU会话管理、终端注册/去注册、鉴权及密钥协商等相关过程的信令数据传递至核心网[11]；RRC子层主要执行无线承载控制及移动性管理、系统消息的广播、寻呼、RRC连接管理等功能[12]；PDCP层对信令数据进行加密和完整性保护；RLC、MAC、PHY三层则执行数据传输的相关功能。协议栈控制平面架构如图1所示。

图1 协议栈控制平面架构

(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海量用户数据背景下构建新型信令监测方案及网络优化测试提供了重要的理论基础和参考意义。