Search NASA⌕ Search

DOE OSTI · 942206

Moving multiple sinks through wireless sensor networks for lifetime maximization.

Abstract

Unattended sensor networks typically watch for some phenomena such as volcanic events, forest fires, pollution, or movements in animal populations. Sensors report to a collection point periodically or when they observe reportable events. When sensors are too far from the collection point to communicate directly, other sensors relay messages for them. If the collection point location is static, sensor nodes that are closer to the collection point relay far more messages than those on the periphery. Assuming all sensor nodes have roughly the same capabilities, those with high relay burden experience battery failure much faster than the rest of the network. However, since their death disconnects the live nodes from the collection point, the whole network is then dead. We consider the problem of moving a set of collectors (sinks) through a wireless sensor network to balance the energy used for relaying messages, maximizing the lifetime of the network. We show how to compute an upper bound on the lifetime for any instance using linear and integer programming. We present a centralized heuristic that produces sink movement schedules that produce network lifetimes within 1.4% of the upper bound for realistic settings. We also present a distributed heuristic that produces lifetimes at most 25:3% below the upper bound. More specifically, we formulate a linear program (LP) that is a relaxation of the scheduling problem. The variables are naturally continuous, but the LP relaxes some constraints. The LP has an exponential number of constraints, but we can satisfy them all by enforcing only a polynomial number using a separation algorithm. This separation algorithm is a p-median facility location problem, which we can solve efficiently in practice for huge instances using integer programming technology. This LP selects a set of good sensor configurations. Given the solution to the LP, we can find a feasible schedule by selecting a subset of these configurations, ordering them via a traveling salesman heuristic, and computing feasible transitions using matching algorithms. This algorithm assumes sinks can get a schedule from a central server or a leader sink. If the network owner prefers the sinks make independent decisions, they can use our distributed heuristic. In this heuristic, sinks maintain estimates of the energy distribution in the network and move greedily (with some coordination) based on local search. This application uses the new SUCASA (Solver Utility for Customization with Automatic Symbol Access) facility within the PICO (Parallel Integer and Combinatorial Optimizer) integer programming solver system. SUCASA allows rapid development of customized math programming (search-based) solvers using a problem's natural multidimensional representation. In this case, SUCASA also significantly improves runtime compared to implementations in the ampl math programming language or in perl.

Explore related subjects

Keep this discovery

Explore connections, maps & timelines

BibTeXRIS

Petrioli, Chiara, Carosi, Alessio, Basagni, Stefano, Phillips, Cynthia Ann. 2008-01-01. Moving multiple sinks through wireless sensor networks for lifetime maximization.. https://searchnasa.com/record/osti%3A942206/moving-multiple-sinks-through-wireless-sensor-networks-for-lifetime-maximization

Citations retain the original authors and DOI and include this site’s record URL. If this discovery service contributed to your research, you can also cite Search NASA by Indiciae: BibTeX · RIS.

KEEP EXPLORING

Related reports

Water4Energy Step-1 Band-M Ready-to-Train Samples for TVA Weeks-to-Years Prediction, Version 0

AI-ready Band-M (monthly) labelled training pack for the Water4Energy Genesis Task-1 project on weeks-to-years prediction of Tennessee Valley temperature and precipitation. The deposit includes leakage-aware issue-time samples (samples_M_v0.nc; N=486), train-only scalers, issue-time split table, supporting monthly panels, and Python generation scripts to recreate the pack from the companion Tier-1 raw observation collection (https://doi.org/10.13139/ORNLNCCS/3398576). Each sample pairs a 12-month lookback of teleconnection indices and SST box anomalies with TVA-mean ERA5 anomaly targets (t2m, tp, msl) at leads 1–3 months.

54 ENVIRONMENTAL SCIENCES↗

Multi-Angle Snowflake Camera, particle analysis

The c1 level data product for the Mutli-Angle Snowflake Camera contains snowflake fall speeds and particle size, among other analysis for images associated with each hydrometeor.

54 ENVIRONMENTAL SCIENCES↗

Multi-Angle Snowflake Camera, time bins

The c1 level data product for the Mutli-Angle Snowflake Camera contains snowflake fall speeds and particle size, among other analysis for images associated with each hydrometeor.

54 ENVIRONMENTAL SCIENCES↗