Amortized Fairness for Drive-Thru Internet

Abstract

The drive-thru Internet is an effective mean to provide Internet access service for wireless sensor networks deployed on vehicles. In these networks, vehicles often experience different link qualities due to different relative positions to the access point. This makes fair and efficient system design a very challenging task. In traditional approaches, the network efficiency has to be greatly sacrificed to provide the fair share for vehicles with low link quality. To address this issue, we propose a novel amortized fairness MAC protocol. The basic idea is that vehicles with lower link quality can defer their fairness requests and let the lost fairness be “amortized” in the future when their links become the high quality. The amortized fairness MAC requires predictions of future link quality. For this, we fully exploit the inner and inter-AP correlations revealed from our extensive field studies and design a link quality prediction algorithm. Based on the predicted link quality, we formulate the optimal amortized fairness MAC as a convex programming problem, which can be solved with the desired precision in polynomial time. Extensive simulation on real traces shows that the amortized fairness MAC scheme is more efficient than the existing fairness schemes in terms of efficiency and fairness.

1. Introduction

Recent years, many wireless sensor networks (WSNs) have been deployed on vehicles [1, 2]. These systems require continuous access to the Internet for data collection. Cellular networks provide a universal access to the Internet, but its high cost and low throughput hinder their usage in reality. Recently, the vehicular drive-thru Internet networks [3, 4] are widely advocated to fulfill this need. Fixed wireless infrastructures such as the IEEE 802.11 access points (APs) are deployed along the roadside. WSNs nodes on vehicles access these APs occasionally when passing by. For example, CarTel [1] deploy IEEE 802.11b based sensor nodes to collect data as a car is driven. When the car enters the range of an AP, the data on cars is delivered to the Internet through the AP. In Beijing, many WiFi APs has been deployed in the downtown area, and the government recently initialed several projects to promote the Internet access for on-board wireless sensor networks.

Like in the traditional wireless local area networks (WLANs), in the drive-thru Internet the basic design goals are the throughput efficiency and fairness. We are in a dilemma when designing a fair and efficient drive-thru Internet, as it has been well known that these two objectives have an inherent trade-off. Vehicles may have different link qualities. Vehicles with a better link quality (e.g., higher signal noise ratio (SNR)) are more productive for the efficiency, while a fair AP access scheme has to allocate the transmission time to low quality vehicles to ensure the fairness, which surely will damage the throughput and efficiency.

In order to strike a better trade-off between efficiency and fairness, various fairness provisioning schemes have been proposed in WLANs (e.g., [5–7]) and in drive-thru Internet (e.g., [8, 9]). Most of these approaches provide instant fairness, in which only the present link qualities are exploited. In drive-thru Internet, vehicles typically experience highly dynamic link qualities, which enables more promising approaches. Rather than requesting the fairness immediately, a low quality vehicle may defer its requests on fairness and wait for a later time when it experiences high link qualities. In other words, its lost fairness is amortized to the future high link qualities, which may have a better price for the network efficiency. As a result, the impacts of low quality links can be largely alleviated by this scheme, which we call amortized fairness.

The amortized fairness highly relies on accurate prediction on the future link qualities, so that low quality vehicles will have better link qualities and their lost fairness will be paid back. As people often drive through familiar routes [10], the same set of APs are encountered frequently. Among different passes of this set of APs, strong correlations between link qualities in an AP (called inner AP correlation) and between neighboring APs (called inter-AP correlation) are observed. Exploiting the inner and inter-AP correlations, we design a link quality prediction algorithm. Then, based on the predicted link quality, we propose an amortized fairness MAC protocol which can intelligently leverage high link qualities in the future to amortize the deferred requests of fairness. The main contributions of this paper are summarized as follows.

• (1)

We conduct extensive field studies on this drive-thru Internet and reveal the strong inner and inter-AP correlations of links between vehicles and APs.

(2)

We design a link quality prediction algorithm for vehicles, whose prediction errors are proven to be bounded. Then, we formulate the optimal amortized fairness in vehicle drive-thru networks as a convex programming problem which can be solved in polynomial time.

(3)

We carry out extensive simulations on real trace to evaluate the proposed amortized fairness MAC protocol. The results show that the amortized fairness MAC outperforms existing fairness schemes. In terms of system throughput, the amortized fairness improves the traditional throughput-based and speed-based fairness by up to 2.5 times and improves the time-based fairness by 40%.

The rest of this paper is structured as follows. Section 2 will introduce the motivation of the amortized fairness with a simple example. In Section 3, we study the wireless link characteristics in the drive-thru Internet to reveal the inner and inter-AP correlations. The proposed amortized fairness MAC protocol is present in Section 4, including the system framework, link quality estimation algorithm, and amortized fairness scheduling algorithm. We evaluate the amortized fairness protocol in Section 5, and overview the related works in Section 6. In the end, a simple conclusion will be drawn in Section 7.

2. Motivations

In this section, we introduce the drive-thru Internet considered in this paper and use a simple example to motivate the amortized fairness.

2.1. Drive-Thru Internet

In this paper, we consider the drive-thru Internet scenario in a one-way road with multiple lanes, as shown in Figure 1. Along the road, there are many WiFi APs deployed by inhabitants, network providers, governments, and so on. Some of them can be accessed by vehicles called open AP, while others called private AP are inaccessible for requiring password or unconnected to the Internet. Vehicles backlog their sensor data and intermittently connect to the Internet through open APs along the road. Usually, one AP may cover several vehicles simultaneously. Vehicles connecting to the same AP contend the transmission opportunities for uploading data.

Figure 1

An illustration of vehicle drive-thru Internet.

2.2. Motivation Example

Consider a simple scenario in which three vehicles u, v, and w are passing through an AP. Suppose because of their dynamic link qualities, vehicles experience different data rates at different times, as illustrated in Figure 2. For example, at $t=[\mathrm{0,2}]$ , u can transmit at only 1 Mb/s, and the data rate improves to 5.5 Mb/s at [2, 4]. In the next, we give a detailed analysis on existing fairness provisioning protocols.

Figure 2

Motivation example.

The throughput-based fairness, providing by original IEEE 802.11 DCF, ensures that every node has the same probability to transmit. By this scheme, at $[\mathrm{0,1}]$ , both u and v can transmit 0.5 Mb data (i.e., 1 s × 1 Mb/s × $1/2$ = 0.5 M). Similarly, we can compute the throughput of u, v, and w at other time slots and the results are depicted in Figure 2(a). The system throughput is 9.1 M. The time-based fairness [5, 6] gives each user u a fair share of transmission time regardless the individual link qualities. For example, at [1, 2], both u and v share half of the airtime. So, u can transmit 0.5 M, and v can transmit 5.5 M in this second, as shown in Figure 2(b). The system throughput by time-based fairness is 20.5 M. The speed-based fairness [11] allocate, transmission probability based on the vehicle's speed. In this example, v and w have a doubled speed than u, so their transmission probabilities are doubled than u's. The individual throughput and the system throughput are shown in Figure 2(c).

Observing this example, we can find another more efficient and fair scheduling scheme. As depicted in Figure 2(d), u gives up its fairness requests in the first two seconds and exclusively transmits in [3, 4], and again gives up in [5, 6]. Vehicles v and w have a similar strategy. By this scheduling scheme, the system throughput is 35 M, and each user obtains roughly 1/3 of the system throughput. The essence of this new allocation strategy is that vehicles defer their requests on the fairness and let the future better shares to amortize the current fairness loss. We call this new allocation strategy amortized fairness. The amortized fairness pays the fair shares with a better price and thus can effectively improve the network efficiency.

The amortized fairness highly relies on accurate predictions on link qualities so that users can justly calculate a best timing of their fair shares. In the next section, we will investigate the characteristics of links in drive-thru Internet which can help us to predict the link qualities.

3. Wireless Link Characteristics in Drive-Thru Internet

Accurate link quality predictions are crucial for the effectiveness of the amortized fairness. In this section, we investigate the wireless link characteristics in drive-thru Internet through empirical studies. We will show that link qualities present strong inner and inter-AP correlations, which can be greedily exploited for predictions.

In our experiments, we employ one programmable open AP and five vehicle nodes. The hardware for the AP and vehicle nodes are similar. They are made of a small embedded computer with an 1.6 GHz processor, 1 GB RAM, a magnetic RS232 GPS receiver for localization, and an Atheros-based CardBus 802.11 a/b/g wireless card. Linux with kernel 2.6.18 and Madwifi 0.9.4 are used to drive the wireless card. For the open AP, the wireless card works in AP mode and works in managed mode for vehicle nodes. Our experiments are carried at a segment of Zhongguancun Road in Beijing about 2 km length. Vehicle nodes are driven through the experiment segment and log the GPS and visible APs SNR at rates of 1 Hz and 5 Hz, respectively. We achieve this high AP scanning rate by programming vehicle nodes to only scan at channel 1. In total, we collect the data sets of 53 passes and discover 892 roadside APs (only one is ours, and others are deployed already).

3.1. Notations

Most notations used in this paper have been summarized in Table 1. Due to the error of commercial off-the-shelf GPS device (averaging to about 20 m [12]), it is difficult to accurately map an SNR sample to the location where this SNR was measured. So, we divide the coverage of a roadside AP into small zones, as shown in Figure 1.

Table 1

Summary of notations.

Symbols associated with link quality
$x_{i,j}^{(p)}$	The average of link quality samples in the zone j when a vehicle passes the AP p ith time.
${\overrightarrow{x}}_i^{(p)}$	The link quality vector of a vehicle passing the AP p at the ith time, written as ${\overrightarrow{x}}_i$ when no confusion, ${\overrightarrow{x}}_i^{(p)}=〈x_{i,\mathrm{1}}^{(p)},x_{i,\mathrm{2}}^{(p)},\dots ,x_{i,K_p}^{(p)}〉$ , where $K_p$ is the number of zones.
${\bar{x}}_i^{(p)}$	The mean of the link quality vector, ${\bar{x}}_i^{(p)}=({\mathrm{1}/K}_p){\sum \mathrm{‍}}_{k=\mathrm{1}}^{K_p}{x}_i^{(p)}(k)$ .
${\overrightarrow{X}}^{(p)}$	The vector of link quality means of m passes, ${\overrightarrow{X}}^{(p)}=〈{\bar{x}}_{\mathrm{1}}^{(p)},\dots ,{\bar{x}}_m^{(p)}〉$ .
${\rho }_{\text{inner}}^{(i,j)}$	The inner AP correlation coefficient of two link quality vectors ${\overrightarrow{x}}_i$ and ${\overrightarrow{x}}_j$ .
${\rho }_{\text{inter}}^{(p,q)}$	The inter-APs correlation coefficient of two neighboring AP p and q.
Symbols associated with throughput
$s(u)$	Individual throughput of vehicle u, that is, the amount of data transferred during the pass of an open AP
$\overrightarrow{s}$	Individual throughput vector, $\overrightarrow{s}=〈s\left(\mathrm{1}\right),s\left(\mathrm{2}\right),\dots ,s(n)〉$ .

Definition 1.

Suppose that a vehicle passes a given AP p for the ith time, the vector of link qualities between the vehicle and the AP is defined as

$$\begin{array}{cc}& {\overrightarrow{x}}_i^{\left(p\right)}=〈x_{i,\mathrm{1}}^{\left(p\right)},x_{i,\mathrm{2}}^{\left(p\right)},\dots ,x_{i,K_p}^{\left(p\right)}〉,\end{array}$$

(1)

where $x_{i,k}^{(p)}$ , $k=\mathrm{1},\dots ,K_p$ is the average of SNR samples from AP p in the zone k at the ith pass, and suppose that the coverage of AP p is divided into $K_p$ zones. The AP id, p, may be ignored for the presentation simplicity when there is no confusion.

The mean of the link quality vector ${\overrightarrow{x}}_i^{(p)}$ can be calculated as follows:

$$\begin{array}{cc}& {\bar{x}}_i^{\left(p\right)}=\frac{\mathrm{1}}{K_p}\sum _{k=\mathrm{1}}^{K_p}{x}_{i,k}^{\left(p\right)}.\end{array}$$

(2)

Definition 2.

Suppose that a vehicle has passed an AP p for m times, the vector of link quality means is defined as

$$\begin{array}{cc}& {\overrightarrow{X}}^{\left(p\right)}=〈{\bar{x}}_{\mathrm{1}}^{\left(p\right)},{\bar{x}}_{\mathrm{2}}^{\left(p\right)},\dots ,{\bar{x}}_m^{\left(p\right)}〉.\end{array}$$

(3)

3.2. Inner AP Correlation

We first investigate correlations among link qualities of different passes for a given vehicle and our open AP. Figure 3(a) shows link quality samples of two passes against the distance between the vehicle and the open AP. The x-axis is the distance, and the y-axis is the SNR in dB. We can observe that the shape of these two curves are very similar. Link quality vectors of these two passes are shown in Figure 3(b). To quantify the similarity, we define the inner AP correlation coefficient of two link quality vectors ${\overrightarrow{x}}_i$ and ${\overrightarrow{x}}_j$ as follows:

$$\begin{array}{cc}& {\rho }_{\text{inner}}^{(i,j)}=\frac{{\sum }_{k=\mathrm{1}}^{K_p}(x_{i,k}-{\bar{x}}_i)(x_{j,k}-{\bar{x}}_j)}{\sqrt{{\sum }_{k=\mathrm{1}}^{K_p}{\left(x_{i,k}-{\bar{x}}_i\right)}^{\mathrm{2}}}\sqrt{{\sum }_{k=\mathrm{1}}^{K_p}{\left(x_{j,k}-{\bar{x}}_j\right)}^{\mathrm{2}}}}.\end{array}$$

(4)

The inner AP correlation coefficient of these two link quality vectors shown in Figure 3 is up to 0.89.

Figure 3

The SNR when a vehicle passes an AP twice.

To further explore characteristics of the inner AP correlation, we show the ${\rho }_{\text{inner}}^{(i,j)}$ of any two passes (i.e., pass i and j) in our 53 data set against the difference of link quality vector means (i.e., $|{\bar{x}}_i-{\bar{x}}_j|$ ) in Figure 4(a), and each dot represents one pair of passes. We can find that coefficients between different passes are pretty high when the difference of means is small, and a larger difference indicates a smaller coefficient. For example, when the difference is less than 2, the coefficients can be as high as 0.94 and the lowest one is 0.82. These results indicate that when appropriately scaled, link quality vectors of previous passes can be used to predict those of latter passes.

Figure 4

Inner AP correlation coefficients.

The CDF of any two link quality vector means difference is shown in Figure 4(b). We can find that the differences of link quality vector means are quite large. About half of the pass pairs have difference more than 5 dB. This conflict to existing measurement studies [3, 13], in which the link qualities vary a little among different passes of the same AP. This is because their experiments were carried out in carefully planned and static environments, while our experiments were carried out in a real environment of city road where the vehicles might take different lanes and have different densities of neighboring vehicles at each pass. Although these dynamic factors change much at different passes, they tend to be stable when the vehicle passes by adjacent APs and have a similar impact on link qualities between the vehicle and these adjacent APs. This is the essential reason of the inter-AP correlation, which will be introduced in the next subsection.

3.3. Inter-AP Correlation

The link qualities are not only affected by the static factors, such as distance and the hardware of transceivers, but also by some dynamic factors such as the lanes vehicles take, the kinds and density of neighboring vehicles. These dynamic factors tend to be stable when a vehicle passes adjacent APs, and they incur similar attenuations of link qualities between the vehicle and those adjacent APs. In this part, we investigate the inter-AP correlations of link qualities. Suppose that a vehicle passes two geographically adjacent APs p and q for m times. So, we have two link quality mean vectors, that is, ${\overrightarrow{X}}^{(p)}$ and ${\overrightarrow{X}}^{(q)}$ . The inter-AP correlation is defined as

$$\begin{array}{cc}& {\rho }_{\text{inter}}^{(p,q)}=\frac{{\sum }_{i=\mathrm{1}}^m({\bar{x}}_i^{\left(p\right)}-{\bar{X}}^{\left(p\right)})({\bar{x}}_i^{\left(q\right)}-{\bar{X}}^{\left(q\right)})}{\sqrt{{\sum }_{i=\mathrm{1}}^m{\left({\bar{x}}_i^{\left(p\right)}-{\bar{X}}^{\left(p\right)}\right)}^{\mathrm{2}}}\sqrt{{\sum }_{i=\mathrm{1}}^m{\left({\bar{x}}_i^{\left(q\right)}-{\bar{X}}^{\left(q\right)}\right)}^{\mathrm{2}}}},\end{array}$$

(5)

where the ${\bar{X}}^{(p)}=(\mathrm{1}/m){\sum ‍}_{i=\mathrm{1}}^m{\bar{x}}_i^{(p)}$ , and the ${\bar{X}}^{(q)}$ is calculated similarly.

Although many roadside APs are found in our experiments, most of them have a few samples of SNR at each pass. It means that these APs are far away from the experiment road. As a result, the link qualities between a vehicle and these APs are impacted by many other dynamic factors. These APs are less useful for the analysis of inter-AP correlation. So we just select the 100 best APs for our analysis (i.e., closest to the road). For each AP we find the most correlated AP and compute the largest inter-AP correlation coefficient. We sort these 100 APs by their largest inter-AP correlation coefficient, and the result is shown in Figure 5. We can find that among all 100 APs, 34 APs have a inter-AP correlation coefficient over 0.9, and 78 APs have the coefficient over 0.8. Since we do not know the locations of all APs, It is difficult to show the relation between the inter-AP correlation and the distance between a pair of APs. We use the location of the largest SNR to approximate the AP's location, and find that not all pairs of nearby APs are high correlated. However, due to the large amount of APs along the road, it is probable to find a high correlated nearby AP for each open AP in practice.

Figure 5

Inter-AP correlation.

4. Amortized Fairness Scheduling

In this section, we present the design of our amortized fairness scheduling protocol. First, we overview the system framework in brief. Then, we give detailed designs on the two entities involved in this protocol, that is, the vehicle part and the roadside AP part.

4.1. Overviews

The amortized fairness scheduling has a very simple system framework. Our design is on top of the CSMA/CA MAC protocols. Figure 6 draws the system framework of the amortized fairness MAC protocol. In general, it is realized by two entities. The vehicle nodes are responsible to collect the link quality measurements and GPS. These information will be stored in a local storage. Upon discovering a new open AP, vehicles retrieve the records and make an appropriate prediction for the future link quality vector within this AP. The vehicle will convert the link quality vector to a data rate vector according to an SNR-to-rate mapping (as shown in Table 2). This SNR-to-rate mapping is summarized from our field measurement experiments and is adopted by vehicle nodes for rate adaptation. Finally, the vehicle will deliver this data rate vector to the open AP.

Table 2

The mapping between link quality and the corresponding data rate.

Rate (Mb)	SNR (dB)
1	4+
2	8+
5.5	16+
11	21+

Figure 6

System framework of amortized fairness.

Collecting the data rate vectors from all vehicles in the communication range, the AP will compute the optimal access strategy with the highest network efficiency and fairness by amortizing the low quality user's fair share to a better timing when necessary. The AP will then convert the optimal strategy to the corresponding minimum contention windows sizes ( $cw$ ) in CSMA/CA and broadcast the $cw$ s to vehicles. The vehicles then make adequate adjustments on their minimum contention windows according to the $cw$ s.

4.2. Estimation of Link Quality Vector

In this section, we present the link quality vector estimation algorithm for vehicles. To get an accurate estimation on link qualities, we exploit the inner and inter-AP correlations which we observed in Section 3. In a nutshell, we use the inter-AP correlation to estimate the mean of link quality vector and use the inner AP correlation to get the “shape” of the link quality vector. By intelligently integrating these two, we can get an accurate estimation of the link quality vector.

Suppose that this is a vehicle u's mth pass through an open AP p. In other words, there are $m-$ 1 history records, and we need to predict the mth link quality vector, that is, ${\overrightarrow{x}}_m^{(p)}$ . Let $\mathrm{\Omega }$ denote the set of p's preceding nearby APs. And for each AP in $\mathrm{\Omega }$ , the vehicle u has passed it m times. Under this scenario, Algorithm 1 gives the pseudocode of the estimation algorithm. The algorithm inputs are the link qualities vectors of all APs in $\mathrm{\Omega }$ and AP p. The output is estimated link quality vector ${\widehat{\overrightarrow{s}}}_m^{(p)}$ for the open AP p. We first exploit the inter-AP correlation to estimate the mean of link quality vector ${\bar{x}}_m^{(p)}$ (from line 1 to line 9). For all AP in $\mathrm{\Omega }$ and p, the vectors of link quality means of the past $m-\mathrm{1}$ passes are computed from line 1 to line 3. In line 4, the inter-AP correlation coefficients between the AP p and each preceding AP are calculated, and we find out the most correlated preceding nearby AP, say the AP q. From line 5 to line 9, we adopt a simple linear model to predict the mean of link quality vector in the mth pass of the AP p, that is,

$$\begin{array}{cc}& {\widehat{\bar{x}}}_m^{\left(p\right)}=b·{\bar{x}}_m^{\left(q\right)}+a,\end{array}$$

(6)

where $b={\rho }_{\text{inter}}^{(p,q)}·{\sigma }^{(p)}/{\sigma }^{(q)}$ and $a={\bar{X}}^{(p)}-b·{\bar{X}}^{(q)}$ are two intermediate parameters for the linear prediction model.

Algorithm 1: Estimation of link quality vector.

Inputs: ${\overrightarrow{x}}_i^{(q)}$ , where $i\in \left[\mathrm{1},m\right]$ , $q\in \mathrm{\Omega }$

    ${\overrightarrow{x}}_i^{(p)}$ , where $i\in \left[\mathrm{1},m-\mathrm{1}\right]$

Outputs: Estimated link quality vector ${\widehat{\overrightarrow{x}}}_m^{(p)}$ .

 (1) for all $q\in \mathrm{\Omega }\cup \{p\}$ do

 (2)    ${\overrightarrow{X}}^{(q)}=〈{\bar{x}}_{\mathrm{1}}^{(p)},{\bar{x}}_{\mathrm{2}}^{(p)},\dots ,{\bar{x}}_{m-\mathrm{1}}^{(p)}〉$

 (3) end for

 (4) $q=\arg {\min }_q({\rho }_{\text{inter}}^{(p,q)})$ , $q\in \mathrm{\Omega }$

 (5) ${\sigma }^{(p)}=\sqrt{{\sum }_{i=\mathrm{1}}^{m-\mathrm{1}}\mathrm{‍}({\bar{x}}_i^{(p)}-{\bar{X}}^{(p)}{)}^{\mathrm{2}}}$

 (6) ${\sigma }^{(q)}=\sqrt{{\sum }_{i=\mathrm{1}}^{m-\mathrm{1}}\mathrm{‍}({\bar{x}}_i^{(q)}-{\bar{X}}^{(q)}{)}^{\mathrm{2}}}$

 (7) $b={\rho }_{\text{inter}}^{(p,q)}·{\sigma }^{(p)}/{\sigma }^{(q)}$

 (8) $a={\bar{X}}^{(p)}-b·{\bar{X}}^{(q)}$

 (9) ${\widehat{\bar{x}}}_m^{(p)}=b·{\bar{x}}_m^{(q)}+a$

 (10) $c={\widehat{\bar{x}}}_m^{(p)}$

 (11) $\pi =\arg {\min }_{\pi }(|c,{\bar{x}}_{\pi }^{(p)}|),\mathrm{1}\le \pi \le m-\mathrm{1}$

 (12) ${\widehat{\overrightarrow{x}}}_m={\overrightarrow{x}}_{\pi }+c-{\bar{x}}_{\pi }$

Next, we explore the inner AP correlation to find the shape of the link quality vector. Line 11 finds the pass π from previous $m-\mathrm{1}$ passes, the mean of whose link quality vector are closest to the predicted mean. We have observed in Section 3 that small difference on the means implies strong inner AP correlation, so the link quality vectors of the pass π and current pass m are strong correlated with high probability. The link quality vector of the pass m is predicted by adding the difference of means to the link quality vector of the pass π, that is,

$$\begin{array}{cc}& {\widehat{x}}_{m,k}^{\left(p\right)}=x_{\pi ,k}^{\left(p\right)}+{\widehat{\bar{x}}}_m^{\left(p\right)}-{\bar{x}}_{\pi }^{\left(p\right)},\hspace{1em}\mathrm{1}\le k\le K_p.\end{array}$$

(7)

For simplify, it can be rewrittne as

$$\begin{array}{cc}& {\widehat{\overrightarrow{x}}}_m={\overrightarrow{x}}_{\pi }+{\widehat{\bar{x}}}_m-{\bar{x}}_{\pi }.\end{array}$$

(8)

We analyze the accuracy of the link quality prediction algorithm in the appendix, and make a comparison with an average-based prediction algorithm. The analysis results show that our proposed algorithm is much better than the average-based prediction algorithm. This is also validated in our simulations in Section 5.1.

4.3. Amortized Scheduling

In this subsection, we present the amortized scheduling algorithm for the drive-thru Internet. We first introduce the goal of the amortized fairness protocol (i.e., maximizing the proportional fairness), then we formulate the optimal amortized scheduling problem.

4.3.1. Proportional Fairness

For fairness, we adopt proportional fairness model that has been widely used in recent works [14]. Suppose that there are n vehicles passing an open AP, and let $s(u)$ denote the total data transmitted by the vehicle u (called individual throughput). All vehicles' individual throughput can be expressed as a vector $\overrightarrow{s}$

$$\begin{array}{cc}& \overrightarrow{s}=〈s\left(\mathrm{1}\right),s\left(\mathrm{2}\right),\dots ,s\left(n\right)〉.\end{array}$$

(9)

An $\overrightarrow{s}$ is said proportionally fair if and only if for any other feasible solution $\overrightarrow{s^{\prime }}$ ,

$$\begin{array}{cc}& \sum _{u=\mathrm{1}}^N‍\frac{s^{\prime }\left(u\right)-s\left(u\right)}{s\left(u\right)}\le \mathrm{0}.\end{array}$$

(10)

In other words, any change in the solution $\overrightarrow{s}$ must have a negative relative change. It has been proved in [14] that a proportionally fair allocation can be obtained by maximizing the system utility $J(\overrightarrow{s})$ over the set of feasible solutions,

$$\begin{array}{cc}& J\left(\overrightarrow{s}\right)=\sum _{u=\mathrm{1}}^N‍\ln \left(s\left(u\right)\right).\end{array}$$

(11)

4.3.2. Scheduling Algorithm

The objective of amortized scheduling is to achieve proportional fairness for all vehicles in the coverage of an open AP, that is, $\max (J(\overrightarrow{s}))$ . In other words, we need to schedule the transmission of each vehicle, so that their individual throughput maximizes the system utility. Suppose that each vehicle has infinite data to upload, and packets transmitted by all vehicles are equally sized. The individual throughput is determined by the minimum contention window size $cw$ of the 802.11 DCF. So, the amortized scheduling problem is to determine the optimal $cw$ for each vehicle.

Divide the time into L slots, and suppose that current time is the kth slot. Due to the short communication range of AP, we suppose that vehicles pass through the coverage of an open AP with constant speed. In addition, we assume that all vehicles' data rate keeps unchanged in each slot. Using $r_{u,j}$ and ${\alpha }_{u,j}$ to denote the data rate and the transmission time of the vehicle u at time slot j, respectively. The expected individual throughput $s(u)$ can be expressed as

$$\begin{array}{c}s\left(u\right)=\sum _{j=\mathrm{1}}^{k-\mathrm{1}}‍{\alpha }_{u,j}{r}_{u,j}+\sum _{j=k}^L‍{\alpha }_{u,j}{\widehat{r}}_{u,j}\\ \hspace{1em}\hspace{0.17em}=S_u\left(k\right)+\sum _{j=k}^L‍{\alpha }_{u,j}{\widehat{r}}_{u,j},\end{array}$$

(12)

where $S_u(k)$ is the amount of data that has already been transferred by vehicle u, and ${\sum }_{j=k}^L‍{\alpha }_{u,j}{\widehat{r}}_{u,j}$ is the amount of data that will be transferred by this vehicle. In order to provide the proportional fairness, we need to maximize the system utility function. So, we formally define the optimal amortized fairness scheduling problem as a convex programming problem as follows:

$$\begin{array}{l}\hspace{1em}\hspace{1em}\max \hspace{1em}\sum _{u=\mathrm{1}}^N‍\ln \left(S_u\left(k\right)+\sum _{j=k}^L‍{\alpha }_{u,j}{\widehat{r}}_{u,j}\right)\\ \text{subject}\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{to}\hspace{1em}\forall u,j\ge k,\hspace{1em}\mathrm{0}\le {\alpha }_{u,j}\le T\\ \phantom{\text{subject}\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{to}}\hspace{1em}\forall j\ge k,\hspace{1em}{\sum }_{u=\mathrm{1}}^n‍{\alpha }_{u,j}\le T,\end{array}$$

(13)

where T is the length of a time slot. The first constraint says that the transmission time of any vehicle in any time slot cannot be longer than the time slot. The second one ensures that the sum of all the transmission time of vehicles in any time slot is no longer than the time slot.

Convex programming problem can be solved to the desired precision in polynomial time [15]. The fractional solution of ${\alpha }_{u,j}$ for each vehicle u in time slot j is an exact solution for transmission scheduling. In CSMA wireless networks, the transmission time is mainly controlled by the minimum contention window size $cw$ . In order to grant the throughput according to the solution, we calculate the minimum contention window size for each vehicle according to its ${\alpha }_{u,j}$ and ${\widehat{r}}_{u,j}$ . Let $c{w}_{u,j}$ be u's minimum window size at the time slot j. So, we have

$$\begin{array}{cc}& c{w}_{\mathrm{1},j}:\cdots :c{w}_{n,j}=\frac{\mathrm{1}}{{\alpha }_{\mathrm{1},j}{\widehat{r}}_{\mathrm{1},j}}:\cdots :\frac{\mathrm{1}}{{\alpha }_{n,j}{\widehat{r}}_{n,j}}\end{array}$$

(14)

for all ${\alpha }_{u,j}{\widehat{r}}_{u,j}>\mathrm{0}$ .

The default minimum contention window size of the IEEE 802.11b is 32. For coexisting with other IEEE 802.11 protocol, we set the average of all vehicles' minimum contention window size also to be 32. As a result, we have

$$\begin{array}{cc}& c{w}_{u,j}=\frac{\mathrm{32}{n}_j}{{\alpha }_{u,j}{\widehat{r}}_{u,j}}{\left(\sum _u^{n_j}‍\frac{\mathrm{1}}{{\alpha }_{u,j}{\widehat{r}}_{u,j}}\right)}^{-\mathrm{1}},\end{array}$$

(15)

where $n_j$ is the number of vehicles satisfying ${\widehat{\alpha }}_{u,j}{\widehat{r}}_{u,j}>\mathrm{0}$ . For the vehicle whose ${\widehat{\alpha }}_{u,j}{\widehat{r}}_{u,j}$ is zero, the $c{w}_{u,j}$ is set to be a default large value.

5. Performance Evaluation

We have implemented a simulator to simulate the drive-thru Internet scenario with 1 open AP and 20 vehicles. In order to emulate the link qualities when a vehicle drives through the open AP, for each vehicle we randomly choose link quality traces of m passes from the data set collected in Section 3, where m is a control parameter. Suppose that vehicles have passed the open AP $m-\mathrm{1}$ times and are going to pass the AP for the mth time. To emulate the mobility of vehicles, we assign a speed and entering time of AP for each vehicle to simulate its mth pass of this AP. The speed is randomly chosen among $[v_{\min },v_{\max }]$ , where $v_{\min }$ and $v_{\max }$ are both parameters. We suppose that vehicles enter the open AP according to the Poisson process with a parameter λ.

We compare the proposed amortized fairness MAC protocol with three existing fairness provisioning schemes, that is, throughput-based fairness, time-based fairness, and speed-based fairness. The former two are widely studied in the WLAN, and the last one is a recent work in the drive-thru Internet.

• (i)

Throughput-based fairness is naturally provided by the current IEEE 802.11 DCF protocol. It assigns each node, regardless the link quality of nodes, the same probability to access the AP. As a result, different nodes are likely to transmit the same amount of packets in average.

(ii)

Time-based fairness grants each node the same amount of the transmission time rather than the probability of the transmission. In this scheme, high quality nodes can transmit more data.

(iii)

Speed-based fairness [9] assigns the transmission probability based on the user's speed. A faster vehicle will be granted with high transmission probability because of its shorter resident time, and vice versa for slower vehicles.

5.1. Accuracy of Link Quality Prediction

We first evaluate the accuracy of the link quality prediction algorithm. It is affected by the amount of link quality vectors which have been recorded (i.e., $m-\mathrm{1}$ ). We vary the parameter m from 2 to 20 and adopt the average error to quantify the prediction accuracy which is defined as

$$\begin{array}{cc}& \sqrt{\frac{{\sum }_{k=\mathrm{1}}^{K_p}{\left({\widehat{x}}_{m,k}^{\left(p\right)}-x_{m,k}^{\left(p\right)}\right)}^{\mathrm{2}}}{K_p}}.\end{array}$$

(16)

For each m, the simulation is run 100 times and the mean of the average error is depicted in Figure 7. The 90% confidence interval is depicted by an error bar in the figure. When $m=2$ (i.e., there is only one past pass available for prediction), the inter-AP correlation coefficient cannot be calculated. In this case, we use the static prediction scheme as ${\widehat{\overrightarrow{x}}}_{\mathrm{2}}^{(p)}={\overrightarrow{x}}_{\mathrm{1}}^{(p)}$ .

Figure 7

Average error under different m.

From Figure 7, we observe that when m is small the prediction error is increasing with the m. This is because that with small m ( $m=3$ and $m=4$ ) the inner-AP correlation of sample set may severely deviate from its true value, incurring large prediction errors. As m continuously increases, the errors begin to reduce with better stability. With more than 15 history records, the errors are stabilized to about 0.28. Fewer further improvements are observed with more records. As there is a direct map from the link quality to the corresponding data rate, and the SNR-based data rate adaption techniques are quite mature, we believe the obtained data rate vector will have a similar accuracy.

5.2. Efficiency and Fairness Evaluations

We compare the amortized fairness scheduling protocol with the three existing fairness provisioning schemes, the throughput-based fairness, time-based fairness, and speed-based fairness. Figure 8 shows the individual throughput of each vehicle by these four fairness schemes under different arrival rate and speed of vehicles. The vehicles are sorted by their individual throughput in increasing order. The x-axis is the index of vehicles, and the y-axis is the obtained individual throughput $s(u)$ . In general, amortized fairness outperforms all the others in all scenarios.

Figure 8

Individual throughput comparison.

For the case of the middle vehicle arrival rate $\lambda =\mathrm{0.5}$ and middle vehicle speed $v_{\max }=\mathrm{20}\hspace{0.17em}\text{m}/\text{s}=\mathrm{72}\hspace{0.17em}\text{km}/\text{h}$ (Figure 8(a)), throughput- and speed-based fairness perform similarly. Time-based fairness has about 100% improvements than them, and the amortized fairness has about 100% further improvements. For example, the 10th individual throughput in these four schemes are 1.9 MB, 1.9 MB, 3.7 MB, and 5.5 MB, respectively. When vehicles have the same speed to pass through the APs (Figure 8(b)), speed-based fairness will become the traditional throughput-based fairness. They have the similar performance.

When we reduce the vehicle arrival rate to $\lambda =\mathrm{0.1}$ and increase the range of speed $v_{\min }=\mathrm{5}$ and $v_{\max }=\mathrm{30}$ (Figure 8(c)), the difference between vehicles' residence times increases and the system is under an under-utilized setting. In that scenario, throughput fairness cannot be aware of the huge difference between vehicles' throughput and becomes fairly unfair. The maximal individual throughput is 48 MB, and the minimal is only 1 MB. Other two existing algorithms are similar. To the contrast, amortized fairness can intelligently exploit the link dynamics and achieve a better fairness and efficiency. We further increase the user arrival rate to 1 (Figure 8(d)). In that case, more users contend the AP simultaneously. So, the traffic of users are lower than the other three cases. Again, we observe the significant improvement of amortized fairness compared with others.

Figure 9 shows the average system throughput of these four fairness provisioning schemes under four previous scenarios. In all cases, amortized fairness exhibits significant outperformance. In the scenarios of A, B, and D, amortized fairness improves the total throughput by about 2.5 times compared with throughput- and speed-based fairness and improves over 40% compared with time-based fairness. In the case C, the improvements are 90% and 30%, respectively.

Figure 9

The average system throughput of different schemes under four scenarios.

6. Related Work

Many works have demonstrated the feasibility of IEEE 802.11 AP-based drive-thru Internet [3, 4]. The authors of [3, 13] have extensively measured the link quality between the vehicle and the roadside AP. They suggest that the link quality varies when a vehicle passes an AP, and the link quality becomes better in entering phase, while becomes worse in leaving phase. Our experiments get a consistent result about the variance course of link quality. In addition, by comparing a vehicle's link qualities at different passes of an AP, we found that the link qualities of two passes over a same AP are correlated (called inner AP correlation), and the mean of link quality when a vehicle passed some adjacent APs is also correlated (called inter-AP correlation).

For the variance of link qualities in drive-thru Internet, when multiple users share an AP simultaneously, it will lead to a dilemma problem of trade-off between efficiency and fairness. The original IEEE 802.11 DCF achieves the same throughput for nodes with different link qualities. It is notorious for the performance anomaly, because it damages the throughput of high quality users severely. Time-based fairness schemes [5, 6] are proposed to alleviate this anomaly by assigning equal transmission time to each node.

In the drive-thru Internet system, Hadaller et al. [13] first consider performance anomaly in drive-thru Internet and propose a greedy algorithm where only nodes with the best SNR are allowed to transmit. This simple scheme can achieve the maximum system throughput, but it incurs a poor fairness. Luan et al. [8] develop an accurate model to investigate the performance of IEEE 802.11 DCF in the drive-thru Internet. By knowing the node mobility and the link rate previously, they configure the minimum contention window size to maximize the system throughput while guaranteeing a certain lower bound of individual throughput for each vehicle. However, the link rate is very difficult to predict due to high environment dynamic. So, the performance will fail to meet their promise in practice.

The diversity of vehicle speed also leads to fairness problem in the drive-thru Internet. because vehicles with different speeds have their different limited time to communicate with AP. The author in [9] proposed MAC scheme to change the minimum contention window size according to vehicles' speed, so that fast vehicles can transfer the same amount of data as slow vehicles. However it has a low efficiency for the performance anomaly. Furthermore, this scheme also supposes that the link rate is known previously.

In this paper, we aim to an efficient and fair drive-thru MAC scheme, namely, we need to handle the performance anomaly of IEEE 802.11 DCF as well as the diversity of vehicle speed. Contrary to existing theoretical works in the drive-thru networks [8, 9], we exploit link correlations to accurately predict the link rate, instead of assuming that the link rate is known previously. Furthermore, rather than requesting the fairness immediately as all above works do, our amortized fairness protocol defers the fairness requests of low quality vehicles and amortized the loss of fairness over future high link qualities. So, the impacts of low quality links can be largely alleviated and the fairness is guaranteed as well.

7. Conclusion

In this paper, we study the fairness and efficiency issues in the drive-thru Internet networks. Different from the traditional fairness provisioning approaches, in this paper, we propose a novel amortized fairness scheduling protocol, which takes the future opportunity as an advantage. It allows low quality vehicles to defer their fairness requests and claim them back at a better timing when their link become high quality. To exploit such future opportunities well, we investigate the inner and inter-AP correlations between wireless links through extensive field studies. We design a link quality prediction algorithm and an amortized fairness scheduling algorithm. The prediction algorithm is proven to have a bounded performance. We conduct trace-driven simulations for performance evaluations and the results demonstrate supreme performance gains against existing methods in all simulation scenarios.