基于最小生成樹模型的通信網(wǎng)絡(luò)鋪設(shè)方案構(gòu)建

劉雅倩，王昌海，曾淑嫻，朱家明

(安徽財(cái)經(jīng)大學(xué)1．金融學(xué)院;2．統(tǒng)計(jì)與應(yīng)用數(shù)學(xué)學(xué)院，安徽蚌埠233030)

基于最小生成樹模型的通信網(wǎng)絡(luò)鋪設(shè)方案構(gòu)建

劉雅倩1，王昌海2，曾淑嫻2，朱家明2

(安徽財(cái)經(jīng)大學(xué)1．金融學(xué)院;2．統(tǒng)計(jì)與應(yīng)用數(shù)學(xué)學(xué)院，安徽蚌埠233030)

針對(duì)通信網(wǎng)絡(luò)設(shè)計(jì)問題，通過有關(guān)數(shù)據(jù)分析，運(yùn)用最小生成樹模型并結(jié)合prim算法得出使通信網(wǎng)絡(luò)的總鋪設(shè)費(fèi)用最省的鋪設(shè)方案，分別考慮通信網(wǎng)絡(luò)結(jié)點(diǎn)與鏈路的可靠性，對(duì)鋪設(shè)方案進(jìn)行進(jìn)一步非線性規(guī)劃，從而保證通信暢通的結(jié)點(diǎn)都能夠達(dá)到90%。

通信網(wǎng)絡(luò);最小生成樹;線性規(guī)劃模型(LP);Netdraw

計(jì)算機(jī)網(wǎng)絡(luò)技術(shù)在各個(gè)領(lǐng)域的應(yīng)用范圍已經(jīng)逐步廣泛起來，其發(fā)展也在不斷地推動(dòng)人類社會(huì)逐漸走向信息時(shí)代。與此同時(shí)也存在著很多不足，諸如安全隱患、信息漏洞等，這些對(duì)人們的工作和生活造成了很大的影響。對(duì)于一個(gè)系統(tǒng)，可靠性是其重要的整體指標(biāo)，通信網(wǎng)絡(luò)亦不例外。通信網(wǎng)絡(luò)的可靠性不僅與通信設(shè)備、鏈路有關(guān)，而且還與網(wǎng)絡(luò)結(jié)構(gòu)有關(guān)。由于網(wǎng)絡(luò)結(jié)構(gòu)的復(fù)雜多變，通信網(wǎng)絡(luò)的可靠性分析一直是個(gè)棘手的問題，本文試圖以獲取的數(shù)據(jù)為例進(jìn)行研究，建立數(shù)學(xué)模型來制定一個(gè)具有較高可靠性的、成本較低的通信網(wǎng)絡(luò)的鋪設(shè)方案。(相關(guān)數(shù)據(jù)見2014年江西省研究生數(shù)學(xué)建模競(jìng)賽試題A題［1］)

1 鋪設(shè)費(fèi)用最省的通信網(wǎng)絡(luò)鋪設(shè)方案的制定

1．1研究思路。

制定一個(gè)鋪設(shè)費(fèi)用最省的通信網(wǎng)絡(luò)鋪設(shè)方案實(shí)際上是設(shè)計(jì)一條沒有固定起點(diǎn)和終點(diǎn)，每個(gè)節(jié)點(diǎn)都能夠?qū)崿F(xiàn)信息通暢且使總費(fèi)用最小的通信結(jié)構(gòu)，屬于典型的最小生成樹［2］問題，應(yīng)該鋪設(shè)一條能夠貫穿所有結(jié)點(diǎn)且不重復(fù)的線路，網(wǎng)絡(luò)不存在自環(huán)現(xiàn)象，即不存在首尾相同的鏈路，并且網(wǎng)絡(luò)中任兩個(gè)節(jié)點(diǎn)之間最多只有一條邊相連。

1．2數(shù)據(jù)處理。

首先對(duì)80個(gè)節(jié)點(diǎn)進(jìn)行編號(hào)，80個(gè)節(jié)點(diǎn)分別從1編號(hào)至80，編的號(hào)碼與數(shù)據(jù)中所給節(jié)點(diǎn)的順序一一相對(duì)應(yīng)。接著計(jì)算節(jié)點(diǎn)距離和節(jié)點(diǎn)間的單位鋪設(shè)價(jià)格計(jì)算節(jié)點(diǎn)間鋪設(shè)費(fèi)用:

設(shè)G=100A．*B，根據(jù)節(jié)點(diǎn)間鋪設(shè)費(fèi)用采用prim算法構(gòu)造最小生成樹，［3］具體步驟如下。設(shè)置頂點(diǎn)集合V和邊集E，它們的初始狀態(tài)為空集;任意選取一個(gè)頂點(diǎn)A加入V中;重復(fù)以下過程直到V中已經(jīng)包含原圖的所有節(jié)點(diǎn):選一條權(quán)值最小的邊(U，V)，并使其滿足U，V兩節(jié)點(diǎn)只有一個(gè)在集合V中。將兩個(gè)節(jié)點(diǎn)中不在V的點(diǎn)置入集合V中，并將邊(U，V)加入邊集E中;所得的子圖G'=(V，E)即為所求的最小生成樹。

1．3結(jié)果分析。

利用Matlab軟件對(duì)模型進(jìn)行求解得到圖1，并利用Netdraw軟件對(duì)模型進(jìn)行求解得到圖2。

雖然方案實(shí)現(xiàn)了費(fèi)用最小化目標(biāo)，但仍存在以下幾點(diǎn)影響方案的可靠性:第一，某些重要節(jié)點(diǎn)沒有多重保障，例如節(jié)點(diǎn)2、35、27等等，一旦這些節(jié)點(diǎn)發(fā)生故障，則會(huì)造成大面積的節(jié)點(diǎn)失去通信的情況，以節(jié)點(diǎn)22為例，一旦22節(jié)點(diǎn)發(fā)生故障，整個(gè)體系的癱瘓概率為66．4%;第二，鋪設(shè)方案主要為鏈狀和樹狀結(jié)構(gòu)，結(jié)構(gòu)單一，缺少適當(dāng)?shù)沫h(huán)形結(jié)構(gòu)。環(huán)形結(jié)構(gòu)是指首尾相接的線形結(jié)構(gòu)，該結(jié)構(gòu)為環(huán)中任意兩個(gè)節(jié)點(diǎn)之間都提供了兩個(gè)通路，環(huán)形結(jié)構(gòu)本身就具有保護(hù)路由的功能，具有較好的可靠性。所以，該方案的可靠性不太理想，需要進(jìn)一步完善。

圖1 節(jié)點(diǎn)連接方案圖

圖2 鋪設(shè)方案圖

2 考慮通信網(wǎng)絡(luò)結(jié)點(diǎn)可靠性的通信網(wǎng)絡(luò)鋪設(shè)方案的制定

2．1研究思路。

研究網(wǎng)絡(luò)穩(wěn)定性的重要方法之一是計(jì)算網(wǎng)絡(luò)生成樹的個(gè)數(shù)。如果刪除某一節(jié)點(diǎn)造成網(wǎng)絡(luò)中生成樹的個(gè)數(shù)減少越多，該節(jié)點(diǎn)越重要。在研究1所得結(jié)果基礎(chǔ)上，對(duì)節(jié)點(diǎn)進(jìn)行分類，將與節(jié)點(diǎn)相連的鏈路的條數(shù)定義為度，則該結(jié)果的節(jié)點(diǎn)種類有1度、2度、3度、4度和5度五個(gè)種類。具體的節(jié)點(diǎn)分類情況見表1。

表1 節(jié)點(diǎn)分類表

對(duì)結(jié)點(diǎn)間能夠保持通信暢通的可靠性都達(dá)到90%進(jìn)行定義:如果一個(gè)節(jié)點(diǎn)i發(fā)生故障，其他節(jié)點(diǎn)間能夠保持兩兩通信通暢的節(jié)點(diǎn)個(gè)數(shù)Ui與總的兩兩之間需要保持通信暢通的總個(gè)數(shù)C2n的比例大于等于90%，設(shè)定該比例為Ri，即為:Ri=Ui/C2n，i=1，2…80。這里將該比例定義為可靠性比率。一般而言，度數(shù)越高，影響越大，可靠性比率越小。對(duì)這五種種類的點(diǎn)遍歷搜索，顯然1度節(jié)點(diǎn)可以不考慮，其對(duì)整體的影響較小，一度節(jié)點(diǎn)總數(shù)為32個(gè)，則只需要計(jì)算48個(gè)點(diǎn)的可靠性比率。最后，對(duì)于那些可靠性比率小于90%的點(diǎn)予以重點(diǎn)考慮，重新設(shè)計(jì)網(wǎng)絡(luò)結(jié)構(gòu)，在保證費(fèi)用最小的情況下使整體可靠性比率大于90%。將研究1所得的鋪設(shè)方案圖進(jìn)行區(qū)域劃分，分為M，N，P，Q四個(gè)區(qū)域，總體區(qū)域設(shè)為Ω，如圖3所示。

圖3 鋪設(shè)方案按照節(jié)點(diǎn)可靠性區(qū)域劃分圖

如果要重新設(shè)計(jì)通信網(wǎng)絡(luò)鋪設(shè)結(jié)構(gòu)，就應(yīng)該重點(diǎn)考慮故障危險(xiǎn)點(diǎn)的網(wǎng)絡(luò)鋪設(shè)，才能盡可能地實(shí)現(xiàn)整體的可靠性比率大于90%。

通信網(wǎng)絡(luò)重建的基本思路:①拓?fù)浣Y(jié)構(gòu)主要有五種:總線型拓?fù)?、星型拓?fù)洹h(huán)型拓?fù)?、樹型拓?fù)浜突旌闲屯負(fù)?，考慮到總線型拓?fù)?、星型拓?fù)浜蜆湫屯負(fù)淙N拓?fù)浣Y(jié)構(gòu)會(huì)使總費(fèi)用成本過高，而環(huán)型拓?fù)洳粌H能解決生成樹通信通暢的問題，而且會(huì)在一定范圍內(nèi)保證費(fèi)用較低。所以這里我們主要考慮環(huán)型拓?fù)浜突旌闲屯負(fù)浣Y(jié)構(gòu);②研究1所得鋪設(shè)方案里有三個(gè)主要的生成樹分支，即為三個(gè)區(qū)域，如若提高整體的可靠性比率，則新設(shè)的鏈路端點(diǎn)至少有3個(gè)分別分布在三個(gè)區(qū)域，其他端點(diǎn)可以分布于整個(gè)區(qū)域的任何位置，并且新設(shè)鏈路必須能夠覆蓋整個(gè)區(qū)域，才能保證一旦生成樹的分支發(fā)生故障，整體通信不受影響;③考慮到環(huán)型拓?fù)浜突旌闲屯負(fù)浣Y(jié)構(gòu)，則新設(shè)鏈路數(shù)應(yīng)該小于等于3條方能實(shí)現(xiàn)通信通暢且費(fèi)用盡可能小。則研究2主要解決的就是在保證費(fèi)用最少的基礎(chǔ)上，設(shè)計(jì)新設(shè)鏈路的節(jié)點(diǎn)(節(jié)點(diǎn)個(gè)數(shù)小于等于6個(gè))的位置分布問題。

2．2研究方法。

計(jì)算48個(gè)點(diǎn)可靠性比率，提取可靠性比率小于90%的節(jié)點(diǎn)，即為61，70，62，47，2，5，35，27，42，53，22，45，76，77，71，16，52，18，30，51，12這些點(diǎn)一旦發(fā)生故障，那么通信暢通的可靠性比率低于90%，這里將這些節(jié)點(diǎn)定義為故障危險(xiǎn)點(diǎn)。如果要重新設(shè)計(jì)通信網(wǎng)絡(luò)鋪設(shè)結(jié)構(gòu)，就應(yīng)該重點(diǎn)考慮故障危險(xiǎn)點(diǎn)的網(wǎng)絡(luò)鋪設(shè)，才能盡可能地實(shí)現(xiàn)整體的可靠性比率大于90%。建立如下模型:

在實(shí)際問題求解時(shí)，對(duì)區(qū)域進(jìn)行劃分，如圖4所示。

圖4 鋪設(shè)方案按照節(jié)點(diǎn)可靠性優(yōu)化區(qū)域劃分圖

將26、1、34、61、50、32劃為i區(qū)域，14、36、70、66、67、62、47、2、29、19、49、28、78、5、79、63、40、35、20、80、24、39、13、7、3、27、42、53、37、56為j區(qū)域，15、44、10、17、74、72、71、 11為m區(qū)域，77、23、75、64、6、57、76、45、54、22為n區(qū)域，30、38、31、59、60、48、4、58為q區(qū)域，剩下的劃分為p區(qū)域。利用matlab進(jìn)行編程算出最小費(fèi)用網(wǎng)絡(luò)鋪設(shè)區(qū)域分布。

表2 連接方案表

并用Netdraw軟件作圖，求得最小費(fèi)用為3054200元，具體的節(jié)點(diǎn)連接圖如圖5。

圖5 考慮節(jié)點(diǎn)可靠性的鋪設(shè)方案優(yōu)化圖

在通信網(wǎng)絡(luò)結(jié)點(diǎn)的可靠性求解過程中，假設(shè)連接各區(qū)域的鏈路數(shù)小于或等于3條，現(xiàn)對(duì)連接各區(qū)域的鏈路數(shù)進(jìn)行靈敏度分析，分析不同區(qū)域的鏈接鏈路數(shù)大小對(duì)總費(fèi)用的影響。

分析可知，當(dāng)連接各區(qū)域的鏈路數(shù)為4時(shí)，對(duì)應(yīng)5個(gè)鏈端點(diǎn)，將各鏈路端點(diǎn)所在區(qū)域進(jìn)行調(diào)整，分別計(jì)算不同調(diào)整類型所對(duì)應(yīng)的費(fèi)用，找到鏈路數(shù)為4時(shí)的最小費(fèi)用，同理，當(dāng)鏈路數(shù)為5，6，7，8，9時(shí)，用同樣方法得到最小費(fèi)用，將不同鏈路數(shù)對(duì)應(yīng)的最小費(fèi)用匯總，得表3。

表3 不同鏈路數(shù)對(duì)應(yīng)的最小費(fèi)用表

為了便于觀察鏈路數(shù)與最小費(fèi)用之間的關(guān)系，用excel畫出折線圖，得到圖6。

圖6 不同鏈路數(shù)對(duì)應(yīng)的最小費(fèi)用折線圖

結(jié)合表3、圖6的結(jié)果分析可知，連接各區(qū)域的鏈路數(shù)與最小費(fèi)用呈線性關(guān)系，當(dāng)連接各區(qū)域的鏈路數(shù)增加時(shí)，最小費(fèi)用也隨之增加;反之則減少。由此可知，當(dāng)連接各區(qū)域的鏈路數(shù)為2時(shí)，就能夠保持通信暢通的可能性都達(dá)到90%且達(dá)到最小費(fèi)用，鏈路數(shù)再增加，只會(huì)增加費(fèi)用，但是考慮實(shí)際情況，有時(shí)候可能會(huì)選擇多種鏈路數(shù)的結(jié)合來實(shí)現(xiàn)費(fèi)用與效率最優(yōu)。

3 考慮通信網(wǎng)絡(luò)鏈路可靠性的通信網(wǎng)絡(luò)鋪設(shè)方案的制定［4 ］

3．1研究思路。

假設(shè)通信網(wǎng)絡(luò)的80個(gè)節(jié)點(diǎn)全部絕對(duì)可靠，網(wǎng)絡(luò)結(jié)構(gòu)的可靠性僅僅考慮每條鏈路的可靠度，并且失效鏈路互相獨(dú)立，即為各條鏈路發(fā)生故障的情況互不影響。

首先，對(duì)通信暢通的結(jié)點(diǎn)都能夠達(dá)到90%進(jìn)行定義:即如果一條鏈路發(fā)生故障，其他節(jié)點(diǎn)間能夠保持兩兩通信通暢的節(jié)點(diǎn)個(gè)數(shù)ui與總的兩兩之間需要保持通信暢通的總個(gè)數(shù)的比例大于等于90%，即為2…80。其次，在研究1基本網(wǎng)絡(luò)鋪設(shè)方案的基礎(chǔ)上，采取同研究2一樣的思路，即提取那些使可靠性小于90%的鏈路，在保證分支生成樹盡可能不變的情況下，對(duì)這些鏈路進(jìn)行重新設(shè)計(jì)。［5］

3．2研究方法。

如圖7所示，對(duì)研究1所得基本網(wǎng)絡(luò)鋪設(shè)方案圖進(jìn)行區(qū)域劃分。將32、50、61、34、1、26、67、66、70、36、3、14劃分為P區(qū)域，62、69、47、2、29、19、49、28、5、35、20、80、24、39、79、63、40、27、3、7、13、42、53、37、56為Q區(qū)域，15、44、10、17、74、72、71、11、77、75、23、64、6、57為E區(qū)域，76、45、54、22為F區(qū)域，25、55、16、52、21、43、9、18為M區(qū)域，剩下部分是A區(qū)域。這五個(gè)區(qū)域?yàn)榫W(wǎng)絡(luò)鋪設(shè)方案圖的生成樹的主要分支部分。

剔除生成樹的分支，重點(diǎn)考慮剩下節(jié)點(diǎn)之間的連接。因?yàn)殒溌房煽啃苑治龊凸?jié)點(diǎn)可靠性分析不同，在對(duì)鏈路分析中，如果盡可能提高整體可靠性，則應(yīng)該使鏈路盡量成環(huán)或者聚集，即應(yīng)該盡可能地實(shí)現(xiàn)星型拓?fù)浜铜h(huán)型拓?fù)浣Y(jié)構(gòu)。并且在這兩種拓?fù)浣Y(jié)構(gòu)中，一個(gè)中心節(jié)點(diǎn)的連接的總節(jié)點(diǎn)數(shù)應(yīng)該小于等于8(因?yàn)榭偨Y(jié)點(diǎn)數(shù)為80，則80×10%=8)，才能盡可能實(shí)現(xiàn)可靠性大于90%。

根據(jù)分析，設(shè)度數(shù)超過1的節(jié)點(diǎn)所處的區(qū)域?yàn)镈，建立

如下模型:［6］

其中第一個(gè)約束條件表示的是每個(gè)節(jié)點(diǎn)至少有一個(gè)鏈路與之相連，第二個(gè)約束條件表示的是生成樹的所有分支的總節(jié)點(diǎn)數(shù)應(yīng)該小于等于8個(gè)，從而能保證整體的可靠性大于90%。

3．3結(jié)果分析。

在對(duì)連接方案進(jìn)行一一分析剔除之后，求得最少費(fèi)用為3047600元，使用Netdraw軟件進(jìn)行繪圖，得到圖7。

圖7 考慮鏈路可靠性的鋪設(shè)方案優(yōu)化圖

4 總結(jié)

本文針對(duì)通信網(wǎng)絡(luò)鏈路可靠性與結(jié)點(diǎn)可靠性的問題，通過有關(guān)數(shù)據(jù)分析，建立了相應(yīng)模型。首先結(jié)合prim算法，結(jié)合最小生成樹模型，設(shè)計(jì)出了鋪設(shè)費(fèi)用較少的鋪設(shè)方案，接著對(duì)重點(diǎn)結(jié)點(diǎn)與鏈路予以重點(diǎn)考慮，建立非線性規(guī)劃模型，對(duì)鋪設(shè)方案進(jìn)行區(qū)域劃分，重新設(shè)計(jì)出保證鏈路可靠性大于90%的鋪設(shè)方案優(yōu)化圖。本文對(duì)解決在盡量滿足總鋪設(shè)費(fèi)用最小和方案可靠性最大的條件下，設(shè)計(jì)理想通信網(wǎng)絡(luò)鋪設(shè)方案問題提出了建議，對(duì)該問題的繼續(xù)研究具有重要的參考價(jià)值。

［1］中國數(shù)學(xué)建模網(wǎng)［EB/OL］．http://www．shumo． com/home/html/2338．html，2014－11－10．

［2］陳國龍，郭文忠，涂雪珠，陳火旺求解多目標(biāo)最小生成樹問題的改進(jìn)算法［J］．軟件學(xué)報(bào)，2006(03)．

［3］楊成慧，殷紅，孟建軍，姜虎強(qiáng)．基于Prim算法的通信網(wǎng)絡(luò)架設(shè)仿真研究與應(yīng)用［J］．計(jì)算機(jī)仿真，2007(10)．

［4］劉曉娥，唐濤，萬麗軍，黃樟燦．基于鏈路可靠性的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)設(shè)計(jì)［J］．武漢理工大學(xué)學(xué)報(bào)(信息與管理工程版)，2002(3):18－24．

［5］孫慧麗．基于可靠性約束的網(wǎng)絡(luò)拓?fù)涠鄿?zhǔn)則滿意優(yōu)化研究［D］．成都:西南交通大學(xué)，2007．

［6］姜啟源，謝金星，葉?。?dāng)?shù)學(xué)模型［M］．北京:高等教育出版社，2003．

The establishment of communication network laying scheme based on minimum spanning tree model

Liu Yaqian1，Wang Changhai2，Zeng Shuxian2，Zhu Jiaming2
(Anhui University of Finance and Economics 1．School of Finance;2．School of Statistics and Applied Math，Bengbu，Anhui 233030，China)

Aimed at the communication network designing，after analyzing relevant data，this paper use the minimum spanning tree model and combine the prim algorithm，which makes the cost as lower as possible．Considering the reliability of communication network nodes and links respectively，this paper uses nonlinear programming model to ensure the number of smooth nodes of this communication network can reach 90%．

communication network，minimum spanning tree，nonlinear programming model，netdraw

TP393．02

A

1672－6758(2015)05－0029－5

(責(zé)任編輯:鄭英玲)

劉雅倩，學(xué)生，安徽財(cái)經(jīng)大學(xué)金融學(xué)院。研究方向:國際金融。

王昌海，學(xué)生，安徽財(cái)經(jīng)大學(xué)金融學(xué)院。研究方向:信息與計(jì)算科學(xué)。

曾淑嫻，學(xué)生，安徽財(cái)經(jīng)大學(xué)金融學(xué)院。研究方向:統(tǒng)計(jì)學(xué)。

朱家明，碩士，副教授，安徽財(cái)經(jīng)大學(xué)數(shù)學(xué)建模實(shí)驗(yàn)室。研究方向:應(yīng)用數(shù)學(xué)與數(shù)學(xué)建模。

國家自然科學(xué)基金(編號(hào):11301001);安徽財(cái)經(jīng)大學(xué)教研項(xiàng)目(編號(hào):acjyzd201429)。

Class No．:TP393．02 Document Mark:A