增值業(yè)務(wù)監(jiān)測(cè)系統(tǒng)LE接口協(xié)議監(jiān)測(cè)方案研究

潘 勇，程 方，張治中

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

截至2012年底，中國(guó)電信移動(dòng)用戶數(shù)超過(guò)1．6億戶，隨著CDMA業(yè)務(wù)大規(guī)模發(fā)展及用戶數(shù)量的劇增，用戶對(duì)網(wǎng)絡(luò)質(zhì)量問(wèn)題日益敏感，為了給終端用戶提供更加方便快捷的服務(wù)，電信運(yùn)營(yíng)商提出了增值業(yè)務(wù)監(jiān)測(cè)系統(tǒng)需求。LE信令監(jiān)測(cè)系統(tǒng)作為整個(gè)增值業(yè)務(wù)監(jiān)測(cè)系統(tǒng)底層處理部分之一，其穩(wěn)定性與可行性對(duì)后期整個(gè)系統(tǒng)的實(shí)時(shí)監(jiān)控、預(yù)警、故障定位、參數(shù)分析，起到極其重要的作用。

監(jiān)測(cè)系統(tǒng)采用模塊化的設(shè)計(jì)思想，將系統(tǒng)劃分為解碼、合成等獨(dú)立相互協(xié)作的模塊。相比其他協(xié)議信令數(shù)據(jù)的二進(jìn)制比特流格式，解碼方法是依據(jù)協(xié)議規(guī)范將其讀取翻譯為有邏輯意義的信息［1］，鑒于LE接口信令格式的不同，本文在分析CDMA2000網(wǎng)絡(luò)中LE接口協(xié)議規(guī)范的基礎(chǔ)上，依協(xié)議規(guī)范要求，提出一種以可讀的可擴(kuò)展標(biāo)記語(yǔ)言(Extensible Markup Language，XML)文檔的嵌套關(guān)系和開始(結(jié)束)標(biāo)簽為依據(jù)關(guān)鍵信息的遞歸解碼方案。目前的呼叫詳細(xì)記錄(Calling Detail Record，CDR)合成方法中使用鏈地址法處理哈希沖突，大量的哈希查找操作存在效率低的問(wèn)題，降低合成效率。針對(duì)目前的不足，提出一種利用平衡二叉查找樹結(jié)構(gòu)存儲(chǔ)沖突節(jié)點(diǎn)的哈希算法以提高查找匹配效率。結(jié)合現(xiàn)網(wǎng)數(shù)據(jù)，該方案在增值業(yè)務(wù)監(jiān)測(cè)系統(tǒng)中完成了測(cè)試與驗(yàn)證，測(cè)試結(jié)果表明，該設(shè)計(jì)方案效果良好。

1 LE接口概述

LE接口協(xié)議是用來(lái)查詢移動(dòng)臺(tái)位置信息的應(yīng)用層協(xié)議，位于服務(wù)器定位平臺(tái)(Location Server)與外部位置應(yīng)用(LCS Client)之間，其提供的位置服務(wù)包括標(biāo)準(zhǔn)位置立即服務(wù)、緊急位置立即服務(wù)、標(biāo)準(zhǔn)位置報(bào)告服務(wù)、緊急位置報(bào)告服務(wù)等［2］。

LE接口能夠返回位置請(qǐng)求中目標(biāo)移動(dòng)終端的數(shù)字、文本等形式位置信息。定位流程如圖1所示:首先，外部位置應(yīng)用向網(wǎng)關(guān)移動(dòng)位置中心(GMLC)發(fā)送定位請(qǐng)求，GMLC通過(guò)歸屬位置寄存器(HLR)獲取被定位用戶的移動(dòng)交換中心(MSC)/服務(wù)支持節(jié)點(diǎn)(SGSN)地址;然后GLMC向MSC/SGSN發(fā)起定位請(qǐng)求，MSC/SGSN調(diào)用無(wú)線接入網(wǎng)中的定位網(wǎng)元進(jìn)行定位;最后，外部位置應(yīng)用將定位結(jié)果以MMS，WAP PUSH等形式發(fā)給用戶。

LE接口協(xié)議結(jié)構(gòu)分為三層:傳輸層、元素層和服務(wù)層。LE接口底層為傳輸層，定義了XML內(nèi)容的傳輸承載協(xié)議，常見的傳輸協(xié)議包括HTTP，WSP，SOAP等。傳輸層之上為元素層，定義了服務(wù)層中共用的元素。最上層為服務(wù)層，定義了LE接口能夠執(zhí)行的操作的核心集合，定義基本服務(wù)［3－4］。

2 接口監(jiān)測(cè)模塊方案設(shè)計(jì)

LE接口信令監(jiān)測(cè)系統(tǒng)采用模塊化的設(shè)計(jì)思想，通過(guò)將各模塊封裝成不同的動(dòng)態(tài)鏈接庫(kù)(Dynamic Link Library，DLL)，實(shí)現(xiàn)各功能模塊間的耦合。結(jié)合運(yùn)營(yíng)商的相關(guān)規(guī)范要求，對(duì)于LE接口監(jiān)測(cè)系統(tǒng)模塊的研究與開發(fā)主要分為劃分?jǐn)?shù)據(jù)的采集、消息緩存、消息解碼、CDR合成等功能。整個(gè)監(jiān)測(cè)模塊的設(shè)計(jì)如圖2所示，首先數(shù)據(jù)采集后將數(shù)據(jù)保存在消息緩存中;然后解碼器從消息緩存中取出消息后逐條進(jìn)行解碼，獲取相關(guān)字段信息，協(xié)議棧調(diào)度注冊(cè)的不同協(xié)議解碼器，LE接口協(xié)議棧由底至上依次為Ethernet，IP，TCP，HTTP，LE;然后將解碼所得到的信息交給協(xié)議分析合成器進(jìn)行CDR合成，同時(shí)得到當(dāng)前協(xié)議相關(guān)的一次通信流程，并將合成結(jié)果發(fā)送存盤;最后根據(jù)用戶需求實(shí)現(xiàn)合成統(tǒng)計(jì)的結(jié)果顯示。其中協(xié)議解碼按功能分兩種:基礎(chǔ)解碼，提取原始數(shù)據(jù)中的關(guān)鍵信息供CDR合成調(diào)用;詳細(xì)解碼，對(duì)原始數(shù)據(jù)逐字節(jié)逐比特的解碼，依據(jù)用戶需要實(shí)現(xiàn)詳細(xì)解碼結(jié)果樹顯示。

2.1 協(xié)議報(bào)文格式分析

XML允許定義自己有意義的標(biāo)記，因此可以最大程度地定制文檔，但XML沒(méi)有規(guī)則就無(wú)法順利地進(jìn)行正確數(shù)據(jù)交換;文檔類型定義(Document Type Definition，DTD)定義合法的XML文檔構(gòu)建模塊，使用一系列合法的元素來(lái)定義文檔的結(jié)構(gòu)。本協(xié)議使用的DTD規(guī)定了協(xié)議格式，并按照標(biāo)準(zhǔn)的DTD進(jìn)行數(shù)據(jù)的交換。通過(guò)DTD，XML文件攜帶一個(gè)自身格式的描述，從而可以一致地使用標(biāo)準(zhǔn)的DTD來(lái)交換數(shù)據(jù)。

XML文檔的主要構(gòu)建模塊是類似 ＜body＞、＜/body＞這樣的標(biāo)簽。均由以下構(gòu)建模塊構(gòu)成:元素，屬性，實(shí)體，PCDATA，CDATA。元素是XML文檔的主要構(gòu)建模塊;屬性可提供有關(guān)元素的額外信息，屬性總是被置于某元素的開始標(biāo)簽中，屬性總是以名稱或值的形式成對(duì)出現(xiàn)的;實(shí)體是用來(lái)定義普通文本的變量;被解析的字符數(shù)據(jù)(Parsed Character Data，PCDATA)為XML元素的開始標(biāo)簽與結(jié)束標(biāo)簽之間的文本，是會(huì)被解析器解析的文本;字符數(shù)據(jù)(Character Data，CDATA)，是不會(huì)被解析器解析的文本［5］。

2.2 解碼方案研究

可采用CmarkUp類來(lái)實(shí)現(xiàn)信令的解碼，它封裝了XML文檔文本、結(jié)構(gòu)和當(dāng)前位置，提供了得到元素屬性和數(shù)據(jù)的所有方法，可以實(shí)現(xiàn)對(duì)XML語(yǔ)言的解析。但是該方法存在以下缺點(diǎn):由于不同服務(wù)類型包含的元素不同，導(dǎo)致程序代碼的冗余，函數(shù)FindChildElem使用完全匹配元素名，易產(chǎn)生因元素名稱不匹配導(dǎo)致的消息解碼錯(cuò)誤或遺漏。在實(shí)驗(yàn)室環(huán)境中是可以實(shí)現(xiàn)解碼的需求，但是現(xiàn)網(wǎng)中要實(shí)現(xiàn)海量數(shù)據(jù)的處理，要求更快的處理速率，要優(yōu)化系統(tǒng)的內(nèi)存占用量和運(yùn)算時(shí)間復(fù)雜度，因此該方法不符合需求。

詳細(xì)解碼邏輯上是一棵樹，完成對(duì)一個(gè)信令數(shù)據(jù)包的解碼，將其翻譯為有邏輯意義的信息，通過(guò)函數(shù)FillTree將詳細(xì)解碼的父結(jié)點(diǎn)、本解碼項(xiàng)對(duì)應(yīng)的原始數(shù)據(jù)的起始(終止)偏移等信息添加到詳細(xì)解碼結(jié)果，將解碼信息實(shí)現(xiàn)樹結(jié)構(gòu)顯示。通過(guò)研究信令內(nèi)容結(jié)構(gòu)，提出一種可行的解碼算法:讀取消息緩存，判斷內(nèi)存中當(dāng)前指針指向的字符，若取值為“〈”且其后不為“/”，表明為開始標(biāo)簽，則取該標(biāo)簽元素為字段變量TagName，并將其作為子節(jié)點(diǎn)添加到詳細(xì)解碼樹的父節(jié)點(diǎn)下。依據(jù)XML元素嵌套結(jié)構(gòu)，運(yùn)用遞歸算法自然可得樹中父(子)節(jié)點(diǎn)層次關(guān)系。若取得當(dāng)前字符是“〉”，之后字符為數(shù)值或字符串，同時(shí)判斷數(shù)值或字符串之后兩個(gè)字節(jié)，判斷字符為“〈/”(即該標(biāo)簽對(duì)應(yīng)的結(jié)束標(biāo)志)，取出開始、結(jié)束標(biāo)簽間的數(shù)據(jù)內(nèi)容TagValue，并將TagValue賦給函數(shù)解碼該標(biāo)簽得到的標(biāo)簽變量TagName。這種解碼算法的優(yōu)勢(shì)在于，從信令數(shù)據(jù)中提取元素作為字段變量TagName，不需在代碼中枚舉標(biāo)簽元素名，也不需在代碼中體現(xiàn)元素間具體的嵌套包含關(guān)系。很好地利用了XML文件的可讀特點(diǎn)?；A(chǔ)解碼作用是提取該P(yáng)DU所包含的關(guān)鍵信息和上層SDU信息，為上層的合成提供支持，其算法與詳細(xì)解碼算法類似，提取關(guān)鍵字段信息并傳送給合成模塊以備調(diào)用，而不做父節(jié)點(diǎn)和開始(終止)偏移信息的提取添加。詳細(xì)解碼算法偽代碼如下:

上述代碼中，chBuf為消息報(bào)文頭指針，length為信令數(shù)據(jù)包長(zhǎng)，int nParent為樹父節(jié)點(diǎn)，字節(jié)偏移int nDecode-Offset表示本詳細(xì)解碼當(dāng)前指針與起始位置的字節(jié)偏移。

2.3 合成方案設(shè)計(jì)

解碼成功該協(xié)議之后數(shù)據(jù)傳送給合成模塊，調(diào)用注冊(cè)在此模塊之上的所有合成器，LE接口合成流程圖3所示。

現(xiàn)網(wǎng)中以消息為單位實(shí)現(xiàn)對(duì)各種協(xié)議和流程的海量數(shù)據(jù)進(jìn)行實(shí)時(shí)處理，首先對(duì)采集到的消息進(jìn)行解碼然后進(jìn)行CDR合成，與此同時(shí)建立完整的建立連接、通信、斷開連接的通信流程。實(shí)時(shí)處理中CDR合成過(guò)程同一業(yè)務(wù)CDR的查找算法顯得尤為重要。

通過(guò)閱讀協(xié)議規(guī)范，考慮到同一通信流程中的IP地址和TCP端口號(hào)Port是相同的，因此用散列查找法，選定IP地址值異或TCP端口值作為散列表的Key值。

從消息緩存取到一條消息，一個(gè)通信流程的消息時(shí)間是緊鄰的。首先進(jìn)行超時(shí)檢查處理，超時(shí)則刪除哈希表中KEY對(duì)應(yīng)節(jié)點(diǎn)，以避免Hash表內(nèi)存空間的浪費(fèi)和冗余，因查詢不必要的Key值而導(dǎo)致的效率低問(wèn)題。然后判斷該消息是否為請(qǐng)求消息，如沒(méi)有記錄則新建新的CDR ID并添加新的CDR;同時(shí)添加超時(shí)到另一散列表，該散列表也以IP和端口號(hào)為KEY值，當(dāng)再次讀取消息依據(jù)KEY值，比較消息時(shí)間和超時(shí)設(shè)定時(shí)間判斷是否超時(shí)。若查詢已經(jīng)存在該CDR，則修改CDR信息并保存;合成結(jié)束將該CDR的數(shù)據(jù)記錄發(fā)送存盤，同時(shí)刪除該CDR在散列表中的記錄節(jié)點(diǎn)，同時(shí)刪除超時(shí)檢查。

處理哈希沖突常采用的方法如鏈地址法［6－8］、再散列法，目前使用的鏈地址法原理是:連續(xù)的哈希地址(桶號(hào))散列離散化存放于數(shù)組中，數(shù)組中存放鏈表(桶)的頭指針;當(dāng)哈希地址沖突時(shí)，即不同Key值對(duì)應(yīng)同一哈希地址，則將該節(jié)點(diǎn)插入到該數(shù)組存放的鏈表中，桶內(nèi)采取順序存儲(chǔ)方式。查找過(guò)程中，哈希函數(shù)得到Key值對(duì)應(yīng)的哈希地址，桶內(nèi)節(jié)點(diǎn)順序比較Key值，相等則取出該節(jié)點(diǎn)value值，完成查找。鏈地址法處理沖突的優(yōu)點(diǎn)是處理沖突簡(jiǎn)單，非同義詞不會(huì)產(chǎn)生哈希沖突。刪除節(jié)點(diǎn)簡(jiǎn)單，只需刪去鏈表上相應(yīng)的節(jié)點(diǎn)。通過(guò)研究鏈地址法，發(fā)現(xiàn)以下問(wèn)題:指針需要額外的空間，影響平均查找速度，最大的問(wèn)題是鏈表采用順序存儲(chǔ)，查找平均遍歷的時(shí)間復(fù)雜度為O(n)，如有相同哈希值的數(shù)據(jù)則采用順序查找方式，效率非常低。

CDR合成中Hash添加、查找、刪除操作使用頻繁，查找運(yùn)算的主要操作是關(guān)鍵字的比較，查找過(guò)程的遍歷時(shí)間復(fù)雜度是衡量一個(gè)查找算法好壞的標(biāo)準(zhǔn)，是影響合成效率的最大因素。針對(duì)現(xiàn)網(wǎng)中海量數(shù)據(jù)處理中哈希遍歷效率低的問(wèn)題，通過(guò)研究解決哈希沖突的方法，提出改進(jìn)的處理哈希沖突的算法，以提高哈希查找效率。該方法是基于改進(jìn)哈希平均遍歷時(shí)間復(fù)雜度的:當(dāng)哈希地址沖突時(shí)，由采用鏈表的結(jié)構(gòu)改進(jìn)為平衡二叉查找樹結(jié)構(gòu)存儲(chǔ)沖突節(jié)點(diǎn)。將樹的根節(jié)點(diǎn)存放于哈希表數(shù)組中，當(dāng)哈希地址沖突時(shí)，將節(jié)點(diǎn)插入到對(duì)應(yīng)二叉查找樹中，樹中每個(gè)節(jié)點(diǎn)中含有用來(lái)指向左子樹的指針，用于指向右子樹的指針，和用作節(jié)點(diǎn)大小比較的關(guān)鍵值KEY。樹中關(guān)鍵字的存儲(chǔ)滿足二叉查找樹性質(zhì):左子樹上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值;右子樹上所有結(jié)點(diǎn)的值均大于它的根結(jié)點(diǎn)的值。二叉查找樹的期望遍歷時(shí)間復(fù)雜度為O(lgn)，在最壞的情況下會(huì)退化為線性結(jié)構(gòu)，操作的時(shí)間復(fù)雜度就變?yōu)榱薕(n)。為了避免出現(xiàn)線性結(jié)構(gòu)，導(dǎo)致查詢的查找長(zhǎng)度過(guò)長(zhǎng)，查詢效率降低。需要減小沖突時(shí)的查找長(zhǎng)度，減少查詢響應(yīng)時(shí)間。筆者的設(shè)計(jì)采用帶有平衡條件的二叉查找樹即AVL樹，樹中節(jié)點(diǎn)增加一個(gè)平衡因子即左右子樹高度差，使二叉查找樹左右子樹的高度差不超過(guò)1。把新節(jié)點(diǎn)插入二叉查找樹中，然后自底向根節(jié)點(diǎn)折回，當(dāng)插入節(jié)點(diǎn)之后二叉樹不平衡，則在該節(jié)點(diǎn)上進(jìn)行旋轉(zhuǎn)來(lái)完成插入操作，使高度差不大于1。從AVL樹中刪除節(jié)點(diǎn)，通過(guò)把待刪除的節(jié)點(diǎn)向下旋轉(zhuǎn)成葉子節(jié)點(diǎn)，然后直接刪除該葉子節(jié)點(diǎn)來(lái)完成。因?yàn)樵谛D(zhuǎn)成葉子節(jié)點(diǎn)期間最多有l(wèi)gn個(gè)節(jié)點(diǎn)被旋轉(zhuǎn)，而每次AVL旋轉(zhuǎn)耗費(fèi)恒定的時(shí)間，刪除處理在整體上耗費(fèi)O(lgn)時(shí)間。查找、插入和刪除在平均和最壞情況下都是O(lgn)，比鏈?zhǔn)巾樞虿檎倚侍岣吡撕芏啵岣吡顺霈F(xiàn)沖突情況下的查找效率。

3 結(jié)果驗(yàn)證

圖4所示為電信增值業(yè)務(wù)監(jiān)測(cè)系統(tǒng)中對(duì)LE接口的現(xiàn)網(wǎng)監(jiān)測(cè)結(jié)果。解碼數(shù)據(jù)無(wú)誤，協(xié)議層次清晰;屬于同一個(gè)CDR流程的不同消息以IP和TCP端口關(guān)聯(lián)，通過(guò)CDR合成得到通信流程，經(jīng)驗(yàn)證方案設(shè)計(jì)正確。

4 結(jié)束語(yǔ)

對(duì)LE接口協(xié)議及通信流程進(jìn)行了深入分析和研究，筆者以程序的正確性、健壯性、穩(wěn)定性為出發(fā)點(diǎn)，提出一種符合測(cè)試規(guī)范要求的接口信令監(jiān)測(cè)系統(tǒng)的設(shè)計(jì)方案，提出解碼算法有效解決了信令解碼問(wèn)題，并針對(duì)目前合成算法的不足，提出一種改進(jìn)哈希算法，改變處理哈希沖突的算法，有效解決了合成中的難題。該方案經(jīng)過(guò)運(yùn)營(yíng)商現(xiàn)網(wǎng)測(cè)試，能正確地、穩(wěn)定地實(shí)現(xiàn)LE接口的業(yè)務(wù)監(jiān)測(cè)。

:

［1］李丹鳳，張治中．LTE網(wǎng)絡(luò)監(jiān)測(cè)系統(tǒng)中DHCP協(xié)議的解碼方案研究［J］．電視技術(shù)，2012，36(9):69－73．

［2］中國(guó)電信集團(tuán)公司．RC 1．1．2，中國(guó)電信CDMA業(yè)務(wù)網(wǎng)絡(luò)接口協(xié)議技術(shù)規(guī)范－Le接口協(xié)議規(guī)范［S］．2008．

［3］ 3GPP．TS 23．171，F(xiàn)unctional stage 2 description of location services in UMTS［S］．2001．

［4］ LIF．TS 101 specification version 3．0．0，Open mobile alliance(OMA)，location inter－operability forum (LIF)mobile location protocol［S］．2002．

［5］ BRAY T，PAOLI J，SPERBERG－MCQUEEN C M．Extensible markup language(XML)1．0 W3C recommendation:REC－xml－20001006［EB/OL］．［2013－09－13］．http://www．w3．org/TR/1998/REC －xml－19980210/．

［6］張朝霞，劉耀軍．有效的哈希沖突解決辦法［J］．計(jì)算機(jī)應(yīng)用，2010，30(11):2966－2969．

［7］夏穎，張治中，馮平．CDMA2000網(wǎng)絡(luò)A1接口BSAP協(xié)議監(jiān)測(cè)技術(shù)的研究與應(yīng)用［J］．重慶郵電大學(xué)學(xué)報(bào):自然科學(xué)版，2009，21(6):757－763．

［8］ 陳玉花，張治中．TD－SCDMA 網(wǎng)絡(luò) Iu－PS口監(jiān)測(cè)技術(shù)的研究［J］．?dāng)?shù)字通信，2009(10):77－80．