Robin Bloomfield

Robert Stroud

Security-Informed Safety "If it's not secure, it's not safe"

Keywords:

Traditionally, safety and security have been treated as separate disciplines, but this position is increasingly becoming untenable and stakeholders are beginning to argue that if it's not secure, it's not safe. The idea of combining safety and security is not new but neither is it straightforward. To illustrate the complexities of the problem, we explore some of the challenges that need to be overcome in order to develop a principled approach to "security-informed safety".

INTRODUCTION

For a system to be safe, it also has to be secure. Otherwise, a safety critical system -one that can harm or injure peoplecould provide attackers with a potential mechanism for causing widespread damage or panic, and it is credible that such systems could become the target of malicious actions.

In principle, achieving interworking between safety and security should be straightforward. Both are sophisticated engineering cultures that emphasise the need for good process, the importance of risk analysis and the need for assurance and justification. However, these similarities are superficial and in practice there are significant challenges, as experience with large-scale systems has shown.

To illustrate the complexities of the problem and in order to stimulate debate, we explore some of the technical issues involved in combining safety and security assurance in a principled way. Our work is informed by an investigation of these issues in the context of the railway industry [START_REF] Bloomfield | Safety and Security: Concepts, Standards and Assurance[END_REF], but is more widely applicable to safety engineering in general.

II. CONCEPTS

The commonalities between safety and security are frequently obscured by the use of different concepts and terminologies. Indeed, there is considerable variation in terminology both within and between the safety and security communities. Thus, to achieve a shared understanding of the key concepts within each domain, there is a need to establish a lingua franca or even a common ontology.

The IFIP WG 10.4 dependability taxonomy [START_REF] Aviziensis | Basic concepts and taxonomy of dependable and secure computing[END_REF] offers some hope for defining a consistent set of terms. In particular, it makes a clear distinction between cause and effect and highlights the need to be clear about system boundaries.

Broadly speaking, safety is concerned with protecting the environment from the system whereas security is concerned with protecting the system from the environment. Security and safety can both be viewed as kinds of dependability and use similar techniques to identify potential failure modes and assess their impact on the overall system. Thus, there is considerable overlap between safety and security methods, although the focus is different and in some cases safety and security requirements can be in conflict.

In particular, one of the major differences between safety and security is that a secure system needs to cope with evolving threats and changes to the environment through design and architectural measures as well as operational ones. It is important for the system to remain safe and secure despite such changes, in other words, to be resilient to change.

III. PRINCIPLES

There are many overlaps between safety and security principles, but there are also some significant differences in emphasis and some potential conflicts. For example, defence in depth is an important architectural principle for both safety and security that depends on the use of multiple, and as far as possible independent, barriers. However, security considerations are likely to challenge the effectiveness and independence of safety barriers. From a safety system perspective, security principles [START_REF] Saltzer | The Protection of Information in Computer Systems[END_REF] such as economy of mechanism, least privilege, and psychological acceptability are probably all readily acceptable. Other principles, such as complete mediation and end-to-end arguments, could have a significant impact on the architecture and performance of systems. But perhaps the most radical security principles from a safety perspective are those based on Kerchoffs' principle [START_REF] Kerckhoffs | La cryptographie militaire[END_REF], namely ease of recovery and open design.

In particular, although safety systems are already designed to support operational changes for calibration and maintenance, the ease of recovery principle, which states that the security of the system should not depend on anything that cannot be easily changed, could have far reaching impact on the architecture of safety systems.

Moreover, changes to threats over the lifetime of the system will probably mean that controls that were adequate initially will need to be reconsidered. This has implications for This research was commissioned on behalf of UK government and the UK rail industry.

the architecture and lifecycle of embedded safety systems where design life may be 20-40 years.

Given the uncertainties around future threats, systems should be designed to be adapted and replaced perhaps sooner then would be necessary from just a safety perspective. This could have significant architectural and cost implications for large infrastructure projects, particularly those that are already in progress IV. METHODOLOGY Risk assessment is a fundamental step in safety and security analysis, but the underlying threat model is different. There is a need for a unified methodology for assessing the threats to the safety and security of a system.

Security considerations can have a significant impact on a safety case. For example, there needs to be an impact analysis of the response to security threats and discovery of new vulnerabilities and reduction in the strength of protection mechanism. This suggests a greater emphasis on resilience of the design.

It is also necessary to consider the potential for attack during a safety incident and the opportunity this might provide for malicious activity. A fail-safe state may not be as safe as previously thought if the system is under attack and the assumption that any security attack on a control system could only, at worst, cause a fail-safe state to be reached is in general not true. Moreover, assumptions about the capabilities and state of society may change; for example, consider managing a safety incident during a major security incident.

Given the importance in security of open scrutiny of design and implementation (e.g. of crypto), it is an appropriate question whether security-informed safety cases in entirety or part should be disclosed. Within the safety community, the principle of independent assessment is well established, but the design details within a safety case are usually considered to be confidential and are not made public in their entirety.

The key question is whether publishing the detailed design and safety analysis for a system would make the system less or more safe and secure, or more precisely which aspects would it be beneficial to expose and which not.

V. STANDARDS Safety standards already require "malevolent and unauthorized actions to be considered during hazard and risk analysis" [START_REF]Functional safety of electrical/electronic/programmable electronic safety-related systems -Part 1: General Requirements[END_REF], and there have been a number of domainspecific attempts to define a unified approach to safety and security assurance [6][7]. However, the standards framework for dealing with security-informed safety needs to be more explicitly designed than is currently the case. In particular, the relationship between generic and domain-specific safety and security standards needs to be clarified, and terminological and conceptual differences need to be resolved.

The standards framework should be based on explicit principles and use a consistent terminology. The standards groups should ensure they have available a suitable mix of both security and safety expertise.

Standards often use levels as a way of classifying systems, risks and controls. However, it is important to understand the assumptions that underpin these classification schemes and not to confuse different kinds of classification. In particular, risk levels, requirement levels, and assurance levels need to be carefully distinguished.

A particular concern is the problem of justifying requirements that specify the use of particular methods and tools to achieve a specific level. In order to support interworking between safety and security standards, we need to develop a better understanding of the rationale for such recommendations and the evidence base that supports them.

Security standards are often based on security controls, a concept that embraces a wide range of different interventions covering process, product and organisation. In contrast, safety standards are typically based on an engineering life cycle model. In principle it should be possible to relate safety mitigations to security controls, but in order to perform such an analysis, it will be necessary to define a common way of classifying controls and mitigations.

VI. NEXT STEPS

We believe that some or all of the following next steps would be helpful in establishing a more principled approach to "security-informed safety".

• Develop guidance on concepts and terminology to support dialogue between the safety and security communities. • Research the applicability of security principles to safety and the associated trade-offs and conflicts. • Consider how to make credible arguments that safety and security risks have been reduced to as low as reasonably practicable.

• Investigate how a Claims-Arguments-Evidence based methodology could be used to support the development of a security-safety protection profile. • Intercept and support the standards process in order to clarify the relationship between safety and security and resolve some of the terminological and conceptual issues.


Badrina Gasmi-Boumezoued
email: badrinagasmi@gmail.com

A Mira

Hassina Nacer

Nacer Boudjlida
email: nacer.boudjlida@loria.fr

Keywords: Knowledge management applications, Composite answers, Conceptual graphs, Mediators federation

The capture, the structuring and the exploitation of competences of an "object" (like a business partner, an employee, a software component, a Web service, etc.) are crucial problems in various applications, like cooperative and distributed applications or e business applications. The work we describe here concerns competence advertising, organization, discovery and composition. Indeed, one of the originality of the proposal is in the nature of the answers the intended system can return when seeking for individuals fitted with given competences: answers may be composite ones in that sense that when no single object meets the search criteria, we attempt to find out what a set of objects, when pooled together, do satisfy the whole search criteria. Conceptual Graphs (CGs) are used as a knowledge representation formalism and operations on graphs are used as a search mechanism. A client/server prototype, viewed as a federation of mediators, has been developed as a proof of concept.

I. INTRODUCTION

A competence management process [START_REF] Berio | Knowledge management for competence management[END_REF] can be achieved following three steps: [START_REF] Berio | Knowledge management for competence management[END_REF] Competence identification: it consists in describing competences under a formal representation. [START_REF] Talantikite | Semantic annotations for web services discovery and composition[END_REF] Competence organization: once represented, competences are organized, classified and structured in order to be efficiently exploited and (3) Competence use: it consists in exploiting the organized competences. In this work, we aim at exploiting the competences for their discovery, i.e. when searching for entities that meet given needs.

Competence management and discovery find their application in different domains, like component-based programming, semanticbased Web services discovery [START_REF] Talantikite | Semantic annotations for web services discovery and composition[END_REF], e-business, human resources management and even enterprise knowledge management [START_REF] Nonaka | The knowledge-creating company: how Japanese companies create the dynamics of innovation[END_REF]. For example, in the e-business domain, we see the application of our work when seeking for possible partners or subcontractors. In human resource management, considering employees enrollment as an example, the application of our wok can be useful when looking for employees satisfying a given work position profile.

In this paper, we aim at proposing a generic approach which can be instantiated in different domains. The ultimate goal is to define a method for competence management and apply the method for competence discovery and composition in distributed knowledge bases. A significant originality of the proposed approach resides in the type of answers we aim at providing. Indeed, when no unique entity satisfies the search criteria, the system attempts to determine a composite answer, i.e. a set of entities that satisfy the whole search criteria, every entity in the resulting set satisfying part of the criteria.

For competence representation and management, we rely on a knowledge representation using Conceptual Graphs (CGs) [START_REF] Sowa | Conceptual structures: information processing in mind and machine[END_REF]: we not only represent knowledge as graphs but the reasoning is made thanks to graph-based operations. From a system architecture point of view, we use a mediator-based architecture [START_REF] Boudjlida | A Mediator-based architecture for capability management[END_REF], i.e. a set of distributed and cooperative mediators.

The presentation of this work is structured as follows. Section II presents related work and the work background. Section III presents the proposed approach for competence management and discovery. Section IV provides an overview of the implementation of the approach whereas concluding remarks are in section V.

II. RELATED WORK AND BACKGROUND

The current work is related to three main bodies of research: (i) Knowledge Representation (section II-A), (ii) competence representation and discovery (sections II-B and II-C) and (iii) heterogeneous and distributed architectures (section II-D). We briefly discuss important studies in these research areas.

A. Knowledge Representation

During the past 40 years, a wide variety of Knowledge Representation (KR) formalisms has been developed. In general, these formalisms fall into two categories: [START_REF] Berio | Knowledge management for competence management[END_REF] those that follow a "logical approach" (like Description Logic [START_REF]Description logics[END_REF]) and provide a general reasoning machinery and a representation language which is usually a variant of the first-order predicate calculus and (2) those that follow a "non-logical approach" (like Semantic Networks [START_REF] Quillian | Semantic memory[END_REF] and CGs [START_REF] Sowa | Conceptual structures: information processing in mind and machine[END_REF], [START_REF] Chein | Graph-Based Knowledge Representation: Computational Foundations of Conceptual Graphs[END_REF]) that use graphical interfaces that enable representing knowledge manipulation according to ad-hoc data structures. CGs are briefly introduced hereafter. CGs are presented as a general model for knowledge representation. They were conceived to represent the semantics of natural languages; they evolved to become complete systems in the sense of logic. A CG description represents ontological knowledge in a structure called support which introduces the vocabulary of the studied domain. The support is implicitly used in the representation of factual knowledge as labeled graphs called conceptual graphs.

The support consists of (an example is in figure 1) (i) a hierarchy of concept types organized around the relation of specialization/generalization, (ii) a set of relation types organized into several hierarchies, each of them organizes relation types having the same arity, (iii) a set of markers or referents (denoted by I in figure 1) that refers to specific concepts (an unspecified concept can be referenced using a generic marker denoted as *), (iv) a conformity relation (τ in figure 1) which relates markers to concept types and (v) signatures of relations which represent all the graphs which express constraints associated with every relation. A signature defines the number of the relation's arguments and their types. A graph signature is constituted by elementary graphs from which we can construct more complex graphs. CGs can have different concrete notations such as graphical representation, textual notation and Conceptual Graph Interchange Format (CGIF) [START_REF] Cgif | Conceptual Graphs Interchange Format[END_REF].

In a graphical notation, called display form (DF) (see figure 2), concepts are represented by rectangles and relations are represented by circles or ovals. The arcs that link the relations to the concepts are represented by arrows. A CGs being a logic system, it can easily be translated under a predicate logic form. As an example, the CG in figure 2 is expressed as: ∃ m ∃ p: Person(p) ∧ Man(m) ∧ father-of(m,p). Furthermore, a variety of operations and extensions [START_REF] Chein | Graph-Based Knowledge Representation: Computational Foundations of Conceptual Graphs[END_REF] are defined on CGs. We recall hereafter those that are necessary to the comprehension of the remainder of this paper.

-Projection: is defined as an application -The Normalization operation returns a graph under a normal form which respects a structure where the markers are unique by merging concepts having the same individual marker. The normal form of a graph avoids semantic and logical ambiguity in CGs. Formally, let H be a CG, and C be the set of its concepts. H is under its normal form if for each couple of concepts (c1, c2) c1 and c2 ∈ C, referent(c1) ̸ = referent(c2).

-The Disjoint sum consists in drawing another CG next to the original CG [START_REF] Nicolov | Sentence generation from conceptual graphs[END_REF]. Formally, let H1 and H2 be two CGs, and let (C1, R1, E1) and (C2, R2, E2) the concept set, the relation set and the edge set of H1 and H2 respectively. The disjoint sum of H1 and H2 is a CG H(C, R, E) such as (1) C is the union of C1 and C2, (2) R is the union of R1 and R2 and (3) E is the union of E1 and E2.

-Headed graphs are graphs that have a certain node chosen as the semantic head.

-Conceptual graph rules [START_REF] Salvat | Raisonner avec des opérations de graphes: graphes conceptuels et règles d'inférence[END_REF] were proposed as an extension of simple CGs to represent "IF A THEN B" knowledge where A and B are simple CGs. Formally, a graph rule is constituted from an hypothesis graph A, a conclusion graph B and a set of attach points corresponding to connection links between A and B. The rule application mechanism in a CG is based on the projection operation.

B. Competence Representation

Competence representation is a sub-field of KR which extends current KR languages to be more suited for competence description [START_REF] Cheng | Competence Management and Discovery in Heterogeneous Environments (Gestion et découverte de compétences dans des environnements hétérogènes)[END_REF]. In [START_REF] Borgida | Adding more dl to idl: Towards more knowledgeable component interoperability[END_REF], competences are methods of object-oriented software. Furthermore, DL is used to describe the intended semantics of these objects and the possible constraints involving their methods. In [START_REF] Bouchikhi | Using larch to specify the behavior of objects in open distributed environments[END_REF], entities are software objects and competences are the capabilities of a software object. In [START_REF] Boudjlida | A Mediator-based architecture for capability management[END_REF], entities are a set of activities (or functions) describing a given domain, an activity being described by the set of the required competences to carry it out. These competences represent the set of properties (or attributes) of the activities and their intended semantic is expressed using DL.

C. Competence Discovery

Competence discovery consists in searching entities having a set of required competences in order to satisfy a given objective. Answers to a competence discovery request may be of two types:

(1) single answers, when single entities satisfy the search criteria, (2) cooperative or composite answers when no single entity, but a set of entities, meets the search criteria. In [START_REF] Cheng | Competence Management and Discovery in Heterogeneous Environments (Gestion et découverte de compétences dans des environnements hétérogènes)[END_REF], competence discovery is defined as a query-answer process that attempts to find out which kind of entities owns a competence, and who they are. In [START_REF] Boudjlida | A Mediator-based architecture for capability management[END_REF], a request X is viewed in term of DL language as a concept having the given competences and the request evaluation consists in locating this concept in the concept classification hierarchy. The answers of a request are the individuals or the instances of all the concepts subsuming X. In an extended work [START_REF] Boudjlida | Complement concept and capability discovery[END_REF], the authors present a method to produce composite answers thanks to the notion of "complementary objects" that is founded on the complement concept in DLs [START_REF] Schmidt-Schauss | Attributive concept descriptions with complements[END_REF].

D. Heterogeneous and Distributed Architectures

In order to satisfy a competence search request in an heterogeneous and distributed environment like Internet, we have to cope with competence descriptions expressed in different formalisms either locally or remotely. This facility requires techniques to transform a competence description from one formalism into another, together with communication between the systems managing the various competence descriptions. Different heterogeneous and distributed architectures are candidate to the implementation of these systems, like Service Oriented Architectures, Peer to Peer (P2P) architectures [START_REF] Bernstein | Data management for peer-to-peer computing: A vision[END_REF], [START_REF] Moore | Adaptable peer-to-peer discovery of objects that match multiple keywords[END_REF] and Mediator-based architectures, the latter being the one we rely on.

A mediation architecture [19] tries to solve the problem of the access and the integration of information by introducing the notion of a mediator as "a software module that exploits encoded knowledge about some sets or subsets of data to create information for a higher layer of application". The mediation can be of two types:

-Centralized mediation: where only one mediator is considered. In this case, all the data sources are stored in the same base.

-Distributed mediation: (or federation of mediators) in which a set of mediators agree to be considered as a single entity when applications demand for services to the federation. Distributed mediation systems have become a reference architecture to integrate both structured and semi-structured data [19], [START_REF] Papakonstantinou | Medmaker: A mediation system based on declarative specifications[END_REF]. In addition, many mediator-based approaches have been proposed in the literature. In [START_REF] Tönshoff | A mediatorbased approach for decentralised production planning, scheduling and monitoring[END_REF], a single mediator is designed to offer an adequate level of decision-making integration of heterogeneous computer systems. The Conflict Resolution Environment for Autonomous Mediation (CREAM) system has been implemented and it provides various user groups with an integrated and collaborative facility to achieve semantic interoperability among participating heterogeneous information sources [START_REF] Ram | Cream: A mediator based environment for modeling and accessing distributed information on the web[END_REF]. The KRAFT (Knowledge Reuse And Fusion/Transformation) architecture provides a generic infrastructure for knowledge management applications. It supports virtual organization using mediator agents [START_REF] Preece | A mediator-based infrastructure for virtual organisations[END_REF]. In [START_REF] Boudjlida | A Mediator-based architecture for capability management[END_REF], [START_REF] Boudjlida | Complement concept and capability discovery[END_REF], [START_REF] Cheng | Capability management and discovery in description logic[END_REF], [START_REF] Cheng | An architecture for heterogenous federated mediators[END_REF], an architecture based on a heterogeneous federation of mediators has been adopted. In this architecture, great emphasis is on cooperation and heterogeneity aspects. Now, let us turn toward our actual proposal for competence management and discovery.

III. PROPOSAL: COMPETENCE MANAGEMENT AND DISCOVERY USING CGS

In this section, we present the approach we propose for competence management and discovery using conceptual graphs as a competence representation formalism and operations on graphs as a reasoning mechanism. The mediator-based architecture, as well as the system architecture, will be described in section IV.

A. Conceptual Architecture

In the proposed approach, a mediator-based architecture has been adopted as described in [START_REF] Boudjlida | A Mediator-based architecture for capability management[END_REF]. It is very similar to the notion of discovery agency in the Web service architecture [START_REF] Cheng | Capability management and discovery in description logic[END_REF]. In this architecture, an "entity", called exporter, publishes its competences at one or more mediators (arrow (a) in figure 3). Entities, called importers, send requests to the mediator asking for exporters fitted with a given set of competences (arrow (b) in figure 3). The mediator explores its competence base to try to satisfy the request. The competence search process is founded on the exported competences and on relationships between them, these relationships being transparently established by the mediator. When the request can be satisfied by some exporters, the references of these exporters are sent back to the importer (arrow (c) in figure 3).

In this architecture, some cases may conduct to a failure of the request when only one mediator is involved. But, if we assume a grouping of mediators, these cases are typical cases where cooperation of mediators is required. When a mediator partner fails in the satisfaction of a request, we need to determine what is missing to the entities to satisfy request. That missing part is then transmitted to a mediator in the federation who, in turn, behaves like the preceding mediator. Therefore, satisfying a request may fall 1. there exist exporters that fully satisfy the request; 2. there exist exporters that partly satisfy the request but, when "combining" or composing the competences of different exporters one can fully satisfy the request; 3. no single exporter nor multiple exporters satisfy the request. In the latter situation, the mediator may initiates a cooperation process with other mediators to attempt to satisfy the request (arrow (d) in 3).

In addition, in a federated mediator architecture, the competence discovery can fall under the following situations:

1. Homogeneous local satisfaction where the request and the knowledge base are in the same KR language, and the knowledge base is located in one server.

Homogeneous distributed satisfaction:

where the request and the knowledge base are in the same KR language, and the knowledge base is distributed in several servers.

Heterogeneous satisfaction:

where the request and the knowledge base are in different KR languages and the knowledge base may be distributed.

In this work, we only deal with the homogeneous distributed satisfaction.

B. Competence Representation

Using CGs, competences are represented by relations and entities are represented by concepts. For example, saying that a programmer p has competences in Java programing is represented as shown in figure 4. However, the simple CG model does not allow to adequately represent entities and their competences. Indeed, in a simple CG model, the semantic of a concept type or a relation type is only given by its position in the type hierarchies; the only mechanism that enables defining a type is the specialization/generalization relation. This representation of types is poor and misses a lot of expressivity to represent generic information about types and also some relation properties such as transitivity, symmetry and reflexivity. To deal with these problems, we propose to use CG rules as described hereafter. 1. Concept type definition: To represent generic information about concept types, these types must be defined. "Concept type definition" is defined here as "an either necessary or necessary and sufficient conditions that entities must verify in order to belong to a concept type". These conditions are formalized using conceptual graph rules. For example, the concept type Mother defined as a "woman that is mother of a person" is defined as follows:

Relation type definition:

In the same way, a "Relation type definition" is "an either necessary or necessary and sufficient conditions which must be verified in order to belong to a relation type". For example, the relation type grandmother of can be defined as follows: 3. Meta-knowledge on relations: Relation properties are also formalized using CG rules. For example, the following rules enables expressing the fact that the relations parent of and child of are symmetric ones:

( ( As a result of the rule-based representation we propose, the domain representation is composed of (1) Ontological knowledge, represented by the support, to which we add a component named "Rule base" (RB) containing the set of rules used to define the types and the relation properties and, (2) Factual knowledge, represented by CGs labeled from the support. In this work, CGs serve for representing entities together with their acquired competences. Each graph is then published in one of the mediators of the federation. The set of the competences that are published in a given mediator are collected into a single CG named "Competence Base" and denoted as CB.

A CB is built and updated every time where a new competence (represented by a CG noted P) is published. For each published graph P, we follow the three following steps:

(1) Disjoint sum of the graphs P and CB in order to add published competences to the CB.

(2) Normalize the graph CB: this normalization avoids graph redundancy and then minimizes the search space.

(3) Apply the rules that are present in RB on the graph CB. This is a very important step : it allows reasoning over the CB in order to add all implicit knowledge that is not directly published into the CB.

C. Competence Discovery

Section III-C1 presents the representation of a request while sections III-C2 to III-C3 present its satisfaction process.

1) Request Representation:

The request is represented as a headed CG form noted RG in which: (i) The searched entities are represented by the head t of RG. We introduce a special marker ? logically equivalent to the * marker in order to indicate such a node. (ii) The requested competences are represented by relations which are directly attached to the node t.

(iii) The rest of RG represents conditions on the requested competences.

For example, seeking for men having some competences in UML (Unified Modeling Language) and some competences in programing using languages that support classes is represented as shown in figure 5.

2) Local Request Satisfaction:

The local satisfaction of a request R runs as follows: (i) Normalize R in order to minimize its size and as a consequence to minimize the search and to avoid logical and semantic ambiguities, (ii) delete from R all the connected components that do not contain the head t, because these components are independent from the searched entities, (iii)Project R on BC and (iv) if at least one projection is found, then there is at least one single answer to the request. Answers are then all the projections (images) of the head node t. Otherwise, search for possible composite answers to the request.

As an example, the satisfaction of the request R in the left part in figure 6 is the circled concept, the right part of the figure being the concept base.

In order to find possible composite answers to a request R, we decompose R into sub-requests where every sub-request consists in searching entities having one of the required competences and we proceed as follows: (i) Decompose R into n sub-requests Ri(i ∈ [1, n]), each Ri containing the head of R connected to one of the sub-graphs representing a discovery request for one competence, together with conditions on it (see section III-C1).

(ii) Satisfy all the sub-requests, one independently from the others. (ii) If all the sub-requests are satisfied then composite answers are the compositions of the answers of the sub-requests.

As an example, to find composite answers to the request in figure 5, R is decomposed into two sub-requests (figure 7).

In addition, the satisfaction of a sub-request Ri proceeds as follows: 3) Cooperative Request Satisfaction: In a federation of mediators, part of a sub-request Ri may be satisfied in one of the mediators of the federation whereas another part may be satisfied in another one. In term of conceptual graphs, this means that a part of the graph that represents Ri may be projected on the CB in one mediator whereas another part may be projected on the CB in another one, as illustrated in the following example, considering the sub-request R2 in figure 7.

Assume that two mediators M1 and M2 are available (figure 8 shows parts of their competence bases denoted CB1 and CB2 respectively). In both the mediators, only a part of R2 is satisfied: in CB1, there is a person having java-programming competences and in CB2, we know that java supports classes. So, in order to satisfy a subrequest in a federation, it is sufficient to find which parts of Ri can be projected on the CB of a mediator and which parts cannot. However, the projection operation such as defined in the CG formalism does not allow to find this type of information. For that reason we propose to proceed according to the following steps: Step1: Decompose Ri into elementary parts containing only one relation. For example, the sub-request R2 in figure 7 is decomposed into two parts (figure 9). Step2: Project these parts on each CB in the federated mediators:

(1) The projection of the two parts on CB1 is shown in figure 10.

(2) Add the projection of the two parts on CB2 (figure 11). Step3: Check whether the projections can be joined and if they do, then the sub-request is satisfied and the satisfactions are the projections of the sub-requests' heads (see the dotted parts in figure 12). Let us now describe the prototype we developed as a support of our proposals.

IV. IMPLEMENTATION

For an experimental validation of the proposed approach, we implemented a prototype using many software components. There exist several tools which implement CGs in particular for research purposes and for information extraction [START_REF]Cogitant : Conceptual graphs integrated tools allowing nested typed graphs[END_REF]- [START_REF] Southey | Notio -a java api for developing cg tools[END_REF]. However, few of these tools offer a complete software environment for the widest possible use of the model: the storage and the manipulation of a large number of graphs. For that reason, we choose to use the CoGITaNT library (Conceptual Graphs Integrated Tools allowing Nested Typed graphs), a library of C++ classes (open source, developed at LIRM Montpellier, CNRS, France) which allows developing applications based on the CG knowledge representation scheme.

We illustrate hereafter the prototype functioning thanks to examples. We present first, the domain population and then examples of competence discovery.

1) Domain population: as an example, we consider the computer science competence management domain represented in terms of a concept type hierarchy (figure 13), a relation type hierarchy (fig- 3) A local query-satisfaction example is shown in the figure 17, in which graph2 denotes the query. 4) A distributed query-satisfaction example: the figures 18 and 19 illustrate the result of the query denoted as graph1 in the figure 18.

V. DISCUSSION AND CONCLUDING REMARKS

In this paper, we presented an approach for competence management and discovery using conceptual graphs (CG) to provide a semantic description of an application domain. Acquired competences are organized under a CG form that is built and updated every time a new competence is published. The advantage of this organization form is that the application of graph rules at publication time facilitates the search and may reduce the response time, since all implicit information are available thanks to the application of these rules at publication time. For competence discovery, we use operations on graphs and the projection is used as a basic operation in the discovery process. For distributed satisfaction of a request, we use another form of graph decomposition where a sub-request is decomposed into elementary parts containing only one relation. In addition, for experimentation purposes, we implemented a federated mediation prototype based on the client/server architecture of COGITANT [START_REF]Cogitant : Conceptual graphs integrated tools allowing nested typed graphs[END_REF]. The prototype is fully written in C++ programming language and it has been successfully verified under Linux and MICROSOFT Windows XP operating systems.

Further work is to consider the complexity of the search algorithm and to cope with heterogeneous mediators cooperation, i.e. mediators where knowledge bases are described in different languages. An additional on-going research topic concerns the dynamic and semanticbased identification of possible cooperating mediators for unsatisfied parts of a competence request together with a performance comparative analysis of a P2P implementation against an implementation using cloud computing technology.

Fig. 1 .

 1 Fig. 1. Conceptual Graph Support

Fig. 2 .

 2 Fig. 2. Conceptual Graph Example In a textual notation, called linear form (LF), concepts are represented by square brackets and relations are represented by parenthesis. Under a LF notation, the CG of figure 2 is expressed as: [Man: *]→(fatherof)→[Person: *]. The CGIF notation has a syntax that uses co-reference labels to represent the arcs. The example in figure 2 is expressed in CGIF as: [Man: *m] [Person: *p] (father-of ?m ?p). *m and *p are variable definitions and ?m and ?p are references to defined variables.

∏

  of the nodes of a graph H towards the nodes of a graph G such as: (1) for each concept c in H, ∏ (c) is either a specialization or the same as c, (2) for each relation r in H, ∏ (r) is either a specialization or the same as r, (3) if the i th edge of r is linked to a concept c in H, then the i th edge of ∏ (r) must be linked to ∏ (c) in G.

Fig. 3 .

 3 Fig. 3. The Mediator-Based Architecture under different cases [12]:1. there exist exporters that fully satisfy the request; 2. there exist exporters that partly satisfy the request but, when "combining" or composing the competences of different exporters one can fully satisfy the request; 3. no single exporter nor multiple exporters satisfy the request. In the latter situation, the mediator may initiates a cooperation process with other mediators to attempt to satisfy the request (arrow (d) in 3).

Fig. 4 .

 4 Fig. 4. Competence Representation Example

[

  M other : * x] ⇒ [W oman :?x] → (mother of ) → [P erson : * ] W oman : * x] → (mother of ) → [P erson : * ] ⇒ [M other :?x].

[

  W oman : * x] → (grandmother of ]) → [P erson : * y] ⇒ [W oman : * x] → (mother of ) → [P erson : * ] → (parent of ) → [P erson :?y]. [W oman : * x] → (mother of ]) → [P erson : * y] → (parent of ) → [P erson : * y] ⇒ [W oman :?x] → (grandmother of ) → [P erson :?y].

  ) [P erson : * x] → (child of ) → [P erson : * y] ⇒ [P erson : * y] → (child of ) → [P erson :?x].

  ) [P erson : * x] → (parent of ) → [P erson : * y] ⇒ [P erson :?y] → (parent of ) → [P erson :?x].

Fig. 5 .

 5 Fig. 5. A Request Example

Fig. 6 .

 6 Fig. 6. A Local Request Satisfaction Example

Fig. 8 .

 8 Fig. 8. Competence Base Examples

Fig. 9 .

 9 Fig. 9. Sub-Request Decomposition Example.

Fig. 10 .

 10 Fig. 10. Sub-Request Parts Projection on CB1

Fig. 12 .

 12 Fig. 12. Sub-Request Satisfaction Verification

Fig. 13 .

 13 Fig. 13. The Concept Hierarchy ure 14), rules used to define concept types, relation types and relations properties.

Fig. 14 .

 14 Fig. 14. The Relation Hierarchy

Fig. 15 .

 15 Fig. 15. Competence Base of the Mediator M1.

Fig. 16 .

 16 Fig. 16. Competence base of the mediator M2.

Fig. 17 .

 17 Fig. 17. Local satisfaction of a request


Mihai Pâslariu

Nacer Boudjlida

A wireless library for the Nintendo dual screen (DS) game console 1

Keywords: Computer Games, Video Game, Multiplayer, Wireless

Due to the popularity of multiplayer games, all of today's gaming consoles have wireless capabilities. However, in order to write the network related part of such a game, the programmer is required to understand and use a low level and difficult API. We address this issue by creating a networking engine that needs to be both efficient to run on the limited resources offered by a gaming console, but also easy to use in order to shorten development time. In this paper we first explain the need for such an engine, then we continue with some theoretical background and finally we present and discuss our results.

Introduction

A multiplayer video game is a game where more than one person can play in the same game environment at the same time. Adding a multiplayer component to a Video game involves a lot of work in designing the network model, in implementing communication between devices and in thoroughly testing the game. This leads to increase the development time. A possible solution to the problem is the use of an application independent network engine [START_REF] Mihai | Wireless Library for the Nintendo DS[END_REF] that can be easily integrated in any game without requiring a lot of extra work. The work which is described hereafter takes exactly this approach, to design a reusable engine that will exploit the wireless capabilities of the Nintendo Dual Screen (DS) and also allows a rapid integration in any application. The end result of this work is a C++ code library.

In addition, the engine had to meet the following requirements: (i) be conform to the requirements imposed by Nintendo for its game titles, (ii) use minimal resources and (iii) have a user-friendly interface in order to allow fast development of multiplayer games. The paper is structured as follows: section 2 introduces the problem statement and the formal background of this work, section 3 details the structure and the role of every component in the library we propose, section 4 discusses our results especially from a performance point of view and finally, section 5 includes concluding remarks and further work.

Problem Statement and Theoretical Background

Video Game Consoles

There are a few elements common to all game consoles: controllers, power supply, core unit, game media and memory card. This work focuses on a game console called Nintendo DS. A detail that should be noticed, since it impacted this work, is that the ARM processor [START_REF] Michael | ARM Stack Unwinding[END_REF] in the Nintendo DS does not have floating-point support. So, we had to emulate the floating point operations. Further, the Nintendo DS has built-in 802.11 wireless network connections [START_REF] Goldsmith | Wireless Communications. Chapter: Overview of Wireless Communications[END_REF] compatible with the only Wireless Equivalent Privacy (WEP) encryption) using a proprietary protocol.

Wireless Networks

Wireless networks can be classified into: managed networks and ad-hoc networks. Managed networks always contain a special node (called the access point) that manages communication among other nodes. In managed networks, wireless access has special security considerations so most modern access points come with built-in encryption. An ad-hoc network [START_REF] Chai | Ad Hoc Mobile Wireless Networks: Protocols and Systems[END_REF] is a network connection method which is most often associated with wireless devices. The connection is established for the duration of one session and requires no base station. Instead, devices discover others within range to form a network. Devices may search for target nodes that are out of range by flooding the network with broadcasts that are forwarded by each node. Connections are possible over multiple nodes (multihop ad hoc network). Routing protocols then provide stable connections even if nodes are moving around.

Interpolation/Extrapolation

In a typical video game, there is one device (a server) that decides the state of the game. All the other participants periodically receive snapshots or updates with the state. When communicating through a protocol where packet loss can happen, the data packets that contain the state may get lost. Loosing packets can cause an incorrect movement of objects on the screen. Even if the packets reach their destination, the delay between sending and receiving them can cause the same effect if it is too high. To partly hide this problem from the user, many games use interpolation and extrapolation algorithms [START_REF] Fritsch | The Effect of Latency and Network Limitations on MMORPGs (A Field Study of Everquest2)[END_REF][START_REF] Neil | Haste". Lag Compensation Technique and Code that does it[END_REF].

Interpolation is a method of constructing new data points within the range of a discrete set of known data points [START_REF] Autar | Spline Interpolation[END_REF][START_REF] Charles | Cubic Spline Interpolation[END_REF]. On the other hand, extrapolation is the process of constructing new data points outside a discrete set of known data points. It is similar to the process of interpolation but its results are often less meaningful, and are subject to greater uncertainty. The current engine implements interpolation algorithms whose results are discussed in section 4.

The Wireless Library

The library has four important components: ad-hoc wireless, resource sharing, Internet communication and interpolation (see Figure 1.) In the following, we will have a look at what each component does, the approach used to solve the problem and the reason for it. To simplify the development, many methods in the engine are synchronous, thus they only finish after the operation is completed. Whenever possible, an asynchronous alternative is also available. Furthermore, if a standard component already exists it is included in the engine so the resulting application will have the same look as other Nintendo DS titles. One of such an example is the Internet connection utility, a small application that can scan for an access point and configure the Internet connections.

The Ad-hoc Networks Component

This component provides routines to allow two or more Nintendo DS devices to connect to each other and exchange messages through the wireless connection. In most ad-hoc networks, all peers have the same functions but, due to restrictions on the DS, we will choose one console to be the server and the rest will be the clients. The server device will control the communication parameters and intermediate all communication between client devices.

The engine contains classes for both server and client. The server broadcasts a beacon message and waits for clients to connect to it. The clients scan for the servers beacon and then establish a connection to the server. After the communication is established, actual communication is performed thanks to send/receive-like functions. This component also features support for WEP encryption. A client that is not configured to use WEP cannot connect to a server with a WEP encryption but a client configured to use encryption can connect to an unsecured server. The engine also has methods to get the connection strength and to configure wireless parameters like the channel to use, the amount of time to scan a specific channel or the time interval at which to send beacon information.

These communication methods allow a user to write multiplayer games much faster than programming directly with the low level API of the device. As

The Resource Sharing Component

This component features the ability to share an executable game code on devices that do not have it, as well as a mechanism to use files through the network as if they were local.

The first part, sharing an executable, is called "Download Play [START_REF] Nintendo | Nintendo DS Lite, Nintendo DSi-Wireless Router Information[END_REF] and it enables users to play multiplayer games with other Nintendo DS systems using only one game card. Players must have their systems within wireless range (up to approximately 30 meters) of each other and the guest system to download the necessary data from the host system. However, the "Download Play" feature can only share a binary executable file. To share resource files, we offer classes that allow a device to share its files with other devices. This is especially useful for transferring the rest of the game after the executable was downloaded by the guest device. An application that wants to use this feature typically does the following operations:

1) A Nintendo DS device with a game card starts a game and shares it.

2) Other devices connect to it and start downloading the game: the only executable is transferred on the client. 3) After the download, the game is started. 4) The server DS device can then share its resource files. 5) Client devices, that are now running the game, can retrieve files from the server's file system.

The Internet Connection Component

This component allows a Nintendo DS device to connect to the Internet and access a wide range of services. It provides the following services: a) Internet connection: This component enables configuring the connection to the Internet, initializing the library and running the connection process. b) Authentication is a component to authenticate the user on the server to facilitate the user's access to the Internet. This authentication is done internally and does not require the user to enter any user-name or password. c) Friend management is a feature that keeps a list of friends. Friend lists are used for matchmaking, to create multiplayer games between players that know each other. d) The communication component offers reliable and unreliable data transmission using protocols from the TCP/IP stack. Internet services} is a component that offers support for services like matchmaking, ranking, storage, etc.

The Utility Component

We implemented interpolation and extrapolation algorithms to help the application hide the effects of packet loss and of network lag. The interpolation/extrapolation classes make use of templates to let the user decide which data type to use for storing points. The example below shows how to use these algorithms in an application: The major limitation in the use of interpolation algorithms on the Nintendo DS is the lack of floating point instructions on the processor. Although it is possible to emulate floating point instructions, this is not usually an option since it dramatically decreases performance. Using integer numbers, the performance is good but the disadvantage is that numeric errors can frequently occur. Most of the algorithms work with both floating point and integers if the values of points and timestamps are in certain documented interval. Another offered feature is the physics interpolator. Given the fact that many games nowadays have a physics engine and most in-game objects move according to the laws of Newtonian physics, we created a new type of interpolation, that tries to guess the values for distance, speed and acceleration and then use them to interpolate or extrapolate the position at any given time.

LinearInterpolator<int, 2>
This utility component also features cryptography related functions. It can encrypt/decrypt sets of data with various algorithms, it can create digests and it can verify digital signatures.

Results

We have run several tests for performance evaluation. Due to the limited space in this paper and since some of the results are confidential, we only discuss two of them. Result 1 -Client-Server transfer rate measurement: Many factors may influence transfer speed between two devices, among these: a) the type of communication (reliable or unreliable), b) the distance between devices, c) the interference from other wireless devices, d) other tasks executed on the processor of the device at the same time, e) the size of the message that is sent, f) the size of the buffer, g) the number of client devices connected to a server, and so on.

In figure 2 we measured transfer rate from a client to the server for multiple message sizes and with different numbers of connected clients. Sending fewer larger data packets increases the performance over sending more smaller packets. Fig. 2: Transfer speed from a client to the server For example, sending 896 bytes at once instead of 7 bytes 128 times can increase performance up to almost 60 times. The second conclusion is that the communication speed varies with the number of clients. This is because the buffer on the server is divided between the clients, so less data is served to them.

Result 2 -Interpolation: For the interpolation component there are two parameters to test: accuracy and speed. The main parameters that affect performance are the algorithm used for interpolation and extrapolation, the data type used for storing points (integer or floating point), the data structure used for points (vectors, lists, ...) and even compiler optimizations. But, as already stated, the processor on the Nintendo DS does not support floating point operations, so they are emulated in software. This induces a performance penalty. In figure 3, the difference between floating points and integers is clearly visible.

These measurements show the number of microseconds that each algorithm needs to execute the two important actions: adding a new data point and interpolating/extrapolating between two points. The two versions, debug and release, are presented here to show the amount of optimization done by the compiler. We can see that the amount of compiler optimizations is greater for those algorithms that do more mathematical computations: like physics, cubic, quadratic or tangent. The data structure used to stored points is not included in the test since it does not influence the results. Another conclusion is that some algorithms do more work when adding data while others spend more time in the interpolation method. We can see that the quadratic spline, cubic spline, tangent and physics algorithms do significant computations when adding a new point. That's where the equations of the spline or movement are calculated. We can also see that all the algorithms take approximately the same amount of time to interpolate because the interpolation procedure is a simple matter of applying a formula for a given point. Many additional conclusions can be drawn: (i) Linear interpolation algorithm is the fastest and its results are good enough for many applications, (ii) Cubic interpolation produces the best results but it is slow and it may produce numeric errors, (iii) Quadratic interpolation produces severe oscillations and it is provided only for completeness, (iv) Other algorithms, like the physics ones, are very effective in particular situations.

Concluding Remarks

We have designed a network engine for the Nintendo DS gaming console that makes developing multiplayer games very easy. It offers to the programmers a simple API and allows them to write the networking part of the application very fast which, in turn, significantly reduces the development time of the game.

Regarding future work, the engine may be expanded to work with other game consoles or even with mobile devices such as smartphones. And finally, the ultimate goal is to develop a commercial Nintendo DS game using the developed engine.

Fig. 1 :

 1 Fig.1: The Structure of the Network Engine.

Fig. 3 :

 3 Fig.3: Interpolation results.

  an example, the code below is all what is needed to write a client program:

	Client client;
	ServerInfo server; Socket socket;
	// scan indefinitely for one server
	client.scan(&server, 1);
	// connect to the server
	if ( ! client.connect(&server) ) { // treat error or retry }
	// create a socket
	socket.startOnClient(&client, SAFE_PORT, &listener);
	while (game_is_running) { // … game code ..
	// send a message to the server
	socket.send(buffer, size);
	// receive 100bytes
	socket.receiveAll(buffer, 100); }
	// stop client
	client.close();

Acknowledgements

M. Pâslariu is indebted to the members of the studio Le Caillou Information Multi-Services (Paris, France) for the very welcoming working environment. He is also indebted to the "Lorraine's Universities' Friends" Association (AUL) for its awards of this work.


Rodrigo A Vaca Ramírez

Eitan Altman
email: eitan.altman@inria.fr

John S Thompson
email: john.thompson@ed.ac.uk

Víctor M Ramos

A Stable Marriage Framework for Distributed Virtual MIMO Coalition Formation

In this paper, a distributed algorithm for energy efficient virtual Multiple-input Multiple-output (MIMO) coalition formation is proposed. We model cooperation as a game theoretic approach derived from the concept of stable marriage with incomplete lists (SMI). Thus, single antenna devices such as mobile and relay stations are allowed to cooperate in order to improve the user's and system's energy efficiency. Our approach is focused on optimizing the circuit consumed power of the single antenna devices rather than on the transmitted power, thus the total device power consumption including the effect of the power amplifiers is taken into account. Furthermore, we show analytically and by simulation that under certain conditions cooperation does not improve the energy efficiency metric of network users, thus single antenna devices prefer to transmit independently in order to maintain the user's performance in the network. Additionally, our distributed approach reduces the communication overhead by 76% when compared with a centralized global optimum scheme, which is coordinated from the base station.

I. INTRODUCTION

Multi-antenna systems have emerged as an effective way to improve capacity and energy efficiency in wireless networks. It has been shown in [START_REF] Paulraj | Introduction to space-time wireless communications[END_REF] that Multiple-input Multiple-output (MIMO) systems require less transmitted power to achieve the same rate requirements than single antenna systems. In fourth generation (4G) networks such as Long Term Evolution (LTE), a base station (BS) can be equipped with multiple antennas. Nevertheless, mobile stations (MSs) may not support more than one single antenna due to physical constraints [START_REF] Jiang | Energy efficiency and optimal power allocation in virtual-MIMO systems[END_REF][START_REF] Sesia | LTE-The UMTS Long Term Evolution From Theory to Practice[END_REF]. Fortunately, if we allow individual single antenna devices such as mobile and relay stations to cooperate with each other on information transmission, a virtual MIMO link can be constructed [START_REF] Paulraj | Introduction to space-time wireless communications[END_REF][START_REF] Jiang | Energy efficiency and optimal power allocation in virtual-MIMO systems[END_REF].

Cooperation in virtual MIMO systems allows a wireless user to obtain important gains in spectral and energy efficiency. However, the design of an efficient cooperation algorithm faces various challenges. On one hand, cooperation costs such as power expenditure can limit the benefits or even degrade the user's performance. On the other hand, if cooperation between wireless nodes is coordinated by a centralized entity, an extra signaling overhead is required for information exchange to set up and maintain the cooperative link. Thus, the design of a distributed algorithm that allows the single antenna devices to autonomously decide "when to cooperate" and "with whom to cooperate" is highly challenging but desirable in practice [START_REF] Saad | A distributed coalition formation framework for fair user cooperation in wireless networks[END_REF].

Energy efficiency has become an important research topic for mobile stations due to their limited battery resources. Moreover, in mobile stations most of the power expenditure is due to the radio frequency (RF) circuits [START_REF] Jensen | LTE UE power consumption model for system level energy and performance optimization[END_REF]. However, current research in energy efficiency has been mainly focused on reducing the transmitted power rather than on reducing the total consumed power of the MS [START_REF] Burchardt | Uplink interference protection and scheduling for energy efficient OFDMA networks[END_REF]. Hence, taking into consideration the power amplifiers' effect for reducing the total consumed power is crucial for improving the MS's battery life, and maintaining the overall MS performance in the network [START_REF] Bobae | A dual-mode power amplifier with on-chip switch bias control circuits for LTE handsets[END_REF].

The main contribution of this paper is to provide a distributed coalition formation framework, which allows single antenna devices to cooperate and form a virtual MIMO link, in order to reduce the energy consumption in the network. Additionally, it is shown analytically and by simulation that under certain conditions forming a virtual MIMO channel does not provide an energy efficient solution, when the circuit power consumption is considered.

The remainder of this paper is as follows, in Section II we present the problem scenario and performance metrics. In Section III, we describe our cooperative framework. A summary of the comparison schemes and the simulation scenario are described in Section IV. Results are presented in Section V. Finally, Section VI offers concluding remarks.

II. SYSTEM SCENARIO AND PERFORMANCE METRICS

In this work, we consider N mobile stations (MSs), all of them equipped with a single antenna sending data on the uplink to a multiple antenna base station (BS). Additionally, R single antenna relay stations (RSs) are uniformly distributed through the cell, assuming R ≫ N . When cooperating, the single antenna devices (MSs and RSs) form a virtual 2 × M r MIMO link, where M r is the number of antennas at the BS side. If cooperation is not possible, the MSs will transmit to the BS on their own in (Single-input Multiple-output) SIMO mode.

The system bandwidth B (Hz) is divided into X resource blocks (RBs). Hence, an orthogonal frequency division multi- ple access (OFDMA) system is constructed, where each RB is assigned to each coalition independently to avoid co-channel interference (CCI). In this paper the term coalition refers to a single user MIMO or SIMO respectively. In Fig. 1, we show an illustration of the system scenario.

A. Channel Model 1) Reverse Link: The uplink received signal at the base station (BS) separated by a distance d k from a coalition k is determined by path loss, log-normal shadowing, and channel variations caused by fading. We assume a flat fading Rayleigh channel, thus the fading coefficients of a 2 × M r MIMO channel may be represented by a matrix

H =      h 1,1 h 1,2 h 2,1 h 2,2 . . . . . . h Mr ,1 h Mr,2      , (1)
where each entry is a Zero Mean Circulant Symmetric Complex Gaussian (ZMCSCG) random variable with unit variance [START_REF] Paulraj | Introduction to space-time wireless communications[END_REF]. SIMO systems can be treated as a special case of MIMO, where the channel is represented by a vector h = [h 1 , h 2 , . . . , h Mr ] T . In addition, path loss and shadowing are modeled as a power fall off that further attenuates the transmitted signal, hence the average power of the received signal P r can be expressed as follows [START_REF] Burchardt | Uplink interference protection and scheduling for energy efficient OFDMA networks[END_REF]:

P r = P t 10 -L(d k )+Xσ 10 , (2)
where P t represents the power of the transmitted signal, X σ is the log-normal shadowing value (dB) with standard deviation σ, and L(d k ) is the distance-dependent path loss (dB), which is calculated as follows:

L(d k ) = 15.3 + 37.6 log 10 (d k ). (3)
When a MIMO coalition is formed, cooperation is made using a short range transmitter, hence it can be assumed that the single antenna devices are close enough to experience the same channel statistics, thus shadowing and path loss remain the same for the devices forming a virtual MIMO link.

The channel is assumed to be known at the transmitter and receiver. Thus, the received signal at the BS may be expressed as

y k = P r M t Hws + n, (4)
where y k is the received signal at the BS from the k-th MIMO coalition, M t is the number of transmitting antennas per coalition, s is the information symbol with unit energy, n is the noise, and w is a complex weight vector, that must satisfy w 2 F = M t to constrain the total average transmitted power, where • 2 F is the Frobenius norm. It should be noted that for a SIMO coalition Eq. ( 4) becomes: y k = √ P r hs + n. Furthermore, the signal-to-noise ratio (SNR) for a MIMO coalition is given by [START_REF] Paulraj | Introduction to space-time wireless communications[END_REF]:

η k mimo = g H Hw 2 F P r M t g 2 F ρ , ( 5
)
where g is an M r × 1 vector of complex weights which multiplies y k at the BS side and ρ is the noise power. Hence, maximizing the SNR at the receiver is equivalent to maximizing g H Hw 2 F / g 2 F . By using singular value decomposition (SVD) the channel matrix can be represented as H = UΣV H , where the columns of V and U are known as the input and output singular vectors respectively, and Σ = diag{σ 1 , σ 2 , ..., σ j } with σ i ≥ 0, where σ i is the i-th singular value of the channel, and j is the rank of H. Thus, the right choice of w/ √ M t and g that maximizes the SNR are the corresponding input and output singular value vectors corresponding to the maximum singular value σ max of H [START_REF] Paulraj | Introduction to space-time wireless communications[END_REF]. Therefore, the received SNR at the BS side from the k-th MIMO coalition may be expressed as follows:

η k mimo = σ 2 max P r ρ , (6)
In the case of a SIMO coalition, the received SNR at the BS may be expressed by [START_REF] Paulraj | Introduction to space-time wireless communications[END_REF]:

η k simo = h 2 F P r ρ , (7)
2) Cooperative Link: If cooperation is achieved, the cooperative link between the MS-n and the RS-r link is modeled as following κ th -power path loss (loss ≈ 1

d κ nr
) with Additive White Gaussian Noise (AWGN). Hence, the received power P nr from the signal transmitted from the MS-n to the RS-r is expressed as follows:

P nr = P tcop d κ nr ( 8
)
where P tcop is the transmitted power for cooperation and d nr is the distance between the MS-n and the RS-r. Hence, the signal-noise ratio (SNR) at the RS side is given by

η nr = P nr ρ (9)
3) Virtual MIMO Link: In Fig. 2 a virtual 2 × M r MIMO link is shown. The MS forwards the information symbol s to the RS using the cooperative (short range) link. Furthermore, in the reverse link the MS and RS transmit the symbol s to the BS through the MIMO channel H. The reverse and cooperative link are designed orthogonal to each other, in order to prevent mutual interference.

B. Physical Components Power Consumption Model

In this paper, we consider the circuit power consumption of the MS's and RS's components, which is due to information transmission in the reverse and the cooperative link. The reverse link power consumption is dependent of components such as the baseband (BB) module and the radio frequency (RF) module. The former comprises the power consumed for the baseband signal processing (e.g., channel coding and decoding), and the latter incorporates the power consumption of the radio frequency components (e.g., the power amplifier). Hence, in order to model the power expenditure of both modules, we adopt the model presented in [START_REF] Jensen | LTE UE power consumption model for system level energy and performance optimization[END_REF], where the authors make an analysis of the power consumption of both modules for a Long Term Evolution (LTE) MS. Hence, the total power consumed in SIMO transmission mode P tot simo only depends on the transmitted power in the uplink P t . Additionally, the total consumed power to form a virtual MIMO link P tot mimo is a function of the transmitted power in the cooperative link P tcop , the transmitted power in the uplink P t , and the distribution of the transmitted power between the MS and the RS, which is due to the weight vector w. Hence, the total consumed power for a SIMO and MIMO coalition is modeled by

P tot simo (P t ) = P circ (P t ) (10)
where P circ is the circuit power consumed in the reverse link, P circop is the circuit consumed power in the short range link (cooperative link), and w ms and w rs are the elements of the weight vector w for the MS and RS respectively in a 2 × M r MIMO channel. Furthermore, a power amplifier array is assumed to model the circuit consumed power of the RF module [START_REF] Jensen | LTE UE power consumption model for system level energy and performance optimization[END_REF][START_REF] Bobae | A dual-mode power amplifier with on-chip switch bias control circuits for LTE handsets[END_REF], as presented in Fig 3 . The power amplifier array is constructed based on a low power amplifier (LPA) and two high power amplifiers HPA 1, and HPA 2, where the power amplifier efficiency is assumed equal for both high power amplifiers; however HPA 2 is designed to transmit up to the half of the maximum transmitted power of HPA 1. Therefore, the circuit power consumption in the uplink P circ [W] is obtained by: 10) and (11), and A is a set of constant values defined as follows [START_REF] Jensen | LTE UE power consumption model for system level energy and performance optimization[END_REF]:

P circ (P t * ) =            2 + 0.
A = P T x + P con -P BB [W ], (13)
where P T x is the base power that the RF chain consumes in transmission mode, P con is the MS's power consumption when connected to the BS, and P BB is the power consumed by the BB module [START_REF] Jensen | LTE UE power consumption model for system level energy and performance optimization[END_REF].

As we have stated, the cooperative link is a short range communications link, thus in order to model its circuit power consumption P circop , we use the LPA model:

P circop (P tcop ) = 2+0.005(P tcop )-A [W ] 10 ≥ P tcop (dBm) (14)

C. Performance Metrics

The achievable throughput on the link between the k-th coalition and the BS using adaptive modulation and coding is calculated as [START_REF] Burchardt | Uplink interference protection and scheduling for energy efficient OFDMA networks[END_REF]:

T k (η k ) = n RB k k sc ̺ s ε(η k ) [bits/s] , (15)
where n RB k is the number of resource blocks assigned to the k-th coalition, k sc is the number of subcarriers per resource block, ̺ s is the symbol rate per subcarrier, and ε(η k ) is the spectral efficiency for a Long Term Evolution (LTE) system [START_REF] Burchardt | Uplink interference protection and scheduling for energy efficient OFDMA networks[END_REF].

The user energy efficiency β k measures the user throughput per unit of consumed energy. This is based on the total consumed power P total k , where P total k is equal to P tot simo when the coalition acts in SIMO mode, and to P tot mimo when a virtual MIMO link is constructed.

β k = T k /P total k [bits/J] . (16)
Additionally, the system energy efficiency β sys is defined as the ratio between the total user throughput and the total power spent by all the users in the system:

β sys = N k=1 T k / N k=1 P total k [bits/J] . (17)

III. DISTRIBUTED VIRTUAL MIMO COALITION FORMATION FRAMEWORK

In order to find the best RS for an MS to cooperate and forming a virtual MIMO link, we model cooperation with a game theoretic approach derived from the concept of stable marriage with incomplete lists (SMI) [START_REF] Iwama | A survey of the stable marriage problem and its variants[END_REF]. The SMI concept is used to find a stable match between two sets (MSs and RSs). A stable match means that no better alternative pairing exists in the other set, where an MS or RS are better off individually compared with the currently matched elements, thus the SMI leads the system to a stable solution.

In our approach, one set contains N mobiles and the other one contains R relay stations. Furthermore, each single antenna's device preference list consists of a subset of the members of the opposite set ordered by preference. A matching M is a tuple (MS, RS) such that each single antenna device belongs to exactly one tuple. If (n, r) ∈ M, we say that the RS-r is the MS-n's partner in M and vice versa. The distributed RS selection procedure is as follows:

1) First, each MS in the system sends a broadcast message on the short range (cooperative) link, in order to find the subset of RSs close enough to cooperate with it, which is denoted as S n ∈ R.

2) After the broadcast message, the RSs willing to form a MIMO link share their channel statistics for their reverse link (path loss, shadowing, and channel fading coefficient) and their channel statistics in the cooperative link (path loss) with subset of mobile stations willing to cooperate with them, which for the RS-r is denoted by S r ∈ N . Mobiles only exchange with the RSs their channel statistics in the reverse link. Hence, each MSs is able to rank its preferred subset of RSs, S n , by using the following utility function:

U nr = P tot simo -P tot mimo , (18)
where U nr is computed as the difference between the power spent by the MS-n acting on its own or making a coalition with the RS-r. Hence the higher is the utility value, the more the MS-n will be willing to cooperate with the RS-r. Additionally, if the utility becomes negative the MS will ignore the RS for coalition formation, since forming a virtual MIMO link will degrade the user's performance. Furthermore, the MS preference list L n is formed by evaluating each element of the subset S n by Eq. (18). MSs that do not obtain any benefit of cooperating with any of the relays in their prefered subset, S n , are allowed to act in SIMO mode. As stated in Theorem 1, under certain conditions SIMO may be prefered over MIMO. The RSs need to compute how important or required is their cooperation with the MSs to form a virtual MIMO link. Thus, RSs rank their suitable candidates as follows:

U rn = P circ P t w rs 2 M t -P circ P t w ms 2 M t , (19)
where U rn is computed as the difference between the power spent by the RS and the MS when forming a virtual MIMO link. Thus, a high value in the utility means that the RS carries most of the power expenditure for the virtual link, since its channel to the BS experiences better instantaneous conditions than the MS channel. Moreover, the RS' preference list, L r , is formed by evaluating each element of S r by Equation (19).

3) After the ranking is done, the SMI procedure given in Algorithm 1, can be applied. Theorem 1. When the user energy efficiencies becomes a function of the circuit consumed power certain conditions such as: an excessive power expenditure in the cooperative link or favorable transmission conditions in the reverse link will allow a SIMO user to experience a higher energy efficiency performance than a virtual MIMO one. Thus

IV. COMPARISON SCHEMES AND SIMULATION SCENARIO

In order to evaluate our proposal, we describe in this section two distributed coalition formation schemes, which allow the mobiles and relays to cooperate in order to form a virtual MIMO link. Additionally, we present a baseline scheme where all the MSs transmit in SIMO mode. Finally, a centralized global optimum scheme, which is coordinated from the BS, is computed based on an exhaustive search approach: this centralized approach is implemented in order to find the price of anarchy for our proposed scheme. This is computed as the difference in performance between a centralized and a distributed approach.

A. Minimum Relaying Hop (MRH) Path Loss Selection

In [START_REF] Sreng | Relayer selection strategies in cellular networks with peer-to-peer relaying[END_REF], the authors propose an RS selection method as a function of path loss. Thus, the best RS-r to form a coalition is the one with the least path loss to the MS-n, which is the relay that has the most energy efficient cooperative link:

RS c = argmin{d κ nr }, (20)

B. Best Worst (BW) Channel Selection

In order to form a virtual MIMO link, each MS should take into consideration the quality of the cooperative link, and the RS channel statistics on the reverse link. This is because both have a direct influence on the total energy expenditure to form the virtual MIMO link. In [START_REF] Sreng | Relayer selection strategies in cellular networks with peer-to-peer relaying[END_REF], the best worst channel is used in which the relay whose worse channel is the best is selected:

argmin{ h r , 1 d κ nr }, (21)
where h r is the fading coefficient between the RS-r and the BS, path loss and shadowing are not considered for the decision making process, since we assume that the other RS candidates are close enough to the MS to experience the same shadowing and path loss.

C. Simulation scenario

Monte Carlo simulations are performed using the parameters listed in Table I. This is done in order to compare the performance of our method with the schemes presented above. The simulation is comprised of a single cell with the mobile stations and relays distributed uniformly over the cell. The cell is served by an omnidirectional BS. Furthermore, the system is only noise limited, thus each coalition transmits in an independent RB. In our simulation, we assume that all the coalitions (SIMO or MIMO) try to achieve the same target SNR.

V. RESULTS

We generate the cumulative distribution function (CDF), and the graphs that show the distribution of the user circuit consumed power at different distances from the BS for the schemes described in the last section. In Fig. 4, we plot the user circuit consumed power. We observe, that when the MSs are close to the BS (up to 160 m), the circuit power consumption of the SIMO scheme matches the SMI and the global optimum curve. This is because the MSs are able to experience better transmission conditions, when they are close to the BS. Thus, turning on the RF transmitter of the relay stations is less power efficient than transmitting with only one antenna. Furthermore, due to the design of the MS's utility function (18) for the SMI case, MSs are able to switch to SIMO mode when it provides power savings. In the case of the other two distributed approaches (MRH path loss selection and the BW channel selection), both schemes always try to form a virtual MIMO link even if the MSs experience favorable transmission conditions to the BS. Hence, their performance at close distances from the BS is lower than for the other three approaches. Furthermore, in Table II, we show the percentage of time that the MSs in the network prefer SIMO over MIMO transmission. Thus, we see that when the circuit power consumption is considered as an optimization metric and under a set of given conditions, SIMO may be preferred over MIMO. Hence, we verify the results of Theorem 1.

Additionally, in Fig. 5, we show the system energy efficiency. At the 50 th percentile, the SMI scheme shows improvements of 37%, 42%, and 44% compared to the SIMO transmission, the MRH path loss and the BW channel respectively. Hence, the proposed SMI approach is more energy efficient than the other two distributed approaches and the baseline case. Furthermore, the price or anarchy for the SMI is 2%, this can be seen as the loss in performance, when the SMI algorithm is compared with the global optimum. Thus, the performance of our distributed approach is similar when compared to a centralized scheme.

Finally, we present in Table II, the channel paths required for each of the proposed methods, where S * n is the number of elements contained in the subset S n . The MRH path loss scheme only requires the channel paths between the MSs and the RSs in the cooperative link. Thus, N × S * n path gains are needed. In the case of the BW channel selection, it requires the paths gains in the cooperative link plus the channel paths between the RSs and the BS, thus the required paths are 2(N × S * n ). For the SMI scheme, we have to add the channel path gains between the MSs and the BS, since MSs exchange their channel statistics with the RSs, hence requiring 3(N ×S * n ) channel path gains. The centralized global optimum uses the channel path gains of N MSs, R RSs, and the gains from the cooperative link, R×N paths. Furthermore, considering the simulation parameters in Table I, the average number of S * n in our simulations is 10. Hence, for our system the SMI requires 600 channel path gains compared with 2540 of the centralized method. Thus, the communication overhead is reduced by 76%.

VI. CONCLUSIONS

We developed in this paper a distributed game theory algorithm derived from the concept of stable marriage with incomplete lists. Based on the presented results, our approach is a more energy efficient solution with improvements of 42%, 44%, and 37% when compared to the MRH path loss, the BW channel, and the SIMO mode scheme respectively. The price of anarchy of our proposed method is of 2%. Moreover, the proposed framework reduces the communication overhead of the network by 76%. We have shown analytically and by simulation that when the circuit consumed power is considered for the optimization process and under a given set of conditions, transmitting in SIMO mode is more energy efficient than forming a virtual MIMO link.

APPENDIX

Proof of Theorem 1

Equation ( 16) will be used to prove that under a given set of conditions forming a virtual MIMO link is less energy efficient than transmitting in SIMO mode. Thus, the following condition is met: β Ptot simo ≥ β Ptot mimo , where β Ptot simo and β Ptot mimo are the user energy efficiencies when transmitting in SIMO and MIMO modes respectively. Furthermore, if the target user rate T k is fixed for both systems, the equation above is equivalent to showing that: P tot mimo (P t , P tcop ) ≥ P tot simo (P t ).

(

) 22
Additionally, by using Equations ( 8) and ( 9), it is easy to see that P tcop should increase proportionally to the separation distance d nr in order to maintain an acceptable SNR at the RS side. Hence, if d nr → ∞ , P tcop → ∞, and consequently P tot mimo (P t , P tcop ) will dominate over P tot simo (P t ).

As stated before, favorable transmission conditions in the reverse link means that the MSs do not need to form a virtual link. Hence, over a long time scale the following is a valid assumption for MIMO and SIMO systems respectively: F } = M t M r [START_REF] Paulraj | Introduction to space-time wireless communications[END_REF]. Thus, by using Equations ( 6) and ( 7) the average SNR E{η k } for a MIMO and SIMO coalition can be computed as follows: E{η k mimo } ≤ Pr Mr Mt ρ , and E{η k simo } = Pr Mr ρ . Hence, in order to achieve the same average SNR at the BS side, a SIMO coalition consumes approximately M t times more transmitted power than a MIMO coalition, thus, P t mimo × M t ≈ P t simo . Furthermore, make P t mimo × M t and P t mimo the inputs for the uplink transmit power in Equations ( 10) and (11) respectively. Making P t mimo to tend to a small value implies the MSs experience favorable transmission conditions in the reverse link, it is easy to see in Equation ( 12) that the reverse link power that is spent when a virtual MIMO link is formed will cause P tot mimo (P t , P tcop ) to be higher than P tot simo (P t ), for favorable transmission conditions in the uplink.

Fig. 1 :

 1 Fig. 1: User cooperation example coalitions considering an OFDMA transmission model.

Fig. 2 :

 2 Fig. 2: A Virtual 2 × M r MIMO link.

Fig. 3 :

 3 Fig. 3: Internal model of the power amplifier for the RF module.

Fig. 4 :

 4 Fig. 4: User circuit consumed power vs distance from the BS.

  , the following condition is met β Ptot simo ≥ β Ptot mimo , where β Ptot simo and β Ptot mimo are the user energy efficiencies for a SIMO and MIMO user respectively, which is proven in the Appendix. Stable Marriage with incomplete lists (SMI).

	Initialization: All MSs must be operating in SIMO mode;
	while There is an MS-n wanting to form a MIMO link;
	do
	RS end
	end
	end
	Algorithm 1:

h is the highest RS in the MS-n preference list, L n , to whom it has not yet proposed; if RS h is free then the MS-n and RS h become engaged; else RS h is already engaged with an MS-i (where i = n); if RS h prefers the MS-n to the MS-i in its preference list, L r ; then MS-n becomes engaged, and the MS-i becomes free; else RS h remains engaged to the MS-i; RS h is deleted from the list of the MS-n, L n ;

TABLE I :

 I Simulation parameters.

	Parameter	Value
	MSs per macro-cell, N	20
	RSs per macro-cell, R	120
	Number of antennas at the receiver, Mr	2
	Intersite-site distance	700m
	Number of available RBs, X	20
	Number of cells, D	1
	Subcarriers per RB, ksc	12
	Symbol rate per subcarrier, ̺s	15ksps
	P T x	31.8dBm
	Pcon	23.8dBm
	P BB for ε = 1.1758 bits symbol	11.7dBm
	Maximum user transmit power	23dBm
	Shadowing, Std. Dev., σ	3dB
	Target SNR,	3dB
	ε for 3dB SNR	1.1758 bits symbol
	κ	3.5

TABLE II :

 II Percentage of time that the MSs prefer SIMO over MIMO and communication overhead.

	Method	Percentage	Propagation paths
	MHR path loss	0%	N × S * n
	BW channel	0%	2(N × S * n )
	SMI	68%	3(N × S * n )
	SIMO mode	100%	none
	Centralized global optimum	66%	N + R + (N × R)

  E{σ 2 max } ≤ E{ H 2 F }, and E{ h 2 F } = M r , where E{ H 2

		1
		0.9
		0.8
		0.7
		0.6
	CDF	0.5
		0.4
		0.3
									MRH path loss
		0.2							BW channel
									SMI
		0.1							SIMO mode
									Global optimum
		1.2	1.4	1.6	1.8	2	2.2	2.4	2.6	2.8	3
				Energy Efficiency [kbits/J]	x 10 4
		Fig. 5: System CDF energy efficiency.