Ibtissem Boulanouar

Stéphane Lohier

Abderrezak Rachedi

Gilles Roussel

Gaspard Monge

CTA: a Collaborative Tracking Algorithm in Wireless Sensor Networks

In this paper we address the problem of Object Tracking in WSN. We define Mobile Object Tracking as a two stage process: 1) detecting the presence of the object in the monitoring area and 2) locating it at each stage of its progression in the area. We propose a Collaborative Tracking Algorithm named CTA. CTA is a distributed protocol that runs on Heterogeneous WSN (HWSN) which consists of two types of sensors: Motion Sensors (MS) and Camera Sensors (CS). The MS deals with the detection phase and then activates the CS based on a probabilistic threshold. In addition to the tracking algorithm, we propose a deployment strategy and study its impact on CTA. The efficiency of our proposed solution is evaluated according to simulation performed. The obtained results are compared to three existing solutions: 1) BASIC solution where only CSs are deployed always in active mode; 2) OCNS (Optimal Camera Node Selection) is cluster-based approach with a CS election and 3) EAOT, our previously proposed algorithm based on heuristic CS wake up. We observe that CTA significantly reduces the tracking cost in term of energy consumption (up to 38.14% of energy saved compared to other algorithms). It also performs tracking (up to 37.5% on the tracking accuracy).

I. INTRODUCTION

Advances in communication technologies have enabled the development of small sensors with different sensing, processing and communication capabilities. A Wireless Sensor Network (WSN) consists of a set of Wireless Sensors which can harvest, process and share data in an area of interest. Nowadays, sensors allow handling more complex data such as multimedia flows. Thus, we observe the emergence of Wireless Multimedia Sensor Networks (WMSN). These WMSN offer a wide range of applications like surveillance and security applications [START_REF] Akyldiz | A survey on Wireless Multimedia Sensor Networks[END_REF]. WSN and WMSN are called Homogeneous Wireless Sensor Networks because all the sensors that compose the network are identical in term of sensing board and have the same capabilities. In Heterogeneous Wireless Sensor Network (HWSN), different types of sensors may coexist in the same network to achieve different tasks. The HWSN are thus composed of sensors with different sensing board designed to collect various type of data but have the same transmission capabilities. The advantage of using this type of network is to improve the network performance and lifetime by sharing the tasks between the different kinds of sensors: high cost energy tasks can be achieved sporadically by powerful sensors while low-cost energy tasks can be done by constrained sensors.

In this paper, we deal with the mobile object tracking which is one of the most important applications in the Multimedia Wireless Sensor research field. Moreover, we study the impact of deployment strategy on the performances of the proposed tracking algorithm. For that purpose, we set up a HWSN composed of two types of sensors, each of them handle a different task: Motion Sensors (MS) are infrared detectors in charge of mobile object detection while Camera Sensors (CS) handle object localization. We propose a Collaborative Tracking Algorithm named CTA that runs on HWSN. CTA is based on the cooperative communication between the two types of sensors. The MS consumes less energy than CS which allows keeping them active in order to monitor the Area of Interest (AoI) [START_REF] Kulkarni | SensEye: A Multitier Camera Sensor Network[END_REF]. When a MS detects the mobile object, it activates only the CS that has a high probability of localizing it. Unlike EAOT, our previously proposed work [START_REF] Boulanouar | Energy-Aware Object Tracking Algorithm using Heterogeneous Wireless Sensor Networks[END_REF], where the activation of CS depends on a heuristic method based only on the number of received messages, CTA introduce an analytical model based on predefined probabilistic threshold which considers a CS sector sensing range and its orientation as parameters of CS wake up. CTA brings significant improvement as it gives more accurate tracking results and allows saving more energy.

The performance of CTA is closely related to the deployment strategy. Optimal sensor deployment is a challenging issue and depends on the knowledge of surrounding environment. For this purpose, we also propose a deployment solution for both types of sensors. We introduce the notion of critical sub-area: in real indoor environment, some areas are more important to cover than other (entrance/exit, corridor, etc.). Our proposed deployment technique begins with MS placement. We divide the AoI in cells grid and place the MSs at the center of each cell. Afterward, we place the CSs, with random orientation, at the corner of every critical sub-area. Finally, every CS calculates its most beneficial orientation using local information such as neighbors and critical sub-areas. The deployment strategy is proposed in order to enhance the video coverage of critical subareas and to improve the performances of CTA.

The reminder of this paper is organized as follows: Related Work is reviewed in Section II. In Section III we describe our proposed solution. In Section IV we discuss the performance evaluation. Finally, the paper concludes with Section V.

II. RELATED WORK

A. Deployment Strategy

Over the last years, many sensor deployment methodologies have been studied. They can be categorized in two main policies: Random and Planned [START_REF] Younis | Strategies and techniques for node placement in wireless sensor networks[END_REF]. Random deployment has the advantage of being simple and fast and is especially suitable when nothing is previously known about the AoI. In planned deployment, the sensors are placed following a predefined method depending on region topology and sensors features. We denote two kinds of sensors: omnidirectional and directional. The most used solution for omnidirectional sensors is the grid approach where the AoI is divided in grid of cells and the sensors are placed at intersection of cells. The cells can be either squares [START_REF] Couqueur | Sensor Deployment Strategy for Target Detection[END_REF] or triangles [START_REF] Pompili | Deployment analysis in underwater acoustic wireless sensor networks[END_REF]. For the directional sensors, specific solutions already exist [START_REF] Y; Osais | on sensor placement for directional wireless sensor networks[END_REF][START_REF] Ma | A coverage enhancing method for 3D directional sensor networks[END_REF]. The solution proposed in [START_REF] Ma | A coverage enhancing method for 3D directional sensor networks[END_REF] is the most popular of them; it is based on a Virtual Force Algorithm (VFA). This algorithm calculates the virtual force applied by neighborhood on the centroid of each directional sensor view field to determine its new position and direction. In VFA the concept of critical sub-areas is neglected. In this work we introduce this concept; we propose a deployment strategy for both kind of sensors and we study its impact in tracking application.

B. Target tracking

Mobile Object Tracking consists in detecting and locating the mobile object throughout its moving stages in AoI. The tracking can be performed using two types of wireless network: Homogeneous Wireless Sensor Network (WSN) and Heterogeneous Wireless Sensor Network (HWSN). In WSN, all the sensors have the same sensing, energy and radio capabilities. The existing researches about target tracking in WSN can be classified in two main categories: predictive and dynamic clustering based techniques. For the first category, predictive models such as Kalman Filter [START_REF] Pahalawatta | Optimal sensor selection for video-based target tracking in a wireless sensor network[END_REF] are used to predict the future location of the mobile object. This solution is not reliable in applications like military tracking as it cannot ensure a sufficient accuracy of the trajectory predicted. In dynamic clustering based techniques [START_REF] Long | Dynamic Nearest Neighborhood Collaboration Target Tracking for WSN[END_REF][START_REF] Jin | Dynamic clustering for object tracking in wireless sensor networks[END_REF], a set of sensors collaborate to select a leader cluster based on given criteria such as location, available energy, etc. The leader cluster handles the tracking while the others nodes remains in inactive mode which allows energy saving. The main limit of tracking in classical WSN, where only Scalar Sensors are deployed, is that visual observation of the target is not possible. In [START_REF] Liu | Optimal Node Selection for Target Localisation in Wireless Camera Sensor Netwoks[END_REF], the authors studied the node selection in WMSN, where a visual observation of the mobile target is available. They proposed a cluster based and two phases cooperative algorithm: target detection and target localization. The main objective of this solution is to maintain the desired subset of Camera Sensors in active mode while the others remain in sleep mode. When a Camera Sensor detects the moving object, it broadcasts its own coordinates to all the nodes that are within its transmission range. Each of them calculates the probability of detecting the mobile target. If this probability exceeds a defined threshold, the node activates its camera to perform the localization. A wake up algorithm is also merging with this solution to keep the desired number of nodes in active mode. Because of the wake up algorithm and the sector sensing range, the mobile object can enter in the area of interest without being detected immediately.

To overcome the limitation of WSN such as similar sensing and energy capabilities, which limit the type of applications where they can be used, the heterogeneity of Sensor Networks is considered in some recent works. In HWSN, the network is composed of different Sensors with same radio capabilities but different sensing and energy capabilities. The tracking in HWSN mainly focus on dynamic clustering. SensEye [START_REF] Kulkarni | SensEye: A Multitier Camera Sensor Network[END_REF] is the first work that considered the deployment of heterogeneous network. This HWSN consists in a multi-level camera sensor with different sensing and communication capabilities; each level achieves a specific task: detection, localization recognition and tracking. SensEye is dedicated only to indoor applications where energy is available. In [START_REF] Shih | On target coverage in wireless heterogeneous sensor networks with multiple sensing units[END_REF][START_REF] Cardei | Energy-Efficient Target Coverage in Heterogeneous Wireless Sensor Networks[END_REF] the authors also consider the deployment of HWSN. In [START_REF] Shih | On target coverage in wireless heterogeneous sensor networks with multiple sensing units[END_REF] the HWSN consists of different scalar sensors equipped with multiple sensing units that allow sensing and collecting different attributes. In [START_REF] Cardei | Energy-Efficient Target Coverage in Heterogeneous Wireless Sensor Networks[END_REF] an HWSN means different sensors energy capabilities. Indeed, the network is composed of energy-rich and energy-constrained nodes. The first ones handle the data relaying where the second ones handle the coverage of the monitoring area. Nevertheless, none of them consider multimedia sensors deployment. In [START_REF] Boulanouar | Energy-Aware Object Tracking Algorithm using Heterogeneous Wireless Sensor Networks[END_REF], the proposed protocol called EAOT for Energy Aware Object Tracking runs on HWSN composed of MS and CS. EAOT is based on a heuristic CS wake up which takes into account the number of DETECTION messages received from MS. The orientation of CS is not integrated as a parameter, which causes an unnecessary wake up of the Camera and a non-negligible energy loss. Our objective is to reduce this loss by avoiding this unavailing wake up and consequently to perform the tracking with more accuracy and less energy.

III. SOLUTION OVERVIEW

A. Preliminaries and Assumptions

Definition 1: The Motion Sensors (MS) are scalar sensors fitted with infrared motion detectors. Each of them has a circular Field of Detection (FoD) with radius R D (Figure 1.A). The Camera Sensors (CS) are multimedia sensors equipped with video cameras. Each of them has a directional Field of View (FoV) defined by a cone with radius R V and angle α (Figure 1.B). For example the imote2 sensor proposed by MEMSIC [START_REF]Imote2_Multimedia_datasheet.pdf[END_REF] (formerly CroosBow) is equipped with an infrared detector and a low-resolution (640x480) video camera which can be independently activated. An individual mobile object is expected to cross the AoI by taking a random trajectory. As defined above, our HWSN consists of a set of MS and CS placed according to our proposed deployment strategy in monitoring region in order to detect, observe and locate a mobile target. All MSs have the same circular FoD and all the CSs have the same FoV. Every MS is aware of its location and every CS is aware of its location and orientation via one of the existing solution [START_REF] He | Rang free localization schemes for large scale sensor networks[END_REF]. Each sensor can communicate with one other, independently of its type, as long as they share the same transmission range (R T ). Initially, all the cameras are supposed to be in sleep mode and the Motion Detectors are always in active mode. Where P MS is the probability that the mobile object is detected by MS. (X m , Y m ) are the coordinates of MS. N is the total number of MSs that detect the target at the same time in a given area. As detailed in [START_REF] Zou | Sensor Deployment and target Localization in Distributed Sensor Network[END_REF], P MS is closely related to the distance between the target and the sensor. Where (X,Y) represents the real target coordinates. We can express P MS as follow: P MS β define the physical characteristics of the MS. We observe that P MS decreases exponentially while increases.

Definition 3: P CS is the important new concept introduced in this work. It represents the probability that the mobile object is detected by CS. It depends on three parameters: 1) the number of MSs in CS's transmission range that detects the target; 2) the distance between CS and these MSs, and 3) the orientation of CS. P CS is obtained as follows:

Proof:

Hence, we can express the probability P CSi that the mobile object is detected by CS depending only on one MS.

A int is the intersection area between FoD and FoV (see black dashed line in Figure 2). It is calculated on the basis of the distance between CS and MS: the value of A int decreases with the distance.

B. Deployment Optimization

In this sub-section we introduce our proposed deployment strategy. For the two type of sensor, we face two main constraints: the MS placement and CS placement and orientation. 1) Initial deployment scheme: We firstly consider the deployment of MSs. We propose to divide the AoI in grid of cells where each cell has the size of MS detection range. Unlike the solution described in [START_REF] Couqueur | Sensor Deployment Strategy for Target Detection[END_REF], we place MS at the center of cells. Thus, we avoid overlaps. The number of MS is equivalent to the number of cells. As we say in previous section, we introduce the notion of critical sub-areas. Therefore, the total number of CSs is calculated according to their number. For convenience, we suppose that these critical sub-areas have square shapes. So, the number of deployed CS is equivalent to the number of critical sub-areas corners. When the total number of CS is obtained, we place them with random orientation at the corner of each critical sub-area. An illustrative example of initial deployment strategy is shown in Figure 2.

2)Camera sensor orienting scheme:We propose a distributed mechanism to find the most beneficial orientation of each CS according to critical sub-areas. 2.a. Collecting information phase: in this phase each node collects information about its surrounding environment. Neighbors list: each CS broadcasts a HELLO message containing its ID and its own coordinates to all neighbors. We consider neighboring CS as CSs which have a common FoV. This condition is realized when the Euclidian distance between them <= 2*R V . This step ensures that every CS is aware of the location of its neighbors. Critical sub-area list: Critical sub-areas information is obtained via environment MAP available at every node memory. This step ensures that every CS is aware of the critical sub-areas located in its perimeter.

2.b. Decision phase: the objective of this phase is to find the value of deviation angle

that: enhance critical sub-area coverage, minimize the negative effect of overlaps and enhance the whole AoI coverage. For that purpose every CS exploits the information collected in the previous phase. It scans its perimeter around 360° axes to determine whether a free angle is available. A free angle is define as angle where the CS can cover the critical sub-area without any overlaps. In this case it computes the correspondent deviation angle and sends FINAL-DIRECTION message to its neighbors. The CSs which receive this message update their Neighbors list. FINAL-DIRECTION message contains the CS ID, its position and its final orientation. Theses information are used to solve the possible litigation that may occur between two neighbors nodes when the most beneficial orientation of these two nodes overlaps each other. If no free angle is found, each CS calculates the angle which minimizes the overlapping area.

A nearer neighbor means larger overlaps. The critical subareas are weighted according to their importance. For exemple entrane/exits have higher importance than corridors. This weight is used when a CS perimeter overlaps more than one critical sub-area. The critical sub-area with the higher weight has the priority. All the deployment information obtained from the proposed schemes is used to deploy the sensors in the AoI.

C. Collaborative Target Tracking

CTA is a collaborative tracking algorithm. It starts when MS detects the mobile target. A target is detected by a MS when it is within its FoD. In this case, the MS broadcasts a DETECTION message to all nodes within its transmission range. DETECTION packet is sent only by MSs to the two types of sensors, it contains the MS coordinates. The life span of DETECTION message T is fixed according to the mobile object speed. Figure 3 illustrates an example of mobile object tracking using CTA. The dashed blue line represents the object trail. In this case, MS1 is the first sensor that detects the object, followed by MS2. Both of them send a DETECTION message to all their neighbors.

CTA flowchart is depicted in Figure 4.A and 4.B. When a CS receives DETECTION message, it checks if its camera is well oriented. Indeed, if the CS's FoV and the MS that send the DETECTION message don't share a common area, the CS doesn't consider this message in the coming steps. As we said before, each CS knows its orientation according to four cardinal points (north, south, east, oust). By using MS's coordinates contained in the DETECTION message; the CS can verify if there is a common area between its FoV and the MS's FoD.

After that, it calculates P CS using equation ( 2). If P CS exceeds a predefined threshold, this CS turns on its camera to ensure that the object is really within its FoV using background subtraction [START_REF] Piccardi | Background substraction[END_REF] and then performs localization using one of the existing methods [START_REF] Oztrarak | Lightweight object localization with single camera in Wireless Multimedia Sensor Networks[END_REF]. The CS sends the obtained coordinates to the first MS via LOCALIZATION message. LOCALISATION packet is sent by CSs only to MSs. Finally, the camera is turned off. At this stage, if MS receives a LOCALIZATION message from CS, it extracts the object coordinates and sends them to the sink. Otherwise, it supports the localization process by calculating the approximate coordinates as detailed in the section above using equations (1). The results are then sent to the sink. After receiving all object coordinates, the sink reconstitutes the whole target trajectory.

IV. PERFORMANCE EVALUATION

A. Simulation setting

We have used NS-2 simulator [20] to evaluate our proposed solution. Simulation parameters are summarized in Table 1. The values are chosen according to Imote features [START_REF]Imote2_Multimedia_datasheet.pdf[END_REF]. The first part of the simulation is dedicated to the evaluation of the deployment strategy; the results are depicted in Table 2.

We choose two different scenarios to evaluate the performance of our deployment strategy. In the first one we have three critical sub-areas in the AoI while in the second we have five ones. We observe from Table 2 that we need 9MS to cover the AoI, according to the size of AoI. We need respectively 12 and 20 CS to cover the critical sub-areas found in the main AoI. With this deployment strategy we reach until 76.97% video coverage of critical sub-areas with a maximum value of 8.32% overlaps. While for the same number of nodes and a random deployment we obtain 49.15% video coverage of critical sub-areas with 21.45% overlaps. Coverage rate of the whole AoI depending on the number of critical sub-areas and so, the number of nodes is shown in Table 2. For the second part of the simulation, we perform the evaluation of CTA, our proposed tracking algorithm. For that purpose, we compare it to three other solutions: EAOT [START_REF] Boulanouar | Energy-Aware Object Tracking Algorithm using Heterogeneous Wireless Sensor Networks[END_REF] and two others where only CSs are deployed. BASIC is a solution where the CSs are always active and OCNS for Optimal Camera Network Sensor [START_REF] Liu | Optimal Node Selection for Target Localisation in Wireless Camera Sensor Netwoks[END_REF] which is described in section II. Table 3 gives the nodes distribution for the chosen scenarios. The total number of nodes is similar for all cases.

B. Simulation results

We consider three metrics: tracking precision, energy consumption and number of exchanged messages. 1) Tracking precision: the tracking precision corresponds to the number of object coordinates retrieved for a given mobile object trajectory. We consider one coordinate as a two dimensional (2D) point. In CTA the collected coordinates can be calculated by CSs or MSs (equation 1). We consider here that the best tracking precision (100%) is obtained when we have one point every five meters (the target speed corresponds to a pedestrian). Figure 5 shows the average tracking precision during one simulation for five random trajectories depending on number of nodes. We observe that the precision increases with the number of critical sub-areas and thus, the number of nodes. The best tracking precision is obtained by CTA followed by EAOT. 90% corresponds about one point every 6 meters which represents a reasonable result given the number of deployed sensors. Due to the deployment of MS, only the CSs which are in object trajectory are activated. BASIC solution has a better tracking precision than OCNS. Indeed, while in BASIC solution the CS sensors are always active, in OCNS they wake up periodically.

2) Energy consumption: This metric includes the energy consumed for communication and sensor activation. It is closely related to the network lifetime. Figure 6 shows the network global average energy consumed during one simulation for five different random trajectories versus the number of nodes. 100% is the network energy available before the simulation begins. BASIC is an unfeasible solution. Indeed, it consumes 75% of the network energy. CTA allows saving up to 24.45% energy compared to EAOT. Unlike EAOT where the CS activation depends on a heuristic method based on the number of DETECTION messages received. CTA introduces the orientation of the CS and a probabilistic threshold as parameters to activate the CS. Thus, it avoids the unnecessary CS wake up. CTA also consumes up to 38.14% less energy than OCNS due to the use of MS which are scalar sensors consuming less energy than the multimedia sensors. P CS plays an important role in energy consumption. P CS =0.8 is the value which manages the best tradeoff between the energy consumption and the tracking accuracy.

3) Number of exchanged messages: this metric represents the amount of collaborative messages exchanged according to the total number of nodes. We assume that the messages size is the same for all the solutions. The BASIC solution is not represented because there is no collaboration between nodes.

For CTA and EAOT the messages consist in DETECTION and LOCALISATION messages exchanged during the tracking process. For OCNS, in addition to collaborative messages, we add the exchanged messages due to the wake up process which are not necessary in our proposed solution. Indeed, we suppose that the are always active while the CS wake up is conditioned to the above mentioned criteria. Moreover, we ignore the messages sent to the sink for all scenarios. We observe from Figure 7 that OCNS has the larger number of exchanged messages whatever the number of nodes deployed. This is due to the additional cost generated by the wake up algorithm which does not exist in our proposed solution. The results of CTA and EAOT are close to each other because they are based on the same cooperation principal.

V. CONCLUSION AND FUTURE WORKS

This work deals with the problem of energy-efficient object tracking using Heterogeneous Wireless Sensor Network (HWSN). We propose a collaborative protocol for mobile object tracking which is based on a probabilistic study to limit the active period of the camera: CTA (Collaborative Tracking Algorithm). The main goal of CTA is to perform the tracking in efficient and low-cost manner. Unlike EAOT which is based on heuristic CS wake up, CTA defines more precise criteria to activate the CSs such as orientation and a probabilistic threshold. In order to improve the performances of CTA, we also propose a deployment strategy and study its impact on our proposed tracking algorithm. The simulations results show that CTA performs the tracking with the best tracking precision. It consumes 24.45% less energy than EAOT and up to 38.14% less energy than OCNS where only CSs are deployed. We also deduce that the deployment strategy has a positive impact on CTA. Our future works will include object identification, multi-object tracking and node positioning.

Figure 1 : 2 :

 12 FoD and FoVDefinition The term approximate coordinates of the target is introduced. (X t , Y t ) represent the target coordinates calculated by the MSs when no CS is available. We calculate them as follows:… (1)

Figure 2 :

 2 Figure 2: Initial deployment strategy

Figure 3 :

 3 Figure 3: An illustrative example of CTA

Figure 5 :

 5 Figure 5: Tracking precision vs. number of nodes

Figure 6 :

 6 Figure 6: Energy Consumption vs. number of nodes

Figure 7 :

 7 Figure 7: Exchanged messages vs. number of nodes

TABLE 1 :

 1 Parameter value of the simulation

	Mac Layer protocol	IEEE 802.15.4
	Access Mode	CSMA/CA
		non-beaconed
	Area size (AoI)	100×100m²
	Target speed	1,38m/s (pedestrian)
	Simulation Time	150s
	Transmission range (R T )	30m
	Detection range (R D ) of MS	15m
	Depth of view (R V ) of CS	20m
	Angle of view of CS (α)	π /3
	Size of message	100 bytes
	Life span of "DETECTION	20s
	" message T

TABLE 2 :

 2 Deployment strategy results

	Number of	Size of	Number	Coverage
	critical sub-	critical	of nodes	of AoI%
	area in AoI	sub-area	in AoI
	3	30×30m²	MS=9	MS=81.58%
			CS=12	CS=20.78%
	5	3: 30×30m²	MS=9	MS=81.52%
		2: 40×40m²	CS=20	CS=34.64%

TABLE 3 :

 3 Number of deployed sensors

			MS	CS
	CTA and EAOT	9	12 (3 critical sub-areas)
				20 (5 critical-sub-areas)
	BASIC	and	0	21 (3 critical sub-areas)
	OCNS			29 (5 critical-sub-areas)