In this paper, we revisit the problem of multi-party conferencing from a practical perspective, and to rethink the design space involved in this problem. We believe that an emphasis on low end-to-end delays between any two parties in the conference is a must, and the source sending rate in a session should adapt to bandwidth availability and congestion. We present Celerity, a multi-party conferencing solution specifically designed to achieve our objectives. It is entirely Peer-to-Peer (P2P), and as such eliminating the cost of maintaining centrally administered servers. It is designed to deliver video with low end-to-end delays, at quality levels commensurate with available network resources over arbitrary network topologies where bottlenecks can be anywhere in the network. This is in contrast to commonly assumed P2P scenarios where bandwidth bottlenecks reside only at the edge of the network. The highlight in our design is a distributed and adaptive rate control protocol, that can discover and adapt to arbitrary topologies and network conditions quickly, converging to efficient link rate allocations allowed by the underlying network. In accordance with adaptive link rate control, source video encoding rates are also dynamically controlled to optimize video quality in arbitrary and unpredictable network conditions. We have implemented Celerity in a prototype system, and demonstrate its superior performance over existing solutions in a local experimental testbed and over the Internet.

In this paper, we attempt to revisit the problem of multi-party conferencing from a practical perspective, and to rethink the design space involved in this problem. We believe that an emphasis on low end-to-end delays between any two parties in the conference is a must, and the source sending rate in a session should adapt to bandwidth availability and congestion. We present Celerity, a multi-party conferencing solution specifically designed to achieve our objectives. It is entirely Peer-to-Peer (P2P), and as such eliminating the cost of maintaining centrally administered servers. It is designed to deliver video with low end-to-end delays, at quality levels commensurate with available network resources over arbitrary network topologies where bottlenecks can be anywhere in the network. This is in contrast to commonly assumed P2P scenarios where bandwidth bottlenecks reside only at the edge of the network. The highlight in our design is a distributed and adaptive rate control protocol, that can discover and adapt to arbitrary topologies and network conditions quickly, converging to efficient link rate allocations allowed by the underlying network. In accordance with adaptive link rate control, source video encoding rates are also dynamically controlled to optimize video quality. We have implemented Celerity in a prototype system, and demonstrate its superior performance over existing solutions in a local experimental testbed and over the Internet.

In this paper, we attempt to revisit the problem of multi-party conferencing from a practical perspective, and to rethink the design space involved in this problem. We believe that an emphasis on low end-to-end delays between any two parties in the conference is a must, and the source sending rate in a session should adapt to bandwidth availability and congestion. We present Celerity, a multi-party conferencing solution specifically designed to achieve our objectives. It is entirely Peer-to-Peer (P2P), and as such eliminating the cost of maintaining centrally administered servers. It is designed to deliver video with low end-to-end delays, at quality levels commensurate with available network resources over arbitrary network topologies where bottlenecks can be anywhere in the network. This is in contrast to commonly assumed P2P scenarios where bandwidth bottlenecks reside only at the edge of the network. The highlight in our design is a distributed and adaptive rate control protocol, that can discover and adapt to arbitrary topologies and network conditions quickly, converging to efficient link rate allocations allowed by the underlying network. In accordance with adaptive link rate control, source video encoding rates are also dynamically controlled to present the best possible video quality in arbitrary and unpredictable network conditions. We have implemented Celerity in a prototype system and demonstrate its superior performance in a local experimental testbed.

Distributed storage systems often introduce redundancy to increase reliability. When coding is used, the repair problem arises: if a node storing encoded information fails, in order to maintain the same level of reliability we need to create encoded information at a new node. This amounts to a partial recovery of the code, whereas conventional erasure coding focuses on the complete recovery of the information from a subset of encoded packets. The consideration of the repair network traffic gives rise to new design challenges. Recently, network coding techniques have been instrumental in addressing these challenges, establishing that maintenance bandwidth can be reduced by orders of magnitude compared to standard erasure codes. This paper provides an overview of the research results on this topic.

In a distributed storage system based on erasure coding, an important problem is the repair problem: If a node storing a coded piece fails, in order to maintain the same level of reliability, we need to create a new encoded piece and store it at a new node. This paper presents a construction of systematic (n,k)-MDS codes for 2k ≤ n that achieves the minimum repair bandwidth when repairing from k+1 nodes.

A write-once memory (wom) is a storage medium formed by a number of “write-once” bit positions (wits), where each wit initially is in a “0” state and can be changed to a “1” state irreversibly. Examples of write-once memories include SLC flash memories and optical disks. This paper presents a low complexity coding scheme for rewriting such write-once memories, which is applicable to general problem configurations. The proposed scheme is called the position modulation code, as it uses the positions of the zero symbols to encode some information. The proposed technique can achieve code rates higher than state-of-the-art practical solutions for some configurations. For instance, there is a position modulation code that can write 56 bits 10 times on 278 wits, achieving rate 2.01. In addition, the position modulation code is shown to achieve a rate at least half of the optimal rate.

A write-once memory (wom) is a storage medium formed by a number of “write-once” binary cells, where each cell initially is in a `0' state and can be changed to a `1' state irreversibly. Examples of write-once memories include SLC flash memories and optical disks. This paper presents some low complexity codes for writing such write-once memories twice.

In a distributed storage system based on erasure coding, when a storage node fails, repairing the erasure code incurs some network traffic. Previous work has characterized the fundamental tradeoff between storage efficiency and repair network bandwidth. This was done via a cut-based analysis on a graph that models the evolution of information flow in the storage system subject to arbitrary sequences of node failures/repairs. This paper presents techniques for constructing network codes that achieve the optimal tradeoff between storage efficiency and repair network bandwidth. The challenge here is that network coding is applied over an unbounded graph with an unbounded number of receivers. It is shown in this paper that optimal codes can be constructed over a finite field whose size depends only on the maximum number of nodes at any instant, but independent of how many failures/repairs can happen. Key to the code construction is a "path-weaving" procedure that leads to inductive existence proof and code construction.

Significant progress has been made toward a fundamental understanding and practical developments of network coding. There still exists tremendous potential for the theory of network coding to affect the design of next-generation network protocols.

Distributed storage systems provide reliable access to data through redundancy spread over individually unreliable nodes. Application scenarios include data centers, peer-to-peer storage systems, and storage in wireless networks. Storing data using an erasure code, in fragments spread across nodes, requires less redundancy than simple replication for the same level of reliability. However, since fragments must be periodically replaced as nodes fail, a key question is how to generate encoded fragments in a distributed way while transferring as little data as possible across the network. For an erasure coded system, a common practice to repair from a single node failure is for a new node to reconstruct the whole encoded data object to generate just one encoded block. We show that this procedure is sub-optimal. We introduce the notion of regenerating codes, which allow a new node to communicatefunctionsof the stored data from the surviving nodes. We show that regenerating codes can significantly reduce the repair bandwidth. Further, we show that there is a fundamental tradeoff between storage and repair bandwidth which we theoretically characterize using flow arguments on an appropriately constructed graph. By invoking constructive results in network coding, we introduce regenerating codes that can achieve any point in this optimal tradeoff.

In a distributed storage system based on erasure coding, when a storage node fails, repairing the erasure code incurs some network traffic. Previous work has characterized the fundamental tradeoff between storage efficiency and repair network bandwidth. This was done via a cut-based analysis on a graph that models the evolution of information flow in the storage system subject to arbitrary sequences of node failures/repairs. This paper presents techniques for constructing network codes that achieve the optimal tradeoff between storage efficiency and repair network bandwidth. The challenge here is that network coding is applied over an unbounded graph with an unbounded number of receivers. It is shown in this paper that optimal codes can be constructed over a finite field whose size depends only on the maximum number of nodes at any instant, but independent of how many failures/repairs can happen. Key to the code construction is a ldquopath-weavingrdquo procedure that leads to an inductive existence proof/code construction.

We consider the problem of recovering from a single node failure in a storage system based on an (n, k) MDS code. In such a scenario, a straightforward solution is to perform a complete decoding, even though the data to be recovered only amount to 1/kth of the entire data. This paper presents techniques that can reduce the network traffic incurred. The techniques perform algebraic alignment so that the effective dimension of unwanted information is reduced.

Motivated by P2P file transfer applications (e.g., BitTorrent) on the Internet, this paper considers the problem of delivering a file from a server to multiple receivers in a P2P network. Each receiver has an associated delay in receiving the file. We aim at understanding the optimal delay region, i.e., the set of all possible delay vectors that can be achieved. Previous work has addressed the problem of delivering the file to all receivers in minimum amount of time (equivalently, minimizing the maximum delay to the receivers), assuming peer uplinks are the only bottleneck in the network. This paper shows that it is in fact possible to significantly reduce the average delay at a slight increase in the maximum delay. Moreover, given an order at which the receivers finish downloading, the optimal delay region is characterized by a system of linear inequalities. Any point in the optimal delay region can be achieved by linear network coding. We also propose a simple routing scheme that has near-optimal empirical performance.

This paper considers the problem of communicating correlated information from multiple source nodes over a network of noiseless channels to multiple destination nodes, where each destination node wants to recover all sources. The problem involves a joint consideration of distributed compression and network information relaying. Although the optimal rate region has been theoretically characterized, it was not clear how to design practical communication schemes with low complexity. This work provides a partial solution to this problem by proposing a low-complexity scheme for the special case with two sources whose correlation is characterized by a binary symmetric channel. Our scheme is based on a careful combination of linear syndrome-based Slepian-Wolf coding and random linear mixing (network coding). It is in general suboptimal; however, its low complexity and robustness to network dynamics make it suitable for practical implementation.

Traditionally, the channelization structure in IEEE 802.11-based wireless LANs has been fixed: Each access point (AP) is assigned one channel and all channels are equally wide. In contrast, it has recently been shown that even on commodity hardware, the channel-width can be adapted dynamically purely in software. Leveraging this capability, we study the use of dynamic-width channels, where every AP adaptively adjusts not only its center-frequency, but also its channel-width to match its traffic load. This gives raise to a novel optimization problem that differs from previously studied channel assignment problems. We propose efficient spectrum-distribution algorithms and evaluate their effectiveness through analysis and simulations using real-world traces. Our results indicate that by allocating more spectrum to highly-loaded APs, the overall spectrum-utilization can be substantially improved and the notorious load-balancing problem in WLANs can be solved naturally.

Routing protocols have traditionally been based on finding shortest paths under certain cost metrics. A conventional routing metric models the cost of a path as the sum of the costs on the constituting links. This paper introduces the concept of a Markovian metric, which models the cost of a path as the cost of the first hop plus the cost of the second hop conditioned on the first hop, and so on. The notion of the Markovian metric is fairly general. It is potentially applicable to scenarios where the cost of sending a packet (or a stream of packets) over a link may depend on the previous hop of the packet (or the stream). Such scenario arises, for instance, in a wireless mesh network equipped with local mixing, a recent link layer advance. This scenario is examined as a case study for the Markovian metric. The local mixing engine sits between the routing and MAC layers. It maintains information about the packets each neighbor has, and identifies opportunities to mix the outgoing packets via network coding to reduce the transmissions in the air. We use a Markovian metric to model the reduction of channel resource consumption due to local mixing. This leads to routing decisions that can better take advantage of local mixing. We have implemented a system that incorporates local mixing and source routing using a Markovian metric in Qualnet. The experimental results demonstrate significant throughput gain and resource saving.

We consider the multi-source network coding problem in cyclic networks. This problem involves several difficulties not found in acyclic networks, due to additional causality requirements. This paper highlights the difficulty of these causality conditions by analyzing two example cyclic networks which are structurally similar. Both networks have an essentially identical network code which appears to transmit all information from the sources to the sinks; however, this network code is invalid since it violates causality. We show that, in one of the networks, the invalid code can be modified to obey causality, whereas in the other network this is impossible. This unachievability result is proven by a new information inequality for causal coding schemes in a simple cyclic network.

A new broadcasting problem that generalizes the conventional broadcast channel is formulated. This new problem models that a receiver may know some messages destined for other receivers a priori. Such scenarios can naturally arise in a practical wireless network. For the case when there are two receivers and the channel is additive white Gaussian, the capacity region of this generalized broadcasting problem is determined.

A number of studies have shown the abundance of unused spectrum in the TV bands. This is in stark contrast to the overcrowding of wireless devices in the ISM bands. A recent trend to alleviate this disparity is the design of Cognitive Radios, which constantly sense the spectrum and opportunistically utilize unused frequencies in the TV bands. A key challenge in the design of such networks is that of Spectrum Allocation, which enables nodes to reserve chunks of the spectrum for certain periods of time. In this paper, we introduce the concept of a time-spectrum block to model spectrum reservation, and use it to present a theoretical formalization of the spectrum allocation problem. We also present a centralized and a distributed protocol for spectrum allocation and show that these protocols are close to optimal in most scenarios. We have implemented the distributed protocol in QualNet and show that our analysis closely matches the simulation results.

Previous studies have proposed a practical network coding scheme for multicasting information in packet networks, which buffers received packets and outputs random linear mixtures of packets in the buffer. To analyze the performance of such a scheme, this paper introduces a continuous-time trellis, which models the packet transmissions in a practical asynchronous network. The continuous-time trellis represents an extension of a discrete-time trellis that was used in prior theoretical studies to model a synchronized network. The asymptotic throughput of the practical network coding scheme is characterized via an analysis of the asymptotic s-T connectivity in the trellis

The multi-source network coding problem, where multiple multicast sessions with independent data share a network, is an open challenge. It is observed that random mixing is asymptotically optimal for a pollution-free multi-source network coding problem, where no receiver can be reached by a source it does not need. To handle pollution in a general network, a pollution-free network of tagged pipes is constructed. Each link is partitioned into tagged pipes; each tag is a subset of the sources. The content flowing in each pipe can only be a function of the sources indicated in the tag. The pipes are interconnected to form a pollution-free network. This constructive scheme gives rise to an achievability theorem for general multi-source network coding. For acyclic graphs, the fact that decoded information can be used in generating output is modelled via "helpers". This results in a stronger achievability theorem for acyclic graphs. Further incorporating the degree of freedom in adding receivers, an even stronger achievability theorem is derived

One central issue in practically deploying network coding is the adaptive and economic allocation of network resource. We cast this as an optimization, where the net-utility-the difference between a utility derived from the attainable multicast throughput and the total cost of resource provisioning-is maximized. By employing the MAX of flows characterization of the admissible rate region for multicasting, this paper gives a novel reformulation of the optimization problem, which has a separable structure. The Lagrangian relaxation method is applied to decompose the problem into subproblems involving one destination each. Our specific formulation of the primal problem results in two key properties. First, the resulting subproblem after decomposition amounts to the problem of finding a shortest path from the source to each destination. Second, assuming the net-utility function is strictly concave, our proposed method enables a near-optimal primal variable to be uniquely recovered from a near-optimal dual variable. A numerical robustness analysis of the primal recovery method is also conducted. For ill-conditioned problems that arise, for instance, when the cost functions are linear, we propose to use the proximal method, which solves a sequence of well-conditioned problems obtained from the original problem by adding quadratic regularization terms. Furthermore, the simulation results confirm the numerical robustness of the proposed algorithms. Finally, the proximal method and the dual subgradient method can be naturally extended to provide an effective solution for applications with multiple multicast sessions.

Given a network of lossless links with rate constraints, a source node, and a set of destination nodes, the multicast capacity is the maximum rate at which the source can transfer common information to the destinations. The multicast capacity cannot exceed the capacity of any cut separating the source from a destination; the minimum of the cut capacities is called the cut bound. A fundamental theorem in graph theory by Edmonds established that if all nodes other than the source are destinations, the cut bound can be achieved by routing. In general, however, the cut bound cannot be achieved by routing. Ahlswede et al. established that the cut bound can be achieved by performing network coding, which generalizes routing by allowing information to be mixed. This paper presents a unifying theorem that includes Edmonds' theorem and Ahlswede et al.'s theorem as special cases. Specifically, it shows that the multicast capacity can still be achieved even if information mixing is only allowed on edges entering relay nodes. This unifying theorem is established via a graph theoretic hardwiring theorem, together with the network coding theorems for multicasting. The proof of the hardwiring theorem implies a new proof of Edmonds' theorem.

Network coding generalizes the conventional routing paradigm by allowing nodes to mix information received on its incoming links to generate information to be transmitted to other nodes. As a result, network coding improves throughput, resource efficiency, robustness, manageability, etc., in wired and wireless ad hoc networks. In particular, it was established that network coding can achieve the maximum rate for multicasting information from a source node to multiple destination nodes. The objective of this work is to show how to achieve the aforementioned multicast capacity with lower processing/implementation complexity than that proposed in the literature. We classify the links in a network into two categories: 1) links entering relay nodes; and 2) links entering destinations. We show the same multicast capacity can be achieved by applying (non-trivial) network coding only on the links entering relay nodes. In other words, links entering destinations only require routing, which leads to a saving in the complexity. The novelty of this work lies in a new algorithm, its proof of correctness, and a complexity analysis.

Given a wireless ad hoc network and an end-to-end traffic pattern, the power rate function refers to the minimum total power required to support different throughput under a layered model of wireless networks. A critical notion of the layered model is the realizable graphs, which describe possible hit-rate supplies on the links by the physical and medium access layers. Under the layered model, the problem of finding the power rate function can he transformed into finding the minimum-power realizable graph that can provide a given throughput. We introduce a usage conflict graph to represent the conflicts among different uses of the wireless medium. Testing the realizability of a given graph can be transformed into finding the (vertex) chromatic number, i.e., the minimum number of colors required in a proper vertex-coloring, of the associated usage conflict graph. Based on an upper bound of the chromatic number, we propose a linear program that outputs an upper bound of the power rate function. A lower bound of the chromatic number is the clique number. We propose a systematic way of identifying cliques based on a geometric analysis of the space sharing among active links. This leads to another linear program, which yields a lower bound of the power rate function. We further apply greedy vertex-coloring to fine tune the bounds. Simulations results demonstrate that the obtained bounds are tight in the low power and low rate regime.

In this paper, the network planning problem in wireless ad hoc networks is formulated as the problem of allocating physical and medium access layer resources or supplies to minimize a cost function, while fulfilling certain end-to-end communication demands, which are given as a collection of multicast sessions with desired transmission rates. We propose an iterative cross-layer optimization, which alternates between: 1) jointly optimizing the timesharing in the medium access layer and the sum of max of flows assignment in the network layer and 2) updating the operational states in the physical layer. We consider two objectives, minimizing aggregate congestion and minimizing power consumption, respectively, corresponding to operating in a bandwidth-limited regime and in an energy-limited regime. The end result is a set of achievable tradeoffs between throughput and energy efficiency, in a given wireless network with a given traffic pattern. We evaluate our approach quantitatively by simulations of community wireless networks and compare with designs that decouple the layers. We demonstrate that significant performance advantages can be achieved by adopting a full-fledged cross-layer optimization. Furthermore, we observe that optimized solutions generally profit from network coding, physical-layer broadcasting, and traffic-dependent physical states.

The minimum energy required to transmit one bit of information through a network characterizes the most economical way to communicate in a network. In this paper, we show that, under a layered model of wireless networks, the minimum energy-per-bit for multicasting in a mobile ad hoc network can be found by a linear program; the minimum energy-per-bit can be attained by performing network coding. Compared with conventional routing solutions, network coding not only allows a potentially lower energy-per-bit to be achieved, but also enables the optimal solution to be found in polynomial time, in sharp contrast with the NP-hardness of constructing the minimum-energy multicast tree as the optimal routing solution. We further show that the minimum energy multicast formulation is equivalent to a cost minimization with linear edge-based pricing, where the edge prices are the energy-per-bits of the corresponding physical broadcast links. This paper also investigates minimum energy multicasting with routing. Due to the linearity of the pricing scheme, the minimum energy-per-bit for routing is achievable by using a single distribution tree. A characterization of the admissible rate region for routing with a single tree is presented. The minimum energy-per-bit for multicasting with routing is found by an integer linear program. We show that the relaxation of this integer linear program, studied earlier in the Steiner tree literature, can now be interpreted as the optimization for minimum energy multicasting with network coding. In short, this paper presents a unifying study of minimum energy multicasting with network coding and routing.

Network coding solutions and routing solutions, namely packing distribution trees, for the problem of information multicast is compared in this paper. To enable the comparison, we develop greedy tree packing algorithms that repeatedly pack the maximum-rate distribution tree and a greedy tree packing algorithm based on Lovasz' proof to Edmonds' theorem. We then investigate the potential advantages of network coding over routing. In terms of throughput, tree packing performs comparably to network coding on the network graphs of six Internet service providers. However, network coding offers additional benefits, including fewer network resources consumed, ease of management, and robustness.

The minimum energy required to transmit a bit of information through a network characterizes the most economical way to communicate in a network. In this paper, we show that under a simplified layered model of wireless networks, the minimum-energy multicast problem in mobile ad hoc networks is solvable as a linear program, assuming network coding. Compared with conventional routing solutions, network coding not only promises a potentially lower energy-per-bit, but also enables finding the optimal solution in polynomial time, in sharp contrast with the NP-hardness of constructing the minimum-energy multicast tree as the optimal routing solution.

A mobile wireless network experiences random variations due to node mobility, which may potentially be exploited for more cost-effective communications. The pioneering work by Grossglauser and Tse (2001) first demonstrated that a network under sufficient amount of (random) mobility could provide a larger scaling rate of throughput capacity than a static network, at the cost of significant and potentially unbounded end-to-end delay. Subsequent works have addressed the issue of the capacity gain under bounded delay. In this paper, we take a rather different approach in that we explore node mobility in the search for the optimal packet delivery routes subject to the QoS criteria such as delay and energy consumption. This is obtained by adopting a deterministic model in a noninterfering mobile ad hoc network (MANET). We present polynomial time algorithms for finding these optimal routes. Specifically, in a system without power control capability, where the transmission range of each node is fixed, we seek optimal routes with minimal end-to-end delivery time or lowest total power consumption along the path, respectively. For both formulations, we propose hop-expansion based algorithms that carry out the computations inductively over the number of hops. In a system with power control, we seek the minimum energy route, subject to certain end-to-end delay constraint. For this optimization, we propose a layered algorithm that performs the computations inductively over the discrete time periods.

We investigate signal detection for MIMO systems with imprecise channel knowledge. The optimal detector is one which best matches the "total" observation matrix and a "total" signal matrix which has a finite alphabet constraint and a Sylvester structure constraint. An iterative local optimization with interference cancellation (LOIC) algorithm is proposed to achieve low complexity and exploit the finite alphabet constraint. Simulation results show that our proposed algorithms can detect signals with BER close to the case of perfect channel knowledge, if a rough channel estimate is available initially.

In this work, we investigate the signal detection for MIMO systems with imprecise channel knowledge. The optimal detector is one which best matches the "total" observation matrix and a "total" signal matrix which has a finite alphabet constraint and a Sylvester structure constraint. An iterative local optimization with interference cancellation (LOIC) algorithm is proposed to achieve low complexity and exploit the finite alphabet constraint. Simulation results show that our proposed algorithms can detect the signals with BER close to the case of perfect channel knowledge, if a rough channel estimate is available initially.

In this paper, we investigate the design of pulse shaping UK filters for impulse radio ultrawideband (UWB) communications systems. The goal of the shaping is to meet an arbitrary spectrum mask, e.g., the mask mandated by the FCC for UWB emissions. Compared with classical FIR filter designs, the current problem introduces three new challenges: (1) it is minimax with quadratic constraints, (2) a single-sided distortion function is used, (3) delay positions are treated as tuning parameters. We first approach this problem by constructing a least-squares approximation to the minimax problem where the optimization over delays can be easily solved. With the LS solution serving as an initialization, nonlinear optimization techniques are employed to fine tune the solutions.

Space-Time Blocking Coding (STBC) has become very popular as an efficient diversity creation technique. With extra transmission redundancies introduced, the receiver performance can be significantly improved via STBC. In this paper, we study the signal recovery problem for a physical Multiple-Input-Multiple-Output (MIMO) channel via an inverse FIR filterbank together with STBC technique. It can be formulated within a multirate polyphase framework to reach an equivalent virtual MIMO system. It is shown that such a system enables equalization of ill conditioned MIMO channels and can offer performance superior to that with direct equalizations. Based on Generalized Bezout Identity theorems, the recoverability conditions are established. We also address the design problem for optimal noise resilience, which is critical from practical perspective. Furthermore, STBC can flexibly reduce the transmission rate to enhance the equalization SNR. The roles of different STBC and equalizer parameters are analyzed for the optimal tradeoff among transmission rate, diversity gain, and implementation complexity.

In this paper, we examine the problem of optimal spreading code assignment in an ad hoc DS-CDMA wireless network. The problem is formulated in two ways, with the optimization criteria being minimizing the congestion measure, and minimizing the total consumed power, respectively. Either formulation is converted to an optimization of the weighted total squared cross-correlation (WTSC), after some mathematical simplification. We then devise algorithms to reach some local minima of the optimization. Simulation results show significant reduction in the network congestion measure and power consumption, compared with random code allocation.

The concentric mosaic offers a solution for quick construction and easy navigation of a virtual environment. However, the huge amount of data presents a heavy burden. We propose the rebinning of slits (ROSS) for the compression of the concentric mosaic. The proposed scheme decorrelates the three-dimensional (3-D) concentric mosaic by rebinning the vertical slits of the 3-D image array into a large two-dimensional (2-D) panorama, and then it compresses the panorama with a JPEG 2000 image coder. Unlike typical video coders that use motion compensation to decorrelate multiple frames, the rebinning converts 3-D spatial correlation into stronger 2-D correlation. Experimental results show that the ROSS outperforms MPEG-2 coding of the concentric mosaic by an average of 1.0 dB.

Using an array of photo shots, the concentric mosaic offers a quick way to capture and model a realistic three-dimensional (3-D) environment. We compress the concentric mosaic image array with a 3-D wavelet transform and coding scheme. Our compression algorithm and bitstream syntax are designed to ensure that a local view rendering of the environment requires only a partial bitstream, thereby eliminating the need to decompress the entire compressed bitstream before rendering. By exploiting the ladder-like structure of the wavelet lifting scheme, the progressive inverse wavelet synthesis (PIWS) algorithm is proposed to maximally reduce the computational cost of selective data accesses on such wavelet compressed datasets. Experimental results show that the 3-D wavelet coder achieves high-compression performance. With the PIWS algorithm, a 3-D environment can be rendered in real time from a compressed dataset.

The concentric mosaic offers a quick solution to construct a virtual copy of a real environment, and to navigate in that virtual environment. However, the huge amount of data associated with the concentric mosaic is a heavy burden for its application. A three-dimensional (3D) wavelet-based compressor has been proposed in a previous work to compress the concentric mosaic. In this paper, we greatly improve the compression efficiency of the 3D wavelet coder by a data rearrangement mechanism called "smart rebinning". The proposed scheme first aligns the concentric mosaic image shots along the horizontal direction and then rebins the shots into multiperspective panoramas. Smart rebinning effectively enhances the correlation in the 3D data volume, translating the data into a representation that is more suitable for 3D wavelet compression. Experimental results show that the performance of the 3D wavelet coder is improved by an average of 4.3 dB with the use of the smart rebinning. The proposed coder outperforms MPEG-2 coding of the concentric mosaic by an average of 3.7 dB.

Concentric mosaics offer a quick solution to construct a virtual copy of a real environment, and navigate in the virtual environment. However, the huge amount of data associated with concentric mosaics is a heavy burden for its application. A 3D wavelet transform-based compressor has been proposed in previous work to compress the concentric mosaics. In this paper, we greatly improve the performance of the 3D wavelet coder with a data rearrangement mechanism called “smart rebinning”. The proposed scheme first aligns the concentric mosaic image shots along the horizontal direction and then rebins the shots into multi-perspective panoramas. Smart rebinning greatly improves the cross shot correlation and enables the coder to better explore the redundancy among shots. Experimental results show that the performance of the 3D wavelet coder improves an average of 4.3dB with the use of smart rebinning. The proposed coder outperforms MPEG-2 coding of concentric mosaics by an average of 3.7dB.