360-degree videos introduce unique challenges to storytelling, especially if filmmakers want to draw the user’s attention to specific regions of the surrounding sphere to ensure the proper flow of narrative at any given time. For instance, at scene cuts, a user might lose track of a story if he/she looks toward a direction that prevents an intended Region of Interest (RoI) to appear in the viewport of the user’s Head-mounted Display (HMD). Because of that, new editing techniques for 360-degree videos are being investigated, and the use of dynamic (i.e., real time) alignment of intended RoI across scene cuts is receiving growing attention. To support research on this topic, we introduce 360EAVP, an open source web-based application for streaming and visualization of 360-degree edited videos on HMDs. The 360EAVP is built on top of the VR DASH Tile Player, which is based on cube mapping projection, and adds new capabilities to handle dynamic video editing. Specifically, 360EAVP introduces (1) real-time track of a user’s viewport direction on the HMD; (2) support for dynamic editing via “snap-change” or “fade-rotation” effects; (3) visibility mapping of the user’s Field of View (FoV) with respect to the player’s cube mapping projection (for purposes of video tile requests during streaming); (4) incorporation of editing timing information into the operation of an ABR algorithm; (5) viewport prediction module based on linear regression or ridge regression models; and (6) video playback data collection and log module. To showcase the use of 360EAVP, we present the results of a small-scale subjective experiment that aimed to evaluate the impact of the “snap-change” and “fade-rotation” editing techniques on user’s Quality of Experience (QoE), comfort, and head movement. Our findings indicate that these editing techniques do not compromise the overall QoE; in fact, in certain scenarios, an improvement is observed. In addition, some subjects significantly reduced their head movements with the editing techniques implemented.

Photorealistic media aim to faithfully represent the world, creating an experience that is perceptually indistinguishable from a real world experience. In the past few years, this area has grown significantly, with new multimedia areas emerging, such as light fields, point clouds, ultra-high definition, high frame rate, high dynamic range imaging, and novel 3D audio and sound field technologies. In spite of all the advances done so far, there are several technological challenges to overcome. In particular, research in this field typically requires the use of big datasets, software tools, and powerful infrastructures. Among these, the availability of meaningful datasets, with a diverse and high-quality content, is of significant importance and, to date, most available datasets are limited and do not provide researchers adequate tools to advance the area of photorealistic applications. To help advancing research efforts in this area, this workshop aims to engage experts and researchers on the synthesis of photorealistic images and/or virtual environments, particularly in the form of public datasets, software tools, or infrastructures, for not only multimedia systems research, but also for other fields, such as machine learning, robotics, computer vision, mixed reality, and virtual reality.

Streaming 360° videos over the Internet to Head Mounted Displays (HMDs) requires high bandwidth owing to their high resolution. Viewers, limited by the Field of View (FoV) of the HMD, can only watch a small portion of the scene at a time. Therefore, predicting the future FoV of viewers and caching popular content in the mobile edge cloud can reduce both downloading latency and traffic over the core network. The primary contributions of this work are: (i) a new strategy for generation of viewing heatmap which significantly improves our understanding of regions of viewer interest, and (ii) demonstrating the relevance of some indices used in economics and election analysis to further narrow down the viewing hot spots that can be most useful in making caching decisions and FoV prediction. We demonstrate how these indices and the improved heatmap can improve caching and FoV prediction for a number of videos drawn from two independent datasets. Most of the computation needed to implement these concepts can be performed offline by video content servers using previous viewers’ FoV traces. Hence, the computation load on viewer devices is also low.

Dynamic Adaptive Streaming over HTTP (DASH) has emerged as the de facto solution for streaming 360°videos. Viewers of 360° videos view only a fraction of each video segment, i.e., the part that corresponds to their Field of View (FoV). To facilitate FoV-adaptive streaming, a segment can be divided into multiple tiles with the FoV corresponding to a subset of tiles. Streaming each segment in its entirety from the video server to a client can incur high communication overheads both in terms of bandwidth and latency. Caching at the network edge can reduce these overheads. However, as edge cache capacity is limited, only a subset of tiles encoded at a subset of supported resolutions may be present in the cache. A viewer, depending on its FoV,may experience cache hit and low download latency for some segments, and a cache miss resulting in high download latency from video server for other segments. This can result in the DASH client unnecessarily triggering quality switches for the following reason: low (high) latency download from edge cache (server, respectively) may be misinterpreted as high (low, respectively) network throughput estimate. In this paper, we propose CooPEC (COOperative Prefetching and Edge Caching), a prefetching and complementary caching solution which uses viewers' FoV entropy to: (i) enable a bitrate oscillation-free video streaming, (ii) reduce core network bandwidth consumption, and (iii) enhance QoE for users.

An important component for viewport-adaptive streaming of 360° videos is viewport prediction. Increasing viewport prediction horizon enables the client to prefetch more chunks into the playback buffer. Having longer buffer results in less rebuffering under fluctuating network conditions. We analyzed the recorded viewport traces of viewers who watched various 360° videos. We propose a clustering-based viewport prediction method that incorporates viewport pattern information from previous video streaming sessions. For several videos, specifically those with well-defined region of interest, the proposed approach increases the viewport prediction horizon and/or prediction accuracy.

In this paper, we propose a taxonomy for 360° videos that categorizes videos based on moving objects and camera motion. We gathered and produced 28 videos based on the taxonomy, and recorded viewport traces from 60 participants watching the videos. In addition to the viewport traces, we provide the viewers' feedback on their experience watching the videos, and we also analyze viewport patterns on each category.

Much recent work has been conducted on supporting soft real-time tasks on multiprocessors due to the multicore revolution. While most earlier works focus on the traditional sporadic task model with deterministic worst-case specification, several recent works investigate the stochastic nature of many workloads seen in practice, specifying task execution times using average-case provisioning instead of the worst case. Unfortunately, all the existing work on supporting soft real-time workloads ignores a simple practical fact that the job inter-arrival time (or task period) is also stochastic for many real-world applications. Adopting a fixed worst-case period to model all the arriving pattern is rather pessimistic and may result in significant capacity loss in practice. Based on these observations, we present a general soft real-time multiprocessor schedulability analysis framework in this paper for practical sporadic task systems specified by stochastic period and execution demand, following probability distributions. Our analysis can be generally applied to global tunable priority-based schedulers, which allow any job's priority to be changed dynamically at runtime within a priority window of constant length. We have extensively evaluated the analysis framework using a MPEG video decoding case study and simulation-based experiments. Experimental results demonstrate significant advantages of our analysis, which yields over 200 and 50 percent improvements compared to existing analysis assuming worst-case task periods in terms of schedulability and magnitude of the derived tardiness bound, respectively.

In recent years, there has been growing popularity of Virtual Reality (VR), enabled by technologies like 360° video streaming. Streaming 360° video is extremely challenging due to high bandwidth and low latency requirements. Some VR solutions employ adaptive 360° video streaming which tries to reduce bandwidth consumption by only streaming high resolution video for user's Field of View (FoV). FoV is the part of the video which is being viewed by the user at any given time. Although FoV-adaptive 360° video streaming has been helpful in reducing bandwidth requirements, streaming 360° video from distant content servers is still challenging due to network latency. Caching popular content close to the end users not only decreases network latency, but also alleviates network bandwidth demands by reducing the number of future requests that have to be sent all the way to remote content servers. In this paper, we propose a novel caching policy based on users' FoV, called FoV-aware caching policy. In FoV-aware caching policy, we learn a probabilistic model of common-FoV for each 360° video based on previous users' viewing histories to improve caching performance. Through experiments with real users' head movement dataset, we show that our proposed approach improves cache hit ratio compared to Least Frequently Used (LFU) and Least Recently Used (LRU) caching policies by at least 40% and 17%, respectively.

HTTP Adaptive Streaming (HAS) is the widely adopted solution for video streaming over the Internet. When network throughput is highly variable, designing an optimal HAS solution that maximizes Quality of Experience (QoE) becomes challenging. Each chunk should be prefetched at highest possible quality while rebufferings and quality switches are minimized. Scalable Video Coding (SVC), with its layered encoding of video, provides more flexibility for HAS clients. It can reduce the occurrence of rebufferings under variable network conditions. However, SVC introduces at least 10% overhead on video bitrate per layer and increases the number of HTTP requests to fetch video chunks. So streaming SVC video at high qualities is more expensive. We propose a solutions that employs both SVC and non-SVC video to improve user's QoE while avoiding the increased bandwidth overhead and HTTP signaling of SVC. Our experiments using real-world bandwidth traces show that this method improves QoE compared to the state-of-the-art adaptation methods under various network conditions.

Applications are typically offered a single, generic option for end-to-end transport, which most commonly consists of the particular flavor of TCP that runs in the server host. This arrangement does not suit well the diversity of the requirements that individual applications pose on network metrics like throughput and delay. Link-Coupled TCP (LCTCP) is a new transport solution that leverages the architectural trends of 5G networks to enable accurate satisfaction of the unique requirements of each application. LCTCP first isolates the 5G access link as the only possible network bottleneck for the application flow, then establishes a lightweight signaling channel between the link buffer and the application server to convey critical information for flexible control of the data source. LCTCP can be deployed in the network without modification of the TCP clients. We use a Linux prototype to demonstrate its feasibility and effectiveness.

Virtual reality and 360-degree video streaming are growing rapidly, yet, streaming high-quality 360-degree video is still challenging due to high bandwidth requirements. Existing solutions reduce bandwidth consumption by streaming high-quality video only for the user's viewport. However, adding the spatial domain (viewport) to the video adaptation space prevents the existing solutions from buffering future video chunks for a duration longer than the interval that user's viewport is predictable. This makes playback more prone to video freezes due to rebuffering, which severely degrades the user's Quality of Experience especially under challenging network conditions. We propose a new method that alleviates the restrictions on buffer duration by utilizing scalable video coding. Our method significantly reduces the occurrence of rebuffering on links with varying bandwidth without compromising playback quality or bandwidth efficiency compared to the existing solutions. We demonstrate the efficiency of our proposed method using experimental results with real world cellular network bandwidth traces.

Virtual reality and 360-degree video streaming are growing rapidly; however, streaming 360-degree video is very challenging due to high bandwidth requirements. To address this problem, the video quality is adjusted according to the user viewport prediction. High quality video is only streamed for the user viewport, reducing the overall bandwidth consumption. Existing solutions use shallow buffers limited by the accuracy of viewport prediction. Therefore, playback is prone to video freezes which are very destructive for the Quality of Experience (QoE). We propose using layered encoding for 360-degree video to improve QoE by reducing the probability of video freezes and the latency of response to the user head movements. Moreover, this scheme reduces the storage requirements significantly and improves in-network cache performance.

The IEEE 802.11 standards define a distributed scheme for Wi-Fi access points and stations to fairly share the wireless medium. Even if fully standard-compliant, Wi-Fi devices from different vendors have implementation differences that lead to disparities in their ability to access the medium. Erratic upper-layer behaviors become manifest when devices that exhibit such disparities inter-operate within one network. In this paper we show examples of those behaviors based on common use cases. We find that a primary cause of performance inconsistency for most network applications is the uneven ability of different IEEE 802.11 devices to access the shared medium for transmission of TCP acknowledgments, further aggravated by the excessive size of the buffers where those packets are queued before transmission. We devise and validate in a real network an effective solution for Linux hosts that is based on the link-layer priorities of IEEE 802.11e. This solution allows researchers conducting Wi-Fi experiments to collect device-independent results, and application providers to guarantee a consistent experience to their users across different devices.

Network emulation strikes the balance between using real machines on full-fledged networks and running software models of applications and networks in simulation environments. Advanced Linux features make it possible to emulate entire networks on a single machine, enabling experiments that are much easier to run and repeat. However, some of these features were not designed with the primary purpose of supporting emulation frameworks: if not carefully configured, they can lead to erroneous results. In this paper we note a few properties of Linux-based network emulation that researchers should consider while planning their experiments. We also recommend a particular configuration that improves the fidelity of emulation results.

Multipath TCP (MPTCP) is an extension of TCP, developed by Internet Engineering Task Force (IETF) to support communication between source and destination through multiple flows under a single connection session. We have conducted several experiments with real hardware on flows with extreme variation in path quality and found that unless receive buffer size is increased to a much higher value, the overall throughput decreases below the level of single-path TCP throughput. We propose a Slow Path Adaptation (SPA) technique to overcome this issue without affecting other performance parameters. The implementation is done on Linux kernel and experimental results are presented.

Repeatability, isolation and accuracy are the most desired factors while testing wireless devices. However, they cannot be guaranteed by traditional drive tests. Channel emulators play a major role in filling these gaps in testing. In this paper we present an efficient channel emulator which is better than existing commercial products in terms of cost, remote access, support for complex network topologies and scalability. We present the hardware and software architecture of our channel emulator and describe the experiments we conducted to evaluate its performance against a commercial channel emulator.

Deployment of Smart Grid networks throughout cities introduces a realistic scenario for a large scale sensor network. Smart Meters create a wireless mesh network for receiving commands and sending metering reports back to provider company. The challenges of reliable and timely communication call for a fresh review of the well studied topic of Wireless Sensor Networks (WSN). We provide a centralized MAC solution for data collection, ATR-MAC, that relaxes requirements in general purpose WSNs, but emphasizes on difficulties a Smart Metering deployment will face. ATR-MAC considers variable reuse distances for minimizing propagation delay. It also increases efficiency of collection deadline instead of energy efficiency, a common concern of general-purpose WSN MAC protocols. We provide time and buffer size analysis of our algorithm, prove its correctness and show experimental results using implementation on a testbed.

The recent increase in the number of technologies operating in the 2.4GHz ISM band has drawn attention towards the impact they can have on each other. In this paper, we have conducted a case study about coexistence of IEEE 802.11and IEEE 802.15.4 which has led us to discover previously unknown interactions. We have performed experiments using real hardware to evaluate the impact of IEEE 802.11 on IEEE 802.15.4 and vice versa. More importantly, we have identified IEEE 802.11MAC/PHY layer parameters that could be changed in order to improve the performance of coexisting IEEE 802.15.4 nodes. We have also identified the order in which these adjustments should be made.

Recently, IEEE 802.11s has been ratified as an amendment to the IEEE 802.11 standard. It adds the ability to establish a wireless mesh network. The amendment makes provisions for a routing protocol called Hybrid Wireless Mesh Protocol(HWMP). In this paper we study the impact of asymmetric bidirectional links on the performance of HWMP. We show through experiments using real hardware on a test bed and the open 80211s implementation of HWMP that such links significantly impact the performance of the protocol. We describe in detail the cause of decline in performance and attribute it to implementation issues and more importantly the inadequacy of the routing metric. Moreover, we propose solutions to the identified problems, implement those solutions by making modifications to the Linux kernel mac80211 stack and show the achieved performance gains through detailed experiments.

The demand for scalable I/O continues to grow rapidly as computer clusters keep growing. Much of the research in storage systems has been focused on improving the scale and performance of I/O throughput. Scalable file systems do a good job of scaling large file access bandwidth by striping or sharing I/O resources across many servers or disks. However, the same cannot be said about scaling file metadata operation rates. Most existing parallel file systems choose to concentrate all the metadata processing load on a single server. This centralized processing can guarantee the correctness, but it severely hampers scalability. This downside is becoming more and more unacceptable as metadata throughput is critical for large scale applications. Distributing metadata processing load is critical to improve metadata scalability when handling huge number of client nodes. However, a solution to speed up metadata operations has to address two challenges simultaneously, namely the scalability and reliability. In this paper, we have designed a decentralized metadata service layer and evaluated its benefits and shortcomings that concern parallel file systems. The main aim of this service layer is to maintain reliability and consistency in a distributed metadata environment. At the same time we also focus on improving the scalability of the metadata operations, and in turn, the scalability of the underlying parallel file system. As demonstrated by experiments, the approach presented in this paper achieves significant improvements over native parallel file systems by large margin for all the major metadata operations. With 256 client processes, our decentralized metadata service outperforms Lustre and PVFS2 by a factor of 1.9 and 23, respectively, to create directories. With respect to stat() operation on files, our approach is 1.3 and 3.0 times faster than Lustre and PVFS.

In several sensing applications the parameter being sensed exhibits a high spatial correlation. For example, if the temperature of a region is being monitored, there are distinct hot and cold spots. The area close to the hot spots is usually warmer than average, with a temperature gradient between the hot and cold spots. We exploit this correlation of sensor data to form a forest of logical trees, with the trees collectively spanning all the sensor nodes. The root of a tree corresponds to a sensor reporting the local peak value. The tree nodes represent the value gradient: each node's sensed value is smaller than that of its parent, and greater than that of its children. GrAFS provides a mechanism to maintain some information at the local peaks and the sink. Using this information the sink can answer several queries either directly, or by probing the region of the sensor field that holds the answer. Thus, queries can be answered in a time and/or bandwidth efficient manner. The GrAFS approach to data aggregation can easily adapt to changes in the spatial distribution of sensed values, and also cope with message losses and sensor node failures. Implementation on MICA2 motes and simulation experiments conducted using TinyOS quantify the performance of GrAFS.

Data centers are becoming increasingly popular for a wide variety of applications such as search, gaming, email and so on. The complex wiring issues in data centers have motivated us to consider a wireless solution for data centers which meets the design goals of a typical data center network while providing the additional benefit of flexibility in the network. The wireless data center is based on the recently released IEEE 802.15.3c wireless networking standard in the 60 GHz ISM band. The standard supports multi-Gbps data rates and enables the transceivers to set up point-to-point links with each other, which makes it suitable for data center interconnects. In this paper, we use 60 GHz wireless technology to design a wireless data center and show how various data center interconnects such as 3-tier and fat-tree can be emulated on such a wireless network.

Low-latency data delivery is an important requirement for achieving effective monitoring through wireless sensor networks. When sensor nodes employ duty cycling, sending a message along the shortest path, however, does not necessarily result in minimum delay. In this paper, we first study the lowest latency path problem, i.e., the characteristics of a path with minimum delay that connects a source node to the sink under random duty cycling nodes. Then, we propose a forwarding protocol based on biased random walks, where nodes only use local information about neighbors and their next active period to make forwarding decisions. We refer to this as lukewarm potato forwarding. Our analytical model and simulation experiments show that it is possible to reduce path latency without significantly increasing the number of transmissions (energy efficiency) needed to deliver the message to the destination. In particular, although deviating from the shortest path requires additional transmissions, and hence, higher energy consumption, this increase is compensated by a lighter duty cycle. Our experiments show that, overall, we can save up to 15 percent of energy while obtaining the same data delivery delay as shortest path routing. Additionally, the proposed solution is tunable. By changing the value of just one threshold parameter, it can be tuned to operate anywhere in the continuum from hot potato/random walk forwarding protocol to a deterministic shortest path forwarding protocol.

Most researchers conduct wireless networking experiments in their laboratory or similar indoor environments. Such environments are veritable RF jungles, especially when we consider the ISM bands. In this paper we examine and test several common explicit and implicit assumptions that researchers tend to make about the wireless environment. Although these assumptions are acknowledged by most researchers, the extent of their impact is often underestimated. We find that because the environment is always in flux, it is almost impossible to reproduce the results of an experiment. Hence, there is a high risk of misinterpreting the data obtained from such experiments. Through this paper we try to caution experimenters against such risky assumptions when they venture into the RF jungle. After a successful proof-of-concept experiment, we advocate the use of wireless networking testbeds that provide experimenters better control over the RF environment by using coaxial cables, programmable attenuators and power dividers/combiners.

This paper studies the coexistence of several independent and dynamic wireless networks using the frequency hopping technique in the unlicensed radio band. We propose a new hopping scheme that allows more networks to collocate effectively, but does not violate federal restrictions regarding frequency constraint (related to the minimum number of frequencies in a hopping set) and time constraint (related to the maximum duration of using a particular frequency). The coexisting networks follow the Gaussian distribution in choosing transmission frequencies from parallel hopping spaces without the overhead of extra message exchange. Simulation results include comparison with other contemporary approaches and establish the viability of the proposed scheme.

Low latency data delivery is an important requirement for achieving effective monitoring through wireless sensor networks. When sensor nodes employ duty cycling, sending a message along the shortest path, however, does not necessarily result in minimum delay. In this paper we firstly study the lowest latency path problem, i.e., the characteristics of path with mini delay that connect a source node to the sink under random duty cycling nodes. Then, we propose a forwarding protocol based on biased random walks, where nodes only use local information about neighbors and their next active period to make forwarding decisions. We refer to this as lukewarm potato forwarding. Our analytical model and simulation experiments show that it is possible to reduce path latency without significantly increasing the number of transmissions (energy efficiency) needed to deliver the message to the destination. Additionally, the proposed solution is tunable. By changing the value of just one threshold parameter it can be tuned to operate anywhere in the continuum from hot potato/random walk forwarding protocol to a deterministic shortest path forwarding protocol.

Software simulation has often been used to evaluate proposed protocols for wireless devices. Simulation allows for rapid development and testing, but does not provide a realistic RF environment. To compensate for this, field experiments are performed. However, problems encountered during field experiments can be difficult to locate and correcting problems on-site can be time-consuming. Emulations attempt to provide the advantages of simulation and field experiments without the suffering the disadvantages of both. This demo provides an overview of the hardware, software, and emulation capabilities of ASSERT, an emulation testbed.

Most papers addressing consensus in wireless ad hoc networks adopt system models similar to those developed for wired networks. These models are focused towards node failures while ignoring link failures, and thus are poorly suited for wireless ad hoc networks. The recently proposed HO model does not have this drawback. The paper shows that an existing algorithm and the HO model can be used for multi-hop wireless ad hoc networks, if extended with an adequate communication layer. The description of the communication layer is augmented with simulation results that validate the feasibility of our approach and provide better understanding of the behavior of wireless environments.

Cognitive radios (CR) technology enables wireless devices to dynamically switch between channels in a wide range of frequency bands and utilize unused parts of licensed and unlicensed frequency bands. The CR-enabled devices can either form a stand-alone multi-hop wireless network or form a multi-hop wireless backbone network that can connect different types of devices together. In a multi-hop wireless network composed of CR-enabled devices the number and the set of available channels vary from one node to another. This is in contrast to the existing multi-hop wireless mesh networks where all the nodes have the same set of channels available. In this paper we present a CSMA-based MAC protocol for CR-based multihop network. This protocol is based on the channel segregation technique proposed for cellular networks. Simulation results indicate that the protocol incurs low latency and achieves reasonable throughput.

Network wide broadcast is a frequently used operation in ad hoc networks and consumes significant amount of energy. Reducing the overall power consumption is extremely important in increasing the longevity of ad hoc networks. As a result, developing energy efficient broadcast operations becomes an important issue in ad hoc networks. In this paper, we propose an adaptive power broadcast algorithm that uses localized information in ad hoc networks. Our algorithm uses a novel technique to improve energy efficiency in network wide broadcast. Our simulation based comparisons show the superiority of our algorithm compared to other approaches.

Previously proposed analytical studies for IEEE 802.11 Distributed Coordination Function model the behavior of a wireless station operating under saturation conditions as a two-dimensional discrete time Markov chain. In this document, we show that the two-dimensional chain can be partitioned into two one-dimensional chains. Such a partitioning not only simplifies the analysis, but also significantly reduces the number of state variables.

Cognitive radios (CR) have the ability to dynamically adapt to local spectrum availability. In a multi-hop wireless network comprised of CR-enabled devices, medium access control (MAC) layer scheduling for data communication involves assignment of timeslots and channels to either links or nodes in the network. The number of channels available and the channel identities vary from one node to another within the CR network. This is in contrast to the existing use of multiple channels where all the nodes have the same set of channels available (for example in IEEE 802.11 networks). In this paper, we present an integer linear programming (ILP) formulation for the MAC-layer scheduling problem and find an optimal schedule. We also propose a simple and efficient distributed heuristic for MAC-layer scheduling. Simulation results indicate that the proposed distributed heuristic provides near optimal schedule

A Mobile Ad hoc NETwork (MANET) is a group of mobile nodes that form a multihop wireless network. The topology of the network can change randomly due to unpredictable mobility of nodes and propagation characteristics. Previously, it was assumed that the nodes in the network were assigned IP addresses a priori. This may not be feasible as nodes can enter and leave the network dynamically. A dynamic IP address assignment protocol like DHCP requires centralized servers that may not be present in MANETs. Hence, we propose a distributed protocol for dynamic IP address assignment to nodes in MANETs. The proposed solution guarantees unique IP address assignment under a variety of network conditions including message losses, network partitioning and merging. Simulation results show that the protocol incurs low latency and communication overhead for an IP address assignment.

Efficient use of the limited energy available with sensor nodes is an important consideration for routing protocols. In an attempt to improve the lifetime of a sensor network using energy-aware routing, existing protocols might route a packet along a longer path - thus increasing its latency. Many applications of sensor networks, e.g., surveillance and security, require that the maximum latency in routing a packet be bounded. We consider the problem of energy-aware routing with a bound on the maximum number of hops any packet can traverse to reach a base station. We formulate a linear program (LP) to minimize the maximum energy spent by any node in the network subject to a limit on the number of hops any packet may traverse. A solution to the LP yields routing information in terms of the number of packets to be forwarded along each edge; however, non-integral values of the flow variables might require splitting a packet across multiple routes. As packet splitting incurs additional overhead in tracking various fragments, it is desirable to have integral routing information. We, therefore, propose a rounding algorithm based on the minimum cost flow problem and prove that the energy spent by a node in the resulting integral solution is at most a constant more than the optimal LP solution

We consider the problem of link scheduling in a sensor network employing a TDMA MAC protocol. Our link scheduling algorithm involves two phases. In the first phase, we assign a color to each edge in the network such that no two edges incident on the same node are assigned the same color. We propose a distributed edge coloring algorithm that needs at most (/spl delta/+1) colors, where /spl delta/ is the maximum degree of the graph. To the best of our knowledge, this is the first distributed algorithm that can edge color a graph with at most (/spl delta/+1) colors. In the second phase, we map each color to a unique timeslot and attempt to identify a direction of transmission along each edge such that the hidden terminal and the exposed terminal problems are avoided. Next, considering topologies for which a feasible solution does not exist, we obtain a direction of transmission for each edge using additional timeslots, if necessary. Finally, we show that reversing the direction of transmission along every edge leads to another feasible direction of transmission. Using both the transmission assignments we obtain a TDMA MAC schedule, which enables two-way communication between every pair of neighbors. For acyclic topologies, we show that at most 2(/spl delta/+1) timeslots are required. Through simulations we show that for sparse graphs with cycles the number of timeslots assigned is close to 2(/spl delta/+1).

The IEEE 802.11 distributed coordination function (DCF) does not require the presence of a central controller (access point). It is based on carrier sense multiple access with collision avoidance and binary exponential backoff. Under saturation conditions, DCF operates very far from the theoretical limit. Enhancements to the DCF scheme to achieve the theoretical limit (Cali, F. et al., 1998; Qiang Ni et al., 2003) have drawbacks. We present an adaptive DCF (ADCF) scheme that adapts its backoff procedure based on such knowledge. Through simulation experiments, we compare the performance of ADCF with that of DCF and the slow contention window decrease (SD) scheme of Qiang Ni et al. Under saturation conditions, we observe that both DCF and SD operate far from the theoretical throughput limit due to their inability to negotiate contention for the medium quickly. By making use of the additional knowledge, the proposed ADCF scheme operates closer to the theoretical limit. For example, when DCF and SD operate 35% and 20%, respectively, below the theoretical throughput limit, ADCF operates only 10% below the theoretical limit. Moreover, by recording the channel state information observed during the recent past, ADCF is able to respond better to variations in the offered traffic.

With advances in physical layer technologies, WLANs are now connected with wired networks and act as parts of the entire networks. Since demands for QoS sensitive applications are extremely high, WLANs, as parts of heterogeneous networks, are required to be QoS-aware. In this paper we present a new QoS-aware multi-access scheme, called ADCF, designed to assure weighted fair queuing in a purely distributed way and to achieve admission control per frame. The results of simulations show that ADCF yields stable weighted fair queuing with consistent performance under most conditions. In most cases, ADCF outperforms DCF of IEEE 802.11 and EDCF of IEEE 802.11e. Also, ADCF guarantees starvation free channel access for a low priority flow.

Sensor networks consist of a large number of sensor nodes performing distributed sensing and event detection. As sensor nodes are energy-constrained, energy-efficient routing is essential for increasing the lifetime of a sensor network. In Gandham, SR et al. (2003), we proposed an ILP-based method for routing in sensor networks with multiple mobile base stations. The ILP-based method does not guarantee integral routes and bounds on running time. In this paper, we consider static base stations and propose an algorithmic approach to obtain integral energy-efficient routes. We propose to split the lifetime of a sensor network into equal periods of time referred to as rounds and model the energy constrained routing during a round as polynomial-time solvable flow problems. The flow information from an optimum solution to a flow problem is then used as a basis for an energy-efficient routing protocol. Through simulations, we demonstrate that our routing algorithm performs significantly better than the shortest path based algorithms and consumes less energy than the ILP-based method. In addition, we present an algorithm to determine, a priori, lower bound on the lifetime of the sensor network.

In this paper, we study the two medium access control (MAC) sublayer policies, namely, schedule after backoff (SAB) and schedule before backoff (SBB), which offer differentiated services in IEEE 802.11-based wireless networks. Both policies control channel access based on frame priorities. In the SAB policy, each node maintains concurrent backoff instances (one per priority class) with different parameter values to realize service differentiation. High-priority data frames use a shorter contention window, so that, in most cases, they are transmitted before the low-priority ones. The enhanced distributed coordination function (EDCF) scheme specified in the upcoming IEEE 802.11e standard is based on the SAB policy. Recent studies [A. Lindgren et al., June 2003] have shown that under high loads of high-priority traffic, EDCT starves low-priority frames. We propose SBB policy, which provides service differentiation without the need for maintaining concurrent backoff instances. In SBB, frame transmission proceeds in two sequential steps: (i) selecting the next frame to be transmitted, and (ii) channel access functionality until the selected frame is either successfully transmitted or its number of retransmissions exceeds the retry limit. These two steps are independent and can be performed using several alternatives. Depending on the way the two steps are carried out, we present four SBB-based MAC schemes. We evaluate SAB and SBB-based MAC schemes through simulation experiments. Our simulation results show that the SBB policy does not starve low-priority traffic and offers differentiated service on par with SAB. This suggests that maintenance of concurrent backoff instances contributes little towards performance improvement.

One of the main design issues for a sensor network is conservation of the energy available at each sensor node. We propose to deploy multiple, mobile base stations to prolong the lifetime of the sensor network. We split the lifetime of the sensor network into equal periods of time known as rounds. Base stations are relocated at the start of a round. Our method uses an integer linear program to determine new locations for the base stations and a flow-based routing protocol to ensure energy efficient routing during each round. We propose four metrics and evaluate our solution using these metrics. Based on the simulation results we show that employing multiple, mobile base stations in accordance with the solution given by our schemes would significantly increase the lifetime of the sensor network.

This paper describes a distributed algorithm for reliable multicast in mobile cellular networks. In the proposed solution the multicast message is flooded to all the base stations over reliable channels. The base stations then collectively ensure that all mobile nodes belonging to the multicast group get the message. The originality of our solution is that it is fully decentralized. Each base station can independently decide when to flush a message from its buffer. Even if a node moves from one cell to another while a multicast is in progress, delivery of the message to the node is guaranteed. Simulation experiments show that using the proposed solution, memory requirements at the base stations are significantly smaller than by using centralized solutions.

Mobile ad hoc networks consist of mobile nodes communicating with each other without the presence of any fixed network infrastructure. Existing mechanisms for cluster formation, e.g. node-id based, and degree based, focus on a particular characteristic of the network. The authors have presented earlier a unified mechanism for cluster formation, which not only encompasses existing mechanisms, but also provides means to explore new mechanisms. Two key parameters of this unified mechanism are: availability factor threshold, a/sub TH/, and clustering gap, /spl Delta/g, i.e., the time between two consecutive clustering decisions. We present the results of the experiments conducted to observe the effect of these two key parameters on the performance of clustering mechanisms. We also present a new performance metric, the unserviced index, which indicates the number of nodes not serviced by any clusterhead at a given time.

A mobile ad hoc network (MANET) is a multi-hop wireless network capable of autonomous operation. The mobility of MANET nodes can lead to frequent and unpredictable topology changes. Most MANET literature assumes that network related information of a node (such as its IP address, netmask, etc.) is configured statically, prior to the node joining the MANET. However, not all nodes have IP addresses permanently assigned to them. Such nodes rely on a centralized server and use a dynamic host configuration protocol, like DHCP (dynamic host configuration protocol), to acquire an IP address. Such a solution cannot be employed in MANETs due to the unavailability of any centralized DHCP server. In this paper, we first present a survey of possible solutions approaches, and discuss their limitations. Then, we present a distributed dynamic host configuration protocol designed to configure nodes in a MANET. We show that the proposed protocol works correctly and does not have the limitations of earlier approaches. Finally, we evaluate the performance of the solution through simulation experiments, and conclude with a discussion of related security issues.

Most of the routing protocols proposed for mobile ad hoc networks (MANETs) rely on caching routes to increase the speed and reduce the cost of route discovery. These protocols assume high path stability between the mobile nodes in the network. This paper studies persistence of paths under various mobility patterns and network sizes. The conclusions drawn from this study enable us to determine the effectiveness of caching and also to suggest suitable caching durations. The simulation experiments indicate that path persistence declines with increasing network density and diameter. Restricting the motion of nodes increases path persistence while also increasing network partitioning. Hence, caching of routes in mobile ad hoc networks appears to have serious scalability problems.

Mobile ad hoc networks (MANETs) consist of a set of similar mobile nodes, communicating with each other using wireless links. As a node may not be able to directly reach every other node, a packet may need to traverse multiple wireless links from its source to its destination. Unidirectional links can occur in such networks. Several existing routing protocols implicitly assume bidirectional links when making their routing decisions. Not using unidirectional links can lead to sub-optimal routes. A tunneling solution to allow efficient operation in ad hoc networks with unidirectional links is presented. The tunneling solution uses information gathered by the routing protocol to tunnel packets from the end-point of the unidirectional link to its source. A naive implementation of tunneling could lead to loops in the system and a deluge of packets. This is because when ACKs (acknowledgments) for link layer messages are tunneled across unidirectional links, ACKs for them may end up being generated recursively. The solution presented here prevents such a packet explosion from occurring.

An ad hoc network may be logically represented as a set of clusters. The clusterheads form a d-hop dominating set. Each node is at most d hops from a clusterhead. Clusterheads form a virtual backbone and may be used to route packets for nodes in their cluster. Previous heuristics restricted themselves to 1-hop clusters. We show that the minimum d-hop dominating set problem is NP-complete. Then we present a heuristic to form d-clusters in a wireless ad hoc network. Nodes are assumed to have a non-deterministic mobility pattern. Clusters are formed by diffusing node identities along the wireless links. When the heuristic terminates, a node either becomes a clusterhead, or is at most d wireless hops away from its clusterhead. The value of d is a parameter of the heuristic. The heuristic can be run either at regular intervals, or whenever the network configuration changes. One of the features of the heuristic is that it tends to re-elect existing clusterheads even when the network configuration changes. This helps to reduce the communication overheads during transition from old clusterheads to new clusterheads. Also, there is a tendency to evenly distribute the mobile nodes among the clusterheads, and evently distribute the responsibility of acting as clusterheads among all nodes. Thus, the heuristic is fair and stable. Simulation experiments demonstrate that the proposed heuristic is better than the two earlier heuristics, namely the LCA and degree-based solutions.

A mobile computing system with no fixed nodes is presented. In traditional cellular systems with fixed base stations the channel reuse pattern is static and deterministic. When the cell layout is dynamic, due to the mobility of base stations, the cluster of cells within co-channel interference range changes with time. Consequently, the channel reuse pattern is highly dynamic, Moreover, base stations also need wireless channels to communicate amongst themselves. A communication session between a pair of nodes may have to switch channels due to the movement of other nodes into the neighborhood. Hence, there is a need for new wireless channel allocation algorithms for virtual cellular systems with mobile base stations. In this paper, principles of mutual exclusion pertaining to distributed computing systems are employed to develop such an algorithm. The inter-base station wireless links are referred to as backbone links while the base station-mobile node links are referred to as short-hop links. The proposed algorithm is distributed, dynamic and deadlock free. Disjoint sets of channels are used for backbone and short-hop links. The distributed nature of the channel allocation scheme leads to robustness as the responsibility is no longer centralized at the MTSO. Instead, it is shared among all the mobile base stations. This also makes the algorithm scalable.

Ad-hoc wireless networks have no wired component, and may have unpredictable mobility pattern. Such networks can get partitioned and reconnected several times. One possible approach for information dissemination in such networks is to replicate information at multiple nodes acting as repositories, and employ quorum based strategies to update and query information. We propose three such strategies that also use local knowledge about the reachability of repositories to judiciously select quorums. The primary goal is high availability of information in the face of network partitioning. We also consider four policies to determine the appropriate time to perform updates. Experimental results indicate that a hybrid information management strategy and an absolute connectivity-based update trigger policy are most suited for partitionable ad-hoc networks.

Wireless ad-hoc networks consist of a set of identical mobile nodes that communicate with each other over limited range wireless links. These wireless links are lossy due to noise and co-channel interference. Moreover, node mobility can lead to establishment of new links and disappearance of some existing links. Current implementations of TCP are not suitably equipped to operate in ad-hoc networks. Loss of packets due to path disruption can be misinterpreted as congestion. We propose to introduce modifications to TCP such that it can work for these kind of dynamic networks. These modifications will exploit the mobility support in the underlying routing protocol. The information provided by the routing protocol can be used to send explicit freeze and resume signals to the TCP source on link disruption and restoration. The proposed solutions can inter-operate with existing TCP implementations, have low communication overheads and are consistent with various ad-hoc network routing protocols.

Ad-hoc networks are completely wireless networks of mobile hosts, in which the topology rapidly changes due to the movement of mobile hosts. This frequent topology may lead to sudden packet losses and delays. Transport protocols like TCP have been built mainly for reliable, fixed networks. Hence, when used in ad-hoc networks, TCP misinterprets this loss as congestion and invokes congestion control. This leads to unnecessary retransmissions and loss of throughput. To overcome this problem, a feedback scheme is proposed, so that the source can distinguish between route failure and network congestion. When a route is disrupted, the source is sent a route failure notification (RFN) packet, allowing it to freeze its timers and stop sending packets. When the route is re-established, the source is informed through a route re-establishment notification (RRN) packet, upon which it resumes by unfreezing timers and continuing packet transmissions. The simulated performance of TCP on ad-hoc networks with and without feedback is compared and reported. It is observed that in the event of route failures, as the route re-establishment time increases, the use of feedback provides significant gains in throughput as well as savings in unnecessary packet transmissions. Several further enhancements and directions for future work are also sketched.

In mobile computing systems the network configuration changes due to node mobility. The paper identifies the issues a group communication service has to take into account in order to handle node mobility. These include the need to identify the location of a node, and the ability to cope with inaccuracies in the determination of a group membership. A multi level architecture for group communication in mobile systems is presented. This architecture contains a synchronous proximity layer protocol to determine the set of mobile nodes in the proximity of a given node in the network. This information is used by a three round group membership protocol for construction of groups used by mobile applications. As an example, the architecture is specialized to solve the channel allocation problem.

Communication protocols designed for database applications are not necessarily suitable for other applications, like multimedia communication, due to the former's requirement of reliable and ordered communication, and the latter's ability to withstand occasional losses and misordering of messages as long as real-time communication can be supported. This paper presents the slotted-FIFO communication mode that supports communication primitives for the entire spectrum of reliability and ordering requirements of distributed applications: for example, FIFO as well as non-FIFO, and reliable as well as unreliable communication. It provides communication with a run-time variable degree of reliability and/or ordering. Hence, the slotted-FIFO communication mode is suitable for applications that can work with relaxed reliability and/or ordering constraints such as multimedia applications. The protocol is simple and has low overheads. As FIFO ordering is not required for all messages, message buffering requirements are considerably reduced. Also, message latencies are lower. We demonstrate such advantages by means of a simulation study. A low overhead protocol implementing slotted-FIFO communication is also presented. The protocol incurs a small resequencing cost.

This paper presents the slotted-FIFO communication mode that supports communication primitives for the entire spectrum of reliability and ordering requirements of distributed applications: FIFO as well as non-FIFO, and reliable as well as unreliable communication. Hence, the slotted-FIFO communication mode is suitable for multimedia applications, as well as non real-time distributed applications. As FIFO ordering is not required for all messages, message buffering requirements are considerably reduced. Also, message latencies are lower. We quantify such advantages by means of a simulation study. A low overhead protocol implementing slotted-FIFO communication is also presented. The protocol incurs a small resequencing cost.

No abstract available.

Causal message ordering is required for several distributed applications. In order to preserve causal ordering, only direct dependency information between messages, with respect to the destination process(es), need be sent with each message. By eliminating other kinds of control information from the messages, the communication overheads can be significantly reduced. In this paper we present an algorithm that uses this knowledge to efficiently enforce causal ordering of messages. The proposed algorithm does not require any prior knowledge of the network topology or communication pattern. As computation proceeds, it acquires knowledge of the communication pattern and is capable of handling dynamically changing multicast communication groups, and minimizing the communication overheads. With regard to communication overheads, the algorithm is optimal for the broadcast communication case. Extensive simulation experiments demonstrate that the algorithm imposes lower communication overheads than previous causal ordering algorithms. The algorithm can be employed in a variety of distributed computing environments. Its energy efficiency and low bandwidth requirement make it especially suitable for mobile computing systems. We show how to employ the algorithm for causally ordered multicasting of messages in mobile computing environments.

Causal message ordering is required for several distributed applications. In order to preserve causal ordering, only direct dependency information between messages with respect to the destination process(es) should be sent with each message. By eliminating other kinds of control information from the messages, the communication overheads can be significantly reduced. In this paper we present an algorithm that uses this knowledge to efficiently enforce causal ordering of messages. The proposed algorithm does not require any prior knowledge of the network or communication topology. As computation proceeds, it acquires knowledge of the logical communication topology and is capable of handling dynamically changing multicast communication groups. With regard to communication overheads, the algorithm is optimal for the broadcast communication case. Its energy efficiency and four bandwidth requirement make it suitable for mobile computing systems. We present a strategy that employs the algorithm for causally ordered multicasting of messages in mobile computing environments.

Mobile computers use wireless channels to communicate with other computers. The finite number of channels should be efficiently allocated to maximize throughput and to avoid co-channel interference. Temporal variations in, channel demand (load) require channel allocation to adapt dynamically to the changing demand. The presence of load imbalance does not automatically imply the usefulness of channel transfer. In this paper we present a probabilistic analysis of the temporal imbalance in channel demand. The effectiveness of channel transfer decisions depends on the probability distribution of the duration for which the imbalance persists. The results of our analysis provide guidelines for the design of dynamic distributed channel allocation strategies.

No abstract available.

A mobile computing system consists of mobile and stationary nodes, connected to each other by a communication network. The presence of mobile nodes in the system places constraints on the permissible energy consumption and available communication bandwidth. To minimize the lost computation during recovery from node failures, periodic collection of a consistent snapshot of the system (checkpoint) is required. Locating mobile nodes contributes to the checkpointing and recovery costs. Synchronous snapshot collection algorithms, designed for static networks, either force every node in the system to take a new local snapshot, or block the underlying computation during snapshot collection. Hence, they are not suitable for mobile computing systems. If nodes take their local checkpoints independently in an uncoordinated manner, each node may have to store multiple local checkpoints in stable storage. This is not suitable for mobile nodes as they have small memory. This paper presents a synchronous snapshot collection algorithm for mobile systems that neither forces every node to take a local snapshot, nor blocks the underlying computation during snapshot collection. If a node initiates snapshot collection, local snapshots of only those nodes that have directly or transitively affected the initiator since their last snapshots need to be taken. We prove that the global snapshot collection terminates within a finite time of its invocation and the collected global snapshot is consistent. We also propose a minimal rollback/recovery algorithm in which the computation at a node is rolled back only if it depends on operations that have been undone due to the failure of node(s). Both the algorithms have low communication and storage overheads and meet the low energy consumption and low bandwidth constraints of mobile computing systems.

Efficient allocation of communication channels is critical for the performance of wireless mobile computing systems.The centralized channel allocation algorithms proposed in literature are neither robust, nor scalable.Distributed channel allocation schemes proposed in the past are complicated and require active participation of the mobile nodes.These algorithms are unable to dynamically adjust to spatial and temporal fluctuations in channel demand.We present a dynamic distributed channel allocation algorithm that can quickly adapt to changes in load distribution.The algorithm described in this paper requires minimal involvement of the mobile nodes, thus conserving their limited energy supply.The algorithm is proved to be deadlock free, starvation free and fair.It prevents co-channel interference and is scalable.