Interactive computational environments can help students explore algorithmic concepts through collaborative hands-on experimentation. However, static and instructor controlled demos in lectures limit engagement. Even when interactive visualizations are used, interactions are solely controlled by the instructor, leaving students as passive observers. In addition, the tools used for demonstration often vary significantly, as they are typically developed by individual instructors. Consequently, the visualizations remain confined to a single classroom, rather than being shared and adapted across courses or reused by other instructors. To address this gap and foster active engagement in live classrooms, we present a lightweight and seamless software framework named LEAP for developing interactive computational lab exercises using a simple idea: remotely callable instructor-defined functions. Using API endpoints and a provided client, students can discover and then call instructor defined functions remotely from their coding environment using scripts or interactive notebooks. Each function call is time-stamped and persistently logged in a database, allowing real-time visualization of participation, diverse solution paths, common pitfalls, and live feedback through collaboration, gamification, and quizzes. Labs are packaged as self-contained folders, each containing their own remotely callable functions. We provide example labs to demonstrate applications relevant for numerical analysis, machine learning, algorithms courses and mention some in electrical engineering (EE), economics, and physics. These capabilities enhance engagement and provide instructors with actionable insights into learning processes. With a standardized lab format and an online directory for community-contributed labs, we aim to foster a global ecosystem for exchanging and expanding interactive pedagogy enabled by LEAP.

This paper studies an important rate allocation problem that arises in many networked and distributed systems: steady-state traffic rate allocation from multiple sources to multiple service nodes when both (i) the access-path delay on each source-node route is rate-dependent (capacity-constrained) and convex, and (ii) each service node (also capacity-constrained) experiences a load-dependent queueing delay driven by aggregate load from all sources. We show that the resulting flow-weighted end-to-end delay minimization is a convex program, yielding a global system-optimal solution characterized by KKT conditions that equalize total marginal costs (a path marginal access term plus a node congestion price) across all utilized routes. This condition admits a Wardrop-type interpretation: for each source, all utilized options equalize total marginal cost, while any option with strictly larger total marginal cost receives no flow. Building on this structure, we develop a lightweight distributed pricing-based algorithm in which each service node locally computes and broadcasts a scalar congestion price from its observed aggregate load, while each source updates its traffic split by solving a small separable convex allocation problem under the advertised prices. Numerical illustrations demonstrate convergence of the distributed iteration to the centralized optimum and highlight the trade-offs induced by jointly modeling access and service congestion.

Ensuring the security and privacy of RFID systems is paramount to prevent unauthorized access and data breaches. In addition, addressing the insecurity of public keys in RFID tags and preventing server-side tag distinction requires a multifaceted approach. This paper proposes an RFID-enabled protocol, calledRISE, Resource-Efficient RFID Security Protocol inIoT withS-Box andElliptic Curve Cryptography, that integrates S-box and elliptic curve cryptography (ECC) to enhance the security of RFID communication. The protocol leverages S-boxes to introduce non-linearity and confusion, thereby thwarting potential attacks such as cryptanalysis and replay attacks. Additionally, ECC is employed for key exchange and authentication, leveraging computational efficiency and strong security properties. Formal proofs and analysis results demonstrate thatRISEprovides robust security and can effectively resist various types of attacks.RISEpresents notable improvements, with an average 51.18% reduction in computational overhead compared to similar protocols. This advancement not only boosts performance but also enhances resource efficiency.

Everlasting options, a relatively new class of perpetual financial derivatives, have emerged to tackle the challenges of rolling contracts and liquidity fragmentation in decentralized finance markets. This paper offers an in-depth analysis of markets for everlasting options, modeled using a dynamic proactive market maker. We examine the behavior of funding fees and transaction costs across varying liquidity conditions. Using simulations and modeling, we demonstrate that liquidity providers can aim to achieve a net positive PnL by employing effective hedging strategies, even in challenging environments characterized by low liquidity and high transaction costs. Additionally, we provide insights into the incentives that drive liquidity providers to support the growth of everlasting option markets and highlight the significant benefits these instruments offer to traders as a reliable and efficient financial tool.

A well-known expression for the saturation throughput of heterogeneous transmitting nodes in a wireless network using p-CSMA, derived from Renewal Theory, implicitly assumes that all transmitting nodes are in range of, and therefore conflicting with, each other. This expression, as well as simple modifications of it, does not correctly capture the saturation throughput values when an arbitrary topology is specified for the conflict graph between transmitting links. For example, we show numerically that calculations based on renewal theory can underestimate throughput by 48-62% for large packet sizes when the conflict graph is represented by a star topology. This is problematic because real-world wireless networks, such as wireless IoT mesh networks, are often deployed over a large area, resulting in non-complete conflict graphs. To address this gap, we present a computational approach based on a novel Markov chain formulation that yields the exact saturation throughput for each node in the general network case for any given set of access probabilities, as well as a more compact expression for the special case where the packet length is twice the slot length. Using our approach, we show how the transmit probabilities could be optimized to maximize weighted utility functions of the saturation throughput values. This would allow a wireless system designer to set transmit probabilities to achieve desired throughput trade-offs in any given deployment.

Scheduling a task graph representing an application over a heterogeneous network of computers is a fundamental problem in distributed computing. It is known to be not only NP-hard but also not polynomial-time approximable within a constant factor. As a result, many heuristic algorithms have been proposed over the past few decades. Yet it remains largely unclear how these algorithms compare to each other in terms of the quality of schedules they produce. We identify gaps in the traditional benchmarking approach to comparing task scheduling algorithms and propose a simulated annealing-based adversarial analysis approach called PISA to address them. We also introduce SAGA, a new open-source library for comparing task scheduling algorithms. We use SAGA to benchmark 15 algorithms on 16 datasets and PISA to compare the algorithms in a pairwise manner. Algorithms that appear to perform similarly on benchmarking datasets are shown to perform very differently on adversarially chosen problem instances. Interestingly, the results indicate that this is true even when the adversarial search is constrained to selecting among well-structured, applicationspecific problem instances. We present the first known lower bounds on the performance of many of the algorithms considered in this paper compared to other popular scheduling algorithms. This work represents an important step towards a more general understanding of the performance boundaries between task scheduling algorithms on different families of problem instances.

Many researchers are working to address the worldwide mental health crisis by developing therapeutic technologies that increase the accessibility of care, including leveraging large language model (LLM) capabilities in chatbots and socially assistive robots (SARs) used for therapeutic applications. Yet, the effects of these technologies over time remain unexplored. In this study, we use a factorial design to assess the impact of embodiment and time spent engaging in therapeutic exercises on participant disclosures. We assessed transcripts gathered from a two-week study in which 26 university student participants completed daily interactive Cognitive Behavioral Therapy (CBT) exercises in their residences using either an LLM-powered SAR or a disembodied chatbot. We evaluated the levels of active engagement and high intimacy of their disclosures (opinions, judgments, and emotions) during each session and over time. Our findings show significant interactions between time and embodiment for both outcome measures: participant engagement and intimacy increased over time in the physical robot condition, while both measures decreased in the chatbot condition.

Scheduling a given graph of tasks on a processing network has been a topic of interest and has been extensively studied, including for IoT applications. However, scheduling a series of task graphs that arrive at different time instances is still under-explored. We discuss this problem and introduce two approaches for it: Residual and Cumulative. We demonstrate using two subtle examples that both approaches face performance challenges.

The integration of the Internet of Things (IoT) and modern Artificial Intelligence (AI) has given rise to a new paradigm known as the Artificial Intelligence of Things (AIoT). In this survey, we provide a systematic and comprehensive review of AIoT research. We examine AIoT literature related to sensing, computing, and networking & communication, which form the three key components of AIoT. In addition to advancements in these areas, we review domain-specific AIoT systems that are designed for various important application domains. We have also created an accompanying GitHub repository, where we compile the papers included in this survey: https://github.com/AIoT-MLSys-Lab/AIoT-Survey. This repository will be actively maintained and updated with new research as it becomes available. As both IoT and AI become increasingly critical to our society, we believe that AIoT is emerging as an essential research field at the intersection of IoT and modern AI. It is our hope that this survey will serve as a valuable resource for those engaged in AIoT research and act as a catalyst for future explorations to bridge gaps and drive advancements in this exciting field.

The globalization of the semiconductor supply chain has paved the way for a rapid enhancement in the research and development, and the production of electronic devices. The exponential growth in manufacturing, design, and distribution has given rise to a complex ecosystem where the risk of counterfeit or Trojan-inserted integrated circuits (ICs) becomes significant. As emerging technologies continue to reshape the landscape of the electronics supply chain, addressing the challenges and risks posed by these developments becomes increasingly crucial. The challenge of ensuring security for 2.D/3D ICs, composed of multiple chiplets manufactured globally, is exacerbated by the lack of trust among entities in the semiconductor supply chain. The chiplets that are fabricated at an untrusted location can be tampered with, resulting in the insertion of malicious circuits that may leak secret information to an adversary. This paper presents a conceptual approach that limits the communication capability of an untrusted chiplet using a whitelisting technique inspired by security measures deployed in traditional networks. We also propose to use a logger to capture any communication rule violation that occurs during die-to-die communications across different chiplets. The logger state can be further uploaded to an immutable blockchain ledger for forensics purposes if an attack is identified.

With the growing concern of AI safety, there is a need to trust the computations done by machine learning (ML) models. Blockchain technology, known for recording data and running computations transparently and in a tamper-proof manner, can offer this trust. One significant challenge in deploying ML Classifiers on-chain is that while ML models are typically written in Python using an ML library such as Pytorch, smart contracts deployed on EVM-compatible blockchains are written in Solidity. We introduce Machine Learning to Smart Contract (ML2SC), a PyTorch to Solidity translator that can automatically translate multi-layer perceptron (MLP) models written in Pytorch to Solidity smart contract versions. ML2SC uses a fixedpoint math library to approximate floating-point computation. After deploying the generated smart contract, we can train our models off-chain using PyTorch and then further transfer the acquired weights and biases to the smart contract using a function call. Finally, the model inference can also be done with a function call providing the input. We mathematically model the gas costs associated with deploying, updating model parameters, and running inference on these models on-chain, showing that the gas costs increase linearly in various parameters associated with an MLP. We present empirical results matching our modeling. We also evaluate the classification accuracy showing that the outputs obtained by our transparent on-chain implementation are identical to the original off-chain implementation with Pytorch.

Truly collaborative scientific field data collection between human scientists and autonomous robot systems requires a shared understanding of the search objectives and tradeoffs faced when making decisions. Therefore, critical to developing intelligent robots to aid human experts is an understanding of how scientists make such decisions and how they adapt their data collection strategies when presented with new information in situ . In this study, we examined the dynamic data collection decisions of 108 expert geoscience researchers using a simulated field scenario. Human data collection behaviors suggested two distinct objectives: an information-based objective to maximize information coverage and a discrepancy-based objective to maximize hypothesis verification. We developed a highly simplified quantitative decision model that allows the robot to predict potential human data collection locations based on the two observed human data collection objectives. Predictions from the simple model revealed a transition from information-based to discrepancy-based objective as the level of information increased. The findings will allow robotic teammates to connect experts’ dynamic science objectives with the adaptation of their sampling behaviors and, in the long term, enable the development of more cognitively compatible robotic field assistants.

We present a comprehensive study on applying machine learning to detect distributed Denial of service (DDoS) attacks using large-scale Internet of Things (IoT) systems. While prior works and existing DDoS attacks have largely focused on individual nodes transmitting packets at a high volume, we investigate more sophisticated futuristic attacks that use large numbers of IoT devices and camouflage their attack by having each node transmit at a volume typical of benign traffic. We introduce new correlation-aware architectures that take into account the correlation of traffic across IoT nodes. We extensively analyze the proposed architectures by evaluating five different neural network models trained on a dataset derived from a 4060-node real-world IoT system. We observe that long short-term memory (LSTM) and a transformer-based model, in conjunction with the architectures that use correlation information of the IoT nodes, provide higher performance (in terms of F1 score and binary accuracy) than the other models and architectures, especially when the attacker camouflages itself by following benign traffic distribution on each transmitting node. For instance, by using the LSTM model, the distributed correlation-aware architecture gives 81% F1 score for the attacker that camouflages their attack with benign traffic as compared to 35% for the architecture that does not use correlation information. We validate the effectiveness of our proposed detection mechanism by implementing it on a real testbed. We also investigate the performance of heuristics for selecting a subset of nodes to share their data for correlation-aware architectures to meet resource constraints.

Researchers have been interested in developing AI tools to help students learn various mathematical subjects. One challenging set of tasks for school students is learning to solve math word problems. We explore how recent advances in natural language processing, specifically the rise of powerful transformer based models, can be applied to help math learners with such problems. Concretely, we evaluate the use of GPT-3, a 1.75B parameter transformer model recently released by OpenAI, for three related challenges pertaining to math word problems corresponding to systems of two linear equations. The three challenges are classifying word problems, extracting equations from word problems, and generating word problems. For the first challenge, we define a set of problem classes and find that GPT-3 has generally very high accuracy in classifying word problems (80%-100%), for all but one of these classes. For the second challenge, we find the accuracy for extracting equations improves with number of examples provided to the model, ranging from an accuracy of 31% for zero-shot learning to about 69% using 3-shot learning, which is further improved to a high value of 80% with fine-tuning. For the third challenge, we find that GPT-3 is able to generate problems with accuracy ranging from 33% to 93%, depending on the problem type.

No abstract available.

In recent years, there has been a significant surge in the deployment of Internet of Things (IoT) devices, which has consequently escalated security threats, notably Distributed Denial of Service (DDoS) attacks. Our prior research developed an LSTM-based framework for detecting futuristic DDoS attacks but largely relied on simulated datasets [1]. To bridge this gap, we designed a Raspberry Pi (RPi) testbed that mimics the complexities of large-scale IoT networks. This setup allows us to simulate realistic DDoS attacks originating from IoT devices and evaluate the effectiveness of various DDoS detection techniques. Specifically, using this RPi testbed, we validated the effectiveness of our LSTM-based framework in identifying futuristic DDoS attacks, observing an F1 score ranging between 0.8 and 0.86 depending on the aggressiveness of the DDoS attack.

In the context of evolving smart cities and autonomous transportation systems, Vehicular Ad-hoc Networks (VANETs) and the Internet of Vehicles (IoV) are growing in significance. Vehicles are becoming more than just a means of transportation; they are collecting, processing, and transmitting massive amounts of data to make driving safer and more convenient. However, this advancement ushers in complex issues concerning the centralized structure of traditional vehicular networks and the privacy and security concerns around vehicular data. This paper offers a novel, game-theoretic network architecture to address these challenges. Our approach decentralizes data collection through distributed servers across the network, aggregating vehicular data into spatio-temporal maps via secure multi-party computation (SMPC). This strategy effectively reduces the chances of adversaries reconstructing a vehicle’s complete path, increasing privacy. We also introduce an economic model grounded in game theory that incentivizes vehicle owners to participate in the network, balancing the owners’ privacy concerns with the monetary benefits of data sharing. This model aims to maximize the data consumer’s utility from the gathered sensor data by determining the most suitable payment to participating vehicles, the frequency in which these vehicles share their data, and the total number of servers in the network. We explore the interdependencies among these parameters and present our findings accordingly. To define meaningful utility and loss functions for our study, we utilize a real dataset of vehicular movement traces.

In the age of data and machine learning, massive amounts of data produced throughout our society can be rapidly delivered to various applications through a broad spectrum of cloud services. However, the spectrum of applications has vastly different data quality requirements and Willingness-To-Pay(WTP), creating a general and complex problem matching consumer quality requirements and budgets with providers’ data quality and price. This paper proposes the Information-Centric Networking(ICN)-based data marketplace to foster quality-data trading service to address the challenge above. We embed a WTP mechanism into an ICN-based data broker service running on cloud computing; therefore, a data consumer can request its desired data with a data name and quality requirement. By specifying nominal WTPs, data consumers can acquire data of the desired quality at the range of maximum nominal WTP. At the same time, a data broker can offer data of a suitable quality based on the profit-optimized price and the proposed service quality using ground-truth accuracy trained by data. We demonstrate that the data broker’s profit can be almost doubled by using the optimal data size and budget determined by considering the one-leader-multiple-followers Stackelberg game. These results show that a value-added data brokering service can profitably facilitate data trading.

The COVID-19 pandemic has brought a significant disruption not only on how schools operate but also affected student sentiments on learning and adoption to different learning strategies. We propose CampusPandemicPlanR, a reinforcement learning-based simulation tool that could be applied to suggest to campus operators how many students from each course to allow on a campus classroom each week. The tool aims to strike a balance between the conflicting goals of keeping students from getting infected, on one hand, and allowing more students to come into campus to allow them to benefit from in-person classes, on the other. Our preliminary results show that reinforcement learning is able to learn better policies over iterations, and that different Pareto-optimal tradeoffs between these conflicting goals could be obtained by varying the reward weight parameter.

In the emerging realm of decentralized finance (DeFi), most of the existing Automated Market Maker (AMM) protocols used by major platforms like Uniswap and Curve are governed by a static mathematical equation, such as the constant product curve. One major shortcoming of these curves is that they require external forces to maintain the price of the liquidity pool (LP), subjecting the LP to loss due to arbitrage. A novel solution, the dynamic curve AMM, was recently proposed to ensure that the pool price always matches the market price, making the LP invulnerable to arbitrageurs. Dynamic curves, however, have a path-dependent trading problem, meaning that the number of trades and the distribution of trades affect the trader’s gain. We show how to find the optimal trading policy for a dynamic AMM curve under several settings. We first show that in a zero-transaction-fee setting the optimal trading policy is to place infinitesimally small trades, resulting in zero slippage. Then, we present an algorithm that computes the optimal policy in a fixed-number-of-trade setting. Though the problem has an exponentially large search space, our algorithm utilizes dynamic programming to achieve a polynomial run-time. Finally, we generalize the solution to more complex settings, including a per-order-fee setting and a percentage-fee setting.

We investigate the application of artificial intelligence to cybersecurity, to contribute to the safe and secure growth of the internet of things (IoT). Specifically, we train and evaluate different neural networks models to detect distributed denial of service (DDoS) attacks in a large-scale IoT system. We consider futuristic attacks launched by sophisticated malicious entities that take over multiple distributed IoT nodes and are able to disguise their intrusion by closely mimicking the benign traffic of the network. Using data from prior work, we find that a truncated Cauchy distribution is a suitable fit for benign traffic volume from IoT devices, and we model the attack traffic volume as following the same distribution but with different parameters for location and scale. We emulate both benign and attack traffic by overlaying these traffic volume distributions on top of an activity status data trace from a real urban IoT deployment consisting of about 4000 nodes. Using our enhanced dataset, we compare four neural network models: multi-layer perceptron (MLP), convolutional neural network (CNN), long short-term memory (LSTM), and autoencoder (AEN), analyzing their performance as a function of a parameter that measures the deviation of the attacks from the benign data. We observe that all four models are sensitive to the distance between benign and attack traffic. We further observe that LSTM gives the best overall performance in terms of both high accuracy and high recall.

Publish-subscribe protocols enable real-time multi-point-to-multi-point communications for many dispersed computing systems like Internet of Things (IoT) applications. Recent interest has focused on adding processing to such publish-subscribe protocols to enable computation over real-time streams such that the protocols can provide functionalities such as sensor fusion, compression, and other statistical analysis on raw sensor data. However, unlike pure publish-subscribe protocols, which can be easily deployed with end-to-end transport layer encryption, it is challenging to ensure security in such publish-process-subscribe protocols when the processing is carried out on an untrusted third party. In this work, we present$\mathcal{XYZ}$, a secure publish-process-subscribe system that can preserve the confidentiality of computations and support multi-publisher-multi-subscriber settings. Within$\mathcal{XYZ}$, we design two distinct schemes: the first using Yao's garbled circuits (the GC-Based Scheme) and the second using homomorphic encryption with proxy re-encryption (the Proxy-HE Scheme). We build implementations of the two schemes as an integrated publish-process-subscribe system. We evaluate our system on several functions and also demonstrate real-world applications. The evaluation shows that the GC-Based Scheme can finish most tasks two orders of magnitude times faster than the Proxy-HE Scheme while Proxy-HE can still securely complete tasks within an acceptable time for most functions but with a different security assumption and a simpler system structure.

Blockchain technology is becoming the cornerstone for the development and deployment of other technologies like Federated Learning (FL) and the Internet of Things (IoT), as it plays a critical role in data sharing and incentives. Blockchains supports decentralization, data-privacy protection, security, and reliability. Assuring secure data sharing in mobile computing and FL is challenging because of untrustworthy participants and unknown data quality. Blockchain provides trust in decentralized environments without requiring trusted third parties. By using smart contracts, blockchain has been able to supporting rich decentralized applications. However, the scalability of blockchain is a challenge that prevents its wide adoption by high-performance applications. To address the blockchain scalability issue, various blockchain sharding technologies and off-chain solutions have been proposed. To improve the network throughput, blockchain sharding divides the entire network into several smaller parallel groups and exploits fast consensus algorithms in blockchain shards. Off-chain solutions, such as payment channel networks (PCNs), transfer the slow on-chain transactions to the off-chain environment, in which transactions can be accelerated. Without consensus and on-chain expensive operations, off-chain scalable solutions significantly reduce transaction costs and increase transaction throughput. This special issue aims to provide a forum for the presentation of state-of-the-art research approaches that advance the construction of intelligent blockchain systems. A total of 27 articles were accepted after a two-round rigorous review process. Based on their topics, we have grouped the accepted articles into four categories: blockchain-based federated learning systems, blockchain and the IoT, blockchain scalability, and high-performance blockchains. In what follows, we introduce these articles and their contributions.

Epidemic diseases bring many challenges to universities. In the case of airborne contagious diseases like COVID-19, health agencies’ guidelines recommend that people maintain a physical distance of about 2 meters from each other. Enforcing such physical distancing on a university campus means that it will potentially take longer for students to get into and out of classrooms and buildings on campus. We use real course registration data from a large US university to study wait times students would encounter to enter and exit campus buildings while keeping the recommended 2 meter physical distance, and show that peak wait times can be longer than 20 minutes. We propose LBCS, a load-balanced course scheduling algorithm that intelligently reduces the peak wait time while ensuring that conflicting classes are scheduled at different times. Through simulations we show that LBCS can reduce the peak wait time by a factor of 3×, better than naive alternatives such as shifting some classes to the weekend or randomly perturbing class start times.

Smart cities must adopt innovative technologies and strategies to boost existing sustainability solutions in order to fight climate change and reduce greenhouse gas emissions. We provide an overview of the existing work on the application of blockchain technologies in conjunction with other digital technologies such as IoT for incentivizing individuals and organizations to engage in more sustainable behaviors. We focus on three main areas in which these digital technologies can encourage actions aimed at reducing environmental impact: low-carbon transportation, energy efficiency, and waste diversion. Some notable examples are The Plastic Bank, ECO-Coin and SolarCoin. By analyzing case studies in which monetary and nonmonetary incentives have successfully demonstrated behavior change, we seek to understand the key elements for implementing blockchain-based solutions. We also identify key directions for future research in this area.

As IoT deployments grow in scale for applications such as smart cities, they face increasing cyber-security threats. In particular, as evidenced by the famous Mirai incident and other ongoing threats, large-scale IoT device networks are particularly susceptible to being hijacked and used as botnets to launch distributed denial of service (DDoS) attacks. Real large-scale datasets are needed to train and evaluate the use of machine learning algorithms such as deep neural networks to detect and defend against such DDoS attacks. We present a dataset from an urban IoT deployment of 4060 nodes describing their spatio-temporal activity under benign conditions. We also provide a synthetic DDoS attack generator that injects attack activity into the dataset based on tunable parameters such as number of nodes attacked and duration of attack. We discuss some of the features of the dataset. We also demonstrate the utility of the dataset as well as our synthetic DDoS attack generator by using them for the training and evaluation of a simple multi-label feed-forward neural network that aims to identify which nodes are under attack and when.

IoT data marketplaces are being developed to help cities and communities create large scale IoT applications. Such data marketplaces let the IoT device owners sell their data to the application developers. Following this application development model, the application developers need not deploy their own IoT devices when developing IoT applications; instead, they can buy data from a data marketplace. In a marketplace-based IoT application, the application developers are making critical business and operation decisions using the data produced by seller's IoT devices. Under these circumstances, it is crucial to verify and validate the security of IoT devices.In this paper, we assess the security of IoT data marketplaces. In particular, we discuss what kind of vulnerabilities exist in IoT data marketplaces using the well-known STRIDE model, and present a security assessment and certification framework for IoT data marketplaces to help the device owners to examine the security vulnerabilities of their devices. Most importantly, our solution certifies the IoT devices when they connect to the data marketplace, which helps the application developers to make an informed decision when buying and consuming data from a data marketplace. To demonstrate the effectiveness of the proposed approach, we have developed a proof-of-concept using I3 (Intelligent IoT Integrator), which is an open-source IoT data marketplace developed at the University of Southern California, and IoTcube, which is a vulnerability detection toolkit developed by researchers at Korea University. Through this work, we show that it is possible to increase the reliability of a IoT data marketplace while not damaging the convenience of the users.

Collaborative computing, leveraging resource on multiple wireless-connected devices, enables complex applications that a single device cannot support individually. However, the problem of assigning tasks over devices becomes challenging in the dynamic environments encountered in real-world settings, considering that the resource availability and channel conditions change over time in unpredictable ways due to mobility and other factors. In this paper, we formulate the task assignment problem as an online learning problem using an adversarial multi-armed bandit framework. We propose MABSTA, a novel algorithm that learns the performance of unknown devices and channel qualities continually through exploratory probing and makes task assignment decisions by exploiting the gained knowledge. The implementation of MABSTA, based on Gibbs Sampling approach, is computational-light and offers competitive performance in different scenarios on the trace-data obtained from a wireless IoT testbed. Furthermore, we prove that MABSTA is 1-competitive compared to the best offline assignment for any dynamic environment without stationarity assumptions, and demonstrate the polynomial-time algorithm for the exact implementation of the sampling process. To the best of our knowledge, MABSTA is the first online learning algorithm tailored to this class of problems.

The blockchain technology has achieved tremendous success in open (permissionless) decentralized consensus by employing Proof of Work (PoW) or its variants, whereby unauthorized nodes cannot gain a disproportionate impact on consensus beyond their computational power. However, PoW-based systems incur a high delay and low throughput, making them ineffective in dealing with the real-time Internet-of-Things (IoT) applications. On the other hand, the Byzantine fault-tolerant (BFT) consensus algorithms with better delay and throughput performance cannot be employed in permissionless settings due to vulnerability to Sybil attacks. In this article, we present a Sybil-proof wireless network coordinate-based Byzantine consensus (SENATE), which has the merits of both real-time consensus reaching and Sybil-proof, i.e., it is based on the conventional BFT consensus framework yet works in open systems of wireless devices where faulty nodes may launch Sybil attacks. As in a Senate, in the legislature, where the quota of senators per state (district) is a constant irrespective with the population of the state, “senators” in SENATE are selected from participating distributed nodes based on their wireless network coordinates (WNCs) with a fixed number of nodes per district in the WNC space. Elected senators then participate in the subsequent consensus reaching process and broadcast the result. Thereby, the SENATE is a proof against Sybil attacks since pseudonyms of a faulty node are likely to be adjacent in the WNC space and hence fail to be elected. The simulation results reveal that the SENATE can achieve real-time consensus (consensus delay under one second) in a network of hundreds of nodes.

We consider a star-topology wireless network for status update where a central node collects status data from a large number of distributed machine-type terminals that share a wireless medium. The Age of Information (AoI) minimization scheduling problem is formulated by the restless multi-armed bandit. A widely-proven near-optimal solution, i.e., the Whittle's index, is derived in closed-form and the corresponding indexability is established. The index is then generalized to incorporate stochastic, periodic packet arrivals and unreliable channels. Inspired by the index scheduling policies which achieve near-optimal AoI but require heavy signaling overhead, a contention-based random access scheme, namely Index-Prioritized Random Access (IPRA), is further proposed. Based on IPRA, terminals that are not urgent to update, indicated by their indices, are barred access to the wireless medium, thus improving the access timeliness. A computer-based simulation shows that IPRA's performance is close to the optimal AoI in this setting and outperforms standard random access schemes. Also, for applications with hard AoI deadlines, we provide reliable deadline guarantee analysis. Closed-form achievable AoI stationary distributions under Bernoulli packet arrivals are derived such that AoI deadline with high reliability can be ensured by calculating the maximum number of supportable terminals and allocating system resources proportionally.

A dynamic routing policy, referred to as Heat-Diffusion (HD), is developed for multihop uniclass wireless networks subject to random traffic, time-varying topology and inter-channel interference. The policy uses only current condition of queue occupancies and channel states, with requiring no knowledge of traffic and topology. Besides throughput optimality, HD minimizes an average quadratic routing cost defined by endowing each channel with a time-varying cost factor. Further, HD minimizes average network delay in the class of routing policies that base decisions only on current condition of traffic congestion and channel states. Further, in this class of routing policies, HD provides a Pareto optimal tradeoff between average routing cost and average network delay, meaning that no policy can improve either one without detriment to the other. Finally, HD fluid limit follows graph combinatorial heat equation, which can open a new way to study wireless networks using heat calculus, a very active area of pure mathematics.

The air pollution level is increasing globally at an alarming rate. In the last two decades, many cities have adopted policies to control the emission of pollutants to the atmosphere as well as to promote sustainable urban developments. However, many of these initiatives have concluded that a long term success would require investing in the environmental literacy of the general population. In this demonstration paper, we present USC AiR, a mobile application that translates the air quality sensor feeds from the CCITI smart campus testbed into augmented reality visualizations for the USC community. USC AiR also allows users to report alarming air quality conditions and recommend environmental interventions such as planting trees. We believe that the integration of augmented reality for air quality monitoring enables the citizens to become more engaged with the air quality data while encouraging them to contribute to the reduction of anthropogenic air pollutants.

The connected and autonomous vehicles are expected to rely heavily on connectivity to exchange data and computation services with other vehicles and remote infrastructure including roadside units and other edge infrastructure to increase their immediate view, which leads to greater safety, coordination and more comfortable experience for their human occupants. In order for vehicles to obtain data, compute and other services from other vehicles or road-side infrastructure, it is important to be able to make micropayments for those services and for the services to run seamlessly despite the challenges posed by mobility and ephemeral interactions with a dynamic set of neighboring devices. We present MOTIVE, a trusted and decentralized framework that allows vehicles to make peer-to-peer micropayments for data, compute and other services obtained from other vehicles or road-side infrastructure within radio range. The framework utilizes distributed ledger technologies including smart contracts to enable autonomous operation and trusted interactions between vehicles and nearby entities.

In a typical Internet of Things (IoT) application where a central controller collects status updates from multiple terminals, e.g., sensors and monitors, through a wireless multiaccess uplink, an important problem is how to attain timely status updates autonomously. In this paper, the timeliness of the status is measured by the recently proposed age-of-information (AoI) metric; both the theoretical and practical aspects of the problem are investigated: we aim to obtain a scheduling policy with minimum AoI and, meanwhile, requires little signaling exchange overhead. Toward this end, we first consider the set of arrival-independent and renewal policies; the optimal policy thereof to minimize the time-average AoI is proved to be a round-robin policy with one-packet (latest packet only and others are dropped) buffers (RR-ONE). The optimality is established based on a generalized Poisson-arrival-see-time-average theorem. It is further proved that RR-ONE is asymptotically optimal among all policies in the massive IoT regime. The AoI steady-state stationary distribution under RR-ONE is also derived. An implementation scheme of RR-ONE is proposed which can accommodate dynamic terminal appearances with little overhead. In addition, considering scenarios where packets cannot be dropped, a Lyapunov optimization-based max-AoI-weight policy is proposed which achieves better performance compared with state-of-the-art.

We present the Intelligent Robotic IoT System (IRIS), a modular, portable, scalable, and open-source testbed for robotic wireless network research. There are two key features that separate IRIS from most of the state-of-the-art multi-robot testbeds. (1)Portability: IRIS does not require a costly static global positioning system such as a VICON system nor time-intensive vision-based SLAM for its operation. Designed with an inexpensive Time Difference of Arrival (TDoA)localization system with centimeter level accuracy, the IRIS testbed can be deployed in an arbitrary uncontrolled environment in a matter of minutes. (2)Programmable Wireless Communication Stack: IRIS comes with a modular programmable low-power IEEE 802.15.4 radio and IPv6 network stack on each node. For the ease of administrative control and communication, we also developed a lightweight publish-subscribe overlay protocol called ROMANO that is used for bootstrapping the robots (also referred to as the IRISbots), collecting statistics, and direct control of individual robots, if needed. We detail the modular architecture of the IRIS testbed design along with the system implementation details and localization performance statistics.

We consider a system where multiple terminals transmit their randomly generated status updates to a base station (BS) sharing a wireless multiaccess uplink channel. The problem of interest, especially in massive Internet-of-Things systems, is that how to schedule the terminals to minimize the time-average age-of-information in a decentralized manner, namely terminals transmit autonomously without signalling exchange (overhead) with the BS or other terminals. Towards this end, the round-robin with one-packet buffers (the newest packet at each terminal only) policy (RR-ONE) is proposed and proved optimal among arrival-independent renewal (AIR) policies. In addition to its simple structure which is instrumental for decentralized implementation, RR-ONE is further proved asymptotically (massive terminals) optimal among all policies, including centralized and non-causal policies.

No abstract available.

Many applications in Wireless Sensor Networks (WSNs) require collecting massive data in a coordinated approach. To that end, a many-to-one (convergecast) communication pattern is used in tree-based WSNs. However, traffic near the sink node usually becomes the network bottleneck. In this work, we propose an extension to the 802.15.4 standard for enabling wider bandwidth channels. Then, we measure the speed of data collection in a tree-based WSN, with radios operating in these wider bandwidth channels. Finally, we propose and implement Funneling Wider Bandwidth (FWB), an algorithm that minimizes schedule length in networks. We prove that the algorithm is optimal in regard to the number of time slots. In our simulations and experiments, we show that FWB achieves a higher average throughput and a smaller number of time slots. This new approach could be adapted for other relevant emerging standards, such as WirelessHART, ISA 100.11a and IEEE 802.15.4e TSCH.

Base station (BS) sleeping is an effective way to reduce the energy consumption of mobile networks. Previous efforts to design sleeping control algorithms mainly rely on stochastic traffic models and analytical derivation. However, the tractability of models often conflicts with the complexity of real-world traffic, making it difficult to apply in reality. In this paper, we propose a data-driven algorithm for dynamic sleeping control called DeepNap. This algorithm uses a deep Q-network (DQN) to learn effective sleeping policies from high-dimensional raw observations or un-quantized systems state vectors. We propose to enhance the original DQN algorithm with action-wise experience replay and adaptive reward scaling to deal with the challenges in nonstationary traffic. We also provide a model-assisted variant of DeepNap through the Dyna framework for inferring and simulating system dynamics. Periodical traffic modeling makes it possible to capture the nonstationarity in real-world traffic and the incorporation with DQN allows for feature learning and generalization from model outputs. Experiments show that both the end-to-end and the model-assisted version of DeepNap outperform table-based${Q}$-learning algorithm and the nonstationarity enhancements improve the stability of vanilla DQN.

We consider the problem of power allocation over one or more time-varying channels with unknown distributions in energy harvesting communications. In the single-channel case, the transmitter chooses the transmit power based on the amount of stored energy in its battery with the goal of maximizing the average rate over time. We model this problem as a Markov decision process (MDP) with transmitter as the agent, battery status as the state, transmits power as the action and rate as the reward. The average reward maximization problem can be modeled by a linear program (LP) that uses the transition probabilities for the state-action pairs and their reward values to select a power allocation policy. This problem is challenging because the uncertainty in channels implies that the mean rewards associated with the state-action pairs are unknown. We therefore propose two online learning algorithms: linear program of sample means (LPSM) and Epoch-LPSM that learn these rewards and adapt their policies over time. For both algorithms, we prove that their regret is upper-bounded by a constant. To our knowledge this is the first result showing constant regret learning algorithms for MDPs with unknown mean rewards. We also prove an even stronger result about LPSM: that its policy matches the optimal policy exactly in finite expected time. Epoch-LPSM incurs a higher regret compared with the LPSM, while reducing the computational requirements substantially. We further consider a multi-channel scenario, where the agent also chooses a channel in each slot, and present our multi-channel LPSM (MC-LPSM) algorithm that explores different channels and uses that information to solve the LP during exploitation. MC-LPSM incurs a regret that scales logarithmically in time and linearly in the number of channels. Through a matching lower bound on the regret of any algorithm, we also prove the asymptotic order optimality of MC-LPSM.

Base stations equipped with resources to harvest renewable energy are not only environment-friendly but can also reduce the grid energy consumed, thus bringing cost savings for the cellular network operators. Intelligent management of the harvested energy can further increase the cost savings. Such management of energy savings has to be carefully coupled with managing the quality of service so as to ensure customer satisfaction. In such a process, there is a trade-off between the energy drawn from grid and the quality of service. Unlike prior studies which mainly focus on network energy minimization, this paper proposes a framework for jointly managing the grid energy savings and the quality of service (in terms of the network latency), which is achieved by downlink power control and user association reconfiguration. We use a real BS deployment scenario from London, U.K., to show the performance of our proposed framework and compare it against existing benchmarks. We show that the proposed framework can lead to around 60% grid energy savings as well as better network latency performance than the traditionally used scheme.

With mobile devices increasingly able to connect to cloud servers from anywhere, resource-constrained devices can potentially perform offloading of computational tasks to either save local resource usage or improve performance. It is of interest to find optimal assignments of tasks to local and remote devices that can take into account the application-specific profile, availability of computational resources, and link connectivity, and find a balance between energy consumption costs of mobile devices and latency for delay-sensitive applications. We formulate an NP-hard problem to minimize the application latency while meeting prescribed resource utilization constraints. Different from most of existing works that either rely on the integer programming solver, or on heuristics that offer no theoretical performance guarantees, we propose Hermes, a novel fully polynomial time approximation scheme (FPTAS). We identify for a subset of problem instances, where the application task graphs can be described as serial trees, Hermes provides a solution with latency no more than (1 + ε) times of the minimum while incurring complexity that is polynomial in problem size and 1/ε. We further propose an online algorithm to learn the unknown dynamic environment and guarantee that the performance gap compared to the optimal strategy is bounded by a logarithmic function with time. Evaluation is done by using real data set collected from several benchmarks, and is shown that Hermes improves the latency by 16 percent compared to a previously published heuristic and increases CPU computing time by only 0.4 percent of overall latency.

We formulate the problem of robots ferrying messages between statically-placed source and sink pairs that they can communicate with wirelessly. We first analyze the capacity region for this problem under ideal conditions. We indicate how robots could be scheduled optimally to satisfy any arrival rate in the capacity region, given prior knowledge about arrival rate. We then consider the setting where the arrival rate is unknown and present a coarse-grained backpressure message ferrying algorithm (CBMF) for it. In CBMF, the robots are matched to sources and sinks once every epoch to maximize a queue-differential-based weight. The matching controls both motion and transmission for each robot. We show through analysis and simulations the conditions under which CBMF can stabilize the network, and its corresponding delay performance. From a practical point of view, we propose a heuristic approach to adapt the epoch duration according to network conditions that can improve the end-to-end delay while guaranteeing the network stability at the same time. We also study the structural properties with its explicit delay performance of the CBMF algorithm in a homogeneous network.

Suppose a disaster happens, and several groups of robots are dispatched from distant control stations. To enable rescue staff to make collective decisions, reliable and robust connections need to be established among stations. Motivated by this scenario, a two-stage robot deployment strategy is proposed for wireless robotic networks (WRNs). In the first stage, robots in distant groups are merged into one group that covers a desirable area. Since connectivity alone cannot guarantee a high communication quality, in the second stage, the flow between any two stations is further optimized in terms of expected number of transmissions per successfully delivered packet. In both stages, a distributed collision-free controller is proposed to regulate the interactive force among robots. The stability issues of WRNs, where the proposed controller together with a class of interaction models based on an acute angle test is implemented for robots, are analyzed under both fixed and switching topology. In order to efficiently switch the neighbor set for each robot, a new energy function is constructed taking finite-time consensus into account. To guarantee that energy agreement is achieved before the next topology change, a fixed-time consensus approach is further proposed and an upper bound of the settling time for the energy agreement is obtained. Numerical simulations are provided to demonstrate the effectiveness of the two-stage deployment strategy.

In wireless sensor networks, data collection (or gathering) is the task of transmitting rounds of measurements of physical phenomena from the sensor nodes to a sink node. We study how to increase the efficiency of data collection via supervised in-network classification of rounds of measurements. We assume that the end users of the data are interested only in rounds characterized by certain patterns. Hence the wireless sensor network uses classification to select the rounds of measurements that are transmitted to the base station. The energy consumption is potentially reduced by avoiding the transmission of rounds of measurements that are not of interest to the end users. In-network classification requires distributed feature extraction and transmission. Such tasks can be less or more energy expensive than the transmission of measurements without classification. We provide analytical results and simulations on real data to show requirements and key trade-offs for the design of in-network data classification systems that can improve the collection efficiency. Besides, we study the impact of spatial subsampling of the sensor data (a way to further decrease energy consumption) on the classification performance.

To reduce the energy consumption of various information and communication systems, sleeping mechanism design is considered to be a key problem. Prior work has derived optimal single server sleeping policies only for non-bursty, memoryless Poisson arrivals. In this paper, for the first time, we derive the optimal sleep operation for a single server facing bursty traffic arrivals. Specifically, we model job arrivals as a discrete-time interrupted Bernoulli process (IBP) which models bursty traffic arrivals. Key factors including the switching and working energy consumption costs as well as a delay penalty are accounted for in our model. As the arrival process state (busy or quiet) cannot be directly observed by the server, we formulate the problem as a POMDP (partially observable Markov decision process), and show that it can be tractably solved as a belief-MDP by considering the time interval since the last observed arrival t. We prove that the optimal sleeping policy is hysteretic and the numerical results reveal that the optimal policy is a t-based two- threshold policy, where the sleeping thresholds change with t. The simulation results show that our policy outperforms the previously derived Poisson-optimal policy and that the system cost decreases with the burstiness of traffic.

Short range vehicle to vehicle and device to device communications are of growing interest due to their utility for vehicular safety and infotainment applications as well as for improving the capacity of cellular networks. These mobile systems are characterized by ephemeral, stochastic links. We consider a fundamental problem in this domain -- how to maximize the amount of useful content downloaded by a client from a server over an encounter that lasts a random amount of time. We assume that the distribution of link duration is known or estimated \emph{a priori} based on historical as well as real-time measurements. We present MERLIN (Maximum Expected download over Random LINks), a single-phase file request protocol that is provably optimal. We evaluate MERLIN comprehensively via simulations based on both ideal link duration distributions as well as empirical distributions obtained from real vehicular mobility traces (from Taxis in Shanghai and Buses in Chicago). We also present two Contiki OS-based implementations of MERLIN (with local and remote calculations) evaluated on the Tmote Sky wireless embedded platform.

Currently, there is an increasing number of patients that are treated in-home, mainly in countries such as Japan, USA and Europe. As well as this, the number of elderly people has increased significantly in the last 15 years and these people are often treated in-home and at times enter into a critical situation that may require help (e.g. when facing an accident, or becoming depressed). Advances in ubiquitous computing and the Internet of Things (IoT) have provided efficient and cheap equipments that include wireless communication and cameras, such as smartphones or embedded devices like Raspberry Pi. Embedded computing enables the deployment of Health Smart Homes (HSH) that can enhance in-home medical treatment. The use of camera and image processing on IoT is still an application that has not been fully explored in the literature, especially in the context of HSH. Although use of images has been widely exploited to address issues such as safety and surveillance in the house, they have been little employed to assist patients and/or elderly people as part of the home-care systems. In our view, these images can help nurses or caregivers to assist patients in need of timely help, and the implementation of this application can be extremely easy and cheap when aided by IoT technologies. This article discusses the use of patient images and emotional detection to assist patients and elderly people within an in-home healthcare context. We also discuss the existing literature and show that most of the studies in this area do not make use of images for the purpose of monitoring patients. In addition, there are few studies that take into account the patient's emotional state, which is crucial for them to be able to recover from a disease. Finally, we outline our prototype which runs on multiple computing platforms and show results that demonstrate the feasibility of our approach.

Backpressure routing, in which packets are preferentially transmitted over links with high queue differentials, offers the promise of throughput-optimal operation for a wide range of communication networks. However, when traffic load is low, backpressure methods suffer from long delays. This is of particular concern in intermittent encounter-based mobile networks which are already delay-limited due to the sparse and highly dynamic network connectivity. While state of the art mechanisms for such networks have proposed the use of redundant transmissions to improve delay, they do not work well when traffic load is high. In this paper we propose backpressure with adaptive redundancy (BWAR), a novel hybrid approach that provides the best of both worlds. This approach is robust, distributed, and does not require any prior knowledge of network load conditions. We also present variants of BWAR that remove redundant packets via a timeout mechanism, and that improve energy use. These algorithms are evaluated by mathematical analysis and by simulations of real traces of taxis in Beijing, China. The simulations confirm that BWAR outperforms traditional backpressure at low load, while outperforming encounter-routing schemes (Spray and Wait and Spray and Focus) at high load.

We present a study which aims to infer the vehicular traffic origin-destination matrix for the Los Angeles Downtown Area, from a unique real-world LA Metro data source which comprises sensor information of traffic counts and speeds obtained in real-time from LA arterial road intersections. We review the possible solution approaches and discuss the one is used here in details. The final results are presented for three different time intervals with different traffic regimes of the same day.

With mobile devices increasingly able to connect to cloud servers from anywhere, resource-constrained devices can potentially perform offloading of computational tasks to either improve resource usage or improve performance. It is of interest to find optimal assignments of tasks to local and remote devices that can take into account the application-specific profile, availability of computational resources, and link connectivity, and find a balance between energy consumption costs of mobile devices and latency for delay-sensitive applications. Given an application described by a task dependency graph, we formulate an optimization problem to minimize the latency while meeting prescribed resource utilization constraints. Different from most of existing works that either rely on an integer linear programming formulation, which is NP-hard and not applicable to general task dependency graph for latency metrics, or on intuitively derived heuristics that offer no theoretical performance guarantees, we propose Hermes, a novel fully polynomial time problem approximation scheme (FPTAS) algorithm to solve this problem. Hermes pros vides a solution with latency no more than (1 + ε) times of the minimum while incurring complexity that is an polynomial in problem size and //ε We evaluate the performance by using real data set collected from several benchmarks, and show that Hermes improves the latency by 16% (36% for larger scale application) compared to a previously published heuristic and increases CPU computing time by only 0.4% of overall latency.

We consider the problem of deploying a team of robots in an unknown, obstructed environment to form a multi-hop communication network. As a solution, we present a unified framework, onLinE rObotic Network formAtion (LEONA), that is general enough to permit optimizing the communication network for different utility functions in non-convex environments. LEONA adopts the principle of “optimism in the face of uncertainty” to allow the team of robots to form optimal network configurations efficiently and rapidly without having to map link qualities in the entire area. We demonstrate and evaluate this framework on two specific scenarios concerning the formation of a multi-hop communication path between fixed end-points: one minimizing the total path cost, and another maximizing the bottleneck communication rate. Our simulation-based evaluation shows that the use of the optimism principle can significantly reduce resources spent in exploring and mapping the entire region prior to network optimization. We also present a mathematical modeling of how the searched area scales with various relevant parameters in each case.

Cities with a large number of people are currently facing urban mobility problems, especially the problem of traffic congestions. This not only has an adverse effect on the economy of the city, but also impairs the quality of life of its citizens. One measure that can be adopted to mitigate these problems is the use of systems that help identify, reduce, and/or avoid these traffic jams, such as intelligent transport systems. In this context, we propose an intelligent traffic information system called UCONDES, which is based on inter-vehicle communications and can be applied to detect and reduce congestion in urban centers. Simulation results shows that, when compared to original vehicular mobility trace, our solution reduces the average trip time, and the overall CO2 emission and fuel consumption. More specifically, the average travel time for drivers was reduced by approximately 26%, resulting in a reduction of fuel consumption by 23% and the CO2 emission by 25%.

We study the presence of social communities in mobility traces from vehicular fleets. By analyzing publicly available sets of fleet vehicle mobility traces obtained from two real-world deployments — consisting of more than 2000 taxis in Shanghai and Beijing respectively, we confirm the existence of small numbers of distinct social communities in vehicular networks, which is in direct contrast to the general belief that vehicular networks are best modeled as a relatively homogeneous system. We examine the spatio-temporal characteristics of social communities, gaining the insight that they are driven primarily by social proximity induced by geographic locality. We then develop a parsimonious multi-community ordinary differential equation (ODE) model, which uses the heterogeneous structure introduced by social communities to model information dissemination. We show through simulations that this approach dramatically outperforms the conventional homogeneous ODE model in capturing the dynamics of the dissemination process. We further demonstrate that the use of the ODE model to optimize seeding of an initial set of vehicles results in improved utility for information dissemination compared to seed-optimization using a homogeneous model.

Sequence-based localization (SBL) is a technique whereby a node is localized based on the ranked sequence of signal strengths obtained from a set of beacon nodes. SBL effectively partitions the area into regions corresponding to unique ranked sequences. Prior work has developed SBL under the assumption that all beacons have the same transmit power. In this work, we consider beacons with unequal transmit power for sequence-based localization and present heuristic algorithms for joint transmit power optimization and beacon placement. We show through comprehensive simulations that a novel enhancement of SBL utilizing optimized non-uniform transmit powers, coupled with careful beacon placement, which we refer to as NU-SBL, can dramatically improve the area partitioning compared to traditional SBL. However, in evaluating these schemes under stochastic fading, we find that the original SBL with optimized location performs nearly as well or slightly better than NU-SBL in many cases. We introduce another scheme, that we refer to as NU-SBL-ZOOM, which further allows the power levels to be optimized non-uniformly so as to focus in on a particular smaller region within the larger localization space. NU-SBL-ZOOM is found to perform much better in terms of both area partitioning as well as location error in the presence of fading.

Computation Offloading, sending computational tasks to more resourceful servers, is becoming a widely-used approach to save limited resources on mobile devices like battery life, storage, processor, etc. Given an application that is partitioned into multiple tasks, the offloading decisions can be made on each of them. However, considering the delay constraint and the extra costs on data transmission and remote computation, it is not trivial to make optimized decisions. Existing works have formulated offloading decision problems as either graph-partitioning or binary integer programming problems. The first approach can solve the problem in polynomial time but is not applicable to delay constraints. The second approach relies on an integer programming solver without a polynomial time guarantee. We provide an algorithm, DTP (Deterministic delay constrained Task Partitioning), to solve the offloading decision problem with delay constraints. DTP gives near-optimal solution and runs in polynomial time in the number of tasks. Going beyond prior work on linear delay constraints that apply only to serial tasks, we generalize the delay constraints to settings where the dependency between tasks can be described by a tree. Furthermore, we provide another algorithm, PTP (Probabilistic delay constrained Task Partitioning), which gives stronger QoS guarantees. Simulation results show that our algorithms are accurate and robust, and scale well with the number of tasks.

A new routing policy, named Heat-Diffusion (HD), is developed for multihop wireless networks subject to stochastic arrivals, time-varying topology, and inter-channel interference, using only current queue congestion and current channel states, without requiring the knowledge of topology and arrivals. Besides throughput optimality, HD minimizes a quadratic routing cost defined by endowing each channel with a cost-factor. It also minimizes average total queue congestion, and so average network delay, within the class of routing policies that base decision only on current queue lengths and current channel states. Further, within this class, HD provides a Pareto optimal tradeoff between average delay and average routing cost, meaning that no policy can improve either one without detriment to the other. Finally, HD fluid limit follows graph combinatorial heat equation that opens a new way to study wireless networks using heat calculus, a very active area of pure mathematics.

Cellular networks can be operated more energy-efficiently if operators agree to share base-stations during off-peak hours. We apply a micro-economic analysis for a single-cell two-operator scenario to investigate the conditions under which self-interested operators would agree to share resources in this manner. Our analysis yields a comprehensive treatment of the existence and number of Nash Equilibria. We consider the cases when the payment rates are exogenous, as well as when they can be set strategically by the operators. Through numerical solutions we examine the quality of the best and worst Nash Equilibria in comparison with the globally optimized solution. Our results show that there is often a sensitive dependence on key parameters such as energy price, capacity, load, revenues, penalties and payments.

In this paper, we demonstrate a novel hybrid architecture for coordinating networked robots in sensing and information routing applications. The proposed INformation and Sensing driven PhysIcally REconfigurable robotic network (INSPIRE), consists of a Physical Control Plane (PCP) which commands agent position, and an Information Control Plane (ICP) which regulates information flow towards communication/sensing objectives. We describe an instantiation where a mobile robotic network is dynamically reconfigured to ensure high quality routes between static wireless nodes, which act as source/destination pairs for information flow. We demonstrate our propositions through simulation under a realistic wireless network regime.

We are interested in modeling the total expected data collection time for a set of cars (or other mobile nodes) to aggregate the information that they are each carrying to a single vehicle. Data collection processes between cars -- or other mobile nodes -- can be modeled as random walks of particles on a graph, and in this model, data is transferred between data-possessing cars once they encounter each other on the same node of the graph. We analyze this process in the special case in which this graph is a square grid torus graph. Recursion occurs in the system because once an encounter between multiple cars that possess data occurs, the system becomes analogous to simpler systems with the same graph and with fewer cars that possess data. We make approximations for the total data collection time using this recursive property.

We present the design and implementation of Multi-Channel Collection (MCC) protocol , a high-rate multi-channel time-scheduled protocol for fair, real-time data collection in Wireless Sensor Networks (WSN). MCC incorporates sophisticated mechanisms for balanced routing tree formation, multiple frequency channel allocation and globally synchronized TDMA scheduling. Through systematic experiments with real WSN hardware (Tmote Sky), we identify the maximum possible throughput for many-to-one (convergecast) data collection as a function of key communication parameters such as packet size, use of acknowledgements, and network topology. Then, we demonstrate that the maximum achievable network throughput can in fact be attained in practice using a carefully designed mix of routing, frequency allocation and time scheduling. Compared to state of the art collection protocols for WSN, we show that MCC offers 33-155% improvement in throughput. We also show how to exploit the time-scheduled nature of this approach for reducing the number of required frequency channels. MCC presents an algorithmic approach for time-frequency scheduling and routing that could be adapted and used in conjunction with relevant emerging standards such as WirelessHART, ISA 100.11a and IEEE 802.15.4e TSCH.

We consider the problem of controlling the motion of a set of robots to ferry messages between a given set of statically-placed nodes. The design and analysis of an arrivalrate unaware throughput-optimal policy for this problem is challenging because of the coupling between position and link rate. We propose a fine-grained backpressure message ferrying algorithm (FBMF) for joint motion and transmission control of robots. Unlike traditional backpressure settings, because the controlled motion of the relay nodes changes the channel rates, it turns out that the conventional approach to prove throughput optimality does not work in this problem setting. We prove for the simplest setting (single-flow, single-robot, constant arrival) that this policy indeed achieves throughput optimality. The analysis reveals that under feasible traffic, even when queues are highly over-loaded, the change in the total queue size can be positive over a time step, nevertheless the system exhibits a limit-cycle behavior and stability holds because the change in the total queue size is negative over the cycle for sufficiently large queues. We pose the design and analysis of a throughput optimal policy for the general case as a challenging open problem for network theory.

We present two novel distributed algorithms for hole detection in a wireless sensor network (WSN) based on the distributed Delaunay triangulation of the underlying communication graph. The first, which we refer to as the distance-vector hole determination (DVHD) algorithm, is based on traditional distance vector routing for multi-hop networks and shortest path lengths between node pairs. The second, which we refer to as the Gaussian curvature-based hole determination (GCHD) algorithm, applies the Gauss-Bonnet theorem on the Delaunay graph to calculate the number of holes based on the graph's Gaussian curvature. We present a detailed comparative performance analysis of both methods based on simulations, showing that while DVHD is conceptually simpler, the GCHD algorithm shows better performance with respect to run-time and message count per node.

We consider the problem of how to identify a set of seed nodes in order to disseminate content efficiently in a vehicular network. We consider several relevant dimensions including proximity, encounters, speed, etc. and identify and taxonomize a number of candidate strategies. We comparatively evaluate these strategies using a set of real vehicular traces (Taxis in Beijing). We conclude that identifying seeds based on their speed, while eliminating redundant and isolated nodes, is the most effective approach, performing significantly better than the previously random seed strategy.

Pure opportunistic dissemination of content in a vehicular network can incur high delays if the number of vehicles is relatively low. We consider in this paper an areabased approach to information broadcast in which vehicle to vehicle (V2V) communications is supplemented with vehicle to infrastructure (V2I) communications in order to improve the delay performance. We show how area-based dissemination can analyzed mathematically using a Markovian model. We also investigate through trace-based simulations how different area partitioning approaches affect the total dissemination time.

Minimum cost routing is considered on multiclass multihop wireless networks influenced by stochastic arrivals, inter-channel interference, and time-varying topology. Endowing each air link with a cost factor, possibly time-varying and different for different classes, we define the Dirichlet routing cost as the square of the link packet transmissions weighted by the link cost-factors. Our recently-proposed Heat-Diffusion (HD) routing protocol [3] is extended to minimize this cost, while ensuring queue stability for all stabilizable traffic demands, and without requiring any information about network topology or packet arrivals. This is the first time in literature that such a multiclass routing penalty can be minimized at network layer subject to queue stability. Further, when all links are of unit cost factor, our protocol here reduces to the one in our recent paper [4], leading to minimum average network delay among all routing protocols that act based only on current queue congestion and current channel states. Our approach is based on mapping a communication network into an electrical network by showing that the fluid limit of wireless network under our routing protocol follows Ohm's law on a nonlinear resistive network.

A fundamental theoretical problem in opportunistic spectrum access is the following: a single secondary user must choose a channel to sense and access at each time, with the availability of each channel (due to primary user behavior) described by a Markov Chain. The problem of maximizing the expected channel usage can be formulated as a restless multi-armed bandit. We present in this paper an online learning algorithm with the best known results to date for this problem in the case when channels are homogeneous and the channel statistics are unknown a priori. Specifically, we show that this policy, that we refer to as CSE, achieves a regret (the gap between the rewards accumulated by a model-aware Genie and the policy) that is bounded in finite time by a function that scales as O(log t). By explicitly learning the underlying statistics over time, this novel policy outperforms a previously proposed scheme shown to provide near-logarithmic regret.

We formulate and address mathematically the fundamental problem of resource allocation in the form of helper nodes in disseminating multiple content in a hybrid intermittently connected mobile network under a general stochastic homogeneous contact process. We consider and solve two variations of the problem - one in which the goal is to maximize the expected demands satisfied and another in which the goal is to minimize the time taken to disseminate the contents. Besides the global optimization perspective, we also examine the problem from a game theoretic perspective in which a central agent auctions the storage to competing content providers, and show how self-interested decisions impact the social welfare.

Disseminating shared information to many vehicles could incur significant access fees if it relies only on unicast cellular communications. We consider the problem of efficient content dissemination over a vehicular network, in which vehicles are equipped with two kinds of radios: a high-cost low-bandwidth, long-range cellular radio, and a free high-bandwidth short-range radio. We formulate and solve an optimization problem to maximize content dissemination from the infrastructure to vehicles within a predetermined deadline while minimizing the cost associated with communicating over the cellular connection. We examine numerically the tradeoffs between cost, delay and system utility in the optimum regime. We find that, in the optimum regime, (a) system utility is more sensitive to the cost budget when the allowed delay for the dissemination is not large, (b) the system requires relatively smaller cost budget as more vehicles participate and more delay is allowed, (c) when the cost is very important, it is better not to spread the content if it needs small delay. We also develop a polynomial-time algorithm to obtain the optimal discrete solution needed in practice. Finally, we verify our analysis using real GPS traces of 632 taxis in Beijing, China.

We investigate the benefits of distributed storage using erasure codes for file sharing in vehicular networks through both analysis and realistic trace-based simulations. We show that the key parameter affecting the on-demand file download latency is the ratio of file size to download bandwidth. When this ratio is small so that a file can be communicated in a single encounter, we find that coding techniques offer very little benefit over simple file replication. However, we analytically show that for large ratios, for a memoryless contact model, distributed erasure coding yields a latency benefit of N/α over uncoded replication, where N is the number of vehicles and α the redundancy factor. Effectively, in this regime, coding yields the same performance as replicating all the files at all other vehicles, but using much less storage. We also evaluate the benefits of coded storage using large real vehicle traces of taxis in Beijing and buses in Chicago. These simulations, which include a realistic radio link quality model for a IEEE 802.11p dedicated short range communication (DSRC) radio, validate the observations from the analysis, demonstrating that coded storage dramatically speeds up the download of large files in vehicular networks.

In a communication system with time varying channel qualities, it is ideal to allocate the limited transmission power to channels that will be in good state. However, it is very challenging to do so because channel states are usually unknown when the power allocation decision is made. In this paper, we derive an optimal power allocation policy that can maximize the expected discounted number of bits transmitted over an infinite time span. Specifically, we first model this problem as a partially observable Markov decision processes (POMDP), and analytically investigate the structure of the optimal policy. Then a simple threshold-based policy is derived for a three-channel communication system. By formulating and solving a linear programming formulation of this power allocation problem, we further verified the derived structure of the optimal policy.

We study the fundamental problem of optimal power allocation over two identical Gilbert-Elliott (Binary Markov) communication channels. Our goal is to maximize the expected discounted number of bits transmitted over an infinite time span by judiciously choosing one of the four actions for each time slot: 1) allocating power equally to both channels, 2) allocating all the power to channel 1, 3) allocating all the power to channel 2, and 4) allocating no power to any of the channels. As the channel state is unknown when power allocation decision is made, we model this problem as a partially observable Markov decision process(POMDP), and derive the optimal policy which gives the optimal action to take under different possible channel states. Two different structures of the optimal policy are derived analytically and verified by linear programming simulation. We also illustrate how to construct the optimal policy by the combination of threshold calculation and linear programming simulation once system parameters are known.

We study the problem of power allocation over two identical Gilbert-Elliot communication channels. Our goal is to maximize the expected discounted number of bits transmitted over an infinite time horizon. This is achieved by choosing among three possible strategies: (1) betting on channel 1 by allocating all the power to this channel, which results in high data rate if channel 1 happens to be in good state, and zero bits transmitted if channel 1 is in bad state (even if channel 2 is in good state) (2) betting on channel 2 by allocating all the power to the second channel, and (3) a balanced strategy whereby each channel is allocated half the total power, with the effect that each channel can transmit a low data rate if it is in good state. We assume that each channel's state is only revealed upon transmission of data on that channel. We model this problem as a partially observable Markov decision processes (MDP), and derive key threshold properties of the optimal policy. Further, we show that by formulating and solving a relevant linear program the thresholds can be determined numerically when system parameters are known.

There has been considerable work developing a stochastic network utility maximization framework using Backpressure algorithms, also known as MaxWeight. A key open problem has been the development of utility-optimal algorithms that are also delay-efficient. In this paper, we show that the Backpressure algorithm, when combined with the last-in-first-out (LIFO) queueing discipline (called LIFO-Backpressure), is able to achieve a utility that is withinO(1/V) of the optimal value, for any scalarV≥ 1, while maintaining an average delay ofO([log(V)]2) for all but a tiny fraction of the network traffic. This result holds for a general class of problems with Markovian dynamics. Remarkably, the performance of LIFO-Backpressure can be achieved by simply changing the queueing discipline; it requires no other modifications of the original Backpressure algorithm. We validate the results through empirical measurements from a sensor network testbed, which show a good match between theory and practice. Because some packets may stay in the queues for a very long time under LIFO-Backpressure, we further develop the LIFOp-Backpressure algorithm, which generalizes LIFOp-Backpressure by allowing interleaving between first-in-first-out (FIFO) and LIFO. We show that LIFOpBackpressure also achieves the sameO(1/V) close-to-optimal utility performance and guarantees an average delay ofO([log(V)]2) for the packets that are served during the LIFO period.

In this paper, we investigate dynamic base station (BS) switching to reduce energy consumption in wireless cellular networks. Specifically, we formulate a general energy minimization problem pertaining to BS switching that is known to be a difficult combinatorial problem and requires high computational complexity as well as large signaling overhead. We propose a practically implementable switching-on/off based energy saving (SWES) algorithm that can be operated in a distributed manner with low computational complexity. A key design principle of the proposed algorithm is to turn off a BS one by one that will minimally affect the network by using a newly introduced notion of network-impact, which takes into account the additional load increments brought to its neighboring BSs. In order to further reduce the signaling and implementation overhead over the air and backhaul, we propose three other heuristic versions of SWES that use the approximate values of network-impact as their decision metrics. We describe how the proposed algorithms can be implemented in practice at the protocol-level and also estimate the amount of energy savings through a first-order analysis in a simple setting. Extensive simulations demonstrate that the SWES algorithms can significantly reduce the total energy consumption, e.g., we estimate up to 50-80% potential savings based on a real traffic profile from a metropolitan urban area.

We propose a new scheduling and routing approach, the Heat Diffusion (HD) protocol, using combinatorial analogue of the heat equation in mathematical physics. The algorithm holds for systems subject to time-varying network conditions with general packet arrivals and random topology states, including ad-hoc networks with mobility. Compared to the well-known backpressure policy, the HD protocol is generalized in form and optimized in performance, which considers link penalties and node capacities in the routing. It mitigates the packet looping behavior of backpressure and attempts to communicate less over links of higher costs and with the nodes of lower capacities. While HD policy shows benefits over backpressure, it is developed using the same underlying control laws. Therefore, it can easily leverage all the theoretical works that have been done in improving the original backpressure. For the same reason, it provides a relatively easy path-way to modify existing applications of backpressure to the optimized versions using HD protocol.

With the advent of the new IEEE 802.11p DSRC/WAVE radios, Vehicle-to-Vehicle (V2V) communications is poised for a dramatic leap. A canonical application for these future vehicular networks is the detection and notification of anomalous road events (e.g., potholes, bumps, icy road patches, etc.). We present the Road Information Sharing Architecture (RISA), the first distributed approach to road condition detection and dissemination for vehicular networks. RISA provides for the in-network aggregation and dissemination of event information detected by multiple vehicles in a timely manner for improved information reliability and bandwidth efficiency. RISA uses a novel Time-Decay Sequential Hypothesis Testing (TD-SHT) approach in which event information from multiple sources is combined with time-varying beliefs. We describe our implementation of RISA which has been deployed and tested on a fleet of vehicles on-site at the GM Warren Technical Center in Michigan. We further provide a comprehensive evaluation of the aggregation mechanism using emulation of the RISA code on real vehicular mobility traces.

Backpressure scheduling and routing, in which packets are preferentially transmitted over links with high queue differentials, offers the promise of throughput-optimal operation for a wide range of communication networks. However, when the traffic load is low, due to the corresponding low queue occupancy, backpressure scheduling/routing experiences long delays. This is particularly of concern in intermittent encounter-based mobile networks which are already delay-limited due to the sparse and highly dynamic network connectivity. While state of the art mechanisms for such networks have proposed the use of redundant transmissions to improve delay, they do not work well when the traffic load is high. We propose in this paper a novel hybrid approach that we refer to as backpressure with adaptive redundancy (BWAR), which provides the best of both worlds. This approach is highly robust and distributed and does not require any prior knowledge of network load conditions. We evaluate BWAR through both mathematical analysis and simulations based on a cell-partitioned model. We prove theoretically that BWAR does not perform worse than traditional backpressure in terms of the maximum throughput, while yielding a better delay bound. The simulations confirm that BWAR outperforms traditional backpressure at low load, while outperforming a state of the art encounter-routing scheme (Spray and Wait) at high load.

The problem of opportunistic spectrum access in cognitive radio networks has been recently formulated as a non-Bayesian restless multi-armed bandit problem. In this problem, there are N arms (corresponding to channels) and one player (corresponding to a secondary user). The state of each arm evolves as a finite-state Markov chain with unknown parameters. At each time slot, the player can select K <; N arms to play and receives state-dependent rewards (corresponding to the throughput obtained given the activity of primary users). The objective is to maximize the expected total rewards (i.e., total throughput) obtained over multiple plays. The performance of an algorithm for such a multi-armed bandit problem is measured in terms of regret, defined as the difference in expected reward compared to a model-aware genie who always plays the best K arms. In this paper, we propose a new continuous exploration and exploitation (CEE) algorithm for this problem. When no information is available about the dynamics of the arms, CEE is the first algorithm to guarantee near-logarithmic regret uniformly over time. When some bounds corresponding to the stationary state distributions and the state-dependent rewards are known, we show that CEE can be easily modified to achieve logarithmic regret over time. In contrast, prior algorithms require additional information concerning bounds on the second eigenvalues of the transition matrices in order to guarantee logarithmic regret. Finally, we show through numerical simulations that CEE is more efficient than prior algorithms.

We investigate the benefits of distributed storage using erasure codes for file sharing in vehicular networks through realistic trace-based simulations. We find that coding offers substantial benefits over simple replication when the file sizes are large compared to the average download bandwidth available per encounter. Our simulations, based on a large real vehicle trace from Beijing combined with a realistic radio link quality model for a IEEE 802.11p dedicated short range communication (DSRC) radio, demonstrate that coding provides significant cost reduction in vehicular networks.

This paper considers a component-level deceleration technique in BS operation, called speed-scaling, that is more conservative than entirely shutting down BSs, yet can conserve dynamic power effectively during periods of low load while ensuring full coverage at all times. By formulating a total cost minimization that allows for a flexible tradeoff between delay and energy, we first study how to adaptively vary the processing speed based on incoming load. We then investigate how this speed-scaling affects the design of network protocol, specifically, with respect to user association. Based on our investigation, we propose and analyze a distributed algorithm, called SpeedBalance, that can yield significant energy savings.

Combinatorial network optimization algorithms that compute optimal structures taking into account edge weights form the foundation for many network protocols. Examples include shortest path routing, minimal spanning tree computation, maximum weighted matching on bipartite graphs, etc. We present CLRMR, the first online learning algorithm that efficiently solves the stochastic version of these problems where the underlying edge weights vary as independent Markov chains with unknown dynamics. The performance of an online learning algorithm is characterized in terms of regret, defined as the cumulative difference in rewards between a suitably-defined genie, and that obtained by the given algorithm. We prove that, compared to a genie that knows the Markov transition matrices and uses the single-best structure at all times, CLRMR yields regret that is polynomial in the number of edges and nearly-logarithmic in time.

User/environmental context detection on mobile devices benefits end-users by providing information support to various kinds of applications. A pervasive question, however, is how the sensors on the mobile device should be sampled energy efficiently without sacrificing too much detection accuracy. In this paper, we formulate the user state sensing problem as the intermittent sampling of a semi-Markov process, a model that provides general and flexible capturing of realistic data with any type of state sojourn distributions. We propose (a) a semi-Markov state estimation mechanism that selects the most likely user state while observations are missing, and (b) a semi-Markov optimal sensing policy us* which minimizes the expected state estimation error while maintaining a given energy budget. Their performance are shown to significantly outperform Markov algorithms on simulated two-state processes and real user state traces pertaining to different types of state distributions. Finally, in order to evaluate the performance of us*, we implement a client-server based basic human activity recognition system on N95 smartphones and desktops which automatically computes user-specific optimal sensing policy based on historically collected data. We show that us* improves the estimation accuracy by 27.8% and 48.6% respectively over Markov-optimal policy and uniform sampling through a set of experiments.

We consider the problem of diffusing cached content in an intermittently connected mobile network, starting from a given initial configuration to a desirable goal state where all nodes interested in particular contents have a copy of their desired contents. The goal is to minimize the time taken for the diffusion process to terminate at a goal state. Due to bandwidth and storage constraints, whenever two nodes encounter each other, they must decide which content if any to transfer to each other. While most prior work on this topic has focused on practically realizable heuristics for this problem, we take a more formal approach. Our main contribution is to show that, assuming global state information is available, this problem can be formulated as a stochastic shortest path problem, which is a kind of Markov decision process (MDP). Using this formulation, we numerically explore some small-scale examples for which we are able to obtain the optimal solution. The results show that the optimal diffusion strategy is very much a function of the underlying encounter graph.

We investigate the following fundamental question—how fast can information be collected from a wireless sensor network organized as tree? To address this, we explore and evaluate a number of different techniques using realistic simulation models under the many-to-one communication paradigm known as convergecast. We first consider time scheduling on a single frequency channel with the aim of minimizing the number of time slots required (schedule length) to complete a convergecast. Next, we combine scheduling with transmission power control to mitigate the effects of interference, and show that while power control helps in reducing the schedule length under a single frequency, scheduling transmissions using multiple frequencies is more efficient. We give lower bounds on the schedule length when interference is completely eliminated, and propose algorithms that achieve these bounds. We also evaluate the performance of various channel assignment methods and find empirically that for moderate size networks of about 100 nodes, the use of multifrequency scheduling can suffice to eliminate most of the interference. Then, the data collection rate no longer remains limited by interference but by the topology of the routing tree. To this end, we construct degree-constrained spanning trees and capacitated minimal spanning trees, and show significant improvement in scheduling performance over different deployment densities. Lastly, we evaluate the impact of different interference and channel models on the schedule length.

We formulate the following combinatorial multi-armed bandit (MAB) problem: There areNrandom variables with unknown mean that are each instantiated in an i.i.d. fashion over time. At each time multiple random variables can be selected, subject to an arbitrary constraint on weights associated with the selected variables. All of the selected individual random variables are observed at that time, and a linearly weighted combination of these selected variables is yielded as the reward. The goal is to find a policy that minimizes regret, defined as the difference between the reward obtained by a genie that knows the mean of each random variable, and that obtained by the given policy. This formulation is broadly applicable and useful for stochastic online versions of many interesting tasks in networks that can be formulated as tractable combinatorial optimization problems with linear objective functions, such as maximum weighted matching, shortest path, and minimum spanning tree computations. Prior work on multi-armed bandits with multiple plays cannot be applied to this formulation because of the general nature of the constraint. On the other hand, the mapping of all feasible combinations to arms allows for the use of prior work on MAB with single-play, but results in regret, storage, and computation growing exponentially in the number of unknown variables. We present new efficient policies for this problem that are shown to achieve regret that grows logarithmically with time, and polynomially in the number of unknown variables. Furthermore, these policies only require storage that grows linearly in the number of unknown parameters. For problems where the underlying deterministic problem is tractable, these policies further require only polynomial computation. For computationally intractable problems, we also present results on a different notion of regret that is suitable when a polynomial-time approximation algorithm is used.

We consider the problem of energy-efficient transmission in multi-flow multihop cooperative wireless networks. Although the performance gains of cooperative approaches are well known, the combinatorial nature of these schemes makes it difficult to design efficient polynomial-time algorithms for joint routing, scheduling and power control. This becomes more so when there is more than one flow in the network. It has been conjectured by many authors, in the literature, that the multiflow problem in cooperative networks is an NP-hard problem. In this paper, we formulate the problem, as a combinatorial optimization problem, for a general setting of k-flows, and formally prove that the problem not only NP-hard but it is o(n1/7-ε) inapproxmiable. To our knowledge, the results in this paper provide the first such inapproxmiablity proof in the context of multiflow cooperative wireless networks. We further prove that for a special case of k = 1 the solution is a simple path, and offer a polynomial time algorithm for jointly optimizing routing, scheduling and power control.

The fundamental problem of multiple secondary users contending for opportunistic spectrum access over multiple channels in cognitive radio networks has been formulated recently as a decentralized multi-armed bandit (D-MAB) problem. In a D-MAB problem there are M users and N arms (channels) that each offer i.i.d. stochastic rewards with unknown means so long as they are accessed without collision. The goal is to design a decentralized online learning policy that incurs minimal regret, defined as the difference between the total expected rewards accumulated by a model-aware genie, and that obtained by all users applying the policy. We make two contributions in this paper. First, we consider the setting where the users have a prioritized ranking, such that it is desired for the K-th-ranked user to learn to access the arm offering the K-th highest mean reward. For this problem, we present the first distributed policy that yields regret that is uniformly logarithmic over time without requiring any prior assumption about the mean rewards. Second, we consider the case when a fair access policy is required, i.e., it is desired for all users to experience the same mean reward. For this problem, we present a distributed policy that yields order-optimal regret scaling with respect to the number of users and arms, better than previously proposed policies in the literature. Both of our distributed policies make use of an innovative modification of the well known UCB1 policy for the classic multi-armed bandit problem that allows a single user to learn how to play the arm that yields the K-th largest mean reward.

We consider a combinatorial generalization of the classical multi-armed bandit problem that is defined as follows. There is a given bipartite graph of M users and N≥M resources. For each user-resource pair (i,j), there is an associated state that evolves as an aperiodic irreducible finite-state Markov chain with unknown parameters, with transitions occurring each time the particular user i is allocated resource j. The user i receives a reward that depends on the corresponding state each time it is allocated the resource j. The system objective is to learn the best matching of users to resources so that the long-term sum of the rewards received by all users is maximized. This corresponds to minimizing regret, defined here as the gap between the expected total reward that can be obtained by the best-possible static matching and the expected total reward that can be achieved by a given algorithm. We present a polynomial-storage and polynomial-complexity-per-step matching-learning algorithm for this problem. We show that this algorithm can achieve a regret that is uniformly arbitrarily close to logarithmic in time and polynomial in the number of users and resources. This formulation is broadly applicable to scheduling and switching problems in communication networks including cognitive radio networks and significantly extends prior results in the area.

In the classic Bayesian restless multi-armed bandit (RMAB) problem, there are N arms, with rewards on all arms evolving at each time as Markov chains with known parameters. A player seeks to activate K ≥ 1 arms at each time in order to maximize the expected total reward obtained over multiple plays. RMAB is a challenging problem that is known to be PSPACE-hard in general. We consider in this work the even harder non-Bayesian RMAB, in which the parameters of the Markov chain are assumed to be unknown a priori. We develop an original approach to this problem that is applicable when the corresponding Bayesian problem has the structure that, de pending on the known parameter values, the optimal solution is one of a prescribed finite set of policies. In such settings, we propose to learn the optimal policy for the non-Bayesian RMAB by employing a suitable meta-policy which treats each policy from this finite set as an arm in a different non-Bayesian multi-armed bandit problem for which a single-arm selection policy is optimal. We demonstrate this approach by developing a novel sensing policy for opportunistic spectrum access over unknown dynamic channels. We prove that our policy achieves near-logarithmic regret (the difference in expected reward compared to a model-aware genie), which leads to the same average reward that can be achieved by the optimal policy under a known model. This is the first such result in the literature for a non Bayesian RMAB.

We formulate the problem of delay constrained energy-efficient broadcast in cooperative multihop wireless networks. We show that this important problem is not only NP-complete, but also o(log(n)) inapproximable. We derive approximation results and an analytical lower-bound for this problem. We break this NP hard problem into three parts: ordering, scheduling and power control. We show that when the ordering is given, the joint scheduling and power-control problem can be solved in polynomial time by a novel algorithm that combines dynamic programming and linear programming to yield the minimum energy broadcast for a given delay constraint. We further show empirically that this algorithm used in conjunction with an ordering derived heuristically using the Dijkstra's shortest path algorithm yields near-optimal performance in typical settings. We use our algorithm to study numerically the trade-off between delay and power-efficiency in cooperative broadcast and compare the performance of our cooperative algorithm with a smart non-cooperative algorithm.

We study a novel game theoretic incentive mechanism design problem for network congestion control in the context of selfish users sending data through a single store-and-forward router (a.k.a. “server” in this work). The scenario is modeled as an M/M/1 queueing game with each user (a.k.a. “player”) aiming to optimize a tradeoff between throughput and delay in a selfish distributed manner. We first show that the original game has an inefficient unique Nash Equilibrium (NE). In order to improve the outcome efficiency, we propose an incentivizing packet dropping scheme that can be easily implemented at the server. We then show that if the packet dropping scheme is a function of the sum of arrival rates, we have a modified M/M/1 queueing game that is an ordinal potential game with a unique NE. In particular, for a linear packet dropping scheme, which is similar to the Random Early Detection (RED) algorithm used with TCP, we show that there exists a unique Nash Equilibrium. For this scheme, the social welfare (expressed either as the summation of utilities of all players or log summation of utilities of all players) at the equilibrium point can be arbitrarily close to the social welfare at the global optimal point. Finally, we show that the simple best response dynamic converges to this unique efficient Nash Equilibrium.

There has been considerable recent work developing a new stochastic network utility maximization framework using Backpressure algorithms, also known as MaxWeight. A key open problem has been the development of utility-optimal algorithms that are also delay efficient. In this paper, we show that the Backpressure algorithm, when combined with the LIFO queueing discipline (called LIFO-Backpressure), is able to achieve a utility that is within O(1/V) of the optimal value for any scalar V ≥ 1, while maintaining an average delay of O([log(V)]2) for all but a tiny fraction of the network traffic. This result holds for general stochastic network optimization problems and general Markovian dynamics. Remarkably, the performance of LIFO-Backpressure can be achieved by simply changing the queueing discipline; it requires no other modifications of the original Backpressure algorithm. We validate the results through empirical measurements from a sensor network testbed, which show good match between theory and practice.

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.

We investigate the tradeoff between two mutually conflicting performance objectives-throughput and delay-for fast, periodic data collection in tree-based sensor networks arbitrarily deployed in 2-D. Two primary factors that affect the data collection rate (throughput) and timeliness (delay) are: 1) efficiency of the link scheduling protocol, and 2) structure of the routing tree in terms of its node degrees and radius. In this paper, we utilize multiple frequency channels and design an efficient link scheduling protocol that gives a constant factor approximation on the optimal throughput in delivering aggregated data from all the nodes to the sink. To minimize the maximum delay subject to a given throughput bound, we also design an (α, β)-bicriteria approximation algorithm to construct a Bounded-Degree Minimum-Radius Spanning Tree, with the radius of the tree at most β times the minimum possible radius for a given degree bound Δ*, and the degree of any node at most Δ*+ α , where α and β are positive constants. Lastly, we evaluate the efficiency of our algorithms on different types of spanning trees and show that multichannel scheduling, combined with optimal routing topologies, can achieve the best of both worlds in terms of maximizing the aggregated data collection rate and minimizing the maximum packet delay.

Reducing the energy consumption of cellular wireless access networks is not only beneficial for the global environment but also makes commercial sense for telecommunication operators. Since access networks are designed to support peak time traffic, the utilization of base stations can be very inefficient during off-peak time because the traffic profile is time varying. We study the dynamic switching of base stations (BS) to reduce the energy consumption considering the time varying characteristic of the traffic profile. We show via analysis that the mean and variance of traffic profile and the BS density are the dominant factors that determine the amount of energy saving that can be achieved. Simulations using ideal and real traffic profiles are used to quantify the potential savings from dynamic BS switching in a realistic setting.

Current data collection protocols for wireless sensor networks are mostly based on quasi-static minimum-cost routing trees. We consider an alternative, highly-agile approach called backpressure routing, in which routing and forwarding decisions are made on a per-packet basis. Although there is a considerable theoretical literature on backpressure routing, it has not been implemented on practical systems to date due to concerns about packet looping, the effect of link losses, large packet delays, and scalability. Addressing these concerns, we present the Backpressure Collection Protocol (BCP) for sensor networks, the first ever implementation of dynamic backpressure routing in wireless networks. In particular, we demonstrate for the first time that replacing the traditional FIFO queue service in backpressure routing with LIFO queues reduces the average end-to-end packet delays for delivered packets drastically (75% under high load, 98% under low load). Further, we improve backpressure scalability by introducing a new concept of floating queues into the backpressure framework. Under static network settings, BCP shows a more than 60% improvement in max-min rate over the state of the art Collection Tree Protocol (CTP). We also empirically demonstrate the superior delivery performance of BCP in highly dynamic network settings, including conditions of extreme external interference and highly mobile sinks.

Mobile device based human-centric sensing and user state recognition provide rich contextual information for various mobile applications and services. However, continuously capturing this contextual information consumes significant amount of energy and drains mobile device battery quickly. In this paper, we propose a computationally efficient algorithm to obtain the optimal sensor sampling policy under the assumption that the user state transition is Markovian. This Markov-optimal policy minimizes user state estimation error while satisfying a given energy consumption budget. We first compare the Markov-optimal policy with uniform periodic sensing for Markovian user state transitions and show that the improvements obtained depend upon the underlying state transition probabilities. We then apply the algorithm to two different sets of real experimental traces pertaining to user motion change and inter-user contacts and show that the Markov-optimal policy leads to an approximately 20% improvement over the naive uniform sensing policy.

This paper explores metrics that capture to what degree packet reception on different links is correlated. Specifically, it explores metrics that shed light on when and why opportunistic routing and network coding protocols perform well (or badly). It presents a new metric, κ that, unlike existing widely used metrics, has no bias based on the packet reception ratios of links. This lack of bias makes κ a better predictor of performance of opportunistic routing and network coding protocols. Comparing Deluge and Rateless Deluge, Deluge's network coding counterpart, we find that κ can predict which of the two is best suited for a given environment. For example, irrespective of the packet reception ratios of the links, if the average κ of the link pairs is very high (close to 1.0), then using a protocol that does not code works better than using a network coding protocol. Measuring κ on several 802.15.4 and 802.11 testbeds, we find that it varies significantly across network topologies and link layers. κ can be a metric for quantifying what kind of a network is present and help decide which protocols to use for that network.

We consider a number of related problem formulations pertaining to adaptive subcarrier allocation in multiuser Orthogonal Frequency-Division Multiplexing (OFDM) systems, and prove that they are NP-hard. Thus there exist no known algorithms that can provide optimal solutions for all instances of these problems in polynomial time. We further prove that these problems are hard to approximate in polynomial time. Finally, we discuss qualitatively the settings under which worst case performance is likely to be observed.

The capabilities of sensor networking devices are increasing at a rapid pace. It is therefore not impractical to assume that future sensing operations will involve real time (inelastic) traffic, such as audio and video surveillance, which have strict bandwidth constraints. This in turn implies that future sensor networks will have to cater for a mix of elastic (having no bandwidth constraint requirements) and inelastic traffic. Current state of the art rate control protocols for wireless sensor networks, are however designed with focus on elastic traffic. In this work, by adapting a recently developed theory of utilityproportional rate control for wired networks to a wireless setting, and combining it with a stochastic optimization framework that results in an elegant queue backpressure-based algorithm, we have designed the first-ever rate control protocol that can efficiently handle a mix of elastic and inelastic traffic in a wireless sensor network. We implement this novel protocol in a real world sensor network stack, the TinyOS-2.x communication stack for IEEE 802.15.4 radios and evaluate the real-world performance of this protocol through comprehensive experiments on 20 and 40-node subnetworks of USC's 94-node Tutornet wireless sensor network testbed.

We consider a problem where two selfish cognitive radio users try to share two channels on which they each have potentially different valuations. We first formulate the problem as a non-cooperative simultaneous game, and identify its equilibria. For cases where the resulting Nash equilibria are not efficient, we then propose a novel coordinated channel access mechanism that can be implemented with low overhead in a decentralized fashion. This mechanism, based on the Nash bargaining solution, guarantees full utilization of the spectrum resources while improving the utility of each user compared to the non-cooperative setting. We quantify the resulting gains. Finally, we prove that risk-averse users that are willing to accept offered information at face value have no incentive to lie to each other about their valuations for the non-cooperative game. However, we find that truthfulness is not guaranteed in the bargaining process, suggesting as an open problem the design of an incentive compatible mechanism for bargaining.

Physical layer cooperation can be a powerful tool for enhancing the performance of multi-hop wireless networks. In this paper, we analyze the time to complete a cooperative broadcast to flood some information from one node to all nodes in a wireless network. We show that with cooperation the total time to complete the broadcast grows only logarithmically with the network diameter (unlike in traditional systems where time to flood increases linearly with the diameter). Simulation results validate the analysis, and show that the improvements in flooding time are more pronounced for higher density networks. We further compare the energy costs of cooperative and traditional flooding, and show that the improvements in flooding time with cooperation do not come at the expense of higher energy costs. These results, albeit based on an idealized form of cooperation, provide a strong motivation to develop and test practical schemes for cooperative flooding in multi-hop wireless networks.

Fast and periodic collection of aggregated data is of considerable interest for mission-critical and continuous monitoring applications in sensor networks. In the many-to-one communication paradigm known as convergecast, we consider scenarios where data packets are aggregated at each hop en route to a sink node along a tree-based routing topology and focus on maximizing the data collection rate at the sink by employing TDMA scheduling and multiple frequency channels. Our key result in the paper lies in proving that minimizing the schedule length for an arbitrary network in the presence of multiple frequencies is NP-hard, and in designing approximation algorithms with worst-case provable performance guarantees for geometric networks. In particular, we design a constant factor approximation for networks modeled as unit disk graphs (UDG) where every node has a uniform transmission range, and a O(Delta(T)log n) approximation for general disk graphs where nodes have different transmission ranges; n is the number of nodes in the network and Delta(T) is the maximum node degree on a given routing tree T. We also prove that a constant factor approximation is achievable on UDG even for unknown routing topologies so long as the maximum node degree in the tree is bounded by a constant. We also show that finding the minimum number of frequencies required to remove all the interfering links in an arbitrary network in NP-hard. We give an upper bound on the maximum number of such frequencies required and propose a polynomial time algorithm that minimizes the schedule length under this scenario. Finally, we evaluate our algorithms through simulations and show various trends in performance for different network parameters.

Urban sensing, participatory sensing, and user activity recognition can provide rich contextual information for mobile applications such as social networking and location-based services. However, continuously capturing this contextual information on mobile devices consumes huge amount of energy. In this paper, we present a novel design framework for an Energy Efficient Mobile Sensing System (EEMSS). EEMSS uses hierarchical sensor management strategy to recognize user states as well as to detect state transitions. By powering only a minimum set of sensors and using appropriate sensor duty cycles EEMSS significantly improves device battery life. We present the design, implementation, and evaluation of EEMSS that automatically recognizes a set of users' daily activities in real time using sensors on an off-the-shelf high-end smart phone. Evaluation of EEMSS with 10 users over one week shows that our approach increases the device battery life by more than 75% while maintaining both high accuracy and low latency in identifying transitions between end-user activities.

The state of the art congestion control algorithms for wireless sensor networks respond to coarse-grained feedback regarding available capacity in the network with an additive increase multiplicative decrease mechanism to set source rates. Providing precise feedback is challenging in wireless networks because link capacities vary with traffic on interfering links. We address this challenge by applying a receiver capacity model that associates capacities with nodes instead of links, and use it to develop and implement the first explicit and precise distributed rate-based congestion control protocol for wireless sensor networks --- the wireless rate control protocol (WRCP). Apart from congestion control, WRCP has been designed to achieve lexicographic max-min fairness. Through extensive experimental evaluation on the USC Tutornet wireless sensor network testbed, we show that WRCP offers substantial improvements over the state of the art in flow completion times as well as in end-to-end packet delays.

The receiver capacity model is a simple model to capture flow dynamics in a multi-hop wireless network, by presenting linear constraints to define the feasible rate region of the network, taking into account interference. The model associates with each receiver in the network a notion of constant receiver capacity. Receiver capacity is defined as the maximum possible sum rate of all flows that the receiver can send, receive, and overhear. As has been shown in prior work by the authors, the linear constraints presented by this model make it particularly useful in approximating the true rate region, and designing distributed protocols for multi-hop wireless networks. It is well known that if we use only local constraints to define the rate region, the constraints have to be bounded by some fraction of the interference free link rate, in order to ensure that the rate satisfying these constraints can be feasibly scheduled in any graph. The key challenge in using this model is therefore to estimate the fraction of the link rate that the receiver capacity should be set to, in order to present a feasible rate vector. In this work we answer this question from a theoretical standpoint, and show that as long as the receiver capacity is set to1/3the interference free link rate, all rate vectors that satisfy the constraints of the receiver capacity model can be feasibly scheduled.

We analyze the single and multihop performance of time synchronization mechanisms for challenging environments characterized by high propagation delays, low duty-cycle operation, and imprecise clocks, such as underwater acoustic sensor networks. We find that receiver-receiver-based schemes are unsuitable for such environments, and therefore focus primarily on sender-receiver schemes. According to our analysis, a one-way dissemination approach provides good clock skew estimation but poor offset estimation while a two-way exchange approach provides accurate offset estimation but imprecise clock skew estimation. In average, using one-way scheme can result in significant cumulative propagation error over multiple hops, and using two-way can lead to high variance of propagation error. We develop and analyze a hybrid one-way dissemination/two-way exchange technique, and verify the performance of our hybrid scheme through trace-based experiments. The results suggest that this hybrid approach can provide bounded average error propagation in multihop settings and significantly lower variance of propagation error.

This paper considers opportunistic communication over multiple channels where the state (ldquogoodrdquo or ldquobadrdquo) of each channel evolves as independent and identically distributed (i.i.d.) Markov processes. A user, with limited channel sensing capability, chooses one channel to sense and decides whether to use the channel (based on the sensing result) in each time slot. A reward is obtained whenever the user senses and accesses a ldquogoodrdquo channel. The objective is to design a channel selection policy that maximizes the expected total (discounted or average) reward accrued over a finite or infinite horizon. This problem can be cast as a partially observed Markov decision process (POMDP) or a restless multiarmed bandit process, to which optimal solutions are often intractable. This paper shows that a myopic policy that maximizes the immediate one-step reward is optimal when the state transitions are positively correlated over time. When the state transitions are negatively correlated, we show that the same policy is optimal when the number of channels is limited to two or three, while presenting a counterexample for the case of four channels. This result finds applications in opportunistic transmission scheduling in a fading environment, cognitive radio networks for spectrum overlay, and resource-constrained jamming and antijamming.

Neighbor-Every-Theta (NET) graphs are such that each node has at least one neighbor in every theta angle sector of its communication range. We show that for thetas < pi, NET graphs are guaranteed to have an edge-connectivity of at least floor (2pi)/thetas, even with an irregular communication range. Our main contribution is to show how this family of graphs can achieve tunable topology control based on a single parameter thetas. Since the required condition is purely local and geometric, it allows for distributed topology control. For a static network scenario, a power control algorithm based on the NET condition is developed for obtaining k-connected topologies and shown to be significantly efficient compared to existing schemes. In controlled deployment of a mobile network, control over positions of nodes can be leveraged for constructing NET graphs with desired levels of network connectivity and sensing coverage. To establish this, we develop a potential fields based distributed controller and present simulation results for a large network of robots. Lastly, we extend NET graphs to 3D and provide an efficient algorithm to check for the NET condition at each node. This algorithm can be used for implementing generic topology control algorithms in 3D.

We propose the development of a broad range of exciting mobile interaction games using intermittently-connected wireless devices such as motes. As a concrete application, we describe the implementation of a random walk game, in which players each attempt to hold on to an otherwise itinerant token for as long as possible by running to evade other players in an open field. Besides obtaining the clear entertainment value, we argue that quantifying and analyzing key performance metrics recorded during the game can not only help people to evaluate player ability, but also provide some insights into adversarial behavior in both human and robotic settings. To this end, we present preliminary quantitative results and analysis for the random walk game obtained through real play evaluation.

We consider opportunistic communications over multiple channels where the state ("good" or "bad") of each channel evolves as independent and identically distributed Markov processes. A user, with limited sensing and access capability, chooses one channel to sense and subsequently access (based on the sensed channel state) in each time slot. A reward is obtained when the user senses and accesses a "good" channel. The objective is to design the optimal channel selection policy that maximizes the expected reward accrued over time. This problem can be generally formulated as a Partially Observable Markov Decision Process (POMDP) or a restless multi-armed bandit process, to which optimal solutions are often intractable. We show in this paper that the myopic policy, with a simple and robust structure, achieves optimality under certain conditions. This result finds applications in opportunistic communications in fading environment, cognitive radio networks for spectrum overlay, and resource-constrained jamming and anti-jamming.

A new generation of community-based social networking mobile applications is emerging. In these applications, there is often a fundamental tension between users' desire for preserving the privacy of their own data and their need for fine-grained information about others. Our work is motivated by a community-based mobile application called Aegis, a personal safety enhancement service based on sharing location information with trusted nearby friends. We model the privacy-participation tradeoffs in this application using a game theoretic formulation. Users in this game are assumed to be self-interested. They prefer to obtain more fine-grained knowledge from others while limiting their own privacy leak (i.e. their own contributions to the game) as much as possible. We design a tit-for-tat mechanism to give user incentives to contribute to the application. We investigate the convergence of two best response dynamics to achieve a non-trivial Nash equilibrium for this game. Further, we propose an algorithm that yields a Pareto optimal Nash equilibrium. We show that this algorithm guarantees polynomial time convergence and can be executed in a distributed manner.

What is the fastest rate at which we can collect a stream of aggregated data from a set of wireless sensors organized as a tree? We explore a hierarchy of techniques using realistic simulation models to address this question. We begin by considering TDMA scheduling on a single channel, reducing the original problem to minimizing the number of time slots needed to schedule each link of the aggregation tree. The second technique is to combine the scheduling with transmission power control to reduce the effects of interference. To better cope with interference, we then study the impact of utilizing multiple frequency channels by introducing a simple receiver-based frequency and time scheduling approach. We find that for networks of about a hundred nodes, the use of multi-frequency scheduling can suffice to eliminate most of the interference. The data collection rate then becomes limited not by interference, but by the maximum degree of the routing tree. Therefore we consider finally how the data collection rate can be further enhanced by the use of degree-constrained routing trees. Considering deployments at different densities, we show that these enhancements can improve the streaming aggregated data collection by as much as 10 times compared to the baseline of single-channel data collection over non-degree constrained routing trees. Addition to our primary conclusion, in the frequency scheduling domain we evaluate the impact of different interference models on the scheduling performance and give topology-specific bounds on time slot and frequency channel requirements.

We introduce a novel sequence-based localization technique for wireless sensor networks. We show that the localization space can be divided into distinct regions that can each be uniquely identified by sequences that represent the ranking of distances from the reference nodes to that region. Fornreference nodes in the localization space, combinatorially,O(n") sequences are possible, but we show that, due to geometric constraints, the actual number of feasible location sequences is much lower: onlyO(n4). Using these location sequences, we develop a localization technique that is robust to random errors due to the multipath and shadowing effects of wireless channels. Through extensive systematic simulations and a representative set of real mote experiments, we show that our lightweight localization technique provides comparable or better accuracy than other state-of-the-art radio signal strength-based localization techniques over a range of wireless channel and node deployment conditions.

The efficacy of data aggregation in sensor networks is a function of the degree of spatial correlation in the sensed phenomenon. The recent literature has examined a variety of schemes that achieve greater data aggregation by routing data with regard to the underlying spatial correlation. A well known conclusion from these papers is that the nature of optimal routing with compression depends on the correlation level. In this article we show the existence of a simple, practical, and static correlation-unaware clustering scheme that satisfies a min-max near-optimality condition. The implication for system design is that a static correlation-unaware scheme can perform as well as sophisticated adaptive schemes for joint routing and compression.

Recent experimental studies have shown that wireless links in real sensor networks can be extremely unreliable, deviating to a large extent from the idealized perfect-reception-within-range models used in common network simulation tools. Previously proposed geographic routing protocols commonly employ a maximum-distance greedy forwarding technique that works well in ideal conditions. However, such a forwarding technique performs poorly in realistic conditions as it tends to forward packets on lossy links. Based on a recently developed link loss model, we study the performance of a wide array of forwarding strategies, via analysis, extensive simulations and a set of experiments on motes. We find that the product of the packet reception rate and the distance improvement towards destination ( PRR × d ) is a highly suitable metric for geographic forwarding in realistic environments.

We study the problem of constructing a data gathering tree over a wireless sensor network in order to minimize the total energy for compressing and transporting information from a set of source nodes to the sink. This problem is crucial for advanced computationally intensive applications, where traditional "maximum" in-network compression may result in significant computation energy. We investigate a tunable data compression technique that enables effective trade-offs between the computation and communication costs. We derive the optimal compression strategy for a given data gathering tree and then investigate the performance of different tree structures for networks deployed on a grid topology, as well as general graphs. Our analytical results pertaining to the grid topology and simulation results pertaining to the general graphs indicate that the performance of a simple greedy approximation to the Minimal Steiner Tree (MST) provides a constant-factor approximation for the grid topology and good average performance on the general graphs. Although, theoretically, a more complicated randomized algorithm offers a polylogarithmic performance bound, the simple greedy approximation of MST is attractive for practical implementation.

We consider a multi-channel opportunistic communication system where the states of these channels evolve as independent and statistically identical Markov chains (the Gilbert- Elliot channel model). A user chooses one channel to sense and access in each slot and collects a reward determined by the state of the chosen channel. The problem is to design a sensing policy for channel selection to maximize the average reward, which can be formulated as a multi-arm restless bandit process. In this paper, we study the structure, optimality, and performance of the myopic sensing policy. We show that the myopic sensing policy has a simple robust structure that reduces channel selection to a round-robin procedure and obviates the need for knowing the channel transition probabilities. The optimality of this simple policy is established for the two-channel case and conjectured for the general case based on numerical results. The performance of the myopic sensing policy is analyzed, which, based on the optimality of myopic sensing, characterizes the maximum throughput of a multi-channel opportunistic communication system and its scaling behavior with respect to the number of channels. These results apply to cognitive radio networks, opportunistic transmission in fading environments, downlink scheduling in centralized networks, and resource-constrained jamming and anti-jamming.

The optimal deployment of sinks in a sensor region for power efficient data gathering of a physical phenomenon is investigated in this work. In the system of consideration, nodes perform lossless distributed coding of the sensed data and the spatial statistics of the monitored phenomenon are possibly nonstationary due to heterogeneity in the sensing environment (e.g. variations in the altimetric profile). Non-stationary spatial statistics lead to uneven spatial profiles of the bit rates, unlike stationary statistics. The properties of rate profiles and the consequent optimal sink locations for a broad class of spatially non-stationary covariance models are studied by mathematical analysis and numerical examples.

We consider opportunistic spectrum access for secondary users over multiple channels whose occupancy by primary users is modeled as discrete-time Markov processes. Due to hardware limitations and energy constraints, a secondary user can choose, in each slot, one channel to sense and decide whether to access based on the sensing outcome. The design of sensing strategies that govern channel selections in each slot for optimal throughput performance of the secondary user can be formulated as a partially observable Markov decision process (POMDP). We exploit the structure of this problem when channels are independently and identically distributed. We reveal that the myopic sensing policy has a simple structure: channel selection is reduced to a counting process with little complexity. Further, for the two-channel case, we prove that the myopic sensing policy is in fact the optimal policy. Numerical results have also demonstrated the optimality of the myopic sensing policy when there are more than two channels.

Experimental studies have demonstrated that the behavior of real links in low-power wireless networks (such as wireless sensor networks) deviates to a large extent from the ideal binary model used in several simulation studies. In particular, there is a large transitional region in wireless link quality that is characterized by significant levels of unreliability and asymmetry, significantly impacting the performance of higher-layer protocols. We provide a comprehensive analysis of the root causes of unreliability and asymmetry. In particular, we derive expressions for the distribution, expectation, and variance of the packet reception rate as a function of distance, as well as for the location and extent of the transitional region. These expressions incorporate important environmental and radio parameters such as the path loss exponent and shadowing variance of the channel, and the modulation, encoding, and hardware variance of the radios.

Abstract A specific characteristic of sensor network applications is that the major traffic consists of data collection from various sensor source nodes to a sink via a unidirectional tree. In this paper, we propose DMAC, an energy efficient and low latency MAC that is designed and optimized for such data gathering trees in wireless sensor networks. We first show that previously proposed MAC protocols for sensor networks that utilize activation/sleep duty cycles suffer from a data forwarding interruption problem, whereby not all nodes on a multihop path to the sink can be notified of data delivery in progress, resulting in significant sleep delay. DMAC is designed to solve the interruption problem, by giving the active/sleep schedule of a node an offset that depends upon its depth on the tree. This scheme allows continuous packet forwarding because all nodes on the multihop path can be notified of the data delivery in progress. DMAC also adjusts node duty cycles adaptively according to the traffic load in the network by varying the number of active slots in an schedule interval. We further propose a data prediction mechanism and the use of more to send (MTS) packets in order to alleviate problems pertaining to channel contention and collisions. Our simulation results as well as experimental results with the Mote platform show that by exploiting the application‐specific structure of data gathering trees in sensor networks, DMAC provides significant energy savings and latency reduction while ensuring high data reliability. Copyright © 2007 John Wiley & Sons, Ltd.

We address the problem of energy consumption reduction for wireless sensor networks, where each of the sensors has limited power and acquires data that should be transmitted to a central node. The final goal is to have a reconstructed version of the data measurements at the central node, with the sensors spending as little energy as possible, for a given data reconstruction accuracy. In our scenario, sensors in the network have a choice of different coding schemes to achieve varying levels of compression. The compression algorithms considered are based on the lifting factorization of the wavelet transform, and exploit the natural data flow in the network to aggregate data by computing partial wavelet coefficients that are refined as data flows towards the central node. The proposed algorithm operates by first selecting a routing strategy through the network. Then, for each route, an optimal combination of data representation algorithms i.e. assignment at each node, is selected. A simple heuristic is used to determine the data representation technique to use once path merges are taken into consideration. We demonstrate that by optimizing the coding algorithm selection the overall energy consumption can be significantly reduced when compared to the case when data is just quantized and forwarded to the central node. Moreover, the proposed algorithm provides a tool to compare different routing techniques and identify those that are most efficient overall, for given node locations. We evaluate the algorithm using both a second-order autoregressive (AR) model and empirical data from a real wireless sensor network deployment.

We use a constrained optimization framework to derive fundamental scaling laws for both unstructured sensor networks (which use blind sequential search for querying) and structured sensor networks (which use efficient hash-based querying). We find that the scalability of a sensor network's performance depends upon whether or not the increase in energy and storage resources with more nodes is outweighed by the concomitant application-specific increase in event and query loads. Let m be the number of events sensed by a network over a finite period of deployment, q the number of queries for each event, and N the size of the network. Our key finding is that q1/2•m must be O(N1/4)for unstructured net-works, and q2/3•m must be O(N1/2)for structured networks, to ensure scalable network performance. These conditions determine (i) whether or not the energy requirement per node grows without bound with the network size for a fixed-duration deployment, (ii) whether or not there exists a maximum network size that can be operated for a specified duration on a fixed energy budget, and (iii) whether the network lifetime increases or decreases with the size of the network for a fixed energy budget. We discuss the practical implications of these results for the design of hierarchical two-tier wireless sensor networks.

In recent years random-walk-based algorithms have been proposed for a variety of networking tasks. These proposals include searching, routing, self-stabilization, and query processing in wireless networks, peer-to-peer networks and other distributed systems. This approach is gaining popularity because random walks present locality, simplicity, low-overhead and inherent robustness to structural changes. In this work we propose and investigate an enhanced algorithm that we refer to as random walks with choice. In this algorithm, instead of selecting just one neighbor at each step, the walk moves to the next node after examining a small number of neighbors sampled at random. Our empirical results on random geometric graphs, the model best suited for wireless networks, suggest a significant improvement in important metrics such as the cover time and load-balancing properties of random walks. We also systematically investigate random walks with choice on networks with a square grid topology. For this case, our simulations indicate that there is an unbounded improvement in cover time even with a choice of only two neighbors. We also observe a large reduction in the variance of the cover time, and a significant improvement in visit load balancing.

The scalability of a wireless sensor network has been of interest and importance. We use a constrained optimization framework to derive fundamental scaling laws for both unstructured sensor networks (which use blind sequential search for querying) and structured sensor networks (which use efficient hash-based querying). We find that the scalability of a sensor network's performance depends upon whether or not the increase in energy and storage resources with more nodes is outweighed by the concomitant application-specific increase in event and query loads. We have figured out the theoretical scaling laws for the networks of 2 dimensional deployment in our previous work [2]. We report on our work-in-progress aimed at extending the scaling laws to networks of various dimensional deployment. As a recent achievement, we find that m⋅q1/2 must be O(N d?1/2d) for unstructured networks, and m⋅q d/d+1 must be O(N d?1/d) for structured networks, to ensure scalable network performance, where m is the number of events sensed by a network over a finite period of deployment, q is the number of queries for each event, d is the dimension of deployment, and N is the size of the network. These conditions determine (i) whether or not the energy requirement per node grows without bound with the network size for a fixed-duration deployment, (ii) whether or not there exists a maximum network size that can be operated for a specified duration on a fixed energy budget, and (iii) whether the network lifetime increases or decreases with the size of the network for a fixed energy budget. An interesting finding of this extension is that 3D uniform deployments are inherently more scalable than 2D uniform deployments, which in turn are more scalable than 1D uniform deployments.

We undertake a systematic experimental study of the effects of concurrent packet transmissions in low-power wireless networks. Our measurements, conducted with Mica2 motes equipped with CC1000 radios, confirm that guaranteeing successful packet reception with high probability in the presence of concurrent transmissions requires that the signal-to-interference-plus-noise-ratio (SINR) exceed a critical threshold. However, we find a significant variation of about 6 dB in the threshold for groups of radios operating at different transmission powers. We find that it is harder to estimate the level of interference in the presence of multiple interferers. We also find that the measured SINR threshold generally increases with the number of interferers. Our study offers a better understanding of concurrent transmissions and suggests richer interference models and useful guidelines to improve the design and analysis of higher layer protocols.

We consider the problem of optimizing the number of replicas for event information in wireless sensor networks, when queries are disseminated using expanding rings. We obtain closed-form approximations for the expected energy costs of search, as well as replication. Using these expressions we derive the replication strategies that minimize the expected total energy cost consisting of search and replication costs, both with and without storage constraints. In both cases, we find that events should be replicated with a frequency that is proportional to the square root of their query rates. We validate our analysis and optimization through a set of realistic simulations that incorporate non-idealities including deployment boundary effects and lossy wireless links.

This paper studies the challenging problem of energy minimization for data gathering over a multiple-sources single-sink communication substrate in wireless sensor networks by exploring the energy-latency tradeoffs using rate adaptation techniques. We consider a real-time scenario for mission-critical applications, where the data gathering must be performed within a specified latency constraint. We first propose an offline numerical optimization algorithm with performance analysis for a special case with a complete binary data gathering tree. Then, by discretizing the transmission time, we present a simple, distributed on-line protocol that relies only on the local information available at each sensor node. Extensive simulations were conducted for both long and short-range communication scenarios using two different source placement models. We used the baseline of transmitting all packets at the highest speed and shutting down the radios afterwards. Our simulation results show that compared with this baseline, up to 90% energy savings can be achieved by our techniques (both off-line and on-line), under different settings of several key system parameters

Medium access techniques for wireless sensor networks raise the important question of providing periodic energy-efficient radio sleep cycles while minimizing the end-to-end communication delays. This study aims to minimize the communication latency given that each sensor has a duty cycling requirement of being awake for only 1/k time slots on an average. As a first step we consider the single wake-up schedule case, where each sensor can choose exactly one of the k slots to wake up. We formulate a novel graph-theoretical abstraction of this problem in the general setting of a low-traffic wireless sensor network with arbitrary communication flows and prove that minimizing the end-to-end communication delays is in general NP-hard. However, we are able to derive and analyze optimal solutions for two special cases: tree topologies and ring topologies. Several heuristics for arbitrary topologies are proposed and evaluated by simulations. Our simulations suggest that distributed heuristics may perform poorly because of the global nature of the constraints involved. We also show that by carefully choosing multiple wake-up slots for each sensor significant delay savings can be obtained over the single wake-up schedule case while maintaining the same duty cycling. Using this technique, we propose algorithms that offer a desirable bound of d+O(k) on the delay for specialized topologies like the tree and grid and a weaker guarantee of O((d+k)log n) for arbitrary graphs, where d is the shortest path between 2 nodes in the underlying topology and n is the total number of nodes.

In this paper we present a novel sequence-based RF localization algorithm called Ecolocation. Our algorithm determines the location of unknown nodes by examining the ordered sequence of received signal strength (RSS) measurements taken at multiple reference nodes. We employ a constraint-based approach that provides for robust location decoding even in the presence of random RSS fluctuations due to multi-path fading and shadowing. Through extensive systematic simulations, and a representative set of real mote experiments, we show that over a wide range of settings Ecolocation performs better than other state of the art approaches in terms of localization accuracy and precision.

This study investigates alternative continuous media replication techniques and their impact on content availability in a mobile car-to-car peer-to-peer (C2P2) network of devices. Using aggregate availability latency as a metric, we compare a simple random replication mechanism with a family of techniques that compute the degree of replication for each title based on its popularity, i.e., frequency of access. We use a simulation study along with some supporting analytical analysis for this comparison. Obtained results demonstrate the following key lesson. When total storage capacity of the network is significantly larger than the clip repository size, a random replication technique is sufficient. Otherwise, there is a large parameter space where the frequency-based replication schemes provide superior performance.

Abstract — We investigate the combination of distributed ge-ographic routing with transmission power control for energy efficient delivery of information in multihop wireless networks. Using realistic models for wireless channel fading as well as radio modulation and encoding, we first show that the optimal power control strategy over a given link should set the transmission power to achieve a special signal-to-noise ratio (SNR) constant that can be computed using an elegant characteristic equation. Counter-intuitively, for typical radios, this corresponds to an optimal operating point of SNR that lies in the transitional region (where packet error rates are non-negligible). We then propose a local power efficiency metric for distributed routing such that at each step the transmitter picks as the next hop the neighbor for which this metric is maximized. Through extensive simulations, we compare the performance of the proposed algorithm and globally optimal routing algorithms. We show that in randomly deployed 2-D networks, the combination of this local metric for routing with optimal power control has close performances, in terms of average power consumption under different node density settings and physical transmission power limits, to the best strategy using global network link state information. In particular, when electronic power is relatively low, the proposed algorithm can provide up to six times reduction in power usage compared to channel-unaware routing algorithms. I.

Abstract — We investigate the problem of energy efficiency in TDMA link scheduling with transmission power control using a realistic SINR-based interference model, given packets of a set of links to be transmitted within a latency bound. First we formulate a fundamental optimization problem (TJSPC) that provides tunable tradeoffs between energy, throughput and latency through a single parameter β. We present both exponential and polynomial complexity solutions to this problem and evaluate their performance. Our results show that for moderate traffic loads, with appropriate tuning of parameters, major energy savings can be obtained without significantly sacrificing throughput. We then investigate the scheduling and power control problem with the objective of minimizing the total transmission energy cost under the constraint that all transmission requests are satisfied (JSPC-TR). We present an iterative approach to solve JSPC-TR that leverages the heuristics for TJSPC and converges rapidly to the setting of β which achieves energy efficiency while guaranteeing data delivery. I.

We examine the problem of maximizing data collection from an energy-limited store-and-extract wireless sensor network, which is analogous to the maximum lifetime problem of interest in continuous data-gathering sensor networks. One significant difference is that this problem requires attention to "data-awareness" in addition to "energy-awareness." We formulate the maximum data extraction problem as a linear program and present a 1+omega iterative approximation algorithm for it. As a practical distributed implementation we develop a faster greedy heuristic for this problem that uses an exponential metric based on the approximation algorithm. We then show through simulation results that the greedy heuristic incorporating this exponential metric performs near-optimally (within 1 to 20% of optimal, with low overhead) and significantly better than other shortest-path routing approaches, particularly when nodes are heterogeneous in their energy and data availability

We study the problem of scheduling packet transmissions for data gathering in wireless sensor networks. The focus is to explore the energy-latency tradeoffs in wireless communication using techniques such as modulation scaling. The data aggregation tree - a multiple-source single-sink communication paradigm - is employed for abstracting the packet flow. We consider a real-time scenario where the data gathering must be performed within a specified latency constraint. We present algorithms to minimize the overall energy dissipation of the sensor nodes in the aggregation tree subject to the latency constraint. For the off-line problem, we propose (a) a numerical algorithm for the optimal solution, and (h) a pseudo-polynomial time approximation algorithm based on dynamic programming. We also discuss techniques for handling interference among the sensor nodes. Simulations have been conducted for both long-range communication and short-range communication. The simulation results show that compared with the classic shutdown technique, between 20% to 90% energy savings can be achieved by our techniques, under different settings of several key system parameters. We also develop an on-line distributed protocol that relies only on the local information available at each sensor node within the aggregation tree. Simulation results show that between 15% to 90% energy conservation can be achieved by the on-line protocol. The adaptability of the protocol with respect to variations in the packet size and latency constraint is also demonstrated through several run-time scenarios.

Sensor network applications have a diverse set of requirements - some involve extraction of sensor data to a single point, others exploit sensor-to-sensor communication; some employ long-lasting data streams while connections in others are mainly ephemeral. Different variants of the directed diffusion routing protocol - pull-based, push-based and hybrid rendezvous-based - have been developed, along with in-network processing and geographic routing techniques. We mathematically model and analyze the performance of these routing techniques across a range of application scenarios (with varying numbers of nodes, sources, sinks, data settings etc.). Besides quantifying the conditions under which the different routing algorithms outperform each other, we obtain a number of useful design insights. Our analysis shows that algorithms mismatched to applications can result in drastically poor performance; demonstrates the desirability of reducing flooded interest and exploratory messages when data aggregation is used; and suggests that it may be difficult to implement efficient hybrid schemes because their performance is very sensitive to the optimal placement of rendezvous points.

IEEE 802.15.4 is a new standard to address the need for low-rate low-power low-cost wireless networking. We provide in this paper one of the first simulation-based performance evaluations of the new medium access protocol in IEEE 802.15.4, focusing on its beacon-enabled mode for a star-topology network. We describe its key features such as the superframe structure, which allows devices to access channels in a contention access period (CAP) or a collision free period (CFP) and the beacon-based synchronization mechanism. Our performance evaluation study reveals some of the key throughput-energy-delay tradeoffs inherent in this MAC protocol. We provide an analysis comparing the energy costs of beacon tracking and non-tracking modes for synchronization, showing that the optimum choice depends upon the combination of duty cycles and data rates.

When the data rates in sensor networks are comparable to the available channel bandwidth, traditional randomized access schemes face the problem of energy inefficiency and reduced throughput due to increased MAC collisions as well as the problem of unfair data delivery. We argue that under such conditions it is preferable to focus on techniques for scheduled access. We present a linear programming formulation and corresponding distributed TDMA-based scheduling algorithms to provide max-min fair collision-free bandwidth allocation to all sources. We evaluate the performance of the proposed scheduled flow technique using the Tossim/Nido network simulator for the Berkeley Mote/TinyOS platform. Our results show that under high data rate conditions, the proposed scheme significantly outperforms randomized access based schemes in terms of key metrics such as fairness, energy efficiency, throughput, and delay.

Summary form only given. In many sensor network applications the major traffic pattern consists of data collected from several source nodes to a sink through a unidirectional tree. We propose DMAC, an energy efficient and low latency MAC that is designed and optimized for such data gathering trees in wireless sensor networks. We first show that previously proposed MAC protocols for sensor networks that utilize activation/sleep duty cycles suffer from a data forwarding interruption problem, whereby not all nodes on a multihop path to the sink are notified of data delivery in progress, resulting in significant sleep delay. DMAC is designed to solve the interruption problem and allow continuous packet forwarding by giving the sleep schedule of a node an offset that depends upon its depth on the tree. DMAC also adjusts the duty cycles adaptively according to the traffic load in the network. We further propose a data prediction mechanism and the use of more-to-send (MTS) packets in order to alleviate problems pertaining to channel contention and collisions. Our simulation results show that by exploiting the application-specific structure of data gathering trees in sensor networks, DMAC provides significant energy savings and latency reduction while ensuring high data reliability.

We describe a novel method for node localization in a sensor network where there are a fraction of reference nodes with known locations. For application-specific sensor networks, we argue that it makes sense to treat localization through online distributed learning and integrate it with an application task such as target tracking. We propose distributed online algorithm in which sensor nodes use geometric constraints induced by both radio connectivity and sensing to decrease the uncertainty of their position. The sensing constraints, which are caused by a commonly sensed moving target, are usually tighter than connectivity based constraints and lead to a decrease in average localization error over time. Different sensing models, such as radial binary detection and distance-bound estimation, are considered. First, we demonstrate our approach by studying a simple scenario in which a moving beacon broadcasts its own coordinates to the nodes in its vicinity. We then generalize this to the case when instead of a beacon, there is a moving target with a-priori unknown coordinates. The algorithms presented are fully distributed and assume only local information exchange between neighboring nodes. Our results indicate that the proposed method can be used to signicantly enhance the accuracy in position estimation, even when the fraction of reference nodes is small. We compare the efficiency of the distributed algorithms to the case when node positions are estimated using centralized (convex) programming. Finally, simulations using the TinyOS-Nido platform are used to study the performance in more realistic scenarios.

We propose a learning-based approach to efficiently and reliably route data to a mobile sink in a wireless sensor field. Specifically, we consider a mobile sink that does not know when to query or does not need to query. Furthermore, the sink moves in a certain pattern within the sensor field. Such a sink passively listens for incoming data that distant source sensors unilaterally push towards it. Unlike traditional routing mechanisms, our technique takes the time-domain explicitly into account, with each node involved making the decision "at this time what is the best way to forward the packet to the sink?". In the presented scheme, motes (nodes in the vicinity of the sink) learn its movement pattern over time and statistically characterize it as a probability distribution function. Having obtained this information at the motes, our scheme uses reinforcement learning to locate the sink efficiently at any point of time.

While most research on wireless sensor networks have focused on the deployment of large numbers of cheap homogeneous sensor devices, in practical settings, it is often feasible to consider heterogeneous deployments of devices with different capabilities. Under the prescribed cost constraints, we analyze such heterogeneous deployments both mathematically and through simulations, and show how they impact the coverage aging process of a sensor network, i.e., how it degrades over time as some nodes become energy-depleted. We derive expressions for the heterogeneous mixture of devices that optimizes the lifetime sensing coverage in a single-hop direct communication model. We then investigate a multi-hop communication model through simulations, and examine the impact of heterogeneity on lifetime sensing coverage and coverage aging both with and without data aggregation. Our results show that using an optimal mixture of many inexpensive low-capability devices and some expensive high-capability devices can significantly extend the duration of a network's sensing performance.

In this work, we address the problem of estimating parameters of diffusion phenomena via autonomous wireless sensor networks. Diffusion phenomena, such as the propagation of a gas in the air or of a chemical agent in the water, can be modeled by means of partial differential equations (PDE's). In several scenarios, the parameters characterizing such models, i.e. the coefficients of the PDE's, are not known a-priori and need to be estimated. We develop an adaptive approach for the distributed identification of the parameters of diffusion models for both the cases of known and unknown boundary conditions (BCs). The technique also applies to the case of spatially varying parameters. We present simulation results to show the performance and the various trade-offs of the method.

We experimentally investigate the impact of variable transmission power on link quality, and propose variable power link quality control techniques to enhance the performance of data delivery in wireless sensor networks. This study extends the state of the art in two key respects: first, while there are a number of previous results on power control techniques for wireless ad hoc and sensor networks, to our knowledge, nearly all of them have been simulated and analytically studied that assumes the idealized link conditions; second, while there are several recent experimental studies that have shown the prevalence of non-ideal unreliable communication links in sensor networks, the paper has not thoroughly investigated the impact of variable transmission power. We perform a systematic set of experiments to analyze how the transmission power changes affect the quality of low power RF wireless links between nodes. These experiments show how significant variation in link qualities occur in real-world deployments and how these effects strongly influence the effectiveness of transmission power control. We then present a packet-based transmission power control mechanism that incorporates blacklisting to enhance link reliability while minimizing interference. The effectiveness of the proposed scheme is demonstrated via test bed experiments.

The wireless sensor networks community, has now an increased understanding of the need for realistic link layer models. Recent experimental studies have shown that real deployments have a "transitional region" with highly unreliable links, and that therefore the idealized perfect-reception-within-range models used in common network simulation tools can be very misleading. In this paper, we use mathematical techniques from communication theory to model and analyze the low power wireless links. The primary contribution of this work is the identification of the causes of the transitional region, and a quantification of their influence. Specifically, we derive expressions for the packet reception rate as a function of distance, and for the width of the transitional region. These expressions incorporate important channel and radio parameters such as the path loss exponent and shadowing variance of the channel; and the modulation and encoding of the radio. A key finding is that for radios using narrow-band modulation, the transitional region is not an artifact of the radio non-ideality, as it would exist even with perfect-threshold receivers because of multi-path fading. However, we hypothesize that radios with mechanisms to combat multi-path effects, such as spread-spectrum and diversity techniques, can reduce the transitional region.

Recent experimental studies have shown that wireless links in real sensor networks can be extremely unreliable, deviating to a large extent from the idealized perfect-reception-within-range models used in common network simulation tools. Previously proposed geographic routing protocols commonly employ a maximum-distance greedy forwarding technique that works well in ideal conditions. However, such a forwarding technique performs poorly in realistic conditions as it tends to forward packets on lossy links. We identify and illustrate this weak-link problem and the related distance-hop trade-off, whereby energy efficient geographic forwarding must strike a balance between shorter, high-quality links, and longer lossy links. The study is done for scenarios with and without automatic repeat request (ARQ).

In designing, analyzing and monitoring wireless sensor networks (WSN), engineers are interested in global performance metrics such as energy consumption, delivery rate, and delay. Such metrics are often variable and stochastic in nature. In traditional broadband networks the variability is primarily due to traffic variations and bandwidth constraints; in WSN there are additional sources of variability including energy, computation constraints, and most significantly, due to the inherently unreliable nature of wireless links. The goal of our study is to understand how link-layer unreliability impacts global performance metrics.

Random geometric graphs result from taking n uniformly distributed points in the unit cube, [0,1]d, and connecting two points if their Euclidean distance is at most r, for some prescribed r. We show that monotone properties for this class of graphs have sharp thresholds by reducing the problem to bounding the bottleneck matching on two sets of $n$ points distributed uniformly in [0,1]d. We present upper bounds on the threshold width, and show that our bound is sharp for d = 1 and at most a sublogarithmic factor away for d ≥ 2. Interestingly, the threshold width is much sharper for random geometric graphs than for Bernoulli random graphs. Further, a random geometric graph is shown to be a subgraph, with high probability, of another independently drawn random geometric graph with a slightly larger radius; this property is shown to have no analogue for Bernoulli random graphs.

Geographic routing in mobile ad hoc networks has proved to provide drastic performance improvement over strictly address-centric routing schemes. While geographic routing has been shown to be correct and efficient when location information is accurate, its performance in the face of location errors is not well understood. In this paper, we study the effect of inaccurate location information caused by node mobility under a rich set of scenarios and mobility models. We identify two main problems, named LINK and LOOP, that are caused by mobility-induced location errors. Based on the analysis via ns-2 simulations, we propose two mobility prediction schemes - neighbor location prediction (NLP) and destination location prediction (DLP) to mitigate these problems. Simulation results have shown noticeable improvement under all mobility models used in our study. Our schemes achieve up to 27% improvement in packet delivery and 37% reduction in network resource wastage on average without incurring any additional communication or intense computation.

We develop a detailed approach to study how mobility impacts the performance of reactive mobile ad hoc network routing protocols. In particular, we examine how the statistics of path durations including probability density functions vary with the parameters such as the mobility model, relative speed, number of hops, and radio range. We find that at low speeds, certain mobility models may induce multimodal distributions that reflect the characteristics of the spatial map, mobility constraints and the communicating traffic pattern. However, this paper suggests that at moderate and high velocities the exponential distribution with appropriate parameterizations is a good approximation of the path duration distribution for a range of mobility models. Analytically, we show that the reciprocal of the average path duration has a strong linear relationship with the throughput and overhead of dynamic source routing (DSR), which is also confirmed by simulation results. In addition, we show how the mathematical expression obtained for the path duration distribution can also be used to prove that the nonpropagating cache hit ratio in DSR is independent of velocity for the freeway mobility model. These two case studies illustrate how various aspects of protocol performance can be analyzed with respect to a number of significant parameters including the statistics of link and path durations.

The current practice in wireless sensor networks (WSNs) is to develop functional system designs and protocols for information extraction using intuition and heuristics, and validate them through simulations and implementations. We address the need for a complementary formal methodology by developing nonlinear optimization models of static WSN that yield fundamental performance bounds and optimal designs. We present models both for maximizing the total information gathered subject to energy constraints (on sensing, transmission, and reception), and for minimizing the energy usage subject to information constraints. Other constraints in these models correspond to fairness and channel capacity (assuming noise but no interference). We also discuss extensions of these models that can handle data aggregation, interference, and even node mobility. We present results and illustrations from computational experiments using these models that show how the optimal solution varies as a function of the energy/information constraints, network size, fairness constraints, and reception power. We also compare the performance of some simple heuristics with respect to the optimal solutions.

We propose a distributed solution for a canonical task in wireless sensor networks - the binary detection of interesting environmental events. We explicitly take into account the possibility of sensor measurement faults and develop a distributed Bayesian algorithm for detecting and correcting such faults. Theoretical analysis and simulation results show that 85-95 percent of faults can be corrected using this algorithm, even when as many as 10 percent of the nodes are faulty.

Geographic routing has been introduced in mobile ad hoc networks and sensor networks. Under ideal settings, it has been proven to provide drastic performance improvement over strictly address centric routing schemes. While geographic routing has been shown to be correct and efficient when location information is accurate, its performance in the face of location errors is not well understood. We study the effect of inaccurate location information caused by node mobility under a rich set of scenarios and mobility models. We identify two main problems, named LLNK and LOOP, that are caused by mobility-induced location errors. Based on analysis via ns-2 simulations, we propose two mobility prediction schemes - neighbor location prediction (NLP) and destination location prediction (DLP) to mitigate these problems. Simulation results show noticeable improvement under all mobility models used in our study. Under the settings we examine, our schemes achieve up to 27 percent improvement in packet delivery and 37 percent reduction in network resource wastage, on average without incurring any additional communication or intense computation.

This paper investigates a novel streaming architecture consisting of home-to-home online (H2O) devices that collaborate with one another to provide on-demand access to large repositories of continuous media such as audio and video clips. An H2O device is configured with a high bandwidth wireless communication component, a powerful processor, and gigabytes of storage. A key challenge of this environment is how to place data across H2O devices in order to enhance startup latency, defined as the delay observed from when a user requests a clip, to the onset of its display. Our primary contribution is a novel replication technique that enhances startup latency, while minimizing the total storage space required from an environment consisting of N H2O devices. This technique is based on the following intuition: The first few blocks of a clip are required more urgently than its last few blocks, and should be replicated more frequently in order to minimize startup latency. We develop analytical models to quantify the number of replicas required for each block. In addition, we describe two alternative distributed implementation of our replication strategy. When compared with full replication, our technique provides on average greater than 97% (i.e., several orders of magnitude) savings in storage space, while ensuring zero startup latency and a hiccup-free reception.

The basic topology desired in data-gathering wireless sensor networks is a spanning tree, since the traffic is mainly in the form of many-to-one flows. Nodes in the network can self-configure themselves into such a topology by a two-phase process: a flood initiated by the root node, followed by parent selection by all nodes. We present four localized topology generation mechanisms - earliest-first, randomized, nearest-first, and weighted-randomized parent selection. We also compare the network performance of these mechanisms on the basis of the following metrics: node degree, robustness, channel quality, data aggregation and latency; our study shows how localized self-configuration mechanisms can impact the global network behavior.

Wireless sensor networks consisting of large numbers of inexpensive energy-constrained nodes are an area of emerging networking research. Routing algorithms in these networks are required to provide tolerance to temporary or lasting faults in individual devices. The conventional methodology is to set radio transmit powers to the minimum levels required for connectivity and use multipath routing to provide robustness. We show in this paper through an analytical example and detailed simulation results that using a single path routing scheme with higher transmit power can also be an energy-efficient solution for robustness to node failures.

We develop a detailed approach to study how mobility impacts the performance of reactive MANET routing protocols. In particular we examine how the statistics of path durations including PDFs vary with the parameters such as the mobility model, relative speed, number of hops, and radio range. We find that at low speeds, certain mobility models may induce multi-modal distributions that reflect the characteristics of the spatial map, mobility constraints and the communicating traffic pattern. However, our study suggests that at moderate and high velocities the exponential distribution with appropriate parameterizations is a good approximation of the path duration distribution for a range of mobility models. The reciprocal of the average path duration is analytically shown to have a strong linear relationship with the throughput and overhead that is confirmed by the simulation results for DSR.

In this paper, we study the impact of heterogeneous receivers on the throughput of multicast flow control and propose a new multicast flow control algorithm to optimally partition group members into multiple subgroups. Our main contributions are as follows. First, we cast the multicast flow control problem in the Internet as the list partition problem and then prove that the list partition problem is equivalent to the optimal paging problem in cellular networks. The result is not only interesting in itself but also essential to derive the first known analytical bounds for the throughput of multicast flow control. Furthermore, we propose an algorithm to solve not only the list partition problem but also the optimal paging problem and the problem of bulk data transfer using multiple multicast groups. The complexity of our algorithm is one order less than the best known algorithm designed only for the problem of bulk data transfer using multiple multicast groups in the literature. While earlier work uses simulations to justify the usage of multiple subgroups to deliver information to a large amount of receivers in heterogeneous networks, we provide the first analytical support.

There are many contexts in distributed wireless networks where there is a critical threshold, corresponding to a minimum amount of the communication effort or power expenditure by individual nodes, above which a desirable global property exists with high probability. When this individual node effort is below the threshold the desired global property exists with a low probability. This "phase transition" is typically seen to become sharper as the number of nodes in the network increases. We discuss some examples of properties that exhibit such critical behavior: node reachability with probabilistic flooding, ad-hoc network connectivity, and sensor network coordination. We discuss the connections between these phenomena and the phase transitions that have been shown to arise in random graphs. We argue that a good understanding of these phase transition phenomena can provide useful design principles for engineering distributed wireless networks.

We present some results regarding the paging cost gains and the cost-delay tradeoff that can be achieved by using sequential paging to locate mobile users in cellular networks. We describe tight bounds on the average paging cost and the paging delay and quantify the intuition that greater gains are achieved when the mobile user's location probabilities are concentrated in a small portion of the location area. We also examine the impact of errors in the location estimates on the paging cost.