Yuehong Gao

Jinxing Yang

Xin Zhang

Yuming Jiang

Capacity Limits for a Cognitive Radio Network under Fading Channel ⋆

Keywords: Capacity, Cognitive Radio, GE Channel, Performance Bound, Stochastic Network Calculus

In this paper, performance evaluation of a cognitive radio network is conducted. The analysis is based on stochastic network calculus. The system is supposed to work in a Time Division Multiple Access (TDMA) mode with fixed slot length. The wireless channel is modeled as a Gilbert-Elliott (GE) fading channel, where the channel quality transits between state ON and state OFF according to a Markov chain. Spectrum sensing errors, which can be classified into mis-detection and false-alarm, are taken into consideration. Particularly, a stochastic arrival curve for spectrum sensing error process, and a stochastic service curve for GE channel, are derived. In addition, performance distribution bounds are obtained based on stochastic network calculus. Furthermore, numerical calculations are made to show the capacity limits under delay constraints.

Introduction

Nowadays, cognitive radio has become a promising technology, since it provides a solution to improve the spectrum utilization efficiency. In a cognitive radio network, the secondary users (SUs) sense the spectrum before transmitting on it, and if they find available spectrum holes, they will make use of those resources. The sensing results, however, may not exactly match with the real condition. In other words, spectrum sensing error happens sometimes, which leads to collision between the primary transmission and the secondary transmission or waste of transmission opportunities for secondary users. Therefore, physical layer retransmission is needed in order to deal with such collisions.

In this paper, we consider a cognitive radio network with two classes of input traffic, the aggregated flow from primary users and the one from secondary users, as shown in Fig. 1. The system works in a slotted mode with fixed slot length T . The flow from PUs has higher priority over SUs flow to be served. Secondary users try to sense the channel and act based on the sensing results. Sensing errors may happen and will affect the performance. How to analyze the performance guarantee for each class of users is a key issue in cognitive radio networks. Some queueing theory based studies have been made such as in [START_REF] Suliman | Queueing analysis of opportunistic access in cognitive radios[END_REF], where delay and queue related parameters are derived. In [START_REF] Gao | Performance Analysis for a Cognitive Radio with Imperfect Spectrum Sensing[END_REF][START_REF] Gao | Performance Bounds for a Cognitive Radio Network with Network Calculus Analysis[END_REF][START_REF] Gao | On the Backlog and Delay Distributions of Primary and Secondary Users in a Cognitive Radio Network[END_REF], we made some analysis by using network calculus to derive the backlog and delay distribution bounds for a simplified system model. Network calculus is an approach to deal with flow problems in communication networks, which was introduced by Cruz in 1991 [START_REF] Cruz | A calculus for network delay, Part I: Network elements in isolations, and Part II: Network Analysis[END_REF]. After about 20-year development, network calculus has evolved into two branches: the deterministic branch and the stochastic branch. In this study, stochastic network calculus is employed. In stochastic network calculus, stochastic arrival curve (sac) and stochastic service curve (ssc) are used to describe the characteristics of a flow and a server, respectively. Based on sac and ssc, performance bounds can be derived.

In [START_REF] Gao | Performance Analysis for a Cognitive Radio with Imperfect Spectrum Sensing[END_REF][START_REF] Gao | Performance Bounds for a Cognitive Radio Network with Network Calculus Analysis[END_REF][START_REF] Gao | On the Backlog and Delay Distributions of Primary and Secondary Users in a Cognitive Radio Network[END_REF], the wireless channel was assumed to be a constant error-free channel. However, this assumption is not practical in real systems, because the essential characteristic of a wireless channel is its fading nature. In this paper, this shortage is overcome by considering the Gilbert-Elliott (GE) channel model [START_REF] Gilbert | Capacity of a bursty-noise channel[END_REF][START_REF] Elliott | Estimates of error rates for codes on bursty-noise channels[END_REF], which has two states, Good (G) and Bad (B). In the discrete time model, these two states transit between each other according to a Markov chain. In addition, the sensing error process is re-modeled compared with the model in [START_REF] Gao | Performance Analysis for a Cognitive Radio with Imperfect Spectrum Sensing[END_REF], so that tighter performance bounds can be obtained.

The paper is organized as follows. In Section 2, stochastic network calculus basics are introduced, where the stochastic arrival curve for sensing error process and the stochastic service curve for GE fading channel are derived, and the delay bound for each flow is also obtained. Section 3 discusses the numerical results and capacity limits, followed by a summary in Section 4.

Stochastic Network Calculus Analysis

Traffic Modeling

Stochastic arrival curve can be defined from different aspects [START_REF] Jiang | Stochastic Network Calculus[END_REF]. Here, we explore the virtual-backlog-centric based definition as follows.

Definition 1. (Stochastic Arrival Curve).

A flow A(t) is said to have a virtual-backlog-centric (v.b.c) stochastic arrival curve α ∈ F3 with bounding function f ∈ F 4 , denoted by A(t) ∼ sac ⟨f, α⟩, if for all t ≥ 0 and all x ≥ 0 there holds:

P { sup 0≤s≤t {A(s, t) -α(t -s)} > x } ≤ f (x), (1)
where A(s, t) denotes the cumulative amount of traffic during period (s, t], A(0, t) is written as A(t) for short, and α(t) is a non-decreasing function.

Stochastic arrival curves of many traffic models have been derived, such as in [START_REF] Jiang | Stochastic Network Calculus[END_REF]. Therefore, we just employ the models directly in this paper, and put our efforts on other aspects.

Modeling of Spectrum Sensing Error Process

In cognitive radio networks, secondary users sense the spectrum and utilize the available white spaces for their transmissions. However, sensing errors may happen, which lead to transmission collision or opportunity waste. To be specific, sensing errors can be classified into two types, mis-detection (MD) and falsealarm (FA). Mis-detection means that the spectrum is occupied by PUs but the spectrum sensing result says it is available for SUs, which will result in transmission collision and influence both PUs' and SUs' current transmission. However, false alarm occurs in the opposite way, when SUs believe that the spectrum is being used by PUs but actually the spectrum is idle. As a result, SUs will miss those transmission opportunities.

Based on the facts described above, the error process can be considered as a special type of input traffic, which also competes for the transmission resource and has the highest priority.In this part, the stochastic arrival curve for sensing error process will be derived.

Here, we consider a slotted system with fixed slot length T , and the probability that sensing error happens in one time slot is supposed to be p. By further assuming the independency between the appearances of sensing errors in adjacent slots, the impairment arrival process I(t) is a Lévy process, where I(t) denotes the number of sensing errors during slot (0, t]. Then, according to Lemma 1 in the appendix, process I(t) has a v.b.c stochastic arrival curve, denoted by I(t) ∼ sac ⟨f I , α I ⟩, where

f I (x) = e -θθ1 e -θx
(2)

α I (t) = [ 1 θ log E[e θI(1) ] + θ 1 ] • t ≡ [ρ I (θ) + θ 1 ] • t (3)
for free parameters ∀θ 1 ≥ 0 and ∀θ > 0.

In each slot, the happening of sensing error has a Bernoulli distribution with parameter p. Therefore, ρ I (θ) in Eq.( 3) can be expressed as

ρ I (θ) = 1 θ log(1 -p + pe θσ ), (4)
where σ denotes the number of packets that are not transmitted successfully in a slot due to a sensing error. Furthermore, mis-detection process and false-alarm process have the same characteristic as the sensing error process, and the only difference is the happening probability. In later parts, the following notations are used to represent the stochastic arrival curves of mis-detection process and false-alarm process:

I M D (t) ∼ sac ⟨f M D , α M D ⟩, I F A (t) ∼ sac ⟨f F A , α F A ⟩, ( 5
)
where f M D and f F A have the same form as in Eq.( 2), α M D and α F A can be obtained by replacing the probability p in Eq.( 3) with p M D and p F A , respectively.

Server Modeling

Similar to the concept of stochastic arrival curve, stochastic service curve is defined to describe the service guarantee that a server can provide, and several different definitions have been proposed. Here, we employ the following one [START_REF] Jiang | Stochastic Network Calculus[END_REF].

Definition 2. (Stochastic Service Curve).

A system S is said to provide a stochastic service curve β ∈ F with bounding function g ∈ F , denoted by S ∼ ssc ⟨g, β⟩, if for all t ≥ 0 and all x ≥ 0 there holds:

P {A ⊗ β(t) -A * (t) > x} ≤ g(x). (6)
Here, A ⊗ β(t) ≡ inf 0≤s≤t {A(s) + β(t -s)}, and A * (t) denotes the cumulative amount of output traffic up to time t. The Gilbert-Elliott channel model is named after the originators, which can be further classified into discrete-time and continuous-time model. In this paper, the discrete time model is considered, since it matches well with the slotted system model. Fig. 2 shows a two-state GE channel, where the channel can either be in ON state (state 1), in which data can be decoded error-free (if no collision happens during the transmission), or in state OFF (state 0), in which the channel quality is too bad to transmit any data. The channel state transits among the two states as a Markov process with transition matrix of Q, where q ij denotes the transition probability from state i to state j (i, j ∈ {0, 1}).

Let S(t) denote the service provided by the channel during (0, t]. Then, there are two cases. -Case 1: t is not within any backlogged period. In this case, there is no backlog in the system at time t, which means that all traffic that arrived up to time t has left the server. Hence, A * (t) = A(t) and consequently

A ⊗ β(t) -A * (t) = A(t) + β(0) -A * (t) = 0.
-Case 2: t is within a backlogged period (t 0 , t b ], where t 0 is the start point of the backlogged period. Then, A * (t 0 ) = A(t 0 ) and

A ⊗ β(t) -A * (t) ≤ A(t 0 ) + β(t -t 0 ) -A * (t) (7) = β(t -t 0 ) + A * (t 0 ) -A * (t) = β(t -t 0 ) -S(t 0 , t) (8)
Then, we have:

P {A ⊗ β(t) -A * (t) > x} ≤ P {β(t -t 0 ) -S(t 0 , t) > x} ≤ P {e θ[β(t-t0)-S(t0,t)] > e θx } ≤ e -θx E[e θ[β(t-t0)-S(t0,t)] ] ≤ e -θx E[e θ[µ(θ)•(t-t0)-S(t0,t)] ] = e -θx E[e θ[µ(θ)•τ -S(τ )] ] ≤ e -θx
where the third step is known as Chernoff bound, and the fourth step is due to that S(t) is stationary, and

µ(θ) ≡ - 1 θτ log E[e -θS(τ ) ]
which is known as the effective bandwidth of process S in the literature [START_REF] Kelly | Notes on effective bandwidths[END_REF] [10]. For the two-state Markov chain of the considered GE channel, its effective bandwidth has an explicit form [START_REF] Chang | Performance Guarantees in Communication Networks[END_REF], which is adopted in this paper as μ(θ) = 1 -θ log ( q 00 + q 11 e -cθ + √ (q 00 + q 11 e -cθ ) 2 -4(q 11 + q 00 -1)e -cθ 2

)

By combining both cases, a stochastic service curve of GE channel has been found as:

S(t) ∼ ssc ⟨g(x) = e -θx , β(t) = µ(θ) • t⟩. ( 9
)

Delay Bound

Previous work in [START_REF] Gao | Performance Analysis for a Cognitive Radio with Imperfect Spectrum Sensing[END_REF] has discussed how to obtain the stochastic service curve that can be effectively provided to each input traffic. Here, by using the following notations for input traffic, f l P : A P (t) ∼ sac ⟨f P (x), α P (t)⟩ (10) f l S : A S (t) ∼ sac ⟨f S (x), α S (t)⟩, [START_REF] Jiang | Fundamental Calculus on Generalized Stochastically Bounded Bursty Traffic for Communication Networks[END_REF] and by further assuming Re-Transmission until Success (RT-S) scheme, the stochastic service curve for PUs' traffic and SUs' traffic can be expressed as:

f l P : S P (t) ∼ ssc ⟨g P (x), β P (t)⟩ (12) with g P (x) = f M D ⊗ g(x), β P (t) = β -α M D (t) (13) f l S : S S (t) ∼ ssc ⟨g S (x), β S (t)⟩ (14) with g S (x) = f I ⊗ g ⊗ f P (x), β S (t) = β -α I -α P (t) (15)
Then, based on the performance bound theorem in [START_REF] Gao | Performance Analysis for a Cognitive Radio with Imperfect Spectrum Sensing[END_REF], the delay distribution bound can be summarized as:

Theorem 1. (Delay Bound) P {D U (t) > h(α U + x, β U )} ≤ [f U ⊗ g U (x)] 1 , ( 16
)
where

U ∈ {P, S}, h(α + x, β) = sup s≥0 {inf {τ ≥ 0 : α(s) + x ≤ β(s + τ )}} and [•] 1 denotes max(min(•, 1), 0)

Numerical Results

In previous sections, traffic model, server model as well as the considered cognitive radio network model are described with the delay bound theorem as an ending. In this section, specific parameters and configurations will be substituted into the deduction above in order to obtain the capacity limit under certain delay constraints. The input packet arrival, f l P and f l S , are assumed to be Poisson flow. And the stochastic arrival curve for Poisson traffic is defined as follows.

Definition 3. (Poisson Traffic). Suppose all packets of a flow have the same size L and they arrive according to a Poisson process with mean arrival rate λ.

Then the flow has a stochastic arrival curve A(t) ∼ sac ⟨f P ois , rt⟩ for any r > λL with bounding function [START_REF] Jiang | Stochastic Network Calculus[END_REF]:

f P ois (x) = 1 -(1 -a) k ∑ i=0 [ [a(i -k)] i i! e -a(i-k)
] where a = λL r and k = ⌈ x L ⌉. The network is supposed to be a LTE system using OFDM technology with slot length of 0.5ms. In each slot, there are 7 OFDM symbols in time domain, 50 resource blocks (RB) in frequency domain with 12 sub-carriers in each RB. 16QAM and 1/3 -rate Turbo code are used as the modulation and coding scheme. Then, the packet length for Poisson arrival is set as the effective bits transmitted in an LTE slot, i.e., 5.6kbits. Based on this assumption, the parameter σ in error process and c in channel model are all equal to 1 packet per slot. State transition probability q 01 and q 10 for GE channel are set as 1 and 0.11, respectively. The free parameters, such as θ, are optimized numerically with a tradeoff between acceptable accuracy and tolerable complexity.

Primary traffic flow is supposed to be a VoIP session, which belongs to the Guaranteed Bit Rate (GBR) bearer in LTE system. While secondary traffic flow is set as TCP interaction service, which is non-GBR bearer because of the lower priority in the whole network. Table .1 lists the QoS Class Identifier (QCI) requirements.

In the system model considered here, re-transmission until success mechanism is employed, which means no packet is dropped because of collision or deep channel fading. Packet loss only happens when the sojourn delay exceeds the delay budget. Therefore, the delay constraints can be written as: In order to fulfill the delay constraints, there exist an upper bound on the arrival rate λ of input traffic, which is defined as the capacity limit in this paper.

The capacity limit of PUs flow can be expressed as:

C P = max{λ P , subject to Constraint 1 } (19)
Fig. 3(a) shows the delay distribution of PUs input flow calculated from Theorem 1. We can notice that, there is still some capacity margin when the arrival rate of PUs traffic is 1600 packets per second; while delay constraint cannot be met when the arrival rate is increased to 1720 packets per second. The maximum arrival rate of primary traffic, also called capacity limit C P , is 1690 packets per second when the delay constraint can be guaranteed at the same time.

As for the secondary traffic, it can be transmitted when there is no primary traffic. Therefore, the maximum arrival rate of the secondary network has close relationship with the load η of primary network, which is defined as the ratio of actual arrival rate over the capacity limit, i.e., η = λ P /C P . Then, the capacity limit of SUs flow can be expressed as:

C S = max{λ S |η, subject to Constraint 2 } (20)
Fig. 3(b) shows three delay distribution bounds when η is set as 0. We can notice that λ S = 1738 packets per second is the capacity limit C S under delay constraint 2. If we define C P = 1690 and C S = 1738 packets per second as 100% load of the primary network and secondary network, respectively, Fig. 4 provides the admissible capacity region of the system, given Poisson arrivals. It is shown that the maximum arrival rate of secondary flow decreases when the load of primary flow increases. Particularly, for any point below the curve, which corresponds to a load of primary traffic and a load of secondary traffic, the system can guarantee the delay requirement and the required loss probability.

Conclusion and Discussion

In this paper, capacity limits, defined as the maximum arrival rate, for both primary and secondary traffics in a cognitive radio network are obtained under delay constraints. Stochastic network calculus is relied on to derive the delay distribution bounds, which includes two fundamental concepts: stochastic arrival curve and stochastic service curve. The spectrum sensing error process is analyzed with stochastic arrival curve first. Secondly, Gilbert-Elliott is used to model the fading channel, and its stochastic service curve is derived. And then, specific expressions for delay distribution bounds are obtained. Parameters and configurations in LTE network are used to calculate the numerical results, where the capacity limit of primary traffic and the capacity limit of secondary traffic under different traffic load are discussed. In this paper, we have only considered Poisson arrival due to space limitation. However, the analysis can be easily extended to other types of arrivals. Particularly, for many types of traffic, their stochastic arrival curves have been found (e.g. see [START_REF] Jiang | Fundamental Calculus on Generalized Stochastically Bounded Bursty Traffic for Communication Networks[END_REF]), with which, the corresponding delay bounds and capacity/throughput regions are readily obtained.

Fig. 1 .

 1 Fig. 1. System Model

Fig. 2 .

 2 Fig. 2. Discrete-time two-state Gilbert-Elliott channel model

Constraint 1 :

 1 P (Delay P > 100slots) ≤ 10 -2 (17) Constraint 2 : P (Delay S > 500slots) ≤ 10 -4 (18)

Fig. 3 .

 3 Fig. 3. Delay Tail Distribution

Fig. 4 .

 4 Fig. 4. Capacity Region

Table 1 .

 1 QoS Requirements for Different Services in LTE System

	Traffic Delay Budget Packet Loss Prob
	VoIP	50ms	10 -2
	TCP	250ms	10 -4

F : the set of non-negative wide-sensing increasing functions

F : the set of non-negative wide-sensing decreasing functions

⋆ This work was partly supported by BUPT Fund for Young Scholars under grant NO.2011RC0114.

Appendix

Lemma 1. (v.b.c Stochastic Arrival Curve) If an arrival process A(t) has independent stationary increments, then it has a v.b.c stochastic arrival curve

e -θx for ∀θ 1 ≥ 0, and for ∀θ > 0 and ρ(θ) = 1

θ log E [ e θA (1) ] .

Proof. Define a sequence of non-negative random variables {V s } as

Since A(t) has independent stationary increments, we then have,

where

) is used to simplify the notations. In addition, it is easy to know that X t-s is independent of X t , X t-1 , ..., X t-s+1 , and it has stationary increments, there holds:

.., V t form a non-negative supermartingale. Then based on an inequality for supermartingale, Doob's inequality, the definition of ρ(θ) and A(t) has stationary increments, there holds:

≤ e -θx E[e θA(t-1,t)-θ[ρ(θ)+θ1] ] ≤ e -θx e -θθ1 (32) which ends the proof.


Morten V Pedersen

Janus Heide

Frank H P Fitzek

Kodo: An Open and Research Oriented Network Coding Library

Keywords:

This paper introduces the Kodo network coding library. Kodo is an open source C++ library intended to be used in practical studies of network coding algorithms. The target users for the library are researchers working with or interested in network coding. To provide a research friendly library Kodo provides a number of algorithms and building blocks, with which new and experimental algorithms can be implemented and tested. In this paper we introduce potential users to the goals, the structure, and the use of the library. To demonstrate the use of the library we provide a number of simple programming examples. It is our hope that network coding practitioners will use Kodo as a starting point, and in time contribute by improving and extending the functionality of Kodo.

Introduction

First introduced by Ahlswede et al. in [START_REF] Ahlswede | Network information flow[END_REF], network coding has in recent years received significant attention from a variety of research communities. However despite the large interest most current contributions are largely based on theoretical, analytical, and simulated studies and only few practical implementations have been developed. Of which even fewer has openly shared their implementations. In this paper we introduce an open source network coding library named Kodo. It is the hope that Kodo may serve as a practical starting point for researchers and students working in the area of network coding algorithms and implementations. At the time of writing the initial release of Kodo supports basic network coding algorithms and building blocks, however by releasing Kodo as open source it is the hope that contributions may lead to additional algorithms being added to Kodo. Before describing the library design and functionality we will first give an overview of the motivations and goals behind the library.

Flexibility: as the target users of Kodo are researchers working with network coding, one of the key goals behind the design of Kodo has been to create a flexible and extensible Application Programming Interface (API), while providing already functional components for implementers to re-use. To enable this, the ambition is that Kodo should provide a number of customizable building blocks rather than only a set of complete algorithms. Creating easy to use extension points in the library is vital to provide researchers the opportunity to use/reuse Kodo for their specific use-case or implementation.

To achieve this goal Kodo relies on the generic programming paradigms provided by the C++ template system. Through the use of C++ templates implementers may substitute or customize Kodo components without modifying the existing code. This makes experimental configurations easy to create and lowers the entry level for new users. Ease of use: to the extend possible it is the intent that Kodo should be usable also for researchers with limited programming experience. To achieve this Kodo attempts to provide a simple and clean API hiding the more complicated implementation details. To further support this Kodo will also provide programming language bindings, which will allow users of programming languages other than C++ to use the library functionality. Currently experimental bindings for the Python programming language are provided for a selected part of the API. Performance: one of the key challenges in the design of Kodo has been to provide the flexibility and ease of use required for research while not significantly sacrificing performance of the library. One of the most active areas for network coding implementations have been investigating and improving the performance of network coding algorithms, see [START_REF] Shojania | Random network coding on the iphone: fact or fiction?[END_REF], [START_REF] Vingelmann | Implementation of random linear network coding on opengl-enabled graphics cards[END_REF], [START_REF] Heide | Network coding for mobile devices -systematic binary random rateless codes[END_REF]. For this reason Kodo attempts to find a reasonable middle ground between flexibility and performance. In cases where these two requirements does not align, Kodo will typically aim for flexibility and ease of use over performance. The reason for this is to keep the library agile, and that high performance implementations should easily be derived from Kodo source code. Testing: to avoid and catch as many problems as early as possible, Kodo is tested using a number of unit tests. At the time of writing most components in Kodo is delivered with accompanying test cases, and it is the goal that all Kodo components should have a matching unit test. The testing framework used in Kodo is Qt test library (QtTestLib). It was chosen due to the good cross-platform support and ease of use provided by the Qt framework. It is important to note that the Kodo library itself does not have any dependencies on Qt, and that Kodo therefore may be used on platforms not supported by the Qt framework. Portability: it is the intention to keep Kodo as portable and self-contained as possible. In cases where platform specific dependencies are required, Kodo should provide interfaces which enable easy adaptation to that specific platform. Contributions: it is the hope that researchers from the networking coding community will join in the development of Kodo and contribute new functionality. Kodo will be released under a research friendly license which allows everybody to contribute and use the library in their research. Benchmarking: since Kodo is created to facilitate research of various Network Coding (NC) implementations, enabling measurements and monitor-ing the performance of the implemented algorithms are a priority. Having good methods for benchmarking allows quick comparisons between performance of existing and future algorithms or optimizations. Using the C++ template system users of Kodo may instrument code to collect useful information about algorithms and data structures used. Examples of this are to monitor the number of finite field operations performed by a specific type of encoder or the number of memory access operations performed during decoding. Additionally it allows the maintainers of Kodo to ensure that no modifications or additions to the library results in unwanted performance regressions.

Following the goals and motivation behind the library the following section will introduce the functionality provided by Kodo.

Network Coding Support

Due to its promising potential many algorithms and protocols have been suggested to demonstrate and exploit the benefits of network coding. Use cases range over wired to wireless and from the physical to the transport and application layer. In addition to these widely different areas of application, different variants of network coding also exist. Examples of this are inter-and intra-session network coding, where the former variant operates on data from a uniquely identifiable network flow and the latter allows mixing of data from different network flows. One might also differentiate between deterministic and non-deterministic network coding algorithms. These refer to the way a computer node participating in a network coding system operates on the data traversing it. Typically in deterministic algorithms a node performs a "fixed" number of operations on the incoming data, these predetermined operations may be selected based on different information e.g. the network topology. In contrast non-deterministic network coding or random network coding operates on the data in a random or pseudo-random manner. This has certain desirable advantages in e.g. dynamic wireless networks.

The initial release of Kodo supports only a subset of these use-cases, however it is the goal that future versions will eventually support a wide range of different network coding variants. The initial features implemented have been selected to support the creation of digital Random Linear Network Coding (RLNC) systems. RLNC has in recent years received a large amount of interest for use in dynamic networks e.g. wireless mesh networks [START_REF] Ho | A Random Linear Network Coding Approach to Multicast[END_REF]. Understanding the functionality of a RLNC system will therefore also be helpful to understand the current structure of the Kodo library. In the following we therefore provide a general overview of the supported RLNC components and show the corresponding C++ code used in Kodo. The C++ programming examples will not be explained in detail here, but are there to demonstrate how a RLNC application would look, using Kodo. For details about usage of the library, the programming API and further programming examples we refer the reader to the Kodo project web page.

Random Linear Network Coding

In RLNC we operate on either finite or infinite streams of binary data. To make the coding feasible we limit the amount of data considered by segmenting it into manageable sized chunks. Each chunk in turn consists of some number g packets, where each packet has a length of d bytes. In network coding terminology such a chunk of binary data, spanning g • d bytes, is called a generation.

One commonly used way for constructing generations from a file is illustrated in Figure 1. In this approach a file is divided into N packets, p 1 , p 2 , , p N . Packets are then sequentially divided into M = N g generations, each containing g packets. In Kodo this algorithm is referred to as the basic partitioning algorithm. Besides the basic partitioning algorithm Kodo also supports other partitioning schemes, such as the random annex code described in [START_REF] Li | Collecting coded coupons over overlapping generations[END_REF]. The following code listing shows how the basic partitioning algorithm is used in Kodo to partition a large buffer. // The buffer contaning all the packets of the file UnalignedBuffer fileBuffer(bufferPackets, packetSize); // Vector to hold the buffers for each generation std::vector<ThinBuffer> generationBuffers; // Run the basic partitioning, and add the generation // buffers to the vector BasicPartitioning basic(generationSize, packetSize); basic(fileBuffer.dataBuffer(), std::back_inserter( generationBuffers));

Listing 1.1 Initially we specify the target generation size and the desired packet size for each generation. The fileBuffer object represents the file, containing a large amount of packets to be distributed over different generations. This is achieved in the last line by passing file buffer to the basic partitioning algorithm. This creates a number of generation buffers and inserts them in the vector. Following this we may operate on a single generation at a time.

In addition to selecting the packet size and generation size parameters, implementers are faced with an additional choice before the coding can start, namely which finite field to use. In NC data operations are performed using finite field arithmetics. Performing arithmetic operations in finite fields are informally very similar to normal arithmetic with integers, the main difference being that only a finite number of elements exist, and that all operations are closed i.e. every operation performed on two field elements will result in an element also in the field. A simple example is the binary field 2 , which consists of two elements namely {0, 1}. In the binary field addition is implemented using the bit-wise XOR and multiplication is implemented using the bit-wise AND operator. For NC applications the choice of finite field represents a trade-off between computational cost and efficiency of the coding, i.e. how fast we may generate coded packets versus how likely it is to generate linear dependent and therefore useless packets. Kodo provides several choices of finite field implementations, and also allow external implementations to be used.

After creating the buffers containing the generation data and selecting the finite field to use, the encoding and decoding processes may start. Figure 2 presents an overview of the basic operations performed for each generation in a typical RLNC system.

At the top of Figure 2 the encoder uses the g original source packets to create k encoded packets, where k is larger or equal to g. The k encoded packets are then transmitted via an unreliable channel, causing a number of packet erasures. The job at the decoder side is to collect enough encoded packets to be able to reconstruct the original data. In general this is possible as long as the decoder receives g or more encoded packets. Note, that in RLNC the number of encoded packets, k, is not fixed which means that the encoder can continuously create new encoded packets if needed. For this reason this type of coding is often referred to as rate-less. Also shown in the figure is one of the most significant differences between NC and traditional schemes, namely the re-coding step shown in the bottom right of Figure 2. In contrast to e.g. traditional error correcting codes, NC based codes are not necessarily end-to-end codes, but allow intermediate nodes between a sender and receiver to re-code and forward data, instead of pure forwarding. In Kodo the encoding and decoding step for a single generation may be performed using the following example code: Listing 1.2 : The source code is a slightly modified excerpt from one of the unit tests, testing the encoder and decoder implementations of Kodo. Initially the coding parameters are specified and some buffers are prepared. We then setup a vector generator. The vector generator is responsible for creating the encoding vectors, in this case we are using a density generator which creates encoding vectors according to some specified density (i.e. number of non-zero elements in the vector). Kodo contains other types of vector generators e.g. for creating systematic encoding vectors. You may notice the word, binary, present in the vector generator, this denotes the finite field we are using. Binary refers to the 2 binary field. Kodo contains a number of different finite field implementations for different field sizes. Following this the code loops passing encoded packets from the encoder into the decoder until the decoder reports that decoding has completed.

The two source code examples shown demonstrates the code needed to implement an operational RLNC application in less than 60 lines of code. This completes the overall introduction of the Kodo functionality, to get an in-depth view on the possibilities with Kodo visit our project website (which may be found at www.cone-ftp.dk.

Conclusion

In this paper we have introduced the Kodo C++ network coding library, the goal of this paper is to provided a general overview of the components of the library and introduce its usage. In the initial release of Kodo a number of goals for the library has been specified, and it is the hope that these goals and introduction of Kodo presented here, may aid researchers in identifying whether Kodo may be useful for them in their network coding research. As shown in this paper Kodo currently support development of basic RLNC schemes and many general NC features are still missing. However, it is the aspiration that by releasing Kodo as open source, researchers will contribute to strengthen the capabilities and usefulness of the project.

Fig. 1 :

 1 Fig. 1: Basic partitioning algorithm for slicing a file into generations of a certain size.

Listing 1 . 1 :

 11 Using the basic partitioning algorithm // Selecting general coding parameters int generationSize = 16; int packetSize = 1600; // Size of the buffer int bufferPackets = 432141;

Fig. 2 :

 2 Fig. 2: Network coding system overview.

Acknowledgments

This work was partially financed by the CONE project (Grant No. 09-066549/FTP) granted by Danish Ministry of Science.


Alberto Moreno
email: alberto@cipher.risk.tsukuba.ac.jp

Eiji Okamoto
email: okamoto@risk.tsukuba.ac.jp

BlueSnarf revisited: OBEX FTP service directory traversal

Keywords: Bluetooth, mobile phones, exploit, data theft

As mobile operating systems reach the same level of complexity of computer operating systems, these may be affected by the same vulnerabilities and may be subject to the same kind of attacks. Bluetooth provides connectivity to a mobile phone but this network can also be used as a channel to deploy attacks and access its resources, such as personal information, confidential files or the possibility of making phone calls and consume the user's balance. When the first attacks to early Bluetooth mobile phones came up, manufacturers were forced to raise awareness about Bluetooth and make improvements in the security of the implementation. In spite of the improvements, we introduce a multi-platform vulnerability for mobile phones that allows a remote attacker to list arbitrary directories, and read and write arbitrary files via Bluetooth. Our experience shows that the attack can be performed in a real environment and it may lead to data theft.

Introduction

In a world that demands increasing levels of productivity the power and connectivity of the mobile phone has risen to meet the computer. Mobile operating systems turn as complex as computer operating systems and whilst capabilities to run applications grow, so does the potential security threat. It is not surprising that mobile phones already began to be affected by the same kind of security flaws as computers. In this paper we focus on attacks to mobile phones via Bluetooth and we show that this network can be used as a channel to run exploits originally aimed at computers.

Bluetooth is a widespread technology integrated in a large range of mobile phones from feature phones to smartphones. The technology is suitable for this class of equipment because of its multiple advantages: globally accessible, designed for low-power consumption and based on low-cost transceiver microchips.

Since its inception, Bluetooth has been subject of study from the point of view of the security and several attacks to mobile phones have been disclosed. Our contribution is the discovery of a multi-platform vulnerability for mobile phones which may lead to data theft.

Overview of Bluetooth

Bluetooth is the specification that defines a global standard for wireless communications in personal area networks. It allows the transmission of voice and data among different pieces of equipment through a radio frequency link in mobile environments.

The specification is based on a multi-layer protocol architecture. Above the protocols we find the Bluetooth profiles, which are generic definitions of usage models of Bluetooth. Each definition uses a particular configuration of protocols so the functionality of Bluetooth varies depending on the profile used by two devices to communicate.

Bluetooth profiles

At the time the standard was developed, the Bluetooth Special Interest Group (SIG) identified certain scenarios in which Bluetooth could allow two devices to communicate wirelessly, and defined each one in a Bluetooth profile [START_REF]Bluetooth SIG: Profiles overview[END_REF]. Some examples of usage models are wireless voice transmission between a mobile phone and handsfree headset, wireless networking between computers, wireless connection between a computer and I/O peripherals, and data exchange. For each application there is a specific Bluetooth profile, which may or may not be implemented in the Bluetooth stack by decision of the manufacturer; however, if implemented, the manufacturer shall follow the definition by Bluetooth SIG. This guarantees the interoperability between devices regardless of the vendor. If two devices of different kinds and different vendors comply with the same Bluetooth profile, we can expect these to interact properly in a given scenario.

All Bluetooth profiles intended for the usage model of data exchange are based on a generic profile called Generic Object Exchange Profile (GOEP). This profile defines the characteristics for the transfer of files and pieces or information such as business cards or meeting appointments, frequently knowns as objects between devices via Bluetooth.

The Generic Object Exchange Profile (GOEP) is based on the OBject EXchange (OBEX) communications protocol, which is maintained by the Infrared Data Association (IrDA). It was originally designed for the exchange of objects via infrared but it has also been adopted by Bluetooth. OBEX functions as a client-server protocol and it provides the capability for sending and receiving data. A client may send objects to a server by using the command OBEX PUT; or request objects from a server by using the command OBEX GET.

Object Push Profile (OPP) and File Transfer Profile (FTP) are two profiles intended for data exchange associated to the Generic Object Exchange Profile (GOEP). Both profiles act like an interface to the file system of a Bluetooth capable device and for this reason in this paper we analyze these from the perspective of security. There exists a potential risk in which these profiles may be exploited with malicious behavior in order to access arbitrary files without user consent, this means data theft. Hence, there is a obvious necessity to provide the Bluetooth protocol with sufficient robust security mechanisms.

Security mechanisms in Bluetooth

Bluetooth technology incorporates two mechanisms that strengthen the security of the protocol: authentication and authorization.

Authentication is the procedure which ensures that a device attempting a connection is indeed who it claims to be. When two devices agree to first establish a link, they must follow a process known as pairing. There are two types of pairing systems depending on the specification of Bluetooth: Legacy Pairing, which is followed by devices with Bluetooth version 2.0 and prior, and Secure Simple Pairing, introduced in Bluetooth version 2.1. At the end of the pairing process a secret link key is created and stored by both devices, this is understood as a trust relationship between devices.

The security function of authentication uses the link key generated after the pairing process and requires no user interaction. It is based on a challengeresponse scheme between devices sharing a secret link key. If the scheme is satisfied by both parts the connection is established. If one or both parts do not satisfy the challenge-response scheme because the link key cannot be provided, either because it was never created before or it was already deleted, then the pairing process is initiated.

Authorization is the procedure that determines whether a requesting device is allowed to access to a particular Bluetooth profile. Generally, this procedure requires user interaction as the owner of the device must manually grant the permission for the remote device to access the Bluetooth profile.

Authorization and authentication are independent mechanisms. A device already paired will satisfy authentication, however it may require manual authorization prior to establishing a connection to any profile.

The specification says that these security mechanisms should be implemented for incoming connections to the Bluetooth profiles, but as we will see in the next section that was not a common practice followed by manufacturers in early Bluetooth capable mobile phones.

Exploiting Bluetooth profiles oriented to file transfer for fun and profit

The mobile phone is one popular piece of equipment which embraced Bluetooth from the earliest stages of the technology. The implementation of Bluetooth in mobile phones soon lured the attention of security researchers interested in exploiting the resources offered by this kind of device: personal information, phone calls, sms, etc. Furthermore, the abuse in part of these resources had a direct impact on the user's balance, there was an economic risk. First attacks came up very soon. Attacks were mainly driven by exploiting a vulnerability in a particular Bluetooth profile due to incorrect implementation by the manufacturer. Some of the attacks [START_REF] Laurie | BlueSnarf[END_REF][START_REF] Laurie | BlueSnarf++[END_REF] aimed to exploit Bluetooth profiles oriented to file transfer, such as the Object Push Profile (OPP) and the File Transfer Profile (FTP), since these provide an interface to access the file system of the mobile phone; some other attacks [START_REF] Herfurt | BlueBug[END_REF][START_REF] Laurie | HeloMoto[END_REF][START_REF] Finisterre | Blueline, Motorola Bluetooth Interface Dialog Spoofing Vulnerability[END_REF] focused on Bluetooth profiles that provide an interface to the AT commands console, such as the Dial Up Networking Profile (DUN) and the Headset Profile (HSP), in order to access the modem in the mobile phone and be able to make phone calls.

The first major security issue related to Bluetooth mobile phones was published in 2003. It was called BlueSnarf [START_REF] Laurie | BlueSnarf[END_REF]. The BlueSnarf attack was based on the extraction of known filenames by establishing a connection to the Object Push Profile (OPP), which in case of early mobile phones did not require authentication. The purpose of the Object Push Profile (OPP) is the rapid exchange of objects such as business cards and meeting appointments between devices by using the command OBEX PUT. The attack exploited the lack of security mechanisms and the incorrect implementation of the OPP service by manufacturers, which allowed the execution of the command OBEX GET to retrieve files with known filename, such as the phone book stored in telecom/pb.vcf and the appointment calendar stored in telecom/cal.vs, without user consent. The vulnerability affected early handsets from vendors such as Motorola, Nokia, Sony-Ericsson and Siemens.

Later in 2005, the BlueSnarf attack was developed into a variation called BlueSnarf++ [START_REF] Laurie | BlueSnarf++[END_REF]. The main difference introduced by this attack was that instead of connecting through the Object Push Profile (OPP), a profile meant to send files only, the attacker could connect through the File Transfer Profile (FTP), which supports a larger range of operations and neither required authentication in early Bluetooth mobile phones. The OBEX FTP server supports send and receive operations and also list operation. Therefore, the attacker no longer needed to previously know the pathname of the file to download because the file system could be browsed. In first implementations, the OBEX FTP server was not restricted to a specific directory in the file system so the attacker could access arbitrary folders in the memory of the mobile phone or the external storage card, and read or write arbitrary files. Other supported operations included removal and overwriting of existing files.

Manufacturers were informed about these security issues but at that time they had no chance to issue an installable hotfix for the vulnerable products. The only possible action was to upgrade the firmware for upcoming models.

Anyway, the disclosure of this kind of attacks made an impact in the industry of mobile phones because it forced manufacturers to raise awareness about the security of Bluetooth. Successive models implemented security mechanisms of authentication and authorization to access Bluetooth profiles. Manufacturers also learned to properly configure a restricted directory for the FTP server so it presented no risk for the information system. The improvements seemed to be significant, in case any attacker aimed to break into the file system of a mobile phone, he would need to overcome two hurdles: the security mechanisms required to connect the File Transfer Profile (FTP) and the limited accessibility restricted by the directory where the FTP server is configured. These, however, are no longer big obstacles from our perspective.

On overcoming the security mechanisms

The first hurdle is related to an old problem that has been subject of study since the earliest stages of Bluetooth: how to overcome the security mechanisms built in Bluetooth. The standard procedure would be to simply pair up with the device. Actually this could be achieved by means of social engineering, if the attacker managed to persuade the user to pair up his mobile phone, but users of Bluetooth devices have become more cautious over the years.

Nevertheless, pairing is not the only option. It has been demonstrated that authentication can be broken if it is possible to eavesdrop the pairing of two given devices using Legacy Pairing, which is followed whenever at least one of the devices uses Bluetooth specification version 2.0 or prior, still a large portion of mobile phones in the market.

To succeed in eavesdropping the Bluetooth Legacy Pairing the attacker would need to use a Bluetooth sniffer, something that can be built from a consumer Bluetooth dongle [START_REF] Moser | Busting the Bluetooth Myth -Getting RAW Access[END_REF]. The sniffer would allow the attacker to capture the packets transmitted during the pairing conversation of two devices and unwhiten the data revealing the temporary keys exchanged [START_REF] Spill | BlueSniff: eve meets alice and bluetooth[END_REF][START_REF] Bittau | BTSniff[END_REF]. From this point, as explained in [START_REF] Shaked | Cracking the Bluetooth PIN[END_REF], the link key generated from the pairing algorithm can be cryptographically broken by brute forcing the PIN input until the temporary keys generated through out the algorithm match the temporary keys captured during the pairing. The response speed in software implementations [START_REF] Zoller | BTCrack[END_REF]12] on a Dual Core P4 2GHz is 0.035 seconds to crack a 4 digit PIN code and 117 seconds to crack an 8 digit PIN code; meanwhile in FPGA implementations it takes 0.001 seconds and 5.6 seconds respectively [START_REF] Zoller | Scheunentor Bluetooth[END_REF]. Considering this short period of time, we have succeeded in performing the attack in a real-time pairing scenario. Once obtained the link key, it becomes trivial for the attacker to impersonate one of the devices to satisfy the challenge-response scheme on the other, since the security function of authentication is based on the shared link key and the Bluetooth MAC address, which can be spoofed.

It may seem that whether two devices are already paired and communicating it would be impossible for the attacker to capture the temporary keys and crack the link key; however, in fact it would be easy to break the pairing relationship and force the devices to re-initiate the pairing process in order to eavesdrop it, as demonstrated in [START_REF] Shaked | Cracking the Bluetooth PIN[END_REF].

Authentication in Secure Simple Pairing, only used by recent Bluetooth 2.1 mobile phones, remains unbroken for the time being, although first security issues have appeared [START_REF] Andrew | Attacks on the Pairing Protocol of Bluetooth v2.1[END_REF].

On overcoming the restriction to access the file system

Our contribution is related to the second hurdle. We present a vulnerability that can be exploited to overcome the restriction to access the file system through the File Transfer Profile (FTP). This profile may require going through the security mechanisms, so after obtaining the proper authentication and authorization privileges, by any of the methods described, from now on we assume that the attacker can successfully establish a connection to the File Transfer Profile (FTP). [START_REF] Herfurt | BlueBug[END_REF] The OBEX FTP service directory traversal vulnerability

The OBEX FTP service

The OBEX FTP service is a software implementation of the File Transfer Profile (FTP). The File Transfer Profile (FTP) is intended for data exchange and it is based on the OBEX communications client-server protocol. The service is present in a large number of Bluetooth mobile phones, for example we used HTC Wildfire, HTC Desire HD and HTC Touch Pro for our research. The service can be discovered in devices nearby by sending Service Discovery Protocol (SDP) queries.

The following example is the output of a command for finding near devices supporting the File Transfer Profile (FTP) with sdptool, a tool available in Linux from kernel versions 2.4.6. Given the known profile name FTP, the command searches for Bluetooth devices nearby and inquires whether the File Transfer Profile (FTP) is supported.

gospel@ubuntu:~$ sdptool search FTP Inquiring ... Searching for FTP on 90:21:55:8C:2C:3A ... Service Name: OBEX File Transfer Service RecHandle: 0x10006 Service Class ID List:

"OBEX File Transfer" (0x1106) Protocol Descriptor List: "L2CAP" (0x0100) "RFCOMM" (0x0003) Channel: 4 "OBEX" (0x0008) Profile Descriptor List:

"OBEX File Transfer" (0x1106) Version: 0x0100

In this case we assume that Bluetooth devices nearby are configured in discoverable or visible mode. In case the devices are configured in non-discoverable or invisible mode, the attacker may still be able to find these by other means [START_REF] Whitehouse | War Nibbling: Bluetooth Insecurity[END_REF][START_REF] Spill | BlueSniff: eve meets alice and bluetooth[END_REF].

The OBEX FTP service provides the user with capability to share files just by moving or copying these into the restricted directory configured strictly for the server. The directory may be either inside the memory of the device or in the storage card. In Windows Mobile, the restricted directory is located by default in the following path of the file system: My Device\My Documents\Bluetooth Share. In Android, it is located in the following path of the file system: /sdcard.

While the service remains active, other devices can connect to the OBEX FTP server to list the content and download or upload files. The server is accessible with any OBEX FTP client, such as ObexFTP [START_REF] Zuckschwerdt | ObexFTP[END_REF], an open source implementation of OBEX protocol for Linux.

The following example is the output of a command for listing a directory with ObexFTP. Given the Bluetooth MAC address of the mobile phone and the path /, the command retrieves the content of the root directory of the FTP server.

gospel@ubuntu:~$ obexftp -b 90:21:55:8C:2C:3A -l "/" Browsing 90:21:55:8C:2C:3A ... Connecting..\done Tried to connect for 83ms Receiving "(null)"...|<?xml version="1.0"?> <!DOCTYPE folder-listing SYSTEM "obex-folder-listing.dtd"> <folder-listing version="1.0"> <folder name="LOST.DIR"/> <folder name=".footprints"/> <folder name="Music"/> <folder name="Photo"/> <file name="HTCDriver_2.0.7.17.exe" size="13702288" user-perm="R" created="20100519T195058Z"/> <folder name="albumthumbs"/> <folder name="dcim"/> <folder name="rssreader"/> </folder-listing>done Disconnecting../done

Implementation of the attack

We found it is possible to abuse the pathname parameter that is sent in a request to the OBEX FTP server in order to gain access to the entire file system of the mobile phone by performing a directory traversal.

A directory traversal is an exploit technique that gives access to restricted directories outside of the root directory of the server. The attack was original for HTTP servers back in 2000, for example it affected older versions of IIS and Apache servers.

To exploit the vulnerability, the sequence "../" should be inserted at the beginning of a pathname and the server would translate it as a reference to the directory located immediately above the current directory, the parent directory. For this reason the technique is also known as dot-dot-slash attack, directory climbing and backtracking.

We discovered we were able to perform with success the same directory traversal technique in the OBEX FTP service installed in HTC mobile phones running Windows Mobile and Android operating systems. A list of vulnerable versions is given in Table 1. Exploiting this issue allows a remote attacker, who previously owned authentication and authorization privileges, to list arbitrary directories, and read and write arbitrary files.

The OBEX FTP server is a 3rd party driver developed by HTC and installed on its devices running Windows Mobile and Android operating systems, so the vulnerability affects specifically to this manufacturer, but it might affect other manufacturers not aware of this security issue as well.

Scope

The directory traversal allows the attacker to reach directories located beyond the root directory of the OBEX FTP server and carry out the actions described below:

1. List arbitrary directories. Any directory within the file system can be browsed. This includes the flash memory of the device, the external storage card and the internal mass storage memory integrated in some particular mobile phones.

The following example is the output of a command for listing a directory with ObexFTP. Given the Bluetooth MAC address of an HTC / Android based mobile phone and the path ../, the command retrieves the content of the parent of the default directory of the FTP server, which happens to be the root directory of the disk file system.

gospel@ubuntu:~$ obexftp -b 90:21:55:8C:2C:3A -l "../" Browsing 90:21:55:8C:2C:3A ... Connecting..\done Tried to connect for 29ms Receiving "../"... Sending ".."...|done /<?xml version="1.0"?> <!DOCTYPE folder-listing SYSTEM "obex-folder-listing.dtd"> <folder-listing version="1.0"> <parent-folder/> <folder name="sqlite_stmt_journals"/> <folder name="config"/> <folder name="sdcard"/> <folder name="d"/> <folder name="etc"/> <folder name="cache"/> <folder name="system"/> <folder name="sys"/> <folder name="sbin"/> <folder name="proc"/> <file name="logo.rle" size="11336" user-perm="R" created="19700101T090000Z"/> <file name="init.rc" size="14664" user-perm="R" created="19700101T090000Z"/> <file name="init.goldfish.rc" size="1677" user-perm="R" created="19700101T090000Z"/> <file name="init.buzz.rc" size="3608" user-perm="R" created="19700101T090000Z"/> <file name="init" size="107668" user-perm="R" created="19700101T090000Z"/> <file name="default.prop" size="118" user-perm="R" created="19700101T090000Z"/> <folder name="data"/> <folder name="root"/> <folder name="dev"/> </folder-listing>done Disconnecting..-done 2. Read arbitrary files. Any file located in the file system can be downloaded. This may lead to access confidential data such as contacts, messages, emails or temporary internet files.

<parent-folder name="Windows" /> <file name="poutlook.lnk" created="20081021T030014Z" size="14"/> <file name="trojan.exe" created="20101025T082104Z" size="11"/> <file name="HTCStartUp.lnk" created="20081021T030014Z" size="28"/> </folder-listing> done Disconnecting..|done

Workaround

The directory traversal is a well-known technique and the solutions to fix the flaw are far documented. There are multiple methods to detect and prevent directory traversal.

1. Parse the pathname and filter malicious characters such as: ../ or ..\, ..\\ which also represent ../, and so on. Also characters encoded using percentencoding such as: %2e%2e%2f which represents ../, %2e%2e%5c which represents ..\, and so on. Also characters encoded using Unicode such as: ..%c0%af which represents ../, ..%c1%9c which represents ..\, and so on. 2. Process the pathname of the directory requested to list or the file requested to download, build the full path and prior to response, ensure it is inside the bounds of the root directory of the OBEX FTP server. 3. Implement chroot jails and specifically for the server process change the root directory of the file system for the directory where it is assumed the OBEX FTP server should operate only. The process would not be able to access directories or serve files outside its restricted directory.

The OBEX FTP service directory traversal for HTC devices running Windows Mobile [START_REF] Moreno | HTC / Windows Mobile OBEX FTP Service Directory Traversal Vulnerability[END_REF] was discovered in 2009. The security hotfix [START_REF]HTC: Hotfix to enhance the security mechanism of Bluetooth service[END_REF] is yet available for download in the support site and users can manually install it in the device.

In 2011 we discovered that the vulnerability also affected to HTC devices running Android and we succeeded in collaborating with the vendor. HTC will soon begin to distribute over-the-air the security hotfix for the affected products as an automatic update.

Conclusion

This paper introduces a vulnerability in multi-platform mobile phones which can be exploited via Bluetooth for data theft purposes. We show how trivial it is for an attacker to access arbitrary files containing confidential information after obtaining the proper privileges for connecting the File Transfer Profile (FTP), as easy as pairing up.

Our intention is to stress that in spite of the improvements made in security after the publication of first attacks to early Bluetooth mobile phones, there still may issues that manufacturers should take into consideration, such as the possibility of bringing attacks from computer environments into mobile devices, just as we succeeded in demonstrating with the directory traversal.

HTC 1

 1 mobile phones running Windows Mobile and Android are prone to a directory traversal vulnerability that allows a remote attacker to list arbitrary directories, and read and write arbitrary files. The vulnerability affects up to 20 Windows Mobile-based mobile phones shipped throughout 2008-2009 and up to 10 Android-based mobile phones shipped throughout 2010-2011.

Table 1 .

 1 HTC mobile phones affected by the vulnerability

	Operating system Windows Mobile	Android
		Windows Mobile 6 Professional Android 2.1
	Version	Windows Mobile 6 Standard	Android 2.2
		Windows Mobile 6.1 Professional
		Windows Mobile 6.1 Standard

HTC is the world's largest provider of Windows Mobile-based smart handheld devices and one of the largest provider of Android-based smart handheld devices.

Acknowledgments. We would like to thank Jean-Luc Beuchat for giving us much feedback on the paper.

The following example is the output of a command for downloading a file with ObexFTP. Given the Bluetooth MAC address of an HTC / Android based mobile phone and the pathname ../data/data/com.android.providers. contacts/databases/contacts2.db, the command retrieves the contacts database. Later, the database can be queried with SQL to obtain the contacts.

gospel@ubuntu:~$ obexftp -b 90:21:55:8C:2C:3A -g ".


Tânia L Monteiro
email: taniamonteiro@ppgia.pucpr.br

Marcelo E Pellenz
email: marcelo@ppgia.pucpr.br

Manoel C Penna
email: penna@ppgia.pucpr.br

Fabrício Enembreck
email: fabricio@ppgia.pucpr.br

Richard Demo Souza
email: richard@utfpr.edu.br

On Optimal Distributed Channel Allocation for Access Points in WLANs

Keywords: Wireless Networks, Channel Assignement, Distributed Constraint Optimization Problem

We propose a new distributed algorithm for optimal channel assignment in WLANs with multiple access points, applying a novel formulation for wireless networks based on Distributed Constraint Optimization Problem (DCOP). The DCOP approach allows to model a wide variety of distributed reasoning tasks of multi-agent applications. The proposed strategy is derived from a polynomialspace algorithm for DCOP named ADOPT, which is guaranteed to find the global optimal solution while allowing agents to execute asynchronously and in parallel. Our proposed algorithm, denoted DCAA-O, allows a group of APs to coordinate themselves in order to find the optimal channel allocation solution which minimizes the network interference. The algorithm performance is evaluated in terms of the required number of transmitted control messages among APs. It is shown that DCAA-O outperforms a recently proposed channel assignment strategy for WLANs.

Introduction

Typical deployments of Wireless Local Area Networks (WLANs) utilize multiple access points (APs) equipped with a single radio interface. Such networks can suffer from serious capacity degradation due to the half duplex nature of the wireless medium and also due to the interference between simultaneous neighboring transmissions. Fortunately the IEEE 802.11b/g and 802.11a standards [1], provide 3 and 12 non-overlapping channels, respectively, which could be used simultaneously within a neighborhood [START_REF] Aoun | Analysis of Capacity Improvements in Multi-Radio Wireless Mesh Network[END_REF]. The ability to utilize multiple channels, benefiting from the whole available spectrum, substantially increases the capacity of wireless networks [START_REF] Ramachandran | Interference Aware Channel Assignment in Multi-Radio Wireless Mesh Networks[END_REF]. The implementation of a dynamic and distributed algorithm for channel allocation is fundamental to keep the network operating at its maximum capacity. Several methods have been proposed for dynamic spectrum access, including pricing and auction mechanisms and graph coloring. Some promising cooperative strategies for channel assignment have been recently proposed in the literature for application in WLANs [START_REF] Chen | Site-Specific Knowledge and Interference Measurement for Improving Frequency Allocations in Wireless Networks[END_REF] and mainly in wireless mesh networks (WMNs) [START_REF] Ko | Distributed Channel Assignment in Multi-Radio 802.11 Mesh Networks[END_REF][START_REF] Li | Distributed Joint Resource Allocation in Multi-Radio Multi-Channel Wireless Mesh Networks[END_REF]. Specifically, our study about channel assignment focus on WLAN scenarios. The existing distributed algorithms do not guarantee optimal solution and may present convergence instability. As many WLAN scenarios are typically not large enough to make an optimization approach unfeasible, we identify the lack of an optimal distributed strategy for channel allocation in order to reduce interference between APs in the same physical neighborhood. Additionally, we consider that APs in the same transmission range can opportunistically communicate among themselves over wireless channel to coordinate a distributed optimization process that guarantee the best solution for the experienced interference scenario. Such coordination approach over wireless channel allows the proposed algorithm to be applied to a wireless network formed by APs belonging to different WLANs.

The paper presents two main contributions. The first one is the novel formulation for the channel assignment problem as a DCOP and the second one is the proposal of a new distributed and synchronous algorithm called DCAA-O (Distributed Channel Assignment Algorithm -Optimal), which is able to reach the optimal frequency assignment, irrespective of the network topology, number of APs, network density and available channels. We compare DCAA-O with a recently proposed measurement-based algorithm, Local-Coord (LO-A), presented by Chen et al. in [START_REF] Chen | Site-Specific Knowledge and Interference Measurement for Improving Frequency Allocations in Wireless Networks[END_REF]. It was shown in [START_REF] Chen | Site-Specific Knowledge and Interference Measurement for Improving Frequency Allocations in Wireless Networks[END_REF] that LO-A performs better than algorithms proposed in [START_REF] Leung | Frequency Assignment for IEEE 802.11 Wireless Networks[END_REF][START_REF] Mishra | Weighted Coloring Based Channel Assignment in WLANs[END_REF][START_REF] Mishra | A Client-Driven Approach for Channel Management in Wireless LANs[END_REF][START_REF] Leith | A Self-Managed Distributed Channel Selection Algorithm for WLANs[END_REF]. The remainder of this paper is organized as follows. Section 2 describes DCOP and ADOPT algorithm [START_REF] Modi | An Asynchronous, Complete Method for General Distributed Constraint Optimization[END_REF]. In Section 3 we present the novel formulation for channel assignment in WLANs via DCOP. The proposed algorithm is described in Section 4. The evaluation scenario and results are presented in Sections 5 and 6. Section 7 concludes the paper.

Background

In artificial intelligence research area, a distributed constraint optimization problem (DCOP), consists of a set of variables that are distributed to a group of collaborative agents as valued constraints, that is, constraints that are described as valuable functions that return values in a specific range. The goal is to optimize a global objective function, maximizing the weight of satisfied constraints [START_REF] Modi | An Asynchronous, Complete Method for General Distributed Constraint Optimization[END_REF].

Consider a set of N agents, A = {a 1 , a 2 , . . . , a N }, and a set of N values, D = {d 1 , d 2 , . . . , d N }, where each value d j is assigned to an agent a j and belongs to a finite discrete domain D j . For each pair of agents (a i , a j ) a cost function f ij (x, y) : D i × D j → R is defined. Agents have to coordinate themselves in order to find a set of values that optimize a global function establishing the costs for constraints. Therefore, the goal of a DCOP algorithm is to find the optimal set, denoted D * , whose values minimize a global cost function g * = g(D * ).

Modi et al. [START_REF] Modi | An Asynchronous, Complete Method for General Distributed Constraint Optimization[END_REF] proposed Simple-ADOPT, the first algorithm for DCOP that can find the optimal solution, using only localized asynchronous communication and polynomial space at each agent. Simple-ADOPT is a backtracking search algorithm that is executed asynchronously and in parallel on every agent, updating lower bounds on global solution quality. The Simple-ADOPT algorithm requires agents to be prioritized in a total order, making use of a spanning tree (ST), obtained through Depth-First Search (DFS) [START_REF] Freuder | Taking Advantage of Stable Sets of Variables in Constraint Satisfaction Problems[END_REF]. The authors use the term parent to refer to an agent's immediate higher priority agent in the ordering and child to refer to an agent's immediate lower priority agent in the ordering. Figure 1b shows the total order on agents for constraint graph of Figure 1a, represented by the ST generated by the DFS algorithm. Giving this ordering, an agent communicates its value d j to all linked lower priority agents, as indicated in Figure 1c, and communicates a lower bound cost to a unique higher priority agent as indicated in Figure 1d.

In order to change its value and lower bound cost information between agents, the Simple-ADOPT algorithm employs two types of control messages, denoted VALUE and VIEW messages respectively. The flow direction of VALUE and VIEW messages are also indicated in Figures 1c and1d, respectively. These graphs are required input parameters for the Simple-ADOPT algorithm and they will be denoted as VALUE graph and VIEW graph, for short. Let P value j and C value j be the set of parents and children of an agent a j in the VALUE graph, respectively. Likewise, let P view j and C view j be the set of parents and children of an agent a j in the VIEW graph. A pair agent/value of the form (a j , d j ) is called a view. The variable Currentvw j of an agent a j is the current set of views {(a i1 , d i1 ), (a i2 , d i2 ), . . . , (a il , d il )}, composed by the all linked ancestor's agent/value pairs, which means that {a i1 , a i2 , . . . , a il } ∈ P value j . The variable vw j of an agent a j stores the current view of agent a j regarding his parent agent a i ∈ P view j in the VIEW graph, denoted (a i , d i ) j . Therefore vw j = (a i , d i ) j ∈ Currentvw j of agent a j . The variable Currentvw j is sent to his parent agent a i ∈ P view j using a VIEW message. When a parent agent a i receives the VIEW message containing Currentvw j from child agent a j , it must perform a view compatibility test. We say that two views (Currentvw j and Currentvw i ) are compatible if the views vw associated to the same parent nodes in the VALUE graph have the same value d, which means that ∀vw = (a, d) ∈ Currentvw j we also have vw ∈ Currentvw i .

Simple-ADOPT begins by each agent a j choosing locally and concurrently a value d j ∈ D j . This value is sent to all its linked descendent agents {a k1 , a k2 , . . . , a kn } ∈ C value j , using VALUE messages. Then agents asynchronously wait for and respond to incoming messages. Given the received VALUE messages from parents agents, agent a j chooses his local value d j according to (1).

d j = x | min x∈Dj ∑ ai∈P value j f ij (d i , x) .
(1)

During the Simple-ADOPT algorithm execution, each agent a j must deal with three distinct cost values, the local cost, the current lower bound cost and the estimated lower bound cost. The local cost is defined by

lc j = ∑ ai∈P value j f ij (d i , d j ).
It is computed as sum of cost functions for all VALUE messages received from ancestors, using the chosen value d j obtained from (1). The current lower bound cost for subtree is computed according to sc j = ∑

a k ∈C view j z * k .
It is the sum of all estimated lower bound costs received from children agents in the VIEW graph, {a k1 , a k2 , . . . , a kn } ∈ C view j . The last one is the estimated lower bound cost defined by z * j = lc j + sc j , which is the sum of local cost lc j with the cost sc j . If an agent a j does not have any descendent, his estimated lower bound cost, z * j , is just its local cost lc j . Whenever an agent a j receives a VALUE message from a linked ancestor a i ∈ P value j , it stores the current received value (a i , d i ) into his Currentvw j variable, which represents a j 's current context. For its current context, the agent a j then reports the estimated lower bound cost z * j to his parent agent a i ∈ P view j , by a VIEW message. In its turn, his parent agent a i , will use the received estimated lower bound cost z * j in order to computed its current lower bound cost for subtree, sc i . The flow of VIEW messages is different from the flow of VALUE messages. The VALUE graph has its origin on the DFS tree plus all conflict edges existing between vertices in the undirected constraint graph G = (V, E) that is not represented in the DFS tree. Meanwhile the VIEW graph is exactly the DFS tree. The parent agent receives a VIEW message but throw away this message when vw j / ∈ Currentvw i . This situation can happen in two cases: either the parent agent a i has a more up-to-date current view than its child a j or a j has a more current up-to-date view than its parent a i . When an agent a j reports to its parent P view j , its estimated lower bound cost z * j , locally the agent assumes the value d j that has minimized z * j . Finally, when an agent a j receives a VALUE message, it updates its current context by updating the current values d i of its parents. The agent then deletes its stored cost z * j , since it may now be invalid. Simple-ADOPT by storing only one current view, has linear space requirements at each agent, considering the number of variables that an agent can assume, represented by the finite discrete domain D j . The algorithm reaches a stable state when all agents are waiting for incoming messages. Then the complete assignment chosen by the agents is equal to the optimal assignment set, denoted D * , whose values minimize a global cost function, g * = g(D * ).

Modeling Channel Assignment via DCOP

In WLANs a large number of access points may be operating in the same region, leading to a scenario where the management of wireless channels is extremely important because co-channel and adjacent-channel interference can significantly reduce the network performance. Consider the problem of optimizing the throughput of a WLAN with multiple APs. This requires that channels of all APs have to be set to maximize the signal-to-interference ratio. As the number of possible channels grows exponentially with the number of APs, we have a NP complex combinatorial optimization problem [START_REF] Briggs | Optimal Channel Allocation for Wireless Cities[END_REF].

The approach of this work is to propose a distributed synchronous parallel method based on multi-agents concept [START_REF] Wooldridge | Jennings: Intelligent Agents Theory and Practice[END_REF], allowing any set of APs coordinate for searching the optimal solution for the channel allocation problem. Since the domains are inherently distributed, we require a method where agents can optimize a global function in a distributed way, using only local coordination (communication with neighboring agents). As our challenge is not only to ensure computational time but also to ensure an acceptable amount of exchanged messages between agents, we adopted a distributed synchronous and parallel solution, that unlike some conventional distributed approaches as Asynchronous Backtracking (ABT) [START_REF] Yokoo | Distributed Constraint Satisfaction: Fondation of Cooperation in Multi-agent Systems[END_REF] and the Synchronous Branch and Bound (SynchBB) algorithm in [START_REF] Hirayama | Distributed Partial Constraint Satisfaction Problem[END_REF], ensures the optimal solution. The considered environment refers to one or more stationary wireless networks, composed by APs arbitrarily distributed over an area, where each AP is equipped with a single IEEE802.11b radio interface [1]. We consider the reduced problem where all radio interfaces across the network use omnidirectional antennas and have identical transmission powers. The goal is find the best channel allocation solution for each AP in order to improve the overall network performance.

In order to apply DCOP an undirected constraint graph G = (V, E) should be obtained from the physical network topology. Consider as an example a WLAN scenario composed of 12 APs, whose physical layout is shown in Figure 2. The dotted lines in Figure 2 represent the connectivity between APs. This means that their respective channel allocations will affect the performance of both due to the multiple access contention and interference. Therefore, the graph represented by the connections between APs in Figure 2 constitutes the constraint graph for the channel allocation problem. In such case, the set of vertices V of the constraint graph G represents the APs, and the set of conflict edges E ⊆ V 2 is represented by connectivity links between APs. As described in Section 2 agents must be prioritized in a total order, making use of a spanning tree. An initialization procedure using a predefined common control channel is required allowing each AP to identify the APs in the neighborhood (constraint graph) and also to configure his logical ordering in the VALUE and VIEW graphs. This can be accomplished by means of a distributed spanning tree algorithm. After the logical graph construction each AP knows its parent, child, and linked descendants. Following the approach used in [START_REF] Briggs | Optimal Channel Allocation for Wireless Cities[END_REF] we consider a cost function metric based on channel spectrum overlapping. Specifically in North America and Europe, there are 11 different channels that an AP may select in IEEE802.11b/g 2.4GHz ISM band. This ISM band is allocated between 2400 and 2483MHz, with channel central frequencies starting at 2412MHz and spaced at 5MHz intervals to 2462MHz. As the channel bandwidth is about 22MHz, there is a substantial spectrum overlap between adjacent channels. If adjacent APs select overlapping channels, it will be induced a spectral interference between concurrent transmissions or multiple access contention. An accurate interference model is necessary taking into account the level of spectrum overlap. For instance, a 5.5 or 11Mbps DSSS (Direct Sequence Spread Spectrum) unfiltered modulated signal has a power spectrum behavior described by:

S(n, f ) =    sin[2πX (n,f )] 2πX (n,f ) 2 , for X (n, f ) ̸ = 0 1, for X (n, f ) = 0 . ( 2
)
where

X (n, f ) = f -2412-5(n-1)

BW

, BW is the null-to-null channel bandwidth and n is the channel number (n = 1, 2, . . . , 11). The WLAN cards employ an IF filtering on both transmit and receive paths in order to reduce sidebands power. The approximated IF filter power spectrum response is defined by

F(n, f ) = [1 + 2.6 X (n, f )]
-6 [START_REF] Briggs | Optimal Channel Allocation for Wireless Cities[END_REF].

It has 3dB bandwidth of 17MHz and stopband 50dB down at ±22MHz. From (2) we can now determine the channel overlap factor, which determines the co-channel interference level between two APs. The spectrum overlap factor SO(n, m) between the channel number n and the channel number m is given by ( 3). The overlap factor can be normalized by the maximum overlap factor which occurs when both channels are the same. The normalized factor is defined by ( 4) as a function of the channel spacing, c spc = n -m, where n ≥ m and c spc ∈ {0, 1, 2, . . . , 10}. Table 1 presents the normalized overlap factor SO norm as a function of channel spacing c spc , obtained using (4).

Its is important to point out that the numerical results shown in Table 1 may vary for different chipset and filter configurations of the WLAN card.

SO(n, m) = ∫ 2700 2200 S(n, f )F(n, f )S(m, f )F(m, f ) df . ( 3
)
SO norm (c spc ) = 1 SO(1, 1) ∫ 2700 2200 S(1, f )F(1, f ) S(c spc + 1, f )F(c spc + 1, f ) df . (4)
In our DCOP formulation, the selected value d j of an agent a j represents the channel selection number of the AP j , therefore the domain of d j is defined as D j = {1, 2, . . . , 11}. For a pair of connected agents (pair of interfering APs) in the constraint graph, the cost function for a pair of values

(d i , d j ) is defined as f ij (x, y) : D i × D j →
R where the values in R represent the interference overlap factors of Table 1. The APs by coordinating themselves have to find a set of channel allocation values, D * , that optimizes a global function establishing the costs for constraints that minimize the total amount of interference. In practice, the channel overlap factor can be weighted by a normalized path loss weighting factor denoted by α ij where 0 ≤ α ij ≤ 1, resulting in a

Proposed Algorithm

The Simple-ADOPT algorithm operates asynchronously and in parallel on every agent. In many multi-agent applications this is not a restriction but, in our case, this is an undesirable characteristic because we want to minimize the number of overhead messages among APs. Therefore, we derived DCAA-O from Simple-ADOPT keeping the optimality conditions and imposing synchronous message control at agents. Our algorithm employs the same basic notation for parents and children nodes, as well as the definition of VALUE and VIEW graph. The pseudocode of the proposed DCAA-O method is shown in Algorithm 1. The parameters listed below are also based on the description of ADOPT, however some changes were necessary for the development of our algorithm.

; sc j (d t j ) = ∑ a k ∈C view j z k (d t j ): Subtree cost of a j ; z j (d j ) = lc j (d j ) + sc j (d j ) where d j = x | min x∈Dj lc j (x) + sc j (x);
The choice of the value d j is an important point of the distributed algorithm execution. A given node a j will iterate with its subtree, through its VALUE and VIEW children, for different temporary d t j ∈ D j choices. During the iteration, the node a j builds its variables, LocalCosts j and SubTreeValues j . After testing all d t j , the node is able to identify the value d j that minimizes the cost of the subtree in the context represented by z j (d j ). From this time the node a j sends a VIEW message to its parent a i ∈ P view j , that can continue with its procedure for choosing its local channel d i . The DCAA-O algorithm can initiate the channel reallocation in a network composed of multiple APs, when an AP identifies co-channel or adjacent channel interference. In a preliminary step the AP a j initiates a distributed algorithm for calculating the spanning tree [START_REF] Gallager | A distributed algorithm for minimumweight spanning trees[END_REF][START_REF] Gatani | An efficient distributed algorithm for generating multicast distribution trees[END_REF] that allows the definition of VALUE and VIEW graphs on all nodes. After the execution of the algorithm, as presented in Algorithm 1, the root node sends a message identified as TERMINATE, containing optimal allocation solution for all other APs through the graph VALUE.

The algorithm DCAA-O was implemented and simulated in a distributed way, using a library of discrete event simulation denoted SIMPATICA [19], based on the actors/messages paradigm. According to this paradigm, a simulation model is composed by a set of actors (or tasks) that communicate among them using messages. This library allowed us to simulate a distributed synchronous environment through three kinds of entities: task, queue and message. Each AP is implemented as a task and has three queues for receiving messages, VIEW QUEUE, VALUE QUEUE, and TERMINATE QUEUE, respectively.

Evaluation Scenario

The performance of DCAA-O was evaluated on random generated network topologies. We considered topologies of 4, 9 and 16 nodes, with graph densities of 1, 2, 3, 4 and 5, when applicable. A graph with link density d has d • n links, where n is the number of nodes in the graph [START_REF] Modi | An Asynchronous, Complete Method for General Distributed Constraint Optimization[END_REF]. For a given number of nodes, a total of 30 random topologies was generated for each density. As a first study scenario, we allowed the APs to select the corresponding channel from an available set with only three channels, composed of the tree non-overlapping channels {1, 6, 11}. In the second scenario APs can select one among 11 available channels. We compared the proposed algorithm to the scalable distributed algorithm, denoted Local-Coord (LO-A), recently proposed by Chen at al. [START_REF] Chen | Site-Specific Knowledge and Interference Measurement for Improving Frequency Allocations in Wireless Networks[END_REF]. LO-A is a simple distributed algorithm, featuring a good balance between solution quality and number of messages exchanged between the APs. However to their considered environment, an AP needs to locally coordinate with others APs via a wired backbone network for channel switching. For comparison purposes, LO-A messages are exchanged among APs via a pre-defined wireless control channel as for DCAA-O.

Simulation Results

The performance of DCAA-O was evaluated in terms of the average number of exchanged messages between APs for convergence to optimal solution. The LO-A algorithm was used as a benchmark algorithm. The stopping criterion for LO-A algorithm concerns to a minimum number of iterations without any improvement or new channel allocation among the APs. We considered a lower bound of 50 iterations for LO-A. This value was determined by simulation as an appropriate criterion to stop the execution of the LO-A algorithm. 3. For the case of 3 available channels, DCAA-O presented lower values for the average number of exchanged messages compared to LO-A (around 50% less). However for the case of 11 channels, although reaching the optimal solution to the cost function, DCAA-O requires a larger number of exchanged messages for convergence than LO-A. As shown in Figure 4, it is important to note that DCAA-O always finds the optimal solution for every scenario, whereas LO-A algorithm achieves suboptimal values for graph densities 1, 2 and 3. For the case of 9 APs with density 4, the suboptimal values obtained by LO-A are close to optimal solution found by DCAA-O. The same conclusions also apply for scenarios with greater densities or with a larger number of nodes, as we observed in topologies with 16 APs. The results for 16 APs were omitted for brevity. It is important to point out that we also validated the DCAA-O solution optimality in each scenario by means of exhaustive search in the solution space. It is important to point out that the final global cost is directly related to the throughput performance metric because it measures the overall network interference. Therefore, by using the analytical cost model we do not need to run extensive throughput simulations.

Conclusions

The work reported in this paper combines artificial intelligence (AI) research methods with wireless network optimization problems, addressing the channel assignment in WLANs as a distributed constraint optimization problem. The proposed algorithm (DCAA-O) achieves the optimal solution for the channel assignment problem, therefore reducing the adjacent channel interference and maximizing the network performance.

The required average number of exchanged messages among APs to reach optimal solution demonstrated to be inferior to LO-A for some specific scenarios. Scenarios with a larger number of APs and higher densities must be investigated in order to reduce the number of exchanged messages in DCAA-O.

Fig. 1 .

 1 Fig. 1. DCOP Example: (a) Constraint graph; (b) Constraint graph of totally ordered agents; (c) Graph of VALUE messages; (d) Graph of VIEW messages

Fig. 2 .

 2 Fig. 2. Example of a physical WLAN deployment.

Fig. 3 .

 3 Fig. 3. Performance of DCAA-O and LO-A (9 APs)

Fig. 4 .

 4 Fig. 4. Final global cost value for DCAA-O and LO-A (9 APs)

Table 1 .

 1 Adjacent Channel Interference Factor ij f ij (x, y), between the APs. The parameter α ij can be computed by agent a i based on the received signal strength intensity (RSSI) of the received message from agent a j . In this study we consider the worst case interference scenario where α ij = 1.

	Channel Spacing Overlap Factor
	0	1
	1	0.7272
	2	0.2714
	3	0.0375
	4	0.0054
	5	0.0008
	6	0.0002
	7 -10	0
	local cost, α

  Table 2 presents the comparison results for topology scenarios Receive VIEW Message (a k , z k (d k ), SubTreeValues k (d k )); APs. In this case the random generated network topologies may only have graph density one. The DCAA-O algorithm presented a number of exchanged messages at least 90% smaller than LO-A. The final global cost value obtained by both algorithms was the same and is omitted here for brevity. The performance evaluation of DCAA-O and LO-A for random topologies formed by 9 APs is shown in Figure

	Algorithm 1: DCAA-O
	1 Procedure Initialization
	2	Currentvwj = ∅;
	3	LocalCostsj = ∅;
	4	SubTreeValuesj(dj) = ∅ ∀dj ∈ Dj;
	5 end
	6 Procedure RootNode
	7	forall the (d t 1 ∈ D1) do
	8	Send VALUE Message(a1, d t 1 ) ∀a k ∈ C value 1	;
	9	forall the (a k ∈ C view 1	) do
	10
	11	SubTreeValues1(d t 1 ) =
		SubTreeValues1(d t 1 ) ∪ SubTreeValues k (d k );
	12	sc1(d t 1 ) = sc1(d t 1 ) + z k (d k );
	13	end
	14	Add [d t 1 , 0, sc1(d t 1 )] to LocalCosts1;
	15	end
	16	d1 = x | min x∈D 1	sc1(x), where sc1(x) ∈ LocalCosts1;
	17	Send TERMINATE(SubTreeValues1(d1)) ∀a k ∈ C view 1	;
	18 end
	19 Procedure OtherNodes
	20	while TERMINATE QUEUE= ∅ do
	21	Receive VALUE Message(ai, d t i );
	25	Add (ai, d t i ) to Currentvwj;
	26	end
	27 28	forall the (d t j ∈ Dj) do lcj(d t j ) = ∑ a i ∈Currentvw j fij(d t i , d t j );
	29	scj(d t j ) = 0;
	30	Add [d t j , lcj(d t j ), scj(d t j )] to LocalCostsj;
	31	end
	32	if (C value j	̸ = ∅) then
	33	forall the (d t j ∈ Dj) do
	34	Send VALUE Message(aj, d t j ) ∀ a k ∈ C value j	;
	35	forall the (a k ∈ C view j	) do
	36			Receive VIEW Message
	(a 37 SubTreeValuesj(d t j ) =
				SubTreeValuesj(d t
	39	end
	40	end
	41	end
	42	dj = x | min x∈D j	lcj(x) + scj(x), where lcj, scj ∈ LocalCostsj;
	43	zj(dj) = lcj(dj) + scj(dj);
	44	SubTreeValuesj(dj) = SubTreeValuesj(dj) ∪ {(aj, dj)};
	46	end
	47	Receive TERMINATE(SubTreeValues1(d1));

22

Add (ai, d t i ) to Currentvwj;

23 forall the (ai ∈ P value ′ j ) do 24 Receive VALUE Message(ai, d t i ); k , z k (d k ), SubTreeValues k (d k )); j ) ∪ SubTreeValues k (d k ); 38 Add z k (d k ) to scj(d t

j ) in LocalCostsj; 45 Send VIEW Message(aj, zj(dj), SubTreeValuesj(dj)) to ai ∈ P view j ; 48 Set channel dj = dm | aj = am, (am, dm) ∈ SubTreeValues1(d1); with 4

Table 2 .

 2 Average Number of Messages -Topologies with 4 APs

	Available Number of Channels DCAA-O LO-A
	3 Channels	29	1324
	11 Channels	277	2140

Acknowledgments

This work was partially supported by CAPES (Brazil), under Grant RH-TVD: AUX-PE-RH-TVD 249/2008.

Send TERMINATE(SubTreeValues1(d1)) ∀a k ∈ C view j ;