Theoretic analysis of IEEE 802.11 rate adaptation algorithm SampleRate

In this paper we investigate rate adaptation algorithm SampleRate, which spends a fixed time on bit-rates other than the currently measured best bit-rate. A simple but effective analytic model is proposed to study the steady-state behavior of the algorithm. Impacts of link condition, channel congestion and multi-rate retry on the algorithm performance are modeled. Simulations validate the model. It is also observed there is still a large performance gap between SampleRate and optimal scheme in case of high frame collision probability.

An accurate Markov model for slotted CSMA/CA algorithm in IEEE 802.15.4 networks

In this letter we propose an Markov model for slotted CSMA/CA algorithm working in a non-acknowledgement mode, specified in IEEE 802.15.4 standard. Both saturation throughput and energy consumption are modeled as functions of backoff window size, number of contending devices and frame length. Simulations show that the proposed model can achieve a very high accuracy (less than 1% mismatch) if compared to all existing models (bigger than 10% mismatch).

Performance analysis of ONOE protocol - an IEEE 802.11 link adaptation algorithm

Link adaptation (LA) plays an important role in adapting an IEEE 802.11 network to wireless link conditions and maximizing its capacity. However, there is a lack of theoretic analysis of IEEE 802.11 LA algorithms. In this article, we propose a Markov chain model for an 802.11 LA algorithm (ONOE algorithm), aiming to identify the problems and finding the space of improvement for LA algorithms. We systematically model the impacts of frame corruption and collision on IEEE 802.11 network performance. The proposed analytic model was verified by computer simulations. With the analytic model, it can be observed that ONOE algorithm performance is highly dependent on the initial bit rate and parameter configurations. The algorithm may perform badly even under light channel congestion, and thus, ONOE algorithm parameters should be configured carefully to ensure a satisfactory system performance. Copyright © 2011 John Wiley & Sons, Ltd.

A rank-based ant system algorithm for solving 0/1 knapsack problem

The 0/1 Knapsack Problem (KP), which is a classical NP-complete problem, has been widely applied to solving many real world problems. Ant system (AS), as one of the earliest ant colony optimization (ACO) algorithms, provides approximate solutions to 0/1 KPs. However, there are some shortcomings such as low efficiency and premature convergence in most AS algorithms. In order to overcome the shortcomings of AS, this paper proposes a rank-based AS algorithm, denoted as RAS to solve 0/1 KP. Taking advantages of the ranked ants with a higher profit, the pheromone of items will be updated with better solutions in RAS. Experimental results in different datasets show that this new kind of AS algorithm can obtain a higher efficiency and robustness when solving 0/1 KP.

A new physarum-based hybrid optimization algorithm for solving 0/1 knapsack problem

As a typical NP-complete problem, 0/1 Knapsack Problem (KP), has been widely applied in many domains for solving practical problems. Although ant colony optimization (ACO) algorithms can obtain approximate solutions to 0/1 KP, there exist some shortcomings such as the low convergence rate, premature convergence and weak robustness. In order to get rid of the above-mentioned shortcomings, this paper proposes a new kind of Physarum-based hybrid optimization algorithm, denoted as PM-ACO, based on the critical paths reserved by Physarum-inspired mathematical (PM) model. By releasing additional pheromone to items that are on the important pipelines of PM model, PM-ACO algorithms can enhance item pheromone matrix and realize a positive feedback process of updating item pheromone. The experimental results in two different datasets show that PM-ACO algorithms have a stronger robustness and a higher convergence rate compared with traditional ACO algorithms.

A parallel random forest algorithm for big data in a spark cloud computing environment

With the emergence of the big data age, the issue of how to obtain valuable knowledge from a dataset efficiently and accurately has attracted increasingly attention from both academia and industry. This paper presents a Parallel Random Forest (PRF) algorithm for big data on the Apache Spark platform. The PRF algorithm is optimized based on a hybrid approach combining data-parallel and task-parallel optimization. From the perspective of data-parallel optimization, a vertical data-partitioning method is performed to reduce the data communication cost effectively, and a data-multiplexing method is performed is performed to allow the training dataset to be reused and diminish the volume of data. From the perspective of task-parallel optimization, a dual parallel approach is carried out in the training process of RF, and a task Directed Acyclic Graph (DAG) is created according to the parallel training process of PRF and the dependence of the Resilient Distributed Datasets (RDD) objects. Then, different task schedulers are invoked for the tasks in the DAG. Moreover, to improve the algorithm's accuracy for large, high-dimensional, and noisy data, we perform a dimension-reduction approach in the training process and a weighted voting approach in the prediction process prior to parallelization. Extensive experimental results indicate the superiority and notable advantages of the PRF algorithm over the relevant algorithms implemented by Spark MLlib and other studies in terms of the classification accuracy, performance, and scalability.