In this article, we study the computation offloading problem in hybrid edge-cloud based space-air-ground integrated networks (SAGIN), where joint optimization of partial computation offloading, unmanned aerial vehicle (UAV) trajectory control, user scheduling, edge-cloud computation, radio resource allocation, and admission control is performed. Specifically, the considered SAGIN employs multiple UAV-mounted edge servers with controllable UAV trajectory and a cloud sever which can be reached by ground users (GUs) via multi-hop low-earth-orbit (LEO) satellite communications. This design aims to minimize the weighted energy consumption of the GUs and UAVs while satisfying the maximum delay constraints of underlying computation tasks. To tackle the underlying non-convex mixed integer non-linear optimization problem, we use the alternating optimization approach where we iteratively solve four sub-problems, namely user scheduling, partial offloading control and bit allocation over time slots, computation resource and bandwidth allocation, and multi-UAV trajectory control until convergence. Moreover, feasibility verification and admission control strategies are proposed to handle overloaded network scenarios. Furthermore, the successive convex approximation (SCA) method is employed to convexify and solve the non-convex computation resource and bandwidth allocation and UAV trajectory control sub-problems. Via extensive numerical studies, we illustrate the effectiveness of our proposed design compared to baselines.

In this paper, we study the computation offloading problem in space-air-ground integrated networks (SAGIN), where joint optimization of partial computation offloading, unmanned aerial vehicles (UAVs) trajectory control, user scheduling, computation and resource allocation is performed. Specifically, the considered SAGIN employs multiple UAV-mounted edge servers with controllable UAV trajectory and a cloud sever which can be reached by ground users (GUs) via multi-hop low-earth-orbit (LEO) satellite communications. This design aims to minimize the weighted energy consumption of the GUs and UAVs while satisfying the maximum delay constraints of underlying computation tasks. To tackle the underlying non-convex mixed integer non-linear optimization problem, we use the alternating optimization approach where we iteratively solve five sub-problems, namely user scheduling, partial offloading control and bit allocation over time slots, computation resource, bandwidth allocation, and multi-UAV trajectory control until convergence. In addition, the successive convex approximation (SCA) method is employed to convexify and solve the non-convex bandwidth allocation and UAV trajectory control sub-problems. Via extensive numerical studies, we illustrate the effectiveness of our proposed design compared to baselines under different network settings.

In this article, we study the trajectory control, subchannel assignment, and user association design for unmanned aerial vehicles (UAVs)-based wireless networks. We propose a method to optimize the max-min average rate subject to data demand constraints of ground users (GUs) where spectrum reuse and co-channel interference management are considered. The mathematical model is a mixed-integer nonlinear optimization problem which we solve by using the alternating optimization approach where we iteratively optimize the user association, subchannel assignment, and UAV trajectory control until convergence. For the subchannel assignment subproblem, we propose an iterative subchannel assignment (ISA) algorithm to obtain an efficient solution. Moreover, the successive convex approximation (SCA) is used to convexify and solve the nonconvex UAV trajectory control subproblem. Via extensive numerical studies, we illustrate the effectiveness of our proposed design considering different UAV flight periods and number of subchannels and GUs as compared with a simple heuristic.

In this paper, we study the trajectory control and sub-channel assignment for unmanned aerial vehicle (UAV) based wireless networks with wireless backhauls. This design aims to maximize the min rate achieved by ground users (GUs) subject to their data transmission demands. To tackle the underlying mixed integer non-linear optimization problem, we use the alternating optimization approach where we iteratively optimize the sub-channel assignment and UAV trajectory control until convergence. Toward this end, we propose a heuristic algorithm to obtain a feasible solution for the sub-channel assignment sub-problem. In addition, the successive convex approximation (SCA) method is used to convexify and solve the non-convex UAV trajectory control sub-problem. Via extensive numerical studies, we illustrate the effectiveness of our proposed design for different network settings.

In this paper, we study the trajectory control and sub-channel assignment for unmanned aerial vehicles (UAVs) based wireless networks with wireless backhaul links. This design aims to optimize the max-min rate subject to data transmission demands of ground users (GUs). The underlying problem is a mixed integer nonlinear optimization problem because of the complicated relationship between the UAV-GU channel gains and the UAV's location in each time slot of the flight period. To tackle this problem, we employ the alternating optimization approach where we iteratively optimize the sub-channel assignment and UAV trajectory control until convergence. Moreover, the difference of convex functions (DC) optimization method and the arithmetic and geometric means (AM-GM) inequality are employed to convexify and solve the non-convex UAV trajectory sub-problem. Via extensive numerical studies, we illustrate the effective UAV's trajectory considering capacity-limited access and backhaul links and the non-negligible rate gain of the proposed design compared to a baseline employing the circular UAV trajectory around the center of service area and a heuristic algorithm for sub-channel assignment.

In this paper, we study the problem of unmanned aerial vehicles (UAVs) placement and bandwidth allocation for wireless networks with wireless backhaul links. The general model with different possible configurations of line-of-sight (LoS) and non-line-of-sight (NLoS) propagation conditions of wireless links between UAVs and ground users (GUs) is explicitly considered based on which we derive the average rates for wireless access links. The underlying problem is a difficult non-convex optimization problem due to the strong co-channel interference and the complicated relationship between the LoS/NLoS probabilities and UAVs' locations. To solve this challenging problem, we employ the alternative optimization approach where we iteratively optimize the bandwidth allocation and UAV placement until convergence. Moreover, we employ the difference of convex functions (DC) optimization and quadratic transformation approaches to convexify and tackle the non-convex UAV placement sub-problem. Via numerical studies, we show that the proposed scheme achieves a significant throughput gain compared to a baseline in which UAVs are deployed at the centers of hotspot areas.

An important evolution of the users’ needs is represented by the on-demand access to the network, storage, and compute resources in order to dynamically match the level of resource consumption with their service requirements. The response of the network providers is to transition to an architecture based on softwarization and cloudification of the network functions. This is the rationale for the deployment of network functions virtualization (NFV) where virtual network functions (VNFs) may be chained together to create network services. Efficient online routing of demand across nodes handling the functions involved in a given service chain is the novel problem that we address in this paper. We provide an original formulation of this problem that includes link and CPU capacity constraints and is based on the construction of an expanded network. We derive the exact mathematical formulation and propose several heuristic algorithms taking into account the main system’s parameters. We conclude by deriving some interesting insights both about the algorithms and the network performance by comparing the heuristics with the exact solutions.

We study fast algorithms for the optimal power allocation in an OFDM-SDMA system when some users have minimum requirements for their downlink transmission rate. We first solve the unconstrained problem for which we propose a fast zero-finding technique that is guaranteed to find an optimal solution, and an approximate algorithm that has lower complexity but is not guaranteed to converge. For the rate-constrained problem, we propose two approximate algorithms. We present numerical results showing that the computation time for the iterative heuristic is about one order of magnitude faster than finding the exact solution with a numerical solver, and the non-iterative technique is an additional order of magnitude faster than the iterative heuristic. We also show that in most cases, the amount of infeasibility with the non-iterative technique is small enough that it can probably be used in practical systems.

In this paper, we study the resource allocation problem for a full-duplex (FD) multiuser wireless system consisting of one FD base-station (BS) and multiple FD mobile nodes. Our main focus is to jointly optimize the power allocation (PA) and subcarrier assignment (SA) for both uplink (UL) and downlink (DL) transmissions of all users to maximize the system sum-rate. Our design captures the self-interference of FD transceivers and allows the utilization of each subcarrier for multiple concurrent UP and DL transmissions. Since the joint optimization problem is a nonconvex mixed integer program, which is difficult to tackle, we propose to employ the bipartite matching method to address the SA. Toward this end, a fast greedy allocation algorithm is developed to perform initial assignment of UL/DL links to each subcarrier that offers the best sum rate. Then from the obtained SA solution, we adopt the successive convex approximation approach to solve the PA problem whose results are used to calculate the SA weights for re-optimizing the SA by using the bipartite matching method. We then present the numerical results to demonstrate the improvement of our proposed algorithm in comparison with the greedy FD and half-duplex (HD) resource allocation algorithms.

This paper focuses on the resource allocation in a full-duplex (FD) multiuser single cell system consisting of one FD base-station (BS) and multiple FD mobile nodes. In particular, we are interested in jointly optimizing the power allocation (PA) and subcarrier assignment (SA) for uplink (UL) and downlink (DL) transmission of all users to maximize the system sum-rate. First, the joint optimization problem is formulated as nonconvex mixed integer program, a difficult nonconvex problem. We then propose an iterative algorithm to solve this problem. In the proposed algorithm, the PA is obtained by employing the SCALE algorithm, whereas the SA is updated by a gradient method. Finally, we present numerical results to demonstrate the significant gains of our proposed design compared to that due to two fast greedy algorithms.

Multi-antenna OFDMA-SDMA systems provide the required high spectral efficiency and flexibility to support the ever increasing data rates requirements of real-time multimedia applications in future wireless access systems. However, the resource allocation process becomes extremely complex because of the large number of degrees of freedom and the strict timing requirement of real-time traffic. In this paper, we propose heuristics to efficiently solve the zero-forcing OFDMA-SDMA resource allocation problem and provide, when feasible, guaranteed service to users with minimum rate requirements. The heuristics combine both rate-constrained power allocation and subcarrier reassignment algorithms. We compare the heuristics performance against an upper bound and other methods proposed in the literature and find that, although they have a slightly lower sum rate performance, they support a wider range of minimum rates while significantly reducing the computational complexity, making them suitable for usage in real-time systems.

The development of native wireless network virtualization implies introducing a new set of base station schedulers that considers the efficient allocation of wireless resources to different Service Providers (SPs) based on flexible Service Level Agreements (SLAs). In this paper we develop an efficient and fast centralized heuristic to allocate the radio resource blocks in multi-cell LTE networks. The scheme maximizes the network-wide sum rate while keeping track of the SLA of each SP expressed as a minimum bandwidth allocation in each cell. We also propose an iterative solution procedure for the non-convex power allocation problem based on DC programming. We find that the results of the heuristic are quite close to those of the iterative method. We also show that there is a significant rate reduction due to the service contracts. Finally, we find that even if the heuristic cannot meet all the requirements in one particular scheduling period, it does provide the required rate over a large number of periods.

The successful virtualization of wireless access networks is strongly affected by the way in which radio resources are managed. The Infrastructure Provider (InP) is required to deploy efficient and flexible scheduling techniques to dynamically allocate the resources for the users associated with different Service Providers (SPs). Service contracts with different SPs and fairness among their users are crucial to the success of the virtualization scheme deployed by the InP. In this paper we develop an efficient resource allocation scheme to allocate the radio resource blocks in LTE networks. The scheme keeps track of the service contracts with the SPs and also the fairness requirements between cell-center users and cell-edge users. Also the scheme allows the flexible definition of fairness requirements for different SPs. The performance of the proposed schemes is evaluated and the results show that the proposed low-complexity scheme is very efficient in terms of computation time and its performance in terms of sum rate is close to the results due to the relaxed solution and coordinate search algorithm.

We study cross-layer design in random-access-based fixed wireless multihop networks under a physical interference model. Due to the complexity of the problem, we consider a simple slotted ALOHA medium access control (MAC) protocol for link-layer operation. We formulate a joint routing, access probability, and rate allocation optimization problem to determine the optimal max-min throughput of the flows and the optimal configuration of the routing, access probability, and transmission rate parameters in a slotted ALOHA system. We then also adapt this problem to include an XOR-like network coding without opportunistic listening. Both problems are complex nonlinear and nonconvex. We provide extensive numerical results for both problems for medium-size mesh networks using an iterated optimal search technique. Via numerical and simulation results, we show that: 1) joint design provides a significant throughput gain over a default configuration in slotted-ALOHA-based wireless networks; and 2) the throughput gain obtained by the simple network coding is significant, especially at low transmission power. We also propose simple heuristics to configure slotted-ALOHA-based wireless mesh networks. These heuristics are extensively evaluated via simulation and found to be very efficient.

For applications in which a node is interested in a function of the data generated at different sources, in-network computation is a promising approach to improve the network performance. In this paper, we study the problem of computing the first M moments of the data using in-network computation in an arbitrary wired communication network. We are interested in finding a routing and queue management strategy that maximizes the data rate at which the sources could generate new data. We first propose a very simple tractable flow model that computes an upper bound on the maximum data generation rate that could be supported in a given network for a given M. To validate the tightness of this upper bound and to provide a practical feasible solution, we then propose a heuristic strategy involving the generation of multiple trees and effective queue management that achieves data generation rates close to this upper bound. This cross-validates the tightness of the upper bound and the goodness of our heuristic strategy. Finally, using the flow model, we provide engineering insights on what in-network computation can achieve.

Many applications require the sink to compute a function of the data collected by the sensors. Instead of sending all the data to the sink, the intermediate nodes could process the data they receive to significantly reduce the volume of traffic transmitted: this is known as in-network computation. Instead of focusing on asymptotic results for large networks as is the current practice, we are interested in explicitly computing the maximum achievable throughput of a given network when the sink is interested in the first M statistical moments of the collected data. Here, the kth statistical moment is defined as the expectation of the kth power of the data. Flow models have been routinely used in multihop wireless networks when there is no in-network computation, and they are typically tractable for relatively large networks. However, deriving such models is not obvious when in-network computation is allowed. We develop a discrete-time model for the real-time network operation and perform two transformations to obtain a flow model that keeps the essence of in-network computation. This gives an upper bound on the maximum achievable throughput. To show its tightness, we derive a numerical lower bound by computing a solution to the discrete-time model based on the solution to the flow model. This lower bound turns out to be close to the upper bound, proving that the flow model is an excellent approximation to the discrete-time model. We then provide several engineering insights on these networks.

Current network planning and design methods use the average delay, packet loss and throughput as metrics to optimize the network cost and performance. New multimedia applications, on the other hand, also have critical jitter requirements that are not taken into account by these methods. Here, we explore the impact on the network performance of adding these jitter constraints. We use a fast jitter calculation model to solve the optimal routing problem for flows subject to jitter or delay constraints. We find that the optimal routing is very different for the two kinds of flows: They should be routed on different paths, the jitter-constrained flows should not be split on multiple paths while the opposite conclusion is true for delay-constrained flows.

MISO-OFDM systems enable the allocation of resources in the frequency and spatial domain to increase the data throughput of wireless systems. In this paper, we initially present a near-optimal solution to the MISO-OFDM Resource Allocation (RA) problem. This solution performs an exhaustive search over all possible user sets and then uses a dual-based approach to optimally assign power to the selected user sets. However, this algorithm requires computing the pseudo-inverse of all subchannel matrices. In order to reduce its computational complexity we derive an efficient heuristic RA algorithm. We first propose an approximation method that only computes the determinant of the squared subchannel matrices and selects the sets with maximum determinant per subcarrier. We then further reduce the computational cost by using a greedy search method which decreases the number of candidate users for each subcarrier. We present simulation results which show that the performance gap of the approximate method is under 0.6% with respect to the near-optimal solution, and under 1.4% when we use the greedy search method pre-selecting 4 sets. These results show that the proposed heuristic algorithms can achieve a performance very close to the optimal at a low computational cost even with a large number of users in the cell.

We present a number of significant engineering insights on what makes a good configuration for medium- to large-size wireless mesh networks (WMNs) when the objective function is to maximize the minimum throughput among all flows. For this, we first develop efficient and exact computational tools using column generation with greedy pricing that allow us to compute exact solutions for networks significantly larger than what has been possible so far. We also develop very fast approximations that compute nearly optimal solutions for even larger cases. Finally, we adapt our tools to the case of proportional fairness and show that the engineering insights are very similar.

In this paper, we study the joint configuration of routing and medium access control (MAC) parameters in fixed wireless networks. Due to the complexity of the problem, we consider a simple slotted ALOHA MAC protocol for link layer operation. We model the link rate of the slotted ALOHA system under a saturation assumption and use a signal to interference plus noise ratio (SINR) based interference model via the concept of conflict set. We formulate a joint routing and MAC (JRM) optimization problem to determine the optimal max-min throughput of the flows and the optimal configuration of routing and MAC parameters. The JRM optimization problem is a non-convex optimization problem and we solve it by an iterated optimal search technique. We validate our approach via simulation and illustrate the potentially high throughput gains that can be obtained by using our joint configuration technique.

We focus on efficient algorithms for resource allocation problems in large wireless networks. We first investigate the link scheduling problem and identify the properties that make it possible to compute solutions efficiently. We then show that the node on-off scheduling problem shares these features and is amenable to the same type of solution method. Numerical results confirm the efficiency of our technique for large scale problems. We also extend the technique to the case where the objective function is nonlinear showing that our technique blends smoothly with a sequential linear programming approach. Numerical results for a cross-layer design with a nonlinear fairness utility show that it is possible to compute optimal solutions for large wireless networks in reasonable CPU time.

Wireless mesh networks are considered as a potentially attractive alternative to provide broadband access to users. They have been studied extensively by the research community since they raised a lot of new issues due to their unique characteristics. Here, we focus on scenarios where these networks are installed and managed to provide broadband access to a set of fixed nodes. While a lot of research has been done on this type of networks, there are very few insightful engineering results that can help network operators deploy and manage such networks. It is the objective of this paper to present some major engineering insights on such networks. We limit our scope to networks that are single rate and in which all nodes use the same transmit power. In particular, we quantify the advantage of multi-hop over single-hop. We illustrate the importance of multi-path routing over single path routing, and of optimal routing versus min-hop routing. We revisit the notion of spatial reuse. Finally we present results showing the importance of selecting an appropriate interference model.

We consider a resource allocation problem for spectrum sharing in cognitive radio networks. Specifically, we investigate the joint subchannel, rate and power allocation for secondary users which share, in a non-disruptive manner, some frequency bands with primary users using OFDM technology. We consider the resource allocation problem for downlink and take into account the maximum total power constraints of the base station and the power constraints determined by distributed spectrum sensing and scanning. We formulate a resource allocation problem as an optimization problem which achieves max-min rate sharing among users. We propose both integer program based optimal and suboptimal fast and low complexity approaches for the spectrum sharing problem. Numerical results are then presented for the proposed heuristics and compared with the optimal solution.

We consider the problem of multirate network design with point-to-multipoint communications. We give a mathematical formulation for this problem. Using approximations, we show that traffic concentration on a small number of links significantly reduces the cost of the network. We then propose a heuristic based on the traffic concentration principle to solve the network design problem approximately. Because this heuristic no longer requires advanced knowledge of demand matrices, we explain how it can be used as the basis for real-time design procedures. By means of numerical results, we show that this heuristic yields nearly optimal solutions.

Multicommodity flow (MF) models are well known and have been widely used in the design of packet-switched networks. They have also been used as approximations in the design of circuit-switched networks with reliability constraints. We investigate the usefulness of multicommodity models both as routing models and as an integral part of design models conceived under the failure propagation strategy. First, we compare the performance measures calculated by the models with results produced by a real-time technique. Next, we study the performance of networks dimensioned with flow models and with known adaptive models under failures of transmission facilities when a real-time routing technique is used. Results obtained using realistic data show that the MF models compare favorably with exact dimensioning algorithms when failures are considered.

We consider the optimization of routing in a broadband ISDN network through the maximization of the revenue generated by the network. Two types of calls are offered to the network with different holding times and bandwidths. The routing is alternative routing and load sharing. First we state the Kuhn-Tucker conditions and show how they provide a simple routing rule based on equal marginal net revenue. We then proposed two-stage decomposition algorithm for optimizing the routing which requires a flow-deviation stage combined with the solution of a linear system of equations. We obtain simple expressions for the net path revenues and the corresponding optimal routing rule. We summarize numerical results related to the convergence of the algorithm and the structure of the optimal routing.>

The optimal routing and dimensioning of circuit-switched networks operating with call revenues is examined, and F.P. Kelly's (1988) model is extended in two directions. First, the formulation is transformed in such a way that the optimality equations are significantly easier to derive, and another interpretation of Kelly's induced costs is given. Alternative routing is introduced, the corresponding values for the induced costs and the net path revenue are given, and it is shown that the optimal routing is given by an equal-revenue rule. It is also shown that the dimensioning aspect is easily decomposed into individual link dimensioning problems if the fixed-point multipliers are known. Some results for networks operating with state protection are presented to show that the method also works quite well for networks with heterogeneous traffic.>

The authors present an algorithm for the multihour dimensioning of telephone networks operating with residual capacity adaptive routing. The method is based on dimensioning techniques for networks operating with nonhierarchical alternate routing and relies on a conservative approximation for traffic evaluation. It is a decomposition method involving a set of fixed-point equations which are solved iteratively until the Kuhn-Tucker conditions are met. The authors investigate the convergence of the method and find that some of the variables of the model are almost stationary after only a few iterations. This leads to some simplifications that make it suitable for large networks with minor modifications. They also investigate the optimality of adaptive routing by comparing it with the optimal routing coefficients and verify the operation of this routing in a network dimensioned for adaptive technique. A question of interest is how well an adaptive algorithm can adapt to dimensioning errors and how well it compares with the optimal routing in these situations.>

The optimal synthesis of private telecommunication networks subject to multiple nonsimultaneous demands is considered. A model is given for the multiservice network synthesis model with an accurate representation of the conversion and access costs, while maintaining a classical multicommodity flow representation of the network. This is done by increasing the original network to produce an augmented network. Two decomposition methods for solving the network synthesis problem are presented. The first one is a classical Lagrangian relaxation method and the second is a resource-decomposition-type technique. Some preliminary computational results in both cases are presented. These show that the two methods converge within reasonable computation times. The results also demonstrate that the multihour aspect of the synthesis of multiservice networks should be taken into account in order to realize fully the economies that are possible due to the noncoincidence of different types of demands.>

The classical ECCS method for dimensioning hierarchical telephone networks is extended to the multihour case. The problem is reformulated as a nonlinear optimization method, and the Kuhn-Tucker equations are derived. It is shown why the ECCS method cannot solve this multihour case. The ECCS method is presented as a solution technique for the Lagrangian relaxation of the multihour problem in which subgradient techniques are used for the solution of the dual. A numerical algorithm implementing these ideas is described that can handle networks with arbitrary hierarchies and allows time-of-day routing changes. Preliminary numerical results of the method are presented, showing that the multihour algorithm can reduce a network's cost when compared to currently used methods.>

An algorithm is proposed for obtaining conservative estimates for the end-to-end blocking probability of networks operating with residual capacity adaptive routing. Two important requirements are that it should be fast enough for use within an iterative network design procedure and have an accuracy sufficient for that purpose. The algorithm is based on the assumption that the stationary behavior of residual capacity adaptive routing can be adequately modeled by a nonadaptive routing with suitably chosen parameters. An algorithm is proposed for the stationary version that is stable and fast but overestimates the blocking. A number of modifications of the model to improve its accuracy are examined. It is concluded that the model can be used for network design if a conservative solution is acceptable.>

A model for computing the blocking probability in circuitswitched networks operating with trunk reservation is extended to the case of noninteger trunk numbers. This generalization is required if the model is to be used in network optimization algorithms, which are generally evaluated over the reals. A simple extension is first presented, and shown to be numerically unstable over some values of the parameters. A recursive approach is then explained that is both robust and efficient for an integer number of reserved trunks and arbitrary parameters. The model is finally extended to arbitrary trunk numbers, and an efficient and robust algorithm is proposed.

Nonhierarchical alternate routing is the simplest extension to the hierarchical routing currently used in telephone networks. In order to evaluate the merits of such a technique, it is necessary to be able to optimize some performance measure over the routing variables. In a first step, a short discussion is presented of the evaluation algorithms used for computing the end-to-end blocking probabilities in networks operating under nonhierarchicai alternate routings. Then the results of a statistical sampling of the routing space for a small network are presented, to illustrate important characteristics of the routing problem. Next, two heuristic optimization techniques are discussed, one based on classical steepest descent and the other inspired from classical routing optimization of traffic flows in transportation and communication networks. Acceleration techniques are discussed in both cases, and the convergences rates of the alorgithms are presented for a number of networks. A brief discussion is finally given of the usefulness of nonhierarchical alternate routing in reducing the blocking probability in already existing networks, and in decreasing the number of trunks required to maintain a prespecified grade of service, both in real and artificially generated networks.

Recursive algorithms for the computation of the end-to-end blocking in circuit-switched networks operating under very general routing schemes have recently been proposed and implemented, but with exponential upper bounds for their running time. For certain important classes of routings, however, we show that algorithms requiring a single pass in all the route trees are sufficient and, thus, have a polynomial bound. Furthermore, we show that the computation of the appropriate link blocking probabilities is best done by a fixed point method, rather than a Newton-type algorithm. Computational experience is also presented, indicating that these algorithms are fast enough to be considered for the evaluation step of a routing optimization procedure.