CDMA2000 1xEV-DO测试仪WAP CDR合成算法的研究*

冯 平，张治中，夏 颖

（重庆邮电大学 通信网与测试技术重点实验室，重庆 400065）

1 引言

随着各电信运营单位的重组和3G牌照的发放，各通信网络的融合与完善对网络协议测试提出更高的要求，对于CDMA2000 1xEV-DO[1]商用网络的实时监测提出了更多的需求。WAP作为CDMA2000 1xEV-DO网络中应用层面的一个重要协议，对该协议模块的业务监测功能除了基本的消息解析、消息个数的统计和原因统计以外，还需对其公共过程和特定过程的相关具体流程实现提取，进而实现更高级的专家分析和综合数据报表输出打印等高级功能。

目前国内外已有相关研究人员对WAP[2]协议测试作了一定的研究，但主要集中在原始消息的初步处理上，对进一步的CDR合成技术研究也曾采用在哈希（Hash）表上外接1个“链表”或者“桶”等处理方式。这虽然可以满足实验室内部的测试需求，但在外网大业务量的情况下容易引发因为合成速度或内存不足的原因而导致的呼叫信息丢失或合成不全等严重问题。针对这些问题，提出一种新型的CDR合成统计的可靠方案，采用Hash增强型动态合成算法，并通过相关的内存管理机制，实现呼叫流程的高效合成。因此，在CDMA2000 1xEV-DO网络测试仪中对WAP协议模块呼叫合成效率的研究与开发是十分必要的[3-4]。

2 WAP模块实现方案

2.1 总体设计方案

网络测试仪中WAP协议模块业务监测的数据处理流程如图1所示。

图1 总体设计流程图

网络测试仪在进行具体的数据处理过程中，首先需要采集数据，通常有2种方式：一是通过各种数据捕捉卡从网络上实时采集数据；二是对以前采集的历史数据进行回放。从数据源捕得数据后，使用独立线程作业的数据缓存管理器对其进行高效的管理、维护和控制，为解码器提供读取数据服务。协议解码器使用一独立线程对每条数据仅进行概要解码，为CDR的合成及统计提供相关信息。概要解码完成后，将触发CDR合成器和统计分析器进行CDR合成与统计并对结果进行保存及界面显示。

2.2 算法方案选择

WAP[5]协议模块的呼叫合成可以采用不同的算法来实现，这里主要介绍线性表算法、红黑二叉树算法、Hash算法以及Hash增强型算法。而查找运算的主要操作是关键字的比较，通常将查找过程中对关键字需要执行的平均比较次数（即平均查找长度ASL）作为衡量一个查找算法效率的标准，具体定义为

式中：n代表结点的个数，pi是查找第i个结点的概率，ci是找到第i个结点所需进行的比较次数。

下面分别对各个方案进行阐述及比较。

1）方案1：线性表

在表的组织方式中，线性表是最简单的1种，其主要包括3种查找方式，即顺序查找、二分查找以及分块查找。在等概率情况下，各种查找方式的ASL值、效率及复杂度等指标如表1所示。

表1 等概率情况下各查找方式的指标

对于顺序存储结构，通常采取复杂度适中、效率较高的二分查找算法。

当选用线性表算法时，二分查找效率最高，但二分查找只适用于静态查找表。若要对动态查找表进行高效率的查找，则可采用红黑二叉树算法。

2）方案2：红黑二叉树算法

红黑二叉树是效率较高的一种树型结构，即在进行插入和删除操作时需要通过特定操作来保持二叉查找树的平衡，从而获得较高的查找性能。相对于线性表而言，其具有更高的效率及更好的统计性能。其ASL值为

3）方案 3：Hash算法

鉴于上面2种方案都是以关键字的比较为基本操作，不利于整个程序的运行效率，提出一种采用直接寻址技术的新型Hash算法。

通常采用“除留余数法”来构造Hash函数，取关键字key被某个不大于哈希表表长m的数p除后所得余数即为哈希地址，即

式中：通常选择p为不大于哈希表表长的素数，该算法的优化性能取决于对p的选择。其ASL值为

式中：n代表结点的个数，M为Hash表的容量，H为Hash函数开销因子。

相比较而言，Hash算法优于前面2种算法，适用范围较大，效率较高。在理想情况下，无须任何比较就可找到待查关键字，查找的期望时间为O（1）。

4）方案4：Hash增强型算法

由于Hash冲突的存在，Hash表的查找过程仍是一个和关键字比较的过程，为了解决Hash冲突，Hash算法通常采取的方法是在Hash表上面外接“链表”或“桶”，以提高其查找效率。但“链表”及“桶”结构的查找效率不高，而且所占内存较大。若用“红黑二叉树”来代替“链表”及“桶”，即Hash增强型算法，则可以在保证效率的前提下，大大减少内存占有量，便于整个系统的扩展。该算法的ASL值为

综上所述，为了最大效率地实现WAP协议模块的CDR合成统计，Hash增强型算法为最佳选择方案。

3 实现算法分析

3.1 Hash增强型算法分析

Hash[6]增强型算法的具体实现流程如图2所示。当1条WAP消息到来时，首先检查该消息对应的key值是否存在，存在则取出该key值所对应的CDR，并修改其属性值；反之则判断该消息是否为WSP连接消息，是则在Hash表中添加一个WSP连接流程CDR节点，并为其指派一个新的CDR_ID，对应修改其CDR属性值并保存。另外，还需判断该CDR流程是否已结束，若出现结束标识则合成完成；否则修改状态标识并将CDR放回缓存中，进行“超时处理”，以避免Hash表因一直等待接收CDR而造成“臃肿现象”。

3.2 哈希冲突解决方案

图2 Hash增强型算法实现原理图

哈希冲突常采用的解决方案主要有链式结构、桶式结构及树式结构3种。Hash算法主要采用前2种，而Hash增强型算法则采用最后1种。

1）链式结构

Hash算法中引入了一种链式结构的高效算法，将所有关键词为同义词的记录存储在同一线性链表中。假设某哈希函数产生的哈希地址在区间[0，m-1]上，则设立1个指针型向量ChainHash，其每个分量的初始状态都是空指针。凡哈希地址为i的记录都插入到头指针为ChainHash[i]的链表中。在链表中的插入位置可以在表头或表尾，也可以在中间，以保持同义词在同一线性链表中按关键字有序排列。此结构比较简单，速度较快，但内存占用较多。

2）桶式结构

为了解决链式结构的内存浪费问题，Hash算法中还引入了一种桶式结构的高效算法。即在Hash表的外部挂“桶”，每个桶内又根据协议特征有规律地装特定的元素，减少整个Hash表所占内存，而且桶内的查找效率与链式结构相比，也提高了很多倍，但增加了复杂度。

3）树式结构

为了更大效率地实现WAP模块的呼叫合成，Hash增强型算法提出了一种新型的树式结构算法，即在Hash表的基础上增加1个红黑二叉树，该算法主要适用于对所占内存较大的动态查找表的高效率查找。

3种哈希冲突解决方案的执行效率及复杂度比较如表2所示。

表2 3种哈希冲突解决方案的执行效率及复杂度比较

4 算法结果验证

上述实现算法的效率比较如图3所示。其中，n代表输入节点数，t代表搜索所有节点所花费的总时间。

图3 算法效率比较图

图3直观显示了线性表算法、Hash算法以及红黑二叉树算法与Hash增强型算法的效率。在内存容量固定不变的情况下，当节点数n为105时，4种算法完成所有节点的搜索费时约为 169 281 ms，37 407 ms，94 ms和 62 ms。可见，Hash增强型算法的搜索速度最快，相对于前3种算法而言，其效率依次约为2 730倍，603倍和1.5倍。

对于输入量较大且无具体排序规律的WAP数据而言，要对其进行快速有效的搜索，应该选择最后1种方案，即Hash增强型算法[6]，WAP模块的具体CDR合成结果如图4所示，该图主要呈现了关于用户浏览网页图片的1个CDR流程。本CDR流程共包括4条消息，即登录网页请求消息（Get）、响应消息（Reply）、确认响应消息（Ack）以及浏览网页成功消息，当且仅当收到最后1条消息时，才可以跟踪并浏览对应网址的页面及内容。

5 小结

图4 WAP呼叫合成结果图

对CDMA2000 1xEV-DO网络测试仪中WAP模块呼叫合成进行了深入分析和研究，结合CDR的新型提取方法，能很好地实现对WAP协议模块的实时业务监测。Hash增强型技术的引入和合成相关数据信息的分离，大大提高了合成效率，同时也为后续协议模块的合成方法理论提供很好的借鉴。目前该方法已经应用到CDMA2000 1xEV-DO网络测试仪的开发中，在外场真实数据的测试过程中，取得了非常好的效果。

[1]BECKER G E，RUDRAPATNA R，SOWLAY S，et al. Integrated network and element management system for the 3rd generation CDMA2000 wireless network[J].IEEE Commun.Surv.，2006，2（3）：2-14.

[2]3GPP TS24.008，Mobile radio interface layer 3 specification， core network protocols[S].2002.

[3]夏鞑，雒江涛，张治中.TD-SCDMA测试仪中Iub接口CDR的合成方案[J].重庆邮电大学学报：自然科学版，2007（1）：35-38.

[4]魏辉，张治中.TD-SCDMA网络测试仪中SCCP协议解码及上层PDU获取方案[J].重庆邮电大学学报：自然科学版，2007（1）：47-52.

[5]吴章.WAP协议的安全策略在移动电子商务中的应用[J].现代商业，2008（24）：189-196.

[6]蚁平，汤泽滢，曹先彬.基于关键属性索引HASH函数的星型模型构造算法[J].计算机工程与应用，2006（21）：143-145.