Alice Dejean

La Batie

PROPOSALS REFORMING FRENCH CIVIL LIABILITY

In cases of non-performance, the creditor of an

Article 1234

When the non-performance of a contractual obligation is the direct cause of a loss suffered by a third party, the latter can only ask for compensation to the debtor on the ground of extra-contractual liability. It will be for the third party to prove the occurrence of one of the operative events provided for by section II of chapter II.

CHAPTER II -THE CONDITIONS OF LIABILITY SECTION 1-Provisions common to contractual and extra-contractual liabilities Subsection 1. Compensable loss Article 1235

A person can ask for compensation of any certain loss arising from an injury and consisting in the harming of a lawful interest, relating to assets or not, individual or collective.

Article 1236

Future loss can be compensated when it is the certain and direct continuation of a present state of affairs.

Article 1237

Expenses incurred by the defendant in order to prevent the imminent occurrence of harm or to prevent its aggravation, as well as to reduce its consequences, represent a compensable loss as long as they were reasonably undertaken.

The only compensable loss of opportunity is the certain and present disappearance of a favourable prospect.

Harm arising from a loss of opportunity is distinct from the advantage that would have accrued had this opportunity come about.

Sub-section 2. The causal link Article 1239

Liability requires the demonstration of a causal connection between a fact attributable to the defendant and the harm.

The causal link can be proved by all means.

Article 1240

When a [physical] injury is caused by an indeterminate member of a group of identified people acting together or for similar reasons, each of them is answerable for the entire loss, unless they can prove that they cannot have caused it. Any fault compels its author to compensate the harm it caused.

Article 1242

A fault is constituted by the violation of a rule of conduct imposed by law or the failure to fulfil the general duty of caution and diligence. §2 Actions of things

Article 1243

A person is strictly liable for harm caused by the actions of tangible things which are in their custody.

The action of a thing is presumed when the thing, while moving, came into contact with the person or the property which is harmed.

In other situations, it is for the victim to prove the action of the thing by showing either that the thing was defective, or that its position, condition or behaviour was abnormal.

The custodian is the person using, controlling and directing the thing at the time of the harmful event. The owner is presumed to have custody.

The provisions of this paragraph are applicable to the actions of animals. §3 Abnormal nuisance

Article 1244

An owner, a tenant, the holder of a title mainly aiming at authorising them to occupy or manage an estate, a project manager, or the person exercising their power, who causes a nuisance is liable when the nuisance exceeds normal inconvenience to be expected of neighbours.

When a harmful activity was administratively authorised, the judge can nonetheless grant compensation or order reasonable measures to be taken in order to stop the nuisance, provided these measures do not contradict provisions made by the administrative authorities in order to protect safety and public hygiene.

Subsection 2. Liability for the actions of other persons

Article 1245

A person is liable for harm caused by another person in the situations and under the conditions provided for by articles 1246 to 1249. Such liability requires evidence of a fact on which the liability of the direct author of the harm could be grounded.

Article 1246

The following persons are strictly liable for the actions of a minor: -their parents, to the extent to which they exercise parental authority; -their guardian(s), as long as they are in charge of the minor -the physical or legal person entrusted by a judicial or administrative decision with the permanent organisation and control of the minor's way of life. In this case, the minor's parents cannot be held liable.

Article 1247

The physical or legal person entrusted by a judicial or administrative decision with the permanent organisation and control of an adult's way of life is strictly liable for the actions of the adult placed under their care.

Article 1248

Other persons who are committed to the care of someone on the basis of a professional contract are liable for the actions of that person unless they can demonstrate that there was no fault on their part.

Article 1249

Employers are strictly liable for the actions of their employees. The employer is the person who has the power to give orders or instructions related to the employee fulfilling their functions.

When this authority has been delegated, the beneficiary of the delegation bears this liability.

The employer, or the beneficiary of the delegation, is not liable if they can prove that the employee acted beyond the scope of the functions they had been tasked with, without authorisation, and for purposes not related to their tasks. They are also not liable if they can prove that the victim could not legitimately believe that the employee was acting on behalf of the employer.

Employees are personally liable only in cases of wilful misconduct or when they acted without authorisation for purposes not related to their tasks.

SECTION 3 -Provisions regarding contractual liability Article 1250

Debtors are liable for any non-performance of their contractual obligation that caused harm to their creditors.

Article 1251

Apart from cases of willful misconduct or gross negligence on their part, debtors are only liable for those consequences of their non-performance that were reasonably foreseeable at the time when the contract was made.

Article 1252

Compensation for loss resulting from a delay in performance requires a prior formal notice made to the debtor. Formal notice is required for the compensation of other losses only when such notice is necessary in order to establish non-performance.

CHAPTER III -Causes of exemption from liability or liability exclusion SECTION 1 -Causes of exemption Article 1253

Acts of God and the actions of a third party or of the victims lead to total exemption if they satisfy the conditions of force majeure .

For extra-contractual matters, force majeure is an event that the defendant, or the person whose actions they are accountable for, could not prevent through appropriate measures, or an event whose consequences could not be so avoided by the defendant.

For contractual matters, force majeure is defined by article 1218.

Article 1254

A victim's failure to fulfil their contractual obligations, their fault, or the fault of a person whose actions the victim is accountable for, leads to partial exemption when it contributed to their loss. In cases of physical injury, only gross negligence can lead to partial exemption.

Article 1255

When the victim has no discernment, their fault does not lead to exemption.

Article 1256

A fault or non-performance that can be invoked against direct victims can also be invoked against indirect victims.

SECTION 2 -Causes of liability exclusion Article 1257

Harmful events do not give rise to fault-based liability when they were compulsory under legislative or administrative provisions, or imposed by a legitimate authority, or ordered by the necessity of self-defence or of the safeguard of a superior interest.

There is also no liability when the event was harmful to a right or an interest that the victim could dispose of, when the victim consented to it.

CHAPTER IV -THE EFFECTS OF LIABILITY SECTION 1 -Principles Article 1258

Provided that there are no contrary provisions or clauses, the object of compensation must be to place the victim in the position they would be in had the harmful event not occurred. This should lead to neither loss nor gain for the victim.

Article 1259

Compensation can be in the form of compensation in kind or in the form of damages. Both measures can be combined in order to fully compensate the loss.

Subsection 1. Compensation in kind Article 1260

Compensation in kind must be specifically suitable to extinguishing, reducing or making up for the harm.

Article 1261

Compensation in kind cannot be imposed on the victim.

It also cannot be ordered when it is impossible, or when it would infringe a fundamental freedom, or when it would represent for the person liable a clearly unreasonable cost considering the interest of such compensation for the victim.

Following the same conditions, the judge may also authorise the victim to take measures themselves to get compensation at the expense of the person liable. The latter may be ordered to pay an advance on forthcoming necessary expenses.

Subsection 2. Damages Article 1262

Damages are assessed at the date of the judgment, taking into account all circumstances which may affect the composition and the value of the loss since the day on which the harm occurred. It also takes into account the reasonably foreseeable development of the loss .

When the harm increased after the court decision, the victim may ask for complementary compensation for the resulting loss.

Each alleged incidence of loss is assessed separately.

Article 1263

For contractual matters, the judge may reduce compensation when the victim did not take those safe and reasonable measures that would have prevented the aggravation of the harm, considering amongst other things the victim's means.

Article 1264

Victims are free in their use of the sums paid to them in compensation, unless exceptional circumstances justify that the judge imposes the use of damages to redress a specific harm.

Subsection 3. The effects of several persons being liable Article 1265

When several persons are liable for the same harm, they are jointly and severally held to compensate the victim. If they all committed a fault, they each contribute in proportion to the gravity of their respective fault. If none of them committed a fault, they contribute equally. If only some of them committed a fault, they are the only ones bearing the final costs of compensation.

Subsection 4. Civil fines Article 1266

When the author of a harm was deliberately grossly negligent, especially when such negligence generated a profit or a saving for its author, the judge may condemn them to the payment of a civil fine, provided the decision is specifically justified. This fine is proportionate to the gravity of the fault, to the payment ability of the author or to the profit they made.

The fine cannot be higher than 2 million euros. However, it can be ten times higher than the amount of the profit or saving made.

If liability is borne by a legal person, the fine can be as high as 10% of the company's highest global pre-tax turnover during any of the completed fiscal years since the fiscal year preceding the fiscal year during which the fault was committed.

This fine goes either to a compensation fund related to the nature of the harm undergone by the victim or, by default, to the Treasury.

SECTION 2 -Rules specific to compensation of certain types of harm Subsection 1. Rules specific to compensation for losses resulting from physical injuries Article 1267

This subsection's rules are applicable to judicial and administrative court decisions, as well as to transactions concluded between the victim and the person liable.

Article 1268

Damages have to be assessed without taking into account the victim's possible predispositions, as long as these predispositions had not already had harmful consequences at the time when the harmful event occurred.

Article 1269

Harm, whether relating to assets or not, resulting from a physical injury is assessed, item-by-item, according to a non-restrictive list of the possible heads of loss provided for by a decree of the Conseil d'Etat.

Article 1270

Unless otherwise specifically provided for, functional impairments are assessed according to a single indicative medical scale. The ways in which this scale is made, revised and published are provided for by government regulation.

Article 1271

[A decree from the Conseil d'Etat provides for the incidences of damage not relating to assets that can be assessed according to an indicative compensation baseline. The ways in which this baseline is made and published are provided for by the same decree. This baseline is regularly re-assessed in light of changes to the average compensation granted by courts.

To that end,] definitive appeal decisions regarding compensation for physical injuries suffered by victims of traffic accidents are gathered in a database, under the control of the State and under the conditions provided for by the decree of the Conseil d'Etat.

Article 1272

Compensation for the loss of professional gains, the loss of income of those close to the victim or for support of a third party, usually comes in the form of an indexed annuity. The index is provided for by government regulation and is linked to changes of the minimal income.

Annuities may be converted into capital so long as the parties agree to it, or if this decision is specifically justified by the judge, and in accordance with a table provided for by government regulation.

When an annuity was provided for by agreement, or by a court decision, as compensation for future losses, the recipient can ask that remaining annuity payments be fully or partially replaced by capital, when this is justified by their personal situation, and in accordance with the conversion table mentioned in the preceding paragraph.

Article 1273

Compensatory sums paid to a victim by a third-party payer can only lead to subrogatory actions when provided for by law.

Article 1274

When the victim of a physical injury receives benefits, a suit against the person liable for damages, or their insurer, is only possible for the following benefits:

1. Benefits paid by agencies, institutions or services in charge of a compulsory social security scheme; 2. Benefits listed by article 1 -II of the #59-76 ordinance of January 7th 1959 concerning suits open to the State and some other public bodies to seek damages; 3. Sums paid as a refund for medical treatment and rehabilitation fees 4. Wages and accessories of wages maintained by the employer during the period of inactivity following the event that caused the harm. 5. Sick pay and disability benefits paid by mutual benefit societies regulated by the Code de la Mutualité , welfare institutions regulated by the Social Security Code or the Rural Code, and insurance companies regulated by the Insurance Code; 6. Benefits provided for by article L.245-1 of the Code de l'Action Sociale et des Familles .

Article 1275

Employers have a direct claim against the person liable for damages or their insurer, for refund of the costs related to remuneration maintained or paid to the victim during the time when the victim was unable to work. These provisions are applicable to the State, as an exception to article 2 of the above-mentioned #59-76 ordinance of January 7th 1959.

Article 1276

Benefits that can be claimed are deduced, item-by-item, only from compensation due by the person liable for the losses covered by the third-party payer, except for losses not relating to assets.

When the insolvency of the person liable would prevent the full compensation of the victim, the latter will have priority over the third-party payer for what is still owed to them.

The victim's fault can only reduce their right to compensation for the part of their loss that is not covered by the third-party payer. The latter is entitled to the residual debt of the person liable.

Article 1277

Apart from benefits mentioned by articles 1274 and 1275, persons liable for damages, or their insurers, have no claim for payments made to a victim under a legal, contractual or statutory obligation.

However, when it is provided for by contract, insurance companies who paid the victim an advance on forthcoming compensation for an accident have a claim against the insurance company of the person liable for damages. This is limited to what remains after payment was made to the third-parties mentioned by article 1274. When required, these suits must be brought before the deadline imposed by law on third-party payers to lodge their claims.

Any provision contrary to article 1273 to 1276 is deemed inexistent unless it is more favourable to the victim.

Subsection 2. Rules specific to compensation for losses resulting from damage to property

However, liability cannot be contractually excluded or limited in cases of physical injuries.

Article 1282

In extra-contractual matters, compensation for harm caused by a fault cannot be excluded or limited.

In cases of strict liability, a contract only has effect when the person trying to invoke the contract can prove that it had been unequivocally agreed to by the victim.

Article 1283

In contractual matters, compensation limitation and exclusion clauses have no effect in cases of wilful misconduct or gross negligence from the debtor, or when such clauses would be in contradiction with an essential obligation of the contract. These clauses also have no effect when the party against whom they are invoked could not become aware of their existence before the formation of the contract.

Subsection 2. Punitive damages Article 1284

When a contract stipulates that the party failing to perform will pay punitive damages, the other party cannot be allocated higher or lower damages.

However, the judge may, on their own initiative, moderate or increase the so-agreed punitive damages if they are clearly excessive or derisory.

In cases of partial performance, the judge may, even on their own initiative, diminish the agreed punitive damages in proportion to the gain made by the creditor thanks to this partial performance, without prejudice to the provisions of the preceding paragraph.

Any stipulation in contradiction with the two preceding paragraphs is deemed inexistent.

Unless nonperformance is definitive, punitive damages are only due after the debtor was formally notified.

CHAPTER V -MAIN SPECIAL REGIMES OF LIABILITY SECTION 1 -Motorised ground vehicles Article 1285

The driver or custodian of a motorised ground vehicle is strictly liable for any harm caused by a traffic accident in which their vehicle, or their trailer, was involved.

The provisions in this section are public policy provisions and are the only ones applicable to the driver or custodian of a vehicle involved in a traffic accident. They even apply when the victim was transported consequent to a contract.

Article 1286

Acts of God or the actions of a third-party cannot be invoked against a victim even when such events and actions satisfy the conditions of force majeure .

Victims are not entitled to compensation when they deliberately sought the harm.

Article 1287

In cases of physical injury, the victim's fault has no impact on the victim's right to compensation, unless it is inexcusable and was the sole cause of the accident.

However, physical injuries are always compensated when suffered by victims under sixteen or over seventy years old, or when the victim, whatever their age, held at the time of the accident a certificate attesting to a permanent functional impairment of at least 80%.

Article 1288

In cases of damage to property, the victim's fault limits or excludes compensation for their loss when it contributed to the production of the harm.

The decision to exclude compensation must be specifically justified by reference to the seriousness of the fault. However, damages caused to medically prescribed supplies or devices follow the rules of compensation for physical injuries.

When the driver of a motorised ground vehicle is not the owner, the driver's fault can be invoked against the owner for compensation for non-physical harm. The owner then has a claim against the driver.

SECTION 2 -Liability for defective products Article 1289

Producers are liable for harm caused by a defect in their products, whether or not they are contractually bound to the victim.

Article 1290

The provisions in this section apply to compensation for losses resulting from physical injuries.

They also apply to compensation for losses resulting from damage to property other than the defective product itself, when the value of such loss is higher than an amount provided for by decree, and on the condition that this asset was of a type normally intended for private use or consumption, and was used by the victim mainly for their private use or consumption.

Article 1291

A product is any movable property, even when it is incorporated into an immovable property, including products from the ground, fishing products, and hunting products. Electricity is also considered as a product.

Article 1292

In this section, a product is defective when it does not fulfil legitimate safety expectations.

The assessment of legitimate safety expectations includes all circumstances, especially the product's presentation, reasonably expected use, and time of release.

A product cannot be considered defective only because a more sophisticated version was subsequently released.

Article 1293

Producers are those who, when acting as professionals, manufacture a final product, produce raw materials, or manufacture a component.

For the application of this section, the following persons are considered producers when they act as professionals: 1°Persons assuming the role of a producer by putting their name, brand or any other distinctive sign on a product; 2°Persons importing a product in the European Union in order to sell, rent -with our without an agreement to sell -, or distribute a product in any other way.

Persons who can be held liable under article 1646-1 and 1792 to 1792-6 are not considered as producers for this section.

Article 1294

If the producer cannot be initially identified, the seller, the lessor -with the exception of a lessor under a lease-purchasing agreement or equivalent -, or any professional supplier, is liable for a product's lack of safety, under the same conditions as the producer, unless they identify their own producer within three months after they were notified of the victim's demand.

Suppliers can sue the producer under the same rules as the direct victim of the defect. However, they must act within one year after being legally notified that they were summoned to court.

Article 1295

In situations where harm was caused by the defect of a product incorporated into another one, the producer of the component and the person who incorporated it are severally liable.

Article 1296

Plaintiffs must prove the harm, the defect and the causal link between the defect and the harm.

Article 1297

Producers can be liable for defects even when the product was made in accordance with standard practice and existing norms, or when it was administratively authorised.

Article 1298

Producers are strictly liable unless they can prove: 1° That they had not released the product; 2°That, considering the circumstances, the defect causing the harm could be considered as inexistent at the time they released the product, or that this defect arose subsequently; 3° That the product was not intended for sale or any form of distribution; [4°That the state of scientific and technical knowledge at the time of release was insufficient to detect the existence of the defect;] 5°Or that the defect is due to the product's compliance with compulsory legislative or regulatory rules.

Producers of components are also not liable if they can prove that the defect can be attributed to the design of the product in which their component was incorporated, or to instructions given by the product's producer

  Producers cannot invoke the exemption provided for by article 1298, 4°when the harm was caused by a component of the human body or by products coming from the human body, or by any health product for human use mentioned by the first Chapter of Title II of the first Book of the fifth Part of the Public Health Code.] Article 1299-1

© Dejean de la Bâtie, 2016 -Grotius-Pothier project Reproduction of this translation is allowed for non-commercial use only and with source reference.

Article 1278

When a tangible asset was harmed, compensation will be equal to either the cost of reparation or to the cost of replacement, whichever is lower. Obsolescence is not taken into account.

When the asset can neither be repaired nor replaced, compensation will be equal to the value of the asset at the time when the court decision was made, in the shape it was in prior to the harm.

If, on the victim's request, the damaged property is not given to the person liable in its current shape, its residual value is deduced from compensation.

Article 1279

If necessary, compensation also covers deprivation from the use of the damaged property, operating losses, or any other harm.

Subsection 3. Rules specific to compensation for losses resulting from damage to the environment Subsection 4. Rules specific to compensation for losses resulting from delay in payment of sums of money Article 1280

Compensation for the loss resulting from delay in the payment of a sum of money consists in an order to pay the interest at the rate set by legislation.

These damages are due with no requirements for the creditor to justify that they suffered any loss. They are due only from the date of service of legal notice, except where legislation provides that they accrue by operation of the law.

A creditor to whom his debtor's delay caused a further loss may recover damages distinct from his award of interest for delay in payment.

SECTION 3 -Contracts about compensation for loss Subsection 1. Contracts regarding liability exclusion or limitation Article 1281

Contracts aiming at excluding or limiting liability are valid in principle, for contractual matters as well as for extra-contractual matters.

Provisions aiming at dismissing or limiting liability for defective products are forbidden and deemed inexistent.

Article 1299-2

Unless producers committed a fault, their liability based on this section ceases ten years after the release of the product that caused the harm, unless the victim started a suit during this time.

Article 1299-3

Compensation suits based on the provisions of this section become prescribed after three years from the moment the claimant knew or should have known about the harm, the defect and the producer's identity.

Article 1299-4

The provisions in this section do not prevent the victims of harm from invoking their rights arising from contractual liability. They also do not prevent victims from invoking the provisions of this chapter regarding extra-contractual liability, or any special liability regime, so long as they are based on a different ground of liability than this section.

Producers remain liable for the consequences of their fault and of the fault of the persons whose actions they are liable for.


Claire Goursaud
email: claire.goursaud@insa-lyon.fr

Yuqi Mo
email: mo.yuqi@insa-lyon.fr

Random Unslotted Time-Frequency ALOHA: Theory and Application to IoT UNB Networks

The ALOHA protocol is regaining interest in the context of the Internet of Things (IoT), especially for Ultra Narrow Band (UNB) signals. In this case, the classical assumption of channelization is not verified anymore, modifying the ALOHA performances. Indeed, UNB signals suffer from a lack of precision on the actual transmission carrier frequency, leading to a behavior similar to a frequency unslotted random access. In this paper, the success probability and throughput of ALOHA is generalized to further describe frequency-unslotted systems such as UNB. The main contribution of this paper is the derivation of a generalized expression of the throughput for the random time-frequency ALOHA systems. Besides, this study permits to highlight the duality of ALOHA in time and frequency domain.

I. INTRODUCTION

Internet of Things (IoT) is a new concept gaining more and more interest from researchers and industries [START_REF] Stankovic | Research directions for the Internet of Things[END_REF] [START_REF]The Internet of Things[END_REF]. The objective is to provide connectivity to a very large number of heterogeneous devices such as RFID tags, actuators, and sensors. The collected data can then be exploited in several application areas, such as smart cities, home automation, industrial applications, among others. The main common feature between these devices is that, contrary to human-driven communications, object-driven communications usually require low transmission rates. Indeed these objects occasionally send and/or receive a small amount of data.

For the communication point of view, the main challenge is not the individual rate, but rather having a very low energy consumption. With contemporary transmission schemes such as LTE [START_REF] Biral | The challenges of M2M massive access in wireless cellular networks[END_REF], the nodes' emission power can be reduced by using small cells, but this leads to a high number of base stations with small load, but high infrastructure costs. Another option is to consider other transmission schemes that provide sufficient coverage for limited emission power. During the last decade, 4 dedicated transmission schemes have emerged for the uplink of such Low Power Wide Area Networks (LPWAN). They are based on new radio technologies [START_REF] Goursaud | Dedicated networks for IoT: PHY / MAC state of the art and challenges[END_REF]: LoRa (Long Range), Weigthless, RPMA (Random Phase Multiple Access) and UNB-based (Ultra Narrow Band). LoRa and RPMA use spread spectrum techniques, UNB occupies a very narrow band (typically 100 Hz), while Weigthless proposes either UNB or spread spectrum techniques depending on the targeted application. The main advantage of UNB transmissions is that it does not rely on access protocols to handle multiple access [START_REF] Mo | Optimization of the predefined number of replications in a Ultra Narrow Band based IoT network[END_REF], while limited signaling is an important issue for IoT networks [START_REF] Jain | Machine type communications in 3GPP systems[END_REF]. Indeed, the hand-shake protocol overheads and the payload packets have almost the same size due to the small amount of data to transfer. Thus, if a reservation packet is successfully received, there is a high probability that a data packet sent in the same conditions would be correctly received. Therefore, the hand-shake protocol overhead should be avoided. Furthermore, it was shown in [START_REF] Wang | Energy-Efficient Random Access for Machineto-Machine (M2M) Communications[END_REF] that the subdivision of the available frequency band, leading to smaller transmission bandwidth, permits to reduce the overall M2M network energy consumption. Thus, it is expected that UNB will be more energy efficient than spread spectrum techniques. This paper focuses on the case of UNB.

In addition to energy, the node cost is an important issue for IoT deployment. Simple modulation schemes such as BPSK (with data rate of 100 bps) are compliant with UNB. A limited node cost means that the use of off the shelf low cost oscillators for the carrier generation is mandatory. This leads to the main specificity of UNB transmissions: the carrier generation imprecision. As a matter of fact, no oscillator is perfect. This lack of precision leads to an offset between the targeted frequency and the actual generated one. For UNB systems, the uncertainty is higher than the signal bandwidth. At such scale, the network performance is insensitive to an additional increase of the carrier frequency uncertainty. This allows the use of unprecise oscillators, without any loss of performances. Nonetheless, with any uncertainty above the signal bandwidth, contrarily to narrow band systems, it is not possible to obtain non-overlapping frequency channels with reasonable frequential guard intervals [START_REF] Do | On the benefits of random FDMA schemes in ultra narrow band networks[END_REF]. Therefore, classical transmission schemes implicitly based on frequency channelization [START_REF] Sen | Analysis of slotted ALOHA with multipacket messages in clustered surveillance networks[END_REF] are not pertinent anymore. This leads to a new paradigm for the multiple access scheme.

In this paper, we take into account the carrier frequency uncertainty to evaluate the ALOHA protocol behavior. The Base Station (BS) collects signals that occur randomly, generated in an unslotted way both in the time and the frequency domains (RFTMA: Random Frequency and Time Multiple Access). This can be viewed as a more general case of the well-known ALOHA medium access [START_REF] Abramson | THE ALOHA SYSTEM: Another alternative for computer communications[END_REF]. The main difference is that, for UNB systems, interference occurs only in a portion of the frequency band. In this case, the interference cannot be easily processed, neither by transmitter cooperation or signal postprocessing at the receiver as in literature [START_REF] Zheng | Rethinking the Role of Interference in Wireless Networks[END_REF]. The goal of this paper is to introduce this new RFTMA scheme and provide its theoretical characterization.

Previous works on ALOHA-based schemes do not consider full and continuous randomness in frequency domain. Usually, the band is divided into several perfectly orthogonal channels, and frequency hopping (FH) is considered [START_REF] Hamdi | Packet-error probability analysis for FH-CDMA unslotted packet networks[END_REF]. However, few works consider the frequency offset. In [START_REF] Herrero | Generalized analytical framework for the performance assessment of slotted random access protocols[END_REF], its impact on the relative phase between considered symbols is taken into account. In [START_REF] Crozier | Performance of 2-dimensional sloppy-slotted ALOHA random access signaling[END_REF], the authors consider that most of the frequency errors are within the signal bandwidth, thus they do not consider UNB. In [START_REF] Modi | ALOHA for Wireless Sensor Networks with Random Frequency Offsets[END_REF], the authors consider K nodes with random frequency offsets relative to a common carrier frequency, and focus on the use of a wide-band receiver to take advantage of the jitters. We complement these studies by considering a uniform and continuous randomness of the carrier frequencies to characterize an UNB-based ALOHA uplink.

The organization of the paper is as follows. In Section II we define a general model of the network. In Section III we develop a theoretical analysis of UNB success probability. In Section IV we present numerical results and applications for a realistic UNB networks. Section V concludes the paper.

II. UNB SYSTEM MODEL

We consider a BS that collects data from N + 1 nodes. The nodes are uniformly deployed in the cell, which can be modeled by a Poisson point process.

All nodes are considered to be perceived with the same power level at the BS. This case corresponds to the worst one. Indeed, when colliding packets are received at the same power level, both are lost. On the contrary, if the received powers are sufficiently unbalanced, the capture effect may permit to decode at least the strongest one [START_REF] Roberts | ALOHA packet system with and without slots and capture[END_REF]. We thus characterize in this paper the lower bound of the network success probability.

Assume that each node transmits a message of duration τ seconds, at a randomly chosen time, every D p seconds on average. Thus, p t = τ /D p is the expected temporal generation rate for a single user. Besides, transmissions are performed inside a dedicated band, which has bandwidth B. One may note that, each transmission occupies a bandwidth b which represents a very small fraction p f = b/B of the total channel bandwidth B. Thus, p f is the frequential occupancy ratio for a single active user. These notations are reported in Table I.

From the base-station point of view, the dedicated band contains from time to time, transmitted ultra narrow signals at random carrier frequencies. For each detected transmission, the BS extracts the signal at the estimated frequency of interest and decodes the packet. Such a detection and estimation can be done as described in a Sigfox patent [START_REF] Sigfox | Method for searching for a useful signal in a multiplexing band[END_REF]. They are currently deployed in their commercial network, and do not fall in the scope of this paper. An example of channel occupancy realization is presented on Fig. 1. We can observe the sparse time-frequency occupations of signals. The three highest peaks (in red) correspond to transmissions that experienced collisions, while the others are interference-free. One may note that the widths (both in time and frequency domain) differ among the collision peaks. This is due to the frequency-unslotted and time-unslotted selection, which induce partial collision in time and frequency domain.

Finally, one may note that a key advantage of UNB is that the noise floor N 0 = k • T • b (with k Boltzmann constant, and T the temperature in Kelvin) which is proportionnal to the bandwidth is highly reduced compared to classical systems. This permits to cover an exceptionally large area with each BS (up to 50km). As noise is negligible, interference is the main limitation of the system performance. We consider in this paper, the interference due to the collisions issuing from uncontrolled random medium access, both in time and frequency domain.

III. ERROR PROBABILITY THEORETICAL ANALYSIS

In the original ALOHA protocol, all packets are sent on the same frequency channel. Thus, only the transmission time is random.

If the total number of generated packets (retransmissions included) in the network is Poisson distributed, and if even partial-time collision leads to the packet loss, it was shown in [START_REF] Abramson | THE ALOHA SYSTEM: Another alternative for computer communications[END_REF], that the probability of success of a given user is:

P 1D = e -αtGt (1)
with α t = 1 for time-slotted ALOHA (TS), α t = 2 for timeunslotted ALOHA (TU), and G t = N p t the average number of packets generated by all the other users during the considered packet transmission. In addition, it was shown in [START_REF] Choudhury | Diversity ALOHA -A random access scheme for satellite communications[END_REF], that for frequency hopping systems with 1 p f = B/b frequency channels having the same bandwidth, eq.( 1) becomes

P FH = e -αtp f Gt (2)
In the following, we extend these equations to the unslotted frequency selection, and provide a new expression that describes all cases.

Theorem 1. The ALOHA success probability with slotted or unslotted time, and slotted or unslotted frequency, and uniform distribution in time and frequency domain, is given by:

P 2D = e -αtα f G tf (3)
with

G tf = N p t p f = N τ b D p B , and
α f = 2 (resp.1)
for frequency-unslotted (FU) (resp. frequency slotted (FS)) ALOHA.

Proof. For the slotted frequency selection case, i.e., for α f = 1, Theorem 1 simplifies to eq.( 2).

The proof now focuses on the unslotted frequency selection α f = 2. To do so, we need to consider the pulse shaping filter of UNB signals. The steep filter edges that can be observed in Fig. 1, allow us to approximate the transmitted signal spectrum by a rectangular function with bandwidth b centered at the actual carrier frequency. We use this model to derive the theoretical throughput.

Any desired packet will be correctly received if it does not experience collision. A collision occurs when there is an overlap both in time and frequency domain between the desired and an interfering packet. In the frequency domain, this implies that their respective frequencies f 0 and f i verify:

|f 0 -f i | ≤ b.
We consider that the transmitting nodes' carrier frequencies are uniformly distributed in the total available bandwidth B. Thus, in the continuous case, spectral collision occurs when at least one undesired user chooses a frequency in the vulnerable band [f 0 -b, f 0 + b]. This happens with probability 2 • b/B. Thus, the spectral collision probability for a unique potential interferer is α f • p f with α f = 2. Therefore the probability that a packet is successfully received, given k additionnal simultaneous transmissions is given by:

P s/k = (1 -α f p f ) k . ( 4
)
As the total number of packets are generated according to a Poisson point process with rate G t , the probability to have k users transmitting during (partly or totally) the desired packet is (αtGt)

k k!
• e -αtGt . Therefore, the probability of success for the targeted packet is :

P s = ∞ k=0 P s/k • (α t G t ) k k! • e -αtGt (5) = e -αtGt • ∞ k=0 (α t G t • (1 -α f p f )) k k! = e -αtGt • e (αtGt•(1-α f p f )) = e -αtα f G tf .
This completes the proof.

In practice, the network behaves as if we use the classical ALOHA protocol restricted to the p f portion of the undesired users. As a consequence, the number of packets created during a time period and in the frequency collision interval is also Poisson distributed, with an average generation rate of potential time-colliding packets G tf = G t • p f . Corollary 1. Time and frequency domain are dual in the ALOHA protocol.

The relevance of Corollary 1 lies on the fact that the time (α t and p t ) and frequency (α f and p f ) parameters can be indifferently interchanged in eq.(3).

IV. GENERALIZED ALOHA EXPRESSION VALIDATION AND RESULTS

A. Validation

We present simulation results for the frequency-unslotted case (α f = 2). To be as realistic as possible, we consider typical values used in SigFox's network. Transmissions are performed in the 868 MHz ISM band, and each individual signal occupies a bandwidth b = 116 Hz during τ = 2s. With current available good oscillators (0.25 ppm) [START_REF] Perrott | A Temperature-to-Digital Converter for a MEMS-Based Programmable Oscillator With < ±0.5 -ppm Frequency Stability and < 1 -ps Integrated Jitter[END_REF], the frequency uncertainty (217 Hz) would be close to the signal bandwidth. So, with cheaper oscillators, (more suitable for massive deployment), the uncertainty is bigger than the signal bandwidth. These features comply with the UNB definition.

Based on these realistics values, Monte Carlo simulations were conducted for both time-slotted (α t = 1) and unslotted (α t = 2) case. Besides, we tested two kind of signal shapes, depending on the considered filter. The first one is the rectangular filter: this exactly corresponds to the case treated in the theoretical section. The second one is a realistic filter as used in SigFox (with a realistic signal spectrum shape obtained by a 1255th order lowpass FIR filter, with a 100 Hz cut-off As expected, we can first note that the error probability increases with the number of users, while it decreases with the available bandwidth and the temporal generation period. More importantly, we verify on all these figures the accuracy of the theoretical analysis. Indeed, both theoretical expression and rectangular model simulation curves coincide, for the timeslotted and time-unslotted cases. Besides, the realistic filter simulation also seems to perfectly coincide. However, if we get more precision (zoom on Fig. 2), we can observe that the rectangular model actually overestimate a little the real case. This is due to the fact that the rectangular model slightly overestimates the interference level in the collision band.

To conclude, the proposed theoretical eq.( 3) provides a tight upperbound on the realistic frequency-unslotted case.

B. Throughput derivation and analysis

To further analyse the network behavior, we use eq.( 3) to deduce the throughput of the network T , as a function of G tf the average total load per time-frequency resource:

T = G tf e -αtα f G tf = N p t p f e -N αtptα f p f (6)
We plot on Fig. 5 the throughput as a function of the load G tf . As time and frequency can be independantly slotted or unslotted, there are 4 possible scenarios : frequencyslotted (resp. unslotted) time-slotted : FSTS (resp. FUTS), and frequency-slotted (resp. unslotted) time-unslotted : FSTU (resp. FUTU). We can first note that the FSTS case is the best one as the time-frequency space is divided into orthogonal channels, thus minimizing the probability of collision. On the opposite, FUTU is the worst one as partial overlapping is possible both in time and frequency domain. Finally, FSTU and FUTS coincide due to the time-frequency duality as stated in Corollary (1). Thus, there are in fact only 3 distinct curves, according to the possible values of the product α t • α f . One may note that the time-frequency duality brings flexibility. Indeed, if both precise frequency and timing are difficult to handle simultaneously, FSTS can not be achieved. The duality between FSTU and FUTS allows to decide which constraint to relax, independantly of the impact on the performances, but based for example, on the network deployment cost. Furthermore, the best achievable load can be evaluated. We derive eq.( 6) with respect to G tf . The maximum throughput is obtained for G tf = 1 αtα f , and can be expressed :

T = 1 α t • α f • e -1 . (7)
As can be verified on Fig. 5, there are in practice 3 optimum throughputs depending on the values of α f and α t : T = 1/e (for FSTS), 1/2e (obtained for either FSTU or FUTS), or 1/4e (for FUTU).

Finally, the constraint for the optimum throughput can be written as

N B = D p α t • α f • τ • b . (8)
So, for a given configuration induced by the targeted application and the targeted rate (i.e. τ , D p and b fixed), and a given configuration for α t • α f , the ratio N/B is a constant. It is thus straightforward to dimension the network transmission band for a targeted number of users.

V. CONCLUSION

In this paper, we have evaluated the extension of the ALOHA scheme to the case of time-frequency random access, as experienced for example with UNB transmissions in IoT networks. We have derived and validated the theoretical expression of the success probability for all the configurations (time slotted or unslotted, and frequency slotted or unslotted). We have exploited the theoretical expression to derive the throughput. Besides, we have also highlighted that frequency randomness and time randomness identically affect the throughput, and that they can be interchanged without loss of performances. This duality is promising as it opens the field to transposition of all existing results on ALOHA to unslottedfrequency networks.

Fig. 1 .

 1 Fig. 1. Example of a time-frequency UNB realization, for b = 116Hz, W = 12000Hz, τ = 2s, during 100s.

Fig. 2 .

 2 Fig. 2. Simulated and theoretical success probability as a function of the number of undesired users for the time slotted and unslotted case, for b = 116Hz, W = 12000Hz, τ = 2s, and Dp = 12 hours.

Fig. 3 .

 3 Fig. 3. Simulated and theoretical success probability as a function of the total availaible bandwidth B for the time slotted and unslotted case, for b = 116Hz, N = 1000000, τ = 2s, and Dp = 12 hours.

Fig. 4 .

 4 Fig. 4. Simulated and theoretical success probability as a function of the temporal generation period Dp for the time slotted and unslotted case, for b = 116Hz, B = 12000Hz, τ = 2s, and N = 100000.

Fig. 5 .

 5 Fig. 5. Network throughput as a function of the load for all αt, α f .

TABLE I TABLE OF NOTATIONS

 IOF

	N	Number of potentially interfering nodes
	τ	Packet duration
	Dp	Average transmission period
	b	Signal spectrum occupancy
	B	Bandwidth of the available channel
	pt	Expected temporal generation rate = τ Dp
	p f	Frequential occupancy ratio
		= b B
	αt	=	1, for time-slotted ALOHA 2, for time-unslotted ALOHA
	α f	=	1, for frequency-slotted ALOHA 2, for frequency-unslotted ALOHA
	G tf	Time-frequency load in the network
		= N ptp f
	f

i Carrier frequency of user i ∈ {1; N }


Yuqi Mo
email: mo.yuqi@insa-lyon.fr

Claire Goursaud
email: claire.goursaud@insa-lyon.fr

Jean-Marie Gorce
email: jean-marie.gorce@insa-lyon.fr

Theoretical Analysis of UNB-based IoT Networks with Path Loss and Random Spectrum Access

UNB is dedicated to long range and low power transmission in IoT networks. The channel access is Random-FTMA, where nodes select their time and frequency in a random and continuous way. This randomness leads to a new behavior of the interference which has not been theoretically analyzed yet, when considering the pathloss of nodes located randomly in an area. In this paper, in order to quantify the system performance, we derive and exploit a theoretical expression of the packet error rate in a UNB based IoT network, when taking into account both interference due to the spectral randomness and path loss due to the propagation.

I. INTRODUCTION

IoT (Internet of things) refer to networks of physical devices that have communications capabilities. It is expected that, by 2020, there will be 20 billions of communicating objects in the world [START_REF] Gubbi | Internet of Things (IoT): A vision, architectural elements, and future directions[END_REF]. They will be designed to support many sorts of applications such as smart metering, smart vehicles, surveillance, etc. [START_REF] Xu | Internet of Things in industries: A survey[END_REF]. To do so, these objects collect and transfer information. One may note that most of these nodes have only a small amount of data to transfer. Thus, a single collecting point can serve, from a capacity point of view, a high number of nodes. For low density deployments, this permits a coverage of tens of kilometers. Nonetheless, the majority of devices are battery-based. As the battery maintenance is to be avoid due to the high number of nodes, a low energy consumption is also a strong requirement for IoT. Thus the challenges of IoT networks are to connect a high number of devices, to be able to manage a bursty access to the medium, to cover a wide area, while keeping it low cost and energy efficient.

To meet these specific demands of IoT networks, new technologies dedicated to LPWAN (Low Power Wide Area Network) have recently emerged on the market [START_REF] Goursaud | Dedicated networks for IoT: PHY / MAC state of the art and challenges[END_REF], such as: LoRa [4] (promoted by the LoRa Alliance), RPMA [5] (developed and exploited by Ingenu), and UNB (Ultra Narrow Band, developed and exploited by SigFox) [6]. Interestingly, two opposite approaches have been exploited to perform the targeted long range transmission. Spreading spectrum is considered in LoRa and RPMA, while UNB permits to transmit messages by using extreme narrow band signals (100-200 Hz, about one thousand times smaller than the whole channel bandwidth). Key advantages of UNB are its simplicity and its bigger practical coverage than the others [START_REF] Goursaud | Dedicated networks for IoT: PHY / MAC state of the art and challenges[END_REF]. We thus focus on UNB in this paper.

The natural channel access scheme of UNB is Random-FTMA (Random Frequency and Time Multiple Access). Every node can access the channel at their will, in an unslotted random way, both in time and in frequency domain [START_REF] Goursaud | Random Unslotted Time-Frequency ALOHA: Theory and Application to IoT UNB Networks[END_REF]. On one hand, the advantage of this uncontrolled access scheme is that the channel reservation of transmission is saved. On the other hand, this randomness in spectrum and time does not prevent from potential interference. In particular, contrarily to traditionally defined transmissions where channelization can be performed, there can be partial spectral conflicts in UNB based networks. This specificity of the interference level has been detailed and modeled in [START_REF] Do | Interference modelling and analysis of random fdma schemes in ultra narrow band networks[END_REF], while its impact on the system performance has been estimated in [START_REF] Do | On the benefits of Random-FDMA schemes in ultra narrow band networks[END_REF]. However, these studies considered a perfect channel case.

In practice, the received signal is attenuated, especially for such long range transmissions. According to Shannon [START_REF] Shannon | A Mathematical Theory of Communication[END_REF], path loss is the main contributor of the received signal power attenuation, which depends mainly on the distance between the transmitter and the receiver. For a network where numerous nodes are randomly located, stochastic geometry has been developed as an analytic tool to model the interference, and to quantify the network performance [START_REF] Haenggi | Stochastic geometry and random graphs for the analysis and design of wireless networks[END_REF]. For example, stochastic geometry has been used to analyze systems such as simple random access in ad hoc networks (ALOHA) [START_REF] Baccelli | An Aloha protocol for multihop mobile wireless networks[END_REF], dense IEEE 802.11 networks [START_REF] Nguyen | A Stochastic Geometry Analysis of Dense IEEE 802.11 Networks[END_REF], multi-tier and cognitive cellular wireless networks [START_REF] Lee | Interference and Outage in Poisson Cognitive Networks[END_REF], [START_REF] Sakr | Cognitive and Energy Harvesting-Based D2D Communication in Cellular Networks: Stochastic Geometry Modeling and Analysis[END_REF], [START_REF] Elsawy | Stochastic Geometry for Modeling, Analysis, and Design of Multi-Tier and Cognitive Cellular Wireless Networks: A Survey[END_REF].

All these works of stochastic geometry are interesting, because they provide us interference models for different kinds of networks. Nevertheless, as all these studies are based on channelization, they do not consider that interference could come from partial collisions in the frequency domain. A way to introduce this characteristic in the stochastic geometry model is to consider a marked spatial Poisson Point Process (PPP), where the mark models the residual proportion of interference which is perceived on the desired transmission. However, due to the shape of this rejection coefficient function, such approach leads to untractable expressions.

We present in this paper another way to compute the Packet Error Probability (PER). The main contribution is to provide an analytic expression of a UNB-based system performance, when considering both the path loss effect and the specific behavior of the interference in the spectral domain.

The rest of the paper is constructed as follows: in Section II we model the network and state all the hypothesis. In Section III, we derive theoretically the expression of packet error rate in UNB network. Then, in Section IV, we validate our analysis and present numerical results. Finally, Section V concludes this paper.

II. MODELING AND ASSUMPTIONS

A. Network topology

We consider a cellular topology, in which nodes only communicate with the Base Stations (BS). As the interference (so the performance) is linked to the BS range, for the sake of simplification, we focus on the behavior of a unique cell. The BS defines the cell center. We suppose that nodes are uniformly distributed in a disk form area, whose range is [r max , r min ], as shown in Fig. 1. Nodes are positioned randomly inside the cell, but no nodes are placed in the inner disk of the cell.

The BS is considered to always be in reception mode, and to scan the whole bandwidth for potential transmissions (as done in SigFox network). At any given moment, we denote by N the number of active nodes actually transmitting. We assume that all these N nodes emit with the same emission power. For each detected transmission (even simultaneous ones), the BS processes the incoming message(s).

We assume that transmissions are performed with the UNB modulation technique. Binary data are broadcast with a BPSK modulation at a very low rate (e.g. R b = 100 bps). The transmitted signal thus occupies a very narrow band (e.g. about b = 100 Hz). Transmissions are realized at a randomly chosen (in an unslotted way) carrier frequency in a much larger band B (typically 192 kHz). The specificity of UNB comes from the inherent lack of precision of any oscillator. Indeed, offset always exists between the targeted frequency and the actual one. But, when the frequency uncertainty is higher than the signal bandwidth, the system is said to be UNB. In this case, contrarily to narrow band systems, it is not possible to obtain non-overlapping frequency channels with reasonable guard intervals [START_REF] Do | On the benefits of Random-FDMA schemes in ultra narrow band networks[END_REF]. This leads to a new paradigm for the multiple access scheme and the interference modeling, as channelization is not pertinent anymore for UNB.

As each node randomly chooses its transmission frequency, the uncontrolled medium access may lead to interference or packet collisions between the active users, especially when

B. Interference model

Without loss of generality, we consider that node 1 is the desired node, while all the others are called interfering nodes as they can collide with the desired node.

The received signal at the base-station is the sum of all signals transmitted by each node in the active set A and can be expressed as:

r(t) = h 1 (t) * g(f 1 , t) * s 1 (t) + y∈{A-1} h y (t) * g(f y , t) * s y (t) + w(t) (1)
where, for any active node i ∈ A, s i (t) is the BPSK symbols vector; g(f i , t) is the transmission FIR filter centered on the randomly chosen carrier frequency f i ; h i (t) is the channel response; * denotes the convolution operator, and w(t) is an additive white Gaussian noise. As the signal is ultra narrow, the noise contribution is very low, and can be neglected compared to interference. At the BS side, after filtering at the desired user carrier frequency f 1 , the signal becomes:

r (f 1 , t) = g(f 1 , t) * r(t) (2) = h 1 • g(f 1 , t) * g(f 1 , t) * s 1 (t) + y∈{A-1} h y • g(f y , t) * g(f 1 , t) * s y (t)
We can first extract the received power corresponding to the signal of the desired node 1 :

P s = h 1 • β(f 1 , f 1 ) • P 0 (3)
with β(f 1 , f 1 ) the filter auto correlation coefficient as it considers the transmission and reception filters centered at the same carrier frequency. Similarly, the interference power I y caused by a single interferer on the desired signal follows:

I y = h y • β(f 1 , f y ) • P 0 (4)
with β(f 1 , f y ) the rejection coefficient as the reception filter is centered on a different frequency than the transmission filter. This rejection coefficient quantifies the portion of emitted signal which is kept after filtering. It depends on the frequency spacing between the two carrier frequencies ∆f = |f 1 -f y | as presented in Fig. 2. We can observe that all the interference is kept (β(f 1 , f y ) = 1) when ∆f = 0 while it tends to 0 as the interferer frequency moves away from the desired user one. The exact expression of the rejection coefficient depends on the filter shape. When considering the filters used in SigFox transmissions, the interference power can be approximated by a zero-mean Gaussian function, depending on the frequency difference ∆f :

β (∆f ) = 150 σ √ 2π exp -∆f 2 2σ 2
(5) with σ = 60 [START_REF] Do | Interference modelling and analysis of random fdma schemes in ultra narrow band networks[END_REF].

We will use this approximation to evaluate the interference contribution of each interfering node.

III. THEORETICAL ANALYSIS

In this section, we derive the theoretical expression of the PER (Packet Error Rate) when considering path loss and spectral interference. As we neglect the noise contribution compared to the interference, a packet is considered to be successfully transmitted if its SIR (Signal to Interference Ratio) is above a predefined threshold. We thus aim at expressing the PER as a function of following parameters: the whole available bandwidth B; the SIR threshold S above which a packet is considered successful; the range of the considered cell r max , the exclusion radius r min ; and the number of active nodes N .

Rigorously, packet loss can be due to a unique interferer, or the aggregation of several interferers. However, in practice, the second case is negligible compared to the first one. We thus consider the case where one node interrupts the desired one. So, we first consider the case of 2 active users before generalizing it to N active users.

We first express the SIR in the 2 users case. We consider that the propagation model is free space, and packets from all nodes are sent at the same time, with the same emission power and antenna gain. We can thus express the received power of any transmitting node as a function of the node distance and the reference power P 0 observed at reference distance r 0 . Distance between desired node (resp. interfering node) and BS is r 1 (resp. r 2 ), as illustrated in Fig. 1. Thus, the SIR of the desired node can be expressed as :

SIR = P 0 r0 r1 2 P 0 r0 r2 2 β (∆f ) = r 2 r 1 2 1 β (∆f ) (6)
If SIR of a given packet is smaller than the threshold S, this packet is considered lost. We have SIR ≤ S when :

r 2 ≤ r 1 Sβ (∆f ) (7)
We decompose (7) by using the law of total probability by conditioning on ∆f . Hence, the PER becomes :

P ER = B 0 P (SIR ≤ S|∆f ) P (∆f ) d∆f (8) = B 0 P r 2 ≤ r 1 Sβ (∆f )|∆f P (∆f ) d∆f
First of all, we derive P (∆f ). Desired and interfering nodes choose their frequencies f 1 and f 2 randomly and uniformly in [0, B]. Thus, their spectral difference ∆f follows the following probability distribution function:

P (∆f ) = =    2 B 1 - ∆f B for ∆f ∈ [0, B] 0 elsewhere (9)
Secondly, we calculate P r 2 ≤ r 1 Sβ (∆f )|∆f . We further decompose it by conditioning on ∆f and r 1 . So we obtain:

P r 2 ≤ r 1 Sβ (∆f )|∆f (10)
= rmax rmin P r 2 ≤ r 1 Sβ (∆f )|∆f ∩ r 1 P (r 1 ) dr 1 P (r) presents the probability of choosing a random position (radius r) in a disk form area of [r min , r max ] :

P (r) =    2r r 2 max -r 2 min = 2r k 2 for r ∈ [r min , r max ] 0 elsewhere (11)
with k 2 = r 2 max -r 2 min . P r 2 ≤ r 1 Sβ (∆f )|∆f ∩ r 1 represents the probability that r 2 is smaller than one specific value, in the considered area. As r 2 is constrained to be in the range [r min , r max ], 3 cases must be considered to correctly define the integration bounds, depending on the range value of r 1 Sβ (∆f ):

P r 2 ≤ r 1 Sβ (∆f )|∆f ∩ r 1 =                    rmin rmin P (r 2 ) dr 2 if r 1 Sβ (∆f ) ≤ r min , r1 √ Sβ(∆f ) rmin P (r 2 ) dr 2 if r min ≤ r 1 Sβ (∆f ) ≤ r max rmax rmin P (r 2 ) dr 2 if r 1 Sβ (∆f ) ≥ r max =          0 if r 1 Sβ (∆f ) ≤ r min , r 1 2 Sβ (∆f ) -r min 2 k 2 if r min ≤ r 1 Sβ (∆f ) ≤ r max 1 if r 1 Sβ (∆f ) ≥ r max (12)
The first line in (12) (resp third line) renders the fact that, the targeted range threshold is so small (resp. so high) that, in the targeted area, no node can be (resp. all the nodes are) closer. The second line is the intermediate case, and its value depends on the desired node location.

With the knowledge of ( 11) and ( 12), we can compute P r 2 ≤ r 1 Sβ (∆f )|∆f as defined in [START_REF] Cardieri | Modeling interference in wireless ad hoc networks[END_REF]. However, as the conditions in (12) depends on both r 1 and ∆f , the expression is computed differently depending on the range of ∆f . We have distinguished 4 cases based on the value of Sβ (∆f ) which characterizes the relative positioning of the desired and interfering node:

1) case 1: Sβ (∆f ) ≤ rmin rmax . This case is directly related to the first line in [START_REF] Haenggi | Stochastic geometry and random graphs for the analysis and design of wireless networks[END_REF]. Due to inequality transitivity, the r 1 Sβ (∆f ) ≤ r max Sβ (∆f ) ≤ r min condition and the [START_REF] Goursaud | Random Unslotted Time-Frequency ALOHA: Theory and Application to IoT UNB Networks[END_REF] one imply that r 2 ≤ r min . This is not achievable, as there is no node inside the exclusion area of radius r min . Thus, for such ∆f , it is not possible to find a node close enough to the BS to create sufficient interference. Thus, P r 2 ≤ r 1 Sβ (∆f )|∆f is null.

2) case 2: rmin rmax ≤ Sβ (∆f ) ≤ 1. This corresponds to the case where the interfering node must be closer to the receiver than the desired node (but not in the exclusion area). In this case, the left inequality in the second line in ( 12) is verified as

r min ≤ r 1 Sβ (∆f ) is equivalent to rmin rmax ≤ rmin r1 ≤ Sβ (∆f ) ≤ 1. Hence, all desired nodes such that r 1 ∈ rmin √ Sβ(∆f )
, r max contribute to this case.

3) case 3: 1 ≤ Sβ (∆f ) ≤ rmax rmin . Contrarily to the second case, the interfering node can be further from the receiver than the desired node. In this case, nodes with a distance

r 1 ∈ r min , rmax √ Sβ(∆f )
verify the right inequality in the second line of [START_REF] Haenggi | Stochastic geometry and random graphs for the analysis and design of wireless networks[END_REF], while those such that

r 1 ∈ rmax √ Sβ(∆f )
, r max verify the third line. 4) case 4: Sβ (∆f ) ≥ rmax rmin . In this last case, even the closest desired user is interfered by any node in the cell. This is directly related to the third line in [START_REF] Haenggi | Stochastic geometry and random graphs for the analysis and design of wireless networks[END_REF], which leads to r2 r1 ≤ rmax rmin ≤ Sβ (∆f ). So P r 2 ≤ r 1 Sβ (∆f )|∆f = 1. Accordingly, we can compute the integral of all the four cases:

P r2 ≤ r1 Sβ (∆f )|∆f (13) =                                        0 if Sβ (∆f ) ≤ r min rmax , rmax r min √ Sβ(∆f ) r1 2 Sβ (∆f ) -rmin 2 k 2 2r1 k 2 dr1 if r min rmax ≤ Sβ (∆f ) ≤ 1 rmax √ Sβ(∆f ) r min r1 2 Sβ (∆f ) -rmin 2 k 2 2r1 k 2 dr1 + rmax rmax √ Sβ(∆f ) 1 * 2r1 k 2 dr1 if 1 ≤ Sβ (∆f ) ≤ rmax r min 1 if Sβ (∆f ) ≥ rmax r min =                        0 if Sβ (∆f ) ≤ r min rmax , a Sβ (∆f ) + bSβ (∆f ) + c if r min rmax ≤ Sβ (∆f ) ≤ 1 d Sβ (∆f ) + eSβ (∆f ) + f if 1 ≤ Sβ (∆f ) ≤ rmax r min 1 if Sβ (∆f ) ≥ rmax r min (14)
with the following constants :

a = r min 4 2k 4 , d = r 4 max 2k 4 - r 2 min r 2 max k 4 - r 2 max k 2 b = r max 4 2k 4 , e = - r 4 min 2k 4 c = - r max 2 r min 2 k 4 , f = r 4 min k 4 + r 2 max k 2
With the above expressions, we can finally derive [START_REF] Do | On the benefits of Random-FDMA schemes in ultra narrow band networks[END_REF]. We first express the integral bounds according to the cases defined in [START_REF] Nguyen | A Stochastic Geometry Analysis of Dense IEEE 802.11 Networks[END_REF]. First,

Sβ (∆f ) ≤ rmin rmax is equivalent to β -1 rmin rmax 2 1 S
≤ ∆f . As the maximum value of ∆f is B, the lower bound must be constrained by B. Thus, the integral bounds for this case are:

b 1 = min β -1 rmax rmin 2 1 S , B and b 0 = B.
Secondly, the same principle applies to

rmin rmax ≤ Sβ (∆f ) ≤ 1 , which leads to β -1 1 S ≤ ∆f ≤ β -1 rmin rmax 2 1
S . The integral bounds for this part are:

b 1 and b 2 = min β -1 1 S , B . Similarly, for 1 ≤ Sβ (∆f ) ≤ rmax rmin , leads to β -1 rmax rmin 2 1 S ≤ ∆f ≤ β -1 1 S . The integral bounds are thus: b 2 and b 3 = min β -1 rmax rmin 2 1 S , B . Finally, Sβ (∆f ) ≥ rmax rmin is equivalent to 0 ≤ ∆f ≤ β -1 rmax rmin 2 1 S . Thus b 4 = 0. One may note that β (∆f ) ∈ [0, 1]. Thus, b 3 exists only if rmax rmin 2 ≤ S.
If not, b 3 would be null, and the last term of integral would be null too.

As a consequence, the integral of ( 9) can be expressed as :

P ER = B 0 P r 2 ≤ r 1 Sβ (∆f )|∆f P (∆f ) d∆f = 0 + b 1 b 2 a SIR th β (∆f ) + bSIR th β (∆f ) + c P (∆f ) d∆f + b 2 b 3 d SIR th β (∆f ) + eSIR th β (∆f ) + f P (∆f ) d∆f + b 3 b 4 1 * P (∆f ) d∆f (15)
The final expression of this PER is given in [START_REF] Sakr | Cognitive and Energy Harvesting-Based D2D Communication in Cellular Networks: Stochastic Geometry Modeling and Analysis[END_REF]. It represents the PER when there are 2 active nodes. We now extend it to N active nodes. When there are N active nodes, any of the N -1 nodes (i.e. all nodes except the desired node) can be an interfering node. Accordingly, the success probability of the desired node, is that it will not be interrupted by any of N -1 nodes. Consequently, the packet error rate is given by:

P ER (N ) = 1 -(1 -P ER) N -1 (17)

IV. VALIDATION AND NUMERICAL RESULTS

A. Validation

In this section, we present simulation results based on realistic network configurations (based on SigFox one). We compare them to our theoretical values, to validate the expression of P ER (N ) [START_REF] Elsawy | Stochastic Geometry for Modeling, Analysis, and Design of Multi-Tier and Cognitive Cellular Wireless Networks: A Survey[END_REF]. We consider the following key parameters: number of active nodes N , bandwidth B, range of transmission area [r min , r max ], and the threshold of signal-interferenceratio S. For a better understanding, we provide here the unit of S in dB. But in the theoretical expression, the linear value of S must be used (10 10 ). The simulation results are obtained with the discrete-event simulator WSNet [18].

P ER = 2 B    aσ 2 π S150 erfi ∆f √ 2σ 2 + 75bS erf ∆f √ 2σ 2 + c∆f - aσ 3 √ 2π BS150 exp ∆f 2 2σ 2 + bS150σ B √ 2π exp ∆f 2 2σ 2 - c (∆f ) 2 2B    b 1 b 2 (16) + 2 B    dσ 2 π S150 erfi ∆f √ 2σ 2 + 75eS erf ∆f √ 2σ 2 + f ∆f - dσ 3 √ 2π BS150 exp ∆f 2 2σ 2 + eS150σ B √ 2π exp ∆f 2 2σ 2 - f (∆f ) 2 2B    b 2 b 3 + 2 B ∆f - ∆f 2
S
We first provide an intermediate validation of our analysis, by comparing [START_REF] Nguyen | A Stochastic Geometry Analysis of Dense IEEE 802.11 Networks[END_REF] with simulation behavior in Fig. 3. We can observe the four parts of the expression (in blue), which define in turn the final expression (red curve). Besides, we can verify that the simulation values (red triangle) are well predicted by the theory.

To finalize this validation, we present on Fig. 456, the evolution of P ER (N ) by varying B, and along with another different parameter for each figure. From a global point of view, we can observe that simulation results match well with theoretical ones. Therefore, we can deduce that the formula (17) is validated.

B. Performances analysis

We now analyze these figures more precisely. In Fig. 4, the area ranges are set to [30,1000]. We can see that PER decreases when B increases. Indeed, as there are more available transmission resources, there are less risks that nodes would collide. In addition, PER increases with N . When numerous actives nodes transmit at the same time, the chance that their frequencies fall into the interfering zone gets higher.

Furthermore, we verify that PER increases when the threshold S becomes bigger, as shown in Fig. 5. When the success criteria becomes stricter, nodes have less chances to attain S, so the network performance becomes worse. Fig. 6 shows that when the maximum range r max changes from 60 to 1000, we have a little bit more errors. Meanwhile, when r max changes from 1000 to 10 6 , their PER evolution totally overlap. It indicates that, when the area is already large, the range does not have many impact on network performance.

To sum up, the usual performance statements are verified: more network load induces more errors, such as small bandwidth and too many nodes; a more strict SIR threshold leads to a higher PER; while the influence of area range to network performance depends on the scale.

C. Results Exploitation

In this section, we exploit the theoretical expression of PER to find out the maximum capacity. This parameter is defined in this study by the maximum number of active nodes N that the network can support simultaneously, while maintaining a targeted PER. We have reported on Fig. 7, the capacity when the PER is targeted to be smaller than 0.1. We can observe that with a larger bandwidth, the system can contain more nodes; nevertheless, with a stricter signal interference ratio threshold, less active nodes can be served. More importantly, we can observe that the capacity increases linearly with the available bandwidth. It is thus easy to scale the bandwidth in accordance to the number of nodes to serve, when keeping the same targeted SIR. However, the theoretical expression still provides an efficient tool for any SIR.

V. CONCLUSION

In this paper, we have theoretically evaluated the packet error rate of a UNB based IoT network, by considering both interference due to spectral randomness, and pathloss. We have derived the expression of PER and validated it by simulations based on realistic configurations. We have evaluated the network performance when varying several parameters: active nodes N , bandwidth B, threshold of signal-interference-ratio S, and the range of transmission area [r min , r max ]. One may note that this analysis can be the theoretical basis for further studies such as the interference cancellation.

Fig. 1 .

 1 Fig. 1. Illustration of network topology: area range is [r min , rmax], red point is the desired node, at a distance of r 1 ; blue point is interfering node, at a distance of r 2

Fig. 2 .

 2 Fig. 2. Interference behavior as a function of the frequency spacing ∆f between desired node and interfering node

2B b 3 b 4 Fig. 3 .

 343 Fig. 3. Segmentation of the four parts of P r 2 ≤ r 1 Sβ (∆f )|∆f in (14), with SN Rth = 10 dB, BW = 12000 Hz, r min = 30 m, and rmax = 60 m.

Fig. 4 .

 4 Fig. 4. PER vs bandwidth B, with different number of active nodes N , rmax = 1000 m, r min = 30 m, S = 6.8 dB.

Fig. 5 .

 5 Fig. 5. PER vs bandwidth B, with different signal-interference-ratio threshold S dB, N = 50, rmax = 1000 m, r min = 30 m.

Fig. 6 .

 6 Fig. 6. PER vs bandwidth B, with different maximum range of area rmax, N = 50, r min = 30 m, S = 6.8 dB.

Fig. 7 .

 7 Fig. 7. Maximum capacity N vs bandwidth B, with different signalinterference-ratio threshold S dB, and PER, r min = 30 m, rmax = 60 m.

ACKNOWLEDGMENT

The authors would like to thank Christophe Fourtet (Sigfox company) for providing realistic UNB network parameters in this study.


Valerio Basile
email: v.basile@rug.nl

Johan Bos
email: johan.bos@rug.nl

Kilian Evang
email: k.evang@rug.nl

Noortje Venhuizen
email: n.j.venhuizen@rug.nl

Developing a large semantically annotated corpus

Keywords: annotation, semantics, discourse

de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Various semantically annotated corpora of reasonable size exist nowadays, including PropBank [START_REF] Palmer | The proposition bank: An annotated corpus of semantic roles[END_REF], FrameNet [START_REF] Baker | The Berkeley FrameNet project[END_REF], and the Penn Discourse TreeBank [START_REF] Prasad | The Penn Discourse TreeBank as a resource for natural language generation[END_REF]. However, efforts that combine various levels of annotation into one formalism are rare. One example is OntoNotes [START_REF] Hovy | OntoNotes: the 90% solution[END_REF], a resource comprising syntax (Penn Treebank style), predicateargument structure (based on PropBank), word senses, and co-reference. Yet, all of the aforementioned resources lack a level of formally grounded "deep" semantic representation that combines various layers of semantic annotation.

We describe an ongoing effort to fill this gap: the Groningen Meaning Bank (GMB) project. The aim of this project is to provide a large collection of semantically annotated English texts with formal rather than shallow semantics. One of its objectives is to integrate phenomena into a single formalism, instead of covering single phenomena in an isolated way. This will provide a better handle on explaining dependencies between various ambiguous linguistic phenomena. Another objective is to annotate texts, not isolated sentences (as in ordinary treebanks), which allows us to deal with, for example, ambiguities on the sentence level that require the discourse context for resolving them.

Manually annotating a comprehensive corpus with gold-standard semantic representations is obviously a hard and time-consuming task. Therefore, we use a sophisticated bootstrapping approach. We employ existing NLP tools to get a reasonable approximation of the target annotations to start with. Then we gather and apply Bits of Wisdom: pieces of information coming from both experts (linguists) and crowd sourcing methods that help us in deciding how to resolve ambiguities. This will allow us to improve our data-driven NLP machinery and produce improved annotations -and so on.

This paper is organised as follows. First we outline our annotation method, which we dub human-aided ma-chine annotation. We illustrate the pipeline of NLP components that we employ, and give some background on the formal semantic representations that we produce. Then we show how we apply Bits of Wisdom, BOWs for short, to the annotation and present the first results.

Human-Aided Machine Annotation

Our corpus annotation method combines conventional approaches with modern techniques. We use stand-off annotations (based on off-set character positions in the raw text) and automatically produce the annotations from the raw texts to be annotated. This is done by a fairly traditional pipeline of NLP components. The output of the final component is a meaning representation based on Discourse Representation Theory with rhetorical relations, our target annotation for texts. At certain points in the pipeline, the intermediate result may be adjusted by Bits of Wisdom, the working of which is explained in detail in section 3.

Levels of Annotation

The pipeline used for constructing meaning representations is a cascade of various components, most of them provided by the C&C tools and Boxer [START_REF] Curran | Linguistically Motivated Large-Scale NLP with C&C and Boxer[END_REF]. This software, trained and developed on the Penn Treebank, shows high coverage for texts in the newswire domain (up to 98%), is robust and fast, and therefore suitable for producing approximations to gold-standard annotations. The pipeline consists of the following steps:

1. token/sentence boundary detection 2. part-of-speech tagging 3. named entity tagging 4. supertagging (with CCG categories) 5. parsing (syntactic analysis) 6. boxing (semantic analysis) Penn [START_REF] Miltsakaki | The Penn Discourse Treebank[END_REF]) named entity ENE [START_REF] Sekine | Extended named entity hierarchy[END_REF] named(X,'John','Person') word senses WordNet (Fellbaum, 1998) pred(X,loon,n,2) thematic roles VerbNet [START_REF] Kipper | A large-scale classification of English verbs[END_REF] rel(E,X,'Agent') syntax CCG [START_REF] Steedman | The Syntactic Process[END_REF]) semantics DRT [START_REF] Kamp | From Discourse to Logic; An Introduction to Modeltheoretic Semantics of Natural Language, Formal Logic and DRT[END_REF] drs(Referents,Conditions) rhetorical relations SDRT [START_REF] Asher | Reference to Abstract Objects in Discourse[END_REF] rel(DRS1,DRS2,because)

The semantic analysis is currently carried out by Boxer and will be extended with various external resolution components. These include: scope resolution, anaphora resolution, presupposition projection, assigning thematic roles, word sense disambiguation, discourse segmentation and determining rhetorical relations.

Table 1 shows how the various levels of annotation are integrated in the Groningen Meaning Bank. The linguistic levels of the GMB are, in order of analysis depth: part of speech tags (Penn tagset); named entities (roughly based on [START_REF] Sekine | Extended named entity hierarchy[END_REF]); word senses (WordNet); thematic roles (VerbNet); syntactic structure (Combinatory Categorial Grammar, CCG); semantic representations, including events and tense, and rhetorical relations (DRT). Even though we talk about different levels here, they are all connected to each other and integrated in a single formalism: Discourse Representation Theory.

Discourse Representation Structures

Discourse Representation Theory (DRT) [START_REF] Kamp | From Discourse to Logic; An Introduction to Modeltheoretic Semantics of Natural Language, Formal Logic and DRT[END_REF]) is a widely accepted theory of meaning representation. As the goal of the Groningen Meaning Bank is to provide deep semantic annotations, DRT is in particular suitable because it is designed to incorporate various linguistic phenomena, including the interpretation of pronouns, temporal expressions and plural entities. DRT is based around Discourse Representation Structures (DRSs), which are recursive formal meaning structures that have a model-theoretic interpretation. This interpretation can be given directly [START_REF] Kamp | From Discourse to Logic; An Introduction to Modeltheoretic Semantics of Natural Language, Formal Logic and DRT[END_REF] or via a translation into first-order logic [START_REF] Muskens | Combining Montague Semantics and Discourse Representation[END_REF]. This property is not only interesting from a theoretical point of view, but also from a practical perspective, because it permits the use of efficient existing inference engines (e.g. theorem provers and model builders) developed by the automated deduction community.

The aim of the Groningen Meaning Bank is to provide fully resolved semantic representations. This inspires the adoption of well-known extensions to the standard theory of DRT to include neo-Davidsonian events (with VerbNet roles [START_REF] Kipper | A large-scale classification of English verbs[END_REF]), presuppositions (van der Sandt, 1992) and rhetorical relations [START_REF] Asher | Reference to Abstract Objects in Discourse[END_REF]. The latter feature is part and parcel of SDRT (Segmented Discourse Representation Theory), a theory that enriches DRT's semantics with a precise dynamic semantics for rhetorical relations [START_REF] Asher | Logics of conversation[END_REF]. In the GMB, rhetorical relations are represented as relations between DRSs, which may in turn be embedded in another DRS. We dis-tinguish different types of rhetorical relations (both coordinating and subordinating relations), and separate the presuppositions of the discourse from the asserted content. Future work may include the representation of ambiguities by adding some underspecification mechanisms to the formalism.

The trademark of the Groningen Meaning Bank is that it provides the information of various layers of meaning within a single representation format: a DRS. Figure 1 shows the semantic representation of an example text from the GMB.

Bits of Wisdom

In order to improve and refine the analysis provided by the tools, their output (which takes the form of text and XML files in various formats) may be adjusted by human expert annotators, crowd sourcing activities or external software components. To prevent these various sources of annotation from stepping on each other's toes, we defined the basic unit of annotation input as what we call a Bit of Wisdom (BOW). A BOW is represented as a database entry that gives advice on a particular linguistic interpretation decision. BOWs can inform where a sentence boundary occurs, where a token starts and ends, what part of speech is assigned to a token, what thematic role is played in an event, what sense of a word is meant, and so on.

Types of BOWs

We distinguish different types of BOWs, each type with a fixed set of integer or string arguments that contain the actual information. Currently, we work with two types of BOWs:

(i) boundary(n, level , polarity) where n is a character offset into the text, level ∈{token,sentence} and polarity ∈ {+, -}, meaning that there is a/there is no token/sentence boundary at n, (ii) tag(l, r, type, tag) where l, r are character offsets, type is a tag type such as POS, word sense, NE or supertag, and tag is a tag of that tag type, meaning that the token between these offsets should carry this tag.

Bits of Wisdom may be applied at different points in the pipeline, e.g., after sentence and token boundary detection in the case of type (i), or after the relevant tagging step in the case of type (ii). Applying a BOW amounts to making the minimal set of changes to the annotation required to make it consistent with the BOW while keeping the overall annotation well-formed. This involves, for example, securing a complete tokenization of the text, avoiding multiple tags of the same type for the same token and creating a token boundary whenever a sentence boundary occurs, or removing a sentence boundary in case a token boundary is removed. In the unusual event that a BOW cannot be applied because, for example, it refers to a token that does not exist anymore due to changed boundaries, the BOW is ignored.

We expect that most of the automatically generated syntactic analyses can be corrected by applying BOWs with the correct lexical category, because CCG is a lexicalised theory of grammar.

Sources of BOWs

There are currently two sources of BOWs, namely a group of experts editing the annotation in a wiki-like fashion through a Web-based tool called GMB Explorer, and a group of non-experts that provide information for the lower levels of annotation decisions (e.g. word senses) by way of a 'Game with a Purpose', called Wordrobe. In this way, we gather bits of both expert wisdom and collective wisdom. A third source of BOWs in future work will be the use of external components, like state-of-the-art WSD, co-reference resolution or semantic role labelling systems.

The first source of BOWs, the GMB Explorer, allows users to make changes to the annotation, such as splitting a token in two, merging an erroneously split sentence back together, or correcting a tag on a token (Basile et al., forthcoming 2012). All changes are stored as BOWs, so they are independent of the previous state of the annotation and can be applied selectively and in any order. We currently apply all expert BOWs for a particular document each time the pipeline is run on that document, in chronological order with the most recent BOW last. This way, experts can freely edit the latest state of the annotation, and the complexity of the BOW application process is linear in the number of BOWs. GMB Explorer makes the collaborative annotation process transparent through global and per-document newsfeeds of BOWs, similar to the "recent changes" and "history" feature of wikis. This is exemplified in Figure 2.

The second source for BOWs, the game with a purpose, is similar to successful initiatives like Phrase Detectives [START_REF] Chamberlain | Addressing the Resource Bottleneck to Create Large-Scale Annotated Texts[END_REF] and Jeux de Mots [START_REF] Artignan | Multiscale visual analysis of lexical networks[END_REF]. It collects answers from non-expert players to problems such as choosing the sense of a word in a given context from a list of definitions. Once the same answer has been given by a significant majority of the players, it is likely to be correct and a BOW is automatically generated.

Judging BOWs

It is important to stress that a single BOW isn't necessarily correct, but rather gives an opinion or prediction of a certain linguistic interpretation -albeit from an authoritative source, thus with a relatively high reliability. As a consequence of the defeasibility of BOWs, a particular annotation choice can be supported by some Bits of Wisdom, and rejected by others, which may arise from various sources with different reliabilities. Whenever there is disagreement between BOWs, a judge component decides how to interpret them. The decisions of the judge may be consistent with the respective NLP component's output, or conflict with it. In the latter case the output is adjusted. This process takes place directly after each component in the pipeline, so subsequent components take advantage of previous decisions, producing higher quality output. The judge component that resolves possible conflicts between different types of BOWs is currently as simple as always applying expert BOWs in the end, giving them priority. We will be investigating other judging methods as we add external software components as a third source of BOWs.

Constructing the GMB

Workflow

In the previous sections we have introduced various techniques used for creating the Groningen Meaning Bank. Combining these techniques results in the worflow depicted in Figure 3. It consists of the NLP pipeline, interleaved with judge components, and a feedback loop. The feedback loop works as follows: the intermediate (e.g. tokens, tags, parse tree) and final outputs (DRS) of the pipeline are visualized in Explorer and used for generating questions for Wordrobe. The BOWs provided by these two sources, as well as annotations created by external tools, are stored in the database and are then judged and applied in subsequent runs of the pipeline. Currently, BOWs can be applied at two points in de pipeline, namely after the token/sentence boundary detector and after the tagging of POS, named entities and CCG categories. The process is orchestrated by the tool GNU make and a daemon process that schedules the reprocessing of individual documents as new BOWs are added to the database.

Data

We believe that a semantically annotated corpus would be extremely valuable for data-driven semantic analysis and future developments in computational semantics, in the same way that treebanks have played a crucial role for the development of robust parsers. Therefore, a corpus developed primarily for research purposes ought to be widely and easily available to researchers in the field. As a consequence, the GMB only comprises texts whose distribution isn't subject to copyright restrictions. Included are newswire texts from Voice of America, country descrip-tions from the CIA Factbook, a collection of texts from the open ANC [START_REF] Ide | The manually annotated sub-corpus: a community resource for and by the people[END_REF]) and Aesop's fables. All of these documents are in the public domain.

Size and quality are factors that influence the usefulness of annotated resources. Since one of the things we have in mind is the use of statistical techniques in natural-language generation, the corpus should be sufficiently large. We aim to provide a trade-off between quality and quantity, with a process that increases the size of the corpus and improves the annotation accuracy in each stable release of the GMB.

Availability

A first release comprising 1,000 texts with 4,239 sentences and 82,752 tokens is available at http://gmb.let.rug.nl.

A further 70K texts with more than 1M sentences and 31M tokens has so far been collected, ready for inclusion in future releases. The current development version contains 5,000 texts and is accessible online through GMB Explorer, where registered users can contribute BOWs. We plan to release a first version of the annotation game Wordrobe within the coming months.

Conclusions

In this paper we introduced human-aided machine annotation, a method for developing a large semantically annotated corpus, as applied in the Groningen Meaning Bank. The method uses state-of-the art NLP tools in combination with human input in the form of Bits of Wisdom.

As the goal of the Groningen Meaning Bank is to create a gold standard for meaning representations, future work will include quantifying the degree to which the gold standard is reached for a certain representation in terms of the Bits of Wisdom applied to the representation. Our working hypothesis is that the more BOWs are applied, the closer the representation comes to a gold standard.

Figure 1 :

 1 Figure1: DRS for the text "The Cayman Islands were colonized from Jamaica by the British during the 18th and 19th centuries and were administered by Jamaica after 1863. In 1959, the islands became a territory within the Federation of the West Indies. When the Federation dissolved in 1962, the Cayman Islands chose to remain a British dependency." (document 55/0688 in the GMB)

Figure 2 :Figure 3 :

 23 Figure 2: Global newsfeed of recently added BOWs in GMB Explorer.

Table 1 :

 1 Integrating linguistic information in the GMB

	Level	Source	DRS encoding example
	POS tag