李海舟

（陜西省行政學院 西安 710068）

1 引言

智慧校園是近年新興的一種基于可編程網(wǎng)絡(luò)的新型網(wǎng)絡(luò)體系架構(gòu)，具有“控制與轉(zhuǎn)發(fā)分離”、“設(shè)備資源虛擬化”和“通用硬件及軟件可編程”這三大特性［1］，能夠靈活滿足不同用戶的應(yīng)用需求，為核心網(wǎng)絡(luò)及應(yīng)用的創(chuàng)新提供了良好的平臺。

智慧校園架構(gòu)分為應(yīng)用層、控制層和轉(zhuǎn)發(fā)層。其中控制層負責處理數(shù)據(jù)平面資源的編排、維護網(wǎng)絡(luò)拓撲狀態(tài)信息等，轉(zhuǎn)發(fā)層負責基于流表的數(shù)據(jù)處理轉(zhuǎn)發(fā)和狀態(tài)收集［2］。目前智慧校園轉(zhuǎn)發(fā)層網(wǎng)絡(luò)大多通過Mininet仿真平臺虛擬實現(xiàn)，或者通過多臺Openvswitch交換機搭建實現(xiàn)［3］。Mininet能夠快速創(chuàng)建一個大規(guī)模網(wǎng)絡(luò)，但是不能完全反映真實網(wǎng)絡(luò)的特點［4］；Openvswitch交換機能夠創(chuàng)建真實網(wǎng)絡(luò)，但是構(gòu)建更新大規(guī)模網(wǎng)絡(luò)時，資源消耗過大［5］。結(jié)合上述兩種技術(shù)的優(yōu)點和缺陷，本研究將Mininet虛擬網(wǎng)絡(luò)與Openvswitch真實交換機融合，搭建一個虛實結(jié)合的智慧校園網(wǎng)絡(luò)環(huán)境，以同時滿足網(wǎng)絡(luò)大規(guī)模和真實性的需求。在搭建智慧校園虛實網(wǎng)絡(luò)過程中，Openvswitch交換機連接多個Mininet虛擬網(wǎng)絡(luò)且Openvswitch通常個數(shù)有限，因此關(guān)鍵問題是如何選擇Openvswitch交換機，即真實節(jié)點的位置。

本文首先基于圖論和社交網(wǎng)絡(luò)等領(lǐng)域的定義，研究真實節(jié)點的特點，設(shè)計了智慧校園虛實網(wǎng)絡(luò)拓撲中真實節(jié)點的定義。在網(wǎng)絡(luò)建模中，進一步解釋了真實節(jié)點的特點。然后通過研究節(jié)點介數(shù)、重疊社區(qū)發(fā)現(xiàn)等算法，提出適用于智慧校園虛實網(wǎng)絡(luò)拓撲的真實節(jié)點定位算法。最后實驗驗證，通過兩種適用于智慧校園虛實網(wǎng)絡(luò)拓撲的真實節(jié)點定位算法，有效發(fā)現(xiàn)了拓撲中真實節(jié)點的位置。

2 準備工作

在智慧校園虛實網(wǎng)絡(luò)拓撲中，節(jié)點分為虛擬節(jié)點和真實節(jié)點。其中，虛擬節(jié)點代表Mininet仿真的虛擬交換機，主要展示網(wǎng)絡(luò)的規(guī)模［6］；真實節(jié)點代表Openvswitch真實交換機，主要展示網(wǎng)絡(luò)的真實性［7］。搭建智慧校園虛實網(wǎng)絡(luò)時，Mininet可以仿真任意拓撲的大規(guī)模網(wǎng)絡(luò)，但是真實性較低。Openvswitch交換機能夠提高網(wǎng)絡(luò)真實性，但是個數(shù)有限［8］。為了通過有限個Openvswitch交換機和Mininet，搭建大規(guī)模且真實性高的網(wǎng)絡(luò)環(huán)境，提前確定網(wǎng)絡(luò)拓撲中真實節(jié)點的位置尤為重要。

2.1 算法基礎(chǔ)

將智慧校園虛實網(wǎng)絡(luò)拓撲建模為一個無向連通圖 G(V，E)，其中V={v1，v2，…，vn}是圖 G 中所有頂點的集合，E={e1，e2，…，em}是所有邊的集合。設(shè)集合 S={s1，s2，…，sh}是圖G中的邊緣節(jié)點集合，為V的子集。

定義1（節(jié)點介數(shù)）：網(wǎng)絡(luò)中所有最短路徑中經(jīng)過該節(jié)點的路徑數(shù)目占最短路徑總數(shù)的比例［9］，公式如下：

其中，σst表示節(jié)點s和t之間所有的最短路徑數(shù)目，σst(v)表示這些路徑中經(jīng)過節(jié)點v的數(shù)目。

定義2（節(jié)點度）：節(jié)點度是指G中與節(jié)點v相關(guān)聯(lián)的邊數(shù)目，即鄰居數(shù)目。

定義3（社區(qū)重疊度）：設(shè) A、B為兩個社區(qū)，則這兩個社區(qū)的重疊度over(A，B)為［10］

其中， ||A和 ||B分別代表A和B社區(qū)中的節(jié)點個數(shù)。

定義4（節(jié)點連接度）：設(shè)有節(jié)點u和社區(qū)c，節(jié)點u與社區(qū)c之間的連接度connect(u，c)為

其中，ku為節(jié)點u的度，如果u與c中的任一節(jié)點v相鄰接，則wuv=1，否則wuv=0。

定義5（真實節(jié)點）：設(shè)真實節(jié)點個數(shù)為r個。圖G中的節(jié)點v如果滿足以下兩個條件之一，則稱節(jié)點v為G的一個真實節(jié)點。

條件一：v處于G中邊緣節(jié)點對(si，sj)之間的最短路徑上，且所有節(jié)點按介數(shù)遞減排序后，v位于前r個。

條件二：v為社區(qū)重疊節(jié)點，且節(jié)點按照重疊次數(shù)（至少為2）從大到小排序后，v位于前r個。

如果v僅滿足上述兩個條件之一，則v為普通真實節(jié)點；如果v同時滿足上述兩個條件，則v為高級真實節(jié)點。

2.2 網(wǎng)絡(luò)建模

假設(shè)智慧校園虛實網(wǎng)絡(luò)拓撲如圖1所示。圓代表交換機，包括真實節(jié)點和虛擬節(jié)點。方塊代表主機，與主機相連的交換機為邊緣節(jié)點。按照真實節(jié)點定義，查找真實節(jié)點的結(jié)果如圖2所示。根據(jù)條件一，真實節(jié)點位于邊緣節(jié)點對之間的最短路徑上，且所有節(jié)點按介數(shù)遞減排序時，真實節(jié)點為前r個。圖2中，黑粗邊代表邊緣節(jié)點對之間的最短路徑。3個淺色節(jié)點和1個深色節(jié)點經(jīng)過的最短路徑數(shù)最多，滿足條件一，因此選為真實節(jié)點。根據(jù)條件二，真實節(jié)點為社區(qū)重疊節(jié)點，且所有節(jié)點按照重疊次數(shù)遞減排序后，真實節(jié)點為前r個。圖2中，深色節(jié)點是唯一一個社區(qū)重疊節(jié)點，滿足條件二，因此也選為真實節(jié)點。另外，由于深色節(jié)點同時滿足條件一和條件二，所以為高級真實節(jié)點，其它3個淺色節(jié)點為普通真實節(jié)點。搭建智慧校園虛實網(wǎng)絡(luò)時，應(yīng)該優(yōu)先在深色節(jié)點位置，配置Openvswitch真實交換機。

圖1 智慧校園虛實網(wǎng)絡(luò)拓撲

圖2 真實節(jié)點查找結(jié)果圖

3 關(guān)鍵算法

考慮到真實節(jié)點傳輸?shù)木W(wǎng)絡(luò)流量較大且通常連接多個局部網(wǎng)絡(luò)，本文設(shè)計了兩種適用于智慧校園虛實網(wǎng)絡(luò)拓撲的真實節(jié)點定位算法，分別為基于節(jié)點介數(shù)分析的真實節(jié)點查找算法和基于重疊社區(qū)發(fā)現(xiàn)的真實節(jié)點查找算法。

3.1 基于節(jié)點介數(shù)分析的節(jié)點查找算法

算法一為基于節(jié)點介數(shù)分析的真實節(jié)點查找算法。為了提高智慧校園虛實網(wǎng)絡(luò)拓撲的真實性，需要最大程度增加真實節(jié)點上的網(wǎng)絡(luò)流量。在智慧校園網(wǎng)絡(luò)中，流量由邊緣節(jié)點連接的主機產(chǎn)生，所以可以把邊緣節(jié)點看作流量的起點和終點［11］。網(wǎng)絡(luò)流量通常經(jīng)過源節(jié)點和目的節(jié)點的最短路徑進行傳輸，因此為了承載最多的網(wǎng)絡(luò)流量，真實節(jié)點應(yīng)該選擇邊緣節(jié)點間最短路徑最多交疊的位置，即介數(shù)最大的節(jié)點［12］。算法一為每個節(jié)點增加了前驅(qū)節(jié)點、最短路徑經(jīng)過次數(shù)等屬性，有效解決了一個節(jié)點可能存在多個前驅(qū)節(jié)點的問題。每找到一條最短路徑，則回溯更新每個節(jié)點出現(xiàn)次數(shù)，最后通過各節(jié)點最短路徑經(jīng)過次數(shù)和最短路徑總數(shù)計算節(jié)點介數(shù)，返回候選真實節(jié)點集合。

算法一：基于節(jié)點介數(shù)分析的節(jié)點查找算法輸入：網(wǎng)絡(luò)G=(V，E)，邊緣節(jié)點個數(shù)h，真實節(jié)點個數(shù)r

輸出：候選真實節(jié)點集合R1

方法：

步驟1：計算所有邊緣節(jié)點間最短路徑總數(shù)，及所有最短路徑上，每個節(jié)點的出現(xiàn)次數(shù)；

1）Fori=1 to h

2）For所有節(jié)點初始化節(jié)點屬性。（節(jié)點狀態(tài)=white，權(quán)重=+∞，前驅(qū)節(jié)點集合 p）

3）邊緣節(jié)點i的權(quán)重=0，p=null

4）節(jié)點i入隊列Q

5）WhileQ不為空

6）Q中首元素t出列

7）For與t相鄰接的所有節(jié)點k

8）If k的狀態(tài)=white

9）K入隊列Q

10）If k的權(quán)重＞t的權(quán)重+1

11）K的權(quán)重=t的權(quán)重+1，k的前驅(qū)節(jié)點集合 p清空，t入集合p

12）Else k的權(quán)重=t的權(quán)重+1

13）If k的前驅(qū)節(jié)點集合 p不包含t，t屬于集合p

14）End If 15）End For

16）t的狀態(tài)=black

17）Forj=i+1 to h

18）計算從 j到i的最短路徑數(shù)，計算路徑上每個節(jié)點出現(xiàn)次數(shù)

19）End For

20）返回所有邊緣節(jié)點間最短路徑總數(shù)sum，及所有最短路徑上每個節(jié)點的出現(xiàn)次數(shù)nodeTimes。

步驟2：計算所有節(jié)點的介數(shù)，按從大到小排序，選擇排序靠前的節(jié)點放入候選真實節(jié)點集合R1。

1）For i=1 to ||V 計算節(jié)點介數(shù)：

2）根據(jù)節(jié)點的betweeness從大到小排序；

3）選擇Top r個節(jié)點作為候選真實節(jié)點，放入R1；

4）返回候選真實節(jié)點集合R1。

算法一中，步驟1首先根據(jù)節(jié)點的權(quán)重，計算每個節(jié)點的前驅(qū)節(jié)點集合。然后回溯邊緣節(jié)點間的每條路徑，統(tǒng)計邊緣節(jié)點間最短路徑總數(shù)以及每個節(jié)點在最短路徑上的出現(xiàn)次數(shù)。步驟2首先計算每個節(jié)點的介數(shù)，然后通過優(yōu)先級隊列，對所有節(jié)點從大到小排序，最后選擇top r個節(jié)點，存入候選真實節(jié)點集合R1。

3.2 基于重疊社區(qū)發(fā)現(xiàn)的節(jié)點查找算法

算法二為基于重疊社區(qū)發(fā)現(xiàn)的真實節(jié)點查找算法。智慧校園虛實網(wǎng)絡(luò)是為了模擬真實的計算機網(wǎng)絡(luò)而設(shè)計的網(wǎng)絡(luò)仿真環(huán)境，其中，Mininet模擬緊密關(guān)聯(lián)的局部子網(wǎng)，Openvswitch模擬子網(wǎng)之間的連接節(jié)點。一個真實節(jié)點連接多個子網(wǎng)，也可以看作是多個子網(wǎng)的重疊節(jié)點。這里引入社交網(wǎng)絡(luò)中的社區(qū)來代表子網(wǎng)，則真實節(jié)點為重疊社區(qū)之間的重疊節(jié)點。算法二引入重疊度閾值和連接度閾值，其中，重疊度閾值［13］控制鄰近社區(qū)的融合，保證一個子網(wǎng)由一個社區(qū)表示。得到初始社區(qū)集合后，連接度閾值［14］則有效解決了剩余節(jié)點的社區(qū)歸屬問題。

算法二：基于重疊社區(qū)發(fā)現(xiàn)的節(jié)點查找算法

輸入：網(wǎng)絡(luò)G=(V，E)，邊緣節(jié)點個數(shù)h，真實節(jié)點個數(shù)r，重疊度閾值overlayT，連接度閾值connectT

輸出：候選真實節(jié)點集合R2

方法：

步驟1：計算以邊緣節(jié)點為核心的社區(qū)，根據(jù)重疊度閾值，融合鄰接的社區(qū)。根據(jù)連接度閾值，劃分節(jié)點到相應(yīng)社區(qū)，返回所有社區(qū)的集合；

1）For i=1 to h計算邊緣節(jié)點的度degree

2）邊緣節(jié)點根據(jù)degree，從大到小排序，放入數(shù)組top

3）候選社區(qū)C0={top[0]}

4）For i=1 to ||V If（top［0］，Vi）∈ E

C0=C0∪{Vi}

5）C0入社區(qū)集合AllC

6）For i=2 to top.length

7）臨時社區(qū)C={top[i]}

8）For j=1 to ||V If（top[i]，Vj）∈ E

C=C∪{Vj}

9）For集合AllC中的每個社區(qū)k

10）計算 over(c，k)

11）If over(c，k)＞overlayT

12）社區(qū)c與k合二為一，去掉重復(fù)節(jié)點，break

13）End For

14）If AllC中沒有社區(qū)與C融合C入社區(qū)集合AllC

15）End For

16）If存在節(jié)點沒有分到AllC任一社區(qū)節(jié)點放入restNode數(shù)組

17）For數(shù)組restNode的每個節(jié)點n

18）For集合AllC中的每個社區(qū)k

19）計算connect(n，k)

20）If connect(n，k)＞connect節(jié)點 n放入社區(qū)k

21）End For

22）End For

23）循環(huán)17）～22），直到AllC中所有社區(qū)的節(jié)點不再變化

24）返回社區(qū)集合AllC

步驟2：計算所有節(jié)點隸屬社區(qū)的個數(shù)，按從大到小排序，選擇排序靠前的節(jié)點放入候選真實節(jié)點集合R1。

1）For集合AllC中的每個社區(qū)k

2）For社區(qū)k中的每個節(jié)點n，計算n隸屬社區(qū)的個數(shù)communityNum

3）根據(jù)節(jié)點的communityNum從大到小排序4）選擇Top r個節(jié)點作為候選真實節(jié)點，放入R2

5）返回候選真實節(jié)點集合R2

算法二中，步驟1首先計算所有邊緣節(jié)點的度，并使用優(yōu)先級隊列對邊緣節(jié)點從大到小排序。然后選擇度最大的邊緣節(jié)點及其鄰接節(jié)點構(gòu)成初始社區(qū)C0，將C0放入社區(qū)集合AllC中。之后依次選擇剩余的度最大的邊緣節(jié)點及其鄰接節(jié)點，構(gòu)成臨時社區(qū)C。計算C與AllC中每個社區(qū)的重疊度over，如果over超過重疊度閾值，則兩個社區(qū)合二為一，去掉相同節(jié)點；如果over未超過重疊度閾值，則AllC增加一個社區(qū)C。所有的邊緣節(jié)點都計算完成后，如果還存在不屬于任一社區(qū)的節(jié)點，則計算節(jié)點與AllC中每個社區(qū)的連接度connect，如果connect超過連接度閾值，則將節(jié)點加入該社區(qū)［15］。循環(huán)這個過程，知道AllC中所有社區(qū)的節(jié)點不再變化。步驟2首先計算所有節(jié)點隸屬社區(qū)的個數(shù)，然后使用優(yōu)先級隊列，對所有節(jié)點從大到小排序，最后選擇top r個節(jié)點，存入候選真實節(jié)點集合R2。

3.3 算法對比

由于智慧校園虛實網(wǎng)絡(luò)拓撲中，流量主要由邊緣節(jié)點，即連接主機的交換機節(jié)點產(chǎn)生，因此相對于傳統(tǒng)計算介數(shù)的算法，算法一只計算邊緣節(jié)點對之間的最短路徑，而不是所有節(jié)點間最短路徑。另外，與Dijkstra算法［16］不同，本文網(wǎng)絡(luò)拓撲中，邊的權(quán)值統(tǒng)一為1，所以部分節(jié)點的前驅(qū)節(jié)點不止一個，算法一為每個節(jié)點配置前驅(qū)結(jié)點集合屬性，解決了部分節(jié)點存在多個前驅(qū)結(jié)點的問題。

網(wǎng)絡(luò)拓撲中，任一子網(wǎng)一定包含多個主機，等價于包含多個邊緣節(jié)點，因此相較于其它基于局部拓展的重疊社區(qū)發(fā)現(xiàn)算法，算法二沒有選擇所有節(jié)點中度最大的節(jié)點為種子節(jié)點，而只對邊緣節(jié)點按度排序，選擇度最大的邊緣節(jié)點作為種子節(jié)點。這樣不僅降低了節(jié)點排序的復(fù)雜度，而且以邊緣節(jié)點為社區(qū)中心能夠更準確地模擬包含多個子網(wǎng)的大規(guī)模網(wǎng)絡(luò)。

算法一和算法二分別基于真實節(jié)點定義的兩個條件設(shè)計。其中，算法一針對真實節(jié)點承載大網(wǎng)絡(luò)流量的特點，算法二針對真實節(jié)點連接多個子網(wǎng)的特點。兩者相比，算法一和算法二分別關(guān)注網(wǎng)絡(luò)拓撲的局部特性和全局特性。算法一適用于網(wǎng)絡(luò)流量大的小規(guī)模網(wǎng)絡(luò)，算法二適用于包含多個子網(wǎng)的大規(guī)模網(wǎng)絡(luò)，對于不同的網(wǎng)絡(luò)拓撲結(jié)構(gòu)，應(yīng)該選擇兩者中更適合的算法。

4 實驗與分析

為了驗證算法的可行性和有效性，本文選取3個不同的網(wǎng)絡(luò)拓撲，對基于節(jié)點介數(shù)分析的真實節(jié)點查找算法和基于重疊社區(qū)發(fā)現(xiàn)的真實節(jié)點查找算法進行驗證。

4.1 網(wǎng)絡(luò)拓撲一

如圖3，網(wǎng)絡(luò)拓撲一中共7個節(jié)點，7條邊。其中，節(jié)點1、2、3和4為邊緣節(jié)點。設(shè)真實節(jié)點個數(shù)為2，算法一和算法二的實驗結(jié)果如表1所示，算法一的候選真實節(jié)點集合為｛5，6｝，算法二的候選真實節(jié)點集合為空，因此對于網(wǎng)絡(luò)拓撲一，節(jié)點5和6為真實節(jié)點。

圖3 網(wǎng)絡(luò)拓撲一

表1 網(wǎng)絡(luò)拓撲一實驗結(jié)果表

1）算法一流程分析（設(shè)真實節(jié)點個數(shù)為2）

首先計算邊緣節(jié)點之間的最短路徑。節(jié)點1為起點時，到其他邊緣節(jié)點的最短路徑有3條，分別為1-5-2、1-5-6-3和1-5-6-4。回溯這三條路徑，更新每個節(jié)點經(jīng)過最短路徑的次數(shù)。其他所有邊緣節(jié)點也循環(huán)這個過程，可得最短路徑總數(shù)為6，各節(jié)點經(jīng)過最短路徑的次數(shù)依次為3、3、3、3、5、5、0。然后計算每個節(jié)點的介數(shù)，并按照遞減排序。由于真實節(jié)點個數(shù)是2，所以最后選擇介數(shù)最大的兩個節(jié)點，即節(jié)點5和節(jié)點6作為候選真實節(jié)點。

2）算法二流程分析（設(shè)真實節(jié)點個數(shù)為2、重疊度閾值為0.45，連接度閾值為0.5）

首先計算所有節(jié)點的度，并將邊緣節(jié)點按照度遞減進行排序。節(jié)點1、2、3、4的度相等，可以從任一邊緣節(jié)點開始形成初始社區(qū)，這里選擇節(jié)點1及其鄰接點構(gòu)成初始社區(qū)C0=｛1，5｝，并放入社區(qū)集合AllC中。然后其他邊緣節(jié)點及其鄰接點依次構(gòu)成臨時社區(qū)C，與AllC中的社區(qū)計算重疊度。節(jié)點2形成的社區(qū)C=｛2，5｝，與C0的重疊度為0.5，超過重疊度閾值，因此C與C0融合為一個社區(qū)，C0=｛1，2，5｝。節(jié)點3形成的社區(qū)C=｛3，6｝，與C0的重疊度為0，小于重疊度閾值，因此形成新的社區(qū)C1=｛3，6｝，同理節(jié)點 4形成的社區(qū)與 C1融合，C1=｛3，4，6｝。剩余節(jié)點7，計算與社區(qū)C0和C1的連接度都為0.5，未超過連接度閾值，因此節(jié)點7不屬于任何社區(qū)。由于社區(qū)C0和C1間不存在重疊節(jié)點，因此最后返回的候選真實節(jié)點集合為空。

4.2 網(wǎng)絡(luò)拓撲二

如圖4，網(wǎng)絡(luò)拓撲二中共7個節(jié)點，8條邊。其中，節(jié)點1、2、3和4為邊緣節(jié)點。設(shè)真實節(jié)點個數(shù)為2，算法一和算法二的計算結(jié)果如表2所示。算法一的候選真實節(jié)點集合為｛2，5｝，算法二的候選真實節(jié)點集合為｛5｝，因此對于網(wǎng)絡(luò)拓撲二，節(jié)點5為高級真實節(jié)點，節(jié)點2為普通真實節(jié)點。

圖4 網(wǎng)絡(luò)拓撲二

表2 網(wǎng)絡(luò)拓撲二實驗結(jié)果表

1）算法一流程分析（設(shè)真實節(jié)點個數(shù)為2）

首先計算邊緣節(jié)點之間的最短路徑。節(jié)點1為起點時，到其他邊緣節(jié)點的最短路徑有3條，分別為1-2、1-2-5-3和1-2-5-7-4?；厮葸@三條路徑，更新每個節(jié)點經(jīng)過最短路徑的次數(shù)。其它所有邊緣節(jié)點也循環(huán)這個過程，可得最短路徑總數(shù)為6，各節(jié)點經(jīng)過最短路徑的次數(shù)依次為3、5、3、3、4、0、3。然后計算每個節(jié)點的介數(shù)，并按照遞減排序。由于真實節(jié)點個數(shù)是2，所以最后選擇介數(shù)最大的兩個節(jié)點，即節(jié)點2和節(jié)點5作為候選真實節(jié)點。

2）算法二流程分析（設(shè)真實節(jié)點個數(shù)為2，重疊度閾值為0.45，連接度閾值為0.5）

首先計算所有節(jié)點的度，并將邊緣節(jié)點按照度遞減進行排序，依次為節(jié)點2、3、4、1，這里選擇節(jié)點2及其鄰接點構(gòu)成初始社區(qū)C0=｛1，2，5，6｝，并放入社區(qū)集合AllC中。然后其他邊緣節(jié)點及其鄰接點依次構(gòu)成臨時社區(qū)C，與AllC中的社區(qū)計算重疊度。節(jié)點3形成的社區(qū)C=｛3，5，7｝，與C0的重疊度為0.33，小于重疊度閾值，因此形成新的社區(qū)C1=｛3，5，7｝，節(jié)點4形成的社區(qū)C=｛4，7｝，與C1的重疊度為0.5，超過重疊度閾值，因此與C1融合，C1=｛3，4，5，7｝。C0和C1包含所有節(jié)點，沒有剩余節(jié)點。由于社區(qū)C0和C1間存在重疊節(jié)點5，因此最后返回的候選真實節(jié)點集合為｛5｝。

4.3 網(wǎng)絡(luò)拓撲三

圖5 網(wǎng)絡(luò)拓撲三

如圖5，網(wǎng)絡(luò)拓撲三為大規(guī)模網(wǎng)絡(luò)，共100個節(jié)點，130條邊。其中，節(jié)點1～35為邊緣節(jié)點。設(shè)真實節(jié)點個數(shù)為10，算法一和算法二的實驗結(jié)果如表3所示，算法一的候選真實節(jié)點集合為｛67，76，17，47，91，18，31，53，25，12｝，算法二的候選真實節(jié)點集合為｛41，65，71，74，75，79，89，91，53，55｝，因此對于網(wǎng)絡(luò)拓撲三，節(jié)點53和91為高級真實節(jié)點，其它節(jié)點為普通真實節(jié)點。

表3 網(wǎng)絡(luò)拓撲三實驗結(jié)果表

1）算法流程分析

通過算法一，計算網(wǎng)絡(luò)拓撲三的最短路徑總數(shù)為1198條，各節(jié)點的介數(shù)如圖6所示。由于真實節(jié)點個數(shù)為10，所以選擇介數(shù)最大的10個節(jié)點，即圖6中空心點，為候選真實節(jié)點。

圖6 節(jié)點介數(shù)

通過算法二，計算網(wǎng)絡(luò)拓撲三中各邊緣節(jié)點的度，如圖7所示。依次選擇度最大的邊緣節(jié)點及其鄰接點形成臨時社區(qū)，與社區(qū)集合AllC中的每個社區(qū)計算重疊度，來決定融合社區(qū)或者形成新的社區(qū)。剩余節(jié)點計算同每個社區(qū)的連接度，來決定節(jié)點是否歸屬某社區(qū)，最后得到表3中的17個社區(qū)。選擇社區(qū)之間重疊次數(shù)最大的10個節(jié)點，為候選真實節(jié)點。

圖7 邊緣節(jié)點度

2）實驗分析

實驗中，如果改變重疊度閾值，算法二得到的社區(qū)總數(shù)和候選真實節(jié)點集合會發(fā)生變化。設(shè)置重疊度閾值范圍為0.01～0.5時，實驗結(jié)果如表4所示。

表4 重疊度閾值分析實驗結(jié)果表

由表4可知，重疊度閾值越小，網(wǎng)絡(luò)拓撲劃分的社區(qū)總數(shù)越少，相應(yīng)的候選真實節(jié)點集合也會發(fā)生變化。當重疊度閾值范圍為［0.3，0.5）時，社區(qū)劃分總數(shù)和候選真實節(jié)點集合最為穩(wěn)定，因此本文設(shè)置重疊度閾值為0.45是合理的。

實驗中，算法一和算法二得到的候選真實節(jié)點集合R1和R2通常不完全一致。如果R1和R2中存在相同的節(jié)點，則為高級真實節(jié)點，在搭建智慧校園虛實網(wǎng)絡(luò)時，應(yīng)該在節(jié)點位置優(yōu)先部署Openvswitch交換機。R1和R2中剩余節(jié)點則為普通真實節(jié)點，可以根據(jù)用戶為R1和R2集合設(shè)置的不同權(quán)重，來選擇其他真實節(jié)點。

5 結(jié)語

本文基于Openvswitch交換機和Mininet仿真平臺，搭建智慧校園虛實網(wǎng)絡(luò)環(huán)境，其中“虛”代表的Mininet保證網(wǎng)絡(luò)的規(guī)模性，“實”代表的Openvswitch保證網(wǎng)絡(luò)的真實性。為了模擬大規(guī)模且真實性高的網(wǎng)絡(luò)，本文提出了針對智慧校園虛實網(wǎng)絡(luò)的真實節(jié)點定位方法。首先基于圖論和社交網(wǎng)絡(luò)等領(lǐng)域的定義，設(shè)計了智慧校園虛實網(wǎng)絡(luò)拓撲中真實節(jié)點的定義。然后通過網(wǎng)絡(luò)建模，進一步解釋了真實節(jié)點的特點，并基于其特點，設(shè)計了兩種適用于智慧校園虛實網(wǎng)絡(luò)拓撲的真實節(jié)點定位算法。最后本文選取3個不同的網(wǎng)絡(luò)拓撲進行實驗分析，實驗表明，本文提出的算法能夠有效發(fā)現(xiàn)拓撲中真實節(jié)點的位置，驗證了算法的可行性和有效性。目前本文使用拓撲圖中，所有節(jié)點和邊的屬性均一致，接下來可以區(qū)分不同節(jié)點和邊的屬性，進一步研究。