检索结果-内蒙古大学图书馆

Fast Approximation Algorithm for Maximum Lifetime aggregation Trees in Wireless Sensor networks

INFORMS JOURNAL ON COMPUTING 2016年第3期28卷 417-431页

作者： Zhu, Xiaojun Chen, Guihai Tang, Shaojie Wu, Xiaobing Chen, Bing Nanjing Univ Aeronaut & Astronaut Coll Comp Sci & Technol Nanjing 211106 Jiangsu Peoples R China Nanjing Univ State Key Lab Novel Software Technol Nanjing 210023 Jiangsu Peoples R China Collaborat Innovat Ctr Novel Software Technol & I Nanjing 210023 Jiangsu Peoples R China Shanghai Jiao Tong Univ Shanghai Key Lab Scalable Comp & Syst Shanghai 200240 Peoples R China Univ Texas Dallas Naveen Jindal Sch Management Richardson TX 75080 USA Univ Canterbury Wireless Res Ctr Christchurch New Zealand

One ultimate goal of wireless sensor networks is to collect the sensed data from a set of sensors and transmit them to some sink node via a data gathering tree. In this work, we are interested in data aggregation, where the sink node wants to know the value for a certain function of all sensed data, such as minimum, maximum, average, and summation. Given a data aggregation tree, sensors receive messages from children periodically, merge them with its own packet, and send the new packet to its parent. The problem of finding an aggregation tree with the maximum lifetime has been proved to be NP-hard and can be generalized to finding a spanning tree with the minimum maximum vertex load, where the load of a vertex is a nondecreasing function of its degree in the tree. Although there is a rich body of research in those problems, they either fail to meet a theoretical bound or need high running time. In this paper, we develop a novel algorithm with provable performance bounds for the generalized problem. We show that the running time of our algorithm is in the order of O(mn alpha)(m, n)), where m is the number of edges, n is the number of sensors, and alpha is the inverse Ackerman function. Though our work is motivated by applications in sensor networks, the proposed algorithm is general enough to handle a wide range of degree-oriented spanning tree problems, including bounded degree spanning tree problem and minimum degree spanning tree problem. When applied to these problems, it incurs a lower computational cost in comparison to existing methods. Simulation results validate our theoretical analysis.

关键词： wireless sensor networks in-network processing and aggregation energy and resource management approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Distributed consensus and linear functional calculation in networks: An observability perspective

Distributed consensus and linear functional calculation in n...

引用

6th International Symposium on Information processing Sensor networks

作者： Sundaram, Shreyas Hadjicostis, Christoforos N. Univ Illinois Coordinated Sci Lab Urbana IL 61801 USA

ISBN: (纸本)9781595936387

We study the problem of performing sensor fusion and distributed consensus in networks, where the objective is to calculate some linear function of the initial sensor values at some or all of the sensors. We utilize a linear iteration where, at each time-step, each sensor updates its value to be a weighted average of its own previous value and those of its neighbors. We show that this approach can be viewed as a linear dynamical system, with dynamics that are given by the weight matrix for the linear iteration, and with outputs for each sensor that are captured by the subset of the state vector that, is measurable by that sensor. We then cast the fusion and consensus problems as that of observing a linear functional of the initial state vector using only local measurements (that are available at each sensor). When the topology of the network is time-invariant, we show that the weight matrix can be chosen so that each sensor can calculate the-desired function as a linear combination of its measurements over a finite number of time-steps.

关键词： distributed consensus distributed fusion networked control in-network processing and aggregation

来源：评论

学校读者我要写书评

暂无评论

Exact distributed Voronoi cell computation in sensor networks

Exact distributed Voronoi cell computation in sensor network...

引用

6th International Symposium on Information processing Sensor networks

作者： Bash, Boulat A. Desnoyers, Peter J. Univ Massachusetts Dept Comp Sci Amherst MA 01003 USA

ISBN: (纸本)9781595936387

Distributed computation of Voronoi cells in sensor networks, i.e. computing the locus of points in a sensor field closest to a given sensor, is a key building block that supports a number of applications in both the data and control planes. For example, knowledge of Voronoi cells facilitates efficient methods for computing the piece-wise approximation of a field, whereby each sensor acts as a representative for the set of points in its Voronoi cell;awareness of Voronoi boundaries and Voronoi neighbors is also useful in load balancing and energy conservation. The methods currently advocated for distributed Voronoi computation in sensor networks are heuristic approximations that can introduce significant inaccuracies that are difficult to rigorously quantify;we demonstrate that these methods may err by a factor of 5 or more in some circumstances. We present and prove an exact method which eliminates these inaccuracies, at the cost of increased messaging overhead, but without necessitating contact with the entire network. To our knowledge, this is the first distributed algorithm that computes accurate Voronoi cells without requiring all-to-all communication. We implement it as a TinyOS module and quantitatively analyze its performance.

关键词： sensor networks Voronoi diagrams in-network processing and aggregation

来源：评论

学校读者我要写书评

暂无评论

DICE: Monitoring Global Invariants with Wireless Sensor networks

引用

ACM TRANSACTIONS ON SENSOR networkS 2014年第4期10卷 54-54页

作者： Guna, Stefan Mottola, Luca Picco, Gian Pietro Univ Trent Dipartimento Ingn Sci Informaz I-38123 Povo TN Italy SICS Swedish ICT S-16440 Stockholm Sweden

Wireless sensor networks (WSNs) enable decentralized architectures to monitor the behavior of physical processes and to detect deviations from a specified "safe" behavior, for example, to check the operation of control loops. Such correct behavior is typically expressed by global invariants over the state of different sensors or actuators. Nevertheless, to leverage the computing capabilities of WSN nodes, the application intelligence needs to reside inside the network. The task of ensuring that the monitored processes behave safely thus becomes inherently distributed, and hence more complex. In this article we present DICE, a system enabling WSN-based distributed monitoring of global invariants. A DICE invariant is expressed by predicates defined over the state of multiple WSN nodes, such as the expected state of actuators based on given sensed environmental conditions. Our modular design allows two alternative protocols for detecting invariant violations: both perform in-network aggregation but with different degrees of decentralization, therefore supporting scenarios with different network and data dynamics. We characterize and compare the two protocols using large-scale simulations and a real-world testbed. Our results indicate that invariant violations are detected in a timely and energy-efficient manner. For instance, in a 225-node 15-hop network, invariant violations are detected in less than a second and with only a few packets sent by each node.

关键词： Algorithms Design System architectures programming models and languages network protocols in-network processing and aggregation

来源：评论

学校读者我要写书评

暂无评论

The Clustered aggregation (CAG) technique leveraging spatial and temporal correlations in wireless sensor networks

引用

ACM TRANSACTIONS ON SENSOR networkS 2007年第1期3卷 3–es页

作者： Yoon, Sunhee Shahabi, Cyrus Univ So Calif Los Angeles CA 90089 USA

Sensed data in Wireless Sensor networks (WSN) reflect the spatial and temporal correlations of physical attributes existing intrinsically in the environment. In this article, we present the Clustered aggregation (CAG) algorithm that forms clusters of nodes sensing similar values within a given threshold (spatial correlation), and these clusters remain unchanged as long as the sensor values stay within a threshold over time (temporal correlation). With CAG, only one sensor reading per cluster is transmitted whereas with Tiny aggregation (TAG) all the nodes in the network transmit the sensor readings. Thus, CAG provides energy efficient and approximate aggregation results with small and often negligible and bounded error. In this article we extend our initial work in CAG in five directions: First, we investigate the effectiveness of CAG that exploits the temporal as well as spatial correlations using both the measured and modeled data. Second, we design CAG for two modes of operation ( interactive and streaming) to enable CAG to be used in different environments and for different purposes. Interactive mode provides mechanisms for one-shot queries, whereas the streaming mode provides those for continuous queries. Third, we propose a fixed range clustering method, which makes the performance of our system independent of the magnitude of the sensor readings and the network topology. Fourth, using mica2 motes, we perform a large-scale measurement of real environmental data (temperature and light, both indoor and outdoor) and the wireless radio reliability, which were used for both analytical modeling and simulation experiments. Fifth, we model the spatially correlated data using the properties of our real world measurements. Our experimental results show that when we compute the average of sensor readings in the network using the CAG interactive mode with the user-provided error threshold of 20%, we can save 68.25% of transmissions over TAG with only 2.46% inaccuracy in t

关键词： algorithm design measurement performance in-network processing and aggregation clustering spatial and temporal correlations energy efficiency accuracy approximation modeling

来源：评论

学校读者我要写书评

暂无评论

aggregation methods for large-scale sensor networks

引用

ACM TRANSACTIONS ON SENSOR networkS 2008年第2期4卷 9-9页

作者： Chitnis, Laukik Dobra, Alin Ranka, Sanjay Univ Florida Gainesville FL 32611 USA

The ability to efficiently aggregate information - for example compute the average temperature - in large networks is crucial for the successful employment of sensor networks. This article addresses the problem of designing truly scalable protocols for computing aggregates in the presence of faults, protocols that can enable million node sensor networks to work efficiently. More precisely, we make four distinct contributions. First, we introduce a simple fault model and analyze the behavior of two existing protocols under the fault model: tree aggregation and gossip aggregation. Second, since the behavior of the two protocols depends on the size of the network and probability of failure, we introduce a hybrid approach that can leverage the strengths of the two protocols and minimize the weaknesses;the new protocol is analyzed under the same fault model. Third, we propose methodology for determining the optimal mix between the two basic protocols;the methodology consists in formulating an optimization problem, using models of the protocol behavior, and solving it. Fourth, we perform extensive experiments to evaluate the performance of the hybrid protocol and show that it usually performs better, sometimes orders of magnitude better, than both the tree and gossip aggregation.

关键词： algorithms design performance reliability in-network processing and aggregation fault tolerance sensor fusion and distributed inference modeling faults

来源：评论

学校读者我要写书评

暂无评论

Hierarchical Data aggregation Using Compressive Sensing (HDACS) in WSNs

引用

ACM TRANSACTIONS ON SENSOR networkS 2015年第3期11卷 45-45页

作者： Xu, Xi Ansari, Rashid Khokhar, Ashfaq Vasilakos, Athanasios V. Univ Illinois Dept Elect & Comp Engn Chicago IL 60607 USA IIT Dept Elect & Comp Engn Chicago IL 60616 USA Univ Western Macedonia Dept Comp & Telecommun Engn Kozani Greece

Energy efficiency is one of the key objectives in data gathering in wireless sensor networks (WSNs). Recent research on energy-efficient data gathering in WSNs has explored the use of Compressive Sensing (CS) to parsimoniously represent the data. However, the performance of CS-based data gathering methods has been limited since the approaches failed to take advantage of judicious network configurations and effective CS-based data aggregation procedures. In this article, a novel Hierarchical Data aggregation method using Compressive Sensing (HDACS) is presented, which combines a hierarchical network configuration with CS. Our key idea is to set multiple compression thresholds adaptively based on cluster sizes at different levels of the data aggregation tree to optimize the amount of data transmitted. The advantages of the proposed model in terms of the total amount of data transmitted and data compression ratio are analytically verified. Moreover, we formulate a new energy model by factoring in both processor and radio energy consumption into the cost, especially the computation cost incurred in relatively complex algorithms. We also show that communication cost remains dominant in data aggregation in the practical applications of large-scale networks. We use both the real-world data and synthetic datasets to test CS-based data aggregation schemes on the SIDnet-SWANS simulation platform. The simulation results demonstrate that the proposed HDACS model guarantees accurate signal recovery performance. It also provides substantial energy savings compared with existing methods.

关键词： Design Algorithms Measurement Performance Wireless sensor networks in-network processing and aggregation clustering energy efficiency compressive sensing modeling

来源：评论

学校读者我要写书评

暂无评论

Adaptive Correctness Monitoring for Wireless Sensor networks Using Hierarchical Distributed Run-Time Invariant Checking

引用

ACM TRANSACTIONS ON AUTONOMOUS AND ADAPTIVE SYSTEMS 2007年第3期2卷 8–es页

作者： Herbert, Douglas Sundaram, Vinaitheerthan Lu, Yung-Hsiang Bagchi, Saurabh Li, Zhiyuan Purdue Univ Dept Comp Sci Sch Elect & Comp Engn W Lafayette IN 47907 USA

This article presents a hierarchical approach for detecting faults in wireless sensor networks (WSNs) after they have been deployed. The developers of WSNs can specify "invariants" that must be satisfied by the WSNs. We present a framework, Hierarchical SEnsor network Debugging (H-SEND), for lightweight checking of invariants. H-SEND is able to detect a large class of faults in data-gathering WSNs, and leverages the existing message flow in the network by buffering and piggybacking messages. H-SEND checks as closely to the source of a fault as possible, pinpointing the fault quickly and efficiently in terms of additional network traffic. Therefore, H-SEND is suited to bandwidth or communication energy constrained networks. A specification expression is provided for specifying invariants so that a protocol developer can write behavioral level invariants. We hypothesize that data from sensor nodes does not change dramatically, but rather changes gradually over time. We extend our framework for the invariants that includes values determined at run-time in order to detect data trends. The value range can be based on information local to a single node or the surrounding nodes' values. Using our system, developers can write invariants to detect data trends without prior knowledge of correct values. Automatic value detection can be used to detect anomalies that cannot be detected in existing WSNs. To demonstrate the benefits of run-time range detection and fault checking, we construct a prototype WSN using CO2 and temperature sensors coupled to Mica2 motes. We show that our method can detect sudden changes of the environments with little overhead in communication, computation, and storage.

关键词： Reliability Verification Design Invariants correctness monitoring run-time tools fault tolerance and diagnostics in-network processing and aggregation network protocols programming models and languages data integrity

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：