增加聚合Convergecast通过管道数据采集频率

文摘

我们考虑的问题增加了数据收集的频率聚合convergecast。先前的研究试图增加数据收集的频率通过缩短单个数据收集周期的完成。我们旨在增加数据收集的频率使用流水线和收集的更新,因此,提高整体数据收集的频率和吞吐量。为了达到这个目标,我们重叠多个数据快照的传播计划在同一整体进度周期,从而增加通过流水线并行性。因此,个人的有效的数据收集时间可能跨越多个快照,连续、调度周期。为此,我们修改聚合convergecast模型,解耦调度长度和数据收集延迟,通过放松其优先约束。这个新问题我们的解决方案涉及到非常规的方法构建计划之前确定确切的数据聚合树的形式,而反过来,要求安排构建阶段保证每个节点可以达到水槽里。我们比较我们的结果对先前提出的算法,使用快照流水线也使用流水线的一种形式,以及对一个算法,虽然缺乏流水线,展品的能力产生非常短的时间安排。结果证实可能实现吞吐量大幅增加,成本的增加一些延迟。

1。介绍

普遍应用的无线传感器网络(网络)是集的值,例如,一个从每个传感器测量,水槽节点。底层协议称为convergecast。convergecast执行,它是有用的路由数据包沿着路径从传感器到水槽和执行传输计划,并发传输,这样不会导致碰撞(在意图接收器)。

特定的各种数据收集问题要求值的子集的提取总结/描述的整个测量集所有传感器。这是松散称为聚合。对于一个给定的网络,可以使用几种不同的生成树路由数据和执行聚合的水槽,即。,不同的聚合树。的聚合convergecast调度关心的问题是确定最佳聚合树收集所需的时间长度单组数据(一个“快照”)从节点到水槽。聚合convergecast调度的输出是一个传输和相应的时间表,跨越、聚合树。生产计划是一个“一次性”计划;也就是说,it dictates all necessary transmissions to collect a single “snapshot” of data to the sink. It is therefore implied that, for any ordinary application in which we are interested in continuous data acquisition, this schedule is periodically repeated. We can therefore assume that this periodic repetition is taking place back-to-back, and we can think of each execution of the schedule as a “cycle.”

构建计划我们需要考虑无线媒体的本质,实施出口限制由于碰撞/干涉当从多个相邻节点对传输相同的接收机同时发生。我们将调用限制引起的干扰的影响资源约束,因为他们执行共享无线资源的访问决策。

此外,在聚合convergecast,叶节点传输测量他们的父节点。内部节点树的执行聚合操作的值从他们的孩子(和自己的价值)和聚合结果传输到他们的父节点。的限制迫使父节点等待的结果所有接收指定的孩子,在他们生产和传输聚合结果,将被称为优先约束。

相关文献中使用的解决方案的方法是将问题分解为两个阶段:第一个构造一个聚合树(即。,决定了路由),第二个确定每个节点的传输时间(即。、调度)。两阶段依赖于启发式。两个重要的方面是,有时隐式地假定:(一)有必要定义一个聚合树第一个为了获得一个时间表和(b)严格的的执行优先约束必须满足一个时间表的时间间隔内循环。一些解决方案获得计划和树同时但从未计划第一次和聚合树后。

聚合convergecast时间表,到目前为止,感兴趣一个单独的、孤立的,沉的所有传感器数据的集合,因此专注于完成收集在最短的时间内。虽然这种方法是可取的,某些类型的应用程序,它不提供其他应用程序,如连续运行数据聚合查询。连续运行的查询可以受益于收集数据样本的能力经常从整个传感器领域,为了让一个更好的时间重建观察到的现象。这样的应用程序要求更高的采样率,即,a higher rate of snapshots collected per unit of time and hence higher throughput data collection. In fact, we may even be willing to accept a longer lead-in time for the first snapshot to be collected as long as the snapshot collections can be performed at a higher rate.

完成既定目标,我们将放松的执行优先级约束在一个时间周期。同时,我们介绍一种流水线的形式,允许多个独立的独立数据快照并逐渐传播,另外,网络内的聚合。不同的快照不“混合”;也就是说,they propagate in FCFS order and are aggregated separately from each other. Since the solution proposed considers satisfying the totality of precedence constraints over a timespan of multiple, consecutive, scheduling cycles, we will call the constituent successive repetitions of the overall transmission schedule as themicroschedules。microschedule共同的特征与原聚合convergecast时间表的定义是,microschedule之内,每个节点传输只有一天。所不同的是,传输的顺序安排在一个microschedule,通常,不足以满足所有约束的依赖。多个连续的microschedules聚合需要完成一个快照。有利的一面是,在microschedule几个快照过程中可能被同时收集/聚合。另外,稍后将看到的,生产microschedules意味着更小的intersnapshot时间短,因此,更高的整体吞吐量。

有利的支持流水线的直觉是基于空间复用的多次反射无线网络媒介。流水线的好处的一个简化的例子是图所示1。解决方案的吞吐量不使用流水线 ,见图1 (b)(每一个快照完成7槽)。吞吐量增加到 在图1 (c)使用流水线。在图1 (c)13、节点传输聚合(一个特定的快照),T11时,节点12时,feed 13,传输节点13(病人)后,违反了优先约束。然而,如果我们考虑到节点的传输12和13是指不同的连续(在本例中)快照,优先约束节点之间12和13所示同样的快照感到满意,尽管在两个连续的(微)调度周期。树拓扑描述图1相对来说,微不足道的管道。在随后的章节中,我们将看到我们的快照流水线技术适用于任意的连接图。

我们研究的贡献对聚合convergecast安排如下:(我)我们扩展,提出一种新的优化模型的聚合convergecast:整合的概念快照模型中,轻松的单一数据收集周期的限制,解耦从延迟,吞吐量和会计的缓冲网络中发生。(2)提出了一种新的范例模型聚合convergecast两阶段方法,通过反相阶段(调度和路由后),同时采用节点激活调度模型(而使用链接激活模型)。

当前论文是基于我们的早期工作大大扩展版本(1]。具体地说,它会向以下方向:(我)它引入了一个正式的模型的优化问题。这个模型要求引入的新概念:快照,microschedule,聚合逗留规,快照序列约束(部分3所示。2);(2)它提供了补充解释通过快照pipeling(部分的例子3所示。3);(3)它介绍了复杂性分析提出了启发式算法(部分4.1);(iv)它执行比较对小型网络的最优解决方案,以及相应的改进约束编程模型(部分5。2);(v)它补充能源消耗的研究特色性能结果的解决方案产生的启发式(部分5。3)。

剩下的纸是组织如下。部分2提出了相关工作。部分3包含聚合convergecast模型,定义和相关概念。该算法描述和讨论的部分4。广泛的模拟和随之而来的结果和发现了部分5。最后,部分6总结了纸。

2。相关工作

一个广泛的作品存在于聚合convergecast问题。问题的复杂性决定了陈et al。2,3),最近重Bramas et al。4),是np难的地方。设计了几种不同的启发式以解决这一问题。一些作者采用集中式方法(2),而其他人提供了一个分布式的解决方案(5]。干扰模型不同的作者。(使用的协议干扰模型6),而采用物理干扰模型(7]。大多数作品采用单通道惯例,但多频方案也被调查(8]。

聚合树的建设是研究最多的话题。最短路径树(SPT)的首选2,9),而基于连通支配集(CDS)树中使用(7]。它也表明,树满足不同条件组合在一个单一的逻辑拓扑。一个例子是SPT的组合与最小干扰树(麻省理工学院),提出了(10]。另一个可能的标准指导聚合树是树的建设对能源消耗的影响,使用,例如,在11]。

我们考虑三个相关方面为目的的比较与当前工作:优先约束的放松;序列(步骤)获得一个解决方案(树节点调度首先,聚合后);和管道的使用。关于第一个方面,大多数作品明确迫使父节点只传输后收到所有指定的孩子(传输9),而其他作品含蓄地使用相同的限制(12,13]。第二方面,我们所知,除了我们的早期工作1),没有以前的算法决定首先对节点的传输时间/时间表和后来的聚合树。第三方面,我们没有在文献中找到一个解决方案提出流水线,除了[10),即使他们使用流水线首先致力于聚合树,随后创建一个管线式安排在这棵树。我们没有找到一个工作,共同把提到的三个方面。

尽管[描述的工作14熊相似,我们的工作,它主要处理网络容量,获得的调度和路由执行细胞网络分区后,基本上覆盖网格拓扑通信图,然后使用压缩数据收集(不是用于我们的工作)。的工作(15)提出了算法LPIPE(拓扑)行和TPIPE(树拓扑)处理管道调度,但他们的模型不使用任何形式的聚合。

以来最接近我们的工作是10],在完整的利益,我们提供了一个简易的操作。聚合树构造称为Bounded-Degree最小半径生成树(BDMRST)。聚合树使用bicriteria优化结合最短路径树和最小干扰树。最佳的聚合树建设制定如下:给定一个阈值度最大的节点上,目标是最小化最大跳数(半径)树。随后,聚合树用作多通道调度的基础。传感器网络部署区域分为一组方格网细胞。首先,频率分配给接收器树的每一个细胞,然后贪婪的时间段分配方案是用于每一个细胞。优先级的调度算法不需要约束;相反,建立了管道的水槽得到所有节点的聚合数据。

3所示。网络模型

WSN聚合convergecast让一个应用程序被定义为一个应用程序通过网络连接图 。网络连接是被一个无向连通图 ,在那里代表顶点/节点的集合代表的边缘。也就是说,有 节点。边缘捕捉物理拓扑结构它们被假定为是双向的。我们认为,为了这个工作,所有的顶点导致数据收集。收集发生在边缘的一个子集, ,这定义了子图 ,聚合树,单个节点 这是水槽,接收收集和聚合数据。所有节点有精确的知识的时间,这样每个节点传输完全在允许的时间段, 。不允许分批传输或分割。每个从节点传输开始和结束时槽 。每一次槽一个时间单位的持续时间。

所有节点在一个单一的渠道运作。每个节点包括一个收发器半双工通信的能力。,所谓的“主要”干扰同时代表了半双工收发器无法接收和发送。此外,我们还假定协议干扰模型,如(10),根据这一潜在接收者节点可以成功地得到传播只有一个,只有一个周边的节点(按照连接图)是传输。如果多个相邻节点同时传输,结果是一个并发传输的碰撞,没有收到。这是形成鲜明对比物理干扰模型同时接收传输的结果从多个邻居取决于相对接收信号传输的优势。碰撞有时被称为协议干扰模型二次干扰。

定义1。让一个快照被定义为工会的设置的值的网络传感器在同一瞬间感觉到自然的时间。序列捕获快照时间顺序,它对应于传感器的值在一个特定的时间, 。快照并不意味着任何聚合操作符(例如,最大值、最小值和AVG)。聚合操作符定义的应用程序。

定义2。收集延迟之间的区别是一个快照的时候(同时传感器测量在所有节点)被和水槽节点的时候已经收到了相关的所有(聚合)数据快照。

定义3。优先约束是限制根据节点传输一次聚合数据的快照,它可以不再被任何传输相关的目的地相同的快照。

定义4。一个聚合convergecast安排使用快照流水线如果节点可以开始传输数据的下一个快照在之前的快照已经完全接收到水槽里。

定义5。时差,感知的水槽,完成接待之间的快照和完整的接待下一个快照代表了intersnapshot延迟 。它也代表了microschedule长度。

排队系统是稳定的意义上说,创建快照的速度,引入网络应该匹配的速度交付给水槽。因此,是一个属性的特殊安排,进而定义了快照的频率可以生成并交付,即。度量的吞吐量。后一个可能的初始瞬态当第一个快照开始通过网络传播,我们达到一个稳定状态,即充分利用管道,并定期快照水槽。微不足道的注意(矛盾),在稳定状态intersnapshot进度拖延等于长度;也就是说, 。

定义6。microschedule是传输进度描述重叠,跨越时间,同时进步的数据收集和聚合多个,但独立的数据快照。系统不断重复microschedule。microschedule必须满足以下要求:(1)每个节点传输一次,只有一次,(2)产生的日程满足快照序列的约束,和(3)产生的进度满足可达性约束。

的具体描述(2)和(3)中给出了定义8和9。直观地,快照序列约束是先的快照在单个节点和传播时,其下沉,而可达性约束是存在的财产无碰撞的路径传输,从任何节点我们可以达到水槽,即使这遍历将涉及多个连续microschedules完成。

流水线是通过多个快照每个期间通过网络传播microschedule期,因此 指出,在以前的工作, 。

定义7。管道吞吐量, ,传输的数据量的比例是参与一个快照收集、intersnapshot延迟,也就是说, ,在那里节点的数量。它可以被理解为单位时间通过水槽节点收集的数据。

在接下来的数包括水槽节点,和包括一个槽的pseudotransmission水槽节点本身的介绍,描述每个快照收集时代的终结。不失一般性,可以使用 指标的计算即“真正的传输,”。、变速箱的人物1。然而,将水槽pseudotransmission更加优雅表示,它从这个点开始采用。节点的总数,包括水槽、水槽和自我传播到本身是包含在槽后立即过去接待从它的孩子。这个自我传播,是虚拟的,是不受任何碰撞/干涉约束。

作为一个例子,考虑拓扑如图2(一个)节点1是水槽节点。传统的最优解聚合convergecast问题如图2 (b)。聚合树是由固体弧之间的节点。时间表如下标签聚合树的相邻弧(除了水槽节点pseudotransmission T5时)。基本上T5表示第一次槽的聚合数据可以提供。传统的时间表microschedule没有管道)的(此句是呈现在图2 (c)。颜色和W符号表示不同的快照(“波”)。显然,在图2 (c)只有一个快照收集。

图3提出了一种解决方案相同的拓扑使用快照流水线技术。聚合树和节点传输时间图所示3(一个)。图3 (b)提供了调度将如何展开的详细视图。完整的数据收集在连续两个microschedules执行。第一个(初始)microschedule,左边图3 (b),是一个短暂的时期。下一个microschedule(向右移动)已经达到稳定状态。快照1 (W1)完成,快照2 (W2)执行初始集合的一部分。的第三个重复microschedule然后执行,快照2 (W2)完成后,和快照3 (W3)执行其初始部分,等等。

从水槽节点的角度来看,有一个吞吐量增加。而不是完成数据收集每一个 时段(图2 (c)),现在可以得到每一个快照 时段(图3 (b))。

3.1。一个解决方案策略

我们的总体解决方案策略是减少调度长度, ,通过构造一个紧microschedule随后构建聚合树适合的时间表。我们逆施工顺序(树第一,计划明年)现有文献紧随其后。介绍的并发症,我们的选择是需要安排不知道谁应该每个传播的接受者,即。,不知道哪个节点将传输节点的父聚合树。因此我们不得不使用节点激活模型据,当一个节点传输,不应当有传输任何——和两跳邻居。由此产生的灵活性决定父母的关系后来付出的成本降低吞吐量(16]。在接下来我们将看到,任何这样的减少是补偿的吞吐量提高了流水线。

总之,我们定义microschedule 并发传输的序列发生在槽 。 槽的节点集传输 ,也叫的集合活跃的节点th插槽。假设 一个节点传输在槽吗 。我们表示即将离任的传播节点的弧向下沉 。由此可见,聚合树被定义为 。在传统的聚合convergecast计划,是固定的预先计算的聚合树,同时,提出了快照流水线,是由一个特定的生成树构建阶段后续调度阶段。

另一个难题是,我们需要确保先交付存在至少一个的快照和抗干扰的路径(传输序列)感知数据可以从任何节点转发sink-even如果这条道路需要传输到多个连续microschedules序列。这是通过执行一个非常温和的要求安排施工期间,我们称之为可达性约束,根据计划没有干扰传输可以扰乱网络中的任何节点的能力至少有一个路径。注意,这个约束并不意味着任何最优对任何这样的路径的长度。然而,随着读者可能已经注意到,长路径不从根本上反对我们的目标,因为我们已经准备好贸易增加了更高的吞吐量延迟。

定义8。一个时间表尊重快照序列约束如果,每一个节点 ,节点传递下一个快照 ,如果它上次传播,传播前()快照(每个节点先的快照)。

定义9。一个时间表尊重可达性约束如果至少存在一个直接的路径从每个节点水槽节点序列中的每个中间节点可以接收传输无碰撞的路径。

约束确保我们避免安排在快照不完全传输,或一个节点的情况下积累数据包来自多个快照传送出来的秩序。在下一节中我们将看到,我们还需要捕获节点的积累(缓冲),这是直接关系到多少时间段收到孩子的数据包之间的时间花在一个父节点和家长发出即时聚合包的快照。为此,我们定义以下。

定义10。的聚合逗留时间(槽)的时间间隔开始时一个人包的快照收到从一个子节点的父节点和结束时,快照的聚合包吗传播的父母。

聚合逗留时间的定义延伸到传感器样品采取快照的一个节点,直到时间传送出来,要么未聚合(叶节点)或聚合(室内树节点)的一部分。积压的聚合逗留时间是一个代理,建立在一个节点开始积累数据。因为很多快照中可以同时收集网络,缓冲要求存储在一个节点积累所有正在进行的(没有传播)快照。甚至传统的聚合convergecast方案涉及的积累数据传输聚合output-however之前,据我们所知,没有以前的工作模型相关的积压。传统的理解是,只有一个空间(内存缓冲区)需要从节点的孩子和执行聚合的时间保持在内存中并不重要。这是一个简单的假设,因为通常的即时聚合(视为算法操作)通常是左不明。在最坏的情况下,它不能发生之前所有组成聚合信息已收到,因此需要存储他们的即时聚合。我们采用的假设,最坏的情况下,持有。需要从多个快照存储消息,这样每个快照分别聚合,进一步增加内存需求/积压。

3.2。正式的模型

我们正式定义管线式聚合convergecast问题使用中列出的符号表1。让 是一个无向连通图中定义的部分3。这个词代表弧的存在如果 ;否则,电弧不存在 。水槽节点pseudotransmission发生在时间 ,定义为槽后立即下沉的最后的接待孩子传播。

作为一个(相对)指标的快照是通过节点传输时间 。快照通过水槽参考相对于其他的吗定义。非常,我们可以设置固定值,例如, 和表达所有剩下的相对于这一点。例如,在图3 (b),请注意 和 ,也请注意,如果 然后 。额外的要求设置的传输在microschedule使用的值序列,他们从 。此外,没有传输 允许从槽开始(因为快照已经完成)。通过定义 ,我们可以间接的定义作为

例如,在图应用公式3 (b)给了 。此外,通过我们可以定义总积压(通过定义10)由于所有快照在进展为代表的所有数据包存储快照节点(在单位时间×空间):

第一个组成部分捕获数据的存储需求的节点 ,也就是说,its own sample, until the node can transmit the aggregated packet. The second component of表达的逗留的总和传入的数据包从节点的孩子(如果有的话)。

上面的符号,结合约束禁止干涉/碰撞,导致以下配方优化问题:

前三个约束是类似传统的聚合convergecast问题[9]。分别,他们捕获单一传输每个节点约束,禁止接收节点的传输在同一个槽已经分配给在收件人收到(半双工)和抑制干扰节点时应该接受。我们放松优先约束,不同的条件添加到执行可达性约束。制定在为基础Subtour消除配方(17)生成树问题。Subtour消除斜靠在观察到生成树(聚合树在我们的问题)没有简单的周期并已 边缘。它可以证明所选边不包含一个周期,如果任何 和 边的数量与端点小于 。第二个约束所必需的Subtour消除了第一个约束。最后制定约束链接快照的概念。州,一个节点的孩子(从快照,快照的推进)在同一快照作为他们的父母,如果孩子的传输时间,使其传播之前父在microschedule(就像在传统的聚合convergecast问题),或者是立即处理下一个快照,如果孩子传递后父节点microschedule。水槽节点是一个特例,它定义了第一个快照(参考)。这一个必要的约束,因为它关系快照目前每个节点处理,根据每个节点的传输时间相对于母公司。不难观察到传统的聚合convergecast问题将只有一个快照,因为孩子们总是传输之前,他们的父母。最后的限制规定快照序列约束中描述的定义8。

目标函数捕捉聚合convergecast模型的三个相互竞争的目标,使用相应的三个重量( )。传统的目标是最小化延迟(在我们的符号)。使用管道我们脱钩吞吐量延迟,吞吐量是捕捉到这也是microschedule长度。较小的更高的吞吐量。第三个元素(在以前的研究中被忽视的)是累积聚合逗留时间被网络中的每个节点(间接,积压在每个节点)。这是可取的积压是尽可能小。在这里,它是被最小化最大总聚合逗留在所有节点。最大的减少总聚合逗留时间有许多可取的属性:(i)它减少节点的孩子以来的儿童数量越大,越大积压,同样,由于节点不需要接受许多孩子的传播,其(接收)通信能耗较小;和(2)往往会导致更快的数据收集由于积压越小,越快完成聚合在一个节点。每个节点有一个单亲的结果,发送聚合的结果,是通信能量传输常数和独立的子节点的数量。注意,优化的一个副作用是确定聚合convergecast树。找到一个优化拓扑不属于原聚合convergecast工作陈et al。2,3),随后导致其他作者创建定制拓扑来处理二次优化标准,如能量。这里,我们间接指导聚合树建设占总聚合逗留时间的影响。然而,这也可以减少并发收集快照,快照在运输途中,因为更大的节点的积压。

3.3。例子

我们提出两个例子使用快照管道数据采集性能有影响。两个例子所示的解决方案的最优解的具体实例。第一个例子是一个链拓扑结构,如图4,第二个树拓扑。在这两种情况下节点1是水槽节点。

表中给出的结果2和3揭示使用快照流水线的优势。尽管传统和管线式方法相似的结果收集延迟和总逗留,使用三个快照允许快照流水线的解决方案“折”时间表和吞吐量的三倍。图5描述了数据收集计划“展开”。瞬态后T1 T6, microschedule处于稳定状态(从T7 T9)和重复(T10病人,T13 T15,等等)。快照forge向前向汇聚节点。

的二叉树图中描述的示例6与时间T传输,我们也表明聚合逗留B值每个节点。目标函数值表中可以看到4。管线式解决方案展示相同的延迟集合传统方法,但其吞吐量更高。

4所示。管道调度算法

制定管线式聚合convergecast问题包括,作为它的子用例之一,原聚合convergecast是np难问题。在这里,我们得到一个启发式算法1)的主要目的是增加吞吐量。最初,输入图像必须转化为一个有向图,每边两个弧。另一个初步行动是删除所有即将离任的弧线从水槽,因为水槽不传送。这些行为是由函数TransfGraph在1号线。

2号线决定了顶点的顺序将被处理。我们考虑三个启发式。每一个启发式可能使用多个决策标准。第一个启发式(ACSPIPE_1)按照以下顺序应用三个标准:(a)选择顶点的即将离任的弧最多的本身和目的地之间的共同邻居顶点,顶点识别的原理图上的内部大派系,安排他们,因为他们可以把更多的冲突弧线(后面会解释),并打破关系,基于(b)优先顶点远离水槽,其基本原理是首先删除多弧远离水槽,离开该地区靠近水槽(所有路径必须逃不掉地收敛)与更多的路径选择,并将剩余的关系,(c)选择第一个顶点和更高的ID。第二个启发式(ACSPIPE_2)是第一个的一种变体,距离水槽应用第一的标准(标准(b)),然后共同邻居的数量标准(标准(a)),然后,在发生领带,秩序是决定基于更高的ID(标准(c))。最后,最后一个启发式(ACSPIPE_3)是随机选择顶点。

一旦定义顶点的顺序,该算法流程节点顺序选定后,试图为每个顶点分配传输尽早槽。这是在3 - 8行执行。一个顶点从队列中被处理。节点的初步日程存储在 ,代表计划周期内的槽指数。布尔变量可获得的用于指示如果水槽节点仍可通过图上的所有顶点。

一次试探性的时间表(即。,slot in which to transmit) is selected for vertex ,是时候来验证如果这个选择不打破可达性限制。首先,该算法决定了冲突的弧线。冲突弧线是那些不可能使用,因为他们的激活将违反一级或二级干扰约束。冲突的弧线是由功能决定的ConflictArcs在第9行。应用干涉来限制可用的路径到达沉而不是限制时段可供顶点传播。

10号线是用于验证如果删除冲突的弧线,在第9行识别,将打破可达性约束。函数可达性检查是否可以从每个水槽节点1-hop和2-hop邻居。

让的设置单邻居和两跳邻居的集合。让节点的集合的局部区域(包括)被定义为 。

定义11。Convergecast可达性是所有顶点的属性根据 在有向图 可以达到水槽节点。

引理12。一个有向图 ,它满足convergecast可达性,保持顶点时这个属性是另外安排,当且仅当所有 后可以达到水槽吗计划。(这可以非常验证通过检查节点的可达性 。)

证明。一个顶点传播只会影响传入的顶点的弧 ,因为这些是顶点的影响主要和次要矛盾。一个传入的弧来自最顶点 。一个有向路径的中断 (从顶点)也中断所有直接路径是一个子集。只有他们所有可能的路径的顶点水槽交叉顶点可能有其可达性的影响,因为他们会有另一个路径,不涉及吗 。假设至少一个顶点的路径 ,然后检查是否所有的顶点维持其可达性的水池能充分保证剩余的顶点也保持其可达性下沉。相反也是如此,因为 。因此,一个有向图维护convergecast只通过检查是否顶点可达性属性维持其可达性的水槽的时间表。

引理12简化是有用的可达性验证。而不是验证所有网络节点,只 节点需要检查。可达性验证可以执行使用广度优先搜索(BFS),根据引理12。每个顶点的被选中作为根。如果没有可达性侵犯时,暂定的计划是有效的和承诺。如果仍然可达性限制,所有矛盾的弧线 ,确定之前,从图 。11到13行执行删除。如果一个可达性侵犯,没有弧删除,相同的顶点再次加工新的试验性时间表(下一个槽)。如果搜索一个时间表槽没有生产可达性侵犯是徒劳的。,所有slots thus far defined for the schedule have been exhausted, then the schedule length expands by one slot (by virtue of Line 8) and vertex是非常定于传输插槽。

一旦一个时间表被定义为所有顶点,我们需要聚合树,最好是一个最小化延迟。中间结果到目前为止是一个有向子图与传输时间为每个顶点。每个顶点可能有多个路径到达汇聚节点。节点后进一步传播,信息内容只是转发节点后的水槽传输的目的地。这个源顶点之间的松弛时间传输和目标节点传输可以用来区分两个或两个以上可能的候选人,说和 ,也就是说,whether to use arc或弧 。因此,我们计算所有节点的松弛时间在16行每个弧和使用它们的重量。如果目的顶点将源顶点后,时差 。如果顶点之前预定的顶点 ,我们利用这一事实信息的收集周期,安排定期重复。如果目的顶点已经在当前周期的传播,松弛持续到的时间传播的下一个周期。因此,松弛时间 。在这里表明microschedule周期的长度 。

每个弧现在有一个与之相关联的重量表示时间从弧源传输到时间转发弧的目的地(或相关的延迟这个弧的“使用”)。我们的目标是找到一个聚合树最小化整体延迟。这样的最小重量树是如何获得的?传统的算法(克鲁斯卡尔和整洁的(18)获得一个生成树用无向图。因此这些算法不能直接应用。相关的问题是计算扎根直接生成树。扎根直接生成树是一个连接图,没有任何周期中,所有节点 弧(每个节点除了根),每个节点都有且只有一个传入的弧。这个配方属于一类分支问题,也被称为最小的代价树状(MCA) (19]。解决这个问题的算法提出了埃德蒙兹(20.]。MCA算法能够获得结果即使输入图周期。

具体来说,可以视为convergecastin-branching问题(19),和轻微的修改对埃德蒙兹的算法就足以获得一个聚合树。修改包含在改变弧的方向获得第18行后,使用相同的权重了。执行此操作的19所示。在第20行,最低成本树状算法和一个向外的树。

快照为每个节点在第21行被选中。的SelectSnapshots函数由遍历在level-order每个节点使用BFS并选择快照属于基于节点的进度和节点的父节点计划。最后一步是在第22行执行,由回归弧的方向。最后,我们计划获得的第15行,第21行中定义的快照,聚合树获得第22行。

一个例子执行图的算法7,因为它是应用于图的输入图像2(一个)。第一阶段的结果是描绘在图7(一)的时间段内表示节点。圈内的数字表示所选择的时间段为每个节点的传播。虚线弧表示弧删除冲突期间安排选择。图7 (b)代表着地位后执行线19日有向图在哪里使用MCA的准备。每个弧旁边的数字表示时间松弛。管道的最终结果聚合convergecast算法是描绘在图7 (c)。聚合convergecast执行时间表是描绘在图7 (d)。在这个例子中,横跨两个完整的传播快照microschedule周期+两个时段在第三个microschedule;因此,三个快照是在同一时间通过网络传播。

4.1。复杂性分析

运行时的复杂性管线式聚合convergecast如下:1号线运行时的复杂性 。第2行可能有不同的运行时的复杂性取决于所使用的启发式。第一个启发式ACSPIPE_1要求更高,因为它必须遍历图的每条边,它的每个端点的第一和第二社区为了定义有多少共同邻居的端点。因此,运行时的复杂性 。第二个启发式ACSPIPE_2在执行 因为BFS足以定义每个顶点属于哪一层。最后一个启发式ACSPIPE_3需要一个运行时不超过的复杂性 得到一个随机的顶点。顶点的排序,使用启发式的权重,可以在执行 。的执行ACSPIPE_1启发式代表了最糟糕的情况。因此,运行时线2的复杂性 。

的调度执行部分线3 - 15所示。第3行显示,每个顶点必须选择安排。因此,它是执行 次了。第6行表明,每个顶点可能改期次,直到没有冲突与以前的顶点。的大小的估计不是微不足道的。然而,我们知道 ,因为 调度长度的上界,或时段的最大数量在每个顶点被测试。第9行获得冲突弧线周围的顶点 。可以发现冲突检查第一和第二的邻居和验证他们的预定时间。因此,它需要最多步骤。可达性验证,在第10行执行,可以通过石 。第12行是一个简单的弧删除,一个运行时的复杂性 。其余的调度与运行时执行一部分的复杂性 。最坏的情况下运行时调度部分的复杂性 。

最后一块定义了路由算法的部分。松弛时间,计算线16和17日运行时的复杂性 。线19和22是简单的弧形倒置,每一个执行的 。第21行在于稍微修改BFS算法,它运行在 。第20行包含运行时分析的复杂性埃德蒙兹的算法,用于获得最低成本树状。Tarjan埃德蒙兹的实现描述的算法(21运行在 。用一个简单的修改,该算法可以在运行 ,这是更适合密集的图形。实现错误纠正Camerini等人在22]。Gabow et al。23]给出一个 实现最佳生成树状。的作者(23)注意是不可能改善埃德蒙兹的时间复杂度的算法实现,因为算法也可以用于排序数字,和排序数量要求时间。因为它总是检查图的每条边,我们不能指望找到一个更好的运行时的复杂性比埃德蒙兹的算法 。因此,我们将承担这个步骤运行时的复杂性 。

的三部分分析的基础上管线式聚合convergecast算法,设置和顶点顺序定义(1 - 2行),安排部分(3日- 15日行),和路由部分(16 - 22行),运行时我们算法的复杂性 。

5。实验

我们评估算法性能通过模拟套连接图由将传感器放置在一个正方形的大小 。传感器位置随机均匀分布在该地区。水槽节点位置也是随机的。每个节点传输范围 ,除非另有注明。我们使用从200到800个节点的节点集。图中的每个点代表一组的平均价值十图与相同数量的传感器。误差线代表置信区间。就像前面提到的3,给出了目标函数的三个分量相等的权重;也就是说, 。我们实现了顶点的三个品种选择部分中描述4:ACSPIPE_1,ACSPIPE_2,ACSPIPE_3。然而,从结果来看,准确的选择ACSPIPE各种证明是小巫见大巫。我们比较ACSPIPE对电线(9),BDMRST(10]。电线代表一个解决方案使用聚合convergecast没有快照流水线,所有优先满足约束在一个计划周期,并使用传统的两阶段方法设计。BDMRST使用流水线但预选聚合树和一些特点。作为BDMRST设计了多通道调度程序,我们限制了吗BDMRST跑单通道。

图8显示每个算法产生的时间长度,而图9介绍了总吞吐量。收集延迟是描绘在图10。每个算法的特点是生产的聚合树在图11通过最大节点的入度。图12捕捉每个算法的吞吐量和延迟之间的权衡。同样,图13显示时间长度之间的关系和收集延迟。两个图上的点的平均值与相同数量的节点集。

5.1。讨论

它一再发现,一般而言,调度数据传输无线网络显示吞吐量和延迟(之间的权衡24,25]。这种情况与聚合convergecast也不例外。试图减少延迟的影响显然是如图10,在那里电线展品的最低数据收集延迟因为延迟和吞吐量之间的联系(一个是其他的倒数)。这链接导致有限的总吞吐量,如图9。的重点从延迟通过允许优先约束满足多个调度周期扩展解决方案空间。ACSPIPE和BDMRST可以探索更大的解决方案空间和新的权衡的可能性。总吞吐量提高了,但延迟增加集合。

网络与大量的节点可能有额外的限制来实现更好的总吞吐量。如果传输范围是固定的,吞吐量受到两个因素:(一)越来越密集的地区,干扰是主导因素限制调度长度减少,,(b)为更广泛的和稀疏的区域,节点分散均匀,啤酒花的数量从每个节点水槽是主导因素限制调度长度减少。在这两种情况下,所需的时间槽数量往往是大型和整体吞吐量下降。在这两种情况下,管道的使用可以是有益的(尽管优先约束),因为它带来的并行数据采集。

除了优先约束,一个聚合树的预选和一些预定义的特征也可以限制性能。BDMRSTbounded-degree和最小半径限制可能的聚合的解空间树。bounded-degree观察到在图的影响11。最终的结果是一个解决方案优于电线的总吞吐量,但不如ACSPIPE。除此之外,BDMRST的延迟并不明显好于集合ACSPIPE的(图10)。它是公平地说,打算BDMRST的作者是把它应用到一个多通道环境,有足够的频率,消除二次冲突。因此,唯一的障碍,提高调度长度是树(半径BDMRST显示了更好的结果比ACSPIPE)。如果没有足够的频率来消除所有二次冲突,BDMRST性能的削弱,因为它限制了潜在的总吞吐量,没有大幅削减收集延迟。

注意到在一个有趣的行为ACSPIPE品种是第二个启发式(优先考虑顶点远离水槽)提出了稍微不同的结果。350个节点后,聚合吞吐量(图9)是劣质的,剩下的两个。这一事实也反映在树上半径(图16),树的深度更小。即使有矮树,收集延迟不是更好。观察表明,树越长半径越小管道计划。另一个方面实验如图所示13耦合的吞吐量和延迟( 等方案)电线创建一个两者之间的线性关系。

我们也观察到,ACSPIPE礼物的自然减少总吞吐量当传输半径增加(图14)。更大的传输范围增加干扰,因此越来越多的时段需要克服争用,和收集延迟将会增加(图15)。

5.2。最优解为小型网络

我们比较我们的算法产生的结果对小型网络的最优解十节点。每个样本获得的最优解使用修改后的版本的约束满足模型聚合中描述convergecast [26]。我们修改5和7约束的模型(优先级约束),引入了约束连接拓扑中,时间表,和快照在一个单一的约束。新的约束来自部分中描述的配方3所示。2。它被实现为一个逻辑模型的约束。也就是说,(4)和(5)描绘了新的逻辑约束添加到这些描述(26]。结果,在 ,如表所示5。我们跑十的样本实例10节点上的算法,使用不同数量的链接跨实例以获取增加密度和连通性的影响。

5.3。能源消耗

在本节中,我们希望确定哪些算法解决方案产生逻辑拓扑和进度,降低了能源消耗。尽管数据聚合方案本身节能方案,每个节点的传输和招待会数量继续扮演重要的角色在决定它的能源消耗。我们认为能源消耗的主要来源是数据包传输和招待会。计划允许一个节点的存在完全关闭其收发器时将发送或接收。的周期性质安排让我们看看每个节点的能量的行为, ,在一个计划周期和推断其长期行为。在一个聚合convergecast周期,接收从一个节点孩子和传送一次聚合的结果。如果传输和接收能量分别和 ,然后,在一个周期中,节点缴费 单位的能量。如果我们假设 然后能量消耗 。 节点的程度吗在树的逻辑拓扑聚合convergecast;也就是说, 。简化不伤在算法进行比较的普遍性。你可以跟踪 ,占儿童(接收成本)与(单一)分开传输成本。然而,这将意味着一个多参数的引入,相对传输和接收成本、 ,鉴于许多收发器影响不大约1.0(通常在0.8和1.5之间)。例如,德州仪器CC2530 (发送和接收当前马马39.6和29.6)。如果我们观察的行为节点在一个时间间隔 ,鉴于时间长度 ,然后每个节点的能耗可以表示为

在算法进行比较,观察间隔是一样的, ,为每个操作和能源, ,是相同的;因此我们可以正常化值的 ,导致一个简化的 。从本质上讲,表达了对节点的能量消耗的速度 。是常见的在能源消耗的研究中,最严格的标准是时间,直到第一个节点失败。假设所有节点最初从相同的能量预算开始,第一个节点失败是最高的消耗速度,也就是说, ,在的年代。在特定聚合树,最高的消耗速率是由节点最高的学位。这个模型的解释很简单:逻辑拓扑节点有小度使用更少能源每周期传输和接收单位,因为将会有更少的招待会的收发器执行。然而,一个拓扑与低度节点可能会花费更多的能量比高度拓扑在相同的时间如果是使用更频繁(小)。我们会直观地预期,更高的吞吐量更高的能源成本的代价的。

图17提出了两个因素之间的关系,影响节点的能耗,度最大的节点 ,和时间长度 。每个算法组上的线是线性回归的平均值和阴影区域代表的置信区间 。图18显示了最大程度上的节点的能耗率为每一个算法,对不同节点的密度。旁边的数量每一个点的平均吞吐量是通过特定节点密度的算法来实现。

鉴于结果在前一节中,我们使用一个代表ACSPIPE家族的算法,由于它们之间的性能差异较小。BDMRST展示一个常数最大节点度(作为其设计规定)和最低能耗率在所有协议。尽管如此,吞吐量低于ACSPIPE如图所示。ACSPIPE密切遵循BDMRST的拓扑特征,也就是说,导致小的最大程度。这是一个欢迎的特点,但它不是一个偏好明确编码的算法,一样BDMRST。相反,它的副作用出现施工过程。的ACSPIPE能耗率高于BDMRST因为它能够实现更高的吞吐量。这两个协议(BDMRST和ACSPIPE)减少能源消耗速率随着节点密度的增加。电线展示了完全不同的动力学。在电线、逻辑拓扑的选择完全地址优先约束的解决方案产生的影响不同的节点度和调度长度之间的关系。结果是图上看到17,它指向一个增加能耗率随着节点密度的增加。这是因为,电线,产生了逻辑拓扑(SPT)的结果在更大的程度上密集的图形。的偏好电线减少优先级约束也可能导致它长的时间长度(26]。

总的来说,流水线的速度影响聚合convergecast的能源消耗。ACSPIPE导致较低的最高节点度,因此损耗率低。虽然能耗率可能是绝对高于BDMRST,这是由于更高的吞吐量,而这只能通过增加节点活动的单位时间。

6。结论

我们提出一个快照流水线方案适用于聚合convergecast问题。通过扩大优先约束的满意度从一个单一的周期多个周期,允许多个数据收集同时进行,我们能够获得更高的吞吐量这是必要的对于某些类型的传感器网络应用程序。在本文中,我们解决主要的理论和算法方面的设计。实际实现未来工作,但问题是评估我们的能源消费行为的第一步计划已经进行的部分5。3。

我们的策略算法推导管线式时间表取决于不同的方式占干扰在安排施工阶段。具体来说,我们考虑的可能性,它限制了可用的路径从节点到水槽但没有提交到一个特定的生成树(聚合)。这与使用干扰在给定聚合树节点时限制时段允许传输。从本质上讲,一个节点的唯一限制是允许在一次传输插槽是确保它不排除直接路径的存在一些其他节点连接到水槽里。我们称这个限制可达性约束。因此,我们把聚合convergecast配方,从考虑优先约束考虑到可达性约束。我们同时还包括的概念传播快照标记每个节点传输特定的快照的顺序索引它向前。我们完成了模型的解耦延迟和吞吐量和包括积压度量。

一个新家庭的启发式(ACSPIPE),使用快照流水线和基于保护提出了可达性在安排施工。我们比较方案与其他两个现有的算法,一个从传统两阶段(路由第一,安排第二)多样性和另一个使用流水线尽管是在一个预定义的聚合树。尽管该算法不是提供最佳的吞吐量,我们的方法能够解决方案、高吞吐量提高现有文献,但在延迟的成本。我们的工作是另一个表达式的著名的吞吐量和延迟的折衷。认识到,固定随机网络,获得更高的吞吐量只能增加成本的延迟(27]。新奇的贡献是在演示如何构建解决方案空间聚合convergecast调度和如何建模问题,快照合并,吞吐量与延迟,和缓冲发生在网络中占选择拓扑。

数据可用性

没有数据被用来支持本研究。

信息披露

本文是基于我们之前大大扩展版本手稿在[1]。

的利益冲突

作者宣称没有利益冲突有关的出版。

引用

1. e . De Souza, i Nikolaidis在聚合convergecast调度,流水线的应用”学报2013年IEEE 14日国际研讨会上一个无线的世界里,移动和多媒体网络,WoWMoM 20132013年6月,页1 - 9,。视图:谷歌学术搜索
2. 陈x, x,和j·朱,“最低在无线传感器网络数据聚合时间问题,”移动特别和传感器网络卷,3794在计算机科学的课堂讲稿施普林格,页133 - 142年,柏林,德国,2005年。视图:谷歌学术搜索
3. 胡x, x, j .朱”数据收集时间表最小聚合时间在无线传感器网络中,“国际期刊的分布式传感器网络,5卷,不。4、321 - 337年,2009页。视图:出版商的网站|谷歌学术搜索
4. 问:Bramas和s . Tixeuil”的复杂性在静态和动态的无线传感器网络数据聚合,”信息和计算,卷255,不。第3部分,369 - 383年,2017页。视图:出版商的网站|谷歌学术搜索|MathSciNet
5. b . Yu, j·李,李y”在无线传感器网络分布式数据聚合调度《28日计算机通讯大会上(INFOCOM ' 09),页2159 - 2167,里约热内卢,巴西,2009年4月。视图:出版商的网站|谷歌学术搜索
6. 美国学术界。黄,P.-J。广域网,c . t . Vu y李,f .姚明,“近常数近似在无线传感器网络数据聚合调度”学报》第26届IEEE国际会议上计算机通信(IEEE INFOCOM ' 07)IEEE,页366 - 372年,2007年5月。视图:出版商的网站|谷歌学术搜索
7. X.-Y。李、徐x王s . et al .,“有效的在种无线传感器网络数据聚合物理干扰模型,”《IEEE 6日国际会议上移动Adhoc网络和传感器系统,2009年。大规模的09年2009年10月,页353 - 362。视图:谷歌学术搜索
8. O。d . Incei和b . Krishnamachari”,加强数据收集无线传感器网络的基于树的聚合速度,”第五届IEEE通信学会学报会议上传感器,网格和临时通信和网络(SECON ' 08)IEEE,页569 - 577年,旧金山,加州,美国,2008年6月。视图:出版商的网站|谷歌学术搜索
9. i . b . Malhotra Nikolaidis, m·a·Nascimento“聚合convergecast调度在无线传感器网络中,”无线网络,17卷,不。2、319 - 335年,2011页。视图:出版商的网站|谷歌学术搜索
10. a·戈什O。d . Incel v . s .阿尼尔•库马尔(Anil Kumar)和b . Krishnamachari“多通道调度和生成树:Throughput-delay权衡快速数据收集在传感器网络中,“IEEE / ACM交易网络,19卷,不。6,1731 - 1744年,2011页。视图:出版商的网站|谷歌学术搜索
11. Upadhyayula和s . k . s . Gupta,“基于生成树的算法低延迟和能量有效的数据聚合增强convergecast (DAC)在无线传感器网络中,“特设网络,5卷,不。5,626 - 648年,2007页。视图:出版商的网站|谷歌学术搜索
12. d . t . m . k .一个n x Lam Huynh,和t . n .阮“最小延迟数据聚合物理干扰模型,”计算机通信,35卷,不。18日,第2186 - 2175页,2012年。视图:出版商的网站|谷歌学术搜索
13. 问:华g . Wang, y,“最小延迟聚集调度任意树拓扑下SINR模型,”特别、移动和无线网络卷,7363在计算机科学的课堂讲稿海德堡,页139 - 152,激飞柏林,柏林,德国,2012年。视图:出版商的网站|谷歌学术搜索
14. s, r . Beyah, z Cai”快照/连续大规模概率无线传感器网络数据收集能力,”《IEEE计算机通讯大会上,一家2012年2012年3月,页1035 - 1043。视图:谷歌学术搜索
15. 崔h . j . Wang和e·a·休斯“调度对传感器网络信息收集,”无线网络,15卷,不。1,第140 - 127页,2009。视图:出版商的网站|谷歌学术搜索
16. j . Gronkvist“空间重用tdma,分配方法”学报第一ACM国际研讨会在移动ad hoc网络&计算MobiHoc 00IEEE出版社,页119 - 124年,皮斯卡塔韦,新泽西,美国,2000年。视图:谷歌学术搜索
17. g . Laporte“广义subtour消除约束和连通性约束,”运筹学学会》杂志上,37卷,不。5,509 - 514年,1986页。视图:出版商的网站|谷歌学术搜索
18. t·h·科尔曼、c . e .雷瑟尔森r·l·莱维斯特和c·斯坦,算法导论书,麻省理工学院出版社和麦格劳-希尔公司,第二版,2001年版。
19. j . Bang-Jensen和g . z . Gutin标识:理论、算法和应用程序施普林格,伦敦,英国,2009年。视图:出版商的网站|MathSciNet
20. j·埃德蒙兹,“最佳之中”,美国国家标准局的研究》杂志上,71 b卷,第240 - 233页,1967年。视图:出版商的网站|谷歌学术搜索|MathSciNet
21. r·e·Tarjan“寻找最优分支”,网络。一个国际期刊,7卷,不。1、25 - 35,1977页。视图:出版商的网站|谷歌学术搜索|MathSciNet
22. p . m . Camerini l . Fratta f . Maffioli,“注意寻找最佳之中”,网络。一个国际期刊,9卷,不。4、309 - 312年,1979页。视图:出版商的网站|谷歌学术搜索|MathSciNet
23. h . n . Gabow z Galil, t·斯宾塞和r . e . Tarjan”有效寻找最小生成树的算法在无向和指示图,“Combinatorica》第六卷,没有。2、109 - 122年,1986页。视图:出版商的网站|谷歌学术搜索|MathSciNet
24. m·j·尼利和大肠Modiano临时移动网络容量和延迟的权衡,”IEEE信息理论,51卷,不。6,1917 - 1937年,2005页。视图:出版商的网站|谷歌学术搜索
25. Toumpis和a·j·戈德史密斯,”大型无线网络在衰落,移动性和延迟约束”2004年《信息通信。23年度联合会议IEEE计算机和通信的社会2004年3月,卷1,。视图:谷歌学术搜索
26. e . De Souza, i Nikolaidis建模聚合convergecast调度使用限制,”学报》第14届ACM国际会议上建模,分析,模拟无线和移动系统,MSWiM”11,页231 - 234,纽约,纽约,美国,2011年11月。视图:谷歌学术搜索
27. a·e·贾迈勒j .定角色,和d·沙阿,“Throughput-delay权衡在无线网络”2004年《信息通信。23 AnnualJoint会议IEEE计算机和通信的社会2004年3月,卷1,。视图:谷歌学术搜索

版权

版权©2018 de Souza Evandro Ioanis Nikolaidis。这是一个开放的分布式下文章知识共享归属许可,它允许无限制的使用、分配和复制在任何媒介,提供最初的工作是正确引用。