Mohamed Rabie Oularbi

Saeed Gazor

Abdeldjalil Aissa

El Bey

Sébastien Houcke

Physical Layer Metrics Estimation for CSMA/CA Networks Using a Markov Modeling and Source Enumeration

come

L'archive ouverte

I. INTRODUCTION

Wireless communication standards are facing a proliferation leading to coexistence of different networks belonging to different administrative domains which makes the radio environment heterogeneous. At the same time, there is an emerging trend to provide ubiquitous wireless access to mobile terminals while the Quality of Service (QoS) needs to be maintained by the upper layers applications. In order to make such an operation possible, and to take advantage of Physical Layer Metrics Estimation for CSMA/CA Networks Using a Markov

Modeling and Source Enumeration

Mohamed-Rabie Oularbi, Saeed Gazor, Abdeldjalil Aïssa-El-Bey and Sébastien Houcke the heterogeneity the terminal shall be smart to sense the surrounding environment and switch cognitively from a standard to another, e.g., if the first one is not satisfying the required QoS. This switching process is known as vertical handover and is possible if the mobile terminal could sense its environment and accordingly/cognitively reconfigure its communication parameters to better adapt to the channel conditions. Thus, the operation of such a cognitive system includes two stages: sense and decide. This paper deals only with the sensing task, prior to perform a vertical handover, where the terminal has to evaluate some relevant metrics that are informative about the QoS of the available networks of interest.

In the context of vertical handover, only the passive estimation is relevant since the terminal seeks to know a priori if a network satisfies its QoS needs without wasting time and power to get connected to this network. To satisfy those conditions, the algorithm here proposed, relies on a physical layer sensing and requires no connection to the access point, no synchronization, no signal demodulation and no frame decoding.

Our networks of interest are based on a carrier sense multiple access with collision avoidance (CSMA/CA) protocol like WiFi (IEEE 802.11). It has been highlighted in [START_REF] Dai | Vertical handover criteria and algorithm in[END_REF], [START_REF] Guo | A seamless and proactive end-to-end mobility solution for roaming across heterogeneous wireless networks[END_REF] that the usage of the channel bandwidth in a CSMA/CA system can be approximated as the ratio between the time in which the channel status is busy according to the NAV (Network Allocation Vector) settings and the considered time interval. The higher the traffic, the larger the NAV busy occupation, and vice versa. Then, once we read a NAV value during a certain time window, the available bandwidth and access delay can be estimated [START_REF] Zhang | Efficient Mobility Management for Vertical Handoff between WWAN and WLAN[END_REF]. The main drawback of this method is that it requires to be connected to the access point in order to obtain the NAV information from the header, this may increases the decision time if many standards or Access Point (AP) are detected. An alternative technique has been presented in [START_REF] Oularbi | Vertical Handover Metrics Estimation for OFDM Based Systems[END_REF], [START_REF] Oularbi | Physical layer ieee 802.11 channel occupancy rate estimation[END_REF], [START_REF] Oularbi | Two physical layer metrics for vertical handover towards an ieee 802.11n network[END_REF] for the estimation of the channel occupancy rate. This technique relies on a physical layer sensing, but requires the knowledge of noise variance and does not give any information about the collision rate which is a complementary metric to the channel occupancy rate. Indeed, in [START_REF] Duffy | Modelling 802.11 wireless links[END_REF] it has been shown that the collision rate is depends on the number of users connected to an access point, and in [START_REF] Raptis | Packet delay metrics for ieee 802.11 distributed coordination function[END_REF] is is stated that the mean of the MAC (Media Access Control) delay associated with a transmission by a particular source is increasing exponentially with the probability of collision. Thus, higher is the collision rate, lower is the available QoS. To the best of our knowledge, the only passive technique for collision detection has been studied in [START_REF] Oularbi | Vertical Handover Metrics Estimation for OFDM Based Systems[END_REF], [START_REF] Oularbi | Two physical layer metrics for vertical handover towards an ieee 802.11n network[END_REF]. Unfortunately, this method needs the knowledge of the edges of the frame (the start and end points) in order to apply information theoretic criterion to test if a collision is occurred. As the receiver doesn't know the exact times when the frame starts and ends, this technique can not be directly applied and requires the edges to be estimated as additional unknown parameters.

From a physical layer perspective, the problem of estimating the channel occupancy rate and the collision rate can be viewed as a source enumeration problem. In fact, the data frames of each user can be viewed as a signal emitted by one source, and the collided frames as a mixture of two or more sources. Rank tracking is a classical model order selection problem that arises in a variety of important statistical signal and array processing, however it is a relatively addressed infrequently in the extant literature [START_REF] Kavcic | Adaptive rank estimation for spherical subspace trackers[END_REF], [START_REF] Rabideau | Fast, rank adaptive subspace tracking and applications[END_REF], [START_REF] Real | Two algorithms for fast approximate subspace tracking[END_REF], [START_REF] Perry | Minimax rank estimation for subspace tracking[END_REF]. In this paper, to achieve this recursive estimation, we propose a new algorithm based on a Markov chain model. Assuming that a maximum of M sources can be present at any observation time, we model the system by a M + 1 states chain (see Figure 1, M states for the sources plus one for the case that no source is active). Our proposed algorithm estimates the number of sources, recursively, in four steps and is an extension of the one proposed in [START_REF] Taherpour | Adaptive spectrum sensing and learning in cognitive radio networks[END_REF] which has been proposed for spectrum sensing.

The application to CSMA/CA based networks is then straightforward. In several papers, such networks have been modeled by a Markov process and their performance have been studied [START_REF] Bianchi | Performance analysis of the ieee 802.11 distributed coordination function[END_REF], [START_REF] Mcdougall | Sensitivity of wireless network simulations to a two-state markov model channel approximation[END_REF], [START_REF] Vercauteren | Online bayesian estimation of hidden markov models with unknown transition matrix and applications to ieee 802.11 networks[END_REF]. In most of these papers, a two state Markov chain is used (good state and bad state).

In our model, we employ a chain with three states: no transmission, one source, and collision.

The objective of the channel sensing is to detect this state. After a period of time, we can easily estimate the channel occupancy rate as the ratio of the total time intervals where the channel is declared as busy (number of sources is not zero) to the total observation time. In addition, the collision rate is estimated as the ratio of the number of frames detected to be involved in a collision to the total number of frames detected during the observation time.

The remaining of the paper is organized as follows. In Section II, we formulate the problem and present the Markov model for tracking the number of source. In Section III, we propose a four step algorithm based on the Markov model for the number of source tracking, the algorithm is presented for a general case and can be used in other applications. In Section IV, we explain how the proposed algorithm is used for a WiFi network. In Section V, we evaluate the performance of the proposed algorithm on the estimation of the channel occupancy rate and the collision rate for a WiFi network. Finally, Section VI, concludes the paper. Throughout this paper we denote: E[.] for mathematical expectation, (.) T for conjugate transposition, (.) H for complex conjugate transposition, . for Frobinius norm, |.| for absolute value, ⊙ for the element wise vector product, I N for N × N identity matrix, ← for overwriting, and diag(.) for diagonal matrix with entries given by elements of (.).

α 0 β 1 α 1 β 2 α M β M 1 -α0 1 -α1 -β1 1 -βM

II. MODEL

Let consider a receiver equipped with N antennas, and x(k) = [x 1 (k), . . . , x N (k)] T denote the received signal at the time instant k. be a mixture of maximum K < N independent signals as follows

x(k) = H(k)s(k) + w(k), (1)
where H(k) ∈ C N ×K is the channel matrix, s(k) ∈ C K×1 is the transmitted data vector and w(k) ∈ C N ×1 is a zero=mean additive white Gaussian noise with variance of σ 2 (k) which is independent with s(k).

The sources are rising transmitting their packets and vanishing upon the time. As a result, the number of active sources K varies with time k and needs to be estimated k iteratively with time k. The classical rank estimation methods are computationally expensive. Thus, we here propose a new approach using a Markov Model. Since, it is very unlikely that more than one source vanish or arise at any given time instance, we can used the Markov chain in Figure 1, where states/hypothesies are defined as follows

                   H 0 :
where M is known and denotes the maximum number of sources that may be active (thus, we

have K ≤ M < N). If no knowledge is available about M, one can set M to N -1.
In Figure 1, the transition probabilities α i for i = 0, . . . , M -1 represent the probability that the channel is occupied by i + 1 sources given that it was occupied by i sources in the previous sensing time.

The probabilities β i for i = 1, . . . , M are the probabilities that i -1 sources are present at the present sensing time given that i sources were present in the previous sensing time. We must note that at a given time instance we have multi-hypothesis composite test problem with some a priori estimates for the unknown parameters.

In our model, the Mobile stations signal are assumed as zero-mean, white, independent and circularly symmetrical complex Gaussian random variables with variances of {ς 2 i (k)} K i=1 at time k. These variances depend on the power of transmitters the channel gains which are unknown and vary with time. We assume that these variances are almost constant or change smoothly from each sensing time to the next. Thus, the distribution of the random vector process x(k) is characterized by its covariance matrix at time k is shown by

R(k) = E[x(k)x H (k)]. (3)
Note that it is implicitly assumed that the process x(k) is non-stationary. The non-stationarity has two different reasons. The first one is that the number of the components of s(k) changes with time as sources vanish or arise. The second reason is that the channel responses H(k) and

{ς 2 i (k)} K i=1
vary with time. However, we assume that H(k) and {ς 2 i (k)} K i=1 vary very smoothly with time. In other words, our assumption is that only the changes in the number of sources creates sudden changes in the eigenstructure of the unknown matrix R(k). The eigenvalue decomposition (EVD) of the matrix R(k) can be written as

R(k) = U(k)Λ(k)U H (k), (4)
U(k)U H (k) = I N . (5)
where

Λ(k) = diag[λ 1 (k), λ 2 (k), . . . , λ N (k)], U(k) = [u 1 (k), u 2 (k), . . . , u N (k)], λ i (k)s are
the eigenvalues and u i (k)s are the orthonormal eigenvectors. Without loss of generality it is

convenient to assume λ 1 (k) ≥ λ 2 (k) ≥ • • • ≥ λ N (k) ≥ 0.
Under Hypothesis H m , the autocorrelation matrix expressed in (3) can be written as

R(k) = H(k)        ς 2 1 (k) 0 . . . 0 0 ς 2 2 (k) . . . 0 . . . . . . . . . 0 0 . . . ς 2 m (k)        H H (k) + σ 2 (k)I N . (6)
Since the number of sources can change with time, the above EVD structure is also subject to modification and thus needs to be tracked. A simple but computationally exhaustive form of subspace tracking consist of performing the estimation of the all EVD parameters for every new observation x(k). To reduce computational complexity, we are interested in algorithms that can estimate Λ(k) and U(k) adaptively using the previous estimates of Λ(k -1) and U(k -1).

These subspace algorithms seek to satisfy the following equation

U(k) Λ(k) U H (k) = (1 -ǫ) U(k -1) Λ(k -1) U H (k -1) + ǫx(k)x H (k) (7)
where the constant ǫ ∈ (0, 1) is called the forgetting factor and determines the effective length of the exponential window 2-ǫ ǫ [START_REF] Yazdian | On the spectral distribution of the windowed sample covariance matrix[END_REF]. A larger value for ǫ < 1 results in a better tracking capability in an environment where H(k) and {ς 2 i (k)} K i=1 vary faster with time (e.g., for larger speeds).

III. PROPOSED ALGORITHM

In our algorithm, for updating EVD, we propose to use the PROTEUS-1 algorithm proposed by B. Champagne et al. [START_REF] Champagne | Plane rotation-based evd updating schemes for efficient subspace tracking[END_REF]. There are several other alternative algorithms that could be used.

This algorithm is computationally efficient using a CORDIC processor as it uses only plane rotations for updating the eigenvectors and directly provides the set of orthonormal eigenvectors which a well suited subspace tracking algorithm for our multi-hypothesis problem which deals with non-stationary data.

In [START_REF] Oularbi | Two physical layer metrics for vertical handover towards an ieee 802.11n network[END_REF] the number of active sources is the number of eigenvalues of R(k) which are larger than σ 2 (k) and is in fact a function of the time k and needs to be determined. We propose the following a four steps soft enumeration algorithm to determine the probability of each hypothesis in (2), recurssively.

STEP 0: Initialization step: We define P m k|k-1 as the a priori probability of having m active sources at time k

P m k|k-1 = P [H m at time k|O(k -1)] (8)
where the hypothesis H m denotes the event that m sources are active and O(k -1) denotes the available information and observation up to the instant k -1. At the instant k = 0, in the absence of any knowledge, we initialize the a priori probabilities as

P m 0|-1 = 1 M , ∀m = 1, . . . , M.
The EVD of the received signal, U(0) and Λ(0) are initialized randomly. STEP 1: Sense and Update: Receive x(k) and perform the preprocessing and normalization steps in PROTEUS-1 [START_REF] Champagne | Plane rotation-based evd updating schemes for efficient subspace tracking[END_REF] as follows 1) Projection :

y(k) = U H (k -1)x(k);
2) Mapping into real vector elements:

y(k) ← D H (k)y(k), U(k) ← U(k -1)D(k) using D(k) = diag( y 1 (k) |y 1 (k)| , • • • , y 1 (k) |yn(k)| )
where y i (k) denotes the ith entry of the vector y(k). 3) Reordering/sorting: Find the permutation matrix Π which reorder the entries of y(k) the decreasing order and

y(k) ← Π T y(k), U(k) ← U(k)Π, Λ(k) ← Π T Λ(k -1)Π
4) Update the EVD using as follows [START_REF] Champagne | Plane rotation-based evd updating schemes for efficient subspace tracking[END_REF]:

for i = 1 : N -1 do for j = i + 1 : N do θ ← y i (k)y j (k)/( λ i (k) -λ j (k)) U(k) ← U(k)G ij (θ) end for end for 5) λ i (k) ← (1 -ǫ) λ i (k) + ǫy 2 i (k)
where G ij (θ) is the well-known plane or Givens rotation matrix defined by

G ij (θ) =           I i-1 cos(θ) . . . sin(θ) . . . I j-i-1 . . .
-sin(θ) . . . cos(θ)

I N -j           . ( 9
)
The computational cost of this step, as stated in [START_REF] Champagne | Plane rotation-based evd updating schemes for efficient subspace tracking[END_REF], is equal to 6N

σ 2 m (k) = 1 N -m N i=m+1 λ i (k), under H m . ( 10
)
This expression represents the maximum likelihood (ML) estimator of the noise variance only for a rectangular window, whereas we are using an exponential window. Our simulation results reveal that as the number of sources change with time the estimate of noise variance will vary significantly. Thus, we used the following alternative estimator under H 0

σ 2 0 (k) = λ N (k), under H 0 . ( 11
)
This estimator is more robust than

σ 2 0 (k) = 1 N N i=m+1 λ i (k)
to the variation of number and power of sources and is more suitable for environments with fast changing dynamics. We must note that λ i (k)s are eigenvalues of [START_REF] Duffy | Modelling 802.11 wireless links[END_REF] and are biased estimators for the true eigenvalues of R(k). In fact, the bias using

σ 2 0 (k) = λ N (k) is than less using σ 2 0 (k) = 1 N N i=m+1 λ i (k).
Obviously some performance gain can be obtained using more elaborate estimators such as the recently proposed ones in [START_REF] Yazdian | Eigenvalue estimation of the exponentially windowed sample covariance matrices[END_REF]. Given these estimates the Log-Likelihood functions for m ≥ 1 are estimated as follows

L(x(k)|H m ) = log ǫ m -(N -m) log(π σ 2 m (k)) (12)
- 1 σ 2 m (k) x(k) -V m (k)V m (k) H x(k) 2 - m j=1 log(π λ j (k)) - 1 λ j (k) |u H j (k)x(k)| 2
and for under H 0 as

L(x(k)|H 0 ) = -N log(π σ 2 0 (k)) - 1 σ 2 0 (k) x(k) 2 (13)
where

V m (k) = [u m+1 (k) u m+2 (k) . . . u N (k)].
The term ln( ǫ m ) is an additional penalty function introduced to avoid overestimation. The reason is that the larger values of m involves more unknown parameters which result in a larger bias in the estimation of the Log-Likelihood functions. The function ln( ǫ m ) is obtained in an empirical manner comforted by simulations and may be justified using the asymptotic distribution of the eigenvalues [START_REF] Yazdian | On the spectral distribution of the windowed sample covariance matrix[END_REF]. The overall computational cost of this step is equal to N 2 + 2N + M(N 2 + N + 4) + 9. STEP 3: Updating posterior probabilities: In this step, we combine the priori probabilities P m k|k-1 defined in [START_REF] Raptis | Packet delay metrics for ieee 802.11 distributed coordination function[END_REF], and the Log-Likelihood functions in ( 12) and ( 13), to obtain the posterior probabilities defined as

P m k|k = P [H m at time k|O(k)]. (14)
In fact, P m k|k and P m k|k-1 denote the estimated probabilities of presence of m sources at the sensing time k, respectively with or without the use of the current available vector of observation x(k).

Let P k|k = [P 0 k|k , . . . , P M k|k ] T and P k|k-1 = [P 0 k|k-1 , . . . , P M k|k-1 ] T denote the vectors containing the M + 1 posterior and a priori probabilities, respectively, and

F(k) = [exp(L(x(k)|H 0 )), • • • , exp(L(x(k)|H M ))] T (15)
be the vector containing the M + 1 likelihood values where (m+ 1)th element of F(k) represents an estimate of f (x(k)|H m ). By exploiting the Bayes rule, we obtain posterior probability vector as

P k|k = 1 F T (k)P k|k-1 F(k) ⊙ P k|k-1 . (16)
A hard decision can be made on the rank, according to the most probable hypothesis,i.e.

K = arg max m {P 0 k|k , . . . , P M k|k }. (17)
The computational cost of this step is equal to 3(M + 1).

Sense x(k)

Update the EVD thanks to PROTEUS-1 [START_REF] Champagne | Plane rotation-based evd updating schemes for efficient subspace tracking[END_REF] Compute the Log-Likelihood Functions [START_REF] Perry | Minimax rank estimation for subspace tracking[END_REF] Update Posterior Probabilities ( 16) Prediction [START_REF] Champagne | Plane rotation-based evd updating schemes for efficient subspace tracking[END_REF] Deceide on the rank, given the most probable state for the next sensing time is needed to compute the posterior probabilities expressed in [START_REF] Vercauteren | Online bayesian estimation of hidden markov models with unknown transition matrix and applications to ieee 802.11 networks[END_REF]. We use the Markov model illustrated in Figure 1 to predict these probabilities as

P k+1|k = TP k|k (18)
where the transition matrix of the Markov chain T as shown in Figure 1 is given by

T =            1 -α 0 α 0 0 . . . 0 β 1 1 -α 1 -β 1 α 1 . . . . . . 0 β 2 1 -α 2 -β 2 . . . 0 . . . . . . . . . . . . α M -1 0 . . . 0 β M 1 -β M            . (19)
A flow-chart of this algorithm is presented in Figure 2 and Algorithm 1.

The computational cost of this last step is equal to (M + 1) 2 , thus, the overall computational cost of the proposed algorithm is equal to the sum of the CCs of each step, that is 6N 3 + (M + 16.5)N 2 + (M + 9.5 + ν)N + 7M + 12.

IV. APPLICATION TO CSMA/CA BASED WIRELESS NETWORKS

The proposed algorithm in the previous section gives an estimate of the number of active sources at each sensing time, recursively. In addition for the context of metric estimation, the soft information in P k+1|k can be used to more accurately extract other information. In particular, the values 1 -P 0 k|k and 1 -P 0 k|k -P 1 k|k represent instantaneous estimates of the probabilities that

y(k) = U H (k -1)x(k); 5: D(k) = diag(y i (k)/|y i (k)|); 6: y(k) ← D H (k)y(k); 7: U(k) ← U(k -1)D(k); 8: y(k) ← Π T y(k); 9: U(k) ← U(k)Π; 10: Λ(k) ← Π T Λ(k -1)Π;
11:

for i = 1 : N -1 do 12:

for j = i + 1 : N do 13: θ ← y i (k)y j (k)/( λ i (k) -λ j (k)); 14: U(k) ← U(k)G ij (θ); 15:
end for 16:

end for 17:

Λ(k) ← (1 -ǫ) Λ(k) + ǫdiag(y 2 i (k)); 18:
for m = 0 : M do 19:

Compute σ 2 (k) according to [START_REF] Real | Two algorithms for fast approximate subspace tracking[END_REF]; end for 23:

P k|k = 1 F T (k)P k|k-1 F(k) ⊙ P k|k-1 ; 24:
Decide on the rank according to the most probable hypothesis; 25:

P k+1|k = TP k|k 26: end for H 0 H 1 H 2 Noise One source Collision α 0 β 1 α 1 β 2 1 -α0 1 -α1 -β1 1 -β2
Fig. 3. Markov Model for the PHY layer of a WiFi Channel system is occupied and has a collision, respectively. Thus, averaging these values over time we can estimate the occupancy and collision rates of samples.

We here apply this proposed algorithm to estimate the channel occupancy rate and the collision rate of a WiFi access point. The IEEE 802.11 (WiFi) communication relies on the protocol CSMA/CA. Carrier sense multiple access with collision avoidance (CSMA/CA) is a multiple access method , in computer networking. Any node wishing to transmit data must first listen to the channel for a predetermined amount of time and determine whether or not the channel is used by another node. Only if the channel is identified to be "idle," then the node is permitted to begin the transmission process. Otherwise if the channel is sensed as "busy," the node defers its transmission and wait for a random period of time called backoff. Thus, there are Inter Frame Spacing (IFS) time intervals between any two consecutive frames during which the observed signal consist of only noise samples. Whereas during data frames, we have signal plus noise.

During transmission of data frames, the observed samples can be from one source plus noise or from two (or more) sources in the case of a collision. Thus from a physical layer point of view, the WiFi communication can be modeled as a Markov chain with three states as illustrated in (

) 20
where 1 -α 0 ∈ (0, 1) represents the probability of idle channel when the channel was idle in the previous sensing time, 1 -α 1 -β 1 ∈ (0, 1) represents the probability of busy channel when the channel was busy in the previous sensing time. Finally 1 -β 2 ∈ (0, 1) represents the probability of a collision when a collision was detected in the previous time. The transition matrix of the Chain is

T =      1 -α 0 β 1 0 α 0 1 -α 1 -β 1 β 2 0 α 1 1 -β 2      (21)
We assume that the cognitive device is equipped with more than two antennas N > 2.

V The matrices U(0) and Λ(0) are initialized by first observing 10 samples on the channel of interest and computing the true EVD of the set of observation. In Figure 4, we plot an example of a sensed communication, the observation is made of two frames : the first frame is a product of a collision between a frame with an observed SNR=15 dB at the cognitive observer, the second frame is emitted by a single source observed with a SNR=10 dB. The top figure represents the posterior probabilities versus time. the decision on the rank (illustrated in the bottom) is made according to the hypothesis presenting the maximum posterior probability. We observe that under these scenario, our algorithm has a good tracking capability. The overestimation that appear in the beginning, is negligible and may be due to the fact that the algorithm needs time to converge. Some delays during the transition from a rank to another appear, for example, the transition from the rank one to two in the figure occurs with a delay of 22 samples, and from the rank two to one occurs after 24 samples. These delays are proportional to the eigenvalue tracking algorithm exponential window 1 ǫ = 1 0.05 = 20. Note that the delays from the state "two sources" to "one source" and vis versa have no impact on the performance of the algorithm. Indeed, the length of the collision does not matter to us, it is the number of collision that is important in our case. In the other side, the delays occurring when transiting from the states "one source" and "noise" are important because they determine the length of the frame, parameter that we are going to use when computing the channel occupancy rate.

In Figure 5, we have conducted simulation in the same scenario as in Figure 4 but using a transition probability α 0 100 times greater. We remark that the tracking capacity of the proposed algorithm is affected by this action, and that the algorithm is sensitive to the choice of the transition matrix T.

As stated previously the channel occupancy rate noted C or is defined as being the ratio between the amount of time where the channel is considered as being busy and the length of the observation window. According to our model illustrated in Figure 3, the C or is processed

where N s is the length of the observation window.

The collision rate is defined as the number of frame issued of a collision (rank>1) divided by the total number of frames on the observation window, that is

R col = Number of collided frames Total number of frames . ( 23
)
Note that the temporal average of P 2 k|k gives the collided rate of signal samples. However, the reason that we use (23) instead of the average of is that P 2 k|k in the MAC layer, the required metric of interest is the collision rate of the frames and not that of samples.

As the algorithm proposed in [START_REF] Oularbi | Vertical Handover Metrics Estimation for OFDM Based Systems[END_REF], the proposed approach suffers in some cases of fluctuations. These fluctuations mainly appear during the transition from a hypothesis to another one, and their duration is proportional to the forgetting factor ǫ. Specially at high SNRs, as the contrast between the eigenvalues become bigger, we noticed that these fluctuations are mainly an overestimation that rapidly vanishes with time. To overcome this problem, we utilize the smoothing algorithm proposed in [START_REF] Oularbi | Vertical Handover Metrics Estimation for OFDM Based Systems[END_REF] which have been tested experimentally on real WiFi signals and shown its efficiency. This smoothing algorithm rely on the fact that in a CSMA/CA algorithm the smallest silence period is an SIFS (Short InterFrame Spacing) and no other frame has a length smaller than it. Hence, if our algorithm meet a frame of size less that the size of an SIFS, it will automatically affect to it the number of source of the frame that comes after it. Once, this smoothing operated the channel occupancy rate and the collision rate are computed thanks to ( 22) and (23).

To evaluate the performance of the proposed method versus the SNR, we realized simulations under the following scenario : a WiFi communication is intercepted, the true channel occupancy rate is equal to 64.97% and the collision rate is equal to 40%. The observation window contains 7880 samples, and is constituted of 5 frame with two of them issued from a collision as illustrated in Figure 6.

where R and R are the estimated and the true channel occupancy rates, respectively. In this figure, we compare the performance of the proposed algorithm to the one proposed in [START_REF] Oularbi | Vertical Handover Metrics Estimation for OFDM Based Systems[END_REF] which requires the knowledge of the noise power σ 2 w . We observe that for Signal to Noise Ratios (SNR) below than 12 dB, the two techniques have similar performance when the Markov approach is out performed by the approach proposed in [START_REF] Oularbi | Vertical Handover Metrics Estimation for OFDM Based Systems[END_REF] for higher SNRs. The performance of the Markov approach are very attractive since it achieve NMSE very close to the one in [START_REF] Oularbi | Vertical Handover Metrics Estimation for OFDM Based Systems[END_REF] without the knowledge of the noise power. In the same figure, is plotted the performance of the proposed algorithm when α 0 is chosen 100 times bigger. We observe that even with this bad choice of the transition probabilities the proposed algorithm still has a good estimation capabilities of the channel occupancy rate. Figure 8 compares the performance of our algorithm to the ones proposed in [START_REF] Oularbi | Two physical layer metrics for vertical handover towards an ieee 802.11n network[END_REF], [START_REF] Oularbi | Vertical Handover Metrics Estimation for OFDM Based Systems[END_REF]. We observe that the proposed approach out performs both techniques based on Akaike Information Criterion (AIC) and Minimum Description Length (MDL). this mainly due to the fact that the estimation is done jointly in our approach, when in the other hand for [START_REF] Oularbi | Two physical layer metrics for vertical handover towards an ieee 802.11n network[END_REF], [START_REF] Oularbi | Vertical Handover Metrics Estimation for OFDM Based Systems[END_REF] we first need to estimate the number of frame using [START_REF] Oularbi | Physical layer ieee 802.11 channel occupancy rate estimation[END_REF] than extract the ones suffering of a collision. Thus two independent sources of error are possible in that case : one in the numerator and one in the denominator. However, conversely to the C or estimation when α 0 became 100 time bigger the algorithm lose it accuracy and our approach is outperformed when estimating the collision rate. The main advantage of the propsoed approach lies on the fact that it does not require any algorithm to detect the frames edges, when the approach proposed in [START_REF] Oularbi | Two physical layer metrics for vertical handover towards an ieee 802.11n network[END_REF], [START_REF] Oularbi | Vertical Handover Metrics Estimation for OFDM Based Systems[END_REF] needs to know perfectly the edges of the frame to perform AIC and MDL on it and then decide weather a collision occurred or not. Markov chain approach Approach proposed in [START_REF] Oularbi | Physical layer ieee 802.11 channel occupancy rate estimation[END_REF] Markov chain approach α 0 × 100

VI. CONCLUSION

In this paper, we presented a new method for joint estimation of the channel occupancy rate and collision rate of a CSMA/CA based network. The proposed four steps algorithm is based on a Markov chain modeling, and can be extended for any application that requires number of sources tracking. Numerical simulation show that our proposed algorithm well behaves for the practical SNR operating range of wireless networks. Our algorithm is computationally cheap and performs noise variance estimation.

SNR (dB) NMSE on the collision rate

Markov chain approach AIC based approach MDL based approach Markov chain approach, α 0 x100

Fig. 1 .

 1 Fig. 1. Markov Chain Model for adaptive source enumeration.

Fig. 2 .

 2 Fig. 2. Flow chart of the proposed algorithm

Algorithm 1 1 ; 2 : 3 :

 1123 Adaptive Source Enumeration 1: Initialize : U(0), Λ(0) and P 0|-Sense x(k) for k = 1 : N s do 4:

  x(k)|H m ) thanks to[START_REF] Perry | Minimax rank estimation for subspace tracking[END_REF];21: Deduce f (x(k)|H m ) = exp(L(x(k)|H m )); 22:

Figure 3 which means M = 2 .H 0 :H 1 :H 2 :

 2012 Figure 3 which means M = 2. The three states of the chain are         

Figure 3

 3 Figure 3 are as follows : α 0 = 10 -4 , α 1 = α 0 /2, β 1 = 10α 0 and β 2 = 40β 1 . These probabilities have been determined empirically by simulations.

Fig. 4 .

 4 Fig. 4. Example for tracking capacity of the algorithm : (a) Magnitude of the observed signal, (b) a posteriori probabilities and (c) Real and estimated rank.

Fig. 5 .

 5 Fig. 5. Example for tracking capacity of the algorithm when changing the transition matrix elements such that α0 is 100 times greater than in the scenario of Figure 4.

Figures 7

 7 Figures 7 illustrates the NMSE (Normalized Mean Square Error) of the estimation of the channel occupancy rate defined as

Fig. 6 .

 6 Fig.[START_REF] Oularbi | Two physical layer metrics for vertical handover towards an ieee 802.11n network[END_REF]. Used scenario for the evaluation of the algorithm performance.

Fig. 7 .

 7 Fig. 7. NMSE on the estimation of the channel occupancy rate.

Fig. 8 .

 8 Fig. 8. NMSE on the estimation of the collision rate.

  3 + 15.5N 2 + (ν + 7.5)N flops, where ν is used as a common flop count for the square root operation. STEP 2: Calculation of Log-Likelihood Functions: In this step, we calculate the Log-Likelihood functions using the observed samples at time k. Under hypothesis H m , we estimate of the noise variance by


Mohamed Boukens

Vincent Lebastard

Godfried Jansen Van Vuuren

Frédéric Boyer
email: frederic.boyer@imt-atlantique.fr

Underwater communication with artificial electric sense

come   L'archive ouverte pluridisciplinaire

Introduction

Due to some intrinsic physical limitations, robotics underwater communication in confined spaces and turbid water still remains a challenging issue [START_REF] Lanzagorta | Underwater communications[END_REF]; [START_REF] Gussen | A survey of underwater wireless communication technologies[END_REF]). To address it, a promising perspective consists in taking inspiration from the several hundred of fresh water fish species that have evolved an original sense, named active electric sense. Discovered by Lisman and Machin in the 50s [START_REF] Lissmann | The mechanism of object location in gymnarchus niloticus and similar fish[END_REF]), electric sense allows these fish to navigate, detect preys and predators, and communicate together, in the turbid waters, saturated of obstacles, of the African and south-American rain forests (von der Emde and Schwarz (2002); [START_REF] Pereira | The active electrosensory range of gymnotus omarorum[END_REF][START_REF] Gebhardt | Electrocommununication in social groups of weakly electric fish: a comparison of mormyrus rume and marcusenius altisambesi (mormyridae, teleostei)[END_REF]). Suited to underwater navigation in confined space and turbid waters, this artificial electric sense, has been applied to several issues in underwater robotics ranging from reactive navigation [START_REF] Boyer | Underwater reflex navigation in confined environment based on electric sense[END_REF][START_REF] Boyer | Underwater navigation based on passive electric sense: New perspectives for underwater docking[END_REF]), object localization [START_REF] Silverman | Location and orientation estimation with an electrosense robot[END_REF]; [START_REF] Lebastard | Underwater robot navigation around a sphere using electrolocation sense and kalman filter[END_REF]) and recognition [START_REF] Bai | Sensing capacitance of underwater objects in bio-inspired electrosense[END_REF]; [START_REF] Lanneau | Model based estimation of ellipsoidal object using artificial electric sense[END_REF]), to haptic feedback remote control [START_REF] Fang | Human-inthe-loop active electrosense[END_REF]; [START_REF] Boyer | Underwater pre-touch based on artificial electric sense[END_REF]).

Objectives and challenges

In this paper, we will show how artificial electric sense can be used for communication in a swarm of small underwater robots. This new functionality of artificial electric sense is implemented and tested on an heterogeneous swarm named subCULTon [START_REF] Thenius | subcultron -cultural development as a tool in underwater robotics[END_REF]). This swarm, which is designed to monitor the turbid waters of the Venice laguna, is composed of three types of robots named aPads, aFish and aMussels [START_REF] Lončar | A heterogeneous robotic swarm for long-term monitoring of marine environments[END_REF]). The aPads are surface platforms that integrate the underwater data collected by the aFish and aMussels. The aMussels (see figure 1(a)) are essentially static robots that monitor their closed surrounding on the sea bottom thanks to several sensors (temperature, turbidity, oxygen...), while aFish are small mobile AUVs (See figure 1(b)) able to navigate encumbered spaces while serving as the vector of information for the swarm. As a proof of concept, we here address the following scenario. An aFish is used as a messenger that propagates information through 2 aMussels. To achieve this goal, the aFish needs to be endowed with several behaviors (taxis) as: "exploring an unknown environment while avoiding obstacles", "detecting an aMussel and aggregate with it", "retrieve the message of the aMussel, disaggregate with the aMussel", and repeat the same strategy until to find another aMussel to which the message is delivered. This scenario raises the following issues. I1: Organize the electric activity of our robots in group in order to preserve information for communication. I2: Ensure aFish to navigate while avoiding obstacles (including other aFish or inactive aMussels) and to aggregate with active aMussels. I3: All these functionalities have to work independently of water conductivity.

Methods

To use electric sense for communication in a swarm of robots (I1), we take inspiration from the original fish which can be roughly classified in two types depending whether they emit an harmonic electric field with a controlled frequency or a train of pulses. The first are named wave-fish [START_REF] Pereira | The active electrosensory range of gymnotus omarorum[END_REF]), the second, pulse-fish (von der Emde and Schwarz ( 2002)). Remarkably, these two types of fish have evolved some specific emission-reception strategies allowing them to avoid jamming between their fields, and so to preserve the informational content for communication [START_REF] Bullock | The jamming avoidance response of highfrequency electric fish, part i & ii[END_REF]; Schumacher and von der Emde (2012)).

In the case of wave fish, they slightly change their emission frequency between them according to some hierarchical position in the group [START_REF] Bullock | The jamming avoidance response of highfrequency electric fish, part i & ii[END_REF]). In the case of pulse fish, they desynchronize their electric activity in order to emit their pulse one after the other in a fixed ordered manner (Schumacher and von der Emde ( 2012)). In this paper, we will see how one can mix these two strategies to organize the electric activity of the robots of the sub-CULtron swarm. In more details, the fields are harmonic but emitted over some time windows which are opened and closed according to a desynchronization algorithm inspired from those proposed to explain the synchronization of blinking in fireflies [START_REF] Tyrrell | Synchronization inspired from nature for wireless meshed networks[END_REF]). While the aPads are not considered in the article, the desynchronization algorithm is implemented on aMussels and aFish in order to manage their electric activity in interaction with other robots (see figure 2(left)). In the case of aFish, this algorithm also manage the electric activity of a variable structure controller based on fuzzy logic (see figure 2 (right)), which allows them to seek for aMussel as well as to aggregate and communicate with them (I2). To achieve these several capabilities together, we need to hybridize active ( P ) and passive (P ) electric sense, the first being useful for exploration and obstacle avoidance, the second for aggregation (A) and communication. Moreover, the informational content of an electric field is separated into its amplitude and frequency, that both need to be measured independently with a new hardware. Finally, to address I3, the new sensor hardware which uses a frequency-shift keying (FSK) protocol for decoding messages [START_REF] Kennedy | Electronic communication systems[END_REF]), has been evolved in order to ensure the expected specifications of the swarm in fresh and salt waters.

Results

Experimental tests with both aMussels and aFish were carried out in a cubic tank of 2m width, full of salt water with conductivity γ ∼ = 3.5 S/m respectively. We report in figure 3 one result that illustrates obstacle avoidance of one aFish with two passive aMussels (circles), and two walls. The desynchronization algorithm and the fuzzy variable structure controller of figure 2 are used with parameters fixed once for all by trial and error in a preliminary calibration phase.

Figure 1

 1 Figure 1: aMussels (a) and aFish (b) designed by Scuola Superiore Sant'Anna (SSSA).

Figure 2 :

 2 Figure2: Graph of events of the desynchronisation algorithm of aMussels and aFish (left), and of the variable structure controller of aFish navigation (right). C 0,1,2,3,4 defines 5 reactive controllers for communication (C 3,4 ), obstacle avoidance (C 1,2 ), aggregation (C 3,4 ). Transitions between continuous controllers are governed by the time evolution of Boolean variables depending on the electric measurements: D means that an exogenous field is detected, P means "passive", and A "aggregated".

Figure 3 :

 3 Figure 3: Paths of the aFish navigating with the controller of figure 2 in obstacle avoidance behavior C 1 (blue) and C 2 (green).

Acknowledgements

This research was funded by European Union Horizon 2020 research and innovation program under grant agreement No 640967: EU-FET proactive project subCUL-Tron (SUBmarine Cultures perform Long-Term Robotic Exploration of unconventional environmental Niches) https://cordis.europa.eu/project/id/640967/fr.