Achieving Power-law Placement in Wireless Sensor Networks
Mika ISHIZUKANTT Information Sharing Platform Labs,NTT Corporation
Abstract

tigated stochastic node placements that had a high degree of fault tolerance and were easily achieved. We
have proposed a new form of stochastic node placement, i.e., power-law placement such that the degree ofthe nodes followed a power-law [6]. In the first step todemonstrate the effectiveness of power-law placement,
we evaluated the relative fault tolerance of power-law
placement and the two most typical forms of stochastic
placement. Through evaluations, we found that powerlaw placement with well-tuned control parameters had
higher tolerance against failure of nodes. In the second step to demonstrate the effectiveness of power-law
placement, we also should show how power-law placement can be achieved with reasonable complexity andaccuracy. Therefore, this paper examines ways of attaining power-law placement.
The rest of this paper is organized as follows. Sect. 2
covers the communications model and simulation scenarios for evaluating fault tolerance. Sect. 3 introduces
our previous research on the fault tolerance of sensor
networks. Sect. 4 proposes ways of achieving power-law
placement. Our proposal to attain power-law placement
is based on the consideration that any stochastic nodeplacement can be achieved by scattering sensor nodes
from the air. After the theoretical foundation for thisconsideration is described, we propose two ways of implementation. Sect. 5 covers evaluations on each implementation. Finally, Sect. 6 presents a summary.

One of the most important issues in sensor networks
is to develop the technology for improved fault tolerance. From this viewpoint, the placement of sensor
nodes is critical. To date, we have proposed stochastic node placements whose degrees of nodes follow a
power-law (“power-law placement”). To demonstrate
the effectiveness of power-law placement, we have toshow that this placement has high fault tolerance andcan be achieved with a reasonable degree of complexity and accuracy. In the first step of our research, wehave shown that power-law placement with well-tuned
parameters is more robust against failure than general
stochastic node placement. In the second step to provethe effectiveness of power-law placement, we investigate
ways of achieving power-law placement in this paper.

1. Introduction
Since networks of sensors with communication capabilities would enable information to be gathered overwide areas, interest in sensor networks is currently attracting a great deal of interest. Sensor nodes are prone
to failure and have limited power capacity, so the creation of technology to increase fault tolerances is also amajor issue in sensor networks. Although sophisticatedrouting and a MAC layer protocol are expected to improve fault tolerances, placement of sensor nodes alsostrongly affects this 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 [1, 2, 3], which requires each sensor
node be placed at predetermined coordinates. This has
following shortcomings, high cost of placement and unknown effects of errors in sensor positions.The alternative approach is stochastic node placement, where thesensor-positions are determined by a probability density function. This approximate positioning that satisfies
the density function should lower the cost of placement.
The concept of stochastic node placement is shown in
Fig. 1. Motivated by these considerations, we inves0-7803-8963-8/05/$20.00 ©2005 IEEE

Masaki AIDA
Faculty of System Design,
Tokyo Metropolitan University

2. Background2.1. Communications Model
We will explain how a sensor network senses andtransmits data by referring to Fig. 2. This is a situation
where the precise location of the target is unknown but isknown to be in a certain region. Here, we have assumed
that the target is within region D.
Each sensor node has a specific sensing range for atarget and sends sensed information to the base station.
A sensor node can transmit data to or receive data fromother sensor nodes within its radio-transmission range.
661

a sensor node

The base station

Figure 1. Stochastic node placement
A route to the base station is selected by a minimumhop strategy. A sensor node consumes battery energy
in transmitting and receiving bits. When a sensor node
uses up its battery energy, all functions of the node stop.
If a relay node on the current route breaks down, an alternative route is selected for the remaining information.
Note that we refer to a target being sensed as successful when one or more sensor nodes is within sensing
range of the target, and at least one of these nodes has aroute to the base station.

2.2. Evaluating fault tolerance
We will describe a performance metric and simulation scenarios to evaluate fault tolerance.
We adopted the virtual sensing-success ratio as a performance metric. This refers to the probability that agiven target uniformly appeared in region D will be successfully sensed. Using this metric, we evaluated thefault tolerance (i.e., sensing-success ratio) at arbitrary
points in time.
We considered scenarios where the number of live
sensor nodes gradually decreases because of random errors or battery exhaustion.
In evaluating tolerance against random failures, weevaluated the virtual sensing-success ratio for various
values of rb , the proportion of broken nodes. Broken
nodes were randomly selected for each value of rb .
In evaluating tolerance against battery exhaustion, we
considered a situation where the number of nodes thathave used up their battery energy increases with thenumber of targets that were uniformly appeared withinregion D. We evaluated the relationship between virtual sensing-success ratio and the number of targets appeared. In the evaluation, we set up the target-sensing
period, T , to follow an exponential distribution with anaverage of 72 min. During target-sensing period, thetransmission interval was 18 min and the data volume
Da sensor noderadio-transmission range
the base station

sensor A
a targetsensing range

sensor B
routes to the base station

Figure 2. Sensing and transmitting data

was 150 kbytes. A new target was appeared TI after theend of the target-sensing period for the previous target.
We set TI to follow an exponential distribution with anaverage of 250 sec.
The number of sensor nodes, N , was 250. We set thesensing range to 60 m and the radio-transmission range
to 100 m. Energy consumption was 3.3e-07 J/bit fortransmission and 1.9e-07 J/bit for reception [4]. The initial energy of each sensor node was 20 J.

3. Our previous results
We have proposed a new form of stochastic nodeplacement, “power-law placement” whose degrees ofnodes followed a power-law [6]. We compared the fault
tolerance of sensor networks configured by power-law
placement with those configured by two typical placements. In this section, we briefly introduce our results.

3.1. Stochastic node placement
We describe three types of stochastic placement wehave evaluated in [6]. Two are the most typical types,
i.e. simple diffusion and constant placement, while thethird is our proposal, power-law placement.
In stochastic node placement, sensor-positions x ∈R2 are defined by a probability density function (p.d.f.),f (x). 1 We assumed that all sensor nodes would beplaced in region D, which
is a circle with radius R. Un
der this assumption, D f (x)dx = 1 is required. We
located the base station at the center of this circle, andtreated this as the origin.
Simple diffusion The simplest way to distribute sensor
nodes is to scatter them from the air above the base station. This is called simple diffusion. Suppose that theweight and shape of the sensor nodes are such that air
drag has a strong effect.If air current is sufficiently weak,placement of the sensor nodes will be randomized, sothat it follows a diffusion equation. Since the solution toa diffusion equation on a two-dimensional boundary isa two-dimensional normal distribution, the p.d.f. of thesensor-positions isCxf (x) =exp(− 2 ),
(1a)
2
2πσ1
2σ
, 0 ≤ x ≤ R. (1b)C=R2
1 − exp(− 2σ2)In Eq. (1), σ2 is the variance in distribution.
Constant placement In much of the work, placement
to achieve a uniform density has been assumed. We callthis constant placement.
1 The probability of a sensor being within region A = {x11 ≤X1 ≤ x12 , x21 ≤ X2 ≤ x22 } can be written in terms of the
p.d.f.
follows: P {x11 ≤ X1 ≤ x12 , x21 ≤ X2 ≤ x22 } = x22 asx12
f (x1 , x2 )dx1 dx2 .
x
x
21

662

11

Power-law placement (our proposal) The p.d.f. ofsensor-positions at polar-coordinates fp (r, θ) is
α + 1  r αfp (r, θ) =,2πR R
0 ≤ r ≤ R, 0 ≤ θ < 2π, −1 < α < 1.
(2)
When the radius of region D is much larger than theradio-transmission range, the asymptotic behavior of the2
degree of the nodes g(x) is proportional to x α−1 . Thismeans the degree of the nodes follows a power law.
The characteristics of various placements are indicated by the p.d.f. plots in Fig. 3. Region D is a circle with a radius of 500 m, centered on the base station.
Variance for simple diffusion has been set so that 99%of the sensors are within region D. In the other placements, all sensor nodes are within region D. The powerlaw placements have greatest density near the base station, and this rapidly decreases with distance and thenremains almost constant. As α increases, density decreases near the base station and increases around theborder of region D.

3.2. Fault tolerance of sensor networks configured by stochastic node placement
We will summarize fault tolerance of sensor networks
configured by each stochastic node placement.
To keep the virtual sensing-success ratio high when
failure of nodes occurs, we must increase the probability of there being some sensor nodes within the sensing
range of each target, and that of at least one of thesenodes having routes to the base station. When there
are few broken nodes, the former probability affects thevirtual sensing-success ratio more, and when there are
more broken nodes, the latter one does. Fault tolerance
becomes higher by using placement where both probabilities are well balanced when failure of nodes occurs.
The former probability is high when the density of
sensor nodes is uniform. The latter is high when sensor
nodes are more dense near the base station, since sensor
nodes near the base station have a higher probability of
being used as a relay node. Since sensor nodes in simple
diffusion are less dense near the border of region D (seeFig. 3), the former probability is low. Since sensor nodes
in constant placement are not so dense near the base station, the latter probability is low. As a result, both havepoor fault tolerance. However, power-law placement canincrease fault tolerance with appropriately selected control parameters (i.e., −0.1 ≤ α ≤ 0.0).

4. Power-law placement achieved with simple diffusion
We will propose ways of achieving power-law placement with α = 0 using superposition of simple diffusion(remember that α = 0 is one of the best parameters). We
use simple diffusion since simple diffusion is one of theeasiest ways to place sensor nodes (i.e., only scattering
sensor nodes from the air achieves simple diffusion).

4.1. Theoretical basis for our proposal
In simple diffusion, p.d.f. of the sensor-positions is
a two-dimensional normal distribution. This is known
as a radial basis function. Daubechies [5] showed 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σ,
x − c).
h(x; c, σ) = exp(−
2σ 2

(3a)
(3b)

In Eq. (3), p(c, σ), c, and σ 2 are the weights, centerand variance for each normal distribution. This expression means infinite superposition of simple diffusion canlead to any form of stochastic sensor-placement. Since
this infinite superposition is hard to implement, we replace the integral in Eq. (3) with the finite superpositionof h(x; ci , σi ) as follows:M
F (x) ≈ j=1 pj (cj , σj )h(x; cj , σj ), (4a)x − cj h(x; cj , σj ) = exp(−
).
(4b)
2σj2
In Eq. (4), pj (cj , σj ), cj , and σj2 are the weights, center, and variance for each normal distribution. M means
the number of superpositions.

4.2. Parameters settings for simple diffusion
Achieving power-law placement is equivalent to determining parameters in Eq. (4). For implementation
simplicity, it is desirable that the amount of scattering
is small and that a regulation on the place of the centers
is imposed. According to this consideration, we propose
two fundamental ways of determining the parameters in
Eq. (4). Note that other ways such as combination ofboth ways are easily achieved by applying these two.
Simple diffusion with fixed centers In this way, centers of simple diffusion are placed in the same position
as the base station (we call this “simple diffusion with
fixed centers”). This corresponds to scattering M typesof sensor nodes with different form or weights (for different σi ) simultaneously in the air above the base station. This is the simplest way to implement Eq. (4),since only once scattering achieves this. Simple diffusion with fixed centers can be used when the area where
the sensor nodes are placed is relatively small. This isbecause there is an upper bound on the area where thesensors can reach using simple diffusion.
663

Power law (α= --0.3)

Power law (α=0)

f(x1,x2)
1e-05
1e-06
1e-07
1e-08-400-200 x 0
1

Power law (α=0.3)

f(x1,x2)200

0-400-200

400

1e-05
1e-06
1e-07
1e-08-400

200400x2-200 x 0
1

Simple diffusion

f(x1,x2)

200

400

0
-400-200

200400
x2

1e-05
1e-06
1e-07
1e-08-400-200 x 01

f(x1,x2)

200

400

0
-400-200

200400
x2

1e-05
1e-06
1e-07
1e-08-400-200 x 0
1

200

400

0
-400-200

200400x2

Figure 3. P.d.f. plots for various placements
Simple diffusion with concentric centers To copewith a large region D, we propose to place centersof simple diffusion on concentric circles. (we callthis “simple diffusion with concentric centers”). This
corresponds to scattering sensor nodes from helicopters
flying on concentric circles. An example of center’s
positions is shown in Fig. 4.
Next, we will describe each way in detail.

4.3. Simple diffusion with fixed centers
In this implementation, Eq. (4) is rewritten as folM p
lows:
(5)
F (x) ≈ j=1 2πσj 2 h(x; 0, σj ).
j

We determined the parameters in Eq. (5) through following strategies.
Since smaller value of M is better for implementation
simplicity, we minimize the value of M .
Under the given value of M , we formulate the optimization problem to determine the parameters (σj , pj ).
In this problem, we minimize sum of differences between the approximated p.d.f. and that of power-law
placementon xi that are uniformlydistributed over reM
gion D. We also add the constraint j=1 pj < P, (P ≥1) to set the upper bound for the number of sensor nodes.
To evaluate the validity of F (x), we compare thefault tolerance of this approximated placement with thatof power-law placement.In evaluation, we use a performance metric (i.e., the virtual sensing-success ratio) andsimulation scenarios described in Sect. 2.2. We consider
F (x) is valid when average of difference in the virtual
sensing-success ratio between this approximated placement and power-law placement is less than the predefined threshold Θ = 0.1 for both tolerances (i.e., tolerance against random failure and that against battery
exhaustion).

4.4. Simple diffusion with concentric centers
Let Mr be the number of concentric circles and rj
be the radius of these circles. Then, the coordinates
1

x2

0.5
0
-0.5
-1
-1

-0.5

0
x1

0.5

1

x12+x22=1
position of centers

Figure 4. An example of center’s positionsof centers are (rj cos θk , rj sin θk ), θk = 2πkMθ , (k =1, · · · , Mθ ). In addition, a center is placed in the same
position as the base station. The standard deviation andweights for simple diffusion in the same circle is thesame. In this implementation, Eq. (4) is rewritten as follows: r pj MθF (x) = M
j=1 2πσj2k=1 h(x; cjk , σj )pMr +1+h(x; 0, σMr +1 ),
(6a)
2
2πσM
r +1
cjk = (rj cos θk , rj sin θk ), θk = 2πk/Mθ . (6b)
We determined the parameters in Eq. (6) through following strategies.
Since a smaller Mr is better in terms of implementation simplicity, we minimize the value of Mr . We fix
the value of Mθ , since Mθ has less impact on the implementation simplicity.
Under the given value of Mr , we formulate the optimization problem to determine the parameters.
Mr +1 The
objective function and the constraint
j=1 pj <P, (P ≥ 1) are same as those in simple diffusion with
fixed centers. In addition, we add the constraint σj < S
to consider the upper bound for distance that sensor
nodes can reach using simple diffusion. Let Rmax be theupper bound of distance where sensor nodes can reachusing simple diffusion and R be the radius of region D.
To place more than 99% of sensor nodes within a circle
max= S. This means
whose radius is Rmax , σj < R3R
a smaller S is needed to place sensor nodes in a larger
area. The validity of F (x) is evaluated in the same way
as simple diffusion with fixed centers.

5. Performance of each implementation
In this section, we discuss the accuracy and fault
tolerance of each implementation. In evaluation, weused a performance metric and simulation scenarios in
Sect. 2.2.

5.1. Simple diffusion with fixed centers
We set P ∈ {1.06, 1.10, 1.16}. The minimum valueof M was 3 for each P . The p.d.f. plots at x2 = 0 are in
Fig. 5. In this figure, the density near the border of a unit
circle is less than that of power-law placement,since thedensity of simple diffusion decays very fast at the tailpart of the distribution. The larger value of P mitigates
the effect of this decay, since a larger P allows more664

sensor nodes are outside region D. These results indicate that there is a tradeoff between the number of sensor nodes and the accuracy of implementation. Next, let
us look at tolerance against random failure. The virtual
sensing-success ratio is plotted in Fig. 6. When there
are fewer broken nodes, the virtual sensing-success ratio in simple diffusion with fixed centers is lower thanthat in power-law placement. This difference is larger
when P is smaller, since the probability of there being
some sensor nodes within the sensing range of the target
decreases as P becomes smaller. This is because sensor
nodes are less dense near the border of region D as P
becomes smaller.
Last, let us look at the tolerance against battery exhaustion. The virtual sensing-success ratio is plotted inFig. 7. With fewer targets, virtual sensing-success ratio of simple diffusion with fixed centers is lower thanthat of power-law placement.This is because of the lower
density of sensor nodes near the border of region D. The
parameter P , on the other hand, has little effect on the
period when the virtual sensing-success ratio is reasonable. This is because only the density near the base station affects the existence of alternative routes to it andthe difference in density near the base station is not sogreat between each P value.
We conclude from these simulation results that fault
tolerance in simple diffusion with fixed centers is almost
the same as that of power-law placement with α = 0when the value of P is appropriately set.

5.2. Simple diffusion with concentric centers
We set S ∈ {0.10, 0.14, 0.18} and P = 1.1. The
minimum value of Mr was 3 for each S. The p.d.f. plots
at x2 = 0 for each S are shown in Fig. 8. In this figure,fluctuations in p.d.f. become higher as the distance fromthe origin increases. Since the distance between adjacentcenters on a circle becomes larger with the radius of acircle, the effect of the tail in simple diffusion increases
with the distance from the origin. This characteristic is
more remarkable when S is smaller, since the spread ofsimple diffusion is restricted by the value of S.
Next, let us now look at tolerance against random
failure. The virtual sensing-success ratio is plotted inFig. 9. When S is small, the virtual sensing-success ratio in simple diffusion with concentric centers is lower
than that in power-law placement. However, fluctuations
in p.d.f. do not affect the virtual sensing-success ratio somuch.
Last, let us look at the tolerance against battery exhaustion. The virtual sensing-success ratio is plotted inFig. 10. The difference between simple diffusion withconcentric centers and power-law placement increases
with the number of targets. In addition, this difference

becomes larger as S becomes smaller. These results indicate that the fluctuations in p.d.f. do not decrease theprobability of there being some sensors within the sensing range of the target but do decrease the probability ofthere being a route to the base station.
We conclude from these results that simple diffusion
with concentric centers has almost as high a fault tolerance as power-law placement with α = 0 when the valueof S is appropriately set.

6. Conclusion
We proposed two ways of achieving power-law
placement with α = 0 using superposition of simple
diffusion. The first way was through simple diffusion
with fixed centers that was suitable when the area thesensors were placed was relatively small. The second
was through simple diffusion with concentric centers,
which could be used even when the area the sensors
were placed was large. Both ways demonstrated powerlaw placement with α = 0 with reasonable complexity
and accuracy. Through simulation, we also found thatthe fault tolerance of each implementation was as highas that of power-law placement with α = 0 when thecontrol parameters were appropriately set.
This research was partially supported by the Grantin-Aid for Scientific Research from Ministry of Education, Science, Sports and Culture of Japan, under Grant
No. 16310116 (2004-2006).
We would like to thank Ms. Kyoko Ashitagawa forher help with the simulations.

References[1] H. Saito and H. Minami, “Performance Issues in Sensor Networking,” Proc. 18th International Teletraffic
Congress, Berlin, 2003.
[2] G. Hoblos, M. Staroswiecki, and A. Aitouche, “Optimal
Design of Fault Tolerant Sensor Networks,” Proc. IEEE
Int’l Conf. Cont. Apps., Sept. 2000, pp. 462–472.
[3] M. Bhardwaj, T. Garnett, and P. Chandrakasan, “Upper
Bounds on the Lifetime of Sensor Networks,” Proc. ICC’01, June 2001, pp. 785–790.
[4] C. Intangonwiwat, R. Govindan, and D. Estrin, “Directed Diffusion: A Scalable and Robust Communication
Paradigm for Sensor Networks,” Proc. ACM MobiCom’00, August 2000, pp. 56–67.
[5] I. Daubechies, Ten Lectures on Wavelets. CBMS-NSF
Regional Conference Series in Applied Mathematics, Society of Industrial and Applied mathematics, 1992.
[6] M. Ishizuka and M. Aida, “The Reliability Performanceof Wireless Sensor Networks Configured by Power-Law
and Other Forms of Stochastic Node Placement ,” IEICE
Trans. on Communications, vol.E87-B, no. 9, September
2004, pp. 2511–2520.

665

10

1

1

1

P=1.06
Power-law with α=0

0.1
-1

0
x1

p.d.f.

10

p.d.f.

p.d.f.

10

P=1.10Power-law with α=0

0.1
1

-1

0
x1

P=1.06

P=1.16
Power-law with α=0

0.1
1

-1

0
x1

P=1.101

P=1.16

1

0.8

0.8

0.6
0.4
0.2

Probability of success

1

0.8

Probability of success

Probability of successFigure 5. P.d.f. plots of simple diffusion with fixed centers
1

0.6
0.4
0.2

Fixed centers (Na=261)
Power-law (N=250)

0.2
Fixed centers (Na=289)
Power-law (N=250)

0
0.2

0.4

Fixed centers (Na=272)
Power-law (N=250)

0
0

0.6

0.4

0.6

0.8

1

0
0

0.2

0.4

0.6

0.8

1

0

0.2

0.4

0.6

Ratio of broken sensor nodes

Ratio of broken sensor nodes

Ratio of broken sensor nodes(a) P=1.05(b) P=1.10(c) P=1.16

0.8

1

1

1

0.8

0.8

0.6
0.4
0.2

Probability of success

1
0.8

Probability of success

Probability of successFigure 6. Virtual sensing-success ratio of simple diffusion with fixed centers (random failure)
0.6
0.4
0.2

Fixed centers (Na=261)
Power-law (N=250)

0.2
Fixed centers (Na=289)
Power-law (N=250)

0
50

0.4

Fixed centers (Na=272)
Power-law (N=250)

0
0

0.6

100
Number of generated targets

150

200

0
0

50

100
Number of generated targets(a) P=1.05

150

200

0

50

100
Number of generated targets(b) P=1.10

150

200

(c) P=1.16

Figure 7. Virtual sensing-success ratio of simple diffusion with fixed centers (battery exhaustion)

1

1

1

0.1

p.d.f.

10

p.d.f.

10

p.d.f.

100.1
S=0.10Power-law with α=0

0.01
-1

0
x1

0.1
S=0.14
Power-law with α=0

0.01
1

-1

0
x1

S=0.10S=0.18
Power-law with α=0

0.01
1

-1

0
x1

S=0.141

S=0.18Figure 8. P.d.f. plots of simple diffusion with concentric centers
1

0.6
0.4
0.2
0

1

Concentric centers (Na=265)
Power-law (N=250)

0.8

Probability of success

Concentric centers (Na=229)
Power-law (N=250)

0.8

Probability of success

Probability of success

1

0.6
0.4
0.2
0

0

0.2

0.4

0.6

0.8

1

Concentric centers (Na=277)
Power-law (N=250)

0.8
0.6
0.4
0.2
0

0

0.2

0.4

0.6

0.8

1

0

0.2

0.4

0.6

Ratio of broken sensor nodes

Ratio of broken sensor nodes

Ratio of broken sensor nodes(a) S=0.10(b) S=0.14(c) S=0.18

0.8

1

Figure 9. Virtual sensing-success ratio of simple diffusion with concentric centers (random
failure)
1

0.6
0.4
0.2
0

1

Concentric centers (Na=265)
Power-law (N=250)

0.8

Probability of success

Concentric centers (Na=229)
Power-law (N=250)
Probability of success

Probability of success

1
0.8

0.6
0.4
0.2
0

0

50

100

150

200

Concentric centers (Na=277)
Power-law (N=250)

0.8
0.6
0.4
0.2
0

0

50

100

150

200

0

50

100

Number of generated targets

Number of generated targets

Number of generated targets(a) S=0.10(b) S=0.14(c) S=0.18

150

200

Figure 10. Virtual sensing-success ratio simple diffusion with concentric centers (battery exhaustion)

666