Performance study of node placement in sensor networks
Mika ISHIZUKA and Masaki AIDANTT Information Sharing Platform Labs, NTT Corporation
3-9-11, Midori-Cho Musashino-Shi Tokyo 180-8585 Japan{ishizuka.mika, aida.masaki}@lab.ntt.co.jp
Abstract
The expectations for sensor networks are growing. Oneof the most important issues in sensor networks is to evaluate the fault tolerance and built technology to improveit, because sensor nodes are prone to fail and have limited power capacity. So far, research on the fault tolerance
has focused on battery exhaustion. Since placement affects
whether there are nodes that can sense and routes to thebase station, placement of sensor nodes is also important.
However, there has been little research on the placement ofsensor nodes and all of it is based on deterministic placement , which is not realistic when many sensor nodes areplaced in a large area. In such a situation, stochastic placement is needed. Therefore, this paper evaluates the tolerance against both random failure and battery exhaustion
from the viewpoint of stochastic node placement.

1. Introduction
Recent advances in electronics such as power saving
LSIs have led to small sensors with communication capability. Since a sensor network composed of these sensor nodes
enables wide area and large-scale information gathering, expectations for sensor networks are growing.
Although a sensor network is a kind of ad hoc network,
it differs in some ways and has new issues [1]. One issue isto evaluate the fault tolerance and build technology that can
improve it, because sensor nodes are prone to fail and have
limited power capacity.
So far, research on fault tolerance has focused on battery exhaustion. The main research topics are the powersaving mode of the MAC protocol [9, 11, 10] and energy
efﬁcient route selection [4, 3, 7]. Since placement affects
whether there are nodes that can sense and routes to thebase station, the placement of sensor nodes is also important. However, there has been little research on the placement of sensor nodes and all of it is based on deterministic
placement [5, 2], which is not realistic when many sensor

nodes are placed in a large area. In such a situation, stochastic placement is needed.
Therefore, this paper evaluates the fault tolerance fromthe viewpoint of stochastic node placement. Moreover, thispaper deals with the tolerance against both random failure
and battery exhaustion. This is because we consider that tolerance against random failure is also important since sensor
nodes are prone to fail.

2. Background2.1. Communication ModelIn this paper, we consider applications where we cannot know the location of the target in advance (e.g. monitoring a vehicle in a forest). A target is generated in region
A. A sensor node can explore a target only if it is in sensing range of the node. A sensor node can transmit data to or
receive data from other sensor nodes within the radio transmission range. Generally, the sensing range is much smaller
than the radio transmission range. When a target is generated, all the sensor nodes that have it within their sensing
ranges send the sensory information to the base station during period D. Here, the data sending rate is so small that nodata collisions occur. Routes are selected based on the minimum hop strategy. An example of the sensing process is illustrated in Fig. 1.
A sensor node consumes its battery energy to transmit(Et [J/bit]) and to receive bits (Er [J/bit]). When a sensor
node exhausts its battery energy, all the functions of the sensor node stop and an alternative route is selected for the remaining information.

2.2. Placement of sensor nodes
When a lot of sensor nodes are placed in a large area,
it is not realistic for someone to place them all at predetermined positions. Instead, stochastic placement is needed.
In this paper, we consider three typical types of stochastic
sensor-placement.

Proceedings of the 24th International Conference on Distributed Computing Systems Workshops (ICDCSW’04)
0-7695-2087-1/04 $20.00 © 2004 IEEEAn example is illustrated in Fig. 3, where the numberof sensor nodes is 400 and they are within 500 [m] of
the base station.

Aradio transmission range

R-random placement Finally, we propose a new method
called the R-random placement. Sensor nodes are uniformly scattered in terms of the radius and angular direction from the center, which coincides with the basestation.
When all the sensor nodes are within range R of
the base station, the p.d.f of sensor-positions in polarcoordinates (r, θ) is

a sensor nodea targetthe base station

sensing range

routes to the base stationf (r, θ) =Figure 1. Example of sensing.

In (4), we set the base station to the origin without losing generality. An example of R-random placement is
illustrated in Fig. 4, where the number of sensor nodes
is 400 and all of them are within 500 [m] of the basestation.
Note that density of sensor nodes nearer the basestation is higher in R-random placement, though p.d.fof sensor-positions does not depend on radius and angle. Actually, ρ(r1 , θ1 ), the density of sensor node at
position (r1 , θ1 ), is given as follows:
Let S(a ≤ r ≤ b, c ≤ θ ≤ d) be the area of theregion X = {a ≤ r ≤ b, c ≤ θ ≤ d}, thenSimple diffusion The simplest way to distribute sensornodes is to scatter them from the air. We call this simple diffusion. Since all the information must reach thebase station, we center the distribution on the base station.
If weight of sensor nodes is light, they will havehigh air resistance. This randomizes their placement, which can be described by diffusion equation. Since solution of diffusion equation forms thetwo-dimensional normal distribution, f (x), the probability density function (p.d.f) of sensor-positionx ∈ R2 is 1

1

The probability of a sensor being within region A = {X1 ≤x1 , X2 ≤ x2 } canwritten xbe
 x1 by using p.d.f as follows: P {X1 ≤2
f (x1 , x1 )dx1 dx2 .
x1 , X2 ≤ x2 } =
−∞

1

=

δr→0 δθ→0 πR(2r1 + δr)

(2)

(3)

θ1

f (r, θ)dθdrδr→0 δθ→0 S(r1 ≤ r ≤ r1 + δr, θ1 ≤ θ ≤ θ1 + δθ)= lim lim

Constant placement In many papers, sensor nodes areplaced so that their density is constant. We call thisconstant placement. The p.d.f of sensor-positions is r1 +δr  θ1 +δθr1

lim lim(1)

In (1), c ∈ R2 is the position at ground which is justunder the point where sensor nodes are scattered andσ 2 is the variance of the distribution. The variance isdetermined by various factors (e.g., shape or weight ofsensors, or the hight at which sensors are released).
An example of simple diffusion is illustrated inFig. 2. Here, the number of sensor nodes is 400 andthe variance is set so that 99% of them may be placed
within 500 [m] of the base station.

1.
f (x) =
|A|

ρ(r1 , θ1 ) =

1
.
2πRr1

(5)

1600
a sensor nodea base station
1400
1200
Y [m]

1
f (x) =h(x − c),
2πσ 2
r2

h(r) = exp(− 2 ).
2σ

1
, 0 ≤ r ≤ R, 0 ≤ θ < 2π.(4)
2πR

1000
800
600
400
400

600

800

1000

1200

1400

X [m]

Figure 2. Example of simple diffusion.

−∞

Proceedings of the 24th International Conference on Distributed Computing Systems Workshops (ICDCSW’04)
0-7695-2087-1/04 $20.00 © 2004 IEEE

1600

3. Simulation Settings
1600
a sensor nodea base station

3.1. Setting of targets

1400

The sensing targets were randomly generated within region A, a circle with a radius of 500 [m] centered on thebase station.
For the evaluation of tolerance against battery exhaustion, we set the target sensing period to be exponentiallydistributed with an average of 72 [min].

Y [m]

1200
1000
800
600
400
400

3.2. Setting of sensor nodes
600

800

1000

1200

1400

1600

X [m]

Figure 3. Example of constant placement.

1600
a sensor nodea base station

The number of sensor nodes was 250. For constant and
R-random placement, all the sensor nodes were placed inregion A. For simple diffusion, the variance was set so that
99% of sensor nodes would be placed within region A.
The sensing range was set to 60 [m] and the the radiotransmission range is to 100 [m]. The data sending rate was
1.1 [kbps], which is enough low to avoid collisions. Energy
consumption was 3.3e-07 [J/bit] to transmit bits and 1.9e07 [J/bit] to receive [6]. The initial energy of each sensor
node was 20 [J].

1400

3.3. Performance criteria
Y [m]

1200
1000
800
600
400
400

600

800

1000
X [m]

1200

1400

1600

Figure 4. Example of R-random placement.

Note that the normal distribution can be used as a basis function. Therefore, any p.d.f of sensor-position can beapproximated as a superposition of normal distributions asfollows [8]:f (x) =N
pi h(x − ci ).

(6)

i=1

That is, repeated simple diffusion can lead to any stochastic
sensor-placements.

In this subsection, we describe how to evaluate the fault
tolerance. We consider the sensing of a target is successful when at least one sensor node is within sensing range ofit and at least one of these nodes has a route to the base station.
In order to evaluate the tolerance against battery exhaustion, we consider the case where the number of sensor nodes
that exhaust their battery energy increases as the number ofgenerated targets increases.
As for performance metrics, both the x%-lifetime andthe cumulative number of received bits are used. Here, x%lifetime is deﬁned as the time (i.e., number of targets generated) when the virtual sensing-success-ratio drops below
x%. The virtual sensing-success-ratio means the probability that sensing a target is successful in the current state.
Here, we say “virtual”, because it does not mean the actual
sensing-success-ratio but the probability of sensing is successful if a target is generated in the current state. It is calculated after target sensing is completed.
Cumulative number of received bits is incremented when
the base station receives new data (note that we increment
them only once for he same data though multiple sensor
nodes send the same data). A longer lifetime means higher
tolerance against battery exhaustion and more cumulative
received bits means a lower ratio of missing the target. In
each simulation, 200 targets were generated and the simulation was repeated ﬁve times.

Proceedings of the 24th International Conference on Distributed Computing Systems Workshops (ICDCSW’04)
0-7695-2087-1/04 $20.00 © 2004 IEEE

600
500
Received data [Mbit]

In order to evaluate the tolerance against random failure,
we considered the case where each node fails with the probability of p. The sensing-success-ratio was evaluated forvarious values of p. In each simulation, 1000 targets weregenerated and the simulation was repeated 30 times. The
performance metrics was the the virtual sensing-successratio.

4. Simulation Results

400
300
200
Constant
R-random
Simple Diffusion

100
04.1. Tolerance against battery exhaustion

0

20

40

60

80

100

120

140

160

180

Number of objects before the success-ratio drops below 5%

To show the transient behavior, we plot the number ofcumulative received bits in Fig. 5. On the left, they are lowest for simple diffusion. As the number of objects increased,
the number of received bits in constant placement saturated
ﬁrst. The number of received bits was higher in R-random
placement in almost all regions.
Figure 6 shows 5%-lifetime and the number of cumulative received bits corresponding to the lifetime. R-random
placement had the longest lifetime and the most received
bits.
600
Constant
R-random
Simple Diffusion

fusion has the highest probability of having no sensors in
any regions, while constant placement has the highest probability of having no routes in Fig. 8. In Fig. 8, the numberof alive nodes nearer the base station is much lower, especially for simple diffusion and constant placement. That is
why the probability of there being sensors within sensing
range is high and the lifetime is long in R-random placement.

400

1

300
200
100
0
0

20

40

60

80

100 120 140 160 180 200

Number of generated targets

Figure 5. Cumulative received bits.

Probability of having no sensors

Received data [Mbit]

500

Figure 6. 5%-lifetime and cumulative received
bits.

Constant
R-random
Simple Diffusion

0.8

0.6

0.4

0.2

0
0

20

40

60

80

100 120 140 160 180 200

Number of generated targets

These results can be explained as follows. Since sensors
nearer the base station have a higher probability of being
used as relay nodes, these nodes exhaust their battery energy earlier. Therefore, the lifetime becomes longer when
the density nearer the base station is higher. However, inthat case, there is a higher probability of there being no sensors in the sensing range, which decreases cumulative received bits.
In order to apply the explanation to the results, the probability of there being no sensors within sensing range of atarget is shown in Fig. 7 and the conditional probability ofthere being no routes (when there are sensors that can sense)is shown in Fig 8. In addition, Fig. 9 shows the number ofalive nodes (i.e, nodes that did not exhaust their battery energy) within x [m] of the base station. In Fig. 7, simple dif-

Figure 7. Probability of having no sensors.

4.2. Tolerance against random failure
The sensing-success-ratio is shown in Fig. 10. When thesensor error ratio is low, simple diffusion has the lowest
success-ratio and constant placement has the highest. This isbecause the probability of there being sensor nodes that cansense is lowest in simple diffusion and highest in constantplacement. However, when the sensor error ratio exceeds
0.4, the success-ratio in constant placement drops rapidly,
which means that the fault tolerance in constant placement

Proceedings of the 24th International Conference on Distributed Computing Systems Workshops (ICDCSW’04)
0-7695-2087-1/04 $20.00 © 2004 IEEE

not decrease as the error ratio decreases in simple diffusion, while it decreases in constant and R-random placement. As for routes to the base station, constant placementshows much higher probability of there being no routes inFig. 12. Summarizing above, we can say R-random placement has a higher probability of having both nodes that cansense and routes to the base station.

Probability of having no routes

1

0.8

0.6

0.4

0.2

Constant
R-random
Simple Diffusion

1
Constant
R-random
Simple Diffusion

0
20

40

60

80

100 120 140 160 180 200

Number of generated targets

Figure 8. Conditional probability of having noroutes.

Probability of success

0

0.8

0.6

0.4

0.2

0
0

0.2

Constant
R-random
Simple Diffusion

0.4

0.6

0.8

1

Sensor error ratio

Figure 10. Sensing-success-ratio.

100

10
1
1
0

100

200

300

400

500

600

700

800

x [m] (Distance from the base station)

Figure 9. The number of alive nodes within
x [m] of the base stationis the lowest of the three. In all regions, R-random shows ahigher success-ratio.
From another point of view, evaluation on tolerance
against random failure is equivalent to that on the density of sensor nodes in region A. Considering this, Fig. 10
also indicates success-ratio for R-random placement is almost proportional to the number of sensor nodes in region
A, while this is not true in the other placements. We consider this observation reveals the essential advantage of Rrandom placement in that the newly added nodes are effectively placed when the number of nodes increases. In otherwords, R-random placement well brings out the potential of
sensor nodes, which leads to the desirable performance ofthe sensor network.
In order to examine the results in detail, we plot the probability of having no sensors in Fig. 11 and the conditional
probability of having no routes (when there are sensors thatcan sense) is shown in Fig. 12. As shown in Fig. 11, theprobability of there being no sensors that can sense does

Probability of having no sensors

The number of alive nodes within x

1000

Constant
R-random
Simple Diffusion

0.8

0.6

0.4

0.2

0
0

0.2

0.4

0.6

0.8

1

Sensor error ratio

Figure 11. Probability of having no sensors.

5. Conclusion
In this paper, we evaluated the fault tolerance in sensor networks and examined how to place sensor nodes toraise the tolerance. Through simulation study, we founda trade-off between the existence of nodes that can sense
and the tolerance against failure. Simple diffusion and constant placement are the most typical stochastic placements.
However, results show that the probability of having nodes
that can sense is low in simple diffusion and the tolerance against failure is low in constant placement. R-random
placement, which is our proposal, has high fault tolerance

Proceedings of the 24th International Conference on Distributed Computing Systems Workshops (ICDCSW’04)
0-7695-2087-1/04 $20.00 © 2004 IEEE

Probability of having no routes

1Constant
R-random
Simple Diffusion

0.8

0.6

0.4

0.2

0
0

0.2

0.4

0.6

0.8

1

Sensor error ratio

Figure 12. Conditional probability of having noroutes.

with the high probability of having nodes that can sense.
This is because the density near the base station is higher,
while that far from the base station is not too low.
R-random placement may not be optimal, but the results in this paper indicate that the fault tolerance against
both battery exhaustion and random failure can be raised
by improving sensor-placement and R-random placement
is an example of good placement. Moreover, the results also
shows R-random placement well brings out the potential of
sensor nodes, in that the newly added nodes are effectively
placed when the number of nodes increases.
For further study, we plan to establish optimal stochastic
placement based on the observations reported in this paper.

[5] G. Hoblos, M. Staroswiecki, and A. Aitouche. Optimal
design of fault tolerant sensor networks. In Proc. IEEE
Int’l Conference on Control Applications, pages 462–472,
September 2000.
[6] C. Intangonwiwat, R. Govindan, and D. Estrin. Directed diffusion: A scalable and robust communication paradigm forsensor networks. In Proc. ACM MobiCom ’00, pages 56–67,
August 2000.
[7] L. Li and Y. Halpern. Minimum-energy mobile wireless networks revisited. In Proc. IEEE ICC ’01, pages 278–283, June
2001.
[8] T. Poggio and S. Edelman. A network that learn to recognize three-dimensional objects. Nature, 343(6255):263–266,
January 1990.
[9] E. Shih, S. H. Cho, N. Ickes, R. Min, A. Sinha, A. Wang, and
A. Chandrakasan. Physical layer driven protocol and algorithm design for energy-efﬁcient wireless sensor networks.
In Proc. ACM MobiCom ’01, pages 272–286, July 2001.
[10] K. Sohrabi, V. A. J. Gao, and G. J. Pottie. Protocols for selforganization of a wireless sensor network. IEEE PersonalCommunications, 7(7):16–27, October 2000.
[11] A. Woo and D. Culler. A transmission control scheme formedia access in sensor networks. In Proc. ACM MobiCom’01, pages 221–235, July 2001.

Acknowledegment
We would like to thank Mr. Keisuke Ishibashi for his
valuable comments and Ms. Kyoko Ashitagawa for her help
with the simulations.

References[1] I. F. Akyildiz, W. Su, Y. Sankarasubramaniam, andE. Cayirci. A survey on sensor networks. IEEE Communications Magazine, 40(8):102–114, August 2002.
[2] M. Bhardwaj, T. Garnett, and P. Chndrakasan. Upper bounds
on the lifetime of sensor networks. In Proc. IEEE ICC ’01,
pages 785–790, June 2001.
[3] W. R. Heinzelman, A. Chandrakasan, and H. Balakrishnan.
Energy-efﬁcient communication protocol for wireless microsensor networks. In Proc. IEEE Hawai Int’l Conf. on System Sciences, pages 3005–3014, January 2000.
[4] W. R. Heinzelman, J.Kulik, and H. Balakrishnan. Adaptive
protocols for information dissemination in wireless sensor
networks. In Proc. ACM MobiCom ’99, pages 174–185, August 99.

Proceedings of the 24th International Conference on Distributed Computing Systems Workshops (ICDCSW’04)
0-7695-2087-1/04 $20.00 © 2004 IEEE