（信號與信息處理專業(yè)論文）基于拓撲約束和數(shù)據(jù)挖掘的網(wǎng)絡(luò)故障定位.pdf

北京郵電大學(xué)碩士研究生畢業(yè)論文摘要 基于拓撲約束和數(shù)據(jù)挖掘的網(wǎng)絡(luò)故障定位 摘要 本文結(jié)合與企業(yè)合作的課題：基于數(shù)據(jù)挖掘的智能化移動通信 網(wǎng)絡(luò)故障管理關(guān)鍵技術(shù)研究，對基于拓撲約束的關(guān)聯(lián)規(guī)則挖掘技術(shù) 在移動通信網(wǎng)絡(luò)故障定位系統(tǒng)中的應(yīng)用及其實現(xiàn)方案進行了研究。 該課題通過研究移動通信網(wǎng)絡(luò)及其告警信息的特征，得出告警是 沿著網(wǎng)絡(luò)拓撲進行傳播的這一結(jié)論。基于此，本文提出了在關(guān)聯(lián)規(guī)則 挖掘算法中引入網(wǎng)絡(luò)拓撲模型作為約束，對告警數(shù)據(jù)進行挖掘中的處 理，將沒有存在拓撲連接關(guān)系的關(guān)聯(lián)規(guī)則過濾掉，從而提高挖掘的效 率和正確性。 本文主要針對關(guān)聯(lián)規(guī)則經(jīng)典挖掘算法存在的各種不足，提出采用 f p g r o w t h 非時序關(guān)聯(lián)規(guī)則挖掘算法，并在該算法的實現(xiàn)過程中加入 了網(wǎng)絡(luò)拓撲關(guān)系。該算法僅掃描數(shù)據(jù)庫兩次，不產(chǎn)生候選集，具有明 顯的性能優(yōu)勢，尤其適合我們將要面對的大型數(shù)據(jù)庫，可以節(jié)省大量 時間，提高執(zhí)行效率。 作者參與了b u p t p r i s m i n e r 智能化告警分析原型系統(tǒng)的研發(fā)， 對f p g r o w t h 非時序關(guān)聯(lián)規(guī)則算法進行了研究和實現(xiàn)，并配合小組成 員把算法集成入b u p t p r i s m i n e r 系統(tǒng)，完成了模塊測試、代碼維護 和文檔編寫等工作。 關(guān)鍵詞：故障定位拓撲模型數(shù)據(jù)挖掘關(guān)聯(lián)規(guī)則f p g r o w t h 算 法 北京郵電大學(xué)碩士研究生畢業(yè)論文a b s t r a c t n e t w o r kf a u i rl o c a l i z a t i o n b a s e do nn e t w o r kt o p o l o g ya n dd a t am i n i n g a b s t r a c t b a s e do nt h ep r o j e c td e v e l o p e dc o o p e r a t i v e l yw i t he n t e r p r i s e ：( ( k e y t e c h n i q u e si ni n t e l l i g e n tm o b i l en e t w o r kf a u l tm a n a g e m e n tb a s e do n d a t am i n i n g ) ) ，t h ep a p e rf o c u s e do nt h ea p p l i c a t i o no ft e c h n i q u e so f m i n i n ga s s o c i a t i o nr u l e si nt h em o b i l en e t w o r kf a u l tl o c a l i z a t i o ns y s t e m t h ep r o j e c tr e a c h e sac o n c l u s i o nt h a ta l a r m ss p r e a dt h r o u g hn e t w o r k t o p o l o g y , a f t e rs t u d y i n gt h em o b i l en e t w o r ka n di t sa l a r m s b a s e do nt h e c o n c l u s i o n ，t h ep a p e rp r e s e n t si n t r o d u c i n gn e t w o r kt o p o l o g yi nm i n i n g a s s o c i a t i o nr u l e st oi n c r e a s em i n i n ge f f i c i e n c ya n dv a l i d i t y t h en e t w o r k t o p o l o g yc a nb eu s e dt op r o c e s st h ea l a r md a t ad u r i n gm i n i n g ，t h u s f i l t r a t i n ga l a r m sa n da s s o c i a t i o nr u l e st h a th a v en ot o p o l o g yc o r r e l a t i o n i na l l u s i o nt ot h ed e f i c i e n c yo ft r a d i t i o n a la l g o r i t h m sf o rm i n i n g a s s o c i a t i o nr u l e s ，t h e p a p e rp r e s e n t su s i n gf p - g r o w t ha l g o r i t h ma n d b r i n g sn e t w o r kt o p o l o g yi n t ot h ea l g o r i t h m t h i sa l g o r i t h ms c a n st h e d a t a b a s eo n l yt w i c e ，i sb e s tf o rh u g ed a t a b a s e ，c a ns a v et i m ea n di m p r o v e e x e c u t i o ne f f i c i e n c y t h ea u t h o r p a r t i c i p a t e d i nt h e s t u d ya n dd e v e l o p m e n to ft h e b u p 耶r i s m i n e r i n t e l l i g e n t a l a r m a n a l y s i ss y s t e m c o n c r e t e l y , t h e a u t h o rt o o kp a r ti nr e a l i z i n gt h ef p - g r o w t ha l g o r i t h m ，h e l po t h e rt e a m m e m b e r st oi n t e g r a t et h ea l g o r i t h m si n t ot h eb u p t p r i s m i n e rs y s t e m m e a n w h i l et h e a u t h o r a c c o m p l i s h e d t h em o d u l e t e s t i n g ，c o d e m a i n t e n a n c e ，d o c u m e n tw r i t i n ga n ds oo n k e yw o r d s ：f a u l tl o c a l i z a t i o n t o p o l o g ym o d e l d a t am i n i n g a s s o c i a t i o nr u l e sf p - g r o w t h a l g o r i t h m 獨創(chuàng)性( 或創(chuàng)新性) 聲明 本人聲明所呈交的論文是本人在導(dǎo)師指導(dǎo)下進行的研究工作及取得的研究 成果。盡我所知，除了文中特別加以標注和致謝中所羅列的內(nèi)容以外，論文中不 包含其他人已經(jīng)發(fā)表或撰寫過的研究成果，也不包含為獲得北京郵電大學(xué)或其他 教育機構(gòu)的學(xué)位或證書而使用過的材料。與我一同工作的同志對本研究所做的任 何貢獻均已在論文中作了明確的說明并表示了謝意。 申請學(xué)位論文與資料若有不實之處，本人承擔一切相關(guān)責任。 本人簽名：困叢日期：絲墨：查：蘭z 關(guān)于論文使用授權(quán)的說明 學(xué)位論文作者完全了解北京郵電大學(xué)有關(guān)保留和使用學(xué)位論文的規(guī)定，即： 研究生在校攻讀學(xué)位期間論文工作的知識產(chǎn)權(quán)單位屬北京郵電大學(xué)。學(xué)校有權(quán)保 留并向國家有關(guān)部門或機構(gòu)送交論文的復(fù)印件和磁盤，允許學(xué)位論文被查閱和借 閱；學(xué)?？梢怨紝W(xué)位論文的全部或部分內(nèi)容，可以允許采用影印、縮印或其它 復(fù)制手段保存、匯編學(xué)位論文。( 保密的學(xué)位論文在解密后遵守此規(guī)定) 保密論文注釋：本學(xué)位論文屬于保密在年解密后適用本授權(quán)書。非保密論 文注釋：本學(xué)位論文不屬于保密范圍，適用本授權(quán)書。 本人簽名：! 塑趁日期：絲q 壁：查：蘭z 導(dǎo)師簽名：二盔 o 北京郵電大學(xué)碩十研究生畢業(yè)論文第一章緒論 第一章緒論 本章主要介紹了論文的課題背景、電信網(wǎng)絡(luò)故障定位技術(shù)在國內(nèi)外的發(fā)展現(xiàn) 狀以及作者在論文期間所作的工作。 1 1 課題背景 本課題依托于北京郵電大學(xué)和i b m 中國研究院聯(lián)合研究的開放課題“基于 數(shù)據(jù)挖掘的智能化移動通信網(wǎng)絡(luò)故障管理關(guān)鍵技術(shù)研究一。該課題的主要研究內(nèi) 容是以北京郵電大學(xué)模式識別實驗室為某省級移動公司開發(fā)的t a c a s 告警關(guān)聯(lián) 與分析系統(tǒng)為基礎(chǔ)，采用創(chuàng)新的方法和技術(shù)，進一步提高告警分析的速度、精度， 減少對人工專家知識的依賴，最終提高故障定位的準確性和效率，以研制出一個 適用于大規(guī)模電信網(wǎng)絡(luò)和海量數(shù)據(jù)應(yīng)用環(huán)境下的智能化實時故障診斷、影響分析 和故障定位系統(tǒng)。 故障定位是網(wǎng)絡(luò)故障管理的核心。隨著現(xiàn)代通信系統(tǒng)的產(chǎn)生與發(fā)展，故障定 位問題備受關(guān)注，并且提出了許多故障定位方案。但是通信系統(tǒng)逐漸地日趨復(fù)雜 并且提供一些新的性能，因此故障定位方案也需要進一步的改進。在故障定位技 術(shù)中常用的是告警關(guān)聯(lián)，即對相同故障源的告警進行分組的處理過程。 傳統(tǒng)的電信網(wǎng)絡(luò)告警關(guān)聯(lián)挖掘，沒有與特定的網(wǎng)絡(luò)拓撲結(jié)構(gòu)相結(jié)合，這種方 式存在兩大缺陷，首先待挖掘的數(shù)據(jù)量很大，其次挖掘的關(guān)聯(lián)規(guī)則多且冗余。為 了克服這兩大缺陷，提出了構(gòu)建網(wǎng)絡(luò)物理拓撲模型，通過網(wǎng)絡(luò)拓撲模型對告警數(shù) 據(jù)進行挖掘中的處理，將沒有存在拓撲連接關(guān)系的關(guān)聯(lián)規(guī)則過濾掉，從而提高挖 掘的效率和正確性。通過對某省級移動通信的網(wǎng)絡(luò)結(jié)構(gòu)和實際告警數(shù)據(jù)進行分析 后，提出采用數(shù)據(jù)庫表來建立和存儲網(wǎng)元拓撲關(guān)系信息，從而實現(xiàn)網(wǎng)絡(luò)物理拓撲 的建模。 基于拓撲約束的關(guān)聯(lián)規(guī)則挖掘算法，依照建立的拓撲結(jié)構(gòu)模型得到的網(wǎng)元之 間的層次關(guān)系，將發(fā)生各個告警的各個設(shè)備進行層次編碼。由拓撲結(jié)構(gòu)體現(xiàn)出的 各網(wǎng)元之間的連接關(guān)系，結(jié)合故障的傳播路徑，得到關(guān)聯(lián)規(guī)則挖掘過程的約束條 件。在挖掘關(guān)聯(lián)規(guī)則過程中，兩個或多個項目是否可能連接為一個項集要由這種 約束條件加以限制。采用基于拓撲約束的關(guān)聯(lián)規(guī)則挖掘算法，實現(xiàn)了在連接前更 大程度地減少待檢測的組合個數(shù)，明顯降低了工作量，同時保證得到的規(guī)則滿足 拓撲關(guān)系，提高了挖掘告警關(guān)聯(lián)規(guī)則過程的時效性和結(jié)果的準確性。 第l 頁 北京郵電大學(xué)碩十研究生畢業(yè)論文第一章緒論 采用基于網(wǎng)絡(luò)拓撲約束的關(guān)聯(lián)規(guī)則數(shù)據(jù)挖掘技術(shù)來改進移動通信網(wǎng)絡(luò)故障 定位系統(tǒng)，就是在這樣的背景下提出的。 1 2 故障定位系統(tǒng)綜述 1 2 1 故障定位的概念 網(wǎng)絡(luò)管理卜1 是指對網(wǎng)絡(luò)的運行狀態(tài)進行檢測和控制，使其能夠有效、可靠、 安全、經(jīng)濟地提供服務(wù)。國際標準化組織( i s o ) 將網(wǎng)絡(luò)管理功能劃分為配置管 理、性能管理、故障管理、安全管理和計費管理五個領(lǐng)域。故障管理的目的是迅 速發(fā)現(xiàn)和糾正網(wǎng)絡(luò)故障，動態(tài)維護網(wǎng)絡(luò)的有效性。故障管理卜1 的主要功能有告警 監(jiān)測、故障定位、測試、業(yè)務(wù)恢復(fù)、故障修復(fù)以及故障日志維護等。故障定位是 網(wǎng)絡(luò)故障管理的核心。在通信系統(tǒng)中，故障的發(fā)生是不可避免的，對于一個健全 可靠的系統(tǒng)而言，快速隔離并檢測出故障是必要的。 故障定位卜1 是通過一些觀測的告警信息發(fā)現(xiàn)準確根源故障的過程，包括故障 隔離、事件關(guān)聯(lián)以及根故障分析。故障p 1 可以定義為那些引起系統(tǒng)以非正常方式 操作的事件，可分為：1 ) 網(wǎng)絡(luò)配置錯誤；2 ) 網(wǎng)絡(luò)硬件問題，包括網(wǎng)卡故障、 m o d e m 故障、通訊媒體故障、路由器轉(zhuǎn)換故障等；3 ) 網(wǎng)絡(luò)軟件異常，如路由軟 件故障、路由表刷新異常、網(wǎng)絡(luò)激活應(yīng)用軟件異常等；4 ) 網(wǎng)絡(luò)流量異常，例如 分組風暴等。在通信網(wǎng)絡(luò)中，一個故障可能引起網(wǎng)管中心的多重告警，其產(chǎn)生原 因是：1 ) 故障重復(fù)發(fā)生；2 ) 一個業(yè)務(wù)可能多次調(diào)用有故障的組建：3 ) 一個設(shè) 備的一個故障產(chǎn)生多個告警；4 ) 多個設(shè)備同時檢測到同一故障并同時發(fā)出告警； 5 ) 故障傳播到其他網(wǎng)絡(luò)產(chǎn)生額外告警。 網(wǎng)絡(luò)或設(shè)備檢測到故障，發(fā)出描述故障現(xiàn)象的消息稱為告警，它是從網(wǎng)絡(luò)設(shè) 備角度對故障的一個描述。組成網(wǎng)絡(luò)的設(shè)備( 組成設(shè)備的模塊) 是相互影響的， 一個設(shè)備發(fā)生異常，相關(guān)設(shè)備會表現(xiàn)出故障征兆，導(dǎo)致每一個相關(guān)設(shè)備都發(fā)出告 警信息，這種現(xiàn)象稱為故障的傳播特性。由于大部分故障都是不可直接觀測的， 系統(tǒng)必須通過已知的告警信息推理出根故障所在。告警可能攜帶的信息有：產(chǎn)生 告警的網(wǎng)元的i d ，故障類型，時間標簽，告警標志符，故障嚴重級別，故障的 文本描述等r j 。 為了提供快速、可靠、有競爭力的服務(wù)，移動通信網(wǎng)絡(luò)管理系統(tǒng)要適應(yīng)網(wǎng)絡(luò) 規(guī)模擴張、帶寬提高、復(fù)雜性增強的變化。隨著網(wǎng)絡(luò)結(jié)構(gòu)規(guī)模日益復(fù)雜，網(wǎng)絡(luò)故 障管理越來越困難。網(wǎng)絡(luò)故障不僅會降低客戶的滿意度，也會導(dǎo)致經(jīng)濟損失。故 障的發(fā)生在所難免，快速檢測和定位故障是保障網(wǎng)絡(luò)穩(wěn)定運行的關(guān)鍵因素，也是 網(wǎng)絡(luò)管理的首要任務(wù)。 第2 頁 北京郵電火學(xué)碩士研究生畢業(yè)論文第一章緒論 1 2 2 現(xiàn)存的故障定位技術(shù) 在故障定位技術(shù)中常用的是告警關(guān)聯(lián)，即對相同故障源的告警進行分組的處 理過程。傳統(tǒng)上的告警關(guān)聯(lián)性分析主要是通過人工分析出關(guān)聯(lián)規(guī)則，然后再加入 到系統(tǒng)當中。然而，隨著網(wǎng)絡(luò)規(guī)模越來越大，單純依靠網(wǎng)絡(luò)管理人員獲得告警關(guān) 聯(lián)性知識已經(jīng)無法滿足網(wǎng)絡(luò)維護的需要。網(wǎng)絡(luò)告警數(shù)據(jù)庫中存儲了大量的歷史告 警信息，其中蘊含了許多反映網(wǎng)絡(luò)運行規(guī)律的有用信息，利用這些信息可以完善 網(wǎng)絡(luò)故障管理。因此可通過用知識發(fā)現(xiàn)的方法分析告警序列，挖掘告警關(guān)聯(lián)規(guī)則。 在移動通信網(wǎng)絡(luò)故障管理中，現(xiàn)今的技術(shù)研究引入了數(shù)據(jù)挖掘的概念和方 法。其基本思想是將數(shù)據(jù)挖掘技術(shù)引入到告警關(guān)聯(lián)中，目的是為了揭示出隱含在 海量原始故障征兆信息后面有意義的知識和規(guī)則，從而以更全面的視角解釋網(wǎng)絡(luò) 故障及性能的問題，使網(wǎng)絡(luò)管理員能快速的進行故障定位、進一步做出故障決策 并完成預(yù)測。這一方法能夠較好的適應(yīng)網(wǎng)絡(luò)的動態(tài)變化，從而找出告警數(shù)據(jù)之間 存在的規(guī)則。 數(shù)據(jù)挖掘在移動網(wǎng)絡(luò)領(lǐng)域的典型應(yīng)用有客戶行為分析、客戶流失預(yù)測、告警 序列分析、網(wǎng)絡(luò)關(guān)鍵性能指標預(yù)測等。從國內(nèi)來看，不少企業(yè)也都意識到將數(shù)據(jù) 挖掘應(yīng)用于告警關(guān)聯(lián)分析的重要性，開展了類似的項目研究。 1 2 3 電信網(wǎng)絡(luò)故障定位系統(tǒng)存在的不足 目前，數(shù)據(jù)挖掘的商用產(chǎn)品，如s p s s ，s a s 以及i b m 的i n t e l l i g e n tm i n e r 等都不適合處理移動網(wǎng)絡(luò)告警這種關(guān)于時間序列的問題。而業(yè)內(nèi)也出現(xiàn)了一些告 警關(guān)聯(lián)應(yīng)用系統(tǒng)，如s i n e r g i a 系統(tǒng)、i b m 的n e t f a c t 系統(tǒng)以及a r t s 公司的 d e c s 系統(tǒng)，但這些系統(tǒng)在使用友好性、處理效率等方面也做得不是很完善。 總體分析，現(xiàn)有的故障定位系統(tǒng)存在如下不足： 1 ) 挖掘耗時長 現(xiàn)有挖掘算法通常以告警標題( 告警類型) 作為候選n 項集進行挖掘，因 為告警標題可能超過千種，從而隨著項集空間的增大，計算量顯著增大，導(dǎo)致挖 掘算法計算量大，效率低，耗時長 2 ) 挖掘結(jié)果準確度低 實際的告警信息存在長尾現(xiàn)象，大量的設(shè)備和大量的告警標題產(chǎn)生的告警信 息非常少，因此實際告警規(guī)則或者告警序列在全部告警數(shù)據(jù)中可能是稀疏的，這 導(dǎo)致了現(xiàn)有挖掘算法通常挖掘出大量的沒有實際價值的告警規(guī)則或者序列模式。 另外，現(xiàn)有挖掘算法都沒有考慮網(wǎng)絡(luò)的拓撲約束，所挖掘出來的告警規(guī)則或 者序列模式與網(wǎng)絡(luò)結(jié)構(gòu)沒有任何關(guān)聯(lián)，因此大大降低了挖掘結(jié)果的準確程度。 第3 頁 北京郵電大學(xué)碩十研究生畢業(yè)論文第一章緒論 3 ) 采用固定時間窗口進行挖掘，規(guī)則和序列模式不完整 目前有關(guān)告警關(guān)聯(lián)的數(shù)據(jù)挖掘算法都會設(shè)置一個固定的時間窗口，雖然設(shè)置 固定的時間窗口使得算法比較容易實現(xiàn)，但是將會導(dǎo)致其挖掘出來的告警關(guān)聯(lián)規(guī) 則正確性低。應(yīng)該設(shè)置動態(tài)的時間窗口，根據(jù)不同的告警或不同的網(wǎng)元動態(tài)地調(diào) 整時間窗口。 1 3 基于拓撲約束的關(guān)聯(lián)規(guī)則挖掘技術(shù)在電信網(wǎng)絡(luò)故障定位系統(tǒng)中 的應(yīng)用 數(shù)據(jù)挖掘是從大量的、不完全的、有噪聲的、模糊的、隨機的數(shù)據(jù)中，提取 隱含在其中的、人們事先不知道的但又是潛在有用的信息和知識的過程。i j l 數(shù)據(jù) 挖掘就是知識發(fā)現(xiàn)技術(shù)在數(shù)據(jù)庫領(lǐng)域中的應(yīng)用，在一個已知狀態(tài)的數(shù)據(jù)集上，通 過設(shè)置一定的學(xué)習算法，發(fā)掘出數(shù)據(jù)間隱含的一些內(nèi)在規(guī)律，即獲取( 發(fā)現(xiàn)) 所 謂的知識。 在大的通信網(wǎng)中，一個故障產(chǎn)生很多告警，當若干故障并存時，產(chǎn)生大量的 告警，這些告警隱藏了故障的原因，以至難以進行故障診斷和定位，這是當今網(wǎng) 絡(luò)故障管理的一個難題。網(wǎng)絡(luò)維護人員感興趣的不是告警事件本身，而是引起告 警的設(shè)備故障。盡管這些告警直接或間接的反映故障現(xiàn)象，但大量的告警事件形 成告警風暴，使迅速、準確定位故障變得很困難。將數(shù)據(jù)挖掘技術(shù)引入到告警關(guān) 聯(lián)中，利用基于規(guī)則的相關(guān)性分析技術(shù)，一方面將多個告警歸結(jié)成較少的告警， 過濾大量的冗余告警，另一方面用于實時故障診斷和故障定位，可以輔助網(wǎng)絡(luò)管 理人員，過濾冗余信息，準確的定位故障，及時排除故障，保障網(wǎng)絡(luò)可靠的運行。 但是，傳統(tǒng)的告警關(guān)聯(lián)規(guī)則挖掘系統(tǒng)大多是直接對原始告警數(shù)據(jù)進行簡單的 預(yù)處理就用挖掘算法進行挖掘，從而得到告警之間的關(guān)聯(lián)關(guān)系。這種方法盡管可 以挖掘出有效的告警關(guān)聯(lián)規(guī)則，但是對于海量的告警數(shù)據(jù)來說，這樣的告警關(guān)聯(lián) 規(guī)則挖掘系統(tǒng)的時效性和效率性都不高。通過引入網(wǎng)絡(luò)拓撲模型作為告警關(guān)聯(lián)規(guī) 則挖掘的約束條件，可以使挖掘過程更有效率、挖掘結(jié)果更加準確。首先，在預(yù) 處理階段通過網(wǎng)絡(luò)拓撲關(guān)系過濾掉不相關(guān)的告警數(shù)據(jù)；其次，在關(guān)聯(lián)規(guī)則挖掘中， 通過拓撲模型可以過濾掉不相關(guān)的候選集?？梢哉f，采用基于拓撲約束的關(guān)聯(lián)規(guī) 則挖掘算法，大大提高了挖掘告警關(guān)聯(lián)規(guī)則過程的時效性和結(jié)果的準確性。 1 4 論文期間所作的工作 本文作者對移動通信網(wǎng)絡(luò)的結(jié)構(gòu)和告警數(shù)據(jù)、故障定位系統(tǒng)、告警關(guān)聯(lián)產(chǎn)品 第4 頁 北京郵電大學(xué)碩十研究生畢業(yè)論文第一章緒論 和關(guān)聯(lián)規(guī)則挖掘算法進行了深入的研究，并參加了“基于數(shù)據(jù)挖掘的智能化移動 通信網(wǎng)絡(luò)故障管理關(guān)鍵技術(shù)研究”課題的開發(fā)和研究。具體的工作如下： 1 ) 對選題進行考察，參與“基于數(shù)據(jù)挖掘的智能化移動通信網(wǎng)絡(luò)故障管理 關(guān)鍵技術(shù)研究課題的學(xué)習。通過閱讀大量的相關(guān)文獻，了解移動通信網(wǎng)絡(luò)故障 定位系統(tǒng)的現(xiàn)存解決方案以及所面臨的挑戰(zhàn)，明確研究方向，撰寫論文開題報告。 2 ) 學(xué)習數(shù)據(jù)挖掘領(lǐng)域的知識與技術(shù)，對網(wǎng)絡(luò)告警關(guān)聯(lián)規(guī)則挖掘技術(shù)進行了 深入的學(xué)習和研究，并且對現(xiàn)有的告警關(guān)聯(lián)產(chǎn)品進行了分析和對比。 3 ) 根據(jù)某省級移動公司提供的真實告警數(shù)據(jù)，對移動通信網(wǎng)絡(luò)及其告警特 征進行了分析。 4 ) 參與了b u p t p r i s m i n e r 智能化告警分析原型系統(tǒng)的研發(fā)。參與了對 f p g r o w t h 非時序關(guān)聯(lián)規(guī)則算法的研究和開發(fā)，并配合小組成員把算法集成入 b u p t p r i s m i n e r 系統(tǒng)，完成模塊測試、代碼維護和文檔編寫等工作。 5 ) 對參與項目所作的工作進行完善和總結(jié)，撰寫研究生階段報告。 6 ) 收集整理資料，總結(jié)研究成果，完成研究生學(xué)位論文。 第5 頁 北京郵電人學(xué)碩十研究生畢業(yè)論文第二章網(wǎng)絡(luò)拓撲模型存故障定位系統(tǒng)中的心用 第二章網(wǎng)絡(luò)拓撲模型在故障定位系統(tǒng)中的應(yīng)用 傳統(tǒng)的電信網(wǎng)絡(luò)告警關(guān)聯(lián)挖掘，沒有與特定的網(wǎng)絡(luò)拓撲結(jié)構(gòu)相結(jié)合，這種方 式存在兩大缺陷，首先待挖掘的數(shù)據(jù)量很大，其次挖掘的關(guān)聯(lián)規(guī)則多且冗余。通 過構(gòu)建網(wǎng)絡(luò)拓撲模型，可以對告警數(shù)據(jù)進行挖掘前的過濾或挖掘中的處理，將沒 有存在拓撲連接關(guān)系的網(wǎng)元告警、關(guān)聯(lián)規(guī)則過濾掉，從而提高挖掘的效率和正確 性。 2 1 網(wǎng)絡(luò)拓撲模型概述 隨著人們對通信需求的不斷增加以及電信產(chǎn)業(yè)的高速發(fā)展，電信網(wǎng)絡(luò)規(guī)模日 益龐大，網(wǎng)絡(luò)設(shè)備不斷增加，網(wǎng)絡(luò)結(jié)構(gòu)也越來越復(fù)雜。網(wǎng)絡(luò)結(jié)構(gòu)的復(fù)雜性和異構(gòu) 性，使得人們對網(wǎng)絡(luò)整體架構(gòu)及拓撲關(guān)系的理解難度加大，同時也很難對網(wǎng)絡(luò)結(jié) 構(gòu)進行直觀的展示和進一步的研究。因此為了更好的理解電信網(wǎng)絡(luò)結(jié)構(gòu)、更好的 對利用網(wǎng)絡(luò)拓撲信息來幫助我們進行一些研究，我們需要對網(wǎng)絡(luò)拓撲關(guān)系建立一 個模型，利用網(wǎng)絡(luò)拓撲的約束對數(shù)據(jù)挖掘技術(shù)進行改進。 拓撲模型是對網(wǎng)絡(luò)結(jié)構(gòu)的一個抽象視圖，它隱藏了跟拓撲關(guān)系無關(guān)的其它各 個方面，通過它，我們可以直觀的了解網(wǎng)絡(luò)中各網(wǎng)元的連接關(guān)系，發(fā)現(xiàn)網(wǎng)絡(luò)連接 的特點，對研究網(wǎng)絡(luò)結(jié)構(gòu)和網(wǎng)絡(luò)性能分析等方面有很大的幫助。所以對網(wǎng)絡(luò)的研 究建立在模型的基礎(chǔ)上會比直接面向?qū)嶋H的網(wǎng)絡(luò)要簡便得多。 2 2 移動網(wǎng)絡(luò)及其告警信息特征分析 當前的移動網(wǎng)絡(luò)環(huán)境具有大型、分布、異構(gòu)、動態(tài)、多供應(yīng)商等特征；網(wǎng)絡(luò) 的告警信息則具有數(shù)據(jù)海量但信息不完整、冗余信息多且時序相關(guān)等特點。大規(guī) 模分布式網(wǎng)絡(luò)包含大量的網(wǎng)絡(luò)實體，它們在運行過程中會產(chǎn)生各種各樣的網(wǎng)絡(luò)告 警信息。這些信息潛在地展示了網(wǎng)絡(luò)實體的運行狀態(tài)和行為，例如鏈路斷路、網(wǎng) 絡(luò)擁塞、設(shè)備失效等。 然而，當前移動網(wǎng)絡(luò)的故障管理非常被動，它是在網(wǎng)絡(luò)發(fā)生故障后，網(wǎng)絡(luò)管 理人員根據(jù)故障告警來發(fā)現(xiàn)并排除故障。由于網(wǎng)絡(luò)本身的復(fù)雜性及其在物理和邏 輯上的關(guān)聯(lián)性，單一的故障可能引發(fā)大量的告警，形成所謂的“告警風暴”。眾 多的告警信息既增加了網(wǎng)管系統(tǒng)的開銷，也不利于網(wǎng)管人員根據(jù)告警排查故障。 因此，網(wǎng)絡(luò)故障管理的首要問題是進行告警關(guān)聯(lián)性分析，即對告警進行合并和轉(zhuǎn) 第6 頁 北京郵電大學(xué)碩士研究生畢業(yè)論文第二章網(wǎng)絡(luò)拓撲模型在故障定位系統(tǒng)中的應(yīng)用 化，將多個告警合并成一條具有更多信息量的告警來代替多條告警，以協(xié)助網(wǎng)管 人員分析故障信息、快速故障定位。 根據(jù)對某省級移動公司真實數(shù)據(jù)的統(tǒng)計和分析，移動通信網(wǎng)絡(luò)的告警信息具 有如下特點： 1 ) 網(wǎng)元數(shù)量多。 一個典型的省級移動通信網(wǎng)絡(luò)包含的網(wǎng)元大約為幾千個。 2 ) 告警數(shù)據(jù)數(shù)量大。 一個典型的省級移動通信網(wǎng)絡(luò)每天產(chǎn)生1 3 萬條告警記錄，每月產(chǎn)生4 0 8 0 萬條告警記錄。 3 ) 告警之間存在時間關(guān)聯(lián)。 即a 告警的發(fā)生可能導(dǎo)致b 告警的發(fā)生。 4 ) 告警類型( 告警標題) 數(shù)量大。 一個典型的省級移動通信網(wǎng)絡(luò)所產(chǎn)生的告警標題多達數(shù)百到數(shù)千種。 5 ) 告警標題產(chǎn)生的告警分布存在大頭現(xiàn)象。 極少量告警標題產(chǎn)生了最大量告警。0 6 8 的告警標題產(chǎn)生了4 3 9 的告警 信息。 6 ) 告警標題產(chǎn)生的告警分布存在長尾現(xiàn)象。 大量告警標題產(chǎn)生了少量告警。4 4 3 7 的告警標題每個只產(chǎn)生1 - 9 個告警； 7 5 3 1 的告警標題每個只產(chǎn)生1 9 9 個告警。 7 ) 實際的關(guān)聯(lián)規(guī)則相對大量的告警信息來說是稀疏的。 在一個網(wǎng)絡(luò)中，即使同一故障每月發(fā)生1 0 0 次( 這種情況非常罕見) ，但是 相對于每月4 0 多萬條告警數(shù)據(jù)來說，還是非常小的。 8 ) 不能排除長尾中的告警信息屬于故障的關(guān)鍵告警信息。 根據(jù)課題對該移動公司兩個告警傳播實例的已有分析和研究，移動網(wǎng)絡(luò)的告 警傳播具有如下特點：告警是沿著網(wǎng)絡(luò)拓撲進行傳播的l u j 。同一個故障可能會引 起若干個存在拓撲連接的網(wǎng)元發(fā)出告警，而不管告警是從低層網(wǎng)元向高層網(wǎng)元傳 播，還是從高層網(wǎng)元向低層網(wǎng)元進行傳播，告警始終都是在故障網(wǎng)元所在的網(wǎng)元 簇中傳播，所以只要我們能根據(jù)網(wǎng)絡(luò)拓撲關(guān)系將網(wǎng)元簇找出來，便可以進一步根 據(jù)該網(wǎng)元簇對告警數(shù)據(jù)進行抽取和判斷，從而進行故障定位。 2 3 故障定位系統(tǒng)中引入網(wǎng)絡(luò)拓撲模型的目的 故障定位是網(wǎng)絡(luò)故障管理的核心，其首要問題是進行告警關(guān)聯(lián)性分析，即對 告警進行合并和轉(zhuǎn)化，將多個告警合并成一條具有更多信息量的告警來代替多條 告警，以協(xié)助網(wǎng)管人員分析故障信息、定位根源故障。而進行網(wǎng)絡(luò)拓撲建模則是 第7 頁 北京郵電大學(xué)碩七研究生畢業(yè)論文第二章網(wǎng)絡(luò)拓撲模型在故障定位系統(tǒng)中的戍用 為了通過網(wǎng)絡(luò)拓撲模型進行約束使挖掘過程更有效率、挖掘結(jié)果更加準確。所以 應(yīng)用網(wǎng)絡(luò)拓撲模型，最終是為數(shù)據(jù)挖掘服務(wù)的。 對網(wǎng)絡(luò)拓撲模型的應(yīng)用可以有兩種方式。第一種應(yīng)用方式是在預(yù)處理階段， 通過網(wǎng)絡(luò)拓撲關(guān)系過濾掉不相關(guān)的告警數(shù)據(jù)。即針對原始告警數(shù)據(jù)中的某條待分 析的告警，通過此告警的網(wǎng)元d 在拓撲模型中找到與該網(wǎng)元具有拓撲關(guān)系的所 有網(wǎng)元( 或者大部分網(wǎng)元) ，將這些連接在一起的網(wǎng)元提取出來，存放在某種數(shù) 據(jù)結(jié)構(gòu)中( 以網(wǎng)元i d 的形式存儲) ，形成一個網(wǎng)元簇1 ，然后將預(yù)設(shè)的時間窗口 內(nèi)原始告警數(shù)據(jù)的網(wǎng)元i d 與網(wǎng)元簇進行匹配，將不屬于該網(wǎng)元簇的告警過濾掉， 最后只留下屬于網(wǎng)元簇內(nèi)網(wǎng)元的告警，然后再用數(shù)據(jù)挖掘算法對這些數(shù)據(jù)進行挖 掘。 第二種應(yīng)用是在關(guān)聯(lián)規(guī)則挖掘中，由l 項頻繁項集產(chǎn)生l + 1 項候選項集時， 通過網(wǎng)絡(luò)拓撲模型來過濾掉不相關(guān)的候選項集。例如，從1 項頻繁項集產(chǎn)生2 項 候選項集，對每一項與其他項進行聯(lián)接時，首先還是根據(jù)該項的網(wǎng)元m 從拓撲 模型中找到相互連接的網(wǎng)元，形成網(wǎng)元簇，這與上面第一種應(yīng)用方式的過程一樣。 然后判斷該項與待聯(lián)接的項是否同出現(xiàn)在網(wǎng)元簇中，如果沒有，則這兩項不進行 聯(lián)接，否則就將這兩項聯(lián)接后放入2 項候選頻繁項集中。從l 項頻繁集產(chǎn)生l + 1 項候選頻繁集過程也與此類似。 綜上所述，建立拓撲模型最主要的目的就是要實現(xiàn)針對某個網(wǎng)元，能夠從模 型中查找出與其存在拓撲連接的所有網(wǎng)元( 或者大部分網(wǎng)元) ，并存儲于某種數(shù) 據(jù)結(jié)構(gòu)中，為其他模塊處理做準備。 2 4 基于拓撲約束和數(shù)據(jù)挖掘的故障定位總體方案 在移動網(wǎng)絡(luò)中，網(wǎng)絡(luò)設(shè)備之間存在的互相作用和互相影響是產(chǎn)生告警傳播的 根源，因此，從相互影響的設(shè)備發(fā)出的告警序列中發(fā)現(xiàn)模式更加具有針對性和更 加有意義。如果不引入設(shè)備間的關(guān)系，就無法濾除不相關(guān)設(shè)備的告警對相關(guān)設(shè)備 告警的干擾，容易產(chǎn)生大量無意義的模式。因此，引入網(wǎng)絡(luò)拓撲的約束非常重要， 將網(wǎng)絡(luò)拓撲約束和數(shù)據(jù)挖掘技術(shù)結(jié)合起來，可以借助約束降低噪音和數(shù)據(jù)缺失帶 來的影響，以發(fā)現(xiàn)有價值的規(guī)律。 下圖是課題提出的基于網(wǎng)絡(luò)拓撲約束和數(shù)據(jù)挖掘技術(shù)的故障管理總體解決 方案架構(gòu)圖。 第8 頁 北京郵電大學(xué)碩十研究生畢業(yè)論文第二章嗍絡(luò)拓撲模型在故障定位系統(tǒng)中的心用 圖2 1 故障管理總體解決方案 6 】 上述解決方案應(yīng)用了現(xiàn)有的數(shù)據(jù)挖掘方法，結(jié)合移動網(wǎng)絡(luò)的具體特征，將網(wǎng) 絡(luò)拓撲約束與數(shù)據(jù)挖掘結(jié)合起來，形成了對移動網(wǎng)絡(luò)故障定位的有針對性的方 法。 在上述解決方案中，本文作者主要針對基于網(wǎng)絡(luò)拓撲建模的非時序告警關(guān)聯(lián) 規(guī)則挖掘算法進行了研究和實現(xiàn)。 移動通信網(wǎng)絡(luò)的網(wǎng)元根據(jù)連接類型以及網(wǎng)元的功能大致可以分成如下幾大 子網(wǎng)：話務(wù)網(wǎng)、信令網(wǎng)、智能網(wǎng)、g p r s 數(shù)據(jù)網(wǎng)和網(wǎng)管網(wǎng)。通過移動通信網(wǎng)絡(luò)結(jié) 構(gòu)分析，我們對網(wǎng)絡(luò)進行抽象，將話務(wù)網(wǎng)、信令網(wǎng)、智能網(wǎng)、g p r s 數(shù)據(jù)網(wǎng)和網(wǎng) 管網(wǎng)等各個子網(wǎng)實際的網(wǎng)絡(luò)結(jié)構(gòu)抽象為一般的拓撲模型圖，分別建立各自的網(wǎng)絡(luò) 拓撲模型，這樣可以更加明晰、直觀的表示網(wǎng)絡(luò)各個子網(wǎng)的整體結(jié)構(gòu)以及子網(wǎng)之 間的關(guān)系。最后將各子網(wǎng)絡(luò)模型根據(jù)連接關(guān)系進行組合，從而形成一個總體的移 動網(wǎng)絡(luò)拓撲模型。 在告警數(shù)據(jù)挖掘方面，首先要進行歷史告警數(shù)據(jù)的離線挖掘。在完成告警離 線預(yù)處理后，對歷史告警數(shù)據(jù)庫進行關(guān)聯(lián)規(guī)則挖掘和序列模式挖掘，之后將挖掘 出的規(guī)則保存在告警規(guī)則和序列庫中，供在線分析使用。 在挖掘算法的選擇上，應(yīng)重點考慮下面三個因素： ( 1 ) 不采用多次掃描數(shù)據(jù)庫的算法。 ( 2 ) 將網(wǎng)元之間的連接關(guān)系作為一種約束條件在挖掘的過程中將一些關(guān)聯(lián) 規(guī)則濾除掉。 第9 頁 圓 圈豳 北京郵電大學(xué)碩十研究生畢業(yè)論文第二章網(wǎng)絡(luò)拓撲模型存故障定位系統(tǒng)中的應(yīng)用 ( 3 ) 網(wǎng)絡(luò)層次應(yīng)當做為考慮的因素，它可以將關(guān)聯(lián)規(guī)則更好地加以限制， 以提高挖掘結(jié)果的正確性。 在告警關(guān)聯(lián)規(guī)則挖掘方面，本文作者對f p g r o w t h 算法進行了研究和實現(xiàn)。 f p g r o w t h 算法對數(shù)據(jù)庫只進行兩次掃描，尤其適合我們將要面對的大型數(shù)據(jù)庫， 可以節(jié)省大量的執(zhí)行時間，提高了執(zhí)行效率。 2 5 基于網(wǎng)絡(luò)拓撲模型的故障定位技術(shù)的特點 通過引入網(wǎng)絡(luò)拓撲模型的約束，將網(wǎng)絡(luò)拓撲模型與數(shù)據(jù)挖掘技術(shù)相接合，克 服了傳統(tǒng)電信網(wǎng)絡(luò)告警關(guān)聯(lián)挖掘中待挖掘的數(shù)據(jù)量大、挖掘的關(guān)聯(lián)規(guī)則多且冗余 的缺點。基于網(wǎng)絡(luò)拓撲模型的故障定位技術(shù)具有如下特點： 首先，提高了數(shù)據(jù)挖掘的效率。現(xiàn)有的挖掘算法通常以告警標題或者類型作 為候選n 項集進行挖掘，因為告警標題可能超過千種，從而隨著項集空間的增 大，計算量顯著增大，導(dǎo)致挖掘算法計算量大、耗時長、效率低。而通過建立網(wǎng) 絡(luò)拓撲模型，以網(wǎng)元關(guān)聯(lián)作為約束來篩選候選n 項集，大大減少了候選集的數(shù) 量，從而可以減少計算量，提高挖掘算法的效率。 其次，提高了數(shù)據(jù)挖掘的精度。傳統(tǒng)的挖掘算法都沒有考慮網(wǎng)絡(luò)的拓撲約束， 所挖掘出來的告警關(guān)聯(lián)規(guī)則與網(wǎng)絡(luò)結(jié)構(gòu)沒有任何關(guān)聯(lián)，從而大大降低了挖掘結(jié)果 的準確程度。而以網(wǎng)元關(guān)聯(lián)作為約束來篩選候選集，建立了告警關(guān)聯(lián)與網(wǎng)絡(luò)拓撲 之間的關(guān)聯(lián)，過濾了不相關(guān)告警對挖掘結(jié)果的影響，從而可以在關(guān)聯(lián)規(guī)則稀疏的 情形下提高挖掘結(jié)果的準確度。 第1 0 頁 北京郵電大學(xué)碩十研究生畢業(yè)論文 第三章面向故障定位的移動通信網(wǎng)絡(luò)拓撲建模 第三章面向故障定位的移動通信網(wǎng)絡(luò)拓撲建模 拓撲模型是對網(wǎng)絡(luò)結(jié)構(gòu)的一個抽象視圖，它隱藏了跟網(wǎng)絡(luò)拓撲關(guān)系無關(guān)的其 他各個方面。通過它，我們可以直觀的了解網(wǎng)絡(luò)中各網(wǎng)元的連接關(guān)系，發(fā)現(xiàn)網(wǎng)絡(luò) 連接的特點。因此將拓撲模型引入網(wǎng)絡(luò)管理故障定位系統(tǒng)，通過拓撲模型濾除掉 不相關(guān)網(wǎng)元設(shè)備的告警對相關(guān)網(wǎng)元告警的干擾，可以提高故障定位數(shù)據(jù)挖掘的時 效性和準確性。 本章在對某省級移動公司通信網(wǎng)絡(luò)特征進行研究和分析的基礎(chǔ)上，提出了網(wǎng) 絡(luò)的抽象拓撲模型。盡觀我們的研究是以某省級移動公司通信網(wǎng)絡(luò)為范本和原型 的，但是由于網(wǎng)絡(luò)具有共性，從該省級移動公司通信網(wǎng)絡(luò)抽象出來的主要特征同 樣適用于其他移動通信網(wǎng)絡(luò)。而拓撲建模方案也同樣可以根據(jù)具體網(wǎng)絡(luò)進行適當 修正后應(yīng)用于其他移動通信網(wǎng)絡(luò)。 3 1 移動通信網(wǎng)絡(luò)結(jié)構(gòu)概述 為支持對某省級移動網(wǎng)絡(luò)告警數(shù)據(jù)進行數(shù)據(jù)挖掘，課題對該省級移動的通信 網(wǎng)絡(luò)結(jié)構(gòu)進行了研究和建模。移動通信網(wǎng)絡(luò)網(wǎng)元的連接類型可根據(jù)傳遞信息的不 同分為三大類：話務(wù)中繼、信令鏈路和分組數(shù)據(jù)線路。其中話務(wù)中繼傳遞的是傳 統(tǒng)話音業(yè)務(wù)；信令鏈路傳遞的是網(wǎng)元間的信令消息：分組數(shù)據(jù)鏈路傳遞的主要是 g p r s 數(shù)據(jù)等。 該省級移動公司通信網(wǎng)絡(luò)的網(wǎng)元根據(jù)這幾種連接類型以及網(wǎng)元的功能大致 可以分為如下五大子網(wǎng)：話務(wù)網(wǎng)、信令網(wǎng)、智能網(wǎng)、g p r s 數(shù)據(jù)網(wǎng)和網(wǎng)管網(wǎng)。在 每個子網(wǎng)中，我們又可以分析其存在的層次關(guān)系。網(wǎng)絡(luò)的層次關(guān)系有助于網(wǎng)絡(luò)通 信的路由查找，而在網(wǎng)絡(luò)故障管理方面，網(wǎng)絡(luò)的層次關(guān)系同樣可以用來進行故障 告警傳播的分析。 通過對移動通信網(wǎng)絡(luò)結(jié)構(gòu)的分析，我們對網(wǎng)絡(luò)進行抽象，將話務(wù)網(wǎng)、信令網(wǎng)、 智能網(wǎng)、g p r s 數(shù)據(jù)網(wǎng)和網(wǎng)管網(wǎng)等各個子網(wǎng)實際的網(wǎng)絡(luò)結(jié)構(gòu)抽象為一般的拓撲模 型圖，分別建立各自的網(wǎng)絡(luò)拓撲模型，這樣可以更加明晰、直觀的表示網(wǎng)絡(luò)各個 子網(wǎng)的整體結(jié)構(gòu)以及子網(wǎng)之間的關(guān)系。最后將各子網(wǎng)絡(luò)模型根據(jù)連接關(guān)系進行組 合，從而形成一個總體的移動網(wǎng)絡(luò)拓撲模型。 第l l 頁 北京郵電大學(xué)碩十研究生畢業(yè)論文第三章面向故障定位的移動通信網(wǎng)絡(luò)拓撲建模 3 2 移動通信網(wǎng)絡(luò)拓撲模型 本節(jié)我們將對各個子網(wǎng)的網(wǎng)元及其連接關(guān)系進行抽象( 比如抽象為網(wǎng)元類 型) ，然后將各個子網(wǎng)通過結(jié)構(gòu)圖表示出來；同時將各個子網(wǎng)之間的關(guān)系進行抽 象，從而得到整個移動通信網(wǎng)絡(luò)的抽象拓撲模型。這樣就可以更加明晰、直觀的 表示出各個子網(wǎng)的整體結(jié)構(gòu)以及子網(wǎng)之間的關(guān)系。 3 2 1 話務(wù)網(wǎng)模型 話務(wù)網(wǎng)是提供傳統(tǒng)話音業(yè)務(wù)的網(wǎng)絡(luò)，是電信網(wǎng)絡(luò)中最主要、網(wǎng)元最多的部分， 其網(wǎng)元之間主要是話務(wù)中繼的連接，同時也有信令鏈路的連接。它主要的網(wǎng)元有 基站( b t s ) 、基站控制器( b s c ) 、變碼器( x c d r ) 、移動交換中心( m s c 、 g m s c 、t m s c ) 等。 話務(wù)網(wǎng)模型圖如圖3 所示，話務(wù)網(wǎng)根據(jù)網(wǎng)元的功能又可分為無線網(wǎng)和交換 網(wǎng)兩部分。無線網(wǎng)即圖中所示的b s s ，主要是為移動臺( 如手機) 與交換機之間 提供鏈路，其結(jié)構(gòu)分層比較明顯，從模型圖中也可以看出，每一個m s c 交換機 連接若干個r x c d r ，而一個或兩個r x c d r 則連接一個b s c ，個b s c 下則 連接若干個b t s 。交換網(wǎng)則主要由交換機與用戶數(shù)據(jù)庫構(gòu)成，進行網(wǎng)絡(luò)通信的交 換和管理，交換網(wǎng)網(wǎng)元的連接則比較復(fù)雜，基本上各個交換機都互相連接，如每 個m s c 都與所有的g m s c 、t m s c 連接，g m s c 、t m s c 之間也有連接。同時 如上節(jié)提到的，m s c 、g m s c 、t m s c 也都與信令轉(zhuǎn)接點有信令鏈路的連接。 第1 2 頁 北京郵電大學(xué)碩士研究生畢業(yè)論文第三章面向故障定位的移動通信網(wǎng)絡(luò)拓撲建模 3 2 2 信令網(wǎng)模型 圖3 - 1 話務(wù)網(wǎng)模型圖”。 7 1 信令網(wǎng)屬于支撐網(wǎng)，它主要進行電信業(yè)務(wù)的接續(xù)、控制，是通信網(wǎng)絡(luò)的神經(jīng) 系統(tǒng)，在該省級移動通信網(wǎng)絡(luò)中它主要的網(wǎng)元有高級信令轉(zhuǎn)節(jié)點( h s l l p ) 、低級 信令轉(zhuǎn)接點( l s 耶) 、歸屬位置寄存器( h l r ，存儲本地用戶信息的數(shù)據(jù)庫，包 括用戶號碼、預(yù)訂業(yè)務(wù)類型、鑒權(quán)信息和當前所在地等信息) 、交換機( m s c 、 g m s c 、t m s c ) 以及其它與信令轉(zhuǎn)接點有信令鏈路連接的網(wǎng)元。 信令網(wǎng)可抽象為圖3 3 。我國7 號信令網(wǎng)為三層結(jié)構(gòu)，即高級信令轉(zhuǎn)接點 h s t p 、低級信令轉(zhuǎn)接點l s t p 、信令點s p 這三層。該省級移動公司的h s t p 及 l s t p 是全互聯(lián)的，而兩臺h s t p 則互為備份，并與其它省份的高級信令轉(zhuǎn)接點 連接。第三層的信令點在實際中包含網(wǎng)絡(luò)中的大部分網(wǎng)元，如圖3 5 中，包含了 話務(wù)網(wǎng)的交換機、g p r s 網(wǎng)的支持節(jié)點、智能網(wǎng)的控制點等等。 3 2 3 網(wǎng)管網(wǎng)模型 圖3 2 信令網(wǎng)模型圖【7 】 網(wǎng)管網(wǎng)是對電信網(wǎng)絡(luò)中所有網(wǎng)元進行監(jiān)控管理的支撐網(wǎng)，主要由操作維護中 心( o m c ) 服務(wù)器通過該網(wǎng)連接到各個網(wǎng)元，從上面獲取配置信息、性能信息 和告警信息等，同時也能通過指令對網(wǎng)元進行遠程操作。 網(wǎng)管網(wǎng)模型圖如圖3 所示，網(wǎng)管網(wǎng)主要由o m c 服務(wù)器及其管理的網(wǎng)元構(gòu) 成，通過x 2 5 等分組網(wǎng)連接，不參與通信業(yè)務(wù)。o m c 根據(jù)管理的網(wǎng)元所屬子網(wǎng) 的不同可分為不同的類型，圖中o m c s 管理交換網(wǎng)的交換機，o m c r 管理無 線網(wǎng)網(wǎng)元，o m c _ t 管理g p r s 網(wǎng)元，o m c i n 管理智能網(wǎng)網(wǎng)元，o m c s 什管 理信令轉(zhuǎn)接點等網(wǎng)元。而同一類型的o m c 由于所管理的網(wǎng)元的廠家不同也有不 第1 3 頁 北京郵電人學(xué)碩1 ：研究生畢業(yè)論文第三章面向故障定位的移動通信網(wǎng)絡(luò)拓撲建模 同的設(shè)備和名稱。各個o m c 服務(wù)器之間都不互連，各管各的網(wǎng)元，但是運營商 可能根據(jù)實際情況建立一個綜合網(wǎng)管系統(tǒng)，將各個o m c 服務(wù)器的管理信息統(tǒng)一 收集起來，進行集中管理、集中監(jiān)控，如圖中虛線所示。但由于該綜合網(wǎng)管系統(tǒng) 是面向前臺維護人員的系統(tǒng)，且在告警數(shù)據(jù)中也沒有該系統(tǒng)的告警，所以我們不 把它列入網(wǎng)絡(luò)拓撲模型中。 3 2 4 智能網(wǎng)模型 圖3 - 3 網(wǎng)管網(wǎng)模型圖 7 1 智能網(wǎng)是在原有通信網(wǎng)的基礎(chǔ)上設(shè)置一層疊加網(wǎng)絡(luò)，用它快速方便、經(jīng)濟靈 活的生成和實現(xiàn)各種新業(yè)務(wù)的體系結(jié)構(gòu)。它包括的網(wǎng)元有業(yè)務(wù)控制點( s c p ) 、 業(yè)務(wù)交換點( s s p ) 、業(yè)務(wù)數(shù)據(jù)點( s d p ) 、充值中心( v c ) 、業(yè)務(wù)管理點( s m p ) 和智能外設(shè)( i p ) 等。 智能網(wǎng)模型圖如圖3 所示。智能網(wǎng)通過s c p 、s s p 與信令轉(zhuǎn)接點連接，接 入7 號信令網(wǎng)，進行信令的交互；通過s s p 與交換機連接，接入話務(wù)網(wǎng)，進行 話務(wù)通信。圖中s t p 和g m s c 用藍色表示，因為這兩者不屬于智能網(wǎng)，但也是 子網(wǎng)間連接的接口。 第1 4 頁 北京郵電大學(xué)碩上研究生畢業(yè)論文第三章面向故障定位的移動通信網(wǎng)絡(luò)拓撲建模 3 2 5g p r s 網(wǎng)模型 圖3 4 智能網(wǎng)模型圖【7 】 g p r s 數(shù)據(jù)網(wǎng)是實現(xiàn)g p r s 業(yè)務(wù)的網(wǎng)絡(luò)，網(wǎng)元包括分組控制單元( p c u ，它 與b s c 集成于同一設(shè)備當中) 、g p r s 服務(wù)支持節(jié)點( s g s n ) 、g p r s 網(wǎng)關(guān)支持 節(jié)點( g g s n ) 、邊界網(wǎng)關(guān)( b g ) 、計費網(wǎng)關(guān)( c g ) 、域名服務(wù)器( d n s ) 和防火 墻( f i r c w a l l ) 等。 g p r s 網(wǎng)模型圖如圖3 一所示。p c u 、s g s n 、g g s n 具有一定的層次結(jié)構(gòu)， p c u 一般與b s c 位于同一網(wǎng)元實體中；s g s n 通過幀中繼與p c u 連接，通過分 組網(wǎng)與g g s n 連接：c g 、b g 、d n s 等設(shè)備也是通過分組網(wǎng)接入到g p r s 網(wǎng)中。 而g p r s 也通過7 號信令網(wǎng)同其它子網(wǎng)的網(wǎng)元連接，如圖中藍色部分所示。 圖3 5g p r s 網(wǎng)模型圖【7 】 第1 5 頁 北京郵電大學(xué)碩l 研究生畢業(yè)論文第三章面向故障定位的移動通信網(wǎng)絡(luò)拓撲建模 3 2 6 移動通信網(wǎng)絡(luò)模型 上述各小節(jié)對移動通信網(wǎng)絡(luò)各個子網(wǎng)分別進行了抽象并建立起抽象模型。而 各子網(wǎng)之問又通過信令鏈路、話務(wù)中繼和分組數(shù)據(jù)鏈路等多種連接類型相互連接 在一起，組成了移動通信網(wǎng)絡(luò)。其中，信令網(wǎng)通過信令鏈路與其它除網(wǎng)管網(wǎng)之外 的子網(wǎng)進行連接；話務(wù)網(wǎng)與信令網(wǎng)有信令鏈路連接，與智能網(wǎng)有話務(wù)中繼連接， 與g p r s 網(wǎng)有分組數(shù)據(jù)鏈路連接；而網(wǎng)管網(wǎng)則通過自身的分組數(shù)據(jù)網(wǎng)將各個網(wǎng)元 連接到相應(yīng)的o m c 服務(wù)器。移動通信網(wǎng)絡(luò)模型如圖3 所示，其中不同顏色代表 了不同的子網(wǎng)，藍色部分表示信令網(wǎng)，綠色部分表示g p r s 網(wǎng)，紅色部分表示話 務(wù)網(wǎng)，橙色部分表示智能網(wǎng)，粉色部分表示網(wǎng)管網(wǎng)。 圖3 6 移動通信網(wǎng)模型圖【7 3 3 移動通信網(wǎng)絡(luò)網(wǎng)元拓撲查找算法研究 本節(jié)依據(jù)課題所提出的網(wǎng)元簇劃分方案，對網(wǎng)元拓撲查找算法進行了研究和 描述。課題將移動通信網(wǎng)絡(luò)網(wǎng)元劃分為三類網(wǎng)元簇，它們分別是：公共連接網(wǎng)元 簇、話務(wù)網(wǎng)網(wǎng)元簇和特殊網(wǎng)元簇，并生成三個網(wǎng)元拓撲文件：公共連接網(wǎng)元文件、 話務(wù)網(wǎng)網(wǎng)元簇拓撲文件和特殊網(wǎng)元簇拓撲文件。 3 3 1 算法概述 基于上述已有的劃分，網(wǎng)元拓撲查找算法對輸入的任意一個網(wǎng)元序列，可以 北京郵電大學(xué)碩士研究生畢業(yè)論文第三章面向故障定位的移動通信剛絡(luò)拓撲建模 從網(wǎng)絡(luò)拓撲數(shù)據(jù)庫中查詢輸入的網(wǎng)元序列是否被一個網(wǎng)元簇包含。如果是則返回 t r u e ，表明這個網(wǎng)元序列中的網(wǎng)元存在拓撲關(guān)系，即它們之間存在告警傳播路徑； 如果不是則返回f a l s e ，即輸入的網(wǎng)元序列不被任何一個網(wǎng)元簇包含，這表明這 個網(wǎng)元序列中的網(wǎng)元之間不存在拓撲關(guān)系，即它們之間不存在告警傳播路徑。 關(guān)聯(lián)規(guī)則挖掘算法根據(jù)返回的t r e e 或f a l s e 對頻繁模式進行篩選，從而過濾 掉不存在告警傳播條件的錯誤頻繁模式。由于f p g r o w t h 算法采用樹結(jié)構(gòu)進行挖 掘，在完成樹的生成后就可以一步生成頻繁模式，所以f p g r o w t h 算法在挖出頻 繁模式后將它們依次進行判定是否符合網(wǎng)絡(luò)拓撲約束，然后將不符合的模式從最 終的頻繁模式集中刪除 由于網(wǎng)元簇的劃分可能不能涵蓋所有的告警傳播路徑，或者不能完整的覆蓋 一個告警傳播路徑，因此增加一個可控參數(shù)一匹配模糊度，來降低現(xiàn)有的網(wǎng)元簇 與過濾掉公共連接網(wǎng)元后的網(wǎng)元序列的匹配精度。匹配模糊度的缺省值為1 ，表 明需要1 0 0 精確的匹配，可以適當降低這個參數(shù)值，如降為9 0 ，此時，若過 濾掉公共聯(lián)接網(wǎng)元后的輸入序列與一個網(wǎng)元簇的匹配度達到9 0 ，網(wǎng)元拓撲查 詢就返回t r u e 。 3 3 2 輸入?yún)?shù)說明 名稱：輸入網(wǎng)元序列 類型：整數(shù)數(shù)組 含義：網(wǎng)元標號序列，在實際算法運行中，該序列數(shù)為頻繁模式中包含的網(wǎng) 元標號序列。 3 3 3 可控參數(shù)說明 名稱：匹配模糊度 類型：雙精度 含義：表征匹配輸入網(wǎng)元序列可接受的模糊度，缺省值為1 。如設(shè)為9 0 則 表明，當存在一個網(wǎng)元簇與過濾掉公共連接網(wǎng)元后的輸入網(wǎng)元序列的匹配度大于 或者等于9 0 時，認為該序列存在拓撲關(guān)系，網(wǎng)絡(luò)拓撲算法返回t r u e 。 3 3 4 輸出參數(shù)說明 類型：布爾類型 含義：表征過濾掉公共連接網(wǎng)元后的輸入網(wǎng)元序列是否被一個定義的網(wǎng)元簇 第1 7 頁 北京郵電人學(xué)碩j ：研究生畢業(yè)論文第三章面向故障定位的移動通信網(wǎng)絡(luò)拓撲建模 所包含，如果是返回t r u e ，否則返回f a l s c 。 3 3 5 算法流程圖 圖3 - 7 網(wǎng)絡(luò)拓撲查找算法流程圖 第1 8 頁 北京郵電人學(xué)碩士研究生畢業(yè)論文第三章面向故障定位的移動通信網(wǎng)絡(luò)拓撲建模 第1 9 頁 北京郵電人學(xué)碩上研究生畢業(yè)論文第三章面向故障定位的移動通信網(wǎng)絡(luò)拓撲建模 3 3 6 算法邏輯說明 從算法流程圖上可以看出，網(wǎng)元拓撲查找算法主要分為三個過程，過濾公共 連接網(wǎng)元，判斷過濾后的序列是否被特殊網(wǎng)元簇包含，如果不被包含，判斷過濾 后的序列是否被話務(wù)網(wǎng)網(wǎng)元簇包含。 過濾公共連接網(wǎng)元 遍歷輸入網(wǎng)元序列的每一個元素，遍歷公共連接網(wǎng)元中的每一個網(wǎng)元，判斷 網(wǎng)元序列的當前元素是否包含于公共連接網(wǎng)元集合中，如果是，刪除該元素，判 斷下一個元素。由于公共連接網(wǎng)元文件的特征是文件每一行僅有一個整數(shù)，文件 每一行內(nèi)容具有唯一性，文件行數(shù)相對比較少，有4 2 行，而唯一性以及個數(shù)的 確定性正是s t l 中s e t 數(shù)據(jù)結(jié)構(gòu)的最大特征，所以使用t 數(shù)據(jù)結(jié)構(gòu)來保存每一 行的數(shù)據(jù)。而使用s e t 數(shù)據(jù)結(jié)構(gòu)可使查詢的時間復(fù)雜度降低。 判斷過濾后的序列是否被特殊網(wǎng)元簇包含 掃描特殊網(wǎng)元簇拓撲數(shù)組的每一個整數(shù)型集合，根據(jù)匹配模糊度以及過濾后 的序列的網(wǎng)元個數(shù)，計算出判定輸入網(wǎng)元序列具有拓撲關(guān)系時該輸入序列被一個 網(wǎng)元簇包含的網(wǎng)元數(shù)目的最小值。遍歷過濾后的序列的每一個網(wǎng)元標號，通過查 找當前網(wǎng)元簇整數(shù)型集合判斷其是否包括當前的網(wǎng)元標號，如果一個網(wǎng)元簇包含 的過濾后的序列中網(wǎng)元標號的個數(shù)大于或者等于由匹配模糊度和網(wǎng)元序列個數(shù) 決定的匹配最小值時，網(wǎng)絡(luò)拓撲查詢算法返回t r u e ，否則執(zhí)行判斷過濾后的序列 是否被話務(wù)網(wǎng)網(wǎng)元簇包含。 判斷過濾后的序列是否被話務(wù)網(wǎng)網(wǎng)元