通信網(wǎng)絡的設計問題

1、通信網(wǎng)絡的設計問題摘要本文針對通訊網(wǎng)絡設訃問題，使用圖論中最小生成樹法、節(jié)點排除法、網(wǎng)絡故障分析法、 對比分析法等方法，分別構建普里姆(prim)模型、節(jié)點故障模型、鏈路故障模型等模型， 使用Matlab軟件編輯算法，得到通訊網(wǎng)絡總費用最省的鋪設方案、可靠性條件下最省鋪設方 案以及綜合條件下最省鋪設方案。針對問題一要求，具體要求為使得通信網(wǎng)絡的總鋪設費用最省，首先使用了簡化模型分 析、反證法等方法，證明最小生成樹算法能測算無向圖遍歷節(jié)點的最省方案，其次應用最小 生成樹法中的普里姆(prim)算法構造通訊網(wǎng)絡總費用最省模型使用Matlab軟件編程，得到 最優(yōu)鋪設方案并作圖。針對問題二要求任意一個

2、結點出現(xiàn)故障時，其它結點間仍然能夠保持通信暢通的可能性 都達到90%時最省鋪設方案設計問題，首先使用節(jié)點排除法進行處理，找到重要節(jié)點，利用 樹圖將節(jié)點分類，再通過分類失效節(jié)點與有效節(jié)點連接達到通暢性要求，最后使用Matlab軟 件編程得出節(jié)點故障模型下最省鋪設方案。針對問題三要求，任意一條鏈路被破壞時，能夠保持通信暢通的結點都能夠達到90%時 最省鋪設方案設計問題，首先找到重要鏈路，并分析鏈路影響的節(jié)點，用樹圖將節(jié)點分類， 再通過分類失效節(jié)點與有效節(jié)點連接達到通暢性要求，最后使用Matlab軟件編程得出鏈路故 障模型下最省鋪設方案。針對問題四要求，綜合考慮網(wǎng)絡的可鼎性以及鋪設費用確定合理的鋪設

3、方案問題，首先 對比分析問題二與問題三的節(jié)點分類，得出節(jié)點穩(wěn)定性比鏈路穩(wěn)定性更重要的結論；再通過 節(jié)點故障模型分別構造通信暢通的可能性都達到85%、90%、95%時所對應的最低鋪設費用， 使用Matlab軟件編程，得到綜合考慮下的鋪設方案。本文后續(xù)對模型進行了誤差分析。還基于對問題四中可靠性不僅僅與節(jié)點和鏈路的穩(wěn)定 性有關，還與節(jié)點的度有關，故引進節(jié)點的度對模型進行改進，并利用蟻群算法建立綜合LI 標下的鋪設模型；最后對模型做出了縱向的推廣和橫向的推廣。關鍵詞：網(wǎng)絡通訊設計；最小生成樹法；故障分析法；蟻群算法；matlab1問題的重述一、背景知識傳統(tǒng)的通信網(wǎng)絡是山傳輸、交換和終端三大部分組成。

4、傳輸是傳送信息的媒體，交 換是各種終端交換信息的中介體，終端是指用戶使用的話機、手機、傳真機和計算機等?，F(xiàn)代電信網(wǎng)是曲專業(yè)機構以通信設備（硬件）和相關工作程序（軟件）有機建立的 通信系統(tǒng)，為個人、企事業(yè)單位和社會提供各類通信服務的總和?，F(xiàn)在計算機網(wǎng)絡技術在各個領域的應用范圍已經(jīng)逐步廣泛起來，其發(fā)展也在不斷的 推動人類社會逐漸走向信息時代。網(wǎng)絡技術的發(fā)展不僅促進了社會生產(chǎn)力的提高，也為 人們的生活帶來了很大的方便。然而，與此同時也存在著很多不足，諸如安全隱患、信 息漏洞等，這些對于人們的工作和生活造成了很大的影響。我們在需要在研究通信網(wǎng)絡 鋪設問題時的費用問題時，也要充分考慮其的可靠性。可靠性是

5、其重要的整體指標，通 信網(wǎng)絡的可靠性不僅與通信設備、鏈路有關，而且還與網(wǎng)絡結構有關。山于網(wǎng)絡結構的 復雜多變，通信網(wǎng)絡的可靠性分析一直是個棘手的問題。二、相關資料1. 80個節(jié)點之間的距離表和鋪設線路的單位費用表（見附表1）；三、要解決的問題問題1.要使得通信網(wǎng)絡的總鋪設費用最省，請建立問題的數(shù)學模型，設計求解算 法，給出鋪設方案，并討論方案的可鼎性；問題2.考慮到通信網(wǎng)絡結點的可靠性，若要求任意一個結點出現(xiàn)故障時，其它結 點間仍然能夠保持通信暢通的可能性都達到90%,請建立問題的數(shù)學模型，設計求解算 法，并給出使總鋪設費用最少的鋪設方案；問題3：考慮到通信網(wǎng)絡鏈路的可靠性，若要求任意一條鏈路

6、被破壞時，能夠保持 通信暢通的結點都能夠達到90%,請建立問題的數(shù)學模型，設計求解算法，并給出使總 鋪設費用最少的鋪設方案；問題4：綜合考慮網(wǎng)絡的可靠性以及鋪設費用，試確定合理的鋪設方案。2問題的分析一、問題的總分析對于問題的總分析，可以給出四個問題整體框架圖，見圖1圖1四個問題的整體框架圖相應呆優(yōu)方案確定通信網(wǎng)絡鋪設的合3方案二、對具體問題的分析1. 對問題一的分析某通信公司擬建一個具有80個結點的通信網(wǎng)絡，需要在這些結點之間鋪設線路，進 行數(shù)據(jù)傳輸。我們需要根據(jù)附件內(nèi)容建立數(shù)學模型，并設計算法使得通信網(wǎng)絡的總鋪設 費用最省，并證明可靠性。我們引入圖論中普里姆算法（Prim算法），算法對通信

7、網(wǎng)絡 的每條路的鋪設費用總額進行模擬測算，形成鋪設費用的最小生成樹，并通過簡化模型 進行檢驗算法的可鼎性。2. 對問題二的分析問題要求這80個節(jié)點任意一個節(jié)點出現(xiàn)故障時，其它節(jié)點間仍然能夠保持通信暢 通的可能性都達到90%,在問題一所得出的最小生成樹的的基礎上，若其中只有一個重 要節(jié)點發(fā)生故障時，會造成八個節(jié)點以上故障，那么通信暢通的可能性就不能達到90%, 故通過節(jié)點刪除法找到重要節(jié)點，再從重要節(jié)點引起故障的其他失效節(jié)點中找到一個節(jié) 點與其他正常節(jié)點連通使得發(fā)生故障的節(jié)點數(shù)少于八個即可，并且改進方案所鋪設的費 用是最省的。3. 對問題三的分析問題要求79個鏈路中任意一條鏈路被破壞時，能夠保持

8、通信暢通的節(jié)點都能夠達 到90%。同樣在問題一所得出的最小生成樹的的基礎上，我們考慮到若其中只要有一個 重要鏈路被破壞時，會造成八個節(jié)點以上故障，那么通信暢通的可能性就不能保證達到 90%,所以，我們可以通過逐個分析每條鏈路，找到重要鏈路，一個鏈路被破壞會使最 小生成樹分割成兩個部分，其中一部分則是失效的，然后再從重要鏈路被破壞而引起的 其他失效節(jié)點中找到一個節(jié)點與其他正常節(jié)點連通使得發(fā)生故障的節(jié)點數(shù)少于或等于 八個，我就能保證通信暢通的可能性達到90%,并且我們要找到的這個節(jié)點與其他正常 節(jié)點連通所鋪設的費用是最省的。4. 對問題四的分析問題要求是綜合考慮網(wǎng)絡的可靠性以及鋪設，試確定合理的鋪

9、設方案。首先對比分析問 題二與問題三的節(jié)點分類，發(fā)現(xiàn)問題三中節(jié)點的分類包含了問題二中節(jié)點的分類，若滿足了 了節(jié)點穩(wěn)定性的要求，則一定能滿足鏈路穩(wěn)定性的要求，故得出節(jié)點穩(wěn)定性比鏈路穩(wěn)定性更 重要的結論：再通過節(jié)點故障模型分別構造通信暢通的可能性都達到85%. 90%、95%時所對 應的最低鋪設費用，使用Matlab軟件編程，綜合考慮穩(wěn)定性和鋪設費用得出鋪設方案。3模型的假設1兩個節(jié)點之間的費用僅由節(jié)點之間的距離和鋪設線路的單位費用決定；2. 各節(jié)點和各鏈條間發(fā)生故障是相互獨立的，節(jié)點1發(fā)生故障不影響節(jié)點2發(fā)生 故障；3. 每個節(jié)點的重要性是相等的，不存在次級差別；4. 任意兩個節(jié)點之間可以進行連

10、接，且一個節(jié)點可以連接的節(jié)點不受限制；5. 網(wǎng)路的穩(wěn)定性與節(jié)點所連的鏈路條數(shù)無關，即每個節(jié)點和鏈路出現(xiàn)故障的可能 性是相等的；4名詞解釋與符號說明一、名詞解釋1. 最小生成樹：一個有n個結點的連通圖的生成樹是原圖的極小連通子圖，且包 含原圖中的所有n個結點，并且有保持圖連通的最少的邊。2. 普里姆算法（Prim算法）指可在加權連通圖里搜索最小生成樹。意即山此算法 搜索到的邊子集所構成的樹中，不但包括了連通圖里的所有頂點，且其所有邊的權值之 和亦為最小。二、主要符號說明序號符號符號說明1V表示加權連通圖的節(jié)點集合2E表示加權連通圖的邊集合3t表示V集合中的任意節(jié)點4%表示初始的節(jié)點集合5U表示集

11、合中的兀素6V表示H中的節(jié)點但不是中的節(jié)點7Xij表示一個0、1變量，0, 1分別表示選中和未選中8%表示節(jié)點i到節(jié)點j鋪設線路所花費的費用9z表示所選的鋪設方案所花費的總費用10e表示最小生成樹的鏈路5模型的一、問題一的分析與求解1. 問題的分析問題要求根據(jù)附件內(nèi)容建立數(shù)學模型，并設訃算法使得通信網(wǎng)絡的總鋪設費用最 省，并證明可靠性：我們引入圖論中普里姆算法（Prim算法），算法對通信網(wǎng)絡的每條 路的鋪設費用總額進行模擬測算，形成鋪設費用的最小生成樹，并通過簡化模型進行檢 驗算法的可靠性。本文中連通圖的頂點為80個通訊網(wǎng)絡的節(jié)點，所有邊的權值為兩節(jié)點之間的鋪設通 訊鏈路的總費用，通過普里姆算

12、法可以得出聯(lián)通所有頂點并且使總鋪設費用最低的樹 圖，即相對于問題一的最優(yōu)鋪設方案。2. 問題的求解模型I總鋪設費用最省模型（1）模型的建立普里姆算法（Prim算法）的步驟：從單一點開始，普里姆算法按照以下步驟逐步擴大樹中所含節(jié)點的數(shù)U,直到遍歷 連通圖的所有節(jié)點。首先設加權連通圖的節(jié)點集合為V，邊集合為E，初始化=”， 其中/為集合V中的任意:節(jié)點，其次在集合中選取權數(shù)最小的邊（“*）,其中為集合 %中的元素，而卩不是，如果存在權數(shù)一樣的可任選其中之一，再次，將卩加入到匕， 重復第二第三步，直到K=Vo引入一個變量知，X9 = 0時說明該路徑未被選中，1則表示被選中count（y）為總結n n

13、minZ =工工叫勺 j=i j=i點數(shù)建立的數(shù)學模型如下s.t=1 ;=1工七 |coz/nZ(V)| - 111 / 29算法流程圖見圖2圖2問題一的算法流程圖為了更好的表現(xiàn)算法內(nèi)容，用以下簡化模型來表示并驗證: 表1普里姆算法示例圖 設置一個加權連通圖，頂點集合為 V,邊集合為E o （ So. a、b、c、為頂點, 連線為邊，邊上數(shù)字為權值）So6cdS。cdSo6cd 選擇頂點集合中任意頂點，此處選 擇S。為初始點。頂點a、b、c、d都有與S（） 直接相連的邊，選取其中權重最小的點（圖 中為a） 下一個頂點為距離a或S最近的頂 點，a距離c為10,距d為6,距b為5； So 距c為1

14、0,距d為15,距b為15；所以最 短的距離是a到b得距離為5,連接a與b 繼續(xù)重復上面的步驟?？梢园l(fā)現(xiàn)距 離6 b和S。最短的是b到c得距離為5,連 接b和6反證法：設生成的樹為0,假設存在d使得總花費cosr(a)1將兩個因素綜合考慮，這里利用線性加權的辦法將其綜合，首先將式(1)、(2)歸 一化，然后定義偏好系數(shù)/e(O,l), /越接近0表是決策者越傾向于費用因素，越接近 于1越傾向于流量因素，所以，最終的目標函數(shù)為：f = sfd (土 丈叫j/-I 7-1七)+冏(M (deg)5/(deg)設置約束條件，其中假定每一個節(jié)點的度數(shù)屬于2,5的閉區(qū)間。凡是有節(jié)點度數(shù)不 在詞區(qū)間的方案

15、都被認為是不可行解。為防止螞蟻在尋優(yōu)的過程中產(chǎn)生不可行解，定義(low,up)為度的約束區(qū)間。對于每一個節(jié)點i,其度deg(/),在此定義一個函數(shù):0s = nunxlOO%f min相應的最大容忍度為兒仁節(jié)點穩(wěn)定性的約束：首先引入一個故障矩陣DP, D表示在節(jié)點i和節(jié)點丿之間 存在連接線時，連接線出現(xiàn)故障的概率。仍然假定節(jié)點不會出現(xiàn)故障，所有故障都來自 于鏈路。而每一條邊對于點來說是并聯(lián)的，利用概率統(tǒng)計的知識，可以求得節(jié)點，能夠 正常工作的概率為：心=1-口令RPmin為用戶規(guī)定的平均最小工作概率。如果在整個網(wǎng)絡中所有節(jié)點工作的概率 的算數(shù)平均值大于RPmm，則這個網(wǎng)絡是可接受的，否則是不可

16、接受的。故RP, %由上述分析，這個優(yōu)化的模型是一個組合優(yōu)化模型，可以用蟻群算法來求解，這里 簡要介紹一下蟻群算法的求解過程。1. 初始化參數(shù)2. 利用概率的方法構建螞蟻的路徑。本文綜合考慮了最小成本模型和度約束條件, 同時在本模型中乂加入了流量及鏈路概率的影響。如當前位于節(jié)點i的螞蟻k選擇丿作為 下一個節(jié)點的概率為：”2伽/.Vj其中，5為鏈路信息素強度；竹 為一個預先給定的啟發(fā)式信息，初始值為鏈路 (/距離的倒數(shù)。為本算法設置了啟發(fā)式信息的優(yōu)先級：鏈路“如果有一個端點的度為1, 則加1倍，若鏈路(/ 2個端點的度都為1, %加2倍。a、卩是2個參數(shù)，它們分 別決定了信息素和啟發(fā)式信息的相對

17、影響力。代表位于節(jié)點j的螞蟻斤可以直接到達 的相鄰節(jié)點的集合，也就是還沒有被螞蟻&訪問的節(jié)點的集合。Step3本文使用的后臺策略是在螞蟻前進一步時就計算各個約束的值，看是否滿足 要求，當有一個約束不再滿足要求時，螞蟻不再前行。一輪路徑探索完之后，計算LI標 函數(shù)的值，進而挑選出最優(yōu)的路徑。Step4在每一輪路徑探索之后，更新信息素，更新規(guī)則如下：tn5 ( +1) = PD (n) + Ar/ (/?)其中p為信息素揮發(fā)程度；Ar/(/O表示第k次循環(huán)是否選擇了鏈路“，如果先擇(/ , XjS = Q/diSij,否則，= 0, Q是常數(shù)。5 當路徑探索的論述達到NCmax時輸出結果。因為蟻群

18、算法有較強的收斂性，故當經(jīng)過不同次數(shù)的迭代實驗是，會得出較為相近 的結果，此時則為最優(yōu)的結果，最終的結果可有C語言編程完成。參考文獻：11 .2基于蟻群算法的多目標網(wǎng)絡鋪設策略研究龔承柱1,諸克軍I,郭海湘1,2(1.中 國地質(zhì)大學經(jīng)濟管理學院，武漢430074： 2.西安交通大學管理學院，西安710049).3姜啟源，謝金星，葉俊.數(shù)學模型M北京；高等教育出版社，2011, 1.21 / 29附錄程序1:%A表示權值矩陣%C表示生成樹的權和%visit標記是否訪問過(1表示訪問，0表示未訪問)，dis記錄當前最短距離，R矩 陣表示結點序號之間從前往后依次連接clc,clearAzzxlsre

19、adCdate.xls);%權值矩陣(節(jié)點之間的費用表二距離*單位費用)L=length(A);A(A=O)=inf;% 初始化鄰接矩陣 dis=zeros(l ,L);dis(:)=inf;%初始化 dis 數(shù)組 visit=zeros( 1 ,L)；RESUET=zeros(L,L)； visit(l )= 1 ;dis(l)=O;next= 1 ;C=0;a=zeros(l,80);%初始時刻1點加入集合中R=zeros(2,79);R(l,:)=l:79;%初始化結果矩陣for k=l:L-l;now=next;%now表示計算的當前節(jié)點 m=inf;%m保存當前節(jié)點到集合的最短距離

20、for i=l:L;if visit(i)=O%如果沒有標記，開始這個點 dis(i)=min(dis(i),A(now,i)；%更新這個i點到集合的最短距離，保存到 dis中if(dis(i)m) m=dis(i); nex t=i; %記錄下最小的那個點，作為下一個計算的點。endendendC=C+m;%加權值visit(next)=l;%標記進集合的點RESULT(k,next)= 1;%整合每次標記endfor t=l:79;R(2,t)=find(RESULT(t,:)= 1);%按順序輸出節(jié)點表示連接過程endR %結果矩陣輸出，第一行表示連接順序，第二行表示表示依次連接節(jié)點數(shù)c

21、 %相應情況下的最省鋪設費用程序二：AzzxlsreadCate.xls1）; %權值矩陣（節(jié)點之間的費用表二距離*單位費用）nl=l 34i2661503270368146667n2=51 30i384583159604812684665334173bn3=77 2366457757111747217104415ml=l 342661503270368146667624769229194928578 351208024m2=513038458315960481268466533417318215243916 5525J ,m3 二7723664577571117472171044157645

22、1；m4=5422 56；%輸入六個節(jié)點分類矩陣xl=m2 m3 m4;x2=ml m3 m4;x3=ml m2 ni4;Ll=length(nl);L2=length(n2);L3=length(n3);L4=length(ml);L5=Iength(m2);L6=length(m3);L7=length(m4);%分別求其長度和兩兩組合長度t=l;for i=l:Ll;for j=l:L2;R(t,:)二n 1 (i) n2(j) A(n 1 (i),n2(j) t=t+l;endend for i=l:Ll;for k=l:L3;R(t,:)=nl(i) n3(k) A(nl(i),n3

23、(k); t=t+l;endendfor j=l:L2;for k=l:L3;R(t,:)=n2(j) n3(k) A(n2(j),n3(k); t=t+l;endendfor i=l:Ll;for p=l:L5+L6+L7;R(t,:)=nl(i) xl(p) A(n 1 (i),xl(p); t=t+l;endendfor j=l:L2;for q= 1: L4+L6+L7;R(t,:)=n2(j) x2(q) A(n2(j),x2(q); t=t+I;endendfor k=l:L3;for r=l:L4+L5+L7;R(t,:)=n3(k) x3(r) A(n3(k),x3(r); t

24、=t+l;endendR1 =sortrows(R( 1:192,:),3);Result(h：)=Rl(l,:);R2=sortrows(R(l 93:360,:),3);Result(2,:)=R2( 1R3=sortrows(R(361:584,:),3);Result(3,:)=R3( 1R4=sortrows(R(585:1101 ,:),3);Result(4,:)=R4(l,:);R5=sortrows(R(l 102:1997,:),3);Result(5,:)=R5(l,:);R6=sortrows(R( 1998:2893,:),3)；Result(6,:)=R6(l,:)

25、;%逐個計算最省費用Result%輸出分類比較下的最省費用及相應連接節(jié)點序號程序三：AzzxlsreadCdate.xls1); %權值矩陣(節(jié)點之間的費用表二距離*單位費用)nl=I 342661503270368146667n2=51 30384583159604812684665334173n3=77 2366457757111747217104415m1=1 342661503270368146667624769229194928578 35208024m2=513038458315960481268466533417318215243916 5525J ,m3=77236645775

26、71117472171044157645；m4=5422 56；xl=m2 m3 m4;x2=ml m3 m4;x3=ml m2 m4;Ll=length(nl);L2=length(n2);L3=Iength(n3);L4=length(ml);L5=length(m2);L6=length(m3);L7=length(m4); %分別求其長度和兩兩組合長度t=l；for i=l:Ll;for j=l:L2;R(t,:)=nl(i) n2(j) A(nl(i),n2(j); t=t+l;endendfor i=l:Ll;for k=l:L3;R(t,:)=nl(i) n3(k) A(nl(i

27、),n3(k); t=t+I;endendfor j=l:L2;for k=l:L3;R(t,:)=n2(j) n3(k) A(n2(j),n3(k); t=t+l;endendfor i=l:Ll;for p=l:L5+L6+L7;R(t,：)=n l(i)xl(p) A(n 1 (i),x 1 (p)； t=t+l;endendfor j=l:L2;for q= 1: L4+L6+L7;R(t,:)=n2(j) x2(q) A(n2(j),x2(q); t=t+l;endendfor k=l:L3;for r=l:L4+L5+L7;R(t,:)=n3(k) x3(r) A(n3(k),x3

28、(r); t=t+I;endend%分別求其長度和兩兩組合長度R1 =sortrows(R( 1:192,:),3);Result(l,:)=Rl(l,:);R2=sortrows(R( 193:360, :),3);Result(25:)=R2( 1R3=sortrows(R(361:584,:),3);Result(3,:)=R3(l,:);R4=sortrows(R(585:1100,:)53)；Resul t(4,: )=R4( 1,:);R5=sortrows(R( 1101:1996,:),3);Result(5,:)=R5( 1R6=sortrows(R( 1997:2562,:

29、),3)；Result(6,:)=R6( 1Result%輸出分類比較下的最省費用及相應連接節(jié)點序號附錄四AzzxlsreadCate.xls1）; %權值矩陣（節(jié)點之間的費用表二距離*單位費用）nl=26 3415032;n2=66 6736814;n3=79 63402024 8039;n4=28 491929;ml =65 337341;m2=3159604838 458m3=6 645775;m4=17104415;xl=m2 m3 m4;x2=ml m3 m4;x3=ml m2 m4;Ll=length(nl);L2=length(n2);L3=length(n3);L4=lengt

30、h(n4);L5=length(ml);L6=length(m2);L7=length(m3);L8=length(m4); %求矩陣長度t=lfor il=1:L1;for jl = l:L5;R(t,:)=nl(il)ml(jl)A(nl(il),ml(jl)l； tn+1；endend for il=1:L1;for jl = l:L6;R(t,:)=nl(il) m2(j 1) A(n 1 (il),m2(j 1); t=t+I;endendfor il=1:L1;fo 叮 1 = 1:L7;R(t,：)=nl(il) m3(j 1) A(n 1 (il),m3(j 1); t=t+I;endendfor il=1:L1;for jl = l:L 8;R(t,:)=nl(il) m4(jl) A(n 1 (il),m4(j 1); t=t+l;endendfor i2=l:L2;fo 叮 2=1 :L6;R(t,:)=n2(i2) m2(j2) A(n2(i2),m2(j2); t=t+l;endendfor i2=l:L2;for j2=l:L7;R(t,:)=n2(i2) m3(j2) A(n2(,m3(j2); t=t+l;endendfor i2=l:L2; f