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
2056643664 2144812583 2105749622 2950588791
We consider the problem of designing distributed mechanisms for joint congestion control and resource allocation in spatial-reuse TDMA wireless networks. The design problem is posed as a utility maximization subject to link rate constraints that involve both power allocation and transmission scheduling over multiple time-slots. Starting from the performance limits of a centralized optimization based on global network information,we proceed systematically in the development of distributed and transparent protocols. In the process,we introduce a novel decomposition method for convex optimization,establish its convergence for the utility maximization problem and demonstrate how it suggests a distributed solution based on flow control optimization and incremental updates of the transmission schedule.We develop a two-step procedure for finding the schedule updates and suggest two schemes for distributed channel reservation and power control under realistic interference models. Although the final protocols are suboptimal,we isolate and quantify the performance losses incurred by each simplification and demonstrate strong performance in examples. It is known that CSMA CA channel access schemes are not well suited to meet the high traffic demand of wireless mesh networks. One possible way to increase traffic carrying capacity is to use a spatial TDMA (STDMA) approach in conjunction with the physical interference model, which allows more aggressive scheduling than the protocol interference model on which CSMA CA is based. While an efficient centralized solution for STDMA with physical interference has been recently proposed, no satisfactory distributed approaches have been introduced so far. In this paper, we first prove that no localized distributed algorithm can solve the problem of building a feasible schedule under the physical interference model. Motivated by this, we design a global primitive, called SCREAM, which is used to verify the feasibility of a schedule during an iterative distributed scheduling procedure. Based on this primitive, we present two distributed protocols for efficient, distributed scheduling under the physical interference model, and we prove an approximation bound for one of the protocols. We also present extensive packet-level simulation results, which show that our protocols achieve schedule lengths very close to those of the centralized algorithm and have running times that are practical for mesh networks. Since wireless ad-hoc networks use shared communication medium, accesses to the medium must be coordinated to avoid packet collisions. Transmission scheduling algorithms allocate time slots to the nodes of a network such that if the nodes transmit only during the allocated time slots, no collision occurs. For real-time applications, by ensuring deterministic channel access, transmission scheduling algorithms have the added significance of making guarantees on transmission latency possible. In this paper we present a distributed transmission scheduling algorithm for hexagonal wireless ad-hoc networks with a particular focus on Wireless Sensor Networks. Afforded by the techniques of ad-hoc networks topology control, hexagonal meshes enable trivial addressing and routing protocols. Our transmission scheduling algorithm constructs network-wide conflict-free packet transmission schedule for hexagonal networks, where the overhead of schedule construction in terms of message exchanges is zero above and beyond that for topology control and other network control related functions. Furthermore, the schedule is optimal in the sense that the bottleneck node does not idle. We also present an implicit clock synchronization algorithm to facilitate scheduling. We derive the real time capacity of our scheduling algorithm. We present evaluations of our scheduling algorithm in the presence of topological irregularities using simulation. 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.