Trickle is a polite gossip algorithm for managing communication traffic. It is of particular interest in low-power wireless networks for reducing the amount of control traffic, as in routing protocols (RPL), or reducing network congestion, as in multicast protocols (MPL). Trickle is used at the network or application level, and relies on up-to-date information on the activity of neighbors. This makes it vulnerable to interference from the media access control layer, which we explore in this paper. We present several scenarios how the MAC layer in low-power radios violates Trickle timing. As a case study, we analyze the impact of CSMA CA with ContikiMAC on Trickle’s performance. Additionally, we propose a solution called Cleansing that resolves these issues.
Various aspects of the Trickle algorithm have been studied so far. For example, in @cite_8 @cite_4 , Trickle has been observed as unfair in terms of load share - certain nodes transmit more often than others. Trickle in absence of a MAC layer has previously been analyzed, e.g., @cite_10 @cite_11 @cite_15 . Similarly, CSMA CA for low-power networks has been analyzed without considering the upper layers, e.g., @cite_18 @cite_5 . Finally, the potential problematic interaction between Trickle-based data dissemination and radio duty cycling has been sketched in @cite_3 , along with potential energy efficiency improvements by reducing the scope of single-hop broadcasts. However, to the best of the authors' knowledge, a detailed analysis on the interaction between Trickle and the MAC layer, consisting of both CSMA CA and radio duty cycling, their combined performance and potential problems in specific topologies, has not yet been conducted, which is what this paper aims to do. The analysis and the results presented in this paper explain the simulation results for MPL in @cite_23 @cite_2 , and the poor performance for small Trickle interval lengths.
@cite_18 @cite_4 @cite_8 @cite_3 @cite_23 @cite_2 @cite_5 @cite_15 @cite_10 @cite_11
2059990980 2109176650 2161281242 1524979472
In this paper, we investigate schemes for energy-efficient multi-hop broadcasting in large-scale dense Wireless Sensor Networks. We begin with an initial simplified study of the schemes for relay selection. Our first finding is that MPR-based (Multipoint Relay) mechanisms work poorly in a dense network while the recently proposed Multicast Protocol for Low power and Lossy Networks (MPL) protocol based on Trickle performs better. However, Trickle requires to overhear packet retransmissions in the vicinity, while sensor nodes try to avoid overhearing by periodically waking up and going to sleep to save energy. We propose Beacon-based Forwarding Tree (BFT), a new scheme that achieves similar performance to MPL, although it fits better the case of nodes with low radio duty cycling MACs of the type of beacon-enabled IEEE 802.15.4. Our scheme also guarantees network coverage and its optimized version results in the shortest path distance to the broadcast source at a cost of lesser load mitigation. We compare and discuss the measured performance of MPL on top of ContikiMAC and BFT over beacon-enabled 802.15.4 on a Contiki testbed. The experimental results of the comparisons show that BFT may achieve very good performance for a range of broadcast intensity, it has a predictable power consumption, a remarkable low power consumption for leaf nodes, and low loss rates. On the other hand, MPL over ContikiMAC can obtain very low duty cycles for low broadcast traffic. Trickle is a polite gossip algorithm for managing communication traffic. It is of particular interest in low-power wireless networks for reducing the amount of control traffic, as in routing protocols (RPL), or reducing network congestion, as in multicast protocols (MPL). Trickle is used at the network or application level, and relies on up-to-date information on the activity of neighbors. This makes it vulnerable to interference from the media access control layer, which we explore in this paper. We present several scenarios how the MAC layer in low-power radios violates Trickle timing. As a case study, we analyze the impact of CSMA CA with ContikiMAC on Trickle’s performance. Additionally, we propose a solution called Cleansing that resolves these issues. In much of the theoretical literature on wireless algorithms, issues of message dissemination are considered together with issues of contention management. This combination leads to complicated algorithms and analysis, and makes it difficult to extend the work to harder communication problems. In this paper, we present results of a current project aimed at simplifying such algorithms and analysis by decomposing the treatment into two levels, using abstract "MAC layer" specifications to encapsulate the contention management. We use two different abstract MAC layers: the basic one of [14, 15] and a new probabilistic layer. We first present a typical randomized contention-manageent algorithm for a standard graph-based radio network model We show that it implements both abstract MAC layers. We combine this algorithm with greedy algorithms for single-message and multi-message global broadcast and analyze the combination, using both abstract MAC layers as intermediate layers. Using the basic MAC layer, we prove a bound of O(D log(n ∈) log Δ) for the time to deliver a single message everywhere with probability 1 -- ∈, where D is the network diameter, n is the number of nodes, and Δ is the maximum node degree. Using the probabilistic layer, we prove a bound of O((D + log(n ∈)) log Δ), which matches the best previously-known bound for single-message broadcast over the physical network model. For multi-message broadcast, we obtain bounds of O((D + kΔ) log(n ∈) log Δ) using the basic layer and O((D + kΔ log(n ∈)) log Δ) using the probabilistic layer, for the time to deliver a message everywhere in the presence of at most k concurrent messages. This paper proposes and analyzes the performance of a simple frequency-agile CSMA MAC protocol. In this MAC, a node carrier-senses multiple frequency channels simultaneously, and it takes the first opportunity to transmit on any one of the channels when allowed by the CSMA backoff mechanism. We show that the frequency-agile MAC can effectively 1) boost throughput and 2) remove temporal starvation. Furthermore, the MAC can be implemented on the existing multiple-frequency setup in Wi-Fi using multi-radio technology, and it can co-exist with the legacy MAC using single radio. This paper provides exact stationary throughput analysis for regular 1D and thin-strip 2D CSMA networks using a "transfer-matrix" approach. In addition, accurate approximations are given for 2D grid networks. Our closed-form formulas accurately quantify the throughput gain of frequency-agile CSMA. To characterize temporal starvation, we use the metric of "mean residual access time" (MRAT). Our simulations and closed-form approximations indicate that the frequency-agile MAC can totally eliminate temporal starvation in 2D grid networks, reducing its MRAT by orders of magnitude. Finally, this paper presents a "coloring theorem" to justify the use of the frequency-agile MAC in general network topologies. Our analysis and theorem suggest that with enough frequency channels, the frequency-agile MAC can effectively decouple the detrimental interactions between neighboring links responsible for low throughput and starvation.