Twice Deployment Node Balance Algorithm for Road Network Surveillance

Abstract

This paper proposes a twice deployment node balance algorithm (TDNB) which guarantees successful detection of the moving target on road networks. Through dividing the deployment of the sensor nodes into two phases instead of deploying all the sensors at one time, TDNB has a better performance. In the former phase, some of the sensors are deployed on the road at random. In the latter phase, the rest of the sensors are deployed on demand to make the number on each path the same. Due to the equivalence of the node's number, the network will have a prolonged lifetime after inserting nodes into the segment according to this algorithm. TDNB extends the network's lifetime remarkably compared with the former algorithms. Furthermore, TDNB enables us to insert nodes to the segment required in the network instead of all the segments, which reduces the workload to a large extent. In short, without increasing the number of sensors in road network, TDNB has a better performance compared to VISA in terms of network lifetime, which meets the demand for persistent monitoring application.

1. Introduction

The demand for surveillance and tracking in extreme environment or battlefield has fostered a growing interest in road network surveillance with wireless sensor network (WSN) in recent years [1, 2]. The lifetime of the network is one of the most important factors when applied to those extreme situations, so it is a big challenge to prolong the network's lifetime in the road network surveillance system. Sensing scheduling and node deployment are two dominant parts of the road network surveillance system for they are related to sensing area, interconnection of road networks, and energy consumption, and all of which will influence the performance of sensor networks greatly [3].

Most of the surveillance systems have focused on surveillance for two-dimensional space, such as open battle field, while the research on road network is limited. WSNroad network surveillance system consists of sensor nodes, targets, and road networks, which are the key features to distinguish it from two-dimensional space WSN surveillance systems. Meanwhile, there are protection point and entrance point in the road network. The entrance point denotes the point from which a target can intrude the network. The protection point denotes the point that surveillance system should protect. In the road network surveillance system, the target is confined within road segments with a bounded maximum speed. A typical scenario is shown in Figure 1.

Figure 1

Road network surveillance.

In a road network, the heart of the area is always the protection point, and the target can get to the protection point through variance of roads. The surveillance system guarantees both of the successful detection of the intruding target before it reaches the protection point and the maximization of the network's lifetime. Jeong et al. firstly proposes the virtual scanning algorithm (VISA) [1, 2] for road network surveillance which extends the lifetime of the network a lot. We will introduce VISA in the next section in detail. Nodes in VISA system are woke up one by one along the way from the protection point to the entrance point just like scanning wave. In this way, intruding target can be detected during a period of time. However, when it is applied to the road network surveillance system which consists of multiple paths, the network will suffer from a short lifetime due to the inherent shortcoming of the algorithm. So diverse scanning time caused by the drawbacks of VISA shortens the lifetime of the network.

In this paper, we propose a node deployment algorithm based on virtual scanning algorithm for target detection. Furthermore, it is the first work to study how to deploy the nodes satisfying the actual requirement and how to prolong the scanning time of wave on short scanning path which will balance the scanning time of all the scanning paths and maximize the lifetime of the networks.

The rest of the paper is organized as follows. Section 2 talks about the related works in road surveillance algorithm especially VISA who is particularly relevant to this paper. Section 3 introduces methodology of this paper. Evaluation of this algorithm is illustrated in Section 4. Section 5 is the summary of this paper.

2. Related Works

Much more attention is paid to the target detection and target tracking in the road network surveillance applications [1, 2]. Current researches are mainly about the open space surveillance algorithm [1, 2]. Take Point Detection and Tracking; for example, Rabbat and Nowak, who came from the Department of Computer, Wisconsin-Madison University, proposed a distributed detection tracking algorithm that utilizes signal strength received to localize the signal source [4]. Chen et al., who came from University of Illinois, presented a lightweight algorithm based on distributed dynamic hierarchical clustering target tracking algorithm, which took the sensing range of the sensor, as well as energy and other aspects of communication limitation into account [5]. Yao presented a localization algorithm based on the observation that signals from different nodes arrive at the target in different time [6]. Gui and Mohapatra proposed a patrolling surveillance algorithm which was similar to the virtual scanning algorithm that allows the nodes to be awake according to the schedule to find the track of the target [7]. In addition, He et al. implemented the target detection system which allows a group of sensor nodes to work together to identify and track target in the practical environment [8].

Those algorithms mentioned above are all for open space without limitation. When Jeong et al. studied surveillance applications on known road networks, he proposed always-scanning algorithm (ASA) [1, 2]. He divided the entire scenario into three parts, namely, entrance points, protection points, and the road network. The system completes the nodes' initialization by merging and duplicating initial messages. When the system starts to work, each wave propagates from the protection points set to the entrance points set. Taking advantages of low duty cycle of the network, the lifetime of the system can be extended greatly.

The VISA algorithm is described as follows. Compared with the open two-dimensional space surveillance system, there are two facts that we can leverage on. First, the movement of targets is confined within roadways. Second, the road network maps are normally known. The typical scenario for road network surveillance system is shown in Figure 2. Note that n is the number of sensors and they are randomly placed on a road segment with the length as l. The sensing circle radius of each sensor is r. We suppose that the road is covered by the circle. Most of commercially available sensors can achieve the assumption aforementioned, for example, a moving car 60–100 feet away can be detected by PIR sensors. Therefore, the scenario of typical road network surveillance system can be illustrated as Figure 2, where n sensors are linearly placed at random. The left end of the road segment is the entrance point where the target can get into the network and the right end of the road segment is the protection point  P  where we should protect.

Figure 2

Road network surveillance scenario with VISA.

To guarantee successful detection of intrusion target, we may let the sensors always awake intuitively. However, the energy consumption is considerable, and there is better solution. It is observed that it takes $l/v$ (called silent time) for the target from entrance point to arrive at protection point. All of the sensors can sleep for $l/v$ (v denotes the velocity of target) time and then wake up at the same time (note that the target is still on the way to protection point). This algorithm is called duty cycling. Through this algorithm, the energy can be saved. Moreover, this algorithm can be improved furthermore.

Based on the fact that targets move only along the roadways, a new design called virtual scanning is proposed by Jaehoon Jeong which prolonged the lifetime of road network remarkably. As shown in Figure 2, sensors are waked up one by one for a certain time w (the least time a sensor needs to guarantee successful detection of a target) from sensor $s_1$ towards sensor $s_n$ after the silent time. Clearly, this wave of sensing activities guarantees the detection and allows additional sleeping time for individual sensors. We should highlight that the direction of the virtual scan waves shall be from the protection point to the entrance point. The virtual scan of the opposite direction cannot guarantee target intrusion detection if a target enters right with a high speed after the beginning of the network-wide silent time.

VISA algorithm extents the lifetime of network remarkably compared with the road surveillance system before. What is more, it opens a promising direction of road network surveillance. However, because the sensors are all randomly deployed at one time, when VISA is applied on road network surveillance system, the scanning time on each path may be different due to the different number of sensors on each path. As a result, the network will suffer from a short lifetime. We find that the algorithm can be improved furthermore. Therefore, we studied the deployment of the sensor nodes. The network's lifetime can be maximized by balancing the scanning time of each of the scanning waves.

3. Method Design

This section presents the detailed design of TDNB and analyzes the performance of the network with our algorithm in theory.

3.1. Definitions and Assumptions

Our TDNB is based on the following assumptions.

• (1)

The road network map is known (download from Google).

(2)

Targets are confined within the road segments with a maximum speed of $v_{\max }$ .

(3)

The sensing area can cover all the paths of the road network, and there is no sensing hole segment in the network.

(4)

Sensors are roughly time-synchronized (it can make sure that the time shift by the existing solutions is under acceptable limits).

(5)

There is no sophisticated sensor applied to the node point (only sensors like PIR).

(6)

When the target move into the sensing area, the system guarantees successful detection.

The relevant parameters are defined in Table 1.

Table 1

The relevant parameters.

Parameters	Description
$T_{\text{net}}$	The lifetime of the sensor network.
$T_{\text{work}}$	Time that a sensor needs to work for reliable detection.
$T_{\text{scan}}$	The scanning time that the wave moves from the protection point to the entrance point.
$T_{\text{silent}}$	The sleeping time of the whole network.
$T_{\text{period}}$	Schedule period of the sensor network; $T_{\text{period}}=T_{\text{scan}}+T_{\text{silent}}$ .
$T_{\text{scan\_s}}$	The shortest scanning time for the wave to accomplish the shortest path in the network.
$T_{\text{scan\_l}}$	The longest scanning time for the wave to accomplish the longest path in the network.
$T_{\text{difference}}$	$T_{\text{difference}}=T_{\text{scan\_l}}-T_{\text{scan\_s}}$ .
$V_{\max }$	The maximum speed of the intrusive target.
$l_{\text{interval}}$	The shortest distance from the wave to the entrance point before we start a new round of scanning.
$T_{\text{move\_s}}$	The time for the target to accomplish the shortest distance in the network. ( $T_{\text{move\_s}}=l_{\text{shortest}}/v_{\max }$ , where $l_{\text{shortest}}$ is the shortest distance in the network.)
$P_{\text{move\_s}}$	The shortest path of the road network.
$n_{\text{scan\_s}}$	The number of sensors on the shortest scanning path.
R	Sensing circle's radius.

3.2. System Model

As shown in Figure 3, there are 4 entrance points and 4 protection points in the road network, and the target intrudes the sensing area and moves towards any protection point from any of the entrance points through any of the paths with the bounded maximum speed as $V_{\max }$ . A large number of sensors are deployed in the sensing area at random. When the target enters into the sensing area, system can guarantee successful detection of the target within a period of time and send the information to the server before the target reaches the protection point.

Figure 3

Sensor deployment in road networks.

There are lots of entrance points and protection points on the road network. When the system starts working with VISA, there are, actually, multiple scanning waves propagating from every protection point simultaneously. According to the working schedule of virtual scanning algorithm on road networks, there are three kinds of scanning wave: (1) waves that are originated from one protection point and their destinations are not any of the entrance points; (2) waves that are originated from one protection point and arrive at one entrance point without any branches; (3) waves that are originated from one protection point and arrive at many entrance points through variance of branches. These three kinds of waves are illustrated in Figure 4.

Figure 4

Types of virtual scan waves.

The scanning time differ from each other due to the different sensor density among road segments and different types of scan waves, which will lead to a big $T_{\text{difference}}$ :

$$\begin{array}{cc}& T_{\text{silent}}=\frac{P_{\text{move}\_s}}{v_{\max }}.\end{array}$$

(1)

According to formula (1), the network's silent time $T_{\text{silent}}$ is determined by $P_{\text{move}\_s}$ . If $P_{\text{move}\_s}$ is quite small and the $T_{\text{difference}}$ is large, the scan wave on the shortest scanning path arrive at the entrance point and sleep for $T_{\text{silent}}$ , while the other waves are still propagating.

As a result, the system needs to start a new round of scanning. The lifetime of the network can be computed as

$$\begin{array}{cc}& T_{\text{net}}=\frac{T_{\text{life}}}{w}\left(T_{\text{scan}\_s}+\frac{P_{\text{move}\_s}}{v_{\max }}\right),\end{array}$$

(2)

where w is the working time of the sensors and

$$\begin{array}{cc}& T_{\text{scan}\_s}=n_{\text{scan}\_s}w.\end{array}$$

(3)

AS we can see from (2) and (3), If $T_{\text{scan}\_s}$ is small, $n_{\text{scan}\_s}$ is small as well, and the lifetime of the whole system will be short. This is the drawback when VISA is applied to the road networks, although it performs well on single path. So the former algorithm should be improved.

3.3. Maximization of the Network's Lifetime

In the previous discussions, $n_{\text{scan}\_s}$ and $l_{\text{shortest}}$ play a decisive role in maximizing the lifetime of the road networks. $l_{\text{shortest}}$ , however, is unchangeable because it is determined by the road network. As a result, in order to maximize the life time of the road network, the only way is to optimize $n_{\text{scan}\_s}$ .

As shown in Figure 5, we can make the number of the sensor nodes on each path from the protection points to entrance points equivalent. Waves propagating from the protection points are transmitted to the entrance points through  m  nodes on each path when the network gets to start. It takes $t_0$ for all the waves to get to the entrance point. The network-wide silent duration can be determined by $T_{\text{silent}}=T_{\text{scan}\_s}/V_{\max }$ . And it will guarantee the equivalent scanning time on each path. We suppose that all the waves are type 2; the number of the nodes  m  on each path is $n/j$ ( $m=n/j$ ); the density of the nodes  ρ  is $n/j_1$ ( $j_1$ is the length of one of the paths). To balance all the waves' scanning time, the shorter the path is, the higher the density of the node will be. The network described above is optimized in terms of the lifetime. This idea can also be used to handle the network which is suffered from a big $T_{\text{difference}}$ . However, this method is based on the ideal deployment of the sensor nodes. Lots of human work is taken for high precision placement of the sensor nodes. So it is more theoretical rather than practical.

Figure 5

Maximization of network's lifetime.

3.4. Improvement on Road Network

In practical, there is always a big difference from one virtual scan wave's scanning time to another. To handle the issue, we propose twice deployment and node balance algorithm which consists of two phases (Figure 9). And we refer the former algorithm as random-deployment and the latter as demand-deployment phase. The sensor nodes are deployed at random during the random-deployment phase. During the demand-deployment phase, the nodes are increased in number and density to make the scanning time longer, and the scanning time will be balanced overall. As a result, the lifetime of the network will be optimized. A model is made to illustrate the scenario we described. As shown in Figure 6(a), there are two entrance points and two protection points.

Figure 6

Network with a big $T_{\text{difference}}$ .

We suppose that it takes at least 1 second for a node to detect the target. That means, when a node is passed, one second should be added to the scanning time. The shortest distance in this scenario is $E_1-P_1$ , and it takes at least 2 seconds for the target to arrive at the protection point.

As shown in Figure 6(b), two waves are propagating from the protection points to the entrance points. Their routes should follow the arrowhead. The time difference for the waves to get to entrance points is 3 seconds while the time for the target to get to the protection point is 2. It implicates that the system should begin another round of virtual scanning before it finished this round. Otherwise, there may be enough time for a target to get to the protection point which will make our system useless. So, it is important to adjust the number of the sensor nodes on each road segment to guarantee the successful detection of the target in our system.

As shown in Figure 7, to change the type of the two waves mentioned above to type two, we add 1 and 4 nodes to $P_2-B$ ,   $E_1-A$ segments, respectively. Clearly, the scanning time of the two waves will be both 8 seconds and the time difference is 0. It will guarantee successful detection of the target by our system. Meanwhile, it will maximize the life time of the road network.

Figure 7

The optimal state of road network.

What is more, to reduce our workload, we can only insert nodes in segment $E_1-A$ instead of in both $E_1-A$ and $P_2-B$ . As shown in Figure 8, the type of the two scanning waves will change to type 1 and type 2 and the scanning time will be 8 seconds and 7 seconds, respectively. The time difference of arrival is 1 second which guarantees the successful detection of the target. With this idea, we insert nodes to the segment according to the requirement of our network instead of all the segments. And this will reduce the workload and optimize the lifetime of the network remarkably.

Figure 8

A better solution.

Figure 9

Twice deployment and node balance algorithm.

To clarify, twice deployment and node balance algorithm is described as follows. There are  n  protection points and  n  entrance points on the road network. The  K  is the last intersection point from protection point to entrance point; that is, there is no intersection within all   $K\text{-}E$   segments. All that  K  points compose a set   $K=\{k_1,k_2,k_3,\dots ,k_n\}$ .

The procedure is as follows.

• (1)

Randomly deploy a lot of nodes in area from the protection points set to the entrance points set.

(2)

Initialize the network. We regard the k point as the last point of the route.

(3)

Compute the waves' scanning time. Waves propagate from j protection point to the entrance point. The system maintains a timer for each wave during their propagation. The timer is set to be 0 when the waves start to propagate. And the node k returns the information.

(4)

Deploy on the demand. To guarantee the equivalence of each wave's scanning time, the terminal utilizes the information provided by overall  k  points to compute the number of the nodes required to insert into each   $K_i-E_i$   segment.

During the random-deployment phase, sensor nodes are deployed at random among the whole area and we just insert nodes into a certain area during the last phase. That is why we call it the twice deployment and node balance algorithm.

After we optimize the algorithm, the lifetime of network $T_{\text{net}}$ is computed as follows:

$$\begin{array}{cc}& T_{\text{net}}=\frac{T_{\text{life}}}{\partial }=\frac{T_{\text{life}}}{w}\left(n_{\text{scan}\_s}w+\frac{{\text{l}}_{\text{shoretest}}}{v_{\max }}\right),\end{array}$$

(4)

where the $n_{\text{scan}\_s}$ is the number of the sensor nodes on the path with the shortest scanning time and $l_{\text{shoretest}}$ is the shortest distance between the entrance point and the protection point. Equation (4) implicates that the lifetime of the network is closely related to   $n_{\text{scan}\_s}$ . Before we optimize the VISA algorithm, all the sensor nodes are deployed at random which will result in an unstable lifetime of network. Despite the sensing hole of the road segment, in the worst case, that is,   $n=l_{\text{shortest}}/2r$ , the lifetime of the network is at minimum. However, the network with TDNB will increase the   $n_{\text{scan}\_s}$ , which lengthens the lifetime and stabilizes the performance of the network.

4. Performance Simulation

The simulation experiment of the system is conducted on the platform built by us. We constructed a virtual road network consisting of 4 protection points and 4 entrance points. Covering every corner of the networks, sensor nodes are deployed at random. The target is set to intrude the road network at the maximum of the bounded speed $V_{\max }$ at any time from any entrance point. The life time of the network ends after the target is detected. (Suppose that sensors can always successfully detect the target.) And different values of different parameters (such as n, w, and $V_{\max }$ ) were set to test the performance of the two algorithms, which are ASA and TDNB. Note that the two algorithms are both based on VISA.

The relevant simulation parameters required are shown in Table 2.

Table 2

Simulation parameters.

Parameters	Value
Shortest path	500 meters
The number of the nodes n	in the range ( $\mathrm{200,300},\dots ,1000$ ) with the default value at 200
Sensing circle's radius r	with a default value at 25 meters
Node's work time $T_{\text{work}}$	in the range ( $\mathrm{0.5,1},\dots ,10$ ) with the default value at 1 second
Energy of the entrance point E	with a default value at 50000
Energy of the node e	with a default value at 10
Maximum speed $V_{\max }$	in the range ( $\mathrm{5,10},\dots ,50$ ) with the default value at 25 m/s
Target's normal speed V	20 m/s
Node's wakeup times g	2 seconds
Repeating time	1000000 times

4.1. Simulation of the Network's Lifetime

n, $T_{\text{work}}$ , and $V_{\max }$ are selected as the 3 parameters in our network's lifetime simulation. The performance in the worst case of ASA (WVISA), the average cases of ASA (MVISA) and TDNB are compared in the experiment.

4.1.1. The Lifetime of the Network Influenced by the Node's Number

As revealed in Figure 10, with the increment of the node's number, the network's lifetime increases linearly, except for the worst case of ASA. Compared with it, TDNB increases rapidly with the increment of the nodes. When the node's number reaches 1000, the life time of the network with ASA and TDNB increases by 241.58% and 313.73%, respectively, compared with the case of 200 nodes. On average, the life time of the network with TDNB algorithm is increased by 66.13% compared with the network using ASA. And from the result of the simulation, the node's number has an equivalent influence on the network's lifetime on either a single path or the road networks. And the increment of the node's number makes a difference to the performance of the network. In ASA, the node's number on the shortest scanning time path is fixed, so it does not make any contribution to the network's lifetime. Generally speaking, TDNB is much better!

Figure 10

The lifetime of the network influenced by the node's number.

4.1.2. The Lifetime of the Network Influenced by the Node's Working Time

As shown in Figure 11, with the increment on the node's working time, it shows a down trend on the network's lifetime. When the node's working time is 1, the lifetime of network with ASA and TDNB algorithm is increased by 36% and 25.71%, respectively, compared with the case that the nodes' working time is 10. Generally speaking, the network's life time with TDNB is increased by 56.73% compared with ASA. And the shorter the working time is the better the network will perform.

Figure 11

The lifetime of the network influenced by the node's working time.

4.1.3. The Lifetime of the Network Influenced by the Maximum Speed

As shown in Figure 12, there is strong negative correlation between the network's lifetime and the target's maximum speed. When the target's maximum speed is 5 m/s, the life time of network with ASA and TDNB is increased by 69.23% and 60.54%, respectively, compared with the case that the nodes' speed is 50 m/s. The increment on the maximum speed results in a big decrement on the network's lifetime due to the negative correlation between the target's maximum speed and the network's silent time. So we need to choose a reasonable $V_{\max }$ .

Figure 12

The lifetime of the network influenced by the maximum speed.

5. Conclusions

The novelty of this paper can be concluded as follows. Compared with the road network surveillance algorithm before, this paper presents a novel algorithm which proved to have a better performance in intrusive target detection in road networks, through dividing the deployment of the sensor nodes into two phases instead of deploying all the sensors at one time. In the former phase, some of the sensors are deployed on the road at random. In the latter phase, the rest of the sensors are deployed on the last road segment to make the number of sensors on each path the same, which will be easier for people to handle in practical scenario. The network will have a prolonged lifetime due to the equivalence of the node's number after inserting nodes on the segments according to this algorithm. TDNB extends the node's lifetime remarkably compared with former algorithms. In short, TDNB meets the demand for persistent monitoring application without increasing the number of sensors in the road networks.