西安电子科技大学：《通信网络基础》课程教学资源（讲义）第四章 多址技术（多址接入协议）4.4 冲突分解算法

Xidian Univ. 4.4冲突分解算法 Broadband Wireless Communications Laboratory,Xidian University

Broadband Wireless Communications Laboratory, Xidian University 1 BWC Xidian Univ. ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈~ ≈ ~ ≈ 4.4 冲突分解算法

Xidian Univ. 冲突分解算法 ·对于有竞争的多址接入协议如何解决冲突 从而使所有碰撞用户都可以成功传输是一 个非常重要的问题。 ■ 通过调整对等待重传队列长度的估值，改 变重传概率，可以进一步减缓碰撞。 ·另一种更有效的解决冲突的方式就是冲突 分解（Collision Resolution) Broadband Wireless Communications Laboratory,Xidian University

Broadband Wireless Communications Laboratory, Xidian University 2 BWC Xidian Univ. ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈~ ≈ ~ ≈ 冲突分解算法  对于有竞争的多址接入协议如何解决冲突 从而使所有碰撞用户都可以成功传输是一 个非常重要的问题。  通过调整对等待重传队列长度的估值，改 变重传概率，可以进一步减缓碰撞。  另一种更有效的解决冲突的方式就是冲突 分解（Collision Resolution）

Xidian Univ 冲突分解算法 ·冲突分解的基本思想是： 如果系统发生碰撞，则让新到达的分组 在系统外等待，在参与碰撞的分组均成 功传输结束后，再让新分组传输。 Broadband Wireless Communications Laboratory,Xidian University

Broadband Wireless Communications Laboratory, Xidian University 3 BWC Xidian Univ. ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈~ ≈ ~ ≈ 冲突分解算法  冲突分解的基本思想是： – 如果系统发生碰撞，则让新到达的分组 在系统外等待，在参与碰撞的分组均成 功传输结束后，再让新分组传输

Xidian Univ 冲突分解算法 ▣例4.2：设两个分组在第个时隙发生碰撞， 若每个分组独立的以1/2的概率在第+1和 +2时隙内重传。求在这次冲突分解过程的 通过率。 Broadband Wireless Communications Laboratory,Xidian University

Broadband Wireless Communications Laboratory, Xidian University 4 BWC Xidian Univ. ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈~ ≈ ~ ≈ 冲突分解算法  例4.2：设两个分组在第i个时隙发生碰撞， 若每个分组独立的以 1/2的概率在第 i+1和 i+2时隙内重传。求在这次冲突分解过程的 通过率

BW Xidian Unit 冲突分解算法 解： -在第+1个时隙内有一个分组成功传输的概率为2。如 果成功，另一个分组在第+2个时隙内成功传输，此时 需2个时隙解决碰撞。 如果第+1个时隙空闲或再次碰撞，则每个分组再独立 地以概率1/2在第+2和+3时隙内重传。这样在第+2 个时隙内有一个分组成功传输的概率为1/4；如成功， 另一个分组在第+3个时隙成功传输，此时共需3个时 隙解决碰撞。 -依此类推，需要k个时隙完成冲突分解的概率为2(k-) Broadband Wireless Communications Laboratory,Xidian University 5

Broadband Wireless Communications Laboratory, Xidian University 5 BWC Xidian Univ. ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈~ ≈ ~ ≈ 冲突分解算法  解： – 在第 i+1个时隙内有一个分组成功传输的概率为 ½。如 果成功，另一个分组在第i+2个时隙内成功传输，此时 需2个时隙解决碰撞。 – 如果第 i+1个时隙空闲或再次碰撞，则每个分组再独立 地以概率 1/2在第 i+2和i+3时隙内重传。这样在第 i+2 个时隙内有一个分组成功传输的概率为 1/4；如成功， 另一个分组在第 i+3个时隙成功传输，此时共需3个时 隙解决碰撞。 – 依此类推，需要k个时隙完成冲突分解的概率为 ( 1) 2− k−

Xidian Univ. 冲突分解算法 设在冲突分解区间，平均需要E时隙完成分 组的冲突分解，使得两个分组均传输成功： 刚=2x3+3xc产++kx×(+… 2×t1-22×分-22-2=3 平均需要3个时隙才能成功发送2个分组。因而 在冲突分解的过程中，通过率为23。 Broadband Wireless Communications Laboratory,Xidian University

Broadband Wireless Communications Laboratory, Xidian University 6 BWC Xidian Univ. ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈~ ≈ ~ ≈ 冲突分解算法 – 设在冲突分解区间，平均需要E[t]时隙完成分 组的冲突分解，使得两个分组均传输成功 ： – 平均需要3个时隙才能成功发送2个分组。因而 在冲突分解的过程中，通过率为 2/3。 2 1 1 2 1 11 1 [ ] 2 ( ) 3 ( ) .. ( ) 22 2 1 11 1 ( ) 2( ( ) ) 2(2 ) 3 2 22 2 k k i k i E t k k i − ∞ ∞ − = = =× +× ++× + = × = × −= −= ∑ ∑ 

Xidian Univ 冲突分解算法 例4.2说明了，通过冲突分解可以有效的提高系统的 通过率。有很多方法可以决定碰撞节点如何进行重 传。下面我们给出两种具体的冲突分解算法： ■树形分裂算法(Tree Splitting Algorithm) ·先到先服务(FCFS Splitting Algorithm)分裂算 法 Broadband Wireless Communications Laboratory,Xidian University

Broadband Wireless Communications Laboratory, Xidian University 7 BWC Xidian Univ. ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈~ ≈ ~ ≈ 冲突分解算法 例4.2说明了，通过冲突分解可以有效的提高系统的 通过率。有很多方法可以决定碰撞节点如何进行重 传。下面我们给出两种具体的冲突分解算法：  树形分裂算法（Tree Splitting Algorithm）  先到先服务（FCFS Splitting Algorithm）分裂算 法

Xidian Univ. 4.4.1树形分裂算法 Broadband Wireless Communications Laboratory,Xidian University 8

Broadband Wireless Communications Laboratory, Xidian University 8 BWC Xidian Univ. ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈~ ≈ ~ ≈ 4.4.1 树形分裂算法

Xidian Univ. 树形分裂算法 ■假设在第k个时隙发生碰撞，碰撞节点的集合为S。 ·所有未介入碰撞的节点进入等待状态。 S被随机地分成两个子集，用左集(L)和右集 (R)表示。 ■左集（L)先在第k+1时隙中传输。 Broadband Wireless Communications Laboratory,Xidian University

Broadband Wireless Communications Laboratory, Xidian University 9 BWC Xidian Univ. ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈~ ≈ ~ ≈  假设在第k个时隙发生碰撞，碰撞节点的集合为S。  所有未介入碰撞的节点进入等待状态。  S被随机地分成两个子集，用左集（L）和右集 （R）表示。  左集（L）先在第k+1时隙中传输。 树形分裂算法

Xidian Univ. 树形分裂算法 如果第k+1时隙中传输成功或空闲，则R在第k+2个时隙中 传输。 ■如果在第k+1时隙中发生碰撞，则将L再分为左集(LL) 和右集(LR),LL在第k+2时隙中传输。 ■如果第k+2时隙中传输成功或空闲，则LR在第k+3个时隙 中传输。 ■依次类推，直至集合S中所有的分组传输成功。 从碰撞的时隙（第k个时隙）开始，直至$集合中所有分组 成功传输结束的时隙称为一个冲突分解期(CP)。 Broadband Wireless Communications Laboratory,Xidian University 10

Broadband Wireless Communications Laboratory, Xidian University 10 BWC Xidian Univ. ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈ ~ ≈~ ≈ ~ ≈ 树形分裂算法  如果第k+1时隙中传输成功或空闲，则R在第k+2个时隙中 传输。  如果在第k+1时隙中发生碰撞，则将L再分为左集（LL） 和右集（LR），LL在第k+2时隙中传输。  如果第k+2时隙中传输成功或空闲，则LR在第k+3个时隙 中传输。  依次类推，直至集合S中所有的分组传输成功。  从碰撞的时隙（第k个时隙）开始，直至S集合中所有分组 成功传输结束的时隙称为一个冲突分解期（CRP）