单击此处编辑母版标题样式

Size: px

Start display at page:

Download "单击此处编辑母版标题样式"

故隐戚
5 years ago
Views:

1 4.3.2 载波侦听型多址协议 Broadband Wireless Communications Laboratory, Xidian University 1

2 作业 Broadband Wireless Communications Laboratory, Xidian University 2

3 在前面讨论的 ALOHA 协议中, 网络中的节点不考虑当前信道是忙还是闲, 一旦有分组到达就独自决定将分组发送到信道显然这种控制策略存在盲目性即使是稍有改进的时隙 ALOHA 协议, 其最大吞吐率也只能达到约若要进一步提高系统吞吐率, 还应进一步设法减少节点间发送冲突的概率 Broadband Wireless Communications Laboratory, Xidian University 3

4 为此, 除了缩小易受破坏区间外 ( 这也是有限度的 ), 还可以从减少发送的盲目性着手, 在发送之前先观察信道是否有用户在传输 ( 或进行载波侦听 ) 来确定信道忙闲状态, 然后再决定分组是否发送这就是被广泛采用的载波侦听型多址接入协议 CSMA(Carrier Sense Multiple Access) Broadband Wireless Communications Laboratory, Xidian University 4

5 CSMA--Polite version of Aloha CSMA 是从 ALOHA 协议演变出的一种改进型协议, 它采用了附加的硬件装置, 每个节点都能够检测 ( 侦听 ) 到信道上有无分组在传输如果一个节点有分组要传输, 它首先检测信道是否空闲, 如果信道有其他分组在传输, 则该节点可以等到信道空闲后再传输, 这样可以减少要发送的分组与正在传输的分组之间的碰撞, 提高系统的利用率 Broadband Wireless Communications Laboratory, Xidian University 5

6 CSMA CSMA 协议可细分为几种不同的实现形式 : 非坚持型 (Non-persistent)CSMA 1- 坚持型 CSMA p- 坚持型 CSMA Broadband Wireless Communications Laboratory, Xidian University 6

7 非坚持型 CSMA 所谓非坚持型 CSMA 是指当分组到达时, 若信道空闲, 则立即发送分组 ; 若信道处于忙状态, 则分组的发送将被延迟, 且节点不再跟踪信道的状态 ( 即节点暂时不检测信道 ), 延迟结束后节点再次检测信道状态, 并重复上述过程, 如此循环, 直到将该分组发送成功为止 Broadband Wireless Communications Laboratory, Xidian University 7

8 1- 坚持型 CSMA 所谓 1- 坚持型 CSMA 是指当分组到达时, 若信道空闲, 则立即发送分组 ; 若信道处于忙状态, 则该节点一直坚持检测信道状态, 直至检测到信道空闲后, 立即发送该分组 Broadband Wireless Communications Laboratory, Xidian University 8

9 p- 坚持型 CSMA 所谓 p- 坚持型 CSMA 是指当分组到达时, 若信道空闲, 则立即发送分组 ; 若信道处于忙状态, 则该节点一直检测信道的状态, 在检测到信道空闲后, 以概率 p 发送该分组 Broadband Wireless Communications Laboratory, Xidian University 9

10 由于电信号在介质中的传播时延, 在不同的观察点上监测到同一信道的出现或消失的时刻是不相同的因此, 在 CSMA 多址协议中, 影响系统性能的主要参数是 ( 信道 ) 载波的检测时延 (τ) 它包括两部分 : 发送节点到检测节点的传播时延和物理层检测时延 ( 即检测节点开始检测到检测节点给出信道是忙或闲所需的时间 ) 设信道速率为 C(bit/s), 分组长度为 L(bit), 则归一化的载波侦听 ( 检测 ) 时延为 β = τ =τ C ( L/ C) L Broadband Wireless Communications Laboratory, Xidian University 10

11 1 非时隙 CSMA 多址协议 Broadband Wireless Communications Laboratory, Xidian University 11

12 非时隙 CSMA 非坚持型非时隙 CSMA 协议的工作过程如下 : 当分组到达时, 如果信道空闲, 则立即发送该分组 ; 如果信道忙, 则分组被延迟一段时间后, 重新检测信道 Broadband Wireless Communications Laboratory, Xidian University 12

13 非时隙 CSMA 如果信道忙或发送时与其它分组碰撞, 则该分组变成等待重传的分组每个等待重传的分组将重复地尝试重传, 重传间隔相互独立且服从指数分布其具体的控制算法描述如下 : 1) 若有分组等待发送, 则转到第 2) 步, 否则处于空闲状态, 等待分组到达 2) 监测信道 : 若信道空闲, 启动发送分组, 发完返回第 1) 步 ; 若信道忙, 放弃监测信道, 选择一个随机时延的时间长度 t 开始延时 ( 此时节点处于退避状态 ) 3) 延时结束, 转至第 1) 步 Broadband Wireless Communications Laboratory, Xidian University 13

14 非时隙 CSMA 分组 i 到达分组 i 在节点内等待的时间退避退避分组 i 发送 τ τ τ t 忙忙闲信道分组 i t τ 为每次监测信道的持续时间表示信道上有其它分组在传输 Broadband Wireless Communications Laboratory, Xidian University 14

15 非时隙 CSMA 非时隙非坚持型 CSMA 多址协议的主要特点是在发送数据前先监测信道, 一旦监测到信道忙时, 能主动的退避一段时间 ( 暂时放弃监测信道 ), 其系统通过率为 S βg U Ge = = B+ I G(1+ 2 β ) + e βg B是信道的忙碌期,I 是信道空闲期, U 是忙碌期中用于成功传输数据的平均时间 Broadband Wireless Communications Laboratory, Xidian University 15

16 非时隙 CSMA U S = B+ I βg U = e 1 I = Poisson到达的平均间隔 G B = (1 + Y + β ) F( y) = P( 在 - β 内无到达 y ) Y =e ( β yg ) 1 e = β G 在内无到达的概率 β, βg y, β 分组到达平均间隔长度 βg U Ge = = B+ I G(1+ 2 β ) + e S Y βg Broadband Wireless Communications Laboratory, Xidian University 16 β 忙碌期 B 空闲期 I 忙碌期 B β

17 2 时隙 CSMA 多址协议 Broadband Wireless Communications Laboratory, Xidian University 17

18 时隙 CSMA 协议时隙 CSMA 协议把时间轴分成宽度为 β 的时隙 ( 注意 : 时隙 ALOHA 中时隙的宽度为一个分组的长度, 这里的时隙宽度为载波检测时间 ) 如果分组到达一个空闲的时隙, 它将在下一个空闲时隙开始传输 Broadband Wireless Communications Laboratory, Xidian University 18

19 时隙 CSMA 协议如果某节点的分组到达时, 信道上有分组正在传输, 则该节点变为等待重传的节点, 它将在当前分组传输结束后的后续空闲时隙中以概率 q r 进行传输 Broadband Wireless Communications Laboratory, Xidian University 19

20 时隙 CSMA 协议我们可以用马尔可夫链来分析时隙 CSMA 协议的性能设分组长度为 1 个单位长度, 其总的到达过程是速率为 λ 的 Poisson 到达过程, 网络中有无穷多个节点 ( 假设 B) 信道状态 0 1 e 的反馈时延最大为 β 又设系统的状态为每一个空闲时隙结束时刻等待重传的分组数 n, 则相继两个状态转移的时间间隔为 β 或 β+1 Broadband Wireless Communications Laboratory, Xidian University 20

21 时隙 CSMA 协议 g( n) = λβ + q r n Broadband Wireless Communications Laboratory, Xidian University 21

22 时隙 CSMA 协议定义在一个状态转移间隔内 n 的平均变化数为 D n = E{ 状态转移间隔内到达的分组数 } = λ E{ 状态转移间隔 } E{ 状态转移间隔时隙空闲时隙空闲 } = β P( ) + (1 + β)(1 P( )) succ P = β + 1 P( 时隙空闲 ) succ λβ n λβ r = β + 1 e (1 q ) β + 1 e e 时隙空闲对应于 β 间隔内无分组到达, 以及 n 个等待重传的节点没有分组发送 r Broadband Wireless Communications Laboratory, Xidian University 22 P qn

23 时隙 CSMA 协议分组成功传输的条件是 : 在 β 内有一个分组到达且 n 个等待重传的节点没有分组发送, 或在 β 内没有新分组到达但 n 个等待重传的节点有一个分组传输因此有, = λβ λβ (1 ) n + λβ (1 ) n 1 succ r r r P e q e nq q q = λβ r n e λβ + (1 q ) r 1 qr ( λβ + qn) g( n) ( λβ + qne ) r = gne ( ) r Broadband Wireless Communications Laboratory, Xidian University 23 n

24 Broadband Wireless Communications Laboratory, Xidian University 24 BWC 时隙 CSMA 协议当 q r 较小时, 有进而有是在一个状态转移间隔内到达分组数和重传分组数之和, 即在一个状态转移间隔内试图进行传输的总分组数 [ ] { } + + = n r r r n r n q e n q q q e D ) (1 1 ) (1 1 λβ λβ λβ β λ - n q n r n r r e q q ) (1 ) (1 1 ) ( ) ( ) ( ) 1 ( n g n g n e n g e D + β λ n q n g r + = λβ ) (

25 时隙 CSMA 协议 D n λ( β + 1 e g( n) ) g( n) e g( n) 使 D n 为负的条件为 : g( n) e λ < β + 1 e g( n) g( n) (4-31) 由于在一个状态转移间隔内到达的总分组数 ( 新到达的和重传的分组数之和 ) 是服从参数为 g(n) 的 Poisson 分布, 所以式 (4-31) 右边的分子为每个状态转移区间内平均成功传输的分组数, 分母为平均状态转移区间的长度, 两者相除表示单位时间内的平均离开率 ( 通过率 ) Broadband Wireless Communications Laboratory, Xidian University 25

26 时隙 CSMA 协议 Broadband Wireless Communications Laboratory, Xidian University 26

27 时隙 CSMA 协议 β=0.01 Broadband Wireless Communications Laboratory, Xidian University 27 β

28 时隙 CSMA 协议 G/S= 平均传输的次数 G/S-1= 平均重传的次数 Broadband Wireless Communications Laboratory, Xidian University 28

29 3 稳定的时隙 CSMA 多址协议 5.7 Broadband Wireless Communications Laboratory, Xidian University 29

30 稳定的时隙 CSMA 多址协议假定所有新进入系统的分组立即变成等待重传的分组设每个状态转移时刻的等待重传分组数为 n n 的估计值为 nˆ, 在每个空闲时隙结束时, 每个等待重传的分组独立地以概率 q r 发送, q r 是 nˆ 的函数稳定的时隙 CSMA 协议的基本出发点是根据 n 如何确定 q r, 使得 g( n) = nq = 2β, 从而使通过量达到最大 r Broadband Wireless Communications Laboratory, Xidian University 30

31 稳定的时隙 CSMA 多址协议给定 n 的估计值 q r nˆ 更新 nˆ 的规则为 :, q r 应该为 2β ( nˆ) = min, 2β ˆ n g(n) = nq ˆ (n) ˆ r ˆk + 1 n = nˆ nˆ k ( nˆ [ ] k 1 qr ( nˆ k ) [ 1 q ( nˆ )] + k r k + λβ + 2) + λ(1 + β ) λ(1 + β ) ; ; ; 时隙空闲成功传输碰撞上式中, 等号后的第一项反映了等待重传队列中分组数变化情况的估计, 第二项反映了新到达的分组数 Broadband Wireless Communications Laboratory, Xidian University 31

32 稳定的时隙 CSMA 多址协议 ˆk + 1 n = nˆ nˆ k ( nˆ [ ] k 1 qr ( nˆ k ) [ 1 q ( nˆ )] + k r k + λβ + 2) + λ(1 + β ) λ(1 + β ) ; ; ; 时隙空闲成功传输碰撞 Broadband Wireless Communications Laboratory, Xidian University 32

33 稳定的时隙 CSMA 多址协议可以证明, 只有当 : λ < β 该算法才是稳定的 Broadband Wireless Communications Laboratory, Xidian University 33

34 4 有碰撞检测功能的载波侦听型多址协议 (CSMA/CD) Broadband Wireless Communications Laboratory, Xidian University 34

35 CSMA/CD 前面讨论的 CSMA 协议由于在发送之前进行载波监听, 所以减少了冲突的机会但由于传播时延的存在, 冲突还是不可避免的只要发生冲突, 信道就被浪费一段时间 CSMA/CD 比 CSMA 又增加了一个功能, 这就是边发送边监听只要监听到信道上发生了冲突, 则冲突的节点就必须停止发送这样, 信道就很快空闲下来, 因而提高了信道的利用率这种边发送边监听的功能称为冲突检测 (Collision Detection) Broadband Wireless Communications Laboratory, Xidian University 35

36 CSMA/CD CSMA/CD 的工作过程如下 : 当一个节点有分组到达时, 它首先侦听信道, 看信道是否空闲如果信道空闲, 则立即发送分组 ; 如果信道忙, 则连续侦听信道, 直至信道空闲后立即发送分组该节点在发送分组的同时, 监测信道 δ 秒, 以便确定本节点的分组是否与其它节点发生碰撞 Broadband Wireless Communications Laboratory, Xidian University 36

37 CSMA/CD 如果没有发生碰撞, 则该节点会无冲突地占用该总线, 直至传输结束如果发生碰撞, 则该节点停止发送, 随机时延一段时间后重复上述过程在实际应用时, 发送节点在检测到碰撞以后, 还要产生一个阻塞信号来阻塞信道, 以防止其它节点没有检测到碰撞而继续传输 Broadband Wireless Communications Laboratory, Xidian University 37

38 CSMA/CD 总的来说,CSMA/CD 接入协议比 CSMA 多址接入协议的控制规则增加了如下三点 : 边说边听强化干扰碰撞检测窗口 Broadband Wireless Communications Laboratory, Xidian University 38

39 CSMA/CD 边说边听任一发送节点在发送数据帧期间要保持侦听信道的碰撞情况一旦检测到碰撞发生, 应立即中止发送, 而不管目前正在发送的帧是否发完保证尽快确知碰撞发生和尽早关闭碰撞发生后的无用发送, 这有利于提高信道利用率 Broadband Wireless Communications Laboratory, Xidian University 39

40 CSMA/CD 强化干扰发送节点在检测到碰撞并停止发送后, 立即改为发送一小段强化干扰信号, 以增强碰撞检测效果可以提高网络中所有节点对于碰撞检测的可信度, 保证了分布式控制的一致性 Broadband Wireless Communications Laboratory, Xidian University 40

41 CSMA/CD 碰撞检测窗口任一发送节点若能完整的发完一个数据帧, 则停顿一段时间 ( 两倍的最大传播时延 ) 并监听信道情况若在此期间未发生碰撞, 则可认为该数据帧已经发送成功此时间区间即称碰撞检测窗口有利于提高一个数据帧发送成功的可信度如果接收节点在此窗口内发送应答帧 (ACK 或 NAK) 的话, 则可保证应答传输成功 Broadband Wireless Communications Laboratory, Xidian University 41

42 CSMA/CD 协议的性能为了简化分析, 首先假定一个局域网 (LAN) 工作在时隙状态下, 以每个分组传输的结束时刻作为参考点, 将空闲信道分为若干个微时隙, 用分组长度进行归一化的微时隙的宽度为 β 所有节点都同步在微时隙的开始点进行传输如果在一个微时隙开始点有分组发送, 则经过一个微时隙后, 所有节点都检测到在该微时隙上是否发生碰撞如果发生了碰撞, 则立即停止发送 Broadband Wireless Communications Laboratory, Xidian University 42

43 CSMA/CD 协议的性能这里仍然用马尔可夫链的方法分析分析的方法与时隙 CSMA 协议相同设网络中有无穷多个节点, 每一个空闲时隙结束时的等待重传的分组数为 n, 每个等待重传的节点在每一个空闲时隙后发送的概率为 q r Broadband Wireless Communications Laboratory, Xidian University 43

44 CSMA/CD 协议的性能在一个空闲时隙发送分组的节点数为 g( n) = λβ + q r n 在一个空闲时隙后可能有三种情况 : 一是仍为空闲时隙, 二是一个成功传输 ( 归一化的分组长度为 1), 三是一个碰撞传输它们所对应的到达下一个空闲时隙结束时刻的区间长度分别为 β,1+β 和 2β Broadband Wireless Communications Laboratory, Xidian University 44

45 CSMA/CD 协议的性能因此, 两个状态转移时刻的平均间隔为 E状态转移时刻的间隔 += β gne + β e gne g( n) g( n) g( n) { } 1 ( ) [(1 ) ( ) ] 有到达的概率式中, 第一项表示在任何情况下基本的间隔为 β, 第二项是成功传输对平均间隔的额外贡献, 第三项是碰撞对平均间隔的额外贡献 Broadband Wireless Communications Laboratory, Xidian University 45

46 CSMA/CD 协议的性能定义在一个状态转移区间内,n 的变化量为 D = λ E{ 状态转移时刻的间隔 } n P succ P succ = g( n) e g( n) Broadband Wireless Communications Laboratory, Xidian University 46

47 CSMA/CD 协议的性能要使 D n < 0 λ < g( n) gne ( ) β + gne + + g( n) ( ) ( ) β g n [1 (1 gn ( )) e ] 从上式可以看出, 不等式的右边为分组离 1 开系统的概率, 其最大值为它对应的 g( n) = β Broadband Wireless Communications Laboratory, Xidian University 47

48 5 有碰撞避免功能的载波侦听型多址协议 (CSMA/CA) Broadband Wireless Communications Laboratory, Xidian University 48

49 CSMA/CA CSMA/CA 是有冲突避免 (Collision Avoidance) 的载波侦听型多址接入协议它是对 CSMA 的另一种改进方法通常在无线系统中, 一台无线设备不能在相同的频率 ( 信道 ) 上同时进行接收和发送, 因而不能采用碰撞检测 (CD) 技术因此, 只能通过冲突避免的方法来减少冲突的可能性在 IEEE 无线局域网 (WLAN) 的标准中, 就采用了 CSMA/CA 协议它不仅支持全连通的网络拓扑, 同时支持部分连通的网络拓扑 Broadband Wireless Communications Laboratory, Xidian University 49

50 CSMA/CA 基本工作过程 : 节点在发送数据帧之前进行信道预约 ; 接收节点收到预约后, 发送应答 ; 其他节点暂缓发送, 并根据信息计算退避时间 Broadband Wireless Communications Laboratory, Xidian University 50

51 IEEE MAC NAV=Network Allocation Vector Broadband Wireless Communications Laboratory, Xidian University 51

52 CSMA/CA IEEE 中 CSMA/CA 的基本工作过程是 : 一个节点在发送数据帧之前先对信道进行预约假定 A 要向 B 发送数据帧, 发送节点 A 先发送一个请求发送帧 RTS(Request To Send) 来预约信道, 所有收到 RTS 帧的节点将暂缓发送而真正的接收节点 B 在收到 RTS 后, 发送一个允许发送的应答帧 CTS(Clear To Send) Broadband Wireless Communications Laboratory, Xidian University 52

53 CSMA/CA 在 RTS 和 CTS 帧中均包括要发送分组的长度 ( 在给定信道传输速率及 RTS 和 CTS 长度的情况下, 各节点就可以计算出相应的退避时间, 该时间通常称为 NAV(Network Allocation Vector)) CTS 帧有两个作用 : 一是表明接收节点 B 可以接收发送节点 A 的帧, 二是禁止 B 的邻节点发送, 从而避免了 B 的邻节点的发送对 A 到 B 的数据传输的影响 RTS 和 CTS 帧很短, 如它们分别可为 20 和 14 个字节而数据帧最长可以达到 2346 字节相比之下,RTS 和 CTS 引入的开销不大 Broadband Wireless Communications Laboratory, Xidian University 53

54 CSMA/CA 为了尽量避免冲突,IEEE 标准给出了三种不同的帧间间隔 IFS(Inter Frame Space), 它们的长短各不相同参照图 4-20, 我们给出只使用一种 IFS( 假定对图中的 SIFS DIFS 不加以区分 ) 时的 CSMA/CA 接入算法 (1) 发送帧的节点先侦听信道若发现信道空闲, 则继续侦听一段时间 IFS, 看信道是否仍为空闲如是, 则立即发送数据 (2) 若发现信道忙 ( 无论是一开始就发现, 还是在后来的 IFS 时间内发现 ), 则继续监听信道, 直到信道变为空闲 Broadband Wireless Communications Laboratory, Xidian University 54

55 CSMA/CA (3) 一旦信道变为空闲, 此节点延时另一个时间 IFS 若信道在时间 IFS 内仍为空闲, 则按二进制指数退避算法延时一段时间只有在退避期间信道一直保持空闲, 该节点才能发送数据这样做可使在网络负荷很重的情况下, 发生冲突的机会大为减小所谓二进制指数退避算法, 即对一个分组的重发退避时延的取值范围与该分组的重发次数构成二进制指数关系也就是说, 随着分组遭碰撞而重发次数的增加, 其退避时延的取值范围按 2 的指数增大 Broadband Wireless Communications Laboratory, Xidian University 55

56 CSMA/CA IEEE 协议中定义了三种不同的帧间间隔 : SIFS, 即短帧帧间间隔 (Short IFS), 典型的数值只有 10µs PIFS, 即点协调功能中的帧间间隔, 比 SIFS 长, 在点协调 (PCF) 方式轮询时使用 DIFS, 即分布协调功能中的帧间间隔, 是最长的帧间间隔, 典型数值为 50µ s 在分布式协调 (DCF) 方式中使用 Broadband Wireless Communications Laboratory, Xidian University 56

单击此处编辑母版标题样式

单击此处编辑母版标题样式 4.3 随机多址接入协议 Broadband Wireless Communications Laboratory, Xidian University 1 作业 4.2 4.3 4.4 4.5 Broadband Wireless Communications Laboratory, Xidian University 2 随机多址接入协议随机多址协议 ( 有竞争的多址接入协议 ) 网络中的节点在网络中的地位是等同的