Fully Homomorphic Encryption (FHE) is a promising technology for secure, non-interactive outsourced computation. One notable method to increase the throughput of FHE-based outsourcing is batching, which typically involves large-scale matrix-matrix multiplications (MM). However, the substantial overhead inherent in existing FHE schemes poses a major challenge for processing these large-scale tasks, often resulting in insufficient memory or prolonged delays on a single machine, making it practically unviable. Utilizing multi-machine parallelism in cloud clusters for outsourced computation offers a natural solution to these obstacles. In this work, we propose FHE4DMM, a distributed algorithm that provides a unified view on encrypted matrices, accommodating various FHE schemes and any matrix dimensions, to accelerate large-scale encrypted MM. A key innovation is its reuse optimizations for parallelized homomorphic computations, which can offer valuable insights for broader FHE-based applications. We utilized FHE4DMM to conduct large-scale square ($4096\times 4096$) and rectangular ($32768\times 32768,32768\times 16$) matrix multiplications on 256 machines, achieving computation time of 172.2 s and 76.1 s, respectively, while ensuring a 128-bit security level. For scalability, the experiments demonstrate that FHE4DMM achieves linear speedup for$2^{i}$($i$is from 0 to 6) machines across various matrix dimension cases. In addition, within the range of matrix dimensions that the state-of-the-art (SOTA) distributed FHE-MM algorithm (Huang et al. 2023) can handle, FHE4DMM attains a maximum speedup of 16.62x. To assess its practical performance, FHE4DMM is applied in a basic multi-layer feedforward network. We used 64 machines to perform secure outsourced inference on MNIST and CIFAR-10 datasets with encrypted models and data. Compared to using the SOTA, our method achieved speedups of up to 3.54x and 4.22x respectively, with the MM module obtaining a 4.09x and 4.87x speedup.

Core number is an essential tool for analyzing graph structure. Graphs in the real world are typically large and dynamic, requiring the development of distributed algorithms to refrain from expensive I/O operations and the maintenance algorithms to address dynamism. Core maintenance updates the core number of each vertex upon the insertion/deletion of vertices/edges. Although the state-of-the-art distributed maintenance algorithm [9] can handle multiple edge insertions/deletions simultaneously, it still has two aspects to improve. (I) Parallel processing is not allowed when inserting/removing edges with the same core number, reducing the degree of parallelism and raising the number of rounds. (II) During the implementation phase, only one thread is assigned to the vertices with the same core number, leading to the inability to fully utilize the distributed computing power. Furthermore, the h-index [1] based distributed core decomposition algorithm [10] can fully utilize the distributed computing power where all vertices can be processed in parallel. However, it requires all vertices to recompute their core numbers upon graph changes. In this article, we propose a distributed core maintenance algorithm based on h-index, which circumvents the issues of algorithm [9]. In addition, our algorithm avoids core numbers recalculation where the numbers do not change. In comparison to the state-of-the-art distributed maintenance algorithm [9], the time speedup ratio is at least 100 in the scenarios of both insertion and deletion. Compared to the distributed core decomposition algorithm [10], the average time speedup ratios are 2 and 8 for the cases of insertion and deletion, respectively.

Core maintenance for dynamic hypergraphs has been receiving an increasing attention. However, existing works mainly focus on the insertion/deletion of hyperedges. This article revisits the problem from the view of vertices change. We study core maintenance when the vertices are inserted/deleted into/from specific hyperedges in the hypergraph, which is a challenging task since the deletion of the vertex may increase the core numbers and the insertion of the vertex may decrease the core numbers. We discuss in detail the possible changes of core numbers in different situations. For the insertion/deletion of vertices contained by a single hyperedge, we design sequential algorithms to discover the vertices whose core numbers have changed. Compared with static recomputation (Leng et al. 2013) and LYCLC (Luo et al. 2021) algorithms, our sequential algorithms can accelerate more than 1,000× and 12× at most in the processing time, respectively. For the insertion/deletion of vertices contained by different hyperedges, we find that core numbers of all vertices change 1 at most if these hyperedges form a matching. We design parallel algorithms that divide a matching into different sets based on their core numbers and allot a thread to each set. Experiments show that our parallel algorithms have good stability, scalability, and parallelism. Compared with the parallel static algorithm (Gabert et al. 2021) and the parallel dynamic algorithm GPC (Gabert et al. 2021), our parallel algorithms with 32 threads can accelerate 33× and 22× at most in the processing time, respectively.

Learning Chinese word embeddings is important in many tasks of Chinese language information processing, such as entity linking, entity extraction, and knowledge graph. A Chinese word consists of Chinese characters, which can be decomposed into sub-characters (radical, component, stroke, etc). Similar to roots in English words, sub-characters also indicate the origins and basic semantics of Chinese characters. So, many researches follow the approaches designed for learning embeddings of English words to improve Chinese word embeddings. However, some Chinese characters sharing the same sub-characters have different meanings. Furthermore, with more cultural interaction and the popularization of the Internet and web, many neologisms, such as transliterated loanwords and network terms, are emerging, which are only close to the pronunciation of their characters, but far from their semantics. Here, a tripartite weighted graph is proposed to model the semantic relationship among words, characters, and sub-characters, in which the semantic relationship is evaluated according to the Chinese linguistic information. So, the semantic relevance hidden in lower components (sub-characters, characters) can be used to further distinguish the semantics of corresponding higher components (characters, words). Then, the tripartite weighted graph is fed into our Chinese word embedding modelinsideCC to reveal the semantic relationship among different language components, and learn the embeddings of words. Extensive experimental results on multiple corpora and datasets verify that our proposed methods outperform the state-of-the-art counterparts by a significant margin.

Private Set Operations (PSO) are a hot research topic and one of the most extensive research problems in data mining. In the PSO, Multi-party Private Set Union (MPSU) is one of the fundamental problems. It allows some participants to learn the union of their data sets without leaking any useful information. However, most of the existing works have high communication, computation and round complexities. In this paper, we first propose a novel and efficient protocol to securely compute MPSU under the semi-honest model. In our system model, there exist n participants where each participant has a set of size k (k could be different among participants). There are also up to t (0 ≤ t < n) participants which could collude with each other. We suppose the communication channels among participants are insecure and can easily suffer from eavesdropping attacks. Our first protocol using element computing algorithm and Homomorphic Encryption, i.e., HE-MPSU, only requires O(1) rounds and has O(nNλ) communication complexity which almost matches the communication lower bound Ω(nN/log n) for the MPSU problem, where λ is a security parameter and N (k ≤ N ≤ nk) is the set union cardinality. In addition, we note that for the two-party case, i.e., n = 2, our HE-MPSU protocol has the same complexities as the state-of-the-art work in [1]. For this special case, i.e., two-party Private Set Union (PSU), we further optimize and design a more efficient protocol using oblivious transfer (OT) protocol, i.e., OT-PSU. It only requires O(1) rounds and O(kλ) communication complexity which almost matches the communication lower bound Ω(k). More importantly, it avoids using computationally expensive public-key operations (exponentiations). In other words, the number of exponentiations in this protocol is independent of the size of the data sets. Compared with the existing protocols, our two protocols have the lowest communication, computation and round complexities.

Complete Event Trend (CET) detection over large-scale event streams is important and challenging in various applications such as financial services, real-time business analysis, and supply chain management. A potential large number of partial intermediate results during complex event matching can raise prohibitively high memory cost for the processing system. The state-of-the-art scheme leverages compact graph encoding, which represents the common sub-sequences of different complex events using a common sub-graph to achieve space efficiency for storing the intermediate results. However, we show that such a design raises unacceptable computation cost for the graph traversal needed whenever a new event comes. To address this problem, in this paper, we propose a novel attribute-based indexing (ABI) graph model to represent the relationship between events. By classifying the predicates and constructing the graph based on both the comparators in the predicates and the attribute values of the events, we achieve parallel event stream processing and efficient graph construction. Our design significantly reduces the total computation cost of graph construction from O(n2) to O(nlog(m)), where n is the number of events and m is the number of the attribute vertices. We further design several efficient traversal-based algorithms to extract CETs from the graph. We implement our design and conduct comprehensive experiments to evaluate the performance of this design. The results show that our design wins a couple of orders of magnitude back from state-of-the-art schemes.

In this paper, we propose a parallel algorithm for computing all-pairs shortest paths (APSP) for sparse graphs on the distributed memory system with p processors. To exploit the graph sparsity, we first preprocess the graph by utilizing several known algorithmic techniques in linear algebra such as fill-in reducing ordering and elimination tree parallelism. Then we map the preprocessed graph on the distributed memory system for both load balancing and communication reduction. Finally, we design a new scheduling strategy to minimize the communication cost. The bandwidth cost (communication volume) and the latency cost (number of messages) of our algorithm are and O(log 2p), respectively, where S is a minimal vertex separator that partitions the graph into two components of roughly equal size. Compared with the state-of-the-art result for dense graphs where the bandwidth and latency costs are and ), respectively, our algorithm reduces the latency cost by a factor of , and reduces the bandwidth cost by a factor of for sparse graphs with . We also present the bandwidth and latency costs lower bounds for computing APSP on sparse graphs, which are and Ω(log 2p), respectively. This implies that the bandwidth cost of our algorithm is nearly optimal and the latency cost is optimal.

Most of existing graph processing systems essentially follow pull-based computation model to handle compute-intensive parts of graph iteration for high parallelism. Considering all vertices and edges are processed in each iteration, pull model may suffers from a large number of invalid (vertex/edge) operations that do not contribute to graph convergence, leading to potential performance degradation. In this paper, we have the insight that these invalid operations can be filtered by leveraging a small fraction of critical information. However, most of critical information are often beyond the visibility of active vertices being processed. We present two novel filtration approaches to (cooperatively) identify out-of-visibility critical information with boundary-cut heuristics and speculative prediction for many graph algorithms. We have integrated both approaches and their hybrid solution into three state-of-art graph processing systems (including Ligra, Gemini, and Polymer). Experimental results using a wide variety of graph algorithms on both real-world and synthetic graph datasets show that neither of these approaches can have an absolute win for all graph algorithms. Boundary-cut, predictive, and hybrid approaches can improve the performance by 115.1, 38.1, and 136.6 percent on average.

Blockchain technology offers an intelligent amalgamation of distributed ledger, Peer-to-Peer (P2P), cryptography, and smart contracts to enable trustworthy applications without any third parties. Existing blockchain systems have successfully either resolved the scalability issue by advancing the distributed consensus protocols from the control plane, or complemented the security issue by updating the block structure and encryption algorithms from the data plane. Yet, we argue that the underlying P2P network plane remains as an important but unaddressed barrier for accelerating the overall blockchain system performance, which can be discussed from how fast and reliable the network is. In order to improve the blockchain network performance about enabling fast and reliable broadcast, we establish a trust-enhanced blockchain P2P topology which takes transmission rate and transmission reliability into consideration. Transmission rate reflects blockchain network speed to disseminate transactions and blocks, and transmission reliability reveals whether transmission rate changes drastically on unreliable network connection. This paper presents BlockP2P-EP, a novel trust-enhanced blockchain topology to accelerate transmission rate and meanwhile retain transmission reliability. BlockP2P-EP first operates the geographical proximity sensing clustering, which leverages K-Means algorithm for gathering proximity peer nodes into clusters. It follows by the hierarchical topological structure that ensures strong connectivity and small diameter based on node attribute classification. Then we propose establishing trust-enhanced network topology. On top of the trust-enhanced blockchain topology, BlockP2P-EP conducts the parallel spanning tree broadcast algorithm to enable fast data broadcast among nodes both intra- and inter- clusters. Finally, we adopt an effective node inactivation detection method to reduce network load. To verify the validity of BlockP2P-EP protocol, we carefully design and implement a blockchain network simulator. Evaluation results show that BlockP2P-EP can exhibit promising network performance in terms of transmission rate and transmission reliability compared to Bitcoin and Ethereum.

This article studies the core maintenance problem for dynamic graphs which requires to update each vertex's core number with the insertion/deletion of vertices/edges. Previous algorithms can either process one edge associated with a vertex in each iteration or can only process one superior edge associated with the vertex (an edge 〈u; v〉 is a superior edge of vertex u if v' core number is no less than u's core number) in each iteration. Thus for high superior-degree vertices (the vertices associated with many superior edges) insertions/deletions, previous algorithms become very inefficient. In this article, we discovered a new structure called joint edge set whose insertions/deletions make each vertex's core number change at most one. The joint edge set mainly contains all the superior edges associated with the high superior-degree vertices as long as these vertices are 3+-hop independent. Based on this discovery, faster parallel algorithms are devised to solve the core maintenance problems. In our algorithms, we can process all edges in the joint edge set in one iteration and thus can greatly increase the parallelism and reduce the processing time. The results of extensive experiments conducted on various types of real-world, temporal, and synthetic graphs illustrate that the proposed algorithms achieve good efficiency, stability and scalability. Specifically, the new algorithms can outperform the single-edge processing algorithms by up to four orders of magnitude. Compared with the matching based algorithm and the superior edge based algorithm, our algorithms show a significant speedup up to 60× in the processing time.

This paper studies jamming-resilient distributed backbone construction in multi-hop wireless networks. Specifically, a strong adversarial jamming model is proposed that captures the general jamming phenomena suffered by wireless communications. The jamming model is based on the realistic Signal-to-Interference-plus-Noise-Ratio (SINR) interference model, and is featured by local-uniformity, unrestricted energy budget and reactivity, which covers more jamming scenarios and is much closer to reality than existing jamming models. Under the strong adversarial jamming model, we propose a randomized distributed algorithm that can construct a backbone in J(O(log n + logR)) rounds with high probability, where J(O(log n + log R)) is the number of rounds in the interval from the beginning of the algorithm execution that contains O(log n + log R) unjammed rounds for every node. This result is asymptotically optimal considering the trivial lower bound of Ω(log n) for a successful transmission even without interference and jamming.

Graph partitioning is a fundamental problem to enable scalable graph computation on large graphs. Existing partitioning models are either streaming based or offline based. In the streaming model, the current edge needs all previous edges' partition choices to make a decision. As a result, it is hard to carry out partitioning in parallel. Besides, offline based partitioning requires full knowledge about the input graph which may not suit well for large graphs. In this work, we propose a quasi-streaming partitioning model and a game theory based solution for the edge partitioning problem. Specifically, we separate the whole edge stream into a series of batches where the batch size is a constant multiple of the number of partitions. In each batch, we model the graph edge partitioning problem as a game process, where the edge's partition choice is regarded as a rational strategy choice of the player in the game. As a result, the edge partitioning problem is decomposed into finding Nash Equilibriums in a series of game processes. We mathematically prove the existence of Nash Equilibrium in such a game process, and analyze the number of rounds needed to converge into a Nash Equilibrium. We further measure the quality of these Nash Equilibriums via computing the PoA (Price of Anarchy), which is bounded by the number of partitions. Then we evaluate the performance of our strategy via comprehensive experiments on both real-world graphs and random graphs. Results show that our solution achieves significant improvements on load balance and replication factor when compared with five exsiting streaming partitioning strategies.

Privacy-preserving data aggregation has been extensively studied in the past decades. However, most of these works target at specific aggregation functions such as additive or multiplicative aggregation functions. Meanwhile, they assume there exists a trusted authority which facilitates the keys and other information distribution. In this paper, we aim to devise a communication efficient and privacy-preserving protocol that can exactly compute arbitrary data aggregation functions without trusted authority. In our model, there exist one untrusted aggregator and n participants. We assume that all communication channels are insecure and are subject to eavesdropping attacks. Our protocol is designed under the semi-honest model, and it can also tolerate k (k ≤ n-2) collusive adversaries. Our protocol achieves (n - k) -source anonymity. That is, for the source of each collected data aparting from the colluded participants, what the aggregator learns is only from one of the (n - k) non-colluded ones. Compared with recent work [1] that computes arbitrary aggregation functions by collecting all the participants' data using the trusted authority, our protocol increases merely by at most a factor of O(([logn/loglogn])2) in terms of computation time and communication cost. The key of our protocol is that we have designed algorithms that can efficiently assign unique sequence numbers to each participant without the trusted authority.

In this paper, we present the first algorithm for exactly implementing the abstract MAC (absMAC) layer in the physical SINR model. The absMac layer, first presented by Kuhn et al. in [15], provides reliable local broadcast communication, with timing guarantees stated in terms of a collection of abstract delay functions, such that high-level algorithms can be designed in terms of these functions, independent of specific channel behavior. The implementation of absMAC layer is to design a distributed algorithm for the local broadcast communication primitives over a particular communication model that defines concrete channel behaviors, and the objective is minimizing the bounds of the abstract delay functions. Halldórsson et al. [10] have shown that in the standard SINR model (synchronous communication, without physical carrier sensing or location information), there cannot be efficient exact implementations. In this work, we show that physical carrier sensing, a commonly seen function performed by wireless devices, can help get efficient exact implementation algorithms. Specifically, we propose an algorithm that exactly implements the absMAC layer. The algorithm provides asymptotically optimal bounds for both acknowledgement and progress functions defined in the absMAC layer. Our algorithm can lead to many new faster algorithms for solving high-level problems in the SINR model. We demonstrate this by giving algorithms for problems of Consensus, Multi-Message Broadcast and Single-Message Broadcast. It deserves to point out that our implementation algorithm is designed based on an optimal algorithm for a General Local Broadcast (GLB) problem, which takes the number of distinct messages into consideration for the first time. The GLB algorithm can handle much more communication scenarios apart from those defined in the absMAC layer. Simulation results show that our proposed algorithms perform well in reality.

Dynamicity is one of the critical characteristics and a major challenge in designing communication protocols in wireless networks. Most of the previous works had focused on the internal node changes (e.g., mobility, arrival, or departure) and not considered the effect of external environmental change. However, the external environmental change, in general, is a more complex phenomenon that can impede nodes from successful communication, implying the protocols of the previous dynamic models do not work well in practice. In this paper, we give an algorithm for distributed broadcasting in a more general model with fully dynamic wireless networks, called FD-Broadcast. Specifically, we present a fully dynamic model which allows node mobility and churns (due to node arrivals/departure) and external environmental change. In contrast to the previous works on dynamic networks, our model defines the full dynamicity in terms of localized topological changes of each node and can tolerate some external environmental change. The external environment changes are captured by the random jamming method. We show that FD-Broadcast can achieve broadcasting in$O(D_{S})$rounds with a high probability guarantee under the assumption of constant dynamic rate in the SINR model, where$D_{S}$is the dynamic diameter, a parameter proposed to depict the complexity of dynamic broadcasting. Moreover, the lower bound of dynamic broadcasting is proved to be$\Omega(D_{S})$, thus, FD-Broadcast is asymptotically optimal with high probability.

The core number of vertices is a basic index depicting cohesiveness of a graph, and has been widely used in large-scale graph analytics. In this paper, we study the update of core numbers of vertices in dynamic graphs with edge insertions/deletions, which is known as the core maintenance problem. Different from previous approaches that just focus on the case of single-edge insertion/deletion and sequentially handle the edges when multiple edges are inserted/deleted, we investigate the parallelism in the core maintenance procedure. Specifically, we show that if the inserted/deleted edges constitute a matching, the core number update with respect to each inserted/deleted edge can be handled in parallel. Based on this key observation, we propose parallel algorithms for core maintenance in both cases of edge insertions and deletions. Extensive experiments are conducted to evaluate the efficiency, stability, parallelism and scalability of our algorithms on different types of real-world, synthetic graphs and temporal networks. Comparing with former approaches, our algorithms can improve the core maintenance efficiency significantly.

Betweenness centrality of a node represents its influence over the spread of information in the network. It is normally defined as the ratio of the number of shortest paths passing through the node among all shortest paths. However, the spread of information may not just pass through the shortest paths which is captured by a new measure of betweenness centrality based on random walks [1]. The random walk betweenness centrality of a node means how often it is traversed by a random walk between all pairs of other nodes. In this paper, we propose an O(n log n) time distributed randomized approximation algorithm for calculating each node's random walk betweenness centrality with an approximation ratio (1-ϵ) where n is the number of nodes and ϵ is an arbitrarily small constant between 0 and 1. Our distributed algorithm is designed under the widely used CONGEST model, where each edge can only transfer O(log n) bits in each round. To our best knowledge, this is the first distributed algorithm for computing the random walk betweenness centrality. Moreover, we give a non-trivial lower bound for distributively computing the exact random walk betweenness centrality under the CONGEST model, which is Ω(n\log n +D) where D is the network diameter. This means exactly computing random walk betweenness cannot be done in sublinear time.

This paper initiates the studies of parallel algorithm for core maintenance in dynamic graphs. The core number is a fundamental index reflecting the cohesiveness of a graph, which is widely used in large-scale graph analytics. We investigate the parallelism in the core update process when multiple edges and vertices are inserted. Specifically, we discover a structure called superior edge set, the insertion of edges in which can be processed in parallel. Based on the structure of superior edge set, an efficient parallel algorithm is then devised. To the best of our knowledge, the proposed algorithm is the first parallel one for the fundamental core maintenance problem. Finally, extensive experiments are conducted on different types of real-world and synthetic datasets, and the results illustrate the efficiency, stability and scalability of the proposed algorithm. The algorithm shows a significant speedup in the processing time compared with previous results that sequentially handle edge and vertex insertions.

Rendezvous is a fundamental process in constructing cognitive radio networks (CRNs), in which two users find a common channel for communication. The licensed spectrum is assumed to be divided into n non-overlapping channels and the users can sense the spectrum by equipping with cognitive radios. Most of previous works assume that the user can find a set of available channels (the channels not occupied by the licensed users) after spectrum sensing stage and the status of all channels are stable all the time. However, this assumption may not be true in reality and we focus on designing efficient algorithms when the status of the channels varies dynamically. In this paper, we introduce two models to describe the dynamic rendezvous problem. Denote pij as the probability that channel j is available for user i. In the Independent model, assuming all pij variables are independently distributed and we propose efficient algorithms for both synchronous and asynchronous users, which guarantee rendezvous in O (log2 n) and O (log3 n) time slots with high probability respectively. In the Dependent model, two nearby users have relevant available probabilities and we introduce a sensing phase and an attempting phase to guarantee rendezvous in O (ε log3 n log log log n) time slots with high probability, where ε is a small constant. We also present an algorithm to increase rendezvous load in the long run, which guarantee rendezvous for at least 1/4 of all time slots.

In this paper, we propose an O(N) time distributed algorithm for computing betweenness centralities of all nodes in the network where N is the number of nodes. Our distributed algorithm is designed under the widely employed CONGEST model in the distributed computing community which limits each message only contains O(log N) bits. To our best knowledge, this is the first linear time deterministic distributed algorithm for computing the betweenness centralities in the published literature. We also give a lower bound for distributively computing the betweenness centrality under the CONGEST model as Ω(D+N/ log N) where D is the diameter of the network. This implies that our distributed algorithm is nearly optimal.

Given an unweighted and undirected graph, this paper aims to give a tight distributed algorithm for computing the all pairs shortest paths (APSP) under synchronous communications and the CONGEST(B) model, where each node can only transfer B bits of information along each incident edge in a round. The best previous results for distributively computing APSP need O(N+D) time where N is the number of nodes and D is the diameter [1,2]. However, there is still a B factor gap from the lower bound Ω(N/B+D) [1]. In order to close this gap, we propose a multiplexing technique to push the parallelization of distributed BFS tree constructions to the limit such that we can solve APSP in O(N/B+D) time which meets the lower bound. This result also implies a Θ(N/B+D) time distributed algorithm for diameter. In addition, we extend our distributed algorithm to compute girth which is the length of the shortest cycle and clustering coefficient (CC) which is related to counting the number of triangles incident to each node. The time complexities for computing these two graph properties are also O(N/B+D).

Controlling a dynamic network is interesting and important in practical applications, which is to drive the network from any initial state to any desired state. Much research has been conducted in revealing the controllability and seeking the underlying correlations of the network. However, no existing works have considered the time needed to control the network, which we refer to as control latency. In this paper, we initiate the study of control latency of dynamic networks. First of all, we formulate the minimum control latency (MCL) problem for designing the controlling pattern with minimum number of controllers. We show that the MCL problem is NP-hard by reducing the multiprocessor scheduling problem to it. Then, we propose a greedy algorithm for designing a controlling pattern that can control the network within two times the minimum control latency. Moreover, when the control latency is bounded by a given value, we propose another constant approximation algorithm to design a controlling pattern which uses at most three times the minimum number of controllers. We conduct extensive simulations on both synthetic and real networks to corroborate our theoretic analysis.

Cognitive radio networks (CRNs) have been proposed to solve the spectrum scarcity problem. One of their fundamental procedures is to construct a communication link on a common channel for the users, which is referred as rendezvous. In reality, the capability to sense the spectrum may vary from user to user, and such users form what is known as a heterogeneous cognitive radio network (HCRN). The licensed spectrum is divided in to n channels, U = {1, 2,..., n}. We denote the capability of user i as Ci⊆ U and the set of available channels (i.e. the channels not occupied by the paying users) as Vi⊆ Ci. We study the rendezvous problem in HCRN under two circumstances: fully available spectrum (Vi= Ci) and partially available spectrum (Vi≠ Ci). For any two users a, b, we propose the Traversing Pointer (TP) algorithm that guarantees rendezvous in O(max{|Ca|,|Cb|}log log n) time slots for the fully available spectrum scenario. This result is only O (log log n) larger than our constructive lower bound. Moreover, it removes an O(min{|Ca|, |Cb|}) factor as compared to the state-of-the-art result (O(|Ca||Cb|) in [26]). For the partially available spectrum scenario, we propose the Moving Traversing Pointers (MTP) algorithm to guarantee rendezvous in O((max{|Va|, |Vb|})2log log n) time slots, which works more efficiently than the previous best result (O(|Ca||Cb|) in [25]) in various circumstances. We also conduct extensive simulations and the results corroborate our analysis.

In this paper, we initiate the Communication and Block Game between two unlicensed users and an adversary in Cognitive Radio Networks (CRNs). In each time slot, the two unlicensed users can successfully communicate on the common available channel if it is not blocked by the adversary. In the communication and block game, the two un-licensed users aim to maximize their communication load, denoted as the number of time slots of their successful communications, while the adversary aims to minimize it. We propose efficient algorithms for both users and the adversary and we prove the proposed algorithms will lead a Nash Equilibrium, i.e. the users can achieve the maximum communication load against any adversary's blocking strategy, while the adversary can minimize the users' communication load against any users' channel accessing strategy. We also present efficient algorithms for both users and adversary for the multiple channels scenario where the users and the adversary are equipped with multiple radios. These algorithms also guarantee high communication load for the users, while the adversary can also block a considerable number of users'communications. Our simulations validate the theoretical analyses.

Rendezvous process is the cornerstone to construct Cognitive Radio Networks (CRNs), through which a secondary user can establish a link for communication with its neighbor on a common channel. Although many blind rendezvous algorithms have been proposed which do not rely on a central controller or a common control channel, all of these works still rely on the global parameters such as the number of licensed channels N and the number of users. This paper aims to design fully distributed blind rendezvous algorithms only based on each user's local information. We first give the Synchronous Check & Hop (SCH) algorithm for two synchronous users where they start the rendezvous process at the same time. The SCH algorithm guarantees rendezvous in O(min{ka,kb} N) time slots where ka,kb are the corresponding number of sensed channels of these two users. Our main contribution is a fully distributed algorithm called Conversion Based Hopping (CBH), where each user only uses its identifier (ID) and its number of sensed channels. CBH guarantees rendezvous between two asynchronous users in O((max{ka,kb})2) time slots. To our knowledge, this is the first result with rendezvous time independent of the global parameter N. We also derive a lower bound of rendezvous time between two users as Ω((ka-kg)(kb-kg)) where k_g is the number of their common channels. All of our results also apply to a more general blind rendezvous problem which we call Oblivious Blind Rendezvous where each user is free to assign their local labels to the sensed channels. Extensive simulation results compared with the state-of-the-art rendezvous algorithms corroborate our theoretical analyses.

Rendezvous is a fundamental process in constructing Cognitive Radio Networks (CRNs), through which the user can communicate with its neighbors by establishing a link on some licensed frequency band (channel). Most of the existing elegant rendezvous algorithms assume each user is equipped with a single radio. Nowadays the multi-radio cognitive radio architecture, where each user can access k ≥ 2 channels at the same time, has become a reality. In this paper, we study the rendezvous problem in multi-radio CRN to see whether and to what extent the multi-radio capability can improve the rendezvous performance. To begin with, we propose a family of deterministic distributed algorithms for two special situations when k=2 and k=O(√n), where n is the number of all channels. These algorithms show that the maximum time to rendezvous (MTTR) can be reduced (largely) in multi-radio CRN. Then we derive a lower bound of MTTR as Ω({|Vi||Vj|}/k2) for arbitrary k (Vi, Vj represents two users' available channel sets) and present a distributed algorithm to guarantee rendezvous in O({|Vi||Vj|}/k2) time slots, which meets the lower bound. Extensive simulations are conducted to corroborate our theoretical analyses.

Rendezvous process plays an important role in constructing Cognitive Radio Networks (CRNs), through which a user establishes a link on a common licensed channel for communication with its neighbors. Generally, the licensed spectrum is divided into N channels and most blind rendezvous algorithms are realized by the “channel hopping” method where each user repeats a Global Sequence constructed on top of all the N channels. This global sequence based method may contain lots of redundant channels resulting in large rendezvous time especially when the number of available channels each user has only accounts for a small fraction of all the N channels. In this paper, we introduce the Local Sequence based rendezvous algorithms where the local sequence is only constructed on top of each user's available channels and different user's local sequence could be different. Our first local sequence based algorithm called LS can guarantee rendezvous in O(N) time slots for symmetric users (both users have the same set of available channels) and in O(N2) time slots for asymmetric users, which matches the best known results [11]. Our major contribution is the Modified Local Sequence (MLS) based algorithm which can guarantee an exponentially shorter rendezvous time than the best known results when the number of available channels each user has is relatively small. Extensive simulation results comparing with the state-of-the-art rendezvous algorithms corroborate our theoretical analyses.

Gathering information in a sensing field of interest is a fundamental task in wireless sensor networks. Current methods either use multihop forwarding to the sink via stationary nodes or use mobile sinks to traverse the sensing field. The multihop forwarding method intrinsically has the energy hole problem and the mobile sinks method has a large gathering latency due to its low mobility velocity. In addition, all the mobile sinks methods assume unlimited power supply and memory which is unrealistic in practice. In this paper, we propose a new approach for information gathering through a Mobile Aerial Sensor Network (MASN). We adopt the Hive-Drone model [5] where a centralized station (Hive) responsible for serving and recharging Micro-Aerial Vehicle (MAV) sensor nodes (Drones) is strategically placed in the sensing field. We then face the challenges of how to control the mobility of each MAV and devising interference-free scheduling for wireless transmissions that can substantially reduce the latency. We present a family of algorithms with constant memory to reduce both gathering latency, which is the duration from dispatching the MAVs to the moment when all the sensed information are gathered at the central station, and information latency, which is the duration from when some information is sensed to when it is received by the station. We also consider how to extend the single Hive to multiple Hives for monitoring an arbitrarily large area. Extensive simulation results corroborate our theoretical analysis.

Multiple-message broadcast is a generalization of the traditional broadcast problem. It is to disseminate k distinct (1 ≤ k ≤ n) messages stored at k arbitrary nodes to the entire network with the fewest timeslots. In this paper, we study this basic communication primitive in unstructured wireless networks under the physical interference model (also known as the SINR model). The unstructured wireless network assumes unknown network topology, no collision detection and asynchronous communications. Our proposed randomized distributed algorithm can accomplish multiple-message broadcast in O((D + k) log n + log2n) timeslots with high probability, where D is the network diameter and n is the number of nodes in the network. To our best knowledge, this work is the first one to consider distributively implementing multiple-message broadcasting in unstructured wireless networks under a global interference model, which may shed some light on how to efficiently solve in general a “global” problem in a “local” fashion with “global” interference constraints in asynchronous wireless ad hoc networks. Apart from the algorithm, we also show an Ω(D+k+log n) lower bound for randomized distributed multiple message broadcast algorithms under the assumed network model.

Rendezvous is a fundamental process in Cognitive Radio Networks, through which a user establishes a link to communicate with a neighbor on a common channel. Most previous solutions use either a central controller or a Common Control Channel (CCC) to simplify the problem, which are inflexible and vulnerable to faults and attacks. Some blind rendezvous algorithms have been proposed that rely on no centralization. Channel Hopping (CH) is a representative technique used in blind rendezvous, with which each user hops among the available channels according to a pre-defined sequence. However, no existing algorithms can work efficiently for both symmetric (both parties have the same set of channels) and asymmetric users. In this paper, we introduce a new notion called Disjoint Relaxed Difference Set (DRDS) and present a linear time constant approximation algorithm for its construction. Then based on the DRDS, we propose a distributed asynchronous algorithm that can achieve and guarantee fast rendezvous for both symmetric and asymmetric users. We also derive a lower bound for any algorithm using the CH technique. This lower bound shows that our proposed DRDS based distributed rendezvous algorithm is nearly optimal. Extensive simulation results corroborate our theoretical analysis.

Minimizing latency and energy consumption is the prime objective of the design of data aggregation in battery-powered wireless networks. A tradeoff exists between the aggregation latency and the energy consumption, which has been widely studied under the protocol interference model. There has been, however, no investigation of the tradeoff under the physical interference model that is known to capture more accurately the characteristics of wireless interferences. When coupled with the technique of successive interference cancellation, by which a receiver may recover signals from multiple simultaneous senders, the model can lead to much reduced latency but increased energy usage. In this paper, we investigate the latency-energy tradeoff for data aggregation in wireless sensor networks under the physical interference model and using successive interference cancellation. We present theoretical lower bounds on both latency and energy as well as their tradeoff, and give an efficient approximation algorithm that can achieve the asymptotical optimum in both aggregation latency and latency-energy tradeoff. We show that our algorithm can significantly reduce the aggregation latency, for which the energy consumption is kept at its lowest possible level.

The unstructured multi-hop radio network model, with asynchronous wake-up, no collision detection and little knowledge on the network topology, is proposed for capturing the particularly harsh characteristics of initially deployed wireless adhoc and sensor networks. In this paper, assuming such a practical model, we study a fundamental problem of both theoretical and practical interests--the local broadcasting problem. Given a set of nodes V where each node wants to broadcast a message to all its neighbors that are within a certain local broadcasting range R, the problem is to schedule all these requests in the fewest timeslots. By adopting the physical interference mode land without any knowledge on neighborhood, we give a new randomized distributed approximation algorithm for the local broadcasting problem with approximation ratio O (log n) where nis the number of nodes. This distributed approximation algorithm improves the state-of-the-art result in [22] by a logarithmic factor.

Minimum-Latency Aggregation Scheduling (MLAS) is a problem of fundamental importance in wireless sensor networks. There however has been very little effort spent on designing algorithms to achieve sufficiently fast data aggregation under the physical interference model which is a more realistic model than traditional protocol interference model. In particular, a distributed solution to the problem under the physical interference model is challenging because of the need for global-scale information to compute the cumulative interference at any individual node. In this paper, we propose a distributed algorithm that solves the MLAS problem under the physical interference model in networks of arbitrary topology in O(K) time slots, where K is the logarithm of the ratio between the lengths of the longest and shortest links in the network. We also give a centralized algorithm to serve as a benchmark for comparison purposes, which aggregates data from all sources in O(log3n) time slots (where n is the total number of nodes). This is the current best algorithm for the problem in the literature. The distributed algorithm partitions the network into cells according to the value K, thus obviating the need for global information. The centralized algorithm strategically combines our aggregation tree construction algorithm with the non-linear power assignment strategy in [9]. We prove the correctness and efficiency of our algorithms, and conduct empirical studies under realistic settings to validate our analytical results.

Recently Moscibroda and Wattenhofer came up with the notion of scheduling complexity to capture the minimum amount of time to successfully schedule all the transmission requests under the physical SINR model. Their algorithm featuring a non-linear power assignment can schedule strongly connected transmissions in narrowband networks with O(log4 n) timeslots. In this paper, we first generalize this result to ultra-wideband networks. We show the strong connectivity scheduling complexity in UWB networks to be O(log (n/m)∙log3 n), where m is the processing gain. Secondly, we show that both of these polylogarithmic scheduling complexity results are gained at the expense of exponential energy complexity with lower bound ω(n∙2n). We also prove the upper bound of the energy complexity in narrowband networks to beO(n2∙2nα), and for UWB networks, this upper bound can be reduced by a processing gain factor.On the other hand, we show that improving the scheduling complexity through arbitrary power control has its limitations, and that different power assignment strategies have different impacts on the protocol interference models, which was often neglected in the design of wireless scheduling algorithms. Compared with narrowband networks, although the effect of aggregate interferences in UWB networks is greatly reduced, we demonstrate that the constant and linear power assignments in UWB networks are still inefficient in the worst case with respect to the scheduling complexity (Ω(n/m), which suggests there is a need for a better arbitrary power assignment.Our analyses shed new light on the design of the power assignment scheme and the performance analysis of the wireless scheduling algorithms. In energy-constrained wireless networks, a tradeoff between the scheduling complexity and energy complexity is a practical consideration. Our results in this paper can be directly applied to other spread-spectrum networks including DS-CDMA and FH-CDMA.