当802.11WLAN网络上的数个装置同时传送数据时,由于频宽的限制,会发生“封包碰撞”(collision)的情况。一般以太网络是使用“指数回归算法”(exponential backoff algorithm)来解决这种问题,而802.11标准也不例外。802.11的MAC标准称作“分布式基础无线媒体撷取控制”(distributed foundation wireless MAC;DFWMAC)。
如果真要自行设计“专属的WLAN”,必须先行克服从射频实体层至MAC层的通信协议问题。假设他们已经具有很纯熟的27MHz无线电传收机技术,则剩下的就是要解决MAC层的通信协议问题,这主要包含两个重要的问题:CSMA/CA和回归(backoff)。当然,除此之外,RTS/CTS流量控制和“分布式协调功能(distributed coordination function;DCF)”,以及更上层的驱动程序、应用软件、各通信层之间的接口….等,都要严格考虑在内。不过,本文将专注于回归技术的探讨。
碰撞的问题
当两台装置同时开始传送数据时,它们将会先检查缆线中是否有载波存在,若载波有存在,而且缆线是处于闲置状态,它们就会马上传送封包。因为它们所发射的电子信号会彼此干扰,这种干扰会造成“封包碰撞”的结果。碰撞会使封包内的数据混淆不清,致使接收到的封包无法还原成正确的数据。
虽然,CSMA/CA和回归都能解决碰撞的问题,不过,在功能上,它们是有差别的。CSMA/CA是一种“竞争”(contention)通信协议,它倾听WLAN网络,避免碰撞发生。它和传统的CSMA/CD(被以太网络使用)不同,CSMA/CD是在碰撞发生之后,才起来处理后续的传送作业。CSMA/CA则是防患未然,所以比较有助于网络通信。因为它在任何真正的数据被传送之前,会先在网络上广播(broadcast)一个信号,倾听是否有碰撞发生,同时告诉其它装置不要广播。
当发生碰撞时,装置必须等待一段时间,等缆线恢复闲置时,才能再传送。不过,若两个装置
同时再次发射信号,则另一个碰撞又将再次发生。为了避免这个情况发生,就必须采用“二进制指数回归算法”来解决。
当802.11 WLAN网络上的数个装置同时传送数据时,由于频宽的限制,会发生“封包碰撞”(collision)的情况。一般以太网络是使用“指数回归算法”(exponential backoff algorithm)来解决这种问题,而802.11标准也不例外。802.11的MAC标准称作“分布式基础无线媒体撷取控制”(distributed foundation wireless MAC;DFWMAC)。
如果真要自行设计“专属的WLAN”,必须先行克服从射频实体层至MAC层的通信协议问题。假设他们已经具有很纯熟的27MHz无线电传收机技术,则剩下的就是要解决MAC层的通信协议问题,这主要包含两个重要的问题:CSMA/CA和回归(backoff)。当然,除此之外,RTS/CTS流量控制和“分布式协调功能(distributed coordination function;DCF)”,以及更上层的驱动程序、应用软件、各通信层之间的接口….等,都要严格考虑在内。不过,本文将专注于回归技术的探讨。
碰撞的问题
当两台装置同时开始传送数据时,它们将会先检查缆线中是否有载波存在,若载波有存在,而且缆线是处于闲置状态,它们就会马上传送封包。因为它们所发射的电子信号会彼此干扰,这种干扰会造成“封包碰撞”的结果。碰撞会使封包内的数据混淆不清,致使接收到的封包无法还原成正确的数据。
虽然,CSMA/CA和回归都能解决碰撞的问题,不过,在功能上,它们是有差别的。CSMA/CA是一种“竞争”(contention)通信协议,它倾听WLAN网络,避免碰撞发生。它和传统的CSMA/CD(被以太网络使用)不同,CSMA/CD是在碰撞发生之后,才起来处理后续的传送作业。CSMA/CA则是防患未然,所以比较有助于网络通信。因为它在任何真正的数据被传送之前,会先在网络上广播(broadcast)一个信号,倾听是否有碰撞发生,同时告诉其它装置不要广播。
当发生碰撞时,装置必须等待一段时间,等缆线恢复闲置时,才能再传送。不过,若两个装置
同时再次发射信号,则另一个碰撞又将再次发生。为了避免这个情况发生,就必须采用“二进制指数回归算法”来解决。
回归的概念
在碰撞之后,再次尝试发射信号之前,每一个传送装置必须等待一段时间。不过,如果它们的等待或延迟时间都一样,则下次还是会有碰撞发生。因此,每个装置必须选择一个0到D的随机数,当成必须等待的时间长度。D是标准的延迟时间值。若又发生碰撞,则每个装置会将之前所选择的随机数大小加倍,这表示现在的随机延迟时间是在0到2D之间。如果又有另一个碰撞发生,则延迟范围将在0到4D之间。以此类推。每碰撞一次,随机延迟时间会以指数增加,所以下次会发生碰撞的机率将会大幅降低,而且重复回归所花费的时间很短,可以忽略不计。
802.11的回归机制
802.11/DFWMAC的回归机制和以太网络的不完全一样,因为前者还牵涉到DCF。DCF是以CSMA/CA为基础的通信协议。DFWMAC整合了两个协调功能—PCF和DCF。PCF支持同步数据传输,DCF支持异步数据传输。这两个模式共享媒体频宽,以多时分工(time-multiplex)的方式,将彼此的数据组合成一个“超大讯框(superframe)”的结构。
利用讯框之间不同的间距(interframe space;IFS),DCF和PCF可以并存。由于具有PCF的桥接器(AP)的IFS比较小,因此它的通信优先级会比处于DCF模式中的工作站高。所以,AP可以在CSMA/CA网络上建立一个超大讯框。
在没有AP装置的WLAN网络环境之中,存取数据要靠DCF。一旦媒体闲置了一段特定的时间(DIFS),并且可以在“竞争窗口”(contention window;CW)的大小范围内,选择一个随机的回归值当成延迟时间。竞争窗口或回归时间都是被分割成数个时槽(slot),每个时槽至少要包含:发射机开启所需的时间+媒体传播所需的时间+侦测忙碌的媒体所需的时间。每个时槽的大小和实体层非常有关。
选择最小延迟时间的工作站,将是最早存取媒体的;其它工作站则暂停它们的回归定时器,等待别人传送完毕;而且,在下一个周期内,继续等待所剩余的延迟时间。通常,已经等待很久的工作站,会比刚加入的工作站,能更早存取媒体。等待的时间愈久,获得存取权的机率就愈高。碰撞只发生在两个或更多个工作站选择了相同的时槽的时候。若持续发生碰撞,它们必须重新竞争,并使用以指数增加的CW值,亦即,2倍的CW、4倍的CW、……,直到最大的CW限制值。
碰撞机率的分布
下面我们来探讨一下DFWMAC的碰撞机率。不过,不对碰撞问题做完整的数学分析,只针对它的性质,做判定和说明。仔细检视CW,和从CW选出的一个时槽的机率:假设有许多个工作站一起竞夺媒体的存取权,刚开始时,这种设计会使回归时间的机率函数呈现平均分布,每一个时槽的被选中机率是相同的。
在第二个周期之内,假设有一个工作站A获得存取权,其工作站在工作站A开始发射信号之前都会等待或延迟,假设这个延迟时间是CWselected—这就是前面所介绍的“随机延迟时间”。现在,剩下的“竞争窗口”是从0到CW-CWselected,剩余的工作站(除了工作站A以外的其它工作站)在0到CW-CWselected的范围内竞争。这范围内的时槽的被选中机率也是相同的,因为它们是重新进行竞争之故。
如果这时有一个新工作站加入竞争;或者在前一个周期内,有两个或以上的工作站发生碰撞,它们将会在CW或2倍的CW或数倍的CW中选择时槽,它们选择时槽的机率应该是较小的。直觉上,新进者本来就要等久一点才能获得存取权;至于发生碰撞的工作站的获得存取权之机率,应该比新进的工作站的获得存取权之机率少一半才对。不过为了便于说明,这里将新进的工作站和发生碰撞的工作站视为同类;此时,它们的机率都远小于其它剩余工作站的机率;而它们的机率的些微差异是可以省略不计的,其中,时槽超过CW-CWselected范围的被选中机率,远低于从0到CW-CWselected范围内的时槽被选中机率。请注意,实际上,新进的和碰撞重来的工作站之时槽被选中机率,占有0到CW-CWselected和CW-CWselected的完整CW范围。
假设WLAN处于高负载的情况(一直有工作站离开,也一直有工作站加入竞争,且离开和加入的数量是均衡的),这时,可以发现位于CW前面的时槽(即较早生成的时槽),具有比较高的被选中机率。因此,时槽的被选中机率是一个递减的阶梯函数(staircase function)。
不过,这会导致一种我们很不想看到的现象:愈可能被选中的时槽,也愈可能被选中两次或更多次,所以它发生碰撞的机会也愈高。为了尽量避免碰撞的发生,应该使每一个时槽的分布机率维持相等。
改良的回归机制
为了解决上述的问题,有许多方法可以采用。其中一种方法是,令剩余的工作站于每个周期,在完整的CW内,选择一个新的随机回归时间。不过,这可能会造成某一个工作站都一直在等待存取的机会,因为此方法并没有限制最大的等待时间。底下分别以两种方法来解决这个问题,它们都企图将新进的工作站和前一次竞争失败的(剩余的)工作站之机率区分开来。这两种方法是:加权的选择机率、负载自适性(load adaptive)选择。为了追求精确和精致,必须使用简要的数学观念和方程式来说明它们。