毕业设计外文资料翻译-低功耗无线网络的扩展网络结构的设计与实现

毕业设计外文资料翻译学院：专业班级：网络工程12（1）学生姓名：学号：指导教师：外文出处：(外文)Jonathan

W.Hui[美]AnExtendedInternetArchitectureforLow-PowerWirelessNetworks-DesignandImplementation,2008

附件：1.外文资料翻译译文；2.外文原文指导教师评语：该英文资料选择合理，与毕业设计论文相关度较高。专业术语、词汇翻译的准确度适中，体现了基本的专业英语应用水平。翻译工作认真细致，严格按照规定，翻译材料能与原文能基本保持一致，能正确表达出原文意思，细节处理得当。翻译字、词数满足要求。翻译材料语句通顺，符合中文的表达习惯。翻译工作能够严格按照规定，达到考核、提高学生英语应用水平的目的，圆满完成要求。签名：2015年10月14日第第页，共27页1．外文资料翻译译文低功耗无线网络的扩展网络结构的设计与实现第7章网络层转发在这一章中，是基于IPv6网络层的第二部分：转发。我们提出了一个高效的代理设计。IP网络层必须提供足够高的“尽力而为”的数据报传输允许有效的端到端通信和可靠的不指定用于转发机制，允许我们选择必要的代理。我们代理的设计主要关注的是能源高效的转发和利用在传感器网络社区开发的技术，包括逐跳传输和拥塞控制、流媒体和QoS。货代还支持使用流的高效多播转发。7.1能源高效的数据转发知识产权结构从路由中分离转发。货代负责从接口接收数据，在转发表中查找下一跳的表演，和提交的信息在适当的接口传输。路由器负责管理转发表中的条目。相反，多传感器网络工作，通常将转发和路由一起，我们基于IPv6的架构保持分离，如图7.1所示。图7.1：转发和路由的分离。从路由中分离转发。接收到的数据报的不是注定的节点被放置在一个转发队列。货代流程信息在转发队列进行转发表查找来确定下一跳的目的地和提交的数据链路层的传输。路由器只负责维护转发表项。转发表作为一个狭窄的接口之间的转发和路由器。IP网络层必须提供足够高的最好的数据报传递允许端到端的机制来实现有效的沟通和可靠传输。但是，知识产权并不需要使用特定的机制或软件体系结构来实现这些机制。转发机制可以有一个显着的整体性能的影响，以及在有线和无线环境中的研究。互联网的快速增长，连接技术的显着进步，数据流的增加导致过去的努力，专注于最大限度地提高整体吞吐量和公平性为许多独立的流量。天真的代理政策，不要在下一跳的DES目的可以导致更高的平均入住率和更频繁的队列溢出队列拥塞响应。更高的通信延迟和丢失率直接转化为较低的吞吐量，尤其是当它与诸如TCP端到端的拥塞控制机制。机制随机下降的消息，以保持平均队列大小小[55，193，69]，提供直接反馈给源[144]，执行逐跳的流量控制机制[125，130，114]，并增加了可靠性和可见性的有损，无线连接[7]已经提出，主要是提高吞吐量和公平性。典型的传感器网络应用程序的工作负载有较低的总吞吐量和信道利用率往往要比传统的IP网络的假设。作为一个结果，这可能发生在拥塞更可能是暂时的现象，而不是常见的情况。例如，许多应用程序，报告一到几个数据报在分钟为时间周期。一些传感器网络应用程序可能需要对大量数据的频繁转移，但很少从多个节点同时。在许多情况下，传感器网络应用可以容忍通信延迟，但可能需要罕见但时间敏感的事件或报警，低延迟的通信。而不是吞吐量和公平性，我们更关心的是实现高的端到端的成功率，高能量效率。没有惊奇的是，能源效率是一个典型的传统知识产权网络，能源是充足的。然而，在传感器网络社区的努力，也没有解决节能转发，即使不受IP框架。虽然现有的工作都集中在传输效率，这个度量的信息传输，而不是发送和接收的能量成本的数目仅解决。随着占空比的链接，将能源成本可以通过级或更多取决于优化的链路层可以采用顺序不同。将多个消息转发到同一个下一个跳的目的地，更有可能利用链路层中的调度和流优化。广播传输往往比单播传输更高的能源成本，因为它要求所有相邻节点唤醒使用全唤醒信号或全网同步。窥探传输从相邻节点接收成本显著增加，可能是由一些链路协议由于每个邻居的状态要求禁止。传感器网络中存在许多的努力依靠广播和监听原语逐跳反馈[45，81，96，146，178，185]。不同的交通特点和需要引起我们的反思传感器网络转发机制实现节能的交付。在这一章中，我们提出的转发机制，有效率作为一个主要目标。能源效率也意味着高成功率的数据报传输，任何回落的消息是浪费资源。高效的单播转发支持三种机制：（一）逐跳恢复，（二）流，和（三）拥塞控制。由于这些机制往往贸易的增加延迟的能源效率，货运代理也适用于简单的服务质量的机制，允许上层（即，运输）选择转发策略。高效的多播转发支持的滴流算法。本章所讨论的所有机制都很简单，不需要任何流状态。用于实现知识产权转发的机制大多是独立的。我们的架构定义的链路本地范围内的无线通信范围内的节点，需要路由协议，在网络层操作。然而，代理可以发生在网络层（如做与传统IP转发）或在链路层（如用MPLS）。如3章所讨论的，链路和网络层转发的方法有各自的权衡。在本章中，我们开发的转发机制是不特定的层转发。7.2单播转发7.2.1背景传统上的知识产权结构将可靠的交付和流量控制的传输层，放置这样的功能，仅在结束点。传输控制协议（TCP）是成为主流的这种机制仍然是广泛使用的今天，[141]。TCP提供可靠的数据流通过实施端到端重传，在终点没有明确承认的数据转发。此外，TCP推断关于网络状态的观察通信的吞吐量，延迟和丢弃的消息进行流量控制[85]。TCP尝试通过操作接近拥塞点尽可能最大化吞吐量。TCP的端到端性能优雅的保持功能的结束点和叶子的核心网络的简单，但缺乏完整的网络可视性。TCP假定拥塞丢包的原因，不能区分排队延迟和通信延迟，无法确定拥塞程度。此外，通信时延限制TCP可以快速响应不断变化的条件。有趣的相互作用，从尾部下降代理引起的网络广泛的同步反应时，拥塞，降低整体吞吐量。这些挑战有限的最大的吞吐量的TCP实现，以及流之间的公平性。TCP的端到端性能优雅的保持功能的结束点和叶子的核心网络的简单，但缺乏完整的网络可视性。TCP假定拥塞丢包的原因，不能区分排队延迟和通信延迟，无法确定拥塞程度。此外，通信时延限制TCP可以快速响应不断变化的条件。有趣的相互作用，从尾部下降代理引起的网络广泛的同步反应时，拥塞，降低整体吞吐量。这些挑战有限的最大的吞吐量的TCP实现，以及流之间的公平性。从网络本身的额外援助是必要的，以提供更大的可视性，提高网络的整体性能。一类努力辅助的端到端速率控制器正在进行的拥塞检测和通知机制在网络。一些提供提前通知，在拥塞发生之前，随机丢弃数据包，隐式通知结束点，拥堵是近[69，85，193]。他人盗用数据包信息提供明确的通知[94，145]或发送色情短信回源[144]。一些努力将检测与通知分离。另一类的努力，包括逐跳控制，放置速率控制器在网络中除了拥塞检测和通知[114，125，130]。跳的跳机制是能够检测，提供反馈，并反应条件直接在哪里发生。作为一个结果，逐跳的机制是更能够迅速和适当的反应当地的条件。逐跳机制，自然提供回压的所有方式的来源，才会发生网络拥塞。相反，端到端的机制遭受较大的通信延迟，缺乏的原因或位置的拥塞时，它会发生无法区分的排队延迟和传播延迟。路由的变化，例如，可能会导致沿一个路径的通信特性的显着变化，和端到端的机制可能需要显着的时间来检测和反应的变化。跳的跳机制可以立即检测和反应的路线变化所发生的地方。在无线空间中，逐跳机制被广泛用于转发消息。无线链路的到来，如WiFi和蜂窝，无效的TCP的拥塞的假设是信息下降的主要原因。最初的广泛部署的无线链路大多是基础设施的基础上，在那里的第一个和最后一个可能是无线。即使如此，链路层恢复和跨层优化，使消息下降到传输层的原因已经被证明显著提高了其性能[7]。跳的跳机制也被证明是有益的多跳无线网络，其有高空间和时间的变化，一个共享的无线介质，和有限的通信资源是最好的服务，通过逐跳机制，可以快速反应当地条件[45，96，146，178185，81]。此外，跳的跳恢复使用，用来提高终端到终端的可靠性[158，177]。无线有较高的损失率，损失率和端到端增加多项式与无线数跳。仅仅依靠端到端重传机制意味着，回收成本也会随着跳数的多项式增长。相比之下，跳的跳数的成本增加线性的跳数。有趣的是，一些机制提出了直接解决能源效率。一些努力，试图通过评估传输效率，以解决能源效率，并指出浪费的传输和浪费能源之间的关系。然而，甚至更少的努力迄今已评估他们的设计对占空比的链路协议。占空比的链接可以极大地影响依靠窥探或广播传播反馈信息的协议，都可以在责任是昂贵的循环操作。链路传输的成本也取决于什么优化的链路可以应用。例如，提交消息一批可能允许链路层缓冲启动成本在多个传输。在下面的章节中，我们提出一套转发机制，寻求减少转发数据包沿着路径的能耗，包括逐段恢复、流和拥塞控制。这些机制通常是在通信延迟的成本降低能源消耗，所以我们也解决简单的服务质量（服务质量）机制，允许上层指定的政策。7.2.2逐跳的恢复转发器实现了逐跳恢复增加端到端的传输速率发送数据报的时候。改进的端到端的传输速率传送数据报的整体能源效率增加。消息未能到达目的地是浪费能源，一些能源一直没有提供数据报。改进的端到端的传输速率也降低了使用端到端可靠传输的触发恢复机制的频率。相比于端到端重传，逐跳传输只发生到需要它们的地方。逐跳转发只负担节点附近传输故障发生时，能迅速适应当地的重发，但负担的路径上的所有节点从问题的来源，增加恢复延迟和整体能源成本。重发为了减少丢包，货代默认为监护权转移的方法，只有离开的消息后下一跳地承认接受在转发队列的最终目的地或安置。监护权转移的方法试图通过减少丢包提高能源效率，但也导致了更大的队列占用的通信延迟。传统的尽力而为的代理往往下降的消息，在试图保持队列占用小，限制流量增多，可能会影响其他附近的流动范围，并提供隐式拥塞信号来避免拥塞。传统的货代也尝试增加许多独立流量的吞吐量和公平性。相反，我们的主要目标在传感器网络，重要的是最大限度地提高能源效率和端到端的传输率，而不是高吞吐量和公平性。丢弃消息以保持队列流，浪费了部分传递这些消息的资源。货代的跳转托管在链路层捎带确认确认信息实现跳，说明是否已收到的包增加一点。而代理必须处理接收到的数据包在链路层确认可以发送，增加处理的延迟相比，IEEE802.15.4通信相对长的时间尺度上是可以忽略的。此外，我们修改了链路层的确认包括寻址信息，使他们不太严格的定时要求的依赖。保证不可预见的错误不会阻止数据包传输成功，货代也从队列中取出消息后分组重传次数超过阈值。传统的方法，严格坚持分层不包括链接确认上层信息。具体而言，基本的链接确认只显示传输失败，但没有提供的信息是上层能够接受或处理数据包。内存约束常见的传感器网络限制转发队列的大小，增加队列溢出的可能性。虽然我们可以禁用链路层确认当队列已满，发送方无法区分在接收机传输故障或拥塞之间。后来，我们讨论了如何包括这样的上层信息也可用于拥塞控制。图7.2：逐跳恢复。跳的逐跳恢复旨在提高能源效率，提高终端到终端的成功率。（1）货代跳重传使用保管传递的方法来降低丢包实现跳。（2）通过对每个转发的下一跳转发查询，允许路由器更新转发表转发，利用接收机的多样性。重新路由的支持在每一个重传的转发表中，转发代理执行下一跳查找。这样做允许网络层利用接收器的多样性，路由器可以在传输尝试失败时修改转发表条目。失败的传输减少链路层提供的链路质量估计，路由器可以通过更新转发表做出反应。我们提供了一个完整的讨论，在第8章中的路由器的行动。传统的方法通常执行一个单一的下一跳查找和提交数据到相应的界面，假设链路质量相对稳定。然而，无线通信，链路质量是高度可变的，具有较高的时间局部性[157]，传输故障表明，随后的传输到相同的目的地在不久的将来也有可能失败。环境效应和节点移动性可以立即改变链路质量。当这样的链路故障发生时，重新路由的可能性增加的可能性，货代可以继续向前发展，降低通信延迟，同时提高端到端的传输速率。重新路由可以复制数据包在转发，当重传来不同的下一跳的目的地是成功接收但失败的承认。复制抑制简单重传时，发生在同一个目标，通过缓存链路层收到的每个数据包的序列号。然而，重传不同的下一跳地可导致复制不被检测到链接。为了帮助抑制这样的重复，源节点标记每个生成的数据包以一个唯一的序列号。序列号可以包含在一个IPv6逐跳选项头或在适配头取决于层转发的实现。使用源地址和序列号，可以检测和抑制已在转发队列中已缓冲的重复消息。抑制只发生在入队消息-简单的缓存元数据最近转发的数据包可能会导致消息的下降是由于瞬态路由环路。重新路由可以复制数据包在转发，当重传来不同的下一跳的目的地是成功接收但失败的承认。复制抑制简单重传时，发生在同一个目标，通过缓存链路层收到的每个数据包的序列号。然而，重传不同的下一跳地可导致复制不被检测到链接。为了帮助抑制这样的重复，源节点标记每个生成的数据包以一个唯一的序列号。序列号可以包含在一个IPv6逐跳选项头或在适配头取决于层转发的实现。使用源地址和序列号，可以检测和抑制已在转发队列中已缓冲的重复消息。抑制只发生在入队消息-简单的缓存元数据最近转发的数据包可能会导致消息的下降是由于瞬态路由环路。7.2.3流货代也实现了流媒体，以减少发送消息的平均能量成本。当多个队列的数据包具有相同的下一跳的目的地，货运发送背靠背。这样做可以使链路层应用流提出了4章优化。货代通知链路层的传输通过媒体管理控制接口相同的目的地。链路层的流优化减少后续传输的传输开销，提高通信吞吐量，提高能源效率。流也提高了能源效率，利用时间特性的链路质量。虽然重新路由，以避免重复传输故障，流媒体的成功后立即成功的概率较高的成功传输。货代也实现了流媒体，以减少发送消息的平均能量成本。当多个队列的数据包具有相同的下一跳的目的地，货运发送背靠背。这样做可以使链路层应用流提出了4章优化。货代通知链路层的传输通过媒体管理控制接口相同的目的地。链路层的流优化减少后续传输的传输开销，提高通信吞吐量，提高能源效率。流也提高了能源效率，利用时间特性的链路质量。虽然重新路由，以避免重复传输故障，流媒体的成功后立即成功的概率较高的成功传输。增加流的机遇，货代故意延误时间或转发队列超过阈值。消息来源是延迟容忍使用IPv6逐跳选项报头或适配头，这取决于层的代理经营。而坚持延迟容忍消息导致更高的队列占用，链接的流优化允许代理快速传输多个数据包作为一个单元。图7.3：流。流数据包发往相同的下一跳节点通过减少传输开销和利用时间局部性的典型无线就自由地从相邻节点接收流式传输提高能源效率。这一突发传输方式使得网络充分利用流和提高能源效率。7.2.4拥塞控制传输失败直接转化为低效的资源利用，消耗能源和渠道能力。传输故障可能是由于一些原因，如拓扑结构的变化，由于节点的移动性，瞬态干扰，或简单的无线链路的有损性质。另一个重要原因是传输失败。拥塞的一种形式涉及高转发队列占用，导致传输失败，因为下一跳的目的地是无法接受的消息。另一种形式的拥塞是争无线介质，在竞争传输碰撞防止接收器的信号的解码。与其他原因的传输故障，转发策略可以显着影响的频率和幅度的拥堵。货运代理人以2种方式检测拥塞。首先，货代检测拥塞时，无法从下一跳的目的地接收确认。除了造成拥挤碰撞，未能收到确认可能仅仅是由于无线链路的性质。然而，在这两种情况下，货代应减少响应的传输速率。减少传输速率减少争用和碰撞的可能性。放缓的传输速率也尊重的时间特性的无线链路质量，在不久的将来传输故障表示一个更高的传输失败的概率。其次，货代通过监测队列占用检测拥塞，拥塞指示只有当队列已满。相比之下，传统的方法表示拥堵之前，排队其实是充分的尝试，以保持队列的大小，并避免队列溢出[55，94，145]。允许充分利用队列，货代可以流更多的数据包时，使流的效益最大化。因为逐跳复苏已经表明当转发队列已满，货代不需要额外的信号来指示拥塞。此外，货代的保管转移的方法有助于确保较少的数据包下降时，队列是充分。货代通过控制传输速率的下一跳地充血反应，使用添加剂增加，乘性减少（AIMD）控制器。因为能源效率是首要目标，AIMD控制器仍然相当保守的代价是降低吞吐量。特定的控制器参数取决于拥塞检测的种类。而一个完整的队列拥塞指示提供了确凿的证据，未能接收到链路层确认不。未能收到单确认可能是由于短期干扰。因此，利率下降小于失去的链路层确认相比，队列溢出。一个重要的细节是，流总是尽可能快地发送数据包。速率控制器只确定节点启动流的多少时间。由于逐跳恢复实现了一个托管转移的方法，逐跳拥塞控制将适当地适用于背压的所有的应用程序源的队列填充。一个问题往往与逐跳回来的压力是一个单一的拥塞点可以影响周围的节点，影响其他独立的流量，但不直接通过拥塞点。值得关注的是在传感器网络设置，减少因为他们有更多的结构化的通信节点通信到几个目的地而不是大量独立的流程。这与我们通常假设任意点的点对点通信的传统网络形成对比。7.2.5质量服务在许多情况下，货代的节能通信延迟的成本。监护权转移的方法不允许代理人将包直到有下一跳节点接受引起较大的队列占用率。流还导致延迟的数据包在接收额外的数据包的希望增加队列占用。保守的拥塞控制策略也减少了传输速率，以帮助提高能源效率。增加队列占用导致较大的队列服务时间。在最坏的情况下，满队列不允许转发接收新消息，并阻止消息向前发展。然而，还有，当通信延迟比能源效率更重要。一些应用程序可能需要低延迟的通信报告关键警报或事件。网络控制和管理交通经常受到终端到终端通信的时间尺度的限制，控制协议，提供信息的状态和健康的网络可能需要快速地警惕的流量来源，关于交付错误。当增加的吞吐量要求，可靠的传输协议，如TCP效益低延迟的通信。在操作一个人的时间尺度时，使用交互界面的管理协议通常更有用。一个支持IP的要点是提供互操作性与现有的IP设备，为了保持与现有协议兼容，货代试图将所有数据报的低通信延迟（在能源效率的成本）除非他们明确标记为延迟容忍。没有被标记为延迟容忍，货代不延迟转发数据包，使得拥塞控制机制不保守，和入队的他们比任何延迟容忍的队列中的消息。总的来说，然而，我们预计许多应用程序标记的数据包延迟性，能更好地利用能源效率优化。满队列可以有最显着的通信延迟的影响，因为他们阻止信息向前发展。转发了满队列使用的影响。图7.4：减轻全队列。货代支持不同的优先级，高优先级的流量可以让货代驱逐消息队列满时。货运代理也支持不同的流量类别，为每个交通类提供单独的队列。这两种情况下，允许消息，即使在低优先级的流量或其他类正在经历拥塞时，以取得进展的进展。首先，节点可以单独的标签数据包优先级高。当代理接收到一个高优先级消息队列满，货代在没有标记为高优先级消息从队列。然而，高优先级的消息从未驱逐其他高优先级的消息。优先级标记是完全正交的延迟容忍的标记，前者只表明什么消息可以被驱逐，后者表明如果额外的努力请求转发。二机制，以减轻全队列的影响是队列保留。货运代理通过为每个类分配一个单独的队列来支持不同的流量类别。在单独的队列，货代可以继续接受一类消息，即使别人都拥挤而不需要其他信息在转发队列。在每一个交通类，货运代理还保留至少一个进入本地产生的流量，防止本地流量时，转发流量保持转发队列。相比优先级标记，队列保留代表了一种悲观的方法来减轻全队列的影响。不同的流量类别是有用的，在支持不同的通信模式。例如，一个交通类可用于出口的流量对边界路由器，而另一个交通类可用于入口流量远离边界路由器。单独的队列允许一个方向的通信继续，即使相反方向是拥挤的。这种能力可以是至关重要的，告诉他们的来源，以减少他们的交通率或传播的应用程序级报警。最后，另一个交通类可以用于连接本地流量，允许节点与相邻节点进行通信，即使在转发其他流量时，也可以进行通信。我们开发了一个这样的路由架构，使有效地利用这些交通类在第8章。限制流量的入口、出口和本地链路支持典型的传感器网络应用程序工作负载的需要，也制约了量的路由，路由器必须维护。虽然有限的内存限制所有流量类的队列大小，可以动态调整队列大小来支持流量特性的变化。例如，一个典型的传感器网络应用的工作量可能需要对边界路由器的数据流量源源不断，在分配一个大型队列疏散交通是最好的应用。然而，偶尔的固件升级可能需要代理暂时分配额外的队列空间入口流量。动态分配也可用于支持增加公平性。例如，保留本地产生的流量的条目的数量可以变化相对其他流量，以提供公平的吞吐量分配下拥塞。然而，我们在今后的工作中，我们将对动态分配的调整进行更全面的处理。2.外文原文AnExtendedInternetArchitectureforLow-PowerWirelessNetworks-DesignandImplementationChapter7NetworkLayer-ForwardingInthischapter,weaddressthesecondcomponentofourIPv6-basednetworklayer:forwarding.Wepresentthedesignofanenergy-efficientforwarderforSensornetworks.TheIPnetworklayermustprovidehighenough“best-effort”datagramdeliverytoalloweffectiveend-to-endcommunicationandreliabletransport.IPdoesnotspecifythemechanismsusedforforwarding,allowingustochooseonesnecessaryforSensornetworks.Ourforwarderdesignisprimarilyconcernedwithenergyefficientforwardingandutilizestechniquesdevelopedwithinthesensornetcommunity,includinghop-by-hopretransmissionsandcongestioncontrol,streaming,andQoS.TheforwarderalsosupportsefficientmulticastforwardingusingTrickle.7.1Energy-EfficientDatagramForwardingTheIParchitectureelegantlyseparatesforwardingfromrouting.Theforwarderisresponsibleforreceivingdatagramsfromaninterface,performingnexthoplookupsinaforwardingtable,andsubmittingthemessagefortransmissionontheappropriateinterface.Therouterisresponsibleformanagingentriesintheforwardingtable.Incontrasttomuchsensornetwork,whichtypicallyintegratesforwardingandroutingtogether,ourIPv6-basedarchitectureforSensornetworksmaintainstheseparation,asshowninFigure7.1.Figure7.1:SeparationofForwardingandRouting.IPseparatesforwardingfromrouting.Receiveddatagramsnotdestinedforthenodeareplacedinaforwardingqueue.Theforwarderprocessesmessagesintheforwardingqueuebyperformingaforwardingtablelookuptodeterminethenext-hopdestinationandsubmitsthedatagramtothelinklayerfortransmission.Therouterisonlyresponsibleformaintainingforwardingtableentries.Theforwardingtableservesasanarrowinterfacebetweentheforwarderandrouter.TheIPnetworklayermustprovidehighenoughbest-effortdatagramdeliverytoallowend-to-endmechanismstoachieveeffectivecommunicationandreliabletransport.ButIPdoesnottakeapositionontheuseofspecificmechanismsorthesoftwarearchitectureusedtoimplementthosemechanisms.Forwardingmechanismscanhaveasignificantinfluenceonoverallperformanceandiswellstudiedinbothwiredandwirelesscontexts.TherapidgrowthoftheInternet,significantadvancementsinlinktechnologies,andincreaseindatastreaminghaveledpasteffortstofocusonmaximizingoverallthroughputandfairnessformanyindependentflows.Naiveforwardingpoliciesthatdon’trespondtocongestionatthenext-hopdes-tinationcanleadtohigherqueueoccupanciesonaverageandmorefrequentqueueoverflows.Thehighercommunicationlatencyandlossratesdirectlytranslateintolowerthroughput,especiallywhencoupledwithend-to-endcongestioncontrolmechanismssuchasTCP.Mechanismsthatrandomlydropmessagestokeepaveragequeuesizessmall[55,69,193],providefeedbackdirectlytothesource[144],performhop-by-hopflow-controlmechanisms[114,125,130],andincreasethereliabilityandvisibilityoflossy,wirelesslinks[7]haveallbeenproposedprimarilytoincreasethroughputandfairness.UnliketraditionalIPnetworks,typicalsensornetapplicationshavevastlydifferenttrafficcharacteristicsandrequirements.TypicalsensornetapplicationworkloadshaveloweraggregatethroughputandchannelutilizationthanisoftenassumedintraditionalIPnetworks.Asaresult,anycongestionthatmayoccurinSensornetworksaremorelikelytobetemporaryoccurrences,ratherthanthecommoncase.Manysensornetapplications,forexample,reportonetofewdatagramswithperiodsontheorderofminutestohours.Somesensornetapplicationsmayrequireinfrequenttransferofbulkdata,butrarelyfrommultiplenodessimul-taneously.Inmanycases,sensornetapplicationsmaybetolerantofcommunicationdelay,butmayrequirelow-latencycommunicationforrarebuttime-sensitiveeventsoralarms.Ratherthanthroughputandfairness,wearemoreconcernedaboutachievinghighend-to-endsuccessrateswithhighenergy-efficiency.Tonosurprise,energy-efficiencyisametricnottypicallyconsideredfortraditionalIPnetworkswhereenergyisplentiful.However,effortswithinthesensornetcommunityhavealsonotaddressedenergy-efficientforwardingwell,evenwhennotconstrainedbytheIPframework.Whileexistingworkhasfocusedontransmissionefficiency,thismetriconlyaddressesthenumberofmessagetransmissionsratherthantheenergycostofbothtransmittingandreceiving.Withduty-cycledlinks,theenergycostoftransmittingcanvarybyanorderofmagnitudeormoredependingonwhatoptimizationsthelinklayercanapply.Forwardingmultiplemessagestothesamenext-hopdestinationconsecutivelyaremorelikelytotakeadvantageofschedulingandstreamingoptimizationswithinthelinklayer.Broadcasttransmissionsoftenhavehigherenergycostthanunicasttransmissions,becauseitrequiresallneighboringnodestowakeupusingafullwakeupsignalornetwork-widesynchronization.Snoopingontransmissionsfromneighboringnodessignificantlyincreasesreceivecostsandmaybeprohibitedbysomelinkprotocolsduetoper-neighborstaterequirements.ManyexistingeffortsinSensornetworksrelyonbothbroadcastandsnoopingprimitivestocommunicatehop-by-hopfeedback[45,81,96,146,178,185].ThedifferenttrafficcharacteristicsandrequirementsforSensornetworkscauseustorethinktheforwardingmechanismsusedtoachieveenergy-efficientdelivery.Inthischapter,wepresentforwardingmechanismsthathaveenergy-efficiencyasaprimarygoal.Energy-efficiencyalsoimplieshighsuccessratesindatagramdelivery,asanydroppedmessagesrepresentwastedresources.Energy-efficientunicastforwardingissupportedbythreemechanisms:(i)hop-by-hoprecovery,(ii)streaming,and(iii)congestioncontrol.Becausethesemechanismsoftentradeincreasedenergyefficiencyforincreasedlatency,theforwarderalsoappliessimpleQoSmechanismsthatallowupperlayers(i.e.,transport)toselecttheforwardingpolicy.EnergyefficientmulticastforwardingissupportedbytheTricklealgorithm.Allofthemechanismswediscussinthischapteraresimpleanddonotrequireanyper-flowstate.ThemechanismsusedtoimplementIPforwardingaremostlyindependentofIP.Ourarchitecturedefineslink-localscopeasthosenodesreachablewithinradiocommunicationrange,requiringroutingprotocolstooperateatthenetworklayer.However,forwardingcanoccuratthenetwork-layer(asdonewithtraditionalIPforwarding)oratthelink-layer(asdonewithMPLS).AsdiscussedinChapter3,thelinkandnetwork-layerforwardingapproacheshavetheirrespectivetradeoffs.Theforwardingmechanismswedevelopinthischapterarenotspecifictolayerthatforwardingoccurs.7.2UnicastForwarding7.2.1BackgroundTheIParchitecturetraditionallyplacesreliabledeliveryandflowcontrolinthetransportlayer,placingsuchfunctionalitysolelyattheendpoints.TheTransmissionControlProtocol(TCP)wasthesuchmechanismtobecomemainstreamandremainswidelyusedtoday[141].TCPprovidesareliabledatastreambyimplementingend-to-endretransmissions,whereendpointsretransmitdatathatisnotexplicitlyacknowledged.Furthermore,TCPinfersstateaboutthenetworkbyobservingcommunicationthroughput,delay,anddroppedmessagestoperformflowcontrol[85].TCPattemptstomaximizethroughputbyoperatingasclosetothecongestionpointaspossible.TCP’send-to-endpropertyelegantlykeepsfunctionalityattheendpointsandleavesthecorenetworksimple,butlackscompletevisibilityofthenetwork.TCPassumesthatcongestionisthecauseofpacketdrops,cannotdistinguishbetweenqueuingdelaysandcommunicationdelays,andcannotdeterminetheextentofthecongestion.Furthermore,communicationdelayslimithowquicklyTCPcanreacttochangingconditions.InterestinginteractionsfromTailDropforwarderscausednetwork-widesynchronizationwhenreactingtocongestion,reducingoverallthroughput.ThesechallengeslimitedthemaximumthroughputTCPcouldachieve,aswellasthefairnessbetweenflows.Extraassistancefromthenetworkitselfwasnecessarytoprovidegreatervisibilityintothenetworkandimproveoverallnetworkperformance.Oneclassofeffortsassistedend-to-endratecontrollersbyplac-ingcongestiondetectionandnotificationmechanismswithinthenetwork.Someprovidedearlynotificationbyrandomlydroppingpacketsbeforecongestionoccurs,implicitlynotifyingendpointsthatcongestionisnear[69,85,193].Othersprovideexplicitnotificationbypiggybackinginformationondatapackets[94,145]orsendingexplicitmessagesbacktothesource[144].Someeffortsdecouplethedetectionfromnotification[55].Anotherclassofeffortsinvolveshop-by-hopcontrol,placingratecontrollerswithinthenetworkinadditiontocongestiondetectionandnotification[114,125,130].Hop-by-hopmechanismsarecapableofdetecting,providingfeedback,andreactingtoconditionsdirectlywheretheyoccur.Asaresult,hop-by-hopmechanismsaremorecapableofreactingquicklyandappropriatelytolocalconditions.Hop-by-hopmechanismsnaturallyprovideback-pressureallthewaytothesource,butonlydoessoascongestioninthenetworkbuilds.Incontrast,end-to-endmechanismssufferfromlargercommunicationlatencies,lackofvisibilityofthecauseorlocationofcongestionwhenitoccurs,andtheinabilitytodistinguishbetweenqueuingdelayandpropagationdelay.Routingchanges,forexample,maycausesignificantchangesinthecommunicationpropertiesalongapath,andend-to-endmechanismsmayrequiresignificanttimetodetectandreacttothechange.Hop-by-hopmechanisms,however,couldimmediatelydetectandreacttotheroutechangewhereitoccurred.Inthewirelessspace,hop-by-hopmechanismsarewidelyusedtoforwardingmessages.Theadventofwirelesslinks,suchasWiFiandcellular,invalidatedTCP’sassumptionthatcongestionistheprimarycauseformessagedrops.Initialwide-spreaddeploymentofwirelesslinksweremostlyinfrastructure-based,whereonlythefirstandlasthopswerelikelytobewireless.Evenso,link-layerrecoveryandcross-layeroptimizationsthatexposethecauseofmessagedropstothetransportlayerhavebeenshowntosignificantlyimproveperformance[7].Hop-by-hopmechanismshavealsobeenshowntobebeneficialinmultihopwirelessnetworks.Highspatialandtemporalvariability,asharedwirelessmedium,andlimitedcommunicationresourcesarebestservedbyhop-by-hopmechanismsthatcanquicklyreacttolocalconditions[45,81,96,146,178,185].Inaddition,hop-by-hoprecoveryisusedtoincreaseend-to-endreliability[158,177].Wirelesslinksinherentlyhavehigherlossrates,andend-to-endlossratesincreasepolynomiallywiththenumberofradiohops.Relyingsolelyonend-to-endretransmissionwouldimplythatrecoverycostswouldalsoincreasepolynomiallywiththenumberofhops.Incontrast,thecostofhop-by-hoprecoveryonlyincreaseslinearlywiththenumberofhops.Interestingly,fewmechanismswereproposedtodirectlyaddressenergyefficiency.Someeffortsattempttoaddressenergyefficiencybyevaluatingtransmissionefficiency,notingtherelationshipbetweenwastedtransmissionsandwastedenergy.However,evenfewereffortssofarhasevaluatedtheirdesignonduty-cycledlinkprotocols.Duty-cycledlinkscangreatlyimpactprotocolsthatrelyonsnoopingorbroadcasttopropagatefeedbackinformation,bothofwhichcanbeexpensiveinduty-cycledoperation.Linktransmissioncostsalsodependonwhatoptimizationsthelinkcanapply.Forexample,submittingmessagesasabatchmayallowthelinklayertoamortizestartupcostsacrossmultipletransmissions.Inthefollowingsections,wepresentasetofforwardingmechanismsthatseektominimizeenergyconsumptionofforwardingdatagramsalongapath,includinghop-by-hoprecovery,streaming,andcongestioncontrol.Thesemechanismstypicallyreduceenergyconsumptionatthecostofcommunicationdelay,sowealsoaddresssimpleQualityofService(QoS)mechanismsthatallowupperlayerstospecifythepolicy.7.2.2Hop-by-HopRecoveryTheforwarderimplementshop-by-hoprecoverytoincreaseend-to-enddeliveryrateswhendeliveringdatagrams.Improvedend-to-enddeliveryratesincreasesoverallenergyefficiencyofdeliveringdatagrams.Messagesthatfailtoreachthedestinationrepresentwastedenergy,assomeenergyhasbeenspentinunsuccessfullydeliveringthedatagram.Improvedend-to-enddeliveryratesalsoreducesthefrequencyoftriggeringrecoverymechanismsusedwithend-to-endreliabletransport.Comparedtoend-to-endretransmissions,hop-by-hopretransmissionsonlyoccurwheretheyareneeded.Hop-by-hopretransmissionsonlyburdenthenodeandneighborhoodwheretransmissionfailuresoccur,adaptingquicklytolocalconditions.End-to-endretransmissions,however,burdenallnodesonthepathfromtheproblemareatothesource,increasingrecoverylatencyandoverallenergycosts.RetransmissionsToreducepacketdrops,theforwarderdefaultstoacustody-transferapproach,onlydequeuingmessagesafterthenext-hopdestinationacknowledgesreceptionbythefinaldestinationorplacementintheforwardingqueue.Thecustody-transferapproachattemptstoincreaseenergyefficiencybyreducingpacketdrops,butalsoinduceslargerqueueoccupanciesandcommunicationlatencies.Traditionalbest-effortforwardersoftendropmessagesinattempttokeepqueueoccupanciessmall,limitthescopeoftrafficbuild-upthatmayaffectothernearbyflows,andprovideimplicitcongestionsignalstoavoidcongestion.Traditionalforwardersalsoattempttoincreasethroughputandfairnessformanyindependentflows.Instead,ourprimarygoalinSensornetworks,however,istomaximizeenergyefficiencyandend-to-enddeliveryrates,ratherthanhighthroughputandfairness.Droppingmessagestokeepqueuesflowingwastestheresourcesalreadyconsumedinpartiallydeliveringthosemessages.Theforwarderimplementshop-by-hopcustody-transferbypiggybackingacknowledgmentinformationonlink-layeracknowledgments,addingasinglebittoindicatewhetherornotthepacketwassuccessfullyreceived.Whiletheforwardermustprocessthereceivedpacketbeforethelink-layeracknowledgmentcanbesent,theaddedprocessingdelayisnegligiblecomparedtotherelativelylongtime-scalesofIEEE802.15.4communication.Furthermore,we’vemodifiedthelink-layeracknowledgmentsinChapter4toincludeaddressinginformation,makingthemlessdependentonstricttimingrequirements.Toensurethatunforeseenerrorsdonotpreventsuccessfulpacketdelivery,theforwarderalsodequeuesmessagesafterthenumberofretransmissionsforapacketexceedsathreshold.Traditionalapproachesthatstrictlyadheretothelayeringdonotincludeupper-layerinformationinlinkacknowledgments.Specifically,basiclinkacknowledgmentsonlyindicatetransmissionfailures,butprovidenoinformationofwhetherupperlayerswereabletoacceptorprocessthepacket.MemoryconstraintscommontoSensornetworkslimitforwardingqueuesizes,increasingthelikelihoodofqueueoverflows.Whilewecoulddisablelink-layeracknowledgmentswhenqueuesarefull,thesendercannotdistinguishbetweentransmissionfailureorcongestionatthereceiver.Later,wediscusshowincludingsuchupper-layerinformationcanalsobeusedforcongestioncontrolaswell.Figure7.2:Hop-by-HopRecovery.Hop-by-hoprecoveryseekstoincreaseenergy-efficiencybyincreasingend-to-endsuccessrates.(1)Theforwarderimplementshop-by-hopretransmissionsusingacustody-transferapproachtoreducepacketdrops.(2)Byperforminganext-hoplookupforeachretransmission,theforwarderallowstheroutertoupdatetheforwardingtablebetweenretransmissionsandtakeadvantageofreceiverdiversity.Re-RoutingSupportTheforwarderperformsanext-hoplookupintheforwardingtableoneveryretransmission.Doingsoallowsthenetworklayertoutilizereceiverdiversity,wheretheroutercanmodifyforwardingtableentrieswhentransmissionattemptsfail.Failedtransmissionsreducethelinkqualityestimateprovidedbythelinklayer,andtheroutermayreactbyupdatingtheforwardingtable.Weprovideacompletediscussionoftherouter’sactionsinChapter8.Moretraditionalapproachesoftenperformasinglenext-hoplookupandsubmitthedatagramtotheappropriateinterface,assumingthatlinkqualitiesarerelativelystable.Withwirelesscommunication,however,linkqualitiesarehighlyvariableandhavehightemporallocality[157].Atransmissionfailureindicatesthatsubsequenttransmissiontothesamedestinationinthenearfuturearealsolikelytofail.Bothenvironmentaleffectsandnodemobilitycaninstantlychangethelinkquality.Whensuchlinkfailuresoccur,re-routingincreasesthelikelihoodthattheforwardercancontinuetomakeforwardprogress,loweringcommunicationlatencywhileimprovingend-to-enddeliveryrates.Re-routingcanduplicatedatagramswhileforwarding,whenretransmissionstodifferentnext-hopdestinationsaresuccessfullyreceivedbutunsuccessfullyacknowledged.Duplicatesuppressionissimplewhenretransmissionsoccurtothesamedestination,bycachinglink-layersequencenumbersreceivedwitheachpacket.However,retransmissionstodifferentnext-hopdestinationscanleadtoduplicatesthatarenotdetectedbythelink.Tohelpsuppresssuchduplicates,thesourcenodemarkseachgeneratedpacketwithauniquesequencenumber.Thesequencenumb