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

北京郵電大學(xué)碩士研究生畢業(yè)論文摘要 基于拓?fù)浼s束和數(shù)據(jù)挖掘的網(wǎng)絡(luò)故障定位 摘要 本文結(jié)合與企業(yè)合作的課題：基于數(shù)據(jù)挖掘的智能化移動(dòng)通信 網(wǎng)絡(luò)故障管理關(guān)鍵技術(shù)研究，對(duì)基于拓?fù)浼s束的關(guān)聯(lián)規(guī)則挖掘技術(shù) 在移動(dòng)通信網(wǎng)絡(luò)故障定位系統(tǒng)中的應(yīng)用及其實(shí)現(xiàn)方案進(jìn)行了研究。 該課題通過(guò)研究移動(dòng)通信網(wǎng)絡(luò)及其告警信息的特征，得出告警是 沿著網(wǎng)絡(luò)拓?fù)溥M(jìn)行傳播的這一結(jié)論?；诖?，本文提出了在關(guān)聯(lián)規(guī)則 挖掘算法中引入網(wǎng)絡(luò)拓?fù)淠Ｐ妥鳛榧s束，對(duì)告警數(shù)據(jù)進(jìn)行挖掘中的處 理，將沒(méi)有存在拓?fù)溥B接關(guān)系的關(guān)聯(lián)規(guī)則過(guò)濾掉，從而提高挖掘的效 率和正確性。 本文主要針對(duì)關(guān)聯(lián)規(guī)則經(jīng)典挖掘算法存在的各種不足，提出采用 f p g r o w t h 非時(shí)序關(guān)聯(lián)規(guī)則挖掘算法，并在該算法的實(shí)現(xiàn)過(guò)程中加入 了網(wǎng)絡(luò)拓?fù)潢P(guān)系。該算法僅掃描數(shù)據(jù)庫(kù)兩次，不產(chǎn)生候選集，具有明 顯的性能優(yōu)勢(shì)，尤其適合我們將要面對(duì)的大型數(shù)據(jù)庫(kù)，可以節(jié)省大量 時(shí)間，提高執(zhí)行效率。 作者參與了b u p t p r i s m i n e r 智能化告警分析原型系統(tǒng)的研發(fā)， 對(duì)f p g r o w t h 非時(shí)序關(guān)聯(lián)規(guī)則算法進(jìn)行了研究和實(shí)現(xiàn)，并配合小組成 員把算法集成入b u p t p r i s m i n e r 系統(tǒng)，完成了模塊測(cè)試、代碼維護(hù) 和文檔編寫等工作。 關(guān)鍵詞：故障定位拓?fù)淠Ｐ蛿?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 獨(dú)創(chuàng)性( 或創(chuàng)新性) 聲明 本人聲明所呈交的論文是本人在導(dǎo)師指導(dǎo)下進(jìn)行的研究工作及取得的研究 成果。盡我所知，除了文中特別加以標(biāo)注和致謝中所羅列的內(nèi)容以外，論文中不 包含其他人已經(jīng)發(fā)表或撰寫過(guò)的研究成果，也不包含為獲得北京郵電大學(xué)或其他 教育機(jī)構(gòu)的學(xué)位或證書而使用過(guò)的材料。與我一同工作的同志對(duì)本研究所做的任 何貢獻(xiàn)均已在論文中作了明確的說(shuō)明并表示了謝意。 申請(qǐng)學(xué)位論文與資料若有不實(shí)之處，本人承擔(dān)一切相關(guān)責(zé)任。 本人簽名：困叢日期：絲墨：查：蘭z 關(guān)于論文使用授權(quán)的說(shuō)明 學(xué)位論文作者完全了解北京郵電大學(xué)有關(guān)保留和使用學(xué)位論文的規(guī)定，即： 研究生在校攻讀學(xué)位期間論文工作的知識(shí)產(chǎn)權(quán)單位屬北京郵電大學(xué)。學(xué)校有權(quán)保 留并向國(guó)家有關(guān)部門或機(jī)構(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ù)在國(guó)內(nèi)外的發(fā)展現(xiàn) 狀以及作者在論文期間所作的工作。 1 1 課題背景 本課題依托于北京郵電大學(xué)和i b m 中國(guó)研究院聯(lián)合研究的開放課題“基于 數(shù)據(jù)挖掘的智能化移動(dòng)通信網(wǎng)絡(luò)故障管理關(guān)鍵技術(shù)研究一。該課題的主要研究?jī)?nèi) 容是以北京郵電大學(xué)模式識(shí)別實(shí)驗(yàn)室為某省級(jí)移動(dòng)公司開發(fā)的t a c a s 告警關(guān)聯(lián) 與分析系統(tǒng)為基礎(chǔ)，采用創(chuàng)新的方法和技術(shù)，進(jìn)一步提高告警分析的速度、精度， 減少對(duì)人工專家知識(shí)的依賴，最終提高故障定位的準(zhǔn)確性和效率，以研制出一個(gè) 適用于大規(guī)模電信網(wǎng)絡(luò)和海量數(shù)據(jù)應(yīng)用環(huán)境下的智能化實(shí)時(shí)故障診斷、影響分析 和故障定位系統(tǒng)。 故障定位是網(wǎng)絡(luò)故障管理的核心。隨著現(xiàn)代通信系統(tǒng)的產(chǎn)生與發(fā)展，故障定 位問(wèn)題備受關(guān)注，并且提出了許多故障定位方案。但是通信系統(tǒng)逐漸地日趨復(fù)雜 并且提供一些新的性能，因此故障定位方案也需要進(jìn)一步的改進(jìn)。在故障定位技 術(shù)中常用的是告警關(guān)聯(lián)，即對(duì)相同故障源的告警進(jìn)行分組的處理過(guò)程。 傳統(tǒng)的電信網(wǎng)絡(luò)告警關(guān)聯(lián)挖掘，沒(méi)有與特定的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)相結(jié)合，這種方 式存在兩大缺陷，首先待挖掘的數(shù)據(jù)量很大，其次挖掘的關(guān)聯(lián)規(guī)則多且冗余。為 了克服這兩大缺陷，提出了構(gòu)建網(wǎng)絡(luò)物理拓?fù)淠Ｐ?，通過(guò)網(wǎng)絡(luò)拓?fù)淠Ｐ蛯?duì)告警數(shù) 據(jù)進(jìn)行挖掘中的處理，將沒(méi)有存在拓?fù)溥B接關(guān)系的關(guān)聯(lián)規(guī)則過(guò)濾掉，從而提高挖 掘的效率和正確性。通過(guò)對(duì)某省級(jí)移動(dòng)通信的網(wǎng)絡(luò)結(jié)構(gòu)和實(shí)際告警數(shù)據(jù)進(jìn)行分析 后，提出采用數(shù)據(jù)庫(kù)表來(lái)建立和存儲(chǔ)網(wǎng)元拓?fù)潢P(guān)系信息，從而實(shí)現(xiàn)網(wǎng)絡(luò)物理拓?fù)?的建模。 基于拓?fù)浼s束的關(guān)聯(lián)規(guī)則挖掘算法，依照建立的拓?fù)浣Y(jié)構(gòu)模型得到的網(wǎng)元之 間的層次關(guān)系，將發(fā)生各個(gè)告警的各個(gè)設(shè)備進(jìn)行層次編碼。由拓?fù)浣Y(jié)構(gòu)體現(xiàn)出的 各網(wǎng)元之間的連接關(guān)系，結(jié)合故障的傳播路徑，得到關(guān)聯(lián)規(guī)則挖掘過(guò)程的約束條 件。在挖掘關(guān)聯(lián)規(guī)則過(guò)程中，兩個(gè)或多個(gè)項(xiàng)目是否可能連接為一個(gè)項(xiàng)集要由這種 約束條件加以限制。采用基于拓?fù)浼s束的關(guān)聯(lián)規(guī)則挖掘算法，實(shí)現(xiàn)了在連接前更 大程度地減少待檢測(cè)的組合個(gè)數(shù)，明顯降低了工作量，同時(shí)保證得到的規(guī)則滿足 拓?fù)潢P(guān)系，提高了挖掘告警關(guān)聯(lián)規(guī)則過(guò)程的時(shí)效性和結(jié)果的準(zhǔn)確性。 第l 頁(yè) 北京郵電大學(xué)碩十研究生畢業(yè)論文第一章緒論 采用基于網(wǎng)絡(luò)拓?fù)浼s束的關(guān)聯(lián)規(guī)則數(shù)據(jù)挖掘技術(shù)來(lái)改進(jìn)移動(dòng)通信網(wǎng)絡(luò)故障 定位系統(tǒng)，就是在這樣的背景下提出的。 1 2 故障定位系統(tǒng)綜述 1 2 1 故障定位的概念 網(wǎng)絡(luò)管理卜1 是指對(duì)網(wǎng)絡(luò)的運(yùn)行狀態(tài)進(jìn)行檢測(cè)和控制，使其能夠有效、可靠、 安全、經(jīng)濟(jì)地提供服務(wù)。國(guó)際標(biāo)準(zhǔn)化組織( i s o ) 將網(wǎng)絡(luò)管理功能劃分為配置管 理、性能管理、故障管理、安全管理和計(jì)費(fèi)管理五個(gè)領(lǐng)域。故障管理的目的是迅 速發(fā)現(xiàn)和糾正網(wǎng)絡(luò)故障，動(dòng)態(tài)維護(hù)網(wǎng)絡(luò)的有效性。故障管理卜1 的主要功能有告警 監(jiān)測(cè)、故障定位、測(cè)試、業(yè)務(wù)恢復(fù)、故障修復(fù)以及故障日志維護(hù)等。故障定位是 網(wǎng)絡(luò)故障管理的核心。在通信系統(tǒng)中，故障的發(fā)生是不可避免的，對(duì)于一個(gè)健全 可靠的系統(tǒng)而言，快速隔離并檢測(cè)出故障是必要的。 故障定位卜1 是通過(guò)一些觀測(cè)的告警信息發(fā)現(xiàn)準(zhǔn)確根源故障的過(guò)程，包括故障 隔離、事件關(guān)聯(lián)以及根故障分析。故障p 1 可以定義為那些引起系統(tǒng)以非正常方式 操作的事件，可分為：1 ) 網(wǎng)絡(luò)配置錯(cuò)誤；2 ) 網(wǎng)絡(luò)硬件問(wèn)題，包括網(wǎng)卡故障、 m o d e m 故障、通訊媒體故障、路由器轉(zhuǎn)換故障等；3 ) 網(wǎng)絡(luò)軟件異常，如路由軟 件故障、路由表刷新異常、網(wǎng)絡(luò)激活應(yīng)用軟件異常等；4 ) 網(wǎng)絡(luò)流量異常，例如 分組風(fēng)暴等。在通信網(wǎng)絡(luò)中，一個(gè)故障可能引起網(wǎng)管中心的多重告警，其產(chǎn)生原 因是：1 ) 故障重復(fù)發(fā)生；2 ) 一個(gè)業(yè)務(wù)可能多次調(diào)用有故障的組建：3 ) 一個(gè)設(shè) 備的一個(gè)故障產(chǎn)生多個(gè)告警；4 ) 多個(gè)設(shè)備同時(shí)檢測(cè)到同一故障并同時(shí)發(fā)出告警； 5 ) 故障傳播到其他網(wǎng)絡(luò)產(chǎn)生額外告警。 網(wǎng)絡(luò)或設(shè)備檢測(cè)到故障，發(fā)出描述故障現(xiàn)象的消息稱為告警，它是從網(wǎng)絡(luò)設(shè) 備角度對(duì)故障的一個(gè)描述。組成網(wǎng)絡(luò)的設(shè)備( 組成設(shè)備的模塊) 是相互影響的， 一個(gè)設(shè)備發(fā)生異常，相關(guān)設(shè)備會(huì)表現(xiàn)出故障征兆，導(dǎo)致每一個(gè)相關(guān)設(shè)備都發(fā)出告 警信息，這種現(xiàn)象稱為故障的傳播特性。由于大部分故障都是不可直接觀測(cè)的， 系統(tǒng)必須通過(guò)已知的告警信息推理出根故障所在。告警可能攜帶的信息有：產(chǎn)生 告警的網(wǎng)元的i d ，故障類型，時(shí)間標(biāo)簽，告警標(biāo)志符，故障嚴(yán)重級(jí)別，故障的 文本描述等r j 。 為了提供快速、可靠、有競(jìng)爭(zhēng)力的服務(wù)，移動(dòng)通信網(wǎng)絡(luò)管理系統(tǒng)要適應(yīng)網(wǎng)絡(luò) 規(guī)模擴(kuò)張、帶寬提高、復(fù)雜性增強(qiáng)的變化。隨著網(wǎng)絡(luò)結(jié)構(gòu)規(guī)模日益復(fù)雜，網(wǎng)絡(luò)故 障管理越來(lái)越困難。網(wǎng)絡(luò)故障不僅會(huì)降低客戶的滿意度，也會(huì)導(dǎo)致經(jīng)濟(jì)損失。故 障的發(fā)生在所難免，快速檢測(cè)和定位故障是保障網(wǎng)絡(luò)穩(wěn)定運(yùn)行的關(guān)鍵因素，也是 網(wǎng)絡(luò)管理的首要任務(wù)。 第2 頁(yè) 北京郵電火學(xué)碩士研究生畢業(yè)論文第一章緒論 1 2 2 現(xiàn)存的故障定位技術(shù) 在故障定位技術(shù)中常用的是告警關(guān)聯(lián)，即對(duì)相同故障源的告警進(jìn)行分組的處 理過(guò)程。傳統(tǒng)上的告警關(guān)聯(lián)性分析主要是通過(guò)人工分析出關(guān)聯(lián)規(guī)則，然后再加入 到系統(tǒng)當(dāng)中。然而，隨著網(wǎng)絡(luò)規(guī)模越來(lái)越大，單純依靠網(wǎng)絡(luò)管理人員獲得告警關(guān) 聯(lián)性知識(shí)已經(jīng)無(wú)法滿足網(wǎng)絡(luò)維護(hù)的需要。網(wǎng)絡(luò)告警數(shù)據(jù)庫(kù)中存儲(chǔ)了大量的歷史告 警信息，其中蘊(yùn)含了許多反映網(wǎng)絡(luò)運(yùn)行規(guī)律的有用信息，利用這些信息可以完善 網(wǎng)絡(luò)故障管理。因此可通過(guò)用知識(shí)發(fā)現(xiàn)的方法分析告警序列，挖掘告警關(guān)聯(lián)規(guī)則。 在移動(dòng)通信網(wǎng)絡(luò)故障管理中，現(xiàn)今的技術(shù)研究引入了數(shù)據(jù)挖掘的概念和方 法。其基本思想是將數(shù)據(jù)挖掘技術(shù)引入到告警關(guān)聯(lián)中，目的是為了揭示出隱含在 海量原始故障征兆信息后面有意義的知識(shí)和規(guī)則，從而以更全面的視角解釋網(wǎng)絡(luò) 故障及性能的問(wèn)題，使網(wǎng)絡(luò)管理員能快速的進(jìn)行故障定位、進(jìn)一步做出故障決策 并完成預(yù)測(cè)。這一方法能夠較好的適應(yīng)網(wǎng)絡(luò)的動(dòng)態(tài)變化，從而找出告警數(shù)據(jù)之間 存在的規(guī)則。 數(shù)據(jù)挖掘在移動(dòng)網(wǎng)絡(luò)領(lǐng)域的典型應(yīng)用有客戶行為分析、客戶流失預(yù)測(cè)、告警 序列分析、網(wǎng)絡(luò)關(guān)鍵性能指標(biāo)預(yù)測(cè)等。從國(guó)內(nèi)來(lái)看，不少企業(yè)也都意識(shí)到將數(shù)據(jù) 挖掘應(yīng)用于告警關(guān)聯(lián)分析的重要性，開展了類似的項(xiàng)目研究。 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 等都不適合處理移動(dòng)網(wǎng)絡(luò)告警這種關(guān)于時(shí)間序列的問(wè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 ) 挖掘耗時(shí)長(zhǎng) 現(xiàn)有挖掘算法通常以告警標(biāo)題( 告警類型) 作為候選n 項(xiàng)集進(jìn)行挖掘，因 為告警標(biāo)題可能超過(guò)千種，從而隨著項(xiàng)集空間的增大，計(jì)算量顯著增大，導(dǎo)致挖 掘算法計(jì)算量大，效率低，耗時(shí)長(zhǎng) 2 ) 挖掘結(jié)果準(zhǔn)確度低 實(shí)際的告警信息存在長(zhǎng)尾現(xiàn)象，大量的設(shè)備和大量的告警標(biāo)題產(chǎn)生的告警信 息非常少，因此實(shí)際告警規(guī)則或者告警序列在全部告警數(shù)據(jù)中可能是稀疏的，這 導(dǎo)致了現(xiàn)有挖掘算法通常挖掘出大量的沒(méi)有實(shí)際價(jià)值的告警規(guī)則或者序列模式。 另外，現(xiàn)有挖掘算法都沒(méi)有考慮網(wǎng)絡(luò)的拓?fù)浼s束，所挖掘出來(lái)的告警規(guī)則或 者序列模式與網(wǎng)絡(luò)結(jié)構(gòu)沒(méi)有任何關(guān)聯(lián)，因此大大降低了挖掘結(jié)果的準(zhǔn)確程度。 第3 頁(yè) 北京郵電大學(xué)碩十研究生畢業(yè)論文第一章緒論 3 ) 采用固定時(shí)間窗口進(jìn)行挖掘，規(guī)則和序列模式不完整 目前有關(guān)告警關(guān)聯(lián)的數(shù)據(jù)挖掘算法都會(huì)設(shè)置一個(gè)固定的時(shí)間窗口，雖然設(shè)置 固定的時(shí)間窗口使得算法比較容易實(shí)現(xiàn)，但是將會(huì)導(dǎo)致其挖掘出來(lái)的告警關(guān)聯(lián)規(guī) 則正確性低。應(yīng)該設(shè)置動(dòng)態(tài)的時(shí)間窗口，根據(jù)不同的告警或不同的網(wǎng)元?jiǎng)討B(tài)地調(diào) 整時(shí)間窗口。 1 3 基于拓?fù)浼s束的關(guān)聯(lián)規(guī)則挖掘技術(shù)在電信網(wǎng)絡(luò)故障定位系統(tǒng)中 的應(yīng)用 數(shù)據(jù)挖掘是從大量的、不完全的、有噪聲的、模糊的、隨機(jī)的數(shù)據(jù)中，提取 隱含在其中的、人們事先不知道的但又是潛在有用的信息和知識(shí)的過(guò)程。i j l 數(shù)據(jù) 挖掘就是知識(shí)發(fā)現(xiàn)技術(shù)在數(shù)據(jù)庫(kù)領(lǐng)域中的應(yīng)用，在一個(gè)已知狀態(tài)的數(shù)據(jù)集上，通 過(guò)設(shè)置一定的學(xué)習(xí)算法，發(fā)掘出數(shù)據(jù)間隱含的一些內(nèi)在規(guī)律，即獲取( 發(fā)現(xiàn)) 所 謂的知識(shí)。 在大的通信網(wǎng)中，一個(gè)故障產(chǎn)生很多告警，當(dāng)若干故障并存時(shí)，產(chǎn)生大量的 告警，這些告警隱藏了故障的原因，以至難以進(jìn)行故障診斷和定位，這是當(dāng)今網(wǎng) 絡(luò)故障管理的一個(gè)難題。網(wǎng)絡(luò)維護(hù)人員感興趣的不是告警事件本身，而是引起告 警的設(shè)備故障。盡管這些告警直接或間接的反映故障現(xiàn)象，但大量的告警事件形 成告警風(fēng)暴，使迅速、準(zhǔn)確定位故障變得很困難。將數(shù)據(jù)挖掘技術(shù)引入到告警關(guān) 聯(lián)中，利用基于規(guī)則的相關(guān)性分析技術(shù)，一方面將多個(gè)告警歸結(jié)成較少的告警， 過(guò)濾大量的冗余告警，另一方面用于實(shí)時(shí)故障診斷和故障定位，可以輔助網(wǎng)絡(luò)管 理人員，過(guò)濾冗余信息，準(zhǔn)確的定位故障，及時(shí)排除故障，保障網(wǎng)絡(luò)可靠的運(yùn)行。 但是，傳統(tǒng)的告警關(guān)聯(lián)規(guī)則挖掘系統(tǒng)大多是直接對(duì)原始告警數(shù)據(jù)進(jìn)行簡(jiǎn)單的 預(yù)處理就用挖掘算法進(jìn)行挖掘，從而得到告警之間的關(guān)聯(lián)關(guān)系。這種方法盡管可 以挖掘出有效的告警關(guān)聯(lián)規(guī)則，但是對(duì)于海量的告警數(shù)據(jù)來(lái)說(shuō)，這樣的告警關(guān)聯(lián) 規(guī)則挖掘系統(tǒng)的時(shí)效性和效率性都不高。通過(guò)引入網(wǎng)絡(luò)拓?fù)淠Ｐ妥鳛楦婢P(guān)聯(lián)規(guī) 則挖掘的約束條件，可以使挖掘過(guò)程更有效率、挖掘結(jié)果更加準(zhǔn)確。首先，在預(yù) 處理階段通過(guò)網(wǎng)絡(luò)拓?fù)潢P(guān)系過(guò)濾掉不相關(guān)的告警數(shù)據(jù)；其次，在關(guān)聯(lián)規(guī)則挖掘中， 通過(guò)拓?fù)淠Ｐ涂梢赃^(guò)濾掉不相關(guān)的候選集?？梢哉f(shuō)，采用基于拓?fù)浼s束的關(guān)聯(lián)規(guī) 則挖掘算法，大大提高了挖掘告警關(guān)聯(lián)規(guī)則過(guò)程的時(shí)效性和結(jié)果的準(zhǔn)確性。 1 4 論文期間所作的工作 本文作者對(duì)移動(dòng)通信網(wǎng)絡(luò)的結(jié)構(gòu)和告警數(shù)據(jù)、故障定位系統(tǒng)、告警關(guān)聯(lián)產(chǎn)品 第4 頁(yè) 北京郵電大學(xué)碩十研究生畢業(yè)論文第一章緒論 和關(guān)聯(lián)規(guī)則挖掘算法進(jìn)行了深入的研究，并參加了“基于數(shù)據(jù)挖掘的智能化移動(dòng) 通信網(wǎng)絡(luò)故障管理關(guān)鍵技術(shù)研究”課題的開發(fā)和研究。具體的工作如下： 1 ) 對(duì)選題進(jìn)行考察，參與“基于數(shù)據(jù)挖掘的智能化移動(dòng)通信網(wǎng)絡(luò)故障管理 關(guān)鍵技術(shù)研究課題的學(xué)習(xí)。通過(guò)閱讀大量的相關(guān)文獻(xiàn)，了解移動(dòng)通信網(wǎng)絡(luò)故障 定位系統(tǒng)的現(xiàn)存解決方案以及所面臨的挑戰(zhàn)，明確研究方向，撰寫論文開題報(bào)告。 2 ) 學(xué)習(xí)數(shù)據(jù)挖掘領(lǐng)域的知識(shí)與技術(shù)，對(duì)網(wǎng)絡(luò)告警關(guān)聯(lián)規(guī)則挖掘技術(shù)進(jìn)行了 深入的學(xué)習(xí)和研究，并且對(duì)現(xiàn)有的告警關(guān)聯(lián)產(chǎn)品進(jìn)行了分析和對(duì)比。 3 ) 根據(jù)某省級(jí)移動(dòng)公司提供的真實(shí)告警數(shù)據(jù)，對(duì)移動(dòng)通信網(wǎng)絡(luò)及其告警特 征進(jìn)行了分析。 4 ) 參與了b u p t p r i s m i n e r 智能化告警分析原型系統(tǒng)的研發(fā)。參與了對(duì) f p g r o w t h 非時(shí)序關(guān)聯(lián)規(guī)則算法的研究和開發(fā)，并配合小組成員把算法集成入 b u p t p r i s m i n e r 系統(tǒng)，完成模塊測(cè)試、代碼維護(hù)和文檔編寫等工作。 5 ) 對(duì)參與項(xiàng)目所作的工作進(jìn)行完善和總結(jié)，撰寫研究生階段報(bào)告。 6 ) 收集整理資料，總結(jié)研究成果，完成研究生學(xué)位論文。 第5 頁(yè) 北京郵電人學(xué)碩十研究生畢業(yè)論文第二章網(wǎng)絡(luò)拓?fù)淠Ｐ痛婀收隙ㄎ幌到y(tǒng)中的心用 第二章網(wǎng)絡(luò)拓?fù)淠Ｐ驮诠收隙ㄎ幌到y(tǒng)中的應(yīng)用 傳統(tǒng)的電信網(wǎng)絡(luò)告警關(guān)聯(lián)挖掘，沒(méi)有與特定的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)相結(jié)合，這種方 式存在兩大缺陷，首先待挖掘的數(shù)據(jù)量很大，其次挖掘的關(guān)聯(lián)規(guī)則多且冗余。通 過(guò)構(gòu)建網(wǎng)絡(luò)拓?fù)淠Ｐ?，可以?duì)告警數(shù)據(jù)進(jìn)行挖掘前的過(guò)濾或挖掘中的處理，將沒(méi) 有存在拓?fù)溥B接關(guān)系的網(wǎng)元告警、關(guān)聯(lián)規(guī)則過(guò)濾掉，從而提高挖掘的效率和正確 性。 2 1 網(wǎng)絡(luò)拓?fù)淠Ｐ透攀?隨著人們對(duì)通信需求的不斷增加以及電信產(chǎn)業(yè)的高速發(fā)展，電信網(wǎng)絡(luò)規(guī)模日 益龐大，網(wǎng)絡(luò)設(shè)備不斷增加，網(wǎng)絡(luò)結(jié)構(gòu)也越來(lái)越復(fù)雜。網(wǎng)絡(luò)結(jié)構(gòu)的復(fù)雜性和異構(gòu) 性，使得人們對(duì)網(wǎng)絡(luò)整體架構(gòu)及拓?fù)潢P(guān)系的理解難度加大，同時(shí)也很難對(duì)網(wǎng)絡(luò)結(jié) 構(gòu)進(jìn)行直觀的展示和進(jìn)一步的研究。因此為了更好的理解電信網(wǎng)絡(luò)結(jié)構(gòu)、更好的 對(duì)利用網(wǎng)絡(luò)拓?fù)湫畔?lái)幫助我們進(jìn)行一些研究，我們需要對(duì)網(wǎng)絡(luò)拓?fù)潢P(guān)系建立一 個(gè)模型，利用網(wǎng)絡(luò)拓?fù)涞募s束對(duì)數(shù)據(jù)挖掘技術(shù)進(jìn)行改進(jìn)。 拓?fù)淠Ｐ褪菍?duì)網(wǎng)絡(luò)結(jié)構(gòu)的一個(gè)抽象視圖，它隱藏了跟拓?fù)潢P(guān)系無(wú)關(guān)的其它各 個(gè)方面，通過(guò)它，我們可以直觀的了解網(wǎng)絡(luò)中各網(wǎng)元的連接關(guān)系，發(fā)現(xiàn)網(wǎng)絡(luò)連接 的特點(diǎn)，對(duì)研究網(wǎng)絡(luò)結(jié)構(gòu)和網(wǎng)絡(luò)性能分析等方面有很大的幫助。所以對(duì)網(wǎng)絡(luò)的研 究建立在模型的基礎(chǔ)上會(huì)比直接面向?qū)嶋H的網(wǎng)絡(luò)要簡(jiǎn)便得多。 2 2 移動(dòng)網(wǎng)絡(luò)及其告警信息特征分析 當(dāng)前的移動(dòng)網(wǎng)絡(luò)環(huán)境具有大型、分布、異構(gòu)、動(dòng)態(tài)、多供應(yīng)商等特征；網(wǎng)絡(luò) 的告警信息則具有數(shù)據(jù)海量但信息不完整、冗余信息多且時(shí)序相關(guān)等特點(diǎn)。大規(guī) 模分布式網(wǎng)絡(luò)包含大量的網(wǎng)絡(luò)實(shí)體，它們?cè)谶\(yùn)行過(guò)程中會(huì)產(chǎn)生各種各樣的網(wǎng)絡(luò)告 警信息。這些信息潛在地展示了網(wǎng)絡(luò)實(shí)體的運(yùn)行狀態(tài)和行為，例如鏈路斷路、網(wǎng) 絡(luò)擁塞、設(shè)備失效等。 然而，當(dāng)前移動(dòng)網(wǎng)絡(luò)的故障管理非常被動(dòng)，它是在網(wǎng)絡(luò)發(fā)生故障后，網(wǎng)絡(luò)管 理人員根據(jù)故障告警來(lái)發(fā)現(xiàn)并排除故障。由于網(wǎng)絡(luò)本身的復(fù)雜性及其在物理和邏 輯上的關(guān)聯(lián)性，單一的故障可能引發(fā)大量的告警，形成所謂的“告警風(fēng)暴”。眾 多的告警信息既增加了網(wǎng)管系統(tǒng)的開銷，也不利于網(wǎng)管人員根據(jù)告警排查故障。 因此，網(wǎng)絡(luò)故障管理的首要問(wèn)題是進(jìn)行告警關(guān)聯(lián)性分析，即對(duì)告警進(jìn)行合并和轉(zhuǎn) 第6 頁(yè) 北京郵電大學(xué)碩士研究生畢業(yè)論文第二章網(wǎng)絡(luò)拓?fù)淠Ｐ驮诠收隙ㄎ幌到y(tǒng)中的應(yīng)用 化，將多個(gè)告警合并成一條具有更多信息量的告警來(lái)代替多條告警，以協(xié)助網(wǎng)管 人員分析故障信息、快速故障定位。 根據(jù)對(duì)某省級(jí)移動(dòng)公司真實(shí)數(shù)據(jù)的統(tǒng)計(jì)和分析，移動(dòng)通信網(wǎng)絡(luò)的告警信息具 有如下特點(diǎn)： 1 ) 網(wǎng)元數(shù)量多。 一個(gè)典型的省級(jí)移動(dòng)通信網(wǎng)絡(luò)包含的網(wǎng)元大約為幾千個(gè)。 2 ) 告警數(shù)據(jù)數(shù)量大。 一個(gè)典型的省級(jí)移動(dòng)通信網(wǎng)絡(luò)每天產(chǎn)生1 3 萬(wàn)條告警記錄，每月產(chǎn)生4 0 8 0 萬(wàn)條告警記錄。 3 ) 告警之間存在時(shí)間關(guān)聯(lián)。 即a 告警的發(fā)生可能導(dǎo)致b 告警的發(fā)生。 4 ) 告警類型( 告警標(biāo)題) 數(shù)量大。 一個(gè)典型的省級(jí)移動(dòng)通信網(wǎng)絡(luò)所產(chǎn)生的告警標(biāo)題多達(dá)數(shù)百到數(shù)千種。 5 ) 告警標(biāo)題產(chǎn)生的告警分布存在大頭現(xiàn)象。 極少量告警標(biāo)題產(chǎn)生了最大量告警。0 6 8 的告警標(biāo)題產(chǎn)生了4 3 9 的告警 信息。 6 ) 告警標(biāo)題產(chǎn)生的告警分布存在長(zhǎng)尾現(xiàn)象。 大量告警標(biāo)題產(chǎn)生了少量告警。4 4 3 7 的告警標(biāo)題每個(gè)只產(chǎn)生1 - 9 個(gè)告警； 7 5 3 1 的告警標(biāo)題每個(gè)只產(chǎn)生1 9 9 個(gè)告警。 7 ) 實(shí)際的關(guān)聯(lián)規(guī)則相對(duì)大量的告警信息來(lái)說(shuō)是稀疏的。 在一個(gè)網(wǎng)絡(luò)中，即使同一故障每月發(fā)生1 0 0 次( 這種情況非常罕見) ，但是 相對(duì)于每月4 0 多萬(wàn)條告警數(shù)據(jù)來(lái)說(shuō)，還是非常小的。 8 ) 不能排除長(zhǎng)尾中的告警信息屬于故障的關(guān)鍵告警信息。 根據(jù)課題對(duì)該移動(dòng)公司兩個(gè)告警傳播實(shí)例的已有分析和研究，移動(dòng)網(wǎng)絡(luò)的告 警傳播具有如下特點(diǎn)：告警是沿著網(wǎng)絡(luò)拓?fù)溥M(jìn)行傳播的l u j 。同一個(gè)故障可能會(huì)引 起若干個(gè)存在拓?fù)溥B接的網(wǎng)元發(fā)出告警，而不管告警是從低層網(wǎng)元向高層網(wǎng)元傳 播，還是從高層網(wǎng)元向低層網(wǎng)元進(jìn)行傳播，告警始終都是在故障網(wǎng)元所在的網(wǎng)元 簇中傳播，所以只要我們能根據(jù)網(wǎng)絡(luò)拓?fù)潢P(guān)系將網(wǎng)元簇找出來(lái)，便可以進(jìn)一步根 據(jù)該網(wǎng)元簇對(duì)告警數(shù)據(jù)進(jìn)行抽取和判斷，從而進(jìn)行故障定位。 2 3 故障定位系統(tǒng)中引入網(wǎng)絡(luò)拓?fù)淠Ｐ偷哪康?故障定位是網(wǎng)絡(luò)故障管理的核心，其首要問(wèn)題是進(jìn)行告警關(guān)聯(lián)性分析，即對(duì) 告警進(jìn)行合并和轉(zhuǎn)化，將多個(gè)告警合并成一條具有更多信息量的告警來(lái)代替多條 告警，以協(xié)助網(wǎng)管人員分析故障信息、定位根源故障。而進(jìn)行網(wǎng)絡(luò)拓?fù)浣t是 第7 頁(yè) 北京郵電大學(xué)碩七研究生畢業(yè)論文第二章網(wǎng)絡(luò)拓?fù)淠Ｐ驮诠收隙ㄎ幌到y(tǒng)中的戍用 為了通過(guò)網(wǎng)絡(luò)拓?fù)淠Ｐ瓦M(jìn)行約束使挖掘過(guò)程更有效率、挖掘結(jié)果更加準(zhǔn)確。所以 應(yīng)用網(wǎng)絡(luò)拓?fù)淠Ｐ?，最終是為數(shù)據(jù)挖掘服務(wù)的。 對(duì)網(wǎng)絡(luò)拓?fù)淠Ｐ偷膽?yīng)用可以有兩種方式。第一種應(yīng)用方式是在預(yù)處理階段， 通過(guò)網(wǎng)絡(luò)拓?fù)潢P(guān)系過(guò)濾掉不相關(guān)的告警數(shù)據(jù)。即針對(duì)原始告警數(shù)據(jù)中的某條待分 析的告警，通過(guò)此告警的網(wǎng)元d 在拓?fù)淠Ｐ椭姓业脚c該網(wǎng)元具有拓?fù)潢P(guān)系的所 有網(wǎng)元( 或者大部分網(wǎng)元) ，將這些連接在一起的網(wǎng)元提取出來(lái)，存放在某種數(shù) 據(jù)結(jié)構(gòu)中( 以網(wǎng)元i d 的形式存儲(chǔ)) ，形成一個(gè)網(wǎng)元簇1 ，然后將預(yù)設(shè)的時(shí)間窗口 內(nèi)原始告警數(shù)據(jù)的網(wǎng)元i d 與網(wǎng)元簇進(jìn)行匹配，將不屬于該網(wǎng)元簇的告警過(guò)濾掉， 最后只留下屬于網(wǎng)元簇內(nèi)網(wǎng)元的告警，然后再用數(shù)據(jù)挖掘算法對(duì)這些數(shù)據(jù)進(jìn)行挖 掘。 第二種應(yīng)用是在關(guān)聯(lián)規(guī)則挖掘中，由l 項(xiàng)頻繁項(xiàng)集產(chǎn)生l + 1 項(xiàng)候選項(xiàng)集時(shí)， 通過(guò)網(wǎng)絡(luò)拓?fù)淠Ｐ蛠?lái)過(guò)濾掉不相關(guān)的候選項(xiàng)集。例如，從1 項(xiàng)頻繁項(xiàng)集產(chǎn)生2 項(xiàng) 候選項(xiàng)集，對(duì)每一項(xiàng)與其他項(xiàng)進(jìn)行聯(lián)接時(shí)，首先還是根據(jù)該項(xiàng)的網(wǎng)元m 從拓?fù)?模型中找到相互連接的網(wǎng)元，形成網(wǎng)元簇，這與上面第一種應(yīng)用方式的過(guò)程一樣。 然后判斷該項(xiàng)與待聯(lián)接的項(xiàng)是否同出現(xiàn)在網(wǎng)元簇中，如果沒(méi)有，則這兩項(xiàng)不進(jìn)行 聯(lián)接，否則就將這兩項(xiàng)聯(lián)接后放入2 項(xiàng)候選頻繁項(xiàng)集中。從l 項(xiàng)頻繁集產(chǎn)生l + 1 項(xiàng)候選頻繁集過(guò)程也與此類似。 綜上所述，建立拓?fù)淠Ｐ妥钪饕哪康木褪且獙?shí)現(xiàn)針對(duì)某個(gè)網(wǎng)元，能夠從模 型中查找出與其存在拓?fù)溥B接的所有網(wǎng)元( 或者大部分網(wǎng)元) ，并存儲(chǔ)于某種數(shù) 據(jù)結(jié)構(gòu)中，為其他模塊處理做準(zhǔn)備。 2 4 基于拓?fù)浼s束和數(shù)據(jù)挖掘的故障定位總體方案 在移動(dòng)網(wǎng)絡(luò)中，網(wǎng)絡(luò)設(shè)備之間存在的互相作用和互相影響是產(chǎn)生告警傳播的 根源，因此，從相互影響的設(shè)備發(fā)出的告警序列中發(fā)現(xiàn)模式更加具有針對(duì)性和更 加有意義。如果不引入設(shè)備間的關(guān)系，就無(wú)法濾除不相關(guān)設(shè)備的告警對(duì)相關(guān)設(shè)備 告警的干擾，容易產(chǎn)生大量無(wú)意義的模式。因此，引入網(wǎng)絡(luò)拓?fù)涞募s束非常重要， 將網(wǎng)絡(luò)拓?fù)浼s束和數(shù)據(jù)挖掘技術(shù)結(jié)合起來(lái)，可以借助約束降低噪音和數(shù)據(jù)缺失帶 來(lái)的影響，以發(fā)現(xiàn)有價(jià)值的規(guī)律。 下圖是課題提出的基于網(wǎng)絡(luò)拓?fù)浼s束和數(shù)據(jù)挖掘技術(shù)的故障管理總體解決 方案架構(gòu)圖。 第8 頁(yè) 北京郵電大學(xué)碩十研究生畢業(yè)論文第二章嗍絡(luò)拓?fù)淠Ｐ驮诠收隙ㄎ幌到y(tǒng)中的心用 圖2 1 故障管理總體解決方案 6 】 上述解決方案應(yīng)用了現(xiàn)有的數(shù)據(jù)挖掘方法，結(jié)合移動(dòng)網(wǎng)絡(luò)的具體特征，將網(wǎng) 絡(luò)拓?fù)浼s束與數(shù)據(jù)挖掘結(jié)合起來(lái)，形成了對(duì)移動(dòng)網(wǎng)絡(luò)故障定位的有針對(duì)性的方 法。 在上述解決方案中，本文作者主要針對(duì)基于網(wǎng)絡(luò)拓?fù)浣５姆菚r(shí)序告警關(guān)聯(lián) 規(guī)則挖掘算法進(jìn)行了研究和實(shí)現(xiàn)。 移動(dòng)通信網(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)。通過(guò)移動(dòng)通信網(wǎng)絡(luò)結(jié) 構(gòu)分析，我們對(duì)網(wǎng)絡(luò)進(jìn)行抽象，將話務(wù)網(wǎng)、信令網(wǎng)、智能網(wǎng)、g p r s 數(shù)據(jù)網(wǎng)和網(wǎng) 管網(wǎng)等各個(gè)子網(wǎng)實(shí)際的網(wǎng)絡(luò)結(jié)構(gòu)抽象為一般的拓?fù)淠Ｐ蛨D，分別建立各自的網(wǎng)絡(luò) 拓?fù)淠Ｐ?，這樣可以更加明晰、直觀的表示網(wǎng)絡(luò)各個(gè)子網(wǎng)的整體結(jié)構(gòu)以及子網(wǎng)之 間的關(guān)系。最后將各子網(wǎng)絡(luò)模型根據(jù)連接關(guān)系進(jìn)行組合，從而形成一個(gè)總體的移 動(dòng)網(wǎng)絡(luò)拓?fù)淠Ｐ汀?在告警數(shù)據(jù)挖掘方面，首先要進(jìn)行歷史告警數(shù)據(jù)的離線挖掘。在完成告警離 線預(yù)處理后，對(duì)歷史告警數(shù)據(jù)庫(kù)進(jìn)行關(guān)聯(lián)規(guī)則挖掘和序列模式挖掘，之后將挖掘 出的規(guī)則保存在告警規(guī)則和序列庫(kù)中，供在線分析使用。 在挖掘算法的選擇上，應(yīng)重點(diǎn)考慮下面三個(gè)因素： ( 1 ) 不采用多次掃描數(shù)據(jù)庫(kù)的算法。 ( 2 ) 將網(wǎng)元之間的連接關(guān)系作為一種約束條件在挖掘的過(guò)程中將一些關(guān)聯(lián) 規(guī)則濾除掉。 第9 頁(yè) 圓 圈豳 北京郵電大學(xué)碩十研究生畢業(yè)論文第二章網(wǎng)絡(luò)拓?fù)淠Ｐ痛婀收隙ㄎ幌到y(tǒng)中的應(yīng)用 ( 3 ) 網(wǎng)絡(luò)層次應(yīng)當(dāng)做為考慮的因素，它可以將關(guān)聯(lián)規(guī)則更好地加以限制， 以提高挖掘結(jié)果的正確性。 在告警關(guān)聯(lián)規(guī)則挖掘方面，本文作者對(duì)f p g r o w t h 算法進(jìn)行了研究和實(shí)現(xiàn)。 f p g r o w t h 算法對(duì)數(shù)據(jù)庫(kù)只進(jìn)行兩次掃描，尤其適合我們將要面對(duì)的大型數(shù)據(jù)庫(kù)， 可以節(jié)省大量的執(zhí)行時(shí)間，提高了執(zhí)行效率。 2 5 基于網(wǎng)絡(luò)拓?fù)淠Ｐ偷墓收隙ㄎ患夹g(shù)的特點(diǎn) 通過(guò)引入網(wǎng)絡(luò)拓?fù)淠Ｐ偷募s束，將網(wǎng)絡(luò)拓?fù)淠Ｐ团c數(shù)據(jù)挖掘技術(shù)相接合，克 服了傳統(tǒng)電信網(wǎng)絡(luò)告警關(guān)聯(lián)挖掘中待挖掘的數(shù)據(jù)量大、挖掘的關(guān)聯(lián)規(guī)則多且冗余 的缺點(diǎn)?；诰W(wǎng)絡(luò)拓?fù)淠Ｐ偷墓收隙ㄎ患夹g(shù)具有如下特點(diǎn)： 首先，提高了數(shù)據(jù)挖掘的效率?，F(xiàn)有的挖掘算法通常以告警標(biāo)題或者類型作 為候選n 項(xiàng)集進(jìn)行挖掘，因?yàn)楦婢瘶?biāo)題可能超過(guò)千種，從而隨著項(xiàng)集空間的增 大，計(jì)算量顯著增大，導(dǎo)致挖掘算法計(jì)算量大、耗時(shí)長(zhǎng)、效率低。而通過(guò)建立網(wǎng) 絡(luò)拓?fù)淠Ｐ停跃W(wǎng)元關(guān)聯(lián)作為約束來(lái)篩選候選n 項(xiàng)集，大大減少了候選集的數(shù) 量，從而可以減少計(jì)算量，提高挖掘算法的效率。 其次，提高了數(shù)據(jù)挖掘的精度。傳統(tǒng)的挖掘算法都沒(méi)有考慮網(wǎng)絡(luò)的拓?fù)浼s束， 所挖掘出來(lái)的告警關(guān)聯(lián)規(guī)則與網(wǎng)絡(luò)結(jié)構(gòu)沒(méi)有任何關(guān)聯(lián)，從而大大降低了挖掘結(jié)果 的準(zhǔn)確程度。而以網(wǎng)元關(guān)聯(lián)作為約束來(lái)篩選候選集，建立了告警關(guān)聯(lián)與網(wǎng)絡(luò)拓?fù)?之間的關(guān)聯(lián)，過(guò)濾了不相關(guān)告警對(duì)挖掘結(jié)果的影響，從而可以在關(guān)聯(lián)規(guī)則稀疏的 情形下提高挖掘結(jié)果的準(zhǔn)確度。 第1 0 頁(yè) 北京郵電大學(xué)碩十研究生畢業(yè)論文 第三章面向故障定位的移動(dòng)通信網(wǎng)絡(luò)拓?fù)浣?第三章面向故障定位的移動(dòng)通信網(wǎng)絡(luò)拓?fù)浣?拓?fù)淠Ｐ褪菍?duì)網(wǎng)絡(luò)結(jié)構(gòu)的一個(gè)抽象視圖，它隱藏了跟網(wǎng)絡(luò)拓?fù)潢P(guān)系無(wú)關(guān)的其 他各個(gè)方面。通過(guò)它，我們可以直觀的了解網(wǎng)絡(luò)中各網(wǎng)元的連接關(guān)系，發(fā)現(xiàn)網(wǎng)絡(luò) 連接的特點(diǎn)。因此將拓?fù)淠Ｐ鸵刖W(wǎng)絡(luò)管理故障定位系統(tǒng)，通過(guò)拓?fù)淠Ｐ蜑V除掉 不相關(guān)網(wǎng)元設(shè)備的告警對(duì)相關(guān)網(wǎng)元告警的干擾，可以提高故障定位數(shù)據(jù)挖掘的時(shí) 效性和準(zhǔn)確性。 本章在對(duì)某省級(jí)移動(dòng)公司通信網(wǎng)絡(luò)特征進(jìn)行研究和分析的基礎(chǔ)上，提出了網(wǎng) 絡(luò)的抽象拓?fù)淠Ｐ?。盡觀我們的研究是以某省級(jí)移動(dòng)公司通信網(wǎng)絡(luò)為范本和原型 的，但是由于網(wǎng)絡(luò)具有共性，從該省級(jí)移動(dòng)公司通信網(wǎng)絡(luò)抽象出來(lái)的主要特征同 樣適用于其他移動(dòng)通信網(wǎng)絡(luò)。而拓?fù)浣７桨敢餐瑯涌梢愿鶕?jù)具體網(wǎng)絡(luò)進(jìn)行適當(dāng) 修正后應(yīng)用于其他移動(dòng)通信網(wǎng)絡(luò)。 3 1 移動(dòng)通信網(wǎng)絡(luò)結(jié)構(gòu)概述 為支持對(duì)某省級(jí)移動(dòng)網(wǎng)絡(luò)告警數(shù)據(jù)進(jìn)行數(shù)據(jù)挖掘，課題對(duì)該省級(jí)移動(dòng)的通信 網(wǎng)絡(luò)結(jié)構(gòu)進(jìn)行了研究和建模。移動(dòng)通信網(wǎng)絡(luò)網(wǎng)元的連接類型可根據(jù)傳遞信息的不 同分為三大類：話務(wù)中繼、信令鏈路和分組數(shù)據(jù)線路。其中話務(wù)中繼傳遞的是傳 統(tǒng)話音業(yè)務(wù)；信令鏈路傳遞的是網(wǎng)元間的信令消息：分組數(shù)據(jù)鏈路傳遞的主要是 g p r s 數(shù)據(jù)等。 該省級(jí)移動(dòng)公司通信網(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)。在 每個(gè)子網(wǎng)中，我們又可以分析其存在的層次關(guān)系。網(wǎng)絡(luò)的層次關(guān)系有助于網(wǎng)絡(luò)通 信的路由查找，而在網(wǎng)絡(luò)故障管理方面，網(wǎng)絡(luò)的層次關(guān)系同樣可以用來(lái)進(jìn)行故障 告警傳播的分析。 通過(guò)對(duì)移動(dòng)通信網(wǎng)絡(luò)結(jié)構(gòu)的分析，我們對(duì)網(wǎng)絡(luò)進(jìn)行抽象，將話務(wù)網(wǎng)、信令網(wǎng)、 智能網(wǎng)、g p r s 數(shù)據(jù)網(wǎng)和網(wǎng)管網(wǎng)等各個(gè)子網(wǎng)實(shí)際的網(wǎng)絡(luò)結(jié)構(gòu)抽象為一般的拓?fù)淠?型圖，分別建立各自的網(wǎng)絡(luò)拓?fù)淠Ｐ?，這樣可以更加明晰、直觀的表示網(wǎng)絡(luò)各個(gè) 子網(wǎng)的整體結(jié)構(gòu)以及子網(wǎng)之間的關(guān)系。最后將各子網(wǎng)絡(luò)模型根據(jù)連接關(guān)系進(jìn)行組 合，從而形成一個(gè)總體的移動(dòng)網(wǎng)絡(luò)拓?fù)淠Ｐ汀?第l l 頁(yè) 北京郵電大學(xué)碩十研究生畢業(yè)論文第三章面向故障定位的移動(dòng)通信網(wǎng)絡(luò)拓?fù)浣?3 2 移動(dòng)通信網(wǎng)絡(luò)拓?fù)淠Ｐ?本節(jié)我們將對(duì)各個(gè)子網(wǎng)的網(wǎng)元及其連接關(guān)系進(jìn)行抽象( 比如抽象為網(wǎng)元類 型) ，然后將各個(gè)子網(wǎng)通過(guò)結(jié)構(gòu)圖表示出來(lái)；同時(shí)將各個(gè)子網(wǎng)之間的關(guān)系進(jìn)行抽 象，從而得到整個(gè)移動(dòng)通信網(wǎng)絡(luò)的抽象拓?fù)淠Ｐ?。這樣就可以更加明晰、直觀的 表示出各個(gè)子網(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ù)中繼的連接，同時(shí)也有信令鏈路的連接。它主要的網(wǎng)元有 基站( b t s ) 、基站控制器( b s c ) 、變碼器( x c d r ) 、移動(dòng)交換中心( m s c 、 g m s c 、t m s c ) 等。 話務(wù)網(wǎng)模型圖如圖3 所示，話務(wù)網(wǎng)根據(jù)網(wǎng)元的功能又可分為無(wú)線網(wǎng)和交換 網(wǎng)兩部分。無(wú)線網(wǎng)即圖中所示的b s s ，主要是為移動(dòng)臺(tái)( 如手機(jī)) 與交換機(jī)之間 提供鏈路，其結(jié)構(gòu)分層比較明顯，從模型圖中也可以看出，每一個(gè)m s c 交換機(jī) 連接若干個(gè)r x c d r ，而一個(gè)或兩個(gè)r x c d r 則連接一個(gè)b s c ，個(gè)b s c 下則 連接若干個(gè)b t s 。交換網(wǎng)則主要由交換機(jī)與用戶數(shù)據(jù)庫(kù)構(gòu)成，進(jìn)行網(wǎng)絡(luò)通信的交 換和管理，交換網(wǎng)網(wǎng)元的連接則比較復(fù)雜，基本上各個(gè)交換機(jī)都互相連接，如每 個(gè)m s c 都與所有的g m s c 、t m s c 連接，g m s c 、t m s c 之間也有連接。同時(shí) 如上節(jié)提到的，m s c 、g m s c 、t m s c 也都與信令轉(zhuǎn)接點(diǎn)有信令鏈路的連接。 第1 2 頁(yè) 北京郵電大學(xué)碩士研究生畢業(yè)論文第三章面向故障定位的移動(dòng)通信網(wǎng)絡(luò)拓?fù)浣?3 2 2 信令網(wǎng)模型 圖3 - 1 話務(wù)網(wǎng)模型圖”。 7 1 信令網(wǎng)屬于支撐網(wǎng)，它主要進(jìn)行電信業(yè)務(wù)的接續(xù)、控制，是通信網(wǎng)絡(luò)的神經(jīng) 系統(tǒng)，在該省級(jí)移動(dòng)通信網(wǎng)絡(luò)中它主要的網(wǎng)元有高級(jí)信令轉(zhuǎn)節(jié)點(diǎn)( h s l l p ) 、低級(jí) 信令轉(zhuǎn)接點(diǎn)( l s 耶) 、歸屬位置寄存器( h l r ，存儲(chǔ)本地用戶信息的數(shù)據(jù)庫(kù)，包 括用戶號(hào)碼、預(yù)訂業(yè)務(wù)類型、鑒權(quán)信息和當(dāng)前所在地等信息) 、交換機(jī)( m s c 、 g m s c 、t m s c ) 以及其它與信令轉(zhuǎn)接點(diǎn)有信令鏈路連接的網(wǎng)元。 信令網(wǎng)可抽象為圖3 3 。我國(guó)7 號(hào)信令網(wǎng)為三層結(jié)構(gòu)，即高級(jí)信令轉(zhuǎn)接點(diǎn) h s t p 、低級(jí)信令轉(zhuǎn)接點(diǎn)l s t p 、信令點(diǎn)s p 這三層。該省級(jí)移動(dòng)公司的h s t p 及 l s t p 是全互聯(lián)的，而兩臺(tái)h s t p 則互為備份，并與其它省份的高級(jí)信令轉(zhuǎn)接點(diǎn) 連接。第三層的信令點(diǎn)在實(shí)際中包含網(wǎng)絡(luò)中的大部分網(wǎng)元，如圖3 5 中，包含了 話務(wù)網(wǎng)的交換機(jī)、g p r s 網(wǎng)的支持節(jié)點(diǎn)、智能網(wǎng)的控制點(diǎn)等等。 3 2 3 網(wǎng)管網(wǎng)模型 圖3 2 信令網(wǎng)模型圖【7 】 網(wǎng)管網(wǎng)是對(duì)電信網(wǎng)絡(luò)中所有網(wǎng)元進(jìn)行監(jiān)控管理的支撐網(wǎng)，主要由操作維護(hù)中 心( o m c ) 服務(wù)器通過(guò)該網(wǎng)連接到各個(gè)網(wǎng)元，從上面獲取配置信息、性能信息 和告警信息等，同時(shí)也能通過(guò)指令對(duì)網(wǎng)元進(jìn)行遠(yuǎn)程操作。 網(wǎng)管網(wǎng)模型圖如圖3 所示，網(wǎng)管網(wǎng)主要由o m c 服務(wù)器及其管理的網(wǎng)元構(gòu) 成，通過(guò)x 2 5 等分組網(wǎng)連接，不參與通信業(yè)務(wù)。o m c 根據(jù)管理的網(wǎng)元所屬子網(wǎng) 的不同可分為不同的類型，圖中o m c s 管理交換網(wǎng)的交換機(jī)，o m c r 管理無(wú) 線網(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)接點(diǎn)等網(wǎng)元。而同一類型的o m c 由于所管理的網(wǎng)元的廠家不同也有不 第1 3 頁(yè) 北京郵電人學(xué)碩1 ：研究生畢業(yè)論文第三章面向故障定位的移動(dòng)通信網(wǎng)絡(luò)拓?fù)浣?同的設(shè)備和名稱。各個(gè)o m c 服務(wù)器之間都不互連，各管各的網(wǎng)元，但是運(yùn)營(yíng)商 可能根據(jù)實(shí)際情況建立一個(gè)綜合網(wǎng)管系統(tǒng)，將各個(gè)o m c 服務(wù)器的管理信息統(tǒng)一 收集起來(lái)，進(jìn)行集中管理、集中監(jiān)控，如圖中虛線所示。但由于該綜合網(wǎng)管系統(tǒng) 是面向前臺(tái)維護(hù)人員的系統(tǒng)，且在告警數(shù)據(jù)中也沒(méi)有該系統(tǒng)的告警，所以我們不 把它列入網(wǎng)絡(luò)拓?fù)淠Ｐ椭小?3 2 4 智能網(wǎng)模型 圖3 - 3 網(wǎng)管網(wǎng)模型圖 7 1 智能網(wǎng)是在原有通信網(wǎng)的基礎(chǔ)上設(shè)置一層疊加網(wǎng)絡(luò)，用它快速方便、經(jīng)濟(jì)靈 活的生成和實(shí)現(xiàn)各種新業(yè)務(wù)的體系結(jié)構(gòu)。它包括的網(wǎng)元有業(yè)務(wù)控制點(diǎn)( s c p ) 、 業(yè)務(wù)交換點(diǎn)( s s p ) 、業(yè)務(wù)數(shù)據(jù)點(diǎn)( s d p ) 、充值中心( v c ) 、業(yè)務(wù)管理點(diǎn)( s m p ) 和智能外設(shè)( i p ) 等。 智能網(wǎng)模型圖如圖3 所示。智能網(wǎng)通過(guò)s c p 、s s p 與信令轉(zhuǎn)接點(diǎn)連接，接 入7 號(hào)信令網(wǎng)，進(jìn)行信令的交互；通過(guò)s s p 與交換機(jī)連接，接入話務(wù)網(wǎng)，進(jìn)行 話務(wù)通信。圖中s t p 和g m s c 用藍(lán)色表示，因?yàn)檫@兩者不屬于智能網(wǎng)，但也是 子網(wǎng)間連接的接口。 第1 4 頁(yè) 北京郵電大學(xué)碩上研究生畢業(yè)論文第三章面向故障定位的移動(dòng)通信網(wǎng)絡(luò)拓?fù)浣?3 2 5g p r s 網(wǎng)模型 圖3 4 智能網(wǎng)模型圖【7 】 g p r s 數(shù)據(jù)網(wǎng)是實(shí)現(xiàn)g p r s 業(yè)務(wù)的網(wǎng)絡(luò)，網(wǎng)元包括分組控制單元( p c u ，它 與b s c 集成于同一設(shè)備當(dāng)中) 、g p r s 服務(wù)支持節(jié)點(diǎn)( s g s n ) 、g p r s 網(wǎng)關(guān)支持 節(jié)點(diǎn)( g g s n ) 、邊界網(wǎng)關(guān)( b g ) 、計(jì)費(fèi)網(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)元實(shí)體中；s g s n 通過(guò)幀中繼與p c u 連接，通過(guò)分 組網(wǎng)與g g s n 連接：c g 、b g 、d n s 等設(shè)備也是通過(guò)分組網(wǎng)接入到g p r s 網(wǎng)中。 而g p r s 也通過(guò)7 號(hào)信令網(wǎng)同其它子網(wǎng)的網(wǎng)元連接，如圖中藍(lán)色部分所示。 圖3 5g p r s 網(wǎng)模型圖【7 】 第1 5 頁(yè) 北京郵電大學(xué)碩l 研究生畢業(yè)論文第三章面向故障定位的移動(dòng)通信網(wǎng)絡(luò)拓?fù)浣?3 2 6 移動(dòng)通信網(wǎng)絡(luò)模型 上述各小節(jié)對(duì)移動(dòng)通信網(wǎng)絡(luò)各個(gè)子網(wǎng)分別進(jìn)行了抽象并建立起抽象模型。而 各子網(wǎng)之問(wèn)又通過(guò)信令鏈路、話務(wù)中繼和分組數(shù)據(jù)鏈路等多種連接類型相互連接 在一起，組成了移動(dòng)通信網(wǎng)絡(luò)。其中，信令網(wǎng)通過(guò)信令鏈路與其它除網(wǎng)管網(wǎng)之外 的子網(wǎng)進(jìn)行連接；話務(wù)網(wǎng)與信令網(wǎng)有信令鏈路連接，與智能網(wǎng)有話務(wù)中繼連接， 與g p r s 網(wǎng)有分組數(shù)據(jù)鏈路連接；而網(wǎng)管網(wǎng)則通過(guò)自身的分組數(shù)據(jù)網(wǎng)將各個(gè)網(wǎng)元 連接到相應(yīng)的o m c 服務(wù)器。移動(dòng)通信網(wǎng)絡(luò)模型如圖3 所示，其中不同顏色代表 了不同的子網(wǎng)，藍(lán)色部分表示信令網(wǎng)，綠色部分表示g p r s 網(wǎng)，紅色部分表示話 務(wù)網(wǎng)，橙色部分表示智能網(wǎng)，粉色部分表示網(wǎng)管網(wǎng)。 圖3 6 移動(dòng)通信網(wǎng)模型圖【7 3 3 移動(dòng)通信網(wǎng)絡(luò)網(wǎng)元拓?fù)洳檎宜惴ㄑ芯?本節(jié)依據(jù)課題所提出的網(wǎng)元簇劃分方案，對(duì)網(wǎng)元拓?fù)洳檎宜惴ㄟM(jìn)行了研究和 描述。課題將移動(dòng)通信網(wǎng)絡(luò)網(wǎng)元?jiǎng)澐譃槿惥W(wǎng)元簇，它們分別是：公共連接網(wǎng)元 簇、話務(wù)網(wǎng)網(wǎng)元簇和特殊網(wǎng)元簇，并生成三個(gè)網(wǎng)元拓?fù)湮募汗策B接網(wǎng)元文件、 話務(wù)網(wǎng)網(wǎng)元簇拓?fù)湮募吞厥饩W(wǎng)元簇拓?fù)湮募?3 3 1 算法概述 基于上述已有的劃分，網(wǎng)元拓?fù)洳檎宜惴▽?duì)輸入的任意一個(gè)網(wǎng)元序列，可以 北京郵電大學(xué)碩士研究生畢業(yè)論文第三章面向故障定位的移動(dòng)通信剛絡(luò)拓?fù)浣?從網(wǎng)絡(luò)拓?fù)鋽?shù)據(jù)庫(kù)中查詢輸入的網(wǎng)元序列是否被一個(gè)網(wǎng)元簇包含。如果是則返回 t r u e ，表明這個(gè)網(wǎng)元序列中的網(wǎng)元存在拓?fù)潢P(guān)系，即它們之間存在告警傳播路徑； 如果不是則返回f a l s e ，即輸入的網(wǎng)元序列不被任何一個(gè)網(wǎng)元簇包含，這表明這 個(gè)網(wǎng)元序列中的網(wǎng)元之間不存在拓?fù)潢P(guān)系，即它們之間不存在告警傳播路徑。 關(guān)聯(lián)規(guī)則挖掘算法根據(jù)返回的t r e e 或f a l s e 對(duì)頻繁模式進(jìn)行篩選，從而過(guò)濾 掉不存在告警傳播條件的錯(cuò)誤頻繁模式。由于f p g r o w t h 算法采用樹結(jié)構(gòu)進(jìn)行挖 掘，在完成樹的生成后就可以一步生成頻繁模式，所以f p g r o w t h 算法在挖出頻 繁模式后將它們依次進(jìn)行判定是否符合網(wǎng)絡(luò)拓?fù)浼s束，然后將不符合的模式從最 終的頻繁模式集中刪除 由于網(wǎng)元簇的劃分可能不能涵蓋所有的告警傳播路徑，或者不能完整的覆蓋 一個(gè)告警傳播路徑，因此增加一個(gè)可控參數(shù)一匹配模糊度，來(lái)降低現(xiàn)有的網(wǎng)元簇 與過(guò)濾掉公共連接網(wǎng)元后的網(wǎng)元序列的匹配精度。匹配模糊度的缺省值為1 ，表 明需要1 0 0 精確的匹配，可以適當(dāng)降低這個(gè)參數(shù)值，如降為9 0 ，此時(shí)，若過(guò) 濾掉公共聯(lián)接網(wǎng)元后的輸入序列與一個(gè)網(wǎng)元簇的匹配度達(dá)到9 0 ，網(wǎng)元拓?fù)洳?詢就返回t r u e 。 3 3 2 輸入?yún)?shù)說(shuō)明 名稱：輸入網(wǎng)元序列 類型：整數(shù)數(shù)組 含義：網(wǎng)元標(biāo)號(hào)序列，在實(shí)際算法運(yùn)行中，該序列數(shù)為頻繁模式中包含的網(wǎng) 元標(biāo)號(hào)序列。 3 3 3 可控參數(shù)說(shuō)明 名稱：匹配模糊度 類型：雙精度 含義：表征匹配輸入網(wǎng)元序列可接受的模糊度，缺省值為1 。如設(shè)為9 0 則 表明，當(dāng)存在一個(gè)網(wǎng)元簇與過(guò)濾掉公共連接網(wǎng)元后的輸入網(wǎng)元序列的匹配度大于 或者等于9 0 時(shí)，認(rèn)為該序列存在拓?fù)潢P(guān)系，網(wǎng)絡(luò)拓?fù)渌惴ǚ祷豻 r u e 。 3 3 4 輸出參數(shù)說(shuō)明 類型：布爾類型 含義：表征過(guò)濾掉公共連接網(wǎng)元后的輸入網(wǎng)元序列是否被一個(gè)定義的網(wǎng)元簇 第1 7 頁(yè) 北京郵電人學(xué)碩j ：研究生畢業(yè)論文第三章面向故障定位的移動(dòng)通信網(wǎng)絡(luò)拓?fù)浣?所包含，如果是返回t r u e ，否則返回f a l s c 。 3 3 5 算法流程圖 圖3 - 7 網(wǎng)絡(luò)拓?fù)洳檎宜惴鞒虉D 第1 8 頁(yè) 北京郵電人學(xué)碩士研究生畢業(yè)論文第三章面向故障定位的移動(dòng)通信網(wǎng)絡(luò)拓?fù)浣?第1 9 頁(yè) 北京郵電人學(xué)碩上研究生畢業(yè)論文第三章面向故障定位的移動(dòng)通信網(wǎng)絡(luò)拓?fù)浣?3 3 6 算法邏輯說(shuō)明 從算法流程圖上可以看出，網(wǎng)元拓?fù)洳檎宜惴ㄖ饕譃槿齻€(gè)過(guò)程，過(guò)濾公共 連接網(wǎng)元，判斷過(guò)濾后的序列是否被特殊網(wǎng)元簇包含，如果不被包含，判斷過(guò)濾 后的序列是否被話務(wù)網(wǎng)網(wǎng)元簇包含。 過(guò)濾公共連接網(wǎng)元 遍歷輸入網(wǎng)元序列的每一個(gè)元素，遍歷公共連接網(wǎng)元中的每一個(gè)網(wǎng)元，判斷 網(wǎng)元序列的當(dāng)前元素是否包含于公共連接網(wǎng)元集合中，如果是，刪除該元素，判 斷下一個(gè)元素。由于公共連接網(wǎng)元文件的特征是文件每一行僅有一個(gè)整數(shù)，文件 每一行內(nèi)容具有唯一性，文件行數(shù)相對(duì)比較少，有4 2 行，而唯一性以及個(gè)數(shù)的 確定性正是s t l 中s e t 數(shù)據(jù)結(jié)構(gòu)的最大特征，所以使用t 數(shù)據(jù)結(jié)構(gòu)來(lái)保存每一 行的數(shù)據(jù)。而使用s e t 數(shù)據(jù)結(jié)構(gòu)可使查詢的時(shí)間復(fù)雜度降低。 判斷過(guò)濾后的序列是否被特殊網(wǎng)元簇包含 掃描特殊網(wǎng)元簇拓?fù)鋽?shù)組的每一個(gè)整數(shù)型集合，根據(jù)匹配模糊度以及過(guò)濾后 的序列的網(wǎng)元個(gè)數(shù)，計(jì)算出判定輸入網(wǎng)元序列具有拓?fù)潢P(guān)系時(shí)該輸入序列被一個(gè) 網(wǎng)元簇包含的網(wǎng)元數(shù)目的最小值。遍歷過(guò)濾后的序列的每一個(gè)網(wǎng)元標(biāo)號(hào)，通過(guò)查 找當(dāng)前網(wǎng)元簇整數(shù)型集合判斷其是否包括當(dāng)前的網(wǎng)元標(biāo)號(hào)，如果一個(gè)網(wǎng)元簇包含 的過(guò)濾后的序列中網(wǎng)元標(biāo)號(hào)的個(gè)數(shù)大于或者等于由匹配模糊度和網(wǎng)元序列個(gè)數(shù) 決定的匹配最小值時(shí)，網(wǎng)絡(luò)拓?fù)洳樵兯惴ǚ祷豻 r u e ，否則執(zhí)行判斷過(guò)濾后的序列 是否被話務(wù)網(wǎng)網(wǎng)元簇包含。 判斷過(guò)濾后的序列是否被話務(wù)網(wǎng)網(wǎng)元