ch8_多址接入150529-zhl

1、多址接入網(wǎng)絡性能分析多址接入網(wǎng)絡性能分析 主要內容n多址接入?yún)f(xié)議概述n隨機多址接入?yún)f(xié)議n載波偵聽型多址協(xié)議主要內容n多址接入?yún)f(xié)議概述n隨機多址接入?yún)f(xié)議n載波偵聽型多址協(xié)議多址接入?yún)f(xié)議概述（1）n網(wǎng)絡中的終端設備通過通信子網(wǎng)來訪問網(wǎng)絡中的資源。當多個終端同時訪問同一資源（如共享的通信信道）時，就可能會產(chǎn)生信息碰撞，導致通信失敗。典型的共享鏈路有：衛(wèi)星鏈路和蜂窩移動通信系統(tǒng)的鏈路、局域網(wǎng)、分組無線電網(wǎng)等多址接入?yún)f(xié)議概述（2）n為了有效的進行通信，就需要有某種機制來決定資源的使用權，這就是網(wǎng)絡的多址接入控制問題。n所謂多址接入?yún)f(xié)議（Multiple Access Protocol）就是在一個網(wǎng)絡中，

2、解決多個用戶如何高效共享一個物理鏈路資源的技術。n多址協(xié)議應盡量避免用戶之間的碰撞，并使信道利用率最高。多址接入?yún)f(xié)議概述（3）n從分層的角度來看，多址技術是數(shù)據(jù)鏈路層的一個子層，一般稱為介質訪問控制子層MAC層。該層用于在各種通信節(jié)點中分配多路訪問介質，仲裁介質的使用權，即規(guī)定站點何時可以使用通信介質 。nMAC層將有限的資源分配給多個用戶，從而使得在眾多用戶之間實現(xiàn)公平、有效地共享有限的帶寬資源；實現(xiàn)各用戶之間良好的連通性，獲得盡可能高的系統(tǒng)吞吐量、以及盡可能低的系統(tǒng)時延。多址協(xié)議的分類（1）n固定分配多址接入?yún)f(xié)議：是指在用戶接入信道時，專門為其分配一定的信道資源（如頻率、時隙、碼字或空間）

3、，用戶獨享該資源，直到通信結束。n隨機分配多址接入?yún)f(xié)議：是指用戶可以隨時接入信道，隨機分配多址接入?yún)f(xié)議：是指用戶可以隨時接入信道，并且可能不會顧及其它用戶是否在傳輸。當信道中同時并且可能不會顧及其它用戶是否在傳輸。當信道中同時有多個用戶接入時，在信道資源的使用上就會發(fā)生沖突有多個用戶接入時，在信道資源的使用上就會發(fā)生沖突（碰撞）。因此，對于有競爭的多址接入?yún)f(xié)議如何解決（碰撞）。因此，對于有競爭的多址接入?yún)f(xié)議如何解決沖突從而使所有碰撞用戶都可以成功進行傳輸是一個非沖突從而使所有碰撞用戶都可以成功進行傳輸是一個非常重要的問題。常重要的問題。n基于預約方式的多址接入?yún)f(xié)議：是指在數(shù)據(jù)分組傳輸之前，先進

4、行資源預約。一旦預約到資源（如頻率、時隙），則在該資源內可進行無沖突的傳輸。多址協(xié)議的分類（2）多址接入?yún)f(xié)議系統(tǒng)模型（1）n從排隊論的觀點出發(fā)，多址信道可以看成一個多進單出的排隊系統(tǒng)（即該系統(tǒng)有多個輸入而僅僅有一個輸出）。n每一個節(jié)點都可以獨立的產(chǎn)生分組，而信道則相當于服務員，它要為各個隊列服務。由于各個排隊隊列是相互獨立的，各節(jié)點無法知道其它隊列的情況，服務員也不知道各個隊列的情況，所以增加了系統(tǒng)的復雜性。n如果我們可以通過某種措施，使各個節(jié)點產(chǎn)生的分組在進入信道之前排列成一個總的隊列，然后由信道來服務，則可以有效的避免分組在信道上的碰撞，大大提高信道的利用率。多址接入?yún)f(xié)議系統(tǒng)模型（2）多址

5、接入?yún)f(xié)議系統(tǒng)模型（3）n用戶到達是隨機的n目標：協(xié)調用戶的傳輸，有效地使用信道多址接入?yún)f(xié)議系統(tǒng)模型（4）：n同步特性。通常用戶是可以在任意時刻接入信道，但也可以以時隙為基礎接入信道。在基于時隙的系統(tǒng)中，用戶只有在時隙的起點才能接入信道。在這種系統(tǒng)中，要求全網(wǎng)有一個統(tǒng)一的時鐘，同時將時間軸劃分成若干個相等的時間段，稱之為時隙。系統(tǒng)中所有數(shù)據(jù)的傳輸開始點都必須在一個時隙的起點。n反饋和應答機制，是用戶獲得信道狀態(tài)的途徑。這里都假設用戶（節(jié)點）可以獲得信道的反饋信息，即信道是空閑、碰撞還是進行了一次成功傳輸。n數(shù)據(jù)產(chǎn)生模型。所有的用戶都按照泊松過程獨立地產(chǎn)生數(shù)據(jù)。主要內容n多址接入?yún)f(xié)議概述n隨機多址

6、接入?yún)f(xié)議n載波偵聽型多址協(xié)議隨機多址接入?yún)f(xié)議n隨機多址協(xié)議又叫做有競爭的多址接入?yún)f(xié)議。網(wǎng)絡中的節(jié)點在網(wǎng)絡中的地位是等同的，各節(jié)點通過競爭獲得信道的使用權。n隨機多址接入?yún)f(xié)議又可細分為完全隨機多址接入?yún)f(xié)議（ALOHA協(xié)議）和載波偵聽型多址接入?yún)f(xié)議。性能分析性能分析主要關心：一個是穩(wěn)態(tài)情況下系統(tǒng)的通過率和時延性能，主要關心：一個是穩(wěn)態(tài)情況下系統(tǒng)的通過率和時延性能，另一個是系統(tǒng)的穩(wěn)定性。另一個是系統(tǒng)的穩(wěn)定性。ALOHA協(xié)議(1)nALOHA協(xié)議是70年代Hawaii大學建立的在多個數(shù)據(jù)終端到計算中心之間的通信網(wǎng)絡中使用的協(xié)議。其基本思想是：若一個空閑的節(jié)點有一個分組到達，則立即發(fā)送該分組，并期望不會

7、和其它節(jié)點發(fā)生碰撞。n為了分析隨機多址接入?yún)f(xié)議的性能，假設系統(tǒng)是由m個發(fā)送節(jié)點組成的單跳系統(tǒng)，信道是無差錯及無捕獲效應的信道，分組的到達和傳輸過程滿足如下假定：1.各個節(jié)點的到達過程為獨立的、參數(shù)為/m的Poisson到達過程，系統(tǒng)總的到達率為。ALOHA協(xié)議(2)2.在一個時隙或一個分組傳輸結束后，信道能夠立即給出當前傳輸狀態(tài)的反饋信息。反饋信息為“0”表明當前時隙或信道無分組傳輸，反饋信息為“1”表明當前時隙或信道僅有一個分組傳輸（即傳輸成功），反饋信息為“e”表明當前時隙或信道有多個分組在傳輸，即發(fā)生了碰撞，導致接收端無法正確接收。3. 碰撞的節(jié)點將在后面的某一個時刻重傳被碰撞的分組，直

8、至傳輸成功。如果一個節(jié)點的分組必須重傳，則稱該節(jié)點為等待重傳的節(jié)點。ALOHA協(xié)議(3)純ALOHA中，幀傳輸完全是在任意時間進行的ALOHA協(xié)議(4)4.對于節(jié)點的緩存和到達過程作如下假設:n假設A：無緩存情況。在該情況下，每個節(jié)點最多容納一個分組。如果該節(jié)點有一個分組在等待傳輸或正在傳輸，則新到達的分組被丟棄且不會被傳輸。在該情況下，所求得的時延是有緩存情況下時延的下界（Low Bound）。n假設B： 系統(tǒng)有無限個節(jié)點 （m= ）。 每個新產(chǎn)生的分組到達一個新的節(jié)點。這樣網(wǎng)絡中所有的分組都參與競爭，導致網(wǎng)絡的時延增加。因此，在該假設情況下求得的時延是有限節(jié)點情況下的時延上界 （Up Bo

9、und）。純ALOHA協(xié)議(1)純ALOHA協(xié)議是最基本的ALOHA協(xié)議。只要有新的分組到達，就立即被發(fā)送并期望不與別的分組發(fā)生碰撞。一旦分組發(fā)生碰撞，則隨機退避一段時間后進行重傳。純ALOHA協(xié)議(2)n如果從數(shù)據(jù)分組開始發(fā)送的時間起點到其傳輸結束的這段時間內，沒有其它數(shù)據(jù)分組發(fā)送，則該分組就不會和其它分組發(fā)送碰撞。n在什么情況時圖中陰影部分表示的數(shù)據(jù)分組（在t0+t時刻產(chǎn)生的分組）可以不受任何干擾的發(fā)送呢？ n為了便于分析，假設系統(tǒng)中所有分組的長度相等，傳輸數(shù)據(jù)分組所需的時間定義為系統(tǒng)的單位時間，為了簡化描述，令該值等于t，并在下面的分析中令其等于1。純ALOHA協(xié)議(3)n將時間區(qū)間t0

10、 , t0 + 2t稱為陰影分組（在t0 + t時刻產(chǎn)生的分組）的易受破壞區(qū)間。n 很顯然，在純ALOHA協(xié)議中，只有在數(shù)據(jù)分組的易受破壞區(qū)間內沒有其它分組傳輸，則該分組可以成功傳輸。n為了分析方便，設系統(tǒng)有無窮多個節(jié)點（假設B），假定重傳的時延足夠隨機，重傳分組和新到達分組合成的分組流是到達率為G的Poisson到達過程。則在純ALOHA系統(tǒng)中，一個分組成功傳輸?shù)母怕?，就是在其產(chǎn)生時刻前一個時間單位內沒有分組發(fā)送，并且在該分組產(chǎn)生時刻的后一個時間單位內僅有一個分組發(fā)送的概率純ALOHA協(xié)議(4)n根據(jù)泊松公式，在單位時間內，產(chǎn)生k個分組的概率是n 則根據(jù)上面的分析，可以得到在純ALOHA系統(tǒng)

11、中，分組成功傳輸?shù)母怕始傾LOHA協(xié)議(5)n在單位時間的意義上，系統(tǒng)分組成功發(fā)送的概率即為系統(tǒng)的通過率n 對上式求最大值，可得系統(tǒng)的最大通過率為n 對應的G = 0.5純ALOHA協(xié)議(6)n純ALOHA（P-ALOHA）是一種完全隨機的多址方式，全網(wǎng)不需要定時和同步，各站發(fā)射時間是完全隨機的。n當終端數(shù)目不多時，系統(tǒng)能夠很好地工作，并具有一定的抗干擾能力。n而當終端數(shù)目很多，傳輸業(yè)務繁忙時，發(fā)生碰撞的概率增大，信道的傳輸效率就降低，最高只能達到18.4，且存在潛在不穩(wěn)定性。 時隙ALOHA協(xié)議(1)n從前面的描述中可以看到，在純ALOHA協(xié)議中，節(jié)點只要有分組就發(fā)送，易受破壞區(qū)間為兩個單位

12、時間。如果縮小易受破壞區(qū)間，就可以減少分組碰撞的概率，提高系統(tǒng)的利用率?；谶@一出發(fā)點，提出了時隙時隙ALOHA協(xié)議：協(xié)議：n時隙ALOHA系統(tǒng)將時間軸劃分為若干個時隙，所有節(jié)點同步，各節(jié)點只能在時隙的開始時刻才能夠發(fā)送分組，時隙寬度等于一個分組的傳輸時間，當一個分組到達某時隙后，它將在下一時隙開始傳輸，并期望不會與其它節(jié)點發(fā)生碰撞。如果在某時隙內，僅有一個分組到達（包括新到達的分組和重傳分組的到達），則該分組會傳輸成功。如果在某時隙內到達兩個或兩個以上的分組，則將會發(fā)生碰撞。碰撞的分組將在以后的時隙中重傳。很顯然，此時的易受破壞區(qū)間長度減少為一個單位時間（時隙）。時隙ALOHA協(xié)議(2) 利

13、用前面的假設條件，并假定系統(tǒng)有無窮多個節(jié)點利用前面的假設條件，并假定系統(tǒng)有無窮多個節(jié)點(假假設設B)。 從圖中可以看出在一個時隙內到達的分組包括兩個部分：從圖中可以看出在一個時隙內到達的分組包括兩個部分：一部分是新到達的分組，另一部分是重傳的分組。設新到一部分是新到達的分組，另一部分是重傳的分組。設新到達的分組是到達率為達的分組是到達率為(分組數(shù)分組數(shù)/時隙時隙)的的Poisson過程。假過程。假定重傳的時延足夠隨機化，這樣就可以近似地認為重傳分定重傳的時延足夠隨機化，這樣就可以近似地認為重傳分組的到達過程和新分組的到達過程之和是到達率為組的到達過程和新分組的到達過程之和是到達率為G( )的的

14、Poisson過程。過程。時隙ALOHA協(xié)議(3)ALOHA協(xié)議的通過率曲線時隙ALOHA協(xié)議(4)n若干個終端用純ALOHA隨機接入?yún)f(xié)議與遠端主機通信。信道速率為2.4kb/s。每個終端平均每3分鐘發(fā)送一個幀，幀長為200bit，問系統(tǒng)中最多可容納多少個終端？若采用時隙ALOHA協(xié)議，其結果又如何？時隙ALOHA協(xié)議穩(wěn)定性分析(1)時隙ALOHA協(xié)議穩(wěn)定性分析(2)時隙ALOHA協(xié)議穩(wěn)定性分析(3)n為了分析系統(tǒng)的動態(tài)行為，先采用假設A（無緩存的情況）來進行討論。時隙ALOHA的行為可以用離散時間馬爾可夫鏈來描述，其系統(tǒng)的狀態(tài)為每個時隙開始時刻等待重傳的節(jié)點數(shù)。時隙ALOHA協(xié)議穩(wěn)定性分析(

15、4)時隙ALOHA協(xié)議穩(wěn)定性分析(5)時隙ALOHA協(xié)議穩(wěn)定性分析(6)時隙ALOHA協(xié)議穩(wěn)定性分析(7)時隙ALOHA協(xié)議穩(wěn)定性分析(8)時隙ALOHA協(xié)議穩(wěn)定性分析(9)時隙ALOHA協(xié)議穩(wěn)定性分析(10)時隙ALOHA協(xié)議穩(wěn)定性分析(11)主要內容n多址接入?yún)f(xié)議概述n隨機多址接入?yún)f(xié)議n載波偵聽型多址協(xié)議載波載波偵聽型多址協(xié)議(1)nCSMA是從ALOHA協(xié)議演變出的一種改進型協(xié)議，它采用了附加的硬件裝置，每個節(jié)點都能夠檢測（偵聽）到信道上有無分組在傳輸。如果一個節(jié)點有分組要傳輸，它首先檢測信道是否空閑，如果信道有其他分組在傳輸，則該節(jié)點可以等到信道空閑后再傳輸，這樣可以減少要發(fā)送的分組與

16、正在傳輸?shù)姆纸M之間的碰撞，提高系統(tǒng)的利用率。nCSMA協(xié)議可細分為幾種不同的實現(xiàn)形式：n非堅持型（Non-persistent）CSMAn1-堅持型CSMAn p-堅持型CSMA載波載波偵聽型多址協(xié)議(2)n非堅持型CSMA：指當分組到達時，若信道空閑，則立即發(fā)送分組；若信道處于忙狀態(tài)，則分組的發(fā)送將被延遲，且節(jié)點不再跟蹤信道的狀態(tài)（即節(jié)點暫時不檢測信道），延遲結束后節(jié)點再次檢測信道狀態(tài)，并重復上述過程，如此循環(huán)，直到將該分組發(fā)送成功為止n1-堅持型CSMA：指當分組到達時，若信道空閑，則立即發(fā)送分組；若信道處于忙狀態(tài)，則該節(jié)點一直堅持檢測信道狀態(tài)，直至檢測到信道空閑后，立即發(fā)送該分組。n p

17、-堅持型CSMA：指當分組到達時，若信道空閑，則立即發(fā)送分組；若信道處于忙狀態(tài)，則該節(jié)點一直檢測信道的狀態(tài)，在檢測到信道空閑后，以概率p發(fā)送該分組非時隙CSMA多址協(xié)議（1）n非時隙CSMA協(xié)議的工作過程如下：當分組到達時，如果信道空閑，則立即發(fā)送該分組；如果信道忙，則分組被延遲一段時間后，重新檢測信道。n如果信道忙或發(fā)送時與其它分組碰撞，則該分組變成等待重傳的分組。每個等待重傳的分組將重復地嘗試重傳，重傳間隔相互獨立且服從指數(shù)分布。其具體的控制算法描述如下：1.若有分組等待發(fā)送，則轉到第2步，否則處于空閑狀態(tài)，等待分組到達。2.監(jiān)測信道：若信道空閑，啟動發(fā)送分組，發(fā)完返回第1步；若信道忙，放

18、棄監(jiān)測信道，選擇一個隨機時延的時間長度t開始延時（此時節(jié)點處于退避狀態(tài)）。3.延時結束，轉至第1步。非時隙CSMA多址協(xié)議（2）時隙CSMA多址協(xié)議（1）n時隙CSMA協(xié)議把時間軸分成寬度為的時隙（注意：時隙ALOHA中時隙的寬度為一個分組的長度，這里的時隙寬度為載波檢測時間）。如果分組到達一個空閑的時隙，它將在下一個空閑時隙開始傳輸時隙CSMA多址協(xié)議（2）n如果某節(jié)點的分組到達時，信道上有分組正在傳輸，則該節(jié)點變?yōu)榈却貍鞯墓?jié)點，它將在當前分組傳輸結束后的后續(xù)空閑時隙中以概率qr進行傳輸時隙CSMA多址協(xié)議（3）n我們可以用馬爾可夫鏈來分析時隙CSMA協(xié)議的性能。設分組長度為1個單位長度，

19、其總的到達過程是速率為的Poisson到達過程，網(wǎng)絡中有無窮多個節(jié)點（假設B）。信道狀態(tài)0、1、e的反饋時延最大為。又設系統(tǒng)的狀態(tài)為每一個空閑時隙結束時刻等待重傳的分組數(shù)n，則相繼兩個狀態(tài)轉移的時間間隔為或1CSMA/CAnCSMA/CA是有沖突避免（Collision Avoidance）的載波偵聽型多址接入?yún)f(xié)議。它是對CSMA的另一種改進方法。通常在無線系統(tǒng)中，一臺無線設備不能在相同的頻率（信道）上同時進行接收和發(fā)送，因而不能采用碰撞檢測（CD）技術。因此，只能通過沖突避免的方法來減少沖突的可能性。n在IEEE802.11無線局域網(wǎng)（WLAN）的標準中，就采用了CSMA/CA協(xié)議。它不僅支持全連通的網(wǎng)絡拓撲，同時支持部分連通的網(wǎng)絡拓撲。時隙 CSMA 協(xié)議定義在一個狀態(tài)轉移間隔內n的平均變化數(shù)為 Dn = E狀態(tài)轉移間隔內到達的分組數(shù)-Psucc =E狀態(tài)轉移間隔-Psucc 這里 E狀態(tài)轉移間隔 =P(時隙空閑)+(1+)（1-P(時隙空閑)）=+1 - P(時隙空閑)=+1- e-(1-qr)