定向扩散路由协议外文翻译

定向扩散的无线传感器网络Chalerek Intanagonwiwat, Ramesh Govindan, Deborah Estrin, John Heidemann, and Fabio Silva摘要-进展处理器，内存和无线技术将能够连接传感，通信和计算的能力小，价格便宜的节点。这些节点的网络可以协调进行的环境现象分布式传感。在本文中，我们探讨了定向扩散范式这种协调。定向扩散是以数据为中心的所有通信进行命名的数据。在定向扩散为基础的网络中的所有节点都应用感知。这使得扩散通过选择良好的经验和路径，通过网络（例如，数据聚合）缓存和处理数据，以达到节约能源。我们探索和评估使用定向扩散的一个简单的远程监控传感器网络解析和实验。我们的评估表明，定向扩散可以达到显著的节能效果，并且可以根据所调查的情况下超越传统的理想化方案（例如，全网组播）。1 介绍 在不久的将来，先进的处理器，内存和无线技术将使小和廉价的节点能够进行无线通信和显著计算。这些设备加入感应功能将会使分布式微感 - 一个在节点的集合坐标，实现活动更大的传感任务成为可能。这种技术可以彻底改变信息收集和在许多情况下的处理。规模大，动态地改变，并且健壮的传感器网络可以部署在恶劣的物理环境，如远程地理区域或有毒的城市地区。他们也将实现低维护传感更良性的，但不太方便，环境：大型工业厂房，飞机内饰等。 为了激励我们的研究，考虑的怎么这么传感器网络将致力于这个简化模型。一个或多个操作人员构成，在网络中的任何节点，表单的问题：“有多少行人，你的地理区域X观察？”，或“告诉我在什么方向的车辆在区域Y移动”。这些查询中指定的区域导致被委派传感器开始收集信息。一旦个别节点检测到行人或车辆的运动，它们可能会影响相邻节点协作，消除歧义行人位置或车辆移动的方向。然后其中一个节点可能会报告的结果返回给操作人员。 通过健壮性，可伸缩性和能效要求的启发，本文探讨了新的数据传播范式，例如传感器网络。这一模式，我们称之为定向扩散1，是以数据为中心。由传感器节点产生的数据被命名为属性 - 值对。节点通过发送兴趣名为数据请求的数据。数据匹配的兴趣，然后“拉”下来，对那个节点。中间节点可以缓存，或转换数据，并且可以直接基于以前缓存的数据（第2节）的兴趣。 使用这种通讯模式，我们的例子中可以如下方式实现。操作人员的查询将被转化为扩散（如广播，地理路由）对在区域X或Y节点，当在该地区的一个节点收到一个零利率，它会激活其传感器，开始收集有关行人的信息。当传感器报告行人的存在，该信息返回沿息传播的反向路径。中间节点可能会汇总数据，例如，更准确地引脚通过组合的些许传感器报告指出行人的位置。定向扩散的一个重要特征是，兴趣和数据传播和聚集是通过局部的相互作用（在一些附近的邻居或节点之间的消息交换）来确定。 定向扩散是显著不同，其中节点通过其端点标识，节点间通信层叠在网络内设置的端至端传送服务的IP式通信。在本文中，我们描述了定向扩散，并说明这种模式的传感器查询，传播和处理的一个实例。我们表明，采用定向扩散可以实现强大的多路输送，凭经验适应网络工作路径的一小部分，并达到显著的节能效果时间中介节点聚合反应的查询（第4章）。我们还实施了几个小的传感器平台定向扩散;我们描述在第5节我们实现设计和我们的经验。 在本文中，我们概述了定向扩散范式，解释其主要特点，并在一些细节描述了定向扩散模式的车辆跟踪传感器网络（第2节）的特定实例。我们指定哪些地方法规实现的利息和数据传输所需的行为。在此过程中，我们将展示如何在定向扩散模式不同于传统的网络和定性认为，这种模式提供了缩放，健壮性和能源效率方面的好处。我们通过定向扩散（第4节）和实施（第5条）的详细的数据包级仿真量化其中的一些好处。C. Intanagonwiwat，R. Govindan，学者海德曼和F席尔瓦与USC/信息科学研究所。 D.雌激素是与加州大学洛杉矶分校。这项工作的早期版本出现在ACM MobiCom的2000论文集17。这项工作是由美国国防高级研究计划局授予下DABT6399-1-0011支持。 1Van雅各布森提出“扩散”命名的属性数据，这个类的应用程序，后来导致了定向扩散的设计理念。(a)兴趣传播 （b)梯度建立 （c)数据传播以及路径加强图1 定向扩散路由协议的过程2定向扩散 定向扩散是由几个要素：兴趣，数据消息，渐变和增强。有兴趣的消息是查询或询问它指定一个用户想要什么。每个兴趣包含所支持的传感器网络进行数据的感测任务的描述。典型地，在传感器网络中的数据是一种物理现象的收集或处理信息。这样的数据可以是一个事件，这是感测到的现象的简短描述。在定向扩散，数据使用属性-值对的名字命名。感测任务（或者其子任务）的传播在整个传感器网络工作有兴趣命名的数据。这个传播设置了网内梯度设计的“画”事件（即数据相匹配的利息） 。具体而言，梯度是接收有兴趣的每个节点创建方向状态。的梯度指向方向设置朝向从其接收了感兴趣的相邻节点。活动开始流向兴趣携带多梯度路径的发起人。传感器网络增强1 ，或少数这些路径。图1示出这些元素。在本节中，我们描述的扩散特别提到一种特殊的传感器网络，一个支持位置跟踪任务的这些元素。正如我们将要看到的，有几个设计选择展示自己，即使在扩散这个特定实例的上下文中。我们对这些设计选择阐述，同时介绍了无线传感器网络的设计。我们的初步评估（第4节）这些重点去选择符号的一个子集。不同的设计选择导致扩散的不同变体（参见16另一种变型），此外，尽管我们描述这种扩散变种基于速率的应用，扩散也适用于事件触发应用程序。2.1命名 在定向扩散，任务描述被命名，例如，描述一个任务属性 - 值对的列表。 A车辆跟踪任务可能被描述为（这是一个简单的描述，请参见第2.2节有详细介绍）： 键入=轮式车辆/检测车辆的位置 间隔时间=20毫秒/将事件发送每20毫秒 持续时间=10秒/为接下来的10秒 矩形= -100，100，200，400/从内部传感器 为了便于说明，我们选择了分区域的代表性，有一些坐标系上定义的矩形;在实践中，这可能是 基于GPS坐标。 直观地说，任务描述指定数据相匹配的属性的兴趣。因为这个原因，这样的任务描述被称为一个兴趣。在回应兴趣发出的数据也被命名使用类似的命名方案。因此，例如，一个传感器，用于检测轮式车辆可能会产生以下数据（参见2.3节的一些属性的说明）：键入=轮式车辆/类型的车辆看到 这种类型的实例=卡车/实例 位置=125，220/节点位置 强度=0.6/信号幅值测量 信心=0.85/信心在比赛中 时间戳=1点20分40秒/事件发生时刻 给定一组由一个传感器网络支持的任务，那么，选择一个命名方案是在对设计定向扩散的第一步网络。对于我们的传感器网络中，我们选择了一个简单的属性值基于兴趣和数据的命名方案。在一般情况下，每个属性具有一个相关的值的范围。例如，属性类型的范围是一组代表的移动物体（车辆书代码值，动物，人类） 。属性的值可以是其范围内的任意子集。在我们的例子中，感兴趣的属性类型的值是对应的轮式车辆还有其他的选择属性值范围（例如，分层）等命名方案（如故意名称1 ） 。一些程度上命名方案的选择会影响任务的表现力，并可能影响扩散算法的性能。在本文中，我们目标是获得扩散模式的初步认识。出于这个原因，可以命名方案的探索已经超出了本文的范围，但是我们已经开始在其他地方的探索 14 （参见第5章） 。2.2兴趣与梯度 第2.1节的命名任务描述构成一个跨估在一些利息通常是注入网络（可能是任意的）节点的网络中。我们使用术语汇来表示这个节点。2.2.1兴趣传播 由于我们选择的命名方案，我们现在描述的兴趣是如何通过传感器网络的扩散。假设一个任务，一个指定类型和矩形，10分钟的持续时间和10毫秒的时间间隔，被实例化的网络中的特定节点。时间间隔参数指定事件的数据速率;因此在我们的例子中，指定的数据速率为每秒100个事件。此汇聚节点记录了任务;任务状态从节点的工期属性指定的时间后清除。对于每个活动任务，水槽周期性地广播一个在表面的消息到多个邻居节点（更有效的方法来发送兴趣后面将要进行讨论）。这最初的兴趣包含指定的矩形和持续时间属性，但包含了更大的时间间隔属性。直观地看，这最初的兴趣可能会被认为是探索性的;它试图确定是否有确实是任何传感器节点该检测轮式车辆要做到这一点，初次试探性的兴趣指定一个低数据速率（在我们的例子中，每秒1个事件） 2 。在第2.4节中，我们描述了如何将所需的数据速率是强化来实现。于是，最初的兴趣采用以下形式：键入=轮式车辆 间隔=1秒 矩形= -100，200，200，400。 时间戳=1点20分40秒/ HH：MM：SS 终止时间=1时30分40秒 之前我们介绍了如何利益的处理，我们强调的是，兴趣是软态 19 ， 29 ， 32 ，将通过水槽周期性地刷新。要做到这一点，水槽简单地重新发送相同的权益，单调递增的时间戳属性。这是必要的，因为兴趣不可靠整个网络传播。刷新率是一个协议的设计参数折衷的开销增加健壮性失去兴趣。 每个节点维护利益兴趣缓存。在缓存中的每一项对应一个不同的兴趣。两种利益是不同的，在我们的例子中，如果他们的属性类型的不同，或它们的矩形属性（可能部分地）不相交。在高速缓存中兴趣列表不包含关于水槽但几乎紧接前一跳的信息。因此，不同范围活动动的兴趣。我们的定义的特殊兴趣也让兴趣聚合。两个兴趣I1和I2 ，具有相同的类型，完全重叠矩形的属性，可以，在某些情况下，表示与单个息条目。其他兴趣聚合是未来研究的一个课题。 一个条目的缓存有几个字段。一个时间戳字段表示过去的时间戳3收到匹配的兴趣。的兴趣条目还包含几个梯度字段,每一个邻居。每个梯度包含一个数据速率要求的领域指定的邻居,源自于兴趣的间隔属性。它还包含一个时间字段,源自于时间戳和到期利益的属性,并指示近似一生的兴趣。这个时间必须超过网络延迟。 当一个节点收到感兴趣时,它检查是否在学习存在于缓存中。如果匹配条目不存在(匹配确定通过上述定义指定的不同的利益),节点创建一个条目。感兴趣的参数条目实例化从接收到的利益。这个条目有一个梯度对邻居的利益,与指定的事件数据速率。在我们的例子中,一个邻居的下沉将设立一个兴趣条目的梯度每秒1事件向下沉。为此,它必须能够区分个体的邻居。任何本地独特的邻居的标识符可以用于一目的。这样的例子标识符包括802.11 MAC地址8,蓝牙13集群地址,或本地独特的临时标识符11。如果存在一个感兴趣的条目,但没有梯度的发送这方利益,节点添加一个梯度与指定值。它还更新条目的适当的时间戳和持续时间字段。最后,如果有一个入口和一个梯度,节点只需更新的时间戳和持续时间字段。 在2.3节中,我们描述如何使用渐变。梯度届满时,从其兴趣条目删除。并不是所有的梯度将到期在同一时间。例如,如果两个不同的水槽表达模糊,利益超期时间不同,一些网络中的节点有兴趣加入不同梯度过期时间。当所有渐变为感兴趣的条目已经过期,兴趣条目本身从缓存中删除。收到感兴趣后,一个节点可能决定转发其邻国的一些子集感兴趣。邻居节点,这似乎感兴趣来自发送节点,尽管它可能来自一个遥远的水槽。这是当地一个交互的一个例子。通过这种方式,兴趣分散在整个网络。并不是所有的兴趣收到重发。一个节点可能抑制收到兴趣如果它最近重发一个匹配的兴趣。一般来说，有对邻居几种可能的选择（图2）。最简单的方法是重新播出的利益对所有邻居。这等同于在整个网络泛滥的兴趣;在没有关于它的信息的传感器节点都可能能够满足在表面，这是唯一的选择。这也是我们模拟在第4节的替代品。在我们的例子传感器网络，它也可以是能够进行地理路由，使用一些文献中所描述的技术 23 ，34， 7 。这可以限制拓扑范围为兴趣扩散，由此导致能量节省。最后，在一个静止的传感器网络中，节点可能会使用缓存数据（参见2.3节）直接利益。例如，如果在响应到一个较早的兴趣，从一些派出一些邻居的数据听过一个节点由属性类型指定的区域内的传感器，它可以引导这种兴趣到A ，而不是广播到所有的邻居。 扩散元素设计选择 兴趣传播洪泛基于位置的限制或定向洪水定向传播基于先前缓存的数据 数据传播强化单一路径交付多路径交付质量选择性沿着不同的路径多路径交付与概率转发 数据缓存与聚合健壮的数据交付在面对节点的失败为协调传感和数据减少兴趣方向 路径加强决定何时来加强的规则多少邻居加强的规则负强化的机制和规则图2 部分设计的空间扩散（a) 梯度建立 （b)强化 （c)复合源 （d)多个水槽 （e)修复图3 扩散不同方面的说明2.2.2建立梯度 图3（a）示出了 通过传感器领域被洪水淹没的情况下建立的梯度。不同的是简化 图1描述（b）条，注意到每对相邻的 节点建立对彼此的渐变。这是一个关键 因此当地的相互作用。当一个节点收到兴趣 从它的邻居，它没有办法知道是否是 兴趣是响应一个它发送出去较早，或者是相同的 从另一个兴趣下沉的“另一边”的邻居。 这样的双向梯度引起的一个节点接收一个 从每个邻居低数据速率的事件副本。但是，因为我们后来证明，这种技术可以使快速恢复 。从失败的路径或经验更好的路径加固 （2.4节），而不会招致持续循环（2.3节）。请注意，我们的传感器网络，渐变指定既是数据速率和在其中传送事件的方向。更一般地，渐变指定一个值和方向。定向 扩散模式使设计师可以自由地连接不同语义梯度值。我们已经表明两个例子梯度使用。图1（c）隐式二进制描述重视梯度。在我们的传感器网络，梯度有两种确定事件报告率值。在其他的传感器网络，梯度值可能被用于，例如，概率性转发的数据沿不同的路径，实现一些测量负载平衡（图2）。综上所述，兴趣传播建立的网络状态网络或其部分），方便是“拆”的数据对下沉。息传播规则是局部的，而且有若干相似之处加入传播的一些互联网组播路由协议 10 。一个关键的区别在于加入传播可以利用单播路由表，直接朝着联接源，而兴趣的传播不能。在本节中，我们描述了兴趣传播规则对于特定类型的任务。更一般地，一个传感器网络可支持多种不同的任务类型。兴趣传播规则可以是用于不同的任务类型的不同。例如，的形式的一个任务类型“计数明显轮式数在矩形R的车辆看到，在未来T秒“不能利用事件数据传输速率为我们的例子一样。然而，一些利息传播元素类似于两个：形式缓存项，利息重新分配规则等。在我们的实现（第5章） ，我们已经扑杀这些相似之处成在每个节点处的扩散基质，从而使传感器网络设计可以使用的兴趣繁殖技术（或一库就此而言，在数据后面的章节中讨论的规则针对不同的任务类型的处理和加固）。2.3数据传输 传感器节点是指定的矩形内处理兴趣如前一节中所述。此外，该节点任务的本地传感器开始采集样品（保存电源，传感器关闭，直到任务）。在本文中，我们不讨论的目标识别算法的细节。简言之，这些算法简单匹配采样波形对库的预采样的，存储的波形。这是基于这样的观察该轮式车辆具有不同的声音或震波的体积比，例如，一个人。采样波形可以存储的波形匹配不同程度;该算法通常一定程度的信心与比赛相关联。此外，采样的波形的强度可粗略地表示距离的信号来源，虽然也许没有方向。检测的目标传感器节点搜索其兴趣缓存匹配兴趣的条目。在这种情况下，匹配的条目是一个其矩形包括在传感器位置，以及条目的类型相匹配的检测目标的类型。当它找到一个，它计算的最高它的所有传出的梯度中要求事件发生率。该节点任务的传感器子系统产生的事件样本在这个最高的数据传输速率。在我们的例子中，这个数据速率最初是每秒1个事件（直到加固应用，第2.4节）。源然后发送给每个邻居其中它有一个梯度，事件描述的形式每秒钟：类型=轮式车辆/类型的车辆看到 这种类型的实例=卡车/实例 位置=125，220/节点位置 强度=0.6/信号幅值测量 信心=0.85/信心在比赛中 时间戳=1点20分40秒/本地事件产生的时间这个数据消息是，实际上，单独的单播到相关的邻居。 （所用的确切机制是无线的MAC层的功能并能对性能有显著影响，因为评估第4.4节。）接收数据消息从它的邻居节点试图找到在缓存中的匹配兴趣的条目。匹配规则为在前面的段落中描述。如果不存在匹配，数据电文丢弃。如果存在匹配，则该节点会检查数据缓存具有匹配的兴趣条目相关联。这种缓存跟踪最近看到的数据项。它有几个潜在的用途，其中之一是环预防。如果接收到的数据报文有匹配的数据高速缓存条目，数据电文丢弃。否则，所接收的消息是添加到数据高速缓存和数据消息重新发送到该节点的邻居。通过检查其数据高速缓冲存储器中，一个节点可以判断接收到的事件4的数据传输速率。重新发送一个接收到的数据报文，一个节点需要研究兴趣匹配项的渐变列表。如果所有梯度的具有数据率大于或等于输入的事件发生率，本点可以简单地发送接收的数据消息到适当的邻居。然而，如果一些梯度具有较低的数据速率比其他（所造成的选择性增强的路径，第2.4节），那么该节点可以下变频到合适的梯度。例如，考虑一个节点已接收的数据以每秒100个事件，但其梯度一项（如，组建了一支由第二水槽发起一个模糊的任务与更大的间隔），每秒50个事件。在这种情况下，该节点可以只发送对相应的邻居每隔事件。或者，它可能会插在一个应用程序特定的方式连续两次事件（在本例中，它可能会选择样品具有较高的信心匹配）。环路预防和下变频说明嵌入的所有节点应用语义（图2 ）的功率。虽然这种设计是不相关的传统网络，它与应用程序特定的传感器网络是可行的。事实上，正如我们在4.4节中，它可以显著提高网络性能。在我们的模拟在第4节，作为简化，我们包括在事件描述的数据传输速率。2.4加固路径建立和截断 在我们所描述的，到目前为止该计划，水槽最初并多次扩散的权益，低速率事件通知。我们称这些试探性的事件，因为它们是用于路径的设置和维修。我们呼吁设立探索性活动探索梯度的梯度。一旦源检测到匹配的目标，它发出试探性的事件，可能是沿着多条路径，向下沉。水槽启动后接收这些探索性的事件，它强化一个特定的邻居，以提取的真实数据（即事件在更高的数据速率允许目标高品质跟踪）。我们称接收高品质的跟踪事件数据梯度的建立。2.4.1路径强化建立在一般情况下，此新颖的定向扩散的功能是通过从动局部规则数据实现的。这种规则的一个例子是加强任何邻居从该节点接收到一个以前看不见的事件。为了加强这个邻居，水槽重新发送原利率的消息，但有较小的间隔（更高的数据速率）：类型=轮式车辆 间隔时间为10ms 矩形= -100，200，200，400。 时间戳=01:22:35 终止时间=1时30分40秒当相邻节点接收到这个兴趣，它发现它已经朝着这个邻居的渐变。另外，它注意到了发送方的利益指定一个更高的数据速率比以前。如果这个新的数据速率也比任何现有的梯度较高（直觉，如果从这个节点“流出”有所增加） ，节点也必须加强，至少有一个邻居。它是如何做到这一点？该节点使用其数据缓存于此目的。再次，相同的局部规则选择适用。举例来说，这个节点可以选择从他们第一次收到最新的邻居事件相匹配的利益。另外，它可能会选择从最近收到的新事件的所有邻居。这意味着我们加强了邻居，只有在发送试探性事件。很显然，我们并不需要加强邻居已经在发送流量更高的数据传输速率。这是我们评估在第4节的替代品。通过对本地交互顺序，一个路径是从源节点到汇聚节点建立传输数据。我们上面描述的本地规则，然后，选择一个经验低延迟路径（图3（ b）示出，可导致该路径时的水槽强化的路径）。它是非常活泼的变化，路径质量;每当一个路径传送的事件比别人快，信宿尝试使用这条道路画下去高质量的数据。然而，因为它是由接收一个新的事件触发时，这可能是浪费资源。更多复杂的局部规则是可能的（图2） ，包括选择该邻居从其中大多数事件已被接收，或者邻居的一贯发送事件等邻居节点之前。这些选择，以提高稳定性权衡反应。2.4.2路径为建立多源和汇在描述加固到目前为止，我们可能已经出现了隐式描述一个单源的情况。事实上，这些规则我们已经描述多源工作。为了说明这一点，考虑图3（c ）。假设最初所有的初始梯度是探索性的。根据本拓扑结构，从源节点到汇聚节点的数据通过两个相邻的节点C与D传输，说C有一贯较低的延迟，我们的规则将只到C强化的路径（这是在图所示） 。但是，如果水槽通过D听到B的事件较早，但A的事件5较早通过C ，水槽将尝试从两个邻居（未显示）提取高质量的数据流。在这种情况下，接收器得到两源从两个邻居的数据，能源效率低下的一个潜在来源。能够避免这样的问题增加了一些复杂性16。同样，如果两个水槽表达相同的利益，我们的利益传播，梯度建立和加强规则的正常工作。不失一般性，假定水槽中的Y图3（d ）已增强的高品质的路径的源。但是请注意，其他节点继续接收试探性事件。当一个操作人员的任务的网络在水槽X中相同的兴趣，X可以使用强化规则来实现显示的路径。要确定最好的经验路径，X无需等待数据相反，它可以利用其数据缓存立即提取高质量的数据向它的自我。2.4.3局部修复的故障路径到目前为止，我们已经描述了加固是由一个接收器触发的情况。然而，在定向扩散，其中调解的节点以前增强路径可以申请加固规则。这是有用的，使之发生故障或降级的路径局部修复。失利原因或降解其中已包括节点的能量消耗，并影响通讯（例如，障碍）的环境因素。考虑图3（e ） ，在其中源极和节点C降解和事件之间的链路的质量，经常损坏。当C检测到这种退化 - 无论是注意到，该事件从它的上游邻居（源）报告率现在是低，或实现其他邻居有被发送以前看不见的位置估计 - 它可以应用增强的规则来发现在图中所示的路径。最终，负面强化了直接链接到源（图中未显示）。我们的描述至今掩盖了这样一个事实：加固规则直接应用将导致有损连接器的下游的所有节点也开始增强程序。这最终将导致1凭经验好的路径的发现，但可能会导致资源浪费。避免这种情况的一个方法是C插入位置估计它接收的事件,以便下游节点仍然认为高质量的跟踪。5注意定向扩散、水槽将无法将一个源与一个事件。因此,“事件”是有些误导。我们真正的意思是,数据生成的区分内容从数据中生成的。2.4.4道路截断使用负强化上面描述的算法(2.4.1节)可以导致多个路径被强化。例如(图4(a),如果沉了加强了邻居,然后从邻居接收一个新的事件B,这将增强路径通过B 6。如果路径通过B（即持续更好。,B发送事件)之前,我们需要一种机制来负面强化通过的路径。负强化的机制之一是软状态,即超时,网络中的所有数据梯度,除非他们明确加强。使用这种方法,水槽将定期加强邻居B,并停止强化邻居a .梯度沿路径通过最终会降低探索性梯度。另一种方法,我们在本文评估,是明确降低路径通过发送一个负强化的信息A在这基于速率扩散,负强化是利益与降低数据率。当收到这个兴趣,其降解梯度向下沉。此外,如果所有的梯度现在探索性,负强化这些邻居已经发送数据(而不是探索事件)7。这个序列的本地交互确保路径通过迅速退化,但在资源利用率增加的成本。完成我们的负强化的描述,我们需要指定当地规则节点使用,以决定是否负强化的邻居。注意,这个规则是正交的选择负强化的机制。一个合理的选择这样的规则是消极强化的邻居没有收到新事件(即。,其他邻居持续发送事件之前的邻居)在一个窗口的事件或时间T。当地规则我们在第四节是基于评估的时间窗口中,选择在我们的模拟2秒。这样的规则有点保守和能源效率低下。例如,即使一个事件十是收到第一次从邻居,邻居的水槽不会负强化。其他变体包括负强化少,邻居的新事件已收到。2.4.5循环使用负强化去除除了抑制高延迟或损耗路径,我们当地的负强化规则也用于循环删除,因为循环路径没有交付事件前8(图4(b)。尽管循环消息将立即抑制使用消息缓存,一般情况下,我们仍将受益于删除资源节约的循环路径。然而,这样的循环删除并不总是适当的,专门为一些共享高速与多个源和汇梯度地图。例如(图4(c),如果两个发送区分事件来源,梯度c和C-B不应该被截断,因为他们每个人都有必要提供事件为特定的源库。虽然这种梯度可能提供一些循环事件,他们也始终如一地交付新事件。负强化与我们的保守统治,这些梯度不会负强化。6这条路可能是也可能不是完全不相交的路径通过邻居A . 7这当地规则的作品即使通过的路径和路径通过B部分联合。联合链接不会消极强化,除非路径都是消极的加强。8只考虑到邻居,探索性活动首先是增强,一个可能认为循环路径不会钢筋(特别是对于单源水槽场景)。然而,增强路径在一个给定的探索性活动可能不同于那些在前几轮。虽然没有强化循环路径,一个加强联盟路径可以包含来自多个轮循环。（a) 多路径 （b)一个可移动的循环 （c)一个不可移动的循环图4 负强化的路径截断和循环去除此外,即使没有循环,它仍然是合理的保持我们的负强化规则不会保守,这样有用的路径截断。例如(图3(c),两种来源可能持续发送区分事件,但他们也会偶尔发送相同的事件虽然。虽然来自不同的来源、扩散的相同的事件被认为是重复9。的路径从一个来源将截断如果负强化规则太激进的反对重复。相反,鉴于我们保守的规则,没有来源负强化。2.5讨论引进的各种元素的扩散,我们也含蓄地描述一个特定兴趣-属性设置渐变画下来的数据。定向扩散范式本身不限制设计师这个特殊的用法。其他用法也是有可能的,比如一个节点可能传播数据在没有利益的情况下,隐式地设置渐变时这样做。这是有用的,例如,自发传播的一些部分传感器领域的一个重要事件。传感器节点可以使用此警告其他传感器节点的活动。此外,其他设计选择为每个元素的扩散也可能的(参见图2)。我们的描述指出了扩散的几个关键特性，以及它是如何不同于传统的网络。首先，扩散是以数据为中心;在扩散为基础的传感器网络的所有通信使用的兴趣来指定命名的数据。第二，在扩散的所有通信是邻居到邻居，不像端至端在传统的数据网络的通信。换句话说，每一个节点是在传感器网络中的“结束”。在这个意义上，有一个传感器网络中没有“路由器”。每个传感器节点可以解释数据和利率的消息。这种设计的选择是由任务特异性传感器网络的理由。传感器网络作品不是通用的通信网络。三，传感器节点并不需要有全局唯一标识符或全局唯一的地址。节点，但是，确实需要邻里之间的区别。最后，在基于IP的无线传感器网络，例如，传感器数据收集和处理可能会对每个由专门的服务器可能，一般来讲，可以远离感测到的现象去除的集合形成。在我们的传感器网络中，由于每个节点可以缓存，聚合，和更一般地，处理消息，通常需要执行协调感测接近所感测到的现象。9在扩散，事件是独立于他们的来源（即，节点将无法向源与事件相关联）。扩散的当前实例只维护高速率的路径，沿着该有用的（新的）的数据一致地传送，而不管源。因此，通常，我们不保证将有至少一个高速率的路径从每个源到每个接收器（例如，当一些来源不产生有用的数据）。扩散显然与传统的网络数据狂胜ING算法。从某种意义上说，它是一种反应式路由技术，因为“路线”按需建立。然而，它不同于在几个方面其他临时反应式路由技术（参见第6节） 。首先，没有试图找出源之间的一个无环路的路径和水槽的数据传输开始前。相反，约束或定向泛滥是用来设置的路径的多重性，和数据消息最初冗余地沿着这些路径发送。第二，此后不久，加固试图减少这种多重性的路径，以一个小数目，是根据经验观察路径的性能。最后，消息缓存用于执行环路避免。利息和梯度设置机制本身并不能保证无环路路径之间的源和汇。为什么要设计这种特殊的选择吗？在这个重新搜索开始时，我们有意识地选择了探索建立严格使用本地（邻居到邻居）通信网络路径的路径设置算法。这一选择背后的直觉是观察，物理系统（如蚁群5）是建立传输路径使用这种通信规模良好，而且非常强大的（参见第6节） 。但是，使用严格的本地通信意味着路径设置不能使用全局拓扑指标;本地通信意味着，只要一个节点都知道，它从邻居接收到的数据从该邻居10来了。这可能是高效节能的变化时，在拓扑不需要通过网络传播高度动态的网络。当然，所产生的通信路径可能是次优的。然而，能源效率低，由于路径子最优可以通过精心设计的网络聚合技术来反击。整体而言，我们认为这种方法折衷，增加耐用性和一定规模的能源效率。在数据消息10显示的位置信息可能会泄露，否则，但这些信息仍然不包含拓扑指标。图5 正方形网格拓扑结构的一个例子最后，它可能出现的，我们选择了特定的实例化，定位，跟踪，具有有限的适用性。我们是里弗，但是，这样的位置跟踪捕获很多的一大类远程监控传感器网络的基本特征。我们强调的是，尽管我们已经在一些细节讨论我们的跟踪网络，各种机制的很多实验和评估是必要的 。我们完全理解扩散的一般健壮性之前，规模和性能的影响，以及我们的一些特别的机制。这两个接下来我们将对这个方向化初始步骤。3分析法评价 在本节中，我们给出了数据传输成本，定向扩散和两个理想化的方案的分析评价：无所不知的组播和洪水。这种分析是为了检查定向扩散背后的知识，并强调一些扩散和其他方法之间的差异。对于解析易处理，我们分析在一个非常简单的，理想化的设定，这三项计划。我们假设一个正方形网格组成的N个节点的。在此网格中，节点的传输范围是这样的，每个节点都可以与在网格上恰好8相邻节点进行通信。图5示出对节点能够相互通信之间的联系。所有n个源被置于沿网格上的左边缘节点，而所有m个接收器被置于沿右边缘。第一个来源是在左侧边界的中心。Ith节点是dni/2上一跳或者下一跳的第一个源节点。此安置方案也可用于接收器不同之处在于两个相邻的接收器之间的距离为dm跳而不是dn跳。由于源节点和汇聚节点都只有垂直放置，不能小于最大值（ndn; mdm）。3.1 洪泛在洪泛方案，洪泛来源的所有事件到网络中的每个节点。洪泛是一种水印定向扩散;如果后者不比洪泛好的话，它不能被认为是可行的传感器网络。在此分析评价，我们测量的性能是从每个源一个事件的发送和接收的所有接收器的总成本。我们定义成本作为一个单元进行消息传输和一个单位的消息接收。这些 假设显然理想化两种方式。发送和接收的成本可能不相同，而且有可能会感兴趣的其他指标。我们考虑更多现实的措施与仿真第4节。通过这一措施，洪泛的代价记为Cf (N; n; m; dn; dm)，或者Cf干脆由以下公式给出洪泛n个事件（从每个源一个事件）的传输成本是NN，因为每个节点每个事件只发送一个MAC广播。相反，每个节点都可以从所有的邻居收到相同的事件。因此，对于那些n个事件的接收费用由2n倍确定链路的网络中的数 在数据传输费用洪泛为O（NN），其成本高于其他计划（见第3.2和3.3）。3.2无所不知组播 在无所不知的组播方案，每个源发送其沿最短路径组播树的所有汇事件。在我们的分析，以及在第4节中描述的模拟，我们不考虑树的建设成本。无所不知的多播而不是表示最好的性能实现在一个基于IP的无线传感器网络，而不考虑开销。我们使用这个方案给读者一些直觉如何在网络处理机制效果的选择性能。对于无所不知组播，确定数据传递成本由在其源特定的最短路径树的链接数量的两倍。然而，即使在这个简单的网格拓扑中，有针对每个源库对数的最短路径。我们选择使用下面的简单的，确定性规则的最短路径。从信宿到源极，一个对角链路始终是下一跳，只要它导致了最短路径。否则，一个水平连接被选中。此路径选择规则被重复，直到源节点为止。因此，没有最短路径包括垂直的联系。逐渐的，无所不知组播的数据传输成本趋于： 3.3定向扩散 扩散的分析进行沿着相同的路线是全网的组播。为了简化分析，我们假设该扩散的本地化算法构造的树是根植在每个源的最短路径树的“联盟”。这个假设是约有效的，当网络工作在低负荷水平。的许多可用的最短路径此外，扩散根据下列规则选择之一：从一个源节点接收到的汇聚节点，一个对角链路总是下一跳，只要它是沿着最短路径的源;否则，一个水平连接被选中。这条规则是同一个，我们用全网组播。尽管使用相同的路径选择方法，扩散Cd的成本不同的，主要是因为应用程序级的数据处理从全知多播的。特别是，如果所有的源发送相同的目标位置估计，然后，由于扩散可以执行应用程序级别的重复抑制，扩散的数据交付成本是两次链接的数量在联盟的所有最短路径树。3.4比较 洪范的数据传输Cf成本的级别比全网组播Co较高几个数量级。但是，Co仍然比Cd扩散成本较高，为了验证这一推理，数据传输费用（由网络规模标准化）的定向扩散和无所不知的组播使用的各种参数绘制（即N，m和n）。作为源的数量和吸收的增加（图6（a）和图6（b）时，节约成本由于在网络处理扩散（例如，重复的抑制）变得更加明显的（因为Cd增加以较低的速率比Co）。特别感兴趣的是成本的情节与网络规模(图6(c)。由于扩散可以抑制应用程序级副本,一个期望,Co是nCd .这并不持有的主要原因是我们的分析有些保守估计扩散的成本。在实践中,扩散会负强化的几个链接,包括我们的分析。4仿真 在本节中，我们使用数据包级仿真探索，在一些细节，我们的一些设计选择的影响。这种检查补充并扩展了我们的第3节的分析，本节介绍我们的方法，比较了对一些理想化的方案扩散的表现，然后考虑网络动态仿真的影响。4.1目标，指标和方法 我们实施我们的车辆跟踪在NS-22模拟器定向扩散的实例（目前NS重新租赁与扩散的支持可以从http:/www.isi.edu/nsnam/ns下载）。我们进行本次评测的学习目标有四个方面：首先，验证和补充我们的分析评价。其次，了解动态，如节点故障，对扩散的影响。第三，探索无线电MAC层上的扩散性能的影响。最后，研究了定向扩散性能参数的选择的敏感性。我们选择三种指标来分析定向扩散的性能，并把它比作其他计划：平均耗能，平均延迟和不同的事件投递率。平均消耗能量测量总的比例消散每个节点能在网络中看到的水槽不同的事件的数目。此指标计算中，向水槽提供有用的跟踪信息的节点所做的平均工作。度量还表示传感器节点的整体寿命。平均延迟测量的平均单向延迟发送事件和接收它在各片之间观察到。此度量定义了传感器网络提供的位置估计的时间精度。不同的事件传递比是接收到最初发送多个不同的事件的数量的比率。类似的指标被用于早期作品比较的ad-hoc路由方案4。我们研究这些指标作为传感器网络规模的函数。为了研究扩散的网络大小的函数的性能，我们产生了各种不同尺寸的传感器领域。在每一个实验中，我们研究五种不同的传感器领域，范围从50到50个节点单位250个节点。通过随机放置节点在160米由160米方产生了50节点传感器领域。每个节点都具有40米的无线范围。通过缩放平方和保持无线电范围内保持恒定，以便保持约传感器节点恒定的平均密度中产生的其他尺寸。我们这样做是因为一个传感器字段的宏观连通的平均密度的函数。如果我们一直保持在传感器领域的区域不变，但增加了网络规模，我们可能已经注意到性能的影响不仅是由于节点数量较多，而且由于增加了连接。我们的方法分解出后，让我们来研究网络规模的单独对我们的一些机制的影响。在NS - 2模拟器实现了1.6 Mb / s的802.11 MAC层。我们的模拟使用修改后的802.11 MAC层。要更加紧密地模仿现实的传感器网络收音机 21 中，我们改变了NS - 2的无线能量模型使得空闲时间功耗约为35MW ，涨幅近10 ，其接收功耗（ 395MW ） ，以及约5它的发射功率耗散（ 660兆瓦） 。该MAC层不完全令人满意，因为能源效率提供了一个令人信服的理由选择一个TDMA的MAC风格的传感器网络，而不是一个使用基于竞争的协议 28 。简单地说，这些原因都与在空闲的时间间隔消耗的无线电能量;与TDMA的MAC风格，可以把收音机待机模式在这样的时间间隔。相比之下， 802.11无线电消耗尽可能多的权力，当它处于空闲状态时，它接收到传输的。在4.4节中，我们分析一个MAC能源车型的影响，其中监听传输消耗的能量是接受他们。最后，在我们大部分的模拟，我们使用它由五个来源和五个接收器一个固定的工作负载。所有源被随机地从节点通过70米方在传感器领域的左下角选在70米。接收器是在传感器领域的均匀分散。每个源每秒产生两个事件。速率为探索事件被选择为在50秒内一个事件。事件被建模为64字节的数据包，利益为36字节的数据包。权益周期性产生的，每5秒，并且兴趣持续时间为15秒。我们选择的窗口负强化是2秒。这些参数的选择是由特定的传感器网络在考虑两个通知（小事件说明，一个地理区域内的资源），并通过我们的探索欲望在非拥堵制度传感器网络的制度（以简化我们对结果的理解）。在每个图的数据点代表平均值通常情况下，95的置信区间。（a) 汇聚节点数量的影响 （b)源节点数量的影响 （c)网络规模的影响图6 在定向扩散和无所不知的组播各种参数的影响4.2比较评价我们的第一个实验比较扩散到无所不知的组播和洪范方案在网络中传播数据。图7（a ）示出了平均消耗每包能量作为网络大小的函数。无所不知的组播消耗比一半多能量每包每个节点比洪范少一点。它实现了通过提供事件沿着单一路径从每个源到每个接收器这样的能量效率。定向扩散具有比无所不知的组播明显更好的能源效率。对于一些传感器领域，其消耗的能量只有60是无所不知的组播。作为具有全知多投，它也通过降低指的冗余数据被传递的路径数达到显著的节能效果。此外，从扩散在网络汇聚显著福利。在我们的实验中，源节点提供相同的位置估计，并且中间节点抑制重复的位置估计。这对应于有，例如，一个单一的车辆在指定的区域的情况。那么，为什么，因为有五个来源，是扩散（负强化）不近五倍的能源效率比无所不知的组播？首先，这两项计划花费可比和不可忽略的能源侦听传输。其次，我们的选择加固和负强化的结果在定向扩散经常支取高质量的数据沿着多条路径，从而消耗更多的能量。具体来说，我们的补强规则，强化谁发出了一个前所未见的事件一个邻居是非常积极的。相反，我们的负强化的规则，这负疑心加强邻居谁只持续重复发送（即先前看到的）事件，是非常保守的。（a) 平均能量消耗 （b)平均延迟图7 定向扩散与洪泛、无所不知的组播图7（b）绘出观察到网络大小的函数的平均延迟。定向扩散具有比较洪范的组播延迟。这是令人鼓舞的。以第一近似值，在一未拥塞传感器网络和在没有障碍物，最短路径也是最低延迟的路径。因此，我们的补强规则似乎在寻找低时延路径。然而，经历洪范的延迟几乎是要比其他方案高出一个数量级。这是MAC层的一个神器：避免广播碰撞，随机选择延迟强加给所有的MAC广播。洪范独家使用MAC协议。扩散只使用如此广泛的转换来传播的初始兴趣。在传感器电台，它采用的TDMA MAC层，我们可以期望发现其他与洪范相比的计划延迟。总之，定向扩散表现出较好的耗能比洪范组播，具有良好的时延性能。最后，所有的三种方案所产生的近1（未示出），一个事件传递比，因为该实验中忽略网络动力学和是畅通无阻。4.3动力学影响为了研究在定向扩散动力学的影响，我们模拟节点故障如下。对于每个传感器区域，反复关闭30秒的节点的固定部分（ 10或20）。这些节点被均匀地从传感器字段选择，与该上下沉的最短路径树的源节点的相等分数也关闭，以相同的持续时间的额外的约束。这样做的目的是为了在扩散是最有可能使用的路径创建节点故障，并在网络中其他地方创建随机故障。此外，先前的实验不同，每个源端发送不同的位置估计（对应于其中每一个源“看见”不同的车辆的情况） 。我们这样做是因为动力学的影响不太明显，当扩散抑制来自其他来源的相同位置的估计。我们也可以学习其他协议动力学的影响，但是，因为无所不知组播是一种理想化的方案，并没有考虑到的路由重新计算成本，它并不完全清楚，这样的比较是有意义的。我们的动态试验规定了数据分发协议相当不利条件。在任何时刻，10或网络中的节点的20是无法使用的。此外，我们不允许节点故障之间的任何“稳定时间”。即便如此，扩散能维持合理的，如果不是恒星，事件传递（如图8（c），而产生额外低于20的平均延迟（如图8（b）。此外，该平均耗散的能量实际上提高了，在有些情况下，在节点故障的存在。这是一个有点反直觉的，因为人们会预期定向扩散会花费精力找到改变本地路径。事实证明，然而，我们的负强化换货规则是保守的，以至于一些增强路径（高品质路径）在正常运行维持生命。因此，在我们模拟的动态水平，扩散不需要做额外的工作。较低的能源损耗结果从一些高品质的路径的故障。我们把这些结果表明，在扩散的机制是在动力学的水平，我们已经探索了相对稳定。通过这一点，我们表示扩散不，在动态，招致显着更高的能量耗散或事件传递延迟。（a) 平均能量消耗 （b)平均延迟 （c）事件投机率图8 节点故障对定向扩散的影响4.4数据聚合和负强化的影响为了解释什么有助于定向扩散的能源效益，我们现在介绍两个独立的实验。在这两个实验中，我们没有模拟节点故障。首先，我们计算扩散的能量效率与不聚合。从4.2节回想一下，在我们的模拟中，我们实现一个简单的聚合策略，其中一个节点抑制由不同的源发送相同的数据。如图9所示，扩散消耗近5倍的能量，在更小的感测区域，因为当它可以抑制重复。在更大的传感器领域中，比例为3 。我们保守的负强化制度占扩散性能的差异没有抑制作为网络规模的函数。用的源和汇的数目相同，较大的网络中有较长的备用路径。这些备用路径由负筋截断，因为他们始终如一地提供事件与较高的延迟。因此，较大的网络消耗更少的能量而不抑制。我们相信，抑制也表现出相同的行为，但能量差是比较小的。（a) 复加强 （b)重复抑制 （c)高闲置射频功率图9 各种因素对定向扩散的影响 第二个好处我们量化是负强化的机制。这种机制李子了更高的延迟路径,并且可以为节约能源做出重大贡献。在这个实验中,我们选择性地关掉负强化和比较的定向扩散性能和加固。直觉上,人们会期望消极控制肯定为节约能源做出重大贡献。事实上,如图9(a)所示,扩散没有负强化消耗两倍的能量,当负面的控制采用肯定的。这表明,甚至我们来讲有效负强化规则删除路径提供一贯高延时。 在没有负强化或抑制，扩散的延迟增加三至八个因素（图表不包括由于篇幅）。这是802.11 MAC层的神器。在扩散，传输的数据流量使用MAC单播。随着越来越多的路径被使用（在不存在负强化），或数据的多个拷贝被发送（不抑制），MAC层的信道争用的增加，从而导致回退和随后的延迟。4.5敏感性分析 最后，我们评估我们的比较（化节4.2）为我们的首选能源模型的灵敏度。扩散的敏感性等因素（数字汇，源极区域的大小）中有更详细18中讨论。 在我们的比较，我们选择了无线电功耗参数，以更紧密地模仿现实的无线电传感器21。我们重新运行第4.2节的比较，但功耗媲美的ATT公司的无线网络：1.6W传输，1.2W接待和1.15W闲置30。在这种情况下，如图9（c）所示，本方案的区别消失。在这个制度下，我们的国家更强大泛滥的所有事件。这是因为空闲时间能利用完全主宰所有方案的性能。这就是为什么传感器收音机非常努力，以尽量减少监听传输的原因。5实施我们已经使用特定的应用程序，例如，迄今描述的定向扩散。然而，这是可取的，以避免重新实现扩散机制为每一个新的应用程序。为此，我们已经实现了一个通用的扩散基材和该代码移植到多个平台，包括WINSng 2.0节点， USC / ISI PC/104节点，微尘，和在NS - 2模拟器模块（扩散代码可以下载从http:/www.isi 。埃杜/ scadds / testbeds.html ） 。在此基板之上，几个应用程序（例如，协同检测，嵌套查询，自适应保真）的制定是在重新搜寻者在BAE系统公司，美国康奈尔大学和宾夕法尼亚州立大学的合作。我们的平台，应用，经验和属性系统是如何影响的细节应用程序可用在别处 14 。我们的通用扩散基材出口两个应用Pro的编程接口（API ） 6 ：一个网络路由API和一个过滤器API 。前者被调用的源和汇，而后者能够在网络处理事件。5.1网络API 网络路由的API是基于发布/订阅模式，并与丹棺材和麻省理工学院/林肯实验室的丹面包车钩被开发了。该接口支持两个操作。接收器可以订阅命名事件，源可以发布事件。扩散基板隐藏的公布的数据是如何传递给用户，我们在第2节所描述的路由算法的细节。事件的发送和异步到达。当事件到达一个节点时，会触发回调到相关的应用程序（那些已订阅相匹配的属性）。在扩散，数据使用属性 - 值对的集合命名。网络路由的API的一个重要特点是，它定义了一个通用的属性类。每个属性都有几个领域： 键表示属性（纬度，经度，频率）的语义。 操作员介绍了如何在两个属性进行比较的属性将匹配。运营商包括：平等，其他的简单比较（不相等，小于，大于，等等），和“属性存在”（等于 - 任何东西）。 类型表示什么算法来匹配属性时运行。我们目前正在实施的32位整数，32位和64位浮点数，字符串和BLOB（不解释）属性。 属性（其数据）的价值，它的长度（如果长度不是从类型的隐） 这种方法具有规范属性的语法和结构，并允许应用程序重用属性处理和匹配的代码的优势。5.2过滤器API 而发布/订阅API允许端点发送和接收数据，在网络处理与过滤器API的关键是扩散性能。应用专用模块可以在摆摊的过滤器中的扩散基材影响的数据，因为它移动通过网络。使用清单在悼念匹配传入的数据指定每个过滤器。当接收到匹配的过滤器的数据时，在基片传递事件的预测应用模块。该模块可以在事件执行一些特定应用的处理;它可以汇总数据，生成增援，甚至使用网络路由的API发行新订阅。在情况下，事件匹配属于一个以上的应用程序模块的过滤器，一个静态优先级顺序确定哪个模块是第一递给该事件。然后该模块可以决定允许其他应用模块对应对应到低优先级的过滤器来处理事件，或者可以选择不这样做。6相关工作分布式传感器网络已经开始在过去几年中得到关注。然而，我们的工作已被告知并受其他各种研究工作，这是我们现在描述。分布式传感器网络是无处不在的计算的一个具体实例作为设想的韦泽 33 。早期的普适计算的努力，但是，没办法的可扩展节点的协调问题，更注重问题的小，无线的设计和包装设备。最近的努力，如WINS 28和小型无线设备的微微网 3 认为网络和通信问题。在WINS项目在确定可行的无线电设计的低功耗环境遥感取得显著进展。他们的项目集中还需要对网络的自组装低级网络同步。我们的定向扩散的原语提供节点间的通信，一旦网络的自组装完毕。该微网项目更侧重于使家庭和办公室的信息发现。其工作依赖于集中式基础设施，而不是自组装网络。此外，最近的努力（即SPIN 24 和LEACH 15 ）所指出的一些呈扩散状应用特异性传感器网络的环境中的优势。特别是， SPIN展示