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.     

A QoS aware joint design for wireless mesh networks

Wireless mesh networks (WMNs) provide Internet access to remote areas and wireless connections on a metropolitan scale. In this paper, we focus on the problem of improving the gateway throughput in WMNs while achieving fairness and supporting quality-of-service (QoS) differentiation for end-users. To address this problem, we propose a new distributed dynamic traffic scheduling algorithm that supports different QoS requirements from different users. We also develop a joint weight-aware channel assignment and minimum expected delay routing mechanism. Simulation results demonstrate the performance of the proposed work in terms of the achieved throughput and minimized packet loss ratio and delay.     

Performance analysis of adaptive MAC protocol in VANETs considering the potential impact on throughput and transmission delays

The existing adaptive multichannel medium access control (MAC) protocols in vehicular ad hoc networks can adjust themselves according to different vehicular traffic densities. These protocols can increase throughput and guarantee a bounded transmission delay for real‐time safety applications. However, the optimized control channel interval is computed based on the maximum throughput while ignoring the strict safety packet transmission delay requirements. In this paper, we analyze the effects of the throughput and strict safety packet transmission delay with adaptive multichannel MAC protocols, such as connectivity‐aware MAC (CA MAC), adaptive multi‐priority distributed MAC (APDM), multi‐priority supported p‐persistent MAC (MP MAC), and variable control channel interval MAC (VCI) protocols. The performance and analysis results show that: (a) under a low data rate condition, CA MAC does not guarantee a strict safety packet transmission delay; (b) APDM not only satisfies the safety packet transmission requirement, but also provides the lowest safety packet transmission delay; (c) under a high data rate condition, we suggest APDM for use as an adaptive MAC protocol because it allows for high throughput for nonsafety packets and preserves low safety packet transmission delay; (d) under a low data rate condition with various data packet sizes, we suggest MP MAC for high throughput, which satisfies the safety packet transmission requirement; and (e) under low vehicle density and low data rate conditions, VCI can support high throughput. A balance between transmission delay and throughput must be considered to improve the optimal efficiency, reliability, and adaptability.     

Stable‐path multi‐channel routing with extended level channel assignment

Wireless mesh networks (WMNs) have gained considerable popularity in recent times thanks to their self‐healing, self‐organizing, and self‐configuring nature. Because of their ability to provide high throughput and minimum packet delay, WMNs are considered to be favorable for broadband applications. For such applications, WMNs employ multiple channels, which give rise to issues like channel assignment, load balancing, and interference avoidance. Most of these issues fall into two broad categories, namely routing and channel assignment. For routing, we propose a novel proactive protocol, the stable‐path multi‐channel routing protocol (SMRP). Our proposed solution, to address channel assignment, is the extended level‐based channel assignment (ELCA) scheme. SMRP is designed to work in combination with ELCA in order to minimize interference and balance the load among the underlying nodes. Simulation results show enhanced throughput and minimal packet delay as compared with the contemporary schemes. Copyright © 2011 John Wiley & Sons, Ltd.     

Performance analysis of Finite-User slotted aloha in wireless networks with multiple packet reception and random traffic

In this paper, we propose an analytical approach for evaluating the performance of finite-user slotted Aloha in wireless networks with multiple packet reception and random traffic. We derive the exact values of the throughput, the average system size, the packet blocking probability, and the average system delay. Our analysis is based on probability theory. We show that our numerical results are identical to simulation results.     

GI/Geom/1 queue based on communication model for mesh networks

In mesh networks architecture, it should be permitted to visit the mobile client points. Whereas in mesh networks environment, the main throughput flows usually communicate with the conventional wired network. The so‐called gateway nodes can link directly to traditional Ethernet, depending on these mesh nodes, and can obtain access to data sources that are related to the Ethernet. In wireless mesh networks (WMNs), the quantities of gateways are limited. The packet‐processing ability of settled wireless nodes is limited. Consequently, throughput loads of mesh nodes highly affect the network performance. In this paper, we propose a queuing system that relied on traffic model for WMNs. On the basis of the intelligent adaptivenes, the model considers the influences of interference. Using this intelligent model, service stations with boundless capacity are defined as between gateway and common nodes based on the largest hop count from the gateways, whereas the other nodes are modeled as service stations with certain capacity. Afterwards, we analyze the network throughput, mean packet loss ratio, and packet delay on each hop node with the adaptive model proposed. Simulations show that the intelligent and adaptive model presented is precise in modeling the features of traffic loads in WMNs. Copyright © 2013 John Wiley & Sons, Ltd.     

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.     

无线网络中最小延迟代价网络编码的研究

网络编码能极大地提高网络吞吐量和传输可靠性.编码机会易受到数据包数量不公平性的影响,提出一个具有最小延迟代价的网络编码方法（MDCNC）.首先找到一条固定路由并确定该路由所经过的每一节点的编码能力,然后根据数据流在不同节点处以及不同时隙的可编码情况,灵活地应用该延迟发送策略,以牺牲较小的端到端延迟时间换取更多的编码机会.仿真结果表明,MDCNC能够带来更多的编码机会,进而使网络拥有更高的吞吐量.     

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.     

基于Markov状态转移方法的网络编码时延分析

网络编码已被验证是改善无线网络吞吐量、可靠性等性能的有效手段,但其对业务流时延性能影响的研究还不充分。针对得到广泛应用的随机线性网络编码,提出了一种基于马尔可夫状态转移的方法对单跳场景下单播业务流时延的期望值以及概率分布进行了分析,同时给出了相应的递推解析式,然后数值分析了有限域大小、信道丢失率、编码批次大小等编码参数对时延的影响。结果表明,随着有限域q的增大,时延的方差不断变小;时延的期望值与信道丢失率、编码批次大小几乎都成线性关系。     

一种适用于虚拟机网络的数据包高效传输方法

为了提高数据包在云计算数据中心中基于虚拟机构成网络中的传输性能,提出了一种基于网络编码的高效数据包传输方法.基于网络编码机制,采用对传输过程中丢失数据包高效的编码组合策略,多个虚拟机终端可以在一次多播或广播传输中获取多个从交换机优先传输的数据包,因此,提出的方法可以提高基于虚拟机网络的多播及广播业务的数据包传输延迟,并提高多播及广播业务的网络吞吐量.仿真结果表明提出的方法在典型信道条件下均获得了较好的数据包传输时延及网络吞吐量性能.     

Hierarchy schedule-sensing protocol for CDMA wireless data-centric networks with multiple packet collision and capture effect

This paper focuses on performance analysis of a CDMA wireless data network based on hierarchy schedule-sensing (HSS) protocol, in which a common-code permission frame beacon is used to schedule request transmissions to avoid packet collisions. To further reduce scheduling delay, hierarchical group-based coding is adopted in the scheme. The performance of such a network is evaluated considering packet collisions with and without packet capture effect using a two-dimensional Markovian chain model. In particular, this paper will study the impact of multiple packet-collision effect on network performance with the help of the average packet-collision rate derived explicitly in the paper. The obtained results show that, despite its low implementation complexity, the HSS protocol is a fairly robust medium-access control protocol featuring uniformly high throughput and short delay even under very high traffic load, which especially suits data-centric wireless networks with relatively small coverage area and great node density.     

Wireless Packet Scheduling Algorithm for OFDMA System Based on Time‐Utility and Channel State

In this paper, we propose an urgency‐ and efficiencybased wireless packet scheduling (UEPS) algorithm that is able to schedule real‐time (RT) and non‐real‐time (NRT) traffics at the same time while supporting multiple users simultaneously at any given scheduling time instant. The UEPS algorithm is designed to support wireless downlink packet scheduling in an orthogonal frequency division multiple access (OFDMA) system, which is a strong candidate as a wireless access method for the next generation of wireless communications. The UEPS algorithm uses the time‐utility function as a scheduling urgency factor and the relative status of the current channel to the average channel status as an efficiency indicator of radio resource usage. The design goal of the UEPS algorithm is to maximize throughput of NRT traffics while satisfying quality‐of‐service (QoS) requirements of RT traffics. The simulation study shows that the UEPS algorithm is able to give better throughput performance than existing wireless packet scheduling algorithms such as proportional fair (PF) and modifiedlargest weighted delay first (M‐LWDF), while satisfying the QoS requirements of RT traffics such as average delay and packet loss rate under various traffic loads.     

Buffered fixed routing: a routing protocol for real-time transportin grid networks

We propose a new routing protocol called buffered fixed routing (BFR) for real-time applications on grid networks. While previous routing protocols for grid networks have been designed to improve network throughput, the BFR scheme is proposed to guarantee the end-to-end packet delay and sequencing without loss by using finite buffers at each node. Thus the proposed scheme can satisfy quality-of-service (QoS) requirements of real-time applications. The BFR scheme uses the token on the row ring to provide QoS guarantees. The performance of the BFR scheme is analyzed by using the Geom/Geom/1 queueing system under uniform traffic. In the simulation, the BFR scheme shows the zero-loss, high-throughput performance with the minimum delay variation compared to other routing protocols such as store and forward routing, deflection routing and vertical routing. In addition, it has shown the smallest average delay at intermediate and heavy loads     

Interference management using basestation coordination in broadband wireless access networks

This paper proposes a transmission‐scheduling algorithm for interference management in broadband wireless access networks. The algorithm aims to minimize the cochannel interference using basestation coordination while still maintaining the other quality of service (QoS) requirements such as packet delay, throughput and packet loss. The interference reduction is achieved by avoiding (or minimizing) concurrent transmission of potential dominant interferers. Dynamic slot allocation based on traffic information in other cells/sectors is employed. In order to implement the algorithm in a distributed manner, basestations (BSs) have to exchange traffic information. Both real‐time and non‐real‐time services are considered in this work. Results show that significant reduction in the packet error rate can be achieved without increasing the packet delay at low to medium loading values and with a higher but acceptable packet delay at high loading values. Since ARQ schemes can also be used for packet error rate reduction, we compare the performance of the proposed scheme with that of ARQ. Results indicate that although ARQ is more effective in reducing packet error rate, the proposed algorithm incurs much less packet delay particularly at medium to high loading. Copyright © 2006 John Wiley & Sons, Ltd.     

Contention-based MAC protocols with erasure coding for wireless data networks

Contention-based medium access control (MAC) protocol is a key component for the success of wireless data networks. Conventional random access protocols like ALOHA and Carrier Sense Multiple Access (CSMA) suffer from packet collision which leads to low throughput. Aimed at improving the throughput performance, we propose to integrate erasure coding with contention-based MAC protocols for recovering collided packets. To demonstrate the effectiveness of this approach, we focus on combining erasure coding with slotted ALOHA and slotted non-persistent CSMA in this paper. The performances of the resulting protocols are evaluated by both analytical model and simulation. Simulation results match very well with analytical results and show that the system throughput is increased for low to medium traffic loading. Packet loss ratio is also improved considerably with our scheme when the maximum number of packet retransmission times is limited. However, the delay for our scheme is higher due to the longer waiting time in our scheme for recovering collided packets. It is also shown that delay can be significantly reduced if we choose appropriate coding parameters though throughput will be sacrificed.     

QoS‐based radio network dimensioning for LTE networks with heavy real‐time traffic

Applications of video streaming and real‐time gaming, which generate large amounts of real‐time traffic in the network, are expected to gain considerable popularity in Long Term Evolution networks. Maintaining the QoS such as packet delay, packet loss ratio, median, and cell border throughput requirements in networks dominated by real time traffic, is critical. The existing dimensioning methodology does not consider QoS parameters of real‐time traffic in network dimensioning. Moreover, exhaustive and time‐consuming simulations are normally required to evaluate the performance and QoS of real‐time services. To overcome this problem, we propose an improved radio network dimensioning framework that considers the QoS of real‐time traffic in network dimensioning. In this framework, an analytical model is proposed to evaluate the capacity and performance of real‐time traffic dominant Long Term Evolution networks. The proposed framework provides a fast and accurate means of finding the trade‐off between system load, packet delay, packet loss ratio, required median, and cell border throughput. It also provides network operators with an analytical means for obtaining the minimum number of sites required by jointly considering coverage, capacity and QoS requirements. The accuracy of the proposed model is validated through simulations. Copyright © 2012 John Wiley & Sons, Ltd.     

Mini‐Slot‐Based Transmission Scheme for Local Customer Internetworking in PONs

We propose a new mini‐slot transmission scheme for a passive optical network (PON) in which each customer can be switched either to access mode or to internetworking mode dynamically. In this paper, we present the system implementation (called LAN‐PON) as well as the performance of the proposed transmission scheme to illustrate its feasibility and benefits. A mini‐slot scheme can rapidly reduce the queuing delay, which increases due to the flooding of the deflected packets in a deflection scheme. We evaluate the impact of mode switching time on the bandwidth gain (throughput) and delay of local area network (LAN) traffic in the LAN‐PON with a mini‐slot scheme. We also analyze a theoretical delay model of the proposed scheme. The simulation results demonstrate that switching time has an impact on LAN performance, and the average packet delay of the proposed scheme is significantly improved compared to that of the deflection scheme.     

基于预测的机会式网络编码

针对理论网络编码在实际应用上的缺陷,以及现有机会式网络编码完全依赖于消息偷听导致应用场合的局限性,以完全不同于网络编码优化问题的思路,提出了基于预测的机会式网络编码的方法。其主要思想是：基于网络流量的自相似性,利用EMD（empirical mode decomposition, 经验模式分解）和ARMA（自回归滑动平均）预测下一个报文的到达时间,综合计算编码时间、为了编码而等待的时间、传输时间等要素,从而决定是否编码。推导出了网络编码在不同情况下要实现吞吐量正增益可以等待的时间上界。仿真实验结果显示,在吞吐量上,提出的方法相对于理论网络编码平均提高15%左右,相对于当前的存储转发平均提高21%左右。在提高吞吐量的基础上,提出方法也可有效地降低网络的能量消耗。     

Star-Structure Network Coding for Multiple Unicast Sessions in Wireless Mesh Networks

In this paper, first, we propose Star-NC, a new network coding (NC) scheme for multiple unicast sessions in an n-input n-output star structure. Then, we evaluate the network throughput of this coding scheme in wireless mesh network over the traditional non-NC transmission. Our scheme benefits from the proximity of all the nodes around the relay node and employs a more general form of overhearing different from other schemes such as COPE. We found that the gain of our NC scheme depends on both the star size and the routing pattern of the unicast transmissions. Based on this, we identify both the situations which the maximum gain is achievable and a lower bound for the expected value of the gain in the case of random routing pattern. Next, we propose an analytical framework for studying throughput gain of our Star-NC scheme in general wireless network topologies. Our theoretical formulation via linear programming provides a method for finding source-destination routes and utilizing the best choices of our NC scheme to maximize the throughput. Finally, we evaluate our model for various networks, traffic models and routing strategies over coding-oblivious routing. We also compare the throughput gain of our scheme with COPE-type NC scheme. We show that Star-NC exploits new coding opportunities different from COPE-type NC and thus can be used with or without this scheme. The results show that Star-NC has often better performance than COPE for a directional traffic model which is a typical model in wireless mesh networks. Moreover, we found that, joint Star and COPE-type NC has better throughput performance than each of Star or COPE alone.