Parametric Probabilistic Routing in Sensor Networks

Motivated by realistic sensor network scenarios that have mis-in-formed nodes and variable network topologies, we propose an approach to routing that combines the best features of limited-flooding and information-sensitive path-finding protocols into a reliable, low-power method that can make delivery guarantees independent of parameter values or information noise levels. We introduce Parametric Probabilistic Sensor Network Routing Protocols, a family of light-weight and robust multi-path routing protocols for sensor networks in which an intermediate sensor decides to forward a message with a probability that depends on various parameters, such as the distance of the sensor to the destination, the distance of the source sensor to the destination, or the number of hops a packet has already traveled. We propose two protocol variants of this family and compare the new methods to other probabilistic and deterministic protocols, namely constant-probability gossiping, uncontrolled flooding, random wandering, shortest path routing (and a variation), and a load-spreading shortest-path protocol inspired by (Servetto and Barrenechea, 2002). We consider sensor networks where a sensor’s knowledge of the local or global information is uncertain (parametrically noised) due to sensor mobility, and investigate the trade-off between robustness of the protocol as measured by quality of service (in particular, successful delivery rate and delivery lag) and use of resources (total network load). Our results for networks with randomly placed nodes and realistic urban networks with varying density show that the multi-path protocols are less sensitive to misinformation, and suggest that in the presence of noisy data, a limited flooding strategy will actually perform better and use fewer resources than an attempted single-path routing strategy, with the Parametric Probabilistic Sensor Network Routing Protocols outperforming other protocols. Our results also suggest that protocols using network information perform better than protocols that do not, even in the presence of strong noise. Christopher L. Barrett is leader of the Basic and Applied Simulation Science Group of the Computing and Computational Sciences Division at Los Alamos National Laboratory. His Group is a simulation science and technology (S&T) invention organization of 30 scientists devoted to providing large-scale, high performance methods for systems analysis and simulation-based assisted reasoning. His Group engages in fundamental mathematical, algorithmic, and complex systems analysis research. Current applied research is focused on interdependent simulation and analysis tools for complex, socio-technical systems like transportation, communications, public health and other critical infrastructure areas. His scientific experience is in simulation, scientific computation, algorithm theory and development, system science and control, engineering science, bio-systems analysis, decision science, cognitive human factors, testing and training. His applied science and engineering achievements include, for example, development of large-scale, high performance simulation systems (e.g., Transportation Analysis Simulation System, TRANSIMS) and development of a distributed computing approach for detailed simulation-based study of mobile, packet switched digital communications systems (Self Organizing Stochastic Rebroadcast Relay, SORSRER). He has a M.S. and Ph.D. in Bio-information Systems from California Institute of Technology. He is a decorated Navy veteran having served in both the submarine service and as a pilot. He has been awarded three Distinguished Service Awards from Los Alamos National Laboratory, one from the Alliance for Transportation Research, one from the Royal Institute of Technology, Stockholm, and one from Artificial Life and Robotics, Oita University, Japan. Stephan J. Eidenbenz is a technical staff member in the Basic and Applied Simulation Science group (CCS-5) at Los Alamos National Laboratory (LANL). He received an M.Sc. in Computer Science from the Swiss Federal Institute of Technology (ETH) in Zurich in 1997 and a Ph.D. in Computer Science from ETH in 2000; he also obtained a Bachelor’s degree in business administration from GSBA in Zurich in 1999. Stephan has worked for McKinsey & Co. in Switzerland, where he received training in business administration and microeconomics. He has held a postdoctoral position at ETH and he has been a postdoctoral fellow at LANL. Stephan’s more than 30 publications cover a wide range of subjects such as approximability and inapproximability properties of visibility problems in polygons and terrains, error modeling in sequencing problems for computation biology, and designing communication protocols robust against selfish behavior. His current research interests include selfish networking, algorithmic game theory, network modeling and simulation, network design, and network optimization. Lukas Kroc is a student of M.Sc. program in Computer Science at Charles University in Prague. In 2003, he was a Graduate Research Assistant at the Basic and Applied Simulation Science group (CCS-5) at Los Alamos National Laboratory. His research interests include simulation, wireless networking and artificial intelligence. Madhav V. Marathe is a Team Leader for Mathematics and Computer Science in the Basic and Applied Simulation Science group, Computer and Computational Sciences (CCS-5) at the Los Alamos National Laboratory. He obtained his B.Tech in 1989 in Computer Science and Engg. from IIT Madras, India and his Ph.D. in 1994 in Computer Science, from University at Albany. His team focuses on developing mathematical and computational tools for design and analysis of large scale simulations of socio-technical and critical infrastructure systems. His research interests are in modeling and simulations of large socio-technical systems, design and analysis of algorithms, computational complexity theory, theory of parallel, distributed and mobile computing and communication systems. He has published over 100 research articles in peer reviewed journals and conferences. He is an adjunct faculty in the Computer Science Department at the University of New Mexico. James P. Smith is a technical staff member in the Basic and Applied Simulation Science Group of the Computing and Computational Sciences Division at Los Alamos National Laboratory. His principal interest is in high performance computing applied to modeling, simulation and analysis of socio-technical systems. His current research applies to national infrastructure, especially telecommunication/computing, public health, and transportation. He has scientific experience in high performance computing and parallel processing applied to large-scale microscopic simulations, including original software design and debugging of very large, evolving systems of inter-operable computational systems, and efficient analysis and synthesis of massive data produced by multi-scale complex environments. Before attending graduate school he worked for a short time in nuclear theory, and had several publications in experimental biophysics from the Pennsylvania Muscle Institute and Bockus Research Institute. During graduate school he took a one year hiatus to start a company to work in analytic finance, and then spent time doing theoretical space physics at LANL. His graduate work eventually included theoretical and experimental fusion research, but concentrated on computational space plasma physics. He has publications in biophysics, analytic finance, education, space plasma physics and computer science, and is a co-inventor on the TRANSIMS patent. He has a Ph.D. in Theoretical Plasma Physics from the University of Texas at Austin.This revised version was published online in August 2005 with a corrected cover date.     

基于跨层设计的无线传感器网络新体系

无线传感器网络是资源受限的网络,网络中节点较简单且差异小,在许多应用背景中对实时性要求较高。而传统的分层网络体系开销较大且灵活性不高,跨层技术的产生可以弥补这些不足。论文分别从实时性、收集信息需要这两方面提出新的基于跨层技术的网络设计方案,以满足不同应用的需求。     

无线传感器网络中基于线性网络编码的节能路由算法

 该文基于网络编码思想,提出一种无需重传与确认的路由算法,这种算法以最小化单位比特有效数据的能耗为目标,给出最优化数学模型,并用遗传算法进行求解.所提出的免重传路由算法可以降低能耗,减轻节点之间的无线电干扰,节省了节点用于重传数据包所需配置的缓存.     

An Energy-Efficient Routing and Self-Organization Algorithm in Wireless Sensor Networks

1IntroductionAs the development of MEMStechnology,the microsensors whichintegrate manyfunctions such as sensing,signal processing and communication have been widelyused[1]. Wireless Sensor Network ( WSN) is construct-ed with hundreds to thousands of sensors and one ormore SINKs .Sensors can sense (monitor) many physi-cal signals such as sound,light ,electronics ,tempera-ture and humidity of the objects in a given region[2 ~3].Sensors transfer these signalsinto sensing data and sendsensin…     

Battery-Aware Routing for Streaming Data Transmissions in Wireless Sensor Networks

Recent technological advances have made it possible to support long lifetime and large volume streaming data transmissions in sensor networks. A major challenge is to maximize the lifetime of battery-powered sensors to support such transmissions. Battery, as the power provider of the sensors, therefore emerges as the key factor for achieving high performance in such applications. Recent study in battery technology reveals that the behavior of battery discharging is more complex than we used to think. Battery powered sensors might waste a huge amount of energy if we do not carefully schedule and budget their discharging. In this paper we study the effect of battery behavior on routing for streaming data transmissions in wireless sensor networks. We first give an on-line computable energy model to mathematically model battery discharge behavior. We show that the model can capture and describe battery behavior accurately at low computational complexity and thus is suitable for on-line battery capacity computation. Based on this battery model we then present a battery-aware routing (BAR) protocol to schedule the routing in wireless sensor networks. The routing protocol is sensitive to the battery status of routing nodes and avoids energy loss. We use the battery data from actual sensors to evaluate the performance of our protocol. The results show that the battery-aware protocol proposed in this paper performs well and can save a significant amount of energy compared to existing routing protocols for streaming data transmissions. Network lifetime is also prolonged with maximum data throughput. As far as we know, this is the first work considering battery-awareness with an accurate analytical on-line computable battery model in sensor network routing. We believe the battery model can be used to explore other energy efficient schemes for wireless networks as well.     

一种安全的无线传感器网络路由协议

Wireless sensor networks are increasingly deployed in security-critical areas, such as battle field. However, general sensor nodes are manufactured with inexpensive components, and they are short of security enhancement. Therefore, an adversary could capture and compromise sensor nodes easily, then launch some malicious attacks （including tampering or discarding useful data collected from source nodes）. In this paper, we propose a secure routing and aggregation protocol for sensor networks, which utilizes one-way hash chain and multi-path mechanism to achieve security of wireless sensor networks.     

无线多跳网络的自适应容量感知优化与控制技术

In wireless multimedia communications, it is extremely difficult to derive general end-to-end capacity results because of decentralized packet scheduling and the interference between communi-cating nodes. In this paper, we present a state-based channel capacity perception scheme to provide sta-tistical Quality-of-Service (QoS) guarantees under a medium or high traffic load for IEEE 802.11 wire-less multi-hop networks. The proposed scheme first perceives the state of the wireless link from the MAC retransmission information and extends this information to calculate the wireless channel capaci-ty, particularly under a saturated traffic load, on the basis of the interference among flows and the link state in the wireless multi-hop networks. Finally, the adaptive optimal control algorithm allocates a net-work resource and forwards the data packet by tak-ing into consideration the channel capacity deploy-ments in multi-terminal or multi-hop mesh net-works. Extensive computer simulations demonstrate that the proposed scheme can achieve better per-formance in terms of packet delivery ratio and net-work throughput compared to the existing capacity prediction schemes.     

基于分簇的水下传感器网络覆盖保持路由算法

在基于分簇架构的水下传感器网络（Underwater Sensor Networks ,UWSNs）中,当簇首以单跳或多跳的通信方式将数据传输至Sink节点时,由于簇首转发大量数据而负载过重,会过早耗尽能量而死亡,这将导致提前出现对监测区域的覆盖盲区。以改善覆盖效果为目标的LEACH-Coverage-U算法由于选举簇首的分簇方法具有随机性,也无法很好解决该问题。本文提出了一种水下传感器网络单跳覆盖保持路由算法（Single-hop Coverage-Preserving Routing Algo-rithm ,SCPR）,首先定义了覆盖冗余度（Coverage Redundancy ,CR）,然后根据该度量来选举簇首,最终以单跳方式直接将数据传送至Sink节点。为减少簇首能耗并获得更高的网络覆盖率,本文还提出一种多跳覆盖保持路由算法（Multi-hop Coverage-Preserving Routing Algorithm ,MCPR ）,簇首之间通信时优先考虑父节点中CR较高的簇首作为其下一跳路由,以多跳路由将数据传送至Sink节点。仿真结果表明,与LEACH-Coverage-U算法相比,SCPR、MCPR算法避免了其选举簇首时的随机性,提高了网络覆盖率,降低了网络能耗,延长了网络生命周期。     

高能量有效性的无线传感器网络数据收集和路由协议

 提出了一种分布式高效节能的无线传感器网络数据收集和路由协议HEEDC.此协议中传感器节点根据自身状态(综合考虑剩余能量、节点密度等因素计算得出的代价因子)自主的竞争簇首,同时为减少簇首节点的能量开销,簇首之间通过多跳方式将各个簇内收集到的数据发送给特定簇首节点,并由此簇首节点将整个网络收集的数据发送给汇聚节点.仿真实验表明,HEEDC协议比起现有的几种重要路由协议(如LEACH、PEGASIS等),能提供更加有效的能量使用效率,延长无线传感器网络的生存周期.因此,使用HEEDC协议的无线传感器网络具有更好的使用性,其监测结果具有更高的可靠性.     

无线Mesh网络跨层路由技术研究

无线Mesh网络(WMN:wireless mesh networks)作为一种新型的无线网络,成为近几年研究的热点。由于无线信道不稳定等特性,如何设计WMN的路由协议成为决定其性能的关键因素之一。近几年来的研究表明,通过跨层设计的方式综合其他层的重要参数来实现路由选择,能够很好地解决这一难题。介绍了几种先进的跨层路由设计方案,总结了现有的跨层路由协议的优缺点,并对如何设计并实现跨层路由协议进行了分析和总结。     

Routing Protocol with Optimal Location of Aggregation Point in Wireless Sensor Networks

1IntroductionAdvances in the miniaturization of MicroElectronicand Mechanical Structures(MEMS)haveledto batterypowered sensor nodes that have sensing,communica-tion,and processing capabilities[1~4].Sensor networkshave emerged as an indispensable and i mpo…     

WSN中基于分簇路由的多维度数据压缩算法研究

 本文在不减少基站获取传感信息量的前提下,以最大程度减少传输数据量为目的,提出一种在分簇路由协议支持下的时间、空间多维度的数据压缩算法.结合基于空间维度的数据压缩方式设计了一种改进的分簇路由.通过实例验证与仿真评测,该数据压缩算法以及配合该算法设计的路由协议可以显著的减少整个无线传感器网络中数据发送量,延长网络的生存周期.     

无线多媒体传感器网络路由协议研究

传统的无线传感器网络(Wireless Sensor Networks,WSNs)路由协议不能很好地适应多媒体数据流的传输.近来,提出了一些无线多媒体传感器网络(Wireless Multimedia Sensor Networks,WMSNs)路由协议.本文首先讲述了WMSNs服务质量保障路由问题及其面临的挑战,从五...     

传感器网络中一种分布式数据汇聚层次路由算法

由于传感器网络具有能量约束,低速率冗余数据和多对一传输等特点,传统的端到端集中式路由算法一般不适合传感器网络.提出了一种分布式数据汇聚层次路由算法,该算法利用能量核的思想汇聚数据和减少传输到目的节点的信息.模拟结果表明:比较传统的端到端集中式路由算法,该算法可以显著减少能量消耗;与一般的数据汇聚算法相比,该算法在保证能量消耗少的条件下,具有复杂度低和可扩展性好的特点.     

Joint Monitoring and Routing in Wireless Sensor Networks Using Robust Identifying Codes

Wireless Sensor Networks (WSNs) provide an important means of monitoring the physical world, but their limitations present challenges to fundamental network services such as routing. In this work we utilize an abstraction of WSNs based on the theory of identifying codes. This abstraction has been useful in recent literature for a number of important monitoring problems, such as localization and contamination detection. In our case, we use it to provide a joint infrastructure for efficient and robust monitoring and routing in WSNs. Specifically, we make use of efficient and distributed algorithm for generating robust identifying codes, an NP-hard problem, with a logarithmic performance guarantee based on a reduction to the set k-multicover problem. We also show how this same identifying-code infrastructure provides a natural labeling that can be used for near-optimal routing with very small routing tables. We provide experimental results for various topologies that illustrate the superior performance of our approximation algorithms over previous identifying code heuristics.     

WSANs中基于跳步数自适应的路由算法

无线传感反应网络是由大量传感节点和少量（可移动）资源丰富的反应节点构成.传感节点 负责收集外部环境信息,而反应节点对外部环境实施相应的操作.本文分析节点能量消耗模 型,求解出理想条件下单条路径上总能耗最小时的最优跳步数.在此基础上,提出了一种跳 步数自适应的路由算法HAR,用来实现数据收集的实时需求与能量消耗之间的平衡.仿真实验 表明：HAR算法在平衡能量消耗与时间延迟的性能上优于HBMECT算法,而且能较好地适用于 反应节点移动的情形.     

基于生成树的无线传感器网络分布式路由协议

在无线传感器网络中,节点具有有限的电池能量,为了延长网络的生存时间,提出了一种基于生成树的分布式路由协议STRP及其具有能量意识的改进版本STRP-PA.每个传感器节点根据相邻节点与基站的距离、剩余能量等信息寻找父节点,构造一棵以基站为根的近优最小生成树,节点采集的数据沿树传输,并在树杈节点进行聚合.仿真实验结果表明:STRP-PA协议能够节省网络能量,显著延长网络稳定工作的时间,性能明显好于LEACH协议.     

无线传感器网络LEACH路由协议改进

由于无线传感器网络(Wireless Sensor Networks,WSN)中节点能量有限,需要设计能量有效的协议,以延长网络的生存时间。在LEACH路由协议的基础上,综合考虑节点已经充当簇头的次数、剩余能量和地理位置参数来优化簇头的选择机制,提出了LEACH-W路由协议算法。实验结果表明,LEACH-W算法具有更长的网络生命周期。     

A Scalable Priority-Based Multi-Path Routing Protocol for Wireless Sensor Networks

In this paper, a scalable priority-based multi-path routing protocol (PRIMP) is proposed for wireless sensor networks to offer extended network lifetime and robust network fault tolerance, under the context of stringent energy constraint and vulnerability of sensors to dynamic environmental conditions. A novel interest dissemination strategy which invokes an on-demand virtual source technique is designed in PRIMP to minimize communication overheads and energy wastage. In routing, data traffic is distributed over multiple braided data paths simultaneously by a priority-based probabilistic approach at each hop to achieve the robustness against the unreliable transmission due to frequent node failures. Extensive simulations validate that PRIMP exhibits significantly better performance in energy conservation, load-balancing and data delivery than comparable schemes, while at the same time PRIMP achieves a nice scalability feature in terms of energy dissipation with various network sizes and network densities. Last but not least, PRIMP addresses the slow startup problem that is prevalent in data-centric routing schemes.     

无线传感器网络三维空间最佳覆盖路由协议

本文针对新兴无线传感器网络中的三维空间随机最佳覆盖NP难问题进行了研究.采用计算几何与图论着色方法建立了三维空间的随机最佳覆盖数学模型,给出了一种分布式启发算法,得到了完成最佳覆盖的低能量消耗路径.并在此基础上设计了一种可以实现无线传感器网络三维空间最佳覆盖的优化路由协议.最后进行了协议算法的性能评价以及最佳覆盖和网络生存时间的实验仿真,结果表明协议算法时间复杂度低,并具有可扩展性、有效性和鲁棒性.