We propose a multi-agent multi-armed bandit (MA-MAB) framework to ensure fair outcomes across agents while maximizing overall system performance. For example, in a ridesharing setting where a central dispatcher assigns drivers to distinct geographic regions, utilitarian welfare (the sum of driver earnings) can be highly skewed—some drivers may receive no rides. We instead measure fairness by Nash social welfare, i.e., the product of individual rewards. A key challenge in this setting is decision-making under limited information about arm rewards (geographic regions). To address this, we introduce a novel probing mechanism that strategically gathers information about selected arms before assignment. In the offline setting, where reward distributions are known, we exploit submodularity to design a greedy probing algorithm with a constant-factor approximation guarantee. In the online setting, we develop a probing-based algorithm that achieves sublinear regret while preserving Nash social welfare. Extensive experiments on synthetic and real-world datasets demonstrate that our approach outperforms baseline methods in both fairness and efficiency.

We formalize sequential decision–making with information acquisition as the Probing-augmented User-Centric Selection (PUCS) framework, where a learner first probes a subset of arms to obtain side information on resources and rewards, and then assigns K plays to M arms. PUCS encompasses practical scenarios such as ridesharing, wireless scheduling, and content recommendation, in which both resources and payoffs are initially unknown and probing incurs cost. For the offline setting (known payoff distributions), we present a greedy probing algorithm with a constant-factor approximation guarantee of ζ=(e-1)/(2e-1). For the online setting (unknown payoff distributions), we introduce OLPA, a stochastic combinatorial bandit algorithm that achieves a regret bound of O(√T+ln2T). We also prove an Ω(√T) lower bound, showing that the upper bound is tight up to logarithmic factors. Numerical results using two real-world datasets demonstrate the effectiveness of our solutions.

Reinforcement learning (RL) systems, while achieving remarkable success across various domains, are vulnerable to adversarial attacks. This is especially a concern in vision-based environments where minor manipulations of high-dimensional image inputs can easily mislead the agent's behavior. To this end, various defenses have been proposed recently, with state-of-the-art approaches achieving robust performance even under large state perturbations. However, after closer investigation, we found that the effectiveness of the current defenses is due to a fundamental weakness of the existing $l_p$ norm-constrained attacks, which can barely alter the semantics of image input even under a relatively large perturbation budget. In this work, we propose SHIFT, a novel policy-agnostic diffusion-based state perturbation attack to go beyond this limitation. Our attack is able to generate perturbed states that are semantically different from the true states while remaining realistic and history-aligned to avoid detection. Evaluations show that our attack effectively breaks existing defenses, including the most sophisticated ones, significantly outperforming existing attacks while being more perceptually stealthy. The results highlight the vulnerability of RL agents to semantics-aware adversarial perturbations, indicating the importance of developing more robust policies.

Reinforcement learning (RL) has achieved phenomenal success in various domains. However, its data-driven nature also introduces new vulnerabilities that can be exploited by malicious opponents. Recent work shows that a well-trained RL agent can be easily manipulated by strategically perturbing its state observations at the test stage. Existing solutions either introduce a regularization term to improve the smoothness of the trained policy against perturbations or alternatively train the agent's policy and the attacker's policy. However, the former does not provide sufficient protection against strong attacks, while the latter is computationally prohibitive for large environments. In this work, we propose a new robust RL algorithm for deriving a pessimistic policy to safeguard against an agent's uncertainty about true states. This approach is further enhanced with belief state inference and diffusion-based state purification to reduce uncertainty. Empirical results show that our approach obtains superb performance under strong attacks and has a comparable training overhead with regularization-based methods. Our code is available at https://github.com/SliencerX/Belief-enriched-robust-Q-learning.

Existing solutions to network scheduling typically assume that the instantaneous link rates are completely known before a scheduling decision is made or consider a bandit setting where the accurate link quality is discovered only after it has been used for data transmission. In practice, the decision maker can obtain (relatively accurate) channel information, e.g., through beamforming in mmWave networks, right before data transmission. However, frequent beamforming incurs a formidable overhead in densely deployed mmWave WLANs. In this paper, we consider the important problem of throughput optimization with joint link probing and scheduling. The problem is challenging even when the link rate distributions are pre-known (the offline setting) due to the necessity of balancing the information gains from probing and the cost of reducing the data transmission opportunity. We develop an approximation algorithm with guaranteed performance when the probing decision is non-adaptive and a dynamic programming-based solution for the more challenging adaptive setting. We further extend our solutions to the online setting with unknown link rate distributions and develop a contextual-bandit based algorithm and derive its regret bound. Numerical results using data traces collected from real-world mmWave deployments demonstrate the efficiency of our solutions.

In representative democracies, regular election cycles are supposed to prevent misbehavior by elected officials, hold them accountable, and subject them to the “will of the people." Pandering, or dishonest preference reporting by candidates campaigning for election, undermines this democratic idea. Much of the work on Computational Social Choice to date has investigated strategic actions in only a single election. We introduce a novel formal model of pandering and examine the resilience of two voting systems, Representative Democracy (RD) and Flexible Representative Democracy (FRD), to pandering within a single election and across multiple rounds of elections. For both voting systems, our analysis centers on the types of strategies candidates employ and how voters update their views of candidates based on how the candidates have pandered in the past. We provide theoretical results on the complexity of pandering in our setting for a single election, formulate our problem for multiple cycles as a Markov Decision Process, and use reinforcement learning to study the effects of pandering by single candidates and groups of candidates over many rounds.

In this article, we consider a discrete-time information-update system, where a service provider can proactively retrieve information from the information source to update its data and users query the data at the service provider. One example is crowdsensing-based applications. In order to keep users satisfied, the application desires to provide users with fresh data, where the freshness is measured by the age-of-information (AoI). However, maintaining fresh data requires the application to update its database frequently, which incurs an update cost (e.g., incentive payment). Hence, there exists a natural tradeoff between the AoI and the update cost at the service provider who needs to make update decisions. To capture this tradeoff, we formulate an optimization problem with the objective of minimizing the total cost, which is the sum of the staleness cost (which is a function of the AoI) and the update cost. Then, we provide two useful guidelines for the design of efficient update policies. Following these guidelines and assuming that the aggregated request arrival process is Bernoulli, we prove that there exists a threshold-based policy that is optimal among all online policies and thus focus on the class of threshold-based policies. Furthermore, we derive the closed-form formula for computing the long-term average cost under any threshold-based policy and obtain the optimal threshold. Finally, we perform extensive simulations using both synthetic data and real traces to verify our theoretical results and demonstrate the superior performance of the optimal threshold-based policy compared with several baseline policies.

Network function virtualization (NFV) is an emerging design paradigm that replaces physical middlebox devices with software modules running on general purpose commodity servers. While gradually transitioning to NFV, Internet service providers face the problem of where to introduce NFV in order to make the most benefit of that; here, we measure the benefit by the amount of traffic that can be served in an NFV-enabled network. This problem is non-trivial as it is composed of two challenging subproblems: 1) placement of nodes to support virtual network functions (referred to as VNF-nodes); 2) allocation of the VNF-nodes’ resources to network flows. These two subproblems must be jointly considered to satisfy the objective of serving the maximum amount of traffic. This problem has been studied for the one-dimensional setting, where all network flows require one network function, which requires a unit of resource to process a unit of flow. In this work, we consider the multi-dimensional setting, where flows must be processed by multiple network functions, which require a different amount of each resource to process a unit of flow. The multi-dimensional setting introduces new challenges in addition to those of the one-dimensional setting (e.g., NP-hardness and non-submodularity) and also makes the resource allocation subproblem a multi-dimensional generalization of the generalized assignment problem with assignment restrictions. To address these difficulties, we propose a novel two-level relaxation method that allows us to draw a connection to the sequence submodular theory and utilize the property of sequence submodularity along with the primal-dual technique to design two approximation algorithms. We further prove that the proposed algorithms have a non-trivial approximation ratio that depends on the number of VNF-nodes, resources, and a measure of the available resource compared to flow demand. Finally, we perform trace-driven simulations to show the effectiveness of the proposed algorithms.

In this paper, we consider a discrete-time information-update system, where a service provider can proactively retrieve information from the information source to update its data and users query the data at the service provider. One example is crowdsensing-based applications. In order to keep users satisfied, the application desires to provide users with fresh data, where the freshness is measured by the Age-of-Information (AoI). However, maintaining fresh data requires the application to update its database frequently, which incurs an update cost (e.g., incentive payment). Hence, there exists a natural tradeoff between the AoI and the update cost at the service provider who needs to make update decisions. To capture this tradeoff, we formulate an optimization problem with the objective of minimizing the total cost, which is the sum of the staleness cost (which is a function of the AoI) and the update cost. Then, we provide two useful guidelines for the design of efficient update policies. Following these guidelines and assuming that the aggregated request arrival process is Bernoulli, we prove that there exists a threshold-based policy that is optimal among all online policies and thus focus on the class of threshold-based policies. Furthermore, we derive the closed-form formula for computing the long-term average cost under any threshold-based policy and obtain the optimal threshold. Finally, we perform extensive simulations using both synthetic data and real traces to verify our theoretical results and demonstrate the superior performance of the optimal threshold-based policy compared with several baseline policies.

We propose a model-based reinforcement learning framework to derive untargeted poisoning attacks against federated learning (FL) systems. Our framework first approximates the distribution of the clients' aggregated data using model updates from the server. The learned distribution is then used to build a simulator of the FL environment, which is utilized to learn an adaptive attack policy through reinforcement learning. Our framework is capable of learning strong attacks automatically even when the server adopts a robust aggregation rule. We further derive an upper bound on the attacker's performance loss due to inaccurate distribution estimation. Experimental results on real-world datasets demonstrate that the proposed attack framework significantly outperforms state-of-the-art poisoning attacks. This indicates the importance of developing adaptive defenses for FL systems.

While mobile apps often need to transmit sensitive information out to support various functionalities, they may also abuse the privilege by leaking the data to unauthorized third parties. This makes us question: Is the given transmission required to fulfill the app functionality? In this paper, we make the first attempt to automatically identify suspicious transmissions from app visual interfaces, including app names, descriptions, and user interfaces. We design and implement a novel framework called FlowIntent to detect nonfunctional transmissions at both software and network levels. During the exercising of the given apps, FlowIntent automatically detects privacy-sharing transmissions and determines their purposes by utilizing the fact that mobile users rely on visible app interface to perceive the functionality of the app at certain context. The characterizations of nonfunctional network traffic are then summarized to provide network level protection. FlowIntent not only reduces the false alarms caused by traditional taint analysis, but also captures the sensitive transmissions missed by widely-used taint analysis system TaintDroid. Evaluation using 2125 sharing flows collected from more than a thousand running instances shows that our approach achieves about 94 percent accuracy in detecting nonfunctional transmissions.

Recent works on adversarial examples for image classification focus on directly modifying pixels with minor perturbations. The small perturbation requirement is imposed to ensure the generated adversarial examples being natural and realistic to humans, which, however, puts a curb on the attack space thus limiting the attack ability and transferability especially for systems protected by a defense mechanism. In this paper, we propose the novel concepts of structure patterns and structure-aware perturbations that relax the small perturbation constraint while still keeping images natural. The key idea of our approach is to allow perceptible deviation in adversarial examples while keeping structure patterns that are central to a human classifier. Built upon these concepts, we propose a \emph{structure-preserving attack (SPA)} for generating natural adversarial examples with extremely high transferability. Empirical results on the MNIST and the CIFAR10 datasets show that SPA exhibits strong attack ability in both the white-box and black-box setting even defenses are applied. Moreover, with the integration of PGD or CW attack, its attack ability escalates sharply under the white-box setting, without losing the outstanding transferability inherited from SPA.

Submodularity is an important property of set functions and has been extensively studied in the literature. It models set functions that exhibit a diminishing returns property, where the marginal value of adding an element to a set decreases as the set expands. This notion has been generalized to considering sequence functions, where the order of adding elements plays a crucial role and determines the function value; the generalized notion is called sequence (or string) submodularity. In this paper, we study a new problem of robust sequence submodular maximization with cardinality constraints. The robustness is against the removal of a subset of elements in the selected sequence (e.g., due to malfunctions or adversarial attacks). Compared to robust submodular maximization for set function, new challenges arise when sequence functions are concerned. Specifically, there are multiple definitions of submodularity for sequence functions, which exhibit subtle yet critical differences. Another challenge comes from two directions of monotonicity: forward monotonicity and backward monotonicity, both of which are important to proving performance guarantees. To address these unique challenges, we design two robust greedy algorithms: while one algorithm achieves a constant approximation ratio but is robust only against the removal of a subset of contiguous elements, the other is robust against the removal of an arbitrary subset of the selected elements but requires a stronger assumption and achieves an approximation ratio that depends on the number of the removed elements. Finally, we generalize the analyses to considering sequence functions under weaker assumptions based on approximate versions of sequence submodularity and backward monotonicity.

Dense deployment of access points in 60 GHz WLANs can provide always-on gigabit connectivity and robustness against blockages to mobile clients. However, this dense deployment can lead to harmful interference between the links, affecting link data rates. In this paper, we attempt to better understand the interference characteristics and effectiveness of interference mitigation techniques using 802.11ad COTS devices and 60 GHz software radio based measurements. We first find that current 802.11ad COTS devices do not consider interference in sector selection, resulting in high interference and low spatial reuse. We consider three techniques of interference mitigation - channelization, sector selection and receive beamforming. First, our results show that channelization is effective but 60 GHz channels have non-negligible adjacent and non-adjacent channel interference. Second, we show that it is possible to perform interference-aware sector selection to reduce interference but its gains can be limited in indoor environment with reflections, and such sector selection should consider fairness in medium access and avoid asymmetric interference. Third, we characterize the efficacy of receive beamforming in combating interference and quantify the related overhead involved in the search for receive sector, especially in presence of blockages. We elaborate on the insights gained through the characterization and point out important outstanding problems through the study.

Network function virtualization (NFV) is an emerging design paradigm that replaces physical middlebox devices with software modules running on general purpose commodity servers. While gradually transitioning to NFV, Internet service providers face the problem of where to introduce NFV in order to make the most benefit of that; here, we measure the benefit by the amount of traffic that can be serviced through the NFV. This problem is non-trivial as it is composed of two challenging subproblems: 1) placement of nodes to support virtual network functions (referred to as VNF-nodes); and 2) allocation of the VNF-nodes resources to network flows; the two subproblems need to be considered jointly to satisfy the objective of serving the maximum amount of traffic. This problem has been studied recently but for the one-dimensional setting, where all network flows require one network function, which requires a unit of resource to process a unit of flow. In this work, we extend to the multi-dimensional setting, where flows can require multiple network functions, which can also require a different amount of each resource to process a unit of flow. The multi-dimensional setting introduces new challenges in addition to those of the onedimensional setting (e.g., NP-hardness and non-submodularity) and also makes the resource allocation a multi-dimensional generalization of the generalized assignment problem with assignment restrictions. To address these difficulties, we propose a novel two-level relaxation method and utilize the primal-dual technique to design two approximation algorithms that achieve an approximation ratio of ((Z-1)(e-1))/(2e2Z(kR)1/(Z-1)) and ((e-1)(Z-1))/(2e(Z-1+eZR1/(Z-1)), where k (resp. R) is the number of VNF-nodes (resp. resources), and Z is a measure of the available resource compared to flow demand. Finally, we perform extensive trace-driven simulations to show the effectiveness of the proposed algorithms.

Recent studies observe that app foreground is the most striking component that influences the access control decisions in mobile platform, as users tend to deny permission requests lacking visible evidence. However, none of the existing permission models provides a systematic approach that can automatically answer the question: Is the resource access indicated by app foreground? In this work, we present the design, implementation, and evaluation of COSMOS, a context-aware mediation system that bridges the semantic gap between foreground interaction and background access, in order to protect system integrity and user privacy. Specifically, COSMOS learns from a large set of apps with similar functionalities and user interfaces to construct generic models that detect the outliers at runtime. It can be further customized to satisfy specific user privacy preference by continuously evolving with user decisions. Experiments show that COSMOS achieves both high precision and high recall in detecting malicious requests. We also demonstrate the effectiveness of COSMOS in capturing specific user preferences using the decisions collected from 24 users and illustrate that COSMOS can be easily deployed on smartphones as a real-time guard with a very low performance overhead.

Coflow has recently been introduced to capture communication patterns that are widely observed in the cloud and massively parallel computing. Coflow consists of a number of flows that each represents data communication from one machine to another. A coflow is completed when all of its flows are completed. Due to its elegant abstraction of the complicated communication processes found in various parallel computing platforms, it has received significant attention. In this paper, we consider coflow for the objective of maximizing partial throughput. This objective seeks to measure the progress made for partially completed coflows before their deadline. Partially processed coflows still could be useful when their flows send out useful data that can be used for the next round computation. In our measure, a coflow is processed by a certain fraction when all of its flows are processed by the same fraction or more. We consider a natural class of greedy algorithms, which we call myopic concurrent. The algorithms seek to maximize the marginal increase of the partial throughput objective at each time. We analyze the performance of our algorithm against the optimal scheduler. In fact, our result is more general as a flow could be extended to demand various heterogeneous resources. Our experiment demonstrates our algorithm's superior performance.

Cybersecurity is increasingly threatened by advanced and persistent attacks. As these attacks are often designed to disable a system (or a critical resource, e.g., a user account) repeatedly, it is crucial for the defender to keep updating its security measures to strike a balance between the risk of being compromised and the cost of security updates. Moreover, these decisions often need to be made with limited and delayed feedback due to the stealthy nature of advanced attacks. In addition to targeted attacks, such an optimal timing policy under incomplete information has broad applications in cybersecurity. Examples include key rotation, password change, application of patches, and virtual machine refreshing. However, rigorous studies of optimal timing are rare. Further, existing solutions typically rely on a pre-defined attack model that is known to the defender, which is often not the case in practice. In this work, we make an initial effort towards achieving optimal timing of security updates in the face of unknown stealthy attacks. We consider a variant of the influential FlipIt game model with asymmetric feedback and unknown attack time distribution, which provides a general model to consecutive security updates.The defender's problem is then modeled as a time associative bandit problem with dependent arms. We derive upper confidence bound based learning policies that achieve low regret compared with optimal periodic defense strategies that can only be derived when attack time distributions are known.

Incentive-driven advanced attacks have become a major concern to cyber-security. Traditional defense techniques that adopt a passive and static approach by assuming a fixed attack type are insufficient in the face of highly adaptive and stealthy attacks. In particular, a passive defense approach often creates information asymmetry where the attacker knows more about the defender. To this end, moving target defense (MTD) has emerged as a promising way to reverse this information asymmetry. The main idea of MTD is to (continuously) change certain aspects of the system under control to increase the attacker's uncertainty, which in turn increases attack cost/complexity and reduces the chance of a successful exploit in a given amount of time. In this paper, we go one step beyond and show that MTD can be further improved when combined with information disclosure. In particular, we consider that the defender adopts a MTD strategy to protect a critical resource across a network of nodes, and propose a Bayesian Stackelberg game model with the defender as the leader and the attacker as the follower. After fully characterizing the defender's optimal migration strategies, we show that the defender can design a signaling scheme to exploit the uncertainty created by MTD to further affect the attacker's behavior for its own advantage. We obtain conditions under which signaling is useful, and show that strategic information disclosure can be a promising way to further reverse the information asymmetry and achieve more efficient active defense.

Mobile applications (apps) often transmit sensitive data through network with various intentions. Some transmissions are needed to fulfill the app's functionalities. However, transmissions with malicious receivers may lead to privacy leakage and tend to behave stealthily to evade detection. The problem is twofold: how does one unveil sensitive transmissions in mobile apps, and given a sensitive transmission, how does one determine if it is legitimate? In this paper, we propose LeakSemantic, a framework that can automatically locate abnormal sensitive network transmissions from mobile apps. LeakSemantic consists of a hybrid program analysis component and a machine learning component. Our program analysis component combines static analysis and dynamic analysis to precisely identify sensitive transmissions. Compared to existing taint analysis approaches, LeakSemantic achieves better accuracy with fewer false positives and is able to collect runtime data such as network traffic for each transmission. Based on features derived from the runtime data, machine learning classifiers are built to further differentiate between the legal and illegal disclosures. Experiments show that LeakSemantic achieves 91% accuracy on 2279 sensitive connections from 1404 apps.

An essential step for achieving multiplexing gain in MIMO downlink systems is to collect accurate channel state information (CSI) from the users. Traditionally, CSIs have to be collected before any data can be transmitted. Such a sequential scheme incurs a large feedback overhead, which substantially limits the multiplexing gain especially in a network with a large number of users. In this paper, we propose a novel approach to mitigate the feedback overhead by leveraging the recently developed Full-duplex radios. Our approach is based on the key observation that using Full-duplex radios, when the base-station (BS) is collecting CSI of one user through the uplink channel, it can use the downlink channel to simultaneously transmit data to other (non-interfering) users for which CSIs are already known. By allowing concurrent channel probing and data transmission, our scheme can potentially achieve a higher throughput compared to traditional schemes using Half-duplex radios. The new flexibility introduced by our scheme, however, also leads to fundamental challenges in achieving throughout optimal scheduling. In this paper, we make an initial effort to this important problem by considering a simplified group interference model. We develop a throughput optimal scheduling policy with complexity O((N/I)I), where N is the number of users and I is the number of user groups. To further reduce the complexity, we propose a greedy policy with complexity O(N log N) that not only achieves at least 2/3 of the optimal throughput region, but also outperforms any feasible Half-duplex solutions. We derive the throughput gain offered by Full-duplex under different system parameters and show the advantage of our algorithms through numerical studies.

Synchronizing videos over file-hosting services on personal cloud such as Dropbox, Box or Onedrive leads to wastage in bandwidth and storage, which can be critical, while using mobile devices. Users can alternatively download the video on-the-go, but that leads to high latency, depending on network bandwidth and video file size. In contrast, adaptive video streaming allows near-real-time viewing by streaming the best possible quality in a given network condition. This feature is achieved by keeping multiple versions of video in cloud, leading to additional costs in cloud storage. Moreover, current solutions can only support a small set of bitrates, leading to abrupt switches in video resolution especially when the network condition is unstable, as often experienced by mobile users. This paper introduces Vsync, a framework for cloud based video synchronization for mobile devices. A video content is streamed using a cloud-based real-time transcoding and transmission framework to provide smooth video quality. Built over prediction models for video transcoding sessions and a QoE based adaptive video streaming protocol, Vsync is able to obtain the improvements of 37 ~ 80% than other compared schemes. The dataset and evaluation was done on a pool of 220K video clips.

In many applications including interactive services and big data analytics, a timely result with a good match is often more valuable than a perfect yet delayed result. This fact can be utilized to improve the total utility gain of a cloud computing platform by allowing partial execution of jobs. A fundamental challenge, however, is that in many real environments, scheduling decisions have to be made online without knowledge about future jobs, which makes it difficult to choose between more valuable jobs with large deadlines and less valuable jobs that are more emergent. Moreover, jobs are often heterogeneous in their utilities, deadlines, and demands for different types of resources. In this paper, we study the problem of online scheduling for deadline-sensitive jobs with concave utility functions that can deliver partial results. We develop efficient online multi-resource allocation algorithms that achieve low competitive ratios for both continuous and discrete job models.

The exponential growth of mobile devices has raised concerns about sensitive data leakage. In this paper, we make the first attempt to identify suspicious location-related HTTP transmission flows from the user's perspective, by answering the question: Is the transmission user-intended? In contrast to previous network-level detection schemes that mainly rely on a given set of suspicious hostnames, our approach can better adapt to the fast growth of app market and the constantly evolving leakage patterns. On the other hand, compared to existing system-level detection schemes built upon program taint analysis, where all sensitive transmissions as treated as illegal, our approach better meets the user needs and is easier to deploy. In particular, our proof-of- concept implementation (FlowIntent) captures sensitive transmissions missed by TaintDroid, the state-of-the-art dynamic taint analysis system on Android platforms. Evaluation using 1002 location sharing instances collected from more than 20,000 apps shows that our approach achieves about 91% accuracy in detecting illegitimate location transmissions.

One key requirement for storage clouds is to be able to retrieve data quickly. Recent system measurements have shown that the data retrieving delay in storage clouds is highly variable, which may result in a long latency tail. One crucial idea to improve the delay performance is to retrieve multiple data copies by using parallel downloading threads. However, how to optimally schedule these downloading threads to minimize the data retrieving delay remains to be an important open problem. In this paper, we develop low-complexity thread scheduling policies for several important classes of data downloading time distributions, and prove that these policies are either delay-optimal or within a constant gap from the optimum delay performance. These theoretical results hold for an arbitrary arrival process of read requests that may contain finite or infinite read requests, and for heterogeneous MDS storage codes that can support diverse storage redundancy and reliability requirements for different data files. Our numerical results show that the delay performance of the proposed policies is significantly better than that of First-Come-First-Served (FCFS) policies considered in prior work.

With increasing popularity of media-enabled handhelds and their integration with the in-vehicle entertainment systems, the need for high-data-rate services for mobile users on the go is evident. This ever-increasing demand of data is constantly surpassing what cellular networks can economically support. Large-scale wireless local area networks (WLANs) can provide such a service, but they are expensive to deploy and maintain. Open WLAN access points, on the other hand, need no new deployments, but can offer only opportunistic services, lacking any performance guarantees. In contrast, a carefully planned sparse deployment of roadside WiFi provides an economically scalable infrastructure with quality-of-service assurance to mobile users. In this paper, we present a new metric, called Contact Opportunity, to closely model the quality of data service that a mobile user might experience when driving through the system. We then present efficient deployment algorithms for minimizing the cost for ensuring a required level of contact opportunity. We further extend this concept and the deployment techniques to a more intuitive metric-the average throughput-by taking various dynamic elements into account. Simulations over a real road network and experimental results show that our approach achieves significantly better cost versus throughput tradeoff in both the worst case and average case compared to some commonly used deployment algorithms.

Cognitive radio networks (CRNs) allow unlicensed users to opportunistically access the licensed spectrum without causing disruptive interference to the primary users (PUs). One of the main challenges in CRNs is the ability to detect PU transmissions. Recent works have suggested the use of secondary user (SU) cooperation over individual sensing to improve sensing accuracy. In this paper, we consider a CRN consisting of multiple PUs and SUs to study the problem of maximizing the total expected system throughput. First, we study the sensing decision problem for maximizing the system throughput subject to a constraint on the PU throughput, and we design a Bayesian decision rule-based algorithm. The problem is shown to be strongly NP-hard and solved via a greedy algorithm with time complexity O([(N5)/(log2[1/(1-ε)])]), where N is the total number of SUs. The algorithm achieves a throughput strictly greater than 1/2(1-ε) of the optimal solution and results in a small constraint violation that goes to zero with ε. We then investigate the more general problem with constraints on both PU throughput and the sensing time overhead, which limits the number of SUs that can participate in cooperative sensing. We illustrate the efficacy of the performance of our algorithms and provide sensitivity analysis via a numerical investigation.

In Cognitive Radio Networks (CRNs), secondary users (SUs) are allowed to opportunistically access the unused/under-utilized channels of primary users (PUs). To utilize spectrum resources efficiently, an auction scheme is often applied where an operator serves as an auctioneer and accepts spectrum requests from SUs. Most existing works on spectrum auctions assume that the operator has perfect knowledge of PU activities. In practice, however, it is more likely that the operator only has statistical information of the PU traffic when it is trading a spectrum hole, and it is acquiring more accurate information in real time. In this paper, we distinguish PU channels that are under the control of the operator, where accurate channel states are revealed in real-time, and channels that the operator acquires from PUs out of its control, where a sense-before-use paradigm has to be followed. Considering both spectrum uncertainty and sensing inaccuracy, we study the social welfare maximization problem for serving SUs with various levels of delay tolerance. We first model the problem as a finite horizon Markov decision process when the operator knows all spectrum requests in advance, and propose an optimal dynamic programming based algorithm. We then investigate the case when spectrum requests are submitted online, and propose a greedy algorithm that is 1/2-competitive for homogeneous channels and is comparable to the offline algorithm for more general settings. We further extend the online algorithm to an online auction scheme, which ensures incentive compatibility for the SUs and also provides a way for trading off social welfare and revenue.

Cognitive Radio Networks allow unlicensed users to opportunistically access the licensed spectrum without causing disruptive interference to the primary users (PUs). One of the main challenges in CRNs is the ability to detect PU transmissions. Recent works have suggested the use of secondary user (SU) cooperation over individual sensing to improve sensing accuracy. In this paper, we consider a CRN consisting of a single PU and multiple SUs to study the problem of maximizing the total expected system throughput. We propose a Bayesian decision rule based algorithm to solve the problem optimally with a constant time complexity. To prioritize PU transmissions, we re-formulate the throughput maximization problem by adding a constraint on the PU throughput. The constrained optimization problem is shown to be strongly NP-hard and solved via a greedy algorithm with pseudo-polynomial time complexity that achieves strictly greater than 1/2 of the optimal solution. We also investigate the case for which a constraint is put on the sensing time overhead, which limits the number of SUs that can participate in cooperative sensing. We reveal that the system throughput is monotonic over the number of SUs chosen for sensing. We illustrate the efficacy of the performance of our algorithms via a numerical investigation.

Vehicular Internet access via open WiFi access points (APs) has been demonstrated to be a feasible solution to provide opportunistic data service to moving vehicles. Using an in situ deployment, however, such a solution does not provide performance guarantees due to unpredictable intermittent connectivity. On the other hand, a solution that tries to cover every point in an entire road network with APs (a full coverage) is not very practical due to prohibitive deployment and operational costs. In this paper, we introduce a new notion of intermittent coverage for mobile users, called Alpha Coverage, which provides worst-case guarantees on the interconnection gap, i.e., the distance or expected delay between two consecutive mobile-AP contacts for a vehicle, while using significantly fewer APs than needed for full coverage. We propose efficient algorithms to verify whether a given deployment provides Alpha Coverage. The problem of finding an economic deployment that provides α -coverage turns out to be NP-hard. We hence provide both approximation algorithms that have provable guarantees on the performance as well as efficient heuristics that perform well in practice. The efficiency of our algorithms is demonstrated via simulations using data from real-world road networks.

Renewable energy enables sensor networks with the capability to recharge and provide perpetual data services. Due to low recharging rates and the dynamics of renewable energy such as solar and wind power, providing services without interruptions caused by battery runouts is nontrivial. Most environment monitoring applications require data collection from all nodes at a steady rate. The objective of this paper is to design a solution for fair and high throughput data extraction from all nodes in the presence of renewable energy sources. Specifically, we seek to compute the lexicographically maximum data collection rate and routing paths for each node such that no node will ever run out of energy. We propose a centralized algorithm and two distributed algorithms. The centralized algorithm jointly computes the optimal data collection rate for all nodes along with the flows on each link, the first distributed algorithm computes the optimal rate when the routing structure is a given tree, and the second distributed algorithm, although heuristic, jointly computes a routing structure and a high lexicographic rate assignment that is nearly optimum. We prove the optimality for the centralized and the first distributed algorithm, and use real test-bed experiments and extensive simulations to evaluate both of the distributed algorithms.

With increasing popularity of media enabled hand-helds, the need for high data-rate services for mobile users is evident. Large-scale Wireless LANs (WLANs) can provide such a service, but they are expensive to deploy and maintain. Open WLAN access-points (APs), on the other hand, need no new deployments, but can offer only opportunistic services with no guarantees on short term throughput. In contrast, a carefully planned sparse deployment of roadside WiFi provides an economically scalable infrastructure with quality of service assurance to mobile users. In this paper, we propose to study the deployment techniques with respect to roadside WiFi. In particular, we present a new metric, called Contact Opportunity, as a characterization of a roadside WiFi network. Informally, the contact opportunity for a given deployment measures the fraction of distance or time that a mobile user is in contact with some AP when moving through a certain path. Such a metric is closely related to the quality of data service that a mobile user might experience while driving through the system. We then present an efficient deployment method that maximizes the worst case contact opportunity under a budget constraint. We further show how to extend this concept and the deployment techniques to a more intuitive metric -- the average throughput -- by taking various dynamic elements into account. Simulations over a real road network and experimental results show that our approach achieves more than 200% higher minimum contact opportunity, 30%-100% higher average contact opportunity and a significantly improved distribution of average throughput compared with two commonly used baseline algorithms.

Tracking of movements such as that of people, animals, vehicles, or of phenomena such as fire, can be achieved by deploying a wireless sensor network. So far only prototype systems have been deployed and hence the issue of scale has not become critical. Real-life deployments, however, will be at large scale and achieving this scale will become prohibitively expensive if we require every point in the region to be covered (i.e., full coverage), as has been the case in prototype deployments. In this paper we therefore propose a new model of coverage, called trap coverage, that scales well with large deployment regions. A sensor network providing trap coverage guarantees that any moving object or phenomena can move at most a (known) displacement before it is guaranteed to be detected by the network, for any trajectory and speed. Applications aside, trap coverage generalizes the de-facto model of full coverage by allowing holes of a given maximum diameter. From a probabilistic analysis perspective, the trap coverage model explains the continuum between percolation (when coverage holes become finite) and full coverage (when coverage holes cease to exist). We take first steps toward establishing a strong foundation for this new model of coverage. We derive reliable, explicit estimates for the density needed to achieve trap coverage with a given diameter when sensors are deployed randomly. Our density estimates are more accurate than those obtained using asymptotic critical conditions. We show by simulation that our analytical predictions of density are quite accurate even for small networks. We then propose polynomial-time algorithms to determine the level of trap coverage achieved once sensors are deployed on the ground. Finally, we point out several new research problems that arise by the introduction of the trap coverage model.

Vehicular Internet access via open WLAN access points (APs) has been demonstrated to be a feasible solution to provide opportunistic data service to moving vehicles. Using an in situ deployment, however, such a solution does not provide worst-case performance guarantees due to unpredictable intermittent connectivity. On the other hand, a solution that tries to cover every point in an entire road network with APs (full coverage) is not very practical due to the prohibitive deployment and operational cost. In this paper, we introduce a new notion of intermittent coverage for mobile users, called a-coverage, which provides worst-case guarantees on the interconnection gap while using significantly fewer APs than needed for full coverage. We propose efficient algorithms to verify whether a given deployment provides alpha-coverage and approximation algorithms for determining a deployment of APs that will provide alpha-coverage. We compare alpha-coverage with opportunistic access of open WLAN APs (modeled as a random deployment) via simulations over a real-world road network and show that using the same number of APs as random deployment, alpha-coverage bounds the interconnection gap to a much smaller distance than that in a random deployment.

The AutoWitness project aims to deter, detect, and track theft of everyday objects using a combination of ultra low-power mobile tags and a wide-area network of static anchors. Key research challenges include dramatically driving down the cost and size of tags and increasing their lifetime, discriminating between normal activities and theft using motion detection and classification algorithms, reconstructing getaway trajectories from sparse anchor rendezvous, and ensuring sufficient coverage and connectivity in a sparse, wide-area network of anchors. The demonstration will show AutoWitness in operation including motion detection, classifying theft signatures, and tracking the trajectories of "stolen" objects near the conference venue.

Communication between arbitrary pairs of nodes has become critical to support in emerging sensor networking applications. Traditional routing techniques for multi-hop wireless networks either require high control overhead in computing and maintaining routes, or may lead to unbounded route-stretch. In order to bound the route-stretch, we propose a distributed shortest-path roadmap based routing paradigm that embodies two ideas: routing hole approximation that summaries the critical information about hole boundaries and controlled advertisement that advertises the boundary information of each hole within limited neighborhoods. We show that our approach makes a desired tradeoff between the worst case route-stretch and the message overhead through both analysis and simulations.

Renewable energy enables sensor networks with the capability to recharge and provide perpetual data services. Due to low recharging rates and the dynamics of renewable energy such as solar and wind power, providing services without interruptions caused by battery runouts is non-trivial. Most environment monitoring applications require data collection from all nodes at a steady rate. The objective of this paper is to design a solution for fair and high throughput data extraction from all nodes in presence of renewable energy sources. Specifically, we seek to compute the lexicographically maximum data collection rate for each node, such that no node will ever run out of energy. We propose a centralized algorithm and an asynchronous distributed algorithm that can compute the optimal lexicographic rate assignment for all nodes. The centralized algorithm jointly computes the optimal data collection rate for all nodes along with the flows on each link, while the distributed algorithm computes the optimal rate when the routes are pre-determined. We prove the optimality for both the centralized and the distributed algorithms, and use a testbed with 155 sensor nodes to validate the distributed algorithm.

In-network caching is a useful technique for reducing latency and retransmission overhead of lost packets for reliable data delivery in wireless networks. However, in-network caching is challenging to implement in memory constrained devices such as RFIDs and sensors, and also in Wireless LAN (WLAN) gateways for large-scale deployments. In this paper we propose a novel technique for management of in-network caches using XOR coding for optimizing the use of limited buffer space in presence of random and burst packet losses. We identify two critical parameters, coding degree and coding distance for the coding scheme. As a case-study we implement our approach over Snoop and evaluate its performance for a WLAN. Using simulations in ns-2, we observe that when the size of the retransmission buffer on the gateway is less than 16 packets per TCP flow, the throughput can be enhanced by up to 30% for random losses and up to 20% for burst losses.

Autonomic computing middleware is a promising way to enable middleware based systems to cope with the rapid and continuous changes in the era of Internet. Technically, there have been three fundamental and challenging capabilities to an autonomic computing middleware, including how to monitor, reason and control middleware platform and applications. This position paper presents a reflection-based approach to autonomic computing middleware, which shows the philosophy that autonomic computing should focus on how to reason while reflective computing supports how to monitor and control. In this approach, the states and behaviors of middleware-based systems can be observed and changed through reflective mechanisms embedded in middleware platform at runtime. On the basis of reflection, some autonomic computing facilities could be constructed to reason and decide when and what to change. The approach is demonstrated on a reflective J2EE application server, which can automatically optimize itself in the standard J2EE benchmark testing