随机接入技术ALOHA.pdf

3 3 1 3 3 附录 B 随机接入技术 ALOHA 在 20 世纪 70 年代初期夏威夷大学首次试验成功随机接入 这是为了使地理上分散的 用户通过无线电来使用中心计算机 由于无线电信道是一个公用信道 一个站发送的信息 可以同时被多个站收到 而每个站又是随机发送的 因此这种系统是一个随机接入系统 夏威夷大学早期研制的系统称为 ALOHA 是 Additive Link On line HAwaii system 的缩写 而 ALOHA 恰好又是夏威夷方言的 你好 下面先介绍纯 ALOHA B 1 纯 ALOHA 1 工作原理 纯 ALOHA 就是最原始的 ALOHA 它可以工作在无线信道 也可以工作在总线式网 络中 为讨论其工作原理 我们采用如图 B 1 所示的模型 这个模型不仅可代表总线式网 络 而且可以代表无线信道的情况 站 1站 2站 N 1 站 N 总线信道 接口 图 B 1 ALOHA 系统的一般模型 图 B 2 表示一个 ALOHA 系统的工作原理 每一个站均自由地发送数据帧 为分析简 单起见 今后帧的长度不是用比特而是用发送这个帧所需的时间来表示 在图 B 2 中用 T0 代表这段时间 我们还设所有的站发送的帧都是定长的 6 5 4 2 3 1 7 发送成功 发送成功 发送成功 冲突重发 冲突重发 冲突重发 冲突再重发 t t t t t 站 1 站 2 站 N 1 站 N T0 2345671 帧到达 T0 T0T0 T0 图 B 2 纯 ALOHA 系统的工作原理 当站 1 发送帧 1 时 其他的站都未发送数据 所以站 1 的发送必定成功 这里不考虑 由信道不良而产生的误码 但随后站 2 和站 N 1 发送的帧 2 和帧 3 在时间上重叠了一些 这就是以前提到过的 碰撞 碰撞的结果是使碰撞的双方 有时也可能是多方 所发送的 数据都出现差错 因而都必须进行重传 但是发生碰撞的各站不能马上进行重传 因为这 样做就必然会继续产生碰撞 ALOHA 系统采用的重传策略是让各站等待一段随机的时间 然后再进行重传 如再发生碰撞 则需再等待一段随机的时间 直到重传成功为止 图中 其余的一些帧的发送情况是帧 4 发送成功 而帧 5 和帧 6 发生碰撞 2 性能分析 3 3 2 下面我们来分析纯 ALOHA 的一些主要性能 这就是吞吐量和平均时延的计算 为便于分析 我们在图 B 2 中用最下面的一个坐标将所有各站的发送情况都画在一起 用一个垂直向下的箭头表示某个帧的开始发送 可以和上面各站的发送情况对照来看 从 图中可看出 一个帧如欲发送成功 必须在该帧发送时刻之前和之后各一段时间 T0内 一 共有 2T0的时间间隔 没有其他帧的发送 否则就必产生碰撞而导致发送失败 例如 帧 3 发送时刻之前 T0的时间内 出现帧 2 的发送 因此帧 3 和帧 2 的发送都要失败 而帧 4 的发送时刻之前和之后的时间 T0内 没有其他帧的发送 因此帧 4 的发送必定成功 我们可以把每发送一个帧看成是有一个帧到达 ALOHA 网络 这样 一个帧发送成功 的条件 就是该帧与该帧前后的两个帧的到达时间间隔均大于 T0 我们设帧的到达服从泊松分布 但这并不完全符合实际情况 这是因为 虽然大量的 站同时随机地发送数据帧时 在每个站的通信量都很小的条件下 整个系统的帧到达可看 成是泊松过程 但在出现重传过程时 这样的到达过程就不再是泊松过程 而是一个与重 传策略有关的较为复杂的过程 然而如果重传时的随机时延足够长 那么认为帧的到达 包 括重传帧 是泊松过程仍是合理的 在这样的假定下 就可以使 ALOHA 系统的分析大为简 化 在有关 ALOHA 系统的文献中 一般都使用这样两个归一化的参数 它们是 1 吞吐量 S 这又称为吞吐率 它等于在帧的发送时间 T0内成功发送的平均帧数 显然 0 S 1 而 S 1 是极限情况 在 S 1 时 帧一个接一个地发送出去 帧与帧之 间没有空隙 这种情况虽然使信道的利用最为充分 但在众多用户随机发送帧的情况下是 不可能实现的 但是 可以用 S 接近于 1 的程度来衡量信道的利用率是否充分 当网络系统达到稳定状态时 在时间 T0内到达网络的平均帧数 即输入负载 应等于吞 吐量 S 2 网络负载 offered load G 从网络的角度看 G等于在T0内总共发送的平均帧数 这里包括发送成功的帧和因碰撞未发送成功而重传的帧 显然 G S 而只有在不发生碰 撞时 G 才等于 S 还应注意到 G 可以远大于 1 例如 G 10 表示在 T0时间内网络 共发送了 10 个帧 这当然会导致很多的碰撞 在稳定状态下 吞吐量 S 与网络负载 G 的关系为 S G P 发送成功 B 1 这里 P 发送成功 是一个帧发送成功的概率 它实际上就是发送成功的帧在所发送的帧的 总数中所占的比例 从图 B 2 可看出 若帧 4 要发送成功 帧 3 和帧 4 的时间间隔应大于 T0 同时帧 4 和帧 5 的时间间隔也要大于 T0 因此 若帧 4 要发送成功 必须在帧 4 到达 的前后各一个 T0的时间内没有其他帧的到达 因为假定了帧的到达是泊松过程 因此在 2T0的时间内有 k 个到达的概率是 P 在 2T0的时间内有 k 个到达 2 1 0 e 2 2 k k G G k B 2 在上式中 2G 是在 2T0的时间内的平均到达帧数 于是 S G P 发送成功 G P 在 2T0的时间内有 0 个到达 G G G 2 0 e 0 2 G G 2 e B 3 3 3 3 这就是 Abramson 于 1970 年首次推导出的 ALOHA 吞吐量公式 当 G 0 5 时 S 0 5e 1 0 184 这是吞吐量 S 可能达到的极大值 这点从图 B 3 的 吞吐量曲线可以看得很清楚 用求极值的方法也可很容易地得出这一结论 0 20 0 10 0 51 01 52 00 G S G S 不稳定区域 0 184 图 B 3 纯 ALOHA 的吞吐量与网络负载的关系曲线 B 3 式是在假设系统工作在稳定状态下推导出来的 然而图 B 3 所示的曲线在 G 值 大于 0 5 呈现负的斜率 因而这段区域是不稳定的 关于这点可做如下解释 设系统工作 在 G 0 5 的某一个点上 G S 假定现在由于某种原因使网络负载 G 增大了一些 根据 图中的曲线 吞吐量应下降 这表明成功发送的帧数减少而发生碰撞的帧数则增加 这种 情况就引起更多的重传 因而使网络负载 G 进一步增大 这样恶性循环的结果 使工作点 迅速沿曲线下降 直到吞吐量下降到零为止 这时 网络负载达到很大的数值 数据帧不 断地发送 碰撞 重传 但是并无有用的输出 整个系统完全不能工作了 可见 在 纯 ALOHA 系统中 网络负载 G 一定不能超过 0 5 一个理想随机接入系统的吞吐量 S 的极限值是 1 但纯 ALOHA 的吞吐量的极大值只 能达到理想值的 18 4 实际上为安全起见 纯 ALOHA 的吞吐量 S 不应超过 10 为 了提高 ALOHA 系统的吞吐量 在纯 ALOHA 出现之后又有了多种改进的 ALOHA 系统 虽然如此 在许多情况下 当需要进行突发式的交互性的数据通信时 采用纯 ALOHA 这样的方式可能既简单又便宜 当年夏威夷大学进行的实验也正是为这种环境而设计的 现在假定许多异步终端通过多点线路连到主机 线路的数据率为 4800 b s 设每份报文有 60 个字符 而用户用键盘输入一份报文需 2 分钟 包括思考时间 再设每个字符用 10 bit 进行编码 则每个终端的平均数据率仅 5 b s 如采用 ALOHA 方式 取 S 0 1 即仅利用 信道容量的 10 则信道的总数据率为 480 b s 这样的系统一共可容纳 480 5 96 个交互 式的用户 还是相当不错的 下面讨论帧的时延 设发完一帧后要经过 R 倍的 T0后才能收到确认信息因而才能发 送下一帧 这样 在最好的情况下 发送一帧所需的时间是 T0 1 R 但若所发送的帧发 生碰撞而必须重传 情况就不一样了 设由超时定时器决定重传需要经过的时间也是 R 倍 的 T0 但重传还要经过一段随机的时延 这样 从决定重传到重传完毕所需要的时间是 n 倍的 T0 而 n 是一个从 1 到某一个事先确定的正整数 K 之间的随机选择出的一个整数 每 次重传都要随机选择一次 重传完毕后 再经过时间 RT0才能收到确认信息 图 B 4 画的 是重传一次的情况 可以看出 当重传一次时 发送一帧所需的时间 从开始发送起到可以 发送下一帧时为止 最小是 T1 T1 T0 RT0 T0 RT0 最大是 T2 T2 T0 RT0 KT0 RT0 若一个帧平均重传 NR次才能发送成功 则不难得出发送一个帧总共所需的平均时间为 D T0 1 R NR R K 1 2 B 4 3 3 4 T0T0RT0 RT0 T1 RT0 t KT0 T2 冲突重传 时延最小 冲突再重传 时延最大 图 B 4 重传帧的时延时间 平均重传次数显然与整数 K 有关 不难想象 K 越小 重传时帧的碰撞机会就越大 因而重传次数也会增多 增大 K 值就可以减少再次碰撞的机会 但若使 K 值变得很大 则 发送一帧的平均时延就会很大 理论分析表明 选择 K 5 是一个很好的折衷 在这种情 况下 重传次数 NR与 K 的关系不大 此时可得出 G S 1 NR B 5 再利用 B 3 式的结果 得出 NR e2G 1 B 6 B 6 式表示 当网络负载增大时 帧的重传次数将按指数规律增长 B 2 时隙 ALOHA S ALOHA 为了提高 ALOHA 系统的吞吐量 可以将所有各站在时间上都同步起来 这要付出代 价 并将时间划分为一段段等长的时隙 slot 记为 T0 同时规定 只能在每个时隙开始 时才能发送一个帧 这样的 ALOHA 系统叫做时隙 ALOHA 或 S ALOHA 图 B 5 为两个站的时隙 ALOHA 的工作原理示意图 图中的一些向上的垂直箭头代表 帧的到达 时隙的长度是使得每个帧正好在一个时隙内发送完毕 从图 B 5 可看出 每一 个帧在到达后 一般都要在缓存中等待一段时间 这时间小于 T0 然后才能发送出去 当 在一个时隙内有两个或两个以上的帧到达时 则在下一个时隙将产生碰撞 碰撞后重传的 策略与纯 ALOHA 的情况是相似的 冲突重传 冲突重传 站 1 站 2 T0 T0 t t 帧到达 帧到达 帧到达 帧到达 图 B 5 时隙 ALOHA 的工作原理 现在推导时隙 ALOHA 的吞吐量公式 吞吐量 S 与网络负载 G 的定义与纯 ALOHA 的 相同 参阅图 B 5 设一个帧在某个时隙开始之前到达 显然 此帧能够发送成功的条件是 没有其他帧在同一时隙内到达 因此 S G P 发送成功 G P 在 T0的时间内有 0 个到达 G G G e 0 0 G G e B 7 3 3 5 此公式为 Roberts 在 1972 推导出来的 当 G 1 时 S Smax e 1 0 368 图 B 6 画出了 B 7 式表示的曲线 为便于比较 纯 ALOHA 的吞吐量且也画在同一坐标中 可以看出 对于时隙 ALOHA 不稳定区域位于 G 1 的部分 0 51 01 52 02 50 0 10 0 20 0 30 0 40 S G 0 368 0 184 时隙ALOHA 纯ALOHA SG G e SG G e 2 图 B 6 时隙 ALOHA 与纯 ALOHA 的吞吐量曲线 时隙 ALOHA 的发送一帧的平均时间的计算方法与纯 ALOHA 的相似 只是要注意 每个帧到达站的时间是随机的 到下一个时隙的到来平均要等待时间 T0 2 因此现在要在 B 4 式右端两个地方加上 0 5 即 D T0 1 5 R NR R 0 5 K 1 2 时隙 ALOHA B 8 这里 NR是帧的平均重传次数 当 K 很大时 NR与 K 基本无关 这样可以很容易求出 NR eG 1 时隙。