Efficient multi-hop scheduling algorithms for packet transmissions in WDM optical star networks

This paper proposes multi-hop scheduling algorithms for the All-to-All Broadcast (AAB) problem in Wavelength Division Multiplexed (WDM) optical star networks. The multi-hop AAB problem can be split into two subproblems: Logical Topologies Construction (LTC) problem, and Transmission Scheduling (TS) problem. For improving the efficiency of multi-hop scheduling, we focus on a new multi-hop transmission model and transfer the LTC problem to a special case of the Round Robin Tournament (RRT) problem. In the proposed logical topologies, our multi-hop scheduling algorithms can easily overlap the tuning latency and reduce the number of tuning operations on each node. We compare our results with previous research in terms of schedule length. Overall results indicate that our multi-hop scheduling algorithms have better performance than previous algorithms.     

Interference-aware broadcast scheduling in wireless networks

In this paper, we study the Interference-Aware Broadcast Scheduling problem, where all nodes in the Euclidean plane have a transmission range and an interference range equal to r and α r for α ? 1, respectively. Minimizing latency is known to be NP-Hard even when α = 1. The network radius D, the maximum graph distance from the source to any node, is also known to be a lower bound.We formulate the problem as integer programs (IP) and optimally solve moderate-size instances. We also propose six variations of heuristics, which require no pre-processing of inputs, based on the number of receivers gained by each additional simultaneous transmitting node. The experimental results show that the best heuristics give solutions that exceed the optimal solutions by only 13–20%. Further, an O(αD) schedule is proven to exist yielding an O(α) approximation algorithm.     

Efficient algorithms for scheduling data broadcast

With the increasing acceptance of wireless technology, mechanisms to efficiently transmit information to wireless clients are of interest. The environment under consideration is asymmetric in that the information server has much more bandwidth available, as compared to the clients. It has been proposed that in such systems the server should broadcast the information periodically. A broadcast schedule determines what is broadcast by the server and when. This paper makes the simple, yet useful, observation that the problem of broadcast scheduling is related to the problem of fair queueing. Based on this observation, we present a log‐time algorithm for scheduling broadcast, derived from an existing fair queueing algorithm. This algorithm significantly improves the time‐complexity over previously proposed broadcast scheduling algorithms. Modification of this algorithm for transmissions that are subject to errors is considered. Also, for environments where different users may be listening to different number of broadcast channels, we present an algorithm to coordinate broadcasts over different channels. Simulation results are presented for proposed algorithms.     

Efficient burst scheduling algorithms in optical burst-switched networks using geometric techniques

Optical burst switching (OBS) is a promising paradigm for the next-generation Internet. In OBS, a key problem is to schedule bursts on wavelength channels, whose bandwidth may become fragmented with the so-called void (or idle) intervals, using both fast and bandwidth efficient algorithms so as to reduce burst loss. To date, two well-known scheduling algorithms, called Horizon and LAUC-VF, have been proposed in the literature, which trade off bandwidth efficiency for fast running time and vice versa, respectively. In this paper, we propose a set of novel burst scheduling algorithms for OBS networks with and without fiber delay lines (FDLs) utilizing the techniques from computational geometry. In networks without FDLs, our proposed minimum-starting-void (Min-SV) algorithm can schedule a burst in O(logm) time, where m is the total number of void intervals, as long as there is a suitable void interval. Simulation results suggest that our algorithm achieves a loss rate which is at least as low as LAUC-VF, but can run much faster. In fact, its speed can be almost the same as Horizon (which has a much higher loss rate). In networks with FDLs, our proposed batching FDL algorithm considers a batch of FDLs to find a suitable FDL to delay a burst which would otherwise be discarded due to contention, instead of considering the FDLs one by one. The average running time of this algorithm is therefore significantly reduced from that of the existing burst scheduling algorithms. Our algorithms can also be used as algorithmic tools to speed up the scheduling time of many other void-filling scheduling algorithms.     

Quantized feedback MIMO scheduling for heterogeneous broadcast networks

One-bit quantization of signal-to-interference-plus-noise ratio is discussed in literature for user scheduling in homogeneous network where users are assumed to have equal signal-to-noise ratio (SNR). It is mentioned in literature that 1-bit quantization with fixed quantization threshold does not achieve multiuser diversity. Moreover, the system sum-rate achieved by this lags significantly behind that of full feedback scheme. Two multi-bit quantized feedback scheduling schemes are proposed for broadcast network with heterogeneous users experiencing different channel statistics. It is presented that these two schemes with fixed optimum quantization thresholds profit from the diversity provided by independent and identically distributed channels. Moreover, proposed optimistic multi-bit quantized scheduling scheme achieves higher system sum-rate than the proposed multi-bit quantized scheme by addressing the limitations of the later one. The optimum quantization thresholds depend on the number of transmit antennas and system SNR. Moreover, these multi-bit quantized feedback scheduling schemes also ensure user fairness. Simulation results are presented to support the numerical analysis.     

An evolutionary algorithm for broadcast scheduling in wireless multihop networks

A technical challenge in successful deployment and utilization of wireless multihop networks (WMN) are to make effective use of the limited channel bandwidth. One method to solve this challenge is broadcast scheduling of channel usage by the way of time division multiple access (TDMA). Three evolutionary algorithms, namely genetic algorithm (GA), immune genetic algorithm (IGA) and memetic algorithm (MA) are used in this study to solve broadcast scheduling for TDMA in WMN. The aim is to minimize the TDMA cycle length and maximize the node transmissions with reduced computation time. In comparison to GA and IGA, MA actively aim on improving the solutions and is explicitly concerned in exploiting all available knowledge about the problem. The simulation results on numerous problem instances confirm that MA significantly outperforms several heuristic and evolutionary algorithms by solving well-known benchmark problem in terms of solution quality, which also demonstrates the effectiveness of MA in efficient use of channel bandwidth.     

Optimal broadcast scheduling in packet radio networks using meanfield annealing

We present an efficient broadcast scheduling algorithm based on mean field annealing (MFA) neural networks. Packet radio (PR) is a technology that applies the packet switching technique to the broadcast radio environment. In a PR network, a single high-speed wideband channel is shared by all PR stations. When a time-division multi-access protocol is used, the access to the channel by the stations' transmissions must be properly scheduled in both the time and space domains in order to avoid collisions or interferences. It is proven that such a scheduling problem is NP-complete. Therefore, an efficient polynomial algorithm rarely exists, and a mean field annealing-based algorithm is proposed to schedule the stations' transmissions in a frame consisting of certain number of time slots. Numerical examples and comparisons with some existing scheduling algorithms have shown that the proposed scheme can find near-optimal solutions with reasonable computational complexity. Both time delay and channel utilization are calculated based on the found schedules     

A parallel algorithm for broadcast scheduling problems in packetradio networks

A parallel algorithm based on an artificial neural network model for broadcast scheduling problems in packet radio networks is presented. The algorithm requires n×m processing elements for an n-mode-m-slot radio network problem. The algorithm is verified by simulating 13 different networks     

Centralized broadcast scheduling in packet radio networks via genetic-fix algorithms

An important, yet difficult, problem in the design of a packet radio network is the determination of a conflict-free broadcast schedule at a minimum cycle length. We first formulate the problem via a within-two-hop connectivity matrix and then, by assuming a known cycle length, determine a conflict-free scheduling pattern using a centralized approach that exploits the structure of the problem via a modified genetic algorithm. This algorithm, called genetic-fix, generates and manipulates individuals with fixed size (i.e., in binary representation, the number of ones is fixed) and therefore, can reduce the search space substantially. We also propose a method to find a reasonable cycle length and shorten it gradually to obtain a near-optimal one. Simulations on three benchmark problems showed that our approach could achieve 100% convergence to solutions with optimal cycle length within reasonable time.     

Packet scheduling in broadcast WDM networks with arbitrarytransceiver tuning latencies

We consider the problem of scheduling packet transmissions in a broadcast, single-hop wavelength-division multiplexing (WDM) network, with tunability provided only at one end. Our objective is to design schedules of minimum length to satisfy a set of traffic requirements given in the form of a demand matrix. We address a fairly general version of the problem as we allow arbitrary traffic demands and arbitrary transmitter tuning latencies. The contribution of our work is twofold, First we define a special class of schedules which permit an intuitive formulation of the scheduling problem. Based on this formulation we present algorithms which construct schedules of length equal to the lower bound provided that the traffic requirements satisfy certain optimality conditions. We also develop heuristics which, in the general case, give schedules of length equal or very close to the lower bound. Secondly, we identify two distinct regions of network operation. The first region is such that the schedule length is determined by the tuning requirements of transmitters; when the network operates within the second region however, the length of the schedule is determined by the traffic demands, not the tuning latency. The point at which the network switches between the two regions is identified in terms of system parameters such as the number of nodes and channels and the tuning latency. Accordingly, we show that it is possible to appropriately dimension the network to minimize the effects of even large values of the tuning latency     

Heuristic approach for broadcast scheduling,problem in wireless mesh networks

Disasters can be natural and human-initiated events that interrupt the usual functioning of people on a large scale. Region where disasters have occurred causes hazards to the public of that area and to the rescue teams. Disaster causes the damage to the communication network infrastructure also. Once the communication infrastructure is damaged, it is very difficult to the rescue teams to actively involve in relief operation. To handle these hazards, different wireless technologies can be initiated in the area of disaster. This paper discusses the innovative wireless technology for disaster management. Specifically, issues related to the broadcast scheduling problem in wireless mesh network is deployed efficiently during disaster relief are discussed. A domain specific memetic algorithm is proposed for solving the optimum time division multiple access broadcast scheduling problem in wireless mesh networks. The aim is to increase the total number of transmissions in optimized time slot with high channel utilization in a less computation time. Simulation results showed that our memetic algorithm approach to this problem achieves 100% convergence to solutions within reduced computation time while compared to recent efficient algorithms. The results were compared with several heuristic and non-heuristic algorithms for broadcast scheduling problem.     

Topology-transparent time division multiple access broadcast scheduling in multihop packet radio networks

Many topology-dependent transmission scheduling algorithms have been proposed to minimize the time-division multiple-access frame length in multihop packet radio networks (MPRNs), in which changes of the topology inevitably require recomputation of the schedules. The need for constant adaptation of schedules-to-mobile topology entails significant problems, especially in highly dynamic mobile environments. Hence, topology-transparent scheduling algorithms have been proposed, which utilize Galois field theory and Latin squares theory. We discuss the topology-transparent broadcast scheduling design for MPRNs. For single-channel networks, we propose the modified Galois field design (MGD) and the Latin square design (LSD) for topology-transparent broadcast scheduling. The MGD obtains much smaller minimum frame length (MFL) than the existing scheme while the LSD can even achieve possible performance gain when compared with the MGD, under certain conditions. Moreover, the inner relationship between scheduling designs based on different theories is revealed and proved, which provides valuable insight. For topology-transparent broadcast scheduling in multichannel networks, in which little research has been done, the proposed multichannel Galois field design (MCGD) can reduce the MFL approximately M times, as compared with the MGD when M channels are available. Numerical results show that the proposed algorithms outperform existing algorithms in achieving a smaller MFL.     

Intra-ONU bandwidth scheduling in Ethernet passive optical networks

Quality-of-service (QoS) support in Ethernet passive optical networks (EPON) is a crucial concern. However, most studies have only focused on optical line terminal (OLT) capacity allocation amongst multiple optical network units (ONU), and the further issue of intra-ONU allocation remains open. In this work a novel decentralized intra-ONU solution is presented using virtual-time schedulers. Results confirm good performance for a wide range of input traffic classes and loads.     

A scheduling application for WDM optical networks

Optical networking using WDM technology has matured considerably, and commercial WDM network equipment and WDM network control and management prototypes have appeared. To use such a network efficiently, a scheduling facility and its enabling mechanisms have to be provided. This scheduling facility should be integrated to interoperate with the rest of the network control and management software such as connection manager or signaling daemon. We present a scheduling application to address this need. The architecture for the application and its key components are presented. Agent-related enabling mechanisms are introduced to monitor the optical signal quality and collect performance measurements. A resource broker is used to manage the communication and interoperability between agents and the application. An event service is developed to decouple the communication between the agents and the scheduling application, and to enable the communication among the agents themselves. The scheduling application consists of the quality of signal information and threshold objects, current network usage, history data module, scheduling module, and access to a performance database. To provide traffic control and high network resource utilization, the application is equipped with wavelength scheduling algorithms. An experimental study for the basic scheduling algorithms has been conducted over the MONET DC network.     

Physical impairment aware scheduling in optical burst switched networks

Optical burst switching (OBS) presents itself as a promising technology for bridging the gap between optical wavelength switching and optical packet switching. Increasingly, researchers attempt to incorporate more realistic constraints into the design of OBS networks. Optical signal transmission quality is subject to various types of physical impairment introduced by optical fibers, switching equipment, or other network components. The signal degradation due to physical impairments may be significant enough such that the bit-error rate of received signals is unacceptably high at the destination, rendering the signal not usable. In this paper, based on earlier work, we study the burst scheduling problem in OBS networks, taking into account physical impairment effects. We propose three effective burst scheduling algorithms: (1) a JET based Physical Impairment Constrained Algorithm (JETPIC), (2) an Integrated Physical Impairment Constrained Algorithm (IPIC), and (3) an Enhanced Integrated Physical Impairment Constrained Algorithm (EIPIC). At an OBS node, the proposed algorithms schedule bursts for transmission by searching for available resources as well as verifying signal quality. Our simulation results show that the proposed algorithms are effective in terms of reducing the burst blocking probability. In general, algorithm JETPIC outperforms algorithms IPIC and EIPIC in burst blocking probability and average end-to-end delay performance.

Impairment-aware ordered scheduling in dual-header optical burst switched networks

Optical burst switching (OBS) is a promising technology for bridging the gap between optical wavelength switching and optical packet switching. Optical signal transmission quality is subject to various types of physical impairment introduced by optical fibers, switching elements, or other network components. The signal degradation due to physical impairment may be significant enough such that the bit-error rate of received signals is unacceptably high at the destination, rendering the signal to not usable. In this article, based on earlier study, we study the burst-scheduling problem in OBS networks using two control packets for each data burst, taking into account physical impairment effects. We propose a burst-scheduling algorithm that accommodates incoming bursts by primary path routing, deflection routing, and burst scheduling. We design an admission control mechanism to use network resources efficiently. At an OBS node, the proposed algorithm schedules bursts for transmission by searching for available resources as well as verifying signal quality. Our simulation results demonstrate that the proposed algorithm is effective in terms of reducing the burst-blocking probability.     

Optimal all-to-all broadcast in WDM optical networks with breakdown or power-off transceivers

All-to-all broadcast is an interesting special case of the packet transmission scheduling in which every pair of nodes has exactly one packet to be transferred. This paper considers the all-to-all broadcast problem in wavelength division multiplexed (WDM) optical star network with some breakdown or power-off transceivers. For reaching high data transmission rates, we will focus the problem on the all-optical scheduling where the traffic reaches its destination in single-hop without being converted to electronic form. Each transmitter is tunable with an associated tuning delay and each receiver is fixed-tuned to one of available wavelengths. In this model, we study two kinds of all-to-all broadcast problems depending on whether each node transmits packets to all nodes including or except itself. We identify the lower bound of the scheduling length for each kind of problems and propose single-hop scheduling algorithms to find the optimal solution in both terms of arbitrary number of wavelengths and value of tuning latency.     

Efficient time gating in ultrafast optical TDM networks

Ultrafast optical communication is the backbone of high-speed global networking infrastructure. Optical time division multiplexing (OTDM) is a popular technique for embedding data from many simultaneous users on a single optical channel. This paper studies the optimal clock signal used in optical time gating to extract the data of the desired user in an OTDM network. We show that the pulse width of the clock signal can be optimized to achieve a minimum bit error rate (BER) in these networks. In this paper, we assume that the optical clock signal used for time gating has jitter, and there is therefore a delay variation between the clock and data signals. We model this delay as a zero mean Gaussian random variable. Using this model, an analytical BER expression is derived for systems with Gaussian pulses. In the numerical results, we find the optimal values of the clock pulse width by evaluating the BER versus the pulse width for different variances of the delay. Simulation results are also presented to evaluate the accuracy of the analytical expression.     

EMS: Efficient mobile sink scheduling in wireless sensor networks

Sink scheduling, in the form of scheduling multiple sinks among the available sink sites to relieve the level of traffic burden, is shown to be a promising scheme in wireless sensor networks (WSNs). However, the problem of maximizing the network lifetime via sink scheduling remains quite a challenge since routing issues are tightly coupled. Previous approaches on this topic either suffer from poor performance due to a lack of joint considerations, or are based on relaxed constraints. Therefore, in this paper, we aim to fill in the research blanks. First, we develop a novel notation Placement Pattern (PP) to bound time-varying routes with the placement of sinks. This bounding technique transforms the problem from time domain into pattern domain, and thus, significantly decreases the problem complexity. Then, we formulate this optimization in a pattern-based way and create an efficient Column Generation (CG) based approach to solve it. Simulations not only demonstrate the efficiency of the proposed algorithm but also substantiate the importance of sink mobility for energy-constrained WSNs.     

Maximum loss budget criteria for subcarrier multiplex broadcast passive optical networks

Analytic criteria for the laser optical modulation index and avalanche photodiode gain which maximise the loss budget of subcarrier multiplexed, broadcast, passive optical networks are described for the first time. A theoretical loss budget approaching 40 dB is predicted for 16.5 dB carrier-to-noise ratio in 36 MHz bandwidth for each of 120 channels under optimum conditions with <1 pA/ square root (Hz) thermal noise III-V avalanche photodiode receivers, 0 dBm laser launch power and <0.1% laser nonlinearity.<>