Manuel Gil Pérez
email: mgilperez@um.es

Félix Gómez Mármol
email: felix.gomez-marmol@neclab.eu

Gregorio Martínez Pérez
email: gregorio@um.es

Antonio F Gómez Skarmeta

Mobility in Collaborative Alert Systems: Building Trust through Reputation

Keywords: Alert Systems, Mobility, Collaboration, Trust, Reputation

Collaborative Intrusion Detection Networks (CIDN) are usually composed by a set of nodes working together to detect distributed intrusions that cannot be easily recognized with traditional intrusion detection architectures. In this approach every node could potentially collaborate to provide its vision of the system and report the alarms being detected at the network, service and/or application levels. This approach includes considering mobile nodes that will be entering and leaving the network in an ad hoc manner. However, for this alert information to be useful in the context of CIDN networks, certain trust and reputation mechanisms determining the credibility of a particular mobile node, and the alerts it provides, are needed. This is the main objective of this paper, where an inter-domain trust and reputation model, together with an architecture for inter-domain collaboration, are presented with the main aim of improving the detection accuracy in CIDN systems while users move from one security domain to another.

Introduction

The open nature of mobile networks has promoted in recent years a high mobility of users among heterogeneous wireless networks, in which they can join to gain access. For example, students, teachers and research staff of a university can benefit of this mobility service in their academic campus without interceding in their wireless connectivity. They can in turn join other networks of the system later, thereby creating a distributed chain of interactions where they can enter and participate in each of those security domains that form the network.

Mobility of users represents a more global and new way of operation, but also introduces some challenges have to be tackled to control and, as a main goal, avoid their possible disruptive behaviors. Current and existing works measure and quantify the trustworthiness of users based on their reputation [START_REF] Michiardi | CORE: A collaborative reputation mechanism to enforce node cooperation in mobile ad hoc networks[END_REF][START_REF] Srinivasan | On trust establishment in mobile ad-hoc networks, chapter Reputation and Trust-based Systems for Ad Hoc and Sensor Networks[END_REF].

That is, they estimate how good users are according to previous experiences or interactions they have had with the system in the past.

We focus mainly in this paper on controlling what mobile users do when they travel across heterogeneous networks and, specifically, in roaming users who can join and cooperate in the context of collaborative alert systems. These systems are built up from the inspection of a great amount of alerts produced in an individual fashion by each of the Intrusion Detection Systems (IDSs) [START_REF] Vincent Zhou | A survey of coordinated attacks and collaborative intrusion detection[END_REF]. Collaborative alert systems provide the basis for building a global knowledge of alerts, based on the cooperation of all members of the system, to increase the accuracy in detecting distributed threats from a more global point of view.

In this paper we expose a Collaborative Intrusion Detection Network (CIDN) designed to improve the accuracy when detecting distributed intrusions. To this end, a global and common alert system is necessary to achieve a high level overview of the entire system. This provides a way to know and anticipate the diverse actions an attacker can execute to compromise the system. This cooperative knowledge is then built upon a set of alerts exchanged among all the components of the network.

The building of this knowledge implies two kinds of communications with the aim of spreading out and sharing these alerts: an intra-domain exchange of alerts among all the detection units, either Host-based IDSs (HIDSs) or Network-based IDSs (NIDSs), into the same security domain; and an inter-domain communication among varying security domains that comprise the alert system to build the desired high level overview.

In this paper we focus on the process of building a common and cooperative knowledge of alerts among security domains, i.e., inter-domain communications, in the context of highly distributed environments. As detection units, especially mobile HIDSs, which can move from one security domain to others, we also propose a reputation mechanism to compute the trustworthiness each domain has on these detection units, regardless of the domain to whom they belong. Reputation values will give security domains a way of assessing whether any of their detection units exhibits a correct or malicious behavior. Alerts provided from those malicious detection units, probably sent to diminish the performance of the system, or even due to a malfunctioning IDS, can be dropped to avoid confusion to others. This fact will improve the detection accuracy by rejecting false alarms received from malicious entities. Thus, the detection of certain malicious behaviors from roaming users is an essential requirement for the success in detecting distributed attacks.

The remainder of this paper is structured as follows. In Section 2, we motivate the problem under consideration. Then, we formulate in Section 3 the reputation mechanism designed to assess the mobile users' trustworthiness when they move across security domains. Section 4 describes the main components that comprise our system architecture. Next, Section 5 discusses the main related work and, finally, Section 6 remarks the main conclusions and highlights the lines of current and future work.

Design of an inter-domain collaborative alert system

This section describes the problem under consideration, which will be used throughout this paper to introduce and describe later the different components that compose the proposed system architecture.

How these components are distributed, and how they communicate each other, will be the basis for the definition of our inter-domain reputation mechanism. This mechanism aim to improve the detection accuracy in collaborative alert systems while roaming users move from one security domain to another.

As a sample scenario, let us suppose the system architecture depicted in Fig. 1. This example is composed by two different administrative domains, A and B. An administrative domain is managed by a single organizational authority, which consists of a certain number of hosts, e.g., workstations, servers or network devices. Each administrative domain can in turn be split into more than one security domain. For example, the Administrative Domain A in Fig. 1 is split into two interconnected domains, named Domain A 1 and Domain A 2 . Each of them is managed internally by the qualified staff in the security field who defines the security policies, if any, under which the domain is governed.

In the scenario presented in Fig. 1, it is worth mentioning that there is an overlapping between two security domains. This overlapping may however not exist, so both domains would act as two networks totally independent of each other but belonging to the same administrate domain.

Hosts connected to a given security domain can make use of it in several ways. They can vary from the ones installed by the domain's administrators to offer a specific service, e.g., Web servers or printing services, and even specific services to monitor and assess the fulfillment of both internal policies and users' behavior. With regard to the latter, we focus on the use of Intrusion Detection Systems, which enable hosts with detection capabilities to know whether an attacker is exploiting some vulnerability in other system components.

As shown in Fig. 1, some hosts have been labeled according to their skills to detect suspect or malicious activities when taking two different kinds of sources of information: at local host to monitor what is happening inside of it, by making use of a HIDS like the OSSEC tool [START_REF]OSSEC: An open source host intrusion detection system[END_REF]; and globally to inspect every single packet that goes through the network, by using a well-known NIDS such as Snort [START_REF] Sourcefire | Snort: An open source network intrusion prevention and detection system[END_REF].

The distribution of these IDSs is as follows. We assume every NIDS is managed by a domain administrator who will have necessary skills to set it up. As NIDSs are detection units totally dependent of their security domain, they are configured according to the internal network distribution and the services their domain offers. These NIDSs have to be installed and deployed as static elements. That is, NIDSs cannot operate in mobile devices to detect anomalies in more than one security domain. Instead, HIDSs do not undergo this kind of restrictions since they only report malicious activities conducted internally in their device. As a consequence, HIDSs can seamlessly operate in mobile scenarios.

In Fig. 1, it can be seen a mobile HIDS that joins different wireless networks while it moves across security domains. In each of them, this HIDS can voluntarily join and collaborate (or disrupt) with such a domain by sending out alerts generated by it. This mobile HIDS, when joining to a particular domain, can come from another domain and it is not really a newcomer in the system.

Thus, the new security domain has to compute what its reputation value is, without forgetting what other domains think about such a detection unit. The calculation of reputation on mobile HIDSs takes place in a special unit for the domain, named administration unit, possibly the most trustworthy unit thereof.

Next sections detail how reputation values are computed, depending on whether mobile HIDSs are moving from one security domain to another, both belonging to the same administrative domain, or whether these movements imply more than one administrative domain.

Inter-domain reputation system

As stated before, the problem we need to solve here is to assess the trustworthiness of the alerts generated by a mobile HIDS that is traveling across different security domains.

So let HIDS i Ωj 1

denote the i-th HIDS, HIDS i , being currently at domain Ω j1 , regardless the domain it actually belongs to.

When HIDS i Ωj 1

moves from domain Ω j1 to Ω j2 , the latter has to compute the reputation for such a mobile HIDS based upon two main sources of information; namely:

the previous behavior records of HIDS i within domain Ω j2 , if any; and the recommendations provided by other security domains where such HIDS i remained in the past, weighted by the reliability of each of those domains from the perspective of domain Ω j2 .

More formally, the reputation of HIDS i Ωj 1

within the domain Ω j2 , which is represented as Rep Ωj 2 (HIDS i Ωj 1

) ∈ [0, 1], would be computed as follows:

Rep Ωj 2 (HIDS i Ωj 1 ) = α • Rep Ωj 2 (HIDS i Ωj 1 )+ β • n k=1 Rep Ωj k (HIDS i Ωj 1 ) × T Ωj 2 ,Ωj k n k=1 T Ωj 2 ,Ωj k (1)
where α, β ∈ [0, 1] (fulfilling that α + β = 1) represent the weights given to previous experiences of domain Ω j2 with HIDS i (direct experiences), and the recommendations provided by other domains (indirect experiences), respectively. In turn, T Ωj 2 ,Ωj k represents the trustworthiness or reliability on domain Ω j k given by domain Ω j2 .

For the selection of the most appropriate value for the weights α and β, we propose two alternatives: a light but less accurate one; and a more accurate approach though requiring some more computation capabilities.

On one hand, α and β values can be predefined as static ones. That is, when bootstrapping the system, a value like α = 0.7 and β = 0.3, for instance, can be set and never changed along the time. On the other hand, those values could be computed in a dynamic fashion as follows:

α → α Ωj k (HIDS i ) β → β Ωj k (HIDS i ) = 1 -α Ωj k (HIDS i ) (2)
Then, α Ωj k (HIDS i ) would be based on the number of alerts generated by the mobile HIDS i within domain Ω j k , so the more alerts it has generated in the past, the higher the weight domain Ω j k will give to its own experience with regards to HIDS i , in contrast to the weight given to other domains' suggestions. In this sense, the direct experiences of HIDS i within domain Ω j k will have a higher importance as this detection unit collaborates more with this domain rather than the rest. On the contrary, β Ωj k (HIDS i ) will have a higher weight when HIDS i provides more alerts to other domains than this one (indirect experiences).

Additionally, the temporal distribution of the alerts generated by HIDS i could be also taken into consideration in order to compute α Ωj k (HIDS i ). In this way, the most recent alerts will be more significant to represent the current behavior of a mobile HIDS i than the older ones. To this end, domain Ω j k has to assign a higher weight to the former ones as opposed to the weight given to the latter ones.

Thus, the calculation of Rep Ωj k (HIDS i ) in a dynamic fashion provides a new way of tuning the reputation of HIDS i when it joins with domain Ω j k , instead of assigning it a fixed reputation value as if this detection unit was a newcomer in the system. Furthermore, it is worth mentioning that the mechanism for computing the amount of trust deposited by one domain in the recommendations provided by other domain, i.e., T Ωj 1 ,Ωj 2 , will be different depending on whether those two domains Ω j1 and Ω j2 are actually subdomains belonging to the same administrative domain, or they indeed represent different administrative domains.

Thus, if Ω j1 and Ω j2 are subdomains belonging to the same administrative domain, then T Ωj 1 ,Ωj 2 will be, in some certain situations, directly equal to 1. In any case, when computing T Ωj 1 ,Ωj 2 , it will most probably have a higher value if Ω j1 and Ω j2 belong to the same administrative domain than if they do not.

Finally, the reputation of one HIDS, either mobile or not, within a domain is built up based on its behavior when generating alerts. Thus, a HIDS spreading out false or even malicious alerts, will end up having a low reputation and hence its alerts will most probably not be taken into consideration anymore. On the contrary, if the HIDS behaves properly and it is able (or collaborates) to detect critical threats, it will end up being considered as highly trustworthy and its generated alerts will be treated as reliable ones.

Architecture for inter-domain collaboration

This section outlines the proposed system architecture by means of the definition of the main functional blocks each administration unit should support. This description will provide a clear vision and understanding on how the reputation mechanism presented above is integrated in those administration units to manage the reputation values deposited on the mobile HIDSs. Therefore, we also focus in this section on the trust and reputation management to strengthen administration units with this new sort of knowledge.

Main functional blocks

The four functional blocks that constitute a particular administration unit are depicted in Fig. 2. At a glance, we can identify each administration unit providing four main functionalities.

The first three ones (communication interface, intrusion detection engine and reaction system) are explained next, while the module to manage the trust and reputation values of mobile HIDSs is detailed later.

Communication module

The communication interface allows administration units to exchange data in two senses. First, they are capable of requesting reputation data to other security domains about a particular mobile HIDS, when it moves from one of those domains to the current one. Then, the current domain will be able to compute the reputation value of the mobile HIDS according to Equation (1).

Second, administration units will be also able to share the alerts detected by them with the rest of members of their domain. It aims at building a cooperative intra-domain knowledge of alerts, as well as sharing them with other security domains with which they have a close collaboration relationship.

Intrusion detection capabilities

As an administration unit can also offer detection capabilities, like any other detection unit of its domain, it is equipped with an intrusion detection module (first block at the top of Fig. 2 Both approaches are fed with raw data collected from the sources of information the detection unit handles, and with alerts generated by other IDSs of its domain. In the latter case, this module also receives the reputation value this unit has deposited on the one that generated the alert. With this information, this module can decide of using it or not depending on such a reputation value.

Decision and reaction system

This module enables the detection unit with reaction capabilities. It will enforce some security rules in the target system for remediating the damages caused by the unauthorized intrusion, provided this unit has the required credentials to do it. This module will also forward the alert detected by the intrusion detection module, either by the Detection Engine or by the Alert Aggregation & Correlation submodule, with the aim of sharing this knowledge with the rest of members of its community.

Trust and reputation management

An administration unit has to manage the reputation values of all IDSs of its domain, by taking their experiences with the domain in the past, especially those that can move from one security domain to another, i.e., the mobile HIDSs.

Let us suppose the sample scenario presented in Section 2. In such an example, a mobile HIDS joins several security domains and collaborates with them by means of sharing the alerts detected by it. Thus, this mobile HIDS will have a different reputation in each of them depending on its previous interactions with the domain (direct experiences) and past interactions conducted in other domains (indirect experiences), as explained in Section 3. Hence, it is necessary to maintain some historic data in each domain to compute these reputation values.

To that end, the Trust & Reputation Management module of Fig. 2 is required to deploy and maintain a repository for registering all detection units that have collaborated with the current domain. Fig. 3 shows the same scenario presented in Section 2, but extended with the information each administration unit has to maintain internally to compute reputation values. The administration unit of each security domain will then store a list of IDSs, which have had any interaction with the domain before, with the following data for each detection unit:

-MAC address: unique identifier to distinguish this detection unit from the rest. Thus, this unit can be identified through the same MAC address in all the involved domains.

-Number of generated alerts: the amount of alerts is necessary to compute α Ωj k (HIDS i ), as explained in Equation ( 2). -Reputation value: this attribute maintains updated the reputation value the domain has deposited on the current detection unit, which is computed by using Equation [START_REF] Michiardi | CORE: A collaborative reputation mechanism to enforce node cooperation in mobile ad hoc networks[END_REF].

In addition to this information, each administration unit also has to store the trust its domain has on the rest of domains, i.e., T Ωj 1 ,Ωj k from the perspective of domain Ω j1 .

Bearing in mind the sample data shown in Fig. 3, let us suppose the mobile HIDS i is currently operating in domain A 1 , where its reputation is 0.84, and it then moves to the domain A 2 . In this new domain, where the mobile HIDS i had already participated in the past with 22 alerts, it has to compute the new reputation of mobile HIDS i .

By applying Equation ( 1), this reputation value would be as follows:

Rep Ω A 2 (HIDS i Ω A 1 ) = 0, 7 • 0, 73 + 0, 3 • 0, 84 • 1 + 0, 91 • 0, 85 1 + 0, 85 = 0, 77

For this example, we have set static values for the weights on direct and indirect experiences; α = 0.7 and β = 0.3, respectively.

As seen, the new reputation value is slightly higher in domain A 2 than before, from 0.73 to 0.77, since the behavior of such a detection unit in other domains was better than in domain A 2 . Then, the domain A 2 will update the reputation for the mobile HIDS i to this new value.

Following with this example, let us suppose the mobile HIDS i moves now from domain A 2 (where it has a new reputation value of 0.77) to domain B 1 . In this case, the mobile HIDS i travels from one administrative domain to another. The new reputation value of the mobile HIDS i in domain B 1 would be as follows:

Rep Ω B 1 (HIDS i Ω A 2 ) = 0, 7 • 0, 91 + 0, 3 • 0, 84 • 0, 95 + 0, 77 • 0, 88 0, 95 + 0, 88 = 0, 88 Now, the new reputation value is slightly lower (from 0.91 to 0.88) since this detection unit had a worse performance in other different domains.

Related work

Enhancing security in highly distributed environments like mobile ad hoc networks (MANETs) or wireless sensor networks (WSNs) has been a subject of research for a number of years now. Recently, efficient and accurate trust and reputation management [START_REF] Srinivasan | On trust establishment in mobile ad-hoc networks, chapter Reputation and Trust-based Systems for Ad Hoc and Sensor Networks[END_REF][START_REF] Lindsay | Trust establishment in distributed networks: Analysis and modeling[END_REF][START_REF] Fernandez-Gago | A survey on the applicability of trust management systems for wireless sensor networks[END_REF] has arisen as a novel and effective solution for certain security lacking environments.

Several works have been done so far in this field, dealing with MANET networks [START_REF] Michiardi | CORE: A collaborative reputation mechanism to enforce node cooperation in mobile ad hoc networks[END_REF][START_REF] Buchegger | A robust reputation system for P2P and mobile ad-hoc networks[END_REF][START_REF] Omar | Reliable and fully distributed trust model for mobile ad hoc networks[END_REF] and WSNs [START_REF] Chen | Agent-based trust model in wireless sensor networks[END_REF][START_REF] Boukerche | Trust-based security for wireless ad hoc and sensor networks[END_REF][START_REF] Gómez | Providing trust in wireless sensor networks using a bio-inspired technique[END_REF], among many other systems. In this way, for example, [START_REF] Michiardi | CORE: A collaborative reputation mechanism to enforce node cooperation in mobile ad hoc networks[END_REF] presents a collaborative reputation model aimed to work in MANETs in order to prevent selfish behavior of its users. The authors claim that all members have to contribute to the community life in order to be entitled to use its resources.

On the other hand, intrusion detection systems and, more specifically, collaborative intrusion detection networks have drawn as well the attention of a number of researchers and research groups from both academia and industry all around the world. These systems improve the efficiency of intrusion detection by exchanging low-level intrusion alerts between IDSs in order to produce a high level overview of the whole system [START_REF] Vincent Zhou | A survey of coordinated attacks and collaborative intrusion detection[END_REF].

Besides, the combination of trust and reputation management and CIDNs, or rather, the application of the former to the latter, is still at a preliminary stage. Only a few works like [START_REF] Fung | Trust management and admission control for host-based collaborative intrusion detection[END_REF][START_REF] Zhang | Radar: A reputationdriven anomaly detection system for wireless mesh networks[END_REF][START_REF] Rehak | Dynamic information source selection for intrusion detection systems[END_REF] address this issue. The first of them [START_REF] Fung | Trust management and admission control for host-based collaborative intrusion detection[END_REF] proposes a trust-based framework for secure collaboration within a CIDN. In particular, each HIDS assesses how trustworthy other HIDSs are, based on its own experience with them. RADAR, which is presented in [START_REF] Zhang | Radar: A reputationdriven anomaly detection system for wireless mesh networks[END_REF], consists of an anomaly detection system aimed to identify abnormal mesh nodes in wireless mesh networks through a reputation measurement characterizing and quantifying a node's behavior in terms of fine-grained performance metrics of interest. Finally, the authors of [START_REF] Rehak | Dynamic information source selection for intrusion detection systems[END_REF] show a trust-based selection mechanism for choosing the optimal information provider in an intrusion/fraud detection system, which works by analyzing the response of nodes (agents) to a set of prepared challenges inserted into the system.

Nevertheless, to the best of our knowledge, the work hereby presented is one of the first ones in the literature applying a reputation mechanism to assess the trustworthiness of the alerts generated by mobile HIDSs traveling across different domains in the context of collaborative intrusion detection networks.

Conclusion and future work

This paper presents a collaborative alert system where different domains can participate in building a cooperative knowledge of alerts. This fact will improve the accuracy in detecting distributed threats by sharing isolated alerts individually detected, thereby providing a high level overview of the entire system. To provide a better accuracy, the proposed Collaborative Intrusion Detection Network (CIDN) is strengthened with an inter-domain reputation mechanism, which is capable of computing the reputation of mobile HIDSs when they travel across security domains.

As a statement of direction, our intention is to continue working in some aspects that have remained open in this proposal. Among them, we indicate here two open issues in which we are interested: first, how to compute the trustworthiness or reliability one security domain has on another for calculating the reputation of a mobile HIDS; and, second, how a domain can estimate the weights α and β, according to its own experiences with the mobile HIDS and those that are provided by other domains.

Fig. 1 .

 1 Fig. 1. Mobility of a user among security domains

Fig. 2 .

 2 Fig. 2. Internal components deployed by an administration unit

Fig. 3 .

 3 Fig. 3. Inter-domain reputation management for mobile HIDSs

Acknowledgment

This work has been partially supported by the SEMIRAMIS EU-IST project (Secure Management of Information across multiple Stakeholders), with code CIP-ICT PSP-2009-3 250453, within the EC Seventh Framework Programme (FP7), by the Spanish MEC as part of the project TIN2008-06441-C02-02 SEIS-CIENTOS and by a Séneca Foundation grant within the Human Resources Research Training Program 2007 (code 15779/PD/10). Thanks also to the Funding Program for Research Groups of Excellence granted by the Séneca Foundation with code 04552/GERM/06.


Georgios Angelopoulos
email: georgios@mit.edu

Muriel Médard
email: medard@mit.edu

Anantha P Chandrakasan
email: anantha@mit.edu

Energy-Aware Hardware Implementation of Network Coding

Keywords: Network Coding VLSI Implementation, Energy Optimization of Network Coding, Network Coding for Mobile Applications

In the last few years, Network Coding (NC) has been shown to provide several advantages, both in theory and in practice. However, its applicability to battery-operated systems under strict power constraints has not been proven yet, since most implementations are based on high-end CPUs and GPUs. This work represents the first effort to bridge NC theory with real-world, low-power applications. In this paper, we provide a detailed analysis on the energy consumption of NC, based on VLSI design measurements, and an approach for specifying optimal algorithmic parameters, such as field size, minimizing the required energy for both transmission and coding of data. Our custom, energy-aware NC accelerator proves the feasibility of incorporating NC into modern, lowpower systems; the proposed architecture achieves a coding throughput of 80MB/s (60MB/s), while consuming 22uW (12.5mW) for the encoding (decoding) process.

Introduction

Network Coding (NC), initially introduced in 2000 by Ahlswede et al. [START_REF] Ahlswede | Network Information Flow. Information Theory[END_REF], has received extensive research attention in the Information Theory and Networking community. The revolutionary idea of NC is to allow intermediate nodes within a network to mix or code previously received or locally generated packets together and let the final destinations decode the mixtures. Some of the reported advantages of NC are throughput gains, increase in data robustness, security and better utilization of network resources [START_REF] Katti | XORS in the air: practical wireless Network cCoding[END_REF][START_REF] Lun | On coding for reliable communication over packet networks[END_REF][START_REF] Fragouli | Network Coding Fundamentals[END_REF]. However, coding complexity and energy cost should be carefully examined in order to make these advantages practical, especially when low-power applications are considered, such as Body Area Networks (BANs).

In the literature, a few papers deal with implementation issues of NC, and almost all of them use high-performance CPUs or GPUs, focusing on the maximum achievable throughput, without analyzing the energy trade-offs of incorporating NC into a system architecture. For instance, in [START_REF] Wang | How practical is network coding?[END_REF] a 3.6 GHz Xeon Dual-Core processor is used to perform NC, achieving a coding throughput of approximately 5MB/s, while, for similar settings, in [START_REF] Chachulski | Trading structure for randomness in wireless opportunistic routing[END_REF] NC is implemented using a 800MHz Celeron CPU, achieving a throughput of 44MB/s. In addition, in [START_REF] Heide | Network coding for mobile devices -systematic binary random rateless codes[END_REF] a special type of systematic NC over GF [START_REF] Ahlswede | Network Information Flow. Information Theory[END_REF] is implemented, both on a cell phone and a laptop, achieving maximum reported throughput of 40MB/s and 1.5GB/s, respectively. However, the authors do not consider the energy analysis neither of the coding process, nor of the implications that the specific algorithmic parameters may have in the total system's energy; for instance, a possible increase in packet retransmissions due to linear dependent packets. Authors in [START_REF] Li | Parallelized Network Coding with SIMD instruction sets[END_REF][START_REF] Vingelmann | Implementation of Random Linear Network Coding on openGL-enabled graphics cards[END_REF][START_REF] Shojania | Nuclei: GPU-accelerated Many-core Network Coding[END_REF][START_REF] Vingelmann | Implementation of Random Linear Network Coding using NVIDIA's CUDA toolkit[END_REF]] make use of multi-core CPUs and GPUs to speed up both encoding and decoding of NC. While remarkable effort is required to achieve this coding performance, the power budget of these approaches is in the order of 100 to 500W, number which is generally prohibitive for low-power systems. Finally, an iPhone is used as the implementation device in reference [START_REF] Shojania | Random Network Coding on the iPhone: Fact or Fiction?[END_REF] , where a maximum throughput of 420 KB/s is reported, while NC is responsible for approximately 33% of the reduction in the total battery life-time.

Although high-end CPUs and GPUs have been successfully used as platforms for implementing NC in previous works, as more and more mobile devices, sensors and other battery-operated systems are used, the need of a highly efficient and optimized implementation of NC is required. To the best of our knowledge, none of prior works deal with the energy analysis of a custom VLSI implementation of NC. In this paper, we provide a detailed analysis for incorporating NC into a lowpower system architecture, giving insight on the trade-offs between algorithmic complexity, energy consumption and coding performance. We also propose an architecture of a custom accelerator, capable of performing NC while consuming tiny amounts of power, dictated by the strict energy constraints of modern lowpower systems. Some possible target applications of our analysis and design may be low-power wireless sensor and mobile networks. Our energy-scalable, ultra low-power NC accelerator consumes 22uW (12.5mW), achieving a coding throughput of 80MB/s (60MB/s), for the encoding (decoding) process, showing that NC can be incorporated successfully into modern low-power systems.

This work is organized as follows. In Section 2, we briefly describe the encoding and decoding procedure of NC, while in Section 3, we cover in more detail some of the Galois field fundamentals. In Section 4, we present an approach for modeling the required energy of NC based on hardware (VLSI) simulation results and we analyze how different values of algorithmic parameters affect the total system's energy. Finally, in Section 5, we present our implementation's results and in Section 6, conclusions are summarized.

Network Coding Overview

Assume that a node has to transmit n packets, P = [P 1 , . . . , P n ], each of L bits length. If the node uses Random Linear Network Coding (RLNC) [START_REF] Ho | The benefits of coding over routing in a randomized setting[END_REF], it will first create n linear combinations of them, and then will transmit the result of the coding process. More specifically, q consecutive bits in each packet are considered to form a symbol over the field GF(2 q ), resulting in L/q symbols per packet. The node randomly generates n sets of coefficients, C = [C 1 , . . . , C n ], each of them associated with a specific coded packet X i . The coded packets X are generated with a matrix multiplication: X = C * P. As soon as a node has received n linear independent coded packets, it can start the decoding process, which is actually a problem of solving n equations with n unknowns, recovering the original packets.

Operations like addition, multiplication and division over GF are involved in the en-/decoding process. As a result, for an energy efficient implementation of NC, a detailed examination of these operations should be done in advance.

Galois Field Fundamentals

In this Section, we provide a brief description of the most important concepts of Abstract Algebra related to NC. Our description serves only the purpose of explaining the decisions made during the design steps; for a more mathematically rigorous approach readers are referred to Algebra books.

A field F is a set of at least two elements, with the operations ⊗ and * (often called addition and multiplication), satisfying certain properties. One of these properties is that F is closed under the two operations, meaning that when an operation is applied to some elements of F, the result will also be an element of this field. The number of elements in F is called order and, when this number is finite, the field is called finite field, denoted also as Galois field (GF). For any prime number p, it is always defined a GF with order p, represented as GF(p), having exactly p elements: GF(p)={0,1, . . . , p-1}. We can also create a GF(p q ), for any q>0, called extension field of GF(p). The definition of field size is often used to characterize the size of a field, denoted as q, where q = log p p q . Elements from GF(p q ) are usually considered and treated as vectors [a q-1 , . . . , a 0 ] or polynomials of degree at most (q-1) with coefficients from GF(p). Finally, all GFs contain a zero, an identity and a primitive element, and have at least one primitive polynomial of degree q associated with them.

The representation basis of the elements in a field is a crucial aspect, determining the efficiency and complexity of the implementation of different arithmetic operations. There are several representation bases; the more popular among them are the standard (or polynomial) and the normal basis. The standard basis is the set of elements Ω = {1, ω, ω 2 , . . . , ω q-1 }, where ω is a primitive element of the field GF(p q ), while the normal basis is the set Ψ = {ψ, ψ p , ψ p 2 , . . . , ψ p q-1 }, where ψ is a generator of the basis. Although the normal basis is more suitable for multiplying two numbers, we choose for our implementation to work entirely on the standard basis in order to avoid conversions when data are exchanged between the accelerator and other hardware modules, because standard basis represents numbers in the same way as fixed-point representation does.

In general, GFs play an important role in many communication systems, such as FEC and cryptographic schemes. Since digital computing machines use Boolean logic, the binary field GF(2)={0, 1}, and its extension fields GF(2 q ), are widely used, due to the direct map between their elements and the Boolean values. In the rest of this work we consider only binary fields.

Addition over Galois Fields

As mentioned previously, each element from GF(2 q ) can be represented as a q-bit vector or polynomial of degree (q-1). Adding two elements is equivalent of adding the coordinates of each vector, or adding the two polynomials, using GF(2) arithmetic. This means that the implementation of addition over GF(2 q ) corresponds simply to a bit-wise XOR operation. Table 1 summarizes the area, power and delay requirements of a standard (a q-bit carry ripple adder) and a GF adder. In this table, area is calculated as the required number of gates, power is approximated to be analogous to area and delay is considered the maximum time for each operation, assuming that AND, OR and XOR gates have the same area, power and delay.

Multiplication over Galois Fields

Using standard basis representation, multiplication over GF(2 q ) of two elements, b and c, can be computed as: D(x ) = (B(x )C(x )) modp(x), where p(x) is primitive polynomial of the field. As we see, GF multiplication is equivalent of polynomial multiplication followed by polynomial modulo reduction. These two operations can be performed separately, leading to fully parallel, modular and standard multiplication architectures.

In general, there are several ways to implement a GF multiplication and the resulting performance is highly dependent on the underlying hardware platform. In previous implementations of NC, logarithmic look-up tables and iterative approaches have been used because of the CPU-based approaches. In this work, trying to minimize the energy consumption of NC, we use a custom, low-power GF multiplier. A widely used algorithm in cryptographic and error correction applications for GF multiplication is Rijndael's algorithm. Our architecture implements a modified version of this algorithm, computing the product of two elements in one clock cycle and having no pipeline stages. The reason for such a choice is that our design aims an ultra low-power operation; direct implementation of the iterative Rijndael's algorithm would result in approximately q times less critical path delay, but also in larger overall power consumption. Table 1 summarizes area, power and delay requirements of a standard q-bit array and our GF multiplier.

Energy Modeling and Optimization of NC

In the following paragraphs, we try to model the energy consumed during the encoding process and specify optimum algorithmic parameters, such as field size, taking into consideration the total system's energy (the results presented in the following paragraphs have been obtained after modeling every circuit component using Verilog, synthesizing and performing post-layout simulations, with a 65nm TSMC process, using standard VLSI CAD tools, such as SPICE). Our main focus is on the encoding, since NC does not follow the end-to-end coding paradigm; intermediate nodes are allowed to re-encode packets without decoding them first, and only final destination nodes have to decode the mixtures.

The encoding process is equivalent of generating a new packet as a linear combination of the existing blocks, weighted according to some random coefficients. Assume that a source wants to transmit n packets, each of length L bits, using RLNC over GF(2 q ). The required energy per packet for the encoding process is:

E COD = nE LF SR + L q (nE M U LT + (n -1)E ADD ) , (1)
where E M U LT and E ADD is the energy consumed per multiplication and addition, respectively, and E LF SR is the energy consumed for generating a q-bit coefficient using a LFSR (Linear Feedback Shift Register ). In Fig. 1a is shown how the choice of field size affects the energy for each operation. In this comparison, we keep the processing data rate same, since, doubling the field size q results in doubling the critical path delay of the GF multiplier, which is used as the reference time period for our circuits; in other words, the ratio of the number of processed bit per operation over the required time for each operation, remains constant. Furthermore, apart from the processing energy, field size also affects the probability of two coded packets being linearly dependent. It can be shown that the expected number of transmitted packets until receiving n linear independent combinations, using RLNC over GF(2 q ), is given by the following formula:

n = n i=1 1 1 -( 1 2 q ) i .
(

) 2
Now it becomes clear that a small field size lowers the required processing energy but results in extra retransmitted packets, increasing the total system's energy. This trade-off can be further explained by examining the expected total system energy (E T OT ), given by:

E T OT = n(E COD + E T X ) , (3)
where E T X is the transmission energy per packet. In Fig. 1b, the total normalized system energy, including both coding for NC and transmission energy, is plotted, assuming that 8 packets are coded together, each of 1KB length, and a transmission energy per bit of 200pJ/bit [START_REF] Chandrakasan | Ultralow-power electronics for biomedical applications[END_REF]. Examining the plot we confirm that, when a small field size is used, the total system's energy in dominated by the extra RF energy due to packet retransmissions. However, as field size becomes large, increased energy is required for performing the coding process, without significantly affecting the expected number of transmitted packets, resulting in higher system's energy consumption.

5 Energy-Aware NC Accelerator

In the following paragraphs we present the results of our energy-aware VLSI implementation of NC, giving its architecture but not focusing in the low-level, circuit-related details. Given our target low-power applications, the number of packets encoded together is expected to be relatively small; in our analysis, we assume that up to 8 packets can be coded together, each of length 1KB. Based on the analysis of the previous Section, we use GF(2 8 ) arithmetic, since field size of 8 appears to be the optimum operation point. Our NC encoder architecture is shown in Fig. 2. It is a parallel implementation of the encoding process, making use of standard low-power VLSI techniques, such as clock gating, parallelism and voltage scaling, to reduce power consumption and achieve energy scalability. We also design a custom accelerator performing the decoding process. A standard Gauss-Jordan elimination algorithm is implemented, capable of transforming the coefficients' matrix into row echelon form after receiving every packet. The same GF adder and multiplier modules, discussed previously, are used also in the decoder. For calculating the inverse value of an element, look-up tables are used. The reasons for using look-up tables in the inversion and not in the multiplication process are, first, that the multiplication requires look-up tables of q 2 elements and, second, that the GF inversion algorithm is more complex and energy consuming than the multiplication one. Our hardware implementation results, using a TSMC 65nm process, are shown in Table 2 (reported numbers for the NC encoder are post-layout measurements, while for the NC decoder are post-synthesis).

Conclusions

It has been shown that Network Coding can provide several advantages to a network, but it is associated with an extra energy cost. In this paper, we provide an energy analysis of NC, especially useful to power constrained networks.

We answer the question of how much energy is required for incorporating NC into a system architecture, using a custom and optimized implementation. With detailed energy modeling of the required NC operations, based on custom VLSI measurement, we optimize the trade-offs between coding performance, computational complexity and energy consumption. By designing, to the best of our knowledge, the first energy-aware VLSI NC accelerator and specifying optimum algorithmic parameters, we believe that a further step is made to bridge NC with real-world, low-power applications, such as sensor and mobile networks.

Fig. 1 :

 1 Fig.1: a) Energy per operation for different values of q. b) Normalized total system's energy of a node transmitting 8 coded packets, using RLNC over GF(2 q ).

Fig. 2 :

 2 Fig. 2: Block diagram of the NC encoder.

Table 1 :

 1 Comparison between standard and Galois Field arithmetic

	q -bit arithmetic	Area	Power	Delay
	Addition	Standard Galois Field	5q q	5q q	2q + 1 1
	Multiplication	Standard Galois Field	6q 2 -8q 2q 2 + 2q	6q 2 -8q 2q 2 + 2q	3q -2 4q

Table 2 :

 2 Implementation results of our energy-aware, custom NC accelerator.

		NC Encoder	NC Decoder
	Supply Voltage	0.4V	1.0V	1.0V
	Frequency	10 MHz	250 MHz	50 MHz
	Throughput	80 MB/s	2 GB/s	60 MB/s
	Power	22.15 uW	10.98 mW	12.5 mW

Acknowledgment

The authors would like to thank X. Shi, P. Nadeau and A. Paidimarri for useful discussions on Network Coding and RF design. This material is based upon work supported by the Georgia Institute of Technology Under Award Number: 017894-010.


Matthias Barrie

Lieven Tytgat

Vânia Gonçalves

Opher Yaron

Ingrid Moerman

Piet Demeester
email: piet.demeester@intec.ugent.bematthias.barrie

Sofie Pollin

Pieter Ballon

Simon Delaere
email: simon.delaere@vub.ac.besofie.pollin@imec.be

Techno-Economic Evaluation of Cognitive Radio in a Factory Scenario

Keywords: RF sensing, coexistence, cognitive radio, CR, dynamic spectrum access, DSA, business analysis, statistical model, Spectrum Etiquettes for Unlicensed Bands

Wireless applications gradually enter every aspect of our life. Unfortunately, these applications must reuse the same scarce spectrum, resulting in increased interference and limited usability. Cognitive Radio proposes to mitigate this problem by adapting the operational parameters of wireless devices to varying interference conditions. However, it involves an increase in cost. In this paper we examine the economic balance between the added cost and the increased usability in one particular real-life scenario. We focus on the production floor of an industrial installation -where wireless sensors monitor production machinery, and a wireless LAN is used as the data backbone. We examine the effects of implementing dynamic spectrum access by means of ideal RF sensing, and model the benefit in terms of increased reliability and battery lifetime. We estimate the financial cost of interference and the potential gain, and conclude that cognitive radio can bring business gains in real-life applications.

Introduction

Recent advances in microelectronics have enabled the use of wireless communication in virtually every application. As a result, the scarce spectrum is getting crowded with ever more wireless communication devices. Indeed, the need to coexist is aggravated by the fact that different applications use different wireless technologies, which are apriori unaware of each other, and therefore cannot collaborate to best share the scarce spectrum. Dynamic Spectrum Access (DSA) is a class of mechanisms that aim at improving spectrum sharing. DSA adapts actively to the dynamic interference environment, leveraging on a variety of cognitive technologies ranging from spectrum sensing to agile radio.

When considering actual deployment of DSA in real-life, there is a natural technoeconomical tradeoff between benefit and cost. In this paper we focus on a particular scenario to examine this economic balance. We consider the case of an industrial plant, where an IEEE 802.15.4 based wireless sensor network coexists with an IEEE 802.11 wireless LAN in the unlicensed ISM band. Throughout the paper we refer to IEEE 802.11 also with the terms WLAN and WiFi, and to IEEE 802.15.4 also with the terms Zigbee and sensor network. The sensor network monitors and controls the production equipment, while WLAN provides wireless access to the data network of the plant, e.g. to machinery operators that use WLAN equipped portable handheld devices. The common approach is to go to great lengths to avoid interference to the production control, e.g. the ISA100.11a industry standard [START_REF]Wireless systems for industrial automation: Process control and related applications[END_REF]. We propose that a more balanced approach is in place. We suggest that the overall economic value of avoiding interference should be considered, calculating the trade-off between the advantages of the lower interference achieved; and the additional cost incurred.

In the proposed scenario the economical benefit of implementing DSA is in reducing machine failure rate and production disruption. DSA improves the reliability of the sensor network, which brings to faster identification of machine status alerts. Potential added cost is due to the actual implementation cost of the selected solution, increased maintenance, and increased cost of battery replacement due to shortened battery lifetime.

The coexistence of WiFi and Zigbee has been studied extensively from the technological perspective. Petrova et. al. [START_REF] Petrova | Performance Study of IEEE 802.15.4 Using Measurements and Simulations[END_REF] tested experimentally the mutual impacts between IEEE 802.15.4 and IEEE 802.11. They conclude that IEEE 802.15.4 has practically no influence on concurrent IEEE 802.11 communications, while IEEE 802.11 has significant negative effect on IEEE 802.15.4. Muoung et. al. [START_REF] Muoung | 11b Performance Analysis in the Presence of IEEE 802.15.4 Interference[END_REF] calculate mathematically the packet loss rate and throughput of IEEE 802.11b when interfered by IEEE 802.15.4. They show that in the unrealistic worst case, when the distance between the 802.11 receiver and 802.15.4 transmitter is small and the Clear Channel Assessment mechanism (CCA) of each network does not hear the other, performance degradation can be substantial. Pollin et al. [START_REF] Pollin | Bahai: Harmful Coexistence Between 802.15.4 and 802.11: A measurement-based study[END_REF] measure the impact of WiFi on Zigbee and show it is significant. They also show that the CCA of Zigbee can reduce collisions with WiFi, but is too slow to avoid all WiFi traffic. Thonet et al. [START_REF] Thonet | ZigBee -WiFi Coexistence[END_REF] show that in typical residential environments Zigbee is not affected by WiFi, but in the lab, under controlled WiFi traffic loads, Zigbee suffers significant packet-loss when the WiFi duty cycle is above 20%. In summary, it is evident that WiFi has significant impact on Zigbee, while Zigbee has at most very low effect on WiFi.

In order to deal with WiFi interference, various measures have been proposed, focusing on three major domains -Time, Frequency and Space. Space based measures focus on spatial reuse of the spectrum. Frequency based measures focus on optimizing the use of the spectral bands, e.g. channel selection algorithms and multichannel solutions. Time based measures focus on intelligent distribution of message transmissions over time.

In this paper we focus on the Time domain. In order to avoid collisions, we propose to implement CCA by a new, cross-technology sensing engine. This new device is able to detect the presence of signals from different technologies. We examine and compare different options for the deployment of sensing engines. In what follows Alternative 1 is the reference of not using sensing engines at all, Alternative 2 is to use sensing engines only in the Zigbee nodes, Alternative 3 is to deploy sensing engines only in the WiFi devices, and Alternative 4 is to add sensing engines to both the Zigbee nodes and the WiFi devices.

The remainder of this paper is organized as follows: Section 2 introduces the specifics of the factory scenario we consider. In section 3 we determine the technical advantages and disadvantages for using the sensing engine in the different deployment alternatives. In section 4 we model the gains achieved by spectrum sensing versus the incurred costs. We conclude this paper in section 5.

Scenario

In order to gain meaningful insight into the use of cognitive networking indoors, we look at a realistic scenario, for which we can discover accurate data, and make viable assumptions when such data is not available. As mentioned in the Introduction, we focus on a particular scenario of an industrial plant, where an IEEE 802.15.4 based wireless sensor network coexists with an IEEE 802.11 wireless LAN. More specifically, we consider a modern electronics contract manufacturer that operates multiple Surface Mount Technology (SMT) assembly lines. A mid-size manufacturer may operate a production floor with 15 assembly lines in parallel. Each line includes 3-4 robots and one oven, and is constantly monitored by 2 human operators on the production floor.

Each robot contains 2 cameras and 6-7 different ZigBee sensors, while the ovens contain another 10 ZigBee sensors each, bringing the total number of ZigBee sensors throughout the production floor to 600. These sensors form a Zigbee wireless sensor and actuator network (WSAN). They measure the temperature and other parameters of machinery and processes on the assembly line, and transmit it periodically to a central control and monitoring system. This system alerts human operators of various types of malfunctions, e.g. component-feed problems and overheating, which typically happen multiple times every day.

The wireless LAN in the factory is composed of 100 WiFi devices, including access points, laptops, portable terminals and smartphones. For example, each of the operators of the assembly lines has a portable terminal that he uses to control software download to the assembly machines, verify that proper material is loaded in the robots, etc. As presented in the Introduction, the WiFi devices interfere with the ZigBee sensor network. The nature of interference in this case is that ZigBee data may be lost during periods of active WiFi transmissions.

Since the sensors are located to monitor critical parameters in the assembly lines, loss of Zigbee data might lead to severe damage to machinery and significant loss of material. Two types of failure are possible. Major Failures are ones that risk damage to machinery. If, for example, a machine overheats while Zigbee packets are lost, the supervisors will not be alerted in time, which could lead to serious damage to the machine and a full stop of the assembly line until the damage is repaired. This would reduce production output, and decrease revenue as a result. Minor Failures are ones that only risk loss of material and profit. If, for example, one of the SMT component feeders gets jammed, then all products that continue to be produced before the problem is fixed are damaged, and considered lost. In our scenario each assembly line uses $700 worth of materials and produces $300 of profit per hour of uninterrupted operation. We assume that every assembly line develops conditions that, if not detected on time, will cause a Major Failure once every year. We also assume that every assembly line suffers a Minor Failure once every hour. Furthermore, we estimate that an assembly line that suffers a Major Failure will shut down for 24 hours, and the total cost of repair, in labor, equipment and replacement parts, is $10,000. We also estimate that if a Minor Failure occurs while Zigbee packets are lost, it will take additional 30 seconds to detect the failure and stop production.

Due to the substantial opportunity costs and repair costs, it is clear that the factory owner is interested to reduce interference to an acceptable minimum. Therefore, we propose the solution of adding cognitive elements to the wireless devices. These come however at an investment and energy consumption costs that must be balanced with the performance gains they promise to deliver.

Technical Analysis

In our scenario automated control of machinery is achieved through the use of a Zigbee WSAN, and a WiFi WLAN is used to provide wireless access to the administrative data network of the factory. Both Zigbee and WiFi use CCA to sense if the medium is free before transmitting a packet. Although the basic mechanism is identical, the details like bandwidth, sensing time and Rx-Tx turnaround time vary. In particular, as mentioned in the Introduction, Zigbee CCA typically detects WiFi transmissions, but WiFi CCA does not detect Zigbee transmissions.

The sensing engine we propose, which is described in [START_REF]imec Cognitive Reconfigurable Radio Solutions[END_REF], performs crosstechnology Clear Channel Assessment. It can be tuned very quickly to any channel in the ISM band, and then detect any Zigbee or WiFi transmission. Thus, if it is implemented on a Zigbee node, it can also detect WiFi transmissions, and if it is implemented in a WiFi device, it can also detect all Zigbee transmissions across the full WiFi channel. In addition, since it uses dedicated hardware, it helps reducing the Rx-Tx turnaround time significantly.

In a previous paper [START_REF] Tytgat | Simon Techno-economical Viability of Cognitive Solutions for a Factory Scenario[END_REF] we perform a detailed mathematical analysis, using the law of total probability, and derive closed-form formulas for the Packet Error Rate (PER) of the Zigbee network in Alternatives 1, 2 and 3 as defined in the Introduction. For Alternative 1 the packet success rate (1 -PER) is expressed as .

(1)

Where

is the PER of a stand-alone Zigbee network (without the presence of a collocated WiFi network), is the average length of a Zigbee packet, is the CCA time of Zigbee (112µs), is the Rx-to-Tx turnaround time of Zigbee (192µs), and is the average Inter Packet Delay (IPD) of WiFi.

According to measurements presented in [START_REF] Petrova | Performance Study of IEEE 802.15.4 Using Measurements and Simulations[END_REF], and considering that Zigbee sensors send infrequent messages, we approximate by 1. Consequently

In Alternative 2 sensing engines are deployed in all Zigbee nodes, with practical effect of reducing to zero and to , the CCA time of our sensing engine. Substituting in (2) we get

In Alternative 3 sensing engines are deployed in all WiFi nodes. Now WiFi nodes will not start transmission when a Zigbee node transmits, and the result is For example, for 10% traffic load in the WiFi network, the PER in the Zigbee network is estimated at 53%. If sensing engines are deployed only in the Zigbee nodes, this PER reduces slightly, to 46%. If sensing engines are deployed only in the WiFi nodes, the PER in the Zigbee network reduces significantly, to 17%. Furthermore, if now sensing engines are deployed also in the Zigbee nodes, then the PER in the Zigbee network reduces further significantly, to 4%.

Power Consumption. The WiFi nodes are powered either by mains power or rechargeable batteries, therefore their cost of energy is just the actual cost of consumed electricity. WiFi nodes are typically 'On' all the time, in one of three states -Receiving, Sensing (before transmitting) and Transmitting. Typical power consumption in these states, with the sensing engine deployed, is 100mW, 50mW and 1W respectively. A typical average is 300mW, with worst case consumption of approximately 1W. Taking a typical cost of mains power electricity of $0.15 /kWh, we calculate the average total energy cost of the WiFi devices over 5 years at $0.15/kWh * 300mW * 24h/d * 365d/y * 100 * 5 = $197, with a worst case cost of $197 * (1W / 300mW) = $657. Moreover, since WiFi is not interfered by Zigbee, no additional retransmissions occur due to the presence of Zigbee.

We now turn to calculate the power consumption of the Zigbee nodes. We make the following assumptions:

• Each Zigbee sensor performs and transmits measurements once every 10 seconds.

At this duty cycle, the average power consumption of the Zigbee sensor (without the sensing engine) is 2mW. • Average power consumption of a Zigbee radio, when active, is 24mW. Average duration of radio activation for the transmission of one packet, including waiting for and reception of acknowledgement, is 1.6ms. Consequently, the average power consumed by a Zigbee radio when sending one packet per second is 24mW * 1.6ms * 1/s = 38µW. • Average power consumption of the sensing engine, when active, is 50mW. The sensing engine is activated for 80µs prior to the transmission of every packet. Consequently, the average power consumed by the sensing engine when sending one packet per second is 50mW * 80µs * 1/s = 4.0µW.

Consequently, at a worst case of even 20 retransmissions of each packet, the power consumption of the radio and the sensing engine is estimated at (38µW + 4.0µW) * 0.1 * 20 = 84µW. This is just 4.2% of the average Zigbee sensor consumption of 2mW. A typical Zigbee sensor node is powered by two D size Lithium batteries, with the following typical characteristics: voltage 3.6V, capacity 14Ah (or 50Wh). The expected lifetime of the batteries is therefore 50Wh * 2 / 2mW = 50.000h = 5.7y, and even with the sensing engine it stays well above 5 years.

Economical Evaluation

Following the terminology of the technical analysis, we compare the reference Alternative 1, of a factory with standard WiFi and Zigbee networks and no cognitive solutions, to the three alternative set-ups. We seek to point out which of the alternatives would provide the most economical benefit compared to the reference alternative, if at all. We base our calculations on a 5-year period, which is a realistic lifetime of wireless nodes.

Potential Gains of Sensing

Sensing reduces the interference between the ZigBee and WiFi networks. In fact, sensing therefore limits the amount of machinery and assembly line failures, which are caused by late alerting due to interference. The economic gains of sensing are thus derived from the amount of failures (along with their costs and losses) that can be avoided. These failures can, as mentioned in the scenario description, be divided into two groups.

In the absence of any monitoring sensors, Major failures would occur on average once a year on each line. Major failures involve damage to machinery, which according to the Scenario section, over a period of 5 years, would cost $10.000 * 15 * 5 = $750.000 to repair, and would cause loss of profit of $300 * 24 * 15 * 5 = $540.000.

With a total cost of $1.290.000 over 5 years, Major failures represent a very large potential loss for the factory.

Again, in the absence of any monitoring sensors, Minor failures would occur on average once an hour on each line. Minor failures involve assembly of defective products, which according to the Scenario section, over a period of 5 years, would cost $700 / 3600 * 30 *24 * 365 * 15 * 5 = $3.832.500 in lost material, and would cause loss of profit of $300 / 3600 * 30 * 24 * 365 * 15 * 5 = $1.642.500.

With a total cost of $5.475.000 over 5 years, Minor failures represent even a larger potential loss than the Major failures.

In summary, the potential total cost of failures in 5 years time amounts up to $6.765.000. This significant figure is the reason monitoring sensors are indeed deployed in assembly lines and other industrial plants. When alerts are sent and received, human operators can react on time and prevent damage to machines, as well as reduce the quantity of damaged products. However, as demonstrated in the Technical Analysis, interference from the WLAN network in the plant causes some packet loss in the Zigbee network, which may result in loss of important alert messages. This interference can be drastically reduced by the use of spectrum sensing and packet retransmissions.

However, variations in where the sensing engines are deployed (represented by the different Alternatives) and which loads are present in the WiFi network lead to different levels of improvement to the reliability of the Zigbee network. In turn, improved reliability reduces the number of un-alerted failures, and with them the consequent costs.

Cost of Sensing

Additional potential cost, which is associated with sensing, can be attributed to two sources -investment cost and energy cost.

Investment Cost. The additional investment cost comes down to the extra price of a node that is equipped with a sensing engine. The core of this engine is an Application Specific Integrated Circuit (ASIC), which is estimated at $1. Some additional components, e.g. RF front-end and Analog-to-Digital Converter (ADC), are necessary for the implementation of the complete sensing engine. These components are included in WiFi devices and can typically be re-used by the sensing engine, therefore we estimate the cost of one sensing engine for a WiFi device at $1. For ZigBee sensors it is necessary to add these components, and we estimate the total cost of this sensing engine at $10 at the most. Because there are 600 ZigBee nodes and 100 WiFi devices throughout the factory, we estimate the total additional investment in Alternative 2 at $6.000, in Alternative 3 at only $100 and in Alternative 4 at the sum of these 2 cases; $6.100.

Energy Cost.

As shown in the Technical Analysis, the average total energy cost over 5 years of the WiFi devices with sensing engine included is estimated at $197, with a worst case cost of $657. In the context of our scenario both these numbers are negligible.

The Zigbee nodes are powered by primary (disposable) batteries, therefore their cost of energy includes the batteries themselves and the cost of replacing them. As shown in the Technical Analysis, the expected lifetime of the batteries is well above 5 years. We assume replacement every 5 years to cover for some safety margin, and intentional scheduling prior to complete depletion. Replacing batteries involves labor and temporary halt of the assembly line. As some sensors are located in hard-to-reach locations, we assume that the average cost of labor for replacing batteries in one sensor is $100, and the production line is halted for 30 minutes on the average. We therefore calculate the total energy costs for ZigBee nodes as follows: 1. Typical battery cost is $20, with total cost for 5 years of $20 * 2 * 600 = $24.000. 2. Battery replacement cost in 5 years in composed of $100 * 600 = $60.000 in labor, and $300 * 0.5 * 600 = $90.000 in loss of profit due to discontinuation of production, with a total of $150.000.

It is important to note that all energy costs apply to all four deployment alternatives of the sensing engine, since we show in the Technical Analysis that the additional power consumption directly associated with the sensing engine is negligible.

Total Savings due to Sensing

Table 1 presents the total expected savings due to the implementation of sensing engines. It is calculated by comparing the remaining cost that is attributed to failures due to interference in the Zigbee network over 5 years, to the costs of interference in the reference case (Alternative 1), while taking into account the initial investment in the sensing engines. Since it is typical to use retransmission to overcome transmission failures, we assume up to 2 retransmissions of each packet. The table shows how the expected savings vary with the different deployment alternatives of sensing engines, and with the traffic load on the WiFi network. We calculate the expected savings when up to 2 retransmissions are performed, for typical WiFi loads of 5%-20%. We also calculate it for an extreme WiFi load of 50%, to examine the robustness of the solution and its immunity to heavy interference. Looking at Table 1 it is clear that when sensing is implemented in both the WiFi and Zigbee nodes, the result is a robust solution, that even under extreme WiFi load of 50% incurs only $290.000 over 5 years due to Zigbee transmission failures. If more that 2 retransmissions are considered, the incurred cost can be reduced further, and implementing sensing engines just in the WiFi nodes can become enough.

In this analysis we completely ignore the cost of energy, as it is practically identical in all the alternatives we examine. This cost totals $174.000, which is anyway very low compared to the potential gains achieved by the sensing engines.

It is well known that in a factory setting the cost of failures can amount to significant numbers. For this reason sensors are deployed to detect failure conditions early. Sensor information is delivered over a data communication network, with clear operational advantages to using wireless technology, e.g. Zigbee. However, the reliability of the Zigbee network is strongly affected by interfering traffic from the collocated administrative WLAN network, with a direct impact on the rate of failure in the factory. To increase reliability, we propose to reduce interference by adding cross-technology sensing engines to the CCA mechanism of some network nodes. We show that from both the technical and economical points of view this improvement is beneficial. We show that adding sensing engines can indeed reduce the effects of interference significantly, and that the resulting reduction in failures outweighs the low investment costs and the negligible increase in energy costs. We conclude that for this case sensing is a viable and profitable solution. We discover that adding sensing engines to both the Zigbee sensors and the WiFi devices is the most beneficial alternative. It brings interference to the lowest level among all alternatives; it is immune to very high traffic load on the WiFi network; and it maximizes the financial gain.

( 4 )

 4 Fig. 1 shows the dependence of Zigbee PER on the traffic load in the WiFi network, for the different deployment alternatives of the sensing engine.

Fig. 1 .

 1 Fig. 1. Zigbee PER in different implementation alternatives of sensing engine

Table 1 .

 1 PER and Cost of failures in the Zigbee sensor network, and the expected savings for the different deployment alternatives of sensing engines

		Alternative 1	Alternative 2	Alternative 3	Alternative 4
	WiFi Load 5% -Zigbee PER	30%	26%	8%	2,3%
	Failure cost -No Retransmissions	2,03M	1,76M	541K	156K
	Failure cost -up to 2 retransmissions	183K	119K	3,5K	80
	WiFi Load 5% -Saving with Sensing	NA	58K	179K	177K
	WiFi Load 10% -Zigbee PER	53%	46%	17%	4,7%
	Failure cost -No Retransmissions	3,59M	3,11M	1,15M	318K
	Failure cost -up to 2 retransmissions	1,0M	659K	33K	700
	WiFi Load 10% -Saving with Sensing	NA	335K	967K	993K
	WiFi Load 15% -Zigbee PER	70%	63%	25%	7,3%
	Failure cost -No Retransmissions	4,74M	4,26M	1,69M	494K
	Failure cost -up to 2 retransmissions	2,32M	1,69M	106K	2,63K
	WiFi Load 15% -Saving with Sensing	NA	624K	2,21M	2,31M
	WiFi Load 20% -Zigbee PER	82%	75%	34%	10%
	Failure cost -No Retransmissions	5,55M	5,07M	2,3M	677K
	Failure cost -up to 2 retransmissions	3,73M	2,85M	266K	6,8K
	WiFi Load 20% -Saving with Sensing	NA	874K	3,46M	3,72M
	WiFi Load 50% -Zigbee PER	99.9%	99.6%	80%	35%
	Failure cost -No Retransmissions	6,76M	6,74M	5,41M	2,37M
	Failure cost -up to 2 retransmissions	6,74M	6,68M	3,46M	290K
	WiFi Load 50% -Saving with Sensing	NA	54K	3,28M	6,44M

Acknowledgments. The research leading to these results has received funding from the European Union's Seventh Framework Programme FP7/2007-2013 under grant agreements n° 257542 (CONSERN project) and n° 258301 (CREW project). It has also received funding from IWT under projects ESSENCES and NGWINETS.


Janus Heide

Morten V Pedersen

Frank H P Fitzek

Decoding Algorithms for Random Linear Network Codes

Keywords: Network Coding, Algorithms, Implementation

We consider the problem of efficient decoding of a random linear code over a finite field. In particular we are interested in the case where the code is random, relatively sparse, and use the binary finite field as an example. The goal is to decode the data using fewer operations to potentially achieve a high coding throughput, and reduce energy consumption. We use an on-the-fly version of the Gauss-Jordan algorithm as a baseline, and provide several simple improvements to reduce the number of operations needed to perform decoding. Our tests show that the improvements can reduce the number of operations used during decoding with 10-20% on average depending on the code parameters.

Introduction

When implementing and deploying Network Coding (NC) at least two performance criteria are important; the magnitude of overhead added by the code, and the speed at which encoding, recoding and decoding can be performed. We consider the last issue and note that it is trivial to implement encoding such that the minimal number of operations are used. As recoding is similar to encoding we turn our attention to the problem of fast decoding.

A popular approach to network coding is Random Linear Network Coding (RLNC), introduced in [START_REF] Ho | The benefits of coding over routing in a randomized setting[END_REF]. It is based on finite fields, and it has been shown that high coding throughput can be obtained with this code when the binary finite field is used [START_REF] Heide | Network coding for mobile devices -systematic binary random rateless codes[END_REF]. Additionally, as a randomly drawn element from the binary field is zero with high probability (50%), the resulting code will be sparse.

As data is encoded and recoded in a random way, there is no special structure or shortcut to exploit when performing decoding. Instead we are left with the tedious task of determining the inverse of operations performed during encoding/recoding. Additionally we prefer to perform decoding as packets arrive in order to avoid a large decoding delay when the final packet arrives. We know the resulting code is sparse, and therefore propose some simple mechanisms to utilize this fact. We have implemented these and their impact on the number of operations used during decoding.

In the remainder of this paper we introduce the used encoding approach, several decoding optimizations, and their measured impact on the decoding.

Coding Algorihtms

We consider encoding packets from some data to be sent from a source to a sink, we denote this data the generation. The generation consists of g pieces, called symbols each with a size of m bits, where g is called the generation size, and thus the generation contains g • m bits of data. The g symbols are arranged in the matrix M = [m 1 ; m 2 ; . . . ; m g ], where m i is a column vector. In practise some original file or data stream may be split into several generations, but here we only consider a single generation.

To generate a new encoded symbol x, M is multiplied with a randomly generated coding vector g of length g, x = M × g. In this way we can construct g + r coded symbols and coding vectors, where r is any number of redundant symbols as the code is rateless. When a coded symbol is transmitted on the network it is accompanied by its coding vector, and together they form a coded packet. A practical interpretation is that each coded symbol, is a combination or mix of the original symbols from the generation. The benefit is that nearly infinite coded symbols can be created.

Coded packet

Existing protocol header Coding vector g Coded symbol x

Decoding

A sink must receive g linearly independent symbols and coding vectors from the generation to decode the data successfully. All received symbols are placed in the matrix X = [x 1 , x2 , . . . , xg ] and all coding vectors are placed in the matrix Ĝ = [ĝ 1 , ĝ2 , . . . , ĝg ], we denote Ĝ the decoding matrix. Thus the vectors and symbols are row vectors in Ĝ and X respectively as this is more convenient during recoding. Hence we may perform any row operation on Ĝ if we perform the same row operation on X.

The original data M can then be decoded as M = X × Ĝ-1 by the decoder. The problem is how to achieve this in an efficient way. We note that row operations on X are more computationally expensive compared to operations on Ĝ, as generally m >> g.

Elements in the matrices are indexed row-column, thus Ĝ[i, j] is the element in Ĝ on the intersection between the i'th row and the j'th column. The i'th row in the matrix is indexed as Ĝ[i]. Initially no packets have been received, thus Ĝ and X are zero matrices. As we operate in the binary finite field we denote bitwise XOR of two bit strings of the same length as ⊕.

Algorithm 1: Decoder initial state Input: g, m Data: Ĝ ← 0 g×g The decoding matrix Data: X ← 0 g×m

The (partially) decoded data Data: rank ← 0 the rank of Ĝ

Basic

As a reference we use the basic decoder algorithm, see Algorithm 5, described in [START_REF] Heide | Network coding for mobile devices -systematic binary random rateless codes[END_REF]. This algorithm is a modified version of the Gauss-Jordan algorithm. On each run the algorithm attempts to get the decoding matrix into reduced echelon form. First the received vector and symbol ĝ and x is forward substituted into the previous received vectors and symbols Ĝ and X respectively, and subsequently backward substitution is performed. If the packet was a linear combination of previous received packets it is reduced to the zero-vector 0 g and discarded.

Algorithm 2: ForwardSubstitute Input: x,ĝ pivotPosition ← 0 0 Indicates that no pivot was found

1 for i ← 1 : g do 2 if ĝ[i] = 1 then 3 if Ĝ[i, i] = 1 then 4 ĝ ← ĝ ⊕ Ĝ[i] substitute into new vector 5 x ← x ⊕ X[i] substitute into

Suppress Null (SN)

To avoid wasting operations on symbols that does not carry novel information, we record the operations performed on the vector. If the vector is reduced to the zero vector, the packet was linearly dependent and the recorded operations are discarded. Otherwise the packet was novel and the recorded operations are executed on the symbol. This reduces the computational cost when a linear dependent packet is received. This is most likely to occur in the end phase of the decoding, thus it is most beneficial for small generation sizes. In real world scenarios the probability of receiving a linearly dependent packet can be high, in which cases this approach would be beneficial. To implement this, line 1 in Algorithm 5 is replaced with Algorithm 7. Algorithm 6: ExecuteRecipe Input: x,recipe for i ← 1 : g do

1 if recipe[i] = 1 then 2 x ← x ⊕ X[i]
substitute into symbol 3 Algorithm 7: ForwardSubstituteSuppressNull Input: x,ĝ pivotPosition ← 0 0 Indicates that no pivot was found

1 recipe ← 0 g 2 for i ← 1 : g do 3 if ĝ[i] = 1 then 4 if Ĝ[i, i] = 1 then 5 ĝ ← ĝ ⊕ Ĝ[i] substitute into

Density Check (DC)

When forward substitution is performed there is a risk that a high density packets is substituted into a low density packet. The density is defined as Density

(h) = g k=1 (h k =0) g
, which is the number of non-zeros in the vector, and where h is the coding vector. Generally a sparse packet requires little work to decode and a dense packet requires much work to decode. When a vector is substituted into a sparse vector, the resulting vector will with high probability have higher density and thus fill-in occur. To reduce this problem incoming packets can be sorted based on density during forward substitution. When it is detected that two vectors have the same pivot element their densities are compared. The vector with the lowest density is inserted into the decoding matrix. The low density packet is then substituted into the high density packet, and the forward substitution is continued with the resulting packet. To implement this, line 1 in Algorithm 5 is replaced with Algorithm 8.

Algorithm 8: ForwardSubstituteDensityCheck Input: x,ĝ pivotPosition ← 0 0 Indicates that no pivot was found

1 for i ← 1 : g do 2 if ĝ[i] = 1 then 3 if Ĝ[i, i] = 1 then 4 if Density(ĝ) < Density( Ĝ[i]) then 5 ĝ ↔ Ĝ[i]
swap new vector with old vector

6 x ↔ X[i]
swap new symbol with old symbol

7 ĝ ← ĝ ⊕ Ĝ[i] 8 x ← x ⊕ X[i]

Delayed Backwards Substitution (DBS)

To reduce the fill-in effect the backwards substitution is postponed until the decoding matrix has full rank. Additionally it is not necessary to perform any backwards substitution on the vectors because backwards substitution is performed starting from the last row. Hence when backwards substitution of a packet is complete, that packet has a pivot element for which all other encoding vectors are zero. This approach is only semi on-the-fly, as only some decoding is performed when packets arrive. Therefore the decoding delay when the final packet arrive will increase. This is implemented with Algorithm 9 Algorithm 9: DecoderDelayedBackwardsSubstitution Input: x,ĝ pivotPosition = ForwardSubstitute(x,ĝ)

1 if pivotPosition > 0 then 2 InsertPacket(x,

Results

We have decoded a large number of generations with each of the optimizations, and measured the used vector and symbol operations which is ⊕ of two vectors, and two symbols respectively. We have considered two densities while encoding, d = 1 2 and d = log 2 (g) g which we denote dense and sparse respectively. d = 1 2 gives the lowest probability of linear dependence, and d = log 2 (g) g is a good trade-off between linear dependence and density. As a reference the mean number of both vector and symbol operations during encoding of one packet can be calculated as g 2 and log 2 (g) for the dense and sparse case respectively. With the Basic algorithm the number of operations during encoding and decoding is identical for the dense case, see Fig 1(a) and 1(b) and calculate g 2 . For the sparse case the number of operations is significantly higher for decoding than for encoding, see Fig 1(c) and 1(d), and calculate log 2 (g).

When Suppress Null is used the number of reduced symbol operations can be observed by subtracting the number of symbol operations from the number of vector operations. The reduction is highest for small g, which is where the ratio of linearly dependent packet is largest. For g = 16 and g = 32 the reduction in symbol operations is 9.5% and 4.4% respectively, for high g s the reduction is approximately 0%.

Density Check reduces the number of operations for the sparse case marginally, but has no effect for the dense case.

The Delayed Backwards Substitution decreases the number of vector operations with approximately 40% when the encoding is sparse, and 50% when the encoding is dense as no operations needs to be performed on the vectors during backwards substitution. Interestingly the number of symbol operations increase significantly for the sparse encoding.

In DC-DBS, density check and delayed backwards substitution are combined, and the number of both data and vector operations are significantly reduced. For the sparse case the reduction is approximately 50% of the vector operations, and almost 20% of the symbol operations. For the dense case the reduction is approximately 50% of the vector operations, and almost 10% of the symbol operations. Interestingly the number of vector and symbol operations is lower for decoding compared to encoding, in the dense case. Hence the combination of DC and DBS is significantly better than the two alone, as the expensive symbol operations are reduced.

With SN-DC-DBS we additionally include Suppress Null, the number of symbol operations is reduced slightly for high g and significantly for low g.

Conclusion

The considered decoding optimizations have been shown to reduce the number of necessary operations during decoding. The reduction in symbol decoding operations is approximately 10%, and 20%, when the density during encoding is dense and sparse respectively. In both cases the number of vector operations is approximately halved. Surprisingly decoding can in some cases be performed with fewer operations than encoding.

2 Ĝ 1 X[pivotposition] = x 2 1 if pivotPosition > 0 then 2 BackwardsSubstitute

 21212 BackwardsSubstituteInput: x,ĝ, pivotPosition for i ← (pivotPosition -1) : 1 do1 if Ĝ[i, pivotPosition] = 1 then [i] ← Ĝ[i] ⊕ ĝ substitute into old vector 3 X[i] ← X[i] ⊕ x substitute intoold symbol 4 Algorithm 4: InsertPacket Input: x,ĝ, pivotPosition Ĝ[pivotposition] = ĝ Algorithm 5: DecoderBasic Input: x,ĝ pivotPosition = ForwardSubstitute(x,ĝ)

Fig. 1 .

 1 Fig. 1. Vector and symbol operations during decoding, when d = 1 2 and d = log 2 (g) g .

12 return pivotPosition 13

	7
	8	else
		pivotPosition ← i	pivot element found

new vector 6 recipe[i] ← 1 9 break 10 if pivotPosition > 0 then 11 ExecuteRecipe(x,recipe)

Acknowledgment

This work was partially financed by the CONE project (Grant No. 09-066549/FTP) granted by the Danish Ministry of Science, Technology and Innovation, and the ENOC project in collaboration with Nokia, Oulu.

Algorithm 10: BackwardsSubstituteFinal for i ← g : 2 do 1 for j ← (i -1) : 1 do All rows above

substitute into the symbol 4

Density Check, and Delayed Backwards Substitution (DC-DBS)

When DC and DBS are combined vectors are sorted so sparse vectors are kept at the top of the decoding matrix while dense vectors are pushed downwards.

Because backwards substitution is performed only when the rank is full, no fill-in occurs during backwards substitution, as only fully decoded packets are substituted back. To implement this, line 1 in Algorithm 9 is replaced with Algorithm 8.

Suppress Null, Density Check, and Delayed Backwards Substitution (SN-DC-DBS)

To reduce the cost of receiving linear dependent packets we include SN, by replacing line 1 in Algorithm 9 with Algorithm 11. Algorithm 11: ForwardSubstitute-SN-DC Input: x,ĝ pivotPosition ← 0 0 Indicates that no pivot was found