Using A ificial In elligence in Wi eless Senso
Rou ing P o ocols
Julio Ba bancho, Ca los Le´on, Ja ie Molina, and An onio Ba bancho
Depa men o Elec onic Technology, Uni e si y o Se ille
C/ Vi gen de ´
A ica, 7. Se ille 41011, Spain
Tl no.: (+034) 954 55 71 92, Fax: (+034) 954 55 28 33
{jba bancho, cleon, jmolina, ayboc}@us.es
Abs ac . This pape ep esen s a disse a ion abou how an a ificial
in elligence echnique can be applied o wi eless senso ne wo ks. Due
o he cons ain s on da a p ocessing and powe consump ion, he use
o a ificial in elligence has been his o ically disca ded in hese kind o
ne wo ks. Howe e , in some special scena ios he ea u es o neu al ne -
wo ks a e app op ia e o de elop complex asks such as pa h disco e y.
In his pape , we explo e he pe o mance o wo e y well known ou-
ing pa adigms, di ec ed diffusion and Ene gy-Awa e Rou ing,andou
ou ing algo i hm, named SIR, which has he no el y o being based
on he in oduc ion o neu al ne wo ks in e e y senso node. Ex ensi e
simula ions o e ou wi eless senso ne wo k simula o , OLIMPO, ha e
been ca ied ou o s udy he efficiency o he in oduc ion o neu al ne -
wo ks. A compa ison o he esul s ob ained wi h e e y ou ing p o ocol
is analyzed.
Keywo ds: Wi eless senso ne wo ks (WSN); Ad hoc ne wo ks, Qual-
i y o se ice (QoS); A ificial neu al ne wo ks (ANN); Rou ing; Sel -
O ganizing Map (SOM), ubiqui ous compu ing.
1 In oduc ion
Goals like efficien ene gy managemen , high eliabili y and a ailabili y, com-
munica ion secu i y, and obus ness ha e become e y impo an issues o be
conside ed in wi eless senso ne wo ks (WSN). This is one o he many easons
why we can no neglec he s udy o he collision effec s and he noise influence.
We p esen in his pape a new ou ing algo i hm which in oduces a ificial
in elligence (AI) echniques o measu e he quali y o se ice (QoS) suppo ed
by he ne wo k.
This pape is o ganized as ollows. In sec ion 2, we ela e he main ou ing
ea u es we should conside in a ne wo k opology. A desc ip ion o he defined
ne wo k opology is gi en. Sec ion 3 in oduces he use o neu al ne wo ks in
senso s o de e mining he quali y o neighbo hood links, gi ing a QoS model
o ou ing p o ocols. The pe o mance o he use o his echnique in exis ing
ou ing p o ocols o senso ne wo ks is e alua ed by simula ion in sec ion 4.
Concluding ema ks and u u e wo ks a e gi en on sec ion 5.
2 Designing he Ne wo k Topology
The WSN a chi ec u e as a whole has o ake in o accoun diffe en aspec s, such
as he p o ocol a chi ec u e; Quali y-o -Se ice, dependabili y, edundancy and
imp ecision in senso eadings; add essing s uc u es, scalabili y and ene gy e-
qui emen s; geog aphic and da a-cen ic add essing s uc u es; agg ega ing da a
echniques; in eg a ion o WSNs in o la ge ne wo ks, b idging diffe en commu-
nica ion p o ocols; e c.
Due o he desi e o co e a la ge a ea, a communica ion s a egy is needed.
he e a e many s udies ha app oach he p oblem o high connec i i y in wi eless
ad hoc ne wo ks [1], [2]. In ou esea ch we conside a andom dis ibu ion o
senso s.
In gene al, ou ing in WSNs can be di ided in o fla -based ou ing, hie a -
chical-base ou ing, and loca ion-based ou ing. In his pape we s udy ne wo ks
whe e all nodes a e supposed o be assigned equal oles o unc ionali ies. In his
sense, fla -based ou ing is bes sui ed o his kind o ne wo ks.
Among all he exis ing fla ou ing p o ocols, we ha e chosen di ec ed diffusion
and Ene gy-Awa e Rou ing (EAR) o e alua e he influence o he use o AI
echniques.
In di ec ed diffusion [3], senso s measu e e en s and c ea e g adien s o in-
o ma ion in hei espec i e neighbo hoods. The base s a ion eques da a by
b oadcas ing in e es s. Each senso ha ecei es he in e es se s up a g adien
owa d he senso nodes om which i has ecei ed he in e es . This p ocess
con inues un il g adien s a e se up om he sou ces back o he base s a ion.
EAR [4] is simila o di ec ed diffusion. Ne e heless i diffe s in he sense
ha i main ains a se o pa hs ins ead o main aining o en o cing one op imal
pa h a highe a es. These pa hs a e main ained and chosen by means o a
ce ain p obabili y. The alue o his p obabili y depends on how low he ene gy
consump ion ha each pa h can achie e is. By ha ing pa hs chosen a diffe en
imes, he ene gy o any single pa h will no deple e quickly.
3 In oducing Neu ons in Senso Nodes
The necessi y o connec i i y among nodes in oduces he ou ing p oblem. In
a WSN we need a mul i-hop scheme o a el om a sou ce o a des iny. The
pa hs he packe s ha e o ollow can be es ablished based on a specific c i e ion.
Possible c i e ia can be minimum numbe o hops, minimum la ency, maximum
da a a e, minimum e o a e, e c. Fo example, imagine ha all he nodes
desi e o ha e a pa h o ou e da a o he base s a ion1. In his si ua ion, he
p oblem is sol ed by a echnique called ne wo k backbone o ma ion.
Ou app oach o enhance his solu ion is based on he in oduc ion o a ificial
in elligence echniques in he WSNs: expe sys ems, a ificial neu al ne wo ks,
uzzy logic and gene ic algo i hms. Due o he p ocessing cons ain s we ha e
1In WSN, we o en conside wo kind o nodes, base s a ions and senso nodes. The e
is usually only one base s a ion.
o conside in a senso node, he bes sui ed, among all hese echniques, is he
sel -o ganizing-map (SOM). This is kind o a ificial neu al ne wo k based on
he sel o ganiza ion concep .
SOM is an unsupe ised neu al ne wo k. The neu ons a e o ganized in an
unidi ec ional wo laye s a chi ec u e. The fi s one is he inpu o senso ial
laye , o med by mneu ons, one pe each inpu a iable. These neu ons wo k
as buffe s dis ibu ing he in o ma ion sensed in he inpu space. The inpu is
o med by s ochas ic samples x( )∈Rm om he senso ial space. The sec-
ond laye is usually o med by a ec angula g id wi h nxxnyneu ons. Each
neu on (i, j) is ep esen ed by an m-dimensional weigh o e e ence ec o
called synapsis,w
ij =[w
ij1,w
ij2,...,w

ijm], whe e mis he dimension o he
inpu ec o x( ). The neu ons in he ou pu laye -also known as he com-
pe i i e Kohonen laye - a e ully connec ed o he neu ons in he inpu laye ,
meaning ha e e y neu on in he inpu laye is linked o e e y neu on in he
Kohonen laye . In SOM we can dis inguish wo phases: he lea ning phase,
in which, neu ons om he second laye compe e o he p i ilege o lea ning
among each o he , while he co ec answe (s) is (a e) no known; and he
execu ion phase, in which e e y neu on (i, j) calcula es he simila i y be-
ween he inpu ec o x( ), {xk|1≤k≤m}and i s own synap ic-weigh - ec o
w
ij.
3.1 Ne wo k Backbone Fo ma ion
This p oblem has been s udied in ma hema ics as a pa icula discipline called
G aph Theo y, which s udies he p ope ies o g aphs.
Adi ec ed g aph Gis an o de ed pai G:= (V,A)wi hV, a se o e ices o
nodes, i,andA, a se o o de ed pai s o e ices, called di ec ed edges,a cs,o
a ows.
An edge xy =(x, y) is conside ed o be di ec ed om x o y;whe eyis called
he head and xis called he ail o he edge.
In 1959, E. Dijks a p oposed an algo i hm ha sol es he single-sou ce sho -
es pa h p oblem o a di ec ed g aph wi h nonnega i e edge weigh s.
We p opose a modifica ion on Dijks a’s algo i hm o o m he ne wo k back-
bone, wi h he minimum cos pa hs om he base s a ion o oo , , oe e y
node in he ne wo k. We ha e named his algo i hm Senso In elligence Rou ing,
SIR [5].
3.2 Quali y o Se ice in Wi eless Senso Ne wo ks
Once he backbone o ma ion algo i hm is designed, a way o measu ing he edge
weigh pa ame e , wij , mus be defined. On a fi s app oach we can assume ha
wij can be modelled wi h he numbe o hops. Acco ding o his assump ion,
wij =1∀i, j ∈R,i =j. Howe e , imagine ha we ha e ano he scena io in
which he node jis loca ed in a noisy en i onmen . The collisions o e jcan
in oduce link ailu es inc easing powe consump ion and dec easing eliabili y
in his a ea. In his case, he op imal pa h om node k o he oo node can
be p, ins ead o p. I is necessa y o modi y wij o sol e his p oblem. The
e alua ion o he QoS in a specific a ea can be used o modi y his pa ame e .
The adi ional iew o QoS in communica ion ne wo ks is conce ned wi h
end- o-end delay, packe loss, delay a ia ion and h oughpu . Nume ous au ho s
ha e p oposed a chi ec u es and in eg a ed amewo ks o achie e gua an eed
le els o ne wo k pe o mance [6]. Howe e , o he pe o mance- ela ed ea u es,
such as ne wo k eliabili y, a ailabili y, communica ion secu i y and obus ness
a e o en neglec ed in QoS esea ch. The defini ion o QoS equi es some ex en-
sions i we wan o use i as a c i e ion o suppo he goal o con olling he
ne wo k. This way, senso s pa icipa e equally in he ne wo k, conse ing ene gy
and main aining he equi ed applica ion pe o mance.
We use a QoS defini ion based on h ee ypes o QoS pa ame e s: imeliness,
p ecision and accu acy. Due o he dis ibu ed ea u e o senso ne wo ks, ou
app oach measu es he QoS le el in a sp ead way, ins ead o an end- o-end
pa adigm. Each node es s e e y neighbo link quali y wi h he ansmissions
o a specific packe named ping. Wi h hese ansmissions e e y node ob ains
mean alues o la ency, e o a e, du y cycle and h oughpu . These a e he ou
me icsweha edefined omeasu e he ela ed QoS pa ame e s.
Once a node has es ed a neighbo link QoS, i calcula es he dis ance o he
oo using he ob ained QoS alue. The exp ession 1 ep esen s he way a node
icalcula es he dis ance o he oo h ough node j,whe eqos is a a iable
whose alue is ob ained as an ou pu o a neu al ne wo k.
d( i)=d( j)·qos (1)
4 Pe o mance E alua ion by Simula ion
Due o he desi e o e alua e he SIR pe o mance, we ha e c ea ed wo simu-
la ion expe imen s unning on ou wi eless senso ne wo k simula o OLIMPO
[7]. E e y node in OLIMPO implemen s a neu al ne wo k (SOM) unning he
execu ion phase (online p ocessing).
Noise influence o e a node has been modelled as an Addi i e Gaussian Whi e
Noise, (AWGN), o igina ing a he sou ce esis ance eeding he ecei e . Acco d-
ing o he adio communica ion pa ame e s we can de e mine he signal- o-noise
a io a he de ec o inpu . This signal- o-noise a io can be exp essed as an as-
socia ed BER (Bi E o Ra e). An inc ease o he noise can deg ade he BER.
In ano he way, due o he ela ion be ween Eb/Noand he ansmission a e
(R), Eb/No=(S/R)/No,aninc easeo Rcan also deg ade he BER.
To e alua e he effec o noise we ha e defined a node s a e decla ed as ailu e.
When he BER goes down below a equi ed alue ( ypically 10−3)weassume
his node has gone o a ailu e s a e. We measu e his me ic as a pe cen age o
he o al li e ime o a node.
Ou SOM has a fi s laye o med by ou inpu neu ons, co esponding wi h
e e y me ic defined in sec ion 3.2 (la ency, h oughpu , e o a e and du y
cycle); and a second laye o med by wel e ou pu neu ons o ming a 3x4 ma ix.
Nex , we de ail ou SOM implemen a ion p ocess.
4.1 Lea ning Phase
In o de o o ganize he neu ons in a wo dimensional map, we need a se o
inpu samples x( )=[la ency( ), h oughpu ( ), e o - a e( ), du y-cycle( )]. This
samples should conside all he QoS en i onmen s in which a communica ion link
be ween a pai o senso nodes can wo k. In ou esea ch we c ea e se e al WSNs
o e OLIMPO wi h 250 nodes and diffe en le els o da a affic. The p ocedu e
o measu e e e y QoS link be ween wo neighbo s is de ailed as ollows: e e y
pai o nodes (eg. iand j) is exposed o a le el o noise. This noise is in oduced
inc easing he noise powe densi y Noin he adio channel in he p oximi y o
a de e mined node. Hence, he signal- o-noise a io a he de ec o inpu o his
selec ed node dec eases and consequen ly he BER ela ed wi h i s links wi h
e e y neighbo ge s wo se.
In o de o measu e he QoS me ics ela ed wi h e e y No,we unaping
applica ion be ween a selec ed pai o nodes (eg. iand j). Node isends pe i-
odically a ping message o node j. Because he ping equi es acknowledgmen
(ACK), he way node i ecei es his ACK de e mines a specific QoS en i-
onmen , exp essed on he ou me ics elec ed: la ency (seconds), h oughpu
(bi s/sec), e o a e (%) and du y cycle(%). This p ocess is epea ed 100 imes
wi h diffe en Noand d. This way, we ob ain a se o samples which cha ac e ize
e e y QoS scena io.
Wi h his in o ma ion, we cons uc a sel -o ganizing map using a high pe o -
mance neu al ne wo k ool, such as MATLAB, on a Pe sonal Compu e . This
p ocessiscalled aining, and uses he lea ning algo i hm. Because he aining
is no implemen ed by he wi eless senso ne wo k, we ha e called his p ocess
offline p ocessing.
Once we ha e o de ed he neu ons on he Kohonen laye , we iden i y each one
o he se o 100 inpu samples wi h an ou pu laye neu on. Acco ding o his
p ocedu e, he se o 100 inpu samples is dis ibu ed o e he SOM.
The ollowing phase is conside ed as he mos difficul one. The samples al-
loca ed in he SOM o m g oups, in such a way ha all he samples in a g oup
ha e simila cha ac e is ics (la ency, h oughpu , e o a e and du y cycle).
This way, we ob ain a map o med by clus e s, whe e e e y clus e co esponds
wi h a specific QoS and is assigned a neu on o he ou pu laye . Fu he mo e,
a synap ic-weigh ma ix w
ij =[w
ij1,w
ij2,...,w

ij4]is o med,whe ee e y
synapsis iden ifies a connec ion be ween inpu and ou pu laye .
In o de o quan i y he QoS le el, we s udy he ea u es o e e y clus e and,
acco ding o he QoS ob ained in he samples alloca ed in he clus e , we assign a
alue be ween 0 and 10. As a consequence, e define an ou pu unc ion Θ(i, j),i∈
[1,3],j ∈[1,4] wi h wel e alues co esponding wi h e e y neu on (i, j),i ∈
[1,3],j ∈[1,4]. The highes assignmen (10) mus co espond o ha scena io in
which he link measu ed has he wo s QoS p edic ed. On he o he hand, he
lowes assignmen (0) co esponds o ha scena io in which he link measu ed
has he bes QoS p edic ed. The assignmen is supe ised by an enginee du ing
he offline p ocessing.

4.2 Execu ion Phase
As a consequence o he lea ning phase, we ha e decla ed an ou pu unc ion,
ha has o be un in e e y senso node. This p ocedu e is named he wining
neu on elec ion algo i hm.
In he execu ion phase, we c ea e a WSN wi h 250 nodes. E e y senso node
measu es he QoS pe iodically unning a ping applica ion wi h e e y neighbo ,
which de e mines an inpu sample. A e a node has collec ed a se o inpu
samples, i uns he wining neu on elec ion algo i hm. A e he winning neu on
is elec ed, he node uses he ou pu unc ion Θ o assign a QoS es ima ion,
qos. Finally, his alue is employed o modi y he dis ance o he oo (eq. 1).
Because he execu ion phase is implemen ed by he wi eless senso ne wo k, we
ha e called his p ocess online p ocessing.
Ou SIR algo i hm has been e alua ed by he ealiza ion o h ee expe imen s
de ailed as ollows:
Expe imen #1: No node ailu e. The pu pose o his expe imen is o
e alua e he in oduc ion o AI echniques in a scena io we e he e is no node
ailu e. This means ha no node has gone o a ailu e s a e because o noise,
collision o ba e y ail influence.
To simula e his scena io, a wi eless senso ne wo k wi h 250 nodes is c ea ed
on ou simula o OLIMPO. Node # 0 is decla e as a sink and node # 22 is
decla ed as a sou ce. A a specific ime, an e en (eg. an ala m) is p o oked in
he sou ce. Consequen ly, he p oblem now is how o ou e he e en om he
specified sou ce o he decla ed sink.
As de ailed in sec ion 2 we sol e his p oblem wi h h ee diffe en ou ing
pa adigms: SIR, di ec ed diffusion and EAR. We choose wo me ics o analyze
he pe o mance o SIR and o compa e i o o he s schemes. These me ics a e:
he a e age dissipa ed ene gy, which compu es he a e age wo k done by a node
a in deli e ing use ul acking in o ma ion o he sinks ( his me ic also indica es
he o e all li e ime o senso nodes); and he a e age delay, which measu es he
a e age one-way la ency obse ed be ween ansmi ing an e en and ecei ing
i a each sink.
We s udy hese me ics as a unc ion o senso ne wo k size. The esul s a e
shown in figu es 1.a and 1.b.
Expe imen #2: 20 % simul aneous node ailu es. The pu pose o his
expe imen is o e alua e he in oduc ion o AI echniques in a scena io whe e
he e is a 20 % o simul aneous node ailu es. This means ha a any ins an , 20
% o he nodes in he ne wo k a e unusable because o noise, collision o ba e y
ailu e influence.
To simula e hese si ua ions we c ea e a WSN wi h 250 nodes. Amongs all o
hem, we selec 20 % o he nodes (50) o in oduce one o he ollowing effec s:
–S/N a io deg ada ion. Due o ba e y ene gy loss, he adio ansmi e
powe decays. Consequen ly, he S/N a io in i s neighbo s adio ecei e s
50 100 150 200 250
0
0.2
0.4
0.6
0.8
1
1.2
1.4
1.6
1.8
2
Ne wo k size (# nodes)
A e age delay (sec)
(a) 50 100 150 200 250
0.008
0.01
0.012
0.014
0.016
0.018
0.02
0.022
0.024
0.026
0.028
Ne wo k size (# nodes)
A e age dissipa ed ene gy (J/node/Recei ed da a packe )
Di ec ed di usion
EAR
SIR
(b)
50 100 150 200 250
0
5
10
15
20
25
30
Ne wo k size (# nodes)
A e age delay (sec)
Di ec ed di usion
EAR
SIR
(c)
50 100 150 200 250
0.008
0.01
0.012
0.014
0.016
0.018
0.02
0.022
0.024
0.026
0.028
Ne wo k size (# nodes)
A e age dissipa ed ene gy (J/node/Recei ed da a packe )
(d)
50 100 150 200 250
0
5
10
15
20
25
30
35
40
Ne wo k size (# nodes)
A e age delay (sec)
(e)
50 100 150 200 250
0.01
0.015
0.02
0.025
0.03
0.035
0.04
Ne wo k size (# nodes)
A e age dissipa ed ene gy (J/node/Recei ed da a packe )
( )
Di ec ed di usion
EAR
SIR
Di ec ed di usion
EAR
SIR
Di ec ed di usion
EAR
SIR
Di ec ed di usion
EAR
SIR
Fig. 1. A e age la ency and a e age dissipa ed ene gy in a scena io wi h no simul a-
neous node ailu e [(a) and (b)]; wi h 20 % simul aneous node ailu es [(c) and (d)];
and wi h 40 % simul aneous node ailu es [(e) and ( )]
is deg aded, causing no de ec ions wi h a ce ain p obabili y, P.In his
si ua ion, we can assume ha he node affec ed by he lack o ene gy is
p one o ailu e wi h p obabili y P.
–In many ac ual occasions, senso nodes a e exposed o high le el o noise,
caused by induc i e mo o s. Fu he mo e, he adio equency band is sha ed
wi h o he applica ions ha can in e e e wi h ou WSN.
In hese scena io we analyze he p oblem s udied desc ibed in expe imen
#1 wi h he h ee pa adigms ela ed. The esul s a e shown in figu es 1.c
and 1.d.
Expe imen #3: 40 % simul aneous node ailu es. This expe imen si-
mula es a scena io wi h a 40 % o simul aneous node ailu es. The esul s a e
shown in figu es 1.e and 1. .
5 Conclusion and Fu u e Wo ks
SIR has been p esen ed in his pape as an inno a i e QoS-d i en ou ing algo-
i hm based on a ificial in elligence. This ou ing p o ocol can be used o e wi e-
less senso ne wo ks s anda d p o ocols, such as IEEE 802.15.4 and Blue oo h,
ando e o he wellknownp o ocolssuchasA achne,SMACS,PicoRadio,e c.
The inclusion o AI echniques (e.g. neu al ne wo ks) in wi eless senso ne -
wo ks has been p o ed o be an use ul ool o imp o e ne wo k pe o mances.
The g ea effo made o implemen a SOM algo i hm inside a senso node
means ha he use o a ificial in elligence echniques can imp o e he WSN pe -
o mance. Acco ding o his idea, we a e wo king on he design o new p o ocols
using hese kinds o ools.
Re e ences
1. K. Aspnes, D. Goldenbe g, and Y. Yang. On he compu a ional complexi y o senso
ne wo k loca ion. Lec une No es In Compu e Science, Sp inge Ve lag, 3121:235–
246, July 2004.
2. S. Saginbeko and I. Ko peoglu. An ene gy efficien sca e ne o ma ion algo i hm
o blue oo h-based senso ne wo ks. In E. C¸ayi cy, S¸. Bayde e, and P. Ha inga,
edi o s, P oceedings o he Second Eu open Wo kshop on Wi eless Senso Ne wo ks,
pages 207–216, Is anbul, Tu key, Feb ua y 2005. IEEE, IEEE P ess.
3. C. In anagonwiwa , R. Go indan, and D. Es in. Di ec ed diffusion: a scalable
and obus communica ion pa adigm o senso ne wo ks. In P oceedings o ACM
Mobicom 2000, pages 56–67, Bos on, MA, USA, 2000.
4. R.C. Shah and J. Rabaey. Ene gy awa e ou ing o low ene gy ad hoc senso
ne wo ks. In P oceeedings o IEEE WCNC, pages 17–21, O lando, FL, USA, 2002.
5. J. Ba bancho, C. Le´on, F.J. Molina, and A. Ba bancho. SIR: A new wi eless senso
ne wo k ou ing p o ocol based on a ificial in elligence. Lec u e No es in Compu e
Science, Sp inge Ve lag, 3842:271–275, Janua y 2006.
6. B. Saba a, S. Cha e jee, M. Da is, J.J. Sydi , and T.F. Law ence. Taxonomy o
QoS specifica ions. In P oceedings o he hi d In e na ional Wo kshop on Objec -
O ien ed Real-Time Dependable Sys ems, pages 100–107. IEEE, IEEE P ess, 1997.
7. J. Ba bancho, F.J. Molina, D. Le´on, J. Rope o, and A. Ba bancho. OLIMPO, an ad-
hoc wi eless senso ne wo k simula o o public u ili ies applica ions. In E. C¸ayi cy,
S¸. Bayde e, and P. Ha inga, edi o s, P oceedings o he Second Eu open Wo kshop on
Wi eless Senso Ne wo ks, pages 419–424, Is anbul, Tu key, Feb ua y 2005. IEEE,
IEEE P ess.