Academic Publications

Cognitive radios with their intelligent mechanisms of avoiding interference and their ability to automatically discover and utilize unoccupied spectrum have frequently been proposed for pervasive wireless deployments.

In recent years, a variety of control algorithms managing such cognitive radios have been developed, following many different types of strategies and implementing the whole range from centralized control to distributed control principles. As future wireless deployments are expected to be very dense, the ability of a cognitive radio control algorithm to scale well to large network sizes becomes crucial.

In this paper, we review and discuss a wide variety of previously proposed algorithms for managing cognitive radio networks. For each of these algorithms, we theoretically analyze performance in pervasive, dense deployments and compare their ability to scale.

We present BoostMAC, a CSMA-based MAC layer protocol for wireless sensor networks that provides an adjustable interface to achieve ultra-low power operation. To reach low power operation, we adaptively set two radio parameters. First, BoostMAC implements a preamble sampling scheme that allows a mote to dynamically set the length of its duty cycles. Second, we apply machine learning such that a sender can predict its destination’s channel polling time and set each outgoing packet’s preamble length accordingly. Our two improvements require no extra communication overhead, and each mote in the network implements simple, local models. Energy conservation is one of the most fundamental problems in sensor networks, and by optimizing low level operation at the MAC layer, sensor network applications realize an increase in overall performance.

Static configuration at the MAC layer inhibits optimal energy conservation within habitat monitoring applications. We implemented BoostMAC in TOSSIM, and we compare its performance to B-MAC, a well-known low power MAC protocol with static behavior. We found that BoostMAC saves energy relative to B-MAC in bursty networks without affecting latency.

Because adaptability greatly improves the performance of a broadcast protocol, we identify three ways in which machine learning can be applied to broadcasting in a mobile ad hoc network (MANET). We chose broadcasting because it functions as a foundation of MANET communication. Unicast, multicast, and geocast protocols utilize broadcasting as a building block, providing important control and route establishment functionality. Therefore, any improvements to the process of broadcasting can be immediately realized by higher-level MANET functionality and applications. While efficient broadcast protocols have been proposed, no single broadcasting protocol works well in all possible MANET conditions. Furthermore, protocols tend to fail catastrophically in severe network environments.

Our three classes of adaptive protocols are Pure Machine Learning, Intra-Protocol Learning, and Inter-Protocol Learning. In the pure machine learning approach, we exhibit a new approach to the design of a broadcast protocol: the decision of whether to rebroadcast a packet is cast as a classification problem. Each mobile node (MN) builds a classifier and trains it on data collected from the network environment.

We introduce calculus-based formulas for the continuous Euler and homotopy operators. The 1D continuous homotopy operator automates integration by parts on the jet space. Its 3D generalization allows one to invert the total divergence operator. As a practical application, we show how the operators can be used to symbolically compute local conservation laws of nonlinear systems of partial diferential equations in multi-dimensions.

Analogous to the continuous case, we also present concrete formulas for the discrete Euler and homotopy operators. We use it to algorithmically invert the forward diference operator. We apply the discrete operator to compute fluxes of diferential-diference equations in (1+1) dimensions.

Our calculus-based approach allows for a straightforward implementation of the operators in major computer algebra system, such as Mathematica and Maple. The symbolic algorithms for integration and summation by parts are illustrated with elementary examples. The algorithms to compute conservation laws are illustrated with nonlinear PDEs and their discretizations arising in fluid dynamics and mathematical physics.

We propose and evaluate wireless sensor routing algorithms designed to extend the lifetime of a heterogeneous wireless sensor network. The network is heterogeneous in the sensors’ energy distribution and also in the amount of data each sensor must communicate. As a basis for comparison, we analyze the lifetime of a network using a simple, nearest-neighbor routing algorithm and an analytic solution to the optimal lifetime of networks meeting certain constraints. We compare the performance of all the routing algorithms in simulation.

The Network Simulator 2 (NS-2) is a popular and powerful simulation environment, and the number of NS-2 users has increased greatly in recent years. Although it was originally designed for wired networks, NS-2 has been extended to work with wireless networks, including wireless LANs, mobile ad hoc networks (MANETs), and sensor networks; however, the Network Animator (NAM) for NS-2 has not been extended for wireless visualization. In this paper, we discuss a new visualization and analysis tool for use with NS-2 wireless simulations. Visual analysis of a wireless environment is important for three areas of NS-2 based simulation research: (1) validating the accuracy of a mobility model’s output and/or the node topology files used to drive the simulation; (2) validation of new versions of the NS-2 simulator itself; and (3) analysis of the results of NS-2 simulations. Our iNSpect program handles all three of these areas quickly and accurately. We’ve made our iN-Spect program available for other researchers in order to improve the accuracy of their simulations.

We present a new broadcast protocol using Bayesian probabilistic classiiers, and we demonstrate its use in a mobile ad hoc network (MANET). Broadcasting functions as a foundation of MANET communication. Unicast, multicast, and geocast protocols utilize broadcasting as a building block, providing important control and route establishment functionality. Therefore, any improvements to the process of broadcasting can be immediately realized by MANET applications. While efficient broadcast protocols have been proposed, no single broadcasting protocol works well in all possible MANET conditions. Furthermore, every protocol fails catastrophically in severe network environments. We exhibit a new approach to the design of a broadcast protocol: the decision of whether to rebroadcast a packet is cast as a classiication problem. Each mobile node (MN) builds a classiier and trains it on data collected from the network environment. Given an input vector describing a broadcast packet and current network conditions, the classifier returns an output label of “Rebroadcast” or “Drop.” Because each MN adapts to changing network conditions, the result is a more robust communication protocol and more efficient use of network resources. We show that our protocol, compared to those tested, is the most eficient under a range of network conditions.

Simulation is the research tool of choice for a majority of the mobile ad hoc network (MANET) community. However, while the use of simulation has increased, the credibility of the simulation results has decreased. To determine the state of MANET simulation studies, we surveyed the 2000—2005 proceedings of the ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc). From our survey, we found significant shortfalls. We present the results of our survey in this paper. We then summarize common simulation study pitfalls found in our survey. Finally, we discuss the tools available that aid the development of rigorous simulation studies. We offer these results to the community with the hope of improving the credibility of MANET simulation-based studies.

We present a new application of the Image Analogies algorithm to be used for image segmentation. Our approach requires supervised training data, so we apply it to the domain of labeling human anatomical data. In the Visible Human Project, expert anatomists are overwhelmed with high-resolution images to analyze. We propose that the anatomist can work in conjunction with our approach, letting the machine segment 80% of the images, and requiring that the expert segment only every fifth image.

When designing a two-alternative classifier, one ordinarily aims to maximize the classifier’s ability to discriminate between members of the two classes. We describe a situation in a real-world business application of machine-learning prediction in which an additional constraint is placed on the nature of the solution: that the classifier achieve a specified correct acceptance or correct rejection rate (i.e., that it achieve a fixed accuracy on members of one class or the other). Our domain is predicting churn in the telecommunications industry. Churn refers to customers who switch from one service provider to another. We propose four algorithms for training a classifier subject to this domain constraint, and present results showing that each algorithm yields a reliable improvement in performance. Although the improvement is modest in magnitude, it is nonetheless impressive given the difficulty of the problem and the financial return that it achieves to the service provider.