arXiv:1206.1355v1 [cs.

NI] 6 Jun 2012

A Coverage Theory of Bistatic Radar Networks:

Worst-Case Intrusion Path and Optimal Deployment

ABSTRACT
Continuing advances in radar technology are driven both
by new application regimes and technological innovations.
A family of applications of increasing importance is detection of a mobile target intruding into a protected area, and
one type of radar system architecture potentially well suited
to this type of application entails a network of cooperating
radars. In this paper, we study optimal radar deployment for
intrusion detection, with focus on network coverage. In contrast to the disk-based sensing model in a traditional sensor
network, the detection range of a bistatic radar depends
on the locations of both the radar transmitter and radar
receiver, and is characterized by Cassini ovals. Furthermore, in a network with multiple radar transmitters and receivers, since any pair of transmitter and receiver can potentially form a bistatic radar, the detection ranges of different bistatic radars are coupled and the corresponding
network coverage is intimately related to the locations
of all transmitters and receivers, making the optimal deployment design highly non-trivial. Clearly, the detectability of an intruder depends on the highest SNR received by
all possible bistatic radars. We focus on the worst-case intrusion detectability, i.e., the minimum possible detectability along all possible intrusion paths. Although it is plausible to deploy radars on a shortest line segment across the
field, it is not always optimal in general, which we illustrate
via counter-examples. We then present a sufficient condition
on the field geometry for the optimality of shortest line deployment to hold. Further, we quantify the local structure
of detectability corresponding to a given deployment order
and spacings of radar transmitters and receivers, building on
which we characterize the optimal deployment to maximize
the worst-case intrusion detectability. Our results show that
the optimal deployment locations exhibit a balanced structure. We also develop a polynomial-time approximation algorithm for characterizing the worse-case intrusion path for
any given locations of radars under random deployment.

Keywords
bistatic radar networks, network coverage, optimal deployment, worst-case intrusion path

c4
c3
c2

c1

c1

Figure 1: Bistatic radar SNR contours as Cassini

ovals with foci at radar transmitter T and radar
receiver R for distance products: c1 < c2 < c3 <
c4 .

1. INTRODUCTION
1.1 Motivation
An active radar system consists of a collection of
transmitters and receivers in which transmitters emit
RF signals and the receivers capture signals resulting
from scattering of the transmitted signals reflected by
objects of interest (targets). A monostatic radar is one
in which a single transmitter and single receiver are collocated. A bistatic radar is also comprised of a single
transmit-receive pair, but the transmitter and receiver
are at different locations. Multistatic radar refers to a
configuration that consists of multiple receivers at different locations. Although physical-layer issues in radar
have been extensively studied [1], very limited attention has been paid to radar network design [24]. Notably, [2] considered a network of monostatic radars,
and [3, 4] studied a multistatic radar with one transmitter. We are thus motivated to consider a network of
multiple radar transmitters and receivers where any pair
of transmitter and receiver can form a bistatic radar.
Unlike traditional passive sensors, one salient feature
of radar sensing is that it actively emits signals to illuminate the target. Further, radar technology provides
superior penetration capability by using radio waves.
Worth mentioning is that the cost of radars can be much
higher than traditional sensors.
The problem of detecting intrusion into a protected

area, across a border or security perimeter, is of increasing interest for numerous applications, and has great potential in several regimes of growing importance, such
as border monitoring, industrial and airport security,
and drug interdiction. Worst-case coverage [5] is a common criterion of efficacy in intrusion detection that has
been applied extensively in the context of sensor networks [69]. It is intimately related to the minimum
possible detectability of an intruder (target) traversing a monitored field. In a bistatic radar network, the
worst-case coverage is quite different and more difficult to quantify than traditional sensor networks, because 1) departing from the disk-based sensing range
of a traditional sensor, the detection range of a bistatic
radar depends on the locations of both radar transmitter and receiver and is characterized by the Cassini oval
(in scenarios where intruder detectability is dominated
by SNR). Formally, a Cassini oval is a locus of points
for which the distances to two fixed points (foci) have
a constant product (as illustrated in Figure 1); 2) the
sensing ranges of different bistatic radars are coupled
with each other, since each transmitter (or receiver) can
pair with other receivers (or transmitters) to form multiple bistatic radars, indicating that its location would
impact multiple bistatic radars.

1.2 Summary of Main Contributions

We first rigorously quantify the intrusion detectability and network coverage attainable by a bistatic
radar network, while taking into account the complication that each pair of transmitter and receiver
can potentially form a bistatic radar. We then
study the worst-case coverage under deterministic deployment, aiming to find optimal deployment
locations of radar transmitters and receivers such
that the worst-case intrusion detectability is maximized. We present a sufficient condition on the
field geometry under which it is optimal to deploy radars on a shortest line segment across the
field, which we refer as a shortcut barrier. The
line barrier appears intuitive but does not hold for
arbitrary field geometry, for which we give counterexamples. Further, when radars are deployed on
the shortcut barrier, the worst-case intrusion detectability turns out to be the vulnerability of the
shortcut barrier, which is the minimum detectability of all points on it.
A main thrust of this study is devoted to characterizing the optimal deployment locations of radars
on the shortcut barrier to minimize its vulnerability. Since the optimization problem is neither
differentiable nor convex, it is highly non-trivial
to solve. We first quantify the local structure of
detectability corresponding to a given deployment

order and spacings along a shortcut barrier. Then,

for a given deployment order, we establish the existence and optimality of balanced deployment spacings required to attain the minimum vulnerability.
Next, we derive sufficient conditions for an optimal deployment order, and characterize the corresponding optimal deployment orders. Our findings reveal that the optimal deployment locations
exhibit a balanced structure. Furthermore, under
the optimal deployment, it suffices for a receiver
to form at most two bistatic radars to guarantee
the optimal coverage quality, under the condition
that the number of receivers is no less than that
of transmitters (which is often the case since radar
transmitters are more costly).
We also study the worst-case coverage under random deployment, and quantify the worst-case intrusion path for any given deployment of radars.
In particular, by developing a novel 2-site Voronoi
diagram with graph search techniques, we design
an algorithm to find an approximate worst-case intrusion detectability, where the approximation error can be made arbitrarily small. The algorithm
is shown to have polynomial-time complexity.
We believe that the studies we initiated here on bistatic
radar networks scratch only the tip of the iceberg. There
are still many questions remaining open for the design
of a networked radar system.
The rest of this paper is organized as follows. Section 2 introduces the model of worst-case coverage for
the bistatic radar network. In Section 3, we characterize the optimal deployment of radars for maximizing
the worst-case detectability. Section 4 presents an efficient algorithm for finding an approximate worst-case
detectability given arbitrary locations of radars. Section 5 provides the evaluation results. Related works
are discussed in Section 6. The paper is concluded in
Section 7.

2. SYSTEM MODEL
Basic Setting. We consider a bistatic radar network
deployed in a field of interest F . The field F is a
bounded and connected region enclosed by four curves:
a left boundary Fl , a right boundary Fr , an entrance
side, and a destination side (see Figure 2). Note that
we allow the boundary curves of the field to be arbitrary. An intruder (target) can traverse through F
along any intrusion path P F from a point on the
entrance to a point on the destination. Specifically, the
bistatic radar network consists of M radar transmitters
Ti T , i M , {1, , M } and N radar receivers
Rj R, j N , {1, , N }. We assume that each
pair of transmitter and receiver can potentially form
a bistatic radar. We further assume that orthogonal

transmissions are used for interference avoidance. For

convenience, we also use Ti or Rj to denote the location
(point) of node Ti or Rj , respectively.
Bistatic radar SNR and Cassini Oval. For a bistatic
radar, the received SNR for a target is given by
K
(1)
SNR =
kT Xk2kRXk2

where kT Xk and kRXk denote the transmitter-target

and receiver-target distances, respectively, and K denote bistatic radar constant which reflects physical-layer
system characteristics, such as transmitting power, radar
cross section, and transmitter/receiver antenna power
gains. For ease of exposition, we assume the bistatic
radar constant is the same, and our study on homogeneous bistatic radars here will serve as a major step for
studying the heterogenous case. Given a bistatic radar,
the SNR contours are characterized by the Cassini ovals
with foci at the transmitter and receiver. We use CT,R (c)
to denote the Cassini oval with foci at points T and R
for constant distance product c.
Intrusion Detectability and Network Coverage. Let
kabk denote the (Euclidean) distance between two points
a and b. It follows from (1) that the received SNR by
a bistatic radar {Ti , Rj } from a target at some point
p is determined by the distance product kTi pkkRj pk.
Then the detectability of a point p is quantified by the
minimum distance product from p to all bistatic radars,
denoted by
I(p) ,

min

Ti T ,Rj R

kTi pkkRj pk.

(2)

Observe from (2) that the detectability increases when

I(p) reduces, and vice versa. The detectability of an
intruder is captured by the detectability of its intrusion
path P , which is the maximum detectability of all points
on P , denoted by
B(P ) , min I(p).
pP

(3)

From the radar networks perspective, in the worst case,

the intruder traverses through F along an intrusion path
P such that B(P ) is maximized. We refer this path
and its detectability as the worst-case intrusion path
and the worst-case intrusion detectability (WID), respectively.

3.

Fr

(4)

Fl
H

Fr

entrance

H
(b)

entrance

(a)

Figure 2: (a) H is a shortcut barrier; (b) H is a

shortest barrier but not a shortcut barrier since
H is shorter than H; the optimal deployment
may not be on H.
The above problem is highly non-trivial in general since
the boundaries of field F can be arbitrary. In particular,
we are interested in the line-based deployment scheme in
which radars are deployed along a line which is simple
to implement in practice. Further, we will show that
it is optimal under some mild condition on the field
geometry. To the best of our knowledge, the optimality
of line-based deployment for worst-case coverage has not
been studied in literature.

3.1 Shortcut Barrier-based Deployment

We need the notion of barrier to establish our results on the line-based deployment. Given any c > 0,
the detection range of a bistatic radar {Ti , Rj }, denoted by ATi ,Rj (c), is the region enclosed by the Cassini
oval CTi ,Rj (c) such that kTi pkkRj pk c for all p
ATi ,Rj (c). The detection range of the bistatic radar
network, denoted by A(c), is the union of the detection
ranges of all the bistatic radars. A barrier is a curve in
the field F connecting the left boundary Fl and right
boundary Fr such that any intrusion path through F
intersects with the barrier. The worst-case coverage is
intimately related to the notion of barrier as given in
the next property. The proof is based on an argument
similar to the growing disks in [7] and is omitted here.
Property 1. The worst-case intrusion detectability
B(P ) is equal to the smallest value of c such that there
exists a barrier in the networks detection range A(c).
We define the vulnerability of a barrier U as the minimum detectability of all points in U , denoted by
pU

We consider both deterministic deployment and random deployment scenarios, in the same spirit as the
arbitrary/random network models in the seminal work
by Gupta and Kumar [10]. In the deterministic deployment case, our goal is to find optimal deployment
locations of radar nodes (i.e., M transmitters and N
receivers) in F such that WID is maximized, i.e.,
minimize B(P )

Fl

destination

Q(U ) , max I(p).

DETERMINISTIC DEPLOYMENT

Ti F,Rj F

destination

(5)

Intuitively, we expect to attain the best coverage quality by deploying radars along a shortest barrier which
an intruder must pass through. We make the following
assumption on the geometry of field F .
Assumption 1. There exists a shortest line segment
H connecting Fl and Fr such that H F .
Although a shortest line segment connecting Fl and Fr
always exists, it is critical to assume that it lies in the

field F (see Figure 2). We refer such an H as the shortcut barrier (SCB) and let h denote its length. In other
words, h is the shortest distance between a point in Fl
and a point in Fr . Note that a shortcut barrier is always
a shortest barrier that has the shortest length among all
barriers, but the converse is not true (as illustrated in
Figure 2). Assumption 1 captures a large class of field
geometry, e.g., any F of convex shape belongs to this
class.
The next result shows that the SCB-based deployment is indeed optimal if the shortcut barrier exists.
(All proofs of the theorems and lemmas in the sequel
are relegated to Appendix).
Theorem 1. Under Assumption 1, it is optimal to
deploy radars on the shortcut barrier H, in order to
maximize the worse-case intrusion detectability.
Although Theorem 1 appears intuitive, we caution
that it is non-trivial since the proof hinges on the existence of a shortcut barrier such that a line barrier with
no greater vulnerability can be constructed from any
arbitrary barrier. In other words, if the shortcut barrier does not exist, the optimal deployment may not be
on a shortest barrier (see Figure 2(b)).
Let Hl and Hr denote the end points of H with
Hl Fl and Hr Fr . Note that the worst-case intrusion detectability under a line-based deployment is
no greater than, but not necessarily equal to, the vulnerability of the line segment. However, the equality
holds for the SCB-based deployment as we show in the
next result.
Theorem 2. Under Assumption 1, if radars are deployed on the shortcut barrier H, the worst-case intrusion detectability amounts to the vulnerability of H, i.e.,
B(P ) = Q(H).
Combining Theorem 1 and 2, we conclude that the
problem (4) is equivalent to finding the radar deployment on the shortcut barrier H such that Q(H) is minimized.

3.2 Line-based Optimal Deployment Locations

In this subsection, we study the optimal deployment
locations of radars on the shortcut barrier H to minimize Q(H). Let ti , kHl Ti k and rj , kHl Rj k. Mathematically, our problem can be formulated as

Therefore, standard optimization methods can not be

applied here.
Consider the reformulation of problem (6) as follows.
First, we treat Hl and Hr as two virtual nodes and
relax the constraint Hl Hr = h. Suppose all nodes in
T and R as well as Hl and Hr are deployed on a line
such that Hl and Hr are the leftmost and rightmost
nodes, respectively. Let S , (Hl , S1 , , SJ , Hr ) denote a deployment order (order for short) of all nodes,
where J , M + N and (S1 , , SJ ) is a permutation
of the set T R such that kHl Hl k = 0 kHl S1 k
kHl SJ k kHl Hr k. Without ambiguity, S also
denote an order of locations of all nodes. Let DS =
(kHl S1 k, , kSJ Hr k) denote the deployment spacings
(spacings for short) of a given deployment order of
nodes S, which are the distances between all pairs of
neighbor nodes in S. Similarly, let (Si , Si+1 , , Si+j )
denote a deployment suborder (suborder for short),
which is a deployment order of neighbor nodes in S,
and D(Si ,Si+1 ,Si+j ) = (kSi Si+1 k, , kSi+j1 Si+j k)
denote its deployment spacings. Clearly, any deployment order S with any deployment spacings DS represent some deployment locations of T and R on a line
segment with length kHl Hr k. Likewise, any deployment
locations of T and R on the line barrier H can be represented by some deployment order S with some deployment spacings DS under the constraint kHl Hr k = h.
To summarize, the problem (6) can be recast as
Problem 1. Find an optimal deployment order S
with optimal deployment spacings DS under the constraint kHl Hr k = h such that Q(Hl Hr ) is minimized.
In what follows, we outline the main steps to solve
Problem 1.
Step1: We show a general and important structure of detectability on Hl Hr (Lemma 1), which leads to the
concept of balanced spacings.
Step2: We introduce the concept of local suborder. Then
we show the existence and characterize balanced
spacings for a local suborder (Lemma 2), and establish the optimality of balanced spacings for a
local suborder (Lemma 3).

(6)

Step3: We rule out some orders from consideration, which

leads to the concept of candidate order (Lemma 4).
Then we show that a candidate order consists of
decoupled local suborders, such that the results in
Step 2 can be applied to show that balanced spacings exist and are optimal for a candidate order
(Theorem 3).

where miniM,jN |x ti ||x rj | represents the detectability of a point p H with kHl pk = x. It can
be easily checked that the objective function of problem (6) is neither differentiable nor convex in general.

Step4: Based on the optimal spacings obtained above, we

derive sufficient conditions for an optimal order
(Theorem 4). Then we characterize the optimal
orders.

minimize
ti ,rj

subject to

max

min

0xh iM,jN

|x ti ||x rj |

0 ti h, i M

0 rj h, j N

I(p)
local vulnerable value

(a)
Hl

Hr

R1
I(p)

T1 R2

R3

T2

R4

(b)

Hl

Hr
R1

T1

R2

R3

T2

R4

Figure 3: The detectability of a point attains

local minimums at the end points and the midpoints of all pairs of neighbor radar nodes. The
local vulnerable values are (a) unequal with arbitrary deployment spacings; and (b) equal with
balanced deployment spacings.
We start with two observations. First, swapping the
locations of any pair of transmitters or any pair of receivers results in an equivalent deployment. Second,
transmitters and receivers are reciprocal to each other.
Specifically, replacing all transmitters by receivers and
replacing all receivers by transmitters results in an equivalent deployment. These observations will be used repeatedly in the sequel.
Let Yab denote the midpoint between two points a
and b. In the next lemma, we show a local structure for
the vulnerability of Hl Hr .
Lemma 1. Given any order S with any spacings DS ,
I(p) attains local maximums on Hl Hr at the end nodes
Hl and Hr , and at the midpoints of all pairs of neighbor nodes in (S1 , , SJ ) (as depicted in Figure 3). In
particular,
arg max I(p) = Hl ,
pHl S1

arg max I(p) = Hr

pSJ Hr

arg max I(p) = YSi Si+1 , i {1, , J 1}.

pSi Si+1

For convenience, we refer a local maximum point of I(p)

and its value as a local vulnerable point and local vulnerable value, respectively. The local structure presented
in Lemma 1 is essentially due to that the detectability
of a point is dominated by the closet transmitter and
receiver. Therefore, it suffices to characterize the local
vulnerable values at the local vulnerable points to determine the vulnerability of Hl Hr . We say the spacings
of an order of nodes are balanced if all the local vulnerable values between or on the two end nodes of that
order are equal (see Figure 3).
We define the pattern of an order of nodes as the order of node types (transmitter type T or receiver type
R) of those nodes. We use T k or Rk to denote k consecutive T or R in a pattern, respectively. We define three

kinds of local patterns P1 = (T, Rk , Hr ), (R, T k , Hr ),

(Hl , Rk , T ), or (Hl , T k , R) for k 1, P2 = (T, Rk , T )
or (R, T k , R) for k 2, and P3 = (T, R) or (R, T ).
We say a suborder Si is a local suborder if it has a
local pattern, and it is associated with a local zone, denoted by ZSi , which is the line segment between the
two end nodes of that local suborder. For example, if
Si = (T1 , R1 , , Rk , Hr ), then ZSi = T1 Hr . The vulnerability of a local zone ZSi is Q(ZSi ). We denote the
length of ZSi by LSi .
We observe that for any local suborder Si with any
spacings, the closest transmitter and receiver from S
for any local vulnerable point in ZSi are nodes from Si .
For example, if Si = (T1 , R1 ), we can see that the closest transmitter and receiver for YT1 R1 are T1 and R1 ,
respectively; if Si = (T1 , R1 , , Rk , Hr ), the closest
transmitter for any of YT1 R1 , , YRk1 Rk , Hr , is T1 ,
and the closest receiver for any of YT1 R1 , , YRk1 Rk ,
Hr , is from {R1 , , Rk }. Hence, the vulnerability of
a local zone ZSi , i.e., Q(ZSi ), only depends on the locations of nodes in Si , or in other words, depends on
the spacings DSi , and it is independent of the locations
of nodes not in Si . Similar observations can be made
for any local suborder. Using Lemma (1), in the next
result, we characterize the balanced spacings of a local
suborder.

Lemma 2. For any c > 0, let e0 (c) , 2 c and ej (c)

P
be the unique positive value of x such that ( j1
i=0 ei (c)+
x/2)(x/2) = c for any j 1. Given any c > 0 and any
local suborder Si , there exist unique spacings DSi such
that DSi is balanced with Q(ZSi ) = c. Furthermore, it
is given by, e.g., if Si = (T1 , R1 ), then DSi = (e0 );
if Si = (T1 , R1 , , Rk , Hr ), then
DSi = (e0 , e1 , , ek1 , ek /2);
if Si = (T1 , R1 , , Rk , T2 ) and k is even, then
DSi = (e0 , e1 , , ek/21 , ek/2 , ek/21 , , e1 , e0 )
or if k is odd, then
DSi = (e0 , e1 , , e(k1)/2 , e(k1)/2 , , e1 , e0 )
where the arguments (c) of ei (c) are omitted for brevity.
Similar results can be obtained for any other local suborder.
By definition, given c, the value of ei (c), i 0 can
be found iteratively and it decreases as i increases (see
Table 1).
The following lemma shows that balanced spacings
are optimal for a local suborder.
Lemma 3. Given any local suborder Si , suppose DSi
is balanced with Q(ZSi ) = c. If Si is the same local suborder as Si and with spacings DSi such that Q(ZSi ) c,
then LSi LSi . Furthermore, if LSi = LSi , then
DSi = DSi .

Table 1:
c
e0 (c)
1
2.0000
5
4.4721
10 6.3246
20 8.9443

Values of balanced spacings

e1 (c)
e2 (c)
e3 (c)
e4 (c)
0.8284 0.6357 0.5359 0.4721
1.8524 1.4214 1.1983 1.0557
2.6197 2.0102 1.6947 1.4930
3.7048 2.8428 2.3966 2.1115

Lemma 3 suggests that given a local suborder and a

constraint on the local zones vulnerability, the balanced
spacings maximize the length of the local zone.
We need the following lemma which reduces our search
space significantly.
Lemma 4. There exists an optimal order S not having a suborder with any of the following patterns: (T, T ,
R, R), (R, R, T, T ), (T, T, R, Hr ), (R, R, T, Hr ), (Hl , T ,
R, R), and (Hl , R, T, T, ).
We say an order S is a candidate order if it does not have
a suborder with any of the patterns given in Lemma 4.
We observe that any given candidate order S consists
of a series of local suborders S1 , , Sm such that 1)
each node in S is included in some Si ; 2) the last node
of Si is the first node of Si+1 for all i = 1, , m 1.
In particular, S1 and Sm have patterns P1 , and Si has
pattern P2 or P3 for i = 2, , m 1. For example,
S3

S1

z }| {
z
}|
{
S = (Hl , R1 , R2 , T1 , R3 , R4 , R5 , T2 , R6 , T3 , T4 , Hr ).
{z
} |
{z
}
|
S2

S4

Accordingly, Hl Hr consists of a series of local zones ZS1 ,

, ZSm , and DS consists of a series of spacings DS1 ,
, DSm . To see why such a series of local suborders
exists for any given candidate order S, we construct a
super order S+ from S by combining neighbor nodes
of the same type in S into a super node. A node not
combined in S is a simple node in S+ . For the above
example, the super order is given by
+
+
+
, T1 , R3,4,5
, T2 , R6 , T3,4
, Hr ).
S+ = (Hl , R1,2

It is clear by our construction that two neighbor nodes

in S+ (excluding Hl and Hr ) are of different types
(transmitter type or receiver type). Since S is a candidate order, it does not have a suborder with any pattern
given in Lemma 4. Hence, it can be easily checked that
two neighbor nodes in S+ can not be both super nodes,
and a super node can not be the third or third-to-last
node in S+ . Then we can see that the first three nodes
and the last three nodes in S+ represent two local suborders with patterns P1 ; each super node and its two
neighbor simple nodes in S+ represent a local suborder
with pattern P2 ; two neighbor simple nodes not at the
beginning or end of S+ (excluding Hl and Hr ) represent
a local suborder with pattern P3 .

The decoupled structure of a candidate order allows

us to apply results of local suborders. Consider a given
candidate order S. We know that S consists of a series of local suborders S1 , , Sm . As a result, the set
of local vulnerability values on Hl Hr is a union of disjoint sets of local vulnerability values on all the local
zones ZS1 , , ZSm . Therefore, since local vulnerability values on a local zone ZSi only depend on the corresponding spacings DSi , we can see that DS is balanced
with Q(Hl Hr ) = c if and only if DSi is balanced with
Q(ZSi ) = c for all i = 1, , m. Hence, by Lemma 2,
there exists unique DS such that DS is balanced with
Q(Hl Hr ) = c.
We observe that given a candidate order S, under the
constraint that DS is balanced with Q(Hl Hr ) = c, DS
varies as a function of c. It follows from Lemma 2 that
each of kHl S1 k, , kSJ Hr k is an increasing function
of c, and hence kHl Hr k = kHl S1 k + + kSJ Hr k is
also an increasing function of c. Furthermore, it can
be easily verified that kHl Hr k = 0 when c = 0 and
kHl Hr k when c . Thus, there exists a unique
c > 0 such that kHl Hr k = h. This implies that under
the constraint kHl Hr k = h, there exist unique balanced
DS . We summary this result below as a corollary of
Lemma 2.
Corollary 1. Given any candidate order S, under
the constraint kHl Hr k = h, there exist unique spacings
DS such that DS is balanced.
Applying Lemma 3, we obtain the following theorem.

Theorem 3. Given any candidate order S, the unique

balanced spacings DS minimize Q(Hl Hr ) under the constraint kHl Hr k = h.
Theorem 3 suggests that the optimal spacings for any
given candidate order is the unique balanced spacings
referred in Corollary 1.
Since we have found the optimal spacings DS for any
candidate order S, our next step is to find an optimal order S . Suppose the number of transmitters is
no greater than the number of receivers, i.e., M N ,
WLOG. Since all transmitters are equivalent, we suppose that transmitters in S are indexed by their order
in S such that 0 kHl T1 k kHl TM k kHl Hr k.
Define N , (nHl T1 , nT1 T2 , , nTM 1 TM , nTM Hr ) where
nTi Ti+1 , nHl T1 , and nTM Hr denote the number of receivers between Ti and Ti+1 , between Hl and T1 , and
between TM and Hr , respectively, in S. Since all receivers are equivalent, it suffices to determine nTi Ti+1 ,
nHl T1 , and nTM Hr for an optimal order. The next result provides sufficient conditions for the optimality of
an order.

(a) Hl

Hr

(b) Hl

Hr

(c) Hl

Hr

Figure 4: Optimal deployment locations of radar

transmitters (square) and receivers (circle) for
(a) M = 3 and N = 7 (b) M = 3 and N = 8 (c)
M = 3 and N = 9.
Theorem 4. A candidate order S is optimal if
|nTi Ti+1 nTj Tj+1 | 1, i 6= j

|nTi Ti+1 2nHl T1 | 1, |nTi Ti+1 2nTM Hr | 1, i.

Using the optimality conditions in Theorem 4, we can

find an optimal order S described as follows. Let two
integers q and r be the quotient and remainder of N/M .
If q is even, there exists an S such that
r

}|
{ zM1r
}| { q
q z
N = ( , q + 1, , q + 1, q, , q, );
2
2

if q is odd and r = 0, there exists an S such that

M1

N = (

q + 1 z }| { q 1
, q, , q,
);
2
2

if q is odd and r 1, there exists an S such that

r1

}|
{ z Mr
}| { q + 1
q+1 z
N =(
, q + 1, , q + 1, q, , q,
).
2
2

It can be easily seen that any order obtained from the

above optimal order by exchanging the values of nHl T1
and nTM Hr , or the values of nTi Ti+1 and nTj Tj+1 for
some i 6= j, also satisfies the optimality condition, and
hence is optimal. We observe that the optimal order
also exhibits a balanced structure.
Given an optimal order S , by Theorem 3, the optimal spacings DS is the unique balanced spacings under
the constraint kHl Hr k = h. The optimal spacings can
be found by a bisection search. In each search step,
for a search criterion c, we can obtain by Lemma 2 the
unique balanced spacings DS with Q(Hl Hr ) = c, and
hence obtain kHl Hr k. If kHl Hr k > h, c is decreased
for the next step; if kHl Hr k < h, c is increased for the
next step. The search completes if kHl Hr k = h. Upon
completion, the optimal spacings DS is found and the
optimal value of Q(Hl Hr ) is equal to the search criterion c.

4. RANDOM DEPLOYMENT
Next, we consider random deployment that can also
be of great interest. In this scenario, given arbitrary locations of radars resulted from random deployment, we
aim to find the worst-case intrusion path P and the
worst-case intrusion detectability B(P ). Due to the
complex geometry of bistatic radar SNR, it is difficult
to find P accurately. Therefore, we design an efficient
algorithm for finding an intrusion path P whose detectability is arbitrarily close to B(P ). Our algorithm
partitions the field F into sub-regions based on a novel
2-site Voronoi diagram, and then constructs a weighted
graph G for the sub-regions to search for an approximate worst-case intrusion path PG .
Given a set of points S, the Voronoi region VS (s) of
a point s S is the set of points which are closer to s
than to any other point in S, i.e.,
VS (s) , {p| min
kps k = kpsk}.

s S

(7)

The Voronoi diagram for S is the collection of all Voronoi

regions {VS (s), s S}. To partition the field F , we
first construct Voronoi diagrams for the set of transmitters T and the set of receivers R, respectively, i.e.,
{VT (Ti ), Ti T } and {VR (Rj ), Rj R}, within the
boundaries of F . Then F can be partitioned into 2site Voronoi regions, where a 2-site Voronoi region, denoted by VT ,R (Ti , Rj ), is the intersection of a transmitter Voronoi region and a receiver Voronoi region, i.e.,
VT ,R (Ti , Rj ) , VT (Ti ) VR (Rj )

(8)

for all Ti T and Rj R such that VT (Ti ) VR (Rj ) 6=

(see Figure 5). Choose an arbitrary > 0. For each
2-site Voronoi region VT ,R (Ti , Rj ), we plot a sequence
of Cassini ovals CTi ,Rj (k) for consecutive positive integer values of k such that VT ,R (Ti , Rj ) is further divided by these Cassini ovals into sub-regions where each
sub-region is bounded between two Cassini ovals with
distance products being consecutive multiples of .
We construct a graph G = (V, E) where each vertex
represents a sub-region, and two vertices are connected
by an edge if they are adjacent sub-regions. Then we
assign each vertex vi a weight wi , which is equal to
the smaller distance product of the two Cassini ovals
bounding this sub-region. We add two virtual vertices
s and t to represent the entrance and destination of F ,
respectively. There exists an edge between vertex s and
vi for vi V \ {s, t} if sub-region vi is adjacent to the
entrance. Similarly, we add an edge between vertex t
and vi for vi V \ {s, t} if sub-region vi is adjacent to
the destination.
It is clear that any intrusion path P is represented by
an st path in G, denoted by PG . We define the weight
of an s t path PG , denoted by W (PG ), as W (PG ) ,
min{i:vi PG } wi . We aim to find an s t path PG with
maximum weight. This can be obtained by a bisection

a
v5

v4

R1

v2

d
e

Hr

(b) Hl

Hr

b
v1

T1

(a) Hl

Figure 6: Heuristic deployment locations of

radar transmitters (square) and receivers (circle) for M = 3 and N = 8 (a) HEU-1 (b) HEU-2.

v3

the worst-case detectability, i.e.,

Figure 5: Overlapping Voronoi diagrams for
radar transmitters and receivers. The polygon
with indices {a, b, c, d, e} is a 2-site Voronoi region
with respect to T1 and R1 ; it is divided into subregions {v1 , v2 , v3 , v4 , v5 }.
search between the smallest and largest vertex weights
in G. In each step, breadth-first-search is used to check
the existence of a s t path using only vertices with
weights larger than a search criterion c. If a path exists,
c is increased to restrict the vertices considered in the
next search step; otherwise, c is decreased to relax the
constraint on the search. Upon completion, a s t path
with maximum weight is found.
Suppose M = O(n) and N = O(n). The number of
vertices in graph G, i.e., the number of sub-regions in
field F , is O(n8 /2 + n6 / + n4 ) and the reason is as follows. We can treat the field F as a planar graph, where
the vertices are the crossing points of Voronoi edges and
Cassini ovals, and the edges are line segments or curves
between two crossing points. The number of Voronoi
edges and the number of Voronoi vertices are both O(n).
So the number of crossing points of Voronoi edges is
O(n2 ). Hence, the number of 2-site Voronoi vertices is
O(n2 ), and the number of 2-site Voronoi edges is O(n4 ).
Since the field F is bounded, the number of Cassini
ovals plotted for a 2-site Voronoi region is O(1/). So
the total number of crossing points of Cassini ovals with
2-site Voronoi edges is O(n4 /). Hence, the number of
vertices of sub-regions is O(n4 / + n2 ), and the number
of edges of sub-regions is O(n8 /2 + n6 / + n4 ). By Eulers formula, the number of faces, which is the number
of sub-regions, is 2 - O(n4 /+n2 ) + O(n8 /2 +n6 /+n4 ),
equal to O(n8 /2 + n6 / + n4 ).
In the next result, part (a) follows from the definition
of 2-site Voronoi diagram and our graph construction;
part (b) follows from our result on the number of vertices in graph G. The proof is omitted due to space
limitation.
Theorem 5. (a) The maximum path weight obtained
by our proposed approximation algorithm is within to

B(P ) W (PG ) B(P ).

(9)

(b) Given , our proposed approximation algorithm has

polynomial-time complexity.

5. PERFORMANCE EVALUATION
In this section, we present some numerical results to
illustrate the effectiveness of our proposed optimal radar
deployment scheme.
We examine the vulnerability of a line segment H under the line-based deployment. In particular, we compare the optimal deployment scheme (OPT) with two
heuristic deployment schemes. The first heuristic (HEU1) is to deploy radar transmitters (or receivers, respectively) with uniform spacings such that the maximum
distance from a point on H to its closet transmitter
(or receiver, respectively) is minimized (see Figure 6).
Specifically, HEU-1 results in 2kHl T1 k = kT1 T2 k
= = kTM1 TM k = 2kTM Hr k and 2kHl R1 k =
kR1 R2 k = = kRN 1 RN k = 2kRN Hr k, where transmitters and receivers are indexed by their orders in S,
respectively. It can be easily verified that this scheme is
optimal if we treat radar transmitters (or receivers, respectively) as traditional sensors with disk-based sensing model. The second heuristic (HEU-2) is to deploy
radar transmitters and receivers according to an optimal order S from OPT but with uniform spacings
such that the maximum distance from a point on H
to its closet transmitter or receiver is minimized (see
Figure 6). Specifically, HEU-2 results in 2kHl S1 k =

kS1 S2 k = = kSM1
SM
k = 2kSM
Hr k.
Figure 7, Figure 8 and Figure 9 depict the vulnerability of H versus the number of radar receivers for 3,
5, and 10 radar transmitters, respectively, where we set
h = 100. We note that HEU-2 results in considerably
lower vulnerability than HEU-1. This is because HEU-1
deploys transmitters and receivers independently, while
HEU-2 takes into account the joint design of transmitters and receivers. We observe that OPT further outperforms HEU-2 significantly. This suggests that optimal spacings is critical for improving the performance
due to the complex geometry of bistatic radar SNR.
Next, we evaluate the worst-case intrusion detectabil-

300

30
OPT
HEU1
HEU2

200
150
100
50
0
3

6
9
12
15
Number of radar receivers

15
10

0
10

18

13
16
19
22
Number of radar receivers

25

Figure 9: Vulnerability vs. number of radar receivers for 10 radar transmitters.

1200

OPT
HEU1
HEU2

80
60
40
20

8
11
14
17
Number of radar receivers

20

Worstcase Invisibility

100

Vunerability

20

Figure 7: Vulnerability vs. number of radar receivers for 3 radar transmitters.

0
5

OPT
HEU1
HEU2

25
Vunerability

Vunerability

250

1000

OPT
RAN

800
600
400
200
0
3 4 5 6 7 8 9 101112131415161718
Number of radar receivers

Figure 8: Vulnerability vs. number of radar receivers for 5 radar transmitters.

Figure 10: Worst-case detectability vs. number

of radar receivers for 3 radar transmitters.

ity under random deployment using our proposed approximate algorithm. We consider a square field F of
size 100 100, where two opposite sides are entrance
and destination, respectively, and the other two opposite sides are left and right boundaries, respectively.
We consider deploying transmitters and receivers in the
field randomly (RAN) with uniform distribution.
Figure 10, Figure 11 and Figure 12 depict the worstcase intrusion detectability versus the number of radar
receivers for 3, 5, and 10 radar transmitters, respectively, where we also plot the shortcut barrier-based optimal deployment scheme (OPT). The results for RAN
are averaged over 100 simulation runs. We observe that
OPT performs significantly better than RAN. The reason is that deployment on a barrier is essentially much
more efficient than deployment in the full field for worstcase coverage.

barrier coverage has been introduced in [13], where critical condition of weak barrier coverage is obtained for
random deployment. The critical condition of strong
barrier coverage is derived in [14] using percolation theory. An effective metric of barrier coverage quality is
proposed in [15]. [16] studies constructing barrier by
sensors with limited mobility after initial deployment.
A novel full-view coverage model is proposed in [17] for
constructing barrier in camera sensor networks.

6.

RELATED WORK

Worst-case coverage has been first studied in [5] for a

traditional sensor network. Polynomial-time algorithms
are devised to find maximum breach and maximum
support paths between two locations. An efficient algorithm is proposed in [7] to solve the best-coverage
problem raised in [5]. In [6], efficient algorithms are developed to find the minimum exposure path in sensor
networks. Localized algorithms are designed in [11] to
solve the minimum exposure path problem. A new coverage measure that captures both the best and worstcase coverage is studied in [9]. The deployment problem to improve the maximal breach path is considered
by [8, 12].
Barrier coverage is an intimately related problem to
worst-case coverage. The concept of weak and strong

7. CONCLUSION
Radar technology has great potential in many applications, such as border monitoring, security surveillance. In this paper, we studied the worst-case coverage
for a bistatic radar network consisting of multiple radar
transmitters and radar receivers, where each pair of
radar transmitter and receiver can form a bistatic radar.
The problem of optimal radar deployment is highly nontrivial since 1) the detection range of a bistatic radar
is characterized by Cassini oval which presents complex
geometry; 2) the detection ranges of different bistatic
radars are coupled and the network coverage is intimately related to the locations of all radar nodes. We
present a general assumption on the field geometry under which it is optimal to deploy radars on a shortest
line segment across the field, for maximizing the worstcase intrusion detectability. Further, we characterized
the corresponding optimal deployment locations along
this shortest line segment. Specifically, the optimal deployment locations exhibits a balanced structure. We
also developed a polynomial-time approximation algorithm for characterizing the worst-case intrusion path
for any given deployment of radars.
To the best of our knowledge, the optimality of line-

Worstcase Invisibility

800
OPT
RAN
600

[9]

400

200

0
5 6 7 8 9 1011121314151617181920
Number of radar receivers

Figure 11: Worst-case detectability vs. number

of radar receivers for 5 radar transmitters.

[10]
[11]

Worstcase Invisibility

300
250

OPT
RAN

200

[12]

150
100
50

[13]

0
10111213141516171819202122232425
Number of radar receivers

Figure 12: Worst-case detectability vs. number

of radar receivers for 10 radar transmitters.
based deployment for the worst-case coverage, in particular for bistatic radar networks, has not been studied
before this work. Although the detectability model involves some idealized assumptions, we believe that this
work will be of value in setting the foundations for networked radar systems. There are still many questions
remaining open for the design of networked radar.

8.

REFERENCES

[1] N.-J. Willis, Bistatic Radar. SciTech Publishing,

2005.
[2] C.-J. Baker and A.-L. Hume, Netted radar
sensing, IEEE Aerospace and Electronic Systems
Magazine, vol. 18, pp. 36, Feb. 2003.
[3] E. Paolini, A. Giorgetti, M. Chiani, R. Minutolo,
and M. Montanari, Localization capability of
cooperative anti-intruder radar systems,
EURASIP Journal on Advances in Signal
Processing, 2008.
[4] S. Bartoletti, S. Conti, and A. Giorgetti, Analysis
of uwb radar sensor networks, in IEEE ICC 2010.
[5] S. Meguerdichian, F. Koushanfar, M. Potkonjak,
and M. Srivastava, Coverage problems in wireless
ad-hoc sensor network, in IEEE INFOCOM
2001.
[6] S. Meguerdichian, F. Koushanfar, G. Qu, and
M. Potkonjak, Exposure in wireless ad-hoc
sensor network, in ACM MOBICOM 2001.
[7] X.-Y. Li, P.-J. Wan, and O. Frieder, Coverage in
wireless ad hoc sensor networks, IEEE
Transactions on Computers, vol. 52, pp. 753763,
Jun. 2003.
[8] R.-H. Gau and Y.-Y. Peng, A dual approach for
the worst-case-coverage deployment problem in

[14]

[15]

[16]

[17]

ad-hoc wireless sensor networks, in IEEE MASS

2006.
C. Lee, D. Shin, S.-W. Bae, and S. Choi, Best
and worst-case coverage problems for arbitrary
paths in wireless sensor networks, in IEEE
MASS 2010.
P. Gupta and P.-R. Kumar, The capacity of
wireless networks, vol. 2, pp. 388404, Mar. 2000.
S. Meguerdichian, S. Slijepcevic, V. Karayan, and
M. Potkonjak, Localized algorithms in wireless
ad-hoc networks: Location discovery and sensor
exposure, in ACM MOBIHOC 2001.
A. Duttagupta, A. Bishnu, and I. Sengupta,
Optimisation problems based on the maximal
breach path measure for wireless sensor network
coverage, in ICDCIT 2006.
S. Kumar, T.-H. Lai, and A. Arora, Barrier
coverage with wireless sensors, in ACM
MOBICOM 2005.
B. Liu, O. Dousse, J. Wang, and A. Saipulla,
Strong barrier coverage of wireless sensor
networks, in ACM MOBIHOC 2008.
A. Chen, T.-H. Lai, and D. Xuan, Measuring and
guaranteeing quality of barrier-coverage in
wireless sensor networks, in ACM MOBIHOC
2008.
A. Saipulla, B. Liu, G. Xing, X. Fu, and J. Wang,
Barrier coverage with sensors of limited
mobility, in ACM MOBIHOC 2010.
Y. Wang and G. Cao, Barrier coverage in camera
sensor networks, in ACM MOBIHOC 2011.

APPENDIX
A. PROOF OF THEOREM 1
Proof: Consider any given deployment locations {T , R}.
It suffices to show that there exist deployment locations
{T , R } on H such that B(P ) B (P ), where indicates that the deployment locations are {T , R }. It
follows from Property 1 that there exists a curve barrier
U with U A(B(P )). Let Ul and Ur be the end points
of curve U with Ul Fl and Ur Fr . We will show
that the deployment at {T , R } forms a line barrier
Ul Ur with Q (Ul Ur ) Q(U ) (see Figure 13).
Let U be the line passing through Ul and Ur . Then
we can find the projection of any Ti T and Rj R
onto line U , denoted by Ti and Rj , such that Ti Ti U
and Rj Rj U . Consider any p Ul Ur . Since curve U
is a path from Ul to Ur , we can find a p U such that
p is the projection of p onto line U . Then it follows
from the property of projection that kTi pk kTi p k and
kRj pk kRj p k for all i, j. Hence, from (2) we have
I(p) I (p ), and it follows that Q (Ul Ur ) Q(U )
due to (5). Since H is the shortcut barrier, we have
h kUl Ur k. Thus, we can translate the line-based de-

Ti

OHl (h)

Rj

Ur
Ul

Ti

Rj

Figure 13: An arbitrary radar deployment forms

a curve barrier U (solid curve), while a linebased radar deployment can form a line barrier
Ul Ur (dashed line) with no greater vulnerability.
ployment {T , R } onto the line where H lies such that
Q (H) Q(U ). Note that {T , R } may not be all on
H. In this case, we can move each Ti
/ H or Rj
/ H to

its closest end point of H such that I (p) is not increased

for all p H and hence Q (H) Q(U ) still holds.
Therefore, since H is a barrier and U A(B(P )), we

have B (P ) Q (H) Q(U ) B(P ).

B. PROOF OF THEOREM 2
Proof: Consider any given deployment locations {T , R}
on H. From the definition of barrier we have B(P )
Q(H). Suppose B(P ) < Q(H). The proof is based
on contradiction. It follows from Property 1 that there
exists a barrier U with U A(B(P )) A(Q(H)).
We will show that barrier U must intersect with H (see
Figure 14).
Step 1: Consider a point p H with I(p) = Q(H).
Suppose p 6= Hl and p 6= Hr . Let H be the line passing
through p such that H H. Consider any p H with
p 6= p. Since kTi p k > kTi pk and kRj p k > kRj pk for
all i, j, we have I(p ) > I(p) and hence p
/ A(Q(H)).
Thus H intersects with A(Q(H)) at a unique point p.
Step 2: Let Al (Q(H)) and Ar (Q(H)) denote the subsets of A(Q(H)) on the left and right side of H , respectively (see Figure 14). Define Oc (r) as an open disk
centered at point c with radius r. We will show that
Al (Q(H)) OHl (h) and Ar (Q(H)) OHr (h).
Let O Hl (h) denote the circle centered at Hl with ral
dius h. Then let OHl (h) denote the subset of OHl (h)

on the left side of H , which is an arc. It can be verified

that kTi ak > kTi pk and kRj ak > kRj pk for all i, j and
l

for all a OHl (h). Then since I(p) = Q(H), we have

l

A(Q(H)) O Hl (h) = . This implies that Al (Q(H))

OHl (h). Similarly, we can show Ar (Q(H)) OHr (h).
Step 3: Let Ul and Ur be the end points of U with
Ul Fl and Ur Fr . Then we have Ul
/ OHr (h) and
Ur
/ OHl (h), since otherwise kUl Hr k < h or kHl Ur k <
h, which contradicts that H is the shortcut barrier. Using the result of Step 2, we have Ul Al (Q(H)) and
Ur Ar (Q(H)). Thus, curve U must intersect H .
From the result of Step 1, U must pass through p. This
implies that Q(U ) I(p) = Q(H), which contradicts

Rj
Hr
p
Al (Q(H)) Ar (Q(H))

Hl

Ti

Figure 14: Any barrier with possibly lower vulnerability than the shortcut barrier H must lie
in the detection range A(Q(H)) (grey area) and
pass through a line H which has a unique intersection p with A(Q(H)).
that Q(U ) B(P ) < Q(H).

C. PROOF OF LEMMA 1
We start with an observations which is used repeatedly
in this proof. Clearly, for any p H, I(p) only depends on the distances of p to its closest transmitter
and receiver, say Ti and Rj , respectively. If p
/ Ti Rj ,
I(p) = kTi pkkRj pk decreases as p moves towards Ti and
Rj ; if p Ti Rj , since kTi pk + kpRj k = kTi Rj k is a constant, it can be easily verified that I(p) = kTi pkkpRj k
increases as p moves towards YTi Rj , and hence attains
maximum when p = YTi Rj .
The main idea of this proof is to divide the line segment between each pair of neighbor nodes into intervals
such that all points on an interval have the same pair of
closest transmitter and receiver, and then we examine
the structure of detectability on each interval using the
observation presented above. Due to space limitation,
we only prove the case when Sk and Sk+1 have different
types (transmitter type and receiver type) for some k.
The same idea is used to prove other cases.
Suppose Sk and Sk+1 have different types. Without
loss of generality (WLOG), let Sk = Ti and Sk+1 = Rj .
1) Suppose the closest transmitter and receiver are Ti
and Rj for any p Ti Rj . Since I(p) = kTi pkkpRj k
for p Ti Rj , I(p) increases as p moves towards YTi Rj .
2) Suppose there exists some Rm Hl Ti such that
YRm Rj Ti YTi Rj . Then I(p) = kRm pkkTi pk for p
Ti YRm Rj , and I(p) = kTi pkkpRj k for p YRm Rj YTi Rj .
For each case of p, I(p) increases as p moves towards
YTi Rj . Similarly, if there exists some Tn Rj Hr such
that YTi Tn YTi Rj Rj , we can also show that I(p) increases as p moves towards YTi Rj for p YTi Rj Rj .

D. PROOF OF LEMMA 2
Due to space limitation, we only prove the case of Si
with pattern P1 , and the same idea is used to prove
other cases. The main idea is to determine the spacing

between two neighbor nodes successively according to

the given order of nodes.
Suppose Si = (T1 , R1 , , Rk , Hr ) and DSi is balanced with Q(T1 Hr ) = c. It follows
from I(YT1 R1 ) =
(kT1 R1 k/2)2 = c that kT1 R1 k = 2 c. Since I(YR1 R2 ) =
kT1 YR1 R2 k kYR1 R2 R2 k = (kT1 R1 k+ kR
1 R2 k/2)
(kR1 R2 k/2) = c, given kT1 R1 k = 2 c, we obtain a
unique value of kR1 R2 k. Similarly, in a recursive manner, given the values of kT1 R1 k, , kRi1 Ri k, we obtain a unique value of kRi Ri+1 k such that I(YRi Ri+1 ) =
c . . . until we obtain a unique value of kRk Hr k such
that I(Hr ) = c. Then we can see that kT1 R1 k = e0 (c),
kR1 R2 k = e1 (c), , kRk1 Rk k = ek1 (c), kRk Hr k =
ek (c)/2. Similar results can be shown for any Si with
pattern P1 .

lar results can be shown for an order with any pattern

given in the claim by a swapping argument.

E. PROOF OF LEMMA 3

H. PROOF SKETCH OF THEOREM 4

Due to space limitation, we only prove the case of Si

with pattern P1 and the same idea is used to prove
other cases. Suppose Si = (T1 , R1 , , Rk , Hr ) and
Si = (T1 , R1 , , Rk , Hr ). Let I (p) denote the detectability of p under Si . The proof is based on contradiction. Suppose kT1 Hr k > kT1 Hr k. Since I(YT1 R1 ) =
(kT1 R1 k/2)2 = c I (YT1 R1 ) = (kT1 R1 k/2)2 , we have
kT1 R1 k kT1 R1 k. Using this, we can show kT1 R2 k
kT1 R2 k. Then following a similar argument, using
kT1 R2 k kT1 R2 k, we can show kT1 R3 k kT1 R3 k . . .
until kT1 Rk k kT1 Rk k.
Since we have supposed kT1 Hr k > kT1 Hr k, we must
have kRk Hr k = kT1 Hr kkT1 Rk k > kT1 Hr kkT1 Rk k =
kRk Hr k. It follows that I (Hr ) = kT1 Hr kkRk Hr k >
kT1 Hr kkRk Hr k = c, which is a contradiction. Thus we
conclude kT1 Hr k kT1 Hr k. Further, it can be easily
verified that if kT1 Hr k = kT1 Hr k, we have kT1 R1 k =
kT1 R1 k, , kRk Hr k = kRk Hr k. Similar results can
be shown for any Si with pattern P1 .

Consider any given candidate order S. Clearly, S consists of suborders S1 , , SM+1 where S1 = (Hl , , T1 ),
, Si = (Ti1 , , Ti ), , SM+1 = (TM , , Hr ).
Suppose DS is balanced with kHl Hr k = h and Q(Hl Hr )
= c.
The proof has two steps. In step 1, we suppose the
conditions given in the claim do not hold, and then we
can find a new order S from S with some spacings DS
such that Q (Hl Hr ) c and kHl Hr k kHl Hr k, where
Q (Hl Hr ) denote the vulnerability of Hl Hr under S .
This implies that S is no worse than S. Repeating
this argument, we can eventually find a new order S
satisfying the conditions in the claim and is no worse
than S. In step 2, we show that all candidate orders
satisfying the conditions in the claim are equivalently
good. This implies that they are all optimal orders.
Due to space limitation, we only prove step 1 for the
case nTi1 Ti nTj1 Tj + 2 and nTj1 Tj 2. The same
idea is used to prove other cases in step 1 although more
intricate arguments are needed for some cases.
Suppose nTi1 Ti nTj1 Tj + 2 and nTj1 Tj 2.
Clearly, Si and Sj must be local suborders. We can
construct a new order S from S by moving a receiver
from between Ti1 and Ti in Si to between Tj1 and Tj
in Sj . Then we set the spacings DSi and DSj balanced
and Q(ZSi ) = Q(ZSj ) = c, and we keep the spacings of
any other suborder unchanged, i.e., DSm = DSm for all
m 6= i, j. Therefore, we must have Q (Hl Hr ) = c.
We observe from Lemma 2 that we have LSj LSj =
e(nTj1 Tj +1)/2 (c) if nTj1 Tj is odd or enTj1 Tj /2 (c) if
nTj1 Tj is even. Also, we have LSi LSi = e(nTi1 Ti 1)/2 (c)
if nTi1 Ti is odd or enTi1 Ti /2 (c) if nTi1 Ti is even. Since
e0 (c) > e1 (c) > e2 (c) > for any c, in any case, we
have kHl Hr kkHl Hr k = (LSj LSj )(LSi LSi ) > 0.

F. PROOF OF LEMMA 4
Suppose S = (Hl , , T1 , T2 , R1 , R2 , , Hr ) with any
spacings. We can construct a new order of locations
S = (Hl , , T1 , R1 , T2 , R2 , , Hr ) from S by swapping the locations of nodes T2 and R1 . Let I (p) denote
the detectability of p after the swapping. We observe
that for any local vulnerable point p Hl T1 , the closest transmitter is not T2 , and for any local vulnerable point p R2 Hr , kT2 pk kT2 pk. Similar observations can be made for R1 and R1 . Thus we can
see that I (p) I(p) for any local vulnerable point
p Hl T1 or p R2 Hr . We also observe that I(YT1 T2 )
(kT1 T2 k/2)2 = (kT1 R1 k/2)2 = I (YT1 R1 ). Similarly,
we can obtain I(YR1 R2 ) I (YT2 R2 ). Furthermore,
we have I(YT2 R1 ) = (kT2 R1 k/2)2 = (kR1 T2 k/2)2 =
I (YR1 T2 ). Thus we have shown that I (p) I(p) for
any local vulnerable point p Hl Hr , and hence,
Q(Hl Hr ) is not increased after the swapping. Simi-

G. PROOF OF THEOREM 3
Suppose DS is balanced with Q(Hl Hr ) = c. We have
shown that S consists of a series of local suborders
S1 , , Sm . Suppose S is the same order as S and with
spacings DS such that Q (Hl Hr ) c, where Q (Hl Hr )
denote the vulnerability of Hl Hr under S . Then S
also consists of a series of local suborders S1 , , Sm
such that Sj and Sj are the same local suborders for
all j = 1, , m. It is clear that Q (ZSj ) c, j.
Then Lemma 3 implies that LSi LSj , j. Since
Pm
Pm

j=1 LSj , we must have LSj = LSj ,

j=1 LSj = h =
j. Hence, by Lemma 3, we have DS = DS .

Recall that we have shown Q (Hl Hr ) = c. Then the desired result follows.