如何应对传感器网络中可靠多跳路由的潜在挑战.docVIP

应对传感器网络中可靠多跳路由的挑战 Taming the Underlying Challenges of Reliable Multihop Routing in Sensor Networks （中文翻译） 作者：Alec Woo，Terence Tong，David Culler 摘要 无线通信的不稳定并且易损的特性是可靠自组织多跳网络的主要挑战。这些非理想的特性在传感网采用了原始低功率收发信机之后使问题更加严峻，并且产生了一些路由协议必须考虑的新问题。链路的连通性必须通过一个既有效又具有适应性的链路估计器才能被统计，路由决策必须充分利用这种连通性统计数据才可靠。链路状态和路由信息必须被保持在一个不论节点密度都具有恒定空间的邻接表中。我们研究和评估链路估计器，邻接表管理和可靠路由协议。我们主要关注多对一，周期性数据采集负载。我们通过对于大规模、大到50个点的高级仿真，深度的实验来缩小设计空间。最有效的解决方案就是利用一个简单的时间平均EWMA估计器，基于频率的表管理和基于开销的路由。 分类和主题描述 C．2.2[计算机通信网]：网络协议 通用术语 算法、性能、设计、实现 关键字 传感网、多跳路由、可靠性、链路估计、邻接管理 引入 传感网中的路由问题和传统ad-hoc无线网有这本质上的区别，因为传感网通常包含许多资源有限的节点，这些节点密集地通过低功率无线电连接，通过多跳上的聚合操作来实现一些具有特定应用的通信模型。在一些更传统的场景中，我们通常采用抽象出物理和链路层的802.11链路和一些独立的两两互联抽象出的应用。传感网中，我们有需求和机会来考虑更大的设计空间，因为外来因素潜在地和路由有着严重的交互。例如，一个简单的概念像最短路仅仅在和一些描述节点单跳通信连通性图的定义相关时能被构造出来。而在实际传感网中，节点通过观察通信事件和共享信息来发现连通性图。此外，连通性不是一个简单的二元关系，而是一个通信成功概率的描述。附近的一个节点可能在长时间内都在通信，但不总是，这取决于干扰、拥塞和其他丢包源。在节点相距远时，通信可能变得不可靠，但有可能存在远处，很多节点之间有很好的连通性。通常来说，很多链路是易损的，并且丢包速率在环境因素影响或者源于应用的高度相关表现的主张而变化不定。也就是说，传感网的路由算法必须将这些潜在因素考虑进去，并且利用在实际负载下的低等级估计机制对其进行评估。 这篇文章中，我们通过简单的低功率无线电和有限存储来探索连通性分析、邻接管理和密集传感网路由。为了定义应用的内容，我们分析一个简单的数据收集通信模型，在这个模型下，一个大的节点集多跳路由一些周期性的采样数据至一个唯一的sink节点。这可能是一个沿简单方向的定向发散流或者仅仅一个选择查询。为了定义硬件和物理结构因素，我们主要关注在大而无阻断的室内空间里大概像格子一样传播的TinyOS的大传感器场。 我们的结论分4个阶段来得出。第2部分提供一个此平台得到的实际链路特征。我们测量许多在一定距离范围内不同的节点对的丢包率。这个工作生成了一个模型，这个模型中链路质量的均值和标准差都是距离的函数。对于大规模节点集合来说，这种简单的模型定性地展示了在实际部署中观察到了的非常规连通性模式。 第3部分研究简单有效的估计器用来确定这些链路概率。一个节点可以通过被动地收集它收到的数据包或者主动地探测估计链路质量。过去对于不同的无线信道和传输层协议提出了很多种链路估计器，我们想找出一种既能快速响应链路变化，又稳定，还不需要大空间和强计算能力的估计器。为了找到设计空间的子集，我们采用了一种人工先验概率丢包发生器。这样缩小了实验得出的选择范围。我们发现一种窗平均的指数级加权平均更好。这个选择可用来做余下的模拟和实际估计。 第4部分探索了怎样去管理有限的、典型的小保存连通性和路由信息的邻接表。获得观测到的链路状态特征时，我们可以猜到，在大规模密集传感器场中，每个节点都会有很多优质链路和劣质链路和其他节点相连。为了构造一个链路估计，对于远端路由的统计历史必须存在于邻节点的邻接表中，并且保持足够长的时间来获取有意义的统计数据。连通性随环境和移动的改变而改变，所以当一个从非邻接表中节点发来的数据包到达时，我们怎样去决定是否分配一个接口给它，还有撤销哪个来腾出这一个？这个问题和在线频率决定有关，在线频率的目的就是利用和入口大小大致相同的缓冲区识别最流中重要的入口。我们发现一种具有适应低速采样的插入方法和保留最常出现节点撤销方法可以用来保持大部分的优秀节点都在邻接表中。 有了这些机制，第5部分建立了一个通过邻节点结构基于开销的分布式路由构成和调查各种形式的最短路和最小传输路由的框架。在单个数据收集流中，路由的结构简化到保持一个下一跳邻接表，或者父节点表，构成一个指向sink节点的路由树