Desynchronization is one of the primitive services for complex networks because it arranges nodes to take turns accessing a shared resource. TDMA is a practical application of desynchronization because it allows node to share a common medium. In this paper, we propose a novel desynchronization algorithm using artificial force field called Multi-hop Desynchronization With an ARtificial Force field or M-DWARF and use it to solve TDMA problems in wireless sensor networks (WSNs). M-DWARF solves hidden terminal problems in multi-hop networks by using relative time relaying and improves resource utilization by employing force absorption. M-DWARF is suitable for use in WSNs because of its low complexity and autonomous operations. We implement M-DWARF using TinyOS and experiment it on both TelosB motes and TOSSIM. From our investigation, M-DWARF is the only desynchronization algorithm that achieves fast convergence with high stability, while maintaining channel utilization fairness. Moreover, we are the first to provide a stability analysis using dynamical systems and to prove that M-DWARF is stable at equilibrium. (This paper is the first part of the series Stable Desynchronization for Wireless Sensor Networks - (I) Concepts and Algorithms (II) Performance Evaluation (III) Stability Analysis)
Other works that are related to desynchronization protocols are distributed Time Division Multiple Access (TDMA) protocols. Distributed TDMA protocols are similar to M-DESYNC @cite_0 ; their protocols work on a granularity of time slots. Similar to M-DESYNC, many of the distributed TDMA protocols such as TRAMA @cite_3 , Parthasarathy @cite_20 , ED-TDMA @cite_22 , and Herman @cite_19 assume time is already slotted or all nodes are synchronized to achieve the same global clock. In our work, we do not require time synchronization and do not assume already slotted time. S. C. @cite_23 propose node-based and level-based TDMA scheduling algorithms for WSNs. Their techniques mainly derive from graph coloring algorithms in which the must have been predefined. In contrast, our desynchronization algorithms never predefine slots but rather allow nodes to adjust their slots with those in the neighborhood on-the-fly. K. S. @cite_17 survey distributed scheduling techniques for wireless mesh networks and A. @cite_14 provide an extensive survey of recent advances in TDMA algorithms in wireless multi-hop networks. Both the survey papers interestingly give a comprehensive overview of the TDMA scheduling algorithms and techniques that are still being investigated and further developed by wireless network researchers worldwide.
@cite_14 @cite_22 @cite_3 @cite_0 @cite_19 @cite_23 @cite_20 @cite_17
1966146195 2133591145 1986917282 2162626583 2950588791 2116567741
One of the major problems in wireless multihop networks is the scheduling of transmissions in a fair and efficient manner. Time Division Multiple Access (TDMA) seems to be one of the dominant solutions to achieve this goal since it is a simple scheme and can prolong the devices’ lifetime by allowing them to transmit only a portion of the time during conversation. For that reason, several TDMA scheduling algorithms may be found in the literature. The scope of this article is to classify the existing TDMA scheduling algorithms based on several factors, such as the entity that is scheduled, the network topology information that is needed to produce or maintain the schedule, and the entity or entities that perform the computation that produces and maintains the schedules, and to discuss the advantages and disadvantages of each category. MAC protocol controls the activity of wireless radio of sensor nodes directly so that it is the major consumer of sensor energy and the energy efficiency of MAC protocol makes a strong impact on the network performance. TDMA-based MAC protocol is inherently collision-free and can rule out idle listening since nodes know when to transmit. However, conventional TDMA protocol is not suitable for event-driven applications. In this paper, we present ED-TDMA, an event-driven TDMA protocol for wireless sensor networks. Then we conduct extensive simulations to compare it with other MAC protocols such as BMA, S-MAC, and LMAC. Simulation results show that ED-TDMA performs better for event-driven application in wireless sensor networks with high-density deployment and under low traffic. The traffic-adaptive medium access protocol (TRAMA) is introduced for energy-efficient collision-free channel access in wireless sensor networks. TRAMA reduces energy consumption by ensuring that unicast, multicast, and broadcast transmissions have no collisions, and by allowing nodes to switch to a low-power, idle state whenever they are not transmitting or receiving. TRAMA assumes that time is slotted and uses a distributed election scheme based on information about the traffic at each node to determine which node can transmit at a particular time slot. TRAMA avoids the assignment of time slots to nodes with no traffic to send, and also allows nodes to determine when they can become idle and not listen to the channel using traffic information. TRAMA is shown to be fair and correct, in that no idle node is an intended receiver and no receiver suffers collisions. The performance of TRAMA is evaluated through extensive simulations using both synthetic- as well as sensor-network scenarios. The results indicate that TRAMA outperforms contention-based protocols (e.g., CSMA, 802.11 and S-MAC) as well as scheduling-based protocols (e.g., NAMA) with significant energy savings. This paper presents a new desynchronization algorithm aimed at providing collision-free transmission scheduling for single-hop and acyclic multi-hop wireless sensor networks. The desynchronization approach is resilient to the hidden terminal problem and topology changes. Each node distributively converges upon a single collision-free transmission slot, utilizing only minimal neighbor information. In addition, we propose two strategies which facilitate increased convergence time. We evaluate the proposed algorithm via simulations over a range of network densities on both single-hop and acyclic multi- hop networks. Convergence and throughput comparison are performed against two previously proposed desynchronization algorithms. Finally, using an experimental tested of TelosB motes we verify the performance, practicality, and correctness of the desynchronization algorithm on varying network topologies. Wireless sensor networks benefit from communication protocols that reduce power requirements by avoiding frame collision. Time Division Media Access methods schedule transmission in slots to avoid collision, however these methods often lack scalability when implemented in networks subject to node failures and dynamic topology. This paper reports a distributed algorithm for TDMA slot assignment that is self-stabilizing to transient faults and dynamic topology change. The expected local convergence time is O(1) for any size network satisfying a constant bound on the size of a node neighborhood. An efficient scheduling scheme is a crucial part of Wireless Mesh Networks (WMNs)—an emerging communication infrastructure solution for autonomy, scalability, higher throughput, lower delay metrics, energy efficiency, and other service-level guarantees. Distributed schedulers are preferred due to better scalability, smaller setup delays, smaller management overheads, no single point of failure, and for avoiding bottlenecks. Based on the sequence in which nodes access the shared medium, repetitiveness, and determinism, distributed schedulers that are supported by wireless mesh standards can be classified as either random, pseudo-random, or cyclic schemes. We performed qualitative and quantitative studies that show the strengths and weaknesses of each category, and how the schemes complement each other. We discuss how wireless standards with mesh definitions have evolved by incorporating and enhancing one or more of these schemes. Emerging trends and research problems remaining for future research also have been identified.