基于最小支撐樹的光纖布線
——以福建師范大學福清分校為例

謝超凡，徐魯雄

(福建師范大學 福清分校,福建 福清 350300)

基于最小支撐樹的光纖布線
——以福建師范大學福清分校為例

謝超凡，徐魯雄

(福建師范大學 福清分校,福建 福清 350300)

信息技術的迅猛發(fā)展,人們對數(shù)據(jù)的通信要求的質(zhì)量也越來越高,為了全校師生員工的科研、教學和信息檢索提供了更好的網(wǎng)絡服務.文章使用最小支撐樹來解決校園網(wǎng)光纖布線,在提高學校網(wǎng)絡服務效率的同時減少費用的支出,達到效率和成本兼顧．

最小支撐樹;光纖;校園網(wǎng)

計算機網(wǎng)絡使用人員不僅僅追求高質(zhì)量的辦公效率,對于圖像、音頻、視頻等多媒體數(shù)據(jù)傳輸?shù)乃俣鹊扰c生活娛樂相關的信息也提出更高的要求[1-2]．校園網(wǎng)作為學校網(wǎng)絡的信息承載中心,其帶寬和傳輸速率直接影響到全校師生對信息系統(tǒng)的使用效率和滿意度．基于計算機和網(wǎng)絡技術建立起來的對教學、科研、管理、技術服務、生活服務等校園信息的收集、處理、整合、存儲、傳輸和應用,使數(shù)字資源得到充分優(yōu)化利用的一種虛擬教育環(huán)境．數(shù)字化校園用層次化、整體的觀點來實施校園信息化建設,將校園網(wǎng)上信息進行更好的組織和分類,讓用戶在網(wǎng)上快速發(fā)現(xiàn)自己需求的信息．為師生提供網(wǎng)上信息交流環(huán)境,讓管理人員科學地、規(guī)范地管理自己的數(shù)據(jù),并將這些信息方便地發(fā)布出去．

在信息化浪潮席卷全球、日益滲透到社會生活各個領域的今天,數(shù)字化校園建設如火如荼．特別是歐美、日本等發(fā)達國家高度重視信息化建設,早在20世紀90年代初幾乎所有的高校便建成了比較完善的校園網(wǎng),各個職能部門都基本實現(xiàn)了網(wǎng)絡化、信息化管理．我國高校信息化建設起步較晚,近十年來,隨著我國高等教育的快速發(fā)展,高校辦學規(guī)模不斷擴大,使各個管理部門任務越來越繁重,不僅增加了工作量,更增大了工作難度,管理手段落后將直接影響教學質(zhì)量和辦學水平．教育信息化已成為教育改革與發(fā)展的必然要求和重要推動力．

通過建設一個高速、安全、可靠、可擴充的網(wǎng)絡系統(tǒng),實現(xiàn)校內(nèi)信息的高度共享、傳遞,教學及管理信息化,并通過與廣域網(wǎng)的互聯(lián),實現(xiàn)校際間的信息共享及與INTERNET的連接,實現(xiàn)遠程教育,為學校的教學、管理、日常辦公、內(nèi)外交流等各方面提供全面、切實的支持．

由于上述的需求對校園網(wǎng)建設提出了很高的要求,歸根結底校園網(wǎng)建設的基礎都是實現(xiàn)校內(nèi)網(wǎng)絡傳輸全光纖化．然而,網(wǎng)絡的建設不是一勞永逸的,隨著招生規(guī)模的擴大和師資隊伍的不斷壯大,對校園網(wǎng)網(wǎng)絡要求只會越來越高,在這種環(huán)境下,需要提高學校的光纖覆蓋和光纖升級改造,但是在改造過程中不能僅僅只考慮到設備的先進性和成熟性,對于經(jīng)濟性和實用性同樣重要．本文使用最小支撐樹來保證網(wǎng)絡節(jié)點正常高速通信的同時,達到成本最小[3-4]．

1 校園網(wǎng)網(wǎng)絡拓撲構造

節(jié)點的集合代表各個要鋪設的樓與中心機房記為V,如果要在兩個樓或者與中心機房鋪設光纖則用邊進行連接,所有邊的集合記為E,由于鋪設的光纖成本依賴于光纖的長度,則邊的權重直接用兩個節(jié)點之間的距離來表示記為W.為了保證學校的行政辦公,因此行政樓與機房只能直連,其他樓之間由于地理位置和高度的原因確實存在鋪設的難題則距離就用+∞表示,可得網(wǎng)絡拓撲圖，見圖1.

兩個節(jié)點之間無法鋪設或者存在鋪設障礙的將權重定義為+∞,不在圖上畫出,現(xiàn)在要解決的問題是要確定鋪設哪些光纖,以使每兩個節(jié)點之間通信的總成本最低．實際上,這就是最小支撐樹的問題．首先,將邊的權重按從小到大排列如表1.

表1 各樓層權重分布 單位:m

2 最小支撐樹構造

構造最小支撐樹常用的方法有避圈法和破圈法構造,本文詳細使用避圈法構造成本最低的光纖鋪設,用破圈法驗證一下．

2.1 使用避圈法構造(kruskal)

開始選一條最小的邊,以后每一步中,總從與已選邊不構成圈的那些未選邊中,選一條權最小的(每一步中,如果有兩條或兩條以上的邊都是權最小的邊,則從中任選一條)．

算法的具體步驟如下:

第1步:令i=1,E0=?

第2步:選一條邊ei∈EEi-1,使ei是使(V,Ei-1∪{ei})不含圈的所有邊e(e∈EEi-1)中權最小的邊．令E=Ei-1∪{ei},如果這樣的邊不存在,則最小支撐樹T就構造好了．

第3步:把i換成i+1,轉(zhuǎn)第2步．

按照算法構造的最小支撐樹如下:

仿造上述的步驟可得到如下的構造圖,見圖2.

圖2 最小支撐樹T

2.2 使用破圈法構造(Rosenstiehl和管梅谷)

任取一個圈,從圈中去掉一條權最大的邊(如果有兩條或兩條以上的邊都是權最大的邊,則任意去掉其中一條)．在余下的圖中,重復這個步驟,直至得到一個不含圈的圖為止,這時的圖便是最小樹．

算法具體步驟:

第1步:i=1,V0=V．

第2步:若Vk中不含圈,轉(zhuǎn)3.否則,設C為Vk中一個圈,ek為C上帶權最大的邊,令Vk+1=Vk-ek;k=k+1,重復2．

第3步:結束．

由圖3可知利用破圈法構造的最小支撐樹與避圈一致．

圖3 最小支撐樹T

3 結論

本文首先利用圖來對校園網(wǎng)的網(wǎng)絡建立拓撲結構,將成本看成是使用光纖的總長度,問題轉(zhuǎn)化為在保證網(wǎng)絡節(jié)點正常通信的同時,怎么使得鋪設光纖使得總成本達到最小,由此自然而然借用圖論中的最小支撐樹理論,從而求出最優(yōu)的方案,為校園網(wǎng)建設的科學決策提供理論和實際的依據(jù)．

[1] 姚 坤.高校校園網(wǎng)建設方案的設計與研究[D].銀川：北方民族大學,2013

[2] 鄧寶林.高校校園網(wǎng)改造工程的規(guī)劃與設計[D].大連：大連理工大學,2013

[3] 楊文宇.基于最小生成樹算法的配電網(wǎng)架優(yōu)化規(guī)劃[D].西安：西安理工大學,2005

[4] 沈 廣，陳允平，劉 棟.基于最小生成樹編碼的配電網(wǎng)恢復遺傳算法[J].電力系統(tǒng)自動化,2007(14)：31-33

Based on the Minimum Spanning Tree of Fiber Optic Cabling ——Case Study of Fuqing Branch of Fujian Normal University

XIE Chaofan, XU Luxiong

(Fuqing Branch of Fujian Normal University, Fuqing 350300, China)

The rapid development of information technology, people's requirements are also increasingly for quality of data,providing a better network services for school staff and students’ research, teaching and information retrieval. This article uses the minimum spanning tree to solve the campus fiber optic cabling, network services to improving school efficiency of network services while reducing the cost of spending to achieve both efficiency and cost.

spanning tree; fiber; campus network

2015-10-24

謝超凡(1984-),男,碩士,福建師范大學福清分校實驗師,主要從事數(shù)據(jù)挖掘研究.

1672-2027(2015)04-0034-05

TP202

A