一种基于博弈论的DCF信道竞争算法

【摘要】在DCF协议支持TCP流量时，往往不同的流量产生信道分配极不公平的现象，这与DCF算法中阶段二进制指数退避算法有很大关系。博弈论是研究具有斗争或竞争性质现象的数学理论和方法。博弈论考虑游戏中的个体的预测行为和实际行为，并研究他们的优化方法。本文将从退避时隙选择概率分布对DCF性能影响的角度出发进行分析,并在理论分析的基础上提出了一种简单有效的退避时隙选择方案.针对载波干扰给 IEEE 802.11 DCF 协议带来的严重不公平问题，提出了一种基于博弈论的DCF算法。采用VC++对该算法进行仿真。仿真证明，该算法能有效地改善 IEEE 802.11 DCF 协议的公平性，并且没有引起网络吞吐量的严重下降。 【关键词】DCF协议;公平性;博弈论;阶段二进制指数退避算法； DCF信道竞争算法 ?1.1.1ad-hoc网络简介 ???? 我们经常提及的移动通信网络一般都是有中心的，要基于预设的网络设施才能运行。例如，蜂窝移动通信系统要有基站的支持；无线局域网一般也工作在有AP接入点和有线骨干网的模式下。但对于有些特殊场合来说，有中心的移动网络并不能胜任。比如，战场上部队快速展开和推进，地震或水灾后的营救等。这些场合的通信不能依赖于任何预设的网络设施，而需要一种能够临时快速自动组网的移动网络。Ad hoc网络可以满足这样的要求。 ??? Ad hoc网络的前身是分组无线网（Packet Radio Network）。对分组无线网的研究源于军事通信的需要，并已经持续了近20年。早在1972年，美国DARPA（Defense Advanced Research Project Agency）就启动了分组无线网（PRNET,Packet Radio NETwork）项目，研究分组无线网在战场环境下数据通信中的应用。项目完成之后，DAPRA又在1993年启动了高残存性自适应网络（SURAN,SURvivable Adaptive Network）项目。研究如何将prnet的成果加以扩展，以支持更大规模的网络，还要开发能够适应战场快速变化环境下的自适应网络协议。1994年，DARPA又启动了全球移动信息系统（GloMo,Globle Mobile Information Systems）项目。在分组无线网已有成果的基础上对能够满足军事应用需要的、可快速展开、高抗毁性的移动信息系统进行全面深入的研究，并一直持续至今。1991年成立的IEEE802.11标准委员会采用了“Ad hoc网络”一词来描述这种特殊的对等式无线移动网络。 ???? 在Ad hoc网络中，结点具有报文转发能力，结点间的通信可能要经过多个中间结点的转发，即经过多跳（MultiHop），这是Ad hoc网络与其他移动网络的最根本区别。结点通过分层的网络协议和分布式算法相互协调，实现了网络的自动组织和运行。因此它也被称为多跳无线网（MultiHop Wireless Network）、自组织网络（SelfOrganized Network）或无固定设施的网络（Infrastructureless Network）。我们经常提及的移动通信网络一般都是有中心的，要基于预设的网络设施才能运行。例如，蜂窝移动通信系统要有基站的支持；无线局域网一般也工作在有AP接入点和有线骨干网的模式下。但对于有些特殊场合来说，有中心的移动网络并不能胜任。比如，战场上部队快速展开和推进，地震或水灾后的营救等。这些场合的通信不能依赖于任何预设的网络设施，而需要一种能够临时快速自动组网的移动网络。Ad hoc网络可以满足这样的要求。 ? 1.1.2基本接入方式 ??? 当工作于基本接入方式时,节点在检测到信道空闲时间超过DIFS (distributed inter frame space)后发送分组;若信道忙,节点在等待信道空闲DIFS后将随机选择一个退避时延(退避时隙值)并启动退避计时器,等待该退避时延后才发送分组.退避计时器在信道空闲时随时间递减;信道忙时将挂起,直到信道空闲时间超过DIFS后才恢复递减;当退避计时器 减为0时节点开始发送分组.退避时隙值在离散区间[0,CW]内按均匀分布随机选择,并以物理层定义的时隙宽度Tslot为单位.CW又称为竞争窗口,竞争窗口初始值为Wmin,每次发送失败,竞争窗口Tbackoff= [Rand(0,CW)]@Tslot(1)都加倍,并重新开始上述过程竞争接入信道,直到发送成功或达到最大竞争窗口Wmax.这里Wmax=2m(Wmin+1)-1,m为最大退避阶数,Wmin和Wmax具体值由物理层决定.源节点在发送分组后,要等待目的节点发送确认接收的ACK帧;而目的节点接收到正确的分组后,则要在等待信道空闲SIFS后向源节点发送ACK帧,对接收到的分组进行确认[1]. 1.1.3 RTS/CTS方式 ??? 除了基本接入方式,DCF还提供了RTSPCTS方式来增强基本CSMAPCA的功能.源节点在发送分组前先发送RTS控制帧,目的节点在收到RTS控制帧后等待信道空闲SIFS后发送CTS控制帧回应;若源节点未能收到CTS帧,表明RTS控制帧发生碰撞,源节点必须重传RTS帧.RTSPCTS帧交换成功后,源节点在检测到信道空闲SIFS之后就可以开始发送数据分组,并等待ACK确认[2].由于在整个传输过程中,碰撞只可能发生在RTS帧期间,而RTSPCTS控制帧和数据分组相比长度较短,可能发生碰撞的持续时间短,因此和基本接入方式相比,RTSPCTS方式能够有效降低碰撞发生的概率. 1.2DCF性能分析 ???? 802.11 DCF采用了一种随机访问机制.当移动终端有新的数据包需要发送时,它首先监测信道,如果信道持续空闲一段时间)))在802.11中,称这段时间为/DCF帧间间隔0时间(DIFS:DCF InterFrame Space),则发送数据包;否则,移动终端继续监测信道,在忙时监测期间,当信道空闲的总时间等于DIFS时,移动终端在发送数据包之前选择一随机延迟时间(这就是DCF的冲突避免特性).另外,为了避免某移动终端长时间占用信道,移动终端在两次连续的数据包发送之间必须进行随机延迟. ???? 本节将扩展文献[2]提出的理论模型,分析退避时隙选择概率分布对802.11DCF性能的影响,并提出一种简单有效的退避时隙选择方案.扩展模型和文献[2]的模型基于同样的前提假设:(1)发送的分组发生碰撞的概率p恒定且相互独立. (2)各节点均工作于饱和状态,即各节点的发送队列中始终有分组等待发送.