英语原文共 5 页，剩余内容已隐藏，支付完成后下载完整资料

A Distributed Collaborative Relay Protocol for Multi-hop WLAN Accesses

Bo Zhanglowast;, Zhongming Zhenglowast;, Xiaohua Jiadagger;, Kan Yanglowast; Department of Computer Science City University of Hong Kong lowast;{Bo.Zhang, 50541654, kanyang3}@student.cityu.edu.hk dagger;jia@cs.cityu.edu.hk

摘要——由于802.11 WLANs的数据包传输的公平性，低传输速率的客户端将耗费更长的时间完成数据包的传输，因此也降低了整个网络的吞吐量，这意味着其他高传输速率的客户端的吞吐量也会受到影响而降低。本论文提出了一种中继合作转发的方法，让高传输速率客户端为低传输速率的客户端中继转发数据从而提高网络的吞吐量。就此，本论文提出了三个原创的优化方法：1）我们建立了一个广义模型，用于分析客户端的多跳中继情况。此广义模型中，那些相隔节点较远的客户端可以利用并行传输的技术来提高网络吞吐量。2）我们提出了一个集中式算法，用以计算客户端的多跳中继拓扑情况，从而选择最优多跳中继方式来达到本广义模型可以达到的最大吞吐量。3）我们还为客户端提出了一个分布式多跳中继协议，来完成客户端对节点网络的动态接入和断开。仿真测试的结果表明，我们所提出的集中式算法显著提升网络性能，平均下来可以把吞吐量提高42%。在网络中，有高达75%的客户端使用单条中继或多跳中继的接入方式，而非与无线接入点直接连接，这有助于提高网络系统的性能。另外，网络中有高达39%的链接有机会与其他链接一起并发传输。

1. 简介

一个客户端通过无线接入点传输数据的速率是由客户端与无线接入点间的信号质量所决定的。那些与无线接入点间信号更弱的客户端（这些客户端一般距离无线接入点较远）的传输速率会更低。IEEE 802.11的内置传输速率自动控制技术可以根据检测到其接受信号的强度来增加或降低数据传输的速率。但是，802.11网络是基于客户端间数据包传输的公平性而设计的。这也就是说，所有的客户端拥有平等机会接入使用无线信道，当一台客户端成功占用信道，它将一直占用该信道直至其完成整个数据包的传输为止。在大多数802.11的协议中，最高数据传输速率一般可以大约比最低传输速率高10倍有多。一台低传输速率的客户端，其相对于高传输速率的客户端而言，占用信道的时间将会多得多，这也因此大幅度地拉低了整个网络系统的吞吐量。这种情况也被称为802.11协议中的异常问题。假设一种情况下，三个客户端都链接到一个传输速率为54Mbps的接入节点，其中传输数据包不存在开销，那么每个客户端理论上都讲具有18Mbps的传输速率。可是，一旦其中一个客户端远离无线接入点而导致其传输速率只有6Mbps时，由于客户端间数据包传输的公平性原理，所以每个客户端最终能达到的吞吐量就降低到了4.9Mbps。

要解决异常问题，其中有一种方法就是让中间节点为距离无线接入点较远的客户端中继转发数据。图一是由华为提供的一组实验数据，其揭示了传输距离与数据传输速率的变化关系。A节点，或者说VA，在距离无线接入点较远的地方，其数据传输速率仅仅可以达到6Mbps。这时，如果我们引入一个在VA和无线接入点中间的客户端VB，让它为VA中继转发数据，那么在VA与VB间数据传输速率为24Mbps的情况下，VA与无线接入点间的数据传输速率可以达到12Mbps。这种情况相较于让VA与无线接入点直连的方式，客户端VB在帮助VA中继转发数据的过程中，也同时提高了自身的吞吐量。

目前，关于利用中继转发节点解决异常问题的研究已经出现了很多。苦于多跳中继转发中的高开销情况，大多数这类研究则是基于单跳中继转发的情况。也就是说，一台远端客户端仅有一个可用中继转发节点为其中继转发数据。然而，如果我们再考虑到并行传输的情况下，那么仅仅是单跳的中继转发就意味着极低几率的并行传输，这是因为单跳中继中节点通常相隔较远并且容易相互影响。

在本论文中，我们将把单跳中继转发的研究向多跳中继转发拓展。首先，我们提出了一个广义模型，用以分析多跳中继转发的吞吐量增益。然后，我们提出了一种可以计算多跳中继转发拓扑情况的算法，从而计算出网络系统可以达到的最大吞吐量。在应用多跳中继转发的技术之后，会有更多的链路（客户端）可以在系统中并发传输数据，从而进一步提升了网络系统的性能。我们同时还提出了一个分布式多跳中继协议，来完成客户端与节点网络的动态接入与断开。

本论文之后的内容编排如下。在第二部分中，我们为现有的用于减轻异常问题的研究做出了综述。在第三部分中，我们进一步描述了大概的系统结构。而在之后的第四第五部分中，我们分别对集中式算法以与其对应的分布式多跳中继协议进行了描述。在第六部分，我们列出了仿真测试的结果。最终，我们在第七部分对本次研究做出了总结。

第二部分 相关研究

传输速率的异常问题最先是在Heusse等人的研究[4]中被提出讨论并分析的。有些研究建议将现在[5]–[7]中MAC所使用的数据包公平传输策略改变为时序公平传输策略，从而解决当前传输速率异常问题。然而，这种方法需要我们修改当前网络结构的MAC层属性，这其实会进一步降低低传输速率的客户端的性能，所以并非是一个整体最优化的解决方法。在[1]和[2]中提到了使用WLANs中一些客户端来完成中继转发的工作，这也被称为多跳拓展。然而，这些中继转发仅仅适用于单跳的情况，而并没有为中继转发网络提供出一个适用的推广算法。

在[8][9]的研究中，可以找到一些关于多跳中继转发结构的初期研究，而在[10]中，其提出了一个广义的多跳WLAN网络结构。然而，这些文献并没有解决传输速率的异常问题。

在[3],[11]–[13]中，提到了许多实际工作中的应用的合作中继转发策略，但是这些研究都没有考虑到使用并发传输的情况。由于多跳中继转发会造成严重的传输开销，所以大多数的算法的设计是基于单跳中继的情况。除此之外，还有一些算法由于过于复杂，很难被应用于实际场景中。

第三部分 问题描述

A 传输及干扰模型

正如图二所示，在一个协作中继网络（CRN）中，现有n个客户端V1到Vn以及一个无线接入点。假设每个客户端与无线接入点的传输功率是定值。本论文不讨论功率调节的情况。Vi和Vj两个客户端如果均在彼此的传输范围内则可以相互通信。其通信的传输速率R(Vi, Vj)由其接收信号强度所决定。接受信号强度可由传输功率Pt(Vi)和信号衰减率A(Vi, Vj)计算得出，其计算公式如下：R(vi, vj) = f(Pt(vi) times; A(vi, vj)),

这里f()是从接收信号强度到传输速率的一种映射。当传输功率为20dBm时，f()的情况如表1数据所示。华为的实验结果在不考虑障碍物的情况，揭示了传输范围和传输速率之间的关系。

在本论文中，我们假设通信连接是双向的，这也符合802.11协议的特性。我们还假设一条链路的两端节点具有同样的传输速率，即R(vi, vj) = R(vj, vi),这使得高速端节点的传输速率在一条链路中与低速端节点保持一致。

我们是这样定义链路间的干扰的。如果链路Li和Lj中有任意端节点在其他链路的端节点的干扰范围内，则视为存在干扰。

在我们提出的多跳中继转发方法中，当两个链路互不干扰的情况下可以并行传输数据，因此可以大幅度提高网络的吞吐量。

B 数据包传输时间与网络效率

客户端—无线接入点数据包传输时间即为一个数据包在客户端与无线接入点间传输的所有时间，这包括了中继节点的转发时间。这里，设T(Vi)为数据包在客户端Vi与无线接入点间的传输时间，t(Vi, Vj)位一个数据包通过链路（Vi, Vj）的传输时间。有：

其中，C是数据包的大小，tau; 为每次传输的开销，例如：802.11中MAC层使用的DIFS，SIFS，帧头以及确认帧等。为了简化计算过程，此处不考虑信道竞争的补偿时间。在802.11g BSS模型中，tau; 恒等于94mu;s，不受传输速率变化影响。

在应用802.11e QoS规格下的帧突发传输技术后，tau; 的值可降至76mu;s。

当客户端Vi直接接入无线接入点时，数据包的传输时间为T(vi) = t(AP, vi)，而当客户端Vi利用中继节点Vk为其转发的情况下，T(vi) = T(vk) t(vk, vi)。

设Gamma; 为所有客户端在网络中传输一个数据包的总时间。因为我们考虑在系统中应用多跳中继转发的情况，所以将会出现很多链路可以并行传输数据。设delta; 为并行传输情况下，每个客户端发出一个数据包的周期内可节约的总时间。其中，Gamma; 为：

因为802.11在信道访问中遵循数据包公平性，所以每个客户端的吞吐量在长周期情况下将会保持基本一致。所以，每个客户端的吞吐量则可以这样计算得到：

通过公式（3）和（4）我们可以发现，为了提升每个客户端的吞吐量，传输过程的总时间应该降低，这可以通过降低T(Vi)或者增加delta; 来实现。因为delta; 很大层度上受传输规划的影响，但本论文中我们并不考虑到传输规划的问题，所以我们选择利用多跳中继转发来降低T(Vi)。不过，在我们的协议中，并行传输是允许的，这也会在仿真阶段进行测试。

第四部分 集中式协作中继算法

正如在第三部分中所讨论到的，我先首先提出了一个算法来建立一个可以达到最低传输时间的拓扑结构。然后，我们还设计了一个简单算法来计算网络中通过并行传输节约下来的总时间。

设客户端Vi与无线接入点的数据包传输最短时间为T*(Vi)，我们可以使用以下公式为客户端Vi得到一条可能的路由并计算出其传输时间：

由以上公式可知，得到的路由可能是客户端Vi与无线接入点的直接连接，也可能是另外一条通过客户端Vk与无线接入点的最优路由。

引理 1 公式（5）总可以得到最优的Trsquo;(Vi)，即等于T*(Vi)。

证明：假设(AP, vk1, vk2, ..., vkn, vi)是可以达到数据包传输最短时间T*(Vi)的路由。那么显然，必存在(AP, vk1, vk2, ..., vkn)可以达到数据包传输最短时间T*(Vkn)。所以，公式（5）包括了所有可能存在的路由情况，也可以得到最优的解决方案。

为了建立一个协作中继网络（CRN），我们先创建了一个树的拓扑结构，其以无线接入点处为树的根部。设已经与树连接的客户端的集合为TAP，余下的客户端为V。假设每个客户端vi isin; V , vk isin; TAP，并满足Tlowast;(vi) ge; Tlowast;(vk)，然后我们可以用一下公式为任意节点Vi求得一条可能的路由。

引理 2 T(vx) = Tlowast;(vx), if Tlowast;(vx) = minviisin;V Tlowast;(vi).

证明：公式（5）和公式（6）的区别在于，计算T (vi ) 时仅仅考虑部分的T lowast; (vi ) 。

显然，如果Tlowast;(vi) = Tlowast;(vk) t(vk,vi) ，则必满足T lowast; (vi ) ge; T lowast; (vk ) ，也即是引理2中计算T (vx ) 的方法。

引理 3 Tlowast;(vx) = minviisin;V Tlowast;(vi), if T(vx) = minviisin;V T(vi), vx isin; V .

证明：假设Tlowast;(vx) ̸= minviisin;V Tlowast;(vi) ，那么必有客户端vy isin; V 满足Tlowast;(vy) = minviisin;V Tlowast;(vi) 。根据引理2可知，T(vy) = Tlowast;(vy) 。那么T(vx)和Tlowast;(vx)的关系将满足，T(vx) lt; T(vy) = Tlowast;(vy) lt; Tlowast;(vx)。因为Tlowast;(vx)为数据包传输的最短时间，所以T (vx )已无法取得更优解。因此，这种情况并非所求最优解。T lowast; (vx ) 必为集合V中客户端的最小值。

根据引理2、3可得，一种计算Tlowast;(vi)和创建树拓扑结构的算法如下：

Algorithm 1 Algorithm to Cons

剩余内容已隐藏，支付完成后下载完整资料

资料编号：[153743]，资料为PDF文档或Word文档，PDF文档可免费转换为Word