謝超凡，徐魯雄

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

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

謝超凡，徐魯雄

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

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

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

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

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

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

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

1 校園網(wǎng)網(wǎng)絡(luò)拓?fù)錁?gòu)造

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

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

表1 各樓層權(quán)重分布 單位:m

2 最小支撐樹構(gòu)造

構(gòu)造最小支撐樹常用的方法有避圈法和破圈法構(gòu)造,本文詳細(xì)使用避圈法構(gòu)造成本最低的光纖鋪設(shè),用破圈法驗(yàn)證一下．

2.1 使用避圈法構(gòu)造(kruskal)

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

算法的具體步驟如下:

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

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

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

按照算法構(gòu)造的最小支撐樹如下:

仿造上述的步驟可得到如下的構(gòu)造圖,見圖2.

圖2 最小支撐樹T

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

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

算法具體步驟:

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

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

第3步:結(jié)束．

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

圖3 最小支撐樹T

3 結(jié)論

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

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

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

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

[4] 沈 廣，陳允平，劉 棟.基于最小生成樹編碼的配電網(wǎng)恢復(fù)遺傳算法[J].電力系統(tǒng)自動(dò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-),男,碩士,福建師范大學(xué)福清分校實(shí)驗(yàn)師,主要從事數(shù)據(jù)挖掘研究.

1672-2027(2015)04-0034-05

TP202

A