Joëlle Despeyroux
email: joelle.despeyroux@inria.fr

Mathematical) Logic for Systems Biology (Invited Paper

We advocates here the use of (mathematical) logic for systems biology, as a unified framework well suited for both modeling the dynamic behaviour of biological systems, expressing properties of them, and verifying these properties. The potential candidate logics should have a traditional proof theoretic pedigree (including a sequent calculus presentation enjoying cut-elimination and focusing), and should come with (certified) proof tools. Beyond providing a reliable framework, this allows the adequate encodings of our biological systems. We present two candidate logics (two modal extensions of linear logic, called HyLL and SELL), along with biological examples. The examples we have considered so far are very simple ones -coming with completely formal (interactive) proofs in Coq. Future works includes using automatic provers, which would extend existing automatic provers for linear logic. This should enable us to specify and study more realistic examples in systems biology, biomedicine (diagnosis and prognosis), and eventually neuroscience.

Introduction

We consider here the question of reasoning about biological systems in (mathematical) logic. We show that two new logics, both modal extensions of linear logic [START_REF] Girard | Linear logic[END_REF] (LL), are particularly well-suited to this purpose. The first logic, called Hybrid Linear Logic (HyLL), has been developed by the author in joint work with K. Chaudhuri [START_REF] Despeyroux | A hybrid linear logic for constrained transition systems[END_REF]. The second logic, an extension of Subexponential Linear Logic (SELL ⋓ ), has been independently proposed by C. Olarte, E. Pimentel and V. Nigam [START_REF] Nigam | A general proof system for modalities in concurrent constraint programing[END_REF]. Both HyLL and SELL provide a unified framework to encode biological systems, to express temporal properties of their dynamic behaviour, and to prove these properties. By constructing proofs in the logics, we directly witness reachability as logical entailment [START_REF] De Maria | A logical framework for systems biology[END_REF][START_REF] Olarte | A proof theoretic view of spatial and temporal dependencies in biochemical systems[END_REF]. This approach is in contrast to most current approaches to applying formal methods to systems biology, which generally encode biological systems either in a dedicated programming language [START_REF] Danos | Agile modelling of cellular signalling (invited paper)[END_REF][START_REF] Fages | Formal cell biology in BIOCHAM[END_REF][START_REF] Phillips | A correct abstract machine for the stochastic pi-calculus[END_REF], or in differential equations [START_REF] Campagna | Hybrid automata in systems biology: How far can we go?[END_REF], express properties in a temporal logic, and then verify these properties against some form of traces (model-checking), eventually built using an external simulator.

In a joint work with E. De Maria and A. Felty, we presented some first applications of HyLL to systems biology [START_REF] De Maria | A logical framework for systems biology[END_REF]. In these first experiments, we focused on Boolean systems and in this case a time unit corresponds to a transition in the system. We believe that discrete modeling is crucial in systems biology because it allows taking into account some phenomena that have a very low chance of happening (and could thus be neglected by differential approaches), but which may have a strong impact on system behavior.

In a recent joint work with C. Olarte and E. Pimentel [START_REF] Despeyroux | Hybrid and subexponential linear logics[END_REF], we compared HyLL and SELL, providing two encodings. The first enoding is from HyLL's logical rules into LL with the highest level of adequacy, hence showing that HyLL is as expressive as LL. We also proposed an encoding of HyLL into SELL ⋓ , showing that SELL ⋓ is more expressive than HyLL. However, the simplicity of HyLL might be of interest, both from the user point of view and as far as proof search is concerned (a priori easier and more efficient in HyLL than in SELL). In this joint work, we furthermore encoded temporal operators of Computational Tree Logic (CTL) into linear logic with fixed point operators.

We first recall here these two previous works. Then we briefly mention our current joint work with P. Lio, on formalizing the evolution of cancer cells, concluding with some future work.

This note is thus based on joint works with K. Chaudhuri (INRIA Saclay), A. Felty (Univ. of Ottawa), P. Lio (Cambridge Univ.), and C. Olarte and E. Pimentel (Universidade Federal do Rio Grande do Norte, Brazil).

Preliminaries

Although we assume that the reader is familiar with linear logic [START_REF] Girard | Linear logic[END_REF] (LL), we review some of its basic proof theory in the following sections. First, let us gently introduce linear logic by means of an example.

Linear Logic for Biology

Linear Logic (LL) [START_REF] Girard | Linear logic[END_REF] is particularly well suited for describing state transition systems. LL has been successfully used to model such diverse systems as: the π-calculus, concurrent ML, security protocols, multiset rewriting, and games.

In the area of biology, a rule of activation (e.g., a protein activates a gene or the transcription of another protein) can be modeled by the following LL axiom:

active(a, b) def = pres(a) -• (pres(a) ⊗ pres(b)).
The formula active(a, b) describes the fact that a state where a is present (pres(a) is true) can evolve into a state where both pres(a) and pres(b) are true.

Propositions such as pres(a) are called resources, and a rule in the logic can be viewed as a rewrite rule from a set of resources into another set of resources, where a set of resources describes a state of the system. Thus, a particular state transition system can be modeled by a set of rules of the above shape. The rules of the logic then allow us to prove some desired properties of the system, such as, for example, the existence of a stable state. However, linear implication is timeless. Linear implication can be used to model one event occurring after another, but it cannot be precise about how many steps or how long the delay is without explicitly encoding time. In a domain where resources have lifetimes and state changes have temporal, probabilistic or stochastic constraints, then the logic will allow inferences that may not be realizable in the system being modeled. This was the motivation of the development of HyLL, which was designed to represent constrained transition systems.

Linear Logic and Focusing

Literals are either atomic formulas (p) or their negations (p ⊥ ). and?. The positive connectives ⊗, 1, ⊕, 0, ∃, and ! are the de Morgan duals of the negative connectives. A formula is positive if it is a negated atom or its top-level logical connective is positive. Similarly, a formula is negative if it is an atom or its top-level logical connective is negative.

Focused proofs are organized into two phases. In the negative phase, all the invertible inference rules are eagerly applied. The positive phase begins by choosing a positive formula F on which to focus. Positive rules are applied to F until either 1 or a negated atom is encountered (and the proof must end by applying the initial rules), the promotion rule (!) is applied, or a negative subformula is encountered and the proof switches to the negative phase.

This change of phases on proof search is particularly interesting when the focused formula is a bipole [START_REF] Andreoli | Logic programming with focusing proofs in linear logic[END_REF]. Focusing on a bipole will produce a single positive and a single negative phase. This two-phase decomposition enables us to adequately capture the application of object-level inference rules by the meta-level linear logic, as shown in [START_REF] Despeyroux | Hybrid and subexponential linear logics[END_REF].

Hybrid Linear Logic

Hybrid Linear Logic (HyLL) is a conservative extension of Intuitionistic firstorder Linear Logic (ILL) [START_REF] Girard | Linear logic[END_REF] where the truth judgments are labelled by worlds representing constraints on states and state transitions. Instead of the ordinary judgment "A is true", for a proposition A, judgments of HyLL are of the form "A is true at world w", abbreviated as A @ w. Particular choices of worlds produce particular instances of HyLL. Typical examples are "A is true at time t", or "A is true with probability p". HyLL was first proposed in [START_REF] Despeyroux | A hybrid linear logic for constrained transition systems[END_REF] and it has been used as a logical framework for specifying biological systems [START_REF] De Maria | A logical framework for systems biology[END_REF].

Formally, worlds are defined as follows.

Definition 1 (HyLL worlds). A constraint domain W is a monoid structure W, ., ι . The elements of W are called worlds and its reachability relation :

W × W is defined as u w if there exists v ∈ W such that u.v = w.
The identity world ι is -initial and is intended to represent the lack of any constraints. Thus, the ordinary first-order linear logic is embeddable into any instance of HyLL by setting all world labels to the identity. A typical, simple example of constraint domain is T = IN , +, 0 , representing instants of time.

Atomic propositions (p, q, . . .) are applied to a sequence of terms (s, t, . . .), which are drawn from an untyped term language containing constants (c, d, . . .), term variables (x, y, . . .) and function symbols (f, g, . . .) applied to a list of terms (t). Non-atomic propositions are constructed from the connectives of first-order intuitionistic linear logic and the two hybrid connectives satisfaction (at), which states that a proposition is true at a given world (w, ι, u.v, . . .), and localization (↓), which binds a name for the (current) world the proposition is true at. The following grammar summarizes the syntax of HyLL.

t

::= c | x | f (t) A, B ::= p(t) | A ⊗ B | 1 | A → B | A & B | ⊤ | A ⊕ B | 0 | !A | ∀x. A | ∃x. A | (A at w) | ↓ u. A | ∀u. A | ∃u.
A Note that world u is bounded in the propositions ↓ u. A, ∀u. A and ∃u. A. World variables cannot be used in terms, and neither can term variables occur in worlds. This restriction is important for the modular design of HyLL because it keeps purely logical truth separate from constraint truth. We note that ↓ and at commute freely with all non-hybrid connectives [START_REF] Despeyroux | A hybrid linear logic for constrained transition systems[END_REF].

The sequent calculus [START_REF] Gentzen | Investigations into logical deductions[END_REF] presentation of HyLL uses sequents of the form Γ ; ∆ ⊢ C @ w where Γ (unbounded context ) is a set and ∆ (linear context ) is a multiset of judgments of the form A @ w. Note that in a judgment A @ w (as in a proposition A at w), w can be any expression in W, not only a variable.

The inference rules dealing with the new hybrid connectives are depicted below (the complete set of rules can be found in [START_REF] Despeyroux | A hybrid linear logic for constrained transition systems[END_REF]).

Γ ; ∆ ⊢ A@u Γ ; ∆ ⊢ (A at u)@w atR Γ ; ∆, A@u ⊢ C@w Γ ; ∆, (A at u)@v ⊢ C@w atL

Γ ; ∆ ⊢ A[w/u]@w Γ ; ∆ ⊢↓ u.A@w ↓ R Γ ; ∆, A[v/u]@v ⊢ C@w Γ ; ∆, ↓ u.A@v ⊢ C@w ↓ L
Note that (A at u) is a mobile proposition: it carries with it the world at which it is true. Weakening and contraction are admissible rules for the unbounded context.

The most important structural properties are the admissibility of the general identity (i.e. over any formulas, not only atomic propositions) and cut theorems. While the first provides a syntactic completeness theorem for the logic, the latter guarantees consistency (i.e. that there is no proof of .; . ⊢ 0 @ w).

Theorem 1 (Identity/Cut). 1. Γ ; A @ w ⊢ A @ w 2. If Γ ; ∆ ⊢ A @ u and Γ ; ∆ ′ , A @ u ⊢ C @ w, then Γ ; ∆, ∆ ′ ⊢ C @ w 3. If Γ ; . ⊢ A @ u and Γ, A @ u; ∆ ⊢ C @ w, then Γ ; ∆ ⊢ C @ w.

Moreover, HyLL is conservative with respect to intuitionistic linear logic: as long as no hybrid connectives are used, the proofs in HyLL are identical to those in ILL. It is worth noting that HyLL is more expressive than S5, as it allows direct manipulation of the worlds using the hybrid connectives and HyLL's δ connective (see Section 5) is not definable in S5. We also note that HyLL admits a complete focused [START_REF] Andreoli | Logic programming with focusing proofs in linear logic[END_REF] proof system. The interested reader can find proofs and further meta-theoretical theorems about HyLL in [START_REF] Despeyroux | A hybrid linear logic for constrained transition systems[END_REF].

Modal Connectives. We can define modal connectives in HyLL as follows:

Definition 2 (Modal connectives). A def = ↓u. ∀w. (A at u.w) ♦A def = ↓u. ∃w. (A at u.w) δ v A def = ↓u. (A at u.v) A [resp. ♦A]
represents all [resp. some] state(s) satisfying A and reachable from now. The connective δ represents a form of delay.

Subexponentials in Linear Logic

Linear logic with subexponentials (SELL) shares with LL all its connectives except the exponentials: instead of having a single pair of exponentials ! and ?, SELL may contain as many subexponentials [START_REF] Danos | The structure of exponentials: Uncovering the dynamics of linear logic proofs[END_REF][START_REF] Olarte | Subexponential concurrent constraint programming[END_REF], written ! a and ? a , as one needs. The grammar of formulas in SELL is as follows:

F ::= 0 | 1 | ⊤ |⊥| p(t) | F 1 ⊗ F 2 | F 1 ⊕ F 2 | F 1 . . . .
F 2 | F 1 & F 2 | ∃x.F | ∀x.F | ! a F | ? a F
The proof system for SELL is specified by a subexponential signature Σ = I, , U , where I is a set of labels, U ⊆ I is a set specifying which subexponentials allow weakening and contraction, and is a pre-order among the elements of I. We shall use a, b, . . . to range over elements in I and we will assume that is upwardly closed with respect to U , i.e., if a ∈ U and a b, then b ∈ U .

The system SELL is constructed by adding all the rules for the linear logic connectives except for the exponentials. The rules for subexponentials are dereliction and promotion of the subexponential labelled with a ∈ I

⊢ ? a1 F 1 , . . . ? an F n , G ⊢ ? a1 F 1 , . . . ? an F n , ! a G ! a ⊢ Γ, G ⊢ Γ, ? a G ? a
Here, the rule ! a has the side condition that a a i for all i. That is, one can only introduce a ! a on the right if all other formulas in the sequent are marked with indices that are greater or equal than a. Moreover, for all indices a ∈ U , we add the usual rules for weakening and contraction.

We can enhance the expressiveness of SELL with the subexponential quantifiers ⋓ and ⋒ ( [START_REF] Nigam | A general proof system for modalities in concurrent constraint programing[END_REF][START_REF] Olarte | Subexponential concurrent constraint programming[END_REF]) given by the rules (omitting the subexponential signature)

⊢ Γ, G[l e /l x ] ⊢ Γ, ⋓l x : a.G ⋓ ⊢ Γ, G[l/l x ] ⊢ Γ, ⋒l x : a.G ⋒
where l e is fresh. Intuitively, subexponential variables play a similar role as eigenvariables. The generic variable l x : a represents any subexponential, constant or variable in the ideal of a. Hence l x can be substituted by any subexponential l of type b (i.e., l : b) if b a. We call the resulting system SELL ⋓ . As shown in [START_REF] Nigam | A general proof system for modalities in concurrent constraint programing[END_REF][START_REF] Olarte | Subexponential concurrent constraint programming[END_REF], SELL ⋓ admits a cut-free and also a complete focused proof system. Theorem 2. SELL ⋓ admits cut-elimination for any subexponential signature.

Modal connectives. We can define modal connectives in SELL as follows:

u A def = ∀l : u. ! l A ♦ u A def = ∃l : u. ! l A A def = ∀t : ∞. ! t A ♦A def = ∃t : ∞. ! t A

First experiments with HyLL

In a joint work with E. De Maria and A. Felty, we presented some first applications of HyLL to systems biology [START_REF] De Maria | A logical framework for systems biology[END_REF]. In these first experiments, we focused on Boolean systems and in this case a time unit corresponds to a transition in the system.

The activation rule seen in LL (Sec. 2.1) can be written in HyLL as

active(a, b) def = pres(a) -• δ 1 (pres(a) ⊗ pres(b)).
We chosed a simple yet representative biological example concerning the DNA-damage repair mechanism based on proteins p53 and Mdm2, and present and proved several properties of this system. All these properties were reachability properties or the existence of an invariant. Most interesting proofs require induction or case analysis, that we borrowed from the meta-level (Coq). We fully formalized these proofs in the Coq Proof Assistant [START_REF] Bertot | Interactive Theorem Proving and Program Development[END_REF]. In Coq, we can both reason in HyLL and formalize meta-theoretic properties about it.

We discussed the merits and eventual drawbacks of this new approach compared to approaches using temporal logic and model checking. To better illustrate the correspondence with such approaches, which all use temporal logic to reason about (simulations of models of) the biological systems described, we also presented, informally but in some detail, the encoding of temporal logic operators in HyLL.

Relative Expressiveness Power of HyLL and SELL

We observe that, while linear logic has only seven logically distinct prefixes of bangs and question-marks, SELL allows for an unbounded number of such prefixes, e.g., ! i , or ! i ? j . Hence, by using different prefixes, we allow for the specification of richer systems where subexponentials are used to mark different modalities/states. For instance, subexponentials can be used to represent contexts of proof systems [START_REF] Nigam | Specifying proof systems in linear logic with subexponentials[END_REF]; to specify systems with temporal, epistemic and spatial modalities [START_REF] Olarte | Subexponential concurrent constraint programming[END_REF] and to specify and verify biological systems [START_REF] Olarte | A proof theoretic view of spatial and temporal dependencies in biochemical systems[END_REF]. An inhibition rule can be written in (classical) SELL as

inhib(a, b) def = ! t a -• ! t+1 (a ⊗ b ⊥ ).
HyLL and Linear Logic. One may wonder whether the use of worlds in HyLL increases also the expressiveness of LL. In a joint work with C. Olarte and E. Pimentel [START_REF] Despeyroux | Hybrid and subexponential linear logics[END_REF], we proved that this is not the case, by showing that HyLL rules can be directly encoded into LL by using the methods proposed in [START_REF] Miller | A formal framework for specifying sequent calculus proof systems[END_REF]. Moreover, the encoding of HyLL into LL is adequate in the sense that a focused step in LL corresponds exactly to the application of one inference rule in HyLL.

HyLL and SELL. Linear logic allows for the specification of two kinds of context maintenance: both weakening and contraction are available (classical context) or neither is available (linear context). That is, when we encode (linear) judgments in HyLL belonging to different worlds, the resulting meta-level atomic formulas will be stored in the same (linear) LL context. The same happens with classical HyLL judgments and the classical LL context.

Although this is perfectly fine, encoding HyLL into SELL ⋓ allows for a better understanding of worlds in HyLL. For that, we use subexponentials to represent worlds, having each world as a linear context. A HyLL judgment of the shape F @w in the (left) linear context is encoded as the SELL ⋓ formula ? w ⌊F @w⌋. Hence, HyLL judgments that hold at world w are stored at the w linear context of SELL ⋓ . A judgment of the form G@w in the classical HyLL context is encoded as the SELL ⋓ formula ? c ? w ⌊G@w⌋. Then, the encoding of G@w is stored in the unbounded (classical) subexponential context c.

We showed that our encoding is indeed adequate. Moreover, as before, the adequacy of the encodings is on the level of derivations.

Information Confinement. One of the features needed to specify spatial modalities is information confinement : a space/world can be inconsistent and this does not imply the inconsistency of the whole system. We showed in [START_REF] Despeyroux | Hybrid and subexponential linear logics[END_REF] that information confinement cannot be specified in HyLL. The authors in [START_REF] Nigam | A general proof system for modalities in concurrent constraint programing[END_REF] exploit the combination of subexponentials of the form ! w ? w in order to specify information confinement in SELL ⋓ . More precisely, note that the sequents (in a 2-sided presentation of SELL) ! w ? w 0 ⊢ 0 and ! w ? w 0 ⊢ ! v ? v 0, representing "inconsistency is local" and ' 'inconsistency is not propagated" respectively hold in SELL.

Computation Tree Logic (CTL) in Linear Logic.

Hybrid linear logic is expressive enough to encode some forms of modal operators, thus allowing for the specification of properties of transition systems. As mentioned in [START_REF] De Maria | A logical framework for systems biology[END_REF], it is possible to encode CTL temporal operators into HyLL considering existential (E) and bounded universal (A) path quantifiers. We extended these encodings in [START_REF] Despeyroux | Hybrid and subexponential linear logics[END_REF], showing how to fully capture E and A CTL quantifiers in linear logic with fixed points. For that, we used the system µMALL [START_REF] Baelde | Least and greatest fixed points in linear logic[END_REF] that extends MALL (multiplicative, additive linear logic) with fixed point operators. In [START_REF] De Maria | A logical framework for systems biology[END_REF], proofs of (encodings of) properties involving CTL quantifiers use induction borrowed from the (Coq) meta-level. In [START_REF] Despeyroux | Hybrid and subexponential linear logics[END_REF], we could directly use fixed points in linear logic.

Concluding Remarks and Future Work

Concerning related work, it is worth noticing that there are some other logical frameworks that are extensions of LL, for example, HLF [START_REF] Reed | Hybridizing a logical framework[END_REF]. Being a logic in the LF family, HLF is based on natural deduction, hence having a complex notion of (βη) normal forms. Thus adequacy (of encodings of systems) results are often much harder to prove in HLF than in (focused) HyLL/SELL. HLF seems to have been later abandonned in favour of Hybridized Intuitionistic Linear Logic (HILL) [START_REF] Caires | Logic-based domain-aware session types[END_REF] -a type theory based on a subpart of HyLL.

Both HyLL and SELL have been used for formalizing and analyzing biological systems [START_REF] De Maria | A logical framework for systems biology[END_REF][START_REF] Olarte | A proof theoretic view of spatial and temporal dependencies in biochemical systems[END_REF]. SELL proved to be a broader framework for handling such systems (in particular localities). However, the simplicity of HyLL may be of interest for specific purposes, such as building tools for diagnosis in biomedicine.

Formal proofs in HyLL were implemented in [START_REF] De Maria | A logical framework for systems biology[END_REF], in the Coq [START_REF] Bertot | Interactive Theorem Proving and Program Development[END_REF] proof assistant. It would be interesting to extend the implementations of HyLL given there to SELL. Such an interactive proof environment would enable both formal studies of encoded systems in SELL and formal meta-theoretical study of SELL itself.

We may pursue the goal of using HyLL/SELL for further applications. That might include neuroscience, a young and promising science where many hypotheses are provided and need to be verified. Indeed, logic is a general tool whose area of potential applications are not restricted per se. This is in contrast to most of the other approaches, which are valid only in a restricted area (typically inside or outside the cell).

In an ongoing joint work with P. Lio, we are formalizing the evolution of cancer cells, acquiring driver or passenger mutations. A rule describing an intravasating Circulating Tumour Cell, for example, might be:

C(n, breast, f, [EPCAM]) -• δ d C(n, blood, 1, [EPCAM])
where f is a fitness parameter, here in {0, 1}. Our long term goal here is the design of a Logical Framework for disease diagnosis and therapy prognosis. This requires the development of automatic tools for proof search in our logics. These tools should benefit both from current research on proof search in linear logic and from current developments of automatic provers for SELL.

  for cut-free proofs. The connectives of linear logic can be divided into two classes. The negative connectives have invertible introduction rules: these connectives are . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

	⊗ and	The connectives . . . . . . . . and their units 1 and ⊥ are multiplicative; the connectives ⊕ and & . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
	and their units 0 and ⊤ are additive; ∀ and ∃ are (first-order) quantifiers; and !
	and ? are the exponentials (called bang and question-mark, respectively).
	First proposed by Andreoli [1] for linear logic, focused proof systems provide
	normal form proofs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . , ⊥, &, ⊤, ∀,

  . . . . . . . . . . . . . . . . . . . . . . . . . .

	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . .


E Benoit

L Foulloy

Symbolic sensors : one solution to the numerical-symbolic interface

According to the evolution of control systems, the nature of information become more complex. Artificial intelligent technics use and produce symbolic information, therefore there is a need for sensors which deliver this kind of information.

This paper introduces the concept of symbolic sensor as an extension of the smart sensor one. Then, the links between the physical world and the symbolic one are introduced. The creation of symbols is proposed within the frame of the pretopology theory. In order to adapt the sensor to the measurement context, a learning process has been used to provide an adaptive interpretation of the measurement. Finally, an example is presented in the case of a temperature measurement.

Introduction

In every control systems, a part of the signal processing is attached to the sensors. Therefore, as controllers become more complex, a part of the signal processing is transferred to the sensor. Analog sensors integrate it in the conditioner, while smart sensors have computation devices to process the signal. The most important difference between this two king of sensors is the nature of informations exchanged with the controller, it fixes the maximum decentralization of the control system. Nowadays, it is generally admitted that the characteristic functionality of a smart sensor should be its ability to communicate with a communication bus or network, to verify the correctness of the measurement and to adapt itself when the environment is changing (Burd [START_REF] Burd | Intelligent transducers[END_REF], Giachino [START_REF] Giachino | Smart sensors[END_REF], Bois [START_REF] Bois | Optical fibre displacement: how fibres can benefit smart sensors[END_REF]). A possible description of a smart sensor is given by Favenec [START_REF] Favenec | Smart sensors in industry[END_REF] (see Fig. 1.). We consider that an intelligent sensor should own four mechanisms: perception (the main part of the sensor), communication, learning and faculty of reasoning. Applications of artificial intelligent technics like expert systems and qualitative control, use symbolic informations. Then, the decentralization of a part of the decision process induces adapted perception organs. For example the Order of Magnitude model uses symbols like "negative medium" or "positive small" [START_REF] Missier | Order of magnitude qualitative algebras : A survey[END_REF], therefore there is a need for sensors that return this kind of symbols.

We define the symbolic sensor as a smart sensor which is able to work and to provide symbolic informations relative to the measurement.

This new property allows the sensor to make

Conditioner

Communication

Smart sensor interface

Power supply

Communication bus

Digital data

Transducer

Identification

Computation device

Physical phenomenon decisions about the measurement and the context, it adds the possibility of reasoning that is commonly used by human beings in usual intelligent activities.

Translation, concept and interpretation

In order to realize a numeric to symbolic link, we define a numerical domain E as the set of the measurement and a symbolic one L as a set of symbols characterizing the measure. The meaning of a symbolic value will be called a translation and be defined as an injective application from the symbolic set to the set of the subsets of the numerical domain (injectivity insures that two identical symbols have the same translation). A generalization of the concept of translation was developed by Luzeaux [START_REF] Luzeaux | Normalizing symbolic reasoning[END_REF].

τ: L → P(E)

The association of a symbolic value and its translation is called a concept. The symbolic measurement will be obtained by means of a new relationship from the numerical domain to the symbolic one, called an interpretation.

ι: E → L

The relationship between the translation and the interpretation is summarized in Fig. 3. The definition of the concepts for any symbol induces the definition of the translation. The translation can be unconstrained, then, for any symbol L, τ(L) can be any subset on E. In the following of this paper, we study a kind of symbolic sensor which impose several conditions on the translation:

• The intersection between the translations of two symbols must be empty.

• The numerical domain is an ordered set with an order relation noted < E .

• The translation of any symbol is an interval:

∀L ∈ L, ∀x, y ∈ τ(L) such that x < E y, ∀z ∈ E x < E z < E y ⇒ z ∈ τ(L)
Then, the interpretation can be define as follow.

L = ι(x) if x ∈τ(L)
This relationship is an application when τ(L) is a partition on E. This assumption will be used in the following.

The pretopology formalism a) Introduction

We give here several notations used in the paper: A ∪ B (resp. A ∩ B) will denote the union (resp. the intersection) of two sets A and B.The difference of sets A,B will be represented by A-B. The complementation of a set A will be denoted by c(A). The positive integer card(A) denotes the cardinal number of the set A. If f is a relation on E, A a subset of E and n an integer up to 0 then

L E τ L A = τ(L) A ∈P(E) x ι • • f n A ( ) f f n 1 -A ( ) ( ) = f 1 A ( ) f A ( ) =
Originally used for morphological image analysis, the pretopology formalism gives operators such as dilatation and erosion working on sets. Before using this mathematical tool on concepts, let us recall the principles of the pretopology described by Emptoz [START_REF] Emptoz | A systemic approach to pattern recognition[END_REF]:

Let E be a set, for any x in E, is given a family B(x) of subsets of E which all contain x. This family is called a structuring base. Given B(x) for any x in E, we say that E is embedded with a pretopological structure or simply a pretopology. Two basic operators, the adherence and the interior are defined as follows.

Let A be a subset of E adh

B (A) = {x ∈ E / ∀B, B∈B(x), B∩A ≠ ∅} int B (A) = c(adh B (c(A)))
Example: E=Z 2 , x = (i, j), B(x)={B1,B2} (Z is the set of signed integers) with: B1 = {(i-1,j),(i,j),(i+1,j)} B2 = {(i, j-1),(i, j), (i, j+1)} Fig. 4. Example using interior and adherence.

Assuming that pred(x) is the element which precedes x and succ(x) the element which follows x in a totally ordered discrete set, the two following structuring bases are defined:

Bsup(x) = {{pred(x)
int B (A) adh B (A) A adh B (adh B (A)) int B (int B (A)) adh Bsup ({4,5}) = {4,5,6} int Bsup ({4,5}) = {5} adh Binf ({4,5}) = {3,4,5} adh Bsup ({}) = {} int Bsup ({0,1}) = {0,1} 0 4 8 0 4 8
These two bases will be used in the following.

b) The generic concept and the creation of new concepts

The generic concept corresponds to a part of the numerical domain which is important for the global task that is to be realized with the sensor. Let us give an example. Assume that a thermometer is used for a swimming-pool. It makes sense to define a generic concept temperature is correct around 23 o C. Now, if the sensor is used into a deep freeze, the generic concept temperature is correct should be around -18 o C. According to our approach, the translation associated to the generic concept is an interval on the numerical domain. Let us define the translation associated to generic concept temperature is correct for the swimming pool example by τ(temperature_is_correct) = {21, 22, 23, 24, 25}.

Obviously, it is a tedious task to specify each translation of the symbols. Let us introduce the operators that are used to generate new concepts. Our problem is to find operators that act in the symbolic domain and their definition in the numerical domain in order to compute the new concepts. First, let us define a mapping function F in the symbolic domain L.

F: L ¡ L L 1 ¡ L 2 = F(L 1 )
We can now define the associated mapping function in the numeric domain E.

f F: P(E) ¡ P(E) τ(L 1 ) ¡ τ(L 2 ) = τ(F(L 1 )) = f F (τ(L 1 ))
The relationship between functions F and f F is given in Fig. 6. Fig. 6. Relationship between F and f F .

L E τ A = τ(L 1 ) • L 1 • L 2 F B = f F (Α) f F
Assuming that A ∈ P(E), L 1 and L 2 ∈ L such that A = τ(L 1 ), four mapping functions have been defined with the help of the pretopology formalism. Let us give an example for a temperature sensor on a discrete measurement set (temperature is given in °C) E = {0,1,...,38,39}. First of all, we define the generic concept good such as τ(good) = {18, 19, 20, 21, 22}. Then, we inform the sensor about the semantics between the generic concept and new concepts.

cold = below(good) and warm=more(good).

The sensor uses this information to build its concepts (see Fig. 7.).

c) Adaptation of the interpretation

In the previous sections, it has been shown how to build automatically with several operators one relationship between the numerical and the symbolic domains. It seems obvious that the definition of translations is the difficult point. A symbolic sensor that is concerned with a temperature measurement problem can interpret the measure "temperature=15°C" as a cool temperature. According to the context, the interpretation can be false: joined with a swimming-pool, the temperature is cold. Joined with a refrigerator, it is very hot. Furthermore, the interpretation can differ with the interlocutor. This last point is very important during the knowledge acquisition time when one wants to implement an expert system. Therefore, there is a need to configure the sensor according to the context (envi- ronment, measurement job) and the interlocutor. The cooperative configuration is based on a learning method with a teacher (control system, human or aggregation sensors) who interprets correctly a measure in a defined context.

f above A ( ) adh Bsup n A ( ) A - n ∞ → lim = f more A ( ) adh Bsup card A ( ) A ( ) A - = f less A ( ) adh Binf card A ( ) A ( ) A - = f below A ( ) adh Binf n A ( ) A - n ∞ → lim = L 2 = more(L 1 ) L 2 = less(L 1 ) L 2 = above(L 1 ) L 2 = below(L 1 )
The principle of the cooperative configuration is given in Fig. 8. It is based on the qualitative comparison between the interpretation of the sensor (sc) and the interpretation of the professor (sp) for the same numerical input x. The qualitative comparison e takes its values in the set of signs S = {-, 0, +} usual in qualitative analysis. The result is obtained from the order relation on L.

e = + if sp > L sc e = -if sp < L sc e = 0 if sp = L sc
The qualitative comparison is used to synthesize a symbolic input u for the sensor which takes its value in the set M = {increase, decrease, maintain}. This symbolic input is used to change the translation of each symbolic value and, of course, the sensor interpretations. The idea is to change the translation in order to obtain a qualitative feedback of the sensor interpretation according to the professor interpretation.

ι k+1 (x) = increase(ι k (x)) ≥ L ι k (x) ι k+1 (x) = decrease(ι k (x)) ≤ L ι k (x) ι k+1 (x) = maintain(ι k (x)) = L ι k (x)
Now, in order to complete the approach, the function increase, decrease and maintain have to be defined. The function maintain is obvious since no action is performed. Let L ∈ L be the interpretation of the measurement x, L = ι k (x), then the functions increase and decrease are defined as follows from the interior operation (another definition from the adherence operator can easily be obtained).

ι k+1 (x) = increase(L): τ k+1 (L) = int Binf (τ k (L)) τ k+1 (succ L (L)) = τ k (succ L (L)) ∪ (τ k (L) -τ k+1 (L)) ι k+1 (x) = decrease(L): τ k+1 (L) = int Bsup (τ k (L)) τ k+1 (pred L (L)) = τ k (pred L (L)) ∪ (τ k (L) -τ k+1 (L))
The application of such functions on a lexical set with five symbolic values at the learning cycle k is provided in Fig. 9. to Fig. 11. -warm is more than good.

τ k (L 2 ) τ k (L 3 ) τ k (L 4 ) τ k (L 5 ) 13 17 18 39 12 0 τ k+1 (L 1 ) τ k+1 (L 2 ) τ k+1 (L 3 ) τ k+1 (L 4 ) τ k+1 (L 5 )
-hot is above warm.

-cool is less than good.

-cold is below cool.

The Fig. 12. shows the concepts built by the sensor. During a learning cycle, the sensor makes a measurement and give it to the teacher (the author in this case), this one makes a qualitative comparison with its interpretation and gives the appropriate action to the sensor. The modification of the perception of the environment is performed around four points in the measurement set (28 The Fig. 13. shows the concepts after the configuration.

Conclusion

After the integration of the analog to digital conversion and the signal processing into intelligent sensors, the integration of a part of the decision process and of the knowledge into the symbolic sensor represents a logical evolution of the decentralization effort of the supervisor system tasks. The symbolic sensor has a perceptive knowledge, materialized through the segmentation of the measurement domain, and a semantics knowledge (the mean of words like "more than" or "increase"). The cooperative configuration enables the acquisition of this knowledge without knowing the relation between the measure, the context and the interpretation. So, the possibility to have a symbolic sensor which can interpret human concepts like comfort or danger can be considered. The expert system, integrated in the sensor, is able to manipulate the knowledge base and the perceptive knowledge, it can take a decision about the sensor itself or about the environment. For example, it can see a failure on itself or determine the context by a communication with the other sensors and the system. This paper has presented a restrictive kind of symbolic sensors working on monodimensional discrete sets of measurement, ordered lexical sets and static phenomena. We actually work on sensors using multidimensional measurement sets and non ordered lexical sets. Furthermore, an extension to a dynamic interpretation and to fuzzy symbolic informations is undergoing.

Fig. 1 .

 1 Fig. 1. Internal scheme of a smart sensor.

Fig. 2 .

 2 Fig. 2. Internal scheme of a symbolic sensor.

Fig. 3 .

 3 Fig. 3. Relationship between a translation and an interpretation

  , x}} and Binf(x) = {{x, succ(x)}} Let us give several examples of the effect, in the set E={0,...,8}, of the adherence and interior operators using Bsup(x) and Binf(x).

Fig. 5 .

 5 Fig. 5. Action of int and adh with Bsup and Binf

Fig. 7 .

 7 Fig. 7. Concepts building.

Fig. 8 .

 8 Fig. 8. principle of cooperative configuration.

Fig. 9 .

 9 Fig. 9. Translation at the learning cycle k.

Fig. 10 .

 10 Fig. 10. New translation after the application of decrease for x=15.

Fig. 11 .

 11 Fig. 11. New translation after the application of increase for x=15.

Fig. 12 .

 12 Fig. 12. The five concepts.

Fig. 13 .

 13 Fig. 13. Result of the configuration.

  o , 25 o , 17 o and 12 o ) during 10 learning cycles. The five first learning cycles are detailed:

	the sensor interpretation is : warm
	τ k+1 (L 2 ) the teacher action is		τ k+1 (L 4 ) : decrease
	12 16 Learning cycle 2 τ k+1 (L 1 ) the temperature is	τ k+1 (L 3 )	: 25 o C	τ k+1 (L 5 )
	17 the sensor interpretation is : warm 11 0 the teacher action is : decrease	39
	Learning cycle 3 the temperature is				: 25 o C
	the sensor interpretation is : warm
	the teacher action is		: decrease
	Learning cycle 4 the temperature is				: 25 o C
	the sensor interpretation is : good
	the teacher action is		: maintain
	Learning cycle 5 the temperature is				: 28 o C
	the sensor interpretation is : hot
	the teacher action is		: decrease
			cool			warm
			13 17	23 27
	0	cold	12	18 22 good	28	hot	39
	Learning cycle 1 the temperature is				: 25 o C


Fatima Salahdine
email: fatima.salahdine@und.edu

Naima Kaabouch
email: naima.kaabouch@engr.und.edu

Hassan El Ghazi
email: elghazi@inpt.ac.ma

Techniques for Dealing with Uncertainty in Cognitive Radio Networks

Keywords: Cognitive radio network, Spectrum sensing, Uncertainty, Bayesian network, Fuzzy logic, Evidence theory

A cognitive radio system has the ability to observe and learn from the environment, adapt to the environmental conditions, and use the radio spectrum more efficiently. However, due to multipath fading, shadowing, or varying channel conditions, uncertainty affects the cognitive cycle processes, measurements, decisions, and actions. In the observing step, measurements (i.e., information) taken by the secondary users (SUs) are uncertain. In the next step, the SUs make decisions based on what has already been observed using their knowledge bases, which may have been impacted by the uncertainty, leading to wrong decisions. In the last step, uncertainty can affect the decision of the cognitive radio system, which sometimes can lead to the wrong action. Thus, the uncertainty propagation influences the cognitive radio performance. Therefore, mitigating the uncertainty in the cognitive cycle is a necessity. This paper provides a deep overview of techniques that handle uncertainty in cognitive radio networks.

I. INTRODUCTION

Wireless networks have grown exponentially over the last decade and the traffic of information has exponentially increased. This has created a high demand for radio spectrum frequency bandwidth. However, most licensed frequency bands are sparsely used or unused by their owners. The U.S. Federal Communications Commission (FCC) and recent studies have shown that with fixed spectrum allocation policy, frequency band utilization ranges from 15% to 85% [START_REF] Masonta | Spectrum decision in cognitive radio networks: A survey[END_REF], which means there are holes in the spectrum. These holes, called white space, are the non-used spectrum by their owner, called primary users (PUs) [START_REF] Akyildiz | NeXt generation/dynamic spectrum access/cognitive radio wireless networks: A survey[END_REF].

In addition to the inefficient utilization of the radio spectrum, the spectrum is a scarce resource. A logical way to overcome the spectrum scarcity is to use it dynamically by sharing the spectrum with other unlicensed users (SUs) without interfering with the transmission of the PUs. This allows SUs to sense unused channels and use them for transmission [START_REF] Yucek | A survey of spectrum sensing algorithms for cognitive radio applications[END_REF]. The opportunistic spectrum access (OSA) has been proposed as a solution for the spectrum allocation problems. The OSA policy allows the spectrum to be shared with all users in contrast to the fixed spectrum access (FSA) policy, in which the spectrum is divided into numerous bandwidths assigned to one or more dedicated users. Under the FSA policy, PUs have access to some specific spectrum bands to transmit their data while others are forbidden [START_REF] Kaabouch | Software-defined and cognitive radio technologies for dynamic spectrum management[END_REF]. In order to advance the use of OSA, several solutions have been proposed, including cognitive radio, which is an enabling paradigm for opportunistic spectrum access.

Cognitive radio is an innovative approach to wireless networking in which the radio device is aware of its environment and has the ability to establish and adjust its parameters autonomously. It has the ability to observe and learn from its environment, adapt to the environmental conditions, and make decisions to use the radio spectrum more efficiently [START_REF] Zeng | A review on spectrum sensing for cognitive radio: Challenges and solutions[END_REF]. Indeed, a cognitive radio can perform the following processes: (1) sensing, which is the comprehension and awareness of the environment; (2) deciding, which is the analysis of results and reliable decision-making based on what is sensed from the environment; and (3) acting intelligently by adapting, changing, and adjusting radio parameters to enhance the performance and overcome the spectrum scarcity issue.

Cognitive radio cycle has three main phases, observation, decision-making, and taking a decision [START_REF] Mitola | Cognitive radio: making software radios more personal[END_REF]. The first stage is critical since it is the stage where the measurements are taken and the spectrums ensign is performed. Multipath fading, shadowing from obstacles and varying channel conditions are the resources of uncertainty and randomness, which affects all the cognitive cycle processes [START_REF] Sun | Wideband spectrum sensing for cognitive radio networks: a survey[END_REF]. When the SUs observe the spectrum and take uncertainty measurements, this uncertainty will be spread to the next stages and this can lead to wrong decisions based on uncertain measurements. SUs make decisions based on what has already been observed using their knowledge bases which may have impacted by the uncertainty. Wrong actions will be then taken. Thus, the uncertainty spreads in all the cognitive cycle stages from the spectrum sensing to the taken action, thus the cognitive radio performance degrades.

Therefore, there is a great need to address these uncertainty problems in the cognitive cycle by sensing the spectrum correctly, making the correct decision, and taking the right action. Existing spectrum sensing techniques, such as energy detection [START_REF] Reyes | Improving the reliability of unmanned aircraft system wireless communications through cognitive radio technology[END_REF] matched filter detection [START_REF] Salahdine | Matched filter detection with dynamic threshold for cognitive radio networks[END_REF], do not consider the uncertainty when measurements are missing or uncertain due to a number of parameters, namely, noise, channel condition changes, fading, shadowing, or interferences. In addition, unknown channel impulse response (CIH) is also an uncertainty resource. CIH represents the channel behavior and its exact value can only be estimated. In order to estimate the fading level in the channel, Doppler and delay spread are considered and can replace the CIH [START_REF] Molisch | Propagation issues for cognitive radio[END_REF].

In order to handle the uncertainty in the cognitive cycle, a model that considers uncertainty in all stages of the cognition cycle should be developed, in which the handling uncertainty solution is applied to provide reliable decisions, leading to intelligent actions by the cognitive radio systems. There is a need for a model that can consider the uncertainty in all cognitive cycle phases to ensure high performance and significant reliability. This paper is a deep overview of the techniques that can mitigate uncertainty in cognitive radio. These techniques are classified into four main categories: probabilistic, fuzzy set theory, possibility theory, and evidence theory methods. The remainder of this paper is organized as follows. Section II represents the uncertainty classification. Section III reviews the handling uncertainty techniques and their application in cognitive radio. Section IV compares the reviewed techniques. Finally, a conclusion is given at the end.

II. UNCERTAINTY CLASSIFICATIONS

According to its origin, uncertainty is classified into two main classes [START_REF] Dubois | Possibility theory in information fusion[END_REF], aleatoric and epistemic, as illustrated in Fig. 1. In general review, aleatoric uncertainty is a statistical uncertainty that reflects the inherent randomness in nature. It represents unknowns that differ each time the same experiment is done. It cannot be eliminated or predicted by collecting more information or knowledge. The studied system can eventually behave differently depending on this uncertainty. In simple terms, it is simply random [START_REF] Tandra | Walls for Signal Detection[END_REF]. Epistemic uncertainty is a systematic uncertainty that is due to a lack of knowledge and subsequent ability to model and measure the studied system. When data are available, epistemic uncertainty can be presented using probabilities and it can be decreased by collecting more information about the studied system [START_REF] Li | Dealing with uncertainty: A survey of theories and practices[END_REF]. Both categories exist in real applications. Aleatoric uncertainty arises from stochastic behavior and epistemic uncertainty arises from parameter estimation. The uncertainty type should be first identified in order to mitigate its spread in a specific system. In [START_REF] Terejanu | Approximate propagation of both epistemic and aleatory uncertainty through dynamic systems[END_REF], the two classes were combined in one as a hybrid framework when both are propagated in a dynamic system.

In the context of cognitive radio, we are handling epistemic uncertainty while spectrum sensing. In order to handle the uncertainty and data deficiency and avoid imprecise decisions, several qualification methods have been proposed under the epistemic type [START_REF] Morgan | Many-valued probability theory[END_REF][START_REF] Parsons | A review of uncertainty handling formalisms[END_REF][START_REF] Awadallah | Quantification of aleatory and epistemic uncertainty in bulk power system reliability evaluation[END_REF][START_REF] Dubois | Possibility theory in information fusion[END_REF]. These methods are classified into four categories: probabilistic, fuzzy set, possibility, and evidence based theories. Fig. 2 illustrates the classifications of the epistemic uncertainty mitigation techniques. Probability theory is the main tool used to estimate all measures of uncertainty. It is a mathematical approach aiming to analyze random phenomena based on random variables, stochastic processes, and events [START_REF] Morgan | Many-valued probability theory[END_REF]. Fuzzy set theory is an alternative way to handle uncertain and imprecise information to make reliable decisions [START_REF] Parsons | A review of uncertainty handling formalisms[END_REF]. Evidence theory is an alternative approach to probabilistic approach for modeling the epistemic uncertainty [START_REF] Awadallah | Quantification of aleatory and epistemic uncertainty in bulk power system reliability evaluation[END_REF]. Possibility theory is a method to mitigate with uncertainty and incomplete or imprecise data in multisource information [START_REF] Dubois | Possibility theory in information fusion[END_REF].

III. HANDLING UNCERTAINTY TECHNIQUES

A. Probabilistic theory based techniques

Probabilistic methods can handle both epistemic through experiments and subjective aleatory uncertainty. Under this category, the degree of belief replaces the knowledge about a system state. The degree of belief is attached to all possible events for the studied system and it is expressed using probabilities since knowledge provides a degree of belief and not certain information. Probabilities relate statements to a state of knowledge. They are expressed as P(A/B), changing with new evidence C to be expressed as P(A/B, C) [START_REF] Morgan | Many-valued probability theory[END_REF]. Using probabilistic theory allows the studied system to choose the best action. Graphical models are examples of techniques classified under this category. Bayesian network [START_REF] Jensen | Bayesian networks and decision graphs[END_REF] and Markov network [START_REF] Yu | Hybrid Markov Models Used for Path Prediction[END_REF] are examples of graphical models.

1) Bayesian Network

Bayesian network is used to present knowledge about an uncertain domain and model how intervening variables influence one another. It allows a system to handle uncertain contexts and express conditional probabilities of events where data is missing [START_REF] Dutt | Handling of uncertainty: A survey[END_REF]. It is a graphical representation of probabilistic relationships between a set of random variables and their conditional dependencies related via a directed acyclic graph, which make it reflects the conditional relations between variables based on directed links between them. These links indicate direct influence from one variable to another, which is the direct dependence between them. The lack of connection identified the conditional independence between variables.

Bayesian models are based on joint probabilities and conditional probabilities to operate and provide probability of how an event is true. The chain rule is used to write any joint probability distribution as an incremental product of conditional distributions. P (x 1, x 2 ….,

x n ) = ∏ i P(x i / x 1, x 2, …., x i-1 ) (1)
where x i is an event, i=1…. n, P(x i ) is the prior probability of x i , and P(x i /x j ) is the conditional probability of x i given x j . The joint probability distribution P(X=x) can be expressed as a function of conditional probabilities associated with each node x i under the conditional independence hypothesis.

P(X=x) = ∏ P(x i /P a (x i )) (2)
where P a (x i ) is the probability of the parent x i of the child x j if x j depends on x i . Bayes' theorem expresses the relations between events using conditional probabilities and it has the form P (x i / x j ) = P (x j / x i ) P(x i ) / P(x j )

This theorem computes probabilities when there is not direct information about an event. It allows the representation of causal dependencies between various contextual events and the obtainment of probability distributions.

The Bayesian models have been used in cognitive radio networks to overcome the uncertainty issues in spectrum sensing. The SUs need to sense the band to find the available channel for transmission. The spectrum sensing problem is reformulated as follows

𝑦(𝑘) = 𝑛 𝑘 , 𝐻0 𝐸 , 𝑒 ./ 0 + 𝑛(𝑘), 𝐻1 (4)
where

where P(y/H 1 ) and P(y/H 0 ) are the probability density functions (PDF) of H 1 and H 0 and P(H 1 ) and P(H 0 ) are the prior probability of H 1 and H 0 . P(H 1 ) and P(H 0 ) are assumed to be known. The PDF of the SU received signal y(n) over an N symbol duration under the hypotheses H 0 and H 1 , respectively, can be written as follows [START_REF] Zheng | Bayesian spectrum sensing for digitally modulated primary signals in cognitive radio[END_REF].

P(y/𝐻 @ ) = A BC D (E)/F 8 GH 8 H=I 0J@ (6)
P(y/𝐻 I ) = A B C E B K L M NO E D F 8 GH 8 H=I 0J@ 𝑃( 𝜑(𝑘)) (7)
Then, from equations ( 6) and ( 7), the likelihood ratio test (LRT) of H 1 and H 0 can be defined as

𝐿𝑅𝑇 𝑦 = 3(4/6 7 ) 3(4/6 8 ) = 𝑒 =U L /H 8 H=I 0J@ cosh (𝑥(𝑘)) (8)
where x(k) = (2√(E s ))/N 0 y(k). From ( 7) and ( 8), the test decision can be deduced by comparing LRT to the threshold δ.

The Bayesian detector is based on the Bayesian decision rule, which aims to minimize the expected posterior cost (EPC) [START_REF] Zheng | Bayesian spectrum sensing for digitally modulated primary signals in cognitive radio[END_REF].

The EPC can be formulated as a function of the cost C ij associated to the decision H i if the state is H j for i, j=0, 1 𝐸𝑃𝐶 = 𝐶 \. 𝑃 𝐻 . 𝑃(𝐻 \ /𝐻 . )

I .J@ I \J@ (9)
From [START_REF] Molisch | Propagation issues for cognitive radio[END_REF], the optimal Bayesian detector can be derived

ln cosh 𝑥 𝑘 > 𝑁𝛾 H=I 0J@ + ln (𝛿) (10)
The threshold is determined using as

𝛿 = 3( 6
The suboptimal Bayesian detector is obtained using approximations for the low and high SNR. The Bayesian rule is also used to derive expressions for P d and P f [START_REF] Srinu | FPGA realization of spectrum sensing based on Bayesian framework for cognitive radio network[END_REF].

Consider a cognitive radio network with N SUs and M licensed channels; the network is modeled by a graph in which each node represents an SU and each edge represents the communication link between the two corresponding nodes (SUs). Bayesian model is used for each SU for decision making and channel selection [START_REF] Li | A graphical framework for spectrum modeling and decision making in cognitive radio networks[END_REF]. In [START_REF] Li | Energy detection based spectrum sensing for cognitive radios over time-frequency doubly selective fading channels[END_REF], spectrum sensing is reviewed under noise uncertainty caused by the channel conditions, which are realistic time-varying multipath fading channels. The authors propose a spectrum sensing scheme, based on energy detection techniques. The proposed scheme deals with uncertainty by estimating both the PU state and time-variant multipath gains. In [START_REF] Tabassam | Game theory in wireless and cognitive radio networks-Coexistence perspective[END_REF], the authors proposed a new approach based on BN and game theory, also called Bayesian games, which allow the analysis of the influence of incomplete data and uncertain information in cognitive radio networks. They address the uncertainty about several "players" decision (SUs) in a cooperative system. In [START_REF] Reyes | A Bayesian network model of the Bit Error Rate for cognitive radio networks[END_REF], a generalized likelihood ratio test (GLRT) is used to address the incomplete knowledge in sensing measurements by considering some parameters known and others unknown and studying the influence and the interactions between them. In [START_REF] Lim | GLRT-based spectrum sensing for cognitive radio[END_REF], in order to learn about the environment conditions, authors proposed a Bayesian network that represents the relationships between variables indicating how the system is performing and identifying which variables affecting bit error rate (BER). Those variables are bit energy to noise spectral density ratio, carrier to interference ratio, modulation scheme, Doppler phase shift, and BER.

2) Markov models

Markov models are undirected graphical models that can be categorized in four divisions used in different situations, according to the system observed (autonomous or controlled) and the system state. These models are Markov chain, Hidden Markov model, Markov decision process, and Partially Observable Markov decision process. The Hidden Markov model is a statistical Markov model [START_REF] Yu | Hybrid Markov Models Used for Path Prediction[END_REF] in which the modeled system is assumed to be a Markovian process with unobserved states. It starts with a Markov chain and adds a noisy observation about the state at each time.

The Markov approach is used in opportunistic spectrum access to model the interactions between PU and SU as continuous-time Markov chains. Hidden Markov models are used to identify the signal features processing in which spectrum activities are Markovian. In [START_REF] Pla | Modeling and characterization of spectrum white spaces for underlay cognitive radio networks[END_REF], the authors proposed a Markov model to obtain the channel holding time, which is the period that the SU uses the free band without PU signal interruption. In [START_REF] Haghighi | An LLR-based cognitive transmission strategy for higher spectrum re-utilization[END_REF], a new scheme is proposed to reduce the spectrum consumption: channels are grouped in clusters, only one channel must to be sensed, and the other channels are estimated using the historical states and their correlation with the sensed channel in the same cluster. The Markov model is used to model the influence of historical states on the current state in which the combination of channel correlation and the Markov model reduces the number of channels which must be sensed to improve sensing performance [START_REF] Yu | Hybrid Markov Models Used for Path Prediction[END_REF].

B. Fuzzy set theory

Fuzzy set theory is an alternative approach for handling uncertain and imprecise data to make decisions and allows the expression of real situations with a mathematical model [START_REF] Parsons | A review of uncertainty handling formalisms[END_REF]. The fuzzy set theory aims to provide a mathematical model to reasoning under uncertainty in detection and decision making. It describes to what degree a decision is certain and reliable using uncertain and imprecise knowledge based on subjective estimation and expert opinions and experiences. Under fuzzy logic, statement truth is not always clear, but depends on a degree of membership to a set or a class; statement truth takes values between 0 and 1, in contrast to classical logic with two possible values: true (1) or false (0). The degree of membership to this set (i.e., the closeness to 0 or 1) indicates the degree of truth of the statement. Fuzzy logic indicates to what degree X is in various sets. The degree of membership in the interval [0, 1] is associated with each element in the fuzzy set [START_REF] Zhou | Representation and reasoning under uncertainty in deception detection: A Neuro-Fuzzy approach[END_REF].

A fuzzy inference system is implemented following a fourstage procedure: fuzzification, fuzzy inference engine, fuzzy rule base, and defuzzification. system's inputs are the measurements that represent uncertainty; inputs are forwarded to determine the membership function the fuzzification stage in which the fuzzy rule IF-THEN is then applied to determine the new outputs set. The fuzzified measurements are used in the next stage, and all rules are aggregating using a fuzzy logic operation (e.g., OR, AND, Union, Intersection). In the final stage, the fuzzy set is converted to a defuzzified set which corresponds to the chance value. Fuzzy probability theory is an extension to handle mixed probabilistic/non-probabilistic uncertainty [START_REF] Mhemed | A fuzzy logic Cluster Formation Protocol for Wireless Sensor Networks[END_REF].

Fuzzy logic is applied to cognitive radio networks in order to make decisions under uncertain environments. SUs make decisions based on information available from the spectrum sensing stage, which includes measurements, incomplete data, and their own knowledge. SUs decide to whether transmit their data depending on what is sensed and then select which channel frequency to use without creating interference to the PUs. The fuzzy logic-based approach can be used to make decisions under incomplete and doubtful data; it can deal with uncertainty in data by transforming imprecise data into precise data based on fuzzy set inference [START_REF] Beer | A summary on Fuzzy probability theory[END_REF]. SUs need specific information about the channel state and this information depends on the spectrum sensing method used in the sensing stage. A fuzzy-based spectrum handoff is proposed in [START_REF] Giupponi | Fuzzy-based spectrum handoff in cognitive radio networks[END_REF] in order to avoid interference to the PUs. The fuzzy inference system estimates the distance between SU and PU and the required SU power for avoiding interference. The results show that fuzzy logic outperforms classical spectrum sensing. In [START_REF] Baldo | Cognitive network access using fuzzy decision making[END_REF], a fuzzy power control scheme is proposed in which a transmit power control system is designed using a fuzzy logic system to permit dynamic control of the transmitted signal power depending on the interference level experienced by PUs. In [START_REF] Banerjee | Energy detection based cooperative spectrum sensing using fuzzy conditional entropy maximization[END_REF], fuzzy conditional entropy maximization is used to design energy detection for cooperative spectrum sensing with the aim to minimize the uncertainty in the threshold selection.

In [START_REF] Liu | An optimal cooperative spectrum sensing scheme based on fuzzy integral theory in cognitive radio networks[END_REF], the authors proposed cooperative spectrum sensing based on the fuzzy integral theory in the context of cognitive radio networks. The proposed scheme seeks to handle the uncertainty in the information provided by the local SUs.

C. Evidence theory

Evidence theory, also called the theory of belief functions or Dempster-Shafer theory (DST), was developed as an alternative technique to probability theory [START_REF] Awadallah | Quantification of aleatory and epistemic uncertainty in bulk power system reliability evaluation[END_REF]. It is a mathematical theory for reasoning and modeling the epistemic uncertainty that reasons with belief and plausibility. Belief provides all evidence available for a specific hypothesis; plausibility offers all evidence which is consistent with this hypothesis. The two concepts give an interval of probabilities, including the true probability, with some certainty. In other words, it combines distinct evidence from several sources to compute the probability of the hypothesis. This evidence is represented by a mathematical function called the belief function. This function considers all evidence available for the hypothesis; a hypothesis and its negation do not have any causal relationship between them, which proves that an ignorance of belief does not involve disbelief, but reflects a state of uncertainty. In order to represent uncertainty in a hypothesis, uncertainty is replaced with belief or disbelief as evidence, which is the concept behind DST. This method suffers from high mathematical complexity and needs all possible states to calculate the exact probability while representing good certainty with additional information about the degree of belief. The DST rule for combination can be defined as the procedure for combining distinct states of evidence. The DST rule for combination consists of a space of mass W and the belief mass as a function denoted m.

m: 2 X → [0, 1] (12)
where X is the set that includes all possible states and 2X is the set of all the subsets of X. DST is able to handle uncertainty, imprecision, ignorance, and lack of data because it is based on the estimation of imprecision and conflict from several sources. In [START_REF] Yu | Hybrid Markov Models Used for Path Prediction[END_REF], evidence theory was used to deal with the uncertainty in a mixed aleatory-epistemic model.

DST is applied in the cognitive radio context to handle uncertainty and an imperfect knowledge in cognition cycles. In [START_REF] Qihang | A distributed spectrum sensing scheme based on credibility and evidence theory in cognitive radio context[END_REF], the authors proposed a distributed spectrum sensing model to improve detection and ensure a reliable and credible spectrum sensing decision. The proposed scheme used the DST to combine the local decisions from several SUs to make the final decision. Each local decision mi is associated with a credibility parameter m i (c) which quantifies the channel condition and sends the information to the access point to make the final decision about the state of the observed band.

It was shown that the proposed scheme performed well in terms of the probability of detection P d and the probability of false alarm P f based on the credibility for hypotheses H 0 and H 1 [START_REF] Qihang | A distributed spectrum sensing scheme based on credibility and evidence theory in cognitive radio context[END_REF]. In [START_REF] Chen | Cooperative spectrum sensing based on double threshold detection and Dempster-Shafer theory[END_REF], a cooperative model was proposed to enhance the reliability of spectrum detection. Energy detection with a double threshold is used for spectrum sensing and the DST is used to make decisions.

D. Possibility theory

Possibility theory is a technique to handle certain types of uncertainty, based on fuzzy set concepts. It is an alternative to probability theory; and an extension to fuzzy logic theory. It permits handling of uncertainty in multisource information [START_REF] Dubois | Possibility theory in information fusion[END_REF]. It is characterized by the possibility Poss measures, which assign numbers to each subset W based on fuzzy logic [39]. Possibility theory rules different from probability theory rules; possibility distribution is defined as

Poss: W → [0, 1] , max (A ∈W, Poss (A) = 1) (13)
Conditional independence in possibility theory allows modeling the dependence between uncertain variables as in probability theory, and can be defined as

Poss (A, B/C) = Poss (A/C) ⊗ Poss (B/C) (14)
In order to model the available information, possibility and necessity measures are considered based on possibility distribution. Possibility theory is sued to handle only epistemic uncertainty, and it is a special case or a subset of evidence theory. Possibility logic was applied in many filed including signal processing to handle noise uncertainty in signal propagation. Noise nature cannot be assumed, estimating the noise level in each sample based on some signal characteristics was treated by applying possibility theory which considered the lack of knowledge about noise; noise uncertainty is due to random perturbation propagated through the transmission channel [START_REF] Loquin | Noise quantization via possibilistic filtering[END_REF]. Theory of possibility applied on cognitive radio network as a special case of theory of evidence already reviewed, especially for optimization problems.

IV. METHODS COMPARISON

Several techniques to handle the uncertainty propagation were reviewed. Selecting a solution depends on several criteria, requirements, conditions; and especially the trade-off between precision and complexity. Through analyzing the different techniques, we can conclude that methods that offer good precision represent high complexity. All techniques had their weaknesses and strengths. The choice of which technique to use depends on the problem to be solved.

Probabilistic theory is a powerful tool of handling uncertainty if precise uncertainty is required. The Bayesian network as a probabilistic method is more efficient and it is the most used to present, reason, and model uncertainty. However, it needs prior probability distributions because in practice measurements and parameters are not always Gaussian. Fuzzy theory is easy to implement, it is more suitable for problems that didn't require precise knowledge of uncertainty, but it handled a degree of truth and not the uncertainty. For evidence theory, it provided additional information about the degree to which information is available. DST is more general than possibility and probability theory. There are other approaches that combine various techniques as a tool to mitigate the hybrid uncertainty. Table I Understanding uncertainty in the context of the cognitive radio network can be considered the most important task in modeling this uncertainty and mitigating it, identifying its type, its source and its influence on the cognitive radio system. As reviewed, Bayesian models and fuzzy logic are the most used in spectrum sensing for reasoning under uncertainty and making decision.

V. CONCLUSION

In order to improve access to the limited radio spectrum, DSA is proposed as a solution to overcome the spectrum scarcity problem. Spectrum sensing is the main task of cognitive radio permitting opportunistic access to the spectrum based on decisions made by the SUs. However, due to the randomness features of communication channels, uncertainty impacts all the processes of the cognitive cycle, including the sensing results at SUs receivers. Making decisions under uncertainty is a challenge that cognitive radio systems must face. This paper examined several models and methods to deal with uncertainty. Among these are a probabilistic theory, fuzzy set theory, possibility theory, and evidence theory. Each of these has advantages and disadvantages. The overarching objective of all these methods is to overcome the error made by the detector due to fading, shadowing, and uncertainty noises, to minimize the sensing error, and to enhance the fidelity of sensing outcome and the sensing decision.

Fig. 1 .

 1 Fig. 1. Uncertainty categories.

Fig. 2 .

 2 Fig. 2. Representation of methods to handle uncertainty.

  summarized and compared the listed techniques.

TABLE I TECHNIQUES COMPARISON Probability theory Fuzzy logic theory Evidence theory Possibility theory

 I

						-
	-Deal		with	-Deal	with	-Deal with epistemic
	randomness	and	imprecise	vague	uncertainty
	subjective			information		Deal with
	uncertainty					-Used where there is	incomplete or
	-Handle epistemic	-Describe o what	some degree of	imprecise data in
	and	aleatory	degree a decision is	ignorance	multisource
	uncertainty			certain and reliable	(incomplete model)	information
	through			using uncertain and
	experiments		imprecise
				knowledge
	-Powerful		for	-Precision	and
	handling			stability	not
	uncertainty in case	guaranteed
	precise uncertainty	-Performance		Improves the
	is required			measured a		More Flexible	precision of
	-Based		on	Posterior		evidence
	mathematical		-Based on user
	probability		to	experience	and
	predict an event	interpretation
	-Applied to all	-Applied	to	-Computationally
	systems -Complex		data	systems that are difficult to model	High complexity	simple -Complexity close
	handling			-Easy to implement	to that of classical
	-Inexac / incorrect	and interpret		logic
	One valued approaches (Truth is one-valued)	Set valued approaches (Truth is many-valued)	Two valued approaches (Truth is 2-valued)	Two valued approaches (Truth is 2-valued)
	Degree of belief	Degree of membership to set	Belief and Plausibility	Possibility measures