IEICE TRANS. COMMUN., VOL.E87–B, NO.9 SEPTEMBER 2004

2511

PAPER

Special Section on Networking Technologies for Mobile Internet Systems

The Reliability Performance of Wireless Sensor Networks
Configured by Power-Law and Other Forms of
Stochastic Node Placement
Mika ISHIZUKA†a) and Masaki AIDA†b) , Members

SUMMARY
Sensor nodes are prone to failure and have limited power
capacity, so the evaluation of fault tolerance and the creation of technology
for improved tolerance are among the most important issues for wirelesssensor networks. The placement of sensor nodes is also important, since
this aﬀects the availability of nodes within sensing range of a target in agiven location and of routes to the base station. However, there has been
little research on the placement of sensor nodes. Furthermore, all research
to date has been based on deterministic node placement, which is not suitable when a great many sensor nodes are to be placed over a large area. In
such a situation, we require stochastic node placement, where the sensorpositions are in accord with a probability density function. In this paper,
we examine how fault tolerance can be improved by stochastic node placement that produces scale-free characteristics, that is, where the degree ofthe nodes follows a power law.
key words: sensor network, node placement, fault tolerance, power law

1.

Introduction

Recent advances in electronics, such as power-saving LSIs,
have led to the production of small sensors equipped with
communications capability. A network of such sensors will
enable information gathering over a wide area, so interest insensor networks is currently strong.
The development of ad hoc network technology is important for wireless-networked sensors, since the ad hoc approach will relieve the network implementor of explicit network configuration. Furthermore, sensor nodes are prone to
failure and have limited power capacity, so the evaluation of
fault tolerance and the creation of technology for improved
tolerance are also major issues for sensor networks. As isthe case for ad hoc networks [1], [2], most research on fault
tolerance in sensor networks to date has been focused on
the power-saving mode of the MAC protocol [3]–[5] andenergy-eﬃcient route selection [6]–[8].
Though sophisticated routing and use of the MAC layer
protocol will improve fault tolerance, the placement of sensor nodes also strongly aﬀects fault tolerance in a sensor
network.
However, little research into placement has been done.
In addition, all research to date has been based on deterministic node placement [9]–[11], which requires that eachsensor node be placed at predetermined coordinates. This
Manuscript received January 16, 2003.
Manuscript revised May 27, 2004.
†
The authors are with the NTT Information Sharing Platform
Laboratories, NTT Corporation, Musashino-shi, 180-8585 Japan.
a) E-mail: ishizuka.mika@lab.ntt.co.jpb) E-mail: aida.masaki@lab.ntt.co.jp

Fig. 1

Concept of deterministic node placement.

Fig. 2Concept of stochastic node placement.

has the following shortcomings:• a high cost of placement and• luck of clarity regarding the eﬀects of errors in sensorposition on performance.
The alternative approach is stochastic node placement,
where the sensor-positions are determined by a probability
density function. Approximate positioning satisfies the density function, so the cost of placement is low. The conceptsof the two approaches to placement are shown in Figs. 1 and2.
Considering the respective characteristics, stochastic
node placement is particularly eﬀective when
• the region where sensor nodes are placed is large andoutdoors, and has conditions that make precise surveying hard (for example, a big park, a forest, a place
where dangers exist), and• the number of sensor nodes is large.
In order to show eﬀectiveness of stochastic node placement,
we should show how to realize stochastic node placement,
though this paper focuses only on the evaluation of fault
tolerance for stochastic node placement. We consider any
stochastic node placement can be realized by scattering sensor nodes from the air (see Fig. 2). The theoretical basis forthis consideration is briefly described in Sect. 2.2.
Note that this paper deals with fault tolerance against
both random failure and battery exhaustion, although most

IEICE TRANS. COMMUN., VOL.E87–B, NO.9 SEPTEMBER 2004

2512

other studies to date have been based on evaluation of thelatter point alone. This is because we consider that fault tolerance against random failure is also important, since sensor
nodes are prone to failure (e.g. for environmental reasons
such as bad weather or because of mechanical trouble). In
addition, the evaluation of fault tolerance against random
failure is equivalent to evaluation of the eﬀects of changes
to the number of sensor nodes. The evaluation of fault tolerance against random failure is thus a meaningful measure of
how eﬀectively sensor nodes are placed by diﬀerent methods of placement.
The topology of the Internet has been shown to havescale-free characteristics; that is, the degree of the nodes
has been shown to follow a power law [12]. In addition, recent research has shown that scale-free networks are highly
tolerant of random failure, since such networks have morealternative routes [12]. Therefore, it is natural to expect that
we can realize a sensor network with high fault tolerance
by constructing the network so that the degree of its nodes
follows a power law around the base station.
Motivated by the above considerations, we are examining how fault tolerance can be improved by stochastic nodeplacement that produces scale-free characteristics. In thispaper, we start by proposing power-law placement, that is,placement so that the degree of the nodes follows a powerlaw. We then evaluate the relative fault tolerance of powerlaw placement and the two most typical forms of stochastic placement. Finally, we identify the optimal placement
among them.
The rest of this paper is organized as follows. As background material, Sect. 2 covers the communications modeland the three forms of stochastic placement. Section 3 describes the conditions used in simulation. Section 4 gives
the results of simulation. Section 5 covers the evaluation of
optimal placement. Finally, Sect. 6 is a summary.
2.

Background

2.1 Communications ModelIn this subsection, we use Fig. 3 in explaining how a sensor
network senses and transmits data. We consider the situation

where the precise location of the target is unknown but thetarget is known to be in a certain region. Here, we assume
that the target is within region D. An example of an application with such conditions is the monitoring of a vehicle ina forest.
Each sensor node has a specific sensing range. Eachsensor node for which a target is within the sensing range
sends sensed information to the base station during each period T . In Fig. 3, sensors A and B are the only sensors capable of sensing the target.
A sensor node can transmit data to or receive data fromother sensor nodes within its radio-transmission range. The
minimum-hop strategy is used to select routes to the basestation. If an intermediate node on the current route breaks
down, an alternative route is selected for the remaining information.
Note that we refer to the sensing of a target as successful when one or more sensor nodes is within sensing rangeof the target, and at least one of these nodes has a route to
the base station.
A sensor node consumes battery energy in transmitting(Et J/bit) and receiving bits (Er J/bit). When a sensor node
used up its battery energy, all functions of the node stop.
2.2 Stochastic Node Placement
In stochastic node placement, sensor-positions x ∈ R2 aredefined by a probability density function (p.d.f.), f (x)† .
In this paper, we evaluate the fault tolerance for three
types of stochastic placement. Two are the most typicaltypes, i.e. simple diﬀusion and constant placement, while
the other is our proposal, power-law placement. In this section, we define the p.d.f. of and briefly describe the characteristics of each approach to placement.
We assume that all sensor nodes are placed in region
D, which is a circle with radius R. Under this assumption,f (x)dx = 1 is required. We set the base station at theDcenter of this circle, and treat this as the origin.
Simple diﬀusion The simplest way to distribute sensornodes is to scatter them from the air above the basestation.
Suppose that the weight and shape of the sensor nodes
are such that air drag has a strong eﬀect on the way
the sensor nodes fall. If air current are weak enough,placement of the sensor nodes will be randomized, sothat it follows a diﬀusion equation. We call this simple
diﬀusion.
Since the solution of a diﬀusion equation on a twodimensional boundary is a two-dimensional normal
distribution, the p.d.f. of the sensor-positions is
f (x) =†

Fig. 3

An example of the sensing and transmission of data.

Ch0 (x; σ),
2πσ2

(1a)

The probability of a sensor being within region A = {x11 ≤X1 ≤ x12 , x21 ≤ X2 ≤ x22 } can be written in terms of theas follows: P{x11 ≤ X1 ≤ x12 , x21 ≤ X2 ≤ x22 } =p.d.f.
x22  x12
f (x1 , x2 )dx1 dx2 .
x
x
21

11

ISHIZUKA and AIDA: THE RELIABILITY PERFORMANCE OF WIRELESS SENSOR NETWORKS

2513

where





h0 (r, σ) = exp −C=constant placement. In this case, the p.d.f. of sensorposition is as follows:


2

r
, and
2σ2

1

 2 ,
1 − exp − R2

(1b)f (x) =
(1c)0 ≤ x ≤ R.
In (1), σ2 is the variance of the distribution. The variance is determined by several factors (i.e. the shape andweight of the sensors, and the height from which they
are released).
Note that sensor nodes scattered from the air are governed by another formula when air currents are strong.
However, we do not take such variation into account,since details on techniques for the scattering of sensor
nodes are beyond the scope of this paper.
The two-dimensional normal distribution is known as aradial basis function. Daubechies [13] has shown thatany functions F(x) can be expressed in terms of one ormore radial basis functions, as follows:F(x) =p(c, σ)h(x; c, σ)dcdσ,
(2a)
where



x − c.
h(x; c, σ) = exp −
2σ2

(2b)

In (2), p(c, σ) are weights of each normal distribution,and c and σ2 are center and variance of the respective
normal distributions.
When a radial basis function is used to approximate
a given function, the integral in (2) is replaced by asuperposition of h(x; ci , σi ) as follows:
F(x) ≈M

pi (ci , σi )h(x; ci , σi ),

(3a)

i=1

where



 x − ci   .
h(x; ci , σi ) = exp −
2σ2i

1, 0 ≤ x ≤ R.
|D|

(4)

In (4), |D| means the area of region D.
Power-law placement (our proposal) The p.d.f. of thesensor-positions in polar-coordinates f p (r, θ) is
α + 1  r αf p (r, θ) =,2πR R
0 ≤ r ≤ R, 0 ≤ θ < 2π, −1 < α < 1.
(5)Power-law placement is characterized by the following two features. Firstly, the density of sensor nodes
is higher near the base station. Actually, ρ(r1 , θ1 ), thedensity of sensor nodes at position (r1 , θ1 ), is as follows.
 r1 +δr  θ1 +δθ
f (r, θ)dθdrrθ
ρ(r1 , θ1 ) = lim lim 1  r1 +δr1  θ1 +δθδr→0 δθ→0
dθdr
r
θ
1

1

α + 1 r1α−1, −2 < α − 1 < 0.
=2π Rα+1(6)

Secondly, the degree of the nodes follows a power law.
Since a sensor node can transmit data to or receive datafrom other sensor nodes within the radio-transmission
range, the degree of a node may be expressed as thep.d.f. of the number of sensor nodes within radiotransmission range. When the radius of the region D
is much larger than the radio-transmission range, theasymptotic behavior of the degree of the nodes is asfollows: df (r, θ)drdθ
g(x) =dx
ρ(r1 ,θ1 )<x 2π  Rd
α+1 r α=( ) drdθ
1
dx 0
2πR R
2πRx
2

∝ x α−1 , 2πR2 < x, −1 < α < 1.
(7)

(3b)

Also in (3), pi (ci , σi ) are weights of each normal distribution, and ci and σ2i are center and variance of therespective normal distributions. In addition, M is thenumber of functions being superposed. As for the accuracy of (3), the upper bound of the error has been
discussed [14].
Repeated simple diﬀusion with diﬀerent centers andvariances can thus lead to any form of stochastic
sensor-placement. In this sense, simple diﬀusion is afundamental distribution in terms of realizing stochastic placement.
Constant placement In much work on sensor networks[5]–[7], [15], placement for uniform probability density of sensor nodes has been assumed. We call this2
α−1From (7), g(x) is proportional to x , so the degree ofthe nodes follows a power law.
Here, we briefly give an example of the realizationof power-law placement, although we leave details ofsuch realization for further study. As was shown in (3),repeated simple diﬀusion can be used to produce any
stochastic placement. To set masa ci , (i = 1, . . . , M)
to the same position as the base station is one of thesimplest parameter settings for (3). In this case, thep.d.f. of placement, f (x), is approximated as follows:
f (x) ≈Mpi
h0 (x; σi ).
2πσ2i
i=1

(8)

One way to realize (8) is to scatter M types of sensor

IEICE TRANS. COMMUN., VOL.E87–B, NO.9 SEPTEMBER 2004

2514

(a)

(b)

(c)

(d)

(e)
Fig. 4

P.d.f. plots for various placements.

(a)

(b)

(c)

(d)

(e)
Fig. 5

Examples of various placements.

nodes with diﬀerent weights (for diﬀerent σi ) simultaneously in the air above the base station. The cost of
preparing “M” types of sensors with diﬀerent weights
will be low, even if the value of M is great. This is because the M types of sensors can be prepared by merely
attaching weights to each sensor. Details on determining the values of M, pi , and σi are not given in thispaper, because the focus of this paper is the evaluationof fault tolerance for each placement.
The characteristics of various placements are shown by plotsof p.d.f. in Fig. 4 and by examples of placement in Fig. 5.
The base station is the origin and region D is a circle with aradius of 500 m, centered on the base station. Variance forsimple diﬀusion is set so that 99% of the sensors are placed
within region D. In the other placements, we suppose thatall sensor nodes are placed within region D. The number of
sensor nodes in Fig. 5 is 250. The density of simple diﬀusion gradually decreases with distance from the base stationand is lowest around the border of region D. The power-law

placements also have greatest density near the base station,and this rapidly decreases with distance and then stays almost constant. As α increases, density decreases near thebase station and increases around the border of region D.
3.

Simulation Settings

3.1 Setting of Targets and Sensor Nodes
Targets were randomly generated within region D, a circle
with a radius of 500 m and centered on the base station, covering about seventeen times the area of the Tokyo Dome.
We consider that region D is large enough to benefit fromthe eﬃciency of stochastic node placement.
In evaluating tolerance of node failures due to battery
exhaustion, we set up the target-sensing period, T , to follow an exponential distribution with an average of 72 min.
A new target was generated T I after the end of the targetsensing period for the previous target. We set T I to follow
an exponential distribution with an average of 250 sec.

ISHIZUKA and AIDA: THE RELIABILITY PERFORMANCE OF WIRELESS SENSOR NETWORKS

2515

The number of sensor nodes, N, was 250. We set thesensing range to 60 m and the radio-transmission range to
100 m.
The data transmission rate was 1.1 kbps, low enough to
avoid collisions. Actually, the data transmission rate is determined by frequency of sensing and by volume of sensory
information. When a certain delay is allowed by an application, frequency of sensing is not so large, since it is reasonable that a sensing node send several times of sensory information collectively. As for volume of sensory information,
it is considered to be small. Considering situation wherea certain delay is allowed by an application and volume ofsensory information is small, we set interval of transmission
is 18 min and volume of data to 150 kbytes. Note that, whendata transmission rate is high enough that collisions are possible, the collisions aﬀect the rate of battery consumption.
In practice, however, we consider these collisions can be
avoided by using techniques such as data aggregation [16].
Therefore, our results can apply to the situation where sometechniques to avoid collisions are used, though details aboutsuch techniques will be considered in further study.
Energy consumption was 3.3e-07 J/bit for transmission
and 1.9e-07 J/bit for reception [15]. The initial energy ofeach sensor node was 20 J.
As was described in Sect. 2.1, target is successfully
sensed when the following two conditions are met.
[Condition 1] One or more sensor nodes is within the sensing range of the target, and[Condition 2] at least one of these nodes has a route to thebase station.

sensor nodes gradually decreases because of random errors
or battery exhaustion.
We adopted the “virtual sensing-success ratio” as theperformance metric. This refers to the probability that agiven target generated in region D is successfully sensed.
This metric is used to evaluate fault tolerance (that is,sensing-success ratio) at arbitrary points in time.
In evaluating tolerance against random failure, we evaluated the virtual sensing-success ratio for various values of
rb , the proportion of broken nodes. We increased rb from 0
with a step size of 0.1. At each value of rb , the broken nodes
are randomly selected.
In evaluating tolerance against battery exhaustion, we
considered a situation where the number of nodes that haveused up their battery energy increases with the numberof targets. We evaluated the relationship between virtual
sensing-success ratio and the number of targets. We also
evaluated the total numbers of bits received as a measure ofactual (simulated) performance.
4.

Results of Simulation

4.1 Tolerance of Random Failure
In the discussion below, ‘sensor node’ and ‘sensor’ refer tofunctioning sensor nodes, except in reference to the original
distributions. ‘The target’ refers to each current target in thesequence.
Results for virtual sensing-success ratio are given in
Figs. 6 and 7. In order to examine the results in detail, weplot the probability that no sensor is within sensing range ofGiven these simple conditions, simulation parameters neednot be changed to investigate the robustness of networks ineach placement against failures of nodes. However, the results of quantitative analysis may be aﬀected by the numberof sensor nodes in region D and the ratio of sensing range toradio-transmission range.
Therefore, we evaluated two additional cases in determining the best placement (Sect. 5):• N is changed to 400, and• N is changed to 400 and sensing range is changed to
30 m.
We evaluated seven forms of power law placement, i.e.
α ∈ {−0.5, −0.3, −0.1, 0, 0.1, 0.3, 0.5}. In each case, all sensor nodes were placed in region D. This was also the case forconstant placement. In the case of simple diﬀusion, the variance was set so that 99% of sensor nodes would be placed
within region D. In evaluating individual items (Sect. 4),
sets of five arrangements produced by constant placement,
simple diﬀusion, and power-law placement with three control parameters were evaluated.

Fig. 6

Virtual sensing-success ratios. (α = −0.5, −0.3, −0.1)

Fig. 7

Virtual sensing-success ratios. (α = 0, 0.1, 0.3, 0.5)

3.2 Simulation Scenario
In this subsection, we describe how we evaluated fault tolerance. We considered scenarios where the number of live

IEICE TRANS. COMMUN., VOL.E87–B, NO.9 SEPTEMBER 2004

2516

Fig. 8 Probability of having no sensors within range of the target. (α =−0.5, −0.3, −0.1)

Fig. 9 Probability of having no sensors within range of the target. (α =0, 0.1, 0.3, 0.5)

Fig. 10 Probability that no sensor node within sensing range of the target
has a route to the base station. (α = −0.5, −0.3, −0.1)

Fig. 11 Probability that no sensor node within sensing range of the target
has a route to the base station. (α = 0, 0.1, 0.3, 0.5)

the target in Figs. 8 and 9. In addition, the probability thatno sensor node within sensing range of the target has a routeto the base station in plotted in Figs. 10 and 11 (we call thisas the probability of having no route to the base station).
The highest virtual sensing-success ratio is for constantplacement when the proportion of broken nodes, rb , is low.
This is because the probability of having no sensor withinsensing range of the target is lowest for constant placement(see Figs. 8 and 9). It is obvious that uniform density of
sensor nodes is desirable in terms of keeping this probability high. However, the ratio for constant placement drops
rapidly after rb reaches 0.4 and this placement produce theworst result in the region of high rb . This is because thisplacement produces the highest probability that there are noroutes to the base station when rb is high (see Figs. 10 and
11). In order to keep the probability that a route to the basestation exists high despite random failures, a higher densityof sensor nodes near the base station is desirable. This is because sensor nodes near the base station have a higher probability of being used as relay nodes. Since constant placement produces the lowest density of sensor nodes near thebase station, the sensing-success ratio for high rb is lowest.
Simple diﬀusion has the lowest or second lowest virtual sensing-success ratio when rb is low, but has the highest
ratio when rb is high. The low sensing-success ratio for simple diﬀusion in the region of small rb is because the probability that no sensor is within sensing range of the target
is high (see Figs. 8 and 9). This is because simple diﬀusion
produces a distribution with relatively fewer nodes aroundthe border of region D (see Fig. 5). The converse of thischaracteristic is the relatively higher sensing-success ratio
in the region of high rb . That is, the probability of having
no route to the base station is smaller in the region of highrb (see Figs. 10 and 11) because there are more sensors near
the base station.
The virtual sensing-success ratio for the power-law
placements increases with α in the region of small rb . Thisis mainly because the probability of having no sensor withinsensing range of the target decreases with α increases (seeFigs. 8 and 9). This decrease in the probability of having
no sensor within sensing range of the target is because thedensity of sensor nodes becomes increasingly uniform as
α increases. The diﬀerences between the virtual sensingsuccess ratios for diﬀerent values of α decrease as rb increases. This is because the probability of having no routeto the base station increases with α in the region of high rb ,while the probability that no sensor is within sensing rangeof the target decreases as α increases (see Figs. 8–11). The
increase is because the density of sensor nodes near the basestation decreases with α.
From another point of view, the evaluation of sensing
success-ratio when random failure occurs is equivalent to
the evaluation of sensing success-ratio when the numberof sensor nodes in region D is changed, since the x-axis
in Figs. 6 and 7 refrects to the number of live nodes, i.e.
N(1 − rb ). We now look at the results in Figs. 6 and 7 fromthis viewpoint.
The virtual sensing success-ratio for constant placement does not increase greatly when the number of operating nodes increases in the right most region of Figs. 6 andISHIZUKA and AIDA: THE RELIABILITY PERFORMANCE OF WIRELESS SENSOR NETWORKS

2517

7. That is, with this distribution, newly added nodes are noteﬀectively placed when the number of sensor nodes is small.
The virtual sensing success-ratio for simple diﬀusion
approaches saturation first and stays relatively low as thenumber of nodes increases in the left sides of these graphs.
In this case, newly added nodes are not eﬀectively placedwhen the number of sensor nodes is large.
The virtual sensing success-ratio for power-law placement rises linearly with the number of nodes in the right-side
and middle regions of these figures. When α < 0, this ratio continues to rise linearly in the left-most region of thesefigures, while the ratios for α ≥ 0 approach relatively highsaturation values in this region. Newly added nodes are thus
always eﬀectively placed, regardless of the number of sensor nodes.

Fig. 14 Probability of having no sensor within range of the target. (α =−0.5, −0.3, −0.1)

4.2 Tolerance of Battery Exhaustion
Relationships between the number of targets that have appeared and the virtual sensing-success ratio are shown in
Figs. 12 and 13. To examine these results in more detail,we plot the probability that no sensor is within range of thecurrent target in Figs. 14 and 15, and the probability that nosensor node within sensing range of the target has a route to
the base station (that is, the probability of having no route to
the base station) in Figs. 16 and 17.

Fig. 12 Virtual sensing-success ratio vs. no. of targets that haveappeared. (α = −0.5, −0.3, −0.1)

Fig. 13 Virtual sensing-success ratio vs. no. of targets that haveappeared. (α = 0, 0.1, 0.3, 0.5)

Fig. 15 Probability of having no sensor within range of the targets. (α =0, 0.1, 0.3, 0.5)

Fig. 16 Probability that no sensor node within sensing range of the target
has a route to the base station. (α = −0.5, −0.3, −0.1)

Fig. 17 Probability that no sensor node within sensing range of the target
has a route to the base station. (α = 0, 0.1, 0.3, 0.5)

IEICE TRANS. COMMUN., VOL.E87–B, NO.9 SEPTEMBER 2004

2518

The highest virtual sensing-success ratio over simulated time is for constant placement highest when very few
targets have appeared. However, the respective plots drop
rapidly and are the first to approach 0 (Figs. 12 and 13).
This indicates that constant placement is also the weakest
approach in terms of failure through battery exhaustion.
While simple diﬀusion has the lowest ratio when relatively few targets have appeared, the ratios drop and approach zero much more strongly than those for constantplacement.
The sensing-success ratios for power-law placementwith α ≤ 0 are almost equal to and generally greater thanthose for simple diﬀusion across the whole range. When relatively few targets have appeared in these cases, the virtual
sensing-success ratios decrease with α. On the other hand,the period over which the virtual sensing-success ratio stays
at a reasonable value becomes longer as α decreases.
These results can be explained as follows. Wile theprobability of having no sensors within range of the target determines the virtual sensing-success ratio when relatively few targets have appeared, the probability of having no routes to the base station becomes dominant whenrelatively many targets have appeared. In a similar way totolerance of random failure, there is a trade-oﬀ between theprobabilities of having no sensor within sensing range of thetargets and of having no route to the base station. That is,
uniform placement of the sensor nodes maximizes the former probability but placement with a high density near thebase station is desirable in terms of raising the latter probability.
From these observations, we can say that placement fora uniform density of sensor nodes shows the highest virtual
sensing success-ratio when the number of targets is small,while placement for a higher density near the base station
keeps the virtual sensing-success ratio at reasonable values
over longer periods.
Unlike the characteristics of tolerance of random failure, however, rapid decreases in the virtual sensing-successratio are seen with most placements. This is because of therapid increase in the probability of having no route to thebase station (Figs. 16 and 17) and the almost constant probability of having no sensor within sensing range of the target(Figs. 14 and 15).
The mechanism behind the rapid increase is as follows.
Since sensor nodes near the base station are more likely to
be used as relay nodes, their batteries are more rapidly used
up. Once some sensor nodes near the base station have usedup their batteries, the remaining sensor nodes near the basestation are more likely to be used as relay nodes, this situation accelerates the consumption of battery energy by thesesensor nodes. Consequently, as the number of targets (simulated time) increases, the density of sensor nodes near thebase station more rapidly decreases, although this eﬀect isdiminished with distance from the base station. This explains the rapid increase in the probability of having no routeto the base station in Figs. 16 and 17.
Considering this acceleration of battery consumption,

Fig. 18

Total number of received bits.

we conclude that the density of sensor nodes near the basestation has a stronger eﬀect on tolerance of battery exhaustion than on tolerance of random failure.
Finally, the total number of bits actually received by
the base station in the above situation is plotted in Fig. 18.
Fewer bits are received with constant placement and simple diﬀusion than with power-law placement when −0.3 ≤α ≤ 0. In the case of constant placement, a greater probability that there is no route to the base station reduces the
cumulative number of bits received. In the case of simple
diﬀusion, a greater probability of having no sensor within
range of targets has a similar but weaker eﬀect. In the caseof power-law placement, intermediate values of α are desirable in terms of keeping the total number of bits received
high, because a smaller value of α raises the probability of
having no sensor within range of targets and a larger valueof α raises the probability of having no route to the base station. Since these two probabilities are relatively balanced
for power-law placements in the range −0.3 ≤ α ≤ 0, relatively higher total numbers of bits are received in this rangeof Fig. 18.
5.

Optimization of Power Law Placement

The simulation-based results in Sect. 4 showed that fault tolerance becomes high when the probabilities of having sensor nodes within range of the targets and of having alternative routes to the base station are both high. Since the former
more strongly aﬀects tolerance of random failure while thelatter more strongly aﬀects tolerance of battery exhaustion,
the most desirable placement diﬀers with the mix of failure types. However, the results of simulation also suggested
that we can balance tolerance of the two types of failure by
selecting power-law placement with an appropriate value of
α. We thus briefly investigate the optimization of power-law
placement in this section.
To optimize power-law placement, we need to express
a performance metric for each type of failure as a function of
α. For tolerance of random failure, we use the expectation of
the virtual sensing-success ratio, and for tolerance of battery
exhaustion, we use the total number of received bits.
A value of α that maximizes both is most desirable.
However, each metric is likely to be maximized by diﬀerent
values of α. We thus suggest the value of α that maximizes

ISHIZUKA and AIDA: THE RELIABILITY PERFORMANCE OF WIRELESS SENSOR NETWORKS

2519

Fig. 19

Fig. 20

Plot of S (α) Cr (α).

Plot of S (α)Cr (α). (N = 400)

the product of the two metrics as a suitable optimal value.
We do this with a limited range of α as follows:max

α∈{−0.5,−0.3,−0.1,0,0.1,0.3,0.5}

where

S (α) Cr (α)

S (α) =NS n P[Nb = n].

(9a)
(9b)

n=0

The function S (α) in (9a) is the expectation of the virtual
sensing-success ratio when random failure occurs, and is
calculated by using (9b). Notation in (9b) is defined as follows:• N: number of sensor nodes.
• S n : virtual sensing-success ratio when the number ofbroken nodes is n (that is, the results in Figs. 6 and 7).
• Nb : the number of broken nodes.
The Cr (α) in (9a) is defined as the total number of received
bits when failure through battery exhaustion is occurring(that is, the result in Fig. 18).
In (9a), S (α) is the expectation of the probability thatsensing is successful and Cr (α) is proportional to the probability that data is successfully received, which means both
metrics do not exceed 1. Therefore, α that makes one metric too large cannot be chosen as the optimal value, eventhough product of S (α) and Cr (α) is chosen as an objectivefunction.
Suppose that the process of sensors breaking down
follows a Bernoulli distribution and that the probability of
breakdown, pb , is 0.001. Under this condition, P[Nb = n] in(9b) is calculated by N Cn pbN (1 − pb )N−n .
We plot S (α) Cr (α) in Fig. 19. In this figure, S (α) Cr (α)
is maximized when α = −0.1.
As was mentioned in 3.1, the number of sensor nodes
N and the ratio of sensing range to radio transmission range
may aﬀect the optimal value of α. We thus evaluate two
additional cases:• N = 400 and sensing range is not changed (that is,remains 60 m), and• N = 400 and sensing range is changed to 30 m.
The plots of S (α)C r (α) for these cases are shown in
Figs. 20 and 21. From these figures, we can confirm that the
optimal value of α is still −0.1.

Fig. 21

6.

Plot of S (α)Cr (α). (N = 400, sensing range = 30 m)

Conclusion

In this paper, we have investigated how forms of stochastic
node placement aﬀect the fault tolerance of a sensor network.
To increase tolerance of failure, we must raise the probability of having sensor nodes within sensing range of eachtarget, and of at least one of these nodes having routes tothe base station. However, neither of the two most typicalforms of stochastic placement, simple diﬀusion and constantplacement, keeps both probabilities high. As a result, bothhave poor fault tolerance. We have shown that power-law
placement, the form proposed in this paper, can raise fault
tolerance with an appropriately selected control parameter.
In addition, we have shown that power-law placement has
superior eﬀectiveness because the sensing-success ratio isalmost linearly proportional to the number of nodes.
While we have not proven that power-law placement is
the optimal form of stochastic placement, our results clearly
indicate that tolerance of both random failures and battery
exhaustion can be raised by improving the placement of sensor nodes. Power-law placement with a well-tuned control
parameter constitutes good placement.
In further study, we plan to investigate the realizationof power-law placement as the superposition of simple diffusion placements in detail.
Acknowledgment
The authors would like to thank Ms. Kyoko Ashitagawa at

IEICE TRANS. COMMUN., VOL.E87–B, NO.9 SEPTEMBER 2004

2520

Human Resources International Co., Ltd. for her help in performing the simulations.
References[1] S.J. Lee and M. Gerla, “AODV-BR: Backup routing in ad hoc networks,” Proc. 2nd IEEE Wireless Communications and Networking
Conf., pp.1311–1316, Sept. 2000.
[2] M.K. Marina and S.R. Das, “On-demand multipath distance vector
routing for ad hoc networks,” Proc. 9th IEEE Int. Conf. on Network
Protocols, pp.14–23, Nov. 2001.
[3] E. Shih, S.H. Cho, N. Ickes, R. Min, A. Sinha, A. Wang, and A.
Chandrakasan, “Physical layer driven protocol and algorithm designfor energy-eﬃcient wireless sensor networks,” Proc. ACM MobiCom’01, pp.272–286, July 2001.
[4] A. Woo and D. Culler, “A transmission control scheme for media
access in sensor networks,” Proc. ACM MobiCom’01, pp.221–235,
July 2001.
[5] K. Sohrabi, J. Gao, V. Ailawadhi, and G.J. Pottie, “Protocols for selforganization of a wireless sensor network,” IEEE Pers. Commun.,vol.7, no.5, pp.16–27, Oct. 2000.
[6] W.R. Heinzelman, J. Kulik, and H. Balakrishnan, “Adaptive protocols for information dissemination in wireless sensor networks,”
Proc. ACM MobiCom’99, pp.174–185, Aug. 1999.
[7] W.R. Heinzelman, A. Chandrakasan, and H. Balakrishnan, “Energyeﬃcient communication protocol for wireless microsensor networks,” Proc. IEEE Hawaii Int’l Conf. Sys. Sci., pp.3005–3014, Jan.
2000.
[8] L. Li and Y. Halpern, “Minimum-energy mobile wireless networks
revisited,” Proc. ICC’01, pp.278–283, June 2001.
[9] H. Saito and H. Minami, “Performance issues and network design for sensor networks,” IEICE Trans. Commun., vol.E87-B, no.2,
pp.294–301, Feb. 2004.
[10] G. Hoblos, M. Staroswiecki, and A. Aitouche, “Optimal design offault tolerant sensor networks,” Proc. IEEE Int’l Conf. Cont. Apps.,
pp.462–472, Sept. 2000.
[11] M. Bhardwaj, T. Garnett, and P. Chandrakasan, “Upper bounds on
the lifetime of sensor networks,” Proc. ICC’01, pp.785–790, June
2001.
[12] A.-L. Barabasi, LINKED: The New Science of Networks, Perseus
Publishing, 2002.
[13] I. Daubechies, Ten Lectures on Wavelets, CBMS-NSF Regional
Confefence Series in Applied Mathematics, Society of Industrial andApplied Mathematics, 1992.
[14] B. Delyon, A. Juditsky, and A. Benveniste, “Accuracy analysis forwavelet approximations,” IEEE Trans. Neural Netw., vol.6, no.2,
pp.332–348, March 1995.
[15] C. Intangonwiwat, R. Govindan, and D. Estrin, “Directed diﬀusion: A scalable and robust communication paradigm for sensor networks,” Proc. ACM MobiCom’00, pp.56–67, Aug. 2000.
[16] C. Intangonwiwat, D. Estrin, and R. Govindan, “Impact of network density on data aggregation in wireless sensor networks,” Proc.
ICDCS’02, pp.1567–1576, July 2002.

Mika Ishizuka
graduated from Keio University, Tokyo, with B.E. and M.E. degrees inControl Engineering in 1992 and 1994, respectively. In 1994, she joined NTT and has been
engaged in research on traﬃc control in computer networks. She received the IEICE Information Networks Research Award in 2003.
Ms. Ishizuka is a member of the Operations Research Society of Japan.

Masaki Aida
received his B.S. and M.S.
in Theoretical Physics from St. Paul’s University, Tokyo, Japan, in 1987 and 1989, and received the Ph.D. in Telecommunication Engineering from the University of Tokyo, Japan,
in 1999. Since joining NTT Laboratories in
1989, he has been mainly engaged in researchon traﬃc issues in ATM networks and computercommunication networks. From March 1998 to
March 2001, he was a manager at Traﬃc Research Center, NTT Advanced Technology Corporation (NTT-AT). He is currently a Senior Research Engineer at NTT
Information Sharing Platform Laboratories. His current interests include
traﬃc issues in communication systems. He received IEICE’s Young Investigators Award in 1996, and Information Networks Research Awards in
2001, 2002, 2003, and 2004. Dr. Aida is a member of the IEEE and the
Operations Research Society of Japan.