朱國(guó)燕，朱家明，翟 浩，吳秀盟

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

0 引言

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

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

1.1 研究思路

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

1.2 研究方法

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

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

1.3 研究結(jié)果

利用Kruskal 算法［4］求解:

(1)首先計(jì)算出各節(jié)點(diǎn)之間的鋪設(shè)費(fèi)用:

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

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

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

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

圖1 最小生成樹

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

由圖1計(jì)算得最小運(yùn)費(fèi)為3，300，500 元.

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

2.1 研究思路

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

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

2.2 研究方法

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

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

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

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

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

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

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

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

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

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

2.3 研究結(jié)果

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

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

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

3 研究鏈路可靠性

3.1 研究思路

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

3.2 研究方法

從三個(gè)主枝干樹葉端開(kāi)始計(jì)數(shù)，通過(guò)分析找出分界鏈路，再將分界鏈路樹葉端的區(qū)域分別劃分為區(qū)域I、區(qū)域II、區(qū)域III，分界鏈路及區(qū)域劃分見(jiàn)圖4:

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

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

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

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

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

3.3 研究結(jié)果

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

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

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

4.1 研究思路

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

4.2 任意一個(gè)節(jié)點(diǎn)被破壞的情況

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

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

我們?cè)趫D1的基礎(chǔ)上新增了五條鏈路，莽總的通信網(wǎng)絡(luò)設(shè)計(jì)見(jiàn)圖6.

圖6 一個(gè)節(jié)點(diǎn)被破壞下最少鋪設(shè)費(fèi)用

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

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

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

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

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

5 結(jié)語(yǔ)

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

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

［2］安徽財(cái)經(jīng)大學(xué)統(tǒng)計(jì)與應(yīng)用數(shù)學(xué)學(xué)院.2014年安徽財(cái)經(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］.計(jì)算機(jī)與現(xiàn)代化，2012，202(6):125－130.

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

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

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