通信工程毕业论文_k轮冲突分解方法的性能分析.docx

1、本科毕业论文（20 届）k 轮冲突分解方法的性能分析所在学院 专业班级 通信工程 学生姓名 学号 指导教师 职称 完成日期 年 月 摘要在多媒体接入控制（MAC）协议中,冲突分解机制是其非常重要的一部分。冲突分解机制的好坏对于多媒体接入控制（MAC）协议的性能有着重要的影响，例如，吞吐量、时延、等。在目前应用较广的多媒体接入控制（MAC）协议中，如 IEEE 802.11DCF，它采用了一种较为简单的冲突分解机制二进制指数退避(BEB )机制。在竞争节点数目较小的无线网络中，二进制指数退避(BEB )机制可以尽最大的努力对数据进行发送以让各个节点共享无线信道，表现出了较为良好的性能。但是，随着

2、无线网络中节点数目的增加，各个节点对共享信道的竞争加剧，二进制指数退避(BEB)机制的调节效率逐渐变差。其性能变差的主要原因是各节点的冲突碰撞率的升高。为此，我们设计了一种新的冲突分解机制K 轮冲突分解方法（K-EC） 。在冲突分解的过程中，K-EC 表现出了令人满意的高效性和可靠性。更重要的是，K-EC 对网络中竞争节点的数目并不敏感。这个特点使得其普遍适用于各种不同大小的网络，有利于广泛的推广。本文中的模拟结果显示，K-EC 对于信道的竞争解决是一个非常有用的帮助。与IEEE 802.11DCF 比较而言，它在吞吐量、时延和公平性 MAC 协议性能指标上占有明显的优势。关键词：无线网络；M

3、AC 协议；接入机制AbstractThe collision resolution algorithm play a important role in the media access control(MAC) protocol. It has a great impact on the performance of MAC, for example throughput, delay and so on. In the current widely used protocols, for example, IEEE 802.11DCF,it adopts a simple collisi

4、on resolution algorithm-the Binary Exponential Backoff(BEB).In the small networks containing a small numbers of contending nodes, BEB can try its best effort to transmit data and has a good performance. However, BEB suffers from bad efficiency as the network size increase. The reason is that the inc

5、reasing number of contending nodes incurs a high collision rate. To solve the problem, we design a new resolution algorithm, k-round elimination contention(K-EC).In the process of elimination contention, K-EC perform a high efficiency and good reliability. More important, it is not sensitive to the

6、number of contending nodes. This makes it widely used in different size networks so that it will become popular in future. In this paper, simulation shows K-EC has better performance than IEEE 802.11DCF in the metrics, such as throughput, delay and fairness.Keywords: Wireless communication, networks

7、, access schemes目录第 1 章 绪论 .11.1 引言 .11.2 冲突分解技术的发展与现状 .11.3 论文的选题与意义 .21.4 论文的总体结构与研究内容 .2第 2 章 MAC 协议中的冲突分解机制 .22.1 概述 .22.2 MAC 协议的种类 .32.3 目前冲突分解机制的种类及存在的不足 .3第 3 章 K 轮冲突分解机制（K-EC） .43.1 原理的由来 .53.2 K 轮冲突分解机制的具体原理 .53.3 C-Slot 的时间长度和 KIFS 的间隔长度 .83.4 最大竞争空间 .93.4.1 扩大 CS 的原因 .103.4.2 m 的最优值 .103

8、.5 一个 CRP 结束后成功发送数据的概率 .113.6 CRP 的平均长度 .123.7 进入到下一轮竞争的平均节点数量 .133.8 网络吞吐量 .153.9 时延 .153.10 K-EC 机制中最佳竞争轮数 k 的选择 .163.11 本章小结 .19第 4 章 性能分析 .194.1 碰撞率 .194.2 网络吞吐量 .204.3 公平性 .244.4 时延 .254.5 本章小结 .25结论 .26参考文献 .27致谢 .28附录 .291k 轮冲突分解机制的性能分析第 1 章 绪论1.1 引言无线局域网的历史可以追溯到四十多年前，当时美军开始采用无线信号传输资料，这让很多学者获

9、得了灵感，1971 年夏威夷大学的研究员开创了基于封包式技术的无线电网络技术无线电通信网络。这可以算是早期的无线局域网络。这最早的 WLAN 包括了七台计算机，横跨四座夏威夷的岛屿。从那时开始无线局域网络可以说是正式诞生了。经过几十年的发展，WLAN 获得了极大的发展。它们被广泛的应用于机场、酒店、校园、商场、火车站等公共场所，这极大地方便了我们的工作生活。我们的手机、电脑甚至是家用电器都离不开 WLAN 的身影。任何事物都具有两面性，WLAN 所依靠的媒介就是空中的无线信道，不同的网络所依靠的信道频率资源却是一样的，资源的有限必然会引起用户之间的竞争。所以随着网络内的用户设备越来越多，如何让

10、它们高效的运作已成为一个亟需解决的问题。其中需要首先解决的是不同设备间发送或接收数据的冲突问题，即多址竞争接入问题。所以，冲突分解技术成为进一步发展无线局域网需要解决的技术难题。1.2 冲突分解技术的发展与现状目前被广泛使用的是由 IEEE 提出的 802.11 系列协议。他们在 MAC 层中都采用了两种基本的冲突分解机制，即分布式协作机制和中心控制式机制。不过，在实际当中，中心控制式机制是依靠分布式机制建立起来的，所以分布式协作机制是重中之重。它被用来解决协调各个发生冲突的节点有序的利用共享介质。但在网络设备数量快速增长的今天，其出现了较高的碰撞率而导致其在吞吐量、时延、公平性等方面的性能下

11、降较为明显 1。因此，又出现了许多其他的机制来代替分布式协作机制（后续章节介绍） ，但无论随着分解机制如何发展，基于竞争机制的 MAC 协议所包括的过程都会包含下列几部分 载波监听（Carrier Sense，CS）,感知载波状态的的能力。 冲突避让机制（Collision Avoidance，CA） 。 冲突检测（Collision Detection，CD ）,检测冲突的能力。因为在无线环境当中，发方无法有效的辨别周围环境当中的信号是噪声信号还是自己发射的信号，所以在大部分现有的无线 MAC 协议中都不包括这一部分。2 应答机制（ACK） ，它可以被用来辨别信息是否发送成功。 退避重传机制

12、，冲突发生后发生冲突的节点等待一段时间重新发送信息。1.3 论文的选题与意义随着无线局域网的快速发展，有限的资源频率变的越来越宝贵，如何在现有的资源条件下，尽最大可能提高无线网络的各项性能已成为研究的热点。那么作为解决该问题的关键冲突分解机制的设计，也已成为人们争相研究的领域。所以本文也从解决冲突分解机制设计的问题出发进行撰写。本文的意义在于设计了一种较为新颖的机制。它将整个竞争周期的长度进行固定，这样就避免了 BEB 算法的窗口大小的不固定给其造成的效率低下；它在安排每一个节点进入下一轮竞争时，取消了像 CONTI2算法那样固定的概率，而是变为随机的选择进入下一轮竞争。以上两点都极大的提高了

13、机制的性能。1.4 论文的总体结构与研究内容第一章为绪论，介绍了无线局域网的发展及背景，提出无线局域网发展所面临的问题，进而引出本文的研究方向和内容，并介绍了本文的结构安排。第二章介绍了截至目前，人们所提出几种应用范围较广的冲突分解机制，并借助相关文献指出它们各自的长处和不足之处，以便为提出新机制提供解决思路。第三章主要介绍了 K-EC 机制的由来及原理，并将原理进行了数学模型化提出竞争矢量的概念，并通过理论分析的形式对机制中的各个参数，如 m、k、各时隙持续时间、数据成功发送概率等，进行了规定。为下一章的仿真提供理论依据。第四章主要是对 K-EC 机制的各项性能，如吞吐量、时延、碰撞率等进行

14、了仿真。以与现有的几种机制作比较，来证明上一章的理论分析的正确性以及 K-EC 机制的优越性。第五章对本文内容进行归纳总结，并得出结论。3第 2 章 MAC 协议中的冲突分解机制2.1 概述无线网络中的 MAC 协议主要解决多用户协调接入和使用信道的问题。当多个用户尝试通过共享的无线介质与其他用户进行通信联系时，这时会产生一个棘手的问题，那就是让谁先占用信道资源，什么时间占用，占用多长时间，当某一用户占用完后，其他用户如何能检测到信道资源此时可以被利用等等。因此，正如开头所说的那样，MAC 协议便是为解决这个问题而设计的，其中针对以上问题，在 MAC 协议中最为重要的部分就是冲突分解机制。一个

15、好的 MAC 协议可以让网络的适应性更强，容量更大，效率更高。所以，目前使用较为广泛的MAC 协议的主要设计目标如下所示： 尽量使每一个用户较为公平的占用共享介质。 使共享介质得到充分利用，信道利用率达到最大化。 保证服务质量（Quality of Service,QoS ） 。 高效的利用有限的能量。 最大程度的减小一个节点从请求发送到能够成功发送信息的时间间隔。 以上网络目标的实现与否，MAC 协议中的冲突分解机制的性能对其有着决定性的作用。冲突分解机制的设计也是基于竞争接入无线网络中需要解决的最基本问题。2.2 MAC 协议的种类无线网络中的 MAC 协议大致可以分为两大类。一种是基于预

16、约机制的 MAC协议，另外一种是基于竞争机制的 MAC 协议。基于预约机制的 MAC 协议可以预约特定的资源来传输相应的分组数据。预约的方式可以是再设计协议时，已经固定好的，也可以是根据网络中的某一指标进行动态的自适应调整。基于预约机制的 MAC 协议包括可以给一个节点分配一段固定的时间，如时分多址（TDMA） ，或者分配某一特定的频率，如频分多址（FDMA） ，也可以分配一段独一无二的编码，如码分多址（CDMA） 。基于预约机制的 MAC 协议通常会依赖于一个中央控制中心来实现，如一个接入点（Access Point，AP）或者一个基站（Base Station，BS） 。利用基于预约机制的

17、 MAC 协议的网络的容量常取决于这个网络所拥有的资源，这些资源包括频率、编码、时间。与基于预约机制的 MAC 协议不同的是，基于竞争机制的 MAC 协议可以让所有的网络节点随机的接入共享介质。这种机制更多的是以一种分布的方式进行工作，而不是像基于预约机制的 MAC4协议那样，依靠一个中央网络协调中心进行工作。由于其在实际当中实现较为简单，相应的便是使用成本较为低廉。所以使用此类协议的产品已经占据了无线网络（WLANs ）的大部分市场份额。基于竞争机制的 MAC 协议的分布特性也是无线自组织网络（Ad hoc networks）所期望的，因为这类网络同样是没有中央协调控制点的。然而，随着网络竞

18、争节点数目的增加时，基于竞争机制的 MAC 协议，如 IEEE 802.11 MAC，会展现出很差的性能。造成这个现象的主要原因在于冲突分解机制的效率低下。2.3 目前冲突分解机制的种类及存在的不足 最先出现的冲突分解机制是 Pure ALOHA3和 Slotted ALOHA4。在 Pure ALOHA 当中，每一个节点只要有需要发送的数据，便会在不考虑介质是否空闲的情况下，立即接入介质进行发送。Pure ALOHA 机制非常的简单，但也由于其简单性造成了很高的节点间的碰撞率。后来人们又发明了 Slotted ALOHA，其主要差别在于它将时间划分成了很多时隙，只允许每一个节点在时隙的开始发

19、送数据，不能再时隙的开始之后发送。一段时间之后，人们为了更少的减少节点间的冲突，又引入了载波监听功能。基于这一功能，一个应用更为广泛的 MAC 协议被提出，即著名的载波监听多址接入（CSMA）协议。在 CSMA 当中，一个节点只有在检测到介质为空闲时才能发送信息，因此避免了其他想要发送数据节点的干扰。一种专门解决隐蔽节点问题的机制被提出，即 MACA（multiple access with collision avoidance） 。在 MACA 中有一个两步握手协议，即请求发送/清除发送（RTS/CTS） ，它们在数据发送前被发送。这种协议被应用于 CSMA/CA 中来辨别信息是否发送成功

20、。IEEE 802.11DCF 便是利用 CSMA/CA 来设计的。无论是 MACA ,CSMA/CA,还是 IEEE 802.11DCF，它们都采用了二进制指数退避(BEB )机制来解决冲突的问题。在二进制指数退避(BEB )中，只要冲突发生，它的竞争窗大小就会加倍，直到达到在先前设定的最大值。如果冲突被解决，成功发送数据之后，窗口的大小便会回到设定的最小值。这样的机制总会有利于最后成功发送数据的节点，进而导致不公平性 5。 因此，在6中 Bharghavan 提出了一个新的机制叫做 MACAW7。在MACAW 中，一种成指数增加线性减小的机制代替二进制指数退避(BEB)来控制竞争窗的大小，

21、因此减少了冲突，提高了性能。除了上述意外，前人们还以各种网络性能指标为目标提出了多种多样的机制，但都相应的存在着各种各样的不足，如 Cali8通过检测不断改变的节点数量来改变竞争窗口的大小以使吞吐量达到最大，但检测节点数量确实很困难的；Kwon提出快速冲突分解（FCR ）机制 9。5尽管它能很大程度上提高信道利用率，但却加剧了不公平性。Sobrinho 和Krishnakumar 提出了叫做 Black Burst10的机制，旨在减小发送信息时延，然而网络的增长和发送速率的增加，网络吞吐量急剧减小。为了更好的理解本文，这里着重介绍由 Abichar 和 Chang 提出的固定时间冲突分解机制（

22、Constant-time contention resolution， CONTI） 。CONTI 可以通过一个竞争时隙将淘汰一部分参与竞争的节点。这个淘汰的过程是通过一个布尔数学变量实现的。通过选择合适的参数，CONTI 可以实现快速冲突分解。然而 CONTI 会造成一个严重的问题，我们将其称为“ 冲突僵局 ”。按照 CONTI，一个冲突分解周期（Contention Resolution Period，CRP）开始于分布式协作模式帧间隔（DIFS ） ，终止于最后一个为被淘汰的胜利者从成功发送信息或者所有参与竞争的节点都被淘汰。每一个节点通过以随机概率发送一个称为“尝试比特”的比特数对共

23、享介质进行阻塞或者监听。如果一个节点监听到共享介质状态为繁忙时，便会自动退出本次竞争，即前面所说的被淘汰。当然，如果一个节点成功阻塞了共享介质，便会自动进入下一个竞争时隙，这意味着其成为本轮竞争的胜利者。如果在一个竞争时隙中，没有节点选择阻塞共享介质，那么所有的节点都会自动进入下一轮的竞争时隙。因此在一个冲突分解周期（CRP）内，如果有连续三个竞争时隙没有节点选择阻塞共享介质，会造成冲突分解失败，即前面所述的“ 冲突僵局 ” 。因为在 IEEE 802.11 中 DIFS 的时间长度是短于三个时隙的，这造成了一个新的冲突分解周期（CRP）将会开始。同时会迫使目前的冲突分解周期（CRP）结束，结

24、果就是在未能选择出最后的胜利者进行发送数据的情况下，便进入了下一个冲突分解周期（CRP） 。因此造成发送数据失败，而共享介质却还是空闲的。如果这样的冲突分解周期（CRP）持续发生这会导致任意一个节点不能发送数据，进而使的网络吞吐量变差，造成“ 冲突僵局 ”。换句话说，冲突分解周期（CRP）无限长的反复出现。以上所述的节点发送数据失败的问题可以通过减小冲突分解周期（CRP）的长度或者提高发送“尝试比特”的概率到100来消除。然而，这会以降低CONTI的效率作为代价。因为，为了彻底的解决这个问题，如果在目前竞争时隙中，共享介质没有被阻塞，所有的节点不得不在进入到下一个竞争时隙之前阻塞共享介质。第 3 章 K 轮冲突分解机制（K-EC）在本章中，我们将介绍所设计的 K 轮冲突分解机制（K-EC）的具体原理。我们所设计的 K-EC 将提供一个快速冲突分解的算法，并且不会产生上章所述的“冲突僵局 ”问题。每轮竞争中包含着多个竞争时隙。在一定长度的冲突分解周期（CRP）内，我们以降低碰撞率为目标，对每一轮竞争的长度进行了优化。更重要的是，这个特定的数值与网络中的竞争节点的数量、分组数据的大小等均无