The Maximum Throughput of A Wireless Multi-Hop Path

In this paper, the maximum end-to-end throughput that can be achieved on a wireless multi-hop path is investigated analytically. The problem is modeled using the conflict graph, where each link in the multi-hop path is represented uniquely by a vertex in the conflict graph and two vertices are adjacent if and only if the associated links mutually interfere. Using the conflict graph and the linear programming formulations of the problem, we analyzed the maximum end-to-end throughput of a wireless multi-hop path a) in a simple scenario where nodes are optimally placed and each node can only interfere with the transmission of its adjacent nodes along the path, and b) in a more complicated scenario where nodes are randomly placed and each node can interfere with the transmission of any number of nearby nodes along the path in both a) an error free radio environment and b) an erroneous radio environment. The maximum end-to-end throughputs for each of the above four scenarios are obtained analytically. We show that the maximum achievable end-to-end throughput is determined by the throughput of its bottleneck clique, where a clique is a maximal set of mutually adjacent vertices in the associated conflict graph. Further our analysis suggests the optimum scheduling algorithm that can be used to achieve the maximum end-to-end throughput and that it is convenient to use the (maximal) independent sets as the basic blocks for the design of scheduling algorithms. The findings in this paper lay guidelines for the design of optimum scheduling algorithms. They can be used to design computationally efficient algorithms to determine the maximum throughput of a wireless multi-hop path and to design a scheduling algorithm to achieve that throughput.     

Urgency-based packet scheduling and routing algorithms for delay-sensitive data over MANETs

This paper proposes urgency-based packet scheduling and routing algorithms to effectively deliver delay-sensitive data over a multi-hop mobile ad hoc networks supporting IEEE 802.11 multi-rate service. First, packet urgency, node urgency, and route urgency are defined on the basis of the end-to-end delay requirement. Based on these urgency metrics and the estimated transmission delay of each packet by Kalman filter, the proposed packet scheduling algorithm determines the transmission order and drop policy to minimize the node urgency without unnecessary packet drop, and the proposed routing algorithm establishes a route to minimize the derivative of route urgency in order to maximize the number of packets delivered within the required end-to-end delay. Finally, experimental results are presented to evaluate the performance of the proposed joint working algorithms.     

Cross-Layer Design of 2D Queuing Model for Multi-hop Wireless Networks

Based on cross-layer design, a modified 2-dimensional queuing model (2DQM) is proposed in this paper to tackle the problem of end-to-end quality of service (QoS) metric calculation. This model exploits the traffic arrival process, multi-rate transmission in the physical layer and error recovery technology with the protocol of truncated automatic repeat request in the data link layer. Based on this model, QoS metrics of wireless links can be evaluated hop by hop. The model can be used in more realistic scenarios of multi-hop wireless networks, although the computational complexity of 2DQM is slightly higher compared with existing 1-dimensional queuing model. Simulation results indicate that the proposed model can estimate the end-to-end packet loss-rate and average delay more accurately than existing models, and a model based QoS routing algorithm can find routes with better QoS performance (with lower end-to-end packet loss-rate and delay).     

Capacity Optimization in TDMA Ad-Hoc Networks

Many scheduling techniques have been developed to solve the problem of sharing the common channel to multiple stations. TDMA has been increasingly used as a scheduling technique in ad-hoc networks. The current trend for QoS capable applications led to the deployment of numerous routing schemes that use TDMA. These schemes try to solve the problem of distributing the available slots among the wireless nodes and at the same time, to find paths within the network that fulfill some QoS related limitations, such as end-to-end delay. The exact way the slots are distributed among the transmitting nodes has an impact on the end-to-end delay and other performance parameters of the network, such as capacity. Therefore, the efficiency of the scheduling algorithms is closely related to the network topologies. In this paper, we propose two new end-to-end TDMA scheduling algorithms that try to enhance the network capacity by increasing the number of concurrent connections established in the network, without causing additional end-to-end delay. We study the efficiency of the proposed algorithms, when applied on various random topologies, and compare them in terms of end-to-end delay and network capacity.     

Multi-hop Delay Performance in Wireless Mesh Networks

Wireless Mesh Network (WMN) technology is an attractive solution to meet the demand of broadband network access anywhere and anytime. In order to effectively support delay-sensitive applications such as video streaming and interactive gaming in a WMN, it is crucial to develop feasible methodologies and techniques for accurately analyzing, predicting and guaranteeing end-to-end delay performance over multi-hop wireless communication paths. In this paper, we extend the link-layer effective capacity model and derive a lower bound of delay-bound violation probability, or complementary cumulative distribution function, over multi-hop wireless connections. A fluid traffic model with cross traffic and a Rayleigh fading channel with additive Gaussian noise and Doppler spectrum are considered in our study. The average multi-hop delay and jitter performance bounds are also obtained. Analytical results are verified by extensive computer simulations under different traffic load and wireless channel conditions. We find that multi-hop delay performance is much more sensitive to traffic load and maximum Doppler rate than traffic correlation.     

TDMA scheduling algorithms for wireless sensor networks

Algorithms for scheduling TDMA transmissions in multi-hop networks usually determine the smallest length conflict-free assignment of slots in which each link or node is activated at least once. This is based on the assumption that there are many independent point-to-point flows in the network. In sensor networks however often data are transferred from the sensor nodes to a few central data collectors. The scheduling problem is therefore to determine the smallest length conflict-free assignment of slots during which the packets generated at each node reach their destination. The conflicting node transmissions are determined based on an interference graph, which may be different from connectivity graph due to the broadcast nature of wireless transmissions. We show that this problem is NP-complete. We first propose two centralized heuristic algorithms: one based on direct scheduling of the nodes or node-based scheduling, which is adapted from classical multi-hop scheduling algorithms for general ad hoc networks, and the other based on scheduling the levels in the routing tree before scheduling the nodes or level-based scheduling, which is a novel scheduling algorithm for many-to-one communication in sensor networks. The performance of these algorithms depends on the distribution of the nodes across the levels. We then propose a distributed algorithm based on the distributed coloring of the nodes, that increases the delay by a factor of 10–70 over centralized algorithms for 1000 nodes. We also obtain upper bound for these schedules as a function of the total number of packets generated in the network.     

QoS-guaranteed packet scheduling in wireless networks

To guarantee the quality of service (QoS) of a wireless network, a new packet scheduling algorithm using cross-layer design technique is proposed in this article. First, the demand of packet scheduling for multimedia transmission in wireless networks and the deficiency of the existing packet scheduling algorithms are analyzed. Then the model of the QoS-guaranteed packet scheduling (QPS) algorithm of high speed downlink packet access (HSDPA) and the cost function of packet transmission are designed. The calculation method of packet delay time for wireless channels is expounded in detail, and complete steps to realize the QPS algorithm are also given. The simulation results show that the QPS algorithm that provides the scheduling sequence of packets with calculated values can effectively improve the performance of delay and throughput.     

基于剩余路径跳数的动态优先调度实现区分服务EF PHB

Internet区分服务（DiiffServ）中EF PHB(Expedited Forwarding Per Hop Behavior)提供严格的端到端延迟保证，其实现机制和性能是当前研究的热点。随着可扩展性成为核心网络考虑的关键因素，一般用简单的FIFO高度实现EF PHB。FIFO实现问题在于最坏的端到端延迟与流经历的最大跳数成正比，结果降低了网络最坏延迟性能，并影响了整个网络的总体利用率。文章在分析并比较FIFO实现以及考虑流跳数因素的绝对跳数优先（HBAP）实现、相对跳数优先（HBRP）实现的延迟性能基础上，提出了用基于剩余路径跳数的动态优先（DHBP）调度实现EF PHB。理论分析和实验结果表明，基于剩余路径跳数的动态优先调度算法可以平衡不同跳数流的端到端延迟性能，从而减小网络最坏的端到端延迟，并有效地提高了网络 选用率，最坏延迟性能明显优于FIFO和绝对跳数优先调度，与性能最优的相对跳数优先调度相似，并将计算复杂度降为0(1)。     

Tandem Queue Models with Applications to QoS Routing in Multihop Wireless Networks

We consider the problem of quality of service (QoS) routing in multi-hop wireless networks where data are transmitted from a source node to a destination node via multiple hops. The routing component of a QoS-routing algorithm essentially involves the link and path metric calculation which depends on many factors such as the physical and link layer designs of the underlying wireless network, transmission errors due to channel fading and interference, etc. The task of link metric calculation basically requires us to solve a tandem queueing problem which is the focus of this paper. We present a unified tandem queue framework which is applicable for many different physical layer designs. We present both exact and approximated decomposition approaches. Using the queueing framework, we can derive different performance measures, namely, end-to-end loss rate, end-to-end average delay, and end-to-end delay distribution. The proposed decomposition approach is validated and some interesting insights into the system performance are highlighted. We then present how to use the decomposition queueing approach to calculate the link metric and incorporate this into the route discovery process of the QoS routing algorithm. The extension of the queueing and QoS routing framework to wireless networks with class-based queueing for QoS differentiation is also presented.     

Delay Aware Link Scheduling for Multi-Hop TDMA Wireless Networks

Time division multiple access (TDMA) based medium access control (MAC) protocols can provide QoS with guaranteed access to the wireless channel. However, in multi-hop wireless networks, these protocols may introduce scheduling delay if, on the same path, an outbound link on a router is scheduled to transmit before an inbound link on that router. The total scheduling delay can be quite large since it accumulates at every hop on a path. This paper presents a method that finds conflict-free TDMA schedules with minimum scheduling delay. We show that the scheduling delay can be interpreted as a cost, in terms of transmission order of the links, collected over a cycle in the conflict graph. We use this observation to formulate an optimization, which finds a transmission order with the min-max delay across a set of multiple paths. The min-max delay optimization is NP-complete since the transmission order of links is a vector of binary integer variables. We devise an algorithm that finds the transmission order with the minimum delay on overlay tree topologies and use it with a modified Bellman-Ford algorithm, to find minimum delay schedules in polynomial time. The simulation results in 802.16 mesh networks confirm that the proposed algorithm can find effective min-max delay schedules.     

无线多跳网络的自适应容量感知优化与控制技术

In wireless multimedia communications, it is extremely difficult to derive general end-to-end capacity results because of decentralized packet scheduling and the interference between communi-cating nodes. In this paper, we present a state-based channel capacity perception scheme to provide sta-tistical Quality-of-Service (QoS) guarantees under a medium or high traffic load for IEEE 802.11 wire-less multi-hop networks. The proposed scheme first perceives the state of the wireless link from the MAC retransmission information and extends this information to calculate the wireless channel capaci-ty, particularly under a saturated traffic load, on the basis of the interference among flows and the link state in the wireless multi-hop networks. Finally, the adaptive optimal control algorithm allocates a net-work resource and forwards the data packet by tak-ing into consideration the channel capacity deploy-ments in multi-terminal or multi-hop mesh net-works. Extensive computer simulations demonstrate that the proposed scheme can achieve better per-formance in terms of packet delivery ratio and net-work throughput compared to the existing capacity prediction schemes.     

A novel statistical and distributed CAC algorithm for IEEE 802.11 based single and multi-hop wireless ad hoc networks

In this paper, we propose a statistical Call Admission Control (CAC) schemes for single and multi-hop IEEE 802.11 based wireless ad hoc networks. Unlike most papers which consider average end-to-end delay, our algorithm guarantees statistical delay that would be more efficient for real time multimedia applications. We use Effective Bandwidth/Effective Capacity theory to compute delay bound stochastically in each hop. The proposed distributed CAC algorithm is suitable for ad hoc networks. Also, with a few changes, it has been implemented in the AODV routing protocol. Simulation results demonstrate that proposed CAC algorithm works efficiently in both single and multi-hop networks. Moreover, we investigated our algorithm with aggregated traffic and the result shows that the algorithm performed accurately under that condition.     

Evaluating the impact of network density,hidden nodes and capture effect for throughput guarantee in multi-hop wireless networks

To optimize the performance of wireless networks, one needs to consider the impact of key factors such as interference from hidden nodes, the capture effect, the network density and network conditions (saturated versus non-saturated). In this research, our goal is to quantify the impact of these factors and to propose effective mechanisms and algorithms for throughput guarantees in multi-hop wireless networks. For this purpose, we have developed a model that takes into account all these key factors, based on which an admission control algorithm and an end-to-end available bandwidth estimation algorithm are proposed. Given the necessary network information and traffic demands as inputs, these algorithms are able to provide predictive control via an iterative approach. Evaluations using analytical comparison with simulations as well as existing research show that the proposed model and algorithms are accurate and effective.     

面向航天器有线无线混合场景的流调度机制研究

随着各国深空探测任务的开展,空间站的建设需求日益增加,而航天器内部大量的数据通信总线在一定程度上影响了航天器的有效载荷。因此,该文将无线通信方式引入到航天器通信系统设计中,但传统无线通信难以保障时敏数据的端到端传输时延,该文提出了一种有线无线融合的时间敏感网络(TSN)流调度方案。设计了一种上下行时隙分离的TDMA时隙分配机制,通过对航天器内部业务类型与有线无线融合传输链路的时延关系进行建模分析,构建了以时敏业务平均端到端时延最小的目标函数,采用粒子群算法对时隙分配方案进行快速求解。最后在Pycharm平台对所提算法进行对比测试,并在EXata网络仿真平台搭建航天传感器采集网络进行验证。实验结果表明,该文所提出的有线无线融合流调度方案能为时敏业务提供稳定、有界的时延保障。     

Distributed Priority Scheduling and Medium Access in Ad Hoc Networks

Providing Quality-of-Service in random access multi-hop wireless networks requires support from both medium access and packet scheduling algorithms. However, due to the distributed nature of ad hoc networks, nodes may not be able to determine the next packet that would be transmitted in a (hypothetical) centralized and ideal dynamic priority scheduler. In this paper, we develop two mechanisms for QoS communication in multi-hop wireless networks. First, we devise distributed priority scheduling, a technique that piggybacks the priority tag of a node's head-of-line packet onto handshake and data packets; e.g., RTS/DATA packets in IEEE 802.11. By monitoring transmitted packets, each node maintains a scheduling table which is used to assess the node's priority level relative to other nodes. We then incorporate this scheduling table into existing IEEE 802.11 priority backoff schemes to approximate the idealized schedule. Second, we observe that congestion, link errors, and the random nature of medium access prohibit an exact realization of the ideal schedule. Consequently, we devise a scheduling scheme termed multi-hop coordination so that downstream nodes can increase a packet's relative priority to make up for excessive delays incurred upstream. We next develop a simple analytical model to quantitatively explore these two mechanisms. In the former case, we study the impact of the probability of overhearing another packet's priority index on the scheme's ability to achieve the ideal schedule. In the latter case, we explore the role of multi-hop coordination in increasing the probability that a packet satisfies its end-to-end QoS target. Finally, we perform a set of ns-2 simulations to study the scheme's performance under more realistic conditions.     

A Delay-Tolerant Virtual Tunnel Scheme for Asynchronous MAC protocols in WSN

Typically, asynchronous MAC protocols are used to monitor a significant facility for rare events or to detect an intrusion in wireless sensor networks. Moreover, asynchronous MAC protocols can achieve high energy efficiency due to the fact that there is no periodic control frame. However, asynchronous MAC protocols have the problem of long end-to-end delay time caused by the absence of precedent time synchronization per link. This paper proposes a new scheme, called virtual tunnel (VT), which can reduce the delivery delay of asynchronous MAC protocols in multi-hop environment. The VT scheme can achieve approximated duty cycle synchronization with on-demand approach. In this scheme, through the estimation of next wakeup time of peer node, without exceptional process, each node on the transmission path can improve end-to-end delay in multi-hop topologies. And it becomes low power consumption by reducing unnecessary retransmissions. Additionally, we devise the protection method of VT. In our simulation results, end-to-end delay according to hop counts and traffic amount is compared with the X-MAC that is an asynchronous protocol recently developed. Furthermore, it is shown that the VT scheme decreases energy consumption due to the lower end-to-end delay than the X-MAC in multi-hop topologies.     

Distributed scheduling based on polling policy with maximal spatial reuse in multi-hop WMNs

The scheduling algorithm based on the three-way handshaking scheme in IEEE 802.16d-2004 standard has some serious problems because of the complexity of the algorithm and low scheduling efficiency.To enhance the scheduling efficiency and improve the performance of multi-hop wireless mesh networks (WMNs), one distributed scheduling algorithm that can maximize the spatial and time reuse with an interference-based network model is proposed.Compared to the graph-based network model, the proposed network model can achieve a better throughput performance with maximal spatial reuse.Furthermore, this proposed scheduling algorithm also keeps fairly scheduling to all links, with a priority-based polling policy.Both the theoretical analysis and simulation results show that this proposed distributed scheduling algorithm is simple and efficient.     

分布式队列服务算法在无线网状网包调度中的应用

根据无线网状网的包调度特点,结合已有的差分队列服务算法和分布式贝尔曼-福特算 法,将有线网络中的差分队列服务算法改进为分布式队列服务算法（DQS）,使之实用于无 线网状网中多任务条件下实现系统的吞吐量最大化。仿真实验证明了DQS算法能有效地避免 传统多径传输中的按“类”或 “流”来进行调度的缺陷,有效地减少了数据包的端到端 延时和缓冲区需求,尤其是DQS算法的实际平均吞吐量性能有了很大的提高。     

Efficient multi-hop scheduling algorithms for packet transmissions in WDM optical star networks

This paper proposes multi-hop scheduling algorithms for the All-to-All Broadcast (AAB) problem in Wavelength Division Multiplexed (WDM) optical star networks. The multi-hop AAB problem can be split into two subproblems: Logical Topologies Construction (LTC) problem, and Transmission Scheduling (TS) problem. For improving the efficiency of multi-hop scheduling, we focus on a new multi-hop transmission model and transfer the LTC problem to a special case of the Round Robin Tournament (RRT) problem. In the proposed logical topologies, our multi-hop scheduling algorithms can easily overlap the tuning latency and reduce the number of tuning operations on each node. We compare our results with previous research in terms of schedule length. Overall results indicate that our multi-hop scheduling algorithms have better performance than previous algorithms.