Hop Constrained Energy-Efficient Broadcasting: Insights from Massively Dense Ad Hoc Networks

We consider source-initiated broadcast session traffic in an ad hoc wireless network operating under a hard constraint on the end-to-end delay between the source and any node in the network. We measure the delay to a given node in the number of hops data travels from the source to that node, and our objective in this paper is to construct an energy-efficient broadcast tree that has a maximum depth Delta, where Delta; represents the end-to-end hop constraint in the network. We characterize the optimal solution to a closely related problem in massively dense networks using a dynamic programming formulation. We prove that the optimal solution can be obtained by an algorithm of polynomial time complexity O(Delta²). The solution to the dynamic program indicates that there is a single optimal policy applicable to all massively dense networks. Elaborating on the insights provided by the structure of the problem in massively dense networks, we design an algorithm for finding a solution to the hop constrained minimum power broadcasting problem in general networks. By extensive simulations, we demonstrate that our proposed optimization-based algorithm generates broadcast trees within 20% of optimality for general dense networks.     

A Tutorial on Cross-Layer Optimization in Wireless Networks

This tutorial paper overviews recent developments in optimization-based approaches for resource allocation problems in wireless systems. We begin by overviewing important results in the area of opportunistic (channel-aware) scheduling for cellular (single-hop) networks, where easily implementable myopic policies are shown to optimize system performance. We then describe key lessons learned and the main obstacles in extending the work to general resource allocation problems for multihop wireless networks. Towards this end, we show that a clean-slate optimization-based approach to the multihop resource allocation problem naturally results in a “loosely coupled” cross-layer solution. That is, the algorithms obtained map to different layers [transport, network, and medium access control/physical (MAC/PHY)] of the protocol stack, and are coupled through a limited amount of information being passed back and forth. It turns out that the optimal scheduling component at the MAC layer is very complex, and thus needs simpler (potentially imperfect) distributed solutions. We demonstrate how to use imperfect scheduling in the cross-layer framework and describe recently developed distributed algorithms along these lines. We conclude by describing a set of open research problems.     

Tabu search based algorithms for bandwidth-delay-constrained least-cost multicast routing

The advent of various real-time multimedia applications in high-speed networks creates a need for quality of service (QoS) based multicast routing. The Steiner tree problem, is a well-known NP-complete problem, provides the mathematical structure behind multicast communications. Two important QoS constraints are the bandwidth constraint and the end-to-end delay constraint. In this paper, we propose various algorithms to solve the bandwidth-delay-constrained least-cost multicast routing problem based on Tabu Search (TS), addressing issues of the selected initial solution and move type as two major building blocks in short-term memory version of Tabu Search and longer-term memory with associated intensification and diversification strategies as advanced Tabu Search techniques. We evaluate the performance and efficiency of the proposed TS-based algorithms in comparison with other existing TS-based algorithms and heuristics on a variety of random generated networks with regard to total tree cost. Finally we identify the most efficient algorithm uncovered by our testing.     

Efficient Scheduling Algorithms for Real-Time Service on WDM Optical Networks

One of the important issues in the design of future generation high-speed networks is the provision of real-time services to different types of traffic with various time constraints. In this paper we study the problem of providing real-time service to hard and soft real-time messages in Wavelength-Division-Multiplexing (WDM) optical networks. We propose a set of scheduling algorithms which prioritize and manage message transmissions in single-hop WDM passive star networks based on specific message time constraints. In particular, we develop time-based priority schemes for scheduling message transmissions in order to increase the real-time performance of a WDM network topology. We formulated an analytical model and conducted extensive discrete-event simulations to evaluate the performance of the proposed algorithms. We compared their performances with that of the state-of-the-art WDM scheduling algorithms which typically do not consider the time constraint of the transmitted messages. This study suggests that when scheduling real-time messages in WDM networks, one has to consider not only the problem of resources allocation in the network but also the problem of sequencing messages based on their time constraints.     

A Tabu search based routing algorithm for wireless sensor networks

In this paper, a Tabu search based routing algorithm is proposed to efficiently determine an optimal path from a source to a destination in wireless sensor networks (WSNs). There have been several methods proposed for routing algorithms in wireless sensor networks. In this paper, the Tabu search method is exploited for routing in WSNs from a new point of view. In this algorithm (TSRA), a new move and neighborhood search method is designed to integrate energy consumption and hop counts into routing choice. The proposed algorithm is compared with some of the ant colony optimization based routing algorithms, such as traditional ant colony algorithm, ant colony optimization-based location-aware routing for wireless sensor networks, and energy and path aware ant colony algorithm for routing of wireless sensor networks, in term of routing cost, energy consumption and network lifetime. Simulation results, for various random generated networks, demonstrate that the TSRA, obtains more balanced transmission among the node, reduces the energy consumption and cost of the routing, and extends the network lifetime.     

Minimum-energy multicast in wireless ad hoc networks with adaptive antennas: MILP formulations and heuristic algorithms

In this paper, we consider wireless ad hoc networks that use adaptive antennas and have limited energy resources. To explore the advantages of power saving offered by the use of adaptive antennas, we consider the case of source initiated multicast traffic. We present a constraint formulation for the MEM (Minimum-Energy Multicast) problem in terms of MILP (Mixed Integer Linear Programming) for wireless ad hoc networks. An optimal solution to the MEM problem using our MILP model can always be obtained in a timely manner for moderately sized networks. In addition to the theoretical effort, we also present two polynomial-time heuristic algorithms called RB-MIDP and D-MIDP to handle larger networks for which the MILP model may not be computationally efficient. The experimental results show that our algorithms compare well with other proposals discussed in this paper.     

Simple Pre-Provisioning Scheme to Enable Fast Restoration

Supporting fast restoration for general mesh topologies with minimal network over-build is a technically challenging problem. Traditionally, ring-based SONET networks have offered close to 50 ms restoration at the cost of requiring 100% over-build. Recently, fast (local) reroute has gained momentum in the context of MPLS networks. Fast reroute, when combined with pre-provisioning of protection capacities and bypass tunnels, enables faster restoration times in mesh networks. Pre-provisioning has the additional advantage of greatly simplifying network routing and signaling. Thus, even for protected connections, online routing can now be oblivious to the offered protection, and may only involve single shortest path computations. In this paper, we are interested in the problem of reserving the least amount of the network capacity for protection, while guaranteeing fast (local) reroute-based restoration for all the supported connections. We show that the problem is NP-complete, and we present efficient approximation algorithms for the problem. The solution output by our algorithms is guaranteed to use at most twice the protection capacity, compared to any optimal solution. These guarantees are provided even when the protection is for multiple link failures. In addition, the total amount of protection capacity reserved by these algorithms is just a small fraction of the amount reserved by existing ring-based schemes (e.g., SONET), especially on dense networks. The presented algorithms are computationally efficient, and can even be implemented on the network elements. Our simulation, on some standard core networks, show that our algorithms work well in practice as well     

Relax online resource allocation algorithms for D2D communication

Maximizing the system sumrate by sharing the resource blocks among the cellular user equipments and the D2D (device to device) pairs while maintaining the quality of service is an important research question in a D2D communication underlaying cellular networks. The problem can be optimally solved in offline by using the weighted bipartite matching algorithm. However, in long‐term evolution and beyond (4G and 5G) systems, scheduling algorithms should be very efficient where the optimal algorithm is quite complex to implement. Hence, a low complexity algorithm that returns almost the optimal solution can be an alternative to this research problem. In this paper, we propose 2 less complex stable matching–based relax online algorithms those exhibit very close to the optimal solution. Our proposed algorithms deal with fixed number of cellular user equipments and a variable number of D2D pairs those arrive in the system online. Unlike online matching algorithms, we consider that an assignment can be revoked if it improves the objective function (total system sumrate). However, we want to minimize the number of revocation (ie, the number of changes in the assignments) as a large number of changes can be expensive for the networks too. We consider various offline algorithms proposed for the same research problem as relaxed online algorithms. Through extensive simulations, we find that our proposed algorithms outperform all of the algorithms in terms of the number of changes in assignment between 2 successive allocations while maintaining the total system sumrate very close to the optimal algorithm.     

An optimization framework for monitoring multi-channel multi-radio wireless mesh networks

This paper studies an optimal monitoring problem for behavior-based detection in multi-channel multi-radio wireless mesh networks. In behavior-based detection, nodes overhear communications in their neighborhood to determine if the behaviors of their neighbors are legitimate. The objective of this work is to maximize the number of nodes being monitored by judiciously choosing a set of monitoring nodes and also channels for the chosen monitoring nodes. This problem is NP-hard, growing exponentially with the number of monitoring nodes. We develop three approximation algorithms, each of which achieves at least a constant factor of the optimum. Furthermore, one of our algorithms achieves the best possible approximation ratio among all polynomial-time algorithms, unless P = NP. We conduct simulations in random networks and scale-free networks to evaluate the coverage and the execution time of the three algorithms.     

A Per-Flow Based Node Architecture for Integrated Services Packet Networks

As the Internet transforms from the traditional best-effort service network into QoS-capable multi-service network, it is essential to have new architectural design and appropriate traffic control algorithms in place. This paper presents a network node architecture and several traffic management mechanisms that are capable of achieving QoS provisioning for the guaranteed service (GS), the controlled-load (CL) service, and the best-effort (BE) service for future integrated services networks. A key feature of our architecture is that it resolves the out-of-sequence problem associated with the traditional design. We also propose two novel packet discarding mechanisms called selective pushout (SP) and selective pushout plus (SP+). Simulation results show that, once admitted into the network, our architecture and traffic management algorithms provide, under all conditions, hard performance guarantees to GS flows and consistent (or soft) performance guarantees to CL flows, respectively; minimal negative impact to in-profile GS, CL and BE traffic should there be any out-of-profile behavior from some CL flows.     

QoS-aware service composition and adaptation in autonomic communication

Advents in network technology and distributed system design have propelled network communication service beyond best effort data delivery. With the rising complexity of network infrastructures and the need for on-demand provisioning operations, a high degree of self-sufficiency and automation is required in the network service infrastructure. Guided by the autonomic communication principle, this paper first presents an autonomic service provisioning framework for establishing quality-of-service (QoS)-assured end-to-end communication paths across administratively independent domains. Through graph abstraction, we show that the domain composition and adaptation problem could be reduced to the classic k-multiconstrained optimal path (MCOP) problem. In analyzing existing k-MCOP solutions, we show their inefficiencies when applied to the service provisioning context and establish a number of new domain composition and adaptation algorithms. These new algorithms are designed for the self-configuration, self-optimization, and self-adaptation of end-to-end network communications and can provide hard QoS guarantees over domains with relative QoS differentiations. Through in-depth experimentations, we compare the performance of our algorithms with classic k-MCOP solutions and demonstrate the effectiveness of our approach.     

A scalable approach to the partition of QoS requirements in unicast and multicast

Supporting quality of service (QoS) in large-scale broadband networks poses major challenges, due to the intrinsic complexity of the corresponding resource allocation problems. An important problem in this context is how to partition QoS requirements along a selected topology (path for unicast and tree for multicast). As networks grow in size, the scalability of the solution becomes increasingly important. This calls for efficient algorithms, whose computational complexity is less dependent on the network size. In addition, recently proposed precomputation-based methods can be employed to facilitate scalability by significantly reducing the time needed for handling incoming requests. We present a novel solution technique to the QoS partition problem(s), based on a "divide-and-conquer" scheme. As opposed to previous solutions, our technique considerably reduces the computational complexity in terms of dependence on network size; moreover, it enables the development of precomputation schemes. Hence, our technique provides a scalable approach to the QoS partition problem, for both unicast and multicast. In addition, our algorithms readily generalize to support QoS routing in typical settings of large-scale networks.     

Multicast routing and bandwidth dimensioning in overlay networks

Multicast services can be provided either as a basic network service or as an application-layer service. Higher level multicast implementations often provide more sophisticated features and can provide multicast services at places where no network layer support is available. Overlay multicast networks offer an intermediate option, potentially combining the flexibility and advanced features of application layer multicast with the greater efficiency of network layer multicast. In this paper, we introduce the multicast routing problem specific to the overlay network environment and the related capacity assignment problem for overlay network planning. Our main contributions are the design of several routing algorithms that optimize the end-to-end delay and the interface bandwidth usage at the multicast service nodes within the overlay network. The interface bandwidth is typically a key resource for an overlay network provider, and needs to be carefully managed in order to maximize the number of users that can be served. Through simulations, we evaluate the performance of these algorithms under various traffic conditions and on various network topologies. The results show that our approach is cost-effective and robust under traffic variations.     

The peak-constrained optimization of stable linear-phase IIR PRQMF bank

In this paper, we propose a new approach for optimization based stable linear-phase infinite impulse response (IIR) perfect reconstruction quadrature mirror filter (PRQMF) bank design. To this end, the design problem is formulated using stop-band energy, stability, transition-band, pass-band and stop-band ripples requirements as constraints. Lagrange multiplier method is used for the solution of optimization-based design problem. The brief conclusion with design example that illustrates the proposed design method is presented.     

Enhanced IPACT: solving the over-granting problem in long-reach EPON

In this paper we address an issue referred to as “over-granting problem”, which is inherent in the existing dynamic bandwidth allocation algorithms for Ethernet-based Passive Optical Networks (EPON), in particular when deployed for multi-threaded scheme in long-reach scenario. In order to solve this problem we design a scheme for the algorithm of Interleaved Polling with Adapted Cycle Time (IPACT) with the limited service discipline. We evaluate the proposed scheme through simulations for single-thread and double-thread cases and demonstrate that, the network performance can be significantly improved by our solution in terms of average delay, jitter, and throughput.     

An Optimization-Based Approach for QoS Routing in High-Bandwidth Networks

In this paper, we propose an optimization-based approach for Quality of Service (QoS) routing in high-bandwidth networks. We view a network that employs QoS routing as an entity that distributively optimizes some global utility function. By solving the optimization problem, the network is driven to an efficient operating point. In earlier work, it has been shown that when the capacity of the network is large, this optimization takes on a simple form, and once the solution to this optimization problem is found, simple proportional QoS routing schemes will suffice. However, this optimization problem requires global information. We develop a distributed and adaptive algorithm that can efficiently solve the optimization online. Compared with existing QoS routing schemes, the proposed optimization-based approach has the following advantages: 1) the computation and communication overhead can be greatly reduced without sacrificing performance; 2) the operating characteristics of the network can be analytically studied; and 3) the desired operating point can be tuned by choosing appropriate utility functions     

Adaptive call admission control under quality of serviceconstraints: a reinforcement learning solution

We solve the adaptive call admission control (CAC) problem in multimedia networks via reinforcement learning (RL). The problem requires that network revenue be maximized while simultaneously meeting quality of service (QoS) constraints that forbid entry into certain states and use of certain actions. We show that RL provides a solution to this constrained semi-Markov decision problem and is able to earn significantly higher revenues than alternative heuristics. Unlike other model-based algorithms, RL does not require the explicit state transition models to solve the decision problems. This feature is very important if one considers large integrated service networks supporting a number of different service types, where the number of states is so large that model-based optimization algorithms are infeasible. Both packet-level and call-level QoS constraints are addressed, and both conservative and aggressive approaches to the QoS constraints are considered. Results are demonstrated on a single link and extended to routing on a multilink network     

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.