1

Robust and Scalable Tracking of Radiation
Sources with Cheap Binary Proximity Sensors

arXiv:1608.00557v1 [math.OC] 2 Aug 2016

Henry E. Baidoo-Williams, Member, IEEE,

Abstract—We present a new approach to tracking of
radiation sources moving on smooth trajectories which
can be approximated with piece-wise linear joins or
piece-wise linear parabolas. We employ the use of cheap
binary proximity sensors which only indicate when a
radiation source enters and leaves its sensing range.
We present two separate cases. The first is considering
that the trajectory can be approximated with piece-wise
linear joins. We develop a novel scalable approach in
terms of the number of sensors required. Robustness
analysis is done with respect to uncertainties in the
timing recordings by the radiation sensors. We show
that in the noise free case, a minimum of three sensors
will suffice to recover one piece of the linear join with
probability one, even in the absence of knowledge of
the speed and statistics of the radiation source. Second,
we tackle a more realistic approximation of trajectories
of radiation sources – piece-wise parabolic joins – and
show that no more than six sensors are required in
the noise free case to track one piece of the parabola
with probability one. Next we present an upper bound
on the achievable error variance in the estimation of
the constant speed and the angle of elevation of linear
trajectories. Finally, a comprehensive set of simulations
are presented to illustrate the robustness of our approach
in the presence of uncertainties.
Index Terms—Tracking, Localization, Estimation, Binary sensor network, Radiation sources, Cramér-Rao
lower bound.

I. I NTRODUCTION

T

RACKING and localization of radiation sources
based on the received photon count at radiation
sensors has garnered recent interest [8], [9], [6], [4].
The problem of tracking the path of a source using
binary proximity sensors has been around for some
time [5], [7], [11], [1], [12], [2], [10]. For tracking
of radiation sensors, there is a great motivation for
using binary proximity sensors. It is easy to argue
that the intrinsic nature of radiation sources and their
adverse effects require the surveillance of vast regions.
Coupled with the fact that radiation sensors – binary
or otherwise – are not as cheap as compared to say
wireless sensors, a delicate balance has to be made
to use these multiple error prone but not so cheap
radiation sensors to attain reasonable errors in tracking.
In this paper, we consider the use of cheap binary
proximity sensors in tracking under some fairly general assumptions on the smoothness and continuity of
H. E. Baidoo-Williams was with the US Army Research Laboratory, Aberdeen Proving Ground, MD and University at Buffalo,
SUNY, NY, 14150, USA e-mail: (henrybai AT buffalo DOT edu).

source trajectory. We consider that the trajectory of the
radiation source can be fairly approximated with piecewise joins. To scenarios are considered – piece-wise
linear and piece-wise parabolic. In our formulation,
we consider tracking using the exponential distributed
arrival times of the photons and the total Poisson
distributed count at radiations sensors. To be precise,
we consider binary sensors which co-ordinate with
a fusion center. The binary proximity sensors record
two transition times and relay this information to the
fusion center for tracking. The two transition times
are the times when a radiation source enters the
detection range of the sensor and when it leave it. We
assume that all observations are available at the fusion
center, thus no consideration is made in this paper for
using distributed algorithms at the sensors to reduce
overhead costs.
The rest of the paper is organized as follows: section
II presents a brief survey of related literature. Section
III presents a summary of our contributions. Section IV
presents a formal statement of the problems presented
in this paper. Section V presents preliminary solutions
and algorithms with particular application to the noise
free case. Section VI presents results on scalability and
robustness of the least squares algorithms presented in
this paper. Section VII presents analysis on the upper
bound on the achievable Cramér-Rao lower bound on
the estimation errors of the constant speed and angle of
elevation of linear trajectories. Sections VIII presents
a comprehensive set of simulations to illustrate the
efficacy of the algorithms developed in this paper
whiles section IX concludes.
II. R ELATED WORK
Binary sensors present a rich toolset for covering
large regions of interest. However, by nature, they are
very noisy, and depending on the physics of the signals
of interest, may compound the attainable accuracies
of estimated parameters. Radiation sources, by nature
are inherently noisy even without any “conventional”
background noise. This is because the received signals
are either the photon count per unit time which is
poisson distributed or the inter-arrival times of the
photons which are exponentially distributed.
The existing studies on tracking of sources on piecewise linear trajectories using binary proximity sensors
considered a least squares approach [4] and Newton
based approach in [3]. In [4], the authors showed

2

that using four generically placed sensors, each piece
of the linear joins can be estimated precisely in the
no noise case. The authors did a robustness analysis,
however, on the detection range of the sensors. This
approach, which will be appropriate in many physical phenomena like wireless and acoustic signals, is
inadequate for radiation sources. In radiation sources,
the errors are in the arrival times. The approach in
[4] also assumes implicitly that the source signal
strength at unit distance and no shielding is known.
This translates to knowledge of the detection range in
the noise free case. It is worthy of note that without
the knowledge of the detection range, the algorithm
in [4] is not implementable. Further, the algorithm in
[4] produces 2n−1 possible solutions obtained from
2n−1 least squares problems where n is the number of
sensors being utilized by linear trajectory. This is not
scalable. In [3], the authors consider tracking of piecewise linear trajectories with unknown detection range
in the noise free case and show that four generically
placed sensors will suffice to localize a single linear
trajectory in the noise free case with probability one.
The authors however use a Newton based algorithm
with no guarantee of convergence unless initialization
is done in the basin of attraction of the true solution.
Again, the authors did a robustness analysis on the
detection range.
Other existing studies do not consider piece-wise
joins, but rely on high density of sensors to guarantee
that every motion is within the detection range of
multiple sensors [11], [12], [13]. These studies also
assume implicitly that the source signal strength at unit
distance and no shielding is known.
III. O UR CONTRIBUTIONS
This brings us to the key contribution of this paper:
1) We consider tracking of radiation sources with
binary proximity sensors on piece-wise linear
trajectories and make the following novel contributions:
• We show that contrary to existing literature,
three generically placed sensors, not four,
suffice to estimate a linear trajectory with
probability one in the absence of noise even
if we have no knowledge of the statistics of
the radiation source.
• Our least squares algorithm for tracking on
linear trajectories requires precisely 2 least
squares problems as compared to 2n−1 in
[4].
• We consider a realistic model – for tracking
of radiation sources – in the sense that the
noise is in the arrival times and is Erlang
distributed with errors scaling as a squared
proportion of the arrival times at the boundaries of the unknown detection range.
2) We extend the results from [4] and [3] to a piecewise parabolic trajectories with a realistic error

model in the inter-arrival times corresponding
to the time of shortest distance of approach to
sensors. We show that no more that six sensors
suffice in the noise free case to localize a linear
trajectory with probability one.
IV. P ROBLEM S TATEMENT
We now formally state the problems to be tackled in
this paper. The problems are categorized under: piecewise linear and piece-wise parabolic.
A. Tracking of a radiation source on a piece-wise
linear trajectory
Consider a mobile radiation source in R2 on a piecewise linear trajectory with the ith piece of the linear
trajectory defined as:
xi (t) = x∗oi + s∗xi (t − toi ) sin θi∗
∗
yi (t) = yoi
+ s∗yi (t − toi ) cos θi∗

(1)

∗
where {x∗oi , yoi
} is the location of the radiation source
at time instant t = toi . {s∗xi , s∗yi } are constant speeds
with respect to the x and y axis respectively in the
cartesian plane. θi is the elevation angle with respect
to the x axis of the cartesian plane.
Consider n binary proximity sensors in R2 under
the following assumption:

Assumption 1. The location of each sensor is a
point source {xj , yj }, j ∈ {1, · · · , m}. Further, the
time instantaneous location of the radiation source
{xi (t), yi (t)}, i ∈ {1, · · · , n} is also a point source.
Under assumption 1, the time instantaneous distance
of the j th radiation sensor, , ∈ {1, · · · , n}, on the ith
linear trajectory, i ∈ {1, · · · , m} is defined as:
q
(2)
dij (t) = (xi (t) − xj )2 + (yi (t) − yj )2
The binary proximity radiation sensors measure the
number of photons received at the j th sensor, j ∈
{1, · · · , n}, and output a time stamp or not depending
on whether the aggregate number of received photons
within a time window is greater or less than an arbitrary threshold which is set a priori. Time transitions
corresponding to a sensors moving form outside the
detection range to inside the detection range of sensors
are recorded and transmitted to a fusion center. Precisely, the j th sensor’s measurements, j ∈ {1, · · · , n},
which are transmitted to the fusion center whiles the
radiation source is on the ith piece of the linear
trajectory, i ∈ {1, · · · , m}, in the noise free case are:
t+ 12

t∗ij1

Z

= argmin
t
t− 12
t+ 21

t∗ij2

Z

= argmax
t
t− 12

∗

e−αs dij (τ )
λT − λb
dτ ≥
d∗2
(τ
)
λ∗s
ij

(3)

∗

e−αs dij (τ )
λT − λb
dτ ≥
d∗2
(τ
)
λ∗s
ij

(4)

3

From (3) – (4), the time of shortest distance of
approach to each sensor j ∈ {1, · · · , n} corresponding
from a particular linear trajectory i ∈ {1, · · · , m}
becomes:
t∗ij1 + t∗ij2
t∗ij =
(5)
2
Here, λ∗s is the photon count at unit distance and zero
shielding per second. αs is the shielding coefficient
which depends on type and geometric shape of the
radiation material. λT > λb implicitly defines the
expected maximum radius beyond which the sensor
is “off”, and “on” otherwise. λb is normally occurring
radiation background noise. In reality, both λ∗s and λb
are poisson random variables.
Suppose the following assumptions hold:
Assumption 2. The radiation source intensity λs , is
unknown.
Assumption 3. The location of the sensors are all
distinct, independent and identical distributed and zero
mean along both the x and y axis in the cartesian
plane.
Assumption 4. The radiation source moves with a
constant speed for each piece of the trajectory. Thus
{s∗xi , s∗yi } = s∗i ∀ i, i ∈ {1, · · · , m}.
Assumption 5. The received radiation photon count
at each sensor with respect to any single piece of the
trajectory, under noise free case, is unimodal.
It is clear that the expected instantaneous received
signal at sensor j with respect to the ith trajectory is
given as:
zij (t) =

λ∗s e−αs dij (t)
+ λb
d2ij (t)

(6)

The expected value of the peak with respect to time
of (6) obeys:


2
1 ˙
λ∗s e−αs dij (t)
dij (t) ⇒
żij (t) =
αs +
2
dij (t)
dij (t) dij (t)
d˙ij (t∗ ) = 0 ⇒
ij

(xi (t∗ij ) − xj )s∗i sin θi∗ + (yi (t∗ij ) − yj )s∗i cos θi∗
0=
d∗ij (t∗ij )

•

what is the minimum number of sensor readings
required for estimation of a single linear piece?
suppose there is noise in the recorded times, can
we still estimate the line robustly?

B. Tracking of radiation source on a piece-wise
parabolic trajectories
Now consider a radiation source in R2 whose ith
piece of a piece-wise parabolic trajectory obeys:
= x∗oi + αi∗ (t − toi )

xi (t)
yi (t)

=

∗
yoi

+

βi∗ (t

− toi ) +

1 ∗
2 γi (t

(8)
2

− toi )

(9)

∗
where {x∗oi , yoi
}, i ∈ {1, · · · , m} is the location of
the radiation source at time instant t = toi , i ∈
{1, · · · , m}. Consequently, the j th sensor’s measurements corresponding to the time of shortest approach,
j ∈ {1, · · · , n}, whiles on the ith piece of the
parabolic trajectory, i ∈ {1, · · · , m}, is as defined in
(5). The time of shortest approach of the ith trajectory
from the j th sensor following a similar derivation
leading to (7) is:

3
1 ∗ ∗
γi (tij − toi )3 + βi∗ (t∗ij − toi )2 +
2
2
αi∗2 + βi∗2
α∗
∗
+ yoi
(t∗ij − toi ) + ∗i (x∗oi − xj )+
∗
γi
γi
βi∗ ∗
(y − yj ) = yj (t∗ij − toi )
(10)
γi∗ oi
This brings us to the second problem statement:
Problem 2. Under (8), suppose assumptions 1, 2, 3,
4 and 5 hold. Given:
1) the sensor readings of the time of shortest approach t∗ij , i ∈ {1, · · · , m}, j ∈ {1, · · · , n}
2) the sensor locations {xj , yj } ∀j ∈ {1, · · · , n}
∗
∗
∗
∗
∗
• can we estimate {xoi , yoi , αi , βi , γi }?
• is the estimate unique?
• what is the minimum number of sensor readings
required for estimation of a single parabolic
piece?
• suppose there is noise in the recorded times, can
we still estimate the parabola robustly?
V. P RELIMINARIES
We now consider the two problems described in
section IV.

leading to:
t∗ij − toi =

•

sin θi∗
cos θi∗
∗
(xj − x∗oi ) +
(yj − yoi
) (7)
∗
si
s∗i

This brings us to the first problem statement:

A. Tracking of piece-wise linear trajectories under no
noise conditions

Problem 1. Under (1), suppose assumptions 1, 2, 3,
4 and 5 hold. Given:
1) the
sensor
readings
{t∗ij1 , t∗ij2 }
,
i ∈ {1, · · · , m}, j ∈ {1, · · · , n}
2) the sensor locations {xj , yj } ∀j ∈ {1, · · · , n}
∗
∗
∗ ∗
• can we estimate {xoi , yoi , θi , si }?
• is the estimate unique?

Suppose that a radiation source is on a line as
defined in (1) and suppose the radiation source triggers
n radiation sensors such that their time of shortest
distance of approach t∗ij − toi , i ∈ {1, · · · , m}, j ∈
{1, · · · , n}, is recorded and transmitted to the fusion
center. Also, suppose the locations of the radiation sensors are known. The question being asked is whether
we can uniquely determine the parameters of (1) from

4

the given information. To begin, we have the following
theorem:
Theorem 1. Suppose a radiation source on a linear
trajectory, as defined in (1), triggers n = 3 sensors
such that:
•
•

the times stamps , {t∗ij1 , t∗ij2 }, i
∈
{1, · · · , m}, j ∈ {1, 2, 3} are available.
the locations of the centers of the n = 3 radiation sensors are independent and identically
distributed in R2 .

Then with probability being equal to one, the line
(1) is uniquely determined based on the n = 3
radiation sensor centers centers (xj , yj ), j ∈ {1, 2, 3}
and the {t∗ij1 , t∗ij2 }, i ∈ {1, · · · , m}, j ∈ {1, 2, 3},
information.
Proof. Without loss of generality, suppose x1 = y1 =
y2 = 0. Notice that this can be achieved by rotation
and translation of the entire space without altering any
of the measured signal because distance measurements
are invariant under translation and rotation. Also note
∗
that the parameters {θi∗ , x∗oi , yoi
} are arbitrarily ro∗
tated with respect to {x1 , y1 , y2 }. {x∗oi , yoi
} are also
translated. We however retain all notations to preserve
clarity. Consequently, from (5):
t∗i1

cos θi∗ ∗
sin θ∗
yoi + toi
= − ∗ i x∗oi −
si
s∗i
sin θi∗
x2 − t∗i1
s∗i

(12)

cos θi∗
sin θi∗
x
+
y3 − t∗i1
3
s∗i
s∗i

(13)

t∗i2 =

t∗i3 =

(11)

Here, (11) has already been utilized to form (12) and
(13). From (12) and (13):
s∗i =

t∗i3

sin θi∗
x2 ⇒
t∗i1 + t∗i2

= (t∗i1 + t∗i2 )



⇒ tan θi∗ =

y3
∗
t∗
i1 +ti3
∗ x2
t∗
i1 +ti2

x3
x2

+

y3
1
tan θi∗ x2

(14)



− t∗i1

− x3

(15)

(16)

Notice that since {x2 , x3 , y3 } 6= 0, there is no degenerate solution in (16). Consequently {θi∗ , s∗i } are
uniquely determined as:


y3

θ̂i∗ = tan−1  t∗ +t∗
(17)
i1
i3
t∗ +t∗ x2 − x3
i1

i2



y3
x
2
ŝ∗i = ∗
sin tan−1  t∗ +t∗
i1
i3
ti1 + t∗ti 2
∗
∗ x2 − x3
ti1 +ti2

Now, we move on to determe {xoi , yoi }. Notice that
(1) can be rewritten devoid of explicit dependence on
time as:
(y − yoi ) sin θi∗ − (x − xoi ) cos θi∗ = 0

(19)

The distance of shortest approach, can easily be shown,
for each sensor to be:
(yj − yoi ) sin θi∗ − (xj − xoi ) cos θi∗ = 0
Since the maximum distant from which any of the
sensors is triggered is the same, we can use any pair
of sensor, to arrive at the following equation:
((yj − yoi ) sin θi∗ − (xj − xoi ) cos θi∗ )2
2
s∗2
s∗2
2
+ i t∗ij2 − t∗ij1 = i (t∗ik2 − t∗ik1 )
4
4
((yk − yoi ) sin θi∗ − (xk − xoi ) cos θi∗ )2

(20)

Further rearrangement of (20) will lead to:

xoi 2(xk − xj ) cos2 θi∗ − 2(yk − yj ) sin θi∗ cos θi∗ +

yoi 2(yk − yj ) sin2 θi∗ − 2(xk − xj ) sin θi∗ cos θi∗

s∗2
= i (tik2 − tik1 )2 − (tij2 − tij1 )2 +
4
(yk sin θi∗ − xk cos θi∗ )2 − (yj sin θi∗ − xj cos θi∗ )2
Recall that by assumption, {x1 , y1 , y2 } = 0. Hence,
we can reduce (20) further to:
2x2 cos2 θi∗ xoi − 2x2 sin θi∗ cos θi∗ yoi =
(21)

s∗2
i
(tik2 − tik1 )2 − (tij2 − tij1 )2 + x22 cos2 θi∗
4
Now, solving (21) concurrently with (11), a degenerate
solution will arise if and only if:
x2 cos θi∗ = 0
Since x2 6= 0, we will have a degenerate solution if and
only if θi∗ ∈ { π2 , 3π
2 }. Notice that we have rotated and
translated the entire space to have a situation where
{x1 , y1 , y2 } = 0. Since {x1 , y1 , y2 } = 0 are i.i.d. distributed, the probability that the angle of elevation after
rotation about {x1 , y1 } such that y2 = 0 is in { π2 , 3π
2 }
∗
is zero. This concludes the proof that {θi∗ , s∗i , x∗oi , yoi
}
and by extension the line (1) is uniquely determined
with probability being equal to one.
B. Tracking of piece-wise parabolic trajectories under
no noise conditions

Suppose that a radiation source is on a parabola
as defined in (8) under no noise conditions. Suppose
the radiation source triggers n radiation sensors such
that their time of shortest distance of approach t∗ij ,
i ∈ {1, . . . , m}, j ∈ {1, · · · , n}, is recorded and
transmitted to a fusion center for processing. Also,
suppose the locations of the binary radiation measurement sensors are known. The question being asked is

whether we can uniquely determined the parameters
 (18) of (8) from the given information.

5

Theorem 2. Suppose a radiation source on a
parabolic trajectory, as defined in (8), triggers n = 6
sensors such that:
• the times corresponding to the shortest distance
of approach, t∗ij , j ∈ {1, · · · , 6}, are available.
• the locations of the centers of the radiation sensors are independent and identically distributed
in R2 .
Then with probability being equal to one, the parabola
(8) is uniquely determined based on the n = 6
measurement sensor point locations (xj , yj ), j ∈
{1, · · · , 6} and the times of shortest distance of approach, t∗ij , j ∈ {1, · · · , 6}, information.
Proof. Without loss of generality, suppose x1 = y1 =
y2 = 0. Again, we retain all notations, to preserve
clarity. Also consider toi = 0. Consequently, from
(10):

 ∗2 ∗2
αi +βi
3 ∗ ∗2
1 ∗ ∗3
∗
t∗i1
+ yoi
2 γi tij + 2 βi tij +
γ∗
i

α∗
+ γ ∗i (x∗oi
i

− xj ) +

βi∗
∗
γi∗ (yoi

− yj ) = yj t∗ij

(22)

∀j ∈ {1, · · · , n}. In matrix form, (22) becomes:

∗
i ∗ + βi y ∗


∗x
0
γ ∗ oi 
 γi oi
i
1 ∗




γ
0


i
2
0 



3 ∗
y3 t∗ 

βi

i3
2


y3 

∗


∗2
∗2
y4 ti4 

  αi +βi + y ∗ 
=
∗
y4  


oi
∗
γ

i
y3 ti3 

∗


α


∗ 
i

y5  
−

y5 ti5 


γ∗
i

y6 
βi∗
y6 t∗
i6
− γ∗
}
i
{z
}
|
 α∗


1

1

1


1

1

1
|

t3∗
i1

t2∗
i1

t∗
i1

0

t3∗
i2

t2∗
i2

t∗
i2

x2

t3∗
i3

t2∗
i3

t∗
i3

x3

t3∗
i4

t2∗
i4

t∗
i4

x4

t3∗
i5

t2∗
i5

t∗
i5

x5

t3∗
i6

t2∗
i6

t∗
i6

x6

{z
Ao

0



Xo

With some algebraic manipulations, it can be shown
that:

Γ

x4
x5
−
κ5
κ4

where κm =



3
Q

y4
y6
−
κ6
κ4




−

x4
x6
−
κ6
κ4

(tim − tik ) and Γ =



y4
y5
−
κ5
κ4

Q

sensors. We will now consider the practical scenario
with noise in the observed arrival times of the photons.
A. Scalable tracking of radiation source on piece-wise
linear trajectories
From Theorem 1, we have shown that given three
generically placed radiation sensors such that they
are non-coincident, we can track a linear trajectory
precisely with probability being 1 if the sensor measurements are noise free. In this section, we will
present a robust and scalable algorithm in terms of
noisy measurement and number of sensors being used
respectively. Recall that, other results on tracking
with binary sensors on piece-wise linear trajectories
required 2n−1 least squares problems and comparisons
to come up with the true solution [2] . In our approach,
we will show that only two least squares problems are
required for all n ≥ 3. Observe that (5) can be written
in matrix form as:
x1
 x2


 .
 .
 .
xn
|


y1
y2
.
.
.
yn
{z

 ∗



sin θi∗
1
ti1 − toi
s∗
 t∗ − toi 


i
1
 i2








=
.
.
cos θi∗
.
.



s∗
.
.



i
∗ ∗
∗ ∗
1
∗
−
(sin
θ
x
+
cos
θ
y
)
t
−
t
∗
1
i oi
i oi
oi
s
in
i
|
{z
}
{z
}
}|
Y1

X1

A1

(24)

The least squares solution can be used to form:
X1 = (AT1 A1 )−1 AT1 Y1

(25)

and note that:
ŝ∗i =

q

X21 (1) + X21 (2)



θ̂i∗


= arctan

X1 (1)
X1 (2)

(26)


(27)

(t∗ik − t∗ij ).

From (20), we can formulate:




α2(1,2) β2(1,2)
This means for a degenerate solution:
γ2(1,2)
 
 .
.. 
 . 
xoi
y6 x4
x6 y5
x6 y4
x5 y4 − x4 y5
y6 x5
 ..
.. 
. 
−
−
−
=
(23)
  


κ(5,6)
κ(4,6)
κ(5,6)
κ(4,6)
κ(5,6)
  = 



 α2(1,n) β2(1,n) 
(28)
γ

2(1,n) 

 yoi
3
Q
∗
∗
sin
θ̂
cos
θ̂
X1 (3)
where κ(m,n) =
(tij − tik ). Now, suppose we
− ŝ∗ i − ŝ∗ i | {z }
k=1
i
i
| {z }
|
{z
} X2
j∈{m,n}
Y2
A2
know {xj , yj }, j ∈ {1, · · · , 5}, {x6 , y6 } will have
to lie on a one-dimensional hyperplane in a two- where
dimensional probability space. Since {x6 , y6 } are indeα2(k,j) = 2(xk − xj ) cos2 θ̂i∗ − 2(yk − yj ) sin θ̂i∗ cos θ̂i∗
pendent and identically distributed, with probability 0,
2 ∗
∗
∗
(23) will not be realized meaning with probability be- β2(k,j) = 2(yk − yj ) sin θ̂i − 2(xk − xj ) sin θ̂i cos θ̂i
ing one, the parabolic trajectory is uniquely determined

ŝ∗2
i
γ
=
(tik2 − tik1 )2 − (tij2 − tij1 )2 +
2(k,j)
from (23). Notice that from X0 , all the parameters of
4
the parabola are uniquely determined.
(yk sin θ̂i∗ − xk cos θ̂i∗ )2 − (yj sin θ̂i∗ − xj cos θ̂i∗ )2
k=1

1≤j≤3
4≤k≤6

VI. ROBUST AND SCALABLE NUMERICAL
SOLUTION TO TRACKING OF RADIATION SOURCES
ON PIECE - WISE LINEAR AND PARABOLIC
TRAJECTORIES
Up till this point, we have been working with the
expectations of the received signals at the radiation

The least squares solution then becomes:
X2 = (AT2 A2 )−1 AT2 Y2 .

(29)

and note that the estimates: x̂oi = X2 (1), and ŷoi =
X2 (2). Notice that we have used the least squares
exactly twice.

6

B. Noise in recorded times for radiation source on
piece-wise linear trajectories
We now consider the robustness with reference to
the presence of noise. Recall that the arrival time
of each photon is at each sensor is exponentially
distributed. Now suppose the following proposition
holds in the noisy case:

∆y1,2
..
.
∆y1,n


(X∗2

− X2 ) =

(AT2 A2 )−1 AT2







 (31)





∗
X 1 (3) − X̂1 (3)
{z
}
|
∆Y2

Proposition 1. The recorded time tijk −toi , k ∈ {1, 2}
corresponding to the earliest and latest sensing by the
j th sensor and the ith piece
 trajectory
 of the linear
T
.
obeys: tijk − toi ∼ Erlang λT , t∗ λ−t
oi
ijk

Proof. Suppose that the λT arrival times in the interval
1
2
corresponding to tijk are denoted τijk
< τijk
< ··· <
λT
λT
1
τijk , τijk − τijk ≤ 1, where the superscripts are just
λT
P
q
for labelling purposes. Suppose λ1T
τijk
− toi ≈
q=1

q
t∗ijk − toi . Notice that the τijk
poisson arrival times
are exponentially distributed with approximate rate
parameter λT . Subsequently,
 it is fairly easy to show
T
that tijk − toi ∼ Erlang λT , t∗ λ−t
.
oi

where

ŝ∗2
i
(t∗i12 − t∗i11 )2 − (t∗ij2 − t∗ij1 )2 −
4
(32)

ŝ∗2
i
2
2
(ti12 − ti11 ) − (tij2 − tij1 )
4
Suppose the followed ordered statistics hold:
∆y1,j =

ti22 − ti21 ≤ · · · ≤ t∗i,b n c−1,2 − tib n2 c−1,1 ≤ t∗i12 − ti11
2

≤ t∗i,b n c+1,2 − ti,b n2 c+1,1 ≤ · · · ≤ tin2 − tin1
2

From (31), we have the following lemma:
Lemma 2. Under Assumption 1 and (31)
lim (X∗2 − X2 ) =→ [0 0]T .

ijk

Corollary 1. The recorded time of shortest
approach,


t∗ij − toi obeys: t∗ij − toi ∼ Erlang 2λT , t∗2λ−tToi .
ij

Consequent to proposition 1, the equations for estimation of the linear trajectory has to be updated.
From (24) - (25) the estimation error in {s∗i , θi∗ } can
be characterized as:
 ∗

ti1 − ti1


..

(30)
(X∗1 − X1 ) = (AT1 A1 )−1 AT1 
.


∗
tin − tik
{z
}
|

k→∞

Proof. Observe that the entries of ∆Y2 , with the
exception of the last row, are zero mean Laplacian
random variables. The last entry is also zero mean
distributed because it is an algebraic sum of xj and yj
components. Thus:
lim AT2 ∆Y2 → 0.

k→∞

The result therefore follows from this observation.
Corollary 3. Under Assumption 1 and (31)
∗
lim [x∗oi − x̂oi , yoi
− ŷoi ]T → [0 0]T .

k→∞

∆Y1

From (30), the following lemma arises:

C. Scalable tracking of radiation source on piece-wise
parabolic trajectories

Lemma 1. Under Assumption 1 and (30)
lim (X∗1 − X1 ) = ∆X1 → [0 0 0]T .

k→∞

Proof.

lim ∆X1 → diag

k→∞

 ∗

ti1 − ti1


1 1
1 T
..


,
,
1
A
.
1


σx2 σy2
k
t∗in − tik
|
{z
}
∆Y1

Since the {xj , yj } elements of AT1 are i.i.d. and zero
mean, the result follows.
Corollary 2. Under Assumption 1 and (30)
lim

k→∞

[s∗i

−

ŝi , θi∗

From Theorem 2, we have shown that given six
generically placed radiation sensors such that they
are non-collinear, we can track a parabolic trajectory
precisely with probability being 1, if we are given the
exact time of shortest distance of approach. In this
section, we will present a robust and scalable algorithm
in terms of noise and number of sensors being used.
Recall from (22):
1
.
.
.



1
|


3
(t∗
i1 − toi )

2
(t∗
i1 − toi )

t∗
i1 − toi

x1

y1

.
.
.

.
.
.

.
.
.

.
.
.

.
.
.

.
. 3
(t∗
in .)

.
. 2
(t∗
in .)
{z

.
.
t∗
in .

xn

yn





 X3 = Y3


}

A3

T

T

− θ̂i ] → [0 0] .

We now need to show that the estimates of
{xoi , yoi } also goes to zero in the limit. From (28)
∗
the estimation error in {x∗oi , yoi
} can be characterized
as:

The least squares solution is:
X3 = (AT3 A3 )−1 AT3 Y3
and note that:
∗

γ̂i = 2X3 (2)

(33)

7

∗

VII. U PPER BOUND ON ACHIEVABLE ERROR

α̂i = −2X3 (2)X3 (5)

VARIANCE OF ESTIMATED PARAMETERS

∗
β̂i

∗

ŷoi
∗

x̂oi = −

= −2X3 (2)X3 (6)


2
2
= X3 (4) − 2X3 (2) X3 (5) + X3 (6)



 X (6)
X3 (1)
3
2
2
− X3 (4) − 2X3 (2) X3 (5) + X3 (6)
.
X3 (5)
X3 (5)

The least squares solution easily scales with number
of measurement sensors.
D. Noise in recorded times for radiation source on
piece-wise parabolic trajectories
We now consider the presence of noise in observed
time stamps. The following proposition follows from
proposition 1:
Proposition 2. The recorded time tij corresponding
to time of shortest approach to the the j th sensor and
the ith piece of the parabolic
 unique and
 trajectory is
obeys: tij − toi ∼ Erlang 2λT , t∗2λ−tToi .
ij

From (33) the estimation error in {s∗i , θi∗ } can be
characterized as:

y1 (t∗i1 − ti1 )
 y2 (t∗ − ti2 ) 
i2


∗
T
−1 T 

(X3 − X3 ) = (A3 A3 ) A3 
..

.


yn (t∗in − tik )
|
{z
}


(34)

We will now characterize the upper bound on the
Cramér-Rao lower bounds on two of the parameters
of the linear trajectory. We will not tackle the bounds
on the parabolic trajectories because it is intractable to
characterize the time of shortest approach in terms of
the parameters of the parabola only. Hence the exact
analytical expressions for the entries of the Fisher
information matrix is not available.
For the linear trajectories, observe also, that the
estimation of the parameters {xoi , yoi } depend on
the difference between the transition times {tij1 −
toi , tij2 − toi }. Again, we do not have analytic expressions for these transition times in terms of only
the parameters of the line. We can also show that
using the time of shortest distance of approach only to
estimate the {xoi , yoi } parameters, the resulting Fisher
information matrix is rank deficient, confirming that
the estimates of {xoi , yoi } is unbounded if only the
tij data is used. The estimates of {s∗i , θi∗ } is however
different. We will use tij − toi to upper bound the
Cramér-Rao lower bound. This is because we are
using a derivative of the actual recorded data, the
{tij1 −toi , tij2 −toi } data. The joint probability density
function of the received tij − toi recordings, or the
mean of the {tij1 − toi , tij2 − toi } times becomes:

n
Y

∆Y3

lim (X∗3 − X3 ) = ∆X3 → [0 0 0 0 0 0]T .

n log

k→∞

Proof.


yk (t∗ik − tik )



k=1
P

 n
3
∗
yk (tik − tik )(tik − toi ) 

k=1

P

 n y (t∗ − t )(t − t )2 

k ik
ik
ik
oi 


∆X3 = (AT3 A3 )−1 k=1

n
 P
∗
yk (tik − tik )(tik − toi ) 


 k=1



n
P


∗
yk xk (tik − tik )




k=1
n


P 2 ∗
yk (tik − tik )
k=1

lim ∆X3 →

k→∞

(AT3 A3 )−1

h

0

0

0

0

0

T

(tij − toi )2λT −1 e

−

2λT (tij −toi )
t∗ −toi
ij

2λT − 1

(35)

Consequently, the log likelihood function, denoted
L(si ,θi ,xoi ,yoi ) becomes:

Lemma 3. Under Assumption 2 and (34)

n
P

2λ

j=1

From (34), the following lemma follows:



2λT
t∗ −toi
ij

0

iT

.

The results stems from the fact that {xk , yk , t∗ik −
tik }, k ∈ {1, · · · , n} are all zero mean random
variables.
Corollary 4. Under Assumption 2 and (34)
∗
limk→∞ [γi∗ −γi , s∗i − ŝi , θi∗ − θ̂i , x∗oi −xoi , yoi
−yoi ]→
[0 0 0 0 0 0].

n
X
(2λT )2λT
log (tij − toi )
+ (2λT − 1)
2λT − 1
j=1

− 2λT
− 2λT

n
X
j=1
n
X
j=1

log

1
∗
((xj − x∗oi ) sin θi∗ + (yj − yoi
) (36)
s∗i

s∗i (tij − toi )
∗ ) cos θ ∗ )
((xj − x∗oi ) sin θi∗ + (yj − yoi
i

From (36), the entries of the Fisher information
matrix are found as:

 2
∂ L(si ,θi ,xoi ,yoi )
2nλT
(37)
= ∗2
−E
∂s2i
si

∂ 2 L(si ,θi ,xoi ,yoi )
−E
=
∂si ∂θi
(38)
n
∗
λT X (xj − x∗oi ) cos θi∗ − (yj − yoi
) sin θi∗
−2 ∗
∗ ) cos θ ∗
si j=1 (xj − x∗oi ) sin θi∗ + (yj − yoi
i


and

∂ 2 L(si ,θi ,xoi ,yoi )
=
−E
∂θi2
(39)
n
∗
X
((xj − x∗oi ) cos θi∗ − (yj − yoi
) sin θi∗ )2
2λT
∗ ) cos θ ∗ )2
((xj − x∗oi ) sin θi∗ + (yj − yoi
i
j=1


8

From (37) – (39), the upper bound on the estimation
errors in s∗i and θi∗ are as follows:
∗

2

ksi − ŝi k ≤
argmin

n 
∗
∗
∗ 2
X
(xj − x∗
s∗2
oi ) cos θi − (yj − yoi ) sin θi
i
∗
∗
∗
∗
2DλT j=1 (xj − xoi ) sin θi + (yj − yoi ) cos θi

1. On each parabola, only six sensors are used to
estimate the parabolic joins. The estimated parabola
is the black curve within the boundaries of the large
colored curves. The two figures above illustrate that

and
∗

2

kθi − θ̂i k ≤
argmin

1
2DλT

(40)

where
D=

n
n X
X
j=1 k6=j

∗
∗
∗
(xj − x∗
oi ) cos θi − (yj − yoi ) sin θi
×
∗ + (y − y ∗ ) cos θ ∗ )2
)
sin
θ
((xj − x∗
j
i
oi
i
oi

. =0.1415, , =1.0894, - =12.4524, xo =-1000, yo =-1000
. =-0.082278, , =-5.7899, - =-12.4164, xo =1000, yo =1000
sensors
triggered sensors

(41)

(xj − xoi )(yk − yoi ) − (yj − yoi )(xk − xoi )
∗
∗
∗
(xk − x∗
oi ) sin θi + (yk − yoi ) cos θi

Remark 1. Observe that the error bounds on the
estimates are inverse law proportional to λT . In fact,
the signal-to-noise-ratio,(SNR), is easily characterized
in terms of λT . The expected value of the transition
times are t∗ijk −toi , k ∈ {1, 2} whiles the variances are
2
(t∗
ijk −toi )
.
λT

Using the so called conventional definition
of SNR as the inverse coefficient of variation:
p
SN R = λT .
We will use this characterization of the SNR to illustrate the performance of our algorithm in the simulations section.
VIII. S IMULATIONS
We consider a comprehensive set of simulations for
both linear trajectories and parabolic trajectories. First
we consider the noise free case, where the exact time
stamps are available. Fig 1 shows four linear trajectories being tracked with zero noise in the recorded
time stamps. On each line, only three sensors are used
to estimate the linear joins. The estimated line is the
black line within the large colored line boundaries.
Fig. 2 also shows the nonlinear counterpart of Fig.

s =12.5, θ =45◦ , xo =-1000, yo =-500
s =13.7, θ =153.4349◦ , xo =500, yo =1000
s =14.2, θ =236.3099◦ , xo =1000, yo =0
s =16.2, θ =347.3196◦ , xo =-500, yo =-1000
sensors
triggered sensors

Fig. 1: Piece-wise linear tracking with no noise in
recorded time stamps

Fig. 2: Piece-wise parabolic tracking with no noise in
recorded time stamps
in the noise free case, our algorithm achieves perfect
localization of the trajectories of the radiation sources.
It is however clear that in practice, we would not have
noise free time stamps. We turn our attention now to
simulations with noise.
From Fig. 3a – Fig. 4b, we present results of 105
Monte-Carlo simulations to illustrate the robustness
of our algorithm to the presence of real noise. In all
cases we present three different number of sensors on
the same plot: {20, 50, 500}. In particular, we show
the performance of our algorithm in the noisy case.
The parameters {s, θ} are compared to our derived
upper bound of the Cramér-Rao lower bound. Here,
all sensors are placed in a 2km by 2km square
grid centered about zero. There are ≈ 1000 sensors
whose locations are uniformly distributed within the
square grid. The true parameters being estimated are
{s∗ , θ∗ , x∗o , yo∗ } = {30, 45◦ , −1000, 500}. In all cases,
the minimum distance from which a sensor is triggered
is 170m. The expected background noise is maintained
at λb = 1 photons per second. For all situations,
αs = 0.0068. λs is varied to keep the minimum
distance for triggering of the sensors same for all SNR
levels, which translates to the same expected transition
time stamps for equitable comparison of performance.
Remark 2. Notice that the SNR cannot go beyond 0
because the minimum allowable count to trigger the

9

sensor is 1 photon.
In all simulations, it is seen that at an SNR of
about 10dB, the performance for all the variables
being estimated is good, with a percentage error well
below or around 1%. From Fig. 5a – Fig. 7a, we
son=20
son=50
son=500
CRLBson=20
CRLBson=50
CRLBson=500

10 0

10 -1

θon=20
θon=50
θon=500
CRLBθon=20
CRLBθon=50
CRLBθon=500

10 0

10 -2

∥θ−θ̂i ∥2
∥θ∥2

10 -3

10 -4

1
n

1
n

n
!

n
!

i=1

i=1

∥s−ŝi ∥2
∥s∥2

10 -2

10 -4
10 -6

Remark 3. The simulation results for the parabolic
trajectories gives an insight to realistic values of
number of sensors or thresholds to use. We either end
up using a very high number of sensors or a very
high threshold. Note that very high thresholds mean
all sensors will almost entirely be lined up along the
trajectory of the source. This will make the observation
matrix with the sensor locations column rank deficient
and affect the inversion because of bad condition
numbers. A high threshold on the other hand will mean
weak signals will escape detection. A balance between
number of sensors and threshold value will have to be
made in practice.

10 -5
10 -8

10 3

10 -6
10 2
0

5

10

SN R = 10 log

15

10 2

20

λT
10 1

(b) Estimation of θ

10 1

10 0

∥β−β̂i ∥2
∥β∥2

Fig. 3: Performance of s and θ in the presence of noise
for linear trajectories.

i=1

(a) Estimation of s

√

10 -1

10 3
xon=20
xon=50
xon=500

10 -3

yon=20
yon=50
yon=500

10 2

10 -1

10 -2

10 -2

10 2

10 0

n
!

20

1
n

15

λT

∥α−α̂i ∥2
∥α∥2

√

n
!

10

SN R = 10 log

i=1

5

1
n

0

10 -3

αn=20
αn=50
αn=200

14

16

10 1

√24
SN R = 10 log λT
18

20

22

26

28

30

βn=20
βn=50
βn=200

14

16

18

20

22

SN R = 10 log

√24
λT

26

28

30

10 1

(a) Estimation of α

10 0

(b) Estimation of β

∥yo −ŷoi ∥2
∥yo ∥2

Fig. 5: Performance of α and β in the presence of
noise for parabolic trajectories.

10 -1

n
!

i=1

10 -2

1
n

1
n

n
!

i=1

∥xo −x̂oi ∥2
∥xo ∥2

10 0
10 -1

10 -2

10 -3
10 -3
10 -4
10 -4
10 -5
10 0

10 -5

10 2
5

10

SN R = 10 log

√

15

20

λT

10 -1
10 1

(b) Estimation of yo
∥yo −ŷoi ∥2
∥yo ∥2

Fig. 4: Performance of xo and yo in the presence of
noise for linear trajectories.

10 -2

10

10 0

n
!

(a) Estimation of xo

0

i=1

λT

20

-3

1
n

15

∥xo −x̂oi ∥2
∥xo ∥2

SN R = 10 log

√

n
!

10

i=1

5

1
n

0

10 -1

10 -4
10 -2

present results of 105 Monte-Carlo simulations on
tracking of parabolic trajectories. Again, we present
three different number of sensors on the same plot:
{20, 50, 200}. Again, all sensors are placed in a 2km
by 2km square grid centered about zero. There are
≈ 500 sensors whose locations are uniformly distributed within the square grid. The true parameters being estimated are {alpha∗ , β ∗ , γ ∗ , x∗o , yo∗ } =
{29.89, 2.61, 0.82, −1000, −1000}. In all cases, the
minimum distance from which a sensor is triggered
is 170 units. The expected background noise is maintained at λb = 1 photons per second. For all situations,
αs = 0.0068. λs is varied to keep the minimum
distance for triggering of the sensors same for all SNR
levels, which translates to the same expected transition
time stamps for equitable comparison of performance.
In all simulations, it is seen that at an SNR of about
20dB, the performance for all the variables being
estimated when using the number of sensors are 50
or 200 is good, with a percentage error well below or
around 5–1%.

10 -5

10 -3

xon =20
xon=50
xon=200

14

16

18

20

22

√

24

SN R = 10 log

26

28

30

yon =20
yon=50
yon=200

14

(a) Estimation of xo

16

18

20

22

SN R = 10 log

λT

√24
λT

26

28

30

(b) Estimation of yo

Fig. 6: Performance of yo and xo in the presence of
noise for parabolic trajectories.

IX. C ONCLUSION
We have considered robust and scalable algorithms
for tracking of piece-wise linear and parabolic trajectories using binary proximity sensors. We have
shown that, with piece-wise linear trajectories, three
generically placed sensors suffice to track a single
linear piece precisely in the noise free case. We have
presented analytical and simulated results to show the
robustness of our least squares algorithm. We have
shown that, even with unknown statistics of the source,
we require far fewer least squares problems, exactly
2n−1 − 2 less least squares problems than the previous

10

10 3

10 2

10 0

1
n

n
!

i=1

∥γ−γ̂i ∥2
∥γ∥2

10 1

10 -1

10 -2

10 -3

γn=20
γn=50
γn=200

14

16

18

20

22

SN R = 10 log

√24
λT

26

28

30

(a) Estimation of γ

Fig. 7: Performance of γ in the presence of noise for
parabolic trajectories.

results in [2]. We have also shown that the number
of sensors is one less than the number used in [2]
and [4] for exact tracking in the noise free case.
Further, we have derived a theoretical upper bound on
the achievable error variance for the constant speed
and elevation angle of the linear trajectory. We have
also extended our work to parabolic trajectories, which
mimic better trajectories of automobiles on highways.
We have shown that with parabolic trajectories no
more than six generic sensors are required in the
noise free case. Our solution for parabolic trajectories
however does not utilize the time difference of between
entering and leaving a sensors sensing range. The total
number of sensors may or may not reduce when that
information is incorporated.

R EFERENCES
[1] J. Aslam, Z. Butler, F. Constantin, V. Crespi, G. Cybenko,
and D. Rus. Tracking a moving object with a binary sensor
network. In Proceedings of the 1st international conference on
Embedded networked sensor systems, pages 150–161. ACM,
2003.
[2] E.-w. Bai, H. E. Baidoo-Williams, R. Mudumbai, and S. Dasgupta. Robust tracking of piecewise linear trajectories with
binary sensor networks. Automatica, 61:134–145, 2015.
[3] H. E. Baidoo-Williams. Novel techniques for estimation and
tracking of radioactive sources. 2014.
[4] H. E. Baidoo-Williams, S. Dasgupta, R. Mudumbai, and
E. Bai. On the gradient descent localization of radioactive
sources. IEEE Signal Processing Letters, 20(11):1046–1049,
2013.
[5] Y. Busnel, L. Querzoni, R. Baldoni, M. Bertier, and A.-M.
Kermarrec. On the deterministic tracking of moving objects
with a binary sensor network. In International Conference
on Distributed Computing in Sensor Systems, pages 46–59.
Springer, 2008.
[6] J. W. Howse, L. O. Ticknor, and K. R. Muske. Least squares
estimation techniques for position tracking of radioactive
sources. Automatica, 37(11):1727–1737, 2001.
[7] W. Kim, K. Mechitov, J.-Y. Choi, and S. Ham. On target
tracking with binary proximity sensors. In IPSN 2005. Fourth
International Symposium on Information Processing in Sensor
Networks, 2005., pages 301–308. IEEE, 2005.
[8] A. H. Liu, J. J. Bunn, and K. M. Chandy. Sensor networks
for the detection and tracking of radiation and other threats in
cities. In Information Processing in Sensor Networks (IPSN),
2011 10th International Conference on, pages 1–12. IEEE,
2011.

[9] R. J. Nemzek, J. S. Dreicer, D. C. Torney, and T. T. Warnock.
Distributed sensor networks for detection of mobile radioactive
sources. IEEE Transactions on Nuclear Science, 51(4):1693–
1700, 2004.
[10] T. Nguyen, D. Nguyen, H. Liu, and D. A. Tran. Stochastic
binary sensor networks for noisy environments. International
Journal of Sensor Networks, 2(5-6):414–427, 2007.
[11] N. Shrivastava, R. M. U. Madhow, and S. Suri. Target
tracking with binary proximity sensors: fundamental limits,
minimal descriptions, and algorithms. In Proceedings of the
4th international conference on Embedded networked sensor
systems, pages 251–264. ACM, 2006.
[12] N. Shrivastava, R. Mudumbai, U. Madhow, and S. Suri. Target
tracking with binary proximity sensors. ACM Transactions on
Sensor Networks (TOSN), 5(4):30, 2009.
[13] Z. Wang, E. Bulut, and B. K. Szymanski. Distributed energyefficient target tracking with binary sensor networks. ACM
Transactions on Sensor Networks (TOSN), 6(4):32, 2010.

