FACTA UNIVERSITATIS Series: Electronics and Energetics Vol. 32, N o 4, December 2019, pp. 539-554 https://doi.org/10.2298/FUEE1904539P © 2019 by University of Niš, Serbia | Creative Commons License: CC BY-NC-ND ON THE NODE ORDERING OF PROGRESSIVE POLYNOMIAL APPROXIMATION FOR THE SENSOR LINEARIZATION  Aneta Prijić, Aleksandar Ilić, Zoran Prijić, Emilija Živanović, Branislav Randjelović University of Niš, Faculty of Electronic Engineering, Niš, Serbia Abstract. Many sensors exhibit nonlinear dependence between their input and output variables and specific techniques are often applied for the linearization of their transfer characteristics. Some of them include additional analog circuits, while the others are based on different numerical procedures. One commonly used software solution is Progressive Polynomial Approximation. This method for sensor transfer function linearization shows strong dependence on the order of selected nodes in the linearization vector. There are several modifications of this method which enhance its effectiveness but require extensive computational time. This paper proposes the methodology that shows improvement over Progressive Polynomial Approximation without additional increase of complexity. It concerns the order of linearization nodes in linearization vector. The optimal order of nodes is determined on the basis of sensor transfer function concavity. The proposed methodology is compared to the previously reported methods on a set of analytical functions. It is then implemented in the temperature measurement system using a set of thermistors with negative temperature coefficients. It is shown that its implementation in the low-cost microcontrollers integrated into the nodes of reconfigurable sensor networks is justified. Key words: Sensor Linearization, Progressive Polynomial Approximation, Reconfigurable Sensor Networks, NTC Thermistor 1. INTRODUCTION Transfer functions of sensors used in measurement systems usually do not have linear dependence between input and output variables. In addition, transfer functions often change with time. For these reasons, measurement systems based on the sensors exhibit various errors such as offset, gain, hysteresis, cross-sensitivity, drift, and non-linearity [1], [2]. In order to achieve reliable measurement, these errors should be compensated. One approach is to use additional analog circuits to condition sensors output signal [3], [4], [5]. However, analog compensation is not always appropriate for sensors integrated Received February 5, 2019; received in revised form July 1, 2019 Corresponding author: Aneta Prijić Faculty of Electronic Engineering, Aleksandra Medvedeva 14, 18000 Niš, Serbia (E-mail: aneta.prijic@elfak.ni.ac.rs)  540 A. PRIJIĆ, A. ILIĆ, Z. PRIJIĆ, E. ŽIVANOVIĆ, B. RANDJELOVIĆ into reconfigurable sensor networks [1], [6], [7]. A more flexible solution is to convert sensor output into the digital domain, where various numerical linearization methods may be applied in the form of compensation algorithms. These methods rely on a set of correction functions applied on a so-called linearization vector composed of linearization nodes. The effectiveness of the linearization method is evaluated on the basis of the number of nodes required to reduce non-linearity below a specific value, computation time, and implementation complexity. The simplest linearization method is based on a look-up table (LUT) which is also the fastest one. However, to obtain a high accuracy of the estimated input value, a high number of linearization nodes should be implemented in the LUT, making it memory consuming. To reduce memory requirement, a sparse LUT can be combined with an interpolation method [8]. A simple method is piece-wise linear interpolation which connects each two adjacent LUT values with an appropriate linear function. This type of interpolation can be also used for linearization of the whole transfer function. For N linearization nodes, sensors inverse transfer function will be represented by N−1 first order polynomials [9]. The main disadvantage of this method is a high number of nodes required for the linearization of highly nonlinear functions. This implies either a large memory requirement or a slow response time of the system [8]. More advanced methods are Lagrange, Newton [10] and spline [11] interpolations. However, Lagrange interpolation suffers from overfitting effect for polynomials of higher degree and it is generally not applicable to highly nonlinear sensors [10], [12]. The Newton method is more flexible and efficient when additional linearization nodes are introduced, but it is primarily applied for equidistant nodes [13]. On the other hand, spline interpolation is effective, but it comes at high implementation costs [14]. More effective and more commonly used methods are Progressive Polynomial Approximation (PPA) [15], [16] and linearization methods based on the Artificial Neural Networks (ANN) [17], [18]. The effectiveness of the PPA method, besides the linearization nodes number, depends on the node ordering in the linearization vector. Results obtained using the same compensation algorithm, but with the different order of nodes (permutation) [19], may vary between almost perfect in some cases, to even increased non-linearity in the other. In the case of the ANN method, effectiveness depends on the neural network topology and the time needed for its training. This paper proposes the methodology that improves the accuracy of the PPA while keeping its simplicity. Theoretical background, a summary of PPA, and an overview of its modifications are presented in Section 2. Section 3 contains an analysis of the PPA method effectiveness considering different permutations of the linearization vector for four different functions. Two of these functions are convex and two concave. This is done in order to elaborate on the idea that the optimal order of nodes in the linearization vector is dependent on the transfer function shape. In such a sense, an extensive computation time needed to accomplish the desired linearity by analysis of all permutations may be avoided. Experimental support of presented numerical results is given in Section 4, using negative temperature coefficient (NTC) thermistors as sensors. On the Node Ordering of Progressive Polynomial Approximation for the Sensor Linearization 541 2. LINEARIZATION METHODS 2.1. Underlying theory The transfer function of sensors is usually expressed as , where x is sensor input and y is sensor output [20]. The linearization method calculates the desired output value , using the workflow depicted in Fig. 1. Sensor output is first digitized, using an analog-to-digital converter (ADC), and then the linearization algorithm is applied. Obtained output value should vary linearly with the sensor input, i.e. , where k is the gain and n (usually 0) is the offset of the desired transfer function [1]. All operations are performed by a microcontroller, which is a part of the reconfigurable sensor node. Fig. 1 Workflow of a sensor linearization process There are two types of linearization methods, as illustrated in Fig. 2. The first involves an estimation of the sensor transfer function and subsequent numerical determination of sensor inverse transfer function which is used to obtain the estimated input value . The linearized output value is . Methods of the second type modify sensors output y using a correction function , so the linearized output is calculated as . Estimated input value, in this case, is calculated as . Fig. 2 Linearization of a sensor output for two distinct methods. The linearization node is a pair of two values: input x and corresponding output y. Values are determined experimentally by applying a known stimulus at the sensor input and measuring the value of its output. Input values are usually chosen equidistantly, starting at the minimal input that a sensor can detect, and ending at the full-scale. Nodes are then ordered to form the linearization vector. Linearization coefficients, implemented into the correction function , are determined using the linearization vector, and then stored in the memory of a microcontroller. On each measurement, these coefficients are used to calculate the linear output value of the sensor. 542 A. PRIJIĆ, A. ILIĆ, Z. PRIJIĆ, E. ŽIVANOVIĆ, B. RANDJELOVIĆ The effectiveness of linearization is evaluated using relative non-linearity [21]: , (1) where is full-scale input and is the maximum deviation of the real input from the ideal transfer characteristic. Due to the nature of the linearization algorithm, non- linearity will be equal to zero for any of the linearization nodes if a quantization error introduced by AD conversion is neglected. Therefore, additional measurements need to be performed to form a set of Ne evaluation nodes and calculate the maximum deviation as: (| |) for i=1,…Ne, (2) where is the applied input value and is the corresponding output value. 2.2. Progressive Polynomial Approximation (PPA) Calculation of the correction function in PPA is a successive process [15]. For each linearization node, new correction function, denoted as , is defined. Therefore, i-th function corrects the non-linearity around the i-th node, while keeping the corrections introduced by the previously defined functions. The final correction function is the one defined for the last node. In order to calculate correction function, linear output value ti at each node should be defined as: for i = 1, . . . , N. (3) These values are then used to calculate linearization coefficients for correction functions. The first correction function is defined as: (4) where is the linearization coefficient calculated for the first linearization node: . (5) Thus, adds the value to the sensor output, eliminating the offset (if present). The correction function at i-th node is defined as: ∏ for i = 2, . . . , N (6) and the linearization coefficient is calculated as: ∏ ( ) for i = 2, . . . , N. (7) These correction functions eliminate the gain error and successively minimize the transfer function non-linearity. Since the final correction function includes all the linearization nodes, it will output the desired value for any of these nodes while between them linearized output will deviate from the ideal one to some extent. On the Node Ordering of Progressive Polynomial Approximation for the Sensor Linearization 543 2.3. Modifications of the PPA method In PPA, the first two nodes in the linearization vector are chosen from the ends of a sensor range, thus eliminating the offset and gain errors [15]. Then, each new node is added halfway between the previous two. When the linearization vector ordered in that way is used, achieved results are not optimal, but large non-linearity is avoided. Note that nodes are not necessarily equidistant. The main advantage of PPA lies in its simplicity, so it does not require intensive time-consuming operations. This makes it particularly suitable for the implementation in reconfigurable sensor networks. Improved Progressive Polynomial Approximation (IMPPA) is the method based on permutations of nodes in the initial linearization vector. Each permutation is tested in order to find the best one [19]. To reduce the number of arithmetic operations, IMPPA does not test all possible permutations of the initial vector. Rather, it fixes the first node from the beginning of the sensor range as the first, the node from the end of the range as the second, and then permutes the remaining ones. The effectiveness of each permutation is determined by the non-linearity obtained at nodes which are inserted between the nodes of the linearization vector. A major drawback of this method is increased implementation costs in terms of the complexity and computation time. It should be noted that this method finds the optimal permutation of the given linearization vector for equidistant nodes. The method can be further improved if linearization vector with non-equidistant nodes is used. A probability density function is used to improve PPA, as presented in [22], [23]. This approach proposes an accumulation of linearization nodes in the part of a transfer function that will be used most commonly during a sensor lifetime. This can significantly improve measurement system accuracy in some cases, but the problem of the further ordering of the selected nodes still remains unsolved. A different linearization method inspired by PPA, called Modified Progressive Polynomial Approximation (MPPA), is addressed in [24]. Methodology for selection of the nodes which does not consider their order in the linearization vector is introduced. The larger set of equidistant nodes is formed first. The linearization vector is not predefined, but it is populated at each step by the node from the original set at which current linearized function deviates most from the linear one. Consequently, selected nodes in the linearization vector are not equidistant. 3. PROPOSED METHODOLOGY Proposed modification of the PPA method concerns the order of nodes in the linearization vector to obtain the desired transfer function linearity without increasing the algorithm complexity. Several analytic expressions commonly used to model sensors transfer functions are analyzed. In order to make a comparison of the results, transfer functions are normalized before the linearization methodology was applied. Both, input (argument) and output (function value) are normalized to range [0, 1]. If x m is sensor input and y m is sensor output, normalized input and output values are calculated using the following equations: , (8) , (9) 544 A. PRIJIĆ, A. ILIĆ, Z. PRIJIĆ, E. ŽIVANOVIĆ, B. RANDJELOVIĆ where and are minimum and full range input values, while and are the corresponding output values. The initial linearization vector TI is formed as a set of N equidistant nodes starting from the beginning of the sensors range. It is expressed as: [ ], (10) or, using shorthand notation: [ ]. Permutations of the linearization vector are denoted as , i = 1, 2, . . . , N − 1!. 3.1. Convex functions The PPA linearization methodology is applied to an exponential function: ⁄ (11) where p is parameter used to adjust its non-linearity (0