Opportunistic Routing for Multi-flow Video Dissemination over Flying Ad-Hoc Networks

A reliable and robust routing service for Flying Ad-Hoc Networks (FANETs) must be able to adapt to topology changes. User experience on watching live video sequences must also be satisfactory even in scenarios with buffer overflow and high packet loss ratio. In this paper, we introduce a Cross-layer Link quality and Geographical-aware beaconless opportunistic routing protocol (XLinGO). It enhances the transmission of simultaneous multiple video flows over FANETs by creating and keeping reliable persistent multi-hop routes. XLinGO considers a set of cross-layer and human-related information for routing decisions, as performance metrics and Quality of Experience (QoE). Performance evaluation shows that XLinGO achieves multimedia dissemination with QoE support and robustness in a multi-hop, multi-flow, and mobile network environments.

Real-World Evaluation of Sensor Context-aware Adaptive Duty-cycled Opportunistic Routing

Energy is of primary concern in wireless sensor networks (WSNs). Low power transmission makes the wireless links unreliable, which leads to frequent topology changes. Resulting packet retransmissions aggravate the energy consumption. Beaconless routing approaches, such as opportunistic routing (OR) choose packet forwarders after data transmissions, and are promising to support dynamic features of WSNs. This paper proposes SCAD - Sensor Context-aware Adaptive Duty-cycled beaconless OR for WSNs. SCAD is a cross-layer routing solution and it brings the concept of beaconless OR into WSNs. SCAD selects packet forwarders based on multiple types of network contexts. To achieve a balance between performance and energy efficiency, SCAD adapts duty-cycles of sensors based on real-time traffic loads and energy drain rates. We implemented SCAD in TinyOS running on top of Tmote Sky sensor motes. Real-world evaluations show that SCAD outperforms other protocols in terms of both throughput and network lifetime.

SCAD: Sensor Context-aware Adaptive Duty-cycled Beaconless Opportunistic Routing for WSNs

Low quality of wireless links leads to perpetual transmission failures in lossy wireless environments. To mitigate this problem, opportunistic routing (OR) has been proposed to improve the throughput of wireless multihop ad-hoc networks by taking advantage of the broadcast nature of wireless channels. However, OR can not be directly applied to wireless sensor networks (WSNs) due to some intrinsic design features of WSNs. In this paper, we present a new OR solution for WSNs with suitable adaptations to their characteristics. Our protocol, called SCAD-Sensor Context-aware Adaptive Duty-cycled beaconless opportunistic routing protocol is a cross-layer routing approach and it selects packet forwarders based on multiple sensor context information. To reach a balance between performance and energy-efficiency, SCAD adapts the duty-cycles of sensors according to real-time traffic loads and energy drain rates. We compare SCAD against other protocols through extensive simulations. Evaluation results show that SCAD outperforms other protocols in highly dynamic scenarios.

A low power routing algorithm for localization in IEEE 802.15.4 networks

Many context-aware applications rely on the knowledge of the position of the user and the surrounding objects to provide advanced, personalized and real-time services. In wide-area deployments, a routing protocol is needed to collect the location information from distant nodes. In this paper, we propose a new source-initiated (on demand) routing protocol for location-aware applications in IEEE 802.15.4 wireless sensor networks. This protocol uses a low power MAC layer to maximize the lifetime of the network while maintaining the communication delay to a low value. Its performance is assessed through experimental tests that show a good trade-off between power consumption and time delay in the localization of a mobile device.

Analysis of ad hoc routing protocols for emergency and rescue scenarios.

A mobile ad hoc network MANET is a collection of wireless mobile nodes that can dynamically configure a network without a fixed infrastructure or centralized administration. This makes it ideal for emergency and rescue scenarios where information sharing is essential and should occur as soon as possible. This article discusses which of the routing strategies for mobile ad hoc networks: proactive, reactive and hierarchical, have a better performance in such scenarios. Using a real urban area being set for the emergency and rescue scenario, we calculate the density of nodes and the mobility model needed for validation. The NS2 simulator has been used in our study. We also show that the hierarchical routing strategies are beffer suited for this type of scenarios.

Behavior of Ad Hoc routing protocols, analyzed for emergency and rescue scenarios, on a real urban area

A mobile Ad Hoc network (MANET) is a collection of wireless mobile nodes that can dynamically configure a network without a fixed infrastructure or central administration. This makes it ideal for emergency and rescue scenarios, where sharing information is essential and should occur as soon as possible. This article discusses which of the routing strategies for mobile MANETs: proactive, reactive or hierarchical, has a better performance in such scenarios. By selecting a real urban area for the emergency and rescue scenario, we calculated the density of nodes and the mobility model needed for the validation study of AODV, DSDV and CBRP in the routing model. The NS2 simulator has been used for our study. We also show that the hierarchical routing strategies are better suited for this type of scenarios.

The Balanced Cross-Layer Design Routing Algorithm in Wireless Sensor Networks Using Fuzzy Logic

Recently, the cross-layer design for the wireless sensor network communication protocol has become more and more important and popular. Considering the disadvantages of the traditional cross-layer routing algorithms, in this paper we propose a new fuzzy logic-based routing algorithm, named the Balanced Cross-layer Fuzzy Logic (BCFL) routing algorithm. In BCFL, we use the cross-layer parameters’ dispersion as the fuzzy logic inference system inputs. Moreover, we give each cross-layer parameter a dynamic weight according the value of the dispersion. For getting a balanced solution, the parameter whose dispersion is large will have small weight, and vice versa. In order to compare it with the traditional cross-layer routing algorithms, BCFL is evaluated through extensive simulations. The simulation results show that the new routing algorithm can handle the multiple constraints without increasing the complexity of the algorithm and can achieve the most balanced performance on selecting the next hop relay node. Moreover, the Balanced Cross-layer Fuzzy Logic routing algorithm can adapt to the dynamic changing of the network conditions and topology effectively.

Performance analysis of multi-radio AODV in hybrid wireless mesh networks

Wireless Mesh Networks (WMNs), based on commodity hardware, present a promising technology for a wide range of applications due to their self-configuring and self-healing capabilities, as well as their low equipment and deployment costs. One of the key challenges that WMN technology faces is the limited capacity and scalability due to co-channel interference, which is typical for multi-hop wireless networks. A simple and relatively low-cost approach to address this problem is the use of multiple wireless network interfaces (radios) per node. Operating the radios on distinct orthogonal channels permits effective use of the frequency spectrum, thereby, reducing interference and contention. In this paper, we evaluate the performance of the multi-radio Ad-hoc On-demand Distance Vector (AODV) routing protocol with a specific focus on hybrid WMNs. Our simulation results show that under high mobility and traffic load conditions, multi-radio AODV offers superior performance as compared to its single-radio counterpart. We believe that multi-radio AODV is a promising candidate for WMNs, which need to service a large number of mobile clients with low latency and high bandwidth requirements.

A hybrid genetic algorithm for the multi-depot vehicle routing problem

The distribution of finished products from depots to customers is a practical and challenging problem in logistics management. Better routing and scheduling decisions can result in higher level of customer satisfaction because more customers can be served in a shorter time. The distribution problem is generally formulated as the vehicle routing problem (VRP). Nevertheless, there is a rigid assumption that there is only one depot. In cases, for instance, where a logistics company has more than one depot, the VRP is not suitable. To resolve this limitation, this paper focuses on the VRP with multiple depots, or multi-depot VRP (MDVRP). The MDVRP is NP-hard, which means that an efficient algorithm for solving the problem to optimality is unavailable. To deal with the problem efficiently, two hybrid genetic algorithms (HGAs) are developed in this paper. The major difference between the HGAs is that the initial solutions are generated randomly in HGA1. The Clarke and Wright saving method and the nearest neighbor heuristic are incorporated into HGA2 for the initialization procedure. A computational study is carried out to compare the algorithms with different problem sizes. It is proved that the performance of HGA2 is superior to that of HGA1 in terms of the total delivery time.

Distributed routing algorithms for interconnected FDDI LANS

The Fibre Distributed Data Interface (FDDI) represents the new generation of local area networks (LANs). These high speed LANs are capable of supporting up to 500 users over a 100 km distance. User traffic is expected to be as diverse as file transfers, packet voice and video. As the proliferation of FDDI LANs continues, the need to interconnect these LANs arises. FDDI LAN interconnection can be achieved in a variety of different ways. Some of the most commonly used today are public data networks, dial up lines and private circuits. For applications that can potentially generate large quantities of traffic, such as an FDDI LAN, it is cost effective to use a private circuit leased from the public carrier. In order to send traffic from one LAN to another across the leased line, a routing algorithm is required. Much research has been done on the Bellman-Ford algorithm and many implementations of it exist in computer networks. However, due to its instability and problems with routing table loops it is an unsatisfactory algorithm for interconnected FDDI LANs. A new algorithm, termed ISIS which is being standardized by the ISO provides a far better solution. ISIS will be implemented in many manufacturers routing devices. In order to make the work as practical as possible, this algorithm will be used as the basis for all the new algorithms presented. The ISIS algorithm can be improved by exploiting information that is dropped by that algorithm during the calculation process. A new algorithm, called Down Stream Path Splits (DSPS), uses this information and requires only minor modification to some of the ISIS routing procedures. DSPS provides a higher network performance, with very little additional processing and storage requirements. A second algorithm, also based on the ISIS algorithm, generates a massive increase in network performance. This is achieved by selecting alternative paths through the network in times of heavy congestion. This algorithm may select the alternative path at either the originating node, or any node along the path. It requires more processing and memory storage than DSPS, but generates a higher network power. The final algorithm combines the DSPS algorithm with the alternative path algorithm. This is the most flexible and powerful of the algorithms developed. However, it is somewhat complex and requires a fairly large storage area at each node. The performance of the new routing algorithms is tested in a comprehensive model of interconnected LANs. This model incorporates the transport through physical layers and generates random topologies for routing algorithm performance comparisons. Using this model it is possible to determine which algorithm provides the best performance without introducing significant complexity and storage requirements.

Improving “last mile” delivery performance to retailers in hub and spoke distribution systems

Purpose – The purpose of this paper is to investigate the “last mile” delivery link between a hub and spoke distribution system and its customers. The proportion of retail, as opposed to non-retail (trade) customers using this type of distribution system has been growing in the UK. The paper shows the applicability of simulation to demonstrate changes in overall delivery policy to these customers. Design/methodology/approach – A case-based research method was chosen with the aim to provide an exemplar of practice and test the proposition that simulation can be used as a tool to investigate changes in delivery policy. Findings – The results indicate the potential improvement in delivery performance, specifically in meeting timed delivery performance, that could be made by having separate retail and non-retail delivery runs from the spoke terminal to the customer. Research limitations/implications – The simulation study does not attempt to generate a vehicle routing schedule but demonstrates the effects of a change on delivery performance when comparing delivery policies. Practical implications – Scheduling and spreadsheet software are widely used and provide useful assistance in the design of delivery runs and the allocation of staff to those delivery runs. This paper demonstrates to managers the usefulness of investigating the efficacy of current design rules and presents simulation as a suitable tool for this analysis. Originality/value – A simulation model is used in a novel application to test a change in delivery policy in response to a changing delivery profile of increased retail deliveries.

Ad hoc network state aware routing protocol

The environment of a mobile ad hoc network may vary greatly depending on nodes' mobility, traffic load and resource conditions. In this paper we categorize the environment of an ad hoc network into three main states: an ideal state, wherein the network is relatively stable with sufficient resources; a congested state, wherein some nodes, regions or the network is experiencing congestion; and an energy critical state, wherein the energy capacity of nodes in the network is critically low. Each of these states requires unique routing schemes, but existing ad hoc routing protocols are only effective in one of these states. This implies that when the network enters into any other states, these protocols run into a sub optimal mode, degrading the performance of the network. We propose an Ad hoc Network State Aware Routing Protocol (ANSAR) which conditionally switches between earliest arrival scheme and a joint Load-Energy aware scheme depending on the current state of the network. Comparing to existing schemes, it yields higher efficiency and reliability as shown in our simulation results. © 2007 IEEE.

Host and network optimizations for performance enhancement and energy efficiency in data center networks

Modern data centers host hundreds of thousands of servers to achieve economies of scale. Such a huge number of servers create challenges for the data center network (DCN) to provide proportionally large bandwidth. In addition, the deployment of virtual machines (VMs) in data centers raises the requirements for efficient resource allocation and find-grained resource sharing. Further, the large number of servers and switches in the data center consume significant amounts of energy. Even though servers become more energy efficient with various energy saving techniques, DCN still accounts for 20% to 50% of the energy consumed by the entire data center. The objective of this dissertation is to enhance DCN performance as well as its energy efficiency by conducting optimizations on both host and network sides. First, as the DCN demands huge bisection bandwidth to interconnect all the servers, we propose a parallel packet switch (PPS) architecture that directly processes variable length packets without segmentation-and-reassembly (SAR). The proposed PPS achieves large bandwidth by combining switching capacities of multiple fabrics, and it further improves the switch throughput by avoiding padding bits in SAR. Second, since certain resource demands of the VM are bursty and demonstrate stochastic nature, to satisfy both deterministic and stochastic demands in VM placement, we propose the Max-Min Multidimensional Stochastic Bin Packing (M3SBP) algorithm. M3SBP calculates an equivalent deterministic value for the stochastic demands, and maximizes the minimum resource utilization ratio of each server. Third, to provide necessary traffic isolation for VMs that share the same physical network adapter, we propose the Flow-level Bandwidth Provisioning (FBP) algorithm. By reducing the flow scheduling problem to multiple stages of packet queuing problems, FBP guarantees the provisioned bandwidth and delay performance for each flow. Finally, while DCNs are typically provisioned with full bisection bandwidth, DCN traffic demonstrates fluctuating patterns, we propose a joint host-network optimization scheme to enhance the energy efficiency of DCNs during off-peak traffic hours. The proposed scheme utilizes a unified representation method that converts the VM placement problem to a routing problem and employs depth-first and best-fit search to find efficient paths for flows.

Cooperative routing for collision minimization in wireless sensor networks

Cooperative communication has gained much interest due to its ability to exploit the broadcasting nature of the wireless medium to mitigate multipath fading. There has been considerable amount of research on how cooperative transmission can improve the performance of the network by focusing on the physical layer issues. During the past few years, the researchers have started to take into consideration cooperative transmission in routing and there has been a growing interest in designing and evaluating cooperative routing protocols. Most of the existing cooperative routing algorithms are designed to reduce the energy consumption; however, packet collision minimization using cooperative routing has not been addressed yet. This dissertation presents an optimization framework to minimize collision probability using cooperative routing in wireless sensor networks. More specifically, we develop a mathematical model and formulate the problem as a large-scale Mixed Integer Non-Linear Programming problem. We also propose a solution based on the branch and bound algorithm augmented with reducing the search space (branch and bound space reduction). The proposed strategy builds up the optimal routes from each source to the sink node by providing the best set of hops in each route, the best set of relays, and the optimal power allocation for the cooperative transmission links. To reduce the computational complexity, we propose two near optimal cooperative routing algorithms. In the first near optimal algorithm, we solve the problem by decoupling the optimal power allocation scheme from optimal route selection. Therefore, the problem is formulated by an Integer Non-Linear Programming, which is solved using a branch and bound space reduced method. In the second near optimal algorithm, the cooperative routing problem is solved by decoupling the transmission power and the relay node se- lection from the route selection. After solving the routing problems, the power allocation is applied in the selected route. Simulation results show the algorithms can significantly reduce the collision probability compared with existing cooperative routing schemes.

A distributed, compact routing protocol for the Internet

The Internet has grown in size at rapid rates since BGP records began, and continues to do so. This has raised concerns about the scalability of the current BGP routing system, as the routing state at each router in a shortest-path routing protocol will grow at a supra-linearly rate as the network grows. The concerns are that the memory capacity of routers will not be able to keep up with demands, and that the growth of the Internet will become ever more cramped as more and more of the world seeks the benefits of being connected. Compact routing schemes, where the routing state grows only sub-linearly relative to the growth of the network, could solve this problem and ensure that router memory would not be a bottleneck to Internet growth. These schemes trade away shortest-path routing for scalable memory state, by allowing some paths to have a certain amount of bounded “stretch”. The most promising such scheme is Cowen Routing, which can provide scalable, compact routing state for Internet routing, while still providing shortest-path routing to nearly all other nodes, with only slightly stretched paths to a very small subset of the network. Currently, there is no fully distributed form of Cowen Routing that would be practical for the Internet. This dissertation describes a fully distributed and compact protocol for Cowen routing, using the k-core graph decomposition. Previous compact routing work showed the k-core graph decomposition is useful for Cowen Routing on the Internet, but no distributed form existed. This dissertation gives a distributed k-core algorithm optimised to be efficient on dynamic graphs, along with with proofs of its correctness. The performance and efficiency of this distributed k-core algorithm is evaluated on large, Internet AS graphs, with excellent results. This dissertation then goes on to describe a fully distributed and compact Cowen Routing protocol. This protocol being comprised of a landmark selection process for Cowen Routing using the k-core algorithm, with mechanisms to ensure compact state at all times, including at bootstrap; a local cluster routing process, with mechanisms for policy application and control of cluster sizes, ensuring again that state can remain compact at all times; and a landmark routing process is described with a prioritisation mechanism for announcements that ensures compact state at all times.