Ad Hoc网络MAC协议公平性研究.doc
Ad Hoc网络MAC协议公平性研究Fairness of MAC Protocol for Ad Hoc Networks Ni Xiaojun, Wang Yuanyuan, Zhang Yun, Chen Chunling (School of Computer Science & Technology, Nanjing University of Posts Telecom munications, Nanjing, 210003, China) ? Abstract: The fairness of distributed coordination function (DCF) in IEEE802.11 is analyzed. It is pointed out that weaknesses of channel allocation unfairness when using DCF access control scheme due to its inherent nature of binary exponentially backoff algorithm. To address this problem, a self-adapt backoff algorithm, called the LDBSB (load detection based self-adapt backoff), is presented based on two-dimensional Markov chain model. Theoretical analysis and simulation results show that the algorithm improves performances on through-put, delay and fairness compared with the binary exponentially backoff algorithm. Key words: Ad Hoc networks; distributed coordination function (DCF); backoff algorithm; fairness IEEE802.11协议中主要的MAC层访问控制技术被称为分布协调功能(Distributed coordination function,DCF)1。DCF采用了载波侦听多点接入碰撞避免CSMACA(Carrier sense multiple access with collison avoidance)策略,在冲突避免中采用了基于时隙的二进制指数退避策略BEB(Binary exponential backoff)。研究发现,在网络拥塞情况下,采用DCF的网络中,节点在信道争用过程中存在着严重的分配不公问题,部分节点会出现“饿死”现象。文献2,3针对网络拥塞环境,提出了减缓竞争窗口变化速度的算法,减轻了因竞争窗口变化过快造成的不公平现象。但这类算法在网络负载较轻的情况下,由于竞争窗口变化过缓,增加了网络的时延,减少了吞吐量。文献4通过对碰撞概率的分析,提出了根据上次发送是否发生碰撞来动态调整竞争窗口的退避算法,可有效改进DCF时隙选择概率的不均匀性,降低包碰撞概率。文献5通过预测网络节点数,采用动态调整竞争窗口最小值的方法,使新算法能较好地适应网络的负载变化。 本文在文献6采用的基于二维离散时间马尔科夫链模型分析802.11 DCF饱和吞吐量的基础上,针对BEB退避算法可能导致的信道争用时分配不公的问题,提出了一种基于网络负载检测的自适应退避算法LDBSB(Load detection based self-adapt backoff),该算法采用一个新的判断信道拥塞程度的指标,使网络可以根据负载情况动态地调整节点的竞争窗口,从而达到公平分配信道容量,提高网络整体吞吐量,并降低网络传输时延的目的。仿真实验表明,所提算法在上述各方面均有较好的表现。 1 IEEE802.11 DCF公平性分析 由于DCF采用的是CSMA方式的接入技术,因此当发生报文冲突时,发送方必须执行退避算法,延时由“退避计数器”产生的随机退避时间后再进行下一次发送尝试。显而易见,某个节点的退避计数器取值越小,它的发送退避间隔时间就越短,抢占信道的能力就越强;反之,节点抢占信道的能力就越弱。对于这个随机延迟时间,DCF采用了二进制指数退避算法(BEB)来实现。在BEB算法中,设置了退避计数器的取值范围在CWmin到CWmax之间,称之为竞争窗口。节点初次发送报文时,退避计数器初值设置为CWmin,以后每次发生报文冲突时,退避计数器的值加倍,直到达到CWmax为止;而每次报文发送成功后,退避计数器的值则直接恢复到最小值CWmin。这种退避计数器的取值方法有两个明显的缺点,(1)这种算法总是将成功发送数据的节点的退避计数器设为最小值,这样发送数据成功的节点将总是保持最强的信道抢占能力,很容易造成发送数据失败的节点难以竞争到信道而被“饿死”,造成信道分配的严重不公;(2)则是当节点竞争信道成功后,不管信道的拥塞情况,将退避计数器降低为最小值,当节点数较多且每个节点的退避计数器都比较小的时候,将会导致冲突的次数明显增加,降低整个网络的性能。 2 基于负载检测的自适应退避算法 针对802.11DCF在信道拥塞情况下造成的不公平现象,本文将提出一种基于网络负载检测的自适应退避算法LDBSB(Load detection based self-adapt backoff)。该算法通过检测网络负载,决定竞争窗口的变化方式。若信道拥塞,则缓慢减小竞争窗口,降低信道竞争的激烈程度;若信道不拥塞,则加快减小竞争窗口,提高信道竞争的激烈程度。 3 结束语 本文针对采用802.11 DCF的节点在信道接入时的不公平问题,引入了一个判断信道空闲程度的指标f,提出了一种基于网络负载检测的自适应退避算法LDBSB。算法结合二维马尔科夫链模型计算出当网络的吞吐量达到最大值时空闲度f的最优大小f0,并根据信道当前f值与f0的比较判断网络的拥塞程度,据此选择相应的退避参数,动态地调整节点的竞争窗口,达到避免节点“饿死”现象发生,同时提高网络整体的性能。仿真实验表明,所提算法在网络的吞吐量、时延和公平性等方面较原算法有明显的改善。
