A topology transparent link activation protocol for mobile CDMAradio networks

A topology transparent protocol for link activation in mobile CDMA networks is presented. The protocol resolves primary and secondary conflicts, and can easily be adapted to TDMA link activation, as well. The proposed protocol guarantees that each link will be successfully activated at least once in a frame without the need to adjust transmission schedules in mobile environments. Compared to other protocols with guaranteed delivery, the overhead due to the recomputation of transmission schedules is eliminated and, accordingly, transmissions need not be suspended for schedule reorganization. Furthermore, contrary to previously known protocols that adapt to mobility by schedule recomputation, the proposed solution is not subject to a potential catastrophic failure when the rate of topology changes exceeds the rate at which schedules can be readjusted. We prove the correctness and evaluate the efficiency of the new protocol by analytical methods     

Making transmission schedules immune to topology changes inmulti-hop packet radio networks

Transmissions scheduling is a key design problem in packet radio networks, relevant to TDMA and CDMA systems. A large number of topology-dependent scheduling algorithms are available, in which changes of topology inevitably require recomputation of transmission schedules. The need for constant adaptation of schedules to mobile topologies entails significant, sometime insurmountable, problems. These are the protocol overhead due to schedule recomputation, performance penalty due to suspension of transmissions during schedule reorganization, exchange of control message and new schedule broadcast. Furthermore, if topology changes faster than the rate at which new schedules can be recomputed and distributed, the network can suffer a catastrophic failure. The authors propose a robust scheduling protocol which is unique in providing a topology transparent solution to scheduled access in multi-hop mobile radio networks. The proposed solution adds the main advantages of random access protocols to scheduled access. Similarly to random access it is robust in the presence of mobile nodes. Unlike random access, however, it does not suffer from inherent instability, and performance deterioration due to packet collisions. Unlike current scheduled access protocols, the transmission schedules of the proposed solution are independent of topology changes, and channel access is inherently fair and traffic adaptive     

Topology-Independent Link Activation Scheduling Schemes for Mobile CDMA Ad Hoc Networks

In this paper, we study medium access control (MAC) protocols with quality-of-service (QoS) support, that is, topology-independent link activation transmission scheduling, for mobile code-division multiple-access (CDMA) ad hoc networks. QoS provisioning for each communication link is guaranteed without the need to adopt transmission schedules in mobile environments. An interference model, which captures the difference between transmission and interference ranges, is considered. Under this interference model, an approach to guaranteeing conflict-free transmission slots in each frame (QoS provisioning) for each communication link is proposed. Compared with the previously known method, superior performance is obtained. We then present a topology-independent link activation scheduling framework based on the theory of group-divisible (GD) designs. By the mathematical properties of GD designs, the proposed framework guarantees conflict-free transmission slots in each frame for each communication link, without the overhead due to the recomputation of transmission schedules when the network topology changes. With the proposed framework, we study and evaluate one series of GD design constructions. Based on the results derived, topology-independent link activation scheduling algorithms are then presented. The proposed schemes are designed for different objectives: maximizing the minimum system throughput and/or minimizing the schedule frame length. Numerical results show that the proposed algorithms outperform previously known schemes. The average performance of the proposed schemes is also derived.     

On Joint MAC and Network Coding in Wireless Ad Hoc Networks

This paper addresses network coding in wireless networks in conjunction with medium access control (MAC). It is known that coding over wired networks enables connections with rates that cannot be achieved by routing. However, the properties of wireless networks (e.g., omnidirectional transmissions, destructive interference, single transceiver per node, finite energy) modify the formulation of time-varying network coding in a way that reflects strong interactions with underlying MAC protocols and deviates from the classical approach used in wired network coding. To perform network coding over conflict-free transmission schedules, predetermined network realizations are separately activated by a time-division mechanism and the content of network flows is derived through network coding to optimize performance measures such as achievable throughput and energy costs. A systematic method is presented to construct linear wireless network codes and interactions with MAC schedules are discussed under wireless assumptions. Network coding is also extended to operate with arbitrary (random or scheduled access based) MAC protocols. Alternatively, conflict-free transmission schedules are jointly constructed with network codes by decomposing wireless networks into subtrees and employing graph coloring on simplified subtree graphs. Finally, network coding and plain routing are compared in terms of throughput, energy and delay performance under different MAC solutions.     

An adaptive transmission-scheduling protocol for mobile ad hoc networks

Transmission-scheduling protocols can support contention-free link-level broadcast transmissions and delay sensitive traffic in mobile, multiple-hop packet radio networks. Use of transmission-scheduling protocols, however, can be very inefficient in mobile environments due to the difficulty in adapting transmission schedules. The paper defines a new adaptive and distributed protocol that permits a terminal to adapt transmission assignments to changes in topology using information it collects from its local neighborhood only. Because global coordination among all the terminals is not required and changes to transmission assignments are distributed to nearby terminals only, the protocol can adapt quickly to changes in the network connectivity. The two key parameters that affect the ability of the protocol to adapt to changes in connectivity are the rate of connectivity changes and the number of terminals near the connectivity changes. Using simulation, we determine the ranges for these parameters for which our adaptive protocol can maintain collision-free schedules with an acceptable level of overhead. The stability of the protocol is also characterized by showing that the protocol can quickly return to a collision-free transmission schedule after a period of very rapid changes in connectivity. Our channel-access protocol does not require a contention-based random-access phase to adapt the transmission schedules, and thus its ability to adapt quickly does not deteriorate with an increase in the traffic load.     

Topology Control for Delay Sensitive Applications in Wireless Sensor Networks

Wakeup scheduling in wireless sensor networks is known as the most effective way to conserve the limited amount of available energy for each sensor node. Such schedules are applicable to protocols of different network layers and often result in higher latency. Tolerance to latency varies greatly depending on the application so that it is low for a large class of delay sensitive applications. In this paper, we present a unified approach in the design of wakeup schedules in different network layers. A new distributed wakeup schedule is introduced in the context of topology control which aims to conserve more energy while not compromising on the delay performance of the system. The proposed protocol addresses the problem of increasing the network longevity for a given upper bound on the average end-to-end delay. In this scheme neither localization nor synchronization is required and only local information about the network topology is used. In addition to its simplicity of implementation, its energy overhead is negligible and it implicitly determines the routing paths. Our simulation results show that the performance of this protocol is close to the optimal schedule and significantly higher than SPAN, an existing topology control mechanism.     

Minimum latency joint scheduling and routing in wireless sensor networks

Wireless sensor networks are expected to be used in a wide range of applications from environment monitoring to event detection. The key challenge is to provide energy efficient communication; however, latency remains an important concern for many applications that require fast response. In this paper, we address the important problem of minimizing average communication latency for the active flows while providing energy-efficiency in wireless sensor networks. As the flows in some wireless sensor network can be long-lived and predictable, it is possible to design schedules for sensor nodes so that nodes can wake up only when it is necessary and asleep during other times. Clearly, the routing layer decision is closely coupled to the wakeup/sleep schedule of the sensor nodes. We formulate a joint scheduling and routing problem with the objective of finding the schedules and routes for current active flows with minimum average latency. By constructing a novel delay graph, the problem can be solved optimally by employing the M node-disjoint paths algorithm under FDMA channel model. We further present extensions of the algorithm to handle dynamic traffic changes and topology changes in wireless sensor networks.     

Achieving timely message delivery quality-of-service in fixed and variable connectivity distributed routing networks

Variable connectivity distributed routing networks (VCDRNs) are networks designed with the goal of reliably delivering message traffic even when network connectivity (both routing node to routing node and subscriber to routing node) is continuously and unpredictably changing. A general-purpose point-to-point VCDRN which provides optimum (fewest hop) connectivity in a fixed network and adapts as network topology changes so as to automatically reroute traffic is presented. The routing algorithm includes the multimedia, multidata rate, multierror rate case. It is shown how to design the network to offer a quality-of-service (QoS) in terms of a numerical probability of successful message delivery in a specified time or to adjust the network to provide a users desired QoS on single and multihop paths. This is an important feature to users who want rapid message delivery, even as network topology changes. The case of multiple message priorities is also included. Routing knowledge is distributed by adding path and error rate information to packets as they traverse the network, without adversely impacting QoS. This methodology applies to all routing protocols that employ selective reject retransmission error control. The methodology also presents a means for comparing the performance of candidate protocols in terms of parameters meaningful to the user. While the methods presented herein are applicable to any network they are of particular value to the wireless network with limited bandwidth, high error rates, and variable connectivity, where the user wants message traffic to be delivered as fast as possible in that environment with some prior assurance as to the speed and certainty of delivery.     

TDMA scheduling design of multihop packet radio networks based onlatin squares

Many transmission scheduling algorithms have been proposed to maximize spatial reuse and minimize the time division multiple access (TDMA) frame length in multihop packet radio networks. Almost all existing algorithms assume exact network topology information and require recomputations when the network topology changes. In addition, existing work focuses on single channel TDMA systems. In this paper, we propose a multichannel topology-transparent algorithm based on latin squares. The proposed algorithm has the flexibility to allow the growth of the network, i.e., the network can add more mobile nodes without recomputation of transmission schedules for existing nodes. At the same time, a minimum throughput is guaranteed. We analyze the efficiency of this algorithm and examine the topology-transparent characteristics and the sensitivity on design parameters by analytical and simulation techniques     

Optimal Block Design for Asynchronous Wake-Up Schedules and Its Applications in Multihop Wireless Networks

In this paper, we consider the problem of designing optimal asynchronous wake-up schedules to facilitate distributed power management and neighbor discovery in multihop wireless networks. We first formulate it as a block design problem and derive the fundamental trade-offs between wake-up latency and the average duty cycle of a node. After the theoretical foundation is laid, we then devise a neighbor discovery and schedule bookkeeping protocol that can operate on the optimal wake-up schedule derived. To demonstrate the usefulness of asynchronous wake-up, we investigate the efficiency of neighbor discovery and the application of on-demand power management, which overlays a desirable communication schedule over the wake-up schedule mandated by the asynchronous wake-up mechanism. Simulation studies demonstrate that the proposed asynchronous wake-up protocol has short discovery time which scales with the density of the network; it can accommodate various traffic characteristics and loads to achieve an energy savings that can be as high as 70 percent, while the packet delivery ratio is comparable to that without power management.     

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.     

Energy-efficient packet transmission over a wireless link

The paper considers the problem of minimizing the energy used to transmit packets over a wireless link via lazy schedules that judiciously vary packet transmission times. The problem is motivated by the following observation. With many channel coding schemes, the energy required to transmit a packet can be significantly reduced by lowering transmission power and code rate and therefore transmitting the packet over a longer period of time. However, information is often time-critical or delay-sensitive and transmission times cannot be made arbitrarily long. We therefore consider packet transmission schedules that minimize energy subject to a deadline or a delay constraint. Specifically, we obtain an optimal offline schedule for a node operating under a deadline constraint. An inspection of the form of this schedule naturally leads us to an online schedule which is shown, through simulations, to perform closely to the optimal offline schedule. Taking the deadline to infinity, we provide an exact probabilistic analysis of our offline scheduling algorithm. The results of this analysis enable us to devise a lazy online algorithm that varies transmission times according to backlog. We show that this lazy schedule is significantly more energy-efficient compared to a deterministic (fixed transmission time) schedule that guarantees queue stability for the same range of arrival rates.     

TDMA scheduling algorithms for wireless sensor networks

Algorithms for scheduling TDMA transmissions in multi-hop networks usually determine the smallest length conflict-free assignment of slots in which each link or node is activated at least once. This is based on the assumption that there are many independent point-to-point flows in the network. In sensor networks however often data are transferred from the sensor nodes to a few central data collectors. The scheduling problem is therefore to determine the smallest length conflict-free assignment of slots during which the packets generated at each node reach their destination. The conflicting node transmissions are determined based on an interference graph, which may be different from connectivity graph due to the broadcast nature of wireless transmissions. We show that this problem is NP-complete. We first propose two centralized heuristic algorithms: one based on direct scheduling of the nodes or node-based scheduling, which is adapted from classical multi-hop scheduling algorithms for general ad hoc networks, and the other based on scheduling the levels in the routing tree before scheduling the nodes or level-based scheduling, which is a novel scheduling algorithm for many-to-one communication in sensor networks. The performance of these algorithms depends on the distribution of the nodes across the levels. We then propose a distributed algorithm based on the distributed coloring of the nodes, that increases the delay by a factor of 10–70 over centralized algorithms for 1000 nodes. We also obtain upper bound for these schedules as a function of the total number of packets generated in the network.     

New dynamic SPT algorithm based on a ball-and-string model

A key functionality in today's widely used interior gateway routing protocols such as OSPF and IS-IS involves the computation of a shortest path tree (SPT). In many existing commercial routers, the computation of an SPT is done from scratch following changes in the link states of the network. As there may coexist multiple SPTs in a network with a set of given link states, such recomputation of an entire SPT not only is inefficient but also causes frequent unnecessary changes in the topology of an existing SPT and creates routing instability.. This paper presents a new dynamic SPT algorithm that makes use of the structure of the previously computed SPT. Our algorithm is derived by recasting the SPT problem into an optimization problem in a dual linear programming framework, which can also be interpreted using a ball-and-string model. In this model, the increase (or decrease) of an edge weight in the tree corresponds to the lengthening (or shortening) of a string. By stretching the strings until each node is attached to a tight string, the resulting topology of the model defines an (or multiple) SPT(s). By emulating the dynamics of the ball-and-string model, we can derive an efficient algorithm that propagates changes in distances to all affected nodes in a natural order and in a most economical way. Compared with existing results, our algorithm has the best-known performance in terms of computational complexity as well as minimum changes made to the topology of an SPT. Rigorous proofs for correctness of our algorithm and simulation results illustrating its complexity are also presented     

Delay Aware Link Scheduling for Multi-Hop TDMA Wireless Networks

Time division multiple access (TDMA) based medium access control (MAC) protocols can provide QoS with guaranteed access to the wireless channel. However, in multi-hop wireless networks, these protocols may introduce scheduling delay if, on the same path, an outbound link on a router is scheduled to transmit before an inbound link on that router. The total scheduling delay can be quite large since it accumulates at every hop on a path. This paper presents a method that finds conflict-free TDMA schedules with minimum scheduling delay. We show that the scheduling delay can be interpreted as a cost, in terms of transmission order of the links, collected over a cycle in the conflict graph. We use this observation to formulate an optimization, which finds a transmission order with the min-max delay across a set of multiple paths. The min-max delay optimization is NP-complete since the transmission order of links is a vector of binary integer variables. We devise an algorithm that finds the transmission order with the minimum delay on overlay tree topologies and use it with a modified Bellman-Ford algorithm, to find minimum delay schedules in polynomial time. The simulation results in 802.16 mesh networks confirm that the proposed algorithm can find effective min-max delay schedules.     

Distributed scheduling of CDMA networks with minimal information

An algorithm which produces conflict-free communication schedules in mobility multihop radio networks is presented. These schedules are produced in a completely distributed manner. The algorithm is based on a globally known permutation on the nodes of the network. As a result the only knowledge needed on the part of individual nodes is the number of nodes in the network. This permutation guarantees that conflict-free schedules can be produced in a distributed manner. Two extensions to the basic permutation are discussed. The first enables neighboring nodes to enhance their communication schedules in a fast, robust, distributed manner. The second extension allows the algorithm to operate in the presence of secondary conflicts     

Genetic Algorithms With Immigrants and Memory Schemes for Dynamic Shortest Path Routing Problems in Mobile Ad Hoc Networks

In recent years, the static shortest path (SP) problem has been well addressed using intelligent optimization techniques, e.g., artificial neural networks, genetic algorithms (GAs), particle swarm optimization, etc. However, with the advancement in wireless communications, more and more mobile wireless networks appear, e.g., mobile networks [mobile ad hoc networks (MANETs)], wireless sensor networks, etc. One of the most important characteristics in mobile wireless networks is the topology dynamics, i.e., the network topology changes over time due to energy conservation or node mobility. Therefore, the SP routing problem in MANETs turns out to be a dynamic optimization problem. In this paper, we propose to use GAs with immigrants and memory schemes to solve the dynamic SP routing problem in MANETs. We consider MANETs as target systems because they represent new-generation wireless networks. The experimental results show that these immigrants and memory-based GAs can quickly adapt to environmental changes (i.e., the network topology changes) and produce high-quality solutions after each change.      

An Optimal Emperor Penguin Optimization Based Enhanced Flower Pollination Algorithm in WSN for Fault Diagnosis and Prolong Network Lifespan

With unmanned aerial vehicles (UAVs) being widely used, the rapidly changing network topology and vertical height changes of UAVs have been bottlenecks for many wild applications, such as battlefield communication. These problems lead to the frequent communication interruptions and poor stability of 3D UAV networks. Facing these challenges, we propose deep neural network routing (DNNR) that is characterized by a dynamic 3D two-subspace division (i.e., vertical-axis cylinder and horizontal-plane divisions) and deep neural network (DNN) forwarding. With the trajectories of base station and nodes changing, vertical-axis cylinder and horizontal-plane divisions also change dynamically according to the broadcast information. Different from multi subspace division, this kind of two subspace divisions could reduce the complexity of routing discovery and make full use of the dynamic adaptability of 3D space division against the rapidly changing network topology. Due to the DNN flexibility, DNN forwarding is a promising scheme to improve the probability of recognizing the available links and select the rational next-hop node. We implement four compared protocols and DNNR in NS3 network simulator and test them for various application scenarios, when changing base station speed, node speed, horizontal plane size, and vertical height. Comparing with four protocols, DNNR achieves better performance in terms of packet delivery rate and energy-saving performance. These indicate that 3D space division is a concise and feasible scheme in flight ad hoc networks which may be extended to other fields. Besides, owing to the flexibility and prevalent availability, machine learning routing protocols are becoming a popular technology.

     

A routing protocol for mobile ad‐hoc networks using the profit optimization model

Recently, wireless networks have become one of the major development trends in computer network technology. Because there is no more need of the wired transmission medium, applications have thus diversified. One such growing field of wireless networks is the mobile ad‐hoc network (MANET). A MANET consists of mobile hosts (such as portable laptops, vehicles, etc.), and no fixed infrastructure is required. MANETs provide ease of self‐configuration and can extend coverage at a low cost. Numerous applications have therefore been proposed under this network environment for daily life use. Because MANETs nodes are capable of moving, MANET network topology changes frequently. Thus, the traditional routing protocols fail to fit such an environment. In this paper, we propose an efficient routing protocol for MANETs, which integrates the mathematical model of profit optimization (the Kelly formula) from the field of economics to cope with the routing problem caused by node mobility. Some numerical simulations have been conducted to evaluate the performance of the proposed method using the network simulator NS‐2. The results show that our proposed method outperforms conventional routing protocols in packet delivery ratio comparisons; and the average end‐to‐end delays are within a tolerable range. Copyright © 2013 John Wiley & Sons, Ltd.     

A distributed link scheduling algorithm for CDMA packet radio networks

A distributed algorithm for the conflict-free channel allocation in CDMA (code division multiple access) networks is presented. Dynamic adjustment to topological changes is also considered. Though the schedules produced by our algorithm are not optimal with respect to link schedule length, the algorithm is simple and practical. The link schedule length minimization problem is NP-complete. Here the length of a link schedule is the number of time slots it uses. The algorithm guarantees a bound 2 — 1 time slots on the TDMA cycle length, where is the maximum degree of a station (i.e., maximum number of stations that a station can reach by radio links) in the network. The message complexity of a station isO().