# Presentation: 102871

## Estimating Missing Data in Sensor Network Databases Using Data Mining to Support Space Data Analysis

**Le Gruenwald**
- The University of Oklahoma
- School of Computer Science
- Norman, OK 73019
- _[ggruenwald@ou.edu](mailto:ggruenwald@ou.edu)_
- This research is funded in part by NASA
- Grant No. NNG05GA30G

## Estimating Missing Data in Sensor Network Databases Using Data Mining to Support Space Data Analysis

- The Objective of this Research
- Project Status
- The Computing Environment
- The Problem Definition
- Possible Approaches
- An Overview of Association Rules
- The DSARM Framework
- The CARMA Approach
- Simulation Results
- Conclusions and Future Work

## The Objective of this Research

*	*
*	**To derive an algorithm to estimate*
*a missing, corrupted or late reading from a sensor in a sensor network environment. *

## Project Status

- Started October 1, 2004.
- Developed an algorithm for estimating data in a centralized sensor network environment (without considering spatial and temporal dimensions).
- Implemented the algorithm and conducted experiments using traffic data.

## The Computing Environment (1)

- Sensor Networks:
- 		Triggered by recent technology advances in Micro 	Electro Mechanical Systems (MEMS) technology, 	low-power analog and digital electronics, and low-	power radio frequency (RF) design.
- Purpose:
- 		To monitor, combine, analyze and respond 	to the data collected by hundreds (thousands) sensors distributed in the physical world in a 	timely manner.
- Example:
- 		Space Science - sensors collecting MARS’ conditions.
- 		Transportation – sensors for traffic monitoring.
- 		Battlefield – sensors attached to soldiers, vehicles or 	scattered throughout important areas.

## The Computing Environment (2)

- USER

- Queries

- Answers

- Real World

- Sensor1

- Sensor2

- SensorN

**SERVER**

**Data Streams**

## The Computing Environment (3)

- Data Streams
- 		- the most natural way to process data in the majority 	of sensor network applications; 	- an append-only collection of tuples that is ordered 	by some increasing key value (often time) [Zdonik,02]
- Data Stream Example:

- Sensor X

***sens_id, time(n), reading***

***sens_id, time(n-1), reading***

***sens_id, time(n-2), reading***

***sens_id, time(n-3), reading***

***sens_id, time(n-4), reading***

## The Problem Definition (1)

- What is the problem?
- 		- a tuple from a particular sensor may be **late**:
- 			due to unsynchronized sensors’ timers;
- 			due to networking issues;
- 		- a tuple may arrive on time, but may be **corrupted**:
- 			due to occurrences of local interferences;
- 			due to exhaust of power at the sensor;
- 		- a tuple may be **lost**:
- 			due to occurrences of local interferences;
- 			due to exhaust of power at the sensor;
- 	 		due to networking issues;

## The Problem Definition (2)

- Why is it a problem?

- 	**The data gathered by the sensors is used by the queries running at the server.**
** **
**	****It can be expected that most of the queries are continuous, i.e. they are evaluated each time a new round of sensor readings arrives at the server. **

## The Problem Definition (3)

- Why is it a problem?

- 	**- In the case of ****a missing or corrupted tuple****, ****	****some ****	****queries cannot be executed;**
**	****- In the case of ****a late tuple****, the result of some ****	****queries will be delayed.**

## Possible Approaches (1)

- Possible Approaches
- 	Ignore	Ask sensor 	    2 or		Estimate the
- 		              again 	        more sensors 	missing value
- 			Averaging	        	      Use existing
- 			techniques	 	relations between
- 						        sensors
- 				**CARMA Approach**

## Possible Approaches (2)

- Combining Association Rule Mining with Average window size (CARMA)
- Use association rule mining to generate a set of sensors that are related to the sensor with the missing value (MS). The values of the related sensors in the current round will contribute with different weights towards the estimated missing value.
- If no related sensors can be found, use an averaging technique to estimate the missing value.

## Overview of Association Rules (1)

- Apriori Algorithm [Agrawal 94] - steps required:
- Find all frequent 1-itemsets: 	at  least minSup% transactions in D contain the item 	(milk, bread, etc.)
- Find all frequent 2-itemsets: 	at  least minSup% transactions in D contain the 2 items
- 		(milk and bread, milk and jam, etc.)
- Find all frequent 3,4...- itemsets, until no larger frequent 	itemset can be generated – the performance bottleneck
- Having all frequent itemsets, generate all association rulesthat satisfy both minSup and minConf.

## The DSARM Framework (1)

- A standard association rule mining technique (e.g. Apriori) cannot be directly applied in a data stream environment:
- 		 - The data to be mined is updated very frequently, 	all the steps are performed for every round with a  	missing value - **poor time performance**;
- 		- The data to be mined in a sensor network 	environment is of a di**fferent nature** from basket 	data.

## Differences between basket and sensor data

| Round Number | Sensor 1 | Sensor 2 | Sensor 3 | Sensor 4 | Sensor 5 |
| --- | --- | --- | --- | --- | --- |
| 1 | Light | Light | Heavy | Light | Light |
| 2 | Light | Light | Moderate | Moderate | Congestion |
| 3 | Heavy | Light | Light | Moderate | Heavy |

- Sensor Traffic Data (Quantitative)

| Transaction ID | bread | milk | yogurt | jam | butter |
| --- | --- | --- | --- | --- | --- |
| 1 | Y | Y | Y | N | N |
| 2 | Y | N | N | Y | Y |
| 3 | Y | Y | N | N | N |

- Basket Data (Boolean)

## The DSARM Framework (2)

- Consider itemsets and association rules always w.r.t. a particular sensor state (sensor value).
- Store the sensor data in a form that will facilitate association rule mining.
- Generate only the association rules that are useful in a particular situation.
- 						_[Formal Definition](slide56.xml)_

## The DSARM Framework (3)

**Apriori Framework****	****        DSARM Framework**

- Find only the **rules between pairs of sensors, in which the MS is a consequent, w.r.t. a particular state**, satisfying both *minSup* and *minConf*

- Find **all valid rules**, satisfying both *minSup* and *minConf*

- a

- c

- a

- b

## DSARM Framework (4)

- The effects of the proposed modifications:

-   **Faster discovery of the association rules – only the 1- and 2- frequent itemsets are generated (avoiding the performance bottleneck for generating 3+ frequent itemsets) ******** faster estimation of the missing value;**

**  ****Data structures containing the metadata (in form of counters) about the 1- and 2- frequent itemsets are memory space feasible ******** faster estimation of the missing value;**

## DSARM Framework (4)

- The effects of the proposed modifications:

- 	**Considering the association rules only w.r.t. a given state leads to a better accuracy of the estimation;**

## DSARM Framework (4)

- The effects of the proposed modifications:

- 	**The calculated *****actSup***** and *****actConf***** of the association rules cannot be used for determining the weight with which each related sensor will contribute towards the estimated missing value. **_[(why?)](slide54.xml)_
**Instead, to determine the weight with which each related sensor S****i ****will contribute towards the estimated value of MS, use the distance in the history of the {S****i****, MS} pair.**

## The CARMA Approach (1)

- 		The CARMA Approach is an implementation
- of the DSARM Framework + using an averaging
- technique to estimate the missing value in the cases
- association rule mining cannot produce an estimation.
- 		The CARMA Approach is a combination of:
- 	- *the Buffer*, *the Cube*, and *the Counter* – data structures to store information received by the sensors;
- 	- *checkBuffer()*, *update()*, and *estimateValue()* algorithms that use the data in the structures.

## The CARMA Approach (2)

*The Buffer*
- _Purpose:_ 	To store the readings from the current round.
- 	Implemented as an array of size equal to the number of
- 	sensors in the network.

| 1 | 2 | 2 | 2 | 3 |
| --- | --- | --- | --- | --- |

- S0

- S1

- S2

- S3

- S4

## The CARMA Approach (3)

*The Cube*
- _Purpose:_  	To keep track of all 1- and 2- itemsets 			observed in the last *w *rounds.
- 	Implemented as a 2D array of DLLs. The information from the newest round is stored at the front of the Cube and the information from the oldest round is stored at the back of the Cube.

- S0

- S0

- S1

- S1

- S2

- S2

- S3

- S3

- S4

- S4

- Time

- oldest

- newest

- -1

- 3

- -1

- -1

- -1

- -1

- 2

- 2

- 2

- -1

- -1

- -1

- -1

- -1

- -1

- -1

- -1

- -1

- 1

- 2

- 2

- 2

- 2

- 2

- 2

## The CARMA Approach (4)

*The Counter*
- _Purpose:_  	To speed up the estimation, counters for all 			possible 1- and 2-itemsets are maintained in 			the Counter.
- 	Implemented as a 3D array. The observed number of 1- and 2-itemsets for a particular state of sensor readings is stored in the corresponding (to the sensors and the state) node in the Counter.

- S0

- S0

- S1

- S1

- S2

- S2

- S3

- S3

- S4

- S4

- 0

- 3

- 2

- 0

- 0

- 1

- 2

- 1

- 2

- 0

- 0

- 0

- 1

- 2

- 1

- 0

- 1

- 0

- 1

- 2

- 2

- 1

- 4

- 2

- 2

- 1

- 2

- 3

- 4

## The CARMA Approach (5)

- The *checkBuffer()* Algorithm
- _Purpose:_  	To check for missing values in the current 			round stored in the Buffer and to initiate a 			proper action as a result of this check.
***1.checkBuffer() {***
***2.******	******while (true) { //repeat indefinitely***
***3.******	******	******while (the time window for the current session with the sensors is still open) {***
***4.******	******	******	******listen to sensors and record their readings;***
***	******	******}***
***5.******	******	******if (a missing data is detected in the Buffer) {***
***6.******	******	******	******call estimateValue();  // to estimate and also to invoke update()***
***	******	******}***
***7.******	******	******else {***
***8.******	******	******	******send OK signal to Application Queries to proceed;***
***9.******	******	******	******call update();***
***	******	******}***
***10.******	******	******clear the Buffer  //set each cell to -1;***
***	******}***
***}******	****	*

## The CARMA Approach (5)

- The *update()* Algorithm
- _Purpose:_  	To update both the Cube and the Counter 			with the data in the current round, which is 			stored in the Buffer.
***update() {***
***	******for (each sensor Si, i = 0 .. numSens, reporting state s) { //i.e. form a 1-itemset w.r.t s***
***	******	******add Cube[Si][Si].slice[0], data field = s; //add new node at the head of a DLL***
***	******	******discard Cube[Si][Si].slice[last]; ***
***	******	******update Counter[Si][Si].state[all affected states];***
***	******	******for (each sensor Sj, j = i+1..numSens) { //add new node at the head of a DLL ***
***	******	******	******add Cube[Si][Sj].slice[0];***
***	******	******	******if (Sj reports the same state as Si) { //i.e. form a 2-itemset w.r.t. s***
***	******	******	******	****** ******the data field in the new node = s;***
***	******	******	******}***
***	******	******	******else { //Si and Sj do not report the same state***
***	******	******	******	******the data field in the new node = -1; ******	******	******	******	******}***
***	******	******	******discard Cube[Si][Sj].slice[last];***
***	******	******	******update Counter[Si][Sj].state[all affected states];***
***	******	******}***
***	******}***
***}******	******	******	******	******	******	******	******         ***_*[Go to an example](slide29.xml)*_

## The CARMA Approach (6)

- The *estimateValue()* Algorithm
- _Purpose:_  	To estimate a missing sensor reading, using
- 			the data in the Counter, the Cube, and the Buffer.
***estimateValue(MS) {***
***     ******determine all eligible states “e” for the MS; //compare actSup with minSup for every possible state***
***     ******	******	******	******	******	******	******	******	***_*[Go to an example](slide30.xml)*_
***     ******for (every eligible state e) {***
***        ******create an empty StateSet_e;******	******	******	******	******	***
***     ******}***
***    ***
***    ******distribute all sensors without missing values in the current round to ***
***    ******a proper StateSet_e based on their states recorded in the Buffer;******	****** ***_*[Go to the example](slide35.xml)*_
***    ***
***    ******for (every StateSet_e) { // determine the eligible sensors***
***        ******for (every sensor Si) {***
***            ******check if a rule Si************ MS | e is valid;  //compare actSup with minSup and actConf with minConf***
***             ******if (not valid) {***
***	******           ******delete Si from the StateSet_e;***
***	******     ******}***
***        ******}***
***    ******} ******	******	******	******	******	******	******	******	****** ***_*[Go to the example](slide36.xml)*_

## The CARMA Approach (7)

- The *estimateValue()* Algorithm (cont.)
-    ***	******......***
***       ******// At this point we have generated all the eligible sensors, ***
***	******// grouped in the corresponding StateSet_e collections***
***	******// Determine the weight with which each eligible sensor will contribute towards the ***
***	******// missing value being “e” and accumulate this weight in StateValue_e and totalWeight***
***	******// variables***
***	******for (every non-empty StateSet_e) {***
***	******    ******for (every sensor Si) {***
***	******         ******weightSi = number of occurrences in which Si and MS have reported the same state***
***	******	******              ******divided by the window size;   // a distance in the history of the pair {Si, MS}***
***	******         ******StateValue_e = StateValue_e + weightSi;***
***                ******totalWeight = totalWeight + weightSi;***
***	******     ******}***
***        ******}******	******	******	******	******	******	****** ***_*[Go to the example](slide38.xml)*_
***	***
***       ******// calculate the estimated value***
***	******missingValue = (************ StateValue_e * e) / totalWeight,  the sum is for every existing state set e***
***} //end of estimateValue()***
***	******	***
- _[Experimental Results](slide40.xml)_***	******                                                       ***_*[Go to the example](slide39.xml)*_

## The Buffer:         S0   S1   S2    S3   S4       (the update() Algorithm					        	        for the very first round)               Cube.slice[0]: Before	               Cube.slice[0]: After

| S4 | 0 | 0 | 0 | 0 | 0 |
| --- | --- | --- | --- | --- | --- |
| S3 | 0 | 0 | 0 | 0 | 0 |
| S2 | 0 | 0 | 0 | 0 | 0 |
| S1 | 0 | 0 | 0 | 0 | 0 |
| S0 | 0 | 0 | 0 | 0 | 0 |
|  | S0 | S1 | S2 | S3 | S4 |

| S4 | - 1 | - 1 | - 1 | - 1 | 3 |
| --- | --- | --- | --- | --- | --- |
| S3 | 2 | - 1 | - 1 | 2 | - 1 |
| S2 | - 1 | 1 | 1 | - 1 | - 1 |
| S1 | - 1 | 1 | 1 | - 1 | - 1 |
| S0 | 2 | - 1 | - 1 | 2 | - 1 |
|  | S0 | S1 | S2 | S3 | S4 |

-                Counter.state[2]: Before	  Counter.state[2]: After	       				_[Go Back](slide26.xml)_

| S4 | - 1 | - 1 | - 1 | - 1 | - 1 |
| --- | --- | --- | --- | --- | --- |
| S3 | - 1 | - 1 | - 1 | - 1 | - 1 |
| S2 | - 1 | - 1 | - 1 | - 1 | - 1 |
| S1 | - 1 | - 1 | - 1 | - 1 | - 1 |
| S0 | - 1 | - 1 | - 1 | - 1 | - 1 |
|  | S0 | S1 | S2 | S3 | S4 |

| S4 | 0 | 0 | 0 | 0 | 0 |
| --- | --- | --- | --- | --- | --- |
| S3 | 1 | 0 | 0 | 1 | 0 |
| S2 | 0 | 0 | 0 | 0 | 0 |
| S1 | 0 | 0 | 0 | 0 | 0 |
| S0 | 1 | 0 | 0 | 1 | 0 |
|  | S0 | S1 | S2 | S3 | S4 |

## An example of the estimateValue() Algorithm

- An example of the *estimateValue()* Algorithm

- Assume:
- 	- minimum support (minSup) = 25%
- 	- minimum confidence (minConf) = 25%
- 	- sliding window size = 5
- The Buffer:	 S0   S1   S2   S3   S4
- i.e. missing value for S1.

**1**

**2**

**-1**

**1**

**2**

## An example of the estimateValue() AlgorithmStep 1. Determine all eligible states for MS

- _Checking for state 1:_
- actSup of S1 | 1 =
- 3 / 5 = 60% > minSup = 25%
**	****=> **	**State 1 is an eligible ****	****state for S1**

| S4 | 0 | 0 | 0 | 0 | 0 |
| --- | --- | --- | --- | --- | --- |
| S3 | 1 | 1 | 1 | 1 | 0 |
| S2 | 2 | 3 | 3 | 1 | 0 |
| S1 | 2 | 3 | 3 | 1 | 0 |
| S0 | 3 | 2 | 2 | 1 | 0 |
|  | S0 | S1 | S2 | S3 | S4 |
|  |  |  |  |  |  |
|  | Counter.state[1] |  |  |  |  |

## An example of the estimateValue() AlgorithmStep 1. Determine all eligible states for MS

- _Checking for state 2:_
- actSup of S1 | 2 =
- 2 / 5 = 40% > minSup = 25%
- 	**=> ****	****State 2 is an eligible ****	****state for S1**

| S4 | 0 | 1 | 1 | 2 | 2 |
| --- | --- | --- | --- | --- | --- |
| S3 | 1 | 2 | 2 | 4 | 2 |
| S2 | 0 | 2 | 2 | 2 | 1 |
| S1 | 0 | 2 | 2 | 2 | 1 |
| S0 | 1 | 0 | 0 | 1 | 0 |
|  | S0 | S1 | S2 | S3 | S4 |
|  |  |  |  |  |  |
|  | Counter.state[2] |  |  |  |  |

## An example of the estimateValue() AlgorithmStep 1. Determine all eligible states for MS

- _Checking for state 3:_
- actSup of S1 | 3 =
- 0 / 5 = 0% < minSup = 25%
- 	**=>****	****State 3 is not an ****	****eligible state for S1**

| S4 | 0 | 0 | 0 | 0 | 2 |
| --- | --- | --- | --- | --- | --- |
| S3 | 0 | 0 | 0 | 0 | 0 |
| S2 | 0 | 0 | 0 | 0 | 0 |
| S1 | 0 | 0 | 0 | 0 | 0 |
| S0 | 0 | 0 | 0 | 0 | 0 |
|  | S0 | S1 | S2 | S3 | S4 |
|  |  |  |  |  |  |
|  | Counter.state[3] |  |  |  |  |

## An example of the estimateValue() AlgorithmStep 1. Determine all eligible states for MS

- _Checking for state 4:_
- actSup of S1 | 4 =
- 0 / 5 = 0% < minSup = 25%
- 	**=>****	****State 4 is not an ****	****eligible state for S1**
**	****	****           **_[Back to the algorithm](slide27.xml)_

| S4 | 0 | 0 | 0 | 0 | 1 |
| --- | --- | --- | --- | --- | --- |
| S3 | 0 | 0 | 0 | 0 | 0 |
| S2 | 0 | 0 | 0 | 0 | 0 |
| S1 | 0 | 0 | 0 | 0 | 0 |
| S0 | 1 | 0 | 0 | 0 | 0 |
|  | S0 | S1 | S2 | S3 | S4 |
|  |  |  |  |  |  |
|  | Counter.state[4] |  |  |  |  |

## An example of the estimateValue() AlgorithmStep 2. Distribute the sensor in the proper StateSets

- An example of the *estimateValue()* AlgorithmStep 2. Distribute the sensor in the proper StateSets

- Created StateSets are: StateSet_1 and StateSet_2
- The Buffer:
-       S0     S1    S2     S3    S4

- StateSet_1 = {S0, S2}
- StateSet_2 = {S3, S4}
**	****	****           **_[Back to the algorithm](slide27.xml)_

**1**

**2**

**-1**

**1**

**2**

## An example of the estimateValue() AlgorithmStep 3. Determine all eligible sensors

- Checking StateSet_1:
- S0: actSup of S0  S1 | 1 =
- 	2/5=40% > minSup=25%
- 	actConf of S0  S1 | 1 =
- 	2/3=67% > minConf=25%
- 	**=>** S0 is an eligible sensor
- S2: actSup of S2  S1 | 1 =
- 	3/5=60% > minSup=25%
- 	actConf of S2  S1 | 1 =
- 	3/3=100% > minConf=25%
- 	=> S2 is an eligible sensor

| S4 | 0 | 0 | 0 | 0 | 0 |
| --- | --- | --- | --- | --- | --- |
| S3 | 1 | 1 | 1 | 1 | 0 |
| S2 | 2 | 3 | 3 | 1 | 0 |
| S1 | 2 | 3 | 3 | 1 | 0 |
| S0 | 3 | 2 | 2 | 1 | 0 |
|  | S0 | S1 | S2 | S3 | S4 |
|  |  |  |  |  |  |
|  | Counter.state[1] |  |  |  |  |

## An example of the estimateValue() AlgorithmStep 3. Determine all eligible sensors

- Checking StateSet_2:
- S3: actSup of S3  S1 | 2 =
- 	2/5=40% > minSup=25%
- 	actConf of S3  S1 | 2 =
- 	2/4=50% > minConf=25%
- 	=> S3 is an eligible sensor
- S4: actSup of S4  S1 | 2 =
- 	1/5=20% < minSup=25%
- 	=> S4 is not an eligible sensor,
- 		delete S4 from StateSet_2
**	****	****          **
**	****	****      **
**	****	****           **_[Back to the algorithm](slide27.xml)_

| S4 | 0 | 1 | 1 | 2 | 2 |
| --- | --- | --- | --- | --- | --- |
| S3 | 1 | 2 | 2 | 4 | 2 |
| S2 | 0 | 2 | 2 | 2 | 1 |
| S1 | 0 | 2 | 2 | 2 | 1 |
| S0 | 1 | 0 | 0 | 1 | 0 |
|  | S0 | S1 | S2 | S3 | S4 |
|  |  |  |  |  |  |
|  | Counter.state[2] |  |  |  |  |

## An example of the estimateValue() AlgorithmStep 4. Determine the weights for all eligible sensorsEligible sensors: S0 and S2 for state 1, S3 for state 2

- An example of the *estimateValue()* AlgorithmStep 4. Determine the weights for all eligible sensorsEligible sensors: S0 and S2 for state 1, S3 for state 2

| Cube[S0][S0].slice[all] | 1 | 1 | 4 | 2 | 1 |
| --- | --- | --- | --- | --- | --- |
| Cube[S1][S1].slice[all] | 2 | 1 | 2 | 1 | 1 |

| Cube[S3][S3].slice[all] | 2 | 1 | 2 | 2 | 2 |
| --- | --- | --- | --- | --- | --- |
| Cube[S1][S1].slice[all] | 2 | 1 | 2 | 1 | 1 |

**StateValue_1** =
- 2/5 (from {S0, S1}) +
- 5/5 (from {S2, S1}) = **1.4**
**StateValue_2** =
- 3/5 (from {S3, S1}) = **0.6**
**TotalWeight **= 1.4 + 0.6 =** 2**
**                           **_[Back to the algorithm](slide28.xml)_

| Cube[S2][S2].slice[all] | 2 | 1 | 2 | 1 | 1 |
| --- | --- | --- | --- | --- | --- |
| Cube[S1][S1].slice[all] | 2 | 1 | 2 | 1 | 1 |

- newest

- oldest

## An example of the estimateValue() AlgorithmStep 5. Calculate the missing value

***missingValue ******	******= (************ StateValue_e * e) / totalWeight =***
***	******	******	******=   (1.4 * 1 + 0.6 * 2) / 2 = 2.6 / 2 = 1.3***
***	***
***The state of the S1 is thus estimated ***
***	******to be equal to 1.***** **
**	****	****	****	****	****	****          **_[Back to the algorithm](slide28.xml)_

## Simulation Results (1)The Simulation Model

- A collection of 108 sensor nodes deployed on city streets. The sensors collect and report the number of the vehicles detected for a given time interval.

-         sensor nodes
- 		server
- 	The _[data](slide63.xml)__ is obtained from [AFIDA 03]._

- A

- B

## Simulation Results (2)The Simulation Model

- The Dynamic Parameters:
- 	- sliding window size (winSize): 6, 18, 30, 42
- 	- minimum support, minimum confidence (MSMC): 0%, 1%, 2%, 4%, 7%, 10%
- 	- number of possible sensor reading states (numStates = number of subsets: 10, 20, 40, 80;
- 	- error rate of the wireless communication link (p): 0.1%, 1%, 10%

## Simulation Results (3)Simulation Experiments

- Performance Measurements:

-  **The achieved ****accuracy**** of the estimated value.**
** ****The total ****main memory access time**** to process a   **
**   ****round of sensors readings (TMMAT).**
** ****The required ****memory space****.**
** ****The overall ****power consumption**** by the sensor  **
**   ****nodes (OPC).**
** ****The percentage of cases in which the **
**   ****estimateValue() algorithm cannot produce an **
**   ****estimation alone.**
**  **

## Simulation Results (4)Evaluation of the Accuracy for different approaches

- Simulation Results (4)Evaluation of the Accuracy for different approaches

- To evaluate the accuracy of the estimation we use the
- 		Normalized Root Mean Square Error (_[RMSE](slide53.xml)_)
- where:
- 	- *Xa**i* and *Xe**i* are the actual value and the estimated 	value, respectively;
- 	- *#estimations* is the number of estimations performed in a 	simulation run;
- 	- *#states* is the number of subsets in which the actual sensor	readings are distributed.

## Simulation Results (5) Evaluation of the Accuracy for different approaches

- 		Compared are 4 different approaches for
- estimating a missing value:
- The Previous Value (PV) approach
- The Average Round (AR) approach
- The Average Window Size (AWS) approach
- The CARMA approach:
-      a combination of the estimateValue() algorithm +
-      the AWS approach for the cases in which association rule
-      mining cannot generate an estimation of a missing value

## Simulation Results (6) Evaluation of the Accuracy for different approaches

- Simulation Results (6) Evaluation of the Accuracy for different approaches

## Simulation Results (7)Evaluation of CARMA TMMAT for different error rates p

- Simulation Results (7)Evaluation of CARMA TMMAT for different error rates *p*

## Simulation Results (8)Evaluation of CARMA Memory Space Requirements

| numSens | winSize | #states | CARMA_space (MB) |
| --- | --- | --- | --- |
| 108 | 6 | 10 | 1 |
| 108 | 6 | 20 | 2 |
| 108 | 6 | 40 | 3 |
| 108 | 6 | 80 | 4 |
| 108 | 18 | 10 | 3 |
| 108 | 18 | 20 | 3 |
| 108 | 18 | 40 | 4 |
| 108 | 18 | 80 | 6 |
| 108 | 30 | 10 | 4 |
| 108 | 30 | 20 | 5 |
| 108 | 30 | 40 | 6 |
| 108 | 30 | 80 | 8 |
| 108 | 42 | 10 | 6 |
| 108 | 42 | 20 | 7 |
| 108 | 42 | 40 | 7 |
| 108 | 42 | 80 | 9 |

## Simulation Results (9)Evaluation of the OPC for different error rates p 

- Simulation Results (9)Evaluation of the OPC for different error rates *p*

- Compared are the CARMA and MultiSend _[Approaches](slide55.xml)_

## Conclusions (1)

- 	This research has proposed an approach called **CARMA**(**C**ombining **A**ssociation **R**ule **M**ining
- with **A**verage window size)for estimating missing values in related data streams.

-   **The CARMA approach achieves the best accuracy  **
**   ****of the estimated missing values compared to **
**   ****alternative approaches (PV, AR, AWS).**
** ****The response time for CARMA is more than the **
**   ****response time for AWS, but will be acceptable for **
**   ****a wide range of applications.**

## Conclusions (2)

-  **The memory space required by CARMA is  **
**   ****feasible.**
**CARMA provides a power-conscious use of a sensor network.**

## Future Work

- Incorporate the Temporal and Spatial Characteristics of NASA data into the mining and data estimation algorithms.
- Reduce space required by the CARMA approach.
- Enhance the DSARM framework to consider multiple failure of co-related sensors.
- Incorporate a relevance function in the estimateValue() algorithm to account for the “freshness” of the data.
- Examine other sensor network architectures: distributed and mobile.
- Implement the algorithms and conduct experiments using NASA data.

**Thank You!**

## Distribution of the Error in the Estimation

- _[Back](slide43.xml)_

## Why actSup and actConf cannot be used?

- Discovered by DSARM are:
- A  C | stateA, actSup = s1, actConf = c1
- B  C | stateA, actSup = s2, actConf = c2
- There may exist a rule (not discovered by DSARM)
- A, B  C | stateA, actSup = s3, actConf = c3
- s3 may != s1 and/or s2
- c3 may != c1 and/or c2				_[Back](slide20.xml)_

## Overall Power Consumption (OPC)

*OPC = numRounds **
*(numSens * currentConsumptionSend * timeSend +*
*+  numSens * currentConsuptionListen * timeListen +*
*+  numMissSens* currentConsuptionRecv * timeRecv +*
*+  numMissSens* currentConsuptionSend * timeSend)*
*	**	**	**	**	**	**	*	_[Back](slide48.xml)_

## The DSARM Framework (3)

- The DSARM Framework:

**Let *****I***** = {A, B,.... , X, Y, N} be a set of sensors. Let the size of the sliding window be *****w***** rounds. Given is the set *****D***** of last *****w***** rounds of reported sensor states, where each round *****T***** consists of reported states for the sensors in *****I*****. **

## The DSARM Framework (3)

- The DSARM Framework:

**Find all ****association rules of the form *****X***** ******** *****Y | s*****, where: **
***	******- s***** is a possible sensor state out of all possible sensor states; **
***	******- X***** and *****Y***** are subsets of size one of *****I***** (i.e. each *****X***** and *****Y***** contains only one item of***** I*****), *****Y *****is MS, and *****X***** ******** *****Y***** = ********.**

## The DSARM Framework (3)

- The DSARM Framework:

**	****An ****association rule *****X***** ******** *****Y***** | *****s***** is said to hold in the set of the currently stored rounds *****D***** with: **
**  ****- confidence***** actConf***** if *****actConf *****% of the rounds that report *****s***** for *****X***** also report *****s***** for *****Y*****;**
**  ****- support *****actSup***** if *****actSup***** % of the currently stored rounds in *****D***** report *****s***** for both *****X***** and *****Y*****. **

## The DSARM Framework (3)

- The DSARM Framework:

**	****The task of mining association rules is to find ****all the association rules between pairs of sensors w.r.t. all possible sensor states**** which satisfy both the user-defined minimum support *****minSup***** and minimum confidence *****minConf*****.**

## The DSARM Framework (4)

- The DSARM Framework - steps required:
- Find all frequent 1-itemsets: 	at  least minSup% transactions in D contain the sensor 	w.r.t. a given state
- Find all frequent 2-itemsets: 	at  least minSup% transactions in D contain the 2 	sensors reporting the same state
- Having all 1- and 2-frequent itemsets, generate all association rules between pairs of sensors, in which the MS is a consequent, w.r.t. a given state, satisfying minSup and minConf
- 								_[Back](slide16.xml)_

## Effect of MSMC on Accuracy of Estimation

- _[Back](slide47.xml)_

## A Sample of the Input Data [TX DOT, Austin, Texas – January, 2000]

|   | S0 | S1 | S2 | S3 | S4 | S5 | S6 | S7 | S8 | S9 | S10 |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| 0:00 | 107 | 97 | 37 | 42 | 0 | 1 | 38 | 19 | 94 | 331 | 380 |
| 0:15 | 123 | 204 | 65 | 42 | 0 | 0 | 9 | 9 | 63 | 520 | 756 |
| 0:30 | 135 | 168 | 61 | 39 | 1 | 0 | 9 | 6 | 71 | 535 | 744 |
| 0:45 | 93 | 128 | 39 | 20 | 1 | 0 | 7 | 8 | 53 | 352 | 454 |
| 1:00 | 61 | 75 | 19 | 12 | 0 | 0 | 8 | 7 | 37 | 232 |   |
| 1:15 | 49 | 54 | 13 | 10 | 1 | 0 | 6 | 6 | 41 | 151 | 191 |
| 1:30 | 59 | 58 | 23 | 10 | 0 | 1 | 8 | 10 | 43 | 172 | 159 |
| 1:45 | 80 | 81 | 46 | 18 | 1 | 1 | 9 | 16 | 56 | 250 | 188 |
| 2:00 | 86 | 82 | 99 | 73 | 1 | 1 | 16 | 25 | 91 | 293 | 225 |
| 2:15 | 96 | 84 | 152 | 168 | 4 | 1 | 31 | 48 | 132 | 339 | 314 |
| 2:30 | 115 | 137 | 246 | 176 | 4 | 3 |   | 62 | 191 | 477 | 459 |
| 2:45 | 156 | 170 | 259 | 182 | 7 | 4 |   | 90 | 271 | 637 | 674 |
| 3:00 | 194 | 230 | 258 | 222 | 6 | 6 |   | 111 | 337 | 821 | 898 |
| 3:15 | 242 | 249 | 226 | 179 | 4 | 4 |   | 118 | 419 | 989 | 1106 |
| 3:30 | 263 | 268 | 220 | 158 | 5 | 4 |   | 145 | 417 | 1121 | 1227 |
| 3:45 | 282 | 295 | 237 | 164 | 6 | 4 |   | 132 | 374 | 1051 | 1218 |
| 4:00 | 261 | 246 | 236 | 165 | 5 | 5 |   | 126 | 363 | 900 | 1022 |
| 4:15 | 256 | 282 | 256 | 177 | 6 | 2 |   | 109 | 334 | 930 | 946 |
| 4:30 | 225 | 248 | 173 | 137 | 3 | 3 | 94 | 67 | 296 | 890 | 901 |
| 4:45 | 242 | 243 | 147 | 151 | 2 | 3 | 75 | 34 | 284 | 1095 | 968 |
| 5:00 | 193 | 212 | 96 | 105 | 2 | 3 | 54 | 25 | 236 | 659 | 803 |
| 5:15 | 141 | 158 | 82 | 80 | 1 | 1 | 38 | 28 | 190 | 535 | 643 |
| 5:30 | 128 | 140 | 58 | 74 | 1 | 1 | 34 | 18 | 136 | 420 | 521 |
| 5:45 | 102 | 112 | 33 | 34 | 1 | 1 | 25 | 21 | 105 | 339 | 800 |
| 6:00 | 68 | 79 | 26 | 29 | 1 | 1 | 18 | 11 | 102 | 210 | 248 |
| 6:15 | 41 | 56 | 11 | 21 | 0 | 1 | 20 | 5 | 42 | 125 | 151 |
| 6:30 | 26 | 29 | 9 | 6 | 0 | 1 | 15 | 5 | 31 | 95 | 117 |
| 6:45 | 24 | 27 | 3 | 6 | 1 | 0 | 14 | 8 | 20 | 76 | 103 |
| 7:00 | 26 | 25 | 11 | 4 | 0 | 1 | 14 | 6 | 28 | 103 | 116 |
| 7:15 | 45 | 40 | 13 | 7 | 1 | 0 | 24 | 11 | 56 | 221 | 268 |
| 7:30 | 144 | 146 | 28 | 15 | 3 | 1 | 24 | 14 | 130 | 722 | 939 |
| 7:45 | 306 | 351 | 72 | 66 | 2 | 2 | 31 | 24 | 248 | 1617 | 1758 |
| 8:00 | 449 | 453 | 168 | 154 | 3 | 4 | 38 | 48 | 289 | 1969 | 1715 |

## A Sample of the Input Data (2)

|   | S0 | S1 | S2 | S3 | S4 | S5 | S6 | S7 | S8 | S9 | S10 |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| 0:00 | 107 | 97 | 37 | 42 | 0 | 1 | 38 | 19 | 94 | 331 | 380 |
| 0:15 | 123 | 204 | 65 | 42 | 0 | 0 | 9 | 9 | 63 | 520 | 756 |
| 0:30 | 135 | 168 | 61 | 39 | 1 | 0 | 9 | 6 | 71 | 535 | 744 |
| 0:45 | 93 | 128 | 39 | 20 | 1 | 0 | 7 | 8 | 53 | 352 | 454 |
| 1:00 | 61 | 75 | 19 | 12 | 0 | 0 | 8 | 7 | 37 | 232 |   |
| 1:15 | 49 | 54 | 13 | 10 | 1 | 0 | 6 | 6 | 41 | 151 | 191 |
| 1:30 | 59 | 58 | 23 | 10 | 0 | 1 | 8 | 10 | 43 | 172 | 159 |
| 1:45 | 80 | 81 | 46 | 18 | 1 | 1 | 9 | 16 | 56 | 250 | 188 |
| 2:00 | 86 | 82 | 99 | 73 | 1 | 1 | 16 | 25 | 91 | 293 | 225 |
| 2:15 | 96 | 84 | 152 | 168 | 4 | 1 | 31 | 48 | 132 | 339 | 314 |
| 2:30 | 115 | 137 | 246 | 176 | 4 | 3 |   | 62 | 191 | 477 | 459 |
| 2:45 | 156 | 170 | 259 | 182 | 7 | 4 |   | 90 | 271 | 637 | 674 |
| 3:00 | 194 | 230 | 258 | 222 | 6 | 6 |   | 111 | 337 | 821 | 898 |
| 3:15 | 242 | 249 | 226 | 179 | 4 | 4 |   | 118 | 419 | 989 | 1106 |
| 3:30 | 263 | 268 | 220 | 158 | 5 | 4 |   | 145 | 417 | 1121 | 1227 |
| 3:45 | 282 | 295 | 237 | 164 | 6 | 4 |   | 132 | 374 | 1051 | 1218 |
| 4:00 | 261 | 246 | 236 | 165 | 5 | 5 |   | 126 | 363 | 900 | 1022 |
| 4:15 | 256 | 282 | 256 | 177 | 6 | 2 |   | 109 | 334 | 930 | 946 |
| 4:30 | 225 | 248 | 173 | 137 | 3 | 3 | 94 | 67 | 296 | 890 | 901 |
| 4:45 | 242 | 243 | 147 | 151 | 2 | 3 | 75 | 34 | 284 | 1095 | 968 |
| 5:00 | 193 | 212 | 96 | 105 | 2 | 3 | 54 | 25 | 236 | 659 | 803 |
| 5:15 | 141 | 158 | 82 | 80 | 1 | 1 | 38 | 28 | 190 | 535 | 643 |
| 5:30 | 128 | 140 | 58 | 74 | 1 | 1 | 34 | 18 | 136 | 420 | 521 |
| 5:45 | 102 | 112 | 33 | 34 | 1 | 1 | 25 | 21 | 105 | 339 | 800 |
| 6:00 | 68 | 79 | 26 | 29 | 1 | 1 | 18 | 11 | 102 | 210 | 248 |
| 6:15 | 41 | 56 | 11 | 21 | 0 | 1 | 20 | 5 | 42 | 125 | 151 |
| 6:30 | 26 | 29 | 9 | 6 | 0 | 1 | 15 | 5 | 31 | 95 | 117 |
| 6:45 | 24 | 27 | 3 | 6 | 1 | 0 | 14 | 8 | 20 | 76 | 103 |
| 7:00 | 26 | 25 | 11 | 4 | 0 | 1 | 14 | 6 | 28 | 103 | 116 |
| 7:15 | 45 | 40 | 13 | 7 | 1 | 0 | 24 | 11 | 56 | 221 | 268 |
| 7:30 | 144 | 146 | 28 | 15 | 3 | 1 | 24 | 14 | 130 | 722 | 939 |
| 7:45 | 306 | 351 | 72 | 66 | 2 | 2 | 31 | 24 | 248 | 1617 | 1758 |
| 8:00 | 449 | 453 | 168 | 154 | 3 | 4 | 38 | 48 | 289 | 1969 | 1715 |

## A Sample of the Input Data (3) – 108 locations are left

|   | S0 | S1 | S2 | S3 | S4 | S5 | S6 | S7 | S8 | S9 | S10 |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| 0:00 | 107 | 97 | 37 | 42 | 0 | 1 | 38 | 19 | 94 | 331 | 380 |
| 0:15 | 123 | 204 | 65 | 42 | 0 | 0 | 9 | 9 | 63 | 520 | 756 |
| 0:30 | 135 | 168 | 61 | 39 | 1 | 0 | 9 | 6 | 71 | 535 | 744 |
| 0:45 | 93 | 128 | 39 | 20 | 1 | 0 | 7 | 8 | 53 | 352 | 454 |
| 1:00 | 61 | 75 | 19 | 12 | 0 | 0 | 8 | 7 | 37 | 232 | 270 |
| 1:15 | 49 | 54 | 13 | 10 | 1 | 0 | 6 | 6 | 41 | 151 | 191 |
| 1:30 | 59 | 58 | 23 | 10 | 0 | 1 | 8 | 10 | 43 | 172 | 159 |
| 1:45 | 80 | 81 | 46 | 18 | 1 | 1 | 9 | 16 | 56 | 250 | 188 |
| 2:00 | 86 | 82 | 99 | 73 | 1 | 1 | 16 | 25 | 91 | 293 | 225 |
| 2:15 | 96 | 84 | 152 | 168 | 4 | 1 | 31 | 48 | 132 | 339 | 314 |
| 2:30 | 115 | 137 | 246 | 176 | 4 | 3 | 43 | 62 | 191 | 477 | 459 |
| 2:45 | 156 | 170 | 259 | 182 | 7 | 4 | 54 | 90 | 271 | 637 | 674 |
| 3:00 | 194 | 230 | 258 | 222 | 6 | 6 | 83 | 111 | 337 | 821 | 898 |
| 3:15 | 242 | 249 | 226 | 179 | 4 | 4 | 103 | 118 | 419 | 989 | 1106 |
| 3:30 | 263 | 268 | 220 | 158 | 5 | 4 | 122 | 145 | 417 | 1121 | 1227 |
| 3:45 | 282 | 295 | 237 | 164 | 6 | 4 | 131 | 132 | 374 | 1051 | 1218 |
| 4:00 | 261 | 246 | 236 | 165 | 5 | 5 | 130 | 126 | 363 | 900 | 1022 |
| 4:15 | 256 | 282 | 256 | 177 | 6 | 2 | 111 | 109 | 334 | 930 | 946 |
| 4:30 | 225 | 248 | 173 | 137 | 3 | 3 | 94 | 67 | 296 | 890 | 901 |
| 4:45 | 242 | 243 | 147 | 151 | 2 | 3 | 75 | 34 | 284 | 1095 | 968 |
| 5:00 | 193 | 212 | 96 | 105 | 2 | 3 | 54 | 25 | 236 | 659 | 803 |
| 5:15 | 141 | 158 | 82 | 80 | 1 | 1 | 38 | 28 | 190 | 535 | 643 |
| 5:30 | 128 | 140 | 58 | 74 | 1 | 1 | 34 | 18 | 136 | 420 | 521 |
| 5:45 | 102 | 112 | 33 | 34 | 1 | 1 | 25 | 21 | 105 | 339 | 800 |
| 6:00 | 68 | 79 | 26 | 29 | 1 | 1 | 18 | 11 | 102 | 210 | 248 |
| 6:15 | 41 | 56 | 11 | 21 | 0 | 1 | 20 | 5 | 42 | 125 | 151 |
| 6:30 | 26 | 29 | 9 | 6 | 0 | 1 | 15 | 5 | 31 | 95 | 117 |
| 6:45 | 24 | 27 | 3 | 6 | 1 | 0 | 14 | 8 | 20 | 76 | 103 |
| 7:00 | 26 | 25 | 11 | 4 | 0 | 1 | 14 | 6 | 28 | 103 | 116 |
| 7:15 | 45 | 40 | 13 | 7 | 1 | 0 | 24 | 11 | 56 | 221 | 268 |
| 7:30 | 144 | 146 | 28 | 15 | 3 | 1 | 24 | 14 | 130 | 722 | 939 |
| 7:45 | 306 | 351 | 72 | 66 | 2 | 2 | 31 | 24 | 248 | 1617 | 1758 |
| 8:00 | 449 | 453 | 168 | 154 | 3 | 4 | 38 | 48 | 289 | 1969 | 1715 |

## A Sample of the Input Data (3) – 108 locations are left

|   | S0 | S1 | S2 | S3 | S4 | S5 | S6 | S7 | S8 | S9 | S10 |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| 0:00 | 107 | 97 | 37 | 42 | 0 | 1 | 38 | 19 | 94 | 331 | 380 |
| 0:15 | 123 | 204 | 65 | 42 | 0 | 0 | 9 | 9 | 63 | 520 | 756 |
| 0:30 | 135 | 168 | 61 | 39 | 1 | 0 | 9 | 6 | 71 | 535 | 744 |
| 0:45 | 93 | 128 | 39 | 20 | 1 | 0 | 7 | 8 | 53 | 352 | 454 |
| 1:00 | 61 | 75 | 19 | 12 | 0 | 0 | 8 | 7 | 37 | 232 | 270 |
| 1:15 | 49 | 54 | 13 | 10 | 1 | 0 | 6 | 6 | 41 | 151 | 191 |
| 1:30 | 59 | 58 | 23 | 10 | 0 | 1 | 8 | 10 | 43 | 172 | 159 |
| 1:45 | 80 | 81 | 46 | 18 | 1 | 1 | 9 | 16 | 56 | 250 | 188 |
| 2:00 | 86 | 82 | 99 | 73 | 1 | 1 | 16 | 25 | 91 | 293 | 225 |
| 2:15 | 96 | 84 | 152 | 168 | 4 | 1 | 31 | 48 | 132 | 339 | 314 |
| 2:30 | 115 | 137 | 246 | 176 | 4 | 3 | 43 | 62 | 191 | 477 | 459 |
| 2:45 | 156 | 170 | 259 | 182 | 7 | 4 | 54 | 90 | 271 | 637 | 674 |
| 3:00 | 194 | 230 | 258 | 222 | 6 | 6 | 83 | 111 | 337 | 821 | 898 |
| 3:15 | 242 | 249 | 226 | 179 | 4 | 4 | 103 | 118 | 419 | 989 | 1106 |
| 3:30 | 263 | 268 | 220 | 158 | 5 | 4 | 122 | 145 | 417 | 1121 | 1227 |
| 3:45 | 282 | 295 | 237 | 164 | 6 | 4 | 131 | 132 | 374 | 1051 | 1218 |
| 4:00 | 261 | 246 | 236 | 165 | 5 | 5 | 130 | 126 | 363 | 900 | 1022 |
| 4:15 | 256 | 282 | 256 | 177 | 6 | 2 | 111 | 109 | 334 | 930 | 946 |
| 4:30 | 225 | 248 | 173 | 137 | 3 | 3 | 94 | 67 | 296 | 890 | 901 |
| 4:45 | 242 | 243 | 147 | 151 | 2 | 3 | 75 | 34 | 284 | 1095 | 968 |
| 5:00 | 193 | 212 | 96 | 105 | 2 | 3 | 54 | 25 | 236 | 659 | 803 |
| 5:15 | 141 | 158 | 82 | 80 | 1 | 1 | 38 | 28 | 190 | 535 | 643 |
| 5:30 | 128 | 140 | 58 | 74 | 1 | 1 | 34 | 18 | 136 | 420 | 521 |
| 5:45 | 102 | 112 | 33 | 34 | 1 | 1 | 25 | 21 | 105 | 339 | 800 |
| 6:00 | 68 | 79 | 26 | 29 | 1 | 1 | 18 | 11 | 102 | 210 | 248 |
| 6:15 | 41 | 56 | 11 | 21 | 0 | 1 | 20 | 5 | 42 | 125 | 151 |
| 6:30 | 26 | 29 | 9 | 6 | 0 | 1 | 15 | 5 | 31 | 95 | 117 |
| 6:45 | 24 | 27 | 3 | 6 | 1 | 0 | 14 | 8 | 20 | 76 | 103 |
| 7:00 | 26 | 25 | 11 | 4 | 0 | 1 | 14 | 6 | 28 | 103 | 116 |
| 7:15 | 45 | 40 | 13 | 7 | 1 | 0 | 24 | 11 | 56 | 221 | 268 |
| 7:30 | 144 | 146 | 28 | 15 | 3 | 1 | 24 | 14 | 130 | 722 | 939 |
| 7:45 | 306 | 351 | 72 | 66 | 2 | 2 | 31 | 24 | 248 | 1617 | 1758 |
| 8:00 | 449 | 453 | 168 | 154 | 3 | 4 | 38 | 48 | 289 | 1969 | 1715 |

## A Sample of the Input Data (4) – 108 locations and 186 rounds

|   | S0 | S1 | S2 | S3 | S4 | S5 | S6 | S7 | S8 | S9 | S10 |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| 0:00 | 107 | 97 | 37 | 42 | 0 | 1 | 38 | 19 | 94 | 331 | 380 |
| 4:00 | 261 | 246 | 236 | 165 | 5 | 5 | 130 | 126 | 363 | 900 | 1022 |
| 8:00 | 449 | 453 | 168 | 154 | 3 | 4 | 38 | 48 | 289 | 1969 | 1715 |
| 12:00 | 558 | 654 | 470 | 543 | 6 | 12 | 271 | 121 | 1023 | 1972 | 1577 |
| 16:00 | 954 | 894 | 468 | 377 | 8 | 9 | 195 | 90 | 848 | 1186 | 948 |
| 20:00 | 726 | 458 | 401 | 287 | 4 | 4 | 137 | 99 | 685 | 964 | 771 |
| 0:00 | 235 | 128 | 340 | 268 | 4 | 2 | 123 | 66 | 489 | 756 | 605 |
| 4:00 | 312 | 325 | 271 | 124 | 2 | 2 | 90 | 76 | 377 | 611 | 488 |
| 8:00 | 567 | 574 | 195 | 105 | 3 | 3 | 63 | 38 | 366 | 378 | 302 |
| 12:00 | 1028 | 994 | 137 | 74 | 0 | 2 | 71 | 19 | 150 | 225 | 180 |
| 16:00 | 1105 | 1125 | 123 | 23 | 1 | 5 | 55 | 19 | 110 | 172 | 137 |
| 20:00 | 647 | 620 | 90 | 20 | 3 | 0 | 50 | 30 | 73 | 137 | 109 |
| 0:00 | 215 | 143 | 63 | 15 | 0 | 2 | 52 | 23 | 102 | 185 | 148 |

## The Input Data (5)

- Minimum number of vehicles = 0
- Maximum number of vehicles = 1993
- Set10 - 10 subsets, range for each subset = 200
- Set20 - 20 subsets, range for each subset = 100
- Set40 - 40 subsets, range for each subset = 50
- Set80 - 80 subsets, range for each subset = 25

## The Input Data (6)A Sample of Set10

|   | S0 | S1 | S2 | S3 | S4 | S5 | S6 | S7 | S8 | S9 | S10 |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| Round 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 2 | 2 |
| Round 2 | 1 | 1 | 1 | 1 | 0 | 0 | 1 | 1 | 2 | 4 | 5 |
| Round 3 | 2 | 2 | 1 | 1 | 0 | 0 | 0 | 0 | 1 | 10 | 9 |
| Round 4 | 3 | 3 | 2 | 3 | 0 | 0 | 1 | 1 | 5 | 10 | 8 |
| Round 5 | 5 | 4 | 2 | 2 | 0 | 0 | 1 | 0 | 4 | 6 | 5 |
| Round 6 | 4 | 2 | 2 | 1 | 0 | 0 | 1 | 0 | 3 | 5 | 4 |
| Round 7 | 1 | 1 | 2 | 1 | 0 | 0 | 1 | 0 | 2 | 4 | 3 |
| Round 8 | 2 | 2 | 1 | 1 | 0 | 0 | 0 | 0 | 2 | 3 | 2 |
| Round 9 | 3 | 3 | 1 | 1 | 0 | 0 | 0 | 0 | 2 | 2 | 2 |
| Round 10 | 5 | 5 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 |
| Round 11 | 6 | 6 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 |
| Round 12 | 3 | 3 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 |
| Round 13 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 |

- The benefit of the Counter!      	_[Back](slide40.xml)__ _