We consider the distributed and parallel construction of low-diameter decompositions with strong diameter. We present algorithms for arbitrary undirected, weighted graphs and also for undirected, weighted graphs that can be separated through k ∈ Õ(1) shortest paths. This class of graphs includes planar graphs, graphs of bounded treewidth, and graphs that exclude a fixed minor K_r. Our algorithms work in the PRAM, CONGEST, and the novel HYBRID communication model and are competitive in all relevant parameters. Given 𝒟 > 0, our low-diameter decomposition algorithm divides the graph into connected clusters of strong diameter 𝒟. For an arbitrary graph, an edge e ∈ E of length 𝓁_e is cut between two clusters with probability O(𝓁_e⋅log(n)/𝒟). If the graph can be separated by k ∈ Õ(1) paths, the probability improves to O(𝓁_e⋅log(log n)/𝒟). In either case, the decompositions can be computed in Õ(1) depth and Õ(m) work in the PRAM and Õ(1) time in the HYBRID model. In CONGEST, the runtimes are Õ(HD + √n) and Õ(HD) respectively. All these results hold w.h.p. Broadly speaking, we present distributed and parallel implementations of sequential divide-and-conquer algorithms where we replace exact shortest paths with approximate shortest paths. In contrast to exact paths, these can be efficiently computed in the distributed and parallel setting [STOC '22]. Further, and perhaps more importantly, we show that instead of explicitly computing vertex-separators to enable efficient parallelization of these algorithms, it suffices to sample a few random paths of bounded length and the nodes close to them. Thereby, we do not require complex embeddings whose implementation is unknown in the distributed and parallel setting.

Mobile Edge Computing (MEC) offloads service functionalities from central cloud to edge network and process user requests there, which reduces service latency and alleviates cloud burden. Only partial services can run on edge nodes with limited resource capacity. Both time varying and heterogeneity of services users requesting introduce great challenges for the resource utilization of edge nodes and user quality of service (QoS). Edge cooperation with joint optimization emerges to cope with this problem for MEC service provider. Recent researches focus on the non-cooperation or partial cooperation among edge nodes in local area network (LAN), their benefits are only explored on a small scale, and the users still face with resources waste and high service. This paper jointly optimizes service placing and task scheduling in MEC based on edge utility maximization and full cooperation of edge nodes in LAN. Edge full cooperation can place as many types of services as possible and capture more user requests in edge network so as to reduce the overall delay and edge energy consumption. Further considering the individual user QoS, we formularize the rewards in the edge utility to promote the local processing of user tasks. The joint optimization is a mixed integer nonlinear program problem which is NP-hard with high computational complexity. Therefore, we design a two-layer iterative strategy (TI-ST) based on Gibbs sampling and linear programming, which has polynomial computation complexity and has provably near optimal performance. Experimental results demonstrate the effectiveness of the proposed scheme when compared with the benchmark schemes.

We consider the problem of computing a compact routing scheme for a weighted undirected planar graph G := (V, E, w) in several models. For a given parameter ϵ > 0, we compute a routing scheme with stretch 1 + ϵ and labels and routing tables of size Õ(ϵ−1). In CONGEST, the construction takes Õ(ϵ−3 · HD) time, where HD denotes the network's hop-diameter. Further, it takes Õ(ϵ−3) time in a PRAM with O(n) processors and the novel HYBRID model. Thus, our algorithms are almost optimal in all relevant parameters. To achieve these results, we extend the divide-and-conquer framework of Li and Parter [STOC '19] and combine it with state-of-the-art distributed distance approximation algorithms [STOC '22].

With the development of big data and network technology, the rapidly growing data amount brings a great challenge to the performance optimization of Internet of Marine things (IoMaT). Both cutting down the redundant data communication and ensuring reliable communication of necessary data are the key issues IoMaT facing. Most existing studies focus on periodical and continuous-time data transmission mode of the source nodes once some data collection task starts, not considering decreasing the data transmission frequency efficiently in the source node. This study investigates the essential characteristics of marine data, formulates the attributes and collection characteristics (CC) of marine data, and modeling the customized data transmission scheme (DTS) based on the CC for the sake of avoiding the redundant data transmission and minimize the data transmission frequency in nature. Furthermore, two specific DTSs are present in terms of various attributes and CC of marine data to not only meet the different requirements of marine monitoring, but also reduce the network traffic. The simulation results show that the proposed schemes can effectively reduce the data transmission frequency and the energy consumption, prolong the network lifetime, and improve the data packet delivery ratio in IoMaT.

Limited bandwidth capacity and battery power are the unique characters of Underwater Sensor Networks (UWSNs). First this study introduces a competition scheme based on delay time. This scheme provides a selection method of relay nodes considering the limited bandwidth capacity. Then a heterogeneous nodes distribution strategy is proposed to balance the energy consumption of the whole UWSN. The ratio between the node initial energy of the adjacent annuluses is analyzed in a circular UWSN. Simulation results validate this design.

Lifetime prolonging is one significant research issue in underwater acoustic sensor networks (UASNs). First this paper analyzes the relationship between the receiving energy consumption and the transmission energy consumption in the acoustic communication of UASNs. The routing tree is built up on the factor of optimal transmission range. Then a hybrid data transmission mechanism based on energy level is proposed to balance energy consumption. The mechanism combines one-hop and multi-hop data transmission to underwater sink considering the current energy level of adjacent nodes. An optimal classification number of energy level has been evaluated through theoretical analysis. Our design will help prolong the lifetime of whole UASN. The simulation results of UASN's lifetime and the energy consumption of sensor nodes have proved the efficiency of the Energy-Level-based hybrid Transmission (ELT) mechanism.

Abstract Lifetime prolonging is one of the most significant issues in the research on underwater acoustic sensor networks (UASNs). Unbalanced energy consumption influences greatly the network lifetime. First this study discusses a probability‐based energy balance (PEB) scheme. The sensor nodes report the data to the sink by single‐hop direct transmission (DT) or by multi‐hop transmission (MT) under the probabilities. A centralized probabilities finding algorithm (PFA) can find a set of transmission probabilities to better balance the energy consumption. Then, a sub‐optimal distance (SOD)‐based data transmission scheme is proposed which is a distributed scheme and operates on each sensor node. It optimizes the slice width and selects the relays near the optimum transmission range. Simulations show that the two schemes can save more energy and prolong the network lifetime efficiently. Copyright © 2008 John Wiley & Sons, Ltd.