通信網(wǎng)絡基礎(chǔ)11

第1章 通信網(wǎng)絡概論

及數(shù)學基礎(chǔ)通信與信息工程學院2023/10/11西安郵電學院通信工程系郭娟內(nèi)容

1.1通信網(wǎng)絡的基本構(gòu)成

1.2協(xié)議體系及分層的概念

1.3通信網(wǎng)絡中的數(shù)學基礎(chǔ)

1.4通信網(wǎng)絡的基本理論問題2023/10/11西安郵電學院通信工程系郭娟1.1通信網(wǎng)絡的基本構(gòu)成1.1.1數(shù)據(jù)傳輸鏈路1.1.2數(shù)據(jù)傳輸網(wǎng)絡1.1.3網(wǎng)絡的互連2023/10/11西安郵電學院通信工程系郭娟1.1通信網(wǎng)絡的基本構(gòu)成2023/10/11西安郵電學院通信工程系郭娟通信網(wǎng)絡的分類用戶活動的類型：移動、固定業(yè)務的種類：電話、計算機數(shù)據(jù)、多媒體傳輸媒介：有線、無線技術(shù)體制：ATM交換體制、電路交換體制、分組交換體制應用領(lǐng)域：軍用、民用/公用、專用通信網(wǎng)絡舉例：固定電話網(wǎng)、移動通信網(wǎng)、ATM網(wǎng)絡、局域網(wǎng)、IP網(wǎng)絡等。2023/10/11西安郵電學院通信工程系郭娟通信網(wǎng)絡舉例（1）2023/10/11西安郵電學院通信工程系郭娟通信網(wǎng)絡舉例（2）它包括的網(wǎng)絡（通常稱為子網(wǎng)）有：ATM網(wǎng)絡（AsynchronousTransferMode，異步轉(zhuǎn)移模式）

、X.25分組數(shù)據(jù)網(wǎng)、PSTN/ISDN（PublicSwitchedTelephoneNetwork/IntegratedServiceDigitalNetwork）、移動通信網(wǎng)/衛(wèi)星通信網(wǎng)、FDDI環(huán)網(wǎng)（FiberDistributedDataInterface，光纖分布式數(shù)據(jù)接口）、局域網(wǎng)及高速骨干核心網(wǎng)等。整個網(wǎng)絡通過以WDM鏈路（WavelengthDivisionMultiplexing）作為核心路由器的高速通道，形成高速信息傳輸平臺，將上述各子網(wǎng)互連互通，可形成一個無縫覆蓋的網(wǎng)絡。2023/10/11西安郵電學院通信工程系郭娟通信網(wǎng)絡舉例（3）路由器是網(wǎng)絡互連的核心設(shè)備，它負責分組（分組是由若干數(shù)據(jù)比特組成的可進行獨立傳輸?shù)臄?shù)據(jù)塊，其長度為幾十個字節(jié)到幾千個字節(jié)）的轉(zhuǎn)發(fā)和為各個分組選擇適當?shù)膫鬏斅窂?。（鐵路運輸?shù)呢涍\站、集裝箱碼頭）2023/10/11西安郵電學院通信工程系郭娟通信網(wǎng)絡舉例（4）正是由于路由器的存在，我們可以將任一用戶（用戶A）的分組，通過一個最優(yōu)的路由（用戶A→路由器R13→路由器R1→路由器R3→ATM網(wǎng)絡→路由器R14→用戶G）轉(zhuǎn)發(fā)給任一目的用戶（用戶G）。（圖1.2）2023/10/11西安郵電學院通信工程系郭娟通信網(wǎng)絡舉例（5）在該網(wǎng)絡中，以分組作為載體來運載不同類型的業(yè)務。這些業(yè)務可以是話音、圖像、視頻，也可以是電子郵件、Web業(yè)務等等。為了向用戶提供不同的服務，除通信網(wǎng)絡本身以外，網(wǎng)絡中還掛有不同類型的服務器，如S1、S2、S3等。因此在通信網(wǎng)中，通信的雙方可以是人與人、機器與機器、人與機器等，通信的形式既可以是一個用戶對一個用戶，也可以是一個用戶對多個用戶或多個用戶對多個用戶。2023/10/11西安郵電學院通信工程系郭娟1.1.1數(shù)據(jù)傳輸鏈路（1）所謂數(shù)據(jù)傳輸鏈路是指在物理傳輸媒介（如雙絞線、同軸電纜、光纖、微波傳輸系統(tǒng)、衛(wèi)星傳輸電路等）上利用一定的傳輸標準（它通常規(guī)定了電氣接口、調(diào)制解調(diào)的方式、數(shù)據(jù)編碼的方式、比特同步、幀格式和復分接的方式等）形成的傳輸規(guī)定速率（和格式）的數(shù)據(jù)比特通道。2023/10/11西安郵電學院通信工程系郭娟1.1.1數(shù)據(jù)傳輸鏈路（2）數(shù)據(jù)傳輸鏈路分為兩大類：一類是用戶到網(wǎng)絡節(jié)點（路由器或交換機）之間的鏈路（簡稱為接入鏈路）；另一類是網(wǎng)絡節(jié)點（路由器或交換機）到網(wǎng)絡節(jié)點（路由器或交換機）之間的鏈路（簡稱為網(wǎng)絡鏈路）。2023/10/11西安郵電學院通信工程系郭娟1.1.1數(shù)據(jù)傳輸鏈路（3）接入鏈路有多種形式，如Modem（調(diào)制解調(diào)器）鏈路、xDSL鏈路、ISDN鏈路、無線鏈路（移動通信和衛(wèi)星通信鏈路）、局域網(wǎng)鏈路等。例如：xDSL鏈路是通過數(shù)字技術(shù)，對PSTN端局（本地電話交換機）到用戶終端之間的線路進行改造而成的數(shù)字用戶線DSL（DigitalSubscriberLine）。DSL的前綴x表示不同的傳輸方案。例如：ADSL（AsymmetricDSL,非對稱數(shù)字用戶線）的上行速率為640kb/s～1Mb/s，下行速率為6～8Mb/s;HDSL(HighSpeedDSL)上下行速率相同，均為768kb/s或1.5Mb/s；VDSL（VeryHighSpeedDSL）下行速率12.96Mb/s、25Mb/s、52Mb/s，上行速率為1.6～2.3Mb/s。2023/10/11西安郵電學院通信工程系郭娟ADSL例如：DMTfullratedownstream(upto8Mbps)DMTfullrateupstream(upto640Kbps)G.liteADSLdownstream(upto1.5Mbps)G.liteADSLupstream(upto512Kbps)2023/10/11西安郵電學院通信工程系郭娟Cable Modem例如：TheDCM-201hasamaximumdownloadingspeedat38Mbps(256QAM)andamaximumuploadingspeedat10Mbps(16QAM).TheDCM-201usestheReed-Solomonerrorcorrectionmethodfordatapacketintegrity.?DownstreamModulation:64QAM,256QAM?FrequencyRange:91-857MHz?UpstreamModulation:QPSK,16QAM?FrequencyRange:5-42MHz2023/10/11西安郵電學院通信工程系郭娟局域網(wǎng)鏈路局域網(wǎng)鏈路中最典型的是以太網(wǎng)（Ethernet）鏈路，在雙絞線上可傳輸?shù)姆逯禂?shù)據(jù)速率為10Mb/s、100Mb/s、1000Mb/s。這是在辦公室環(huán)境下，最常用的接入方式。2023/10/11西安郵電學院通信工程系郭娟GPRS/CDMA鏈路高速上網(wǎng)：支持GPRSclass8;支持最高53.6Kbps的下載速度。雙頻支持：GSM雙頻（900MHz/1.8GHz）CDMA上網(wǎng)卡：數(shù)據(jù)傳輸速率最高達256Kbps，實際接入速度平均可達每秒233Kbps，網(wǎng)速是GPRS的3-4倍，CDMA網(wǎng)絡升級到3G,無需更換設(shè)備速度更可高達1.9MBps2023/10/11西安郵電學院通信工程系郭娟1.1.1數(shù)據(jù)傳輸鏈路（4）網(wǎng)絡鏈路也有多種形式，如：幀中繼、SDH、WDM等。例如：SDH（Synchronous DigitalHierachy，同步數(shù)字系列）是在美國貝爾實驗室提出的SONET（SynchronousOpticalNetwork，光同步數(shù)字網(wǎng)）的基礎(chǔ)上制定的技術(shù)標準，它具有一套標準化的結(jié)構(gòu)等級STM-N（N=1，4，16，64），它們的傳輸速率分別為STM-1（155.520Mb/s），STM-4（622.080Mb/s），STM-16（2488.320Mb/s），STM-64（9953.280Mb/s）。2023/10/11西安郵電學院通信工程系郭娟1.1.1數(shù)據(jù)傳輸鏈路（5）光波分復用（WDM，WaveLengthDivisionMultiplexing）技術(shù)是在一根光纖中能同時傳輸多個波長光信號的一種技術(shù)。在發(fā)端將不同波長的光信號組合（復用）起來。在接收端又將組合的光信號分開（解復用）并送到不同的終端。目前在一根光纖上可提供的數(shù)據(jù)速率為4*2.5Gb/s（第一個數(shù)字4為波長數(shù)，第二個數(shù)字2.5為每一波長上的速率）、16*10Gb/s，160*2.5Gb/s、128*10Gb/s等，理論上可達5Tb/s的傳輸速率。1550nm窗口的DWDM光纜系統(tǒng)2023/10/11西安郵電學院通信工程系郭娟1.1.2數(shù)據(jù)傳輸網(wǎng)絡（1）數(shù)據(jù)傳輸網(wǎng)絡的基本功能是通過網(wǎng)絡中的交換機（或路由設(shè)備）為運載用戶業(yè)務的分組，選擇合適的傳輸鏈路，從而使這些分組迅速可靠地傳送到目的用戶。（一個分組經(jīng)過的所有傳輸鏈路的集合稱為一條路徑(或路由)）。在數(shù)據(jù)傳輸網(wǎng)絡中，要傳送的基本內(nèi)容稱為消息（Message）。根據(jù)不同的應用場合，消息可有不同的含義。比如，消息可以是一份電子郵件（E-mail），一份文件，一幅圖像，……。

2023/10/11西安郵電學院通信工程系郭娟1.1.2數(shù)據(jù)傳輸網(wǎng)絡（2）在要進行交互操作的場合，如：A可以發(fā)一個消息給B，B可以發(fā)一個應答給A，雙方需要交互多次才可完成信息交換的過程，或者說，雙方需要按一定的順序交換大量的消息。我們稱這樣一個消息的序列為一個會話過程（Session）。2023/10/11西安郵電學院通信工程系郭娟1.1.2數(shù)據(jù)傳輸網(wǎng)絡（2）數(shù)據(jù)傳輸網(wǎng)絡必須保證每一個會話過程可靠、及時、高效地完成。典型的數(shù)據(jù)傳輸網(wǎng)絡：分組交換網(wǎng)和ATM網(wǎng)等。2023/10/11西安郵電學院通信工程系郭娟1．分組交換網(wǎng)（1）在分組交換網(wǎng)中，將消息分成許多比較短的、格式化的數(shù)據(jù)塊稱為分組（Packet）進行傳輸和交換。每一個分組由若干比特的數(shù)據(jù)組成。每一個分組通常包括一個附加的分組頭。分組頭指明該分組的目的節(jié)點及其他網(wǎng)絡控制信息。在每一個網(wǎng)絡節(jié)點中采用存儲轉(zhuǎn)發(fā)的工作方式來將輸入的分組送到選定的輸出鏈路上。（這種按照一定的規(guī)則（路由算法）將輸入分組送到選定的輸出鏈路上的過程稱為交換。）2023/10/11西安郵電學院通信工程系郭娟1．分組交換網(wǎng)（2）重裝2023/10/11西安郵電學院通信工程系郭娟1．分組交換網(wǎng)（2）如何選擇一條合適的傳輸路徑？基本方式：虛電路方式數(shù)據(jù)報方式2023/10/11西安郵電學院通信工程系郭娟1．分組交換網(wǎng)（3）在虛電路方式中，在一個會話過程開始時，確定S→D的一條邏輯通路（即實際分組傳輸時才占用物理鏈路，無分組傳輸時不占用物理鏈路。此時物理鏈路可用于其他用戶分組的傳輸）。會話過程中所有的分組都沿此邏輯通道進行。例如圖1-3（a）的S→D之間為消息A建立了一條邏輯通路。每一條邏輯通路中的邏輯鏈路可用一個虛電路號（VCn）來表示。2023/10/11西安郵電學院通信工程系郭娟1．分組交換網(wǎng)（4）在數(shù)據(jù)報方式中，為會話過程中的每一個分組獨立地選擇路由，也就是S→D之間一次會話過程中的分組可以獨立地選擇路徑A，路徑B或路徑C或其他路徑。因而，到達目的節(jié)點D的分組所經(jīng)過的鏈路可能各不相同。2023/10/11西安郵電學院通信工程系郭娟電路交換電路交換是指根據(jù)用戶的呼叫請求，將輸入物理電路直接與輸出物理電路相連接的一種交換技術(shù)。電路交換機在功能上等效為一個開關(guān)矩陣，當某一輸入電路要與某一輸出電路相連時，則將對應的開關(guān)閉合，形成直接的通路。在電路交換網(wǎng)中，在雙方通信之前，需要在雙方建立一條直接的物理通路，在通信結(jié)束后，要拆除該物理通路。在通信過程中，收發(fā)雙方獨占該道物理通路。在電路交換方式中，信息的傳輸具有很短的時延，且可以保持收發(fā)雙方嚴格的同步關(guān)系。但與分組交換相比，鏈路使用效率相對較低。2023/10/11西安郵電學院通信工程系郭娟2．ATM網(wǎng)絡（1）ATM（AsynchronousTransferMode）是在傳統(tǒng)電話網(wǎng)使用的電路交換以及分組交換網(wǎng)基礎(chǔ)上發(fā)展起來的一種交換技術(shù)，可以較好地支持不同速率、不同種類的寬帶信息交換。2023/10/11西安郵電學院通信工程系郭娟2．ATM網(wǎng)絡（2）它與分組交換的差別是采用一個全網(wǎng)統(tǒng)一的固定長度的分組（稱之為信元）進行傳輸和交換。ATM網(wǎng)絡中，信元的長度為53個字節(jié)，其中5個字節(jié)為信元頭，48個字節(jié)用來運載信息。好處：由于信元長度和格式固定，可用硬件電路對信元進行處理，因而縮短了每一個信元的處理時間。它采用面向連接（即虛電路）方式，以提高信息傳送的實時性。ATM設(shè)計是以光纖傳輸為基礎(chǔ)，因此在傳輸鏈路上采用了非常簡單的差錯控制和流量控制等措施，提高了信元在網(wǎng)絡中的傳輸速率。2023/10/11西安郵電學院通信工程系郭娟2．ATM網(wǎng)絡（3）ATM用戶（終端）到ATM交換機（網(wǎng)絡）之間的接口稱為UNI（User-NetworkInterface，用戶網(wǎng)絡接口）。交換機（網(wǎng)絡節(jié)點）之間的接口稱為NNI（Network-NodeInterface，網(wǎng)絡節(jié)點接口）。2023/10/11西安郵電學院通信工程系郭娟2．ATM網(wǎng)絡（4）ATM的信元格式：UNI接口和NNI接口的信元格式除前12個比特格式不同外，其余格式完全相同。GFC（GenericFlowControl）是流量控制比特。VPI/VCI用來表示信元傳遞的路徑。其中，VPI（VirtualPathIdentifier）是虛通道標識；VCI（VirtualChannelIdentifier）是虛信道標識。PT（PayloadType,負荷類型）用來區(qū)分該信元是用戶信息還是控制信息。CLP（CellLossPriority，信元丟失優(yōu)先級）指示信元的丟失優(yōu)先級。HEC（HeaderErrorControl，信元頭差錯控制）提供信元頭四個字節(jié)的差錯控制，可進行多個比特的檢錯和單個比特的糾錯。2023/10/11西安郵電學院通信工程系郭娟2．ATM網(wǎng)絡（5）2023/10/11西安郵電學院通信工程系郭娟2．ATM網(wǎng)絡（6）ATM信元通常是在SDH鏈路上進行傳輸?shù)摹榱酥С植煌愋偷臉I(yè)務，ATM網(wǎng)絡向用戶提供四種類別的服務，即A類、B類、C類和D類。服務類別是根據(jù)業(yè)務的比特率是固定的還是可變的、源節(jié)點到目的節(jié)點是否需要同步、以及是面向連接還是無連接來劃分的。對于不同類別的業(yè)務，ATM網(wǎng)絡采用不同的適配方法（即如何將業(yè)務比特流分段，形成數(shù)據(jù)協(xié)議單元（CS-PDU），再如何將CS-PDU分成信元，最后如何有效地傳輸這些信元）。這些適配的方法稱為AAL1～AAL5。2023/10/11西安郵電學院通信工程系郭娟2．ATM網(wǎng)絡（7）AAL1支持A類：恒定比特流、收發(fā)需要定時關(guān)系、面向連接的業(yè)務。AAL2支持B類：可變比特流、收發(fā)需要定時關(guān)系且面向連接的業(yè)務（如話音和圖像等業(yè)務）。AAL3/4支持C類/D類業(yè)務，服務既可以是面向連接的也可以是無連接的，支持的業(yè)務可以是報文模式也可以是流模式。AAL5為面向連接的應用提供更為有效的運載措施。2023/10/11西安郵電學院通信工程系郭娟1.1.3網(wǎng)絡的互連（1）前面兩個小節(jié)，我們主要討論的是一個子網(wǎng)內(nèi)的問題，這時所有的鏈路具有相同特性，采用某種數(shù)據(jù)傳輸鏈路協(xié)議和尋址方式，通過交換設(shè)備來實現(xiàn)子網(wǎng)內(nèi)的路由選擇和信息交換。當多個（不同傳輸和交換方式的）子網(wǎng)要互聯(lián)互通構(gòu)成一個大的網(wǎng)絡時，需要采用路由器（設(shè)備）。如圖1-5所示。2023/10/11西安郵電學院通信工程系郭娟1.1.3網(wǎng)絡的互連（2）2023/10/11西安郵電學院通信工程系郭娟1.1.3網(wǎng)絡的互連（3）路由器的基本功能有兩個：一是根據(jù)路由表，將報文（datagram）發(fā)送到正確的目的地；二是維持和更新決定報文傳輸路徑的路由表。路由表中指明到達目的地應將報文送入與路由器相連的哪一個子網(wǎng)。輸入端口輸入子網(wǎng)輸出子網(wǎng)輸出端口

1子網(wǎng)C子網(wǎng)A22子網(wǎng)A子網(wǎng)B33子網(wǎng)B子網(wǎng)C12023/10/11西安郵電學院通信工程系郭娟1.1.3網(wǎng)絡的互連（4）路由器工作方式是：從接收報文中提取目的地址，并確定該地址中的網(wǎng)絡號，查找路由表以獲得與該目標網(wǎng)絡相匹配的表項。該表項包括報文應到達的下一網(wǎng)絡及到達下一網(wǎng)絡的必要信息（如對應的路由器輸出端口）。報文被封裝在選定的輸出端口的數(shù)據(jù)幀中(采用輸出子網(wǎng)的數(shù)據(jù)格式)，并由輸出端口輸出。2023/10/11西安郵電學院通信工程系郭娟1.1.3網(wǎng)絡的互連（5）為了實現(xiàn)全網(wǎng)互連需要兩個基本條件：一是全網(wǎng)統(tǒng)一編址，二是路由算法。編址解決如何區(qū)分網(wǎng)絡中的節(jié)點、用戶終端等，例如，在Internet中是采用IP地址來區(qū)分路由器、服務器、用戶計算機等。路由算法解決從源到目的地之間應經(jīng)過的子網(wǎng)、路由器、網(wǎng)絡節(jié)點等。例如，可以采用從源到目的地經(jīng)過的路由器最少的原則來選擇一條路由。2023/10/11西安郵電學院通信工程系郭娟1.1.3網(wǎng)絡的互連（6）路由器區(qū)別于交換機的關(guān)鍵特征是它可連接使用不同物理傳輸媒介、具有不同傳輸協(xié)議的數(shù)據(jù)鏈路。在一個典型的網(wǎng)絡中，通常會有一種以上的局域網(wǎng)（LAN）和廣域網(wǎng)（WAN）技術(shù)，而每個子網(wǎng)都有獨立的數(shù)據(jù)鏈路傳輸協(xié)議和尋址方式。2023/10/11西安郵電學院通信工程系郭娟內(nèi)容

1.1通信網(wǎng)絡的基本構(gòu)成

1.2協(xié)議體系及分層的概念

1.3通信網(wǎng)絡中的數(shù)學基礎(chǔ)

1.4通信網(wǎng)絡的基本理論問題2023/10/11西安郵電學院通信工程系郭娟1.2協(xié)議體系及分層的概念

1.2.0通信協(xié)議的重要性

1.2.1分層的概念

1.2.2OSI協(xié)議的體系結(jié)構(gòu)

1.2.3TCP/IP協(xié)議的體系結(jié)構(gòu)

1.2.4混合的分層協(xié)議體系2023/10/11西安郵電學院通信工程系郭娟通信協(xié)議（1）2023/10/11西安郵電學院通信工程系郭娟通信協(xié)議（2）通信協(xié)議的重要性：占據(jù)兩個山頂?shù)乃{軍與駐扎在山谷的白軍作戰(zhàn)。力量對比是：一個山頂上的藍軍打不過白軍，但兩個山頂?shù)乃{軍協(xié)同作戰(zhàn)就可戰(zhàn)勝白軍。一個山頂上的藍軍擬于次日正午向白軍發(fā)起攻擊。于是發(fā)送電文給另一山頂上的友軍。但通信線路很不好，電文出錯的可能性很大。因此要求收到電文的友軍必須發(fā)送確認電文。但確認電文也可能出錯。試問能否設(shè)計出一種協(xié)議，使得藍軍能實現(xiàn)協(xié)同作戰(zhàn)因而一定(即100%)取得勝利？2023/10/11西安郵電學院通信工程系郭娟明日正午進攻，如何？同意收到“同意”收到：收到“同意”………………這樣的協(xié)議無法實現(xiàn)！通信協(xié)議（3）2023/10/11西安郵電學院通信工程系郭娟通信協(xié)議（4）不難看出，如此往復下去將引起無窮多次信息的交換，也不可能使雙方同時進入進攻的狀態(tài)。這個問題出現(xiàn)的關(guān)鍵是：每一方很難相信自己是正確的，它要求雙方的信息都必須嚴格正確。如果我們把前面嚴格確認的條件放松，即要求同時進攻的概率很高，這樣上面的問題就可以解決。解決的方法是：如果紅軍一方要在某個時間發(fā)起進攻，它就同時派出多個信使，并確信對方會以很大的概率獲得該信息，而對方確信請求進攻方會發(fā)起進攻。這樣雙方取勝的可能性很大。2023/10/11西安郵電學院通信工程系郭娟通信協(xié)議（5）上述例子說明了通信協(xié)議（規(guī)則）的重要性，完善的通信協(xié)議應當保證通信的終端能高效地向用戶提供所需的服務。不同的通信功能需要不同的通信協(xié)議，如IEEE802.3，IP，TCP，HTTP,…。一個完整的通信(信息)系統(tǒng)需要一組通信協(xié)議。通信協(xié)議通?？赏ㄟ^完善的協(xié)議體系來描述。為了描述協(xié)議體系，這里首先給出分層的概念。2023/10/11西安郵電學院通信工程系郭娟1.2.1分層的概念（1）通信網(wǎng)絡的協(xié)議可按照分層的概念來設(shè)計。分層概念的基礎(chǔ)是“模塊”的概念。例如：在計算機系統(tǒng)中，一個模塊就是一個過程或一臺設(shè)備，它完成一個給定的功能；若干個模塊組成一個完整的系統(tǒng)功能。模塊提供的功能通常稱之為“服務”。2023/10/11西安郵電學院通信工程系郭娟1.2.1分層的概念（2）采用模塊概念的好處是：設(shè)計簡單、可懂性好、標準化、互換性好，有大量現(xiàn)存的模塊可以利用。對于模塊設(shè)計人員，要關(guān)心該模塊內(nèi)部的細節(jié)和模塊的操作。而對于模塊使用人員，把模塊當作一個黑盒子，只關(guān)心該模塊的輸入、輸出以及輸入輸出的功能關(guān)系，而不關(guān)心模塊內(nèi)部的工作細節(jié)。模塊可以嵌套組成更大的模塊。2023/10/11西安郵電學院通信工程系郭娟1.2.1分層的概念（3）例如：一個高層的模塊由低層模塊加上一些簡單模塊組成。2023/10/11西安郵電學院通信工程系郭娟1.2.1分層的概念（4）通信網(wǎng)絡的分層可以看成由一套模塊組成的體系結(jié)構(gòu)，除了最低層由物理通信鏈路組成以外，每一個高層模塊是由低層黑盒子通信系統(tǒng)加一組簡單的模塊組成。2023/10/11西安郵電學院通信工程系郭娟1.2.1分層的概念（5）對等模塊：由于信息的交換必須在雙方進行，通信的雙方必須有相同（或相應）的功能塊，才能完成給定的功能，因此在每一層雙方兩個功能相對應的模塊就稱為對等（peer）模塊或?qū)Φ冗^程。如圖1-8中的模塊H和H′，模塊L和L′都是對等模塊。在該圖中，低層模塊（通信系統(tǒng)黑盒子）本身由更低層的對等模塊和更低層的通信系統(tǒng)黑盒子組成。2023/10/11西安郵電學院通信工程系郭娟1.2.1分層的概念（5）假設(shè)我們討論的是第n層，那么一個節(jié)點中第n層對等模塊與對方節(jié)點中第n層對等模塊通過第n-1層進行通信時，有兩個非常重要的方面。第一方面是：需要有一個分布式算法（或稱為協(xié)議）來供兩個對等層相互交換消息，以便為高層提供所需的功能和業(yè)務。第二方面是第n層和第n-1層之間的接口（API），該接口對于實際系統(tǒng)的設(shè)計和標準化非常重要。2023/10/11西安郵電學院通信工程系郭娟1.2.2 OSI協(xié)議的體系結(jié)構(gòu)國際標準化組織（ISO）將協(xié)議體系結(jié)構(gòu)模型分為七個層次：應用層、表示層、會話層、運輸層、網(wǎng)絡層、數(shù)據(jù)鏈路層和物理層，并將它作為開發(fā)協(xié)議標準的框架。該模型被稱為開放系統(tǒng)互連（OSI）參考模型，如圖1-9所示。2023/10/11西安郵電學院通信工程系郭娟1.2.2 OSI協(xié)議的體系結(jié)構(gòu)第一層：物理層（physicallayer）。在由物理通信信道連接的任一對節(jié)點之間，提供一個傳送比特流（比特序列）的虛擬比特管道。在發(fā)端它將從高層接收的比特流變成適合于物理信道傳輸?shù)男盘枺谑斩嗽賹⒃撔盘柣謴统伤鶄鬏數(shù)谋忍亓?。物理信道包括：雙絞線、同軸電纜、光纜、無線電信道等。2023/10/11西安郵電學院通信工程系郭娟1.2.2 OSI協(xié)議的體系結(jié)構(gòu)第二層：數(shù)據(jù)鏈路層（datalinklayer）。物理層提供的僅僅是原始的數(shù)字比特流傳送服務，它并不進行差錯保護。而數(shù)據(jù)鏈路層負責數(shù)據(jù)塊（幀）的傳送，并進行必要的同步控制、差錯控制和流量控制。由于有了第二層的服務，它的上層可以認為鏈路上的傳輸是無差錯的。2023/10/11西安郵電學院通信工程系郭娟1.2.2 OSI協(xié)議的體系結(jié)構(gòu)第三層：網(wǎng)絡層（networklayer）網(wǎng)絡層的基本功能是把網(wǎng)絡中的節(jié)點和數(shù)據(jù)鏈路有效地組織起來，為終端系統(tǒng)提供透明的傳輸通路（路徑）。網(wǎng)絡層通常分為兩個子層：網(wǎng)內(nèi)子層和網(wǎng)際子層。網(wǎng)內(nèi)子層解決子網(wǎng)內(nèi)分組的路由、尋址和傳輸問題；網(wǎng)際子層解決分組跨越不同子網(wǎng)的路由選擇、尋址和傳輸問題。它還包括不同子網(wǎng)之間速率匹配、流量控制、不同長度分組的適配、連接的建立、保持和終止等問題。2023/10/11西安郵電學院通信工程系郭娟1.2.2 OSI協(xié)議的體系結(jié)構(gòu)第四層：運輸層（transportlayer）。運輸層可以看成是用戶和網(wǎng)絡之間的“聯(lián)絡員”。它利用低三層所提供的網(wǎng)絡服務向高層提供可靠的端到端的透明數(shù)據(jù)傳送。它根據(jù)發(fā)端和終端的地址定義一個跨過多個網(wǎng)絡的邏輯連接（而不是第三層所處理的物理連接），并完成端到端（而不是第二層所處理的一段數(shù)據(jù)鏈路）的差錯校正和流量控制功能。它使得兩個終端系統(tǒng)之間傳送的數(shù)據(jù)單元無差錯，無丟失或重復，無次序顛倒。2023/10/11西安郵電學院通信工程系郭娟1.2.2 OSI協(xié)議的體系結(jié)構(gòu)第五層：會話層（sessionlayer）。會話層負責控制兩個系統(tǒng)的表示層（第六層）實體之間的對話。它的基本功能是向兩個表示層實體提供建立和使用連接的方法，而這種表示層之間的連接就叫做“會話”（session）。2023/10/11西安郵電學院通信工程系郭娟1.2.2 OSI協(xié)議的體系結(jié)構(gòu)第六層：表示層（presentationlayer）。表示層負責定義信息的表示方法，并向應用程序和終端處理程序提供一系列的數(shù)據(jù)轉(zhuǎn)換服務，以使兩個系統(tǒng)用共同的語言來進行通信。表示層的典型服務有：數(shù)據(jù)表示（信息編碼、加密和字符集的翻譯），格式化（數(shù)據(jù)格式的修改及文本壓縮）和語法選擇（語法的定義及不同語言之間的翻譯）等。2023/10/11西安郵電學院通信工程系郭娟1.2.2 OSI協(xié)議的體系結(jié)構(gòu)第七層：應用層（applicationlayer）。應用層是最高的一層，直接向用戶（即應用進程AP）提供服務，它為用戶進入OSI環(huán)境提供了一個窗口。應用層包含了管理功能，同時也提供一些公共的應用程序，如文件傳送，作業(yè)傳送和控制，事務處理，網(wǎng)絡管理等等。2023/10/11西安郵電學院通信工程系郭娟1.2.2 OSI協(xié)議的體系結(jié)構(gòu)高層功能低層功能2023/10/11西安郵電學院通信工程系郭娟1.2.3TCP/IP協(xié)議的體系結(jié)構(gòu)TCP/IP(Transmission Control Protocol/InternetProtocol)協(xié)議族是美國國防部高級研究規(guī)劃局(DARPA)所資助的實驗性分組交換網(wǎng)絡ARPARNET上研究開發(fā)成功的。TCP/IP協(xié)議族的通信任務組織成五個相對獨立的層次：應用層、運輸層、互連網(wǎng)層、網(wǎng)絡接入層、物理層。（它沒有OSI七層模型中的表示層和會話層）。TCP/IP協(xié)議族重點強調(diào)應用層、運輸層和互連網(wǎng)層，而對網(wǎng)絡接入層只要求能夠使用某種協(xié)議來傳送互連網(wǎng)層的分組。2023/10/11西安郵電學院通信工程系郭娟1.2.3TCP/IP協(xié)議的體系結(jié)構(gòu)網(wǎng)絡接入層的主要功能是解決與硬件相關(guān)的功能，向互連網(wǎng)層提供標準接口。從網(wǎng)絡的角度來講，它是解決在一個網(wǎng)絡中兩個端系統(tǒng)之間傳送數(shù)據(jù)的問題，以及一個端系統(tǒng)（計算機）和它連接的網(wǎng)絡之間的數(shù)據(jù)交換。2023/10/11西安郵電學院通信工程系郭娟1.2.3TCP/IP協(xié)議的體系結(jié)構(gòu)如果兩臺設(shè)備連在兩個不同的網(wǎng)絡上，要使數(shù)據(jù)穿過多個互連的網(wǎng)絡正確地傳輸，這是互連網(wǎng)層（網(wǎng)際層）要完成的功能。該層采用的協(xié)議稱為互連網(wǎng)協(xié)議（IP），它提供跨越多個網(wǎng)絡的選路功能和中繼功能。IP解決了網(wǎng)絡互連問題，但它是一個不可靠的傳輸協(xié)議。在傳輸過程中可能會出現(xiàn)IP報文的錯誤、丟失和亂序等問題。2023/10/11西安郵電學院通信工程系郭娟1.2.3TCP/IP協(xié)議的體系結(jié)構(gòu)TCP為應用程序之間的數(shù)據(jù)傳輸提供可靠連接，它是面向連接的傳輸控制協(xié)議。UDP為應用層提供無連接的服務，它并不保證一定傳到，也不保證按順序傳輸以及不重復傳送。2023/10/11西安郵電學院通信工程系郭娟1.2.4混合的分層協(xié)議體系由于現(xiàn)代通信網(wǎng)絡的低層基本都是參照OSI的模型設(shè)計的，而TCP/IP協(xié)議隨著Internet的飛速發(fā)展而被廣泛采用，因而通常采用混合的分層協(xié)議體系來描述一個信息網(wǎng)絡，如圖1-11所示。它包括應用層、運輸層、網(wǎng)絡層、數(shù)據(jù)鏈路層和物理層。2023/10/11西安郵電學院通信工程系郭娟內(nèi)容1.1通信網(wǎng)絡的基本構(gòu)成1.2協(xié)議體系及分層的概念1.3通信網(wǎng)絡中的數(shù)學基礎(chǔ)1.4通信網(wǎng)絡的基本理論問題

2023/10/11西安郵電學院通信工程系郭娟1.3通信網(wǎng)絡中的數(shù)學基礎(chǔ)

1.3.1隨機過程的基本概念

1.3.2Poisson過程

1.3.3馬爾可夫鏈

1.3.4圖論基礎(chǔ)2023/10/11西安郵電學院通信工程系郭娟1.3通信網(wǎng)絡中的數(shù)學基礎(chǔ)為了定量地描述通信網(wǎng)絡的運行過程、設(shè)計通信網(wǎng)絡的體系結(jié)構(gòu)和評估通信網(wǎng)絡容量、時延和服務質(zhì)量等，我們需要了解網(wǎng)絡中每個鏈路、節(jié)點、交換機/路由器，用戶終端等設(shè)備的輸入輸出業(yè)務流的行為特征和處理過程。描述這些行為特征和處理過程的基本數(shù)學基礎(chǔ)是隨機過程和排隊論，描述網(wǎng)絡結(jié)構(gòu)的基本方法是圖論。本節(jié)主要討論常用的隨機過程和圖論基礎(chǔ)，在第三章中將詳細討論排隊論的基本內(nèi)容。

2023/10/11西安郵電學院通信工程系郭娟1.3.1隨機過程的基本概念（1）隨機過程是用來描述在一個觀察區(qū)間內(nèi)某一實體（瀑布的水流量、食堂中的人數(shù)）的隨機行為。例如:在通信系統(tǒng)中的噪聲就是一個典型的隨機過程。(n臺性能完全相同的通信接收機的輸出如下圖。(1)(2)(n)2023/10/11西安郵電學院通信工程系郭娟1.3.1隨機過程的基本概念（2）隨機過程是隨機變量概念在時間域上的延伸。直觀地講，隨機過程是時間t的函數(shù)的集合，在任一個觀察時刻，隨機過程的取值是一個隨機變量。或者說，依賴于時間參數(shù)t的隨機變量所構(gòu)成的總體稱為隨機過程?！?023/10/11西安郵電學院通信工程系郭娟1.3.1隨機過程的基本概念（3）設(shè)X(t)是一個隨機過程，則可以從兩個方面來描述X(t)的特征：一是在任意時刻t1，隨機變量X(t1)的統(tǒng)計特征，如一維分布函數(shù)，概率密度函數(shù)，均值和方差等。二是同一隨機過程在不同時刻t1和t2對應的隨機變量X(t1)

和X(t1)

的相關(guān)特性，如多維聯(lián)合分布函數(shù)、相關(guān)函數(shù)、協(xié)方差矩陣等?！?023/10/11西安郵電學院通信工程系郭娟1.3.1隨機過程的基本概念（4）隨機過程X(t)的一維分布函數(shù)，定義為

Ft(x)=P{X(t)<x}

式中P{}表示概率。如果Ft(x)對x的微分存在，則X(t)的一維概率密度函數(shù)定義為

2023/10/11西安郵電學院通信工程系郭娟1.3.1隨機過程的基本概念（5）通常一維分布函數(shù)不能完全描述隨機過程的特征，需要采用n維聯(lián)合分布函數(shù)。對于給定的n個時刻t1，t2，…，tn，隨機變量X(t1)，X(t2)，…，X(tn)的聯(lián)合分布函數(shù)為：則隨機過程X(t)的均值函數(shù)為

2023/10/11西安郵電學院通信工程系郭娟1.3.1隨機過程的基本概念（6）若對任給的時刻t1和t2，如下列函數(shù)存在，則稱CX(t1,t2)為X(t)的協(xié)方差函數(shù)。為X(t)的方差函數(shù)。2023/10/11西安郵電學院通信工程系郭娟1.3.1隨機過程的基本概念（7）若對任給的時間t1和t2，RX(t1,t2)=E[X(t1)X(t2)]存在，則RX(t1,t2)為X(t)的自相關(guān)函數(shù)。協(xié)方差函數(shù)，自相關(guān)函數(shù)、均值函數(shù)有下列關(guān)系：

Cx(t1,t2)=Rx(t1,t2)-mx(t1)mx(t2)2023/10/11西安郵電學院通信工程系郭娟1.3.1隨機過程的基本概念（8）幾類典型的隨機過程：1.獨立隨機過程2.馬爾可夫(Markov)過程3．獨立增量過程4．平隱隨機過程5．Poisson過程6.馬爾可夫鏈2023/10/11西安郵電學院通信工程系郭娟1.獨立隨機過程設(shè)有一個隨機過程X(t)，如果對任意給定的時刻t1，t2，…，tn，隨機變量X(t1),X(t2),…,X(tn)是相互獨立的，也就是其n維分布函數(shù)可以表示為：

則稱X(t)是獨立隨機過程。該過程的特點是任意一時刻的狀態(tài)與其他任何時刻的狀態(tài)無關(guān)。2023/10/11西安郵電學院通信工程系郭娟2.馬爾可夫(Markov)過程(1)設(shè)有一個隨機過程X(t)，如果對于一個任意的時間序列：t1<t2<…<tn，n≥3，在給定隨機變量的X(t1)=x1,X(t2)=x2,… ,X(tn-1)=xn-1的條件下,X(tn)=xn

的分布可以表示為：則稱X(t)為馬爾可夫過程或簡稱為馬氏過程。2023/10/11西安郵電學院通信工程系郭娟2.馬爾可夫(Markov)過程(2)該過程的基本特點是無后效性。當該過程在t0時刻的狀態(tài)為已知的條件下，則該過程在t(>t0)所處的狀態(tài)與該過程在t0時刻之前的狀態(tài)無關(guān)。式（1-9）右端的條件分布函數(shù)可以寫成：該式稱為馬氏過程的轉(zhuǎn)移概率。2023/10/11西安郵電學院通信工程系郭娟3．獨立增量過程設(shè)X(t2)-X(t1)=X(t1,t2)是隨機過程X(t)在時間間隔[t1,t2)上的增量，如果對于時間t的任意n個值0≤t1<t2<…<tn，增量X(t1,t2),X(t2,t3),…,X(tn-1,tn)是相互獨立的，則稱X(t)為獨立增量過程。該過程的特點是：在任一時間間隔上過程狀態(tài)的改變并不影響未來任一時間間隔上狀態(tài)的改變?？梢宰C明獨立增量過程是一種特殊的馬爾可夫過程。2023/10/11西安郵電學院通信工程系郭娟4．平隱隨機過程(1)如果對于時間t的任意n個值t1，t2

，…，tn和任意實數(shù)，隨機過程X(t)的n維分布函數(shù)滿足關(guān)系式：則稱X(t)為平穩(wěn)隨機過程或簡稱為平穩(wěn)過程。該過程的特點是隨機過程的統(tǒng)計特性不隨時間的平移而變化。2023/10/11西安郵電學院通信工程系郭娟4．平隱隨機過程(2)按照上述定義的隨機過程通常稱為嚴（狹義）平穩(wěn)過程。在實際應用中，我們更關(guān)心這樣一類過程：其E[|X(t)|2]

<∞（二階矩過程），且滿足下列條件：1）均值為常量（與時間t無關(guān)）；2）對于任意時刻s和t，其相關(guān)函數(shù)滿足Rx(s,t)=Rx(t-s),即相關(guān)函數(shù)僅與時差t-s有關(guān)，而與s,t的取值無關(guān)；稱這類過程為寬（廣義）平穩(wěn)過程。在實際應用中所指的隨機過程通常是寬平穩(wěn)過程。2023/10/11西安郵電學院通信工程系郭娟各態(tài)歷經(jīng)性(1)平穩(wěn)過程中一個重要特征就是是否具有各態(tài)歷經(jīng)性。為了說明各態(tài)歷經(jīng)性，在時間軸上定義下列兩種平均：為隨機過程的時間均值和時間相關(guān)函數(shù)。2023/10/11西安郵電學院通信工程系郭娟各態(tài)歷經(jīng)性(2)如果X(t)是一個平穩(wěn)過程，如果<X(t)>=E[X(t)]=mx依概率1成立（即對所有樣本都成立），則稱隨機過程X(t)的均值具有各態(tài)歷經(jīng)性；如果依概率1成立，則稱過程X(t)的自相關(guān)函數(shù)具有各態(tài)歷經(jīng)性；如果X(t)的均值和自相關(guān)函數(shù)都具有各態(tài)歷經(jīng)性，則稱X(t)是（寬）各態(tài)歷經(jīng)過程，或者說X(t)是各態(tài)歷經(jīng)的。2023/10/11西安郵電學院通信工程系郭娟1.3.2 Poisson過程(1)在日常生活中，如果我們觀察顧客進入商店、銀行或其它公共服務場所的過程，我們發(fā)現(xiàn)如果把一位顧客的到達看成一個“隨機點”，則這是一個源源不斷出現(xiàn)隨機點的過程。在這一過程中任一段時間內(nèi)到達的顧客數(shù)也是隨機的。這類描述到達顧客數(shù)及其特征的過程通常稱為計數(shù)過程。如果我們考察一個交換局中電話呼叫到達（人們撥打電話的行為中拿起電話并撥出對方號碼的動作稱為一次電話呼叫到達）的過程也具有類似的特征。

2023/10/11西安郵電學院通信工程系郭娟1.3.2 Poisson過程(2)設(shè)一個隨機過程為{A(t),t≥0}的取值為非負整數(shù)，如果該過程滿足下列條件，則稱該過程為到達率為λ的Poisson(泊松)過程:(1)A(t)是一個計數(shù)過程，它表示在[0,t）區(qū)間內(nèi)到達的用戶總數(shù)，A(0)=0,A(t)的狀態(tài)空間為{0,1,2,…}。如圖1-12所示。任給兩個時刻s和t，且s<t，則A(t)-A(s)即為[s,t)之間到達的用戶總數(shù)。2023/10/11西安郵電學院通信工程系郭娟1.3.2 Poisson過程(3)(2)A(t)是一個獨立增量過程。即在兩個不同時間區(qū)間（區(qū)間不重疊）內(nèi)到達的用戶數(shù)是相互獨立的。(3)任一個長度為

的區(qū)間內(nèi)，到達的用戶數(shù)服從參數(shù)為λ

的Poisson分布，即其均值和方差均為。由于在區(qū)間τ內(nèi)平均到達的用戶數(shù)為，則λ即為單位時間平均到達的用戶數(shù)或稱為到達率。2023/10/11西安郵電學院通信工程系郭娟1.3.2 Poisson過程(4)Poisson過程的基本特征有：（1）到達時間間隔=tn+1-tn相互獨立，且服從指數(shù)分布，其概率密度函數(shù)為其分布函數(shù)為該特性說明Poisson過程的到達間隔服從指數(shù)分布。相反，如果一個計數(shù)過程的到達間隔序列是相互獨立同分布，其分布是參數(shù)為的指數(shù)分布，則該過程是到達率為的Poisson過程。因此，說“顧客到達過程為到達率為的Poisson過程”與說“顧客到達間隔相互獨立

且服從參數(shù)

為的的指數(shù)分布是等價的。2023/10/11西安郵電學院通信工程系郭娟1.3.2 Poisson過程(5)（2）對于一個任意小的區(qū)間≥0，將Poisson分布用Taylor級數(shù)展開，即利用可得：式中，o()表示的高階無窮小，即2023/10/11西安郵電學院通信工程系郭娟1.3.2 Poisson過程(6)（3）多個相互獨立的Poisson過程之和

A=A1+A2+…+Ak

仍是一個Poisson過程，其到達率為λ=λ1+λ2+…+λk

，式中λk是Poisson過程Ak的到達率。2023/10/11西安郵電學院通信工程系郭娟1.3.2 Poisson過程(6)（4）如果將一個Poisson過程的到達以概率p和1-p獨立地分配給兩個子過程，則這兩個子過程也是Poisson過程。注意:這里是將到達獨立地進行分配。如果把到達交替的分配給兩個子過程，即兩個子過程分別由奇數(shù)號到達和偶數(shù)號到達組成，則這兩個子過程就不是Poisson過程。2023/10/11西安郵電學院通信工程系郭娟1.3.2 Poisson過程(6)例1.1有紅、綠、藍三種顏色的汽車，分別以強度為λR、λG、λB的Poisson流到達某哨卡，設(shè)它們是相互獨立的。把汽車合并成單個輸出過程（假設(shè)汽車長度為0）。2023/10/11西安郵電學院通信工程系郭娟1.3.2 Poisson過程(7)（1）求兩輛汽車之間的時間間隔的概率密度函數(shù)；解:由于獨立的Poisson過程之和仍為Poisson過程，且其強度為λC=λR+λG+λB。設(shè)ZC為兩輛汽車到達的時間間隔，則其概率密度函數(shù)為:合成的過程的特性？2023/10/11西安郵電學院通信工程系郭娟1.3.2 Poisson過程(7)(2)求在t0時刻觀察到一輛紅色汽車，下一輛汽車將是(a)紅的，(b)藍的，(c)非紅的概率；設(shè)ZR、ZG、ZB分別為兩輛紅色、綠色、藍色汽車到達的時間間隔，Zx為紅色與非紅色汽車到達的時間間隔，λx為非紅色汽車的到達強度，則有：λx=λG+λB

。ZRt02023/10/11西安郵電學院通信工程系郭娟1.3.2 Poisson過程(7)2023/10/11西安郵電學院通信工程系郭娟1.3.2 Poisson過程(8)（2）求在t0時刻觀察到一輛紅色汽車，下一輛汽車將是(a)紅的，(b)藍的，(c)非紅的概率；令Zy為從t0起的非藍色汽車到達的時間間隔，λy為非藍色汽車的到達強度，則有：λy=λG+λR

ZBt02023/10/11西安郵電學院通信工程系郭娟1.3.2 Poisson過程(8)2023/10/11西安郵電學院通信工程系郭娟1.3.2 Poisson過程(10)（3）求在t0時刻觀察到一輛紅色汽車，下三輛汽車是紅的，然后又是一輛非紅色汽車將到達的概率。2023/10/11西安郵電學院通信工程系郭娟1.3.3 馬爾可夫鏈(1)馬爾可夫（Markov）鏈是最簡單的馬氏過程----即時間和狀態(tài)過程的取值參數(shù)都是離散的馬氏過程。{X(t1),X(t2),X(t3),…,X(tn),…}2023/10/11西安郵電學院通信工程系郭娟1.3.3 馬爾可夫鏈(2)我們把可列個發(fā)生狀態(tài)轉(zhuǎn)移（變化）的時刻記為t1，t2，…,tn，…，在tn時刻發(fā)生的轉(zhuǎn)移稱為第n次轉(zhuǎn)移；并且假定在每一個時刻tn(n=1,2,…),Xn=X(tn)所有可能的狀態(tài)的集合S是可數(shù)的，即可表示為S={0,1,2,…}。對應于時間序列t1,t2,…tn,…,馬氏鏈的狀態(tài)序列為i1,i2,…,in,…。這時對應于式（1-9）（馬氏過程的概率分布）有馬氏鏈的轉(zhuǎn)移概率為：P{Xn=in|Xn-1=in-1,…,x1=i1}=P{Xn=in|Xn-1=in-1}該式表示在Xn-1=in-1的條件下，第n次轉(zhuǎn)移出現(xiàn)in的概率。2023/10/11西安郵電學院通信工程系郭娟1.3.3 馬爾可夫鏈(3)如轉(zhuǎn)移概率與n無關(guān)（即與哪一次轉(zhuǎn)移無關(guān)，僅與轉(zhuǎn)移前后的狀態(tài)有關(guān)），則該馬氏鏈為齊次馬氏鏈；否則稱為非齊次馬氏鏈。此時式（1-21）可以表示為Pij=P{Xn=j|Xn-1=I}上式稱為馬氏鏈的（一步）轉(zhuǎn)移概率。Pij滿足下列條件：

2023/10/11西安郵電學院通信工程系郭娟1.3.3 馬爾可夫鏈(4)相應的轉(zhuǎn)移概率矩陣可以表示為：2023/10/11西安郵電學院通信工程系郭娟1.3.3 馬爾可夫鏈(5)例1.2 設(shè)一盲人（或一個隨機點）在如圖1-13所示的線段上游走，其步長為l。假定他只能在a1=2l，a2=l，a3=0，a4=-l，a5=-2l這5個點上停留，且只在時刻t=1,2,…上發(fā)生游走。游走的規(guī)則是：如果游走前他在a2，a3，a4這幾個點上，那么就分別以1/2的概率向左或向右走動一步；如果游走前他在a1(a5)上，那么就以概率1走到a2(a4)點上。

2023/10/11西安郵電學院通信工程系郭娟1.3.3 馬爾可夫鏈(6)以Xn=ai,i=1,2,3,4,5表示在t=n時刻盲人位于停留點ai處，則容易看出X1,X2,…是一個馬氏鏈，且他游走的轉(zhuǎn)移概率矩陣為：2023/10/11西安郵電學院通信工程系郭娟1.3.3 馬爾可夫鏈(7)如果用圖來表示這一轉(zhuǎn)移過程，則可得圖1-14。圖中的圓圈表示馬氏過程的狀態(tài)，圖中帶箭頭的弧線表示狀態(tài)的轉(zhuǎn)移，弧線上的數(shù)字表示一步轉(zhuǎn)移概率。該圖稱為馬氏過程的狀態(tài)轉(zhuǎn)移圖。2023/10/11西安郵電學院通信工程系郭娟1.3.3 馬爾可夫鏈(8)在考察馬氏過程中，我們還經(jīng)常用到n步轉(zhuǎn)移概率，即它表示當前（第m步）的狀態(tài)為i，經(jīng)過n步轉(zhuǎn)移后（第n+m步）系統(tǒng)的狀態(tài)為j的概率。

2023/10/11西安郵電學院通信工程系郭娟1.3.3 馬爾可夫鏈(9)系統(tǒng)中n=m1+m2步狀態(tài)轉(zhuǎn)移概率可用下式(Chapman—Kolmogorov)等式來求解：2023/10/11西安郵電學院通信工程系郭娟1.3.3 馬爾可夫鏈(10)根據(jù)n步轉(zhuǎn)移概率，就可以來定義馬氏鏈狀態(tài)轉(zhuǎn)移的特性。如果馬氏鏈的兩個狀態(tài)i和j有下列特性：即存在整數(shù)n和n’有及（也就是從狀態(tài)i(j)經(jīng)過n(n’)步轉(zhuǎn)移到狀態(tài)j(i)的概率大于0），則稱i和j是互通的。如果馬氏鏈的所有狀態(tài)都是互通的，則該馬氏鏈是不可約的(irreducible)。2023/10/11西安郵電學院通信工程系郭娟1.3.3 馬爾可夫鏈(11)如果馬氏鏈的狀態(tài)i有下列特性：存在某個整數(shù)m≥1,使，且存在某個整數(shù)d>1并僅當n為d的整倍時有，則狀態(tài)i是有周期性的。如果馬氏鏈中沒有一個狀態(tài)是有周期性的，則稱該馬氏鏈為非周期的。本課程中僅考慮非周期不可約的馬氏鏈。上面討論了狀態(tài)之間的轉(zhuǎn)移概率，同時我們還需關(guān)心過程處于某一狀態(tài)的穩(wěn)態(tài)概率。2023/10/11西安郵電學院通信工程系郭娟1.3.3 馬爾可夫鏈(12)對于馬氏鏈，其狀態(tài)的穩(wěn)態(tài)概率定義為：如果有則稱概率分布{Pj|j≥0}是馬氏鏈的穩(wěn)態(tài)分布。對于概率分布有穩(wěn)態(tài)概率反映了系統(tǒng)達到穩(wěn)態(tài)后，系統(tǒng)處于某一狀態(tài)的可能性（概率）。2023/10/11西安郵電學院通信工程系郭娟1.3.3 馬爾可夫鏈(13)穩(wěn)態(tài)分布可以表示為：即過程從初始狀態(tài)X0=i出發(fā)，最終轉(zhuǎn)移到狀態(tài)Xn=j的概率。顯然Pj與初始狀態(tài)X0=i無關(guān)。穩(wěn)態(tài)分布也可以表示為：（以概率1成立）

因此pj表示該過程中訪問狀態(tài)j的時間比例或頻率，且該頻率與初始狀態(tài)無關(guān)。2023/10/11西安郵電學院通信工程系郭娟1.3.3 馬爾可夫鏈(14)由于，則結(jié)合有該式為全局平衡方程(Global balanceequations)。它表示在穩(wěn)態(tài)情況下，從一個狀態(tài)j轉(zhuǎn)移出去的頻率（上式左邊）等于轉(zhuǎn)移進入狀態(tài)j的頻率（上式右邊）。該方程提供給我們一種典型的求解穩(wěn)態(tài)概率分布的方法。2023/10/11西安郵電學院通信工程系郭娟1.3.3 馬爾可夫鏈(15)例1.2（續(xù)）求隨機游走過程的穩(wěn)態(tài)概率。在例1.2中我們已知各種狀態(tài)的轉(zhuǎn)移概率矩陣為：2023/10/11西安郵電學院通信工程系郭娟設(shè)狀態(tài)a5,a4,a3,a2,a1的穩(wěn)態(tài)概率為p5,

p4,p3,p2和p1，則我們根據(jù)可得穩(wěn)態(tài)概率的方程為：2023/10/11西安郵電學院通信工程系郭娟1.3.3 馬爾可夫鏈(16)由于{pi|i=1,2,...5}是穩(wěn)態(tài)概率分布，則有求解式(1-31)和式(1-32)組成的方程組，得穩(wěn)態(tài)概率分布為：

(p5,p4,p3,p2,p1)=(1/8,1/4，1/4，1/4，1/8)2023/10/11西安郵電學院通信工程系郭娟生滅（birth-death）過程(1)在實際中，我們經(jīng)常遇到這樣一類特殊的馬氏過程：僅有相鄰狀態(tài)的轉(zhuǎn)移，而沒有其它狀態(tài)的轉(zhuǎn)移（即如果|i–j|>1，則Pij=0），如圖1-15所示。這一類過程通常稱為生滅（birth-death）過程。2023/10/11西安郵電學院通信工程系郭娟生滅（birth-death）過程(2)它表示一個群體（動物、生物等）總數(shù)為n的特殊狀態(tài)轉(zhuǎn)移過程。該群體總數(shù)的狀態(tài)轉(zhuǎn)移只有三種可能：或者從n增加一個（群體出生一個），或者從n減少一個（死亡一個），或者群體的總數(shù)n保持不變。而其它所有可能的轉(zhuǎn)移相對前三種轉(zhuǎn)移都是高階無窮小，因而可以忽略不計。該群體狀態(tài)的轉(zhuǎn)移概率取決于群體的總數(shù)n（狀態(tài)）。2023/10/11西安郵電學院通信工程系郭娟生滅（birth-death）過程(3)令S={0,1,…,n,n+1,…}，則應用式（1-30）可得：

pnPn,n+1=pn+1Pn+1,nn=0,1,…它表示在穩(wěn)態(tài)的情況下，從狀態(tài)n轉(zhuǎn)移到狀態(tài)n+1的頻率等于從狀態(tài)n+1轉(zhuǎn)移到狀態(tài)n的頻率，或在狀態(tài)轉(zhuǎn)移圖中設(shè)置一個虛擬的平面（圖1-15中的虛線），則進入該平面的頻率等于退出該平面的頻率，即該平面是系統(tǒng)的一個穩(wěn)定點。2023/10/11西安郵電學院通信工程系郭娟生滅（birth-death）過程(4)式(1-35)可推廣到一個更一般的形式：

pjPji=piPij該等式稱為詳細平衡方程（detailedbalanceequation)。如果對于一個過程，有式（1-36）成立，則意味著有式（1-30）全局平衡方程存在。但并不是任何馬爾可夫鏈都必須有式（1-36）成立。但在很多實際應用中，式（1-36）是成立的。因此實際中，我們可以先假設(shè)式（1-36）成立，然后通過它們求解穩(wěn)態(tài)概率{pj,j≥0}。如果求得的結(jié)果滿足，則求得的分布{pj,j≥0}就是滿足式(1-27)的穩(wěn)態(tài)分布。2023/10/11西安郵電學院通信工程系郭娟生滅（birth-death）過程(5)例1.3 設(shè)一個特殊的生滅過程的狀態(tài)轉(zhuǎn)移概率為Pn,n+1=pR,Pn+1,n=pL,試求其穩(wěn)態(tài)分布。解：利用式（1-35）（或假設(shè)式（1-36）成立）有：從而有：式中

經(jīng)過遞推得：2023/10/11西安郵電學院通信工程系郭娟生滅（birth-death）過程(6)顯然只有在的情況下，才可能有下式成立:從而可得進而可得：綜上可得，在的情況下，該生滅過程的穩(wěn)態(tài)分布為2023/10/11西安郵電學院通信工程系郭娟1.3.4圖論基礎(chǔ)圖論是一個新的數(shù)學分支，在很多領(lǐng)域都得到了廣泛的應用。在通信網(wǎng)絡中，許多問題的描述都是基于圖論的，因此，我們下面對圖論的一些基本概念進行討論。 2023/10/11西安郵電學院通信工程系郭娟1.圖的概念（1）一般幾何上將圖定義成空間中一些點（頂點）和連接這些點的線（邊）的集合。圖論中將圖定義為G=(V,E)，其中V表示頂點的集合，E表示邊的集合。例如：如圖1-16所示的圖可以表示為：V={v1,v2,v3,v4},E={e1,e2,e3,e4,e5,e6}2023/10/11西安郵電學院通信工程系郭娟1.圖的概念（2）我們也可以用邊的兩個頂點來表示邊。如果邊e的兩個頂點是u和v，那么e可寫成e=(u,v)，這里（u,v）表示u和v的有序?qū)ΑＨ绻校╱,v）和（v,u）同時存在，它表達了以u，v為端點的一條無向邊。如果圖中的所有邊都是無向邊，則稱該圖為無向圖?？梢赃@樣來表示無向圖1-16：G=(V,E)，V={v1,v2,v3,v4},E={(v1,v2),(v1,v3),(v1,v4),(v2,v3),(v2,v4),(v3,v4)}

或：E={(v2,v1),(v3,v1),(v4,v1),(v3,v2),(v4,v2),(v4,v3)}

2023/10/11西安郵電學院通信工程系郭娟1.圖的概念（3）一般圖G=(V,E)的頂點數(shù)用n=(|V|)表示，邊的數(shù)目用m=(|

E|)表示。若V 和E都是有限的，則稱圖G是有限圖，否則稱為無限圖。2023/10/11西安郵電學院通信工程系郭娟1.圖的概念（4）在實際應用中，圖中每條邊可能有一個方向是很自然的（它反映了信息或物質(zhì)的流向）。當給圖G的每一條邊都規(guī)定一個方向，則稱該圖為有向圖。對有向圖圖G=(V,E)，有向邊e用與其關(guān)聯(lián)的頂點（u，v）的有序?qū)肀硎?，即e=(u,v)，它表示u為邊e的起點，v為邊e的終點。圖1-17所示的有向圖可表示如下：G=(V,E)，V={v1,v2,v3,v4},E={(v1,v2),(v1,v3),(v1,v4),(v2,v3),(v2,v4),(v3,v4)}2023/10/11西安郵電學院通信工程系郭娟1.圖的概念（5）如果頂點v是邊e的一個端點，則稱邊e和頂點v相關(guān)聯(lián)(incident)；對于頂點u和v，若(u,v)∈E，則稱u和v是鄰接的（adjacent）。在圖1-16中，邊e2，e4，e5都與頂點v4相關(guān)聯(lián)，v4分別與v1，v2，v3相鄰接。若兩條邊有共同的頂點，則稱這兩條邊是鄰接的。在圖1-16中，邊e1，e2，e3兩兩相鄰接。2023/10/11西安郵電學院通信工程系郭娟1.圖的概念（6）對圖G=(V,E)和G’=(V’,E’)來說，若有V’?V和E’?E，則稱圖G’是圖G的一個子圖；若V’V或E’

E，則稱圖G’是圖G的一個真子圖。2023/10/11西安郵電學院通信工程系郭娟2．路徑與回路(1)定義：圖的一些頂點和邊的交替序列=v0e1v1...vk-1ekvk，且邊ei的端點為vi-1和vi，i=1,2,3,…k，則稱

為一條路徑（Path），v0和vk分別為

的起點和終點。如果

中所有的邊均不相同，則稱其為簡單路徑。以v0為起點，vk為終點的路徑稱為v0-

vk路徑。如果路徑

中有v0=vk，則

為回路(或環(huán)Cycle)，回路中沒有重復邊時稱為簡單回路。2023/10/11西安郵電學院通信工程系郭娟2．路徑與回路(2)例4：在圖1-18中，S={v1e1v2e3v3e6v4}是一路徑，C={v1e1v2e3v3e6v4e4v1}是一回路。2023/10/11西安郵電學院通信工程系郭娟2．路徑與回路(3)定義：對圖G=(V,E)來說，若G的兩個頂點u，v之間存在一條路徑，則稱u和v是連通的；若圖G的任意兩個頂點都是連通的，則稱圖G是連通的；否則是非連通的。非連通的圖可分解為若干連通的子圖。2023/10/11西安郵電學院通信工程系郭娟2．路徑與回路(4)圖1-19的無方向圖中，圖（a）中任意兩個頂點之間都有路徑，所以該圖是連通的；圖(b)中頂點3和其它頂點之間沒有路徑，所以該圖是非連通的；圖（c）則是一個孤立的節(jié)點。2023/10/11西安郵電學院通信工程系郭娟2．路徑與回路(5)對于有向圖，若邊去掉方向后是連通的，則稱該圖為連通的有向圖。若對于有向圖的任意兩個頂點u和v之間存在u到v的路徑和v到u的路徑時，稱該圖為強連通的。圖1-20（a）的有向圖是一個連通的有向圖，但不是強連通的。因為頂點2和頂點3之間不存在雙向的路徑；圖1-20（b）是一個強連通的圖，該圖中任意兩個頂點之間都存在雙向的路徑。 圖1-20方向圖（a）連通的方向圖(b)強連通的方向圖2023/10/11西安郵電學院通信工程系郭娟生成樹和最小重量生成樹（1）定義：不包括回路（環(huán)）的連通圖，稱為樹。定義：對于圖G=(V,E)，包含了圖G中所有頂點的樹稱為生成樹（SpanningTree）。在圖1-21中，圖（b）、（c）和（d）都是樹。而圖（a）由于有回路，所以不是樹。在圖1-21中，圖（b）和圖（c）都是圖（a）的生成樹。2023/10/11西安郵電學院通信工程系郭娟3.生成樹和最小重量生成樹(2)對于一個給定的圖G=(V,E)，其生成樹的構(gòu)造算法如下：1)令n是V中的任意一個頂點，構(gòu)造子圖G’=(V’,E’)，其中，V’={n},E’=?｛空集｝；2)如果V’=V則停止。此時G’=(V’,E’)就是一個生成樹。否則進行第3）步；3)令(i,j)∈E，其中i∈V’,j∈V-V’，并采用下列方式更新V’和E’：V’:=V’∪{j}，E’:=E’∪{(i,j)}，轉(zhuǎn)到第2）步。2023/10/11西安郵電學院通信工程系郭娟3.生成樹和最小重量生成樹(3)該算法是從僅有一個頂點、0條邊的子圖開始，以后每執(zhí)行一次第3）步就增加一個頂點和一條邊。這就意味著最終生成的樹有|V|個節(jié)點,|V|-1條鏈路。通常對于一個連通圖，其邊的條數(shù)大于等于|V|-1。如果一個圖G的邊的數(shù)目等于|V|-1,則上述算法將使用該圖中所有的邊，因而有G=G’，即此時圖G本身就是一顆樹。2023/10/11西安郵電學院通信工程系郭娟3.生成樹和最小重量生成樹(4)一般而言，對于一個圖可以有很多個生成樹。對于通信網(wǎng)絡來說，利用生成樹來實現(xiàn)廣播是比較經(jīng)濟的。但每一條邊的成本或時延通常是不相同的，這時就要考慮樹中各邊的重量（成本或時延）。通常我們用Wij表示邊（i,j）的重量。最小重量生成樹（MST，MinimumWeightSpanningTree）：是指邊的重量和最小的生成樹。2023/10/11西安郵電學院通信工程系