Federated learning (FL) is a promising paradigm that can enable collaborative model training between vehicles while protecting data privacy, thereby significantly improving the performance of intelligent transportation systems (ITSs). In vehicular networks, due to mobility, resource constraints, and the concurrent execution of multiple training tasks, how to allocate limited resources effectively to achieve optimal model training of multiple tasks is an extremely challenging issue. In this paper, we propose a mobility-aware multi-task decentralized federated learning (MMFL) framework for vehicular networks. By this framework, we address task scheduling, subcarrier allocation, and leader selection, as a joint optimization problem, termed TSLP. For the case with a single FL task, we derive the convergence bound of model training. For general cases, we first model TSLP as a resource allocation game, and prove the existence of a Nash equilibrium (NE). Then, based on this proof, we reformulate the game as a decentralized partially observable Markov decision process (DEC-POMDP), and develop an algorithm based on heterogeneous-agent proximal policy optimization (HAPPO) to solve DEC-POMDP. Finally, numerical results are used to demonstrate the effectiveness of the proposed algorithm.

The rapid advancement of AI-generated content (AIGC) is poised to reshape content delivery, by enabling AIGC capabilities at the network edge or directly on end-user devices. This will allow content requests to be satisfied with AIGC based on prompts, rather than transmitting the original content. Each option presents unique trade-offs. On-device AIGC minimizes network traffic by transmitting only prompts, but it produces lower content quality than on-edge AIGC, which supports larger AI models. AIGC on the edge, in turn, results in lower quality than the original content. Delivering the original content requires more resource on radio access (and backhaul if not cached), while on-edge AIGC consumes computing power. To optimally exploit these trade-offs, we formulate a utility maximization problem where for each content the system can opt for the original content, on-edge AIGC, or on-device AIGC, accounting for backhaul capacity, computational resources, and radio access constraints. For this discrete optimization problem, we prove that, by applying Lagrangian multipliers to the three resource constraints, the problem relaxation can be efficiently solved to optimality. We then propose a solution approach that combines the problem relaxation with an algorithm for reaching feasible solutions of the overall problem. Simulation results demonstrate that our approach outperforms the baseline strategies and the solutions are close to the global optimum.

Federated Learning (FL) on low earth orbit (LEO) satellites represents a promising frontier for on-orbit edge intelligence. However, the inherent network dynamics and heterogeneity of datasets and resource across satellites pose challenges to efficient on-orbit FL. In this work, we model client selection and inter-satellite routing as a joint optimization problem. We derive and minimize an upper bound of the global empirical loss as the objective function, to enable fast convergence. We model the constraints of inter-satellite routing via time-varying graphs and network flow theory. We propose both exact and approximate solutions for the joint optimization problem. In addition, we formalize and prove the convergence property of our approach. Last, by simulation we demonstrate the efficiency and superiority of the proposed scheme for realistic satellite networking scenarios.

The integration of Artificial Intelligence (AI) and Internet of Things (IoT) devices has given rise to IoAT, promising transformative applications across various domains. Federated Learning (FL) and Split Learning (SL) are pivotal in harnessing the potential of IoAT, enabling decentralized model training while preserving data privacy. However, the heterogeneity and scalability challenges in IoAT environments necessitate advanced frameworks. In this paper, we introduce an integration of block-wise Neural Architecture Search (NAS) with a multi-partition SFL framework, called NASFLY. This approach uses only devices for actual model training and offers flexible scaling of model fragments to accommodate a wide range of device capabilities. In particular, NASFLY allows devices to utilize idle periods during the lengthy SFL forward and backward propagation phases. This is achieved by employing auxiliary model components dispatched from the server to conduct local supernet elastification using the device’s local dataset. Our method alternates between SFL for backbone network optimization and the local supernet elastification within NAS, where knowledge from the backbone network is transferred to the local supernet branches using distillation techniques. We also propose a device clustering algorithm to further improve training efficiency. Our experimental results demonstrate that this methodology significantly enhances device utilization and improves training efficiency compared with the conventional SFL.

Passively cooled base stations (PCBSs) offer low deployment cost and energy consumption for the next generation networks. By its nature, however, dealing with the thermal issue becomes crucial. For an outdoor PCBS, a major challenge is that the heat dissipation is uncertain over time. We address this online temperature scheduling problem with uncertain parameters via adjustable robust optimization (ARO) embedded into a re-optimization framework. In each optimization instance, temperature pre-scheduling is done to achieve solution robustness, looking ahead into forthcoming time slots. The solution is adaptive with respect to the gradually realized heat dissipation. Interestingly, we prove that the robust temperature pre-scheduling problem can be addressed via solving a compact linear program (LP), even though the number of possible realizations of heat dissipation is infinite. Simulation results show that our algorithm achieves robustness as well as very good average performance.

Passively cooled base stations (PCBSs) are highly relevant for achieving better efficiency in cost and energy. However, dealing with the thermal issue via load management, particularly for outdoor deployment of PCBS, becomes crucial. This is a challenge because the heat dissipation efficiency is subject to (uncertain) fluctuation over time. Moreover, load management is an online decision-making problem by its nature. In this paper, we demonstrate that a reinforcement learning (RL) approach, specifically Soft Actor-Critic (SAC), enables to make a PCBS stay cool. The proposed approach has the capability of adapting the PCBS load to the time-varying heat dissipation. In addition, we propose a denial and reward mechanism to mitigate the risk of overheating from the exploration such that the proposed RL approach can be implemented directly in a practical environment, i.e., online RL. Numerical results demonstrate that the learning approach can achieve as much as 88.6% of the global optimum. This is impressive, as our approach is used in an online fashion to perform decision-making without the knowledge of future heat dissipation efficiency, whereas the global optimum is computed assuming the presence of oracle that fully eliminates uncertainty. This paper pioneers the approach to the online PCBSs load management problem.

In multi-access edge computing (MEC) systems, there are multiple local cache servers caching contents to satisfy the users’ requests, instead of letting the users download via the remote cloud server. In this paper, a multi-cell content scheduling problem (MCSP) in MEC systems is considered. Taking into account jointly the freshness of the cached contents and the traffic data costs, we study how to schedule content updates along time in a multi-cell setting. Different from single-cell scenarios, a user may have multiple candidate local cache servers, and thus the caching decisions in all cells must be jointly optimized. We first prove that MCSP is NP-hard, then we formulate MCSP using integer linear programming, by which the optimal scheduling can be obtained for small-scale instances. For problem solving of large scenarios, via a mathematical reformulation, we derive a scalable optimization algorithm based on repeated column generation. Our performance evaluation shows the effectiveness of the proposed algorithm in comparison to an off-the-shelf commercial solver and a popularity-based caching.

Content caching at the network edge is an effective way of mitigating backhaul load and improving user experience. Caching efficiency can be enhanced by content recommendation and by keeping the information fresh. By content recommendation, a requested content that is not in the cache can be alternatively satisfied by a related cached content recommended by the system. Information freshness can be quantified by age of information (AoI). This article has the following contributions. First, we address optimal scheduling of cache updates for a time-slotted system accounting for content recommendation and AoI, and to the best of our knowledge, there is no work that has jointly taken into account these aspects. Next, we rigorously prove the problem's NP-hardness. Then, we derive an integer linear formulation, by which the optimal solution can be obtained for small-scale scenarios. On the algorithmic side, our contributions include the development of an effective algorithm based on Lagrangian decomposition, and efficient algorithms for solving the resulting subproblems. Our algorithm computes a bound that can be used to evaluate the performance of any suboptimal solution. We conduct simulations to show the effectiveness of our algorithm.

Caching popular contents at cell edge has been recognized as a promising way to facilitate rapid content delivery and alleviate backhaul burden. The content popularity is greatly influenced by recommendations by content providers. In this paper, we leverage this fact to jointly optimize caching and recommendation towards higher caching efficiency. We focus on both personalized and incumbent-aware recommendation. The incumbent content refers to the content that a user is currently browsing, resulted by the user's short-term interest. We model and formulate the resulting cache efficiency maximization problem subject to user satisfaction requirements. We prove the NP-hardness of the problem, and reformulate it using integer linear programming, enabling to solve optimally small-scale instances. Based on problem analysis with a graph representation, we derive three polynomial-time algorithms, where the recommendation sub-problem is solved to global optimum. Among these algorithms, the first two are based on sub-modularity, with$1-e^{-1}$approximation guarantee under mild conditions, while the last one is an alternation-based algorithm with fast convergence. Numerical results show the close-to-optimal performance of the proposed algorithms.

Performance degradation due to target deviation by, for example, drift or jitter, presents a significant issue to inter-satellite laser communications. In particular, with periodic acquisition for positioning the satellite receiver, deviation may arise in the time period between two consecutive acquisition operations. We propose a robust optimization approach to the problem. To solve the robust optimization problem, we deploy a process of alternately solving a decision maker’s problem and an adversarial problem. The former optimizes the divergence angle for a subset of the uncertainty set, whereas the latter is used to explore if the subset needs to be augmented. Simulation results show the approach leads to significantly more robust performance than using the divergence angle as if there is no deviation, or other ad-hoc schemes.

In multi-access edge computing (MEC) systems, there are several local cache servers caching contents to satisfy the users’ requests, instead of letting the users download via the remote cloud server. In this paper, a content scheduling problem (CSP) in MEC systems is considered. Taking into account jointly the freshness of the cached contents and the traffic data costs, we study how to schedule content updates along time in a multi-cell setting. Different from single-cell scenarios, a user may have multiple candidate cache servers, and thus all cells and their caching decisions must be jointly taken. We first prove that CSP is $\mathcal{N}\mathcal{P}$-hard, then we formulate CSP using integer linear programming. For problem solving, via a mathematical reformulation, we derive a column generation algorithm embedded into a rounding scheme. Our performance evaluation demonstrates that the solutions obtained are within 0.8% from global optimality.

In this article, we investigate the joint task assignment and power control problems for Device-to-Device (D2D) offloading communications with energy harvesting. Exploiting the D2D links for data offloading allows reducing the traffic load of the cellular base stations. The energy consumed by the D2D transmitters for data offloading can be compensated by energy harvesting. The main objective is to maximize the energy efficiency (EE) under energy causality and delay constraints, assuming a harvest–transmit model. Hence, the proposed model results in a nonconvex problem. We first derive an equivalent and more tractable optimization problem by exploiting nonlinear fractional programming, also known as the Dinkelbach method. We propose a layered optimization method by decoupling the EE maximization problem into power allocation and offloading assignment. The first step consists of computing the optimal power values by applying the conjugate gradient method. In the second step, the problem of the D2D pair formation for data offloading amounts to the bipartite graph matching. It can be solved to optimality using the Hungarian algorithm. Extensive simulations were performed on various network scenarios. Numerical results show that the proposed resource allocation scheme achieves remarkable improvements in terms of network EE.

The notion of age of information (AoI) has become an important performance metric in network and control systems. Information freshness, represented by AoI, naturally arises in the context of caching. We address optimal scheduling of cache updates for a time-slotted system where the contents vary in size. There is limited capacity for the cache for making updates. Each content is associated with a utility function that depends on the AoI and the time duration of absence from the cache. For this combinatorial optimization problem, we present the following contributions. First, we provide theoretical results of problem tractability. Whereas the problem is NP-hard, we prove solution tractability in polynomial time for a special case where all contents have the same size, by a reformulation using network flows. Second, we derive an integer linear formulation for the problem, of which the optimal solution can be obtained for small-scale scenarios. Next, via a mathematical reformulation, we derive a scalable optimization algorithm using repeated column generation. In addition, the algorithm computes a bound of global optimum, that can be used to assess the performance of any scheduling solution. Performance evaluation of large-scale scenarios demonstrates the strengths of the algorithm in comparison to a greedy schedule. Finally, we extend the applicability of our work to cyclic scheduling.

This paper considers the joint optimization of trajectory and beamforming of a wirelessly connected robot using intelligent reflective surface (IRS)-assisted millimeter-wave (mm-wave) communications. The goal is to minimize the motion energy consumption subject to time and communication quality of service (QoS) constraints. This is a fundamental problem for industry 4.0, where robots may have to maximize their battery autonomy and communication efficiency. In such scenarios, IRSs and mm-waves can dramatically increase the spectrum efficiency of wireless communications providing high data rates and reliability for new industrial applications.We present a solution to the optimization problem that exploits mm-wave channel characteristics to decouple beamforming and trajectory optimizations. Then, the latter is solved by a successive-convex optimization (SCO) algorithm. The algorithm takes into account the obstacles’ positions and a radio map and provides solutions that avoid collisions and satisfy the QoS constraint. Moreover, we prove that the algorithm converges to a solution satisfying the Karush-Kuhn-Tucker (KKT) conditions.

Deploying Intelligent reflecting surfaces (IRS) to enhance wireless communications is a promising technique. In this paper, we consider resource minimization in a multi-IRS-assisted multi-cell system, subject to finite user data demand. In our problem, the interference generated by a cell is not known a priori, as it depends on the resource consumption level of the cell. Therefore, the cells are highly coupled in interference, and the overall problem is non-convex. To tackle it, we first solve the single-cell problem by an algorithm based on the Majorization-Minimization method. Then, we embed this algorithm into an algorithmic framework to obtain a locally optimal solution to the multi-cell problem. Simulation results demonstrate the benefit of optimal IRS configuration in time-frequency resource utilization in the multi-cell system.

This paper proposes scheduling and power control schemes to mitigate the impact of both co-channel interference (CCI) and adjacent channel interference (ACI) on direct vehicle-to-vehicle broadcast communication. The objective is to maximize the number of vehicles that can communicate with the prescribed requirement on latency and reliability. The joint scheduling and power control problem is formulated as a mixed Boolean linear programming (MBLP) problem. A column generation method is proposed to reduce the computational complexity of the joint problem. From the joint problem, we formulate a scheduling-alone problem (given a power allocation) as a Boolean linear programming (BLP) problem and a power control-alone problem (given a schedule) as an MBLP problem. The scheduling problem is numerically sensitive due to the high dynamic range of channel values and adjacent channel interference ratio (ACIR) values. Therefore, a novel sensitivity reduction technique, which can compute a numerically stable optimal solution at the price of increased computational complexity, is proposed. Numerical results show that ACI, just as CCI, is a serious problem in direct vehicle-to-vehicle (V2V) communication due to near-far situations and hence should not be ignored, and its impact can be reduced by proper scheduling and power control.

In this technical note, we present a new theoretical result for multi-cell non-orthogonal multiple access (NOMA). For multi-cell scenarios, a so-called load-coupling model has been proposed earlier to characterize the presence of mutual interference for NOMA, and the optimization process relies on the use of fixed-point iterations across cells. One difficulty here is that the order of decoding for successive interference cancellation (SIC) in NOMA is generally not known a priori. This is because the decoding order in one cell depends on interference, which, in turn, is governed by resource usage in other cells, and vice versa. To achieve convergence, previous works have used workarounds that pose restrictions to NOMA, such that the SIC decoding order remains throughout the fixed-point iterations. As a comment to the previous works, we derive and prove the following result: The convergence is guaranteed, even if the order changes over the iterations. The result not only waives the need of previous workarounds, but also implies that a wide class of optimization problems for multi-cell NOMA is tractable, as long as that for single cell is.

In this paper, we study the problem of optimal scheduling of content placement along time in a base station with limited cache capacity, taking into account jointly the offloading effect and freshness of information. We model offloading based on popularity in terms of the number of requests and information freshness based on the notion of age of information (AoI). The objective is to reduce the load of backhaul links as well as the AoI of contents in the cache via a joint cost function. For the resulting optimization problem, we prove its hardness via a reduction from the Partition problem. Next, via a mathematical reformulation, we derive a solution approach based on column generation and a tailored rounding mechanism. Finally, we provide performance evaluation results showing that our algorithm provides near-optimal solutions.

Multi-connectivity is emerging as a promising solution to provide reliable communications and seamless connectivity for the millimeter-wave frequency range. Due to the blockage sensitivity at such high frequencies, connectivity with multiple cells can drastically increase the network performance in terms of throughput and reliability. However, an inefficient link scheduling, i.e., over and under-provisioning of connections, can lead either to high interference and energy consumption or to unsatisfied user's quality of service (QoS) requirements. In this work, we present a learning-based solution that is able to learn and then to predict the optimal link scheduling to satisfy users' QoS requirements while avoiding communication interruptions. Moreover, we compare the proposed approach with two base line methods and the genie-aided link scheduling that assumes perfect channel knowledge. We show that the learning-based solution approaches the optimum and outperforms the base line methods.

Abstract Joint scheduling and routing of data flows with deadline constraints in communication networks has been attracting research interest. This type of problem distinguishes from conventional multicommodity flows due to the presence of the time dimension. In this paper, we address a flow routing and scheduling problem with delivery deadline, where the assignment of link capacity occurs in discrete units. Discrete capacity allocation is motivated by applications in communication systems, where it is common to have a base unit of capacity (e.g., wavelength channel in optical communications). We present and prove complexity results of the problem. Next, we give an optimization formulation based on a time slicing approach, which amounts to a discretization of the time into time slices to enable to formulate the deadline constraints. We then derive an effective reformulation of the problem, via which a column generation algorithm is developed. In addition, we propose a simple and fast max‐flow‐based algorithm. We use a number of networks and traffic scenarios to study various performance aspects of the algorithms.

Link scheduling, i.e., which links should transmit together and for how long, has been and remains a cornerstone optimization problem in wireless networking. In minimum-time scheduling, the task is to minimize the amount of time before emptying the data demand residing at the source nodes. We derive a complete structural characterization of the solution that unifies and significantly extends the known results. First, we approach link scheduling with a general system model without restrictions on the shape of the achievable rate region. Then, we give and prove a solution characterization of optimality that is conceptually simple yet powerful. We demonstrate several applications of this characterization for analysis of optimality and problem tractability. Next, we consider a significant extension by including deadline constraints, under which optimal scheduling becomes much more complex. Yet, we show how our formulation yields a solution description for that problem as well.

In a cloud radio access network (C-RAN), distributed remote radio heads (RRHs) are coordinated by baseband units (BBUs) in the cloud. The centralization of signal processing provides flexibility for coordinated multipoint transmission (CoMP) of RRHs to cooperatively serve user equipments (UEs). We target enhancing UEs' capacity performance, by jointly optimizing the selection of RRHs for serving UEs, i.e., CoMP selection, and resource allocation. We analyze the computational complexity of the problem. Next, we prove that under fixed CoMP selection, the optimal resource allocation amounts to solving a so-called iterated function. Towards user-centric network optimization, we propose an algorithm for the joint optimization problem, aiming at scaling up the capacity maximally for any target UE group of interest. The proposed algorithm enables network-level performance evaluation for quality of experience.

We investigate the effect of bursty traffic in an LTE and Wi-Fi aggregation (LWA)-enabled network, where part of the LTE traffic is offloaded to Wi-Fi access points (APs) to boost the performance of LTE networks. A Wi-Fi AP maintains two queues containing data intended for the LWA-mode user and the native Wi-Fi user, and it is allowed to serve them simultaneously by using superposition coding (SC). With respect to the existing works on LWA, the novelty of our study consists of a random access protocol allowing the Wi-Fi AP to serve the native WiFi user with probabilities that depend on the queue size of the LWA-mode data. We analyze the throughput of the native Wi-Fi network, accounting for different transmitting probabilities of the queues, the traffic flow splitting between LTE and Wi-Fi, and the operating mode of the LWA user with both LTE and Wi-Fi interfaces. Our results provide fundamental insights in the throughput behavior of such aggregated systems, which are essential for further investigation in larger topologies.

Task offloading is a key component in mobile edge computing. Offloading a task to a remote server takes communication and networking resources. An alternative is device-to- device (D2D) offloading, where a task of a device is offloaded to some device having computational resource available. The latter requires that the devices are within the range of each other, first for task collection, and later for result gathering. Hence, in mobility scenarios, the performance of D2D offloading will suffer if the contact rates between the devices are low. We enhance the setup to base station (BS) assisted D2D offloading, namely, a BS can act as a relay for task distribution or result collection. However, this would imply additional consumption of wireless resource. The associated cost and the improvement in completion time of task offloading compose a fundamental trade-off. For the resulting optimization problem, we mathematically prove the complexity, and propose an algorithm using Lagrangian duality. The simulation results demonstrate not only that the algorithm has close-to-optimal performance, but also provide structural insights of the optimal trade-off.

Caching is an effective way to address the challenges due to explosive data traffic growth and massive device connectivity in fifth-generation (5G) networks. Currently, few works on caching pay attention to the impact of the time duration for which content is stored, called retention time, on caching optimization. The research on retention time is motivated by two practical issues, i.e., flash memory damage and storage rental cost in cloud networks, together giving rise to the storage cost. How to optimize caching contents taking the storage cost into consideration is a challenging problem, especially for the scenarios with cache-enabled mobile nodes. In this paper, a retention-aware caching problem (RACP) in vehicular networks is formulated, considering the impact of the storage cost. The problem's complexity analysis is provided. For symmetric cases, an optimal dynamic programming (DP) algorithm with polynomial time complexity is derived. For general cases, a low complexity and effective retention aware multi-helper caching algorithm (RAMA) is proposed. Numerical results are used to verify the effectiveness of the algorithms.

Relaying techniques for millimeter-wave wireless networks represent a powerful solution for improving the transmission performance. In this paper, we quantify the benefits in terms of delay and throughput for a random-access multi-user millimeter-wave wireless network, assisted by a full-duplex network cooperative relay. The relay is equipped with a queue for which we analyze the performance characteristics (e.g., arrival rate, service rate, average size, and stability condition). Moreover, we study two possible transmission schemes: fully directional and broadcast. In the former, the source nodes transmit a packet either to the relay or to the destination by using narrow beams, whereas, in the latter, the nodes transmit both the destination and the relay in the same timeslot by using a wider beam but with lower beamforming gain. In our analysis, we also consider the beam alignment phase that occurs every time, a transmitter node changes the destination node. We show the duration of how the beam is aligned, as well as position and a number of transmitting nodes, significantly affect the network performance. In addition, we discuss the impact of beam alignment errors and imperfect self-interference cancellation technique at the relay for full-duplex communications. Moreover, we illustrate the optimal transmission scheme (i.e., broadcast or fully directional) for several system parameters and show that a fully directional transmission is not always beneficial, but in some scenarios, broadcasting and relaying can improve the performance in terms of throughput and delay.

Towards energy savings in large-scale nonorthogonal multiple access (NOMA) networks, we investigate power and load optimization for multi-cell and multi-carrier NOMA systems in this paper. To capture the coupling relation of mutual interference among cells, firstly, we extend a load-coupling model from orthogonal multiple access (OMA) to NOMA networks. Next, with this analytical tool, we formulate the considered optimization problem in NOMA-based load-coupled systems, where optimizing load, power, and determining decoding order are the key aspects in the optimization. Theoretically, we prove that the minimum network energy consumption can be achieved by using all the time-frequency resources in each cell to deliver users' demand. To achieve the optimal load and enable efficient power optimization, we develop a power-adjustment algorithm. Numerical results demonstrate promising energy-saving gains of NOMA over OMA in large-scale cellular networks, in particular for the high-demand and resource-limited scenarios.

We address an energy-efficient scheduling problem for practical multiple-input single-output (MISO) systems with stringent execution-time requirements. Optimal user-group scheduling is adopted to enable timely and energy-efficient data transmission, such that all the users' demand can be delivered within a limited time. The high computational complexity in optimal iterative algorithms limits their applications in real-time network operations. In this paper, we rethink the conventional optimization algorithms, and embed machine-learning based predictions in the optimization process, aiming at improving the computational efficiency and meeting the stringent execution-time limits in practice, while retaining competitive energy-saving performance for the MISO system. Numerical results demonstrate that the proposed method, i.e., optimization with machine- learning predictions (OMLP), is able to provide a time-efficient and high-quality solution for the considered scheduling problem. Towards online scheduling in real-time communications, OMLP is of high computational efficiency compared to conventional optimal iterative algorithms. OMLP guarantees the optimality as long as the machine- learning based predictions are accurate.

Caching popular contents at edge devices is an effective solution to alleviate the burden of the backhaul networks. Earlier investigations commonly neglected the storage cost in caching. More recently, retention-aware caching, where both the downloading cost and storage cost are accounted for, is attracting attention. Motivated by this, we address proactive and retention-aware caching problem with the presence of user mobility, optimizing the sum of the two types of costs. More precisely, a cost-optimal caching problem for vehicle-to-vehicle networks is formulated with joint consideration of the impact of the number of vehicles, cache size, storage cost, and content request probability. This is a combinatorial optimization problem. However, we derive a stream of analytical results and they together lead to an algorithm that guarantees global optimum with polynomial-time complexity. Numerical results show significant improvements in comparison to popular caching and random caching.

Multi-connectivity is emerging as promising solution to provide reliable communications and seamless connectivity at the millimeter-wave frequency range. Due to the obstacles that cause frequent interruptions at such high frequency range, connectivity to multiple cells can drastically increase the network performance in terms of throughput and reliability by coordination among the network elements. In this paper, we propose an algorithm for the link scheduling optimization that maximizes the network throughput for multi-connectivity in millimeter-wave cellular networks. The considered approach exploits a centralized architecture, fast link switching, proactive context preparation and data forwarding between millimeter-wave access points and the users. The proposed algorithm is able to numerically approach the global optimum and to quantify the potential gain of multi-connectivity in millimeter-wave cellular networks.

Information age is a recently introduced metric to represent the freshness of information in communication systems. We investigate age minimization in a wireless network and propose a novel approach of optimizing the scheduling strategy to deliver all messages as fresh as possible. Specifically, we consider a set of links that share a common channel. The transmitter at each link contains a given number of packets with time stamps from an information source that generated them. We address the link transmission scheduling problem with the objective of minimizing the overall age. This minimum age scheduling problem (MASP) is different from minimizing the time or the delay for delivering the packets in question. We model the MASP mathematically and prove it is NP-hard in general. We also identify tractable cases as well as optimality conditions. An integer linear programming formulation is provided for performance benchmarking. Moreover, a steepest age descent algorithm with better scalability is developed. Numerical study shows that, by employing the optimal schedule, the overall age is significantly reduced in comparison to other scheduling strategies.

Modern over-the-top (OTT) applications can be accessed via Internet connections over cellular networks, possibly shared and managed by multiple mobile network operators (MNOs). The OTT service providers (OSPs) need to interact with MNOs, requesting resources for serving users of different categories and with different quality-of-service requirements. For this purpose, OSPs need OTT application flow prioritization in resource allocation, while the network resource scheduling should respect network neutrality that forbids OSP prioritization. OSPs also need to request resources periodically, according to their performance goals, i.e., grade-of-service (GoS) level (blocking probability), causing delay in flows' accommodation due to: 1) the time required for information exchange between OSPs and MNOs, affected by network congestion, and 2) the time required for flows to receive resources, affected by the number of concurrently active flows. Acknowledging the lack of OSP-oriented resource management approaches, we: 1) introduce a novel matching theoretic flow prioritization (MTFP) algorithm that respects network neutrality and 2) design analytical models that enable the thorough investigation of the GoS and delay performance in various scenarios. Our results (analytical and simulation) show that MTFP improves both metrics compared to the best effort approach, whereas its performance is affected by the number of flows and the resource allocation frequency.

Caching popular files at the user equipments (UEs) provides an effective way to alleviate the burden of the backhaul networks. Generally, popularity-based caching is not a system-wide optimal strategy, especially for user mobility scenarios. Motivated by this observation, we consider optimal caching with the presence of mobility. A cost-optimal caching problem (COCP) for device-to-device (D2D) networks is modeled, in which the impact of user mobility, cache size, and total number of encoded segments are all taken into account. The hardness of the problem is proved via a reduction from the satisfiability problem. Next, a lower-bounding function of the objective function is derived. By the function, an approximation of COCP (ACOCP) achieving linearization is obtained, which features two advantages. First, the ACOCP approach can use an off-the-shelf integer linear programming algorithm to obtain the global optimal solution, and it can effectively deliver solutions for small-scale and medium-scale system scenarios. Second, and more importantly, based on the ACOCP approach, one can derive a lower bound of global optimum of COCP, thus enabling performance benchmarking of any sub-optimal algorithm. To tackle large scenarios with low complexity, we first prove that the optimal caching placement of one user, giving other users' caching placements, can be derived in polynomial time. Then, based on this proof, a mobility aware multi-user algorithm is developed. Simulation results verify the effectivenesses of the two approaches by comparing them to the lower bound of global optimum and conventional caching algorithms.

Optimizing non-orthogonal multiple access (NOMA) in multi-cell scenarios is much more challenging than the single-cell case because inter-cell interference must be considered. Most papers addressing NOMA consider a single cell. We take a significant step in analyzing NOMA in multi-cell scenarios. We explore the potential of NOMA networks in achieving optimal resource utilization with arbitrary topologies. Towards this goal, we investigate a broad class of problems consisting of optimizing power allocation and user pairing for any cost function that is monotonically increasing in time-frequency resource consumption. We propose an algorithm that achieves global optimality for this problem class. The basic idea is to prove that solving the joint optimization problem of power allocation, user pair selection, and time-frequency resource allocation amounts to solving a so-called iterated function without a closed form. We prove that the algorithm approaches optimality with fast convergence. Numerically, we evaluate and demonstrate the performance of NOMA for multi-cell scenarios in terms of resource efficiency and load balancing.

Long Term Evolution (LTE)-Wireless Local Area Network (WLAN) Path Aggregation (LWPA) based on Multipath Transmission Control Protocol (MPTCP) has been under standardization procedure as a promising and cost-efficient solution to boost Downlink (DL) data rate and handle the rapidly increasing data traffic. This paper aims at providing tractable analysis for the DL performance evaluation of large-scale LWPA networks with the help of tools from stochastic geometry. We consider a simple yet practical model to determine under which conditions a native WLAN Access Point (AP) will work under LWPA mode to help increasing the received data rate. Using stochastic spatial models for the distribution of WLAN APs and LTE Base Stations (BSs), we analyze the density of active LWPA-mode WiFi APs in the considered network model, which further leads to closed-form expressions on the DL data rate and area spectral efficiency (ASE) improvement. Our numerical results illustrate the impact of different network parameters on the performance of LWPA networks, which can be useful for further performance optimization.

Caching popular files at user equipments (UEs) provides an effective way to alleviate the burden of the backhaul networks. Generally, popularity based caching is not a system-wide optimal strategy, especially for mobility scenarios. Motivated by this observation, an optimal caching problem with respect to user mobility is investigated. To be specific, a cost-optimal caching problem (COCP) for device-to-device (D2D) networks is formulated, in which the impact of user mobility, cache size, and total number of encoded file segments are considered. Compared with the related studies, our investigation guarantees that the collected segments are non-overlapping, takes into account the cost of downloading from the network, and provides a rigorous complexity analysis. For problem solving, we first prove that the optimal caching placement of one user, giving other users' caching placements, can be derived in polynomial time. Then, based on this proof, a fast yet effective caching placement algorithm for all users is developed. Simulation results verify the effectiveness of this algorithm by comparing it to conventional caching algorithms.

Non-orthogonal multiple access (NOMA) allows multiple users to simultaneously access the same time-frequency resource by using superposition coding and successive interfer- ence cancellation (SIC). Thus far, most papers on NOMA have focused on performance gain for one or sometimes two base stations. In this paper, we study multi-cell NOMA and provide a general framework for user clustering and power allocation, taking into account inter-cell interference, for optimizing resource allocation of NOMA in multi-cell networks of arbitrary topology. We provide a series of theoretical analysis, to algorithmically en- able optimization approaches. The resulting algorithmic notion is very general. Namely, we prove that for any performance metric that monotonically increases in the cells' resource consumption, we have convergence guarantee for global optimum. We apply the framework with its algorithmic concept to a multi-cell scenario to demonstrate the gain of NOMA in achieving significantly higher efficiency.

We consider link scheduling in wireless networks for emptying the queues at the transmitters in minimum time, with time constraints, or deadlines, for one or multiple individual links. We formulate the minimum-time scheduling problem with deadlines (MTSD) mathematically and derive the optimal activation order of the link sets in a schedule solution. Theoretical results are obtained, showing that the MTSD can be treated as the conventional minimum-time scheduling problem by “absorbing” the deadline constraints into the rate region where the scheduling problem is defined. By this approach, optimality characterization and geometric interpretation for the MTSD are provided. Furthermore, we extend the results to the MTSD in a general form that accommodates an arbitrary rate region.

Device-to-device (D2D) multicast transmission is an important feature for group-oriented applications. In this paper, we propose a joint channel allocation and power control scheme for the D2D multicast underlay communications. In single-rate multicast, the achieved data rate is determined by the weakest link. Therefore, we formulate this MINLP problem as a maximin optimization problem to guarantee fairness of different multicast groups. Each D2D group can reuse the channel of all cellular users. In order to limit the impact of D2D communications on cellular users' quality of service (QoS), we define an SINR threshold value for the cellular users. The non-linear Perron-Frobenius theory is used to derive a deterministic algorithm for solving the non-convex non-linear fair power control problem. A novel-genetic-algorithm-aided efficient scheme is then proposed to solve the combinatory issue of the joint channel allocation and power control. The proposed scheme is evaluated by using extensive simulations. Numerical results highlight the performance of our approach in terms of sum rate fairness.

The rapid growth in the number and variety of connected devices requires 5G wireless systems to cope with a very heterogeneous traffic mix. As a consequence, the use of a fixed transmission time interval (TTI) during transmission is not necessarily the most efficacious method when heterogeneous traffic types need to be simultaneously serviced. This work analyzes the benefits of scheduling based on exploiting scalable TTI, where the channel assignment and the TTI duration are adapted to the deadlines and requirements of different services. We formulate an optimization problem by taking individual service requirements into consideration. We then prove that the optimization problem is NP-hard and provide a heuristic algorithm, which provides an effective solution to the problem. Numerical results show that our proposed algorithm is capable of finding near-optimal solutions to meet the latency requirements of mission critical communication services, while providing a good throughput performance for mobile broadband services.

Communications using frequency bands in the millimeter-wave range can play a key role in future generations of mobile networks. By allowing large bandwidth allocations, high carrier frequencies will provide high data rates to support the ever-growing capacity demand. The prevailing challenge at high frequencies is the mitigation of large path loss and link blockage effects. Highly directional beams are expected to overcome this challenge. In this paper, we propose a stochastic model for characterizing beam coverage probability. The model takes into account both line-of-sight and first-order non-line-of-sight reflections. We model the scattering environment as a stochastic process and we derive an analytical expression of the coverage probability for any given beam. The results derived are validated numerically and compared with simulations to assess the accuracy of the model.

Cloud-based Radio Access Network (C-RAN) is a promising architecture for future cellular networks, in which Baseband Units (BBUs) are placed at a centralized location, with capacity-constrained fronthaul connected to multiple distributed Remote Radio Heads (RRHs) that are far away from the BBUs. The centralization of signal processing enables the flexibility for coordinated multi-point transmission (CoMP) to meet high traffic demand of users. We investigate how to jointly optimize CoMP-cell selection and base station resource allocation so as to enhance the quality of service (QoS), subject to the fronthaul capacity constraint in orthogonal frequency-division multiple access (OFDMA) based C-RAN. The problem is proved to be NP-hard in this paper. To deal with the computational complexity, we derive a partial optimality condition as the foundation for designing a cell-selection algorithm. Besides, we provide a solution method of the optimum of the time-frequency resource allocation problem without loss of fairness on the QoS enhancement of all users. The simulations show good performance of the proposed algorithms for jointly optimizing the cell selection and resource allocation in a C-RAN, with respect to QoS.

We address the maximum link activation problem in wireless networks with new features, namely when the transmitters can perform cooperative transmission, and the receivers are able to perform successive interference cancellation. In this new problem setting, which transmitters should transmit and to whom, as well as the optimal cancellation patterns at the receivers, are strongly intertwined. We present contributions along three lines. First, we provide a thorough tractability analysis, proving the NP-hardness as well as identifying tractable cases. Second, for benchmarking purposes, we deploy integer linear programming for achieving global optimum using off-the-shelf optimization methods. Third, to overcome the scalability issue of integer programming, we design a suboptimal but efficient optimization algorithm for the problem in its general form, by embedding maximum-weighted bipartite matching into local search. Numerical results are presented for performance evaluation, to validate the benefit of cooperative transmission and interference cancellation for maximum link activation, and to demonstrate the effectiveness of the proposed algorithm.

We extend the problem of optimizing user association for load balancing in cellular networks along 2-dimensions. First, we consider joint transmission, which is one of the coordinated multipoint techniques with which a user may be simultaneously served by multiple base stations. Second, we account for, mathematically, the coupling relation between the base stations' load levels that are dependent on each other due to inter-cell interference. We formulate two optimization problems, sum load minimization (MinSumL) and maximum load minimization (MinMaxL). We prove that both MinSumL and MinMaxL are NP-hard. We propose a mixed integer linear programming based scheme by means of linearization. This approach also leads to a bounding scheme for performance benchmarking. Then, we derive a set of partial optimality conditions. Fulfillment of the conditions will guarantee performance improvement for both MinSumL and MinMaxL. A solution algorithm is then derived based on the conditions. Simulation results are provided to demonstrate the effectiveness of the approaches.

Freshness of information is of critical importance for a host of applications of wireless communications. In order to deliver information from multiple sources in a timely and fair fashion through a wireless channel, we propose optimizing the link scheduling strategy in respect of age of information, which is a newly introduced metric that measures how fresh information is. Specifically, we consider a set of co-channel links, each having a number of packets to be delivered, and address the problem that aims to find the optimal scheduling solution, such that the maximum peak age of information is minimized. We mathematically formulate this so-called min-max peak age scheduling problem (MPASP), and prove it is NP-hard. Theoretical insights including tractable cases and optimality properties are derived. For problem solution, an integer linear programming (ILP) formulation is proposed. We also develop a sub-optimal, but fast, algorithm to solve the problem with better scalability. Numerical study shows that, by employing the optimal schedule, the maximum peak age is significantly reduced in comparison to other classic scheduling strategies such as minimum-time scheduling.

Dynamic spectrum sensing and opportunistic access in cognitive communications enable secondary users to recognize and utilize the white spaces of the licensed bandwidth. Our prior work proposed a non-uniform scheme of bandwidth partition and traffic allocation with the aim of regularizing the primary user's (PU's) bandwidth occupancy pattern, which was able to improve the performance of the secondary user (SU). In the current paper, we study the non-uniform scheme under fading situations. The optimal bandwidth allocation under fading situations is defined as maximizing the spare capacity for the SU subject to satisfying the PU's demand. The problem is proved to be NP-hard. To lower the computational overhead, we further study the problem of maximizing the spare subcarriers for the SU, and propose an optimal algorithm for the PU traffic allocation with polynomial time complexity. By numerical simulations, we demonstrate that the algorithm is able to achieve almost identical performance to that of the optimal solution of the original problem. In addition, the non-uniform scheme, which is based on that algorithm, exhibits better performance than the uniform one even under fading situations.

We consider an energy minimization problem for cooperative LTE networks. To reduce energy consumption, we investigate how to jointly optimize the transmit power and the association between cells and user equipments (UEs), by taking into consideration joint transmission (JT), one of the coordinated multipoint (CoMP) techniques. We formulate the optimization problem mathematically. For solving the problem, a dynamic power allocation algorithm that adjusts the transmit power of all cells, and an algorithm for optimizing the cell-UE association, are proposed. The two algorithms are iteratively used in an algorithmic framework to enhance the energy performance. Numerically, the proposed algorithms can lead to lower energy consumption than the optimal energy setting in the non-JT case. In comparison to fixed power allocation in JT, the proposed dynamic power allocation algorithm is able to significantly reduce the energy consumption.

We consider link scheduling in wireless networks for emptying the queues of the source nodes, and provide a unified mathematical formulation that accommodates all meaningful settings of link transmission rates and network configurations. We prove that, any scheduling problem is equivalent to solving a convex problem defined over the convex hull of the rate region. Based on the fundamental insight, a general optimality condition is derived, that yields a unified treatment of optimal scheduling. Furthermore, we demonstrate the implications and usefulness of the result. Specifically, by applying the theoretical insight to optimality characterization and complexity analysis of scheduling problems, we can both unify and extend previously obtained results.

In wireless powered communication networks (WPCNs), each user node, e.g., wireless powered sensor, is capable of either harvesting energy from a power station or transmitting data to a sink node. In the previous works, time division multiple access (TDMA) is typically used for transmission scheduling in WPCNs, that is, only one node can transmit data in one time slot. The spectrum efficiency is therefore limited by this orthogonality in time-domain scheduling. In this paper, to maximize the throughput in WPCNs, we present a new scheduling approach for energy harvesting and data transmission. Unlike TDMA, we consider that multiple nodes can simultaneously transmit their data in the same time slot, and the signals are separated at the sink node by performing successive interference cancellation (SIC). We formulate the throughput maximization problem as a linear programming problem. For solving the large scale instances, we design an algorithmic framework based on column generation. Numerical results demonstrate that compared to the TDMA based scheduling approach, substantial throughput improvement is achieved by the proposed algorithm.

There is a growing interest in age of information, which is a newly introduced metric that measures the freshness of information in communication systems. We investigate the age of information in wireless networks and propose the novel approach of optimizing the scheduling strategy to deliver the information as timely as possible. We consider a set of links that share a common channel, each containing a number of packets with time stamps, and address the scheduling problem with the objective of minimizing the overall information age. We model this problem mathematically and prove it is NP-hard in general. Fundamental insights including tractable cases and optimality conditions are presented. An integer linear programming formulation is provided for performance benchmarking. Moreover, a steepest age decent algorithm with better scalability is developed. Numerical study shows that, by employing the optimal schedule, the overall information age is significantly reduced in comparison to other scheduling strategies.

Internet-of-Things (IoT) devices can be equipped with multiple heterogeneous network interfaces. An overwhelmingly large amount of services may demand some or all of these interfaces' available resources. Herein, we present a precise mathematical formulation of assigning services to interfaces with heterogeneous resources in one or more rounds. For reasonable instance sizes, the presented formulation produces optimal solutions for this computationally hard problem. We prove the NP-completeness of the problem and develop two algorithms to approximate the optimal solution for big instance sizes. The first algorithm allocates the most demanding service requirements first, considering the average cost of interfaces' resources. The second one calculates the demanding resource shares and allocates the most demanding of them first by choosing randomly among equally demanding shares. Finally, we provide simulation results giving insight into services splitting over different interfaces for both cases.

A promising multi-user access scheme, non-orthogonal multiple access (NOMA) with successive interference cancellation (SIC), is currently under consideration for 5G systems. NOMA allows more than one user to simultaneously access the same frequency-time resource and separates multi-user signals by SIC. These render resource optimization in NOMA different from orthogonal multiple access. We provide theoretical insights and algorithmic solutions to jointly optimize power and channel allocation in NOMA. We mathematically formulate NOMA resource allocation problems, and characterize and analyze the problems' tractability under a range of constraints and utility functions. For tractable cases, we provide polynomial-time solutions for global optimality. For intractable cases, we prove the NP-hardness and propose an algorithmic framework combining Lagrangian duality and dynamic programming to deliver near-optimal solutions. To gauge the performance of the solutions, we also provide optimality bounds on the global optimum. Numerical results demonstrate that the proposed algorithmic solution can significantly improve the system performance in both throughput and fairness over orthogonal multiple access as well as over a previous NOMA resource allocation scheme.

Deploying direct device-to-device (D2D) links is a promising technology for vehicle-to-X (V2X) applications. However, intracell interference, along with stringent requirements on latency and reliability, are challenging issues. In this paper, we study the radio resource management problem for D2D-based safety-critical V2X communications. We first transform the V2X requirements into the constraints that are computable using slowly varying channel state information only. Secondly, we formulate an optimization problem, taking into account the requirements of both vehicular users (V-UEs) and cellular users (C-UEs), where resource sharing can take place not only between a V-UE and a C-UE but also among different V-UEs. The NP-hardness of the problem is rigorously proved. Moreover, a heuristic algorithm, called Cluster-based Resource block sharing and pOWer allocatioN (CROWN), is proposed to solve this problem. Finally, simulation results indicate promising performance of the CROWN scheme.

Non-orthogonal multiple access (NOMA) with successive interference cancellation (SIC), is considered as a candidate multi-user access scheme for 5G cellular systems. In this paper, we provide theoretical insights and solution algorithm for optimizing multi- user power and channel allocation in NOMA systems. We mathematically formulate the NOMA resource allocation problem and prove its NP-hardness. For solving the problem, we propose an algorithm combining Lagrangian duality and dynamic programming to deliver a competitive suboptimal solution. Numerical results demonstrate that the proposed algorithmic solution can significantly improve the system performance over orthogonal frequency division multiple access (OFDMA) as well as over other existing NOMA resource allocation scheme.

In cognitive communication, dynamic sensing and opportunistic accessing enable secondary users to recognize and utilize the white spaces of the licensed bandwidth. Most present efforts focus on designing smarter channel sensing and access algorithms for secondary users to optimize the overall throughput and bandwidth utilization efficiency, without interfering with primary users' communication. However, the transmission of the primary users are basically random and unpredictable, which usually makes the cognitive process complex and ineffective. In this paper, a non-uniform bandwidth allocation scheme is proposed, in order to regularize primary users' bandwidth occupancy, which can in turn improve the sensing efficiency and throughput of the secondary users. The performance benefits are demonstrated analytically and verified by numerical simulations. In comparison to the conventional uniform bandwidth allocation scheme, the non-uniform scheme shows a higher sensing efficiency and spectrum utilization due to less bandwidth loss and lower sensing cost.

The problem of scheduling transmission in single hop and multi-hop wireless networks with arbitrary topology under the physical interference model has been extensively studied. The focus has been on optimizing the efficiency of transmission parallelization through a minimum-frame-length schedule that meets a given set of traffic demands using the smallest number of time slots, each of which is associated with a set of compatible (according to the interference model) transmissions. This approach maximizes the resource reuse efficiency, but in general does not correspond to the best performance in terms of end-to-end packet delivery delay for multiple source-destination pairs, due to the inherent restriction of frame periodicity. In this paper, we study the problem of scheduling to minimize the end-to-end delay in wireless networks under the Signal to Interference plus Noise Ratio (SINR) constraints, and propose two schemes. The first scheme extends the minimum-frame-length approach with a phase of time slot ordering to account for the delay metric. The second scheme directly optimizes delay without the constraint of periodic framing. We propose novel mixed integer programming models for the two schemes and study their properties and complexity. Moreover, we present an efficient heuristic method that provides good quality solutions time-efficiently.

As one of the Coordinated Multipoint (CoMP) techniques, Joint Transmission (JT) can improve the overall system performance. In this paper, from the load balancing perspective, we study how the maximum load can be reduced by optimizing JT pattern that characterizes the association between cells and User Equipments (UEs). To give a model of the interference caused by cells with different time-frequency resource usage, we extend a load coupling model, by taking into account JT. In this model, the mutual interference depends on the load of cells coupled in a non-linear system with each other. Under this model, we study a two-cell case and proved that the optimality is achieved in linear time in the number of UEs. After showing the complexity of load balancing in the general network scenario, an iterative algorithm for minimizing the maximum load, named JT-MinMax, is proposed. We evaluate JT-MinMax in a Heterogeneous Network (HetNet), though it is not limited to this type of scenarios. Numerical results demonstrate the significant performance improvement of JT-MinMax on min-max cell load, compared to the conventional non-JT solution where each UE is served by the cell with best received transmit signal.

With the densification of nodes in cellular networks, free space optic (FSO) connections are becoming an appealing low cost and high rate alternative to copper and fiber backhaul solutions for wireless communication systems. To ensure a reliable cellular backhaul, provisions for redundant disjoint paths between the nodes must be made in the design phase. This paper aims at finding a cost-effective solution to upgrade the cellular backhaul with pre-deployed optical fibers using FSO links and mirror components. Since the quality of the FSO links depends on several factors, such as transmission distance, power, and weather conditions, we adopt an elaborate formulation to calculate link reliability. We present a novel integer linear programming model to approach optimal FSO backhaul design, guaranteeing $K$-disjoint paths connecting each node pair. Next, we derive a column generation method to a path-oriented mathematical formulation. Applying the method in a sequential manner enables high computational scalability. We use realistic scenarios to demonstrate that our approaches efficiently provide optimal or near-optimal solutions, and thereby allow for accurately dealing with the trade-off between cost and reliability.

We consider a combinatorial optimization problem in passive In-Building Distributed Antenna Systems (IB-DAS) deployment for indoor mobile broadband service. These systems have a tree topology, in which a central base station is connected to a number of antennas located at tree leaves via cables represented by the tree edges. Each inner node corresponds to a power equipment, of which the available types differ in the number of output ports and/or by power gain at the ports. This paper focuses on the equipment selection problem that amounts to, for a given passive DAS tree topology, selecting a power equipment type for each inner node and assigning the outgoing edges of the node to the equipment ports. The performance metric is the power deviation at the antennas from the target values. We consider as objective function the minimization of either the total or the largest power deviation over all antennas. Our contributions are the development of exact pseudo-polynomial time algorithms and (additive) fully-polynomial time approximation schemes for both objectives. Numerical results are provided to illustrate the algorithms. We also extend some results to account for equipment cost.

We consider the problem of minimization of sum transmission energy in cellular networks where coupling occurs between cells due to mutual interference. The coupling relation is characterized by the signal-to-interference-and-noise-ratio (SINR) coupling model. Both cell load and transmission power, where cell load measures the average level of resource usage in the cell, interact via the coupling model. The coupling is implicitly characterized with load and power as the variables of interest using two equivalent equations, namely, non-linear load coupling equation (NLCE) and non-linear power coupling equation (NPCE), respectively. By analyzing the NLCE and NPCE, we prove that operating at full load is optimal in minimizing sum energy, and provide an iterative power adjustment algorithm to obtain the corresponding optimal power solution with guaranteed convergence, where in each iteration a standard bisection search is employed. To obtain the algorithmic result, we use the properties of the so-called standard interference function; the proof is non-standard because the NPCE cannot even be expressed as a closed-form expression with power as the implicit variable of interest. We present numerical results illustrating the theoretical findings for a real-life and large-scale cellular network, showing the advantage of our solution compared to the conventional solution of deploying uniform power for base stations.

In cognitive communication, dynamic sensing and opportunistic access enable secondary users to recognize and utilize the white spaces of the licensed bandwidth. Most present efforts focus on designing smarter channel sensing and access algorithms for secondary users, with the aim of optimizing the overall throughput and bandwidth utilization efficiency, under the condition of not interfering with primary users' communication. However, as the transmissions of the primary users are inherently random and unpredictable, sensing and sharing spectrum with the primary users inevitably make the cognitive process of the secondary users complex and ineffective. In this paper, a non-uniform bandwidth allocation scheme is proposed that regularizes the primary users' bandwidth occupancy pattern. The regularization is not designed to reshape the primary users's traffic, but to improve the sensing efficiency and throughput of the secondary users by optimizing the spectrum allocation. After the description of the new allocation scheme, we demonstrate its performance by theoretic analysis. Then we verify the validity of the non-uniform scheme with numerical simulations under non-fading and fading situations respectively. Through comparisons with the conventional uniform bandwidth allocation scheme, the non-uniform one shows higher sensing efficiency and better spectrum utilization due to lower sensing cost and reduced bandwidth loss.

We consider a wireless network comprising a number of cochannel (hence mutually interfering) links. We study the power control problem of maximizing the rate that all links can simultaneously support under a novel setup, where receivers have interference cancelation (IC) capabilities. The problem of allocating the transmitting power is intertwined with determining the links on which receivers can perform IC and the order of cancelations. We provide and prove the theoretical results of the problem complexity and structural properties. For the problem solution, we propose a mixed-integer linear programming framework that enables jointly determining the optimal power and the IC patterns using off-the-shelf algorithms. This allows for the accurate assessment of the potential of IC for power control. Extensive numerical results are presented for performance evaluation, demonstrating the benefit of deploying IC in power control.

Optimizing activation and deactivation of base station transmissions provides an instrument for improving energy efficiency in cellular networks. In this paper, we study the problem of performing cell clustering and setting the activation time of each cluster, with the objective of minimizing the sum energy, subject to a time constraint of serving the users' traffic demand. Our optimization framework accounts for inter-cell interference, and, thus, the users' achievable rates depend on cluster formation. We provide mathematical formulations and analysis, and prove the problem's NP hardness. For problem solution, we first apply an optimization method that successively augments the set of variables under consideration, with the capability of approaching global optimum. Then, we derive a second solution algorithm to deal with the trade-off between optimality and the combinatorial nature of cluster formation. Numerical results demonstrate that our solutions achieve more than 40% energy saving over existing schemes, and that the solutions we obtain are within a few percent of deviation from global optimum.

The 4G standard Long Term Evolution (LTE) utilizes discontinuous reception (DRX) to extend the user equipments battery lifetime. DRX permits an idle UE to power off the radio receiver for two predefined sleep period and then wake up to receive the next paging message. Two major basic power saving models proposed to data are the 3GPP ETSI model and industrial DRX model proposed by Nokia. While previous studies have investigated power saving with the 3GPP ETSI models, the industrial DRX model has not been considered for analytical studies to date. Thus, there is a need to optimize the DRX parameters in the industrial model so as to maximize power saving without incurring network reentry and packet delays. In this paper, we take an overview of various static DRX cycles of the LTE/LTE-Advanced power saving mechanisms by modelling the system with bursty packet data traffic using a semi-Markov process. Using this analytical model, we will show the tradeoff relationship between the power saving and wake-up delay performance in the industrial model.

The 4G standard Long Term Evolution (LTE) has been developed for high-bandwidth mobile access for today's data-heavy applications, consequently, a better experience for the end user. Since cellular communication is ready available, LTE communication has been designed to work at high speeds for vehicular communication. The challenge is that the protocols in LTE/LTE-Advanced should not only provide good packet delivery but also adapt to changes in the network topology due to vehicle volume and vehicular mobility. It is a critical requirement to ensure a seamless quality of experience ranging from safety to relieving congestion as deployment of LTE/LTE-Advanced become common. This requires learning how to improve the LTE/LTE-Advanced model to better appeal to a wider base and move toward additional solutions. In this paper we present a feasibility analysis for performing vehicular communication via a queueing theory approach based on a multi-server queue using real LTE traffic. A M/M/m model is employed to evaluate the probability that a vehicle finds all channels busy, as well as to derive the expected waiting times and the expected number of channel switches. Also, when a base station (eNB) becomes overloaded with a single-hop, a multi-hop rerouting optimization approach is presented.

We consider the problem of sum transmission energy minimization in a cellular network where base stations interfere with one another. Each base station has to serve a target amount of data to its set of users, by varying its power and load, where the latter refers to the average level of channel resource usage in the cell. We employ the signal-to-interference-and-noise-ratio (SINR) load-coupled model that takes into account the load of each cell. We show analytically that operating at full load is optimal to minimize sum energy. Moreover, we provide an iterative power adjustment algorithm for all base stations to achieve full load. Numerical results are obtained that corroborate the analysis and illustrate the advantage of our solution compared to the conventional solution where uniform power is used for all base stations.

In multi-cell long term evolution (LTE) networks, the load levels that represent the cells' resource consumption are coupled due to mutual interference. The coupling relation forms a non-linear system, in which one cell's load governs the interference seen by the other cells. For heterogeneous networks with shared resource, load coupling takes place within the macro cell and small cell layers, as well as across the two layers. We investigate the problem of setting cell load levels for maximizing the overall system utility, where the utility is an increasing and concave function in served traffic. The paper presents the following contributions. First, we provide and prove the problem's NP-hardness. Second, for the sub-problem of resource allocation for given cell load, we present optimality conditions and tractability, along with detailing the computation for logarithmic utility functions. Third, for the non-convex problem of optimal load selection, we provide necessary optimality conditions to guide load adjustment in seeking utility improvement. Repeatedly applying load adjustment leads to a search algorithm for load optimization. Fourth, we illustrate cell load optimization for a representative LTE heterogeneous network scenario, and highlight the impact of utility function and the range of small cells on optimal load and user throughput.

The spectrum overcrowding drives investigating solutions to increase the usage of underutilized spectrum bands, minimize redundant interference and maximize expected throughput. Cognitive radio (CR) has presented itself as an appealing technology for solutions in energy constrained devices. Within this context, this paper introduces a system structure which enhances wireless multi-interfaced objects with cognitive radio. We propose a modular architecture to imbue such multi-interfaced devices with cognitive radio features, and based on it we present numerical results which identify performance boundaries and potential energy savings for an adaptive uncoded modulation scheme. Our results show that the tradeoff between throughput and energy consumption can be leveraged satisfactorily to enhance the lifetime significantly in noisy environments.

We consider a wireless network with transmitters and receivers sharing a common channel. We study the maximum link activation (LA) problem under a novel setup, where the transmitters are able to cooperatively transmit data and the receivers have interference cancellation (IC) capabilities. In this version of LA problem, determining which transmitters should jointly transmit and to whom, as well as the proper IC patterns at receivers, to achieve the maximum number of compatible links, are intertwined. We provide and prove theoretical results related to problem complexity. From the theoretical insights, an algorithm composed by local search and bipartite matching is proposed. Numerical results are presented for performance evaluation. The results show the satisfactory performance of the algorithm and demonstrate the benefit of jointly deploying cooperative transmission and successive IC in LA.

We consider a set of transmitter-receiver pairs, or links, that share a wireless medium and address the problem of emptying backlogged queues with given initial size at the transmitters in minimum time. The problem amounts to determining activation subsets of links, and their time durations, to form a minimum-time schedule. Scheduling in wireless networks has been studied under various formulations before. In this paper, we present fundamental insights and solution characterizations that include: 1) showing that the complexity of the problem remains high for any continuous and increasing rate function; 2) formulating and proving sufficient and necessary optimality conditions of two baseline scheduling strategies that correspond to emptying the queues using one-at-a-time or all-at-once strategies; and 3) presenting and proving the tractability of the special case in which the transmission rates are functions only of the cardinality of the link activation sets. These results are independent of physical-layer system specifications and are valid for any form of rate function. We then develop an algorithmic framework for the solution to this problem. The framework encompasses exact as well as sub-optimal, but fast, scheduling algorithms, all under a unified principle design. Through computational experiments, we finally investigate the performance of several specific algorithms from this framework.

We provide a general framework for the problem of data offloading in a heterogeneous wireless network, where some demand of cellular users is served by a complementary network. The complementary network is either a small-cell network that shares the same resources as the cellular network, or a WiFi network that uses orthogonal resources. For a given demand served in a cellular network, the load, or the level of resource usage, of each cell depends in a non-linear manner on the load of other cells due to the mutual coupling of interference seen by one another. With load coupling, we optimize the demand to be served in the cellular or the complementary networks, so as to maximize a utility function. We consider three representative utility functions that balance, to varying degrees, the revenue from serving the users vs the user fairness. We establish conditions for which the optimization problem has a feasible solution and is convex, and hence tractable to numerical computations. Finally, we propose a strategy with theoretical justification to constrain the load to some maximum value, as required for practical implementation. Numerical studies are conducted for both under-loaded and over-loaded networks.

A key planning task in heterogeneous networks is to optimally plan small cell locations for capacity enhancement and offloading. In LTE systems, the cells' load levels are inherently coupled with each other in a non-linear manner because of mutual interference, which complicates the task. In this paper, we address the offloading aspect by optimally selecting, from a set of candidate locations, up to a given number of small cell sites in a deployed macro cell network, subject to the load-coupling relation between the cells. We prove that the problem is NP-hard and present computational optimization approaches. The first approach is a search algorithm targeting near-optimal solutions of deploying small cells. The second, complementary, approach aims at numerically constructing a tight linear approximation of load coupling, with a possibility of iterative refinement, to enable the use of mixed-integer linear programming to gauge optimality. The optimization concepts are illustrated using a representative LTE heterogeneous network scenario. The results demonstrate the effectiveness of the optimization approaches, and enable insights into optimal offloading with respect to traffic demand and the number of small cells.

Single carrier frequency division multiple access (SC-FDMA) has been adopted as the standard multiple access scheme for 3GPP LTE uplink. In comparison to orthogonal frequency division multiple access (OFDMA), the subcarriers assigned to each user are required to be consecutive in SC-FDMA localized scheme, which imposes more difficulties on resource allocation problem. Subject to this constraint, various optimization objectives, such as utility maximization and power minimization, have been studied for SC-FDMA resource allocation. In this paper, we focus on developing a general algorithm framework with near-optimal performance and polynomial-time complexity to maximize the total utility for SC-FDMA systems. The proposed algorithm is based on low-complexity estimation for the partial solution space. Compared with existing algorithms, simulation results show that our algorithm improves the system utility significantly and has less deviation to global optimum. In addition, the proposed algorithm framework allows a flexible trade-off between computational effort and solution performance by varying the complexity of estimation approaches.

The MESH-WISE project is aiming to address key fundamental issues in wireless mesh networking that span from fundamental performance characterization to prototyping heterogeneous-access mesh networking solutions for emergency response scenarios. In this paper we present the infrastructures that will be leveraged in this project and the latest results that have been acquired from the ones that are deployed. We further discuss the state of the art in academic and industrial resource and network management platforms and discuss how we will use existing know-how towards a centralized solution.

Optimal channel allocation is a key performance engineering aspect in single-carrier frequency-division multiple access (SC-FDMA). In SC-FDMA with localized channel assignment, the channels of each user must form a consecutive block. Subject to this constraint, various performance objectives, such as maximum utility, minimum power, and minimum number of channels, have been studied. We present a unified graph labeling algorithm for these problems, based on the structural insight that SC-FDMA channel allocation can be modeled as finding an optimal path in an acyclic graph. By this insight, our algorithm applies the concept of labeling and label domination that represent non-trivial extensions of finding a shortest or longest path. The key parameter in trading performance versus computation is the number of labels kept per node. Increasing the number ultimately enables global optimality. The algorithm's approach is further justified by its global optimality guarantee with strong polynomial-time complexity for two specific scenarios, where the input is user-invariant and channel-invariant, respectively. For the general case, we provide numerical results demonstrating the algorithm's ability of attaining near-optimal solutions.

A distributed, load-aware, joint power and frequency allocation protocol is introduced for LTE-based cellular networks, and system-level simulations are performed. Our proposed scheme aims to cooperatively limit the impact of Fractional Frequency Reuse (FFR) on the center users' throughput compared to the Reuse 1 scheme, while providing sufficient throughput for the edge users. This is achieved through an asynchronous, lightweight scheme of local message exchange between neighboring LTE eNodeBs. The proposed scheme facilitates a type of “bargain” where an overloaded sector requests permission to utilize its neighbors' edge bands for its center users at a limited set of transmit power levels. Grants are generated at each neighbor by solving a small-scale optimization problem. Using an LTE simulator we evaluate our scheme on a network with 21 sectors of varying load patterns. The proposed scheme's performance for center users is consistently improved with respect to FFR-3, while for edge users the performance degradation is controlled by a parameter we set in the optimization problems' definitions; compared to Reuse 1 edge users still have gains. Specifically, we observed up to a 46% gain in the sectors' center throughput with a cost below 9% at the edges when compared to the classic FFR scheme, while the overall system throughput goes up by up to 26% in heavily loaded scenarios.

Heterogeneous networks (HetNets) with a topology of mixed macro-cells and low-power nodes (LPNs) form an important step of capacity enhancement for LTE and LTE-A. In this paper, we present an optimization framework for load balancing in LTE HetNets, by means of cell range assignment using cell-specific offset. For any given offset setting, the resulting cell load is effectively approached via the solution of a system of non-linear equations characterizing the load-coupling relation between cells. We present a computationally efficient bounding scheme to approximate the solution of the non-linear system and provide theoretical insights into the monotonicity and convergence of the scheme. The bounding scheme is embedded into an algorithm based on the principle of design of experiments (DOE) for cell offset optimization. Simulation results demonstrate the effectiveness of the optimization process for LTE load balancing with HetNet elements.

We consider N transmitter-receiver pairs that share a wireless channel and we address the problem of obtaining a schedule for activating subsets of these links so as to empty the transmitter queues in minimum time. Our aim is to provide theoretical insights for the optimality characterization of the problem, using both a cross-layer model formulation, which takes into account the effect of interference on achievable transmission rates, as well as a collision-based model, which does not incorporate the physical layer realities into the problem. We present the basic linear programming formulation of the problem and establish that the optimal schedule need not consist of more than N subset activation frames. We then prove that the problem is NP-hard for all reasonable continuous rate functions. Finally, we obtain sufficient and/or necessary conditions for optimality in a number of special cases.

We consider the problem of constructing a shared broadcast tree (SBT) in wireless networks, such that the total power required for supporting broadcast initiated by all source nodes is minimal. In the well-studied minimum-energy broadcast (MEB) problem, the optimal tree varies by source. In contrast, SBT is source-independent, thus substantially reducing the overhead for information storage and processing. The SBT problem also differs from the range assignment problem (RAP), because the power for message forwarding in SBT, although being source-independent, depends on from which tree neighbor the message is received. We approach SBT from a computational optimization standpoint, and present a dual decomposition method applied to an optimization model that embeds multiple directed trees into a shared tree. For the dual decomposition method, some of the constraints in the model are preferably formulated implicitly. The dual decomposition scheme is coupled with a fast local search algorithm. We report computational results demonstrating the effectiveness of the proposed approach. In average, the performance gap to global optimality is less than three percent.

System-centric modeling and analysis are of key significance in planning and optimizing cellular networks. In this paper, we provide a mathematical analysis of performance modeling for LTE networks. The system model characterizes the coupling relation between the cell load factors, taking into account non-uniform traffic demand and interference between the cells with arbitrary network topology. Solving the model enables a network-wide performance evaluation in resource consumption. We develop and prove both sufficient and necessary conditions for the feasibility of the load-coupling system, and provide results related to computational aspects for numerically approaching the solution. The theoretical findings are accompanied with experimental results to instructively illustrate the application in optimizing LTE network configuration.

We consider a wireless network comprising a number of mutually-interfering links. We study the transmit power control problem that determines the egalitarian signal-to-interference-plus-noise ratio under a novel setup. Namely, we assume that the receivers have multiuser detection capability, which enables decoding and cancellation of the interference, when it is strong enough. Determining the interference terms that can be cancelled is a combinatorial problem, which is intertwined with the power control problem. We propose a mixed-integer linear programming framework that jointly solves these problems optimally, using off-the-shelf algorithms. We illustrate with a simulation result the merit of the novel approach against the conventional one that precludes interference cancellation.

A new fully decentralized dynamic fractional frequency reuse (FFR)-based scheme for cellular OFDMA networks is introduced. FFR is a technique to mitigate inter-cell interference to improve the throughput of interference-limited users on the cell edge, to the expense of the rest of the cell's users and the aggregate throughput. The proposed scheme aims to limit the FFR-incurred loss of the center users' throughput, while still providing sufficient bandwidth for the cell edge users' communication. This is done by local information sharing and distributed optimization. The resulting flexibility of frequency reuse can be especially beneficial in scenarios with non-uniform and time-varying load. The optimization task is accomplished by solving a knapsack problem in each cell, where the goal is to maximize the center throughput while maintaining acceptable degradation on the cell edge with respect to the original FFR allocation. The performance improvement resulting from the distributed and dynamic FFR scheme is demonstrated by snapshot simulations on an 81-cells network with asymmetric cell load. The proposed scheme achieves up to a 62% gain in cell-center throughput with a cost of no more than 18% at the edges when compared to the classic FFR scheme. The overall system throughput improvement ranges from 22% to 58%.

Avoiding signaling congestion in location management of cellular networks is becoming increasingly important as the population of user equipments (UEs) rapidly grows. Congestion can occur due to massive mobility of UEs behaving in a similar manner, such as the train movement scenario. In this paper, we explore the use of overlapping tracking area lists (TALs) in Long Term Evolution (LTE) networks for congestion mitigation that is not possible with the conventional tracking area concept. Each cell can use multiple and overlapping TALs, to be allocated to UEs requesting their TALs from the cell. We show that finding the optimal proportional use of TALs can be formulated as a linear program. Solving the linear program minimizes the maximum tracking area updates occurring between the cells. We present numerical results to illustrate the performance of the approach. The experiments demonstrate the effectiveness of overlapping TALs for mitigating mobility signaling congestion.

A fundamental and computationally challenging optimization task in wireless networks is to maximize the number of simultaneous transmissions, subject to signal-to-noise-and-interference ratio (SINR) requirements at the receivers. The conventional approach guaranteeing global optimality is to solve an integer programming model with explicit SINR constraints. These constraints are however numerically very difficult. We develop a new integer programming algorithm based on a much more effective representation of the SINR constraints. Computational experiments demonstrate that the new approach performs significantly better in proving optimality.

Frequency reuse is a key concept for interference mitigation and thereby enhancing cell-edge performance in OFDMA networks. Two representative strategies are Fractional Frequency Reuse (FFR) and Soft Frequency Reuse (SFR). Both divide a cell into a center zone and an edge zone, and differentiate their levels of frequency reuse. Previous work on FFR and SFR has focused on networks of relatively small size with standard hexagon-shaped cells. And dividing the cell edge frequency band into three parts has been a common practice so far. However, for real-life networks, this is inadequate because of the irregular cell layout. We consider generalized FFR and SFR schemes, where the number of sub-bands is not restricted to three, and for SFR the power ratio is variable. To find optimal sub- band allocation for the generalized schemes, we present an approach based on large-scale optimization to deal with networks with irregular cell layout. The optimization process allows us to analyze the impact of the number of sub-bands and the SFR power ratio on cell-edge performance, and thereby compare the reuse schemes. We conduct experiments on large networks with realistic radio propagations and present a thorough numerical comparison.

Reducing the overhead required for tracing mobile devices is one of the major aspects in the study of mobility management of a cellular network. The Long Term Evolution (LTE) systems give a more flexible configuration of Tracking Area (TA) design by means of Tracking Area List (TAL). Being a novel concept, TAL goes beyond the capability of the conventional TA approach. Although TAL is expected to be able to reduce the overall signaling overhead by overcoming a couple of major limitations of the conventional TA concept, how to apply TAL in large scale networks, remains unexplored. In this paper, we present a novel approach for allocating and assigning TA lists. The approach does not require any data other than what is needed for conventional TA design. We present numerical results to illustrate the approach for a realistic network of Lisbon city. The experiments demonstrate the ability of TAL in reducing the signaling overhead compared to the conventional TA concept.

Coverage planning by means of controlling cell Common Pilot Channel (CPICH) power is an important task in deploying UMTS networks. In addition to determining coverage, CPICH power heavily influences the amount of Soft Handover (SHO). Non-uniform cell CPICH power allows for significant power saving and thereby higher capacity for traffic channels. However, optimizing non-uniform CPICH is challenging in terms of computational effort, if the resulting coverage pattern is required to satisfy a desired level of SHO. We present a very fast algorithm for this planning problem. The algorithm has utilized the fact that SHO is strongly correlated with cell overlap. Using overlap as a very good approximation of SHO, the algorithm can compute a near optimal coverage pattern within a few seconds even for large networks. Next, the solution is further polished to deal with SHO accurately. Simulation results show that our solution strategy is able to perform non-uniform CPICH optimization very time-efficiently, making it possible to tackle large scale UMTS coverage planning under SHO consideration.

Soft frequency reuse (SFR) has been proposed for enhancing cell-edge performance in OFDMA networks. Previous studies of SFR have used simulations over rather small networks having hexagon-shaped cells. In this paper, we examine the expected performance gain of SFR for networks in realistic radio environments and with irregular cell patterns. We define a performance metric that allows for fast assessment of expected gain of SFR over the service area of large networks. An optimization algorithm is used to tackle the resulting frequency allocation problem. Our approach enables SFR to go beyond the conventional schemes in terms of the number of sub-bands and power setting. We provide a thorough numerical study of SFR in large scale networks and investigate the performance trade-off between cell-edge and cell-center zones to illustrate pros and cons of SFR.

Improving the tracking areas (TA) configuration over time to reduce signaling overhead is vital for location management of Long Term Evolution networks. The user location and mobility patterns have the tendency to change over time, and consequently the TA layout needs to be revised. A TA reconfiguration would cause service interruption and "cost". Hence there will always be a tradeoff between the total signaling overhead and the reconfiguration cost. In this paper a genetic algorithm together with local search are applied to this bi-objective problem. Unlike previous methods, our approach does not need to weight together the two objective functions. Instead, the algorithm is designed to deliver various Pareto-optimal solutions in a single run. Computational experiments are presented for a realistic TA planning scenario of Lisbon city. The results illustrate the ability of the approach to address the primary concern in decision making of an operator - benefit versus cost, by means of providing multiple reconfiguration choices with various levels of trade-off between the two factors.

We present and demonstrate a novel approach for automated planning of common pilot channel (CPICH) power in mobile networks with co-existing HSDPA and R99 services. CPICH power allocation greatly influences the cell coverage pattern. A conventional strategy is to uniformly allocate a constant proportion of the total power to CPICH. We study non-uniform CPICH and optimize its allocation for enhancing HSDPA performance. We focus on HSDPA performance at cell edges, where user throughput is typically very low. Our approach is based on a linear-integer mathematical model; solving the model results in a power allocation that both ensures CPICH coverage and optimizes HSDPA performance at cell edges. Moreover, the model allows for precise control of soft handover (SHO) regions for R99 service. Experimental results show that our approach yields significant enhancement of HSDPA performance at cell edges with preserved R99 SHO control.

The rapid deployment of High Speed Downlink Packet Access (HSDPA) calls for automated optimization in network planning. In this paper, we study HSDPA performance improvement by means of optimizing base station antenna configuration. We consider networks with mixed HSDPA and Release 99 (R99) services that share the power resource of the cells. We present an optimization framework to capture the relationship between antenna configuration, service coverage, power sharing between R99 and HSDPA, and HSDPA performance, taking into account the influence of cell size and user distribution on HSDPA user throughput. The cost function is targeted at improving the average HSDPA user throughput. The engine of our computational machinery is a simulated annealing algorithm that is able to search and improve antenna configurations effectively and time-efficiently. We report the benefit of our approach for a realistic planning scenario for the city of Lisbon. The experiment demonstrates that automated optimization leads to significantly better HSDPA throughput.

Abstract A multicast session in a wireless ad hoc network concerns routing messages from a source to a set of destination devices. Transmitting messages consumes energy at the source and intermediate devices of the session. Since a battery is the only energy source in many applications of wireless ad hoc networks, energy efficiency is an important performance measure of multicasting. In this paper, we present and analyze integer programming models for the problem of minimizing the total energy required by multicasting. We start from a straightforward multicommodity flow model, which is strengthened by a more efficient representation of transmission power. Further strengthening is accomplished by lifting the capacity constraints of the model. We then present cut‐based models for the problem, and prove, from a bounding standpoint, the equivalence in strength between these models and their flow‐based counterparts. By expanding the underlying graph, we show that the problem can be transformed into finding a minimum Steiner arborescence. The expanded graph arises also in the separation procedure for solving one of the cut‐based models. In addition to a theoretical analysis of the relation between various models, we perform extensive computational experiments to study the numerical strengths of these models and their efficiency in solving the problem. © 2008 Wiley Periodicals, Inc. NETWORKS, 2008

A virtual backbone forms a source-independent broadcast infrastructure in wireless ad hoc networks. Backbone formation amounts to constructing a connected dominating set (CDS) in the underlying graph. CDS construction in static networks is a well-addressed topic, whereas distributed backbone management in mobile networks has been studied to less extent. We present an algorithmic framework for managing a dynamic backbone in presence of node mobility. The framework is designed to be effective in dealing with mobility as well as in keeping backbone size small. Our approach is fully decentralized. Nodes are not required to acquire network topology information other than its local environment. All operations involved in backbone management are distributed. Moreover, the operations do not require coordination in time. As a result, decisions of joining and leaving the backbone are made locally, individually, and asynchronously at nodes. Our simulation study demonstrates the effectiveness of the framework. Even under high mobility, backbone update is satisfactorily fast to maintain backbone connectivity as well as to keep backbone size moderate

We present an algorithm for maximizing the lifetime of broadcasting over a virtual backbone in wireless ad hoc networks. The algorithm is fully distributed in performing backbone update, and its message overhead is insensitive to the update interval. Moreover, our algorithm design guarantees backbone connectivity throughout the update process. We present simulation studies to demonstrate that the algorithm can significantly prolong lifetime

In this paper we propose an effective algorithm for configuring radio base station antennas in UMTS networks and optimizing the primary common pilot channel (CPICH) transmit power. The algorithm is based on tabu search and utilizes the advantage of a problem size reduction technique which allows us to detect the most critical parts of the service area where the coverage loss probability is very sensitive to the choice of antenna configuration in neighboring cells. We report numerical results for a test network originating from a realistic planning scenario for the city of Lisbon.

Broadcasting in wireless ad hoc networks can use a virtual backbone formed by a connected dominating set (CDS). If nodes use constant and identical transmission power, energy-efficient broadcasting amounts to minimizing the size of the backbone (i.e., CDS cardinality). This is referred to as the minimum connected dominating set (MCDS) problem. We present two feasibility conditions, and show that each of the conditions is both sufficient and necessary for characterizing a CDS. The first condition yields an integer programming model, which allows us to compute an MCDS for networks of moderate size (up to 80 nodes in our experiments). The second condition leads to a class of distributed algorithms. We compare numerically the performance of this class of algorithms to that of a centralized algorithm, as well as to MCDS found using the integer programming model. Our performance evaluation suggests that the class of algorithms presented in this paper have a close-optimal performance. In addition, we highlight possible algorithm extensions to cope with timing and mobility issues.

We study minimum-energy broadcast routing in all-wireless networks. Up to now, a number of heuristics have been proposed for this NP-hard problem. Among them, the broadcast incremental power (BIP) algorithm, presented by Wieselthier et al., is most known. The contribution of our work consists of a refinement of the BIP algorithm and a novel integer programming formulation. The refined version of BIP is a natural extension of the original algorithm. The integer programming formulation allows us to compute optimal broadcast trees for networks of small size. For large-sized networks, the formulation admits the computation of a sharp lower bound to the optimal tree. We are thus able to efficiently assess the numerical performance of any heuristic algorithm for the problem. In our computational study, we compare the performance of our refined BlP algorithm to that of its original version, and examine the numerical performance of the two algorithms in terms of optimality using our integer programming model.

In WCDMA networks, the power level of the common pilot channel (CPICH) has a significant impact on the network performance. The power level of a pilot signal determines the cell size, and thereby the load of the cell. By taking into account the variation of the traffic intensity over the service area, the pilot power can be adjusted to equalize the traffic load over the cells. We present a model for load balancing in WCDMA networks, and propose an algorithm for solving the load balancing optimization problem subject to the constraint of full coverage of the service area. We report our computational experiments for the real-life WCDMA networks of Berlin and Lisbon.

In WCDMA networks, Common Pilot Channel (CPICH) signals are used by mobile terminals for channel quality estimation, cell selection, and handover. The strength of the CPICH signal determines the coverage area of the cell, impacts the network capacity, and thereby the quality of service, and is therefore a crucial parameter in network planning and optimization. Pilot power is the most important parameter that allows to control the strength of the CPICH signal. The more power is spent for pilot signals, the better coverage is obtained. On the other hand, a higher value of the pilot power level in a cell means higher pilot pollution in the network and less power available to serve user traffic in the cell. In this paper, we consider the problem of minimizing the total amount of pilot power subject to a coverage constraint. We present a basic model for pilot power optimization subject to a full coverage constraint as well as its extended version which allows us to study various coverage levels and to consider user traffic distribution over the network. We also propose an efficient algorithm that gives near-optimal solutions to the problem. We report our numerical experiments for a WCDMA network based on a planning scenario for the city of Berlin.

Abstract We consider network design and routing for Internet Protocol (IP) traffic. The design problem concerns capacity dimensioning of communication links, where the design cost consists of fixed charges and linear capacity expansion costs. The optimization problem also concerns determining the amount of traffic demand to be carried by the network and the metric used by a shortest path routing protocol. We present a novel linear mixed‐integer mathematical formulation and two heuristic solution procedures. The first heuristic uses mixed‐integer programming to generate a sequence of routing solutions. The second solution approach is a simulated annealing meta heuristic. Computational experiments for synthesized and real‐life networks show that high‐quality solutions can be obtained by both approaches. © 2003 Wiley Periodicals, Inc.

Wireless communications using ad hoc networks are receiving an increasing interest. The most attractive feature of ad hoc networks is the flexibility. The network is set up by a number of units in an ad hoc manner, without the need of any fixed infrastructure. Communication links are established between two units if the signal strength is sufficiently high. As not all pairs of nodes can establish direct links, the traffic between two units may have to be relayed through other units. This is known as the multihop functionality. Design of ad hoc networks is a challenging task. In this paper we study the problem of resource allocation with spatial TDMA (STDMA) as the access control scheme. Previous work for this problem has mainly focused on heuristics, whose performance is difficult to analyze when optimal solutions are not known. We develop, for both node-oriented and link-oriented allocation strategies, mathematical programming formulations for resource optimization. We further present a column generation approach, which, in our numerical experiments, constantly yields optimal or near-optimal solutions. Our results provide important benchmarks when evaluating heuristic on-line algorithms for resource optimization using STDMA.

The multicommodity network-flow model concerns routing of a number of commodities through a capacitated network at minimal cost. In the basic model, it is assumed that for each commodity, the flow can be routed on any path connecting its origin and its destination. In telecommunication applications, where a commodity represents a communication pair, there are often additional time-delay or reliability requirements on paths that are used for routing. These requirements may vary by communication pair, represented by different priority classes. In this paper, we extend the basic multicommodity network-flow model to include such side constraints on paths. The extended problem is NP-hard with the constrained shortest-path problem as a special case. To solve the extended model, we use a column-generation approach, in which the solution is built up successively by path generation. The side constraints are efficiently handled in the path-generation subproblem. We further discuss various enhancements of this approach. Computational results show that the column-generation approach provides an efficient way for solving the extended model, even for fairly large networks.