基于可靠性通信網(wǎng)絡(luò)設(shè)計的探究

朱國燕，朱家明，翟 浩，吳秀盟

(安徽財經(jīng)大學(xué)a.金融學(xué)院;b.統(tǒng)計與應(yīng)用數(shù)學(xué)學(xué)院 安徽 蚌埠233030)

0 引言

對于一個系統(tǒng)，可靠性［1］是其重要的整體指標(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ò)的可靠性分析一直是個棘手的問題.某通信公司擬建一個具有80 個結(jié)點的通信網(wǎng)絡(luò)，需要在這些結(jié)點之間鋪設(shè)線路，進(jìn)行數(shù)據(jù)傳輸.給出結(jié)點之間的距離和鋪設(shè)線路的單位費用，基于可靠性建立模型，給出最優(yōu)通信網(wǎng)絡(luò)設(shè)計(數(shù)據(jù)來源于文獻(xiàn)［2］).

1 最小總鋪設(shè)費用模型

1.1 研究思路

采用圖論中最小生成樹［3］的理論，先將實際問題抽象為圖論模型，計算出各節(jié)點之間的運費，再使用Kruskal 算法，借助Matlab 軟件，得到總鋪設(shè)費用最省的鋪設(shè)方案.最后對方案的可靠性進(jìn)行討論.

1.2 研究方法

在通信網(wǎng)絡(luò)的設(shè)計中，我們將每個節(jié)點用一個點表示，則得頂點集合V={v1，v2，…，v80}，若某用戶和另一用戶之間有線路相連則我們將這兩點之間連上一條邊，邊集合即為E={eij=(vi，vj|vi，vj∈V)}.這樣就利用點和邊將通信網(wǎng)絡(luò)抽象成圖論當(dāng)中的圖，我們將其記為G(V，E).對于圖G(V，E)的每條邊eij=(vi，vj)的權(quán)值Wij，我們就用節(jié)點之間的鋪設(shè)費用來表示.這樣，要研究通信網(wǎng)絡(luò)的最優(yōu)鋪設(shè)問題，我們只需要在由實際問題抽象成的賦權(quán)圖G(V，E)上研究即可.

利用最小生成樹的理論，可以得到最優(yōu)的鋪設(shè)方案，即為求此圖G 的最小權(quán)值的生成樹.

1.3 研究結(jié)果

利用Kruskal 算法［4］求解:

(1)首先計算出各節(jié)點之間的鋪設(shè)費用:

將連通圖G 中的所有邊按權(quán)值(即鋪設(shè)費用)遞增(或非減)的次序排列，取權(quán)值最小的前120 個數(shù)據(jù)，這里列出前20 個作為范例.對應(yīng)節(jié)點見表1.

(2)選取權(quán)值最小(即鋪設(shè)費用最小)的邊為樹枝，這里選取節(jié)點10 連接到節(jié)點44，然后從G 中所有留下邊中選取與前次選取的諸邊不構(gòu)成回路的另一條最短邊，如有幾條權(quán)值相同的邊，可依次選取;

(3)這樣繼續(xù)下去，一直選夠79 條邊，得到的最小生成樹見圖1.

表1 權(quán)值最小的前20 個數(shù)據(jù)對應(yīng)節(jié)點

圖1 最小生成樹

圖2 三個主要枝干及區(qū)域

由圖1計算得最小運費為3，300，500 元.

2 研究節(jié)點可靠性

2.1 研究思路

要實現(xiàn)任意一個結(jié)點出現(xiàn)故障時，其它結(jié)點間仍然能夠保持通信暢通的可能性都達(dá)到90%這一目標(biāo)，即要保證任何一個節(jié)點被破壞時，最多只能有8 個節(jié)點失效.在問題一的基礎(chǔ)上，根據(jù)問題一得出的最優(yōu)鋪設(shè)方案，對圖1中的最小生成樹進(jìn)行分析，發(fā)現(xiàn)該最小生成樹有三個主要枝干，依次在三個主要枝干上從樹葉開始計數(shù)，找到位于枝干上的一個關(guān)鍵點，并以它為分界點.把位于分界點樹葉一端的節(jié)點設(shè)為一個區(qū)域，這樣就得到三個區(qū)域.

只要連通這三個區(qū)域，就能實現(xiàn)節(jié)點可靠性目標(biāo).然后利用Matlab 軟件［5］，找出連接這三個區(qū)域的、鋪設(shè)費用最小兩條鏈路，這樣既能實現(xiàn)可靠性目標(biāo)并得到費用最省的鋪設(shè)方案.

2.2 研究方法

圖1中最小生成樹有三個主要枝干，將其命名為第一主枝干、第二主枝干、第三主枝干，見圖2.

在第一主枝干上從樹葉端開始計數(shù)，通過分析找出分界點，它是V22，并將分界點的樹葉端節(jié)點所在區(qū)域命名為區(qū)域I.同理，在第二主枝干上的分界點是V35，分界點的樹葉端節(jié)點所在區(qū)域命名為區(qū)域II.第三主枝干的分界點是V70，分界點的樹葉端節(jié)點所在區(qū)域為區(qū)域III.各區(qū)域的節(jié)點分布見表2:

表2 各區(qū)域節(jié)點分布

只要連通這三個區(qū)域，就能實現(xiàn)任意一個結(jié)點出現(xiàn)故障時，其它結(jié)點間仍然能夠保持通信暢通的可能性都達(dá)到90%這一目標(biāo).

為了得到總鋪設(shè)費用最少的鋪設(shè)方案，只需連通三個區(qū)域的路線的鋪設(shè)費用最少即可.設(shè)vaibj表示第a 個區(qū)域第i 個節(jié)點與第b 個區(qū)域第j 個節(jié)點之間的距離，其單位鋪設(shè)費用為cij，鋪設(shè)費用為waibj，則:

按下述步驟找出鋪設(shè)費用最小的鋪設(shè)方案:

Step1:求區(qū)域I 與區(qū)域II 之間的最小鋪設(shè)費用min(w1i2j);

Step2:求區(qū)域I 與區(qū)域III 之間的最小鋪設(shè)費用min(w1i3j);

Step3:求區(qū)域II 與區(qū)域III 之間的最小鋪設(shè)費用min(w2i3j);

Step4:選取min(w1i2j)、min(w1i3j)、min(w2i3j)中最小的兩個，連接對應(yīng)節(jié)點，得到鋪設(shè)費用最少的鋪設(shè)方案.

2.3 研究結(jié)果

用Matlab 軟件尋找鋪設(shè)費用最少的鋪設(shè)方案，得到鋪設(shè)費用最小的為連接區(qū)域I 中節(jié)點v64到區(qū)域II中節(jié)點v57的線路，鋪設(shè)費用為70，300 元，緊接著為連接區(qū)域I 中節(jié)點v54到區(qū)域III 中節(jié)點v34的線路，鋪設(shè)費用為77，000 元.總的通信網(wǎng)絡(luò)設(shè)計見圖3:

由圖3計算得當(dāng)實現(xiàn)任意一個結(jié)點出現(xiàn)故障時，其它結(jié)點間仍然能夠保持通信暢通的可能性都達(dá)到90% 時，最少鋪設(shè)費用為3，447，800 元.

圖3 節(jié)點可靠性下鋪設(shè)費用最少

3 研究鏈路可靠性

3.1 研究思路

與問題二類似，在問題一的基礎(chǔ)上，根據(jù)問題一得出的最優(yōu)鋪設(shè)方案，對圖1中的最小生成樹進(jìn)行分析，找出分界鏈路，再劃分區(qū)域，這樣就得到三個區(qū)域，只要連通這三個區(qū)域，就能實現(xiàn)鏈路可靠性目標(biāo).然后利用Matlab 軟件，找出連接這三個區(qū)域的、鋪設(shè)費用最小兩條鏈路，這樣既能實現(xiàn)任意一條鏈路被破壞時，能夠保持通信暢通的結(jié)點都能夠達(dá)到90%這一目標(biāo)，也得到了總鋪設(shè)費用最少的鋪設(shè)方案.

3.2 研究方法

從三個主枝干樹葉端開始計數(shù)，通過分析找出分界鏈路，再將分界鏈路樹葉端的區(qū)域分別劃分為區(qū)域I、區(qū)域II、區(qū)域III，分界鏈路及區(qū)域劃分見圖4:

圖4 分界鏈路及區(qū)域劃分圖

圖5 鏈路可靠性下鋪設(shè)費用最少

各區(qū)域節(jié)點分布見表3:

表3 各區(qū)域節(jié)點分布

只要連通這三個區(qū)域，就能實現(xiàn)任意一條鏈路被破壞時，能夠保持通信暢通的結(jié)點都能夠達(dá)到90%這一目標(biāo).

3.3 研究結(jié)果

按問題二中步驟找出連通三個區(qū)域的、鋪設(shè)費用最少的鏈路，用Matlab 求解，得到費用最少的鏈路是區(qū)域I 22?區(qū)域II 53，鋪設(shè)費用為43，200 元;其次是區(qū)域II 40?區(qū)域III 66，鋪設(shè)費用為43，500 元.總的通信網(wǎng)絡(luò)設(shè)計見圖5.

由圖5計算得當(dāng)實現(xiàn)任意一條鏈路被破壞時，能夠保持通信暢通的結(jié)點都能夠達(dá)到90%時，最少鋪設(shè)費用為3，387，200 元.

4 確定合理鋪設(shè)方案

4.1 研究思路

綜合上述問題，將可靠性提高到95%，考慮兩種情況.第一，任意一個節(jié)點被破壞時，能夠保持通信暢通的結(jié)點都能夠達(dá)到95%;第二，任意一條鏈路被破壞時，能夠保持通信暢通的結(jié)點都能夠達(dá)到95%.在此前提下求解鋪設(shè)費用最少的通信網(wǎng)絡(luò)設(shè)計.分析方法與問題二和問題三類似，但是劃分區(qū)域與各區(qū)域節(jié)點的數(shù)目有所不同.

4.2 任意一個節(jié)點被破壞的情況

要實現(xiàn)任意一個結(jié)點出現(xiàn)故障時，其它結(jié)點間仍然能夠保持通信暢通的可能性都達(dá)到95%這一目標(biāo)，即要保證任何一個節(jié)點被破壞時，最多只能有4 個節(jié)點失效.采用與問題二相同的研究方法，得到七個區(qū)域，借助Matlab 軟件，找出連通這七個區(qū)域的、鋪設(shè)費用最少的鏈路，結(jié)果見表4:

表4 最少鋪設(shè)費用鏈路

我們在圖1的基礎(chǔ)上新增了五條鏈路，莽總的通信網(wǎng)絡(luò)設(shè)計見圖6.

圖6 一個節(jié)點被破壞下最少鋪設(shè)費用

圖7 一條鏈路被破壞下最少鋪設(shè)費用

由圖6計算得當(dāng)實現(xiàn)任意一個結(jié)點出現(xiàn)故障時，其它結(jié)點間仍然能夠保持通信暢通的可能性都達(dá)到95%時，最少鋪設(shè)費用為3，795，800 元.4.3 任意一條鏈路被破壞的情況

要實現(xiàn)任意一條鏈路出現(xiàn)故障時，能夠保持通信暢通的結(jié)點都能夠達(dá)到95%這一目標(biāo)，即要保證任何一個節(jié)點被破壞時，最多只能有4 個節(jié)點失效.采用與問題三相同的研究方法，得到七個區(qū)域，借助Matlab 軟件，找出連通這七個區(qū)域的、鋪設(shè)費用最少的鏈路，結(jié)果見表5:

表5 最少鋪設(shè)費用鏈路

我們在圖1的基礎(chǔ)上新增了六鏈路.總的通信網(wǎng)絡(luò)設(shè)計見圖7.由圖7計算得當(dāng)實現(xiàn)任意一條鏈路被破壞時，能夠保持通信暢通的結(jié)點都能夠達(dá)到95%時，最少鋪設(shè)費用為3，635，500 元.

5 結(jié)語

本文根據(jù)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，基于可靠性設(shè)計通信網(wǎng)絡(luò)，運用貪心算法得到運費最小的通信網(wǎng)絡(luò)設(shè)計.運用多種數(shù)據(jù)統(tǒng)計方法，巧妙結(jié)合圖形，緊密聯(lián)系實際，得到的結(jié)果全面可靠.本文運用的貪心算法［6］及其求解方法還可以推廣到其它領(lǐng)域，如快遞運輸問題，具有很強的適用性.

［1］張品，董志遠(yuǎn)，沈政.基于網(wǎng)絡(luò)拓?fù)湓u估網(wǎng)絡(luò)可靠性的新算法［J］.計算機系統(tǒng)應(yīng)用，2012，21(12):99－100.

［2］安徽財經(jīng)大學(xué)統(tǒng)計與應(yīng)用數(shù)學(xué)學(xué)院.2014年安徽財經(jīng)大學(xué)數(shù)學(xué)建模模擬題［OL］.(2014－10－23)［2014－07－16］.http://zhujm1973.blog.163.com/blog/static/315513552014923288768/.

［3］程遠(yuǎn).網(wǎng)絡(luò)最小生成樹更新策略［J］.計算機與現(xiàn)代化，2012，202(6):125－130.

［4］王偉，孟思燕.Kruskal 算法的研究與改進(jìn)［J］.重慶文理學(xué)院學(xué)報，2010，29(3):25－27;32.

［5］吳禮斌，閆云俠.經(jīng)濟數(shù)學(xué)實驗與建模［M］.天津:天津大學(xué)出版社，2009.

［6］楊桂元，朱家明.數(shù)學(xué)建模競賽優(yōu)秀論文評析［M］.合肥:中國科技大學(xué)出版社，2013.