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.     

Novel Section‐Based Joint Network Coding and Scheduling Scheme in WMNs: JNCS

Guaranteeing quality of service over a multihop wireless network is difficult because end‐to‐end (ETE) delay is accumulated at each hop in a multihop flow. Recently, research has been conducted on network coding (NC) schemes as an alternative mechanism to significantly increase the utilization of valuable resources in multihop wireless networks. This paper proposes a new section‐based joint NC and scheduling scheme that can reduce ETE delay and enhance resource efficiency in a multihop wireless network. Next, this paper derives the average ETE delay of the proposed scheme and simulates a TDMA network where the proposed scheme is deployed. Finally, this paper compares the performance of the proposed scheme with that of the conventional sequential scheduling scheme. From the performance analysis and simulation results, the proposed scheme gives more delay‐ and energy‐efficient slot assignments even if the NC operation is applied, resulting in a use of fewer network resources and a reduction in ETE delay.     

On-demand coding-aware routing in wireless Mesh networks

Network coding,which exploits the broadcast nature of wireless medium,is an effective way to improve network performance in wireless multi-hop networks,but the first practical wireless network coding system COPE cannot actively detect a route with more coding opportunities and limit the coding structure within two-hop regions.An on-demand coding-aware routing scheme(OCAR)for wireless Mesh networks is proposed to overcome the limitations specified above by actively detecting a route with more coding opportunities along the entire route rather than within two-hop regions.Utilizing more coding opportunities tends to route multiple flows 'close to each other' while avoiding interference requires routing multiple flows 'away from each other'.OCAR achieves a tradeoff by adopting RCAIA as routing metric in route discovery,which is not only coding-aware but also considers both inter and intra flow interference.Simulation results show that,compared with Ad-hoc on-demand distance vecfor routing(AODV)and AODV+COPE,OCAR can find more coding opportunities,thus effectively increase network throughput,reduce end to end delay and alleviate network congestion.     

Towards an end-to-end delay analysis of wireless multihop networks

In wireless multihop networks, end-to-end (e2e) delay is a critical parameter for quality of service (QoS) guarantees. We employ discrete-time queueing theory to analyze the end-to-end (e2e) delay of wireless multihop networks for two MAC schemes, m-phase TDMA and slotted ALOHA. In one-dimensional (1-D) networks, due to the lack of sufficient multiplexing and splitting, a space–time correlation structure exists, the nodes are spatially correlated with each other, and the e2e performance cannot be analyzed as in general two-dimensional networks by assuming all nodes independent of each other. This paper studies an 1-D network fed with a single flow, an extreme scenario in which there is no multiplexing and splitting. A decomposition approach is used to decouple the whole network into isolated nodes. Each node is modeled as a GI/Geo/1 queueing system. First, we derive the complete per-node delay distribution and departure characterization, accounting for both the queueing delay and access delay. Second, based on the departure process approximation, we define a parameter to measure the spatial correlation and its influence on the e2e delay variance. Our study shows that traffic burstiness of the source flow and MAC together determines the sign of the correlation.     

Self-coordinating localized fair queueing in wireless ad hoc networks

Distributed fair queueing in a multihop, wireless ad hoc network is challenging for several reasons. First, the wireless channel is shared among multiple contending nodes in a spatial locality. Location-dependent channel contention complicates the fairness notion. Second, the sender of a flow does not have explicit information regarding the contending flows originated from other nodes. Fair queueing over ad hoc networks is a distributed scheduling problem by nature. Finally, the wireless channel capacity is a scarce resource. Spatial channel reuse, i.e., simultaneous transmissions of flows that do not interfere with each other, should be encouraged whenever possible. In this paper, we reexamine the fairness notion in an ad hoc network using a graph-theoretic formulation and extract the fairness requirements that an ad hoc fair queueing algorithm should possess. To meet these requirements, we propose maximize-local-minimum fair queueing (MLM-FQ), a novel distributed packet scheduling algorithm where local schedulers self-coordinate their scheduling decisions and collectively achieve fair bandwidth sharing. We then propose enhanced MLM-FQ (EMLM-FQ) to further improve the spatial channel reuse and limit the impact of inaccurate scheduling information resulted from collisions. EMLM-FQ achieves statistical short-term throughput and delay bounds over the shared wireless channel. Analysis and extensive simulations confirm the effectiveness and efficiency of our self-coordinating localized design in providing global fair channel access in wireless ad hoc networks.     

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.     

Network-coding-based scheduling and routing schemes for service-oriented wireless mesh networks - [Service-oriented broadband wireless network architecture]

Service-oriented wireless mesh networks have recently been receiving intensive attention as a pivotal component to implement the concept of ubiquitous computing due to their easy and cost-effective deployment. To deliver a variety of services to subscriber stations, a large volume of traffic is exchanged via mesh routers in the mesh backbone network. One of the critical problems in service-oriented wireless mesh networks is to improve the network throughput. Wireless network coding is a key technology to improve network throughput in multihop wireless networks since it can exploit not only the broadcast nature of the wireless channel, but also the native physical-layer coding ability by mixing simultaneously arriving radio waves at relay nodes. We first analyze the throughput improvement obtained by wireless network coding schemes in wireless mesh networks. Then we develop a heuristic joint link scheduling, channel assignment, and routing algorithm that can improve the network throughput for service-oriented wireless mesh networks. Our extensive simulations show that wireless network coding schemes can improve network throughput by 34 percent.     

Opportunistic delay‐margin‐based resource allocation for next‐generation wireless networks

This paper studies and develops efficient traffic management techniques for downlink transmission at the base station (BS) of multi‐service IP‐based networks by combining quality‐of‐service (QoS) provision and opportunistic wireless resource allocation. A delay‐margin‐based scheduling (DMS) for downlink traffic flows based on the delays that each packet has experienced up to the BS is proposed. The instantaneous delay margin, represented by the difference between the required and instantaneous delays, quantifies how urgent the packet is, and thus it can determine the queuing priority that should be given to the packet. The proposed DMS is further integrated with the opportunistic scheduling (OPS) to develop various queueing architectures to increase the wireless channel bandwidth efficiency. Different proposed integration approaches are investigated and compared in terms of delay outage probability and wireless channel bandwidth efficiency by simulation. Copyright © 2010 John Wiley & Sons, Ltd.     

Expedited forwarding end‐to‐end delay and jitter in DiffServ

The scheduling disciplines and active buffer management represent the main components employed in the differentiated services (DiffServ) data plane, which provide qualitative per‐hop behaviors corresponding to the QoS required by supported traffic classes. In the first part of this paper, we compute the per‐hop delay bound that should be guaranteed by the different multiservice scheduling disciplines, so that the end‐to‐end (e2e) delay required by expedited forwarding (EF) traffic can be guaranteed. Consequently, we derive the e2e delay bound of EF traffic served by priority queuing–weighted fair queuing (PQ–WFQ) at every hop along its routing path. Although real‐time flows are principally offered EF service class, some simulations on DiffServ‐enabled network show that these flows suffer from delay jitter and they are negatively impacted by lower priority traffic. In the second part of this paper, we clarify the passive impact of delay jitter on EF traffic, where EF flows are represented by renewal periodic ON–OFF flows, and the background (BG) flows are characterized by the Poisson process. We analyze through different scenarios the jitter effects of these BG flows on EF flow patterns when they are served by a single class scheduling discipline, such as first‐input first‐output, and a multiclass or multiservice scheduling discipline, such as static priority service discipline. As a result, we have found out that the EF per‐hop behaviors (PHBs) configuration according to RFCs 2598 and 3246 (IETF RFC 2598, June 1999; RFC 3246, IETF, March 2002) cannot stand alone in guaranteeing the delay jitter required by EF flows. Therefore, playout buffers must be added to DiffServ‐enabled networks for handling delay jitter problem that suffers from EF flows. Copyright © 2008 John Wiley & Sons, Ltd.     

Delay Analysis of All-Optical Packet-Switching Ring and Bus Communications Networks

We study the delay performance of all-optical packet communication networks configured as ring and bus topologies employing cross-connect switches (or wavelength routers). Under a cross-connect network implementation, a packet experiences no (or minimal) internal queueing delays. Thus, the network can be implemented by high speed all-optical components. We further assume a packet-switched network operation, such as that using a slotted ring or bus access methods. In this case, a packet's delay is known before it is fed into the network. This can be used to determine if a packet must be dropped (when its end-to-end delay requirement is not met) at the time it accesses the network. It also leads to better utilization of network capacity resources. We also derive the delay performance for networks under a store-and-forward network operation. We show these implementations to yield very close average end-to-end packet queueing delay performance. We note that a cross-connect network operation can yield a somewhat higher queueing delay variance levels. However, the mean queueing delay for all traffic flows are the same for a cross-connect network operation (under equal nodal traffic loading), while that in a store-and-forward network increases as the path length increases. For a ring network loaded by a uniform traffic matrix, the queueing delay incurred by 90% of the packets in a cross-connect network may be lower than that experienced in a store-and-forward network. We also study a store-and-forward network operation under a nodal round robin (fair queueing) scheduling policy. We show the variance performance of the packet queueing delay for such a network to be close to that exhibited by a cross-connect (all-optical) network.     

On the characteristics of queueing and scheduling at encoding nodes for network coding

Synchronization can greatly influence the performance of network coding. In this paper, we shall investigate the synchronization issue based on the use of queueing theory. We shall first propose a queueing model, referred to as the classic model, to investigate the characteristics of the encoding process. It will be proved that given the packet arrival processes are stationary, i.e. the distribution of the arrival processes does not depend on time, and obey independently and identically Poisson distribution and that the encoding time is exponentially distributed, the output flow will be an asymptotically Poisson flow with the same parameter. Through simulation we shall show that the network is sensitive to the arrival rate of input flows and becomes unstable with the input queue size increasing to infinity. This indicates that the classic coding scheme would impose strict requirements on synchronization over the whole network. In order to address this, we shall propose a combined opportunistic scheduling and encoding (COSE) strategy, in which the classic coding scheme and the traditional forwarding algorithm are well integrated. Theoretical analysis and simulation will demonstrate that the COSE strategy is able to control the input queue sizes and keep the network operating in a stable state while maintaining a relatively high throughput, low blocking probability and small waiting delay under various levels of traffic load. Copyright © 2009 John Wiley & Sons, Ltd.     

Performance analysis of hierarchical cellular networks with queueing and user retrials

How to efficiently utilize the scarce radio channel resource while maintaining the desired user‐perceived quality level and improved network performance is a major challenge to a wireless network designer. As one solution to meet this challenge in cellular mobile networks, a network architecture with hierarchical layers of cells has been widely considered. In this paper, we study the performance of a hierarchical cellular network that allows the queueing of both overflow slow‐mobility calls (from the lower layer microcells) and macrocell handover fast‐mobility calls that are blocked due to lack of free resources at the macrocell. Further, to accurately represent the wireless user behaviour, the impact of call repeat phenomenon is considered in the analysis of new call blocking probability. Performance analysis of the hierarchical cellular structure with queueing and call repeat phenomenon is performed using both analytical and simulation techniques. Numerical results show that queueing of calls reduces forced call termination probability and increases resource utilization with minimal call queueing delay. It is also shown that ignoring repeat calls leads to optimistic estimates of new call blocking probability especially at high offered traffic. Copyright © 2005 John Wiley & Sons, Ltd.     

Stochastic performance analysis of non-feedforward networks

Many Internet applications are both delay and loss sensitive, and need network performance guarantees that include bandwidth, delay/delay jitter, and packet loss rate. It is very important to quantify and exploit the capabilities of guaranteed service provisioning of communication networks. In this paper, we study the queueing behaviors of non-feedforward networks (a non-feedforward network is a network in which at least one set of acyclic traffic routes forms a cycle; a feedforward network is a network in which any set of acyclic traffic routes does not form a cycle) with FIFO scheduling discipline and Regulated, Markov On-Off, and Fractional Brownian traffic sources. We develop a new methodology to analyze the probabilistic bounds on the delays experienced by traffic. By leveraging the large deviations and fixed-point techniques, we turn probability problems into deterministic optimization problems and translate a probabilistic delay bound into a fixed point of a non-linear real function. Our contribution in this paper is the derivation of a probabilistic bound on the delays experienced by traffic in non-feedforward networks, based on an assumption, i.e., the tail probability of the difference between the beginning time of a busy interval of a server and the earliest arriving time at the corresponding network ingress of the traffic arrivals that arrive at this server during this busy interval can be bounded by the maximum of the violation probabilities of the accumulative upper stream delay bound suffered by this server‘s traffic arrivals. Consequently, our new results not only consummate the theory of stochastic analysis of network performance, but also facilitate the design of protocols and algorithms for non-feedforward networks to provide performance guarantees to various applications with diverse performance requirements.     

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.     

Wireless network coding in slotted aloha with two-hop unbalanced traffic

This paper deals with two representative unbalanced traffic cases for two-hop wireless relay access systems employing network coding and a slotted ALOHA protocol. Network coding is a recent and highly regarded technology for capacity enhancement with multiple unicast and multisource multicast networks. We have analyzed the performance of network coding on a two-hop wireless relay access system employing the slotted ALOHA under a balanced bidirectional traffic. The relay nodes will generally undergo this unbalanced multidirectional traffic but the impact of this unbalanced traffic on network coding has not been analyzed. This paper provides closed-form expressions for the throughput and packet delay for two-hop unbalanced bidirectional traffic cases both with and without network coding even if the buffers on nodes are unsaturated. The analytical results are mainly derived by solving queueing systems for the buffer behavior at the relay node. The results show that the transmission probability of the relay node is a design parameter that is crucial to maximizing the achievable throughput of wireless network coding in slotted ALOHA on two-hop unbalanced traffic cases. Furthermore, we show that the throughput is enhanced even if the traffic at the relay node is unbalanced.     

Downlink media streaming with wireless fountain coding in wireline‐cum‐WiFi networks

This paper addresses the problem of streaming packetized media data in a combined wireline/802.11 network. Since the wireless channel is normally the bottleneck for media streaming in such a network, we propose that wireless fountain coding (WFC) be used over the wireless downlink in order to efficiently utilize the wireless bandwidth and exploit the broadcast nature of the channel. Forward error correction (FEC) is also used to combat errors at the application‐layer. We analytically obtain the moment generating function (MGF) for the wireless link‐layer delay incurred by WFC. With the MGF, the expected value of this wireless link‐layer delay is found and used by the access point (AP), who has no knowledge of the buffer contents of wireless receivers, to make a coding‐based decision. We then derive the end‐to‐end packet loss/late probability based on the MGF. We develop an integrated ns‐3/EvalVid simulator to evaluate our proposed system and compare it with the traditional 802.11e scheme which is without WFC capability but equipped with application‐ and link‐layer retransmission mechanisms. Through extensive simulations of video streaming, we show that streaming with WFC is able to support more concurrent video flows compared to the traditional scheme. When the deadlines imposed on video packets are relatively stringent, streaming with WFC also shows superior performance in terms of packet loss/late probability, video distortion, and video frame delay, over the traditional scheme. Copyright © 2011 John Wiley & Sons, Ltd.     

On delay constrained CAC scheme and scheduling policy for CBR traffic in IEEE 802.11e wireless LANs

CBR (constant bit rate) traffic is expected to be an important traffic source in wireless networks. Such sources usually have stringent jitter or delay requirements and in many cases they should be delivered exactly as they were generated. In this paper, we propose a strictly guaranteed QoS (quality‐of‐service) provisioning CAC (call admission control) scheme with a polling‐based scheduling policy for CBR traffic in IEEE 802.11e wireless LANs. Under such a scheme, the proposed transmit‐permission policy for HCCA (HCF controlled channel access) method can forecast the maximum suffered delay for each packet and derive sufficient conditions so that all the CBR sources satisfy their time constraints to provide deterministic QoS guarantees. A simple analytical model is carried out to estimate the average queueing delay of the proposed scheme. In addition to theoretical analysis, simulations are conducted to validate its promising performance. Our simulation results show that the proposed scheme maintains a high throughput with respect to the whole range of system load. Copyright © 2009 John Wiley & Sons, Ltd.     

Fair scheduling in wireless packet networks

Fair scheduling of delay and rate-sensitive packet flows over a wireless channel is not addressed effectively by most contemporary wireline fair-scheduling algorithms because of two unique characteristics of wireless media: (1) bursty channel errors and (2) location-dependent channel capacity and errors. Besides, in packet cellular networks, the base station typically performs the task of packet scheduling for both downlink and uplink flows in a cell; however, a base station has only a limited knowledge of the arrival processes of uplink flows. We propose a new model for wireless fair-scheduling based on an adaptation of fluid fair queueing (FFQ) to handle location-dependent error bursts. We describe an ideal wireless fair-scheduling algorithm which provides a packetized implementation of the fluid mode, while assuming full knowledge of the current channel conditions. For this algorithm, we derive the worst-case throughput and delay bounds. Finally, we describe a practical wireless scheduling algorithm which approximates the ideal algorithm. Through simulations, we show that the algorithm achieves the desirable properties identified in the wireless FFQ model     

Weighted partial network coding and its applications in wireless mesh networks

Network coding (NC) has showed to be beneficial to improve transmission performance in wireless mesh networks. Random linear coding is usually applied as the default coding schema. However, random linear coding causes significant decoding delay and jitter at receiver. Further, current NC does not support weight assignment to original packets, which is however indispensable for popular applications such as quality of service control and multipath media streaming in wireless mesh networks. Partial network coding (PNC) can largely reduce decoding delay and receiving fluctuation while keeping the benefit of NC. However, PNC does not support weight‐based data replacement and weight assignment to original packets. In this work, we propose weighted partial network coding (WPNC), which is a generalized coding schema of PNC. WPNC inherits all merits of PNC and part of NC. With WPNC, both decoding delay and receiving fluctuation will be reduced as observed in PNC. Also, WPNC is quite suitable for those applications that require weight assignment to original packets. After providing the whole framework of WPNC and thorough theoretical analysis to its performance, we have demonstrated how WPNC can be integrated with quality of service control and multipath routing supported media streaming in wireless mesh networks. Performance of WPNC is inter‐validated by both theoretical analysis and numeric evaluations. Copyright © 2011 John; Wiley & Sons, Ltd.     

Provisioning of Parameterized Quality of Service in 802.11e Based Wireless Mesh Networks

There has been a growing interest in the use of wireless mesh networks. Today’s wireless technology enables very high data rate up to hundreds of Megabits per second, which creates the high demand of supporting real-time multimedia applications over wireless mesh networks. Hence it is imperative to support quality of service (QoS) in wireless mesh networks. In this paper, we design a framework to provide parameterized QoS in 802.11e based wireless mesh networks. Our framework consists of admission control algorithms and scheduling algorithms, which aim at supporting constant bit-rate (CBR) traffic flows, as well as variable bit-rate (VBR) traffic flows. We first present deterministic end-to-end delay bounds for CBR traffic. We then prove that the delay of VBR traffic can be bounded if the traffic flow conforms to a leaky-bucket regulator. We further study different admission control algorithms for VBR traffic. Our simulation results show that, by taking advantage of statistical multiplexing, much more traffic flows can be admitted.