随机接入技术ALOHA

3.313.3附录B随机接入技术ALOHA在20世纪70年代初期夏威夷大学首次试验成功随机接入。这是为了使地理上分散的用户通过无线电来使用中心计算机。由于无线电信道是一个公用信道，一个站发送的信息可以同时被多个站收到，而每个站又是随机发送的，因此这种系统是一个随机接入系统。夏威夷大学早期研制的系统称为ALOHA，是AdditiveLinkOn-lineHAwaiisystem的缩写，而ALOHA恰好又是夏威夷方言的“你好”。下面先介绍纯ALOHA。B.1纯ALOHA1.工作原理纯ALOHA就是最原始的ALOHA。它可以工作在无线信道，也可以工作在总线式网络中。为讨论其工作原理，我们采用如图B-1所示的模型。这个模型不仅可代表总线式网络，而且可以代表无线信道的情况。站1站2站(N–1)站N总线信道接口图B-1ALOHA系统的一般模型图B-2表示一个ALOHA系统的工作原理。每一个站均自由地发送数据帧。为分析简单起见，今后帧的长度不是用比特而是用发送这个帧所需的时间来表示，在图B-2中用T0代表这段时间。我们还设所有的站发送的帧都是定长的。6542317发送成功发送成功发送成功冲突重发冲突重发冲突重发冲突再重发ttttt站1站2站N–1站N…T02345671帧到达T0T0T0T0图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)网络负载(offeredload)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kkGGk(B-2)在上式中，2G是在2T0的时间内的平均到达帧数。于是S=GP[发送成功]=GP[在2T0的时间内有0个到达]GGG20e!0)2(=GG2e(B-3)3.33这就是Abramson于1970年首次推导出的ALOHA吞吐量公式。当G=0.5时，S=0.5e10.184。这是吞吐量S可能达到的极大值。这点从图B-3的吞吐量曲线可以看得很清楚。用求极值的方法也可很容易地得出这一结论。0.200.100.51.01.52.00GS(G,S)不稳定区域0.184图B-3纯ALOHA的吞吐量与网络负载的关系曲线(B-3)式是在假设系统工作在稳定状态下推导出来的。然而图B-3所示的曲线在G值大于0.5呈现负的斜率，因而这段区域是不稳定的。关于这点可做如下解释。设系统工作在G0.5的某一个点上(G',S')。假定现在由于某种原因使网络负载G增大了一些。根据图中的曲线，吞吐量应下降。这表明成功发送的帧数减少而发生碰撞的帧数则增加。这种情况就引起更多的重传，因而使网络负载G进一步增大。这样恶性循环的结果，使工作点迅速沿曲线下降，直到吞吐量下降到零为止。这时，网络负载达到很大的数值。数据帧不断地发送、碰撞、重传……，但是并无有用的输出。整个系统完全不能工作了。可见，在纯ALOHA系统中，网络负载G一定不能超过0.5。一个理想随机接入系统的吞吐量S的极限值是1。但纯ALOHA的吞吐量的极大值只能达到理想值的18.4%。实际上为安全起见，纯ALOHA的吞吐量S不应超过10%。为了提高ALOHA系统的吞吐量，在纯ALOHA出现之后又有了多种改进的ALOHA系统。虽然如此，在许多情况下，当需要进行突发式的交互性的数据通信时，采用纯ALOHA这样的方式可能既简单又便宜。当年夏威夷大学进行的实验也正是为这种环境而设计的。现在假定许多异步终端通过多点线路连到主机，线路的数据率为4800b/s。设每份报文有60个字符，而用户用键盘输入一份报文需2分钟(包括思考时间)。再设每个字符用10bit进行编码，则每个终端的平均数据率仅5b/s。如采用ALOHA方式，取S=0.1，即仅利用信道容量的10%，则信道的总数据率为480b/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4T0T0RT0RT0T1RT0tKT0T2冲突重传(时延最小)冲突再重传(时延最大)图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站2T0T0tt帧到达帧到达帧到达帧到达图B-5时隙ALOHA的工作原理现在推导时隙ALOHA的吞吐量公式。吞吐量S与网络负载G的定义与纯ALOHA的相同。参阅图B-5。设一个帧在某个时隙开始之前到达。显然，此帧能够发送成功的条件是没有其他帧在同一时隙内到达。因此，S=GP[发送成功]=GP[在T0的时间内有0个到达]=GGGe!0)(0=GGe(B-7)3.35此公式为Roberts在1972推导出来的。当G=1时，S=Smax=e10.368。图B-6画出了(B-7)式表示的曲线。为便于比较，纯ALOHA的吞吐量且也画在同一坐标中。可以看出，对于时隙ALOHA，不稳定区域位于G1的部分。0.51.01.52.02.500.100.200.300.40SG0.3680.184时隙ALOHA纯ALOHASGGeSGGe2图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(时隙ALOHA)(B-9)若K不是很大，NR将与K有关，其关系的计算相当复杂，此处从略。实际上，只要K5，(B-4)式和(B-8)式都还是相当准确的。K的大小对帧的时延有很大的影响。K太大会使时延增大。但K太小又会使重传时的碰撞机会增大，这反而会增加重传次数。可见存在一个最佳的K值。但帧的时延对K值的选择并不灵敏(只要S不是太接近于极限值)。一般可取K=5。图B-7画的是两种ALOHA的归一化的帧平均传输时延D/T0与吞吐量S的关系曲线。这是在忽略传播时延并令K=5的条件下得出的。从两条曲线的对比可看出，当吞吐量很小时，纯ALOHA的性能要稍好一些。但当吞吐量增大时，纯ALOHA的时延会急剧上升(尤其是当S接近于0.18时)，而对时隙ALOHA却可以在更高的吞吐量下工作。0.10.20.30.401234D/T0S时隙ALOHA纯ALOHA5图B-7帧的平均传输时延与吞吐量的关系曲线(无传播时延，K=5)最后还要强调一下，这两种ALOHA的吞吐量公式的推导，