A Note on the Complexity of Some Quality of Information Optimisation Problems in Sensor Networks

(1)

A Note on the Complexity of Some Quality of Information Optimisation Problems in Sensor Networks

Research Report 441 Ellen Munthe-Kaas 3rd October, 2014

ISBN 978-82-7368-406-6

ISSN 0806-3036

(2)

(3)

A Note on the Complexity of Some

Quality of Information Optimisation Problems in Sensor Networks

Ellen Munthe-Kaas

Abstract

We prove that a selection of quality of information optimisation problems related to event detection in sensor networks are NP-hard.

1 Introduction

In event detection systems, where the aim is to utilize sensors in a network to detect events of interest, there is a need to balance the sensors’ energy usage against the frequency of data transfer in order to prolong the lifetime of the sensors. This leads to a number of optimisation problems, all of which tend to be NP-hard. In this note we review most of the optimisation problems in [1], [2], [3], [4] and prove that the corresponding decision problems are NP-complete.

2 Cost and Quality of Information Functions

Consider an event detection system with a set of sensors S. The aim of the system is to use data from the sensors for detecting an event characterised by an expressionE. Each sensor i has a hop count hi ∈N (the number of communication links from the sensor to where the sensed data are collected and processed) and a sending rateri, where N is the set of natural numbers (positive integers).

A sensor’s energy usage is proportional to the number of transmitted data tuples. The cost of employing a subset of the sensors θ ⊆ S is therefore represented by γ�

i∈θhiri, whereγis a scaling constant. The sending rates can be changed dynamically, for instance to lower the cost. For each sensori,ri reflects a percentage of its maximum sending rate.

In practice the sensor might accomplish the requested sending rate by repeatedly sampling 1

(4)

and sendingr_i data tuples out of a100 possible, thus we assume thatr_i is a non-negative integer in the range[0..100]. Since γ does not aﬀect the computational complexity of any of the optimisation problems, we for simplicity assume that γ = 1 and consequently use the cost function

Cost_r_¯(θ) = �

i∈θh_ir_i (1)

where r¯are the sending rates. We write Cost(θ)when r¯is obvious from the context.

Each sensor contributes to the system’s information extraction. The quality of this information is influenced by the sensor’s sending rate; the more data tuples provided, the more accurate the information gained from the sensed values. The contribution to the quality of information from a sensor that is actively producing and sending data, is represented by a function q(α, β, r), where r > 0 is the sending rate and α > 0 and β > 0 are used for tuning the value ofq to each individual sensor. The actual shape ofqcan be chosen in a number of diﬀerent ways as long asq(α, β, r)is monotonically increasing in r and obeys 1/2≤q(α, β, r)≤1 (assuming reasonable values for α and β). The rationale behind q(α, β, r) ≥ 1/2 is related to Equation (4), which is introduced further down.

When ri = 0, i.e., sensor i does not provide any data, its contribution to the quality of information is 0. Let αi and βi be the values of α and β respectively for sensor i. We write qi forq(αi, βi, ri)when the value of ri is obvious from the context.

We consider the following two possible definitions of q, both of which are monotonically increasing in each of α, β and r (slight variations of these definitions appear in the papers [1], [2], [3], [4]):

q(α, β, r) = αb⁻^βr¹ (2)

q(α, β, r) = 1−_α¹b⁻^βr (3)

wherebis the base of the exponent (withb =eorb= 2as the most prominent candidates).

The quality of information function for a set of mutually independent sensors θ and an event expression E, QoI[E]r¯(θ), is defined recursively wrt. the structure ofE [3]:

• E is an atomic event: For atomic events the quality of information function is a fusion of those for the individual sensors, and follows a Bayesian formulation.

QoI[E]¯r(θ) =

�

i∈θqi

�

i∈θqi+�

i∈θ(1−qi) (4)

�

i∈θqi

�

i∈θqi+�

i∈θ(1−qi) should be monotonically increasing in the size ofθ; the more sensors employed, the more accurately an atomic event can be detected. In order to ensure this, we require that qi ≥1/2.

• E is a conjunction of events E1 ∧ · · · ∧En, consecutive events E1 → · · · → En, or concurrent events E1 � · · · � En (assuming that for i �= j the atomic events occurring in Ei and Ej are independent):

QoI[E]¯r(θ) =�n

j=1QoI[Ej]r¯(θ) (5)

(5)

• E is a disjunction of eventsE₁∨ · · · ∨E_n(assuming that for i�=j the atomic events occurring in Ei and Ej are independent):

QoI[E]¯r(θ) = 1−�n

j=1(1−QoI[Ej]¯r(θ)) (6)

We write QoI[E](θ) when the sending rates ¯r are obvious from the context.

3 Optimisation Problems

The optimisation problems that we consider in this note, are the following:

Problem 1. MinCost – Find a subset of the sensors that minimises the cost while maintaining an acceptable quality of information:

Instance. A set of sensors S and an event expression E. For each sensor i, a sending rateri ∈N, a hop counthi ∈N, and constantsαi >0andβi >0such that1/2≤qi ≤1.

A minimum quality of information value Q >0.

Problem. Find a subset θ ⊆ S such that QoI[E](θ) ≥ Q and such that Cost(θ) is minimised.

Problem 2. MaxQoI – Find a subset of the sensors that maximises the quality of information while maintaining an acceptable cost:

Instance. A set of sensors S and an event expression E. For each sensor i, a sending rateri ∈N, a hop counthi ∈N, and constantsαi >0andβi >0such that1/2≤qi ≤1.

A maximum cost C ∈N.

Problem. Find a subset θ ⊆ S such that Cost(θ) ≤ C and such that QoI[E](θ) is maximised.

Problem 3. MaxQoIBalancing–Given a partition of the sensors, find for each group in the partition a subset such that the overall quality of information is maximised while maintaining an acceptable cost for each subset as well as an acceptable overall cost:

Instance. A set of sensors S and an event expression E. For each sensor i, a sending rateri ∈N, a hop counthi ∈N, and constantsαi >0andβi >0such that1/2≤qi ≤1. A partition S1, . . . , Sk of S. A maximum cost C ∈ N. For each Sj, a local maximum cost C_j ∈N.

Problem. Find subsets θj ⊆ Sj such that Cost(θj) ≤ Cj for all j, Cost(θ) ≤ C, and such that QoI[E](θ) is maximised, whereθ =�k

j=1θj.

3

(6)

Problem 4. MaxLifetime – Find an allocation of sensors into groups that maximises the number of groups while ensuring that each group provides an acceptable quality of information:

Instance. A set of sensors S and an event expression E. For each sensor i, a sending rate ri ∈N and constantsαi >0and βi >0 such that1/2≤qi ≤1. A minimum quality of information valueQ >0.

Problem. Find a subsetS^� ⊆Sand a partitionθ1, . . . , θkofS^�such thatQoI[E](θj)≥Q for all j and such that k is maximised.

Problem 5. MaxMinQoI–Find an allocation of sensors into a given number of groups such that the quality of information for the group with the lowest such value, is maximised:

Instance. A set of sensors S and an event expression E. For each sensor i, a sending rate ri ∈N and constants αi >0 and βi >0such that 1/2≤qi ≤1. A constantk ∈N. Problem. Find a subset S^� ⊆S and a partition θ1, . . . , θk of S^� such that

min_1≤j≤k{QoI[E](θ_j)} is maximised.

In MaxLifetime and MaxMinQoI, if a problem instance has more than one optimal solution, one might additionally consider optimising the subset S^�, for instance by choosing the solution with the smallest Cost(S^�). If such a further optimisation of S^� is not a concern, one may simplify the problems to finding a partitionθ1, . . . , θk of S rather than a partition of S^�. We have however chosen to keep the original problem formulations.

4 Decision Problems

In order to provide complexity results for the problems in Section 3, we first state the corresponding decision problems.

The decision versions of Problems 1 and 2 are identical:

Problem 6. MinCostDec and MaxQoIDec

Instance. A set of sensors S and an event expression E. For each sensor i, a sending rater_i ∈N, a hop counth_i ∈N and constantsα_i >0andβ_i >0such that1/2≤q_i ≤1. A minimum quality of information value Q >0 and a maximum cost C ∈N.

Question. Is there a subset θ⊆S such that QoI[E](θ)≥Qand Cost(θ)≤C?

If we for each sensor iabstract the cost and quality of information to constants ci and pi

respectively, and restrict our focus to atomic events, we get the following formulation of Problem 6, where pf(θ) =

�

i∈θpi

�

i∈θp_i+�

i∈θ(1−p_i) is the fusion of the pi’s:

(7)

Problem 7. Bayesian Profit

Instance. A set of items U. For each item i, a profitpi where 1/2≤pi ≤1, and a cost ci ∈N. A minimum profit P > 0and a maximum cost C ∈N.

Question. Is there a subset θ⊆U such that pf(θ)≥P and �

i∈θci ≤C?

We simplify the decision versions of Problems 3–5 similarly, noting that the decision versions of Problems 4 and 5 are identical:

Problem 8. MaxQoIBalancingDec

Instance. A set of items U. For each item i, a profit pi such that 1/2≤pi ≤1, and a cost ci ∈N. A partition U1, . . . , Uk of U. A minimum profitP >0 and a maximum cost C ∈N. For eachUj, a local maximum cost Cj ∈N.

Question. Are there subsets θj ⊆Uj such that pf(θ)≥ P, �

i∈θjci ≤ Cj for allj, and

�

i∈θc_i ≤C, where θ=�k j=1θ_j?

Problem 9. MaxLifetimeDec and MaxMinQoIDec

Instance. A set of items U. For each item i, a profit pi such that 1/2 ≤ pi ≤ 1.

A minimum profit P > 0. A constant k ∈N.

Question. Is there a subset V ⊆U and a partitionθ1, . . . , θk ofV such thatpf(θj)≥P for j = 1, . . . , k?

5 Complexity of the Problems

Our aim is to prove that all the decision problems in Section 4 are NP-complete. We base our proofs on the known NP-complete decision problems Knapsack [5] (often named 0-1 Knapsack) and Dual Bin Packing [6]:

Problem 10. Knapsack

Instance. A set of items U. For each item i, a profit pi ∈ N and a weight wi ∈ N. A minimum profit P ∈N and a maximum weight W ∈N.

Question. Is there a subset V ⊆U such that �

i∈V wi ≤W and �

i∈V pi ≥P?

Problem 11. Dual Bin Packing

Instance. A set of itemsU. For each itemi, a profitpi ∈N. A minimum profitP ∈N. A constant k ∈N.

Question. Is there a partition of U into k sets U1, . . . , Uk such that �

i∈Ujpi ≥ P for j = 1, . . . , k?

5

(8)

In the proofs below we use tilde (X˜) to emphasize that an entity X belongs to the transformed problem.

Lemma 1. Bayesian Profit is NP-complete.

Proof. Transformation from Knapsack: Let U˜ = U

˜

pi = 1−₁₊₂¹pi

˜ ci = wi

P˜ = ₁₊₂¹₋P

C˜ = W

Since pi ∈ N ⇒ 2^pⁱ ≥ 1, we have 0 ≤ ₁₊₂¹pi ≤ 1/2, and consequently 1/2 ≤ p˜i ≤ 1.

θ ⊆U is a witness for Knapsack if and only if it is a witness for the transformed problem:

�

i∈θwi =�

i∈θ˜ci, so �

i∈θwi ≤W iﬀ �

i∈θ˜ci ≤C.˜ Further, p˜i = ₁₊₂²^pi_pi, so ^1−˜_p_˜_i^pⁱ = 2⁻^pⁱ. Thus,

pf(θ) = ^� ^�ⁱ^∈^θ^p^˜ⁱ

i∈θp˜i+�

i∈θ(1−p˜i) = ¹

1+�

i∈θ 1−pi˜

pi˜

= ₁₊^� ¹

i∈θ2^−pi = ¹

1+2⁻^�i∈θ pi. Consequently,

�

i∈θpi ≥P ⇔2⁻^�ⁱ^∈^θ^pⁱ ≤2⁻^P ⇔pf(θ)≥ ₁₊₂¹−P = ˜P .

Lemma 2. MinCostDec and MaxQoIDec are NP-complete.

Proof. Transformation from Bayesian Profit: Let S˜ =U

E˜ = any atomic event

˜ α_i = 1

˜ ri =ci

h˜i = 1 Q˜ =P C˜ =C

In addition we choose the value of β˜i so that q˜i = pi (thus, 1/2 ≤ q˜i ≤ 1). The actual choice of β˜i depends on the definition of q(α, β, r):

β˜i = −1/(cilog_bpi) if q(α, β, r) = αb⁻^βr¹ , β˜_i = −log_b(1−p_i)/c_i if q(α, β, r) = 1− _α¹b⁻^βr.

Let θ ⊆ U. Then θ is a witness for Bayesian Profit if and only if it is a witness for the transformed problem: �

i∈θ˜hir˜i =�

i∈θci, so�

i∈θci ≤C iﬀ Cost(θ)≤C˜. Since q˜i =pi

and the event is atomic, QoI[ ˜E](θ) = �

i∈θpi/(�

i∈θpi +�

i∈θ(1−pi)) = pf(θ), and thus pf(θ)≥P iﬀ QoI[ ˜E](θ)≥Q.˜

(9)

Lemma 3. MaxQoIBalancingDec is NP-complete.

Proof. The transformation from Bayesian Profit is straightforward: Let U˜ = U

˜ pi = pi

˜ ci = ci

k˜ = 1 U˜1 = U P˜ = P C˜ = C C˜₁ = C

Then θ ⊆ U is a witness for Bayesian Profit iﬀ it is a witness for the transformed problem.

Lemma 4. MaxLifetimeDec and MaxMinQoIDec are NP-complete.

Proof. Transformation from Dual Bin Packing: Let U˜ = U

˜

pi = 1−₁₊₂¹pi

k˜ = k P˜ = ₁₊₂¹₋P

Since 2^pⁱ ≥ 1, 1/2 ≤ p˜_i ≤ 1. Since ¹⁻_p_˜_i^p^˜ⁱ = 2⁻^pⁱ, we get that for all θ ⊆ S, pf(θ) =

1

1+2⁻^�ⁱ∈θ pi. Consequently, for all θ⊆S, �

i∈θpi ≥P iﬀ pf(θ)≥ ₁₊₂¹−P = ˜P . Let θ₁, . . . , θ_k be a witness for the transformed problem (with V = �k

j=1θ_j). Then for allj,pf(θj)≥P˜, and consequently�

i∈θjpi ≥P for all j. Let θ0 =U\�k

j=1θj and let θ_i^� =

� θ1∪θ0 if i= 1, θi if i >1.

Then for all j > 1, �

i∈θ_j^� pi = �

i∈θjpi ≥ P. Further, �

i∈θ^�₁pi ≥ �

i∈θ1pi ≥ P, so θ₁^�, . . . , θ^�_k is a witness for Dual Bin Packing.

Let θ₁, . . . , θ_k be a witness for Dual Bin Packing. Then for all j, �

i∈θjp_i ≥ P, and consequently pf(θj)≥P˜ for all j, so θ1, . . . , θk is a witness for the transformed problem (with V =U =�k

j=1θj).

7

(10)

6 Conclusion

As the decision problems are provably NP-complete, the corresponding optimisation problems are NP-hard.

References

[1] V.H. Nguyen, E. Munthe-Kaas, and T. Plagemann. Energy-balanced sensor selection for social context detection. InPervasive Computing and Communications Workshops (PERCOM Workshops), 2012 IEEE International Conference on, pages 32–37, March 2012.

[2] V.H. Nguyen, E. Munthe-Kaas, and T. Plagemann. Quality and energy aware data acquisition for activity and locomotion recognition. InPervasive Computing and Com- munications Workshops (PERCOM Workshops), 2013 IEEE International Conference on, pages 493–498, March 2013.

[3] V.H. Nguyen, E. Munthe-Kaas, and T. Plagemann. Towards quality and energy aware complex event processing. In Wireless and Mobile Computing, Networking and Communications (WiMob), 2013 IEEE 9th International Conference on, pages 352–359, Oct 2013.

[4] V.H. Nguyen, E. Munthe-Kaas, and T. Plagemann. Energy saving for activity recognition through sensor selection, scheduling and sampling rate tuning. InWireless and Mobile Networking Conference (WMNC), 2014 7th IFIP, pages 1–8, May 2014.

[5] Richard M. Karp. Reducibility among combinatorial problems. In Raymond E. Miller and James W. Thatcher, editors, Complexity of Computer Computations, The IBM Research Symposia Series, pages 85–103. Plenum Press, New York, 1972.

[6] S.F. Assmann, D.S. Johnson, D.J. Kleitman, and J.Y.-T. Leung. On a dual version of the one-dimensional bin packing problem. Journal of Algorithms, 5(4):502 – 525, 1984.