The flexibility of wireless communication makes it more and more widely used in industrial scenarios. To satisfy the strict real-time requirements of industry, various wireless methods especially based on the time division multiple access protocol have been introduced. In this work, we first conduct a mathematical analysis of the network model and the problem of minimum packet loss. Then, an optimal Real-time Scheduling algorithm based on Backtracking method (RSBT) for industrial wireless sensor networks is proposed; this yields a scheduling scheme that can achieve the lowest network packet loss rate. We also propose a suboptimal Real-time Scheduling algorithm based on Urgency and Concurrency (RSUC). Simulation results show that the proposed algorithms effectively reduce the rate of the network packet loss and the average response time of data flows. The real-time performance of the RSUC algorithm is close to optimal, which confirms the computation efficiency of the algorithm.

Regression testing is essential for assuring the quality of a software product. Because rerunning all test cases in regression testing may be impractical under limited resources, test case prioritization is a feasible solution to optimize regression testing by reordering test cases for the current testing version. In this paper, we propose a novel test case prioritization approach that combines the clustering algorithm and the scheduling algorithm for improving the effectiveness of regression testing. By using the clustering algorithm, test cases with same or similar properties are merged into a cluster, and the scheduling algorithm helps allocate an execution priority for each test case by incorporating fault detection rates with the waiting time of test cases in candidate set. We have conducted several experiments on 12 C programs to validate the effectiveness of our proposed approach. Experimental results show that our approach is more effective than some well studied test case prioritization techniques in terms of average percentage of fault detected (APFD) values.

For an efficient processing of large data in a distributed system, Hadoop MapReduce performs task scheduling such that tasks are distributed with consideration of the data locality. The data locality, however, is limitedly exploited, since it is pursued one node at a time basis without considering the global optimality. In this paper, we propose a novel task scheduling algorithm that globally considers the data locality. Through experiments, we show our algorithm improves the performance of MapReduce in various situations.

With the growth of cloud-based services, cloud data centers are experiencing large growth. A key component in a cloud data center is the network technology deployed. In particular, Ethernet technology, commonly deployed in cloud data centers, is already envisioned for 10 Tbps Ethernet. In this paper, we study and analyze the makespan, workload execution times, and virtual machine migrations as the network speed increases. In particular, we consider homogeneous and heterogeneous data centers, virtual machine scheduling algorithms, and workload scheduling algorithms. Results obtained from our study indicate that the increase in a network's speed reduces makespan and workloads execution times, while aiding in the increase of the number of virtual machine migrations. We further observed that the number of migrations' behaviors in relation to the speed of the networks also depends on the employed virtual machines scheduling algorithm.

Non-orthogonal multiple access (NOMA) utilizing the power domain and advanced receiver has been considered as one promising multiple access technology for further cellular enhancements toward the 5th generation (5G) mobile communications system. Most of the existing investigations into NOMA focus on the combination of NOMA with orthogonal frequency division multiple access (OFDMA) for either downlink or uplink. In this paper, we investigate NOMA for uplink with single carrier-frequency division multiple access (SC-FDMA) being used. Differently from OFDMA, SC-FDMA requires consecutive resource allocation to a user equipment (UE) in order to achieve low peak to average power ratio (PAPR) transmission by the UE. Therefore, sophisticated designs of scheduling algorithm for NOMA with SC-FDMA are needed. To this end, this paper investigates the key issues of uplink NOMA scheduling such as UE grouping method and resource widening strategy. Because the optimal schemes have high computational complexity, novel schemes with low computational complexity are proposed for practical usage for uplink resource allocation of NOMA with SC-FDMA. On the basis of the proposed scheduling schemes, the performance of NOMA is investigated by system-level simulations in order to provide insights into the suitability of using NOMA for uplink radio access. Key issues impacting NOMA performance are evaluated and analyzed, such as scheduling granularity, UE number and the combination with fractional frequency reuse (FFR). Simulation results verify the effectiveness of the proposed algorithms and show that NOMA is a promising radio access technology for 5G systems.

In Worldwide interoperability for Microwave Access (WiMAX) network, QoS(quality of service) is provided for service flows. For this, five classes of services are defined in IEEE 802.16. They are Unsolicited Grant Service (UGS), Extended Real-Time Polling Service (ertPS), Real-Time Polling Service (rtPS), Non Real-Time Polling Service (nrtPS) and Best Effort (BE). For real-time classes, the sent packet has a deadline. As the transmission delay is over the limitation of deadline, the packet becomes useless and will be discarded. Thus, they will be served earlier and have higher probability. Nevertheless, non-real-time packets need also to be served from time to time. The scheduler should assign proper bandwidth for non-real-time flows and send the real-time packets before they are discarded. To deicide the right allocated bandwidth, the arrival rate of each flow is a good parameter for assignment. The average µ and standard deviation σ of arrival rate correspond to the long term need and variation of load for one flow. Thus, we proposed a scheduling algorithm named BAcSOA in which µ+kσ is used as a reference to allocate bandwidth with weighted round robin for one flow [5]. Different classes of flows will be given different values of k which corresponds to the priorities of classes. In this algorithm, flow with higher priority should have larger value of k. The value of k will decide the performance of this class. In this paper, we revise the algorithm to EBAcSOA and propose a mathematical way to decide the value of k for a required performance. Then, a simulation platform is proposed to decide k such that a required performance can be obtained for an operating system. This approach may be different from other researches in which there is no required performance and the performance results are obtained only for several operating points. However, the approach proposed is more practical from the view of an operator and may become an attractive point for other researchers.

Support of incoming traffic differentiation and Quality of Service (QoS) assurance is very important for the development of high performance packet switches, capable of separating traffic flows. In our previous paper, we proposed the implementation of two buffers at each crosspoint of a crossbar fabric that leads to the Dual Crosspoint Queued (DCQ) switch. Inside DCQ switch, one buffer is used to store the real-time traffic and the other for the non-real-time traffic. We also showed that the static priority algorithms can provide the QoS only for the real-time traffic due to their greedy nature that gives the absolute priority to that type of traffic. In order to overcome this problem, in our paper we propose the DCQ switch with the Largest Weighted Occupancy First scheduling algorithm that provides the desired QoS support for both traffic flows. Detailed analysis of the simulation results confirms the validity of proposed solution.

Wireless sensor nodes are becoming more and more common in various settings and require a long battery life for better maintainability. Since most sensor nodes are powered by batteries, energy efficiency is a critical problem. In an experiment, we observed that when peak power consumption is high, battery voltage drops quickly, and the sensor stops working even though some useful charge remains in the battery. We propose three off-line algorithms that extend battery life by scheduling sensors' execution time that is able to reduce peak power consumption as much as possible under a deadline constraint. We also developed a simulator to evaluate the effectiveness of these algorithms. The simulation results showed that one of the three algorithms dramatically can extend battery life approximately three time as long as in simultaneous sensor activation.

Most large-scale Peer-to-Peer (P2P) live streaming systems are constructed as a mesh structure, which can provide robustness in the dynamic P2P environment. The pull scheduling algorithm is widely used in this mesh structure, which degrades the performance of the entire system. Recently, network coding was introduced in mesh P2P streaming systems to improve the performance, which makes the push strategy feasible. One of the most famous scheduling algorithms based on network coding is R2, with a random push strategy. Although R2 has achieved some success, the push scheduling strategy still lacks a theoretical model and optimal solution. In this paper, we propose a novel optimal pull-push scheduling algorithm based on network coding, which consists of two stages: the initial pull stage and the push stage. The main contributions of this paper are: 1) we put forward a theoretical analysis model that considers the scarcity and timeliness of segments; 2) we formulate the push scheduling problem to be a global optimization problem and decompose it into local optimization problems on individual peers; 3) we introduce some rules to transform the local optimization problem into a classical min-cost optimization problem for solving it; 4) We combine the pull strategy with the push strategy and systematically realize our scheduling algorithm. Simulation results demonstrate that decode delay, decode ratio and redundant fraction of the P2P streaming system with our algorithm can be significantly improved, without losing throughput and increasing overhead.

In multiple-input multiple-output (MIMO) systems, the multiuser MIMO (MU-MIMO) systems have the potential to provide higher channel capacity owing to multiuser and spatial diversity. Block diagonalization (BD) is one of the techniques to realize MU-MIMO systems, where multiuser interference can be completely cancelled and therefore several users can be supported simultaneously. When the number of multiantenna users is larger than the number of simultaneously receiving users, it is necessary to select the users that maximize the system capacity. However, computation complexity becomes prohibitive, especially when the number of multiantenna users is large. Thus simplified user scheduling algorithms are necessary for reducing the complexity of computation. This paper proposes a simplified capacity-based user scheduling algorithm, based on analysis of the capacity-based user selection criterion. We find a new criterion that is simplified by using the properties of Gram-Schmidt orthogonalization (GSO). In simulation results, the proposed algorithm provides higher sum rate capacity than the conventional simplified norm-based algorithm; and when signal-to-noise power ratio (SNR) is high, it provides performance similar to that of the conventional simplified capacity-based algorithm, which still requires high complexity. Fairness of the users is also taken into account. With the proportionally fair (PF) criterion, the proposed algorithm provides better performance (sum rate capacity or fairness of the users) than the conventional algorithms. Simulation results also shows that the proposed algorithm has lower complexity of computation than the conventional algorithms.

The aggregate throughput of wireless mesh networks (WMNs) can be significantly improved by equipping the mesh routers with multiple radios tuned to orthogonal channels. Not only the links using orthogonal channels can be activated at a time, but some links in the same channel also can be activated concurrently if the Signal-to-Interference-and-Noise Ratio (SINR) at their receivers is not lower than the threshold, which is the spatial-reuse characteristic. STDMA is considered as one of the medium access schemes that can exploit spatial reuse to improve network throughput. Past studies have shown that optimizing the performance of STDMA is NP-Hard. Therefore, we propose a STDMA-based scheduling algorithm that operates in a greedy fashion for WMNs. We show that the proposed algorithm enhances not only the throughput but also the fairness by capturing the essence of spatial-reuse approach of STDMA and giving medium access opportunities to each network element based on its priority. We furthermore validate our algorithm through theoretical analysis and extensive simulations and the results show that our algorithm can outperform state-of-the-art alternatives.

Scheduling algorithms are crucial in radio resource management especially for multimedia networks. Many scheduling algorithms are based on the assumption of error-free connections, which is not suitable for wireless networks. Therefore, a scheduling algorithm based on the modification of Static Priority (SP) algorithm and Earliest-Due-Date (EDD) algorithm is proposed for wireless multimedia networks with link adaptation in this paper. In the proposed algorithm, various quality of service requirements, such as delay, throughput, and packet loss ratio, are considered. Particularly, the influence of error tolerance of voice communications, which is usually ignored in most scheduling algorithms, is taken into account. Simulation results show that the proposed algorithm, compared with SP, EDD, and other scheduling algorithms, succeeds in meeting the delay and packet loss ratio (PLR) requirements at much heavier traffic load.

IEEE 802.11 MAC protocol for medium access control in wireless Local Area Networks (LANs) is the de facto standard for wireless ad hoc networks. However, it does not perform well in terms of fairness, delay and throughput specially, in multihop networks. The problem is due to both the MAC and link layer contentions. Many research papers have been published in these fields. Among them, a modification of IEEE 802.11 MAC protocol was proposed to achieve per-node fairness, but modifications to the original MAC layer requires a change of hardware, therefore, it is difficult to implement. Moreover, it fails to solve the per-flow unfairness problem. In this paper, we propose a new scheduling method, Probabilistic Control on Round robin Queue (PCRQ) scheduling, aiming to achieve per-flow fairness in multihop ad hoc networks. PCRQ scheduling in the link layer is proposed without modifying IEEE 802.11 MAC protocol. Our proposed method achieves good performance results in both UDP and TCP traffic.

In this paper, we analyze the extended real-time Polling Service (ertPS) algorithm in IEEE 802.16e systems, which is designed to support Voice-over-Internet-Protocol (VoIP) services with data packets of various sizes and silence suppression. The analysis uses a two-dimensional Markov Chain, where the grant size and the voice packet state are considered, and an approximation formula for the total throughput in the ertPS algorithm is derived. Next, to improve the performance of the ertPS algorithm, we propose an enhanced uplink resource allocation algorithm, called the e 2rtPS algorithm, for VoIP services in IEEE 802.16e systems. The e 2rtPS algorithm considers the queue status information and tries to alleviate the queue congestion as soon as possible by using remaining network resources. Numerical results are provided to show the accuracy of the approximation analysis for the ertPS algorithm and to verify the effectiveness of the e 2rtPS algorithm.

We propose a polynomial-time algorithm for the scheduling of real-time parallel tasks on multicore processors. The proposed algorithm always finds a feasible schedule using the minimum number of processing cores, where tasks have properties of linear speedup, flexible preemption, arbitrary deadlines and arrivals, and parallelism bound. The time complexity of the proposed algorithm is O(M3log N) for M tasks and N processors in the worst case.

Multiple Input Multiple Output (MIMO) represents a highly promising technique for 4G communication networks as it uses multiple antennas at the transmitter and receiver to improve the reliability of transmissions and to provide a high data rate. This paper introduces an adjustable scheduling algorithm for multi-user MIMO systems that can provide an advantageous trade-off solution between throughput maximization and fair resource allocation among users. Specifically, our algorithm is proposed as a solution to system requirement issues through the flexible control of fairness factors.

This letter proposes an efficient uplink scheduling algorithm for the voice over Internet protocol (VoIP) service with variable frame-duration according to the voice activity in IEEE 802.16e/m systems. The proposed algorithm dynamically changes the grant-interval to save the uplink bandwidth, and it uses the random access scheme when the voice activity changes from silent-period to talk-spurt. Numerical results show that the proposed algorithm can increase the VoIP capacity by 26 percent compared to the conventional extended real-time polling service (ertPS).

IEEE 802.16 broadband wireless access (BWA) technology is suitable for providing multimedia applications without accessing the wired networks directly. Although IEEE 802.16 standard well defines the quality of service (QoS) framework, it makes no specific recommendation with regard to the bandwidth allocation. In this paper, we propose an algorithm for allocating bandwidth in response to dynamic changes in the arrival rate such that the total bandwidth is efficiently utilized.

We present a TCP flow level performance evaluation on error rate aware scheduling algorithms in Evolved UTRA and UTRAN networks. With the introduction of the error rate, which is the probability of transmission failure under a given wireless condition and the instantaneous transmission rate, the transmission efficiency can be improved without sacrificing the balance between system performance and user fairness. The performance comparison with and without error rate awareness is carried out dependant on various TCP traffic models, user channel conditions, schedulers with different fairness constraints, and automatic repeat request (ARQ) types. The results indicate that error rate awareness can make the resource allocation more reasonable and effectively improve the system and individual performance, especially for poor channel condition users.

In a key scheduling algorithm (KSA) of stream ciphers, a secret key is expanded into a large initial state. An internal state reconstruction method is known as a general attack against stream ciphers; it recovers the initial state from a given pair of plaintext and ciphertext more efficiently than exhaustive key search. If the method succeeds, then it is desirable that the inverse of KSA is infeasible in order to avoid the leakage of the secret key information. This paper shows that it is easy to compute a secret key from an initial state of RC4. We propose a method to recover an -bit secret key from only the first bits of the initial state of RC4 using linear equations with the time complexity less than that of one execution of KSA. It can recover the secret keys of which number is 2103.6 when the size of the secret key is 128 bits. That is, the 128-bit secret key can be recovered with a high probability when the first 128 bits of the initial state are determined using the internal state reconstruction method.