BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Anurag Kumar

Anurag Kumar appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Networking and Internet ArchitectureSoundeess.ASMachine LearningComputer Science and Game TheoryComputer VisionMultimediaSocial and Information NetworksSystems and ControlArtificial IntelligenceInformation Theorymath.ITMultiagent SystemsPerformancephysics.soc-phApplicationsComputation and LanguageData Structures and AlgorithmsDiscrete Mathematicseess.IVOther Computer Science

Catalog footprint

What is connected

58works
21topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

58 published item(s)

preprint2023arXiv

Rethinking complex-valued deep neural networks for monaural speech enhancement

Despite multiple efforts made towards adopting complex-valued deep neural networks (DNNs), it remains an open question whether complex-valued DNNs are generally more effective than real-valued DNNs for monaural speech enhancement. This work is devoted to presenting a critical assessment by systematically examining complex-valued DNNs against their real-valued counterparts. Specifically, we investigate complex-valued DNN atomic units, including linear layers, convolutional layers, long short-term memory (LSTM), and gated linear units. By comparing complex- and real-valued versions of fundamental building blocks in the recently developed gated convolutional recurrent network (GCRN), we show how different mechanisms for basic blocks affect the performance. We also find that the use of complex-valued operations hinders the model capacity when the model size is small. In addition, we examine two recent complex-valued DNNs, i.e. deep complex convolutional recurrent network (DCCRN) and deep complex U-Net (DCUNET). Evaluation results show that both DNNs produce identical performance to their real-valued counterparts while requiring much more computation. Based on these comprehensive comparisons, we conclude that complex-valued DNNs do not provide a performance gain over their real-valued counterparts for monaural speech enhancement, and thus are less desirable due to their higher computational costs.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Conformer-Based Self-Supervised Learning for Non-Speech Audio Tasks

Representation learning from unlabeled data has been of major interest in artificial intelligence research. While self-supervised speech representation learning has been popular in the speech research community, very few works have comprehensively analyzed audio representation learning for non-speech audio tasks. In this paper, we propose a self-supervised audio representation learning method and apply it to a variety of downstream non-speech audio tasks. We combine the well-known wav2vec 2.0 framework, which has shown success in self-supervised learning for speech tasks, with parameter-efficient conformer architectures. Our self-supervised pre-training can reduce the need for labeled data by two-thirds. On the AudioSet benchmark, we achieve a mean average precision (mAP) score of 0.415, which is a new state-of-the-art on this dataset through audio-only self-supervised learning. Our fine-tuned conformers also surpass or match the performance of previous systems pre-trained in a supervised way on several downstream tasks. We further discuss the important design considerations for both pre-training and fine-tuning.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Curriculum optimization for low-resource speech recognition

Modern end-to-end speech recognition models show astonishing results in transcribing audio signals into written text. However, conventional data feeding pipelines may be sub-optimal for low-resource speech recognition, which still remains a challenging task. We propose an automated curriculum learning approach to optimize the sequence of training examples based on both the progress of the model while training and prior knowledge about the difficulty of the training examples. We introduce a new difficulty measure called compression ratio that can be used as a scoring function for raw audio in various noise conditions. The proposed method improves speech recognition Word Error Rate performance by up to 33% relative over the baseline system

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Ego4D: Around the World in 3,000 Hours of Egocentric Video

We introduce Ego4D, a massive-scale egocentric video dataset and benchmark suite. It offers 3,670 hours of daily-life activity video spanning hundreds of scenarios (household, outdoor, workplace, leisure, etc.) captured by 931 unique camera wearers from 74 worldwide locations and 9 different countries. The approach to collection is designed to uphold rigorous privacy and ethics standards with consenting participants and robust de-identification procedures where relevant. Ego4D dramatically expands the volume of diverse egocentric video footage publicly available to the research community. Portions of the video are accompanied by audio, 3D meshes of the environment, eye gaze, stereo, and/or synchronized videos from multiple egocentric cameras at the same event. Furthermore, we present a host of new benchmark challenges centered around understanding the first-person visual experience in the past (querying an episodic memory), present (analyzing hand-object manipulation, audio-visual conversation, and social interactions), and future (forecasting activities). By publicly sharing this massive annotated dataset and benchmark suite, we aim to push the frontier of first-person perception. Project page: https://ego4d-data.org/

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Improving Speech Enhancement through Fine-Grained Speech Characteristics

While deep learning based speech enhancement systems have made rapid progress in improving the quality of speech signals, they can still produce outputs that contain artifacts and can sound unnatural. We propose a novel approach to speech enhancement aimed at improving perceptual quality and naturalness of enhanced signals by optimizing for key characteristics of speech. We first identify key acoustic parameters that have been found to correlate well with voice quality (e.g. jitter, shimmer, and spectral flux) and then propose objective functions which are aimed at reducing the difference between clean speech and enhanced speech with respect to these features. The full set of acoustic features is the extended Geneva Acoustic Parameter Set (eGeMAPS), which includes 25 different attributes associated with perception of speech. Given the non-differentiable nature of these feature computation, we first build differentiable estimators of the eGeMAPS and then use them to fine-tune existing speech enhancement systems. Our approach is generic and can be applied to any existing deep learning based enhancement systems to further improve the enhanced speech signals. Experimental results conducted on the Deep Noise Suppression (DNS) Challenge dataset shows that our approach can improve the state-of-the-art deep learning based enhancement systems.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Multichannel Speech Enhancement without Beamforming

Deep neural networks are often coupled with traditional spatial filters, such as MVDR beamformers for effectively exploiting spatial information. Even though single-stage end-to-end supervised models can obtain impressive enhancement, combining them with a traditional beamformer and a DNN-based post-filter in a multistage processing provides additional improvements. In this work, we propose a two-stage strategy for multi-channel speech enhancement that does not require a traditional beamformer for additional performance. First, we propose a novel attentive dense convolutional network (ADCN) for estimating real and imaginary parts of complex spectrogram. ADCN obtains state-of-the-art results among single-stage models. Next, we use ADCN with a recently proposed triple-path attentive recurrent network (TPARN) for estimating waveform samples. The proposed strategy uses two insights; first, using different approaches in two stages; and second, using a stronger model in the first stage. We illustrate the efficacy of our strategy by evaluating multiple models in a two-stage approach with and without a traditional beamformer.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

RemixIT: Continual self-training of speech enhancement models via bootstrapped remixing

We present RemixIT, a simple yet effective self-supervised method for training speech enhancement without the need of a single isolated in-domain speech nor a noise waveform. Our approach overcomes limitations of previous methods which make them dependent on clean in-domain target signals and thus, sensitive to any domain mismatch between train and test samples. RemixIT is based on a continuous self-training scheme in which a pre-trained teacher model on out-of-domain data infers estimated pseudo-target signals for in-domain mixtures. Then, by permuting the estimated clean and noise signals and remixing them together, we generate a new set of bootstrapped mixtures and corresponding pseudo-targets which are used to train the student network. Vice-versa, the teacher periodically refines its estimates using the updated parameters of the latest student models. Experimental results on multiple speech enhancement datasets and tasks not only show the superiority of our method over prior approaches but also showcase that RemixIT can be combined with any separation model as well as be applied towards any semi-supervised and unsupervised domain adaptation task. Our analysis, paired with empirical evidence, sheds light on the inside functioning of our self-training scheme wherein the student model keeps obtaining better performance while observing severely degraded pseudo-targets.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

SAQAM: Spatial Audio Quality Assessment Metric

Audio quality assessment is critical for assessing the perceptual realism of sounds. However, the time and expense of obtaining ''gold standard'' human judgments limit the availability of such data. For AR&VR, good perceived sound quality and localizability of sources are among the key elements to ensure complete immersion of the user. Our work introduces SAQAM which uses a multi-task learning framework to assess listening quality (LQ) and spatialization quality (SQ) between any given pair of binaural signals without using any subjective data. We model LQ by training on a simulated dataset of triplet human judgments, and SQ by utilizing activation-level distances from networks trained for direction of arrival (DOA) estimation. We show that SAQAM correlates well with human responses across four diverse datasets. Since it is a deep network, the metric is differentiable, making it suitable as a loss function for other tasks. For example, simply replacing an existing loss with our metric yields improvement in a speech-enhancement network.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Speech Quality Assessment through MOS using Non-Matching References

Human judgments obtained through Mean Opinion Scores (MOS) are the most reliable way to assess the quality of speech signals. However, several recent attempts to automatically estimate MOS using deep learning approaches lack robustness and generalization capabilities, limiting their use in real-world applications. In this work, we present a novel framework, NORESQA-MOS, for estimating the MOS of a speech signal. Unlike prior works, our approach uses non-matching references as a form of conditioning to ground the MOS estimation by neural networks. We show that NORESQA-MOS provides better generalization and more robust MOS estimation than previous state-of-the-art methods such as DNSMOS and NISQA, even though we use a smaller training set. Moreover, we also show that our generic framework can be combined with other learning methods such as self-supervised learning and can further supplement the benefits from these methods.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

The impact of removing head movements on audio-visual speech enhancement

This paper investigates the impact of head movements on audio-visual speech enhancement (AVSE). Although being a common conversational feature, head movements have been ignored by past and recent studies: they challenge today's learning-based methods as they often degrade the performance of models that are trained on clean, frontal, and steady face images. To alleviate this problem, we propose to use robust face frontalization (RFF) in combination with an AVSE method based on a variational auto-encoder (VAE) model. We briefly describe the basic ingredients of the proposed pipeline and we perform experiments with a recently released audio-visual dataset. In the light of these experiments, and based on three standard metrics, namely STOI, PESQ and SI-SDR, we conclude that RFF improves the performance of AVSE by a considerable margin.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Time-domain Ad-hoc Array Speech Enhancement Using a Triple-path Network

Deep neural networks (DNNs) are very effective for multichannel speech enhancement with fixed array geometries. However, it is not trivial to use DNNs for ad-hoc arrays with unknown order and placement of microphones. We propose a novel triple-path network for ad-hoc array processing in the time domain. The key idea in the network design is to divide the overall processing into spatial processing and temporal processing and use self-attention for spatial processing. Using self-attention for spatial processing makes the network invariant to the order and the number of microphones. The temporal processing is done independently for all channels using a recently proposed dual-path attentive recurrent network. The proposed network is a multiple-input multiple-output architecture that can simultaneously enhance signals at all microphones. Experimental results demonstrate the excellent performance of the proposed approach. Further, we present analysis to demonstrate the effectiveness of the proposed network in utilizing multichannel information even from microphones at far locations.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

TPARN: Triple-path Attentive Recurrent Network for Time-domain Multichannel Speech Enhancement

In this work, we propose a new model called triple-path attentive recurrent network (TPARN) for multichannel speech enhancement in the time domain. TPARN extends a single-channel dual-path network to a multichannel network by adding a third path along the spatial dimension. First, TPARN processes speech signals from all channels independently using a dual-path attentive recurrent network (ARN), which is a recurrent neural network (RNN) augmented with self-attention. Next, an ARN is introduced along the spatial dimension for spatial context aggregation. TPARN is designed as a multiple-input and multiple-output architecture to enhance all input channels simultaneously. Experimental results demonstrate the superiority of TPARN over existing state-of-the-art approaches.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

A bandit approach to curriculum generation for automatic speech recognition

The Automated Speech Recognition (ASR) task has been a challenging domain especially for low data scenarios with few audio examples. This is the main problem in training ASR systems on the data from low-resource or marginalized languages. In this paper we present an approach to mitigate the lack of training data by employing Automated Curriculum Learning in combination with an adversarial bandit approach inspired by Reinforcement learning. The goal of the approach is to optimize the training sequence of mini-batches ranked by the level of difficulty and compare the ASR performance metrics against the random training sequence and discrete curriculum. We test our approach on a truly low-resource language and show that the bandit framework has a good improvement over the baseline transfer-learning model.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Multi-Channel Speech Enhancement using Graph Neural Networks

Multi-channel speech enhancement aims to extract clean speech from a noisy mixture using signals captured from multiple microphones. Recently proposed methods tackle this problem by incorporating deep neural network models with spatial filtering techniques such as the minimum variance distortionless response (MVDR) beamformer. In this paper, we introduce a different research direction by viewing each audio channel as a node lying in a non-Euclidean space and, specifically, a graph. This formulation allows us to apply graph neural networks (GNN) to find spatial correlations among the different channels (nodes). We utilize graph convolution networks (GCN) by incorporating them in the embedding space of a U-Net architecture. We use LibriSpeech dataset and simulate room acoustics data to extensively experiment with our approach using different array types, and number of microphones. Results indicate the superiority of our approach when compared to prior state-of-the-art method.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

A Sequential Self Teaching Approach for Improving Generalization in Sound Event Recognition

An important problem in machine auditory perception is to recognize and detect sound events. In this paper, we propose a sequential self-teaching approach to learning sounds. Our main proposition is that it is harder to learn sounds in adverse situations such as from weakly labeled and/or noisy labeled data, and in these situations a single stage of learning is not sufficient. Our proposal is a sequential stage-wise learning process that improves generalization capabilities of a given modeling system. We justify this method via technical results and on Audioset, the largest sound events dataset, our sequential learning approach can lead to up to 9% improvement in performance. A comprehensive evaluation also shows that the method leads to improved transferability of knowledge from previously trained models, thereby leading to improved generalization capabilities on transfer learning tasks.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Large Scale Audiovisual Learning of Sounds with Weakly Labeled Data

Recognizing sounds is a key aspect of computational audio scene analysis and machine perception. In this paper, we advocate that sound recognition is inherently a multi-modal audiovisual task in that it is easier to differentiate sounds using both the audio and visual modalities as opposed to one or the other. We present an audiovisual fusion model that learns to recognize sounds from weakly labeled video recordings. The proposed fusion model utilizes an attention mechanism to dynamically combine the outputs of the individual audio and visual models. Experiments on the large scale sound events dataset, AudioSet, demonstrate the efficacy of the proposed model, which outperforms the single-modal models, and state-of-the-art fusion and multi-modal models. We achieve a mean Average Precision (mAP) of 46.16 on Audioset, outperforming prior state of the art by approximately +4.35 mAP (relative: 10.4%).

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

SAGRNN: Self-Attentive Gated RNN for Binaural Speaker Separation with Interaural Cue Preservation

Most existing deep learning based binaural speaker separation systems focus on producing a monaural estimate for each of the target speakers, and thus do not preserve the interaural cues, which are crucial for human listeners to perform sound localization and lateralization. In this study, we address talker-independent binaural speaker separation with interaural cues preserved in the estimated binaural signals. Specifically, we extend a newly-developed gated recurrent neural network for monaural separation by additionally incorporating self-attention mechanisms and dense connectivity. We develop an end-to-end multiple-input multiple-output system, which directly maps from the binaural waveform of the mixture to those of the speech signals. The experimental results show that our proposed approach achieves significantly better separation performance than a recent binaural separation approach. In addition, our approach effectively preserves the interaural cues, which improves the accuracy of sound localization.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Secost: Sequential co-supervision for large scale weakly labeled audio event detection

Weakly supervised learning algorithms are critical for scaling audio event detection to several hundreds of sound categories. Such learning models should not only disambiguate sound events efficiently with minimal class-specific annotation but also be robust to label noise, which is more apparent with weak labels instead of strong annotations. In this work, we propose a new framework for designing learning models with weak supervision by bridging ideas from sequential learning and knowledge distillation. We refer to the proposed methodology as SeCoST (pronounced Sequest) -- Sequential Co-supervision for training generations of Students. SeCoST incrementally builds a cascade of student-teacher pairs via a novel knowledge transfer method. Our evaluations on Audioset (the largest weakly labeled dataset available) show that SeCoST achieves a mean average precision of 0.383 while outperforming prior state of the art by a considerable margin.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Throughput Optimal Decentralized Scheduling with Single-bit State Feedback for a Class of Queueing Systems

Motivated by medium access control for resource-challenged wireless Internet of Things (IoT), we consider the problem of queue scheduling with reduced queue state information. In particular, we consider a time-slotted scheduling model with $N$ sensor nodes, with pair-wise dependence, such that Nodes $i$ and $i + 1,~0 < i < N$ cannot transmit together. We develop new throughput-optimal scheduling policies requiring only the empty-nonempty state of each queue that we term Queue Nonemptiness-Based (QNB) policies. We propose a Policy Splicing technique to combine scheduling policies for small networks in order to construct throughput-optimal policies for larger networks, some of which also aim for low delay. For $N = 3,$ there exists a sum-queue length optimal QNB scheduling policy. We show, however, that for $N > 4,$ there is no QNB policy that is sum-queue length optimal over all arrival rate vectors in the capacity region. We then extend our results to a more general class of interference constraints that we call cluster-of-cliques (CoC) conflict graphs. We consider two types of CoC networks, namely, Linear Arrays of Cliques (LAoC) and Star-of-Cliques (SoC) networks. We develop QNB policies for these classes of networks, study their stability and delay properties, and propose and analyze techniques to reduce the amount of state information to be disseminated across the network for scheduling. In the SoC setting, we propose a throughput-optimal policy that only uses information that nodes in the network can glean by sensing activity (or lack thereof) on the channel. Our throughput-optimality results rely on two new arguments: a Lyapunov drift lemma specially adapted to policies that are queue length-agnostic, and a priority queueing analysis for showing strong stability.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

ADWISERv2: A Plug-and-play Controller for Managing TCP Transfers in IEEE~802.11 Infrastructure WLANs with Multiple Access Points

In this paper, we present a generic plug-and-play controller that ensures fair and efficient operation of IEEE~802.11 infrastructure wireless local area networks with multiple co-channel access points, without any change to hardware/firmware of the network devices. Our controller addresses performance issues of TCP transfers in multi-AP WLANs, by overlaying a coarse time-slicing scheduler on top of a cascaded fair queuing scheduler. The time slices and queue weights, used in our controller, are obtained from the solution of a constrained utility optimization formulation. A study of the impact of coarse time-slicing on TCP is also presented in this paper. We present an improved algorithm for adaptation of the service rate of the fair queuing scheduler and provide experimental results to illustrate its efficacy. We also present the changes that need to be incorporated to the proposed approach, to handle short-lived and interactive TCP flows. Finally, we report the results of experiments performed on a real testbed, demonstrating the efficacy of our controller.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Analytical Modeling of IEEE 802.11 Type CSMA/CA Networks with Short Term Unfairness

We consider single-hop topologies with saturated transmitting nodes, using IEEE~802.11 DCF for medium access. However, unlike the conventional WiFi, we study systems where one or more of the protocol parameters are different from the standard, and/or where the propagation delays among the nodes are not negligible compared to the duration of a backoff slot. We observe that for several classes of protocol parameters, and for large propagation delays, such systems exhibit a certain performance anomaly known as short term unfairness, which may lead to severe performance degradation. The standard fixed point analysis technique (and its simple extensions) do not predict the system behavior well in such cases; a mean field model based asymptotic approach also is not adequate to predict the performance for networks of practical sizes in such cases. We provide a detailed stochastic model that accurately captures the system evolution. Since an exact analysis of this model is computationally intractable, we develop a novel approximate, but accurate, analysis that uses a parsimonious state representation for computational tractability. Apart from providing insights into the system behavior, the analytical method is also able to quantify the extent of short term unfairness in the system, and can therefore be used for tuning the protocol parameters to achieve desired throughput and fairness objectives.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Audio Content based Geotagging in Multimedia

In this paper we propose methods to extract geographically relevant information in a multimedia recording using its audio. Our method primarily is based on the fact that urban acoustic environment consists of a variety of sounds. Hence, location information can be inferred from the composition of sound events/classes present in the audio. More specifically, we adopt matrix factorization techniques to obtain semantic content of recording in terms of different sound classes. These semantic information are then combined to identify the location of recording.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Audio Event Detection using Weakly Labeled Data

Acoustic event detection is essential for content analysis and description of multimedia recordings. The majority of current literature on the topic learns the detectors through fully-supervised techniques employing strongly labeled data. However, the labels available for majority of multimedia data are generally weak and do not provide sufficient detail for such methods to be employed. In this paper we propose a framework for learning acoustic event detectors using only weakly labeled data. We first show that audio event detection using weak labels can be formulated as an Multiple Instance Learning problem. We then suggest two frameworks for solving multiple-instance learning, one based on support vector machines, and the other on neural networks. The proposed methods can help in removing the time consuming and expensive process of manually annotating data to facilitate fully supervised learning. Moreover, it can not only detect events in a recording but can also provide temporal locations of events in the recording. This helps in obtaining a complete description of the recording and is notable since temporal information was never known in the first place in weakly labeled data.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Experiments on the DCASE Challenge 2016: Acoustic Scene Classification and Sound Event Detection in Real Life Recording

In this paper we present our work on Task 1 Acoustic Scene Classi- fication and Task 3 Sound Event Detection in Real Life Recordings. Among our experiments we have low-level and high-level features, classifier optimization and other heuristics specific to each task. Our performance for both tasks improved the baseline from DCASE: for Task 1 we achieved an overall accuracy of 78.9% compared to the baseline of 72.6% and for Task 3 we achieved a Segment-Based Error Rate of 0.76 compared to the baseline of 0.91.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Features and Kernels for Audio Event Recognition

One of the most important problems in audio event detection research is absence of benchmark results for comparison with any proposed method. Different works consider different sets of events and datasets which makes it difficult to comprehensively analyze any novel method with an existing one. In this paper we propose to establish results for audio event recognition on two recent publicly-available datasets. In particular we use Gaussian Mixture model based feature representation and combine them with linear as well as non-linear kernel Support Vector Machines.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Speech Enhancement In Multiple-Noise Conditions using Deep Neural Networks

In this paper we consider the problem of speech enhancement in real-world like conditions where multiple noises can simultaneously corrupt speech. Most of the current literature on speech enhancement focus primarily on presence of single noise in corrupted speech which is far from real-world environments. Specifically, we deal with improving speech quality in office environment where multiple stationary as well as non-stationary noises can be simultaneously present in speech. We propose several strategies based on Deep Neural Networks (DNN) for speech enhancement in these scenarios. We also investigate a DNN training strategy based on psychoacoustic models from speech coding for enhancement of noisy speech

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

An Approximate Inner Bound to the QoS Aware Throughput Region of a Tree Network under IEEE 802.15.4 CSMA/CA and Application to Wireless Sensor Network Design

We consider a tree network spanning a set of source nodes that generate measurement packets, a set of additional relay nodes that only forward packets from the sources, and a data sink. We assume that the paths from the sources to the sink have bounded hop count. We assume that the nodes use the IEEE 802.15.4 CSMA/CA for medium access control, and that there are no hidden terminals. In this setting, starting with a set of simple fixed point equations, we derive sufficient conditions for the tree network to approximately satisfy certain given QoS targets such as end-to-end delivery probability and delay under a given rate of generation of measurement packets at the sources (arrival rates vector). The structures of our sufficient conditions provide insight on the dependence of the network performance on the arrival rate vector, and the topological properties of the network. Furthermore, for the special case of equal arrival rates, default backoff parameters, and for a range of values of target QoS, we show that among all path-length-bounded trees (spanning a given set of sources and BS) that meet the sufficient conditions, a shortest path tree achieves the maximum throughput.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Competitive Selection of Ephemeral Relays in Wireless Networks

We consider a setting in which two nodes (referred to as forwarders) compete to choose a relay node from a set of relays, as they ephemerally become available (e.g., wake up from a sleep state). Each relay, when it arrives, offers a (possibly different) "reward" to each forwarder. Each forwarder's objective is to minimize a combination of the delay incurred in choosing a relay and the reward offered by the chosen relay. As an example, we develop the reward structure for the specific problem of geographical forwarding over a network of sleep-wake cycling relays. We study two variants of the generic relay selection problem, namely, the completely observable (CO) case where, when a relay arrives, both forwarders get to observe both rewards, and the partially observable (PO) case where each forwarder can only observe its own reward. Formulating the problem as a two person stochastic game, we characterize solution in terms of Nash Equilibrium Policy Pairs (NEPPs). For the CO case we provide a general structure of the NEPPs. For the PO case we prove that there exists an NEPP within the class of threshold policy pairs. We then consider the particular application of geographical forwarding of packets in a shared network of sleep-wake cycling wireless relays. For this problem, for a particular reward structure, using realistic parameter values corresponding to TelosB wireless mote, we numerically compare the performance (in terms of cost to both forwarders) of the various NEPPs and draw the following key insight: even for moderate separation between the two forwarders, the performance of the various NEPPs is close to the performance of a simple strategy where each forwarder behaves as if the other forwarder is not present. We also conduct simulation experiments to study the end-to-end performance of the simple forwarding policy.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Unsupervised Fusion Weight Learning in Multiple Classifier Systems

In this paper we present an unsupervised method to learn the weights with which the scores of multiple classifiers must be combined in classifier fusion settings. We also introduce a novel metric for ranking instances based on an index which depends upon the rank of weighted scores of test points among the weighted scores of training points. We show that the optimized index can be used for computing measures such as average precision. Unlike most classifier fusion methods where a single weight is learned to weigh all examples our method learns instance-specific weights. The problem is formulated as learning the weight which maximizes a clarity index; subsequently the index itself and the learned weights both are used separately to rank all the test points. Our method gives an unsupervised method of optimizing performance on actual test data, unlike the well known stacking-based methods where optimization is done over a labeled training set. Moreover, we show that our method is tolerant to noisy classifiers and can be used for selecting N-best classifiers.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

A Fast and Accurate Performance Analysis of Beaconless IEEE 802.15.4 Multi-Hop Networks

We develop an approximate analytical technique for evaluating the performance of multi-hop networks based on beaconless IEEE 802.15.4, a popular standard for wireless sensor networks. The network comprises sensor nodes, which generate measurement packets, relay nodes which only forward packets, and a data sink (base station). We consider a detailed stochastic process at each node, and analyse this process taking into account the interaction with neighboring nodes via certain time averaged unknown variables (e.g., channel sensing rates, collision probabilities, etc.). By coupling the analyses at various nodes, we obtain fixed point equations that can be solved numerically to obtain the unknown variables, thereby yielding approximations of time average performance measures, such as packet discard probabilities and average queueing delays. The model incorporates packet generation at the sensor nodes and queues at the sensor nodes and relay nodes. We demonstrate the accuracy of our model by an extensive comparison with simulations. As an additional assessment of the accuracy of the model, we utilize it in an algorithm for sensor network design with quality-of-service (QoS) objectives, and show that designs obtained using our model actually satisfy the QoS constraints (as validated by simulating the networks), and the predictions are accurate to well within 10% as compared to the simulation results.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Impromptu Deployment of Wireless Relay Networks: Experiences Along a Forest Trail

We are motivated by the problem of impromptu or as- you-go deployment of wireless sensor networks. As an application example, a person, starting from a sink node, walks along a forest trail, makes link quality measurements (with the previously placed nodes) at equally spaced locations, and deploys relays at some of these locations, so as to connect a sensor placed at some a priori unknown point on the trail with the sink node. In this paper, we report our experimental experiences with some as-you-go deployment algorithms. Two algorithms are based on Markov decision process (MDP) formulations; these require a radio propagation model. We also study purely measurement based strategies: one heuristic that is motivated by our MDP formulations, one asymptotically optimal learning algorithm, and one inspired by a popular heuristic. We extract a statistical model of the propagation along a forest trail from raw measurement data, implement the algorithms experimentally in the forest, and compare them. The results provide useful insights regarding the choice of the deployment algorithm and its parameters, and also demonstrate the necessity of a proper theoretical formulation.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Influence Spread in Social Networks: A Study via a Fluid Limit of the Linear Threshold Model

Threshold based models have been widely used in characterizing collective behavior on social networks. An individual's threshold indicates the minimum level of influence that must be exerted, by other members of the population engaged in some activity, before the individual will join the activity. In this work, we begin with a homogeneous version of the Linear Threshold model proposed by Kempe et al. in the context of viral marketing, and generalize this model to arbitrary threshold distributions. We show that the evolution can be modeled as a discrete time Markov chain, and, by using a certain scaling, we obtain a fluid limit that provides an ordinary differential equation model (o.d.e.). We find that the threshold distribution appears in the o.d.e. via its hazard rate function. We demonstrate the accuracy of the o.d.e. approximation and derive explicit expressions for the trajectory of influence under the uniform threshold distribution. Also, for an exponentially distributed threshold, we show that the fluid dynamics are equivalent to the well-known SIR model in epidemiology. We also numerically study how other hazard functions (obtained from the Weibull and loglogistic distributions) provide qualitative different characteristics of the influence evolution, compared to traditional epidemic models, even in a homogeneous setting. We finally show how the model can be extended to a setting with multiple communities and conclude with possible future directions.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

QoS Aware and Survivable Network Design for Planned Wireless Sensor Networks

We study the problem of wireless sensor network design by deploying a minimum number of additional relay nodes (to minimize network cost) at a subset of given potential relay locations, in order to convey the data from already existing sensor nodes (hereafter called source nodes) to a Base Station, while meeting a certain specified hop count bound (the hop count bound is chosen to ensure a pre-determined probability of the data being delivered to the BS within a given maximum delay). We study two variations of the problem. First we sudy the problem of guaranteed QoS connected network design, where the objective is to have at least one path from each source to the BS with the specified hop count bound. We show that the problem is NP-Hard. For a problem in which the number of existing sensor nodes and potential relay locations is n, we propose an O(n) approximation algorithm of polynomial time complexity. Results show that the algorithm performs efficiently (in over 90% of the tested scenarios, it gave solutions that were either optimal or were worse than optimal by just one relay) in various randomly generated network scenarios. Next, we study the problem of survivable network design with guaranteed QoS, i.e, the requirement is to have at least k > 1 node disjoint hop constrained paths from each source to the BS. We show that the problem is NP-Hard. We also show that the problem of finding a feasible solution to this optimization problem is NP-Complete. We propose two polynomial time heuristics for this problem, and compare their performance on various randomly generated network scenarios.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

QoS Constrained Optimal Sink and Relay Placement in Planned Wireless Sensor Networks

We are given a set of sensors at given locations, a set of potential locations for placing base stations (BSs, or sinks), and another set of potential locations for placing wireless relay nodes. There is a cost for placing a BS and a cost for placing a relay. The problem we consider is to select a set of BS locations, a set of relay locations, and an association of sensor nodes with the selected BS locations, so that number of hops in the path from each sensor to its BS is bounded by hmax, and among all such feasible networks, the cost of the selected network is the minimum. The hop count bound suffices to ensure a certain probability of the data being delivered to the BS within a given maximum delay under a light traffic model. We observe that the problem is NP-Hard, and is hard to even approximate within a constant factor. For this problem, we propose a polynomial time approximation algorithm (SmartSelect) based on a relay placement algorithm proposed in our earlier work, along with a modification of the greedy algorithm for weighted set cover. We have analyzed the worst case approximation guarantee for this algorithm. We have also proposed a polynomial time heuristic to improve upon the solution provided by SmartSelect. Our numerical results demonstrate that the algorithms provide good quality solutions using very little computation time in various randomly generated network scenarios.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

SmartConnect: A System for the Design and Deployment of Wireless Sensor Networks

We have developed SmartConnect, a tool that addresses the growing need for the design and deployment of multihop wireless relay networks for connecting sensors to a control center. Given the locations of the sensors, the traffic that each sensor generates, the quality of service (QoS) requirements, and the potential locations at which relays can be placed, SmartConnect helps design and deploy a low- cost wireless multihop relay network. SmartConnect adopts a field interactive, iterative approach, with model based network design, field evaluation and relay augmentation per- formed iteratively until the desired QoS is met. The design process is based on approximate combinatorial optimization algorithms. In the paper, we provide the design choices made in SmartConnect and describe the experimental work that led to these choices. We provide results from some experimental deployments. Finally, we conduct an experimental study of the robustness of the network design over long time periods (as channel conditions slowly change), in terms of the relay augmentation and route adaptation required.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

As-You-Go Deployment of a Wireless Network with On-Line Measurements and Backtracking

We are motivated by the need, in some applications, for impromptu or as-you-go deployment of wireless sensor networks. A person walks along a line, making link quality measurements with the previous relay at equally spaced locations, and deploys relays at some of these locations, so as to connect a sensor placed on the line with a sink at the start of the line. In this paper, we extend our earlier work on the problem (see [1]) to incorporate two new aspects: (i) inclusion of path outage in the deployment objective, and (ii) permitting the deployment agent to make measurements over several consecutive steps before selecting a placement location among them (which we call backtracking). We consider a light traffic regime, and formulate the problem as a Markov decision process. Placement algorithms are obtained for two cases: (i) the distance to the source is geometrically distributed with known mean, and (ii) the average cost per step case. We motivate the per-step cost function in terms of several known forwarding protocols for sleep-wake cycling wireless sensor networks. We obtain the structures of the optimal policies for the various formulations, and provide some sensitivity results about the policies and the optimal values. We then provide a numerical study of the algorithms, thus providing insights into the advantage of backtracking, and a comparison with simple heuristic placement policies.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Cell-Level Modeling of IEEE 802.11 WLANs

We develop a scalable \textit{cell-level} analytical model for multi-cell infrastructure IEEE 802.11 WLANs under a so-called Pairwise Binary Dependence (PBD) condition. The PBD condition is a geometric property under which the relative locations of the nodes inside a cell do not matter and the network is free of \textit{hidden nodes}. For the cases of saturated nodes and TCP-controlled long-file downloads, we provide accurate predictions of cell throughputs. Similar to Bonald et al (Sigmetrics, 2008), we model a multi-cell WLAN under short-file downloads as "a network of processor-sharing queues with state-dependent service rates." Whereas the state-dependent service rates proposed by Bonald et al are based only on the \textit{number} of contending neighbors, we employ state-dependent service rates that incorporate the the impact of the overall \textit{topology} of the network. We propose an \textit{effective service rate approximation} technique and obtain good approximations for the \textit{mean flow transfer delay} in each cell. For TCP-controlled downloads where the APs transmit a large fraction of time, we show that the throughputs predicted under the PBD condition are very good approximations in two important scenarios where hidden nodes are indeed present and the PBD condition does not strictly hold.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Measurement Based Impromptu Deployment of a Multi-Hop Wireless Relay Network

We study the problem of optimal sequential ("as-you-go") deployment of wireless relay nodes as a person walks along a line of random length (with a known distribution). The objective is to create an impromptu multihop wireless network for connecting a packet source to be placed at the end of the line with a sink node located at the starting point, to operate in the light traffic regime. As the deployment person walks along the line from the sink towards the source, at every step, he measures the channel quality to one (or more) previously placed relays, and places the relay nodes based on these measurements, so as to minimize either the sum power or the maximum power from the source to the sink node in the resultant network, subject to a constraint on the expected number of relays placed. For each of these two objectives, two different relay selection strategies are considered: (i) each relay communicates with the sink via its immediate previous relay, (ii) the communication path can skip some of the deployed relays. With appropriate modeling assumptions, we formulate each of these problems as a Markov decision process (MDP). We provide the optimal policy structures for all these cases, and provide illustrations, via numerical results, for some typical parameters.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Optimal Capacity Relay Node Placement in a Multi-hop Wireless Network on a Line

We use information theoretic achievable rate formulas for the multi-relay channel to study the problem of optimal placement of relay nodes along the straight line joining a source node and a sink node. The achievable rate formulas that we use are for full-duplex radios at the relays and decode- and-forward relaying. For the single relay case, and individual power constraints at the source node and the relay node, we provide explicit formulas for the optimal relay location and the optimal power allocation to the source-relay channel, for the exponential and the power-law path-loss channel models. For the multiple relay case, we consider exponential path-loss and a total power constraint over the source and the relays, and derive an optimization problem, the solution of which provides the optimal relay locations. Numerical results suggest that at low attenuation the relays are mostly clustered close to the source in order to be able to cooperate among themselves, whereas at high attenuation they are uniformly placed and work as repeaters. The structure of the optimal power allocation for a given placement of the nodes, then motivates us to formulate the problem of impromptu ("as-you-go") placement of relays along a line of exponentially distributed length, with exponential path- loss, so as to minimize a cost function that is additive over hops. The hop cost trades off a capacity limiting term, motivated from the optimal power allocation solution, against the cost of adding a relay node. We formulate the problem as a total cost Markov decision process, for which we prove results for the value function, and provide insights into the placement policy via numerical exploration.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Relay Selection with Channel Probing in Sleep-Wake Cycling Wireless Sensor Networks

In geographical forwarding of packets in a large wireless sensor network (WSN) with sleep-wake cycling nodes, we are interested in the local decision problem faced by a node that has custody of a packet and has to choose one among a set of next-hop relay nodes to forward the packet towards the sink. Each relay is associated with a reward that summarizes the benefit of forwarding the packet through that relay. We seek a solution to this local problem, the idea being that such a solution, if adopted by every node, could provide a reasonable heuristic for the end-to-end forwarding problem. Towards this end, we propose a relay selection problem comprising a forwarding node and a collection of relay nodes, with the relays waking up sequentially at random times. At each relay wake-up instant the forwarder can choose to probe a relay to learn its reward value, based on which the forwarder can then decide whether to stop (and forward its packet to the chosen relay) or to continue to wait for further relays to wake-up. The forwarder's objective is to select a relay so as to minimize a combination of waiting-delay, reward and probing cost. Our problem can be considered as a variant of the asset selling problem studied in the operations research literature. We formulate our relay selection problem as a Markov decision process (MDP) and obtain some interesting structural results on the optimal policy (namely, the threshold and the stage-independence properties). We also conduct simulation experiments and gain valuable insights into the performance of our local forwarding-solution.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Neighbor Oblivious and Finite-State Algorithms for Circumventing Local Minima in Geographic Forwarding

We propose distributed link reversal algorithms to circumvent communication voids in geographic routing. We also solve the attendant problem of integer overflow in these algorithms. These are achieved in two steps. First, we derive partial and full link reversal algorithms that do not require one-hop neighbor information, and convert a destination-disoriented directed acyclic graph (DAG) to a destination-oriented DAG. We embed these algorithms in the framework of Gafni and Bertsekas ("Distributed algorithms for generating loop-free routes in networks with frequently changing topology", 1981) in order to establish their termination properties. We also analyze certain key properties exhibited by our neighbor oblivious link reversal algorithms, e.g., for any two neighbors, their t-states are always consecutive integers, and for any node, its t-state size is upper bounded by log(N). In the second step, we resolve the integer overflow problem by analytically deriving one-bit full link reversal and two-bit partial link reversal versions of our neighbor oblivious link reversal algorithms.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Optimal Sequential Wireless Relay Placement on a Random Lattice Path

Our work is motivated by the need for impromptu (or "as-you-go") deployment of relay nodes (for establishing a packet communication path with a control centre) by fire-men/commandos while operating in an unknown environment. We consider a model, where a deployment operative steps along a random lattice path whose evolution is Markov. At each step, the path can randomly either continue in the same direction or take a turn "North" or "East," or come to an end, at which point a data source (e.g., a temperature sensor) has to be placed that will send packets to a control centre at the origin of the path. A decision has to be made at each step whether or not to place a wireless relay node. Assuming that the packet generation rate by the source is very low, and simple link-by-link scheduling, we consider the problem of relay placement so as to minimize the expectation of an end-to-end cost metric (a linear combination of the sum of convex hop costs and the number of relays placed). This impromptu relay placement problem is formulated as a total cost Markov decision process. First, we derive the optimal policy in terms of an optimal placement set and show that this set is characterized by a boundary beyond which it is optimal to place. Next, based on a simpler alternative one-step-look-ahead characterization of the optimal policy, we propose an algorithm which is proved to converge to the optimal placement set in a finite number of steps and which is faster than the traditional value iteration. We show by simulations that the distance based heuristic, usually assumed in the literature, is close to the optimal provided that the threshold distance is carefully chosen.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Performance Analysis of Beacon-Less IEEE 802.15.4 Multi-Hop Networks

We develop an approximate analytical technique for evaluating the performance of multi-hop networks based on beacon-less CSMA/CA as standardised in IEEE 802.15.4, a popular standard for wireless sensor networks. The network comprises sensor nodes, which generate measurement packets, and relay nodes which only forward packets. We consider a detailed stochastic process at each node, and analyse this process taking into account the interaction with neighbouring nodes via certain unknown variables (e.g., channel sensing rates, collision probabilities, etc.). By coupling these analyses of the various nodes, we obtain fixed point equations that can be solved numerically to obtain the unknown variables, thereby yielding approximations of time average performance measures, such as packet discard probabilities and average queueing delays. Different analyses arise for networks with no hidden nodes and networks with hidden nodes. We apply this approach to the performance analysis of tree networks rooted at a data sink. Finally, we provide a validation of our analysis technique against simulations.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Spread of Influence and Content in Mobile Opportunistic Networks

We consider a setting in which a single item of content (such as a song or a video clip) is disseminated in a population of mobile nodes by opportunistic copying when pairs of nodes come in radio contact. We propose and study models that capture the joint evolution of the population of nodes interested in the content (referred to as destinations), and the population of nodes that possess the content. The evolution of interest in the content is captured using an influence spread model and the content spread occurs via epidemic copying. Nodes not yet interested in the content are called relays; the influence spread process converts relays into destinations. We consider the decentralized setting, where interest in the content and the spread of the content evolve by pairwise interactions between the mobiles. We derive fluid limits for the joint evolution models and obtain optimal policies for copying to relay nodes in order to deliver content to a desired fraction of destinations. We prove that a time-threshold policy is optimal while copying to relays. We then provide insights into the effects of various system parameters on the co-evolution model through simulations.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Co-evolution of Content Popularity and Delivery in Mobile P2P Networks

Mobile P2P technology provides a scalable approach to content delivery to a large number of users on their mobile devices. In this work, we study the dissemination of a \emph{single} content (e.g., an item of news, a song or a video clip) among a population of mobile nodes. Each node in the population is either a \emph{destination} (interested in the content) or a potential \emph{relay} (not yet interested in the content). There is an interest evolution process by which nodes not yet interested in the content (i.e., relays) can become interested (i.e., become destinations) on learning about the popularity of the content (i.e., the number of already interested nodes). In our work, the interest in the content evolves under the \emph{linear threshold model}. The content is copied between nodes when they make random contact. For this we employ a controlled epidemic spread model. We model the joint evolution of the copying process and the interest evolution process, and derive the joint fluid limit ordinary differential equations. We then study the selection of the parameters under the content provider's control, for the optimization of various objective functions that aim at maximizing content popularity and efficient content delivery.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Combined Base Station Association and Power Control in Multi-channel Cellular Networks

A combined base station association and power control problem is studied for the uplink of multichannel multicell cellular networks, in which each channel is used by exactly one cell (i.e., base station). A distributed association and power update algorithm is proposed and shown to converge to a Nash equilibrium of a noncooperative game. We consider network models with discrete mobiles (yielding an atomic congestion game), as well as a continuum of mobiles (yielding a population game). We find that the equilibria need not be Pareto efficient, nor need they be system optimal. To address the lack of system optimality, we propose pricing mechanisms. It is shown that these mechanisms can be implemented in a distributed fashion.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Delay Optimal Event Detection on Ad Hoc Wireless Sensor Networks

We consider a small extent sensor network for event detection, in which nodes take samples periodically and then contend over a {\em random access network} to transmit their measurement packets to the fusion center. We consider two procedures at the fusion center to process the measurements. The Bayesian setting is assumed; i.e., the fusion center has a prior distribution on the change time. In the first procedure, the decision algorithm at the fusion center is \emph{network-oblivious} and makes a decision only when a complete vector of measurements taken at a sampling instant is available. In the second procedure, the decision algorithm at the fusion center is \emph{network-aware} and processes measurements as they arrive, but in a time causal order. In this case, the decision statistic depends on the network delays as well, whereas in the network-oblivious case, the decision statistic does not depend on the network delays. This yields a Bayesian change detection problem with a tradeoff between the random network delay and the decision delay; a higher sampling rate reduces the decision delay but increases the random access delay. Under periodic sampling, in the network--oblivious case, the structure of the optimal stopping rule is the same as that without the network, and the optimal change detection delay decouples into the network delay and the optimal decision delay without the network. In the network--aware case, the optimal stopping problem is analysed as a partially observable Markov decision process, in which the states of the queues and delays in the network need to be maintained. A sufficient statistic for decision is found to be the network-state and the posterior probability of change having occurred given the measurements received and the state of the network. The optimal regimes are studied using simulation.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Distributed Detection/Isolation Procedures for Quickest Event Detection in Large Extent Wireless Sensor Networks

We study a problem of distributed detection of a stationary point event in a large extent wireless sensor network ($\wsn$), where the event influences the observations of the sensors only in the vicinity of where it occurs. An event occurs at an unknown time and at a random location in the coverage region (or region of interest ($\ROI$)) of the $\wsn$. We consider a general sensing model in which the effect of the event at a sensor node depends on the distance between the event and the sensor node; in particular, in the Boolean sensing model, all sensors in a disk of a given radius around the event are equally affected. Following the prior work reported in \cite{nikiforov95change_isolation}, \cite{nikiforov03lower-bound-for-det-isolation}, \cite{tartakovsky08multi-decision}, {\em the problem is formulated as that of detecting the event and locating it to a subregion of the $\ROI$ as early as possible under the constraints that the average run length to false alarm ($\tfa$) is bounded below by $γ$, and the probability of false isolation ($\pfi$) is bounded above by $α$}, where $γ$ and $α$ are target performance requirements. In this setting, we propose distributed procedures for event detection and isolation (namely $\mx$, $\all$, and $\hall$), based on the local fusion of $\CUSUM$s at the sensors. For these procedures, we obtain bounds on the maximum mean detection/isolation delay ($\add$), and on $\tfa$ and $\pfi$, and thus provide an upper bound on $\add$ as $\min\{γ,1/α\} \to \infty$. For the Boolean sensing model, we show that an asymptotic upper bound on the maximum mean detection/isolation delay of our distributed procedure scales with $γ$ and $α$ in the same way as the asymptotically optimal centralised procedure \cite{nikiforov03lower-bound-for-det-isolation}.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Optimal Forwarding in Delay Tolerant Networks with Multiple Destinations

We study the trade-off between delivery delay and energy consumption in a delay tolerant network in which a message (or a file) has to be delivered to each of several destinations by epidemic relaying. In addition to the destinations, there are several other nodes in the network that can assist in relaying the message. We first assume that, at every instant, all the nodes know the number of relays carrying the packet and the number of destinations that have received the packet. We formulate the problem as a controlled continuous time Markov chain and derive the optimal closed loop control (i.e., forwarding policy). However, in practice, the intermittent connectivity in the network implies that the nodes may not have the required perfect knowledge of the system state. To address this issue, we obtain an ODE (i.e., a deterministic fluid) approximation for the optimally controlled Markov chain. This fluid approximation also yields an asymptotically optimal open loop policy. Finally, we evaluate the performance of the deterministic policy over finite networks. Numerical results show that this policy performs close to the optimal closed loop policy.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Optimum Sleep-Wake Scheduling of Sensors for Quickest Event Detection in Small Extent Wireless Sensor Networks

We consider the problem of quickest event detection with sleep-wake scheduling in small extent wireless sensor networks in which, at each time slot, each sensor node in the awake state observes a sample and communicates the information to the fusion centre. The sensor nodes in the sleep state do not sample or communicate any information to the fusion centre (FC), thereby conserving energy. At each time slot, the FC, after having received the samples from the sensor nodes in the wake state, makes a decision to stop (and thus declare that the event has occurred) or to continue observing. If it decides to continue, the FC also makes the decision of choosing the number of sensor nodes to be in the wake state in the next time slot. We consider three alternative approaches to the problem of choosing the number of sensor nodes to be in the wake state in time slot k+1, based on the information available at time slot k, namely, 1. optimal control of M_{k+1}, the number of sensor nodes to be in the awake state in time slot k+1, 2. optimal control of q_{k+1}, the probability of a sensor node to be in the awake state in time slot k+1, and 3. optimal probability q that a sensor node is in the awake state in any time slot. In each case, we formulate the problem as a sequential decision process. We show that a sufficient statistic for the decision at time k is the a posteriori probability of change Pi_k. Also, we show that the optimal stopping rule is a threshold rule on Pi_k. The optimal policy for M_{k+1} can keep very few sensors wake during the prechange phase and then quickly increase the number of sensors in the wake state when a change is "suspected". Among the three sleep-wake algorithms described, we observe that the total cost is minimum for the optimum control of M_{k+1} and is maximum for the optimum control on q.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Relay Selection with Partial Information in Wireless Sensor Networks

Our work is motivated by geographical forwarding of sporadic alarm packets to a base station in a wireless sensor network (WSN), where the nodes are sleep-wake cycling periodically and asynchronously. When a node (referred to as the source) gets a packet to forward, either by detecting an event or from an upstream node, it has to wait for its neighbors in a forwarding set (referred to as relays) to wake-up. Each of the relays is associated with a random reward (e.g., the progress made towards the sink) that is iid. To begin with, the source is uncertain about the number of relays, their wake-up times and the reward values, but knows their distributions. At each relay wake-up instant, when a relay reveals its reward value, the source's problem is to forward the packet or to wait for further relays to wake-up. In this setting, we seek to minimize the expected waiting time at the source subject to a lower bound on the average reward. In terms of the operations research literature, our work can be considered as a variant of the asset selling problem. We formulate the relay selection problem as a partially observable Markov decision process (POMDP), where the unknown state is the number of relays. We begin by considering the case where the source knows the number of relays. For the general case, where the source only knows a pmf on the number of relays, it has to maintain a posterior pmf on the number of relays and forward the packet iff the pmf is in an optimum stopping set. We show that the optimum stopping set is convex and obtain inner and outer bounds to this set. The computational complexity of the above policies motivates us to formulate an alternative simplified model, the optimal policy for which is a simple threshold rule. We provide simulation results to compare the performance of the various one-hop and end-to-end forwarding policies.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Spatial SINR Games of Base Station Placement and Mobile Association

We study the question of determining locations of base stations that may belong to the same or to competing service providers. We take into account the impact of these decisions on the behavior of intelligent mobile terminals who can connect to the base station that offers the best utility. The signal to interference and noise ratio is used as the quantity that determines the association. We first study the SINR association-game: we determine the cells corresponding to each base stations, i.e., the locations at which mobile terminals prefer to connect to a given base station than to others. We make some surprising observations: (i) displacing a base station a little in one direction may result in a displacement of the boundary of the corresponding cell to the opposite direction; (ii) A cell corresponding to a BS may be the union of disconnected sub-cells. We then study the hierarchical equilibrium in the combined BS location and mobile association problem: we determine where to locate the BSs so as to maximize the revenues obtained at the induced SINR mobile association game. We consider the cases of single frequency band and two frequency bands of operation. Finally, we also consider hierarchical equilibria in two frequency systems with successive interference cancellation.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Analytical Modeling of Saturation Throughput in Power Save Mode of an IEEE 802.11 Infrastructure WLAN

We consider a single station (STA) in the Power Save Mode (PSM) of an IEEE 802.11 infrastructure WLAN. This STA is assumed to be carrying uplink and downlink traffic via the access point (AP). We assume that the transmission queues of the AP and the STA are saturated, i.e., the AP and the STA always have at least one packet to send. For this scenario, it is observed that uplink and downlink throughputs achieved are different. The reason behind the difference is the long term attempt rates of the STA and the AP due to the PSM protocol. In this paper we first obtain the the long term attempt rates of the STA and the AP and using these, we obtain the saturation throughputs of the AP and the STA. We provide a validation of analytical results using the NS-2 simulator.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Distributed Construction of the Critical Geometric Graph in Dense Wireless Sensor Networks

Wireless sensor networks are often modeled in terms of a dense deployment of smart sensor nodes in a two-dimensional region. Give a node deployment, the \emph{critical geometric graph (CGG)} over these locations (i.e., the connected \emph{geometric graph (GG)} with the smallest radius) is a useful structure since it provides the most accurate proportionality between hop-count and Euclidean distance. Hence, it can be used for GPS-free node localisation as well as minimum distance packet forwarding. It is also known to be asymptotically optimal for network transport capacity and power efficiency. In this context, we propose DISCRIT, a distributed and asynchronous algorithm for obtaining an approximation of the CGG on the node locations. The algorithm does not require the knowledge of node locations or internode distances, nor does it require pair-wise RSSI (Received Signal Strength Indication) measurements to be made. Instead, the algorithm makes use of successful Hello receipt counts (obtained during a Hello-protocol-based neighbour discovery process) as edge weights, along with a simple distributed min-max computation algorithm. In this paper, we first provide the theory for justifying the use of the above edge weights. Then we provide extensive simulation results to demonstrate the efficacy of DISCRIT in obtaining an approximation of the CGG. Finally, we show how the CGG obtained from DISCRIT performs when used in certain network self-organisation algorithms.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

New Insights from an Analysis of Social Influence Networks under the Linear Threshold Model

We study the spread of influence in a social network based on the Linear Threshold model. We derive an analytical expression for evaluating the expected size of the eventual influenced set for a given initial set, using the probability of activation for each node in the social network. We then provide an equivalent interpretation for the influence spread, in terms of acyclic path probabilities in the Markov chain obtained by reversing the edges in the social network influence graph. We use some properties of such acyclic path probabilities to provide an alternate proof for the submodularity of the influence function. We illustrate the usefulness of the analytical expression in estimating the most influential set, in special cases such as the UILT(Uniform Influence Linear Threshold), USLT(Uniform Susceptance Linear Threshold) and node-degree based influence models. We show that the PageRank heuristic is either provably optimal or performs very well in the above models, and explore its limitations in more general cases. Finally, based on the insights obtained from the analytical expressions, we provide an efficient algorithm which approximates the greedy algorithm for the influence maximization problem.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Obstacle Constrained Total Area Coverage in Wireless Sensor Networks

This paper deals with the accomplishment of total area coverage of an arbitrary region using sensors with a finite sensing radius of rs. For a given region, we aim to obtain a deterministic placement of sensors which, apart from ensuring that the entire region comes under the purview of at least a single sensor, minimises the number of sensors utilised. We begin by considering regions devoid of obstacles and thus having every location amenable for placement. Herein, we formalise the popular notion that sensors at the centres of the hexagons of a hexagonal tessellation provide the most optimal placement. We then move on to regions which may comprise obstacles of arbitrary size at arbitrary locations. We recognise two distinct classes of obstacles, namely transparent and opaque obstacles, which are distinguished by their ability (or the lack of it) to permit sensing radiation through them. In the real world, transparent obstacles model lakes, ponds and swamps, while the opaque ones stand for, inter alia, hills, trees and walls.We propose a polynomial-time algorithm for achieving optimal placement in the aforesaid scenarios and we prove its convergence.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

State Dependent Attempt Rate Modeling of Single Cell IEEE~802.11 WLANs with Homogeneous Nodes and Poisson Packet Arrivals

Analytical models for IEEE 802.11-based WLANs are invariably based on approximations, such as the well-known \textit{decoupling approximation} proposed by Bianchi for modeling single cell WLANs consisting of saturated nodes. In this paper, we provide a new approach to model the situation when the nodes are not saturated. We study a State Dependent Attempt Rate (SDAR) approximation to model $M$ queues (one queue per node) served by the CSMA/CA protocol as standardized in the IEEE 802.11 DCF MAC protocol. The approximation is that, when $n$ of the $M$ queues are non-empty, the transmission attempt probability of the $n$ non-empty nodes is given by the long-term transmission attempt probability of $n$ "saturated" nodes as provided by Bianchi's model. The SDAR approximation reduces a single cell WLAN with non-saturated nodes to a "coupled queue system". When packets arrive to the $M$ queues according to independent Poisson processes, we provide a Markov model for the coupled queue system with SDAR service. \textit{The main contribution of this paper is to provide an analysis of the coupled queue process by studying a lower dimensional process, and by introducing a certain conditional independence approximation}. We show that the SDAR model of contention provides an accurate model for the DCF MAC protocol in single cells, and report the simulation speed-ups thus obtained by our \textit{model-based simulation}.

0 citations0 reviewsNo code linkedOpen access