Lazinica A. (ed.) Particle Swarm Optimization

Подождите немного. Документ загружается.

Finding Base-Station Locations in Two-Tiered Wireless Sensor Networks

by Particle Swarm Optimization

271

100

120

140

160

0 20406080100

ANs

Lifetime

Figure 8. The lifetimes along with different numbers of ANs

It can be seen from Figure 8 that the lifetime decreased along with the increase of the

number of ANs. It was reasonable since the probability for at least an AN in the system to

fail would increase when the number of ANS grew up. The execution time along with

different numbers of ANs is shown in Figure 9.

0,02

0,04

0,06

0,08

0,1

0,12

0 20406080100

ANs

Time (sec.)

Figure 9. The execution time along with different numbers of ANs

It can be observed from Figure 9 that the execution time increased along with the increase of

numbers of ANs. The relation was nearly linear. Experiments were then made to show the

relation between lifetimes and numbers of particles for 50 ANs and 300 generations. The

internal weight was set at 1. The experimental results are shown in Figure 10.

Particle Swarm Optimization

272

70.5

71.5

0 20406080100

Particles

Lifetime

Figure 10. The lifetimes along with different numbers of particles

It can be seen from Figure 10 that the lifetime increased along with the increase of numbers

of particles for the same number of generations. The execution time along with different

numbers of particles for 300 generations is shown in Figure 11.

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0 20406080100

Particles

Time (sec.)

Figure 11. The execution time along with different numbers of particles for 50 ANs

Method Lifetime

The proposed PSO algorithm 72.0763

The exhaustive grid search

(grid size = 1)

72.0048

The exhaustive grid search

(grid size = 0.1)

72.0666

The exhaustive grid search

(grid size = 0.01)

72.0752

Table 7. A lifetime comparison of the PSO approach and the exhaustive grid searc

Finding Base-Station Locations in Two-Tiered Wireless Sensor Networks

by Particle Swarm Optimization

273

It can be observed from Figure 11 that the execution time increased along with the increase

of numbers of particles. The relation was nearly linear. This was reasonable since the

execution time would be approximately proportional to the number of particles.

Note that no optimal solutions can be found in a finite amount of time since the problem is

NP-hard. For a comparison, an exhaustive search using grids was used to find nearly

optimal solutions. The approach found the lifetime of the system when a BS was allocated at

any cross-point of the grids. The cross-point with the maximum lifetime was then output as

the solution. A lifetime comparison of the PSO approach and the exhaustive search with

different grid sizes are shown in Table 7.

It can be observed from Table 7 that the lifetime obtained by our proposed PSO algorithm

was not worse than those by the exhaustive grid search within a certain precision. The

lifetime by the proposed PSO algorithm was 72.0763, and was 72.0048, 72.0666 and 72.0752

for the exhaustive search when the grid size was set at 1, 0.1 and 0.01, respectively. For the

exhaustive grid search, the smaller the grid size, the better the results.

7. Conclusion

In wireless sensor networks, minimizing power consumption to prolong network lifetime is

very crucial. In this paper, a two-tiered wireless sensor networks has been considered and

an algorithm based on particle swarm optimization (PSO) has been proposed for general

power-consumption constraints. The proposed approach can search for nearly optimal BS

locations in heterogeneous sensor networks, where ANs may own different data

transmission rates, initial energies and parameter values. Finding BS locations is by nature

very similar to finding the food locations originated from PSO. It is thus very easy to model

such a problem by the proposed algorithm based on PSO. Experiments have also been made

to show the performance of the proposed PSO approach and the effects of the parameters on

the results. From the experimental results, it can be easily concluded that the proposed PSO

algorithm converges very fast when compared to the exhaustive search. It can also be easily

extended to finding multiple base stations.

8. Acknowledgement

This research was supported by the National Science Council of the Republic of China under

contract NSC 97-2221-E-390-023. We also like to thank Mr. Cheng-Hsi Wu for his help in

making part of the experiments.

9. References

J. Chou, D. Petrovis and K. Ramchandran, A distributed and adaptive signal processing

approach to reducing energy consumption in sensor networks, The 22nd IEEE

Conference on Computer Communications (INFOCOM), pp. 1054-1062, San Francisco,

USA, March, 2003. [1]

R. C. Eberhart and J. Kennedy, A new optimizer using particles swarm theory, The Sixth

International Symposium on Micro Machine and Human Science, pp. 39-43, Nagoya,

Japan, October, 1995. [2]

R. C. Eberhart and J. Kennedy, Particle swarm optimization, The IEEE International Conference

on Neural Networks, Vol. 4, pp. 1942-1948, Perth, Australia, November, 1995. [3]

Particle Swarm Optimization

274

Z. L. Gaing, Discrete particle swarm optimization algorithm for unit commitment, The IEEE

Power Engineering Society General Meeting, Toronto, Canada, July, 2003. [4]

W. Heinzelman, J. Kulik, and H. Balakrishnan, Adaptive protocols for information

dissemination in wireless sensor networks, The Fifth ACM International Conference on

Mobile Computing and Networking, pp. 174-185, Seattle, USA, August, 1999. [5]

W. Heinzelman, A. Chandrakasan, and H. Balakrishnan, Energy-efficient communication

protocols for wireless microsensor networks, The Hawaiian International Conference on

Systems Science, Hawaii, USA, January, 2000. [6]

C. Intanagonwiwat, R. Govindan and D. Estrin, Directed diffusion: a scalable and robust

communication paradigm for sensor networks, The ACM International Conference on

Mobile Computing and Networking, Boston, USA, August, 2000. [7]

Vikas Kawadia and P. R. Kumar, Power control and clustering in ad hoc networks, The 22nd IEEE

Conference on Computer Communications (INFOCOM), San Francisco, USA, March, 2003. [8]

N. Li, J. C. Hou and L. Sha, Design and analysis of an mst-based topology control algorithm,

The 22nd IEEE Conference on Computer Communications (INFOCOM), San Francisco,

USA, March, 2003. [9]

S. Lee, W. Su and M. Gerla, Wireless ad hoc multicast routing with mobility prediction, Mobile

Networks and Applications, Vol. 6, No. 4, pp. 351-360, 2001. [10]

D. Niculescu and B. Nath, Ad hoc positioning system (APS) using AoA, The 22nd IEEE

Conference on Computer Communications (INFOCOM), pp. 1734-1743, San Francisco,

USA, March, 2003. [11]

J. Pan, Y. Hou, L. Cai, Y. Shi and X. Shen, Topology control for wireless sensor networks, The

Ninth ACM International Conference on Mobile Computing and Networking, pp. 286-299,

San Diego, USA, September, 2003. [12]

J. Pan, L. Cai, Y. T. Hou, Y. Shi and S. X. Shen, Optimal base-station locations in two-tiered

wireless sensor networks, IEEE Transactions on Mobile Computing, Vol. 4, No. 5, pp.

458-473, 2005. [13]

Y. Q. Qin, D. B. Sun, N. Li and Y. G. Cen, Path planning for mobile robot using the particle

swarm optimization with mutation operator, The IEEE Third International Conference on

Machine Learning and Cybernetics, pp. 2473-2478, Shanghai, China, August, 2004. [14]

V. Rodoplu and T. H. Meng, Minimum energy mobile wireless networks, IEEE Journal on

Selected Areas in Communications, Vol. 17, No. 8, 1999. [15]

R. Ramanathan and R. Hain, Topology control of multihop wireless networks using transmit

power adjustment, The 19th IEEE Conference on Computer Communications

(INFOCOM), Tel Aviv, Israel, March, 2000. [16]

Y. Shi and R. C. Eberhart, A modified particle swarm optimizer, The IEEE International

Conference on Evolutionary Computation, pp. 69-73, Anchorage, USA, May, 1998, [17]

A. Stacey, M. Jancic and I. Grundy, Particle swarm optimization with mutation, The IEEE Congress

on Evolutionary Computation, pp. 1425-1430, Canberra, Australia, December, 2003. [18]

D. Tian and N. Georganas, Energy efficient routing with guaranteed delivery in wireless

sensor networks, The IEEE Wireless Communication and Networking Conference, Orleans,

USA, March, 2003. [19]

F. Ye, H. Luo, J. Cheng, S. Lu and L. Zhang, A two-tier data dissemination model for large

scale wireless sensor networks, The

CM International Conference on Mobile Computing

and Networking, Atlanta, USA, September, 2002. [20]

Particle Swarm Optimization Algorithm for

Transportation Problems

Han Huang

and Zhifeng Hao

School of Software Engineering, South China University of Technology

College of Mathematical Science, South China University of Technology

P. R. China

1. Brief Introduction of PSO

Particle swarm optimization (PSO) is a newer evolutionary computational method than

genetic algorithm and evolutionary programming. PSO has some common properties of

evolutionary computation like randomly searching, iteration time and so on. However,

there are no crossover and mutation operators in the classical PSO. PSO simulates the social

behavior of birds: Individual birds exchange information about their position, velocity and

fitness, and the behavior of the flock is then influenced to increase the probability of

migration to regions of high fitness. The framework of PSO can be described as Figure 1.

Figure 1. The framework of classical PSO

In the optimal size and shape design problem, the position of each bird is designed as

variables

, while the velocity of each bird v influences the incremental change in the

position of each bird. For particle

Kennedy proposed that position

be updated as:

ddd

ttt

=+ (1)

111 22

()()

dd dd gd

t t tt tt

vvcrpxcrpx

=+ − + − (2)

Here,

is the best previous position of particle

at time t , while

is the global best

position in the swarm at time t .

r and

r are uniform random numbers between 0 and 1,

and

2cc==.

1. Initialize K

Particles

, ,...,

XX, calculating

,...,

best pbest and

gbest , 1t = ;

2. For

1,...,iK= and 1,...,

N= , update particles and use

to refresh

best and gbest ; (shown as equation 1 and 2)

1tt=+

; If max_tgen> , output gbest and exit; else, return Step 2.

Particle Swarm Optimization

276

2. Particle Swarm Optimization for linear Transportation Problem

2.1 Linear and Balance Transportation Problem

The transportation problem (TP) is one of the fundamental problems of network flow

optimization. A surprisingly large number of real-life applications can be formulated as a

TP. It seeks determination of a minimum cost transportation plan for a single commodity

from a number of sources to a number of destinations. So the LTP can be described as:

Given there are

n sources and m destinations. The amount of supply at source i is

and the demand at destination

. The unit transportation cost between source i and

destination

c .

is the transport amount from source

to destination

, and the

LTP model is:

min

ij ij

zcx

∑∑

s.t.

1,2,...,

ij i

ai n

≤=

∑

(3)

1,2, ...,

ij j

jmxb

=≥

∑

0; 1,2,..., ; 1,2,...,

injm≥= =

TP has been paid much attention to and classified into several types of transmutation.

According to the nature of object function, there are four types: (1) linear TP

and nonlinear

TP. (2) single objective TP and multi objective. Based on the type of constraints, there are

planar TP and solid TP. The single object LTP dealt with in this paper is the basic model for

other kinds of transportation problems.

A special LTP called balanced LTP is considered as follows:

min

ij ij

zcx

∑∑

s.t.

1,2,...,

ij i

ai n

∑

(4)

1,2,...,

ij j

bj m

∑

0; 1,2,..., ; 1,2,...,

xinjm≥= =

Particle Swarm Optimization Algorithm for Transportation Problems

277

The fact that a nm× LTP can be changed into a (1)nm×+ balanced LTP, can be found

in operational research

because the demand at destination 1m+ could be calculated by

mij

bab

=−

∑∑

with the condition

≥

∑

2.2 Initialization of PSO for Linear and Balance Particle Swarm Optimization

A particle

11 1

...

... ... ...

...

nnm

⎡⎤

⎢⎥

⎣⎦

stands for a solution to LTP. There are nm particles

initialized to form nm initial solutions in the initialization. Every element of set N can be

chosen as the first assignment to generate the solutions dispersedly, which is good for

obtaining the optimal solution in the iteration.

If a LTP is balanced, the following procedure can be used to obtain an initial solution:

program GetOnePrimal (var X: Particle, first: int)

var i,j,k: integer;

N: Set of Integer;

begin

k :=0;

N := {1,2,…,nm};

repeat

if k=0 then

k:=first ;

else

k:= a random element in N;

i :=

(k-1)/m + 1

⎢⎥

⎣⎦

;

j := ((k-1) mod m) +1;

:= min {a

, b

};

:= a

- x

;

:= b

- x

;

N := N \ {k};

until N is empty

end.

Particle Swarm Optimization

278

And the initialization of PSO-TP can be designed as follows:

program Initialization

var i : integer;

begin

Get a balanced LTP;

i := 1;

repeat

GetOnePrimal (X

, i);

i := i+1;

until i > nm

end.

2.3 Updating Rule of PSO for Linear and Balance Particle Swarm Optimization

In PSO algorithm, a new solution can be obtained by using the position updating rule as

equations 2 and 3. However, the classical rule is unable to meet such constraints of TP as

ij i

∑

and

ij j

∑

. A new rule is designed to overcome this shortcoming. For

particle

d , we propose that position

( nm× ) be updated as

121 2

()() 0

[( ) ( )] 0

tt tt

ttttt

dd gd

dddgd

PX PX t

VPXPXt

ϕϕ

λλϕ ϕ

⎧

−+ − =

⎨

+−+− >

⎩

(5)

ddd

ttt

=+ (6)

where

PX≠

and

PX≠

PX= and

PX≠ ,

= . If

PX≠ and

PX= ,

= . If

PX= and

PX= ,

= .

( nm× ) is the best previous position of particle d at time

, while

( nm× ) is the

global best position in the swarm at time t .

and

are uniform random numbers in (0,

1), meeting

ϕϕ

+=, while

is a uniform random number between [0.8, 1.0) and

λλ

=− .

0,if t =

ddd

ttt

()()

dd gd d

tt tt t

PX PX X

ϕϕ

=−+−+

12 1 2

()( )

dg d dd

tt t tt

PXXX

ϕϕ ϕ ϕ

+−+ +=

Particle Swarm Optimization Algorithm for Transportation Problems

279

(1)

∑

12 12

11 111

() () ( () ()) ()

mm mmm

dgddd

ij ij ij ij ij

jj jjj

tptxtxtxt

ϕϕ ϕϕ

== ===

=+− + +

∑∑ ∑∑∑

12 12

()

ii iiii

aa aaaa

ϕϕ ϕϕ

=+− + +=

(1)

∑

12 12

11 111

() () ( () ()) ()

nn nnn

dgddd

ij ij ij ij ij

ii iii

tptxtxtxt

ϕϕ ϕϕ

== ===

=+− + +

∑∑ ∑∑∑

12 12

()

jjjjj

bb bbbb

ϕϕ ϕϕ

=+− + +=

,0if t >

+ 1

121 2

[( ) ( )]

dddgdd

tttttt

VPXPXX

λλϕ ϕ

=+ −+ −+

1212 1 2

[( ) ( )]

ddgddd

tttttt

VPPXXX

λλϕϕ ϕ ϕ

++−++=

1121212

()[( )( )]

dd d g d d d

tt t t t t t

XPPXXX

λλϕϕϕϕ

−

=−+ +−+ +

(1)

∑

121212

(() (1))( ( ))

ij ij i i i i i

txt aaaaa

λ λϕϕ ϕϕ

−−++−++=

∑∑

()0

ii i i

aa aa

=−++=

(1)

∑

1 212 12

(() (1))( ( ))

ij ij j j j j j

txt bbbbb

λ λϕϕ ϕϕ

−−++−++=

∑∑

()0

jjj

bb bb

−++==

Particle Swarm Optimization

280

Therefore,

would meet the condition that

(1)

ij i

∑

and

(1)

ij j

∑

with the function of Formulae 5 and 6. However, the new rule cannot

ensure the last constraint that

0, 1,.., , 1,...,

inj m≥= =

. In the following section, an

extra operator is given to improve the algorithm.

2.4 Negative Repair Operator

A particle of PSO-TP (Formula 7) will be influenced by the negative repair operator if

0, 1,..., , 1,...,

knim<= =

, which is indicated as follows:

11 1 1

... ...

... ... .. . ... ...

... ...

...

... ...

...

... ...

kkikm

⎡

⎤

⎢

⎥

⎢

⎥

⎢

⎥

⎢

⎥

⎢

⎥

⎢

⎥

⎢

⎥

⎢

⎥

⎢

⎥

⎢

⎥

⎢

⎥

⎣

⎦

（7）

program RepairOnePos (var X: Particle, k,i: int)

begin

select the maximum element signed as

in Col. i;

x= ,

li li

xx=− , :0

x = ;

change elements in Row.k into

kj kj

⎧

⎪

⎨

⎪

⎩

−>

;

(

u is the number of times when the following condition

0, 1,...,

jm>=

is met)

change elements in Row. l into

lj kj

⎧

⎪

⎨

⎪

⎩

;

end.