Code pruning in opportunistic routing through bidirectional coding traffic comparison

Opportunistic routing (OR) significantly improves transmission reliability and network throughput in wireless mesh networks by utilizing the broadcast nature of the wireless medium. Through the integration of network coding (NC), the complicated coordination to select the best forwarding node (FN) in OR can be bypassed. However, the introduction of NC exacerbates the redundant‐packet‐transmission problem. To mitigate this issue, existing coded OR protocols either adopt the loss‐rate‐based approach, employ orthogonal vectors as coded feedback, or pursue the stream‐based coded OR model. However, these three solutions suffer inaccuracy and obsolescence of the loss‐rate measurement, false‐positive/false‐negative problem, and unavailability of hop‐by‐hop stream‐based OR, respectively. To address the previous problems, we propose a simple but practical coded feedback scheme, cumulative coding coefficient acknowledgement (C³ACK), based on the relevance between forward (coded packets received from upstream nodes) and backward coding traffic (coded packets overheard from downstream nodes), and apply C³ACK to both batch‐based and stream‐based coded OR models in order to prune redundant forward and backward coding traffic. Both testbed evaluation and simulation study show that our code‐pruning schemes can outperform existing approaches in terms of expected throughput and transmission count. Copyright © 2014 John Wiley & Sons, Ltd.     

Throughput and resource optimization for adaptive coding‐based random access networks with correlated sources

Modern wireless communication networks frequently have lower application throughput due to higher number of collisions and subsequent retransmission of data packets. Moreover, these networks are characterized by restricted computational capacity due to limited node‐battery power. These challenges can be assessed for deploying fast, reliable network design with resource‐restrained operation by means of concurrent optimization of multiple performance parameters across different layers of the conventional protocol stack. This optimization can be efficiently accomplished via cross‐layer design with the aid of network coding technique and optimal allocation of limited resources to wireless links. In this paper, we evaluate and analyze intersession coding across several source–destination pairs in random access ad hoc networks with inherent power scarcity and variable capacity links. The proposed work addresses the problem of joint optimal coding, rate control, power control, contention, and flow control schemes for multi‐hop heterogeneous networks with correlated sources. For this, we employ cross‐layer design for multiple unicast sessions in the system with network coding and bandwidth constraints. This model is elucidated for global optimal solution using CVX software through disciplined convex programming technique to find the improved throughput and power allocation. Simulation results show that the proposed model effectively incorporates throughput and link power management while satisfying flow conservation, bit error rate, data compression, power outage, and capacity constraints of the challenged wireless networks. Finally, we compare our model with three previous algorithms to demonstrate its efficacy and superiority in terms of various performance metrics such as transmission success probability, throughput, power efficiency, and delay.     

A Network Coding Scheme to Improve Throughput for IEEE 802.11 WLAN

In IEEE 802.11 infrastructure wireless local area network (WLAN), the communication between any two nodes is relayed by an access point (AP), which becomes the bottleneck of WLAN and severely restricts the overall throughput. It is well known that network coding technique is able to greatly improve the throughput of wireless networks. But, the available coding schemes do not make full advantage of channel capacity due to the fact that they pick at most one packet from each data flow for coding and the picked packets may have a great difference in packet size, wasting some channel capacity. To remedy the problem, in this paper, we propose the coding scheme that combines multiple buffered packets in one flow into a larger packet for coding so that the packets participating in coding have close sizes. We formulate an integer programming problem to find the optimal packet coding, which is solved by an optimal algorithm with relative high time complexity together with a heuristic algorithm with relative low time complexity. Simulation results show that the proposed coding scheme is able to greatly improve the throughput of WLAN and the throughput gain increases with the growth of the number of coding flows.     

基于流的无线网络编码

针对无线链路的不可靠性和物理层的广播特性,将网络编码与无线网络相结合,提出一种基于流的无线网络编码算法——FNC。该算法在先验参考路径的基础上,充分利用每个节点处的路由表项,探测编码机会,在有编码机会的节点对满足编码条件的数据流进行网络编码,达到提高网络吞吐量的目的。仿真结果表明：FNC有效提高了整个网络的吞吐量,改善了网络性能。     

Environment-Driven Opportunity Forwarding Cross-Layer Optimization for Ubiquitous Wireless Networks

In this paper, an environment-driven cross-layer optimization scheme is proposed to maximize packet forwarding efficiency. The proposed algorithm is aimed to improve the performance of location-based routing protocol in respect of greedy forwarding and avoid void regions for ubiquitous wireless networks. In greedy forwarding mode, we use a new routing metric IAPS which can estimate the forwarding distance, link quality and the difficulty of channel access during the process of the next hop node selection. When the packet forwarding comes into a local minimum, the proposed scheme uses an opportunistic forwarding method based on competitive advantage to bypass the void regions. NS2 simulation results indicate that the proposed algorithm can improve network resource utilization and the average throughput, and reduce congestion loss rate of wireless multi-hop network comparison with existing GPSR algorithm.     

Cooperative Strategies and Achievable Rate for Tree Networks With Optimal Spatial Reuse

In this paper, a low-complexity cooperative protocol that significantly increases the average throughput of multihop upstream transmissions for wireless tree networks is developed and analyzed. A system in which transmissions are assigned to nodes in a collision free, spatial time division fashion is considered. The suggested protocol exploits the broadcast nature of wireless networks where the communication channel is shared between multiple adjacent nodes within interference range. For any upstream end-to-end flow in the tree, each intermediate node receives information from both one-hop and two-hop neighbors and transmits only sufficient information such that the next upstream one-hop neighbor will be able to decode the packet. This approach can be viewed as the generalization of the classical three node relay channel for end-to-end flows in which each intermediate node becomes successively source, relay and destination. The achievable rate for any regular tree network is derived and an optimal schedule that realizes this rate in most cases is proposed. Our protocol is shown to dramatically outperform the conventional scheme where intermediate nodes simply forward the packets hop by hop. At high signal-to-noise ratio (SNR), it yields approximately 66% throughput gain for practical scenarios.     

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.     

Probabilistic Forwarding Decision Scheme for Reliable Geocasting in Wireless Sensor Networks

Geocasting is an important communication service in wireless sensor networks. Most of the existing geocasting protocols assume that sensor nodes and the area of interest have accurate location information. However, this assumption is unreasonable if localization systems or schemes cannot work well. This study proposes an efficient probabilistic forwarding decision scheme for reliable geocasting in virtual coordinate-based wireless sensor networks. The proposed scheme uses directional code and hop distance to identify sensor node’s location. The sensor node determines a direction-based probability and a distance-based probability derived from its directional code and hop distance, respectively. The sensor node depends on the two probabilities to determine its ultimate forwarding probability. Simulation results confirm that the proposed scheme outperforms the pure direction-based forwarding scheme in packet delivery ratio though it occurs more packets. Results also show that the direction-based probability significantly dominates the geocasting performance.     

无线多跳网络中一种基于网络编码的机会路由

近年来机会路由和网络编码是两种利用无线信道广播特性提高网络性能的新兴技术。相比传统的静态路由决策,机会路由利用动态和机会路由选择减轻无线有损链路带来的影响。网络编码可以提高网络的资源利用率。但编码机会依赖于多个并发流所选路径的相对结构。为了创造更多的网络编码机会和提高网络吞吐量,本文提出了一种基于流间网络编码的机会路由(ORNC)算法。在ORNC中,每个分组转发的机会路径选择是基于网络编码感知的方式进行的。当没有编码机会时,采用背压策略选择下一跳转发路径以平衡网络负载。仿真结果表明本文提出的ORNC算法能够提高无线多跳网络的吞吐量。     

基于网络编码的无线路由技术研究进展

网络编码是近年来通信领域所取得的重大进展之一,其核心思想是网络节点对于接收的分组不是采取的传统的存储-转发的简单路由方式,而是存储-编码处理-转发的方式。网络编码已被证明是改善无线网络性能特别是吞吐量性能方面的下一代关键技术之一,特别适合战场环境下广播和组播信息的高效传输。本文综述了近年来基于网络编码的无线路由技术的相关研究进展,分析了现有研究的局限性与不足,并对下一步研究方向进行了展望。     

High-performance architectures for IP-based multihop 802.11 networks

The concept of a forwarding node, which receives packets from upstream nodes and then transmits these packets to downstream nodes, is a key element of any multihop network, wired or wireless. While high-speed IP router architectures have been extensively studied for wired networks, the concept of a "wireless IP router" has not been addressed so far. We examine the limitations of the IEEE 802.11 MAC protocol in supporting a low-latency and high-throughput IP datapath comprising multiple wireless LAN hops. We first propose a wireless IP forwarding architecture that uses MPLS with modifications to 802.11 MAC to significantly improve packet forwarding efficiency. We then study further enhancements to 802.11 MAC that improve system throughput by allowing a larger number of concurrent packet transmissions in multihop 802.11-based IP networks. With 802.11 poised to be the dominant technology for wireless LANs, we believe a combined approach to MAC, packet forwarding, and transport layer protocols is needed to make high-performance multihop 802.11 networks practically viable.     

Applications of network coding to improve TCP performance over wireless mesh networks: a survey

There is growing interest in the use of wireless mesh network (WMN) as a last‐mile option for Internet access. Despite the many benefits of WMNs, the performance of Internet access may not be ideal. One of the main issues is the interaction of transmission control protocol (TCP) with the underlying network. The poor performance of TCP over multi‐hop networks is well‐documented, and extensive research exists, which addresses TCPs foible and enhance TCP performance for multi‐hop environments. This paper provides a thorough survey of TCP performance issues over WMNs and the available solutions to address these issues. Among the existing methods, we focused on network coding (NC) and the ways that TCP interacts with network coded systems. NC is a technique that encodes the received packets in each node before forwarding them towards the destination. The use of NC in the transport layer to address performance issues raised by wireless access is a recent research topic. This paper presents a detailed study of TCP interaction with NC. Some open research areas in this field are suggested. Copyright © 2012 John Wiley & Sons, Ltd.     

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.     

Goodput and throughput comparison of single‐hop and multi‐hop routing for IEEE 802.11 DCF‐based wireless networks under hidden terminal existence

We investigate how multi‐hop routing affects the goodput and throughput performances of IEEE 802.11 distributed coordination function‐based wireless networks compared with direct transmission (single hopping), when medium access control dynamics such as carrier sensing, collisions, retransmissions, and exponential backoff are taken into account under hidden terminal presence. We propose a semi‐Markov chain‐based goodput and throughput model for IEEE 802.11‐based wireless networks, which works accurately with both multi‐hopping and single hopping for different network topologies and over a large range of traffic loads. Results show that, under light traffic, there is little benefit of parallel transmissions and both single‐hop and multi‐hop routing achieve the same end‐to‐end goodput. Under moderate traffic, concurrent transmissions are favorable as multi‐hopping improves the goodput up to 730% with respect to single hopping for dense networks. At heavy traffic, multi‐hopping becomes unstable because of increased packet collisions and network congestion, and single‐hopping achieves higher network layer goodput compared with multi‐hop routing. As for the link layer throughput is concerned, multi‐hopping increases throughput 75 times for large networks, whereas single hopping may become advantageous for small networks. The results point out that the end‐to‐end goodput can be improved by adaptively switching between single hopping and multi‐hopping according to the traffic load and topology. Copyright © 2015 John Wiley & Sons, Ltd.     

Simulation‐based real‐time routing protocol with load distribution in wireless sensor networks

In wireless sensor networks (WSNs), sensors gather information about the physical world and the base station makes decision and then performs appropriate actions upon the environment. This technology enables a user to effectively sense and monitor from a distance in real‐time. WSNs demand real‐time forwarding which means messages in the network are delivered according to their end‐to‐end deadlines (packet lifetime). This paper proposes a novel real‐time routing protocol with load distribution (RTLD) that ensures high packet throughput with minimized packet overhead and prolongs the lifetime of WSN. The routing depends on optimal forwarding (OF) decision that takes into account of the link quality (LQ), packet delay time and the remaining power of next hop sensor nodes. The proposed mechanism has been successfully studied through simulation work. Copyright © 2009 John Wiley & Sons, Ltd.     

Performance analysis of slotted ALOHA and network coding for single-relay multi-user wireless networks

Deployment of wireless relay nodes can enhance system capacity, extend wireless service coverage, and reduce energy consumption in wireless networks. Network coding enables us to mix two or more packets into a single coded packet at relay nodes and improve performances in wireless relay networks. In this paper, we succeed in developing analytical models of the throughput and delay on slotted ALOHA (S-ALOHA) and S-ALOHA with network coding (S-ALOHA/NC) for single-relay multi-user wireless networks with bidirectional data flows. The analytical models involve effects of queue saturation and unsaturation at the relay node. The throughput and delay for each user node can be extracted from the total throughput and delay by using the analytical models. One can formulate various optimization problems on traffic control in order to maximize the throughput, minimize the delay, or achieve fairness of the throughput or the delay. In particular, we clarify that the total throughput is enhanced in the S-ALOHA/NC protocol on condition that the transmission probability at the relay node is set at the value on the boundary between queue saturation and unsaturation. Our analysis provides achievable regions in throughput on two directional data flows at the relay node for both the S-ALOHA and S-ALOHA/NC protocols. As a result, we show that the achievable region in throughput can be enhanced by using network coding and traffic control.     

Byzantine robust trust establishment for mobile ad hoc networks

In a mobile ad hoc network (MANET), the nodes act both as traffic sources and as relays that forward packets from other nodes along multi-hop routes to the destination. Such networks are suited to situations in which a wireless infrastructure is unavailable, infeasible, or prohibitively expensive. However, the lack of a secure, trusted infrastructure in such networks make secure and reliable packet delivery very challenging. A given node acting as a relay may exhibit Byzantine behavior with respect to packet forwarding, i.e., arbitrary, deviant behavior, which disrupts packet transmission in the network. For example, a Byzantine node may arbitrarily choose to drop or misroute a certain percentage of the packets that are passed to it for forwarding to the next hop. In earlier work, we proposed a trust establishment framework, called Hermes, which enables a given node to determine the “trustworthiness” of other nodes with respect to reliable packet delivery by combining first-hand trust information obtained independently of other nodes and second-hand trust information obtained via recommendations from other nodes. A deficiency of the Hermes scheme is that a node can fail to detect certain types of Byzantine behavior, such as packet misforwarding directed at a particular source node. In this paper, we propose new mechanisms to make Hermes robust to Byzantine behavior and introduce a punishment policy that discourages selfish node behavior. We present simulation results that demonstrate the effectiveness of the proposed scheme in a variety of scenarios involving Byzantine nodes that are malicious both with respect to packet forwarding and trust propagation.     

An efficient network‐coding based back‐pressure scheduling algorithm for wireless multi‐hop networks

Back‐pressure scheduling has been considered as a promising strategy for resource allocation in wireless multi‐hop networks. However, there still exist some problems preventing its wide deployment in practice. One of the problems is its poor end‐to‐end (E2E) delay performance. In this paper, we study how to effectively use inter‐flow network coding to improve E2E delay and also throughput performance of back‐pressure scheduling. For this purpose, we propose an efficient network coding based back‐pressure algorithm (NBP), and accordingly design detailed procedure regarding how to consider coding gain in back‐pressure based weight calculation and how to integrate it into next hop decision making in the NBP algorithm. We theoretically prove that NBP can stabilize the networks. Simulation results demonstrate that NBP can not only improve the delay performance of back‐pressure algorithm, but also achieve higher network throughput. Copyright © 2016 John Wiley & Sons, Ltd.     

Cross‐layer bandwidth and power allocation for a two‐hop link in wireless mesh network

In this paper, a cross‐layer analytical framework is proposed to analyze the throughput and packet delay of a two‐hop wireless link in wireless mesh network (WMN). It considers the adaptive modulation and coding (AMC) process in physical layer and the traffic queuing process in upper layers, taking into account the traffic distribution changes at the output node of each link due to the AMC process therein. Firstly, we model the wireless fading channel and the corresponding AMC process as a finite state Markov chain (FSMC) serving system. Then, a method is proposed to calculate the steady‐state output traffic of each node. Based on this, we derive a modified queuing FSMC model for the relay to gateway link, which consists of a relayed non‐Poisson traffic and an originated Poisson traffic, thus to evaluate the throughput at the mesh gateway. This analytical framework is verified by numerical simulations, and is easy to extend to multi‐hop links. Furthermore, based on the above proposed cross‐layer framework, we consider the problem of optimal power and bandwidth allocation for QoS‐guaranteed services in a two‐hop wireless link, where the total power and bandwidth resources are both sum‐constrained. Secondly, the practical optimal power allocation algorithm and optimal bandwidth allocation algorithm are presented separately. Then, the problem of joint power and bandwidth allocation is analyzed and an iterative algorithm is proposed to solve the problem in a simple way. Finally, numerical simulations are given to evaluate their performances. Copyright © 2008 John Wiley & Sons, Ltd.     

XORs in the Air: Practical Wireless Network Coding

This paper proposes COPE, a new architecture for wireless mesh networks. In addition to forwarding packets, routers mix (i.e., code) packets from different sources to increase the information content of each transmission. We show that intelligently mixing packets increases network throughput. Our design is rooted in the theory of network coding. Prior work on network coding is mainly theoretical and focuses on multicast traffic. This paper aims to bridge theory with practice; it addresses the common case of unicast traffic, dynamic and potentially bursty flows, and practical issues facing the integration of network coding in the current network stack. We evaluate our design on a 20-node wireless network, and discuss the results of the first testbed deployment of wireless network coding. The results show that using COPE at the forwarding layer, without modifying routing and higher layers, increases network throughput. The gains vary from a few percent to several folds depending on the traffic pattern, congestion level, and transport protocol.