Daniel Willkomm
email: willkomm@tkn.tu-berlin.de

Sridhar Machiraju
email: machiraju@acm.org

Jean Bolot

Adam Wolisz
email: wolisz@ieee.org

The Problem of Sensing Unused Cellular Spectrum

Keywords: Cognitive radio, spectrum sensing, dynamic spectrum access

Sensing mechanisms that estimate the occupancy of wireless spectrum are crucial to the success of approaches based on Dynamic Spectrum Access. In this paper, we present key insights into this problem by empirically investigating the design of sensing mechanisms applied to check the availability of excess capacity in CDMA voice networks. We focus on power-based sensing mechanisms since they are arguably the easiest and the most cost-effective. Our insights are developed using a unique dataset consisting of sensed power measurements in the band of a CDMA network operator as well as "ground-truth" information about primary users based on operator data. We find that although power at a single sensor is too noisy to help us accurately estimate unused capacity, there are well-defined signatures of call arrival and termination events. Using these signatures, we show that we can derive lower bound estimates of unused capacity that are both useful (non-zero) and conservative (never exceed the true value). We also use a combination of measurement data and analysis to deduce that multiple sensors are likely to be quite effective in eliminating the inaccuracies of single-sensor estimates.

Introduction

Dynamic Spectrum Access (DSA) is often viewed as a remedy against the spectrum scarcity caused by existing static spectrum allocation schemes. In DSAbased approaches primary users, who are often the licensed users of spectrum, have strictly higher priority than secondary users, who must vacate spectrum if and when it is needed by primary users.

A fundamental problem in DSA is: how can secondary users know whether or not primary users are using spectrum? This problem has been studied most frequently in the case of secondary usage of spectrum licensed to TV broadcasters [START_REF] Kim | In-band Spectrum Sensing in Cognitive Radio Networks: Energy Detection or Feature Detection?[END_REF]. For TV bands as well as other usage scenarios, secondary users need to reach a binary decision, namely, whether a primary user is present or not. In this paper, we address spectrum licensed to another set of primary users -cellular telephony operators. Our focus on cellular bands is justified given the significant recent interest in implementing DSA in these bands [START_REF] Daoud | Secondary pricing of spectrum in cellular CDMA networks[END_REF][START_REF] Alyfantis | Non-cooperative dynamic spectrum access for cdma networks[END_REF][START_REF] Buddhikot | Spectrum management in coordinated dynamic spectrum access based cellular networks[END_REF][START_REF] Chen | Mining spectrum usage data: a large-scale spectrum measurement study[END_REF][START_REF] Hamouda | Dynamic spectrum access in heterogeneous networks: Hsdpa and wimax[END_REF]. Such interest is fueled by the large number of devices and networks using cellular bands. In addition, as VoIP services and wireless data networks proliferate, cellular voice bands may see reduced loads. Secondary usage of such spectrum is an attractive way by which providers can extract value. We study CDMA cellular bands since they are one of the most widely-used cellular technologies (along with GSM) and we had access to the ground truth of such a network.

Since CDMA voice users share spectrum, the goal is not to detect whether a user is present or not but to identify the amount of unused spectrum capacity. Of course, even if there is unused spectrum capacity, secondary usage can have an impact on primary users. Hence, it is acceptable, perhaps even desirable, that some amount of spectrum is left un-utilized by secondary users. Thus, if secondary users want to use capacity X, we would like to check the availability of capacity Y > X + ∆ beyond what is already used by primary users. Though understanding it is outside the scope of this paper, we do believe that -at the least -low-bandwidth applications (e.g., urban sensing) may be well placed to exploit unused capacity in CDMA voice networks.

In this paper, we investigate how secondary users can estimate unused spectrum capacity by utilizing sensing mechanisms. In particular, we focus on what are arguably the simplest sensing mechanisms -those that are based on single sensors considering power alone. Not only are these mechanisms simple but they are also cheap (thus enabling large-scale secondary user deployment). We phrase our investigation in terms of the following problem: What information about primary user occupancy do spectrum measurements of power yield? Can this information be used to estimate the unused capacity that secondary users can exploit?

To conduct our investigation, we leverage a large and unique dataset containing both spectrum measurements of transmitted power as well as the corresponding "ground truth", i.e., the exact information about all the calls in progress at every point in time obtained from the call records collected at the network switches. In other words, we capture both the actual behavior of the primary users (calls in progress, which can only be measured inside the network) as well as the estimated behavior of the primary users, as would be measured by secondary sensing users. To our knowledge, this is the first study to execute and evaluate such synchronized measurements of sensing and ground-truth. Throughout this paper, we use the natural approach of estimating unused capacity by first estimating primary usage and subtracting it from the total capacity.

We start by exploring if sensed power can be easily converted to the amount of primary usage. We find that this way of estimating primary usage is not practical. Therefore, we focus on investigating other, indirect ways of estimating unused capacity. In particular, we explore the possibility of identifying primary usage events (call arrivals or terminations). Using statistics of call durations that are published or well-known [START_REF] Guo | Estimate the call duration distribution parameters in GSM system based on k-l divergence method[END_REF][START_REF] Willkomm | Primary Users in Cellular Networks: A Large-scale Measurement Study[END_REF], we can then convert the estimated intensity of event arrivals into estimates of primary usage. It turns out that sensed power, when averaged over time, contains distinct, well-defined power signatures corresponding to call arrival events and, to a lesser extent, call termination events. However, the noise in sensed power at any single time instant is large enough that we cannot exploit these signatures to accurately identify individual call events. We conclude that accurate estimation of primary usage (and hence unused capacity) using a single sensor is likely to be unachievable.

Power sensed by a single sensor can nevertheless be of value to secondary users since it can provide estimates of unused capacity that are conservative (underestimates) yet useful (not equal to zero). We show that a single sensor can provide such useful underestimates because of the following reason: even though our event identification algorithms are hampered by noise, they can be suitably configured so that they never overestimate unused capacity but still yield useful estimates of unused capacity. For example, in the moderately-loaded cells that we monitored in our experiments, we can correctly estimate that at least 5% of total capacity is almost always available for secondary use without ever overestimating unused capacity. Thus, we can use power measurements from a single sensor to at least support a low-bandwidth secondary application.

Finally, we show how accurate estimates of unused capacity can be obtained by using multiple sensors. Using our measurement-based characterization, we estimate the number of sensors required to achieve better accuracy.

Measurement Methodology

To evaluate if sensed power yields information about the underlying primary usage, we conducted a large number of sensing measurements spread over time and multiple locations. In addition, we simultaneously collected detailed information about primary usage. Thus, we were able to collect a large amount of unique data consisting of both measurements and ground truth. Our measurements were collected in the band used by a CDMA-based cellular operator, which is an important target for dynamic spectrum access as described in the introduction. In total, our experiments yielded approximately 90 GB of ground truth data on primary usage and 14 GB of data with spectrum power measurements. In this section, we describe our measurement methodology in detail and also the salient aspects of the collected datasets.

Ground Truth on Primary Usage

To compute the ground-truth, we use call records collected at the switches of a CDMA-based cellular operator. These records capture the start time, duration, initial and final sector as well as assigned carrier5 of the voice calls made in the network. The call duration reflects the RF emission time of the call and captures precisely what we want -the duration of primary usage. All timestamps were measured with a resolution of a few milliseconds.

Using the call records, we calculate the ground-truth usage in each carrier of a cell sector. We split the call records based on the sector and carrier. We create two records for each call corresponding to its initiation and termination. Then, we sort these records in order of their time to get a sequence of call events that are known to have occurred in each sector/carrier. Using the sorted list of events, we also calculate the load of each sector and carrier. We do so by maintaining a running count of the number of ongoing calls. This count is increased by +1 when a call begins and decreased by -1 when a call terminates.

Since the switches only record the initial and final sector of each call, we are unable to account for the spectrum usage in other sectors that the user may have visited in between. This implies that our list of events is accurate but not necessarily complete (it may not count call initiation and termination events caused by handover). Similarly, for calculating load, we assign the whole call to the initial sector/carrier. We also try other approximations of load by, for example, assigning the first half of the call to the initial sector/carrier and the last half to the final sector/carrier. Since these approximations do not alter our results significantly, we do not provide them. Furthermore, we believe that full mobility information is unlikely to change our results either.

Power Sensing

We collected our power measurements using a W1314A Multi-band Wireless Measurement Receiver from Agilent [START_REF]W1314a datasheet[END_REF]. We used the Model 110 so that we can sense the uplink and downlink CDMA bands (in the 1900 MHz frequency range) used by the network whose call records we had access to. This receiver captured in real-time power measurements from all 12 1.25 MHz carriers belonging to a single provider. The power measurements were reported twice or thrice a second on average. Unless stated otherwise, we convert this raw data into per-second averages (computed using 2 or 3 readings). Our wireless measurement receiver is a sophisticated piece of equipment and can be viewed as being capable of the most accurate power based sensing that a secondary user can perform.

We collected multiple datasets at four different urban locations (L1 to L4). For each of the locations the power measurements were collected over multiple days and spanned all possible 1.25 MHz carriers of the CDMA band. We use C1, C2, . . . to refer to the various carriers. L1 was within line-of-sight and about 0.5 miles from the nearest base station. L2 was at a similar distance but not with line-of-sight of the closest base station. In both L1 and L2 the antenna was placed close to a window at the second floor. L3 and L4 were about twice the distance (1 mile) to the closest base station, on the ground floor and heavily shadowed from the closest base station.

Our analysis showed the following trends: datasets collected at the same location (at different times) showed similar results. Furthermore, the datasets collected at locations L1 and L2 illustrated better results than those collected at locations L3 and L4. This was due to the heavy shadowing at the latter locations. On account of this and space limitations, we provide results only for L1 and L2 in this paper. In particular, we use two datasets, which we label D1 and D2. D1 was collected over a period of 3 days at location L1 and D2 was collected over a period of 4 days at location L2. In this paper, we present results for two carriers C1 and C2, which were the most active carriers in the two locations.

For each experiment, we also recorded the identities of the cell sectors with the strongest pilots. For each dataset, we refer to the cell sectors as S1, S2, . . . in decreasing order of pilot strength. We observe that, for both of our datasets, this order reflected the distance of the sectors from the measurement locations. Usually a cell sector has activity in more than one carrier. We denote this by referring to the activity of sector 1 in carrier 1 with S1.1, in carrier 2 with S1.2, etc. Note that, for each of these cell sectors, we computed ground-truth (events and load) using the call records as described in Sect. 2.1.

Estimation via Power Thresholds

In this section, we present how well power is correlated with primary usage. We obtain these results by investigating the following question: Can a simple scheme based on mapping sensed power information to load information work? We start with some preliminary observations and data analysis for synchronizing the power measurements and ground truth.

Power-Load Correlation

In Fig. 1, we plot the power sensed and network ground truth for dataset D1 (downlink). We plot results for the two strongest sectors S1 and S2 and two carriers C1 and C2 used by both sectors. For data confidentiality reasons, we normalize the load values by a randomly chosen number so that the absolute load is obfuscated while preserving the trends. Notice that the day/night variations of the load are clearly visible. This is not surprising since it corresponds to levels of human activity and has also been observed in prior work [START_REF] Kamakaris | A case for coordinated dynamic spectrum access in cellular networks[END_REF][START_REF] Willkomm | Primary Users in Cellular Networks: A Large-scale Measurement Study[END_REF]. The plots showing the sensed power also illustrate a distinct diurnal pattern with higher power levels during the day and lower levels at night. Cross-correlation is a simple and well-known metric that we can use to measure the extent to which power "tracks" load. We plot the cross-correlation between sensed power and load for several lags in Fig. 2. The maximum is not reached at lag 0 since the clocks used for collecting call records and power measurements are only synchronized to within a few seconds of each other. In addition, for each sector/carrier, we see peaks separated by roughly one day. These local maxima are caused by the underlying diurnal pattern of the load. Overall, it is clear that the sensed power is indeed well correlated with load.

It turns out that the cross-correlation curves for all sector/carriers reach a maximum at the same lag of 13 seconds as shown in Fig. 2. We observed maxima at a similar lag with dataset D2 as well. For the rest of this paper, we, thus, use the above lag to synchronize the power measurements and call records.

Naive Threshold-based Scheme

We start investigating if there is a unique mapping of power level to sector load with Fig. 3(a). We plot the distribution of the sensed power levels for various coarse-grained levels of load during peak hours of the day (12PM to 6PM). As expected, with increasing load, the power levels tend to increase. But, observe that for different values of load, the same power levels are often seen. Moreover, when the load is low, the power levels are more spread out. This indicates that it is challenging to distinguish small changes in load using static power alone.

Power levels are better able to separate the coarse-grained measures of load at night (12AM to 6AM) as shown in Fig. 3(b). Note that, since the load at night is never high, we only show two levels. These levels are relatively well separated: for example, the power level is below -70 dBm for 60% of the time when the load is low as opposed to 5% of the time we have medium load. Such power-based thresholds separating coarse-grained load levels such as low, medium and high are likely to depend on location. For example, in separate short experiments, we found that the average power levels close (about 100 m) to a base station were around -50 dBm. Though we did not find much variation at a given location within a few days, it is unclear how long thresholds at a location remain valid.

To summarize, load estimation based on power thresholds (that are gleaned on a per-location basis) can provide coarse-grained information about load especially at night. Though fine-grained information is difficult to extract, such coarse-grained information might be sufficient to decide whether or not to start secondary usage. The above threshold-based scheme is a black-box estimation of load in the sense that no information is required from the cellular operator.

Event Signatures

During our analysis, we found that sensed power contains information about the "first derivative", i.e., change of primary usage load. These changes are typically due to call initiation and termination in a CDMA voice network.

The sensed power in our datasets shows often jumps and drops when events occur. To understand if such event signatures exist and characterize them, we examine all initiation and termination events spread across multiple days in our datasets. Since the average power across these days may not be stationary we rely on what we refer to as t-average plots: we extract the power for a short time periods before and after events and average the sensed power across all initiation and termination events. This allows us to look at time-averaged characteristics of power when events occur even in the absence of stationarity -a key advantage.

In Fig. 4, we show t-average plots capturing the average behavior for 10 seconds before and after call initiation and termination events of dataset D1.

In this figure, we are considering only the downlink bands. We notice two key patterns for the events involving the strongest cell sector S1:

-On average, call initiation events are characterized by a spike that is about 0.3 -0.4 dBm followed by a general increase of power afterwards that is around 0.05 -0.1 dBm. This trend is clearly seen during the daytime and nighttime as well (not shown). We believe that this spike is easily explained by the CDMA downlink power control loop [START_REF] Vanghi | The cdma2000 System for Mobile Communications: 3G Wireless Evolution[END_REF]. This loop ensures that, when a call starts, the base station transmits with high power. The power level is then reduced to a minimal level while maintaining call quality using the rapid closed-loop power control of CDMA. The increase of 0.05-0.1 dBm reflects the increased power due to a new call, of course. -On average, call termination events are characterized by a dip of at least 0.05 -0.1 dBm (a bit higher during nighttime) immediately after the event. This reflects our intuition that the call termination corresponds to lesser power being emitted by the base station.

Thus, there exist well-defined power signatures for initiation and termination events in CDMA networks. Figure 4 also shows that there are no visible signatures corresponding to the events of the second strongest cell sector S2.

Recall from Sect. 2.2 that we collected a second dataset D2 from experiments conducted at another location. To verify that the event signatures persist across locations, we plot t-average plots for D2 in Fig. 5. The call initiation signature corresponding to events of the strongest sector S1 continues to be clearly seen for both carriers. As before, there is no signature corresponding to events of the second strongest sector S2. Surprisingly, the call termination signature for D2 is less clear. The location at which dataset D2 was collected had no line-of-sight to S1 or S2 which is the likely reason behind the weak termination signature.

We also use t-average plots (not shown due to lack of space) to investigate if such signatures are also present in the sensed power of uplink bands. We find no identifiable signatures corresponding to initiation or termination events for both S1 and S2. The absence of signatures in uplink power is not surprising given that the average power levels are about 25 -30 dBm lower than the downlink power measurements. Such lower power levels are likely due to the stricter power budget of end-user devices. Also, the sources of uplink power are end-user devices, which are spatially distributed. We expect to see signatures when such devices are nearby. To verify this hypothesis, we conducted "active" experiments by initiating phone calls using a mobile handset located our power sensor. When these calls were initiated, we did observe identifiable spikes in power similar to the downlink initiation signature. These experiments confirm that uplink sensing is of use only if the sensor is close to all end-user devices. Since this is physically impossible, we do not further investigate uplink sensing in this paper.

Event Detection

In the previous section, we found the presence of well-defined signatures corresponding to call initiation and termination events on the downlink CDMA channels. In this section, we show that such average-case signatures do, however, not translate into algorithms for accurate event detection.

Discriminators of Initiation Signature

The t-average plots discussed in the previous section indicate that call initiation can potentially be identified by detecting spikes in the sensed power. Referring to the t-average plots of Fig. 4, we see that there are roughly three time periods: during, before and after call initiation. The spike occurs during the call initiation and is significantly higher than the power before and after. We also expect the power after call initiation to be higher than before.

Based on the above discussion, we are motivated to consider three intuitive discriminators of initiation signatures. We use P (•) to denote the power (as a function of time) and T to represent the second when a call is initiated. We divide a contiguous period of time around T into three periods: the first period of call initiation consisting of a window of w seconds including and after T , a window of w -seconds prior to this period, and, a window of w + seconds after the call initiation period. We calculate the average power in each of these three periods and define the criteria for the 3 discriminators as follows:

1. The difference between the power in the call initiation period and the power in the period before call initiation is larger than a threshold τ 1 , i.e.,

P ([T, T + w -1]) -P ([T -w-, T -1]) ≥ τ1.
2. The difference between the power during the call initiation period and the power thereafter is larger than a threshold τ 2 .

P ([T, T + w -1]) -P ([T + w, T + w + w+ -1]) ≥ τ2.

3. The difference between the power after and before call initiation is larger than a threshold τ 3 .

P ([T + w, T + w + w+ -1]) -P ([T -w-, T -1]) ≥ τ3.
An advantage of using a window of several seconds in each period might be the potential reduction in the variance of the estimated power. At the same time, larger periods may be polluted by other call initiation and termination events.

To better understand the impact of the various parameters including the window sizes and thresholds, we rely on so-called cCDF (complementary CDF ) plots. Consider the first discriminator. Recall that it looks at the difference during and before call initiation and expects this difference to exceed a threshold when a call is initiated. A cCDF plot shows if this discriminator is justified by plotting the distribution of the difference for all T when a call was initiated, and, compares it with the distribution for all T when a call was not initiated. Since we are interested in the number of cases that the difference exceeds a threshold, we plot the cCDF (the CDF subtracted from 1) and experiment with several choices of w and w -(plots not shown due to lack of space). Fraction nInit q 0.5 init q 0.5 nInit q 0.2 init q 0.2 day 1 day 2 day 3 day 4 day 5 0 0.2 0.4 0.6 0.8 1 Time Fraction nInit q 0.5 init q 0.5 nInit q 0.2 init q 0.2 The higher we choose τ 1 to be, the fewer call initiation events satisfy the criterion. However, as we make τ 1 smaller, more seconds during which no call was initiated satisfy the criterion. The sweet spot appears to be at around 0.4 -0.5 dBm, below which the latter increase faster than the former. We also get marginally better results when we define the period during call initiation as consisting of exactly 1 second. Larger windows do not improve our results. It seems that the power during additional seconds is not as high as that of the first second. Hence, any potential variance reduction from the additional power measurements comes at the cost of eliminating the signature itself. The size w - of the period before call initiation impacts the results to a lesser extent, leading to marginally better results with a window of size 4.

Using the cCDF plots for the other two discriminators we find that they exhibit similar behavior, namely, smaller windows are better. 0.3 -0.5 dBm appears to be a good threshold value of τ 2 . However, the third criterion is not as useful since the difference in power before and after call initiation is not as clear.

The success of our criteria may vary with time which is explored in Fig. 6. We choose the thresholds corresponding to the 0.5 and 0.2 cCDF quantiles. We then apply the criteria with the respective thresholds on an hourly basis and plot the fraction of initiation events and "non-events" satisfying them in Fig. 6.

As expected, the fraction of initiation events satisfying each criterion does not vary significantly and stays around the quantile value (0.5 or 0.2) used to choose the thresholds. However, the fraction of "non-events" passing the criteria show a clear dip during night time for both thresholds. This implies significantly better performance during night time on account of lesser noise in power.

Initiation Detectors

We now investigate how the various discriminators and their criteria can be used for the best possible detection of initiation events. Due to lack of space, we do not focus on detecting call terminations since discriminators based on call termination events do not perform as well as those based on call initiation.

We quantify discriminator performance, by looking at the detection probability, i.e., the probability of detecting an initiation event given that a call was really initiated. In Fig. 7(a), we plot the detection probability when each of our three discriminators are used on dataset D1. For each detector, we vary the corresponding threshold from -1 to 2.5 dBm. As expected, the detection probability reduces with increasing thresholds. In Fig. 7(b), we show the probability of detecting a call initiation event, although no call was initiated.

Comparing Fig. 7(a) and Fig. 7(b) shows a common problem using energy detection: Choosing a threshold τ 1 that achieves a high detection probability results in many non-initiation events to be declared as initiation event and vice versa. E.g., using criterion 1, a threshold of τ 1 = 0 dBm results in detecting close to 75% of the initiation events, but also in mistakenly detecting about 50% of the non-events as initiations. In contrast, a threshold of τ 1 = 0.5 dBm detects only 10% of the non-events as initiations but fails to detect 70% of the initiations.

Estimating Unused Capacity

In this section, we discuss how we can use power sensed by a single sensor to derive useful estimates of unused capacity. Specifically, we find lower bounds for the unused capacity so that -at least -low-bandwidth applications can utilize it. Note that these estimates are useful because they are significantly greater than zero. We compute lower bounds using the call initiation detectors to estimate call arrival rates. We then estimate the load in the system using Little's law as

E[k] = λE[b] where E[b]
is the mean call duration and λ the estimated arrival rate. We do assume that we have partial information about the system being studied, namely, the average call durations. Such information can be obtained from previous studies [START_REF] Guo | Estimate the call duration distribution parameters in GSM system based on k-l divergence method[END_REF][START_REF] Willkomm | Primary Users in Cellular Networks: A Large-scale Measurement Study[END_REF] (since mean call durations are quite stable over time) or directly from providers. Since we use such information, we refer to it as a gray-box approach (in-between black-box and white-box approaches).

In Fig. 8 we show how well we can achieve our goal: finding unused spectrum to satisfy the secondaries bandwidth requirement. We show results for dataset D1 and criterion 1. We divide our dataset into hour-long time periods and calculate average values within these time periods. Remember, that it is crucial to never overestimate the unused capacity. Using the whole dataset, the maximum threshold would be τ ≤ 0.5 dBm resulting in X = 5% of capacity unused in more than half of the time periods (figure not shown). If we use different thresholds for daytime (9am to 10pm) time periods and nighttime (11pm to 8am) time periods, we can improve performance significantly. The maximum thresholds so that we never overestimate are τ ≤ 0.7 dBm and τ ≤ 0.5 dBm respectively. These are indicated by the solid black lines in Fig. 8. This figure also shows that, using the maximum daytime threshold (τ = 0.7 dBm), we correctly estimate 5% (50%) of total capacity is unused almost always (in 14% of the daytime time periods). For the maximum nighttime threshold (τ = 0.5 dBm) we correctly estimate that 50% (80%) of total capacity is unused in 75% (46%) of the nighttime hours.

For dataset D2, the results are similar though the maximum thresholds (so that we never overestimate) are closer to 1 dBm. These results show that power measurements at a single sensor can be quite useful especially for secondary applications such as urban sensing, which have low bandwidth demands but strict power constraints. Given the differences we observed between D1 and D2, local calibration might be necessary to choose the appropriate power thresholds.

Towards Spatial Diversity

An alternative approach is to improve the accuracy of event detection. Clearly, this is hard to achieve with a single sensor because the signatures of individual events are obfuscated by additive white noise, which makes accurate detection very hard especially in the low SNR regime [START_REF] Sahai | Fundamental design tradeoffs in cognitive radio systems[END_REF][START_REF] Tandra | Snr walls for signal detection[END_REF]. The natural way to improve event detection accuracy would be to use multiple sensors in spatially diverse locations so that we can eliminate the white noise. There are various proposals for cooperative spectrum sensing approaches in the literature, e.g., [START_REF] Mishra | Cooperative sensing among cognitive radios[END_REF][START_REF] Pham | Optimal cooperative spectrum sensing in cognitive sensor networks[END_REF][START_REF] Sun | Cooperative spectrum sensing for cognitive radios under bandwidth constraints[END_REF].

We now use our dataset to quantify the benefits of cooperative sensing. In particular, we consider the approach of soft decision combining as described in [START_REF] Mishra | Cooperative sensing among cognitive radios[END_REF] and make a natural assumption of zero-mean additive Gaussian noise with variance σ 2 . With k distributed (and independent) sensors, the white noise in the average sensed power can be approximated as a zero-mean normal variable N (0, σ 2 k ) with variance σ 2 k by the Central Limit Theorem. We calculate the quality of event detection under the above model: Assume that a call is initiated at time T and the first criterion of Sect. 5 with w = w -= 1. At time T , the criterion shows a power spike of about 0.4 dBm plus the difference between the white noise at T and T -1. Assuming that white noise at these time instants is independent, their difference is a zero-mean normal variable with variance 2σ 2 k . Hence, the criterion will have a false negative with probability P fn and false positive with probability P fp

P fn = P N 0, 2σ 2 k + 0.4 ≤ τ P fp = P N 0, 2σ 2 k ≥ τ ,
where τ is the decision threshold. Given a maximum tolerable false positive and false negative probability, we can solve the above to estimate the minimum number of sensors (k) required. For example, for P fn ≤ p and P fp ≤ n we get:

√ k ≥ max q 1-p √ 2σ τ 1 , q n √ 2σ τ 1 -0.4
Here, q y is the value at which the quantile of the standard normal distribution is y. We estimate σ using D1. Since we do not want to capture temporal mean variations, we remove the moving average of the previous 5 seconds for each power reading. This yields an estimate σ = 0.39 with which we can achieve less than 10% false negatives and false positives using k = 13 sensors and τ = 0.2 dBm. In the previous section, we saw that it may be desirable to have a much smaller fraction of false positives than false negatives. It turns out that we can achieve at most 1% false positives and 10% false negatives with k = 26 sensors and τ = 0.25 dBm. Deploying such numbers of sensors per cell could very well be economical, especially if existing consumer devices can be leveraged.

Related Work

In recent years, a lot of measurement studies [START_REF] Chiang | A quantitative analysis of spectral occupancy measurements for cognitive radio[END_REF][START_REF] Macdonald | A survey of spectrum occupancy in chicago[END_REF][START_REF] Mchenry | Chicago spectrum occupancy measurements & analysis and a long-term studies proposal[END_REF] have been carried out to show the under-utilization of the licensed spectrum. Though these studies show the abundance of temporally unused spectrum, they give little insight into the dynamic behavior of the licensed users legally operating in those bands.

The authors of [START_REF] Kamakaris | A case for coordinated dynamic spectrum access in cellular networks[END_REF] estimate the load in the New York cellular bands (CDMA as well as GSM) based on spectrum measurements. However, in addition to pure power measurements, the CDMA signals are demodulated to determine the number of active Walsh codes (i.e., the number of ongoing calls). To determine the number of calls in the GSM bands, image processing of the spectrogram snapshots is used. This is in contrast to our study, which is based on power measurements and uses minimal processing. In addition, to our best knowledge, there is no study which correlates spectrum measurements with the actual load as recorded by the system. Sensing for TV bands has been previously studied, for example in [START_REF] Kim | In-band Spectrum Sensing in Cognitive Radio Networks: Energy Detection or Feature Detection?[END_REF]. They found that energy detection with multiple sensors is often better than feature detection. However, their results are for the relatively static TV bands and not for cellular bands.

Conclusions

We used a unique set of simultaneous sensing and network measurements to study the problem of sensing-based estimation of unused capacity in cellular spectrum. When averaged over time, we found well-defined signatures of call initiation and termination events using the power at a single sensor. However, sensing noise makes it challenging to use these signatures to estimate unused capacity by identifying call events. We found that useful underestimates can nevertheless be computed especially for low-bandwidth secondary applications. Alternatively, we can obtain accurate estimates by using multiple sensors. To our knowledge, our work is the first detailed study of how well sensing works in CDMA networks, which are often viewed as candidates for DSA. In the future, we intend to design and evaluate better sensing algorithms including those based on multiple sensors.

Fig. 1 .

 1 Fig. 1. Dataset D1: (a) Sensed power over time for carriers C1 and C2. (b) Normalized load for strongest cell sector S1. (c) Normalized load for 2 nd strongest cell sector S2.

Fig. 2 .Fig. 3 .

 23 Fig. 2. Dataset D1: Crosscorrelation of sensed power and ground truth load.

Fig. 4 .

 4 Fig. 4. Dataset D1: 10-second t-average plots for (downlink) power for C1 (top) and C2 (bottom) during (a) Call initiation events, and, (b) Call termination events.

Fig. 5 .

 5 Fig. 5. Dataset D2: 10-second t-average plots for (downlink) power for C1 (top) and C2 (bottom) during (a) Call initiation events, and, (b) Call termination events.

Fig. 6 .

 6 Fig. 6. Dataset D1: Fraction of initiation events and non-events that satisfy the discriminators defined by (a) Criterion 1. (b) Criterion 2. (c) Criterion 3.

Fig. 7 .Fig. 8 .

 78 Fig. 7. Dataset D1: (a) Fraction of initiation events identified by the detectors (b) Fraction of non events declared as initiation events by the detectors based on the 3 criteria with varying threshold values.

⋆ The author was at Sprint when this work was done.

Each cell sector may be assigned one or more carriers -a 1.25 MHz portion of the spectrum. Each carrier is capable of supporting tens of calls.


Kamil Kołtyś

Krzysztof Pieńkosz

Eugeniusz Toczyłowski

A Flexible Auction Model for Virtual Private Networks

Keywords: auction model, virtual private network, bandwidth trading

We consider the resource allocation problem related to Virtual Private Networks (VPNs). VPN provides connections between geographically dispersed endpoints over a shared network. To realize VPN service, sufficient amount of bandwidth of network resources must be reserved for any traffic demand specified by a customer. We assume that there are many customers that want to purchase VPN services, and many network providers that offer their network resources for sale. We present a multicommodity auction model that enables the efficient management of the network resources in the market environment. On the other hand it is very convenient for the customers as it allows them to specify the bandwidth requirements concerning VPN in a very flexible way, including pipe and hose VPN representations. The proposed model has also many other valuable properties, such as individual rationality and budget balance. The auction model has a form of LP for which the computational efficiency can be improved by applying the column generation technique.

Introduction

Virtual Private Network (VPN) is a logical network that is established over a shared network in order to provide VPN users with service compared to dedicated private lines. A sufficient amount of bandwidth of a bundle of shared network resources must be reserved for VPN service to satisfy traffic demand pattern specified by customer. The basic way of representing the set of traffic demands values of VPN is in the form of the pipe model [START_REF] Duffield | A flexible model for resource management in virtual private networks[END_REF][START_REF] Kołtyś | A bandwidth auction model for purchasing VPN[END_REF]. It requires that VPN customer specifies, for each pair of endpoints, the maximum demand volume. This approach is applicable to VPNs for which the exact traffic demands matrix can be predicted. As the number of endpoints per VPN is constantly growing, the traffic demands patterns are becoming more and more complex. Therefore, for some VPNs, it is almost impossible to predict maximum value of each traffic demand. Duffield at all proposed in [START_REF] Duffield | A flexible model for resource management in virtual private networks[END_REF] the hose VPN model in which VPN customer specifies aggregate requirements for each VPN endpoint, and not for each pair of endpoints. In comparison to the pipe model, the hose model provides a simpler and more flexible way of VPN traffic demands specification.

The customer only defines ingress and egress bandwidths of VPN endpoints, which can be more easily predicted than traffic demands matrix. In the hose model it is assumed that all patterns of traffic demands that conforms the ingress and egress bandwidths of VPN endpoints can be realized. In [START_REF] Chu | New architecture and algorithms for fast construction of hosemodel vpns[END_REF] the concept of architecture for provisioning VPNs that come sequentially in the dynamic fashion is presented. Nonetheless, it does not take into account the costs of network resources. The problem of determining the minimum cost bandwidth reservation that satisfies all VPN traffic requirements in hose model is analyzed in [START_REF] Altin | Provisioning virtual private networks under traffic uncertainty[END_REF][START_REF] Erlebach | Optimal bandwidth reservation in hose-model VPNs with multi-path routing[END_REF]. In [START_REF] Ben-Ameur | Routing of uncertain traffic demands[END_REF] a more general model of VPN traffic demands is considered, called polyhedral model, that allows for specifying a set of required VPN traffic demands defined by some linear inequalities.

In this paper we consider the general network resource allocation problem in the context of the multilateral trade. In this problem the network resources are owned by several market entities, such as companies laying cables, network providers and other network link owners. The customers on the market are geographically spread organizations and other institutions that are interested in purchasing VPN services. We assume that sellers offer single links and buyers want to purchase VPN services between several nodes. Currently, the dominating form of bandwidth trading are bilateral agreements in which two participants negotiate the contract terms. The negotiations are complex, nontransparent and time consuming. The customer that wants to purchase bandwidth between several nodes connected by a set of links owned by different providers must independently negotiate with all of them. If the negotiation fails with one of them (whereas agreements with other sellers would be drawn up and signed), the customer will get useless bandwidth as it will not ensure the connection between all selected nodes. Also even if the buyer manages to purchase bandwidth that ensures connectivity between all VPN endpoints, there is a risk that VPN service could be provided by a cheaper set of links. Thus there is a need of designing more sophisticated market mechanisms that will support customers in purchasing network resources of complex structure and enable efficient management of network resources distributed among several providers. Lately analysis of bandwidth market gives promise of emerging new forms of bandwidth trading in the future [START_REF] Iselt | Bandwidth trading -a business case for ASON?[END_REF][START_REF] Rabbat | Revisiting bandwidth-on-demand enablers and challengers of a bandwidth market[END_REF].

Most of the auction mechanisms for bandwidth trading considered in the literature concern auctioning the bundles of links [START_REF] Dramitinos | An auction mechanism for allocating the bandwidth of networks to their users[END_REF][START_REF] Jain | Efficient market mechanisms for network resource allocation[END_REF][START_REF] Jain | An efficient mechanism for network bandwidth auction[END_REF]. They support purchasing VPN in a very limited way because they require that the customer explicitly specifies the set of links realizing all VPN traffic demands instead of allowing the customer for convenient VPN traffic demands specification as in the abovementioned pipe or hose model. In [START_REF] Stańczuk | Trading links and paths on a communication bandwidth markets[END_REF] the multicommodity auction model for balancing communication bandwidth trading (BCBT) is presented. Although it enables submitting buy offers for end to end demands, it does not guarantee that all end to end demands associated with the particular VPN are obtained by the customer. A generalization of BCBT model that supports purchasing VPN services represented in the pipe model is proposed in [START_REF] Kołtyś | A bandwidth auction model for purchasing VPN[END_REF]. In this paper we introduce a more flexible VPN auction model AM-VPN that allows the customer to specify the requirements for VPN traffic demands defined not only in the pipe but also in the hose and mixed pipe-hose representations.

Auction Model

The proposed AM-VPN model concerns a single-round sealed-bid double auction of network resources. The set 𝒱 represents all nodes of the network. We denote the set of sell offers by ℰ and the set of buy offers by ℬ.

The sell offer 𝑒 ∈ ℰ regards to single link and the parameter 𝑎 𝑣𝑒 defined for each network node 𝑣 ∈ 𝒱 states which node is a source of this link (𝑎 𝑣𝑒 = 1), which is a destination of this link (𝑎 𝑣𝑒 = -1) and which nodes are not associated with this link (𝑎 𝑣𝑒 = 0). Sell offer 𝑒 includes the minimum sell unit price 𝑆 𝑒 and the maximum volume of bandwidth 𝑥 max 𝑒 offered for sale at particular link. We assume that bandwidth of links is a fully divisible commodity and every sell offer can be partially accepted. We denote the contracted bandwidth of link offered in sell offer 𝑒 by variable 𝑥 𝑒 .

The buy offer 𝑚 ∈ ℬ regards to VPN. It contains the maximum price 𝐸 𝑚 that buyer is willing to pay for VPN and specification of the VPN traffic demands. We denote the set of VPN endpoints by 𝒬 𝑚 (𝒬 𝑚 ⊆ 𝒱) and the set of traffic demands between VPN endpoints by 𝒟 𝑚 . Each demand 𝑑 ∈ 𝒟 𝑚 represents a required connection between source endpoint 𝑠 𝑑 ∈ 𝒬 𝑚 and destination endpoint 𝑡 𝑑 ∈ 𝒬 𝑚 , where 𝑠 𝑑 ̸ = 𝑡 𝑑 . For demand 𝑑 ∈ 𝒟 𝑚 and each network node 𝑣 ∈ 𝒱 the parameter 𝑐 𝑣𝑑 is defined, such that 𝑐 𝑠 𝑑 𝑑 = 1, 𝑐 𝑡 𝑑 𝑑 = -1 and 𝑐 𝑣𝑑 = 0 if 𝑣 ̸ = 𝑠 𝑑 and 𝑣 ̸ = 𝑡 𝑑 . Any value of the traffic demand 𝑑 ∈ 𝒟 𝑚 is a variable denoted by 𝑥 𝑑 . The set 𝒳 𝑚 contains all vectors of traffic demands values (𝑥 𝑑 ) 𝑑∈𝒟𝑚 that must be provided by VPN service. We assume that buy offer can be partially accepted and denote the accepted fraction of buy offer 𝑚 by variable 𝑥 𝑚 .

We propose the mixed pipe-hose model which enables to define the set 𝒳 𝑚 in the general way that combines pipe and hose traffic demands models. In the mixed pipe-hose model the VPN customer is able to define two types of requirements. The first type of requirements allows for specifying the egress bandwidth 𝑏 + 𝑚𝑣 and ingress bandwidth 𝑏 - 𝑚𝑣 for given endpoints 𝑣 ∈ 𝒬 H 𝑚 (𝒬 H 𝑚 ⊆ 𝒬 𝑚 ). The second type of requirements allows for specifying the maximum volume ℎ 𝑑 of bandwidth for some demands 𝑑 ∈ 𝒟 P 𝑚 (𝒟 P 𝑚 ⊆ 𝒟 𝑚 ). Thus, in the mixed pipehose model the set 𝒳 𝑚 is defined by parameters 𝑏 + 𝑚𝑣 , 𝑏 - 𝑚𝑣 and ℎ 𝑑 as follows:

𝒳 𝑚 = { (𝑥 𝑑 ) 𝑑∈𝒟𝑚 : ∑ 𝑑∈𝒟𝑚: 𝑣=𝑠 𝑑 𝑥 𝑑 ≤ 𝑏 + 𝑚𝑣 , ∑ 𝑑∈𝒟𝑚: 𝑣=𝑡 𝑑 𝑥 𝑑 ≤ 𝑏 - 𝑚𝑣 ∀ 𝑣∈𝒬 H 𝑚 ; 𝑥 𝑑 ≤ ℎ 𝑑 ∀ 𝑑∈𝒟 P 𝑚 }
The above mixed pipe-hose model is a generalization of the pipe and hose models. Let parameter 𝑥 𝜏 𝑑 be a value of demand 𝑑 ∈ 𝒟 in scenario 𝜏 ∈ 𝒯 . We assume that routing for each demand is static and can be carried on many paths. For each demand 𝑑, we denote by variable 𝑓 𝑒𝑑 the fraction of traffic demand value 𝑥 𝜏 𝑑 (regardless of scenario 𝜏 ) that is routed through link offered in sell offer 𝑒.

The AM-VPN model defines the allocation and pricing rules. The allocation rule determines contracted bandwidth of sell offers and realization of buy offers that provides the maximum social welfare Q. It also settles a matching of accepted sell and buy offers by assigning links bandwidth of accepted sell offers to VPN services of accepted buy offers. The pricing rule defines the revenues of sellers and payments of buyers. The allocation rule is defined as linear programming (LP) problem. Such a formulation is very advantageous because standard optimization solvers can be used to determine optimal allocation and dual prices can be used to define the pricing rule. Below we present both rules in detail.

Allocation Rule

The allocation rule can be formulated as the following optimization problem:

Q = max ( ∑ 𝑚∈ℬ 𝐸 𝑚 𝑥 𝑚 - ∑ 𝑒∈ℰ 𝑆 𝑒 𝑥 𝑒 ) (1)
∑ 𝑚∈ℬ ∑ 𝑑∈𝒟𝑚 𝑓 𝑒𝑑 𝑥 𝜏 𝑑 ≤ 𝑥 𝑒 ∀ 𝑒∈ℰ , ∀ 𝜏 ∈𝒯 (2)
∑ 𝑒∈ℰ 𝑎 𝑣𝑒 𝑓 𝑒𝑑 = 𝑐 𝑣𝑑 𝑥 𝑚 ∀ 𝑣∈𝒱 , ∀ 𝑚∈ℬ , ∀ 𝑑∈𝒟𝑚 (3) 0 ≤ 𝑥 𝑒 ≤ 𝑥 max 𝑒 ∀ 𝑒∈ℰ (4) 0 ≤ 𝑥 𝑚 ≤ 1 ∀ 𝑚∈ℬ (5) 0 ≤ 𝑓 𝑒𝑑 ∀ 𝑒∈ℰ , ∀ 𝑚∈ℬ , ∀ 𝑑∈𝒟𝑚 (6)
The objective function is defined by equation ( 1) that express the social welfare being maximized. Thus, the allocation rule provides the highest economic profit that may be obtained by the sellers and buyers as a result of the trade. The constraints (2) ensure that for each scenario the bandwidth sold at link is sufficient to realize the appropriate fraction of demands values of all buy offers. Equation ( 3) is a flow conservation constraint that must be met for each demand of every buy offer. If 𝑥 𝑚 = 0, then buy offer 𝑚 is rejected. If 𝑥 𝑚 = 1, then buy offer 𝑚 is fully accepted. Otherwise, buy offer 𝑚 is partially accepted and a set 𝒳 ′ 𝑚 defined by parameters

𝑏 + ′ 𝑚𝑣 = 𝑥 𝑚 𝑏 + 𝑚𝑣 , 𝑏 -′ 𝑚𝑣 = 𝑥 𝑚 𝑏 - 𝑚𝑣 and ℎ ′ 𝑑 = 𝑥 𝑚 ℎ 𝑑 is provided.
Note that in such a case the connectivity between all VPN endpoints is ensured, but only the values of traffic demands that can be realized by the VPN service are smaller proportionally to 𝑥 𝑚 .

The above LP problem is hard to solve directly, because the constraints (2) must be defined for immense number of scenarios 𝜏 ∈ 𝒯 . Below we present two different allocation models, called AR1 and AR2 , that are based on compact LP formulation and column generation method, respectively.

To formulate the AR1 model of the allocation problem let us assume that the routing of all VPN demands (𝑓 𝑒𝑑 ) is fixed. For given buy offer 𝑚 we denote by 𝑥 𝑚𝑒 the bandwidth of link involved with offer 𝑒 that is required to realize the worst case scenario of VPN traffic demands values. Taking vector (𝑥 𝑑 ) 𝑑∈𝒟𝑚 as decision variables and inequalities defining set 𝒳 𝑚 as constraints, we can form following optimization problem that determines the minimum value of 𝑥 𝑚𝑒 :

x𝑚𝑒 = max ( ∑ 𝑑∈𝒟𝑚 𝑓 𝑒𝑑 𝑥 𝑑 ) (7)
∑

𝑑∈𝒟𝑚:𝑣=𝑠 𝑑 𝑥 𝑑 ≤ 𝑏 + 𝑚𝑣 , ∀ 𝑣∈𝒬 H 𝑚 ( 8
)
∑ 𝑑∈𝒟𝑚:𝑣=𝑡 𝑑 𝑥 𝑑 ≤ 𝑏 - 𝑚𝑣 , ∀ 𝑣∈𝒬 H 𝑚 ( 9
)
𝑥 𝑑 ≤ ℎ 𝑑 , ∀ 𝑑∈𝒟 P 𝑚 (10) 0 ≤ 𝑥 𝑑 , ∀ 𝑑∈𝒟𝑚 (11)
By 𝜋 𝑣+ 𝑚𝑒 , 𝜋 𝑣- 𝑚𝑒 and 𝜋 𝑑 𝑒 we denote the dual variables corresponding to constraints (8), [START_REF] Dramitinos | An auction mechanism for allocating the bandwidth of networks to their users[END_REF], and [START_REF] Jain | Efficient market mechanisms for network resource allocation[END_REF], respectively. For each buy offer 𝑚 ∈ ℬ and demand 𝑑 ∈ 𝒟 𝑚 we define a parameter 𝜎 𝑑 , such that

𝜎 𝑑 = 1 if 𝑑 ∈ 𝒟 P 𝑚 and 𝜎 𝑑 = 0 if 𝑑 / ∈ 𝒟 P 𝑚 .
Then, the allocation rule AR1 can be formulated as the following LP problem:

Q = max ( ∑ 𝑚∈ℬ 𝐸 𝑚 𝑥 𝑚 - ∑ 𝑒∈ℰ 𝑆 𝑒 𝑥 𝑒 ) (12)
∑ 𝑒∈ℰ 𝑎 𝑣𝑒 𝑓 𝑒𝑑 = 𝑐 𝑣𝑑 𝑥 𝑚 ∀ 𝑣∈𝒱 , ∀ 𝑚∈ℬ , ∀ 𝑑∈𝒟𝑚 (16) 0 ≤ 𝑥 𝑒 ≤ 𝑥 max 𝑒 ∀ 𝑒∈ℰ (17) 0 ≤ 𝑥 𝑚 ≤ 1 ∀ 𝑚∈ℬ (18) 0 ≤ 𝜋 𝑣+ 𝑚𝑒 , 𝜋 𝑣- 𝑚𝑒 ∀ 𝑒∈ℰ , ∀ 𝑚∈ℬ , ∀ 𝑣∈𝒬 H 𝑚 (19) 0 ≤ 𝜋 𝑑 𝑒 ∀ 𝑒∈ℰ , ∀ 𝑚∈ℬ , ∀ 𝑑∈𝒟 P 𝑚 ( 20
)
where ( 13) and ( 14) represent objective function and constraints of the dual problem to ( 7)- [START_REF] Jain | An efficient mechanism for network bandwidth auction[END_REF]. The optimization problem AR1 is a LP problem that can be solved directly using standard optimization solvers. A similar approach for solving a problem of provisioning VPN in the hose model was proposed in [START_REF] Altin | Provisioning virtual private networks under traffic uncertainty[END_REF].

An alternative formulation AR2 of the allocation rule is also the LP problem, but it applies column generation technique to achieve optimal allocation. For each buy offer 𝑚 ∈ ℬ we define a set ℱ 𝑚 that contains scenarios of network resource allocation realizing VPN service specified in buy offer 𝑚. For given buy offer 𝑚 ∈ ℬ, scenario 𝛽 ∈ ℱ 𝑚 and sell offer 𝑒 ∈ ℰ the parameter 𝛼 𝛽 𝑚𝑒 states how much bandwidth of particular link associated with sell offer 𝑒 is required by scenario 𝛽. Let variable 𝑥 𝛽 𝑚 denotes the realization of buy offer 𝑚 in the scenario 𝛽 ∈ ℱ 𝑚 . The master problem of the column generation algorithm used in AR2

problem determines the optimal allocation for given set of scenarios ℱ 𝑚 defined for each buy offer 𝑚 ∈ ℬ. It has a form of the following LP problem AR2-MP:

Q = max ( ∑ 𝑚∈ℬ 𝐸 𝑚 𝑥 𝑚 - ∑ 𝑒∈ℰ 𝑆 𝑒 𝑥 𝑒 ) (21)
𝑥 𝑚𝑒 = ∑ 𝛽∈ℱ𝑚 𝛼 𝛽 𝑚𝑒 𝑥 𝛽 𝑚 ∀ 𝑚∈ℬ , ∀ 𝑒∈ℰ (22)
∑ 𝑚∈ℬ 𝑥 𝑚𝑒 ≤ 𝑥 𝑒 ∀ 𝑒∈ℰ ( 23
)
𝑥 𝑚 = ∑ 𝛽∈ℱ𝑚 𝑥 𝛽 𝑚 ∀ 𝑚∈ℬ ( 24
)
𝑥 𝑒 ≤ 𝑥 max 𝑒 ∀ 𝑒∈ℰ (25)
𝑥 𝑚 ≤ 1 ∀ 𝑚∈ℬ (26) 0 ≤ 𝑥 𝑒 ∀ 𝑒∈ℰ (27) 0 ≤ 𝑥 𝑚 ∀ 𝑚∈ℬ (28) 0 ≤ 𝑥 𝛽 𝑚 ∀ 𝑚∈ℬ , ∀ 𝛽∈ℱ𝑚 (29)
For each buy offer 𝑚 and prices 𝜉 𝑒 obtained from the master problem AR2-MP we define the optimization subproblem AR2-SP 𝑚 (𝜉 𝑒 ) that determines the allocation 𝛼 𝑚𝑒 realizing VPN service of buy offer 𝑚 with the lowest cost Ψ𝑚 :

Ψ𝑚 = min ( ∑ 𝑒∈ℰ 𝜉 𝑒 𝛼 𝑚𝑒 ) (30) ∑ 𝑣∈𝒬 H 𝑚 (𝜋 𝑣+ 𝑚𝑒 𝑏 + 𝑚𝑣 + 𝜋 𝑣- 𝑚𝑒 𝑏 - 𝑚𝑣 ) + ∑ 𝑑∈𝒟 P 𝑚 𝜋 𝑑 𝑒 ℎ 𝑑 ≤ 𝛼 𝑚𝑒 ∀ 𝑒∈ℰ (31) 0 ≤ 𝑓 𝑒𝑑 ≤ ∑ 𝑣∈𝒬 H 𝑚 : 𝑣=𝑠 𝑑 𝜋 𝑣+ 𝑚𝑒 + ∑ 𝑣∈𝒬 H 𝑚 : 𝑣=𝑡 𝑑 𝜋 𝑣- 𝑚𝑒 + 𝜎 𝑑 𝜋 𝑑 𝑒 ∀ 𝑒∈ℰ , ∀ 𝑑∈𝒟𝑚 (32) ∑ 𝑒∈ℰ 𝑎 𝑣𝑒 𝑓 𝑒𝑑 = 𝑐 𝑣𝑑 ∀ 𝑣∈𝒱 , ∀ 𝑑∈𝒟𝑚 (33) 0 ≤ 𝛼 𝑚𝑒 ∀ 𝑚∈ℬ , ∀ 𝑒∈ℰ (34) 0 ≤ 𝜋 𝑣+ 𝑚𝑒 , 𝜋 𝑣- 𝑚𝑒 ∀ 𝑒∈ℰ , ∀ 𝑣∈𝒬 H 𝑚 (35) 0 ≤ 𝜋 𝑑 𝑒 ∀ 𝑒∈ℰ , ∀ 𝑑∈𝒟 P 𝑚 (36)
The allocation rule of the AM-VPN model can be now formulated as the optimization problem AR2 , that can be solved by the following algorithm based on the column generation technique:

1. For each 𝑚 ∈ ℬ initialize the set ℱ 𝑚 (e.g. for each 𝑚 ∈ ℬ solve AR2-SP 𝑚 (𝑆 𝑒 )).

2. Solve AR2-MP. For obtained optimal solution let λ𝑒 and ω𝑚 denote the values of dual prices associated with constraints ( 23) and (24), respectively.

3. For each 𝑚 ∈ ℬ solve AR2-SP 𝑚 ( λ𝑒 ) determining Ψ𝑚 i α𝑚𝑒 .

4. If for each 𝑚 ∈ ℬ inequality Ψ𝑚 ≥ ω𝑚 is met, then allocation determined in step 2 is optimal (STOP). Otherwise for each 𝑚 ∈ ℬ that fulfills inequality Ψ𝑚 < ω𝑚 , create new scenario 𝛽, such that 𝛼 𝛽 𝑚𝑒 = α𝑚𝑒 , and add it to set ℱ 𝑚 . Go to step 2.

It can be proved that optimization problems AR1 and AR2 define equivalent allocation rules of the AM-VPN model. In general the result of the allocation rule is denoted as vector x=(x 𝑒 , x𝑚 , x𝑚𝑒 ).

Pricing Rule

The pricing rule of the AM-VPN model is strictly connected with the formulation of AM-VPN allocation rule as it leverages the fact that allocation rule is defined by LP problems AR1 or AR2 . For allocation x determined by solving problem AR1 or AR2 we define by λ𝑒 the values of corresponding dual prices associated with constraint (15) in the case of AR1 , or constraint (23) in the case of AR2 . The pricing rule of the AM-VPN model sets the unit clearing price of link associated with offer 𝑒 equal to λ𝑒 . Then the revenue 𝑝 𝑒 of the seller that submits sell offer 𝑒 equals:

𝑝 𝑒 = λ𝑒 x𝑒 , (37)
and the payment 𝑝 𝑚 of the buyer that submits buy offer 𝑚 equals:

𝑝 𝑚 = ∑ 𝑒∈ℰ λ𝑒 x𝑚𝑒 . ( 38
)
5 Model Properties

In this section we present some general properties of the proposed auction model AM-VPN . Denote the economic profit of seller whose sell offer 𝑒 realization is 𝑥 𝑒 and revenue equals 𝑝 𝑒 as follows:

𝑈 𝑒 (𝑥 𝑒 , 𝑝 𝑒 ) = 𝑝 𝑒 -𝑆 𝑒 𝑥 𝑒 , (39)
Analogously, define the economic profit of the buyer whose buy offer 𝑚 realization is 𝑥 𝑚 and payment equals 𝑝 𝑚 as follows: Proof. This proof assumes that the allocation x is given by AR2 , but analogously proof can be done in the case of AR1 . Let γ𝑚𝑒 , λ𝑒 , ω𝑚 , μ𝑒 , μ𝑚 be the values of dual variables corresponding to optimal solution of AR2 related to constraints ( 22)-( 26), respectively. From duality theory it follows that above values satisfy the following complementary slackness conditions:

𝑈 𝑚 (𝑥 𝑚 , 𝑝 𝑚 ) = 𝐸 𝑚 𝑥 𝑚 -𝑝 𝑚 . ( 40
)
x𝑒 (𝑆 𝑒 + μ𝑒 -λ𝑒 ) = 0 ∀ 𝑒∈ℰ (41) x𝑚 (-𝐸 𝑚 + μ𝑚 + ω𝑚 ) = 0 ∀ 𝑚∈ℬ (42) x𝛽 𝑚 ( ∑ 𝑒∈ℰ γ𝑚𝑒 𝛼 𝛽 𝑚𝑒 -ω𝑚 ) = 0 ∀ 𝑚∈ℬ , ∀ 𝛽∈ℱ𝑚 (43) x𝑚𝑒 ( λ𝑒 -γ𝑚𝑒 ) = 0 ∀ 𝑚∈ℬ , ∀ 𝑒∈ℰ (44)
The economic profit of seller that submits sell offer 𝑒 is non-negative because:

𝑈 𝑒 (x 𝑒 , 𝑝 𝑒 ) = 𝑝 𝑒 -𝑆 𝑒 x𝑒 = ( λ𝑒 -𝑆 𝑒 )x 𝑒 = μ𝑒 x𝑒 ≥ 0 (45)
The equations in (45) results from (39), ( 37) and ( 41), respectively and the last inequality holds, because μ𝑒 ≥ 0 as it is a dual variable related to inequality constraint (25). The economic profit of the buyer that submits buy offer 𝑚 is non-negative because:

𝑈 𝑚 (x 𝑚 , 𝑝 𝑚 ) = 𝐸 𝑚 x𝑚 -𝑝 𝑚 = 𝐸 𝑚 x𝑚 - ∑ 𝑒∈ℰ λ𝑒 x𝑚𝑒 = (46) = 𝐸 𝑚 x𝑚 - ∑ 𝑒∈ℰ γ𝑚𝑒 x𝑚𝑒 = 𝐸 𝑚 x𝑚 - ∑ 𝑒∈ℰ γ𝑚𝑒 ∑ 𝛽∈ℱ𝑚 𝛼 𝛽 𝑚𝑒 x𝛽 𝑚 = (47) = 𝐸 𝑚 x𝑚 - ∑ 𝛽∈ℱ𝑚 ω𝑚 x𝛽 𝑚 = (𝐸 𝑚 -ω𝑚 )x 𝑚 = μ𝑚 x𝑚 ≥ 0 (48)
The equations in (46) results from (40) and (38), respectively. The equations in (47) follows from (44) and ( 22), respectively. The equations in (48) results from (43), ( 24) and (42), respectively, and the last inequality holds, because μ𝑚 ≥ 0 as it is a dual variable related to inequality constraint (26). ⊓ ⊔ Proposition 2. The AM-VPN model has budget balance property, i.e. for given allocation x, revenues 𝑝 𝑒 and payments 𝑝 𝑚 determined by the AM-VPN model the following condition is met:

∑ 𝑚∈ℬ 𝑝 𝑚 = ∑ 𝑒∈ℰ 𝑝 𝑒 . (49)
Proof. This proof assumes that the allocation x is given by AR2 , but analogously proof can be done in the case of AR1 . Let λ𝑒 be the value of dual variable corresponding to optimal solution of AR2 related to constraint (23). From duality theory it results that following complementary slackness condition is satisfied:

λ𝑒 ( ∑ 𝑚∈ℬ x𝑚𝑒 -x𝑒 ) = 0 ∀ 𝑒∈ℰ (50)
Then the following equations are met:

∑ 𝑚∈ℬ 𝑝 𝑚 = ∑ 𝑚∈ℬ ∑ 𝑒∈ℰ λ𝑒 x𝑚𝑒 = ∑ 𝑒∈𝐸 λ𝑒 x𝑒 = ∑ 𝑒∈ℰ 𝑝 𝑒 (51)
The equations in (51) results from (38), ( 50) and (37) respectively.

⊓ ⊔

We have shown that the AM-VPN is individually rational and budget balanced. These properties are very valuable. The first one guarantees that trader will not lose by participating in the auction. The second one ensures that the operator organizing the auction does not have to pay extra money in order to proceed the auction and it does not obtain any unjustified economic profits.

Flexibility of the AM-VPN Auction Model

The AM-VPN model provides a flexible way for defining the customer's preferences related to VPN service using mixed pipe-hose representation. In this section we illustrate some benefits that customer obtains by having possibility of specifying a VPN service with mixed pipe-hose representation rather than with pipe or hose representation only.

The example concerns the network presented in Fig. 1a. The network consists of 11 nodes and 10 pairs of directed links denoted by solid lines. Each directed link is involved with one sell offer. Thus, there are 20 sell offers having the same unit price 10 and maximum volume 1500. We consider one customer that want to purchase VPN service concerning nine nodes: 𝐴, 𝐵, 𝐶, 𝐷, 𝐹 , 𝐺, 𝐻, 𝐽 and 𝐾. The VPN topology is depicted in Fig. 1a. The numbers at nodes denote the ingress and egress bandwidth of appropriated endpoints. The dotted lines connecting the selected pairs of VPN endpoints mean the demands that are required to be satisfied by VPN. All remaining demands between VPN endpoints have not to be provided. The customer is willing to pay 60000 for this VPN service.

Above resource allocation problem can be solved by means of the AM-VPN model with customer requirements related to VPN specified in mixed pipe-hose representation. Achieved allocation is depicted in Fig. 1b. The numbers at links denote the bandwidth sold to the customer. Note that the buy offer is fully accepted. The clearing prices of links determined by the model AM-VPN are equal to 10. Thus, the customer has to pay 10*4000=40000 for the VPN service. Assume now that the customer is only able to use pipe or hose model instead of flexible mixed pipe-hose representation.

In the case of hose model the customer can only specify the ingress and egress bandwidth of each VPN endpoint. If the customer submits a buy offer that concerns such a VPN service specification the optimal allocation provided by the AM-VPN changes as follows: the bandwidth sold at links between nodes 𝐸 and 𝐺 grows to 800 and the bandwidth sold at links between nodes 𝐺 and 𝐻 grows to 400. The clearing prices remain the same. Thus, in comparison with mixed pipe-hose case the customer has to purchase extra 400 units of bandwidth at links between nodes 𝐸 and 𝐺 and extra 200 units of bandwidth at links between nodes 𝐺 and 𝐻 resulting in higher customer's payment, i.e. 10*(4000+2*400+2*200)=52000.

In the case of pipe model the customer must define the maximum values of all demands. The maximum values of non-zero demands (denoted by dotted lines) are defined according to the typical pipe mesh approach, namely as the minimum of the egress bandwidth of source endpoint and the ingress value of destination endpoint. Naturally, the maximum values of all remaining demands are set to 0. If customer submits a buy offer that concerns such a VPN service specification, the allocation provided by the AM-VPN changes in comparison with the mixed pipe-hose model case at links between nodes 𝐸 and 𝐺 on which the bandwidth sold to the customer grows to 1000. The clearing prices remain the same. Thus, in comparison with mixed pipe-hose case the customer has to purchase extra 600 units of bandwidth at links between nodes 𝐸 and 𝐺 resulting in the higher customer's payment, i.e. 10*(4000+2*600)=52000.

Concluding this example, if the customer specifies his requirements for VPN traffic demands in the mixed pipe-hose model, he pays 40000 for required VPN service but if he is able to use merely the pipe or hose model, he has to pay much more, i.e. 52000. It results from the fact that the VPN specified in the pipe or hose model may require more network resources than the VPN specified in the mixed pipe-hose model which restricts the required VPN traffic demands more accurately than the pipe or hose model. Thus, as the above example illustrates, the flexibility of the AM-VPN model enables the customer to specify precisely the VPN service requirements in the mixed pipe-hose model which may improve his economic profit.

Computational Efficiency

In this section AR1 and AR2 allocation problems are compared in the respect of computational efficiency. We solve several resource allocation problems concerning three networks from SNDlib library [START_REF]Survivable network design library website[END_REF]: polska (12 nodes and 18 links), france (25 nodes and 45 links) and cost266 (37 nodes and 57 links). For each network 12 problems were prepared differing in the number of buy offers and the sizes of VPNs specified in the hose model. We consider problems with 5, 10, 25 and 50 buy offers, respectively and with VPNs that consist of 3, 6 and 9 nodes. In every allocation problem there is one sell offer submitted on each link.

Table 1 presents the time of determining the optimal solution by allocation rules AR1 and AR2 . The computations have been performed on computer with processor Intel Core2 Duo T8100 2,1GHz, main memory 3GB and 32-bit operating system MS Vista. For solving LP problems the CPLEX 12.1 has been used. For all problems concerning small VPNs (with 3 endpoints) or having small number of buy offers (5 or 10) AR1 is faster than AR2 . Nevertheless, as the size of the problem grows, the solution time of AR1 increases much more than in the case of AR2 . The benefits from applying AR2 rather than AR1 are especially apparent for the largest resource allocation problem defined for the cost266 network for which AR1 needs more than 7 hours to determine the allocation while AR2 calculates the optimal solution in about 11 minutes. Thus for the real resource allocation problems which usually are of large sizes it is better to use the AR2 rather than AR1 .

Conclusions

We propose the AM-VPN auction model that supports the allocation of the network resources distributed among several providers to the customers of VPN services. The model matches many sell and buy offers aiming at maximization of social surplus. The AM-VPN model has individual rationality and budget balance properties. The main merit of the model is flexibility in specifying the VPN traffic demands. It enables the VPN customer to employ the pipe, hose or mixed pipe-hose representations. The presented example demonstrates benefits gained by VPN customer when using the mixed pipe-hose traffic demands model. The proposed model determines optimal allocation and prices by solving an appropriate LP optimization model. The computational efficiency for large resource allocation problems can be improved by applying column generation technique.

  If we put 𝒬 H 𝑚 = ∅ and 𝒟 P 𝑚 = 𝒟 𝑚 , we obtain the VPN specification in the pipe model. If we put 𝒬 H 𝑚 = 𝒬 𝑚 and 𝒟 P 𝑚 = ∅, we obtain the VPN specification in the hose model. Define two following sets: 𝒳 = 𝒳 𝑚1 × ... × 𝒳 𝑚 |ℬ| and 𝒟 = 𝒟 𝑚1 ∪ ... ∪ 𝒟 𝑚 |𝒟𝑚| and denote by 𝒯 a set of all scenarios of VPNs demands values (𝑥 𝑑 ) 𝑑∈𝒟 ∈ 𝒳 .

Fig. 1 :

 1 Fig. 1: The network resource allocation problem solved by the AM-VPN model.

  Proposition 1. The AM-VPN model has individual rationality property, i.e. for given allocation x, revenues 𝑝 𝑒 and payments 𝑝 𝑚 determined by the AM-VPN model each seller obtains non-negative economic profit 𝑈 𝑒 (x 𝑒 , 𝑝 𝑒 ) ≥ 0, and each buyer obtains non-negative economic profit, 𝑈 𝑚 (x 𝑚 , 𝑝 𝑚 ) ≥ 0.

Table 1 :

 1 The time of determining the optimal allocation by AR1 and AR2[s]

	Network polska VPN endpoints 3 6 9	Buy offers 25 AR1 AR2 AR1 AR2 AR1 AR2 AR1 AR2 5 10 50 0,02 3,02 0,05 2,38 0,39 5,02 1,89 13,07 0,52 9,72 1,19 8,55 9,63 12,37 58,49 30,09 4,81 14,83 25,18 28,74 78,72 58,24 682,74 143,54
	Network france VPN endpoints 3 6 9	Buy offers 25 AR1 AR2 AR1 AR2 AR1 AR2 AR1 AR2 5 10 50 0,08 12,56 0,62 22,76 2,92 22,74 4,01 51,36 1,45 86,83 7,11 83,01 50,79 124,21 142,18 169,54 5,51 233,89 52,43 232,77 294,25 333 1653,20 283,62
	Network cost266 VPN endpoints 3 6 9	Buy offers 25 AR1 AR2 AR1 AR2 AR1 AR2 AR1 AR2 5 10 50 0,11 33,08 0,61 19,03 3,51 22,04 27,74 31,49 3,17 78,15 10,72 63,18 117,52 123,41 692,82 188,77 12,57 266,56 57,24 222,32 17130 418,44 26101 703,2

Acknowledgments

The authors acknowledge the Ministry of Science and Higher Education of Poland for partially supporting the research through Project N N514 044438.


Yung-Cheng Tu

Meng Chang

Yeali S Sun

Adaptive On-The-Go Scheduling for End-to-End Delay Control in TDMA-based Wireless Mesh Networks *

Keywords: TDMA-based scheduling, wireless mesh networks, slot allocation

Providing end-to-end delay bound for real-time applications is a major challenge in wireless mesh networks (WMNs) because the bandwidth requirements of flows are time-varied and the channel condition is unstable due to the wireless interference between the links. In this paper, we present a twostage slot allocation mechanism in TDMA-based WMNs. First, we assume that the bandwidth requirement of each flow is given in the form of a range and use a distributed algorithm to pre-allocate time slots to each link. Then, we implement an On-The-Go scheduling scheme, which enables each link to schedule its transmission time promptly without coordinating with others. In contrast to traditional approaches, our method allows a degree of control over the collision probability, but it only requires a few control messages and the computational overhead is lower. The simulation results show that our mechanism performs efficiently and flexibly on supporting real-time applications in WMNs.

Introduction

For high affordability and easy deployment, wireless mesh networks (WMNs) have been developed as cost-efficient networking platforms to support ubiquitous broadband Internet access in several cities [START_REF]Seattle wireless[END_REF][2] [START_REF]Rice TFA Network[END_REF]. A communication flow from source to destination in a WMN usually requires multiple hops. Due to the available bandwidth for each hop is time-varied depending on the current load and interference between the wireless links, supporting end-to-end quality of service (QoS) guarantees for communication flows in WMNs is a challenging task.

In this paper, we focus on QoS provisioning for real-time applications, such as VoIP, video conferencing and multi-media streaming. Real-time applications usually generate variable-bit-rate (VBR) traffic and require an end-to-end QoS guarantee. It is known that contention-based protocols, like CSMA/CA used in IEEE 802.11 [START_REF]IEEE Standard for Information Technology-Telecommunications and Information Exchange Between Systems-Local and Metropolitan Area Networks-Specific Requirements -Part 11: Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications[END_REF], cannot provide strict QoS guarantees because they will result in service unfairness 2 Yung-Cheng Tu, Meng Chang Chen and Yeali S. Sun between wireless links [START_REF] Garetto | Modeling Per-flow Throughput And Capturing Starvation in CSMA Multi-hop Wireless Networks[END_REF] in multi-hop wireless networks. In contrast, time division multiple access (TDMA) based MAC protocols, such as the 802.16 mesh protocol [START_REF]IEEE Standard for Local and Metropolitan Area Networks Part 16: Air Interface for Fixed Broadband Wireless Access Systems[END_REF] and the 802.11s mesh coordination function (MCF) coordinated channel access protocol [START_REF]IEEE Draft STANDARD for Information Technology--Telecommunications and information exchange between systems--Local and metropolitan area networks--Specific requirements Part 11: Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) specifications Amendment 10: Mesh Networking[END_REF], provide collision-free communications and allow fine control of the throughput and delay of network traffic.

Several TDMA-based scheduling algorithms with different objective functions have been proposed for WMNs, e.g., maximizing system throughput [START_REF] Kabbani | Distributed Low-Complexity Maximum-Throughput Scheduling for Wireless Backhaul Networks[END_REF][9] [START_REF] Li | Joint Throughput Optimization for Wireless Mesh Networks[END_REF], fairness [START_REF] Li | Joint Throughput Optimization for Wireless Mesh Networks[END_REF] [START_REF] Cicconetti | FEBA: A Bandwidth Allocation Algorithm for Service Differentiation in IEEE 802.16 Mesh Networks[END_REF], and flow utility [START_REF] Wang | Qos-Aware Fair Rate Allocation in Wireless Mesh Networks[END_REF] [START_REF] Hou | A Distributed Scheduling Framework for Multi-User Diversity Gain and Quality of Service in Wireless Mesh Networks[END_REF], or minimizing end-to-end transmission delays [START_REF] Djukic | Delay Aware Link Scheduling for Multi-Hop TDMA Wireless Networks[END_REF]. These algorithms can be classified into two types: centralized algorithms and distributed algorithms. For centralized algorithms, the central controller requires a substantial amount of time to collect the bandwidth requirements of all links, apply the scheduling algorithm and deliver the scheduling results to all the mesh nodes. In contrast, a distributed scheduling algorithm is applied by each mesh node without the information about the whole network. However, coordination between the mesh nodes is necessary to ensure that the transmissions of different links will not conflict with each other. As a result, the coordination mechanism incurs extra overheads and scheduling waiting time [START_REF] Kabbani | Distributed Low-Complexity Maximum-Throughput Scheduling for Wireless Backhaul Networks[END_REF] [START_REF] Cicconetti | FEBA: A Bandwidth Allocation Algorithm for Service Differentiation in IEEE 802.16 Mesh Networks[END_REF][13] [START_REF] Rhee | DRAND: Distributed Randomized TDMA Scheduling for Wireless Ad Hoc Networks[END_REF].

One of the major challenges in providing end-to-end QoS guarantees for real-time application flows in TDMA-based WMNs is how to rapidly adjust the slot allocation of each link when the traffic load of flows and network condition vary frequently. As mentioned above, for both centralized and distributed scheduling algorithms, there is a certain amount of latency between the time a link requests a scheduler and the time it gets the scheduling result. Therefore, all existing TDMA-based scheduling algorithms assume that the state of each link is fixed. Mostly when a link's state changes, it is usually necessary to re-schedule the transmission time of all the links in the network. To address the above problem, we propose an adaptive on-the-go scheduling scheme that allocates time slots for each link dynamically. The contributions of this work are as follows: 1. We propose a two-stage slot allocation mechanism for TDMA-based WMNs.

The first stage provides minimum end-to-end QoS guarantees to all real-time application flows; and the second stage allows each link to adjust its transmission time dynamically to maximally satisfy the QoS requirements of all flows on the link and prevent transmission collisions with other links. 1. In contrast to traditional conflict-free slot allocation schemes, we allocate conflictfree slots and multi-access slots to each link. The transmissions in the conflictfree slots of each link will not be interfered by those of other links. For the multiaccess slots, we can control the number of interference nodes and maximize network utilization by selecting appropriate transmission time slots for each link. 2. We present an adaptive on-the-go scheduling scheme that each link can schedule its transmission times without coordinating with other links. The mechanism performs more flexibly on real-time application flows than traditional one-stage conflict-free slot allocation schemes.

The remainder of this paper is organized as follows. In Section 2, we define the network and system model of our work. In Section 3, we present our two-stage slot allocation mechanism. In Section 4, we introduce the adaptive on-the-go scheduling scheme for our two-stage slot allocation mechanism. In Section 5, we evaluate the scheme's performance via simulations. Finally, we give a conclusion in section 6. Like most TDMA-based protocols, we divide the timeline into recurrent frames, each comprised of M fixed-length time slots. Suppose the demand rate of flow f i at the link v k in the frame t is r i,k (t) and C k is the channel capacity of link v k ., we can estimate the total bandwidth requirement R k (t) and slot requirement T k (t) of the link v k in the frame t as follows:

Adaptive On-The-Go

, | ( ) ( )

k i k i k i v Path R t r t ∈ = ∑ (1) ( ) ( ) k k k T t M R t C = ⋅     (2)
Similarly, we can derive the minimum and maximum slot requirements, denoted as T k min and T k max , of v k from R k min and R k max . We assume that the demand rate r i,k (t) of each flow i at link v k is between min , i k r and min , i k r , so the slot requirements of link v k is bounded by min max ( , )

k k T T .

The Two-Stage Slot Allocation Mechanism

The system framework of our two-stage slot allocation mechanism with on-the-go scheduling is shown in Fig. 1. The demand rate of a flow f i is estimated based on the traffic load, network condition and the end-to-end QoS requirement of the flow. Any bandwidth estimation algorithm that supports end-to-end delay control, such as the per-node delay assignment scheme [START_REF] Vagish | Per-Node Delay Assignment Strategies for Real-Time High Speed Network[END_REF] or the bulk scheduling scheme [START_REF] Tu | Enhanced Bulk Scheduling for Supporting Delay Sensitive Streaming Applications[END_REF], can be used in our mechanism. In the first stage, we pre-allocate slots to each link v k according to the link's minimum and maximum slot requirements. Since T k min and T k max are determined by the minimum and maximum demand rates of all flows in v k , slot pre-allocation is only required when a flow joins or leaves this link. It is not necessary to dynamically adjust the pre-allocated slots with the variable traffic load; therefore coordination between the links is allowed in this stage. The second stage of our slot allocation mechanism implements the on-the-go scheduling scheme. The scheme tries to select slots dynamically from the pre-allocated slots in the first stage to maximally satisfy the immediate bandwidth requirements of all flows on the link and prevent transmission collisions with other links.

Conflict-free and multi-access slots

The objective of the slot pre-allocation scheme is to allocate slots for each link v k such that T k min can be guaranteed and T k max can be satisfied as much as possible in the second stage. Therefore, our pre-allocation scheme assigns two types of slots: conflict-free slots and multi-access slots for each link v k . The former is not allocated to any neighbor of v k while the latter can be allocated to some of its neighbors. Let m k and m' k be, respectively, the number of conflict-free slots and all pre-allocated slots. In our pre-allocation scheme, the m k is equal to T k min and m' k must be greater than T k min but cannot exceed T k max . Our scheme has the same constraint as [START_REF] Djukic | Delay Aware Link Scheduling for Multi-Hop TDMA Wireless Networks[END_REF], which requires that a link's pre-allocated slots are continuous in order to reduce the overhead of coordination between links. In addition, we assume that each active link contains at least one conflict-free slot to prevent flow starvation. Then the conflict-free slots of each link must also be continuous because the pre-allocated slots between any two conflict-free slots of a link v k cannot be pre-allocated to any neighbor of v k or it will result in the fragmentation of the pre-allocated slots of the link v k . Thus the preallocated slots of each link can be divided into three periods as in Fig. 2.

Suppose the starting positions of all pre-allocated slots and conflict-free slots of link v k in the frame table are the slot s' k and slot s k respectively. We define three periods of the pre-allocated slots of v k , namely, the head period Z k head , the body period Z k body and the tail period Z k tail , as follows:

( ) ( ) { } | , , head k k k k Z i s i s s ′ ′ = ∆ < ∆ (3) ( ) ( ) ( ) { } | , , , body k k k k k k k Z i s s s i s s m ′ ′ ′ = ∆ ≤ ∆ < ∆ + (4) ( ) ( ) { } | , , tail k k k k k k Z i s s m s i m ′ ′ ′ = ∆ + ≤ ∆ < (5)
Adaptive On-The-Go Scheduling for End-to-End Delay Control in TDMA-based Wireless Mesh Networks 5

where ( ) , ( ) mod M i j j i ∆ =represents the distance from slot i to slot j in recurrent frames. The relationships between the three periods are shown in Fig. 2. The transmission of link v k in a slot i during its head period will only compete for transmission opportunities with link v l , where v l ∈NB(v k ) and v l 's tail period Z l tail contains the slot i. Moreover, a transmission of v k in a slot j∈Z k tail will only compete with the link v m , where v m ∈NB(v k ,) and j∈Z m head . Thus, the contention degree of a link v k in our two-stage slot allocation mechanism can be bounded. Let CG(v k ) be a subgraph of CG that contains only the neighbors of v k and the edges between the neighbors. Under our pre-allocation scheme, the number of links that compete for transmission opportunities with v k , in any time slot is not greater than the size of the maximum independent set of all links in CG(v k ) because the links that can compete for transmission opportunities with v k at any slot cannot be neighbors with each other.

Body (Conflict-free) Head (Multi-access) Tail (Multi-access) Frame table of link v k s' k s k s k + m k s' k + m' k

The slot pre-allocation scheme

The objective of our slot pre-allocation scheme is to maximally satisfy the slot requirements of all links. The pre-allocation scheme can be centralized or distributed with some coordination. However, the scheduler needs information about all the links in the WMN to get the global optimal solution, which incurs a large communication overhead and requires a great deal of computation time. Moreover, because all links in a WMN must adjust their pre-allocated slots once a link changes its pre-allocation, each link's pre-allocation will be changed frequently. This results in instability in the short-term throughput of each link and higher delay jitters between links. Therefore, we consider the following local optimization problem for each link which can be solved by a distributed pre-allocation algorithm:

( ) ( ) ( ) ( ) (
)

min max min max : , , , ( ), and , , , of all ( )
: , , , :

0 0 , , , , ( ) ,
k k k l l l l l k k k k k k k k k k k k k k k k l l k l k k k k k k M T T NB v s s m m v NB v s s m m m m T m T s s m m s s s m s v NB v s m s m s ′ ′ ∈ ′ ′ ′ ′ < = ≤ ≤ ′ ′ ≤ ∆ ≤ - ′ ∆ ≤ ∆ + ∀ ∈ ′ ′ ∆ + + ≤ ∆ Given Find Maximize s.t. ( ) , , ( )
k l l k m s v NB v + ∀ ∈
To solve this problem, each node only needs to gather the pre-allocated slots, which consist of the head, body and tail periods, from all neighbors. This problem can be easily solved by a linear search. Since more than one region would meet the above requirements, choosing an appropriate one as the pre-allocation is also a problem in the pre-allocation scheme. In this paper, we choose pre-allocate slots in the longest available period for v k to achieve the objective of maximizing the m' k .

Any existing TDMA-based distributed slot allocation protocol can be applied to our pre-allocation scheme with a little modification where the allocated slots are represented by four parameters (s' k , s k , m k , m' k ). For example, the slot allocations in IEEE 802.16 are performed by a three-way handshake: request, grant and confirm. To apply our mechanism in IEEE 802. [START_REF] Gupta | The Capacity of Wireless Networks[END_REF], a node sends a request message containing the minimum and maximum slot requirements min max ( , )

On-The-Go Scheduling Scheme

In previous section, we introduced the pre-allocation scheme for each link v k . However, we still need an efficient scheduling scheme to select slots from the preallocated slots to transmit data in each frame. Therefore, we propose the on-the-go scheduling scheme that 1) chooses slots dynamically for transmissions without coordinating with other links or waiting for scheduling from a central server; and 2) prevents collisions between links and maximize the network throughput. Specifically, the on-the-go scheduling scheme assigns an index value to each slot and chooses slots according to the immediate slot requirement and index values.

Index values and transmission slots selection

In the following, we use x k to denote the vector of all index values of link v k , where x k (i) is the i-th element in x k and represents the index value of slot i of link v k . With our design, the index value of a slot in the body period and the idle period must be Adaptive On-The-Go Scheduling for End-to-End Delay Control in TDMA-based Wireless Mesh Networks 7 zero and infinite respectively. Each multi-access slot has a unique integer index value between 1 and k k m m ′ -. Let x k max (t) denote the maximum index value of slots that v k can transmit data in the frame t.

The Near-Body-First (NBF) policy

In our mechanism, the slot with smaller index value has higher priority to be selected to transmit data. The x k is used to prevent transmission collisions and maximize the network throughput. This is achieved by the Near-Body-First policy. An index value assignment x k of v k is a Near-Body-First (NBF) index assignment if the index values of any two adjacent slots i and j, j=(i+1) mod M, of v k satisfy the constraints:

( ) ( ) ( ) ( ) ,if , ,if , head k k k tail k k k x i x j i j Z x i x j i j Z  > ∈   < ∈   (6)
Theorem 1. Given the head, body, and tail periods of each link and an index value assignment x k whose expected throughput for each link v k is θ k , we can always find an NBF index assignment x' k such that the expected throughput of each link v k with x' k is higher than or equal to θ k .

The Theorem 1 can be proved by iteratively exchanging the index values of any two adjacent slots that violate the NBF policy and ensuring that each iteration will not diminish the expected throughput of each link. The detail of the proof is omitted here due to the limitation of paper length.

From Theorem 1, we know that the NBF index assignments can provide the highest expected throughput for all links. However, given the head, body and tail periods of a link v k , there are many index assignments belonging to NBF index assignments. To dynamically calculate the index assignment for each link according to the links channel conditions to avoid collisions is a major concern of the on-the-go scheduling scheme. In this paper, we define the parameters w k h2t (t), called the weight of the head over the tail, for the index assignment of v k in frame t as follows:

2 ( 1) ( ) ( 1
)
head h t k k tail k g t w t g t δ δ -+ = -+ (7)
where g k head (t-1) and g k tail (t-1) are the numbers of packets transmitted successfully during the head and the tail periods of v k in the previous frame. The parameter δ is a very small value to avoid the illegal division by zero and let w k h2t (t) be 1 when both g k head (t-1) and g k tail (t-1) are equal to 0. Since a link v k will compete for transmission opportunities with different neighbors in its head and tail periods, it will experience different interferences in the two periods.

The parameter w k h2t (t) represents the relation of the interferences in head period and that in tail period. A higher value of w k h2t (t) indicates that the link v k has fewer collisions during its head period. Thus, we calculate the index value of each multiaccess slot in frame t as follows:

( ) ( ) ( ) ( ) 2 2 , min Z , ( ( , ) 1) / ( ) , if i Z ( ) , min , ( ) ( , ) , if i Z tail h t head k k k k k k head h t tail k k k k k k k i s i s w t x i s m i Z w t s m i    ∆ + ∆ - ∈    =  ∆ + + ⋅ ∆ + ∈   ( 8
)
where |Z k tail | and |Z k head | are the lengths of the tail and head periods of v k . Fig. 4 shows three examples of index assignments in which w k h2t (t) is infinite, 0 and 2 respectively.

2 1 0 0 0 0 6 7 8 ∞ ∞ ∞ 3 ∞ 9 10 4 5 ∞ ∞ ∞ 2 ( ) h t k w t → ∞ 2 ( ) 0 h t k w t → 7 6 0 0 0 0 1 2 3 ∞ ∞ ∞ 8 ∞ 4 5 9 10 ∞ ∞ ∞ 2 ( ) 2 h t k w t = 2 1 0 0 0 0 3 6 8 ∞ ∞ ∞ 4 ∞ 9 10 5 7 ∞ ∞ ∞ s' k s k s k +m k s' k +m' k

Congestion control

Although the design of w k h2t (t) reflects the difference between interferences in the head and tail periods, simply adjusting the index values of each slot can not avoid collisions when the slot requirement is large because the link will tend to use all the multi-access slots to transmit data. Therefore, we incorporate a congestion control mechanism into our on-the-go scheduling scheme. The congestion control is achieved by introducing the parameter x k max (t) and limiting the link v k can only transmit data in slots with index values smaller than x k max (t). If collisions occurred in the transmissions of v k in the previous frame, the value of x k max (t) is reduced to slow down the transmission rate of v k as follows: max ( )

( 1) 1

head tail k k k x t g t g t = -+ -- (9)
If there were no collisions in the transmissions of v k in the previous frame, we gradually raise the transmission rate by increasing the x k max (t):

max max ( ) ( 1) 1 k k x t x t = -+ (10)

Drop tail policy

The drop tail policy is another collision avoidance mechanism. Its function is to "stop all the transmissions of v k after a collision of v k has occurred during its tail period until the next head period begins." The concept of the drop tail policy is based on the property that the transmissions of v k during its tail period will only be affected by the transmissions of the neighbors of v k in their head periods. Moreover, according to the NBF policy, once a slot i is selected to transmit data by v k , the slots following slot i in the head period of v k will also be selected to transmit data. Therefore, if a collision occurs in the tail period of v k , the residual slots in the same tail period will fail. We can discard the transmissions in these slots that the v k and its neighbors will have lower collision probabilities.

Adaptive On-The-Go Scheduling for End-to-End Delay Control in TDMA-based Wireless Mesh Networks 9

Performance Evaluation

In this section, we evaluate the performance of the proposed two-stage slot allocation mechanism and on-the-go scheduling scheme by simulations. All of the simulations were performed using the ns-2 network simulator [START_REF]Network Simulator ns-2[END_REF] with TDMA enhancements in the MAC layer of IEEE 802.11. We show the benefit of the proposed mechanism by comparing with other two types of transmission schemes: the IEEE 802.11, and the traditional conflict-free TDMA-based schemes with average-rate and peak-rate slot allocations, denoted as TDMA-avg and TDMA-peak, respectively. The system configuration of our simulations is listed in Table I. All flows use the UDP as their transport protocol. The period of each simulation is 3000 seconds. The distance between the source and destination of each link is 200 meters in all scenarios.

Chain topology

In this scenario, we examine the cases of one flow and multi-flows on a 6-hop chain topology as shown in Fig. 5(a). We first consider the wireless network with a 6-hop flow. We evaluate the performance of our mechanism by increasing the average sending rate of the 6-hop flow and Fig. 5(b), 5(c) and 5(d) show the simulation results. We can see that our on-the-go (OTG) scheduling provide higher end-to-end throughput than IEEE 802.11 and TDMA-avg as shown in Fig. 5(c). Although TDMA-peak has shorter end-to-end delay than OTG, but it can not admit the flow with average sending rate more than 1200 Kbps while OTG can allow the sending rate of the 6-hop flow up to 1600 Kbps. Note that in the cases of TDMA-peak and OTG with sending rate more than their schedulable limits, we still admit the flow but only the maximum schedulable slots are allocated. The TDMA-avg has shorter average end-to-end delay when traffic load is high because most packets are dropped by the interface queue. We also show the performance of our enhancements, congestion control and drop tail, for on-the-go scheduling in Fig. 5(d). The results show that the two enhancements can reduce the collision probability of the on-the-go scheduling when traffic load is high.

In the second part of this scenario, we consider multiple flows with different path lengths. There are one 6-hop, two 3-hop and six 1-hop flows, as in Fig. 5(a). We fix the sending rates of 1-hop and 3-hop flows to 512Kbps while the sending rate of the 6-hop flow varies from 200Kbps to 1000Kbps in this simulation. We show the average end-to-end delay of each flow and collision probability under IEEE 802.11 and OTG in Fig 5(e) and 5(f). The results of TDMA-peak and TDMA-avg are not presented because the comparisons of their performances with OTG are similar as in the scenario of single flow shown in Fig. 5(b). We can see that OTG provides constant end-to-end delay for each flow when the requests are schedulable. The average scheduling delay [START_REF] Djukic | Delay Aware Link Scheduling for Multi-Hop TDMA Wireless Networks[END_REF] of each hop is about 30ms in our simulation, which results in about 150ms and 60ms end-to-end scheduling delay to 6-hop and 3-hop flows. If we only consider the queueing delay, the on-the-go scheduling performs fairly on flows with different hops.

Mesh topology

In this section, we consider four flows in a wireless mesh network as shown in Fig.

Conclusion and Discussion

In this paper, we proposed a two-stage slot allocation mechanism on TDMA-based transmission protocols in WMNs. The mechanism allocates not only conflict-free slots but also multi-access slots to each link compared to traditional one-stage slot allocation algorithms. An adaptive on-the-go scheduling for the two-stage slot allocation mechanism is also introduced to dynamically schedule the transmission time slots within the multi-access slots for each link. The on-the-go scheduling scheme selects slots for transmission and avoid collisions without coordinating with other links that it can afford rapidly adjusting the slot allocation to support real-time applications with variable-bit-rate traffic. The simulation results also show that our on-the-go scheduling scheme achieves higher utilization than IEEE 802.11 MAC protocol and performs more flexibly and efficiently than traditional TDMA-based slot allocations.

Fig. 1 .

 1 Fig. 1. The framework of the two-stage slot allocation mechanism with On-The-Go scheduling.

Fig. 2 .

 2 Fig. 2. The head, body and tail periods of a link.

Fig. 3 .

 3 Fig. 3. The illustration of retrieving the frame to find the feasible allocations.

Fig. 4 .

 4 Fig. 4. Three examples of NBF index assignment.

FlowFlowFig. 5 .

 5 Fig. 5. The topology and simulation results in the 6-hop chain wireless network.

  6(a). We fixed the sending rate of flow 1, 2 and 4 to 1000Kbps and varied the sending rate of flow 3 from 100Kbps to 1000Kbps to examine the performance of flows with different channel conditions. The results of average end-to-end delay of each flow and collision probability with different mechanisms are shown in Fig.6(b), 6(c) and 6(d).Adaptive On-The-Go Scheduling for End-to-End Delay Control in TDMA-based Wireless Mesh Networks 11From the results, we can see that OTG preserves the property of isolation between flows that, as shown inFig 6(b), the end-to-end delays of OTG flows maintain constant when the rate of flow 3 increases. Similarly, the TDMA-peak also provides isolation between flows but it can only admit the flow 3 with traffic load less than 300Kbps. We have not shown the collision probability of TDMA-avg and TDMApeak in Fig.6(d) because their collision probabilities all equal to zero. The drop tail policy only has little improvement because almost all collisions are occurred in the last slot in the tail period of each link when traffic load is not heavy.

Fig. 6 .

 6 Fig. 6. The topology and simulation results of four flows in a 4x4 grid wireless network.

  Scheduling for End-to-End Delay Control in TDMA-based WirelessWe model a WMN by a directed network graph NG=(N,V), where N={n a ,n b ,n c ,…} is the set of nodes and V={v 1 ,v 2 ,v 3 ,…} is the set of directed links. In a WMN, a node n a can transmit data to another node n b if n b is in the transmission range D TR of n a . A link from node n a to node n b means the node n a has the ability to transmit data to node n b .

						Mesh Networks	3
	2 Network and System Models
	Two links in a WMN will interfere with one another if they can not transmit packets
	simultaneously. In this paper, we adopt the protocol model proposed in [16] as our
	interference model. Under the model, a transmission from node n a to node n b is
	successful if and only if there is no other node within the interference range D IR of n b
	transmitting data at the same time. With the protocol model, we can construct a
	undirected contention graph CG=(V,E), where V is the same as above and an edge
	(v k ,v l ) is in E if links v k and v l can not transmit data simultaneously. Then, we define
	link v k 's neighbor set as NB(v k )={v l | (v k ,v l ) ∈E}.
	A real-time application flow f i in a WMN consists of a routing path, defined as
	Path i ={v k | v k ∈V, f i passes through the link v k }, and the range of the flow's demand
	rate min max , , ( , i k i k r r	)	at all v k ∈Path i , where min , i k r	and max , i k r	are, respectively, the minimum
	and maximum demand rates of f i at link v k . Then, the bandwidth requirement of link
	v k is bound by min max ( , k k R R	)	, where min k R is the summation of min , i k r of all flows that pass
	through v k ; max k R	can be obtained in a similar manner.

Table 1 .

 1 The system Configuration of our simulations.

	Parameter	Value
	Channel Bandwidth	11Mbps
	Interface Queue Size	100 packets
	Packet Size	1500 bytes
	Flow type	Exponentially distributed ON/OFF model
		Average ON/OFF period : 1000/1000 ms.
	Transmission/Interference Range	250m/420m
	TDMA slot/frame duration	1.2 ms/60 ms (50slots per frame)

The project was partly supported by NSC Taiwan under contract NSC98-2221-E-001-005-MY3.