Sage Journals: Discover world-class research

Abstract

Combining individual sensor decisions can be an effective way for the enhancement of the final decision on sensor fields for intruder detection. This paper proposes a novel methodology to unify the decisions from individual sensors on a sensor field through the (hidden Markov model) HMM and rules. The HMM especially provides a stochastic decision out of the individual sensor decisions on the sensor field; then it is filtered through rule inferences reflecting the knowledge of movement patterns on the level of the sensor field, such as spatial-temporal information and factual information on the movement of objects. This use of contextual knowledge remarkably improves the final decision for the detection. Also, this paper proposes the discretization method to express the state space of sensor field, and the performance evaluation is given by simulations.

1. Introduction

Good quality intruder detection is a critical issue in many applications such as surveillance in military zones and security and protection of mission-critical facilities. The human surveillance has many limitations in the quality of detection because of physical limitations of human beings such as the hardness of a consistent concentration on surveillance and the lack of reliability due to the capriciousness in human emotion. To overcome such limitations, the automated surveillance using sensors can be introduced because sensors do not get exhausted and keep alarmed stably without interruptions by changes like those in human emotion. A weakness in using sensors, however, is the lack of intelligence in detection which drops the detection quality. This implies that how intelligence equips sensor networks is critical for the automated surveillance and detection. On the other hand, the sensitivity of individual sensors of different types is varied depending on their deployed environment, and their detection performances are wide in their values—especially in case of outdoor sensor networks [1, 2]. This makes it a challenge in practice how to deploy sensors in a sensor network so that it may fully reflect their environment states in spite of their variegated changes. For instance, the true and false alarm rates in an intruder detection sensor network change over time according to the states of the given environment, that is, sunny, snowing, raining, and so forth. This fact commands the robustness of outdoor sensor networks from the changeable environment [3].

The unification of individual sensor decisions on a sensor field, a deployed sensor network, could be a viable option to construct a robust sensor network under the uncertain environment. The decision-making step after collecting the knowledge of detections out of individual sensors may provide a chance to determine the extent of utilization of these individual decisions towards the final decision in the sensor network. This unification of small individual decisions has several advantages. First, the final decision in the sensor network mediates the individual sensor decisions, rather than leaving them isolated, that it could provide one conclusive decision. This decision synthesizing out of individual sensor decisions may definitely help to avoid misjudgments or confusions caused by those individual sensor decisions solely, though this mediation is varied and not easy in complexity [4]. Second, during the process of unifying individual sensor decisions, it is possible to combine and exploit knowledge beyond those of the individual sensors in order to enhance the final decision.

This addition of knowledge should undoubtedly heighten the intelligence of the detection system, because it considers extensive knowledge systematically towards the final decision. In usual practical sensor networks, however, since decisions are made mainly based on the information collected from individual sensors that is mostly scalar sensing data [5, 6], most of holistic knowledge sensor networks can use tends to be ignored in general; this may lead to misunderstandings in their decision makings. For example, usual sensor networks care about signal data, such as frequency, amplitude, and intensity, rather than the whole contextual knowledge on sensor fields: the spatial information (e.g., the relative location with respect to the whole network where a sensor reacts), the temporal information (e.g., the sensing pattern over time), and the factual information (e.g., the sensor type that makes a sensor node alarmed). These kinds of information are indeed precious in that they could contribute to the final decision for intruder detection. Hence, this paper purports to propose a methodology of decision making using the contextual knowledge by unifying individual sensor decisions on a sensor field. Although the proposed methodology in this paper is designed for intruder detection on sensor fields, it could be extended to other purposes on sensor networks.

This study focuses on knowledge obtained from the three kinds of information mentioned above, called patterns on a sensor field. Table 1 shows the considerable patterns needed in the decision making of intruder detection.

Table 1

The considerable patterns for intruder detection.

The considerable patterns for intruder detection
(1) Proper Movement Patterns of an object on a sensor field.
(e.g., adjacency between alarmed sensors, proper track of moving object, etc.).
(2) Detected average speed of an object on a sensor field.
(3) Specific movement patterns of an object on a sensor field.
(4) The types of sensor reacting with an object on a sensor field.

Proper movement patterns of an object on a sensor field could be investigated by the HMM with the Viterbi algorithm as shown in Figure 1. In a given observation, an explicit tracking of an object is available under the consideration of a stochastic movement pattern. The movement pattern retrieved by the HMM could be used for the intruder detection on the sensor field. For example, when the expected type of the target object is “Person,” the contiguity of the locations of the chased movement becomes a measurement to decide whether the moving object is “Person” or not; that is, when the retrieved trace of the moving object is improper, it could be filtered out by the consideration of the proper trace of the expected type of the target object. This is very helpful for the identification of the intruder. The trace of the detected object is also used for estimating its average speed so that the comparison of the estimated speed with the reported standard average speed of the expected type of the object can give useful information for the intruder identification. Furthermore, the movement pattern of the object can be restricted by the state and shape of the sensor field in many ways. If the corresponding movement patterns are explicitly definable by reflecting the restrictions, that knowledge could be useful for the intruder detection. For example, if the sensor field contains mine fields or cliff edges in a military zone, the movement of the target type “Person” can be hindered by the obstacles, and hence the movement of the intruder is predictable. The estimation of the trace of the moving object thus could be beneficial from such a state of the sensor field to increase the performance of the detection and the identification of the intruder.

Figure 1

Proper movement patterns retrieved by HMM with Viterbi algorithm.

The knowledge about the types of sensors that respond to the types of the moving object is very useful for the intruder detection. Figure 2 shows the responding sensor types for the type of each object. According to the figure, it is recognized that the moving object cannot be an animal if a magnetic sensor reports detection because magnetic sensors do not react to animals. These pieces of knowledge are contained in inference rules, by which any detection in a sensor can be inferred to a conclusion about the type of an object.

Figure 2

The corresponding sensors for objects.

Different from sensor network systems in signal processing, the main purpose of this paper is to construct an enhanced intruder detection model as a decision model unifying individual sensor decisions in a sensor network by using the HMM and inference rules. This paper also proposes a dynamic discretization method to express the state space for a sensor field. The remainder of the paper is organized as follows. In the next section, this paper continues with the description of the state space representation for the sensor field to which the HMM is applied. The structure of the HMM for intruder detection comes next and suggests the unifying decision-making approach that this paper uses. This part mainly consists of two subparts with an example, the stochastic decision, and the rule based decision. The conclusion follows lastly.

2. The State Space Representation of a Sensor Field for HMM

In order to deal with extended observation space $O^{+}$ above, one of the options this paper adopts HMM [7–9] because of its strengths in finding out what the class sequence was. For the state space representation of a sensor field using HMM, let this paper introduce HMM with the formula of object function which is defined as

\begin{matrix} \arg \max_{x^{t_{1}}, \dots, x^{t_{n}}} P (x^{t_{1}}, \dots, x^{t_{n}} ∣ o^{t_{1} : t_{n}}), \end{matrix}

(1)

where

n \in ℕ

; denote the given observation of

t_{1}, \dots, t_{n}

o^{t_{1} : t_{n}}

and the state space of

t_{1}, \dots, t_{n}

x^{t_{1}}, \dots, x^{t_{n}}

. The underlying HMM model λ is the triple

λ (A, B, Π)

where

Π = {π} = P (X^{t_{1}} = x_{t_{1}})

A = a_{i j} = P (X^{k} = x_{j} ∣ X^{k - 1} = x_{i})

B = b_{i j} = P (O^{k} = o_{j} ∣ X^{k} = x_{i})

i, j, k \in ℕ, i, j, k > 0, and j > i

. Denote the initial state probability by Π, the transition probability by A, and the emission probability by B. With consideration of the formula (1) and

λ

, the state space representation should be affordable for the calculation of conditional probability (i.e., emission probability), involve state and observation parts, and be capable of describing time-series state and observation lists.

2.1. State Formulation on HMM for a Sensor Field

Consider the following state space in discrete form:

\begin{matrix} S = ⋃_{i = 1}^{n} R_{i}, \end{matrix}

(2)

where

R_{i} = {X_{j} ∣ \exists j \in ℕ, X_{j} \in R_{i}}

; denote by S all possible state space, by

R_{i}

the subset of

S

, and by

X_{j}

the element state of

R_{i}

. Note that the state space S points out all possible state space for a given sensor field which are categorized into the space in the detection of a sensor field and the space out of the detection of a sensor field; the categorized state space can be separated into several subcategories as described in Figure 3.

Figure 3

All the possible states on a sensor field.

Then, (2) is rewritten as follows:

\begin{matrix} S = R_{1} \cup R_{2} \cup R_{3} \cup R_{4} \cup R_{5} . \end{matrix}

(3)

Assumption 1.

Let this paper make assumption for a sensor field as follows: (1)

the sensor field consist of sensor nodes, a sensor nodes is the set of sensors;

(2)

there is no duplicated detection area of sensor node but a sensor does;

(3)

the sensors on sensor node are aligned to the same direction;

(4)

there is at least one omnisensor having maximum detection distance among sensors in a sensor node.

Based on the above assumption, this paper suggests discretization method for the state space of dynamic sensor field; obviously, the sensor field of MSN (mobile sensor network) cannot but be dynamic [10, 11]. Through Figure 3, with Assumption 1, we notice that the range of sensor detection is the criteria for the distinction of $R_{1} \cup R_{2}$ and $R_{3} \cup R_{4}$ . More specifically, $R_{1} and R_{2}$ are discriminated by the detection distance of sensor; $R_{3} and R_{4}$ are distinct by geometrical features derived from triangulation and rectangulation. The discretization process follows Figure 4. Basically, the state space of “the area in the range of sensor detection ( $R_{1} \cup R_{2}$ )” corresponds to the ability of sensor detection; the state space of “out of the range of sensor detection area ( $R_{3} \cup R_{4}$ )” depends on the deploy locations of sensors. The internal space of a sensor field not including sensor detection area ( $R_{3}$ ) especially, is obtained by Delaunay triangulation [12] as subtracting from triangle areas to $R_{1} \cup R_{2}$ ; the border of a sensor field ( $R_{4}$ ) is obtained by rectangulation from deployed location of sensors with subtracting from rectangle areas to $R_{1} \cup R_{2} \cup R_{3}$ ; the remaining area is $R_{5}$ .

Figure 4

The discretization process for a dynamic sensor field.

Based on Figures 3 and 4, this paper points out R as follows:

\begin{matrix} R_{1} = {X_{j} ∣ X_{j} \cap S_{i} \neq \emptyset, \exists i \neq j}, \\ R_{2} = {X_{j} ∣ X_{j} \cap S_{i} = \emptyset, \forall i \neq j}, \end{matrix}

(4)

where $X_{j} = S_{j} - ⋃_{i \in {l | S_{l} \subset S_{j}}} S_{i}$ and $S_{j}$ denotes the detection area of jth sensor.

As for the areas of $R_{1}$ and $R_{2}$ , these are determined by the properties of sensor detection such as the radius of detection and the angle of detection. This paper introduces an example of that in the following section (Section 2.1.1 is an example for state formulation). The possible state space for undetectable area is defined as follows:

delaunayTriangulation: $D T ({c_{i} ∣ c_{i} is the centroid of i th sensor node})$ → ${T_{1}, T_{2}, \dots, T_{u}}$ where, $u$ is the number of generated triangles.

convexSet $: C S = ⋃_{i = 1}^{u} T_{i}$ define the set of boundary edges of $C S$ as $B E$ .

boundaryPoint $: B P$ $= {p_{i} ∣ p_{i} \in B E and p_{i} is the centroid of ith sensor node}$

boundarySegment $: B S = {(p_{i}, p_{j}) ∣ p_{i}, p_{j} \in B P and \bar{p_{i} p_{j}} \subset B E}$ .

circumscribedQuadrilateral: $C Q (B S)$ → ${Q_{1}, Q_{2}, \dots, Q_{v}}$ , where, $v$ is the number of generated quadrilaterals.

\begin{array}{r} R_{3} = {X_{j} ∣ X_{j} = T_{j} - ⋃_{X_{i} \in (R_{1} \cup R_{2})} X_{i}}, \\ where j = 1, \dots, u, \\ R_{4} = {X_{j} ∣ X_{j} = Q_{j} - ⋃_{X_{i} \in (R_{1} \cup R_{2} \cup R_{3})} X_{i}}, \\ where j = 1, \dots, v, \\ R_{5} = {X_{0} ∣ X_{0} = {(⋃_{X_{i} \in (R_{1} \cup R_{2} \cup R_{3} \cup R_{4})} X_{i})}^{c}} . \end{array}

(5)

Denote the set of center coordinations of sensor nodes by

c_{i}

and the set of triangles derived from

c_{1}, \dots, c_{m}

T_{1}, \dots, T_{u}

. Note that m is the numbers of sensor nodes and u is the numbers of triangles which satisfy the objectives of Delanuary Triangulation for given

c_{1}, \dots, c_{m}

. There are three cases of undetectable areas of sensor field which are

R_{3}

R_{4}

, and

R_{5}

R_{3} \cup R_{4}

points out the undetectable areas of in sensor field, while

R_{5}

indicates the area of out of sensor field.

Note that the state space representation ensures that it presents all the possible state space. For the $R_{1}$ and $R_{2}$ , those are described precisely by the given parameters—which means that the range of detection area of the sensor is given explicitly. However, it has ambiguity to define “The area out of the range of sensor detection” ( $R_{3} \cup R_{4}$ ) because the shape of that area is flexible in concordance with the deployment information such as the number, the location, and the type of sensor. Hence, we need to make sure that $R_{3} \cup R_{4}$ covers all the areas of “The area out of the range of sensor detection” in any case. For this purpose, this paper defines those areas separately by triangle and rectangular. From the Delaunay triangulation, we guarantee that the obtained area “Internal area of a sensor field” is convex set and completely covers internal area of a sensor field; after that, by adding circumscribed quadrilateral ( $R_{4}$ ), this paper guarantees that the obtained area of $R_{1} \cup R_{2} \cup R_{3} \cup R_{4}$ addresses all the space of a sensor field consequently and obtained set is convex.

2.1.1. An Example for State Formulation

Let this paper explain our discretization method in the previous section with an example.

As seen in Figure 5, there are two types of sensor node. The first one consists of pressure, acoustic, and magnetic sensor, and the other consists of pressure, PIR, and UWB sensor. Consider $R_{1}$ and $R_{2}$ as the branch of “The area in the range of sensor detection.” Then detection distances of sensors in sensor node are only factors to distinct $R_{1}$ “Duplicated area of sensor detection” and $R_{2}$ (“Unduplicated area of sensor detection”) so that we define $R_{1}$ as the detectable area of sensors which have less detection distance than the one that has a maximum detection distance of a sensor node. In order to allocate $R_{1}$ and $R_{2}$ on sensor field, Let us define $S_{j}$ (the detection area of sensor j):

\begin{array}{l} A_{j} = {(c_{x}, c_{y}) ∣ {(c_{x} - m_{j})}^{2} + {(c_{y} - n_{j})}^{2} < r_{j}^{2}}, where \\ c_{x}, m_{j}, c_{y}, n_{j}, r_{j} \in ℝ, j \in ℕ, \\ B_{j} : \\ {\begin{array}{l} {(c_{x}, c_{y}) ∣ ArcTangent (\frac{c_{y} - n_{j}}{c_{x} - m_{j}}) \in {D e t e c t i o n A n g l e}_{j}}, \\ where c_{x} - m_{j} \geq 0 and c_{y} - n_{j} \geq 0 \\ {(c_{x}, c_{y}) ∣ ArcTangent (\frac{c_{x} - m_{j}}{c_{y} - n_{j}}) + 90^{°} \in {D e t e c t i o n A n g l e}_{j}}, \\ where c_{x} - m_{j} < 0 and c_{y} - n_{j} > 0 \\ {(c_{x}, c_{y}) ∣ ArcTangent (\frac{c_{y} - n_{j}}{c_{x} - m_{j}}) + 180^{°} \in {D e t e c t i o n A n g l e}_{j}}, \\ where c_{x} - m_{j} > 0 and c_{y} - n_{j} > 0 \\ {(c_{x}, c_{y}) ∣ ArcTangent (\frac{c_{x} - m_{j}}{c_{y} - n_{j}}) + 360^{°} \in {D e t e c t i o n A n g l e}_{j}}, \\ where c_{x} - m_{j} > 0 and c_{y} - n_{j} < 0 . \end{array} \end{array}

(6)

Then, we define

S_{j}

\begin{matrix} S_{j} = {S_{j} ∣ {S_{j} = A}_{j} \cap B_{j}} . \end{matrix}

(7)

Denote x-coordinate and y-coordinate on a sensor field by

c_{x}

and

c_{y}

m_{j}

n_{j}

, and

r_{j}

indicate the center coordinates and the detection distance of sensor

{s e n s o r}_{j}

, respectively, where

{s e n s o r}_{j}

is one of the sensors of sensor node and

r_{j} < r_{\max}

(

r_{\max}

is the maximum detection distance on sensor node). In addition

{D e t e c t i o n A n g l e}_{j}

points out that

{minAngle}_{j} \leq

the detection angle of

{s e n s o r}_{j} \leq

{maxAngle}_{j}

. Notice that there are two types of sensor node, sector type and circle type. Basically, (7) is derived from the sector type of a sensor node. However, the circle type of sensor node has

0^{\circ} \leq {D e t e c t i o n A n g l e}_{j} \leq 360^{\circ}

such that (7) is held in case of circle type of sensor node as well. As for the detection area of

R_{1}

and

R_{2}

, numbers of sensors,

n - 1

duplicated areas are there.

R_{1}

and

R_{2}

are described as

\begin{matrix} R_{1} = {X_{j} ∣ {X_{j} = S}_{j} - S_{i}}, \end{matrix}

(8)

where

r_{{s e n s o r}_{j}} < r_{{s e n s o r N o d e}_{k}}

r_{{s e n s o r}_{j}} > r_{{s e n s o r}_{i}}

and

{s e n s o r}_{j}

{s e n s o r}_{i} \in {s e n s o r N o d e}_{k}

\begin{matrix} R_{2} = {X_{j} ∣ {X_{j} = S}_{j} - S_{i}}, \end{matrix}

(9)

where

r_{{s e n s o r}_{j}} = r_{{s e n s o r N o d e}_{k}}

r_{{s e n s o r}_{j}} > r_{{s e n s o r}_{i}}

and

{s e n s o r}_{j}

{s e n s o r}_{i} \in {s e n s o r N o d e}_{k}

Figure 5

State space representation—an example a sensor field.

Denote the detection radius of a sensor and a sensor node by $r_{s e n s o r}$ and $r_{s e n s o r N o d e}$ repectively. Note that ${s e n s o r N o d e}_{k} = {{s e n s o r}_{1}, \dots, {s e n s o r}_{n}}$ . If ${s e n s o r}_{j}$ has the same detection radius of its sensor node, then the obtained $X_{j}$ binds to $R_{2}$ , otherwise $R_{1}$ .

As mentioned in Section 2.1, on account of the flexibility of undetectable area in a sensor field, this paper describes that area as triangles and circumscribed quadrilateral to ensure that our approach represents all the possible state space on a sensor field in any shape. The way to achieve the goal is fairly simple in principle. From the Delaunay triangulation, we obtain guaranteed convex set for the internal space of undetectable area on a sensor field; after that as using line segments of triangles for circumscribed quadrilateral, facilely we generate optimal state space, and the meaning of optimal state space here is that all the area is evenly separated as possible as a given parameter. The acquisition of the internal space of undetectable area is achieved by

\begin{array}{l} T_{j} = {(c_{x}, c_{y}) ∣ f_{1} (p_{1_{x}}^{{t r i}_{k}}, p_{1_{y}}^{{t r i}_{k}}) f_{1} (c_{x}, c_{y}) \geq 0, \\ f_{2} (p_{2_{x}}^{{t r i}_{k}}, p_{2_{y}}^{{t r i}_{k}}) f_{2} (c_{x}, c_{y}) \geq 0, \\ f_{3} (p_{3_{x}}^{{t r i}_{k}}, p_{3_{y}}^{{t r i}_{k}}) f_{3} (c_{x}, c_{y}) \geq 0, \\ p^{{t r i}_{k}} \in T r i a n g l e s A p e x e s}, where \\ p, c \in ℝ^{2}, k \in ℕ, \end{array}

(10)

\begin{array}{l} f_{1} (x, y) = (x - p_{2_{x}}^{{t r i}_{k}}) (p_{2_{y}}^{{t r i}_{k}} - p_{3_{y}}^{{t r i}_{k}}) \\ - (y - p_{2_{y}}^{{t r i}_{k}}) (p_{2_{x}}^{{t r i}_{k}} - p_{3_{x}}^{{t r i}_{k}}), \end{array}

(11)

\begin{array}{l} f_{2} (x, y) = (x - p_{3_{x}}^{{t r i}_{k}}) (p_{3_{y}}^{{t r i}_{k}} - p_{1_{y}}^{{t r i}_{k}}) \\ - (y - p_{3_{y}}^{{t r i}_{k}}) (p_{3_{x}}^{{t r i}_{k}} - p_{1_{x}}^{{t r i}_{k}}), \end{array}

(12)

\begin{array}{l} f_{3} (x, y) = (x - p_{1_{x}}^{{t r i}_{k}}) (p_{1_{y}}^{{t r i}_{k}} - p_{2_{y}}^{{t r i}_{k}}) \\ - (y - p_{1_{y}}^{{t r i}_{k}}) (p_{1_{x}}^{{t r i}_{k}} - p_{2_{x}}^{{t r i}_{k}}) . \end{array}

(13)

Denote the apexes of the triangle by

p^{{t r i}_{k}}

. The function

f (p_{x}, p_{y}) f (c_{x}, c_{y})

evaluates whether or not the points p and c are located in the same region (i.e.,

f (p_{x}, p_{y}) f (c_{x}, c_{y}) \geq 0

) for a given linear equation

f_{1}, f_{2}

, and

f_{3}

, respectively. Note that by (10)~(13)

T_{j}

indicates the interior area of the given triangle. Hence, the undetectable area inside a sensor field

R_{3}

is described as

\begin{array}{l} R_{3} = {X_{j} ∣ X_{j} = T_{j} - (X_{a} \cup X_{b})}, where \\ X_{a} \subseteq R_{1}, X_{b} \subseteq R_{2} . \end{array}

(14)

Related to the given parameters of (18), this paper adopts Delaunay triangulation to generate undetectable areas shaped in triangles. Being the apexes of triangle, the center coordinates of sensors are applied for the triangulation. The procedure of Delaunay triangulation is as follows: (1) Define the center coordinate of sensors

P = {p_{1}, \dots, p_{n}}

. (2) Define

p_{1}

as an uppermost y-point of elements that is the maximum y-value of

P

. (3) Generate two arbitrary points

p_{left}

and

p_{right}

for the triangle composed of

p_{1}, p_{left}

, and

p_{right}

to cover all coordinates in P. (4) Index the rest of elements in P from

p_{2}

p_{n}

. So the number of points used for Delaunay triangulation is

n + 2

. (5) Do

t r i a n g u l a t i o n (p_{i})

in order.

(5.1)

If the generated triangle (e.g., the triangle of

p_{1}, p_{left}

, and

p_{right}

) contains

p_{i}

, then make three triangles by drawing three lines

\bar{p_{i} p_{1}}, \bar{p_{i} p_{left}}, and \bar{p_{i} p_{right}}

(5.2)

p_{i}

exists on

\bar{p_{2} p_{3}}

of the triangle by

p_{1}, p_{2}, and p_{3}

, then make two triangles by drawing line

\bar{p_{i} p_{1}}

(5.3)

p_{i}

is located on the line

\bar{p_{2} p_{3}}

that two triangles share (e.g., the triangles of

p_{1}, p_{2}, p_{3}

and

p_{2}, p_{3}, p_{4}

), then make four triangles by drawing two lines

\bar{p_{i} p_{1}}

\bar{p_{i} p_{4}}

with the legal edge condition. (6) Figure 6(a) points out the illegal edge condition in which encountering angles

(a, b)

is bigger than 180°. With the illegal edge condition,

\bar{p_{1} p_{2}}

has to be removed to generate new edge

\bar{p_{3} p_{4}}

for the legal edge condition as shown in Figure 6(b). (7) Remove arbitrary generated points

p_{left}

and

p_{right}

Figure 6

Edge flip condition in Delaunay triangulation.

For the border of a sensor field, consider the following equation:

\begin{array}{l} Q_{j} = {(c_{x}, c_{y}) ∣ c_{x} \in R e t a n g u l e A r e a (d, e, p, q), \\ c_{y} \in R e t a n g u l e A r e a (d, e, p, q)}, where \\ d, e, p, q \in ℝ^{2}, j \in ℕ, \end{array}

(15)

\begin{array}{l} R_{4} = {X_{j} ∣ {X_{j} = Q}_{j} - (X_{a} \cup X_{b} \cup X_{c})}, where \\ X_{a} \subseteq R_{1}, X_{b} \subseteq R_{2}, X_{c} \subseteq R_{3} . \end{array}

(16)

Note that the equation to calculate the area of rectangular is similar as (10) in principle by using linear equation. Hence, we skip explaining the specific function

R e t a n g u l e A r e a (d, e, p, q)

. Denote by

d, e, p

, and

q

the coordinate of rectangular by

X_{a}, X_{b}

, and

X_{c}

the area involved in

R_{1}, R_{2}

, and

R_{3}

. Note that

\bar{p q}

is line segment of circumscribed quadrilateral and of triangle as well;

\bar{p q}

is acquired by triangulation which means that

p, q

are the center coordinates of sensor. Basically,

d and e

are easily derived from given p, q by Pythagorean theorem. From the reason of that p, q are the center coordinates of circle or sector, the derived rectangles are always circumscribed quadrilateral such that in any case pythagorean theorem is valid in the calculation to obtain

d

, e. Let us explain the calculation for

d, e

with the definition of which

r a d i u s (x)

is the function retrieving the radius of the sensor having the center coordinate x. In the 2-D coordination, Euclidian distance is

\begin{array}{l} d i s t a n c e (p, q) = \sqrt{\sum_{i = 1}^{2} {(p_{i} - q_{i})}^{2}}, where \\ p_{1} = p_{x}, p_{2} = p_{y} . \end{array}

(17)

From (17),

\bar{d q} is \sqrt{{d i s t a n c e (p, q)}^{2} + {r a d i u s (p)}^{2},}

hence and

\bar{d q}

is given; after that

\begin{matrix} \bar{d q} = \sqrt{{(d_{x} - q_{x})}^{2} + {(d_{y} - q_{y})}^{2},} \\ r a d i u s (p) = \sqrt{{(d_{x} - p_{x})}^{2} + {(d_{y} - p_{y})}^{2} .} \end{matrix}

(18)

We have two variables (

d_{x}, d_{y}

) and (18) such that d is calculated. Through the same procedures of (17) and (18), the circumscribed quadrilaterals based on line segments of triangles are generated. As a consequence, from (16) we generate “the border of a sensor field” state.

R_{5}

is simply defined as

X_{0} = {\emptyset}

because of “out of the area on a sensor field.”

2.1.2. The Representation of Observations of the Example

According to the sensing factors, different types of sensors determine its decision through signals that react with thresholds [13]. In this point, the decisions from these sensors are regarded as the decisions reflecting the features of each type of sensors. In our point of view, this is meaningful in terms of sensor network. Hence, this paper exploits the decisions of each sensor in a sensor field as the observation of HMM.

The observation in HMM can either be discrete or continuous [14, 15]. This paper applies discrete observation which represents “Detect” (Active) and “No respond.” The possible discrete observation space in our case is $2^{n}$ (n is the number of sensors in a sensor field). In order to deal with all possible observation space, this paper represents the observation as $“ {o b}_{1}, \dots, {o b}_{2^{n}} ”$ with the interpretation of n digits code. For example, if there are four sensors in a sensor field, we interpret the observation as “ $0 ∣ 1,0 ∣ 1,0 ∣ 1,0 ∣ 1$ ” (0: No respond, 1: Detect). In addition, for the calculation of conditional probability, the state representation of HMM is interpreted by n digit code in the same way as well. The emission probabilities are calculated by means of those representations, and the transition probabilities are obtained with first order Markov assumptions [9].

Figure 7 depicts an example of the representation of states and observations for Figure 5. There are 36 sensors on a sensor field. The whole possible numbers of observations are $2^{36} = 68719476136$ . We define the symbol ${o b}_{0}$ to indicate that no alarm is reported and ${o b}_{3}$ for what sensor 1 and sensor 3 make an alarm. The indexes of symbol for an observation are obtained by transforming the binary to the decimal notation. In case of the representation of states for a sensor field, we adopt the suggested discretization approach at Section 2.1. According to the deploy information of sensors and its detection ranges, the symbol indicating a state is assigned with the proper range of a region. And the proper range assigned for that is interpreted by the detection ranges of sensors. For example, $x_{1}$ could be depicted by the ranges of sensor 1, sensor 1, and sensor 3. The one advantage of describing states by the detectable ranges in the manner of sensor is that it enables the calculation of emission probability through the given observations and states.

Figure 7

The state space representation—an example.

3. The Structure of HMM for Intruder Detection

The structure of HMM could be represented by $λ (A, B, Π)$ . Denote initial probability by $Π$ , transition probability by $A$ , and emission probability by $B$ . Define that initial probability $Π = {π} = P (X^{t_{1}} = x_{t_{1}})$ , $A = a_{i j} = P (X^{k} = x_{j} ∣ X^{k - 1} = x_{i})$ and $B = b_{i j} = P (O^{k} = o_{j} ∣ X^{k} = x_{i})$ , where $i, j, k \in ℕ$ and $j > i$ . Note that an emission probability is calculated by a given observation with the performance of sensor which is $P_{d e t e c t i o n s u c c e s s} = P (a l a r m ∣ T a r g e t)$ , $P_{f a l s e d e t e c t i o n} = P (a l a r m ∣ N o n T a r g e t)$ , $P_{d e t e c t i o n f a i l u r e} = P (n o R e s p o n s e ∣ T a r g e t)$ , and $P_{n o R e s p o n s e} = P (n o R e s p o n s e ∣ N o n T a r g e t)$ . However, in order to obtain initial and transition probability of HMM, the actual movement of an object is required. Hence, this paper applies Gaussian mobility model [15] to gain proper movements of objects. Gaussian mobility model is a well-known model to generate reliable movement of object by manipulating the parameters. The following indicates movement equations of the model.

The equation for speed and direction calculation

\begin{matrix} s_{n} = α s_{n - 1} + (1 - α) \bar{s} + \sqrt{(1 - α^{2})} σ_{s}, \\ d_{n} = α d_{n - 1} + (1 - α) \bar{d} + \sqrt{(1 - α^{2})} σ_{d} . \end{matrix}

(19)

The equation for coordinate generation (2 Dimention)

\begin{matrix} x_{n} = x_{n - 1} + s_{n - 1} \cos d_{n - 1}, \\ y_{n} = y_{n - 1} + s_{n - 1} \sin d_{n - 1} . \end{matrix}

(20)

Denote the speed and direction at time n by $s_{n}$ and $d_{n}$ , respectively, the tuning parameter for adjustment of randomness where $0 \leq α \leq 1$ by α, the mean values of speed and direction of object by $\bar{s}$ and $\bar{d}$ , and the standard of deviation of speed and direction by $σ_{s}$ and $σ_{d}$ . Note that according to the tune of α with $\bar{s}$ , $\bar{d}$ , $σ_{s}$ , and $σ_{d}$ , the movement of a desired object is modeled.

The movement model of “Person,” “Animal (Deer),” and “Tracked Vehicle” has been approximated with given parameters as follows: Person: (4.32,0.3888,10.0,0.75) for $\bar{s}$ (km), $σ_{s}$ (km), $σ_{d}$ (°), and $α$ ; Animal: (29.00,2.6000,20.0,0.50); Tracked Vehicle: (40.0,3.6000,10.0,0.95). Through the generated movement by random sampling from the conducted Gaussian mobility model, the state matrix of HMM is calculated (Figure 8). In our case, we generated 200,000 samples for each movement (Person, Animal, and Tracked Vehicle) and then by calculating the frequencies of state changes, the state matrix of HMM is conducted with the following equations.

Figure 8

Initial and transition probability generation.

Inital probability:

\begin{matrix} Π_{i} = \frac{c o u n t (x_{0 i})}{c o u n t (\sum_{k = 1}^{n} x_{0 k})}, \end{matrix}

(21)

where

i, j, k \in ℕ

, and n is the total numbers of states.

Transition probability:

\begin{matrix} x_{i j} = \frac{c o u n t (x_{i j})}{c o u n t (\sum_{k = 1}^{n} x_{i k})} . \end{matrix}

(22)

Basically, the model λ requires transition matrix, initial probability, and emission matrix. The way of obtaining those factors of HMM is that for the case of transition matrix, random sampling is used as we mentioned above. Secondly, initial probability is obtained by the state change from $X_{0}$ to $X_{n}$ which means the entering probability to a sensor field. It is reasonable because we define $X_{0} \in R_{5}$ (out of the sensor field) at Section 2. Thirdly, emission matrix is dynamically calculated with the interpretation of Section 2.1.2. Assume that there are sensors having the same performance $P_{d e t e c t i o n s u c c e s s} = 0.8$ , $P_{d e t e c t i o n f a i l u r e} = 0.1$ , $P_{f a l s e d e t e c t i o n} = 0.1$ , and $P_{n o R e s p o n s e} = 0.5$ for an example of emission probability calculation. The calculation for that is depicted in Figure 9. The representation shown in Figure 9 is derived from the sensor field having 1 sensor node comprised of three sensors. From this, obtained emission probability for $P (x_{2} ∣ {o b}_{2})$ is “ $0.8 \times 0.1 \times 0.1 = 0.008$ .” In the details, $x_{2}$ points out the state detectable by sensor 3 and sensor 2; in the mean time ${o b}_{2}$ indicates the observation of alarmed by sensor 3 and sensor 1. Hence, the emission probability is calculated with the false alarm rate of sensor 1, the rate of detection failure of sensor 2, and the rate of detection success of sensor 3.

Figure 9

An example of calculation of emission probability on a sensor field.

4. Decision-Making Methodology Using HMM with Rules

As a first phase of our methodology for combining decisions, this paper provides the decision-making methodology based on stochastic model by adopting the suggested discretization method to HMM. The motivation of our methodology is quite naïve. Simply, there are distinct advantages between stochastic and cause-and-effect deterministic model. With an assumption of which all the events have probabilities to be happened, stochastic model is more explainable than cause-and-effect model for a given phenomenon. However, at some points, the cause-and-effect model could complement stochastic model for the enhanced decision. For example, the knowledge which has a difficulty in the representation of stochastic model can be easily extended to the rules for better decisions (experienced knowledge, statistical values, common sense, and others). Figure 10 indicates the architecture for our approach to combine stochastic (HMM) and rule-based decision within complexity of $O (N^{2} T)$ and $O (R A C T)$ , respectively. Denote evaluated costs by $O (T)$ , numbers of states of HMM by N, numbers of rules by $R$ , the number of assertions $A$ , and the approximate number of conditions per rule by $C$ .

Figure 10

The architecture to combine of stochastic (HMM) and rule-based decision.

As an approach for unifying decisions of sensors on a sensor field, this paper adopts HMM and rules. The first part of synthesizing decisions is achieved by HMM and then as a second part, this paper adopts rule-based decision. As shown in Figure 10, sensors in the sensor field have made sensor decisions by the input signals such as frequencies, amplitudes, decibels, and others. Then the decisions $(D e t e c t ∣ N o R e s p o n s)$ become the input parameters to HMM as the observation O of a moving object. In our methodology, the unified decision by HMM is achieved by means of judging the acceptability of model $λ_{1 : n} (i . e ., {HMM}_{1}, {HMM}_{2}, \dots, {HMM}_{n})$ by thresholds $θ_{1}, θ_{2}$ , and $θ_{3}$ and selecting one of the judged model with

\begin{matrix} \arg \max_{k = 1, \dots, n} ({\hat{δ}}_{k}), where n \in ℕ, {\hat{δ}}_{k} \in ℝ . \end{matrix}

(23)

Denote by k the number of HMM model and by

{\hat{δ}}_{k}

the probability of the most likely state sequence for given observations on kth model (e.g., Person, Animal, or Tracked Vehicle). Note that (23) selects one model whatever it is, according to the probability of the most likely state sequence. Then the identification of moving object is performed by the selected model. Hence, it is necessary to measure the acceptability of HMM model and filter the stochastic decision, the decision which has been made by HMM. The acceptability of HMM model is judged with thresholds

θ_{1}, θ_{2}

, and

θ_{3}

and then the stochastic decision is filtered by rules.

4.1. Stochastic Decision-Making Model with HMM on a Sensor Field

The procedure of stochastic decision is depicted by Figure 11. The procedure of stochastic decision making starts with calculating likelihood probability for the sequences of observations and obtaining maximum likelihood probability for the estimated movement patterns by Viterbi algorithm. Likelihood probability δ indicates how given observations are explainable by the established model (HMM), while $\hat{δ}$ points out how estimated patterns occur by given observations on the model. Both of them would be criteria for choosing a model for stochastic decision. However, this paper mainly focuses on the movement of an object. We adopt $\arg \max_{k = 1, \dots, n} ({\hat{δ}}_{k})$ as a measure of HMM decision.

Figure 11

The procedure of stochastic decision using HMM.

The δ in Figure 11 is calculated by the observations in time $t_{1 : n}$ as follows:

\begin{array}{l} P (O ∣ λ) = \sum_{X} P (O, X ∣ λ) \\ = \sum_{X} P (O ∣ X, λ) P (X ∣ λ) \\ = \sum_{X} π a_{x^{t_{1}} x^{t_{2}}} b_{x^{t_{2}}} (o_{t_{2}}) b_{x^{t_{3}}} (o_{t_{3}}) \\ \times b_{x^{t_{4}}} (o_{t_{4}}) \dots b_{x^{t_{n}}} (o_{t_{n}}) \\ \times a_{x^{t_{2}} x^{t_{3}}} a_{x^{t_{3}} x^{t_{4}}} \dots a_{x^{t_{n - 1}} x^{t_{n}}} \\ = \sum_{X} π a_{x^{t_{1}} x^{t_{2}}} \prod_{i = 2}^{n} b_{x^{t_{i}}} (o_{t_{i}}) a_{x^{t_{i - 1}} x^{t_{i}}}, \end{array}

(24)

where

X \in A l l P o s s i b l e S t a t e s S e q u e n c e s

in time

t_{1}, \dots, t_{n}

. Denote by O observations, by X states, and by π initial probability. Note that the function

b_{x^{t_{n}}} (o_{t_{n}})

indicates the emission probability of observation for the state and

a_{x^{t_{n - 1}} x^{t_{n}}}

points out transition probability. In our case, observations are the detection decisions of sensors on a sensor field and states indicate the area of a sensor field.

This paper applies Viterbi algorithm [16] to find the most likely underlying explanation of the sequence of observation $\hat{X}$ and the probability of estimated state sequence $\hat{δ}$ with the following object functions:

\begin{matrix} {\hat{x}}^{1, \dots, t} = \arg \max_{x^{1}, \dots, x^{t}} P (x^{1}, \dots, x^{t} ∣ o^{1 : t}) . \end{matrix}

(25)

Note that $δ_{t} (x_{j}) = \max_{x^{1}, \dots, x^{t}} P (x^{1, \dots, t - 1}, o^{1 : t}, x^{t} = x_{j}) = \max_{x^{t - 1}} δ_{t - 1} (x_{i}) a_{x_{i} x_{j}} b_{x_{j}} (o^{t})$ so that estimated movement pattern could be obtained from ${\hat{x}}^{t} = \max_{x^{t}} δ_{t} (x_{j})$ . And the probability of estimated sequence called maximum likelihood could be calculated with

\begin{matrix} {\hat{δ}}^{t} = P ({\hat{x}}^{1, \dots, t}, o^{1 : t} ∣ λ) . \end{matrix}

(26)

Basically, stochastic decision is established with

\begin{array}{l} \overset{´}{λ} = λ_{k} = \arg \max_{k = 1, \dots, n} ({\hat{δ}}_{k}^{t}), where \\ \overset{´}{λ} \in {HMM}_{n} . \end{array}

(27)

To ensure that $\overset{´}{λ}$ is a proper decision because the function of arg max anyway chooses one of the HMMs (Figure 12), this paper adopts three thresholds $θ_{1}, θ_{2}$ , and $θ_{3}$ . Those thresholds are the filtering condition of, $\hat{δ}$ , and $P (x_{0}^{1, \dots, t} ∣ o^{1 : t}, λ)$ . Each of probabilities of those indicates the possibilities of all possible state sequences (δ), estimated state sequence $(\hat{δ})$ , and Nothing State $(P (x_{0}^{1, \dots, t} ∣ o^{1 : t}, λ))$ .

Figure 12

The measurements of filtering required.

We define $θ_{1}$ by $δ$ , $θ_{2}$ by $\hat{δ}$ , and $θ_{3}$ by $P (x_{0}^{1, \dots, t} ∣ o^{1 : t}, λ)$ with the following equations:

\begin{matrix} θ_{1} = \min_{i = 1, \dots, n} δ_{i} = \min_{i = 1, \dots, n} (P_{i} (o^{1 : t} ∣ λ)), \\ θ_{2} = \min_{i = 1, \dots, n} {\hat{δ}}_{i} = \min_{i = 1, \dots, n} (P_{i} (x^{1 : t} ∣ o^{1 : t}, λ)), \\ θ_{3} = \max_{i = 1, \dots, n} (P_{i} (x_{0} ∣ o^{1 : t}, λ)) . \end{matrix}

(28)

$θ_{1}$ and $θ_{2}$ are configured by minimum $δ, and \hat{δ}$ is obtained by model simulation with the correct movement $(n = 100)$ ; $θ_{3}$ is configured by maximum value of $P (x_{0}^{1, \dots, t} ∣ o^{1 : t}, λ)$ from the simulation. Using threshold-based filtering, stochastic decision is finalized with

\begin{array}{l} \overset{´}{λ} = λ_{k} = \arg \max_{k = 1, \dots, n} ({\hat{δ}}_{k}^{t}) \\ = {\begin{cases} λ_{k}, & f_{1} (δ), f_{2} (\hat{δ}) and f_{3} (P (x_{0} ∣ o^{1 : t}, λ)) are 1, \\ Nothing, & f_{1} (δ), f_{2} (\hat{δ}) or f_{3} (P (x_{0} ∣ o^{1 : t}, λ)) are 0 . \end{cases} \end{array}

(29)

Note that

\begin{matrix} f_{1} (δ) = {\begin{cases} 0, & δ < θ_{1}, \\ 1, & δ \geq θ_{1}, \end{cases} \\ f_{2} (\hat{δ}) = {\begin{cases} 0, & \hat{δ} < θ_{2}, \\ 1, & \hat{δ} \geq θ_{2}, \end{cases} \\ f_{3} (P (x_{0} ∣ o^{1 : t}, λ)) = {\begin{cases} 1, & P (x_{0} ∣ o^{1 : t}, λ) \leq θ_{3}, \\ 0, & P (x_{0} ∣ o^{1 : t}, λ) > θ_{3} . \end{cases} \end{matrix}

(30)

4.2. Rule-Based Filtering to Enhance the Stochastic Decision

The simplest idea of rule-based filtering is that a tactic and implicit knowledge could be conducted as hypothesizes for the decision making. For example, the knowledge such as “the average speed of a moving object,” “stop pattern (specific pattern of an object),” and “corresponding types of sensors to an object” could be utilized as hypothesizes for intruder detection. This paper intends to represent those hypothesizes as rules for filtering HMM decision to enhance intruder detection. Hence, as shown in Figure 13, the final decision of our approach is defined as

Final Decision $\hat{λ}$ :

$\overset{´}{λ}$ has inTheRangeOfAverageSpeed ∧ $\overset{´}{λ}$ has regularPath ∧ $\overset{´}{λ}$ is the ProperType for Sensor Responding→intuderType is $\overset{´}{λ}$ .

Figure 13

Decision-making using HMM with rules.

The rule for final decision $\hat{λ}$ could be depicted by the rule tree (Figure 14). $\hat{λ}$ considers at first the specific patterns of given objects. In our case, we conduct the rules for “Person,” “Animal,” and “Tracked Vehicle”. Secondly, as filtering criteria, this paper investigates the estimated speed from retrieved pattern using Viterbi algorithm, through the comparison of an estimated speed of the object and a statistic average speed of the object. At last, the knowledge of corresponding types of sensors is employed for final decision $\hat{λ}$ .

Figure 14

The rule tree for final decision.

The rules for $\hat{λ}$ are conducted through SWRL (Semantic Web Rule Language), and the derived rules from Figure 14 are as follows:

# Final Decision Rules

EstimatedTrajectory $(? x)$ ∧ hasEstimatedSpeed $(? x, ? z) \land$ hasHMMEstimatedIntruderType $(? x, ? y) \land$ isRegularPath $(? x, ? g_{1}) \land$ isInAverageSpeed $(? z, ? g_{2}) \land$ ProperIntruderTypes $(? y) \land$ $s w r l b$ : notEqual $(? y, A n i m a l) \land ? g_{1} \land ? g_{2} \land ? g_{3}$ → intruderType $(? y)$

EstimatedTrajectory $(? x) \land$ hasEstimatedSpeed $(? x, ? z) \land$ hasHMMEstimatedIntruderType $(? x, ? y) \land$ isRegularPath $(? x, ? g_{1}) \land$ isInAverageSpeed $(? z, ? g_{2}) \land$ ProperIntruderTypes $(? y) \land$ $s w r l b$ : notEqual $(? y, A n i m a l) \land$ $s w r l b$ : booleanNot $(? g_{1}, ? g_{2}) \land$ $s w r l b$ : booleanNot $(? g_{2}, ? g_{3}) \land$ $s w r l b$ : booleanNot $(? g_{3}, ? g_{1})$ → intruderType $(N o t h i n g)$

EstimatedTrajectory $(? x) \land$ hasEstimatedSpeed $(? x, ? z) \land$ hasHMMEstimatedIntruderType $(? x, ? y) \land$ isRegularPath $(? x, ? g_{1}) \land$ isInAverageSpeed $(? z, ? g_{2}) \land$ ProperIntruderTypes $(? y) \land$ $s w r l b$ : notEqual $(? y, A n i m a l) \land$ $s w r l b$ : equal $(? g_{1}, F a l s e) \land$ $s w r l b :$ equal $(? g_{2}, F a l s e) \land$ $s w r l b$ : equal $(? g_{3}, F a l s e)$ →intruderType(Nothing)

EstimatedTrajectory $(? x) \land$ hasEstimatedSpeed $(? x, ? z) \land$ hasHMMEstimatedIntruderType $(? x, ? y) \land$ isInAverageSpeed $(? z, ? g_{1}) \land$ ProperIntruderTypes $(? y) \land$ $s w r l b$ : $notEqual (? y, A n i m a l) \land ? g_{1} \land ? g_{2}$ →intruderType $(? y)$ .

$\hat{λ}$ has three criteria which are $i s R e g u l a r P a t h$ , $i s I n A v e r a g e S p e e d$ , and $P r o p e r I n t r u d e r T y p e s$ . $i s R e g u l a r P a t h$ represents the specific pattern of an object. For example, assume that there are mine area or cliff edge on a sensor field; in this case we suppose that the allowed area to the a sensor field are restricted for “Person” which means if nonallowed areas are traced by HMM, then we can decide explicitly that the type of intruder is not “Person” as follows:

# The restrict condition of an intruder movement (=Person)

EstimatedTrajectory $(? x) \land$ EstimatedSeq $(? y) \land$ EstimatedSeq $(? y_{2}) \land$ hasHMMEstimatedIntruderType $(? x, “Person”) \land$ hasSequence $(? x, ? y) \land$ hasSequenceType $(? y, I n i t a l_P e n e t r a t i o n_P a t h w a y) \land$ hasHiddenState $(? y, X_{3}) \land$ hasSequence $(? x, ? y_{2}) \land$ hasSequenceType $(? y_{2}, P e n e t r a t i o n_P a t h w a y) \land$ $s w r l b$ : booleanNot $(h a s H i d d e n S t a t e (? y_{2}, X_{7}), T r u e)$ ∧ $s w r l b$ : booleanNot $(h a s H i d d e n S t a t e (? y_{2}, X_{8}), T r u e)$ ∧ $s w r l b$ : booleanNot $(h a s H i d d e n S t a t e (? y_{2}, X_{9}), T r u e)$ →isRegularPath $(? x, “ T r u e ”)$ .

The rule of $i s I n A v e r a g e S p e e d$ is referred to by the parameters of Gaussian mobility model for each objects. The purpose of adopting rules is filtering the misjudgment of a stochastic decision. In this point, we establish the deviation of the average speed to cover the wide range of speed, because of two reasons. The first one is that our approach applies discrete variable to represent the state space of HMM and that makes it hard to measure precise estimated speed. In the second one, basically we assume that stochastic decision has an admissible performance for detecting intruder. Hence, we intend to filter ridiculous estimated speed only by rules. In other word, we expect that the observations from earthquake, airplane, and any other unclassified objects are filtered during the sarcastic decision procedure. However, if it is not filtered by HMM, then rule-based filtering would be operated. The following rule is conducted for the case in which moving object is person with reflecting above argument:

EstimatedTrajectory $(? x) \land$ hasHMMEstimatedIntruderType $(? x, “Person”) \land$ hasEstimatedAverageSpeed $(? x, ? y) \land$ $s w r l b$ : lessThanOrEqual $(? y, 8.32) \land$ $s w r l b$ : greaterThanOrEqual $(? y, 0.32)$ → isInAverageSpeed $(? y, T r u e)$ .

Knowing the type of the corresponding sensor to object is beneficial to determine the type of intruder. For example, Table 2 points out the sensors being available for the detection in given objects. From Table 2, this paper conducts ProperIntruderTypes rules shown in Table 3.

Table 2

The corresponding sensors to an object.

	Magnetic	PIR	Acoustic	Pressure	UWB
Person	$1$	$1$	$1$	$1$	$1$
Animal	$0$	$1$	$1$	$1$	$1$
Vehicle	$1$	$0$	$1$	$1$	$1$
Airplane	$0$	$0$	$1$	$1$	$0$
Birds	$0$	$0$	$1$	$0$	$0$

Table 3

The rules for ProperIntruderType.

	Types of sensor responding (= alarmed sensor)										Moving objects
	Magnetic	∧	PIR	∧	Acoustic	∧	Pressure	∧	UWB	→ProperIntruderType =	{person,	animal,	Vehicle,	Airplane,	birds}
Rule 1	$0$		$0$		$0$		$0$		$0$	→	$1$	$1$	$1$	$1$	$1$
Rule 2	$0$		$0$		$0$		$0$		$1$	→	$0$	$0$	$0$	$1$	$1$
Rule 3	$0$		$0$		$0$		$1$		$0$	→	$0$	$0$	$0$	$0$	$1$
Rule 4	$0$		$0$		$0$		$1$		$1$	→	$0$	$0$	$0$	$1$	$1$
Rule 5	$0$		$0$		$1$		$0$		$0$	→	$0$	$0$	$0$	$0$	$0$
Rule 6	$0$		$0$		$1$		$0$		$1$	→	$0$	$0$	$0$	$1$	$1$
Rule 7	$0$		$0$		$1$		$1$		$0$	→	$0$	$0$	$0$	$0$	$1$
Rule 8	$0$		$0$		$1$		$1$		$1$	→	$0$	$0$	$0$	$1$	$1$
⋮	⋮		⋮		⋮		⋮		⋮	→	⋮	⋮	⋮	⋮	⋮
Rule 31	$1$		$1$		$1$		$1$		$0$	→	$0$	$1$	$1$	$1$	$1$
Rule 32	$1$		$1$		$1$		$1$		$1$	→	$0$	$1$	$1$	$1$	$1$

5. Experimental Result

5.1. The Sensor Field Applied for the Simulation

This paper produces simulated results through the sensor field comprised of different types of 36 sensors having 90 percent of detecting rate and 1 percent of false alarm rate. Figure 15 indicates the utilized sensor field for the simulation. We assumed that a sensor field is deployed along the road.

Figure 15

The sensor field simulated.

We conduct three kinds of HMM model which are “Person,” “Animal,” and “Tracked Vehicle” with parameters of Gaussian mobility model. Among those models, this paper defines the possible types of intruders (target objects) on the sensor field as “Person” and “Tracked Vehicle.” The other incoming objects are classified as nontarget objects of a sensor field (animal, airplane, and other clutters). Assume that the expected initial points of intruders are “ $X_{3}$ ,” “ $X_{42}$ ,” and “ $X_{6}$ ,” while non-target objects have the random initial points.

5.2. The Performance of Our Approach Using HMM with Rules for Intruder Detection

The performance of Table 4 is measured by three kinds of a sensor field. Each sensor field has $(80 %, 1 %)$ , $(90 %, 3 %)$ and $(99 %, 5 %)$ of detection rate and false alarm rate, respectively. Define the measurements for the performance test as follows:

Detection rate of sensor: $P ({S e n s o r}_{a l a r m} ∣ T a r g e t)$ , False alarm rate of sensor: $P ({S e n s o r}_{n o R e p o n d} ∣ \neg T a r g e t)$

Intruder detection rate of a sensor field $M_{d s} = P ({D e c i s i o n}_{i n t r u d e r} ∣ I n t r u d e r)$

False detection rate of a sensor field $M_{f d} = P ({D e c i s i o n}_{i n t r u d e r} ∣ \neg I n t r u d e r)$

Detection fail of a sensor field $M_{d f} = P ({D e c i s i o n}_{n o n I n t r u d e r} ∣ I n t r u d e r)$

No response of a sensor field $M_{n r} = P ({D e c i s i o n}_{n o n I n t r u d e r} ∣ \neg I n t r u d e r)$ .

Table 4

The performance of intruder detection using HMM with rules.

Moving objects	The performance of sensors on a sensor field			The performance of our approach (%)
Moving objects	Detection rate (%)	False alarm rate (%)		The performance of our approach (%)
Intruder
Person	$80$	$1$		$98$
	$90$	$3$		$97$
	$99$	$5$	Intruder detection rate	$95$
Tracked vehicle	$80$	$1$	Intruder detection rate	$100$
	$90$	$3$		$100$
	$99$	$5$		$100$

Nonintruder
Animal	$80$	$1$		$0$
	$90$	$3$		$0$
	$99$	$5$	False detection rate	$0$
Random noise	$80$	$1$	False detection rate	$0$
	$90$	$3$		$0$
	$99$	$5$		$0$

Note that $T a r g e t = {Person, Animal, Tracked Vehicle}$ , Intruder $= {Person, Tracked Vehicle}$ , and NonIntruder $= \neg$ Intruder (any other objects or clutters except “Person” and “Tracked Vehicle”). The listed results in Table 4 are obtained by 100 times simulation for each object. The movements of “Person,” “Animal,” and “Tracked Vehicle” are generated through Gaussian mobility model, and random noise is acquired by random observations. The average performance of our approach using HMM with rules represents 98.3% of intruder detection rate ( $M_{d s}$ ) and $0 %$ of false detection rate ( $M_{f d}$ ). From the results, in overall, this paper insists that our approach successfully makes a decision for intruder detection. The simulation for intruder detection is designed to investigate the sensitivity of a sensor field. Hence, each movement of objects has been generated to a different sensor field $(SF = {(80, 1), (90, 3), (99, 5)})$ . The obtained results point out that the performance of intruder detection is more sensitive to “False alarm rate” than “Detection rate” of sensors. In the same manner, we assume that “False detection rate” $M_{f d}$ is one of the key measures to evaluate the performance of a sensor field.

5.3. The Effectiveness Analysis of Our Approach

Our approach is mainly designed to focus on reducing $M_{f d}$ as using threshold-based filter and rule-based filtering. Table 5 demonstrates the effectiveness in reducing “False detection rate” of our approach. In Table 5, “Misclassification rate” is obtained from stochastic decision using HMM only, while “False detection rate” is calculated with our approach. The fed observations to each model as follows: (i)

Random noise: random observations

(ii)

Airplane: simultaneously, pressure and acoustic sensors only react

(iii)

Animal*: force magnetic sensor to react with animal movement; make every movements pass by an magnetic sensor at least once.

Table 5

The results of false detection simulation with a sensor field (detection rate: 0.9, false alarm rate: 0.01 for sensors).

	Person	Animal	Tracked vehicle	Misclassification rate (HMM decision)	False detection rate (HMM with rules decision)
Random noise	$0$	$0$	$0$	$0$	$0 %$
Airplane	$0$	$0$	$0$	$0$
Animal*	$91$	$9$	$0$	$1$

From the thresholds for stochastic decision, “Random Noise” and “Airplane” are filtered as “Nonintruder.” In case of “Animal*,” the sequences of observations are classified into 91% of Person and 9% of Animal. Hence, “Misclassification rate” is measured as 1 because by definition of “Animal*” the movement of that should not be classified as Person, Animal, and Tracked Vehicle.

The interesting point in Table 5 is that nine movement patterns of “Animal*” are classified as animal. Basically, magnetic sensors do not react with animal movements. As a result, in principal, the emission probability of HMM for “Animal” ( $P (X ∣ O)$ ) is always 0, when magnetic sensors are responded. That means that magnetic sensors make alarms, whenever the movement is not an animal. For this issues, there are two exceptional cases determining an animal for given observations of “Animal*.” The first is that the false alarm rate of the sensors could contribute to emission probability when calculating its probability. In this case, we have disabled the probability of detection and of false alarm as well in the establishment of HMM model for “Animal.” The second one is that the rate of detection failure for “Animal*” could make the observations which magnetic sensor does not react to. This situation causes the movement of “Animal*” to be classified into an animal (misclassification) and in general, practically it makes the measurements of $M_{f d}$ and $M_{d f}$ considerable when establishing detection model. From this point of view, keeping least rates of detection fail and false detection, not to mention detection rate, is a main objective for intruder detection model. Table 6 and Figure 16 reveal the outstanding performance of our approach.

Table 6

Decision-making performance.

The performance of sensors (detection rate, false detection)									HMM with rules
%	Measurements	${SDR}_{(1)}$	SDR₃	SDR₅	SDR₁₀	SDR₂₀	SDR₃₀	SDR₄₀	HMM with rules
$(80, 1)$	Detection	$100$	$100$	$100$	$98$	$13$	$2$	$0.5$	$99$
	Detection fail	$0$	$0$	$0$	$1.5$	$84$	$98$	$99.5$	$1$
	False detection	$100$	$65$	$52.67$	$33.33$	$26.00$	$3.33$	$0$	0
$(90, 3)$	Detection	$100$	$100$	$100$	$100$	$44$	$14.5$	$2.5$	$98.5$
	Detection fail	$0$	$0$	$0$	$0$	$56$	$85.5$	$97.5$	$1.5$
	False detection	$100$	$66$	$61.67$	$33.33$	$33.33$	$30$	$12$	0
$(99, 5)$	Detection	$100$	$100$	$100$	$100$	$68$	$45$	$33$	$97.5$
	Detection fail	$0$	$0$	$0$	$0$	$32$	$55$	$67$	$2.5$
	False detection	$100$	$71$	$64.33$	$33.33$	$33.33$	$33.33$	$33.33$	$0$

Figure 16

Decision-making performance.

We conduct $SDR$ (simple decision rule) to compare with our approach. ${SDR}_{n}$ makes a decision when the consecutive alarms are reported at least n times. In terms of detection rate, ${SDR}_{(1)}$ is the most effective model than any other models but it also has the worst performance on false detection rate. Basically, the numbers of consecutive alarms are in inverse proportion to detection fail and in direct proportion to detection and false detection. Hence, the optimal numbers of $SDR$ could be obtained by the analyzing sensitivity of measurements (detection, detection fail, and false detection). According to the sensitivity of those measurements in some specific problems, an optimal $SDR$ sometimes could be more effective than our approach. However, in general we insist that our approach is more distinguish than $SDR$ because of holding the admissible detection rate with low level of false detection and detection fail (Figure 16).

As the final simulation, we investigate the possibility finding out the initial point for decision-making process. We recognized that once enough observations are accumulated, then the movement decoding using Viterbi algorithm is properly operated. From this point, we assume that finding out the number of consecutive sensor alarms would be beneficial to the movement estimation of objects by delaying the initial activation time of HMM. As an example, we investigate person's movement with 100 times random samples. Figure 17 represents the tendency of conditional probability that intruder exists on a sensor field and consecutive sensor alarms at the time t. The probability that an intruder exists on a sensor field is calculated with $P_{i n t r u d e r e x i s t} = 1 - P (X_{0} ∣ O)$ and consecutive sensor alarms are measured by ${CSA}_{t}$ = $C^{t} / Max (C^{t_{1} : t_{n}})$ . Note that $C^{t}$ points out the consecutive sensor alarms having the same observation at the time t. In Figure 17, we recognize if ${CSA}_{t}$ has a first peak with predefined threshold 0.2 for person movement, and in the mean time $P_{i n t r u d e r e x i s t}$ closes to 1 which means some object is on a sensor field. From the result, we expect that the initial activation time of HMM could be determined as using ${CSA}_{t}$ . This brings to us valuable points. First, by determining the initial activation time for HMM, we could increase the performance of tracing movement. Second, with the policy of sensor activation using ${CSA}_{t}$ , we could extend the operating time of a sensor field by delaying activation of the decision process for unnecessary observations.

Figure 17

Consecutive sensor alarms.

6. Conclusion

In this paper, we consider a decision-making methodology for intruder detection by synthesizing the decisions on sensor network. This paper especially adopts the HMM to combine individual sensor decisions in stochastic manner and applies rules for the enhancement of the final decision. Firstly, using the HMM, this paper collects decisions of individual sensors on a sensor field and retrieves an estimated movement of a moving object. The obtained movement pattern is employed to identify the type of an object on the sensor field by taking advantage of spatial-temporal information. In this way, retrieved movement patterns on a sensor field contribute to the judgment of intruder detection beyond the simple use of signal values from individual sensors with some thresholds in their decisions. Secondly, this paper uses rules to enhance the stochastic decision obtained from the HMM. In principle, the HMM makes a decision by a given transition and emission probabilities under the assumption that all events have probabilities to occur. However, there are worth axioms and knowledge for a decision making on a sensor field that contradicts the assumption of probabilistic model (HMM). This paper adopts these knowledge and axioms as rules to enhance the decision of sensor field. As an example, this paper conducts several rules representing specific movement patterns of objects, the average speeds of the movements, and the sensor types which respond to specific objects. Since any kind of knowledge can be expressed by the rules, this proposed methodology could be easily extended for other purposes.

The contribution of this paper can be summarized as follows. First, this paper proposes the dynamic discretization method for the construction of the state space in a sensor field. Any shape of a sensor field is dynamically represented as a state space for the HMM through the proposed discretization method. Second, this paper provides a decision-making methodology for intruder detection on a sensor field by using HMM and rules, and its performance is evaluated with simulations.

Footnotes

Acknowledgment

This research was supported by the Basic Science Research Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Education, Science and Technology (2010-0024532).

References

Howard

Mataric

M. J.

Sukhatme

G. S.

Mobile sensor network deployment using potential fields: a distributed, scalable solution to the area coverage problem

Proceedings of the 6th International Symposium on Distributed Autonomous Robotics Systems (DARS '02)

2002

Clouqueur

Phipatanasuphorn

Ramanathan

Saluja

K. K.

Sensor deployment strategy for target detection

Proceedings of the 1st ACM International Workshop on Wireless Sensor Networks and Applications

September 2002

42 48

2-s2.0-0036983208

C.-H.

Lee

K.-C.

Chung

Y.-C.

A Delaunay Triangulation based method for wireless sensor network deployment

Computer Communications 2007 30 14-15 2744 2752

2-s2.0-34548824817

10.1016/j.comcom.2007.05.017

Zhang

A novel element detection method in audio sensor networks

International Journal of Distributed Sensor Networks 2013 2013 12

607187

10.1155/2013/607187

Zhao

Liu

Guibas

Reich

Collaborative signal and information processing: an information-directed approach

Proceedings of the IEEE 2003 91 8 1199 1209

2-s2.0-3042514350

10.1109/JPROC.2003.814921

Tenney

R. R.

Sandell

N. R.

Jr.

Detection with distributed sensors

IEEE Transactions on Aerospace and Electronic Systems 1981 17 4 501 510

2-s2.0-0019596509

Blunsom

Hidden markov models

Lecture Notes, August 2004

Tugac

Efe

Radar target detection using hidden Markov models

Progress in Electromagnetics Research B 2012 44 241 259

Henderson

Salzberg

Fasman

K. H.

Finding genes in DNA with a hidden Markov model

Journal of Computational Biology 1997 4 2 127 141

2-s2.0-0030810993

10.

Eschenauer

Gligor

V. D.

A key-management scheme for distributed sensor networks

Proceedings of the 9th ACM Conference on Computer and Communications Security

November 2002

41 47

2-s2.0-0038341106

11.

Zhang

Trappe

Managing the mobility of a mobile sensor network using network dynamics

IEEE Transactions on Parallel and Distributed Systems 2008 19 1 106 120

2-s2.0-37149006099

10.1109/TPDS.2007.1113

12.

Lischinski

Incremental Delaunay triangulation

Graphics Gems IV 1994

Academic Press

47 59

13.

Jian

Zhang

Tao

Wang

A novel HMM-based TTS system using both continuous HMMS and discrete HMMS

Proceedings of the IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP '07)

April 2007

IV709 IV712

2-s2.0-34547514452

10.1109/ICASSP.2007.367011

14.

Bocchieri

Vector quantization for the efficient computation of continuous density likelihoods

Proceedings of the IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP '93)

April 1993

692 695

2-s2.0-0027297381

15.

Camp

Boleng

Davies

A survey of mobility models for ad hoc network research

Wireless Communications and Mobile Computing 2002 2 5 483 502

2-s2.0-0038675868

10.1002/wcm.72

16.

Lou

H.-L.

Implementing the Viterbi algorithm

IEEE Signal Processing Magazine 1995 12 5 42 52

2-s2.0-0029375555

10.1109/79.410439

HMM and Rule-Based Hybrid Intruder Detection Approach by Synthesizing Decisions of Sensors

Abstract

1. Introduction

2. The State Space Representation of a Sensor Field for HMM

2.1. State Formulation on HMM for a Sensor Field

Assumption 1.

2.1.1. An Example for State Formulation

2.1.2. The Representation of Observations of the Example

3. The Structure of HMM for Intruder Detection

4. Decision-Making Methodology Using HMM with Rules

4.1. Stochastic Decision-Making Model with HMM on a Sensor Field

4.2. Rule-Based Filtering to Enhance the Stochastic Decision

5. Experimental Result

5.1. The Sensor Field Applied for the Simulation

5.2. The Performance of Our Approach Using HMM with Rules for Intruder Detection

5.3. The Effectiveness Analysis of Our Approach

6. Conclusion

Footnotes

Acknowledgment

References