27 June 2019 in IEEE/ACM Transactions on Networking
In this paper, we study the problem of providing heterogeneous quality-of-service (QoS) guarantees for asynchronous grant-free uplink transmissions in multichannel wireless networks. The multiple access channel model is the classical collision channel, where partially overlapped packets during the transmissions are assumed to be completely lost. For such a network model, we propose two asynchronous multichannel transmission schedules (AMTS): 1) the EPC-based AMTS and 2) the DS-based AMTS. The EPC-based AMTS is constructed by time-spreading one-dimensional extended prime code (EPC), and the DS-based AMTS is constructed by using difference sets (DS) and finite projective planes. We show for both scheduling algorithms that the maximum delay between two successive successful transmissions of an active device can be upper bounded by a constant when the channel load does not exceed a designed threshold parameter. Moreover, different devices are allowed to have different throughput (rate) guarantees. By conducting extensive simulations, we also show that the overall throughputs of both scheduling algorithms are almost identical to that of the random access protocol, when the number of active devices exceeds the designed threshold parameter.
15 August 2017 in IEEE/ACM Transactions on Networking
The multichannel rendezvous problem in cognitive radio networks (CRNs) has been a hot research topic lately. One of the most challenging settings of the multichannel rendezvous problem is the oblivious rendezvous problem in heterogeneous CRNs, where: 1) there are no distinguishable roles of users; 2) users’ clocks are not synchronized; 3) users may have different available channel sets; and 4) there is no universal labelling of the channels. Most existing works in the literature focus on achieving deterministic bounds for the maximum conditional time-to-rendezvous (MCTTR) and perform poorly (in comparison with the random algorithm) for the expected time-to-rendezvous (ETTR) due to the “stay” modes in these works. In this paper, we tackle the oblivious rendezvous problem by taking both MCTTR and ETTR into consideration. In order to have guaranteed rendezvous, we only make two assumptions: (A1) there is at least one common available channel and (A2) there is a unique ID for each user. We first propose a new class of strong symmetrization mappings to encode user IDs for speeding up the rendezvous process. Two efficient and yet simple encoding schemes are proposed by utilizing the $\cal C$ -transform and the existing 4B5B encoding. Based on the new class of strong symmetrization mappings, we propose the two-prime modular clock algorithm for the two-user rendezvous problem. The ETTR of our algorithm is almost the same as that of the random algorithm and its MCTTR is also comparable to the best existing bound. We also extend the two-prime modular clock algorithm for multiuser rendezvous by proposing the stick together algorithm and the spread out algorithm. One interesting finding for the multiuser rendezvous problem is that the spread out algorithm is not always better than the stick together algorithm as commonly claimed in the literature.
6 June 2007 in Queueing Systems
17 August 2015 in Network Science
In this paper, we develop a formal framework for what a good community should look like and how strong a community is (community strength). One of the key innovations is to incorporate the concept of relative centrality into structural analysis of networks. In our framework, relative centrality is a measure that measures how important a set of nodes in a network is with respect to another set of nodes, and it is a generalization of centrality. Building on top of relative centrality, the community strength for a set of nodes is measured by the difference between its relative centrality with respect to itself and its centrality. A community is then a set of nodes with a nonnegative community strength. We show that our community strength is related to conductance that is commonly used for measuring the strength of a small community. We define the modularity for a partition of a network as the average community strength for a randomly selected node. Such a definition generalizes the original Newman's modularity and recovers the stability in as special cases. For the local community detection problem, we also develop efficient agglomerative algorithms that guarantee the community strength of the detected local community.
30 October 2017 in IEEE/ACM Transactions on Networking
There is growing interest in structural analysis of directed networks. Two major points that need to be addressed are: 1) a formal and precise definition of the graph clustering and community detection problem in directed networks and 2) algorithm design and evaluation of community detection algorithms in directed networks. Motivated by these, we develop a probabilistic framework for structural analysis and community detection in directed networks based on our previous work in undirected networks. By relaxing the assumption from symmetric bivariate distributions in our previous work to bivariate distributions that have the same marginal distributions in this paper, we can still formally define various notions for structural analysis in directed networks, including centrality, relative centrality, community, and modularity. We also extend three commonly used community detection algorithms in undirected networks to directed networks: the hierarchical agglomerative algorithm, the partitional algorithm, and the fast unfolding algorithm. These are made possible by two modularity preserving and sparsity preserving transformations. In conjunction with the probabilistic framework, we show these three algorithms converge in a finite number of steps. In particular, we show that the partitional algorithm is a linear time algorithm for large sparse graphs. Moreover, the outputs of the hierarchical agglomerative algorithm and the fast unfolding algorithm are guaranteed to be communities. These three algorithms can also be extended to general bivariate distributions with some minor modifications. We also conduct various experiments by using two sampling methods in directed networks: 1) PageRank and 2) random walks with self-loops and backward jumps.
22 January 2021 in IEEE/ACM Transactions on Networking
In this article, we develop a probabilistic framework for analyzing coded random access. Our framework is based on a new abstract receiver (decoder), called a Poisson receiver, that is characterized by a success probability function of a tagged packet subject to a Poisson offered load. We show that various coded slotted ALOHA (CSA) systems are Poisson receivers. Moreover, Poisson receivers have two elegant closure properties: (i) Poisson receivers with packet routing are still Poisson receivers, and (ii) Poisson receivers with packet coding are still Poisson receivers. These two closure properties enable us to use smaller Poisson receivers as building blocks for analyzing a larger Poisson receiver. As such, we can analyze complicated systems that are not possible by the classical tree evaluation method. In particular, for CSA systems with both spatial diversity and temporal diversity, we can use the framework of Poisson receivers to compute the exact (asymptotic) throughput. We demonstrate that our framework can be used to provide differentiated services between ultra-reliable low-latency communication (URLLC) traffic and enhanced mobile broadband (eMBB) traffic. By conducting extensive simulations, we also verify that our theoretical results match extremely well with the simulation results.