We investigate the problem of minimizing the sum of the queue lengths of all the nodes in a wireless network with a tree topology. Nodes send their packets to the tree's root (sink). We consider a time-slotted system and a K-hop interference model. We characterize the existence of causal sample-path optimal scheduling policies in these networks, i.e., we wish to find a policy such that at each time-slot, for any traffic arrival pattern, the sum of the queue lengths of all the nodes is minimum among all policies. We provide an algorithm that takes any tree and K as inputs, and outputs whether a causal sample-path optimal policy exists for this tree under the K-hop interference model. We show that when this algorithm returns FALSE, there exists a traffic arrival pattern for which no causal sample-path optimal policy exists for the given tree structure. We further show that for certain tree structures, even noncausal sample-path optimal policies do not exist. We provide causal sample-path optimal policies for those tree structures for which the algorithm returns TRUE. Thus, we completely characterize the existence of such policies for all trees under the K-hop interference model. The nonexistence of sample-path optimal policies in a large class of tree structures implies that we need to study other (relatively) weaker metrics for this problem.

This paper introduces the vector sparse matrix transform (vector SMT), a new decorrelating transform suitable for performing distributed processing of high-dimensional signals in sensor networks. We assume that each sensor in the network encodes its measurements into vector outputs instead of scalar ones. The proposed transform decorrelates a sequence of pairs of vector outputs, until these vectors are decorrelated. In our experiments, we simulate distributed anomaly detection by a network of cameras, monitoring a spatial region. Each camera records an image of the monitored environment from its particular viewpoint and outputs a vector encoding the image. Our results, with both artificial and real data, show that the proposed vector SMT transform effectively decorrelates image measurements from the multiple cameras in the network while maintaining low overall communication energy consumption. Since it enables joint processing of the multiple vector outputs, our method provides significant improvements to anomaly detection accuracy when compared with the baseline case when the images are processed independently.

We investigate the problem of minimizing the sum of the queue lengths of all the nodes in a wireless network with a forest topology. Each packet is destined to one of the roots (sinks) of the forest. We consider a time-slotted system and a primary (or one-hop) interference model. We characterize the existence of causal sample-path optimal scheduling policies for this network topology under this interference model. A causal sample-path optimal scheduling policy is one for which at each time-slot, and for any sample-path traffic arrival pattern, the sum of the queue lengths of all the nodes in the network is minimum among all policies. We show that such policies exist in restricted forest structures, and that for any other forest structure, there exists a traffic arrival pattern for which no causal sample-path optimal policy can exist. Surprisingly, we show that many forest structures for which such policies exist can be scheduled by converting the structure into an equivalent linear network and scheduling the equivalent linear network according to the one-hop interference model. The nonexistence of such policies in many forest structures underscores the inherent limitation of using sample-path optimality as a performance metric and necessitates the need to study other (relatively) weaker metrics of delay performance.

Motivated by the need to judiciously allocate scarce sensing resources to attain the highest benefit for the applications that sensor networks serve, in this article we develop a flexible solutions methodology for maximizing the overall reward attained, subject to constraints on the resource demands under fairly general reward or demand functions. We map a broad class of related problems for data fusion in wireless sensor networks into an integer programming problem and provide an iterative Lagrangian relaxation technique to solve it. Each iteration step involves solving for a maximum-weight independent set of an appropriately constructed graph, which, in many cases, can be obtained in polynomial time. We apply our methodology to the problem of tracking targets moving over a period of time through a nonhomogeneous, energy-constrained sensor field. With rewards represented by the quality of information attained in tracking, we study its trade-offs and relationship with energy consumption and periodic measurement taking. We finally illustrate other applications of our framework in sensor networks.

We investigate the problem of minimizing the sum of the queue lengths of all the nodes in a wireless network with a tree topology. Nodes send their packets to the tree's root (sink). We consider a time-slotted system, and a K-hop interference model. We characterize the existence of causal sample-path optimal scheduling policies in these networks, i.e., we wish to find a policy such that at each time slot, for any traffic arrival pattern, the sum of the queue lengths of all the nodes is minimum among all policies. We provide an algorithm that takes any tree and K as inputs, and outputs whether a causal sample-path optimal policy exists for this tree under the K-hop interference model. We show that when this algorithm returns FALSE, there exists a traffic arrival pattern for which no causal sample-path optimal policy exists for the given tree structure. We further show that for certain tree structures, even non-causal sample-path optimal policies do not exist. We provide causal sample-path optimal policies for those tree structures for which the algorithm returns TRUE. Thus, we completely characterize the existence of such policies for all trees under the K-hop interference model. The non-existence of sample-path optimal policies in a large class of tree structures implies that we need to study other (relatively) weaker metrics for this problem.

In this paper, we develop a mathematical framework for studying the problem of maximizing the "information" received at the sink in a data gathering wireless sensor network. We explicitly account for unreliable links, energy constraints, and in-network computation. The network model is that of a sensor network arranged in the form of a tree topology, where the root corresponds to the sink node, and the rest of the network detects an event and transmits data to the sink over one or more hops. This problem of sending data from multiple sources to a common sink is often referred to as the convergecasting problem. We develop an integer optimization based framework for this problem, which allows for tackling link unreliability using general error-recovery schemes. Even though this framework has a non-linear objective function, and cannot be relaxed to a convex programming problem, we develop a low complexity, distributed solution. The solution involves finding a Maximum Weight Increasing Independent Set (MWIIS) in rectangle graphs over each hop of the network, and can be obtained in polynomial time. Further, we apply these techniques to a target tracking problem where we optimally select sensors to track a given target such that the information obtained is maximized subject to constraints on the per-node sensing and communication energy. We validate our algorithms through numerical evaluations, and illustrate the advantages of explicitly considering link unreliability in the optimization framework.

We investigate the problem of minimizing the sum of the queues of all the nodes in a wireless network with a tree topology. Nodes send their packets to the tree's root (sink). We consider a time-slotted system, and a primary interference model. We first consider the case where the root has only one child while the rest of the tree is arbitrary, and provide a causal sample-path delay optimal scheduling policy, i.e., at each time slot, for any traffic arrival pattern, the sum of the queues of all the nodes is minimum among all policies. We are able to fully characterize tree structures for which such policies exist. In particular, when the root has multiple children, there exists a causal sample-path delay optimal policy as long as only one child is not a leaf node. We also show that for any other tree structure there exists no causal sample-path delay optimal policy, thus underscoring the inherent limitation of using sample-path optimality as a performance metric and implying that other weaker metrics of delay performance should be investigated.

We study the problem of maximizing the aggregated information in a wireless sensor network. We consider a sensor network with a tree topology, where the root corresponds to the sink, and the rest of the network detects an event and transmits data to the sink. We formulate an integer optimization problem that maximizes the aggregated information that reaches the sink under deadline and interference constraints. This framework allows using a variety of error recovery schemes to tackle link unreliability. We show that the optimal solution involves solving a Job Interval Selection Problem (JISP) which is known to be MAX SNP-Hard. We construct a sub-optimal version, and develop a low complexity, distributed optimal solution to this version. We investigate tree structures for which this solution is optimal to the original problem. Our numerical results show that the sub-optimal solution outperforms existing JISP approximation algorithms even for general trees.