INFOCOM 2015 论文列表

The continual proliferation of mobile devices has stimulated the development of opportunistic encounter-based networking and has spurred a myriad of proximity-based mobile applications. A primary cornerstone of such applications is to discover neighboring devices effectively and efficiently. Despite extensive protocol optimization, current neighbor discovery modalities mainly rely on radio interfaces, whose energy and wake up delay required to initiate, configure and operate these protocols hamper practical applicability. Unlike conventional schemes that actively emit radio tones, we exploit ubiquitous audio events to discover neighbors passively. The rationale is that spatially adjacent neighbors tend to share similar ambient acoustic environments. We propose AIR, an effective and efficient neighbor discovery protocol via low power acoustic sensing to reduce discovery latency. Especially, AIR substantially increases the discovery probability of the first time they turn the radio on. Compared with the state-of-the-art neighbor discovery protocol, AIR significantly decreases the average discovery latency by around 70%, which is promising for supporting vast proximity-based mobile applications.

Over years, virtual backbone has attracted lots of attentions as a promising approach to deal with the broadcasting storm problem in wireless networks. One popular way to construct a quality virtual backbone is to solve the minimum connected dominating set problem. However, a virtual backbone computed in this way is not resilient against topology change since the induced graph by the connected dominating set is one-vertex-connected. As a result, the minimum k-connected m-dominating set problem is introduced to construct a fault-tolerant virtual backbone. Currently, the best known approximation algorithm for the problem in unit disk graph assumes k ≤ 3 and m ≥ 1 and its performance ratio is 280 when k = m = 3. In this paper, we use a classical result from graph theory, Tutte decomposition, to design a new approximation algorithm for the problem in unit disk graph for k ≤ 3 and m ≥ 3. In particular, the algorithm features with much simpler structure and much smaller performance ratio, e.g. nearly 66 when k = m = 3. We also conduct simulation to evaluate the performance of our algorithm.

The problem of scheduling transmission in single hop and multi-hop wireless networks with arbitrary topology under the physical interference model has been extensively studied. The focus has been on optimizing the efficiency of transmission parallelization through a minimum-frame-length schedule that meets a given set of traffic demands using the smallest number of time slots, each of which is associated with a set of compatible (according to the interference model) transmissions. This approach maximizes the resource reuse efficiency, but in general does not correspond to the best performance in terms of end-to-end packet delivery delay for multiple source-destination pairs, due to the inherent restriction of frame periodicity. In this paper, we study the problem of scheduling to minimize the end-to-end delay in wireless networks under the Signal to Interference plus Noise Ratio (SINR) constraints, and propose two schemes. The first scheme extends the minimum-frame-length approach with a phase of time slot ordering to account for the delay metric. The second scheme directly optimizes delay without the constraint of periodic framing. We propose novel mixed integer programming models for the two schemes and study their properties and complexity. Moreover, we present an efficient heuristic method that provides good quality solutions time-efficiently.

We study student performance prediction in Massive Open Online Courses (MOOCs), where the objective is to predict whether a user will be Correct on First Attempt (CFA) in answering a question. In doing so, we develop novel techniques that leverage behavioral data collected by MOOC platforms. Using video-watching clickstream data from one of our MOOCs, we first extract summary quantities (e.g., fraction played, number of pauses) for each user-video pair, and show how certain intervals/sets of values for these behaviors quantify that a pair is more likely to be CFA or not for the corresponding question. Motivated by these findings, our methods are designed to determine suitable intervals from training data and to use the corresponding success estimates as learning features in prediction algorithms. Tested against a large set of empirical data, we find that our schemes outperform standard algorithms (i.e., without behavioral data) for all datasets and metrics tested. Moreover, the improvement is particularly pronounced when considering the first few course weeks, demonstrating the “early detection” capability of such clickstream data. We also discuss how CFA prediction can be used to depict graphs of the Social Learning Network (SLN) of students, which can help instructors manage courses more effectively.

Millimeter-wave communication achieves multi-Gbps data rates via highly directional beamforming to overcome pathloss and provide the desired SNR. Unfortunately, establishing communication with sufficiently narrow beamwidth to obtain the necessary link budget is a high overhead procedure in which the search space scales with device mobility and the product of the sender-receiver beam resolution. In this paper, we design, implement, and experimentally evaluate Blind Beam Steering (BBS) a novel architecture and algorithm that removes in-band overhead for directional mm-Wave link establishment. Our system architecture couples mm-Wave and legacy 2.4/5 GHz bands using out-of-band direction inference to establish (overhead-free) multi-Gbps mm-Wave communication. Further, BBS evaluates direction estimates retrieved from passively overheard 2.4/5 GHz frames to assure highest mm-Wave link quality on unobstructed direct paths. By removing in-band overhead, we leverage mm-Wave's very high throughput capabilities, beam-width scalability and provide robustness to mobility. We demonstrate that BBS achieves 97.8% accuracy estimating direction between pairing nodes using at least 5 detection band antennas. Further, BBS successfully detects unobstructed direct path conditions with an accuracy of 96.5% and reduces the IEEE 802.11ad beamforming training overhead by 81%.

Prior studies show that repairing partially corrupted packets, instead of retransmitting them in their entirety, holds potential in improving the performance of 802.11 networks. However, the efficiency of existing packet recovery approaches is severely limited by various overhead associated to redundant transmission and repeated channel contention. In this paper, we propose CodeRepair, a practical coding-based protocol that recovers partially corrupted 802.11 packets without these pains. The design of CodeRepair is based on two novel ideas. First, CodeRepair pushes the limit of 802.11 PHY to piggyback parities in the padded bits of OFDM, obviating the need of transmitting extra information for error correction. Second, CodeRepair corrects errors at the PHY layer, which is significantly more efficient than traditional link-layer approaches. This is due to the fact that a single coded bit usually affects the decoding of a group of data bits in 802.11 convolutional code. As a result, CodeRepair can salvage a partially corrupted packet by correcting a small number of erroneous coded bits using the padded parities. To reduce computational cost of error recovery, CodeRepair employs single parity code for correcting coded bit errors. We propose several techniques to augment the error correcting capability of single parity code without compromising its computation efficiency. Our evaluation shows that CodeRepair recovers an average of 34% partially corrupted packets, and improves the end-to-end link goodput by 59% on lossy 802.11 links.

Due to the convenience, the data sharing in cloud computing via mobile devices has become more and more popular. However, data confidentiality and online computational cost still present practical concerns to the deployment of data sharing in cloud computing for mobile devices. Existing data sharing protocols in cloud computing either cannot support the flexible sharing style for the encrypted data, or suffer from massive online computational cost that scales with the complexity of the access policy. In this paper, to cope with these challenging concerns, we propose a new data sharing protocol for cloud computing by using a new cryptographic primitive named online/offline attribute-based proxy re-encryption and the transform key technique. To the best of our knowledge, the proposed data sharing protocol is the first one featuring with fine-grained access control, flexible sharing, data confidentiality, and minimum online computational cost on the user side at the same time. Furthermore, the proposed online/offline attribute-based proxy re-encryption scheme may be of independent interest. At last, extensive analysis shows that our proposed data sharing protocol is secure in terms of data confidentiality, and suitable for mobile devices in terms of online computational cost.

The recently proposed 3-Tier access model for Whitespace by the Federal Communications Commission (FCC) mandates certain classes of devices to share frequency bands in space and time. These devices are envisioned to be a heterogeneous mixture of licensed (Tier-1 and Tier-2) and unlicensed, opportunistic devices (Tier-3). The hierarchy in accessing the channel calls for superior adaptation of Tier-3 devices with varying spectral opportunity. While policies are being ratified for efficient sharing, it also calls for redesigning many common applications to adapt to this novel paradigm. In this paper, we focus on the ever-increasing demand for video streaming and present a methodology suitable for Tier-3 devices in the shared access model. Our analysis begins with a stress test of commonly adopted video streaming methods under the new sharing model. This is followed by the design of a robust MDP-based solution that proactively adapts to fast-varying channel conditions, providing better user quality of experience when compared to existing solutions, such as MPEG-DASH. We evaluate our solution on an experimental testbed and find that our MDP-based algorithm outperforms DASH, and partial information of Tier-2 dynamics improves video quality.

Datacenter demand response is envisioned as a promising tool for mitigating operational stability issues faced by smart grids. It enables significant potentials in peak load reduction and facilitates the incorporation of distributed generation. Monetary refund from the smart grid can also alleviate the cloud's burden in escalating electricity cost. However, the current demand response paradigm is inefficient towards incentivizing a cloud that runs over geo-distributed datacenters. Leveraging auction theory, this work presents an efficient incentive mechanism to elicit demand response from geo-distributed clouds. To determine the winning bids and their corresponding payments, the cloud that acts as the auctioneer needs to solve a set of winner determination problems that are highly challenging. By integrating techniques from the Gibbs sampling method and the alternating direction method of multipliers, we propose a decentralized algorithm for each datacenter to make autonomous decisions on winning bid selection and workload management, striking a balance among the economic efficiency, truthfulness and the computational efficiency. Through extensive trace-driven evaluations, we demonstrate that our incentive mechanism constitutes a win-win mechanism for both the geo-distributed cloud and the smart grid.

WiFi technology has fostered numerous mobile computing applications, such as adaptive communication, finegrained localization, gesture recognition, etc., which often achieve better performance or rely on the availability of Line-Of-Sight (LOS) signal propagation. Thus the awareness of LOS and Non-Line-Of-Sight (NLOS) plays as a key enabler for them. Realtime LOS identification on commodity WiFi devices, however, is challenging due to limited bandwidth of WiFi and resulting coarse multipath resolution. In this work, we explore and exploit the phase feature of PHY layer information, harnessing both space diversity with antenna elements and frequency diversity with OFDM subcarriers. On this basis, we propose PhaseU, a real-time LOS identification scheme that works in both static and mobile scenarios on commodity WiFi infrastructure. Experimental results in various indoor scenarios demonstrate that PhaseU consistently outperforms previous approaches, achieving overall LOS and NLOS detection rates of 94.35% and 94.19% in static cases and both higher than 80% in mobile contexts. Furthermore, PhaseU achieves real-time capability with millisecond-level delay for a connected AP and 1-second delay for unconnected APs, which is far beyond existing approaches.

The time variance of a channel is exploited in interference alignment techniques. However, in the case of static channels, these interference alignment techniques do not hold, specifically for single-antenna systems. In this paper, we introduce simple data processing techniques that enable us to create the effect of a time varying channel from the underlying static channel. We call this channel the shadow channel. We exploit the time-varying nature of the relative channels introduced by the shadow channel for interference alignment. We demonstrate the throughput benefits of this interference alignment technique for different topologies. This technique can be thought of as operating over the two dimensions of the complex space of typical communication systems. In this paper, we present the feasibility of interference alignment techniques for single antenna nodes in static channel. We establish bound on the throughput gain due to this technique. Finally, we implement interference alignment over the shadow channel on the NI PXIe 1082 based software defined radio. We achieve throughput gains of upto 1.44X over TDMA systems using this interference alignment technique and upto 1.61X when this technique is coupled with interference cancellation.

Network operators can and do deploy multiple routing control-planes, e.g., by running different protocols or instances of the same protocol. With the rise of SDN, multiple control-planes are likely to become even more popular, e.g., to enable hybrid SDN or multi-controller deployments. Unfortunately, previous works do not apply to arbitrary combinations of centralized and distributed control-planes. In this paper, we develop a general theory for coexisting control-planes. We provide a novel, exhaustive classification of existing and future control-planes (e.g., OSPF, EIGRP, and Open-Flow) based on fundamental control-plane properties that we identify. Our properties are general enough to study centralized and distributed control-planes under a common framework. We show that multiple uncoordinated control-planes can cause forwarding anomalies whose type solely depends on the identified properties. To show the wide applicability of our framework, we leverage our theoretical insight to (i) provide sufficient conditions to avoid anomalies, (ii) propose configuration guidelines, and (iii) define a provably-safe procedure for reconfigurations from any (combination of) control-planes to any other. Finally, we discuss prominent consequences of our findings on the deployment of new paradigms (notably, SDN) and previous research works.

TCP has been the dominant transport protocol for mobile internet since its origin. Its behaviors play an essential role in determining quality of service/experience (QoS and QoE) for mobile apps. While TCP has been extensively studied in a static, walking, or driving mobility, it has not been well explored in highspeed (> 200 km/h) mobility cases. With increasing investment and deployment of high speed rails (HSRs), a critical demand of understanding TCP performance under extremely high-speed mobility arises. In this paper, we conduct an in-depth study to investigate TCP behaviors on HSR. We collect 90 GB of measurement data on HSPA+ networks in Chinese high-speed trains with a peak speed of 310 km/h, along various routes (covering 5,000 km) during an 8-month period. We analyze the impacts of high-speed mobility and handoff on performance metrics including RTT, packet loss and network disconnection. Then we demystify the grand challenges posed on TCP operations (TCP establishment, transmission, congestion control and termination). Our study shows that performance greatly declines in HSR, where RTT spikes, packet drops and network disconnections are more significant and occur more frequently, compared with static, slowly moving or driving mobility cases. Moreover, TCP fails to adapt well to such extremely high-speed and yields severely abnormal behaviors, such as high spurious RTO rate, aggressive congestion window reduction, long delay of connection establishment and closure, and transmission interruption. All these findings indicate that extremely high-speed indeed poses a big threat to today's TCP and it calls for urgent efforts to develop HSR-friendly protocols and wireless networks to address even more complicated challenges raised by faster trains/aircrafts in the foreseeable future.

With the pervasion of mobile devices, crowdsourcing based received signal strength (RSS) fingerprint collection method has drawn much attention to facilitate the indoor localization since it is effective and requires no pre-deployment. However, in large open indoor environment like museums and exhibition centres, RSS measurement points cannot be collocated densely, which degrades localization accuracy. This paper focuses on measurement point collocation in different cases and their effects on localization accuracy. We first study two simple preliminary cases under assumption that users are uniformly distributed: when measurement points are collocated regularly, we propose a collocation pattern which is most beneficial to localization accuracy; when measurement points are collocated randomly, we prove that localization accuracy is limited by a tight bound. Under the general case that users are distributed asymmetrically, we show the best allocation scheme of measurement points: measurement point density ρ is proportional to (cμ)2/3in every part of the region, where μ is user density and c is a constant determined by the collocation pattern. We also give some guidelines on collocation choice and perform extensive simulations to validate our assumptions and results.

Information sharing is an important issue for stochastic bandit problems in a distributed setting. Consider N players dealing with the same multi-armed bandit problem. All players receive requests simultaneously and must choose one of M actions for each request. Sharing information among these N players can decrease the regret for each of them but also incurs cooperation and communication overhead. In this setting, we study how cooperation and communication can impact the system performance measured by regret and communication cost. For both scenarios, we establish a uniform lower bound to the regret for the entire system as a function of time and network size. Concerning cooperation, we study the problem from a game-theoretic perspective. When each player's actions and payoffs are immediately visible to all others, we identify strategies for all players under which co-operative exploration is ensured. Regarding the communication cost, we consider incomplete information sharing such that a player's payoffs and actions are not entirely available to others. The players communicate observations to each other to reduce their regret, however with a cost. We show that a logarithmic communication cost is necessary to achieve the optimal regret. For Bernoulli arrivals, we specify a policy that achieves the optimal regret with a logarithmic communication cost. Our work opens a novel direction towards understanding information sharing for active learning in a distributed environment.

Truthful auctions make bidders reveal their true valuations for goods to maximize their utilities. Currently, almost all spectrum auction designs are required to be truthful. However, disclosure of one's true value causes numerous security vulnerabilities. Secure spectrum auctions are thus called for to address such information leakage. Previous secure auctions either did not achieve enough security, or were very slow due to heavy computation and communication overhead. In this paper, inspired by the idea of secret sharing, we design an information-theoretically secure framework (ITSEC) for truthful spectrum auctions. As a distinguished feature, ITSEC not only achieves information-theoretic security for spectrum auction protocols in the sense of cryptography, but also greatly reduces both computation and communication overhead by ensuring security without using any encryption/description algorithm. To our knowledge, ITSEC is the first information-theoretically secure framework for truthful spectrum auctions in the presence of semi-honest adversaries. We also design and implement circuits for both single-sided and double spectrum auctions under the ITSEC framework. Extensive experimental results demonstrate that ITSEC achieves comparable performance in terms of computation with respect to spectrum auction mechanisms without any security measure, and incurs only limited communication overhead.

Multiple-Input Multiple-Output (MIMO) technology has become an efficient way to improve the capacity and reliability of wireless networks. Traditional MIMO schemes are designed mainly for the scenario of contiguous spectrum ranges. However, in cognitive radio networks, the available spectrum is discontiguous, making traditional MIMO schemes inefficient for spectrum usage. This motivates the design of new MIMO schemes that apply to networks with discontiguous spectrum ranges. In this paper, we propose a scheme called VSMC MIMO, which enables MIMO nodes to transmit variable numbers of streams in multiple discontinuous spectrum ranges. This scheme can largely improve the spectrum utilization and meanwhile maintain the same spatial multiplexing and diversity gains as traditional MIMO schemes. To implement this spectral-efficient scheme on cooperative MIMO relays in cognitive radio networks, we propose a joint relay selection and spectrum allocation algorithm and a corresponding MAC protocol for the system. We also build a testbed by the Universal Software Radio Peripherals (USRPs) to evaluate the performances of the proposed scheme in practical networks. The experimental results show that VSMC MIMO can efficiently utilize the discontiguous spectrum and greatly improve the throughput of cognitive radio networks.

Discrete beeping is an extremely rigorous local broadcast model depending only on carrier sensing. It describes an anonymous broadcast network where the nodes do not need unique identifiers and have no knowledge about the topology and size of the network. Within such a model, time is divided into slots, and nodes can either beep or keep silent at each slot. We consider the problem of constructing a minimum dominating set (MDS) and a minimum connected dominating set (MCDS), respectively, under the discrete beeping model in this paper. By assuming that an upper bound N of the network size is known, we first propose and analyze a distributed synchronous algorithm termed BMDS for constructing a minimum dominating set (MDS) and then propose a distributed synchronous algorithm BCDS for CDS construction based on a maximal independent set (MIS) algorithm and a weakly CDS (WCDS). To our best knowledge, we are the first to study the MCDS construction under the discrete beeping model. We prove that the time complexity of BMDS is O(log2N) rounds with constant approximation ratio of at most 2, and BCDS can converge to a CDS within O(log3N) rounds.

Video streaming on smartphone consumes lots of energy. One common solution is to download and buffer future video data for playback so that the wireless interface can be turned off most of time and then save energy. However, this may waste energy and bandwidth if the user skips or quits before the end of the video. Using a small buffer can reduce the bandwidth wastage, but may consume more energy and introduce rebuffering delay. In this paper, we analyze the power consumption during video streaming considering user skip and early quit scenarios. We first propose an offline method to compute the minimum power consumption, and then introduce an online solution to save energy based on whether the user tends to watch video for a long time or tends to skip. We have implemented the online solution on Android based smartphones. Experimental results and trace-driven simulation results show that that our method can save energy while achieving a better tradeoff between delay and bandwidth compared to existing methods.