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

Garrido-Castellano and Murillo-Fuentes EURASIP Journal on Wireless Communications and Networking (2015) 2015:171 DOI 10.1186/s13638-015-0382-6 RESEARCH Open Access On the implementation of distributed asynchronous non-linear kernel methods over wireless sensor networks Juan A. Garrido-Castellano*and Juan J. Murillo-Fuentes Abstract In this paper, we face the implementation of a non-linear kernel method for regression on a wireless sensor network (WSN) based on MICAz motes. The operating system used is TinyOS 2.1.1. The algorithm estimates the value of some magnitude from the measurements of the motes in a distributed approach where information and computations are performed asynchronously. This proposal includes a research on the potential problems encountered along with the developed solutions. Namely, matrix and floating computations, acknowledgement mechanisms and data loss. Keywords: Wireless sensor network; Distributed; Linear; Kernel method; Asynchronous; Algorithm; MICAz; Mote; TinyOS 1 Introduction Wireless sensor networks (WSNs) are very useful to monitor physical conditions in large or difficult access environments. Due to their wireless capabilities and their use of batteries, these networks have low costs of deployment. The nodes, usually known as motes, may include sensors of many kinds. Since they are also endowed with processing capabilities, they can perform a set of algorithms accordingly to the result of the measurements. These features open a wide spectrum of applications for WSNs [1]. They can be seen as intelligent and autonomous networks. A WSN is often understood as a network with a central node that runs the main operations such as network synchronization, data processing and storage, while the rest of nodes would just take measures to later send them to the central node. We may find several real implementations of centralized WSNs, e.g. in agriculture [2] or tracking [3]. However, it is well known that this topology has several problems in large networks due to its dependency on the central node. To name a few: •Unbalanced energy consumption: since computations and communications are concentrated in one and a few nodes, respectively. *Correspondence: [email protected] Department of Signal and Communications Theory, Universidad de Sevilla, Camino Descubrimientos, s/n - Isla Cartuja, Seville, Spain •Inefficient use of network bandwidth: large number of relays and nodes around central node with high rates associated, also wasting energy. •Unreliability: if the central node or nodes around it get down for any reason, the network is unavailable. •Poor response time: in large networks, we have large latencies associated to relays and management of huge amounts of data. These problems can be solved by using a distributed network model (see Fig. 1), where all nodes compute the solution for the locations in its neighbourhood by interchanging information locally. There are simple methods to make distributed estimations such as least squares regression. Nevertheless, attending to the application, more improved algorithms may be needed. For example, in structural health monitoring (SHM), some approaches in WSN need to manage non-linear cases in a distributed architecture [4]. And support vector machine-based non-linear distributed approaches can be applied to solve localization problems from RSSI parameters [5]. In this sense, some general frameworks for distributed kernel approaches have been presented in [6, 7] to solve non-linear regression in a distributed and real-time way. The design of distributed intelligent WSN involves both the design of distributed algorithms (like [4–8]) and their implementation. While the former is platform independent, the latter sets out © 2015 Garrido-Castellano and Murillo-Fuentes. This is an Open Access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly credited. Garrido-Castellano and Murillo-Fuentes EURASIP Journal on Wireless Communications and Networking (2015) 2015:171 Page 2 of 14 Fig. 1 Example of distributed wireless sensor network some interesting problems when translated to a WSN architecture. Some works on distributed implementations have already been proposed [9, 10]. However, to our knowledge, there is no implementation description of complex nonlinear kernel-based algorithms reported in the literature, like the ones in [6, 7]. Due to the important benefits of these algorithms, we have selected them as a target to study as a real implementation over a network composed by simple motes like MICAz, using the temperature field to easily illustrate the performance of the algorithm. These algorithms are quite demanding on both communication and processing capabilities. So, the main question to face is about its feasibility when implemented on an standard WSN with low resources motes. We positively answer this question by proposing a solution for this problem. The algorithm in [7] is based on the kernel least squares (KLS) algorithm. Its main advantage is that although it is computed in a distributed way, it converges to the solution of the centralized version. As discussed, the distributed KLS (DKLS) is highly demanding in terms of communication and computation capabilities. It requires matrix and kernel operations at the same time than multi-node communication management. Our solution is possible thanks to the versatile features of TinyOS, the operating system that will be used to program and compile the application into the motes. Besides the computational complexity of the algorithm, we have found severe problems with data packet loss, management of the transceiver buffers and unsupported hardware floating point data computation. The two first problems have been solved developing a new layer for communication handling that works as an extension of the related native libraries of TinyOS, in which not only data buffering features have been extended but also some changes into these native libraries have been done in order to improve the performance. On the other hand, regarding the floating point data management, TinyOS provides a software emulation with severe limitations when using with matrix data. In this way, a two-step solution has been adopted to allow these operations. This paper is organized as follows. In Section 2, we introduce the regression algorithm to be implemented, starting with the classic KLS regression and ending with the DKLS algorithm. Next, the modified DKLS (m-DKLS) algorithm, an evolution of DKLS, is explained in Section 3. Its implementation is our target in this paper. In Section 4, we provide an overview on the main concepts of this operating system, in order to better understand the limitations later found, which are detailed in Section 5. These limitations are the starting point of our work. The ideas to solve these problems are presented in Section 6. The next step is detailed in Section 7, where we develop the implementation in a MICAz network. In Section 8, the testing scenario is defined, and some obtained results are included. Finally, in Section 9, we summarize the work done, establishing in Section 9.1 some points of improvement and pending work to be done in this line of research. 2 Distributed kernel least squares 2.1 Classic kernel least squares regression As introduced in [11], the classic kernel least squares regression method is a well-known approach based on applying the kernel trick to the linear least squares algorithm. Given xi∈Rd, a set of training inputs, and yi∈R, the corresponding outputs, with i=1, ..., n,thealgorithm finds the hyperplane in the non-linearly transformed kernel space, f(x), that better fits a given set of training data, minimizing a least squares criteria. Then, for any new or test input, x, the method predicts the output as f(x).Ina WSN, the input xicould be the position coordinates while the output yicould be some environment measure, e.g. the temperature. In the computation of the prediction, f(x),anoptimization problem is solved where a loss function, L,between the truth yiand its prediction f(xi) L(yi,f(xi)) ≥0, (1) is averaged over the joint probability density function of the input and outputs, R(f)=Y×X L(y,f(x))p(y,x)dydx(2) where R(f)is the so-called risk function. Usually, the risk of making estimations cannot be computed because the joint distribution between the inputs and the outputs is unknown. However, we can compute Garrido-Castellano and Murillo-Fuentes EURASIP Journal on Wireless Communications and Networking (2015) 2015:171 Page 3 of 14 an approximation averaging the error function of the available data, as it is formulated by the empirical risk minimization (ERM) principle. The formulation in (2) yields Remp(f)= n  i=1 L(yi,f(xi)).(3) Using the least squares (LS) loss function, we get: Remp(f)= n  i=1 (yi−f(xi))2.(4) Since there is an infinite set of non-linear prediction functions, f(x), that fit the output data, we need to constrain the solution. This is achieved through Thikonov regularization. We get the classic formulation (5) of the KLS problem, fλ(·)=arg min f∈HK 1 n n  i=1 (f(xi)−yi)2+λf2 HK.(5) The optimization variable is f, which is a function constrained to be in HK,thereproducing kernel Hilbert space induced by the kernel k(·,·), denoting by · HKits norm. HKis a vector space of functions with a certain (and convenient) inner product. Note that in (5), we compute f(·) to minimize the mean square error with the first term, while with the last one we force the solution f(·)to have minimum norm to avoid overfitting. The inner-product structure implies that the solution to (5), denoted by fλ(·), satisfies: fλ(·)= n  i=1 cλ,ik(·,xi)(6) for some cλ∈Rr.Thisfactisknownastherepresenter theorem in [12]. In the case of least squares, cλis the solution to a system of nlinear equations, satisfying: cλ=(K+λI)−1y(7) where Kis the kernel matrix whose elements are defined by kij =k(xi,xj), and the kernel is pre-specified. 2.2 Distributed kernel least squares (DKLS) 2.2.1 Distributed definition of KLS The previous solution is a centralized algorithm and cannot be implemented in a distributed approach as it is. Let us suppose that we have a wireless sensor network of m nodes and we have n≤mmeasurements from them as training samples. Using the same notation as in Section 2.1, we could think of position as inputs xi∈R3, and temperature measures yias outputs. The training samples are ensembles in the set Sn. Let us suppose that not all nodes have access to all the samples, so the training samples accessible from node jis the subset Sj n.Letusalsodenote the set of the indices of the training samples in Snby Sn and the indices of training samples accessible by node jas Sj n. The first approximation to a distributed problem in this scenario is to compute mcentralized solutions, one for each node of the network, so the classical KLS problem could be written as: min fj∈HK n  i=1 (zi−yi)2+ m  j=1 λjfj2 HK(8) s.t.zi=fj(xi),∀i∈Sn,j=1, ..., m.(9) In this problem, the optimization variables are z∈Rn, i.e. {fj}m j=1, and rather than finding a function f(·),weare estimating a set of them. The constraints in (9) require that all nodes agree on the training data. This fact makes it to be equivalent to the classic KLS problem, getting the centralized solution, i.e. fj(·)=fλ(·)for j=1, ..., m(see Lemma 1 in Appendix of [6]). So, we can associate a centralized regression to a global agreement of nodes on the training samples. But we could think of an association of a distributed regression to a local agreement instead. Local agreement would involve that only a limited number of samples are shared between each two nodes. This last problem can be described as follows, min fj∈HK i∈Sj n (zi−yi)2+ m  j=1 λjfj2 HK(10) s.t.zi=fj(xi),∀i∈Sj n,j=1, ..., m.(11) In this formulation, the solution is feasible if and only if fj(xi)=zi=fk(xi)for (xi,yi)∈Sj n∩Sk nand for j,k= 1, ..., m; that is, if and only if every pair of node decision rules agree on samples they share. We get (z,f1, ..., fm)as the minimizer solution of (10), and fjis a function of only the training samples in Sj nas part of the joint minimizer. 2.2.2 Successive orthogonal projections algorithm A distributed approach of KLS problem has been shown in the previous subsection. Here, we face its solution, for which an alternate projections algorithm is proposed in [6], taking into account the similarities between both problems. In particular, the algorithm uses the nonrelaxed successive orthogonal projection (SOP) algorithm, next described. Let C1, ..., Cmbe closed convex subsets of the Hilbert space H, whose intersection C=∩ m i=1Ciis non-empty. Let PC(ˆ v)denote the orthogonal projection of ˆ v∈Honto C: PC(ˆ v)arg min v∈Cv−ˆ v(12) And the orthogonal projection of ˆ v∈Honto Ci: PCi(ˆ x)arg min v∈Ci v−ˆ v(13) Garrido-Castellano and Murillo-Fuentes EURASIP Journal on Wireless Communications and Networking (2015) 2015:171 Page 4 of 14 In [6, 13], it is defined the successive orthogonal projection (SOP) algorithm to compute PC(·)using PCi(·)m i=1as follows: v0:=ˆ vv t:=PC(tmod m)+1(vt−1)(14) In this definition (14), we denote by (tmodm)to the remainder of the division t/m. It establishes that the PC(·) can be computed projecting sequentially onto all the convex subsets Ci,usingforthePCi+1the result of the previous projection: first, it projects ˆ vonto C1, the result PC1is projected onto C2, and it iterates in this way successively a certain number of times. As pointed out in [6] (Theorem 2), it is demonstrated in [14] that for every v∈Cand every t≥1 vt−v≤ vt−1−v(15) and that lim n→∞ vn∈(∩m i=1Ci)(16) lim n→∞ vt−PC(ˆ v)= 0 (17) if Ciareaffineforalli∈{1, ..., m}.Hence,themore iterations we perform, the more accurate result we get. 2.2.3 Distributed KLS solution It is possible to redefine the problem in (10) in terms of the SOP algorithm [6], where the Hilbert space H=Rn×Hm K with norm (z,f1, ..., fm)2= z2 2+ m  i=1 λifi2 HK(18) is defined. With it, (10) can be interpreted as the orthogonal projection of the vector (y, 0, ..., 0)∈Honto the set C=∩ m j=1Cj⊂H,with Cj=(z,f1, ..., fm):fj(xi)=zi,∀i∈Sj n, z∈Rn,fjm j=1⊂HK⊂H(19) It is important to note that, for any v=(z,f1, ..., fm)∈H, the computation of PCj(v)=arg min v∈Cj v−v(20) is restricted to the locally accessible training examples by node j.ItmeansthatcomputingPCj(v)leaves zi unchanged for all i/∈Sj nand leaves fkunchanged for all k= j. The new function associated with the node jcan be computed using fj,{xi}i∈Sj n and the message variables {zi}i∈Sj n . This method defines the DKLS algorithm (using the notation of [7]), shown in Algorithm 1. Algorithm 1 DKLS algorithm Initialization Each node jbroadcasts their location xjto its neighbouring sensors. Each node jbroadcasts their measurement yjto their neighbouring sensors. Each node jinitializes zk=yk,∀k∈Sj n. Each node jinitializes fj,0 =0. Training for t=1,...,T do for j=1, ..., mdo fj,t=argmin f∈HK i∈Sj n (f(xi)−zi)2+λjf−fj,t−12 HK Node jbroadcasts fj,t(xk)∀k∈Sj n Every node sharing data ireplaces zkby fj,t(xk),∀k∈Si n end for end for It is interesting to note that the solution in (10) is an approximation to the centralized KLS. As discussed in [6], the neighbourhood of a mote limits the accuracy of its estimations, so local connectivity influences an estimator’s bias. In [6, 7], there are some studies that show through simulations that the error decays exponentially with the number of neighbours. 3 Non-linear asynchronous distributed algorithm The DKLS algorithm in [6] is beneficial in many ways, but in [7], the authors highlight several limitations: •After each node completes its training stage, it must generate a prediction for each neighbour (a different message computation for each one). •Due to that, the communication burden grows with the number of neighbours, and it means that the communication and computation load can be high. •Each node broadcasts one estimation for each neighbour node, and all of these messages should be received by all of its neighbours. Let us denote n0as the sender mote and n1,n2as neighbours of n0. Node n0would broadcast both fj,t(xn1)and fj,t(xn2)and both would be received by n1and n2.Ifn1and n2are not neighbours between them, they must discard the non-corresponding message, but the packet already have been received and read. This means waste of resources, in terms of processing and energy consumption. •It needs a synchronization of the network to do the training step, because we can only train one node at a Garrido-Castellano and Murillo-Fuentes EURASIP Journal on Wireless Communications and Networking (2015) 2015:171 Page 5 of 14 time. Otherwise, a node could receive several updates for zk, and then it would not know which one should keep. •Finally, if a sensor stops working (or some radio link fails) then the learning procedure stops, and the next node does not receive new predictions so it does not start its training stage. To overcome these limitations, in [7], the authors propose a simple modification in the algorithm: instead of transmitting fj,t(xk)for k ∈Sj n, the node would only broadcast fj,t(xj)(the prediction for the current node) to all its neighbours. The resulting algorithm is the modified DKLS algorithm (m-DKLS, see Algorithm 2). Algorithm 2 Modified DKLS algorithm (m-DKLS) Initialization Each node jbroadcasts their location xjto its neighbouring sensors. Each node jbroadcasts their measurement yjto their neighbouring sensors. Each node jinitializes zk=yk,∀k∈Sj n. Each node jinitializes fj,0 =0. Training for t=1,...,T do for j=1, ..., mdo fj,t=argmin f∈HK i∈Sj nf(xi)−zi2+λjf−fj,t−12 HK Node jbroadcasts fj,t(xj) Each neighbouring node replaces zjby fj,t(xj) end for end for The benefits of the algorithm can be summarized as follows: •It reduces the number of messages generated from Nj (the number of neighbours of node j)to1.Itonly needs to broadcast one message. •Since it broadcasts only one data, there is no need to synchronize the network. Each node decides when to transmit. •If a connection between two nodes stops working, it does not stop the training stage of the other nodes of the network. Although it exhibits a slightly worse convergence than the DKLS approach, again the error reduces exponentially with the number of neighbours. The number of retransmissions reduces significantly while the number of iterations increases to achieve a given error level [7]. In addition, the retransmissions can be performed asynchronously. At this point it is interesting to note that the m-DKLS algorithm can be easily extended to other kernel methods different to the KLS. 4 Brief introduction to TinyOS 4.1 NesC overview TinyOS is an open source operating system designed to work specifically with wireless sensor networks. It has an event-oriented architecture, and it has a set of libraries that provides data acquisition tools for the motes. These libraries are open source, so the code is available to be modified. It uses the NesC programming language, which is a dialect of the C language that adds some additional event-oriented features. Every NesC application is based on modular programming. An application is composed by one or more components. Each component can be seen as a functional part of the application. Each component has interfaces.These interfaces are used to connect this component to other components of the application. Interfaces use two kind of operations: • Commands (input): to allow external components to trigger operations to the component. • Events (output): to send notifications to other components. 4.2 Tasks Tasks are a very important feature of TinyOS. They are code blocks that are executed only when the processor is available: •When the processor is running the operations of a task , it can not be stopped to execute any other task . For this reason, it’s desirable not to include too many operations in one task in order to share the processor by all the modules of the application. All tasks have same execution priority. • Tasks do not work as functions do; they do not admit parameters. 4.3 Event and commands types In TinyOS, it is quite important to introduce the different ways to use events and commands (see [15], Section 4.5). Two kind of events and commands are available in TinyOS: •Synchronous operations have the same execution priority, and they are related to tasks . •Asynchronous operations have higher priority: they interrupt the current execution (even tasks ), and they are related to interrupts . Garrido-Castellano and Murillo-Fuentes EURASIP Journal on Wireless Communications and Networking (2015) 2015:171 Page 6 of 14 In the following sections, we explain how important all these features are, in order to implement the algorithm. 5 Platform features and limitations 5.1 Hardware features: MICAz The selected hardware for this work are the MICAz motes. They have limited resources compared to other devices such as Imote2. Hence, a successful implementation on this platform ensures the compatibility with other more powerful devices. They have the following features: •ATMEGA128L 8-bit micro-controller [16]. •Temperature and humidity sensors. •ChipCon CC2420 IEEE 802.15.4 compliant RF transceiver. It works with the standard IEEE 802.15.4 at 2.4 GHz. Maximum data rate of 250 kbps [17]. It has 128-byte transmission and reception-independent FIFOs. •Internal flash 128 kB, RAM 4 kB, external flash 512 kB. 5.2 Limitations 5.2.1 Floating point data limitations The m-DKLS algorithm is based on kernel least squares learning, and it requires to perform floating point operation capabilities. We need to develop a linear algebra library to implement the algorithm. This library is compound by several functions: matrix inversion, matrix product, scalar product etc. Each function executes a certain matrix operation and needs to receive the arguments to be used (matrices). The only way to pass matrices to functions in NesC is passing arguments by reference (pointers). MICAz motes do not support floating point operations by hardware, and they are needed by the algorithm, which uses matrices of floating point data. Floating point variables are, then, managed by software emulation when the application is compiled, but passing floating point parameters by reference to functions are not supported; we need this feature to compute matrix operations. 5.2.2 Reception buffer limitations It is necessary to define a frame structure to send and receive data in the network. We have used the frame structure in Fig. 2. Note that not all the fields are required for an implementation but are useful for monitoring purposes: Fig. 2 Frame structure used in WSN • type (1 byte): this field is used to classify the frame by the step of the algorithm which it belongs to. • ack (1 bit): Boolean field to indicate if the message is an ACK. • nodeid_src (1 byte): identification of the sender node. • nodeid_dest (1 byte): identification of the destination node. • pos (2 bytes): position of the nodeid_src node. • zk (4 bytes): its value depends on the step of the algorithm which the message belongs to. If the message is an initialization step message, then this field contains the temperature measured by nodeid_src . If the message is a training step message, then it contains the fj,t(xj)of m-DKLS. • pred (4 bytes): this field only takes value when the training step has been completed and a result is sent. The value sent is corresponding to the prediction of temperature in the position indicated by the field pospred . • pospred (2 bytes): position in which the latest prediction has been done, and which temperature value is in the field pred . • dsn (1 byte): field used for acknowledgement control. In the m-DKLS algorithm, each node must compute an estimate of fj,tafter receiving a new data from its neighbours. Let us suppose the following buffer-overflow scenario: •The number of neighbours of a mote is greater than the number of frames that the receiving buffer of the CC2420 chip can hold. •All the neighbours of this mote send a new data at the same time while the mote is computing the current data, or the incoming messages in the mote arrive too quickly to process them in real time. •The default mode of events and commands of TinyOS is used to manage the events of all modules, i.e. synchronous mode. In such a situation, we have the problem described in Fig. 3. This figure represents the mote by its two main parts, namely, the micro-controller and the CC2420 transceiver, both with a vertical computation timeline. We have a three-message length reception buffer and a neighbourhood of five nodes. Due to the default synchronous event mode, all the events have the same priority of execution, including the event that signals the reception of a new packet into the buffer. This means that the microprocessor does not attend that event until the current task execution ends. In this scenario, it is easy to lose incoming packets due to buffer overflow. Garrido-Castellano and Murillo-Fuentes EURASIP Journal on Wireless Communications and Networking (2015) 2015:171 Page 7 of 14 Fig. 3 Overflow in reception buffer of transceiver. In this example, the number of neighbours is greater than the number of packets that the transceiver buffer can hold. The last packet would be lost if no retransmissions are done 5.2.3 Transmission buffer limitations We could have similar problems when transmitting data to the network. The native libraries to handle the transmission of data only use one RAM memory variable to hold the packet until it is accepted by the transceiver and saved into its transmission buffer. If the processor requests to transmit several packets (for example, the calculated zjto all the neighbours) while the hardware transmission buffer is full, only the last of them will be transmitted due to variable overwriting. Therefore, it is needed an additional control by software to transmit messages. 5.2.4 Acknowledgement mechanism limitations CC2420 chips provide an acknowledgement mechanism (a hardware mechanism). This can protect the radio link from undesired problems in the radio channel. But as it is referenced in [18] (and we have observed during our work), some additional issues are detected, like false acknowledgements. A false acknowledgement occurs when the radio chip receives a packet and it acknowledges its reception, but the micro-controller would never receive it. For this reason, it is advisable to use a software acknowledgement mechanism at the application level with certain special behaviour. This idea will be detailed as part of the proposed solution (in Sections 6 and 7). 5.2.5 The problem of the initialization step with communication errors The initialization step of the m-DKLS algorithm is critical. If a node starts the training step without the sample (xi,yi) of one of its neighbours, the algorithm will get quite wrong results, as it will use a 0 value for the initial measure of that neighbour. So the way by which the nodes acquire the knowledge of the neighbourhood is of high importance: •We need a very reliable transmission and reception of data if the network topology is fixed. •We must protect each node not to start its training step until all the neighbour measures have been received. When using a fixed topology, each mote knows its neighbourhood because it is defined in the application source code. This means that matrix dimensions are also fixed, so all the initialization messages from the neighbours must be received in order to start the training step. 6 Proposed solution In the last section, we detected two main problems when implementing the algorithm in the MICAz motes: •Packet loss. •Short time between packets preventing their processing in real time, in scenarios like Fig. 3. To avoid on these problems, we have based the implementation only on unicast messages, although the broadcasting data would be desirable in terms of communication energy consumption. We have developed an additional layer to control the communications among motes and to ensure that all the unicast messages are received and processed by the destination motes. Finally, we focus on minimizing the number of retransmissions in scenarios like shown in Fig. 3. To sum up, the following points must be addressed: •To solve the floating point data limitations. •Each mote must have transmission and reception buffers with enough capacity to attend to all the neighbours. •If a received packet into the transceiver buffer cannot be attended by the microprocessor, it should be removed from the buffer to avoid overflow if possible. •If a packet must be sent and the transceiver buffer is full, we must ensure that it will be sent when possible. •The required time to process a packet must not affect to the communications to other motes. •All the received packets must be processed. •We need to achieve zero packet loss, trying to minimize as possible the number of retransmissions in the network. 6.1 Floating point computation To face the limitations described in Section 5.2.1, we could scale the floating point variables and treat them like integer variables, but overflow problems were present. Garrido-Castellano and Murillo-Fuentes EURASIP Journal on Wireless Communications and Networking (2015) 2015:171 Page 8 of 14 To deal with these problems, we have adopted a twostep solution with good results: 1. Matrices are saved into the RAM-like scaled values (integers). Doing this we can pass them by reference to the matrix functions. 2. Once into each matrix function, all pointed data are saved into local variables (matrices), converting them to float variables without scale. Hence, internally, each function will do all the operations with floating point variables avoiding overflow problems. Finally, the results will be scaled again and returned like integer values. The library is set to allow the user to select not only the scale of the input data but also the scale of the result. 6.2 Reception Our proposed solution for reception is shown in Fig. 4. Let us have a comprehensive overview with a few points: 1. First, we must modify the native events and commands of TinyOS that manage the reception of packets, converting them from synchronous mode to asynchronous mode. This will make that whenever exist packets into the buffer, no processing operations will be done until all of them have been saved into the RAM. If some processing operation is running when a new packet gets into the transceiver buffer, the process will be stopped and continued once the packet has been extracted from the transceiver and saved into the RAM memory. Fig. 4 Overview of the proposed solution for reception of data. Combining asynchronous reception events with the extension of the transceiver capabilities allows the handling of both communication and computation operations. Both the circular buffer and the data resulting from the m-DKLS algorithm are saved into the RAM memory 2. A new reception module must be implemented. It must include a circular buffer into the RAM memory to save all the incoming messages. Each time a packet is received from the transceiver (in asynchronous mode), it will be saved in this buffer. 3. The new module must handle a new acknowledgement mechanism at microprocessor level. A message is not acknowledged until it is saved into the circular buffer. This mechanism will require a pre-processing operation, as it will be detailed in New-acknowledgement-mechanism . 4. The reception operations must be transparent to the user. 6.3 Transmission The solution for transmission is similar, but in this case, it is not necessary to convert the corresponding native events and commands into asynchronous mode: 1. We must provide a circular buffer into the RAM memory to save all the messages that must be sent. 2. The new module for transmission must manage the new acknowledgement mechanism (detailed in New-acknowledgement-mechanism ). It must manage the timer of the mechanism. 3. The transmission operations must be transparent to the user. 6.4 New acknowledgement mechanism We propose to use the direct-sequence number (DSN) mechanism. The transmitter mote labels each packet and waits for a given time for a response. It must control situations like the scenario shown in Fig. 5, where we have a retransmission because processing times to Fig. 5 Acknowledgement mechanism details. An example of special scenarios that must be controlled by the acknowledgement mechanism Garrido-Castellano and Murillo-Fuentes EURASIP Journal on Wireless Communications and Networking (2015) 2015:171 Page 9 of 14 acknowledge are larger than timers. The acknowledgement mechanism uses a timer to evaluate if a packet must be resent. We want to minimize the number of retransmissions in the network. In our solution, we are processing the incoming packets sequentially in the circular buffer, so if we do not send the acknowledgement until its turn of processing, retransmissions will be done. In the reception of the acknowledgement, we have a similar problem. Suppose mote m1sends a packet to m2 and starts the timer. When it is received by m2,itwill be attended in asynchronous mode to be saved into its reception circular buffer. Once it is saved, the m2sends an acknowledgement packet to m1. Once the acknowledgement packet is received by m1,itwillattenditbut a pre-processing is needed: this kind of packet must not wait their turn into the circular buffer in order to avoid unnecessary retransmissions. So, all the incoming packets must be pre-processed: if they are ACK packets, they will not be saved into the circular buffer; they must be processed immediately to clear the timer. 7 The implementation Finally, we detail the components that provide the new functionalities described in Section 6. The solution is based on three new modules (see Fig. 6): •The main component (moteC). •The new transmitter component (QueuedSenderC). •The new reception component (QueuedReceiverC). We propose an upper layer to handle the wireless communications, apart from the module responsible for the execution of the m-DKLS algorithm. 7.1 The main module moteC This module is connected to the native TinyOS component of receiving data from the CC2420. It means that when the transceiver component signals the Fig. 6 Simple representation of the solution. Representation of the relationships between the modules of the new communication layer reception of a new packet into its hardware buffer, that event is received in the module moteC.Previously,we have set that event in asynchronous mode. The moteC module uses the interface QReceive provided by the new module QueuedReceiverC (detailed later). Through this interface, the module QueuedReceiverC gets new messages and pre-process them. When a new message event is received by moteC,itgets the message from the transceiver and sends it to QueuedReceiverC through the QReceive interface. Everything in this chain is working in asynchronous mode so all these operations will be done with the highest priority. 7.2 The new reception component QueuedReceiverC This new component implements our reception circular buffer. It also provides the QReceive interface and uses the interface QSend provided by the new module Queued- SenderC. When a new message is received from the QReceive interface, this component must pre-process it: 1. If the message is an acknowledgement of a previously sent message by this mote, this message must be sent to the QueuedSenderC component (through its interface QSend ) to reset the timer. This operation must be immediately done, so the QSend interface must work in asynchronous mode too. 2. If the message is not an acknowledgement, it must be saved into the circular buffer. Once saved, an acknowledgement message must be sent immediately to the sender of the message, so QueuedReceiverC puts an ACK message into the QSend interface. In our implementation, the QueuedReceiverC is also responsible for the execution of the m-DKLS algorithm, butitisexecutedinsynchronousmodethroughseveral tasks. The operations related to m-DKLS algorithm could also be easily implemented into a separated module to have the communications independent from the algorithm. In synchronous mode, this component does the following operations: 1. Detection of non-processed messages by the m-DKLS algorithm into the circular buffer. 2. If there are non-processed messages, extract the oldest one, delete it from the circular buffer and process it in m-DKLS, obtaining a result. 3. Send the result to all the neighbours through the interface QSend of the component QueuedSenderC . To avoid a continuous check loop to control the status of the circular buffer, we have used two pointers, one of them pointing to the last received message and another one pointing to the last processed message. Depending on the relative positions between them, we can easily know if there are non-processed messages. This involves a very