Files in this item



application/pdf06630679.pdf (179kB)
Main articlePDF


Title:Worst-case performance of a mobile sensor network under individual sensor failure
Author(s):Park, Hyongju; Hutchinson, Seth
Subject(s):worst-case performance
mobile sensor networks
sensor failure
dynamic programming
greedy algorithm
Lloyd algorithm
Abstract:In this paper, we consider the problem of worst-case performance by a mobile sensor network (MSN) when some of the nodes in the network fail. We formulate the problem as a game in which some subset of the nodes act in an adversarial manner, choosing their motion strategies to maximally degrade overall performance of the network as a whole. We restrict our attention in the present paper to a target detection problem in which the goal is to minimize the probability of missed detection. We use a partitioned cost function that is minimized when each sensor executes a motion strategy given by Lloyd's algorithm (i.e., each agent moves toward the centroid of its Voronoi partition at each time instant), and when the probability of missed detection for each functioning sensor increases with the distance between sensor and target for correctly functioning sensors; adversarial nodes in the network are unable to detect the target, and move to maximally increase the probability of missed detection by the properly functioning sensors. We pose the problem as a multi-stage decision process, and use forward dynamic programming over a finite horizon to numerically compute optimal strategies for the adversaries. We compare the resulting strategies to a greedy algorithm, providing both system trajectories and evolution of the probability of missed detection during execution.
Issue Date:2013-05-06
Citation Info:Hyongju Park; Hutchinson, S., "Worst-case performance of a mobile sensor network under individual sensor failure," Robotics and Automation (ICRA), 2013 IEEE International Conference on , vol., no., pp.895,900, 6-10 May 2013 doi: 10.1109/ICRA.2013.6630679 keywords: {computational geometry;decision making;dynamic programming;failure analysis;greedy algorithms;minimisation;object detection;probability;telecommunication network reliability;wireless sensor networks;Lloyd algorithm;MSN;Voronoi partition;finite horizon;forward dynamic programming;functioning sensor;greedy algorithm;individual sensor failure;missed detection probability minimization;mobile sensor network;motion strategies;motion strategy;multistage decision process;network performance degradation;optimal strategies;partitioned cost function;probability evolution;target detection problem;worst-case performance;Dynamic programming;Equations;Heuristic algorithms;Mobile communication;Mobile computing;Partitioning algorithms;Robot sensing systems}, URL:
Conference Paper / Presentation
Conference Proceeding (whole)
Date Available in IDEALS:2015-05-13

This item appears in the following Collection(s)

Item Statistics