0

我正在研究一个简单的指数退避算法，我想知道我的结果是否正确。以下是假设：

  • 有N个车站

  • 每个站有 1 个数据包要发送

  • 最初，所有站都尝试在时隙 0 中发送

  • 当两个或多个站点想要在同一时隙中发送它们的帧时会发生冲突（因此所有站点的帧在第一轮中发生冲突）

  • 当发生碰撞时，站使用指数退避函数计算其等待时间（即在c次碰撞后，它将等待0到2^c - 1的随机时隙数）

我用Java编码。以下是使用 10 个站点的运行结果：

插槽 0：站 0 站 1 站 2 站 3 站 4 站 5 站 6 站 7 站 8 站 9
插槽 1：  
插槽 2：  
插槽 3：  
插槽 4：  
插槽 5：  
插槽 6：  
插槽 7：  
插槽 8：  
插槽 9：  
插槽 10：     
插槽 11：     
插槽 12：     
插槽 13：     
插槽 14：     
插槽 15：     
插槽 16：     
插槽 17：     
插槽 18：     
插槽 19：     
插槽 20：     
插槽 21：     
插槽 22：     
插槽 23：     
插槽 24：     
插槽 25：     
插槽 26：     
插槽 27：     
插槽 28：     
插槽 29：     
插槽 30：     
插槽 31：     
插槽 32：     
插槽 33：     
插槽 34：     
插槽 35：     
插槽 36：     
插槽 37：     
插槽 38：     
插槽 39：     
插槽 40：     
插槽 41：     
插槽 42：     
插槽 43：     
插槽 44：     
插槽 45：     
插槽 46：     
插槽 47：     
插槽 48：     
插槽 49：     
第一轮碰撞： 站 0 站 1 站 2 站 3 站 4 站 5 站 6 站 7 站 8 站 9
插槽 0：  
插槽 1：站 1 站 3 站 5 站 6
插槽 2：站 0 站 2 站 4 站 7 站 8 站 9
插槽 3：  
插槽 4：  
插槽 5：  
插槽 6：  
插槽 7：  
插槽 8：  
插槽 9：  
插槽 10：     
插槽 11：     
插槽 12：     
插槽 13：     
插槽 14：     
插槽 15：     
插槽 16：     
插槽 17：     
插槽 18：     
插槽 19：     
插槽 20：     
插槽 21：     
插槽 22：     
插槽 23：     
插槽 24：     
插槽 25：     
插槽 26：     
插槽 27：     
插槽 28：     
插槽 29：     
插槽 30：     
插槽 31：     
插槽 32：     
插槽 33：     
插槽 34：     
插槽 35：     
插槽 36：     
插槽 37：     
插槽 38：     
插槽 39：     
插槽 40：     
插槽 41：     
插槽 42：     
插槽 43：     
插槽 44：     
插槽 45：     
插槽 46：     
插槽 47：     
插槽 48：     
插槽 49：     
第 2 轮碰撞： 站 0 站 1 站 2 站 3 站 4 站 5 站 6 站 7 站 8 站 9
插槽 0：  
插槽 1：  
插槽 2：站 3
插槽 3：站 0 站 2 站 4 站 6
插槽 4：站 1 站 8 站 9
插槽 5：第 5 站 第 7 站
插槽 6：  
插槽 7：  
插槽 8：  
插槽 9：  
插槽 10：     
插槽 11：     
插槽 12：     
插槽 13：     
插槽 14：     
插槽 15：     
插槽 16：     
插槽 17：     
插槽 18：     
插槽 19：     
插槽 20：     
插槽 21：     
插槽 22：     
插槽 23：     
插槽 24：     
插槽 25：     
插槽 26：     
插槽 27：     
插槽 28：     
插槽 29：     
插槽 30：     
插槽 31：     
插槽 32：     
插槽 33：     
插槽 34：     
插槽 35：     
插槽 36：     
插槽 37：     
插槽 38：     
插槽 39：     
插槽 40：     
插槽 41：     
插槽 42：     
插槽 43：     
插槽 44：     
插槽 45：     
插槽 46：     
插槽 47：     
插槽 48：     
插槽 49：     
第三轮碰撞： 0站 1站 2站 4站 5站 6站 7站 8站 9站
插槽 0：  
插槽 1：  
插槽 2：站 3
插槽 3：  
插槽 4：  
插槽 5：站 6
插槽 6：  
插槽 7：9 号站
插槽 8：站 0
插槽 9：站 1 站 4
插槽 10：8 号站
插槽 11：站 2
插槽 12：7 号站
插槽 13：第 5 站
插槽 14：     
插槽 15：     
插槽 16：     
插槽 17：     
插槽 18：     
插槽 19：     
插槽 20：     
插槽 21：     
插槽 22：     
插槽 23：     
插槽 24：     
插槽 25：     
插槽 26：     
插槽 27：     
插槽 28：     
插槽 29：     
插槽 30：     
插槽 31：     
插槽 32：     
插槽 33：     
插槽 34：     
插槽 35：     
插槽 36：     
插槽 37：     
插槽 38：     
插槽 39：     
插槽 40：     
插槽 41：     
插槽 42：     
插槽 43：     
插槽 44：     
插槽 45：     
插槽 46：     
插槽 47：     
插槽 48：     
插槽 49：     
第 4 轮碰撞：Station 1 Station 4
插槽 0：  
插槽 1：  
插槽 2：站 3
插槽 3：  
插槽 4：  
插槽 5：站 6
插槽 6：  
插槽 7：9 号站
插槽 8：站 0
插槽 9：  
插槽 10：8 号站
插槽 11：站 2
插槽 12：7 号站
插槽 13：第 5 站
插槽 14：站 1
插槽 15：     
插槽 16：     
插槽 17：     
插槽 18：     
插槽 19：     
插槽 20：     
插槽 21：     
插槽 22：     
插槽 23：站 4
插槽 24：     
插槽 25：     
插槽 26：     
插槽 27：     
插槽 28：     
插槽 29：     
插槽 30：     
插槽 31：     
插槽 32：     
插槽 33：     
插槽 34：     
插槽 35：     
插槽 36：     
插槽 37：     
插槽 38：     
插槽 39：     
插槽 40：     
插槽 41：     
插槽 42：     
插槽 43：     
插槽 44：     
插槽 45：     
插槽 46：     
插槽 47：     
插槽 48：     
插槽 49：     
第 5 轮碰撞：没有碰撞！
碰撞总数：77
站 0 在时隙 8 发送了 3 次冲突。
站 1 在时隙 14 发送了 4 次冲突。
站 2 在时隙 11 发送了 3 次冲突。
站 3 在时隙 2 发送了 2 次冲突。
站 4 在时隙 23 发送了 4 次冲突。
站 5 在时隙 13 发送了 3 次冲突。
站 6 在时隙 5 发送了 3 次冲突。
站 7 在时隙 12 发送了 3 次冲突。
站 8 在时隙 10 发送了 3 次冲突。
站 9 在时隙 7 发送了 3 次冲突。

这看起来对吗？我似乎无法在任何地方找到使用此功能的 N 个站的平均碰撞次数，所以我不确定我是否搞砸了。任何帮助是极大的赞赏。

4

1 回答 1

1

一个站可以尝试在一个时隙中多次发送似乎很奇怪。在我看来，退避值应该是电台跳过的时隙数。因此，如果站 A 在时间段 1 发生冲突并选择跳过 0 个时隙，它将被安排在时隙 2 再次发送。它不会尝试在同一时隙内重新发送。

这更有意义。一个站在一个时隙内最多可以尝试一次发送。

因此，如果每个人都试图在时隙 0 发送，他们都会发生冲突并选择跳过从 0 到 2^i-1 的随机数个时隙（其中 i 是当前时隙）。因为 2^i-1 为 0，所以它们都会尝试在时隙 1 发送。

平均而言，其中一半将尝试在时隙 2 发送，一半将尝试在时隙 3 发送。假设奇数站选择不跳过，偶数站都跳过一个时隙。在时间段 1 结束时，您的状态如下所示：

slot    stations
 2      1, 3, 5, 7, 9
 3      2, 4, 6, 8, 10

在时隙 2 期间也会发生冲突。每个站将选择跳过 0、1、2 或 3 个时隙。在时间段 2 之后，您的状态将类似于：

slot    stations
 3      1, 2, 4, 6, 8, 10
 4      3, 7
 5      9
 6      5

由于时隙 3 中的冲突，这六个站将自己分散在时隙 4 到 10 中（选择从 0 到 7 个时隙）。我会让你建立相应的状态。

最终你会到达一个点，在当前时隙只有一个站，然​​后那个站可以发送。

如果您以这种方式考虑问题，则调试代码会变得容易得多，因为您可以构建一个表格并显示每个时间段结束时的状态。这将告诉您是否正确选择了退避值，以及您是否根据所选的退避值正确调度了站点。

于 2013-10-30T19:43:53.897 回答