This paper proposes a novel algorithm to retroactively compute the evolution of edge signals from a given sequence of partial observations from topological structures, a concept referred to as evolution backcasting. Our backcasting algorithm exploits the spatio-temporal dependencies present in the real-world edge signals using the simplicial vector autoregressive (S-VAR) model. The proposed algorithm jointly estimates the S-VAR filter coefficients and recovers missing data from the partial observations. Subsequently, the algorithm capitalizes on the learned S-VAR model and the reconstructed signals to execute the backcasting of edge signal evolution. Using traffic and water distribution networks as case studies, we showcase the superior capabilities of our algorithm compared with baseline alternatives.

The performance of reproducing kernel Hilbert space-based methods is known to be sensitive to the choice of the reproducing kernel. Choosing an adequate reproducing kernel can be challenging and computationally demanding, especially in data-rich tasks without prior information about the solution domain. In this paper, we propose a learning scheme that scalably combines several single kernel-based online methods to reduce the kernel-selection bias. The proposed learning scheme applies to any task formulated as a regularized empirical risk minimization convex problem. More specifically, our learning scheme is based on a multi-kernel learning formulation that can be applied to widen any single-kernel solution space, thus increasing the possibility of finding higher-performance solutions. In addition, it is parallelizable, allowing for the distribution of the computational load across different computing units. We show experimentally that the proposed learning scheme outperforms the combined single-kernel online methods separately in terms of the cumulative regularized least squares cost metric.

Vector autoregressive (VAR) model is widely used to model time-varying processes, but it suffers from prohibitive growth of the parameters when the number of time series exceeds a few hundreds. We propose a simplicial VAR model to mitigate the curse of dimensionality of the VAR models when the time series are defined over higher-order network structures such as edges, triangles, etc. The proposed model shares parameters across the simplicial signals by leveraging the simplicial convolutional filter and captures structure-aware spatio-temporal dependencies of the time-varying processes. Targetting the streaming signals from the real-world nonstationary networks, we develop a group-lasso-based online strategy to learn the proposed model. Using traffic and water distribution networks, we demonstrate that the proposed model achieves competitive signal prediction accuracy with a significantly less number of parameters than the VAR models.

Multi-agent deep reinforcement learning (MADRL), where a group of agents inside multi-agent systems cooperate to achieve a common goal, has been shown useful in many applications such as collaborative robots, autonomous driving or video games involving teams. In this paper, we propose two multi-agent deep reinforcement learning (MADRL) frameworks for value function factorization built by using Graph Convolutional Neural Networks (GCNN) based on neighborhood graph filters (NGFs). These MADRL frameworks are based on the paradigm of centralized training with decentralized execution (CTDE). In this work, we show that the superior stability of the NGFs as compared to standard graph filters leads also to superior performance for the MADRL algorithms. In the first MADRL framework, the NGF-based GCNN is used to predict the local q-value at each of the agents, while in the other one, the NGF-based GCNN is used to mix the local q-values to generate a global Q-value. We have compared the performance of NGF-based GCNNs over state-of-the-art graph neural networks for value function factorization in the MADRL framework for the StarCraft II and Coalition Structure Generation problems. The results show that the proposed MARL frameworks outperform the existing state-of-art architectures.

While Deep Learning based methods can solve complex problems by employing Neural Networks to act as powerful function approximators, they often suffer from inflexibility in terms of deployment beyond the training scenario and also include irrelevant data priors in the form of an ordered array of input values. This problem is quite evident in the field of Multi-Agent Reinforcement Learning (MARL), where most research covers methods that are trained on a fixed number of agents, restricted by the fixed size of the input vector. In this paper, we argue that this is not a reasonable assumption, both in terms of the inflexible amount of environmental information and the restrictive nature of the structure of the information. We explore DeepSets and Set Transformers as two powerful set function approximators to address the problem of cardinality invariance and permutation invariance in the observation space of a reinforcement learning agent. We explain Set-Input Reinforcement Learning (SIRL) in detail and evaluate the performance of the DeepSets and Set Transformer methods through simulated experiments on a challenging multi-agent environment, that otherwise yields sub-optimal policies through traditional function approximation approaches. We demonstrate that both DeepSets and Set Transformer based encoders scale well to increasing the number of agents from training to evaluation.

Accurate estimation of radio maps is important for various applications of wireless communications, such as network planning, and resource allocation. To learn accurate radio map models, one needs to have accurate knowledge of transmitter and receiver locations. However, it is difficult to obtain accurate locations in practice, especially, in scenarios having a high degree of wireless multi-path. Alternatively, time of arrival (ToA) features, which are easier to obtain, can be employed for estimating radio maps. To this end, this paper investigates the application of transfer learning method using ToA features for estimating radio maps under indoor wireless communications. The performance is compared with the scenarios where only the locations of receivers and both ToAs and locations of receivers, are used for estimating radio maps, assuming that locations are known. Due to the changes in propagation characteristics, a radio map model learned in a specific wireless environment cannot be directly employed in a new wireless environment. To address this issue, a data-driven transfer learning method is designed that transfers and fine-tunes a deep neural network model learned for a radio map from a source wireless environment to other distinct (target) wireless environments. Our proposed method predicts the training data required in the new wireless environments using a data-driven similarity measure. Our results demonstrate that using ToA (location-free) features results in a superior performance for estimating radio maps in terms of the necessary number of sensor measurements for estimating radio maps with a good accuracy, as compared to a location-based approach, where it may be difficult to have accurate location estimations. It leads to a saving of 70-90% of the necessary sensor measurement data for a mean square error (MSE) of 0.004.

An online algorithm for missing data imputation for networks with signals defined on the edges is presented. Leveraging the prior knowledge intrinsic to real-world networks, we propose a bi-level optimization scheme that exploits the causal dependencies and the flow conservation, respectively via(i)a sparse line graph identification strategy based on a group-Lasso and(ii)a Kalman filtering-based signal reconstruction strategy developed using simplicial complex (SC) formulation. The advantages of this first SC-based attempt for time-varying signal imputation have been demonstrated through numerical experiments using EPANET models of both synthetic and real water distribution networks.

Multi-Agent Reinforcement Learning (MARL) algorithms based on the Centralised Training Decentralised Execution (CTDE) approach have seen a great deal of interest in recent years. Most of the recent works focus on a specific class of environments built on the StartCraft Multi-Agent Challenge (SMAC) environment suite. However, experiments with the PettingZoo multi-particle environments show poor performance in an interesting subset of tasks. In this paper, the nature of these environments and the reward structures are analyzed. It shows that poor performance in these tasks is not due to a lack of representation power in the individual Q function or mixing functions, but rather a result of convergence to a suboptimal equilibrium of dual channel rewards and the issue of agent-reward decoupling that can be a common problem for many MARL environments. We present reward curriculum-based versions of QMIX and VDN as a solution to these problems and compare their results with the standard algorithms. The results show a clear performance gain in terms of a common cumulative reward metric.

This paper presents the design of a data-driven algorithm for a multi-user channel aware single step signal detection system in Non-Orthogonal Multiple Access (NOMA) wireless communication networks. In a NOMA downlink system, the Successive Interference Cancellation (SIC) decoding process can be performed at the receiver, where users are decoded based on their channel behavior. The SIC detection accuracy largely depends on the estimation accuracy of the Channel State Information (CSI) which is highly difficult in general due to the non-linear and non-stationary nature of the real wireless channels. Moreover, SIC performance is limited by the receiver complexity and error propagation problems. In this paper, we design a Deep Learning (DL) based NOMA receiver that considers jointly the CSI and detects the originally transmitted symbols of the multiple users. This approach differs from the existing NOMA receivers that use SIC decoding because our proposed DL-based channel aware single-step signal detection method allows each user to detect their symbols using their respective Deep Neural Network (DNN) in a single step. The DNNs are first trained offline using data generated from the channel realizations and labelled symbol data, and then they are tested in terms of recovering new transmitted symbols directly. Our simulation results show that the DL-based approach provides a better symbol detection performance than the SIC.

In this paper, we investigate the application of transfer learning to train a Deep Neural Network (DNN) model for joint channel and power allocation in underlay device-todevice (D2D) communication. Based on the traditional optimization solutions, generating training dataset for scenarios with perfect channel state information (CSI) is not computationally demanding, compared to scenarios with imperfect CSI. Thus, a transfer learning-based approach can be exploited to transfer the DNN model trained for the perfect CSI scenarios to the imperfect CSI scenarios. We also consider the issue of defining the similarity between two types of resource allocation tasks. For this, we first determine the value of outage probability for which two resource allocation tasks are same, that is, for which our numerical results illustrate the minimal need of relearning from the transferred DNN model. For other values of outage probability, there is a mismatch between the two tasks and our results illustrate a more efficient relearning of the transferred DNN model. Our results show that the learning dataset required for relearning of the transferred DNN model is significantly smaller than the required training dataset for a DNN model without transfer learning.

Underlay device-to-device (D2D) communications improve the spectral efficiency by simultaneously allowing direct communication between D2D-users on the same channels as cellular-users (CUs). However, most related works consider perfect channel-state-information (CSI) with single-antenna transmissions and usually assign each channel to one D2D pair. In this work, we formulate an optimization problem for maximizing the aggregate rate of all D2D pairs and CUs in single and multiple antenna configurations under imperfect CSI, by optimizing channel and power resources. Our formulation guarantees probability of outage below a specified threshold and fairness in channel allocation across D2D pairs. The resulting problem is a stochastic-mixed-integer-non-convex problem, we solve it approximately by alternating between power-allocation and channel-assignment sub-problems. The stochastic objective and outage constraints are addressed by the concept of order-of-statistics in the single-antenna case and the Bernstein-type inequality in the multiple-antenna configuration. The power-allocation sub-problem is solved by exploiting a quadratic-transformation, while the channel-assignment sub-problem is solved by integer relaxation. Furthermore, two computationally efficient algorithms are proposed to approximately solve the problem in a partially decentralized manner. We also establish convergence guarantees for the different algorithms proposed in this work. Simulation results show that the proposed approach achieves higher throughput compared to the state-of-the-art alternatives.

Improving the energy-efficiency of remotely deployed sensor nodes in agriculture wireless networks is very challenging due to a lack of access to energy grid. Network clustering and limiting the amount of sensor data are among the various methods to improve the lifetime of these sensor nodes. In this work, an optimal sensor-selection scheme is proposed to improve the Quality of Service in clustered agriculture networks. the proposed method selects a limited number of sensor nodes to be active in each cluster. It considers the estimator performance while selecting limited sensor nodes for environmental monitoring. the optimal sensor-selection process considers the information of remaining energy of sensor nodes in agriculture wireless networks. the proposed method selects a limited number of nodes in each cluster while maximizing the estimator performance at the receiver. Our cluster based sensor-selection scheme optimizes the energy-efficiency in a distributed manner. Network clustering also ensures a uniform sensor-selection over a network area. Extensive experiments are conducted to analyse the performance of the proposed optimal sensor-selection method over different network scenarios. Our experimental results indicate significant improvements in energy-efficiency of agriculture wireless sensor networks and motivate the proposed method in practice.

Decentralized signal processing performs learning tasks on data distributed over a multi-node network which can be represented by a graph. Implementing linear transformations emerges as a key task in a number of applications of decentralized signal processing. Recently, some decentralized methods have been proposed to accomplish that task by leveraging the notion of graph shift operator, which captures the local structure of the graph. However, existing approaches have some drawbacks such as considering special instances of linear transformations, or reducing the family of transformations by assuming that a shift matrix is given such that a subset of its eigenvectors spans the subspace of interest. In contrast, this paper develops a decentralized method to compute linear transformations in a small number of iterations. To this end, a set of successive graph shift operators is designed. Hence, a new optimization problem is proposed whose goal is to compute the desired transformation as fast as possible.

Abstract This paper presents a sparse code multiple access (SCMA) system with massive antennas at the base station. This system is referred to as M‐SCMA system. A spectrally‐efficient and massive access next‐generation wireless network is realized through massive antennas and non‐orthogonal SCMA techniques. Two detection algorithms, namely, modified message passing algorithm (MMPA) and extended message passing algorithm (EMPA) are proposed to detect multiple users' symbols in M‐SCMA. A deep learning (DL)‐based detection scheme is also proposed for M‐SCMA so as to avoid channel estimation and to lower the detection complexity. Numerical results show that the DL‐based detection has similar performance as MMPA even when the channel information is not estimated explicitly. Furthermore, authors also establish the sum rate trade‐off between SCMA and orthogonal multiple access in a massive antenna system. The impact of various M‐SCMA parameters such as the number of antennas and the overloading factor, on the proposed DL, MMPA, and EMPA‐based detection are also investigated.

Multicast device-to-device communications operating underlay with cellular networks is a spectral efficient technique for disseminating data to nearby receivers. However, due to the critical challenge of having an intelligent interference coordination between multicast groups along with the cellular network, it is necessary to judiciously perform resource allocation for the combined network. In this work, we present a framework for a joint channel and power allocation strategy to maximize the sum rate of the combined network while guaranteeing minimum rate to individual groups and cellular users. The objective function is augmented by an austerity function that penalizes excessive assignment of low rate channels. The formulated problem is a mixed-integer-non-convex program, which requires exponential complexity to obtain the optimal solution. To tackle this, we exploit fractional programming and integer relaxation to obtain a parametric convex approximation. Based on sequential convex approximation approach, we first propose a centralized algorithm that ensures convergence to a limit point. Next, we propose a distributed algorithm in which via dual decomposition, separable sub-problems are formulated to be solved at the respective groups in cooperation with the base station. We provide convergence guarantees of the proposed solutions and demonstrate their merits by simulations, showing improvement in network throughput.

In order to estimate the channel gain (CG) between the locations of an arbitrary transceiver pair across a geographic area of interest, CG maps can be constructed from spatially distributed sensor measurements. Most approaches to build such spectrum maps are location-based, meaning that the input variable to the estimating function is a pair of spatial locations. The performance of such maps depends critically on the ability of the sensors to determine their positions, which may be drastically impaired if the positioning pilot signals are affected by multipath channels. An alternative location-free approach was recently proposed for spectrum power maps, where the input variable to the maps consists of features extracted from the positioning signals, instead of location estimates. The location-based and the location-free approaches have complementary merits. In this work, apart from adapting the location-free features for the CG maps, a method that can combine both approaches is proposed in a mixture-of-experts framework.

Robust beamforming is an efficient technique to guarantee the desired receiver performance in the presence of erroneous channel state information (CSI). However, the application of robust beamforming in underlay device-to-device (D2D) communication still requires further investigation. In this paper, we investigate resource allocation problem for underlay D2D communications by considering multiple antennas at the base station (BS) and at the transmitters of D2D pairs. The proposed design problem aims at maximizing the aggregate rate of all D2D pairs and cellular users (CUs) in downlink spectrum. In addition, our objective is augmented to achieve a fair allocation of resources across the D2D pairs. Further, assuming elliptically bounded CSI errors, the formulation ensures maintaining signal to interference plus noise ratio (SINR) above a specified threshold. The derived optimization problem results in a mixed integer non-convex problem and requires exponential complexity to obtain the optimal solution. We perform a semi-definite relaxation (SDR) to handle the stochastic SINR constraints by using the S-Lemma, obtaining a number of linear matrix inequalities. The non-convexity is addressed by introducing slack variables and performing a quadratic transformation to obtain sub-optimal beamformers via alternating optimization. The solution for channel assignments to D2D pairs is obtained by convex relaxation of the integer constraints. Finally, we demonstrate the merit of the proposed approach by simulations in which we observe higher and more robust network throughput, as compared to previous state-of-the-art.

Multicast device-to-device (D2D) communications operating underlay with cellular networks is a spectral efficient technique for disseminating data to the nearby receivers. However, due to critical challenges such as, mitigating mutual interference and unavailability of perfect channel state information (CSI), the resource allocation to multicast groups needs significant attention. In this work, we present a framework for joint channel assignment and power allocation strategy to maximize the sum rate of the combined network. The proposed framework allows access of multiple channels to the multicast groups, thus improving the achievable rate of the individual groups. Furthermore, fairness in allocating resources to the multicast groups is also ensured by augmenting the objective with a penalty function. In addition, considering imperfect CSI, the framework guarantees to provide rate above a specified outage for all the users. The formulated problem is a mixed integer nonconvex program which requires exponential complexity to obtain the optimal solution. To tackle this, we first introduce auxiliary variables to decouple the original problem into smaller power allocation problems and a channel assignment problem. Next, with the aid of fractional programming via a quadratic transformation, we obtain an efficient power allocation solution by alternating optimization. The solution for channel assignment is obtained by convex relaxation of integer constraints. Finally, we demonstrate the merit of the proposed approach by simulations, showing a higher and a more robust network throughput.

A large number of applications in Wireless Sensor Networks include projecting a vector of noisy observations onto a subspace dictated by prior information about the field being monitored. In general, accomplishing such a task in a centralized fashion, entails a large power consumption, congestion at certain nodes and suffers from robustness issues against possible node failures. Computing such projections in a decentralized fashion is an alternative solution that solves these issues. Recent works have shown that this task can be done via the so-called graph filters where only local inter-node communication is performed in a distributed manner using a graph shift operator. Most of the existing methods have focused on the design of graph filters for symmetric topologies to compute an exact subspace projection. However, in this paper, motivated by the asymmetric communications in Wireless Sensor Networks, we analyze the design of graph shift operators to perform decentralized subspace projection for asymmetric topologies. we first characterize the existence of solutions and then we present a convex optimization problem that considers also the efficiency of the graph filtering, with an ADMM-based solver.

Wireless sensor networks (WSNs) are considered as a major technology enabling the Internet-of-Things (IoT) paradigm. The recent emerging graph signal processing field can also contribute to enabling the IoT by providing key tools, such as graph filters (GFs), for processing the data associated with the sensor devices. GFs can be performed over WSNs in a distributed manner by means of a certain number of communication exchanges among the nodes. But, WSNs are often affected by interferences and noise, which leads to view these networks as directed, random and time-varying graph topologies. Most of the existing works neglect this problem by considering an unrealistic assumption that claims the same probability of link activation in both directions when sending a packet between two neighboring nodes. This work focuses on the problem of operating graph filtering in random asymmetric WSNs. We show first that graph filtering with finite impulse response GFs (node-invariant and node-variant) requires having equal connectivity probabilities for all the links in order to have an unbiased filtering, which cannot be achieved in practice in random WSNs. After this, we characterize the graph filtering error and present an efficient strategy to conduct graph filtering tasks over random WSNs with node-variant GFs by maximizing accuracy, that is, ensuring a small bias-variance tradeoff. In order to enforce the desired accuracy, we optimize the filter coefficients and design a cross-layer distributed scheduling algorithm (CDSA) at the MAC layer. Extensive numerical experiments are presented to show the efficiency of the proposed solution as well as the CDSA for the denoising application.

Since the spectral efficiency of wireless communications is already close to its fundamental bounds, a significant increase in spatial efficiency is required to meet future traffic demands. Device-to-device (D2D) communications provide such an increase by allowing nearby users to communicate directly without passing their packages through the base station. To fully exploit the benefits of this paradigm, proper channel assignment and power allocation algorithms are required. The main limitation of existing schemes, which restrict D2D transmitters to operate on a single channel at a time, is circumvented by the joint channel assignment and power allocation algorithm proposed in this paper. This algorithm relies on convex relaxation to efficiently obtain nearly-optimal solutions to the mixed-integer program arising in this context. Numerical experiments corroborate the merits of the proposed scheme relative to state-of-the art alternatives.

In this paper, we consider a joint topology and radio resource optimization for device-to-device (D2D) based mobile social networks. The considered social network is an interest based which is modeled as a d-intersection binomial random graph. The Radio network is also modeled as a random graph where an edge between any two distinct nodes is activated with a certain probability that is equivalent to the probability of exceeding a certain signal to interference ratio for that link. The entire network is then modeled as an intersection graph between the social and radio induced graphs. Thereafter, network topology is optimized such that enabled social edges satisfy certain network connectivity constrains under specific radio environment characteristics. Radio resource allocation is performed to maximize the radio resource utilization exploiting both social ties awareness among the network nodes and knowledge of channel gains among users' locations. We formulate our radio resource allocation problem as a semidefinite program over a graph representing the network topology. Simulation based numerical results are shown in terms of achieved link efficiency and optimized topology parameters.

Spectrum cartography constructs maps of metrics such as channel gain or received signal power across a geographic area of interest using measurements of spatially distributed sensors. Applications of these maps include network planning, interference coordination, power control, localization, and cognitive radio to name a few. Existing spectrum cartography methods necessitate knowledge of sensor locations, but such locations cannot be accurately determined from pilot positioning signals (such as those in LTE or GPS) in indoor or dense urban scenarios due to multipath. To circumvent this limitation, this paper proposes localization-free cartography, where spectral maps are directly constructed from features of these positioning signals rather than from location estimates. The proposed algorithm capitalizes on the framework of kernel-based learning and offers improved prediction performance relative to existing alternatives, as demonstrated by a simulation study in a street canyon.

A significant number of linear inference problems in wireless sensor networks can be solved by projecting the observed signal onto a given subspace. Decentralized approaches avoid the need for performing such an operation at a central processor, thereby reducing congestion and increasing the robustness and the scalability of the network. Unfortunately, existing decentralized approaches either confine themselves to a reduced family of subspace projection tasks or need an infinite number of iterations to obtain the exact projection. To remedy these limitations, this paper develops a framework for computing a wide class of subspace projections in a decentralized fashion by relying on the notion of graph filtering. To this end, a methodology to obtain the shift matrix and the corresponding filter coefficients that provide exact subspace projection in a nearly minimal number of iterations is proposed. Numerical experiments corroborate the merits of the proposed approach.

This paper presents a framework for spectrum cartography based on the use of adaptive Gaussian radial basis functions (RBF) centered around a specific number of centroid locations, which are determined, jointly with the other RBF parameters, by the available measurement values at given sensor locations in a specific geographical area. The spectrum map is constructed non-parametrically as no prior knowledge about the transmitters is assumed. The received signal power at each location (over a given bandwidth and time period) is estimated as a weighted contribution from different RBF, in such a way that the both RBF parameters and the weights are jointly optimized using an alternating minimization method with a least squares loss function and a quadratic regularization term. Our method is evaluated through simulations, showing a performance (in terms of normalized MSE) that is comparable to semi-parametric methods, and even superior as the number of sensors or RBF increases.

Wireless Sensor Networks have emerged as a very powerful tool for the monitoring and control, over large areas, of diverse phenomena. One of the most appealing properties of these networks is their potentiality to perform complex tasks in a total distributed fashion, without requiring a central entity. In this scenario, where nodes are constrained to use only local information and communicate with one-hop neighbors, iterative consensus algorithms are extensively used due to their simplicity. In this work, we propose the design of a consensus-based distributed Kalman filter for state estimation, in a sensor network whose connections are subject to random failures. As a result of this unreliability, the agreement value of the consensus process is a random variable. Under these conditions, we ensure that the estimator is unbiased, and adaptively compute the gain of the filter by considering the statistical properties of the consensus process. To the best of our knowledge, this is the first time that the design of a consensus-based distributed Kalman filter is addressed by considering the random error introduced by the consensus process. We present some numerical results that confirm the validity of our approach.

Event detection is a crucial tasks in wireless sensor networks. The importance of a fast response makes distributed strategies, where nodes exchange information just with their one-hop neighbors to reach local decisions, more adequate than schemes where all nodes send observations to a central entity. Distributed detectors are usually based on average consensus, where all nodes iteratively communicate to asymptotically agree on a final result. In a realistic scenario, communications are subject to random failures, which impacts the performance of the consensus. We propose an alternative detector, which adapts to the statistical properties of the consensus and compensate deviations from the average. Simulation results show that this adaptive detector improves the performance and approximates to the one of the optimal detector.

The estimation of a parameter corrupted by noise is a common tasks in wireless sensor networks, where the deployed nodes cooperate in order to improve their own inaccurate observations. This cooperation usually involves successive data exchanges and local information updates until a global consensus value is reached. The quality of the final estimator depends on the amount of collected observations, hence the number of active nodes. Moreover, the inherent iterative nature of the consensus process involves a certain energy consumption. Since the devices composing the network are usually battery powered, nodes becoming inactive due to battery depletion emerges as a serious problem. In this work, we aim to maximize the lifetime of the most energy demanding nodes, such that the quality of the global estimator is maintained above a certain threshold. To this end, we optimize the network topology considering both the duration of each consensus process, given by the algebraic connectivity of the network, and the power consumption per iteration of the most demanding nodes. Numerical results are provided to demonstrate the validity and efficiency of our methodology.

In this paper, we consider the problem of distributed spatial estimation for field reconstruction in wireless sensor networks. In order to estimate the field, a geostatistical technique called kriging is used. Centralized spatial estimation algorithms with a large number of sensors lead to significant computational cost and energy wastage. We present a novel distributed clustering algorithm for estimating spatial interference maps, which are essential for operations and management in future wireless networks. In this algorithm, clusters are adaptively formed with a small subset of sensors by minimizing the kriging variance. The semivariogram computation and kriging prediction are locally performed in each cluster in a distributed fashion. The complexity of the clustering algorithm is analyzed and its performance is evaluated by comparing it with centralized and other distributed approaches.

Wireless Sensor Networks have been identified as a promising technology to efficiently perform distributed monitoring, tracking and control tasks. In order to accomplish them, since fast decisions are generally required, high values of throughput must be obtained. Additionally, a high packet reception rate is important to avoid wasting energy due to unsuccessful transmissions. These communication requirements are more easily satisfied by exploiting the broadcast nature of the wireless medium, which allows several simultaneous receptions through a unique node transmission. We propose a Medium Access Control protocol that ensures, simultaneously, high values of throughput and a high packet reception rate in broadcast scenarios. To this extent, we first propose a utility function to measure the performance of the network in terms of these two parameters. Then, we design a medium access policy that, relying on local and adaptive decisions of the nodes, obtains greater values of this utility function than existing approaches based on fixed communication thresholds.

The so-called scale free property is a feature of many complex systems, including the Internet and World Wide Web, where most nodes have just a few links whereas the rest have a huge number of them. The traditional models conceived to reproduce the formation of these systems do not take into account the topological features of the growing network. Nevertheless, the resulting topology has a major influence on important properties of the network, such as synchronization and consensus time of nodes, network robustness, etc. In this work, we propose a new growth model that, starting from a random deployment of nodes, performs a wiring process using a metric that balances the degree of the nodes (preferential attachment), the euclidean distance (power consumption) and the algebraic connectivity (consensus time among others). Numerical results show that our proposal not only captures the properties of scale free networks, but also achieves a final topology that leads to more energy-efficient processes than traditional approaches.

Average consensus algorithms are an essential tool in wireless sensor networks for multiple estimation tasks, being the convergence time and the energy consumption of these algorithms critical for their usability. Most existing work in the related literature focuses on improving these two parameters, assuming generally unicast communications, which are neither realistic nor efficient given the wireless nature of these networks. Instead, broadcast communications allow a greater instantaneous exchange of information between the network nodes, accelerating the consensus and saving energy in communications. In this work, we propose two methods that optimize the network topology to simultaneously improve the total power consumption per iteration, the maximum power consumption per node and the convergence time in a broadcast scenario. The first method is applied to continuous systems, while the second one is more suitable for discrete systems. Numerical results are presented to show the validity and efficiency of the proposed methods.

We present the Dynamic Inhibition Areas Reaction-Diffusion (DIA-RD) algorithm, a distributed medium access control protocol that globally maximizes the spatial reusability (number of simultaneous transmissions per unit area) of wireless sensor networks. This algorithm is able, in consequence, to minimize the number of time slots needed to schedule the set of demanded links, making it very efficient to solve the Shortest Link Schedule problem. DIA-RD combines accurate interference management, provided by the use of dynamic inhibition areas based on the physical interference model; and global intelligent behavior, provided by the bio-inspired technique known as Reaction-Diffusion. This technique ensures global convergence to dense feasible transmission patterns (no active link inside the inhibition area of other active link) in a decentralized way. Experimental results show that our DIA-RD algorithm provides superior performance, in terms of spatial reusability, than the best state-of-the-art approaches, namely the DIA-LS, RD-MAC, GOW* and ML2S algorithms.

Consensus algorithms are simple processes that involve repeated communications between the nodes of the network until a consensus is reached with certain accuracy. In this setting, the lifetime of the network and the total required energy not only depend on the number of iterations needed to achieve consensus, but also on the power consumption per node and iteration. In this work, we propose a method to optimize the network topology in order to reduce the total energy required to achieve consensus while increasing the network lifetime. Our solution is based on an optimization technique that performs a tradeoff between these two concepts. Simulation results, under different types of networks, are presented to show clearly the efficiency and validity of our approach.

We present a novel distributed algorithm, called Dynamic Inhibition Area Link Scheduling (DIA-LS), which efficiently solves the Shortest Link Schedule (SLS) problem in wireless ad-hoc networks. The schedule length is reduced by maximizing the spatial reusability, which is the number of simultaneous transmissions per unit area, obtaining a dense feasible transmission pattern at each time slot. Most algorithms in the literature assume binary or protocol interference models and are based on uniformly partitioning the network deployment area. It leads to inaccurate interference management, making algorithms behave in an overly conservative way. In contrast, the proposed DIA-LS algorithm is based on the formation of individual inhibition areas around every potential receiver node. These inhibition areas are generated according to the physical interference model, providing a more accurate interference management. We first show a constant O(1) approximation bound to the optimal link schedule and demonstrate that our DIA-LS algorithm outperforms the GOW* and the ML2S algorithms, present in the literature.

Carrier Sense Multiple Access protocols are the most widely used methods for collision avoidance in Wireless Sensor Networks (WSNs). These protocols are prone to suffer from the hidden and exposed terminal problems, which lead to inefficiency and unfairness in the communications. Both problems are particularly significant in applications with massive traffic requirements, commonly found in WSNs. The control procedures generally employed to alleviate these effects may lead to performance degradation in the presence of intensive communications. In this paper, we propose a CSMA protocol based on the physical interference model, which mitigates the effect of hidden and exposed terminal problems in a real testbed. Our protocol provides to each pair of transmitter-receiver nodes a different threshold, which determines the maximum tolerated noise for this transmission. No additional control method is used to avoid collisions. Finally, we measure the performance of our protocol by executing over it the average consensus algorithm, which determines the high traffic demand. The packet reception rate, the throughput and the convergence of the consensus algorithm are evaluated in a real testbed.

An essential process in a Wireless Sensor Network is the noise mitigation of the measured data, by exploiting their spatial correlation. A widely used technique to achieve this reduction is to project the measured data into a proper subspace. We present a low complexity and distributed algorithm to perform this projection. Unlike other algorithms existing in the literature, which require the number of connections at every node to be larger than the dimension of the involved subspace, our algorithm does not require such dense network topologies for its applicability, making it suitable for a larger number of scenarios. Our proposed algorithm is based on the execution of several consensus processes, and therefore the mixing weights that drive the iterative process can be much more easily computed by using information local to each particular node. These two main advantages makes our approach more suitable for large networks composed by simple and power limited nodes. Simulations results are presented to show that our algorithm performs the projection faster and, in several scenarios, consuming less energy than other existing works in the related literature.

In this paper, we consider a sensing-based spectrum sharing scenario in cognitive radio networks where the overall objective is to maximize the sum-rate of each cognitive radio user by optimizing jointly both the detection operation based on sensing and the power allocation, taking into account the influence of the sensing accuracy and the interference limitation to the primary users. The resulting optimization problem for each cognitive user is non-convex, thus leading to a non-convex game, which presents a new challenge when analyzing the equilibria of this game where each cognitive user represents a player. In order to deal with the non-convexity of the game, we use a new relaxed equilibria concept, namely, quasi-Nash equilibrium (QNE). A QNE is a solution of a variational inequality obtained under the first-order optimality conditions of the player's problems, while retaining the convex constraints in the variational inequality problem. In this work, we state the sufficient conditions for the existence of the QNE for the proposed game. Specifically, under the so-called linear independent constraint qualification, we prove that the achieved QNE coincides with the NE. Moreover, a distributed primal-dual interior point optimization algorithm that converges to a QNE of the proposed game is provided in the paper, which is shown from the simulations to yield a considerable performance improvement with respect to an alternating direction optimization algorithm and a deterministic game.

An extended analog joint source-channel coding (JSCC) multiple description (MD) scheme is introduced. This new scheme extends a previously presented analog JSCC-MD scheme in order to work at different bandwidth ratios. This scheme is suitable for transmissions through parallel AWGN on-off channels and parallel slow-fading channels. The strengths of the proposed scheme in comparison with other coding alternatives are its coding/decoding simplicity and low delay, and its optimality in terms of distortion exponent in the fading parallel channels.

The average consensus algorithm is a well known distributed process in which the nodes iteratively communicate with the nodes within their communication range in order to obtain an estimation of the global average. These repeated communications, when performed in a uniformly randomly deployed network, such as a Wireless Sensor Network, lead to several nodes consuming much more power than others, thus reducing the lifetime of the whole network. This paper proposes a fully distributed method that allows the network nodes to suitably decide which subset of communications provides the best performance during the consensus process in terms of convergence time and power efficiency. Our method simultaneously improves both the convergence of the consensus algorithm and the lifetime of the whole network. Moreover, as a benchmark, we propose a convex optimization problem whose results can be compared with those obtained by our distributed approach. Simulation results are presented to show the efficiency of our proposal, comparing our two methods with existing approaches in the related literature.

In this paper, we develop a new power-efficient algorithm for Wireless Sensor Networks (WSN) in order to obtain, in a distributed manner, the Projection of an observed sampled spatial field on a subspace of lower dimension. This is an important problem that is motivated in various applications where there are well defined subspaces of interest (e.g. spectral maps in cognitive radios). As opposed to traditional Gossip Algorithms used for subspace projection assuming separation of channel coding and computation, our algorithm combines Computational Coding and a modification of existing Gossip Algorithms, achieving important savings in convergence time and yielding an exponential decrease in energy consumption as the size of the network increases.

In this paper, we develop a novel strategy to compute the transition matrix for the projection problem in a distributed fashion through gossiping in Wireless Sensor Networks. So far, the transition matrix had to be computed off-line by a third party and then provided to the network. The Subspace Projection Problem is useful in various application scenarios (e.g. spectral spatial maps in cognitive radios) and consists of projecting the observed sampled spatial field into a subspace of interest with lower dimension. Although the actual exact computation of the optimal transition matrix is not feasible in a distributed way, we develop an algorithm that is based on well known results from linear algebra and a distributed genetic algorithm in order to compute an approximation of the optimal matrix to a desired precision.

This paper considers the problem of power-efficient distributed estimation of vector parameters related to localized phenomena so that both the subset of sensor selection and the routing structure in a wireless sensor network are optimized jointly in order to obtain the best possible estimation performance at a given querying node, for a given total power budget. We first formulate our problem as an optimization problem and show that it is NP-Hard. Then, we design two algorithms: a fixed-tree relaxation-based and a novel and very efficient local distributed optimization to optimize jointly the sensor selection and the routing structure. We also provide a lower bound for our optimization problem and show that our local distributed optimization algorithm provides a performance that is close to this bound. Although there is no guarantee that the gap between this lower bound and the optimal solution of the main problem is always small, our numerical experiments support that this gap is actually very small in many cases. An important result from our work is that because of the interplay between the communication cost over the links and the gains in estimation accuracy obtained by choosing certain sensors, the traditional shortest-path-tree routing structure, widely used in practice, is no longer optimal, that is, our routing structures provide a better trade-off between the overall power efficiency and the final estimation accuracy obtained at the querying node. Comparing to more conventional sensor selection and fixed routing algorithms, our proposed joint sensor selection and routing algorithms yields a significant amount of energy saving.

In this paper, we consider the problem of power-efficient distributed estimation of a localized event in the large-scale Wireless Sensor Networks (WSNs). In order to increase the power efficiency in these networks, we develop a joint optimization problem that involves both selecting a subset of active sensors and the routing structure so that the quality of estimation at a given querying node is the best possible subject to a total imposed communication cost. We first formulate our problem as an optimization problem and show that it is NP-Hard. Then, we design two algorithms: a fixed-tree relaxation-based and a novel and very efficient iterative distributed to optimize jointly the sensor selection and the routing structure. We also provide a lower bound for our optimization problem and show that our iterative distributed algorithm provides a performance that is close to this bound. Although there is no guarantee that the gap between this lower bound and the optimal solution of the main problem is always small, our numerical experiments support that this gap is actually very small in many cases. An important result from our work is the fact that because of the interplay between communication cost and gain in estimation when fusing measurements from different sensors, the traditional Shortest Path Tree (SPT) routing structure, widely used in practice, is no longer optimal, that is, our routing structures provide a better trade-off between the overall communication cost and estimation accuracy. Comparing to more conventional sensor selection and fixed routing algorithms, our proposed joint sensor selection and routing algorithms yield a significant amount of energy saving.

In this paper, we tackle the problem of spatial interpolation for distributed estimation in Wireless Sensor Networks by using a geostatistical technique called kriging. We present a novel Distributed Iterative Kriging Algorithm (DIKA) which is composed of two main phases. First, the spatial dependence of the field is exploited by calculating semivariograms in an iterative way. Second, the kriging system of equations is solved by an initial set of nodes in a distributed manner, providing some initial interpolation weights to each node. In our algorithm, the estimation accuracy can be improved by iteratively adding new nodes and updating appropriately the weights, which leads to a reduction in the kriging variance. As a consequence, each cluster is constructed adaptively by the set of nodes that achieves the best estimation over the sub-area covered by them. We analyze the most influential parameters to implement this algorithm. Finally, we evaluate the performance of our algorithm and we also analyze its complexity.

In this paper, we consider a sensing-based spectrum sharing scenario and present an efficient decentralized algorithm to maximize the total throughput of the cognitive radio users by optimizing jointly both the detection operation and the power allocation, taking into account the influence of the sensing accuracy. This optimization problem can be formulated as a distributed non-cooperative power allocation game, which can be solved by using an alternating direction optimization method. The transmit power budget of the cognitive radio users and the constraint related to the rate-loss of the primary user due to the interference are considered in the scheme. Finally, we use variational inequality theory in order to find the existence and uniqueness of the Nash equilibrium for our proposed distributed non-cooperative game.

Given a spectrum-sensing network, a set of active nodes jointly aggregate sensed data at a preset frequency-band and simultaneously route this information to an arbitrarily chosen querying node through a power-constrained multi-hop path. Locally, each sensor node is assumed to be an energy-based detector. This work focuses on deriving algorithms that jointly optimize sensor selection and cooperative detection from which a power-efficient route to the querying node can be established, and then, a tree routing structure spanning the chosen nodes is constructed under a power budget constraint. Sensor information is sequentially aggregated along this optimized routing structure up to the querying node. Each parent node combines the information coming from each of its child nodes using either log-likelihood ratios or optimal linear weights. This is done with the goal of maximizing, at the querying node, the overall probability of detection (PD) for a given probability of false alarm (PFA) and a given total power budget spent by the sensor network for routing the sensor information. We propose two algorithms: (1) greedy and (2) select-aggregate-forward that provide a trade-off between the detection quality and the power consumption. We provide experimental results that show the outperformance of our algorithms against traditionally proposed routing structures such as the shortest-path-tree.

Dynamic spectrum access with Cognitive Radio (CR) network is a promising approach to increase the efficiency of spectrum usage. To allow the optimization of resource allocation and transmission adaptation techniques, each CR terminal needs to acquire awareness of the state of the time-frequency-location varying radio spectrum. In this paper we present a Spectrum Cartography (SC) approach where CR terminals are supported by a fixed wireless sensor network (WSN) to estimate and update the Power Spectral Density (PSD) over the area of interest. The wireless sensors collaborate to estimate the spatial distribution of the received power at a given frequency using either a centralized or a distributed Kriging (DK) algorithm. We present an analysis of the semivariogram models used to estimate the spatial statistics of wireless PSD distributions. The performance of the centralized and DK algorithms are evaluated by simulating different realizations of the PSD and the results are compared with classical interpolating schemes varying the density of nodes in the area and the number of nodes used for local estimation.

In this paper, we consider the problem of power-efficient distributed estimation of a localized event in the large-scale Wireless Sensor Networks (WSNs). In order to increase the power efficiency in these networks, we develop a joint optimization problem that involves both selecting a subset of active sensors and the routing structure so that the quality of estimation at a given querying node is the best possible subject to a total imposed communication cost. We first formulate our problem as an optimization problem and show that it is NP-Hard. Then, we propose a local distributed optimization algorithm that is based on an Estimate-and-Forward (EF) strategy, which allows to perform sequentially this joint optimization in an efficient way. We also provide a lower bound for our optimization problem and show that our local distributed optimization algorithm provides a performance that is close to this bound. Although there is no guarantee that the gap between this lower bound and the optimal solution of the main problem is always small, our numerical experiments support that this gap is actually very small in many cases. An important result from our work is that because of the interplay between the communication cost over the links and the gains in estimation accuracy obtained by choosing certain sensors, the traditional Shortest Path Tree (SPT) routing structure, widely used in practice, is no longer optimal, that is, our routing structures provide a better trade-off between the overall power efficiency and the final estimation accuracy obtained at the querying node. Our experimental results show that our algorithms yield a significant energy saving.

We propose a low complexity analog joint source channel coding Multiple Description (MD) scheme for transmitting the symbols of a Gaussian source across a pair of independent AWGN channels. The outputs of these channels have each a separated receiver, whereas a third receiver has both outputs available. At the transmitter side, a pair of bandwidth-reduction analog mappings are used for joint source-channel coding. The presented scheme has the inherent advantage over digital MD schemes based on separation, that coding and decoding can be performed by using a single-letter (or symbol), a strategy that is very suitable for applications where latency originated by the digital compression and the error correcting coding can not be tolerated. Our scheme achieves a performance that is competitive as compared to the optimal region while having a very low complexity and delay.

Owing to the non-zero probability of the missed detection and false alarm of active primary transmission, a certain degree of performance degradation of the primary user (PU) from cognitive radio users (CRs) is unavoidable. In this paper, we consider OFDM-based communication systems and present efficient algorithms to maximize the total rate of the CR by optimizing jointly both the detection operation and the power allocation, taking into account the influence of the probabilities of missed detection and false alarm, namely, the sensing accuracy. The optimization problem can be formulated as a two-variable non-convex problem, which can be solved approximately by using an alternating direction optimization method. Our algorithm can operated basically in two regimes depending on our constraints that are involved, while keeping the performance degradation of the PU bounded properly. Simulation results demonstrate that the proposed solution can considerably improve system performance.

In this paper, we obtain approximations for the optimal Log-Likelihood Ratio (LLR) decision rule in cooperative detection when local energy detectors are assumed. Considering conditional independence, we also show under which bandwidth and sampling frequency regimes these approximations hold best. Furthermore, we present simulations where the performance of the approximated LLR decision rule is compared with other sub-optimal decision rules given in the literature such as the optimal linear weighting. The simulations show that the density functions of the approximations exhibit negligible error in comparison with the exact ones, when conditions on bandwidth and sampling frequencies are met. The approximations presented in this paper allow to perform efficiently the joint LLR decision rule for a set of nodes without requiring Monte-Carlo simulations.

We study the source coding problem in sensor networks deployed to monitor the evolution of spatio-temporal temperature distributions. The sensors sample the temperature field, quantize the samples and transmit the encoded samples through digital channels to some central unit, which computes an estimate of the original temperature field. Our analysis is based on the heat kernel's spectral properties, which are induced by the physics of heat diffusion. We determine rate distortion functions for various source coding schemes. In particular, we compare centralized coding, independent coding, Berger-Tung coding, and predictive quantization.

Efficient spectrum sensing ensures cognitive radio users opportunistically use the under-utilized frequency band without causing harmful interference to primary users. However, in practice, owing to the non-zero probability of the missed detection and false alarm of active primary transmission, a certain degree of performance degradation of the primary user is unavoidable. In this paper, we consider OFDM-based communication systems and present efficient algorithms to maximize the total throughput of the cognitive radio by optimizing jointly both the detection operation and the power allocation, taking into account the influence of the probabilities of missed detection and false alarm.The optimization problem can be formulated as a two-variable non-convex problem, which can be solved approximately by using an alternating direction optimization method. A novel criterion is introduced to ensure that the performance degradation of the primary user is bounded properly. First, we analyze the case of only one cognitive radio and then we generalize to the case of a two cognitive radio non-cooperative power allocation game, showing that a Nash equilibrium can be achieved in few iterations by using an iterative alternating direction optimization method. Simulation results demonstrate that the proposed solution can considerably improve system performance.

In this paper, we consider the problem of improving the convergence speed of an average consensus gossip algorithm by sparsifying a sufficiently dense network graph. Thus, instead of adding links, as usually proposed in the literature, or globally optimizing the mixing matrix of the gossip algorithm for a given network, which requires global knowledge at every node, we find a sparser network that has better spectral properties and faster convergence than the original denser one. This allows to reduce simultaneously both the convergence time and the communication cost involved in the execution of the gossip algorithm. We first show why it is possible to sparsify a network while increasing its convergence rate and also that there exists an optimal fraction of links to be removed. As a benchmark, we devise a centralized method that selects in an optimal way the set of links to be removed from the original network. Then, we propose a low complexity and scalable decentralized protocol requiring only local information at each node, which also generates a sparser network having a substantially better convergence rate. Simulation results are presented to verify and show clearly the efficiency of our approach.

This paper addresses the construction of a novel efficient rotation-invariant texture retrieval method that is based on the alignment in angle of signatures obtained via a steerable sub-Gaussian model. In our proposed scheme, we first construct a steerable multivariate sub-Gaussian model, where the fractional lower-order moments of a given image are associated with those of its rotated versions. The feature extraction step consists of estimating the so-called covariations between the orientation subbands of the corresponding steerable pyramid at the same or at adjacent decomposition levels and building an appropriate signature that can be rotated directly without the need of rotating the image and recalculating the signature. The similarity measurement between two images is performed using a matrix-based norm that includes a signature alignment in angle between the images being compared, achieving in this way the desired rotation-invariance property. Our experimental results show how this retrieval scheme achieves a lower average retrieval error, as compared to previously proposed methods having a similar computational complexity, while at the same time being competitive with the best currently known state-of-the-art retrieval system. In conclusion, our retrieval method provides the best compromise between complexity and average retrieval performance.

In our previous work [1], we proposed a construction of critically sampled perfect reconstruction transforms with directional vanishing moments (DVMs) imposed in the corresponding basis functions along different directions, called directionlets. Here, we combine the directionlets with the space-frequency quantization (SFQ) image compression method, originally based on the standard two-dimensional (2-D) wavelet transform (WT) and proposed in [2]. We show that our new compression method outperforms the standard SFQ as well as the state-of-the-art compression methods, like SPIHT and JPEG-2000, in terms of the quality of compressed images, especially in a low-rate compression regime. We also show that the order of computational complexity remains the same, as compared to the complexity of the standard SFQ algorithm.

The standard separable 2-D wavelet transform (WT) has recently achieved a great success in image processing because it provides a sparse representation of smooth images. However, it fails to efficiently capture 1-D discontinuities, like edges or contours. These features, being elongated and characterized by geometrical regularity along different directions, intersect and generate many large magnitude wavelet coefficients. Since contours are very important elements in the visual perception of images, to provide a good visual quality of compressed images, it is fundamental to preserve good reconstruction of these directional features. In our previous work, we proposed a construction of critically sampled perfect reconstruction transforms with directional vanishing moments imposed in the corresponding basis functions along different directions, called directionlets. In this paper, we show how to design and implement a novel efficient space-frequency quantization (SFQ) compression algorithm using directionlets. Our new compression method outperforms the standard SFQ in a rate-distortion sense, both in terms of mean-square error and visual quality, especially in the low-rate compression regime. We also show that our compression method, does not increase the order of computational complexity as compared to the standard SFQ algorithm.

The standard separable two-dimensional (2-D) wavelet transform (WT) has recently achieved a great success in image processing because it provides a sparse representation of smooth images. However, it fails to capture efficiently one-dimensional (1-D) discontinuities, like edges and contours, that are anisotropic and characterized by geometrical regularity along different directions. In our previous work, we proposed a construction of critically sampled perfect reconstruction anisotropic transform with directional vanishing moments (DVM) imposed in the corresponding basis functions, called directionlets. Here, we show that the computational complexity of our transform is comparable to the complexity of the standard 2-D WT and substantially lower than the complexity of other similar approaches. We also present a zerotree-based image compression algorithm using directionlets that strongly outperforms the corresponding method based on the standard wavelets at low bit rates.

This paper presents a novel rotation-invariant image retrieval scheme based on a transformation of the texture information via a steerable pyramid. First, we fit the distribution of the subband coefficients using a joint alpha-stable sub-Gaussian model to capture their non-Gaussian behavior. Then, we apply a normalization process in order to Gaussianize the coefficients. As a result, the feature extraction step consists of estimating the covariances between the normalized pyramid coefficients. The similarity between two distinct texture images is measured by minimizing a rotation-invariant version of the Kullback-Leibler Divergence between their corresponding multivariate Gaussian distributions, where the minimization is performed over a set of rotation angles.

In spite of the success of the standard wavelet transform (WT) in image processing in recent years, the efficiency of its representation is limited by the spatial isotropy of its basis functions built in the horizontal and vertical directions. One-dimensional (1-D) discontinuities in images (edges and contours) that are very important elements in visual perception, intersect too many wavelet basis functions and lead to a nonsparse representation. To efficiently capture these anisotropic geometrical structures characterized by many more than the horizontal and vertical directions, a more complex multidirectional (M-DIR) and anisotropic transform is required. We present a new lattice-based perfect reconstruction and critically sampled anisotropic M-DIR WT. The transform retains the separable filtering and subsampling and the simplicity of computations and filter design from the standard two-dimensional WT, unlike in the case of some other directional transform constructions (e.g., curvelets, contourlets, or edgelets). The corresponding anisotropic basis unctions (directionlets) have directional vanishing moments along any two directions with rational slopes. Furthermore, we show that this novel transform provides an efficient tool for nonlinear approximation of images, achieving the approximation power O(N(-1.55)), which, while slower than the optimal rate O(N(-2)), is much better than O(N(-1)) achieved with wavelets, but at similar complexity.

Sensor networks measuring correlated data are considered, where the task is to gather data from the network nodes to a sink. A specific scenario is addressed, where data at nodes are lossy coded with high-resolution, and the information measured by the nodes has to be reconstructed at the sink within both certain total and individual distortion bounds. The first problem considered is to find the optimal transmission structure and the rate-distortion allocations at the various spatially located nodes, such as to minimize the total power consumption cost of the network, by assuming fixed nodes positions. The optimal transmission structure is the shortest path tree and the problems of rate and distortion allocation separate in the high-resolution case, namely, first the distortion allocation is found as a function of the transmission structure, and second, for a given distortion allocation, the rate allocation is computed. The second problem addressed is the case when the node positions can be chosen, by finding the optimal node placement for two different targets of interest, namely total power minimization and network lifetime maximization. Finally, a node placement solution that provides a tradeoff between the two metrics is proposed.

We consider the joint optimization of sensor placement and transmission structure for data gathering, where a given number of nodes need to be placed in a field such that the sensed data can be reconstructed at a sink within specified distortion bounds while minimizing the energy consumed for communication. We assume that the nodes use either joint entropy coding based on explicit communication between sensor nodes, where coding is done when side information is available, or Slepian-Wolf coding where nodes have knowledge of network correlation statistics. We consider both maximum and average distortion bounds. We prove that this optimization is NP-complete since it involves an interplay between the spaces of possible transmission structures given radio reachability limitations, and feasible placements satisfying distortion bounds.We address this problem by first looking at the simplified problem of optimal placement in the one-dimensional case. An analytical solution is derived for the case when there is a simple aggregation scheme, and numerical results are provided for the cases when joint entropy encoding is used. We use the insight from our 1-D analysis to extend our results to the 2-D case and compare it to typical uniform random placement and shortest-path tree. Our algorithm for two-dimensional placement and transmission structure provides two to three fold reduction in total power consumption and between one to two orders of magnitude reduction in bottleneck power consumption. We perform an exhaustive performance analysis of our scheme under varying correlation models and model parameters and demonstrate that the performance improvement is typical over a range of data correlation models and parameters. We also study the impact of performing computationally-efficient data conditioning over a local scope rather than the entire network. Finally, we extend our explicit placement results to a randomized placement scheme and show that such a scheme can be effective when deployment does not permit exact node placement.

We consider large sensor networks where the cost of collecting data from the network nodes to the data gathering sink is critical. We propose several algorithms that use limited local communication and distributed signal processing to make communication more efficient in terms of transmission cost. We consider a model that uses distributed wavelet-based signal processing. We first propose an algorithm that performs processing at nodes as data is forwarded to the sink. Then, we analyze algorithms that perform network division into groups of adaptive size and for which signal processing is applied separately to each group. We show by numerical simulations that such multiresolution approaches result in significant improvements for data gathering in terms of total communication costs.

We consider data gathering by a network with a sink node and a tree communication structure, where the goal is to minimize the total transmission cost of transporting the information, collected by the nodes, to the sink node. This problem requires a joint optimization of the data representation at the nodes and of the transmission structure. First, we study the case when the measured data are correlated random variables, both in the lossless scenario with Slepian-Wolf coding, and in the high-resolution lossy scenario with optimal rate-distortion allocation. We show that the optimal transmission structure is the shortest path tree, and we find, in closed-form, the rate and distortion allocation. Second, we study the case when the measured data are deterministic piecewise constant signals, and data is described with adaptive level wavelet-based multiresolution representation. We show experimentally that, when computation is decentralized, there is an optimal network division into node groups of adaptive size. Finally, we also analyze the node positioning problem where, given a correlation structure and an available number of sensors, the goal is to place the nodes optimally in terms of minimizing the transmission cost; our results show that important gains can be obtained compared to a uniformly distributed sensor positioning.

This paper presents a novel rotation-invariant image retrieval scheme based on steerable pyramid transforms. First, we model the subband coefficients as sub-Gaussian random vectors to capture their non-Gaussian behavior. Then, we apply a normalization process in order to Gaussianize the coefficients. As a result, the feature extraction step consists of estimating the covariances between the normalized pyramid coefficients. The similarity of two distinct images is measured by minimizing the Kullback-Leibler divergence (KLD) between their corresponding multivariate Gaussian distributions, where the minimization is performed over a set of rotation angles. We provide analytical expressions for the minimum KLD and we demonstrate the effectiveness of our proposed method using a set of real texture images.

In spite of the success of the standard wavelet transform (WT) in image processing, the efficiency of its representation is limited by the spatial isotropy of its basis functions built in only horizontal and vertical directions. One-dimensional (1-D) discontinuities in images (edges and contours), which are very important elements in visual perception, intersect too many wavelet basis functions and reduce the sparsity of the representation. To capture efficiently these anisotropic geometrical structures, a more complex multi-directional (M-DIR) and anisotropic transform is required. We present a new lattice-based perfect reconstruction and critically sampled anisotropic M-DIR WT (with the corresponding basis functions called directionlets) that retains the separable filtering and simple filter design from the standard two-dimensional (2-D) WT and imposes directional vanishing moments (DVM). Further-more, we show that this novel transform has non-linear approximation efficiency competitive to the other previously proposed over-sampled transform constructions.

Sensor networks are usually dense networks where the network diversity can be exploited in order to overcome failures. In this paper, we study the use of multiple description techniques in the context of sensor networks where the cause of failures is due to the usual practical constraint of having finite buffers in the sensors, instead of the more traditional case of link failures considered in previous research. Although from a theoretical point of view we observe that the use of more descriptions provides usually better performance, we show experimentally that this is not the case in practice, when real constraints are introduced, such as finite buffers and the presence of header information, necessary for any real application. Our main result is that the optimal number of descriptions, in terms of average distortion, decreases as the fraction of header information increases for a given buffer size

The analysis and design of routing algorithms for finite buffer networks requires solving the associated queue network problem which is known to be hard. We propose alternative and more accurate approximation models to the usual Jackson's theorem that give more insight into the effect of routing algorithms on the queue size distributions. Using the proposed approximation models, we analyze and design routing algorithms that minimize overflow losses in grid networks with finite buffers and different communication patterns, namely uniform communication and data gathering. We show that the buffer size required to achieve the maximum possible rate decreases as the network size increases. Motivated by the insight gained in grid networks, we apply the same principles to the design of routing algorithms for random networks with finite buffers that minimize overflow losses. We show that this requires adequately combining shortest path tree routing and traveling salesman routing. Our results show that such specially designed routing algorithms increase the transmitted rate for a given loss probability up to almost three times, on average, with respect to the usual shortest path tree routing.

We consider a sensor network measuring correlated data, where the task is to gather all data from the network nodes to a sink. We consider the case where data at nodes is lossy coded with high-resolution, and the information measured by the nodes should be available at the sink within certain total and individual distortion bounds. First, we consider the problem of finding the optimal transmission structure and the rate-distortion allocations at the various spatially located nodes, such as to minimize the total power consumption cost of the network. We prove that the optimal transmission structure is the shortest path tree and that the problems of rate and distortion allocation separate in the high-resolution case, namely, we first find the distortion allocation as a function of the transmission structure, and then the rate allocation is computed. Then, we also study the case when the node positions can be chosen, by finding the optimal node placement when two different targets of interest are considered, namely total power minimization and network lifetime extension.

Consider a set of correlated sources located at the nodes of a network, and a set of sinks that are the destinations for some of the sources. The minimization of cost functions which are the product of a function of the rate and a function of the path weight is considered, for both the data-gathering scenario, which is relevant in sensor networks, and general traffic matrices, relevant for general networks. The minimization is achieved by jointly optimizing a) the transmission structure, which is shown to consist in general of a superposition of trees, and b) the rate allocation across the source nodes, which is done by Slepian-Wolf coding. The overall minimization can be achieved in two concatenated steps. First, the optimal transmission structure is found, which in general amounts to finding a Steiner tree, and second, the optimal rate allocation is obtained by solving an optimization problem with cost weights determined by the given optimal transmission structure, and with linear constraints given by the Slepian-Wolf rate region. For the case of data gathering, the optimal transmission structure is fully characterized and a closed-form solution for the optimal rate allocation is provided. For the general case of an arbitrary traffic matrix, the problem of finding the optimal transmission structure is NP-complete. For large networks, in some simplified scenarios, the total costs associated with Slepian-Wolf coding and explicit communication (conditional encoding based on explicitly communicated side information) are compared. Finally, the design of decentralized algorithms for the optimal rate allocation is analyzed.

We consider the rate-distortion problem for sensing the continuous space-time physical temperature in a circular ring on which a heat source is applied over space and time, and which is allowed to cool by radiation or convection. The heat source is modelled as a continuous space-time stochastic process which is bandlimited over space and time. The temperature field is the result of a certain continuous space-time convolution of the heat source with the Green's function corresponding to the heat equation, which is space and time invariant. The temperature field is sampled at uniform spatial locations by a set of sensors and it has to be reconstructed at a base station. The goal is to minimize the mean-square-error per second, for a given number of nats per second, assuming ideal communication channels between sensors and base station. We find a) the centralized R/sup c/(D) function of the temperature field, where the base station can optimally encode all the space-time samples jointly. Then, we obtain b) the R/sup s-i/(D) function, where each sensor, independently, encodes its samples optimally over time, and c) the R/sup st-i/(D) function, where each sensor is constrained to encode also independently over time. We also study two distributed prediction-based approaches: a) with perfect feedback from the base station, where temporal prediction is performed at the base station and each sensor performs differential encoding; and b) without feedback, where each sensor locally performs temporal prediction.

We consider the problem of A/D conversion for non-bandlimited signals that have a finite rate of innovation, in particular, the class of a continuous periodic stream of Diracs, characterized by a set of time positions and weights. Previous research has only considered the sampling of these signals, ignoring quantization which is necessary for any practical application (e.g. UWB, CDMA). In order to achieve accuracy under quantization, we introduce two types of oversampling, namely, oversampling in frequency and oversampling in time. High accuracy is achieved by enforcing the reconstruction to satisfy either three convex sets of constraints related to (1) sampling kernel, (2) quantization and (3) periodic streams of Diracs, which is then said to provide strong consistency, or only the first two, providing weak consistency. We propose three reconstruction algorithms, the first two achieving weak consistency and the third one achieving strong consistency. For these three algorithms, respectively, the experimental MSE performance for time positions decreases as O(1/R/sub t//sup 2/ R/sub f//sup 3/), and O(1/R/sub t//sup 2/ R/sub f//sup 4/), where R/sub t/ and R/sub f/ are the oversampling ratios in time and in frequency, respectively. It is also proved theoretically that our reconstruction algorithms satisfying weak consistency achieve an MSE performance of at least O(1/R/sub t//sup 2/ R/sub f//sup 3/).

We consider the problem of correlated data gathering by a network with a sink node and a tree communication structure, where the goal is to minimize the total transmission cost of transporting the information collected by the nodes, to the sink node. Two coding strategies are analyzed: a Slepian-Wolf model where optimal coding is complex and transmission optimization is simple, and a joint entropy coding model with explicit communication where coding is simple and transmission optimization is difficult. This problem requires a joint optimization of the rate allocation at the nodes and of the transmission structure. For the Slepian-Wolf setting, we derive a closed form solution and an efficient distributed approximation algorithm with a good performance. For the explicit communication case, we prove that building an optimal data gathering tree is NP-complete and we propose various distributed approximation algorithms.

We study network capacity limits and optimal routing algorithms for regular sensor networks, namely, square and torus grid sensor networks, in both, the static case (no node failures) and the dynamic case (node failures). For static networks, we derive upper bounds on the network capacity and then we characterize and provide optimal routing algorithms whose rate per node is equal to this upper bound, thus, obtaining the exact analytical expression for the network capacity. For dynamic networks, the unreliability of the network is modeled in two ways: a Markovian node failure and an energy based node failure. Depending on the probability of node failure that is present in the network, we propose to use a particular combination of two routing algorithms, the first one being optimal when there are no node failures at all and the second one being appropriate when the probability of node failure is high. The combination of these two routing algorithms defines a family of randomized routing algorithms, each of them being suitable for a given probability of node failure.

We consider the rate-distortion problem for sensing the continuous space-time physical temperature in a circular ring on which a heat source is applied over space and time, and which is also allowed to cool by radiation or convection to its surrounding medium. The heat source is modelled as a continuous space-time stochastic process which is bandlimited over space and time. The temperature field is the result of a circular convolution over space and a continuous-time causal filtering over time of the heat source with the Green's function corresponding to the heat equation, which is space and time invariant. The temperature field is sampled at uniform spatial locations by a set of sensors and it has to be reconstructed at a base station. The goal is to minimize the mean-square-error per second, for a given number of nats per second, assuming ideal communication channels between sensors and base station. We find a) the centralized Rc (D) function of the temperature field, where all the space-time samples can be observed and encoded jointly. Then, we obtain b) the Rs-i (D) function, where each sensor, independently, encodes its samples optimally over time and c) the Rst-i (D) function, where each sensor is constrained to encode also independently over time. We also study two distributed prediction-based approaches: a) with perfect feedback from the base station, where temporal prediction is performed at the base station and each sensor performs differential encoding, and b) without feedback, where each sensor locally performs temporal prediction.

We consider the joint optimization of sensor placement and transmission structure for data gathering, where a given number of nodes need to be placed in a field such that the sensed data can be reconstructed at a sink within specified distortion bounds while minimizing the energy consumed for communication. We assume that the nodes use joint entropy coding based on explicit communication between sensor nodes, and consider both maximum and average distortion bounds. The optimization is complex since it involves an interplay between the spaces of possible transmission structures given radio reachability limitations, and feasible placements satisfying distortion bounds. We address this problem by first looking at the simplified problem of optimal placement in the one-dimensional case. An analytical solution is derived for the case when there is a simple aggregation scheme, and numerical results are provided for the cases when joint entropy encoding is used. We use the insight from our 1-D analysis to extend our results to the 2-D case, and show that our algorithm for two-dimensional placement and transmission structure provides significant power benefit over a commonly used combination of uniformly random placement and shortest path trees.

Consider a set of correlated sources located at the nodes of a network, and a sink to which the data from all the sources have to arrive. We address the minimization of a separable joint communication cost function given by the product [rate] o [edge weight]. We present two possible approaches for rate allocation, namely Slepian-Wolf coding, and coding by explicit communication, and compare asymptotically (large networks) the associated total costs by finding their corresponding scaling laws and analyzing the ratio between them. We also provide the specific conditions on the correlation structure which determine the different cases of asymptotic behaviors.

Recent results in sampling theory [M. Vetterli et al., (2002)] showed that perfect reconstruction of nonbandlimited signals with finite rate of innovation can be achieved performing uniform sampling at or above the rate of innovation. We study analog-to-digital (A/D) conversion of these signals, introducing two types of oversampling and consistent reconstruction.

In this paper, we propose a new rotation-invariant image retrieval system based on steerable pyramids and the concept of angular alignment across scales. First, we define energy-based texture features which are steerable under rotation, i.e., such that features corresponding to the rotated version of an image can be easily obtained from the features of the original (non-rotated) image. We also propose an approach to measure similarity between images that is robust to rotation; images are compared after being aligned in angle. The retrieval process is performed by means of a decision tree classifier where the angular alignment is performed at each node in the tree. To demonstrate the effectiveness of our system we consider a distributed image classification system, where the feature encoder and the classifier are physically apart and thus features are compressed before being transmitted. Our results of retrieval performance versus rate show a clear gain with respect to a wavelet transform (as an example, for the same rate, the retrieval precision is increased from 40% to 65%).

The application of the wavelet transform in image processing is most frequently based on a separable construction. While simple, such an approach is not capable of capturing properly all 2D properties in images. In this paper, a new truly separable multidirectional transform is proposed with a subsampling method based on lattice theory. Applications are possible in many areas of image processing. Some promising improvements are achieved in nonlinear approximation and denoising of images.

We study construction of structured regular quantizers for overcomplete expansions in /spl Ropf//sup N/. Our goal is to design structured quantizers which allow simple reconstruction algorithms with low complexity and which have good performance in terms of accuracy. Most related work to date in quantized redundant expansions has assumed that the same uniform scalar quantizer was used on all the expansion coefficients. Several approaches have been proposed to improve the reconstruction accuracy, with some of these methods having significant complexity. Instead, we consider the joint design of the overcomplete expansion and the scalar quantizers (allowing different step sizes) in such a way as to produce an equivalent vector quantizer (EVQ) with periodic structure. The construction of a periodic quantizer is based on lattices in /spl Ropf//sup N/ and the concept of geometrically scaled- similar sublattices. The periodicity makes it possible to achieve good accuracy using simple reconstruction algorithms (e.g., linear reconstruction or a small lookup table).

We present a study of separability of acoustic waveforms of speech at phoneme level. The analyzed data consist of 64ms segments of acoustic waveforms of individual phonemes from TIMIT data base, sampled at 16kHz. For each phoneme, by means of principal component analysis, we identify subspaces which contain a given proportion of the total energy of the available waveforms in time-domain, and also in spectral-magnitude domain. In order to assess separation between phonemes in the two domains, we perform pairwise classification of phonemes on clean data and on data immersed in white additive Gaussian noise up to 0dB signal to noise ratio. While the classification based on spectral magnitudes exhibits high sensitivity to additive noise, the time-domain classification proves to be very robust.

We study the construction of structured regular quantizers for overcomplete expansions in R/sup N/. Our goal is to design structured quantizers allowing simple reconstruction algorithms with low (memory and computational) complexity and having good performance in terms of accuracy. Most related work to date in quantized redundant expansions has assumed that uniform scalar quantization with the same stepsize was used on the redundant expansion and then has dealt with more complex methods to improve the reconstruction. Instead, we consider the design of scalar quantizers with different stepsizes for each coefficient of an overcomplete expansion in such a way as to produce an equivalent vector quantizer with periodic structure. The periodicity makes it possible to achieve good accuracy using simple reconstruction algorithms from the quantized coefficients of the overcomplete expansion.

The use of quantized redundant expansions is useful in applications where the cost of having oversampling in the representation is much lower than the use of a high-resolution quantization (e.g., oversampled A/D). Most work to date has assumed that simple uniform quantization was used on the redundant expansion and then has dealt with methods to improve the reconstruction. Instead, we consider the design of quantizers for overcomplete expansions. Our goal is to design quantizers such that simple reconstruction algorithms (e.g., linear) provide as good reconstructions as with more complex algorithms. We achieve this goal by designing quantizers with different step sizes for each coefficient of the expansion in such a way as to produce a quantizer with periodic structure.