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

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

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

0 引言

對于一個系統(tǒng)，可靠性［1］是其重要的整體指標，通信網(wǎng)絡亦不例外.通信網(wǎng)絡的可靠性不僅與通信設備、鏈路有關，而且還與網(wǎng)絡結構有關.由于網(wǎng)絡結構的復雜多變，通信網(wǎng)絡的可靠性分析一直是個棘手的問題.某通信公司擬建一個具有80 個結點的通信網(wǎng)絡，需要在這些結點之間鋪設線路，進行數(shù)據(jù)傳輸.給出結點之間的距離和鋪設線路的單位費用，基于可靠性建立模型，給出最優(yōu)通信網(wǎng)絡設計(數(shù)據(jù)來源于文獻［2］).

1 最小總鋪設費用模型

1.1 研究思路

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

1.2 研究方法

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

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

1.3 研究結果

利用Kruskal 算法［4］求解:

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

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

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

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

表1 權值最小的前20 個數(shù)據(jù)對應節(jié)點

圖1 最小生成樹

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

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

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

2.1 研究思路

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

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

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)任意一個結點出現(xiàn)故障時，其它結點間仍然能夠保持通信暢通的可能性都達到90%這一目標.

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

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

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

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

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

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

2.3 研究結果

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

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

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

3 研究鏈路可靠性

3.1 研究思路

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

3.2 研究方法

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

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

圖5 鏈路可靠性下鋪設費用最少

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

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

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

3.3 研究結果

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

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

4 確定合理鋪設方案

4.1 研究思路

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

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

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

表4 最少鋪設費用鏈路

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

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

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

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

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

表5 最少鋪設費用鏈路

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

5 結語

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

［1］張品，董志遠，沈政.基于網(wǎng)絡拓撲評估網(wǎng)絡可靠性的新算法［J］.計算機系統(tǒng)應用，2012，21(12):99－100.

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

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

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

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

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