現(xiàn)代通信網(wǎng)課件通信網(wǎng)絡(luò)設(shè)計(jì)基礎(chǔ)

第3章通信網(wǎng)絡(luò)設(shè)計(jì)基礎(chǔ)第二講本講主要內(nèi)容最短路徑站址選擇排隊(duì)論基本概念1.最短路徑——背景建立多個(gè)城市之間的有線通信網(wǎng)絡(luò)，如何確定能夠連接所有城市并使得線路費(fèi)用最小的網(wǎng)絡(luò)結(jié)構(gòu)？在一定網(wǎng)絡(luò)結(jié)構(gòu)上，如何選擇通信路由，怎樣確定首選路由和迂回路由？這些問(wèn)題都?xì)w結(jié)到路徑選擇或者路徑優(yōu)化問(wèn)題上來(lái)。1.1最小支撐樹尋找最小支撐樹是一個(gè)優(yōu)化問(wèn)題，可以分為兩種情況：無(wú)限制條件（無(wú)約束條件）和有限制條件（有約束條件）。這里重點(diǎn)介紹無(wú)限制條件的最小支撐樹搜索方法。求無(wú)限制條件的最小支撐樹的方法：K方法和P方法求解最小支撐樹的Kruskal

方法（K方法）例3-3求解最小支撐樹的Prim方法（P方法）求有限制條件的最小支撐樹的方法在設(shè)計(jì)通信網(wǎng)的網(wǎng)絡(luò)結(jié)構(gòu)時(shí)，經(jīng)常會(huì)提出一些特殊要求，如：兩個(gè)交換中心通信時(shí)，轉(zhuǎn)接的次數(shù)不能太多；某條線路上的話務(wù)量不能太大等等。這類問(wèn)題可以歸結(jié)為在限制條件下求最小支撐樹。求有約束條件的最小支撐樹的方法簡(jiǎn)單來(lái)說(shuō)是這樣的：先按照上述K方法或者P方法求出無(wú)約束條件的最小支撐樹，然后根據(jù)所給的約束條件對(duì)網(wǎng)絡(luò)結(jié)構(gòu)進(jìn)行調(diào)整，使之既滿足約束條件，又盡量接近最小支撐樹。1.2點(diǎn)間最短路徑在通信網(wǎng)的網(wǎng)絡(luò)結(jié)構(gòu)確定以后，任意兩點(diǎn)之間的通信，首選路由是它們之間的最短路由，這是求兩點(diǎn)間最短路徑的問(wèn)題。兩點(diǎn)間的最短路徑問(wèn)題有兩種情況：（1）指定點(diǎn)到其他點(diǎn)的最短路徑和（2）任意兩點(diǎn)間的最短路徑。指定點(diǎn)到其他點(diǎn)的最短路徑求指定點(diǎn)到其他各點(diǎn)的最短路徑，Dijkstra算法（簡(jiǎn)稱D算法）是最有效的算法之一。D算法的具體步驟例3-5任意兩點(diǎn)之間的最短路徑算法求任意兩點(diǎn)之間的最短路徑，可以依次選擇每個(gè)點(diǎn)為指定點(diǎn)，用D算法做n次運(yùn)算，但這樣做比較繁瑣。下面介紹一種更為有效的算法——Floyd算法，簡(jiǎn)稱F算法。F算法的原理與D算法相同，只是使用矩陣形式進(jìn)行運(yùn)算，有利于在計(jì)算機(jī)中進(jìn)行處理。例3-63.站址選擇實(shí)際通信網(wǎng)中，可以設(shè)立新的交換局，或者在某些交換局之間設(shè)立匯接局或高等級(jí)的交換局，它的位置選擇應(yīng)能使得路徑最短或者網(wǎng)的總費(fèi)用最小。新交換局可以設(shè)立一個(gè)或者多個(gè)，在數(shù)學(xué)上是求單中位點(diǎn)或者多中位點(diǎn)的問(wèn)題。3.1單中位點(diǎn)距離測(cè)度單中位點(diǎn)位置的確定（矩形線測(cè)度）3.排隊(duì)論基本概念1.排隊(duì)系統(tǒng)的概念（1）排隊(duì)論與排隊(duì)系統(tǒng)的概念顧客——要求服務(wù)的一方；服務(wù)機(jī)構(gòu)——提供服務(wù)的一方服務(wù)員——服務(wù)機(jī)構(gòu)內(nèi)的具體設(shè)施排隊(duì)現(xiàn)象產(chǎn)生的原因和排隊(duì)論需要解決的問(wèn)題顧客需求的隨機(jī)性和服務(wù)設(shè)施的有限性是產(chǎn)生排隊(duì)現(xiàn)象的根本原因。排隊(duì)論就是利用概率論和隨機(jī)過(guò)程的理論，研究隨機(jī)服務(wù)系統(tǒng)內(nèi)服務(wù)機(jī)構(gòu)與顧客需求之間的關(guān)系，以便合理地設(shè)計(jì)和控制排隊(duì)系統(tǒng)。由于顧客到達(dá)的數(shù)目和要求提供服務(wù)的時(shí)間長(zhǎng)短都是不確定的，這種要求隨機(jī)服務(wù)的顧客和服務(wù)機(jī)構(gòu)兩個(gè)方面構(gòu)成的系統(tǒng)稱為隨機(jī)服務(wù)系統(tǒng)或者排隊(duì)系統(tǒng)。3.排隊(duì)論基本概念（2）排隊(duì)系統(tǒng)的一般表示任何一個(gè)排隊(duì)系統(tǒng)都有以下過(guò)程：顧客到達(dá)服務(wù)機(jī)構(gòu)，若服務(wù)員有空閑便立刻得到服務(wù)，若服務(wù)員不空閑，則需要排隊(duì)等待服務(wù)員有空閑時(shí)再接受服務(wù)，服務(wù)完后離開服務(wù)機(jī)構(gòu)。圖3-213.2排隊(duì)系統(tǒng)的基本參數(shù)3.2排隊(duì)系統(tǒng)的基本參數(shù)3.3排隊(duì)系統(tǒng)的三個(gè)特征3.3排隊(duì)系統(tǒng)的三個(gè)特征3.3排隊(duì)系統(tǒng)的三個(gè)特征3.3排隊(duì)系統(tǒng)的三個(gè)特征3.3排隊(duì)系統(tǒng)的三個(gè)特征綜上所述，無(wú)論是顧客輸入過(guò)程，還是服務(wù)過(guò)程，只要是最簡(jiǎn)單流，則所對(duì)應(yīng)的概率分布函數(shù)都為負(fù)指數(shù)分布，又稱M分布。3.3排隊(duì)系統(tǒng)的三個(gè)特征3.4排隊(duì)系統(tǒng)的幾個(gè)主要指標(biāo)及李特爾（Little）定律3.4排隊(duì)系統(tǒng)的幾個(gè)主要指標(biāo)及李特爾（Little）定律3.4排隊(duì)系統(tǒng)的幾個(gè)主要指標(biāo)及李特爾（Little）定律3.4排隊(duì)系統(tǒng)的幾個(gè)主要指標(biāo)及李特爾（Little）定律3.5排隊(duì)系統(tǒng)的分類3.5排隊(duì)系統(tǒng)的分類3.6M/M/1排隊(duì)系統(tǒng)3.6M/M/1排隊(duì)系統(tǒng)3.6M/M/1排隊(duì)系統(tǒng)3.6M/M/1排隊(duì)系統(tǒng)3.7M/M/m/n排隊(duì)系統(tǒng)3.7M/M/m/n排隊(duì)系統(tǒng)3.8排隊(duì)論在通信網(wǎng)中的應(yīng)用3.8排隊(duì)論在通信網(wǎng)中的應(yīng)用本次課內(nèi)容回顧最小支撐樹求解的目的最小支撐樹及其求解方法K方法和P方法最短路徑求解的目的點(diǎn)間最短路徑求解方法：指定點(diǎn)到其他點(diǎn)的