Marek Dvorsky
email: marek.dvorsky@vsb.cz

Libor Michalek
email: libor.michalek@vsb.cz

Pavel Moravec
email: pavel.moravec@vsb.cz

Roman Sebesta
email: roman.sebesta@vsb.cz

Improved GSM-based Localization by Incorporating Secondary Network Characteristics

Keywords: GSM, localization, TA, RXLEV, SRTM

The techniques used in GSM networks for mobile station localization typically use several methods with different level of granularity, based on the base network parameters such as Cell Identification, Timing Advance, the position of Base Transceiver Station, the parameters of Base Transceiver Station antenna etc. This article introduces several others parameters that can be used for network description. This extension can be useful with visualization of localization outputs in cellular network.

Introduction

The most basic localisation methods are based on the Cell Identification (CELL ID) [5,[START_REF] Samama | Global Positioning: Technologies and Performance[END_REF]. In Global System for Mobile Communications (GSM) networks [START_REF] Ahson | Location-Based Services Handbook: Applications[END_REF], Base Transceiver Station (BTS) serves only a limited geographical area. The identity of the BTS serving Mobile Stations (MS) provides the simplest location information. An accuracy improvement of this method is achieved if BTS uses sector antennas.

Additionally, the accuracy of MS localization for GSM BTS, which covers areas over a distance of 550 m, can be improved by limiting area by network parameter Timing Advance (TA) [START_REF] Ahson | Location-Based Services Handbook: Applications[END_REF]. The TA represents the round trip delay between the MS and the Serving BTS (SBTS). According to the GSM specifications [5], the TA is an integer number between 0 and 63. The accuracy of this method depends on the size of the covered area, ranging from hundreds of meters to several kilometers [START_REF] Eberspächer | GSM-Architecture, Protocols and Service[END_REF]. The main benefit of this method is the independence from the type of MS and a low cost of implementation into the real mobile network [7,[START_REF] Steele | GSM, CDMA One and 3G Systems[END_REF].

The aim of this paper is to describe an extended network parameters, that can be additionally used in the basic location methods in GSM cellular network. It uses measured values of network parameters that contain information about the current network settings and reception conditions in the SBTS and the six Neighbouring BTS (NBTS) [6]. Recorded information is then sent by each MS during communication over the GSM cellular network.

Description of Common Parameters

Parameters Provided by Network

The present localization methods use a set of common parameters provided by the network. In dedicated mode, the MS periodically sends Measurement Report (MR) messages to the network. These messages contain measurements results of parameters defining reception characteristics from the current SBTS and from NBTS cells. The MS can, at most, report the measurements from the 6 strongest BTS. RXLEV of BTS is measured on the Broadcast Control Channel (BCCH) frequencies and with their Base Station Identity Code (BSIC) a Receiving Quality (RXQUAL) parameters are send through Slow Associated Control Channel (SACCH) to the network. For this purpose, so called measurement report is used, see [START_REF]Digital cellular telecommunications system (phase 2+), mobile radio interface layer 3 specification 5[END_REF].

The TA parameter is provided by network in periodic intervals. TA is decremented or incremented by an air interface one-bit period of about 3.69 µs. A one bit adjustments corresponds to a radial distance of approximately 550 m).

Furthermore, the MS receives information elements about identity of cell, such as CELL ID, Local Area Code (LAC), Mobile Country Code (MCC) and Mobile Network Code (MNC). The purpose of the Cell Identity information element is to identify a cell within a location area. The purpose of the Location Area Identification information element is to provide an unambiguous identification of location areas within the area covered by the GSM network. [START_REF]Digital cellular telecommunications system (phase 2+), mobile radio interface layer 3 specification 5[END_REF].

Parameters Provided by Mobile Telecommunication Operator

Configuration of each BTS is unique and depends mainly on the location of the station. Each mobile telecommunication operator stores a database of records, which consist of following parameters: Longitude, Latitude, Altitude of BTS; CELL ID; BSIC; BCCH; ID of Base Station Controller (BSC); LAC that identify to which location area the BTS belongs; max. electrical power; azimuth of antenna; tilt of the antenna -the angle from horizontal (from -90 degrees (fold up) to +90 degrees (fold down)) 3 ; the beam width is angular range of the antenna pattern in which at least half of the maximum power is emitted -this angle is then described as beam width or aperture angle (in the GSM network, there are most commonly used antennas with beam width of 60, 90, 120 and 360 degrees); the antenna Gain.

Measurement Performed by Drive Test

Drive test is a procedure of recording received levels and timing events whilst driving across a cellular network, e.g. GSM. It is frequently performed during the time when the network is deployed. The reason is that no propagation model can be accurate enough to predict the reception levels in every point of the network. Moreover, the tests are performed also once the deployment of a network is finished. The measurement results can be obtained by performing drive tests with an automatic measurement system, which includes a laptop PC, multi-band GSM test phone and synchronized Global Positioning System (GPS), in order to geo-reference the results.

The trace of drive test should be representative across the network. The trace are chosen according to the concentration of population or according to an importance of place, e.g. motorway. In addition, the measurement results can be also used as an input data for development of a new localization method [START_REF] Falcone | Performance analysis by measurement results in operating 3g network[END_REF].

Abnormal Propagation Areas

We can find areas with abnormal wave propagation conditions in the mobile network. Following text describes a base propagation model used at GSM frequency band, typical problematic situations at abnormal areas with connection to a terrain model that is described by Shuttle Radar Topography Mission (SRTM) data.

Problematic Places

When determining mobile node location, the method must take into account a wide range of abnormal situations and conditions, where a general approach which uses combination of several methods is likely to fail or may perform worse than a specific method, suitable only for given situation. Some of these most problematic issues are:

-Signal Reflection -signal reflections cause problems mainly in mountains and heavy urban areas. The problem is reflected in a wrongly reported TA. Obstacles between MS and BTS cause the MS to receive signal reflected from mountains or on other obstacles. As a result, because of the reflected signal the sector is wrongly visualized with radius that has an equal path length as reflected path.

-Side Lobes -one of the antenna parameters is the angle of antenna main lobe α (see chap. 2.2). As a result, the MS is placed aside to main lobe in the direction to so-called side lobe (angle α + ∆). In that case the wrongly visualized sector is limited by α range. In this case it should be detected other antenna sectors and their main lobes. -Repeater -The GSM frequency repeater extends the coverage of a BTS by receiving and re-transmitting signals of the same frequency and at a higher power level.

The repeater is a bi-directional amplifier connected to a given BTS. -Nanocell -the Nanocell BTS improves indoor coverage of a cellular system, e.g. GSM. It is cost effective method that improves coverage and capacity in smaller areas such as conference rooms, sheds, halls etc. In addition, nanocells do not require as accurate network planning due to their low power. We can exemplify the way abovementioned problems influence the localization in an simple example, shown in Figure 1. In this example, we will use only the combination of RXLEV, TA, BTS antenna position and main lobe direction.

When all required information is available, we can use the localization shown in (a) variant. When the antenna main lobe direction is missing, we have to resort to (b) variant. On the other hand, when we do not have the TA value, or expect it to be invalid, we have to resort to variants (c) or (e) if the angle is not available, with RXLEV-based distance limitation, or limiting the distance to technology limits (e.g. 35 km). Should all the parameters be correct, but the reflection is suspected, we can use the pattern (d).

Lastly, should the measured signal come from a nanocell, the distance may be reduced to cover a much smaller area than the TA zone as shown in (f).

Digital Elevation Models

Digital elevation model (DEM) provides the three-dimensional representation of surface obtained from terrain elevation data. They may be represented as a grid, a set of 3D points or a 3D mesh. In our approach, we would prefer the digital surface model, since it is easier to measure and includes the buildings.

Operators already have to use commercial digital surface models for coverage calculations, in our case we have decided to use one of the freely-available public resources. We chose the Shuttle Radar Topography Mission (SRTM) data [START_REF] Rabus | The shuttle radar topography mission-a new class of digital elevation models acquired by spaceborne radar[END_REF], which offers terrain elevation data with the resolution of approximately 90 meters (3") for non-US areas. The SRTMv3 provides sufficient coverage for our main goal, which is the calculation of approximate BTS elevation and detection of mountainous terrain.

Proposed Secondary Attributes

As mentioned in section 3.1, it is impossible to use a combination of even the basic methods in all situations. Based on available parameters of each individual node in network, we can define a set of parameters which locally describe the whole network. Based on them and expert knowledge, we can define heuristics for correct predicted area visualization.

With the knowledge of network parameters, we can define the first set of secondary attributes:

1. Average distance of k-nearest NBTSes -this value can be calculated from network topology, provided by the operator or by obtaining BTS locations form public resources. We will not include co-located sectors in this calculation and use this value for determination of BTS density. 2. Intravillan indicator -based on the Average distance of k-nearest NBTSes, we can determine, if the BTS is likely to be in intravillan or extravillan environment. The threshold between intravillan and extravillan was set to be 3 km, which corresponds to conducted experiments. 3. Intravillan and Extravillan zones -calculated from the average distances, these indicators may be used to judge the expected location determination precision (especially when using other, independent methods [START_REF] Novosad | Mobile phone positioning in GSM networks based on information retrieval methods and data structures[END_REF]) and for visual improvements in GIS presentation. 4. Borders -state or covered area borders may indicate worse localization performance, since measurement reports may contain unknown combinations of BSICs and BCHs, with both national (not recorded) and foreign BTSes. Also, we may not benefit from techniques based on the inclusion of neighbor lists in this case. 5. Co-located neighbor indication -we should identify, if additional sectors of given site are returned in measurement report. In such case, we should also distinguish between sectors co-located in clockwise and counter-clockwise directions. This information can be used for shifting of the predicted angle (or gradient-based visualization), as well as detection of very close proximity to the BTS (based on RXLEVs and other information in measurement report) or excessive reflections, should colocated sectors in both directions be present.

From the BTS position, antenna azimuth and DEM data, we can determine following two attributes:

6. Antenna elevation -can be used for both BTS visualization (and better operator decision-making) and signal propagation models (especially if the altitude has not been supplied by the operator). 7. Terrain granularity -based on the terrain (and corresponding DEM data) in the direction covered by main antenna lobe, we can determine the terrain granularity. With this information, we can expect and detect the problem. The inspected area can be further fine-tuned by the TA and RXLEV values, similarly to the methods used in methods for modeling of signal propagation [START_REF] Backman | Signal level interpolation for coverage area prediction[END_REF]. For instance, this can be used to detect mountainous terrain to prevent invalid localizations by using patterns such as Figures 1b and1d.

Finally, we can include information from actual measurement reports both when doing reference measurements and during the actual localization [START_REF] Novosad | Mobile phone positioning in GSM networks based on information retrieval methods and data structures[END_REF]. Based on these measurements we can define following remaining parameters:

8. Suspicious measurements -BTS data measured during data collection phase together with positions may indicate BTSes where invalid TA values or azimuths were measured. This may be used to prevent invalid visualization and we may use this together with a list of repeater CELL IDs. 9. Broken MS measurement -some values in measurement report may indicate, that it was broken (e.g. the service BTS appears more than once), mostly during the handover. In this case, we have to decide, which pattern from Figure 1 will be used. 10. Nanocell indication -the information may be either provided by operator by special BSC, or by measurements indicating close proximity of BTS but a low RXLEV.

Conclusion

In the paper we have developed the set of secondary attributes which will be used together with basic network parameters provided by operators for the selection of correct localization methods and their combination. The resulting attributes could be used as a basis for visualization techniques. In the next step, these attributes will be combined with parameters from other localization method and a resulting model, based both on patterns from Section 3.1, neighboring cell information and vector space model approach [START_REF] Novosad | Mobile phone positioning in GSM networks based on information retrieval methods and data structures[END_REF] will be used to generate the final area.

In future, we could also define additional attributes or use BTS coverage models to better identify possible locations, especially for the UMTS networks, which lack the TA indicator.

Fig. 1 .

 1 Fig. 1. Example of CELL ID, antenna main lobe and TA (or RXLEV/max. distance) combinations

The work was supported by the IT Cluster 2009-2012 No. 5.1 SPK01/029 grant, funded by the European Fund for Regional Development and Ministry of Industry and Trade, and the paper by the BIOM project, reg. No. CZ.1.07/2.3.00/20.0073, funded by Operational Programme Education for Competitiveness, co-financed by ESF and Czech state budget.

We distinguish from electrical and mechanical tilt. Electrical tilt is used to reduce signal coverage of a sector area because it improves the close area coverage with increased vertical beam width. BTS mechanical antenna tilt is used as a tool for radio network planners to optimize their networks in sense of coverage and capacity[START_REF] Niemela | Impact of mechanical antenna downtilt on performance of WCDMA cellular network[END_REF].


Huaizhou Shi

R Venkatesha Prasad

Vijay S Rao

I G M M Niemegeers

A Fairness Model for Resource Allocation in Wireless Networks

Keywords: Fairness metrics, Resource allocation, Wireless networks, Jain's index, P2PWRAN

In wireless networks many nodes contend for available resources creating a challenge in resource allocation. With shared resources, fairness in allocation is a serious issue. Fairness metrics have been defined to measure the fairness level of resource decisions in allocations. Therefore, fairness metrics significantly influence network and node performances emphasizing the need for due diligence to fairness metrics. It can be seen that fairness metrics in many of the allocation strategies and algorithms in the literature are not analyzed in depth to show the overall fairness of allocations from different perspectives. Hence, we propose a series of fairness metrics for resource allocation in wireless networks, which evaluate individual, system, short and long term fairness. Our metrics are general enough to be adapted in either multiple or single resource sharing scenarios. Algorithms using these metrics for channel allocation problem in peer-to-peer wireless regional area network is proposed and simulated, and the results show that our metrics in conjunction with smart channel allocation strategies guarantee both the fairness and performances.

Introduction

In wireless networks, many resources have to be shared. While in an individual wireless device or node, its computing resources and memory are shared among different applications, at the network level different layers of the device have to operate in synergy with other nodes in order to achieve successful communication and task completion. In a wireless network, channels, time slots, bandwidth, and other resources need to be allocated to different devices in either centralized or distributed way. Hence, resource allocation plays an important role in wireless networking.

Two optimization goals of resource allocation are utility and fairness [START_REF] Montuno | Fairness of Resource Allocation in Cellular Networks: A Survey[END_REF]. Utility reflects the performance of wireless network, and fairness indicates the balance in resource sharing by different wireless devices. Much work can be seen in literature in this regard with emphasis of fairness in resource allocation [START_REF] Montuno | Fairness of Resource Allocation in Cellular Networks: A Survey[END_REF][START_REF] Radunovic | A unified framework for max-min and min-max fairness with applications[END_REF]. Though a detailed discussion on fairness issues for resource allocation in wireless networks covering most of the fairness issues is in [START_REF] Jain | A Quantitative Measure of Fairness and Discrimination for Resource Allocation in Shared Systems[END_REF][START_REF] Radunovic | A unified framework for max-min and min-max fairness with applications[END_REF], there is still a lack of general fairness model. Some issues still need more considerations, for example, not treating fairness as an independent issue [START_REF] Montuno | Fairness of Resource Allocation in Cellular Networks: A Survey[END_REF], confusing it with resource allocation itself or utility [START_REF] Zheng | A two-phase utility maximization framework for wireless medium access control[END_REF], and only considering absolute fairness during allocation in which weights are not adopted or every individual is assigned with the same weight [START_REF] Jain | A Quantitative Measure of Fairness and Discrimination for Resource Allocation in Shared Systems[END_REF][START_REF] Kelly | Rate control for communication networks: shadow prices, proportional fairness and stability[END_REF][START_REF] Radunovic | A unified framework for max-min and min-max fairness with applications[END_REF].

In this paper, we discuss related work on fairness metrics in wireless networks in Section 2. We propose a new fairness model for resource allocation that contains a series of fairness metrics in Section 3. These metrics provide an entire view of fairness with multiple fairness metrics. The simulations in Section 4 confirm that our metrics can be employed in resource allocation in wireless networks easily. Conclusions are provided in Section 5.

Related Work on Fairness Issues

Some commonly adopted fairness metrics in wireless networks in the literature are Jain's index, max-min and proportional fairness [START_REF] Jain | A Quantitative Measure of Fairness and Discrimination for Resource Allocation in Shared Systems[END_REF][START_REF] Kelly | Rate control for communication networks: shadow prices, proportional fairness and stability[END_REF][START_REF] Radunovic | A unified framework for max-min and min-max fairness with applications[END_REF]]. Jain's index does not consider the individual fairness. Another shortcoming is that it cannot be adopted in multiple resource allocation scenarios. Moreover, weighted strategies are not considered in it, and all individuals are treated similarly during allocations, which is hardly true in reality. Max-min indicates a decision 0, 1 whether the allocation is fair or not (1 implying fair allocation). Thus, max-min fairness cannot measure the level of unfairness. Also, it cannot distinguish between system and individuals. Similar to Jain's index, it is an absolute fairness metric without weighted strategies and individual fairness. Modified max-min fairness are proposed (for example in [START_REF] Bertsekas | Data networks[END_REF]) to add weights, but they cannot measure the individual fairness. Proportional fairness, however, cannot measure how unfair the system is, and no weighted strategies are considered originally. An advanced proportional fairness metric (p, α) -proportional fairness was proposed in [START_REF] Mo | Fair end-to-end window-based congestion control[END_REF]. Weights of different resources for an individual are added in this model. However, it cannot measure both individual and system fairness. Moreover, assigning the weights to individuals was not described in detail.

Considering the shortcomings in these existing fairness metrics, we try to propose a fairness model which includes a series of fairness metrics for resource allocation that can measure the fairness of a resource allocation decision in the aspects of system, individual, short, and long term fairness.

Fairness Model

We assume that there are m (m 1) different resources, and the capacity of resource k is C (t) k . n individuals are in the system. The allocation decision at time t is

X (t) = (X (t) 1 , ..., X (t) n ), in which X (t) k is the allocation of resource k and X (t) k = (x (t) k1 , ..., x (t) kn ). x (t)
ki is the amount of resource k that is allocated to individual i. Furthermore, F (t) k (X (t) ) is the system fairness metric on resource k and f (t) ki (X (t) ) is the fairness metric for an individual i for resource k. f (t) i is the fairness of individual i on all resources. When m = 1, it is single resource allocation and we just drop the resource subscript, for example, C (t) is the resource capacity,

X (t) = (x (t) 1 , ..., x (t)
n ) is the allocation decision for an individual i. We consider two elements during the weight assignment, which are request ratios and historical allocation information. For individuals with more requests and less historical allocation than others, heavier weights should be assigned to them, giving them higher chance to obtain more resources. Let

R (t) = {R (t) 1 , ..., R (t) m } stand for request at time t, in which R (t) k is the allocation request for resource k. R (t) k = (r (t) k1 , ..., r (t) kn ) and r (t)
ki is the request of resource k from individual i at time t. We assume that x

(t) ki r (t) ki C k .
We also assume the weights are

W (t) = {W (t) 1 , ..., W (t) m } and W (t) k = (w (t) k1 , ..., w (t) km ), in which W (t) k
is the weights of resource k, and w

(t)
ki is the weight of individual i for resource k at time t. We assign the weight w (t) ki as,

w (t) ki =                    0 If r (t) ki = 0; e 1-i r (t) ki nr (t) ki Else if t,i x ki (t) = 0; e      1-Kr i r (t) ki nr (t) ki -K h n t,r (t) ki =0 x (t) ki r (t) ki t,i,r (t) ki =0 x (t) ki r (t) ki     
Otherwise.

(

) 1
Where

w (t)
ki indicates the importance and priority for a resource k set by an individual i at time t by considering the request and historical allocation. K r and K h (K r ≤ 0 and K h ≤ 0) are the factors for the current request and historical allocation, and Kr + k h = 1. Therefore, 0 w (t) ki e. Based on the weights and request, we define "fair ratio" e (t) ki in Eq. ( 2), which indicates the satisfaction level of an individual to the current allocation.

e (t) ki =      e 2 If r (t) ki w (t) ki = 0; e   x (t) ki r (t) ki   w (t) ki
Otherwise.

(2)

All our following short and long term and individual and system fairness metrics in this paper are based on fair ratios (e

(t)
ki ). Incase where there is no request or weight is zero, an individual is satisfied with (e

(t)
ki = e 2 ), otherwise, the satisfaction depends on the ratio of its allocation and weight.

The short term system fairness metric for resource k at allocation t (can also be a discrete allocation number) is given by Eq. ( 3) where 0 F k (X

(t) k ) 1.
It is a variant of Jain's index with the weights and can measure fairness even in multiple resources scenarios.

F (t) k (X (t) k ) =          0 If i e (t) ki = 0; 1 Else if i w (t) ki r (t) ki = 0; i e (t) ki 2 n i e (t) ki 2 Otherwise. (3)
The short term individual fairness of individual i on resource k is shown in Eq. ( 4), which measures the current fairness of one individual over a certain resource, and 0 f

(t) ki
1, but with the historical allocation information.

f (t) ki =    0 If e (t) ki = 0; e -i e (t) ki ne (t) ki
Otherwise.

(

) 4
The individual fairness of i for all resources is described in Eq. ( 5), which is the fairness metric for an individual in the whole resource allocation with multiple resources.

f (t) i =    0 If k e (t) ki = 0; e -k,i e (t) ki n k e (t)
ki Otherwise.

(

) 5
Similar to short term fairness metrics, system and individual long term metrics are proposed in Eq. ( 6), [START_REF] Montuno | Fairness of Resource Allocation in Cellular Networks: A Survey[END_REF], and [START_REF] Radunovic | A unified framework for max-min and min-max fairness with applications[END_REF], in which the fairness ratios e (t) ki are considered in a long time period instead of a single time slot.

F k (X k ) =          0 If t,i e (t) ki = 0; 1 Else if t,i r (t) ki = 0; t,i e (t) ki 2 n i t e (t) ki 2 Otherwise. (6)
f ki =    0 If t e (t) ki = 0; e -t,i e (t) ki n t e (t)
ki Otherwise.

(7)

f i =    0 If t,k e (t) ki = 0; e -t,k,i e (t) ki n t,k e (t)
ki Otherwise.

(

) 8
Our model is proposed keeping in mind multiple resource allocation scenarios. As a special case for single resource allocation, we just need to set m = 1, and all metrics and the mechanisms stay the same. For distributed scenarios, allocation decisions are made by individuals instead of a centralized allocation manager. Therefore, the metrics only use the local information they collect, and localized fairness and utility can be achieved. The following advantages can be seen in our fairness metric for resource allocation:

-We adopt a weighted strategy and define it by considering the request and historical allocations, which assign priority to individuals due to their requests and historical allocation information. -Both system and individual fairness can be measured by our metrics, which describe fairness on different aspects. -The fair ratio e (t) ki considers the satisfaction of individuals in an allocation, which gives a more precise description of fairness feature than absolute fairness [START_REF] Jain | A Quantitative Measure of Fairness and Discrimination for Resource Allocation in Shared Systems[END_REF][START_REF] Kelly | Rate control for communication networks: shadow prices, proportional fairness and stability[END_REF][START_REF] Radunovic | A unified framework for max-min and min-max fairness with applications[END_REF].

-Short term and long term fairness can be measured by our metrics, which may be used in different applications.

-Our fairness model is proposed for multiple resource fair allocation in wireless networks; however, it can also be adapted to other diverse scenarios with slight modification.

Simulations and Results

An Example Scenario

Peer to peer WRAN (P2PWRAN) was proposed in [START_REF] Shi | An intra-cell peer to peer protocol in ieee 802.22 networks[END_REF]. P2PWRANs support peer to peer communication in a cell thereby increasing the network capacity by many folds. At the same time, a problem in P2PWRANs is how to allocate the channels efficiently and fairly. Channel allocation has two parameters -(i) total number of available channels, and (ii) interference amongst inter-CPE communication1 . It is not easy to achieve a fair resource allocation at all times. Therefore, we test our definition of fairness metric model in the channel allocation scenario in a P2PWRAN cell. Two types of communication can be seen in P2PWRAN communication in a cell, which are communication between CPEs and between CPE to BS. The allocation of channels for CPEs can be treated as a multiple resource allocation case. The first type is the channel allocation for CPE to CPE communication and the other type is the channel allocation for CPE to BS (and BS to CPE) communication. Channel allocation in standard WRAN is queue based [START_REF] Ko | Channel management in IEEE 802.22 wran systems[END_REF]. Hence, we first queue the channel requests from CPEs, then allocate channel sequentially to the request if no interference is expected to occur. Three different mechanisms for queuing channel requests were adopted in the channel allocation for P2PWRAN in our simulations as follows.

-First one (M1 ) is the absolute fair queuing mechanism, in which the requests are queued considering the channel allocation history of the nodes. CPEs which have received lesser channels have more chance of getting a channel in the current time slot. M1 treats every individual identically, and tries to reach absolute fairness amongst all individuals during channel allocation. -The second mechanism (M2 ) is based on our long term individual fairness metric. The long term individual fairness is employed as the basis for queuing. With (M2 ), CPEs which are not treated fairly in the past would have more opportunities to obtain channels. -The third mechanism (M3 ) queues the requests due to the possibilities of the interference that the requests may cause. Since, if the same channel is allocated to two request (r i , r j ) both of which cause less interference than two other requests (r i , r j ), then it is better to allocate the channel to r i and r j . Generally, requests with shorter transmission distances cause lesser interference than requests with longer distances. Therefore, the transmission distances of the requests are used to queue channel requests, and requests with short transmission distances are allocated first. The purpose of M3 is to reuse channels efficiently.

Results

The network performance on channel reuse and node throughput can be seen in Fig. 1. In Fig. 1(a) and 1(b), the queue mechanism based on our fairness metrics lead to the higher channel reuse times for every channel and most of the nodes obtain higher throughput than the absolute fair mechanism and distance based mechanisms. With our metric in M2 , node requests are queued considering individual long term fairness and the ratios of node requests and historical allocation decisions, and it leads to the best performance amongst the three mechanisms.

We can also see in the figures that fair mechanisms performs better than the distance based mechanisms (M3 ). The individual fairness of channel allocation is shown in Fig. 2 with both short term (Fig. 2(b) and Fig. 2(d)) and long term fairness (Fig. 2(a) and Fig. 2(c)). For CPE to CPE communication, the mechanism based on our metrics (M2 ) results in fairer allocation than absolute fair mechanism M1 and distance based mechanism M3 in both short term and long term fairness. The individual long term fairness is adopted to queue the request, therefore, it results in fairer individual allocation in CPE to CPE communication. However, the short term fairness is still much lower than the long term fairness, because the channels are very rare compared to amount of requests. For CPE to BS allocation, the amount of requests (on average more than 20 requests in a time slot) is much higher than the allocation rate (once in a time slot). Hence, both long term and short term CPE to BS fairness are very low, as shown in Fig. 2(d) and Fig. 2(c).

Results of system fairness are shown in Fig. 3 including both short term and long term system fairness. For CPE to CPE communication, long term fairness is adopted to queue the requests, therefore, mechanism (M2 )leads to fairer allocation than M1 and M3 as shown in Fig. 3(a). The short term system fairness for CPE to CPE with M1, M2 and M3 are similar to each other as shown in Fig. 3(b). The long term system fairness for CPE to BS (Fig. 3(c)) are very low because only one node can obtain a channel in one time slot, and the fairness for the rest is assigned to be 0. The short term fairness for CPE to BS is increased by M2 (Fig. 3(d)) because in many time slots there is no CPE to BS request, and the short term system fairness is assigned as 1. Concerning all the resources and their allocation, fairness issue plays an important role in wireless networks. However, the metrics nowadays has many shortages. Therefore, a series of fairness metrics are proposed in this paper for resource allocation in wireless networks, which can measure the fairness of allocation from the point of view of individuals and system, further, also from the point view of short term and long term. We applied the developed fairness metric for IEEE 802.22 WRAN scenario. We also applied our metric to test the allocation fairness in a futuristic P2P channel usage in WRANs. The simulation results show that the metrics can be employed in wireless resource allocation mechanisms easily. When it is adopted in the channel allocation in P2PWRAN, higher fairness and performance can be achieved than the fairness and performance when absolute and distance based mechanisms are used. We are now planning to focus on more number of implementation scenarios (for example in rate allocation, flow and packet scheduling, power control and energy control) to test our metric, and testing its ability of measuring fairness.

Fig. 1 .

 1 Fig. 1. Performances.

  (a) Long term CPE to CPE fairness. (b) Short term CPE to CPE fairness. (c) Long term CPE to BS fairness. (d) Short term CPE to BS fairness.

Fig. 2 .

 2 Fig. 2. Individual fairness.

Fig. 3 .

 3 Fig. 3. System fairness.

For a more detailed discussion of channel allocation in P2PWRAN we refer to[START_REF] Shi | An intra-cell peer to peer protocol in ieee 802.22 networks[END_REF].


Eleni Agiatzidou

Costas Courcoubetis

Olivier Dugeon
email: olivier.dugeon@orange.com

Finn-Tore Johansen
email: finn-tore.johansen@telenor.com

George D Stamoulis
email: gstamoul@aueb.gr

Inter-domain Coordination Models

Keywords: Charging and pricing QoS, game theory, end-to-end services

In order for the Network Service Providers (NSPs) to provide end-to-end Quality of Service (QoS) at the inter-domain level different coordination models have been proposed by ETICS project. In this work we present and analyse the plausible alternatives of those models and we compare them with each other in terms of information asymmetry issues. We show that different information sets affect the total service provision and we present a basic model analysis on information issues by means of game-theoretic models.

Introduction

QoS enabled services such as Gaming as a Service require end-to-end (interdomain) connectivity that can be achieved through the existence of agreements among the involved Network Service Providers (NSPs). Interconnection agreements are constantly changing to fulfil the needs of the new technologies affecting the Internet architectures [START_REF] Faratin | Complexity of Internet Interconnections: Technology, Incentives and Implications for Policy[END_REF]. The FP7 ETICS project [2] studies those Internet architectures and the collaboration models that are capable of sharing information about business and technical parameters to provide QoS-enabled end-to-end connectivity services.

According to the ETICS solution, the NSPs share information concerning the traffic source, destination and the statistics of the QoS-enabled service, as well as the price of their part of the service. The price affects the final service that will be provided to the buyer. The revelation of the buyer's willingness to pay may lead to advantageous positions for some providers. On the other hand the total price that the chain of providers asks for an end-to-end service may lead to failure of its provision. Also in cases of many paths between a source-destination pair the pricing strategy of an NSP may affect the final chain of NSPs that will serve the customer. In this paper, we study a variety of inter-domain coordination models defined in the framework of ETICS, and we address the information and coordination issues that arise. The knowledge of how the information affects the formation of the end-to-end paths is necessary for the right definition of pricing and revenue sharing models.

In section 2 of the paper we describe the ETICS framework while in section 3 we present the different inter-domain coordination models. In section 4, we present a comparison of the models based on information issues. In section 5, we formulate a game-theoretic model pertaining to one of the above models in its simplest form in order to draw some preliminary conclusions that verify our initial analysis.

ETICS Framework

The ETICS project [2] has introduced the notion of the ETICS Community. Fig. 1 depicts the interaction between the ETICS community and a customer, who asks for provision of a QoS service from its collaborating NSP inside the ETICS community.

¡ ¢ £ ¤ ¥ ¦ ¤ § © £ ¤ £ ¦ § ¨ ¤ £ Fig. 1. ETICS Community
The nodes that belong to the ETICS Community collaborate in order to provide QoS-enabled services to members and non-members. Those nodes represent edge, transit or transport NSPs and form paths between an S (source) and a D (destination) NSP. In our considered case, the objective of NSP S (which we will call "buyer" to differentiate from the "customer" which does not belong to the community) is to buy connectivity to an IP range in domain NSP D allowing its packets to reach the specific destination under the conditions desired. Besides the destination range, a Point of Interconnection (PoI) and specific requirements, such as maximum delay, minimum bandwidth, jitter, period of validity etc. have to be defined. The PoI describes where and how the traffic is exchanged between two NSPs. These parameters along with a price specify completely a service that is provided to the buyer, or in other words an SLA offer, which has to be created from sub-SLAs offered by the various NSPs in the path. For the provision of a bundled offer, the NSPs participating in the community have to share information about what they are willing to provide. This is the Publishing Phase. When a buyer is willing to purchase a QoS-enabled service, the Service Composition Phase is triggered to perform the abutment of the different sub-SLA offers in order to provide a global proposal to the buyer. In the next section we study the different scenarios of those two phases and the effect that different information sets may have on the pricing strategies of the participants.

Inter-domain Coordination Models

As studied in [START_REF] Constantiou | Information Asymmetry Models in the Internet Connectivity Market[END_REF], the role of information asymmetry is critical when considering interconnection agreements. The way information about NSP network capabili-ties is propagated affects the topology that each NSP will be aware of after the Publishing Phase. The Service Composition Phase can be performed by using Centralized and Distributed models. The Centralized models require the existence of a central entity, called Facilitator, which gathers information from the NSPs and assists the composition of the offer under agreed selection criteria. In the Distributed models the information is propagated between neighbors only. The Service Composition can furthermore be done by using Push and Pull models, which concern the creation time of the offer. In Push models, the offers are available before a buyer's request while in Pull models the offers are created upon a buyer's request. The combination of those models and the creation of two hybrid ones results in six different scenarios. For all these scenarios we investigate the minimum information set that each participant must have available in order for the model to serve its purpose. In all subsequent scenarios, we suppose that an ETICS customer issues requests to the NSP S about connectivity from NSP S to D. Even if we show only one intermediate NSP A for the clarity of the figures, all scenarios could be extended to many intermediate NSPs.

! " # $ $ % & ' ( ) 0 0 1 2 3 ( 4 5 6 7 1 8 9 1 @ A B ( C 9 D E F 1 E ) 0 0 1 2 Fig. 2. Distributed Push Model Fig. 3. Distributed Pull Model
Fully Centralized Push Model. During the Publishing Phase all NSPs in the community inform the Facilitator about their sub-SLA offers. For the rest of our analysis we assume that these sub-SLA offers contain: the logical point(s) of interconnection (PoI), the destination(s) network(s) prefix, the QoS characteristics, the expiration time of the offer and a price. The Service Composition Phase begins with the buyer's request. The buyer (S ) communicates with the Facilitator and reveals only the PoI (where its traffic is taken care of the ETICS Community), the destination and the QoS characteristics that it wishes to have for the specific end-to-end connectivity (SLA Request). The Facilitator, based on the knowledge that it already has due to the Publishing Phase and the SLA request, combines sub-SLA offers of those NSPs that form a chain from the source NSP to the destination NSP(s). If there are multiple possible offers, the model is flexible regarding the selection criteria of the Facilitator. Indeed, it can choose the best offer from a social welfare or the buyer's point of view or even let the buyer decide. The buyer may accept or not the price of the bundled SLA offer(s) presented by the Facilitator (Fig. 2).

Fully Centralized Pull Model. The Publishing Phase of this model is slightly different from the previous one. The Facilitator is aware of the Network Capabilities (PoIs, and QoS characteristics but not the final price offer) of all NSPs of the community. Based on this information, the Facilitator computes one or multiple NSP chains that could potentially handle the buyer's request for PoI, destination and QoS characteristics. When it receives a request from the buyer it sends specific sub-requests to the NSPs in those chains. After receiving the sub-SLA offers, it combines them. The best offer is chosen under one of the criteria that previously mentioned (Fig. 3).

Distributed Push Model. In this model the information that is available to each NSP depends entirely on the Publishing Phase. Each NSP in this phase publishes its sub-SLA offers to all of its neighbors, to a subset of them or to the whole community. In the first two cases each NSP may combine its own offers with all the offers that it is already informed about and propagate the combined offers to other NSPs in order for the information to be diffused to other participants. Thus, each NSP may be notified about already bundled sub-SLA offers that are available in the community in a cascading way. The buyer will negotiate with its neighbor in order to buy a bundled offer (Fig. 4). The Composition phase begins with the buyer's request for connectivity from its neighbor(s) in order to reach a destination (Fig. 5). The neighbor accepts (or rejects) this SLA Request by providing a price offer. In case of accepting, it extracts the part of the requesting SLA that corresponds to its Network Capabilities and adds a price. It subsequently propagates the price and the remaining Network Capabilities requirements to its neighbor(s). After the destination NSP adds a price to the SLA request, the complete offered price is propagated back to the buyer in the reverse cascading way, which then accepts or rejects the final offer. Clearly, the position of an NSP in the chain can affect its strategic power. Such issues can be analyzed by means of game-theoretic models; as discussed in Section 5.

G H I P Q R S T R U V V T W X H U V V T W
Per-NSP Centralized Push Model. This model is a hybrid of the Centralized and the Distributed Push models. The NSPs create sub-SLA offers (including prices) that are published to catalogues that are available to the community.

In the Composition Phase the buyer combines offers and creates a bundled one that fulfils its needs. As opposed to the Distributed model, here the buyer buys the SLA offers from each NSP even if it is not directly connected to it (Fig. 6).

Per-NSP Centralized Pull Model. The buyer is informed about the Network Capabilities that each NSP is willing to provide during the Publishing Phase.

During the Composition Phase it asks each NSP in the chain for an SLA offer (which is a part of the whole ASQ good that it wants). In this model (Fig. 7) the buyer communicates separately with each NSP in the chain. The apportioning of price and/or QoS is done according to the buyer's own strategy who leads the composition.

Information Issues on the Inter-domain Coordination Models

The total price of the service, the revenue sharing among the NSPs (affected by means of the prices assigned to their sub-SLA offers) and the selection of the NSPs that will participate in providing a service differ across the models. These differences have their origin in the information set that is available to each NSP and is formed during the Publishing Phase, as well as in the fact that a different entity makes the decision of the optimal offer in each model.

In case of a Centralized model the Facilitator has all the available information during the Publishing Phase. In the Distributed models the information must be propagated through the NSPs. The simplest way is to propagate information to the direct neighbors who undertake to bundle it with their own and redistribute it. However, this approach allows for strategic behaviors. For example, an NSP may decide not to propagate the information of all of its neighbors. This may result in different visible options for topologies due to different sets of information available. To overcome this possibility, rules may be enforced in the community in order for the information to be propagated equally. For example a rule could be enforced that the information must be flooded to all community members. Per-NSP Centralized models suffer from the same problem as the Distributed ones. Even if NSPs publish their information in catalogues which can be accessed by every member and thus allowing equal information to all, a minimal set of information about the topology and how the NSPs can be reached has to be available to all participants in the community.

The entity that makes the choice about the optimal offer that will be purchased may be the Facilitator or the buyer. One of the approaches applying to the Centralized models is for the Facilitator to propagate the available choices to the buyer and let it decide; alternatively, the Facilitator may decide according to its own criteria on the final choice, or on a subset of them which are subsequently passed to the buyer for the final selection. In such a case the Facilitator can choose to maximize the expected social welfare, thus improving the overall well-being of the community of customers. Related criteria may be the maximization of the number of buyers that can be satisfied, or of the utilization of the network. Alternatively, the Facilitator can choose the optimal offer by applying potential buyers criteria, typically the lowest price.

In the Distributed (and Per-NSP) models the buyer accepts or not the final offer(s) that are reaching it and thus it has the final choice. However, each NSP may influence the price of the bundled offer. Putting a high price in its part of the service an NSP increases both its profits if this offer is indeed purchased and the risk of rejection of the offer. Authors in [START_REF] He | Pricing and revenue sharing strategies for Internet service providers[END_REF] present similar problems and show that non-cooperative pricing strategies between providers may lead to unfair distribution of profit. Moreover the position of an NSP in the path to the destination may influence the price that it claims for its part of the service. Thus, certain NSPs may have an advantage in this model due to their position; e.g. the first NSP in the chain, or possibly bottleneck or central NSPs. As this constitutes a problem for all models where the NSPs publish their prices sequentially, and thus most of our models depending on their implementation, we illustrate in the following section the analysis of a simple Distributed Pull model that highlights the effect of the advantageous position of an NSP.

Analysis of a Distributed Pull Model

The effect of having an advantageous NSP position in the chain on pricing strategy and on the price of the whole service is presented through a theoretical analysis of a simple Distributed Pull model. We compare the model's efficiency in terms of the probability of the service being offered to the basic collaborative model where the NSPs share the price of the buyer so that they have equal profits.

We assume that we have only three NSPs in the chain; thus, the buyer S requests from A an SLA to connect to D (see Fig. 5). We assume that the Publishing Phase has already been completed and all NSPs have the same set of information about the network capabilities of the other NSPs. The Composition Phase is initiated by S who sends its request for a particular SLA. After deciding on its price P A , A propagates the SLA and P A to D. (Note that the results are still applicable if we reverse the roles of A and D, with D choosing first.) D decides its own price P D and they propagate P A + P D to the buyer which takes the offer or not. For A and D to agree to make the transaction their prices have to exceed their costs (C A , C D ). Also P A + P D ≤ P S and C A + C D ≤ P S , where P S is the price that the buyer is willing to pay, should apply in order for the service to be ultimately provided. Also, both the costs are here assumed to be known to both the providers who only know the distribution of P S . The problem that the NSPs A and D have to solve is:

maxE [(P * (C * ) -C * ) * 1 (Service is provided)] (1)
The interaction of A and D corresponds to a Stackelberg game. The optimization problem for D is:

where P A is a function of C A , and C D s.t. P A ≥ C A .

In order to proceed with the analysis of a simple yet illustrative case, we assume that P S follows a uniform distribution and thus P S ∼ U [0, P S max]. Since A chooses its price first it will choose P A such that 0 ≤ P A + C D ≤ P S max. It can avoid the case of P A + C D ≥ P S max (where the service is not provided) since it is assumed to know C D too. (Note that A can be assumed to have some knowledge on the cost of D if e.g. they have similar infrastructure. Of course, the assumption that this knowledge is accurate is only adopted for preserve simplicity of the model.) Once P A is announced to D, then the only feasible and at the same time meaningful choice for P D is to satisfy: P A + P D ≤ P S max. Solving the maximization problem for D we obtain the optimal choice for him (P * D ). Subsequently, we solve the maximization problem of A. The value of P * D is not known to A. It comes as a result of the choice of P A by A. However, A can make use of the expression of P * D and then calculate P A on this basis. A will choose P A such that P * D + P A ≤ P S max. Through those optimal choices we can calculate the actual profits of A and D in the cases that the service is indeed provided. In the table below, we show some numerical values of those profits and we compare them to the Collaborative scenario. As presented and also proved in closed form the profits of A in the Distributed Pull model are always higher than in the Collaborative one and also double those of D. Also the third row shows a case of a failure of service provision under the Distributed model in contrast to the Collaborative one. The last row shows a failure of both models due to a low price of the buyer. Also we can evaluate this model by showing the loss in efficiency. This loss can be quantified by comparing: a) the probability P r[P * D + P * A ≤ P S ] (see eq. 4) that the service is achieved under this model, where A and D follow their own optimal strategies (P * A , P * D ); and b) the probabilityP r[C D + C A ≤ P S ] (see eq. 5) that a service is achieved collaboratively. Thus, when the NSPs act selfishly (Distributed Pull model) there is a huge loss in efficiency, resulting in a reduction of the probability that the service is offered by a factor of 4.

Conclusions

In this paper we have studied the different coordination models proposed by the ETICS project and the way that different information sets affect the service provision under those models. Our research (only partly reported in this paper) has shown that for the Distributed models, either in Push or Pull ones, NSPs may gain an advantageous position against others by excluding a neighbor from having information of other NSPs and thus resulting in a topology different than that in a Centralized model. On the other hand the adoption of a Centralized model implies the concentration of all the information from the NSPs in one single entity which has to be unbiased and meet an optimization goal agreed by all community members. Therefore, future work on the ETICS architecture should consider and evaluate the alternative of using appropriate rules to promote collaboration and deter aggressive selfish pricing strategies.

Fig. 4 .

 4 Fig. 4. Distributed Push Model Fig. 5. Distributed Pull Model Distributed Pull Model. During the Publishing Phase the NSPs exchange information about their Network Capabilities. As in the previous model, the NSPs may decide what kind of information they publish and propagate to each of their neighbors.The Composition phase begins with the buyer's request for connectivity from its neighbor(s) in order to reach a destination (Fig.5). The neighbor accepts (or rejects) this SLA Request by providing a price offer. In case of accepting, it extracts the part of the requesting SLA that corresponds to its Network Capabilities and adds a price. It subsequently propagates the price and the remaining Network Capabilities requirements to its neighbor(s). After the destination NSP adds a price to the SLA request, the complete offered price is propagated back to the buyer in the reverse cascading way, which then accepts or rejects the final offer. Clearly, the position of an NSP in the chain can affect its strategic power. Such issues can be analyzed by means of game-theoretic models; as discussed in Section 5.

Fig. 7 .

 7 Fig. 6. Distributed Push Model

  max [(P D (C D ) -C D ) * P r [P A + P D (C D ; P A ) ≤ P S ]] (2) where P D is a function of C D and P A , s.t. P D ≥ C D . Knowing that D will act this way, the optimization problem for A becomes: max [(P A (C A ; C D ) -C A ) * P r [P A (C A ; C D ) + P D (C D ; P A ) ≤ P S ]]

  P r[P* D + P * A ≤ P S ] = P r[ 3P S max + C A + C D 4 ≤ P S ] = P S max -C A -C D 4P S max(4)P r[C D + C A ≤ P S ] = 1 -P r[P S ≤ C D + C A ] = P S max -C A -C D P S max(5)

Table 1 .

 1 Comparison of Profits of A and D

	(CA, CD, PS)	Collaborative Model	Distributed Pull Model
		Actual Profits	Actual Profits of A Actual Profits of D
	(0.043, 0.169, 0.649)	0.218	0.394	0.197
	(0.113, 0.030, 0.939)	0.387	0.417	0.208
	(0.075, 0.054, 0.531)	0.200	-	-
	(0.547, 0.138, 0.149)	-	-	-

Acknowledgments. The research work of E. Agiatzidou has been co-financed by the European Union (European Social Fund-ESF) and Greek national funds through the Operational Program Education and Lifelong Learning of the National Strategic Reference Framework (NSRF) Research Funding Program Heracleitus II. Investing in knowledge society through the European Social Fund. Also, this work has been performed in the framework of the EU ICT Project ETICS. The authors would like to thank all ETICS partners for their useful discussions on the subject of the paper and specially M. Dramitinos, N. Le Sauze, H. Pouyllau, P. Zwickl and A. Cimmino.


Till Wollenberg
email: till.wollenberg@uni-rostock.de

Estimation of expectable network quality in wireless mesh networks

Keywords: wireless mesh network, network quality, prediction, smart environments

Our work aims to improve the usability of wireless mesh networks as communication layer of smart office environments. While wireless mesh networks are well-suited for this task in general, the negative impact of interference, fading, and saturation makes the communication basically opportunistic. Our goal is to develop a system which allows a short-term estimation of network quality in terms of throughput, packet loss and latency. The estimation is based on channel measurements and detected high-level activities. With the estimated quality, we expect a significant improvement to user assistance and a speed-up of device integration. In this work-in-progress paper, we define the fundamental problem and its background and design a system that is suitable to solve the problem. We also present some preliminary results from ongoing experiments we carry out in a custom indoor test bed.

Introduction and Background

The work presented in this paper is part of a larger research project which focuses on user assistance in smart environments (SE). These environments are composed of an ensemble of various devices, many of them mobile or portable. The application scenario covers instrumented rooms-referred to as smart meeting rooms-that support teams in tasks such as knowledge exploration and knowledge integration. The present devices include laptops, smart phones, projectors, lights, motorized blinds and canvases, sensors for light intensity and temperature, cameras, microphones and indoor positioning systems.

These devices need to cooperate spontaneously in order to assist the user. The assistance is based on the user's inferred intentions. For achieving their joint goal, it is inevitable that the devices form a network and communicate among each other. According to [START_REF] Poslad | Ubiquitous Computing: Smart Devices, Environments and Interactions[END_REF], network concepts suitable for the task must provide Wireless mesh networks (WMN) based on IEEE 802.11 Wireless LAN fulfill almost all of the requirements and are therefore well-suited for this task [START_REF] Akyildiz | Wireless mesh networks: a survey[END_REF]. The technology is commonly available and achieves a throughput which is comparable to Fast Ethernet when using 802.11n. WMN require routing mechanisms that compensate for the inherent properties of wireless communication such as time-varying quality of links as well as movement, arrival, and disappearance of devices. Numerous different approaches exist which implement the mesh functionality either on the network layer (such as OLSR-LQ) or on the link layer (such as 802.11s).

The link quality of the wireless links has a significant effect on the network quality in terms of packet loss, throughput, and latency. Therefore, the applied routing metric must take the current link qualities into account in order to find optimal routes. As to that, numerous cost functions have been developed in the past [START_REF] Baumann | A survey on routing metrics[END_REF]. The main reasons for the variations in link quality are (a) fading due to attenuation and multipath propagation, (b) interference caused by non-WLAN devices, and (c) transmissions of neighboring WLAN devices.

The 2.4 GHz and 5 GHz frequency bands which are used for WLAN are also utilized by various other wireless systems which normally cannot decode WLAN transmissions (b). Thus, cooperative sharing of the wireless channel does not work here. Additionally, transmissions of other WLAN devices can degrade the link quality significantly (c) because of collisions and the shared medium access.

To enforce certain service qualities in wireless networks, different methods have been proposed. Both or either of prioritization (such as in 802.11e) or reservation (such as in [START_REF] Carlson | A distributed endto-end reservation protocol for IEEE 802.11-based wireless mesh networks[END_REF]) are commonly used. However, these approaches work neither in the presence of interference caused by non-WLAN devices nor in case of WLAN stations which do not support the corresponding protocols. In the context of our work, we therefore consider the communication in WMN to be basically opportunistic.

Goal

Our research project aims at improving the usability of WMN for smart office environments. In these environments, devices execute autonomously planned action sequences. In order to execute a particular action, the network requirements of this action must be met. For the reasons stated in § 1, we can neither use reservation nor prioritization to guarantee this. Our goal therefore is to estimate the short-term network quality. For this, we need to create empirical models that allow us to determine the expectable network quality in terms of throughput, packet loss, and latency.

The estimated values will be used as an input to the strategy synthesis. The main challenge of the strategy synthesis component is to generate device action sequences which are then executed by the devices of the ensemble. Generated sequences need to be validated in order to decide whether they are executable. The estimation of network quality is a valuable input in this validation process. For example, a remote user wants to participate in a meeting which takes place in a smart meeting room. With respect to the user experience, the system should only offer a video chat with the remote user if the network conditions currently allow a stable video transmission. Otherwise, the system may offer only an audio transmission. Also, it is possible to exclude certain actuators during planning if it is known that control commands will not reach these actuators reliably because of high packet loss conditions.

Moreover, the models to be developed will help us to reduce the time needed to integrate a new device into the network. Currently, routing protocols commonly measure the link quality be sending and counting test packets. We can omit this time-consuming process if we can estimate the link quality after only a few exchanged packets. Finally, the experiments we carried out in order to create and validate the empirical models are also helpful to understand the real-world patterns of interference and network usage in smart office environments.

System Description

Based on the requirements outlined in § 1 and § 2 we designed a system which allows us to estimate the quality of a link in the mesh network from (i) knowledge about the intensity and frequency of interference, (ii) the activity of all neighboring WLAN devices, (iii) information about detected user activities, and (iv) the current channel state. If such information is available for all links within a path between two communicating devices, we can estimate the quality for the entire path. For (i-iii), we consider not only the current conditions, but use also recorded, historic data for prediction. For (iv), we consider only the current state since even minor movement of devices or obstacles can influence the channel significantly due to the strong effects of multipath propagation in indoor environments. A prediction is therefore not promising here. We designed the system in respect to the possibilities of commercial offthe-shelf hardware to allow straightforward prototypic implementations. Also, we intend the system to work decentralized, as routing in mesh networks is usually organized in a distributed manner. Therefore, one instance of the system is required to run on each network node. Figure 1 shows one instance. Both the wireless network interface card (NIC) and a separate spectrum analyzer serve as data sources. For each received frame, we extract and store the 802.11 frame type, source address and duration1 . Additionally, we extract the channel state information similar to [START_REF] Halperin | Predictable 802.11 packet delivery from wireless channel measurements[END_REF]. To detect interference and non-WLAN spectrum users, we use a simple spectrum analyzer (Ubiquiti AirView). It detects the signal energy across the entire 2.4 GHz ISM2 band with a bandwidth of 500 kHz. Existing solutions [START_REF] Rayanchu | Airshark: Detecting Non-WiFi RF Devices using Commodity WiFi Hardware[END_REF] show that this step may be done as well solely with a wireless NIC.

In the recorded data about interference and WLAN activity, we extract patterns and use them for prediction, resulting in a probabilistic estimation of the channel occupancy. In this step, we combine methods of time series analysis with machine learning methods such as Hidden Markov Models. Our goal is to combine information from both observations of spectrum use and knowledge of the user's activities. We classify activities into e.g. "lecture", "group meeting", and "empty room". Eventually, we can describe the channel occupancy rate such as shown in [START_REF] Oularbi | Physical layer IEEE 802.11 channel occupancy rate estimation[END_REF], [START_REF] Wellens | Lessons learned from an extensive spectrum occupancy measurement campaign and a stochastic duty cycle model[END_REF] and [START_REF] Geirhofer | Dynamic spectrum access in wlan channels: empirical model and its stochastic analysis[END_REF]. We use the current channel state information (CSI) to estimate the probability of a successful frame reception for each 802.11 data rate 3 . Since models for this purpose already exist, this step is not in our focus.

From the estimations of packet loss, channel availability and information about planned or ongoing activities for which the impact on the network is known, we can finally estimate the short-term network quality and supply this information to the strategy synthesis component. Moreover, we are able to provide information about the number and type of currently present wireless devices to the intention recognition component of the SE.

Next to the information exchange between a node and components of the SE there is an exchange among the nodes of the network. First, neighboring nodes can share their knowledge about current and past interference conditions and channel occupancy since we can assume that the conditions are similar for nodes spatially close to each other. Such an exchange is also helpful for new nodes joining the network in that they can benefit from the knowledge acquired by nodes which are already on-site. We have to develop a metric which allows us to decide whether knowledge from a neighboring node is applicable to another node. Secondly, each node can provide the results of the packet loss estimations to its direct neighbors in order to allow them to select an optimal 802.11 data rate for their transmissions. prediction of channel occupancy solely with time-series data is not sufficient, because it will not be accurate enough to predict overall network quality. Our approach is therefore to increase the accuracy of prediction by combining timeseries data with external information about user activities.

Figure 2a (green graph) shows the number of active WLAN devices nearby our network node, computed by observing WLAN channels 1-13 using a sequential pattern ("channel hopping"). We consider only data frames originating from a wireless station and compute the number of unique MAC addresses occurring within a 10-minute window from that. The high number of active devices observed can be explained by the fact that transmissions from adjacent offices and corridors, and a from small lecture room were also received by our test-bed node. It can be seen in the raw data that a high number of present WLAN devices at a particular point in time indicates a high channel occupancy at this time4 .

Conclusion and Outlook

In § 1 and § 2, we outlined the general problems with the use of wireless mesh networks as communication layer for smart office environments. Instead of reservation or prioritization, our goal was an estimation of network quality. Based on our findings we developed the system model described in § 3.

As a next step, we will develop the estimation models for channel occupancy and overall network quality and verify them in our test bed. In the final step, we will deploy the network nodes in the smart meeting room and evaluate the overall prediction accuracy in real-world use cases.

  The author is a PhD student funded by the German Research Foundation (DFG) as part of the research training group 1424 "Multimodal Smart Appliances for Mobile Applications" (MuSAMA). Postal address: Universität Rostock, Fakultät für Informatik und Elektrotechnik, Institut für Informatik, Lehrstuhl für Informations-und Kommunikationsdienste, D-18055 Rostock a flexible and robust communication layer which (I) does not depend on a central infrastructure, (II) supports device mobility within the network, (III) integrates new devices seamlessly, and (IV) allows the discovery of devices and services.

Fig. 1 .

 1 Fig. 1. Overview the designed system. One node of the mesh network is shown. The labels on the right side indicate information exchange with other nodes of the WMN and other components of the smart environment.

Computed from frame length, data rate and preamble type.

Industrial, Scientific and Medical

e.g. each combination of modulation, forward error correction and antenna configuration

Please note that in Fig.2athe channel occupancy is only computed for channel 1, while the number of active clients is computed for channels 1-13.

Intermediate Results

Based on a commercial router platform, Ubiquiti RouterStation Pro, we built a test bed with ten prototypic network nodes and deployed them in a typical office environment at our university department building. We conducted long-term experiments in this test bed to explore patterns in channel occupancy, network usage, and interference. We also assessed the impact of multipath propagation on current wireless consumer hardware in a typical office environment.

In Fig. 2a we show some measurements from the test bed about channel occupancy of WLAN channels in the 2.4 GHz ISM band. We took data collected from one of our network nodes which is located in a lab room at the department. The room is occasionally used for meetings as well. The black graph shows the channel occupancy of a single WLAN channel on 28 consecutive days in January 2012. We computed the channel occupancy by taking the samples collected with the spectrum analyzer. We observed a span of 20 MHz around 2.412 GHz (channel 1), which is the channel used by most clients in this room. We applied a threshold of γ = -96 dBm to distinguish between "idle" and "occupied" channel states and finally computed the average occupancy in 60 s windows. For Fig. 2b we took the time series data from 2a and computed the autocorrelation function (ACF) with a lag of up to 192 h (8 days).

It can be seen that the channel occupancy is very low during the night (ca. 5 %, mainly caused by beacon frames) and moderate to high during the working hours. It can also be seen that different days show different patterns of usage. The ACF shows that there is a periodicity of 24 h, but the low values imply that a prediction of consecutive days and even of consecutive weeks is not promising. We found similar results also for other network nodes in our test bed. These nodes are placed in lecture halls, labs, and meeting rooms. We conclude therefore, that


C Ponsard

SPATIAL FUZZY CONSUMER' S BEHAVIOR A multidimensional Analysis

This paper is devoted to a multidimensional analysis of the consumer's behavior when the decisionmaker is acting in a fuzzy space and pointing out an imprecise attitude.

At first, the process of decisionmaking is described with the help of three relationships between the set of goods which are supplied in seve ral points, the set of their characteristics and the set of consumer's a priori possible behaviors. All these relations are fuzzy. The model applies the theory of fuzzy relations equations.

Then, the stages of the decision process are analyzed. Often fuzzy com portemental relations are like "black boxes". The mathematical solution of the model indicates in which conditions their valuations are possi ble.

The main interest of this method is to do without additive operations on subjective items and to use operators which are coherent with the fuzzy nature of the variables.

Introduction.

In Operational Research, especially in marketing and advertising stu dies, searchers have often to solve the following problem : what will be the behavior of a group of individuals in presence of a lot of consump tion goods which are supplied in some scattered supply points and have numerous and various characteristics ?

The process of decisionmaking to be analyzed lays on subjective and qua litative relationships : some relations express the perception of real or fancied characteristics which are associated with goods and spatial structures of markets ; other relations formulate the consumers' atti tude with respect to these characteristics ; at last, other relations express the revealed behaviors as to the goods such as they have been appreciated and valued.

The aim of this paper is to present a model which fully takes into account the subjective and qualitative nature of the relationships bet ween man, space and goods. This model applies the theory of fuzzy rela tions equations. Initially, this theory was formulated by [START_REF] Sanchez | Equations de relations floues[END_REF]1976). Then it was set out and developed by several authors (see especially [START_REF] Kaufmann | Introduction à la théorie des sous-ensembles flous[END_REF][START_REF] Prevot | Sous-ensembles flous -Une approche théorique[END_REF]1981 ;Viganza 1982 ;[START_REF] Pedrycz | Fuzzy Relational Equations with Generalized Con nectives and their Applications[END_REF]). Recently Zu-Wei (1980) introduced the necessary and suf ficient conditions for the existence of solutions of fuzzy equations, without developing the proofs. They will be supplied in the Appendix next to this paper.

The following model is different, but complementary, of neoclassical fuzzy spatial models. In these ones, relationships between man, space and goods are expressed with fuzzy preferences relations which allow, under certain conditions, to define fuzzy utility functions [START_REF] Ponsard C | On the Imprecision of Consumer's Spatial Prefe rences[END_REF]1981 a). In this framework, consumer's partial equilibrium is the result of a fuzzy economic calculation : to maximize the fuzzy uti lity function with an elastic ressources constraint (Ponsard 1981 b).

The same solution is available for the producer's equilibrium analysis, by means of suitable adaptations (Ponsard 1982 a). At last, in the par ticular case where the objective is precise and the constraint alone is fuzzy, the economic calculation is technically simpler (Ponsard 1982 b). Now the aim of the present approach is to apply a multidimensional ana lysis to the exploration of the consumer's decisionmaking mechanism in a fuzzy context. At first, the complete decisionmaking process is des cribed and formalized. Then, its different steps are analyzed in de tails. The conditions, which must be verified in order that the rela tions specifying each phasis of the process be compatible with each other, are proved. They express the economic conditions for the fuzzy behavior coherence.

Remark. In order to avoid any ambiguity in the notation of mathematical terms, ordinary (non fuzzy) concepts are underlined, whereas fuzzy con cepts are not.

The decisionmaking process.

The economic decisionmaker is an individual consumer or an homogeneous group of consumers. Its residential location is given. It enables to set out the delivered price system for the consumer. But consumption can take place either at the consumer's residence or at any other point. In this last case, the consumer's travelling expenses are incorporated in the delivered price. I, t], be a set of t spots indexed s where the goods are supplied.

In order to express that a good can be supplied at several spots and a spot can supply several goods, we define a mapping, denoted by f, from P x S into rN+ such that : C1,r] be a set of r goods indexed p, and Thus, we define the set of located goods :

ii x L = -with A = { xi ) > i ^ I_.
Example. The above mentioned formulation is complicated but it expresses a very simple relationship. It enables to indicate the nature of a given good and its supply spot with the help of one index only so that the symbols below are made easier.

Let four goods and three supply spots. Therefore = 3. We have (See Table 1).

Next, will be written in the form of a vector.

The located goods have numerous intrinsic characteristics. Also, a given good has many characteristics according to its supply spot. indexed k. For example, k = 1 means the aptitude of a located good to satisfy a given need ; k = 2 designates the value which is associated with the state of contentment furnished by a consumption ; k = 3 indica tes the delivered price level such as the consumer appreciates it ; k = 4 means the quality imputed to a located good ; k = 5 designates the accessibility of goods depending on their supply spots location ; and so on.

possible behaviors that the consumer can have regarding the located goods and their characteristics. This set is not reduced to the purcha sing behavior alone ; it includes all the elements which characterize the spatial consumption behavior. For example, j = 1 designates the in tention of purchasing some quantities of goods at some supply spots ; j = 2 means the attachment to a trademark ; j = 3 indicates the propen sity to imitate other consumers' behavior ; j = 4 designates the prefe rence for a given supply spot ; and so on.

Let

At last, , with j € _J, = [1,n], the set of n a priori 4bis Table 1 g1

(1,1) (1,2) (1,3) X1 X2 X3 (2,1) (2,2) (2,3) X4 X5 X6 g3 (3,1) (3,2) (3,3) ... / X7 X8 X9 g4 (4,1) (4,2) (4,3) X10 X11 X12 G x L X
The relationships between the sets X, X anc* -are iike "black boxes", in the sense that they are very imprecise. First, the consumer has only exceptionally a complete information relating to his environment. Gene rally, he knows imperfectly the space where he lives. Then, man is not a robot and the consumer has not a perfect aptitude to discriminate bet ween goods and supply spots. He does not necessarily associate an exact valuation to a given characteristic. He does not always know if a good supplied at a given spot has a wanted characteristic. Accordingly, the decisionmaking is subject to a weakened rationality.

Therefore, to consider the relationships between X.» X anc^ -as fuzzY bi nary relations and to analyze them with the help of fuzzy relations equations theory is pertinent.

The decisionmaking process includes three stages : treatment of informa tion by the consumer, valuation of characteristics and revealed beha vior.

Treatment of information.

At first, a good x^ has more or less a given characteristic depending on the consumer's appreciation and/or on the supply spot.

This treatment of data is dependent on the perception and the apprehen sion of the available information relating to spatial environment and real or fancied characteristics of goods. It also depends on learning by doing phenomenon.

It means that x^ is set in correspondence with y^ at a given degree, de noted by y (x^, y^). We put that y (x^, y^) €[0,1]. Thus, a fuzzy bina ry relation, denoted by A, between the elements of and X is defined.

Relation A is a fuzzy subset of X x Y such that :
To simplify, we put : y^ (x^, y^) = a ^. 2).

Then, B o A = C gives, by application of the max-min composite relation formula : (see Table 3). The solution of the first problem will be explained thoroughly. The so lution of the second question will be given without proof because it follows the same arguments. Moreover, in practice, relation B is the (

1) V a.. > V c . • , V k 6 K , M j 6 J , V i £ l k 1 j J i.e./] T = ( k 6 H I aik > Y cij \ * 0 » y 1 6 I J (2) V U (b a c )\ » V Cii , V i £ 1 , y p €1. , V j € J. k€ T v PJ / j J
where A' designates the transpose of A and a an operator such that c = a a b

with c = 1 if a 4 b c = b if a > b.
The proof is tedious. It is stated in the Appendix (see Definition (1)

and Theorem (3)).

The theorem demonstrates the existence of solutions, but not its unique ness. In the Appendix, we shall prove that the above solution B is the greatest element in the set of possible solutions, i.e. the solution which overranks all the others. The non-uniqueness of the solution may appear as a deceptive result, but we must recall that the problem is put in a fuzzy context (for a complete mathematical statement, see Appendix, Theorems (1) to ( 5)).

Illustration (II).

We consider again illustration (I). Now A and C are given. We would com pute B.

First we verify if conditions (1) and (2) of the above theorem are sa tisfied. 4)

Matrix B of illustration (I) is found again.

Particular case.

The solution of the preceding problem can be improved in the particular case where matrix A contains one and only one element for a row which is equal to 1, all the others being null. This formulation fits the hypo thesis in which the consumer, during the phasis of information treat ment, bounds his appreciation to a single characteristic of the located goods, for example the delivered price, and does not take into conside ration the others. Or, it expresses that the consumer's data treatment is such that the most appreciated characteristic alone is chosen, all the others being neglected, in the valuation of each located good.

In such a context, the set of solutions B of equation B ° A = C has the structure of a complete lattice. In other words, there exist a greatest and a smallest element which bound the set of solutions. Indeed, we prove that the greatest element, denoted by B, is equal to A' @ C, as A in the general case ; the smallest element, denoted by B, is equal to A'

C where the toplined terms designate the pseudocomplements and A 1 the transpose of matrix A (see Appendix, Definitions (2) and ( 3) and Theorems ( 6) and ( 7)).

Illustration (III).

We consider again illustration (I). Now the matrix A is such that the maximal elements of each row are equal to 1, all the others being null.

Matrix B is kept.

We have : (see Table 5)

Like in illustration (II), we verify that the necessary and sufficient conditions of a solution B of equation B o A = C are fulfilled.

We have :

(1) Maximal solution : B = A' (a) C.

(see Table 6)

(2) Minimal solution : B = A' (a) C. (see Table 7)

(3) In the two cases, we verify that matrix C is found again. (

2) k'sT (p (bKp ° W j > ï cij -« J « J -» p e J , w i e i-

where C' designates the transpose of C and (B (a) C 1)' the transpose of (B © C ' ) .

From this result, the analysis is analogous to the study which was sta ted for the valuation of the characteristics in the general case.

Illustration (IV).

Let the following equation :

(see Table 8)

After conditions (1) and (2) of the theorem have been verified, we have (see Table 9)

Conclusion.

The consumer does not always know what he wants exactly. The fuzziness which distinguishes his behavior may foil empirical policies, for exam ple marketing programming, advertising campaign or shops location choi ces. Also applied economics needs a theoretical model likely to forma lize the fuzziness of behaviors and to analyse their effects. The par ticular case where behavior is not fuzzy is not opposite : it is simply an extremal case where membership functions are Boolean.

The conditions for the existence of solutions of composite fuzzy rela tions equations have a manifest economic significance. They express the conditions which must be fulfilled in order that behaviors reveal at least a weakened coherence. When they are not verified, the observed behaviors are incoherent and the model permits to know where the causes of this inconsistency are situated.

At last, the above model should be still more thoroughly examined. In the general case, the set of solutions has the structure of a sup-semilattice. The minimal solutions bounding inferiorly the set of solutions will require to be studied. We note : B = A. Clearly, A can be the pseudocomplement of A itself. We write then :

y x G E : (x) = 1 -yA (x).
Remark. These two definitions must be carefully distinguished. In defi nition (1), J_ is endowed with the properties of a Brouwerian lattice, while in definition (2) L_ is viewed as a membership set.

Theorem (1). Let A c x and C c X_ x 1_ . We have : (2) must be fulfilled in order that this equality be true.

We have :

  ,s) = i, i G I_, fN+ with i = (p -1 )_S + 1, pS> 11 p E P where _S = Card S_ We put f (r,t) = m. Thus _I = [1,m].

6 •

 6 Figure1

3 .

 3 Analysis of the decisionmaking process stages. Now two interesting problems can be studied : in which conditions does equation B o A = C admit a solution B and a solution A ? In other words, is it possible to make explicit the valuation of characteristics if A and C are known ? In the same manner, is it possible to make explicit the step of information treatment if B and C are known ?

7 0. 5 ,

 5 C c X. x 1 most difficult for empirical observation. Solution B of equation B o A = C. General case. The necessary and sufficient conditions for the existence of solutions B of equation B o A = C are set out by the following theorem. Theorem. Equation B o A = C has a solution B = A' (S) C if and only if :

  with T = {k € K I sik >/ y Cjj ] For i = 1, we have : T* = £ 2 j For i = 2, 3, 4, we have : T 1 = {l ^.We have :T = {2 } : (0.7 a 0.4) a (0.3 a 0.5) a (0.5 a 0.5) a (0.6 a 0.5) = 0.4 T = [1 J : (0.1 a 0.2) a (0.8 a 0.7) a (0.6 a 0.6) a ( 1 a 0.7) = 0.7 Condition (2) is fulfilled for any i. Solution B = A' (a) C. (see Table

  It suffi ces to compute (A o Ü) and (A o B) respectively. Solution A of equation B o A = C . Now, if the phasis of data treatment is unknown, the equation must be solved into A, relations B and C being given. Theorem : Equation B o A = C has a solution A = (B (a)C')' if and only if (1> k bkj > Ï cij . w i e i , w j £ j , w k e K. i . e . O = t , T =[k<= K I bkj> y C i , j / 0 WjSJ U b i s

  : A Brouwer's lattice is a lattice, denoted by J-, in which for any couple of given elements a and b the set of all elements x, x G J_, such that a a x b contains a greatest element, [0,1] and if a, b G L^, then : a a b = 1 ifa^b a a b : b if a > b The operator © is neither commutative nor associative. The relative pseudocomplement of a in b is unique. Definition (2) : Let E be a set and L_ = [0,1] the set in which the ele ments of the subsets of have their values. Let A and B be two fuzzy subsets of £. By definition, B is the pseudo complement of A if : V x G E : pB (x) = 1 -(x).

(

  A' (a) C) o A c C where A' is the transpose of the relation A. Proof. We put W = (A1 (a) C) o A We have : yw (x,z) = V ^A (x,y) A V a c (y,z)) by definition of the operation o (max-min composite fuzzy relation). Let still : yw (x,z) = y (x(yA (x,y)' yA (x,y) 0 1 yc(x'z))j = y ( V x,y) A (yA (x,y) a y c ( x ' z) y) a Uc (t,z)fj By definition of the operation a, we have : yw (x,z) * y^(yA (x,y) A (V X,y)a Uc (x' z)) yw (x,z) y (x,z). [Q.E.D.] Corollary. If B = A 1 (a) C is the solution of the equation B o A = C, then (A' @ C) o A = C. similar to that of theorem (1). Theorem (3). The equation B o A = C has a solution B = A' (a) C if and only if : (1) k aik > y cij . v k e k , \/ j . i.e.^-T = ^k G K. | ai(< >/ ^ c " j i 0 , conditions. In virtue of the corollary of theorem (1), if B = A 1 (a) C is the solution of the equation B o A = C, the equality (A1 (a) C) o A = C is verified. We must prove that the conditions (1) and

B

  " A = (A' © C) . A = J v ^a,k * ( a (akp o. cp .))J = ilf Ca-kA <vi ° v > < v ......... <\ " c > ) because a, . = a.. ki ik . I a .. a c . . a k I ik ij [a (a. a c .))] Ip kp PJ // because a A ( aab)=aA b = [ ( k a ik) A C ij A ( k f p A ( a k p 0,cpj)|] If condition (1) is not verified, i.e. if 3 i G I / /a.. < V c. . , \t k G K , \j j G J, there is no solution, k ik j ij -J Indeed, let . c . . = c . " v ... v c . . v... v c . = M J ij i1 ij m We have : if a.. a c. . a ( Y / A (a a c .)k aik)A (k(pA ( \ p a c Pj ^ k S k < c ij Consequently : B 0 A = (A1 @ C)c A / C. Condition (1) is necessary. If condition (2) is not fulfilled, i.e. if 3 i ej. /k ^ (akp a cp J ))< y Cij ,«P6I, t f j 6 J , » i S I there is no solution. a (a, a c .)] P kp PJ 1 B o A = (A' a C) o A = ^ |a.k a ^, ; [{k e ï (aik A (j <akp a cPj I ] v (uVei-T ( aik Afi(\p a cpj^)where1 -T = G _K | a ^ < V Cij^ > ^ ^ I But' k exfik A (j (akp " "pj')) = = k € T (aik A (ak1 ° V A---A <aki " ^ A---A <akm ° c, j ) = k € 7 (aik A (aik " cij> A (? (V cpj^) because a.. = a. . lk ki = k ï r ( ai k A c i j A (î ' V ^p j ' ) ) = (k 6 * aik) A cij A (k 6 % (È (akp " ^j 1)) >/ V c . . = c." v...v c . . v...v c . ; (k 6 T aik)A cij A (k I 7 (A (\ p 01 "pj»)) = = °ij A (k €T (p (akp " cp j >)) »j£J,#i6I,#p6I = M A il C m Í A ( a i a C •)) I g VT (aik * ( a ^ a cpJ)))In the same manner, we have : k€ I-T (aik A (è <akp a cpj>)) = ( k S j -T aik)A cij A fél-T (p (akp " V ) )We have :a..< ^c . . , V k £ I -T , If i 6 I , V i c . . , t f j £ J , n £ _ Ik Ê I -T aik < Ci1 V -'-V cij V *--V cin We have : k ^ < c ^ , tf i G I, V j € J ™ US ' (k e J.-T ' ik)* cij (k G I_-T (p (akp a cpj))j ^ k G 1 / T aik < W i G I , V p 6 I , tf j G J . Consequently : B 0 A = ( A'(a) C) A £ C. Condition (2) is necessary.Sufficient conditions. We suppose that conditions (1) and (2) are ful filled. We have : = [ k ( aik ''(P M \ P % j > ) j (k€T (aik A (p (akp " c p j ' )/} V [ k 6I-T(aikA (p(akp " c pj'»))) y k G J< , M i GI_, \j j 6 J , y p G_I_ But> k e T ^' l i ^k p ^p j 1)) = k 6 T (aik A<ak1 ''•••A ( a ki 01 "ij' (akm a cmn^j = k £ T (aik A (aik " cij)A (pA (akp ° cpj>)) B o A = (A-a C) o A = because a.. = a. . lk ki : i/cm ia ii, A c -• A /A (a, a c .)')) k G T ^ ik ij ^p kp pj'IJ because aA(aab)=aAb k€T aikj A Cij A ^kG T ( p ^3kp a Cp j ^) By condition (1): V * a . . >/ V c . . ,Vk6T,tfiEI, WjGJ 1 .V c . . V . . .V c. ' l1 IJ in , c i A (ai a c .)) >/ c.. , V i G I, Wp 6 I, y j 6 o A = (A1 (a) C)c>A = = Conditions (1) and (2) are sufficient [Q.E.D.]

Table 4

 4

						Z1	Z2
	X1	X2	X3	X4	X1	0.2	0.4	Z1	*2
	0.1	0.8	0.6	1	X2	0.7	0.5
				a
	0.7	0.3	0.5	0.6	X3	0.6	0.5
	0.3	0.6	0.4	0.3	x4	0.7	0.5

Table 5

 5

	y1	*2	y3

ACKNOWLEDGEMENTS 13

The author would like to thank Mr. Prevot, associated with the Institute of Economic Mathematics, for fruitfull discussions he had with him and Mrs Penez for her assistance in translating this paper into English.

The proof is similar to that of theorem [START_REF] Martin | Contribution à l'étude du comportement de consomma tion[END_REF].

Remark. The forms of theorems ( 3) and ( 4) are slightly different from Zu-Wei's formulations (1980) in which a third condition is put. In fact, the proofs can be derived from more concise statements.

Theorem [START_REF] Ponsard C | On the Imprecision of Consumer's Spatial Prefe rences[END_REF]. Let S(B) be the set of fuzzy relations such that B o A = C.

Then (A' © C) is the greatest element in S(B). (2) V y / y , y G V : y^ (x, y) = 0.

Therefore this relation is not fuzzy. The expression "elementary rowed relation" simply means "a single element for each row equal to 1, all the others being equal to zero". Each row is an elementary vector.

Theorem [START_REF] Ponsard C | An Application of Fuzzy Subsets Theory to the Analysis of the Consumer's Spatial Preferences[END_REF]. Let A c X x V an elementary rowed relation and B e y x Z a fuzzy relation. We have :

By definition : y^-\ (x, z) = y (x, z) = 1 -y (x, z).

DO H C C

In virtue of De Morgan theorems, we have : (1) Let B^ G S(B) and B^ G S(B). It is easy to prove that the properties of a lattice are verified. Indeed, it suffices to point out that B^ and B2 fulfill the following properties : commutativity, associativity, idempotence, and absorption. These properties are dual for the fuzzy union and the fuzzy intersection.

(2) B = A_' (a) C by virtue of theorem [START_REF] Ponsard C | On the Imprecision of Consumer's Spatial Prefe rences[END_REF].