Laszlo Gyongyosi
email: gyongyosi@hit.bme.hu

Sandor Imre

Private Quantum Coding for Quantum Relay Networks

Keywords: Quantum communications, private quantum channel, quantum polar encoding. Phase Amplitude 1 Amplitude, Z) Data (Phase, X) Amplitude, Z)

The relay encoder is an unreliable probabilistic device which is aimed at helping the communication between the sender and the receiver. In this work we show that in the quantum setting the probabilistic behavior can be completely eliminated. We also show how to combine quantum polar encoding with superactivation-assistance in order to achieve private communication over noisy quantum relay channels.

Introduction

The relay encoding scheme for classical communication channels was introduced by Cover and Gamal [START_REF] Cover | Capacity theorems for the relay channel[END_REF]. The relay encoding with classical polar coding was studied by Andersson et al. [START_REF] Andersson | Nested Polar Codes for Wiretap and Relay Channels[END_REF], using their nested polar relay channel codes. Here we show that relay encoding can also be used in the quantum setting to achieve enhanced private communication [START_REF] Devetak | The private classical capacity and quantum capacity of a quantum channel[END_REF] between the sender and receiver. Our two main goals can be summarized as follows: First, by constructing capacity-achieving quantum polar codes we would like to maximize the transmittable private classical information over the quantum relay channel. Second, we would like to prove that using superactivation-assistance [START_REF] Smith | Quantum Communication with Zero-capacity Channels[END_REF] the reliability of the quantum relay encoder can be maximized and the probabilistic behavior can be completely eliminated.

This paper is organized as follows: In Section 2 we discuss the proposed encoding scheme. In Section 3 we show the quantum relay encoder. In Section 4 we present the theorems and proofs. Finally, in Section 5, we conclude our results.

Our Private Encoding Scheme

The channel polarization scheme introduced by Arikan [START_REF] Arikan | Channel polarization: A method for constructing capacity achieving codes for symmetric binary-input memoryless channels[END_REF] makes it possible to achieve the symmetric capacity of a noisy communication channel. The symmetric capacity is the highest rate at which the channel can be used for communication if the probability of the input letters is equal [START_REF] Arikan | Channel polarization: A method for constructing capacity achieving codes for symmetric binary-input memoryless channels[END_REF][START_REF] Mahdavifar | Achieving the Secrecy Capacity of Wiretap Channels Using Polar Codes[END_REF][START_REF] Smith | Quantum Communication with Zero-capacity Channels[END_REF]. The polar coding technique was extended to secure communication over classical channels by Mahdavifar and Vardy [START_REF] Mahdavifar | Achieving the Secrecy Capacity of Wiretap Channels Using Polar Codes[END_REF]. The quantum polar coding scheme was studied by Wilde and Guha [START_REF] Wilde | Polar codes for classical-quantum channels[END_REF] and by Renes et al. [START_REF] Renes | Efficient Quantum Polar Coding[END_REF]. Later, the results of [START_REF] Renes | Efficient Quantum Polar Coding[END_REF] were extended by Wilde and Renes [START_REF] Wilde | Quantum polar codes for arbitrary channels[END_REF], [START_REF] Wilde | Polar codes for private classical communication[END_REF] for arbitrary quantum channels. Gyongyosi and Imre have given a solution for the polaractivation of private classical capacity of noisy quantum channels [START_REF] Gyongyosi | Quantum Polar Coding for Noisy Optical Quantum Channels[END_REF][START_REF] Gyongyosi | Private Classical Communication over Zero-Capacity Quantum Channels Using Quantum Polar Codes[END_REF]. The superactivation is an extreme violation of the additivity of quantum channel capacities and enables the use of zero-capacity quantum channels for communication [START_REF] Smith | Quantum Communication with Zero-capacity Channels[END_REF], [START_REF] Gyongyosi | Algorithmic Superactivation of Asymptotic Quantum Capacity of Zero-Capacity Quantum Channels[END_REF], [START_REF] Brandao | Public Quantum Communication and Superactivation[END_REF][START_REF] Brandao | When does noise increase the quantum capacity?[END_REF][START_REF] Imre | Wireless Myths, Realities and Futures: From 3G/4G to Optical and Quantum Wireless[END_REF]. In this work we show, that this effect can also be exploited. The relay encoder is placed between the Alice and Bob and intended to help Bob receiving messages from Alice [START_REF] Cover | Capacity theorems for the relay channel[END_REF].

The channel which contains an relay encoder between Alice and Bob is called the relay channel [START_REF] Cover | Capacity theorems for the relay channel[END_REF]. In case of a degraded relay channel, the relay receiver works better than Bob's receiver  and the relay encoder can cooperate with original encoder to help to decode the message on Bob's side [START_REF] Cover | Capacity theorems for the relay channel[END_REF], [START_REF] Andersson | Nested Polar Codes for Wiretap and Relay Channels[END_REF]. In our scheme we use polar encoding to achieve the private classical capacity.

2  2  1 
For a quantum channel  the symmetric classical capacity is equal to the quantum mutual information   : I AB [START_REF] Imre | Quantum Computing and Communications -An Engineering Approach[END_REF], [START_REF] Imre | Advanced Quantum Communications -An Engineering Approach[END_REF], [START_REF] Bradler | Trade-off capacities of the quantum Hadamard channels[END_REF],

    1 lim max : n sym n CI n A B     , (1)
where denotes the n channel uses, and the probability distribution of the input states is assumed to be uniform [START_REF] Arikan | Channel polarization: A method for constructing capacity achieving codes for symmetric binary-input memoryless channels[END_REF], [START_REF] Wilde | Polar codes for classical-quantum channels[END_REF]. The symmetric private classical capacity [START_REF] Devetak | The private classical capacity and quantum capacity of a quantum channel[END_REF], [START_REF] Imre | Advanced Quantum Communications -An Engineering Approach[END_REF] can be expressed as follows:

n         1 lim max : : n sym n PI A B I n  A E     , (2)
where  :  I AE is the quantum mutual information function assuming a symmetric channel between Alice and Eve. In Fig. 1, we depict our encoding scheme [START_REF] Gyongyosi | Quantum Polar Coding for Noisy Optical Quantum Channels[END_REF]. Alice encodes her private message M into the phase using the X basis and then into the amplitude using the Z basis [START_REF] Gyongyosi | Quantum Polar Coding for Noisy Optical Quantum Channels[END_REF]. The phase carries the data, while the amplitude is the key for the encryption i.e., in our scheme Alice first encodes the phase (data) and then the amplitude (key). Bob applies it in the reverse direction using his successive and coherent decoder, and finally gets M  as follows [START_REF] Renes | Efficient Quantum Polar Coding[END_REF], [START_REF] Boileau | Optimal State Merging Without Decoupling[END_REF]: he first decodes the amplitude (key) information in the Z basis [START_REF] Imre | Quantum Computing and Communications -An Engineering Approach[END_REF]. Then Bob continues the decoding with the phase information, in the X basis [START_REF] Imre | Quantum Computing and Communications -An Engineering Approach[END_REF]. According to our encoding scheme, the symmetric private classical capacity sym P is defined as AB is the symmetric mutual information that can be achieved by the phase information between Alice and Bob [START_REF] Arikan | Channel polarization: A method for constructing capacity achieving codes for symmetric binary-input memoryless channels[END_REF], [START_REF] Gyongyosi | Quantum Polar Coding for Noisy Optical Quantum Channels[END_REF], [START_REF] Imre | Advanced Quantum Communications -An Engineering Approach[END_REF]. To construct the input polar codeword sets, we use the notation of 'good'

                 
 ,    and 'bad'  ,   
, where 0.5

 

[3] channels for the transmission of phase and amplitude. The set of polar codewords which can transmit private information (both amplitude and phase) is denoted by:

in S     ,, in amp phase S      . ( 4
)
All of other input codewords cannot transmit private classical information, however some of them can be used to transmit non private classical information. These codewords are defined by the set as follows:

bad S                  ,, ,, ,, .
From set , we define the completely useless codewords which cannot transmit any classical information as

bad S     ,, amp phase        , (6)
while the 'partly good' (i.e., can be used for non private classical communication) input codewords will be denoted by

    1 ,, amp phase         (7)
and

    2 ,, amp phase         , ( 8
)
where 0.5   is a fixed constant [START_REF] Arikan | Channel polarization: A method for constructing capacity achieving codes for symmetric binary-input memoryless channels[END_REF]. The working process of the polar-encoding based quantum relay encoder can be summarized as follows: The first encoder



. In the next step, the quantum relay encoder with probability adds the amplitude information to the phase information, using polar codes from the set , and then sends it to Bob. Otherwise, with probability it leaves unchanged

2  2 p    2 p   2 ,\   1  , phase    2  2 
and transmits to Bob. The problem with the quantum relay encoder is that it is unreliable since it works in a probabilistic way, which also makes the channel  too noisy.

Our Quantum Relay Encoder

Our proposed quantum relay encoder is depicted in Fig. 2. Alice would like to send her l-length private message M to Bob. The first encoder can encode only phase information, while the quantum relay encoder can encode only amplitude information. The quantum relay encoder can add the amplitude information to the message A received from only with success probability For a degradable quantum relay channel

2   1  2 0 p 2  2 1  1    . In
      ,, , , pBBAA pBAA pBBA      , (10)
where

  A A B   B  is a Markov chain and     ,, , pBB AA pBB A     .
  d decoder  can            12 ,
max min , : :

:, :

sym pAA CI A A A B A IABBA IA   , , B I BA         (1  1)
which is equivalent to the following definition. Let be the classical capacity of the channel between encoder and quantum relay encoder is

 n cu            min , sym sym C C      . )
Our quantum relay

         22 2 ,\ 1 ,, phase phase Bp p            (13)
with

    2 2 ,\ phase Bp       or     2 1, phase Bp  ,    
The private capaci In this section we present the theorems and give the proofs. Our result on the reliability of the proposed quantum relay encoder is summarized in Theorem 1.

e pp         , ( 18
)
where and is the 50% erasure channel [START_REF] Smith | Quantum Communication with Zero-capacity Channels[END_REF]. The channel with probability p is a  , Alice will feed the following entangled system to the inputs (denoted by A and C) of the joint channel [START_REF] Smith | Quantum Communication with Zero-capacity Channels[END_REF]:

0 p  1 e   2   channel (i.e.,
  11 11
1 00 00 00 00 2

AC ACAC          , (19)
where  is evaluated as follows: .

 1 00 11 2     is a Bell-state. The coh I quantum coherent information of for the input system 1   2 AC  is      
                 
Proof: For the input system, the quantum coherent information of is evaluated as follows:

12                  12

Conclusion

In this paper we have shown that by combining the polar coding with superactivationassistance, the reliability of the quantum relay encoder can be increased and the rate of the private communication over the superactivation-assisted relay quantum channel can be maximized at the same time. The proposed encoding scheme can be a useful tool in private quantum communications.

Fig. 1 .

 1 Fig. 1. Private communication of Alice and Bob over a quantum channel in presence of an eavesdropper Eve. The quantum channel has positive private classical capacity if it can send both phase and amplitude.

2  1 

 21 encodes the phase information into the codeword A and then sends it to , using set 2

  quantum channel between the quantum relay encoder and Bob's decoder .

Fig. 2 .

 2 Fig. 2. The quan information, th reliable, it works tum rela ann e relay encoder. The first encoder encodes onl e second adds only plitude information. The quantum relay encoder is no with suc y ch cess pr el with th the am obability

1  2 

 12

  the combination of the superactivation-assistance and polar encoding ref

Theorem 1 . 2  2 

 122 Using the unreliable quantum relay encoder with .Proof: First, Alice generates codeword A with . In the next step, she transmits it over 1 A . It will be transmitted over , which will result in Bob's input B. For positive private classical capacity , both the phase and the amplitude have to be transmitted; however, the encoders and individually cannot encode both of them. Using channel 0

  following lower bound for the P symmetric private classical capacity of :



  , since the maximum of the rate of any private communication over the relay channel[START_REF] Gyongyosi | Quantum Polar Coding for Noisy Optical Quantum Channels[END_REF]

Acknowledgment

The results discussed above are supported by the grant TAMOP-4.2.1/B-09/1/KMR-2010-0002, 4.2.2.B-10/1--2010-0009 and COST Action MP1006.


Jeffrey Van Den Brande
email: j.vandenbrande@student.utwente.nl

Aiko Pras
email: a.pras@utwente.nl

The Costs of Web Advertisements while Mobile Browsing

Keywords: mobile Internet, web advertisements, roaming, accounting

Tablet PCs, iPads and mobile phones all include facilities to browse the mobile Internet. The costs of mobile Internet access may become extraordinary, however, when the data limit is exceeded or when the user is roaming abroad without a roaming data plan. Since users may see advertisements as unwanted traffic, they can be confronted with a bill of which a significant part is caused by data they did not ask for. The goal of this paper is to investigate the amount of data generated by advertisements when browsing, and the potential costs of such advertisements for average users. Our analysis shows that web advertisements take up 7-9% of the total data traffic, depending on Flash usage.

Introduction

Wireless Internet access is an important feature for users of mobile devices such as PDAs, mobile phones, tablet PCs, iPads etc. [START_REF]Individuals -Mobile Internet access[END_REF]. Like users of fixed PCs, mobile users receive advertisements on web pages, for which they may have to pay. Currently many providers offer relatively cheap flat-fee data plans for mobile Internet usage and some even provide some flat-fee plans for roaming. At this moment there are many discussions, however, since several providers want to reduce or even stop such offerings, as according to these providers such plans cost more money for investments in their infrastructure than the plans bring in [START_REF] Tweakers | providers draaien de klok terug[END_REF]. Also, when mobile users access the Internet outside the provider's base country (roaming), the costs of accessing the Internet are usually not covered by the regular flat fee that was valid at home. It is only recently that the European Commission decided to force providers to limit their roaming costs inside the European Union [30]. Finally, even if the Internet is accessed in the provider's base country, users may have to pay additional money in case they exceed the limit of their data plan. Although plugins exists for browsers on fixed PCs, such as Adblock Plus and Opera's URL filtering, such plugins are generally not available for mobile devices. Therefore it is interesting to investigate whether the amount of data (and thus the costs) generated by web advertisements is an issue that is worth to consider, or can be ignored. Although many people may have an opinion on this, the scientific evidence to proof such opinion hardly exists.

The goal of this paper is therefore to perform such investigation, and give initial results. Since the number of pricing options is overwhelming, it is explicitly not the intention to present a complete analysis of all mobile Internet costs.

The research questions that will be investigated in this paper are as follows 1 :

1. Do web advertisements take up a significant amount of traffic? 2. Do these amounts vary per browser and over time? 3. Is there a significant difference when Flash is enabled? 4. Can we estimate the costs of web advertisements for roaming users?

The approach to answer these questions, is to set-up a measurement environment in which a configurable proxy server is used as advertisement filter. To mimic user behavior, an AutoBrowse program is used to retrieve hundred of the most popular URLs. With such set-up, the answer to the first question can be found by measuring the amount of web data with an active, and with an inactive proxy filter. To answer the second question, measurements will be repeated multiple times and with different browsers. By enabling and disabling Flash, is is possible to answer the third question. The approach to answer the fourth question is to search the web for pages showing the average (prepaid) costs of mobile Internet. Since the amount of web traffic generated by an average advertisement is known from the previous questions, we can calculate the costs of a single advertisement by multiplying the amount of web traffic with these average costs. Once we found the average number of pages downloaded per day, we can also calculate monthly costs. We focussed, as examples, on the Netherlands and the United States. Note that, due to the overwhelming number of pricing options, the often confusing information on roaming costs and the fact that mobile operators sometimes 'reshape' data (for example, to re-encode pictures), our answer to the fourth research question remains limited to an initial estimation; a complete answer to this question would be too intricated to fit within the scope of this workshop paper.

The structure of this paper is as follows. Section 2 introduces the general topic of Internet accounting and discusses the related work. The approach to tackle the research questions 1, 2 and 3 will be presented in Section 3; the answers to these questions is provided in Section 4. The last research question is analyzed in Section 5, whereas the conclusions can be found in Section 6.

Related Work

Internet accounting is a relative well-established research area, which received quite some attention with the invent of INTSERV [START_REF] Braden | Integrated Services in the Internet Architecture: an Overview[END_REF] and DIFFSERV [START_REF] Blake | An Architecture for Differentiated Services[END_REF] technologies at the end of the nineties of the previous century [START_REF] Pras | Internet Accounting[END_REF]. At that time it 1 It should be noted that an initial version of this paper has been presented at the fourteenth Twente Student Conference on Information Technology. However, that was an internal event of the University of Twente, of which the proceedings have not officially been published by any publisher [START_REF] Van Den Brande | Mobile Internet costs of web advertisements[END_REF].

was believed that the Internet would evolve into a network capable of providing different quality of service classes to its users; terms like 'gold', 'silver' and 'bronze' were used to denote these different classes. Depending on the quality required for a specific service, the user could select a specific quality and switch to another class, if needed [START_REF] Sprenkels | A customer service management architecture for the Internet[END_REF]. To cope with the potential problem of service asymmetry, i.e. the client requests for data, whereas the server sends the data and will therefore be charged, well-known concepts like reverse charging were investigated for suitability within the Internet [START_REF] Sprenkels | An architecture for reverse charging in the Internet[END_REF].

Due to the complexity of service differentiation within the Internet core, the idea of charging based on service usage and quality slowly diminished and nowadays many ISPs have adopted flat-fee schemes, also since users seem to prefer such schemes [START_REF] Odlyzko | Internet Pricing and the History of Communications[END_REF]. Content providers are still confronted with service asymmetry, however, but discovered advertisements as a viable approach to cover at least part of their costs.

Nowadays the usage of iPads, PDAs, and other mobile devices capable to access the Internet shows an impressive growth. The pricing schemes used by mobile operators are completely different from the flat-fee schemes used by ISPs for the fixed Internet, however, which means that also the research interest in (mobile) Internet accounting is again growing. Several studies already exist on generic accounting architectures, and how accounting data can be collected within networks [START_REF] Racz | Design and implementation of an integrated accounting architecture for distributed UMTS and WLAN networks[END_REF]. There are also many papers that describe the design of accounting systems for the mobile Internet [START_REF] Koutsopoulou | Charging, Accounting and Billing Management in Mobile Telecommunication Networks and the Internet[END_REF] [START_REF] Foell | Service-Oriented Accounting and Charging for 3G and B3G Mobile Environments[END_REF]. The behavior of mobile users browsing the Internet has been investigated [START_REF] Roto | Data Traffic Costs and Mobile Browsing User Experience[END_REF], and there are many papers that discuss the effects and click-through rates of web advertisements. Such papers are often written from the perspective of the advertiser or website owner (to improve the design of web servers and effectiveness of the advertisements), however, and not from the perspective of the user. This paper takes the perspective of the mobile user, however, and builds upon an earlier paper that analyzed the hidden energy costs of web advertisements [START_REF] Simons | The Hidden Energy Cost of Web Advertising[END_REF].

Approach to measure advertisement traffic

The best approach to answer the first three research questions, is by comparing the browsing behavior of mobile internet users without advertisements being blocked, and with such blocking. Since it is hard to obtain usage data from mobile operators, experiments with real users cannot easily be performed. An alternative approach is therefore to set up a test environment that automatically retrieves some of the most popular web pages. By retrieving these pages twice, the first time with and the second time without web advertisements, it is possible to calculate how much traffic is used for web advertisements. This chapter first discusses approaches to filter advertisements (section 3.1), followed by how users browse webpages (section 3.2), and ways how such browsing can be emulated (section 3.3). The chapter concludes with approaches to measure traffic (section 3.4) and a presentation of the specific measurement set-up used in the remainder of this paper (section 3.5).

Blocking advertisements

First of all a method to block web advertisements is needed. There are several methods available for this purpose. Most methods make use of at least URL filtering, which means advertisements are blocked based on their URL (prefix). The Opera web browser includes this feature by default, although it does not include default entries. Most advertisement blocking solutions rely on more sophisticated methods, such as CSS-and JavaScript-based filtering. The Adblock Plus plugin for Mozilla Firefox [START_REF] Palant | Adblock Plus -for annoyance-free web surfing[END_REF] is an example of such a solution. Since different types of web browsers should be investigated in this research, browser-specific advertisement blocking solutions should not be used.

Another approach is to use a proxy server. A proxy server is a device that is located between the web browser and the web server. The proxy receives the requests from the web browser, and forwards the requests to the web server on behalf of the web browser. Responses also go via the proxy. Since all data passes the proxy server, the proxy can simply measure the data that is being exchanged. The proxy can also modify this data, for example to filter advertisements.

Proximodo [START_REF] Boucher | Proximodo[END_REF] is a kind of proxy server that can filter based on a URL blacklist. Unfortunately the program is no longer maintained and seems to be outdated. Privoxy [19] is a more advanced proxy server that can also filter based on the more sophisticated methods described above. Finally there is the possibility to convert an Apache web server to a proxy server, using the 'mod proxy' module [START_REF]Apache Module mod proxy[END_REF]. Such approach would take a lot of time and detailed knowledge on the operation of Apache web servers, however, and would for our purpose not bring any advantages compared to Privoxy. Therefore it was decided to use Privoxy as advertisement blocking method for the remainder of this research.

Browsing behavior

Since there are, to the best of our knowledge, no recent and openly available behavioral studies that specifically analyze how mobile users browse the Internet, we will assume within this paper that the browsing behavior of mobile users is comparable to that of 'normal' Internet users. In this paper we will therefore not consider that some websites also offer 'mobile' versions or special Apps, which are optimized for mobile devices with small screens. In this paper we also assume that roaming users are more reluctant to browse the mobile internet, and thus visit far less web pages than when they would not be roaming. The research of Infante and Vallejo [START_REF] Infante | Regulation of international roaming in the European Union -lessons learned[END_REF] gives an indication of this, as they state that on average the international roaming market accounts for about 4% of the total revenues in the mobile services industry, while the international roaming rates are several factors higher than domestic data rates. Therefore, it can be concluded that roaming users produce only a small fraction, say 10%, of their normal traffic when they are not roaming.

To mimic the behavior of average Internet users, the URLs of the web pages that are visited should be known. For our purpose it will not be sufficient to simply look at website rankings to find the most popular websites, as such rankings only include the home page of popular websites, which may contain many advertisements, while an average user may also open deep pages, which contain fewer advertisements.

According to Simons [START_REF] Simons | The Hidden Energy Cost of Web Advertising[END_REF], a good way to obtain a list of frequently seen web pages is to analyze the most popular posts on Digg.com. This is a community website that allows users to post links to web pages with content that the users find interesting [START_REF]What is Digg?[END_REF] and thus gives a good reflection of popular web pages loaded by average users. Digg provides an Application Program Interface (API), based on the PEAR package of PHP, for retrieving its content; optionally it is also possible to retrieve XML-files. For our research we have used this option to retrieve the 100 most popular stories. Extracting the URLs out of these stories results in a list of URLs average Internet users would browse to.

Next to the URLs, also the average time spent on these web pages needs to be discovered, as some "heavier" rich media advertisements might continuously reload. There has been some research on the average time a person stays on a web page. That research shows that a pageview lasts on average about 12 seconds [START_REF] Weinreich | Not quite the average: An empirical study of Web use[END_REF], but the result includes pageviews of non-interesting web pages as well, to which a user has accidentally navigated to. These pages will be loaded, but viewed for only a short time. Since no numbers are available on the number of pages that were 'accidentally' loaded, our research assumes that all visited web pages are of interest to the user, and the user stays the same time on each page. Based on these considerations, the average time spent on each web page should be higher than 12 seconds.

Browsing emulation

For emulating a user's daily browsing behavior, the AutoBrowse program written by Simons [START_REF] Simons | The Hidden Energy Cost of Web Advertising[END_REF] was used. This program is a JavaScript tool that runs on every modern web browser and that retrieves a given set of URLs. This set is the top 100 URL list mentioned before (see section 3.2); as interval to load new pages we chose 30 seconds.

Traffic measurements

Several tools exist to measure network traffic. Tcpdump can monitor network activity and offers some options for filtering the captured network traffic. Wireshark is based on Tcpdump, but offers a graphical interface and has better and more comprehensive filtering capabilities. Also it allows to easily generate statistics. To analyze wireless networks, Kismet is a good tool as well, and has the ability to export its traces to Wireshark compatible file formats.

For practical reasons, our research will not emulate actual wireless data transferral, but use wired ethernet connections instead. Therefore it was decided to use the packet sniffing program Wireshark on the proxy server to capture all traffic. For our analysis we filtered on the IP-address of the client PC on which the web browser and AutoBrowse programs were running.

Measurement set-up

The previous sections discussed all considerations to set-up our measurements environment. This environment consists of a client PC, a proxy server and a connection to the rest of the Internet (see Figure 1). The client PC has an Intel Core 2 Duo 2.40 GHz processor, 4.00 GB RAM and runs Windows 7 Professional. The proxy server is a dedicated Dell Latitude D830 laptop with an Intel Core 2 Duo 2.20 GHz processor, 2.00 GB RAM and also running Windows 7 Professional.

The client PC runs only a browser with the AutoBrowse program. To answer the question whether the results would be browsers dependent, two different browsers were used: Mozilla Firefox (version 3.6.12) and Opera (version 10.63). The proxy server runs the Privoxy program, as discussed in section 3.1; Wireshark is also run on the proxy. The cloud called "Internet" represents the connections to the web servers elsewhere, as identified by the URLs in our top 100 list.

Measurement results

Table 1 shows the measurements results. Each row in the table represents one measurement; in the first four measurements Flash was enabled, whereas in measurements 5 to 8 Flash was disabled. To see if results would change over time, the Firefox measurements were repeated multiple times. In each measurement 100 pages were loaded.

The table shows two numbers for the amount of network data captured. 'Normal' indicates the run in which the advertisements filter was disabled and 'Ads blocked' indicates the run in which the filter was enabled. The 'Difference per page' shows the differences between both amounts, using Equation 1. This difference is specified per page, and expressed in KB (instead of MB).

Difference per page =

Normal browsing -Ads blocked No. of pages loaded * 1024

The 1. Measurement results -Traffic with and without web advertisements average normal traffic with Flash enabled (thus the normal case), is 127.22 MB; without advertisements the amount reduces to 116.54 MB. If Flash is disabled, these amounts are 102.23 MB and 95.25 MB respectively. From these numbers we may conclude that web advertisements increase data traffic with 7.3% (Flash disabled) to 9.2% (Flash enabled).

Costs

In the previous section we've discussed the percentage of network traffic generated by web advertisements. To estimate the costs of web advertisements for roaming users (our fourth research question), we will first present rates for mobile Internet usage (Section 5.1) and then use these rates to investigate whether the costs incurred by web advertisements is worth considering (Section 5.2).

Mobile Internet Rates

Before we can calculate the costs of web advertisements, we need to know the average rate per data unit. This rate is determined by analyzing the tariffs from popular mobile providers, from the US as well as the Netherlands (since the authors live in the Netherlands). Since we are interested in the additional costs caused by web advertisements, flat-fee plans for domestic as well as roaming use are not taken into account. Also, it is not the intention to present a complete analysis of all mobile Internet costs, as the number of pricing options is limitless, but to give a good indication of possible costs incurred.

For the Netherlands four major providers (KPN [START_REF] Kpn | Mobiel Internet abonnement voor je tablet of laptop[END_REF], Vodafone [START_REF] Vodafone | Tarievenoverzicht Vodafone Prepaid[END_REF], Telfort [START_REF] Telfort | Productinformatie & Tarieven[END_REF] and T-Mobile [START_REF]Prijslijst T-Mobile Mobiel Internet[END_REF]) have an average cost estimate of e0.22 per MB domestic and e3.88 per MB when roaming. The United States' major providers (Verizon Wireless [START_REF]Data Connect to the things that matter[END_REF], AT&T [START_REF]AT&T Data Plans[END_REF], Sprint [START_REF]Sprint. Plans -Mobile Broadband[END_REF] and T-Mobile [START_REF]Prepaid plans[END_REF]) average their costs per MB at $0.16 domestic and $17.48 when roaming. All numbers were collected in June 2012. Although these numbers are continuously changing and our tables do not pretend to give a complete view, the numbers should still be usable to get an impression whether the additional costs of web advertisements can be significant, or not.

Web Advertisement Costs

To calculate the average costs of web advertisements for mobile Internet users, we still need to know the browsing behavior of average mobile users. Unfortunately little is publicly known regarding this behavior. However, Opera, which is used by roughly 56% of all mobile Internet users [START_REF]Opera use and user behavior white paper[END_REF], publishes usage statistics for their mobile browser [START_REF]State of the Mobile Web[END_REF] on a monthly basis. In March 2011, for example, Opera measured per user an average number of daily pageviews of 13.9 in the United States, and 7.4 in the Netherlands.

These numbers can also be used to calculate the costs associated with mobile Internet browsing. Multiplying these average daily pageviews with the average data rates (Section 5.1) and the average amount of data generated per web advertisement (Section 4), gives us the average daily costs of web advertisements and thus the average monthly costs (see Table 2). In this paper it is assumed roaming users visit 90% less pages than domestic users, because they only browse to essential webpages, and thus this is taken into account in the calculations. As there is a noticeable difference between traffic with Flash enabled or disabled, both cases are shown separately. In our analysis it is quietly assumed that the websites downloaded on PCs, PDAs, tablet PCs and mobile phones are comparable. In reality there may be differences, but we do not have access to data to verify this. It is known, however, that several mobile operators modify content for mobile devices, for example to reduce the quality and resolution of JPEG pictures. It is unlikely, however, that such operators would distinguish between normal data and web advertisements. As such, the percentage of traffic generated because of advertisements may not be effected.

Conclusions

The goal of this paper was to investigate whether advertisements take up a significant part of the data traffic produced while browsing on mobile devices, and whether these advertisements lead to extra costs that can not be neglected.

Section 3 of this paper presented an approach to measure the average amount of network traffic generated by web advertisements. In this approach the data from hundred popular webpages was automatically retrieved via a proxy server; in the first run the proxy did not filter any advertisement, but in the second run the proxy did. By calculating the difference between both runs, the average amount of traffic generated by advertisements was found.

Our results, which were presented in Section 4, show that the amount of network traffic generated by web advertisements will be more than 100 KB per page if Flash is enabled, and around 70 KB without Flash. These numbers vary over time, based on the actual advertisement being offered by the website. Web advertisements therefore increase the total amount of network traffic with roughly 9% if Flash is enabled, and 7% without Flash.

In Section 5 these numbers were used to calculate the additional costs that mobile users would experience because of advertisements. In the US, average users without any data plan would be charged an additional $4.5 to $7 when browsing domestically, and between $50 and $80 when roaming. In the Netherlands these additional costs would be, without any data plan, between e3 and e5 when browsing domestically and about e6 to e9 when roaming. These costs need to be viewed as rough estimates, however, for mobile users not using any data plan.

Because the share of web advertisements in the total data traffic produced appears to be significant, it would be interesting to use this paper as motivation for further research in this area. Such research could focus, for example, on the distribution function of advertisement sizes, their variance, heavy-tailed characteristics, etc. Also further research is needed on the browsing behavior of mobile users.

Fig. 1 .

 1 Fig. 1. Diagram of measurement set-up

  table shows an average difference of 109.41 KB per page when Flash is enabled; if Flash is disabled this difference is reduced to 71.47 KB per page. The

			Flash No. of pages Total traffic (MB)	Difference
	No. Browser	used loaded	Normal Ads blocked per page (KB)
	1	Opera 10.63 Yes	100	133.38	120.63	130.51
	2	Firefox 3.6.12 Yes	100	117.70	108.10	98.99
	3	Firefox 3.6.12 Yes	100	144.61	132.55	123.52
	4	Firefox 3.6.12 Yes	100	113.18	104.92	84.62
				Average	127.22	116.54	109.41
	5	Opera 10.63 No	100	91.66	86.12	56.74
	6	Firefox 3.6.12 No	100	102.05	94.52	77.10
	7	Firefox 3.6.12 No	100	107.71	101.99	58.57
	8	Firefox 3.6.12 No	100	107.51	98.38	93.46
				Average	102.23	95.25	71.47
		Table

Table 2 .

 2 Average monthly costs of web advertisements

		Monthly costs
		Flash enabled Flash disabled
	NL domestic	e5.32	e3.48
	NL roaming	e9.27	e6.06
	US domestic	$7.11	$4.64
	US roaming	$78.94	$51.56


Árpád Huszák
email: huszak@hit.bme.hu

Győző Gódor

Károly Farkas
email: farkask@hit.bme.hu

Investigation of WLAN Access Point Placement for Indoor Positioning

Keywords: Indoor positioning, WLAN, simulated annealing, MATLAB

Wireless indoor positioning has been a popular research topic for years because it provides the basis for a broad domain of location-based applications. Especially the usage of WLAN (Wireless Local Area Network) technology is widespread to build an indoor positioning system due to the reuse of existing and almost ubiquitous WLAN infrastructure worldwide lowering the costs. However, these WLAN systems were not originally designed for positioning services, thus the provided accuracy might be low. The accuracy can be increased by the careful placement of WLAN access points to cover the given area appropriately. In this paper, we propose a method based on simulated annealing to find the optimal number and placement of WLAN access points for indoor positioning and show its investigation using simulations.

Introduction

With the proliferation of mobile devices and the rapid development of pervasive communication the popularity of location-aware services and applications has been increasing. This requires the use of location sensing systems. Getting the position information in an outdoor environment is relatively simple by using matured technologies, such as GPS (Global Positioning System). However, indoor positioning has been an issue under research for years. Numerous technologies and systems have been proposed and developed for indoor location sensing [START_REF] Liu | Survey of Wireless Indoor Positioning Techniques and Systems[END_REF], but the most popular technology is WLAN (Wireless Local Area Network) due to the low cost of WLAN equipments and the possible reuse of existing and almost ubiquitous WLAN infrastructure worldwide.

However, today's WLAN systems were not originally designed for location sensing, hence the accuracy and precision achieved by these systems might be low. For instance, several position estimation schemes use triangulation methods to determine the position of a mobile host [START_REF] Liu | Survey of Wireless Indoor Positioning Techniques and Systems[END_REF]. The common indispensable condition for all of these methods is to receive the signal of at least three reference APs (Access Point). But most of the existing WLAN systems does not fulfill this criterion.

Moreover, the number and placement of the access points can have substantial impact on the position accuracy [START_REF] Baala | The Impact of AP Placement in WLAN-based Indoor Positioning System[END_REF].

In this work, we investigated how to place the WLAN access points to receive the signal of at least three reference APs everywhere in the given indoor area, but keep the number of deployed APs as low as possible (thus minimizing the overall cost of the indoor positioning system and its operation expenses). To find the optimal number and placement of the APs considering the map of the given territory we propose a simulated annealing based algorithm. Our method can find a solution, in most of the cases a global optimal one, nearly in constant time in realistic scenarios. Moreover, we have developed a simulation tool in MATLAB [START_REF]MATLAB and Simulink for Technical Computing[END_REF] environment. We used this tool to implement our algorithm together with several signal propagation models and to analyze the algorithm's behavior.

The rest of the paper is structured as follows. In section 2 and section 3, we give a short overview about WLAN-based indoor positioning systems and signal propagation models, respectively. We describe our simulated annealing based algorithm in section 4, and present some simulation results of its evaluation in section 5. Finally, we give a short summary in section 6.

Overview of WLAN-based Indoor Positioning Systems

In the last decade, indoor location-based services have been developed rapidly requiring suitable and accurate indoor positioning. Wireless communication technologies are often used in positioning systems due to their handiness. Fig. 1 depicts the most popular wireless technologies used in current positioning systems with their accuracy, scale and the typical localization methods. As we can see from the figure the UWB (Ultra-Wide Band) technology offers the highest accuracy for indoor positioning, but it is quite an expensive solution still today. IR (Infrared) technology requires line-of-sight visibility, since GPS does not work in indoor environment. In cellular networks, usually the positioning information is accessible only by the network provider, and its accuracy is low. It is not so surprising, that WLAN technology is the most popular one to be used in indoor positioning systems, even if the accuracy it basically provides is only in the range of some meters, because it is inexpensive and easy to deploy.

Localization Methods Used in WLAN-based Positioning Systems

In the following, we briefly discuss the most relevant localization methods used in WLAN-based positioning systems [START_REF] Liu | Survey of Wireless Indoor Positioning Techniques and Systems[END_REF].

Received Signal Strengths (RSS): This method is based on the measurement of the received signal level. By using signal path loss models the distance between the transmitter and the receiver can be estimated. In ideal case, the signal of three reference points is enough to calculate the position.

Time Of Arrival (TOA): This method is based on the travel time of a radio signal between the transmitter and the receiver. The distance between them can be derived from the carrier frequency knowing the medium. TOA requires at least three reference points and the precise synchronization of all transmitters and receivers.

Time Difference Of Arrival (TDOA): In case of TDOA the idea is analogous to TOA, but it uses the difference in signal arrival time measured at multiple receivers.

Angle Of Arrival (AOA): This method uses the direction of the received radio waves. At least three reference points and three measured angles are required to derive the location in the 3-D space.

Specific WLAN-based Indoor Positioning Systems

Several different indoor positioning systems have been developed using WLAN technology. In the following, we shortly discuss couple of them.

The RADAR system has been developed by Microsoft [START_REF] Bahl | RADAR: An in-building RF based user location and tracking system[END_REF]. RADAR is an indoor position tracking system which applies existing WLAN architecture. This solution uses the RSS measurement method combined with the triangulation location technique. For the correct localization at least three APs' signals are to be received. The system achieves an accuracy of around 4m with 50% probability.

The COMPASS system is proposed in [START_REF] King | COMPASS: A Probabilistic Indoor Positioning System Based on 802.11 and Digital Compasses[END_REF]. In COMPASS, the positioning algorithm uses a fingerprint-based technique in which the signal strength of a given mobile device is measured by different APs. Moreover, digital compasses are utilized for getting a relatively accurate position. Thus, the user's orientation, considered also in the location estimation, can be measured by a digital compass which is integrated in most of today's mobile devices. COMPASS can achieve an accuracy of about 1.65m, however this system is not suitable for tracking multiple users. In the Horus system [START_REF] Youssef | WLAN location determination via clustering and probability distributions[END_REF], the localization is based on a joint clustering technique using a probabilistic method. Each location candidate has a signal strength vector (fingerprint) and in the location estimation phase each candidate coordinate is regarded as a class associated with the probability that the mobile is in that location. A given location is chosen when its likelihood is the highest. This method can acquire an accuracy of 2.1m with more than 90% probability.

Indoor Signal Propagation Models

Most of the location estimation techniques in wireless networks is based on some kind of mapping of each transmitter's signal. In a simple model, each point is mapped to the signal strength of each sensible access point. In case of a more complex model, besides the signal strengths other data can also be considered, such as the detailed map of the building, walls, obstructions, etc.

To compute the signal strength numerous propagation models were proposed [START_REF] Tummala | Indoor Propagation Modeling at 2.4 Ghz for IEEE[END_REF]. The indoor signal propagation models are more complex than the outdoor ones, because approximating a real indoor environment (signal strength, path loss, etc.) is more difficult due to reflection, diffractions and multi-path propagation. In this section, we overview three well-known indoor signal propagation models we used in our WLAN access point placement investigations.

Free-Space Propagation Model

Line-of-sight path through free space can be described by the simple free-space propagation model. In this environment, there are no obstacles which could cause reflection or diffraction. Typically the free space is the air.

Equation (1) describes the free-space propagation model [START_REF] Sandeep | Wireless Network Visualization and Indoor Empirical Propagation Model for a Campus WI-FI Network[END_REF].

2 RT T R PP G G 4d           , (1)
where P R is the received power from transmitter (W), P T is the transmitted power (W), G T is the transmitter antenna gain (dB), G R is the receiver antenna gain (dB), λ is the signal wavelength (m) and d is the distance from the transmitter (m). In this model, the received power is inversely proportional to the square of the distance between the transmitter and receiver, proportional to the square of the radio signal's wavelength, and directly proportional to the transmitter and receiver antenna gains [START_REF] Seybold | Introduction to RF Propagation[END_REF].

In our investigations, we use this model in such a way that we examine the path between the transmitter and the receiver and in that case when an obstacle exists along the path the received power is reduced by a given value assigned to the object.

Site-General ITU Indoor RF Model

In contrast to the free-space propagation model, this model was developed for indoor environments [START_REF] Lkhagvatseren | Path loss aspects of a wireless communication system for sensors[END_REF][START_REF] Chrysikos | Site-Specific Validation of ITU Indoor Path Loss Model at 2.4 GHz[END_REF]. Equation (2) describes the ITU path loss model.

 

L 20 log N log d Lf n 28 f    , (2)
where L is the total path loss (dB), f is the frequency (MHz), N is the distance power loss coefficient, d is the distance between the transmitter and the receiver (m), Lf(n) is the floor penetration loss factor and n is the number of floors between the transmitter and the receiver.

The received power strength can be derived according to equation [START_REF]MATLAB and Simulink for Technical Computing[END_REF].

RT PPL   , (3)
where P R is the received power (dBm), P T is the transmitted power (dBm) and L is the total path loss (dB).

From ( 2) we can deduce that increasing either the distance or the frequency the path loss also increases. It is analogous with the free-space model, however, the ITU indoor prediction model better estimates the real environment using factor N and Lf(n) [START_REF] Ranvier | Path loss models[END_REF]. Their values are defined in Table 1 and2 Since our goal is to find the minimal number of APs for a WLAN-based indoor positioning system, which still guarantees full coverage, we selected the values of factor N and Lf(n) for the 1.8-2 GHz commercial environment to be used in our simulations.

Hata-Okumura

The Hata-Okumura model was developed to predict the path loss particularly in outdoor environments, but it can be used also indoor [START_REF] Bose | A Practical Path Loss Model For Indoor WiFi Positioning Enhancement[END_REF]. There are three variants of the model, such as urban area, suburban area and open area. Usually this model is applied in cellular telecommunication systems to predict the total path loss between the mobile station and the base station [START_REF] Nadir | Pathloss Determination Using Okumura-Hata Model and Spline Interpolation for Missing Data for Oman[END_REF].

In this model, the received power can be derived by using equation ( 4).

 

RT T R α P P G G 10 n log d X 20 log 20 log 4          , (4)
where P R is the received power (dBm), P T is the transmitted power (dBm), G T is the transmitter antenna gain (dB), G R is the receiver antenna gain (dB), n is the number of obstacles in the signal path (in case of an indoor environment the value is between 4 and 5), d is the distance from the transmitter (m), X α is a variable with normal distribution and α deviation (in case of WLAN environment (2.4 GHz) α is between 3 and 20dB) and λ is the signal wavelength (m).

WLAN Access Point Placement

As we saw above, several position estimation schemes use triangulation methods to determine the position of a mobile host. The common indispensable condition for all of these methods is to receive the signal of at least three reference APs. In this work, we investigated how to place the APs to provide visibility of at least three reference points everywhere in the given area, but keep the number of deployed APs as low as possible. By reducing the number of deployed APs, the overall cost of the indoor positioning system and its operation expenses can be minimized.

Problem of Optimal WLAN Access Point Placement

Finding the optimal positions for the APs in real environment is a challenging task for analytical methods, because the signal absorption characteristics are too complex to be realistically modeled. However, in order to install the minimum number of reference APs an obvious approach is to analyze and compare all the possible AP setups. Unfortunately, in real word this process is hard to be accomplished, therefore simulations are to be used. Actually, the number of AP position combinations is infinite because the territory, where the APs can be deployed, is continuous and contains infinite number of points available for AP deployment. To handle this problem, we assume that the APs can be located only in discrete points of the map. If the density of these points are high enough the original situation can be approximated well. For example, if we consider a 100x100m territory where the APs can be placed 10cm from each other, the number of possible AP locations is 10 6 .

Unfortunately, analyzing all possible AP location setups with a brute force algorithm cannot be accomplished due to the high number of location setup combinations. In the previous example, 2 1000000 different AP position setups exist that cannot be processed in acceptable time. To solve this problem, alternative solutions must be found.

Method for Optimal WLAN Access Point Placement

We propose the following top-down AP placement algorithm to find the optimal AP location setup(s).

The first step is to place an AP in every possible point on the map. In the next step, the coverage area of each AP must be estimated using signal propagation models in order to determine the number of sensed APs in each point where a mobile host can be present. If there is no point on the map where the number of sensed APs is less than three, one AP can be removed. If the number of sensed APs still fulfills the criterion another AP can be removed, otherwise the algorithm stops.

This method can be modeled with a tree graph, where the states are the AP combinations represented by binary numbers. The binary number determines which APs are part of the given setup (e.g., 010 means that the AP in the second position is installed, while the others are already removed). Fig. 2 illustrates the introduced algorithm where the Hamming distance of neighboring states is always one, because only one AP can be removed within one step. The presented graph-model of the AP placement scheme can be used to originate our task in a graph theory problem. Thus, our goal is to find the longest distance from the root, where the three receivable AP criterion is still fulfilled. On each level of the tree the number of removed APs is the same, therefore the deeper we are in the tree the less APs are needed to cover the served territory. The described "longest path" task is an NP-complete problem in graph theory [START_REF] Karger | On approximating the longest path in a graph[END_REF].

Numerous heuristic optimization algorithms were developed to find the global optimum for NP-complete problems, like hill climbing, swarm intelligence, integer linear programming, simulated annealing, etc. For our case, we propose simulated annealing to approach the optimal AP locations for WLAN-based indoor positioning. Simulated annealing is a generic probabilistic algorithm for the global optimization problem. It tries to locate a good approximation to the global optimum of a given function in a large search space even for NP-complete problems.

Our above mentioned AP placement scheme can be extended with the simulated annealing algorithm to approach optimal AP setup(s). Hence, a previously removed AP can be added again with probability given in [START_REF] King | COMPASS: A Probabilistic Indoor Positioning System Based on 802.11 and Digital Compasses[END_REF]:

exp E T      , (5)
where ∆E stands for the difference of cost functions of the two neighboring AP setup states. The cost function is determined as the number of APs in the given state of the graph. Parameter T is called temperature and calculated as the sum of the number of sensed APs for each position on the map. The possibility of putting a previously removed AP back prevents the method from being stuck in a local minimum that is worse than the global one.

The main steps of the extended algorithm are summarized in the following pseudocode:

1.
initialization (add all APs) 2.

WHILE (counter>0) 3.

Choose neighbor state randomly (add or remove AP) 4.

CASE add 5.

IF {random < exp(dE/T)} addAP()

IF {visibleAPs < 3} restoreAP() 9.

counter=counter-1

Note, that our method does not guarantee that the global optimum will be found, but it can be still useful to plan the AP placement in WLAN-based indoor positioning systems. Another weakness of the method is that the AP coverage areas must be estimated using signal propagation models. As we saw above, numerous models were developed in the last decades, but neither of them is 100% realistic. Fortunately, in our solution the punctual received signal strength is not important, only the coverage area borders of an AP must be estimated accurately.

Evaluation

In order to evaluate the proposed, simulated annealing based algorithm we used simulations.

Simulation Environment

We have developed a simulation tool in MATLAB [START_REF]MATLAB and Simulink for Technical Computing[END_REF] environment. Our AP positioning algorithm relies on signal propagation models, therefore we implemented the above mentioned three different models, such as free-space, ITU indoor and Hata-Okumura. The signal absorption depends on the frequency, transmitter antenna gain, receiver antenna gain and transmitted power in all of the models. The default values of these parameters we used in the analysis are 2.4GHz, 5dB, 2dB and 100mW, respectively.

Our aim was to create a general tool, so we made our simulator adaptable to different wireless technologies by allowing the adjustment of the parameters. The received signal strength can be estimated using the propagation models. However, if the RSS is too low, the access point is not sensed by the host and cannot be used for positioning purposes. In order to determine the AP coverage area, we have introduced the sensitivity parameter (-80dB) of a host. If the received signal strength is lower than the host sensitivity, the terminal is out of the AP's range.

Moreover, the simulated area (map) has to be loaded at the beginning of the simulation process. A .bmp image file can be used to determine the simulated environment by defining the rooms, walls, pillars, etc. The wall attenuation is also an adjustable parameter in our tool, what we set to 5dB.

In the simulator, not only the simulated annealing based algorithm was implemented, but a brute force method, too. In cases, when the number of possible AP positions is not too high the brute force method is a better choice providing always the global optimal solution.

Simulation Results

Due to space limitation we can present only a small subset of our simulation results. In our first simulation, we have compared the brute force and simulated annealing based method using the free-space signal propagation model to analyze the limits of the algorithms. The simulation time was measured in function of the number of possible AP positions (Fig. 3). The result shows that the simulated annealing algorithm is scalable and the simulation time remains almost constant even if the number of possible AP positions is increasing. On the contrary, the brute force algorithm does not scale well and the simulation time increases exponentially, as expected.

Then, we investigated further our extended AP positioning algorithm based on simulated annealing in a 102x106m territory, where the possible AP locations are 30cm from each other. In this case, the number of possible AP locations is close to 120000. Moreover, we used the ITU indoor signal propagation model this time. The simulation time was about 2 minutes. The simulated annealing randomly chooses the neighbor states in the graph, therefore in case of several optimal solutions the resulted AP setup scheme can be different in consecutive simulation runs, even if the input parameters are the same. An output of the simulation is presented in Fig. 4 where the selected AP locations and the RSS of the access points are illustrated. The ideal AP positions are highly influenced by the walls inside the indoor area due to the significant signal attenuation, therefore the map of the territory must be entered before running the simulations (the walls, illustrated by straight lines, are slightly visible in Fig. 4). In the presented result, 9 APs were enough to cover the territory by receiving the signal of at least three APs in each point of the map. We have iterated the simulation process in order to examine whether the resulted number of APs is always the same (we reached a global optimal) or it is changing due to the randomness of the simulated annealing algorithm (we reached a local optimal). We found that in most of the cases the algorithm's output was 9 APs, but rarely it gave 10 APs as a solution. We can conclude that the simulation must be repeated several times to find a global optimal solution with high probability.

In this paper, we investigated the issue of optimal placement of WLAN access points for indoor positioning. We proposed a simulated annealing based method to find the optimal solution of how to place the access points to receive the signal of at least three reference APs everywhere in the given indoor area, but keep the number of deployed APs as low as possible. Our method provides a solution, usually a global optimal one, nearly in constant time in realistic scenarios. Moreover, we have developed a simulation tool in MATLAB environment. In this tool, we implemented our algorithm together with several signal propagation models and analyzed the algorithm's behavior.

The developed simulation tool and our simulated annealing based algorithm can be useful in planning radio-based positioning systems not just focusing on WLAN technology. By minimizing the amount of required access points, the cost of deployment and the operation expenses can be reduced but still an efficient and accurate positioning system can be operated.

As future work, we plan to further investigate the performance and limitations of our algorithm. Moreover, we plan to collect real world measurements and compare them with our simulation results.

Fig. 1 .

 1 Fig. 1. Wireless technologies in current positioning systems and their accuracy, scale and localization methods [1].

Fig. 2 .

 2 Fig. 2. Graph representation of the proposed AP placement algorithm.

Fig. 3 .

 3 Fig. 3. Simulation time vs. number of possible AP positions in case of the brute force and simulated annealing algorithms.

Fig. 4 .

 4 Fig. 4. Selected AP locations and the RSS of the access points using our extended AP positioning algorithm based on simulated annealing. The colors represent the highest RSS in the given point.

Table 1 .

 1 . Distance power loss coefficient values (N) used in the ITU model[START_REF] Seybold | Introduction to RF Propagation[END_REF].

	Frequency	Home env.	Office env.	Commercial env.
	900 MHz	-	33	20
	1.2-1.3 GHz	-	32	22
	1.8-2 GHz	28	30	22
	4 GHz	-	28	22
	5.2 GHz	-	31	-
	60 GHz	-	22	17

Table 2 .

 2 Floor penetration loss factor values (Lf(n)) used in the ITU model[START_REF] Seybold | Introduction to RF Propagation[END_REF].

	Frequency	No. of level	Home env.	Office env.	Commercial env.
	900 MHz	1	-	9	-
	900 MHz	2	-	19	-
	900 MHz	3	-	24	-
	1.8-2 GHz	N	4n	15+4(n-1)	6+3(n-1)
	5.2 GHz	1	-	16	-

Acknowledgments. This work was supported by the BME-Infokom Innovátor Nonprofit Kft. Károly Farkas has also been partially supported by the Hungarian Academy of Sciences through the Bolyai János Research Fellowship.


Pikulski Wojciech
email: w.pikulski@elka.pw.edu.pl

Nonmonotonicity in Trust Management

Keywords: Software security, trust management, RT Framework, nonmonotonicity, credential chain, credential graph, freshness constraints

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

Introduction

Distributed systems have become very popular during the last decade. Due to the expansion of the Internet access in the last few years, they have also become open to the external environment. Global market and economy made companies set partnerships which often need infrastructure that can provide access to the shared resources and supply collaboration services.

Distributed design meets many issues that have to be solved in order to enable application collaboration. Some of the most significant are security of shared resources and provisioning of convenient access control mechanisms in distributed environment, where subjects and resources are situated and operate in different security domains also called administrative domains. Each of such domain controls its subjects and resources.

To solve problems listed above, various access control models have been proposed. Security mechanisms dedicated for utilisation in distributed environment are named Trust Management. Researchers have also focused on creating Automated Trust Negotiation mechanism that can establish trust between strangers in automated way.

This work is focused on nonmonotonicity issues in trust management models. The monotonicity of the security model means that when access decision evaluates to true at some point in time, it cannot evaluate to false in future when time lapses or new information is added to policy. Model can introduce nonmonotonicity when it allows for credential revocation or role negation. Currently, nonmonotonicity is regarded as undesirable [START_REF] Chapin | Authorization in trust management: Features and foundations[END_REF] [START_REF] Seamons | Requirements for policy languages for trust negotiation Proc[END_REF]. However, in [START_REF] Li | Nonmonotonicity, User Interfaces, and Risk Assessment in Certificate Revocation Financial Cryptography[END_REF] authors proved that certificate revocation, that used to be thought as nonmonotonic, can be implemented in monotonic manner by introducing freshness constraints. This paper analyses the nonmonotonicity caused by credential revocation. The work aims at introducing credential revocation in the Rolebased Trust-management Framework. This goal is achieved by creating the model of freshness constraints propagation. The paper presents its formal description and evaluates the idea against real-life scenario.

Because certificates and credentials are electronically signed documents containing digital information, the freshness constraints can be implemented for both. As certificates contain binding of an entity name to its private key, they are entity's electronic identity. Credentials contain signed policy statements defining permissions.

The rest of the paper is outlined as follows. Section 2 describes related work. In section 3 trust management is defined. Section 4 presents business problem which would incorporate credential revocation. The RT Framework and freshness constraint propagation model is presented and discussed in Section 5. Finally, in section 6 the paper is summed up and future work is outlined.

Related Work

A significant effort has been carried out to address problem of trust in distributed systems. There were presented many models for authorisation in such environment. Few examples are KeyNote [START_REF] Blaze | The KeyNote trustmanagement system, version 2[END_REF], PolicyMaker [START_REF] Blaze | Compliance Checking in the PolicyMaker Trust Management System[END_REF] and RT Framework [START_REF] Li | Design of a Role-Based Trust-Management Framework[END_REF]. Seamons et. al. in [11] and Chapin et. al. in [4] point out the requirements for trust management systems and perform survey of proposed models against them. One of the commonly agreed requisite is monotonicity of the model, which is regarded to be one of the factors allowing a practical implementation of the system. However, Li et. al. in [START_REF] Li | Nonmonotonicity, User Interfaces, and Risk Assessment in Certificate Revocation Financial Cryptography[END_REF] proved that certificate revocation, which was thought to cause system nonmonotonic, can be implemented in monotonic manner. Skalka et. al. [START_REF] Skalka | Risk management for distributed authorization[END_REF] created RT R language which takes into consideration a risk associated with each credential. The risk is being propagated along credential chains. The notion is conceptually similar to the idea of freshness constraints propagation presented in this work. Changyu et. al. in [15] introduce a non-monotonic trust management model called Shinren. The concept is different from RT framework analysed in the paper in the sense that Shinren utilises multi-value logic with negative assertions in contrast to RT, which uses classic logic with only positive statements. Furthermore, presented freshness constraints propagation focuses on allowing for credential revocation instead of expressing negative information in the security policy.

Another subject of research in the area is automated trust negotiation. Seamons et. al. in [START_REF] Seamons | Requirements for policy languages for trust negotiation Proc[END_REF] present the requirements for languages used to specify policies and for compliance checkers which parse the policies and make access decisions. The idea of automated trust negotiation is elaborated in [START_REF] Seamons | Limiting the Disclosure of Access Control Policies during Automated Trust Negotiation NDSS[END_REF] where authors present negotiation strategies and policy graphs.

Access Control and Trust Management

The aim of access control is to prevent unwanted users from acquiring access to a shared resource [9]. Trust management is an evolution of access control for distributed systems. A decentralised design brings new problems and imposes additional requirements for access control mechanisms. The main difference is that subjects and resources can belong to various administrative domains. Another issue is that the credentials are decentralised and its number is virtually unlimited. The problem of creating access control for such environment is referred as trust management, and was first introduced in [START_REF] Blaze | Decentralized trust management Proc[END_REF].

Trust management research mainly focuses on two problems: authorisation and trust negotiation. The former is answering a question whether a particular resource access request should be allowed or denied. To achieve this models utilise credentials defining subject permissions and inferencing rules that allow to evaluate an access decision. Trust negotiation is a newer problem, whose point is to establish trust between two stranger parties in automated manner. It is accomplished by a bidirectional conversation with gradual exchange of owned credentials. Each party has a policy defining for each credential what credentials have to be revealed by the negotiating partner in order to be disclosed. Details can be found in [START_REF] Blaze | Decentralized trust management Proc[END_REF][10] [11][13].

Business Problem

This paper describes a problem of nonmonotonocity caused by credential revocation. The issue is illustrated with a real-life scenario adopted from [START_REF] Czenko | An Introduction to the Role Based Trust Management Framework RT[END_REF]. As work is focused on the RT Framework, policies are presented in form of RT credentials.

The example demonstrates how nonmonotonicity is introduced into RT Framework when it would allow for credential revocation. In such situation, each credential could be revoked before its expiry time passes. As a consequence an unaware acceptor would accept revoked credential. In the example, an eStore offers discount both to its long-standing customers and also to students who are simultaneously members of Superior Mountaineering Club (SMC). The student role definition is delegated to the Accrediting Board for Universities and Schools (ABUS) which defines it for universities and schools appropriately. Sample credentials are listed below:

.

.

.

.

.

.

.

.

.

. ( 10)

. ( 11
)
Evaluation of above credentials leads to conclusion that both Adam and John are eligible for discount. The evaluation process is described in Section 5 and [START_REF] Li | Distributed Credential Chain Discovery in Trust Management[END_REF].

In real-life scenario, it would be reasonable if security model would allow to revoke credentials. For example, if Adam does not meet semester requirements, his student credential can be revoked. Similar situation would happen if Adam resigns or is expelled from SMC. In any of both cases, eStore would unwittingly accept revoked credentials and grant discount.

Nonmonotonicity in Trust Management

Monotonicity of a security model is defined as a feature that if an access decision evaluates to true at some point in time, it should still be true if time lapses or additional credentials are introduced into the policy. There are two types of nonmonotonocity. If time lapse makes access decision false, system is nonmonotonic in " ". Such situation can happen when model allows for credential revocation, as revoking credential can cause that user will no longer be member of specific role. When addition of new credentials makes access decision false, system is nonmonotonic in " z ". This can happen when model allows to negate roles in policy. When user becomes a member of a negated role, he loses access to a resource. This paper presents the analysis of former type of nonmonotonicity leaving the latter for future research.

Time Domain Nonmonotonicity

Li and Feigenbaum in [START_REF] Li | Nonmonotonicity, User Interfaces, and Risk Assessment in Certificate Revocation Financial Cryptography[END_REF] proved that the certificate revocation can be implemented in monotonic manner. Thus, time domain nonmonotonicity is turned to be monotonic. Typically, certificates are interpreted as: "valid from their issue time t 0 to their expiry time t ex ". When system supports certificate revocation, a certificate can be cancelled before its expiry time. Such action introduces nonmonotonicity as acceptors unaware of certificate revocation will still accept it. The nonmonotonicity is temporal, because when certificate expiry time passes no authoriser will accept the certificate anymore, even when it was revoked.

In order to solve this issue, certificate meaning should be modified to "at the time of issuing t 0 , certificate is valid from t 1 to t 2 ". This interpretation is true any time after t 0 and it does not change even when certificate is revoked. The introduction of t 1 parameter is not crucial, but increases expressivity. Apart from new certificate interpretation, a notion of fresh time (t f ) of a certificate is introduced. Initially its value is set to certificate issue time (t f =t o ). When acceptor ensures that certificate is still valid at a later time t x , its fresh time is changed to it (t f =t x ). Each acceptor defines a parameter t which states the maximum age of accepted certificates. That is, if t f t now -t, then certificate is regarded as valid. If the condition does not hold, authoriser needs to reject certificate or verify its validity.

In this paper, the t parameter is called a freshness constraint or requirement. Setting t to small value implies frequent certificates validity checks. Defining big values limits validity verification but introduces risk of accepting revoked credential. The exact value of t depends on application and level of risk it can accept.

Freshness Constraints. After closer look at the idea of fresh time, one can find that t parameter should be specified not globally, but on more grained plane such as policy level. For example, some certificates can be treated as more vulnerable to revocation than others. Moreover, t value can also be defined based on contextual information available during policy evaluation, e.g. number of revoked certificates from given issuer or customer order amount. Another issue is whether t value for a credential should be defined by its issuer or authoriser. This is not a trivial problem. The issuer is aware of credential meaning and circumstances under whose it can be revoked. On the other hand, a freshness constraint can be regarded by acceptor as a part of access policy and therefore should be specified by himself. To link two solutions, system would allow issuers to specify hints about t, but let acceptor define final value used in access decision evaluation. The paper focuses on freshness constraints propagation leaving hints specification for future research.

Role-based Trust-management Framework

The RT Framework is a trust management model. Users, applications and resource holders are called entities. Each entity can define roles and its members. To access a resource, user must be a member of role that represents a shared resource. Entity can also delegate authority over role to other users who will be able to define members of the delegated role. The policy is expressed with a set of RT credentials. At the basis of the RT Framework are sets: ─ or -a set of RT credentials. ─ -a set of RT entities for a given set of RT credentials C. ─ -a set of names of roles that can be used by entities to define roles for a given set of RT credentials C.

Each RT credential has a form: :

. Head contains a credential issuer with role name. Body contains a role expression which depends on credential type. In the framework, there are four types of credentials:

1. Simple membership:

. With this statement A asserts that D is a member of role A.r.

Simple inclusion:

. Issuer A asserts that all members of B.s are also members of A.r. This is a simple role delegation, since B can add new entities to A.r role by adding them to B.s role.

Linking inclusion:

. Issuer A asserts that A.r includes all members of B.t role for each B that is member of A.s. This type of credential allows for authority delegation over A.r to members of A.s. 4. Intersection:

. This credential allows A to assert that a member of A.r is any entity that simultaneously is member of C.s and D.t.

Based on presented definitions, four sets can be defined: ─ : . ─ : . ─ : . ─ .

Authorisation procedure in the RT Framework utilises a credential graph, which is built based on RT credentials. Each vertex corresponds to a role expression, while edges represent credentials. If access should be granted, there should be a path linking node corresponding to resource with vertex representing user. Such path is called a credential chain.

Credential graph is defined below [START_REF] Czenko | An Introduction to the Role Based Trust Management Framework RT[END_REF] . This is called a derived intersection edge, and is a support set for this edge.

To illustrate the authorisation process of RT Framework Figure 1 presents a credential graph corresponding to scenario described in Section 4. There exist credential chains that link John and Adam entities with role representing accessed resource, i.e. eStore.discount. This implies that those users are eligible for a discount. Path for John contains only normal credential edges, whereas path for Adam also contains a derived intersection edge. Not derived edges are labelled with corresponding credentials numbers presented in example scenario policy. Derived link and intersection edges are dashed and dotted respectively and are annotated with their support sets names.

Freshness Constraints

The paper discusses the possibility to allow for credential revocation in the RT Framework by introducing fresh time notion to it. The idea is to check during access decision evaluation whether all credentials are fresher than a specified value.

Because RT Framework allows for authority delegation, the mechanism should ensure that users to whom the authority over particular role has been delegated does not grant access to entities whose credentials fresh time has exceeded requirements defined in the policy. For instance, a freshness of credentials defining ABUS.university.student members should not exceed freshness constraint defined for eStore.discount role.

Fig. 1. Credential graph for example scenario

The idea of the propagation mechanism is based on a freshness graph, which is constructed based on RT credential graph. The first step of the procedure is to calculate a freshness constraint for node representing accessed resource. Then, this value is propagated along edges of the freshness graph. If authorisation procedure encounters a credential whose freshness exceeds the propagated constraint, the credential validity is checked. Depending of the verification result, the credential is accepted or rejected.

For the sake of easier understanding, a freshness graph is presented before the formal model of freshness constraints propagation. The graphs for John and Adam entities are depicted on Figure 2. They are based on credential graph presented on Figure 1. In freshness graph, each node has associated a freshness constraint which is denoted by f n . During credential validity verification this value is used as a freshness requirement.

Defining Freshness Requirements. Policy creators should have possibility to define freshness constraints on different levels of granularity:

─ role definition levelallows to define constraint value per role definition (e.g. eStore.discount, ABUS.student); ─ entity leveldefines freshness requirement value for specific entity and any roles defined by it (e.g. ABUS, eStore); ─ global levelglobal value used when no other freshness requirement is defined.

In the paper a role representing shared resource to which user tries to get access is called a root role. In the example, a root role is an eStore.discount role. Presented levels are used in freshness constraint computation only when evaluating constraints for a root role. This value is used as a starting point of the propagation process. Thus, it is called an initial freshness constraint.

A global freshness constraint t g defines global level restriction. To define a freshness constraints for entities and roles, a f c function is introduced. To allow for using contextual information during defining freshness requirements, a set of predicates is defined. Each predicate corresponds to a contextual condition. For example, freshness constraints in eStore depend on order amount. Therefore, P has one element, P={p 1 : order.amount>$100}. Definition 3. Function defines freshness requirements on entities and roles level:

:

, where and is a predicate vector. Values of define logical values of predicates.

In the real world scenarios, freshness constraints will be specified only for a subset of the D and not all predicates will be used in definition for given D member. Therefore, can be defined in simplified form presented in Table 1. It contains only a subset of D for whom freshness constraints are explicitly defined. For each member of D, a list of optionally negated predicates is constructed. If all elements in the list evaluate to true, then given value is used. If table does not contain row for given role or entity, an infinite value is assigned. When the predicate list is empty, it means that freshness constraint does not depend on logical values of any predicates. Freshness Constraints Propagation. The propagation process starts with calculation of initial freshness constraint. This value is propagated along freshness graph edges.

To compute a propagated freshness constraints, a propagation operator ∇ is introduced. It can be defined in many ways, but the function should be commutative, monotonically decreasive and associative. In this paper a minimum function is used as a propagation operator: x ∇ y = min(x,y).

A final freshness constraint for each node of freshness graph is stored in f n function. This value is used during credential freshness verification. To propagate freshness requirements from root role to all nodes of freshness graph, two steps have to be performed. Firstly, a freshness constraint for role expression that is represented by processed node has to be evaluated. This is achieved by calc function. It utilises constraints defined by policy creator in form of f c function. Definition 4. A calc function calculates freshness constraint for a given role expression:

:

. ( 12
) Pikulski Wojciech . ( 13
) ∇ . ( 14
) ∇ . ( 15
) ∇ . ( 16
)
The second step of propagation is to take into consideration a freshness constraint

'
The result is stored in f n function.

Definition 5. A f n function represents a freshness constraint for each node of FG C .

Each node that is a root role, has a freshness constraint of value:

∇ . ( 17
)
Each node that is vertex of a freshness edge and is not a root role, has a freshness constraint of value:

∇ ∇ ∇ : . ( 18
)
The f n definition for node that does not represent a root role contains a case for w ' ' aken into consideration. This strategy separates freshness constraints propagation of each intersection element. For example, in Figure 2 if freshness constraint calculation for node 8 would include intersection present in node 5, then f n =30 value would be propagated to node 8. This is undesirable as this value is defined for SMC.member role but not eStore.student role.

Freshness Constraints Interpretation. Freshness constraints are propagated along edges of FG C . At the end of the process, each node contains associated freshness requirement. Because credential head contains its issuer, during its validity verification system should use a freshness constraint defined for node corresponding to credential head. Credential containing an entity in its body states that an entity is a member of role defined in credential head. Therefore, freshness constraint associated with node representing this entity should be used during verification of user public key certificate binding user identity to an entity.

Example Scenario Analysis

Table 2 contains freshness constraints defined in eStore policy. Constraint for eStore.discount depends on order amount. Table also contains constraints for roles defined by ABUS and SMC. As eStore delegates authority to these entities, it may decide to define freshness constraints for their roles. Since eStore and SMC are partners, eStore is aware that SMC collects fees on monthly basis and sets constraint for SMC.member role to this period. The situation with John entity is straightforward. A freshness constraint for root role is 20 and the value is propagated along all freshness edges. Finally, node representing John has freshness constraint f n =20. This value should be used for verification of John public key certificate binding this user to John entity.

Freshness graph for Adam entity contains freshness link edges and freshness intersection edges. They are a consequence of link and intersection derived edges in the RT credential graph. Because Adam entity is a solution to intersection node , it has two predecessors, whose freshness constraints are combined using propagation operator. Final Adam' freshness constraint is f n =30 and this value should be used for verification of his public key certificate.

During RT credentials validity verification, a f n value associated with role expression of credential head should be used. For example, during verifying a f n (eStore.student)=50 is utilised.

Summary

In the paper an analysis of time domain nonmonotonicity has been performed. It was explained how credential revocation causes it. Afterwards, a freshness constraints have been introduced and it was pointed out that credentials are in fact certificates but they convey different type of information. A formal model of freshness requirements propagation has been proposed. It was implemented in the RT Framework to allow for credential revocation. The model allows to define freshness constraints in the policy on different levels of granularity. The solution constructs a freshness graph that is based on credential graph. Freshness requirements are propagated along freshness graph edges. Finally, the model has been evaluated against to real-life example.

In future work, a verification of proposed freshness constraints propagation model will be performed. In order to process authorisation requests search algorithms have been created. Further research will focus on modifying those algorithms in order to supplement them with freshness constraint propagation. Additionally, a possibility for credential issuers to specify freshness requirements hints will be analysed. The work focused on time domain nonmonotonicity. Future work will also include an analysis of system size domain nonmonotonicity.

Fig. 2 .

 2 Fig. 2. Freshness constraints for Adam and John entities.

Table 1 .

 1 Sample freshness constraints definition matrix

	D	predicates
	A	5
	A	10
	B.r	40

Table 2 .

 2 Freshness constraints for example scenario Figure2presents freshness graphs for John and Adam entities with propagated freshness constraints. It was assumed that John has made an order of amount greater than $100, whereas Adam has purchased goods for less than that amount.

	global constraint: t g =100
		function matrix
	D	predicates	t [days]
	eStore		70
	eStore.discount	order.amount > $100	20
	eStore.discount	(order.amount > $100)	50
	ABUS.university.student		180
	SMC.member		30