Computational offloading is a promising approach to overcome client device resource constraints by moving application computations to remote servers. With the advent of specialized hardware accelerators, client devices can now perform fast local processing of tasks such as machine learning inference, reducing the need for offloading. However, edge servers with accelerators also offer faster offloading performance than was previously possible. In this paper, we present an analytic and experimental comparison of on-device processing and edge offloading across accelerator, multi-tenant, and workload scenarios to understand when to use local processing versus offloading. We present models that leverage queuing theory to derive explainable closed-form equations for end-to-end latencies, yielding quantitative performance crossover predictions to guide adaptive offloading. We validate our models across various settings and show that they achieve a mean absolute percentage error of 2.2% compared to observed latencies. We further use these models to develop a resource manager for adaptive offloading and demonstrate its effectiveness in dynamic multi-tenant edge environments.

In wireless networks characterized by dense connectivity, the significant signaling overhead generated by distributed link scheduling algorithms can exacerbate issues like congestion, energy consumption, and radio footprint expansion. To mitigate these challenges, we propose a distributed link sparsification scheme employing graph neural networks (GNNs) to reduce scheduling overhead for delay-tolerant traffic while maintaining network capacity. A GNN module is trained to adjust contention thresholds for individual links based on traffic statistics and network topology, enabling links to withdraw from scheduling contention when they are unlikely to succeed. Our approach is facilitated by a novel offline constrained unsupervised learning algorithm capable of balancing two competing objectives: minimizing scheduling overhead while ensuring that total utility meets the required level. In simulated wireless multi-hop networks with up to 500 links, our link sparsification technique effectively alleviates network congestion and reduces radio footprints across four distinct distributed link scheduling protocols.

Incorporating transformer models into edge devices poses a significant challenge due to the computational demands of adapting these large models across diverse applications. Parameter-efficient tuning (PET) methods (e.g. LoRA, Adapter, Visual Prompt Tuning, etc.) allow for targeted adaptation by modifying only small parts of the transformer model. However, adapting to dynamic unlabeled target distributions at the test time remains complex. To address this, we introduce AdMiT: Adaptive Multi-Source Tuning in Dynamic Environments. AdMiT innovates by pre-training a set of PET modules, each optimized for different source distributions or tasks, and dynamically selecting and integrating a sparse subset of relevant modules when encountering a new, few-shot, unlabeled target distribution. This integration leverages Kernel Mean Embedding (KME)-based matching to align the target distribution with relevant source knowledge efficiently, without requiring additional routing networks or hyperparameter tuning. AdMiT achieves adaptation with a single inference step, making it particularly suitable for resource-constrained edge deployments. Furthermore, AdMiT preserves privacy by performing an adaptation locally on each edge device, without the need for data exchange. Our theoretical analysis establishes guarantees for AdMiT’s generalization, while extensive benchmarks demonstrate that AdMiT consistently outperforms other PET methods across a range of tasks, achieving robust and efficient adaptation.

A significant challenge for computation offloading in wireless multi-hop networks is the complex interactions among traffic flows in the presence of interference. Existing approaches often ignore these key effects and/or rely on outdated queueing and channel state information. To fill these gaps, we reformulate joint offloading and routing as a routing problem on an extended graph with physical and virtual links. We adopt the state-of-the-art shortest path-biased Backpressure routing algorithm, which allows the destination and the route of a job to be dynamically adjusted at every time step based on network-wide long-term information and real-time states of local neighborhoods. In large networks, our approach achieves smaller makespan than existing approaches, such as separated Backpressure offloading, and joint offloading and routing based on linear programming.

Federated Learning (FL) enables model training across decentralized clients while preserving data privacy. However, bandwidth constraints limit the volume of information exchanged, making communication efficiency a critical challenge. In addition, non-IID data distributions require fairness-aware mechanisms to prevent performance degradation for certain clients. Existing sparsification techniques often apply fixed compression ratios uniformly, ignoring variations in client importance and bandwidth. We propose Fed-Band, a dynamic bandwidth allocation framework that prioritizes clients based on their contribution to the global model. Unlike conventional approaches, FedBand does not enforce uniform client participation in every communication round. Instead, it allocates more bandwidth to clients whose local updates deviate significantly from the global model, enabling them to transmit a greater number of parameters. Clients with less impactful updates contribute proportionally less or may defer transmission, reducing unnecessary overhead while maintaining generalizability. By optimizing the trade-off between communication efficiency and learning performance, FedBand substantially reduces transmission costs while preserving model accuracy. Experiments on non-IID CIFAR-10 and UTMobileNet2021 datasets, demonstrate that FedBand achieves up to 99.81% bandwidth savings per round while maintaining accuracies close to that of an unsparsified model (80% on CIFAR-10, 95% on UTMobileNet), despite transmitting less than 1% of the model parameters in each round. Moreover, FedBand accelerates convergence by 37.4%, further improving learning efficiency under bandwidth constraints. Mininet emulations further show a 42.6% reduction in communication costs and a 65.57% acceleration in convergence compared to baseline methods, validating its real-world efficiency. These results demonstrate that adaptive bandwidth allocation can significantly enhance the scalability and communication efficiency of federated learning, making it more viable for real-world, bandwidth-constrained networking environments.

Despite the success of Test-time adaptation (TTA), recent work has shown that adding relatively small adversarial perturbations to a limited number of samples leads to significant performance degradation. Therefore, it is crucial to rigorously evaluate existing TTA algorithms against relevant threats and implement appropriate security countermeasures. Importantly, existing threat models assume test-time samples will be labeled, which is impractical in real-world scenarios. To address this gap, we propose a new attack algorithm that does not rely on access to labeled test samples, thus providing a concrete way to assess the security vulnerabilities of TTA algorithms. Our attack design is grounded in theoretical foundations and can generate strong attacks against different state of the art TTA methods. In addition, we show that existing defense mechanisms are almost ineffective, which emphasizes the need for further research on TTA security. Through extensive experiments on CIFAR10-C, CIFAR100-C, and ImageNet-C, we demonstrate that our proposed approach closely matches the performance of state-of-the-art attack benchmarks, even without access to labeled samples. In certain cases, our approach generates stronger attacks, e.g., more than 4% higher error rate on CIFAR10-C.

This paper proposes an efficient approach to joint task offloading and routing for real-time sensor data analytics at the network edge, enabling applications such as video surveillance and environmental monitoring. This problem can be formulated as a mixed-integer program (MIP) with the objective of utility maximization subject to the constraints of network topology, limited link capacity, and diverse task profiles. To efficiently approximate this NP-hard problem, we propose SeLR, a combination of primal-dual optimization and reweighted L1-norm regularization, which iteratively solves the convex relaxation while penalizing constraint violations and encouraging sparsity. Compared to greedy heuristics, SeLR provides a better accuracy—latency trade-off and better scalability to larger problems. Moreover, it reduces scheduling runtime by up to 9.17× over optimal solvers in networks with 300 nodes and 100 tasks.

We examine an uplink cell-free (CF) massive multiple-input multiple-output (MIMO) system in which multiple-antenna access points (APs) are connected to a central processing unit (CPU) via unlimited capacity front-haul links, and each user equipment (UE) is equipped with a single antenna. In such a system, optimizing AP selection to maximize the sum spectral efficiency (SE) while meeting real-time communication requirements is challenging. To address this, we develop a novel approach using a heterogeneous graph neural network (HetGNN), which effectively captures the complex relationships between AP and UE nodes. Given the difficulty in obtaining ground truth for optimal AP selection, we employ an unsupervised HetGNN model that directly optimizes AP selection through its loss function. Simulation results demonstrate that our approach achieves an average improvement of at least 8% compared to existing methods and surpasses an offline approach using the Simulated Annealing method. Our approach also results in high fairness scores on Jain's Fairness Index; averaging greater than 0.845 per UE and exceeding 0.9 as the system scales. Our computation time analysis shows that the average inference time remains low and within acceptable limits for communication systems.

We propose a joint channel estimation and data detection algorithm for massive multilple-input multiple-output systems based on diffusion models. Our proposed method solves the blind inverse problem by sampling from the joint posterior distribution of the symbols and channels and computing an approximate maximum a posteriori estimation. To achieve this, we construct a diffusion process that models the joint distribution of the channels and symbols given noisy observations, and then run the reverse process to generate the samples. A unique contribution of the algorithm is to include the discrete prior distribution of the symbols and a learned prior for the channels. Indeed, this is key as it allows a more efficient exploration of the joint search space and, therefore, enhances the sampling process. Through numerical experiments, we demonstrate that our method yields a lower normalized mean squared error than competing approaches and reduces the pilot overhead.

This paper studies an application of “secret-message transmission by echoing encrypted probes (STEEP)” to multiple access (MA) between users' equipment (UEs) and an access point (AP). This method, referred to as MA-STEEP, allows all UEs to take advantage of a common sequence of probes broadcasted by AP, which helps to meet the low-latency requirement. The secrecy capacity of MA-STEEP from each UE to AP is shown to be positive with high probability (subject to a power condition) and robust against the number$M$of UEs. A total secrecy capacity of MA-STEEP increases with$M$, unlike a common-nonce method.

The advent of 5G promises high bandwidth with the introduction of mmWave technology recently, paving the way for throughput-sensitive applications. However, our measurements in commercial 5G networks show that frequent handovers in 5G, due to physical limitations of mmWave cells, introduce significant under-utilization of the available bandwidth. By analyzing 5G link-layer and TCP traces, we uncover that improper interactions between these two layers causes multiple inefficiencies during handovers. To mitigate these, we propose M2HO, a novel device-centric solution that can predict and recognize different stages of a handover and perform state-dependent mitigation to markedly improve throughput. M2HO is transparent to the firmware, base stations, servers, and applications. We implement M2HO and our extensive evaluations validate that it yields significant improvements in TCP throughput with frequent handovers.

We develop an efficient and near-optimal solution for beamforming in multi-user multiple-input-multiple-output single-hop wireless ad-hoc interference networks. Inspired by the weighted minimum mean squared error (WMMSE) method, a classical approach to solving this problem, and the principle of algorithm unfolding, we present unfolded WMMSE (UWMMSE) for MU-MIMO. This method learns a parameterized functional transformation of key WMMSE variables using graph neural networks (GNNs), where the channel and interference components of a wireless network constitute the underlying graph. These GNNs are trained through gradient descent on a network utility metric using multiple instances of the beamforming problem. Comprehensive experimental analyses illustrate the superiority of UWMMSE over the classical WMMSE and state-of-the-art learning-based methods in terms of performance, generalizability, and robustness.

We propose a novel data-driven approach to allocate transmit power for federated learning (FL) over interference-limited wireless networks. The proposed method is useful in challenging scenarios where the wireless channel is changing during the FL training process and when the training data are not independent and identically distributed (non-i.i.d.) on the local devices. Intuitively, the power policy is designed to optimize the information received at the server end during the FL process under communication constraints. Ultimately, our goal is to improve the accuracy and efficiency of the global FL model being trained. The proposed power allocation policy is parameterized using graph convolutional networks (GCNs), and the associated constrained optimization problem is solved through a primal-dual (PD) algorithm. Theoretically, we show that the formulated problem has a zero duality gap and, once the power policy is parameterized, optimality depends on how expressive this parameterization is. Numerically, we demonstrate that the proposed method outperforms existing baselines under different wireless channel settings and varying degrees of data heterogeneity.

We propose a throughput-optimal biased backpressure (BP) algorithm for routing, where the bias is learned through a graph neural network that seeks to minimize end-to-end delay. Classical BP routing provides a simple yet powerful distributed solution for resource allocation in wireless multi-hop networks but has poor delay performance. A low-cost approach to improve this delay performance is to favor shorter paths by incorporating pre-defined biases in the BP computation, such as a bias based on the shortest path (hop) distance to the destination. In this work, we improve upon the widely-used metric of hop distance (and its variants) for the shortest path bias by introducing a bias based on the link duty cycle, which we predict using a graph convolutional neural network. Numerical results show that our approach can improve the delay performance compared to classical BP and existing BP alternatives based on pre-defined bias while being adaptive to interference density. In terms of complexity, our distributed implementation only introduces a one-time overhead (linear in the number of devices in the network) compared to classical BP, and a constant overhead compared to the lowest-complexity existing bias-based BP algorithms.

We present a new threat model enabling a passive adversary to infer which overheard packets belong to which transmitters. We call this threat model unsupervised wireless diarization (UWD) where the adversary assigns transmitter identity (label) to received packets in an encrypted wireless network without access to the MAC headers. To demonstrate the feasibility of such an attack, we develop UWDNet, a wireless diarization pipeline comprised of a Siamese neural network to extract embeddings from received packets, a similarity metric to compare embeddings, and unsupervised clustering. We evaluate UWDNet on both synthetic datasets and datasets of real wireless transmissions collected using Rice University's configurable massive MIMO testbed RENEW. Via various experimentation scenarios, our initial results show that UWDNet achieves a diarization accuracy of above 90% on synthetic data of transmitters it has never seen. To push the limits of performance evaluation, we collected a real radio transmissions dataset representing a worst-case (almost pathological) setting where all nodes are co-located. Even in this near-pathological case, UWDNet accuracy is > 60% – well above a random label assignment, indicating the feasibility of unsupervised wireless diarization in real-life scenarios. We also analyzed different factors such as the spatial channel and transmit parameters, which impact diarization accuracy in real-world scenarios.

We consider the problem of training a given machine learning model by decentralized parallel stochastic gradient descent over training data distributed across multiple nodes, which arises in many application scenarios. Although extensive studies have been conducted on improving the communication efficiency by optimizing what to communicate between nodes (e.g., model compression) and how often to communicate, recent studies have shown that it is also important to customize the communication patterns between each pair of nodes, which is the focus of this work. To this end, we propose a framework and efficient algorithms to design the communication patterns through Laplacian matrix sampling (LMS), which governs not only which nodes should communicate with each other but also what weights the communicated parameters should carry during parameter aggregation. Our framework is designed to minimize the total cost incurred until convergence based on any given cost model that is additive over iterations, with focus on minimizing the communication cost. Besides achieving a theoretically guaranteed performance in the special case of additive homogeneous communication costs, our solution also achieves superior performance under a variety of network settings and cost models in experiments based on real datasets and topologies, saving 24–50% of the cost compared to the state-of-the-art design without compromising the quality of the trained model.

A widely established set of unsupervised node embedding methods can be interpreted as consisting of two distinctive steps: i) the definition of a similarity matrix based on the graph of interest followed by ii) an explicit or implicit factorization of such matrix. Inspired by this viewpoint, we propose improvements in both steps of the framework. On the one hand, we propose to encode node similarities based on the free energy distance, which interpolates between the shortest path and the commute time distances, thus, providing an additional degree of flexibility. On the other hand, we propose a matrix factorization method based on a loss function that generalizes that of the skip-gram model with negative sampling to arbitrary similarity matrices. Compared with factorizations based on the widely used$\ell _{2}$loss, the proposed method can better preserve node pairs associated with higher similarity scores. Moreover, it can be easily implemented using advanced automatic differentiation toolkits and computed efficiently by leveraging GPU resources. Node clustering, node classification, and link prediction experiments on real-world datasets demonstrate the effectiveness of incorporating free-energy-based similarities as well as the proposed matrix factorization compared with state-of-the-art alternatives.

The growing demand for edge computing resources, particularly due to increasing popularity of Internet of Things (IoT), and distributed machine/deep learning applications poses a significant challenge. On the one hand, certain edge service providers (ESPs) may not have sufficient resources to satisfy their applications according to the associated service-level agreements. On the other hand, some ESPs may have additional unused resources. In this paper, we propose a resource-sharing framework that allows different ESPs to optimally utilize their resources and improve the satisfaction level of applications subject to constraints such as communication cost for sharing resources across ESPs. Our framework considers that different ESPs have their own objectives for utilizing their resources, thus resulting in a multi-objective optimization problem. We present an${N}$-person Nash Bargaining Solution (NBS) for resource allocation and sharing among ESPs with Pareto optimality guarantee. Furthermore, we propose a distributed, primal-dual algorithm to obtain the NBS by proving that the strong-duality property holds for the resultant resource sharing optimization problem. Using synthetic and real-world data traces, we show numerically that the proposed NBS based framework not only enhances the ability to satisfy applications’ resource demands, but also improves utilities of different ESPs.

Estimation of transmission rates by a malicious user can serve as a stepping stone to further attacks on the network. In this paper, we aim to investigate the general problem of estimating traffic transmission rates in a CSMA/CA network using a class of passive eavesdropping methods. We consider the case where a single eavesdropper passively monitors all active network nodes but cannot observe all packet transmissions due to spatial-reuse collisions. To enable tractable analysis, we first propose an approximate statistical model that can help the eavesdropper estimate transmission rates with partial measurements under spatial reuse. We next consider a class of eavesdroppers that become increasingly more capable, and develop a framework to demonstrate that two classes of eavesdropper capabilities are sufficient to achieve a consistent transmission rate estimator. We provide numerical tests of our proposed estimators under practical network cases using the NS-3 simulator that validate the theoretical results.

Efficient scheduling of transmissions is a key problem in wireless networks. The main challenge stems from the fact that optimal link scheduling involves solving a maximum weighted independent set (MWIS) problem, which is known to be NP-hard. In practical schedulers, centralized and distributed greedy heuristics are commonly used to approximately solve the MWIS problem. However, most of these greedy heuristics ignore important topological information of the wireless network. To overcome this limitation, we propose fast heuristics based on graph convolutional networks (GCNs) that can be implemented in centralized and distributed manners. Our centralized heuristic is based on tree search guided by a GCN and 1-step rollout. In our distributed MWIS solver, a GCN generates topology-aware node embeddings that are combined with per-link utilities before invoking a distributed greedy solver. Moreover, a novel reinforcement learning scheme is developed to train the GCN in a non-differentiable pipeline. Test results on medium-sized wireless networks show that our centralized heuristic can reach a near-optimal solution quickly, and our distributed heuristic based on a shallow GCN can reduce by nearly half the suboptimality gap of the distributed greedy solver with minimal increase in complexity. The proposed schedulers also exhibit good generalizability across graph and weight distributions.

We propose a data-driven approach for power allocation in the context of federated learning (FL) over interference-limited wireless networks. The power policy is designed to maximize the transmitted information during the FL process under communication constraints, with the ultimate objective of improving the accuracy and efficiency of the global FL model being trained. The proposed power allocation policy is parameterized using a graph convolutional network and the associated constrained optimization problem is solved through a primal-dual algorithm. Numerical experiments show that the proposed method outperforms three baseline methods in both transmission success rate and FL global performance.

Distributed scheduling algorithms for throughput or utility maximization in dense wireless multi-hop networks can have overwhelmingly high overhead, causing increased congestion, energy consumption, radio footprint, and security vulnerability. For wireless networks with dense connectivity, we propose a distributed scheme for link sparsification with graph convolutional networks (GCNs), which can reduce the scheduling overhead while keeping most of the network capacity. In a nutshell, a trainable GCN module generates node embeddings as topology-aware and reusable parameters for a local decision mechanism, based on which a link can withdraw itself from the scheduling contention if it is not likely to win. In medium-sized wireless networks, our proposed sparse scheduler beats classical threshold-based sparsification policies by retaining almost 70% of the total capacity achieved by a distributed greedy max-weight scheduler with 0.4% of the point-to-point message complexity and 2.6% of the average number of interfering neighbors per link.

In wireless multi-hop networks, delay is an important metric for many applications. However, the max-weight scheduling algorithms in the literature typically focus on instantaneous optimality, in which the schedule is selected by solving a maximum weighted independent set (MWIS) problem on the interference graph at each time slot. These myopic policies perform poorly in delay-oriented scheduling, in which the dependency between the current backlogs of the network and the schedule of the previous time slot needs to be considered. To address this issue, we propose a delay-oriented distributed scheduler based on graph convolutional networks (GCNs). In a nutshell, a trainable GCN module generates node embeddings that capture the network topology as well as multi-step lookahead backlogs, before calling a distributed greedy MWIS solver. In small- to medium-sized wireless networks with heterogeneous transmit power, where a few central links have many interfering neighbors, our proposed distributed scheduler can outperform the myopic schedulers based on greedy and instantaneously optimal MWIS solvers, with good generalizability across graph models and minimal increase in communication complexity.

This paper presents a secure downlink communication system where a transmitter with multiple antennas sends information to multiple single antenna users under ultra reliable and low-latency communication (uRLLC) system requirement. To meet uRLLC requirement and provide secrecy against multi-antenna eavesdropper (Eve), transmitter adopts a special channel training scheme called anti-eavesdropping channel estimation (ANECE) as well as a standard transmit beamforming to send secret information in short blocklength regime. Using ANECE, two or more cooperative full-duplex radio devices obtain their receive channel state information (CSI) with respect to each other while preventing Eve from obtaining a consistent estimate of its receive CSI, which improves the secrecy of subsequent transmission of information between the devices. We derive an expression for the average secrecy throughput (AST) of ANECE assisted transmission. This easy-to-evaluate expression of approximated AST in terms of blocklength and various controllable parameters leads to useful insights to maximize AST under uRLLC requirement. Finally, numerical results are presented and discussed.

Flow networks are ubiquitous in natural and engineered systems, and in order to understand and manage these networks, one must quantify the flow of commodities across their edges. This paper considers the estimation problem of predicting unlabeled edge flows from nodal supply and demand. We propose an implicit neural network layer that incorporates two fundamental physical laws: conservation of mass, and the existence of a constitutive relationship between edge flows and nodal states (e.g., Ohm's law). Computing the edge flows from these two laws is a nonlinear inverse problem, which our layer solves efficiently with a specialized contraction mapping. Using implicit differentiation to compute the solution's gradients, our model is able to learn the constitutive relationship within a semi-supervised framework. We demonstrate that our approach can accurately predict edge flows in several experiments on AC power networks and water distribution systems.

Anti-eavesdropping channel estimation (ANECE) among two or more cooperative full-duplex radio devices allows these devices to obtain consistent estimates of their receive channel state information (CSI) with respect to each other but at the same time prevents eavesdropper (Eve) from obtaining a consistent estimate of its receive CSI, which improves the secrecy of subsequent transmission of information between the devices. This paper presents an analysis of secrecy throughput of ANECE assisted transmission of information between such single-antenna devices against Eve with multiple antennas. The analysis is based on finite blocklength coding and assumes that Eve applies a standard approach for information detection. Easy-to-compute analytical expressions of secrecy throughput in terms of various controllable parameters are obtained. Numerical results are presented and discussed.

Many tasks regarding the monitoring, management, and design of communication networks rely on knowledge of the routing topology. However, the standard approach to topology mapping—namely, active probing with traceroutes—relies on cooperation from increasingly non-cooperative routers, leading to missing information. Network tomography, which uses end-to-end measurements of additive link metrics (like delays or log packet loss rates) across monitor paths, is a possible remedy. Network tomography does not require that routers cooperate with traceroute probes, and it has already been used to infer the structure of multicast trees. This paper goes a step further. We provide a tomographic method to infer the underlying routing topology of an arbitrary set of monitor paths using the joint distribution of end-to-end measurements, without making any assumptions on routing behavior. Our approach, called the Möbius Inference Algorithm (MIA), uses cumulants of this distribution to quantify high-order interactions among monitor paths, and it applies Möbius inversion to “disentangle” these interactions. In addition to MIA, we provide a more practical variant called Sparse Möbius Inference, which uses various sparsity heuristics to reduce the number and order of cumulants required to be estimated. We show the viability of our approach using synthetic case studies based on real-world ISP topologies.

We study the problem of optimal power allocation in a single-hop ad hoc wireless network. In solving this problem, we propose a hybrid neural architecture inspired by the algorithmic unfolding of the iterative weighted minimum mean squared error (WMMSE) method, that we denote as unfolded WMMSE (UWMMSE). The learnable weights within UWMMSE are parameterized using graph neural networks (GNNs), where the time-varying underlying graphs are given by the fading interference coefficients in the wireless network. These GNNs are trained through a gradient descent approach based on multiple instances of the power allocation problem. Once trained, UWMMSE achieves performance comparable to that of WMMSE while significantly reducing the computational complexity. This phenomenon is illustrated through numerical experiments along with the robustness and generalization to wireless networks of different densities and sizes.

We study the problem of adaptive contention window (CW) design for random-access wireless networks. More precisely, our goal is to design an intelligent node that can dynamically adapt its minimum CW (MCW) parameter to maximize a network-level utility knowing neither the MCWs of other nodes nor how these change over time. To achieve this goal, we adopt a reinforcement learning (RL) framework where we circumvent the lack of system knowledge with local channel observations and we reward actions that lead to high utilities. To efficiently learn these preferred actions, we follow a deep Q-learning approach, where the Q-value function is parametrized using a multi-layer perceptron. In particular, we implement a rainbow agent, which incorporates several empirical improvements over the basic deep Q-network. Numerical experiments based on the NS3 simulator reveal that the proposed RL agent performs close to optimal and markedly improves upon existing learning and non-learning based alternatives.

A fundamental problem in the design of wireless networks is to efficiently schedule transmission in a distributed manner. The main challenge stems from the fact that optimal link scheduling involves solving a maximum weighted independent set (MWIS) problem, which is NP-hard. For practical link scheduling schemes, distributed greedy approaches are commonly used to approximate the solution of the MWIS problem. However, these greedy schemes mostly ignore important topological information of the wireless networks. To overcome this limitation, we propose a distributed MWIS solver based on graph convolutional networks (GCNs). In a nutshell, a trainable GCN module learns topology-aware node embeddings that are combined with the network weights before calling a greedy solver. In small- to middle-sized wireless networks with tens of links, even a shallow GCN-based MWIS scheduler can leverage the topological information of the graph to reduce in half the suboptimality gap of the distributed greedy solver with good generalizability across graphs and minimal increase in complexity.

We take the first step towards understanding the fundamental limits of blind wireless network inference performed by a distributed network of single-antenna adversary nodes. The distributed adversary nodes are assumed to be blind to the protocol parameters as well as the modulation, coding and encryption schemes used by the network being monitored. Focusing on the special case of inferring the channel access probabilities of the monitored nodes, we derive minimax bounds for blind inference. We show that blind inference is possible with similar sample complexity (asymptotically) as non-blind inference given certain network connectivity conditions are satisfied.

Mobile edge computing seeks to provide resources to different delay-sensitive applications. This is a challenging problem as an edge cloud-service provider may not have sufficient resources to satisfy all resource requests. Furthermore, allocating available resources optimally to different applications is also challenging. Resource sharing among different edge cloud-service providers can address the aforementioned limitation as certain service providers may have resources available that can be “rented” by other service providers. However, edge cloud service providers can have different objectives orutilities. Therefore, there is a need for an efficient and effective mechanism to share resources among service providers, while considering the different objectives of various providers. We model resource sharing as a multi-objective optimization problem and present a solution framework based onCooperative Game Theory(CGT). We consider the strategy where each service provider allocates resources to its native applications first and shares the remaining resources with applications from other service providers. We prove that for a monotonic, non-decreasing utility function, the game is canonical and convex. Hence, thecoreis not empty and the grand coalition is stable. We propose two algorithms,Game-theoretic Pareto optimal allocation(GPOA) andPolyandrous-Polygamous Matching based Pareto Optimal Allocation(PPMPOA) that provide allocations from the core. Hence the obtained allocations areParetooptimal and the grand coalition of all the service providers is stable. Experimental results confirm that our proposed resource sharing framework improves utilities of edge cloud-service providers and application request satisfaction.

We study the problem of optimal power allocation in a single-hop ad hoc wireless network. In solving this problem, we depart from classical purely model-based approaches and propose a hybrid method that retains key modeling elements in conjunction with data-driven components. More precisely, we put forth a neural network architecture inspired by the algorithmic unfolding of the iterative weighted minimum mean squared error (WMMSE) method, that we denote by unfolded WMMSE (UWMMSE). The learnable weights within UWMMSE are parameterized using graph neural networks (GNNs), where the time-varying underlying graphs are given by the fading interference coefficients in the wireless network. These GNNs are trained through a gradient descent approach based on multiple instances of the power allocation problem. We show that the proposed architecture is permutation equivariant, thus facilitating generalizability across network topologies. Comprehensive numerical experiments illustrate the performance attained by UWMMSE along with its robustness to hyper-parameter selection and generalizability to unseen scenarios such as different network densities and network sizes.

As Deep Packet Inspection (DPI) middleboxes become increasingly popular, a spectrum of adversarial attacks have emerged with the goal of evading such middleboxes. Many of these attacks exploit discrepancies between the middlebox network protocol implementations, and the more rigorous/complete versions implemented at end hosts. These evasion attacks largely involve subtle manipulations of packets to cause different behaviours at DPI and end hosts, to cloak malicious network traffic that is otherwise detectable. With recent automated discovery, it has become prohibitively challenging to manually curate rules for detecting these manipulations. In this work, we propose CLAP, the first fully-automated, unsupervised ML solution to accurately detect and localize DPI evasion attacks. By learning what we call the packet context, which essentially captures inter-relationships across both (1) different packets in a connection; and (2) different header fields within each packet, from benign traffic traces only, CLAP can detect and pinpoint packets that violate the benign packet contexts (which are the ones that are specially crafted for evasion purposes). Our evaluations with 73 state-of-the-art DPI evasion attacks show that CLAP achieves an Area Under the Receiver Operating Characteristic Curve (AUCROC) of 0.963, an Equal Error Rate (EER) of only 0.061 in detection, and an accuracy of 94.6% in localization. These results suggest that CLAP can be a promising tool for thwarting DPI evasion attacks.

The problem of quickest growing dynamic anomaly detection in sensor networks is studied. Initially, the observations at the sensors, which are sampled sequentially by the decision maker, are generated according to a pre-change distribution. At some unknown but deterministic time instant, a dynamic anomaly emerges in the network, affecting different sets of sensors as time progresses. The observations of the affected sensors are generated from a post-change distribution. It is assumed that the number of affected sensors increases with time, and that only the initial and the final size of the anomaly are known to the decision maker. The goal is to detect the emergence of the anomaly as quickly as possible while guaranteeing a sufficiently low frequency of false alarm (FA) events. This detection problem is posed as a stochastic optimization problem by using a delay metric that is based on the worst possible path of the anomaly. A detection rule is proposed that is asymptotically optimal as the mean time to false alarm goes to infinity. Finally, numerical results are provided to validate our theoretical analysis.

Existing Graph Neural Network (GNN) methods that learn inductive unsupervised graph representations focus on learning node and edge representations by predicting observed edges in the graph. Although such approaches have shown advances in downstream node classification tasks, they are ineffective in jointly representing larger k-node sets, k{>}2. We propose MHM-GNN, an inductive unsupervised graph representation approach that combines joint k-node representations with energy-based models (hypergraph Markov networks) and GNNs. To address the intractability of the loss that arises from this combination, we endow our optimization with a loss upper bound using a finite-sample unbiased Markov Chain Monte Carlo estimator. Our experiments show that the unsupervised joint k-node representations of MHM-GNN produce better unsupervised representations than existing approaches from the literature.

We identify optimal strategies for maximising influence within a social network in competitive settings under budget constraints. While existing work has focussed on simple threshold models, we consider more realistic settings, where (i) states are dynamic, i.e., nodes oscillate between influenced and uninfluenced states, and (ii) continuous amounts of resources (e.g., incentives or effort) can be expended on the nodes.

Effectively representing graph node sequences in the form of vector embeddings is critical to many applications. We achieve this by (i) first learning vector embeddings of single graph nodes and (ii) then composing them to compactly represent node sequences. Specifically, we propose SENSE-S (Semantically Enhanced Node Sequence Embedding - for Single nodes), a skip-gram based novel embedding mechanism, for single graph nodes that co-learns graph structure as well as their textual descriptions. We demonstrate that SENSE-S vectors increase the accuracy of multi-label classification tasks by up to 50% and link-prediction tasks by up to 78% under a variety of scenarios using real datasets. Based on SENSE-S, we next propose generic SENSE to compute composite vectors that represent a sequence of nodes, where preserving the node order is important. We prove that this approach is efficient in embedding node sequences, and our experiments on real data confirm its high accuracy.

The problem of quickest detection of significant events in networks is studied. A distributed setting is investigated, where there is no fusion center, and each node only communicates with its neighbors. After an event occurs in the network, a number of nodes are affected, which changes the statistics of their observations. The nodes may possibly perceive the event at different times. The goal is to design a distributed sequential detection rule that can detect when the event is "significant", i.e., the event has affected no less than η nodes, as quickly as possible, subject to false alarm constraints. A distributed algorithm is proposed, which is based on a novel combination of the alternating direction method of multipliers (ADMM) and average consensus approaches. Numerical results are provided to demonstrate the performance of the proposed algorithm.

In distributed software-defined networks (SDN), multiple physical SDN controllers, each managing a network domain, are implemented to balance centralised control, scalability, and reliability requirements. In such networking paradigms, controllers synchronize with each other, in attempts to maintain a logically centralised network view. Despite the presence of various design proposals for distributed SDN controller architectures, most existing works only aim at eliminating anomalies arising from the inconsistencies in different controllers' network views. However, the performance aspect of controller synchronization designs with respect to given SDN applications are generally missing. To fill this gap, we formulate the controller synchronization problem as a Markov decision process (MDP) and apply reinforcement learning techniques combined with deep neural networks (DNNs) to train a smart, scalable, and fine-grained controller synchronization policy, called the Multi-Armed Cooperative Synchronization (MACS), whose goal is to maximise the performance enhancements brought by controller synchronizations. Evaluation results confirm the DNN's exceptional ability in abstracting latent patterns in the distributed SDN environment, rendering significant superiority to MACS-based synchronization policy, which are 56% and 30% performance improvements over ONOS and greedy SDN controller synchronization heuristics.

Representation learning in heterogeneous graphs aims to pursue a meaningful vector representation for each node so as to facilitate downstream applications such as link prediction, personalized recommendation, node classification, etc. This task, however, is challenging not only because of the demand to incorporate heterogeneous structural (graph) information consisting of multiple types of nodes and edges, but also due to the need for considering heterogeneous attributes or contents (e.g., text or image) associated with each node. Despite a substantial amount of effort has been made to homogeneous (or heterogeneous) graph embedding, attributed graph embedding as well as graph neural networks, few of them can jointly consider heterogeneous structural (graph) information as well as heterogeneous contents information of each node effectively. In this paper, we propose HetGNN, a heterogeneous graph neural network model, to resolve this issue. Specifically, we first introduce a random walk with restart strategy to sample a fixed size of strongly correlated heterogeneous neighbors for each node and group them based upon node types. Next, we design a neural network architecture with two modules to aggregate feature information of those sampled neighboring nodes. The first module encodes "deep" feature interactions of heterogeneous contents and generates content embedding for each node. The second module aggregates content (attribute) embeddings of different neighboring groups (types) and further combines them by considering the impacts of different groups to obtain the ultimate node embedding. Finally, we leverage a graph context loss and a mini-batch gradient descent procedure to train the model in an end-to-end manner. Extensive experiments on several datasets demonstrate that HetGNN can outperform state-of-the-art baselines in various graph mining tasks, i.e., link prediction, recommendation, node classification & clustering and inductive node classification & clustering.

We consider assignment policies that allocate resources to users, where both resources and users are located on a one-dimensional line (0, ∞). First, we consider unidirectional assignment policies that allocate resources only to users located to their left. We propose the Move to Right (MTR) policy, which scans from left to right assigning the nearest available resource located to the right of a user, and contrast it to the Unidirectional Gale-Shapley (UGS) matching policy. While both policies among all unidirectional policies, minimize the expected distance traveled by a request, MTR is fairer. Moreover, we show that when user and resource locations are modeled by statistical point processes, and resources are allowed to satisfy more than one user, the spatial system under unidirectional policies can be mapped into bulk service queueing systems, thus allowing the application of many queueing theory results that yield closed form expressions. As we consider a case where different resources can satisfy different numbers of users, we also generate new results for bulk service queues. We also consider bidirectional policies where there are no directional restrictions on resource allocation and develop an algorithm for computing the optimal assignment which is more efficient than known algorithms in the literature when there are more resources than users. Finally, numerical evaluation of performance of unidirectional and bidirectional allocation schemes yields design guidelines beneficial for resource placement.

We propose a novel confidence metric, namely, attribution-based confidence (ABC) for deep neural networks (DNNs). ABC metric characterizes whether the output of a DNN on an input can be trusted. DNNs are known to be brittle on inputs outside the training distribution and are, hence, susceptible to adversarial attacks. This fragility is compounded by a lack of effectively computable measures of model confidence that correlate well with the accuracy of DNNs. These factors have impeded the adoption of DNNs in high-assurance systems. The proposed ABC metric addresses these challenges. It does not require access to the training data, the use of ensembles, or the need to train a calibration model on a held-out validation set. Hence, the new metric is usable even when only a trained model is available for inference. We mathematically motivate the proposed metric and evaluate its effectiveness with two sets of experiments. First, we study the change in accuracy and the associated confidence over out-of-distribution inputs. Second, we consider several digital and physically realizable attacks such as FGSM, CW, DeepFool, PGD, and adversarial patch generation methods. The ABC metric is low on out-of-distribution data and adversarial examples, where the accuracy of the model is also low. These experiments demonstrate the effectiveness of the ABC metric to make DNNs more trustworthy and resilient.

Modern machine learning systems are susceptible to adversarial examples; inputs which clearly preserve the characteristic semantics of a given class, but whose classification is (usually confidently) incorrect. Existing approaches to adversarial defense generally rely on modifying the input, e.g. quantization, or the learned model parameters, e.g. via adversarial training. However, recent research has shown that most such approaches succumb to adversarial examples when different norms or more sophisticated adaptive attacks are considered. In this paper, we propose a fundamentally different approach which instead changes the way the output is represented and decoded. This simple approach achieves state-of-the-art robustness to adversarial examples for L 2 and L ∞ based adversarial perturbations on MNIST and CIFAR10. In addition, even under strong white-box attacks, we find that our model often assigns adversarial examples a low probability; those with high probability are usually interpretable, i.e. perturbed towards the perceptual boundary between the original and adversarial class. Our approach has several advantages: it yields more meaningful probability estimates, is extremely fast during training and testing, requires essentially no architectural changes to existing discriminative learning pipelines, is wholly complementary to other defense approaches including adversarial training, and does not sacrifice benign test set performance

Representation learning in heterogeneous networks faces challenges due to heterogeneous structural information of multiple types of nodes and relations, and also due to the unstructured attribute or content (e.g., text) associated with some types of nodes. While many recent works have studied homogeneous, heterogeneous, and attributed networks embedding, there are few works that have collectively solved these challenges in heterogeneous networks. In this paper, we address them by developing a Semantic-aware Heterogeneous Network Embedding model (SHNE). SHNE performs joint optimization of heterogeneous SkipGram and deep semantic encoding for capturing both heterogeneous structural closeness and unstructured semantic relations among all nodes, as function of node content, that exist in the network. Extensive experiments demonstrate that SHNE outperforms state-of-the-art baselines in various heterogeneous network mining tasks, such as link prediction, document retrieval, node recommendation, relevance search, and class visualization.

In-Network Processing (INP) is an effective way to aggregate and process data from different sources and forward the aggregated data to other nodes for further processing until it reaches the end user. There is a trade-off between energy consumption for processing data and communication energy spent on transferring the data. An essential requirement in the INP process is to ensure that the user expectation of quality of information (QoI) is delivered during the process. Using wireless sensor networks for illustration and with the aim of minimizing the total energy consumption of the system, we study and formulate the trade-off problem as a nonlinear optimization problem where the goal is to determine the optimal data reduction rate, while satisfying the QoI required by the user. The formulated problem is a Signomial Programming (SP) problem, which is a non-convex optimization problem. We propose two solution frameworks. First, we introduce an equivalent problem which is still SP and non-convex as the original one, but we prove that the strong duality property holds, and propose an efficient distributed algorithm to obtain the optimal data reduction rates, while delivering the required QoI. The second framework applies to the system with identical nodes and parameter settings. In such cases, we prove that the complexity of the problem can be reduced logarithmically. We evaluate our proposed frameworks under different parameter settings and illustrate the validity and performance of the proposed techniques through extensive simulation.

For well over a quarter century, detection systems have been driven by models learned from input features collected from real or simulated environments. An artifact (e.g., network event, potential malware sample, suspicious email) is deemed malicious or non-malicious based on its similarity to the learned model at runtime. However, the training of the models has been historically limited to only those features available at runtime. In this paper, we consider an alternate learning approach that trains models using privileged information--features available at training time but not at runtime--to improve the accuracy and resilience of detection systems. In particular, we adapt and extend recent advances in knowledge transfer, model influence, and distillation to enable the use of forensic or other data unavailable at runtime in a range of security domains. An empirical evaluation shows that privileged information increases precision and recall over a system with no privileged information: we observe up to 7.7% relative decrease in detection error for fast-flux bot detection, 8.6% for malware traffic detection, 7.3% for malware classification, and 16.9% for face recognition. We explore the limitations and applications of different privileged information techniques in detection systems. Such techniques provide a new means for detection systems to learn from data that would otherwise not be available at runtime.

When sensor fusion operations are conducted in coalition environments, security of the data and infrastructure used for model fusion are very important. AI enabled sensor fusion infrastructure can be attacked on many fronts, including attacks on the data used for sensor information fusion and disrupting the communication between devices and the fusion nodes, in addition to the traditional security attacks. As the infrastructure for sensor fusion becomes more automated with multiple intelligent assistants for data collection, different types of attacks are possible. AI enabled approaches can be used to improve the security and resiliency of federated networks, and the data that is shared across coalition problems. In this paper, we discuss the challenges associated with security of coalition infrastructures, and approaches to improve the security using AI and machine learning techniques.

Malicious coresidency is a precursor to side-channel attacks that target information leakage. In this paper, we seek to understand the interactions between a defender (the cloud service provider) who tries to detect malicious coresidency by an attacker, who in turn attempts to co-reside its VM with a victim VM on the same physical machine by exploiting the VM allocation policy employed by the cloud service provider while at the same time, trying to evade detection. The problem is modeled as a two-player game. Specifically, the attacker chooses how long to keep its VM operational before terminating and relaunching it to increase its odds of success. On the other hand, the defender attempts to detect and penalize malicious VMs based on their activity in a given time window. The defender estimates a maliciousness measure for all active VMs which then modulates the likelihood of a specific VM being migrated to a different physical machine. We study the equilibrium strategies for both players for different ranges of environment parameters and show the non-existence of equilibrium with pure strategies. Subsequently, we characterize the equilibrium of the game with mixed strategies.

Energy efficiency is a fundamental requirement of modern data communication systems, and its importance is reflected in much recent work on performance analysis of system energy consumption. However, most works have only focused on communication and computation costs, but do not account for caching costs. Given the increasing interest in cache networks, this is a serious limitation. In this paper, we consider the energy consumption trade-off between communication, computation, and caching (C3) under a Quality of Information (QoI) guarantee in a communication network. To attain this goal, we formulate an optimization problem to capture the C3 costs, which turns out to be a non-convex Mixed Integer Non-Linear Programming (MINLP) Problem. We then propose a variant of spatial branch and bound algorithm (V-SBB), that can achieve ε -global optimal solution to the original MINLP. We show numerically that V-SBB is more stable and robust than other candidate MINLP solvers under different network scenarios. More importantly, we observe that the energy efficiency under our C3 optimization framework improves by as much as 88% compared to any C2 optimization between communication and computation or caching.

An upcoming frontier for distributed computing might literally save lives in future military operations. In civilian scenarios, significant efficiencies were gained from interconnecting devices into networked services and applications that automate much of everyday life from smart homes to intelligent transportation. The ecosystem of such applications and services is collectively called the Internet of Things (IoT). Can similar benefits be gained in a military context by developing an IoT for the battlefield? This paper describes unique challenges in such a context as well as potential risks, mitigation strategies, and benefits.

Network centrality plays an important role in many applications. Central nodes in social networks can be influential, driving opinions and spreading news or rumors. In hyperlinked environments, such as the Web, where users navigate via clicks, central content receives high traffic, becoming target for advertising campaigns. While there is an extensive amount of work on centrality measures and their efficient computation, controlling nodes' centrality via network updates is a more recent and challenging task. Performing minimal modifications to a network to achieve a desired property falls under the umbrella of network design problems. This paper is focused on improving group (coverage and betweenness) centrality, which is a function of the shortest paths passing through a set of nodes, by adding edges to the network. Several variations of the problem, which are NP-hard as well as APX-hard, are introduced. We present a greedy algorithm, and even faster sampling algorithms, for group centrality maximization with theoretical quality guarantees under realistic constraints. The experimental results show that our sampling algorithms outperform the best baseline solution in terms of centrality by up to 5 times while being 2–3 orders of magnitude faster than our greedy approach.

Event-based social network (EBSN) services have emerged as a new platform on which users can choose events of interest to attend in the physical world. Over years, there are growing research interests in predicting whether certain actors will participate in an event together. In this work, we refer to this task as the event attendance prediction problem and aim to address the predictability of individuals' event attendance. In real-world settings, the factors that influence an individual's attendance may change over time, leading to the dynamic nature of individuals' behavior. However, existing event attendance prediction methods cannot deal with such dynamic scenarios. To address this issue, we propose an end-to-end Deep Event Attendance Prediction (DEAP) framework—a three-level hierarchical LSTM architecture—to explicitly model users' multi-dimensional and evolving preferences. Extensive experiments on three real-world datasets demonstrate that DEAP significantly outperforms the state-of-the-art techniques across various settings.

We consider the problem of optimally compressing and caching data across a communication network. Given the data generated at edge nodes and a routing path, our goal is to determine the optimal data compression ratios and caching decisions across the network in order to minimize average latency, which can be shown to be equivalent to maximizing the compression and caching gain under an energy consumption constraint. We show that this problem is NP-hard in general and the hardness is caused by the caching decision subproblem, while the compression sub-problem is polynomial-time solvable. We then propose an approximation algorithm that achieves a $(1-1/e)$-approximation solution to the optimum in strongly polynomial time. We show that our proposed algorithm achieve the near-optimal performance in synthetic-based evaluations. In this paper, we consider a tree-structured network as an illustrative example, but our results easily extend to general network topology at the expense of more complicated notations.

The sparsest cut problem consists of identifying a small set of edges that breaks the graph into balanced sets of vertices. The normalized cut problem balances the total degree, instead of the size, of the resulting sets. Applications of graph cuts include community detection and computer vision. However, cut problems were originally proposed for static graphs, an assumption that does not hold in many modern applications where graphs are highly dynamic. In this paper, we introduce sparsest and normalized cuts in temporal graphs, which generalize their standard definitions by enforcing the smoothness of cuts over time. We propose novel formulations and algorithms for computing temporal cuts using spectral graph theory, divide-and-conquer and low-rank matrix approximation. Furthermore, we extend temporal cuts to dynamic graph signals, where vertices have attributes. Experiments show that our solutions are accurate and scalable, enabling the discovery of dynamic communities and the analysis of dynamic graph processes.

We propose a context-aware trust management model called CATrust for service-oriented ad hoc networks such as peer-to-peer and Internet of Things networks wherein a node can be a service requester or a service provider. The novelty of our design lies in the use of logistic regression to dynamically estimate trustworthiness of a service provider based on its service behavior patterns in response to context environment changes. We develop a recommendation filtering mechanism to effectively screen out dishonest recommendations even in extremely hostile environments in which the majority recommenders are dishonest. We demonstrate desirable convergence, accuracy, and resiliency properties of CATrust. We also demonstrate that CATrust outperforms contemporary peer-to-peer and Internet of Things trust models in terms of service trust prediction accuracy against collusion recommendation attacks.

Machine learning (ML) models, e.g., deep neural networks (DNNs), are vulnerable to adversarial examples: malicious inputs modified to yield erroneous model outputs, while appearing unmodified to human observers. Potential attacks include having malicious content like malware identified as legitimate or controlling vehicle behavior. Yet, all existing adversarial example attacks require knowledge of either the model internals or its training data. We introduce the first practical demonstration of an attacker controlling a remotely hosted DNN with no such knowledge. Indeed, the only capability of our black-box adversary is to observe labels given by the DNN to chosen inputs. Our attack strategy consists in training a local model to substitute for the target DNN, using inputs synthetically generated by an adversary and labeled by the target DNN. We use the local substitute to craft adversarial examples, and find that they are misclassified by the targeted DNN. To perform a real-world and properly-blinded evaluation, we attack a DNN hosted by MetaMind, an online deep learning API. We find that their DNN misclassifies 84.24% of the adversarial examples crafted with our substitute. We demonstrate the general applicability of our strategy to many ML techniques by conducting the same attack against models hosted by Amazon and Google, using logistic regression substitutes. They yield adversarial examples misclassified by Amazon and Google at rates of 96.19% and 88.94%. We also find that this black-box attack strategy is capable of evading defense strategies previously found to make adversarial example crafting harder.

We have recently seen an increasing number of attacks that are distributed, and span an entire wide area network (WAN). Today, typically, intrusion detection systems (IDSs) are deployed at enterprise scale and cannot handle attacks that cover a WAN. Moreover, such IDSs are implemented at a single entity that expects to look at all packets to determine an intrusion. Transferring copies of raw packets to centralized engines for analysis in a WAN can significantly impact both network performance and detection accuracy. In this paper, we propose Jaal, a framework for achieving accurate network intrusion detection at scale. The key idea in Jaal is to monitor traffic and construct in-network packet summaries. The summaries are then processed centrally to detect attacks with high accuracy. The main challenges that we address are (a) creating summaries that are concise, but sufficient to draw highly accurate inferences and (b) transforming traditional IDS rules to handle summaries instead of raw packets. We implement Jaal on a large scale SDN testbed. We show that on average Jaal yields a detection accuracy of about 98%, which is the highest reported for ISP scale network intrusion detection. At the same time, the overhead associated with transferring summaries to the central inference engine is only about 35% of what is consumed if raw packets are transferred.

Incentive-driven advanced attacks have become a major concern to cyber-security. Traditional defense techniques that adopt a passive and static approach by assuming a fixed attack type are insufficient in the face of highly adaptive and stealthy attacks. In particular, a passive defense approach often creates information asymmetry where the attacker knows more about the defender. To this end, moving target defense (MTD) has emerged as a promising way to reverse this information asymmetry. The main idea of MTD is to (continuously) change certain aspects of the system under control to increase the attacker's uncertainty, which in turn increases attack cost/complexity and reduces the chance of a successful exploit in a given amount of time. In this paper, we go one step beyond and show that MTD can be further improved when combined with information disclosure. In particular, we consider that the defender adopts a MTD strategy to protect a critical resource across a network of nodes, and propose a Bayesian Stackelberg game model with the defender as the leader and the attacker as the follower. After fully characterizing the defender's optimal migration strategies, we show that the defender can design a signaling scheme to exploit the uncertainty created by MTD to further affect the attacker's behavior for its own advantage. We obtain conditions under which signaling is useful, and show that strategic information disclosure can be a promising way to further reverse the information asymmetry and achieve more efficient active defense.

We study the problem of representation learning in heterogeneous networks. Its unique challenges come from the existence of multiple types of nodes and links, which limit the feasibility of the conventional network embedding techniques. We develop two scalable representation learning models, namely metapath2vec and metapath2vec++. The metapath2vec model formalizes meta-path-based random walks to construct the heterogeneous neighborhood of a node and then leverages a heterogeneous skip-gram model to perform node embeddings. The metapath2vec++ model further enables the simultaneous modeling of structural and semantic correlations in heterogeneous networks. Extensive experiments show that metapath2vec and metapath2vec++ are able to not only outperform state-of-the-art embedding models in various heterogeneous network mining tasks, such as node classification, clustering, and similarity search, but also discern the structural and semantic correlations between diverse network objects.

We study the problem of network topology design within a set of policy-compliant topologies as a game between a designer and an adversary. At any time instant, the designer aims to operate the network in an optimal topology within the set of policy compliant topologies with respect to a desired network property. Simultaneously, the adversary counters the designer trying to force operation in a suboptimal topology. Specifically, if the designer and the attacker choose the same link in the current topology to defend/grow and attack, respectively, then the latter is thwarted. However, if the defender does not correctly guess where the attacker is going to attack, and, hence, acts elsewhere, the topology reverts to the best policy-compliant configuration after a successful attack. We show the existence of various mixed strategy equilibria in this game and systematically study its structural properties. We study the effect of parameters, such as probability of a successful attack, and characterize the steady state behavior of the underlying Markov chain. While the intuitive adversarial strategy here is to attack the most important links, the Nash equilibrium strategy is for the designer to defend the most crucial links and for the adversary to focus attack on the lesser crucial links. We validate these properties through two use cases with example sets of network topologies. Next, we consider a multi-stage framework where the designer is not only interested in the instantaneous network property costs but a discounted sum of costs over many time instances. We establish structural properties of the equilibrium strategies in the multi-stage setting, and also demonstrate that applying algorithms based on the Q-Learning and Rollout methods can result in significant benefits for the designer compared with strategies resulting from a one-shot based game.

We consider the problem of placing the minimum number of monitors in a dynamic network to identify additive link metrics from path metrics measured along cycle-free paths between monitors. Our goal is robust monitor placement, i.e., the same set of monitors can maintain network identifiability under topology changes. Our main contribution is a set of monitor placement algorithms with different performance-complexity tradeoffs that can simultaneously identify multiple topologies occurring during the network lifetime. In particular, we show that the optimal monitor placement is the solution to a generalized hitting set problem, for which we provide a polynomial-time algorithm to construct the input and a greedy algorithm to select the monitors with logarithmic approximation. Although the optimal placement is NP-hard in general, we identify non-trivial special cases that can be solved efficiently. Our secondary contribution is a dynamic triconnected decomposition algorithm to compute the input needed by the monitor placement algorithms, which is the first such algorithm that can handle edge deletions. Our evaluations on mobility-induced dynamic topologies verify the efficiency and the robustness of the proposed algorithms.

We investigate the capability of localizing node failures in communication networks from binary states (normal/failed) of end-to-end paths. Given a set of nodes of interest, uniquely localizing failures within this set requires that different observable path states associate with different node failure events. However, this condition is difficult to test on large networks due to the need to enumerate all possible node failures. Our first contribution is a set of sufficient/necessary conditions for identifying a bounded number of failures within an arbitrary node set that can be tested in polynomial time. In addition to network topology and locations of monitors, our conditions also incorporate constraints imposed by the probing mechanism used. We consider three probing mechanisms that differ according to whether measurement paths are: (i) arbitrarily controllable; (ii) controllable but cycle-free; or (iii) uncontrollable (determined by the default routing protocol). Our second contribution is to quantify the capability of failure localization through: 1) the maximum number of failures (anywhere in the network) such that failures within a given node set can be uniquely localized and 2) the largest node set within which failures can be uniquely localized under a given bound on the total number of failures. Both measures in 1) and 2) can be converted into the functions of a per-node property, which can be computed efficiently based on the above sufficient/necessary conditions. We demonstrate how measures 1) and 2) proposed for quantifying failure localization capability can be used to evaluate the impact of various parameters, including topology, number of monitors, and probing mechanisms.

With the proliferation of fairly powerful mobile devices and ubiquitous wireless technology, we see a transformation from traditional mobile ad hoc networks (MANETs) into a new era of service-oriented MANETs wherein a node can provide and receive services. Requested services must be decomposed into more abstract services and then bound; we formulate this as a multi-objective optimization (MOO) problem to minimize the service cost, while maximizing the quality of service and quality of information in the service a user receives. The MOO problem is an SP-to-service assignment problem. We propose a multidimensional trust based algorithm to solve the problem. We carry out an extensive suite of simulations to test the relative performance of the proposed trust-based algorithm against a non-trust-based counterpart and an existing single-trust-based beta reputation scheme. Our proposed algorithm effectively filters out malicious nodes exhibiting various attack behaviors by penalizing them with loss of reputation, which ultimately leads to high user satisfaction. Further, our proposed algorithm is efficient with linear runtime complexity while achieving a close-to-optimal solution.

While stochastic geometric models based on Poisson point processes (PPPs) provide a tractable approach for the analysis of uniform two-tier network deployments, the performance evaluation of a non-uniform deployment remains an open issue, which we address in this paper. This is due to the fact that smaller cells can be more efficiently deployed in areas where the QoS of traditional macro base stations is poor. Therefore, in this paper, we introduce Stienen's model, which allows us to analyse such non-uniform deployment. In contrast to traditional PPP-based analysis, performance characterization under the Stienen model is more challenging due to location and density dependencies. However, we demonstrate that the performance can be approximated in a tractable manner. The developed statistical framework is employed to characterize the gains in terms of energy efficiency (EE) for non-uniform deployments. Results show an achievable 19% to 124% improvement in the macrocell coverage as compared to a uniform deployment, while the femtocell coverage and system EE are of the same order of magnitude for both deployments. These results are complemented with the fact that OPEX and CAPEX are reduced due to a lesser number of FAPs deployed.

This paper studies wireless networks with multiple real-time flows that have stringent requirements on both per-packet delay and long-term average delivery ratio. Each flow dynamically adjusts its traffic load based on its observation of network status. When the requirements of per-packet delay and delivery ratio are satisfied, each flow obtains some utility based on its traffic load. We aim to design joint rate control and scheduling policies that maximize the total utility in the system. We first show that the problem of maximizing total utility can be formulated as a submodular optimization problem with exponentially many constraints. We then propose two simple distributed policies that require almost no coordination between different entities in the network. The total utilities under these two policies can be made arbitrarily close to the theoretical upper-bound. Extensive simulations also show that they achieve much better performance than state-of-the-art policies.

We study the interactive compression of an arbitrary function of two discrete sources with zero-error. The information on the joint distribution of the sources available at the two sides is asymmetric, in that one user knows the true distribution, whereas the other user observes a different distribution. This paper considers the minimum worst-case zero-error codeword length under such asymmetric prior distributions. We investigate the cases for which reconciling the information mismatch is better or worse than not reconciling it, but instead using an encoding scheme that ensures zero-error with possibly increased communication rate. Our results indicate a reconciliation-communication tradeoff and that there exist cases for which partially reconciling the mismatched information is better than both perfect reconciliation and no reconciliation.

Deep learning takes advantage of large datasets and computationally efficient training algorithms to outperform other approaches at various machine learning tasks. However, imperfections in the training phase of deep neural networks make them vulnerable to adversarial samples: inputs crafted by adversaries with the intent of causing deep neural networks to misclassify. In this work, we formalize the space of adversaries against deep neural networks (DNNs) and introduce a novel class of algorithms to craft adversarial samples based on a precise understanding of the mapping between inputs and outputs of DNNs. In an application to computer vision, we show that our algorithms can reliably produce samples correctly classified by human subjects but misclassified in specific targets by a DNN with a 97% adversarial success rate while only modifying on average 4.02% of the input features per sample. We then evaluate the vulnerability of different sample classes to adversarial perturbations by defining a hardness measure. Finally, we describe preliminary work outlining defenses against adversarial samples by defining a predictive measure of distance between a benign input and a target classification.

We study optimal monitor placement for intrusion detection in networks with persistent attackers. The problem is modeled as a stochastic game in which the attacker attempts to control targets by delivering malicious packets while the defender tries to detect such attempts. The state of the game is determined by the target end-systems in the network, each of which can be in either a healthy or a compromised state. Compromised targets are controlled by the attacker and may be used to inject malicious packets into the network to attack healthy targets. In addition, a random re-imaging process is deployed on all targets to regain control of compromised targets. We find the game value and the equilibrium strategies for both players under different assumptions on the knowledge of the state at the defender.

We study how to communicate semantic information in the presence of an agent that can influence the decoder by providing side information. The agent's true intentions, which may be adversarial or helpful, is unknown to the communicating parties. Actions taken by the agent are governed by its intentions, and they may improve or deteriorate the communication performance. We characterize the optimal transmission policies to minimize the end-to-end average semantic error, i.e., difference between the meanings of intended and recovered messages, under the uncertainty in the agent's true intentions. We formulate the semantic communication problem as a Bayesian game, and investigate the conditions under which a pure strategy Bayesian Nash equilibrium exists. We then explore the structure of the encoding and decoding functions under the mixed strategy Bayesian Nash equilibrium, which for the semantic communication problem at hand always exists. Our results show that the optimal policies are strongly influenced by the belief the parties hold about the agent's true intention.

Detecting a small number of outliers from a set of data observations is always challenging. This problem is more difficult in the setting of multiple network samples, where computing the anomalous degree of a network sample is generally not sufficient. In fact, explaining why a given network is exceptional, expressed in the form of subnetwork, is also equally important. We develop a novel algorithm to address these two key problems. We treat each network sample as a potential outlier and identify subnetworks that help discriminate it from nearby samples. The algorithm is developed in the framework of network regression combined with the constraints on both network topology and L1-norm shrinkage to perform subnetwork discovery. Our method thus goes beyond subspace/subgraph discovery. We also show that the developed method converges to a global optimum. Empirical evaluation on various real-world network datasets demonstrates the advantages of our algorithm over various baseline methods.

We consider the problem of placing the minimum number of monitors in a communication network with possible topology changes to identify additive link metrics from path metrics. The core of our solution is a suite of robust monitor placement algorithms with different performance-complexity tradeoffs that guarantee network identifiability for the multiple possible topologies. In particular, we show that the optimal (i.e., minimum) monitor placement is the solution to a generalized hitting set problem, where we provide a polynomial-time algorithm to construct the input. Although the optimal placement is NP-hard in general, we identify non-trivial special cases that can be solved efficiently. We further demonstrate how the proposed algorithms can be augmented to handle unpredictable topology changes and tradeoffs between monitor cost and adaptation cost. Our evaluations on mobility-induced dynamic topologies verify the effectiveness and robustness of the proposed algorithms.

Modeling information that resides on vertices of large graphs is a key problem in several real-life applications, ranging from social networks to the Internet-of-things. Signal Processing on Graphs and, in particular, graph wavelets can exploit the intrinsic smoothness of these datasets in order to represent them in a compact and accurate manner. However, how to discover wavelet bases that capture the geometry of the data with respect to the signal as well as the graph structure remains an open problem. In this paper, we study the problem of computing graph wavelet bases via sparse cuts in order to produce low-dimensional encodings of data-driven bases. This problem is connected to known hard problems in graph theory (e.g. multiway cuts) and thus requires an efficient heuristic. We formulate the basis discovery task as a relaxation of a vector optimization problem, which leads to an elegant solution as a regularized eigenvalue computation. Moreover, we propose several strategies in order to scale our algorithm to large graphs. Experimental results show that the proposed algorithm can effectively encode both the graph structure and signal, producing compressed and accurate representations for vertex values in a wide range of datasets (e.g. sensor and gene networks) and significantly outperforming the best baseline.

Data aggregation techniques exploit spatial and temporal correlations among data and aggregate data into a smaller volume as a means to optimize usage of limited network resources including energy. There is a trade-off among the Quality of Information (QoI) requirement and energy consumption for computation and communication. We formulate the energy-efficient data aggregation problem as a non-linear optimization problem to optimize the trade-off and control the degree of information reduction at each node subject to given QoI requirement. Using the theory of duality optimization, we prove that under a set of reasonable cost assumptions, the optimal solution can be obtained despite non-convexity of the problem. Moreover, we propose a distributed, iterative algorithm that will converge to the optimal solution. Extensive numerical results are presented to confirm the validity of the proposed solution approach.

Deep learning algorithms have been shown to perform extremely well on many classical machine learning problems. However, recent studies have shown that deep learning, like other machine learning techniques, is vulnerable to adversarial samples: inputs crafted to force a deep neural network (DNN) to provide adversary-selected outputs. Such attacks can seriously undermine the security of the system supported by the DNN, sometimes with devastating consequences. For example, autonomous vehicles can be crashed, illicit or illegal content can bypass content filters, or biometric authentication systems can be manipulated to allow improper access. In this work, we introduce a defensive mechanism called defensive distillation to reduce the effectiveness of adversarial samples on DNNs. We analytically investigate the generalizability and robustness properties granted by the use of defensive distillation when training DNNs. We also empirically study the effectiveness of our defense mechanisms on two DNNs placed in adversarial settings. The study shows that defensive distillation can reduce effectiveness of sample creation from 95% to less than 0.5% on a studied DNN. Such dramatic gains can be explained by the fact that distillation leads gradients used in adversarial sample creation to be reduced by a factor of 1030. We also find that distillation increases the average minimum number of features that need to be modified to create adversarial samples by about 800% on one of the DNNs we tested.

We propose a framework for optimizing in-network processing (INP) in wireless sensor networks. INP provides a platform for processing (e.g., fusing, aggregating or compressing) the data along the transmission routes in the sensor network. This can reduce the volume of transmitted data, therefore optimizing the utilization of energy and bandwidth. However, such data processing must ensure that the end result can meet given QoI requirements. We formulate the QoI-aware INP problem as a non-linear optimization problem to identify the optimal degree of data compression at each sensor node subject to satisfying a QoI requirement for the end-user. The formulation arranges all involved sensor nodes in a tree where data is transfered and processed from nodes to their parent nodes toward the root node of the tree. Under the assumption of uniform parameter setting, we show that the processing tree can be collapsed into a linear graph where the number of nodes represents the node levels of the original processing tree. This represents a significant reduction in complexity of the problem. Numerical example are provided to illustrate the performance of the proposed approach.

We study the problem of network topology design within a sequence of policy-compliant topologies as a game between a designer and an adversary. At any time instant, the designer aims to operate the network in an optimal topology within this policy compliant sequence with respect to a desired network property. Simultaneously, the adversary counters the designer trying to force operation in a suboptimal topology. We show the existence of various mixed strategy equilibria in this game and systematically study its structural properties. We study the effect of parameters, and characterize the steady state behavior of the underlying Markov chain. While the intuitive adversarial strategy here is to attack links appearing early in the topology sequence, the Nash Equilibrium strategy is for the designer to defend the earlier links and for the adversary to attack the later links. We validate these properties through two use cases with example sets of network topologies.

We present a framework and a set of algorithms for determining faults in networks when large scale outages occur. The design principles of our algorithm, netCSI, are motivated by the fact that failures are geographically clustered in such cases. We address the challenge of determining faults with incomplete symptom information due to a limited number of reporting nodes. netCSI consists of two parts: a hypotheses generation algorithm, and a ranking algorithm. When constructing the hypothesis list of potential causes, we make novel use of positive and negative symptoms to improve the precision of the results. In addition, we propose pruning and thresholding along with a dynamic threshold value selector, to reduce the complexity of our algorithm. The ranking algorithm is based on conditional failure probability models that account for the geographic correlation of the network objects in clustered failures. We evaluate the performance of netCSI for networks with both random and realistic topologies. We compare the performance of netCSI with an existing fault diagnosis algorithm, MAX-COVERAGE, and demonstrate an average gain of 128 percent in accuracy for realistic topologies.

We study the problem of minimizing the scheduling time length to serve users' traffic demand by link scheduling in multi-hop mmWave wireless networks. We formulate a constrained Binary Integer Programming (BIP) problem incorporating a flexible interference model for directional transmissions and a Markov chain based blockage model. Since the problem is NP hard, we propose a heuristic algorithm with greatly reduced complexity, which first finds the optimal streaming path for each data flow and then maximizes the instant network throughput by optimizing the link scheduling at each time slot. The performance of the heuristic algorithm is validated with simulations.

We consider the problem of sampling a node-weighted graph. The objective is to infer the values of all nodes from that of a minimum subset of nodes by exploiting correlations in node values. We first introduce the concept of information dominating set (IDS). A subset of nodes in a given graph is an IDS if the value of these nodes is sufficient to infer the information state of the entire graph. We focus on two fundamental algorithmic problems: (i) how to determine whether a given subset of vertices is an IDS; (ii) how to construct a minimum IDS. Assuming binary node values and the local majority rule, we show that the first problem is co-NP-complete and the second problem is NP-hard in a general network. We then show that in acyclic graphs, both problems admit linear-complexity solutions by establishing a connection between the IDS problems and the vertex cover problem. For general graphs, we develop algorithms for solving both problems based on the concept of essential differential set. These results find applications in opinion sampling such as political polling and market survey in social-economic networks, and inferring epidemics and cascading failures in communication and infrastructure networks.

The heterogeneous and dynamic nature of tactical coalition networks poses several challenges to common network management tasks, due to the lack of complete and accurate network information. In this paper, we consider the problem of redeploying services in mobile tactical networks. We propose M-iTop, an algorithm for inferring the network topology when only partial information is available. M-iTop initially constructs a virtual topology that overestimates the number of network components, and then repeatedly merges links in this topology to resolve it towards the structure of the true network. We perform extensive simulations and show that M-iTop enables an efficient redeployment of services over the network despite the limitation of partial information.

We study the problem of maximizing the multicast throughput in a dense multi-channel multi-radio (MC-MR) wireless network with multiple multicast sessions. Specifically, we consider a fully connected network topology where all nodes are within transmission range of each other. In spite of its simplicity, this topology is practically important since it is encountered in several real-world settings. Further, a solution to this network can serve as a building block for more general scenarios that are otherwise intractable. For this network, we show that the problem of maximizing the uniform multicast throughput across multiple sessions is NP-hard. However, its special structure allows us to derive useful upper bounds on the achievable uniform multicast throughput. We show that an intuitive class of algorithms that maximally exploit the wireless broadcast feature can result in very poor worst case performance. Using a novel group splitting idea, we then design two polynomial time approximation algorithms that are guaranteed to achieve a constant factor of the throughput bound under arbitrary multicast group memberships. These algorithms are simple to implement and provide interesting tradeoffs between the achievable throughput and the total number of transmissions used.

Network tomography aims to infer the individual performance of networked elements (e.g., links) using aggregate measurements on end-to-end paths. Previous work on network tomography focuses primarily on developing estimators using the given measurements, while the design of measurements is often neglected. We fill this gap by proposing a framework to design probing experiments with focus on probe allocation, and applying it to two concrete problems: packet loss tomography and packet delay variation (PDV) tomography. Based on the Fisher Information Matrix (FIM), we design the distribution of probes across paths to maximize the best accuracy of unbiased estimators, asymptotically achievable by the maximum likelihood estimator. We consider two widely-adopted objective functions: determinant of the inverse FIM (D-optimality) and trace of the inverse FIM (A-optimality). We also extend the A-optimal criterion to incorporate heterogeneity in link weights. Under certain conditions on the FIM, satisfied by both loss and PDV tomography, we derive explicit expressions for both objective functions. When the number of probing paths equals the number of links, these lead to closed-form solutions for the optimal design; when there are more paths, we develop a heuristic to select a subset of paths and optimally allocate probes within the subset. Observing the dependency of the optimal design on unknown parameters, we further propose an algorithm that iteratively updates the design based on parameter estimates, which converges to the design based on true parameters as the number of probes increases. Using packet-level simulations on real datasets, we verify that the proposed design effectively reduces estimation error compared with the common approach of uniformly distributing probes.

Full knowledge of the routing topology of the Internet is useful for a multitude of network management tasks. However, the full topology is often not known and is instead estimated using topology inference algorithms. Many of these algorithms use Traceroute to probe paths and then use the collected information to infer the topology. We perform real experiments and show that, in practice, routers may severely disrupt the operation of Traceroute and cause it to only provide partial information. We propose iTop, an algorithm for inferring the network topology when only partial information is available. iTop constructs a virtual topology, which overestimates the number of network components, and then repeatedly merges links in this topology to resolve it toward the structure of the true network. We perform extensive simulations to compare iTop to state-of-the-art inference algorithms. Results show that iTop significantly outperforms previous approaches and its inferred topologies are within 5% of the original networks for all considered metrics. Additionally, we show that the topologies inferred by iTop significantly improve the performance of fault localization algorithms when compared with other approaches.

A hypergraph is a set V of vertices and a set of nonempty subsets of V, called hyperedges. Unlike graphs, hypergraphs can capture higher-order interactions in social and communication networks that go beyond a simple union of pairwise relationships. In this paper, we consider the shortest path problem in hypergraphs. We develop two algorithms for finding and maintaining the shortest hyperpaths in a dynamic network with both weight and topological changes. These two algorithms are the first to address the fully dynamic shortest path problem in a general hypergraph. They complement each other by partitioning the application space based on the nature of the change dynamics and the type of the hypergraph. We analyze the time complexity of the proposed algorithms and perform simulation experiments for random geometric hypergraphs, energy efficient routing in multichannel multiradio networks, and the Enron email data set. The experiment with the Enron email data set illustrates the application of the proposed algorithms in social networks for identifying the most important actor and the latent social relationship based on the closeness centrality metric.

We formulate and study the thinnest path problem for secure communication in wireless ad hoc networks. The objective is to find a path from a source to its destination that results in the minimum number of nodes overhearing the message by a judicious choice of relaying nodes and their corresponding transmission powers. We adopt a directed hypergraph model of the problem and establish the NP-completeness of the problem in 2-D networks. We then develop two polynomial-time approximation algorithms that offer √(n/2) and n/2√(n-1) approximation ratios for general directed hypergraphs (which can model nonisotropic signal propagation in space) and constant approximation ratios for ring hypergraphs (which result from isotropic signal propagation). We also consider the thinnest path problem in 1-D networks and 1-D networks embedded in a 2-D field of eavesdroppers with arbitrary unknown locations (the so-called 1.5-D networks). We propose a linear-complexity algorithm based on nested backward induction that obtains the optimal solution for both 1-D and 1.5-D networks. This algorithm does not require the knowledge of eavesdropper locations and achieves the best performance offered by any algorithm that assumes complete location information of the eavesdroppers.

We propose a greedy algorithm, Cluster-MAX-COVERAGE (CMC), to efficiently diagnose large-scale clustered failures. We primarily address the challenge of determining faults with incomplete symptoms. CMC makes novel use of both positive and negative symptoms to output a hypothesis list with a low number of false negatives and false positives quickly. CMC requires reports from about half as many nodes as other existing algorithms to determine failures with 100 percent accuracy. Moreover, CMC accomplishes this gain significantly faster (sometimes by two orders of magnitude) than an algorithm that matches its accuracy. When there are fewer positive and negative symptoms at a reporting node, CMC performs much better than existing algorithms. We also propose an adaptive algorithm called Adaptive-MAX-COVERAGE (AMC) that performs efficiently during both independent and clustered failures. During a series of failures that include both independent and clustered, AMC results in a reduced number of false negatives and false positives.

We investigate the problem of localizing node failures in a communication network from end-to-end path measurements, under the assumption that a path behaves normally if and only if it does not contain any failed nodes. To uniquely localize node failures, the measurement paths must show different symptoms under different failure events, i.e., for any two distinct sets of failed nodes, there must be a measurement path traversing one and only one of them. This condition is, however, impractical to test for large networks. Our first contribution is a characterization of this condition in terms of easily verifiable conditions on the network topology with given monitor placements under three families of probing mechanisms, which differ in whether measurement paths are (i) arbitrarily controllable, (ii) controllable but cycle-free, or (iii) uncontrollable (i.e., determined by the default routing protocol). Our second contribution is a characterization of the maximum identifiability of node failures, measured by the maximum number of simultaneous failures that can always be uniquely localized. Specifically, we bound the maximal identifiability from both the upper and the lower bounds which differ by at most one, and show that these bounds can be evaluated in polynomial time. Finally, we quantify the impact of the probing mechanism on the capability of node failure localization under different probing mechanisms on both random and real network topologies. We observe that despite a higher implementation cost, probing along controllable paths can significantly improve a network's capability to localize simultaneous node failures.

We investigate the problem of placing a given number of monitors in a communication network to identify the maximum number of link metrics from end-to-end measurements between monitors, assuming that link metrics are additive, and measurement paths cannot contain cycles. Motivated by our previous result that complete identification of all link metrics can require a large number of monitors, we focus on partial identification using a limited number of monitors. The basis to our solution is an efficient algorithm for determining all identifiable links for a given monitor placement. Based on this algorithm, we develop a polynomial-time greedy algorithm to incrementally place monitors such that each newly placed monitor maximizes the number of additional identifiable links. We prove that the proposed algorithm is optimal for 2-vertex-connected networks, and demonstrate that it is near-optimal for several real ISP topologies that are not 2-vertex-connected. Our solution provides a quantifiable tradeoff between level of identifiability and available monitor resources.

In-network processing (INP) is a promising method that allows aggregation of data while it is being transferred along the communication paths as a means to optimize the utilization of network resources without violating the quality of information (QoI) requirements. Given the large amount of data existing in dynamic environments, the optimization of INP requires a distributed framework that can adapt easily to network changes and user requirements. In this work, we develop the principle for designing a distributed mechanism in order to determine and control INP. Specifically, the proposed framework can decide, in a distributed way, which nodes along the communication paths optimally perform INP, with consideration of operational energy consumption and QoI requirements for achieving global optimal INP. The significance of the proposed distributed method is that it requires each node to make independent decisions locally for data aggregations, thus naturally enhance robustness and efficiency against network and data load dynamics. Extensive numerical results are presented to confirm the validity of the proposed approach.

We investigate the problem of identifying individual link metrics in a communication network from end-to-end path measurements, under the assumption that link metrics are additive and constant. To uniquely identify the link metrics, the number of linearly independent measurement paths must equal the number of links. Our contribution is to characterize this condition in terms of the network topology and the number/placement of monitors, under the constraint that measurement paths must be cycle-free. Our main results are: 1) it is generally impossible to identify all the link metrics by using two monitors; 2) nevertheless, metrics of all the interior links not incident to any monitor are identifiable by two monitors if the topology satisfies a set of necessary and sufficient connectivity conditions; 3) these conditions naturally extend to a necessary and sufficient condition for identifying all the link metrics using three or more monitors. We show that these conditions not only facilitate efficient identifiability tests, but also enable an efficient algorithm to place the minimum number of monitors in order to identify all link metrics. Our evaluations on both random and real topologies show that the proposed algorithm achieves identifiability using a much smaller number of monitors than a baseline solution.

In an ad hoc cognitive radio network, secondary users access channels temporarily unused by primary users, and the existence of a communication link between two secondary users depends on the transmitting and receiving activities of nearby primary users. Using theories and techniques from continuum percolation and ergodicity, we analytically characterize the connectivity of the secondary network defined in terms of the almost sure finiteness of the multihop delay, and show the occurrence of a phase transition phenomenon while studying the impact of the temporal dynamics of the primary traffic on the connectivity of the secondary network. Specifically, as long as the primary traffic has some temporal dynamics caused by either mobility and/or changes in traffic load and pattern, the connectivity of the secondary network depends solely on its own density and is independent of the primary traffic; otherwise, the connectivity of the secondary network requires putting a density-dependent cap on the primary traffic load. We show that the scaling behavior of the multihop delay depends critically on whether or not the secondary network is instantaneously connected. In particular, we establish the scaling law of the minimum multihop delay with respect to the source-destination distance when the propagation delay is negligible.

Backup paths are widely used in IP networks to protect IP links from failures. However, existing solutions such as the commonly used independent model and Shared Risk Link Group (SRLG) model do not accurately reflect the correlation between IP link failures, and thus may not choose reliable backup paths. We propose a cross-layer approach for minimizing routing disruption caused by IP link failures. We develop a probabilistically correlated failure (PCF) model to quantify the impact of IP link failure on the reliability of backup paths. With the PCF model, we propose an algorithm to choose multiple reliable backup paths to protect each IP link. When an IP link fails, its traffic is split onto multiple backup paths to ensure that the rerouted traffic load on each IP link does not exceed the usable bandwidth. We evaluate our approach using real ISP networks with both optical and IP layer topologies. Experimental results show that two backup paths are adequate for protecting a logical link. Compared with existing works, the backup paths selected by our approach are at least 18 percent more reliable and the routing disruption is reduced by at least 22 percent. Unlike prior works, the proposed approach prevents the rerouted traffic from interfering with normal traffic.

Team science is a collaborative approach to research, typically with researchers drawn from different disciplines. Team science networks have certain unique characteristics in their conception and intent that set them apart from other commonly studied social and collaboration networks. We study the structural properties, and present metrics for collaborative performance assessment in two real-world team science networks initiated by the Army Research Lab. We model a team using a higher-order generalization of an edge called a simplex. A simplex captures group relationships distinct from the union of pairwise relationships. Our evaluation using a rigorous methodology reveals that the distributions of vertex and facet degrees (the number of maximal groups that a vertex belongs to) follow a power law, but with exponential cut-off at the tail in most cases. We propose metrics for quantitatively assessing the extent of intra-team and extra-team collaborations, and compare their effectiveness vis-a-vis our intuitive notions. Our work can be used as the basis for generative models, and for evaluating the collaborative performance of team science networks.

We investigate the problem of identifying individual link performance metrics in a communication network by measuring end-to-end metrics of selected paths between monitors, under the assumption that link metrics are additive and constant during the measurement, and measurement paths cannot contain cycles. In a previous work, we developed an algorithm that places the minimum number of monitors to identify all link metrics. However, even the minimum number can be large in some practical networks (e.g., 60% of all the nodes), suggesting high monitor deployment cost. In this paper, we study the dual problem where given a fixed number of monitors, we want to place them to maximize the number of identifiable link metrics, with concrete results for the case of two monitors. The significance of the two-monitor case is that all the tomographic computation can be performed at the destination monitor without shipping measurements to a central node, thus enabling endhost-based network monitoring. We develop an efficient algorithm to determine all identifiable links in an arbitrary network with a given placement of two monitors, based on which we propose an optimal two-monitor placement algorithm to maximize the number of identifiable links. Our evaluation on real ISP topologies shows that although a large number of monitors is needed to identify all link metrics, we can usually identify a substantial portion (up to 97%) of the links using a single pair of optimally placed monitors.

There has recently been increased interest in applications of topology to areas ranging from control and sensing, to social network analysis, to high-dimensional point cloud data analysis. Here we use simplicial complexes to represent the group relationship structure in a network. We detail a novel algorithm for simplifying homology and “hole location” computations on a complex by reducing it to its core using a strong collapse. We show that the homology and hole locations are preserved and provide motivation for interest in this reduction technique with applications in sensor and social networks. Since the complexity of finding “holes” is quintic in the number of simplices, the proposed reduction leads to significant savings in complexity.

We consider a large-scale cyber network with N components. Each component is either in a healthy state or an abnormal state. To model scenarios where attacks to the network may not follow a stochastic process and the attackers may adapt to the actions of the intrusion detection system (IDS) in an arbitrary and unknown way, we adopt a non-stochastic model in which the attack process at each component can be any unknown deterministic sequence. Due to resource constraints, the IDS can only choose K (K <; N) components to probe at each time. An abnormal component incurs a cost per unit time (depending on the criticality of the component) until it is probed and fixed. The objective is a dynamic probing strategy under the performance measure of regret, defined as the performance loss compared to that of a genie who knows the entire attack processes a priori and probes optimally (under certain constraints) based on this knowledge. We propose a policy that achieves sublinear regret order, thus offers the same time averaged performance as that of the omniscient genie.

We investigate the problem of identifying individual link metrics in a communication network from accumulated end-to-end metrics over selected measurement paths, under the assumption that link metrics are additive and constant during the measurement, and measurement paths cannot contain cycles. We know from linear algebra that all link metrics can be uniquely identified when the number of linearly independent measurement paths equals u, the number of links. It is, however, inefficient to collect measurements from all possible paths, whose number can grow exponentially in u, as the number of useful measurements (from linearly independent paths) is at most u. The aim of this paper is to develop efficient algorithms for constructing linearly independent measurement paths and calculating link metrics. We show that whenever there exists a set of u linearly independent measurement paths, there must exist a set of three pairwise independent spanning trees. We exploit this property to develop an algorithm that can construct u linearly independent, cycle-free paths between monitors without examining all candidate paths, whose complexity is quadratic in u. A further benefit of the proposed algorithm is that the generated paths satisfy a nested structure that allows linear-time computation of link metrics without explicitly inverting the measurement matrix. Our evaluations on both synthetic and real network topologies verify the superior efficiency of the proposed algorithms, which are orders of magnitude faster than benchmark solutions for large networks.

We investigate the problem of identifying individual link metrics in a communication network from end-to-end path measurements, under the assumption that link metrics are additive and constant. To uniquely identify the link metrics, the number of linearly independent measurement paths must equal the number of links. Our contribution is to characterize this condition in terms of the network topology and the number/placement of monitors, under the constraint that measurement paths must be cycle-free. Our main results are: (i) it is generally impossible to identify all the link metrics by using two monitors; (ii) nevertheless, metrics of all the interior links not incident to any monitor are identifiable by two monitors if the topology satisfies a set of necessary and sufficient connectivity conditions; (iii) these conditions naturally extend to a necessary and sufficient condition for identifying all the link metrics using three or more monitors. We show that these conditions not only allow efficient identifiability tests, but also enable an efficient algorithm to place the minimum number of monitors in order to identify all link metrics. Our evaluations on both random and real topologies show that the proposed algorithm achieves identifiability using a much smaller number of monitors than a baseline solution.

A recent topic of research in the network science community is combined or composite networks - these are two or more interacting networks that must be characterized jointly rather than individually. For example, a social network and a communication network sharing some nodes (corresponding to users) may be modeled together as a composite network. This may be useful since the aggregate performance of a composite network may often depend on how the individual networks influence each other. Information may travel faster or slower through composite networks depending on how they are coupled. The above vision was captured in the Call for Papers for this special issue in the IEEE Journal On Selected Areas In Communications, and it was published in June 2012. As a result of this solicitation, we received 62 submissions by the deadline of August 15, 2012. Papers were selected after two rigorous rounds of review. The first round of notifications were sent out on December 17, 2012 to the authors whose papers passed the first round of review. Revised versions of the papers were submitted on January 31, 2013. Finally, after a second round of review, the Guest Editorial board decided on March 12, 2013 to accept 16 high quality papers for publication in this competitive special issue. Papers appearing in this special issue belong to five broad themes, which are not necessarily mutually exclusive: (1) fundamental principles in network science, (2) information propagation models in networks, (3) bringing insights from other genres of networks, (4) economic and game theoretic models, and (5) application of network science principles to communications networking problems.

We consider a variation of the Deffuant-Weisbuch model introduced by Deffuant et al. in 2000, to provide new analytical insights on the opinion dynamics in a social group. We model the trust that may exist between like-minded agents through a trust function, which is a discontinuous (hard-interaction) non-increasing function of the opinion distance. In this model, agents exchange their opinions with their neighbors and move their opinions closer to each other if they are like-minded (that is, the distance between opinions is smaller than a threshold). We first study the dynamics of opinion formation under random interactions with a fixed rate of communication between pairs of agents. Our goal is to analyze the convergence properties of the opinion dynamics and explore the underlying characteristics that mark the phase transition from opinion polarization to consensus. Furthermore, we extend the hard-interaction model to a strategic interaction model by considering a time-varying rate of interaction. In this model, social agents themselves decide the time and energy that should be expended on interacting each of their neighbors, based on their utility functions. The aim is to understand how and under what conditions clustering patterns emerge in opinion space. Extensive simulations are provided to validate the analytical results of both the hard-interaction model and the strategic interaction model. We also offer evidence that suggests the validity of the proposed model, using the location and monthly survey data collected in the Social Evolution experiment over a period of nine months.

In this article, we quantify the achievable spatial throughput of a multi-antenna Poisson cognitive radio network (CRN) collocated with a Poisson multi-antenna primary network. CR users employ Slotted-ALOHA medium access control. The success probability (SP) of a primary link is quantified in the presence of the secondary and primary interferers. It is demonstrated that two fold gains are experienced by employing multiple antennas at primary, i.e., (i) the fixed high desired SP threshold is met; (ii) CRs can also be accommodated without QoS deterioration. Further in this paper, the maximum permissible medium access probability (MAP) for CRN is derived from the link SP and primary users QoS constraint. The impact of the number of antennas and modulation employed at the primary on the permissible MAP of the CRN is also explored. Assuming that CR users employ multi-hop communication, QoS aware relaying with a radian sector forwarding area is studied. The average forward progress (AFP) and isolation probability for a CR user with QoS based connectivity is characterized under the permissible MAP. The spatial throughput for the CRN is quantified by the analysis of the AFP and the permissible MAP. It is shown that there exists an optimal MAP which maximizes the spatial throughput of the CRN. This optimal MAP is coupled with the permissible MAP, density of users, number of antennas and modulation schemes employed in both primary and secondary networks. Lastly, a few important design questions are investigated for multi-hop MIMO underlay CRNs.

We address physical layer security in multiple- input-multiple-output (MISO) communications in the presence of an unknown passive eavesdropper. Beamforming and artificial noise broadcasting are chosen to increase communications security. We first study the effect of a close eavesdropper on security and then we define a “Protected Zone” in the transmitter's vicinity. We present an optimisation strategy that intelligently sets the transmission power and the size of the protected zone to probabilistically achieve secrecy at a specified target secrecy rate. The results show that this strategy can achieve a high probability of secrecy by efficiently prioritising the use of the available resources.

In this paper, we propose an algorithm to efficiently diagnose large-scale clustered failures. The algorithm, Cluster-MAX-COVERAGE (CMC), is based on greedy approach. We address the challenge of determining faults with incomplete symptoms. CMC makes novel use of both positive and negative symptoms to output a hypothesis list with a low number of false negatives and false positives quickly. CMC requires reports from about half as many nodes as other existing algorithms to determine failures with 100% accuracy. Moreover, CMC accomplishes this gain significantly faster (sometimes by two orders of magnitude) than an algorithm that matches its accuracy. Furthermore, we propose an adaptive algorithm called Adaptive-MAX-COVERAGE (AMC) that performs efficiently during both kinds of failures, i.e., independent and clustered. During a series of failues that include both independent and clustered, AMC results in a reduced number of false negatives and false positives.

Gossiping models have been increasingly applied to study social network phenomena, in particular, to model the dynamics of social behavior or belief through local interactions. In this context, this paper investigates how the opinions of social agents diffuse in a network under a so-called hard-interaction model, in which the agents interact more strongly with neighbors that share their beliefs and have no influence on the neighbors whose opinions differ by more than a threshold. We analyze the convergence properties of the opinion dynamics and provide analytical insights to characterize the phase transition from a society of radicalized opinions to one of convergent behavior.

Quickly recovering IP networks from failures is critical to enhancing Internet robustness and availability. Due to their serious impact on network routing, large-scale failures have received increasing attention in recent years. We propose an approach called Reactive Two-phase Rerouting (RTR) for intra-domain routing to quickly recover from large-scale failures with the shortest recovery paths. To recover a failed routing path, RTR first forwards packets around the failure area to collect information on failures. Then, in the second phase, RTR calculates a new shortest path and forwards packets along it through source routing. RTR can deal with large-scale failures associated with areas of any shape and location, and is free of permanent loops. For any failure area, the recovery paths provided by RTR are guaranteed to be the shortest. Extensive simulations based on ISP topologies show that RTR can find the shortest recovery paths for more than 98.6% of failed routing paths with reachable destinations. Compared with prior works, RTR achieves better performance for recoverable failed routing paths and uses much less network resources for irrecoverable failed routing paths.

Nodes that are part of a multihop wireless network, typically deployed in mission critical settings, are expected to perform specific functions. Establishing a notion of reliability of the nodes with respect to each function (referred to as functional reliability or FR) is essential for efficient operations and management of the network. This is typically assessed based on evidence collected by nodes with regards to other nodes in the network. However, such evidence is often affected by factors such as channel induced effects and interference. In multihop contexts, unreliable intermediary relays may also influence evidence. We design a framework for collaborative assessment of the FR of nodes, with respect to different types of functions; our framework accounts for the above factors that influence evidence collection. Each node (say Chloe) in the network derives the FR of other nodes (say Jack) based on two types of evidence: (i) direct evidence, based on her direct transactions with each such node and (ii) indirect evidence, based on feedback received regarding Jack from others. Our framework is generic and is applicable in a variety of contexts. We also design a module that drastically reduces the overhead incurred in the propagation of indirect evidence at the expense of slightly increased uncertainty in the assessed FR values. We implement our framework on an indoor/outdoor wireless testbed. We show that with our framework, each node is able to determine the FR for every other node in the network with high accuracy. Our indirect evidence propagation module decreases the overhead by 37% compared to a simple flooding based evidence propagation, while the accuracy of the FR computations is decreased only by 8%. Finally, we examine the effect of different routing protocols on the accuracy of the assessed values.

In this paper, we solve a fundamental problem: how to use distributed random access to achieve the performance of centralized schedulers. We consider wireless networks with arbitrary topologies and spatial traffic distributions, where users can receive traffic from or send traffic to different users and different communication links may interfere with each other. The channels are assumed heterogeneous, and the random channel gains of different links may have different distributions. To resolve the network contention in a distributed way, each frame is divided into contention and transmission periods. The contention period is used to resolve conflicts, while the transmission period is used to send payload in collision-free scenarios. We design a multistage channel-aware Aloha scheme for the contention period to enable users with relatively better channel states to have higher probabilities of contention success while assuring fairness among all users. We show analytically that the proposed scheme completely resolves network contention and achieves throughput close to that of centralized schedulers. Furthermore, the proposed scheme is robust to any uncertainty in channel estimation. Simulation results demonstrate that it significantly improves network performance while maintaining fairness among different users. The proposed random access approach can be applied to different wireless networks, such as cellular, sensor, and mobile ad hoc networks, to improve quality of service.

We present a probabilistic framework for physical layer secrecy when the locations and channels of the eavesdroppers are unknown. The locations are modeled by a Poisson point process. The channels include path loss and Rayleigh fading. Beamforming and frequency-selectivity of the fading channels are shown to greatly increase the probability of secure communications.

We consider the broadcasting problem in multi-radio multi-channel ad hoc networks. The objective is to minimize the total broadcast cost, where the cost can be of any form that is summable over all the transmissions (e.g., the transmission and reception energy, the price for accessing a specific channel). Our technical approach is based on a simplicial complex model that allows us to capture the broadcast nature of the wireless medium and the heterogeneity across radios and channels. Specifically, we show that broadcasting in multi-radio multi-channel ad hoc networks can be formulated as a minimum spanning problem in simplicial complexes. We establish the NP-completeness of the minimum spanning problem and propose two approximation algorithms with order-optimal performance guarantee. These two algorithms offer tradeoffs between performance and time complexity. In a broader context, this work appears to be the first that studies the minimum spanning problem in simplicial complexes and weighted minimum connected set cover problem.

We consider the problem of disseminating data from a base station to a sparse, partitioned mobile network by controllable data ferries with limited ferry-node and ferry-ferry communication ranges. Existing solutions to data ferry control mostly assume the nodes to be stationary, which reduces the problem to designing fixed ferry routes. In the more challenging scenario of mobile networks, existing solutions have focused on single-ferry control and left out an important issue of ferry cooperation in the presence of multiple ferries. In this paper, we jointly address the issues of ferry navigation and cooperation using the approach of stochastic control. Under the assumption that ferries can communicate within each partition, we propose a hierarchical control system called Dispatch-and-Search (DAS), consisting of a global controller that dispatches ferries to individual partitions and local controllers that coordinate the search for nodes within each partition. Formulating the global and the local control as Partially Observable Markov Decision Processes (POMDPs), we develop efficient control policies to optimize the (discounted) total throughput, which significantly improve the performance of their predetermined counterparts in cases of limited prior knowledge.

In this paper we present a framework and a set of algorithms for determining faults in networks when large scale outages occur. The design principles of our algorithm, netCSI, are motivated by the fact that failures are geographically clustered in such cases. We address the challenge of determining faults with incomplete symptom information due to a limited number of reporting nodes in the network. netCSI consists of two parts: hypotheses generation algorithm, and ranking algorithm. When constructing the hypotheses list of potential causes, we make novel use of the positive and negative symptoms to improve the precision of the results. The ranking algorithm is based on conditional failure probability models that account for the geographic correlation of the network objects in clustered failures. We evaluate the performance of netCSI for networks with both random and realistic topologies. We compare the performance of netCSI with an existing fault diagnosis algorithm, MAX-COVERAGE, and achieve an average gain of 128\% in accuracy for realistic topologies.

The problem of distributed learning and channel access is considered in a cognitive network with multiple secondary users. The availability statistics of the channels are initially unknown to the secondary users and are estimated using sensing decisions. There is no explicit information exchange or prior agreement among the secondary users and sensing and access decisions are undertaken by them in a completely distributed manner. We propose policies for distributed learning and access which achieve order-optimal cognitive system throughput (number of successful secondary transmissions) under self play, i.e., when implemented at all the secondary users. Equivalently, our policies minimize the sum regret in distributed learning and access, which is the loss in secondary throughput due to learning and distributed access. For the scenario when the number of secondary users is known to the policy, we prove that the total regret is logarithmic in the number of transmission slots. This policy achieves order-optimal regret based on a logarithmic lower bound for regret under any uniformly-good learning and access policy. We then consider the case when the number of secondary users is fixed but unknown, and is estimated at each user through feedback. We propose a policy whose sum regret grows only slightly faster than logarithmic in the number of transmission slots.

We analyze the multihop delay of ad hoc cognitive radio networks, where the transmission delay of each hop consists of the propagation delay and the waiting time for the availability of the communication channel (i.e. the occurrence of a spectrum opportunity at this hop). Using theories and techniques from continuum percolation and ergodicity, we establish the scaling law of the minimum multihop delay with respect to the source-destination distance in cognitive radio networks. When the propagation delay is negligible, we show the starkly different scaling behavior of the minimum multihop delay in instantaneously connected networks as compared to networks that are only intermittently connected due to scarcity of spectrum opportunities. Specifically, if the network is instantaneously connected, the minimum multihop delay is asymptotically independent of the distance; if the network is only intermittently connected, the minimum multihop delay scales linearly with the distance. When the propagation delay is nonnegligible but small, we show that although the scaling order is always linear, the scaling rate for an instantaneously connected network can be orders of magnitude smaller than the one for an intermittently connected network.

We address the percolation-based connectivity of large-scale ad hoc heterogeneous wireless networks, where secondary users exploit channels temporarily unused by primary users and the existence of a communication link between two secondary users depends on not only the distance between them but also the transmitting and receiving activities of nearby primary users. We introduce the concept of connectivity region defined as the set of density pairs-the density of secondary users and the density of primary transmitters - under which the secondary network is connected. Using theories and techniques from continuum percolation, we analytically characterize the connectivity region of the secondary network and reveal the tradeoff between proximity (the number of neighbors) and the occurrence of spectrum opportunities. Specifically, we establish three basic properties of the connectivity region-contiguity, monotonicity of the boundary and uniqueness of the infinite connected component, where the uniqueness implies the occurrence of a phase transition phenomenon in terms of the almost sure existence of either zero or one infinite connected component; we identify and analyze two critical densities which jointly specify the profile as well as an outer bound on the connectivity region; we study the impacts of secondary users' transmission power on the connectivity region and the conditional average degree of a secondary user and demonstrate that matching the interference ranges of the primary and the secondary networks maximizes the tolerance of the secondary network to the primary traffic load. Furthermore, we establish a necessary condition and a sufficient condition for connectivity, which lead to an outer bound and an inner bound on the connectivity region.

Power control is important in interference-limited cellular, ad-hoc, and cognitive underlay networks, when the objective is to ensure a certain quality of service to each connection. Power control has been extensively studied in this context, including distributed algorithms that are particularly appealing in ad-hoc and cognitive settings. A long-standing issue is that the power control problem may be infeasible, thus requiring appropriate admission control. The power and admission control parts of the problem are tightly coupled, but the joint optimization problem is NP-hard. We begin with a convenient reformulation which enables a disciplined convex approximation approach. This leads to a centralized approximate solution that is numerically shown to outperform the prior art, and even yield close to optimal results in certain cases - at affordable complexity. The issue of imperfect channel state information is also considered. A distributed implementation is then developed, which alternates between distributed approximation and distributed deflation - reaching consensus on a user to drop, when needed. Both phases require only local communication and computation, yielding a relatively lightweight distributed algorithm with the same performance as its centralized counterpart.

Spectrum sensing in cognitive radio becomes a challenging task when the signals received at the secondary users' transmitters exhibit low power. Locally optimum detectors (LOD) are therefore desirable thanks to their optimality in the low SNR regime. Here, we assume that the primary user transmits a training sequence, and propose a semi-blind LOD (SBLOD). In the case of BPSK signals, the test statistic of the proposed SBLOD is shown to be a weighted sum of the matched filter output, the energy and pseudo-energy. For higher size constellations, the SBLOD reduces to a linear combination of the matched filter and the energy detector. Although combining the matched filter and energy detector is a classical approach, our study provides a systematic and (locally) optimal way of combining these detectors. Simulations results show the merits of the proposed detector.

Power control is important in interference-limited cellular, ad-hoc, and cognitive wireless networks, when the objective is to ensure a certain quality of service to each connection. Power control has been extensively studied in this context, including distributed algorithms that are particularly appealing in ad-hoc and cognitive settings. A long-standing issue is that the power control problem may be infeasible, thus requiring appropriate admission control. The power and admission control parts of the problem are tightly coupled, but the joint problem is NP-hard. In recent work, we developed a convex relaxation-based deflation approach to the joint problem, which was shown to outperform the prior art, and yield close to optimal solutions at moderate computational cost. In this paper, we derive a distributed version of our joint power and admission control algorithm. The algorithm alternates between distributed approximation and distributed deflation - reaching consensus on a user to drop, when needed. Both phases require only local communication and computation, yielding a relatively lightweight distributed algorithm which also attains close to optimal performance.

We analyze the multihop delay of ad hoc cognitive radio networks, where the transmission delay of each hop consists of the propagation delay and the waiting time for the availability of the communication channel (i.e., the occurrence of a spectrum opportunity at that hop). Using theories and techniques from continuum percolation and ergodicity, we establish the scaling law of the minimum multihop delay with respect to the source-destination distance. We show the starkly different scaling behavior of the multihop delay in instantaneously connected networks as compared to networks that are only intermittently connected due to the scarcity of spectrum opportunities.

Neighbor discovery is essential for the process of self-organization of a wireless network, where almost all routing and medium access protocols need knowledge of one-hop neighbors. In this paper we study the problem of neighbor discovery in a static and synchronous network, where time is divided into slots, each of duration equal to the time required to transmit a hello message, and potentially, some sort of feedback message. Our main contributions lie in detailing the physical layer mechanism for how nodes in receive mode detect the channel status, describing algorithms at higher layers that exploit such a knowledge, and characterizing the significant gain obtained. In particular, we describe one possible physical layer architecture that allows receivers to detect collisions, and then introduce a feedback mechanism that makes the collision information available to the transmitters. This allows nodes to stop transmitting packets as soon as they learn about the successful reception of their discovery messages by the other nodes in the network. Hence, the number of nodes that need to transmit packets decreases over time. These nodes transmit with a probability that is inversely proportional to the number of active nodes in their neighborhood, which is estimated using the collision information available at the nodes. We show through analysis and simulations that our algorithm allows nodes to discover their neighbors in a significantly smaller amount of time compared to the case where reception status feedback is not available to the transmitters.

We seek to support communications in highly-partitioned mobile wireless networks via controllable data ferries. While existing ferry control techniques assume either stationary nodes or complete ferry observation of node locations, we address the more challenging scenario of highly mobile nodes and partial ferry observations. Using the tool of Partially Observable Markov Decision Processes (POMDP), we develop a comprehensive framework where we expand the solution space from predetermined trajectories to policies that can map ferry observations to navigation actions dynamically. Under this framework, we present an optimal and several efficient heuristic policies. We compare the proposed policies with predetermined control through analysis and simulations with respect to multiple node mobility parameters including speed, locality, activeness, and range of movement. The comparisons show a significant performance gain of up to twice the contact rate in cases of high uncertainty. In cases of low uncertainty, we give a sufficient condition under which predetermined control is optimal.

Controlled mobile helper nodes called data ferries have recently been proposed to bridge communications between disconnected nodes in a delay-tolerant manner. While existing work has explored various trajectory designs for the data ferry by assuming either static nodes or full observations at the data ferry, the problem remains open when the nodes are mobile and the ferry only has partial observations. In this paper, we investigate the problem of dynamic ferry mobility control under limited-range sensing. Assuming the data ferries are capable of sensing node presence within certain range and adjust their movements dynamically, we aim to design control policies that maximize the number of effective contacts. We provide a comprehensive model of the control framework using Partially Observable Markov Decision Process (POMDP), based on which we study the structure of the optimal policy and propose an efficient heuristic policy which shows significant improvement over the predetermined benchmark. To the best of our knowledge, this is the first data ferry control mechanism that can handle both stochastic node mobility and incomplete ferry observations.

The vitality and utility of a network are affected significantly by the network management system (NMS) that is used to administer and monitor the network. However, models that can characterize the quality of a NMS are generally missing in the literature. In this paper, we introduce the concept of quality of monitoring (QoM), provide a mathematical formulation based on stochastic processes that can be used to model a network monitoring system and define QoM metrics based on this formulation. A formal analysis of the proposed framework along various metrics is also provided, along with a case study of its application to network monitoring in a mobile ad hoc network.

In this paper, we compare the battery power efficiencies of various pulse-based modulations widely adopted for their low complexity. Taking into account circuit modules and battery imperfectness, we establish simple closed-form analytical formulas which can be used to conveniently determine the relative preference between arbitrary pulse-based modulation pairs in terms of their actual average battery energy consumption.

Lattice reduction (LR) has been applied to linear equalizers and decision feedback equalizers to improve their performance. Recently, Seysen's algorithm (SA) has been proposed as an alternative LR method to the well-documented LLL algorithm. In this paper, we first provide a tree-search implementation method of SA which enables flexible performance-complexity trade-offs. Based on this tree structure, SA-aided hard-output and soft-output detectors are proposed to enhance performance. The diversity and complexity of the proposed methods are also studied. Thorough comparisons of SA and other LR algorithms are provided. Our analysis of complexity and numerical simulations provide insights that are useful to system designers.

We investigate distributed channel-aware random access for networks with arbitrary topologies and traffic distributions, where users can receive traffic from or send traffic to different users and different communication links may interfere with others. We consider heterogeneous channels, where the random channel gains of different links may have different distributions. To resolve the network contention in a distributed way, each frame is divided into contention and transmission periods. The contention period is used to resolve conflicts near optimally and to schedule users with better channel states with higher probabilities while assuring fairness among all users. The proposed scheme completely resolves contention of networks with arbitrary topologies and is robust to any channel uncertainty. Besides, it performs close to central schedulers.

The multipath diversity and coding gain metrics for cyclic-prefixed single-carrier (SC-CP) systems, which characterize the bit error rate (BER) at high SNR, have not been carefully studied in the literature. We first show that, unlike OFDM, the diversity and coding gains for SC-CP are data-realization-dependent. Then, we show that there is a signal-to-noise ratio (SNR) threshold beyond which the dominant diversity order starts deviating from the maximum diversity order to eventually reduce to one at higher SNRs. Using the averaged pairwise probability, we derive an analytical expression for this SNR threshold. The latter is shown to increase with the block length and to be unrealistically high for moderate/high block lengths. Comparisons of SC-CP with rotated constellations and zero-padded SC systems are also provided.

A novel formulation for optimal sensor selection and in-network fusion for distributed inference known as the prize- collecting data fusion (PCDF) is proposed in terms of optimal tradeoff between the costs of aggregating the selected set of sensor measurements and the resulting inference performance at the fusion center. For i.i.d. measurements, PCDF reduces to the prize-collecting Steiner tree (PCST) with the single-letter Kullback-Leibler divergence as the penalty at each node, as the number of nodes goes to infinity. PCDF is then analyzed under a correlation model specified by a Markov random field (MRF) with a given dependency graph. For a special class of dependency graphs, a constrained version of the PCDF reduces to the PCST on an augmented graph. In this case, an approximation algorithm is given with the approximation ratio depending only on the number of profitable cliques in the dependency graph. Based on these results, two heuristics are proposed for node selection under general correlation structure, and their performance is studied via simulations.

Sensor nodes in wireless sensor networks (WSNs) are often expected to operate on batteries for a long period of time. Battery power efficiency (BPE) is therefore a critical factor dictating the lifetime of WSNs. In this paper, we aim to select the appropriate modulation scheme from a battery power efficiency perspective. Pulse position modulation (PPM) and on-off keying (OOK), as low-complexity pulse-based modulation schemes, are used for a case study of our methodology. The analysis is based on a general model that integrates typical WSN transmission and reception modules with a realistic nonlinear battery model. We first present the quantitative comparison results under general system design criteria. Then, we illustrate the comparisons with theoretical and numerical results under the bit error rate (BER) system design criterion.

The energy scaling laws of multihop data fusion networks for distributed inference are considered. The fusion network consists of randomly located sensors distributed i.i.d. according to a general spatial distribution in an expanding region. Under Markov random field (MRF) hypotheses, among the class of data-fusion policies which enable optimal statistical inference at the fusion center using all the sensor measurements, the policy with the minimum average energy consumption is bounded below by the average energy of fusion along the minimum spanning tree, and above by a suboptimal policy, referred to as Data Fusion for Markov Random Fields (DFMRF). Scaling laws are derived for the energy consumption of the optimal and suboptimal fusion policies. It is shown that the average asymptotic energy of the DFMRF scheme is strictly finite for a class of MRF models with Euclidean stabilizing dependency graphs.

We consider power control in cognitive radio networks where secondary users identify and exploit instantaneous and local spectrum opportunities without causing unacceptable interference to primary users. We qualitatively characterize the impacts of the transmission power of secondary users on the occurrence of spectrum opportunities and the reliability of opportunity detection. Based on a Poisson model of the primary network, we quantify these impacts by showing that (i) the probability of spectrum opportunity decreases exponentially with the transmission power of secondary users, where the exponential decay constant is given by the traffic load of primary users; (ii) reliable opportunity detection is achieved in the two extreme regimes in terms of the ratio between the transmission power of secondary users and that of primary users. Such analytical characterizations allow us to study power control for optimal transport throughput under constraints on the interference to primary users. Furthermore, we reveal the difference between detecting primary signals and detecting spectrum opportunities, and demonstrate the complex relationship between physical layer spectrum sensing and MAC layer throughput. The dependency of this PHY-MAC interaction on the application type and the use of handshake signaling such as RTS/CTS is also illustrated.

Co-channel interference (CCI) has become an important problem with the increasing deployment of wireless networks in the unlicensed frequency band. The existing Bluetooth scheme avoids collisions by modifying its hop sequences in the presence of WLAN. We propose a frequency diversity technique, namely dual channel transmission (DCT), which reduces packet error rate (PER) due to CCI when multiple Bluetooth piconets coexist with or without WLAN interference. The idea of DCT is to transmit the same packet on two distinct frequency hopped channels simultaneously and the power used in each channel is half of what would be used in single channel transmission (SCT). Since a packet is successfully received if at least one channel survives, the PER is reduced even when multiple piconets coexist. Further, the two channels of DCT are separated by at least 22 MHz to ensure robustness to WLAN interference. Theoretic analysis and numerical simulations on key metrics - PER, throughput, and transmission time are presented to validate the proposed approach and quantify its advantages. Comparisons to other coexistence mechanisms also demonstrate the effectiveness of DCT.

We consider schemes for decentralized cross-layer optimization of multichannel random access by exploiting local channel state and traffic information. In the network we are considering, users are not necessarily within the transmission ranges of all others; therefore, when a user is transmitting, it may only interfere with some users, which is different from most existing channel aware Aloha schemes. Besides, we also consider complicated traffic distribution, e.g. each user may choose to send packets to or receive packets from different users simultaneously. We develop decentralized optimization for multichannel random access (DOMRA). DOMRA consists of three steps: neighborhood information collection, transmission control of the MAC layer based on the instantaneous channel state information, and power allocation for each traffic flow on each subchannel. Simulation results demonstrated that DOMRA significantly outperforms existing channel aware Aloha schemes due to its exploitation of both multiuser diversity through cross-layer design and the inhomogeneous characteristics of traffic spatial distribution in the network. Besides, DOMRA performs closely to the globally optimum solution, which requires full network knowledge to be obtained. DOMRA can be applied to different types of wireless networks, such as wireless sensor networks and mobile ad hoc networks, to improve quality of service.

The problem of hypothesis testing against independence for a Gauss–Markov random field (GMRF) is analyzed. Assuming an acyclic dependency graph, an expression for the log-likelihood ratio of detection is derived. Assuming random placement of nodes over a large region according to the Poisson or uniform distribution and nearest-neighbor dependency graph, the error exponent of the Neyman–Pearson detector is derived using large-deviations theory. The error exponent is expressed as a dependency-graph functional and the limit is evaluated through a special law of large numbers forstabilizinggraph functionals. The exponent is analyzed for different values of the variance ratio and correlation. It is found that a more correlated GMRF has a higher exponent at low values of the variance ratio whereas the situation is reversed at high values of the variance ratio.

Orthogonal frequency division multiplexing (OFDM) is an effective technique to deal with frequency-selective channels since it facilitates low complexity equalization and decoding. Many existing OFDM designs successfully exploit the multipath diversity offered by frequency-selective channels. However, most of them require maximum likelihood (ML) or near-ML detection at the receiver, which is of high complexity. On the other hand, empirical results have shown that linear detectors have low complexity but offer inferior performance. In this paper, we analytically quantify the diversity orders of linear equalizers for linear precoded OFDM systems, and prove that they are unable to collect full diversity. To improve the performance of linear equalizers, we further propose to use a lattice reduction (LR) technique to help collect diversity. The LR-aided linear equalizers are shown to achieve maximum diversity order (i.e., the one collected by the ML detector), but with low complexity that is comparable to that of conventional linear equalizers. The theoretical findings are corroborated by simulation results.

Abstract Since battery technology has not progressed as rapidly as semiconductor technology, power efficiency has become increasingly important in wireless networking, in addition to the traditional quality and performance measures, such as bandwidth, throughput, and fairness. Energy‐efficient design requires a cross layer approach as power consumption is affected by all aspects of system design, ranging from silicon to applications. This article presents a comprehensive overview of recent advances in cross‐layer design for energy‐efficient wireless communications. We particularly focus on a system‐based approaches toward energy optimal transmission and resource management across time, frequency, and spatial domains. Details related to energy‐efficient hardware implementations are also covered. Copyright © 2008 John Wiley & Sons, Ltd.

In most sensor network applications, the vector containing the observations gathered by the sensors lies in a space of dimension equal to the number of nodes, typically because of observation noise, even though the useful signal belongs to a subspace of much smaller dimension. This motivates smoothing or rank reduction. We formulate a convex optimization problem, where we incorporate a fidelity constraint that prevents the final smoothed estimate from diverging too far from the observations. This leads to a distributed algorithm in which nodes exchange updates only with neighboring nodes. We show that the widely studied consensus algorithm is indeed only a very specific case of our more general formulation. Finally, we study the convergence rate and propose some approaches to maximize it.

The problem of minimum cost in-network fusion of measurements, collected from distributed sensors via multihop routing is considered. A designated fusion center performs an optimal statistical-inference test on the correlated measurements, drawn from a Markov random field. Conditioned on the delivery of a sufficient statistic for inference to the fusion center, the structure of optimal routing and fusion is shown to be a Steiner tree on a transformed graph. This Steiner-tree reduction preserves the approximation ratio, which implies that any Sterner- tree approximation can be employed for minimum cost fusion with the same approximation ratio. The proposed fusion scheme involves routing packets of two types viz., raw measurements sent for local processing, and aggregates obtained on combining these processed values. The performance of heuristics for minimum cost fusion are evaluated through theory and simulations, showing a significant saving in routing costs, when compared to routing all the raw measurements to the fusion center.

The problem of distributed fusion for binary hypothesis testing in a multihop network is considered. The sensor measurements are spatially correlated according to a Markov random field (MRF) under both the hypotheses. A fusion scheme for detection involves selection and localized processing of a subset of sensor measurements, fusion of these processed values to form a sufficient statistic, and its delivery to the fusion center. The goal is to find a fusion scheme that achieves optimal linear tradeoff between the total routing costs and the resulting detection error exponent at the fusion center. The Neyman-Pearson error exponent, under a fixed type-I bound, is shown to be the limit of the normalized sum of the Kullback-Leibler distances (KLD) over the maximal cliques of the MRF under some convergence conditions. It is shown that optimal fusion reduces to a prize- collecting Steiner tree (PCST) with the approximation factor preserved when the cliques of the MRF are disjoint. The PCST is found over an expanded communication graph with virtual nodes added for each non-trivial maximal clique of the MRF and their KLD assigned as the node penalty.

This paper studies the scaling laws of the data gathering capacity of large scale multihop wireless networks. Unlike the data communication paradigms studied in previous research, for example, the many-to-many, many-to-one, broadcast, and multicast paradigms, the data gathering capacity concerns the per source node throughput in a network where a subset of nodes send data to some designated destinations while other nodes serve as relays. This some-to-some communication paradigm is commonplace in many wireless networks, for example, wireless mesh networks and wireless sensor networks, and in some cases perhaps more prevalent than the other paradigms. We first derive the upper and constructive lower bounds for the data gathering capacity, and then examine their design and performance implications. Our results show that the data gathering capacity is constrained by different factors in several different scaling regimes of the number of source and destination nodes, exhibiting distinct scaling laws in those regimes. This work fills a gap in our understanding of the capacity of various communication paradigms, and can lead to better network planning and performance for data gathering wireless network applications.

Frame timing and carrier frequency offsets in orthogonal frequency division multiplexing (OFDM) may drastically degrade performance if not accurately compensated. In practice, these offsets are estimated by transmitting a training block at the beginning of each frame. By designing this training block to have a repetitive structure, various estimation methods have been proposed in the literature. These existing estimation methods rely on the repetitive structure and not on the actual training block. In other words, these methods are based on some second-order statistics of the received signal. Here, we instead use first-order statistics and two modified versions of the nonlinear least squares method. The proposed methods are shown to provide significantly more accurate frame and frequency synchronization at the expense of a slight increase in implementation complexity. As a by-product, an accurate channel estimate is obtained with the same preamble, thus reducing the resources allocated to training.

Noncoherent receivers are favored for UWB-IR systems because of their low implementation complexity compared with coherent correlation receivers. However, existing noncoherent schemes, such as transmitted reference (TR) systems and frame-level differential receivers (FDR), suffer from performance degradation and energy efficiency loss. We propose to use block-coded modulation and develop a novel energy detection-based noncoherent reception scheme for UWB-IR systems. Our scheme is capable of effective noise/interference mitigation without loss of energy efficiency and data rate. Performance evaluation shows that even in the presence of strong inter-frame interference and multiuser interference, our scheme is robust.

In this correspondence, the problem of distributed Bayesian estimation is considered in the context of a wireless sensor network. The Bayesian estimation performance is analyzed in terms of the expected Fisher information normalized by the transmission rate of the sensors. The sensors use a communication scheme known as the type-based random access (TBRA) scheme. Under a constraint on the expected transmission energy, an optimal spatio-temporal allocation scheme that maximizes the performance metric is characterized. It is shown that the performance metric is crucially dependent on the fading parameter known as the channel coherence index. For channels with low coherence indices, sensor transmissions tend to cancel each other, and there exists an optimal finite mean transmission rate that maximizes the performance metric. On the other hand, for channels with high coherence indices, there should be as many simultaneous transmissions as allowed by the network. The presence of a critical coherence index where the change from one behavior to another occurs is established.

Opportunistic spectrum access (OSA) that allows secondary users to independently search for and exploit instantaneous spectrum availability is considered. The design objective is to maximize the throughput of a secondary user while limiting the probability of colliding with primary users. Integrated in the joint design are three basic components: a spectrum sensor that identifies spectrum opportunities, a sensing strategy that determines which channels in the spectrum to sense, and an access strategy that decides whether to access based on potentially erroneous sensing outcomes. This joint design is formulated as a constrained partially observable Markov decision process (POMDP), and a separation principle is established. The separation principle reveals the optimality of myopic policies for the design of the spectrum sensor and the access strategy, leading to closed-form optimal solutions. Furthermore, it decouples the design of the sensing strategy from that of the spectrum sensor and the access strategy, and reduces the constrained POMDP to an unconstrained one. Numerical examples are provided to study the tradeoff between sensing time and transmission time, the interaction between the physical layer spectrum sensor and the MAC layer sensing and access strategies, and the robustness of the ensuing design to model mismatch.

We design opportunistic spectrum access strategies for improving spectrum efficiency. In each slot, a secondary user chooses a subset of channels to sense and decides whether to access based on the sensing outcomes. Incorporating the secondary user's residual energy and buffer state, we formulate this sequential decision-making problem as a partially observable Markov decision process (POMDP). Within the POMDP framework, we obtain stationary optimal sensing and access policies. By exploiting the rich structure of the underlying problem, we develop monotonicity results for the optimal policies, which accelerate the computations. Numerical results are provided to study the impact of the secondary user's packet arrival rate and residual energy on the optimal sensing and access decisions.

Carrier frequency offset (CFO) estimation is a key challenge in multicarrier systems such as OFDM. Often, this task is carried out using a preamble made of a number, say J, of repetitive-slots (RS). Here, we address the issue of optimal RS preamble design using the Cramer -Rao bound. We show that the optimal value of J is a trade-off between the multipath diversity gain and the number of unknowns to be estimated. In the case of correlated channel taps, we show that uniform power loading of the active subcarriers is not optimal (in contrast with the uncorrelated case) and a better power loading scheme is proposed. The theoretical results are supported by computer simulations.

While most existing channel aware Aloha schemes focus on wireless networks where each user intends to send only one traffic flow, and interferes with all the other users, some wireless networks may have more complicated traffic distribution and the transmissions of different users may interfere with different groups of users. In this paper, we consider schemes for the decentralized cross-layer optimization of multichannel random access, in which users are not necessarily within the transmission ranges of all other users, and each user may choose to send packets to or receive packets from different users simultaneously. With cross-layer design, users are configured according to local neighborhood information to adapt to inhomogeneous network characteristics. It is demonstrated by simulation that the proposed scheme significantly outperforms existing channel aware Aloha schemes due to its exploitation of both multiuser diversity and the inhomogeneous characteristics of traffic distribution in the network.

The problem of hypothesis testing against independence for a Gauss-Markov random field (GMRF) with nearest-neighbor dependency graph is analyzed. The sensors measuring samples from the signal field are placed IID according to the uniform distribution. The asymptotic performance of Neyman-Pearson detection is characterized through the large-deviation theory. An expression for the error exponent is derived using a special law of large numbers for graph functionals. The exponent is analyzed for different values of the variance ratio and correlation. It is found that a more correlated GMRF has a higher exponent (improved detection performance) at low values of the variance ratio, whereas the opposite is true at high values of the ratio.

Achieving consensus on common global parameters through totally decentralized algorithms is a topic that has attracted considerable attention in the last few years. Several algorithms have been developed, among which the most popular is the average consensus method. The main advantage of these approaches is that they do not require a fusion center. But, on the other hand, they are typically based on iterative algorithms, whose energy consumption is proportional to the time necessary to achieve consensus. This time depends on the network topology, as well as on the transmit power of each node. In this paper, we show that there exists an optimal transmit power that minimizes the overall energy consumption necessary to achieve the global estimate within a given accuracy and that this power depends on the network topology.

Sensor nodes in wireless sensor networks (WSNs) are often expected to operate on batteries for a long period of time. Battery power-efficiency is a critical factor dictating the lifetime of WSNs. In this paper, we compare two pulse-based modulations, namely pulse position modulation (PPM) and on-off keying (OOK), both of which are suitable for WSNs due to their low complexity transceivers. The comparison is based on a general model that integrates typical WSN transmission and reception modules with realistic nonlinear battery models. We analyze and compare the battery power-efficiency of PPM and OOK using coherent detection, and with bit error rate (BER) and cutoff rate criteria. Our results reveal that in sparse WSNs, PPM is more battery power-efficient. In dense WSNs, OOK outperforms PPM. In addition, the battery power-efficiency of OOK increases as the required cutoff rate decreases.

In this paper, we provide a survey of dynamic spectrum access techniques. Various approaches envisioned for dynamic spectrum access are broadly categorized under three models: dynamic exclusive use model, open sharing model, and hierarchical access model. Based on this taxonomy, we provide an overview of the technical challenges and recent advances under each model.

Timing synchronization is a preeminent challenge in ultra-wideband impulse radios (UWB-IRs). The conventional all-digital synchronization methods encounter some formidable implementation difficulties such as high rate sampling and high complexity RAKE structure. To avoid these challenges, semi-analog methods have been motivated recently. We have recently proposed a code-assisted blind synchronization (CABS) algorithm to realize timing synchronization blindly with the help of the discriminative property of both time hopping codes and well- designed polarity codes. The algorithm requires sampling at the frame rate only and bypasses channel estimation during the synchronization phase. This paper analyzes the identifiability and both the probability of acquisition and the the mean square error performance of CABS analytically. A data-aided code-assisted synchronization (CAS) algorithm is also proposed and a modified version of CABS which relies solely on the time hopping code is investigated.

We propose decentralized cognitive MAC protocols that allow secondary users to independently search for spectrum opportunities without a central coordinator or a dedicated communication channel. Recognizing hardware and energy constraints, we assume that a secondary user may not be able to perform full-spectrum sensing or may not be willing to monitor the spectrum when it has no data to transmit. We develop an analytical framework for opportunistic spectrum access based on the theory of partially observable Markov decision process (POMDP). This decision-theoretic approach integrates the design of spectrum access protocols at the MAC layer with spectrum sensing at the physical layer and traffic statistics determined by the application layer of the primary network. It also allows easy incorporation of spectrum sensing error and constraint on the probability of colliding with the primary users. Under this POMDP framework, we propose cognitive MAC protocols that optimize the performance of secondary users while limiting the interference perceived by primary users. A suboptimal strategy with reduced complexity yet comparable performance is developed. Without additional control message exchange between the secondary transmitter and receiver, the proposed decentralized protocols ensure synchronous hopping in the spectrum between the transmitter and the receiver in the presence of collisions and spectrum sensing errors

Ultra-wideband (UWB) radios have received increasing attention recently for their potential to overlay legacy systems, their low-power consumption and low-complexity implementation. Because of the pulsed or duty-cycled nature of the ultra-short transmitted waveforms, timing synchronization and channel estimation pose major, and often conflicting, challenges and requirements. In order to address (or in fact bypass) both tasks, we design and test noncoherent UWB (de)modulation schemes, which remain operational even without timing and channel information. Relying on integrate-and-dump operations of what we term "dirty templates," we first derive a maximum likelihood (ML) optimal noncoherent UWB demodulator. We further establish a conditional ML demodulator with lower complexity. Analysis and simulations show that both can also be applied after (possibly imperfect) timing acquisition. Under the assumption of perfect timing, our noncoherent UWB scheme reduces to a differential UWB system. Our approach can also be adapted to a transmitted reference (TR) UWB system. We show that the resultant robust-to-timing TR (RTTR) approach considerably improves performance of the original TR system in the presence of timing offsets or residual timing acquisition errors

We consider the effect of mobility on a wideband direct sequence spread spectrum (DSSS) communication system, and study a scale-lag Rake receiver capable of leveraging the diversity that results from mobility. A wideband signal has a large bandwidth-to-center frequency ratio, such that the typical narrowband Doppler spread assumptions do not apply to mobile channels. Instead, we assume a more general temporal scaling phenomenon, i.e., a dilation of the transmitted signal's time support. Based on a uniform ring of scatterers model, we determine that the wideband scattering function, which quantifies the average scale spreading, has a "bathtub-shaped" scale profile. We compare the performances of a scale-lag Rake and a frequency-lag Rake, each capable of leveraging the diversity that results from mobility. Such analysis applies, for example, to ultra-wideband (UWB) radio frequency channels and underwater wideband acoustic channels.

Channel aware medium access protocols perform decisions primarily based on the instantaneous channel state information (CSI) available. In practice, channel measurements and quantization introduce distortion in the available CSI at the transmitter. In this paper, we investigate the effect of imperfect CSI on the asymptotic throughput of a particularly important medium access protocol - the channel aware Aloha. We show that any degree of uncertainty in the channel estimate leads to zero throughput asymptotically in the existing single carrier Aloha scheme; however, multicarrier diversity is effective in compensating for lack of perfect CSI.

For MIMO systems operating over frequency-selective channels, we establish the Cramer-Rao bound (CRB) for the CFO and channel parameters. We derive training sequences so that the resulting CRB on the CFO is independent of the channel. We show that these designs lead to simple implementation of the maximum likelihood estimators of the CFO and channel parameters, Simulation results illustrate the performance of the proposed designs

The problem of tracking the frequency and complex amplitude of a frequency-hopped complex sinusoid is considered, using a novel stochastic state-space formulation and particle filtering tools. The problem is of considerable interest for interference mitigation in frequency-hopped wireless networks, and in military communications. The proposed particle filtering approach has a number of desirable features. It affords high-resolution estimates of carrier frequency and hop timing, manageable complexity (linear in the number of processed samples), and flexibility in tracking signals with irregular hopping patterns due to intentional timing jitter. The proposed state-space model is not only parsimonious, but fortuitous as well: it turns out that the associated optimal importance function can be computed in closed form, and thus samples from it can be drawn using rejection techniques. Both prior and optimal importance sampling versions are developed and illustrated in pertinent simulations

We consider the design of quantizers for the distributed estimation of a deterministic parameter, when the fusion center uses a Maximum-Likelihood estimator. We define a new metric of performance, which is to minimize the maximum ratio between the Fisher Information of the unquantized and quantized observations. Since the estimator is M-L, the criterion is equivalent to the minimizing the maximum asymptotic relative efficiency due to quantization. We propose an algorithm to obtain the quantizer that optimizes the metric and prove its convergence. Through simulations, we illustrate that the quantizer performance is close to the best possible Fisher Information as number of quantization bits increases. Furthermore, under certain conditions, the quantizer structure is found to belong to the class of score-function quantizers, hich maximize Fisher Information for a given value of the parameter.

Low-duty-cycle Ultra-wideband (UWB) radios have the potential to provide low-probability of detection (LPD) communications with low-power and low-complexity implementation. Pulse position modulation (PPM) is a prevalent scheme for UWB radios since it can further lower the transmitter complexity by avoiding pulse negation. However, the position shifts of impulse-like UWB waveforms, together with the severe frequency-selectivity of the propagation channels, aggravate the difficulty and complexity of timing synchronization and channel estimation. To circumvent both of these challenging tasks, we develop a differential encoder and its corresponding noncoherent demodulator for PPM-UWB signals. Relying on integrate-and-dump operations of "dirty" templates, our designs are operational when the timing offset and channel information both remain unknown.

Nonideal sampling clocks in orthogonal frequency-division multiplexing (OFDM)-based ultra-wideband (UWB) systems introduce random timing jitter, which results in interchannel interference (ICI) and degrades the system performance. In this paper, we investigate the impact of timing jitter on OFDM-based UWB systems. We first derive an exact expression for the ICI power due to timing jitter. From the exact ICI power expression, we then develop various bounds on the ICI power under different situations. When timing jitters at different samples are independent, we obtain tight upper and lower bounds. When timing jitters at different samples are dependent, the ICI powers are different at different subcarriers and a universal upper bound for the ICI power is derived in this case. Compared with the exact expression for the ICI power, the developed bounds are easy to evaluate and provide insights. Their accuracy is confirmed by numerical examples. We also discuss the potential and the limitations of using oversampling to reduce the ICI power at the end.

We use the cutoff rate to study the optimal binary input distributions for the Rayleigh flat-fading channel with imperfect receiver channel state information (CSI). First, we evaluate the cutoff rate and analyze the optimal binary input as a function of the CSI quality and receiver SNR. Next, we study the limiting distributions - BPSK and on-off keying (OOK) - and derive an analytic design rule that allows adaptive switching between these two as the receiver CSI changes. We establish the virtues of a modulation scheme that employs only these limiting distributions, rather than the full spectrum of binary inputs. Finally, we use our results to design an adaptive modulation scheme for pilot symbol assisted modulation systems. We show that switching between just BPSK and equiprobable-OOK is nearly optimal for moderate to large SNR, and that switching between BPSK and generalized-OOK is nearly optimal for all SNR

We address the problem of frequency-selective channel estimation and symbol detection using superimposed training. Both single and multiple antenna systems are studied. The superimposed training consists of the sum of a known sequence and a data-dependent sequence unknown to the receiver. The data-dependent sequence cancels the effects of the unknown data on channel estimation. The performance of the proposed approach is shown to outperform significantly existing methods based on superimposed training.

We consider the effect of mobility on a wideband direct sequence spread spectrum (DSSS) communication system, and study a scale-lag Rake receiver capable of leveraging the diversity that results from mobility. A wideband signal has a large bandwidth-to-center frequency ratio, such that the typical narrowband Doppler spread assumptions do not apply to mobile channels. Instead, we assume a more general temporal scaling phenomenon, i.e., a dilation of the transmitted signal's time support. Such analysis applies, for example, to ultra-wideband (UWB) radio frequency channels and underwater wideband acoustic channels.

Cooperative relays have recently been proposed and studied for mobile ad hoc networks. It has been shown that under perfect symbol synchronization, parallel relays with space-time modulation can yield more than 10 dB power savings over conventional serial relays in a highly mobile environment. We analyze the effect of synchronization errors on the performance of parallel relays, and also study several effective methods to reduce the negative impact of synch errors. Our study shows that when the synch errors are much smaller than a symbol interval, the performance of parallel relays deteriorates gracefully. We have also found that well designed space-time coding techniques, such as TR-STC and ST-OFDM, can be highly effective in combating large synch errors with only marginal reduction of data rate.

It is well known that on-off keying (OOK) suffers from a 3 dB SNR penalty relative to BPSK for coded transmission over a Rayleigh fading channel with perfect receiver channel state information (CSI). Previously, the cutoff rate has been used to show that this 3 dB penalty can be partially recovered if the OOK transmission probability can be varied, with full recovery in the limit of vanishing rates. We extend these results to the case of imperfect CSI. We show that the maximum penalty with partial CSI is 4 dB, and that there is a range of rates and CSI quality for which the penalty is instead a gain. By further varying the transmission probability of the '1' bit in OOK, we show that the 3 dB penalty can be recovered for small rates, but not at larger rates. Finally, we consider the energy penalty for using OOK under a peak power constraint.

We address the problem of frequency-selective channel estimation and symbol detection using superimposed training. The superimposed training consists of the sum of a known sequence and a data-dependent sequence that is unknown to the receiver. The data-dependent sequence cancels the effects of the unknown data on channel estimation. The performance of the proposed approach is shown to significantly outperform existing methods based on superimposed training (ST).

With the rapid growth of frequency-hopped (FH) wireless networks, interference due to frequency collisions has become one of the main performance-limiting challenges. This paper proposes a novel multiuser detection method for joint hop timing and frequency estimation, which is capable of unraveling and demodulating multiple FH transmissions in the presence of collisions and unknown hop patterns without retransmission. The method is based on the principle of dynamic programming (DP) coupled with two-dimensional harmonic retrieval (2-D HR) or low-rank trilinear decomposition, and it remains operational even with multiple unknown hop rates, frequency offsets, and asynchronism. The model is based on frequency-shift keying (FSK) and phase-shift keying (PSK) modulation, but the algorithms are also evaluated with Gaussian minimum-shift keying (GMSK) modulation and shown to be robust.

When the orthogonal frequency-division multiplexing (OFDM) signal is appreciably wideband, as in underwater communications, a single Doppler-shift parameter is inadequate to model the Doppler effect, and a rate parameter is required as well. Such a model also accommodates nonsynchronized sampling of the received signal. We establish conditions for the identifiability of the Doppler parameters, and show how they affect the placement of null subcarriers (NSC). We derive the maximum-likelihood (ML) estimator and the corresponding conditional Crame/spl acute/r-Rao lower bound. We show that the vector formulation is amenable to estimation of signal parameters via rotational invariance techniques (ESPRIT) analysis, leading to a suboptimal but closed-form estimator. If the rate parameter is left uncompensated, we establish that the effective SNR is drastically reduced, which further leads to an increased bit error rate (BER). The ML estimator is demonstrated by numerical simulations that show that the performance of the estimator approaches the Crame/spl acute/r-Rao lower bound in the moderate-to-high SNR regions.

Due to the high sensitivity of OFDM to carrier frequency-offset, accurate estimation algorithms are required in order to achieve high performance. We show that many of the existing methods share the same underlying approach, which is the exploitation of null subcarriers. Based on this, a novel computationally simple estimator, named the approximate nonlinear squares estimator (ANLS), is developed. We show that the performance of the ANLS estimator is very close to that of the computationally more demanding NLS estimator, and superior to existing low-complexity estimators.

We consider the problem of optimal allocation of resources between training and data for transmission over a Gauss-Markov fading channel. Inaccurate channel state information (CSI) is available at the receiver through periodic training. There is no feedback, so that CSI is not available at the transmitter. We study MMSE estimators that predict the current channel state based on: all past pilot observations; only the most recent pilot observation; and the most recent and next in the future pilot observations. We analyze the optimal training energy and periodicity for each of these estimators. We show that optimizing the energy and periodicity of training results in significant energy savings over a sensible, but unoptimized, approach, particularly for rapidly varying channels.

We consider distributed detection with a large number of identical sensors deployed over a region where the phenomenon of interest (POI) has unknown spatially varying strength. Each sensor makes a decision based on its own measurement of the signal at its location and the local decision of each sensor is sent to a fusion center through a multiple access channel. The fusion center decides whether the POI has occurred in the region, under a global size constraint in the Neyman-Pearson formulation. Assuming that the initial distribution of sensors is a homogeneous spatial Poisson process, we show that the Poisson process of 'alarmed' sensors satisfies the locally asymptotic normality (LAN) condition as the number of sensor goes to infinity. We derive a new asymptotically locally most powerful (ALMP) detector jointly over the fusion scheme and the sensor threshold. We also derive the conditions on the spatial signal shape to guarantee the existence of the ALMP detector. We show that the optimal test statistic is a weighted sum of local decisions, the optimal weight function being the shape of the spatial signal, but the exact value of the spatial signal is not required. The optimal threshold for a single sensor is also derived. For the case of independent, identically-distributed (i.i.d.) sensor observation, we show that the counting-based detector is also asymptotic locally optimal.

We consider the distributed detection problem with a large number if identical sensors deployed over a region where the phenomenon of interest (POI) has different signal strength depending on the location. Each sensor makes a decision based on its own measurement of the spatially varying signal and the local decision of each sensor is sent to a fusion center through a multiple access channel. The fusion center decides whether the POI has occurred in the region, under a global size constraint in the Neyman-Pearson formulation. Assuming that the initial distribution of sensors is a homogeneous spatial Poisson process, we show that the Poisson process of 'alarmed' sensors satisfies the locally asymptotic normality (LAN) condition as the number of sensor goes to infinity and derive a new asymptotically locally most powerful detector for the spatially varying signal. We show that (1) an optimal test statistic is a weighted sum of local decisions, (2) the optimal weight function is the shape of the spatial signal, and (3) the exact value of the spatial signal is not required. For the case of independent, identical distributed (i.i.d.) sensor observation, we show that the counting-based detector is also asymptotic locally optimal.

This paper presents a temporally correlated single user Rayleigh flat-fading channels with imperfect receiver CSI. A cutoff rate analysis is used to determine the partial CSI of the receiver

We consider a binary pulsed communication system, with possibly episodic transmission, i.e., the system transmits n pulses per information bit and allows for off-time separation between pulses. In the ultra-wideband (UWB) regime, such systems are motivated for overlay applications, as well as low probability of intercept and low probability of detection scenarios. Processing gain enables low-power transmission, and the UWB pulsing limits the interference effects into narrowband systems. We introduce a random ternary sequence model and use this to study multiuser system performance. We consider the issues of processing gain, jamming margin, coding gain, and multiuser interference (MUI) for a single-user matched filter receiver. The introduction of episodic transmission, with a corresponding reduction in bit rate, provides system flexibility with respect to both MUI rejection and handling multipath channels. Highly episodic transmission provides nearly orthogonal low-rate users, even with system asynchrony and no power control. Performance of a single-user RAKE receiver is evaluated via a Chernoff bound on bit error rate, in the presence of MUI. The analysis includes the impact of fading as well as pilot-aided channel estimation.

A noncoherent reception scheme is developed for joint blind estimation of hop timing, hop frequency and direction-of-arrival (DOA) of frequency hopped signals over multipath fading channels. Based on the principle of dynamic programming and 2-dimensional harmonic retrieval, the method does not require knowledge of users' hop codes, and it remains operational even with multiple (unknown) hop rates, frequency offsets, and asynchronism. The model is based on FSK, but the scheme is also evaluated with GMSK modulation and shown to be robust.

Given a noisy sequence of (possibly shifted) integer multiples of a certain period, it is often of interest to estimate the period (and offset). With known integer regressors, the problem is classical linear regression. In many applications, however, the actual regressors are unknown; only categorical information (i.e., the regressors are integers) and, perhaps, loose bounds are available. Examples include hop timing estimation, pulse repetition interval (PRI) analysis, and passive rotating-beam radio scanning. With unknown regressors, this seemingly simple problem exhibits many surprising twists. Even for small sample sizes, a proposed quasi-maximum likelihood approach essentially meets the clairvoyant CRB at moderately high SNR - the latter assumes knowledge of the unknown regressors. This is quite unusual, and it holds despite the fact that our algorithm ignores noise color. We outline analogies and differences between our problem and classical linear regression and harmonic retrieval, and corroborate our findings with careful simulations.

A new semiblind channel estimation technique is proposed for space-time coded wideband CDMA systems using aperiodic and possibly multirate spreading codes. Using a decorrelating matched filter, the received signal is projected onto subspaces from which channel parameters and data symbols can be estimated jointly. Exploiting the subspace structure of the WCDMA signaling and the orthogonality of the space-time code, the proposed algorithm provides the least squares channel estimate in closed form. A new identifiability condition is established. The mean square error of the estimated channel is compared with the Cramer-Rao bound, and a bit error rate (BER) expression for the proposed algorithm is compared with differential schemes.

In this paper we consider a CDMA system equipped with multiple antenna transceivers to implement space-time block coding (STBC). The codes incorporate a cyclic prefix (CP), to facilitate channel equalization and simplify the rejection of multiuser interference (MUI) in broadband transmissions over frequency-selective channels. The only price paid for the introduction of CP is a rate reduction, depending on the relative length of the CP with respect to the code length. To limit, and possibly avoid, this loss, we propose a CDMA/STBC scheme using CP of length smaller than the channel. To prevent interblock interference which would require a sophisticated decoding procedure, we equip the receiver with a MIMO channel shortening filterbank. We derive the conditions under which we can achieve perfect shortening using an FIR filterbank. Finally, we show that the choice of a CP length represents a trade-off between the rate reduction factor and the SNR loss resulting from the insertion of the channel shortening filter.

We address the problem of carrier frequency offset (CFO) synchronization in OFDM-based communications systems in the context of frequency-selective fading channels. A blind CFO estimator was recently developed, which exploits the virtual subcarriers (VSC) in a practical OFDM system. Here, we propose a semi-blind approach where a few (either zero or non-zero) pilots are inserted in the OFDM block. The semi-blind estimator (SBE) is shown to significantly outperform the blind estimator even with a few pilots provided they are equispaced. Further, the SME based on zero pilots consistently outperforms that based on non-zero pilots. Reliable estimation of an unknown frequency-selective channel requires that some (or all) of the pilots be non-zero, since zero pilots are useless for channel estimation. It is shown that if the total number of pilots is (much) larger that the channel order, zero pilots and non-zero pilots lead to almost the same CFO estimation performance. Therefore, in this case, non-zero pilots should be preferred to zero pilots.

We compare single user digital multi-carrier spread spectrum (MC-SS) modulation with direct sequence (DS) SS (with a modified implementation) in the presence of narrowband interference (NBI) and multipath fading. We derive closed-form expressions for the symbol error probability for both the linear MMSE receiver as well as the conventional matched-filter receiver under different scenarios: additive white Gaussian noise (AWGN) channel with NBI, multipath channel with or without NBI. We show that DS-SS can achieve the same performance as MC-SS if the spreading code is carefully designed to have perfect periodic autocorrelation function (PACF). On the other hand, MC-SS is more robust to narrowband interference and multipath fading than is DS-SS with the widely used spreading codes that do not possess perfect PACE. Our analysis reveals that the performance improvement of MC-SS is precisely due to the implicit construction of an equivalent spreading code having nonconstant amplitude but possessing perfect periodic autocorrelation.

We address the problem of frequency synchronization in OFDM-based communications systems in the context of frequency-selective fading channels. Frequency offsets are estimated by inserting null sub-carriers into a single OFDM block. The paper clarifies issues related to acquisition range and identifiability of carrier frequency offset (CFO), and performance of estimators. A deterministic maximum likelihood estimation approach is adopted. We derive necessary and sufficient conditions on the number of null-subcarriers and their placement in order to ensure identifiability. The Cramer-Rao bound (CRB) for the CFO is derived; for a given number of null sub-carriers, the optimal placement which minimizes the CRB is derived. We show that if the number of null sub-carriers is less than half the total number of sub-carriers, performance is optimal when the null sub-carriers are equispaced.

We address the problem of estimating changes in fractional integrated ARMA (FARIMA) processes. These changes may be in the long range dependence (LRD) parameter or the ARMA parameters. The signal is divided into "elementary" segments: the objective is then to estimate the segments in which the changes occur. This estimation is achieved by minimizing a penalized least-squares criterion based on the parameter estimates computed in each segment. The optimization problem is then solved using a dynamic programming algorithm. Simulation results on synthetic data (computer network traffic) are reported.

We compare single user digital multi-carrier spread spectrum modulation with direct sequence spread spectrum in the presence of frequency-selective multipath fading. We derive closed-form expressions for the bit error probability and show that MC-SS is more robust to multipath fading than is DS-SS.

Blind synchronization of minimum-shift-keying signals in the context of time-selective fading communication channels is considered. Strictly feedforward algorithms based on second- and fourth-order cyclic statistics are proposed for frequency and timing offset estimation. The new estimators are shown to outperform existing methods. Extensions of the algorithm to GMSK are also studied. Finally, fourth-order cyclic statistics are shown to provide an accurate estimate of the Doppler spread.

Scale mixtures of the Gaussian have been used to approximate the PDF of symmetric alpha stable processes. Such mixtures, however, cannot easily capture the heavy-tails. We propose to use Cauchy-Gaussian mixtures which are natural in this setting. Variations of standard EM algorithms can be used to estimate the parameters of the noise PDFs under various scenarios (noise-only data, weak-signal assumption, partially known-signal case). The fitted mixture models can be used for detection and estimation. In the multivariate case, we present several results on Gaussian mixture approximations of sub-Gaussian PDFs, including robust estimation of the underlying correlation matrix.

The problem of channel estimation for a frequency hopping system is considered. Under a discrete multipath fading model, the path gains and delays are estimated separately. By exploiting fixed (but unknown) patterns in the data packet, the delay estimation problem is formulated in an ESPRIT-like format by identifying multiple rotational invariance structures in the received data. Since ESPRIT is limited to exploitation of single invariance, the previously proposed SPECC algorithm is employed for the multipath delay estimation. Performance results based on simulations are presented.

A simple method, based on elementary fourth-order cumulants, is proposed for the classification of digital modulation schemes. These statistics are natural in this setting as they characterize the shape of the distribution of the noisy baseband I and Q samples. It is shown that cumulant-based classification is particularly effective when used in a hierarchical scheme, enabling separation into subclasses at low signal-to-noise ratio with small sample size. Thus, the method can be used as a preliminary classifier if desired. Computational complexity is order N, where N is the number of complex baseband data samples. This method is robust in the presence of carrier phase and frequency offsets and can be implemented recursively. Theoretical arguments are verified via extensive simulations and comparisons with existing approaches.

This paper considers the problem of estimating the parameters of chirp signals with randomly time-varying amplitude. Two methods for solving this problem are presented. First, a nonlinear least-squares approach (NLS) is proposed. It is shown that by minimizing the NLS criterion with respect to all samples of the time-varying amplitude, the problem reduces to a two-dimensional maximization problem. A theoretical analysis of the NLS estimator is presented and an expression for its asymptotic variance is derived. It is shown that the NLS estimator has a variance very close to the Cramer-Rao bound. The second approach combines the principles behind the high-order ambiguity function (HAF) and the NLS approach. It provides a computationally simpler but suboptimum estimator. A statistical analysis of this estimator is also carried out. Numerical examples attest to the validity of the theoretical analysis and establish a comparison between the two proposed methods.

The problem of estimating the phase parameters of a phase modulated signal in the presence of coloured multiplicative noise (random amplitude modulation) and additive white noise, both Gaussian, is addressed. Closed-form expressions for the exact and large-sample Cramer-Rao bounds (CRB) are derived. It is shown that the CRB is not significantly affected by the colour of the modulating process, especially when the signal-to-noise ratio is high. Hence, maximum likelihood type estimators which ignore the noise colour and optimize a criterion with respect to only the phase parameters are proposed. These estimators are shown to be equivalent to the nonlinear least squares estimators which consist of matching the squared observations with a constant amplitude phase modulated signal when the mean of the multiplicative noise is forced to zero. Closed-form expressions are derived for the efficiency of these estimators, and are verified via simulations.

We analyze discrete wavelet transform (DWT) multiscale products for detection and estimation of steps. Here the DWT is an over complete approximation to smoothed gradient estimation, with smoothing varied over dyadic scale, as developed by Mallat and Zhong (1992). The multiscale product approach was first proposed by Rosenfeld (1970) for edge detection. We develop statistics of the multiscale products, and characterize the resulting non-Gaussian heavy tailed densities. The results may be applied to edge detection with a false-alarm constraint. The response to impulses, steps, and pulses is also characterized. To facilitate the analysis, we employ a new general closed-form expression for the Cramer-Rao bound (CRB) for discrete-time step-change location estimation. The CRB can incorporate any underlying continuous and differentiable edge model, including an arbitrary number of steps. The CRB analysis also includes sampling phase offset effects and is valid in both additive correlated Gaussian and independent and identically distributed (i.i.d.) non-Gaussian noise. We consider location estimation using multiscale products, and compare results to the appropriate CRB.

The paper addresses the problem of detecting two spectrally equivalent parametric processes (SEPP): the noisy AR process and the ARMA process. Higher-order statistics (HOS) are shown to be effective for detection. Two HOS based detectors are derived and compared. The fist detector studies the singularity of a HOS-based Yule-Walker matrix. The second detector filters the data by an AR filter estimated from the data; the residual HOS are then shown to be effective for the SEPP detection problem.

We consider step detection and estimation using a multiscale wavelet analysis, based on the ability of a certain discrete wavelet transform (DWT) to characterize signal steps and edges. This DWT, developed by Mallat and Zhong (1992), estimates the gradient at various smoothing levels without downsampling in time. As first proposed by Rosenfeld (1970) for edge sharpening, multiple scales are combined by forming the pointwise product across scales. We show that this approach is a non-linear whitening transformation, and characterize the non-Gaussian PDF of the output. Detection curves are shown for parameterized sigmoidal step change signals. Step location estimation performance is also shown, with comparison to the Cramer-Rao bound in additive white Gaussian noise.

The problem of interest is the estimation of the parameters of harmonics in the presence of additive and multiplicative noise. Expressions for the asymptotic performance of the cyclic-variance (CV) based method are derived when the multiplicative noise has a non-zero mean. We show that the CV-based method may yield more accurate results than methods based on the cyclic mean (CM), depending upon the color of the noise and the intrinsic and local SNRs. The performance is analyzed in detail for several special cases of the multiplicative noise, such as white Gaussian, AR and generalized-Gaussian noise.

Although alpha-stable processes have infinite variance, one can define and consistently estimate the normalized correlations and cumulants of linear processes with stable innovations. Hence, conventional techniques can be used to estimate the parameters of nonminimum phase alpha-stable processes.

Current algorithms for estimating the parameters of a symmetric alpha-stable ARMA process are either highly non-linear, or assume small MA orders (q/spl les/3), or invoke the minimum-phase assumption. We use results from the statistics literature to show that the normalized correlation is well-defined; we show that the normalized cumulants are also well-behaved. We propose to use the correlation to estimate the spectrally-equivalent minimum-phase (SEMP) parameters, and then to use the cumulants to resolve the phase of the model. We also show that correlation-based techniques (such as ESPRIT) work well for estimating the parameters of harmonics observed in alpha-stable noise. Correlation-based algorithms are shown to work well despite the infinite variance of the alpha-stable process.

Considers the parameter estimation problem for a class of amplitude modulated polynomial phase signals (PPS), observed in noise. The main contributions of the paper are: (1) The authors prove that the high-order ambiguity function (HAF) is invariant to certain types of amplitude modulation; thus, phase parameter estimation proceeds as in the constant amplitude case. (2) The authors derive the Cramer-Rao bounds for both the amplitude and phase parameters, when the additive noise is white Gaussian. (3) They show that the HAF is almost additive for multi-component PPS. (4) They establish the covariance bounds for the nonlinear least squares estimator when the additive noise is (non) Gaussian, and satisfies some weak mixing conditions.

We consider the problem of estimating the parameters of harmonics (with non-random parameters) observed in zero mean (colored/white, Gaussian/non-Gaussian) stationary mixing noise. A new fourth-order moment based non-parametric estimator is introduced, and it is shown that this estimator is superior to the conventional second-order estimator at all SNR's. The variance of the frequency estimator is shown to converge as 1/T/sup 3/; for the harmonic with frequency /spl omega//sub 0/, and amplitude A/sub 0/, the peak amplitude of the normalized fourth-order spectrum is shown to be /spl alpha/(/spl omega//sub 0/)(|A/sub 0/|/sup 2//2/spl sigma//sub /spl upsi///sup 2/+1)/sup 2/ where /spl alpha/(/spl omega//sub 0/) is the local SNR, and /spl sigma//sub /spl upsi///sup 2/ is the noise variance.>

Gerr's Wigner bispectrum is generalized, and the properties of the resulting time-frequency distribution are studied. Continuous- and discrete-time versions, aliasing problems, and analysis and synthesis techniques are studied. Extensions to higher-order Wigner distributions are briefly discussed. It is stressed that third-order Wigner distributions will enjoy the robustness of third-moment statistics to symmetrically distributed noise only if they are average across time (short-time bispectra) or across independent realizations. Potential applications are discussed, including detection and quantification of quadratic phase coupling in nonstationary signals, such as speech and seismic signals, as well as electroencephalograms and electrocardiograms.>

The problem of estimating the order and parameters of a noncausal autoregressive moving average (NCARMA) model excited by an unobservable independent and identically distributed process is addressed. The observed output may be corrupted by additive colored Gaussian noise. A fourth-order cumulant based parameter estimator is proposed, and the consistency of the estimator is established. The proposed algorithm leads readily to an order determination algorithm as well. The algorithms can be extended to higher-orders, but not to third-order cumulants. Once the AR parameters have been estimated, the AR-compensated residual time-series may be estimated.>

Using a compact Kronecker-product-based representation for the cumulants of vector processes, the authors develop several techniques for estimating the parameters of a multichannel ARMA (autoregressive moving average) process, from sample cumulants of the output processes: (1) the AR parameters are estimated first; the MA parameters are then estimated from the AR compensated time series. (2) AR and IR (impulse response) parameters are estimated simultaneously; (3) an algorithm that handles causal as well as noncausal ARMA models, by transforming the ARMA parameter estimation problem to a pair of MA parameter estimation problems, is given. Order-determination techniques are also proposed. The algorithms are applicable to both stochastic and deterministic problems.>

Using the observable state-space realization corresponding to a given multi-input-multi-output autoregressive moving average (ARMA) model, the authors derive closed-form and lag-recursive expressions for the cumulants of the output process. Their approach involves the computation of cumulants of vector processes, which they define compactly in terms of Kronecker products, and leads to a unified treatment of multichannel, time-varying and nonstationary processes. Computational aspects are discussed in detail. A new cumulant-based identification method is proposed in which the matrices of the SSM are first estimated and then transformed to ARMA parameters.>

The authors extrapolate, in the maximum-entropy (ME) sense, one-dimensional (1-D) cumulant statistics of a stationary random process which is the output of a linear, time-invariant (LTI) model excited by a non-Gaussian, independent and identically distributed input. The entropy rate of a linear process, is related with a special 1-D polyspectrum. Based on this relationship they derive 1-D polyspectral estimates that correspond to the most random time series whose cumulant sequence is consistent with the given finite set of 1-D cumulant statistics. The ME extension of the cumulant sequence of linear processes corresponds to that of an AR (autoregressive) process whose coefficients can be computed as the solution of a system of linear equations. The AR filter obtained using the ME cumulant extrapolation is applied to harmonic retrieval, and phase estimation of nonminimum-phase LTI systems.>

A statistical multidimensional sequence, generated by a non-Gaussian process, passes through a linear space-invariant (perhaps ARMA) model and colored Gaussian noise is added at the output. Given output cumulants, algorithms are derived for the nonparametric reconstruction of the system's phase as well as for the parametric identification of the ARMA model, which can be noncausal or have nonseparable denominator.>

A lattice version of the recursive instrumental variable method for adaptive parameter identification of ARMA (autoregressive moving-average) processes is developed. Appropriate choice of the instrumental variables leads to cumulant-based AR parameter estimates. Cumulant-based normal equations may be obtained by using nonconventional orthogonality conditions in the linear prediction problem. The development leads to a pair of lattices, one excited by the observed process y(n), and the other by the instrumental process z(n). The lattices are coupled through order-update and time-update equations. The lattice structure yields the AR compensated residual time series. Hence, adaptive versions of cumulant-based MA parameter identification algorithms are directly applicable. Some convergence results are presented.>

A time-series consisting of sinusoids observed in additive i.i.d. noise or in additive colored Gaussian noise of unknown spectral density is considered. The number of harmonics, as well as their amplitudes and frequencies are determined using the one-dimensional diagonal slice of the fourth-order cumulant. Applications to the detection of cubic phase coupling are discussed.>