Olivier Bodini

Guillaume Moroz

AND Hanane Tafat-Bouzid

INFINITE BOLTZMANN SAMPLERS AND APPLICATIONS TO BRANCHING PROCESSES

 to allow for infinite size objects; in particular, this extension now fully includes Galton-Watson processes. We then illustrate our idea with two examples, one of which is the generation of prefixes of infinite Cayley trees.

INTRODUCTION

Boltzmann sampling, introduced by Duchon, Flajolet, Louchard and Schaeffer [START_REF] Duchon | Boltzmann samplers for the random generation of combinatorial structures[END_REF] in 2001, is an automatic random generation method: it can directly derive random samplers from any combinatorial description, without requiring adhoc bijections or modifications; and it does so, without precomputations, by evaluating the generating function which enumerates the combinatorial class. The efficiency of this method (it can sample from most classes in time linear with respect to the size of the output) coupled with its genericity have made it fairly popular: since it's inception it has seen many theoretical developments [START_REF] Bodini | Multi-dimensional Boltzmann Sampling of Languages[END_REF][START_REF] Bodini | Boltzmann samplers for first order combinatorial differential equations[END_REF][START_REF] Flajolet | Boltzmann Sampling of Unlabelled Structures[END_REF][START_REF] Bodini | Boltzmann samplers for colored combinatorial objects[END_REF], and many practical applications [START_REF] Canou | Fast and sound random generation for automated testing and benchmarking in objective caml[END_REF][START_REF] Bodini | Random sampling of plane partitions[END_REF][START_REF] Fusy | Uniform random sampling of planar graphs in linear time[END_REF].

The concept developed in the original paper nevertheless presents an important restriction: classes must have a combinatorial generating function which is analytic 1 in 0, and the size distribution of the generated objects must remain in N. In other words, the probability of drawing an object of infinite size if always zero. For instance, while binary planar trees constructed by a Boltzmann sampler can be considered in all respects as Galton-Watson processes [1, §1], the infinite-size limitation restricts us to extinction probabilities that are larger than 1/2-and this limitation seems trite.

In this note, we extend the definition of Boltzmann samplers so as to bypass this restriction. Our approach is quite unique in analytic combinatorics (see [START_REF] Flajolet | Analytic Combinatorics[END_REF] for an overview of the topic) as, when considering the equation derived from the combinatorial specification, it no longer restricts itself to the unique combinatorial generating function which is analytic in 0, but instead considers other solutions.

Because of the succinctness of this note, we assume our reader is familiar with the Boltzmann method, as well as with analytic combinatorics.

GENERALIZING THE BOLTZMANN MODEL TO INFINITE PROCESSES

In this section, we give an extended definition of the Boltzmann distribution, so that it is now defined on N ∪ {∞}. Intuitively, we downscale the existing, traditional distribution to then insert an additional probability, of the object being of infinite size.

We first introduce two technical, commonplace definitions.

Definition. Let C be a combinatorial class and C(x) its associated generating function. We denote by E C (z, C(z)) the functional equation derived from the recursive 2 specification of the combinatorial class C and we denote by V C the 1-manifold associated with the functional equation E C , and defined by

V C := {(x, y) | E C (x, y) = 0} .
1 Recent work on random samplers for multiplicative classes [START_REF] Bodini | Dirichlet Random Samplers for Combinatorial Structures[END_REF], which are enumerated by Dirichlet generating functions, has already been confronted with a situation where this is no longer the case. 2 We only consider infinite size objects resulting from branching processes; thus all the combinatorial specifications we consider are recursive. Definition. Let C be a combinatorial class and V C be the 1-manifold associated to its functional equation. A point (x, y) ∈ V C is called Boltzmann-valid if and only if:

• x ∈ R > ; • y ∈ R > ;
• y C(x). We denote by T C the set of Boltzmann-valid points.

We are now equipped to define the main topic of this paper.

Definition. The infinite-Boltzmann distribution associated with (x, y) ∈ T C , for the random variable N ∈ N ∪ {∞} is defined as follows,

P[N = n] = c n x n y and P[N = ∞] = 1 - C(x) y with C(x) = γ∈C x |γ| = ∞ n=0 c n x n .
Notice that C(z) (the generating function of the combinatorial class) is the unique solution of E U (z, C(z)) which is analytic in 0 and which has non-negative coefficients; furthermore for (x, y) ∈ V C such that y = C(z), we return to the classical Boltzmann distribution, under which P[N = ∞] = 0.

INFINITE-BOLTZMANN SAMPLERS

This section introduces the concrete rules needed to construct infinite-Boltzmann samplers, and is in divided in two parts: one for unlabeled classes and the other for labeled classes. As usual, much of this will feel redundant to those familiar with the initial paper [START_REF] Duchon | Boltzmann samplers for the random generation of combinatorial structures[END_REF]; to keep this section brief we will use the abbreviated notations used therein, for instance,

Ber(p) ⇒ A | B ≡ { if Ber(p) = 1 then A else B } Geo(p) ⇒ A ≡ { k = Geo(p)
; return a k-tuple of independent calls to A} and this second construction is generalized to Poisson and log-series distributions.

3.1. Infinite-Boltzmann samplers for unlabeled classes. Let C be an unlabeled combinatorial class, an infinite-Boltzmann sampler, denoted by Γ (x,y) , of parameters (x, y) ∈ T C is a random algorithm which draws an objects γ ∈ C following the distribution P[γ] = x |γ| /y, where |γ| is the size of the object γ. This distribution is the infinite-Boltzmann distribution which we defined in the previous section. We now wish, as in the original paper, to constructively describe infinite-Boltzmann samplers. The first bricks are samplers for the neutral class and the atomic class (i.e. classes with only one element of size respectively 0 and 1). They just return the unique element in their class. Disjoint Union. Let Γ (x,y A ) A (resp. Γ (x,y B ) B) be an infinite-Boltzmann sampler for unlabeled class A (resp. B), then the following rule gives an infinite-Boltzmann sampler for the unlabeled class

C = A + B, Γ (x,y A +y B ) C := Ber y A y A + y B ⇒ Γ (x,y A ) A | Γ (x,y B ) B.
Cartesian Product. Let Γ (x,y A ) A (resp. Γ (x,y B ) B) be an infinite-Boltzmann sampler for unlabeled class A (resp. B), then the following rule gives an infinite-Boltzmann sampler for the unlabeled class C = A × B,

Γ (x,y A •y B ) C := (Γ (x,y A ) A, Γ (x,y B ) B).
Sequence. The sequence operator SEQ can be recursively defined from the disjoint union and the Cartesian product-C = SEQ (A) ≡ C = 1 + AC-we can therefore deduce the correct sampler from the two previous rules,

Γ (x,1/(1-y A )) C := Geo(y A ) ⇒ Γ (x,y A ) A.
Similarly, we can extend unlabeled Boltzmann samplers given in Flajolet et al. [START_REF] Flajolet | Boltzmann sampling of unlabelled structures[END_REF], such as the cycle and the multiset, by similarly rewriting their rules.

3.2. Infinite-Boltzmann samplers for labeled classes. Consider now labeled combinatorial structures C in which a labeled object of size n is an object composed of n distinct (labeled) atoms. We can adapt the notion of Boltzmannvalidity by considering the point (x, y) verifying the functional equation E C (z, C) and the three properties:

x ∈ R > , y ∈ R > , y Ĉ(x)
where Ĉ(z) is the exponential generating function of C. Let C be a labeled combinatorial class, the generalized Boltzmann distribution with parameters (x, y) ∈ T C for the random variable N with values in N ∪ {∞} is defined as follows:

P[N = n] = c n x n n!y and P[N = ∞] = 1 - Ĉ(x) y with Ĉ(x) = γ∈C x |γ| |γ|! = ∞ n=0 c n x n n! .
As for unlabeled classes, samplers for the neutral class and the atomic class (i.e. classes just return the unique element in their class. The rules for the disjoint union, the Cartesian product and the sequence are the same as in the labeled case. Now however, the set and cycle constructions are sufficiently simple that we can give them here. Set. Let Γ (x,y A ) A be an infinite-Boltzmann sampler for labeled class A, if C = SET (A), then

Γ (x,exp (y A )) C := Poi(y A ) ⇒ Γ (x,y A ) A.
Cycle. Let Γ (x,y A ) A be an infinite-Boltzmann sampler for labeled class A, if C = CYC (A), then

Γ (x,ln(1/(1-y A ))) C := Loga(y A ) ⇒ Γ (x,y A ) A.

EXAMPLES

We propose two applications of our extension. The first one consists in showing how we can fully include infinite process in the Boltzmann model. The second one shows a simulation of the prefix of a random infinite Cayley tree.

Galton-Watson processes.

A direct application of the infinite-Boltzmann model is the full integration of branching processes of Galton-Watson [START_REF] Athreya | Branching processes[END_REF] in it. Here we will apply the principle in the case of the simplest branching processes: that is, one where each vertex has a probability p of extinction (leaf) and a probability 1 -p to have two children. When p < 1/2, one has a nonzero probability of having an infinite process which could not be considered in the classical Boltzmann model. We describe later in this section how thanks to the sampling under infinite-Boltzmann model, it is possible to reproduce the Galton-Walton process even in the infinite case.

This branching process immediately returns to the symbolic specification of binary trees which is : T = Z + ZT 2 , The set of valid points is T T = {(x, y), x ≤ 1/2, x + xy 2 = y}.

So, for every (x, y) ∈ T T , we have the sampler Γ (x,y) T := Ber(x/y) → ( |[ , Γ (x,y) T , Γ (x,y) T ]) Now, the couples (x, y) ∈ T T can be partitioned in two classes, couples of the shape

C 1 = {( 1- √ 1-4 x 2 2x
), ∀0 ≤ x ≤ 1/2} and whose of the shape

C 2 = {( 1+ √ 1-4 x 2 2x
), ∀0 ≤ x < 1/2}. The class C 1 corresponds to the branching processes with p ≥ 1/2 and could already be reached with classical Boltzmann sampling. The class C 2 henceforth allows to reach the branching processes with p < 1/2. The figure 1 shows the probability that the process does not finish in function to the stop probability p.

Of course, the main interest of this example is to highlight how infinite-Boltzmann sampler can now include the infinite branching processes.

In order to complete our considerations, the next paragraph is dedicated to prove that in the case of simple variety of trees (i.e. when the functional equation is of the shape t = zφ(t, z) with φ a bivariate polynomial) for every α in ]0, 1[, there exists a unique (x, y) ∈ V C such that α = x y . In other words, we want to prove that our new Boltzmann model contains Galton-Watson processes for every probability of death.

First we recall a corollary of the Descartes rule of sign.

Lemma 1. Let p = a 0 + • • • + a d x d be a univariate polynomial such that for all i ≥ 1, a i ≤ 0 and p is a non constant polynomial. Then, the equation p(x) = 0 has exactly one positive solution if a 0 > 0, and no positive solution otherwise.

Proof. The Descartes lemma ([13, page 121]) states that the number of positive solutions is bounded by the number of sign alternation in the coefficient vector. Moreover, the number of positive solutions has the same parity as the number of sign alternation. If a 0 > 0, the number of sign alternation is 1, else, it is 0, hence the result. On the left, the curve of the valid points for the class of binary trees. On the right, the probability that the process does not finish according to the death probability.

Lemma 2. Let p be a bivariate polynomial of the form p(x, y) = y -xq(x, y), where q is a polynomial non-constant, with non-negative coefficients, and such that q(0, 0) = 1. Let V be the set of real positive points (x, y) ∈ (R * + ) 2 solution of p(x, y) = 0. Then the map:

f : V → ]0, 1[ (x, y) → x y is a bijection.
Proof. Let d be the total degree of q(x, y). First, we introduce the new polynomial Q such that ( y x ) d Q(x, x y ) = q(x, y). If q ij denotes the coefficient of x i y j in q(x, y), then Q is defined explicitly as:

Q(x, α) := 0≤k≤d d-k≤l≤d q k+l-d,d-l x k α l = q 00 α d + 1≤k≤d d-k≤l≤d q k+l-d,d-l x k α l r(α,x)
where r(x, α) is a polynomial whose all monomials have a degree greater or equal to 1 in x. Thus, for all x > 0, y > 0, the equation y -xq(x, y) = 0 is equivalent to:

( x y ) d-1 -Q(x, x y ) = 0
In particular, if we denote x y by α, then, x is the solution of the polynomial equation:

s α (x) := α d-1 -q 00 α d -r(α, x) = 0
By hypothesis, x > 0 and y > 0, thus α > 0. Also, q(0, 0) = 1 and q is non-constant, thus q 00 = 1 and s α is non-constant. According to Lemma 1, the polynomial equation s α (x) = 0 has a positive solution if and only if

α d-1 -α d > 0, which implies that α ∈]0, 1[. This ensures that f (V ) ⊂]0, 1[. Moreover, if α ∈]0, 1[, Lemma 1 states
that the positive solution of s α (x) is unique. This ensures that f is bijective.

Simulation of the prefix of infinite Cayley trees.

The second application we present is the simulation of the prefix of a random infinite Cayley tree T , which are a labelled trees such that each vertex has a finite number of children. Therefore the specification of Cayley trees is T = Z × SET(T ).

By applying the rules given previously, the infinite-Boltzmann sampler is:

Γ (x,x•e y ) T = (Z, Poi(y) =⇒ Γ (x,y) T ).
We are interested in generating the prefix of a height H of an infinite Cayley tree, which is the set of vertices of the tree from the root to the height H. To obtain this prefix, we construct the tree T in depth, which allows us to control the development of its branches.

The generator of a prefix at height less than or equal to H of a Cayley tree of infinite size is given by the following algorithm: Remark. Note that this algorithm is iterative-as opposed to recursive like all Boltzmann samplers-because as we perhaps wish to increase the size of the height during the course of the algorithm, it is a more natural way to write the algorithm; in this form, it also bears a striking resemblance with the definition of branching processes.

That said however, it would be equivalent to write this as a regular recursive Boltzmann sampler, with an additional parameter H recursively tracking the height and only making recursive calls if it is not past the desired height.

COMPLEXITY ANALYSIS

It is natural to ask whether our extension can be applied efficiently in practice. Specifically, two questions may come to mind. First, what is the complexity for generating the prefix of a possibly infinite tree (which, in fact, can also be considered as the "beginning of a branching process)? In this case, the answer is straightforward and is an immediate consequence of the proof given in the seminal paper [START_REF] Duchon | Boltzmann samplers for the random generation of combinatorial structures[END_REF].

Proposition 5.1. At each step of the computation, an infinite-Boltzmann sampler's complexity (measured in the number of real-arithmetic operations) is linearly proportional to the number of atoms which have been outputted.

The second question we can ask ourselves is whether the ability to generate infinite trees can be diverted to advantageously generate large (but finite) approximate-size trees.

Currently in the Boltzmann model, the best way to generate approximate-size trees is to choose a control parameter near the dominant singularity, and to generate and discard trees until one is obtained which is within the desired size interval. It well-known that although of a constant order, the number of discarded trees is large, with many small trees sampled before a satisfyingly large one is produced. If we target infinite trees however, we can expect to discard fewer trees. However this is counterbalanced by the fact that the trees with are then discarded (with anticipated rejection, which consists in interrupting the construction of the tree as soon as it becomes larger than the target interval, see [4, §1.4] for a practical application of this concept) are much larger on average. This is summarized in the following proposition essentially proved in [START_REF] Duchon | Boltzmann samplers for the random generation of combinatorial structures[END_REF].

Proposition 5.2. The probability generating function F (u) for the cost of an interrupted infinite-Boltzmann sampler targeting objects of size within

[n 1 , n 2 ] F (u) = 1 1 - n<n1 anx n u n y + u n2 n<n2 anx n y n≤n1≤n2 a n x n u n y , where F (u) := k P[Cost = k] u k .
The mean of the cost is done by E(Cost) = ∂ ∂u F (u)| u=1 , and A full analysis can be done to prove that the average cost is linear when then combinatorial class is given by a recursive specification which is irreducible and aperiodic. Remark. The alternate idea of building large trees by truncating, in some way, infinite trees seems like it would be much too complicated with our current tools-indeed the problem of how to truncate the tree so that overall the distribution is still uniform is non-trivial.

CONCLUSION

While the Boltzmann sampling method usually involves evaluating generating series, in this note, we use instead the functional equation related to the specification. This slight extension (which is derived from the symbolic method, and hence makes an underlying use of generating functions) allows us to efficiently simulate unbounded branching processes in a new way, while remaining in the Boltzmann framework.

Whether this method has any practical advantages over traditional ways of simulating branchings processes remains to be seen. However, our main interest resides in the fact that this new approach seems very promising with regards to the optimization of Boltzmann samplers. Indeed, in work in progress, we pursue a further extension of this idea which allows us to circumvent the main problem of Boltzmann sampling which is the calculation of the oracle (in contrast with previous approaches that sought to efficiently calculate the oracle).

Figure 1 .

 1 Figure1. On the left, the curve of the valid points for the class of binary trees. On the right, the probability that the process does not finish according to the death probability.

Algorithme 1 : 2 For 3 h

 123 Γ (x,x•e y ) T Input : parameters x, y, H Output : prefix of height ≤ H of infinite Cayley tree 1 while (h ≤ H) do any vertex v of height h do: k = Poi(y), add k sons to v = h + 1 4 return tree Simulation of the algorithm 1 for different values of the parameters (x, y, H) gives the following prefix of infinite Cayley trees : (0.5, 0.3, 4): Standard Boltzmann sampler (0.24, 0.34, 4) (0.16, 0.20, 4) (0.35, 0.80, 4).

  For instance, for unary-binary trees, the specification is U = Z + ZU + ZU 2 , the ordinary generating function is U (z) = z + zU (z) + zU (z) 2 and E U (z, U (z)) = z + zU (z) + zU (z) 2 -U (z) which can be rewritten as a bivariate polynomial E U (x, y) = x + xy + xy 2 -y. Thus, V U := {(x, y) | x + xy + xy 2 -y = 0}.

1

Example.

ACKNOWLEDGEMENTS

We gratefully acknowledge Jérémie Lumbroso's help in writing and formatting this note, as well as his diligence in checking over our results.

This work was supported by the French ANR MAGNUM.


Djamel Benferhat

Frédéric Guidec

Patrice Quinton

Disruption-Tolerant Wireless Sensor Networking for Biomedical Monitoring in Outdoor Conditions

Keywords: J.3 [Computer Applications]: Life and Medical Sciences-Health; C.2.1 [Computer Systems Organization]: Computer-Communication Networks-Wireless Communication wireless networking, delay/disruption-tolerant networking, sensor networking, biomedical monitoring

Off-the-shelf wireless sensing devices open up interesting perspectives for biomedical monitoring. Yet because of their limited processing and transmission capacities most applications considered to date imply either indoor real-time data streaming, or ambulatory data recording. In this paper we investigate the possibility of using disruption-tolerant wireless sensors to monitor the biomedical parameters of athletes during outdoor sports events. We focus on a scenario we believe to be a most challenging one: the ECG monitoring of runners during a marathon race, using off-the shelf sensing devices and a limited number of base stations deployed along the marathon route. Preliminary experiments conducted during an intra-campus sports event show that such a scenario is indeed viable, although special attention must be paid to supporting episodic, low-rate transmissions between sensors carried by runners and road-side base stations.

INTRODUCTION

The concept of Wireless Biomedical Sensor Network (WBSN) opens up new opportunities for biomedical monitoring, such as the long-term, continuous monitoring of patients in a clinical environment or at home [START_REF] Alemdar | Wireless Sensor Networks for Healthcare: a Survey[END_REF][START_REF] Konstantas | Continuous Monitoring of Vital Constants for Mobile Users: the MobiHealth Approach[END_REF].

In a typical deployment scenario, one or several batterypowered wireless sensors are attached to a patient, and a wireless base station is installed in this patient's surroundings. This base station can either store the data received from the sensors, or it can forward these data directly to a remote site, such as a physician's desktop computer or a hospital's monitoring center. In any case, since the sensors are wireless the patient can move freely around the base station, while an endless stream of data flows from the sensors he/she is carrying to the base station. This freedom of movement is however limited by the short transmission range of the wireless sensors. Indeed, most sensors include low-power radio transceivers (such as IEEE 802.15.4/ZigBee transceivers or, less frequently, IEEE 802.15.1/Bluetooth transceivers), with which actual transmission ranges are usually between a few meters (indoor) and up to a hundred meters (outdoor).

In traditional scenarios involving wireless biomedical sensors and a base station, it is commonly assumed that the transmission link between sensor and base station is continuously available and reliable. Transmission protocols can actually tolerate transient link disruptions without data loss, but the general assumption is that frequent, long-term disruptions should never occur while a patient's health status is being monitored. Such an assumption holds when a patient does not move much around the base station, as is the case in a hospital environment or at home. Yet there are other circumstances when the connectivity between sensor and base station can be seriously disrupted by the patient's mobility.

In this paper we investigate the possibility of using offthe-shelf wireless sensors to monitor the health of highlymobile people in outdoor conditions. Our main motivation is to confront the possibilities offered by currently available sensors with the requirements of a demanding biomedical application, in order to assess if such an application can indeed be implemented using existing devices and technologies. To achieve this goal we focus on a scenario we consider as a most challenging one: monitoring the cardiac activity of runners during a marathon race. The underlying idea is that if biomedical monitoring can be performed in such a challenging scenario, then similar solutions can also be designed and implemented for less constrained situations.

The remainder of this paper is organized as follows. The marathon scenario we consider is described in Section 2, and Section 3 provides an overview of the sensors we plan to use in this scenario. In Section 5 we report on field trials we conducted during an intra-campus sports event in order to check the feasibility of ECG monitoring of runners. This section presents the conditions for the field trials. Lessons learned on that occasion are discussed in Section 6, as well as ongoing work. In Section 7 we conclude this paper, observing that monitoring the ECG activity of athletes in out-

DESCRIPTION OF THE MARATHON SCENARIO

The scenario we consider as a test case is defined as follows: we assume the cardiac activity of athletes must be monitored using off-the-shelf sensors featuring an ECG sensing element during a marathon race. This particular scenario was selected because runners must cover a long distance during a marathon, and that distance clearly exceeds the limited radio range of the low-power IEEE 802.15.4 radio transceivers available on most current sensor platforms. Besides, since runners in a marathon all follow exactly the same route, a number of base stations can be deployed along that route (see Figure 1).

A base station (BS) is typically composed of a processing unit -for example a laptop-featuring an 802.15.4 interface, and at least one wired or wireless interface for longdistance transmissions (typically an access to the Internet). The 802.15.4 interface is used to receive data from the sensors carried by marathon runners, and the long-range interface is used to forward these data to a remote site (for example the closest medical aid station, or a physician's desktop, laptop, or smartphone). Data received from the sensors can be processed locally on the BS before being forwarded to the monitoring site, although that is not a requirement.

We conducted a series of preliminary tests in outdoor conditions in order to measure the radio range that can be observed between 802.15.4 transceivers operating at full power. We measured that this range can reach up to 50 meters in ideal conditions, but that an average value is closer to 30 meters. A BS deployed along a marathon route would thus cover about 60 meters of that route, and about 700 base stations would be required to ensure a full coverage of the 42.2 km route.

Since deploying that many base stations is hardly an option for organizational and financial reasons, our approach is based on the assumption that only a sparse coverage of the route can be ensured, using a reasonable number of base stations. A disruption-tolerant solution for data gathering must therefore be implemented, using the store-carryand-forward principle. This principle is the foundation of Disruption-Tolerant Networking (DTN): a mobile node that is temporarily disconnected from the rest of the network can store data (or messages) in a local cache, carry these data for a while, and forward them later when circumstances permit [START_REF] Fall | Messaging in Difficult Environments[END_REF]. In our scenario, the ECG sensor carried by a runner captures data continuously and stores these data locally. Whenever the runner passes by a BS, a transient radio contact occurs between the sensor and that BS. This contact is exploited by the sensor to upload data to the BS, which in turn can relay these data to the monitoring center (see Fig. 1). The distance between successive base stations and the speed of the runner determine how often "fresh" data can be sent to the monitoring center. According to cardiologists we consulted, a physician monitoring the cardiac activity of marathon runners should receive updated data for each runner at least every 5 to 10 minutes, in order to be able to detect arrhythmias and prevent incidents. Considering the pace of an average runner this implies that base stations should be placed about 1 to 2 km apart.

To the best of our knowledge, utilization of the storecarry-and-forward approach to collect biomedical data in outdoor conditions has not been investigated much so far, although disruption-tolerant solutions for non-biomedical sensorbased applications have already been proposed in the literature [START_REF] Pisztor | Opportunistic Mobile Sensor Data Collection with SCAR[END_REF][START_REF] Jain | Exploiting Mobility for Energy Efficient Data Collection in Wireless Sensor Networks[END_REF][START_REF] Nayebi | Data Gathering, and Neighbor Discovery in Delay-Tolerant Wireless Sensor Networks[END_REF].

OVERVIEW OF OFF-THE-SHELF WIRE-LESS SENSOR DEVICES

As a general rule a typical sensor node -or mote-is composed of a micro-controller or full-featured CPU, one or several transceiver modules, internal and/or external memory, a power source, and one or more sensing elements. In our project we use SHIMMER platforms as biomedical sensors and TELOS-B platforms as the radio units of our base stations (see Fig. 2).

Both kinds of platforms feature an 8 MHz TI MSP430 micro-controller with 10kB RAM, 16 kB EEPROM, 48 kB flash memory (for program code), and 1 MB external flash memory (for data logging). The radio module is based on an IEEE 802.15.4/ZigBee compliant CC2420 transceiver, which operates in the 2.4 GHz ISM band and allows data rates up to 250 kbps. Data acquisition is performed on up to 8 channels through a 12-bit AD converter. Programming and data collection can be performed either via a radio link or via a built-in USB interface.

Crossbow's TELOS-B "mote" platform includes sensing elements for light (visible and IR) and for humidity. Additional sensing elements can be connected to the platform through a USART (UART/SPI/I2C and DMA) and digital I/O bus. Power is provided either by 2 AA batteries or by the USB interface.

The SHIMMER platform is mostly dedicated to recording and transmitting physiological and kinematic data [START_REF] Burns | SHIMMER : A Wireless Sensor Platform for Noninvasive Biomedical Research[END_REF]: several kinds of expansion modules are available, including physiological sensors such as ECG (electrocardiography), EMG (electromyography) or GSR (galvanic skin response) sensors, as well as kinematic sensors for 3-axis angular rate sensing and 3-axis low field magnetic sensing.

The ECG expansion module of the SHIMMER platform provides RA-LL (Right Arm -Left Leg) and LA-LL (Left Arm -Left Leg) input leads. The RA-LA (Right Arm -Left Arm) lead can then be calculated based on the first two leads. Sampling is performed on each RA-LL and LA-LL channel by 12-bit A/D converters, and the sampling fre- The two kinds of motes used in this project. The SHIMMER sensor (left) with its ECG expansion module and electrodes will be carried by runners, and the TELOS-B mote (right) will serve as the radio transceiver of a base station quency can be adjusted between 200 Hz and 1 kHz. ECG sampling on two channels therefore produces a continuous stream of data, at a rate that can be adjusted between 4.8 kbps (for 200 Hz sampling) and 24 kbps (for 1 kHz sampling). A 2 GB micro-SD card provides storage capacity for data logging, and the platform is powered by an integrated 250 mAh Li-Ion battery. Besides the ZigBeecompliant CC2420 transceiver, the SHIMMER platform also includes a WML-C46A class 2 Bluetooth transceiver.

Like many other sensor platforms the TELOS-B and SHIM-MER platforms are driven by TinyOS, a free and opensource component-based operating system targeting wireless sensor networking [START_REF] Levis | TinyOS: an Operating System for Sensor Networks[END_REF]. TinyOS applications are built in nesC (a dialect of the C language optimized for low memory consumption) out of event-based software components, some of which present hardware abstractions and others higherlevel abstractions such as packet communication, routing, sensing, actuation and storage.

REQUIREMENTS AND CONSTRAINTS

The implementation of our disruption-tolerant transmission scenario for marathon monitoring might seem to be quite straightforward. Yet the problem is that ECG monitoring is a rather demanding application, whereas radio transmissions based on the IEEE 802.15.4 standard can only be achieved on short distances, and with low data rates. The question is therefore to determine if the requirements of ECG monitoring can be balanced with the constraints of episodic, low-rate, and short-range transmissions.

In order to answer this question it is necessary to evaluate the exact requirements of ECG monitoring, as well as the possibilities offered by SHIMMER and TELOS-B platforms for outdoor data transmission.

Requirements of ECG monitoring

ECG monitoring is usually performed with a 500 Hz sampling frequency, and the SHIMMER platform's A/D converters have a 12-bit resolution. In such conditions the bitrate of the data stream produced by the platform's 2channel ECG module is 12 kbps. If needed several options can be considered in order to reduce this figure:

• Using lower sampling frequency and resolution: a 200 Hz sampling with 8-bit samples (on each channel) would for example produce a 3.2 kbps data stream. Such parameters may of course alter the quality of the ECG data stream, but signal reconstruction techniques can be used on the receiver side in order to compensate for this low quality [START_REF] Singh | Optimal Selection of Wavelet Basis Function Applied to ECG Signal Denoising[END_REF].

• Compressing ECG data before storage and transmission: an important constraint here is to implement an algorithm that does not exceed the computation power of the SHIMMER platform's micro-controller, such as that proposed in [START_REF] Hossein | Real-Time Compressed Sensing-Based Electrocardiogram Compression on Energy Constrained Wireless Body Sensors[END_REF].

• Processing ECG data on the SHIMMER platform, and transmitting reports and alerts rather than the whole data stream: a recognition module for cardiac arrhythmia is proposed in [START_REF] Madzarov | Heartbeat Tracking Application for Mobile Devices -Arrhythmia Recognition Module[END_REF], and delineation algorithms for the automatic detection of the major ECG characteristic waves are described in [START_REF] Boichat | Wavelet-Based ECG Delineation on a Wearable Embedded Sensor Platform[END_REF]. The algorithms proposed in both papers have a low computational complexity, so they can run on resource-constrained platforms such as the SHIMMER platform.

Constraints presented by sensor platforms

The SHIMMER and TELOS-B platforms we use in this project both include IEEE 802.15.4 transceivers that allow a 250 kbps transfer rate. This transfer rate is actually the signaling rate that can be achieved on the radio channel. The actual transfer rate available at application level is of course significantly lower than that signaling rate.

In order to clarify the real potential of 802.15.4-enabled sensor platforms for data transmissions in our marathon scenario, we conducted a series of preliminary field experiments:

• Power consumption: we observed that a SHIMMER sensor with an ECG expansion module car run for almost 10 hours on its built-in battery (while storing ECG data on the micro-SD card and sending these data continuously on the wireless channel).

• Radio range: as mentioned before the radio range between SHIMMER and TELOS-B platforms is around 30 meters (on average) for outdoor transmissions, although transmissions on up to 50 meters can sometimes be observed.

• Transmission bitrate: the achievable transfer rate between sensor and BS cannot exceed 50 kbps.

The transmission bitrate mentioned above is surprisingly low compared to the standard's 250 kbps signaling rate. Yet this is the maximal bitrate we observed, and this result is actually consistent with other results mentioned in the literature [START_REF] Farshchi | A TinyOS-Based Wireless Neural Sensing, Archiving, and Hosting System[END_REF] and in the TinyOS forum. Indeed it appears that the architecture of the SHIMMER and TELOS-B platforms both present a transmission bottleneck, which lies in the connection between the micro-controller and radio transceiver.

Although the CC2420 radio transceiver can send and receive frames at 250 kbps on the radio channel, these frames can only be transferred to or from the micro-controller at a very limited rate. This is an important disadvantage for our marathon scenario, which requires that a single base station be able to receive data streams from several ECG sensors in the same timespan.

Trials conditions

The preliminary experiments mentioned in Section 4 gave us a crude idea of what can be expected from sensors and base stations in a marathon scenario, but we decided to get a proof-of-concept in more realistic conditions. Field trials were conducted during an intra-campus sports event that occurred in September 2011 on the Ker Lann campus (France). A 3.9 km running race was organized during that event, and three volunteers (two students and a professor) were equipped with ECG-enabled SHIMMER sensors on that occasion (see Fig. 3). Four base stations (BS1 to BS4) were deployed along the running route (Fig. 4). This route was a loop, so the runners passed two times near each base station. BS4 had to be moved between the first and second round, since the second round was shorter than the first round. The distance between successive base stations was about 500 meters.

During these field trials at Ker Lann campus each base station was composed of a netbook connected to a TELOS-B mote (see Fig. 5). The netbooks were not connected to a remote monitoring center on that occasion, since our motivation was primarily to observe how ECG data could be collected from the SHIMMER sensors as the runners passed close to a base station. Each base station therefore simply recorded the data obtained from passing sensors in flash memory, and the data recorded by all four base stations were reassembled and analyzed after the race was over.

Protocol for data acquisition and transmission

We developed specific code in nesC in order to ensure the acquisition, storage, and transmission of data between SHIMMER sensors and TELOS-B platforms. The main features of this code are detailed below.

Data acquisition on a SHIMMER sensor.

The acquisition of ECG data on each SHIMMER sensor is performed on the two 12-bit channels (RA-LL and LA-LL leads), with 500 Hz sampling frequency. The 12 kbps data stream hence produced is compressed on-the-fly, using a simple differential compression algorithm that lowers the bitrate to about 6 kbps. The data stream is then packetized in small bundles, each bundle containing a 34-byte header (including the sensor's identifier and a local timestamp), and 80 bytes of compressed ECG data. A bundle can thus fit in a single 802.15.4 data frame (whose size cannot exceed 128 bytes). After its creation a bundle is stored as a file in the SHIMMER sensor's micro-SD card, from which it can be retrieved to be transmitted during radio contacts with a base station.

Data transmission between SHIMMER sensor and base station.

Since each base station (using a TELOS-B mote as an 802.15.4 transceiver) can have to interact with several passing SHIMMER sensors at the same time, some form of medium access control is required in order to avoid frame collisions on the radio channel. We therefore designed and implemented a simple coordination protocol, whereby a base station can allocate time slots to each sensor in range for data transmissions. This protocol is strongly inspired from the GTS (Guaranteed Time Slot) allocation method defined in the ZigBee specification [7]. Each base station periodically broadcasts a beacon frame, which allows neighbor SHIM-MER sensors to detect its presence. The interval between two successive beacons is split in two parts: a Contention Access Period (CAP), and a Contention-Free Period (CFP). During the CAP sensors can notify the base station of their presence and request the allocation of a time slot for data transmission. During the CFP each sensor can use its allocated time slot to upload bundles of data to the base station, with no interference from other sensors. Since all sensors do not necessarily have the same amount of data (that is, the same number of data bundles) to upload to the base station, the number of available data bundles is included in the request a sensor sends to the base station during the CAP. The base station can thus adjust the duration of the CAP time slots assigned to neighbor sensors proportionally to the amount of data they need to upload. Information about the allocation, ordering and duration of time slots is notified to all neighbor sensors at once, using a single frame that is broadcast by the base station at the end of the CAP and just before the CFP.

Each bundle of ECG data can fit in a single data frame, so no fragmentation is required. MAC-level data frame acknowledgement is enabled during the CFP: after sending a data bundle a sensor receives an ACK frame, that confirms that the data bundle has been received and accepted by the base station. If the ACK frame is not received the same data frame is sent again after a timeout. Upon receiving an ACK for a data frame the corresponding bundle remains in the micro-SD filesystem, but it is tagged as "transmitted" so the sensor will not try to upload this bundle again (to the same base station or to the next one).

Several strategies can be devised in order to determine which data bundles should be sent first when a SHIMMER sensor establishes a connection with a nearby base station. An option is for example to preserve the chronological ordering of data bundles, uploading the oldest bundles first. For the field trials we decided to favor the transmission of "fresh" ECG data first, and to fill the gaps by uploading older bundles whenever possible. The transmission algorithm running on the sensors was therefore implemented in such a way that "real-time" bundles (i.e. those produced during a radio contact between sensor and base station) were uploaded to the base station first, and the time remaining during each GTS time slot was used to upload "old" bundles (i.e. bundles that had been stored on the sensor's micro-SD card, and that had not been uploaded to a base station yet). A monitoring system receiving ECG data from a marathon runner could thus display the current heart activity of the runner, and optionally allow a user to rewind the ECG stream in order to display past events. Besides serving as a coordinator for wireless medium access, the base station receives ECG data bundles from passing sensors. As mentioned before, each bundle includes an identifier of the source sensor and a timestamp that is associated with the data when they are packetized. The SHIMMER platform does not include any real-time clock, so timestamping is performed based on a local timer that ticks every 100 ms. When a data bundle is sent by a sensor to a nearby base station, the duration since this bundle was recorded is calculated, and this duration is inserted in the bundle's header in place of the record time. When the data frame is received by the base station the actual time of the bundle's production is calculated based on the current time (according to the base station's system clock), on the duration specified in the bundle's header, and on an estimation of the time required to transmit the data frame between sensor and base station (this transmission can be estimated quite accurately since data frames are transmitted during a CFP period, when no backoff mechanism is used).

Every bundle of ECG data thus received by a base station contains an indication of where and when it was produced. Each base station can therefore record data bundles for deferred analysis, or transmit these bundles to a remote site with no risk of data mixup or disordering.

Results

During the field trials at Ker Lann campus the three runners covered the 3.9 kilometers in about 22 minutes, and each sensor produced about 2.5 MB of ECG data (that is, about 65.000 compressed bundles) during that time.

Figure 6 shows an excerpt of the ECG data stream that was collected from one of the sensors during the race. This data stream would probably need some noise reduction processing, but as such it is exploitable by a cardiologist.

During the race our prime motivation was to observe if the data bundles produced continuously on each sensor could actually be transmitted when the sensor established radio contact with one or another base station. Figure 7 shows the timeline of transmissions between the three sensors (S1 to S3) and the four base stations (BS-1 to BS-4). More precisely it shows the duration of the radio contacts as each sensor passed close to a base station (dotted lines), and the amount of data that were uploaded to the base station during that contact. For example, a radio contact was established between S1 and BS-1 between 09h15m55s and 09h16m22s. It can be observed that during this 27-second contact only a small amount of data was uploaded from S1 to BS-1, and none of the data acquired before the radio contact was uploaded to BS-1. About two minutes later S1 established a radio contact with BS-2, and during this contact 82% of the data produced since the former contact was uploaded to BS-2. The next contact was established between S1 and BS-3, and this time S1 managed to upload to BS-3 all the data it had produced since its contact with BS-2, plus 17% of the data that it had failed to transmit to BS-2.

By observing carefully the timing of the radio contacts between the sensors and base stations, it can be observed that the data uploading process was more effective when a base station only had to interact with one or two sensors simultaneously. In contrast, when a sensor had to deal with the three sensors (as happened at the beginning of the race when all three sensors passed close to BS-1 at the same time) only a fraction of the data could be uploaded to the BS.

During the race the duration of radio contacts ranged between 11 seconds and 48 seconds, with an average value of 19 seconds. During these contacts the sensors managed to upload 79% of their data to the base stations. The remaining 21% of data bundles were not lost, though, since they were stored on each sensor's micro-SD card and could be collected after the race.

DISCUSSION

Lessons learned from the field trials

Globally the results of the field trials confirm that the protocol we implemented can indeed tolerate transient connectivity between sensors and base stations, and is resilient to connectivity disruptions. However they also show that in spite of this disruption-tolerant procotol not all data acquired during the race could be uploaded to the base stations.

A major outcome of these field trials is that they clearly show the limits of outdoor ECG data acquisition using shortrange, low-rate transmissions based on 802.15.4 transceivers. Although these field trials were conducted with only three sensors, and although the distance between successive base stations was rather short (about 400 meters instead of the 1 or 2 km required during a marathon race), only a fraction of the data acquired on each sensor could be collected by base stations during the race.

Of course the amount of data produced on each sensor could certainly be reduced, as explained in Section 4, by adjusting the frequency and resolution of ECG acquisition. A more efficient compression algorithm could also be implemented, provided the code of this algorithm could hold in the SHIMMER platform's 48 kB flash memory. Our current code (which handles data acquisition, compression, packetization, storage, and transmissions) has a 45 kB footprint. Replacing the simple differential compression algorithm it contains by a more efficient compression algorithm without exceeding the SHIMMER's capacity would be quite a challenge.

Ongoing and future work

In order to get around the constraints mentioned above, we started investigating an alternative approach whereby smartphones carried by runners can serve as relays between SHIMMER sensors and base stations. In this new config-uration the ECG data stream produced by a SHIMMER sensor is transmitted directly and continuously to a smartphone through a Bluetooth RFCOMM link. The smartphone processes this data stream (packetization + compression + storage + optional signal analysis), and the upload of data bundles from a smartphone to roadside base stations can be performed using Wi-Fi wireless links rather than 802.15.4 links. Base stations are then standard Wi-Fi access points, with broadband connectivity to the monitoring center. This approach is expected to raise the limitations we observed with 802.15.4 transmissions. Indeed, with Wi-Fi transceivers instead of 802.15.4 transceivers the range of wireless transmissions is increased by approximately one order of magnitude, and the data throughput is increased by about two orders of magnitude. Optionally, data bundles can also be transmitted from a smartphone directly to a remote monitoring center, using 3G (UMTS or CDMA2000) connections for data transmission.

One of the drawbacks of this alternative approach is of course that runners might be reluctant to carry a smartphone in an armband, in addition to the SHIMMER sensor. A SHIMMER unit with its ECG expansion module weighs about 22 grams. In contrast a smartphone usually weighs between 150 and 200 grams. Additionally, the autonomy of a smartphone might be an issue during a marathon race. Experiments conducted in our laboratory show that an Android smartphone maintaining one Bluetooth connection with a SHIMMER sensor and one Wi-Fi connection with a nearby access point can deplete its battery in a couple of hours. The situation is even worse if a UMTS connection is used instead of Wi-Fi to upload data bundles to a remote site. Further experiments are planned in order to check if a smartphone can run continuously (with continuous Bluetooth transmissions and sporadic Wi-Fi or 3G transmissions) during the duration of a marathon race.

CONCLUSION

Off-the-shelf wireless sensing devices such as the SHIM-MER platform open a wide range of perspectives for health monitoring. Yet because of the limited computation and transmission capacities of such platforms most applications considered to date imply either indoor real-time data streaming, or ambulatory data recording. With disruption-tolerant networking another approach can be considered, whereby data are captured and stored continuously on the sensor platform, and transient connectivity with one or several base stations is used opportunistically to upload data to a remote monitoring center.

In order to illustrate this approach we investigate a challenging scenario: the ECG monitoring of runners during a marathon race. Preliminary field trials have been conducted during a campus sports event, using SHIMMER platforms for data acquisition and IEEE 802.15.4 transmissions to upload ECG data to roadside base stations. These trials confirm that capturing and transmitting ECG data during a running race is indeed feasible, but that this application is hampered by the low computation power, short transmission range, and low transmission bitrate offered by SHIMMER sensors. Work is now in progress in order to use Android smartphones as relays between ECG sensors and roadside base stations. With this approach each runner must carry a smartphone, additionally to the ECG sensor. ECG data are received and processed continuously by the smartphone

Figure 1 :

 1 Figure 1: Illustration of disruption-tolerant ECG monitoring of marathon runners

Figure 2 :

 2 Figure 2: The two kinds of motes used in this project. The SHIMMER sensor (left) with its ECG expansion module and electrodes will be carried by runners, and the TELOS-B mote (right) will serve as the radio transceiver of a base station

Figure 3 : 1 Figure 4 :

 314 Figure 3: One volunteer is equipped with an ECGenabled SHIMMER sensor for the running race at Ker Lann campus

Figure 5 :

 5 Figure 5: One base station (i.e. netbook + TELOS-B mote) installed on the roadside during the running race at Ker Lann campus

Figure 6 :

 6 Figure 6: Example of ECG data collected from a runner's sensor during the race

Figure 7 :

 7 Figure 7: Timeline of data transmissions during the race for the three sensors


Frédéric Guidec
email: frederic.guidec@univ-ubs.fr

Djamel Benferhat

Patrice Quinton

Biomedical Monitoring of Non-Hospitalized Subjects using Disruption-Tolerant Wireless Sensors

Keywords: biomedical monitoring, disruption-tolerant networking, Wi-Fi

come   L'archive ouverte pluridisciplinaire

Introduction

Wireless sensors open up interesting opportunities for biomedical monitoring, such as the long-term, continuous monitoring of subjects in a clinical environment or at home [START_REF] Alemdar | Wireless Sensor Networks for Healthcare: a Survey[END_REF][START_REF] Konstantas | Continuous Monitoring of Vital Constants for Mobile Users: the MobiHealth Approach[END_REF]. In a typical deployment scenario, one or several wireless sensors are attached to a subject, and a wireless base station is installed in this subject's surroundings. This base station can either record the data received from the sensors, or it can forward these data directly to a remote site, such as a physician's desktop computer or a hospital's monitoring center. In any case, since the sensors are wireless the subject can move freely around the base station, while an endless stream of data ows from the sensors he is carrying to the base station. This freedom of movement is however hampered by the short transmission range of current o-the-shelf wireless sensors. Indeed, most of these sensors include low-power radio transceivers, with which actual transmission ranges usually do not exceed a few meters. For this reason most research projects targeting health monitoring on mobile subjects rely either on dedicated base stations that must be deployed specically for that purpose [START_REF] Babovic | Prosense Reaseach Activities in Belgrad[END_REF], or assume ubiquitous connectivity to 2.5/3G infrastructure [START_REF] Konstantas | MobiHealth Innovative 2.5-3G Mobile Services and Applications for Healthcare[END_REF].

The concept of Disruption-Tolerant Networking3 (DTN) is a means to cope with challenging situations where continuous transmissions cannot be guaranteed. When considering a scenario involving mobile wireless devices, the general idea is to apply the store, carry, and forward principle: a device that is temporarily disconnected from the network can store data for a while in a local cache, carry these data while moving towards a location where network connectivity can be restored, and ultimately forward the data when circumstances permit.

Applying the store, carry and forward principle in wireless biomedical sensors is an appealing prospect. Indeed, a clinician monitoring a subject remotely does not necessarily need to receive data concerning this subject in real time. In most cases a time lag of a few minutes is perfectly tolerable. Using the store, carry and forward principle therefore makes sense in order to give greater mobility to the monitored subject. To the best of our knowledge this approach has not been investigated much so far, although disruption-tolerant solutions for non-biomedical sensor-based applications have already been proposed in the literature [START_REF] Pisztor | Opportunistic Mobile Sensor Data Collection with SCAR[END_REF][START_REF] Jain | Exploiting Mobility for Energy Ecient Data Collection in Wireless Sensor Networks[END_REF][START_REF] Nayebi | Routing, Data Gathering, and Neighbor Discovery in Delay-Tolerant Wireless Sensor Networks[END_REF].

The solution we consider specically in this paper consists in using any accessible Wi-Fi hotspot as a gateway for data uploading. Nowadays, Wi-Fi hotspots can be counted in millions. Besides corporate hotspots, most DSL providers distribute residential gateways that include a builtin Wi-Fi access point, which can operate a private and public Wi-Fi hotspot simultaneously. When a DSL subscriber accepts to enable the public hotspot service on his own residential gateway, he can in return access any other public hotspot deployed by the same DSL provider in the country. The millions of public hotspots managed by a single provider therefore constitute a wide community network that covers a signicant part of urban areas. A subject should thus be able to attend to his daily business, while the sensing system he's wearing relies on nearby hotspots to upload data to a monitoring center.

The remainder of this paper is organized as follows. The SHIMMER platform we use in this project for data acquisition on mobile subjects is described in Section 2. Section 3 presents the main features of the transmission chain we designed in order to support the disruption-tolerant transmission of data between subjects and a monitoring center. In Section 4 we present the results of one of the eld trials we conducted in order to validate this approach. Section 5 concludes this paper.

Overview of SHIMMER sensors

In this project we use SHIMMER platforms in order to acquire biomedical data on non-hospitalized subjects (see Fig. 1). The SHIMMER platform is a programmable lighweight wireless sensing system that can record and transmit physiological and kinematic data in real-time [START_REF] Burns | SHIMMER : A Wireless Sensor Platform for Noninvasive Biomedical Research[END_REF]. Data acquisition is performed on up to 8 channels through a 12-bit AD converter. Several kinds of expansion modules are available, including physiological sensors such as ECG (electrocardiography), EMG (electromyography) and GSR (galvanic skin response) sensors, as well as kinematic sensors for 3-axis angular rate sensing and 3-axis low eld magnetic sensing. Two low-power radio transceivers operating in the 2.4 GHz ISM band are included in the platform: an IEEE 802.15.4/ZigBee compliant CC2420 transceiver, and a WML-C46A class 2 Bluetooth transceiver. Since none of these standards can be used to connect directly to a Wi-Fi (IEEE 802.11) access point, an additional wearable device is required to serve as a relay between a SHIMMER sensor and a Wi-Fi access point. In the solution we propose this relaying device is an Android smartphone, which can receive data continuously from the sensor through a Bluetooth RFCOMM link, and forward these data whenever possible to nearby Wi-Fi access points, while tolerating the transient connectivity to such access points.

Protocol for data acquisition and transmission

We developed specic code in nesC (a dialect of C) for the SHIMMER sensors, and a Java application for Android smartphones. The main features of this code are detailed below.

Data acquisition on a SHIMMER sensor. This acquisition is performed on two 12-bit channels, with a sampling frequency that can be adjusted as needed. The nature of the data depends on the kind of expansion module that is associated with the main unit. In any case the data stream produced by the sensor is transmitted on-the-y to the smartphone through a Bluetooth RFCOMM link.

Transmission between sensor and smartphone. Each sensor must be paired with a specic smartphone, and two paired devices must of course be carried by the same subject. Once a smartphone is paired with a sensor, an RFCOMM link is established between them. Through this link, the smartphone can control the sensor, and send simple commands in order to adjust the sampling frequency or resolution, to start or stop data acquisition, etc. When data acquisition is enabled on a sensor, a continuous data stream is sent to the smartphone through the RFCOMM link.

The data stream received by the smartphone is packetized in small bundles, which are then stored in the smartphone's SD-card, awaiting for transmission to the monitoring center. The bundle's header includes an identier of the source sensor and a timestamp. Its payload is simply a byte array that contains a sequence of data bytes received from the sensor. The size of this payload depends on the data acquisition frequency and resolution on the sensor, as well as on the period set for data bundling. For example, data acquisition on two 12-bit channels with 200 Hz sampling produces a continuous data stream at 4.8 kbps.

Assuming a bundle is produced every 20 seconds on the smartphone, each bundle contains a 12 kiB payload.

Hotspot discovery, selection, and authentication. When a subject enters a hotspot, the smartphone he is carrying must detect the Wi-Fi access point that serves this hotspot and attempt to associate with it. If the association succeeds, the smartphone must send a DHCP request in order to obtain IP parameters from a DHCP server. Finally, some form of authentication may be required before access to the Internet is granted.

In order to ensure hotspot discovery, selection, and authentication in our project we rely on Wi2Me, an Android-based application that has been designed specically to support fast handover between hotspots in corporate and community networks [START_REF] Castignani | Wi2Me: A Mobile Sensing Platform for Wireless Heterogeneous Networks[END_REF].

Wi2Me notably uses active probe requests (rather than the standard's default passive scan) in order to locate nearby hotspots, and Kalman lters to characterize signal attenuation tendencies and select interesting hotspots accordingly. When connecting to a selected hotspot Wi2Me can authenticate with this hotspot using the standard WPA (Wi-Fi Protected Access) procedure, or through an HTTPS captive portal.

Transmission between smartphone and remote server. Once the Wi2Me application has managed to establish a connection and to authenticate with a nearby hotspot, the disruption-tolerant Android application we designed can start uploading data bundles to a server that is the entry point of the monitoring center. This application basically behaves like a client thread with respect to the server. Whenever a Connected notication is issued by the Wi2Me program, this thread attempts to open a TCP session with the server. If this attempt fails, the thread waits for a few seconds before initiating another attempt. Once a TCP session is established, bundles stored in the local cache are sent to the server sequentially, and each bundle received by the server is acknowledged explicitly at application level. This approach allows the client thread to detect and react to transmission failures, which typically occur when the subject carrying the smartphone moves out of the radio range of the current hotspot. The Wi-Fi connection is then broken unexpectedly, and the TCP session must be closed unilaterally on the client side while TCP segments (containing fragments of data Several strategies can be devised in order to determine which data bundles should be sent rst when a smartphone establishes a connection with a new hotspot. An option is for example to preserve the chronological ordering of data bundles, uploading the oldest bundles rst. In the current implementation we decided to favor the transmission of fresh data rst, and to ll the gaps by uploading older bundles whenever possible. The application's client thread was therefore implemented in such a way that real-time bundles (i.e. those produced during a radio contact between the sensor and the base station) get uploaded to the monitoring center rst, and the time remaining during a contact window is used to upload older bundles, that is, bundles that are stored on the smartphone's micro-SD card and that have not been uploaded to the monitoring center yet. A graphical application running in the monitoring center can thus display the latest data concerning a subject, while allowing an operator to rewind the data stream in order to display past data if necessary.

Experimental results

In order to validate our approach, we conducted several eld trials involving volunteers carrying SHIMMER sensors and HTC Wildre S smartphones.

Several scenarios were considered, with subjects staying at home, going to work, shopping, etc. In this section we present the results observed with a sub- The subject was rst equipped at home with an ECG-enabled sensor and a smartphone (Fig. 1). After a few minutes he went for a 4.6 km walk, and came back home about an hour later. Figure 2 shows the route followed by the subject during his walk, as well as the community hotspots his smarphone managed to connect to along that route. Figure 3 shows the timeline of data bundles storage and transmissions during this experiment, as well as the connectivity status of the smartphone.

At 13:35 both devices were switched on. The sensor immediately started monitoring the cardiac activity of the subject, while the smartphone connected to the subject's own Wi-Fi access point (the most accessible hotspot at that time). The bundles of ECG data produced were therefore transmitted in real time to the remote server. At 13:40 the subject went out. The smartphone then disconnected from the access point, and started storing data bundles. At 13:44 the smartphone connected to a second hotspot, but did not manage to upload bundles through that hotspot. At 13:46 it connected to a third hotspot, and this time it managed to upload through that hotspot the 20 bundles stored in its cache. Since the connection with that hotspot was maintained for almost one minute, the smartphone additionally managed to upload a couple of fresh bundles before the connection was broken. As the subject continued walking in the streets further connections were established with community hotspots, until the subject came back home around 14:47.

This trial lasted 74 minutes, and 45 hotspots were used for data uploading in the meantime. disconnected periods. It can be observed that about 80% of the connections to hotspots lasted less than one minute, which is consistent with the fact that the subject was mobile and walking at a steady pace most of the time during the period considered. Similarly, it can be observed that more than 90% of the disconnected periods lasted less than 2.5 minutes. This observation conrms that the density of community hotspots in a residential area is such that a disruptiontolerant application like ours can nd many opportunities to upload data to a remote server. The delay before data bundles can reach the server of course depends on the frequency of connections with hotspots. As shown in Figure 4.b, during this trial most bundles reached the server in less than one minute, and no bundle was more than 6 minutes old when it reached the server.

During this trial the battery level on the smartphone dropped by 40%. Since the GPS receiver was enabled in order to record the route followed by the subject, this gure is not a good indication of the autonomy of the system. According to measurements we performed in our laboratory, a SHIMMER sensor with an ECG expansion module can run for almost 10 hours on its built-in battery, while sending data continuously on a Bluetooth RFCOMM link. A HTC Wildre S smartphone maintaining a Bluetooth connection with a SHIMMER sensor and establishing episodic connections with nearby Wi-Fi hotspots depletes its battery in 5 to 7 hours, depending on the frequency of radio contacts with these hotspots. In contrast, it is worth mentioning that if the smartphone uses 3G transmissions instead of Wi-Fi transmissions its battery is depleted in less than 3 hours. These gures conrm that with a combination of Bluetooth and Wi-Fi transmissions (with disruption tolerance on the Wi-Fi segment) a subject can be monitored during his daily activity, provided the smartphone's battery can be recharged at least once or twice during the meantime.

In this paper we investigated the possibility to collect biomedical data on nonhospitalized mobile subjects. The approach we propose involves o-the-shelf wireless sensors for data acquisition, and smartphones that can record data continuously and upload these data whenever possible to a remote monitoring center. Transient connectivity with personal, corporate, or community Wi-Fi hotspots is used by a disruption-tolerant application running on the smartphone to perform data uploading transparently and opportunistically.

Results of a eld trial involving a subject walking in a residential area conrm that the density of community hotspots in such an environment is sucient to ensure regular updates of the data collected by the monitoring center. Other trials conducted in dierent conditions (subject at work, shopping, practising sports, etc) have led to similar conclusions.

There are of course circumstances when the smartphone carried by a subject may be unable to connect to a Wi-Fi hotspot for long periods of time. In such circumstances it may be useful to resort to 3G transmissions, if only to upload a minimal set of data while waiting for the next hotspot connection. With this approach the major bottlenecks are the lower transmission rate (for upload) and the power-greedy nature of 3G transmissions. In future papers we shall propose a combination of these solutions, balancing transmission delays with cost and longevity.

Fig. 1 .

 1 Fig. 1. A volunteer is equipped with an ECG-enabled SHIMMER sensor and a smartphone (which can be worn in an armband or in a pocket)

Fig. 2 .

 2 Fig. 2. Route followed by the volunteer sub ject during the experiment. The green circles represent community hotspots used by his smartphone to upload ECG data while he walked along streets and footpaths

Fig. 3 .

 3 Fig. 3. Timeline of data storage and transmissions during the experiment

Figure 4 .Fig. 4 .

 44 Fig. 4. Cumulative distribution (a) of hotspot connectivity periods, and (b) of the age of bundles at delivery time

The term Delay-Tolerant Networking is also used in the literature.


Djamel Benferhat

Frédéric Guidec

Patrice Quinton

Cardiac Monitoring of Marathon Runners using Disruption-Tolerant Wireless Sensors

published or not. The documents may come   L'archive ouverte pluridisciplinaire

Introduction

In this paper we investigate the possibility of using o-the-shelf wireless sensors to monitor the cardiac activity of runners during a marathon race. In such a scenario the runners must cover a long distance during the race, and that distance clearly exceeds the very limited radio range of the low-power IEEE 802.15.4 (Zig-Bee) or IEEE 802.15.1 (Bluetooth) radio transceivers available on most current sensors. However, since runners in a marathon all follow exactly the same route, a number of base stations (BS) with broadband connectivity to the Internet can be deployed on the roadside (see Figure 1). Whenever a runner passes by a BS, ECG data received from this runner's ECG sensor can be forwarded to a remote site, such as the closest medical aid station or a physician's desktop, laptop, or smartphone.

In previous work we considered using IEEE 802.15.4 (ZigBee) transceivers to implement the wireless link between sensors and roadside stations [START_REF] Benferhat | Disruption-Tolerant Wireless Biomedical Monitoring for Marathon Runners: a Feasibility Study[END_REF]. Each roadside station then took the form of a netbook or laptop with a ZigBee interface. Yet this approach proved ineective and unable to support a large number of runners, mostly because of the low bitrate and low transmission range allowed by the IEEE 802.15.4 standard. In the current work the base stations take the form of standard Wi-Fi access points. Since o-the-shelf ECG sensing devices do not feature Wi-Fi interfaces, each runner must carry a smartphone (additionally to the ECG sensor) that can serve as a relay between the sensor and base stations. With this conguration the ECG data stream produced by an ECG sensor is transmitted directly and continuously to the associated smartphone through a Bluetooth RFCOMM link. The smartphone processes this data stream, and forwards the resulting data bundles whenever possible to roadside base stations using Wi-Fi wireless links.

Current biomedical applications usually either perform data recording for deferred analysis, or they depend on continuous connectivity for real-time transmission and processing. For example projects Mobihealth and HYGEIAnet assume continuous network connectivity, as they aim at developing new healthcare mobile services using 2.5/3G technology for physiological data collection [START_REF] Konstantas | Continuous Monitoring of Vital Constants for Mobile Users: the MobiHealth Approach[END_REF][START_REF] Nayebi | Routing, Data Gathering, and Neighbor Discovery in Delay-Tolerant Wireless Sensor Networks[END_REF]. Data recording for deferred analysis is notably used in [START_REF] Kugler | Mobile Recording System for Sport Applications[END_REF][START_REF] Chelius | A Wearable Sensor Network for Gait Analysis: A 6-Day Experiment of Running Through the Desert[END_REF], which rely on wearable recording sensors for health monitoring during sports activities. To the best of our knowledge the utilization of disruption-tolerant techniques to monitor athletes in outdoor conditions has not been investigated much so far, although disruption-tolerant solutions for non-biomedical sensor-based applications have already been proposed in the literature [START_REF] Nayebi | Routing, Data Gathering, and Neighbor Discovery in Delay-Tolerant Wireless Sensor Networks[END_REF][START_REF] Pasztor | Opportunistic Mobile Sensor Data Collection with SCAR[END_REF].

The remainder of this paper is organized as follows. In Section 2 we estimate the number of base stations required to would be required to cover the full length of a marathon route, and show that a sparse deployment of base stations can be sucient to cover this route satisfactorily. The SHIMMER sensor we use in this project for ECG data acquisition is described in Section 3. Section 4 presents the main features of the tranmission chain we designed in order to support the disruption-tolerant transmission of ECG data between runners and a monitoring center. In Section 5 we report on a eld trial we conducted on our university campus in order to validate this work. Section 6 concludes this paper.

2 Rationale for a sparse coverage of the marathon route In outdoor conditions, the transmission range between a mobile smartphone and a xed Wi-Fi access point can sometimes exceed 300 meters. Of course this distance is often diminished because of obstacles or radio interferences. Let us assume that the connectivity between mobile smartphone and a base station (basically an access point) is guaranteed on an average distance of 100 meters.

A base station deployed along a marathon route would thus cover about 200 meters of that route, and at least 200 base stations would be required to ensure a full coverage of the 42.2 km route.

Since deploying hundreds of base stations along a marathon route is hardly an option for organizational and nancial reasons, our approach is based on the premise that only a sparse coverage of the route needs to be ensured, using a reasonable number of base stations. A disruption-tolerant solution for data gathering must therefore be implemented, using the store-carry-and-forward principle. This principle is the foundation of Disruption-Tolerant Networking (DTN): a mobile node that is temporarily disconnected from the rest of the network can store data (or messages) in a local cache, carry these data for a while, and forward them later when circumstances permit [START_REF] Fall | Messaging in Dicult Environments[END_REF]. In our scenario, the ECG sensor carried by a runner captures data continuously and transmits these data to the smartphone, which stores these data locally. Whenever the runner passes by a BS, a transient radio contact occurs between the smartphone and that BS. This contact is exploited by the smartphone to upload bundles of data to the BS, which in turn can forward these bundles to the monitoring center (see Fig. 1).

The distance between successive base stations and the speed of the runner determine how often fresh data can be sent to the monitoring center. According to cardiologists, a physician monitoring the cardiac activity of marathon runners should receive updated data for each runner at least every 5 to 10 minutes, in order to be able to detect arrhythmias and prevent incidents. Considering the pace of an average runner this implies that base stations should be placed about 1 to 2 km apart. With this approach, ten to twenty base stations are sucient to cover a marathon route satisfactorily.

Overview of SHIMMER sensors

In this project we use SHIMMER platforms in order to acquire ECG data on each runner, and HTC Android smartphones as disruption-tolerant relays between SHIMMER sensors and roadside base stations.

The SHIMMER platform is a programmable lighweight wireless sensing system that can record and transmit physiological and kinematic data in realtime [START_REF] Burns | SHIMMER : A Wireless Sensor Platform for Noninvasive Biomedical Research[END_REF]. Data acquisition on the SHIMMER platform is performed on up to We developed specic code in nesC (a dialect of C) for the SHIMMER sensors, and in Java for Android smartphones. The acquisition of ECG data on each SHIMMER sensor is performed on two 12bit channels (RA-LL and LA-LL leads), with a sampling frequency that can be adjusted as needed. The data stream hence produced is transmitted on-the-y to the smartphone through a Bluetooth RFCOMM link.

Transmission between SHIMMER sensor and Android smartphone

Each SHIMMER sensor must be paired with a specic smartphone, and two paired devices must of course be carried by the same marathon runner. The Java application we designed for Android smartphones allows a user to locate nearby SHIMMER sensors, and to pair the smartphone with one or several of these sensors, using secured pairing if desired. The possibility for a single smartphone to collect data from several sensors is a provision for future work: several sensors may thus be attached to a single athlete, so dierent kinds of data can be collected simultaneously. Once a smartphone is paired with a sensor, an RFCOMM link is established between them. Through this link the smartphone can control the sensor, and send simple commands in order to adjust the sampling frequency or resolution, to start or stop the data acquisition, etc. When data acquisition is enabled on a sensor, a continuous data stream is sent to the smartphone through the RFCOMM link.

The code we designed for both SHIMMER sensors and Android smartphones can tolerate transient disruptions in RFCOMM links. For example, if paired sensor and smartphone get disconnected for a while, they strive to re-establish the connection, and data transmission (if enabled) resumes as soon as the connection is re-established.

The data stream received by the smartphone is packetized in small bundles, which are then stored in the smartphone's SD-card, awaiting for transmission to the monitoring center. Each bundle consists of a header and a payload. The header includes an identier of the source sensor and a timestamp. The payload is simply a byte array that contains a sequence of data bytes received from the sensor. The size of this byte array depends on the data acquisition frequency and resolution on the sensor, as well as on the period set for data bundling. For example, data acquisition on two 12-bit channels with 200 Hz sampling produces a continuous data stream at 4.8 kbps. Assuming a bundle is produced every 20 seconds on the smartphone, each bundle contains a payload of 12 kiB.

Transmission between SHIMMER sensor and roadside base station

As mentioned in the former section a base station is typically a standard Wi-Fi access point with broadband connectivity to the Internet. When a runner passes close to a base station, the smartphone he/she is carrying detects the access point and tries to associate with it. If the association succeeds, the smartphone authenticates if needed, and sends a DHCP request in order to obtain IP parameters from a DHCP server. Once the IP connectivity is obtained, the Android application we designed starts uploading data bundles to a remote server that is the entry point of the monitoring center.

The transmission of data bundles between smartphone and server is performed using UDP datagrams. Each bundle of ECG data easily ts in a single datagram, so no fragmentation is required at this level. An ARQ (Automatic Repeat reQuest) mechanism is however implemented in order to prevent any loss of data bundle.

Rate control. When a smartphone carried by a runner establishes a connection with a base station these devices are still far away from each other (see Fig. 1).

The quality of the wireless link between them is usually quite low, so sending data bundles too hastily in such conditions could yield a high level of data loss. In order to prevent this problem our Android application implements a rate control mechanism that is inspired from TCP's slow-start mechanism. At the beginning of a contact window when the smartphone has just received IP parameters from the DHCP server a simple stop-and-wait method is used: the smartphone only sends one bundle, and waits for an acknowledgement that this bundle has been received by the server. Once this acknowledgement is received the next data bundles are sent with a go-back-N method: up to N bundles can be sent in a row, before receiving the acknowledgement of the rst of these bundles.

The width of the sliding window (N) can be adjusted dynamically as the runner moves closer to the access point, then farther from this access point. Experience conrms that the combination of both ARQ methods allows an ecient use of the contact window between smartphone and base station, and does not induce a high level of transmission failures at the beginning of a contact window.

Uploading strategy. Several strategies can be devised in order to determine which data bundles should be sent rst when a smartphone establishes a connection with a nearby base station. An option is for example to preserve the chronological ordering of data bundles, uploading the oldest bundles rst. For the eld trial reported in the next section we decided to favor the transmission of fresh ECG data rst, and to ll the gaps by uploading older bundles whenever possible. The transmission algorithm running in the smartphone's application was therefore implemented in such a way that real-time bundles (i.e. those produced during a radio contact between sensor and base station) get uploaded to the monitoring center rst, and the time remaining during a contact window is used to upload older bundles, that is, bundles that are stored on the smartphone's micro-SD card and that have not been uploaded to the monitoring center yet. A graphical application running in the monitoring center can thus display the latest cardiac activity of a runner, while allowing an operator to rewind the ECG stream in order to display past events if necessary.

Power consumption. According to measurements we performed in our laboratory, a SHIMMER sensor with an ECG expansion module car run for almost 10 hours on its built-in battery, while sending ECG data continuously on a Bluetooth RFCOMM link. An HTC Wildre S smartphone maintaining a Bluetooth connection with a SHIMMER sensor and establishing episodic connections with nearby Wi-Fi access points depletes its battery in 5 to 7 hours, depending on the frequency of radio contacts with these access points. These gures conrm that with a combination of Bluetooth and Wi-Fi transmissions (with disruption tolerance on the Wi-Fi segment) a runner can be monitored during the whole duration of a marathon race. In contrast, it is worth mentioning that a smartphone using 3G transmissions instead of Wi-Fi transmissions to upload ECG data to a monitoring center depletes its battery in about 3 hours. If using 3G instead of Wi-Fi there is therefore a risk that the smartphone shuts down before the runner has reached the nish-line.

Experimental results

Before trying to capture the ECG stream of runners during a real marathon, we decided to run eld trials at a much smaller scale in order to validate our approach. An experiment was thus conducted on our university campus. Three volunteers were equipped with ECG-enabled SHIMMER sensors and HTC Wildre S smartphones, and two base stations (BS1 and BS2) were placed about 1 km apart along the running route. These base station were standard Wi-Fi access points. They were both placed on a window-ledge, and connected to the campus LAN. The runners had to run around the campus, passing twice close to each base station.

During the race our prime motivation was to observe if the data bundles produced continuously on each runner could actually be transmitted when the runner's smartphone established radio contact with one or another base station. Figure 2 shows the timeline of transmissions between the smartphones carried by the three runners (S1 to S3) and the two base stations. The rectangles in dotted lines depict a radio contact between a smartphone and a base station. The grey background shows the actual running time of a runner during the trial.

Let us examine the transmission timeline for S1. This smartphone was installed together with a SHIMMER sensor on a runner around 10:58. Both devices were activated immediately, so S1 started collecting bundles of data from that time on. Once the three runners were ready to go, they walked together to the start line. Since BS1 was located near that line a connection S1 established a connection with B1, and started uploading to the remote server all the bundles it had recorded since its activation. At 11:04, the three runners started running.

The connection between S1 and BS1 was therefore interrupted, after a 105 second contact window during which 21 data bundles had been uploaded to the server. Around 11:10 S1 established a connection with the second base station. This new contact window lasted 40 seconds, and this time 19 bundles were uploaded by S1 (17 of these bundles had been produced since S1 lost contact with BS1, and 2 new bundles were produced while S1 was in contact with BS2). As the runner carrying S1 continued running around the campus, S1 later established a connection again with BS1 (around 11:19), and then with BS2 (around 11:28), which was installed close to the nish-line. 123456778339 Fig. 2. Timeline of data transmissions during the race for the three runners During this trial no data bundle was lost, or failed to reach the remote server. These results therefore conrm that the protocol we implemented on SHIMMER sensors and Android smartphones can indeed tolerate episodic connectivity to roadside base stations, with no loss of data. Further experiments involving a larger number of runners covering a longer distance should of course be conducted, but considering the high bandwidth available with Wi-Fi transmissions it can be expected that dozens of runners can be monitored simultaneously using this approach.

Conclusion

In this paper we investigated the possibility to monitor the cardiac activity of runners during a marathon race. Unlike most current monitoring applications, which imply either indoor real-time data streaming or ambulatory data recording, the solution we propose makes it possible to get updates about each runner's health regularly during the race, using episodic transmissions between sensors carried by runners and base stations deployed sparsely along the marathon route. Disruption-tolerant transmission techniques are used to cope with the partial coverage of the route.

A preliminary eld trial has been conducted with volunteers running around our university campus, using SHIMMER sensors for data acquisition and Android smartphones for Wi-Fi transmission to roadside base stations. This trial conrms that capturing and transmitting ECG data during a running race is indeed feasible with such devices and technologies. In future work we plan to increase both the number of monitored runners and the duration of the eld trials in order to check the scalability of this approach. Ultimately we would of course like to demonstrate that dozens (or possibly hundreds) of runners can be monitored during a real marathon race.

Fig. 1 .

 1 Fig. 1. Illustration of disruption-tolerant ECG monitoring of marathon runners

8

  channels through a 12-bit AD converter. Several kinds of expansion modules are available: the ECG module we use provides RA-LL (Right Arm -Left Leg) and LA-LL (Left Arm -Left Leg) input leads. The RA-LA (Right Arm -Left Arm) lead can be calculated based on the rst two leads. Two built-in radio transceivers operating in the 2.4 GHz ISM band are available: an IEEE 802.15.4/ZigBee compliant CC2420 transceiver, and a WML-C46A class 2 Bluetooth transceiver.

4 . 1

 41 Data acquisition on a SHIMMER sensor