第7章通信網(wǎng)絡(luò)設(shè)計基礎(chǔ)

1、第第7 7章章 通信網(wǎng)絡(luò)設(shè)計基礎(chǔ)通信網(wǎng)絡(luò)設(shè)計基礎(chǔ)主要內(nèi)容主要內(nèi)容 7.1 通信網(wǎng)絡(luò)結(jié)構(gòu)設(shè)計基礎(chǔ) 7.2 網(wǎng)絡(luò)流量設(shè)計基礎(chǔ)7.1.2 7.1.2 最短路徑最短路徑7.1.1 7.1.1 圖論基礎(chǔ)知識圖論基礎(chǔ)知識7.1.3 7.1.3 站址選擇站址選擇通信網(wǎng)絡(luò)結(jié)構(gòu)設(shè)計基礎(chǔ)7.1 圖論基礎(chǔ)知識7.1.1 1 1圖的基本概念圖的基本概念（1 1）圖的定義）圖的定義 設(shè)有點(diǎn)集 和邊集 ，如果對任一邊 ，有V中的一個點(diǎn)對 與之對應(yīng)，則圖可用有序二元組 表示，記為 （2 2）點(diǎn)的度數(shù)）點(diǎn)的度數(shù) 與同一端點(diǎn)相關(guān)聯(lián)的邊的個數(shù)稱為此端點(diǎn)的度數(shù)或次數(shù)，記為 。（3 3）鏈路、路徑與回路）鏈路、路徑與回路u鏈路對于圖

2、 ，其中 條邊和與之關(guān)聯(lián)的端點(diǎn)依次排成點(diǎn)和邊的交替序列，則稱該序列為鏈路。邊的數(shù)目 稱為鏈路的長度。u路徑無重復(fù)的點(diǎn)和邊的鏈路稱為路徑。u回路如果路經(jīng)的起點(diǎn)和終點(diǎn)重合，則稱為回路。.,21nvvvV,21meeeEEek),(jivv),(EV),(EVG )(ivd),(EVG )2(kk 圖論基礎(chǔ)知識7.1.1,46553844331vevevevevev,5532211vevevev,175532211vevevevev，長度為5；，長度為3；，長度為4。 路徑：回路：鏈路：圖7-3 有自環(huán)與并行邊的圖圖論基礎(chǔ)知識 7.1.1另外還有兩個概念：自環(huán)兩個端點(diǎn)重合為一點(diǎn)的邊稱為自環(huán)。例如圖7

3、-3中的 ；并行邊與同一對端點(diǎn)關(guān)聯(lián)的兩條或兩條以上的邊稱為并行邊。例如圖7-3中的 和 為并行邊。4e8e9e圖論基礎(chǔ)知識 （4 4）圖的分類圖的分類 有限圖和無限圖 當(dāng)集合V和E都是有限集時，所構(gòu)成的圖稱為有限圖；否則就稱為無限圖。 簡單圖和復(fù)雜圖 沒有自環(huán)和并行邊的圖稱為簡單圖；有自環(huán)和并行邊的圖稱為復(fù)雜圖。 無向圖與有向圖 設(shè)圖 如果任一條邊 都對應(yīng)的是無序點(diǎn)對 ，則稱G為無向圖，如圖7-4（a）所示。 設(shè)圖 如果任一條邊 都對應(yīng)一個有序點(diǎn)對 ，則稱G為有向圖，如圖7-4（b）所示。),(EVG 7.1.1ke),(jivv),(EVG kejivv ,圖論基礎(chǔ)知識 7.1.1例7-1

4、寫出圖7-4（a）和（b）的點(diǎn)集、邊集和權(quán)的值圖7-4 無向圖和右向圖圖論基礎(chǔ)知識 有權(quán)圖與無權(quán)圖 設(shè)圖 ，如果它的每一條邊 都賦以一個實數(shù) ，則稱圖G為有權(quán)圖或加權(quán)圖；否則為無權(quán)圖。 連通圖與非連通圖 設(shè)圖 ，若圖G中任意兩個點(diǎn)之間至少存在一條路徑，則稱G為連通圖；否則稱G為非連通圖。（5 5）子圖的概念）子圖的概念 設(shè)有圖 和圖 ，若 ，即圖 的點(diǎn)集和邊集分別為圖 的點(diǎn)集和邊集的子集，則稱圖 是圖 的子圖。 由圖的定義可以看出，任何圖都是自己的子圖。另外還有兩種子圖：真子圖不包含原圖的所有邊的子圖是真子圖。生成子圖包含原圖的所有點(diǎn)的子圖就是生成子圖。),(EVG 7.1.1kekp),(E

5、VG ),(EVG ),(EVGEEVV,GGGG圖論基礎(chǔ)知識7.1.12 2樹樹（1 1）樹的基本概念）樹的基本概念 樹的定義 一個無回路的連通圖稱為樹樹。樹中的邊稱為樹枝樹枝。樹枝有樹干和樹尖之分：若樹枝的兩個端點(diǎn)都至少與兩條邊關(guān)聯(lián)，則稱該樹枝為樹干樹干；若樹枝的一個端點(diǎn)僅與此邊關(guān)聯(lián)，則稱該樹枝為樹尖，并稱該端點(diǎn)為樹葉樹葉。 樹的分類 常見的樹的種類有三種：根樹根樹、星樹星樹和線樹線樹。 樹的性質(zhì)l具有n個點(diǎn)的樹共有n-1個樹枝；l樹中任意兩個點(diǎn)之間只存在一條路徑；l樹是連通的，但去掉任一條邊便不連通，即樹是最小連通圖；l樹無回路，但增加一條邊便可得到一個回路；l任一棵樹至少有兩片樹葉，也

6、就是說樹至少有兩個端的度數(shù)為1。圖論基礎(chǔ)知識7.1.1（2 2）圖的支撐樹）圖的支撐樹支撐樹的概念如果一棵樹T為一個連通圖G的子圖，且包含G中所有的點(diǎn)，則稱該樹為G的支撐樹，也叫生成樹。只有連通圖才有支撐樹。支撐樹的邊樹枝集，支撐樹外的邊連枝集一個連通圖有不只一棵支撐樹（除非圖本身就是一棵樹）。 圖的階和空度 連通圖G的支撐樹的樹枝數(shù)稱為圖G的階，記為。若圖G有n個端點(diǎn)，則它的階為n-1。 連通圖G的連枝數(shù)稱為圖G的空度，記為。當(dāng)圖G有m條邊時，其空度為=m-n+1。顯然+ =m。圖論基礎(chǔ)知識7.1.13 3圖的矩陣表示圖的矩陣表示（1 1）完全關(guān)聯(lián)矩陣與關(guān)聯(lián)矩陣）完全關(guān)聯(lián)矩陣與關(guān)聯(lián)矩陣 完全

7、關(guān)聯(lián)矩陣是表示點(diǎn)與邊關(guān)聯(lián)性的矩陣。一個具有n個點(diǎn)、m條邊的圖G的完全關(guān)聯(lián)矩陣M(G)，是以每點(diǎn)為一行、每邊為一列的nm矩陣，即 mnijmGM)(01mij不關(guān)聯(lián)與關(guān)聯(lián)與jijievev011mij不關(guān)聯(lián)與的終點(diǎn)是的起點(diǎn)是jijijievevev 對無向圖 對有向圖 （7 7-4-4）（7-37-3）圖論基礎(chǔ)知識7.1.1 例例7-2 7-2 求圖7-12(a)和(b)的完全關(guān)聯(lián)矩陣。圖圖7-12 7-12 矩陣?yán)}圖矩陣?yán)}圖 圖論基礎(chǔ)知識 7.1.1解解 1e2e3e4e5e6e7e )(1GM54321vvvvv000110011001100110001000100101010011e2

8、e3e4e5e6e)(2GM4321vvvv001101100110010111001001圖論基礎(chǔ)知識圖論基礎(chǔ)知識 0100110101010110010111110)(1GA7.1.1nG)(GAnnnnijaGA)(01ijajivvvvjiji無邊，或到有邊到（2 2）鄰接矩陣）鄰接矩陣鄰接矩陣是表示點(diǎn)與點(diǎn)之間關(guān)系的矩陣。對于一個具有個點(diǎn)的圖 ,其鄰接矩陣是方陣，即 其中 （7-5）0001101101000010)(2GA 圖論基礎(chǔ)知識圖論基礎(chǔ)知識.1 nGnnijwGW)(0ijijpwjivvvvjiji無邊到有邊到（3 3）權(quán)值矩陣）權(quán)值矩陣個點(diǎn)的簡單圖，其權(quán)值

9、矩陣為 其中 （7-6）具有 最短路徑最短路徑.21.1.最小支撐樹最小支撐樹權(quán)值之和最小的那棵支撐樹稱為最小支撐樹。（1 1）求無限制條件的最小支撐樹的方法）求無限制條件的最小支撐樹的方法Kruskal方法（K方法）利用K方法求最小支撐樹的步驟為：K0：將連通圖G中的所有邊按權(quán)值遞增（或非減）的次序排列（如果有兩條以上邊的權(quán)值相等，則這些邊可以任意次序排列）。K1：選取G中權(quán)值最小的邊為樹枝，然后每下一步從G中所有留下邊中選取與前次選出的諸邊不構(gòu)成回路的另一條最短邊（如有幾條權(quán)值相同的邊，可依次選?。2：這樣繼續(xù)下去，一直選夠n-1條邊就構(gòu)成圖G的最小支撐樹。 iv最短路

10、徑最短路徑.2Prim方法（P方法）P方法的思路：任意選擇一個點(diǎn) ，將它與 相連，同時使具有的權(quán)值最小，再從 、 以外的其他各點(diǎn)中選取一點(diǎn) 與或 相連，同時使所連兩點(diǎn)的邊具有最小的權(quán)值，重復(fù)這一過程，直至將所有點(diǎn)相連，就可得到連接n個節(jié)點(diǎn)的最小支撐樹。P方法具體步驟為：參考書上jvivjivv ,ivjvkvivjv（2 2）求有限制條件的最小支撐樹的方法求有限制條件的最小支撐樹的方法求有約束條件的最小支撐樹的方法簡單說來是這樣的：先按上述所介紹的K方法或P方法求出無約束條件的最小支撐樹，然后根據(jù)所給的約束條件，對網(wǎng)絡(luò)結(jié)構(gòu)進(jìn)行調(diào)整，使之既滿足約束條件，又盡量接近最小支撐樹。 s

11、v最短路徑最短路徑.22.點(diǎn)間最短距離（1）指定點(diǎn)到其它各點(diǎn)的最短路徑算法Dijkstra算法(簡稱D算法)D算法的具體步驟：lD0：設(shè)定 ，得 ， ， lD1：計算暫設(shè)值為 其中 是上一次某一點(diǎn)到 的最小距離的設(shè)定值， 是上一次的暫設(shè)值。lD2：取最小值將 并入 得新的 。若 中的點(diǎn)數(shù)為n，結(jié)束；否則返回D1。sPvG 0sw)(PjjGGvw),(min*ijijGvGGvjdwwwPiPjiwswjw*minjGGviwwPijvPGPGPG nnijwW00最短路徑最短路徑.2（2）任意兩點(diǎn)之間的最短路徑算法Floyd算法(簡稱F算法)對于n個點(diǎn)、各邊權(quán)

12、值 ，的圖G,順序計算圖G的權(quán)值（徑長）矩陣W和路由矩陣R, F算法的具體步驟如下：lF0：徑長矩陣 ，路由矩陣 ，其中式中 為邊 的權(quán)值。ijdnnijrR000ijijpwjivvvvjiji無邊到有邊到ijp),(jivv00jrijjiwwijij或00 1kW最短路徑最短路徑.2F1：已知 和 矩陣，求 和 矩陣的元素如下：（3）次短路徑算法 首選路由的業(yè)務(wù)量出現(xiàn)溢出或發(fā)生故障時，就需要尋找次短徑作為首選路由的第一、第二迂回路由。1kRkWkR),min(111kkjkikkijkijwwwwkrrkijkij111kijkijkijkijwwww ),(00yx站址

13、選擇站址選擇.3 通信網(wǎng)中，我們可能設(shè)立新的交換局，新的交換局可設(shè)立一個或多個，在數(shù)學(xué)上是求單中位點(diǎn)或多中位點(diǎn)的問題。1 1單中位點(diǎn)單中位點(diǎn)（1 1）距離測度）距離測度設(shè)單中位點(diǎn)的坐標(biāo)為 ，有n個用戶點(diǎn)，它們的平面坐標(biāo)為 令 表示各用戶點(diǎn)與中位點(diǎn)之間的距離測度，有兩種距離測度方法，即歐氏距離測度和矩形線距離測度。歐氏距離測度為矩形距離測度為。，niyxii321,),(0id20200)()(yyxxdiiiiiiyyxxd000ip),(00yx站址選擇站址選擇.3（2）單中位點(diǎn)位置的確定只討論矩形線距離的情況。 令 表示加權(quán)系數(shù)，可代表用戶點(diǎn)用戶數(shù)或線路費(fèi)用

14、。單中位點(diǎn)就是找到 ，使得代價iiidpL0最小的點(diǎn)iiiiyyiiyyiixxiixxiippyppx000000： 中位點(diǎn)的選擇應(yīng)能使 x0左邊點(diǎn)的加權(quán)系數(shù)之和等于x0右邊各點(diǎn)加權(quán)系數(shù)之和； y0上邊所有點(diǎn)的加權(quán)系數(shù)之和等于y0下邊各點(diǎn)加權(quán)系數(shù)之和。站址選擇站址選擇.3圖7-18 單中位點(diǎn)示意圖站址選擇站址選擇.32.多中位點(diǎn)（1）服務(wù)區(qū)的劃分歐式距離測度矩形距離測度圖7-19 最佳服務(wù)區(qū)ijimjniijmmjjdpCgfL111jfmg站址選擇站址選擇.3（2）各中位點(diǎn)位置的確定目標(biāo)函數(shù) 式中， 為建第j個交換中心的費(fèi)用，j=1,2,.,

15、m; 為設(shè)m個交換中心時中繼線的總費(fèi)用； 為第i個用戶點(diǎn)的加權(quán)系數(shù)，i=1,2,n; 為第i個用戶點(diǎn)與第j個交換中心之間的用戶線長度； 為連線系數(shù)，即ipijdijC01ijC線線戶戶用用無有間間與與jjiiijimjniijdpCL11站址選擇站址選擇.3（2）各中位點(diǎn)位置的確定 當(dāng)中位點(diǎn)的數(shù)目m確定后，交換中心的費(fèi)用是個常數(shù)，若不再計中繼線的總費(fèi)用，目標(biāo)函數(shù)式變?yōu)椋呵蠼獾牟襟E如下：lM0:任選m個點(diǎn) 作為各中位點(diǎn)的位置，劃分m個區(qū)域，將所有用戶點(diǎn)分給距其最近的中位點(diǎn)所在區(qū)域，計算用戶線費(fèi)用L1。lM1:用求單中位點(diǎn)的方法重新確定各中位點(diǎn)的位置，并計算用戶線費(fèi)用L2。lM2:

16、比較L1與L2，若兩者相等或接近相等就結(jié)束；否則，返回步驟M0。),(00jjyx站址選擇站址選擇.3（3）中位點(diǎn)數(shù)目m的確定 確定中位點(diǎn)數(shù)目m應(yīng)使目標(biāo)函數(shù)式最小，可依次求單中位點(diǎn)、2個中位點(diǎn)、3個中位點(diǎn)直至m個中位點(diǎn)的解，其中使L為最小的m值即為所求。ijimjniijmmjjdpCgfL111站址選擇站址選擇.3（3）中位點(diǎn)數(shù)目m的確定 確定中位點(diǎn)數(shù)目m應(yīng)使目標(biāo)函數(shù)式最小，可依次求單中位點(diǎn)、2個中位點(diǎn)、3個中位點(diǎn)直至m個中位點(diǎn)的解，其中使L為最小的m值即為所求。ijimjniijmmjjdpCgfL111站址選擇站址選擇.37.2.2 M/M

17、/17.2.2 M/M/1排隊系統(tǒng)模型排隊系統(tǒng)模型7.2.1 7.2.1 排隊論基本概念排隊論基本概念網(wǎng)絡(luò)流量設(shè)計基礎(chǔ)7.2排隊論基本概念排隊論基本概念.1（1）排隊論與排隊系統(tǒng)的概念 由于顧客到達(dá)的數(shù)目和要求提供服務(wù)的時間長短都是不確定的，這種由要求隨機(jī)性服務(wù)的顧客和服務(wù)機(jī)構(gòu)兩方面構(gòu)成的系統(tǒng)稱為隨機(jī)服務(wù)系統(tǒng)或排隊系統(tǒng)。1 1排隊系統(tǒng)的概念排隊系統(tǒng)的概念（2）排隊系統(tǒng)的一般表示排 隊服務(wù)機(jī)構(gòu)顧客到達(dá)輸入排隊規(guī)則服務(wù)規(guī)則顧客離去輸出T1排隊論基本概念排隊論基本概念.1（1）顧客到達(dá)率顧客到達(dá)率 顧客到達(dá)率是單位時間內(nèi)平均到達(dá)排隊系統(tǒng)的顧客數(shù)量。 2.排隊系統(tǒng)的基本

18、參數(shù)排隊系統(tǒng)的基本參數(shù)（2）服務(wù)員數(shù)目m 服務(wù)的設(shè)備或窗口數(shù)（3）服務(wù)員服務(wù)速率 服務(wù)員服務(wù)速率指的是單位時間內(nèi)由一個服務(wù)員進(jìn)行服務(wù)所離開排隊系統(tǒng)的平均顧客數(shù)。1排隊論基本概念排隊論基本概念.13.排隊系統(tǒng)的排隊系統(tǒng)的3個特征個特征 顧客輸入過程 排隊過程 顧客接受服務(wù)(然后離去)的過程(1)(1)顧客到達(dá)間隔時間的分布函數(shù)顧客到達(dá)間隔時間的分布函數(shù) 如果顧客的輸入過程滿足平穩(wěn)性、稀疏性和無后效性，稱該輸入為最簡單流。 當(dāng)輸入過程為最簡單流時，在給定時間間隔內(nèi)t系統(tǒng)有k個顧客到達(dá)的概率為 上式稱為泊松分布tkkekttP!)()(排隊論基本概念排隊論基本概念.1

19、當(dāng)輸入過程為最簡單流時，T的概率分布函數(shù) 顧客到達(dá)間隔時間的概率密度函數(shù)為 tTetPtTPtTPtF1)(1)(1)()(0tTTedttdFtf)()(顧客到達(dá)時間間隔T服從負(fù)指數(shù)分布排隊論基本概念排隊論基本概念.1(2)(2)服務(wù)時間的分布函數(shù)服務(wù)時間的分布函數(shù) 假設(shè)顧客接受服務(wù)的過程也滿足最簡單流的平穩(wěn)性、稀疏性和獨(dú)立性。服務(wù)時間的概率分布函數(shù)為 其概率密度函數(shù)為 tetF 1)(tetf)(服務(wù)時間也是負(fù)指數(shù)分布 負(fù)指數(shù)分布又稱為M分布，稱為M分布的原因是這種分布使排隊過程具有馬爾科夫性（無記憶性）排隊論基本概念排隊論基本概念.1（3 3）排隊規(guī)則）排

20、隊規(guī)則 損失制系統(tǒng)(即時拒絕方式) 顧客到達(dá)時，如果所有服務(wù)窗口均被占滿，則立即遭到拒絕，即服務(wù)機(jī)構(gòu)不允許顧客排隊等待，這種稱為損失制系統(tǒng)。 等待制系統(tǒng)(不拒絕方式) 當(dāng)顧客到達(dá)系統(tǒng)時，如果所有的服務(wù)窗口已占滿，允許顧客排隊等待，且對排隊隊長沒有限制，這種稱為等待制系統(tǒng)。 混合制系統(tǒng)(延時拒絕方式) 當(dāng)顧客到達(dá)系統(tǒng)時，如果所有的窗口已占滿，允許顧客排隊等待，但對排隊隊長有所限制，這種系統(tǒng)稱為混合制系統(tǒng)。排隊論基本概念排隊論基本概念.1 具有等待性質(zhì)的排隊系統(tǒng)(包括等待制系統(tǒng)和混合制系統(tǒng))相應(yīng)的服務(wù)規(guī)則主要有下列幾種： 先到先服務(wù) 后到先服務(wù) 隨機(jī)服務(wù) 優(yōu)先制服務(wù)4 4排隊系統(tǒng)的

21、幾個主要指標(biāo)及李特爾排隊系統(tǒng)的幾個主要指標(biāo)及李特爾(Little)(Little)定律定律(1)(1)排隊系統(tǒng)的幾個主要指標(biāo)排隊系統(tǒng)的幾個主要指標(biāo)排隊長度k(簡稱隊長)等待時間w服務(wù)時間系統(tǒng)時間smm/排隊論基本概念排隊論基本概念.1 系統(tǒng)效率 穩(wěn)定性：也叫排隊強(qiáng)度，用表示，一般令(2)(2)李特爾李特爾(Little)(Little)定律定律 對于一個平均到達(dá)率為的排隊系統(tǒng)，在平均的意義上有skN排隊論基本概念排隊論基本概念.15 5排隊系統(tǒng)的分類排隊系統(tǒng)的分類 排隊系統(tǒng)通常使用符號表示。其中X是顧客到達(dá)間隔時間的分布，Y是服務(wù)時間的分布， m是服務(wù)員個數(shù)，

22、n為排隊系統(tǒng)中允許的顧客數(shù), 也稱為截止隊長。當(dāng)n為時(即為不拒絕方式)，則可省略。 常用的分布符號有： M 負(fù)指數(shù)時間分布；D定長時間分布； k階愛爾蘭時間分布； k階超指數(shù)時間分布。nmYX/kEkH排隊論基本概念排隊論基本概念.1常見的排隊系統(tǒng)：常見的排隊系統(tǒng)：（1）M/M/m/n排隊系統(tǒng)l當(dāng)n=時，表示為M/M/m，等待制排隊系統(tǒng)（不拒絕方式）；l當(dāng)n時，為混合制排隊系統(tǒng)（時延拒絕方式）；l當(dāng)n=m時，為損失制系統(tǒng)（即時拒絕方式）；l當(dāng)m=1且n=，為M/M/1系統(tǒng)，最簡單的排隊系統(tǒng)。（2）M/D/1系統(tǒng)（3）M/ /1系統(tǒng)（4）M/ /1系統(tǒng) kEkHM/M/1M/M/1排隊系統(tǒng)排隊系統(tǒng).21 1M/M/1M/M/1排隊系統(tǒng)模型排隊系統(tǒng)模型 服務(wù)機(jī)構(gòu)n泊松輸入過程指數(shù)服務(wù)時間分布一個服務(wù)員M/M/1M/M/1排隊系統(tǒng)有以下幾個特點(diǎn)