Neighbor discovery (ND) is an essential prerequisite for any peer-to-peer communication. In general, minimizing the discovery time is the goal for ND schemes. In this paper, we study the average discovery time for directional random ND when nodes have prior information about their set of possible neighbors, which also helps identify the performance limits of random ND schemes. Typically, discovery time analysis is done for assumptions that simplify the network structure, such as uniform neighbor relations for all nodes. However, with prior information the directional transmission probabilities depend on the node and the direction. This complicates the analysis of the expected discovery time. We first provide a closed-form expression for the expected discovery time based on the non-uniform coupon collector problem. Next, we identify directional transmission probabilities of each node that achieve a small discovery time. Due to the mathematical complexity, we provide a lower and an upper bound on the expected discovery time, which allows us to write the problem as a convex optimization problem. Through simulations, we demonstrate the performance gain due to prior knowledge with the proposed methods as compared with when no prior information is available, as well as the impact of uncertainty in the prior knowledge.

In recent years, deep convolutional networks have been successfully used for the tasks of image classification and speech recognition. The highly non-linear modeling combined with its emphasis on local connectivity makes them highly suitable for such tasks. However, their performance in other domains is not well explored. Specifically, in the oil industry, researchers use manual features from time series data as input to various machine learning models. In this paper, we employ deep convolutional autoencoders to extract non linear latent features from time series data. We propose a novel deep network architecture and show its efficacy in two oil field tasks related to reservoir optimization - steam job prediction and slippage detection. We show that our architecture outperforms state-of-the-art methods significantly on steam job prediction. We demonstrate the success of our model on an oil field dataset which consists of production and failure data of over two years. Our architecture achieves a precision of 98% for precision@50 in steam job prediction, and 25% improvement over the methods used in the industry. To the best of our knowledge, we are the first to attempt to automatically detect slippage failures in well pumps. We are able to classify slippage events with 70.3% accuracy, a 10.6% improvement over using manually defined input features.

Neighbor discovery is an essential prerequisite for any device-to-device (D2D) communication. Unlike ad-hoc networks, the base station (BS) in D2D networks may facilitate the neighbor discovery process. However, device-to-BS channel states or device locations are not enough to provide BS with information on the channel quality between the devices. Thus, due to the inherent uncertainty of link quality between devices, the BS-assisted neighbor discovery cannot be treated as typical scheduling problem. In this paper, we investigate the assisted directional neighbor discovery in D2D networks. We first formulate the scheduling problem as an integer optimization problem that captures the uncertainty. Then we propose a greedy based centralized scheduling to determine directional pilot transmission instances. We also propose a one-way randomized discovery, where we choose the directional transmission probabilities based on two techniques, an intuitive and an optimized methods. Finally, we provide simulation results that assess the performance the schemes.

We consider the scenario of broadcasting for real-time applications, such as multi-player games and video streaming, and loss recovery via instantly decodable network coding. The source has a single time slot or multiple time slots to broadcast (potentially coded) recovery packet(s), and the application does not need to recover all losses. Our goal is to find packet(s) that are instantly decodable and maximize the number of lost packets that the users can recover. First, we show that this problem is equivalent to the unique coverage problem in the general case, and therefore, it is hard to approximate. Then, we consider the practical probabilistic scenario, where users have i.i.d. loss probability and the number of packets is either constant (video streaming), linear (multi-player games), or polynomial in the number of users, and we provide two polynomial-time (in the number of users) algorithms. For the single-slot case, we propose Max Clique, an algorithm that provably finds the optimal coded packet w.h.p. For the case where there is a small constant number of slots, we propose Multi-Slot Max Clique, an algorithm that provably finds a near-optimal solution w.h.p. when the number of packets is sufficiently large. The proposed algorithms are evaluated using both simulation and real network traces from an Android multi-player game. And they are shown to perform near optimally and to significantly outperform the state-of-the-art baselines.

We introduce a new neighbor discovery method for wireless nodes with adaptive antennas, called "directional ZigZag." Adaptive antennas are capable of electronically changing their gain pattern and in particular form beams and steer them in arbitrary directions. Despite improving range, this makes neighbor discovery more difficult. We consider three cases; namely, nodes transmit with beamsteering and receive in omni-directional mode (DTOR), transmit with omni-directional antenna and receive with beam- steering (OTDR), and use beamsteering (directional antennas) for both transmitting and receiving (DTDR). We show that directional ZigZag detects the neighbors with vanishing probability of error. Furthermore, it is the first algorithm that requires a discovery period that scales on linearly with the average number of neighbors. This is proven through establishing a connection between ZigZag and message passing decoding.

We introduce a new neighbor discovery method called “ZigZag”. We present two versions of ZigZag, namely, deterministic and random. We show a close connection between performance of ZigZag and message passing decoding of low density parity check codes over an erasure channel.

We present the first deterministic measurement matrix construction with an order-optimal number of rows for sparse signal reconstruction. This improves the measurements required in prior constructions and addresses a known open problem in the theory of sparse signal recovery. Our construction uses adjacency matrices of bipartite graphs that have large girth. The main result is that girth (the length of the shortest cycle in the graph) can be used as a certificate that a measurement matrix can recover almost all sparse signals. Specifically, our matrices guarantee recovery “for-each” sparse signal under basis pursuit. Our techniques are coding theoretic and rely on a recent connection of compressed sensing to LP relaxations for channel decoding.

We study the problem of neighbor discovery in which each node desires to detect nodes within a single hop. Each node is assigned a unique signature known by all other nodes. The problem can be considered as a compressed sensing problem. We propose a explicit-non-random-construction for the signatures. Further, we suggest the basis pursuit to detect the neighbors and offer a guarantee for its performance. Specifically, we show that the average number of errors can be made arbitrary small as the number of nodes in the network grows. Our result does not depend on the density of the network, i.e., how the average number of neighbors scales with respect to the total number of nodes.

We explicitly construct binary measurement matrices with good sparse approximation guarantees. Specifically, our measurement matrices have an order optimal number of measurements and have ℓ1/ℓ1approximation guarantee. Our construction uses the progressive edge growth technique. We apply coding theoretic results and rely on a recent connection of compressed sensing to LP relaxation for channel decoding.

We consider a wireless broadcast station that transmits packets to multiple users. The packet requests for each user may overlap, and some users may already have certain packets. This presents a problem of broadcasting in the presence of side information, and is a generalization of the well-known (and unsolved) index coding problem of information theory. We represent the problem by a bipartite demand graph. Uncoded transmission is optimal if and only if this graph is acyclic. Next, we define a code-constrained capacity region that restricts attention to any prespecified set of coding actions. A dynamic max-weight algorithm that acts over variable length frames is developed. The algorithm allows for random packet arrivals and supports any traffic inside the code-constrained capacity region. A simple set of codes that exploit cycles in the demand graph are shown to be optimal for a class of broadcast relay problems.

We investigate a fundamental wireless broadcast problem called Index coding. We focus on binary linear scalar index coding problems when it is a-priori known that the optimal solution requires three transmissions. For this case, we characterize the relation of the clique cover number of the side information graph G and the optimal index code. This allows us to show that even when there is a-priori knowledge that three transmissions can solve a given index coding problem, finding these transmissions is NP-hard. Another implication of our results is that for three solvable undirected problems, the benefit of interference alignment solutions is at most one compared to a simple clique cover.

We consider a wireless broadcast station that transmits packets to multiple users. The packet requests for each user may overlap, and some users may already have certain packets. This presents a problem of broadcasting in the presence of side information, and is a generalization of the well known (and unsolved) index coding problem of information theory. Rather than achieving the full capacity region, we develop a code-constrained capacity region, which restricts attention to a pre-specified set of coding actions. We develop a dynamic max-weight algorithm that allows for random packet arrivals and supports any traffic inside the code-constrained capacity region. Further, we provide a simple set of codes based on cycles in the underlying demand graph. We show these codes are optimal for a class of broadcast relay problems.

We analyze a generalized index coding problem that allows multiple users to request the same packet. For this problem we introduce a novel coding scheme called partition multicast. Our scheme can be seen as a natural generalization of clique cover for directed index coding problems. Further, partition multicast corresponds to an achievable scheme for the generalized bipartite index coding problem that we introduce in this paper. Our scheme partitions the nodes into groups and solves a multicasting problem within each group. We show that Partition Multicast is optimal for a few families of graphs and generalizes previous achievable schemes, namely directed cycle covers. We also show that finding the best partition is computationally intractable to compute in general.

The multiple-access framework of ZigZag decoding [1] is a useful technique for combating interference via multiple repeated transmissions, and is known to be compatible with distributed random access protocols. However, in the presence of noise this type of decoding can magnify errors, particularly when packet sizes are large. We present a simple soft-decoding version, called SigSag, that improves performance. We show that for two users, collisions result in a cycle-free factor graph that can be optimally decoded via belief propagation. For collisions between more than two users, we show that if a simple bit-permutation is used then the graph is locally tree-like with high probability, and hence belief propagation is near optimal. Through simulations we show that our scheme performs better than coordinated collision-free time division multiple access (TDMA) and the ZigZag decoder.

We show that girth can be used to certify that sparse compressed sensing matrices have good sparse approximation guarantees. This allows us to present the first deterministic measurement matrix constructions that have an optimal number of measurements for ℓ1/ℓ1approximation. Our techniques are coding theoretic and rely on a recent connection of compressed sensing to LP relaxations for channel decoding.