With the proliferation of LEO satellite communications (SatCom) serving rural areas, there is a strong interest on exploring the performance limit (e.g., throughput) with such a service. This problem is challenging due to highly dynamic satellite positions, limited satellite beams and spectrum bandwidth, and wide disparity in number of subscribers across a vast area. Most existing analytical models fail to capture real-world characteristics of operational satellite network, such as long time interval between satellite handover and polarization in transmission. This paper makes a major step in advancing this research area by formalizing an analytical framework for LEO SatCom based on real-world satellite network. Our analytical framework addresses architectural issues such as gateway service region (GSR) and scheduling problems such as satellite/beam/channel-to-cell allocation, interference issues such as co-channel interference avoidance, polarization, and performance issues such as throughput fairness. Simulation results on a real-world satellite ephemeris (Starlink) show that the optimal scheduling solution based on our analytical framework can offer 93% scheduling efficiency while satisfying all design requirements and system constraints.

To facilitate dynamic spectrum sharing, the FCC has designated certified SAS administrators to implement their own spectrum access systems (SASs) that manage the shared spectrum usage in the novel CBRS band. As a premise, different SAS servers must conduct periodic inter-SAS coordination to synchronize service states and avoid allocation conflicts. However, SAS servers may inevitably stop service for regular upgrades, crash down, or even perform maliciously that deviate from the normal routines, posing a fundamental operation security problem --- the system shall be robust against these faults to guarantee secure and efficient spectrum sharing service. Unfortunately, the incumbent inter-SAS coordination mechanism, CPAS, is prone to SAS failures and does not support real-time allocation. Recent proposals that rely on blockchain smart contracts or state machine replication mechanisms to realize fault-tolerant inter-SAS coordination require all SASs to follow a unified allocation algorithm. They however face performance bottlenecks and cannot accommodate the current fact that different SASs hold their own proprietary allocation algorithms.

Supporting ultra reliable low-latency communication (URLLC) is an extremely challenging problem, due to the excessive requirements on reliability and latency. To date, few of the existing research efforts have successfully addressed the ultra reliability problem for URLLC. This article investigates this problem through the design of a URLLC scheduler for industrial automation under the open radio access network (O-RAN) architecture. We cast the URLLC data transmission problem as a resource scheduling problem, where a set of resource blocks (RBs) from a set of O-RAN radio units (O-RUs) must be allocated to a set of user equipments (UEs) for information transmission. The challenge is to find a scheduling solution in each mini-slot (sub millisecond time scale) based on dynamic channel conditions and satisfy the ultra reliability requirement (e.g., 99.9999%, or six-nine). We present Pistis—a novel scheduler design that fully utilizes the three control loops in O-RAN. Pistis exploits channel slow fading and PHY-layer properties to reduce the search space in its design of the near-real time (near-RT) component. It further leverages GPU parallel computing in its design of the real time (RT) component, which takes into account of fast fading in channel dynamics. We implement Pistis on commercial off-the-shelf hardware and demonstrate that Pistis is able to meet the six-nine reliability requirement for 4 O-RUs, 40 RBs, and 40 UEs within 0.5 ms.

Open Radio Access Network (O-RAN) offers a new paradigm for the design and deployment of future RANs. The unique architecture of O-RAN presents two main challenges when designing a scheduler. First, it is impractical to obtain accurate and full Channel State Information (CSI) due to estimation errors and limited bandwidth of the fronthaul link between Open Radio Unit (O-RU) and Open Distributed Unit (O-DU). Second, the large-scale processing at an O-DU introduces difficulties in meeting the stringent time requirement in O-RAN, especially in the real-time (RT) control loop. To address these challenges, we propose R3—a real-time robust Multi-user, Multiple Input, Multiple Output (MU-MIMO) scheduler for O-RAN. R3 serves as a comprehensive scheduling solution encompassing RB allocation, MCS selection, and beamforming calculation. Most notably, R3 utilizes a limited number of CSI samples to offer probabilistic QoS guarantees. To meet the timing requirements of O-RAN, R3 decomposes the scheduling problem into two distinct sub-problems and integrates them into separate control loops. Moreover, each sub-problem is designed with a parallel structure, utilizing a reduced search space, and implemented on a GPU platform to accelerate the computation time. Experimental results demonstrate that R3 offers competitive throughput performance as the state-of-the-art while simultaneously fulfilling the QoS guarantees. Further, R3 meets the timing requirements of various control loops in O-RAN over a wide range of operating conditions.

An over-the-air membership inference attack (MIA) is presented to leak private information from a wireless signal classifier. Machine learning (ML) provides powerful means to classify wireless signals, e.g., for PHY-layer authentication. As an adversarial machine learning attack, the MIA infers whether a signal of interest has been used in the training data of a target classifier. This private information incorporates waveform, channel, and device characteristics, and if leaked, can be exploited by an adversary to identify vulnerabilities of the underlying ML model (e.g., to infiltrate the PHY-layer authentication). One challenge for the over-the-air MIA is that the received signals and consequently the RF fingerprints at the adversary and the intended receiver differ due to the discrepancy in channel conditions. Therefore, the adversary first builds a surrogate classifier by observing the spectrum and then launches the black-box MIA on this classifier. The MIA results (based on both simulations and over-the-air software-defined radio (SDR) experiments) show that the adversary can reliably infer signals (and potentially the radio and channel information) used to build the target classifier. Therefore, a proactive defense is developed against the MIA by building a shadow MIA model and fooling the adversary. This defense can successfully reduce the MIA accuracy and prevent information leakage from the wireless signal classifier. Moreover, this defense does not reduce the accuracy of signal classification.

An adversarial deep learning approach is presented to launch over-the-air spectrum poisoning attacks. A transmitter applies deep learning on its spectrum sensing results to predict idle time slots for data transmission. In the meantime, an adversary learns the transmitter's behavior (exploratory attack) by building another deep neural network to predict when transmissions will succeed. The adversary falsifies (poisons) the transmitter's spectrum sensing data over the air by transmitting during the short spectrum sensing period of the transmitter. Depending on whether the transmitter uses the sensing results as test data to make transmit decisions or as training data to retrain its deep neural network, either it is fooled into making incorrect decisions (evasion attack) or the transmitter's algorithm is retrained incorrectly for future decisions (causative attack). Both attacks are energy efficient and hard to detect (stealth) compared to jamming the long data transmission period, and substantially reduce the throughput. A dynamic defense is designed for the transmitter that deliberately makes a small number of incorrect transmissions (selected by the confidence score on channel classification) to manipulate the adversary's training data. This defense effectively fools the adversary (if any) and helps the transmitter sustain its throughput with or without an adversary present.

Edge computing, which sinks a large number of complex calculations into edge servers, can effectively meet the requirement of low latency and bandwidth efficiency and can be conducive to the development of the Internet of Vehicles (IoV). However, a large number of edge servers mean a big cost, especially for the 5G scenario in IoV, because of the small coverage of 5G base stations. Fortunately, coherent beamforming (CB) technology enables fast and long‐distance transmission, which gives us a possibility to reduce the number of 5G base stations without losing the whole network performance. In this paper, we try to adopt the CB technology on the IoV 5G scenario. We suppose we can arrange roadside nodes for helping transferring tasks of vehicles to the base station based on the CB technology. We first give the mathematical model and prove that it is a NP‐hard model that cannot be solved directly. Therefore, we design a heuristic algorithm for an Iterative Coherent Beamforming Node Design (ICBND) algorithm to obtain the approximate optimal solution. Simulation results show that this algorithm can greatly reduce the cost of communication network infrastructure.

In general, edge devices and edge servers in edge computing environment communicate with each other by wireless network, which put forward a high requirement for end-to-end wireless communication performance. In this paper, we propose an optimal strategy by combining the coherent beamforming (CB) technique and the successive interference cancellation (SIC) technique for improving the performance of the edge device communications. CB technique can be used for expanding the transmitter's transmitting range, while SIC technique can be used for improving the receiver's receiving ability. However, when these two techniques are used jointly, interference will occur between transmitters and receivers, which makes the CB-SIC strategy hard to be designed. We first give the mathematical model based on CB-SIC and show it is difficult to solve directly. Then, we design a heuristic algorithm called time slot loop allocation (TSLA) algorithm. TSLA is based on greedy strategy to obtain an approximate optimal solution. By using TSLA, the whole scheduling time will be divided into many time slots. In each time slot, we try to make as many edge devices as possible to transmit data to the server. These can increase the overall data throughput. In simulation, we compare CB-SIC wireless network with CB only, SIC only, and traditional multi-hop network. Simulation results show that the TSLA algorithm can improve the end-to-end communication performance in edge computing environment.

Degree-of-freedom (DoF) based models have become prevalent in studying MIMO-based wireless networks. However, most existing DoF-based models assume the channel matrix is of full-rank. Such a simplifying assumption has gradually become problematic, particularly when the number of antennas increases and the propagation environment is not close to ideal. In this paper, we address this problem by developing a general theory for the DoF-based model under general channel rank conditions. We start with a fundamental understanding on how MIMO's DoFs are consumed at each node for spatial multiplexing (SM) and interference cancellation (IC) in the presence of rank-deficient channels. Based on this understanding, we develop a DoF model that can be used for identifying the DoF region of a multi-link MIMO network and for studying DoF scheduling in MIMO networks under general channel rank conditions. Specifically, we find that for IC, shared DoF consumption at both transmit and receive nodes is critical for efficient DoF allocation. Further, we show that DoF consumption under the existing full-rank assumption is a special case of our generalized DoF model. Based on case studies, we show that the general IC model can achieve larger feasible DoF regions or improved objective values than existing unilateral IC models. The findings of this paper pave the way for future research of many-antenna networks under general channel rank conditions.

Machine learning finds rich applications in Internet of Things (IoT) networks such as information retrieval, traffic management, spectrum sensing, and signal authentication. While there is a surge of interest to understand the security issues of machine learning, their implications have not been understood yet for wireless applications such as those in IoT systems that are susceptible to various attacks due the open and broadcast nature of wireless communications. To support IoT systems with heterogeneous devices of different priorities, we present new techniques built upon adversarial machine learning and apply them to three types of over-the-air (OTA) wireless attacks, namely denial of service (DoS) attack in terms of jamming, spectrum poisoning attack, and priority violation attack. By observing the spectrum, the adversary starts with an exploratory attack to infer the channel access algorithm of an IoT transmitter by building a deep neural network classifier that predicts the transmission outcomes. Based on these prediction results, the wireless attack continues to either jam data transmissions or manipulate sensing results over the air (by transmitting during the sensing phase) to fool the transmitter into making wrong transmit decisions in the test phase (corresponding to an evasion attack). When the IoT transmitter collects sensing results as training data to retrain its channel access algorithm, the adversary launches a causative attack to manipulate the input data to the transmitter over the air. We show that these attacks with different levels of energy consumption and stealthiness lead to significant loss in throughput and success ratio in wireless communications for IoT systems. Then we introduce a defense mechanism that systematically increases the uncertainty of the adversary at the inference stage and improves the performance. Results provide new insights on how to attack and defend IoT networks using deep learning.

Social connections among network nodes have been well investigated as an additional opportunity in network design (e.g., in routing strategies and trusted networking). This paper presents a paradigm shift that explores the design and performance analysis of combining social links jointly with communication links for message delivery in wireless networks. In a combined multi-layer social and communication network, communication links are based on conventional wireless technologies (e.g., WiFi, Bluetooth) and social links are overlaid over a communication infrastructure (e.g., cellular network) that provides an alternative way for data transmission. The goal is to characterize the performance analytically when routing is designed by combining social and communication links. A distance discretization technique is applied to model the reliability and delay of message delivery. The analytical foundation is developed to analyze the end-to-end delay and success probability under various effects of persistent transmission, potential error in distance estimation, and mobility. Systematic routing strategies that employ network inference are then designed to improve the performance in different aspects, such as delivery delay, delivery success probability, and energy-saving. A network emulation testbed is implemented with actual radios and real-world social network datasets to measure the performance of a heterogeneous network with social and communication links. The results in this paper show that the integration of social links in wireless network routing as a multi-layer design leads to substantial performance improvement for delay and reliability of message delivery.

In recent years, degree-of-freedom (DoF) based models were proven to be very successful in studying MIMO-based wireless networks. However, most of these studies assume channel matrix is of full-rank. Such assumption, although attractive, quickly becomes problematic as the number of antennas increases and propagation environment is not close to ideal. In this paper, we address this problem by developing a general theory for DoF-based model under rank-deficient conditions. We start with a fundamental understanding on how MIMO's DoFs are consumed for spatial multiplexing (SM) and interference cancellation (IC) in the presence of rank deficiency. Based on this understanding, we develop a general DoF model that can be used for identifying DoF region of a multi-link MIMO network and for studying DoF scheduling in MIMO networks. Specifically, we found that shared DoF consumption at transmit and receive nodes is critical for optimal allocation of DoF for IC. The results of this paper serve as an important tool for future research of many-antenna based MIMO networks.

An adaptive rate optimization solution is presented to utilize the benefits of multiuser multiple-input multiple-output (MU-MIMO) communications in a wireless network with distributed and decentralized control that adapts to dynamic channel, interference, and traffic conditions. First, the ergodic sum rates of MIMO multiple access channel (MAC) and interference channel (IC) configurations are determined by jointly integrating the error and overhead effects due to channel estimation (training) and feedback into the rate optimization. Then, a distributed channel access protocol that leverages local information without any centralized scheduler is developed to select and activate MU-MIMO configurations with the maximum achievable sum rates depending on channel, interference, and traffic conditions. In a mobile ad hoc network (MANET), MU-MIMO is shown to provide major gains in network throughput (after accounting for the control message overhead) compared with single antenna and point-to-point (P2P) MIMO communications.

Interference neutralization (IN) is regarded as a promising interference management techniques for multi-hop wireless networks. Yet most existing results of IN are limited to two-hop networks such as the relay-aided cellular network. Little progress has been made so far in the exploration of IN in generic multi-hop (more than two hops) networks. This paper aims to bridge this gap by developing an optimization framework for IN in a generic multi-hop network with the objective of maximizing the end-to-end throughput of multiple coexisting communication sessions. We first derive a mathematical model for IN in a special one-hop network to characterize the capability of IN, and then generalize this model to a multi-hop network. Based on the IN model, we develop a cross-layer optimization framework for a multi-hop network with the objective of fully translating the benefits of IN to the end-to-end throughput of the multi-hop sessions. To evaluate the performance of IN in multi-hop networks, we compare its performance against the case where IN is not employed. Simulation results show that the use of IN can significantly (more than 50%) increase the session throughput and, more notably, the throughput gain of IN increases with the node density and traffic intensity in the network.

This paper presents a novel system, synthetic high-fidelity social media data generator (SHIELD), for generating the synthetic social media data. SHIELD jointly generates time-varying, directed and weighted interaction graph structures and topic-driven text features similar to the input social media data. A synthetic interaction graph is generated by a social network model to minimize the distance to real graph and is enhanced by adding various patterns, such as anomalies and information cascades, interaction types, and temporal dynamics. A synthetic text generator based on the$n$-gram Markov model is trained under each topic identified by topic modeling. Synthetic text and graph structures are combined through the assignment of synthetic social media entities. Extensive performance evaluation via a graph and text analysis is provided to demonstrate the statistical fidelity of large-scale synthetic data generated by SHIELD. A data evaluation exercise with human participants is executed to identify how difficult it is for a human to distinguish between tweets that were generated by SHIELD and tweets that were posted by real users. Experimental results followed by a statistical significance analysis showed that human participants cannot reliably distinguish between real and synthetic tweets.

There are different forms of uncertainty in satellite communications, including cognitive interferers, channel conditions, packet traffic, and spectrum occupancy of users across channels. In addition, delay (such as propagation delay observed over satellite links) increases spectrum uncertainty and makes spectrum sensing and spectrum access two challenging tasks. To address such challenges, this paper presents a regret minimization solution for primary user (PU) and secondary user (SU) spectrum access to satellite resources in the presence of cognitive interferers. This robust game theoretic solution supports hierarchical spectrum sharing and dynamic spectrum access over multiple channels. Users select channels for data transmission and perform power control to optimize individual utility functions that are random due to different forms of uncertainty. The proposed game engine based on regret minimization framework provides a low-complexity and fast solution compared with traditional game solutions based on expected utility maximization. Detailed numerical results evaluate throughput and delay of PUs and SUs in the presence of cognitive interferers and compare the robust game theory-enabled approach with two benchmark schemes (with and without knowledge on channel availability). To support controllable and repeatable test and evaluation with real radios, an emulation testbed is built with software-defined radios connected with a network channel emulator that generates channel, mobility, and interference effects for satellite communications. GNU Radio modules are developed for cognitive network functionalities and run on USRP N210 radios that represent SU, PU, interferer, and satellite nodes. Emulation tests validate the effectiveness of the proposed solution under real radio effects.

Underwater acoustic (UWA) networks are a key form of communications for human exploration and activities in the oceanographic space of the earth. A fundamental issue of UWA communications is large propagation delays due to water medium, which has posed a grand challenge in UWA network protocol design. Conventional wisdom of addressing this issue is to live with this disadvantage by inserting a guard interval to introduce immunity to propagation delays. Recent advances in interference alignment (IA) open up a new direction to address this issue and promise a great potential to improve network throughput by exploiting large propagation delays. In this paper, we investigate propagation delay-based IA (PD-IA) in multi-hop UWA networks. We first develop a set of simple constraints to characterize PD-IA feasible region at the physical layer. Based on the set of PD-IA constraints, we develop a distributed PD-IA scheduling algorithm to greedily maximize interference overlapping possibilities in a multi-hop UWA network. Simulation results show that the proposed PD-IA algorithm yields higher throughput than an idealized benchmark algorithm without propagation delays, indicating that large propagation delays are not adversarial but beneficial for network throughput performance.

Interference alignment (IA) is widely regarded as a promising interference management technique in wireless networks. Despite its rapid advances in cellular networks, most results of IA are limited to information-theoretic exploration or physical-layer signal design. Little progress has been made so far to advance IA in cellular networks from a networking perspective. In this paper, we aim to fill this gap by studying IA in large-scale cellular networks. For the uplink, we propose an OFDM-based IA scheme and prove its feasibility at the physical layer by showing that all data streams in the IA scheme can be transported free of interference. Based on the IA scheme, we develop a cross-layer IA optimization framework that can fully translate the benefits of IA to throughput gain in cellular networks. Furthermore, we show that the IA optimization problem in the downlink can be solved in the exactly same way as that in the uplink. Simulation results show that our OFDM-based IA scheme can significantly increase the user throughput and the throughput gain increases with user density in the network.

This paper addresses the problem of joint inference and optimization in wireless networks. An optimization framework based on information-geometric network inference is developed and implemented (using a real radio emulation testbed) with scalable solutions to infer the end-to-end rate distributions of stochastic network flows from link rate measurements. The proposed low-complexity solutions apply when the underlying network inference (network tomography) problem can be decomposed to smaller-size subproblems that are solved independently by partially inferring only the flow rates of interest. The solutions are extended to infer flow rates jointly with link loss rates when retransmissions are considered over unreliable wireless links. By using the inferred distributions of flow rates, an inference mechanism is presented to optimize the network performance. First, the distributions of flow rates are inferred from the average rate measurements on selected links. Then, the distributions of all links rates are computed from the inferred distributions of flow rates. Finally, these inference results are used with network optimization. The weighted sum of link outage probabilities is minimized by adapting power control or routing decisions in mobile wireless access. This approach is iterated between network inference and optimization, providing link outage and end-to-end throughput gains compared to static approaches with fixed network (inference and optimization) parameters. The joint network inference and optimization framework is implemented with real configurable radios and the performance is verified with hardware-in-the-loop emulation test results that are obtained with actual radio transmissions over emulated channels.

Existing spectrum sharing paradigms have set clear boundaries between the primary and secondary networks. There is either no or very limited node-level cooperation between the primary and secondary networks. In this paper, we develop a new and bold spectrum-sharing paradigm beyond the state of the art for future wireless networks. We explore network cooperation as a new dimension for spectrum sharing between the primary and secondary users. Such network cooperation can be defined as a set of policies under which different degrees of cooperation are to be achieved. The benefits of this paradigm are numerous, as they allow integrating resources from two networks. There are many possible node-level cooperation policies that one can employ under this paradigm. For the purpose of performance study, we consider a specific policy called United cooperation of Primary and Secondary (UPS) networks. UPS allows a complete cooperation between the primary and secondary networks at the node level to relay each other's traffic. As a case study, we consider a problem with the goal of supporting the rate requirement of the primary network traffic while maximizing the throughput of the secondary sessions. For this problem, we develop an optimization model and formulate a combinatorial optimization problem. We also develop an approximation solution based on a piece-wise linearization technique. Simulation results show that UPS offers significantly better throughput performance than that under the interweave paradigm.

Due to the increasing usage of cloud computing applications, it is important to minimize energy cost consumed by a data center, and simultaneously, to improve quality of service via data center management. One promising approach is to switch some servers in a data center to the idle mode for saving energy while to keep a suitable number of servers in the active mode for providing timely service. In this paper, we design both online and offline algorithms for this problem. For the offline algorithm, we formulate data center management as a cost minimization problem by considering energy cost, delay cost (to measure service quality), and switching cost (to change servers’s active/idle mode). Then, we analyze certain properties of an optimal solution which lead to a dynamic programming based algorithm. Moreover, by revising the solution procedure, we successfully eliminate the recursive procedure and achieve an optimal offline algorithm with a polynomial complexity. For the online algorithm, We design it by considering the worst case scenario for future workload. In simulation, we show this online algorithm can always provide near-optimal solutions.

This paper presents a game theoretic solution for hierarchical spectrum sharing between primary users (PUs) and secondary users (SUs) in the presence of cognitive interferers. There exist several forms of uncertainty, including channel conditions, packet traffic, and spectrum occupancy of users across channels. This uncertainty is further aggravated by delays (such as propagation delays observed over satellite links) that make spectrum-efficient communication a challenging task. A robust game theoretic framework is developed for dynamic spectrum access (DSA) management over multiple channels. Cognitive functionalities employed in the game solution include selecting channels for data transmission and performing power control at each user to sustain target rates. By considering random utility functions, the game engine based on regret minimization provides low complexity and fast solutions compared to traditional game solutions based on expected utility maximization. Detailed numerical results with comparison to benchmark schemes (the ideal case and the random case where users have perfect or no knowledge on channel availability, respectively) are provided to show the effectiveness of robust game theory-enabled approach.

Interference neutralization (IN) is an interference management technique that allows simultaneous transmission of multiple links by nullifying their mutual interference in the air via cooperation among the transmitters. Although IN has been studied from information theoretic perspective, its potential for a general multi-hop wireless network has not been explored. The goal of this paper is to understand IN in a multi-hop wireless network from networking perspective. We first establish an IN reference model. Based on this reference model, we develop a set of feasibility constraints for a subset of links to be active simultaneously. By identifying each eligible neutralization node (called neut), we study IN in a general multi-hop network and develop a set of necessary constraints to characterize neut selection, IN, and scheduling. These constraints allow us to study the performance of multi-hop networks without the need of getting involved into onerous signal design issues at the physical layer. Finally, we apply our IN model and constraints to study a throughput maximization problem and show that the use of IN can generally increase network throughput. In particular, throughput gain is most significant when the node density increases.

Network-coded cooperative communications (NC-CC) refers to the use of network coding (NC) in cooperative communications (CC). Prior studies have shown that NC has the potential to improve the performance of CC when there are multiple sessions in the wireless network. These studies were done for the case when multiple sessions are sharing a single relay node. However, how NC-CC behaves when multiple relay nodes are employed remains an open problem. In this paper, we explore this problem by analyzing the achievable rate of each session in this setting. We develop closed form formulas for the mutual information and the achievable data rate for each session. We show that prior results for a single relay is a special case of our result. Based on these findings, we then study a network optimization problem that requires joint optimization of session grouping, relay node grouping, and matching of session/relay groups. We show that this problem is NP-hard, and present a polynomial time heuristic algorithm to solve this problem. Using simulation results, we show this algorithm is highly competitive and can produce results that are near to optimality.

Interference alignment (IA) is a powerful technique to handle interference in wireless networks. Since its inception, IA has become a central research theme in the wireless communications community. Due to its intrinsic nature of being a physical layer technique, IA has been mainly studied for point-to-point or single-hop scenario. There is a lack of research of IA from a networking perspective in the context of multi-hop wireless networks. The goal of this paper is to make such an advance by bringing IA technique to multi-hop MIMO networks. We develop an IA model consisting of a set of constraints at a transmitter and a receiver that can be used to determine IA for a subset of interfering streams. We further prove the feasibility of this IA model by showing that a DoF vector can be supported free of interference at the physical layer as long as it satisfies the constraints in our IA model. Based on the proposed IA model, we develop an IA design space for a multi-hop MIMO network. To study how IA performs in a multi-hop MIMO network, we compare the performance of a network throughput optimization problem based on our developed IA design space against the same problem when IA is not employed. Simulation results show that the use of IA can significantly decrease the DoF consumption for IC, thereby improving network throughput.

Recently, a new MIMO degree-of-freedom (DoF) model was proposed to allocate DoF resources for spatial multiplexing (SM) and interference cancellation (IC) in a multi-hop network. Although this DoF model promises many benefits, it hinges upon a global node ordering to keep track of IC responsibilities among all the nodes. An open question about this model is whether its global ordering property can be achieved among the nodes in the network through distributed operations. In this paper, we explore this question by studying DoF scheduling in a multi-hop MIMO network, with the objective of maximizing the minimum throughput among a set of sessions. We propose an efficient DoF scheduling algorithm to solve it and show that our algorithm only requires local operations. We prove that the resulting DoF scheduling solution is globally feasible and show that there exists a corresponding feasible global node ordering for IC, albeit such global ordering is implicit. Simulation results show that the solution values obtained by our algorithm are relatively close to the upper bound values computed by CPLEX solver, thereby indicating that our algorithm is highly competitive.

The classical approach to interference management in wireless medium access is based on avoidance. Recently, there is a growing interest in exploiting interference (rather than avoiding it) to increase network throughput. This was made possible by a number of advances at the physical layer. In particular, the so-called successive interference cancellation (SIC) scheme appears very promising, due to its ability to enable concurrent receptions from multiple transmitters as well as interference rejection. Although SIC has been extensively studied as a physical layer technology, its research and advances in the context of multi-hop wireless network remain limited. In this paper, we aim to close this gap by offering a systematic study of SIC in a multi-hop wireless network. After gaining a fundamental understanding of SIC's capability and limitation, we propose a cross-layer optimization framework for SIC that incorporates variables at physical, link, and network layers. We use numerical results to affirm the validity of our optimization framework and give insights on how SIC behaves in a multi-hop wireless network.

Recently, degree-of-freedom (DoF)-based models have been widely used to study MIMO network performance. Existing DoF-based models differ in their interference cancellation (IC) behavior and many of them suffer from either loss of solution space or possible infeasible solutions. To overcome these limitations, a new DoF-based model, which employs an IC scheme based on node-ordering was proposed. In this paper, we apply this new DoF IC model to study a throughput maximization problem in a multihop MIMO network. The problem formulation involves joint consideration of flow routing and DoF allocation and falls in the form of a mixed-integer linear program (MILP). Our main contribution is an efficient polynomial time algorithm that offers a competitive solution to the MILP through a series of linear programs (LPs). The algorithm employs a sequential fixing framework to obtain an initial feasible solution and then improves the solution by exploiting: 1) the impact of node ordering on DoF consumption for IC at a node and 2) route diversity in the network. Simulation results show that the solutions obtained by our proposed algorithm are competitive and feasible.

The transparent coexistence (TC) paradigm allows simultaneous activation of the secondary users with the primary users as long as their interference to the primary users can be properly canceled. This paradigm has the potential to offer much more efficient spectrum sharing than the traditional interweave paradigm. In this paper, we design a distributed algorithm to achieve this paradigm for a secondary multi-hop network. For interference cancelation (IC), we employ MIMO at secondary nodes. We present a distributed iterative algorithm to maximize each secondary session's throughput while meeting all IC requirements under TC. By maintaining two local sets for each node, we can keep track of the node's IC responsibility. Although no explicit node ordering is maintained in our distributed algorithm, we prove that our distributed data structure at each node (with the use of two local sets) can be mapped to an explicit global node ordering for IC among all nodes in the network. This guarantees that each active node's degree-of-freedoms allocated for IC is feasible at the physical layer. Our algorithm is iterative in nature and all steps can be accomplished based on local information exchange among the neighboring nodes. We present the simulation results to show that the performance of our distributed algorithm is highly competitive when compared with an upper bound solution from the corresponding centralized problem.

Recent advances in MIMO degree-of-freedom (DoF)models allow us to study MIMO in a multi-hop network environment. On the other hand, successive interference cancellation (SIC) is a powerful physical layer technique used in multi-user detection. Based on the strengths and weaknesses of MIMO DoF and SIC, we propose a marriage between these two techniques so that DoF-based interference cancellation (IC) and SIC can help each other as follows: (i) SIC is exploited to decode multiple received signals to conserve DoF resources in IC, and (ii) DoFIC resolves the potential SINR barrier that SIC may encounter. In this paper, we develop the necessary mathematical models to realize the two ideas in a multi-hop wireless network. Together with scheduling and routing constraints, we develop a cross-layer optimization framework with joint DoF IC and SIC. By applying the framework on a throughput maximization problem, we find that SIC and DoF IC can indeed offer significant performance improvement by addressing each other's limitation.

Wireless energy transfer (WET) is a new technology that can be used to charge the batteries of sensor nodes without wires. Although wireless, WET does require a charging station to be brought to within reasonable range of a sensor node so that a good energy transfer efficiency can be achieved. On the other hand, it has been well recognized that data collection with a mobile base station has significant advantages over a static one. Given that a mobile platform is required for WET, a natural approach is to employ the same mobile platform to carry the base station for data collection. In this paper, we study the interesting problem of co-locating a wireless charger (for WET) and a mobile base station on the same mobile platform-the wireless charging vehicle (WCV). The WCV travels along a pre-planned path inside the sensor network. Our goal is to minimize energy consumption of the entire system while ensuring that 1) each sensor node is charged in time so that it will never run out of energy, and 2) all data collected from the sensor nodes are relayed to the mobile base station. We develop a mathematical model for this problem (OPT-t), which is time-dependent. Instead of solving OPT-t directly, we show that it is sufficient to study a special subproblem (OPT-s) which only involves space-dependent variables. Subsequently, we develop a provably near-optimal solution to OPT-s. Our results offer a solution on how to use a single mobile platform to address both WET and data collection in sensor networks.

The dominate spectrum sharing paradigm of today is interference avoidance, where a secondary network can use the spectrum only when such a use is not interfering with the primary network. However, with the advances of physical-layer technologies, the mindset of this paradigm is being challenged. This paper explores a new paradigm called “transparent coexistence” for spectrum sharing between primary and secondary nodes in a multihop network environment. Under this paradigm, the secondary network is allowed to use the same spectrum simultaneously with the primary network as long as their activities are “transparent” (or “invisible”) to the primary network. Such transparency is accomplished through a systematic interference cancelation (IC) by the secondary nodes without any impact on the primary network. Although such a paradigm has been studied in the information theory (IT) and communications (COMM) communities, it is not well understood in the wireless networking community, particularly for multihop networks. This paper offers an in-depth study of this paradigm in a multihop network environment and addresses issues such as scheduling (both in frequency channels and time slots) and IC (to/from primary network and within the secondary network). Through a rigorous modeling and formulation, problem formulation, solution development, and simulation results, we show that transparent coexistence paradigm offers significant improvement in terms of spectrum access and throughput performance as compared to the current prevailing interference avoidance paradigm.

Wireless energy transfer based on magnetic resonant coupling is a promising technology to replenish energy to a wireless sensor network (WSN). However, charging sensor nodes one at a time poses a serious scalability problem. Recent advances in magnetic resonant coupling show that multiple nodes can be charged at the same time. In this paper, we exploit this multi-node wireless energy transfer technology and investigate whether it is a scalable technology to address energy issues in a WSN. We consider a wireless charging vehicle (WCV) periodically traveling inside a WSN and charging sensor nodes wirelessly. Based on charging range of the WCV, we propose a cellular structure that partitions the two-dimensional plane into adjacent hexagonal cells. We pursue a formal optimization framework by jointly optimizing traveling path, flow routing, and charging time. By employing discretization and a novel Reformulation-Linearization Technique (RLT), we develop a provably near-optimal solution for any desired level of accuracy. Through numerical results, we demonstrate that our solution can indeed address the charging scalability problem in a WSN.

This paper models and analyzes the problem of search (navigation) with local information in combined social and wireless communication networks. Social networks are modeled with short-range and long-range connections representing small-world and scale-free network characteristics. By distinguishing the delay and success probability on different link types, the end-to-end delay distribution and success probability are first derived as functions of the social separation from the destination. New routing algorithms are then developed to improve the delay and chain completion success, and the effects of delay deadline on success probability are evaluated. The analysis is extended to the multi-layer combined social and communication network model, where wireless communication becomes the underlay to route information with the aid of social connections. The analytical results on delay and success probability are validated by comparing them with search results on a real-world social and communication network. Results of this paper show how social connections can help reduce the search delay and increase the success probability in chain completion that runs on interdependent social and wireless communication network structures.

A fundamental challenge in wireless networks is how to handle packet loss due to noise, interference, and dynamic channel effects, especially when there is no per-packet acknowledgement due to additional delay and potential loss of feedback packets. We design and implement a packet coding optimization scheme, applied at the source node, to enhance end-to-end transmission reliability in a lossy multi-hop network. Specifically, each source node transmits a file of packets to its destination node in the network where the end-to-end packet acknowledgement is not readily available because of the possible error or delay effects over multiple hops. By simply retransmitting packets, a source node cannot guarantee innovative packet arrivals at the destination node. Thus, we design an optimization scheme for adaptive packet coding applied at the source node to avoid transmitting redundant packets, thereby significantly improving the throughput, even for the case of a single unicast session. This scheme does not require any knowledge of network topology and can seamlessly operate with any routing or network coding protocol used at the intermediate relay nodes. We analyze the throughput properties of coded transmissions and verify the feasibility of performance gains via simulations. Then, we provide high fidelity emulation testbed results with real radio transmissions over emulated channels to evaluate the throughput gains. Without relying on end-to-end acknowledgment for each packet, we show that the adaptive packet coding optimization scheme can achieve significantly higher throughput than the retransmission scheme in lossy networks with unicast traffic.

Transparent coexistence, also known as underlay, offers much more efficient spectrum sharing than traditional interweave coexistence paradigm. In a previous work, the transparent coexistence for a multi-hop secondary networks is studied. In this paper, we design a distributed solution to achieve this paradigm. In our design, we show how to increase the number of data streams iteratively while meeting constraints in the MIMO interference cancelation (IC) model and achieving transparent coexistence. All steps in our distributed algorithm can be accomplished based on local information exchange among the neighboring nodes. Our simulation results show that the performance of our distributed algorithm is highly competitive when compared to an upper bound solution for the centralized problem.

Recent advances in information theory (IT) have shown great promises of interference alignment (IA) for cellular networks. However, due to a number of assumptions, these IT results cannot be directly applied to address practical problems. The goal of this paper is to fill in this gap by studying IA for cellular networks with more practical settings. We propose an IA scheme that includes constraints at each user and each base station (BS) for the uplink communication of a cellular network. We prove the feasibility of the IA scheme by constructing the encoding and decoding vectors for each data stream so that it can be transported free of interference. Based on this IA scheme, we study an uplink user throughput maximization problem and show the throughput improvement of the IA scheme over two other schemes.

Network-coded cooperative communications (NC-CC) is a new paradigm for communications in wireless networks that employs network coding (NC) to improve the performance of CC. A key problem to harness the potential of NC-CC is how to put sessions into different groups, and assign a relay node for each group. In this paper, we study this joint grouping and relay node selection problem for NC-CC. We provide a formal proof of NP-hardness for this problem. Due to NP-hardness, we propose a distributed and online algorithm and show that it offers near-optimal solution to this problem. The key idea in this algorithm is to have each neighboring relay node of a new session calculate the best local group that it can offer and advertise this information; and then to have the source node of the new session select the best local group to join among all offers. We show that our distributed algorithm has polynomial time complexity. Using extensive numerical results, we show that our distributed algorithm adapts well to online network dynamics.

The rapid advances of MIMO to date have mainly stayed at the physical layer. Such fruits have not fully benefited MIMO research at the network layer mainly due to the computational complexity associated with the matrix-based model that MIMO involves. Recently, there have been some efforts to simplify link layer model for MIMO so as to facilitate research at the upper layers. These models only require simple numeric computations on MIMO's degrees-of-freedom (DoFs) to characterize spatial multiplexing (SM) and interference cancellation (IC). Thus, these models are much simpler than the original matrix-based model from the communications world. However, achievable DoF regions of these DoF-based models are not analyzed. In this paper, we re-visit this important problem of MIMO modeling. Based on accounting of how DoFs are consumed for SM and IC, we develop a tractable link layer model for multi-hop MIMO networks. We show that under common assumptions of DoF-based models and additional assumption of no dependency cycle, this model includes all the feasible solutions by the matrix-based model under SM and IC for any network topology. This work offers an important building block for theoretical research on multi-hop MIMO networks.

This paper addresses the problem of search with local information in combined social and communication networks. Social networks are modeled with short-range and long-range connections representing small-world and scale-free network characteristics. By distinguishing the delay and success probability on different social links, the end-to-end delay distribution and success probability are derived as functions of the social separation from the destination. Also, greedy routing algorithms are developed to improve the delay and chain completion success. Then, the analysis is extended to the combined social and communication networks, where wireless communication becomes the underlay to route information with the aid of social connections. The analytical results are validated via simulated search results on a combined social and communication network. Our results show how social connections can help reduce the search delay and increase the success probability in chain completion.

Wireless energy transfer is a promising technology to fundamentally address energy and lifetime problems in a wireless sensor network (WSN). On the other hand, it has been well recognized that a mobile base station has significant advantages over a static one. In this paper, we study the interesting problem of co-locating the mobile base station on the wireless charging vehicle (WCV). The goal is to minimize energy consumption of the entire system while ensuring none of the sensor nodes runs out of energy. We develop a mathematical model for this complex problem. Instead of studying the general problem formulation (OPT-t), which is time-dependent, we show that it is sufficient to study a special subproblem (OPT-s) which only involves space-dependent variables. Subsequently, we develop a provably near-optimal solution to OPT-s. The novelty of this research mainly resides in the development of several solution techniques to tackle a complex problem that is seemingly intractable at first glance. In addition to addressing a challenging and interesting problem in a WSN, we expect the techniques developed in this research can be applied to address other related networking problems involving time-dependent movement, flow routing, and energy consumption.

Degree-of-Freedom (DoF)-based model is a simple yet powerful tool to analyze MIMO's spatial multiplexing (SM) and interference cancellation (IC) capabilities in a multi-hop network. Recently, a new DoF model was proposed and was shown to achieve the same rate region as the matrix-based model (under SM and IC). The essence of this new DoF model is a novel node ordering concept, which eliminates potential duplication of DoF allocation for IC. In this paper, we investigate DoF scheduling for a multi-hop MIMO network based on this new DoF model. Specifically, we study how to perform DoF allocation among the nodes for SM and IC so as to maximize the minimum rate among a set of sessions. We formulate this problem as a mixed integer linear programming (MILP) and develop an efficient DoF scheduling algorithm to solve it. We show that our algorithm is amenable to local implementation and has polynomial time complexity. More importantly, it guarantees the feasibility of final solution (upon algorithm termination), despite that node ordering establishment and adjustment are performed locally. Simulation results show that our algorithm can offer a result that is close to an upper bound found by CPLEX solver, thus showing that the result found by our algorithm is highly competitive.

Interference alignment (IA) is a major advance in information theory. Despite its rapid advance in the information theory community, most results on IA remain point-to-point or single-hop and there is a lack of advance of IA in the context of multi-hop wireless networks. The goal of this paper is to make a concrete step toward advancing IA technique in multi-hop MIMO networks. We present an IA model consisting of a set of constraints at a transmitter and a receiver that can be used to determine a subset of interfering streams for IA. Based on this IA model, we develop an IA optimization framework for a multihop MIMO network. For performance evaluation, we compare the performance of a network throughput optimization problem under our proposed IA framework and the same problem when IA is not employed. Simulation results show that the use of IA can significantly decrease the DoF consumption for IC, thereby improving network throughput.

There has been a growing interest to employ the so-called degree-of-freedom (DoF) based models to study multihop MIMO networks. Existing DoF-based models differ in their interference cancelation (IC) behavior and suffer from either loss of solution space or possible infeasible solutions. Recently, a DoF model based on a novel node-ordering concept was proposed to overcome the limitations of the exiting DoF models. In this paper, we apply this new DoF model to study a throughput maximization problem in a multi-hop network. The problem formulation jointly considers half duplex, node ordering, DoF consumption constraints and flow routing and is in the form of a mixed integer linear program (MILP). Our main contribution is the development of an efficient polynomial time algorithm that offers a competitive solution to the MILP through a series of linear programs (LPs). The key idea in the algorithm is to explore (i) the impact of node ordering on DoF consumption for IC at a node, and (ii) route diversity in the network while ensuring DoF constraints are satisfied at each node throughout the iterations. Simulation results show that our solutions by the proposed algorithm are competitive and feasible.

The dominant spectrum sharing paradigm of today is the interweave paradigm. This paper advocates a new and alternative paradigm called United network of Primary and Secondary networks (UPS). UPS allows a complete cooperation between primary and secondary networks at the node level to relay each other's traffic, in addition to existing dynamic spectrum access (DSA) in time, space, and frequency domains. Such cooperation allows the primary and secondary networks to access a much richer network resources from the combined network. As a case study, we consider a problem with the goal of supporting the rate requirement of the primary network traffic while maximizing the minimum throughput of the secondary sessions. For this problem, we develop an optimization model and formulate a combinatorial optimization problem. Although this problem is in the form of mixed integer linear program (MILP), we can use CPLEX to solve it efficiently. Simulation results show that the UPS paradigm offers much better throughput performance than the interweave DSA paradigm.

Wireless power transfer is a promising technology to fundamentally address energy problems in a wireless sensor network. To make such a technology work effectively, a vehicle is needed to carry a charger to travel inside the network. On the other hand, it has been well recognized that a mobile base station offers significant advantages over a fixed one. In this paper, we investigate an interesting problem of co-locating the mobile base station on the wireless charging vehicle. We study an optimization problem that jointly optimizes traveling path, stopping points, charging schedule, and flow routing. Our study is carried out in two steps. First, we study an idealized problem that assumes zero traveling time, and develop a provably near-optimal solution to this idealized problem. In the second step, we show how to develop a practical solution with non-zero traveling time and quantify the performance gap between this solution and the unknown optimal solution to the original problem.

This paper explores the so-called “transparent coexistence” paradigm for spectrum sharing between primary and secondary nodes in a multi-hop network environment. Although such paradigm has been studied in the information theory and communications communities, it is not well understood in the wireless networking community, particularly for multihop networks. Under this paradigm, a secondary network is allowed to use the same spectrum simultaneously with the primary network as long as their activities are “transparent” (or “invisible”) to the primary network. Such transparency can be accomplished through a systematic interference cancellation (IC) by the secondary nodes without any impact on the primary network. This paper offers an in-depth study of this paradigm in a multi-hop network environment and addresses issues such as channel selection, IC to/from primary network, and IC within the secondary network. Through a rigorous modeling and formulation, we develop an optimization problem under this paradigm with the objective of maximizing secondary user's throughput. Through simulation results, we show that such paradigm offers significant improvement to a multi-hop network in terms of spectrum efficiency and throughput performance as compared to the prevailing interference-avoidance paradigm.

Interference management is an important problem in wireless networks. In this paper, we focus on the successive interference cancellation (SIC) technique, and aim to design an efficient cross-layer solution to increase throughput for multi-hop wireless networks with SIC. We realize that the challenge of this problem is its mixed integer linear programming formulation, which has bunches of integer variables. In order to solve this problem efficiently, we propose an iterative framework to improve the solution for integer variables and use a linear programming to solve the problem for other variables. Our analysis indicates that the proposed algorithm is with polynomial-time complexity. Simulation results show that SIC can increase throughput of a multi-hop wireless network by around 300%.

Network throughput and energy consumption are two important performance metrics for a multihop wireless network. Current state-of-the-art research is limited to either maximizing throughput under some energy constraint or minimizing energy consumption while satisfying some throughput requirement. Although many of these prior efforts were able to offer some optimal solutions, there is still a critical need to have a systematic study on how to optimize both objectives simultaneously. In this paper, we take a multicriteria optimization approach to offer a systematic study on the relationship between the two performance objectives. To focus on throughput and energy performance, we simplify link layer scheduling by employing orthogonal channels among the links. We show that the solution to the multicriteria optimization problem characterizes the envelope of the entire throughput-energy region, i.e., the so-called optimal throughput-energy curve. We prove some important properties of the optimal throughput-energy curve. For case study, we consider both linear and nonlinear throughput functions. For the linear case, we characterize the optimal throughput-energy curve precisely through parametric analysis, while for the nonlinear case, we use a piecewise linear approximation to approximate the optimal throughput-energy curve with arbitrary accuracy. Our results offer important insights on exploiting the tradeoff between the two performance metrics.

This paper tries to reconcile the tension between the physical model and the protocol model that have been used to characterize interference relationship in a multihop wireless network. The physical model (a.k.a. signal-to-interference-and-noise ratio model) is widely considered as a reference model for physical layer behavior but its application in multihop wireless networks is limited by its complexity. On the other hand, the protocol model (a.k.a. disk graph model) is simple but there have been doubts on its validity. This paper explores the following fundamental question: How to correctly use the protocol interference model? We show that, in general, solutions obtained under the protocol model may be infeasible and, thus, results based on blind use of protocol model can be misleading. We propose a new concept called "reality check” and present a method of using a protocol model with reality check for wireless networks. Subsequently, we show that by appropriate setting of the interference range in the protocol model, it is possible to narrow the solution gap between the two models. Our simulation results confirm that this gap is indeed small (or even negligible). Thus, our methodology of joint reality check and interference range setting retains the protocol model as a viable approach to analyze multihop wireless networks.

The cost of energy consumption is an important concern for network operators. In this paper, we study an energy-related problem that focuses on network-wide energy consumption. In the first part of this work, we study how to maximize throughput under a network-wide energy constraint. We formulate this problem as a mixed-integer nonlinear program (MINLP). This formulation differs from prior efforts as it considers a non-zero device power, which complicates the problem. We propose a novel piece-wise linear approximation to transform the nonlinear constraints into linear constraints. We prove that the solution developed under this approach is near-optimal with a guaranteed performance bound. In the second part, we generalize the problem in the first part via a multicriteria optimization framework, which simultaneously optimizes throughput and total network energy. We show how weakly Pareto-optimal solutions can characterize an optimal throughput-energy curve. We offer some interesting properties of the optimal throughput-energy curves, which are useful to both network operators and end-users. Our results fill in some important gaps in the current understanding on optimizing total network energy.

Conserving network-wide energy consumption is becoming an increasingly important concern for network operators. In this work, we study network-wide energy conservation problem which we hope will offer insights to both network operators and users. In the first part of this work, we study how to maximize throughput under a network-wide energy constraint. We formulate this problem as a mixed-integer nonlinear program (MINLP). We propose a novel piece-wise linear approximation to transform the nonlinear constraints into linear constraints. We prove that the solution developed under this approach is near-optimal with guaranteed performance bound. In the second part, we generalize the problem in the first part by exploring throughput and network-wide energy optimization via a multi-criteria optimization framework. We show that the weakly Pareto-optimal points in the solution can characterize an optimal throughput-energy curve. We offer some interesting properties of the optimal throughput-energy curve which are useful to both network operators and end users.

There is a growing interest in exploiting interference (rather than avoiding it) to increase network throughput. In particular, the so-called successive interference cancellation (SIC) scheme appears very promising, due to its ability to enable concurrent receptions from multiple transmitters as well as interference rejection. Although SIC has been extensively studied as a physical layer technology, its research and advances in the context of multi-hop wireless network remain limited. In this paper, we try to answer the following fundamental questions. What are the limitations of SIC? How to overcome such limitations? How to optimize the interaction between SIC and interference avoidance? How to incorporate multiple layers (physical, link, and network) in an optimization framework? We find that SIC alone is not adequate to handle interference in a multi-hop wireless network, and advocate the use of joint SIC and interference avoidance. To optimize a joint scheme, we propose a cross-layer optimization framework that incorporates variables at physical, link, and network layers. This is the first work that combines successive interference cancellation and interference avoidance in multi-hop wireless network. We use numerical results to affirm the validity of our optimization framework and give insights on how SIC and interference avoidance can complement each other in an optimal manner.

Capacity scaling laws offer fundamental understanding on the trend of user throughput behavior when the network size increases. Since the seminal work of Gupta and Kumar, there have been active research efforts in developing capacity scaling laws for ad hoc networks under various advanced physical layer technologies. These efforts led to many custom-designed solutions, most of which were intellectually challenging and lacked universal properties that can be extended to address scaling laws of ad hoc networks with other physical layer technologies. In this paper, we present a set of simple yet powerful tool that can be applied to quickly determine the capacity scaling laws for various physical layer technologies under the protocol model. We prove the correctness of our proposed criteria and demonstrate their usage through a number of case studies, such as ad hoc networks with directional antenna, MIMO, multi-channel multi-radio, cognitive radio, and multiple packet reception. These simple criteria will serve as powerful tools to networking researchers to obtain throughput scaling laws of ad hoc networks under different physical layer technologies, particularly those to be developed in the future.

Wireless energy transfer based on magnetic resonant coupling is a promising technology to replenish energy to sensor nodes in a wireless sensor network (WSN). However, charging sensor node one at a time poses a serious scalability problem. Recent advances in magnetic resonant coupling shows that multiple nodes can be charged at the same time. In this paper, we exploit this multi-node wireless energy transfer technology to address energy issue in a WSN. We consider a wireless charging vehicle (WCV) periodically traveling inside a WSN and charging sensor nodes wirelessly. We propose a cellular structure that partitions the two-dimensional plane into adjacent hexagonal cells. The WCV visits these cells and charge sensor nodes from the center of a cell. We pursue a formal optimization framework by jointly optimizing traveling path, flow routing and charging time. By employing discretization and a novel Reformulation-Linearization Technique (RLT), we develop a provably near-optimal solution for any desired level of accuracy.

It has been shown that cooperative communications (CC) has the potential to significantly increase the capacity of wireless networks. However, most of the existing results are limited to single-hop wireless networks. To explore the behavior of CC in multi-hop wireless networks, we study a joint optimization problem of relay node assignment and flow routing for a group of sessions. We develop a mathematical model and propose a solution procedure based on the branch-and-bound framework augmented with cutting planes (BB-CP). We design several novel components to speed-up the computational time of BB-CP. Via numerical results, we show the potential rate gain that can be achieved by incorporating CC in multi-hop networks.

A major benefit of employing network coding (NC) in cooperative communications (CCs) is its ability to reduce time-slot overhead. Such approach is called network-coded CC (or NC-CC). Most of the existing works have mainly focused on exploiting this benefit without considering its potential adverse effect. In this paper, we show that NC may not always benefit CC. We substantiate this important finding with two important scenarios: employing analog network coding (ANC) in amplify-and-forward (AF) CC, and digital network coding (DNC) in decode-and-forward (DF) CC. For both scenarios, we introduce the important concept of network coding noise (NC noise). We analyze the origin of this noise via a careful study of signal aggregation at a relay node and signal extraction at a destination node. We derive a closed-form expression for NC noise at each destination node and show that the existence of NC noise could diminish the advantage of NC in CC. Our results shed new light on how to use NC in CC most effectively.

The benefits of using a mobile base station to prolong sensor network lifetime have been well recognized. However, due to the complexity of the problem (time-dependent network topology and traffic routing), theoretical performance limits and provably optimal algorithms remain difficult to develop. This paper fills this important gap by contributing some theoretical results regarding the optimal movement of a mobile base station. Our main result hinges upon two key intermediate results. In the first result, we show that a time-dependent joint base station movement and flow routing problem can be transformed into a location-dependent problem. In the second result, we show that, for$(1- \varepsilon)$optimality, the infinite possible locations for base station movement can be reduced to a finite set of locations via several constructive steps [i.e., discretization of energy cost through a geometric sequence, division of a disk into a finite number of subareas, and representation of each subarea with a fictitious cost point (FCP)]. Subsequently, for each FCP, we can obtain the optimal sojourn time for the base station (as well as the corresponding location-dependent flow routing) via a simple linear program. We prove that the proposed solution can guarantee the achieved network lifetime is at least$(1- \varepsilon)$of the maximum (unknown) network lifetime, where$\varepsilon$can be made arbitrarily small depending on the required precision.

Wireless sensor networks are constrained by limited battery energy. Thus, finite network lifetime is widely regarded as a fundamental performance bottleneck. Recent breakthrough in the area of wireless power transfer offers the potential of removing this performance bottleneck, i.e., allowing a sensor network to remain operational forever. In this paper, we investigate the operation of a sensor network under this new enabling energy transfer technology. We consider the scenario of a mobile charging vehicle periodically traveling inside the sensor network and charging each sensor node's battery wirelessly. We introduce the concept of renewable energy cycle and offer both necessary and sufficient conditions. We study an optimization problem, with the objective of maximizing the ratio of the wireless charging vehicle (WCV)'s vacation time over the cycle time. For this problem, we prove that the optimal traveling path for the WCV is the shortest Hamiltonian cycle and provide a number of important properties. Subsequently, we develop a near-optimal solution by a piecewise linear approximation technique and prove its performance guarantee.

Network-coded cooperative communications (NC-CC) refers to the use of network coding (NC) in cooperative communications (CC). Prior studies have shown that NC has the potential to improve the performance of CC when there are multiple sessions in the wireless network. These studies were done for the case when multiple sessions are sharing a single relay node. However, how NC-CC behaves when multiple relay nodes are employed remains an open problem. In this paper, we explore this problem by analyzing the achievable rate of each session in this setting. We develop closed form formulas for the mutual information and the achievable data rate for each session and show that prior results for a single relay is a special case of our result. Our findings in this paper offer an important building block on the theory of NC-CC. To demonstrate the application of our theoretical result, we apply it in a numerical study to understand the impact on a session's achievable rate when different sets of relay nodes are employed in NC-CC.

Cognitive radio is envisioned to be an enabling radio technology for future wireless networks. In this paper, we study the capacity scaling laws for cognitive radio ad hoc networks (CRNs), i.e., how each individual node's capacity scales as the number of nodes in the network increases. This effort is critical to the fundamental understanding of the scalability of such network. However, due to the heterogeneity in available frequency bands at each node, the asymptotic capacity is much more difficult to develop than prior efforts for other types of wireless networks. To overcome this difficulty, we introduce two auxiliary networks ζ and α to analyze the capacity upper bound and lower bound. We derive the capacity results under both the protocol model and the physical model. Further, we show that the results developed by Gupta and Kumar for the simple single-channel single-radio (SC-SR) networks are special cases under the results for CRNs.

Abstract-Network throughput and energy consumption are two important performance metrics for a multi-hop wireless network. Current state-of-the-art is limited to either maximizing throughput under some energy constraint or minimizing energy consumption while satisfying some throughput requirement. In this paper, we take a multicriteria optimization approach to offer a systematic study on the relationship between the two performance objectives. We show that the solution to the multi criteria optimization problem is equivalent to finding an optimal throughput-energy curve, which characterizes the envelope of the entire throughput-energy region. We prove some important prop erties of the optimal throughput-energy curve. For case study, we consider both linear and nonlinear throughput functions. In the linear case, we characterize the optimal throughput-energy curve precisely through parametric analysis, while in the nonlinear case, we use a piece-wise linear approximation to approximate the optimal throughput-energy curve with arbitrary accuracy. Our results offer important insights on exploiting the trade-off between the two performance metrics. I.

Network-coded cooperative communications (NC-CC) is a new paradigm in wireless networks that employs network coding (NC) to improve the performance of CC. The core mechanism to harness the benefits of NC-CC is to appropriately combine sessions into separate groups, and then have each group select the most beneficial relay node for NC-CC. In this paper, we study this joint grouping and relay node selection problem for NC-CC. Due to NP-hardness of problem, we propose a distributed and online algorithm that offers near-optimal solution to this problem. The key idea in our algorithm is to have each neighboring relay node of a new session determine and offer its best local group; and then to have the source node of the new session select the best group among all offers. We show that our distributed algorithm has polynomial complexity. Using extensive numerical results, we show that our distributed algorithm adapts well to online network dynamics.

The rapid advances of MIMO to date have mainly stayed at the physical layer. Such fruits have not been fully benefited at the network layer mainly due to the computational complexity associated with the matrix-based model that MIMO involves. Recently, there are some efforts to simplify link layer model for MIMO so as to ease research for the upper layers. These models only require numeric computations on MIMO's degrees-of-freedom (DoFs) for spatial multiplexing (SM) and interference cancellation (IC) to obtain a feasible rate region. Thus, these models are much simpler than the original matrix-based model from the communications world. However, none of these DoF-based models is shown to achieve the same rate region as that by the matrix-based model. In this paper, we re-visit this important problem of MIMO modeling. Based on accurate accounting of how DoFs are consumed, we develop a simple link layer model for multi-hop MIMO networks. We show that this model is optimal in the sense of achieving the same rate region as that by the matrix-based model under SM and IC for any network topology. This work offers an important building block for theoretical research on multi-hop MIMO networks.

Traditional wireless sensor networks are constrained by limited battery energy. Thus, finite network lifetime is widely regarded as a fundamental performance bottleneck. Recent breakthrough in the area of wireless energy transfer offers the potential of removing such performance bottleneck, i.e., allowing a sensor network remain operational forever. In this paper, we investigate the operation of a sensor network under this new enabling energy transfer technology. We consider the scenario of a mobile charging vehicle periodically traveling inside the sensor network and charging each sensor node's battery wirelessly. We introduce the concept of renewable energy cycle and offer both necessary and sufficient conditions. We study an optimization problem, with the objective of maximizing the ratio of the wireless charging vehicle (WCV)'s vacation time over the cycle time. For this problem, we prove that the optimal traveling path for the WCV is the shortest Hamiltonian cycle and provide a number of important properties. Subsequently, we develop a near-optimal solution and prove its performance guarantee.

We study a multicast communication problem in a multi-hop ad hoc network where each node is equipped with a cognitive radio (CR). The goal is to minimize the required network-wide resource to support a set of multicast sessions, with a given bit rate requirement for each multicast session. The unique characteristics and complexity associated with CR distinguish this problem from existing multicast problems for ad hoc networks. In this paper, we formulate this problem via a cross-layer approach by taking consideration of scheduling and routing jointly. Although the problem formulation is in the form of a mixed-integer linear program, we develop a polynomial-time algorithm that offers highly competitive solutions. By comparing the solution values with a lower bound, we show that the proposed algorithm can provide a solution that is close to the optimum.

Cognitive radio (CR) and multiple-input multiple-output (MIMO) are two independent physical layer technologies that have made significant impact on wireless networking. CR operates on the channel/band level to exploit white space across spectrum dimension while MIMO operates within the same channel to improve spectral efficiency within the same band. In this paper, we explore MIMO-empowered CR network, which we call {\rm CRN}^{{\rm MIMO}}, to achieve the ultimate flexibility and efficiency in dynamic spectrum access and spectrum utilization. Given that CR and MIMO handle interference at different levels (across channels vs. within a channel), we are interested in how to jointly optimize both so as to maximize user throughput in a multihop network. To answer this question, we develop a tractable mathematical model for {\rm CRN}^{{\rm MIMO}}, which captures the essence of channel assignment (for CR) and degree-of-freedom (DoF) allocation (for MIMO) within a channel. Based on this mathematical model, we use numerical results to show how channel assignment in CRN and DoF allocation in MIMO can be jointly optimized to maximize throughput. More important, for a {\rm CRN}^{{\rm MIMO}} with A_{{\rm MIMO}} antennas at each node, we show that joint optimization of CR and MIMO offers more than A_{MIMO}-fold throughput increase than a CRN (without MIMO).

Cognitive radio networks (CRNs) have the potential to utilize spectrum efficiently and are positioned to be the core technology for the next-generation multihop wireless networks. An important problem for such networks is its capacity. We study this problem for CRNs in the SINR (signal-to-interference-and-noise-ratio) model, which is considered to be a better characterization of interference (but also more difficult to analyze) than disk graph model. The main difficulties of this problem are two-fold. First, SINR is a nonconvex function of transmission powers; an optimization problem in the SINR model is usually a nonconvex program and NP-hard in general. Second, in the SINR model, scheduling feasibility and the maximum allowed flow rate on each link are determined by SINR at the physical layer. To maximize capacity, it is essential to follow a cross-layer approach, but joint optimization at physical (power control), link (scheduling), and network (flow routing) layers with the SINR function is inherently difficult. In this paper, we give a mathematical characterization of the joint relationship among these layers. We devise a solution procedure that provides a (1- \varepsilon ) optimal solution to this complex problem, where \varepsilon is the required accuracy. Our theoretical result offers a performance benchmark for any other algorithms developed for practical implementation. Using numerical results, we demonstrate the efficacy of the solution procedure and offer quantitative understanding on the interaction of power control, scheduling, and flow routing in a CRN.

Recently, cooperative communications, in the form of having each node equipped with a single antenna and exploit spatial diversity via some relay node's antenna, is shown to be a promising approach to increase data rates in wireless networks. Under this communication paradigm, the choice of a relay node (among a set of available relay nodes) is critical in the overall network performance. In this paper, we study the relay node assignment problem in a cooperative ad hoc network environment, where multiple source-destination pairs compete for the same pool of relay nodes in the network. Our objective is to assign the available relay nodes to different source-destination pairs so as to maximize the minimum data rate among all pairs. The main contribution of this paper is the development of an optimal polynomial time algorithm, called ORA, that achieves this objective. A novel idea in this algorithm is a “linear marking” mechanism, which maintains linear complexity of each iteration. We give a formal proof of optimality for ORA and use numerical results to demonstrate its capability.

Multi-input multi-output (MIMO) is a key technology to increase the capacity of wireless networks. Although there has been extensive work on MIMO at the physical and link layers, there is limited work on MIMO at the network layer (i.e., multi-hop MIMO network), particularly results on capacity scaling laws. In this paper, we investigate capacity scaling laws for MIMO ad hoc networks. Our goal is to find the achievable throughput of each node as the number of nodes in the network increases. We employ a MIMO network model that captures spatial multiplexing and interference cancellation. We show that for a MIMO network with n randomly located nodes, each equipped with α antennas and a rate of W on each data stream, the achievable throughput of each node is Θ(αW/√(n ln n)).

MIMO-based communications have great potential to improve network capacity for multi-hop wireless networks. Although there has been significant progress on MIMO at the physical layer or single-hop communication, advances in the theory of MIMO for multi-hop wireless networks remain limited. This stagnation is mainly due to the lack of an accurate and more important, analytically tractable model that can be used by networking researchers. In this paper, we propose such a model to enable the networking community to carry out cross-layer research for multi-hop MIMO networks. In particular, at the physical layer, we develop a simple model for MIMO channel capacity computation that captures the essence of spatial multiplexing and transmit power limit without involving complex matrix operations and the water-filling algorithm. We show that the approximation gap in this model is negligible. At the link layer, we devise a space-time scheduling scheme called OBIC that significantly advances the existing zero-forcing beamforming (ZFBF) to handle interference in a multi-hop network setting. The proposed OBIC scheme employs simple algebraic computation on matrix dimensions to simplify ZFBF in a multi-hop network. As a result, we can characterize link layer scheduling behavior without entangling with beamforming details. Finally, we apply both the new physical and link layer models in cross-layer performance optimization for a multi-hop MIMO network.

It has been shown that cooperative communications (CC) have the potential to significantly increase the capacity of wireless networks. However, most of the existing results are limited to single-hop wireless networks. To illustrate the benefits of CC in multi-hop wireless networks, we solve a joint optimization problem of relay node assignment and flow routing for concurrent sessions. We study this problem via mathematical modeling and solve it using a solution procedure based on the branch-and-cut framework. We design several novel components to speed-up the computation time of branch-and-cut. Via numerical results, we show the significant rate gains that can be achieved by incorporating CC in multi-hop networks.

Network coding (NC) is a promising approach to reduce time-slot overhead for cooperative communications (CC) in a multi-session environment. Most of the existing works take advantage of the benefits of NC in CC but do not fully recognize its potential adverse effect. In this paper, we show that employing NC may not always benefit CC. We substantiate this important finding in the context of analog network coding (ANC) and amplify-and-forward (AF) CC. This paper, for the first time, introduces an important concept of network coding noise (NC noise). Specifically, we analyze the signal aggregation at a relay node and signal extraction at a destination node. We then use the analysis to derive a closed-form expression for NC noise at each destination node in a multi-session environment. We show that NC noise can diminish the advantage of NC in CC. Our results formalizes an important concept on using NC in CC.

Broadband multi-carrier MIMO (MC-MIMO) is a promising technology that could provide significant capacity gain for wireless ad hoc networks. For MC-MIMO networks, since the capacity is affected by potential mutual interference on subcarriers, scheduling for subcarriers and algorithms for power control/allocation become key problems to harness their potential. However, due to non-convexity and large size of the underlying problem, there are few results on this important problem. In this paper, we first show that the non-convex problem for MC-MIMO networks satisfies the so-called concave perturbation condition, which gives a zero duality gap for the problem. This important result allows us to tackle the problem in the dual domain. The dual approach has the highly desirable benefit of reducing the complexity of the underlying problem, which allows us to design a near-optimal off-line algorithm. In addition to the off-line algorithm, we also devise an online adaptive algorithm (OAA) without the need of channel distribution information (CDI). We show that OAA is able to achieve the same result as the off-line algorithm.

This paper tries to reconcile the tension between physical model and protocol model that have been used to characterize interference relationship in a multi-hop wireless network. The physical model (a.k.a. SINR model) is widely considered as a reference model for physical layer behavior but its application in multi-hop wireless networks is limited by its complexity. On the other hand, the protocol model (a.k.a. unified disk graph model) is simple but there have been doubts on its validity. This paper explores the following fundamental question: How to correctly use the protocol interference model? We show that in general, solutions obtained under the protocol model may be infeasible in practice and thus, results based on blind use of protocol model can be misleading. We propose a novel concept called "reality check" and present a method of using protocol model with reality check for wireless networks. Subsequently, we show that by appropriate setting of the interference range in the protocol model, it is possible to narrow the solution gap between the two models. Our simulation results confirm that this gap is indeed small (or even negligible). Thus, our methodology of joint reality check and interference range setting retains the protocol model as a viable approach to analyze multi-hop wireless networks.

Base station location has a significant impact on network lifetime performance for a sensor network. For a multihop sensor network, this problem is particularly challenging due to its coupling with data routing. This article presents an approximation algorithm that can guarantee (1 − ε)-optimal network lifetime performance for base station placement problem with any desired error bound ε > 0. The proposed (1 − ε)-optimal approximation algorithm is based on several novel techniques that makes it possible to reduce an infinite search space to a finite-element search space for base station location. The first technique used in this reduction is to discretize cost parameter (associated with energy consumption) with performance guarantee. Subsequently, the continuous search space can be broken up into a finite number of subareas. The second technique is to exploit the cost property of each subarea and represent it by a novel notion called fictitious cost point, each with guaranteed cost bounds. We give a proof that the proposed base station placement algorithm is (1− ε)-optimal. This approximation algorithm is simpler and faster than a state-of-the-art algorithm and represents the best known result to the base station placement problem.

Cognitive radio network (CRN) is a promising approach to improve spectrum efficiency for wireless networking. This paper investigates how to perform optimal power control on each node (or per-node based power control) in the network so as to optimize network performance. Per-node based power control is a difficult problem due to its large design space (i.e., interaction among the powers on different nodes in the network) and the coupling relationship between power control and upper layers (scheduling and routing). In this paper, we develop a formal mathematical model for joint power control, scheduling, and routing. We formulate a cross-layer optimization problem encompassing these three layers and develop a unified solution procedure based on branch-and-bound framework and convex hull relaxation. Using numerical results, we demonstrate the efficacy of the solution procedure and offer insights on the behavior of per-node based power control.

The benefits of using mobile base station to prolong sensor network lifetime have been well recognized. However, due to the complexity of the problem (time-dependent network topology and traffic routing), theoretical performance limit and provably optimal algorithms remain difficult to develop. This paper fills this important gap by contributing theoretical results regarding the optimal movement of a mobile base station. Our main result hinges upon a novel transformation of the joint base station movement and flow routing problem from time domain to space domain. Based on this transformation, we first show that if the base station is allowed to be present only on a set of pre-defined points, then we can find the optimal time span for the base station on each of these points so that the overall network lifetime is maximized. Based on this finding, we show that when the location of the base station is un-constrained (i.e., can move to any point in the two-dimensional plane), we can develop an approximation algorithm for the joint mobile base station location and flow routing problem such that the network lifetime is guaranteed to be at least (1-epsiv) of the maximum network lifetime, where epsiv can be made arbitrarily small depending on required precision.

Cognitive radio (CR) is a revolution in radio technology and is viewed as an enabling technology for dynamic spectrum access. This paper investigates how to design distributed algorithm for a future multi-hop CR network, with the objective of maximizing data rates for a set of user communication sessions. We study this problem via a cross-layer optimization approach, with joint consideration of power control, scheduling, and routing. The main contribution of this paper is the development of a distributed optimization algorithm that iteratively increases data rates for user communication sessions. During each iteration, there are two separate processes, a Conservative Iterative Process (CIP) and an Aggressive Iterative Process (AIP). For both CIP and AIP, we describe our design of routing, minimalist scheduling, and power control/scheduling modules. To evaluate the performance of the distributed optimization algorithm, we compare it to an upper bound of the objective function, since the exact optimal solution to the objective function cannot be obtained via its mixed integer nonlinear programming (MINLP) formulation. Since the achievable performance via our distributed algorithm is close to the upper bound and the optimal solution (unknown) lies between the upper bound and the feasible solution obtained by our distributed algorithm, we conclude that the results obtained by our distributed algorithm are very close to the optimal solution.

Recently, cooperative communications, in the form of keeping each node with a single antenna and having a node exploit a relay node's antenna, is shown to be a promising approach to achieve spatial diversity. Under this communication paradigm, the choice of relay node plays a significant role in the overall system performance. In this paper, we study the relay node assignment problem in a network environment, where multiple source-destination pairs compete for the same pool of relay nodes in the network. The main contribution of this paper is the development of a polynomial time algorithm to solve this problem. A key idea in this algorithm is a "linear marking" mechanism, which is able to offer a linear complexity for each iteration. We give a formal proof of optimality for this algorithm. We also show several attractive properties associated with this algorithm.

Cognitive radio (CR) capitalizes advances in signal processing and radio technology and is capable of reconfiguring RF and switching to desired frequency bands. It is a frequency-agile data communication device that is vastly more powerful than recently proposed multi-channel multi-radio (MC-MR) technology. In this paper, we investigate the important problem of multi-hop networking with CR nodes. For such a network, each node has a pool of frequency bands (typically of unequal size) that can be used for communication. The potential difference in the bandwidth among the available frequency bands prompts the need to further divide these bands into sub-bands for optimal spectrum sharing. We characterize the behavior and constraints for such a multi-hop CR network from multiple layers, including modeling of spectrum sharing and sub-band division, scheduling and interference constraints, and flow routing. We develop a mathematical formulation with the objective of minimizing the required network-wide radio spectrum resource for a set of user sessions. Since the formulated model is a mixed-integer non-linear program (MINLP), which is NP-hard in general, we develop a lower bound for the objective by relaxing the integer variables and using a linearization technique. Subsequently, we design a near-optimal algorithm to solve this MINLP problem. This algorithm is based on a novel sequential fixing procedure, where the integer variables are determined iteratively via a sequence of linear programs. Simulation results show that solutions obtained by this algorithm are very close to the lower bounds obtained via the proposed relaxation, thus suggesting that the solution produced by the algorithm is near-optimal.

MIMO-based communications systems have great potential to improve network capacity for wireless ad hoc networks. Due to unique physical layer characteristics associated with MIMO, network performance is tightly coupled with mechanisms at physical, link, and routing layers. So far, research on MIMO-based wireless ad hoc networks is still in its infancy and few results are available. In this paper, we consider the problem of jointly optimizing power and bandwidth allocation at each node and multi-hop/multi-path routing in a MIMO-based wireless ad hoc network. We develop a solution procedure to this cross-layer optimization problem and use simulations to validate the efficacy of this solution.

There is growing interest in employing ultra-wideband (UWB) communication systems at the physical layer for multihop wireless networks. Recent efforts show that networking problems involving UWB systems should follow a cross-layer approach with consideration at multiple layers. Due to the nonlinear nature of the optimization problem, there are very limited theoretical results for this important problem. In this paper, we address this problem by considering a UWB-based ad hoc network. We study how to maximize capacity (in the form of a data rate utility) for a set of communication sessions. Via a cross-layer approach, we formulate this utility maximization problem into a nonlinear programming (NLP) problem, which takes into consideration routing, scheduling, and power control. We develop a solution procedure based on the so-called branch-and-bound framework. Within this framework, we employ a powerful optimization technique called reformulation linearization technique (RLT). We use numerical results to validate the efficacy of this solution procedure and offer insights on UWB-based ad hoc networks. This work provides a theoretical result for the achievable performance bound for a UWB-based ad hoc network.

Maximizing the total mutual information of multiuser multiple-input multiple-output (MIMO) systems with interference is a challenging problem. In this paper, we consider the power control problem of finding the maximum sum of mutual information for a multiuser network with mutually interfered MIMO links. We propose a new and powerful global optimization method using a branch-and-bound (BB) framework, coupled with a novel reformulation-linearization technique (RLT). The proposed BB/RLT guarantees finding a global optimum for multiuser MIMO networks with interference. To reduce the complexity of BB/RLT, we propose a modified BB variable selection strategy to accelerate the convergence process. Numerical examples are also given to demonstrate the efficacy of the proposed solution.

Software defined radio (SDR) capitalizes advances in signal processing and radio technology and is capable of reconfiguring RF and switching to desired frequency bands. It is a frequency-agile data communication device that is vastly more powerful than recently proposed multi-channel multi-radio (MC-MR) technology. In this paper, we investigate the important problem of multi-hop networking with SDR nodes. For such network, each node has a pool of frequency bands (not necessarily of equal size) that can be used for communication. The uneven size of bands in the radio spectrum prompts the need of further division into sub-bands for optimal spectrum sharing. We characterize behaviors and constraints for such multi-hop SDR network from multiple layers, including modeling of spectrum sharing and sub-band division, scheduling and interference constraints, and flow routing. We give a formal mathematical formulation with the objective of minimizing the required network-wide radio spectrum resource for a set of user sessions. Since such problem formulation falls into mixed integer non-linear programming (MINLP), which is NP-hard in general, we develop a lower bound for the objective by relaxing the integer variables and linearization. Subsequently, we develop a near-optimal algorithm to this MINLP problem. This algorithm is based on a novel sequential fixing procedure, where the integer variables are determined iteratively via a sequence of linear programming. Simulation results show that solutions obtained by this algorithm are very close to lower bounds obtained via relaxation, thus suggesting that the solution produced by the algorithm is near-optimal.

Software defined radio (SDR) is a revolution in radio technology that promises unprecedented flexibility in radio communications and is viewed as an enabling technology for dynamic spectrum access. This paper investigates how to support user communication sessions by jointly considering power control, scheduling, and flow routing for an SDR-based multi-hop wireless network. We develop a formal mathematical model for scheduling feasibility under the influence of power control. This model extends existing protocol interference model for wireless networks and can be used for a broad class of problems where power control (and thus transmission range and interference range) is part of the optimization space. We formulate a cross-layer optimization problem encompassing power control, scheduling, and flow routing. Subsequently, we develop an efficient solution procedure based on branch-and-bound technique and convex hull relaxation. Using simulation results, we demonstrate the efficacy of the solution procedure and offer insights on the impact of power control on scheduling feasibility, bandwidth efficiency, and bandwidth-footprint product (BFP).

Ultra-wideband (UWB) has great potential for wireless communications in emerging applications such as sensor networks. This paper studies the following fundamental problems for UWB-based sensor networks: For a given network instance, what is the maximum data rate (network capacity) that can be received at the base-station (i.e., sink node)? What is the network capacity bound among arbitrary network instances? We show that these problems can be cast into a cross-layer formulation with joint consideration of routing, scheduling, power control, and rate assignment. For a given network instance, we find a closed-form network capacity as well as corresponding optimal routing, scheduling, power control, and rate assignment. We also find a network capacity bound among arbitrary network instances.

MIMO-based systems have great potential to improve network capacity for wireless mesh networks (WMNs). Due to unique physical layer characteristics associated with MIMO systems, network performance is tightly coupled with mechanisms at physical layer and link layer. So far, research on MIMO-based WMNs is still in its infancy and little results are available in this important area. In this paper, we consider the problem of jointly optimizing power and bandwidth allocation at each node and multihop/multipath routing in a MIMO-based WMN where links operate in orthogonal channels. To solve this problem, we develop a mathematical solution procedure, which combines Lagrangian dual decomposition, gradient projection, and cutting-plane methods. We provide theoretical insights in deriving gradient projection and cutting plane methods. We also use simulations to verify the efficacy of our algorithm.

Since energy constraint is a fundamental issue for wireless sensor networks, network lifetime performance has become a key performance metric for such networks. In this paper, we consider a two-tier wireless sensor network and focus on the flow routing problem for the upper tier aggregation and forwarding nodes (AFNs). Specifically, we are interested in how to perform flow routing among the nodes when the bit rate from each source node is time-varying. We present an algorithm that can be used to construct a flow routing solution with the following properties: (1) If the average rate from each source node is known a priori, then flow routing solution obtained via such algorithm is optimal and offers provably maximum network lifetime performance; (2) If the average rate of each source node is unknown but is within a fraction (epsiv) of an estimated rate value, then network lifetime by the proposed flow routing solution is within 2epsiv/1-epsiv from the optimum. These results fill in an important gap in theoretical foundation for flow routing in energy-constrained sensor networks.

Maximizing the total mutual information of a multiuser multiple-input multiple-output (MIMO) system with interference is a well-known and challenging problem. In this paper, we consider the power control problem of finding the maximum sum of mutual information for multiuser MIMO systems with equal power allocation at each link. A new and powerful global optimization method using a branch-and-bound framework coupled with the reformulation-linearization technique (BB/RLT) is introduced. The proposed BB/RLT is the first such method that guarantees finding a global optimum for multiuser MIMO systems with interference. In addition, we propose a modified branch-and-bound (BB) variable selection strategy to accelerate the convergence process, and apply the proposed technique to several MIMO systems in order to demonstrate its efficacy.

Base station placement has significant impact on sensor network performance. Despite its significance, results on this problem remain limited, particularly theoretical results that can provide performance guarantee. This paper proposes a set of procedure to design (1 -- ε) approximation algorithms for base station placement problems under any desired small error bound ε > 0. It offers a general framework to transform infinite search space to a finite-element search space with performance guarantee. We apply this procedure to solve two practical problems. In the first problem where the objective is to maximize network lifetime, an approximation algorithm designed through this procedure offers 1 / ε2 complexity reduction when compared to a state-of-the-art algorithm. This represents the best known result to this problem. In the second problem, we apply the design procedure to address base station placement problem for maximizing network capacity. Our (1 -- ε) approximation algorithm is the first theoretical result on this problem.

This paper considers ultra-wideband (UWB)-based sensor networks and studies the following problem: given a set of source sensor nodes in the network each generating a certain data rate, is it possible to relay all these rates successfully to the base station? We will show that such problem is intrinsic cross-layer, and subsequently we formulate an optimization problem, with joint consideration of link-layer scheduling, power control, and network-layer routing. For large-sized networks, we propose an efficient heuristic algorithm by partitioning the given network into a core centered around the base station and a boundary edge. For the network core, we formulate a nonlinear programming problem, which can be solved by branch-and-bound approach. For data generated at network edge, we propose an algorithm to connect it to the network core. We use simulation results to demonstrate the efficacy of the proposed solution procedure, as well as the importance of cross-layer considerations.

Wireless sensor networks are becoming increasingly important in recent years due to their ability to detect and convey real-time, in-situ information for many civilian and military applications. A fundamental challenge for such networks lies in energy constraint, which poses a performance limit on the achievable network lifetime. We consider a two-tier wireless sensor network and address the network lifetime problem for upper-tier aggregation and forwarding nodes (AFNs). Existing flow routing solutions proposed for maximizing network lifetime require AFNs to split flows to different paths during transmission, which we call multisession flow routing solutions. If an AFN is equipped with a single transmitter/receiver pair, a multisession flow routing solution requires a packet-level power control at the AFN so as to conserve energy, which calls for considerable overhead in synchronization among the AFNs. In this paper, we show that it is possible to achieve the same optimal network lifetime by power control on a much larger timescale with the so-called single-session flow routing solutions, under which the packet-level power control and, thus, strict requirement on synchronization are not necessary. We also show how to perform optimal single-session flow routing when the bit-rate of composite flows generated by AFNs is time-varying, as long as the average bit-rate can be estimated

Directional antenna has great potential to reduce power consumption in energy constrained wireless sensor networks. We consider a two-tier wireless sensor network where directional antenna is employed for upper-tier aggregation and forwarding nodes (AFNs). Existing flow routing solutions for maximizing network lifetime require each AFN to transmit multiple flows to different nodes at the same time, which we call multi-beam flow routing solution. In this paper, we show that it is possible to develop single-beam flow routing solution for nodes with directional antenna. More important, we show that the single-beam flow routing solution developed here is provably optimal in terms of network lifetime performance. This result is based on a novel technique to transform the optimal multi-beam flow routing into an equivalent single-beam flow routing solution. Numerical example illustrating how to obtain an optimal single-beam flow routing solution is also given.

We consider a two-tier wireless sensor network and focus on the flow routing problem for the upper tier aggregation and forwarding nodes (AFNs). Assuming each AFN is equipped with directional antennas for transmission, we are interested in how to perform flow routing at each node such that the network lifetime is maximized. We present a flow routing algorithm that provably has the following properties: (1) when the average source rate of each AFN is known a priori, the flow routing algorithm is optimal and gives maximum network lifetime performance; (2) when the average source rate of each AFN is unknown but is within a fraction, /spl epsiv/, of an estimated rate value, then the network lifetime given by the proposed flow routing algorithm is no more than 2/spl epsiv//(1-/spl epsiv/) from optimal. As a result, the proposed flow routing algorithm can provide predictable lifetime performance, even when the source bit rate can be time-varying.

We consider a wireless ad hoc network where each node employs a single-beam directional antenna and is provisioned with limited energy. We are interested in an online multicast routing algorithm for successive multicast communication requests with the aim of maximizing network lifetime. The beamforming property associated with single-beam directional antenna introduces some unique problems that do not exist for omnidirectional antennas and therefore significantly increases the design space for routing algorithms. The contributions of this paper are twofold. First, we provide some important theoretical understanding on various multicast problems and deduce that even an offline version of this problem is NP-hard. Second, we develop a highly competitive online heuristic algorithm that takes network lifetime consideration directly into iterative calculations and show that an algorithm designed under this methodology provides consistently better performance than the current state-of-the-art algorithm that takes remaining energy into iterative calculations. The theoretical results and heuristic algorithm in this paper offer some important insights on algorithmic design for energy-constrained wireless ad hoc networks with directional antennas.

Ultra-wideband (UWB) has great potential for wireless communications in emerging applications such as sensor networks. This paper considers UWB-based sensor networks and studies the following problem: given a set of source sensor nodes in the network each generating a certain data rate, is it possible to relay all these rates successfully to the base-station? We follow a cross-layer optimization approach, with joint consideration of link layer scheduling, power control, and network layer routing. The optimization problem is formulated as a non-linear programming problem. For small-sized networks, we develop a powerful approximation solution procedure to this problem based on the branch-and-bound approach and the novel Reformulation-Linearization Technique (RLT). For large-sized networks, we propose an efficient heuristic algorithm by partitioning the sensor network into a core centered around the base-station and an edge that is outside the core. We also provide a closed-form analysis for the maximum rate that a base-station can receive. Simulation results exhibit the efficacy of our proposed optimization solution procedure and demonstrate the importance of the cross-layer approach to UWB-based sensor networks.

Energy constraints have had a significant impact on the design and operation of wireless sensor networks. In this paper, we investigate base station selection (or anycast) problem in wireless sensor networks. We consider a wireless sensor network having multiple base stations (data sink nodes), where each source node must send all its locally generated data to only one base station. To maximize the network lifetime, it is essential to optimally match each source node to a particular base station in addition to finding an optimal routing solution. We propose a polynomial time heuristic for optimal base station selection for anycast via a sequential fixing procedure, under the assumption that the bit rate from each source node is constant. Through extensive simulation results, we show that this heuristic has excellent performance behavior and is a tight low bound that is very close to optimal solution for the original optimization problem.

Abstract — Wireless sensor networks that operate on batteries have limited network lifetime. There have been extensive recent research efforts on how to design protocols and algorithms to prolong network lifetime. However, due to energy constraint, even under the most efficient protocols and algorithms, the network lifetime may still be unable to meet the mission’s requirements. In this paper, we consider the energy provisioning problem for a two-tier wireless sensor network. In addition to provisioning additional energy on the existing nodes, we also consider deploying relay nodes (RNs) into the network to mitigate network geometric deficiency and prolong network lifetime. We formulate the joint problem of energy provisioning and relay node placement (EP-RNP) into a mixed-integer nonlinear programming (MINLP) problem. Since an MINLP problem is NP-hard in general, and even the state-of-the-art software and techniques are unable to offer satisfactory solutions, we develop a heuristic algorithm, called SPINDS, to address this problem. We show a number of novel algorithmic design techniques in the design of SPINDS that effectively transforms a complex MINLP problem into linear programming (LP) problems without losing critical points in its search space. Through numerical results, we show that SPINDS offers very attractive solution and some important insights to the EP-RNP problem. Index Terms — Energy provisioning, relay node placement, power control, network lifetime, flow routing, wireless sensor networks. I.

We consider generic two-tiered wireless sensor networks (WSNs) consisting of sensor clusters deployed around strategic locations, and base-stations (BSs) whose locations are relatively flexible. Within a sensor cluster, there are many small sensor nodes (SNs) that capture, encode, and transmit relevant information from a designated area, and there is at least one application node (AN) that receives raw data from these SNs, creates a comprehensive local-view, and forwards the composite bit-stream toward a BS. This paper focuses on the topology control process for ANs and BSs, which constitute the upper tier of two-tiered WSNs. Since heterogeneous ANs are battery-powered and energy-constrained, their node lifetime directly affects the network lifetime of WSNs. By proposing algorithmic approaches to locate BSs optimally, we can maximize the topological network lifetime of WSNs deterministically, even when the initial energy provisioning for ANs is no longer always proportional to their average bit-stream rate. The obtained optimal BS locations are under different lifetime definitions according to the mission criticality of WSNs. By studying intrinsic properties of WSNs, we establish the upper and lower bounds of maximal topological lifetime, which enable a quick assessment of energy provisioning feasibility and topology control necessity. Numerical results are given to demonstrate the efficacy and optimality of the proposed topology control approaches designed for maximizing network lifetime of WSNs.

We study the network lifetime problem by considering not only the maximized time until the first node fails, but also the maximized lifetime for all the nodes in the network which we define as the lexicographic max-min (LMM) node lifetime problem. The main contributions of this paper are two-fold. First, we develop a polynomial-time algorithm to derive the LMM-optimal node lifetime vector, which effectively circumvents the computational complexity problem associated with an existing state-of-the-art approach, which is exponential. Second, we present a simple (also polynomial-time) algorithm to calculate the flow routing schedule such that the LMM-optimal node lifetime vector can be achieved. Our results in this paper advance the state-of-the-art algorithmic design to network-wide node lifetime problems.

An important performance consideration for wireless sensor networks is the amount of information collected by all the nodes in the network over the course of network lifetime. Since the objective of maximizing the sum of rates of all the nodes in the network can lead to a severe bias in rate allocation among the nodes, we advocate the use of lexicographical max-min (LMM) rate allocation for the nodes. To calculate the LMM rate allocation vector, we develop a polynomial-time algorithm by exploiting the parametric analysis (PA) technique from linear programming (LP), which we call serial LP with Parametric Analysis (SLP-PA). We show that the SLP-PA can be also employed to address the so-called LMM node lifetime problem much more efficiently than an existing technique proposed in the literature. More important, we show that there exists an elegant duality relationship between the LMM rate allocation problem and the LMM node lifetime problem. Therefore, it is sufficient to solve any one of the two problems and important insights can be obtained by inferring duality results for the other problem.

We consider a two-tiered Wireless Sensor Network (WSN) consisting of sensor clusters deployed around strategic locations and base-stations (BSs) whose locations are relatively flexible. Within a sensor cluster, there are many small sensor nodes (SNs) that capture, encode and transmit relevant information from the designated area, and there is at least one application node (AN) that receives raw data from these SNs, creates a comprehensive local-view, and forwards the composite bit-stream toward a BS. In practice, both SN and AN are battery-powered and energy-constrained, and their node lifetimes directly affect the network lifetime of WSNs. In this paper, we focus on the topology control process for ANs and BSs, which constitute the upper tier of a two-tiered WSN. We propose approaches to maximize the topological network lifetime of the WSN, by arranging BS location and inter-AN relaying optimally. Based on an algorithm in Computational Geometry, we derive the optimal BS locations under three topological lifetime definitions according to mission criticality. In addition, by studying the intrinsic properties of WSNs, we establish the upper and lower bounds of their maximal topological lifetime. When inter-AN relaying becomes feasible and favorable, we continue to develop an optimal parallel relay allocation to further prolong the topological lifetime of the WSN. An equivalent serialized relay schedule is also obtained, so that each AN only needs to have one relay destination at any time throughout the mission. The experimental performance evaluation demonstrates the efficacy of topology control as a vital process to maximize the network lifetime of WSNs.