第二講-數(shù)據(jù)鏈路層課件

MAC協(xié)議

無線網絡需要克服的問題無線局域網MAC協(xié)議無線傳感網絡MAC協(xié)議內容提要1.數(shù)據(jù)鏈路層概述2.MAC協(xié)議CSMA IEEE802.11MAC協(xié)議 S-MAC協(xié)議數(shù)據(jù)鏈路層介紹數(shù)據(jù)鏈路層在五層結構中的位置 √MAC在協(xié)議結構中的重要性（52頁第二段）數(shù)據(jù)鏈路層的基本概念下一張PPT √數(shù)據(jù)鏈路層的簡單模型 如下圖所示數(shù)據(jù)鏈路層基本概念數(shù)據(jù)鏈路(datalink)除了物理線路外，還必須有通信協(xié)議來控制這些數(shù)據(jù)的傳輸。把實現(xiàn)這些協(xié)議的硬件和軟件加到鏈路上，就構成了數(shù)據(jù)鏈路。數(shù)據(jù)鏈路層的主要功能(1)鏈路管理 √(2)幀定界(3)流量控制(4)差錯控制 √(5)將數(shù)據(jù)和控制信息區(qū)分開(6)透明傳輸(7)尋址鏈路管理：當網絡中的兩個結點要進行通信時，數(shù)據(jù)的發(fā)方必須確知收方是否已經處在準備接收的狀態(tài)。數(shù)據(jù)鏈路的建立、維持和釋放就叫做鏈路管理。信道分割方法，如后數(shù)據(jù)鏈路層基本概念信道的分割方法信道分割,按時間,頻率或編碼時分、碼分、頻分隨機分割(動態(tài))ALOHA,S-ALOHA,CSMA輪轉分割從主結點發(fā)出輪詢,令牌傳遞（tokenpassing）數(shù)據(jù)鏈路層介紹數(shù)據(jù)鏈路層在五層結構中的位置 數(shù)據(jù)鏈路層的基本概念下一張PPT 數(shù)據(jù)鏈路層的簡單模型 √如下圖所示局域網廣域網主機

H1主機

H2路由器

R1路由器

R2路由器

R3電話網局域網主機

H1

向

H2

發(fā)送數(shù)據(jù)鏈路層應用層運輸層網絡層物理層鏈路層應用層運輸層網絡層物理層鏈路層網絡層物理層鏈路層網絡層物理層鏈路層網絡層物理層R1R2R3H1H2從層次上來看數(shù)據(jù)的流動數(shù)據(jù)鏈路層的簡單模型數(shù)據(jù)鏈路層的簡單模型(續(xù)）局域網廣域網主機

H1主機

H2路由器

R1路由器

R2路由器

R3電話網局域網主機

H1

向

H2

發(fā)送數(shù)據(jù)鏈路層應用層運輸層網絡層物理層鏈路層應用層運輸層網絡層物理層鏈路層網絡層物理層鏈路層網絡層物理層鏈路層網絡層物理層R1R2R3H1H2僅從數(shù)據(jù)鏈路層觀察幀的流動下面介紹數(shù)據(jù)鏈路層的差錯控制傳輸差錯產生過程差錯檢測在傳輸過程中可能會產生比特差錯：1可能會變成0而0也可能變成1。在一段時間內，傳輸錯誤的比特占所傳輸比特總數(shù)的比率稱為誤碼率

BER(BitErrorRate)。誤碼率與信噪比有很大的關系（正比關系）。為了保證數(shù)據(jù)傳輸?shù)目煽啃?，在計算機網絡傳輸數(shù)據(jù)時，必須采用各種差錯檢測措施。循環(huán)冗余檢驗的原理在數(shù)據(jù)鏈路層傳送的幀中，廣泛使用了循環(huán)冗余檢驗CRC的檢錯技術。在發(fā)送端，先把數(shù)據(jù)劃分為組。假定每組k個比特。假設待傳送的一組數(shù)據(jù)M=101001（現(xiàn)在k=6）。我們在M的后面再添加供差錯檢測用的n

位冗余碼一起發(fā)送。冗余碼的計算用二進制的模

2

運算進行2n乘M的運算，這相當于在M后面添加n個0。得到的(k+n)位的數(shù)除以事先選定好的長度為(n+1)位的除數(shù)

P，得出商是Q而余數(shù)是R，余數(shù)R比除數(shù)P少1位，即R是n

位。冗余碼的計算舉例現(xiàn)在

k=6,M=101001。設

n=3,除數(shù)

P=1101，被除數(shù)是2nM=101001000。模2運算的結果是：商

Q=110101，

余數(shù)

R=001。把余數(shù)R作為冗余碼添加在數(shù)據(jù)M的后面發(fā)送出去。發(fā)送的數(shù)據(jù)是：2nM+R

即：101001001，共(k+n)位。

110101

←

Q

(商)P(除數(shù))→

1101101001000

←

2nM(被除數(shù))

1101

1110

1101

0111

0000

1110

1101

0110

0000

1100

1101

001←R(余數(shù))，作為FCS

循環(huán)冗余檢驗

1101010110

←

Q

商

除數(shù)

G

→

110101101000110100000

←

2nM被除數(shù)

110101

111011

110101

111010

110101

111110

110101

101100

110101

110010

110101

01110

←

R

余數(shù)循環(huán)冗余檢驗的原理說明假設待傳送的數(shù)據(jù)M=1010001101（共kbit）。我們在M的后面再添加供差錯檢測用的nbit冗余碼一起發(fā)送。循環(huán)冗余檢驗舉例幀檢驗序列FCS在數(shù)據(jù)后面添加上的冗余碼稱為幀檢驗序列

FCS(FrameCheckSequence)。循環(huán)冗余檢驗CRC和幀檢驗序列FCS并不等同。CRC是一種常用的檢錯方法，而FCS是添加在數(shù)據(jù)后面的冗余碼。FCS可以用CRC這種方法得出，但CRC并非用來獲得FCS的唯一方法。

接收端對收到的每一幀進行CRC檢驗(1)若得出的余數(shù)R=0，則判定這個幀沒有差錯，就接受(accept)。（嚴格說，這么做是不正確的，有可能出現(xiàn)R為0，而幀有差錯，那為什么可以這么做呢，其理由是：R為0，而幀有差錯的概率很?。?2)若余數(shù)R

0，則判定這個幀有差錯，就丟棄。（嚴格說，這么做是正確的，即R

0這個幀一定出了差錯）但這種檢測方法并不能確定究竟是哪一個或哪幾個比特出現(xiàn)了差錯。（因此，這是一種后向糾錯方法）只要經過嚴格的挑選，并使用位數(shù)足夠多的除數(shù)

P，那么出現(xiàn)檢測不到的差錯的概率就很小很小。CRC校驗碼的檢錯能力：可檢出所有奇數(shù)個錯；可檢出所有雙位錯；可檢出所有≤G(x)長度的突發(fā)錯。常用的生成多項式G(x)：CRC16=x16+x15+x2+1CRC32=x32+x26+x23+x22+x16+x11+x10+x8+x7+x5+x4+x2+x+1應當注意僅用循環(huán)冗余檢驗CRC差錯檢測技術只能做到無差錯接受(accept)?！盁o差錯接受”是指：“凡是接受的幀（即不包括丟棄的幀），我們都能以非常接近于

1

的概率認為這些幀在傳輸過程中沒有產生差錯”。也就是說：“凡是接收端數(shù)據(jù)鏈路層接受的幀都沒有傳輸差錯”（有差錯的幀就丟棄而不接受）。要做到“可靠傳輸”（即發(fā)送什么就收到什么）就必須再加上確認和重傳機制。內容提要1.概述前面介紹了差錯檢驗的問題，下面介紹鏈路管理2.MAC協(xié)議CSMA √IEEE802.11MAC協(xié)議 S-MAC協(xié)議CSMA載波監(jiān)聽多點接入“多點接入”表示許多計算機以多點接入的方式連接在一根總線上。“載波監(jiān)聽”是指每一個站在發(fā)送數(shù)據(jù)之前先要檢測一下總線上是否有其他計算機在發(fā)送數(shù)據(jù)，如果有，則暫時不要發(fā)送數(shù)據(jù)，以免發(fā)生碰撞。CSMA分為堅持型與非堅持型CSMA/CD表示CarrierSenseMultipleAccesswithCollisionDetection。檢測到碰撞后在發(fā)生碰撞時，總線上傳輸?shù)男盘柈a生了嚴重的失真，無法從中恢復出有用的信息來。每一個正在發(fā)送數(shù)據(jù)的站，一旦發(fā)現(xiàn)總線上出現(xiàn)了碰撞，就要立即停止發(fā)送，免得繼續(xù)浪費網絡資源，然后等待一段隨機時間后再次發(fā)送。電磁波在總線上的有限傳播速率的影響當某個站監(jiān)聽到總線是空閑時，也可能總線并非真正是空閑的。A向B發(fā)出的信息，要經過一定的時間后才能傳送到B。B若在A發(fā)送的信息到達B之前發(fā)送自己的幀(因為這時B的載波監(jiān)聽檢測不到A所發(fā)送的信息)，則必然要在某個時間和A發(fā)送的幀發(fā)生碰撞。碰撞的結果是兩個幀都變得無用。1kmABt碰撞t=2

A檢測到發(fā)生碰撞t=

B發(fā)送數(shù)據(jù)B檢測到發(fā)生碰撞t=t=0單程端到端傳播時延記為

傳播時延對載波監(jiān)聽的影響1kmABt碰撞t=

B檢測到信道空閑發(fā)送數(shù)據(jù)t=

/2發(fā)生碰撞t=2

A檢測到發(fā)生碰撞t=

B發(fā)送數(shù)據(jù)B檢測到發(fā)生碰撞t=ABABABt=0A檢測到信道空閑發(fā)送數(shù)據(jù)ABt=0t=B檢測到發(fā)生碰撞停止發(fā)送STOPt=2

A檢測到發(fā)生碰撞STOPAB單程端到端傳播時延記為

爭用期最先發(fā)送數(shù)據(jù)幀的站，在發(fā)送數(shù)據(jù)幀后至多經過時間2（兩倍的端到端往返時延）就可知道發(fā)送的數(shù)據(jù)幀是否遭受了碰撞。（如上一頁所示）以太網的端到端往返時延2稱為爭用期，或碰撞窗口。經過爭用期這段時間還沒有檢測到碰撞，才能肯定這次發(fā)送不會發(fā)生碰撞。爭用期的長度以太網取51.2s為爭用期的長度。對于10Mb/s以太網，在爭用期內可發(fā)送512bit，即64字節(jié)。以太網在發(fā)送數(shù)據(jù)時，若前64字節(jié)沒有發(fā)生沖突，則后續(xù)的數(shù)據(jù)就不會發(fā)生沖突。最短有效幀長如果發(fā)生沖突，就一定是在發(fā)送的前64字節(jié)之內。由于一檢測到沖突就立即中止發(fā)送，這時已經發(fā)送出去的數(shù)據(jù)一定小于64字節(jié)。以太網規(guī)定了最短有效幀長為64字節(jié)，凡長度小于64字節(jié)的幀都是由于沖突而異常中止的無效幀。強化碰撞當發(fā)送數(shù)據(jù)的站一旦發(fā)現(xiàn)發(fā)生了碰撞時：立即停止發(fā)送數(shù)據(jù)；再繼續(xù)發(fā)送若干比特的人為干擾信號(jammingsignal)，以便讓所有用戶都知道現(xiàn)在已經發(fā)生了碰撞。

數(shù)據(jù)幀干擾信號TJ人為干擾信號ABTBtB發(fā)送數(shù)據(jù)A檢測到沖突開始沖突信道占用時間A發(fā)送數(shù)據(jù)B也能夠檢測到沖突，并立即停止發(fā)送數(shù)據(jù)幀，接著就發(fā)送干擾信號。這里為了簡單起見，只畫出A發(fā)送干擾信號的情況。內容提要1.概述2.MAC協(xié)議CSMA IEEE802.11MAC協(xié)議 √S-MAC協(xié)議CSMA/CD協(xié)議不適用于無線網絡主要原因如下：無線局域網中的隱蔽站問題隱蔽站:A,C兩個站點不能互相“聽見”障礙物,信號衰減在B站點發(fā)生沖突

802.11MAC的設計目標:

避免可能在B站發(fā)生的沖突CSMA/CA:帶有沖突避免（CollisionAvoidance）策略的CSMA，見第53頁倒數(shù)第3、4段的描述。暴露站問題IEEE802.11MAC協(xié)議IEEE802.11MAC協(xié)議分為分布式協(xié)調功能(DistributedCoordinationFunction,DCF)和點協(xié)調功能(PointCoordinationFunction，PCF)兩種訪問控制方式，其中DCF方式是IEEE802.11協(xié)議的基本訪問控制方式。（54頁第1、2段）幀間間隔IEEE802.11MAC協(xié)議規(guī)定了三種基本幀間間隔(InterFrameSpace，IFS)，用來提供訪問無線信道的優(yōu)先級：SIFS(shortIFS)：最短幀間間隔。PIFS(PCFIFS)：PCF方式下節(jié)點使用的幀間間隔。DIFS(DCFIFS)：DCF方式下節(jié)點使用的幀間問隔。

根據(jù)CSMA/CA協(xié)議，當節(jié)點要傳輸一個分組時，它首先偵聽信道狀態(tài)。如果信道空閑，而且經過一個幀間間隔時間DIFS后，信道仍然空閑，則站點立即開始發(fā)送信息。如果信道忙，則站點始終偵聽信道，直到信道的空閑時間超過DIFS。當信道最終空閑下來的時候，節(jié)點進一步使用二進制退避算法，進入退避狀態(tài)來避免發(fā)生碰撞。隨機退避時間按下面公式進行計算：

退避時間=Random()×aSlottime

其中，Random()是在競爭窗口[0，CW]內均勻分布的偽隨機整數(shù)；CW是整數(shù)隨機數(shù)，它的數(shù)值位于標準規(guī)定的aCWmin和aCWmax之間；aSlottime是一個時槽時間，包括發(fā)射啟動時間、介質傳播時延、檢測信道的響應時間等。

網絡節(jié)點在進入退避狀態(tài)時，啟動一個退避計時器，當計時達到退避時間后結束退避狀態(tài)。在退避狀態(tài)下，只有當檢測到信道空閑時才進行計時。如果信道忙，退避計時器中止計時，直到檢測到信道空閑時間大于DIFS后才繼續(xù)計時。當多個節(jié)點推遲且進入隨機退避時，利用隨機函數(shù)選擇最小退避時間的節(jié)點作為競爭優(yōu)勝者。802.11MAC層:CSMA/CA簡述802.11CSMA:發(fā)送方-如果檢測到信道閑置了DISF

秒.

然后傳輸整個幀(無沖突檢測)-如果檢測到信道忙

然后進行二進制避退802.11CSMA接收方:如果接收OK

等待SIFS后返回ACKIEEE802.11MAC協(xié)議802.11CSMA協(xié)議:其他方NAV:網絡分配向量（NetworkAllocation

Vector）802.11幀具有傳輸時間字段其他站點(聽見有傳輸時)必須推遲若干NAV時間單位再對信道進行訪問沖突避免:RTS-CTS交換CSMA/CA:進行顯式的信道預留發(fā)送方:發(fā)送簡短的RTS:requesttosend接收方:使用簡短的CTS:cleartosend回應CTS為發(fā)送方預留了信道,并通知了其他(可能是隱蔽的)站點避免了隱蔽站點問題A,B,CA,B,D沖突避免:RTS-CTS交換由于RTS/CTS比較短:發(fā)送時間短，發(fā)生沖突的可能小最終的結果同沖突檢測基本一致802.11MAC協(xié)議通過立即主動確認機制和預留機制提高性能。在主動確認機制中，當目標節(jié)點收到一個發(fā)送給它的有效數(shù)據(jù)幀(DATA)時，必須向源節(jié)點發(fā)送一個應答幀(ACK)，確認數(shù)據(jù)已被正確接收到。為了保證目標節(jié)點在發(fā)送ACK過程中不與其它節(jié)點發(fā)生沖突，目標節(jié)點使用SIFS幀間隔。主動確認機制只能用于有明確目標地址的幀，不能用于組播和廣播報文傳輸。802.11MAC小結CSMA/CA什么是CSMA/CA3種IFSRTC/CTSNAV無線傳感器網絡MAC協(xié)議概述無線傳感器網絡MAC協(xié)議需要考慮3個問題（52頁）節(jié)省能量可擴展性網絡效率傳統(tǒng)MAC協(xié)議不適于無線傳感器網絡（52頁最后一段）例如，IEEE802.11MAC協(xié)議無線傳感器網絡MAC協(xié)議通常采用“偵聽/睡眠”的策略（53頁）MAC協(xié)議分類分類方式（53頁）分配信道的方式 時分復用無競爭型隨機競爭型 （53頁倒數(shù)第5段）例如，SMAC √混合型：二者結合使用的信道數(shù)目單信道多信道控制方式集中式控制發(fā)布式控制52SensorMAC協(xié)議SensorMAC協(xié)議概述是一種基于競爭的MAC層協(xié)議S-MAC協(xié)議的適用條件是傳感器網絡的數(shù)據(jù)傳輸量不大，網絡內部能夠進行數(shù)據(jù)的處理和融合以減少數(shù)據(jù)通信量，網絡能容忍一定程度的通信延遲在802.1lMAC協(xié)議的基礎上，針對傳感器網絡的節(jié)省能量需求而提出的采用RTS/CTS/DATA/ACK作為基本傳輸機制SMAC協(xié)議-基本思想周期性睡眠和監(jiān)聽機制：睡眠與監(jiān)聽的周期交替流量自適應偵聽機制：不進入睡眠而是保持偵聽狀態(tài)串擾避免機制：鄰居通信的時候，進入睡眠狀態(tài)消息傳遞機制：支持長消息傳輸SMAC協(xié)議-基本思想周期性睡眠和監(jiān)聽（57頁）為什么周期性睡眠和監(jiān)聽什么是周期性睡眠和監(jiān)聽S-MAC協(xié)議將時間分為幀，幀內分