随机多址协议讲稿.doc

6 随机多址协议6.1 随机多址协议的概述 70年代，诺曼艾布拉姆森（Norman Abramson）和他的伙伴在夏威夷大学设计出一种新的解决信道分配问题的方法。他们的成果后来被许多研究者所扩充（艾布拉姆森1985）。尽管艾布拉姆森的称为ALOHA系统的这项成果是以地面无线电为基础的，但其基本思想却适用于有多个彼此无协调关系的用户竞争单一共事信道使用权的任何系统。6.1.1 纯ALOHA与时隙ALOHA 纯ALOHA系统的基本思想很简单：让用户什么时候有要送的数据就什么时候发送。当然会有冲类，而遭遇冲突的帧受到破坏。但是根据广播的反馈性质，发送者总可以靠监听信道输出来弄清它发出的帧是否遭到破坏。在LAN情况下，这种反馈是即刻的，但在卫星环境等无线信道下。要经过长（卫星270毫秒）延迟之后发送者才知道发送是否成功。如果发送的帧受到破坏了，发送者就要等待某个随机时间之后再次发送。等待时间必须是随机的，否则相同的帧必然以整齐的步伐二次又一次地反复冲突。在一个系统中，多个用户以一种会导致冲突的方式共享一个公共信道何群的系统被广泛称为争用系统（contention system）。 在一个ALOHA系统中，一般假设所有帧都具有同样长度，因为ALOHA系统的吞吐量是在统一帧长情况下而不是有多种帧长的情况下达到最大。 每当有两个帧企图在同一时刻占据信道，就产生冲突，两个帧都被破坏。必须认识到，一个新帧的第1位与要快结束的一帧的最后位相重叠，这两个帧也算全破坏了，因而这两个帧必须都得稍后重发。校验和不能（也不应该）区分是全部丢失还是丢失一点点。 最令人感兴趣的是ALOHA信道效率如何？也就是混在这样混乱环境中，发送出的所有帧中逃脱冲突的帧占多大比例？首先让我们考虑说限多交互式用户集合都坐在她们的终端（站）旁。用户总是处于两种状态之一：发送与守侯。一开始，所有用户都处于守侯状态之中。当某个用户决定进行下发送时，发送数据帧，并检查信道，看这帧是否发送成况一如果成功了，返回守侯在状态。如果没成功，重发这个数据，直到发送成功为止。 这里我们假设无限多普通用户产生新分组都符合泊松公布，每“时隙”平均S分组。（为了确保在用户变为发送状态时S不至于减少，上述“无限”的假设是需要的）。 除了产生新帧之外，新到达和重复发送的数据综合起来每“时隙”中总的数据由些变化，每“时隙”平均为G。显然GS。在低负荷情况下（即G和S都很小），冲突很少，因而重发也很少，所以GS。在高负荷情况下，情况不同了。图6-1 随机接续过程示意图 如果分组数据长度时T，则在T时间内到达的分组数可以用破送分布表示：，对于随机ALOHA系统莫如图6-1所示，在2T时间内部只能到达一个分数，否则会发生碰撞，而导致数据分数的破坏。信道的利用率可以这样得到，在2T时间内到达1个数据分组的概率为：，而且要保证在2T时间结束本此数据传输，因此要求，在2T时间内到达一个分组，分组的数据头必须在第一个T时间 内。而分组数据的头在第一个T内的概率为0.5（均匀分布）。所以信道成功传输的概率为：（6-1）最大数值为；另外一种方法是连续观测信道，统计第一个T时间备到达一个分组，第二个T时间内没有分组到达或第一个T时间内没有分组，第二个T时间到达1个的概率为，这两种情况的概率和为1，所以信道利用率1公式相同。 当系统不是纯ALOHA，而是采用统一的时隙结构的时候，信道利用率可以从也可以使用6.1，但是时间不是2T。而是T，也 没有1/2的系数，因此信道利用率为：（6-2） 最大数值为1/e=0.367。6.1.2 局域网络协议 使用时隙ALOHA nd利用率最好可达到1/e。这毫不奇怪，因为各站都随意发送，从不顾及其它站在干什么，因而必定发生许多冲突。但是在局域网络中，各站可以检测其它站正在干什么，从而决定相应的操作。 1. 持久的与非持久的CSMA 各站用于监听载波（即传送）和活动的协议称为载波监听协议CSMA。 第一个载波监听协议是1率永久CSMA（载波监听多重访问Carrier Sense Multiple Access）。当有一个站有数据要发送时，首先听一听信道是否有其它站正在传送。如果信道忙，则这个站就等着，直到该站变为空闲。当信道检测到信道空闲时，它就传送一帧。如果发生冲突，这个站就等待一定随机时间，然后再完全重新开始。这个协议称为1率永久协议是因为各站在发现信道空闲时才发送，概率为1。 传播延迟严重影响这种协议的性能。很少有这样的可能：就在一个站刚开始发送之后，另一个站就准备好发送，并监听信道。如果第一个站的信号尚未到达第二个站的时候，第二个站检测出信道空闲，于是也开始发送，结果造成冲突。传播延迟越长，这种影响变得越严重，因而协议的性能越坏。 即便是传播延迟为零，还会有冲突。如果有两个站都在第三个站传送过程中准备好发送，两个站都“很礼貌”地一直等到传送结束，然后准确地同时开始发送，结果还是发生冲突。如果它们不是这样急切，冲突就会少些。即使这样，这个协议还是比纯ALOHA好得多。因而两个站因为受第三个站传送帧的干扰而不能发送的可能性要小得多。直观看来，这比纳ALOHA的性能要好。严格说来，与时隙ALOHA的性能相同。 第二种载波监听协议称为非永久CSMA（nonpcrsistent CSMA）。在这种协议中，发送尝试比较有节制，不像前种协议那么急切。某站在发送以前要监听信道。如果没有其它站正在发送，这个站就开始发送。但是，如果信道已在使用之中，这个站不是为了测出传输结束立即 捉住信道而连续监听信道，而是等待一定随机时间周期之后再重复发送操作。直观看来，这种方法比工率永久CSMA的信道利用率要好，延迟也要长些。 最后一种协议称为p李永久CSMAo这种协议用干时隙信道，工作如下。有一个站准备好发送时，就监听信道。如果信道空闲，该站就以概率p发送。若概率为q=l-p，就推迟到下个时隙。如果那个时隙也是空闲的，这个站要么发送，要么再次推迟，概率分别p和q。这个过程一直重复下去，直到有一个帧发出来，或者其它站已经开始传送。在后一种情况下，其作用好象产生一次冲突（即要等待一定随机时间，然后再开始）。如果这个站一开始就监听到信道繁忙，它就等到下个时陡然后使用上述算法。图6-2 不同控制算法的信道利用率 2. 带有冲突避免的CSMA 虽然永久的和非永久的CSMA都是对ALOHA的改进协议，因为都能保证在监听到信道忙时没有站开始发送。另一种改进是对各站而言，当它们检测到冲突，立即把它们的发送动作废掉。换句话说，如果两个站都听到信道空闲，因而同时开始发送，它们俩使几乎立即都检测到冲突。不要等到发送完毕，因为发送的帧已破碎得不可恢复，要一旦检测到冲突就立即停止发送。迅速结束损害的帧可以节省时间和带宽。这种协议就是著名的CSMACD（带有冲突检测的载波监听多重访问Carrier Sense Multivle Access with Collision Dection），并且在LAN中的MAC层得到广泛应用。 3. 其他协议 使用CSMA/CD在有一个越明确占有信道期间不会出现冲突，但在争夺期间还可能出现冲突。这些冲突对系统性能产生有害的影响，尤其在电缆长（即r很大）而帧短的情况下。由于长度长而频带宽的光纤网络投入使用，把大r与短帧结合起来也不会产生严重问题。本节与下边几节讨论一些协议，这些协议解决信道完全摆脱冲突的问题，甚至在争夺期间也不发生冲突。例如，轮询是在控制下的无冲突协议。此外还有有限冲突协议。可以阅读参考书6.2 分组数据业务量分析以及参数估计6.2.1 数据业务量分析 本节以动态时隙为基础分析时隙协议算法的计算和估计过程。 下面分析首先假设信道上是简单流，归一化强度为，信道接续方式为时隙ALOHA协议，在长为N时隙的一帧中有Ne个空闲时隙、Ng个碰撞时隙、Ns个成功时隙，Ns代表执行业务量，但Ng不能代表损失业务量，因为碰撞时隙的碰撞数量未知。现假设第i个时隙碰撞，在本帧开始前的时间是T，则K个用户选择第i个时隙的概率为：(6-3) 由条件概率rk个用户发送|碰撞=，对所有碰撞时隙的呼叫数均值可表示为(6-4) 每一个时隙呼叫数均值为(6-5)如果系统工作在最佳条件下，T应为，即每个时隙的呼叫数均值为，此时系统的容量达到最大。在此条件下碰撞时隙的呼叫均值应为：(6-6)这时得出无干扰条件下信道的业务量指标，设帧长为N流入业务量(6-7)执行业务量0Ns/N(6-8)损失业务量-0(6-9) 当信道有干扰存在时，此时观测到的碰撞时隙一部分是真正碰撞所至，所以观测到的碰撞概率与真正碰撞概率的关系可以表示为： (6-10) (6-11)其中P(A|i)表示有i个用户发送发生碰撞的条件概率，此条件下的碰撞时隙的呼叫数均值为:，由此式来计算信道上的业务量，真正的碰撞的呼叫数是Ng=。 如果信道上发生捕获现象，观测到的成功概率是，真正一个时隙只有一个分组的概率为，则与的关系可以表示为：(6-12)则在成功时隙中单一用户的概率Ps为：(6-13)其中,P(B|i)表示i个用户发送发生捕获的概率。此时系统的执行业务量0 Ns/N(6-14)流入业务量：(6-15)损失业务量：(6-16)6.2.2 非理想信道信令业务量分析及参数估计 在一个实际的系统中，信道不可能是理想的，信道上有噪声和捕获效应，系统应考虑到这些情况并有相应的处理能力。在非理想条件下，系统的观测情况与实际情况是有差异的，下面的讨论要解决的问题是从观测到的结果来估计系统的真实运行情况，以保证系统动态控制的正确。 假设在一个系统的覆盖区域内，设g(r)是话务流的密度函数，r为用户到基地台的距离，则在0r范围内的业务量G(r)为：(6-17) r的空间分布函数和密度函数为：(6-18)(6-19)当时(6-20)(6-21) 在我们设计的实际系统中，(n,k)线性分组码编码格式，系统的误码率为Pb，令Pbc为数据解码的误码率，则Pbc可以由下面计算 (6-22) d为最小码距，t=INT(d-1)/2，采用(n,k)线性分组码。对一般的陆地移动通信系统，正确接收的概率Pc为：(6-23)对所有可能的位置求Pc的均值 (6-24) 由信道流入强度可求得捕获的概率为：P(正确接收|碰撞)(6-25)其中Ps|i=P(正确接收|i个用户发送)，P(i)是i个用户选择本时隙发送的概率。 对接收失败时隙有： P(用户数大于1|接收失败)(6-26)其中P（error|k)是有k(k2)个用户发送而接收错误的概率。 用同样方法求得Ps(一个用户发送|发送成功)的值Ps(一个用户|发送成功)=(6-27) 在上述计算过程中，要依赖信道的捕获概率和碰撞概率，而这些值又与信道流入参数有关。实际上如果知道信道流入参数，也就得到了信道流入业务量，所以如果用某一点的捕获概率和碰撞概率数值进行信道估计，显然不仅不知道误差而且对信道变化没有适应能力。这种方式在实际工程应用中是不适用的，并且计算量大。 对于我们设计并已经投入使用的集中控制式系统，应用了另外一种参数估计算法，这种方法对信道的捕获和噪声影响合并考虑，用对一段时间内的数据帧进行观测，来决定系统的流入强度等动态控制参数，这种方法在实际应用中简便易行并回避了对捕获概率和碰撞概率的计算。令PsN(i)是长度为N个时隙的帧中有i个时隙成功传送的概率，PgN(i)是长度为N个时隙的帧中有i个时隙碰撞的概率，PeN(i)是长度为N个时隙的帧中有i个时隙空闲的概率，在一帧中成功、碰撞、空闲的时隙的期望值分别是： (6-28) (6-29) (6-30)图6-3 各种时隙期望值随流入强度的变化曲线 图6-3给出了这三个期望值对帧长N的归一化数值，可以证明，(6-30)，(6-29)式为单调函数，当观测到Ng和Ne后，可以求得g和e，由(6-28)可以求得s1和s2，且s1s2，在理想信道条件下，应有ges1，可以认为系统此时的话务流入强度为。 当系统有干扰时，可导致平均碰撞数上升，平均成功时隙数下降，这将导致s1和g之间差值增大，由此可以判断信道受干扰的程度。由于噪声干扰使得一些本应成功传输的分组同步头出错而丢失或信息段错误比特过多而判别为碰撞时隙，这两部分各占一定的比例，信道干扰程