彭 聪，陈海荣，范 平

(1.湖北科技学院 计算机科学与技术学院，湖北 咸宁 437100；
2.内蒙古工业大学 轻工与纺织系，呼和浩特 010000)

对于分散无线网络的媒质访问控制(MAC,medium access control)协议[1-2]来说，需要同时满足多个相互冲突的目标：高信道利用率、高发送成功概率和高公平性；
协议还应当易于理解和实现，并能提供绝对或相对的差异化服务；
高发送成功概率对于自动重传请求(ARQ,automatic re-transmission query)较难和模糊的广播传输尤为重要[3]。

现有的MAC协议通常采用3种基本机制来分配信道访问(接入)：载波侦听、载波突发和树分裂。在基于载波侦听的协议如基于带冲突避免的载波侦听多路访问(CSMA/CA,carrier sense multiple access with collision avoidance)的IEEE 802.11标准中，节点反复侦听信道，然后在有足够空闲时隙的情况下执行发送；
在基于载波突发的协议如Hiperlan/1中采用的消除产生非抢占式优先级多点接入(EY-NPMA,elimination yield non-preemptive priority multiple access)中，节点尝试通过突发(即阻塞信道，时间比其他节点长)来赢得信道；
在树分裂协议如无线网络分布式排队随机访问协议(DQRAP-WN,distributed queuing random access protocol in wireless networks)中，节点通过分布式深度优先树遍历进行操作。

IEEE 802.11中采用的MAC算法[4]是CSMA/CA协议。在CSMA/CA中，节点首先在一个称为帧间间隔(IFS,inter frame space)的短时间内侦听信道。如果信道繁忙或发生碰撞，节点将从U{0,CW}中采样大量的退避时隙，其中CWmin≤CW≤CWmax为争用窗口。当检测到媒质空闲时，退避计数器自减即每个时隙减1。节点将在其退避计数器为零时访问信道。接收节点等待一个短的IFS(SIFS,short IFS)，然后发送一个ACK。在一个不成功的发送尝试后，CW加倍。尝试成功后，将CW设置为CWmin。

在数据传输之前的控制帧交换可选择地按以下方式执行。发送方以发送一个请求发送(RTS, request to send)开始，接收方在首先等待一个SIFS之后，以一个清除发送(CTS,clear to send)数据包作出响应。在接收方、发送方或两者范围内的节点，在完成帧交换序列期间将延迟访问。

在一个IEEE 802.11网络中，碰撞允许相关节点调整它们的争用窗口。关于条件的信息以很高的代价(碰撞)收集，但不与非碰撞节点共享。这导致了公平性和低信道利用率的问题。

文献[5]提出的指数倍增方案有利于最后成功的节点，但又造成了公平性问题；
当采用非最佳争用窗口时，信道利用率问题由高碰撞概率引起。文献[6]表明，优化争用窗口大小的一个关键问题是准确估计节点的数量。碰撞概率仅依赖于最小争用窗口和节点数量，将最小争用窗口减半相当于将用户数量加倍。文献[7-8]对这两个问题提出了不同的争用窗口调节方案；
文献[9]提出了一种改进自适应的退避算法来解决当接入网络用户数较多时系统性能的优化。通过对经典的二进制指数退避机制的改进，得到一种改进的自适应退避机制使得调节退避窗口时能够自适应地感知网络环境的变化。该机制主要考虑3个方面：引入窗口划分的思想，使得竞争窗口的值仅限于在不同退避阶段的非重叠区间取得。加入冻结概率使模型更符合无线信道中实际传输的过程。设置与信道利用率有关的参数控制退避窗口调节幅度，从而减小碰撞发生的可能性；
文献[10] 针对802.11网络或其他无线网络中的CSMA/CA提出了一种半窗方案，通过添加概率预测因子改进退避时间的计算方法。概率预测因子用于调整介质访问概率计算退避时间的竞争窗口，将窗口划分为至少2个半窗，然后根据窗口的信息增益选择其中一个半窗进行概率预测，从而减少介质的竞争。

EY-NPMA即Hiperlan/1中规定的信道分配和冲突解决协议工作如下：在成功发送后，节点在下一次争用开始前等待一个IFS。争用分为3个阶段：优先级确定、消除和产生。在优先级确定阶段，节点必须在发送优先级确定突发之前，侦听到信道空闲的时隙数目等于它们的优先级(0～4，其中0为最高优先级)。具有较低优先级的节点侦听到信道繁忙并放弃争用，而剩余的节点根据几何分布突发一个随机数量的时隙X，即X～Geom(P)且:

(1)

式中,pE为每个消除时隙中突发的概率，mES为最大突发时间。在生存验证时隙中验证了其生存之后，节点可以访问U{0,mYS}个时隙。采样次数最少的一个或多个节点将访问该信道。

在标准中，时隙长度是根据位周期来指定的，并不是所有类型的时隙都相同。在分析协议时，为了简化和可比性，一般采用统一的时隙长度τ。EY-NPMA中的默认参数为pE=0.5、mES=12和mYS=9都不是最优的。

文献[11]提出的交叉感知层MAC控制方案是另一种基于发送方优先级算法分配突发长度的突发协议。

基本的树分裂算法工作如下[12]：当在一个时隙i中发生碰撞时，所有涉及到的节点被分割成许多子集，第一个子集在时隙i+1中重传，第二个子集在时隙i+2中重传，以此类推。如果一个子集中的节点之间发生了另一个碰撞，则这个子集就会递归地分裂成两个。子集允许发送的顺序可以是广度优先遍历，也可以是深度优先遍历。由于每个节点在每轮中只成功发送一次，因此保证了公平性，但这种协议算法不考虑丢包和干扰，因此降低了信道吞吐量和利用率。

文献[13]针对有线网络提出了分布式排队随机访问协议(DQRAP,distributed queuing random access protocol)，文献[14]将其改进为具有中央控制器的无线网络DQRAP协议即DQRAP-WN，但该协议的操作相当复杂，工作如下：在无争用的情况下，节点只要有一个可用的数据包，就发送一个数据包。如果存在碰撞和包丢失即没有ACK，则节点切换到基于争用的操作。在每个固定长度的数据时隙之后，涉及碰撞的节点随机选择两个小时隙中的一个来发送一个最小的数据包。所有非发送节点在每个小时隙之后的微时隙中提供反馈。如果涉及的节点检测到碰撞，它们就发送一个NACK，并将自己放置在处理队列(RQ,resolution queue)中。如果存在一个单独的节点即没有NACK，则把它放在传输队列(TQ,transmission queue)中。在两个小时隙之后，TQ中的第一个节点访问信道。节点维护两个队列的长度和它们自己在其中的位置；
文献[15]提出了另一种树分裂协议，其中控制器由获胜发送方动态指定，在第一次成功处截断树的深度优先遍历。

以上所提出的各种协议都不能满足分散无线网络对MAC协议的所有要求，因此本文提出了一种新的协议。算法根据几何分布采用随机长度的突发来重复消除信道访问节点。为了获得期望的相对优先级，基于基本优先级向量提出了一种实现差异化服务的相对优先级机制，从而提高整个网络的信道总利用率。

为便于分析，把本文提出的协议算法称之为重复消除突发和带差异化服务优先级机制(REB & PMDS,repeated elimination bursts and prioritization mechanisms with differentiated service)的无线媒体访问控制协议。

假设信道为分时隙且每个发送方能够在每个时隙中执行以下2种操作之一：载波侦听操作或执行一个短突发或干扰发送。发送方在每个时隙i以P(Ai=tx)=qi和P(Ai=cs)=1-qi=pi随机选择执行哪个动作A。如果发送方侦听到一个空闲信道，它就添加一个计数器IdleSlots。当IdleSlots=h时，则认为已赢得信道并开始发送。算法1为描述REB & PMDS算法的伪代码。

算法1:REB & PMDS

1.侦听信道空闲TIFS

2.IdleSlots=0,i=1

3.whileIdleSlots

4. ifAi=tx then

5. TransmitNoise(τ)

6. else//Ai=cs

7. if busy=SenseChannel(τ) then

8. else

9.IdleSlots=IdleSlots+1

10. end if

11. end if

13.i=i+1

14.end while

15.TransmitMessage(Tm)

REB & PMDS算法的运行示例如图1所示。图中灰色梯形为消除突发，白色梯形为载波侦听操作，宽的深灰色梯形为数据发送。示例中n=6，h=4和q=0.5。最初，所有节点在随机执行载波侦听(Ai=cs)或消除突发发送(Ai=tx)之前等待一个TIFS。在示例中，S2和S5侦听到信道繁忙并离开争用。在接下来的时隙中，S3和S6被消除。剩下的节点S1和S4在第一次消除中存活下来，并进入到第二次节点S1的消除中。S4执行两次额外的消除，直至IdleSlots=h并允许访问为止。

图1 有6个节点的REB & PMDS工作过程

接下来对所提出的REB & PMDS算法性能进行分析。假设信道工作在饱和条件下，没有隐藏终端，信道噪声等不影响结果，所有数据包的长度相同。文中采用的记号及其含义和值如表1所示。

2.1 单次消除

在每次消除中，突发时间最长的节点将存活下来。n个节点间最长突发的期望长度为[16]：

表1 文中采用的记号含义和值(时间单位为μs)

(2)

精确式(2)对于较大的n来说是不实用的，所以排除误差项后消除阶段的期望长度近似为：

(3)

式中,γ=0.577为欧拉常数。在本文的数值示例中，当n>50时采用这个近似式。

n个节点中有m个节点在消除阶段存活下来的概率为[17]：

(4)

对于较大的n近似为：

(5)

式中,δm(x)=1/m!·∑j≠0Γ(m-2jπi/log(q-1))e2jπix且Γ为Γ函数。在本文的数值示例中，当n<10时，可以采用精确式(4)。

2.2 重复消除

通过递归扩展式(4)，可以得到n个节点中有m个节点在第k次消除中存活的概率为：

(6)

发送成功的概率等于h次消除后仅剩下一个节点的概率，即：

pS=p1,h(n)

(7)

第k次消除的期望长度同样可得到如下：

(8)

代入数值可知，对于大多数n值，当q=0.5和h=1时，pS≈0.721。检测到h个空闲时隙后，一个节点成为唯一获胜者的概率为：

(9)

由近似式(9)得到的数值结果与精确式(7)的数值结果很接近，例如，对于n=50时误差在±0.02以内。

2.3 信道利用率

平均信道利用率ρ由一个周期中有用数据传输的持续时间Tm除以该周期的持续时间再乘以该周期中成功发送的概率，即：

(10)

2.4 最佳参数的确定

采用数值技术和式(10)并结合表1中给定的其他一些参数可计算最佳参数h和q。对于给定的h，存在相应的最佳q值。h越低，q越高，反之亦然。对于大范围的n值、h=4和q=0.5可以接近最佳值，在后面的分析和仿真中，除非另有说明，将采用h=4和q=0.5。

2.5 Jain公平性指数

前面分析中的信道利用率与归一化总吞吐量是相同的，即总吞吐量除以调制速率就是信道利用率；
而Jain公平性指数是一种度量公平性的指标，即资源分配的平等性。Jain公平性指数为1表示绝对公平，数值越低(最小值为零)，表示不公平程度越高。Jain公平性指数定义为[18]：

(11)

式中,xi为节点i的吞吐量。

2.6 实现差异化服务的优先级机制

本节通过引入优先级向量将REB & PMDS扩展为一个简单的优先机制，目的是通过相对优先级实现差异化服务。

针对IEEE 802.11网络提出了3种基本的服务机制：设置不同的CW[19]、允许高优先级业务使用较短的IFS 和限制最大传输时间。在IEEE 802.11 e中，所有这些机制都以服务类别的形式组合在一起，每个服务类别都是上述因素的特定组合[20]。在IEEE 802.11中，这种抢占式优先级可以通过2种机制来实现：为每个优先级类别设置最佳争用窗口或为每个类别设置固定争用窗口。

2.6.1 最佳争用窗口

不同的CW可以这样设置：首先计算每个优先级类别的最佳p-坚持传输概率：

(12)

(13)

式中,P为优先级类别的数量，ni为类别i中节点的数量。最后得到期望的争用窗口大小为：

(14)

2.6.2 固定争用窗口

2.6.3 本文提出的差异化服务优先级机制

在本文的REB & PMDS算法中，如果一个时隙为忙，则停留在争用的概率为：

P(停留)=P(停留(A=cs)p+P(停留(A=tx)q

(15)

在基本机制P(停留|A=cs, 信道忙)=0和P(停留|A=tx)=1中，可得到P(停留|信道忙)=q=0.5。调整两种“停留”概率中的任何一种，如通过给予节点额外的生存期，将意味着在无线媒体中可用的信息与某些节点的内部状态之间存在差异，这样就得到一个基于对每个节点调整q的机制。由于争用中的时隙数量事先是未知的，具有不相等但固定的q值将使预测一类节点的最终优先级变得困难。因此，我们选择通过为每个节点和时隙分配不同的q值来实现。

分析表明，具有q={1,0.5,0.5,…}的节点在第一次消除中获胜的概率是原来的2倍，它相当于2个虚拟节点。基本优先级向量为q={0.5,0.5,…}。对于任意的q向量，获胜概率即相对优先级可以计算为：

(16)

式中,k为消除长度。注意，qi(j)(j>k)的元素对最终结果没有任何影响。为了简化分析，假设对于任意的j≤≈k，qi(j)=0.5。

(17)

为便于比较，对提出的REB & PMDS稍作改进，得到一种称为REB & PMDS-β的改进形式。在REB & PMDS-β中，用合适的RTS数据包取代消除突发，把每个时隙分为2部分。第一部分中每个节点随机选择发送或不发送一个RTS数据包。非发送节点侦听信道并在信道忙时离开争用。第二部分中节点视情况发送CTS数据包，除非一个节点接收到一个CTS数据包，否则它将在最大h次消除内保持争用。

首先采用在饱和条件下的仿真来验证解析模型，然后通过在可变负荷条件下的仿真来扩展研究，并在信道利用率和公平性方面与IEEE 802.11、REB & PMDS-β和DQRAP-WN的性能进行比较。

3.1 仿真环境及模型

采用GloMoSim仿真器环境。对于物理层建模，采用一个没有额外衰落的简单双射线传播模型，仿真区域为边长=200 m的正方形。对于不同仿真情形，发送方的数量n可变。假设没有移动性，且在仿真区域内随机设置每个发送方的位置。更多仿真参数见表1；
每个发送方根据泊松过程发送数据包，速率为每秒发送λ个数据包。对于每次发送，接收方都是从每个发送方的邻居中均匀选择的。

3.2 仿真结果

图2(a)为本文REB & PMDS协议算法与DQRAP-WN、EY-NPMA和IEEE 802.11协议的信道利用率的解析计算比较结果，图2(b)为在饱和条件下，随着竞争发送方数量的增加，对于REB & PMDS、REB & PMDS-β、DQRAP-WN和IEEE 802.11的信道利用率的实际仿真结果。其中EY-NPMA值与其他协议采用相同的时隙长度、帧间间隔、数据包长度和开销；
从图2可见，REB & PMDS和IEEE 802.11的分析结果与仿真结果吻合较好，分析模型对REB & PMDS的仿真结果有轻微高估。当存在许多节点时，分析模型低估了IEEE 802.11的信道利用率。这是因为该模型没有考虑到所有影响IEEE 802.11性能的相关参数，例如扩展的IFS (Extended IFS,EIFS)。图2(a)中的DQRAP-WN是对仿真DQRAP-WN结果的良好预测器。总之，仿真结果验证了分析的正确性。

从图2(b)还可看见，当n增加时，REB & PMDS和DQRAP-WN的性能稳定，而对于IEEE 802-11和REB & PMDS-β，信道利用率略有下降；
当n较小时，DQRAP-WN有较小的下降。这是反馈机制的结果。如果一个节点在另一个时隙发送数据，那么它只能为一个小时隙提供反馈。如果所有节点都选择相同的小时隙，且在处理队列或传输队列中没有节点，那么就不会有任何节点为特定的时隙提供反馈。当n很小时，这种情况更有可能发生。结果是不正确的反馈导致不连贯的队列状态，最终导致数据时隙碰撞。

图2 DQRAP-WN、IEEE 802.11、REB & PMDS和 REB & PMDS-β的信道利用率比较

图3为DQRAP-WN、REB & PMDS-β、REB & PMDS和IEEE 802.11在饱和条件下的公平性随时间的收敛情况。DQRAP-WN几乎很快达到理想的公平。采用FIFO队列的全局连贯状态的结果。其他3个协议收敛到大致相同的公平性水平，但IEEE 802.11收敛较慢。在引言部分讨论了IEEE 802.11协议中的公平性问题。值得注意的是，尽管每个协议的公平性收敛速度或多或少有些慢，但相对排序是相同的。还应当注意到，对于所有协议，服务的数据包的数量是不一样的，因为吞吐量是不一样的。采用服务的数据包数量而不采用运行时间不会改变协议的相对排序。

图3 Jain公平指数作为时间的函数

图4为对于100个节点时，当总负荷增加时的总吞吐量变化。从图5可见，REB & PMDS、REB & PMDS-β和DQRAP-WN的总吞吐量都呈线性增加，直到饱和，然后保持稳定；
另一方面，IEEE 802.11的吞吐量在达到饱和点后逐渐降低。REB & PMDS达到饱和点的时间要长得多。

图4 n=100时总吞吐量作为流量负荷的函数

对于优先级机制，仿真比较3种方法：可变q的REB & PMDS和IEEE 802.11中的最佳CW和固定CW。考虑两类节点，类型1具有基本优先级，类型2具有优先级r21=5.589 5，这种选择能在两个节点之间获得相对优先级。

图5 有2个优先级类别的总信道利用率和 每个类别的信道利用率

仿真考虑了2种情形，结果如图5(a)和(b)所示。图中对于每种协议从上到下依次为：总信道利用率、高优先级业务信道利用率和低优先级业务信道利用率。可以看到，在这2种情形，REB & PMDS和最佳CW的总信道利用率都是鲁棒的，但REB & PMDS略好一些。在固定CW的情形下，IEEE 802.11的总信道利用率迅速下降。

在第一种情形，如图5(a)所示，基本优先级节点数量固定即n1=50，同时在网络中注入越来越多的高优先级节点。在REB & PMDS和最佳CW中，高优先级类别的信道所占的份额越来越大，基本优先级类别保持某个份额。在固定CW的情形下，几乎所有减少的信道利用率都进入了高优先级类别。

在第二种情形，如图5(b)所示，两种类别以相同的速度增加。REB & PMDS和最佳CW在类别之间保持恒定的关系，而固定的CW对于基本优先级类别导致份额不断下降。在维持期望的相对优先级方面，REB & PMDS略优于最佳CW。

本文提出了一种新的无线信道分配协议REB & PMDS。REB & PMDS与EY-NPMA的相似之处在于根据几何分布采用随机长度的突发来消除信道访问节点。不同之处在于突发是未截断的，允许大量的节点，采用不截断的消除和非固定突发概率，允许提供相对优先级，而EY-NPMA仅提供非抢占式的绝对优先级，同时REB & PMDS采用反复消除来微调成功概率。

分析和仿真结果表明，REB & PMDS具有较高的信道利用率和成功概率。与IEEE 802.11相比，REB & PMDS的无记忆特性使得每个争用都独立于之前的争用，因而具有良好的公平性。

对于未来的研究，将考虑隐藏终端条件下的性能并分析通过REB & PMDS的TCP/IP业务。进一步的研究还包括与IEEE 802.11e标准进行比较，即研究如何将REB & PMDS上的多播与IEEE 802.11上的单播结合起来。

猜你喜欢时隙公平性数据包基于Jpcap的网络数据包的监听与分析电脑与电信(2021年9期)2021-12-21高管薪酬外部公平性、机构投资者与并购溢价南开管理评论(2021年1期)2021-04-13基于时分多址的网络时隙资源分配研究舰船电子对抗(2020年2期)2020-06-23复用段单节点失效造成业务时隙错连处理铁道通信信号(2018年9期)2018-11-10SmartSniff网络安全和信息化(2018年4期)2018-11-09一种高速通信系统动态时隙分配设计舰船电子对抗(2016年3期)2016-12-13时隙宽度约束下网络零售配送时隙定价研究广西大学学报（自然科学版）(2016年5期)2016-11-12关于公平性的思考中国卫生(2015年3期)2015-11-19面向多路径并行传输的拥塞控制及公平性华东理工大学学报(自然科学版)(2014年1期)2014-02-27移动IPV6在改进数据包发送路径模型下性能分析电子设计工程(2011年24期)2011-06-09