We study queues with impatient customers and Processor Sharing (PS) discipline as well as other variants of PS discipline, namely, Discriminatory Processor Sharing (DPS) and Generalized Processor Sharing (GPS) disciplines, where customers have deadlines until the end of service (DES). Customers arrive according to a state-dependent Poisson process and have general impatience. Customers have exponential service times with state-dependent service rates. Analytical methods based on simple Markov chains are given for the performance analysis of such queues. The principal measures of performance are the steady-state probability of missing deadline and the steady-state probability of blocking. Similar results are obtained for related queues with Random Order Service (ROS) discipline where customers have deadlines until the beginning of service (DBS). In view of a lack of exact analytical results for First Come First Served (FCFS) queues with state-dependent rates, a highly accurate approximation method is also given for these latter queues. The efficacy and accuracy of the approach are illustrated by some numerical examples and simulation experiments.

A new transport protocol is introduced to increase the responsiveness of the network to congestion. The new transport protocol, QUCO, reacts to congestion by selectively dropping off parts of a payload packet (combined with mitigation mechanisms to handle the loss of part of the payload). This packet trimming scheme greatly reduces the variations in the number of the packets going through the network. This allows to set tighter targets on the number of packets in flight and on the depth of the switch buffers. QUCO has less delay and much less delay variations than TCP. The resulting reduction in jitter is extremely useful, especially for media distribution.

The current Internet protocol suite, with its best-effort semantics, can result in potentially very different delivery characteristics for packets. Actually, no two paths (or even different packet flows on the same path) can be assumed to have identical properties in terms of bandwidth, delay and jitter. However, multi-site remote collaboration applications are highly inter-dependent and must remain consistent across multiple users. To this end, we introduce a new network capability, called coordinated communication service, and propose coordination points to support coordinated delivery of multiple flows in the network.

Name lookup is an essential function but a performance bottleneck in both today's and future network architectures. Trie is an excellent candidate data structure and has been widely used for looking up and updating names. However, the granularity of trie-at bit, byte (character), or component level-can dramatically affect the network performance in terms of memory usage and packet-processing speed, which has not yet been studied adequately. To fill this gap, we first show that the choice of trie's granularity for name lookups and updates (i.e., insertions and removals) is not a trivial problem due to the complex performance tradeoffs involved. We also introduce a new tool, called NameGen, which uses a Markov-based name learning model and generates pseudo-real datasets with different tunable name characteristics. We compare different trie granularities based on a collection of datasets and performance metrics, highlight the strengths and weaknesses of each granularity, and draw a conclusion on the choice of granularity. Surprisingly, our experimental evaluation finds that there are only two key rules to choose the proper trie's granularity for any kind of dataset: 1) bit-level trie is the choice when the memory requirement is a real concern and 2) character- and component-level tries are preferred for faster lookups and updates when dealing with names composed of short and long components, respectively.

In recent years, augmented reality (AR) has drawn significant attention in the automotive industry and shown great potential for a variety of driver-assistance applications. Tracking the driver's head is vital to seamlessly merge the AR content in the driver's view but still remains an open problem. Specifically, most existing in-vehicle AR solutions rely on cameras for head tracking, which suffer from low sampling rate, weak performance at night, and even high computation costs. Wearing a dedicated headset, on the other hand, is intrusive and inconvenient for daily driving.

Name lookup is an essential function, but a performance bottleneck in both today's and future network architectures. Variable-length and unbounded names rather than fixed-length addresses, as well as much larger and more dynamic forwarding tables call for a careful re-engineering of lookup structures for fast, memory-efficient, and scalable packet forwarding. We propose a novel data structure, called NameTrie, to store and index forwarding table entries efficiently and to support fast name lookups and updates. Its novelty lies in the optimized design and implementation of a character-trie structure. The nodes of NameTrie are stored compactly, improving cache efficiency and speeding up packet processing. Its edges are implemented using a hash table, facilitating fast name lookups and updates. A new scheme is used to encode control information without consuming additional memory. Running on conventional commodity hardware and using large-scale real-world name datasets, our implementation of NameTrie in software achieves 2.82~3.56, 3.48~3.72, and 2.73~3.25 million name insertions, lookups, and removals per second, respectively, for various datasets while requiring a small memory footprint. We have conducted a comprehensive performance evaluation against the state-of-the-art of named data networking (NDN) as a typical use-case. It is shown to require at least 35% less memory and runs at least 3x faster for name table lookups and updates than two well-known trie-based schemes in NDN.

Maximizing quality of aggregation (QoA) is an essential requirement for real-time wireless sensor networks (WSNs) where the participation of all sensor nodes in data aggregation is hampered by the underlying sink deadline and interference constraints. This problem, however, remains unsolved under the physical interference model that captures the reality more accurately than the widely used graph-based models. In this paper, we formulate an optimization problem of maximizing QoA under deadline and interference constraints in commonly seen tree- based WSNs. We prove the problem to be NP- complete, and then propose a suboptimal scheduling algorithm which relies on a Markov approximation framework and modifies the matching graphs in order to handle the globally-imposed interference constraints. The problem and its solution are then coupled with successive interference cancellation (SIC) to improve QoA by increasing the number of concurrent transmissions. Our evaluation has shown the proposed solution to be effective under the physical interference model, both with and without SIC.

Limited energy in each node is the major design constraint in wireless sensor networks (WSNs). To overcome this limit, wireless rechargeable sensor networks (WRSNs) have been proposed and studied extensively over the last few years. In a typical WRSN, batteries in sensor nodes can be replenished by a mobile charger that periodically travels along a certain trajectory in the sensing area. To maximize the charged energy in sensor nodes, one fundamental question is how to control the traveling velocity of the charger. In this paper, we first identify the optimal velocity control as a key design objective of mobile wireless charging in WRSNs. We then formulate the optimal charger velocity control problem on arbitrarily-shaped irregular trajectories in a 2D space. The problem is proved to be NP-hard, and hence a heuristic solution with a provable upper bound is developed using novel spatial and temporal discretization. We also derive the optimal velocity control for moving the charger along a linear (1D) trajectory commonly seen in many WSN applications. Extensive simulations show that the network lifetime can be extended by 2.5× with the proposed velocity control mechanisms.

Data aggregation is a key, yet time-consuming functionality introduced to conserve energy in wireless sensor networks (WSNs). In this paper, to minimize time latency, we focus on aggregation scheduling problem and propose an efficient distributed algorithm that generates a collision-free schedule with the least number of time slots. In contrast to others, our approach named FAST mainly contributes to both tree construction, where the former studies employ Connected 2-hop Dominating Sets, and aggregation scheduling that was previously addressed through the Competitor Sets computation. We prove that the latency of FAST under the protocol interference model is upper-bounded by 12R + Δ - 2, where R is the network radius and Δ is the maximum node degree in the communication graph of the original network. Both the theoretical analysis and simulation results show that FAST outperforms the state-of-the-art aggregation scheduling algorithms.

Data aggregation is an effective technique which is introduced to conserve energy by reducing packet transmissions in wireless sensor networks (WSNs). In addition, it is possible to consume less energy by using the spatial correlation and redundancy of data in dense networks to form clusters of nodes sensing similar values and, in turn, transmit one data packet per cluster. In this paper, we propose a Data-Aware Clustering and Aggregation scheme (DACA) to manage the energy constraint in a query-driven WSN. The DACA selects cluster head nodes by forming a new factor as a function of three parameters including the residual energy, the data value, and the number of neighbors at each node. Moreover, it exploits a cluster merging method to overcome the problem of the previous studies in which all sensor nodes become cluster heads over time, so it prolongs the network lifetime. Extensive simulations in NS-2 verify the superiority of our approach.

Data aggregation is an efficient method to conserve energy by reducing packet transmissions in WSNs. However, providing end-to-end data reliability is a major challenge when the network uses data aggregation. In this case, a packet loss can miss a complete subtree of values, thus greatly affecting the final results. Data transmission in multiple paths can tolerate this problem, but it may incur some computation errors for duplicate-sensitive aggregates. In this paper, we propose a Flexible Overlay Multi-path data Aggregation protocol (FOMA) which uses the available path redundancy to deliver a correct aggregate result to the sink with high reliability in an energy-efficient manner. It aggregates data in two layers, routing layer and data aggregation layer, while eliminating the computation errors by using a signature-based method. We implement FOMA in TinyOs 2.x and test it by the TOSSIM simulator. The results reveal that the proposed algorithm outperforms other existing ones in terms of energy consumption and data accuracy.

Network Coding (NC) is an emerging technique that helps wireless networks to have higher throughput and better energy efficiency. In this paper, a novel network coding-aware routing (S-NC) which uses NC to improve reliability and robustness in unreliable WSNs is proposed. It is based on a structure-free routing algorithm as the underlying routing engine which employs neighbor queue length to increase coding opportunity; while exploiting a spatial coding method to control the amount of redundancy. To the best of our knowledge, this is the first study on the topic of network coding-aware routing in WSNs. Simulation results in TOSSIM demonstrate that S-NC significantly improves the performance in terms of reliability, end-to-end delay, and energy consumption in the network.

The main source of energy consumption in the current MAC protocols for wireless sensor networks is idle listening. To mitigate this problem, duty cycling is used. However, it increases data delivery latency. In this paper, we propose an Interference-aware duty-cycle MAC (IMAC) protocol for wireless sensor networks that uses cross-layer information to reserve multiple paths for each source and send data packets along them efficiently. IMAC also handles the existing interference between these paths such that data packets can be delivered in the minimum required number of cycles. Simulation results in ns-2 show that the proposed algorithm has an average reduction of 49% in data delivery latency compared to a current solution called RMAC.

Data aggregation is an effective technique which is introduced to save energy by reducing packet transmissions in WSNs. However, it extends the delay at the intermediate nodes, so it can complicate the handling of delay-constrained data in event-critical applications. Besides, the structure-based aggregation as the dominant data gathering approach in WSNs suffers from high maintenance overhead in dynamic scenarios for event-based applications. In this paper, to make aggregation more efficient, we design a novel structure-free Real-time Data Aggregation protocol, RDAG, using a Real-time Data-aware Routing policy and a Judiciously Waiting policy for spatial and temporal convergence of packets. Extensive simulations in NS-2 verify the superiority of RDAG in WSNs.

The reliability of wireless sensor networks (WSNs) depends on both sensing coverage and reliable transmission of collected data provided by the target cluster of sensors in the proximity of the phenomenon to the observer. In this paper, we establish a probabilistic fundamental quantitative notion for performance-critical applications on reliable information transfer and propose a new analytical model to calculate the coverage-oriented reliability of cluster-based WSNs. Here, the packet loss probability is modeled as a function of two main parameters. The first is the probability of link failure when the node's buffer at the end point of the link is full (discarding the packet) or when the link encounters some errors (corrupting the packet). The second is the probability of path failure when at least the energy of one node is depleted on the path. Most of network properties are considered as random variables and a queuing-theory based model is derived. Simulation results are used to validate the proposed model. The simulation results agree well with the model.