In this paper, we present a ring referral scheme, by which a user can publicly prove her knowledge of a valid signature for a private message that is signed by one of an ad hoc set of authorized issuers, without revealing the signing issuer. Ring referral is a natural extension to traditional ring signature by allowing a prover to obtain a signature from a third-party signer. Our scheme is useful for diverse applications, such as certificate-hiding decentralized identity, privacy-enhancing federated authentication, anonymous endorsement and privacy -preserving referral marketing. In contrast with prior issuer-hiding credential schemes, our ring referral scheme supports more distinguishing features, such as (1) public verifiability over an ad hoc ring, (2) strong user anonymity against collusion among the issuers and verifier to track a user, (3) transparent setup, (4) message hiding, (5) efficient multi-message logarithmic verifiability, (6) threshold scheme for requiring multiple co-signing issuers. Finally, we implemented our ring referral scheme with extensive empirical evaluation.

Traditional Insurance, a popular approach of financial risk management, has suffered from the issues of high operational costs, opaqueness, inefficiency and a lack of trust. Recently, blockchain-enabledparametric insurancethrough authorized data sources (e.g., remote sensing and IoT) aims to overcome these issues by automating the underwriting and claim processes of insurance policies on a blockchain. However, the openness of blockchain platforms raises a concern of user privacy, as the private user data in insurance claims on a blockchain may be exposed to outsiders. In this paper, we propose a privacy-preserving parametric insurance framework based on succinct zero-knowledge proofs (zk-SNARKs), whereby an insuree submits a zero-knowledge proof (without revealing any private data) for the validity of an insurance claim and the authenticity of its data sources to a blockchain for transparent verification. Moreover, we extend the recent zk-SNARKs to support robust privacy protection for multiple heterogeneous data sources and improve its efficiency to cut the incurred gas cost by 80%. As a proof-of-concept, we implemented a working prototype of bushfire parametric insurance on real-world blockchain platform Ethereum, and present extensive empirical evaluations.

Zero-knowledge range proofs play a critical role in confidential transactions (CT) on blockchain systems. They are used to prove the non-negativity of committed transaction payments without disclosing the exact values. Logarithmicsized range proofs with transparent setups, e.g., Bulletproofs, which aim to prove a committed value lies in the range [0, 2 -1] where is the bit length of the range, have gained growing popularity for communication-critical blockchain systems as they increase scalability by allowing a block to accommodate more transactions. In this paper, we propose SwiftRange, a new type of logarithmic-sized zero-knowledge range argument with a transparent setup in the discrete logarithm setting. Our argument can be a drop-in replacement for range proofs in blockchain-based confidential transactions. Compared with Bulletproofs, our argument has higher computational efficiency and lower round complexity while incurring comparable communication overheads for CT-friendly ranges, where N ∈ {32, 64}. Specifically, a single SwiftRange achieves 1.73× and 1.37× proving efficiency with no more than 1.1× communication costs for both ranges, respectively. More importantly, our argument is doubly efficient in verification efficiency. Furthermore, our argument has a smaller size when N ≤ 16, making it competitive for many other communication-critical applications. Our argument supports the aggregation of multiple single arguments for greater efficiency in communication and verification. Finally, we benchmarked our argument against the state-of-the-art range proofs to demonstrate its practicality.

Decentralizing crowdsourcing using blockchain removes the trusted mediator who may cause social biases in data aggregation and uncertainties in ensuring proper rewards to workers. Permissionless blockchain discloses all data on public ledgers, which compromises the privacy and anonymity of workers and induces free-riders. State-of-the-art anonymous crowdsourcing systems enable anonymity through identity registration of workers and a trusted setup for key generation. However, these systems fail to support anonymous payments to workers, which may compromise the identities of workers. In this paper, we incorporate anonymous payments in crowdsourcing and dispense with identity registration and trusted setup to support open anonymous participation from any worker. Our solution is based on the decentralized anonymous payment systems (e.g., Zerocoin), commitment schemes, and efficient non-interactive zero-knowledge proofs.

Unmanned aerial vehicles (UAVs), commonly known as drones, are being increasingly deployed throughout the globe as a means to streamline monitoring, inspection, mapping, and logistic routines. When dispatched on autonomous missions, drones require an intelligent decision-making system for trajectory planning and tour optimization. Given the limited capacity of their onboard batteries, a key design challenge is to ensure the underlying algorithms can efficiently optimize the mission objectives along with recharging operations during long-haul flights. With this in view, the present work undertakes a comprehensive study on automated tour management systems for an energy-constrained drone: (1) We construct a machine learning model that estimates the energy expenditure of typical multi-rotor drones while accounting for real-world aspects and extrinsic meteorological factors. (2) Leveraging this model, the joint program of flight mission planning and recharging optimization is formulated as a multi-criteria Asymmetric Traveling Salesman Problem (ATSP), wherein a drone seeks for the time-optimal energy-feasible tour that visits all the target sites and refuels whenever necessary. (3) We devise an efficient approximation algorithm with provable worst-case performance guarantees and implement it in a drone management system, which supports real-time flight path tracking and re- computation in dynamic environments. (4) The effectiveness and practicality of the proposed approach are validated through extensive numerical simulations as well as real-world experiments. Note to Practitioners—This study is stimulated by the need for developing pragmatic and provably efficient automated tour management systems for UAVs deployed on energy-constrained, long-distance flight missions. As such, UAVs provide a nifty platform for facilitating environmental monitoring, disaster management, transport of medical supplies, as well as expediting last-mile deliveries. However, existing path planners generally fall short of capturing several crucial aspects, such as detailed power consumption model (e.g., factoring in payload, wind speed and direction) or performance guarantees, potentially leading to underutilized or infeasible routing decisions. To address these issues, the present work proposes a theoretically-backed routing approach with a certifiable degree of optimality and develops an effective, practical power consumption evaluation model for multi-rotor UAVs, verified on multiple drone models.

With the development of 5G technology, mobile edge computing is emerging as an enabling technique to reduce the response latency of network services by deploying cloudlets at 5G base stations to form mobile edge cloud (MEC) networks. Network service providers now shift their services from remote clouds to cloudlets of MEC networks in the proximity of users. However, the permanent placement of network services into an MEC network is not economic due to limited computing and bandwidth resources imposed on its cloudlets. A smart way is to cache frequently demanded services from remote clouds to cloudlets of the MEC network. In this paper, we study the problem of service caching in an MEC network under a service market with multiple network service providers competing for both computation and bandwidth resources in terms of Virtual Machines (VMs) in the MEC network. We first propose an Integer Linear Program (ILP) solution and a randomized rounding algorithm, for the problem without VM sharing among different network service providers. We then devise a distributed and stable game-theoretical mechanism for the problem with VM sharing among network service providers, with the aim to minimize the social cost of all network service providers, through introducing a novel cost sharing model and a coalition formation game. We also analyze the performance guarantee of the proposed mechanism, Strong Price of Anarchy (SPoA). We third consider the cost- and delay-sensitive service caching problem with temporal VM sharing, and propose a mechanism with provable SPoA. We finally evaluate the performance through extensive simulations and a real world test-bed implementation. Experimental results demonstrate that the proposed algorithms outperform existing approaches by achieving at least$40\%$lower social cost via service caching and resource sharing among different network service providers.

Cloud computing has been a dominant paradigm for a variety of information processing platforms, particularly for enabling various popular applications of sharing economy. However, there is a major concern regarding data privacy on these cloud-based platforms. This work presents novel cloud-based privacy-preserving solutions to support collaborative consumption applications for sharing economy. In typical collaborative consumption, information processing platforms need to enable fair cost-sharing among multiple users for utilizing certain shared facilities and communal services. Our cloud-based privacy-preserving protocols, based on homomorphic Paillier cryptosystems, can ensure that the cloud-based operator can only obtain an aggregate schedule of all users in facility sharing, or a service schedule conforming to service provision rule in communal service sharing, but is unable to track the personal schedules or demands of individual users. More importantly, the participating users are still able to settle cost-sharing among themselves in a fair manner for the incurred costs, without knowing each other’s private schedules or demands. Our privacy-preserving protocols involve no other third party who may compromise privacy. We also provide an extensive evaluation study and a proof-of-concept system prototype of our protocols.

Data sensing and gathering is an essential task for various information-driven services in smart cities. On the one hand, Internet of Things (IoT) sensors can be deployed at certain fixed locations to capture data reliably but suffer from limited sensing coverage. On the other hand, data can also be gathered dynamically through crowdsensing contributed by voluntary users but suffer from its unreliability and the lack of incentives for users’ contributions. In this article, we explore an integrated paradigm called “ hybrid sensing ” that harnesses both IoT-sensing and crowdsensing in a complementary manner. In hybrid sensing, users are incentivized to provide sensing data not covered by IoT sensors and provide crowdsourced feedback to assist in calibrating IoT-sensing. Their contributions will be rewarded with credits that can be redeemed to retrieve synthesized information from the hybrid system. In this article, we develop a hybrid sensing system that supports explicit user privacy—IoT sensors are obscured physically to prevent capturing private user data, and users interact with a crowdsensing server via a privacy-preserving protocol to preserve their anonymity. A key application of our system is smart parking, by which users can inquire and find the available parking spaces in outdoor parking lots. We implemented our hybrid sensing system for smart parking and conducted extensive empirical evaluations. Finally, our hybrid sensing system can be potentially applied to other information-driven services in smart cities.

Ride-sharing or vehicle-pooling allows commuters to team up spontaneously for transportation cost sharing. This has become a popular trend in the emerging paradigm of sharing economy. One crucial component to support effective ride-sharing is the matching mechanism that pairs up suitable commuters. Traditionally, matching has been performed in a centralized manner, whereby an operator arranges ride-sharing according to a global objective (e.g., total cost of all commuters). However, ride-sharing is a decentralized decision-making paradigm, where commuters are self-interested and only motivated to team up based on individual payments. Particularly, it is not clear how transportation cost should be shared fairly between commuters, and what ramifications of cost-sharing are on decentralized ride-sharing. This paper sheds light on the principles of decentralized ride-sharing and vehicle-pooling mechanisms based on stable matching, such that no one would be better off to deviate from a stable matching outcome. We study various fair cost-sharing mechanisms and the induced stable matching outcomes. We compare the stable matching outcomes with a social optimal outcome (that minimizes total cost) by theoretical bounds of social optimality ratios, and show that several fair cost-sharing mechanisms can achieve high social optimality. We also corroborate our results with an empirical study of taxi sharing under fair cost-sharing mechanisms by a data analysis on New York City taxi trip dataset, and provide useful insights on effective decentralized mechanisms for practical ride-sharing and vehicle-pooling.

The papers in this special section focus on the intersection of computing and communication technologies with energy systems. Computing and communication technologies impact energy systems in two distinct ways. The exponential growth of these technologies has made them large energy consumers. Therefore, new architectures, technologies and systems are being developed and deployed to make computing and networked systems more energy efficient. Additionally, these technologies will play a central role in the ongoing transformation of our energy systems. They help measure, monitor and control energy resources, inform and shape human demand, and determine how utilities, generators, regulators, and consumers interact. Recently, there have been vibrant developments in the research community at the intersection of computing and communication technologies with energy systems. Diverse applications of computing and networked systems have made legacy systems more energy-efficient, as well as improved the design, analysis, and development of innovative new energy systems.

Provisioning reliable network services for mobile users in a mobile edge computing environment is the top priority for most network service providers, as unreliable or severely failed services will result in tremendous loss on their revenues and consumers. In this paper, we study a novel service reliability augmentation problem in a Mobile Edge-Cloud (MEC) network, where mobile users request various network services through issuing requests with service function chain (SFC) requirements and reliability expectations, and an admitted request may not meet its reliability expectation initially. To enhance its service reliability to reach its expectation, it is a common practice to make use of redundant backups, that is to place redundant VNF instances of each Virtual Network Function (VNF) in its SFC in case its primary VNF instance fails. In this paper, we aim to augment the reliability of each admitted request as much as possible with the ultimate objective to reach its reliability expectation, subject to computing capacity on each cloudlet in the network. To this end, we first formulate a novel service reliability augmentation problem. We then deal with the problem for the admitted request under the assumption that all the secondary VNF instances of each primary VNF instance in its SFC must be placed into the cloudlets no more than l hops from the cloudlet of the primary VNF instance, where 1 ≤ l ≤ n − 1 and n is the number of cloudlets in the network, for which we propose an integer linear program (ILP) solution, and develop a randomized algorithm with a provable approximation ratio while a moderate resource constraint violation. We also devise an efficient heuristic algorithm for the problem without any resource constraint violation. We finally evaluate the performance of the proposed algorithms through experimental simulations. Experimental results demonstrate that the proposed algorithms are promising, and their empirical results are superior to their analytical counterparts.

With the development of 5G technology, mobile edge computing is emerging as an enabling technique to promote Quality of Service (QoS) of network services. In particular, the response latency of network services can be significantly reduced by deploying cloudlets at 5G base stations in mobile edge clouds. Network service providers that usually deploy their services in remote clouds now shift their services from the remote clouds to the network edge in the proximity of users. However, the permanent placement of their services into edge clouds may not be economic, since computing and bandwidth resources in edge clouds are limited and relatively expensive. A smart way is to cache the services that are frequently requested by mobile users in edge clouds. In this paper, we study the problem of service caching in mobile edge network under a mobile service market with multiple network service providers completing for both computation and bandwidth resources of the edge cloud. We propose an Integer Linear Program (ILP) and a randomized rounding algorithm, for the problem without resource sharing among the network service providers. We also devise a distributed and stable game-theoretical mechanism for the problem with resource sharing among the network service providers, with the objective to minimize the social cost of all network service providers, by introducing a novel cost sharing model and a coalition formation game. We analyze the performance of the mechanism by showing a good guaranteed gap between the solution obtained and the optimal one, i.e., Strong Price of Anarchy (SPoA). We finally evaluate the performance of our algorithms by extensive simulations, and the obtained results show that the social cost of all players can be reduced significantly via allowing cooperation among network service providers in service caching.

This special issue (SI) aims to present recent advances in the design and analysis of communication interfaces for Industry 4.0. The Industry 4.0 paradigm aims to integrate advanced manufacturing techniques with Industrial Internet-of-Things (IIoT) to create an agile digital manufacturing ecosystem. The main goal is to instrument production processes by embedding sensors, actuators and other control devices which autonomously communicate with each other throughout the value-chain[1].

Timely processing has been increasingly required on smart IoT devices, which leads to directly implementing information processing tasks on an IoT device for bandwidth savings and privacy assurance. Particularly, monitoring and tracking the observed signals in continuous form are common tasks for a variety of near real-time processing IoT devices, such as in smart homes, body-area, and environmental sensing applications. However, these systems are likely low-cost resource-constrained embedded systems, equipped with compact memory space, whereby the ability to store the full information state of continuous signals is limited. Hence, in this article,* we develop solutions of efficient timely processing embedded systems for online classification and tracking of continuous signals with compact memory space. Particularly, we focus on the application of smart plugs that are capable of timely classification of appliance types and tracking of appliance behavior in a standalone manner. We implemented a smart plug prototype using low-cost Arduino platform with small amount of memory space to demonstrate the following timely processing operations: (1) learning and classifying the patterns associated with the continuous power consumption signals and (2) tracking the occurrences of signal patterns using small local memory space. Furthermore, our system designs are also sufficiently generic for timely monitoring and tracking applications in other resource-constrained IoT devices.

The Internet-of-Things (IoT) has engendered a new paradigm of integrated sensing and actuation systems for intelligent monitoring and control of smart homes and buildings. One viable manifestation is that of IoT-empowered smart lighting systems, which rely on the interplay between smart light bulbs (equipped with controllable LED devices and wireless connectivity) and mobile sensors (possibly embedded in users’ wearable devices such as smart watches, spectacles, and gadgets) to provide automated illuminance control functions tailored to users’ preferences (e.g., of brightness, color intensity, or color temperature). Typically, practical deployment of these systems precludes the adoption of sophisticated but costly location-aware sensors capable of accurately mapping out the details of a dynamic operational environment. Instead, cheap oblivious mobile sensors are often utilized, which are plagued with uncertainty in their relative locations to sensors and light bulbs. The imposed volatility, in turn, impedes the design of effective smart lighting systems for uncertain indoor environments with multiple sensors and light bulbs. With this in view, the present article sheds light on the adaptive control algorithms and modeling of such systems. First, a general model formulation of an oblivious multisensor illuminance control problem is proposed, yielding a robust framework agnostic to a dynamic surrounding environment and time-varying background light sources. Under this model, we devise efficient algorithms inducing continuous adaptive lighting control that minimizes energy consumption of light bulbs while meeting users’ preferences. The algorithms are then studied under extensive empirical evaluations in a proof-of-concept smart lighting testbed featuring LIFX programmable bulbs and smartphones (deployed as light sensing units). Lastly, we conclude by discussing the potential improvements in hardware development and highlighting promising directions for future work.

The Paradigm of Internet of Things (IoT) is increasingly integrated with real-world applications. There are many critical IoT applications in the energy sector. Worldwide energy systems and infrastructure are experiencing tremendous transformation. There has been a drastic surge in the global energy consumption, which has tripled in the past 50 years. As a result, new measures have been introduced to improve the responsiveness and robustness of the energy systems, along with the global trends of deregulation and decarbonization.

Electrification of transportation is critical for a low-carbon society. In particular, public vehicles (e.g., taxis) provide a crucial opportunity for electrification. Despite the benefits of eco-friendliness and energy efficiency, adoption of electric taxis faces several obstacles, including constrained driving range, long recharging duration, limited charging stations, and low gas price, all of which impede taxi drivers' decisions to switch to electric taxis. On the other hand, the popularity of ride-hailing mobile apps facilitates the computerization and optimization of taxi service strategies, which can provide computer-assisted decisions of navigation and roaming for taxi drivers to locate potential customers. This paper examines the viability of electric taxis with the assistance of taxi service strategy optimization, in comparison with conventional taxis with internal combustion engines. A big data study is provided using a large data set of real-world taxi trips in New York City (NYC). Our methodology is to first model the computerized taxi service strategy by Markov decision process, and then obtain the optimized taxi service strategy based on NYC taxi trip data set. The profitability of electric taxi drivers is studied empirically under various battery capacity and charging conditions. Consequently, we shed light on the solutions that can improve viability of electric taxis.

Information exchange in a vehicular network between autonomous vehicles and the roadside infrastructure is important for improving road safety. These autonomous vehicles, equipped with a sensor suite, are capable of obtaining road map data that can be used to inform other vehicles and update the central road map repository through roadside units. The roadside infrastructure nodes act as local databases for distributing regional 3D road map data in form of point clouds to autonomous vehicles passing by. Since the vehicles might have various side information regarding the road network and traffic condition, minimizing the required number of transmissions to satisfy the demand of participating vehicles through network coding is an interesting research problem in road map data dissemination. In this paper, we propose the Road Map Data Encoding and Dissemination System (REDS) and evaluate its performance in a four-way junction scenario. It is based on index coding for broadcasting road map data from a centrally-managed roadside node to vehicles. REDS uses the data availability and demand knowledge for encoding and transmitting 3D point cloud road map data from different road segments. The data availability information helps prevent the transmission of duplicated road map data and provides the sets of side information in the index coding problem, while the data demand information further defines the message transmission priority based on the data demand of different road segments. Simulation results indicate that REDS reduces the average number of transmissions and transmitted point cloud data size by around 30% when the data availability probability is about 0.5 under random mobility in all simulated scenarios when compared to the traditional broadcasting approach.

Drive modes are driver-selectable pre-set configurations of powertrain and certain vehicle parameters. Plug-in hybrid electric vehicles typically feature the special options of drive modes that can affect the hybrid energy source management system; for example, electric vehicle mode (which draws fully on battery) and charge sustaining mode (which utilizes internal combustion engine to charge the battery while propelling the vehicle). This paper studies an optimization problem to enable the driver to select the appropriate drive modes for fuel minimization. We develop the optimization algorithms that optimize the decisions of drive modes based on trip information and, integrated with path planning to find an optimal path, considering intermediate filling and charging stations. We further provide an online algorithm that is based on the revealed trip information. We evaluate our algorithms empirically on a Chevrolet Volt, which shows significant fuel savings.

The advent of abundant on-board sensors and electronic devices in vehicles populates the paradigm of participatory sensing to harness crowd-sourced data gathering for intelligent transportation applications, such as distance-to-empty prediction and eco-routing. While participatory sensing can provide diverse driving data, there lacks a systematic study of effective utilization of the data for personalized prediction. There are considerable challenges on how to interpolate the missing data from a sparse data set, which often arises from participatory sensing. This paper presents and compares various approaches for personalized vehicle energy consumption prediction, including a blackbox framework that identifies driver/vehicle/environment-dependent factors and a collaborative filtering approach based on matrix factorization. Furthermore, a case study of distance-to-empty prediction for electric vehicles by participatory sensing data is conducted and evaluated empirically, which shows that our approaches can significantly improve the prediction accuracy.

The increasingly dense deployments of wireless CSMA networks arising from applications of Internet-of-things call for an improvement to mitigate the interference among simultaneous transmitting wireless devices. For cost efficiency and backward compatibility with legacy transceiver hardware, a simple approach to address interference is by appropriately configuring the carrier sensing thresholds in wireless CSMA protocols, particularly in dense wireless networks. Most prior studies of the configuration of carrier sensing thresholds are based on a simplified conflict graph model, whereas this paper considers a realistic signal-to-interference-and-noise ratio model. We provide a comprehensive study for two effective wireless CSMA protocols: Cumulative-interference-Power Carrier Sensing and Incremental-interference-Power Carrier Sensing, in two aspects: (1) static approach that sets a universal carrier sensing threshold to ensure interference-safe transmissions regardless of network topology, and (2) adaptive approach that adjusts the carrier sensing thresholds dynamically based on the feedback of nearby transmissions. We also provide simulation studies to evaluate the starvation ratio, fairness, and goodput of our approaches.

There is a fundamental tradeoff between the communication cost and the latency in information aggregation. Aggregating multiple communication messages over time can alleviate overhead and improve energy efficiency on one hand, but inevitably incurs information delay on the other hand. In the presence of uncertain future inputs, this tradeoff should be balanced in an online manner, which is studied by the classical dynamic TCP ACK problem for a single information source. In this paper, we extend dynamic TCP ACK problem to a general setting of collecting aggregate information from distributed and correlated information sources. In this model, distributed sources observe correlated events, whereas only a small number of reports are required from the sources. The sources make online decisions about their reporting operations in a distributed manner without prior knowledge of the local observations at others. Our problem captures a wide range of applications, such asin-situsensing, anycast acknowledgement, and distributed caching. We present simple threshold-based competitive distributed online algorithms under different settings of intercommunication. Our algorithms match the theoretical lower bounds in order of magnitude. We observe that our algorithms can produce satisfactory performance in simulations and practical test bed.

A challenge in future smart grid is how to efficiently allocate power among customers considering inelastic demands, when the power supply is constrained by the network or generation capacities. This problem is an extension to the classical knapsack problem in a way that the item values are expressed as non-positive real or complex numbers representing power demands, rather than positive real numbers. The objective is to maximize the total utility of the customers. Recently in Chau-Elbassioni-Khonji [AAMAS 14], a PTAS was presented for the case where the maximum phase angle between any pair of power demands is φ ≤ π/2; and a bi-criteria FPTAS when π/2 <; φ ≤ π - ε, for any polynomially small ε. For 0 ≤ φ ≤ π/2, Yu and Chau [AAMAS 13] showed that unless P=NP, there is no FPTAS. In this paper, we present important hardness results that close the approximation gap. We show that unless P=NP, there is no α-approximation for π/2 <; π ≤ π - ε, where a is any number with polynomial length. Moreover, for the case when φ is arbitrarily close to π, neither a PTAS nor any bi-criteria approximation algorithm with polynomial guarantees can exist. In this paper, we also present a natural generalization to a networked setting such that each edge in the transmission network can have a capacity constraint. We show that there is no bi-criteria approximation algorithm with polynomial guarantees for this networked setting, even all power demands are real (non-complex) numbers.

Nowadays digital services, such as cloud computing and network access services, allow dynamic resource allocation and virtual resource isolation. This trend can create a new paradigm of flexible pricing schemes. A simple pricing scheme is to allocate multiple isolated service classes with differentiated prices, namely Paris Metro Pricing (PMP). The benefits of PMP are its simplicity and applicability to a wide variety of general digital services, without considering specific performance guarantees for different service classes. The central issue of our study is whether PMP is economically viable, namely whether it will produce more profit for the service provider and whether it will achieve more social welfare. Prior studies had only considered specific models and arrived at conflicting conclusions. In this article, we identify unifying principles in a general setting and derive general sufficient conditions that can guarantee the viability of PMP. We further apply the results to analyze various examples of digital services.

Microgrids represent an emerging paradigm of future electric power systems that can utilize both distributed and centralized generations. Two recent trends in microgrids are the integration of local renewable energy sources (such as wind farms) and the use of co-generation (i.e., to supply both electricity and heat). However, these trends also bring unprecedented challenges to the design of intelligent control strategies for microgrids. Traditional generation scheduling paradigms rely on perfect prediction of future electricity supply and demand. They are no longer applicable to microgrids with unpredictable renewable energy supply and with co-generation (that needs to consider both electricity and heat demand). In this paper, we study online algorithms for the microgrid generation scheduling problem with intermittent renewable energy sources and co-generation, with the goal of maximizing the cost-savings with local generation. Based on the insights from the structure of the offline optimal solution, we propose a class of competitive online algorithms, called CHASE (Competitive Heuristic Algorithm for Scheduling Energy-generation), that track the offline optimal in an online fashion. Under typical settings, we show that CHASE achieves the best competitive ratio among all deterministic online algorithms, and the ratio is no larger than a small constant 3. We also extend our algorithms to intelligently leverage on limited prediction of the future, such as near-term demand or wind forecast. By extensive empirical evaluations using real-world traces, we show that our proposed algorithms can achieve near offline-optimal performance. In a representative scenario, CHASE leads to around 20% cost reduction with no future look-ahead, and the cost reduction increases with the future look-ahead window.

In multi-hop wireless networks, per-hop forwarding strategies that optimize local transmissions can have a subtle impact on network performance. Motivated by a number of scenarios for improving signal strength or mitigating interference, we study a fundamental problem that arises in a wireless ad hoc network with directional transmission (e.g., using directional antennas), where nodes are randomly placed with their transmission footprints (each as a sector) aligned toward the destinations. Only the nodes located in the transmission footprint of a transmitter act as forwarders. Our study addresses connectivity of this setting. We first examine through simulation the percolation probability and the number of cross-area paths available to directional transmission, at different spread angles of transmission footprints. We observe that there is a critical spread angle, above which there is little impact on these properties. Analytically, we derive upper and lower bounds for the critical spread angle. Moreover, we show that with high probability there exist at least Ω(n/ log n) number of disjoint paths across a strip area of n × Θ(n), when the critical spread angle lies above the threshold. Our results provide insights on optimizing directional transmission in wireless ad hoc networks.

Mixing time is a fundamental property for a number of transient behaviors of stochastic processes, particularly, random access in CSMA networks. We use mixing time to characterize temporal starvation, which is a transient phenomenon where links can starve for prolonged periods indefinitely often despite having good stationary throughput. Considering a general CSMA network, we study a fundamental setting with multiple frequency agility, such that more than one frequency channel is available, and a link can transmit on at most one of the frequency channels not occupied by its neighbors. The characterization of throughput in such a setting is challenging, involving a hidden Markov chain of the associated stochastic process. This paper develops new results based on the mixing time of hidden Markov chains to shed light on the temporal starvation. Our analytical results quantify the effect of the number of frequency channels on temporal starvation. We provide sufficient and necessary conditions for fast mixing time of the corresponding hidden Markov chain.

Interoperation in MANETs is an important issue in many operational situations, because of the growing number of heterogeneous MANETs with different standards, technologies and adminstrative management. To enable interoperation, gateways are often deployed for protocol translation, inter-MANET routing, and management policy enforcement among these heterogeneous MANETs. To optimize gateway deployment, we consider the gateway functionalities to be enabled or disabled dynamically in response to the changing network topology. In this paper, we offer mechanisms to select the minimal subset of enabled gateways among the deployed gateways to ensure the interoperation among the MANETs. To this aim, we formulate a novel graph optimization problem, called Minimal Gateway Assignment Problem, and prove that it is NP-hard. Nonetheless, we provide efficient algorithms to solve this problem with varying degrees of complexity and coordination. First, we provide a centralized polynomial-time algorithm that is 2-approximable, and a distributed algorithm. Second, by simulation, we show that our centralized and distributed algorithms can perform close to the optimal. We also report an interesting result that cooperation is the key factor to produce optimal outcomes - a simple algorithm with tight cooperation among MANETs gives much better outcomes than a smart algorithm with loose cooperation.

One of the challenges of wireless networks is to provide a reliable end-to-end path between two end hosts in the face of link and node outages. These can occur due to fluctuations in channel quality, node movement, or node failure. One mechanism that has been proposed is based on multipath routing, the idea being to establish two or more paths between the end hosts so that they always have a path between them with high probability in the face of outages. This naturally raises the question of how to discover these paths in an unknown, random wireless network to enable robust multipath routing. In order to answer this question, we model a random wireless network as a 2D spatial Poisson process. Based on the results of percolation highways in Franceschetti, et al., we present accurate conditions that enable robust multipath routing. If the number of hops of a path between the end hosts is n, then there exists a path between them in a strip of width proportional to log n. More precisely, there exist C log n disjoint paths in a strip of width a(C, p) · log n, where p is the probability that characterizes the availability of an individual wireless communication link. We derive tight bounds for the function a(C, p). This provides a useful guideline for the establishment of multiple paths in a real wireless network, namely that the width should grow logarithmically in the number of hops on the path between the hosts.

The information of temporal correlations among network-wide data flows is crucial to a wide range of network management applications, such as root-cause analysis, threat monitoring, and traffic profiling. While several prior work had only studied the centralized and offline computation of flow correlations, we present DisTrack, a space-efficient network management mechanism for online tracking of network-wide temporal flow correlations. The major benefits of DisTrack include low space complexity, high processing speed, and ease of distributed deployment. This paper presents its randomized data structures, with theoretical analysis on the trade-off between space complexity and accuracy. We further provide extensive empirical evaluations on real network traces.

Duty cycling or periodic sleep scheduling of RF transceivers of nodes in a wireless ad hoc or sensor network can significantly reduce energy consumption. This paper sheds light on the fundamental limits of the end-to-end data delivery latency and the per-flow throughput in a wireless network with multiple interfering flows, in the presence of "coordinated" duty cycling. We propose green wave sleep scheduling (GWSS) - inspired by synchronized traffic lights - for scheduling sleep-wake slots and routing data in a duty cycling wireless network, whose performance can approach the aforementioned limits. Particularly, we derive a general latency lower bound and show that GWSS is latency optimal on various structured topologies, such as the line, grid and the tree, at low traffic load. For an arbitrary network, finding a solution to the delay-efficient sleep scheduling problem is NP-hard. But for the 2D grid topology, we show that a non-interfering construction of GWSS is optimal in the sense of scaling laws of latency and capacity. Finally, using results from percolation theory, we extend GWSS to random wireless networks, where nodes are placed in a square area according to the Poisson point process. Aided by strong numerical evidence for a new conjecture on percolation on a semi-directed lattice that we propose, we demonstrate the latency optimality of GWSS on a random extended network, i.e., for an area-n random network with unit-density-Poisson distributed nodes, and a node-active (duty-cycling) rate p, GWSS can achieve a per-flow throughput scaling of T(n, p) = Ω(p/√n) bits/sec and latency D(n, p) scaling of O(√n) + O(1/p) hops/packet/flow.

Stateless opportunistic forwarding is a simple fault-tolerant distributed scheme for packet delivery, data gathering, and information querying in intermittently connected networks by which packets are forwarded to the next available neighbors in a “random walk” fashion until they reach their intended destinations or expire. It has been employed in diverse situations, for instance, when: 1) the global network topology is not known or is highly dynamic; 2) the availability of the next-hop neighbors is not easily controllable; or 3) the relaying nodes are computationally constrained. Data delivery in sensor networks, ad hoc networks, and delay-tolerant networks are well-known applications besides searching in peer-to-peer networks. A major challenge for stateless opportunistic forwarding is the difficulty to predict the end-to-end latency. To facilitate latency evaluation, we study a simplified model of stateless opportunistic forwarding, namely a “weighted random walk” in a finite graph. This paper makes several contributions toward the analysis of this model. 1) By spectral graph theory we derive a general formula to efficiently compute the exact hitting and commute times of random walks with heterogeneous transition times at relay nodes. Such transition times can model the heterogeneous delivery times and availability periods of the next-hop neighbors. 2) We study a common class of distance-regular networks with a varying number of geographical neighbors and obtain exact and approximation formulas for the hitting time in such networks. 3) Based on these results, we study other sophisticated settings, such as random geographical locations, topology-aware forwarding, and multicopy random-walk forwarding. Our results provide the basic analytical tools for managing and controlling the performance of stateless opportunistic forwarding in finite networks.

In the literature, asymptotic studies of multihop wireless network capacity often consider only centralized and deterministic time-division multiple-access (TDMA) coordination schemes. There have been fewer studies of the asymptotic capacity of large-scale wireless networks based on carrier-sensing multiple access (CSMA), which schedules transmissions in a distributed and random manner. With the rapid and widespread adoption of CSMA technology, a critical question is whether CSMA networks can be as scalable as TDMA networks. To answer this question and explore the capacity of CSMA networks, we first formulate the models of CSMA protocols to take into account the unique CSMA characteristics not captured by existing interference models in the literature. These CSMA models determine the feasible states, and consequently the capacity of CSMA networks. We then study the throughput efficiency of CSMA scheduling as compared to TDMA. Finally, we tune the CSMA parameters so as to maximize the throughput to the optimal order. As a result, we show that CSMA can achieve throughput as Ω([1/√(n)]), the same order as optimal centralized TDMA, on uniform random networks. Our CSMA scheme makes use of an efficient backbone-peripheral routing scheme and a careful design of dual carrier-sensing and dual channel scheme. We also address implementation issues of our CSMA scheme.

Paris Metro Pricing (PMP) is a simple multi-class flat-rate pricing scheme already practiced by transport systems, specifically by the Paris Metro at one time. The name is coined after Andrew Odlyzko proposed it for the Internet as a simple way to provide differentiated services. Subsequently, there were several analytical studies of this promising idea. The central issue of these studies is whether PMP is viable, namely, whether it will produce more profit for the service provider, or whether it will achieve more social welfare. The previous studies considered similar models, but arrived at different conclusions. In this paper, we point out that the key is how the users react to the congestion externality of the underlying system. We derive sufficient conditions of congestion functions that can guarantee the viability of PMP, and provide the relevant physical meanings of these conditions.

While scheduling the nodes in a wireless network to sleep periodically can save energy, it also incurs higher latency and lower throughput. We consider the problem of designing optimal sleep schedules in wireless networks, and show that finding sleep schedules that can minimize the latency over a given subset of source-destination pairs is NP-hard. We also derive a latency lower bound given by d + O(1/p) for any sleep schedule with a required active rate (i.e., the fraction of active slots of each node) p, and the shortest path length d. We offer a novel solution to optimal sleep scheduling using green-wave sleep scheduling (GWSS), inspired by coordinated traffic lights, which is shown to meet our latency lower bound (hence is latency-optimal) for topologies such as the line, grid, ring, torus and tree networks, under light traffic. For high traffic loads, we propose non-interfering GWSS, which can achieve the maximum throughput scaling law given by T(n,p) = ¿(p/¿n) bits/sec on a grid network of size n, with a latency scaling law D(n,p) = O(¿n) + O(1/p). Finally, we extend GWSS to a random network with n Poisson-distributed nodes, for which we show an achievable throughput scaling law of T(n,p) = ¿(p/¿(n log n)) bits/sec and a corresponding latency scaling law D(n,p) = O(¿(n/log n)) + O(1/p); hence meeting the well-known Gupta-Kumar achievable throughput rate ¿(1/¿(n log n)) when p ¿ 1.

The advancements of diverse radio technologies and emerging applications have spawned increasing heterogeneity in mobile ad hoc networks (MANETs). But the collaborative nature of communications and operations often requires that these heterogeneous MANETs to be interoperable. Nonetheless, the existing interconnection protocols designed for the Internet (namely inter-domain routing protocol such as BGP) are not adequate for handling the unique challenges in MANETs. In this paper, we present a novel Inter-MANET Routing protocol called InterMR that can handle the heterogeneity and dynamics of MANETs. Our first contribution is an Inter-MANET address scheme based on a variety of node attributes (e.g., symbolic name, property, etc.); this allows dynamic merging/split of network topologies without a separate Name Server. Our second contribution is to provide a seamless routing mechanism across heterogeneous MANETs without modifying the internal routing mechanisms in each MANET. The proposed scheme can transparently adapt to topological changes due to node mobility in MANETs by dynamically assigning the gateway functionalities. We show, by packet-level simulation, that the performance of InterMR can be improved by up to 112% by adaptive gateway assignment functionalities. We also show that InterMR is scalable with only modest overhead by analysis.

Many applications of wireless sensor networks rely on batteries. But most batteries are not simple energy reservoirs, and can exhibit battery recovery effect. That is, the deliverable energy in a battery can be self-replenished, if left idling for sufficient time. As a viable approach for energy optimisation, we made several contributions towards harnessing battery recovery effect in sensor networks. 1) We empirically examine the gain of battery runtime of sensor devices due to battery recovery effect, and affirm its significant benefit in sensor networks. We also observe a saturation threshold, beyond which more idle time will contribute only little to battery recovery. 2) Based on our experiments, we propose a Markov chain model to capture battery recovery considering saturation threshold and random sensing activities, by which we can study the effectiveness of duty cycling and buffering. 3) We devise a simple distributed duty cycle scheme to take advantage of battery recovery using pseudo-random sequences, and analyse its trade-off between the induced latency of data delivery and duty cycle rates.

Stateless opportunistic forwarding is a simple fault- tolerant distributed approach for data delivery and information querying in wireless ad hoc networks, where packets are forwarded to the next available neighbors in a "random walk" fashion, until they reach the destinations or expire. This approach is robust against ad hoc topology changes and is amenable to computation/bandwidth/energy-constrained devices; however, it is generally difficult to predict the end-to-end latency suffered by such a random walk in a given network. In this paper, we make several contributions on this topic. First, by using spectral graph theory we derive a general formula for computing the exact hitting and commute times of weighted random walks on a finite graph with heterogeneous sojourn times at relaying nodes. Such sojourn times can model heterogeneous duty cycling rates in sensor networks, or heterogeneous delivery times in delay tolerant networks. Second, we study a common class of distance-regular networks with varying numbers of geographical neighbors, and obtain simple estimate-formulas of hitting times by numerical analysis. Third, we study the more sophisticated settings of random geographical locations and distance-dependent sojourn times through simulations. Finally, we discuss the implications of this on the optimization of latency-overhead trade-off.

In the literature, asymptotic studies of multi-hop wireless network capacity often consider only centralized and deterministic TDMA (time-division multi-access) coordination schemes. There have been fewer studies of the asymptotic capacity of large-scale wireless networks based on CSMA (carrier-sensing multi-access), which schedules transmissions in a distributed and random manner. With the rapid and widespread adoption of CSMA technology, a critical question is that whether CSMA networks can be as scalable as TDMA networks. To answer this question and explore the capacity of CSMA networks, we first formulate the models of CSMA protocols to take into account the unique CSMA characteristics, not captured by existing interference models in the literature. These CSMA models determine the feasible states, and consequently the capacity of CSMA networks. %and are functions of various CSMA parameters. We then study the throughput efficiency of CSMA scheduling as compared to TDMA. Finally, we tune the CSMA parameters so as to maximize the throughput to the optimal order. As a result, we show that CSMA can achieve throughput as Ω(1/√n), the same order as optimal centralized TDMA, on uniform random networks. Our CSMA scheme makes use of an efficient backbone-peripheral routing scheme and a careful design of dual carrier-sensing and dual channel scheme. We also address practical implementation issues of our capacity-optimal CSMA scheme.

Random geometric graphs are widely-used for modelling wireless ad hoc networks, where nodes are randomly deployed with each covering a finite region. The fundamental properties of random geometric graphs are often studied in the literature, such as the probability of connectivity and random coverage area. While there are numerous asymptotic results that concern the related scaling laws in very large random geometric graphs, more accurate estimation for the finite cases with moderate-sized networks remains challenging. In this paper, we present a remarkably good approximation relationship for the probability of connectivity and random coverage area between the random geometric graphs induced by circular and square coverage models, under suitable normalisation. We also provide analytical results towards justifying the good approximation relationship. This relationship is then exploited, combining with the results from reliability studies, to obtain more accurate estimation for the probability of connectivity in finite random geometric graphs.

Many applications of sensor networks require batteries as the energy source, and hence critically rely on energy optimisation of sensor batteries. But as often neglected by the networking community, most batteries are non-ideal energy reservoirs and can exhibit battery recovery effect — the deliverable energy in batteries can be replenished per se, if left idling for sufficient duration. We made several contributions towards harnessing battery recovery effect in sensor networks. First, we empirically examine the gain of battery runtime due to battery recovery effect, and found this effect significant and duration-dependent. Second, based on our findings, we model the battery recovery effect in the presence of random sensing activities by a Markov chain model, and study the effect of duty cycling and buffering to harness battery recovery effect. Third, we propose a more energy-efficient duty cycling scheme that is aware of battery recovery effect, and analyse its performance with respect to the latency of data delivery.

We propose a new firewall architecture that treats port numbers as part of the IP address. Hosts permit connectivity to a service by advertising the IPaddr:port/48 address; they block connectivity by ensuring that there is no route to it. This design, which is especially well-suited to MANETs, provides greater protection against insider attacks than do conventional firewalls, but drops unwanted traffic far earlier than distributed firewalls do.

This paper analyses the robustness of networked systems from a game-theoretical perspective. Networked systems often consist of several subsystems sharing resources interdependently based on local preferences. These systems can be modelled by a dependence game, which is a generalisation of stable paths problem. A unique pure Nash equilibrium in a dependence game can characterise the robustness of the represented networked system, precluding oscillations and nondeterminism. We show that the absence of a structure termed a generalised dispute wheel is useful to ensure the existence of a unique pure Nash equilibrium. Furthermore, we consider more sophisticated settings: tie-breaking over non-strict preferences and asynchronous communications among subsystems. We also obtain stronger results that the absence of a generalised dispute wheel can be useful to ensure the consistency of tie-breaking and asynchronous convergence to a pure Nash equilibrium.

We use the term policy-based routing to refer collec- tively to the Stable Paths Problem, Sobrinho's Routing Algebras, and to classical Path Algebras (semi-rings used to generalise minimum-weight routing). These theories all contain sufficient conditions that ensure the existence of solutions (stable routings) for labelled graphs. We attempt to provide a unified theory from which all of these seemingly disparate sufficient conditions can be derived. Our theory is based purely on abstract relations and their properties and not on the syntactic or axiomatic details of the policy-based theories.

Traditional studies of routing problems often assumed strict preferences on paths, by eliminating ambiguity in path comparisons, or imposing a priori deterministic tie-breaking. Such an assumption is outpaced by today's common practice of non-deterministic,multi-path routing, which is crucial to traffic engineering, QoS routing, multicasting and virtual private networking. A pair of paths may be incomparable or equally preferred. In the presence of ambiguous preferences at pairs, or even multiple collections of paths, a challenge is to ensure robustness in the complex and sophisticated situations of policy-based routing where heterogeneous routing policies are allowed among routing systems. This paper presents an extensive study of policy-based routing with non-strict preferences, deriving sufficient conditions that ensure the existence, optimality and asynchronous convergence of stable routings.