Home // UBICOMM 2014, The Eighth International Conference on Mobile Ubiquitous Computing, Systems, Services and Technologies // View article

An SMT-based Accurate Algorithm for the K-Coverage Problem in Sensor Network

Authors:
Weiqiang Kong
Ming Li
Long Han
Akira Fukuda

Keywords: K-coverage; wireless sensor network; satisfiability modulo theory; accurate algorithm

Abstract:
In the context of wireless sensor network (WSN), the K-Coverage problem denotes that each point in a certain network area is covered by at least K sensors at the same time so as to guarantee the quality of services provided by the WSN. In this paper, we first propose a bottom-up modeling method for the K-coverage problem. Based on this method, we investigate a set of iteratively-applicable simplification techniques for simplifying the problem. Furthermore, we propose a satisfiability modulo theory (SMT) based algorithm for computing an accurate solution to the K-coverage problem. Experimental results have shown that our proposed simplification techniques and algorithm provide sufficiently satisfiable performance with respect to both computing speed and problem size.

Pages: 240 to 245

Copyright: Copyright (c) IARIA, 2014

Publication date: August 24, 2014

Published in: conference

ISSN: 2308-4278

ISBN: 978-1-61208-353-7

Location: Rome, Italy

Dates: from August 24, 2014 to August 28, 2014