通信網(wǎng)絡結(jié)點設計問題的研究

1、承 諾 書我們仔細閱讀了全國大學生數(shù)學建模競賽章程和全國大學生數(shù)學建模競賽參賽規(guī)則（以下簡稱為“競賽章程和參賽規(guī)則”，可從全國大學生數(shù)學建模競賽網(wǎng)站下載）。我們完全明白，在競賽開始后參賽隊員不能以任何方式（包括電話、電子郵件、網(wǎng)上咨詢等）與隊外的任何人（包括指導教師）研究、討論與賽題有關(guān)的問題。我們知道，抄襲別人的成果是違反競賽章程和參賽規(guī)則的，如果引用別人的成果或其他公開的資料（包括網(wǎng)上查到的資料），必須按照規(guī)定的參考文獻的表述方式在正文引用處和參考文獻中明確列出。我們鄭重承諾，嚴格遵守競賽章程和參賽規(guī)則，以保證競賽的公正、公平性。如有違反競賽章程和參賽規(guī)則的行為，我們將受到嚴肅處理。我們授

2、權(quán)全國大學生數(shù)學建模競賽組委會，可將我們的論文以任何形式進行公開展示（包括進行網(wǎng)上公示，在書籍、期刊和其他媒體進行正式或非正式發(fā)表等）。我們參賽選擇的題號是（從A/B/C/D中選擇一項填寫）： 我們的參賽報名號為（如果賽區(qū)設置報名號的話）： 所屬學校（請?zhí)顚懲暾娜?參賽隊員 (打印并簽名) ：1. 2. 3. 指導教師或指導教師組負責人 (打印并簽名)： （論文紙質(zhì)版與電子版中的以上信息必須一致，只是電子版中無需簽名。以上內(nèi)容請仔細核對，提交后將不再允許做任何修改。如填寫錯誤，論文可能被取消評獎資格。） 日期： 2014 年 9 月 2 日賽區(qū)評閱編號（由賽區(qū)組委會評閱前進行編號）：編

3、 號 專 用 頁賽區(qū)評閱編號（由賽區(qū)組委會評閱前進行編號）：賽區(qū)評閱記錄（可供賽區(qū)評閱時使用）：評閱人評分備注全國統(tǒng)一編號（由賽區(qū)組委會送交全國前編號）：全國評閱編號（由全國組委會評閱前進行編號）：通信網(wǎng)絡結(jié)點設計問題的研究摘要本文針對通信網(wǎng)絡結(jié)點之間鋪設線路的設計問題進行研究，以提高網(wǎng)絡的可靠性以及使鋪設費用最少為最終目的，得出了切實可行的方案。針對問題一，首先利用通信網(wǎng)絡結(jié)點之間的距離和鋪設線路的單位費用，求出各個結(jié)點之間的鋪設總費用。然后根據(jù)最短距離的思想，以各個結(jié)點間的鋪設總費用作為圖邊的權(quán)值，通過建立網(wǎng)絡鋪設模型，利用Prim算法，求出最小生成樹。根據(jù)得出的最小生成樹，進而得出最少鋪

4、設該通信網(wǎng)絡的費用為2947800元。最后在所得的網(wǎng)絡結(jié)構(gòu)的基礎(chǔ)上，結(jié)合總鋪設費用進一步討論方案的可靠性為1.235%。針對問題二，首先找出無論是哪個結(jié)點出現(xiàn)故障，都能保持通信暢通達到90%的點，再將這些找出來的點進行剔除。然后建立結(jié)點可靠性模型，利用Matlab編程，對剩下結(jié)點通過增加鏈路進行改進，以構(gòu)成環(huán)的方式使得網(wǎng)絡的可靠性達到90%以上。最后根據(jù)改進后的網(wǎng)絡結(jié)構(gòu)圖求出總鋪設費用為3783700元。針對問題三，首先任意找出一條鏈路使之出現(xiàn)故障，判斷故障鏈路所形成的子網(wǎng)絡是否能夠保持通信暢通的結(jié)點都能夠達到90%的要求。通過區(qū)分重要子網(wǎng)絡與非重要子網(wǎng)絡，從而得出斷鏈結(jié)點集。然后建立鏈路可靠

5、性模型，利用Matlab編程，從而確定需要增加的鏈路數(shù)為2條。以構(gòu)成環(huán)的方式使得網(wǎng)絡的可靠性達到90%以上。最后根據(jù)增加鏈路后的網(wǎng)絡結(jié)構(gòu)圖求出最少總鋪設費用為3056600元。針對問題四，要求綜合考慮網(wǎng)絡的可靠性以及鋪設費用，根據(jù)網(wǎng)絡可靠性的評估模型和網(wǎng)絡可靠性及其代價模型，可完成網(wǎng)絡可靠性的優(yōu)化設計。從而采用加權(quán)或效用系數(shù)法來建立多目標規(guī)劃問題的網(wǎng)絡優(yōu)化模型，并采用將傳統(tǒng)的啟發(fā)式算法與演化算法混和使用來進行求解，利用Matlab編程，從而得到最少費用為3420150元，以及網(wǎng)絡結(jié)構(gòu)圖。本文最后還對模型進行了誤差分析，模型的改進，并恰當?shù)貙δＰ瓦M行了評價。還從實際出發(fā)，對模型進行了相應的推廣。

6、關(guān)鍵詞：通信網(wǎng)絡 Prim算法 Matlab編程 可靠性代價模型 多目標規(guī)劃一、問題重述1.1背景知識1.1.1通信網(wǎng)絡人們的信息交流從語言、文字、印刷、電報、電話一直到今日的多姿多彩的現(xiàn)代通信。當今現(xiàn)代通信網(wǎng)絡正向數(shù)字化、智能化、綜合化、寬帶化、個人化邁進。隨著我國社會經(jīng)濟的發(fā)展、科學技術(shù)的進步，通信網(wǎng)絡技術(shù)也得到長久的發(fā)展1。傳統(tǒng)的通信網(wǎng)絡（即電話交換的網(wǎng)絡）是由傳輸、交換和終端三大部分組成。傳輸是傳送信息的媒體，交換（主要是指交換機）是各種終端交換信息的中介體。終端是指用戶使用的話機、手機、傳真機和計算機等。而現(xiàn)代電信網(wǎng)是由專業(yè)機構(gòu)以通信設備（硬件）和相關(guān)工作程序（軟件）有機建立的通信系

7、統(tǒng)，為個人、企事業(yè)單位和社會提供各類通信服務的總和。1.1.2 通信網(wǎng)絡的可靠性通信網(wǎng)絡的可靠性在通信網(wǎng)絡管理及決策中發(fā)揮著重要作用。通信網(wǎng)絡的可靠性不僅與通信設備、鏈路有關(guān)，而且還與網(wǎng)絡結(jié)構(gòu)有關(guān)。傳統(tǒng)的通信網(wǎng)絡可靠性分析和評估方法大多只考慮了某一方面性能或指標，無法全面準確地進行評估。由于網(wǎng)絡結(jié)構(gòu)的復雜多變，通信網(wǎng)絡的可靠性分析一直是個棘手的問題2。那么，如何綜合考慮網(wǎng)絡的可靠性以及鋪設費用，確定合理的鋪設方案也成為很多通信公司面臨的一大難題。1.2相關(guān)數(shù)據(jù)（1）通信網(wǎng)絡結(jié)點之間的距離（詳見原題附件1）；（2）通信網(wǎng)絡結(jié)點之間鋪設線路的單位費用（詳見原題附件1）。1.3要解決的問題1.3.1

8、問題一要使得通信網(wǎng)絡的總鋪設費用最省，請建立問題的數(shù)學模型，設計求解算法，給出鋪設方案，并討論方案的可靠性。1.3.2問題二考慮到通信網(wǎng)絡結(jié)點的可靠性，若要求任意一個結(jié)點出現(xiàn)故障時，其它結(jié)點間仍然能夠保持通信暢通的可能性都達到90%，請建立問題的數(shù)學模型，設計求解算法，并給出使總鋪設費用最少的鋪設方案。1.3.3問題三考慮到通信網(wǎng)絡鏈路的可靠性，若要求任意一條鏈路被破壞時，能夠保持通信暢通的結(jié)點都能夠達到90%，請建立問題的數(shù)學模型，設計求解算法，并給出使總鋪設費用最少的鋪設方案。1.3.4問題四綜合考慮網(wǎng)絡的可靠性以及鋪設費用，確定合理的鋪設方案。二、問題分析2.1 問題的總分析問題主要圍繞

9、在要使得通信網(wǎng)絡的總鋪設費用最省以及方案的可靠性討論上，先分別考慮結(jié)點和鏈路對通信網(wǎng)絡結(jié)構(gòu)的影響，建立出合適的數(shù)學模型，求得各自的鋪設方案。然后再綜合考慮結(jié)點和鏈路的總影響，以得到最佳的鋪設方案。2.2 對具體問題的分析2.2.1對問題一的分析問題一要求使得通信網(wǎng)絡的總鋪設費用最省，首先利用通信網(wǎng)絡結(jié)點之間的距離和鋪設線路的單位費用，求出各個結(jié)點之間的鋪設總費用。然后根據(jù)最短距離的思想，以各個結(jié)點間的鋪設總費用作為圖邊的權(quán)值，通過建立網(wǎng)絡鋪設模型，利用Prim算法，求出最小生成樹。根據(jù)得出的最小生成樹，進而得出最少鋪設該通信網(wǎng)絡的費用。最后在所得的網(wǎng)絡結(jié)構(gòu)的基礎(chǔ)上，結(jié)合總鋪設費用進一步討論方案

10、的可靠性。2.2.2對問題二的分析問題二實際上是要在問題一的基礎(chǔ)上加以改進。要求任意一個結(jié)點出現(xiàn)故障時，其它結(jié)點間仍然能夠保持通信暢通的可能性都達到90%。首先找出無論是哪個結(jié)點出現(xiàn)故障，都能保持通信暢通達到90%的點，將找出來的點進行剔除。然后建立結(jié)點可靠性模型，利用Matlab編程，對剩下結(jié)點通過增加鏈路進行改進，以構(gòu)成環(huán)的方式使得網(wǎng)絡的可靠性達到90%以上。最后根據(jù)改進后的網(wǎng)絡結(jié)構(gòu)圖求出總鋪設費用。2.2.3對問題三的分析問題三要求任意一條鏈路被破壞時，能夠保持通信暢通的結(jié)點都能夠達到90%，并且網(wǎng)絡連接所花費的費用要最少。由于任意一條鏈路出現(xiàn)故障之后，原來的最小生成樹網(wǎng)絡就將斷成兩個或

11、多個子網(wǎng)絡，如果子網(wǎng)絡中所包含的結(jié)點數(shù)大于或等于72，則該網(wǎng)絡能滿足任意一條鏈路被破壞后，能夠保持通信暢通的結(jié)點都能夠達到90%的要求。問題轉(zhuǎn)化為求鏈路被破壞后，最大子網(wǎng)絡之外的所有子網(wǎng)絡的結(jié)點總數(shù)不能超過8。最后可通過增加的鏈路，即可求出最少的鋪設費用。2.2.4對問題四的分析問題四要求綜合考慮網(wǎng)絡的可靠性以及鋪設費用，并確定合理的鋪設方案。由上述幾問可知本文網(wǎng)絡的可靠性是指網(wǎng)絡節(jié)點的可靠性，網(wǎng)絡鏈路的可靠性以及網(wǎng)絡拓撲結(jié)構(gòu)的可靠性。本文主要考慮網(wǎng)絡節(jié)點的可靠性和鏈路的可靠性。網(wǎng)絡的優(yōu)化設計關(guān)鍵在于網(wǎng)絡的可靠性要高,并且網(wǎng)絡設計費用要低?？捎靡环N基于鏈路的網(wǎng)絡優(yōu)化模型并運用演化算法來求解。該

12、方法能夠?qū)W(wǎng)絡的可靠性給出評價。三、模型假設（1）假設兩個結(jié)點之間的費用僅由單位費用和距離決定的；（2）假設通信網(wǎng)絡結(jié)構(gòu)只與結(jié)點和鏈路有關(guān)，不考慮其他因素的影響；（3）假設出故障時，有且只有一個結(jié)點或一條鏈路出故障，其他結(jié)點或鏈路保持暢通；（4）假設80個結(jié)點中，任意兩個結(jié)點都可以連接；（5）假設任意鏈路之間相互獨立，即一條鏈路的可靠性不會影響其他鏈路。四、名詞解釋與符號說明4.1 名詞解釋1. 通信度對于含有80個結(jié)點的網(wǎng)絡圖，若某一個結(jié)點出現(xiàn)故障，即將該結(jié)點剔除后，剩下網(wǎng)絡的結(jié)點對數(shù)與總的網(wǎng)絡結(jié)點對數(shù)的比值。2. 重要子網(wǎng)絡有且只有一條鏈路被破壞后，被分成的子網(wǎng)絡中含結(jié)點最多的那個子網(wǎng)絡的

13、結(jié)點數(shù)不能小于72，將該子網(wǎng)絡稱為重要子網(wǎng)絡，剩下結(jié)點數(shù)所組成的網(wǎng)絡為非重要子網(wǎng)絡。3. 斷鏈結(jié)點集將重要子網(wǎng)絡與非重要子網(wǎng)絡連接的結(jié)點與重要子網(wǎng)絡所鏈接的鏈路稱為重要斷鏈，若重要斷鏈出現(xiàn)故障之后剩下的相對結(jié)點較少的結(jié)點集合稱為斷鏈結(jié)點集。4.2 符號說明 表示通信網(wǎng)絡的總鋪設費用表示第個結(jié)點的通信度表示0、1變量，0表示該路徑未被選入，1表示路徑被選入表示網(wǎng)絡結(jié)點的可靠性表示最小路的可靠性表示連通圖中每個連通分支中的結(jié)點數(shù)表示刪除后總的不連通結(jié)點對數(shù)表示增加鏈路后的最少費用表示新增加鏈路的費用表示增加鏈路之后的最少費用 表示節(jié)點的串長表示一個網(wǎng)絡的代價五、模型的建立與求解5.1 問題一：網(wǎng)絡

14、鋪設模型5.1.1 建模思路要使得通信網(wǎng)絡的總鋪設費用最省，首先利用通信網(wǎng)絡結(jié)點之間的距離和鋪設線路的單位費用，求出各個結(jié)點之間的鋪設總費用。然后根據(jù)最短距離的思想，以各結(jié)點間的鋪設總費用作為圖邊的權(quán)值，通過Prim算法，求出最小生成樹。根據(jù)得出的最小生成樹，進而得出最少鋪設費用。最后根據(jù)總鋪設費用進一步討論方案的可靠性。5.1.2 建模準備Prim算法3Prim算法用于求無向圖的最小生成樹，設圖，其生成樹的頂點集合為。 把放入。 在所有的邊中找一條最小權(quán)值的邊，加入生成樹。 把找到的邊的加入集合。如果集合已有n個元素，則結(jié)束。否則繼續(xù)執(zhí)行。其算法的時間復雜度為。5.1.3 模型的建模與求解通

15、信網(wǎng)用圖來表示，假設為無自環(huán)圖（可以為連通圖也可以是非連通圖），有n個定點，m條邊。代表頂點的集合，圖的頂點對應網(wǎng)絡的結(jié)點；代表邊的集合，圖的邊對應著網(wǎng)絡的通信鏈路，網(wǎng)絡中n個結(jié)點之間不能夠相互備份，也沒有多余的備份結(jié)點，網(wǎng)絡拓撲結(jié)構(gòu)固定不變。網(wǎng)絡中的結(jié)點只有兩種工作狀態(tài)：正常和失效。網(wǎng)絡中每個結(jié)點的故障發(fā)生時相互獨立的，網(wǎng)絡中的鏈路不發(fā)生故障，但是當網(wǎng)絡中某個結(jié)點失效時，與該結(jié)點相關(guān)聯(lián)的所有鏈路同時失效。為了建立一個最優(yōu)的網(wǎng)絡鋪設模型，首先僅考慮鋪設成本對最終路線的影響，根據(jù)前面的假設，鋪設成本與鋪設長度與兩點間的費用單價有關(guān)。這樣問題就轉(zhuǎn)化成求解一個保證連通性的最小費用鋪設方案。由于結(jié)點間

16、的距離和單位距離間的費用是已知的，首先構(gòu)造結(jié)點費用矩陣，矩陣中第行列的元素值就是結(jié)點到結(jié)點的最小費用。為了表達結(jié)點之間的聯(lián)系，根據(jù)費用矩陣，轉(zhuǎn)化成無向賦權(quán)聯(lián)通圖。為求解最少費用，問題抽象為求解這個完全圖的最小生成樹。對于賦權(quán)連通圖,為頂點，為邊，為圖的有權(quán)矩陣。引入一個0、1變量，0表示該路徑未被選入，1表示路徑被選入。則數(shù)學模型如下：根據(jù)基本模型的目標函數(shù)和約束條件，先把費用矩陣轉(zhuǎn)換成全連通圖，根據(jù)圖論可以利用Prim算法，并通過Matlab編程，求出最小生成樹。如圖1:圖1 最小生成樹圖由此可知：元。通信網(wǎng)絡的可靠性是指系統(tǒng)在規(guī)定的條件下、規(guī)定的時間內(nèi)完成指定功能的能力。網(wǎng)絡的可靠性就是數(shù)

17、據(jù)傳輸節(jié)點，數(shù)據(jù)傳輸線路、拓撲結(jié)構(gòu)的可靠度。對于給定的一個網(wǎng)絡它包含3個部分,即結(jié)點。連接結(jié)點之間的鏈路和拓撲結(jié)構(gòu)。任意一個網(wǎng)絡的可靠性與結(jié)點、鏈路和網(wǎng)絡的拓撲結(jié)構(gòu)有關(guān)。網(wǎng)絡的可靠性同的可靠性關(guān)系如下:表明鏈路、結(jié)點的可靠性越高,網(wǎng)絡的拓撲結(jié)構(gòu)的連通性越高。由此網(wǎng)絡的可靠性就越高。在計算網(wǎng)絡的可靠性時,為處理問題的方便,對結(jié)點和鏈路的可靠性可作出以下假設:任一結(jié)點的可靠性相同；無向鏈路2個方向的可靠性相同；任意鏈路之間相互獨立，即一條鏈路的可靠性不會影響其他鏈路。網(wǎng)絡拓撲可靠性的評價可用多種方法，但最終的目的是要比較網(wǎng)絡可靠性的優(yōu)劣。一個網(wǎng)絡的可靠性可定義成所有結(jié)點對之間可靠性的平均值。在一個

18、有n結(jié)點網(wǎng)絡中有個結(jié)點對，顯然最小路是從結(jié)點到結(jié)點的鏈路序，并且從這個鏈路序中除去任意一條鏈路后就不是從結(jié)點到結(jié)點的路。由以上分析可知,要求一個復雜網(wǎng)絡的可靠性關(guān)鍵就是求最小路的可靠性。任意結(jié)點和的第條最小路的可靠性可由連接最小路之間所有鏈路的可靠性得到，由于這些鏈路之間是串聯(lián),并且每條弧都不對其他的鏈路有影響，故這條最小路的可靠性可表述如下：其中，是第條鏈路的可靠性，由此可得結(jié)點對之間的可靠性為：網(wǎng)絡的可靠性指標反映了網(wǎng)絡的拓撲結(jié)構(gòu)因素。針對本文，僅考慮網(wǎng)絡結(jié)構(gòu)的可靠性，即結(jié)點和鏈路絕對可靠,即時。則可得所得最小生成樹的可靠性為：由此可知，該樹形網(wǎng)絡結(jié)構(gòu)的可靠性相當?shù)?，而從樹形圖上也可以看出

19、，當位于中間的某個點出現(xiàn)故障時，整個網(wǎng)絡就將處于分離的狀態(tài)。結(jié)論：該樹形網(wǎng)絡，若只考慮費用問題，便可得出最少的費用。但是整個網(wǎng)絡的可靠性極低，不能滿足實際的需求，即該方案不可行。5.2 問題二：結(jié)點可靠性模型5.2.1建模思路問題二實際上是要在問題一的基礎(chǔ)上加以改進。首先找出無論是哪個結(jié)點出現(xiàn)故障，都能保持通信暢通達到90%的點，將找出來的點進行剔除。然后建立結(jié)點可靠性模型，對剩下結(jié)點通過增加鏈路進行改進，以構(gòu)成環(huán)的方式使得網(wǎng)絡的可靠性達到90%以上。最后根據(jù)改進后的網(wǎng)絡結(jié)構(gòu)圖求出總鋪設費用。5.2.2 建模準備不連通節(jié)點對的計算對個結(jié)點的連通圖，設刪除任一結(jié)點后所形成的連通分支數(shù)為，每個連通

20、分支中的結(jié)點數(shù)為。刪除任一結(jié)點后使自身與剩余結(jié)點之間產(chǎn)生的不連通結(jié)點對數(shù)為對，而在剩余結(jié)點之間產(chǎn)生的不連通結(jié)點對數(shù)為。因此，刪除后總的不連通結(jié)點對數(shù)為。定義1 通信度：對于含有80個結(jié)點的網(wǎng)絡圖，若某一個結(jié)點出現(xiàn)故障，即將該結(jié)點剔除后，剩下網(wǎng)絡的結(jié)點對數(shù)與總的網(wǎng)絡結(jié)點對數(shù)的比值。即：由定義可知，當，則此點為能保持通信暢通達到90%的點，此點為非重要結(jié)點。當，則此點為不能保持通信暢通達到90%的點，此點為重要結(jié)點。即重要點為刪除某一點后通信網(wǎng)絡的通信能力低于90%的點，反之則為非重要點。任一重要點出現(xiàn)故障，則整個通信網(wǎng)絡的可靠性將不能達到要求。重要結(jié)點之所以重要是因為其失效會使網(wǎng)絡中相連接的結(jié)點

21、對數(shù)目減少或使結(jié)點對之間的通路少，網(wǎng)絡的生存性降低。在本文的網(wǎng)絡模型中，結(jié)點要么工作正常，要么失效，因此我們可以具體地量化結(jié)點對網(wǎng)絡的影響。通過計算得出問題一中樹形圖的重要結(jié)點圖：圖2 重要結(jié)點圖分析圖2可知，要保證圖2中的每一個節(jié)點出現(xiàn)故障之后，圖2所組成的網(wǎng)絡的任一結(jié)點間仍然能夠正常通信。即必須要構(gòu)成環(huán)才能滿足要求。問題轉(zhuǎn)化為在增加費用最小的情況下，使得在圖2的基礎(chǔ)上構(gòu)成環(huán)。即在結(jié)點16,31,23,17,61之間增加鏈路來保證通信的可靠性?？紤]到以上節(jié)點與一些非重要點鏈接，稱以上五個節(jié)點與各自相連的非重要節(jié)點所構(gòu)成的子網(wǎng)絡為連通塊。則只需在這五個連通塊中各自選出一個節(jié)點構(gòu)成一個最小生成樹

22、，從而使得增加的鏈路的費用最小。新構(gòu)成的最小生成樹只有5個結(jié)點，同問題一可知增加鏈路的最小費用為，由以上連通塊的定義可知，當節(jié)點35,2,70出現(xiàn)故障時，仍不能滿足重要結(jié)點間能夠正常通信的要求，則只需將該3個結(jié)點的連通塊中的任一結(jié)點與圖2中連接費用最小的重要結(jié)點之間進行連接，即在保證可靠性的前提下，保證了所有增加鏈路的費用最小。新增3個連通塊的鏈路費用為,建立模型如下：其中為增加鏈路之后的最小費用，為問題一中求得的最少費用。分析選出的重要結(jié)點，使其通過增加鏈路后，能保證任意一點出現(xiàn)故障后，其余的重要結(jié)點仍然能夠正常的通信。設計算法流程圖，如圖3：結(jié)點號刪除結(jié)點計算去掉后的連通結(jié)點對的數(shù)量m，并

23、計算通信度是否所有結(jié)點都被刪除過比較通信度是否大于90%設結(jié)點為重要結(jié)點設結(jié)點為非重要結(jié)點否是是否圖3 設計算法流程圖通過Matlab編程可得到增加鏈路后的連通圖如圖4：圖4 增加鏈路后的連通圖虛線為增加的鏈路，并得出改進方案后的最小費用為3783700元。5.3 問題三：鏈路可靠性模型5.3.1 建模思路問題三要求任意一條鏈路被破壞時，能夠保持通信暢通的結(jié)點都能夠達到90%，并且網(wǎng)絡連接所花費的費用要最少。由于任意一條鏈路出現(xiàn)故障之后，原來的最小生成樹網(wǎng)絡就將斷成兩個或多個子網(wǎng)絡，如果子網(wǎng)絡中所包含的結(jié)點數(shù)大于或等于72，則該網(wǎng)絡能滿足任意一條鏈路被破壞后，能夠保持通信暢通的結(jié)點都能夠達到9

24、0%的要求。問題轉(zhuǎn)化為求鏈路被破壞后，最大子網(wǎng)絡之外的所有子網(wǎng)絡的結(jié)點總數(shù)不能超過8。同問題二思想可得到最重要的鏈路所組成的子網(wǎng)絡，并在此子網(wǎng)絡上通過增加鏈路來使得網(wǎng)絡滿足可靠性的要求。通過增加的鏈路，即可求出最少的鋪設費用。5.3.2建模準備通過分析可知，需求鏈路被破壞后，最大子網(wǎng)絡之外的所有子網(wǎng)絡的結(jié)點總數(shù)不能超過8的情況。引進重要子網(wǎng)絡和斷鏈結(jié)點集的的概念。定義2：有且只有一條鏈路被破壞后，被分成的子網(wǎng)絡中含結(jié)點最多的那個子網(wǎng)絡的結(jié)點數(shù)不能小于72，將該子網(wǎng)絡稱為重要子網(wǎng)絡，剩下結(jié)點數(shù)所組成的網(wǎng)絡為非重要子網(wǎng)絡。定義3：將重要子網(wǎng)絡與非重要子網(wǎng)絡連接的結(jié)點與重要子網(wǎng)絡所鏈接的鏈路稱為重要

25、斷鏈，若重要斷鏈出現(xiàn)故障之后剩下的相對結(jié)點較少的結(jié)點集合稱為斷鏈結(jié)點集。由以上定義可知該最小生成樹網(wǎng)絡共有3個斷鏈網(wǎng)絡集。分別為U112，33，41，46，51，64，65，73U26，10，11，15，17，23，44，57，64，71，72，74，75，77U31，8，14，26，32，34，36，50，61，66，67，70則只需在3個斷鏈網(wǎng)絡集中分別選出一個結(jié)點，在這三個結(jié)點中，連接兩條鏈路就能保證保持通信暢通的結(jié)點都能夠達到90%的要求。重要子網(wǎng)絡中的結(jié)點數(shù)可以表示為。通過以上分析，建立鏈路模型為：其中表示增加鏈路后的最少費用，為原來最小生成樹網(wǎng)絡所需的費用，為新增加鏈路的費用。通過

26、Matlab編程得到的新增加鏈路為（46,36）、（46,71）。如圖5:圖5 鏈路增加圖此時通信網(wǎng)絡的最少費用為3056600元。5.4 問題四：網(wǎng)絡優(yōu)化模型5.4.1 建模思路問題四要求綜合考慮網(wǎng)絡的可靠性以及鋪設費用，并確定合理的鋪設方案。由上述幾問可知本文網(wǎng)絡的可靠性是指網(wǎng)絡節(jié)點的可靠性，網(wǎng)絡鏈路的可靠性以及網(wǎng)絡拓撲結(jié)構(gòu)的可靠性。本文主要考慮網(wǎng)絡節(jié)點的可靠性和鏈路的可靠性。網(wǎng)絡的優(yōu)化設計關(guān)鍵在于網(wǎng)絡的可靠性要高,并且網(wǎng)絡設計費用要低。可用一種基于鏈路的網(wǎng)絡優(yōu)化模型并運用演化算法來求解。該方法能夠?qū)W(wǎng)絡的可靠性給出評價。5.4.2 建立模型網(wǎng)絡代價分析對網(wǎng)絡的優(yōu)化在于網(wǎng)絡的可靠性要高、網(wǎng)

27、絡的代價要低。一個網(wǎng)絡的代價就是鏈路的代價,則有網(wǎng)絡的代價為:其中,根據(jù)網(wǎng)絡可靠性的評估模型和網(wǎng)絡可靠性及其代價模型，可完成網(wǎng)絡可靠性的優(yōu)化設計。優(yōu)化設計指標為網(wǎng)絡的造價、網(wǎng)絡的可靠性，優(yōu)化的方法主要有調(diào)整網(wǎng)絡的拓撲結(jié)構(gòu)、弧的可靠性。網(wǎng)絡可靠性優(yōu)化設計是個很復雜的問題，是典型問題，對節(jié)點很多的大型網(wǎng)絡的優(yōu)化問題，此時時間復雜度很大，用一般的方法便無能為力了。在這種情況下可考慮運用演化算法來求解?？紤]到費用的數(shù)學模型是多目標規(guī)劃問題,為此采用加權(quán)或效用系數(shù)法來建立網(wǎng)絡優(yōu)化模型：其中為罰函數(shù)，是罰因子，為問題一中網(wǎng)絡的可靠性。這樣可以得到很多組的、，根據(jù)實際來選擇拓撲結(jié)構(gòu)圖。5.4.3 算法設計網(wǎng)

28、絡的可靠性優(yōu)化用演化算法求解,與傳統(tǒng)的啟發(fā)式算法相比,演化算法不適應鄰域最優(yōu)解的微調(diào)結(jié)構(gòu),應該把傳統(tǒng)的啟發(fā)式算法和它混和使用,在解決此問題時采用如下3個步驟:將啟發(fā)式嵌入初始化中產(chǎn)生一個適應性好的初始解,按照這種方式,混合演化算法能夠保證優(yōu)于傳統(tǒng)的啟發(fā)式算法。將啟發(fā)式嵌入到評估函數(shù)中將染色體解碼。局域搜索啟發(fā)式嵌入演化算法基本環(huán)節(jié)中,同變異和交叉算子一起作用,在評估前對后代實行快速且局部優(yōu)化。這樣可以使2種方法結(jié)合起來,相互彌補不足,混合的演化算法比傳統(tǒng)的演化算法尋優(yōu)速度提高了。演化算法的基本過程為：啟發(fā)式得到初始化 ；評估；不滿足終止條件重組 獲得；啟發(fā)式獲得；評估；從 和 中選擇；對于染色

29、體,采用二進制串表達,弧選為1，否則就記為0。這樣就可以得到一個二進制串,結(jié)點的串長為 。染色體的初始種群可隨機產(chǎn)生,染色體的條數(shù)可以根據(jù)實際節(jié)點的多少來定。對于交叉和變異,可以采用斷點交叉法。隨機地選一個斷點,交換雙親上斷點的右端,生成新的后代。在傳統(tǒng)的演化算法中,變異只是后備算子,用于產(chǎn)生關(guān)于染色體的微小振動以維持個體的分散性。筆者設計了一個混合式的演化算法,基本原則是可以在任何有優(yōu)益的情況下混合。因此在這里設計的變異算子就不是后備算子了,主要過程如下:隨機選擇一個沒有變異的算子；從中挑出a 個不同的基因；基于基因的所有排列構(gòu)造鄰域；評估所有鄰域的情況；挑選最好的鄰域染色體作為后代； 通過

30、以上算法，利用Matlab編程可得到網(wǎng)絡的最少費用為網(wǎng)絡結(jié)構(gòu)圖為：圖6 網(wǎng)絡結(jié)構(gòu)圖六、模型的誤差分析誤差分析（1）模型的求解方法在一定程度上不夠精確，存在一定偏差；（2）本題中結(jié)點數(shù)太多，鏈路太多，使模型的求解方法有一定的局限性，導致結(jié)果有不可避免的偏差；（3）通信網(wǎng)絡的鋪設總費用只考慮了與結(jié)點和鏈路有關(guān)，與其它因素無關(guān)，但在現(xiàn)實中，是不可能局限于這兩個因素的，因此由模型求解出來的結(jié)果還具有一定的局限性和不可靠性；（4）多目標規(guī)劃模型的精確解難已實現(xiàn)，計算機的實現(xiàn)可能帶來小的偏差。然而，在實際中，這些問題不足以對結(jié)果產(chǎn)生太大的影響。因此，模型及結(jié)果是可信的。七、模型評價7.1 模型的優(yōu)點（1）

31、Prim算法應用比較成熟，模型中將每兩個結(jié)點間的鋪設費用視為權(quán)值，編程通過計算機計算實現(xiàn)，因此可以快速的得出精確的結(jié)果；（2）問題一中有效地利用了最短路徑的思考方法，將每兩個結(jié)點間的鋪設費用作為權(quán)值，從而解出了最小生成樹。（3）問題二、三中的模型考慮得深入詳細，各有特點，都較快地得出了恰當可行的方案；（4）利用Netrel軟件畫出了通信網(wǎng)絡結(jié)構(gòu)圖，并用流程圖來表示思路，使模型更加簡便、直觀、快捷；（5）本文建立的模型與實際緊密聯(lián)系，充分考慮了現(xiàn)實情況，從而使模型更加簡單實際，且通用性強。7.2 模型的缺點（1）本題中的網(wǎng)絡結(jié)構(gòu)圖并沒有依據(jù)各個結(jié)點間的距離作圖，在視覺上容易給人造成錯覺，產(chǎn)生距離

32、長短之別；（2）在建立模型中，為了使計算簡便，所得結(jié)果更理想化，只考慮了結(jié)點和鏈路對網(wǎng)絡結(jié)構(gòu)的影響，忽略了其他因素的影響。八、模型的改進在數(shù)據(jù)問題四的算法設計中，可參照選取的變異率和交叉率為，從而得出鏈路的費用矩陣和鏈路可靠性矩陣，由此可得拓撲結(jié)構(gòu)圖。網(wǎng)絡的可靠性指標反映了網(wǎng)絡的拓撲結(jié)構(gòu)因素。當結(jié)點和弧絕對可靠,即時,為網(wǎng)絡的抗毀性能指標，反映網(wǎng)絡拓撲結(jié)構(gòu)的可靠性。因此，是反映可靠性和抗毀性的一個綜合指標,同時這一指標是相對全連通、全可靠網(wǎng)絡的歸一化指標。對于全連通、完全可靠的網(wǎng)絡, 恒等于1 , 因此對任一網(wǎng)絡有 。因而,這一指標可用于指導網(wǎng)絡的可靠性、抗毀性分析和評估。只是本文沒有給出足夠

33、的數(shù)據(jù)得出相應的變異率和交叉率，因此不能得出鏈路的相關(guān)矩陣，從而不能快速解決問題四中需要綜合考慮鏈路和結(jié)點，設計出最佳的網(wǎng)絡鋪設結(jié)構(gòu)圖。九、模型的推廣（1）問題二、三中所建立的模型，都是以不同因素為出發(fā)點考慮，建立相關(guān)模型，得到最少的鋪設費用。此模型可以推廣到因素分析方面，例如商店月利潤影響因素分析、環(huán)境污染因素考察等方面。（2）問題四中的建立的網(wǎng)絡優(yōu)化模型，綜合考慮各個方面的因素，使花費的鋪設費用最少的模型，同樣可以推廣到其它的運輸優(yōu)化方案和資源配置優(yōu)化的問題中。（3）本文中建立的模型都可以算作為優(yōu)化設計模型，并繪制出了相應的網(wǎng)絡結(jié)構(gòu)圖，因此模型還可以推廣到公交車站點的最優(yōu)設置、新增商店的最

34、優(yōu)配置、自行車租賃點的最優(yōu)設置等問題中。十、參考文獻1 徐駿. 無線通信網(wǎng)絡技術(shù)探析J. 信息通信, 2013(7):212-213.2 江光杰, 王朝瑞. 通信網(wǎng)絡的可靠性評估J. 通信學報, 1997(8):85-89.3 江波, 張黎. 基于Prim 算法的最小生成樹優(yōu)化研究J. 計算機工程與設計, 2009， 31(13):3244-3247.4姜啟源.數(shù)學模型M.北京:高等教育出版社,2003.5 趙靜，但琦. 數(shù)學建模與數(shù)學實驗 M. 北京:高等教育出版社, 2008.6 楊桂元. 數(shù)學建模M. 合肥:中國科學技術(shù)大學出版社, 2008.7 黃樟燦,楊鵬,李亮,施保華. 網(wǎng)絡拓撲結(jié)

35、構(gòu)的數(shù)學模型及遺傳算法J. 計算機工程與應用. 2001(02).8 劉衛(wèi)國. Matlab程序設計教程M. 北京:中國水利水電出版社, 2005.9 吳禮斌. 經(jīng)濟數(shù)學實驗與建模M. 天津:天津大學出版社, 2009.10 卓金武. MATLAB在數(shù)學建模中的應用M. 北京:北京航空航天大學出版社, 2011.11 韓中庚. 數(shù)學建模方法及其應用M. 北京:高等教育出版社, 2009.12 張超, 馬存寶, 許家棟. 通信網(wǎng)絡的運行可靠性評估新方法J. 計算機工程與應用, 2006(31).13 劉健, 楊文字, 余健明等. 基于改進最小生成樹算法并考慮J. 電網(wǎng)技術(shù), 2005, 29(16):61-65.14 曾勇,王宇平. 用基于多目標決策的遺傳算法解網(wǎng)絡拓撲結(jié)構(gòu)設計問題J. 計