无线网络中的延迟带宽产品对吞吐量的影响

© 2014年。由爱思唯尔公司出版信息工程研究院负责评选和同行评议可在www.sciencedirect.com上在线获取ScienceDirectIERI Procedia 10（2014）153 - 1592014未来信息工程在具有大延迟带宽积的王嘉棉，刘卫东 *清华大学计算机科学与技术系，北京100084摘要传统上，带宽延迟积可以用来衡量两个节点之间的网络“管道”的容量。然而，在多跳无线网络中，带宽延迟积不能准确反映网络状况。在本文中，我们定义了一个新的度量称为延迟带宽产品（DBP）的无线网络，它衡量的能力，一跳管道在无线网络中。具有大DBP的无线网络可以具有比基于传统理解的吞吐量更大的吞吐量。我们提出了一种调度算法的目的是利用大的DBP在无线网络中。然后，我们设计模拟，以找出有多少吞吐量增益可以在无线网络中实现，小的DBPs和大的DBPs分别。仿真结果表明，我们可以实现显着的吞吐量增益在无线网络与大DBP。© 2014作者。由爱思唯尔公司出版 这是一篇基于CC BY-NC-ND许可证的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/3.0/）。信息工程研究院负责评选和同行评议关键词：无线网络;无线传感器网络;吞吐量;延迟带宽积1. 介绍传统上，带宽延迟乘积（BDP）用于测量端到端网络管道的容量[1]。它被定义为数据链路的容量与其端到端延迟的乘积。BDP是传统网络性能的关键因素;例如，在具有大BDP的网络中，标准TCP需要电子邮箱：wangjm11@mails.tsinghua.edu.cn，liuwd@tsinghua.edu.cn。2212-6678 © 2014作者由爱思唯尔公司出版 这是一篇基于CC BY-NC-ND许可证的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/3.0/）。信息工程研究所负责的选择和同行评审154Jiamian Wang和Weidong Liu/IERI Procedia 10（2014）153Fig. 1.广播域中的三个节点（a）和传输调度（b）。可以验证所有数据包都可以成功发送和接收，没有任何冲突。以充分利用底层可用带宽[2]。然而，一些无线网络采用“逐跳”传输方案而不是“端到端”方案，例如无线传感器网络。因此，传统的带宽延迟乘积不能准确反映无线网络的性能。在本文中，我们定义了一个新的概念称为延迟带宽产品（DBP）的无线网络，它被定义为产品的一跳传播的平均延迟和带宽的无线网络。它测量无线网络中一跳管道的容量。在具有大DBP的无线网络中，即使是一跳管道也可能包含多个同时传播的分组。此外，由于大多数无线传感器网络采用逐跳传输方式，DBP可能是影响网络性能的关键因素。传统上，我们认为无线网络中单个广播域内的节点在每个分组传输时间（PTT）最多可以发送和接收一个分组[3]。在这项工作中，我们发现具有大DBP的无线网络可以具有比传统理解的吞吐量更大的吞吐量。由于即使是单跳管道也能够包含多个同时传播的数据包，因此我们可以利用它。图1（a）中的例子直观地展示了研究结果。三个节点A、B和C在同一广播域中。每两个节点之间的传播延迟是一个PTT。在以PTT为单位将时间划分为连续时隙之后，考虑三个传输：在时隙0中从A到B的分组#1，在时隙0中从B到A的分组#2，以及在时隙1中从C到A的分组#3。它很容易验证所有的数据包可以成功地发送和接收没有任何冲突，如图所示。1（b）.这个例子意味着我们可以通过使用大的DBP来实现吞吐量增益。然而，这个例子太理想化了，不能应用于实际情况，原因有二。首先，节点必须小心放置;其次，即使节点放置得很小心，位置的微小移动也会破坏传输。幸运的是，我们在第三节中提出了一种新的传输调度算法，它不仅适应于任意节点位置，而且对位置移动具有容忍性。我们现在讨论的无线网络，可以有一个吞吐量大于一个基于传统的理解。令Δ表示延迟带宽积。为了简单起见，我们考虑以数据包为单位而不是以比特为单位进行分组，并且我们假设每个数据包都具有相同的200字节长度。显然，图1中的场景可以发生，当且仅当假设1。我们从IEEE802.11b/g网络开始，它的传播速度为3 ×108 m/s，平均带宽通常小于50 Mbps，两个相邻节点之间的平均距离小于100 m。DBP小于0.01包。由于非常小的误差，图1中的场景无法构建。我们继续寻找其他无线网络与WiFi1。通常，大的DBP可以由大的传播延迟或大的带宽引起。大的传播延迟可以进一步由长距离或远距离引起。传播速度低。我们可以举几个例子。航天器网络。在航天器网络[4]或行星际互联网中，传播速度为3 ×108 m/s，平均带宽为200 kbps，两个相邻节点之间的平均距离大于Jiamian Wang和Weidong Liu/IERI Procedia 10（2014）153155图二、一个例子表明，吞吐量增益大于零总是存在于无线网络中，无论多小的干扰。5，000km时，DBP的传输速率约为2个包。大的DBP主要是由节点之间的长距离引起的。水下声学网络。在1,500 m/s的非常低的传播速度下，平均带宽约为20 kbps，两个相邻节点之间的平均距离约为1200 m [5]，DBP的传输量约为10个数据包。大的DBP主要由大的传播延迟引起。因此，可以在各种场景中实现更高的性能。在这项工作中，我们试图提供一个新的理解DBP在无线网络中，并揭示其对吞吐量的影响。我们的贡献是三方面的。首先，我们揭示了在各种无线网络中可以实现比传统理解的吞吐量更大的吞吐量，这与延迟带宽积（DBP）密切相关，DBP是我们为无线网络定义的一个新度量，用于测量无线网络中一跳管道的容量。其次，针对无线网络中具有大DBP的单个广播域，提出了一种新的调度方案，该方案可以利用大DBP。第三，我们建立了仿真，并分析了一个大的DBP如何提高网络的性能。本文的其余部分组织如下。第2节揭示了DBP对吞吐量的影响。在第3节中，我们提出了一个调度算法，利用大DBP在无线网络中。第4节模拟DBP如何影响吞吐量。最后，本文在第五部分结束。2. 延迟带宽积一个主要的问题是，为什么大的延迟带宽积扩大在无线网络中的吞吐量。为了简单起见，我们在单个广播域中考虑它。首先，我们提出几个限制。为了成功地接收分组，接收器必须花费一个PTT来接收分组。在此期间，不允许其他信号干扰接收器。此外，来自发射机的分组迟早会干扰PTT的其他节点，除了目标节点。由于DBP较大，某些约束会有所不同。首先，一个节点可以发送数据包，同时受到非目标数据包的干扰，这称为干扰发送。此外，多个干扰可能重叠在一起，这称为干扰重叠。干扰传输和干扰重叠都将使吞吐量增益成为可能。例如，在图1（b）的时隙#1中，我们可以看到干扰重叠--来自节点A和B的干扰在节点C处重叠在一起。此外，我们可以看到干扰传输-当节点C受到干扰时，它正在传输而不是什么都不做。一个关键问题是延迟带宽积如何影响我们可以实现的吞吐量增益通过下面的两个定理，我们给出了吞吐量增益和DBP之间的定量关系定理1. 对于任何一个网络，如果网络的吞吐量大于0，那么吞吐量增益的情况总是存在的。证据我们只需要构建一个场景，该场景可以在任何情况下都获得吞吐量增益。考虑具有λ 1/2的情况，因为它可以应用于λ> 1/2的任何情况。”考虑下面的例子，在一个线段的长度为a= 1，如图所示二、这里节点A，B，C156Jiamian Wang和Weidong Liu/IERI Procedia 10（2014）1534作者姓名/ IERI Procedia 00（2014）000图三.两个数据包的同时传输时间大于1/2。D、E、F和G分别位于位置0、a/9、2a/9、6a/9、7a/9、8a/9和a。每个箭头表示分组传输。传输从左侧时间轴中给定的时间开始。这里，四个数据包将在4 - 8a/9内成功发送和接收。因此，吞吐量增益为4/（4 - 8a/9）-l> 2a/9。因此，对于任何n> 0，具有较大吞吐量的情况总是存在。即使在DBP很小的网络中，也总是可以获得吞吐量增益，尽管它可能很小。此外，当DBP达到零时，增益也接近于零事实上，我们发现，可实现的最大吞吐量增益受到DBP的限制，DBP在下一个定理中给出。定理2. 当 吞吐量为”1/2时，最大吞吐量增益不超过2dB。证据首先，我们证明了矛盾的同时传输时间为任何两个数据包应不超过100。假设我们有两个数据包，如图所示 3，并且它们的同时传输时间T大于1，例如T = 1 + 1，0，<”1 - 1（当它们在同一时刻开始传输时，T = 1，1 - 1）。 现在考虑时间t，它们最后一次同步传输时间的开始时刻。 分组#1和分组#2的接收器在t时必须接收分组#1的信号，原因是在t时分组#1的第一比特已经被传播超过1/4，这意味着在单个广播域内具有大小1/4的所有点已经接收到第一比特。同时，在t处的分组#1的发送器仍在发送其剩余比特。因此，在t时，分组#1和分组#2的接收器必须接收分组#1的信号类似地，分组#1和分组#2的接收机在t时必须接收分组#2的信号 因此，对于分组#1和分组#2的两个接收器，在t处发生冲突。 因此，任何两个数据包的同时传输时间不应超过1/2。现在，作为1/2，很容易知道最多两个分组可以同时传输分组。否则，必须有两个数据包的同时传输时间大于1/2。此外，任何分组最多可以使其第一个和最后一个定时器与其他分组同时发送信号。因此，网络在平均1毫秒的时间间隔内最多只能传输一个数据包。因此，吞吐量增益不超过1/（1-λ）-1 = λ/（1-λ）λ2 λ，当λ= 1/2时。总之，DBP是无线网络中吞吐量增益的关键影响因素3. 调度算法对于具有大DBP的无线网络，可以增大吞吐量。现在，给定一个具有大DBP的无线网络，我们如何利用它？在本节中，我们提出了一种调度算法，它不仅非常简单，而且是完美的公平。一般来说，我们的调度算法有两个关键原则Jiamian Wang和Weidong Liu/IERI Procedia 10（2014）153157(1) 该算法对所有节点轮流调度，保证了调度的公平性，简化了调度;(2) 对于每个节点，分组将在第一个可用时隙中传输，以最大化性能。传统上，用于发送的可用时隙应该满足下面列出的标准（C1）-（C5）。（C1）对于发送方：发送方本身在该时隙中必须既不接收也不发送。（C2）对于接收器：接收过程将持续1个PTT。在此期间，接收器必须处于空闲状态，这意味着接收器不得正在发送、接收或受到干扰。（C3）对于其他节点：传输的信号将肯定会黑其他节点为1 PTT不久或稍后。该信号必须不干扰接收它们自己的分组的其他节点。（C4）关于干涉：干涉不能重叠。（C5）关于发射：不允许干扰发射然而，在具有大DBP的无线网络中，标准（C4）和（C5）不再是必要的。实际上，干扰传输和干扰重叠都是实现吞吐量增益的关键。下面我们详细介绍调度算法。我们将网络建模为有向图G（V，E），其中V是单个广播域内的节点集合，|V| = n，并且E是节点之间的有向链路的集合。假设数据被分组为相同大小的分组，并且所有分组具有相同的PTT。每个节点v生成rv个分组，并且每个分组具有其目的地节点。所有这些数据包必须按顺序传输。为了简单起见，我们让时隙的长度等于一个PTT。该算法首先建立一个n行矩阵来存储调度结果.其中的每个元素可以是以下状态之一：“TX”-对应节点将在该时隙中发送;“RX”-将接收信号;“IN”-将被其他信号干扰;“NA”-未调度。请注意，列的数量不是固定的;它随着算法的运行而增长。然后，该算法枚举所有的节点和调度节点在哪个时隙发送其第一个数据包。对于每个特定节点v，如果没有分组要从它发送，则算法简单地跳过该节点，然后开始调度节点v+1（如果v是最后一个节点，则跳到第一个节点）;否则，算法根据本节前面列出的标准搜索第一个可用的时隙用于发送。一旦找到可用时隙，算法就将节点v的该时隙标记为“TX”。此外，接收器和其他节点的对应时隙也应该被标记为算法中的一个关键问题是，由于节点之间的距离可能不是整数，到达其他节点的信号可能会跨越两个连续的时隙。解决方案是标记两个连续的时隙。例如，假设有两个节点A和B，距离为|AB| = 2.3PTT。如果节点A在时隙2中向B发送分组，则信号将在时隙4.3到达节点B，并且持续到时隙5.3。因此，该算法将节点B的时隙4和5都标记为“RX”。对于两个节点之间的距离为整数的情况，我们将接收时隙或干扰时隙与有界的两个时隙一起标记。例如，如果发送方节点A和接收方节点B之间的距离是2PTT，并且节点A在时隙2中发送，则算法将B的时隙3、4、5标记为“接收”。这样做可以确保我们以槽为单位进行调度，这是简单而合理的。此外，由于在大多数情况下到达信号跨越两个时隙，节点位置的轻微移动不会破坏调度。更重要的是，如果位置急剧变化，我们可以标记更多的连续插槽，以确保鲁棒性，以降低性能为代价。4. 仿真及性能评估在本节中，我们构建模拟来证实理论分析。仿真场景由无线网络的一个广播域中的n个节点组成。节点的位置是随机生成的。假设相同的数据包大小为p，无线网络的平均带宽为k。在这种情况下，可以计算出延迟带宽积。首先，我们计算这些场景中的平均单跳距离l（以信号传播的距离为单位158Jiamian Wang和Weidong Liu/IERI Procedia 10（2014）153一个PTT），因此无线网络的平均一跳延迟是l *（p/k）。因此，延迟-带宽积是k =l*（p/k）*k/p=l个分组。图四、当延迟带宽积≥1（a）和≥1（b）时的仿真结果该图表明，当k非常小时，几乎不能实现吞吐量增益;然而，当k> 1/2时，k和n越大，可以实现的吞吐量增益越大纵轴表示利用无线网络中DBP大的特点可以节省的时隙比例，越高越好。例如，纵轴中的40%意味着如果我们使用大的DBP，网络可以仅用传统理解的60%的时隙传输相同数量的数据包。图五.当n = 10（a）和n= 10（b）时的模拟结果。给定时延带宽积，节点数越多，性能越高;同样，给定节点数n，时延带宽积越大，性能越好。纵轴表示利用无线网络中DBP大的特点可以节省的时隙比例，越高越好。对于每个场景，我们运行两个模拟。一种是遵循传统理解下的准则，即不允许干扰重叠和干扰传输。另一种是按照本文提出的理解下的标准。假设传统的调度方案花费x个时隙来成功传输所有分组，而新的调度方案需要y个时隙。那么，如果我们利用无线网络中的大DBP，则可以节省的时隙的比率是Δ =（x-y）/x我们在这里强调，对于每个n和n，模拟了100多个不同的场景，以计算出Jiamian Wang和Weidong Liu/IERI Procedia 10（2014）153159平均节省时隙比率。幸运的是，当n和n固定时，比率相当稳定，因此平均比率是评估性能改进的特征度量。结果如图4所示。以下可得出一些重要结论(1) 如果在单个广播域中只有两个节点，则无论DBP有多大，都不能实现吞吐量增益。这是合理的，因为在这些场景中没有出现干扰。(2) 当在单个广播域中存在多于两个节点时，可以实现更高的吞吐量。而且，随着节点数量的增加，吞吐量增益也会越来越大。这是有道理的：节点越多，利用干扰的机会就越多。(3) 正如我们在第2节中所讨论的，即使当吞吐量非常小时，也可以实现更高的吞吐量，尽管它可能非常小。特别是当为1/2时，几乎不能获得吞吐量增益。(4) 一方面，给定节点的数量，节点数越大，可以实现的性能越高。另一方面，给定DBP，节点数量越多，也可以实现越高的性能。图5（a）示出了节约的时隙比率与具有k = 10的无线网络中的节点数量之间的关系。图5（b）示出了当在一个广播域内存在10个节点时，节约时隙比率与DBP带宽之间的关系。总之，在具有大DBP的网络中可以实现显著的吞吐量增益。在一个典型的情况下，水下声传感器网络的DBP = 10和4个节点内的广播域，大约一半的传输时间可以节省传输相同数量的数据包，如果我们利用大的DBP。5. 结论和今后的工作在本文中，我们揭示了一个吞吐量大于一个基于传统的理解，可以实现在各种无线网络。我们指出，吞吐量的增益是密切相关的一个大的延迟带宽产品（DBP），我们定义的无线网络的一跳管道在无线网络中的容量的一个新的度量。然后，我们提出了一个简单的，但非常有效的调度算法，旨在利用大的延迟带宽积在无线网络中。该算法简单、公平、实用。在本文的最后一部分，我们建立了模拟。从仿真结果中可以总结出几个重要的结论，这与本文前面的分析是一致的。今后可以做一些工作。特别是对于时延带宽积较大的网络，需要进行形式化的理论分析，以揭示其内在的性质。引用[1] 陈凯，薛耀，王志华，张志华，等，移动自组网中的带宽时延积，计算机通信27（10）（2004）923[2] 陈文辉，高带宽延迟积与随机损失之网路传输协定/网际网路之效能分析，国立成功大学资讯工程研究所硕士论文，（1997）[3] L. G. Roberts，Aloha packet system with and without slots and capture，SIGCOMM COMPUT.Commun. Rev. 5（2）（1975）28-42. doi：10.1145/1024916.1024920。网址http://doi.acm.org/10.1145/1024916.1024920[4] M. A. Bergamo，高吞吐量分布式航天器网络：体系结构和多址技术，计算机网络47（5）（2005）725[5] I.F.Akyildiz，D.Pompili，T.Melodia，Underwater Acoustic Sensor Networks：ResearchChallenges，Ad Hoc Networks 3（3）（2005）257