This paper addresses the problem of computing a maximal independent set (MIS), defined as a set of vertices where no two vertices are connected by an edge and no additional vertex can be added without violating the independence property. While several GPU-accelerated algorithms exist to find the MIS efficiently, the problem remains challenging for graphs exceeding the memory of a single GPU. In this paper, we present cuMIS, a unified scalable framework for computing MIS on single-GPU, multi-GPU, and distributed multi-node configurations. cuMIS employs a data-driven approach that processes only an active set of undecided vertices for reduced memory access and a degree-aware workload distribution that mitigates imbalance and thread divergence. Our results show that cuMIS outperforms ECL-MIS and MG-MIS—the state-of-the-art single-GPU and multi-GPU baselines—achieving speedups of up to 6.5 × and 156 ×, respectively, while maintaining comparable or superior solution quality. Finally, we demonstrate that cuMIS scales effectively to process trillion-edge graphs in distributed multi-node environments where existing approaches fail to operate.

Katz centrality is an important metric for measuring the relative importance of nodes in a graph, commonly used in social networks. This measure is prohibitively expensive to compute exactly, as it requires up to cubic-time complexity. Although several approximation methods exist, most fail to exploit parallelism, limiting their scalability to large graphs. To address this limitation, we propose two highly parallelizable Monte Carlo algorithms based on random walks named MC-Katz and MC-KatzP, which approximate the truncated Katz centrality and its original form, respectively. Empirical results on nine real-world datasets show that they achieve low mean relative error and high accuracy in ranking the most influential nodes in the networks, while delivering two to three orders of magnitude speedups over the baselines.

Due to the growing concern about unsavory behaviors of machine learning models toward certain demographic groups, the notion of 'fairness' has recently drawn much attention from the community, thereby motivating the study of fairness in graph clustering. Fair graph clustering aims to partition the set of nodes in a graph into k disjoint clusters such that the proportion of each protected group within each cluster is consistent with the proportion of that group in the entire dataset. It is, however, computationally challenging to incorporate fairness constraints into existing graph clustering algorithms, particularly for large graphs. To address this problem, we propose FairAD, a computationally efficient fair graph clustering method. It first constructs a new affinity matrix based on the notion of algebraic distance such that fairness constraints are imposed. A graph coarsening process is then performed on this affinity matrix to find representative nodes that correspond to k clusters. Finally, a constrained minimization problem is solved to obtain the solution of fair clustering. Experiment results on the modified stochastic block model and six public datasets show that FairAD can achieve fair clustering while being up to 40 times faster compared to state-of-the-art fair graph clustering algorithms.

Graph neural networks (GNNs) are powerful tools for solving graph-related problems. Distributed GNN frameworks and systems enhance the scalability of GNNs and accelerate model training, yet most are optimized for node classification. Their performance on link prediction remains underexplored. This paper demystifies distributed training of GNNs for link prediction by investigating the issue of performance degradation when each worker trains a GNN on its assigned partitioned subgraph without having access to the entire graph. We discover that the main sources of the issue come from not only the information loss caused by graph partitioning but also the ways of drawing negative samples during model training. While sharing the complete graph information with each worker resolves the issue and preserves link prediction accuracy, it incurs a high communication cost. We propose SpLPG, which effectively leverages graph sparsification to mitigate the issue of performance degradation at a reduced communication cost. Experiment results on several public real-world datasets demonstrate the effectiveness of SpLPG, which reduces the communication overhead by up to about 80% while mostly preserving link prediction accuracy.

Patching nodes is an effective network defense strategy for malware control at early stages, and its performance is primarily dependent on how accurately the infection propagation is characterized. In this paper, we aim to design a novel patching policy based on the susceptible-infected epidemic network model by incorporating the influence of patching delay–the type of delay that has been largely overlooked in designing patching policies in the literature, while being prevalent in practice. We first identify ‘critical edges’ that form a boundary to separate the most likely infected nodes from the nodes which would still remain healthy after the patching delay. We next leverage the critical edges to determine which nodes to be patched in light of limited patching resources at early stages. To this end, we formulate a constrained graph partitioning problem and use its solution to identify a set of nodes to patch or vaccinate under the limited resources, to effectively prevent malware propagation from getting through the healthy region. We numerically validate that our patching policy significantly outperforms other baseline policies in protecting the healthy nodes under limited patching resources and in the presence of patching delay.

Temporal graph link prediction aims to predict future interactions between nodes in a graph based on their historical interactions, which are encoded in node embeddings. We observe that heterogeneity naturally appears in temporal interactions, e.g., a few node pairs can make most interaction events, and interaction events happen at varying intervals. This leads to the problems of ineffective temporal information encoding and forgetting of past interactions for a pair of nodes that interact intermittently for their link prediction. Existing methods, however, do not consider such heterogeneity in their learning process, and thus their learned temporal node embeddings are less effective, especially when predicting the links for infrequently interacting node pairs. To cope with the heterogeneity, we propose a novel framework called TAMI, which contains two effective components, namely log time encoding function (LTE) and link history aggregation (LHA). LTE better encodes the temporal information through transforming interaction intervals into more balanced ones, and LHA prevents the historical interactions for each target node pair from being forgotten. State-of-the-art temporal graph neural networks can be seamlessly and readily integrated into TAMI to improve their effectiveness. Experiment results on 13 classic datasets and three newest temporal graph benchmark (TGB) datasets show that TAMI consistently improves the link prediction performance of the underlying models in both transductive and inductive settings. Our code is available at https://github.com/Alleinx/TAMI_temporal_graph.

A user's movement path can be precisely and concisely described as a concatenation of straight lines having the user's turns as their end points. Learning such a path description or representation from inertial measurement unit (IMU) sensors enables various mobile and IoT applications, as it allows efficient processing of the movement path data. It is, however, non-trivial to learn a succinct yet accurate path description from IMU sensor readings in the mobile device of a moving useron the flydue to the dynamically changing behaviors and the technical difficulty in detecting the user's turns. We propose PATHLIT, a novel online path description learning system based on IMU signals. PATHLIT learns position vectors of a user from IMU sensor readings by our custom-made self-attention network model. Once each position vector is learned, PATHLIT also decides whether or not to take it as a part of the resulting path description by our efficient online algorithm developed under the minimum description length principle, which essentially detects the user's turns along the path. We conduct extensive experiments on two large datasets. The experiment results show that PATHLIT achieves superior performance over state-of-the-art algorithms by up to 50% in absolute trajectory error using only 15% of trajectory data points.

To design fast neural networks, many works have been focusing on reducing the number of floating-point operations (FLOPs). We observe that such reduction in FLOPs, however, does not necessarily lead to a similar level of re-duction in latency. This mainly stems from inefficiently low floating-point operations per second (FLOPS). To achieve faster networks, we revisit popular operators and demonstrate that such low FLOPS is mainly due to frequent memory access of the operators, especially the depthwise con-volution. We hence propose a novel partial convolution (PConv) that extracts spatial features more efficiently, by cutting down redundant computation and memory access simultaneously. Building upon our PConv, we further propose FasterNet, a new family of neural networks, which attains substantially higher running speed than others on a wide range of devices, without compromising on accuracy for various vision tasks. For example, on ImageNet-lk, our tiny FasterNet-TO is 2.8×, 3.3×, and 2.4× faster than MobileViT-XXS on GPU, CPU, and ARM processors, respectively, while being 2.9% more accurate. Our large FasterNet-L achieves impressive 83.5% top-1 accuracy, on par with the emerging Swin-B, while having 36% higher inference throughput on GPU, as well as saving 37% compute time on CPU. Code is available at https://github.com/JierunChen/FasterNet.

Floor labels of crowdsourced RF signals are crucial for many smart-city applications, such as multi-floor indoor localization, geofencing, and robot surveillance. To build a prediction model to identify the floor number of a new RF signal upon its measurement, conventional approaches using the crowdsourced RF signals assume that at least few labeled signal samples are available on each floor. In this work, we push the envelope further and demonstrate that it is technically feasible to enable such floor identification with only one floor-labeled signal sample on the bottom floor while having the rest of signal samples unlabeled. We propose FIS-ONE, a novel floor identification system with only one labeled sample. FIS-ONE consists of two steps, namely signal clustering and cluster indexing. We first build a bipartite graph to model the RF signal samples and obtain a latent representation of each node (each signal sample) using our attention-based graph neural network model so that the RF signal samples can be clustered more accurately. Then, we tackle the problem of indexing the clusters with proper floor labels, by leveraging the observation that signals from an access point can be detected on different floors, i.e., signal spillover. Specifically, we formulate a cluster indexing problem as a combinatorial optimization problem and show that it is equivalent to solving a traveling salesman problem, whose (near-)optimal solution can be found efficiently. We have implemented FIS-ONE and validated its effectiveness on the Microsoft dataset and in three large shopping malls. Our results show that FIS- ONE outperforms other baseline algorithms significantly, with up to 23 % improvement in adjusted rand index and 25% improvement in normalized mutual information using only one floor-labeled signal sample.

In applications such as elderly care, dementia anti-wandering and pandemic control, it is important to ensure that people are within a predefined area for their safety and well-being. We propose GEM, a practical, semi-supervised Geofencing system with network EMbedding, which is based only on ambient radio frequency (RF) signals. GEM models measured RF signal records as a weighted bipartite graph. With access points on one side and signal records on the other, it is able to precisely capture the relationships between signal records. GEM then learns node embeddings from the graph via a novel bipartite network embedding algorithm called BiSAGE, based on a Bipartite graph neural network with a novel bi-level SAmple and aggreGatE mechanism and non-uniform neighborhood sampling. Using the learned embeddings, GEM finally builds a one-class classification model via an enhanced histogram-based algorithm for in-out detection, i.e., to detect whether the user is inside the area or not. This model also keeps on improving with newly collected signal records. We demonstrate through extensive experiments in diverse environments that GEM shows state-of-the-art performance with up to 34% improvement in F-score. BiSAGE in GEM leads to a 54% improvement in F-score, as compared to the one without BiSAGE.

We study the problem of floor identification for radiofrequency (RF) signal samples obtained in a crowdsourced manner, where the signal samples are highly heterogeneous and most samples lack their floor labels. We propose GRAFICS, a graph embedding-based floor identification system. GRAFICS first builds a highly versatile bipartite graph model, having APs on one side and signal samples on the other. GRAFICS then learns the low-dimensional embeddings of signal samples via a novel graph embedding algorithm named E-LINE. GRAFICS finally clusters the node embeddings along with the embeddings of a few labeled samples through a proximity-based hierarchical clustering, which eases the floor identification of every new sample. We validate the effectiveness of GRAFICS based on two large-scale datasets that contain RF signal records from 204 buildings in Hangzhou, China, and five buildings in Hong Kong. Our experiment results show that GRAFICS achieves highly accurate prediction performance with only a few labeled samples (96% in both micro- and macro-F scores) and significantly outperforms several state-of-the-art algorithms (by about 45% improvement in micro-F score and 53% in macro-F score).

The mean hitting time of a Markov chain on a graph from an arbitrary node to a target node randomly chosen according to its stationary distribution is called Kemeny's constant, which is an important metric for network analysis and has a wide range of applications. It is, however, still computationally expensive to evaluate the Kemeny's constant, especially when it comes to a large graph, since it requires the computation of the spectrum of the corresponding transition matrix or its normalized Laplacian matrix. In this paper, we propose a simple yet computationally efficient Monte Carlo algorithm to approximate the Kemeny's constant, which is equipped with an ε,δ)-approximation estimator. Thanks to its inherent algorithmic parallelism, we are able to develop its parallel implementation on a GPU to speed up the computation. We provide extensive experiment results on 13 real-world graphs to demonstrate the computational efficiency and scalability of our algorithm, which achieves up to 500x speed-up over the state-of-the-art algorithm. We further present its practical enhancements to make our algorithm ready for practical use in real-world settings.

We study the problem of how to estimate the latent in-degree distribution of large directed graphs from random samples, when the samples only indicate the presence of partial incoming edges into nodes and thus their sampled distribution is far from the original one. While this problem can be cast as an inverse problem, it often appears to be ill-posed and leads to poor estimation performance. There have thus been few recent studies to overcome this problem, which include a constrained, penalized weighted least squares estimator and an asymptotic estimator. The recent estimators, however, are computationally expensive or only limited to estimating the tail distribution, and their performance may not be satisfactory. In this paper, we formulate the problem as a maximum-likelihood estimation problem. We then employ the expectation-maximization algorithm to solve this problem and derive a simple iterative estimator, which is easy to implement and computationally fast. Finally, we empirically demonstrate that our estimator is significantly more accurate than the state-of-the-art estimators and it can also be further improved with a proper choice of its parameter.

In this paper, we study a problem of trapping malicious web crawlers in social networks to minimize the attacks from crawlers with malicious intents to steal personal/private information. The problem is to find where to place a given set of traps over a graph so as to minimize the expected number of users who possibly fall prey to a (possibly random) set of malicious crawlers, each of which traverses the graph in a random-walk fashion for a random finite time. We first show that this problem is NP-hard and also a monotone submodular maximization problem. We then present a greedy algorithm that achieves a ($1-1/e$)-approximation. We also develop an $(ε,δ)$-approximation Monte Carlo estimator to ease the computation of the greedy algorithm and thus make the algorithm scalable for large graphs. We finally present extensive simulation results to show that our algorithm significantly outperforms other baseline algorithms based on various centrality measures.

Over the past several years, low-cost micro-electro-mechanical systems (MEMS) sensors have been actively used for detecting earthquakes in real time. To utilize the low-cost MEMS sensors for earthquake early warning (EEW), it is crucial to construct a high-density seismic network of the sensors along with a server system to process a large volume of acceleration data transmitted from the sensors. It is also of vital importance to design an effective and efficient detection algorithm for the networked system in order to ensure realtime earthquake detection with high accuracy and low false alarms. In this paper, we introduce our recent effort in South Korea to build an EEW system based on several thousands of low-cost MEMS sensors and a deep-learning-based detection algorithm, which is currently being developed and deployed nationwide. Its initial version of a networked system has been in operation for over a year and has been able to detect a few small-magnitude earthquakes. While the early results have been positive and promising, we envision to ultimately integrate the networked system of low-cost MEMS sensors with the existing network of traditional seismic stations so as to build a unified EEW system that has better coverage and detection performance.

Recently, low-cost acceleration sensors have been widely used to detect earthquakes due to the significant development of MEMS technologies. It, however, still requires a high-density network to fully harness the low-cost sensors, especially for real-time earthquake detection. The design of a high-performance and scalable networked system thus becomes essential to be able to process a large amount of sensor data from hundreds to thousands of the sensors. An efficient and accurate earthquake-detection algorithm is also necessary to distinguish earthquake waveforms from various kinds of non-earthquake ones within the huge data in real time. In this paper, we present CrowdQuake, a networked system based on low-cost acceleration sensors, which monitors ground motions and detects earthquakes, by developing a convolutional-recurrent neural network model. This model ensures high detection performance while maintaining false alarms at a negligible level. We also provide detailed case studies on two of a few small earthquakes that have been detected by CrowdQuake during its last one-year operation.

In this paper, we aim to understand the transient dynamics of a susceptible-infected (SI) epidemic spreading process on a large network. The SI model has been largely overlooked in the literature, while it is naturally a better fit for modeling the malware propagation in early times when patches/vaccines are not available, or over a wider range of timescales when massive patching is practically infeasible. Nonetheless, its analysis is simply non-trivial, as its important dynamics are all transient and the usual stability/steady-state analysis no longer applies. To this end, we develop a theoretical framework that allows us to obtain an accurate closed-form approximate solution to the original SI dynamics on any arbitrary network, which captures the temporal dynamics over all time and is tighter than the existing approximation, and also to provide a new interpretation via reliability theory. As its applications, we further develop vaccination policies with or without knowledge of already-infected nodes, to mitigate the future epidemic spreading to the extent possible, and demonstrate their effectiveness through numerical simulations.

We study how the so-called Rao-Blackwellization, which is a variance reduction technique via “conditioning” for Monte Carlo methods, can be judiciously applied for graph sampling through neighborhood exploration. Despite its popularity for Monte Carlo methods, it is little known for Markov chain Monte Carlo methods and has never been discussed for random walk-based graph sampling. We first propose two forms of Rao-Blackwellization that can be used as a swap-in replacement for virtually all (reversible) random-walk graph sampling methods, and prove that the ‘Rao-Blackwellized’ estimators reduce the (asymptotic) variances of their original estimators yet maintain their inherent unbiasedness. The variance reduction can translate into lowering the number of samples required to achieve a desired sampling accuracy. However, the sampling cost for neighborhood exploration, if required, may outweigh such improvement, even leading to higher total amortized cost. Considering this, we provide a generalization of Rao-Blackwellization, which allows one to choose a suitable extent of obtaining Rao-Blackwellized samples in order to achieve a right balance between sampling cost and accuracy. We finally provide simulation results via real-world datasets that confirm our theoretical findings.

Graph sampling techniques via random walk crawling have been popular for analyzing statistical characteristics of large online social networks due to simple implementation and provable guarantees on unbiased estimates. Despite the growing popularity, the `cost' of sampling and its true impact on the accuracy of estimates still have not been carefully studied. In addition, the random walk-based methods inherently suffer from the sluggish nature of random walks and the `slow-mixing' structure of social graphs, thereby leading to high correlation in the samples obtained. With these in mind, in this paper, we develop a mathematical framework such that the cost of sampling is properly taken into account, which in turn re-defines a widely used asymptotic variance into a cost-based asymptotic variance. Our new metric enables us to compare a class of sampling policies under the same cost constraint, integrating “random skipping” (bypassing nodes without sampling) into the random walk-based sampling. We obtain an optimal policy striking the right balance between sampling quality (less correlation) and sampling quantity (higher cost per sample), which greatly improves over the usual skip-free crawling-based samplers. We further extend our framework, enabling one to design more sophisticated sampling strategies with an array of control knobs, which all produce unbiased estimates under the same cost constraint.

Heterogeneity arises in a wide range of scenarios in mobile opportunistic networks and is one of the key factors that govern the performance of forwarding algorithms. While the heterogeneity has been empirically investigated and exploited in the design of new forwarding algorithms, it has been typically ignored or marginalized when it comes to rigorous performance analysis of such algorithms. In this paper, we develop an analytical framework to quantify the performance gain achievable by exploiting the heterogeneity in mobile nodes' contact dynamics. In particular, we derive a delay upper bound of a heterogeneity-aware static forwarding policy per each given number of message copies and obtain its closed-form expression, which enables our quantitative study on the benefit of leveraging underlying heterogeneity structure in the design of forwarding algorithms. In addition, we develop a dynamic forwarding policy that performs as an extension of the static forwarding policy while proven to improve the delay performance. We then demonstrate that only a small fraction of total (unlimited) message copies, via both static and dynamic forwarding policies, are enough under various heterogeneous network settings to achieve the same delay as that obtained using the unlimited message copies when the networks become homogeneous. We also show that, given the same number of message copies, our dynamic forwarding policy significantly outperforms the `homogeneous-optimal' forwarding policy (up to about 50 percent improvement in the delay performance), especially when the number of message copies allowed in the networks is small.

Recently, several CSMA algorithms based on the Glauber dynamics model have been proposed for wireless link scheduling, as viable solutions to achieve the throughput optimality, yet simple to implement. However, their delay performance still remains unsatisfactory, mainly due to the nature of the underlying Markov chains that imposes a fundamental constraint on how the link state can evolve over time. In this paper, we propose a new approach toward better queueing delay performance, based on our observation that the algorithm needs not be Markovian, as long as it can be implemented in a distributed manner. Our approach hinges upon utilizing past state information observed by local link and then constructing a high-order Markov chain for the evolution of the feasible link schedules. We show that our proposed algorithm, named delayed CSMA, achieves the throughput optimality, and also provides much better delay performance by effectively “decorrelating” the link state process (and thus resolves link starvation). Our simulation results demonstrate that the delay under our algorithm can be reduced by a factor of 20 in some cases, compared to the standard Glauber-dynamics-based CSMA algorithm.

In this paper, we address how to design a distributed movement strategy for mobile collectors, which can be either physical mobile agents or query/collector packets periodically launched by the sink, to achieve successful data gathering in wireless sensor networks. Formulating the problem as general random walks on a graph composed of sensor nodes, we analyze how much data can be successfully gathered in time under any Markovian random-walk movement strategies for mobile collectors moving over a graph (or network), while each sensor node is equipped with limited buffer space and data arrival rates are heterogeneous over different sensor nodes. In particular, from the analysis, we obtain the optimal movement strategy among a class of Markovian strategies so as to minimize the data loss rate over all sensor nodes, and explain how such an optimal movement strategy can be made to work in a distributed fashion. We demonstrate that our distributed optimal movement strategy can lead to about two times smaller loss rate than a standard random walk strategy under diverse scenarios. In particular, our strategy results in up to 70 percent cost savings for the deployment of multiple collectors to achieve the target data loss rate than the standard random walk strategy.

The Metropolis-Hastings (MH) algorithm, in addition to its application for Markov Chain Monte Carlo sampling or simulation, has been popularly used for constructing a random walk that achieves a given, desired stationary distribution over a graph. Applications include crawling-based sampling of large graphs or online social networks, statistical estimation or inference from massive scale of networked data, efficient searching algorithms in unstructured peer-to-peer networks, randomized routing and movement strategies in wireless sensor networks, to list a few. Despite its versatility, the MH algorithm often causes self-transitions of its resulting random walk at some nodes, which is not efficient in the sense of the Peskun ordering - a partial order between off-diagonal elements of transition matrices of two different Markov chains, and in turn results in deficient performance in terms of asymptotic variance of time averages and expected hitting times with slower speed of convergence. To alleviate this problem, we present simple yet effective distributed algorithms that are guaranteed to improve the MH algorithm over time when running on a graph, and eventually reach `efficiency-optimality', while ensuring the same desired stationary distribution throughout.

Recently, several CSMA algorithms based on the Glauber dynamics model have been proposed for multihop wireless scheduling, as viable solutions to achieve the throughput optimality, yet simple to implement. However, their delay performance still remains unsatisfactory, mainly due to the nature of the underlying Markov chains that imposes a fundamental constraint on how the link state can evolve over time. In this paper, we propose a new approach toward better queueing delay performance, based on our observation that the algorithm needs not be Markovian, as long as it can be implemented in a distributed manner. Our approach hinges upon utilizing past state information observed by local link and then constructing a high-order Markov chain for the evolution of the feasible link schedules. We show in theory and simulation that our proposed algorithm, named delayed CSMA, achieves the throughput optimality, and also provides much better delay performance by effectively `de-correlating' the link state process (and thus resolves link starvation). Our extensive simulations demonstrate that the delay under our algorithm can be often reduced by a factor of 20 over a wide range of scenarios, compared to the standard Glauber-dynamics-based CSMA algorithm.

Being able to capture the properties of massive real graphs and also greatly reduce data scale and processing complexity, graph sampling techniques provide an efficient tool for complex network analysis. Random walk-based sampling has become popular to obtain asymptotically uniform samples in the recent literature. However, it produces highly correlated samples and often leads to poor estimation accuracy in sampling large networks. Another widely-used approach is to launch random jump by querying randomly generated user/node ID, but also has the drawback of unexpected cost when the ID space is sparsely populated. In this paper, we develop a hybrid graph sampling framework that inherits the benefit of returning immediate samples from random walk-based crawling, while incorporating the advantage of reducing the correlation in the obtained samples from random jump. We aim to strike the right balance between random jump and crawling by analyzing the resulting asymptotic variance of an estimator of any graph nodal property, in order to give guidelines on the design of better graph sampling methods. We also provide simulation results on real network (graph) to confirm our theoretical findings.

With recent drastic growth in the number of users carrying smart mobile devices, it is not hard to envision opportunistic ad-hoc communications taking place with such devices carried by humans. This leads to, however, a new challenge to the conventional link-level metrics, solely defined based on user mobility, such as inter-contact time, since there are many constraints including limited battery power that prevent the wireless interface of each user from being always `on' for communication. By taking into account the process of each user's availability jointly with mobility-induced contact/inter-contact process, we investigate how each of them affects the link-level connectivity depending on their relative operating time scales. We then identify three distinct regimes in each of which (1) the so-called impact of mobility on network performance prevails; (2) such impact of mobility disappears or its extent is not that significant; (3) the user availability process becomes dominant. Our findings not only caution that mobility alone is not sufficient to characterize the link-level dynamics, which in turn can lead to highly misleading results, but also suggest the presence of many uncharted research territories for further exploration.

Recently several CSMA algorithms based on the Glauber dynamics model have been proposed for multihop wireless scheduling, as viable solutions to achieve the throughput optimality, yet are simple to implement. However, their delay performances still remain unsatisfactory, mainly due to the nature of the underlying Markov chains that imposes a fundamental constraint on how the link state can evolve over time. In this paper, we propose a new approach toward better queueing and delay performance, based on our observation that the algorithm needs not be Markovian, as long as it can be implemented in a distributed manner, achieving the same throughput optimality and better delay performance. Our approach hinges upon utilizing past state information observed by local link and then constructing a high-order Markov chain for the evolution of the feasible link schedules. Our proposed algorithm, named delayed CSMA, adds virtually no additional overhead onto the existing CSMA-based algorithms, achieves the throughput optimality under the usual choice of link weight as a function of queue length, and also provides much better delay performance by effectively resolving temporal link starvation problem. From our extensive simulations we observe that the delay under our algorithm can be often reduced by a factor of 20 over a wide range of scenarios, compared to the standard Glauber-dynamics-based CSMA algorithm.

In this paper, we focus on how the heterogeneous contact dynamics of mobile nodes impact the performance of forwarding algorithms in mobile opportunistic networks (MONs). To this end, we consider two representative heterogeneous network models, each of which captures heterogeneity among node pairs (individual) and heterogeneity in underlying environment (spatial), respectively, and examine the full extent of difference in delay performance they cause on forwarding algorithms through formal stochastic comparisons. We first show that these heterogeneous models correctly capture non-Poisson contact dynamics observed in real traces. We then rigorously establish stochastic/convex ordering relationships on the delay performance of direct forwarding and multicopy two-hop relay protocol under these heterogeneous models and the corresponding homogeneous model, all of which have the same average intercontact time of a random pair of nodes. In particular, we demonstrate that the heterogeneous models predict an entirely opposite ordering relationship in delay performance depending on which of the two heterogeneity structures is captured. We also provide simulation results including the delay performance of epidemic routing protocol to support the analytical findings. Our results thus suggest that the heterogeneity in mobile nodes' contact dynamics should be properly taken into account for the performance evaluation of forwarding algorithms. Our results will also be useful for better design of forwarding algorithms correctly exploiting the heterogeneity structure.

Glauber dynamics, a method of sampling a given probability distribution via a Markov chain, has recently made considerable contribution to the MAC scheduling research, providing a tool to solve a long-standing open issue - achieving throughput-optimality with light message passing under CSMA. In this paper, we propose a way of reducing delay by studying generalized Glauber dynamics parameterized by βϵ[0, 1], ranging from Glauber dynamics (β=0) to the Metropolis algorithm (β =1). The same stationary distribution is sustained across this generalization, thus maintaining the long-term optimality. However, a different choice of β results in a significantly different second-order behavior (or variability) that has large impact on delay, which is hardly captured by the recent research focusing on delay in the large n (the number of nodes) asymptotic. We formally study such second-order behavior and its resulting delay performance, and show that larger β achieves smaller delay. Our results provide new insight into how to operate CSMA for large throughput and small delay in real, finite-sized systems.

In this paper, we address how to design the distributed movement strategy for mobile collectors, which can be either physical mobile agents or query/collector packets periodically launched by the sink, to achieve successful data gathering in wireless sensor networks. Formulating the problem as general random walks on a graph composed of sensors, we analyze how many data can be successfully gathered in time under any Markovian movement strategies for mobile collectors moving over a graph (or network), while each sensor is equipped with limited buffer space and data arrival rate to each node is heterogeneous. In particular, from the analysis, we obtain the optimal movement strategy among a class of Markovian strategies so as to minimize the data loss rate over all sensors, and explain how such optimal movement strategy can be made to work in a distributed fashion. We demonstrate that our distributed optimal movement strategy leads to about 2 times smaller loss rate than the simple random walk strategy under diverse scenarios. In particular, our strategy can result in about 50% cost savings for the deployment of multiple collectors to achieve the target data loss rate than the simple random walk.

Graph sampling via crawling has been actively considered as a generic and important tool for collecting uniform node samples so as to consistently estimate and uncover various characteristics of complex networks. The so-called simple random walk with re-weighting (SRW-rw) and Metropolis-Hastings (MH) algorithm have been popular in the literature for such unbiased graph sampling. However, an unavoidable downside of their core random walks -- slow diffusion over the space, can cause poor estimation accuracy. In this paper, we propose non-backtracking random walk with re-weighting (NBRW-rw) and MH algorithm with delayed acceptance (MHDA) which are theoretically guaranteed to achieve, at almost no additional cost, not only unbiased graph sampling but also higher efficiency (smaller asymptotic variance of the resulting unbiased estimators) than the SRW-rw and the MH algorithm, respectively. In particular, a remarkable feature of the MHDA is its applicability for any non-uniform node sampling like the MH algorithm, but ensuring better sampling efficiency than the MH algorithm. We also provide simulation results to confirm our theoretical findings.

In wireless sensor networks (WSNs), sensor nodes are typically power-constrained with limited lifetime, and thus it is necessary to know how long the network sustains its networking operations. We consider the network lifetime as the time until that a majority of functional nodes remains connected of one another, forming a giant component, in the network. We then analytically examine such network lifetime of a large-scale WSN via the theory of site percolation on a random graph model with a given degree distribution. In particular, we develop an analytical framework to quantify the network lifetime if the node lifetime can be controlled based on its degree, and show in theory and simulation that, by properly exploiting the heterogeneity over the node degrees, we can always increase the network lifetime when compared with that under the comparable degree-independent node lifetime.

A simple random walk (SRW) has been considered as an effective forwarding method for many applications in wireless sensor networks (WSNs) due to its desirable properties. However, a critical downside of SRW - slow diffusion or exploration over the space, typically leads to longer packet delay and undermines its own benefits. Such slow-mixing problem becomes even worse under random duty cycling adopted for energy conservation. In this paper, we study how to overcome this problem without any sacrifice or tradeoff, and propose a simple modification of random duty cycling, named Smart Sleep, which achieves more power-saving as well as faster packet diffusion (or smaller delay) while retaining the benefits of SRW. We also introduce a class of p-backtracking random walks and establish its properties to analytically explain the fast packet diffusion induced by Smart Sleep. We further obtain a necessary condition to achieve an optimal performance under our Smart Sleep, and finally demonstrate remarkable performance improvement via independent simulation results over various network topologies.

In wireless sensor networks (WSNs), sensor nodes are typically subjected to energy constraints and often prone to topology changes. While duty cycling has been widely used for energy conservation in WSNs, random walks have been popular for many delay-tolerant applications in WSNs due to their many inherent desirable properties. In this paper, we consider an opportunistic forwarding under an asynchronous and heterogeneous duty cycling. We first show that its resulting packet trajectory can be interpreted as a continuous-time random walk, and then provide an analytical formula for its end-to-end delay. Since the extremely large end-to-end delay is still undesirable even for most delay-tolerant applications, we develop a distributed wake-up scheduling algorithm in which each node autonomously adjusts its (heterogeneous) wake-up rate based only on its own degree information so as to improve the worst-case end-to-end delay. In particular, we prove that our algorithm outperforms pure homogeneous duty cycling, where every node uses the same wake-up rate, in its guaranteed asymptotic upper bound of the worst-case delay for any graph. In addition, we show that our proposed algorithm brings out more than 35% performance improvement on average when compared with pure homogeneous duty cycling, under various settings of random geometric graphs via numerical evaluations and independent simulation results.

Heterogeneity arises in a wide range of scenarios in mobile opportunistic networks and is one of key factors that govern the performance of packet forwarding algorithms. While the heterogeneity has been empirically investigated and exploited in the design of new forwarding algorithms, it has been typically ignored or marginalized when it comes to rigorous performance analysis of such algorithms. In this paper, we develop an analytical framework to quantify the performance gain achievable by exploiting the heterogeneity in mobile nodes' contact dynamics. In particular, we derive a delay upper bound of a heterogeneity-aware forwarding policy per a given number of message copies and obtain its closed-form expression, which enables our quantitative study on the benefit of leveraging underlying heterogeneity structure in the design of forwarding algorithms. We then analytically show that less than 20% of total (unlimited) message copies is only enough under various heterogeneous network settings to achieve the same delay as that obtained using the unlimited message copies when the networks become homogeneous. We also provide independent simulation results including real trace-driven evaluation to support our analytical results.

Mobility is the most important component in mobile ad hoc networks (MANETs) and delay-tolerant networks (DTNs). In this paper, we first investigate numerous GPS mobility traces of human mobile nodes and observe superdiffusive behavior in all GPS traces, which is characterized by a ¿faster-than-linear¿ growth rate of the mean square displacement (MSD) of a mobile node. We then investigate a large amount of access point (AP) based traces, and develop a theoretical framework built upon continuous time random walk (CTRW) formalism, in which one can identify the degree of diffusive behavior of mobile nodes even under possibly heavy-tailed pause time distribution, as in the case of reality. We study existing synthetic models and trace-based models in terms of the capability of producing various degrees of diffusive behavior, and use a set of Levy walk models due to its simplicity and flexibility. In addition, we show that diffusive properties make a huge impact on contact-based metrics and the performance of routing protocols in various scenarios, and that existing models such as random waypoint, random direction model, or Brownian motion lead to overly optimistic or pessimistic results when diffusive properties are not properly captured. Our work in this paper, thus, suggests that the diffusive behavior of mobile nodes should be correctly captured and taken into account for the design and comparison study of network protocols.

In this paper we focus on how the heterogeneous contact dynamics of mobile nodes impact the performance of forwarding/routing algorithms in delay/disruption-tolerant networks (DTNs). To this end, we consider two representative heterogeneous network models, each of which captures heterogeneity among node pairs (individual) and heterogeneity in underlying environment (spatial), respectively, and examine the full extent of difference in delay performances they cause on forwarding/routing algorithms through formal stochastic comparisons. We first show that these heterogeneous models correctly capture non-Poisson contact dynamics observed in real traces. Then, we consider direct forwarding and multicopy two-hop relay protocol and rigorously establish stochastic/convex ordering relationships on their delay performances under these heterogeneous models and the corresponding homogeneous model, all of which have the same average inter-contact time over all node pairs. We show that heterogeneous models predict an entirely opposite ordering relationship in the delay performances depending on which of the two heterogeneities is captured. This suggests that merely capturing non-Poisson contact dynamics - even if the entire distribution of aggregated inter-contact time is precisely matched, is not enough and that one should carefully evaluate the performance of forwarding/routing algorithms under a properly chosen heterogeneous network setting. Our results will also be useful in correctly exploiting the underlying heterogeneity structure so as to achieve better performance in DTNs.

The class of isotropic random walk mobility models, including random direction mobility model, random walk mobility model and Brownian motion mobility model, has been widely used in the study of Mobile Ad-Hoc Networks for mobility modeling and control. In this paper, we show an important property for contact time of isotropic random walk mobility models. Specifically, we find that the mean contact time of two mobile nodes following isotropic random walk mobility models is invariant with respect to the step-length distribution under both the simplest distance-based (Boolean) interference model and the more realistic SINR-based interference model. We also study the effect of system parameters on the contact and inter-meeting time of mobile nodes and discuss their higher-order statistics.

In the mobile IP-enabled wireless LAN (WLAN), packet transfer is interrupted due to the handoff of mobile node (MN), which results in burst packet losses. This transient behavior hurts time-critical streaming media applications. In case of one-way streaming media applications, it is well known that pre-buffering at the receiver side is effective in overcoming network fluctuations. However, determining the required margin of buffering is difficult in the mobile IP network, since it depends on the efficiency of adopted link-/lP-Iayer handoff options. In this paper, we introduce a scheme that helps estimate the required pre-buffering level more accurately by considering both handoff duration and transient packet losses. For experiment, we implement a packet buffering and forwarding mechanism (a.k.a. smooth handoff) to reduce the packet losses during the link-/IP-layer handoffs. Also, pre-buffering adjustment is performed based on the handoff latency experimentally measured and analytically obtained by the handoff transient time analysis. The experiment and simulation results shows that the proposed scheme can provide an appropriate guideline on the buffer parameters and thus can facilitate the seamless streaming over the mobile IP networks.