Search

In a multiple-message broadcast, an arbitrary number of messages originate at arbitrary nodes in the network at arbitrary times. The problem is to disseminate all these messages to the whole network. This paper gives the first randomized distributed multiple-message broadcast algorithm with worst-case performance guarantee in wireless ad hoc networks employing the SINR interference model which takes interferences from all the nodes in the network into account. The network model used in this paper also considers the harsh characteristics of wireless ad hoc networks: there is no prior structure, and nodes cannot perform collision detection and have little knowledge of the network topology. Under all these restrictions, our proposed randomized distributed multiple-message broadcast protocol can deliver any message m to all nodes in the network in O ( D + k + log 2 ⁡ n ) timeslots with high probability, where D is the network diameter, k is the number of messages whose broadcasts overlap with m , and n is the number of nodes in the network. We also study the lower bound for randomized distributed multiple-message broadcast protocols. In particular, we prove that any uniform randomized algorithm needs Ω ( D + k + log 2 ⁡ n log ⁡ log ⁡ log ⁡ n ) timeslots to disseminate k messages initially stored at k nodes. [ABSTRACT FROM AUTHOR]

In multi-hop radio networks, such as wireless ad-hoc networks and wireless sensor networks, nodes employ a MAC (Medium Access Control) protocol such as TDMA to coordinate accesses to the shared medium and to avoid interference of close-by transmissions. These protocols can be implemented using standard node coloring. The ( Δ + 1 ) -coloring problem is to color all nodes in as few timeslots as possible using at most Δ + 1 colors such that any two nodes within distance R are assigned different colors, where R is a given parameter and Δ is the maximum degree of the modeled unit disk graph using R as a scaling factor. Being one of the most fundamental problems in distributed computing, this problem is well studied and there is a long chain of algorithms prescribed for it. However, all previous works are based on abstract models, such as message passing models and graph based interference models, which limit the utility of these algorithms in practice. In this paper, for the first time, we consider the distributed ( Δ + 1 ) -coloring problem under the more practical SINR interference model. In particular, without requiring any knowledge about the neighborhood, we propose a novel randomized ( Δ + 1 ) -coloring algorithm with time complexity O ( Δ log ⁡ n + log 2 ⁡ n ) . For the case where nodes cannot adjust their transmission power, we give an O ( Δ log 2 ⁡ n ) randomized algorithm, which only incurs a logarithmic multiplicative factor overhead. [ABSTRACT FROM AUTHOR]

As an important concept to depict the freshness of an information when it arrives at the destination, the Age-of-Information (AoI) and its relative scheduling works can be a very useful tool to aggregate the information from the end devices to the edge servers in Internet of Vehicles, which can strongly support those time-sensitive services in intelligent transportation system. However, most of the previous works about the AoI scheduling on edge computing are the centralized ones, rely on the reliable communications, and ignore the mobility of vehicles, which may not suit the dynamic environment in Internet of Vehicles. In this paper, we consider the AoI optimization problem in a more comprehensive vehicle model, and present a distributed AoI optimization algorithm based on a single hop end-to-edge wireless network. With an arbitrary power control technique, our algorithm reaches an asymptotically optimal performance on minimizing the expectation of AoI. Both of theoretical analysis and extensive simulations are conducted to verify the correctness and efficiency of our proposed algorithm. [ABSTRACT FROM AUTHOR]