通信網(wǎng)設計基礎

1、現(xiàn)代通信網(wǎng)技術3 通信網(wǎng)是一個由多個系統(tǒng)、設備、部件組成的復雜而龐大的整體，要求設計出既能滿足各項性能指標要求，又能節(jié)省費用的結(jié)構(gòu)合理的網(wǎng)絡，首先要求設計人員要掌握相當?shù)木W(wǎng)絡理論基礎和網(wǎng)絡分析計算方法，如通信網(wǎng)所涉及的數(shù)學理論、優(yōu)化算法、網(wǎng)絡的基礎分析方法與指標計算方法等。 本章介紹進行通信網(wǎng)絡設計必備的基礎知識，主要包括： (1)在進行網(wǎng)絡結(jié)構(gòu)設計必備的圖論基本概念和通信路由選擇及網(wǎng)絡優(yōu)化基礎知識最短路徑算法和站址選擇。 (2)在進行網(wǎng)絡流量分析和設計必備的排隊論基礎知識及一些網(wǎng)絡性能指標的分析和計算。7.17.1通信網(wǎng)絡結(jié)構(gòu)設計基礎 通信網(wǎng)是由終端設備節(jié)點、交換設備節(jié)點和傳輸鏈路組成的。設

2、計人員首先要確定眾多的節(jié)點和傳輸鏈路之間的連接方式，也就是通信網(wǎng)的網(wǎng)絡的結(jié)構(gòu)，這是通信網(wǎng)規(guī)劃設計中的第一層次的問題，這個問題的實質(zhì)是要尋找滿足一定條件下的最佳拓撲結(jié)構(gòu)，因而網(wǎng)絡設計的過程就是對網(wǎng)絡結(jié)構(gòu)進行優(yōu)化的過程。借助于電子計算機，使用一定的數(shù)學模型的優(yōu)化算法，將會使網(wǎng)絡的設計更科學、更合理、更經(jīng)濟。本節(jié)首先介紹圖論的基本知識，它是網(wǎng)絡結(jié)構(gòu)設計的數(shù)學工具，然后由此引出最短路經(jīng)的算法和站址選擇問題，這些都可看作網(wǎng)絡結(jié)構(gòu)優(yōu)化的基礎?，F(xiàn)代通信網(wǎng)技術4現(xiàn)代通信網(wǎng)技術57.1.1 圖論基本知識 圖論是離散數(shù)學的一部分，是現(xiàn)代應用數(shù)學的一個分支。離散數(shù)學以研究離散量的結(jié)構(gòu)，相互間的關系為主要目標，其研究

3、對象一般是有限個或可數(shù)個元素。圖論則專門研究人們在自然界和社會生活中遇到的包含某種二元關系的問題或系統(tǒng)。它把這種問題或系統(tǒng)抽象為點和線的集合，用點和線相互連接的圖來表示，圖7.1所示就是這樣一個圖，通常稱為點線圖。圖7.1 圖的概念示例圖現(xiàn)代通信網(wǎng)技術6一、 圖的基本概念1. 圖的定義 由圖7.1可看出，點線圖是由若干個點和點間的連接線組成，點是任意設置的，連線則表示不同點之間的聯(lián)系，由此可引出圖的定義： 設有點集V=v1v2，vn和邊集E=e1，e2，em，如果對任一邊E，有V中的一個點對(vi，vj)與之對應，則圖可用有序二元組(V，E)表示，記為G=(V，E)。 定義中的邊就是點線圖中的

4、連線，如果邊與點對(vi，vj)相對應，則稱，是的端點，記為ek=(vi，vj) ，稱點，與邊關聯(lián)，而稱與為相鄰點，若有兩條邊與同一端點關聯(lián)，則稱這兩條邊為相鄰邊?，F(xiàn)代通信網(wǎng)技術7 2. 有向圖與無向圖 設圖G=(V，E)，如果任一邊ek都對應有一個有序點=(vi，vj) ，則稱圖G為有向圖，如果ek對應的有無序點對(vi，vj)，則稱G為無向圖，如圖7.2(a)所示。在有向圖中，用尖括號表示其中的端點是有序的vi，vj和vj，vi是兩條不同的邊，即vi，vjvj， vi，而用點vj指向vi的箭頭表示vj，vi， 如圖7.2(b)所示。 對無 向中，(vi，vj)和(vj，vi) 是同一條邊。

5、 即：(vi，vj)=(vj，vi)。 圖7.2 有權圖示例圖現(xiàn)代通信網(wǎng)技術8 在實際中，經(jīng)常遇到需要用有向圖表示的問題較多，如電路中的電流，通信網(wǎng)中的數(shù)據(jù)流，它們的流動是有方向的，是和端點的先后次序有關的，這類問題用無向圖是無法表示的，必須使用有向圖。當然，在研究時為了使問題簡化，有時也把它當著無向圖來研究。 3. 有權圖 若對圖G=(V，E)中的每一條邊ek都賦以一個實數(shù)wk，則稱圖G為有權圖或加權圖，wk稱為邊ek的權值。根據(jù)研究問題的需要，權值可以表示不同的含義，如距離、流量、費用、時間等，對通信網(wǎng)來說，權值可以是信道的造價、容量、長度等?，F(xiàn)代通信網(wǎng)技術9 鏈路、路徑、回路 若圖G=(

6、V，E)，其中k(2)條邊和與之關聯(lián)的點依次排成點和邊的交替序列，則稱該序列為鏈路；如果鏈路中不出現(xiàn)重復的邊，則稱為路徑；如果路徑的起點和終點重合，則稱為回路。我們將兩個端點重合為一點的邊稱為自環(huán)；與同一對端點相關聯(lián)的兩條或兩條以上的邊稱為并行邊。把設有自環(huán)和并行邊稱和圖稱簡單圖，在簡單圖中，鏈路、路徑和回路可以只用相應的點序表示。 圖7.3有自環(huán)與并行邊示例圖現(xiàn)代通信網(wǎng)技術105. 連通圖與非連通圖 若圖G中任意兩位點之間至少存在一條路徑，則稱說圖G為連通圖，否則稱為非連通圖。非連通圖總可以分成幾個分離的部分。如圖7.4所示，圖(a)為連通圖，圖上任意兩點之間均可以至少找到一條路徑；圖(b)

7、為非連通圖，v1v2v3v4v5v2v4v6v7v5v8v3（a）連通圖 （b）非連通圖圖7.4 連通圖與非連通圖示例圖現(xiàn)代通信網(wǎng)技術116. 子圖設有圖G=(V，E)和圖 ,GV E若有 VVE E則稱 G是G的子圖； 若有 V V， EE且 E E則稱 G是G的真子圖； （a） （b） （c）圖7.5 圖與子圖示例圖若有V VEE則稱 G是G的生成圖 如圖7.5所示圖(b)是圖(a)的真子圖，圖(c)是圖(a)的生成圖，也是真子圖?，F(xiàn)代通信網(wǎng)技術127. 圖的連通性 在通信網(wǎng)中，圖的連通性起著重要的作用。我們定義與某點相關聯(lián)的邊數(shù)為點的度數(shù)(或次數(shù))，記為d(vi) 。若為有向圖，用 表示

8、 離開或從 的射出的邊數(shù)， 表示進入 或射入 的邊數(shù)； d( )= + 表示 的度數(shù)。如圖7.6(a)為無向圖，如圖7.6(b)為有向圖。 idviviv idviviviv idv id viv圖7.6 圖的度數(shù)示例圖現(xiàn)代通信網(wǎng)技術13.圖的度數(shù)有如下兩個性質(zhì)：(1)對于n個點、m條邊的圖，必有： (7-1) 12niid vm(2) 任意圖中，度數(shù)為奇數(shù)的點的數(shù)目必為偶數(shù)(或零)。這兩個性質(zhì)很容易證明。由于任何邊或與兩個不同的點關聯(lián)，或與一個關聯(lián)而形成自環(huán)，都將提供度數(shù)2，所有點的度數(shù)之和必為邊數(shù)的2倍。若將圖的點集V分為奇度數(shù)點集 和偶度數(shù)點集 ，V= + 根據(jù)(7-1)式有：1V2V

9、122ijkijkv vvvvvd vd vd vm現(xiàn)代通信網(wǎng)技術148. 幾種特殊的連通圖(1) 完全圖 任意兩點都有一條邊的無向圖稱為完全圖。完全圖的點數(shù)叫做圖的階。圖7.7所示是一個6階完全圖。完全圖的點數(shù)n與邊數(shù)m有固定關系。這是因為n階完全圖中每個點數(shù)的度數(shù)為n-1，所有點有度數(shù)之和為n(n-1)根據(jù)式(7-1)有：2m=n(n-1) 則： 雖然，完全圖就是通信網(wǎng)的拓撲結(jié)構(gòu)中的網(wǎng)狀網(wǎng)。圖7.7 6階完全圖示例圖112mn n現(xiàn)代通信網(wǎng)技術15 (2) 正則圖 所有點的度數(shù)均相等的連通圖稱為正則圖。此時d(vi)=常數(shù)。d(vi)=2和d(vi)=3的正則圖如圖7.8（a）（b）所示，

10、完全圖也是正則圖，各點的度數(shù)均為n-1。正則圖的連通性最均勻，它是取得一定連通性邊數(shù)最少的圖。圖7.8 正則圖示例圖現(xiàn)代通信網(wǎng)技術16(3) 尤拉圖 各點度數(shù)均為偶數(shù)的圖稱為尤拉圖，尤拉圖可以是連通圖，也可以是非連通圖，但后者的各部分必均為連通的尤拉圖。連通尤拉圖的充分必要條件是存在一個包含所有邊的閉鏈。圖7.9就是一個連通的尤拉圖。有共邊的兩個尤拉圖構(gòu)成一個尤拉圖的例子如圖7.9所示。圖7.9 尤拉圖的環(huán)和示例圖現(xiàn)代通信網(wǎng)技術17(4) M圖 如果圖中只有兩個度數(shù)為奇數(shù)的點，則此圖稱為M圖。雖然，在M圖中除了兩個點外，所有端的度數(shù)都是偶數(shù)。M圖可以是連通圖，也可以是尤拉圖。連通M圖的充分必要

11、條件是：存在一個含有所有邊的鏈。圖7.10所示是一個M圖。 圖7.10 M圖示例圖現(xiàn)代通信網(wǎng)技術18(5) 漢密爾頓圖 當圖中至少存在一個含有所有點的環(huán)，這個圖稱為漢密爾頓圖，上述的環(huán)稱為漢密爾頓環(huán)。一個漢密爾頓環(huán)可以有幾個不同的漢密爾頓環(huán)，圖7.11所示就是一個漢密爾頓圖，或簡稱H圖 圖7.11 H圖示例圖現(xiàn)代通信網(wǎng)技術192 樹樹 樹是由圖論中一個十分重要的概念，在計算機科學和網(wǎng)絡理論等方面應用很廣泛。（1）、樹的定義與性質(zhì) 樹有各種定義方法，但它們都是等價的，所以可任意取一種作為定義，其它的作為樹的性質(zhì)。 樹的定義為任何兩個點間有路徑且只有一條路徑的連通圖。樹中的路經(jīng)徑稱為樹枝。圖7.1

12、2畫出了幾種圖的例子。許多事物可以用樹的圖形來表示，如計算機的目錄查詢系統(tǒng)、資料檢索系統(tǒng)、通信網(wǎng)絡中的星形網(wǎng)等。樹具有以下性質(zhì)：(1) 具有n個點的樹共有n-1個樹枝。(2) 樹是連通的，但去掉的一條邊便不連通。(3) 樹無回路，但增加一條邊便可得到一個回路。(4) 除單點樹外，樹至少有兩個點度數(shù)為1。 圖7.12 樹示例圖現(xiàn)代通信網(wǎng)技術20圖7.12 樹示例圖現(xiàn)代通信網(wǎng)技術21（2）、圖的支撐樹 若樹 TG，且T包含G的所有的點，則稱T是G的支撐樹，又叫生成樹。換言之，支撐樹是覆蓋連通圖所有點的樹。 由上述定義可知，只有連通圖才有支撐樹，反之，有支撐樹的圖必為連通圖。通常圖G本身就是樹外，G

13、的支撐樹不止一個，即一個連通圖至少有一棵支撐樹。如圖7.13所示，(b)，(c)是圖(a)的兩個支撐樹，支撐樹上的邊組成樹枝集，非樹枝的邊組成連枝集。顯然不同的支撐樹有不同的連枝集。圖7.13 圖的支撐樹示例圖現(xiàn)代通信網(wǎng)技術223 3 割和環(huán)割和環(huán) 在討論圖的連通性時，通常需用樹的概念；而在討論破壞圖的連通性時，就需有割的概念。 割是指圖的某些子集，去掉這些子集就使圖的部分數(shù)增加。若圖是連通的，去掉這種子集就成為非連通的圖。根據(jù)這種子集的元素不同，可分為割點集和割邊集，以下將討論這兩種割。（1）. 割點和割點集 令v是圖G的一個點，去掉v和與之關聯(lián)的邊后，若使G的部分數(shù)增加，則稱v是G的割點。

14、有的圖可能沒有割點，即去掉任一個點，圖的部分數(shù)還是不變，對于連通圖，還是連通的，這種圖稱為不可分圖。但是去掉幾個點后，部分數(shù)增加，則這些點的集合稱割點集。 （2）. 割邊集和割集 令S是連通圖G的邊子集，如果在G中去掉S能使G成為非連結(jié)圖，則稱S是G的割邊集；若S的任何真子集都不是割邊集，則稱S為割集。實際上，割集是最小割邊集。 現(xiàn)代通信網(wǎng)技術23 4 4 圖的矩陣表示圖的矩陣表示 圖的幾何表示具有直觀性，已被廣泛應用，但在數(shù)值計算和分析時，不便于處理和運算，需借助于矩陣表示。這些矩陣是與幾何圖形一一對應的，有了圖形必能寫出矩陣，反之有了矩陣也能畫出圖形。當然根據(jù)矩陣畫出的圖形可以不一樣，但在

15、拓撲結(jié)構(gòu)上是一致的，也就是滿足圖的抽象定義的。用矩陣表示的最大優(yōu)點是可存入計算機，并進行所需的處理和運算。 這里討論幾種常用的矩陣現(xiàn)代通信網(wǎng)技術24(1)完全關聯(lián)矩陣與關聯(lián)矩陣關聯(lián)矩陣是表達點與邊的關聯(lián)性的矩陣。一個具有n個點，m條邊的圖G的完全關聯(lián)陣M(G)，是以每點為一行、每邊為一列的nm矩陣，即： Mijn mGm其中：對無向圖為：不關聯(lián)和關聯(lián)和jijiijevevm01對有向圖為： 不關聯(lián)與的終點是的起點是jijijiijevevevm011例7.2 求圖7.17(a)，(b)的完全關聯(lián)矩陣現(xiàn)代通信網(wǎng)技術25圖7.17 矩陣例題圖 從 和 可以看出，每行中非零元素的個數(shù)等于該點的度數(shù)。

16、對無向圖，每個邊有兩個端點，因此 的每一列元素之和必為2，按模2計算值為0；對有向圖，每條邊有一個起點和一個終點，因此矩陣的每一列元素之和恒為0。所以n個行向不是線性無關的，至少只有n-1個線性無關。這樣意味著在完全關聯(lián)矩陣中，有一行向量是多余的。如果去掉其中的任意一行就可得到關聯(lián)矩陣 ， 關聯(lián)陣它完全能代表一個圖。若以上例中 為參考點，則得到關聯(lián)矩陣 和 分別為：現(xiàn)代通信網(wǎng)技術2612345671213451 0001111 100000()0 1100100 0110010 001100eeeeeeevvM Gvvv12345612234100101111000()011110000011

17、eeeeeevvM Gvv1M G 2M G 1M G 01ijnmMGm 對于連通圖，關聯(lián)矩陣的階是n-1，實際上就是圖的階，即支撐樹的邊數(shù)。換句話說，連通圖的關聯(lián)矩陣中，必存在至少一個(n-1)(n-1)的方陣是非奇異的；這個方陣所對應的邊集就是一棵支撐樹。若關聯(lián)矩陣中有一個(n-1)(n-1)方陣是奇異的，即它的行列式值為零，則這個方陣所對應的邊集中必存在環(huán)，因為形成環(huán)的邊所對應的矢量必線性相關，將使行列式值為零。由此可見，非奇異的方陣所對應的邊中不存在環(huán)，而是一棵支撐樹?，F(xiàn)代通信網(wǎng)技術27123456723014511000000110010( )00110010001100eeeee

18、eevvM Gvv123456202341 1 1 0 0 0( )0 1 1 1 1 00 0 0 0 1 1e e e e e evM Gvv 鄰接矩陣 鄰接矩陣是表示點與點之間關聯(lián)的矩陣，對于一個n個點的圖G，其鄰接矩陣A(G)是nn方陣，即 ，其中： (7-7) 對于無簡單向圖，鄰接矩陣是對稱的，且對角線元素均為零；對于有向的簡單圖，即沒有自環(huán)和同方向并行邊的有向圖，對角線元素也全是零，但鄰接矩陣一般不對稱。如圖7.17中 、 的鄰接矩陣分別為：現(xiàn)代通信網(wǎng)技術絡28nnijaGA)(jivvvvajijiij或無邊與（到）有邊與（到）01123451213450111110100( )

19、110101010110010vvvvvvvAGvvv12341223401000010()11011000vvvvvvA Gvv 對于有向圖的鄰接矩中每一行上1的個數(shù)是該點的射出度數(shù) ，而每列上1的個數(shù)是由該點射入度數(shù) ；對無向圖中，每行和每列上的1的個數(shù)則為點總度數(shù) ，因此，無向圖中全零行式全零列都說明該端為孤立點，而對有向圖中則不一定，除非對應該點的行和列都是零。應注意的是,在寫鄰接矩陳時，行和列上點的順序排列應相同。 權值矩陣 對具有n個點的簡單圖G，其權值矩陣為W(G)= 其中:現(xiàn)代通信網(wǎng)技術29 idv idv id vijn nwjivvvvpwjijiijij0無邊到有邊到 顯

20、然，權值矩陣與鄰接矩陣有類似性，無向簡單圖的權值矩陣是對稱的，對角線元素為零。有向簡單圖的權值矩陣不一定對稱，但對角線元素全為零。圖7.17的權值矩陣 和 分別為：現(xiàn)代通信網(wǎng)技術30 1W G 2W G12345121345036108.5305650810800()vvvvvvvW Gvvv12341223405073.5 5.6044.70()vvvvvvW Gvv現(xiàn)代通信網(wǎng)技術3.2路徑選擇路徑選擇 在進行通信網(wǎng)絡結(jié)構(gòu)設計和選擇路由時，經(jīng)常遇到以下問題，建立多個城市之間的有線通信網(wǎng)，如何確定能夠連接所有城市并使線路費用最小的網(wǎng)絡結(jié)構(gòu)；在一定網(wǎng)絡結(jié)構(gòu)下如

21、何選擇通信路由，怎樣確定首選路由和迂回路由等。這些問題就是路徑選擇或者路徑優(yōu)化的問題?？紤]到實際需要，這里只涉及無向簡單圖的路徑優(yōu)化。1 1、最小支撐樹、最小支撐樹 如前所述，若連通圖本身是一棵樹，其支撐樹往往不止一個，但滿足一定條件的權值和為最小的支撐樹至少存在一個。尋找最小支撐樹是常見的優(yōu)化問題?？煞譃閮煞N情況：一種是無限制條件的情況，另一種是有限制條件的情況。以下分別討論兩種情況下最小支撐樹的算法。 1. 無限制條件的情況 無限制條件下的最小支撐樹算法常用的有兩種：一種是順序取點的普列姆(prim)算法，簡稱P算法，另一種是順序取邊的克魯斯格爾(Kru skal)算法，簡稱K算法?，F(xiàn)代通

22、信網(wǎng)技術32(1) P算法P算法是一種順序取點的算法，其步驟如下。 0P：起始，任取一點 1jv作為子圖 1G= ，取最小的，把所連的點 1jv。比較 1G到G- 1G各邊的權值中 2jv并入 1G，得 2G= 1jv， 2jv 即： 111 2minj jj jj G Gdd 1P：對已得到r-1個點的子圖 1rG，比較 1rG中各點到G- 1rG中各點所有邊的權值，取最小的，即： 11minrrrijsji Gj G Gdd 2P：若rn，重復 1P，若r=n終止，即得最小支撐樹 nG現(xiàn)代通信網(wǎng)技術33例7.3 P算法計算圖7.18所示圖的最小支撐樹。圖7.18 最小支撐樹算法示例圖解：依

23、P算法可以順序得：1G1v=；= ；2G=3G4G5G1v1v1v1v2v5v2v2v5v2v4v5v4v；圖7.19 最小支撐樹示例圖現(xiàn)代通信網(wǎng)技術34P算法所得的樹必為最小支撐樹，這可證明(見講義）rGrG G11111236nrr nrnnn討論一下P算法的復雜性。從算法開始到終止共進行n-1步，每步須從r 個中的點與n-r個間的距離進行比較，求出最小 （7-13）者。可見第r步中要作r(n-r)-1次比較，由此得到P算法的計算量為：3n2n2n3n這是的數(shù)量級。P算法的比較是有重復的，若每次比較結(jié)果都記下來，則比較次數(shù)可降至數(shù)量級。當然這樣以來復雜性都屬于算法將簡單一些； 不過不論是

24、或多項式型，即當n很大時，一般均可借助于計算機來實現(xiàn)?，F(xiàn)代通信網(wǎng)技術35(2) K算法K算法是一種順序取邊算法，其步驟如下： 0K：把所有邊按非減順序排成有序的隊列。 1K：取最短的邊 ijd與相關的端構(gòu)成子圖 1G= iv。并在的， jv隊列中刪去這條邊。2K：設已取r條邊，r+1個點所構(gòu)成的子圖 rG，在所剩的邊隊列中取最短的邊，檢查加上這條邊看是否有環(huán)，也就是這個邊的兩個點是否已在rG中，若有環(huán)，刪去這條邊，繼續(xù)進行選取最短的邊，直到不形成環(huán)。3K：若rn-1，重復 2K；r=n-1，終止，即得所需的最小的支 撐樹。現(xiàn)代通信網(wǎng)技術36 這種算法的復雜性主要決定于把各邊排成有序的隊列。當原

25、圖中有m條邊時，可有m!種排法，相當于2log!m次比較。 對于n個點的圖，最大邊數(shù)是112n n 則復雜性為2lognn量級，所以也是多項式型的。這里忽略了檢查是否形成環(huán)的計算量，可證明這個量的量級低于2lognn當n很大時可以不計。用K算法所得的樹也可證明是最短的，即不存在另一支撐樹，其邊長之和比算得的更少，至多相等。證明見講義?，F(xiàn)代通信網(wǎng)技術372. 有限制條件的情況 有許多情況下，網(wǎng)內(nèi)n個站除了連通的要求外，還會提出一些其它要求，如在設計通信網(wǎng)絡結(jié)構(gòu)時，要求站間通信時的轉(zhuǎn)換次數(shù)不宜過多，某一條線路的話務量不能太大等。這類問題可歸結(jié)為在限制條件下求最小支撐樹。對于不同的限制條件，算法也就

26、有所區(qū)別，目前還沒有一般的有效算法。有兩種較常用的解決此類問題的方法，各有優(yōu)短點，這就是窮舉法和調(diào)整法。(1) 窮舉法 窮舉法就是先把圖中的所有支撐樹舉出來，再按條件篩選，最后選出最短的支撐樹。顯然這是一種最直觀的也是最繁復的方法，雖然可以得到最佳結(jié)果。但計算量往往很大。例如n點的全連通圖，經(jīng)計算可知。它的支撐樹數(shù)為 2nn個。隨著n的大，這數(shù)值將急劇增大，計算復雜性已屬于非多項式的難題(NP-Hard)，即使在高速計算機上也難于求解。因此，窮舉法只適用于點和邊均不大的情況?，F(xiàn)代通信網(wǎng)技術38(2) 調(diào)整法 調(diào)整法的思路是：先選定適當?shù)那笞钚≈螛涞姆椒?，如P算法或K算法，但在算法的每一步中要

27、判斷是否滿足限制條件并進行調(diào)整，直到最后得到支撐樹。這種算法的復雜性一般都是多項式型的，但不能保證取得最佳解而只能是準最佳解。 調(diào)整法的實現(xiàn)有許多，現(xiàn)用厄斯威廉算法，簡稱E-W算法 來說明這類算法的步驟。E-W算法是為計算機網(wǎng)絡設計而設計的一種算法。E-W算法開始以n個點作為n個部分，每次取一邊，使部分數(shù)逐漸下降；當部分數(shù)為1時，即得支撐樹。選邊的準則是取轉(zhuǎn)接損失最小的，相當于K算法中取最短邊。若這邊不滿足要求，繼續(xù)選以最小損失的邊，直到得到支撐樹為止?，F(xiàn)代通信網(wǎng)技術39算法步驟如下：0EW：起始，n個點的n個部分，鄰接陣為全零陣。 到各部分的距離 1EW：計算主機 1v1id和不在一個部分內(nèi)

28、的兩點之間的邊的轉(zhuǎn)接損失ijt2EW：選 ijt中的最小值為： * *,miniji ji jtt檢驗加入 *iv到 * jv的 邊后是否滿足條件。3EW：若部分數(shù)大于1，回到EW1，等于1，終止。 例7.5 自己看一下：現(xiàn)代通信網(wǎng)技術402 2 點間最短經(jīng)點間最短經(jīng)在通信網(wǎng)的網(wǎng)絡結(jié)構(gòu)確定后，任意兩點間的通信，首選路由應是它們間的最短徑，這就是求兩點之間的最短徑的問題。（1）. 指定點到其它各點的最短徑算法。給定圖G，已知所有邊的權值 dij求指定點 sv到其它定點的最短徑可用迪克斯(Dij Kstra)算法，簡稱D算法，這被認為是最有效的算法之一。 D算法的思路如下：D算法把點集分成兩組，已

29、選定點集pG和未選定點集pGG每個點都有一個標值iw對已選定點，這標值是sv到該點的最短徑長度。將pGG中徑長最短的點歸入pG然后再計算pGG中各點的iw與上次的iw相比較，取最小的，如此一直下去，直到pG中有n個點，所選定的標值就是最短徑長。現(xiàn)代通信網(wǎng)技術41D算法的步驟可歸納如下： 0D：設定 sv，得 pG= sv， 并選定 1w=0，暫定值 jw= ( jv( pGG1D：重新計算暫定值： *min,jpipjjiijvG GvGww wd 2D：取最小值： *minj G Gpijvww 將 jv并入 pG得新的 pG，若 pG中的點數(shù)為n，結(jié)束；否則1D返回無邊到有邊到jijiij

30、ijvvvvdd其中：iw是上次選定值，jw是上次暫定值。) 例7.6 用D算法求圖7.21中的 到其它各點的最短路徑和徑長。圖7.21 最短徑長 的 計算示例圖現(xiàn)代通信網(wǎng)技術421v解： (1) 選定1v得pG=1v，并選定1w=0，暫設jw=(j=2，3，7)(2) 重新計算暫定值*2w=min2w，112wd=min，0+0.5 =0.5*3w=min3w113wd， =min，0+2.0 =2.0*4w=min4w，114wd =min，0+1.5=1.5*5w=min5w，115wd=min，0+=*6w= =(3) 選定2w=min*2w*3w*4w*5w*6w*7w*7w=0.5

31、，并將2v選定，并入pG12,v v=，(4) 依次重復上述(2)、(3)過程，可得表7.1和圖7.22中粗線條所示的支撐樹。現(xiàn)代通信網(wǎng)技術43點最 短路徑徑長00.52.05.11v2v3v4v5v6v7v 1v12,v v13,v v14,v v125, ,v v v1256, , ,v v v v137,v v v表 7.1各點的最短路徑表7.1說明了1v到各點的最短路徑及其徑長，實際上就是以1v為樹根的連通圖G的一棵最小支撐樹。 D算法中每一個循環(huán)的暫定值的變化情況記錄了各最短徑的路由，D算法的運算量可估計如下: 在第k步時，要做(n-k)次加法，再做(n-k)次比較

32、可更新各點的暫定值；再做(n-k-1)次比較求最小值，共有3(n-k)-1次運算，則總的運算量大約為：現(xiàn)代通信網(wǎng)技術441n1) 1(23)(3knnkn(7-19)所以計算復雜性為2n量級，可以在計算機上實現(xiàn)?，F(xiàn)代通信網(wǎng)技術45(2). 所有點間最短徑的算法 求任意點之間的最短路徑，可以依次選擇每個點為指定點，用D算法做n次運算，但這樣做比較麻煩，一般認為比較好的一種算法是弗洛埃德(Floyd)算法，簡稱F算法。其實這種算法的原理和D算法一樣，只是用矩陣形式來表達，并進行系統(tǒng)化的計算。對于n個點，已知邊長 ijd的圖，順序計算各個nn的W陣和R陣，前者代表徑長，后者代表轉(zhuǎn)接路由?，F(xiàn)代通信網(wǎng)技

33、術46其步驟如下： 0F：置 W = 0ijn nW1F：已得 1kw和 1kR陣，求 kw和 kR中的元素如下： F2： kn重復F1： k=n終止1111111,minkijkijkikkijkijkijkijkkjkikkijkijwwrwwrrwwww若若(7-22)nnijrR00和 其中：jivvvvdwjijiijij00之間無邊和若之間有邊和若jiwwjrijijij或若若0000由上述步驟可見，F(xiàn)算法的基本思想是：現(xiàn)代通信網(wǎng)技術471kWkW是計算經(jīng)過kv轉(zhuǎn)接時是否會縮短徑長，如有縮短，更改ijw并在R陣中記下轉(zhuǎn)接的點，最后算得nW和nR中，就可得到任意兩點間最短徑長和最短路

34、徑需經(jīng)過的轉(zhuǎn)接路由。例7.7 用F算法計算圖7.21中任意兩點間的最短經(jīng)。解：首先寫出圖7.21 最短徑長計算結(jié)果示例圖0W和0R.現(xiàn)代通信網(wǎng)技術4812345671230456700.5 2.01.50.5005.03.11.504.01.25.00015.60vvvvvvvvvvWvvvv1234567123045670234000100056010005071000007023006002005070034060vvvvvvvvvvRvvvv求第一次修改矩陣12345671231456700.52.01.50.502.52.0 1.

35、29.22.02.503.55.03.504.01.25.00015.60vvvvvvvvvvWvvvv1234567123145670234000101156011015071110007023006002005070034060vvvvvvvvvvRvvvv矩陣中：現(xiàn)代通信網(wǎng)技術49110002332232113min,min,0.5 2.02.5wwwww110002442242114min,min,0.5 1.52.0wwwww110003443343114min,min,2.0 1.53.5wwwww求第二次修改矩陣2W和2R矩

36、陣中:現(xiàn)代通信網(wǎng)技術50221111551151225min,min,wwwww221111661161226min,min,wwwww7 .112 . 95 . 2 ,min,min126232136263236WWWWW7 . 32 . 15 . 2 , 5min,min125132135253235wwwww2 . 32 . 10 . 2 ,min,min125142145254245wwwww2 .112 . 90 . 2 ,min,min126142146264246wwwww求第三次修改矩陣： 33R和W矩陣中:1 . 55 . 30 . 2 ,

37、min,min237213217371317wWwww?，F(xiàn)代通信網(wǎng)技術518 . 61 . 37 . 3 ,min,min237253257375357wwwww6 . 51 . 35 . 2 ,min,min237223227372327wwwww求第四次修改矩陣：44R和W，由于經(jīng)轉(zhuǎn)接任意兩點均不會縮短，所以有：34WW34RR ，求第五次修改矩陣：矩陣中：4 . 87 . 67 . 1 , 7 . 9min,min456415416561516wwwww9 . 77 . 62 . 1 , 2 . 9min,min456425426562526wwwww 4 .107 . 67 . 3 ,

38、 7 .11min,min456435436563536wwwww。現(xiàn)代通信網(wǎng)技術529 . 97 . 62 . 3 , 2 .11min,min456445446564546wwwww5 .138 .67 .6 , 6 .15min,min457465467576567wwwww，即要經(jīng)過 經(jīng)點轉(zhuǎn)接，任意點路徑均不會改變，所以有：從和。中，可以找到任意兩點間最短路徑長度和路由，例如，從到的最短路徑長是6.8，這可以從矩陣中看出。從矩陣找到轉(zhuǎn)接，再看135r，即要經(jīng)過1v轉(zhuǎn)接，215r525r，則其路由是。F算法的運算量決定于式(7-22)，可知為現(xiàn)代通信網(wǎng)技術533n量級，也是可行的。在下列

39、情況下，F(xiàn)算法可以簡化，從而減少計算量。 若圖G中有度數(shù)為1的點，可把這些點去掉再做計算。設sv是這些點中一個，只與iv相連接，則sv與其它點的最短路徑必經(jīng)過iv，所以它與其它點jv間的最短徑必為：sjsiijwdw (7-23)其中ijw是去掉sv等點后用F算法求得的最短徑長。 圖G中所有度數(shù)為2的點也可按上述方去掉，設sv長度數(shù)為2，它只與iv和jv相連接，則sv其它點kv的最短徑長為：min,sksiiksjjkwdwdw(7-24) 若圖G里一個疏稀連通圖，可將全圖分成幾個部分進行計算，然后合并起來。現(xiàn)代通信網(wǎng)技術543. 次短徑和可用徑（1） 次短徑 在實際問題中，除了求最短徑外，往

40、往需要求次短徑和可用徑，例如當網(wǎng)內(nèi)點間的主路由業(yè)務量溢出或發(fā)生故障時，就需尋找次短徑或其它可用徑作為迂回路由。 圖7.24 次短徑和可用徑示例圖圖7.24所示兩點sv與tv間有三條徑，即：1Psv1v2vtv：2P：svtv3v2v是最短徑，4v3P：sv5v6vtv若1P2P與1P沒有公共邊，但有公共點，稱1P與2P為不共邊徑或分離徑。1P2P與 除了起點和終點外，沒有公共點，現(xiàn)代通信網(wǎng)技術55找與最短徑邊分離的次短徑。用F算法或D算法得到最短徑后，可從圖中去掉這些徑的所有邊，然后在剩下的圖中用D算法求 sv和 tv間的最短徑，這就是所要求的次短徑。 找一最短徑點分離的次短徑。在這種情況下，

41、求得最短徑后，應把這徑中的所有中間點去掉，在余下的圖中求 vs和vt間的最短徑，就得到與最短徑點分離的次短徑。這種方法也可繼續(xù)進行下去，直到不存在徑，從而得到一系列點分離的次短徑。 稱為不共點徑或點分離徑。雖然，點分離徑必為邊分離徑，反之則不一定。由此可見有兩類次短徑問題。這種方法還可以計算下去，可把次短徑的所有邊再去掉，在剩下的圖中求最短徑，就得到次短徑的邊分離次短徑，直到剩下的圖中sv和 tv間已無徑。需說明的是，去掉一個點，同時也去掉與之關聯(lián)的邊，但去掉邊時要保留這條邊的兩個點?，F(xiàn)代通信網(wǎng)技術56（2） 可用徑 在某些應用中，要求找一些滿足某種限制條件的徑而并不要求它們的點分離或徑分離，

42、這批徑稱為該限制條件下可用徑。 限制條件可以各式各樣，解法也就不同。也可能要同時滿足幾種限制條件，這時可以先用一個條件求可用徑，再從這些徑中篩選出滿足其條件的徑就是所需的可用徑。現(xiàn)代通信網(wǎng)技術574. 網(wǎng)的中心和中點 從前述的點間最短徑出發(fā)，可定義網(wǎng)的中心、中點和直一個點vi在網(wǎng)中的位置可用最長的最短徑長ti表示，即maxiijjtwti的最小值對應的點稱為網(wǎng)的中心，即 在距離的意義上來說，若按最短徑走，從網(wǎng)中心到最遠點去所走的路徑比其它點為短，所以網(wǎng)中心作為維修中心和服務中心最為有利的。這一結(jié)論不但對通信網(wǎng)有用，對其它網(wǎng)也是如此。(7-25)iiittmin*(7-26)網(wǎng)的中點可定義為平均

43、最短徑長為最小的點，即：iijjsw (7-27)*miniiist (7-28)其中 *is其網(wǎng)的中點。如果邊的權均為1，網(wǎng)的中點就是現(xiàn)代通信網(wǎng)技術58.平均轉(zhuǎn)接次數(shù)最少的點，所以網(wǎng)的中點可用作全網(wǎng)的交換或控制中心。還可定義網(wǎng)的直徑D為網(wǎng)內(nèi)兩點間最短徑長的最大值，即:,maxiji jDw(7-29)以前面已求得W陣的圖7.21為例可得：網(wǎng)中心是 5v,網(wǎng)中點是1v,直徑是13.5?，F(xiàn)代通信網(wǎng)技術597.1.3 7.1.3 站址選擇站址選擇 上面我們討論的最小支撐樹、最短徑和網(wǎng)中心等，都是在網(wǎng)內(nèi)所有點是預先規(guī)定，不能另設新點。實際通信網(wǎng)中，并不排除設計一些點；除了用戶點是客觀需求外，交換站是

44、可以選擇的。各交換點之間的匯接點或高一層的交換點也是如此。這樣一來，最小支撐樹可以更短，網(wǎng)中心所對應的平均最短徑長也可以更短，倘若只允容許另設一個點，可稱為單中點問題；允許設K個點，就是K中點問題。下面先討論這兩類問題，而后研究站址選擇的優(yōu)化問題。一、一、 單中位點單中位點設有n個用戶點，它們的平面座標分別為( xi,yi) ，i=12，n。又設各點的加權系數(shù)為 wi可代表該用戶所需的聯(lián)線數(shù)或者其它需求的大小。單中點問題就是要找一個中點的座標 (xq,tq),使得代價函數(shù)： iqiiLwd為最小。 (7-30)其中現(xiàn)代通信網(wǎng)技術60qid是中點與用戶之間的距離測度。根據(jù)問題的性質(zhì)，這種測度可以

45、有不同的形式，最常見的是歐氏距離，即：22qiiqiqdxxyy(7-31)但也有以距離平方作為測度的，即：22qiiqiqdxxyy(7-32)這適用于廣播系統(tǒng)的發(fā)射點位置選擇，因為每個方向的接收功率是與歐氏距離平方成反比的，為了有一定的接收功率，就是要求發(fā)射點的功率要依上述qid的正比增加，所以(7-30)式中的L最小，就是發(fā)射總功率最小。蜂窩狀小區(qū)的移動通信也有類似的情況。再有一種矩形距離，即：qiqixxyyqid (7-33)這是考慮到在城市中放線時，常需沿街道鋪設。若街道是方格形的，那么從中點到用戶的線路長度按(7-33)式計算。現(xiàn)代通信網(wǎng)技術61 求中點座標的方法： （1）. 歐

46、氏距離的情況qiiiqqixxLwxdqiiiqqiyyLwyd2223qiiiqqiyyLwxd2223qiiiqqixxLwyd23qiqiiiqqqixxyyLwx yd 用二元泰勒級數(shù)展開，其二階增量為： 22222222qqqqqqqqLLLxxyyxx yy 23qiqqiqiqiyyxxxywd還可提出一種連續(xù)分布的情況。當用戶點數(shù)目很大，用有限數(shù)n來計算很困難，可假設用戶數(shù)量按(x，y)連續(xù)分布的，則在(x，y)點附近的用戶數(shù)是(x，y)xy。(x，y)稱為(x，y)點上用戶點的密度。此時(7-30)式成為：,qLx y dx y dxdy (7-34)，；，；0現(xiàn)代通信網(wǎng)技術

47、62 則函數(shù)L是下凸的，也就是一階偏導為零可得L的極值，即當： iiq iqiq iiiq iqiq iw xdxwdw ydywd時，L是極小。 (7-35)但(7-35)式是一個隱函數(shù)式，不能直接計算所需的qx和qy，因qid中隱含有和qxqy但是可用它來迭代而求解。一般情況下，這種迭代算法是收斂的。（2）. 平方距離的情況當采用歐氏距離的平方和作為距離測度時，得 ：現(xiàn)代通信網(wǎng)技術63 ，2iqiiqLw xxx2iqiiqLwyyy置偏導為零，得： iiqiiiqiw xxww yyw這個式的解是顯式，可直接算出中點的位置。 (7-36)而這樣得到的中心必使L值最小，也是易于用二次取導證

48、明的。實際上，這個中點就是iw為權的各點iv的重心。3. 矩形線距離情況這種情況下，導數(shù)將出現(xiàn)不連續(xù)點。即:qiqxxxiqiqiqxxxxxx不定11現(xiàn)代通信網(wǎng)技術64由于當,qiqiiii xxi xxqLwwx,qiqiiii yyi yyqLwwyL的極值應出現(xiàn)在：,1,11:21:2qiqiqiqiqiii xxi xxiiqiii yyi yyiixwwwywww，qx=ix時，0qixx，這已不影響L值，所以可以不計。把式(7-33)式代入(7-30)式并對qyqx和求偏導，可得：上式的含義是：qx的選擇應能使qx的右邊所有點的它的左邊的所有點的權之和。和qy和qy權之和等于 (

49、7-37)在實際應用中式(7-37)求中位點會遇到以下幾種情況； .現(xiàn)代通信網(wǎng)技術65iw是偶數(shù)，而且可以沿橫軸和縱軸各等分兩部分，這時可直接用(7-37)式求中位點，但中位點不是唯一的，如圖7.25(a)所示。在斜線范圍內(nèi)均能使L最小。圖中各點旁所標數(shù)字是權值iwiw是偶數(shù)但只能沿縱軸等分為兩部分，這時中位點iw點是一個點(qx，qy)可能與某用戶點的(qx) 相同； 如圖，iw必定與某點的ix相等。而qy則可與y軸平行一條線段上，如圖7.25(b)所示的ab粗實線。同理若是偶數(shù)只能沿橫軸等分為兩部分，則qy與某點的iy相等，而qx可在與x軸平行的一條線段上，如圖7.25(c)中所示的粗實線

50、ab。是偶數(shù)但橫軸和縱軸均不能等分或iw是奇數(shù)時，中位ixiy7.25(d)所示的a點?，F(xiàn)代通信網(wǎng)技術66圖7.25 單中位點示意圖現(xiàn)代通信網(wǎng)技術674. 用戶連續(xù)分布的情況 求解方法基本上與前述有限用戶點的情況相同。 對于歐氏距離有： 22222222,qqqqqqqqqqxx yxxyydxdyxx yxxyydxdyyx yxxyydxdyyx yxxyydxdy的迭代公式。 也就是對L求qx和qy的偏導數(shù)并置零，解得qx和qy值即可。 (7-38)對于平方距離有： dxdyyxdxdyyxydxdyyxdxdyyxxqq),(),(y),(),(x (7-39)的求重心公式。 現(xiàn)代通信

51、網(wǎng)技術68.對矩陣形線距離有： ,qqqqxqxyqyxdxdxx y dydxx y dyydxdxx y dydxx y dy 的求解等式。(7-40)在用連續(xù)分布的用戶點來求解時，常會提出選擇最佳服務區(qū)域的問題。當所劃的區(qū)域較小，建一個交換局的代價分配到每一個用戶的份額增大；反之，所劃的區(qū)域較大，遠距離線路鋪設費用較多，也會使這份額增大。如何劃分一個交換局的服務區(qū)域，才能使每一個用戶所費的代價最小，是一個有實際意義的問題。不失一般性，可設x=0，y=0處建一個交換局，其費用為C；從這個局到點(x，y)每用戶的線路建設一個費用和維護費用為f(x，y)；若服務區(qū)域是A時，總費用將為：LtM要

52、使t達到極值，必有：20M L L MtM 或LLMM (7-43)若區(qū)域為現(xiàn)代通信網(wǎng)技術69*A時得t的極值*t，則有*,AAx y fx y dxdyL ALtMM Ax y dxdy或*,tf x y其中f(x，y)是*A的邊界上的某一點(x，y)的f值。由于*t是一個定值，所以使t取極值的區(qū)域邊界上f(x，y)也必為常數(shù)，令區(qū)域*A在x軸上的截距為a,則邊界線的方程為：,0fx yf a當函數(shù)f為已知時，從上式解出y，可寫成,yq x a因此，只要能找到截距a，最佳區(qū)域的問題也就解決了。其實在(7-43)式中，L和M都是a的函數(shù)，0dtda就可解出a的值。由于L和M都是A的遞增函數(shù)。上

53、面求得的t的極值也就是最小值。 (7-44)(7-45) (7-46)現(xiàn)代通信網(wǎng)技術702 2 多中位點問題多中位點問題 單中位點只解決了用戶數(shù)目和地理范圍不太大時的選址問題，當用戶數(shù)目增多，或地理分散，往往要求分成幾個群體，每個群體有一個中位點，這時不僅要考慮用戶線費用，還要考慮中繼線費用及各個交換中心的建設費用。這時的目標函數(shù)為：111mmnimijiijjjiLfqC w d (7-47)式中：jf建第j個交換中心的費用，j=1,2,，m；mq設m個交換中心時中繼線的總費用；iw第i個用戶點的加權系數(shù)；ijd第i有用戶點與第j個交換中心之間的用戶線長度。ijc連線系數(shù)。間無用戶線與間有用

54、戶線與jijicij01現(xiàn)代通信網(wǎng)技術71(2). m確定后各中位點的位置當中位點數(shù)目m選定后，交換中心的費用是個常數(shù)，不計中繼線的費用，目標函數(shù)變?yōu)椋?11mnijiijjiLC w d(1). 服務區(qū)的劃分假設中位點數(shù)目已經(jīng)確定，服務區(qū)的劃分應使得每用戶的平均費用最小，通過求極值的方法可得到最佳服務區(qū)的形狀，這個問題在上面已討論過。求解步驟如下：(1)任選m個點（xoi,yoi)作為中位點的位置，劃分m個區(qū)域，將所有用戶分給距其最近的中位點所在區(qū)域，計算用戶線費用 L1。(2) 用求單中位點的方法重新確定各中位點的位置，并計算用戶線費用 L2(3) 比較 L1和L2，若兩者相等或接近就結(jié)束

55、。否則返回(1)重新計現(xiàn)代通信網(wǎng)技術72 例7.8 某地區(qū)有16個用戶點，如圖7.26示，各點的數(shù)字代表用戶個數(shù)，已知要劃分三個交換區(qū)，問應如何確定各交換中心的位置(采用矩形線距離測度)?解：（省略）算。也可按改變后的各中位點位置重新劃分區(qū)域，仍然按最近距離的原則將幾個用戶分給m個中位點，如分區(qū)沒有改變結(jié)束，否則返回步驟(2)。圖7.26 三個中位點的問題示例圖現(xiàn)代通信網(wǎng)技術733. 中位點數(shù)目m的確定 確定中位點的數(shù)目m應使目標函數(shù)式最小，可依次求單中位點，兩個中位點、三個中位點直到m個中位點的解，其中使L為最小的值即為所求。所使用的方法就是前面介紹的單中位點和多中位點的求解方法。在計算總費

56、用時，除了計算用戶線的費用外，還要計算建立m個交換中心所需要的局內(nèi)交換設備的費用與場地及建筑物費用，即 1mijf和中繼線費用 mq電話通信網(wǎng)的局所數(shù)目m與費用L之間的關系可用圖7.27中的曲線表示，0m為最佳局所數(shù)目。從圖中可以看出。a、用戶線的費用隨m的增加而下降。因為所建的交換局越多，交換區(qū)的范圍將越小，用戶線的長度會縮短，因而，減少了用戶線費用。當用戶線的單位價格上漲時，總費用的極限點會向左移動，即最佳局所數(shù)0m增大。b、現(xiàn)代通信網(wǎng)技術74中繼線的費用隨m的增加而上升。因為交換局越多，局間中繼線的總長度和費用就會增加，當中繼線的單價上升時，中繼線的費用曲線會向上彎曲，0m將減小。C、交

57、換設備的費用隨m的增加而增加。因為當交換設備單價上升，場地和建筑物費用上漲時，這兩條曲線的斜率將增大，結(jié)果使0m將減小。值得指出的是：由上述可見最佳局所數(shù)目0m的求解是一個多元函數(shù)，它和m確定后確定各中位點位置一樣，也只能是準最佳結(jié)果。現(xiàn)代通信網(wǎng)技術757.1.4 7.1.4 流量分配流量分配 網(wǎng)的作用主要是將業(yè)務流量從源點至送宿點。為了充分利用網(wǎng)絡資源，包括線路和轉(zhuǎn)接設備等，總希望合理地分配流量，以使從源到宿的流量盡可能的大，傳輸代價盡可能小等，流量分配的優(yōu)劣將直接關系到網(wǎng)的使用效率和相應的經(jīng)濟效益，是網(wǎng)運行的重要指標之一。 網(wǎng)內(nèi)流量的分配并不是任意的，它受限于網(wǎng)的拓撲結(jié)構(gòu)，邊和點的容量，所

58、以流量分配實際上是在某些條件下的優(yōu)化問題。 在通信網(wǎng)中，流量是指傳信率，例如幾路電話，幾比特每秒數(shù)據(jù)，廣義地說，是與邊有關的某種權值。在實際問題中，通信流量具有隨機性，為了簡化，本節(jié)中只限于平均流量，即被認為是常量。至于它的隨機性，將在下節(jié)中分析。 下面先從網(wǎng)內(nèi)流量優(yōu)化的一般問題開始，然后分別討論最大流量和最佳流量分配的算法?，F(xiàn)代通信網(wǎng)技術76一、一、 流量優(yōu)化流量優(yōu)化 每條邊能通過的最大流量稱為邊的容量，用cij表示；實際上這條邊上的流量記為fij ,一組流量的安排fij 稱為網(wǎng)內(nèi)的一個流。若這個流使從源點到宿點的總流量F，則這些 fij必須滿足下述兩個限制條件。 非負性和有限性 連續(xù)性：

59、jvjviiijijvvff其他為宿點為源點0sisivvFvvF0ijfijc(7-49) (7-50)具有m條邊、n個點的圖共有2m+n-1個限制條件，其中包括m個非負性條件、m個有限性條件和n-1個連續(xù)條件。(7-50)式中有n個等式對應于n個點，但是有一個不是獨立的，所以只有n-1個限制條件是獨立的。現(xiàn)代通信網(wǎng)技術77一般有兩種優(yōu)化可行流的問題。(1)最大流問題。變更可行流中各fij值以使總量F最大。實質(zhì)上就是在式(7-49)式的m個條件和(7-50)式中的vi不是vs和vt的(n-2)個條件下，使目標函數(shù)F最大的線性規(guī)劃問題。 (2) 最佳流或最小費用流問題。當每條邊除了有容量 ci

60、j的規(guī)定外，尚有費用aij ，表示單位流量所需的費用。給定F，選擇路由分配這個流量，也就是調(diào)整fij以使總費用為： ijijijeEa f為最小。 滿足(7-49)式和(7-50)式的流稱為可行流。不同的流量分配可得不同的可行流。一般有兩種優(yōu)化可行流的問題。 (7-51)現(xiàn)代通信網(wǎng)技術782 2、 流量優(yōu)化算法流量優(yōu)化算法 最大流量的算法常用標志算法或稱M算法。 這種算法的基本思想是從一個可行流出發(fā)，搜索每一條從源到宿點的路是否可增流。每找到一條可增流的路，就可進行增流，總流量得以擴大，直至不存在可增流路，即得到源宿點的量大流量值和相應的流量分配。 當所有邊上流量都是零時，這個流必為可行流。通