Future Multi-access edge computing (MEC) systems are required to execute applications composed of dependent tasks under end-to-end delay requirements. Further, they are likely to rely on renewable (or green) energy sources that are limited and fluctuate over time. These conditions give rise to a fundamental optimization problem that involves determining how tasks should be offloaded across edge servers so that dependency and delay constraints are satisfied while maximizing green energy usage or reducing an operator’s reliance on brown energy. In addition, the problem involves how green energy is shared among servers. Henceforth, we address a novel problem, called Green Dependent Task Offloading (G-DTO), that aims to maximize green energy usage, subject to the following constraints: (i) each edge server has limited green energy and computational capacity, and (ii) each task of an application, with a specified size, energy, and computational requirement, must be executed by a given deadline. To determine the optimal solution, we outline a Mixed-Integer Linear Programming (MILP) model. We also outline a genetic-algorithm-based approach, called G-DTO/GA. The simulation results on 18 synthetic network scenarios with small problem instances show that G-DTO/GA achieves an average of 96.83% green energy usage, closely matching the optimal MILP solution while requiring only 9.93% of the MILP runtime. Further experiments on the same 18 synthetic network scenarios, but with large problem instances, show that G-DTO/GA sustains high green energy usage, averaging 90.10%.

This paper introduces a novel network planning problem called Multi-stage Edge Server Deployment (M-ESD). The problem calls for a solution that (i) adds fixed edge servers to an existing Multi-access Edge Computing (MEC) network incrementally over multiple stages, e.g., in years, and (ii) optimizes the offloading of tasks to installed servers. More specifically, when upgrading a network, at each stage, the problem involves the following constraints: (i) budget (in $), (ii) server deployment cost (in $) and cost depreciation rate (in %), (iii) number of tasks and their increase rate (in %), and (iv) server storage capacity . The goal of M-ESD is to ensure the resulting network maximizes the average number of tasks that meet their delay requirement. This paper presents a Mixed Integer Linear Programming (MILP) model and a heuristic approach called M-ESD/H to solve the M-ESD problem. Simulation results on small networks show that M-ESD/H produces results that are within 13.6% of the optimal MILP solution. Further, it significantly reduces runtime and produces results in less than 0.1 s as compared to MILP, which failed to produce results in some networks after running for over 48 h. For large networks, M-ESD/H is compared against two versions of M-ESD that consider arbitrary budget allocation and/or edge server placement, i.e., M-ESD/A1 and M-ESD/A2. The results show that M-ESD/H outperforms both M-ESD/A1 and M-ESD/A2 across various options with varying numbers of stages, budget allocation, and tasks.

This article considers a topology construction problem involving a fixed-wing autonomous aerial vehicle (AAV), a set of quad-rotor AAVs and mobile ground users. The constructed topology must maximize the max-min flow rate of ground users over a given planning horizon. To this end, we outline a mixed integer linear program (MILP) that jointly optimizes the trajectory of the fixed-wing AAV, placement of quad-rotor AAVs, and routing of traffic from each source-destination ground user pair. Solving the MILP is challenging because it requires an exhaustive collection of topologies. To this end, this article outlines a solution called rollout to determine the network topology in each time slot of a given planning horizon iteratively. The main idea of rollout is to generate a sequence of future decisions using a heuristic, where a decision corresponds to the placement of quad-rotor AAVs. Further, each sequence of decisions has a cost-to-go value. Rollout then selects the sequence with the highest cost-to-go value. The results show that the max-min flow rate achieved by rollout is on average 81% that of MILP.

This article considers an unmanned aerial vehicle (UAV) that is used in industrial Internet of things (IIoT) networks to execute one or morepreloadedcomputation tasks. A key novelty is that these tasks support imprecise computation, where each task has a mandatory and optional part. Another novelty is that both parts of a task require data from one or more solar-powered ground devices. The mandatory part of each task must be computed by the UAV before the end of its trajectory. If there are sufficient resources and time, the UAV can download more data from devices and execute the optional part of tasks to improve results quality. To schedule tasks on a UAV, this article outlines a novel mixed integer linear program to optimize the execution of tasks and data collection. Furthermore, it outlines the first model predictive control (MPC)-based solution, called MPC-$S$, for the problem at hand that uses current and past energy arrivals information of devices. Our results show that MPC-$S$achieves approximately 89.9% of the optimal results quality.

In future Internet of Thing (IoT) networks, devices can be leveraged to compute tasks or services. To this end, this article addresses a novel problem that requires devices to collaboratively execute tasks with dependencies. A key consideration is that in order to conserve energy, devices may execute a task in approximate mode, which generate errors. To optimize their operation mode, we outline a novel chance-constrained program that aims to execute as many tasks as possible in approximate mode subject to a probabilistic constraint relating to the said errors. We also outline two novel solutions to determine task execution modes: 1) a sample average approximation (SAA) method and 2) a heuristic solution called minimum communication cost (MinC). We have studied the performance of SAA and MinC with round robin (RR), which assigns tasks to devices in an RR manner. Specifically, we find that the maximum energy consumption of devices when using MinC and RR is, respectively, around 14.2% and 23.1% higher than SAA, which yields the optimal solution. Further, MinC results in approximately 27.9% lower energy consumption as compared to RR.

This paper considers a network design problem using Unmanned Aerial Vehicles (UAVs). It aims to create a network to provide communication and computation service to a set of source-destination ground node pairs. The main performance metric is the minimum amount of computed data among a set of source-destination pairs. To optimize this metric, we outline two mixed Integer Linear Programs (MILPs), namely S-MILP and NS-MILP, which are designed respectively for splittable and non-splittable traffic flow models. They jointly optimize the placement of UAVs, assignment of Virtualized Network Functions (VNFs), and routing of unprocessed and processed flow. Further, NS-MILP optimizes the path selection of each source-destination pair. A key challenge is that these MILPs require an exhaustive collection of network topologies. To this end, this paper outlines two heuristic algorithms, called Resource-Aware Location Selection (RALS) and Resource-Aware Path and Location Selection (RAPLS), respectively for each traffic flow model. The simulation results show that RALS and RAPLS achieve on average 83% and 80% of the amount of computed flow of S-MILP and NS-MILP, respectively. Lastly, RALS and RAPLS require 45% and 53% less computation time as compared to S-MILP and NS-MILP, respectively.

This article considers task scheduling in solar-powered Internet of Things (IoT) networks where devices are capable of sharing energy wirelessly. Our aim is to minimize the completion time of all tasks. We outline a novel mixed-integer linear program (MILP) to schedule tasks and determine whether devices share their harvested energy via radio frequency (RF) in each time slot. The MILP considers the coupling between the energy level at devices across time slots. It also considers the dependency of tasks, whereby each task must be executed on a given set of devices in a specific order. Further, we propose a heuristic algorithm called minimum time first with energy sharing (MinTime-ES) for large scale networks. Our results show that with energy sharing, MILP and MinTime-ES achieve 28.86% and 7.83% reduction in task completion time as compared to competing algorithms that do not consider energy sharing between devices.

This article considers routing and link scheduling in a two-tier wireless backhaul network. The first tier consists of routers and the second tier consists of radio frequency (RF)-energy-harvesting Internet-of-Things (IoT) devices that rely on routers for energy. Our aim is to derive the shortest time division multiple access (TDMA) link schedule that satisfies the traffic demand of routers and energy demand of IoT devices. We formulate a linear program (LP) to jointly derive a routing and link schedule solution. We also propose a heuristic link scheduler called transmission set generation (TSG) to generate transmission sets and to derive the transmit power allocation of routers. In addition, we present a novel routing metric that considers RF-energy-harvesting devices on a given path. TSG on average achieves 31.25% shorter schedules as compared to competing schemes. Finally, our novel routing metric results in link schedules that are at most 24.75% longer than those computed by LP.

This article considers routing and link scheduling in a two-tier wireless Internet of Things (IoT) network. The first tier consists of routers that communicate via active radio-frequency (RF) transmissions. The second tier consists of passive tags that backscatter ambient RF signals from routers. Our objective is to maximize the network throughput at both tiers. To this end, we outline a mixed-integer linear program (MILP) that jointly optimizes the active time of RF links and backscatter links, and traffic over links. We also present a heuristic called the algorithm-transmission set generator (ALGO-TSG) to compute transmission sets. Moreover, we also outline a heuristic called centralized max-flow (CMF) to maximize network throughput by jointly considering routing and link scheduling. The results show that: 1) the network throughput achieved by ALGO-TSG at both tiers is 29.80% higher as compared to the case without backscattering and 2) the throughput of CMF is on average 21.36% lower than the throughput computed by MILP.

This article considers energy delivery by a hybrid access point (HAP) to one or more radio-frequency (RF)-energy harvesting devices. Unlike prior works, it considers imperfect and causal channel state information (CSI) and probabilistic constraints that ensure devices receive their required amount of energy over a given planning horizon. To this end, it outlines two novel contributions. The first is a chance-constrained program, which is then solved using a mixed-integer linear program (MILP) coupled with a sample average approximation (SAA) method. The second is a model predictive control (MPC) solution that utilizes the Gaussian mixture model (GMM) and a so-calledbackoffthat is used to tighten probabilistic constraints. The results show that the performance of the MPC-based solution is within 8% of the optimal solution with a probability of 90.8%.

This paper considers the problem of activating links in a rechargeable Wireless Sensor Network (rWSN). Unlike past works, it considers: (i) the energy harvesting time of nodes, (ii) a battery cycle constraint that accounts for memory effects, and (iii) nodes with a dual-battery system. It outlines a greedy algorithm that schedules links according to the earliest time in which a battery at the end nodes of each link can be discharged or is full. Our results show that equipping nodes with a dual-battery system decreases link schedules by up to 35.19% and 15.12% as compared to equipping nodes with a single battery with and without the said battery cycle, respectively. Such a system also respectively reduces the number of charge/discharge cycles by up to 15% and 87.13%. Finally, a longer energy harvesting time increases link schedules linearly, but has no impact on the number of charge/discharge cycles.

This paper considers the problem of upgrading a legacy network into a Software Defined Network (SDN) over multiple stages and maximizing energy saving (ES) in the resulting upgraded network or hybrid SDN. In each stage, an operator needs to select and replace legacy switches with SDN switches and seek to switch off as many cables as possible over each link. This paper addresses the said problem where it considers (i) the available budget at each stage, (ii) maximum path delays, (iii) maximum link utilization, (iv) per-stage increase (decrease) in traffic size (upgrade cost), and (v) each non SDN switch must comply with the Open Shortest Path First (OSPF)-Equal Cost Multi-Path (ECMP) protocol. It outlines a Mixed Integer Program (MIP) and a heuristic algorithm called M-GMSU. The results show that (i) MIP and M-GMSU achieve ES of up to 71.93%, (ii) using a larger budget and/or number of stages increases ES, and (iii) the ES of M-GMSU is within 3.55% away from the optimal ES computed by MIP.

This article considers a novel Internet of Things network comprising of sensor devices and power beacons (PBs); both types of nodes are equipped with a cognitive radio (CR). In addition, these sensor devices are powered by radio-frequency signals from PBs. Our aim is to maximize the minimum rate of devices acting as sources. We outline the first mixed integer linear program (MILP) that jointly optimizes the channel assignment of PBs and devices, beamforming vector of PBs, data routing over multiple hops and link activation schedule of devices. We also design a distributed protocol called distributed max–min rate with CR (D-MRCR) for use by devices and PBs. Devices set their operation mode using local information and use a game theory-based approach to iteratively adjust their transmit power. On the other hand, each PB employs a linear program to determine its beamforming vector. Our results show that the max–min rate of D-MRCR is within 51.84% that of MILP.

A binary transmission range model, widely utilised for the connectivity analysis of wireless multihop networks (WMNs), ignores the stochastic nature of wireless channels leading to erroneous results and conclusions in estimating the connectivity metrics. This work examines the influence of boundary effects along with the stochastic nature of wireless channels on the connectivity metrics of WMNs. Specifically, this work proposes analytical closed‐form solutions for the minimum node degree distribution and node isolation probability of a WMN deployed in a circular region by considering boundary effects in shadowing environments. Furthermore, it investigates the influence of node's transmission range, node's count, and the standard deviation of shadowing effects on minimum node degree distribution, node isolation probability, and ‐ connectivity. The authors simulation results on WMNs show that with the increase in the standard deviation of shadowing effects, node isolation probability increases, and minimum node degree distribution as well as ‐ connectivity decreases. Furthermore, the node isolation probability decreases, and minimum node degree distribution as well as ‐ connectivity increases with the increase in node's count and node's transmission range. The results produced by their analytical approach have only up to 0.0033 root mean square error as compared to simulated results, showing the accuracy of their approach.

Future Internet-of-Things (IoT) networks will consist of radio-frequency (RF) energy harvesting devices that are charged by solar-powered power beacons (PBs). To this end, this article aims to maximize the minimum data rate of devices acting as sources operating in a multihop IoT network. The main problem is to decide the amount of energy delivered by solar-powered PBs, routing of data from each source, and link scheduling, which determines the capacity of links. To this end, we make two contributions. First, we present a linear program (LP) to optimize the max-min rate of sources. Our LP considers nonlinear RF conversion at devices, energy storage loss at devices due to the imperfect battery, and time-varying channel quality, which affect the amount of energy harvested by devices. The second contribution is a novel distributed protocol called distributed max-min rate allocation (D-MRA), whereby devices only need local information, such as their battery and data buffer state to make decisions. Our results show that the max-min rate of D-MRA is 58.25% that of LP, which requires global information, in all tested cases.

Wireless sensor networks (WSNs) find application in various fields like environmental monitoring, health-care, land security, and many more. To ease our day-to-day activity, WSNs have become an integral tool for complex data gathering tasks. Monitoring a phenomenon by a WSN depends on the collective data provided by the sensor nodes. To ensure reliable operation of WSNs, it is important to quantify the performance of such networks in terms of network reliability measures. This article studies the reliability of WSNs with multistate nodes and proposes an approach to evaluate the flow-oriented network reliability of WSNs consisting of multistate sensor nodes. The proposed method takes into account the dynamic state of the network due to multistate sensor nodes. The proposed approach includes enumeration of shortest minimal paths from application-specific flow satisfying sensor nodes (source nodes) to the sink node. It then proposes a modified sum-of-disjoint products approach to evaluate WSN reliability in the presence of multistate nodes from the enumerated shortest minimal paths. Simulations are performed on WSNs of various sizes to show the applicability of the proposed approach on arbitrary WSNs.

We consider Rechargeable Wireless Sensor Networks (R-WSNs) where nodes harvest energy from both solar and the Radio Frequency (RF) transmissions of their neighbors. Our aim is to maximize the minimum source or sensing rate of nodes. This rate is determined by the available energy at sensor nodes as well as link capacity, which is determined by the set of transmitting nodes. In this paper, we first study and show the benefits of energy sharing. Intuitively, a sensor node should share its energy if doing so increases source rates. We present a novel Linear Program (LP) to determine the routing, link schedule, energy transmission, and reception time that maximize the minimum source rate of a given R-WSN. Our numerical results indicate that, on average, the minimum transmission rate of sensor nodes increased by 16.03 percent when nodes share energy. This motivates the development of a practical protocol called E-RSVP that iteratively increases the time slots of each source node. It also considers using time slots for transmission or reception of energy. Our simulation results show E-RSVP yields minimum source rates that are 14.80 percent higher as compared to the case without energy sharing.

A link scheduler ensures the transmissions in rechargeable Wireless Sensor Networks (rWSNs) are collision-free. Hence, it plays a critical role in ensuring high network capacity and the energy used for transmission/reception is not wasted due to collisions. This paper proposes a scheduler that generates a Time Division Multiple Access link schedule for use in a rWSN. Different from most prior works, our scheduler considers the time required by each node to harvest sufficient energy to transmit/receive a packet. Further, it utilizes the more efficient Harvest-Use-Store (HUS) model and considers sensor nodes with finite battery capacity. We present a greedy heuristic that activates links according to the earliest time in which their end nodes have sufficient energy to transmit/receive a packet. Our simulation results show that the time to recharge a sensor node significantly increases the link schedule or superframe lengths; i.e., by up to 563.9% as compared to the case where sensor nodes have no energy constraint. Further, in comparison to the Harvest-Store-Use (HSU) model, using HUS can reduce superframe lengths by up to 45.3%. Our experiments also show that increasing battery capacity does not effect the superframe length significantly; i.e., it reduces the length only by up to 2.5%. Finally, our proposed heuristic can generate superframe lengths that are on average 23% longer as compared to the lower bound on the superframe length when nodes have energy constraint.

In a rechargeable wireless sensor network (rWSN), the amount of data forwarded by source nodes to one or more sinks is bounded by the energy harvesting rate of sensor nodes. To improve sensing quality, we consider a novel approach whereby we place a finite number of auxiliary chargers (ACs) with wireless power transfer and energy harvesting ability to boost the energy harvesting rate of some sensor nodes. We formulate a mixed integer linear program (MILP) to determine the subset of nodes that if upgraded will maximize the minimum source rate. We also propose two heuristic algorithms to place ACs in large-scale rWSNs: greedy node deployment (GND), which checks every nonupgraded sensor node and places an AC next to the one yielding the highest increase in max-min rate; and one-unit energy deployment (OUED), which uses a relaxed version of the MILP to first share one unit of energy among sensor nodes. It then upgrades the sensor node with the highest one-unit share. Our results show that the max-min rate obtained by GND and OUED is, respectively, within 99.60% and 97.82% of the max-min rate derived by MILP in small networks with at most 90 nodes. In large networks with 200 nodes, the maximum gap between OUED and GND is only 0.191 kb/s. Lastly, OUED runs at least five times faster than GND.

This paper addresses an NP-hard problem, referred to as Network Topology Design with minimum Cost subject to a Reliability constraint (NTD-CR), to design a minimal-cost communication network topology that satisfies a pre-defined reliability constraint. The paper describes a dynamic programming (DP) scheme to solve the NTD-CR problem, and proposes a DP approach, called Dynamic Programming Algorithm to solve NTD-CR (DPCR-ST), to generate the topology using a selected sequence of spanning trees of the network, STXmin. The paper shows that our DPCR-ST approach always provides a feasible solution, and produces an optimal topology given an optimal order of spanning trees. The paper proves that the problem of optimally ordering the spanning trees is NP-complete, and proposes three greedy heuristics to generate and order only k spanning trees of the network. Each heuristic allows the DPCR-ST approach to generate STXminusing only k spanning trees, which improves the time complexity while producing a near optimal topology. Simulations based on fully connected networks that contain up to 2.3×109spanning trees show the merits of using the ordering methods and the effectiveness of our algorithm vis-à-vis to four existing state-of-the-art techniques. Our DPCR-ST approach is able to generate 81.5% optimal results, while using only 0.77% of the spanning trees contained in networks. Further, for a typical 2 × 100 grid network that contains up to 1.899102spanning trees, DPCR-ST approach requires only k=1214 spanning trees to generate a topology with a reliability no larger than 5.05% off from optimal.

The capacity of Wireless Mesh Networks (WMNs) has significantly increased with the recent addition of multiple transmit (Tx) and receive (Rx) (MTR) capability or smart antennas. This increase however is predicated on an effective link scheduler. The aim of any scheduler is to derive a superframe comprising the smallest number of slots that affords each link one or more transmission opportunities. In particular, the scheduler is required to solve an instance of the NP-complete, MAX-CUT problem, in each time slot. To this end, there are a number of centralized schedulers, but only a handful of distributed schedulers. However, each of these distributed schedulers has its own drawbacks; either they do not guarantee maximal activated links or do not guarantee all links are activated. Henceforth, in this paper, we add to the state-of-the-art by proposing a novel distributed scheduler, called Algo-d, which approximates the MAX-CUT problem in a distributed manner using only local information. In fact, this is the first distributed solution for MAX-CUT problem. Through theoretical analysis and simulation, we show that Algo-d achieves the following performance: 1) Algo-d schedules on average 12% fewer and 46.5% more links in each time slot than two centralized algorithms, and 2) Algo-d schedules 28% more links than ROMA and 270% more links than JazzyMAC; both state-of-the-art distributed schedulers for MTR WMNs.

Network robustness and throughput can be improved by routing each demand d via two disjoint paths (2DP). However, 2DP routing increases energy usage while providing lower link utilization and redundancy. In this paper, we address an NP-complete problem, called 2DP-EAR, that aims to switch off redundant nodes and links while guaranteeing two constraints: traffic demands must be afforded 2DP, and maximum link utilization. We design an efficient heuristic, called 2DP by Nodes First (2DP-NF). We have extensively evaluated the performance of 2DP-NF on both real and/or synthetic topologies and traffic demands. As compared to using Shortest Path routing, on the GÉANT network, 2DP-NF can save around 20% energy by switching off links only with negligible effects on path delays and link utilization, even for MLU below 30%. Furthermore, 2DP-NF can obtain 39.7% power savings by switching off both nodes and links on the GÉANT network.

Green networking techniques aim to shut down the least utilized links and/or routers during off-peaks hours. In this paper, we show that such techniques negatively impact the operation of the Border Gateway Protocol (BGP). We quantify the impacts of two representative green approaches: (i) GAES, a green technique that modifies link weights, and (ii) ESOL, a green technique that does not involve link weights adjustments. Experiments over the Abilene, AT&T, GEANT and SURFnet topologies show that when using GAES, routing changes and the proportion of rerouted traffic, both of which affect BGP, are in the order of 108% and 141% greater than ESOL. Therefore, we propose Hot Potato Low UtiliZation (HotPLUZ), a green approach that takes hot-potato routing into account. HotPLUZ reroutes traffic from lowly utilized links and aggregate said traffic onto highly utilized links, whilst minimizing any changes to the corresponding egress router of a given destination. In addition, HotPLUZ considers link utilization in order to avoid packet loss and high latencies. Our experimental results indicate an overall saving of up to 21% under low network load.

Recently, researchers have created Wireless Mesh Networks (WMNs) where routers have multiple transmit (Tx) or receive (Rx) capability. A fundamental problem in such WMNs is deriving a transmission schedule that yields minimal end-to-end delays. In this paper, we approach this problem via joint routing and link scheduling. Specifically, we consider two fundamental issues that influence end-to-end delays: superframe length and transmission slot order. We propose two algorithms: JRS-Multi-DEC and JRS-BIP, where the former uses a novel metric to minimize the load of each link whilst the latter uses a binary integer program solver. Both algorithms have the similar aim of minimizing overall delay and to re-order slots such that packets are forwarded quickly along their path. Numerical results show that our algorithms can reduce average delay by approximately 50% as compared to a non joint routing and scheduling algorithm.

Recently, researchers have developed Wireless Mesh Networks (WMNs) where each router is capable of performing multiple transmissions or receptions concurrently; aka Multi Tx-Rx (MTR) WMNs. Consequently, each node is able to transmit (Tx) or receive (Rx) to/from its neighbors simultaneously. A fundamental problem in such WMNs is to derive a transmission schedule with minimal superframe length to maximize network capacity and minimize end-to-end delays. Unfortunately, deriving a minimal superframe length is equivalent to solving the NP-complete, MAX-CUT problem. To this end, there are a number of centralized schedulers, but only but only one distributed scheduler, called JazzyMAC. Henceforth, in this paper, we add to the state-of-the-art by proposing Algo-d, a novel distributed scheduler that solves the MAX-CUT problem using only local information. Experiment results show Algo-d generates superframes that are 37.5% shorter and it activates 264% more links as compared to JazzyMAC. Lastly, as compared to centralized schedulers, Algo-d schedules 50% more links than Algo-1 and at most 7% fewer links than Algo-2.

Next generation Wireless Mesh Networks (WMNs) will require a link scheduler that exploits the full advantage of Multi-Transmit-Receive (MTR) communication. To this end, we design a distributed link scheduler called Voting-ALGO that is aware of queue lengths and uses the celebrated max weight policy to achieve 100% throughput.

This paper addresses an NP-hard problem to design a network topology with maximum all-terminal reliability subject to a cost constraint, given the locations of the various computer centers (nodes), their connecting links, each link's reliability and cost, and the maximum budget cost to install the links. Because cost is always a major focus in network design, this problem is practical for critical applications requiring maximized reliability. This paper first formulates a Dynamic Programming (DP) scheme to solve the problem. A DP approach, called DPA-1, generates the topology using all spanning trees of the network (STG). The paper shows that DPA-1 is optimal if the spanning trees are optimally ordered. Further, the paper describes an alternative DP algorithm, called DPA-2, that uses only k spanning trees ( k ≤ n, where n=|STG|) sorted in increasing weight and lexicographic order to improve the time efficiency of DPA-1 while producing similar results. Extensive simulations using hundreds of benchmark networks that contain up to 1.899102spanning trees show the merits of using the sorting method, and the effectiveness of our algorithms. DPA-2 is able to generate 85% optimal results, while using only a small number of k spanning trees, and up to 16.83 CPU seconds. Furthermore, the non-optimal results are only up to 3.4% off from optimal for the simulated examples.

This paper addresses an NP-complete problem, called NTD-CR, to design a minimal-cost communication network topology that satisfies a pre-defined two terminal reliability constraint, given the locations of the various computer centers (nodes), their connecting links, each link's reliability and cost, and the required reliability for the network to operate. This paper formulates a dynamic programming (DP) scheme to solve the NTD-CR problem. DP approach, called DPCR-P, generates the topology using a selected set of paths of the network. We propose two different greedy heuristics to generate and order only k≤n paths, where n is the total number of paths in the network. Each heuristic allows DPCR-P to enumerate the selected paths using only k paths, which improves the time complexity while producing near optimal topology. Extensive simulations using benchmark networks with various sizes show the merits of path-orders, and the effectiveness of our approach. DPCR-P is able to generate 91% optimal results on the networks using only 8.89% to 27.5% of all paths in the networks. Further, its non-optimal results are no more than 10.97% off from optimal.

Current network infrastructures are over-provisioned to increase their resilience against resource failures, e.g., bundled links and nodes, as well as congestion during peak hours. However such strategies waste resources as well as exhibit poor energy efficiency at off-peak periods. To this end, several energy-aware routing algorithms have been proposed to maximally switch off redundant network resource at low traffic load to minimize energy usage. These routing solutions, however, do not consider network reliability as critical back-off links/nodes maybe switched off. Henceforth, we aim to quantify the effects of five recently proposed green routing approaches, namely FGH, GreenTE, MSPF, SSPF, and TLDP, on the following two reliability measures: (i) 2-terminal reliability (ii) path reliability. Experiments using three topologies with real and synthetic traffic demands show that switching off redundant links significantly affects the 2-terminal reliability. Routing traffic through multiple paths has lesser reliability impact while reducing energy, especially when the paths are link disjoint. Interestingly, TDLP and MSPF have better path reliabilities than using shortest path routing.

This paper considers the problem of deriving a link schedule for Time Division Multiple Access (TDMA)-based concurrent transmit/receive Wireless Mesh Networks (WMNs) that results in low end-to-end delays as well as high network capacity. We first propose a MAX-CUT heuristic approach, called Algo-2, that maximizes link activations in each slot of a super-frame. Algo-2 is shown to produce better network capacity as compared to existing heuristic approaches and significantly improves the super-frame length of an existing MAX-CUT approach that enforces 2-phase transmit-receive restriction - a node that transmits (receives) in slot i ≥ 1 is to become a receiver (transmitter) in slot i + 1. Then, we propose a heuristic solution, called BDA, as a complement to existing schedulers to reduce transmission delays. Since BDA only reorders slots in the superframe, it maintains each original schedule's super-frame length, and hence capacity, while reducing delays by up to 70% in 6-node random topology networks.

Network robustness and throughput can be improved by routing each source-to-terminal (s, t) demand via two link-disjoint paths (TLDP). However, the use of TLDP incurs higher energy cost. Henceforth, we address the problem of minimizing the energy usage of networks that use TLDP. Specifically, our problem is to maximally switch off redundant network links while maintaining at least 0≤T≤100% of (s, t) TLDP in the network, for a given T, and limiting the maximum link utilization (MLU) to no greater than a configured threshold. To address this problem, we present a fast heuristic, called TLDP by Shortest Path First (TLDP-SPF), and extensively evaluate its performance on both real and/or synthetic topologies and traffic demands. Our simulation results show that TLDP-SPF can reduce network energy usage, on average, by more than 20%, even for MLU below 50%. As compared to using Shortest Path routing, while reducing energy by about 20%, TLDP-SPF does not significantly affect (s, t) path length, even for MLU<50%.

This paper addresses the NP-hard problem of switching off bundled links whilst retaining the QoS provided to existing applications. We propose a fast heuristic, called Multiple Paths by Shortest Path First (MSPF), and evaluated its performance against two state-of-the-art techniques: GreenTE, and FGH. MSPF improves the energy saving on average by 5% as compared to GreenTE with only 1% CPU time. While yielding equivalent energy savings, MSPF requires only 0.35% of the running time of FGH. Finally, for Maximum Link Utilization (MLU) below 50% and delay no longer than the network diameter, MSPF reduces the power usage of the GÉANT topology by up to 91%.

Recently, multipath solutions have been proposed to improve the quality-of-service of the source to destination (s,t)-path in communication networks (CNs). This paper de scribes the λDP/DR problem to obtain λ ≥ 1 edge-disjoint (s,t)-paths (λDP) such that its reliability is maximized while keeping its delay no longer than a delay constraint D ≥ 1. This problem is NP-hard, and thus this paper proposes an approximate solution using Lagrange-relaxation. Our algorithm generates λDP with δ(λDP) ≤ D, and reliability bounded by |log(Rmin)| ≤ |log(ρ(λDP))| ≤ (1 + k)*|log(Rmin)|, where Rminis the minimum reliability of any (s, t)-path in the CN, and k ≥ 1. Our simulations on forty random CNs and large grid networks show that our solution produces λDP with delay and reliability comparable to those obtained by the optimal but exponential time algorithm.

The success of wireless mesh networks hinges on their ability to support bandwidth intensive, multi-media applications. A key approach to increasing network capacity is to equip wireless routers with smart antennas. These routers, therefore, are capable of focusing their transmission on specific neighbors whilst causing little interference to other nodes. This, however, assumes there is a link scheduling algorithm that activates links in a way that maximizes network capacity. To this end, we propose a novel link activation algorithm that maximally creates a bipartite graph, which is then used to derive the link activation schedule of each router. We have verified the proposed algorithm on various topologies with increasing node degrees as well as node numbers. From extensive simulation studies, we find that our algorithm outperforms existing algorithms in terms of the number of links activated per slot, superframe length, computation time, route length and end-to-end delay.

Recently, multi-paths solutions have been proposed to improve the quality-of-service (QoS) in communication networks (CNs). This paper addresses the problem to obtain the λ-edge-disjoint-path-set (λ DP/B) with maximum bandwidth (λ DPB), for λ≥1. λDP/B is useful for applications that require maximum bandwidth for data transmission, such as video conferencing, video-on-demand, large file downloads and FTP. We propose a polynomial time heuristic algorithm, Maximum Bandwidth Algorithm (MBA), to solve the problem. We have implemented MBA and evaluated its performance against an optimal, but exponential time, brute force algorithm (BF) and three existing heuristic algorithms: Algorithm-1, CBA-G', DPSP'. Simulations on seventy CNs show that MBA is able to produce the optimal λ DPBfor about 99% of the time while using only 0.005% CPU time of BF. Our simulations also show that MBA is significantly more effective than these existing algorithms while using competitive CPU time.

Recently, multipaths solutions have been proposed to improve the quality-of-service (QoS) in communication networks (CN). Peng and Shen algorithm (PSA) was proposed to generate lambdaDP/DC - the maximum edge-disjoint-path-set with minimal cost subject to a delay constraint, for lambdales2. This paper introduces a different and equally important problem, lambdaDP/DR, to obtain the maximal edge-disjoint-path-set with maximum reliability subject to a given delay constraint, for lambdales1. lambdaDP/DR is applicable to time critical applications that require non-compromised time delay while demanding maximum system reliability. In this paper we show how lambdaDP/DR is different from lambdaDP/DC, and propose an approximate algorithm similar to the Lagrange-relaxation based PSA to solve the problem. Our simulations on three randomly generated CNs show that our polynomial time algorithm produced lambdaDP/DR with comparable optimality to that obtained using the NP-hard brute-force approach.

Multipath routing protocols (MRP) help improve the network quality of service (QoS), including load balancing, fault tolerance (reliability), aggregate bandwidth and delay. While multipaths communication provides better failure-tolerance, their resilience only holds if the multiple paths are selected carefully. Note that selecting an optimal path set is a NP-complete problem. Recently, several algorithms have appeared in the literature to help construct multiple node-disjoint paths or multiple edge-disjoint paths. This paper presents two algorithms, discussing the later issue. The first algorithm, called clique-based-approach (CBA), finds the edge-disjoint-path-set with the optimal reliability. The second algorithm, greedy-CBA (CBA-G), is a heuristic that reduces the computational complexity of CBA. Results show that CBA-G improves the efficiency of CBA without negatively affecting its effectiveness. We also provide an explanation as to why CBA-G is able to produce edge-disjoint-path-sets with reliabilities equal or better than a benchmark protocol, DPSP.

Dynamic IP router table schemes, proposed in the literature, perform an IP lookup or an on-line prefix update in O(log n) memory accesses. In term of lookup time, they are still slower than FEC (CNHA/CWA) scheme, which requires exactly (at most) three memory accesses for each lookup, irrespective of the number of prefixes n. The prefix update in FEC (CNHA/CWA) has a drawback: Off-line solutions need structure reconstruction, or implementing on-line prefix updates is difficult. This paper solves this problem. We propose the use of lexicographic ordered prefixes to reduce off-line construction time. Simulations on several real routing databases, run on the same platform, show that our approach constructs FEC (CNHA/CWA) tables in 2.56 to 7.74 (1.56 to 2.7) times faster than that from previous techniques. Our on-line update scheme uses an updatable-address-set and selectively decompresses the FEC and CNHA/CWA structures to modify only the next-hops of the addresses in the set. Recompressing the updated structures, the resulting tables are identical to what would have been obtained by structure reconstructions, but at much lower computational cost. Our on-line update for FEC (CNHA/CWA) scheme takes at most 10.1 (7.21) -Ýs, which is of same order as achieved by the recently proposed schemes.

This paper presents an efficient cutset approach to compute the reliability of a large communication network having heterogeneous link capacities. The reliability measure has been defined as capacity related reliability (CRR). The proposed method, subset cut technique (SCT), requires the cutset information of the network. For each minimal cut C/sub i/, and a given minimum bandwidth requirement W/sub min/, the method enumerates all nonredundant subset cut (SC), where each SC relates link capacities & minimum bandwidth requirements. Note that if all links in an SC fail, the capacity of the induced cut C/sub i/ will be less than W/sub min/. Given the failure probability of each link, and the nonredundant SC, any Boolean technique for generating mutually disjoint terms can be utilized to obtain a capacity related unreliability (CRU) of the network. Thus, the CRU for an (s,t) node pair is the probability that the network has a capacity of less than W/sub min/ for the given node pair. Note that CRR=1-CRU. Two SCT algorithms are proposed: Algorithm-1, and Algorithm-2; and the suitability of using either algorithm is also discussed. Examples are given to illustrate the techniques. The time complexity, and the proof of correctness for the proposed algorithms are also included. It is shown empirically that the time complexity of generating the nonredundant SC of a network is polynomial in the order of the number of cuts of the network. The proposed SCT algorithms have been implemented in C. We have utilized the SCT to generate the CRR of some large communication networks with various W/sub min/ values.

The hypercube topology, also known as the Boolean n-cube, has recently been used for multiprocessing systems. The paper considers two structural-reliability models, namely, terminal reliability (TR) and network reliability (NR), for the hypercube. Terminal (network) reliability is defined as the probability that there exists a working path connecting two (all) nodes. There are no known polynomial time algorithms for exact computation of TR or NR for the hypercube. Thus, lower-bound computation is a better alternative, because it is more efficient computationally, and the system will be at least as reliable as the bound. The paper presents algorithms to compute lower bounds on TR and NR for the hypercube considering node and/or link failures. These algorithms provide tighter bounds for both TR and NR than known results and run in time polynomial in the cube dimension n, specifically, within time O(n/sup 2/).>

Experimental results are presented showing the number of disjoint products and computer time involved in generating sum of disjoint product (SDP) terms. To help obtain the results, the authors have considered 19 benchmark networks containing paths (cuts) varying from 4 (4) to 780 (7376). Several SDP techniques are reviewed and are generalized into three propositions to find their inherent merits and demerits. An efficient SDP technique is, then, utilized to run input files of paths/cuts preprocessed using (1) cardinality, (2) lexicographic, and (3) Hamming distance ordering methods and their combinations. The experimental evaluation has been performed on an FPS 500 system. Results are analyzed, and it is shown that the preprocessing based on cardinality or its combinations with (2) and/or (3) performs better.>

An efficient method to compute the terminal reliability (the probability of communication between a pair of nodes) of a distributed computing system (DCS) is presented. It is assumed that the graph model G(V,E) for DCS is given and that the path and/or cut information for the network G(V,E) is available. Boolean algebraic concepts are used to define four operators: compare, reduce, combine, and generate. The proposed method, called CAREL, uses the four operators to generate exclusive and mutually disjoint events. CAREL has been implemented using bit vector representation on an Encore MULTIMAX 320 system. It is shown that CAREL solves large DCS networks (having a pathset on the order of 780 and a cutset on the order of 7300 or more) with a reasonable memory requirement. A comparison with other algorithms reveals the computational efficiency of the method. The proof of correctness of CAREL is included.>