In cooperative multi-agent reinforcement learning, the outcomes of agent-wise policies are highly stochastic due to the two sources of risk: (a) random actions taken by teammates and (b) random transition and rewards. Although the two sources have very distinct characteristics, existing frameworks are insufficient to control the risk-sensitivity of agent-wise policies in a disentangled manner. To this end, we propose Disentangled RIsk-sensitive Multi-Agent reinforcement learning (DRIMA) to separately access the risk sources. For example, our framework allows an agent to be optimistic with respect to teammates (who can prosocially adapt) but more risk-neutral with respect to the environment (which does not adapt). Our experiments demonstrate that DRIMA significantly outperforms prior state-of-the-art methods across various scenarios in the StarCraft Multi-agent Challenge environment. Notably, DRIMA shows robust performance where prior methods learn only a highly suboptimal policy, regardless of reward shaping, exploration scheduling, and noisy (random or adversarial) agents.

Global adaptive routing is a critical component of high-radix networks in large-scale systems and is necessary to fully exploit the path diversity of a high-radix topology. The routing decision in global adaptive routing is made between minimal and non-minimal paths, often based on local information (e.g., queue occupancy) and rely on "approximate" congestion information through backpressure. Different heuristic-based adaptive routing algorithms have been proposed for high-radix topologies; however, heuristic-based routing has performance trade-off for different traffic patterns and leads to inefficient routing decisions. In addition, previously proposed global adaptive routing algorithms are static as the same routing decision algorithm is used, even if the congestion information changes. In this work, we propose a novel global adaptive routing that we refer to as dynamic global adaptive routing that adjusts the routing decision algorithm through a dynamic bias based on the network traffic and congestion to maximize performance. In particular, we propose DGB - Decoupled, Gradient descent-based Bias global adaptive routing algorithm. DGB introduces a dynamic bias to the global adaptive routing decision by leveraging gradient descent to dynamically adjust the adaptive routing bias based on the network congestion. In addition, both the local and global congestion information are decoupled in the routing decision - global information is used for the dynamic bias while local information is used in the routing decision to more accurately estimate the network congestion. Our evaluations show that DGB consistently outperforms previously proposed routing algorithms across diverse range of traffic patterns and workloads. For asymmetric traffic pattern, DGB improves throughput by 65% compared to the state-of-the-art global adaptive routing algorithm while matching the performance for symmetric traffic patterns. For trace workloads, DGB provides average performance improvement of 26%.

Growing interest in emerging IoT applications provides a strong drive to release a plethora of communication radios from different standards, which are largely classified into short-range (IEEE 802.15.4) and long-range radios (IEEE 802.15.4g). In this paper, we propose a joint, self-configuring MAC and routing protocol, SEDA-Net, which aims at adaptively choosing the best configuration for communication coordination and data delivery, depending on different deployed topologies and external conditions. SEDA-Net is a combination of SEDA-MAC, SEDA-Routing, and Cross-Opt. SEDA-MAC and SEDA-Routing adaptively determine (i) the best radio configuration for communication coordination under duty-cycling and (ii) each node's next-hop over which radio and Cross-Opt jointly optimizes inter-coupled MAC and routing iteratively. SEDA-Net differs from prior approaches which are designed with static configurations of radios and/or mainly with the goal of throughput maximization for dual Wi-Fi or Wi-Fi/LTE setups. We implement SEDA-Net on Contiki OS and perform extensive simulations and experiments using a testbed in an office building. This testbed consists of 45 nodes equipped with a commercial platform, Firefly, having 2.4 GHz short-range and 920 MHz long-range radios. We demonstrate that energy efficiency quantified by the network lifetime increases by up to 2.1 times, compared to that of existing approaches.

In this paper, we consider the problem of learning a tree graph structure that represents the statistical data dependency among nodes for a set of data samples generated by nodes, which provides the basic structure to perform a probabilistic inference task. Inference in the data graph includes marginal inference and maximum a posteriori (MAP) estimation, and belief propagation (BP) is a commonly used algorithm to compute the marginal distribution of nodes via message-passing, incurring non-negligible amount of communication cost. We inevitably have the trade-off between the inference accuracy and the message-passing cost because the learned structure of data dependency and physical connectivity graph are often highly different. In this paper, we formalize this trade-off in an optimization problem which outputs the data dependency graph that jointly considers learning accuracy and message-passing costs. We focus on two popular implementations of BP,ASYNC-BPandSYNC-BP, which have different message-passing mechanisms and cost structures. InASYNC-BP, we propose a polynomial-time learning algorithm that is optimal, motivated by finding a maximum weight spanning tree of a complete graph. InSYNC-BP, we prove the NP-hardness of the problem and propose a greedy heuristic. For both BP implementations, we quantify how the error probability that the learned cost-efficient data graph differs from the ideal one decays as the number of data samples grows, using the large deviation principle, which provides a guideline on how many samples are necessary to obtain a certain trade-off. We validate our theoretical findings through extensive simulations, which confirms that it has a good match.

The carrier sense multiple access (CSMA) algorithm has been used in the wireless medium access control (MAC) under standard 802.11 implementation due to its simplicity and generality. An extensive body of research on CSMA has long been made not only in the context of practical protocols, but also in a distributed way of optimal MAC scheduling. However, the current state-of-the-art CSMA (or its extensions) still suffers from poor performance, especially in multi-hop scenarios, and often requires patch-based solutions rather than a universal solution. In this paper, we propose an algorithm which adopts an experience-driven approach and train CSMA-based wireless MAC by using deep reinforcement learning. We name our protocol, Neuro-DCF. Two key challenges are: (i) a stable training method for distributed execution and (ii) a unified training method for embracing various interference patterns and configurations. For (i), we adopt a multi-agent reinforcement learning framework, and for (ii) we introduce a novel graph neural network (GNN) based training structure. We provide extensive simulation results which demonstrate that our protocol, Neuro-DCF, significantly outperforms 802.11 DCF and O-DCF, a recent theory-based MAC protocol, especially in terms of improving delay performance while preserving optimal utility. We believe our multi-agent reinforcement learning based approach would get broad interest from other learning-based network controllers in different layers that require distributed operation.

We study the problem of unsupervised domain adaptation that aims at obtaining a prediction model for the target domain using labeled data from the source domain and unlabeled data from the target domain. There exists an array of recent research based on the idea of extracting features that are not only invariant for both domains but also provide high discriminative power for the target domain. In this paper, we propose an idea of improving the discriminativeness: Adding an extra artificial class and training the model on the given data together with the GAN-generated samples of the new class. The trained model based on the new class samples is capable of extracting the features that are more discriminative by repositioning data of current classes in the target domain and therefore increasing the distances among the target clusters in the feature space. Our idea is highly generic so that it is compatible with many existing methods such as DANN, VADA, and DIRT-T. We conduct various experiments for the standard data commonly used for the evaluation of unsupervised domain adaptations and demonstrate that our algorithm achieves the SOTA performance for many scenarios.

Internet of Things (IoT), which connects a large number of devices with wireless connectivity, has come into the spotlight. As the scope of IoT applications becomes wider, we observe a surge of missioncritical IoT services, e.g., industrial automation systems and medical IoT systems, requiring to satisfy stringent latency, reliability, and/or energy efficiency guarantees. For this purpose, a new MAC, called Time Slotted Channel Hopping (TSCH), has been standardized in IEEE 802.15.4e. However, it is challenging to design a distributed scheduling protocol that achieves the required QoS and energy efficiency at the same time due to complicated tradeoff (providing enough number of slots for QoS vs. minimizing scheduled slots for energy efficiency). In this paper, we propose a novel framework for providing QoS, called SSAP, which is designed to maximize network lifetime in a distributed fashion while satisfying given reliability and latency requirements. To this end, we decompose our goal into two crucial design components: (i) scheduling of slot and channel, and (ii) control of medium access period, each of which is performed by low-complexity and distributed mechanisms. To the best of our knowledge, this paper is the first work to comprehensively handle multiple QoSes for TSCH-based IoT networks. We implement SSAP in Contiki OS and perform extensive simulations and real experiments under various scenarios. Our evaluation results demonstrate that SSAP satisfies highly reliable communication and latency requirements while having the network lifetime that is 1.6 times longer compared to existing protocols for TSCH.

With the explosive increase in wireless devices, physical-layer signal analysis has become critically beneficial across distinctive domains including interference minimization in network planning, security and privacy (e.g., drone and spycam detection), and mobile health with remote sensing. While SDR is known to be highly effective in realizing such services, they are rarely deployed or used by the end-users due to the costly hardware ~1K USD (e.g., USRP). Low-cost SDRs (e.g., RTL-SDR) are available, but their bandwidth is limited to 2-3 MHz and operation range falls well below 2.4 GHz - the unlicensed band holding majority of the wireless devices. This paper presents SDR-Lite, the first zero-cost, software-only software defined radio (SDR) receiver that empowers commodity WiFi to retrieve the In-phase and Quadrature of an ambient signal. With the full compatibility to pervasively-deployed WiFi infrastructure (without any change to the hardware and firmware), SDR-Lite aims to spread the blessing of SDR receiver functionalities to billions of WiFi users and households to enhance our everyday lives. The key idea of SDR-Lite is to trick WiFi to begin packet reception (i.e., the decoding process) when the packet is absent, so that it accepts ambient signals in the air and outputs corresponding bits. The bits are then reconstructed to the original physical-layer waveform, on which diverse SDR applications are performed. Our comprehensive evaluation shows that the reconstructed signal closely reassembles the original ambient signal (>85% correlation). We extensively demonstrate SDR-Lite effectiveness across seven distinctive SDR receiver applications under three representative categories: (i) RF fingerprinting, (ii) spectrum monitoring, and (iii) (ZigBee) decoding. For instance, in security applications of drone and rogue WiFi AP detection, SDR-Lite achieves 99% and 97% accuracy, which is comparable to USRP.

Graph learning is an inference problem of estimating connectivity of a graph from a collection of epidemic cascades, with many useful applications in the areas of online/offline social networks, p2p networks, computer security, and epidemiology. We consider a practical scenario when the information of cascade samples are partially observed in the independent cascade (IC) model. For the graph learning problem, we propose an efficient algorithm that solves a localized version of computationally-intractable maximum likelihood estimation through approximations in both temporal and spatial aspects. Our algorithm iterates the operations of recovering missing time logs and inferring graph connectivity, and thereby progressively improves the inference quality. We study the sample complexity, which is the number of required cascade samples to meet a given inference quality, and show that it is asymptotically close to a lower bound, thus near-order-optimal in terms of the number of nodes. We evaluate the performance of our algorithm using five real-world social networks, whose size ranges from 20 to 900, and demonstrate that our algorithm performs better than other competing algorithms in terms of accuracy while maintaining fast running time.

This paper presents GateScatter, the first backscatter-based gateway connecting commodity IoT to WiFi. The backscatter design of GateScatter is an economic option towards pervasive Internet connectivity for ever-growing IoT. The carefully designed tag optimally reshapes ZigBee IoT packets with an arbitrary payload into an 802.11b WiFi packet over the air, such that the payload can be reliably retrieved at the WiFi receiver (hence a gateway). Gate-Scatter is highly compatible - it works with a wide range of IEEE 802.15.4-compliant systems, is agnostic to upper layer proprietary protocols, and does not require any modification to the commodity IoT platforms. GateScatter is extended to BLE IoT for generality. We prototype GateScatter hardware on FPGA where the wide applicability is demonstrated through evaluations on five popular IoT devices including Samsung SmartThings sensor, Philips smart bulb, and Amazon Echo Plus. Further extensive evaluations show that GateScatter consistently achieves throughput above 200 kbps and range of over 27 m under diverse practical scenarios including a corridor, dormitory room, and under user mobility.

Hypergraphs provide a natural way of representing group relations, whose complexity motivates an extensive array of prior work to adopt some form of abstraction and simplification of higher-order interactions. However, the following question has yet to be addressed: How much abstraction of group interactions is sufficient in solving a hypergraph task, and how different such results become across datasets? This question, if properly answered, provides a useful engineering guideline on how to trade off between complexity and accuracy of solving a downstream task. To this end, we propose a method of incrementally representing group interactions using a notion of n-projected graph whose accumulation contains information on up to n-way interactions, and quantify the accuracy of solving a task as n grows for various datasets. As a downstream task, we consider hyperedge prediction, an extension of link prediction, which is a canonical task for evaluating graph models. Through experiments on 15 real-world datasets, we draw the following messages: (a) Diminishing returns: small n is enough to achieve accuracy comparable with near-perfect approximations, (b) Troubleshooter: as the task becomes more challenging, larger n brings more benefit, and (c) Irreducibility: datasets whose pairwise interactions do not tell much about higher-order interactions lose much accuracy when reduced to pairwise abstractions.

We propose a new MAC protocol for IoT applications, called Bird-MAC, which is highly energy efficient in the applications where IoT sensors report monitoring status in a quasi-periodic manner, as in structural health monitoring and static environmental monitoring. Two key design ideas of Bird-MAC are: (a) no need of early-wake-up of transmitters and (b) taking the right balance between synchronization and coordination costs. The idea (a) is possible by allowing a node (whether it is a transmitter or receiver) to wake up just with its given wake-up schedule, and letting a late bird (which wakes up later) notify its wake-up status to its corresponding early bird (which wakes up earlier), where the early bird just infrequently waits for the late bird's wake-up signal. The idea (b) is realized by designing Bird-MAC to be placed in a scheme between purely synchronous and asynchronous schemes. We provide a rigorous mathematical analysis that is used to choose the right protocol parameters of Bird-MAC. We demonstrate the performance of Bird-MAC through extensive simulations, and real experiments. The experiment on our testbed using a 26 node testbed at an underground parking lot of our office building to monitor its structural health shows that energy consumption is reduced by about up to 45 percent over existing sensor MAC protocols. We also confirm the applicability of Bird-MAC in a challenging and realistic scenario through the experiment on Yeongjong Grand Bridge in South Korea.

Fog computing is a paradigm which brings computing, storage, and networking closer to end users and end devices for better service provisioning. One of the crucial factors in the success of fog computing is on how to incentivize the individual users' edge resources and provide them to end users such that fog computing is economically beneficial to all involved economic players. In this paper, we model and analyze a market of fog computing, from which we aim at drawing practical implications to uncover how the fog computing market should operate. To this end, we conduct an economic analysis of such user-oriented fog computing by modeling a market consisting of Infrastructure and Service Provider (ISP), end Service Users (SUs), and Edge Resource Owners (EROs) as a non-cooperative game. In this market, ISP, which provides a platform for fog computing, behaves as a mediator or a broker which leases EROs' edge resources and provides various services to SUs. In our model, a two-stage dynamic game is used where in each stage, there exists a dynamic game, one for between ISP and EROs and another for between ISP and SUs, to model the market more practically. Despite this complex game structure, we provide a closed-form equilibrium analysis which gives an insight on how much economic benefit is obtained by ISP, SUs, and EROs from user-oriented fog computing under what conditions, and we figure out the economic factors that have a significant impact on the success of fog computing.

In this paper, we study a problem of detecting the source of diffused information by querying individuals, given a sample snapshot of the information diffusion graph, where two queries are asked: (i) whether the respondent is the source or not, and (ii) if not, which neighbor spreads the information to the respondent. We consider the case when respondents may not always be truthful and some cost is taken for each query. Our goal is to quantify the necessary and sufficient budgets to achieve the detection probability 1- δ for any given 0 <; δ <; 1. To this end, we study two types of algorithms: adaptive and non-adaptive ones, each of which corresponds to whether we adaptively select the next respondents based on the answers of the previous respondents or not. We first provide the information theoretic lower bounds for the necessary budgets in both algorithm types. In terms of the sufficient budgets, we propose two practical estimation algorithms, each of non-adaptive and adaptive types, and for each algorithm, we quantitatively analyze the budget which ensures 1- δ detection accuracy. This theoretical analysis not only quantifies the budgets needed by practical estimation algorithms achieving a given target detection accuracy in finding the diffusion source, but also enables us to quantitatively characterize the amount of extra budget required in non-adaptive type of estimation, referred to as adaptivity gap. We validate our theoretical findings over synthetic and real-world social network topologies.

Currently, miners typically join mining pools to solve cryptographic puzzles together, and mining pools are in high competition. This has led to the development of several attack strategies such as block withholding (BWH) and fork after withholding (FAW) attacks that can weaken the health of PoW systems and but maximize mining pools' profits. In this paper, we present strategies called Adaptive Retaliation Strategies (ARS) to mitigate not only BWH attacks but also FAW attacks. In ARS, each pool cooperates with other pools in the normal situation, and adaptively executes either FAW or BWH attacks for the purpose of retaliation only when attacked. In addition, in order for rational pools to adopt ARS, ARS should strike to an adaptive balance between retaliation and selfishness because the pools consider their payoff even when they retaliate. We theoretically and numerically show that ARS would not only lead to the induction of a no-attack state among mining pools, but also achieve the adaptive balance between retaliation and selfishness.

Crowdsourcing platforms emerged as popular venues for purchasing human intelligence at low cost for large volume of tasks. As many low-paid workers are prone to give noisy answers, a common practice is to add redundancy by assigning multiple workers to each task and then simply average out these answers. However, to fully harness the wisdom of the crowd, one needs to learn the heterogeneous quality of each worker. We resolve this fundamental challenge in crowdsourced regression tasks, i.e., the answer takes continuous labels, where identifying good or bad workers becomes much more non-trivial compared to a classification setting of discrete labels. In particular, we introduce a Bayesian iterative scheme and show that it provably achieves the optimal mean squared error. Our evaluations on synthetic and real-world datasets support our theoretical results and show the superiority of the proposed scheme.

Energy efficiency is critical in many IoT applications with sensors that deliver data over wireless communications. Duty-cycling has been a major method for reducing energy consumption. One popular duty-cycling is MAC duty-cycling where an MCU commands the periodic or adaptive turning on and off of an RF chip. Recently, there has been an increase in the number of RF chips for IoT that are equipped with PHY duty-cycling, a new capability of autonomously switching on and off an RF chip without the use of an MCU. These two schemes working at different layers have different pros and cons in terms of operating time scale, the amount of energy saved when the RF chip is switched off, all of which depend on the characteristics of the MCU and the RF chip. In this paper, we propose a novel protocol named HD-MAC (Hierarchical Duty-cycling MAC) that hierarchically integrates duty-cycling in the MAC and physical layers. By smartly applying the new function of chip-level duty-cycling, HD-MAC is able to further reduce the amount of on-time in MAC duty-cycling; hence, energy efficiency can be improved. To optimize HD-MAC’s energy efficiency while achieving a given delay requirement, we formulate an optimization problem and solve it to obtain the optimal parameters in the cross-layer context. We implement HD-MAC on Contiki OS and perform extensive experiments using a real sensor mote Firefly with a CC1200 RF chip. We demonstrate that the energy efficiency of HD-MAC is up to 72% higher than that of existing protocols while still satisfying the delay requirement and sustaining similar reliability.

We explore value-based solutions for multi-agent reinforcement learning (MARL) tasks in the centralized training with decentralized execution (CTDE) regime popularized recently. However, VDN and QMIX are representative examples that use the idea of factorization of the joint action-value function into individual ones for decentralized execution. VDN and QMIX address only a fraction of factorizable MARL tasks due to their structural constraint in factorization such as additivity and monotonicity. In this paper, we propose a new factorization method for MARL, QTRAN, which is free from such structural constraints and takes on a new approach to transforming the original joint action-value function into an easily factorizable one, with the same optimal actions. QTRAN guarantees more general factorization than VDN or QMIX, thus covering a much wider class of MARL tasks than does previous methods. Our experiments for the tasks of multi-domain Gaussian-squeeze and modified predator-prey demonstrate QTRAN’s superior performance with especially larger margins in games whose payoffs penalize non-cooperative behavior more aggressively.

We consider the Markov Decision Process (MDP) of selecting a subset of items at each step, termed the Select-MDP (S-MDP). The large state and action spaces of S-MDPs make them intractable to solve with typical reinforcement learning (RL) algorithms especially when the number of items is huge. In this paper, we present a deep RL algorithm to solve this issue by adopting the following key ideas. First, we convert the original S-MDP into an Iterative Select-MDP (IS-MDP), which is equivalent to the S-MDP in terms of optimal actions. IS-MDP decomposes a joint action of selecting K items simultaneously into K iterative selections resulting in the decrease of actions at the expense of an exponential increase of states. Second, we overcome this state space explosion by exploiting a special symmetry in IS-MDPs with novel weight shared Q-networks, which provably maintain sufficient expressive power. Various experiments demonstrate that our approach works well even when the item space is large and that it scales to environments with item spaces different from those used in training.

Rate Adaptation (RA) is a fundamental mechanism in 802.11 systems. It allows transmitters to adapt the coding and modulation scheme as well as the MIMO transmission mode to the radio channel conditions, to learn and track the (mode, rate) pair providing the highest throughput. The design of RA mechanisms has been mainly driven by heuristics. In contrast, we rigorously formulate RA as an online stochastic optimization problem. We solve this problem and present G-ORS (Graphical Optimal Rate Sampling), a family of provably optimal (mode, rate) pair adaptation algorithms. Our main result is that G-ORS outperforms state-of-the-art algorithms such as MiRA and Minstrel HT, as demonstrated by experiments on a 802.11n network test-bed. The design of G-ORS is supported by a theoretical analysis, where we study its performance in stationary radio environments where the successful packet transmission probabilities at the various (mode, rate) pairs do not vary over time, and in non-stationary environments where these probabilities evolve. We show that under G-ORS, the throughput loss due to the need to explore sub-optimal (mode, rate) pairs does not depend on the number of available pairs. This is a crucial advantage as evolving 802.11 standards offer an increasingly large number of (mode, rate) pairs. We illustrate the superiority of G-ORS over state-of-the-art algorithms, using both trace-driven simulations and test-bed experiments.

Fog computing is a paradigm which brings computing, storage, and networking closer to end users and devices for better service provisioning. One of the crucial factors towards the success of fog computing is how to incentivize the individual users' edge resources, thereby opening the era of user- participated fog computing. In this paper, we provide an economic analysis of such user-oriented fog computing by modeling a market consisting of ISP (Infrastructure and Service Provider), SUs (end Service Users), and EROs (Edge Resource Owners) as a noncooperative game. In this market, ISP, which provides a platform of fog computing, behaves as a mediator or a broker to lease the edge resources from EROs and provide various services to SUs. In our game formulation, a two-stage dynamic game is used, where in each stage there exists another dynamic game, one for between ISP and EROs and another for between ISP and SUs, to model the market more practically. Despite this complex game structure, we provide a closed- form equilibrium analysis, which gives an insight of how much economic benefits are obtained by ISP, SUs, and EROs under what conditions.

In this paper, we study a problem of detecting the source of diffused information by querying individuals, given a sample snapshot of the information diffusion graph, where two queries are asked: (i) whether the respondent is the source or not, and (ii) if not, which neighbor spreads the information to the respondent. We consider the case when respondents may not always be truthful and some cost is taken for each query. Our goal is to quantify the necessary and sufficient budgets to achieve the detection probability$1-\delta$for any given$0 < \delta < 1$. To this end, we study two types of algorithms: adaptive and non-adaptive ones, each of which corresponds to whether we adaptively select the next respondents based on the answers of the previous respondents or not. We first provide the information theoretic lower bounds for the necessary budgets in both algorithm types. In terms of the sufficient budgets, we propose two practical estimation algorithms, each of non-adaptive and adaptive types, and for each algorithm, we quantitatively analyze the budget which ensures$1-\delta$detection accuracy. This theoretical analysis not only quantifies the budgets needed by practical estimation algorithms achieving a given target detection accuracy in finding the diffusion source, but also enables us to quantitatively characterize the amount of extra budget required in non-adaptive type of estimation, refereed to as adaptivity gap. We validate our theoretical findings over synthetic and real-world social network topologies.

In this paper, we consider the problem of recovering a graph that represents the statistical data dependency among nodes for a set of data samples generated by nodes, which provides the basic structure to perform an inference task, such as MAP (maximum a posteriori). This problem is referred to as structure learning. When nodes are spatially separated in different locations, running an inference algorithm requires a non-negligible amount of message passing, incurring some communication cost. We inevitably have the trade-off between the accuracy of structure learning and the cost we need to pay to perform a given message-passing based inference task because the learnt edge structures of data dependency and physical connectivity graph are often highly different. In this paper, we formalize this trade-off in an optimization problem which outputs the data dependency graph that jointly considers learning accuracy and message-passing cost. We focus on a distributed MAP as the target inference task due to its popularity, and consider two different implementations, ASYNC-MAP and SYNC-MAP that have different message-passing mechanisms and thus different cost structures. In ASYNC-MAP, we propose a polynomial time learning algorithm that is optimal, motivated by the problem of finding a maximum weight spanning tree. In SYNC-MAP, we first prove that it is NP-hard and propose a greedy heuristic. For both implementations, we then quantify how the probability that the resulting data graphs from those learning algorithms differ from the ideal data graph decays as the number of data samples grows, using the large deviation principle, where the decaying rate is characterized by some topological structures of both original data dependency and physical connectivity graphs as well as the degree of the trade-off, which provides some guideline on how many samples are necessary to obtain a certain learning accuracy. We validate our theoretical findings through extensive simulations, which confirm that it has a good match.

Successful operation of User-Provided Networks (UPN) requires that both of Internet Service Provider (ISP) and self network-operating users (hosts) cooperate appropriately in terms of resource sharing and pricing strategy since ISP and hosts have a multilateral reliance on each other with respect to virtual infrastructure expansion and Internet connectivity. However, it has been underexplored whether such cooperation provides sufficient incentive to ISP and hosts under a setup where ISP and hosts are fully included, having a high dependence on how to cooperate and how to distribute the resulting cooperation worth. In this paper, we model a market of UPN, consisting of ISP, hosts, and clients via game theory, where we model various heterogeneities in terms of (i) willingness to pay and mobility pattern of clients, (ii) hosts' QoS, and (iii) type of cooperation among ISP and hosts. The key technical challenges lie in the natural mixture of cooperative and non-cooperative game theoretic angles, where the worth function---one of the crucial components in coalitional game theory---comes from the equilibrium of an embedded, non-cooperative two-stage dynamic game. We consider the Shapley value as a mechanism of revenue sharing and overcome its hardness in characterization by taking the fluid limit when the number of hosts and clients is large. Our analytical studies reveal useful implications that in UPN when and how much economic benefits can be given to the players and when they maintain their grand coalition under what conditions, referred to as stability.

Crowdsourcing systems are popular for solving large-scale labeling tasks with low-paid workers. We study the problem of recovering the true labels from the possibly erroneous crowdsourced labels under the popular Dawid-Skene model. To address this inference problem, several algorithms have recently been proposed, but the best known guarantee is still significantly larger than the fundamental limit. We close this gap by introducing a tighter lower bound on the fundamental limit and proving that the belief propagation (BP) exactly matches the lower bound. The guaranteed optimality of BP is the strongest in the sense that it is information-theoretically impossible for any other algorithm to correctly label a larger fraction of the tasks. Experimental results suggest that the BP is close to optimal for all regimes considered and improves upon competing the state-of-the-art algorithms.

Game-theoretic approaches have provided valuable insights into the design of robust local control rules for the individuals in multi-agent systems, e.g., Internet congestion control, road transportation networks, and so on. In this paper, we introduce a non-cooperative medium access control game for wireless networks and propose new fully distributed carrier sense multiple access (CSMA) algorithms that are provably optimal in the sense that their long-term throughputs converge to the optimal solution of a utility maximization problem over the maximum throughput region. The most significant part of our approach lies in introducing novel price functions in agents' utilities so that the proposed game admits an ordinal potential function with no price-of-anarchy. The game formulation naturally leads to game-based dynamics finding a Nash equilibrium, but they often require global information. Toward our goal of designing fully distributed operations, we propose new game-inspired dynamics by utilizing a certain property of CSMA that enables links to estimate their temporary throughputs without message passing. They can be thought of as stochastic approximations to the standard dynamics, which is a new feature in our work, not prevalent in other traditional game-theoretic approaches. We show that they converge to a Nash equilibrium, and numerically evaluate their performance to support our theoretical findings.

Social networks are the major routes for most individuals to exchange their opinions about new products, social trends and political issues via their interactions. It is often of significant importance to figure out who initially diffuses the information, i.e., finding a rumor source or a trend setter. It is known that such a task is highly challenging and the source detection probability cannot be beyond 31% for regular trees, if we just estimate the source from a given diffusion snapshot. In practice, finding the source often entails the process of querying that asks “Are you the rumor source?” or “Who tells you the rumor?” that would increase the chance of detecting the source. In this paper, we consider two kinds of querying: (a) simple batch querying and (b) interactive querying with direction under the assumption that queriees can be untruthful with some probability. We propose estimation algorithms for those queries, and quantify their detection performance and the amount of extra budget due to untruthfulness, analytically showing that querying significantly improves the detection performance. We perform extensive simulations to validate our theoretical findings over synthetic and real-world social network topologies.

We consider a problem of how to effectively diffuse a new product over social networks by incentivizing selfish users. Traditionally, this problem has been studied in the form of influence maximization via seeding, where most prior work assumes that seeded users unconditionally and immediately start by adopting the new product and they stay at the new product throughout their lifetime. However, in practice, seeded users often adjust the degree of their willingness to diffuse, depending on how much incentive is given. To address such diffusion willingness, we propose a new incentive model and characterize the speed of diffusion as the value of a combinatorial optimization. Then, we apply the characterization to popular network graph topologies (Erdos-Renyi, planted partition and power law graphs) as well as general ones, for asymptotically computing the diffusion time for those graphs. Our analysis shows that the diffusion time undergoes two levels of order-wise reduction, where the first and second one are solely contributed by the number of seeded users, i.e., quantity, and the amount of incentives, i.e., quality, respectively. In other words, it implies that the best strategy given budget is (a) first identify the minimum seed set depending on the underlying graph topology, and (b) then assign largest possible incentives to users in the set. We believe that our theoretical results provide useful implications and guidelines for designing successful advertising strategies in various practical applications.

This paper studies the problem of parameter learning in graphical models having latent variables, where the standard approach is the expectation maximization algorithm alternating expectation (E) and maximization (M) steps. However, both E and M steps are computationally intractable for high dimensional data, while the substitution of one step to a faster surrogate for combating against intractability can often cause failure in convergence. To tackle the issue, the Contrastive Divergence (CD) learning scheme has been popularly used in the deep learning community, where it runs the mean-field approximation in E step and a few cycles of Markov Chains (MC) in M step. In this paper, we analyze a variant of CD, called Adiabatic Persistent Contrastive Divergence (APCD), which runs a few cycles of MCs in both E and M steps. Using multi-time-scale stochastic approximation theory, we prove that APCD converges to a correct optimum, where the standard CD is impossible to have such a guarantee due to the mean-field approximation gap in E step. Despite of such stronger theoretical guarantee of APCD, its possible drawback is on slow mixing on E step for practical purposes. To address the issue, we also design a hybrid approach applying both mean-field and MC approximations in E step, where it outperforms the standard mean-field-based CD in our experiments on real-world datasets.

We propose a new sensor MAC protocol, called Bird-MAC, which is highly energy efficient in the applications where sensors periodically report monitoring status with a very low rate, as in structural health monitoring and static environmental monitoring. Two key design ideas of Bird-MAC are: (a) no need of early-wake-up of transmitters and (b) taking the right balance between synchronization and coordination costs. The idea (a) is possible by allowing a node (whether it is a transmitter or receiver) to wake up just with its given wake-up schedule, and letting a late bird (which wakes up later) notify its wake-up status to its corresponding early bird (which wakes up earlier), where the early bird just infrequently waits (i.e., nods) for the late bird's wake-up signal. The idea (b) is realized by designing Bird-MAC to be placed in a scheme between purely synchronous and asynchronous schemes. We provide rigorous mathematical analysis that is used to choose the right protocol parameters of Bird-MAC. We demonstrate the performance of Bird-MAC through extensive simulations, and real experiments using a 26 node testbed at an underground parking lot of our office building to monitor its structural health, where we confirm that energy consumption is reduced by about up to 45% over existing sensor MAC protocols.

The Internet consists of economically selfish players in terms of access/transit connection and content distribution. Such selfish behaviors often lead to techno-economic inefficiencies, such as unstable peering and revenue imbalance. Recent research results suggest that cooperation-based fair revenue sharing, i.e., multi-level Internet service provider (ISP) settlements, can be a candidate solution to avoid unfair revenue share. However, it has been under-explored whether selfish ISPs actually cooperate or not (often referred to as the stability of coalition), because they may partially cooperate or even do not cooperate, depending on how much revenue is distributed to each individual ISP. In this paper, we study this stability of coalition in the Internet, where our aim is to investigate the conditions under which ISPs cooperate under different regimes on the traffic demand and network bandwidth. We first consider the under-demanded regime, i.e., network bandwidth exceeds traffic demand, where revenue sharing based on Shapley value leads ISPs to entirely cooperate, i.e., stability of the grand coalition. Next, we consider the over-demanded regime, i.e., traffic demand exceeds network bandwidth, where there may exist some ISPs who deviate from the grand coalition. In particular, this deviation depends on how users' traffic is handled inside the network, for which we consider three traffic scheduling policies having various degrees of content-value preference. We analytically compare those three scheduling policies in terms of network neutrality, and stability of cooperation that provides useful implications on when and how multi-level ISP settlements help and how the Internet should be operated for stable peering and revenue balance among ISPs.

Delay-tolerant Wi-Fi offloading is known to improve overall mobile network bandwidth at low delay and low cost. Yet, in reality, we rarely find mobile apps that fully support opportunistic Wi-Fi access. This is mainly because it is still challenging to develop delay-tolerant mobile apps due to the complexity of handling network disruptions and delays. In this paper, we present Cedos, a practical delay-tolerant mobile network access architecture in which one can easily build a mobile app. Cedos consists of three components. First, it provides a familiar socket API whose semantics conforms to TCP, while the underlying protocol, D2TP, transparently handles network disruptions and delays in mobility. Second, Cedos allows the developers to explicitly exploit delays in mobile apps. App developers can express maximum user-specified delays in content download or use the API for real-time buffer management at opportunistic Wi-Fi usage. Third, for backward compatibility to existing TCP-based servers, Cedos provides D2Prox, a protocol-translation Web proxy. D2Prox allows intermittent connections on the mobile device side, but correctly translates Web transactions with traditional TCP servers. We demonstrate the practicality of Cedos by porting mobile Firefox and VLC video streaming client to using the API. We also implement delay/disruption-tolerant podcast client and run a field study with 50 people for eight weeks. We find that up to 92.4% of the podcast traffic is offloaded to Wi-Fi, and one can watch a streaming video in a moving train while offloading 48% of the content to Wi-Fi without a single pause.

In this paper, we propose a simple, distributed, but highly efficient fairness-enforcing incentive mechanism for cooperative computing. The proposed mechanism, called triangle chaining (T-Chain), enforces reciprocity to avoid the exploitable aspects of the schemes that allow free-riding. In T-Chain, symmetric key cryptography provides the basis for a lightweight, almost-fair exchange protocol, which is coupled with a pay-it-forward mechanism. This combination increases the opportunity for multi-lateral exchanges and further maximizes the resource utilization of participants, each of whom is assumed to operate solely for his or her own benefit. T-Chain also provides barrier-free entry to newcomers with flexible resource allocation, allowing them to immediately benefit, and, therefore, is suitable for dynamic environments with high churn (i.e., turnover). T-Chain is distributed and simple to implement, as no trusted third party is required to monitor or enforce the scheme, nor is there any reliance on reputation information or tokens.

The data explosion and resource scarcity of mobile cellular networks require new paradigms to effectively integrate heterogeneous radio resources. Of many candidate approaches, smart aggregation of LTE and Wi-Fi radios is a promising solution that bonds heterogeneous links to meet a mobile terminal's bandwidth need. Motivated by the existence of a significant number of carrier operated Wi-Fi APs, we propose an easily deployable mechanism, called LTE-W, which efficiently utilizes LTE and Wi-Fi links only with the minimum change of eNodeBs, LTE backhaul networks, and mobile terminals. LTE-W, which is a link-level aggregation mechanism, has the following two key components: 1) mode selection and 2) bearer-split scheduling. First, in the mode selection, LTE-W internally decides who should be served by either LTE-only or LTE-Wi-Fi aggregation considering intra-cell fairness rather than just following users' intention of aggregation. For the users' preference to be offered the aggregation service, we choose a bearer (roughly defined in LTE as a set of flows with a similar QoS) as a basic unit of aggregation and propose a smart intra-bearer scheduling algorithm that splits a bearer's traffic into LTE and Wi-Fi links, considering the performance of TCP flows that take two heterogeneous wireless links. We evaluate our mechanism using the NS-3 with LENA, under various configurations, including nodes with mobility and HTTP traffic, and compare it with a transport-level aggregation mechanism, multipath TCP (MPTCP), demonstrating that LTE-W significantly improves MPTCP, e.g., up to 75% in terms of Jain's fairness index.

Crowdsourcing systems are popular for solving large-scale labelling tasks with low-paid (or even non-paid) workers. We study the problem of recovering the true labels from noisy crowdsourced labels under the popular Dawid-Skene model. To address this inference problem, several algorithms have recently been proposed, but the best known guarantee is still significantly larger than the fundamental limit. We close this gap under a simple but canonical scenario where each worker is assigned at most two tasks. In particular, we introduce a tighter lower bound on the fundamental limit and prove that Belief Propagation (BP) exactly matches this lower bound. The guaranteed optimality of BP is the strongest in the sense that it is information-theoretically impossible for any other algorithm to correctly la- bel a larger fraction of the tasks. In the general setting, when more than two tasks are assigned to each worker, we establish the dominance result on BP that it outperforms other existing algorithms with known provable guarantees. Experimental results suggest that BP is close to optimal for all regimes considered, while existing state-of-the-art algorithms exhibit suboptimal performances.

Recently, the problem of detecting the rumor source in a social network has been much studied, where it has been shown that the detection probability cannot be beyond 31% even for regular trees. In this paper, we study the impact of an anti-rumor on the rumor source detection. We first show a negative result: the anti-rumor's diffusion does not increase the detection probability under Maximum-Likelihood-Estimator (MLE) when the number of infected nodes are sufficiently large by passive diffusion that the anti-rumor starts to be spread by a special node, called the protector, after is reached by the rumor. We next consider the case when the distance between the rumor source and the protector follows a certain type of distribution, but its parameter is hidden. Then, we propose the following learning algorithm: a) learn the distance distribution parameters under MLE, and b) detect the rumor source under Maximum-A-Posterior-Estimator (MAPE) based on the learnt parameters. We provide an analytic characterization of the rumor source detection probability for regular trees under the proposed algorithm, where MAPE outperforms MLE by up to 50% for 3-regular trees and by up to 63% when the degree of the regular tree becomes large. We demonstrate our theoretical findings through numerical results, and further present the simulation results for general topologies (e.g., Facebook and US power grid networks) even without knowledge of the distance distribution, showing that under a simple protector placement algorithm, MAPE produces the detection probability much larger than that by MLE.

In various online/offline networked environments, it is very popular that the system can benefit from coordinating actions of two interacting nodes, but incur some cost due to such coordination. Examples include a wireless sensor networks with duty cycling, where a sensor node consumes a certain amount of energy when it is awake, but a coordinated operation of sensors enables some meaningful tasks, e.g., sensed data forwarding, collaborative sensing of a phenomenon, or efficient decision of further sensing actions. In this paper, we formulate an optimization problem that captures the amount of coordination gain at the cost of node activation over networks. This problem is challenging since the target utility is a function of the long-term time portion of the inter-coupled activations of two adjacent nodes, and thus a standard Lagrange duality theory is hard to apply to obtain a distributed decomposition as in the standard NUM (Network Utility Maximization). We propose a fully-distributed algorithm that requires only one-hop message passing. Our approach is inspired by a control of Ising model in statistical physics, and the proposed algorithm is motivated by a stochastic approximation method that runs a Markov chain incompletely over time, but provably guarantees its convergence to the optimal solution. We validate our theoretical findings on convergence and optimality through extensive simulations under various scenarios.

People are seeking solutions in diverse directions to cope with mobile data explosion and resource scarcity in mobile cellular networks. Of many candidate approaches, smart aggregation of LTE and Wi-Fi radios is a promising solution that bonds heterogeneous links to meet a mobile terminal's available bandwidth need. Motivated by the existence of a significant number of carrier-operated Wi-Fi APs, we propose a mechanism, called LTE-W, of efficiently utilizing LTE and Wi-Fi links only with the minimum changes of eNodeBs, LTE backhaul networks, and mobile terminals. Our mechanism has the following two key components: (i) mode selection and (ii) bearer-split scheduling. In the mode selection, LTE-W internally decides who should be served by either of LTE or LTE-Wi-Fi aggregation considering intra-cell fairness rather than just following users' intention of aggregation. For the users decided to be offered the aggregation service, we choose a bearer (roughly defined a set of flows with a similar QoS in LTE) as a basic unit of aggregation and propose a smart intra-bearer scheduling algorithm that splits a bearer's traffic into LTE and Wi-Fi links, considering the tuning of TCP flows that take two heterogeneous wireless links. We evaluate our mechanism using the NS-3 with LENA, and compare it to a transport-level aggregation mechanism, MPTCP, demonstrating that LTE-W significantly improves MPTCP, e.g., up to 75% in terms of Jain's fairness index.

To cope with consumers' ever-increasing demand of high-quality contents in the Internet, content providers (e.g., YouTube) mainly pay to global pure-play CDN companies (e.g., Akamai) instead of ISPs for content delivery. This motivates ISPs to offer their own regional CDN services as Telco-CDNs that compete with the pure-play CDNs for CPs in the CDN market. Unlike the pure-play CDNs with global consumer coverage geographically, Telco-CDNs have the strength of better QoS due to integration of traffic engineering with content delivery. In this paper, we study their competition for CPs by using dynamic game theory, where Telco-CDNs can choose to federate with each other and to which extent. We first analyze the traditional case when Telco-CDNs do not federate and independently operate to locally compete with a typical pure-play CDN. We next study the case when Telco-CDNs form a federation by (i) physically pooling their resources and/or further (ii) economically sharing the total revenue. Depending on the degree of their cooperation (with only (i), called partial federation, or with both (i) and (ii), called full federation), we study how strongly and successfully Telco-CDNs are able to penetrate into the CDN market. Perhaps surprisingly, we show that Telco-CDNs' federation may not help themselves due to the threat of perfect competition with the pure-play CDN.

An essential condition precedent to the success of mobile applications based on Wi-Fi (e.g., iCloud) is an energy-efficient Wi-Fi sensing. Clearly, a good Wi-Fi sensing policy should factor in both inter-access point (AP) arrival time (IAT) and contact duration time (CDT) distributions of each individual. However, prior work focuses on limited cases of those two distributions (e.g., exponential) or proposes heuristic approaches such as Additive Increase (AI). In this paper, we first formulate a generalized functional optimization problem on Wi-Fi sensing under general inter-AP and contact duration distributions and investigate how each individual should sense Wi-Fi APs to strike a good balance between energy efficiency and performance, which is in turn intricately linked with users mobility patterns. We then derive a generic optimal condition that sheds insights into the aging property, underpinning energy-aware Wi-Fi sensing polices. In harnessing our analytical findings and the implications thereof, we develop a new sensing algorithm, called Wi-Fi Sensing with AGing (WiSAG), and demonstrate that WiSAG outperforms the existing sensing algorithms up to 37% through extensive trace-driven simulations for which real mobility traces gathered from hundreds of smartphones is used.

This paper proposes a new protocol called Optimal DCF (O-DCF). O-DCF modifies the rule of adapting CSMA parameters, such as backoff time and transmission length, based on a function of the demand-supply differential of link capacity captured by the local queue length. O-DCF is fully compatible with 802.11 hardware, so that it can be easily implemented only with a simple device driver update. O-DCF is inspired by the recent analytical studies proven to be optimal under assumptions, which often generates a big gap between theory and practice. O-DCF effectively bridges such a gap, which is implemented in off-the-shelf 802.11 chipset. Through extensive simulations and real experiments with a 16-node wireless network testbed, we evaluate the performance of O-DCF and show that it achieves near-optimality in terms of throughput and fairness and outperforms other competitive ones, such as 802.11 DCF, optimal CSMA, and DiffQ for various scenarios. Also, we consider the coexistence of O-DCF and 802.11 DCF and show that O-DCF fairly shares the medium with 802.11 via its parameter control.

A variety of models have been proposed and analyzed to understand how a new innovation (e.g., a technology, a product, or even a behavior) diffuses over a social network, broadly classified into either of epidemic-based or game-based ones. In this paper, we consider a game-based model, where each individual makes a selfish, rational choice in terms of its payoff in adopting the new innovation, but with some noise. We address the following two questions on the diffusion speed of a new innovation under the game-based model: (1) what is a good subset of individuals to seed for reducing the diffusion time significantly, i.e., convincing them to preadopt a new innovation and (2) how much diffusion time can be reduced by such a good seeding. For (1), we design near-optimal polynomial-time seeding algorithms for three representative classes of social network models, Erdös-Rényi, planted partition and geometrically structured graphs, and provide their performance guarantees in terms of approximation and complexity. For (2), we asymptotically quantify the diffusion time for these graph topologies; further derive the seed budget threshold above which the diffusion time is dramatically reduced, i.e., phase transition of diffusion time. Furthermore, based on our theoretical findings, we propose a practical seeding algorithm, called Practical Partitioning and Seeding (PrPaS) and demonstrate that PrPaS outperforms other baseline algorithms in terms of the diffusion speed over a real social network topology. We believe that our results provide new insights on how to seed over a social network depending on its connectivity structure, where individuals rationally adopt a new innovation.

In the past few years, an exciting progress has been made on CSMA (Carrier Sense Multiple Access) algorithms that achieve throughput and utility optimality for wireless networks. However, most of these algorithms are known to exhibit poor delay performance making them impractical for implementation. Recently, several papers have addressed the delay issue of CSMA and yet, most of them are limited, in the sense that they focus merely on specific network scenarios with certain conditions rather than general network topology, achieve low delay at the cost of throughput reduction, or lack rigorous provable guarantees. In this paper, we focus on the recent idea of exploiting multiple channels (actually or virtually) for delay reduction in CSMA, and prove that it is per-link delay order-optimal, i.e., O(1)-asymptotic-delay per link, if the number of virtual channels is logarithmic with respect to mixing time of the underlying CSMA Markov chain. The logarithmic number is typically small, i.e., at most linear with respect to the network size. In other words, our contribution provides not only a provable framework for the multiple-channel based CSMA, but also the required explicit number of virtual-multi-channels, which is of great importance for actual implementation. The key step of our analytic framework lies in using quadratic Lyapunov functions in conjunction with (recursively applying) Lindley equation and Azuma's inequality for obtaining an exponential decaying property in certain queueing dynamics. We believe that our technique is of broader interest in analyzing the delay performance of queueing systems with multiple periodic schedulers.

Recent studies on MAC scheduling have shown that carrier sense multiple access (CSMA) algorithms can be throughput optimal for arbitrary wireless network topology. However, these results are highly sensitive to the underlying assumption on `static' or `fixed' system conditions. For example, if channel conditions are time-varying, it is unclear how each node can adjust its CSMA parameters, so-called backoff and channel holding times, using its local channel information for the desired high performance. In this paper, we study `channel-aware' CSMA (A-CSMA) algorithms in time-varying channels, where they adjust their parameters as some function of the current channel capacity. First, we assume that backoff rates can be arbitrary large and show that the achievable rate region of A-CSMA equals to the maximum rate region if and only if the function is exponential. Furthermore, given an exponential function in A-CSMA, we design updating rules for their parameters, which achieve throughput optimality for an arbitrary wireless network topology. They are the first CSMA algorithms in the literature which are proved to be throughput optimal under time-varying channels. Moreover, we also consider the case when back-off rates of A-CSMA are restricted compared to the speed of channel variations, and characterize the throughput performance of A-CSMA in terms of the underlying wireless network topology. Our results not only guide a high-performance design on MAC scheduling under highly time-varying scenarios, but also provide new insights on the performance of CSMA algorithms in relation to their backoff rates and underlying network topologies.

In this paper, we address the problem of associating mobile stations (MSs) with base stations (BSs) in an energy-efficient manner. We take a population game approach, which allows tractable analysis of many selfish mobiles without growing mathematical complexity. From our game-theoretical analysis, we prove that a simple power-dependent pricing by operators leads a Nash equilibrium to be equal to the optimal solution of a social optimization problem (i.e., no price-of-anarchy). We study three evolution dynamics of associating MSs, each expressed as a differential equation, all of which provably and/or numerically converge to the Nash equilibrium. Based on several considerations regarding implementation of association algorithms in practice, we found that asynchronicity and fast load tracking are the key components to practical algorithms. Motivated by this, we propose a practical energy-efficient user association mechanism, named BRUTE. To evaluate the performance of BRUTE, we implement a cellular network simulator using an event-driven simulator, SimPy, and perform extensive simulations under various scenarios including a real BS topology in U.K. Our simulation results show that BRUTE outperforms other conventional user association techniques.

Both users and mobile network providers increasingly suffer from explosive growth of mobile traffic. We study so-called delayed Wi-Fi offloading that has been recently proposed as a low-cost solution of alleviating mobile data explosion. Delayed Wi-Fi offloading is a technology that offloads traffic from cellular to Wi-Fi by persuading users into delaying their delay-tolerant traffic and thus enlarging users' chance to meet Wi-Fi. In this paper, we study the economic effects of such user-oriented delayed Wi-Fi offloading in two market models: 1) monopoly and 2) duopoly with one multiservice provider. First, in the monopoly market with a single provider, we model a two-stage game, where the provider selects an Wi-Fi usage price for which users are the price-takers. Second, in the duopoly market with one multiservice provider, we consider a situation that both providers, say A and B, offer cellular service and only A launches a delayed Wi-Fi offloading service as a separate service from the original cellular service, thus allowing the users in B to subscribe to the offloading service from A, but with some incurring dual subscription cost. In those two markets, we study how the Wi-Fi usage price at an equilibrium changes depending on other system parameters such as cellular cost, Wi-Fi density, and the number of subscribers by analytically computing the Nash equilibria and conducting extensive numerical computations under various parameter changes. Our results give us useful insights into how economically viable user-oriented delayed Wi-Fi offloading is.

In this paper, we propose a simple, distributed, but highly efficient fairness-enforcing incentive mechanism for cooperative computing. The proposed incentive scheme, called Triangle Chaining (T-Chain), enforces reciprocity to minimize the exploitable aspects of other schemes that allow free-riding. In T-Chain, symmetric key cryptography provides the basis for a lightweight, almost-fair exchange protocol, which is coupled with a pay-it-forward mechanism. This combination increases the opportunity for multi-lateral exchanges and further maximizes the resource utilization of participants, each of whom is assumed to operate solely for his or her own benefit. T-Chain also provides barrier-free entry to newcomers with flexible resource allocation, providing them with immediate benefits, and therefore is suitable for dynamic environments with high churn (i.e., Turnover). TChain is distributed and simple to implement, as no trusted third party is required to monitor or enforce the scheme, nor is there any reliance on reputation information or tokens.

Optimal CSMA, which is fully distributed wireless MAC theory, has provided a rule of dynamically adapting CSMA parameters according to some theoretically developed principles, and has reported to offer nice analytical guarantees on throughput and fairness. Despite a couple of research efforts that transfer Optimal CSMA to practical protocols, e.g., O-DCF, our evaluation results show that they are still far from being deployable in practice mainly due to bad performance with TCP. In this paper, we first investigate how Optimal CSMA based MAC conflicts with TCP and degrades end-to-end performance, if poorly transferred to practice. Then, we propose a new wireless MAC protocol, called A-DCF, that inherits the basic framework and rationale of Optimal CSMA and O-DCF, but are largely redesigned to make A-DCF work well with TCP. The key idea of A-DCF lies in smartly exploiting both queue length and delay which widens our design space for compatibility with TCP. Our extensive simulation and experimental results demonstrate that A-DCF outperforms the traditional 802.11 and O-DCF. Particularly, we report our implementation code of A-DCF as a device driver module. To our knowledge, it is the first driver-level implementation of an Optimal CSMA based MAC protocol, being of broad interest to the community.

We study how an innovation (e.g., product or technology) diffuses over a social network when individuals strategically make selfish, rational choices in adopting the new innovation. This diffusion has been studied by modeling individuals' interactions with a noisy best response dynamic over a networked coordination game, but mainly in the nonprogressive setup. In this paper, we study the case when people are progressive, i.e., never going back to the old technology once the new technology is chosen, where such a progressive behavior is explained using the notion of sunk cost fallacy in social psychology. Our main focus is on the diffusion time, i.e., time till all choose the new innovation. To this end, we first provide a combinatorial characterization of the diffusion time that corresponds to the time reaching the absorbing state in a Markov chain. Based on this, we propose a polynomial-time algorithm that computes the diffusion time, where such a task is known to be computationally intractable in the non-progressive diffusion. Second, we asymptotically quantify the diffusion times for a class of well-known social graph topologies, and compare them to those under the non-progressive diffusion. Finally, we study the impact of seeding to speed up the diffusion in the progressive setup, and show that the diffusion speed is impossible to significantly accelerate with just a small-budget seeding, which is in part in stark contrast to that in the non-progressive diffusion. Our results provide not only understandings on the progressive strategic diffusion in a social network, but also computational tractability on other related problems, e.g., seeding, which we believe should be of broader interest in the future.

Delay-tolerant Wi-Fi offloading is known to improve overall mobile network bandwidth at low delay and low cost. Yet, in reality, we rarely find mobile apps that fully support opportunistic Wi-Fi access. This is mainly because it is still challenging to develop delay-tolerant mobile apps due to the complexity of handling network disruptions and delays.

Carrier sense multiple access (CSMA), which resolves contentions over wireless networks in a fully distributed fashion, has recently gained a lot of attentions since it has been proved that appropriate control of CSMA parameters guarantees optimality in terms of stability (i.e., scheduling) and system-wide utility (i.e., scheduling and congestion control). Most CSMA-based algorithms rely on the popular Markov chain Monte Carlo technique, which enables one to find optimal CSMA parameters through iterative loops of simulation-and-update. However, such a simulation-based approach often becomes a major cause of exponentially slow convergence, being poorly adaptive to flow/topology changes. In this paper, we develop distributed iterative algorithms which produce approximate solutions with convergence in polynomial time for both stability and utility maximization problems. In particular, for the stability problem, the proposed distributed algorithm requires, somewhat surprisingly, only one iteration among links. Our approach is motivated by the Bethe approximation (introduced by Yedidia, Freeman, and Weiss) allowing us to express approximate solutions via a certain nonlinear system with polynomial size. Our polynomial convergence guarantee comes from directly solving the nonlinear system in a distributed manner, rather than multiple simulation-and-update loops in existing algorithms. We provide numerical results to show that the algorithm produces highly accurate solutions and converges much faster than the prior ones.

In this paper, a joint optimization of link scheduling, routing and replication for delay-tolerant networks (DTNs) has been studied. The optimization problems for resource allocation in DTNs are typically solved using dynamic programming which requires knowledge of future events such as meeting schedules and durations. This paper defines a new notion of approximation to the optimality for DTNs, called snapshot approximation where nodes are not clairvoyant, i.e., not looking ahead into future events, and thus decisions are made using only contemporarily available knowledges. Unfortunately, the snapshot approximation still requires solving an NP-hard problem of maximum weighted independent set (MWIS) and a global knowledge of who currently owns a copy and what their delivery probabilities are. This paper proposes an algorithm, Max-Contribution (MC) that approximates MWIS problem with a greedy method and its distributed online approximation algorithm, Distributed Max-Contribution (DMC) that performs scheduling, routing and replication based only on locally and contemporarily available information. Through extensive simulations based on real GPS traces tracking over 4,000 taxies and 500 taxies for about 30 days and 25 days in two different large cities, DMC is verified to perform closely to MC and outperform existing heuristically engineered resource allocation algorithms for DTNs.

This paper considers a hybrid peer-to-peer (p2p) system, a dynamic distributed caching system with an authoritative server dispensing contents only if the contents fail to be found by searching an unstructured p2p system. We study the case when some peers may not be fully cooperative in the search process and examine the impact of various noncooperative behaviors in the aspect of scalability, more specifically average server load and average peer load as the peer population size increases. We categorize selfish peers into three classes: impatient peers that directly query the server without searching the p2p system, non-forwarders that refuse to forward query requests, and non-resolvers that refuse to share contents. It is shown that in the hybrid p2p system, impatient and/or non-forwarding behaviors prevent the system from scaling well because of the high server load, while the system scales well under the non-resolving selfish peers. Our study implies that the hybrid p2p system does not mandate an incentive mechanism for content sharing, which is in stark contrast to unstructured p2p systems, where incentivizing peers to share contents is known to be a key factor for the system's scalability.

The CDN (Content Delivery Network) market consists of content providers (CPs), Internet service providers (ISPs), and CDN providers and evolves based on their complex cooperation and competition. Recently, the rapid growth of content-oriented traffic has brought forth a new entity called Telco CDNs in the content delivery supply chain, where Telco CDNs are the ISP-operated CDN providers, vertically integrating content delivery service with traffic engineering, so as to provide better reliability and QoS to users and reduce infrastructure investments. Telco CDNs and traditional CDNs would compete for their market shares with their unique advantages: Telco CDNs are capable of jointly optimizing network costs and user-perceived QoS, but possibly with their geographical limitation in service areas, whereas traditional CDNs operate a network of servers worldwide, with the advantages of performing global, sophisticated analytics or providing better security solutions. Telco CDNs may form an alliance (e.g., cache server sharing) to compete with traditional CDNs, but with some alliance cost. With this CDN market evolution, this paper conducts a game-theoretic study of when and how traditional CDNs survive in the competition with Telco CDNs. In particular, our study answers the questions about the impact of Telco CDNs' unique characteristics on the long-term competition against traditional CDNs, and the impact of Telco CDNs' alliance. Our analysis provides useful implications on the economics of the future CDN market, e.g., what factors can be Achilles' heel and thus what features should be more focused for Telco and traditional CDNs.

Rate Adaptation (RA) is a fundamental mechanism in 802.11 systems. It allows transmitters to adapt the coding and modulation scheme as well as the MIMO transmission mode to the radio channel conditions, and in turn, to learn and track the (mode, rate) pair providing the highest throughput. So far, the design of RA mechanisms has been mainly driven by heuristics. In contrast, in this paper, we rigorously formulate such design as an online stochastic optimisation problem. We solve this problem and present ORS (Optimal Rate Sampling), a family of (mode, rate) pair adaptation algorithms that provably learn as fast as it is possible the best pair for transmission. We study the performance of ORS algorithms in stationary radio environments where the successful packet transmission probabilities at the various (mode, rate) pairs do not vary over time, and in non-stationary environments where these probabilities evolve. We show that under ORS algorithms, the throughput loss due to the need to explore sub-optimal (mode, rate) pairs does not depend on the number of available pairs. This is a crucial advantage as evolving 802.11 standards offer an increasingly large number of (mode, rate) pairs. We illustrate the efficiency of ORS algorithms (compared to the state-of-the-art algorithms) using simulations and traces extracted from 802.11 test-beds.

Game-theoretic modeling and equilibrium analysis have provided valuable insights into the design of robust local control rules for the individual agents in multi-agent systems, e.g., Internet congestion control, road transportation networks, etc. In this paper, we introduce a non-cooperative MAC (Medium Access Control) game for wireless networks and propose new fully-distributed CSMA (Carrier Sense Multiple Access) learning algorithms that are probably optimal in the sense that their long-term throughputs converge to the optimal solution of a utility maximization problem over the maximum throughput region. The most significant part of our approach lies in introducing a novel cost function in agents' utilities so that the proposed game admits an ordinal potential function with (asymptotically) no price-of-anarchy. The game formulation naturally leads to known game-based learning rules to find a Nash equilibrium, but they are computationally inefficient and often require global information. Towards our goal of fully-distributed operation, we propose new fully-distributed learning algorithms by utilizing a unique property of CSMA that enables each link to estimate its temporary link throughput without message passing for the applied CSMA parameters. The proposed algorithms can be thought as `stochastic approximations' to the standard learning rules, which is a new feature in our work, not prevalent in other traditional game-theoretic approaches. We show that they converge to a Nash equilibrium, which is a utility-optimal point, numerically evaluate their performance to support our theoretical findings and further examine various features such as convergence speed and its tradeoff with efficiency.

In the past few years, an exciting progress has been made on CSMA (Carrier Sense Multiple Access) algorithms that achieve throughput and utility optimality for wireless networks. However, most of these algorithms are known to exhibit poor delay performance making them impractical for implementation. Recently, several papers have addressed the delay issue of CSMA and yet, most of them are limited, in the sense that they focus merely on specific network scenarios with certain conditions rather than general network topology, achieve low delay at the cost of throughput reduction, or lack rigorous provable guarantees. In this paper, we focus on the recent idea of exploiting multiple channels (actually or virtually) for delay reduction in CSMA, and prove that it isper-link delay orderoptimal, i.e.,O(1)-asymptotic-delay per link, if the number of virtual channels is logarithmic with respect to mixing time of the underlying CSMA Markov chain. The logarithmic number is typically small, i.e., at most linear with respect to the network size. In other words, our contribution provides not only a provable framework for the multiple-channel based CSMA, but also the required explicit number of virtual-multi-channels, which is of great importance for actual implementation. The key step of our analytic framework lies in using quadratic Lyapunov functions in conjunction with (recursively applying) Lindley equation and Azuma's inequality for obtaining an exponential decaying property in certain queueing dynamics. We believe that our technique is of broad interest in analyzing the delay performances of other general queueing systems.

A variety of models have been proposed and analyzed to understand how a new innovation (e.g., a technology, a product, or even a behavior) diffuses over a social network, broadly classified into either of epidemic-based or game-based ones. In this paper, we consider a game-based model, where each individual makes a selfish, rational choice in terms of its payoff in adopting the new innovation, but with some noise. We study how diffusion effect can be maximized by seeding a subset of individuals (within a given budget), i.e., convincing them to pre-adopt a new innovation. In particular, we aim at finding `good' seeds for minimizing the time to infect all others, i.e., diffusion speed maximization. To this end, we design polynomial-time approximation algorithms for three representative classes, Erdőos-Réenyi, planted partition and geometrically structured graph models, which correspond to globally well-connected, locally well-connected with large clusters and locally well-connected with small clusters, respectively, provide their performance guarantee in terms of approximation and complexity. First, for the dense Erdős-Rényi and planted partition graphs, we show that an arbitrary seeding and a simple seeding proportional to the size of clusters are almost optimal with high probability. Second, for geometrically structured sparse graphs, including planar and d-dimensional graphs, our algorithm that (a) constructs clusters, (b) seeds the border individuals among clusters, and (c) greedily seeds inside each cluster always outputs an almost optimal solution. We validate our theoretical findings with extensive simulations under a real social graph. We believe that our results provide new practical insights on how to seed over a social network depending on its connection structure, where individuals rationally adopt a new innovation. To our best knowledge, we are the first to study such diffusion speed maximization on the game-based diffusion, while the extensive research efforts have been made in epidemic-based models, often referred to as influence maximization.

Both users and mobile network providers increasingly suffer from explosive growth of mobile traffic. We study socalled delayed Wi-Fi offloading that has been recently proposed as a low-cost solution of alleviating mobile data explosion. Delayed Wi-Fi offloading is a technology that offloads traffic from cellular to Wi-Fi by persuading users into delaying their delay-tolerant traffic and thus actively exploiting users' chance to meet Wi-Fi. In this paper, we study the economic effects of such user-oriented delayed Wi-Fi offloading in the monopoly market as well as the market with two providers. In the monopoly market, we model a two-stage game, where the provider selects an offloading price for which users are the price-takers. In the market with two providers, we consider a situation that either of providers, say A, launches a delayed Wi-Fi offloading service as a separate service from the original cellular service, thus allowing the users in another provider, say B, to subscribe to the offloading service from A, but with some incurring switching cost. In both markets, we study how the equilibrium offloading price changes depending on other system parameters, e.g., cellular cost, Wi-Fi density, and the number of subscribers, by computing the Nash equilibriums and providing extensive numerical results for various parameter changes, which gives us useful insights into how economically viable user-oriented delayed Wi-Fi offloading is.

This paper studies an incentive structure for cooperation and its stability in peer-assisted services when there exist multiple content providers, using a coalition game-theoretic approach. We first consider a generalized coalition structure consisting of multiple providers with many assisting peers, where peers assist providers to reduce the operational cost in content distribution. To distribute the profit from cost reduction to players (i.e, providers and peers), we then establish a generalized formula for individual payoffs when a “Shapley-like” payoff mechanism is adopted. We show that the grand coalition is unstable, even when the operational cost functions are concave, which is in sharp contrast to the recently studied case of a single provider where the grand coalition is stable. We also show that irrespective of stability of the grand coalition, there always exist coalition structures that are not convergent to the grand coalition under a dynamic among coalition structures. Our results give us an incontestable fact that a provider does not tend to cooperate with other providers in peer-assisted services and is separated from them. Three facets of the noncooperative (selfish) providers are illustrated: 1) underpaid peers; 2) service monopoly; and 3) oscillatory coalition structure. Lastly, we propose a stable payoff mechanism that improves fairness of profit sharing by regulating the selfishness of the players as well as grants the content providers a limited right of realistic bargaining. Our study opens many new questions such as realistic and efficient incentive structures and the tradeoffs between fairness and individual providers' competition in peer-assisted services.

Cellular networks are facing severe traffic overloads due to the proliferation of smart handheld devices and traffic-hungry applications. A cost-effective and practical solution is to offload cellular data through WiFi. Recent theoretical and experimental studies show that a scheme, referred to as delayed WiFi offloading, can significantly save the cellular capacity by delaying users' data and exploiting mobility and thus increasing chance of meeting WiFi APs (Access Points). Despite a huge potential of WiFi offloading in alleviating mobile data explosion, its success largely depends on the economic incentives provided to users and operators to deploy and use delayed offloading. In this paper, we study how much economic benefits can be generated due to delayed WiFi offloading, by modeling the interaction between a single provider and users based on a two-stage sequential game. We first analytically prove that WiFi offloading is economically beneficial for both the provider and users. Also, we conduct trace-driven numerical analysis to quantify the practical gain, where the increase ranges from 21% to 152% in the providers revenue, and from 73% to 319% in the users surplus.

An essential condition precedent to the success of mobile applications based on Wi-Fi (e.g., iCloud) is an energy-efficient Wi-Fi sensing. From a user's perspective, a good WiFi sensing policy should depend on both inter-AP arrival and contact duration time distributions. Prior work focuses on limited cases of those two distributions (e.g., exponential) or introduces heuristic approaches such as AI (Additive Increase). In this paper, we formulate a functional optimization problem on Wi-Fi sensing under general inter-AP and contact duration distributions, and propose how each user should sense Wi-Fi APs to strike a balance between energy efficiency and performance, depending on the users' mobility pattern. To that end, we derive an optimal condition which sheds insights into the aging property, the key feature required by efficient Wi-Fi sensing polices. Guided by the analytical studies and the implications, we develop a new sensing algorithm, called WiSAG (Wi-Fi Sensing with AGing), which is demonstrated to outperform the existing sensing algorithms up to 34% through extensive trace-driven simulations using the real mobility traces gathered from smartphones.

This paper studies how global information affects the diffusion of innovations on a network. The diffusion of innovation is modeled by the logit dynamics of a weighted N-person coordination game among (bounded) rational users where innovations spread through users' strategic choices. We find a critical asymptotic threshold for the weight on global information where the diffusion of innovations undergoes a transition in the rate of convergence regardless of any network structure. In particular, it is found that the convergence to the pervasive adoption is slowed down by global information.

This paper considers a hybrid peer-to-peer (p2p) system, a dynamic distributed caching system with an authoritative server dispensing contents only if the contents fail to be found by searching an unstructured peer-to-peer (p2p) system. We study the case when some peers may not be fully cooperative in the search process and examine the impact of various noncooperative behaviors on the querying load on the server as the peer population size increases. We categorize selfish peers into three classes: impatient peers that directly query the server without searching the p2p system, non-forwarders that refuse to forward query requests, and non-resolvers that refuse to share contents. It is shown that in the hybrid p2p system, impatient and/or nonforwarding behaviors prevent the system from scaling well because of the high server load, while the system scales well under the non-resolving selfish peers. Our study implies that the hybrid p2p system does not mandate an incentive mechanism for content sharing, which is in stark contrast to unstructured p2p systems, where incentivizing peers to share contents is known to be a key factor for the system's scalability.

The Internet consists of economically selfish players in terms of access/transit connection, content distribution, and users. Such selfish behaviors often lead to techno-economic inefficiencies such as unstable peering and revenue imbalance. Recent research results suggest that cooperation in revenue sharing (thus multi-level ISP settlements) can be a candidate solution for the problem of unfair revenue share. However, it is unclear whether providers are willing to behave cooperatively. In this paper, we study the interaction between how content-oriented traffic scheduling at the edge is and how stable the intended cooperation is. We consider three traffic scheduling policies having various degrees of content-value preference, compare them in terms of implementation complexity, network neutrality, and stability of cooperation, and present interesting trade-offs among them.

Cellular networks are facing severe traffic overloads due to the proliferation of smart handheld devices and traffichungry applications. A cost-effective and practical solution is to offload cellular data through WiFi. Recent theoretical and experimental studies show that a scheme, referred to as delayed WiFi offloading, can significantly save the cellular capacity by delaying users' data and exploiting mobility and thus increasing chance of meeting WiFi APs (Access Points). Despite a huge potential of WiFi offloading in alleviating mobile data explosion, its success largely depends on the economic incentives provided to users and network providers to deploy and use delayed offloading. In this paper, we study how much economic benefits can be generated due to delayed WiFi offloading, by modeling the interaction between a single provider and users based on a two-stage sequential game. We first analytically prove that WiFi offloading is economically beneficial for both the provider and users. Also, we conduct trace-driven numerical analysis to quantify the practical gain, where the increase ranges from 21 to 152% in the provider's revenue, and from 73 to 319% in the users' surplus.

CSMA (Carrier Sense Multiple Access), which resolves contentions over wireless networks in a fully distributed fashion, has recently gained a lot of attentions since it has been proved that appropriate control of CSMA parameters guarantees optimality in terms of system-wide utility. Most algorithms rely on the popular MCMC (Markov Chain Monte Carlo) technique, which enables one to find optimal CSMA parameters through iterative loops of simulation-and-update. However, such a simulation-based approach often becomes a major cause of exponentially slow convergence, being poorly adaptive to flow/topology changes. In this paper, we develop a distributed iterative algorithm which produces approximate solutions with convergence in polynomial time. Our approach is motivated by a scheme in statistical physics, referred to as the Bethe approximation, allowing us to express approximate solutions via a certain non-linear system with polynomial size. We provide numerical results to show that the algorithm produces highly accurate solutions and converges much faster than prior ones.

Recent studies on MAC scheduling have shown that carrier sense multiple access (CSMA) algorithms can be throughput optimal for arbitrary wireless network topology. However, these results are highly sensitive to the underlying assumption on `static' or `fixed' system conditions. For example, if channel conditions are time-varying, it is unclear how each node can adjust its CSMA parameters, so-called backoff and channel holding times, using its local channel information for the desired high performance. In this paper, we study `channel-aware' CSMA (A-CSMA) algorithms in time-varying channels, where they adjust their parameters as some function of the current channel capacity. First, we show that the achievable rate region of A-CSMA equals to the maximum rate region if and only if the function is exponential. Furthermore, given an exponential function in A-CSMA, we design updating rules for their parameters, which achieve throughput optimality for an arbitrary wireless network topology. They are the first CSMA algorithms in the literature which are proved to be throughput optimal under time-varying channels. Moreover, we also consider the case when back-off rates of A-CSMA are highly restricted compared to the speed of channel variations, and characterize the throughput performance of A-CSMA in terms of the underlying wireless network topology. Our results not only guide a high-performance design on MAC scheduling under highly time-varying scenarios, but also provide new insights on the performance of CSMA algorithms in relation to their backoff rates and underlying network topologies.

This paper proposes a new wireless MAC protocol called Optimal DCF (O-DCF). O-DCF modifies the rule of adapting CSMA parameters, such as backoff time and transmission length, based on a function of the supply-demand differential captured by the local queue length. O-DCF is fully compatible with 802.11 hardware, so that it can be easily implemented only with a simple device driver update. O-DCF is inspired by the recent theoretical studies on queue-based CSMA for high throughput and fairness. O-DCF effectively bridges the gap between theory and practice, implemented and tested in an off-the-shelf 802.11 chipset. Through extensive simulations and real experiments with a 16-node wireless network testbed, we evaluate the performance of O-DCF and show that it outperforms other competitive ones, such as 802.11 DCF, optimal CSMA, and DiffQ for various scenarios.

Delay-capacity tradeoffs for mobile networks have been analyzed through a number of research works. However, Lévy mobility known to closely capture human movement patterns has not been adopted in such work. Understanding the delay-capacity tradeoff for a network with Lévy mobility can provide important insights into understanding the performance of real mobile networks governed by human mobility. This paper analytically derives an important point in the delay-capacity tradeoff for Lévy mobility, known as the critical delay. The critical delay is the minimum delay required to achieve greater throughput than what conventional static networks can possibly achieve (i.e., O(1/√n) per node in a network with n nodes). The Lévy mobility includes Lévy flight and Lévy walk whose step-size distributions parametrized by α ∈ (0,2] are both heavy-tailed while their times taken for the same step size are different. Our proposed technique involves: 1) analyzing the joint spatio-temporal probability density function of a time-varying location of a node for Lévy flight, and 2) characterizing an embedded Markov process in Lévy walk, which is a semi-Markov process. The results indicate that in Lévy walk, there is a phase transition such that for α ∈ (0,1), the critical delay is always Θ(n[1/2]), and for α ∈ [1,2] it is Θ(n[(α)/2]). In contrast, Lévy flight has the critical delay Θ(n[(α)/2]) for α ∈ (0,2].

This paper presents a quantitative study on the performance of 3G mobile data offloading through WiFi networks. We recruited 97 iPhone users from metropolitan areas and collected statistics on their WiFi connectivity during a two-and-a-half-week period in February 2010. Our trace-driven simulation using the acquired whole-day traces indicates that WiFi already offloads about 65% of the total mobile data traffic and saves 55% of battery power without using any delayed transmission. If data transfers can be delayed with some deadline until users enter a WiFi zone, substantial gains can be achieved only when the deadline is fairly larger than tens of minutes. With 100-s delays, the achievable gain is less than only 2%-3%, whereas with 1 h or longer deadlines, traffic and energy saving gains increase beyond 29% and 20%, respectively. These results are in contrast to the substantial gain (20%-33%) reported by the existing work even for 100-s delayed transmission using traces taken from transit buses or war-driving. In addition, a distribution model-based simulator and a theoretical framework that enable analytical studies of the average performance of offloading are proposed. These tools are useful for network providers to obtain a rough estimate on the average performance of offloading for a given WiFi deployment condition.

As high-speed networks are becoming commonplace, it is increasingly challenging to prevent the attack attempts at the edge of the Internet. While many high-performance intrusion detection systems (IDSes) employ dedicated network processors or special memory to meet the demanding performance requirements, it often increases the cost and limits functional flexibility. In contrast, existing software-based IDS stacks fail to achieve a high throughput despite modern hardware innovations such as multicore CPUs, manycore GPUs, and 10 Gbps network cards that support multiple hardware queues.

Glauber dynamics, a method of sampling a given probability distribution via a Markov chain, has recently made considerable contribution to the MAC scheduling research, providing a tool to solve a long-standing open issue - achieving throughput-optimality with light message passing under CSMA. In this paper, we propose a way of reducing delay by studying generalized Glauber dynamics parameterized by βϵ[0, 1], ranging from Glauber dynamics (β=0) to the Metropolis algorithm (β =1). The same stationary distribution is sustained across this generalization, thus maintaining the long-term optimality. However, a different choice of β results in a significantly different second-order behavior (or variability) that has large impact on delay, which is hardly captured by the recent research focusing on delay in the large n (the number of nodes) asymptotic. We formally study such second-order behavior and its resulting delay performance, and show that larger β achieves smaller delay. Our results provide new insight into how to operate CSMA for large throughput and small delay in real, finite-sized systems.

Femtocells are a promising technology for handling exponentially increasing wireless data traffic. Although extensive attention has been paid to resource control mechanisms, for example, power control and load balancing in femtocell networks, their success largely depends on whether operators and users accept this technology or not. In this paper, we study the economic aspects of femtocell services for the case of monopoly market, and aim to answer questions on operator's revenue, user surplus, and social welfare by considering practical service types and pricing strategies. We consider three user subscription services, that is, users can access only macro BSs (mobile-only), or deploy femto BSs in their house and open / exclusively use their femto BSs (open- / closed-femto). For pricing strategies, flat pricing and partial volume pricing are exploited. The main messages include the following: 1) open-femto service is beneficial to both users and providers; 2) in flat pricing, the impact on operator revenue of allowing or blocking the access of mobile-only users to open femto BSs is minor; and 3) compared with partial volume pricing, flat pricing is advantageous to the operator when users are sensitive to price.

DSL broadband access suffers from crosstalk among different lines within the same cable bundle. Dynamic spectrum management (DSM) refers to a set of techniques to mitigate the impact of crosstalk leading to spectacular performance gains. DSM research has mainly aimed at physical layer performance metrics, such as data rates and transmit powers. However, for many applications higher-layer performance metrics, such as throughput and delay, may be much more important to improve user satisfaction. In this paper, we provide a cross-layer DSM framework to study throughput and delay performance by looking at scheduling and DSM together. We show how optimal scheduling can be combined with both optimal and suboptimal DSM and provide throughput-optimal scheduling algorithms which require only polynomial complexity. We analytically study the impact on delay performance of achieving throughput-optimality with suboptimal DSM compared to optimal DSM. We then present extensions that significantly improve delay performance by exploiting the specific structure of the problem, such as the temporal-spectral correlation property. Furthermore, we propose a second cross-layer DSM framework that achieves throughput-optimal scheduling with suboptimal DSM, but in addition also significantly reduces overall power consumption. Finally, we analyze and quantify the tradeoff between throughput, delay and power consumption for concrete DSL scenarios.

Greening effect in interference management (IM), a way of enhancing spectrum sharing via intelligent transmit power control, can be achieved by the fact that as BSs moderately reduce their transmit powers, the performance degradation decreases slower than linearly, yet a considerable overall energy saving is expected due to transmit powers' exerting influence on operational power. This paper investigates the impact of different spatial and/or temporal power sharing policies for a given system-wide power budget in IM schemes. We develop an optimization-theoretic IM framework on cellular network greening, from which we first develop four IM schemes governed by different power sharing: no sharing, only temporal sharing, only spatial sharing, and both spatial and temporal sharing. Through extensive simulations, including a real BS deployment in Manchester city, United Kingdom, we obtain the following interesting observations: (i) the gains both from performance and power saving are obtained by adopting the spatial and/or temporal power sharing policies, (ii) tighter greening regulation (i.e., smaller total power budget) leads to higher spatio-temporal power sharing gain than IM gain, (iii) spatial power sharing significantly excels temporal one in terms of power saving, and (iv) higher greening efficiency can be achieved as the cell size becomes smaller.

In order to utilize network resources efficiently and reduce regional congestion, associating mobile stations (MSs) with proper base stations (BSs) is of crucial importance in wireless cellular networks. There have been several load-aware proposals in literature, where most are classified into so-called closed-form approaches. In such approaches, each MS independently and deterministically selects the BS which is expected to provide the highest throughput. The throughput is estimated by a closed-form equation based on the assumption of the Proportional Fair (PF) user scheduler that ensures temporal fairness. However, the closed-form approaches do not perform well when the closed-form equation is not available, e.g., general α-fair user scheduler, where temporal fairness is not guaranteed, or deterministic BS association may make wrong decisions, e.g., under the dynamics of mobility or flow arrivals/departures. In this paper, we propose a novel BS association scheme, called ViSE (Virtual Scheduling based Emulation) to tackle such challenges. It emulates an optimal BS association by running a notion of virtual scheduler, and each MS randomly determines its associated BS with the probability proportional to the throughput virtually allocated by the virtual scheduler. We demonstrate through extensive simulations under various practical scenarios that ViSE outperforms the existing algorithms in terms of user schedulers with diverse fairness and robustness to network dynamics.

This paper analytically derives the delay-capacity tradeoffs for Lévy mobility: Lévy walks and Lévy flights. Lévy mobility is a random walk with a power-law flight distribution. α is the power-law slope of the distribution and 01/2) and for 1 ≤ α ≤ 2, is Θ(nα/2). In contrast, Lévy flight has critical delay Θ(nα/2) for 0 <; α ≤ 2.

By `optimal CSMA' we denote a promising approach to maximize throughput-based utility in wireless networks without message passing or synchronization among nodes. Despite the theoretical guarantees on the performance of these protocols, their evaluation in real networking scenarios has been preliminary. In this paper, we propose a methodical approach for the first comprehensive evaluation of optimal CSMA, via experimentation with a custom implementation. Example findings include; 1) hidden terminals with symmetric channels can drive the protocol to a state of extreme contention aggressiveness due to the low service received by flows. Since increasing aggressiveness does not mitigate collisions but actually aggravates them, optimal CSMA enters a positive-feedback loop eventually reaching a deadlock state of total flow starvation; 2) however, the use of RTS/CTS in such scenarios can reduce collisions to lower levels, restoring throughput and preventing an excessive contention aggressiveness by optimal CSMA flows; 3) in practical hidden terminal scenarios with physical layer capture optimal CSMA reduces the aggressiveness of dominant flows, but the contention window sizes used by such adaptation mechanism are not long enough to solve competing flows' starvation when carrier sensing fails; 4) topologies with a “flow-in-the-middle” yield starvation in traditional CSMA but fairness in optimal CSMA, because its contention aggressiveness adaptation creates frequent transmission opportunities for the central (otherwise starved) flow; 5) optimal CSMA excessively prioritizes links with low channel quality, due to queue-based control that does not otherwise incorporate channel conditions; 6) in its current design, optimal CSMA conflicts with window-based end-to-end congestion control, and leads to a efficiency-fairness tradeoff in TCP performance. This study deepens our understanding of optimal CSMA and the general adaptation philosophy behind its design, and the derived insights suggest enhancements to optimal CSMA theory.

The femtocell is an enabling technology to handle exponentially increasing wireless data traffic. Despite extensive attentions paid to resource control, e.g., power control and load balancing in femtocell networks, the success largely depends on whether operators and users accept this technology or not. In this paper, we study the economic aspects of femtocell services with game theoretic models between providers and/or users. We consider three services: users can access only macro BSs (mobile-only), or open/exclusively use their femto BS (open or closed-femto). The main messages include: 1) it is better off for the operator to provide just the open-femto service than a mix of closed and open-femto services; 2) two polices of allowing or blocking the access of mobile-only users to open femto BS are not significantly differentiated in the revenue.

Greening effect in interference management (IM), which is a technology to enhance spectrum sharing via intelligent BS transmit power control, can be achieved by the fact that even small reduction in BS transmit powers enables considerable saving in overall energy consumption due to their exerting influence on operational powers. In this paper, we study the impact of power sharing policies in IM schemes on cellular network greening, where different spatio-temporal power sharing policies are considered for a fixed system-wide power budget. This study is of great importance in that the pressure on the CO2emission limit per nation increases, e.g., by Kyoto protocol, which will ultimately affect the power budget of a wireless service provider. We propose optimization theoretic IM frameworks with greening, from which we first develop four IM schemes with different power sharing policies. Through extensive simulations under various configurations, including a real BS deployment in Manchester city, United Kingdom, we obtain the following interesting observations: (i) tighter greening regulation (i.e., the smaller total power budget) leads to higher spatio-temporal power sharing gain than IM gain, (ii) spatial power sharing significantly excels temporal one, and (iii) more greening gain can be achieved as the cell size becomes smaller.

Energy-efficiency, one of the major design goals in wireless cellular networks, has received much attention lately, due to increased awareness of environmental and economic issues for network operators. In this paper, we develop a theoretical framework for BS energy saving that encompasses dynamic BS operation and the related problem of user association together. Specifically, we formulate a total cost minimization that allows for a flexible tradeoff between flow-level performance and energy consumption. For the user association problem, we propose an optimal energy-efficient user association policy and further present a distributed implementation with provable convergence. For the BS operation problem (i.e., BS switching on/off), which is a challenging combinatorial problem, we propose simple greedy-on and greedy-off algorithms that are inspired by the mathematical background of submodularity maximization problem. Moreover, we propose other heuristic algorithms based on the distances between BSs or the utilizations of BSs that do not impose any additional signaling overhead and thus are easy to implement in practice. Extensive simulations under various practical configurations demonstrate that the proposed user association and BS operation algorithms can significantly reduce energy consumption.

Due to the increasing demand of capacity in wireless cellular networks, the small cells such as pico and femto cells are becoming more popular to enjoy a spatial reuse gain, and thus cells with different sizes are expected to coexist in a complex manner. In such a heterogeneous environment, the role of interference management (IM) becomes of more importance, but technical challenges also increase, since the number of cell-edge users, suffering from severe interference from the neighboring cells, will naturally grow. In order to overcome low performance and/or high complexity of existing static and other dynamic IM algorithms, we propose a novel low-complex and fully distributed IM scheme, called REFIM (REFerence based Interference Management), in the downlink of heterogeneous multi-cell networks. We first formulate a general optimization problem that turns out to require intractable computation complexity for global optimality. To have a practical solution with low computational and signaling overhead, which is crucial for low-cost small-cell solutions, e.g., femto cells, in REFIM, we decompose it into per-BS (base station) problems based on the notion of reference user and reduce feedback overhead over backhauls both temporally and spatially. We evaluate REFIM through extensive simulations under various configurations, including the scenarios from a real deployment of BSs. We show that, compared to the schemes without IM, REFIM can yield more than 40% throughput improvement of cell-edge users while increasing the overall performance by 10~107%. This is equal to about 95% performance of the existing centralized IM algorithm (MC-IIWF) that is known to be near-optimal but hard to implement in practice due to prohibitive complexity. We also present that as long as interference is managed well, the spectrum sharing policy can outperform the best spectrum splitting policy where the number of subchannels is optimally divided between macro and femto cells.

Achieving sufficient spatial capacity gain through the use of small cells requires careful consideration of inter-cell interference (ICI) management via BS power coordination coupled with user scheduling inside cells. Optimal algorithms are known to be difficult to implement due to high computation and signaling overhead. This study proposes joint pattern-based ICI management and user scheduling algorithms that are practically implementable. The key idea is to decompose the original problem into two sub-problems in which ICI management is run at a slower time scale than user scheduling. We empirically show that even with such a slow tracking of system dynamics at the ICI management part, the decomposed approach achieves a considerable performance increase compared to conventional universal reuse schemes.

This paper presents a quantitative study on the performance of 3G mobile data offloading through WiFi networks. We recruited about 100 iPhone users from metropolitan areas and collected statistics on their WiFi connectivity during about a two and half week period in February 2010. Our trace-driven simulation using the acquired traces indicates that WiFi already offloads about 65% of the total mobile data traffic and saves 55% of battery power without using any delayed transmission. If data transfers can be delayed with some deadline until users enter a WiFi zone, substantial gains can be achieved only when the deadline is fairly larger than tens of minutes. With 100 second delays, the achievable gain is less than only 2--3%. But with 1 hour or longer deadline, traffic and energy saving gains increase beyond 29% and 20%, respectively. These results are in stark contrast to the substantial gain (20 to 33%) reported by the existing work even for 100 second delayed transmission using traces taken from transit buses or war-driving. The major performance difference comes from traces: while bus and war-driving traces contain much shorter connection and inter-connection times, our traces reflects the daily mobility patterns of average users more accurately.

This is by far the first paper considering joint optimization of link scheduling, routing and replication for disruption-tolerant networks (DTNs). The optimization problems for resource allocation in DTNs are typically solved using dynamic programming which requires knowledge of future events such as meeting schedules and durations. This paper defines a new notion of optimality for DTNs, called snapshot optimality where nodes are not clairvoyant, i.e., cannot look ahead into future events, and thus decisions are made using only contemporarily available knowledge. Unfortunately, the optimal solution for snapshot optimality still requires solving an NP-hard problem of maximum weight independent set and a global knowledge of who currently owns a copy and what their delivery probabilities are. This paper presents a new efficient approximation algorithm, called Distributed Max-Contribution (DMC) that performs greedy scheduling, routing and replication based only on locally and contemporarily available information. Through a simulation study based on real GPS traces tracking over 4000 taxies for about 30 days in a large city, DMC outperforms existing heuristically engineered resource allocation algorithms for DTNs.

We consider a widely applicable model of resource allocation where two sequences of events are coupled: on a continuous time axis (t), network dynamics evolve over time. On a discrete time axis [t], certain control laws update resource allocation variables according to some proposed algorithm. The algorithmic updates, together with exogenous events out of the algorithm's control, change the network dynamics, which in turn changes the trajectory of the algorithm, thus forming a loop that couples the two sequences of events. In between the algorithmic updates at [t-1] and [t], the network dynamics continue to evolve randomly as influenced by the previous variable settings at time [t-1]. The standard way used to avoid the subsequent analytic difficulty is to assume the separation of timescales, which in turn unrealistically requires either slow network dynamics or high complexity algorithms. In this paper, we develop an approach that does not require separation of timescales. It is based on the use of stochastic approximation algorithms with continuous-time controlled Markov noise. We prove convergence of these algorithms without assuming timescale separation. This approach is applied to develop simple algorithms that solve the problem of utility-optimal random access in multi-channel, multi-radio wireless networks.

This is a quantitative study on the performance of 3G mobile data offloading through WiFi networks. We recruited about 100 iPhone users from a metropolitan area and collected statistics on their WiFi connectivity during about a two and half week period in February 2010. We find that a user is in WiFi coverage for 70% of the time on average and the distributions of WiFi connection and disconnection times have a strong heavy-tail tendency with means around 2 hours and 40 minutes, respectively. Using the acquired traces, we run trace-driven simulation to measure offloading efficiency under diverse conditions e.g. traffic types, deadlines and WiFi deployment scenarios. The results indicate that if users can tolerate a two hour delay in data transfer (e.g, video and image up-loads), the network can offload 70% of the total 3G data traffic on average. We also develop a theoretical framework that permits an analytical study of the average performance of offloading. This tool is useful for network providers to obtain a rough estimate on the average performance of offloading for a given inputWiFi deployment condition.

Aggregate traffic loads and topology in multihop wireless networks may vary slowly, permitting MAC protocols to “learn” how to spatially coordinate and adapt contention patterns. Such an approach could reduce contention, leading to better throughput. To that end, we propose a family of MAC scheduling algorithms and demonstrate general conditions, which, if satisfied, ensure lattice rate optimality (i.e., achieving any rate-point on a uniform discrete lattice within the throughput region). This general framework enables the design of MAC protocols that meet various objectives and conditions. In this paper, as instances of such a lattice-rate-optimal family, we propose distributed, synchronous contention-based scheduling algorithms that: 1) are lattice-rate-optimal under both the signal-to-interference-plus-noise ratio (SINR)-based and graph-based interference models; 2) do not require node location information; and 3) only require three-stage RTS/CTS message exchanges for contention signaling. Thus, the protocols are amenable to simple implementation and may be robust to network dynamics such as topology and load changes. Finally, we propose a heuristic, which also belongs to the proposed lattice-rate-optimal family of protocols and achieves faster convergence, leading to a better transient throughput.

Abstract It has been recently suggested by Jiang and Walrand that adaptive carrier sense multiple access (CSMA) can achieve optimal utility without any message passing in wireless networks. In this paper, after a survey of recent work on random access, a generalization of this algorithm is considered. In the continuous‐time model, a proof is presented of the convergence of these adaptive CSMA algorithms to be arbitrarily close to utility optimality, without assuming that the network dynamics converge to an equilibrium in between consecutive CSMA parameter updates. In the more realistic, slotted‐time model, the impact of collisions on the utility achieved is characterized, and the tradeoff between optimality and short‐term fairness is quantified. Copyright © 2009 John Wiley & Sons, Ltd.

It has been recently suggested by Jiang andWalrand that adaptive carrier sense multiple access (CSMA) can achieve optimal utility without any message passing in wireless networks. In this paper, a generalization of this algorithm is considered. In the continuous-time model, a proof is presented of t

Dynamic spectrum management (DSM) has been recognized as a key technology for tackling multi-user crosstalk interference for DSL broadband access. Up to now, DSM design has mainly been focusing on maximization of data rates. However, recently, reducing the total power has become a main target, as IT power consumption has been identified as a significant contributor to global warming. In this paper we extend traditional DSM design towards a much wider energy-efficient scope and show how to tackle the corresponding optimization problems. The impact of this 'green DSL' approach is evaluated for practice with some surprisingly good numerical results. Furthermore bounds are provided on the trade-off between data rate performance and power saving.

Distributed scheduling algorithms for wireless ad hoc networks have received substantial attention over the last decade. The complexity levels of these algorithms span a wide spectrum, ranging from no message passing to constant/polynomial time complexity, or even exponential complexity. However, by and large it remains open to quantify the impact of message passing complexity on throughput and delay. In this paper, we study the effective throughput and delay performance in wireless scheduling by explicitly considering complexity through a vacation model, where signaling complexity is treated as "vacations" and data transmissions as "services," with a focus on delay analysis in heavy traffic regimes. We analyze delay performance in two regimes of vacation models, depending on the relative lengths of data transmission and vacation periods. State space collapse properties proved here enable a significant dimensionality reduction in the challenging problem of delay characterization. We then explore engineering implications and quantify intuitions based on the heavy traffic analysis.

Achieving sufficient spatial capacity gain by having small cells requires careful treatment of inter-cell interference (ICI) management via BS power coordination coupled with user scheduling inside cells. Optimal algorithms have been known to be hard to implement due to high computation and signaling overheads. We propose joint pattern-based ICI management and user scheduling algorithms that are practically implementable. The basic idea is to decompose the original problem into two sub-problems, where we run ICI management at a slower time scale than user scheduling. We empirically show that even with such a slow tracking of system dynamics at the ICI management part, the decomposed approach achieves high performance increase, compared to a conventional universal reuse scheme.

The flow-level stability and performance of data networks with utility-maximizing allocations are studied in this paper. Similarly to prior works on flow-level models, exogenous data arrivals with finite workloads are considered. However, to model many realistic situations, the rate region, which constrains the feasibility of resource allocation, may be either nonconvex or time-varying. When the rate region is fixed but nonconvex, sufficient and necessary conditions are characterized for stability for a class ofalpha-fair allocation policies, which coincide when the set of allocated rate vectors have continuous contours. When the rate region is time-varying according to a Markovian stationary and ergodic process, the precise stability region is obtained. In both cases, the size of the stability region depends on the resource allocation policy, in particular, on the fairness parameteralphainalpha-fair utility maximization. This is in sharp contrast with the substantial existing literature on stability under fixed and convex rate regions, in which the stability region coincides with the rate region for many utility-based resource allocation schemes, independent of the value of the fairness parameter. It is further shown that for networks which consist of flows from two different classes underalpha-fair allocations, there exists a tradeoff between the stability region and the fairness parameteralpha. Moreover, the impact of this fairness-stability tradeoff on the system performance, e.g., average throughput and mean flow response time, is studied, and numerical experiments that illustrate the new stability region and the performance versus fairness tradeoff are presented.

In modern DSL networks, crosstalk among different lines (i.e., users) is the major source of performance degradation. Dynamic spectrum management (DSM) refers to a set of techniques to mitigate the effect of crosstalk leading to spectacular performance gains. However the main research efforts in DSM aim at only physical layer performance whereas the true end user experience depends on what they see at the application rather than the physical layer. Upper layer performance metrics like throughput and delay may be much more important to improve the user satisfaction. To that end, we provide a framework to study upper layer performance by looking at scheduling and DSM together. We show how optimal scheduling can be combined with optimal DSM and provide throughput-optimal scheduling algorithms which require only polynomial complexity. We furthermore present extentions that significantly improve delay performance by using the specific structure of the underlying problem.

We develop a family of distributed wireless scheduling algorithms that requires only O(1) complexity for M-hop interference model, for any finite M. The recent technology advances and heterogeneity in wireless networks lead to various interference patterns. Thus, a scheduling algorithm geared into a specific interference model (typically one-hop or two-hop in literature) may be limited in its applicability. In this paper, we tackle this problem, and develop a family of scheduling algorithms (which guarantees throughput and delay performance) for M-hop interference models. To achieve such a goal, we use the concept of vertex augmentation, and for a given M, the family of parameterized algorithms are proposed and the tradeoffs among throughput, complexity, and delay are studied.

The multi-carrier interference channel where interference is treated as additive white Gaussian noise, is a very active topic of research, particularly important in the area of Dynamic Spectrum Management (DSM) for Digital Subscriber Lines (DSL). Here, multiple users optimize their transmit power spectra so as to maximize the total weighted sum of data rates. The corresponding optimization problem is however nonconvex and thus computationally intractable, i.e. a certificate of global optimality requires exponential time complexity algorithms. This paper shows that under certain channel conditions, this nonconvex problem can be solved in polynomial time with a certificate of global optimality. The channel conditions are discussed consisting of different interference models including synchronous and asynchronous DSL transmission. Simulations demonstrate its applicability to realistic DSL scenarios.

It has been an important research topic since 1992 to maximize stability region in constrained queueing systems, which includes the study of scheduling over wireless ad hoc networks. In this paper, we propose a framework to study a wide range of existing and future scheduling algorithms and characterize the achieved tradeoffs in stability, delay, and complexity. These characterizations reveal interesting properties hidden in the study of any one or two dimensions in isolation. For example, decreasing complexity from exponential to polynomial, while keeping stability region the same, generally comes at the expense of exponential growth of delays. Investigating trade-offs in the 3-dimensional space allows a designer to fix one dimension and vary the other two jointly. For example, incentives for using scheduling algorithms with only partial throughput-guarantee can be quantified with regards to delay and complexity. Trade-off analysis is then extended to systems with congestion control through utility maximization for non-stabilizable arrival inputs, where the complexity-utility-delay trade-off is shown to be different from the complexity-stability-delay tradeoff. Finally, we analyze more practical models with bounded message size, and consider "effective throughput" which reflects resource occupied by control messages. We show that effective throughput may degrade significantly in certain scheduling algorithms, and suggest a mechanism to avoid this problem in light of the 3D tradeoff framework.

This is an overview of the ongoing FAST Copper project, which is aimed at substantial improvements in rate, reach, reliability, and quality in copper-last-mile broadband access through fiber/DSL deployment, engineering innovations, and fundamental research. The project is funded by NSF, and is currently pursued jointly by Princeton University, Stanford University, and Fraser Research Lab. In this article, we outline the motivations, challenges, and research issues associated with the project, and report some of the recent results by the Princeton team in each of the four dimensions: frequency, amplitude, space, and time.

We propose a general family of MAC scheduling algorithms that achieve any rate-point on a uniform discrete-lattice within the throughput-region (i.e., lattice-throughput-optimal) under a physical interference model. Under the physical interference model, a centralized algorithm requires information on node locations (and distance among nodes) to determine a schedule that is provably throughput-optimal. In this paper, we propose a distributed, synchronous contention-based scheduling algorithm that (i) is lattice-throughput-optimal, (ii) does not require node location information, and (iii) has a signaling complexity that does not depend on network size. Thus, it is amenable to simple implementation, and is robust to network dynamics such as topology and load changes.

In this paper we characterize flow-level stochastic stability for networks with non-convex or time-varying rate regions underresource allocation based on utility maximization. Similar to prior works on flow-level stability, we consider exogenous data arrivals with finite workloads. However, to model many realistic situations, the rate region, which constrains the feasibility of resource allocation, may be either non-convex or time-varying. When the rate region is fixed but non-convex, we derive sufficient and necessary conditions for stability, which coincide when the set of allocated rate vectors has continuous contours. When the rate region is time-varying according to some stationary, ergodic process, we derive the precise stability region. In both cases,the size of the stability region depends on the resource allocation policy, in particular, on the fairness parameter in ∝-fair utility maximization. This is in sharp contrast with the substantial existing literature on stability under fixed and convex rate regions, in which the stability region coincides with the rate region for many utility-based resource allocation schemes, independently of the value of the fairness parameter. We further investigate the tradeoff between fairness and stability when rate region is non-convex or time-varying. Numerical examples of both wired and wireless networks are provided to illustrate the new stability regions and tradeoffs proved in the paper.

This paper focuses on congestion control over multi-hop, wireless networks. In a wireless network, an important constraint that arises is that due to the MAC (media access control) layer. Many wireless MACs use a time-division strategy for channel access, where, at any point in space, the physical channel can be accessed by a single user at each instant of time. We develop a fair hop-by-hop congestion control algorithm with the MAC constraint being imposed in the form of a channel access time constraint, using an optimization based framework. In the absence of delay, we show that this algorithm is globally stable using a Lyapunov function based approach. Next, in the presence of delay, we show that the hop-by-hop control algorithm has the property of spatial spreading. In other words, focused loads at a particular spatial location in the network get "smoothed" over space. We derive bounds on the "peak load" at a node, both with hop-by-hop control, as well as with end-to-end control, show that significant gains are achieved with the hop-by-hop scheme, and validate the analytical results with simulation.