Binary linear multicast network coding on acyclic networks: principles and applications in wireless communication networks

Conventional linear multicast can be constructed on any acyclic network by increasing the order of the finite field to a sufficiently large amount over which the multicast is defined. In this paper, we first discuss the reciprocal theorem of the conventional linear multicast and design a linear multicast on any give acyclic network with constant finite field by extending the multicast dimension and relaxing the constraint on the information storage. In particular, we propose the binary linear multicast network coding and the linear multicast with binary coefficients. With the proposed method, the computation complexity for network coding at the intermediate nodes can be significantly reduced; therefore cheap network nodes can be deployed in a large scale due to their low cost for wireless communications. In addition, some applications of the proposed binary linear multicast network coding in wireless communication networks are illustrated and validated.     

A batched network coding scheme for wireless networks

Several wireless network coding schemes apply either inter-flow traffic or intra-flow traffic, but not both. This paper proposes a novel batched network coding scheme to deal with both inter-flow and intra-flow traffics, which attempts to combine the advantages of both network coding approaches. Based on the idea in the well-known network coding scheme COPE, our batched network coding scheme allows each node to make use of intra-flow network coding technique to improve the transmission reliability in a lossy environment, consequently obtaining higher throughput. Moreover, we also utilize the multiple-path transmitting scheme to further increase the throughput of wireless networks with low link delivery probability. Finally, using a simplified network topology model, we show theoretically that our proposed scheme outperforms COPE significantly, particularly when the link quality is low.     

Maximum flow and network capacity of network coding for ad-hoc networks

Network coding is an effective way to achieve the maximum flow of multicast networks. In this letter, we focus on the statistical properties of the maximum flow or the capacity of network coding for ad-hoc networks based on random graph models. Theoretical analysis shows that the maximum flow can be modelled as extreme order statistics of Gaussian distribution for both wired and wireless ad-hoc networks as the node number is relatively large under a certain condition. We also investigate the effects of the nodes' covering capabilities on the capacity of network coding.     

A hybrid network coding technique for single-hop wireless networks

In this paper, we investigate a hybrid network coding technique to be used at a wireless base station (BS) or access point (AP) to increase the throughput efficiency of single-hop wireless networks. Traditionally, to provide reliability, lost packets from different flows (applications) are retransmitted separately, leading to inefficient use of wireless bandwidth. Using the proposed hybrid network coding approach, the BS encodes these lost packets, possibly from different flows together before broadcasting them to all wireless users. In this way, multiple wireless receivers can recover their lost packets simultaneously with a single transmission from the BS. Furthermore, simulations and theoretical analysis showed that when used in conjunction with an appropriate channel coding technique under typical channel conditions, this approach can increase the throughput efficiency up to 3.5 times over the automatic repeat request (ARQ), and up to 1.5 times over the HARQ techniques.     

On the capacity of network coding for random networks

We study the maximum flow possible between a single-source and multiple terminals in a weighted random graph (modeling a wired network) and a weighted random geometric graph (modeling an ad-hoc wireless network) using network coding. For the weighted random graph model, we show that the network coding capacity concentrates around the expected number of nearest neighbors of the source and the terminals. Specifically, for a network with a single source, l terminals, and n relay nodes such that the link capacities between any two nodes is independent and identically distributed (i.i.d.) /spl sim/X, the maximum flow between the source and the terminals is approximately nE[X] with high probability. For the weighted random geometric graph model where two nodes are connected if they are within a certain distance of each other we show that with high probability the network coding capacity is greater than or equal to the expected number of nearest neighbors of the node with the least coverage area.     

Fair coding for inter‐session network coding in wireless mesh networks

Because of the broadcast and overhearing capability of wireless networks, network coding can greatly improve throughput in wireless networks. However, our investigation of existing inter‐session network coding protocols found that the short‐term unfairness that existed in 802.11‐based medium access control (MAC) protocols actually decreases the coding opportunity, which in turn compromises the throughput gain of network coding. To alleviate the negative impact of this unfairness, we propose a coding‐aware cross‐layer heuristic approach to optimize the coordination of network coding and MAC layer protocol, named FairCoding, which can significantly increase coding opportunities for inter‐session network coding through a fair short‐term traffic allocation for different coding flows. Experiment evaluation shows that the proposed mechanism can bring more coding opportunities and improve the total throughput of wireless mesh networks by up to 20%, compared with the coding mechanism, without considering the negative impact of the short‐term unfairness. Copyright © 2015 John Wiley & Sons, Ltd.     

Video-aware opportunistic network coding over wireless networks

In this paper, we study video streaming over wireless networks with network coding capabilities. We build upon recent work, which demonstrated that network coding can increase throughput over a broadcast medium, by mixing packets from different flows into a single packet, thus increasing the information content per transmission. Our key insight is that, when the transmitted flows are video streams, network codes should be selected so as to maximize not only the network throughput but also the video quality. We propose video-aware opportunistic network coding schemes that take into account both the decodability of network codes by several receivers and the importance and deadlines of video packets. Simulation results show that our schemes significantly improve both video quality and throughput. This work is a first step towards content-aware network coding.     

A one-hop opportunistic network coding algorithm for wireless mesh networks

This paper proposes a Bearing Opportunistic Network (BON) coding procedure that operates in wireless multihop networks over multiple unicast sessions and it introduces very low overhead to the network. The BON coding is used to increase network performance in terms of a higher throughput and a lower delay. It can be seen as an independent layer in the communication stack, relying solely on information that is on the node itself. The proposed coding procedure is easy to implement and deploy. The performance evaluation of the BON coding procedure was performed in a dedicated simulation model. The comparison was made to the well-known network coding procedure COPE and the case where network coding is not used at all. Results show that BON coding increases the network goodput and decreases the delay in comparison to COPE and case where network coding is not used.     

Compressive network coding for error control in wireless sensor networks

Since the observed signals of nearby sensors are known to be correlated, this paper firstly investigates the connection between network coding and compression concept of compressed sensing and then makes an in-depth combination between these two powerful concepts for error control in wireless sensor networks. Thus, a joint scheme is developed to achieve the maximum gain by exploiting the temporal and spatial correlations simultaneously. This scheme overcomes drawbacks of network coding theory by injecting the corresponding distributed compressed sensing concept into network coding, i.e., the scheme possesses good compression gain and graceful degradation of precision in the reconstruction process. Meanwhile, it can tolerate finite erasures and errors as well as reconstruct the original information as precise as possible when the rank of error matrix (induced by erasures and errors) doesn’t exceed the upper boundary. Finally, the reliability analysis and numeric results show that the compressive network coding scheme (i.e., the joint scheme) outperforms the conventional network coding scheme in robustness and performance.     

Efficient CQI feedback via network coding for wireless relay networks

For the efficacy of radio resource management in downlink wireless relay networks, the channel quality indicator (CQI) between a mobile station (MS) and a relay station (RS) should be fed back from the RS to its base station (BS), at the cost of additional feedback overhead. In this letter, we propose an efficient feedback scheme based on network coding between a pilot sequence and the CQI of MS-RS link, through which the BS can have both CQIs of MS-RS and RS-BS links without overhead. Numerical results reveal that the proposed CQI reporting scheme has as good feedback performance as conventional one which generally requires additional feedback burden.     

基于网络编码的机会网络高效路由算法

针对采用Epidemic机制的机会网络路由算法在数据分组传送阶段存在通信冗余的问题,提出了一种基于网络编码的高效路由算法--NCBER(network-coding-based epidemic routing）。NCBER在传送数据分组的过程中使用主动异或网络编码和多播,并取消了 Request（请求）控制分组,从而减少数据分组的转发次数和控制分组数量,降低网络开销,缩短分组传输时延。理论分析和仿真结果表明,NCBER 算法在网络开销和数据分组端到端时延性能方面优于经典的Epidemic路由算法及其改进算法MRRMR（message redundancy removal of multi-copy routing）,并且使数据传送成功率保持在100%。     

Multicast with network coding in application-layer overlay networks

All of the advantages of application-layer overlay networks arise from two fundamental properties: 1) the network nodes in an overlay network, as opposed to lower-layer network elements such as routers and switches, are end systems and have capabilities far beyond basic operations of storing and forwarding; 2) the overlay topology, residing above a densely connected Internet protocol-layer wide-area network, can be constructed and manipulated to suit one's purposes. We seek to improve end-to-end throughput significantly in application-layer multicast by taking full advantage of these unique characteristics. This objective is achieved with two novel insights. First, we depart from the conventional view that overlay nodes can only replicate and forward data. Rather, as end systems, these overlay nodes also have the full capability of encoding and decoding data at the message level using efficient linear codes. Second, we depart from traditional wisdom that the multicast topology from source to receivers needs to be a tree, and propose a novel and distributed algorithm to construct a two-redundant multicast graph (a directed acyclic graph) as the multicast topology, on which network coding is applied. We design our algorithm such that the costs of link stress and stretch are explicitly considered as constraints and minimized. We extensively evaluate our algorithm by provable analytical and experimental results, which show that the introduction of two-redundant multicast graph and network coding may indeed bring significant benefits, essentially doubling the end-to-end throughput in most cases.     

Optimized multipath network coding in lossy wireless networks

Network coding has been a prominent approach to a series of problems that used to be considered intractable with traditional transmission paradigms. Recent work on network coding includes a substantial number of optimization based protocols, but mostly for wireline multicast networks. In this paper, we consider maximizing the benefits of network coding for unicast sessions in lossy wireless environments. We propose Optimized Multipath Network Coding (OMNC), a rate control protocol that dramatically improves the throughput of lossy wireless networks. OMNC employs multiple paths to push coded packets to the destination, and uses the broadcast MAC to deliver packets between neighboring nodes. The coding and broadcast rate is allocated to transmitters by a distributed optimization algorithm that maximizes the advantage of network coding while avoiding congestion. With extensive experiments on an emulation testbed, we find that OMNC achieves more than two-fold throughput increase on average compared to traditional best path routing, and significant improvement over existing multipath routing protocols with network coding. The performance improvement is notable not only for one unicast session, but also when multiple concurrent unicast sessions coexist in the network.     

Scalable broadcast with network coding in heterogeneous networks

This article studies the scalable broadcast scheme realized with the joint application of layered source coding,unequal error protection(UEP)and random network coding from the theoretical point of view.The success probability for any non-source node in a heterogeneous network to recover the most important layers of the source data is deduced.This probability proves that in this broadcast scheme every non-source node with enough capacity can always recover the source data partially or entirely as long as the finite field size is sufficiently large.Furthermore,a special construction for the local encoding kernel at the source node is proposed.With this special construction,an increased success probability for partial decoding at any non-source node is achieved,i.e.,the partial decodability offered by the scalable broadcast scheme is improved.     

Cross-layer optimization for wireless multihop networks with pairwise intersession network coding

For wireless multi-hop networks with unicast sessions, most coding opportunities involve only two or three sessions as coding across many sessions requires greater transmission power to broadcast the coded symbol to many receivers, which enhances interference. This work shows that with a new flow-based characterization of pairwise intersession network coding (coding across two unicast sessions), an optimal joint coding, scheduling, and rate-control scheme can be devised and implemented using only the binary XOR operation. The new scheduling/rate-control scheme demonstrates provably graceful throughput degradation with imperfect scheduling, which facilitates the design tradeoff between the throughput optimality and computational complexity of different scheduling schemes. Our results show that pairwise intersession network coding improves the throughput of non-coding solutions regardless of whether perfect/imperfect scheduling is used. Both the deterministic and stochastic packet arrivals and departures are considered. This work shows a striking resemblance between pairwise intersession network coding and non-coded solutions, and thus advocates extensions of non-coding wisdoms to their network coding counterpart.     

High efficient multipacket decoding approach for network coding in wireless networks

To improve the performance of transmission by reducing the number of transmission and network overhead of wireless single-hop networks, this paper presents a high efficient multipacket decoding approach for network coding (EMDNC) in wireless networks according to the idea of encoding packets which cannot be decoded and are stored in buffer by receiving nodes, the lost packets can be recovered from these encoded packets. Compared with the network coding wireless broadcasting retransmission (NCWBR), EMDNC can improve the efficiency of decoding and reduce the number of retransmission and transmission delay. Simulation results reveal that EMDNC can effectively reduce the number of retransmission and network overhead.     

Throughput analysis of two-hop wireless networks with network coding

A Two-hop Wireless Network (TWN) is the basic topology structure that provides network coding opportunity for improving throughput. Network coding on a homogeneous TWN, in which all the data flows have the same packet size and all the links have the same transmission rate, has been extensively investigated. In this paper, network coding on more practical heterogeneous TWNs, featured by various packet sizes and transmission rates, is studied. Based on the Markov model, the throughput of the proposed network coding scheme, together with the throughput gain, is derived, which matches the simulation results very well. Numerical analyses indicate that, encoding the packets with close size and close transmission rate and enlarging buffer size at the relay node help in improving the throughput gain.     

Overcoming untuned radios in wireless networks with network coding

The drive toward the implementation and massive deployment of wireless sensor networks calls for ultralow-cost and low-power nodes. While the digital subsystems of the nodes are still following Moore's Law, there is no such trend regarding the performance of analog components. This work proposes a fully integrated architecture of both digital and analog components (including local oscillator) that offers significant reduction in cost, size, and overall power consumption of the node. Even though such a radical architecture cannot offer the reliable tuning of standard designs, it is shown that by using random network coding, a dense network of such nodes can achieve throughput linear in the number of channels available for communication. Moreover, the ratio of the achievable throughput of the untuned network to the throughput of a tuned network with perfect coordination is shown to be close to 1/e. This work uses network coding to leverage the fact that throughput equal to the max-flow in a graph is achievable even if the topology is not know a priori. However, the challenge here is finding the max-flow of the random graph corresponding to the network.     

On the relay selection for cooperative wireless networks with physical-layer network coding

In this paper, we investigate a large cooperative wireless network with relay nodes, in which cooperation is enabled through physical-layer network coding (PLNC). Specifically, we study the impact of the relay selection on the network capacity with power constraints in two scenarios. First, we consider the basic PLNC model (a.k.a., the ARB model), in which one pair of source nodes (A,?B) exchange messages via a selected relay node (R). Given the power constraint, we derive the optimal relay selection and power allocation that maximize the sum capacity, defined as the summation of the capacity for two source-destination channels. Based on results obtained above, we then consider a more general scenario with multiple pairs of source nodes. Assuming the constant power constraint, we derive the upper bound of the minimal sum capacity of any source pair. The optimal power allocation among multiple source pairs is also derived. To validate these theoretical results, we also provide two relay selection strategies: a modified optimal relay assignment strategy and a novel middle point strategy for maximizing the minimal sum capacity of any source pair.     

A network coding based interference cancelation scheme for wireless ad hoc networks

The performance of wireless networks is limited by multiple access interference (MAI) in the traditional communication approach where the interfered signals of the concurrent transmissions are treated as noise. In this paper, we treat the interfered signals from a new perspective on the basis of additive electromagnetic (EM) waves and propose a network coding based interference cancelation (NCIC) scheme. In the proposed scheme, adjacent nodes can transmit simultaneously with careful scheduling; therefore, network performance will not be limited by the MAI. Additionally we design a space segmentation method for general wireless ad hoc networks, which organizes network into clusters with regular shapes (e.g., square and hexagon) to reduce the number of relay nodes. The segmentation method works with the scheduling scheme and can help achieve better scalability and reduced complexity. We derive accurate analytic models for the probability of connectivity between two adjacent cluster heads which is important for successful information relay. We proved that with the proposed NCIC scheme, the transmission efficiency can be improved by at least 50% for general wireless networks as compared to the traditional interference avoidance schemes. Numeric results also show the space segmentation is feasible and effective. Finally we propose and discuss a method to implement the NCIC scheme in a practical orthogonal frequency division multiplexing (OFDM) communications networks. Copyright © 2009 John Wiley & Sons, Ltd.