Elie Khoury
email: elie.akhoury@ua.edu.lb

Maguy Medlej
email: maguy.medlej@ua.edu.lb

Chady Abou
email: chady.aboujaoude@ua.edu.lb

Christophe Guyeux
email: christophe.guyeux@univ-fcomte.fr

Novel Order preserving encryption Scheme for Wireless Sensor Networks

Keywords: Order preserving encryption, security, wireless sensor networks

An Order-Preserving Encryption (OPE) scheme is a deterministic cipher scheme, whose encryption algorithm produces cipher texts that preserve the numerical ordering of the plain-texts. It is based on strictly increasing functions. It is a kind of homomorphic encryption where the homomorphic operation is order comparison. This means that comparing encrypted data provides the exact result than comparing the original data. It is attractive to be used in databases, especially in cloud ones as a method to enhance security, since it allows applications to perform order queries over encrypted data efficiently (without the need of decrypting the data). Wireless sensor network is another potential domain in which order preserving encryption can be adopted and used with high impact. It can be integrated with secure data aggregation protocols that use comparison operations to aggregate data (MAX, MIN, etc.) in a way that no decryption is being performed on the sensor nodes, which means directly less power consumption. In this paper, we will review many existing order-preserving encryption schemes with their related brief explanation, efficiency level, and security. Then, and based on the comparative table generated, we will propose a novel order-preserving encryption scheme that has a good efficiency level and less complexity, in order to be used in a wireless sensor network with an enhanced level of security.

I. INTRODUCTION

Wireless Sensor Networks (WSNs) are still one of the most challenging research areas in our present time. They consist of a system of sensor nodes that communicates using wireless communications distributed in either a safe or an unfriendly environment. The most challenging part of these nodes is their restriction in terms of resources, since they have low battery power, limited memory and computation capacity. WSNs are used in various fields like agriculture, medicine, the army, VANet, etc. [START_REF] Tannoury | Efficient and accurate monitoring of the depth information in a Wireless Multimedia Sensor Network based surveillance[END_REF]. Hence, the usage of the WSNs in these vast and critical fields, has obliged the security part to become one of the major aspects to be enhanced, alongside minimizing energy consumption.

As a solution for the energy consumption and to enhance the wireless sensor network vitality status, data aggregation is being adopted as an efficient technique to enhance the battery life of each node by minimizing the processing operation, and reducing the amount of data being sent between the nodes. Hence, sensor nodes send their values to the aggregators, then the aggregators collect the data received and send them to the base station. Since some wireless sensor network applications are used in military fields and are being dispersed in hostile and non-controllable zones, security of the WSNs has become a very essential part to be strengthened and enhanced. In addition, and since WSNs are being used in critical public sectors like VANet and medical fields, security is becoming a complete requirement since if any of the security triangle, confidentiality, integrity, or availability is compromised, the whole application will no longer be reliable.

Based on all the previous interpretations [START_REF] Bahi | Two Security Layers for Hierarchical Data Aggregation in Sensor Networks[END_REF], [START_REF] Guyeux | A Complete Security Framework for Wireless Sensor Networks: Theory and Practice[END_REF], securing the sensed data aggregated from the beginning to the end is essential by adopting an end-to-end encryption. In addition, using homomorphic encryption with different homomorphic operations (addition, multiplication, comparison, etc.) will enhance the sensor battery lifetime, since no decryption/encryption needed on the aggregated node is required to perform data aggregation operations based on the chosen data aggregation protocol.

Order-preserving encryption (OPE) is a kind of homomorphic encryption where the homomorphic operation is order comparison. This means that comparing encrypted data provides the exact result than comparing the original data. In summary, if x < y, then f (x) < f (y). Its rewards is that systems can perform order operations on cipher texts in the same way as on plaintexts [START_REF] Agrawal | Database management as a service: Challenges and opportunities[END_REF], [START_REF] Popa | An ideal-security protocol for orderpreserving encoding[END_REF], [START_REF] Boldyreva | Order-preserving encryption revisited: improved security analysis and alternative solutions[END_REF], [START_REF] Liu | Programmable order preserving secure index for encrypted database query[END_REF], [START_REF] Wang | Enabling secure and efficient ranked keyword search over outsourced cloud data[END_REF]. Because of the status of the wireless sensor nodes, in terms of low battery level, limited memory, and computation capacity, performing order operation on cipher text is very efficient. Indeed, it allows the node to use the encrypted data as it is (without decryption), and to perform order operations like equality and range comparison as well as the MAX, MIN, COUNT, GROUP BY, and ORDER BY computation.

In this paper, we will provide a brief summary regarding the most known order preserving encryption schemes used in several domains with their respective efficiency, security, and complexity levels. Then, based on the comparative table generated, we will introduce a novel order-preserving encryption scheme that can work in a wireless sensor network. This novel OPE scheme will be based on a low complexity level encryption algorithm (O (log(n))), a high efficiency level compared to other OPE schemes, and a high security level since the symmetric key generated will be periodically updated based on a random T period of time. For future work, this novel order preserving encryption will be tested and enhanced in every single part.

The remainder of this paper is organized as follows : In Section II, previous works on order preserving encryption in other fields and sectors are described. An optimized scheme that has a better performance, less complexity, and enhanced security is proposed in Section III. This latter can fit in wireless sensor networks. The simulation outcomes and results are shown and analyzed in Section IV. The conclusion and future work are finally summarized in Section V.

II. RELATED WORK

There has been a serious quantity of work on OPE schemes, see, e.g., [START_REF] Agrawal | Database management as a service: Challenges and opportunities[END_REF], [START_REF] Popa | An ideal-security protocol for orderpreserving encoding[END_REF], [START_REF] Boldyreva | Order-preserving encryption revisited: improved security analysis and alternative solutions[END_REF], [START_REF] Liu | New order preserving encryption model for outsourced databases in cloud environments[END_REF], [START_REF] Liu | Programmable order preserving secure index for encrypted database query[END_REF], [START_REF] Kaur | Review on Security Issues and Attacks in Wireless Sensor Networks[END_REF], [START_REF] Boldyreva | Order-preserving symmetric encryption[END_REF], [START_REF] Liu | Nonlinear order preserving index for encrypted database query in service cloud environnements[END_REF], [START_REF] Yum | Order preserving encryption for non-uniformly distributed plaintexts[END_REF], [START_REF] Kadhem | Multivaluedorder preserving encryption scheme: A novel scheme for encrypting integer value to many different values[END_REF], [START_REF] Kadhem | A secure and efficient order preserving encryption scheme for relational databases[END_REF], [START_REF] Lee | Chaotic order preserving encryption for efficient and secure queries on databases[END_REF], [START_REF] Agrawal | Order preserving encryption for numeric data[END_REF], [START_REF] Kolesnikov | On the limits of privacy provided by order-preserving encryption[END_REF], [START_REF] Acharya | Secure Comparison of Encrypted Data in Wireless Sensor Networks[END_REF], [START_REF] Minkyu | Comment on the Security of an Order-Preserving Encryption Scheme Using Pseudo-Random Function[END_REF], [START_REF] Liua | New order preserving encryption model for outsourced databases in cloud environments[END_REF], [START_REF] Kanherkar | A Simplified Approach on Security Analysis Using Probabilistic Order Preserving Encryption Based on Cloud Data Search[END_REF], [START_REF] Peng | hOPE: improved order preserving encryption with the power to homomorphic operations of ciphertexts[END_REF]. They either provide a good efficiency but low security or the opposite, as will be proven later. In this area, we present a detailed overview of different typical known types of OPE schemes with their related advantage/disadvantage, alongside with the parameters chosen to evaluate the OPE Scheme, i.e., efficiency level, security level, complexity level, and the order of comparison.

The premier provably-secure OPE scheme was created by Boldyreva [START_REF] Boldyreva | Order-preserving symmetric encryption[END_REF]. It provided the first formal treatment of security. Like any other OPE, Boldyreva's order-preserving encryption algorithm forms a monotonically increasing curve. The BCLO (Boldyreva, Chenette, Lee, and O'Neill) scheme was introduced based on a sampling algorithm for the hypergeometric probability distribution. This Hypergeometric Distribution (HG) is a discrete probability distribution that represents the number of successes in a series of draws from a finite population without replacement. In order to meet the security notion of an OPE scheme looks "as-random-as possible", the encryption method of the BCLO scheme uses 2 algorithms (LazySample and LazySampleInv) that examine a random order-preserving function from domain D to range R and its inverse, respectively (plaintext-space D and ciphertext-space R). In other words, any order-preserving function g(.) from domain D= {1. . . M} to range R= {1. . . N} can be particularly defined by a combination of M out of N ordered items.

With this approach, encryption function is based on hypergeometric distribution maps plaintexts from the set [1, 2, ..., M] to the set [1, 2, ..., N], where N > M . The cipher texts generated from this scheme is in order and associated correspondingly with plaintext numbers. This scheme has a low-efficiency level, but with a medium security standing that makes it different from other low-security levels. To reduce the computational cost of the BCLO scheme of [START_REF] Boldyreva | Order-preserving symmetric encryption[END_REF], Yum used the probabilistic middle gap instead of the Euclidean middle one [START_REF] Yum | Order preserving encryption for non-uniformly distributed plaintexts[END_REF]. Simulations show that the proposed method is effective for various distributions, especially for distributions with small variance. This scheme has a low to medium efficiency level with a same medium security standing of the Boldyreva, 2009 [START_REF] Boldyreva | Order-preserving symmetric encryption[END_REF].

In 2011, Boldyreva [START_REF] Boldyreva | Order-preserving encryption revisited: improved security analysis and alternative solutions[END_REF] provided a promising extension, the modular order-preserving encryption (MOPE), that enhances the security level of the basic OPE by inserting a secret modular offset to each data value before encrypting it. MOPE improves the security of OPE in a sense, as it does not leak any information about plaintext location. But later on, it was proven [START_REF] Boldyreva | Order-preserving encryption revisited: improved security analysis and alternative solutions[END_REF] that OPE schemes cannot satisfy standard notions of security, such as indistinguishability against chosen-plaintext attack (IND-CPA), since they lack the ordering information of the plaintexts. If an adversary knows plaintexts p1, p2 and corresponding ciphertexts c1, c2, and c, such that c1<c<c2, it is obvious that the plaintext for c lies in the interval (p1, p2). In addition, the adversary can always discover the decryption function in some approximation, for instance, using linear interpolation. In [START_REF] Mavroforakis | Modular Order-Preserving Encryption[END_REF], they introduced a new appropriate security model for MOPE that has a significant security improvement over the basic OPE. The complexity of the algorithm used in [START_REF] Boldyreva | Order-preserving encryption revisited: improved security analysis and alternative solutions[END_REF], [START_REF] Mavroforakis | Modular Order-Preserving Encryption[END_REF] is O (n), but has low efficiency level and medium security (it leaks some data).

Liu and Wang [START_REF] Liu | Programmable order preserving secure index for encrypted database query[END_REF] presented a simple linear scheme, easy to use, that is based on a linear expression. In addition to the linear expression, a random noise is added to the initial plaintext to enhance the security level. In details, the linear order preserving encryption scheme proposed in [START_REF] Li | Security Analysis on One-to-Many Order Preserving Encryption Based Cloud data Search[END_REF] is built over the expressions of the form y = a × x + b + noise, where x is a plaintext, a and b are secret coefficients, y is the ciphertext, and noise is a randomly selected value. To guarantee the order preserving property, it is required that a > 0 in the linear expression and that noise is randomly selected from some particular range. To determine the range of noises, the sensitivity of input values is needed. The sensitivity characterizes the minimal difference between two plaintexts, i.e., if the plaintexts belongs to Z, then sensitivity is equal to 1. Another example, if the sensor collects the weather degree, the sensed values can be 35.5, 35.6, 35.7, etc. So the minimal difference between one degree and another one is 0.1, which leads to a sensitivity of 0.1. This OPE scheme is information-theoretically secure, since attackers cannot get enough information to solve the linear equations over the input values. But, as discovered later on, the linear OPE scheme might be vulnerable when there are too many duplicates in plaintexts. For each plaintext value v, we generate an encrypted value v' by using the linear function Enc(x) = ax + b + noise. The advantage of this solution is the efficiency level, but it has low security.

Until now, the only ideal security OPE scheme is the mutable order-preserving encoding (mOPE) implemented by Popa [START_REF] Popa | An ideal-security protocol for orderpreserving encoding[END_REF], where the ciphertexts reveal nothing except the order of the plaintext values. The mOPE run by building a balanced search tree that includes all of the plaintext values encrypted by the application in the database side. The interactive encryption protocol, with a small number of interactions, changes over time the ciphertexts for a small number of plaintext values. These operations in database side can be executed by User Define Functions (UDFs).

In summary, it requires the database server to retain additional information and perform comparison or range query by UDFs. However, order operations will no longer be executed directly on the ciphertext. It will affect the efficiency and make this scheme unsuitable for some cases, i.e., for wireless sensors networks. More specifically, experiments show that it has a poor efficiency, extra storage, no direct comparison on ciphertexts, and its execution time of encryption is very high. On the other Hand, in terms of security, the Popa's scheme achieves ideal-security. Let us finally note that algorithm complexity is of the magnitude of O (n log n).

In order to address the vulnerability of the previous linear

a > 0, (1)
noise

∈ [0, a * f (v + sens) * (v + sens) -a * (f (v) * v)], (2)
f (x) > 0 for x = 0, (3)
f (x 1 ) ≥ f (x 2 ) for x 1 > x 2 > 0. (4)
The advantage of this method is that it is more secure than the previous one. The disadvantage is that it is less efficient since the encryption algorithm is more complex.

A new simple OPE model has been proposed by Liu in 2014 [START_REF] Liu | New order preserving encryption model for outsourced databases in cloud environments[END_REF], that uses message space expansion and nonlinear space split for hiding the frequency and the data distribution. This research was based on Liu's 2013 scheme, and works as follows. Firstly, the original message space is randomly split into successive intervals with different lengths. Secondly, an extended ciphertext space is selected and split into the same number of intervals. Finally, some nonlinear mapping functions are used to map the original element into another one in the extended message space (Enc(x) = ax + b + noise). This scheme is constructed by some linear mathematical functions used by Liu and Wand, 2013. In terms of security, this scheme can achieve to face ciphertext-only attacks. Furthermore, this scheme uses message space expansion and nonlinear space split to cover data distribution and frequency, and thus can resist to statistical attacks.

Finally, in 2017, J. Dyer [START_REF] Dyer | Order-Preserving Encryption using approximate integer common divisors[END_REF] proposed a new simple randomized order-preserving encryption scheme based on the general approximate common divisor problem (GACDP). It is based on computational hardness primitive. The results show that this scheme is very efficient compared to other OPE schemes, since there are O(1) arithmetic operations for both encryption and decryption. Note finally that the security level of this scheme is classified as medium.

Table I displays the comparison between some typical OPE schemes. The compared parameters are the efficiency level, the security, the complexity, and the order of comparison. About the security, only Popa [START_REF] Popa | An ideal-security protocol for orderpreserving encoding[END_REF] provides a high level of security compared to others OPE schemes, since the ciphertexts reveal nothing except for the order of the plaintext values (idealsecurity). About the efficiency, we can see that security and efficiency are always contradictory: the most secure is the less efficient. Dyer [START_REF] Dyer | Order-Preserving Encryption using approximate integer common divisors[END_REF] and Liu [START_REF] Liu | Programmable order preserving secure index for encrypted database query[END_REF] using an O(1) and O(n) arithmetic operations respectively for encryption and decryption have the best efficiency compared to others.

In summary, and since we are targeting the integration of OPEs in wireless sensor networks, our approach is to use an efficient OPE scheme in order to be applicable in the WSN (less complexity = less resources usage = more efficient). In addition, the more the OPE scheme is secure the better we are, for that purpose our tactic will be to enhance the security level for the selected OPE.

III. PROPOSAL AND IMPLEMENTATION ENVIRONMENT

A. Order Preserving Encryption standard Scheme

An order-preserving encryption (OPE) scheme with plaintext-space [M] and ciphertext space [N] is a tuple of algorithms OP E = (Kgen, Enc, Dec) where:

• The randomized key-generation algorithm Kgen outputs a key, K(a, b).

• The deterministic encryption algorithm Enc, inputs a key K, a plaintext m and outputs the ciphertext c.

• The deterministic decryption algorithm Dec, inputs a key K, a ciphertext c and outputs the plaintext m.

In addition to the usual requirement that Dec(Enc(K, m)) = m, for every plain-text m and key K, we require that m1 < m2 if and only if Enc(K, m1) < Enc(K, m2) for all plaintexts m1, m2 and every key K. Notations are summarized below. The system model shown in Figure 1 works using three stages:

• Stage1: Encryption phase Sensors encrypt the data detected by using OPE with a master secret key shared by all the wireless nodes in the network. The encrypted data set is sent to the aggregator.

• Stage2: Aggregation -Verification The aggregator calculates/analyses/compares the aggregates of the encrypted data using order operations like equality/range comparison as well as the MAX, MIN, COUNT, GROUP BY, and ORDER BY. It then sends the results to the Base Station: no need for decryption.

• Stage3: Decryption phase The base station decrypts the encrypted data set and calculates the plaintexts of the aggregates.

C. Proposing our novel OPE Scheme.

Based on Table I, OPE encryption based on both the linear expression y = ax+b and the logarithm expression c = a * log(m + b) have the best efficiency, since their complexity levels are low: linear expression O(n) and logarithm expression O(log(n)). They are very suitable to be used in a wireless sensor network, especially for the O(log(n)) complexity, which is obviously better than the O(n) one.

So, as a first step, we will use the logarithm expression, y = a log(x+b) as the base of our OPE system, with a, b ∈ Z + and x+b > 0. But this cryptosystem, like many others, will be vulnerable to the chosen-plaintext attack. And, even if we add to this expression some random noise, this cryptosystem will be less vulnerable. But, it will still be defenseless against the chosen-plaintext attack, and the key (K) can be revealed. For this reason, updating a and b on a random period can minimize the era time of the key k(a,b), so any chosen-plaintext attack cannot cause any serious damage to this OPE scheme, since the key will be generated on a random period. In a nutshell, our proposed OPE is very efficient and is mainly more secure compared to other OPE schemes.

To implement this novel OPE scheme, our algorithm will be divided into 3 parts, which can be written as follows: OPE = (KeyGen, OPEEnc, OPEDec)

• Step1:
The target of this algorithm is to set up the exact parameters to generate the encryption key, in addition to defining the period of time it takes p to regenerate a new key.

• Step3

The target of this algorithm is to decrypt the encrypted data y and outputs its OPE plaintext.

Algorithm 3 OPE Decryption 1: Procedure OPEDec (c,K) // inverse of the procedure OPEEnc 2: m = (a log(c + b)) -1 // the exponential function is the inverse function of a logarithm function ⇒ it will be complex ⇒ more battery usage ⇒ it will be performed on the base station only since we are considering working in an end-to-end encryption 3: Return m 4: End Procedure As a programming language, Matlab was used to perform the simulation. The algorithms were tested on a virtual machine that has the following specifications: i3-7100 CPU, 8GB DDR4, and 1TB HDD 7200 RPM. The VM has Windows 8.1 OS running on it. This VM will be matched to a next generation wireless sensor node.

D. Strategy Selection

Based on the comparative Table I, we selected Dyer [START_REF] Dyer | Order-Preserving Encryption using approximate integer common divisors[END_REF] OPE scheme that is based on the general approximate common divisor problem (GACDP) as the baseline of our simulation. Our selection was based on the efficiency level of this scheme compared to other OPE schemes, since there are O(1) arithmetic operations for encryption and decryption. In addition of its efficiency, this scheme has a good security level, since it produces larger cipher texts, ∼ 3.67 times the number of bits of the plaintext, and has minimal impact on the running time. Based on our experiment results, we discovered that the efficiency of this scheme makes it fit for usage in wireless sensor networks.

The security level of our OPE scheme is definitely better, because the symmetric encryption key will be updated on a random period, so it can minimize the era time of the key k(a,b). We will now test the efficiency level of our code, and prove that our Olog(n) code is also faster.

IV. EXPERIMENTAL RESULTS

To evaluate our novel OPE scheme in practice, we performed an experiment by encrypting 100 times both OPE schemes; the first one (in red) represents the general approximate common divisor problem (GACDP) and the second one (in blue) is our novel OPE scheme. The simulation is based on the algorithm and the strategy already mentioned previously in the article. Note that both algorithms will be executed separately. The parameters needed for the key generation (a, b and p) will be selected manually or randomly. As a first observation, and based on several simulations and testing performed on the key generation, we noticed that the resolution time of our novel OPE scheme is faster than the (GACDP) scheme for the period between 0 < T < 60 as visualized in the Figure 2 and Figure 3. As a second observation, we can detect that after the period of 60, T > 60, the resolution time of our novel OPE will start to be similar than the OPE of the approximate common divisor problem (GACDP), (see Figure 2 and Figure 3). As an outcome, our novel OPE resolution time code is faster than the (GACDP) scheme when the period is less than 60, and after 60 it starts to decelerate but in the other hand more secure for the reason that the key is being changed and generated on a random basis, strengthening the security level of our scheme and harden the key detection by any attacker and the bigger the period is, the greater the security level is.

V. CONCLUSION AND FUTURE WORK

In this article, we provided a sharp description of various order preserving encryption schemes. In addition, various design issues such as data confidentiality, data integrity, efficiency level, and security of these OPE schemes have also been discussed and evaluated. And, based on the data generated in the comparative table of this paper, we have proposed a novel secure order preserving encryption scheme that can suit a wireless sensor network, in terms of efficiency, complexity, and security. The implemented OPE scheme is based on a logarithm encryption function which makes the scheme very efficient and less complex compared to other OPE schemes. In addition, and to enhance the security level of this OPE scheme, the symmetric encryption key is updated based on a T period of time, so it can minimize the era of the key k(a,b). In consequence, it is very hard for any attacker to discover the key. And even if the key is sorted out, it will be useless since it will have expired based on period already specified. After performing some experiments, we have proven that our new OPE scheme is faster, more efficient, and most of all more secure. In addition, and after fine tuning the results, we have found that T between 0 and 60 is the best range. Beyond 60, our scheme starts losing its efficiency compared to the other OPE Scheme.

As a future work, the efficiency level of the adopted OPE cryptosystem with improvement of the bundle of algorithms used (keyGen, OPEEnc, OPEDec) can be optimized. In addition, a smart key generation updater could be based on a machine learning algorithm that can detect the rate of live attacks. As a consequence, the rate of the key generation will be optimized in a secure and efficient way.

m

  ⇒ plain-text c ⇒ cipher-text K ⇒ the Encryption key, belonging into k = {(a, b), a, b ∈ Z + } Enc ⇒ Encryption algorithm that contains the procedure OPEEnc Dec ⇒ Decryption algorithm that contains the function OPEDec B. Secure Data aggregation in Wireless Sensor Networks (endto-end encryption) using OPE scheme.

Fig. 1 .

 1 Fig. 1. Secure Data aggregation in Wireless Sensor Network (end to end encryption) using Order-Preserving Encryption scheme

Algorithm 1 Key Generation 1 :

 1 Procedure KeyGen(a,b) 2: Input (a,b) // {(a, b), a, b ∈ Z + }, random input 3: Return K 4: End Procedure 5: input p // p=period, the period of time before a new key generation• Step2The target of this algorithm is to encrypt the plaintext data m and outputs its OPE cipher text. To encrypt m, we need to have the key generated k as an input. Algorithm 2 OPE Encryption 1: Procedure OPEEnc (m,k) 2: m ∈ Z + 3: Input (m,K) 4: c = a*log(m+b) // This cryptosystem is highly efficient, since the encryption function is logarithmic (O(log(n)) 5: Return c 6: Threshold T = T+1 7: If T == p then KeyGen(a,b) // a,b should be random new numbers, p = period already defined 8: End Procedure

Fig. 2 .Fig. 3 .

 23 Fig. 2. Comparison of time resolution -Simulation 1

Figure 2 and

 2 schemes; the first one (in red) represents the general approximate common divisor problem (GACDP) and the second one (in blue) is our novel OPE scheme. The simulation is based on the algorithm and the strategy already mentioned previously in the article. Note that both algorithms will be executed separately. The parameters needed for the key generation (a, b and p) will be selected manually or randomly. Figure2and Figure3represents two simulations samples that have different random key generation parameters(a,b and p).

TABLE I .

 I COMPARISON BETWEEN TYPICAL OPE SCHEMES OPE schemes when there are too many duplicates in plaintexts, Liu and Wang[START_REF] Liu | Nonlinear order preserving index for encrypted database query in service cloud environnements[END_REF] presented a nonlinear OPE that can be calculated from the expression y = a × f (x) × v + b + noise, where a, f (x), and b are kept secret, with the following requirements satisfied:

	Scheme	Efficiency	Security	Complexity	Order of comparison
	Agrawal, 2004 [17]	Medium	Low	O(n)	Direct
	Boldyreva, 2009 [7]	Low	Medium	O(n)	Direct
	Agrawal, 2009 [1]	Medium	Medium	O(n)	Direct
	Boldyreva, 2011 [3]	Low	Medium	O(n)	Direct
	Liu, 2012 [5]	High	Low	O(n)	Direct
	Popa, 2013 [2]	Low	High	O(n log n)	UDFs
	Liu, 2013 [8]	Medium	Medium	O(n 2 )	Direct
	Dyer, 2017 [13]	High	Medium	O(1)	Direct


Anthony Tannoury

Rony Darazi

Abdallah Makhoul

Christophe Guyeux

Wireless multimedia sensor network deployment for disparity map calculation

published or not. The documents may come

Wireless Multimedia Sensor Network deployment for disparity map calculation Anthony Tannoury a,b , Rony Darazi a , Abdallah Makhoul b , and Christophe Guyeux b a TICKET Lab, Antonine University, Hadat-Baabda, Lebanon. b Univ. Bourgogne Franche-Comté, FEMTO-ST Institute/CNRS, Belfort, France Emails: anthony.tannoury@ua.edu.lb, rony.darazi@ua.edu.lb, abdallah.makhoul@univ-fcomte.fr, christophe.guyeux@univ-fcomte.fr Abstract-The use of Wireless Multimedia Sensor Networks (WMSNs) has been increased in the recent decade in several fields. One of the main advantages of WMSNs is activity monitoring, where 2D images and videos have been used traditionally for surveillance and detection so far. However, a lot of interest is paid to depth information that is not normally available while using 2D images. In our previous work, the use of disparity information in WMSNs has been studied. In this paper, our contribution consists of evaluating the Sensor deployment for efficient disparity calculation for indoor and outdoor purposes. The simulation results show that while considering images from adjacent sensors, the disparity map is successfully calculated. The quality of the disparity is evaluated using structural similarity metric between one reference image captured by one sensor and the calculated disparity map.

Index Terms-Wireless Multimedia Sensor Networks, Disparity Map, Stereo Vision, 3D Scene Reconstruction, Surveillance, Event Detection.

I. INTRODUCTION

Scene surveillance is a promising research subject in Internet of Things (IoTs). Traditional Wireless Sensor Networks (WSNs) can sense scalar data like humidity, speed, etc [START_REF] Brindha | The data aggregation approach to enhance the lifetime of wireless sensor network[END_REF]. The added value(s) in WMSNs is the multimedia data that can be sensed and delivered such as image, video, and audio. The availability of small-scale and low-powers Complementary Metal Oxide Semiconductor (CMOS) camera sensors helps in developing new WMSNs applications in multiple fields like military, e-health, etc [START_REF] Ukani | Routing Protocols for Wireless Multimedia Sensor Networks: Challenges and Research Issues[END_REF]. Requirements in terms of quality of service, energy consumption and computations time differ from one application to another. In WMSNs surveillance systems, the main challenge is to develop an efficient monitoring network that covers the maximum range of target objects with the lowest computation time and energy consumption.

Calculating the depth value in 3D space is an essential indicator before detecting a change in the monitored scene and then triggering an alert or 3D reconstructing the scene. Actual stereo vision systems and 3D reconstruction solutions lies on professional and complex hardware like laser scanners or advanced cameras [START_REF] Ripolles | Smart video sensors for 3d scene reconstruction of large infrastructures[END_REF]. In [START_REF] Yun | Recognition of transparent objects using 3d depth camera[END_REF], even transparent objects could be recognized using Intel Realsense R200 long range stereoscopic depth sensor. Guizi et al. [START_REF] Da Silva Guizi | Real-time people detection and tracking using 3d depth estimation[END_REF] proposed a 3D algorithm, via tridimensional depth estimation, for real time people detection and tracking in indoor environments. However, video sensors in WMSNs are limited in power resources because they are Fig. 1. Proposed model powered by batteries. Our main objective is to calculate the 3D depth while saving power and then delivering valuable multimedia data to the sink(s), sufficient for event/changes detection or 3D Scene Reconstruction [START_REF] Bahi | Low cost monitoring and intruders detection using wireless video sensor networks[END_REF].

For the above-mentioned reasons, we introduced the disparity map computation in the context of WMSNs based surveillance [START_REF] Tannoury | Efficient and accurate monitoring of the depth information in a wireless multimedia sensor network based surveillance[END_REF], [START_REF] Bahi | Secure scheduling of wireless video sensor nodes for surveillance applications[END_REF]. The depth information is saved in the disparity maps calculated on each couple of sensors, marked as left and right cameras. The Fig. 1 outlines our system. As can be seen, the double-view images are processed locally via the couple of low cost sensor nodes. This will reduce transmission rate, which is the direct and important cause for altering the network lifetime. Our system will not deliver high size images but only gray-scale disparity maps, on demand or triggered by a change or intrusion in the monitored scene/object. This reminder of the paper is organized as follows. Section II explains the context of surveillance using WMSNs. Section III introduces the disparity map usage for WMSNs surveillance systems, respecting WMSNs specifications, challenges and limitations. In Section IV, one low cost disparity map calculation method is experimented, particularly the Sum of Absolute Differences (SAD). The experimentation is done with reference to our previous work [START_REF] Tannoury | Efficient and accurate monitoring of the depth information in a wireless multimedia sensor network based surveillance[END_REF], where SAD achieved the best results in terms of complexity, computation cost, and speed. Two different scenes, indoor and outdoor, help us to determine the system configuration and sensor nodes deployment with different angles/views and distances. This leads to extract good and well structured disparity maps, holding a high percentage of scene details. Finally we conclude our paper in section V.

II. BACKGROUND

WMSNs are used in different domains and applications, popularly implemented for surveillance [START_REF] Sert | Data fusion and processing in wireless multimedia sensor networks: An analysis for surveillance applications[END_REF]. The development of new surveillance systems is increasing and it motivates both researchers and industrial experts. They try to reach higher level of safety in different contexts such as national security, traffic monitoring, habitat monitoring, e-health, etc [START_REF] Javed | Automated Multi-Camera Surveillance: Algorithms and Practice[END_REF]. Traditional single view monitoring systems recommend a 24/7 human intervention in order to detect or track an intrusion/changes. Adding to this, the high cost and complexity of implementation to configure a well designed hardware based surveillance system must be taken into account. Using WMSNs is very advantageous because of sensors mobility and multiple view cameras. A single camera cannot observe the complete area of interest. Multiple image sensors sources give the application the opportunity to adaptively process and extract data on demand. So WMSNs will cover more areas and bigger ranges for automated real-time monitoring. WMSNs nodes are able to capture, store, process and aggregate multimedia data transmitted from different sensors in the network [START_REF] Ang | Wireless Multimedia Sensor Networks on Reconfigurable Hardware: Information Reduction Techniques[END_REF].

We are focusing on developing a WMSNs system to monitor a scene from different views, using low cost cameras, that can cover and reconstruct the maximum possible area. We will show in Section III how we can profit from different sensor couples to calculate disparity maps holding depth values and essential for 3d scene monitoring or reconstruction. In our previous research work [START_REF] Tannoury | Introducing disparity map for 3d scene reconstruction in wireless multimedia sensor networks[END_REF], we investigated all WMSNs applications and constraints from disparity map calculation perspective, where we studied all disparity map methods and chosen possible algorithms applicable in our context.

Energy consumption is the main constraint while developing new WMSN systems independently from the applications like monitoring, objects tracking, traffic avoidance, etc. Transmission consumes the big portion of the power, as experimented in [START_REF] Zhao | Estimating the battery consumption of data processing in a wireless sensor node[END_REF]. So decreasing the transmitted multimedia data size and distance between sensors leads to increasing network lifetime. Our distributed WMNSs will calculate disparity maps on each sensor couples and deliver to the sink low size gray-scale disparity maps.

Another crucial constraint in WMSNs is the coverage problem, where random objects like trees or cars can cause occlusion with the monitored target. Also, two parallel sensors can be overlapped together. Figure 2 shows an example of occlusion and overlapping. Costa et al. [START_REF] Costa | The coverage problem in video-based wireless sensor networks: A survey[END_REF] surveyed this specific issue. The next sections III and IV will take into Fig. 2. Occlusion and overlapping problems in video sensor network coverage consideration all conditions to ensure a good camera sensors placement for better disparity map calculation. This plays an important role by putting sensors in sleep mode or reactivating them based on the area of interest, thus extending the network lifetime.

Consequently, even with these constraints, WMSNs are very advantageous for surveillance purpose including:

1) Enlarging the view: two different camera nodes can monitor the same target but from different distances, one closer from the second; 2) Large field of view: different camera with multiple Field Of Views (FOVs) can be used; 3) Different views: multiple cameras, at the same distance from the target, can point to it from different angles. In the next section, referencing to our previous contributions [START_REF] Tannoury | Introducing disparity map for 3d scene reconstruction in wireless multimedia sensor networks[END_REF], [START_REF] Tannoury | Efficient and accurate monitoring of the depth information in a wireless multimedia sensor network based surveillance[END_REF], we will explain disparity map calculation constraints respecting to WMSNs prementioned limitations. This ensure an efficient usage of WMSNs for disparity map calculation.

III. DISPARITY MAPS IN WIRELESS MULTIMEDIA SENSOR

NETWORKS

The main idea of using disparity maps via WMSNs came from before-mentioned network limitations and the low size of these black and white maps. Calculating the depth value(s) is the essential key to trigger any alert after scene change(s). Sensor nodes can enter sleep mode, so in case an event occurs, sensors can wake up each others to recalculate again new disparities. So worst case, one sensor will be active and the second one sleeps thus decreasing 50 % of the processing and transmission on distributed pairs level. In our last article [START_REF] Tannoury | Introducing disparity map for 3d scene reconstruction in wireless multimedia sensor networks[END_REF], we surveyed all disparity map calculation methods and regrouped them in terms of:

• Computational demand: clock frequency (in MHz/GHz), frame rate (FPS), image quality (in pixels). • Local or Global method: global methods bring off better results than local but are computationally expensive. • Disparity Range: some methods reach deeper disparity ranges.

• Occlusion, discontinuities and uniform textures or texture-less areas handling. • Hardware implementation: requires a graphical processing unit GPU, central processing unit CPU or fieldprogrammable gate array FPGA. Our proposed compromise operates as follows: calculate efficient and accurate disparity maps on a couple of sensors, with limited computational and energy resources. We chosen to use local methods with the minimum clock rate and image quality. Thus we compared and experimented two acceptable methods: Sum of Absolute Differences (SAD) and Sum of Squared Differences (SSD) [START_REF] Tannoury | Introducing disparity map for monitoring and surveillance in wireless video sensor networks[END_REF] [START_REF] Tannoury | Efficient and accurate monitoring of the depth information in a wireless multimedia sensor network based surveillance[END_REF]. Processing time increased linearly with images resolutions and number of couples (pairs of sensors).

Let us recall that the SAD algorithm calculates the absolute difference between the intensity of each pixel in the reference block and that of the corresponding pixel in the target block:

SAD(x, y, d) = (x,y)∈w |I l (x, y) -I r (x -d, y)| (1)
• (x, y, d) represent the disparity map coordinates;

• (x, y) are the coordinates of the pixel of interest;

• d is the disparity value;

• I l is the left reference image;

• I r is the right target candidate image.

It makes the sum of differences over w, where w is the aggregated support window. SAD over-performed SSD with lower computational complexity and processing time, so it is convenient for real-time applications.

Studying, experimenting, and resolving computational requirements while choosing SAD as ideal disparity map calculation method for WMSNs monitoring is principal. But, as stereo matching has its own constraints, this paper outlines all stereo vision requirements for better sensor deployment. At this stage, we can wonder: what are the restrictions to compute good quality disparity maps, and monitor an outdoor or indoor scene from different views and perspectives?

For all researchers working in this field, designing and developing accurate stereo vision systems, and improving the quality of 3D projections, stereo baseline is preliminary. This is the distance between sensor 1 and sensor 2. Wutthigrai Boonsuk [START_REF] Boonsuk | Investigating effects of stereo baseline distance on accuracy of 3d projection for industrial robotic applications[END_REF] implemented a stereo vision system for industrial robotics and concluded the following: shorter baseline distances performs better at shorter distances to the target, but at longer distances, wide baselines are better. Si et al. [START_REF] Si | Barrier coverage for 3d camera sensor networks[END_REF] used camera sensor networks to detect intrusions passing through a barrier area. They implemented multiple parallel cameras in order to guarantee a maximum coverage for the monitored barrier. Increasing the number of cameras lets them ensure that a minimum of two sensors will capture the intruder.

Kim et al. [START_REF] Kim | 3d scene reconstruction from multiple spherical stereo pairs[END_REF] proposed a 3d modeling method using high resolution spherical images. Their 3D reconstruction was based on stereo image pairs using vertical displacement between camera views. The epipolar geometry depends on the In our context, the added value is computing the disparity map between two camera nodes and tracking the change(s) in depth or reconstruct the intruder in the scene.

Figure 3 illustrates the effect of increasing parallel cameras baseline or rotating them. The disparity value is between 0 and 1 and it increases with the sensing direction. So a high disparity value indicates a high difference between the couple of images: they are less correlated. Otherwise, two perpendicular cameras, weakly correlated, leads to a disparity of 1 [START_REF] Dai | A spatial correlation model for visual information in wireless multimedia sensor networks[END_REF].

Figure 4 shows how depth changes with baseline b and distance to target h. C 1 and C 2 are the centers of the sensors. M 1 and N 1 are the projections of the points M and N in the first image. M 2 and N 2 in the second image. ∆M and ∆N are the shifts between these positions. ∆M -∆N is proportional to the disparity ∆E and ∆E itself is approximately proportional to the depth difference ∆Z. A larger coefficient b/h leads to smaller error in depth. However, a high coefficient reflects more changes between the images, hence more difficult matching process. For example, metropolitan images where there is a big number of buildings creating occlusions and changing fast with observation angle. Thus, smaller angles between views is recommended for accurate disparity maps.

So the choice of the coefficient b/h depends on the monitored scene scenario compromise. Delon et al. [START_REF] Delon | Small baseline stereovision[END_REF] studied deeply stereo visions with small baselines and resulted that an angle of 53%, typically b/h = 1, is ideal for indoor. Objects far from sensors lenses shift less, and objects nearer shift more. In traditional WMSNs coverage, it is advantageous to increase the angles and distances between the nodes to avoid duplication of data. Two near sensors may monitor the same object. But in our context, it is different because we tend to increase intersection between cameras, since we risk to search for a match in the second sensor that is not shown in the first reference one. The next section shows experimental results for two different outdoor and indoor scenes, where disparity calculation is made with different baselines, distances and angles. This ensure and improve the sensors deployment strategy for better disparity maps quality.

IV. EXPERIMENTATION RESULTS

We created our own data-set using Autodesk 3ds Max 2018, where we modelled two realistic outdoor and indoor scenes. The indoor scene represents an elderly man walking in the bedroom, as shown in Figure 5. Similarly, Figure 6 displays The simulated scenes have different textures, lighting conditions, colors, reflections, and occlusions. So it keeps natural and random environmental conditions as real as possible. Cameras are placed with predefined field of views (FOV) of 45 and 60 degrees. Our experimentation takes into consideration multiple baseline distances and distance to the target (the man) in meter(s), and angles of observation in degree(s). Figure 7 shows an example of camera sensors placement to cover the monitored scene.

Firstly, for each camera couple, we rendered the images and exported them as Joint Photographic Experts Group (JPEG). The rendered captured images are low in resolution of 640x480 pixels (indoor) and 480x270 pixels (outdoor). This is because resolutions affects directly the disparity map processing time, as experimented in our last publication [START_REF] Tannoury | Efficient and accurate monitoring of the depth information in a wireless multimedia sensor network based surveillance[END_REF]. Secondly, Sum of Absolute Differences (SAD) uses them as parameters to compute disparity maps via MATLAB 2017. Finally, we made a quality testing on the computed disparity maps to conclude the best sensors placements (distance and orientation). To experiment the disparity maps quality, tradi- tional computer vision researchers use a ground truth disparity map as reference. This best quality reference is computed with a laser scanner or from middlebury data-set [START_REF] Scharstein | High-resolution stereo datasets with subpixel-accurate ground truth[END_REF]. This is not feasible in our context since we created our own virtual scenario, so no ground truth. The Structural Similarity (SSIM) is used to solve this issue and define a disparity map quality measurement methodology. SSIM measures the similarity between two images, thus making it convenient to compare the saved structure between the computed disparity and one of the left or right images pair. To prove the concept, we applied SSIM on different disparity maps going from bad to very high quality, and we monitored how SSIM changed linearly from 0 to 1.

Figure 8 illustrates a high SSIM of 0.3941 of a good disparity map between two sensors having a baseline of 0.6 meters and 3.0 meters from the target (walking man). Table I, Table II, and Table III show different disparity map qualities for multiple baselines, angles and distances for indoor and outdoor scenes. Table I shows how SSIM increases with the baseline distance. So, for indoor scenes, it is recommended to use wide baselines thus ensuring a small FOV, small depth error but more occlusions risks. For small baselines, the stereo correspondence is simpler as images are similar with few occluded regions, but it risks a large depth uncertainty. Based on Table II results, increasing the angle between the sensors gives us more opportunity to have good disparity maps for long distance to target. For short distances, changes in the angle results a big difference in the views. Table III insured that for outdoor scenes, monitoring a long ranged target can be done with higher angle between sensors. Yet, the ideal baseline for indoor monitoring is 0.9m. The best angle for rotated sensors is 30 degree with a baseline of 3.0m. For outdoor, putting sensors with 10 degrees rotation and 6m to target calculates good disparity maps.

V. CONCLUSION AND FUTURE WORK

Calculating disparity maps on distributed sensors is a WM-SNs added value for traditional multimedia data by saving and delivering depth information. This is preliminary and essential for events/changes detection or 3D scene reconstruction. Our approach respects all WMSNs limitations, specially power consumption and quality of service. This research outlines an For future work, we intend to explore and define how disparity maps will be transferred from couple to another, from nodes to aggregator(s). In this way, we will reach an efficient WMSNs based surveillance system that covers a high range of targets for long lifetime. The 3D reconstructed information(s) can help different applications in many domains like elderly people monitoring, military tracking, habitat monitoring, etc.

Fig. 3 .

 3 Fig. 3. Stereo vision system baseline and orientation

Fig. 5 .

 5 Fig. 5. Indoor scene: elderly man walking in his private bedroom

Fig. 7 .

 7 Fig. 7. Camera positions from top

TABLE II SSIM

 II VALUES FOR DIFFERENT ANGLES AT DIFFERENT DISTANCES FROM TARGET (INDOOR)

		Rotated sensors
	Angle between sensors (degree) Distance to target h SSIM
			0.9	0.2539
	30		1.5	0.3377
			3.0	0.3649
			0.9	0.1754
	90		1.5	0.2237
			3.0	0.2640
		TABLE III
	SSIM VALUES FOR DIFFERENT ANGLES (OUTDOOR)
	Angle between	Distance =	Distance =	Distance =
	camera1 and	4 m	6 m	8 m
	camera2
	(degree)
	10	0.1597	0.1602	0.1453
	20	0.1318	0.1346	0.1282
	30	0.1387	0.1445	0.1367
	40	0.1371	0.1356	0.1344
	50	0.1375	0.1294	0.1431
	60	0.1395	0.1318	0.1506
	70	0.1310	0.1386	0.1502
	80	0.1235	0.1354	0.1533
	90	0.1293	0.1354	0.1575
	experimental contribution to ensure good sensors deployment
	for ideal disparity map quality.

ACKNOWLEDGMENT

This work is partially funded by the Labex ACTION program (contract ANR-11-LABX-01-01), the France-Suisse Interreg RESponSE project, the National Council for Scientific Research in Lebanon CNRS-L and the Hubert Curien CEDRE programmme.


Christian Salim

Abdallah Makhoul

Rony Darazi

Raphaël Couturier

Kinematics Based Approach for Data Reduction in Wireless Video Sensor Networks

Keywords: wireless video sensor networks, shot similarity, video aggregation, frames similarity, event detection

Recently, Wireless Video Sensor Networks (WVSNs) have been one of the most used technologies for surveillance, event tracking, nature catastrophe and other sudden events. Those networks are composed of small embedded camera motes which help to extract the needed information for the monitored zone of interest. A WVSN is divided into 3 different layers: the video sensor-node layer, the coordinator layer and the sink. Every video sensor-node is in charge of capturing the raw data of images and videos and sending it to the coordinator for further analysis before sending the analyzed data to the sink. In a normal scenario, the load of collected images and videos from different sensor nodes on the same network is huge. Sending all the images from all the sensor nodes to the coordinator consumes a lot of energy on every sensor, and may cause a bottleneck. In this paper, some processing and analysis are added based on the similarity between frames on the sensor-node level to send only the important frames to the coordinator. Kinematic functions are defined to predict the next step of the intrusion and to schedule the monitoring system accordingly. Compared to a fully scheduling approach based on predictions, this approach minimizes the transmission on the network. Thus, it reduces the energy consumption and the possibility of any bottleneck while guaranteeing the detection of all the critical events at the sensornode level as shown in the experiments.

I. INTRODUCTION

In wireless video sensor networks, WVSN, the event driven and periodic approaches are combined. The wireless video sensor networks are 3 layers network: The Wireless Sensor Node level, The Coordinator level and the Sink as shown in Figure 1. The wireless video sensor nodes have very limited energy resources. Those nodes are responsible of monitoring a well determined area of interest. Thus, to monitor an area, they film it according to their field of views (FOVs) and send those videos to the coordinator. Filming a video and capturing its frames consume a lot of energy especially since each sensor is sending a big number of frames to the coordinator. To reduce the energy consumption on the sensor node level, the main target is to reduce the energy consumption related to the sensing process, and to the transmission phase.

Normally if there is no critical event in the area of interest, the WVSN operates periodically [START_REF] Salim | Combining frame rate adaptation and similarity detection for video sensor nodes in wireless multimedia sensor networks[END_REF]. To reduce the energy consumption related to the sensing process on the sensor level, a simple probabilistic method has been proposed to adapt the frame rate of every sensor node, depending on the level of criticality, the position and the trajectory direction of the intrusion in the scene (the movement's vector) based on a probability based prediction [START_REF] Jiang | Probability-based prediction and sleep scheduling for energy-efficient target tracking in sensor networks[END_REF].

After adapting the number of frames sensed by the node in every period, the main goal is to reduce the number of frames sent from the sensor node to the coordinator. To reduce this number, each sensed frame is compared with the last frame sent. This comparison is an edge based comparison: according to [START_REF] Soro | A survey of visual sensor networks[END_REF], we are interested in the simple image processing algorithms. Local (on-board) processing of the image data reduces the total amount of data that needs to be communicated through the network. Local processing can involve simple image processing algorithms (such as background substraction for motion/object detection, and edge detection). According to a predefined threshold of similarity, the node decides whether to send this frame to the coordinator or not [START_REF] Salim | Combining frame rate adaptation and similarity detection for video sensor nodes in wireless multimedia sensor networks[END_REF].

The coordinator of an area of interest serves as a cluster head leading a defined number of nodes. To sum up, we try to detect critical events and track intrusions through the area of interest via a wireless video sensor network, while using an energy efficient method.

The reminder of this paper is divided as follows: section II introduces the state of the art, section III explains in brief the Movement State Vector for later use in the kinematic based approach. For Data Reduction on the sensing phase, the kinematic based and position based approaches used for predictions, as well as the frame rate adaptation technique are explained in section IV. Data Reduction technique on the transmission phase is discussed in section V. In section VI, some experimental results validate the approach. At the end, section VII concludes the paper.

II. RELATED WORK

In this section, some previous works regarding this topic in the literature are explored. Several works dealt with the location of the intrusion and the target in the zone of interest [START_REF] Ghelichi | Target localization in wireless sensor network based on time difference of arrival[END_REF], [START_REF] Yoo | Target localization in wireless sensor networks using online semi-supervised support vector regression[END_REF], [START_REF] Ghosal | A survey on energy efficient intrusion detection in wireless sensor networks[END_REF], [START_REF] Krontiris | Towards intrusion detection in wireless sensor networks[END_REF], [START_REF] Li | Group-based intrusion detection system in wireless sensor networks[END_REF], [START_REF] Misra | A simple learning automatabased solution for intrusion detection in wireless sensor networks[END_REF]. In [START_REF] Ghelichi | Target localization in wireless sensor network based on time difference of arrival[END_REF], the authors implement an evolution of the time difference of arrival (TDOA) using 4 stationnary sensor nodes as reference nodes in the area of interest. The intersection of several hyberboles are studied to perform the localization process which needs 4 equations from the 4 reference nodes. This new method outperforms the traditional TDOA in terms of error rate. Machine learning has been used for target localization in WSN in [START_REF] Yoo | Target localization in wireless sensor networks using online semi-supervised support vector regression[END_REF]. In [START_REF] Ghosal | A survey on energy efficient intrusion detection in wireless sensor networks[END_REF], [START_REF] Krontiris | Towards intrusion detection in wireless sensor networks[END_REF], [START_REF] Li | Group-based intrusion detection system in wireless sensor networks[END_REF], [START_REF] Misra | A simple learning automatabased solution for intrusion detection in wireless sensor networks[END_REF], the Intrusion Detection System (IDS) has been used. This system divides the network into several areas and each area into sub-areas. The location of the intrusion is equal to the group position. In [START_REF] Gupta | Tracking moving targets in a smart sensor network[END_REF], the authors develop a small algorithm that detects and tracks a moving target in WSN. The sensor that detects the intrusion sends an alert according to the projected path of the target. They use the triangulation method to locate the target. Several works have studied the path of an intrusion in the area of interest in the literature. In [START_REF] Marculescu | Efficient tracking of moving targets by passsively handling traces in sensor networks[END_REF], the authors develop a method that exploits the traces of target presence. The sensor node plays a role in decreasing a trace intensity with time and propagates them to the network. A tracking agent is used to follow the traces. This agent can be a pure software originated by a mobile sink, a human being with a device to communicate with the network or a mobile robot. The objective is to follow the traces from the first alert message detecting a target, the agent can immediately start with the first trace by studying the intensity of the trace, and then by grouping 2 or more traces, the path can be built. In [START_REF] Wen | Energy efficient moving target tracking in wsn[END_REF] the target is considered as an unkown sensor with RFF. Measurement selection in this work are based on fuzzy modeling, the position estimation is aggregated through neighborhood functions. An optimization of this work is done by the Generalized Kalman Filter method. The authors in [START_REF] Ez | A comparative study of target tracking approaches in wireless sensor networks[END_REF] compare between several target tracking approaches in WSN. They show the different aspects of tracking: security, energy efficiency, network structure, accuracy, mobility of the target, fault tolerance... Several metrics in [START_REF] Ez | A comparative study of target tracking approaches in wireless sensor networks[END_REF] have been taken into consideration: 1) The network structure : Tree Structure, Face structure or Cluster structure 2) Prediction-based Tracking: to predict the next position of the target several approaches use the kinematics functions, Kalman filter, extended Kalman filter and particle filter.

3) The number of targets: it differs if there is 1 target or several targets which can be more consuming with high complexity. 4) Type of the Object: Discrete (people, animals, vehicles) or Continuous (forest fires, oil spills, ....). Several reasons may cause the loss of the target in [START_REF] Ez | A comparative study of target tracking approaches in wireless sensor networks[END_REF] such as communication failures, abrupt changes in the speed and direction of the target, the energy-hole problem, the inaccuracy and the delay caused by the computation of the algorithms. Authors in [START_REF] Alaybeyoglu | A dynamic lookahead tree based tracking algorithm for wireless sensor networks using particle filtering technique[END_REF], [START_REF] Chen | Dynamic object tracking tree in wireless sensor network[END_REF] adopted spanning tree methods to locate and track the intrusions in the area of interest in WSN. A lot of works focus on cluster-based approaches to track the targets in the network [START_REF] Darabkh | Performance evaluation of selective and adaptive heads clustering algorithms over wireless sensor networks[END_REF], [START_REF] Cheng | A survey of localization in wireless sensor network[END_REF], [START_REF] Boukerche | Localization systems for wireless sensor networks[END_REF], [START_REF] Wang | A hybrid clusterbased target tracking protocol for wireless sensor networks[END_REF], [START_REF] Kong | Energy-aware distributed clustering algorithm for improving network performance in wsns[END_REF], [START_REF] Deldar | Designing a predictionbased clustering algorithm for target tracking in wireless sensor networks[END_REF]. In [START_REF] Wang | A hybrid clusterbased target tracking protocol for wireless sensor networks[END_REF], they use a hybrid cluster-based target tracking. This method has static clusters, each node cooperates with its cluster head to track the mobile target. Once a target approaches the boundaries, sensors from different clusters can cooperate forming a dynamic cluster on the borders. When the target moves away, the dynamic cluster is dismissed. It is energy consuming and uses a lot of overhead to form and dismiss a cluster. Some papers concentrate on the contour tracking using minimal contour tracking algorithms to improve energyefficency such as [START_REF] Jeong | Mcta: target tracking algorithm based on minimal contour in wireless sensor networks[END_REF] where all sensors in the contour are on and all the others are off depending on a sleep schedule. In [START_REF] Rahman | Energy efficient multiple targets tracking using target kinematics in wireless sensor networks[END_REF], [START_REF] Alsalih | Distributed voronoi diagram computation in wireless sensor networks[END_REF], the authors transform the whole tracking area to voronoi polygons while having 3 kinds of sensors: workers, border and computational. Other approaches are based on kinematics rules and the probability theory [START_REF] Jiang | Probability-based prediction and sleep scheduling for energy-efficient target tracking in sensor networks[END_REF], kinematics rules are used to detect the path of the target in the network, and the probability theory can help to schedule the sleep mechanism of the sensors according to the trajectory of the target and its future predicted positions, acceleration and speed.

In this paper, 2 sensor nodes are neighbors as shown in Fig 2 if there is a geometrical correlation between their FOVs. A node to node connection is established. If an intrusion is detected in sensor node S 1 , this sensor studies the direction vector of the trajectory D of this intrusion, and send this vector to all its neighbors. In this figure S 2 is the neighboor that receives the vector. In other terms, this vector also represents an alert that an intrusion is taking place in the monitored area. In the kinematic based approach (KBA) proposed in this paper, every sensor node starts the sensing process by taking as a frame rate the minimum frame rate possible [START_REF] Salim | Combining frame rate adaptation and similarity detection for video sensor nodes in wireless multimedia sensor networks[END_REF]. When this sensor is triggered by another node (after the probability study of the trajectory and the new location of the intrusion) that an intrusion may pass by its FOV, it adapts the frame rate according to the level of probability sent in the alarm message from the sending sensor. In this paper, we consider that a sensor node can determine the position of the intrusion at detection [START_REF] Jiang | Probability-based prediction and sleep scheduling for energy-efficient target tracking in sensor networks[END_REF].

III. SENSOR NODE LEVEL: SENSING PHASE

In the sensing phase section, the probability based prediction method is introduced to determine the trajectory of the intrusion. This process leads to adapt the frame rate of the triggered sensors in the region of the predicted path. This adaptation of the frame rate differs in the same region between sensor nodes according to the probability. This probability defines the percentage of the intrusion to pass by this sensor's field of view (FOV). It all depends on the trajectory vector generated from the first sensor that detects the intrusion.

When a node detects a target, it sends an alarm to actively raise the frame rate of all its neighbor sensor nodes. In this case all these nodes will be ready to detect the approaching target. But the target may move to a side that is disproportional to some sensor's field of views, in this case the variation of the frame rate varies between sensor nodes depending on the direction of the target. A node by which the intrusion may not pass by is called a low-probability sensor node, this node raises its frame rate to a certain extent in case any abrupt change of direction or speed of the intrusion happens. However, a node by which the intrusion has a high probability to pass by, raises its frame rate to the maximum frame rate.

The target prediction technique is based on two big studies: first, the kinematics rules to calculate the expected displacement of the intrusion (position after a certain time t and moving direction). Secondly, the probability theory to adapt the frame rate of each sensor node. Based on these predictions, the decision of raising the frame rate in each sensor node is made according to the probabilistic study that also schedules the time to raise the frame rate when the probability is close to one. This approach reduces the energy consumption of the whole network by selecting the sensors that need to adapt their frame rate not only in the whole network but also in a very specific region.

To summarize, 3 steps are needed to apply the KBA (kinematics based approach) approach on the sensor node level:

1) The target prediction.

2) The reduction of the number of triggered node to adapt their frame rate.

3) The adaptation time control: based on the probability, the approach schedules the node to adapt its frame rate when the probability of detecting the target in its FOV is equal or close to 1.

A. Movement State Vector

Let us start by defining the Movement Vector. The movement state vector is a combination of 5 parameters related to the movement.

--→ M S(n)={t n , x n , y n , -→ v (n), -→ a (n)}, where: t n is the actual time, x n and y n define the position of the target at t n , -→ v (n) is the average velocity vector defined by its scalar speed v n and its moving direction θ n and -→ a (n) refer to the acceleration during [t n-1 ,t n ].

B. Current State Movement Calculation

First to calculate the first movement state vector of the intrusion, the first two detected positions of the intrusion are needed. To be able to calculate the movement state vector at time t n , all we need to have are --→ M S(n -1) and the position x n , y n at t n so the functions can calculate the velocity

- → v (n)(v n ,θ n ) and
v n = (y n -y n-1 ) 2 + (x n -x n-1 ) 2 t n -t n-1 (1)
θ n = arctan y n -y n-1 x n -x n-1 , x n = x n-1 (2)
-→ a n = -→ v n ---→ v n-1 t n -t n-1 (3)
In this approach, the sensor nodes are time synchronized locally in a small range, so that the received t n-1 may be used in the calculation. Local time synchronization may be easily achieved with a protocol such as RBS [START_REF] Elson | Fine-grained network time synchronization using reference broadcasts[END_REF], or simply with HELLO message exchange [START_REF] Jiang | Cflood: A constrained flooding protocol for real-time data delivery in wireless sensor networks[END_REF].

IV. PREDICTIONS In this section, the kinematics-Based prediction technique is discussed.

In this type of prediction, we suppose that τ = t n+1 -t n as the lapse of time between two states, and all the prediction vectors are labeled with an apostrophe such as -----→ M S n+1 .

A. Kinematics-Based

The kinematics rules are used to generate a prediction about --→ v n+1 and -----→ M S n+1 . To do so, we consider the acceleration -→ a n as constant during a defined time of t n+1 -t n indeed, according to the displacements taylor polynomial, its rate of change can be ignored because it is the third derivative of displacement. In this case, the predicted velocity, acceleration, trajectory and position of any intrusion can be computed based on the kinematics rules and equations as follows:

-

-→ a n+1 = -→ a n (4) --→ v n+1 = -→ v n + --→ a n+1 × τ (5) -----→ M S n+1 = --→ v n+1 × τ + --→ a n+1 × τ 2 (6)

B. Position-Based

To be able to compute the following predicted positions, at least the first two positions of the intrusion must be detected before any prediction.

--------→

(x n+1 , y n+1 ) = -----→ (x n , y n ) + -----→ M S n+1 (7)
The fact of considering --→ a n+1 = -→ a n should to be respected over a time τ = t n+1 -t n for the estimation. But once the sensor senses the new position of the intrusion, the new --→ a n+1 is computed and taken into account in the rest of the processing. The distance between position n and n + 1 is calculated as follows:

d n+1 = v n+1 × τ (8)
d n+1 = (x n -x n+1 ) 2 + (y n -y n+1 ) 2 (9)
The main target in this work is to get the estimation of the new position of the intrusion (x n+1 , y n+1 ). A straight line can be drawn for y displacement as a function of x such as:

y n+1 = y n -y n-1 x n -x n-1 × x n+1 + b (10)
This above equation is also valid for x n and y n already sensed and stored, their values are used to get b. In the next step, a system of two equations for x and y are used to get x n+1 and y n+1 as follows:

x n+1 = 1 2 a n+1 τ 2 + v n+1 τ + x n y n+1 = 1 2 a n+1 τ 2 + v n+1 τ + y n (11)

C. Adaptive frame rate function

In this section the Adaptive Frame Rate function is discussed. This function is dedicated to changing the frame rate of each sensor node according to the direction conditions, the generated probabilty and the maximum Frame Rate of the sensor node.

Each sensor that detects the intrusion sends an alarm message to its neighbor nodes. This message contains the ID and the position of the alarm node, as well as the movement state vector ---→ M S n and the prediction results ( -----→ M S n+1 ,x ,y ).

Every sensor that receives the message checks the received values and predictions with its own FOV. If the intrusion is set to pass by this sensor the probability prob is different than 0. In this case, this sensor node increases its frame rate F R according to the predefined maximum frame rate F R max as follows:

F R = F R max × prob (12)
As shown in Figure 4, if the probability prob is close to 1 then the frame rate of this sensor node increases and approximately reaches its maximum frame rate available. The probability is computed based on the number of periods nb p needed by the intrusion to reach the sensor-node in question as the equation below shows:

prob = 1 nb p ( 13
)
The number of periods needed is computed based on the distance between the intrusion and the sensor node and the speed of the intrusion. After adapting the number of frames sensed by the node in every period, the aim is to reduce the number of frames sent from the sensor node to the coordinator. To reduce this number, each sensed frame is compared with the last sent frame to the coordinator. This comparison is an edge based comparison: according to the study in [START_REF] Soro | A survey of visual sensor networks[END_REF], we are interested in the simple image processing algorithms. Local (on-board) processing of the image data reduces the total amount of data that needs to be communicated through the network. Local processing can involve simple image processing algorithms (such as background substraction for motion/object detection, and edge detection). According to a predefined threshold of similarity, the node decides whether to send this frame to the coordinator or not [START_REF] Salim | Combining frame rate adaptation and similarity detection for video sensor nodes in wireless multimedia sensor networks[END_REF].

VI. EXPERIMENTAL RESULTS

In this section, several experiments have been conducted using MATLAB simulator, connected to multiple Microsoft Vx-800 cameras. A defined scenario has been taken into consideration as shown in Figure 5 andTable I. This table represents the sensor nodes in their active mode, when the intrusion is in their FOV, and in their passive mode when no intrusion is detected in their area of interest. A stable frame rate of 30 fames per second (Fps) is set to be the frame rate of the cameras. The maximum frame rate in those experiments is decreased to 15 Fps. This approach is compared to the PPSS algorithm proposed in [START_REF] Jiang | Probability-based prediction and sleep scheduling for energy-efficient target tracking in sensor networks[END_REF]. The main purpose in this work is to send to the coordinator the frames that represent the critical situations. The coordinator reacts accordingly. We have used 6 Microsoft LifeCam VX-800 cameras to film a short video of 750 seconds, each camera is connected to a laptop to do the processing via a Matlab simulator. In this study, an intrusion has been detected in the sensor-nodes at the following S1: 60 seconds from 30 to 90. S2: 60 seconds from 70 to 130. S3: 300 seconds from 120 to 420 S4: 240 seconds from 400 to 640 S5: 60 seconds from 630 to 690 S6: 0 seconds. The process has been run for 720 periods, each period consists of 1 second, with a frame rate equal to 30 frames per second. The frame rate in each sensor node changes independantly according to the theory explained above. In each period, every sensor node senses a certain number of frames according to the assigned frame rate. The minimum frame rate is set to F R = 1 frame per period. The initial and maximum frame rate is considered as F R = 15 frames per period. In this case the sensor node senses 15 frames from the 30 ones in the period.

Then, the PPSS approach has been implemented like in [START_REF] Jiang | Probability-based prediction and sleep scheduling for energy-efficient target tracking in sensor networks[END_REF] for the same video sequence. This algorithm adopts the normal law of probability and the kinematics rules. Its role is to schedule the monitoring time of the sensor-node depending on the trajectory of the intrusion and the time needed to reach its FOV and the sensor-node sends all the sensed frames to the coordinator while the intrusion is in its FOV, and then it goes back to the sleep mode. But after several experiments, this approach tends to lose information up to 15% due to probability errors. This loss of data in PPSS is shown in Figures 6 and7 for sensor S1 in our scenario.

A. Data Reduction

In this section, the biggest challenge in WSN is exploited, which is the energy consumption problem due to the limited resources of the sensor nodes and to the big number of data (frames) transmitted all over the network. On the sensor node level, the energy consumption problem is the main issue as well as the bandwidth limitations. In the proposed scenario, when no adapted frame rate is implemented on each sensor node, the amount of sensed frames remains at 30 for each period. In terms of energy consumption and bandwidth usage, sending all the frames is costly while a lot of frames are identical and do not represent any criticality. Sending frames with a time difference inferior to 0.03 seconds in a video surveillance not represent any additional information. For this reason, we set the initial and maximal frame rate to F R = 15 frames sensed per period. The proposed method is implemented on every video-sensor node to reduce the number of frames sensed and sent to the coordinator. For every sensor node, the frame rate is adapted after two periods where P = 1 second. Every sensor node sends the first frame of each period. For sensor node S1, as seen in Figure 7, this technique only sends the critical frames to the coordinator according to a predefined threshold of similarity as explained in the upper sections, this threshold is set to 70% [START_REF] Salim | Combining frame rate adaptation and similarity detection for video sensor nodes in wireless multimedia sensor networks[END_REF]. The number of frames sent in each period is the parameter that influences the frame rate. The frame rate variation seen in Figure 6 validates the frame rate adaptation method in the active mode of sensor S1, when an intrusion is detected.

Figure 7 reveals the number of critical frames sent to the coordinator via S1, this variation in the number of critical frames per period is proportional to the adaptation of the frame rate. As seen in Tables II and III for S1 and in Tables IV and V for S3, adapting the frame rate reduces the sent data by more than 90%. Then, applying the similarity function proposed in this paper causes the degradation of the number of sent frames by 92% from 129, 600 frames to 11, 041 frames. Tables VI,VIII show the data reduction caused by KBA on the sensing and transmission levels. As for the bottleneck issue, the bandwidth capacity is the main concern and the KBA approach decreases the use of this capacity by reducing the number of frames transmitted all over the network as shown in Table XIII

B. Energy Consumption Study

In this section, an energy model is adopted from [START_REF] Jiang | Cflood: A constrained flooding protocol for real-time data delivery in wireless sensor networks[END_REF] where the radio energy for the transmission of the data on the radio and the computational energy for the in-node processing are the core of the energy consumption of every sensor node as shown in the equation below:

E = E radio + E comp (14)
Table XIV shows the different parameters to compute the energy consumption while considering: I T X and I RX the electric power needed to respectively send and receive by the radio while T T X and T RX the respective corresponding operating times over 1 byte, and V is the constant voltage supply throughout the transmission.

E radio (k) = k.I T X .V.T T X + k.I RX .V.T RX (15)
Taking into account that k is the number of bytes sent from a specific sender to a specific receiver. For the computational energy consumption:

add , mul , cmp , sht are the basic operations (shift,addition,comparison,multiplication, etc...), Table XIV shows the required energy for each operation. To compute this energy consumption, the number of each basic operation in the algorithm must be counted: In order to compare both approaches, the two components of the energy consumption have been computed using a CC2420 radio transceiver and an ARM7TDMI microprocessor. Table XIV displays the parameters that are used in the calculations and which are found in the data sheets of the node's components [START_REF] Jiang | Cflood: A constrained flooding protocol for real-time data delivery in wireless sensor networks[END_REF].

E comp = N add × add +N sht × sht +N mul × mul +N cmp × cmp (16)

C. Sensor Node Level

In the experiments, when running the KBA technique, 9262 frames were sensed and compared using the similaritiy function. For a 640 × 480 frame size, 307, 200 pixels exist in each frame. Each similarity takes into account all the pixels in every frame. The KBA approach consists of 1 comparison. The maximum computational energy for E comp for 9, 262 similarities is computed as follows:

E comp = 13, 768 × 640 × 480 × cmp (17)
For KBA, E comp,KBA =9 J. For PPSS, E comp,P P SS =0.1 J.

To move on to the transmission phase, using KBA, where the network transmits 11, 041 frames = 220 MB, comparing to the 17, 694 frames = 354 MB for PPSS.

E radio,KBA = 423J (18)
E radio,P P SS = 682J

The total energy consumption is computed as follows:

E KBA = E comp,KBA + E radio,KBA = 432J (20)
E P P SS = E comp,ppss + E radio,ppss = 682J

Based on Figure 8, KBA algorithm consumes more energy on the computational level, but reduces much more energy on the transmission level. Figure 8 compares both approaches in terms of energy consumption on the overall network while considering a starting energy of 1, 000 J for the network.

VII. CONCLUSION

In this paper, a kinematics based approach for an adaptive frame rate with a similarity detection function for wireless video sensor nodes has been introduced. The conducted experiments show that the proposed algorithm did not miss any event in the recorded video sequence. Thus, the algorithm sends the minimum required frames to the coordinator node by using a similarity detection function at the sensor node level. The selected frames are transmitted by the sensor nodes to the coordinator without missing any required information. The results show that the size of the transmitted data in each period is reduced and the energy consumption is decreased, thus, preventing any bottleneck problem regarding the bandwidth limitation issue. Comparing KBA approach with [START_REF] Elson | Fine-grained network time synchronization using reference broadcasts[END_REF] in terms of data reduction and energy consumption, helps us to find out that KBA approach outperforms PPSS, and reduces the number of data for more than 40% than PPSS. Thus, PPSS consumes 2 times more energy than KBA. As future works, some real experimentations are needed on real sensor-nodes.

Fig. 1 .

 1 Fig. 1. Architecture of WVSN

Fig. 2 .

 2 Fig. 2. Direction Vector

  acceleration -→ a (n) vectors to compose the new movement state vector --→ M S(n) at t n as shown in Fig 3 and in the equations below:

Fig. 3 .

 3 Fig. 3. Movement State Vector and kinematics rules

Fig. 4 .

 4 Fig. 4. Adaptative Frame Rate Function

Fig. 6 .Fig. 7 .

 67 Fig. 6. Difference between KBA and PPSS on the sensing phase

Fig. 8 .

 8 Fig. 8. Energy consumption comparison for KBA and PPSS

  . Table XIII the upper hand of KBA over PPSS in the bandwidth consumption reduction.

ACKNOWLEDGEMENT

This project has been performed in cooperation with the Labex ACTION program (contract ANR-11-LABX-0001-01) and partially funded with support from the National Council for Scientific Research in Lebanon CNRS-L, the Hubert Curien CEDRE programme n40283YK, and the Agence Universitaire de la Francophonie AUF-PCSI programme.

By comparing these numbers to the number of frames in Tables IX, X, XI, XII, while applying PPSS algorithm, the efficiency of the KBA approach for the sensing and transmission process surpasses the PPSS algorithm. This gain grows