Search

This paper studies decentralized federated learning algorithms in wireless IoT networks. The traditional parameter server architecture for federated learning faces some problems such as low fault tolerance, large communication overhead and inaccessibility of private data. To solve these problems, we propose a Decentralized-Wireless-Federated-Learning algorithm called DWFL. The algorithm works in a system where the workers are organized in a peer-to-peer and server-less manner, and the workers exchange their privacy preserving data with the analog transmission scheme over wireless channels in parallel. With rigorous analysis, we show that DWFL satisfies $(\epsilon,\delta)$-differential privacy and the privacy budget per worker scales as $\mathcal{O}(\frac{1}{\sqrt{N}})$, in contrast with the constant budget in the orthogonal transmission approach. Furthermore, DWFL converges at the same rate of $\mathcal{O}(\sqrt{\frac{1}{TN}})$ as the best known centralized algorithm with a central parameter server. Extensive experiments demonstrate that our algorithm DWFL also performs well in real settings.

Nowadays, more and more federated learning algorithms have been implemented in edge computing, to provide various customized services for mobile users, which has strongly supported the rapid development of edge intelligence. However, most of them are designed relying on the reliable device-to-device communications, which is not a realistic assumption in the wireless environment. This paper considers a realistic aggregation problem for federated learning in a single-hop wireless network, in which the parameters of machine learning models are aggregated from the learning agents to a parameter server via a wireless channel with physical interference constraint. Assuming that all the learning agents and the parameter server are within a distance [Formula: see text] from each other, we show that it is possible to construct a spanning tree to connect all the learning agents to the parameter server for federated learning within [Formula: see text] time steps. After the spanning tree is constructed, it only takes [Formula: see text] time steps to aggregate all the training parameters from the learning agents to the parameter server. Thus, the server can update its machine learning model once according to the aggregated results. Theoretical analyses and numerical simulations are conducted to show the performance of our algorithm.

In the past decades, Dynamic Internet of Things (D-IoT) networks have played a conspicuously more important role in many real-life areas, including disaster relief, environment monitoring, public safety, and so on, to rapidly collect information from the environment and help people to make the decision. Meanwhile, due to the widespread implementation of dynamic IoT networks, there exists an enormous demand on designing suitable models and efficient algorithms for fundamental operations in dynamic IoT networks, to achieve the high throughput and reliable low-latency communication demands in 6G networks. In this article, we first present a general dynamic model to comprehensively depict most of the dynamic phenomena in IoT networks. Then, based on the proposed dynamic model, a distributed scheduling algorithm is proposed to competitively optimize the Age-of-Information (AoI) problem in the context of a D-IoT network. We say our scheduling algorithm is competitive: the throughput of the base station approximates the optimal solution with constant competitive ratio; and, the latency for a packet received by the base station is only constant times larger than the optimal latency. Rigorous theoretical analysis and extensive simulations are presented to verify the high throughput and reliable low-latency communications in our proposed algorithm.

In this paper, we investigate distributed broadcasting in dynamic networks, where the topology changes continually over time. We propose a network model that captures the dynamicity caused by both churn and mobility of nodes. In contrast to existing work on dynamic networks, our model defines the dynamicity in terms of localized topological changes in the vicinity of each node, rather than a global view of the whole network. Obviously, a local dynamic model suits distributed algorithms better than a global one. The proposed dynamic model uses the more realistic SINR model to depict wireless interference, instead of oversimplified graph-based models adopted in most existing work. We consider the fundamental communication primitive of global broadcast, which is to disseminate a message from a source node to the whole network. Specifically, we present a randomized distributed algorithm that can accomplish dynamic broadcasting in an asymptotically optimal running time of $O(D_{T})$ with a high probability guarantee, under the assumption of reasonably constant dynamicity rate , where $D_{T}$ is the dynamic diameter , a parameter proposed to depict the complexity of dynamic broadcasting. We believe our local dynamic model can greatly facilitate distributed algorithm studies in mobile and dynamic wireless networks.

In this paper, we study distributed algorithms to realize efficient communications under the Rayleigh-fading model. This model extends the popular deterministic SINR model using stochastic propagations to address the fading effects observed in reality. Stochastic propagations can greatly increase the difficulty of handling interference and collisions, especially in a local context without much global knowledge. We present a new technique called Inductive Coloring that can be used to schedule fast transmissions with Rayleigh-fading interference. The computation of inductive coloring takes only $O(\log ^{2}n)$ time with the proposed distributed algorithm, where $n$ is the number of nodes in the network. We illustrate the power of inductive coloring by giving a distributed and randomized algorithm to implement the abstract MAC (absMAC) layer, which was first proposed by Kuhn et al. . With two basic time-guaranteed communication primitives, namely acknowledgement and progress, which correspond to the operations of node local broadcasts and message receptions from others, the absMAC layer decomposes the algorithm design and analysis in networks into two independent components, i.e., implementing the absMAC layer over a physical network and designing algorithms with the help of the two primitives in the absMAC layer. Thus, it sharply reduces the fussy and complicated process of algorithm design and analysis over the physical network. Our proposed algorithm implements the absMAC layer under the Rayleigh-fading model with no more than a logarithmic factor inferior to the optimal solution in terms of time complexity. The presented simulation results indicate that our algorithm performs well in realistic environments. Furthermore, we show that by making full use of our proposed absMAC layer algorithm, many network primitives such as Neighbor Discovery, Single/Multiple-Message Broadcast, and Consensus, can be efficiently implemented.

China’s Chang’e 5 mission has been a remarkable success, with the Chang’e 5 lander traveling on the Oceanus Procellarum to collect images of the lunar surface. Over the past half century, people have brought back some lunar rock samples, but its quantity does not meet the need for research. Under current circumstances, people still mainly rely on the analysis of rocks on the lunar surface through the detection of lunar rover. The Oceanus Procellarum, chosen by Chang’e 5 mission, contains various kinds of rock species. Therefore, we first applied to the National Astronomical Observatories of the China under the Chinese Academy of Sciences for the Navigation and Terrain Camera (NaTeCam) of the lunar surface image, and established a lunar surface rock image data set CE5ROCK. The data set contains 100 images, which randomly divided into training, validation and test set. Experimental results show that the identification accuracy testing on convolutional neural network (CNN) models like AlexNet or MobileNet is about to 40.0%. In order to make full use of the global information in Moon images, this paper proposes the MRNet (MoonRockNet) network architecture. The encoding structure of the network uses VGG16 for feature extraction, and the decoding part adds dilated convolution and commonly used U-Net structure on the original VGG16 decoding structure, which is more conducive to identify more refined but more sparsely distributed types of lunar rocks. We have conducted extensive experiments on the established CE5ROCK data set, and the experimental results show that MRNet can achieve more accurate rock type identification, and outperform other existing mainstream algorithms in the identification performance.

The byzantine model is widely used to depict a variety of node faults in networks. Previous studies on byzantine-resilient protocols in wireless networks assume reliable communications and do not consider the jamming behavior of byzantine nodes. Such jamming, however, is a very critical and realistic behavior to be considered in modern wireless networks. In this paper, for the first time, we integrate the jamming behavior of byzantine nodes into the network setting. We show that, in this much more comprehensive and harsh model, efficient distributed communication protocols can be still devised with elaborate protocol design. In particular, we developed an algorithm that can accomplish the basic multiple-message dissemination task close to the optimal solution in terms of running time. Empirical results validate the byzantine-resilience and efficiency of our algorithm.

In this paper, we present the first algorithm to precisely implement the abstract MAC (absMAC) layer under the physical SINR model in dynamic networks. The absMac layer, first presented by (Kuhn et al ., 2009), provides reliable local broadcast communications, with timing guarantees stated in terms of a collection of abstract delay functions, based on which high-level algorithms can be designed, independent of specific channel behaviors. The implementation of absMAC requires the design of a distributed algorithm for the local broadcast communication primitives over a particular communication model that defines concrete channel behaviors, and the objective is to minimize the bounds of the abstract delay functions. Halldorsson et al. (2015) showed that under the standard SINR model (synchronous communications without physical carrier sensing or location information), there exist no efficient exact implementations. In this work, we demonstrate 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 precisely implements the absMAC layer under the SINR model in dynamic networks. The algorithm provides asymptotically optimal bounds for both acknowledgement and progress functions defined in the absMAC layer. Our algorithm leads to many new faster algorithms for solving high-level problems under the SINR model in dynamic networks. We demonstrate this by exemplifying 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 many 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 most challenging, yet, key aspects of wireless networks. It can come in many guises, such as churn (node insertion/deletion) and node mobility. Although the study of dynamic networks has been popular in distributed computing domain, previous works considered only partial factors causing dynamicity. In this work, we propose a dynamic model that is comprehensive to include crucial dynamic factors on nodes and links. Our model defines dynamicity in terms of localized topological changes in the vicinity of each node, rather than a global view of the whole network. Obviously, a localized dynamic model suits distributed algorithm studies better than a global one. The proposed dynamic model makes use of the more realistic SINR model to describe wireless interference, instead of the oversimplified graph-based models adopted by most existing research. Under the proposed dynamic model, we develop an efficient distributed algorithm accomplishing local broadcast services in the abstract MAC layer that was first presented by Kuhn et al. [24] . Our solution paves the way for many new fast algorithms to solve high-level problems in dynamic networks, such as consensus, single-message broadcast, and multiple-message broadcast. Extensive simulation studies indicate that our algorithm exhibits good performance in realistic environments with dynamic network behaviors.

In the era of big data, sensor networks have been pervasively deployed, producing a large amount of data for various applications. However, because sensor networks are usually placed in hostile environments, managing the huge volume of data is a very challenging issue. In this study, we mainly focus on the data storage reliability problem in heterogeneous wireless sensor networks where robust storage nodes are deployed in sensor networks and data redundancy is utilized through coding techniques. To minimize data delivery and data storage costs, we design an algorithm to jointly optimize data routing and storage node deployment. The problem can be formulated as a binary nonlinear combinatorial optimization problem, and dueto its NP-hardness, designing approximation algorithms is highly nontrivial. By leveraging the Markov approximation framework, we elaborately design an efficient algorithm driven by a continuous-time Markov chain to schedule the deployment of the storage node and corresponding routing strategy. We also perform extensive simulations to verify the efficacy of our algorithm.

In the partial assignment problem, a seller has an item set M = { i 1 , i 2 , … , i m } , the amount of each item is exactly one. There are n buyers N = { b 1 , b 2 , . . . , b n } , each buyer b p has a preferred bundle B p ⊆ M and a value function f p ( ⋅ ) . Assume that each item should be sold integrally and thus can be only assigned to at most one buyer. In previous works, buyers are often considered to be single-minded, i.e., a buyer can be either assigned the whole preferred bundle, or nothing. In this paper, we consider a more generalized and realistic model where the buyer can be partially satisfied, i.e., buyer b p can have some positive value if the seller assigns a subset of b p 's preferred bundle. However, there might be exponential number of subsets, to tackle this situation, a value oracle is implemented. We can get the value f p ( S p ) for buyer b p and S p ⊆ B p by querying the value oracle. The objective is to assign items to buyers such that the total values are maximized, i.e., max ⁡ ∑ p = 1 n f p ( S p ) . We first show that in this model, maximizing the total values is NP-hard. We then propose provably efficient approximation algorithms for general and submodular value functions respectively. If the value function satisfies non-negative, monotone and normalized, an 1 / m -approximation algorithm can be achieved. If the value function is submodular, the total values can be approximated within a factor of ( 1 − 1 / e ) .

Network function virtualization (NFV) is a promising virtualization technology that has the potential to significantly reduce the expenses and improve service agility. The NFV makes it possible for Internet service providers (ISPs) to employ various virtual network functions (VNFs) without installing new equipments. One of the most attractive approaches in the NFV technology is the so-called joint placement and allocation of virtual network functions (JPA-VNFs), which considers the balance between VNF investment with Quality of Services (QoS). We introduce a novel capability function to measure the potential of locating VNF instances for each server in the proposed OJPA-HS model. This model allows the servers in the network to be heterogeneous, at the same time combines and generalizes many classical JPA-VNF models. Despite its NP-hardness, we present a provable best-possible deterministic online algorithm based on dynamic programming (DP). To conquer the high complexity of DP, we propose two additional randomized heuristics, Las Vegas (LV) and Monte Carlo (MC) randomized algorithms, which perform even as good as DP with much smaller complexity. Besides, MC is a promising heuristic in practice as it has the advantage to deal with the big data environment. Extensive numerical experiments are constructed for the proposed algorithms in this article.

In smart city services, information systems can provide efficient and effective support during an emergency, and an emergency management system can make use of any available infrastructure network, such as the Internet of Things. However, ordinary communication infrastructures can be prone to disruptions or even failures during emergencies. Hence, it is necessary to present a fallback system in case of such failures. In this article, we propose such a fallback design for emergency management that relies on short-range multihop wireless communications. Specifically, we model the crowd by a multihop ad hoc network consisting of nodes (i.e., civilians with smartphones or wearable devices) that are capable of short-range communications, and address the problem of how to “diffuse” the crowd in an efficient and distributed fashion. The problem is subdivided into crowd density computation and crowd diffusion . We treat the area as a grid that is divided into square cells. Crowd density computation is to compute the density of each cell, for which we present efficient distributed algorithms that compute the density of each grid cell exactly. With the computed densities, crowd diffusion is to design a load-balancing strategy (to direct local movements of individual civilians) such that in a short time the nodes/civilians will become evenly distributed over the entire area. We present a distributed diffusion algorithm that has good performance. We conduct extensive simulations to evaluate the proposed algorithms, and the results corroborate our theoretical analyses.

Hard-capacitated k-means (HCKM) is one of the fundamental problems remaining open in combinatorial optimization and engineering. In HCKM, one is required to partition a given n-point set into k disjoint clusters with known capacity so as to minimize the sum of within-cluster variances. It is known to be at least APX-hard, and most of the work on it has been done from a meta heuristic or bi-criteria approximation perspective. To the best our knowledge, no constant approximation algorithm or existence proof of such an algorithm is known. As our main contribution, we propose an FPT(k) approximation algorithm with constant performance guarantee for HCKM in this paper.

In the past decades, with the exponential implementation of large-scale wireless networks such as Internet-of-Things, an enormous demand on designing the relative algorithms and protocols has come into our sight. As an important primitive function in wireless communication, the problem of leader election has attracted much attention in research. In this paper, we pursue efficient distributed solutions for leader election in large-scale wireless networks. Specifically, a simple but optimal distributed leader election algorithm in wireless networks with asynchronous wakeup nodes is proposed, under the practical Signal-to-Interference-plus-Noise (SINR) interference-depicting model. Our algorithm is randomized and can elect a leader in an asymptotically optimal time bound of Θ(log n) with high probability, where n is the number of nodes in network. The algorithm does not rely on any information about the network topology, needs only simple node capability to implement, and uses no encoding and decoding functions. Hence, the algorithm is efficient and energy-saving, which makes it possible to be implemented in a wide range of scenarios, and become a building block for many higher-level operations, like consensus, broadcast and so on.