It is known that packet collisions in wireless networks will deteriorate system performance, hence substantial efforts have been made to avoid collision in multi-user access designs. Also, there have been many studies...It is known that packet collisions in wireless networks will deteriorate system performance, hence substantial efforts have been made to avoid collision in multi-user access designs. Also, there have been many studies on throughput analysis of CSMA wireless networks. However, for a typical CSMA network in which not all nodes can sense each other, it is still not well investigated how link throughputs are affected by collisions. We note that in practical 802.11-like networks, the time is divided into mini-timeslots and packet collisions are in fact unavoidable. Thus, it is desirable to move forward to explore how collisions in such a network will affect system performance. Based on the collision-free ideal CSMA network(ICN) model, this paper attempts to analyze link throughputs when taking the backoff collisions into account and examine the effect of collisions on link throughputs. Specifically, we propose an Extended Ideal CSMA Network(EICN) model to characterize the collision effects as well as the interactions and dependency among links in the network. Based on EICN, we could directly compute link throughputs and collision probabilities. Simulations show that the EICN model is of high accuracy. Under various network topologies and protocol parameter settings, the computation error of link throughputs using EICN is kept to 4% or below. Interestingly, we find that unlike expected, the effect of collisions on link throughputs in a modest CSMA wireless network is not significant, which enriches our understanding on practical CSMA wireless networks such as Wi-Fi.展开更多
To support dramatically increased traffic loads,communication networks become ultra-dense.Traditional cell association(CA)schemes are timeconsuming,forcing researchers to seek fast schemes.This paper proposes a deep Q...To support dramatically increased traffic loads,communication networks become ultra-dense.Traditional cell association(CA)schemes are timeconsuming,forcing researchers to seek fast schemes.This paper proposes a deep Q-learning based scheme,whose main idea is to train a deep neural network(DNN)to calculate the Q values of all the state-action pairs and the cell holding the maximum Q value is associated.In the training stage,the intelligent agent continuously generates samples through the trial-anderror method to train the DNN until convergence.In the application stage,state vectors of all the users are inputted to the trained DNN to quickly obtain a satisfied CA result of a scenario with the same BS locations and user distribution.Simulations demonstrate that the proposed scheme provides satisfied CA results in a computational time several orders of magnitudes shorter than traditional schemes.Meanwhile,performance metrics,such as capacity and fairness,can be guaranteed.展开更多
Cell association is a significant research issue in future mobile communication systems due to the unacceptably large computational time of traditional schemes.This article proposes a polynomial-time cell association ...Cell association is a significant research issue in future mobile communication systems due to the unacceptably large computational time of traditional schemes.This article proposes a polynomial-time cell association scheme which not only completes the association in polynomial time but also fits for a generic optimization objective function.On the one hand,traditional cell association as a non-deterministic polynomial(NP)hard problem with a generic utility function is heuristically transformed into a 2-dimensional assignment optimization and solved by a certain polynomial-time algorithm,which significantly saves computational time.On the other hand,the scheme jointly considers utility maximization and load balancing among multiple base stations(BSs)by maintaining an experience pool storing a set of weighting factor values and their corresponding performances.When an association optimization is required,a suitable weighting factor value is taken from the pool to calculate a long square utility matrix and a certain polynomial-time algorithm will be applied for the association.Comparing with several representative schemes,the proposed scheme achieves large system capacity and high fairness within a relatively short computational time.展开更多
To mitigate interference on celledge users and improve fairness of the whole system, dynamic inter-cell interference coordination(ICIC) is one of the promising solutions. However, traditional dynamic ICIC is considere...To mitigate interference on celledge users and improve fairness of the whole system, dynamic inter-cell interference coordination(ICIC) is one of the promising solutions. However, traditional dynamic ICIC is considered as an NP-hard problem and power variability further adds another dimension to this joint optimization issue, making it even more difficult to quickly reach a near-optimal solution. Therefore, we theoretically obtain the closed-form expression of the near-optimal power allocation ratio for users in adjacent cells paired in the same resource block and interfere each other, so that the total utility corresponding to α-fairness is maximized. Dynamic ICIC using this closed-form solution could improve user fairness without causing an increment of the computational complexity. Numerical results show that, compared with the schemes using identical power for different users, our method does not obviously degrade the system's average spectral efficiency.展开更多
Phylogenetic trees have been widely used in the study of evolutionary biology for representing the tree-like evolution of a collection of species. However, different data sets and different methods often lead to the c...Phylogenetic trees have been widely used in the study of evolutionary biology for representing the tree-like evolution of a collection of species. However, different data sets and different methods often lead to the construction of different phylogenetic trees for the same set of species. Therefore, comparing these trees to determine similarities or, equivalently, dissimilarities, becomes the fundamental issue. Typically, Tree Bisection and Reconnection(TBR)and Subtree Prune and Regraft(SPR) distances have been proposed to facilitate the comparison between different phylogenetic trees. In this paper, we give a survey on the aspects of computational complexity, fixed-parameter algorithms, and approximation algorithms for computing the TBR and SPR distances of phylogenetic trees.展开更多
基金partially supported by the National Natural Science Foundation of China under Grant 61571178,Grant 61771315 and Grant 61501160
文摘It is known that packet collisions in wireless networks will deteriorate system performance, hence substantial efforts have been made to avoid collision in multi-user access designs. Also, there have been many studies on throughput analysis of CSMA wireless networks. However, for a typical CSMA network in which not all nodes can sense each other, it is still not well investigated how link throughputs are affected by collisions. We note that in practical 802.11-like networks, the time is divided into mini-timeslots and packet collisions are in fact unavoidable. Thus, it is desirable to move forward to explore how collisions in such a network will affect system performance. Based on the collision-free ideal CSMA network(ICN) model, this paper attempts to analyze link throughputs when taking the backoff collisions into account and examine the effect of collisions on link throughputs. Specifically, we propose an Extended Ideal CSMA Network(EICN) model to characterize the collision effects as well as the interactions and dependency among links in the network. Based on EICN, we could directly compute link throughputs and collision probabilities. Simulations show that the EICN model is of high accuracy. Under various network topologies and protocol parameter settings, the computation error of link throughputs using EICN is kept to 4% or below. Interestingly, we find that unlike expected, the effect of collisions on link throughputs in a modest CSMA wireless network is not significant, which enriches our understanding on practical CSMA wireless networks such as Wi-Fi.
基金This work was supported by the Fundamental Research Funds for the Central Universities of China under grant no.PA2019GDQT0012by National Natural Science Foundation of China(Grant No.61971176)by the Applied Basic Research Program ofWuhan City,China,under grand 2017010201010117.
文摘To support dramatically increased traffic loads,communication networks become ultra-dense.Traditional cell association(CA)schemes are timeconsuming,forcing researchers to seek fast schemes.This paper proposes a deep Q-learning based scheme,whose main idea is to train a deep neural network(DNN)to calculate the Q values of all the state-action pairs and the cell holding the maximum Q value is associated.In the training stage,the intelligent agent continuously generates samples through the trial-anderror method to train the DNN until convergence.In the application stage,state vectors of all the users are inputted to the trained DNN to quickly obtain a satisfied CA result of a scenario with the same BS locations and user distribution.Simulations demonstrate that the proposed scheme provides satisfied CA results in a computational time several orders of magnitudes shorter than traditional schemes.Meanwhile,performance metrics,such as capacity and fairness,can be guaranteed.
基金the results of the research project funded by the National Natural Science Foundation of China under Grant No.61971176in part by the Applied Basic Research Program of Wuhan City under grand 2017010201010117。
文摘Cell association is a significant research issue in future mobile communication systems due to the unacceptably large computational time of traditional schemes.This article proposes a polynomial-time cell association scheme which not only completes the association in polynomial time but also fits for a generic optimization objective function.On the one hand,traditional cell association as a non-deterministic polynomial(NP)hard problem with a generic utility function is heuristically transformed into a 2-dimensional assignment optimization and solved by a certain polynomial-time algorithm,which significantly saves computational time.On the other hand,the scheme jointly considers utility maximization and load balancing among multiple base stations(BSs)by maintaining an experience pool storing a set of weighting factor values and their corresponding performances.When an association optimization is required,a suitable weighting factor value is taken from the pool to calculate a long square utility matrix and a certain polynomial-time algorithm will be applied for the association.Comparing with several representative schemes,the proposed scheme achieves large system capacity and high fairness within a relatively short computational time.
基金supported by the National Natural Science Foundation of China under Grant No. 61501160supported by the Fundamental Research Funds for the Central Universities of China under Grant No. 2015HGCH0013
文摘To mitigate interference on celledge users and improve fairness of the whole system, dynamic inter-cell interference coordination(ICIC) is one of the promising solutions. However, traditional dynamic ICIC is considered as an NP-hard problem and power variability further adds another dimension to this joint optimization issue, making it even more difficult to quickly reach a near-optimal solution. Therefore, we theoretically obtain the closed-form expression of the near-optimal power allocation ratio for users in adjacent cells paired in the same resource block and interfere each other, so that the total utility corresponding to α-fairness is maximized. Dynamic ICIC using this closed-form solution could improve user fairness without causing an increment of the computational complexity. Numerical results show that, compared with the schemes using identical power for different users, our method does not obviously degrade the system's average spectral efficiency.
基金supported by the National Natural Science Foundation of China (Nos.61103033,61173051, 61232001,and 70921001)
文摘Phylogenetic trees have been widely used in the study of evolutionary biology for representing the tree-like evolution of a collection of species. However, different data sets and different methods often lead to the construction of different phylogenetic trees for the same set of species. Therefore, comparing these trees to determine similarities or, equivalently, dissimilarities, becomes the fundamental issue. Typically, Tree Bisection and Reconnection(TBR)and Subtree Prune and Regraft(SPR) distances have been proposed to facilitate the comparison between different phylogenetic trees. In this paper, we give a survey on the aspects of computational complexity, fixed-parameter algorithms, and approximation algorithms for computing the TBR and SPR distances of phylogenetic trees.