计算机网络ALOHA.docx
《计算机网络ALOHA.docx》由会员分享，可在线阅读，更多相关《计算机网络ALOHA.docx（10页珍藏版）》请在冰点文库上搜索。
计算机网络ALOHA
ALOHA
ALOHA是世界上最早的无线电计算机通信网。
它是1968年美国夏威夷大学的一项研究计划的名字。
70年代初研制成功一种使用无线广播技术的分组交换计算机网络，也是最早最基本的无线数据通信协议。
取名ALOHA，是夏威夷人表示致意的问候语，这项研究计划的目的是要解决夏威夷群岛之间的通信问题。
Aloha网络可以使分散在各岛的多个用户通过无线电信道来使用中心计算机，从而实现一点到多点的数据通信。
Aloha-背景
ALOHA系统模型
第一个使用无线电广播来代替点到点连接线路作为通信设施的计算机系统是夏威夷大学的ALOHA系统。
它始建于1971年，这个系统所采用的技术是地面无线电广播技术，采用的协议就是有名的ALOHA协议，叫做纯ALOHA（PureALOHA）。
以后，在此基础上，又有了许多改进过的ALOHA协议被用于卫星广播网和其它广播网络。
从通信的角度来说，地球同步通信卫星相当于在太空中安装了一个固定的微波转播台，由它与地球上的卫星地面站进行互相通信，或者通过地球通信卫星上的转发器，实现地面站之间的通信，已经出现了频分多址存取（FDMA）、时分多址存取（TDMA）、码分多址存（CDMA）和空分多址存取（SDNA）等多种技术的通信方式。
九十年代是移动通信大发展的年代，它的迅速发展基于以下几个方面原因：
*用户迫切希望能随时随地与对方直接、收集各种信息、处理紧迫问题。
*移动通信设备的集成化、小型化使设备的重量、尺寸减小到可以随身携带，方便。
.技术的不断改进，价格的不断下降。
*可覆盖常规通信设施不能到达的地区，甚至在城市间漫游。
移动通信的发展已迅速经历了第一代、第二代的演变并出现了第三代移动通信。
第一代的代表是运用模拟通信技术，但在新业务的发展和新技术的应用方面，受到一定的限制。
随着通信网的数字化，出现了以数字蜂窝移动通信技术为代表的第二代通信。
移动通信的数字化可以使电路集成度进一步提高，因而体积、重量进一步减小，价格也更为便宜，更重要的是除了通话之外，还可接通传真、图文和高速数据通信可以接入计算机网，还可以进入综合业务数字网（ISDN），适应各种新的通信业务的发展。
此外移动通信的主题就是“个人通信”，设备的体积、重量更趋小型化，桌上的电话机将转变为小总机，均匀分布于各楼层、各街道及公共场所，移动电话机将变得象计算器、钢笔和手表一样。
随身携带的袖珍机通过分布式的任何一个小总机就可接入通信网，随时随地进行通信，这将是电话通信的一次革命，有人称之为“最理想的通信”。
Aloha-分类
时隙ALOHA吞吐量
ALOHA协议分为纯ALOHA和时隙ALOHA两种。
1、纯ALOHA
ALOHA协议的思想很简单，只要用户有数据要发送，就尽管让他们发送。
当然，这样会产生冲突从而造成帧的破坏。
但是，由于广播信道具有反馈性，因此发送方可以在发送数据的过程中进行冲突检测，将接收到的数据与缓冲区的数据进行比较，就可以知道数据帧是否遭到破坏。
同样的道理，其他用户也是按照此过程工作。
如果发送方知道数据帧遭到破坏（即检测到冲突），那么它可以等待一段随机长的时间后重发该帧。
对于局域网LAN，反馈信息很快就可以得到；而对于卫星网，发送方要在270ms后才能确认数据发送是否成功。
通过研究证明，纯ALOHA协议的信道利用率最大不超过18.4%（1/2e）。
纯ALOHA协议的工作原理和特点
工作原理：
站点只要产生帧，就立即发送到信道上；规定时间内若收到应答，表示发送成功，否则重发。
重发策略：
等待一段随机的时间，然后重发；如再次冲突，则再等待一段随机的时间，直到重发成功为止
优点：
简单易行
缺点：
极容易冲突
竞争系统：
多个用户以某种可能导致冲突的方式共享公用信道的系统
纯ALOHA协议性能分析
T0帧的发送时延
吞吐量S 在帧的发送时间T0内成功发送的平均帧数
网络负载G在T0内总共发送的平均帧数（包括发送成功的帧和因冲突未发送成功的帧）。
则：
吞吐量S=G*e-2G
极大值为G=0.5时，S=0.184
2、时隙ALOHA（S-ALOHA）
1972年，Roberts发明了一种能把信道利用率提高一倍的信道分配策略，即时隙ALOHA协议。
他的思想是用时钟来统一用户的数据发送。
办法是将时间分为离散的时间片，用户每次必须等到下一个时间片才能开始发送数据，从而避免了用户发送数据的随意性，减少了数据产生冲突的可能性，提高了信道的利用率。
在时隙ALOHA系统中，计算机并不是在用户按下回车键后就立即发送数据，而是要等到下一个时间片开始时才发送。
这样，连续的纯ALOHA就变成离散的时隙ALOHA。
由于冲突的危险区平均减少为纯ALOHA的一半，因此时隙ALOHA的信道利用率可以达到36.8%（1/e），是纯ALOHA协议的两倍。
但对于时隙ALOHA，用户数据的平均传输时间要高于纯ALOHA系统。
时隙ALOHA和纯ALOHA比较
时隙ALOHA的工作原理
基本思想：
把信道时间分成离散的时间槽，槽长为一个帧所需的发送时间。
每个站点只能在时槽开始时才允许发送。
其他过程与纯ALOHA协议相同。
信道效率：
冲突危险区是纯ALOHA的一半，所以P0=e-G，S=Ge-G；与纯ALOHA协议相比，降低了产生冲突的概率，信道利用率最高为36.8%。
重发策略：
同纯ALOHA，等待一段随机的时间，然后重发；如再次冲突，则再等待一段随机的时间，直到重发成功为止。
代价：
需要全网同步；可设置一个特殊站点，由该站点发送时钟信号
时隙ALOHA协议性能分析：
T0 一个数据帧的发送时间
吞吐量S 在帧的发送时间T0内成功发送的平均帧数
网络负载G在T0内总共发送的平均帧数（包括发送成功的帧和因冲突未发送成功的帧）。
则：
吞吐量S=G*e-G
极大值为G=1.0时，S=0.368
Aloha-组成
ALOHA时隙
ALOHA网的组成框图，可以把它分为五个部分。
（1）用户终端：
包括智能终端和简单终端。
（2）用户接口:
执行通信控制部件,例如终端控制器。
集中器。
用户终端和用户接口组成节点。
（3）无线电通信子系统:
由各端收发信机及转发器组成通信子网。
（4）通信处理机（IMP）:
位于中央节点,处理用户访问和通信控制。
（5）网络资源：
包括本地各台主机以及其他网络。
中央IMP与网络资源组成中央节点。
经过TIP（是ARPA网的终端接口处理机），中央IMP可与ARPA网的IMP（接口信息处理机）相连接，使ALOHA网的用户终端可访问其他网终的资源。
ALOHA网有两种通信方式：
广播和竞争。
从中央节点发送信息到各用户节点，采用广播方式，在UHF频带区使用413.475MHz的频率，占用100KMz的信道，中央IMP发送的任何信息，正常情况下各用户终端控制器都能到。
从各用户节点到中央节点，采用随机的竞争方式，以407.350MHz的频率，也占用100KHz信道。
如果各用户不同时发送信息，IMP可以正确收到;如果各用户同时发送信息，则会发生冲突，使信息不可识别，必须考重发。
显然，信息的冲突会降低传输效率。
但是考虑到各用户的数据报文较短（即占用信道时间较短），发送信息的性带有突发性和断续性，因此这种随机性访问网络方式还是可行的。
Aloha-访问方式
ALOHA访问方式
网络中多个用户共用一个信道，因此采用竞争方式，各自随机地访问中央系统。
由于产生冲突现象，使传输效率或网络的吞吐率降低。
（1）纯ALOHA法（Pure--ALOHA）
发送站向网络传送的报文分组内，包含目的地址和源地址，并在发送起动计时器，根据在一预定时间内有没有得到接收应答信号来判断这个报文分组是否安全到达目的地。
对用户的发送，不加以限制，就很容易发生冲突，造成重发报文组。
发生冲突以后，有两种解决措施。
一种办法，是给每个用户规定一个互不相同的重发时延，即根据优先程度给予用户重发权利，达到避免再次冲突。
另一种办法，是对每个用户随机地选取重发时延，例如时延可在0。
2s到1。
5s的范围内选取。
当然，最小时延应考虑用户收到来自中央IMP的确认（ACK），如果太短的话，用户因可能尚未收到ACK而执行不必要的重发。
传输效率一般以单位时间内传输的有效信息量与额定的信道容量之比值来表示，以此衡量各种访问网络方法的性能。
纯ALOHA法的传输效率较低，约有18.4%。
（2）时间片法（Slotted--ALOHA），又称开糟ALOHA法
通过划分相等的时间片，每个时间片对于一个帧，指定用户在每个时间的开始端发送信息，不允许终端在任何时候发送，由于强加这一种限制，减少了时间片内中间冲突的概率，并且，如果在开始端发生冲突，也只会浪费这个时间片。
每个时间片的长度，要合理设计。
因为从各个用户的报文分组到达中央系统的传输延迟不同，最大的报文分组长度相关于第一个报文分组首部到达时刻与最后一个报文分组尾部到时刻之时间差值，由这个先后到达的时间差值，选择每个时间片的宽度。
对拥有中等数量用户的系统，时间片法的传输效率约为36.8％，如果用户数量效少，传输效率还可提高。
（3）卫星通信ALOHA
如前所述，ALOHA的问题是信道效率低，对于纯ALOHA，只有0。
184效率，即使是开糟ALOHA，也只有0.368（可以通过分析，精确计算而得）。
在卫星通信中也运用开糟ALOHA，分成上行信道和下行信道。
每个信道具有2Bbps分配带宽中的一半，即带宽Bbps，吞吐量将是B/ebps，信道效率就是（B/e）/2B，或者是1/2e，约为0.184。
由于卫星通信要求每个帧都由卫星重新广播，与每个站可以直接听到原发送的ALOHA系统相比，效率只有一半。
如图所示的是具有两个上行信道和一个下行信道的ALOHA系统。
有帧发送的站随机地选择两个上行信道中的一个，在下一个时间片中发送。
每个上行信道就是一个独立的开糟的ALOHA信道。
经分析下行信道的利用率为0。
599。
这一方案所占用的总带宽为3B，吞量为0.599B，所以此方案的效率约为0.20，或者说比只有一个上行道和下行信道的系统效率0.184高9％。
如以具体数据来说明，假设数据发送可用1Mbps带宽，如果按照500kbps为上行信道，500kbps为下行信道来分配，吞吐量最多将为184kbps。
然而如果分配成两个333kbps的上行信道和一个333kbps的下行信道，吞吐量最多将达2o0kbps。
由此可见，有两个上行信道的系统就要比只有一个上行信道和一个下行信道系统有所改进。
不过，在有两个上行信道的系统中如果两帧一起成功地到达了，其中一个必须丢弃，因为只有一个下行信道。
这里可能有两种改进方法：
一种是在卫星上增加存储容量，使得不立即重新广播的帧能够保存起来等待以后的时间片。
另一种是增加下行信道。
从卫星增加存储器的要求而论，需附加能源，这意味着将带入空间更多的太阳电池和更大的重量。
早期的卫星没有任何存储帧和以后重新广播的措施，随着卫星技术的进步，卫星上带存储器更为常见，在以后还开发了具有卫星存储器和多波束的卫星。
Aloha-预约ALOHA
预约ALOHA
预约ALOHA（ReservationALOHA）为了在信道高负载情况下，更好地利用单个共享信道，按照时分多路复用的原理，对每个站预定分配一个时间片，要允许它在相对应的时间片发送报文分组。
根据预约申请和释放的方法之不同可以有以下几种不同形式的预约方案。
第一种是Binder在1975年提出的，如TDM那样，N个连续时间片组合在一起成为一个组，每个站预拥有它自已的时间片位置。
如果时间片数比站点数多，多余的时间片不分配给其它任何站点。
如果一个时间片的拥有站不想在当前的组中使用它，就不做任何事，此时间片就成为空时间片。
空时间片是给其它任何站的一个信号，表明拥有者没有通信量。
在下一组中，这个时间片就在竞争的基础上，为所有想用的站所争用。
如果拥有者想恢复他的时间片，他发送一个帧，这样强加了一个碰撞（如果有其它通信的话）。
在碰撞之后，除了拥有者外的其它站必须停止使用该时间片，这样拥有者总是可以在不超过两个组的时间内开始传送。
在每次碰撞之后，碰撞者必须避开一个组以观察拥有者是否想要收回那个时间片。
这个方案的微小不足处是：
每当一个时间片的拥有者不想用，这个位置必须在下一组中空闲以表明其拥有者不用它。
为了消除这种浪费掉的时间片，可以在所有帧的头部附加一位来通知别人，其拥有者在下一组中有没有数据。
然而另一严重问题在于用户数必须事先知道，否则，当这种情况发生时的仲裁是：
每个用户分配给一个优先级，在冲突时低优先级服从高优先级用户。
第二种是Crowther等人在1973年提出的，适用于知站点数目点和站点数动态改变的情况。
在此方法中，时间片没有永的拥有者，而每当一个发送成功，就给予这个发送站在下一组中也使用此时间片的权利。
这样，在一个站有数据发送期间，它可以无限期地连续这样做。
既然所有的站点为不可能同时有长数据发送，这种方法甚至当每组时间片数远于站点数时也可工作。
在本属上，这种方法是一种开糟ALOHA与TDM的动态混合，让专用于每个站的时间片数量随着要求变化。
在一个有8个时间片的组中，初始时，E使用最后一个时间片，但是两个组以后，它不再需要。
此时间片空闲了一个组后，D获得了该时间片并且一直保持到完成。
第三种是Roberts方案，要求站点在发送前先申请。
每个组包含一个特别的时间片，它被分割成V个小的子时间片用于预约。
当一个站想要发送数据，它就在其中某一个预约子时间片内广播一个短的申请帧，然后下一个规则是时间片（或一些时间片）就被预约。
在所有的时候，每个站都必须保持一个队列长度的轨迹（预约时间片数），使得当任何一个站作一项成预约时，他将知道在发送前应该跳过多少数据时间片。
站不必保留谁排队的轨迹，它们只需要知道队列有多长，当队列长度跌到0，所有的时间片转化预约子时间片，加以速预约过程。
1979年Jacobs等人提出把TDM和上述方法结合起来处理流数据突发数据等两种形式的数据。
他们的协议PODA（PriorityOrientedDemandAssigment）和其它协议一样把时间片集合成组，它保留其中一部分作为数据发送用而其它部分作为预约子时间片。
这两种之间的界限随要求而变。
分配预约时间片有两种策略：
把预约子时间片固定分配给用户，叫做FPOD，或者竞争分配预约子时间片，叫做CPDOA。
PDOA的一个有趣特点是站点通过在数据帧中置某些位来预约的能力，以使重发用户不必等待下一个预约子时间为（FPDOA0），或者去竞争一个预约时间片（CPDOA）。
预约信息包括帧的大小与优先级，可以为单个帧，或为帧流进行预约。
升级会员 