CDMA2000 1xEV-DO測試儀WAP CDR合成算法的研究*

馮 平，張治中，夏 穎

（重慶郵電大學(xué) 通信網(wǎng)與測試技術(shù)重點(diǎn)實(shí)驗(yàn)室，重慶 400065）

1 引言

隨著各電信運(yùn)營單位的重組和3G牌照的發(fā)放，各通信網(wǎng)絡(luò)的融合與完善對網(wǎng)絡(luò)協(xié)議測試提出更高的要求，對于CDMA2000 1xEV-DO[1]商用網(wǎng)絡(luò)的實(shí)時(shí)監(jiān)測提出了更多的需求。WAP作為CDMA2000 1xEV-DO網(wǎng)絡(luò)中應(yīng)用層面的一個(gè)重要協(xié)議，對該協(xié)議模塊的業(yè)務(wù)監(jiān)測功能除了基本的消息解析、消息個(gè)數(shù)的統(tǒng)計(jì)和原因統(tǒng)計(jì)以外，還需對其公共過程和特定過程的相關(guān)具體流程實(shí)現(xiàn)提取，進(jìn)而實(shí)現(xiàn)更高級的專家分析和綜合數(shù)據(jù)報(bào)表輸出打印等高級功能。

目前國內(nèi)外已有相關(guān)研究人員對WAP[2]協(xié)議測試作了一定的研究，但主要集中在原始消息的初步處理上，對進(jìn)一步的CDR合成技術(shù)研究也曾采用在哈希（Hash）表上外接1個(gè)“鏈表”或者“桶”等處理方式。這雖然可以滿足實(shí)驗(yàn)室內(nèi)部的測試需求，但在外網(wǎng)大業(yè)務(wù)量的情況下容易引發(fā)因?yàn)楹铣伤俣然騼?nèi)存不足的原因而導(dǎo)致的呼叫信息丟失或合成不全等嚴(yán)重問題。針對這些問題，提出一種新型的CDR合成統(tǒng)計(jì)的可靠方案，采用Hash增強(qiáng)型動(dòng)態(tài)合成算法，并通過相關(guān)的內(nèi)存管理機(jī)制，實(shí)現(xiàn)呼叫流程的高效合成。因此，在CDMA2000 1xEV-DO網(wǎng)絡(luò)測試儀中對WAP協(xié)議模塊呼叫合成效率的研究與開發(fā)是十分必要的[3-4]。

2 WAP模塊實(shí)現(xiàn)方案

2.1 總體設(shè)計(jì)方案

網(wǎng)絡(luò)測試儀中WAP協(xié)議模塊業(yè)務(wù)監(jiān)測的數(shù)據(jù)處理流程如圖1所示。

圖1 總體設(shè)計(jì)流程圖

網(wǎng)絡(luò)測試儀在進(jìn)行具體的數(shù)據(jù)處理過程中，首先需要采集數(shù)據(jù)，通常有2種方式：一是通過各種數(shù)據(jù)捕捉卡從網(wǎng)絡(luò)上實(shí)時(shí)采集數(shù)據(jù)；二是對以前采集的歷史數(shù)據(jù)進(jìn)行回放。從數(shù)據(jù)源捕得數(shù)據(jù)后，使用獨(dú)立線程作業(yè)的數(shù)據(jù)緩存管理器對其進(jìn)行高效的管理、維護(hù)和控制，為解碼器提供讀取數(shù)據(jù)服務(wù)。協(xié)議解碼器使用一獨(dú)立線程對每條數(shù)據(jù)僅進(jìn)行概要解碼，為CDR的合成及統(tǒng)計(jì)提供相關(guān)信息。概要解碼完成后，將觸發(fā)CDR合成器和統(tǒng)計(jì)分析器進(jìn)行CDR合成與統(tǒng)計(jì)并對結(jié)果進(jìn)行保存及界面顯示。

2.2 算法方案選擇

WAP[5]協(xié)議模塊的呼叫合成可以采用不同的算法來實(shí)現(xiàn)，這里主要介紹線性表算法、紅黑二叉樹算法、Hash算法以及Hash增強(qiáng)型算法。而查找運(yùn)算的主要操作是關(guān)鍵字的比較，通常將查找過程中對關(guān)鍵字需要執(zhí)行的平均比較次數(shù)（即平均查找長度ASL）作為衡量一個(gè)查找算法效率的標(biāo)準(zhǔn)，具體定義為

式中：n代表結(jié)點(diǎn)的個(gè)數(shù)，pi是查找第i個(gè)結(jié)點(diǎn)的概率，ci是找到第i個(gè)結(jié)點(diǎn)所需進(jìn)行的比較次數(shù)。

下面分別對各個(gè)方案進(jìn)行闡述及比較。

1）方案1：線性表

在表的組織方式中，線性表是最簡單的1種，其主要包括3種查找方式，即順序查找、二分查找以及分塊查找。在等概率情況下，各種查找方式的ASL值、效率及復(fù)雜度等指標(biāo)如表1所示。

表1 等概率情況下各查找方式的指標(biāo)

對于順序存儲結(jié)構(gòu)，通常采取復(fù)雜度適中、效率較高的二分查找算法。

當(dāng)選用線性表算法時(shí)，二分查找效率最高，但二分查找只適用于靜態(tài)查找表。若要對動(dòng)態(tài)查找表進(jìn)行高效率的查找，則可采用紅黑二叉樹算法。

2）方案2：紅黑二叉樹算法

紅黑二叉樹是效率較高的一種樹型結(jié)構(gòu)，即在進(jìn)行插入和刪除操作時(shí)需要通過特定操作來保持二叉查找樹的平衡，從而獲得較高的查找性能。相對于線性表而言，其具有更高的效率及更好的統(tǒng)計(jì)性能。其ASL值為

3）方案 3：Hash算法

鑒于上面2種方案都是以關(guān)鍵字的比較為基本操作，不利于整個(gè)程序的運(yùn)行效率，提出一種采用直接尋址技術(shù)的新型Hash算法。

通常采用“除留余數(shù)法”來構(gòu)造Hash函數(shù)，取關(guān)鍵字key被某個(gè)不大于哈希表表長m的數(shù)p除后所得余數(shù)即為哈希地址，即

式中：通常選擇p為不大于哈希表表長的素?cái)?shù)，該算法的優(yōu)化性能取決于對p的選擇。其ASL值為

式中：n代表結(jié)點(diǎn)的個(gè)數(shù)，M為Hash表的容量，H為Hash函數(shù)開銷因子。

相比較而言，Hash算法優(yōu)于前面2種算法，適用范圍較大，效率較高。在理想情況下，無須任何比較就可找到待查關(guān)鍵字，查找的期望時(shí)間為O（1）。

4）方案4：Hash增強(qiáng)型算法

由于Hash沖突的存在，Hash表的查找過程仍是一個(gè)和關(guān)鍵字比較的過程，為了解決Hash沖突，Hash算法通常采取的方法是在Hash表上面外接“鏈表”或“桶”，以提高其查找效率。但“鏈表”及“桶”結(jié)構(gòu)的查找效率不高，而且所占內(nèi)存較大。若用“紅黑二叉樹”來代替“鏈表”及“桶”，即Hash增強(qiáng)型算法，則可以在保證效率的前提下，大大減少內(nèi)存占有量，便于整個(gè)系統(tǒng)的擴(kuò)展。該算法的ASL值為

綜上所述，為了最大效率地實(shí)現(xiàn)WAP協(xié)議模塊的CDR合成統(tǒng)計(jì)，Hash增強(qiáng)型算法為最佳選擇方案。

3 實(shí)現(xiàn)算法分析

3.1 Hash增強(qiáng)型算法分析

Hash[6]增強(qiáng)型算法的具體實(shí)現(xiàn)流程如圖2所示。當(dāng)1條WAP消息到來時(shí)，首先檢查該消息對應(yīng)的key值是否存在，存在則取出該key值所對應(yīng)的CDR，并修改其屬性值；反之則判斷該消息是否為WSP連接消息，是則在Hash表中添加一個(gè)WSP連接流程CDR節(jié)點(diǎn)，并為其指派一個(gè)新的CDR_ID，對應(yīng)修改其CDR屬性值并保存。另外，還需判斷該CDR流程是否已結(jié)束，若出現(xiàn)結(jié)束標(biāo)識則合成完成；否則修改狀態(tài)標(biāo)識并將CDR放回緩存中，進(jìn)行“超時(shí)處理”，以避免Hash表因一直等待接收CDR而造成“臃腫現(xiàn)象”。

3.2 哈希沖突解決方案

圖2 Hash增強(qiáng)型算法實(shí)現(xiàn)原理圖

哈希沖突常采用的解決方案主要有鏈?zhǔn)浇Y(jié)構(gòu)、桶式結(jié)構(gòu)及樹式結(jié)構(gòu)3種。Hash算法主要采用前2種，而Hash增強(qiáng)型算法則采用最后1種。

1）鏈?zhǔn)浇Y(jié)構(gòu)

Hash算法中引入了一種鏈?zhǔn)浇Y(jié)構(gòu)的高效算法，將所有關(guān)鍵詞為同義詞的記錄存儲在同一線性鏈表中。假設(shè)某哈希函數(shù)產(chǎn)生的哈希地址在區(qū)間[0，m-1]上，則設(shè)立1個(gè)指針型向量ChainHash，其每個(gè)分量的初始狀態(tài)都是空指針。凡哈希地址為i的記錄都插入到頭指針為ChainHash[i]的鏈表中。在鏈表中的插入位置可以在表頭或表尾，也可以在中間，以保持同義詞在同一線性鏈表中按關(guān)鍵字有序排列。此結(jié)構(gòu)比較簡單，速度較快，但內(nèi)存占用較多。

2）桶式結(jié)構(gòu)

為了解決鏈?zhǔn)浇Y(jié)構(gòu)的內(nèi)存浪費(fèi)問題，Hash算法中還引入了一種桶式結(jié)構(gòu)的高效算法。即在Hash表的外部掛“桶”，每個(gè)桶內(nèi)又根據(jù)協(xié)議特征有規(guī)律地裝特定的元素，減少整個(gè)Hash表所占內(nèi)存，而且桶內(nèi)的查找效率與鏈?zhǔn)浇Y(jié)構(gòu)相比，也提高了很多倍，但增加了復(fù)雜度。

3）樹式結(jié)構(gòu)

為了更大效率地實(shí)現(xiàn)WAP模塊的呼叫合成，Hash增強(qiáng)型算法提出了一種新型的樹式結(jié)構(gòu)算法，即在Hash表的基礎(chǔ)上增加1個(gè)紅黑二叉樹，該算法主要適用于對所占內(nèi)存較大的動(dòng)態(tài)查找表的高效率查找。

3種哈希沖突解決方案的執(zhí)行效率及復(fù)雜度比較如表2所示。

表2 3種哈希沖突解決方案的執(zhí)行效率及復(fù)雜度比較

4 算法結(jié)果驗(yàn)證

上述實(shí)現(xiàn)算法的效率比較如圖3所示。其中，n代表輸入節(jié)點(diǎn)數(shù)，t代表搜索所有節(jié)點(diǎn)所花費(fèi)的總時(shí)間。

圖3 算法效率比較圖

圖3直觀顯示了線性表算法、Hash算法以及紅黑二叉樹算法與Hash增強(qiáng)型算法的效率。在內(nèi)存容量固定不變的情況下，當(dāng)節(jié)點(diǎn)數(shù)n為105時(shí)，4種算法完成所有節(jié)點(diǎn)的搜索費(fèi)時(shí)約為 169 281 ms，37 407 ms，94 ms和 62 ms。可見，Hash增強(qiáng)型算法的搜索速度最快，相對于前3種算法而言，其效率依次約為2 730倍，603倍和1.5倍。

對于輸入量較大且無具體排序規(guī)律的WAP數(shù)據(jù)而言，要對其進(jìn)行快速有效的搜索，應(yīng)該選擇最后1種方案，即Hash增強(qiáng)型算法[6]，WAP模塊的具體CDR合成結(jié)果如圖4所示，該圖主要呈現(xiàn)了關(guān)于用戶瀏覽網(wǎng)頁圖片的1個(gè)CDR流程。本CDR流程共包括4條消息，即登錄網(wǎng)頁請求消息（Get）、響應(yīng)消息（Reply）、確認(rèn)響應(yīng)消息（Ack）以及瀏覽網(wǎng)頁成功消息，當(dāng)且僅當(dāng)收到最后1條消息時(shí)，才可以跟蹤并瀏覽對應(yīng)網(wǎng)址的頁面及內(nèi)容。

5 小結(jié)

圖4 WAP呼叫合成結(jié)果圖

對CDMA2000 1xEV-DO網(wǎng)絡(luò)測試儀中WAP模塊呼叫合成進(jìn)行了深入分析和研究，結(jié)合CDR的新型提取方法，能很好地實(shí)現(xiàn)對WAP協(xié)議模塊的實(shí)時(shí)業(yè)務(wù)監(jiān)測。Hash增強(qiáng)型技術(shù)的引入和合成相關(guān)數(shù)據(jù)信息的分離，大大提高了合成效率，同時(shí)也為后續(xù)協(xié)議模塊的合成方法理論提供很好的借鑒。目前該方法已經(jīng)應(yīng)用到CDMA2000 1xEV-DO網(wǎng)絡(luò)測試儀的開發(fā)中，在外場真實(shí)數(shù)據(jù)的測試過程中，取得了非常好的效果。

[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].重慶郵電大學(xué)學(xué)報(bào)：自然科學(xué)版，2007（1）：35-38.

[4]魏輝，張治中.TD-SCDMA網(wǎng)絡(luò)測試儀中SCCP協(xié)議解碼及上層PDU獲取方案[J].重慶郵電大學(xué)學(xué)報(bào)：自然科學(xué)版，2007（1）：47-52.

[5]吳章.WAP協(xié)議的安全策略在移動(dòng)電子商務(wù)中的應(yīng)用[J].現(xiàn)代商業(yè)，2008（24）：189-196.

[6]蟻平，湯澤瀅，曹先彬.基于關(guān)鍵屬性索引HASH函數(shù)的星型模型構(gòu)造算法[J].計(jì)算機(jī)工程與應(yīng)用，2006（21）：143-145.