Ga ido-Cas ellano and Mu illo-Fuen es EURASIP Jou nal on Wi eless Communica ions and
Ne wo king (2015) 2015:171
DOI 10.1186/s13638-015-0382-6
RESEARCH Open Access
On he implemen a ion o dis ibu ed
asynch onous non-linea ke nel me hods o e
wi eless senso ne wo ks
Juan A. Ga ido-Cas ellano*and Juan J. Mu illo-Fuen es
Abs ac
In his pape , we ace he implemen a ion o a non-linea ke nel me hod o eg ession on a wi eless senso ne wo k
(WSN) based on MICAz mo es. The ope a ing sys em used is TinyOS 2.1.1. The algo i hm es ima es he alue o some
magni ude om he measu emen s o he mo es in a dis ibu ed app oach whe e in o ma ion and compu a ions a e
pe o med asynch onously. This p oposal includes a esea ch on he po en ial p oblems encoun e ed along wi h he
de eloped solu ions. Namely, ma ix and loa ing compu a ions, acknowledgemen mechanisms and da a loss.
Keywo ds: Wi eless senso ne wo k; Dis ibu ed; Linea ; Ke nel me hod; Asynch onous; Algo i hm; MICAz; Mo e;
TinyOS
1 In oduc ion
Wi eless senso ne wo ks (WSNs) a e e y use ul o mon-
i o physical condi ions in la ge o di icul access en i-
onmen s. Due o hei wi eless capabili ies and hei use
o ba e ies, hese ne wo ks ha e low cos s o deploymen .
The nodes, usually known as mo es, may include senso s
o many kinds. Since hey a e also endowed wi h p o-
cessing capabili ies, hey can pe o m a se o algo i hms
acco dingly o he esul o he measu emen s. These ea-
u es open a wide spec um o applica ions o WSNs [1].
They can be seen as in elligen and au onomous ne wo ks.
A WSN is o en unde s ood as a ne wo k wi h a cen-
al node ha uns he main ope a ions such as ne wo k
synch oniza ion, da a p ocessing and s o age, while he
es o nodes would jus ake measu es o la e send hem
o he cen al node. We may ind se e al eal implemen-
a ions o cen alized WSNs, e.g. in ag icul u e [2] o
acking [3]. Howe e , i is well known ha his opol-
ogy has se e al p oblems in la ge ne wo ks due o i s
dependency on he cen al node. To name a ew:
•Unbalanced ene gy consump ion: since
compu a ions and communica ions a e concen a ed
in one and a ew nodes, espec i ely.
*Co espondence: [email p o ec ed]
Depa men o Signal and Communica ions Theo y, Uni e sidad de Se illa,
Camino Descub imien os, s/n - Isla Ca uja, Se ille, Spain
•Ine icien use o ne wo k bandwid h: la ge numbe
o elays and nodes a ound cen al node wi h high
a es associa ed, also was ing ene gy.
•Un eliabili y: i he cen al node o nodes a ound i
ge down o any eason, he ne wo k is una ailable.
•Poo esponse ime: in la ge ne wo ks, we ha e la ge
la encies associa ed o elays and managemen o
huge amoun s o da a.
These p oblems can be sol ed by using a dis ibu ed
ne wo k model (see Fig. 1), whe e all nodes compu e
he solu ion o he loca ions in i s neighbou hood by
in e changing in o ma ion locally.
The e a e simple me hods o make dis ibu ed es i-
ma ions such as leas squa es eg ession. Ne e heless,
a ending o he applica ion, mo e imp o ed algo i hms
may be needed. Fo example, in s uc u al heal h mon-
i o ing (SHM), some app oaches in WSN need o man-
age non-linea cases in a dis ibu ed a chi ec u e [4].
And suppo ec o machine-based non-linea dis ibu ed
app oaches can be applied o sol e localiza ion p oblems
om RSSI pa ame e s [5]. In his sense, some gene al
amewo ks o dis ibu ed ke nel app oaches ha e been
p esen ed in [6, 7] o sol e non-linea eg ession in a
dis ibu ed and eal- ime way. The design o dis ibu ed
in elligen WSN in ol es bo h he design o dis ibu ed
algo i hms (like [4–8]) and hei implemen a ion. While
he o me is pla o m independen , he la e se s ou
© 2015 Ga ido-Cas ellano and Mu illo-Fuen es. This is an Open Access a icle dis ibu ed unde he e ms o he C ea i e
Commons A ibu ion License (h p://c ea i ecommons.o g/licenses/by/4.0), which pe mi s un es ic ed use, dis ibu ion, and
ep oduc ion in any medium, p o ided he o iginal wo k is p ope ly c edi ed.
Ga ido-Cas ellano and Mu illo-Fuen es EURASIP Jou nal on Wi eless Communica ions and Ne wo king (2015) 2015:171 Page 2 o 14
Fig. 1 Example o dis ibu ed wi eless senso ne wo k
some in e es ing p oblems when ansla ed o a WSN
a chi ec u e.
Some wo ks on dis ibu ed implemen a ions ha e
al eady been p oposed [9, 10]. Howe e , o ou knowledge,
he e is no implemen a ion desc ip ion o complex non-
linea ke nel-based algo i hms epo ed in he li e a u e,
like he ones in [6, 7]. Due o he impo an bene i s o
hese algo i hms, we ha e selec ed hem as a a ge o
s udy as a eal implemen a ion o e a ne wo k composed
by simple mo es like MICAz, using he empe a u e ield
o easily illus a e he pe o mance o he algo i hm. These
algo i hms a e qui e demanding on bo h communica ion
and p ocessing capabili ies. So, he main ques ion o ace
is abou i s easibili y when implemen ed on an s anda d
WSN wi h low esou ces mo es. We posi i ely answe his
ques ion by p oposing a solu ion o his p oblem.
The algo i hm in [7] is based on he ke nel leas squa es
(KLS) algo i hm. I s main ad an age is ha al hough i
is compu ed in a dis ibu ed way, i con e ges o he
solu ion o he cen alized e sion. As discussed, he
dis ibu ed KLS (DKLS) is highly demanding in e ms o
communica ion and compu a ion capabili ies. I equi es
ma ix and ke nel ope a ions a he same ime han
mul i-node communica ion managemen . Ou solu ion is
possible hanks o he e sa ile ea u es o TinyOS, he
ope a ing sys em ha will be used o p og am and compile
he applica ion in o he mo es.
Besides he compu a ional complexi y o he algo i hm,
we ha e ound se e e p oblems wi h da a packe loss,
managemen o he anscei e bu e s and unsuppo ed
ha dwa e loa ing poin da a compu a ion. The wo i s
p oblems ha e been sol ed de eloping a new laye o
communica ion handling ha wo ks as an ex ension o
he ela ed na i e lib a ies o TinyOS, in which no only
da a bu e ing ea u es ha e been ex ended bu also some
changes in o hese na i e lib a ies ha e been done in o de
o imp o e he pe o mance. On he o he hand, ega d-
ing he loa ing poin da a managemen , TinyOS p o ides
a so wa e emula ion wi h se e e limi a ions when using
wi h ma ix da a. In his way, a wo-s ep solu ion has been
adop ed o allow hese ope a ions.
This pape is o ganized as ollows. In Sec ion 2, we
in oduce he eg ession algo i hm o be implemen ed,
s a ing wi h he classic KLS eg ession and ending wi h
he DKLS algo i hm. Nex , he modi ied DKLS (m-DKLS)
algo i hm, an e olu ion o DKLS, is explained in Sec ion
3. I s implemen a ion is ou a ge in his pape . In Sec ion
4, we p o ide an o e iew on he main concep s o his
ope a ing sys em, in o de o be e unde s and he limi-
a ions la e ound, which a e de ailed in Sec ion 5. These
limi a ions a e he s a ing poin o ou wo k. The ideas
o sol e hese p oblems a e p esen ed in Sec ion 6. The
nex s ep is de ailed in Sec ion 7, whe e we de elop
he implemen a ion in a MICAz ne wo k. In Sec ion 8,
he es ing scena io is de ined, and some ob ained esul s
a e included. Finally, in Sec ion 9, we summa ize he
wo k done, es ablishing in Sec ion 9.1 some poin s o
imp o emen and pending wo k o be done in his line o
esea ch.
2 Dis ibu ed ke nel leas squa es
2.1 Classic ke nel leas squa es eg ession
As in oduced in [11], he classic ke nel leas squa es
eg ession me hod is a well-known app oach based on
applying he ke nel ick o he linea leas squa es algo-
i hm. Gi en xi∈Rd, a se o aining inpu s, and yi∈R,
he co esponding ou pu s, wi h i=1, ..., n, healgo i hm
inds he hype plane in he non-linea ly ans o med ke -
nel space, (x), ha be e i s a gi en se o aining da a,
minimizing a leas squa es c i e ia. Then, o any new o
es inpu , x, he me hod p edic s he ou pu as (x).Ina
WSN, he inpu xicould be he posi ion coo dina es while
he ou pu yicould be some en i onmen measu e, e.g. he
empe a u e.
In he compu a ion o he p edic ion, (x),anop imiza-
ion p oblem is sol ed whe e a loss unc ion, L,be ween
he u h yiand i s p edic ion (xi)
L(yi, (xi)) ≥0, (1)
is a e aged o e he join p obabili y densi y unc ion o
he inpu and ou pu s,
R( )=Y×X
L(y, (x))p(y,x)dydx(2)
whe e R( )is he so-called isk unc ion.
Usually, he isk o making es ima ions canno be com-
pu ed because he join dis ibu ion be ween he inpu s
and he ou pu s is unknown. Howe e , we can compu e
Ga ido-Cas ellano and Mu illo-Fuen es EURASIP Jou nal on Wi eless Communica ions and Ne wo king (2015) 2015:171 Page 3 o 14
an app oxima ion a e aging he e o unc ion o he
a ailable da a, as i is o mula ed by he empi ical isk min-
imiza ion (ERM) p inciple. The o mula ion in (2) yields
Remp( )=
n

i=1
L(yi, (xi)).(3)
Using he leas squa es (LS) loss unc ion, we ge :
Remp( )=
n

i=1
(yi− (xi))2.(4)
Since he e is an in ini e se o non-linea p edic ion
unc ions, (x), ha i he ou pu da a, we need o con-
s ain he solu ion. This is achie ed h ough Thikono
egula iza ion. We ge he classic o mula ion (5) o he
KLS p oblem,
λ(·)=a g min
∈HK
1
n
n

i=1
( (xi)−yi)2+λ 2
HK.(5)
The op imiza ion a iable is , which is a unc ion con-
s ained o be in HK, he ep oducing ke nel Hilbe space
induced by he ke nel k(·,·), deno ing by ·
HKi s no m.
HKis a ec o space o unc ions wi h a ce ain (and con-
enien ) inne p oduc . No e ha in (5), we compu e (·)
o minimize he mean squa e e o wi h he i s e m,
while wi h he las one we o ce he solu ion (·) o ha e
minimum no m o a oid o e i ing. The inne -p oduc
s uc u e implies ha he solu ion o (5), deno ed by λ(·),
sa is ies:
λ(·)=
n

i=1
cλ,ik(·,xi)(6)
o some cλ∈R .This ac isknownas he ep esen-
e heo em in [12]. In he case o leas squa es, cλis he
solu ion o a sys em o nlinea equa ions, sa is ying:
cλ=(K+λI)−1y(7)
whe e Kis he ke nel ma ix whose elemen s a e de ined
by kij =k(xi,xj), and he ke nel is p e-speci ied.
2.2 Dis ibu ed ke nel leas squa es (DKLS)
2.2.1 Dis ibu ed de ini ion o KLS
The p e ious solu ion is a cen alized algo i hm and can-
no be implemen ed in a dis ibu ed app oach as i is. Le
us suppose ha we ha e a wi eless senso ne wo k o m
nodes and we ha e n≤mmeasu emen s om hem as
aining samples. Using he same no a ion as in Sec ion
2.1, we could hink o posi ion as inpu s xi∈R3, and em-
pe a u e measu es yias ou pu s. The aining samples a e
ensembles in he se Sn. Le us suppose ha no all nodes
ha e access o all he samples, so he aining samples
accessible om node jis he subse Sj
n.Le usalsodeno e
he se o he indices o he aining samples in Snby Sn
and he indices o aining samples accessible by node jas
Sj
n.
The i s app oxima ion o a dis ibu ed p oblem in his
scena io is o compu e mcen alized solu ions, one o
each node o he ne wo k, so he classical KLS p oblem
could be w i en as:
min
j∈HK
n

i=1
(zi−yi)2+
m

j=1
λj j2
HK(8)
s. .zi= j(xi),∀i∈Sn,j=1, ..., m.(9)
In his p oblem, he op imiza ion a iables a e z∈Rn,
i.e. { j}m
j=1, and a he han inding a unc ion (·),wea e
es ima ing a se o hem.
The cons ain s in (9) equi e ha all nodes ag ee on he
aining da a. This ac makes i o be equi alen o he
classic KLS p oblem, ge ing he cen alized solu ion, i.e.
j(·)= λ(·) o j=1, ..., m(see Lemma 1 in Appendix
o [6]). So, we can associa e a cen alized eg ession o a
global ag eemen o nodes on he aining samples. Bu we
could hink o an associa ion o a dis ibu ed eg ession o
a local ag eemen ins ead. Local ag eemen would in ol e
ha only a limi ed numbe o samples a e sha ed be ween
each wo nodes. This las p oblem can be desc ibed as
ollows,
min
j∈HK
i∈Sj
n
(zi−yi)2+
m

j=1
λj j2
HK(10)
s. .zi= j(xi),∀i∈Sj
n,j=1, ..., m.(11)
In his o mula ion, he solu ion is easible i and only i
j(xi)=zi= k(xi) o (xi,yi)∈Sj
n∩Sk
nand o j,k=
1, ..., m; ha is, i and only i e e y pai o node decision
ules ag ee on samples hey sha e. We ge (z, 1, ..., m)as
he minimize solu ion o (10), and jis a unc ion o only
he aining samples in Sj
nas pa o he join minimize .
2.2.2 Successi e o hogonal p ojec ions algo i hm
A dis ibu ed app oach o KLS p oblem has been shown
in he p e ious subsec ion. He e, we ace i s solu ion,
o which an al e na e p ojec ions algo i hm is p oposed
in [6], aking in o accoun he simila i ies be ween bo h
p oblems. In pa icula , he algo i hm uses he non-
elaxed successi e o hogonal p ojec ion (SOP) algo i hm,
nex desc ibed.
Le C1, ..., Cmbe closed con ex subse s o he Hilbe
space H, whose in e sec ion C=∩
m
i=1Ciis non-emp y.
Le PC(ˆ
)deno e he o hogonal p ojec ion o ˆ
∈Hon o
C:
PC(ˆ
)a g min
∈C −ˆ
(12)
And he o hogonal p ojec ion o ˆ
∈Hon o Ci:
PCi(ˆ
x)a g min
∈Ci
 −ˆ
(13)
Ga ido-Cas ellano and Mu illo-Fuen es EURASIP Jou nal on Wi eless Communica ions and Ne wo king (2015) 2015:171 Page 4 o 14
In [6, 13], i is de ined he successi e o hogonal p ojec-
ion (SOP) algo i hm o compu e PC(·)using PCi(·)m
i=1as
ollows:
0:=ˆ
:=PC( mod m)+1( −1)(14)
In his de ini ion (14), we deno e by ( modm) o he
emainde o he di ision /m. I es ablishes ha he PC(·)
can be compu ed p ojec ing sequen ially on o all he con-
ex subse s Ci,using o hePCi+1 he esul o he p e ious
p ojec ion: i s , i p ojec s ˆ
on o C1, he esul PC1is p o-
jec ed on o C2, and i i e a es in his way successi ely a
ce ain numbe o imes.
As poin ed ou in [6] (Theo em 2), i is demons a ed in
[14] ha o e e y ∈Cand e e y ≥1
 − ≤ −1− (15)
and ha
lim
n→∞ n∈(∩m
i=1Ci)(16)
lim
n→∞  −PC(ˆ
)= 0 (17)
i Cia ea ine o alli∈{1, ..., m}.Hence, hemo e
i e a ions we pe o m, he mo e accu a e esul we
ge .
2.2.3 Dis ibu ed KLS solu ion
I is possible o ede ine he p oblem in (10) in e ms o he
SOP algo i hm [6], whe e he Hilbe space H=Rn×Hm
K
wi h no m
(z, 1, ..., m)2= z2
2+
m

i=1
λi i2
HK(18)
is de ined. Wi h i , (10) can be in e p e ed as he o hog-
onal p ojec ion o he ec o (y, 0, ..., 0)∈Hon o he se
C=∩
m
j=1Cj⊂H,wi h
Cj=(z, 1, ..., m): j(xi)=zi,∀i∈Sj
n,
z∈Rn, jm
j=1⊂HK⊂H(19)
I is impo an o no e ha , o any =(z, 1, ..., m)∈H,
he compu a ion o
PCj( )=a g min
∈Cj
 − (20)
is es ic ed o he locally accessible aining examples
by node j.I means ha compu ingPCj( )lea es zi
unchanged o all i/∈Sj
nand lea es kunchanged o all
k= j.
The new unc ion associa ed wi h he node jcan be
compu ed using j,{xi}i∈Sj
n
and he message a iables
{zi}i∈Sj
n
. This me hod de ines he DKLS algo i hm (using
he no a ion o [7]), shown in Algo i hm 1.
Algo i hm 1 DKLS algo i hm
Ini ializa ion
Each node jb oadcas s hei loca ion xj o i s neigh-
bou ing senso s.
Each node jb oadcas s hei measu emen yj o hei
neighbou ing senso s.
Each node jini ializes zk=yk,∀k∈Sj
n.
Each node jini ializes j,0 =0.
T aining
o =1,...,T do
o j=1, ..., mdo
j, =a gmin
∈HK
i∈Sj
n
( (xi)−zi)2+λj − j, −12
HK
Node jb oadcas s j, (xk)∀k∈Sj
n
E e y node sha ing da a i eplaces zkby
j, (xk),∀k∈Si
n
end o
end o
I is in e es ing o no e ha he solu ion in (10) is an
app oxima ion o he cen alized KLS. As discussed in
[6], he neighbou hood o a mo e limi s he accu acy o
i s es ima ions, so local connec i i y in luences an es i-
ma o ’s bias. In [6, 7], he e a e some s udies ha show
h ough simula ions ha he e o decays exponen ially
wi h he numbe o neighbou s.
3 Non-linea asynch onous dis ibu ed algo i hm
The DKLS algo i hm in [6] is bene icial in many ways, bu
in [7], he au ho s highligh se e al limi a ions:
•A e each node comple es i s aining s age, i mus
gene a e a p edic ion o each neighbou (a di e en
message compu a ion o each one).
•Due o ha , he communica ion bu den g ows wi h
he numbe o neighbou s, and i means ha he
communica ion and compu a ion load can be high.
•Each node b oadcas s one es ima ion o each
neighbou node, and all o hese messages should be
ecei ed by all o i s neighbou s. Le us deno e n0as
he sende mo e and n1,n2as neighbou s o n0. Node
n0would b oadcas bo h j, (xn1)and j, (xn2)and
bo h would be ecei ed by n1and n2.I n1and n2a e
no neighbou s be ween hem, hey mus disca d he
non-co esponding message, bu he packe al eady
ha e been ecei ed and ead. This means was e o
esou ces, in e ms o p ocessing and ene gy
consump ion.
•I needs a synch oniza ion o he ne wo k o do he
aining s ep, because we can only ain one node a a
Ga ido-Cas ellano and Mu illo-Fuen es EURASIP Jou nal on Wi eless Communica ions and Ne wo king (2015) 2015:171 Page 5 o 14
ime. O he wise, a node could ecei e se e al upda es
o zk, and hen i would no know which one should
keep.
•Finally, i a senso s ops wo king (o some adio link
ails) hen he lea ning p ocedu e s ops, and he nex
node does no ecei e new p edic ions so i does no
s a i s aining s age.
To o e come hese limi a ions, in [7], he au ho s p opose
a simple modi ica ion in he algo i hm: ins ead o ans-
mi ing j, (xk) o k ∈Sj
n, he node would only b oadcas
j, (xj)( he p edic ion o he cu en node) o all i s
neighbou s. The esul ing algo i hm is he modi ied DKLS
algo i hm (m-DKLS, see Algo i hm 2).
Algo i hm 2 Modi ied DKLS algo i hm (m-DKLS)
Ini ializa ion
Each node jb oadcas s hei loca ion xj o i s neigh-
bou ing senso s.
Each node jb oadcas s hei measu emen yj o hei
neighbou ing senso s.
Each node jini ializes zk=yk,∀k∈Sj
n.
Each node jini ializes j,0 =0.
T aining
o =1,...,T do
o j=1, ..., mdo
j, =a gmin
∈HK
i∈Sj
n (xi)−zi2+λj − j, −12
HK
Node jb oadcas s j, (xj)
Each neighbou ing node eplaces zjby j, (xj)
end o
end o
The bene i s o he algo i hm can be summa ized as
ollows:
•I educes he numbe o messages gene a ed om Nj
( he numbe o neighbou s o node j) o1.I only
needs o b oadcas one message.
•Since i b oadcas s only one da a, he e is no need o
synch onize he ne wo k. Each node decides when o
ansmi .
•I a connec ion be ween wo nodes s ops wo king, i
does no s op he aining s age o he o he nodes o
he ne wo k.
Al hough i exhibi s a sligh ly wo se con e gence
han he DKLS app oach, again he e o educes
exponen ially wi h he numbe o neighbou s. The num-
be o e ansmissions educes signi ican ly while he
numbe o i e a ions inc eases o achie e a gi en e o
le el [7]. In addi ion, he e ansmissions can be pe -
o med asynch onously.
A his poin i is in e es ing o no e ha he m-DKLS
algo i hm can be easily ex ended o o he ke nel me hods
di e en o he KLS.
4 B ie in oduc ion o TinyOS
4.1 NesC o e iew
TinyOS is an open sou ce ope a ing sys em designed o
wo k speci ically wi h wi eless senso ne wo ks. I has an
e en -o ien ed a chi ec u e, and i has a se o lib a ies
ha p o ides da a acquisi ion ools o he mo es. These
lib a ies a e open sou ce, so he code is a ailable o be
modi ied. I uses he NesC p og amming language, which
is a dialec o he C language ha adds some addi ional
e en -o ien ed ea u es.
E e y NesC applica ion is based on modula p og am-
ming. An applica ion is composed by one o mo e com-
ponen s. Each componen can be seen as a unc ional pa
o he applica ion. Each componen has in e aces.These
in e aces a e used o connec his componen o o he
componen s o he applica ion. In e aces use wo kind o
ope a ions:
•
Commands
(inpu ): o allow ex e nal componen s o
igge ope a ions o he componen .
•
E en s
(ou pu ): o send no i ica ions o o he
componen s.
4.2 Tasks
Tasks a e a e y impo an ea u e o TinyOS. They a e
code blocks ha a e execu ed only when he p ocesso is
a ailable:
•When he p ocesso is unning he ope a ions o a
ask
, i can no be s opped o execu e any o he
ask
.
Fo his eason, i ’s desi able no o include oo many
ope a ions in one
ask
in o de o sha e he p ocesso
by all he modules o he applica ion. All
asks
ha e
same execu ion p io i y.
•
Tasks
do no wo k as unc ions do; hey do no admi
pa ame e s.
4.3 E en and commands ypes
In TinyOS, i is qui e impo an o in oduce he di e en
ways o use e en s and commands (see [15], Sec ion 4.5).
Two kind o e en s and commands a e a ailable in
TinyOS:
•Synch onous ope a ions ha e he same execu ion
p io i y, and hey a e ela ed o
asks
.
•Asynch onous ope a ions ha e highe p io i y: hey
in e up he cu en execu ion (e en
asks
), and hey
a e ela ed o
in e up s
.

Ga ido-Cas ellano and Mu illo-Fuen es EURASIP Jou nal on Wi eless Communica ions and Ne wo king (2015) 2015:171 Page 6 o 14
In he ollowing sec ions, we explain how impo an all
hese ea u es a e, in o de o implemen he algo i hm.
5 Pla o m ea u es and limi a ions
5.1 Ha dwa e ea u es: MICAz
The selec ed ha dwa e o his wo k a e he MICAz
mo es. They ha e limi ed esou ces compa ed o o he
de ices such as Imo e2. Hence, a success ul implemen-
a ion on his pla o m ensu es he compa ibili y wi h
o he mo e powe ul de ices. They ha e he ollowing
ea u es:
•ATMEGA128L 8-bi mic o-con olle [16].
•Tempe a u e and humidi y senso s.
•ChipCon CC2420 IEEE 802.15.4 complian RF
anscei e . I wo ks wi h he s anda d IEEE 802.15.4
a 2.4 GHz. Maximum da a a e o 250 kbps [17]. I
has 128-by e ansmission and
ecep ion-independen FIFOs.
•In e nal lash 128 kB, RAM 4 kB, ex e nal lash 512 kB.
5.2 Limi a ions
5.2.1 Floa ing poin da a limi a ions
The m-DKLS algo i hm is based on ke nel leas squa es
lea ning, and i equi es o pe o m loa ing poin ope a-
ion capabili ies.
We need o de elop a linea algeb a lib a y o imple-
men he algo i hm. This lib a y is compound by se e al
unc ions: ma ix in e sion, ma ix p oduc , scala p od-
uc e c. Each unc ion execu es a ce ain ma ix ope a ion
and needs o ecei e he a gumen s o be used (ma ices).
The only way o pass ma ices o unc ions in NesC is
passing a gumen s by e e ence (poin e s).
MICAz mo es do no suppo loa ing poin ope a ions
by ha dwa e, and hey a e needed by he algo i hm, which
uses ma ices o loa ing poin da a. Floa ing poin a i-
ables a e, hen, managed by so wa e emula ion when he
applica ion is compiled, bu passing loa ing poin pa am-
e e s by e e ence o unc ions a e no suppo ed; we need
his ea u e o compu e ma ix ope a ions.
5.2.2 Recep ion bu e limi a ions
I is necessa y o de ine a ame s uc u e o send and
ecei e da a in he ne wo k. We ha e used he ame s uc-
u e in Fig. 2. No e ha no all he ields a e equi ed o an
implemen a ion bu a e use ul o moni o ing pu poses:
Fig. 2 F ame s uc u e used in WSN
•
ype
(1 by e): his ield is used o classi y he ame by
he s ep o he algo i hm which i belongs o.
•
ack
(1 bi ): Boolean ield o indica e i he message is
an ACK.
•
nodeid_s c
(1 by e): iden i ica ion o he sende node.
•
nodeid_des
(1 by e): iden i ica ion o he des ina ion
node.
•
pos
(2 by es): posi ion o he
nodeid_s c
node.
•
zk
(4 by es): i s alue depends on he s ep o he
algo i hm which he message belongs o. I he
message is an
ini ializa ion s ep
message, hen his
ield con ains he empe a u e measu ed by
nodeid_s c
. I he message is a
aining s ep
message,
hen i con ains he j, (xj)o m-DKLS.
•
p ed
(4 by es): his ield only akes alue when he
aining s ep
has been comple ed and a esul is sen .
The alue sen is co esponding o he p edic ion o
empe a u e in he posi ion indica ed by he ield
posp ed
.
•
posp ed
(2 by es): posi ion in which he la es
p edic ion has been done, and which empe a u e
alue is in he ield
p ed
.
•
dsn
(1 by e): ield used o acknowledgemen
con ol.
In he m-DKLS algo i hm, each node mus compu e
an es ima e o j, a e ecei ing a new da a om i s
neighbou s. Le us suppose he ollowing bu e -o e low
scena io:
•The numbe o neighbou s o a mo e is g ea e han
he numbe o ames ha he ecei ing bu e o he
CC2420 chip can hold.
•All he neighbou s o his mo e send a new da a a he
same ime while he mo e is compu ing he cu en
da a, o he incoming messages in he mo e a i e oo
quickly o p ocess hem in eal ime.
•The de aul mode o e en s and commands o
TinyOS is used o manage he e en s o all modules,
i.e. synch onous mode.
In such a si ua ion, we ha e he p oblem desc ibed
in Fig. 3. This igu e ep esen s he mo e by i s wo
main pa s, namely, he mic o-con olle and he CC2420
anscei e , bo h wi h a e ical compu a ion imeline.
We ha e a h ee-message leng h ecep ion bu e and a
neighbou hood o i e nodes. Due o he de aul syn-
ch onous e en mode, all he e en s ha e he same
p io i y o execu ion, including he e en ha signals
he ecep ion o a new packe in o he bu e . This
means ha he mic op ocesso does no a end ha
e en un il he cu en ask execu ion ends. In his sce-
na io, i is easy o lose incoming packe s due o bu e
o e low.
Ga ido-Cas ellano and Mu illo-Fuen es EURASIP Jou nal on Wi eless Communica ions and Ne wo king (2015) 2015:171 Page 7 o 14
Fig. 3 O e low in ecep ion bu e o anscei e . In his example, he
numbe o neighbou s is g ea e han he numbe o packe s ha he
anscei e bu e can hold. The las packe would be los i no
e ansmissions a e done
5.2.3 T ansmission bu e limi a ions
We could ha e simila p oblems when ansmi ing
da a o he ne wo k. The na i e lib a ies o handle he
ansmission o da a only use one RAM memo y a iable
o hold he packe un il i is accep ed by he anscei e
and sa ed in o i s ansmission bu e . I he p ocesso
eques s o ansmi se e al packe s ( o example, he
calcula ed zj o all he neighbou s) while he ha dwa e
ansmission bu e is ull, only he las o hem will
be ansmi ed due o a iable o e w i ing. The e o e, i
is needed an addi ional con ol by so wa e o ansmi
messages.
5.2.4 Acknowledgemen mechanism limi a ions
CC2420 chips p o ide an acknowledgemen mechanism
(a ha dwa e mechanism). This can p o ec he adio link
om undesi ed p oblems in he adio channel. Bu as
i is e e enced in [18] (and we ha e obse ed du ing
ou wo k), some addi ional issues a e de ec ed, like alse
acknowledgemen s.
A alse acknowledgemen occu s when he adio chip
ecei es a packe and i acknowledges i s ecep ion, bu
he mic o-con olle would ne e ecei e i . Fo his
eason, i is ad isable o use a so wa e acknowledgemen
mechanism a he applica ion le el wi h ce ain special
beha iou . This idea will be de ailed as pa o he p o-
posed solu ion (in Sec ions 6 and 7).
5.2.5 The p oblem o he ini ializa ion s ep wi h
communica ion e o s
The ini ializa ion s ep o he m-DKLS algo i hm is c i ical.
I a node s a s he aining s ep wi hou he sample (xi,yi)
o one o i s neighbou s, he algo i hm will ge qui e w ong
esul s, as i will use a 0 alue o he ini ial measu e o
ha neighbou . So he way by which he nodes acqui e he
knowledge o he neighbou hood is o high impo ance:
•We need a e y eliable ansmission and ecep ion o
da a i he ne wo k opology is ixed.
•We mus p o ec each node no o s a i s aining
s ep un il all he neighbou measu es ha e been
ecei ed.
When using a ixed opology, each mo e knows i s
neighbou hood because i is de ined in he applica ion
sou ce code. This means ha ma ix dimensions a e also
ixed, so all he ini ializa ion messages om he neigh-
bou s mus be ecei ed in o de o s a he aining
s ep.
6 P oposed solu ion
In he las sec ion, we de ec ed wo main p oblems when
implemen ing he algo i hm in he MICAz mo es:
•Packe loss.
•Sho ime be ween packe s p e en ing hei
p ocessing in eal ime, in scena ios like Fig. 3.
To a oid on hese p oblems, we ha e based he
implemen a ion only on unicas messages, al hough he
b oadcas ing da a would be desi able in e ms o com-
munica ion ene gy consump ion. We ha e de eloped an
addi ional laye o con ol he communica ions among
mo es and o ensu e ha all he unicas messages a e
ecei ed and p ocessed by he des ina ion mo es. Finally,
we ocus on minimizing he numbe o e ansmissions in
scena ios like shown in Fig. 3.
To sum up, he ollowing poin s mus be add essed:
•To sol e he loa ing poin da a limi a ions.
•Each mo e mus ha e ansmission and ecep ion
bu e s wi h enough capaci y o a end o all he
neighbou s.
•I a ecei ed packe in o he anscei e bu e canno
be a ended by he mic op ocesso , i should be
emo ed om he bu e o a oid o e low i possible.
•I a packe mus be sen and he anscei e bu e is
ull, we mus ensu e ha i will be sen when possible.
•The equi ed ime o p ocess a packe mus no a ec
o he communica ions o o he mo es.
•All he ecei ed packe s mus be p ocessed.
•We need o achie e ze o packe loss, ying o
minimize as possible he numbe o e ansmissions
in he ne wo k.
6.1 Floa ing poin compu a ion
To ace he limi a ions desc ibed in Sec ion 5.2.1, we
could scale he loa ing poin a iables and ea hem like
in ege a iables, bu o e low p oblems we e p esen .
Ga ido-Cas ellano and Mu illo-Fuen es EURASIP Jou nal on Wi eless Communica ions and Ne wo king (2015) 2015:171 Page 8 o 14
To deal wi h hese p oblems, we ha e adop ed a wo-
s ep solu ion wi h good esul s:
1. Ma ices a e sa ed in o he RAM-like scaled alues
(in ege s). Doing his we can pass hem by e e ence
o he ma ix unc ions.
2. Once in o each ma ix unc ion, all poin ed da a a e
sa ed in o local a iables (ma ices), con e ing hem
o loa a iables wi hou scale. Hence, in e nally,
each unc ion will do all he ope a ions wi h loa ing
poin a iables a oiding o e low p oblems. Finally,
he esul s will be scaled again and e u ned like
in ege alues.
The lib a y is se o allow he use o selec no only he
scale o he inpu da a bu also he scale o he esul .
6.2 Recep ion
Ou p oposed solu ion o ecep ion is shown in Fig. 4. Le
us ha e a comp ehensi e o e iew wi h a ew poin s:
1. Fi s , we mus modi y he na i e e en s and
commands o TinyOS ha manage he ecep ion o
packe s, con e ing hem om synch onous mode o
asynch onous mode. This will make ha whene e
exis packe s in o he bu e , no p ocessing
ope a ions will be done un il all o hem ha e been
sa ed in o he RAM. I some p ocessing ope a ion
is unning when a new packe ge s in o he
anscei e bu e , he p ocess will be s opped and
con inued once he packe has been ex ac ed
om he anscei e and sa ed in o he RAM
memo y.
Fig. 4 O e iew o he p oposed solu ion o ecep ion o da a.
Combining asynch onous ecep ion e en s wi h he ex ension o he
anscei e capabili ies allows he handling o bo h communica ion
and compu a ion ope a ions. Bo h he ci cula bu e and he da a
esul ing om he m-DKLS algo i hm a e sa ed in o he RAM memo y
2. A new ecep ion module mus be implemen ed. I
mus include a ci cula bu e in o he RAM memo y
o sa e all he incoming messages. Each ime a packe
is ecei ed om he anscei e (in asynch onous
mode), i will be sa ed in his bu e .
3. The new module mus handle a new
acknowledgemen mechanism a mic op ocesso
le el. A message is no acknowledged un il i is sa ed
in o he ci cula bu e . This mechanism will equi e
a p e-p ocessing ope a ion, as i will be de ailed in
New-acknowledgemen -mechanism
.
4. The ecep ion ope a ions mus be anspa en o he
use .
6.3 T ansmission
The solu ion o ansmission is simila , bu in his case,
i is no necessa y o con e he co esponding na i e
e en s and commands in o asynch onous mode:
1. We mus p o ide a ci cula bu e in o he
RAM memo y o sa e all he messages
ha mus be sen .
2. The new module o ansmission mus manage he
new acknowledgemen mechanism
(de ailed in
New-acknowledgemen -mechanism
).
I mus manage he ime o he mechanism.
3. The ansmission ope a ions mus be anspa en
o he use .
6.4 New acknowledgemen mechanism
We p opose o use he di ec -sequence numbe (DSN)
mechanism. The ansmi e mo e labels each packe
and wai s o a gi en ime o a esponse. I mus
con ol si ua ions like he scena io shown in Fig. 5, whe e
we ha e a e ansmission because p ocessing imes o
Fig. 5 Acknowledgemen mechanism de ails. An example o special
scena ios ha mus be con olled by he acknowledgemen
mechanism
Ga ido-Cas ellano and Mu illo-Fuen es EURASIP Jou nal on Wi eless Communica ions and Ne wo king (2015) 2015:171 Page 9 o 14
acknowledge a e la ge han ime s. The acknowledge-
men mechanism uses a ime o e alua e i a packe mus
be esen . We wan o minimize he numbe o e ans-
missions in he ne wo k. In ou solu ion, we a e p o-
cessing he incoming packe s sequen ially in he ci cula
bu e , so i we do no send he acknowledgemen un il i s
u n o p ocessing, e ansmissions will be done.
In he ecep ion o he acknowledgemen , we ha e a
simila p oblem. Suppose mo e m1sends a packe o m2
and s a s he ime . When i is ecei ed by m2,i will
be a ended in asynch onous mode o be sa ed in o i s
ecep ion ci cula bu e . Once i is sa ed, he m2sends
an acknowledgemen packe o m1. Once he acknowl-
edgemen packe is ecei ed by m1,i willa endi bu
a p e-p ocessing is needed: his kind o packe mus no
wai hei u n in o he ci cula bu e in o de o a oid
unnecessa y e ansmissions. So, all he incoming pack-
e s mus be p e-p ocessed: i hey a e ACK packe s, hey
will no be sa ed in o he ci cula bu e ; hey mus be
p ocessed immedia ely o clea he ime .
7 The implemen a ion
Finally, we de ail he componen s ha p o ide he new
unc ionali ies desc ibed in Sec ion 6. The solu ion is
based on h ee new modules (see Fig. 6):
•The main componen (mo eC).
•The new ansmi e componen (QueuedSende C).
•The new ecep ion componen (QueuedRecei e C).
We p opose an uppe laye o handle he wi eless com-
munica ions, apa om he module esponsible o he
execu ion o he m-DKLS algo i hm.
7.1 The main module mo eC
This module is connec ed o he na i e TinyOS
componen o ecei ing da a om he CC2420. I
means ha when he anscei e componen signals he
Fig. 6 Simple ep esen a ion o he solu ion. Rep esen a ion o he
ela ionships be ween he modules o he new communica ion laye
ecep ion o a new packe in o i s ha dwa e bu e , ha
e en is ecei ed in he module mo eC.P e iously,we
ha e se ha e en in asynch onous mode.
The mo eC module uses he in e ace QRecei e p o ided
by he new module QueuedRecei e C (de ailed la e ).
Th ough his in e ace, he module QueuedRecei e C ge s
new messages and p e-p ocess hem.
When a new message e en is ecei ed by mo eC,i ge s
he message om he anscei e and sends i o Queue-
dRecei e C h ough he QRecei e in e ace. E e y hing in
his chain is wo king in asynch onous mode so all hese
ope a ions will be done wi h he highes p io i y.
7.2 The new ecep ion componen QueuedRecei e C
This new componen implemen s ou ecep ion ci cula
bu e . I also p o ides he QRecei e in e ace and uses he
in e ace QSend p o ided by he new module Queued-
Sende C. When a new message is ecei ed om he
QRecei e in e ace, his componen mus p e-p ocess i :
1. I he message is an acknowledgemen o a p e iously
sen message by his mo e, his message mus be sen
o he
QueuedSende C
componen ( h ough i s
in e ace
QSend
) o ese he ime . This ope a ion
mus be immedia ely done, so he
QSend
in e ace
mus wo k in asynch onous mode oo.
2. I he message is no an acknowledgemen , i mus be
sa ed in o he ci cula bu e . Once sa ed, an
acknowledgemen message mus be sen immedia ely
o he sende o he message, so
QueuedRecei e C
pu s an ACK message in o he
QSend
in e ace.
In ou implemen a ion, he QueuedRecei e C is also
esponsible o he execu ion o he m-DKLS algo i hm,
bu i isexecu edinsynch onousmode h oughse -
e al asks. The ope a ions ela ed o m-DKLS algo i hm
could also be easily implemen ed in o a sepa a ed module
o ha e he communica ions independen om he algo-
i hm. In synch onous mode, his componen does he
ollowing ope a ions:
1. De ec ion o non-p ocessed messages by he
m-DKLS algo i hm in o he ci cula bu e .
2. I he e a e non-p ocessed messages, ex ac he
oldes one, dele e i om he ci cula bu e and
p ocess i in m-DKLS, ob aining a esul .
3. Send he esul o all he neighbou s h ough he
in e ace
QSend
o he componen
QueuedSende C
.
To a oid a con inuous check loop o con ol he s a us
o he ci cula bu e , we ha e used wo poin e s, one o
hem poin ing o he las ecei ed message and ano he
one poin ing o he las p ocessed message. Depending on
he ela i e posi ions be ween hem, we can easily know
i he e a e non-p ocessed messages. This in ol es a e y