Enrique Luis

Cortés-Berrueco

Carlos Gershenson

Christopher R Stephens
email: stephens@nucleares.unam.mx

Self-Organization Promotes the Evolution of Cooperation with Cultural Propagation

In this paper three computational models for the study of the evolution of cooperation under cultural propagation are studied: Kin Selection, Direct Reciprocity and Indirect Reciprocity. Two analyzes are reported, one comparing their behavior between them and a second one identifying the impact that different parameters have in the model dynamics. The results of these analyzes illustrate how game transitions may occur depending of some parameters within the models and also explain how agents adapt to these transitions by individually choosing their attachment to a cooperative attitude. These parameters regulate how cooperation can self-organize under different circumstances. The emergence of the evolution of cooperation as a result of the agent's adapting processes is also discussed.

Introduction

Urban traffic problems have a complex behavior even in their most simplistic abstractions [START_REF] Nagatani | Chaos and dynamical transition of a single vehicle induced by traffic light and speedup[END_REF]. This behavior becomes more complex when driver interaction is added [START_REF] Wastavino | Modeling traffic on crossroads[END_REF]. With these two premises, in this paper, three computational models, which were originally intended for studying driving behaviors and their impact in traffic, are presented. The aim is to explore the possibilities for controlling some of the complex characteristics of traffic, e.g. the consequences of driver interactions. The possibility of using them for other social problems is also discussed.

The models were conceived to study the evolution of cooperation [START_REF] Axelrod | The evolution of cooperation[END_REF], which studies how cooperative behaviors are preserved when selfish behaviors offer greater individual rewards, e.g. drivers who yield at lane changes or crossings, animal females taking care of their offspring, students who don't betray each other. Several abstractions for simulating different circumstances in which this phenomenon occurs have been proposed [START_REF] Santos | Evolutionary dynamics of social dilemmas in structured heterogeneous populations[END_REF]. The models are based in three abstractions of different observed situations in which cooperation evolves [START_REF] Nowak | Five rules for the evolution of cooperation[END_REF]. Table 1 shows these abstractions as theoretical games in which players may choose between two behaviors: cooperative or selfish. When a player chooses to cooperate she has to pay a cost that her game partner is going to receive as a benefit. In each game, the decision of the players is influenced by a different probabilistic variable. This variable represents some feature that is exploited by the global behavior to favor the evolution of cooperation. For the kin selection strategy, relationships are exploited, the relation may be genetic, emotional or of any other type but as long as it its closer, cooperation will be more frequent. In the direct reciprocity case, the evolution of cooperation is linked with the probability of one player to play again with the same partner, and this condition is set because players are responding cooperation with cooperation and defection with defection. The feature exploited by the indirect reciprocity case is peer pressure. While more players get to know the actions of a determined player, she will obtain more benefits by cooperating and while fewer players get to know her actions more benefits she will obtain by defecting. Each strategy has a condition for the cooperation to become an evolutionary stable strategy (ESS, cooperators survive), another when cooperation becomes risk-dominant (RD, cooperators are near 1/2 of the population) and other when cooperators are advantageous (AD, cooperators are near 2/3 of the population). Table 1. Rules for the three game strategies [START_REF] Nowak | Five rules for the evolution of cooperation[END_REF].

2

The Models

We developed agent-based computational models, using the NetLogo [START_REF] Wilensky | NetLogo[END_REF] platform, to better understand three strategies for the evolution of cooperation: kin selection, direct reciprocity and indirect reciprocity [START_REF] Nowak | Five rules for the evolution of cooperation[END_REF]. Unlike the results shown in [START_REF] Nowak | Five rules for the evolution of cooperation[END_REF] these models are focused in cultural evolution (players may choose to cooperate or not under different circumstances instead of been born as players who always cooperate or always defect), therefore, the first characteristic these models share is that they have a constant population. The behavior of the agents is similar to the one of agents described in Skyrm's Matching Pennies model [START_REF] Skyrm | The dynamics of rational deliberation[END_REF]. Agents have a cooperation probability variable (cp) that determines their attachment to a cooperator strategy, while this variable gets a greater value the agent will cooperate more frequently. We will use this variable for deciding if the agents will cooperate or not in a particular game. Each agent is able to identify herself as a cooperator or as a defector: Where p i is the i th agent or player, c i is the i th cooperator and d i is the i th defector. As a consequence of this characteristic, a partition of the population can be made. The initial proportions of cooperative versus defective agents in the population (ipc and ipd) are relevant parameters of the model although they can be reduced to one as ipc=1-ipd. In order to identify agents as cooperators or defectors at the beginning of the simulations we give them an initial cp, thus, initial cp of defectors (iicpd) and initial cp of cooperators (icpc) are two more parameters. The agents move through a defined two-dimensional space. It has been seen [START_REF] Nagel | A cellular automaton model for freeway traffic[END_REF] that in such cases population density is a key determinant of the dynamics, so the number of players (population) interacting in the defined space is another important parameter of the model.

Agents interact following the payoff tables corresponding to each strategy studied. As can be seen in Table 1, the three strategies share two variables: the benefit (b) one agent gives to another while cooperating and the cost (c) paid by the cooperator while cooperating. With the purpose of keeping track of the player's decisions, each one of them is assigned a fitness value from where the cost will be subtracted and the benefits will be added.

Appendix A of [13] shows the instructions executed by the agents during each iteration of the simulations. The behaviors of each game are detailed in appendix B of [13].

Tune cooperation probability

Agents adapt to the environment by modifying whether they are going to cooperate or defect in the next round. We implemented several exogenous tuning algorithms based on the literature [START_REF] Skyrm | The dynamics of rational deliberation[END_REF][9][6][7] [START_REF] Weirich | Computer simulations in game theory[END_REF] with no satisfactory results. We developed two self-organizing tuning alternatives and were tested with very good results: Selfish fitness: the agents only take their own fitness value as a parameter, unlike other algorithms that take into account the values of all the other players or values of the game partners. If the player cooperates or defects, and her fitness increases, then the agent increases or decreases her cp respectively. If the player cooperates or defects, and her fitness is reduced, then the agent decreases or increases her cp respectively. And if there is no change in the agent's fitness, then there is no change in her cp.

Selfish profit: this is very similar to the previous one, but instead of comparing fitness values (sum of all profits obtained), agents act based in the comparison of the profit of their last game and the profit of the current round. Thus, if the player cooperates or defects and the actual profit is greater than the last one, then the agent increases or decreases her cp. If the player cooperates or defects and the actual profit is lower than the last one, then the agent decreases or increases her cp. Finally if the last profit is equal to the actual profit, then there is no change in the cp value.

Methods

Before general results were obtained, an analysis of the variables was conducted. A primary goal of this analysis was to determine the impact of the parameters on the dynamics of the models. A secondary goal was to obtain parameter values that best exemplify the model's behavior. Detailed information about the experiments may be found in appendix C of [13].

Results

Interesting results can be derived from a careful analysis of the graphics of the payoff table behavior as the corresponding probability takes values within the range [0,1] (Figure 1). As x has a higher value, the agents move to different games. Using the same notations as in [START_REF] Santos | Evolutionary dynamics of social dilemmas in structured heterogeneous populations[END_REF] that designates R (reward) when two agents cooperate, P (punishment) when two players defect, T (temptation) when one player defects and the other cooperates and S (sucker´s payoff) when one player cooperates and the other defects; the move from game to game is described in appendix D of [13]. The values of b and c also determine the transition value of x that takes the agents from one game to another. It is important to notice that the agents respond to these transitions by interacting with the others and adapt by using only simple local rules with only two basic requirements: 1) the agents must know how to distinguish that an amount is bigger than other and 2) the agents must have the notion of more is better. Within the strategies studied, other requirements are implicitly given for each case and are described in the appendix E of [13].

ESS, RD and AD conditions

It was shown in Table 1, when the x variable reaches certain value, ESS, RD and AD behaviors emerge. Figure 2 shows the characteristic behavior obtained by the analysis described in the behavior part of the Methods section; in it, these expected behaviors are not noticeable. Analyzing the model variables, we could find that these conditions are preserved, but the effect can be observed by setting the starting population of cooperators as 2/3, 1/2 and 1/3 of the total population for ESS, RD and AD respectively and obtaining a graphic similar to Figure 2. This result is shown in appendix F of [13] along with the impact of all the parameters to each strategy.

Self-organization

Self-organization seems to be a key element for the cultural evolution of cooperation. There are several studies [START_REF] Skyrm | The dynamics of rational deliberation[END_REF][9][6][7] [START_REF] Weirich | Computer simulations in game theory[END_REF] in which the agents just can choose between cooperate or defect. In the models presented here, the players can choose the degree of cooperation that they consider the best. Another important difference between our models and the others [6][7] is the inclusion of a probabilistic variable so that agents choose the degree of cooperation by comparing their actual state with a past one instead of comparing their state with the state of others. This is important because each agent may be seen as an individual system adaptable to different environments or contexts using the information given by the interactions with other similar, not necessarily equal, systems.

Conclusions

Three agent-based computational models for the study of the evolution of cooperation under cultural propagation were described. It was shown that their behavior is the result of transitions between games defined by Game Theory. The transitions are consequences of the structure determined by the payoff matrixes of the three strategies studied. Each of these strategies abstracts well-known real behaviors [START_REF] Nowak | Five rules for the evolution of cooperation[END_REF]; hence the importance of creating computational models that let us experiment exhaustively different circumstances for these phenomena, a difficult task with living organisms. The impact of the parameters in each model was analyzed to better understand how to manipulate the models and adapt them for more specific studies, such as social phenomena (e.g. bulling, market formation, and migration), traffic problems (e.g. signaling issues, conflicting use of roads) and biological processes (e.g. interactions between organisms and populations).

  If

Fig. 1 .

 1 Fig. 1. Graphics of the payoff table behaviors for x's values in the range [0,1] for a) Kin Selection, b) Indirect Reciprocity and c) Direct Reciprocity (DR is in logarithmic scale).

Fig. 2 .

 2 Fig. 2.Percentage of cooperating population while the corresponding probability is varied.


Andreas Kaltenbrunner

Pablo Aragón

David Laniado

Yana Volkovich

Not all paths lead to Rome: Analysing the network of sister cities

Keywords: Social network analysis, sister cities, social self-organisation

This work analyses the practice of sister city pairing. We investigate structural properties of the resulting city and country networks and present rankings of the most central nodes in these networks. We identify different country clusters and find that the practice of sister city pairing is not influenced by geographical proximity but results in highly assortative networks.

Introduction

Human social activity in the form of person-to-person interactions has been studied and analysed in many contexts, both for online [START_REF] Mislove | Measurement and analysis of online social networks[END_REF] and off-line behaviour [START_REF] Wasserman | Social network analysis: Methods and applications[END_REF]. However, sometimes social interactions give rise to relations not anymore between individuals but rather between entities like companies [START_REF] Höpner | The politics of the german company network[END_REF], associations [START_REF] Moore | International NGOs and the role of network centrality in humanitarian aid operations: A case study of coordination during the 2000 Mozambique floods[END_REF] or countries [START_REF] Caldarelli | A network analysis of countries export flows: Firm grounds for the building blocks of the economy[END_REF]. Often these relations are associated with economic exchanges [START_REF] Caldarelli | A network analysis of countries export flows: Firm grounds for the building blocks of the economy[END_REF], sports rivalry [START_REF] Mukherjee | Identifying the greatest team and captaina complex network approach to cricket matches[END_REF] or even cooperation [START_REF] Moore | International NGOs and the role of network centrality in humanitarian aid operations: A case study of coordination during the 2000 Mozambique floods[END_REF].

In this work we study one type of such relations expressed in the form of sister city partnerships 1 . The concept of sister cities refers to a partnership between two cities or towns with the aim of cultural and economical exchange. Most partnerships connect cities in different countries, however also intra-country city partnerships exist. Our study aims at understanding some of the basic social, geographical and economic mechanisms behind the practice of city pairings.

We extracted the network of sister cites as reported on the English Wikipedia, as far as we know the most extensive but probably not complete collection of this kind of relationships. The resulting social network, an example of social self organisation, is analysed in its original form and aggregated per country. Although there exist studies that analyse networks of cities (e.g. networks generated via aggregating individual phone call interactions [START_REF] Krings | Scaling behaviors in the communication network between cities[END_REF]) to the best of our knowledge this is the first time that institutional relations between cities are investigated.

Dataset description

The dataset used in this study was constructed (using an automated parser and a manual cleaning process) from the listings of sister cities on the English Wikipedia. 2 We found 15 225 pairs of sister cities, which form an undirected3 city network of 11 618 nodes. Using the Google Maps API we were able to geo-locate 11 483 of these cities. We furthermore construct an aggregated undirected and weighted country network, where two countries A and B are connected if a city of country A is twinned with a city of country B. The number of these international connections is the edge weight. The country network consists of 207 countries and 2 933 links. Some countries have self-connections (i.e. city partnerships within the same country). Germany has the largest number of such self links as a result of many sister city relations between the formerly separated East and West Germany.

Table 1 lists the principal macroscopic measures of these two networks. The clustering coefficient of the city network is comparable to the values observed in typical social networks [START_REF] Newman | Random graph models of social networks[END_REF]. Also the average path-length between two cities is with 6.7 in line with the famous six-degrees-of-separation. The country network is denser, witnessed by the remarkably high value of the clustering coefficient ( C = 0.43), and a very short average distance of 2.12.

In Figure 1 we plot the degree distributions of both networks. We observe in Figure 1 (left) that more than 60% of the cities have only one sister city, about 16% have two and only less than 4% have more than 10. For the countries we observe in Figure 1 (right) that around 58% of the countries have less than 10 links to other countries, but at the same time more than 20% of the countries have more than 100 sister city connections (i.e. weighted degree ≥ 100). Both networks have skewed degree-distributions with a relative small number of hubs.

Assortativity

To understand mixing preferences between cities, we follow the methodology of [START_REF] Foster | Edge direction and the structure of networks[END_REF] and calculate an assortativity measure based on the Z-score of a comparison between the original sister city network and 100 randomised equivalents.

For degree-assortativity, randomised networks are constructed by reshuffling the connections and preserving the degree; in the other cases, the network structure is preserved while the values of node properties are reshuffled. Table 2 gives an overview of the results. We find that the city network is highly assortative indicating a clear preference for connections between cities with similar degree. We also analyse assortativity scores for other variables and find that cities from countries with similar Gross Domestic Product (GDP) per capita, Human Development Index or even similar indexes of political stability are more likely to twin. Only for the nominal GDP neutral mixing is observed.

Rankings

We discuss now city and country rankings based on centrality measures. For the sister city network we show the top 20 cities ranked by degree (Table 3, left). Saint Petersburg, often referred to as the geographic and cultural border of the West and East, is the most connected and also most central sister city. There are also cities, such as Buenos Aires, Beijing, Rio de Janeiro and Madrid, which have large degrees but exhibit lower betweenness ranks. In particular, the Spanish and the Chinese capitals have significantly lower values of betweenness, which could be caused by the fact that other important cities in these countries (e.g. Barcelona or Shanghai) act as primary international connectors.

In Table 3 (right) we present rankings for the country network. In this case the USA lead the rankings in the two centrality measures we report. The top ranks are nearly exclusively occupied by Group of Eight (G8) countries suggesting a relation between economic power and sister city connections.

Clustering of the country network

In Figure 2 we depict the country network. Node size corresponds to the weighted degree, and the width of a connection to the number of city partnerships between the connected countries. The figure shows the central position of countries like the USA, France, UK and China in this network.

The colours of the nodes correspond to the outcome of node clustering with the Louvain method. We find 4 clusters. The largest one (in violet) includes the USA, Spain and most South American, Asian, and African countries. The second largest (in green) is composed of Eastern-European and Balkan countries: Turkey, Russia, and Poland are the most linked among them. The third cluster (in red) consists of Central and Western-European countries and some of their former colonies. It is dominated by Germany, UK, France and the Netherlands. Finally, the smallest cluster (in cyan) mainly consists of Nordic countries.

The clustering suggests cultural or geographical proximity being a factor in city partnerships. In the next section we will investigate this further.

Distances

To test the extent to which geographical proximity is an important factor for city partnership we analyse the distributions of geographical distances between all pairs of connected sister cities.

Figure 3 depicts this distribution as a histogram (blue bars in the left subfigure) or as a cumulative distribution (blue curve in the right sub-figure). The figure also shows the overall distance distribution between all possible pairs (connected or not) of geo-located sister cities (green bars and red curve). There is nearly no difference (apart from some random fluctuations) between these two distributions. The fluctuations vanish in the cumulative distributions where the two curves are nearly overlapping. Only for very close cities it is slightly more likely than expected by random choice to establish a city sistership. This can also be observed in the very small difference of the average distance of two randomly chosen cities (10 006 km) and a pair of connected sister cities (9 981 km).

Conclusions

We have studied the practice of establishing sister city connections from a network analysis point of view. Although there is no guarantee that our study covers all existing sister city relations, we are confident that the results obtained give reliable insights into the emerging network structures and country preferences.

We have found that sister city relationships reflect certain predilections in and between different cultural clusters, and lead to degree-assortative network structures comparable to other types of small-world social networks. We also observe assortative mixing with respect to economic or political country indexes.

The most noteworthy result may be that the geographical distance has only a negligible influence when a city selects a sister city. This is different from what is observed for person-to-person social relationships (see for example [START_REF] Kaltenbrunner | Far from the eyes, close on the Web: impact of geographic distance on online social interactions[END_REF]) where the probability of a social connection decays with the geographical distance between the peers. It may, thus, represent the first evidence in real-world social relationships (albeit in its institutional form) for the death of distance, predicted originally as a consequence of decrease of the price of human communication [START_REF] Cairncross | The death of distance: How the communications revolution is changing our lives[END_REF].

Possible directions for future work include combination of the analysed networks with the networks of air traffic or goods exchange between countries.

Fig. 1 .

 1 Fig. 1. Cumulative degree distribution in the city (left) and country networks (right).

Fig. 2 .

 2 Fig. 2. Country network: node size corresponds to degree and node colours indicate the four clusters obtained with the Louvain method.

Fig. 3 .

 3 Fig.3. Distribution of the distances between connected sister cities (blue) and the practically identical distance distribution between all cities (green in pdf, red in cdf).

Table 1 .

 1 Network properties: number of nodes N and edges K, average clustering coefficient C , % of nodes in the giant component GC, average path-length d .

	network	N	K	C	% GC d
	city network	11 618 15 225 0.11 61.35% 6.74
	country network	207 2933 0.43 100% 2.12

Table 2 .

 2 Comparing assortativity coefficients r of the city network with the mean assortativity coefficients r rand and the corresponding stdv σ rand of randomised networks. Resulting Z-scores ≥ 2 (in bold) indicate assortative mixing. Apart from the city degrees, the city properties used coincide with the corresponding country indexes.

	property	r r rand σ rand	Z
	city degree	0.3407 -0.0037 0.0076 45.52
	Gross Domestic Product (GDP) 4 0.0126 -0.0005 0.0087 1.51
	GDP per capita 5	0.0777 0.0005 0.0078 9.86
	Human Development Index (HDI) 6 0.0630 -0.0004 0.0075 8.46
	Political Stability Index 7	0.0626 0.0004 0.0090 6.94

Starting from http://en.wikipedia.org/wiki/List_of_twin_towns_and_sister_cities, which includes links to listings of sister cities grouped by continent, country and/or state.

Although only 29.8% of the links were actually reported for both directions.

Source http://en.wikipedia.org/wiki/List_of_countries_by_GDP_(nominal)

Source: http://en.wikipedia.org/wiki/List_of_countries_by_GDP_(nominal)_per_capita

Source: http://en.wikipedia.org/wiki/List_of_countries_by_Human_Development_Index

Source: http://viewswire.eiu.com/site_info.asp?info_name=social_unrest_table

This work was supported by Yahoo! Inc. as part of the CENIT program, project CEN-20101037, and ACC1 Ó -Generalitat de Catalunya (TECRD12-1-0003). Acknowledges the Torres Quevedo Program from the Spanish Ministry of Science and Innovation, co-funded by the European Social Fund. 1 to as twin town, partnership town, partner town or friendship town. Here we use preferentially the term sister city.


Lei Fang

Simon Dobson

Unifying sensor fault detection with energy conservation

Wireless sensor networks are attracting increasing interest but suffer from severe challenges such as power constraints and low data reliability. Sensors are often energy-hungry and cannot operate over the long term, and the data they gather are frequently erroneous in complex ways. The two problems are linked, but existing work typically treats them independently: in this paper we consider both side-by-side, and propose a self-organising solution for model-based data collection that reduces errors and communications in a unified fashion.

Introduction

Wireless Sensor Network (WSN) applications have been attracting growing interest from both academia and industry. For environmental monitoring, distributed nodes are deployed to sense the environment and return sampled data to the sink, typically at a regular frequency. However, sensors are energy hungry. Various energy-saving techniques [START_REF] Schurgers | STEM: Topology management for energy efficient sensor networks[END_REF][START_REF] Liu | Energy efficient information collection with the ARIMA model in wireless sensor networks[END_REF] have been proposed, such as sleep/wakeup protocols, model-based data collection, and adaptive sampling.

Another, related problem is the low reliability of data gathered by sensors. A substantial portion of the data gathered in real monitoring applications is actually faulty [START_REF] Sharma | Sensor faults: Detection methods and prevalence in real-world datasets[END_REF]. A data-fault can be defined as reading entries, sampled and reported by the sensor nodes, deviating from the true representation of the physical phenomenon to be measured. For example, many data series, such as [START_REF]INTEL: Intel Berkeley Laboratory sensor data set[END_REF], have been found to be faulty. Deployed WSNs are expected to operate in remote areas for long periods of time without human intervention: manual fault filtering is not an option. To increase data reliability, automatic data fault detection methods become imperative. However, most existing work adopts a centralised and off-line approach to checking the validity of data, which does not validate the sensed data until it has been collected. Recent work [START_REF] Kamal | Packet-Level Attestation: a framework for in-network sensor-data reliability[END_REF] has proposed a framework to increase sensor data reliability in a real time.

However, the two domains -energy and error -are typically excluded from each other: sensor fault detection has always been separated from sensor data collection techniques. Existing sensor fault detection methods do not care how the data is collected and whether the collection is energy-efficient or not. Conversely, energy-efficient data collection methods usually assume the validity of sensor data and so do not incorporate sensor fault detection into their collection method. In reality, these two problems both coexist and co-relate. To achieve energy-efficient, minimum-error data collection, we require a solution combining fault detection and energy-aware data collection.

In this paper, we propose an initial framework addressing both features in a self-organising fashion. We use only local data and communications to learn and autonomously maintain a model of the data expected to be observed by the network, and then uses this model both to pre-filter data to remove probable errors and to reduce the amount of raw data exchanged to reduce energy usage.

Section 2 presents our framework, which is evaluated in section 3 by means of some preliminary simulation results. Section 4 concludes with some directions for future work.

A proposed framework

In our proposed framework, models describing the expected behaviour of the sensed phenomena are maintained symmetrically in both network nodes and sink(s). The model is used to predict the measurements sampled by the nodes within some error bounds. Essentially when a data entry sensed is within a predefined error-band ( ) of the value calculated by the model, the data entry is exempt from sending to the sink. However, a disagreement between the data and the model may either mean the model is stale, making the model no longer fits the changing phenomenon, or the data is faulty, resulting in it deviating from the model. Therefore, a fault-detection technique is needed to filter out faulty data from "normal" readings so that necessary updates can take place.

The whole life cycle of the framework can be described as follows. The algorithm starts with a learning phase, in which the data model (we use ARIMA model in this work, which is presented in detail in 2.1) and a spatial model (Algorithm 1) is learnt and synced between nodes and sink. Also the fault detection model, presented in detail in 2.2, is also constructed in this phase. Following the learning phase, a error-aware data collection phase starts. In each remote node, it compares data entries sensed against the model. When a disagreement occurs, the data entry will go through the fault detector first, and different actions will be taken according to the result. If the result is positive, i.e. faulty, the data entry will be ignored; otherwise, it will be sent to the sink. The whole process will go back to the learning phase again, when a large number of data entries have to be sent.

Another way to look at this approach is that the WSN develops a model of the data it is observing in a manner akin to what a scientist does when evaluating a data set -but performs this analysis automatically and on-the-fly as data is being collected. The data being collected is therefore being used to maintain and refine the model rather than being treated as uninterpreted by the network, with the model being updated dynamically to reflect the data. While not appropriate for all domains, we believe that this approach is well-suited to systems with missions to detect anomalies, systematic or other deviations from an expected observational baseline, and this class of systems has wide applicability in domains including environmental monitoring and human safety.

The ARIMA model

The ARIMA model is widely used for univariate time series modelling, and has been used [START_REF] Liu | Energy efficient information collection with the ARIMA model in wireless sensor networks[END_REF] to form an energy-efficient information-collection algorithm.

ARIMA consists of three terms: the auto-regressive (AR), the moving average (MA), and an optional integration term (I). The AR term is a linear regression of the current data value against prior historical data entries. The MA term captures the influence of random "shocks" to the model. The I term makes the process stationary by differencing the original data series. A first-order differencing of data series X t , for example, is defined as

X 1 t = X t -X t-1 .
We use the notation ARIMA(p, d, q) to define a data series modelled by a ARIMA model with p-lagged historic data entries, q most recent random shocks, and d-order difference:

X d t = φ 1 × X d t-1 + . . . + φ p × X d t-p + ε t + θ 1 × ε t-1 + . . . + θ q × ε t-q (1)
In the learning phase, the parameter set, including φ 1 , ..., φ p ; θ 1 , ..., θ q , is learnt from the learning data by either conditional least squares method or maximum likelihood method. However, if the model include only AR terms, then ordinary least square method can be used, which means the whole computation can be placed in network. To sync the model, only an array of floating numbers are required to send.

Data fault detection

In this work, in order to place the detector into resource-constrained sensors, we use a simple but effective method to filter out erroneous readings. Spatial correlation is exploited to further validate an observation. To quantify the spatial correlation, each node i maintains a 2 × |nbr i | spatial matrix, where nbr i denotes the set of neighbouring nodes of i. The spatial matrix simply stores the maximum and minimum difference in observation between node i and its neighbours1 . We use a voting mechanism to validate a suspect data entry. When a data entry does not match the statistical model, the hosting node will send the data to its neighbours. Upon receiving a validation request, each node will consult the spatial matrix and send back a boolean result accordingly. The final decision will be made according to the results solicited from the neighbours. The data will be marked as faulty if a larger number of neighbours believe so. The spatial correlation between nodes is assumed to be stable, meaning that the spatial matrix remains valid during the whole data collection process, which is a common (although not unassailable) assumption [START_REF] Kamal | Packet-Level Attestation: a framework for in-network sensor-data reliability[END_REF].

Preliminary evaluation

We evaluate our proposed framework by simulation over an accepted benchmark real-world data set [START_REF]INTEL: Intel Berkeley Laboratory sensor data set[END_REF], collected by 54 sensors in Intel's Berkeley Laboratory. We examine both the fault-detection accuracy and energy-saving features respectively using our time-series and spatial correlation models.

Fault model

Injecting artificial faults into real data set is a common approach to measure the accuracy of a detector [START_REF] Sharma | Sensor faults: Detection methods and prevalence in real-world datasets[END_REF]. We consider four particular kinds of faults: short, constant, noise, and drift. The parameters for the fault modelling, which are selected based on existing literatures [3] [5], are provided as well.

SHORT Data d i,t is replaced by d i,t + d i,t * f where f is a random multiplicative factor. f ranging from 0.1 to 10.0 is used here. CONSTANT Data d i,t for t ∈ [t s , t e ] is replaced by some random constant c, and c is randomly selected from 30 to 999. NOISE Data d i,t for t ∈ [t s , t e ] is replaced by d i,t + x, where x is a Gaussian random variable, whose distribution is N (0, σ 2 ), and σ is set to be 2. DRIFT Data d i,t for t ∈ [t s , t e ] is replaced by d i,t + a t+1-ts , where a > 1. We use natural number e here.

Results

Table 1 shows the behaviour of the model to the different injected faults as described in the previous section. ARIMA(4,2,0) model is used here with the first 100 data entries as learning data. As there is no MA terms, the whole learning process is tractable to be carried out in remote sensor mote. The error-band, , is set 0.4 Celsius degree.

It is clear that the proposed solution has high classification accuracy while keeping false alarm rate low. Note that although there is no specific rule to each fault type, for example constant or drift, the solution still exhibits good detection performance. It is also interesting to see that the false alarms rate is zero for all four cases. This is mainly because of the stationarity of the spatial correlation, making neighbouring nodes become good reference models for error detection. In assessing the energy efficiency, in the interests of space we only list the performance of one sensor, Sensor 1 from the data set [START_REF]INTEL: Intel Berkeley Laboratory sensor data set[END_REF]. ARIMA(4, 2, 0) is still used. Figure 1 shows both actual data series sampled at a remote node and the data series restored at the sink as error-band is set 0.2 and 1.0 Celsius degree. It is clear that both data series restored by the ARIMA model closely follows the actual data series but at different granularities. It is obvious that the data from upper graph fits the actual data better. The mean squared error is 0.0068 and 0.2053 respectively. However the accuracy comes at the cost of higher energy consumption: only 76% of the data are exempted from sending back to the sink, while the bottom one saves 95%. But both of them save great amount of energy from sending data back to sink. Note the overall energy saving also depends on the size of data faults. As more data faults present, more extra efforts are paid to clean them out by local communication.

In general, there is a trade-off between energy saving and data integrity and granularity. Better restored data and data integrity is achieved at the price of relative frequent communication, or higher energy cost. The trade-off can be set by the error-band parameter. Users can choose its value according to specific application requirements.

Conclusion

We have presented a framework which features couples fault detection and energy efficiency in data collection. We learn and maintain statistical models of the expected data stream and use these models to reduce communications and improve bad-point rejection. Potentially they may also be used to answer queries at the sink without recourse to the WSN.

We believe that our preliminary results show that these two significant challenges to WSN deployments can be addressed using a unified approach, in a way that maintains the statistical and properties of the data collected. We believe that this suggests a practical approach to further improving WSN longevity in the field.

The work presented here remains proof-of-concept. We are currently implementing our framework on real sensors to perform a more thorough evaluation on the method, and also to test its feasibility in a real-world deployment. Other data modelling and fault detection methods are also being investigated, and we hypothesis that a range of techniques can be incorporated into the same framework to target different classes of sensor network mission. We would also like to move beyond model-based data collection methods to investigate other energy-saving techniques that have the potential to integrate further with the fault detector.

Figure 1 .

 1 Figure 1. Actual versus restored data at the sink node with different error-band (up ( = 0.2 • C), bottom ( = 1.0 • C))

Table 1 .

 1 Fault Detection Accuracy

	SHORT CONSTANT NOISE DRIFT
	True Positive 99.5%	100%	83% 100%
	False Positive 0.0%	0.0%	0.0% 0.0%

We assume for simplicity that all data is represented by a continuous range of values. Categorical data requires a slightly different treatment.

Acknowledgements

Lei Fang is supported by a studentship from Scottish Informatics and Computer Science Alliance (SICSA).