A Voronoi-Based Sensor Handover Protocol for Target Tracking in Distributed Visual Sensor Networks

Abstract

Target tracking is one of the important applications of wireless sensor networks. For a visual sensor network, the visual sensors have particular characteristics such as directional sensing, limited angle of view, and line-of-sight view. Target tracking with visual sensors is different from that with scalar sensors. Moreover, the quality of sensed visual data can be much important in many applications. In this paper, the concept of Voronoi diagram is utilized for target tracking in visual sensor networks. The structure of Voronoi cells is suitable for the design of a distributed/localized algorithm and it exists a property of bisector for dividing a distance line or region. This paper proposed a Voronoi-based distributed sensor handover protocol for visual sensor networks. The simulation result shows the benefits of our proposed approach in terms of target-detected latency, target-tracked ratio, and average target distance, which indicates that the quality of target tracking service can be improved with the proposed approach for visual sensor networks.

1. Introduction

Wireless sensor networks (WSN) [1], which have the essential capabilities of sensing, computing, and communicating, have attracted a wide range of attention in the past decade. WSNs are well suited to many applications such as surveillance and monitoring applications [2, 3]. In such applications sensing coverage is one of the fundamental measurement indexes of the QoS (Quality of Service) [4]. A scalar sensor usually has an omnidirectional sensing range (a circular sensing coverage), while a directional sensor has a limited sensing direction and noncircular sensing range [5]. The advances in the technologies of image sensor and embedded system have promoted rapid development of camera/visual sensor networks (VSN) [6, 7]. VSNs belong to a directional sensor network and can provide visual image or video data for the applications of surveillance and monitoring. Numerous related works of object detection, localization, and tracking for WSNs have been proposed [8]. However, most of these approaches are not applicable to the VSNs due to the different characteristics of a visual sensor [9]. In other words, a visual sensor has a limited effective sensing range characterized by its directionality and size-specific sensing angle; moreover, the type of sensed data by a visual sensor is image-based, which are different from the wireless scalar sensors. Different approaches are necessary for the object detection, localization, and tracking in VSN applications. In this paper, the geometric structure of Voronoi diagram [10] is utilized in the proposed design of a visual sensor handover protocol for target tracking in VSNs where a large number of visual sensors are considered to be randomly deployed in a wild field to perform the sensing and tracking tasks. Moreover, the target localization is designed to be completed by single visual sensor without any prior knowledge of target positions, while other related works did the localization by multiple visual sensors. The use of the concept of Voronoi diagram also facilitates the determination of a nearest visual sensor to a detected target object. To the best of our knowledge, this is the first paper that utilizes Voronoi diagram for both target localization and target tracking in a distributed VSN. The major contribution of this paper includes $(1)$ the target localization for tracking can be completed by only single visual sensor using the proposed scheme and needs no prior knowledge of the target position. The localization is completed by neither collaborative multiple sensors nor exploiting the target objects which are equipped with an additional signal transmission component; $(2)$ the proposed distributed Voronoi-based target tracking approach makes the target be tracked by only single sensor at a time, without the need of cooperation of multiple visual sensors; $(3)$ the handover protocol decides when to handover by only the current tracker based on the geometrical Voronoi cell structure. It needs no cooperation information of multiple sensors to compute and make the decision; and $(4)$ the proposed Voronoi-based tracking scheme can ensure the visual quality of the target because it is a shortest-distance-based tracking and handover scheme.

The remainder of the paper is organized as follows. Section 2 briefs the related works of target localization and tracking for WSNs and VSNs. Section 3 describes the assumptions and preconditions for this study. In Section 4, the proposed scheme of Voronoi-based target tracking and sensor handover are described. Section 5 evaluates the performance by simulations. Finally, concluding remarks are made in Section 6.

2. Related Works

For many applications of WSNs, utilization of a localization technology is a requirement to perform certain functions. Localization techniques utilized in WSNs provide useful location information for subjects such as deployment, coverage, routing, tracking, and rescue. It can be categorized into sensor localization and target localization [11]. Both the categories of localization in WSNs have drawn considerable attention of researchers and the solution schemes can be classified as coarse grained or fine grained, GPS free or GPS based, anchor free or anchor based, centralized or distributed, range free or range based, and stationary or mobile sensors [12, 13]. Target localization is specifically for the applications of surveillance and monitoring because this kind of applications is usually interested in not only the existence but also the location of a target object. Most of the target localization schemes used in scalar WSNs are not applicable to VSNs due to the characteristic of directional FoV of a visual/camera sensor. A sensor selection-based target localization algorithm was proposed in [14]. A set of camera sensors that can detect the target with a high probability is selected as candidates, and then certain of the candidates will be selected for the estimation of target position. The algorithm needs numerous camera sensors deployed with higher density in the surveillance region and the target needs to be observed/detected synchronously by a number of sensors. In [15], the authors also proposed an algorithm of sensor selection to select a set of camera sensors for the improvement of target localization accuracy. The algorithm also needs the target to occur in the overlapped area of FoVs of several camera sensors. In [16], coarse-grained and fine-grained localization procedures are performed, respectively. Ordinary wireless sensors are used for rough estimation of target position and camera sensors are used to determine accurate target location. However, it is assumed that targets are equipped with a wireless transceiver to calculate Received Signal Strength Indication (RSSI) and transmit information to sever. The calculation of target position is completed in the server and it is a centralized scheme. In our study, target localization can be completed by only one sensor and there is no need to equip with an additional localization device or signal transmitter on the targets.

Regarding the target tracking, numerous related works aimed for tracking target in ordinary WSNs [17–20]. Data delivery delay time and network lifetime were considered for target tracking in [17]. A heterogeneous wireless sensor network and a mobile wireless sensor network were used in the studies [18, 19], respectively. In [20], boundary nodes of a monitoring region can be found and used to know the entry and exit of a target through the monitoring region. For VSNs, the related work [16] used a hybrid sensor network composed of ordinary and camera sensors for target tracking. The sensors are regularly deployed and arranged in an array, which is different from a random deployment. The work [21] focuses on the solution of cooperative multiobject tracking among multiple camera sensors in a VSN established with a highly correlated sensing mode. In the approach, global information is needed for each camera sensor. In [22], a centralized 2-camera system was proposed for detecting and tracking humans in a realistic indoor home environment. The work [23] utilizes Graphics Processing Unit (GPU) coprocessors to compare image frames of a camera sensor, so as to acquire human position and velocity for tracking and handoff. In [24], multiple camera sensors which detected the same target will cooperate to track the target. An optimal sensor will be selected from these sensors according to a confidence measurement and this optimal sensor is mainly responsible for the tracking task. When the target is detected by a new camera sensor or there is a target movement, a new optimal camera sensor will be selected. The tracking handoff scheme needs the communication of cooperation data of these sensors. In our Voronoi-based handover protocol, there is no need of cooperation data of target detection and tracking of multiple sensors. In [25], an observation correlation coefficient (OCC) is defined as the ratio of the overlap area of two cameras to the FoV of one camera. It is used for the determination of activating a set of cameras to improve the accuracy of target tracking. The scheme works under the cooperation of multiple sensors which observed the target. More camera sensors need to be deployed in the monitoring field and bring coverage overlaps for performing the algorithm. Our proposed protocol can be performed without high overlapped coverage among sensors. On the contrary, our scheme make camera sensors reduce FoV overlaps to have a high overall field coverage and can track the target by a single camera sensor. Table 1 shows a summary of comparing the proposed scheme with the related works.

Table 1

Summary of comparison with related works.

Reference	Characteristic	Comparison
Reference	Characteristic	Related work	Proposed scheme in this paper
[16]	Uses a hybrid sensor network composed of ordinary and camera sensors for target tracking	(i) Targets are equipped with a radio transceiver for RSSI calculation and location estimation (ii) Sensors are regularly deployed and arranged in an array (iii) A centralized approach	(i) No additional component to be equipped on the targets (ii) Sensors are randomly deployed (iii) A distributed approach
[21]	Focuses on the solution of cooperative multiobject tracking among multiple camera sensors	(i) Cooperative tracking by relevant multiple sensor nodes and the VSN is established with a highly correlated sensing mode (ii) Assumes that relative positions and sensing parameters of all sensors are known by each sensor (iii) Multitarget tracking	(i) Tracks the target by a single camera sensor based on Voronoi cell structure (ii) Not need global information (iii) Each sensor aims to track one target, but the algorithm can be extended to track multiple target with one sensor
[22]	Detects and tracks humans in a realistic home environment by exploiting both color and depth camera sensors	(i) It is designed for indoor smart home environment (ii) A 2-camera system; and fuses images from two channels to achieve accuracy rate (iii) A centralized system	(i) It is designed for large scale VSNs (ii) Tracks the target by a single camera sensor based on Voronoi cell structure (iii) A distributed algorithm
[23]	Utilizes GPU coprocessors to compare image frames and obtain human position and velocity for target tracking	(i) Needs Graphics Processing Unit (GPU) (ii) Projects several hundred grid-based ellipsoids on each image frame to compare with the image	(i) Uses general camera sensor without additional GPU (ii) Uses Voronoi cells for target tracking, not grid-based structure
[24]	Presents a cooperative multicamera target tracking method based on node selection scheme	(i) Tracking handoff scheme needs the communication of cooperation data of multiple sensors to select optimal tracker (ii) Whenever the target is detected by a new camera sensor or there is a target movement, a new optimal camera sensor will be selected	(i) Voronoi-based handover protocol does not need the cooperation data of multiple sensors. (ii) No sensor selection procedure
[25]	Shows an observation correlation coefficient (OCC) which is defined and used for the determination of activating a set of cameras to improve the accuracy of target tracking	(i) At least two cameras are needed to determine the target location (ii) Tracking under the cooperation of multiple sensors (iii) More camera sensors are needed to be deployed with coverage overlaps for performing the algorithm	(i) Tracks the target by a single camera sensor based on Voronoi cell structure (ii) Performs without high overlapped sensor coverage; on the contrary, overlap is reduced to increase overall coverage ratio

3. Preliminaries

3.1. Voronoi Diagram

In this study, the properties of a Voronoi diagram is utilized to propose the sensor handover protocol for target tracking in a VSN. A Voronoi diagram, as shown in Figure 1, has the following properties. (1)

It divides an area into convex polygons, called Voronoi cells, according to a given set of points.

(2)

Each of the given points lies in exactly one Voronoi cell.

(3)

The common/shared edge of two adjacent Voronoi cells is the bisector line between the two points in the two cells.

(4)

For any position q which lies in the cell associated with point p, the distance between q and p must be shorter than the distance between q and the associated point within any other cell.

(5)

For an area with a given set of points, the Voronoi diagram is unique.

A well-known algorithm to construct Voronoi diagram is Fortune's algorithm [26], which is a centralized algorithm. It can generate the Voronoi diagram with the global information of positions of a set of points in a plane. In a VSN, deployed visual sensors can be treated as the set of points for the construction of Voronoi diagram of the surveillance region. For any object which appears in a Voronoi cell, the sensor in the same cell can obtain the optimal sensing quality (the clarity of the picture) of the object and has the strongest reaction capacity to the object. Therefore, the concept of Voronoi diagram is used in the proposed protocol. However, in this study, Voronoi diagram is constructed, distributed, and localized by the deployed sensors without global information. It is not constructed by using a centralized algorithm which needs the global information. Each sensor constructs its own Voronoi cell with local information. Those local Voronoi cells that are constructed by all the deployed sensors will form a complete Voronoi diagram. The detail of the construction of Voronoi cell in this study is described in the Section 4.1.

Figure 1

A Voronoi diagram.

3.2. Assumptions

The basic assumptions in this study are described as follows. (1)

The visual sensors are homogeneous and randomly deployed in the surveillance region at initial phase. They are stationary and direction rotatable.

(2)

Each visual sensor can obtain its coordinates by a localization technology and has enough communication range or can use a multihop transmission method to transmit information to its neighbor sensors.

(3)

The objects to be tracked have no positioning component. Their coordinates are originally unknown.

(4)

The type of target object in the tracking system is determinate or it can be simply recognized by the shape of detected object. Accordingly, the height of the target object can be given approximately.

3.3. Visual Sensing Model

The visual sensors used in this study are directional. And as mentioned in previous Section 3.2 of assumptions, the sensors are direction rotatable. The effective sensing area (Field of View) of the visual sensor is in sector shape. The sensing model for the visual sensors in the proposed protocol is shown in Figure 2 and the related notations are listed in Table 2.

Table 2

Notations for the sensing model.

Notation	Description
( $x_{s}$ , $y_{s}$ )	Coordinates of the visual sensor
α	Angle of view (AoV) of the visual sensor
r	Effective sensing radius of the visual sensor
$θ_{s}$	Sensing direction of the visual sensor (direction angle relative to the positive x-axis)

Figure 2

Sensing model for visual sensors.

4. Voronoi-Based Sensor Handover Protocol (VSHP)

4.1. Local Voronoi Cell Construction and Sensing Coverage Enhancement

In this study, the concept of Voronoi diagram is utilized for dividing the surveillance region into numerous convex polygons, namely, Voronoi cells. The sensors deployed in the surveillance region can be treated as the points in a Voronoi diagram, and each sensor belongs to one and only one cell in the diagram. As mentioned in Section 3.1, a Voronoi diagram can be generated by the well-known Fortune's algorithm, which is a centralized algorithm, from a given set of points in a plane. However, this study aims at proposing a distributed protocol; the sensors only distributedly construct the local Voronoi cell of their own without the global information of the sensor network.

After the random deployment of sensors, each sensor will broadcast its coordinates to and receive coordinates from neighbors. Figure 3 illustrates the construction of a local Voronoi cell with only the local information of neighbor positions. The sensor $s_{t_{0}}$ receives coordinates from $s_{t_{1}}$ , $s_{t_{2}}, \dots$ in sequence and constructs the corresponding bisector line segments one at a time. Finally, $s_{t_{0}}$ can obtain the structure of its local Voronoi cell enclosed by these bisector line segments.

Figure 3

Construction of a local Voronoi cell.

Because the visual sensors are randomly deployed, their positions and sensing directions are also random at initial phase. A coverage enhancement is needed to reduce the overlaps of sensing coverage of these visual sensors. Then, the overall coverage ratio of the surveillance region can be improved for the task of target tracking. The algorithm in our previous work [27] is utilized for coverage enhancement in this study.

4.2. Object Detection

In a tracking system, object detection is necessary prior to the object tracking. For tracking in a VSN, the detection can be done by object segmentation from the camera scenes. Background subtraction [28–30] is an important approach for object segmentation in visual surveillance system, which compares two images to acquire the difference. A simple illustration of background subtraction is shown in Figure 4. A foreground intruder object can be extracted by comparing current image frame, $f (x, y, t_{i + 1})$ , with previous reference background image, $f (x, y, t_{i})$ . Furthermore, a dynamic background subtraction approach will keep background image updated for next comparison with newer incoming image to detect object movement. Dynamic background subtraction can be defined as the following equation where $f_{diff} (x, y, t_{i + 1})$ is the image frame of difference between background frame and subsequent frame:

\begin{matrix} f_{diff} (x, y, t_{i + 1}) = | f (x, y, t_{i}) - f (x, y, t_{i + 1}) | . \end{matrix}

(1)

Figure 4

Dynamic background subtraction for object and movement detection.

4.3. Target Localization

Once an incoming object is detected by a visual sensor, the sensor will estimate the actual position of the object on the ground plane. To estimate the object position, firstly the direction of the object will be calculated and secondly the distance of the object. Regarding the object direction, as shown in Figure 5, the view from the visual sensor is limited by its angle of view and the captured scene is shown on the image in a rectangle shape. Things in a line of sight will appear in a vertical line on the image. As the illustration, the direction of the detected target object (a human) can be calculated by the following equations with the notations listed in Table 3:

\begin{matrix} β = α \cdot \frac{w_{t}}{W_{R}} = α \cdot \frac{w_{LB} + w_{RB}}{2 W_{R}}, \\ θ_{t} = θ_{s} - \frac{α}{2} + β . \end{matrix}

(2)

Table 3

Notations for calculation of target object direction.

Notation	Description
$θ_{t}$	Angle of the direction from the sensor to the target relative to the positive x-axis
β	Included angle between the line of sight from the sensor to the target and the right edge of the field of view (FoV)
$W_{R}$	Horizontal resolution (width in pixels) of the image
$w_{t}$	Width (in pixels) of the distance between the target object center and the right edge of the image
$w_{LB}$	Width (in pixels) of the distance between the left edge of the detected target object and the right edge of the image
$w_{RB}$	Width (in pixels) of the distance between the right edges of the detected target object and the image

Figure 5

Calculation of object (target) direction.

Regarding the distance of the object, as shown in Figure 6, the image of real object is projected reversely on the internal image sensor (usually a CCD or CMOS sensor) through the camera lens, and then electronic signals generated by the internal image sensor are processed with an image processor to form the digital image. Since the target object was assumed to be a height of given value, the distance between the target object and visual sensor can be calculated by the following equations with the notations listed in Table 4:

\begin{matrix} \tan λ = \frac{h_{t}}{d_{t}} = \frac{h_{s}}{d_{s}}, \\ d_{t} = \frac{h_{t} d_{s}}{h_{s}} = \frac{h_{t} d_{s}}{H_{S} (h_{BB} - h_{TB}) / H_{R}} = \frac{h_{t} d_{s} H_{R}}{H_{S} (h_{BB} - h_{TB})} . \end{matrix}

(3)

Table 4

Notations for calculation of target object distance.

Notation	Description
$h_{t}$	Assumed (given) height of the target object
$d_{t}$	Distance between the visual sensor and target object
λ	Included angle of the two lines of sight to top and bottom of the target object
$H_{S}$	Height of the internal image sensor
$h_{s}$	Height of the captured target object in the internal image sensor
$d_{s}$	Distance between the internal image sensor and the camera lens
$H_{R}$	Vertical resolution (height in pixels) of the image
$h_{BB}$	Height (in pixels) of the distance between the bottom edge of the object and the top edge of the image
$h_{TB}$	Height (in pixels) of the distance between the top edges of the object and the image

Figure 6

Calculation of object (target) distance.

If the height of the target object is not exactly equal to the given assumed value and there is a difference of ε, a calculation error of distance will occur. As shown in Figure 6, if the actual height of the object is $h_{t}^{'} = h_{t} + ε$ and the image height of the captured object is the same, the system believes that the object distance is $d_{t}$ after the calculation. However, the actual distance should be $d_{t}^{'}$ , which can be calculated by the following equations. Equation (7) shows that there will be an error ratio of $ε / h_{t}$ between the calculated and actual object distances. For instance, if $h_{t}$ is given as a value of 170 cm and the calculated object distance $d_{t}$ is 30 m, but the actual height $h_{t}^{'}$ of the object is 175 cm, then the actual distance should have an error of $5 cm / 170 cm \times 30 m = 0.88 m$ . We believe that the distance error ratio of $ε / h_{t}$ is tolerable.

Let

\begin{matrix} k = \frac{d_{s} H_{R}}{H_{S} (h_{BB} - h_{TB})}, \end{matrix}

(4)

\begin{matrix} d_{t} = h_{t} k, \end{matrix}

(5)

\begin{matrix} d_{t}^{'} = (h_{t} + ε) k = h_{t} k + ε k = d_{t} + ε \frac{d_{t}}{h_{t}}, \end{matrix}

(6)

\begin{matrix} d_{t}^{'} = d_{t} (1 + \frac{ε}{h_{t}}) . \end{matrix}

(7)

As shown in Figure 7, ( $x_{s}$ , $y_{s}$ ) and ( $x_{t}$ , $y_{t}$ ) indicate the coordinates of the visual sensor and target object, respectively. Once both the direction and distance of the target object are calculated, the coordinates of the object can be obtained as follows. This will be used in the control of sensor handover:

\begin{matrix} x_{t} = x_{s} + d_{t} \cos θ_{t}, \\ y_{t} = y_{s} + d_{t} \sin θ_{t} . \end{matrix}

(8)

Figure 7

Calculation of object (target) coordinates.

4.4. Sensor Handover

After the visual sensor obtains the coordinates of the target object, it adjusts the sensing direction toward the target and then detects object movement by dynamic background subtraction mentioned in Section 4.2. Once a movement of the target object is detected, the new position of the object will be calculated by the localization scheme described in Section 4.3 again. This is a routine procedure for local target tracking by the visual sensor until the tracking task is handed over.

To determine that whether the visual sensor will handover the task of tracking of the target object, firstly the sensor utilizes the structure of the constructed local Voronoi cell and divides the cell into several subregions. As shown in Figure 8, the Voronoi cell associated with the sensor s is divided into several triangular subregions according to the vertices of the cell, and the target object t is located in the subregion of $Δ v_{R i} s v_{L i}$ with an included angle of $∠ v_{R i} s v_{L i} = ϕ$ .

Figure 8

Subregions divided from a local Voronoi cell according to the vertices.

A target object t is detected by a sensor s and belongs to one of the subregions if and only if all the following three conditions are satisfied. (1)

The object distance is less than or equal to the sensing radius of the sensor:

\begin{matrix} d_{t} \leq r . \end{matrix}

(9)

(2)

The distance between the object and the sensor is less than or equal to the one between the object and the neighbor sensor on the opposite side of the bisector line (edge) facing the included angle of the subregion:

\begin{matrix} \sqrt{{(x_{t} - x_{s})}^{2} + {(y_{t} - y_{s})}^{2}} \leq \sqrt{{(x_{t} - x_{s_{i}})}^{2} + {(y_{t} - y_{s_{i}})}^{2}} . \end{matrix}

(10)

(3)

The object is located inside the two edges of the included angle of the subregion:

\begin{array}{l} (x_{t} - x_{s}) (x_{L_{i}} - x_{s}) + (y_{t} - y_{s}) (y_{L_{i}} - y_{s}) \\ \geq \sqrt{\frac{{(x_{t} - x_{s})}^{2} + {(y_{t} - y_{s})}^{2}}{{(x_{R_{i}} - x_{s})}^{2} + {(y_{R_{i}} - y_{s})}^{2}}} \\ \times ((x_{L_{i}} - x_{s}) (x_{R_{i}} - x_{s}) + (y_{L_{i}} - y_{s}) (y_{R_{i}} - y_{s})), \end{array}

(11)

\begin{array}{l} (x_{t} - x_{s}) (x_{R_{i}} - x_{s}) + (y_{t} - y_{s}) (y_{R_{i}} - y_{s}) \\ \geq \sqrt{\frac{{(x_{t} - x_{s})}^{2} + {(y_{t} - y_{s})}^{2}}{{(x_{L_{i}} - x_{s})}^{2} + {(y_{L_{i}} - y_{s})}^{2}}} \\ \cdot ((x_{L_{i}} - x_{s}) (x_{R_{i}} - x_{s}) + (y_{L_{i}} - y_{s}) (y_{R_{i}} - y_{s})) . \end{array}

(12)

Equation (11) represents that the target object is not located outside the left edge $\bar{s v_{L_{i}}}$ and (12) represents that the target object is not located outside the right edge $\bar{s v_{R_{i}}}$ . The former is derived from the definition of inner product of two Euclidean vectors in linear algebra:

\begin{matrix} \overset{⃑}{s v_{L_{i}}} \cdot \overset{⃑}{s v_{R_{i}}} = ∥ \overset{⃑}{s v_{L_{i}}} ∥ ∥ \overset{⃑}{s v_{R_{i}}} ∥ \cos \emptyset, \end{matrix}

(13)

\begin{matrix} \cos \emptyset = \frac{\overset{⃑}{s v_{L_{i}}} \cdot \overset{⃑}{s v_{R_{i}}}}{∥ \overset{⃑}{s v_{L_{i}}} ∥ ∥ \overset{⃑}{s v_{R_{i}}} ∥} . \end{matrix}

(14)

The angle

∠ v_{L i} s t

must be less than or equal to ϕ; therefore

\begin{array}{l} \overset{⃑}{s t} \cdot \overset{⃑}{s v_{L_{i}}} \geq ∥ \overset{⃑}{s t} ∥ ∥ \overset{⃑}{s v_{L_{i}}} ∥ \cos \emptyset, \\ \overset{⃑}{s t} \cdot \overset{⃑}{s v_{L_{i}}} \geq ∥ \overset{⃑}{s t} ∥ ∥ \overset{⃑}{s v_{L_{i}}} ∥ \cdot \frac{\overset{⃑}{s v_{L_{i}}} \cdot \overset{⃑}{s v_{R_{i}}}}{∥ \overset{⃑}{s v_{L_{i}}} ∥ ∥ \overset{⃑}{s v_{R_{i}}} ∥}, \\ 〈 x_{t} - x_{s}, y_{t} - y_{s} 〉 \cdot 〈 x_{L_{i}} - x_{s}, y_{L_{i}} - y_{s} 〉 \\ \geq \frac{∥ 〈 x_{t} - x_{s}, y_{t} - y_{s} 〉 ∥}{∥ 〈 x_{R_{i}} - x_{s}, y_{R_{i}} - y_{s} 〉 ∥} \\ \cdot 〈 x_{L_{i}} - x_{s}, y_{L_{i}} - y_{s} 〉 \cdot 〈 x_{R_{i}} - x_{s}, y_{R_{i}} - y_{s} 〉 . \end{array}

(15)

Then, (11) is derived. Similarly, the angle

∠ v_{R i} s t

must be less than or equal to ϕ; thus

\overset{⃑}{s t} \cdot \overset{⃑}{s v_{R_{i}}} \geq ∥ \overset{⃑}{s t} ∥ ∥ \overset{⃑}{s v_{R_{i}}} ∥ \cos \emptyset

, and then (12) also can be derived.

Once a sensor detected an object and ascertained that the object is located in one of the subregions of the local Voronoi cell, there will be four conditions, while the sensor keeps tracking the moving target object. (1)

As shown in Figure 9(a), the target object can still be detected and it is still located in the same triangular subregion; that is to say, (9), (10), (11), and (12) are still satisfied under the same pair of vertices $v_{L i}$ and $v_{R i}$ . For this condition, the sensor will normally keep tracking the target object.

(2)

As shown in Figure 9(b), the target object can still be detected but it has just moved from original subregion to another subregion. For this condition, the sensor will calculate and obtain a new pair of vertices, $v_{L j}$ and $v_{R j}$ , for the target tracking in the new subregion. Equations (9), (10), (11), and (12) are still satisfied for this condition.

(3)

As shown in Figure 9(c), the target object can still be detected, but the target object has just moved beyond the bisector line $\bar{v_{L_{i}} v_{R_{i}}}$ between the two sensors s and $s_{i}$ ; that is to say, (10) is no longer satisfied and the object moved from the original Voronoi cell to the Voronoi cell belongs to the sensor $s_{i}$ . This means that the sensor $s_{i}$ will obtain a better sensing (image) quality than the sensor s and it is more suitable to track the target object. For this condition, the sensor s will send a request message with the object coordinates to $s_{i}$ and handover the tracking task to $s_{i}$ . After receiving the request message, the sensor $s_{i}$ will adjust its sensing direction to the target object and reply a message to s for confirmation of taking over the tracking task.

(4)

As shown in Figure 9(d), the target object is still in the triangular subregion, but it moved out of the sensing radius of the sensor s; that is to say, (9) is no longer satisfied. This means that the sensor lost track of the target object. For this condition, the sensor will send a request message with the final detected coordinates of the target object to certain of its adjacent sensors. Those sensors that received the request message will adjust their sensing directions to the received coordinates and wait (detect) for the possible appearance of the target object. For example, though the target object was lost track, it may move around and appear near one of the vertices of the triangular subregion (e.g., $v_{R i}$ ). Accordingly, the sensor s will send a request message to both $s_{i}$ and $s_{j}$ to notify them that the target object may move to and appear in their fields of view and an adjustment of sensing direction is needed. The following equations show the selection of destination sensors for sending the request message. Notations $(x_{t_{f}}, y_{t_{f}})$ and $V_{s_{k}}$ are the final detected coordinates of the target and the set of local Voronoi vertices of sensor $s_{k}$ , respectively:

\begin{array}{l} v^{'} = {v ∣ v \in {v_{L_{i}}, v_{R_{i}}}, \\ \sqrt{{(x_{v} - x_{s})}^{2} + {(y_{v} - y_{s})}^{2}} > r}, \\ v^{''} = {\begin{cases} \underset{v \in v^{'}}{\arg \min} \sqrt{{(x_{v} - x_{t_{f}})}^{2} + {(y_{v} - y_{t_{f}})}^{2}}, \\ \frac{\sqrt{{(x_{s_{i}} - x_{s})}^{2} + {(y_{s_{i}} - y_{s})}^{2}}}{2} > r \\ v^{'}, \\ otherwise, \end{cases} \\ S_{req} = {s_{k} ∣ v^{''} \in V_{s_{k}}} - {s} . \end{array}

(16)

Figure 9

Different target tracking conditions.

The probability of that a target can be detected by a visual sensor is equal to the overall sensing coverage ratio of the VSN. In addition, once a target has been detected and under tracking, the probability of target missing is equal to $e^{- λ π r^{2}}$ where λ is the density of visual sensors and r is the sensing radius. This value of probability is $1 - R_{omni}$ where $R_{omni}$ is the omnidirectional coverage (in the shape of a circle) ratio of the sensors. It is because one visual sensor will be notified of rotating the sensing direction and taking over the target when the target is going to leave apart from its current tracker. This will be failed if no other sensor can cover the target even if the sensing direction is rotated.

As described in Section 4.1, after visual sensors are deployed initially, an algorithm of sensing coverage enhancement is performed. Whenever a sensor keeps tracking a moving target object or several sensors are notified of adjusting their sensing directions to wait a possible appearance of the lost target, their sensing directions will be changed and the overlapped coverage can be increased; thus overall field coverage can be reduced. This will cause a negative effect on further object detection and tracking. Therefore, in the proposed protocol, those sensors that have changed the sensing direction will return to their original directions if the sensors have lost the target or waited the appearance of target for a long time, $t_{ret}$ .

4.5. Procedures of VSHP

Figure 10 summarizes the procedures of the proposed Voronoi-based sensor handover protocol for moving target tracking.

Figure 10

Procedures of the proposed VSHP.

With regard to the issue of energy consumption, the sensor operations about computation, communication, direction rotation, and photographing will consume energy of the sensor. This could cause sensors energy exhaustion and malfunction in the applications of wireless VSNs. A recent research topic and current trend about energy issue of sensor networks are the energy harvesting sensors [31–33]. Energy harvesting is one of the promising solutions to the problem of limited energy capacity in wireless sensor networks. It is easy to foresee that a future sensor network can consist of sensor devices with the integration of the technology of energy harvesting. This paper aims at the target localization and tracking in VSNs; therefore energy issue is not concerned. However, our proposed algorithm can still perform well, while some of the sensors are malfunctioning. This is due to the fact that the proposed Voronoi-based algorithm makes visual sensors be able to easily reconstruct the local Voronoi cells and can keep the VSN tracking operations well performing until most (or all) of the sensors are failed. It has the characteristic of fault tolerance and graceful degradation.

On the other hand, the tracking algorithm described above focuses on the case of tracking single target with one visual sensor. It is applicable to the case of which multiple targets occur in the surveillance region and can be, respectively, tracked by one sensor. Once the multiple targets occur in one Voronoi cell at the same time, they only can be all tracked if $(1)$ all of them keep locating in the FoV of the associated sensor of the Voronoi cell or $(2)$ each individual of the targets is located within the sensing radius of any other visual sensor that can be notified of taking over the target.

5. Simulation Results

This study evaluates the proposed Voronoi-based approach with simulations. There are four QoS criteria to be used for the evaluation: $(1)$ the overall sensing field coverage; $(2)$ the target-detected latency; $(3)$ the target-tracked ratio; and $(4)$ the average target distance. The first, overall coverage, will affect the detection of target objects. The second, target-detected latency, indicates how long the time is taken by a sensor detecting the target since the target moved into the surveillance region. The third, target-tracked ratio, indicates the total time of durations of which the target is tracked in its movement across the surveillance region. The last, average target distance, represents the image quality, while the target is tracked. In the simulations, a large scale visual sensor network is deployed randomly in the surveillance region and the target moves across the surveillance region with a random waypoint mobility model [34]. The target tracking services with and without the proposed protocol are evaluated and compared by the above-mentioned QoS criteria. Table 5 shows the parameters setting of the simulations.

Table 5

Parameters setting of the simulations.

Notation	Description	Value	Default
F	Size of the surveillance region	800 m × 800 m
n	Number of the visual sensors	50~100 (interval: 10)	100
α	Angle of view (AoV) of the visual sensors	60°~120° (interval: 15°)	105°
r	Sensing radius of the visual sensors	50 m~90 m (interval: 10 m)	70 m

Figure 11 shows the simulation results of both coverage and target-detected latency. OVSN-C and VSHP-C represent the overall field coverage ratios after deployment of ordinary visual sensor network (OVSN) and after enhancement with proposed VSHP, respectively. OVSN-L and VSHP-L represent the ratios of target-detected latency under OVSN and proposed VSHP approach, respectively. The ratio of target-detected latency ( $r_{L}$ ) is defined as (17) where $t_{D}$ represents how long the time is taken by a sensor detecting the target since the target moved into the surveillance region, and $t_{SR}$ is the total time of the sensor traveling in the surveillance region. In Figure 11, the simulation result shows that the target-detected latency of VSHP is less than the one of OVSN no matter how many the number of deployed sensors is (n = 50~100). VSHP reduces about 4% of the total travel time of the target to detect the target. This is due to the coverage enhancement in VSHP. The simulation result shows that there is a coverage improvement of about 5.5% with VSHP:

\begin{matrix} r_{L} = \frac{t_{D}}{t_{SR}} . \end{matrix}

(17)

Figure 11

Coverage and target-detected latency (fixed $α = 105^{°}$ ; $r = 70$ m).

The total travel time of a target in the surveillance region consists of target-tracked and target-untracked durations. Keeping a higher target-tracked time ratio is an important criterion for target tracking services. Figure 12 shows that VSHP provides a higher target-tracked ratio than OVSN. This is due to the efficacy of the Voronoi-based sensor handover mechanism.

Figure 12

Target-tracked ratio (fixed $α = 105^{°}$ ; $r = 70$ m).

The other criterion for measuring the QoS of target tracking in a VSN is the average distance between the sensor and the target, while the target is tracked (monitored) by the sensor. For a visual (camera) sensor, a shorter target distance will bring a clearer (higher) quality of image or video. Figure 13 shows the simulation result of average target distance of which the target is tracked. The proposed VSHP has a shorter average target distance than OVSN does. This is due to the fact that the proposed handover protocol utilizes the characteristic of Voronoi cell to select an appropriate sensor for the tracking task. Moreover, the average target distance is reduced from 40 m to 35 m, while the number of sensor is increased from 50 to 100. This indicates that the VSHP can select more appropriate sensors from the larger number of deployed sensors for the target tracking.

Figure 13

Average target distance (fixed $α = 105^{°}$ ; $r = 70$ m).

The results given above are with various values of n but fixed values of α and r. The simulation results of the cases with fixed n but various α and r were also given as foll ows. Figures 14, 15, and 16 show the coverage and target-detected latency, the target-tracked ratio, and the average target distance, respectively. The results are similar to those given above. VSHP obtained higher coverage ratios and less target-detected latency in comparison with OVSN. The target-tracked ratio of VSHP is higher than that of OVSN. And VSHP obtained shorter average target distance than OVSN did. In summary, VSHP can provide a better quality of target tracking in visual sensor networks.

Figure 14

Coverage and target-detected latency (fixed $n = 100$ ).

Figure 15

Target-tracked ratio (fixed $n = 100$ ).

Figure 16

Average target distance (fixed $n = 100$ ).

6. Conclusion and Future Works

This paper utilizes the structure and characteristic of Voronoi cells and proposes a new solution for target tracking in visual/camera sensor networks. The solution contains mechanisms of coverage enhancement, object detection, target localization, and sensor handover. Simulations were used for the evaluation of effectiveness of the proposed approach. Four QoS criteria for target tracking were evaluated. The results show that the approach performs well and has an improvement in comparison with target tracking in ordinary visual sensor networks.

Our future work is to implement a practical system with real camera sensors. An experimental evaluation of effectiveness and performance for the practical system will be made. Moreover, the utilizations of mobile visual sensors (e.g., smartphones) and the integration with cloud-based monitoring service will be developed and realized for an extension of this study.

Footnotes

Conflict of Interests

The authors declare that there is no conflict of interests regarding the publication of this paper.

Acknowledgments

This work is supported by National Science Council of Taiwan under Grant no. NSC 102-2219-E-006-001 and Research Center for Energy Technology of National Cheng Kung University under Grant no. D102-23015.

References

Akyildiz

I. F.

Vuran

M. C.

Wireless Sensor Networks 2010

New York, NY, USA

John Wiley and Sons

Khedo

K. K.

Perseedoss

Mungur

A wireless sensor network air pollution monitoring system

International Journal of Wireless and Mobile Networks 2010 2 2 31 45

Felemban

Advanced border intrusion detection and surveillance using wireless sensor network technology

International Journal of Communications, Network and System Sciences 2013 6 5 251 259

Zhu

Zheng

Shu

Han

A survey on coverage and connectivity issues in wireless sensor networks

Journal of Network and Computer Applications 2012 35 2 619 632

2-s2.0-84856225521

10.1016/j.jnca.2011.11.016

Guvensan

M. G.

Yavuz

A. G.

On coverage issues in directional sensor networks: a survey

Ad Hoc Networks 2011 9 7 1238 1255

2-s2.0-79958163700

10.1016/j.adhoc.2011.02.003

Bramberger

Doblander

Maier

Rinner

Schwabach

Distributed embedded smart cameras for surveillance applications

Computer 2006 39 2 68 75

2-s2.0-33344460692

10.1109/MC.2006.55

Soro

Heinzelman

A survey of visual sensor networks

Advances in Multimedia 2009 2009 22

2-s2.0-68949132673

10.1155/2009/640386

640386

Viani

Rocca

Oliveri

Trinchero

Massa

Localization, tracking, and imaging of targets in wireless sensor networks: an invited review

Radio Science 2011 46 5

2-s2.0-80052774797

10.1029/2010RS004561

RS5002

Charfi

Wakamiya

Murata

Challenging issues in visual sensor networks

IEEE Wireless Communications 2009 16 2 44 49

2-s2.0-67349127129

10.1109/MWC.2009.4907559

10.

Okabe

Boots

Sugihara

Chiu

S. N.

Spatial Tessellations: Concepts and Applications of Voronoi Diagrams 2000 2nd

Chichester, UK

Wiley

11.

Cheng

Zhang

Maple

A survey of localization in wireless sensor network

International Journal of Distributed Sensor Networks 2012 2012 12

962523

10.1155/2012/962523

12.

Alrajeh

N. A.

Bashir

Shams

Localization techniques in wireless sensor networks

International Journal of Distributed Sensor Networks 2013 2013 9

304628

10.1155/2013/304628

13.

Niewiadomska-Szynkiewicz

Localization in wireless sensor networks: classification and evaluation of techniques

Information International Journal of Applied Mathematics and Computer Science 2012 22 2 281 297

14.

Liu

Zhang

Optimal node selection for target localization in wireless camera sensor networks

IEEE Transactions on Vehicular Technology 2010 59 7 3562 3576

2-s2.0-77956788283

10.1109/TVT.2009.2031454

15.

Zhang

Sensor selection for improving sccuracy of target localisation in wireless visual sensor networks

IET Wireless Sensor Systems 2012 2 4 293 301

16.

Gao

Zhu

Chao

H. C.

A hybrid localization and tracking system in camera sensor networks

International Journal of Communication Systems 2012

10.1002/dac.2492

17.

Liu

Algorithms for energy efficient mobile object tracking in wireless sensor networks

Cluster Computing 2010 13 2 181 197

2-s2.0-77952097358

10.1007/s10586-009-0108-9

18.

Khedr

A. M.

Osamy

Effective target tracking mechanism in a self-organizing wireless sensor network

Journal of Parallel and Distributed Computing 2011 71 10 1318 1326

2-s2.0-80051667853

10.1016/j.jpdc.2011.06.001

19.

Chen

Cooperative distributed target tracking algorithm in mobile wireless sensor networks

Journal of Control Theory and Applications 2011 9 2 155 164

2-s2.0-79958184036

10.1007/s11768-011-8124-8

20.

Sahoo

P. K.

Sheu

J. P.

Hsieh

K. Y.

Target tracking and boundary node selection algorithms of wireless sensor networks for internet services

Information Sciences 2013 230 21 38

10.1016/j.ins.2012.07.034

21.

Chu

Zhuo

Zhao

Cooperative multi-object tracking method for wireless video sensor networks

Proceedings of the 3rd IEEE International Workshop on Multimedia Signal Processing (MMSP '11)

November 2011

Hangzhou, China

1 5

2-s2.0-84055176978

10.1109/MMSP.2011.6093796

22.

Han

Pauwels

E. J.

de Zeeuw

P. M.

de With

P. H. N.

Employing a RGB-D sensor for real-time tracking of humans across multiple Re-entries in a smart environment

IEEE Transactions on Consumer Electronics 2012 58 2 255 263

23.

Limprasert

Wallace

Michaelson

Real-time people tracking in a camera network

IEEE Journal on Emerging and Selected Topics in Circuits and Systems 2013 3 2 263 271

24.

Wang

Fang

Automatic node selection and target tracking in wireless camera sensor networks

Computers and Electrical Engineering 2013

10.1016/j.compeleceng.2013.07.005

25.

Camera sensor activation scheme for target tracking in wireless visual sensor networks

International Journal of Distributed Sensor Networks 2013 2013 11

397537

10.1155/2013/397537

26.

Fortune

A sweepline algorithm for Voronoi diagrams

Algorithmica 1987 2 1–4 153 174

2-s2.0-52449147685

10.1007/BF01840357

27.

Sung

T. W.

Yang

C. S.

Voronoi-based coverage improvement approach for wireless directional sensor networks

Journal of Network and Computer Applications 2014 39 202 213

10.1016/j.jnca.2013.07.003

28.

Elgammal

Background Subtraction: Theory and Practice. Augmented Vision and Reality 2013

Berlin, Germany

Springer

29.

Alvar

Sánchez

Á.

Arranz

Á.

Fast background subtraction using static and dynamic gates

Artificial Intelligence Review 2014 41 1 113 128

10.1007/s10462-011-9301-3

30.

Barnich

Van Droogenbroeck

ViBe: a universal background subtraction algorithm for video sequences

IEEE Transactions on Image Processing 2011 20 6 1709 1724

2-s2.0-79957497122

10.1109/TIP.2010.2101613

31.

Roscoe

N. M.

Judd

M. D.

Harvesting energy from magnetic fields to power condition monitoring sensors

IEEE Sensors Journal 2013 13 6 2263 2270

32.

Xie

Shi

Hou

Y. T.

Sherali

H. D.

Making sensor networks immortal: an energy-renewal approach with wireless power transfer

IEEE/ACM Transactions on Networking 2012 20 6 1478 1761

2-s2.0-84857126297

10.1109/TNET.2012.2185831

33.

Sudevalayam

Kulkarni

Energy harvesting sensor nodes: survey and implications

IEEE Communications Surveys and Tutorials 2011 13 3 443 461

2-s2.0-79959289243

10.1109/SURV.2011.060710.00094

34.

Bettstetter

Hartenstein

Pérez-Costa

Stochastic properties of the random waypoint mobility model

Wireless Networks 2004 10 5 555 567

2-s2.0-3042778324

10.1023/B:WINE.0000036458.88990.e5