On the implementation of distributed asynchronous non-linear kernel methods over wireless sensor networks

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