基于GIS的網(wǎng)絡(luò)拓?fù)錁?gòu)建與展示技術(shù)方法研究

馮同寒，艾中良

(華北計算技術(shù)研究所，北京 100083)

0 引言

信息社會對計算機網(wǎng)絡(luò)愈加依賴，而計算機網(wǎng)絡(luò)的規(guī)模日益龐大和復(fù)雜，并且網(wǎng)絡(luò)上的信息流量急速增長?？焖?、準(zhǔn)確、全面地掌握網(wǎng)絡(luò)信息，可以使管理和決策人員對網(wǎng)絡(luò)進行優(yōu)化，對網(wǎng)絡(luò)異常實現(xiàn)及時響應(yīng)。

傳統(tǒng)的網(wǎng)絡(luò)拓?fù)鋬H限于網(wǎng)絡(luò)設(shè)備邏輯層面的展示［1］，只能表現(xiàn)網(wǎng)絡(luò)節(jié)點間的邏輯關(guān)系，提供的信息十分有限。結(jié)合GIS的網(wǎng)絡(luò)拓?fù)湔故痉椒榫W(wǎng)絡(luò)節(jié)點增加了地理位置信息，這就為網(wǎng)絡(luò)管理和決策人員進行網(wǎng)絡(luò)管理和網(wǎng)絡(luò)事件分析提供了可視化方法。目前對結(jié)合GIS的網(wǎng)絡(luò)拓?fù)湔故痉椒ㄑ芯枯^少［2］，并且已有的研究方法存在拓?fù)鋵哟蝿澐植幻鞔_、顯示信息不夠全面等問題。

針對目前研究中存在的問題，結(jié)合細(xì)節(jié)層次LOD(Levels of Detail)方法，對基于GIS的網(wǎng)絡(luò)拓?fù)錁?gòu)建及展示方法進行研究，重點從網(wǎng)絡(luò)拓?fù)湔故灸Ｐ偷臉?gòu)建、拓?fù)鋽?shù)據(jù)的組織管理、LOD方法的使用3方面進行研究。

1 網(wǎng)絡(luò)拓?fù)涠嘁晥D模型構(gòu)建

計算機網(wǎng)絡(luò)具有區(qū)域結(jié)構(gòu)特點和層次化特點。以國內(nèi)互聯(lián)網(wǎng)為例，國內(nèi)的互聯(lián)網(wǎng)核心層由北京、上海、廣州、沈陽、南京、武漢、成都、西安等8個城市的核心節(jié)點組成。其中北京、上海、廣州是國內(nèi)互聯(lián)網(wǎng)的外聯(lián)節(jié)點。要構(gòu)造一個相對真實直觀的網(wǎng)絡(luò)拓?fù)淠Ｐ停仨毧紤]網(wǎng)絡(luò)的區(qū)域性特點和層次性特點［3］。

針對網(wǎng)絡(luò)結(jié)構(gòu)層次化、內(nèi)容復(fù)雜的特點，構(gòu)建如圖1所示的網(wǎng)絡(luò)拓?fù)淇梢暬嘁晥D模型，可視化模型主要由拓?fù)滟Y產(chǎn)視圖、網(wǎng)絡(luò)狀態(tài)視圖、網(wǎng)絡(luò)屬性視圖、拓?fù)浣y(tǒng)計視圖等組成［4］。通過這幾個視圖的綜合運用，可以多角度、多層次地展示網(wǎng)絡(luò)拓?fù)湫畔?。多視圖模型主要完成以下幾個功能:

1)針對網(wǎng)絡(luò)的層次化特點構(gòu)建多視圖模型，建立模型與網(wǎng)絡(luò)結(jié)構(gòu)之間的對應(yīng)關(guān)系。

2)梳理每個視圖所展示網(wǎng)絡(luò)拓?fù)湫畔?，展示要素之間的組合。

3)在特定視圖中，每張GIS地圖只顯示與其對應(yīng)的網(wǎng)絡(luò)所在地理范圍內(nèi)可見的網(wǎng)絡(luò)拓?fù)湫畔⒑途W(wǎng)絡(luò)狀態(tài)信息［5］。

4)不同視圖之間交互機制的設(shè)計，視圖之間網(wǎng)絡(luò)信息的聯(lián)動。

圖1 多視圖模型

在圖1所示多視圖模型中:1)拓?fù)滟Y產(chǎn)視圖展示的內(nèi)容主要包括主機、交換機、路由器、服務(wù)器等網(wǎng)路節(jié)點設(shè)備;2)網(wǎng)絡(luò)屬性視圖展示的內(nèi)容主要包括具體的網(wǎng)絡(luò)節(jié)點設(shè)備的屬性信息，以及如子網(wǎng)，匯聚鏈路等抽象網(wǎng)絡(luò)對象的屬性信息［6］;3)網(wǎng)絡(luò)狀態(tài)視圖展示的內(nèi)容主要是網(wǎng)絡(luò)微觀的網(wǎng)絡(luò)節(jié)點狀態(tài)及安全信息和宏觀的抽象節(jié)點的運行狀態(tài)和網(wǎng)絡(luò)安全信息;4)拓?fù)浣y(tǒng)計視圖展示的內(nèi)容主要包括數(shù)量、比例以及其他用戶自定義的統(tǒng)計事項信息。

2 拓?fù)鋽?shù)據(jù)的組織

2.1 基本對象數(shù)據(jù)模型定義

在上述多視圖展示模型的基礎(chǔ)上，結(jié)合網(wǎng)絡(luò)結(jié)構(gòu)的特點，設(shè)計了結(jié)合GIS信息的網(wǎng)絡(luò)拓?fù)湔故净緦ο髷?shù)據(jù)模型，主要包括3個基本的抽象對象:節(jié)點、子網(wǎng)、鏈路。其中節(jié)點表示網(wǎng)絡(luò)中的設(shè)備，如主機、交換機、路由器、服務(wù)器等;子網(wǎng)表示一組節(jié)點對象和鏈路結(jié)合［7］，這里的節(jié)點對象可以是具體的網(wǎng)絡(luò)設(shè)備節(jié)點，也可以是表示子網(wǎng)的抽象節(jié)點;鏈路表示節(jié)點與節(jié)點之間或子網(wǎng)與子網(wǎng)之間的連接。下面是建立模型所需的定義和描述。

定義1 節(jié)點用一個五元組表示，Node＜ID，NP，Ni，L1...N，NS ＞ ，其中 ID 為節(jié)點唯一標(biāo)識，NP 為節(jié)點地理位置，Ni為節(jié)點所屬子網(wǎng)，L1...N為節(jié)點所連鏈路，NS為節(jié)點狀態(tài)信息。

定義2 鏈路用一個四元組表示，Link＜ID，Ni，N1...N，LS ＞ ，其中 ID 為鏈路的唯一標(biāo)識，Ni為鏈路所屬子網(wǎng)，N1...N為鏈路包含節(jié)點，LS 為鏈路狀態(tài)信息。

定義3 子網(wǎng)用一個五元組表示，SubNet＜ID，SP，Ni，N1…N，SS ＞ ，其中 ID 為子網(wǎng)唯一標(biāo)識，SP 為繪圖定位點位置，Ni為子網(wǎng)所屬上層子網(wǎng)，N1…N為子網(wǎng)內(nèi)節(jié)點設(shè)備，SS為子網(wǎng)狀態(tài)。

2.2 拓?fù)鋽?shù)據(jù)組織

2.2.1 LOD 分層方法

當(dāng)網(wǎng)絡(luò)數(shù)據(jù)規(guī)模較大時，網(wǎng)絡(luò)拓?fù)浼?xì)節(jié)不能全部同時在繪圖區(qū)上展示，需要調(diào)整所渲染的數(shù)據(jù)細(xì)節(jié)以滿足可視化的要求。事實上，用戶在某一時刻只能關(guān)注有限的數(shù)據(jù)，因此不需要同時渲染所有的拓?fù)鋽?shù)據(jù)細(xì)節(jié)，只要直觀地給出用戶想要看到的關(guān)鍵數(shù)據(jù)細(xì)節(jié)［8］。

因此，在進行復(fù)雜場景、多圖形實時繪制時，為提高繪制效率，常使用LOD方法，LOD的技術(shù)原理是:隨著窗口的深度變化，加載不同層次的數(shù)據(jù)，窗口通常只加載視角范圍內(nèi)的數(shù)據(jù)，而對視角外的數(shù)據(jù)以及遠(yuǎn)的數(shù)據(jù)進行簡化和隱藏。LOD方法只讀取所需目標(biāo)區(qū)域的數(shù)據(jù)，而非全局?jǐn)?shù)據(jù)。

本文在繪制和展示二維拓?fù)鋱D時，借助LOD方法對網(wǎng)絡(luò)拓?fù)溥M行分層顯示。需要說明的是，傳統(tǒng)地圖的等級劃分是根據(jù)比例尺，采用制圖綜合方法分級顯示，層級之間是替代顯示的關(guān)系，而網(wǎng)絡(luò)拓?fù)湟晥D是根據(jù)節(jié)點級別分層顯示，層級之間是疊加的關(guān)系。

針對網(wǎng)絡(luò)拓?fù)鋱D這種特點，在借助LOD方法的同時，本文使用四叉樹結(jié)構(gòu)對網(wǎng)絡(luò)拓?fù)鋽?shù)據(jù)進行分層組織［9］。根據(jù)四叉樹原理(如圖2所示)，分割的深度越大，則網(wǎng)絡(luò)節(jié)點越多。本文結(jié)合網(wǎng)絡(luò)特點，將四叉樹的深度設(shè)為5層。其中前4層是結(jié)合GIS的網(wǎng)絡(luò)拓?fù)滹@示，第5層為邏輯拓?fù)滹@示。

圖2 四叉樹原理示意圖

本文設(shè)計的基于四叉樹結(jié)構(gòu)的LOD分層基本思路如下:

1)根據(jù)所有節(jié)點所在位置確定初始視口相關(guān)參數(shù):X，Y，Length，Width。其中 X，Y 為矩形左下角坐標(biāo)，Length，Width為矩形長和寬;

2)采用遞歸方式將初始矩形4等分，得到每個子區(qū)域矩形參數(shù);

3)根據(jù)矩形范圍參數(shù)及每個節(jié)點的位置確定每個子區(qū)域包含的節(jié)點。對不在視口范圍的那部分節(jié)點進行隱藏。

本文還定義了適用于網(wǎng)絡(luò)拓?fù)銵OD結(jié)構(gòu)的四叉樹節(jié)點評價函數(shù):

式中Di為子節(jié)點到當(dāng)前節(jié)點的距離，Area為當(dāng)前視口的范圍，λ為細(xì)節(jié)調(diào)整參數(shù)，R為當(dāng)前地圖比例尺，Number為子節(jié)點數(shù)量［10］。

2.2.2 向上緩存

此外，在對大規(guī)模網(wǎng)絡(luò)拓?fù)溥M行展示時，為兼顧拓?fù)鋱D繪制的系統(tǒng)開銷，提高繪制速率，增強顯示效果，提出“向上緩存”的方法。在內(nèi)存中為大規(guī)模節(jié)點的繪制設(shè)置緩存區(qū)。

具體來說，當(dāng)拓?fù)鋱D由粗粒度到細(xì)粒度時，即對當(dāng)前網(wǎng)絡(luò)的子網(wǎng)拓?fù)溥M行展示時，當(dāng)前網(wǎng)絡(luò)及向上層級的網(wǎng)絡(luò)節(jié)點數(shù)量有限，為提高顯示效果，對當(dāng)前及向上層級的拓?fù)湟廊贿M行繪制和渲染;當(dāng)拓?fù)鋱D由細(xì)粒度到粗粒度，即對當(dāng)前網(wǎng)絡(luò)的上層網(wǎng)絡(luò)進行展示時，考慮到下層節(jié)點數(shù)量較大，則在內(nèi)存中刪除，再次展示時，從數(shù)據(jù)源重新讀取數(shù)據(jù)進行展示［11］。

3 網(wǎng)絡(luò)拓?fù)湔故?/h2>

3.1 改進“Angle+Radius”布局算法

繪圖技術(shù)的研究內(nèi)容實現(xiàn)圖到幾何空間的映射關(guān)系。用形式化的方法可以表示為:對于圖G=(V，E)，有 d:G→R3，或者 G=(V，E)，d:G→R2，其中d(v∈V)={X(x)，Y(y)，Z(z)};d(e∈E)={(e1，e2)，(e2，e3)，…，(en，en-1)}［12］。為每個網(wǎng)絡(luò)設(shè)備分配三維或二維的坐標(biāo)。

網(wǎng)絡(luò)拓?fù)涞睦L圖算法分為物理布局和邏輯布局，其中邏輯布局與節(jié)點設(shè)備實際位置無關(guān)，是布局算法的主要研究內(nèi)容。本文在對網(wǎng)絡(luò)拓?fù)溥M行邏輯布局時，結(jié)合傳統(tǒng)的樹型和射線布局算法，提出了“Angle+Radius”樹型和射線型布局算法。

3.1.1 改進的樹型布局算法

傳統(tǒng)的樹型布局結(jié)構(gòu)中有一個根節(jié)點，具有可擴展的深度和寬度，并且簡單直觀，層次分明，具有通用性，是廣泛使用的一種簡單布局算法。但存在節(jié)點重疊、覆蓋等缺點。針對這些缺點，本文在傳統(tǒng)樹型布局算法基礎(chǔ)上進行改進，在進行樹型布局時，充分考慮節(jié)點之間的數(shù)量和父子位置關(guān)系，進行“Angle+Radius”的計算。改進的樹型布局算法如圖3所示，基本過程如下:

1)確定節(jié)點到父節(jié)點半徑長度，在樹型布局中，實際是要確定Y軸距離，X軸距離已經(jīng)確定［12］。這時要綜合考慮2個因素，一是待布局節(jié)點的兄弟節(jié)點數(shù)量，二是待布局節(jié)點的子節(jié)點數(shù)量。一般來說，兄弟節(jié)點和子節(jié)點數(shù)越多的，半徑越長。

2)確定角度區(qū)域。首先確定當(dāng)前已布局節(jié)點與根節(jié)點的角度，以該夾角為基礎(chǔ)，加上或減去一個調(diào)整因數(shù)β(β根據(jù)實際情況調(diào)整的)，形成子節(jié)點的布局區(qū)域，進而計算各子節(jié)點的具體位置。

3)待布局節(jié)點沒有子節(jié)點(葉節(jié)點)時，則只需要考慮兄弟節(jié)點數(shù)量。

4)拓?fù)溥B接關(guān)系發(fā)生變化時，對發(fā)生改變的區(qū)域進行局部更新。避免全局刷新。

圖3 改進的樹型布局示意圖

3.1.2 改進的射線布局算法

傳統(tǒng)的射線型布局算法中，根節(jié)點位于一個圓環(huán)的中心，將子節(jié)點布局在環(huán)上，然后環(huán)上的子節(jié)點為圓心，進行下一輪布局。射線型布局算法具有較好的空間利用率，節(jié)點分布相對均勻［13］。但也存在節(jié)點重疊、交叉等問題。本文在傳統(tǒng)射線布局算法基礎(chǔ)上進行改進，在進行射線布局時，充分考慮下層節(jié)點的數(shù)量與上層節(jié)點的位置關(guān)系，進行“Angle+Radius”的計算。改進的射線布局算法如圖4所示，算法基本過程如下:

1)確定節(jié)點到父節(jié)點半徑長度，同樣要綜合考慮2個因素，一是待布局節(jié)點的兄弟節(jié)點數(shù)量，二是待布局節(jié)點的子節(jié)點數(shù)量。一般來說，兄弟節(jié)點和子節(jié)點數(shù)越多的，半徑越長。

2)確定子節(jié)點布局角度范圍。首先確定當(dāng)前已布局節(jié)點與根節(jié)點的角度，以該夾角為基礎(chǔ)，加上或減去一個調(diào)整因數(shù)β(β根據(jù)實際情況調(diào)整的)，形成子節(jié)點的布局區(qū)域。進一步計算各子節(jié)點的具體位置。

3)待布局節(jié)點沒有子節(jié)點(葉節(jié)點)時，則只需要考慮兄弟節(jié)點數(shù)量。

4)拓?fù)溥B接關(guān)系發(fā)生變化時，對發(fā)生改變的區(qū)域進行局部更新。避免全局刷新。

圖4 改進的射線布局示意圖

3.2 拓?fù)涠嘁晥D可視化工作流程

本文設(shè)計的拓?fù)湔故鞠到y(tǒng)工作流程如圖5所示［14］。

圖5 系統(tǒng)工作流程圖

3.3 實驗結(jié)果及分析

使用VC++和OpenGL編程，對結(jié)合GIS的網(wǎng)絡(luò)拓?fù)湔故具M行實現(xiàn)。包括具備地理信息的網(wǎng)絡(luò)拓?fù)湔故竞统橄蟮倪壿嬐負(fù)涞恼故?。其中具備地理信息的拓?fù)湔故臼褂肔OD方法，對邏輯拓?fù)涞牟季质褂谩癆ngle+Radius”的基本算法。

圖6所示為國內(nèi)核心層網(wǎng)絡(luò)拓?fù)?，圖7所示編號為NET-NJ-01的子網(wǎng)拓?fù)洌瑘D8所示編號為NET-NJ-1201的子網(wǎng)邏輯拓?fù)洹?/p>

圖6 網(wǎng)絡(luò)拓?fù)湟?/p>

圖7 網(wǎng)絡(luò)拓?fù)涠?/p>

圖8 網(wǎng)絡(luò)拓?fù)淙?/p>

從圖6和圖7可以看出，運用LOD方法對結(jié)合GIS的網(wǎng)絡(luò)拓?fù)溥M行展示，具有層次鮮明，過渡平滑的優(yōu)點;從圖8可以看出，拓?fù)鋱D在畫布中部，各層節(jié)點分布均勻，無重疊、交叉等問題。

4 結(jié)束語

通過對基于地理信息的網(wǎng)絡(luò)拓?fù)湔故痉椒ㄟM行研究，完成了網(wǎng)絡(luò)拓?fù)湔故灸Ｐ偷臉?gòu)建，設(shè)計了拓?fù)鋽?shù)據(jù)基本對象模型。本文在進行網(wǎng)絡(luò)展示方面使用LOD方法實現(xiàn)視圖的轉(zhuǎn)換［16］，在對網(wǎng)絡(luò)邏輯拓?fù)溥M行展示時，使用改進的樹型布局算法和射線布局算法作為基本布局算法，達到較好的網(wǎng)絡(luò)拓?fù)湔故拘Ч?/p>

［1］李艷霞，劉學(xué)，黨壽江，等.網(wǎng)管系統(tǒng)中基于谷歌地圖的拓?fù)淇梢暬瘜崿F(xiàn)［J］.計算機工程與設(shè)計，2013，34(2):681-685.

［2］鄒曉天，余俊.基于GIS的戰(zhàn)術(shù)通信網(wǎng)絡(luò)拓?fù)涑尸F(xiàn)技術(shù)研究［J］.通信技術(shù)，2014，47(2):231-234.

［3］何鵬，陸建新，施佺.互聯(lián)網(wǎng)拓?fù)淇梢暬ぞ逩eoPlot研究［J］.計算機與現(xiàn)代化，2011(4):64-67.

［4］申山宏，李龍江，夏棋.基于移動GIS系統(tǒng)的網(wǎng)絡(luò)拓?fù)鋱D呈現(xiàn)機制［J］，微型機與應(yīng)用，2013(7):53-57.

［5］陳軍，周曉光.基于拓?fù)渎?lián)動的增量更新方法研究［J］.測繪學(xué)報，2008，37(3):322-329，337.

［6］張偉明，羅軍勇，王清賢.網(wǎng)絡(luò)拓?fù)淇梢暬芯烤C述［J］.計算機應(yīng)用研究，2008，25(6):1606-1610.

［7］李琳，李杰.基于SNMP的網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)算法［J］.計算機工程與設(shè)計，2008，29(6):1345-1347.

［8］Matthew W，Georges G，Daniel K.Interactive Data Visualization:Foundations，Techniques and Applications［M］.AK Peters Ltd.，2010:28-29.

［9］Shifflet J A.A Technique independent fusion model for network intrusion detection［C］//Proceedings of the Midstates Conference on Undergraduate Research in Computer Science and Mathematics.2005:13-19.

［10］Bejerano Y.Taking the skeletons out of the closets:A sim-ple and efficient topology discovery scheme for large Ethernet［J］.IEEE/ACM Transactions on Networking，2009，17(5):1385-1398.

［11］Wang Haoxiang.From a mess to graphic maps:Visualizaiton large-scale heterogeneous networks［C］//Proceedings of the Second International Conference on Computer Modeling and Simulation.2005:531-535.

［12］Gregory C，Kulsoom A.Passive visual fingerprinting of network attack tools［C］//Proceedings of 2004 ACM Workshop on Visualization and Data Mining for Computer Security.2004:45-54.

［13］Li Xiangyu.A method of network topology visualization based on SNMP［C］//Proceedings of 2011 International Conference on Instrumentation，Measurement，Computer，Communication and Control.2011:245-248.

［14］Yang Guozheng，Lu Yuliang，Chen Huixian.A new network topology visualization algorithm［C］//Proceedings of 2011 International Conference on Instrumentation，Measurement，Computer，Communication and Control.2011:369-372.

［15］Li Xiangyan，Wang Qingxian，Yang Lin，et al.The research on network security visualization key technology［C］//Proceedings of 2012 Fourth International Conference on Multimedia Information Network and Security.2012:983-988.

［16］McCormick B H，DeFanti T A，Brown M D，et al.Visualization in scientific computing［J］.IEEE Computer Graphics and Applications，1987，7(10):69.

［17］Au S，Leckie C，Parhar A.Efficient visualization of large routing topologies［J］.International Journal of Network Management，2004，9(2):105-118.

［18］Li Xiaobin，Li Shuzhen.SNMP-Web-based distributed network management system design and implementation［J］.Microcomputer Information，2010，26(3):142-143.