无线局域网的动态切分与重构

许士博　刘晓兰　任丰原

(清华大学计算机科学与技术系　北京 100084)

(xshbo@csnet1.cs.tsinghua.edu.cn)



无线局域网的动态切分与重构

许士博刘晓兰任丰原

(清华大学计算机科学与技术系北京 100084)

(xshbo@csnet1.cs.tsinghua.edu.cn)

Splitting and Restructuring a WLAN Dynamically

Xu Shibo, Liu Xiaolan, and Ren Fengyuan

(DepartmentofComputerScienceandTechnology,TsinghuaUniversity,Beijing100084)

AbstractDue to user mobility and favorite of collective activities, the distribution of users in WLANs is seriously uneven and changeable. When a lot of users congest in a WLAN, the WLAN performance degrades and the user experience becomes worse. To address dynamical congestion in a WLAN, existing solutions are unpractical. In this paper, through introducing shadow access point (SAP) and station mapping, a solution called splitting and restructuring dynamically (SRD) is proposed, and formal analysis of station mapping and performance is conducted, and an algorithm for the optimal mapping is devised. According to the change of WLAN status, SRD can dynamically split an overcrowded WLAN to multiple sub-WLANs and restructure them into a centralized WLAN. So, the distribution of stations in all sub-WLANs can be monitored and controlled centralizedly. SRD can reduce the number of stations in each sub-WLAN, and improve user throughput and alleviate the impact of both collisions and multi-rate. The simulation results show that SRD can improve the WLAN throughput a lot. Besides, SRD requires no modifications on user devices.

Key wordswireless local area network (WLAN); access point (AP); occasionally crowded; shadow AP (SAP); station mapping

摘要因用户的游移和喜好集会活动，用户在无线局域网(wireless local area network, WLAN)中的分布是非常不均匀的且是动态变化的.当1个WLAN的用户数量很大时，整个网络和每个用户的吞吐量都会大幅下降.对于1个WLAN范围内的间歇拥塞问题，已有的性能改进方法存在一些不足.因此，提出了1套WLAN动态切分与重构的方案SRD(splitting and restructuring dynamically)，引入了影子AP(shadow access point, SAP)和终端映射2个概念，并对终端映射和方案的整体性能进行了形式化分析，设计了最优映射的计算方法.该方案能根据网络负载及状态的变化，动态地将1个拥挤的WLAN切分成若干子网，并重构成1个微型的集中式架构的WLAN，从而对各子网中的终端分布进行监控.因此，该方案能大幅减少1个子网中的终端数量，提高用户吞吐量，缓解冲突和异构速率的影响.仿真结果表明，该方案能成倍地提高网络及每个用户的吞吐量，此外，该方案的部署不需要用户终端设备作任何的更改.

关键词无线局域网；接入点；间歇拥塞；影子AP；终端映射

当前，无线接入点(access point, AP)被广泛地部署在很多公共场所，为了以最低的成本覆盖最大的面积，AP的部署在地里位置上一般都是均匀分布的，尤其是那些由运营商、单位、学校、小区统一批量部署的AP.然而，用户在无线局域网(wireless local area network, WLAN)中的分布是严重不平衡且动态变化的.比如,在学校白天用户大都集中在教室和图书馆，就餐时间则会转移到食堂，而晚上又聚集到宿舍.1个更为具体的实例，在2008年ACM SIGCOMM大会上，WLAN活跃用户的数量在5～90之间周期地波动[1].在用户比较拥挤的WLAN中，网络和每个用户的吞吐量都比较低,由于用户不规则的游移，总有些AP会间歇(偶发)地处于拥塞状态.本文的研究重点和目标就是解决小范围内的间歇拥塞问题，即当1个WLAN范围内聚集很多用户时，提升WLAN和每个用户的吞吐量.

在用户很多时吞吐量较差的主要原因有3个：1)每个用户所能分得的传输机会减少；2)随着用户数量的增多，因同时发送引发的冲突增多，影响了网络的性能；3)异构速率(也称为性能异常(perfor-mance anomaly)[2])和异构传输模式的影响，用户越多设备的异构性和传输距离的差异越大，异构速率和异构传输模式的影响也就越大，这进一步降低了网络性能.

学术界为解决以上问题，已有很多的研究和成果.文献[3-4]将移动通信中的小区呼吸技术引入到WLAN中，可以动态地减少1个WLAN中的用户数，以提升每个用户分得的带宽.文献[5-6]使用非分布式协调功能DCF(distributed coordination function)的方法来避免或减少冲突.文献[7-10]分别使用了不同的方法来缓解异构速率的影响.然而，以上所有方法与现有终端设备都是不兼容的，它们需要修改用户的终端设备.由于终端设备大都属于用户个人所有，以上条件在现实中难以得到满足.

在现实中，为缓解间歇拥塞带来的压力，可以临时地部署一些普通AP或移动AP(也称为便携AP).但是，在大部分环境下，AP的连线很不方便.此外，因移动AP的回程链路是移动通信网络，其带宽容量有限且流量收费，主要适用于个人.另一方面，即使临时地部署了一些AP或移动AP，用户在各AP之间的恰当分配也无法实现和保证.已证实，用户在AP间的分配是1个影响WLAN性能的重要因素[3]，因为WLAN的性能不仅与用户的数量有关，还与各用户传输的报文大小、传输速率高低等因素有关.

为提升小范围间歇拥塞情况下网络及用户的吞吐量，本文提出一套无线局域网动态切分与重构的方案SRD(splitting and restructuring dynamically).该方案的核心思想是将1个WLAN重构成1个微型的集中式(centralized)架构的WLAN，通过动态地调整其拓扑结构来保持最优的性能.因为现有的AP无法方便、有效地解决间歇拥塞问题，为此，SRD引入了1种特殊的AP，即影子AP(shadow AP, SAP)，SAP能实现WLAN的切分，且使用高吞吐量的WLAN作为回程链路.同时，本文将用户在AP之间的分配形式化为终端映射问题，并对该问题进行了分析和求解，提出了1个启发式算法.利用以上概念和方法，SRD能将1个WLAN动态地切分为多个子网(sub-WLAN)，这样可以实现：

1) 多个子网在多个信道上进行并行传输，提升信道传输容量，减少1个子网中的用户数量，减少冲突.

2) 通过动态地、有策略地调整终端映射，能保证用户在AP之间的最佳分配，缓解异构速率和异构传输模式的影响.

与已有的方法不同，SRD的部署很简便，不需在用户终端设备上做任何改动.仿真结果表明，SRD不仅能提升WLAN的吞吐量，还能在一定程度上保证终端之间的公平.

1背景及相关工作

1.1背景

WLAN是基于IEEE 802.11[11]标准的，使用DCF工作模式.任何一个终端在发送数据前，必须先监测信道，如果信道连续空闲时间达到了分布式帧间间隔(distributed inter frame space, DIFS)，该终端即进行发送，否则它将启动1个由二进制指数退避(binary exponential backoff, BEB)算法控制的计时器.当该计时器达到零时，该终端将再次尝试发送.如果只有1个终端在发送数据，该传输就能成功，否则就会发生冲突，传输失败.可见,冲突是1个影响WLAN性能的重要因素.

DCF是1个为所有终端提供均等传输机会的资源分配算法，它不考虑各终端在物理层实际的传输速率，也就是说在一段时间内所有终端传输的帧数是均等的.所以，当不同传输速率的终端共存时，高速终端与低速终端的吞吐量是相等的[2]，这就是异构速率问题.由于低速终端要花更长的时间去传输1个帧，所以异构速率将损害WLAN的性能[2].当前，异构速率的影响越来越明显的2个原因是：1)随着物理层传输速率的迅速提高，最低速率到最高速率之间的差距越来越大，在进行数据传输时，通过速率自适应，终端可以采用任一支持的速率进行传输；2)从IEEE 802.11b到IEEE 802.11n，该标准系列都是向后兼容的，也就是说最新的标准必须能够识别早期的传输模式和传输速率.此外，向后兼容性还引发了另外一个问题，即异构传输模式.为了避免不兼容的传输模式之间的干扰，需要采用一些相应的保护机制，比如RTSCTS(request to sendclear to send)和CTS-to-self，这些保护机制带来一定的开销，也影响了WLAN的性能[12].

随着终端数量的增多，DCF的固有特性导致了3个后果：1)较多的终端意味着每个终端所能得到的传输机会很少；2)较多的终端意味着较多的冲突，这进一步减少了成功传输的机会；3)较多的终端还导致了更严重的异构速率和异构传输模式的影响.所以，在用户或终端比较拥挤的环境下，WLAN和用户的吞吐量很低.

1.2相关工作

截止到目前，关于增加传输机会数量、减少冲突、缓解异构速率和异构传输模式影响的研究工作有很多，现简要综述如下.

为了增加传输机会数量，文献[3-4]将移动通信中的小区呼吸技术引入到了WLAN中，它通过调整发送功率来调节AP的覆盖范围，从而改变网络中的终端数量，减少网络中的终端数就可以增多每个终端的传输机会，但该方法需要AP设备支持动态的功率控制.自IEEE 802.11n开始，帧聚合(frame aggregation)和块确认(block-ACK)技术被用来提升WLAN的MAC(media access control)效率[13].从另一个角度看，这2项技术也可以增多传输机会，如果在1次传输中，利用帧聚合传输x个帧，那么传输机会相当于增多了x倍.关于帧聚合的研究也有不少，比如文献[13-15]，在如何有效使用帧聚合方面，它们都有很好的参考价值.然而，一方面,由于等待和处理时延较大，帧聚合在现实中的应用程度还不够;另一方面,虽然1个聚合帧中允许有多个来自不同终端的子帧，但WLAN的拓扑结构使得这种帧转发现象不会出现.还有些研究试图通过减少开销来增多传输机会，文献[16]提出了一种基于散列(hashing)的退避和无竞争的访问方法，文献[17]则提出了1个混合的信道预留竞争方法，虽然这些方法能有效地减少等待开销，但它们需要修改终端设备，不便于部署.

为了避免冲突，文献[5-6,16]提出了一些非DCF的方法，但它们与广泛使用的DCF不兼容.小区呼吸技术也可以用来缓解冲突，通过减少1个WLAN中的终端数量，就可以减少冲突.然而，以上方法不适用于现有的用户终端设备.

因为传输距离与传输速率之间有很强的相关性[9]，较远的距离意味着较低的传输速率.为了缓解异构速率影响、提升较远终端的传输速率，文献[9-10]提出了中继的方法，中继结点部署在AP与较远终端之间，这样，从较远终端到中继结点、从中继结点到AP的传输速率就能得到提升(距离缩短了).经过2跳高速链路传输1个帧的时间要小于经过1跳低速链路的传输时间，这样也就提高了传输性能.中继方法能从一定程度上减缓异构速率和异构传输模式的影响，但它有2方面的缺陷：1)如果低速终端的传输速率已经是它所能支持的最高速率了，中继方法不仅不能带来任何好处，还会增加开销；2)对于每个被中继的帧来说，要至少经历2次基于DCF的传输，所以中继效率很低、开销很大.此外，为解决异构速率影响，文献[7-8]提出了传输时间公平(airtime fairness)的信道分配方法，但它们与现有标准不兼容.

此外，新发布的IEEE 802.11ac[18]不仅支持更高的传输速率，还能在5 GHz频段上使用更多的非重叠信道.然而，越高的传输速率意味着越低的MAC效率[13]和越严重的异构速率影响，所以，仅靠提高传输速率来提高性能其效果是有限的.

在现实中，为缓解间歇拥塞，部署一些临时AP是1个简单直观的方法.但是，一方面，静态部署的成本很高，因为无法确定拥塞会在何时出现在何地，只能尽量多地部署一些冗余AP；另一方面，动态部署又很不方便，主要是线缆连接困难.虽然移动AP无需线缆，但它们的回程链路一般是移动通信网络，所以带宽容量有限且流量是收费的.更重要的是，无论部署以上哪种AP，都不能保证终端在AP之间的合理分配，这也很大程度地影响着WLAN的性能.

此外，成熟的mesh网络虽然能解决无线接入问题，比如IEEE 802.16j中的中继机制，但它主要解决的是无限覆盖、移动、接入和组网问题，有1套完整的管理机制和协议，适用于较大的地理范围.一方面，现用的用户设备大都不支持mesh，WLAN中也缺乏完整的管理机制和协议;另一方面，无线用户往往聚集在1个较小的空间内(如报告厅)，这是mesh无法解决的.对于大规模统一部署而言，集中式WLAN架构，即“瘦AP+AC(access control)”，是最合适的选择，它的主要优点是方便的管理、监控、收费、移动，在部署时瘦AP往往也是均匀部署的，希望以最低的成本覆盖最大的面积.一方面，在集中式架构中也存在小范围内的拥塞问题，如1个瘦AP范围内拥挤过多的用户;另一方面，AC虽然具有一定的负载均衡能力，但它的控制粒度和反应条件太粗放，不适用于小范围内的间歇拥塞.

2SRD方案

本节将从整体上介绍SRD方案，包括它的动机、概述和实现上的相关问题.

2.1动机

拥塞时WLAN及用户吞吐量很低主要是因为过多的终端数，因此很自然地，比较直观的方法是减少1个WLAN中的终端数，一旦终端数减少，每个终端所能得到的传输机会就会增多，冲突数也减少了，异构速率和异构传输模式的影响也能得到缓解.

为了达到以上目的且不影响已有的用户，要减少1个WLAN中的终端数只能是部署更多的AP，将1个WLAN切分成多个，然后将所有的用户分摊到多个WLAN中.现实中部署临时AP或移动AP的方法遵循的就是这个道理，但它们面临线缆连接或回程链路以及终端分配的问题.当前的技术发展，比如5 GHz、中继以及帧聚合，使得WLAN切分更为可行.尤其是最新公布的IEEE 802.11ac，它工作在5 GHz频段上，可同时使用的非重叠信道数量超过20个，而在传统的2.4 GHz频段上只有3个非重叠信道可用，因此将1个冲突域切分成多个是可能的.现在及以后主流的无线设备都支持IEEE 802.11ac，在不久的将来，5 GHz将成为WLAN的主要工作频段，所以，WLAN的切分在现实中也是可行的，这样可以实现多信道上的并行传输，能大幅提升WLAN的容量.另一方面，在应用中继技术时，中继结点上往往会积累多个终端的很多帧，所以更便于使用帧聚合技术来进一步优化性能.

总之，以上各项技术的发展使得WLAN的动态切分成为可能.

2.2概述

SRD是1个WLAN动态重构方案，通过引入影子AP和终端映射，基于已有的技术，SRD能动态地将1个WLAN切分成多个子网，并有策略地将其重构成1个微型的集中式架构的WLAN，使网络及每个用户的吞吐量能得到倍增.

SRD的工作原理示意如图1所示.在普通网络模式下，9个终端连接到1个AP上，它们都工作在信道1上.使用SRD方案并引入2个SAP(SAP1和SAP2，无需支持多频)，SAP1是1个独立的物理实体，SAP2为1个普通的用户终端(需要安装额外的软件).AP为每个SAP分配1个非重叠的信道(6和11)，并根据全网的终端信息有策略地把这些终端分配给SAP或自己，比如按距离就近分配.这样，原有的1个WLAN就被切分为3个子网，它们分别工作在3个非重叠信道上(即信道1，6，11)，2个SAP像普通终端一样通过信道1与AP通信.该重构后的WLAN为1个微型的集中式架构的WLAN，其中AP同时担任着AC的角色.SAP1和SAP2也具有双重角色：对于AP来讲，它们是终端；而对于连接到它们的终端来讲，它们又是AP.显然，SRD具有4个优点：

1) SRD将所有的终端分摊到多个子网中，很大程度地减少了1个子网中的终端数，每个终端所能得到的传输机会也就增多了，冲突数也就减少了；

2) SRD可以为每个子网分配1个独立的、非重叠的信道，因此能够实现并行传输；

3) 通过将较远的低速终端连接到距离它们较近的SAP上，SRD能缓解异构速率的影响；

4) 通过将相同传输模式的终端分配到1个子网中，SRD能减少异构传输模式引发的开销.

Fig. 1　Schematic diagram of SRD.图1　SRD原理示意

SRD的工作流程如下：2个SAP在启动时扫描可用的AP和空闲信道，在用户1或管理用户指示下连入指定的AP或缺省AP(信道1).在SAP与AP之间可正常无线通信后，就开始了SRD正常的工作流程，如图2所示.首先，AP和SAP要实时收集网络状态信息，如各信道的可用状态、各终端的流量和速率变化等，SAP需要将采集到的信息提交给AP.在初始时，AP要为各SAP分配非重叠的信道，若在运行中信道的可用状态发生了较大变化，还可为SAP重新分配信道.通过对采集到的网络状态信息进行预处理，若发现变化程度超过一定阈值，AP则重新进行映射计算.根据计算所得的最优映射，若需要调整终端的分配，则AP将配合SAP控制终端进行切换.若可用信道状态发生了变化，AP还要配合SAP将某个子网迁移到另一个信道上.以上的循环过程虽然是持续进行的，为减少开销，AP与SAP之间的交互、终端切换和信道切换的时机和次数需要进行权衡.除了以上的管控流程，AP和SAP的另一个核心任务是协调完成流量的中继和帧聚合.

Fig. 2　Workflow of SRD.图2　SRD工作流程

在SRD方案中，存在2个关键问题，即WLAN切分和终端分配.

1) WLAN的切分需要1个特殊的AP，其不需要任何线缆连接且具备高速、免费的回程链路.因此，引入了SAP，SAP是1个与AP相似的网络构件，具有以下特点：

① SAP的回程链路是一条连接到普通AP的WLAN链路；

② SAP的服务集标识(service set identifier, SSID)和与其相连的AP相同，所以SAP的存在对终端来讲是透明的；

③ SAP集成了一些已有技术，如中继、帧聚合和块确认，以最大程度地提高回程链路上的吞吐量；

④ SAP通过分时复用的方法，可以工作在多种模式(终端模式和AP模式)和多个信道上.

2) 如何将所有终端合理地分配到各个子网中.本文将终端分配定义为终端映射问题，即终端与AP及SAP之间的对应关系.不同的终端映射对应着不同的终端分配，也影响着WLAN的性能.本文中，SRD期望的最优终端映射(简称最优映射)满足3个条件：

① 最大化WLAN的吞吐量;

② 保持被中继终端和未被中继终端的公平性;

③ 保持实时性，即中继流量的传输时间不超过指定阈值.

然而，寻找最优映射是一个非常复杂的问题，原因有2个:1)可能的终端映射数量随着终端数的增多成指数增长即搜索空间太大;2)影响WLAN性能的因素有很多，包括终端数、帧长分布、传输速率分布以及传输模式等.因此，要找到最优映射，需要设计1种特殊的方法，相关的讨论将在第3节进行.

总之，通过引入SAP和终端映射，SRD利用已有的技术能动态地对WLAN进行切分和重构，重构后的WLAN因允许多信道并行传输、每个子网用户数减少、冲突减少、异构速率和异构传输模式影响减小而吞吐量倍增.

2.3实现相关问题

本节将讨论SRD在技术上的可行性，包括终端的透明切换(handoff)、工作模式信道的快速切换(switch)和SAP的实现与部署问题.

根据最优映射计算结果，SRD需要通过控制终端切换来调整终端到AP或SAP的连接.为了不影响已有用户的网络连接，需要实现终端的透明切换.对该技术已有一些相关的研究，比如文献[19]提出的虚拟AP技术.由于重构后的WLAN是1个微型的集中式架构的WLAN，所有SAP和终端的配置信息(如IP地址)都存放在AP上，终端在不同SAP或AP之间的切换不会引起其IP地址的变化，所以，终端的正常通信不会因切换而中断，即终端的切换对用户来讲是透明的.

在AP与被中继终端之间中继数据时，SAP需要交替地工作在终端模式和AP模式，且这2种模式通常工作在不同信道上，因此还需要同时进行信道切换，为了减少工作模式和信道切换带来的开销，必须采用快速切换技术，该技术的实现已经比较成熟[20]，本文不再赘述.

在实现方式上，SAP可以是1个独立的硬件，也可以是1个安装在普通用户终端上的软件模块.硬件方式的实现在部署时不需要用户设备做任何改动，但需要一些成本投资；软件方式的实现需要在用户设备上安装软件但不需要额外的投资.此外，本文只考虑SAP安装了1个无线收发模块，如果SAP安装了多个无线收发模块，那么它就可以在多个信道上同时进行收发，也就不需要进行工作模式和信道的切换了.此外，本文只考虑SAP以独立物理硬件形态实现.

很明显，SAP的部署位置也是与性能相关的因素.此类问题，如中继结点的安放，在文献[9,21-23]中已进行了广泛深入的研究.在本文中，一方面，几米的偏差对性能的影响不大，所以SAP的部署可凭经验操作，比如用户较为密集的、距离AP不太远(视线距离内)的位置.另一方面，SAP的安放是由最终使用者实施的，SRD的任务是在SAP的位置确定后对WLAN进行合理的切分和重构.此外，因为SAP和AP工作在非重叠信道上，所以，部署的SAP数量受所在场所的空闲信道数约束，也要考虑实际用户数量的大小.

此外，由于AP掌握着整个WLAN的所有信息，也便于监控网络状态的变化、计算最优映射和调整终端分配，所以SRD在技术上是可行的.

3终端映射

本节描述SRD是如何解决2.2节所述的第2个关键问题，即寻找最优映射.首先，本节对终端映射进行形式化分析，而后给出相应的计算方法.

3.1形式化

假设1个静态的(终端的数量与位置是固定的)WLAN由1个AP和n个终端组成，每个终端的物理层传输速率和帧大小都是固定的，所有终端都是饱和的，且所有的流量都是由终端发往AP的，以上假设与传统的分析思路[24]一致.不妨将由n个终端组成的终端集合记为N={1,2,…,n}，帧长集合记为S={s1,s2,…,sn}，传输速率集合记为R={r1,r2,…,rn}.由于异构速率的影响与异构传输模式的影响相似，为简化起见，将异构传输模式的影响耦合到异构速率中，即只考虑异构速率的影响.

再假设有s个SAP部署在该WLAN中，每个都工作在独立的非重叠信道上，任一终端到任一SAP的距离是固定的，因此可假设它们之间的传输速率也是固定的.设分配给任一SAPi的终端集合为Ni(Ni⊆N)，帧长集合为Si(Si⊆S)，传输速率集合为Ri，分配给AP的终端(即未被中继的终端)构成集合N0.s+1个终端集合满足2个条件：

N0∪N1∪N2∪…∪Ns=N，

∀i,j,i≠j,0≤i≤s,0≤j≤s⟹Ni∩Nj=∅.

定义1. 终端映射.1个终端映射就是1个可能的终端分配方案，形式化定义为

mk={{N0,S0,R0}k,{N1,S1,R1}k,…,{Ns,Ss,Rs}k}.

需要注意的是，同一终端到不同SAP的距离是不同的，所以该终端到不同SAP的传输速率也是不同的.因为终端总数为n，子网总数为s+1，所以共有(s+1)n个可能的终端映射.

因所有终端的帧长都是固定的，为便于计算，将帧速率(单位时间内成功传输的帧数)当作吞吐量.对于1个普通WLAN{N,S,R}而言，其吞吐量记作F(N,S,R)，当利用SRD方案和终端映射mk将其重构后，其吞吐量记作FSRD(mk).

定义2. 最优映射mo是1个特殊的终端映射，满足条件：

∀k,k≠o⟹FSRD(mo)≥FSRD(mk)，

FSRD(mo)>F(N,S,R).

也就是说，基于最优映射重构后的WLAN能实现吞吐量的最大化.SRD方案的目标就是寻找最优映射，并基于最优映射对WLAN进行重构.3.2节将普通WLAN的吞吐量作为参考依据，通过比较来寻找最优映射.

3.2普通WLAN的吞吐量

本节将推导普通WLAN的吞吐量.根据文献[24]，1个WLAN的吞吐量为

F(N,S,R)=

(1)

其中，Ps是成功传输的概率，Ptr是在任一时隙(slot time)中至少有1个帧在传输的概率，Tslot是1个标准时隙的时间长度.与文献[24]相似但不同的是，在本文中，1个成功传输所占用信道的平均时间Ts是由n个终端的数值计算所得的均值.类似地，1个冲突所占用信道的平均时间Tc也是由n个终端的数值计算所得的均值.

(2)

其中，TDIFS为分布式帧间间隔(DIFS),TSIFS为短帧间间隔(short inter frame space, SIFS),TPHY为数据帧和确认(ACK)帧的物理层开销，对于1个固定的场景，这3个时间量都是固定的.在WLAN中，由于每个终端都享有均等的传输机会，因此1个成功传输所占用信道的平均时间为

Ts(N,S,R)=

(3)

当发生冲突时，信道被占用的时间取决于耗时最长的那个传输，即信道占用时间tc为

(4)

(5)

因此，终端i与1个或多个编号小于它的终端冲突的概率为

(6)

该冲突占用信道的时间为

(7)

所以，1次冲突占用信道的平均时间为

(8)

讨论如何计算式(1)中的Ps和Ptr.假设条件冲突概率为p，即任一传输发生冲突的概率为p，那么很容易得到：

(9)

(10)

(11)

(12)

其中，W为最小竞争窗口，m为最大退避次数，它们都是常量.因此，τ，Ptr，Ps都是n的函数，虽然很难得到它们的解析解，但可以计算出它们的数值解.

最后，冲突的平均信道占用时间Tc(N,S,R)和WLAN的吞吐量F(N,S,R)就能计算得出，因为所有终端的传输机会都是均等的，所以所有终端的吞吐量(帧速率)也是相等的，即任一终端的吞吐量为

(13)

3.3重构后WLAN的吞吐量

对于1个给定的终端映射mk，计算基于它重构的WLAN的吞吐量，首先计算任一子网的吞吐量.

为简化过程，忽略SAP工作模式切换和信道切换所带来的开销，并且将完成1次收发的过程定义为1轮(round).也就是说，在1轮中，SAP将从所有下属的终端接收一定数量的帧，聚合后再转发给AP，完成以上过程后该轮结束，新的1轮随即开始.对于任一SAPi，设其平均1轮的时间长度为ti，工作在AP模式与终端模式的时间比例为αi.

当SAPi工作在AP模式时，该子网(SWi)的吞吐量为F(Ni,Si,Ri)，可利用式(1)计算得出.当SAPi工作在终端模式时，SWi的吞吐量为0.所以，在1轮中，SWi的平均吞吐量为

(14)

那么，SWi中每个终端的吞吐量为

(15)

要计算重构后整个WLAN的吞吐量，需要知道AP下属的终端数及它们的帧长分布.连接在AP上的终端包括未被中继的终端和s个SAP.下面讨论由SAP发往AP的帧长和AP下属的活跃终端数.

为了提高中继效率和被中继终端的竞争力(相对于未被中继终端)，SAP和AP之间的数据传输使用了帧聚合和块确认机制.帧聚合包括2种实现模式，即聚合MAC服务数据单元(aggregate MAC service data unit, AMSDU)和聚合MAC协议数据单元(aggregate MAC protocol data unit, AMPDU).前者有较高的聚合效率，但易受干扰影响，因此在现实中后者应用的居多，在传输过程中，即使AMPDU中某些子帧发生错误，其他子帧仍然可以使用，发生错误的子帧还可以选择性地进行重传.所以，本文也采用AMPDU模式进行帧聚合，那么根据协议标准，有2个限制条件，即1个AMPDU中子帧的数量不能超过64，整个AMPDU帧的长度应小于64 KB(最大长度为65 535 B).在现实网络中，由于大部分报文的长度都比较小，70%的报文长度不到128 B[25]，所以，在下文分析中，为简单起见忽略帧长限制.

对于SAPi，在1轮中，它有tiFi(Ni,Si,Ri)个帧需要聚合，因此，SAPi的1个AMPDU中的子帧数量为

(16)

由于SAPi下属的终端发出的帧数在统计上是均等的，所以，1个AMPDU的平均长度为

(17)

其中,ld为MPDU(MAC protocol data unit)定界符(delimiter)的长度.

(18)

(19)

其中，rSAP,i表示SAPi与AP之间的传输速率，在一个固定的环境下，它是一个已知常量.

(20)

要求解基于终端映射mk重构后的整个WLAN的吞吐量FSRD(mk)，还需要进一步知道每个SAP在不同工作模式上的时间比例.根据以上分析，一旦ti和αi确定，FSRD(mk)就可计算得出，下面对此进行讨论.

为了保证实时性，中继帧的传输必须在一定时间内完成，设时间上限为tu，即中继帧从被中继终端到AP总的传输延时不超过tu.显然，ti≤tu(1≤i≤s)，并且tu越大聚合的效率也就越高.因此，得到2个约束条件：

(21)

通过将约束条件(21)中的帧数最大化，可以得出ti，为了保证公平性，被中继终端和未被中继终端的吞吐量应该相当，即：

(22)

通过式(22)，可以计算出αi，也就保证了被中继终端和未被中继终端之间的公平性.式(22)给出了每个被中继终端和未被中继终端的吞吐量，所以，重构后整个WLAN的吞吐量为

(23)

3.4最优映射计算

根据3.3节的分析，对于任一给定的终端映射，可以计算出重构后WLAN的吞吐量，因此，可以通过穷尽比较的方法找出最优映射，过程如下：

1) 利用穷尽的方法找到每个可能的终端映射；

2) 计算基于每个终端映射重构后的WLAN的吞吐量；

3) 通过比较所有终端映射对应的WLAN的吞吐量，得出最优映射.

利用以上方法寻找最优映射需要完成2步操作：1)找到每种可能的终端映射，将n个终端分配到s+1个子网中，共有(s+1)n个可能的结果；2)计算每个终端映射对应的WLAN的吞吐量，该过程包括一些复杂的数值计算.所以穷尽比较方法的复杂度是O((s+1)n)，主要由第1步决定.

由于以上方法过于复杂，需要找到1个更简单实用的方法.SRD方案的基本思路是动态地对WLAN进行切分，以允许多信道上的并行传输、减少1个子网中的终端数.虽然不同的终端映射会对最终的性能有一些影响，在现实中，本文认为1个次优的终端映射也是可以接受的.由于影响WLAN性能的关键因素主要是终端数(与传输机会和冲突相关)、传输速率和传输模式(与多速率相关)，以及帧长度(与MAC效率相关)，因此，综合考虑以上因素，本文提出1个启发式算法如下：

1) 利用传输速率和帧长度对终端集合S进行排序.首先，用传输速率对S进行递增排序.如果有多个终端的传输速率相同，再按以下方法用帧长度对这些终端进行二次排序：如果传输速率等于最大的传输速率，则按帧长度对这些终端进行递增排序，否则进行递减排序.

2) 如果|N0|>βmax{|N1|,|N2|,…,|Ns|}，则顺序地从S中选取下一个终端i作为被中继终端，否则算法结束.也就是说，分配给每个SAP的最大终端数应少于未被中继的终端数.其中，β(1.0≤β≤1.5)是1个调整被中继终端和未被中继终端比例的参数.

3) 为终端i选择1个合适的SAP(SAPj).不妨用r(x,y)表示x和y这2个结点之间的传输速率，SAPj需要满足3个条件，依次用这3个条件对所有SAP进行筛选，直到剩下1个SAP.条件1：SAPj是负载最轻的，即从其所有下属终端各收1个帧所需时间之和最短;条件2：SAPj所带来的时间增益(式(24))最大;条件3：分配给SAPj的终端数最少.

4) 将终端i分配给SAPj.

5) 返回步骤2)重复执行，即继续选择下一个可被中继的终端.

时间增益的计算方法为

(24)

该启发式算法主要包含2步，即选择可被中继的终端和为终端选择合适的SAP.由于所有终端的数据传输都要通过AP所在的信道，所以，提高该信道上的传输速率和MAC效率对所有终端都有好处，终端分配的1个重要原则就是最大程度地提高或保持该信道上的传输速率和MAC效率.由于不同终端使用信道的传输速率和MAC效率不同，所以该启发式算法按一定顺序来选择可被中继的终端.因为低速终端的吞吐量低且影响所有其他终端的传输性能，所以低速终端优先被选择.对于多个传输速率相同的低速终端来讲，帧长越大的占用信道的时间越长，所以优先选择帧长较大的；而对于高速终端而言，帧长越小的MAC效率越低、吞吐量也就越低，因此优先选择帧长较小的.此外，为了最大化WLAN的吞吐量，各子网之间应尽量保持负载均衡，对于AP来讲，低速终端因耗时更长所以带来的负载也就更大，因此，低速终端大都分配给了各SAP.又因为SAP只是部分时间地工作在AP模式，所以，为各SAP分配的终端数应少于未被中继的终端数.在该算法中，β就是1个调整被中继终端和未被中继终端数量的系数.显然，该算法的复杂度为O(ns)，它比穷尽比较算法更为简单.

以上讨论和分析假设信道的带宽是固定的，这也是当前WLAN缺省的工作模式.为充分利用频谱资源，一些新的研究提出了可变带宽信道的思想，比如文献[26]基于博弈理论研究了可变带宽信道的分配策略.通过调整SRD方案中的相关参数，SRD也能适用于可变信道环境.

4验证

4.1实验验证

在如图3所示的实验环境中，本节用以下设备验证了SAP的效果.

1) AP：Netgear WNDR3700；

2) 测试服务器：普通PC机，通过有线连接AP，用于接收并统计流量数据；

3) 终端1：联想Thinkpad T430，距AP约7 m；

4) 终端2：PC机+360wifi2无线网卡，距AP约9 m；

5) 终端3：联想Thinkpad X200，距AP约15 m；

6) 终端4：联想Thinkpad X100，距AP约15 m；

7) 终端5：PC机+COMFASTCF-WU770N无线网卡，距AP约19 m；

8) SAP：PC机+360wifi2无线网卡+Netcore NW336无线网卡，距AP约8 m.

Fig. 3　Scenario of experiments.图3　实验场景

本实验所用的SAP为一通用PC机，装配了2个无线网卡：一个工作在普通网卡模式，用于向AP发送数据；另一个工作在AP模式，用于接收终端的数据.在SAP上部署定制的转发程序，在收到终端的数据包后，每累积12个数据包就合并为1个数据包，然后转发给AP(模拟帧聚合).因使用了双网卡，该SAP没有模式切换开销，但中继功能由上层应用来完成，因此转发效率略低.

首先5个终端通过无线关联到AP(信道11)，然后向测试服务器循环发送UDP数据包，报文长度均为100 B，在5 min内测试服务器统计到的各终端吞吐量的累积分布函数(cumulative distribution function, CDF)如图4所示.然后，终端3～5关联到SAP(信道1)上， 以同样的方式向测试服务器发送数据，统计到的各终端的吞吐量CDF如图5所示，可知各终端有效的数据传输速率都有了明显提升.2种环境下各终端5 min内传输的字节数如图6所示.5个终端总的吞吐量变化情况如图7所示，可以看出，使用1个SAP后整个网络及每个终端的吞吐量都有了明显提升.由于实验室环境较复杂，周边有10多个其他的AP，各设备形态性能不同，无线网卡的商家也不同，所以各终端所表现的传输性能也不同，传输速率也不稳定.

Fig. 4　Distribution of station goodput without SAP.图4　未使用SAP时各终端的吞吐量分布

Fig. 5　Distribution of station goodput with one SAP.图5　使用1个SAP时各终端的吞吐量分布

Fig. 6　Received bytes by stations in five minutes.图6　各终端5 min内传输的数据量

Fig. 7　Total goodput of five stations.图7　5个终端的聚合吞吐量

4.2仿真验证

Fig. 8　Scenario of simulation.图8　仿真场景

本节通过仿真来验证SRD方案的性能和效果.在如图8所示的仿真场景中有1个报告厅，1个AP部署在正前方，100个用户在报告厅中通过WLAN访问互联网.这些用户(终端)到AP的距离和传输速率分布如表1所示.其中，在距离AP较近的74个用户中，4个用户使用的是802.11g设备.所有终端的MSDU(MAC Service data unit)长度随机分布，构成比例是70%为100 B，15%为1 024 B，15%为1 400 B[25].有3个SAP(SAP1，SAP2，SAP3)分别部署在3个不同的位置(A，B，C)，根据直观经验，3个SAP都部署在AP与较远用户之间且用户较多的位置，SAP之间保持一定的距离.802.11g终端的传输速率为54 Mbps，其他被中继终端与SAP之间、SAP与AP之间的传输速率均为300 Mbps，其他MAC层的相关参数设置如表2所示.因为SRD方案属于MAC层的优化方法，不考虑跨层因素的影响，所以，假设使用的所有信道都是理想的、非重叠的，对各网络设备的物理特性也不做特殊要求，所有设备都能以预定的速率正常传输.

Table 1　Distance and Data Rate

因为经过中继的帧要经历2次DCF竞争，所以冲突对被中继终端的影响要大于未被中继终端.SAP和各未被中继终端面临相同的冲突概率，未被中继终端遭遇冲突时仅丢失1帧，而SAP的AMPDU冲突时将丢失多个帧，所以，SAP的竞争力应进一步提高，此类方法有很多，在仿真中SAP的最小竞争窗口为各终端的一半，终端数量比例系数β=1.2.

Fig. 9　Total frames sent and dropped.图9　传输和丢弃的总帧数

比较4种不同场景下的WLAN性能：场景1为普通WLAN，即不使用任何SAP；场景2只使用一个SAP(SAP1)；场景3使用2个SAP(SAP1和SAP2)；场景4则使用3个SAP.比较30 s内整个WLAN及每个终端的吞吐量，且每一实验重复10次取其均值作为统计结果.

图9给出了不同场景下整个WLAN成功传输和丢弃的总帧数，横坐标表示不同场景对应的SAP数，0对应的为场景1，即没有使用SAP.为了便于比较，把丢弃的帧数放大了50倍.由图9可以看出，WLAN的吞吐量随着SAP的增多而线性增长，每增加1个SAP，吞吐量的增长幅度约为初始(场景1)总量的70%;同时，因冲突而导致的丢包数也随着SAP的增多而明显减少，表明冲突概率随着SAP的增多而大幅下降，如图10所示:

Fig. 10　Collision rate declines as more SAPs are deployed.图10　冲突概率随着SAP的增多而下降

Fig. 11　Distribution of stations with different data rates in each sub-WLAN.图11　各子网中不同速率终端的分布

下面，进一步检验不同速率和不同帧长的终端在各子网中的分布.先按速率把所有终端分为3类：高速(high rate)终端(300 Mbps)、中速(medium rate)终端(180 Mbps)和低速(low rate)终端(54～60 Mbps).同样方式，按帧长也把所有终端分为3类：长帧(large frame)终端(1400 B)、中帧(medium frame)终端(1024 B)和短帧(small frame)终端(100 B).图11给出了不同速率的终端在各子网中的分布，SW0代表由未被中继终端组成的子网，即AP所在的子网；SW1代表SAP1所在的子网.图12给出了不同帧长的终端在各子网中的分布.这2个图表明终端被分摊到各个子网中，然而，终端的分配有以下2个明显的特点：

1) 被中继终端在各子网中的分布是比较均匀的.①各SAP下属的被中继终端的总量是相等或相近的；②各SAP的下属终端中，不同速率、不同帧长的终端分布也是均匀的.

Fig. 12　Distribution of stations with different frame sizes in each sub-WLAN.图12　各子网中不同帧长终端的分布

2) 被中继终端和未被中继终端之间的终端分布是不均匀的.例如，未被中继终端的数量要大于任一子网中的被中继终端的数量，不同速率、不同帧长的终端在被中继与未被中继之间的分布也是不均匀的.

该现象的产生原因有3个：①为了充分提高AP(SW0)所在信道的吞吐量，低速终端和短帧终端大都被中继了；②为了保持SAP之间的负载均衡，终端总数、不同速率或帧长的终端数在各SAP之间的分配也是尽量均衡的；③为了保持被中继终端的竞争力，任一SAP下被中继终端的数量少于未被中继终端的数量.

Fig. 13　CDF of goodput variance of each station.图13　各终端吞吐量方差的CDF

Fig. 14　Average frames sent by stations in each sub-WLAN.图14　各子网中终端传输的帧数均值

5总结

小范围间歇拥塞情况下WLAN及用户的吞吐量很低，为此，本文提出了1个SRD方案，通过引入影子AP和终端映射，SRD能对WLAN进行动态切分和合理重构.分析和仿真结果证明，SRD能很大程度地提升WLAN的吞吐量.此外，SRD的部署无需终端设备作任何改动.

参考文献

[1]Gupta A, Min J, Rhee I. WiFox: Scaling WiFi performance for large audience environments[C]Proc of CoNEXT’12. New York： ACM, 2012: 217-228

[2]Heusse M, Rousseau F, Berger-Sabbatel G, et al. Performance anomaly of 802.11b[C]Proc of IEEE Int Conf on Computer Communications (IEEE INFOCOM’03). Piscataway, NJ: IEEE, 2003: 836-843

[3]Bahl P, Hajiaghayi M, Jain K, et al. Cell breathing in wireless LANs: Algorithms and evaluation[J]. IEEE Trans on Mobile Computing, 2007, 6(2): 164-178

[4]Bejerano Y, Han S. Cell breathing techniques for load balancing in wireless LANs[J]. IEEE Trans on Mobile Computing, 2009, 8(6): 735-749

[5]Kim S, Verma L, Choi S, et al. Collision-aware rate adaptation in multi-rate WLANs: Design and implementation[J]. Computer Networks, 2010, 54(17): 3011-3030

[6]Lin J, Chen C, Feng K. Adaptive reservation-assisted collision resolution protocol for wireless local area networks[C]Proc of WCNC’09. Piscataway, NJ: IEEE, 2009: 1-6

[7]Joshi T, Mukherjee A, Yoo Y, et al. Airtime fairness for IEEE 802.11 multirate networks[J]. IEEE Trans on Mobile Computing, 2009, 7(4): 513-527

[8]Zhang M, Chen S, Jian Y. MAC-layer time fairness across multiple wireless LANs[C]Proc of IEEE Int Conf on Computer Communications (IEEE INFOCOM’10). Piscataway, NJ: IEEE, 2010: 1-9

[9]So A, Liang B. Enhancing WLAN capacity by strategic placement of tetherless relay points[J]. IEEE Trans on Mobile Computing, 2007, 6(5): 522-535

[10]Bahl P, Chandra R, Lee P, et al. Opportunistic use of client repeaters to improve performance of WLANs[J]. IEEEACM Trans on Networking, 2009, 17(4): 1160-1171

[11]IEEE Computer Society. IEEE Std 802.11-2012, Part 11: Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications[S]. Los Alamitos, CA: IEEE Computer Society, 2012

[12]AirMagnet. Impact of legacy devices on 802.11n networks[OL].[2015-03-15].http:www.nle.comliteratureAirmagnet_impact_of_legacy_devices_on_80211n.pdf

[13]Li T, Ni Q, Malone D, et al. Aggregation with fragment retransmission for very high-speed WLANs[J]. IEEEACM Trans on Networking, 2009, 17(2): 591-604

[14]Kolap J, Krishnan S, Shaha N. Frame aggregation mechanism for high-throughput 802.11n WLANs[J]. International Journal of Wireless & Mobile Networks, 2012, 4(3): 141-153

[15]Skordoulis D, Ni Q, Chen H, et al. IEEE 802.11n MAC frame aggregation mechanisms for next-generation high-throughput WLANs[J]. IEEE Wireless Communications, 2008, 15(1): 40-47

[16]Starzetz P, Heusse M, Rousseau F, et al. Hashing backoff: A collision-free wireless access method[C]Proc of the 8th Int IFIP-TC 6 Networking Conf. Berlin: Springer, 2009: 429-441

[17]Zhang R, Ruby R, Pan J, et al. A hybrid reservationcontention-based MAC for video streaming over wireless networks[J]. IEEE Journal on Selected Areas in Communications, 2010, 28(3): 389-398

[18]IEEE Computer Society. IEEE Std 802.11ac-2013, Part 11: Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications, Amendment 4: Enhancements for Very High Throughput for Operation in Bands Below 6GHz[S]. Los Alamitos, CA: IEEE Computer Society, 2013

[19]Grunenberger Y, Rousseau F. Virtual access points for transparent mobility in wireless LANs[C]Proc of WCNC’10. Piscataway, NJ: IEEE, 2010: 1-6

[20]Kandula S, Lin K, Badirkhanli T, et al. FatVAP: Aggregating AP backhaul capacity to maximize throughput[C]Proc of NSDI’08. Berkeley, CA: USENIX Association, 2008: 89-104

[21]So A, Liang B. Efficient wireless extension point placement algorithm in urban rectilineal WLANs[J]. IEEE Trans on Vehicular Technology, 2008, 57(1): 532-547

[22]Islam M, Dziong Z, Sohraby K, et al. Capacity-optimal relay and base station placement in wireless networks[C]Proc of ICOIN’12. Piscataway, NJ: IEEE, 2012: 358-363

[23]Lin B, Ho P, Xie L, et al. Optimal relay station placement in broadband wireless access networks[J]. IEEE Trans on Mobile Computing, 2010, 9(2): 259-269

[24]Bianchi G. Performance analysis of the IEEE 802.11 distributed coordination function[J]. IEEE Journal on Selected Areas in Communications, 2000, 18(3): 535-547

[25]Huda T. Throughput enhancement of IEEE 802.11 WLAN for multimedia communications[C]Proc of AH-ICI’09. Piscataway, NJ: IEEE, 2009: 1-6

[26]Huang Tingpei, Chen Haiming, Zhang Zhaoliang, et al. Variable-width channel allocation based on game theory in 802.11 networks[J]. Journal of Computer Research and Development, 2013, 50(10): 2059-2069 (in Chinese)(黄庭培, 陈海明, 张招亮, 等. 802.11网络中基于博弈理论的可变带宽信道分配研究[J]. 计算机研究与发展, 2013, 50(10): 2059-2069)

Xu Shibo, born in 1975. PhD. His main research interests include WLAN, performance analysis and optimization.

Liu Xiaolan, born in 1975. PhD candidate. Her main research interests include WLAN, mobile network, performance analysis and optimization.

Ren Fengyuan, born in 1970. PhD. Professor and PhD supervisor. His main research interests include DCN, virtualization, wireless, performance evaluation (renfy@tsinghua.edu.cn).

中图法分类号TN925.93; TP393

基金项目：国家自然科学基金项目(61225011)；国家“九七三”重点基础研究发展计划基金项目(2012CB315803)

收稿日期：2014-10-21；修回日期：2015-05-05

This work was supported by the National Natural Science Foundation of China (61225011) and the National Basic Research Program of China (973 Program) (2012CB315803).