A Graph Coloring Based TDMA Scheduling Algorithm for Wireless Sensor Networks

Wireless sensor networks should provide with valuable service, which is called service-oriented requirement. To meet this need, a novel distributed graph coloring based time division multiple access scheduling algorithm (GCSA), considering real-time performance for clustering-based sensor network, is proposed in this paper, to determine the smallest length of conflict-free assignment of timeslots for intra-cluster transmissions. GCSA involves two phases. In coloring phase, networks are modeled using graph theory, and a distributed vertex coloring algorithm, which is a distance-2 coloring algorithm and can get colors near to $(\updelta +1)$ , is proposed to assign a color to each node in the network. Then, in scheduling phase, each independent set is mapped to a unique timeslot according to the set’s priority which is obtained by considering network structure. The experimental results indicate that GCSA can significantly decrease intra-cluster delay and increase intra-cluster throughput, which satisfies real-time performance as well as communication reliability.     

Distributed Priority Scheduling and Medium Access in Ad Hoc Networks

Providing Quality-of-Service in random access multi-hop wireless networks requires support from both medium access and packet scheduling algorithms. However, due to the distributed nature of ad hoc networks, nodes may not be able to determine the next packet that would be transmitted in a (hypothetical) centralized and ideal dynamic priority scheduler. In this paper, we develop two mechanisms for QoS communication in multi-hop wireless networks. First, we devise distributed priority scheduling, a technique that piggybacks the priority tag of a node's head-of-line packet onto handshake and data packets; e.g., RTS/DATA packets in IEEE 802.11. By monitoring transmitted packets, each node maintains a scheduling table which is used to assess the node's priority level relative to other nodes. We then incorporate this scheduling table into existing IEEE 802.11 priority backoff schemes to approximate the idealized schedule. Second, we observe that congestion, link errors, and the random nature of medium access prohibit an exact realization of the ideal schedule. Consequently, we devise a scheduling scheme termed multi-hop coordination so that downstream nodes can increase a packet's relative priority to make up for excessive delays incurred upstream. We next develop a simple analytical model to quantitatively explore these two mechanisms. In the former case, we study the impact of the probability of overhearing another packet's priority index on the scheme's ability to achieve the ideal schedule. In the latter case, we explore the role of multi-hop coordination in increasing the probability that a packet satisfies its end-to-end QoS target. Finally, we perform a set of ns-2 simulations to study the scheme's performance under more realistic conditions.     

一种用于水声传感网的MAC层协议

针对分簇的水声传感网,提出了一种基于时分多址（TDMA）的MAC层协议——Cluster-TDMA。该协议主要由规划阶段和传输阶段组成。规划阶段,首先由网关节点规划能造成簇间干扰的子节点的传输,其次由各簇头节点分别规划本簇内其他子节点的传输;传输阶段,子节点根据规划表周期性地向簇头节点发送数据,这些数据最终汇聚到网关节点。该协议简单有效地解决了引起簇间干扰子结点的传输规划问题。C++仿真实验表明,该协议具有良好的吞吐率和能量效率性能。     

DRAND: Distributed Randomized TDMA Scheduling for Wireless Ad Hoc Networks

This paper presents a distributed implementation of RAND, a randomized time slot scheduling algorithm, called DRAND. DRAND runs in O(delta ) time and message complexity where delta is the maximum size of a two-hop neighborhood in a wireless network while message complexity remains O(delta ), assuming that message delays can be bounded by an unknown constant. DRAND is the first fully distributed version of RAND. The algorithm is suitable for a wireless network where most nodes do not move, such as wireless mesh networks and wireless sensor networks. We implement the algorithm in TinyOS and demonstrate its performance in a real testbed of Mica2 nodes. The algorithm does not require any time synchronization and is shown to be effective in adapting to local topology changes without incurring global overhead in the scheduling. Because of these features, it can also be used even for other scheduling problems such as frequency or code scheduling (for FDMA or CDMA) or local identifier assignment for wireless networks where time synchronization is not enforced. We further evaluate the effect of the time-varying nature of wireless links on the conflict-free property of DRAND-assigned time slots. This experiment is conducted on a 55-node testbed consisting of the more recent MicaZ sensor nodes.     

An algorithm that uses forward planning to expedite conflict-freetraffic assignment in time-multiplex switching systems

In multichannel telecommunication networks, switching systems, and processor-memory interconnects, the need for conflict-free traffic assignment arises whenever packets (or requests) are to be directed from input buffers (processors) to specific outlets (modules). This paper presents an algorithm, based on forward planning, which can be used in the above-mentioned applications for scheduling conflict-free transfers of packets from inputs to outputs. The performance of the algorithm is evaluated in the sense of throughput and delay and is compared with that of system of distinct representatives (SDR), an earlier proposed algorithm featuring 100% assignment efficiency. Then, its worst-case computational complexity is compared with that of SDR and several suboptimal (but low complexity) algorithms reported in literature. The proposed forward planning algorithm is shown to have the lowest order of computational complexity and permits simpler buffer organization and access modes. Moreover, it is shown that forward planning of packet transmissions offers significant performance improvements if the finite capacity of buffers is taken into account     

Joint scheduling and routing with power control for centralized wireless sensor networks

We consider a TDMA-based multi-hop wireless sensor network, where nodes send data to a sink, which is aware of received powers at all receivers; the sink is responsible for creating the network topology and assigning time slots to links. Under this centralized approach, we propose two algorithms that jointly define the tree topology connecting nodes to the sink, and assign time slots, avoiding any packet loss. In contrast with previous works, the proposed algorithms accurately account for interference effects; when evaluating the signal-to-interference ratio to establish the tree and schedule transmissions, we consider the sum of all actual interfering signals, a fact of relevance for networks with increasing number of nodes. Optimal selection of transmit powers, minimizing energy consumption, is also applied. Our algorithms are compared to a benchmark solution and other proposals from the literature; it is shown that they bring to better radio resource utilization, higher throughput and lower energy consumption, while keeping the average delay limited.

     

Active caching: a transmission method to guarantee desired communication reliability in wireless sensor networks

Due to the high packet loss rate during multi-hop transmissions in wireless sensor networks, more reliable endto- end data transmission is desirable. Because wireless sensor network applications require various levels of communication reliability (CR), the end-to-end data transmission should satisfy the desired CR of the applications. In this letter, we propose a flexible loss recovery mechanism for sensor network applications with various CRs. The proposed scheme caches data packets at intermediate nodes over routing paths computed by CR to retransmit lost packets during multi-hop transmissions. Because the proposed scheme presents a tradeoff between end-to-end delays and memory requirements dependent on CR, it can be used flexibly in various sensor network applications.     

A Centralized Mechanism for Preventing DDOS Attack in Wireless Sensor Networks

Wireless sensor networks face numerous limitations. Security and Privacy are the two most essential parameters that require consideration in wireless sensor networks for conveying responsive information amid basic applications. High density and limited communication range of sensor nodes, forwarding packets in sensor networks have caused the performance of during multi-hop data transmission. Hence communication with different devices these days are not secure, due to the absence of centralized monitoring and overprotective requirements. This paper is related to speak about Distributed Denial of Service which debilitates the ability of the network and the data being transmitted. The earlier system guarantees the WSN through a self arranged and confined procedure between the nodes in the sensor environment. Here, the authors present the Centralized Detect Eliminate and Control algorithm for authorization and centralized monitoring component to discover the node that has turned into a victim node and to get rid of the information communicated to the fatality node from the neighbour nodes. Overprotective of the communication between the nodes leads to dependability. The simulation results improve the malicious node detection rate and increase the various parameters like throughput and reduce the average delay. This leads to, the overall detection rate built, eventually enhancing the parameters of the network environment.

     

Dynamic Spectrum Sharing for OFDMA-Based Multi-hop Cognitive Radio Networks with Priority

In this paper, we propose a resource assignment scheme of a secondary user (SU) for a multi-hop cognitive radio network. In multi-hop networks, since each link has different SNR because of their different distance between stations and multipath fading, the link of the smallest SNR is the bottleneck. For overcoming this problem, it is proposed to give a priority to each link based on the link SNR and to assign the resource blocks (RBs) in ordering of instantaneous SNR on the link. This link priority information is shared among nodes through a control channel. Then, we assign the selected SU RB to each SU node according to the SNR ordering with distributed manner. We confirm the effectiveness of the proposed SU RB assignment by using computer simulation.     

Routing protocol over lossy links for ISA100.11a industrial wireless networks

This paper proposes novel routing and topology control algorithms for industrial wireless sensor networks (IWSNs) based on the ISA100.11a standard. The proposed algorithms not only reduces energy consumption at the node level but also reduces packet latency at the network level. Using the residual energy and packet reception rate of neighbor nodes, the source node can estimate the highest election weight. Hence, packets are conveyed by a multi-hop forwarding scheme from source nodes to the sink by the optimal path. Furthermore, energy consumption and network latency are minimized using integer linear programming. Simulation results show that the proposed algorithms are fully effective in terms of energy conservation and network latency for IWSNs.     

A Novel Distributed Scheduling Algorithm for Downlink Relay Networks

To extend network coverage and to possibly increase data packet throughput, the future wireless cellular networks could adopt relay nodes for multi-hop data transmission. This letter proposes a novel distributed scheduling algorithm for downlink relay networks. Soft-information indicating the probability of activating each network link is exchanged iteratively among neighboring network nodes to determine an efficient schedule. To ensure collision-free simultaneous data transmissions, collision-avoiding local constraint rules are enforced at each network node. To increase resource utility, the soft-information is weighted according to the urgency of data transmission across each link, which also helps maintain throughput fairness among network users.     

Multi-factor and Distributed Clustering Routing Protocol in Wireless Sensor Networks

One of important issues in wireless sensor networks is how to effectively use the limited node energy to prolong the lifetime of the networks. Clustering is a promising approach in wireless sensor networks, which can increase the network lifetime and scalability. However, in existing clustering algorithms, too heavy burden of cluster heads may lead to rapid death of the sensor nodes. The location of function nodes and the number of the neighbor nodes are also not carefully considered during clustering. In this paper, a multi-factor and distributed clustering routing protocol MFDCRP based on communication nodes is proposed by combining cluster-based routing protocol and multi-hop transmission. Communication nodes are introduced to relay the multi-hop transmission and elect cluster heads in order to ease the overload of cluster heads. The protocol optimizes the election of cluster nodes by combining various factors such as the residual energy of nodes, the distance between cluster heads and the base station, and the number of the neighbor nodes. The local optimal path construction algorithm for multi-hop transmission is also improved. Simulation results show that MFDCRP can effectively save the energy of sensor nodes, balance the network energy distribution, and greatly prolong the network lifetime, compared with the existing protocols.     

The Maximum Throughput of A Wireless Multi-Hop Path

In this paper, the maximum end-to-end throughput that can be achieved on a wireless multi-hop path is investigated analytically. The problem is modeled using the conflict graph, where each link in the multi-hop path is represented uniquely by a vertex in the conflict graph and two vertices are adjacent if and only if the associated links mutually interfere. Using the conflict graph and the linear programming formulations of the problem, we analyzed the maximum end-to-end throughput of a wireless multi-hop path a) in a simple scenario where nodes are optimally placed and each node can only interfere with the transmission of its adjacent nodes along the path, and b) in a more complicated scenario where nodes are randomly placed and each node can interfere with the transmission of any number of nearby nodes along the path in both a) an error free radio environment and b) an erroneous radio environment. The maximum end-to-end throughputs for each of the above four scenarios are obtained analytically. We show that the maximum achievable end-to-end throughput is determined by the throughput of its bottleneck clique, where a clique is a maximal set of mutually adjacent vertices in the associated conflict graph. Further our analysis suggests the optimum scheduling algorithm that can be used to achieve the maximum end-to-end throughput and that it is convenient to use the (maximal) independent sets as the basic blocks for the design of scheduling algorithms. The findings in this paper lay guidelines for the design of optimum scheduling algorithms. They can be used to design computationally efficient algorithms to determine the maximum throughput of a wireless multi-hop path and to design a scheduling algorithm to achieve that throughput.     

Contrôle de puissance dans les réseaux ad-hoc

In an ad-hoc network, mobile stations communicate with each other using multi-hop wireless links. There is no stationary infrastructure such as base stations. Each node in the network also acts as a router, forwarding data packets for other nodes. In this architecture, mobile stations have a multi-hop path, via other mobile stations acting as intermediaries or relays, to indirectly forward packets from source to destination. Adjusting the transmitted power is extremely important in ad-hoc networks due to at least the following reasons. The transmitted power of the radio terminals determines the network topology. The network topology in turn has considerable impact on the throughput (fraction of packets, sent by a source, and successfully received at the receiver) performance of the network. The need for power efficiency must be balanced against the lifetime of each individual node and the overall life of the network. Power control problem can be classified in one of three categories. The first class comprises of strategies to find an optimal transmitted power to control the connectivity properties of the network. The second class of approaches could be called power aware routing. Most schemes use some shortest path algorithm with a power based metric, rather than a hop count based metric. The third class of approaches aim at modifying the mac layer. We use distributed power control algorithms initially proposed for cellular networks. We establish a classification of power control algorithms for wireless ad-hoc networks. We evaluate these algorithms in anIeee 802.11b multi-hop wireless ad-hoc LAN environment. Results show the advantage of power control in maximizing signal-to-interference ratio and minimizing transmitted power.     

A Class of Decentralized Routing Algorithms Using Relaxation

An important problem in packet-switched communication networks is the optimal assignment of routes to the message packets. An optimal routing assignment is one which chooses network paths for the packets in a way that minimizes some cost function, typically average message delay. A class of optimal routing algorithms is described which utilize a type of iterative computation known as relaxation. Computation is decentralized in the sense that each node computes its routing strategy using only information supplied from adjacent nodes. Being iterative, the algorithms are inherently adaptive. The routing computation is based conceptually on an electrical network analog for the optimization problem. We show that a simple, convergent relaxation procedure can be used to "solve" the analog network, thereby yielding the optimal routing strategy. A simple example is presented to illustrate the method. In general, the computational load compares favorably with other (centralized) methods, although further work is needed to obtain quantitive comparisons in specific cases.     

Lifetime Maximization Based on Coverage and Connectivity in Wireless Sensor Networks

We consider information retrieval in a wireless sensor network deployed to monitor a spatially correlated random field. We address optimal sensor scheduling and information routing under the performance measure of network lifetime. Both single-hop and multi-hop transmissions from sensors to an access point are considered. For both cases, we formulate the problems as integer programming based on the theories of coverage and connectivity in sensor networks. We derive upper bounds for the network lifetime that provide performance benchmarks for suboptimal solutions. Suboptimal sensor scheduling and data routing algorithms are proposed to approach the lifetime upper bounds with reduced complexity. In the proposed algorithms, we consider the impact of both the network geometry and the energy consumption in communications and relaying on the network lifetime. Simulation examples are used to demonstrate the performance of the proposed algorithms as compared to the lifetime upper bounds.     

Minimum Interference Channel Assignment in Multiradio Wireless Mesh Networks

In this paper, we consider multi-hop wireless mesh networks, where each router node is equipped with multiple radio interfaces and multiple channels are available for communication. We address the problem of assigning channels to communication links in the network with the objective of minimizing overall network interference. Since the number of radios on any node can be less than the number of available channels, the channel assignment must obey the constraint that the number of different channels assigned to the links incident on any node is atmost the number of radio interfaces on that node. The above optimization problem is known to be NP-hard. We design centralized and distributed algorithms for the above channel assignment problem. To evaluate the quality of the solutions obtained by our algorithms, we develop a semidefinite program and a linear program formulation of our optimization problem to obtain lower bounds on overall network interference. Empirical evaluations on randomly generated network graphs show that our algorithms perform close to the above established lower bounds, with the difference diminishing rapidly with increase in number of radios. Also, ns-2 simulations as well as experimental studies on testbed demonstrate the performance potential of our channel assignment algorithms in 802.11-based multi-radio mesh networks.     

A scalable joint routing and scheduling scheme for large-scale wireless sensor networks

The multihop configuration of a large-scale wireless sensor network enables multiple simultaneous transmissions without interference within the network. Existing time division multiple access (TDMA) scheduling schemes exploit gain based on the assumption that the path is optimally determined by a routing protocol. In contrast, our scheme jointly considers routing and scheduling and introduces several new concepts. We model a large-scale wireless sensor network as a tiered graph relative to its distance from the sink, and introduce the notion of relay graph and relay factor to direct the next-hop candidates toward the sink fairly and efficiently. The sink develops a transmission and reception schedule for the sensor nodes based on the tiered graph search for a set of nodes that can simultaneously transmit and receive. The resulting schedule eventually allows data from each sensor node to be delivered to the sink. We analyze our scheduling algorithm both numerically and by simulation, and we discuss the impact of protocol parameters. Further, we prove that our scheme is scalable to the number of nodes, from the perspectives of mean channel capacity and maximum number of concurrent transmission nodes. Compared with the existing TDMA scheduling schemes, our scheme shows better performance in network throughput, path length, end-to-end delay, and fairness index.     

Energy-Efficient Scheduling for Wireless Sensor Networks

We consider the problem of minimizing the energy needed for data fusion in a sensor network by varying the transmission times assigned to different sensor nodes. The optimal scheduling protocol is derived, based on which we develop a low-complexity inverse-log scheduling (ILS) algorithm that achieves near-optimal energy efficiency. To eliminate the communication overhead required by centralized scheduling protocols, we further derive a distributed inverse-log protocol that is applicable to networks with a large number of nodes. Focusing on large-scale networks with high total data rates, we analyze the energy consumption of the ILS. Our analysis reveals how its energy gain over traditional time-division multiple access depends on the channel and the data-length variations among different nodes.     

Multiple access protocol for power-controlled wireless access nets

We consider ad hoc wireless networks that are configured as Mobile Backbone Networks. A hierarchical network architecture is synthesized, consisting of Access Nets (ANets) and Backbone Nets (BNets). Each ANet is managed by a (dynamically elected) Backbone Node (BN) that is equipped with higher capability (transmission and processing) modules. The BNs are chosen from currently active mobile backbone-capable nodes or are represented by (ground and/or airborne) unmanned vehicles (UVs) that are guided into selected positions. We develop and investigate a new joint power controlled medium access control (MAC) algorithm for wireless access nets (ANets). Under our new protocol, the net backbone node instructs the ANet nodes to make power control adjustments while simultaneously allocating to them slots for the requested transmissions of their packets. This algorithm, in contrast to other employed conventional graph-based scheduling algorithms, satisfies the requirement that a minimum signal-to-interference and noise ratio (SINR) is met at all intended receivers. We show our algorithm to lead to a significant increase in the net throughput level by attaining high spatial reuse.