Shortest Link Scheduling in Wireless Networks with Oblivious Power Control

Link scheduling has always been a fundamental problem in wireless networks for its direct impacts on the performance of wireless networks such as throughput capacity,transmission delay,lifetime,etc.Existing work is mainly established under graphbased models,which are not only impractical but also incorrect due to the essentially fading characteristics of signals.In this paper,we study the shortest link scheduling problem under two more realistic models,namely the signal to interference plus noise ratio(SINR)model and the Rayleigh fading model.We propose a centralized square-based scheduling algorithm(CSSA)with oblivious power control under the SINR model and prove its correctness under both the SINR model and the Rayleigh fading model.Furthermore,we extend CSSA and propose a distributed square-based scheduling algorithm(DSSA).Note that DSSA adopts CSMA/CA so that a wireless node can compete for the wireless channel before starting its communication.We also show theoretical analysis and conduct extensive simulations to exhibit the correctness and efficiency of our algorithms.

SWRR:The Link Scheduling Algorithm Based on Weighted Round-Robin

With the rapid development of the Internet,people pay more and more attention to the protection of privacy.The second-generation onion routing system Tor is the most commonly used among anonymous communication systems,which can be used to protect user privacy effectively.In recent years,Tor’s congestion problem has become the focus of attention,and it can affect Tor’s performance even user experience.Firstly,we investigate the causes of Tor network congestion and summarize some link scheduling algorithms proposed in recent years.Then we propose the link scheduling algorithm SWRR based on WRR(Weighted Round Robin).In this process,we design multiple weight functions and compare the performance of these weight functions under different congestion conditions,and the appropriate weight function is selected to be used in our algorithms based on the experiment results.Finally,we also compare the performance of SWRR with other link scheduling algorithms under different congestion conditions by experiments,and verify the effectiveness of the algorithm SWRR.

Data-Driven Heuristic Assisted Memetic Algorithm for Efficient Inter-Satellite Link Scheduling in the BeiDou Navigation Satellite System

Inter-satellite link(ISL)scheduling is required by the BeiDou Navigation Satellite System(BDS)to guarantee the system ranging and communication performance.In the BDS,a great number of ISL scheduling instances must be addressed every day,which will certainly spend a lot of time via normal metaheuristics and hardly meet the quick-response requirements that often occur in real-world applications.To address the dual requirements of normal and quick-response ISL schedulings,a data-driven heuristic assisted memetic algorithm(DHMA)is proposed in this paper,which includes a high-performance memetic algorithm(MA)and a data-driven heuristic.In normal situations,the high-performance MA that hybridizes parallelism,competition,and evolution strategies is performed for high-quality ISL scheduling solutions over time.When in quick-response situations,the data-driven heuristic is performed to quickly schedule high-probability ISLs according to a prediction model,which is trained from the high-quality MA solutions.The main idea of the DHMA is to address normal and quick-response schedulings separately,while high-quality normal scheduling data are trained for quick-response use.In addition,this paper also presents an easy-to-understand ISL scheduling model and its NP-completeness.A seven-day experimental study with 10080 one-minute ISL scheduling instances shows the efficient performance of the DHMA in addressing the ISL scheduling in normal(in 84 hours)and quick-response(in 0.62 hour)situations,which can well meet the dual scheduling requirements in real-world BDS applications.

A Near-Optimal Optimization Algorithm for Link Assignment in Wireless Ad-Hoc Networks

Over the past few years, wireless networking technologies have made vast forays in our daily lives. In wireless ad-hoc networks, links are set up by a number of units without any permanent infrastructures. In this paper, the resource optimization is considered to maximize the network throughput by efficiently using the network capacity, where multi-hop functionality and spatial TDMA （STDMA） access scheme are used. The objective is to find the minimum frame length with given traffic distributions and corresponding routing information. Because of the complex structure of the underlying mathematical problem, previous work and analysis become intractable for networks of realistic sizes. The problem is addressed through mathematical programming approach, the linear integer formulation is developed for optimizing the network throughput, and then the similarity between the original problem and the graph edge coloring problem is shown through the conflict graph concept. A column generation solution is proposed and several enhancements are made in order to fasten its convergence. Numerical results demonstrate that the theoretical limit of the throughput can be efficiently computed for networks of realistic sizes.

Low-latency Data Gathering with Reliability Guaranteeing in Heterogeneous Wireless Sensor Networks

In order to achieve low-latency and high-reliability data gathering in heterogeneous wireless sensor networks(HWSNs),the problem of multi-channel-based data gathering with minimum latency(MCDGML),which associates with construction of data gathering trees,channel allocation,power assignment of nodes and link scheduling,is formulated as an optimization problem in this paper.Then,the optimization problem is proved to be NP-hard.To make the problem tractable,firstly,a multi-channel-based low-latency(MCLL)algorithm that constructs data gathering trees is proposed by optimizing the topology of nodes.Secondly,a maximum links scheduling(MLS)algorithm is proposed to further reduce the latency of data gathering,which ensures that the signal to interference plus noise ratio(SINR)of all scheduled links is not less than a certain threshold to guarantee the reliability of links.In addition,considering the interruption problem of data gathering caused by dead nodes or failed links,a robust mechanism is proposed by selecting certain assistant nodes based on the defined one-hop weight.A number of simulation results show that our algorithms can achieve a lower data gathering latency than some comparable data gathering algorithms while guaranteeing the reliability of links,and a higher packet arrival rate at the sink node can be achieved when the proposed algorithms are performed with the robust mechanism.