Optimal placement of barrier coverage in heterogeneous bistatic radar sensor networks

Abstract

Barrier Coverage is an important sensor deployment issue in many industrial, consumer and military applications.The barrier coverage in bistatic radar sensor networks has attracted many researchers recently. The Bistatic Radars (BR) consist of radar signal transmitters and radar signal receivers. The effective detection area of bistatic radar is a Cassini oval area that determined by the distance between transmitter and receiver and the predefined detecting SNR threshold. Many existing works on bistatic radar barrier coverage mainly focus on homogeneous radar sensor networks. However, cooperation among different types or different physical parameters of sensors is necessary in many practical application scenarios. In this paper, we study the optimal deployment problem in heterogeneous bistatic radar networks.The object is how to maximize the detection ability of bistatic radar barrier with given numbers of radar sensors and barrier’s length. Firstly, we investigate the optimal placement strategy of single transmitter and multiple receivers, and propose the patterns of aggregate deployment. Then we study the optimal deployment of heterogeneous transmitters and receivers and introduce the optimal placement sequences of heterogeneous transmitters and receivers. Finally, we design an efficient greedy algorithm, which realize optimal barrier deployment of M heterogeneous transmitters and N receivers on a L length boundary, and maximizing the detection ability of the barrier. We theoretically proved that the placement sequence of the algorithm construction is optimal deployment solution in heterogeneous bistatic radar sensors barrier. And we validate the algorithm effectiveness through comprehensive simulation experiments.

1 Introduction

Barrier Coverage is an important sensor deployment issue in many industrial, consumer and military applications, such as machine management, health care monitoring, battlefield surveillance [19], etc. Recent years have witnessed a trend that radar sensors have been increasingly deployed in guarding militarized zones, and monitoring hazards warehouse and frontier [2, 25, 28, 31]. Traditional passive sensors typically leverage on a disk sensing model. In contrast, BR sensors use a Cassini oval sensing model [5]. The sensing region of a BR sensor depends on the locations of both the BR transmitter and receiver, and is characterized by a Cassini oval. Moreover, since a BR transmitter (or receiver) can potentially form multiple BRs with different BR transmitters (or receivers, respectively), the sensing regions of different BRs are coupled, making the coverage of a BR sensor network highly non-trivial.

The barrier coverage problem of bistatic radar sensor network has been studied by many researchers recently. Gong et al. [9] studied the barrier coverage problem of bistatic radar sensor network. In [30], a minimum cost placement algorithm was developed for line barrier coverage. To improve quality, a belt with a predefined breadth is considered and covered by several same lines. In [3], the authors studied both fault tolerance and energy-saving issues combining the minimum cost placement of BR sensors for belt barrier coverage. In the above researches,they all assumed that radar sensors have the same physical parameters, and all BRs are homogeneous in their barrier coverage model.

However, heterogeneous deployment of sensors with different physical parameters is necessary in many practical application scenarios. In [12], the authors introduce a heterogeneous barrier-coverage in which guarantees that any penetration variation of intruder is detected by at least one sensor with different sensing capabilities. In [16], the author investigates the impact of heterogeneity on lifetime sensing coverage in heterogeneous sensor network. They use an optimal mixture of inexpensive low-capability sensors and expensive high-capability sensor to significantly extend the lifetime of network. In [11], the authors consider a hybrid barrier coverage application for heterogeneous sensor network to protecting critical facilities located inside the barrier region, and preventing illegal border crossings.The existing work on bistatic radar barrier coverage mainly focus on homogeneous radar sensor networks, while little effort has been made on barrier coverage formation in heterogeneous radar sensor networks.

In this paper, we study the optimal barrier coverage problem in heterogeneous bistatic radar sensor networks. Heterogeneous bistatic radar sensor network is composed of bistatic radar sensors with different physical parameters. We consider using bistatic heterogeneous radar sensors to optimal deploy a straight barrier with predefined length, and maximize the detection probability of the barrier. Firstly, we explore the optimal placement strategy of single transmitter and multiple receiver, and propose the pattern of aggregate deployment. Then we further study the optimal deployment sequences of multiple heterogeneous transmitters and receivers. Finally, we introduce an efficient greedy algorithm, which realize optimal barrier deployment of M heterogeneous transmitters and N receivers on a L length boundary, and achieving the maximizing of the detection probability of the barrier. We theoretically prove that the deployment of heterogeneous bistatic radar barrier is optimal. And we validate the algorithm effectiveness through comprehensive simulation experiments. To the best of our knowledge, this appears the first work to investigate the barrier coverage problem in heterogeneous bistatic radar sensor networks.The main contributions of this paper are summarized as follows.

• We investigate the Cassini oval sensing models and propose the optimal placement pattern of single transmitter and multiple receivers.

• We introduce the convergent deployment of heterogeneous transmitters and receivers. It can achieve the maximum coverage length under the condition to satisfy the predefined detecting SNR threshold.

• We propose the Greedy Selection Algorithm to realize the optimal deployment of coverage barrier with M heterogeneous transmitters and N receivers on a specific length barrier, and maximize the detection probability of an intruder crossing any part of the barrier.

• We theoretically prove that the convergent deployment sequence of heterogeneous bistatic radar achieves optimal coverage, and validate the effectiveness of the optimal deployment algorithm through comprehensive simulation experiments.

The rest of paper is organized as follows: Section 2 reviews the related work. Section 3 introduces the system model and problem description. Section 4 describes the optimal deployment method of heterogeneous straight barrier coverage. Simulation results are presented in Sections 5 and 6 concludes the paper.

2 Related work

Many barrier coverage problems have been widely studied in the last decade, and most of these studies are based on the passive disk coverage model [1, 4, 13, 14, 21, 23], or passive sector coverage model [6, 20, 26, 32]. The sensors sense and receive surrounding information passively, such as seismic sensor [24], acoustic sensor [22] and so on. Many scholars studied the optimal barrier coverage problem based on the passive sensing model, examples are the weak barrier coverage [17], strong barrier coverage [19] and K-barrier coverage [29].

In recent years,some researchers studied the radar sensor coverage problem [7, 8]. Being different from passive disk sensing, the radar sensor detects the target by the active transmitting radar signal, such as Doppler radar [8], bistatic radar [30]. These sensors have important application in security and target tracking [15, 18], and have become a important research problem in wireless sensor network recently. In [10], the authors consider the problem of deploying a network of homogeneous BRs in a region to maximize the worst-case intrusion detectability, which amounts to minimizing the vulnerability of a barrier. In [30], a minimum cost bistatic radar placement algorithm was developed for line radar barrier coverage to monitor intruders. To improve quality, a belt radar sensor barrier with a predefined breadth is considered and covered by several same lines. In [5], the authors discussed how to construct a static radar barrier on the smallest circumcircle of the area which is protected to minimize the cost. In [3], the authors study belt barrier coverage in bistatic radar sensor model. They propose a new deployment method that further reduces the total placement cost and then study the fault-tolerance issue and the energy-saving issue.

Aforementioned studies of sensor coverage are mainly focused on homogeneous sensor networks. However, cooperation among different types or different physical parameters of sensors is necessary in many practical application scenarios. In [16], the author investigate the impact of heterogeneity on lifetime sensing coverage in a single-hop direct communication model and a multi-hop communication model. In [27], the authors discuss the intrusion detection in the homogeneous and heterogeneous WSN.In [12], the authors introduce a heterogeneous barrier-coverage in which guarantees that any penetration variation of intruder is detected by at least one sensor with different sensing capabilities. They use disk sensing model. In [11], the authors consider a hybrid barrier coverage application for heterogeneous sensor network to protecting critical facilities located inside the barrier region, and preventing illegal border crossings.In the existing works on heterogeneous sensors coverage issues, they mainly use disk sensing model with different sensing capabilities, or different sensor types, such as electronic, optic and acoustic sensors.

However, the existing studies of bistatic radar sensor coverage are mainly focused on homogeneous radar sensor networks. They all assumed that bistatic radar have the same physical parameters in their radar barrier coverage model.While little effort has been made on barrier coverage formation in heterogeneous radar sensor networks. Hence, in this paper, we investigate the barrier coverage in heterogeneous bistatic radar sensor networks.In order to improve the detection probability of heterogeneous bistatic radar barrier, we study how to construct barrier coverage with predefined length using given number of transmitter and receivers to achieve maximized sensing capability.

3 Sensor model and problem definition

3.1 Bistatic radar sensor model

Different from traditional sensors, a bistatic radar sensor has both transmitters and receivers. A transmitter can be pair with one receiver to form a radar pair, and the transmitter and receiver are placed in different locations. The transmitter sends signals, and the receiver receives the signals when the signals are reflected by a target. Whether a target can be detected by a transmitter and receiver pair depends on SNR that the target reflects. It is shown in Figure 1.

Figure 1

The bistatic radar sensor

We use ∥AB∥ to denote the (Euclidean) distance between two points A and B, T_i and R_j to denote the locations of a transmitter node and of a receiver node, respectively. X denotes the location of the target. SNR obtained by the target X is

$$ SNR(X) =\frac{K}{{{\|{{T_{i}}X}\|}^{2}}{{\| {{R_{j}}X}\|}^{2}}} $$

(1)

where K denotes a bistatic radar physical parameter that reflects sensing characteristics of the T_iR_j pair and is determined by the transmitter. SNR obtained by a target is inversely proportional to the product of the square of the distance between the transmitter and receiver.

Definition 1 (Detection Threshold)

When SNR threshold of a BR pair is determined, its detection threshold is defined as

$$ C = \sqrt{K/SNR} $$

(2)

The detection threshold is the maximum of the product of the distance between the transmitter and the receiver when SNR threshold is determined. If the distance is exceeded, the target cannot be detected by the BR pair.

Definition 2 (Detection Value)

For a target x, the product of the distance between the transmitter T_i and x, and the distance between the receiver R_j and x is defined as the detection value of x obtained by T_iR_j bistatic radar pair.

$$ D(X) = \| {{T_{i}}x} \| \times \| {{R_{j}}x} \| $$

(3)

For a target x, if D(x) < C (C is the detection threshold when SNR is determined), x can be detected by this T_iR_j pair. Therefore, the sensing region of a BR pair can be characterized by a Cassini oval, as shown in Figure 2.

Figure 2

Detection range of bistatic radar sensor

A Cassini oval is a locus of points. The product of the distances to two fixed points (coci) is constant for any point on Cassini oval. If the detection value of the point on the Cassini oval locus is equal to C, the detection value of the points within the area of the Cassini oval locus is less than C, the area outside the locus is greater than C. That is, the area within the Cassini oval locus can be detected and the area outside the Cassini oval locus cannot be detected by this BR pair.

In a bistatic radar network, one transmitter paired with one receiver forms a BR pair. Theoretically, every transmitter (or receiver) can potentially pair with different receivers (or transmitters) to form multiple BR pairs.

3.2 Problem definition

In this paper, we mainly study the barrier coverage problem in heterogeneous bistatic radar sensor networks. The heterogeneous bistatic radar network is composed of M transmitters with different physical parameters and N receivers. We consider using bistatic heterogeneous radar sensors to deploy a straight barrier with length L,to achieve the optimal detection performance on the straight boundary. Every transmitter has different signal transmission frequency. All receivers are capable of receiving any frequency of radar transmitters’ signals. We assume that each receiver can only receive the specific frequency signal from a transmitter at final deployment, and each transmitter can send signal to multiple receivers.

As shown in Figure 3, the star represents the transmitter and the circle represents the receiver. We use different colors to represent transmitters with different parameters. Every receiver can select to receiving only one transmitter’s signal in heterogeneous single-receive bistatic radar barrier. We construct a heterogeneous bistatic radar barrier in which a number of transmitters with different sensing signal frequencies and a number of receivers form a fixed length bistatic radar barrier to detect cross-barrier intruder. We provide some definitions as follows.

Figure 3

Heterogeneous single-receive bistatic radar barrier

Definition 3 (Placement sequence)

A placement sequence is an sequence of all the radar nodes on the line from left to right.

The radar transmitters in the Figure 4 have different phisical parameters , but the receivers are of the same type. The placement sequence contains two aspects: 1) the permutation of the sensor nodes (transmitters and receivers) ; 2) the space between every two adjacent radar nodes.

Figure 4

Placement sequence sketch map

Definition 4 (SNR of A Point)

For any point x on the barrier I_i, it may attained multi-SNRs by multiple BR pairs. We use the maximum SNR as this point’s SNR.

$$ SNR(x) = \underset{{T_{i}} \in T,{R_{j}} \in R}{\max} \left\{ {\frac{{{K_{i}}}}{{{{\| {{T_{i}}x} \|}^{2}}{{\| {{R_{j}}x} \|}^{2}}}}} \right\} $$

(4)

Where T is the transmitter set and R is the receiver set.

Definition 5 (Vulnerability)

The vulnerability V (I_i) of a barrier I_i is the minimum SNR of all points in I_i.

$$ V({I_{i}}) = \underset{{x_{i}} \in X}{\min} \{ SNR({x_{i}})\} $$

(5)

Where the X is the set of all points in I_i.

As to the optimal barrier deployment model on heterogeneous bistatic radar, we give a formal description of the problem as follows.

Problem 1

The length of barrier I in Figure 3 is L, there are M transmitters that have different physical parameters and N receivers. Our goal is to find the optimal placement sequence. The optimal placement sequence has the maximum vulnerability of barrier I, namely, the barrier has the best performance of intrusion detection.

The Problem-1 is defined as follows.

$$ \begin{array}{l} \max \{ V(I)\} \\ sub{\mathrm{ to }}\left\| {{{\mathrm{H}}_{\mathrm{l}}}{H_{r}}} \right\| = L \end{array} $$

(6)

Where H_l and H_r denote the left endpoint and right endpoint of barrier I, respectively.

We can formulate a related Problem-2 of Formula (7) from Formula (6).

$$ \begin{array}{@{}rcl@{}} &&\max \{ \left\| {{H_{l}}{H_{r}}} \right\|\}\\ &&{\mathrm{sub to V}}(I) \ge {\mathrm{r}} \end{array} $$

(7)

Problem 2

As it is described by Formula (7) , it is about how to find the optimal placement sequence for maximum the barrier’s length when of SNR of I’s vulnerability is not less than r. If we can solve Formula (7), we can also solve Formula (6) by the bisection search in Algorithm 1.

The function optimal − algorithm(r) in the code of Algorithm 1 is the algorithm to solve Formula (7).

In order to solve the Formula (7) , we need to determine.

• 1. The permutation of the transmitters and the receivers in the optimal placement sequence.

• 2. The corresponding transmitter of every receiver is determined.

• 3. The distance between every pair of adjacent radar nodes.

4 Model construction and Algorithm analysis

4.1 Basic coverage pattern

Every receiver can be paired only with one transmitter. Every transmitter has only one receiver set that only receive the signals from this transmitter no matter what final optimal placement sequence is. Therefore, the area covered by a transmitter and its corresponding receiver set is called basic coverage pattern, as shown in Figure 5.

Figure 5

Basic coverage pattern

4.2 Optimal placement of single transmitter and multiple receivers

We study the following problem before solving Problem-2.

Problem 3

For any one transmitter T_i, given n{n = 1,2,3,..., N} receivers, we will find the optimal placement sequence to get the maximum cover length when SNR threshold is not less than r.

$$ \max \{ {\text{cover}}(S_{{T_{i}}}^{n})\} $$

(8)

Where $S_{{T_{i}}}^{n}$ denotes the placement sequence and it consists of transmitter T_i and n receivers. ${\text {cover}}(S_{{T_{i}}}^{n})$ denotes the length covered by placement sequence $S_{{T_{i}}}^{n}$.

For transmitter T_i, we get its detection range by Formula (2), denoted by C_i when SNR threshold is r. That is, the target x cannot be detected by the T_iR_j pair when the product of the distance between the target and the transmitter T_i and the distance between the target and the receiver R_j exceeds.

For Formula (8) , we consider this situation first: the receivers are only deployed at one side of the transmitter.

When n = 1, there is only one receiver, as shown in Figure 6.

Figure 6

Placement interval when n = 1

Let d₁ = ∥T_iR₁∥, the minimum SNR point between $\overline {{T_{i}}{R_{1}}}$ is the midpoint of the $\overline {{T_{i}}{R_{1}}}$, the detection value of this point is $D(O) = \frac {{{d_{1}}}}{2} \times \frac {{{d_{1}}}}{2}$. We assume D(O) = C_i, and obtained ${d_{1}} = 2\sqrt {{C_{i}}}$, the coverage range is the longest (Appendix, Proof 1).

When n = 2, there are two receivers, as shown in Figure 7.

Figure 7

Placement interval when n = 2

Where ∥T_iR₁∥ = d₁, let d₂ = ∥R₁R₂∥. The vulnerability in $\overline {{R_{1}}{R_{2}}}$ is the midpoint of $\overline {{R_{1}}{R_{2}}}$, and its detection value is $D(O) = \frac {{{d_{2}}}}{2} \times \left ({\frac {{{d_{2}}}}{2} + {d_{1}}} \right )$, let $\frac {{{d_{2}}}}{2} \times \left ({\frac {{{d_{2}}}}{2} + {d_{1}}} \right ) = {C_{i}}$, and d₂ is solved. namely, when ∥T_iR₁∥ = d₁, ∥R₁R₂∥ = d₂, the coverage range is the longest (Appendix, Proof 2).

We obtain a formula to calculate the distance between R_k− 1 and R_k when n = k, k = 3,4,5....

$$ \frac{1}{2}{d_{k}} \times \left( {\frac{1}{2}{d_{k}} + \sum\limits_{i = 1}^{k - 1} {{d_{i}}} } \right) = {C_{i}} $$

(9)

According to formula (9), we obtain every value of d_i{i = 1,2,3...}. If we deploy receivers at one side of a transmitter according to the value d_i{i = 1,2,3...}, the range covered by the placement sequence is the longest. Therefore we obtained the optimal placement interval array d[] = {d₁, d₂, d₃,...d_n} of transmitter T_i. It is a decline array. d_i continues to decrease, the coverage range after every receiver deployed decreases when i increases, as shown in Figure 8.

Figure 8

Single side maximum spacing placement for single transmitter

We study the problem that deploys the receivers at one side of the transmitter for maximizing the coverage range in the previous studies. After that, we consider the case of deploying receivers on both sides of the transmitter. We deploy receivers on both sides of the transmitter symmetrically so that the of numbers of receivers on both sides are the same, or there is one more receiver in one side than that in the other side. And the receiver deployment interval in each side belongs to the optimal interval array (Appendix, Proof 3) . We find the deployment method to solve Formula (8), as shown in Figure 9.

Figure 9

Maximum interval deployment and coverage set for single transmitter

4.3 Optimal placement for multiple heterogeneous transmitters and multiple receivers

In the previous sections, we have solved the problem-3: there are one transmitter and n receivers, the placement sequence for maximizing the coverage range is obtained when SNR threshold is determined. But if there are more than one transmitter, and every transmitter has several receivers. It is a problem to obtain the placement sequence for maximizing the coverage range. Details are as follows.

Problem 4

There are m transmitters {T₁, T₂,...T_m}, and the number of receivers that every transmitter owns is {K₁, K₂,...K_m}. It is a problem to find the optimal placement sequence for maximizing the cover length on the line when SNR threshold is r.

Definition 6 (Converge deployment)

For a placement sequence, if every transmitter and its receiver set (its receiver set only receives its signals) are deployed together, it means there is no other transmitter(s) or receiver(s) among them, and the deployment of every transmitter and its receivers satisfies the maximum interval deployment. We call it a converge structure. In a converge structure, two adjacent basic coverage patterns clung to each other. We call this deployment strategy the converge deployment.

As shown in Figure 10, in the converge deployment, the black solid ellipse and the red dotted ellipse are arranged tightly on the left and right sides of the line barrier respectively. In Non-converge deployment, as shown in Figure 11, the black solid ellipse and the red dotted ellipse in the fence are arranged separately from each other.

Figure 10

Converge deployment

Figure 11

Non-converge deployment

Theorem 1

The optimal placement sequence of Problem-4 satisfies the converge deployment.

Proof

The Proof of Theorem 1 is in Appendix. □

If a placement sequence satisfies the converge deployment, every basic coverage pattern has the longest coverage length. Because there is no overlap among basic coverage patterns, the entire placement sequence gained is the longest coverage length.

Theorem 2

The length of range covered by a placement sequence that satisfies the converge deployment strategy are all equal.

Proof

The Proof of Theorem 2 is in Appendix. □

According to Theorem 2, when a placement sequence satisfies the converge deployment strategy, the order of basic coverage pattern does not matter, so the coverage length that the placement sequence covers is not influenced. Therefore, if we find the placement sequence that satisfied the converge deployment strategy, Problem-4 is solved.

From the definition of converge structure, there is no gap in the converge structure. If an intruder crosses the barrier which is formed by a placement sequence that satisfies the converge deployment strategy, the intruder is detected.

4.4 Optimal placement sequence algorithm in heterogeneous bistatic radar sensor

We denote the optimal placement sequence to solve Problem-2 by S_op. It contains M transmitters {T₁, T₂...T_M}, and the numbers of receivers that every transmitter owns are {K₁, K₂,...K_M}, and $\sum \nolimits _{i = 1}^{M} {{K_{i}} = N}$. From Problem-4, S_op satisfies the converge deployment strategy. In order to solve Problem-2, we need to determine the value of K_i.

• 1. every T_i’s optimal interval array dⁱ[] in S_op is computed according to the maximum placement interval deployment.

• 2. the greedy − searchalgorithm is proposed to determine the number of receivers that every transmitter matched.

The greedy − searchalgorithm is described as follows: before a receiver is assigned, an iteration is run. In the iteration, every transmitter gets the maximal interval in all optimal interval array. Then the receiver is assigned to this transmitter. This interval is deleted in its optimal interval array. This process is repeated until every receiver is assigned.

In the above codes, the array p[] records the number of receivers that every transmitter has already owned. Line 3 ∼ 5 computes every transmitter’s optimal interval array dⁱ[]{i = 1,2...M}. Line 8 ∼ 12 selects the transmitter that has the maximal interval. The number of receivers of every transmitter is determined. These radars are deployed according to converge deployment strategy. The optimal placement sequence is obtained.

5 Simulation results

The simulation experiments are performed on Windows 10 system; Programming language is C++ and Python. The algorithms are realized in C++ language. And the visualization of deployment results is realized in Python language. We study the deployment of M transmitters that have different physical parameters and N receivers to form a barrier in a straight line with a length of L, and maximize the vulnerability in the barrier. We propose the optimal deployment strategy, OPT. In order to validate the performance of OPT, we compared with two deployment methods in simulation experiments.

Method1: As shown in Figure 12, we compute the square root of every transmitter’s physical parameters: ${q_{i}} = \sqrt {{K_{i}}} \{ i = 1,2...M\}$. Then we determine every transmitter’s coverage length and the number of receivers according to the value of q_i in proportion. We combine every 2 receivers into a group when assigning the number of receivers. Every transmitter has the same or nearly the same number of receivers. For every T_i, we assume that it has N_i receivers and the length of coverage range is L_i, and we determine the location of every node in the following way: T_i is deployed in the midpoint of L_i, and N_i/2 receivers are deployed in both sides of T_i. The interval of deployment is half of the former one.

Figure 12

Determine placement locations according to geometric ratio of q_i in method 1

As shown in Figure 13, we obtain x by computation, and the location of every receiver can be determined. Therefore, we finally obtain the locations of every transmitter and every receiver.

Figure 13

Deployment sequences for menthod 1

Method2: As shown in Figure 14, the receivers are deployed in the straight line uniformly. Every transmitter’s coverage length is determined in proportion with the value of q_i. These coverage ranges are placed in Line L. Every transmitter in the coverage range is deployed.

Figure 14

Deployment sequences for menthod 2

In the experiment, we investigate the influence of the number of transmitters, receivers, barrier length on the detecting performance. The detecting capability of bistatic radar barrier is determined by the minimum detecting SNRs of all point on the barrier’s boundary, called as the barrier’s vulnerability.

We assume the length of barrier L = 1000m. When the number of transmitters is fixed (M = 20), SNR of the barrier’s vulnerability is increase when the number of receivers is increased. As shown in Figure 15, our OPT deployment method has higher detecting performance compared with method 1 and method 2.

Figure 15

The number of transmitters M = 20. When the number of receivers N is different, the comparison of SNR of barrier’s weaknesses in the three schemes

When the number of receivers is fixed (N = 100), SNR of the barrier’s vulnerability is increased when the number of transmitters is increased. As shown in Figure 16, our OPT deployment method also has higher detecting performance compared with method 1 and method 2.

Figure 16

The number of receivers N = 100. When the number of transmitters M is different, the comparison of SNR of barrier’s weaknesses in the three schemes

In Figure 17, we use the same set of sensors, and we find that the effect of OPT is always better than the other two methods. When the barrier’s length increases,the interval spaces between transmitters and receivers increase, the detectiong vulnerability will become very small, and the performance of our method will become closer to method 1 and method 2. As shown Figure 18, when we zoom in on local charts in the case of L ≥ 1600m, the performance of OPT was still better than the other two methods.

Figure 17

The number of transmitters M = 20, the number of receivers N = 100. When the barrier length L is different, the comparison of SNR of barrier’s weaknesses in the three schemes

Figure 18

When the barrier length L ≥ 1600m, the comparison of SNR of barrier’s weaknesses in the three schemes

6 Conclusions

Barrier Coverage is an important sensor deployment issue in many industrial, consumer and military applications. In this paper, we studied optimal barrier coverage in the heterogeneous bistatic radar barrier sensor networks. The object is how to maximize the detection ability of bistatic radar barrier with given numbers of radar sensors and barrier’s length. We proposed the optimal placement strategy of single transmitter and multiple receiver, and proved the optimal pattern of aggregate placement. Then we proposed the optimal deployment strategy of multiple heterogeneous transmitters and receivers and proved the optimal placement sequences of radar sensors. Finally, we design an efficient greedy algorithm, which realize optimal barrier deployment of M heterogeneous transmitters and N receivers on a L length boundary, and maximizing the detection ability of the barrier. We validated the algorithms’ effectiveness through theoretical analysis and comprehensive simulation experiments.

Appendix

Proof

(Proof 1) When a placement sequence consist of one transmitter and one receiver, the coverage length reaches the maximum when the distance between them is $2\sqrt {{c_{i}}}$.

Let d₁ = ∥T_iR_j∥, we consider three possible cases as follows.

• Case 1: when ${d_{1}} < 2\sqrt {{c_{i}}}$, the coverage range is presented in Figure 19.

  We can divide the range into 3 parts: part $\overline {A{T_{i}}}$, part $\overline {{T_{i}}{R_{j}}}$, part $\overline {{R_{j}}B}$. Let ∥AT_i∥ = ∥R_jB∥ = x, because of ∥AT_i∥ ×∥AR_j∥ = c_i, then x (x + d₁) = c_i, so the length of coverage range is ${L_{1}} = \sqrt {{d_{1}^{2}} + 4{c_{i}}}$.

• Case 2: when ${d_{1}} = 2\sqrt {{c_{i}}}$, the coverage range is presented in Figure 20.

  Similar to Case 1, the length of coverage range is ${L_{2}} = \sqrt {{d_{1}^{2}} + 4{c_{i}}}$, then L₂ > L₁, because of $d_{1}^{(2)} > d_{1}^{(1)}$.

• Case 3: when ${d_{1}} > 2\sqrt {{c_{i}}}$, the coverage range is presented in Figure 21.

Figure 19

Detection area when ${d_{1}} < 2\sqrt {{c_{i}}}$

Figure 20

Detection area when ${d_{1}} = 2\sqrt {{c_{i}}}$

Figure 21

Detection area when ${d_{1}} > 2\sqrt {{c_{i}}}$

Because $d_{1}^{(3)} > d_{1}^{(2)}$, then ∥AT_i∥⁽³⁾ = ∥R_jD∥⁽³⁾ < ∥AT_i∥⁽²⁾ = ∥R_jB∥⁽²⁾, and ∥T_iB∥⁽³⁾ = ∥R_jC∥⁽³⁾ < ∥T_iO∥⁽²⁾ = ∥R_jO∥⁽²⁾, so we get that L₃ = 2 (∥AT_i∥⁽³⁾ + ∥T_iB∥⁽³⁾) < L₂ = 2 (∥AT_i∥⁽²⁾ + ∥T_iO∥⁽²⁾). □

Proof

(Proof 2) Optimal deployment interval when the number of deployed receivers is n = 2, as shown in Figure 22.

Figure 22

Optimal deployment interval when n = 2

As shown in Figure 21, let d₁ = ∥T₁R₁∥, d₂ = ∥R₁R₂∥. When ${d_{1}} = 2\sqrt {{c_{i}}}$ and d₂ is the solution of $\frac {1}{2}{d_{2}} \times \left ({\frac {1}{2}{d_{2}} + {d_{1}}} \right ) = {c_{i}}$, the coverage length of the placement sequence is the longest. It is because the following discussion.

When ∥R₁R₂∥ < d₂, it is shown in Figure 23.

Figure 23

Deployment situation when $\left \| {{R_{1}}{R_{2}}} \right \| < {d_{2}}$

Here, compared with Figure 23, ∥T₁D^∗∥ < ∥T₁D∥¹ (the superscript 1 denotes Figure 23), and ∥AT₁∥ remains unchanged, therefore the coverage length of the placement sequence becomes shorter.

When ∥R₁R₂∥ > d₂, it is shown in Figure 24.

Figure 24

Deployment situation when $\left \| {{R_{1}}{R_{2}}} \right \| > {d_{2}}$

∥DE∥ < ∥CD∥¹ (the superscript 1 denote the Figure 22), so the coverage length turns shorter compared with Figure 22. Therefore, if we deploy two receivers on one side of a transmitter, the coverage length is longest when ∥T₁R₁∥ = d₁ and ∥R₁R₂∥ = d₂. □

Proof

(Proof 3) When a placement sequence consists of one transmitter and n receivers, the coverage length is longest when we deploy the n receivers on both sides of the transmitter equally and the deploy intervals satisfied the optimal deployment intervals.

As shown in Figure 25, we assume that we have two deployment strategies: strategy1 and strategy2.

Figure 25

Two deployment strategies

strategy1: |left₁ − right₁| ≤ 1, left₁ + right₁ = n

strategy2: |left₂ − right₂| > 1, left₂ + right₂ = n

left denotes the number of receivers that are deployed on the left of the transmitter, and the right denotes the number of receivers that are deployed on the right of the transmitter.

In Proof 2, if we deploy receivers on one side of the transmitter, the coverage length is the longest if the deployment intervals are the optimal deployment intervals. Therefore, we assume that the deployment intervals in strategy1 or strategy2 all satisfy the requirement of the optimal deployment intervals.

For convenience, we assume left₁ ≤ right₁, left₂ ≤ right₂, we get left₁ > left₂, right₁ < right₂ and left₁ − left₂ = right₂ − right₁. The optimal interval array d[] is a decreasing array, we assume.

sum₁ = d[left₂] + d[left₂ + 1] + ... + d[left₁]

sum₂ = d[right₁] + d[right₁ + 1] + ... + d[right₂]

Therefore, sum₁ > sum₂, and the range from left₂ to right₁ is a shared part of both strategy1 and strategy2. So the coverage length obtained from strategy1 is longer than that from strategy2. □

Proof

(Theorem 1) There are two placement sequences, S₁ and S₂. S₁ satisfies the converge deployment and S₂ don’t satisfies the converge deployment.

Our proof is reduction ad absurdum. We assume S₂ is the optimal placement sequence. Its coverage range covered is the longest. Because S₂ doesn’t satisfy the converge deployment, there is at least one transmitter T_i, the deployment sequence with this transmitter (and its receivers set) doesn’t satisfy the optimal interval deployment. However, S₁ satisfies the converge deployment, the deployment sequence with this transmitter (and its receivers set) satisfies the optimal interval deployment. We obtain the following expression from section 4. 2, ${\text {cov}} er({~}^{1}S_{{T_{i}}}^{{K_{i}}}) > {\text {cov}} er({~}^{2}S_{{T_{i}}}^{{K_{i}}})$ and ${\text {cov}} er({~}^{1}S_{{T_{j}}}^{{K_{j}}}) > {\text {cov}} er({~}^{2}S_{{T_{j}}}^{{K_{j}}}),j = 1,2,...M{\mathrm { and j}} \ne {\mathrm {i}}$. K_i denotes the number of receivers in T_i’s receivers set. ${~}^{1}S_{i}^{{K_{i}}}$ denotes the placement sequence with T_i and its K_i receivers. Therefore, ${\text {cov}} er({S_{1}}) > {\text {cov}} er({S_{2}})$. S₂ is not set up for the optimal placement sequence. □

Proof

(Theorem 2) If there are two placement sequences with the same transmitter parameters of the, and the number of receivers owned by each transmitter is the same. If both placement sequences satisfy the converge deployment, that is to say they have the same basic coverage patterns, therefore their coverage ranges are equal. We give an example to illustrate this conclusion, It is shown in Figure 26.

Figure 26

Comparison of different deployment sequences satisfying converge deployment structure

Both placement sequences are composed of the same three basic coverage patterns. But the arrangement sequences of these three basic coverage patterns are different, Therefore they are two different placement sequences. But the coverage range covered by each basic coverage patterns of the two placement sequences correspond are equal. The coverage range covered by these two placement sequences are equal. □