文章目錄

• 第四章 多址技術(shù)
• • 4.1 多址協(xié)議概述
  • • 4.1.1 MAC層在通信協(xié)議中的位置
    • 4.1.2 多址協(xié)議的分類
    • 4.1.3 系統(tǒng)模型
  • 4.2 固定多址接入?yún)f(xié)議
  • • 4.2.1 頻分多址接入(FDMA)
    • 4.2.2 時分多址接入?yún)f(xié)議(TDMA)
    • 4.2.3 固定多址接入?yún)f(xié)議的性能分析
  • 4.3 隨機(jī)多址接入技術(shù)
  • • 4.3.1 ALOHA協(xié)議
    • • 1.純ALOHA協(xié)議
      • 2.時隙ALOHA協(xié)議
    • 4.3.2 載波偵聽多址協(xié)議(CSMA)
    • • 1.非時隙CMSA多址協(xié)議
      • 2.時隙CSMA多址協(xié)議
      • 3.有碰撞檢測功能的載波偵聽多址協(xié)議(CSMA/CD)
      • 4.有碰撞避免功能的載波偵聽多址協(xié)議(CSMA/CA)
  • 4.4 沖突分解算法
  • • 4.4.1 樹形分裂算法
    • 4.4.2 先到先服務(wù)(FCFS)分裂算法
  • 4.4 預(yù)約多址接入技術(shù)
  • 4.5 本章課后習(xí)題

第四章 多址技術(shù)

4.1 多址協(xié)議概述

網(wǎng)絡(luò)中的終端設(shè)備通過通信子網(wǎng)來訪問網(wǎng)絡(luò)中的資源。當(dāng)多個終端同時訪問同一資源（如共享的通信信道）時，就可能會產(chǎn)生信息碰撞，導(dǎo)致通信失敗。典型的共享鏈路有：衛(wèi)星鏈路和蜂窩移動通信系統(tǒng)的鏈路、局域網(wǎng)、分組無線電網(wǎng)等，如圖4-1所示。

在衛(wèi)星和蜂窩移動通信系統(tǒng)中，多個用戶采用競爭或預(yù)約分配等方法向一個中心站（衛(wèi)星或移動通信系統(tǒng)中的基站）發(fā)送信息，中心站通過下行鏈路（中心站到用戶的鏈路）發(fā)送應(yīng)答信息。

在局域網(wǎng)中，一個用戶發(fā)送，所有用戶都可以接收到，它是一個全連通的網(wǎng)絡(luò)，其典型網(wǎng)絡(luò)是以太網(wǎng)（Ethernet）。

在分組無線電網(wǎng)絡(luò)中，用戶分布在一個很廣的范圍內(nèi)，每個用戶僅能接收到其通信范圍以內(nèi)的信息，任意兩個用戶之間可能需要多次中轉(zhuǎn)才能相互交換信息，它是一個部分連通（或稱為多跳）的網(wǎng)絡(luò)。

在上述網(wǎng)絡(luò)中，如果多個用戶同時發(fā)送時，就會發(fā)生多個用戶的幀在物理信道上相互重疊（即碰撞），可能使得接收端無法正確接收。

為了有效地進(jìn)行通信，就需要有某種機(jī)制來決定資源的使用權(quán)，這就是網(wǎng)絡(luò)的多址接入控制問題。所謂多址接入?yún)f(xié)議(Multiple Access Protocol)就是在一個網(wǎng)絡(luò)中，解決多個用戶如何高效共享一個物理鏈路資源的技術(shù)。

4.1.1 MAC層在通信協(xié)議中的位置

從分層的角度來說，多址技術(shù)是數(shù)據(jù)鏈路層的一個子層。多址接入控制層（Medium Access Control，MAC層）在通信協(xié)議中的位置如圖所示。它處于數(shù)據(jù)鏈路邏輯控制層（LLC）的下方，物理層（PHY）的上方。MAC層將有限的資源分配給多個用戶，從而使得在眾多用戶之間實(shí)現(xiàn)公平、有效地共享有限的帶寬資源；實(shí)現(xiàn)各用戶之間良好的連通性，獲得盡可能高的系統(tǒng)吞吐量以及盡可能低的系統(tǒng)時延。邏輯鏈路控制（LLC）子層為本節(jié)點(diǎn)提供了到其臨節(jié)點(diǎn)的“鏈路”，而如何協(xié)調(diào)本節(jié)點(diǎn)和其他結(jié)點(diǎn)有效地共享帶寬資源，是媒介接入控制子層（MAC層）的主要功能。

4.1.2 多址協(xié)議的分類

多址協(xié)議主要分為固定分配多址接入?yún)f(xié)議、隨機(jī)分配多址接入?yún)f(xié)議和基于預(yù)約方式的多址接入?yún)f(xié)議。

所謂固定分配多址接入是指在用戶接入信道時，專門為其分配一定的信道資源（如頻率、時隙、碼字或空間），用戶獨(dú)享該資源，直到通信結(jié)束。

所謂隨機(jī)多址接入是指用戶可以隨時接入信道，并且可能不會顧及其他用戶是否在傳輸。當(dāng)信道中同時有多個用戶接入時，在信道資源的使用上就會發(fā)生沖突（碰撞）。因此，對于有競爭的多址接入?yún)f(xié)議如何解決沖突，從而使所有碰撞用戶都可以成功進(jìn)行傳輸是一個非常重要的問題。

所謂基于預(yù)約的多址接入?yún)f(xié)議，是指在數(shù)據(jù)分組傳輸之前，先進(jìn)行資源預(yù)約。一旦預(yù)約到資源（如
頻率、時隙），則在該資源內(nèi)可進(jìn)行無沖突的傳輸。可用圖４-3來描述多址接入?yún)f(xié)議的分類。

4.1.3 系統(tǒng)模型

從排隊(duì)論的觀點(diǎn)出發(fā)，多址信道可以看成一個多進(jìn)單出的排隊(duì)系統(tǒng)（即該系統(tǒng)有多個輸入而僅僅有一個輸出）。每一個節(jié)點(diǎn)都可以獨(dú)立的產(chǎn)生分組，而信道則相當(dāng)于服務(wù)員，它要為各個隊(duì)列服務(wù)。由于各個排隊(duì)隊(duì)列是相互獨(dú)立的，各節(jié)點(diǎn)無法知道其他隊(duì)列的情況，服務(wù)員也不知道各個隊(duì)列的情況，所以增加了系統(tǒng)的復(fù)雜性。如果可以通過某種措施，使各個節(jié)點(diǎn)產(chǎn)生的分組在進(jìn)入信道之前排列成一個總的隊(duì)列，然后由信道來服務(wù)，則可以有效地避免分組在信道上的碰撞，大大提高信道的利用率。如圖4-4所示。

為了能夠有效地分析多址接入?yún)f(xié)議，必須根據(jù)應(yīng)用環(huán)境做一些假設(shè)。在討論每種多址協(xié)議時，應(yīng)該考慮下列問題：
1 . 網(wǎng)絡(luò)的連通特性。通常將網(wǎng)絡(luò)按其連通模式分為：單跳、兩跳及多跳網(wǎng)絡(luò)。

所謂單跳網(wǎng)絡(luò)是指網(wǎng)絡(luò)中所有的節(jié)點(diǎn)都可以接收到其他節(jié)點(diǎn)發(fā)送的數(shù)據(jù)；

所謂兩跳網(wǎng)絡(luò)是指網(wǎng)絡(luò)中的部分節(jié)點(diǎn)之間不能直接通信，需要經(jīng)過一次中繼才能通信；

而所謂多跳網(wǎng)絡(luò)是指網(wǎng)絡(luò)中源節(jié)點(diǎn)和目的節(jié)點(diǎn)之間的通信可能要經(jīng)過多次中繼。多跳網(wǎng)絡(luò)既可以是有線網(wǎng)絡(luò)，也可以是無線網(wǎng)絡(luò)。

在無線通信網(wǎng)絡(luò)中，通信節(jié)點(diǎn)之間的有效通信距離是由發(fā)端的發(fā)送功率、節(jié)點(diǎn)之間的距離以及接收機(jī)靈敏度等條件決定的。

本章主要討論對稱的信道，即任意兩個在通信距離內(nèi)的節(jié)點(diǎn)都可以有效的和對方進(jìn)行通信。

２.同步特性。通常用戶是可以在任意時刻接入信道，但也可以以時隙為基礎(chǔ)接入信道。在基于時隙的系統(tǒng)中，用戶只有在時隙的起點(diǎn)才能接入信道。在這種系統(tǒng)中，要求全網(wǎng)有一個統(tǒng)一的時鐘，同時將時間軸劃分成若干個相等的時間段，稱之為時隙。系統(tǒng)中所有數(shù)據(jù)的傳輸開始點(diǎn)都必須在一個時隙的起點(diǎn)。

3.反饋和應(yīng)答機(jī)制。反饋信道是用戶獲得信道狀態(tài)的途徑。在本章的討論中，假設(shè)用戶（節(jié)點(diǎn)）可以獲得信道的反饋信息，即信道是空閑、碰撞還是進(jìn)行了一次成功傳輸。

4.數(shù)據(jù)產(chǎn)生模型。所有的用戶都按照泊松過程獨(dú)立地產(chǎn)生數(shù)據(jù)。

4.2 固定多址接入?yún)f(xié)議

固定多址接入?yún)f(xié)議又稱為無競爭的多址接入?yún)f(xié)議或靜態(tài)分配的多址接入?yún)f(xié)議。固定多址接入為每個用戶固定分配一定的系統(tǒng)資源，這樣當(dāng)用戶有數(shù)據(jù)發(fā)送時，就能不受干擾地獨(dú)享已分配的信道資源。固定多址接入的優(yōu)點(diǎn)在于可以保證每個用戶之間的“公平性”（每個用戶都分配了固定的資源）以及數(shù)據(jù)的平均時延。典型的固定多址接入?yún)f(xié)議有：頻分多址（ＦＤＭＡ）、時分多址（ＴＤＭＡ）、碼分多址（ＣＤＭＡ）及空分多址（ＳＤＭＡ）等。在本節(jié)中重點(diǎn)討論時分多址和頻分多址系統(tǒng)。

4.2.1 頻分多址接入(FDMA)

4.2.2 時分多址接入?yún)f(xié)議(TDMA)

4.2.3 固定多址接入?yún)f(xié)議的性能分析

Ｄ 的最小值是２。當(dāng)ｍ＝２ 時,TDMA 和FDMA的性能相同，兩曲線重合。ｍ值越大，兩者的差別就越大。

從上面的討論和分析可以看出，傳統(tǒng)的固定多址接入?yún)f(xié)議不能有效地處理用戶數(shù)量的可變性和通信業(yè)務(wù)的突發(fā)性，因此，將進(jìn)一步討論隨機(jī)接入的多址協(xié)議。

4.3 隨機(jī)多址接入技術(shù)

隨機(jī)多址協(xié)議又叫做有競爭的多址接入?yún)f(xié)議。網(wǎng)絡(luò)中的節(jié)點(diǎn)在網(wǎng)絡(luò)中的地位是等同的，各節(jié)點(diǎn)通過競爭獲得信道的使用權(quán)。隨機(jī)多址接入?yún)f(xié)議又可細(xì)分為完全隨機(jī)多址接入?yún)f(xié)議（ALOHA協(xié)議）和載波偵聽型多址接入?yún)f(xié)議。不論是哪種隨機(jī)多址接入?yún)f(xié)議，主要關(guān)心兩個方面的問題：一個是穩(wěn)態(tài)情況下系統(tǒng)的通過率和時延性能，另一個是系統(tǒng)的穩(wěn)定性。

4.3.1 ALOHA協(xié)議

為了分析隨機(jī)多址接入?yún)f(xié)議的性能，假設(shè)系統(tǒng)是由ｍ 個發(fā)送節(jié)點(diǎn)組成的單跳系統(tǒng)，信道是無差錯及無捕獲效應(yīng)的信道，分組的到達(dá)和傳輸過程滿足如下假定：
（１） 各個節(jié)點(diǎn)的到達(dá)過程為獨(dú)立的參數(shù)為λ/ｍ的Poisson到達(dá)過程，系統(tǒng)總的到達(dá)率為λ。
（2）在一個時隙或一個分組傳輸結(jié)束后，信道能夠立即給出當(dāng)前傳輸狀態(tài)的反饋信息。反饋信息為“０”表明當(dāng)前時隙或信道無分組傳輸，反饋信息為“１”
表明當(dāng)前時隙或信道僅有一個分組傳輸（即傳輸成功），反饋信息為“ｅ”表明當(dāng)前時隙或信道有多個分組在傳輸，即發(fā)生了碰撞，導(dǎo)致接收端無法正確接收。
（3）碰撞的節(jié)點(diǎn)將在后面的某一個時刻重傳被碰撞的分組，直至傳輸成功。
如果一個節(jié)點(diǎn)的分組必須重傳，則稱該節(jié)點(diǎn)為等待重傳的節(jié)點(diǎn)。
（4）對于節(jié)點(diǎn)的緩存和到達(dá)過程作如下假設(shè)：
假設(shè)Ａ：無緩存情況。在該情況下，每個節(jié)點(diǎn)最多容納一個分組。如果該節(jié)點(diǎn)有一個分組在等待傳輸或正在傳輸，則新到達(dá)的分組被丟棄且不會被傳輸。在該情況下，所求得的時延是有緩存情況下時延的下界（Low Bound）。

假設(shè)Ｂ：系統(tǒng)有無限個節(jié)點(diǎn)（$ｍ＝\infty$）。每個新產(chǎn)生的分組到達(dá)一個新的節(jié)點(diǎn)。這樣網(wǎng)絡(luò)中所有的分組都參與競爭，導(dǎo)致網(wǎng)絡(luò)的時延增加。因此，在該假設(shè)情況下求得的時延是有限節(jié)點(diǎn)情況下的時延上界（Up Bound）。

如果一個系統(tǒng)采用假設(shè)Ａ 或假設(shè)Ｂ 分析的結(jié)果類似，則采用這種分析方法就是對具有任意大小緩存系統(tǒng)性能的一個很好的近似。

1.純ALOHA協(xié)議

純ALOHA協(xié)議是最基本的ALOHA協(xié)議。只要有新的分組到達(dá)，就立即被發(fā)送并期望不與別的分組發(fā)生碰撞。一旦分組發(fā)生碰撞，則隨機(jī)退避一段時間后進(jìn)行重傳。

如果從數(shù)據(jù)分組開始發(fā)送的時間起點(diǎn)到其傳輸結(jié)束的這段時間內(nèi)，沒有其他數(shù)據(jù)分組發(fā)送，則該分組就不會和其他分組發(fā)生碰撞。如圖４－９所示， 在什么情況下圖中陰影部分表示的數(shù)據(jù)分組（在ｔ０＋ｔ時刻產(chǎn)生的分組）可以不受任何干擾的發(fā)送呢？

為了便于分析，假設(shè)系統(tǒng)中所有分組的長度相等，傳輸數(shù)據(jù)分組所需的時間定義為系統(tǒng)的單位時間，為了簡化描述，令該值等于ｔ，并在下面的分析中令其等于１）。從圖中可以看到，如果在t0 到t0+t時間內(nèi)，其他用戶產(chǎn)生了數(shù)據(jù)分組，則該分組的尾部就會和陰影分組的頭部碰撞；同樣，在t0+t 和t0+2t之間產(chǎn)生的任何分組都將和陰影分組的尾部發(fā)生碰撞。時間區(qū)間［ｔ０，ｔ０＋２ｔ］稱為陰影分組（在ｔ０＋ｔ時刻產(chǎn)生的分組）的易受破壞區(qū)間。

很顯然，在純ALOHA協(xié)議中，只有在數(shù)據(jù)分組的易受破壞區(qū)間內(nèi)沒有其他分組傳輸，則該分組可以成功傳輸。為了分析方便，設(shè)系統(tǒng)有無窮多個節(jié)點(diǎn)（假設(shè)Ｂ），假定重傳的時延足夠隨機(jī)，重傳分組和新到達(dá)分組合成的分組流是到達(dá)率為Ｇ的Poisson到達(dá)過程。則在純ALOHA系統(tǒng)中，一個分組成功傳輸?shù)母怕示褪窃谄洚a(chǎn)生時刻前一個時間單位內(nèi)沒有分組發(fā)送，并且在該分組產(chǎn)生時刻的后一個時間單位內(nèi)也沒有分組發(fā)送的概率，即在該分組產(chǎn)生時刻前后兩個時間單位內(nèi)沒有其他分組發(fā)送的概率。

2.時隙ALOHA協(xié)議

從前面的描述中可以看到，在純ＡＬＯＨＡ 協(xié)議中，節(jié)點(diǎn)只要有分組就發(fā)送，易受破壞區(qū)間為兩個單位時間。如果縮小易受破壞區(qū)間，就可以減少分組碰撞的概率，提高系統(tǒng)的利用率。基于這一出發(fā)點(diǎn)，提出了時隙ALOHA協(xié)議。

例題

分析：信道速率?通過率=所有終端發(fā)送速率之和 ，可以推出終端個數(shù)=信道速率?通過率/每個終端發(fā)送數(shù)據(jù)的速率。

平均傳輸時延和吞吐量的關(guān)系

4.3.2 載波偵聽多址協(xié)議(CSMA)

在前面討論的ＡＬＯＨＡ 協(xié)議中，網(wǎng)絡(luò)中的節(jié)點(diǎn)不考慮當(dāng)前信道是忙還是閑，一旦有分組到達(dá)就獨(dú)自決定將分組發(fā)送到信道。顯然這種控制策略存在盲目性。即使是稍有改進(jìn)的時隙ＡＬＯＨＡ協(xié)議，其最大吞吐率也只能達(dá)到約0.368。若要進(jìn)一步提高系統(tǒng)吞吐率，還應(yīng)進(jìn)一步設(shè)法減少節(jié)點(diǎn)間發(fā)送沖突的概率。為此，除了縮小易受破壞區(qū)間外（這也是有限度的），還可以從減少發(fā)送的盲目性著手，在發(fā)送之前先觀察信道是否有用戶在傳輸（或進(jìn)行“載波偵聽”）來確定信道忙閑狀態(tài)，然后再決定分組是否發(fā)送。這就是被廣泛采用的載波偵聽型多址接入?yún)f(xié)議CSMA(Carrier Sense Multiple Access)。

CSMA 是從ALOHA協(xié)議演變出的一種改進(jìn)型協(xié)議，它采用了附加的硬件裝置，每個節(jié)點(diǎn)都能夠檢測（偵聽）到信道上有無分組在傳輸。如果一個節(jié)點(diǎn)有分組要傳輸，它首先檢測信道是否空閑，如果信道有其他分組在傳輸，則該節(jié)點(diǎn)可以等到信道空閑后再傳輸，這樣可以減少要發(fā)送的分組與正在傳輸?shù)姆纸M之間的碰撞，提高系統(tǒng)的利用率。

1.非時隙CMSA多址協(xié)議

非時隙ＣＳＭＡ協(xié)議的工作過程如下：當(dāng)分組到達(dá)時，如果信道空閑，則立即發(fā)送該分組；如果信道忙，則分組被延遲一段時間后，重新檢測信道。如果信道忙或發(fā)送時與其他分組碰撞，則該分組變成等待重傳的分組。每個等待重傳的分組將重復(fù)地嘗試重傳，重傳間隔相互獨(dú)立且服從指數(shù)分布。

非堅(jiān)持型非時隙ＣＳＭＡ 多址協(xié)議的主要特點(diǎn)是在發(fā)送數(shù)據(jù)前先監(jiān)測信道，一旦監(jiān)測到信道忙時，能主動的退避一段時間（暫時放棄監(jiān)測信道）。

2.時隙CSMA多址協(xié)議

時隙ＣＳＭＡ協(xié)議把時間軸分成寬度為β的時隙（注意：時隙ＡＬＯＨＡ 中時隙的寬度為一個分組的長度，這里的時隙寬度為載波檢測時間）。如果分組到達(dá)一個空閑的時隙，它將在下一個空閑時隙開始傳輸［如圖（ａ）］。如果某節(jié)點(diǎn)的分組到達(dá)時，信道上有分組正在傳輸，則該節(jié)點(diǎn)變?yōu)榈却貍鞯墓?jié)點(diǎn)，它將在當(dāng)前分組傳輸結(jié)束后的后續(xù)空閑時隙中以概率$q_r$ 進(jìn)行傳輸。

從圖中可以看出，非堅(jiān)持型ＣＳＭＡ 協(xié)議可以大大減少碰撞的機(jī)會，使系統(tǒng)的最大吞吐量達(dá)到信道容量的80％ 以上，時隙非堅(jiān)持型ＣＳＭＡ協(xié)議的性能則更好。１－ 堅(jiān)持型ＣＳＭＡ 由于毫無退避措施，在業(yè)務(wù)量很小時，數(shù)據(jù)的發(fā)送機(jī)會較多，響應(yīng)也較快。但若節(jié)點(diǎn)數(shù)增大或總的業(yè)務(wù)量增加時，碰撞的機(jī)會急劇增加，系統(tǒng)的吞吐量特性急劇變壞，其最大吞吐量只能達(dá)到信道容量的５３％左右。但總的說來，ＣＳＭＡ 協(xié)議的性能優(yōu)于ＡＬＯＨＡ 協(xié)議的性能。

3.有碰撞檢測功能的載波偵聽多址協(xié)議(CSMA/CD)

前面討論的ＣＳＭＡ 協(xié)議由于在發(fā)送之前進(jìn)行載波監(jiān)聽，所以減少了沖突的機(jī)會。但由于傳播時延的存在，沖突還是不可避免的。只要發(fā)生沖突，信道就被浪費(fèi)一段時間。CSMA/CD 比CSMA又增加了一個功能，這就是邊發(fā)送邊監(jiān)聽。只要監(jiān)聽到信道上發(fā)生了沖突，則沖突的節(jié)點(diǎn)就必須停止發(fā)送。這樣，信道就很快空閑下來，因而提高了信道的利用率。這種邊發(fā)送邊監(jiān)聽的功能稱為沖突檢測。

總的來說，ＣＳＭＡ／ＣＤ接入?yún)f(xié)議比ＣＳＭＡ 多址接入?yún)f(xié)議的控制規(guī)則增加了如下三點(diǎn)：
（１）“邊說邊聽”———任一發(fā)送節(jié)點(diǎn)在發(fā)送數(shù)據(jù)幀期間要保持偵聽信道的碰撞情況。一旦檢測到碰撞發(fā)生，應(yīng)立即中止發(fā)送，而不管目前正在發(fā)送的幀是否發(fā)完。
（２）“強(qiáng)化干擾”———發(fā)送節(jié)點(diǎn)在檢測到碰撞并停止發(fā)送后，立即改為發(fā)送一小段“強(qiáng)化干擾信號”，以增強(qiáng)碰撞檢測效果。
（３）“碰撞檢測窗口”———任一發(fā)送節(jié)點(diǎn)若能完整的發(fā)完一個數(shù)據(jù)幀，則停頓一段時間（兩倍的最大傳播時延）并監(jiān)聽信道情況。若在此期間未發(fā)生碰撞，則可認(rèn)為該數(shù)據(jù)幀已經(jīng)發(fā)送成功。此時間區(qū)間即稱“碰撞檢測窗口”。

上述第（１）點(diǎn)保證盡快確知碰撞發(fā)生和盡早關(guān)閉碰撞發(fā)生后的無用發(fā)送，這有利于提高信道利用率；第（２）點(diǎn)可以提高網(wǎng)絡(luò)中所有節(jié)點(diǎn)對于碰撞檢測的可信度，保證了分布式控制的一致性；第（３）點(diǎn)有利于提高一個數(shù)據(jù)幀發(fā)送成功的可信度。如果接收節(jié)點(diǎn)在此窗口內(nèi)發(fā)送應(yīng)答幀（ACK 或NAK）的話，則可保證應(yīng)答傳輸成功。

4.有碰撞避免功能的載波偵聽多址協(xié)議(CSMA/CA)

CSMA/CA是有沖突避免（Collision Avoidance）的載波偵聽型多址接入?yún)f(xié)議。它是對CSMA的另一種改進(jìn)方法。通常在無線系統(tǒng)中，一臺無線設(shè)備不能在相同的頻率（信道）上同時進(jìn)行接收和發(fā)送，因而不能采用碰撞檢測（CD）技術(shù)。因此，只能通過沖突避免的方法來減少沖突的可能性。在IEEE802.11無線局域網(wǎng)（WLAN）的標(biāo)準(zhǔn)中，就采用了CSMA/CA協(xié)議。它不僅支持全連通的網(wǎng)絡(luò)拓?fù)?#xff0c;同時支持部分連通的網(wǎng)絡(luò)拓?fù)洹?/p>

IEEE802.11中CSMA/CA 的基本工作過程是：一個節(jié)點(diǎn)在發(fā)送數(shù)據(jù)幀之前先對信道進(jìn)行預(yù)約。假定Ａ 要向Ｂ 發(fā)送數(shù)據(jù)幀，發(fā)送節(jié)點(diǎn)Ａ先發(fā)送一個請求發(fā)送幀ＲＴＳ（Request To Send）來預(yù)約信道，所有收到ＲＴＳ 幀的節(jié)將暫緩發(fā)送。而真正的接收節(jié)點(diǎn)Ｂ 在收到ＲＴＳ 后，發(fā)送一個允許發(fā)送的應(yīng)答幀ＣＴＳ（Clear To Send）。在ＲＴＳ和ＣＴＳ幀中均包括要發(fā)送分組的長度（在給定信道傳輸速率及ＲＴＳ和ＣＴＳ長度的情況下，各節(jié)點(diǎn)就可以計(jì)算出相應(yīng)的退避時間，該時間通常稱為ＮＡＶ（Network Allocation Vector））。

CTS幀有兩個作用：一是表明接收節(jié)點(diǎn)Ｂ 可以接收發(fā)送節(jié)點(diǎn)Ａ 的幀，二是禁止Ｂ 的鄰節(jié)點(diǎn)發(fā)送，從而避免了Ｂ的鄰節(jié)點(diǎn)的發(fā)送對Ａ 到Ｂ的數(shù)據(jù)傳輸?shù)挠绊憽TS和CTS幀很短，如它們分別可為２０和１４ 個字節(jié)。而數(shù)據(jù)幀最長可以達(dá)到２３４６字節(jié)。相比之下，RTS和CTS引入的開銷不大。RTS/CTS的傳輸過程如圖4-20所示。

4.4 沖突分解算法

對于有競爭的多址接入?yún)f(xié)議如何解決沖突從而使所有碰撞用戶都可以成功傳輸是一個非常重要的問題。從前面的討論可以看出，通過調(diào)整對等待重傳隊(duì)列長度的估值，改變重傳概率，可以進(jìn)一步減緩碰撞。而另一種更有效的解決沖突的方式就是沖突分解（Collision Resulution）。

沖突分解的基本思想是：如果系統(tǒng)發(fā)生碰撞，則讓新到達(dá)的分組在系統(tǒng)外等待，在參與碰撞的分組均成功傳輸結(jié)束后，再讓新分組傳輸。

下面針對ＡＬＯＨＡ協(xié)議進(jìn)行討論，以兩個分組碰撞的情況來簡要說明沖突分解的過程和好處。

一旦一個分組成功傳輸，則另一個分組在下一時隙必然成功傳輸，所以平均需要３個時隙才能成功發(fā)送２個分組。因而在沖突分解的過程中，通過率為2/3.

4.4.1 樹形分裂算法

假設(shè)在第ｋ個時隙發(fā)生碰撞，碰撞節(jié)點(diǎn)的集合為Ｓ。所有未介入碰撞的節(jié)點(diǎn)進(jìn)入等待狀態(tài)。Ｓ被隨機(jī)地分成兩個子集，用左集（Ｌ）和右集（Ｒ）表示。左集（Ｌ）先在第ｋ＋１時隙中傳輸。如果第ｋ＋１時隙中傳輸成功或空閑，則Ｒ在第ｋ＋２個時隙中傳輸。如果在第ｋ＋１ 時隙中發(fā)生碰撞，則將Ｌ 再分為左集（ＬＬ）和右集（ＬＲ），ＬＬ在第ｋ＋２個時隙中傳輸。如果第ｋ＋２ 時隙中傳輸成功或空閑，則ＬＲ在第ｋ＋３個時隙中傳輸。以此類推，直至集合Ｓ中所有的分組傳輸成功。從碰撞的時隙（第ｋ個時隙）開始，直至Ｓ集合中所有分組成功傳輸結(jié)束的時隙稱為一個沖突分解期（ＣＲＰ）。

該圖中用了８個時隙完成了沖突分解。該算法中，在給定每個時隙結(jié)束時立即有（０，１，ｅ）反饋信息的情況下，各個節(jié)點(diǎn)能構(gòu)造一個相同的樹，并確定自己所處的子集和確定何時發(fā)送自己的分組。

具體的方法如下：樹形算法中的發(fā)送順序可對應(yīng)于一個數(shù)據(jù)壓入堆棧的順序。當(dāng)一個碰撞發(fā)生后，碰撞節(jié)點(diǎn)的集合被分為子集，形成的每一個子集作為一個元素壓入堆棧。在發(fā)送時，堆棧最頂端的子集從堆棧中移出并進(jìn)行發(fā)送。每個節(jié)點(diǎn)采用一個計(jì)數(shù)器來跟蹤它的分組所在的當(dāng)前子集處于堆棧中的位置。如果該子集處于堆棧的頂端，則立即發(fā)送。當(dāng)該節(jié)點(diǎn)的分組傳輸發(fā)生碰撞（沖突分解開始），計(jì)數(shù)器的初值置０或１（取決于該分組被放在哪個子集中，顯然如果該分組被放入左子集，則初值被置為０；而如果該分組被放入右子集，則初值置為１）。在沖突分解過程中，當(dāng)計(jì)數(shù)器的值為０時，則發(fā)送該分組。如果計(jì)數(shù)器為非０，則在沖突分解過程中，每次時隙發(fā)生碰撞，計(jì)數(shù)器值加１，每次成功傳輸或時隙空閑，計(jì)數(shù)器值減１。

在沖突分解期（ＣＲＰ）中，處理的分組是介入碰撞的分組。而在ＣＲＰ 中，還會不停地有新分組到達(dá)。對于ＣＲＰ中新到達(dá)的分組有兩種處理方法。方法一是在當(dāng)前ＣＲＰ結(jié)束后立即開始一個新的ＣＲＰ，該新ＣＲＰ所處理的分組就是當(dāng)前ＣＲＰ中到達(dá)的新分組。這種方法的問題是，如果當(dāng)前ＣＲＰ到達(dá)了很多分組，則在新的ＣＲＰ 中，可能要碰撞很長時間才能通過分解得到一個很小的子集。方法二是在當(dāng)前ＣＲＰ 結(jié)束時刻，立即將到達(dá)的分組分為ｊ個子集（ｊ的選擇應(yīng)使每個子集中的分組數(shù)稍大于１），然后對每一個子集進(jìn)行沖突分解。該方法的最大通過率可以達(dá)到每個時隙０．４３個分組。

通過仔細(xì)觀察樹形算法，可以發(fā)現(xiàn)，如果在一次碰撞（如第ｋ個時隙）以后，下一個時隙（第ｋ＋１時隙）是空閑的，則第ｋ＋２ 個時隙必然會再次發(fā)生碰撞。這表明將碰撞節(jié)點(diǎn)集合中的所有節(jié)點(diǎn)都分配到了右集（Ｒ），自然會再次發(fā)生碰撞。改進(jìn)的方法是：當(dāng)碰撞后出現(xiàn)空閑時隙，則不傳送第二個子集（Ｒ）中的分組，而是立即將Ｒ 再次分解，然后再傳輸分解后的第一個子集（ＲＬ），如果再次空閑，則再次進(jìn)行分解，然后傳送ＲＬＬ集合中的分組，以此類推。通過這樣的改進(jìn)可以使每個時隙的最大通過率達(dá)到０．４６個分組。

4.4.2 先到先服務(wù)(FCFS)分裂算法

4.4 預(yù)約多址接入技術(shù)

4.5 本章課后習(xí)題

４．１　請討論固定多址接入?yún)f(xié)議的優(yōu)缺點(diǎn)是什么？

４．２　在ＡＬＯＨＡ協(xié)議中，為什么會出現(xiàn)穩(wěn)定平衡點(diǎn)和不穩(wěn)定的平衡點(diǎn)，重傳概率對系統(tǒng)的性能有何影響？
４．３　設(shè)信道數(shù)據(jù)速率為９６００ｂｉｔ／ｓ，分組長度為８０４ｂｉｔ。計(jì)算當(dāng)Ｇ＝０．７５時純ＡＬＯＨＡ 系統(tǒng)負(fù)荷為多少。

４．４　ｎ個節(jié)點(diǎn)共享一個９６００ｂｉｔ／ｓ的信道，每個節(jié)點(diǎn)以每１００ｓ產(chǎn)生一個１０００ｂｉｔ 分組的平均速率發(fā)送數(shù)據(jù)分組。試求在純ＡＬＯＨＡ 系統(tǒng)和時隙ＡＬＯＨＡ系統(tǒng)中最大可容許的系統(tǒng)用戶數(shù)Ｎ 的值。

４．５　什么叫穩(wěn)定的多址接入?yún)f(xié)議？使用偽貝葉斯算法的時隙ＡＬＯＨＡ協(xié)議是不是穩(wěn)定的多址接入?yún)f(xié)議？如果是，其穩(wěn)定的最大通過率是多少？

４．６　ＣＳＭＡ協(xié)議的基本原理是什么？與ＡＬＯＨＡ 系統(tǒng)相比，為什么ＣＳＭＡ系統(tǒng)有可能獲得更高的系統(tǒng)吞吐率？

4．７　ＣＳＭＡ系統(tǒng)主要是在什么問題的處理決策上去區(qū)分三種不同類型的ＣＳＭＡ 協(xié)議？說明它們各自的關(guān)鍵技術(shù)特點(diǎn)。
4.7 答：CSMA 系統(tǒng)主要在分組到達(dá)時若信道忙，是否持續(xù)偵聽信道及在獲得空閑信道后怎樣發(fā)送分組的處理上區(qū)分三種不同的CSMA 協(xié)議的，也即對沖突問題的處理決策上來區(qū)分的。
三種形式：
非堅(jiān)持型CSMA ：當(dāng)分組到達(dá)時，若信道空閑，則立即發(fā)送分組；若信道處于忙狀態(tài)，則分組的發(fā)送將被延遲，且節(jié)點(diǎn)不再跟蹤信道的狀態(tài)（即節(jié)點(diǎn)暫時不檢測信道），延遲結(jié)束后節(jié)點(diǎn)再次檢測信道狀態(tài)，并重復(fù)上述過程，如此循環(huán)，直到將該分組發(fā)送成功為止。

1-堅(jiān)持型CSMA ：當(dāng)分組到達(dá)時，若信道空閑，則立即發(fā)送分組；若信道處于忙狀態(tài)，則該節(jié)點(diǎn)一直堅(jiān)持檢測信道狀態(tài)，直至檢測到信道空閑后，立即發(fā)送該分組。

p-堅(jiān)持型CSMA ：當(dāng)分組到達(dá)時，若信道空閑，則立即發(fā)送分組；若信道處于忙狀態(tài)，則該節(jié)點(diǎn)一直檢測信道的狀態(tài)，在檢測到信道空閑后，以概率p 發(fā)送該分組。
４．８　ＣＳＭＡ方法有什么應(yīng)用環(huán)境限制？在衛(wèi)星信道上能采用ＣＳＭＡ 接入方法嗎？為什么？

４．９　假設(shè)有以下兩個ＣＳＭＡ／ＣＤ網(wǎng)：
網(wǎng)絡(luò)Ａ是ＬＡＮ（局域網(wǎng)），傳送速率為５Ｍｂｉｔ／ｓ，電纜長１ｋｍ，分組長度１０００ｂｉｔ；
網(wǎng)絡(luò)Ｂ是ＭＡＮ（城域網(wǎng)），電纜長５０ｋｍ，分組長度１０００ｂｉｔ。
那么，網(wǎng)絡(luò)Ｂ需要多大的傳送速率才能達(dá)到與網(wǎng)絡(luò)Ａ 相同的吞吐量？

４．１０　Ｋ 個節(jié)點(diǎn)共享１０Ｍｂｉｔ／ｓ的總線電纜，用ＣＳＭＡ／ＣＤ作為訪問方案（即以太網(wǎng)ＬＡＮ）。總線長５００ｍ，分組長Ｌ 比特，假設(shè)網(wǎng)絡(luò)上的Ｋ個節(jié)點(diǎn)總有業(yè)務(wù)準(zhǔn)備傳送（重負(fù)荷情況）。Ｐ是競爭時隙中一個節(jié)點(diǎn)發(fā)送分組的概率。令Ｋ＝１０，傳播速度是３×１０８ ｍ／ｓ。求競爭周期的平均時隙數(shù)、競爭周期的平均持續(xù)時間及以下兩種情況的信道利用率。
（１） Ｌ＝１００ｂｉｔ。
（２） Ｌ＝１０００ｂｉｔ。
４．１１　試給出圖４－２６所示網(wǎng)絡(luò)中的無沖突矢量集合。

總結(jié)

以上是生活随笔為你收集整理的通信网络基础期末复习-第四章-多址接入协议的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。