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?？梢姡琀ash增強型算法的搜索速度最快，相對于前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.