Selected publications

Book chapters

  1. Download: waltertraffic.pdf 
    This is an initial study into the behavior of traffic matrices at different scales of resolution.
  2. J. Chui, S. Das, N. Al-Dhahir, S. N. Diggavi, and A. R. Calderbank, "Space-time codes and application in WiMAX." , 2007.
  3. Download: acdbookchapter.pdf 
    This was a survey on space-time codes and signal processing with a focus on recent (when the chapter was written) developments.
  4. Download: divincomm.pdf 
    This paper brings together how diversity plays a role in diverse topics like source coding, physical layer wireless communication and mobility in wireless networks.
  5. Download: dimacschap.pdf 
    Diversity embedded codes give different levels of diversity protection to different information streams. This was the short paper that introduced diversity embedded codes.
  6. S. N. Diggavi, N. Al-Dhahir, and A. R. Calderbank, "Diversity Order of Space-Time Block Codes in Inter-Symbol Interference Multiple-Access Channels." , 2003, vol. 62.

Journal papers (preprints)

Journal papers (published/to appear)

  1. Download: tian_matched.pdf 
  2. Download: mishra_secure.pdf 
  3. Download: shirin_nested.pdf 
  4. Download: laszlo_lp.pdf 
  5. Download: winetsec_boe.pdf www 
  6. Download: karam_hier.pdf 
  7. Download: jad_multilevel.pdf 
  8. Download: kwd_it15.pdf www 
  9. Download: koltead_it15.pdf www 
  10. Download: secretcom_czap.pdf www 
  11. Download: snc_czapfpd.pdf www 
  12. Abstract:
    Wireless network topologies change over time and maintaining routes requires frequent updates. Updates are costly in terms of consuming throughput available for data transmission, which is precious in wireless networks. In this paper, we ask whether there exist low-overhead schemes that produce near-optimal routes. We show that random geometric graphs and variants have a nice property that they are doubling metric spaces, with high probability. This enables us to design hierarchical routing schemes with provable performance that account for the user mobility and scale well with network size.
  13. Download: on Arxiv 
    The vast majority of today's critical infrastructure is supported by numerous feedback control loops and an attack on these control loops can have disastrous consequences. This is a major concern since modern control systems are becoming large and decentralized and thus more vulnerable to attacks. This paper is concerned with the estimation and control of linear systems when some of the sensors or actuators are corrupted by an attacker. We give a new simple characterization of the maximum number of attacks that can be detected and corrected as a function of the pair (A,C) of the system and we show in particular that it is impossible to accurately reconstruct the state of a system if more than half the sensors are attacked. In addition, we show how the design of a secure local control loop can improve the resilience of the system. When the number of attacks is smaller than a threshold, we propose an efficient algorithm inspired from techniques in compressed sensing to estimate the state of the plant despite attacks. We give a theoretical characterization of the performance of this algorithm and we show on numerical simulations that the method is promising and allows to reconstruct the state accurately despite attacks. Finally, we consider the problem of designing output-feedback controllers that stabilize the system despite sensor attacks. We show that a principle of separation between estimation and control holds and that the design of resilient output feedback controllers can be reduced to the design of resilient state estimators.
  14. Download: on Arxiv 
    We consider the source-channel separation architecture for lossy source coding in communication networks. It is shown that the separation approach is optimal in two general scenarios and is approximately optimal in a third scenario. The two scenarios for which separation is optimal complement each other: the first is when the memoryless sources at source nodes are arbitrarily correlated, each of which is to be reconstructed at possibly multiple destinations within certain distortions, but the channels in this network are synchronized, orthogonal, and memoryless point-to-point channels; the second is when the memoryless sources are mutually independent, each of which is to be reconstructed only at one destination within a certain distortion, but the channels are general, including multi-user channels, such as multiple access, broadcast, interference, and relay channels, possibly with feedback. The third scenario, for which we demonstrate approximate optimality of source-channel separation, generalizes the second scenario by allowing each source to be reconstructed at multiple destinations with different distortions. For this case, the loss from optimality using the separation approach can be upper-bounded when a difference distortion measure is taken, and in the special case of quadratic distortion measure, this leads to universal constant bounds.
  15. Download: lattice_qmf.pdf 
    Recently, a new relaying strategy, quantize-map-and-forward (QMF) scheme, has been demonstrated to approximately achieve (within an additive constant number of bits) the Gaussian relay network capacity, universally, i.e., for arbitrary topologies, channel gains, and SNRs. This was established using Gaussian codebooks for transmission and random mappings at the relays. In this paper, we develop structured lattice codes that implement the QMF strategy. The main result of this paper is that such structured lattice codes can approximately achieve the Gaussian relay network capacity universally, again within an additive constant. In addition, we establish a similar result for half-duplex networks, where we demonstrate that one can approximately achieve the capacity using fixed transmit-receive (TX-RX) schedules for the relays with no transmit power optimization across the different TX-RX states of the network.
  16. Download: on Arxiv 
    We consider the problem of distributed computation of a target function over a two-user deterministic multiple-access channel. If the target and channel functions are matched (i.e., compute the same function), significant performance gains can be obtained by jointly designing the communication and computation tasks. However, in most situations there is mismatch between these two functions. In this work, we analyze the impact of this mismatch on the performance gains achievable with joint communication and computation designs over separation-based designs. We show that for most pairs of target and channel functions there is no such gain, and separation of communication and computation is optimal.
  17. Download: on Arxiv 
    We consider the Gaussian “diamond” or parallel relay network, in which a source node transmits a message to a destination node with the help of N relays. Even for the symmetric setting, in which the channel gains to the relays are identical and the channel gains from the relays are identical, the capacity of this channel is unknown in general. The best known capacity approximation is up to an additive gap of order N bits and up to a multiplicative gap of order N2, with both gaps independent of the channel gains. In this paper, we approximate the capacity of the symmetric Gaussian N-relay diamond network up to an additive gap of 1.8 bits and up to a multiplicative gap of a factor 14. Both gaps are independent of the channel gains and, unlike the best previously known result, are also independent of the number of relays N in the network. Achievability is based on bursty amplify-and-forward, showing that this simple scheme is uniformly approximately optimal, both in the low-rate as well as in the high-rate regimes. The upper bound on capacity is based on a careful evaluation of the cut-set bound. We also present approximation results for the asymmetric Gaussian N-relay diamond network. In particular, we show that bursty amplify-and-forward combined with optimal relay selection achieves a rate within a factor O(log4(N)) of capacity with preconstant in the order notation independent of the channel gains.
  18. Download: suc_dec_ic.pdf 
    In this paper, we investigate the maximum achievable sum-rate of the two-user Gaussian interference channel with Gaussian superposition coding and successive decoding. We first examine an approximate deterministic formulation of the problem, and introduce the complementarity conditions that capture the use of Gaussian coding and successive decoding. In the deterministic channel problem, we find the constrained sum-capacity and its achievable schemes with the minimum number of messages, first in symmetric channels, and then in general asymmetric channels. We show that the constrained sum-capacity oscillates as a function of the cross link gain parameters between the information theoretic sum-capacity and the sum-capacity with interference treated as noise. Furthermore, we show that if the number of messages of either of the two users is fewer than the minimum number required to achieve the constrained sum-capacity, the maximum achievable sum-rate drops to that with interference treated as noise. We provide two algorithms to translate the optimal schemes in the deterministic channel model to the Gaussian channel model. We also derive two upper bounds on the maximum achievable sum-rate of the Gaussian Han-Kobayashi schemes, which automatically upper bound the maximum achievable sum-rate using successive decoding of Gaussian codewords. Numerical evaluations show that, similar to the deterministic channel results, the maximum achievable sum-rate with successive decoding in the Gaussian channels oscillates between that with Han-Kobayashi schemes and that with single message schemes.
  19. Download: on Arxiv 
    Systems that employ network coding for content distribution convey to the receivers linear combinations of the source packets. If we assume randomized network coding, during this process, the network nodes collect random subspaces of the space spanned by the source packets. We establish several fundamental properties of the random subspaces induced in such a system and show that these subspaces implicitly carry topological information about the network and its state that can be passively collected and inferred. We leverage this information toward a number of applications that are interesting in their own right, such as topology inference, bottleneck discovery in peer-to-peer systems, and locating Byzantine attackers. We thus argue that randomized network coding, apart from its better known properties for improving information delivery rate, can additionally facilitate network management and control.
  20. Download: secret_keygen.pdf 
    We study the secret-key capacity in a joint source-channel coding setup-the terminals are connected over a discrete memoryless channel and have access to side information, modelled as a pair of discrete memoryless source sequences. As our main result, we establish the upper and lower bounds on the secret-key capacity. In the lower bound expression, the equivocation terms of the source and channel components are functionally additive even though the coding scheme generates a single secret-key by jointly taking into account the source and channel equivocations. Our bounds coincide, thus establishing the capacity, when the underlying wiretap channel can be decomposed into a set of independent, parallel, and reversely degraded channels. For the case of parallel Gaussian channels and jointly Gaussian sources we show that Gaussian codebooks achieve the secret-key capacity. In addition, when the eavesdropper also observes a correlated side information sequence, we establish the secret-key capacity when both the source and channel of the eavesdropper are a degraded version of the legitimate receiver. We finally also treat the case when a public discussion channel is available, propose a separation based coding scheme, and establish its optimality when the channel output symbols of the legitimate receiver and eavesdropper are conditionally independent given the input.
  21. Download: on Arxiv 
    We provide a complete characterization of the achievable distortion region for the problem of sending a bivariate Gaussian source over bandwidth-matched Gaussian broadcast channels, where each receiver is interested in only one component of the source. This setting naturally generalizes the simple single Gaussian source bandwidth-matched broadcast problem for which the uncoded scheme is known to be optimal. We show that a hybrid scheme can achieve the optimum for the bivariate case, but neither an uncoded scheme alone nor a separation-based scheme alone is sufficient. We further show that in this joint source channel coding setting, the Gaussian scenario is the worst scenario among the sources and channel noises with the same covariances.
  22. Abstract:
    In this paper we study two-stage Gaussian relay-interference networks where there are weak cross-links, causing the networks to behave like a chain of Z Gaussian channels. Our main result is an approximate characterization of the capacity region for such networks. We propose a new interference management scheme, termed interference neutralization, which is implemented using structured lattice codes. This scheme allows for over-the-air interference removal, without the transmitters having complete access the interfering signals.
  23. Download: on Arxiv 
  24. Abstract:
    We show that the diversity-multiplexing tradeoff in fading inter-symbol interference (ISI) channels with a single degree of freedom (MISO/SIMO) is successively refinable. This demonstrates that ideal opportunistic codes can be designed asymptotically in SNR.
  25. Abstract:
    This paper approximately resolves the information flow over wireless (Gaussian) relay networks to within a constant number of bits. It introduced the linear deterministic model and established a max-flow min-cut result for linear deterministic networks. The insights from the deterministic approach led to the approximate max-flow min-cut characterization for noisy Gaussian networks, through the introduction of a new relaying strategy called quantize-map-forward (QMF).
  26. Abstract:
    We propose a channel model for the non-coherent network coding introduced by Koetter and Kschischang. The model captures the essence of such a network operation, and we use it to calculate the capacity of non-coherent network codes as a function of network parameters. We prove that use of subspace coding is optimal, and show that, in some cases, the capacity-achieving distribution uses subspaces of several dimensions, where the employed dimensions depend on the packet length.
  27. Abstract:
    We show that source-channel separation is approximately optimal for transmitting a Gaussian source over a bandwidth mismatched Gaussian channel, for quadratic distortion measures. Furthermore, we show that the results can be extended to general broadcast channels, and the performance of the source-channel separation based approach is also within the same constant multiplicative factors of the optimum.
  28. Download: asymmd.pdf on Arxiv 
    This paper introduces the asymmetric multi-level lossless data compression problem and gives a complete characterization for the three-description version. It then uses insights from this characterization to provide an approximate characterization for the 3-description asymmetric multiple description problem.
  29. Abstract:
    In a significant class of sensor-network applications, the identities of the reporting sensors constitute the bulk of the communicated data, whereas the message itself can be as small as a single bit. or to track incremental environmental changes at fixed locations. In such scenarios, the traditional network-protocol paradigm of separately specifying the source identity and the message in distinct fields leads to inefficient communication. This work addresses the question of how communication should happen in such identity-aware sensor networks.
  30. Abstract:
    We study end-to-end network utility maximization (NUM) approach to allocate resources to multiple flows, each encoding multiple description data compression streams, by taking into account the end-to-end distortion measures.
  31. Abstract:
    Approximately solves symmetric Gaussian multiple description problem to within a bit, by sandwiching the MD rate region between two polytopes separated by at most a fraction of a bit.
  32. Abstract:
    We characterize the rate region of the two-description multiple description coding for stationary Gaussian sources under the squared error distortion measure.
  33. Download: lccdfinal.pdf 
    This paper studies how to use the NUM framework in conjunction with diversity embedded codes to allow multiple streams with different QoS requirements to share wireless links.
  34. J. Goseling, C. Fragouli, and S. N. Diggavi, "Network Coding for Undirected Information Exchange," IEEE Communication Letters, vol. 13, iss. 1, pp. 25-27, 2009.
  35. Abstract:
    We introduce the problem of side-information scalable data compression In this problem, the encoder constructs a progressive description, such that the receiver with high quality side information will be able to truncate the bit-stream and reconstruct in the rate distortion sense, while the receiver with low quality side information will have to receive further data in order to decode. We provide a complete characterization of the rate distortion region for the important quadratic Gaussian case with multiple jointly Gaussian side-informations, where the side information quality does not have to be monotonic along the scalable coding order. Inner and outer bounds are provided to the rate distortion region for general discrete memoryless sources.
  36. Abstract:
    This paper introduces the problem of diversity embedded codes for inter-symbol interference (ISI) channels and gives algebraic constructions for them. These constructions are based on designing binary rank-distance codes with a specific (Toeplitz-like) constraint and lifting them to the complex domain through set-partitioning maps. As a special case these algebraic constructions also give rate-diversity optimal codes for transmission over ISI channels when there are transmit alphabet constraints.
  37. Abstract:
    We consider the problem of transmitting a Gaussian source on a slowly fading Gaussian channel, subject to the mean squared error distortion measure. We propose an efficient algorithm to compute the optimal expected distortion at the receiver in linear time O(M), when the total number of possible discrete fading states is M. We also provide a derivation of the optimal power allocation when the fading state is a continuum, using the classical variational method.
  38. Download: ddac.pdf 
    This paper develops in a unified way the theory for diversity embedded codes for broadband (ISI) channels, both from an information theory viewpoint as well as an algebraic coding perspective. It also develops practical aspects by connecting it to unequal error protection for image transmission as well as using diversity embedded codes in conjunction with NUM.
  39. Abstract:
    We study the multi-user successive refinement problem (posed in Pradhan and Ramchandran, 2002), where the users are connected to a central server through links with different noiseless capacities. Each user requires to reconstruct the source in a scalable manner. We provide the best known achievable strategy for the two-user, two-layer case and the complete characterization of the rate-distortion region for the Gaussian source under the mean-squared error (MSE) distortion measure.
  40. Abstract:
    This paper introduces diversity embedded codes, which are space-time codes that simultaneously give different levels of diversity protection to different information streams. The paper provides algebraic constructions based on binary codes designed for rank distance and lifts them to the complex domain. It also gives several example of linear diversity embedded codes.
  41. Abstract:
    This solves an open problem (posed by Steinberg and Merhav, 2004) on multi-stage successive refinement with side information, when successive stages are for decoders with improving quality side-information. In solving this problem, we identified the general notion of successive refinability of data compression with side-information. A source-channel separation theorem is provided when the descriptions are sent over independent channels for the multistage case.
  42. Download: finbuf.pdf 
    This paper was motivated by the transmission of information over finite buffer channels. Analyzing the capacity of such channels naturally led us to the study of deletion channels. In deletion channels, in contrast to erasure channels, symbols of the transmitted sequence are removed, and the receiver does not know which symbols have been deleted. This was a classic problem from the 1960s in the context of modeling synchronization errors. This paper gave the best known (at the time of publication) lower bounds to capacity of deletion channels since the 1960s. It also studied erasure channels with arbitrary memory in the erasure process. It showed that even when the erasure process has memory, feedback does not increase the capacity.
  43. Download: subsp.pdf 
    This paper was motivated by non-coherent space-time codes with fixed transmit alphabet constraints. To obtain maximal diversity order, the subspaces represented by the space-time codeword matrix needs to be non-intersecting. This led to the study of how many non-intersecting subspaces can be constructed from a finite alphabet.
  44. Download: gc.pdf 
    This paper studies the scaling capacity of asymptotically large wireless networks. It shows that even restricted one-dimensional mobility allows the total capacity of the wireless network scales linearly with the number of nodes. This implies that per-node capacity scales as a constant, demonstrating that even restricted mobility can be used to provide non-diminishing throughput for large-scale wireless networks. This is demonstrated by utilizing the multi-user diversity which is instantiated through node-mobility.
  45. Download: quatstbc_final.pdf 
  46. Download: dimacs.pdf 
    This studied the online scheduling problem of allocating time or frequency slots to multiple users in a wireless broadcast channel. The study was from a CS algorithms viewpoint, with criteria such as delay (average/maximal) and stretch (relative delay). We gave a resource-augmented competitive analysis of many scheduling algorithms, and demonstrated that a small amount of overprovisioning (resource-augmentation) will make the scheduling algorithms competitive to the off-line optimal, even for adversarial demand inputs.
  47. Note: This paper won the 2006 IEEE Donald Fink Prize prize paper award, which is an IEEE-wide paper award across all IEEE journals and magazines.
    Download: procieee.pdf 
    Spatial diversity is realized through multiple independently fading transmit/receive antenna paths in single-user communications; through independently fading links in multi-user communications; through multiple independent routing paths in networks. Adopting spatial diversity as a central theme, we study its information-theoretic foundations, then we examine its benefits across the physical (signal transmission/coding and receiver signal processing) and networking (resource allocation, routing, and applications) layers.
  48. Download: tdis.pdf 
    This paper studies time-reversed space-time block codes, which is an extension of the Alamouti code to inter-symbol interference (ISI) channels. We study the algebraic properties of this code by demonstrating that the polynimial matrices representing the time-reversed space-time block codes form a multiplicative group. This property enables us to analyze the diversity (error) performance of a ISI multiple access channel where each user uses such a code. We also study the finite-block length implementation of such codes.
  49. Download: mimo_ofdm.pdf 
    This paper studies the impact of time-variation within a transmission block on multiple-input multiple output (MIMO) OFDM, which is the chosen modulation strategy of 4G wireless systems. We demonstrate how time-variation can lead to inter-carrier interference, and give algorithms that can mitigate its effects. A central challenge is how to estimate the channel, when it varies within a block. We devise pilot tone placement strategies that enable better channel estimation. We show that in time-varying channels it may be better to group pilot tones together into clumps equispaced onto the FFT grid; this placement technique is in contrast to the common wisdom for time-invariant channels.
  50. S. N. Diggavi, N. Al-Dhahir, A. Stamoulis, and A. R. Calderbank, "Differential Space-Time Transmission for Frequency-Selective Channels," IEEE Communication Letters, vol. 6, iss. 6, pp. 253-255, 2002.
  51. Download: guardtcomm.pdf 
    In block transmission a guard sequence (prefix) is sent to prevent inter-block interference. A cyclic prefix is used in OFDM and an all-zero sequence is used in vector coding.The question we asked is, what should such a sequence be to maximize throughput under the constraint that the sequence itself carries no new information. This paper answers this question by showing that the optimal guard sequence is a linear combination of the information symbols, with the particular optimal combination characterized (depending on the channel and the signal power). Both vector coding and DMT are special cases of this transmission scheme and significant gains in throughput over DMT can be obtained by using such a guard sequence optimization.
  52. Download: mbcjr.pdf 
  53. Download: final_mdc.pdf 
    This designs asymmetric multiple description lattice quantizers, which covers the entire range of the distortion profile, from symmetric to successive refinement. We present a solution to the labeling problem, which is an important part of the construction. We show that this construction is optimal in the high-rate regime, by comparing it to the information-theoretic bounds.
  54. Download: worstnoise.pdf 
    This paper started with a simple question: is the maximum entropy noise the worst noise for additive channels? In the case of scalar channels with a power constraint on the noise, this is true, as is well known. However, we show that in the vector case, with covariance constraints, the answer is yes and no. Yes, if the transmit power is large enough and no otherwise. Along the way we give a solution to the mutual information game with covariance constraints and show that Gaussian solutions form saddle points, but there could also be other saddlepoints. We also demonstrate that the information rates can be achieved using mismatched (Gaussian) decoders.
  55. Download: nbi.pdf 
    Narrowband interference (NBI) could occur in transmission media such as twisted pair or coaxial cable. We analyzed the effect of such interference on the data throughput for finite-blocklength transmission over noisy inter-symbol interference channels. It was shown that the worst narrowband interference spreads its power over the “sweet spots” of the signal (i.e. where the signal puts highest power). More precisely, the auto-correlation matrix of worst-case narrowband (rank-deficient) interference is shown to have the same eigendirections as the signal. Moreover, if the rank of the covariance matrix of the NBI is M
  56. Download: fading.pdf 
    This is an early study of the capacity of MIMO channels inspired by the work of Telatar and Foschini. It shows that the capacity grows linearly in the number of transmit and receive antennas (degrees of freedom) either when the SNR becomes large or when the number of antennas in the MIMO system becomes large. It shows that the linear rate growth can be achieved by simpler linear detector structures, such as a matched filter receiver. However, it shows that the price paid for simple matched filter receivers is that the SNR growth flattens. It also examines the case where the channel matrix has a constant expected Frobenius norm. In this case, even with isotropic fading, it is shown that the capacity of MIMO channels does not grow linear in the number of antennas, but grows linearly in SNR. Finally, the effect of time-variation within a transmission block for ISI fading channels is examined in terms of capacity.
  57. Download: intsup.pdf 
  58. S. N. Diggavi, J. J. Shynk, and N. J. Bershad, "Convergence Models for Rosenblatt's Perceptron Learning Algorithm," IEEE Transactions on Signal Processing, vol. 43, iss. 7, pp. 1696-1702, 1995.
  59. S. N. Diggavi, J. J. Shynk, and A J. Laub, "Direction-of-arrival estimation for a lens-based array," IEEE Transactions on Antennas and Propagation, vol. 42, iss. 5, pp. 666-675, 1994.

Selected conference papers

  1. Download: publications 
    Hierarchical cooperation, introduced by Ozgur, Leveque and Tse showed that linear scaling is possible in wireless network capacity, asymptotically in network size. In this paper, we investigate the impact of absence of channel state information on the performance of hierarchical cooperation. If the product of coherence time and coherence bandwidth of the wireless channel is on the order of the number of nodes in the network, we show that non-coherent hierarchical cooperation achieves the same order rate as the coherent version. If the product is smaller than the number of nodes, we show that non-coherent hierarchical cooperation can still yield sizable gains over multihop communication, but may not achieve the same order rate as the coherent version.
  2. Download: md_itw10.pdf 
    We study the problem where there is a single adversarial node which injects signals to disrupt this communication in a parallel relay network. Like the source, it can only influence the destination through the relays. We develop an approximate characterization of the reliable transmission rate in the presence of such an adversary. A deterministic version of the same problem is solved exactly, yielding insights which are used in the approximate characterization.
  3. Download: tcdsspcom10.pdf 
    We consider the source-channel separation architecture for lossy source coding in communication networks. It is shown that the separation approach is optimal when the memoryless sources at source nodes are arbitrarily correlated, each of which is to be reconstructed at possibly multiple destinations within certain distortions, and the channels in this network are synchronized, orthogonal and memoryless (i.e., noisy graphs).
  4. Download: od_isit10.pdf on Arxiv 
    An approximate max-flow min-cut result for arbitrary wireless relay network was recently established using Gaussian codebooks for transmission and random mappings at the relays. In this paper, we show that the approximation result can be established by using lattices for transmission and quantization along with structured mappings at the relays. This also extended the original scalar quantizer analysis to vector quantizers and obtained a slightly better approximation constant.
  5. Note: Invited paper surveying our results on wireless relay network secrecy.
    Download: pdtizs10.pdf 
  6. Download: pdtisit10.pdf 
    In this paper we consider information-theoretically secure communication between two special nodes (“source” and “destination”) in a memoryless network with authenticated relays, where the secrecy is with respect to a class of eavesdroppers. We develop achievable secrecy rates when authenticated relays also help increase secrecy rate by inserting noise into the network.
  7. Abstract:
    This explores ideas of nearest neighbor search through comparisons. The problem is motivated by the problem of navigating an image database with human assistance. We develop both theoretical bounds, provable algorithms and preliminary experimental results.
  8. Abstract:
    Lossless transmission of a set of correlated sources over a deterministic relay network is considered for two traffic requirements. In distributed multicast, the set of sources are to be delivered to a set of destinations. The source exchange requires all the nodes with access to sources to be able to reconstruct all other sources observed at other nodes. We develop achievable regions and outer bounds for both these situations. For linear deterministic networks, these bounds coincide, yielding a characterization.
  9. Abstract:
    In this paper we consider secret communication between two special nodes (“source” and “destination”) in a wireless network with authenticated relays: the message communicated to the destination is to be kept information-theoretically (unconditionally) secret from any eavesdropper within a class. Since the transmissions are broadcast and interfere with each other, complex signal interactions occur. We develop cooperative schemes which utilize these interactions in wireless communication over networks with arbitrary topology, and give provable unconditional secrecy guarantees.
  10. Abstract:
    The compound wiretap channel generalizes the classical problem in broadcast information-theoretic secrecy by allowing a class of potential eavesdroppers. In this paper we present a new coding scheme that generalizes known approaches to this problem. The scheme prefixes an artificial multiple access channel to the transmission scheme in order to design a structured transmit codebook. The idea is that such a structure can potentially increase the perfect secrecy rate for the legitimate users in the presence of the class of eavesdroppers.
  11. Download: sdfpitw09.pdf 
    Abstract—We consider the two message set problem, where a source broadcasts a common message W1 to an arbitrary set of receivers U and a private message W2 to a subset of the receivers P !U . Transmissions occur over linear deterministic channels. For the case where at most two receivers do not require the private message, we give an exact characterization of the capacity region, where achievability is through linear coding.
  12. Download: pdtencsiisit09.pdf 
    In this paper we find properties that are shared between two seemingly unrelated lossy source coding setups with side-information. The first setup is when the source and sideinformation are jointly Gaussian and the distortion measure is quadratic. The second setup is when the side-information is an erased version of the source. We begin with the observation that in both these cases the Wyner-Ziv and conditional ratedistortion functions are equal. Next, we consider the case when there are two decoders with access to different side-information sources. For the case when the encoder has access to the sideinformation we establish bounds on the rate-distortion function and a sufficient condition for tightness. Under this condition, we find a characterization of the rate-distortion function for physically degraded side-information. This characterization holds for both the Gaussian and erasure setups.
  13. Download: pdt_icc09.pdf 
    We introduce the interference-multiple-access channel, which is a discrete memoryless channel with two transmitters and two receivers, similar to the interference channel. One receiver is required to decode the information encoded at one transmitter, the other receiver is required to decode the messages from both transmitters. We provide an inner bound on the capacity region of this channel, as well as an outer bound for a special class of such channels. For this class, we also quantify the gap between inner and outer bound and show that the bounds match for a semi-deterministic channel, providing a complete characterization. For the Gaussian case, we show that the gap is at most 1 bit, yielding an approximate characterization.
  14. Abstract:
    We ask whether there exist low- overhead schemes for dynamic wireless networks, that produce routes that are within a small constant factor (stretch) of the op- timal route-length. For a class of models for wireless network that ful- fill some mild conditions on the connectivity and on mobility over the time of interest, we can design distributed routing algorithm that maintain the routes over a changing topol- ogy with provable performance guarantees. This scheme needs only node identities and integrates location service along with routing, therefore accounting for the complete overhead.
  15. Download: pdt_allerton08.pdf 
    We study a line network with an eavesdropper having access to the relay transmission. We assume that there could also be a public feedback channel from the destination. We develop achievable strategies to achieve certain rate-equivocation pairs.
  16. Download: degmsgsetbc07.pdf 
    In this paper we study the nested (degraded) message set problem, where user i requires messages W_1, . . . ,W_i. We study this for a MIMO linear deterministic broadcast channel model, which is motivated by some recent successes in using such models to obtain insights into approximate characterizations for the Gaussian relay and interference channels. We establish the complete solution for the K = 3 user nested message problem for the MIMO linear deterministic broadcast channel. We also establish some extremal points for the general K-user case, where there are only two messages of interest.
  17. Download: delubisit07.pdf 
    We present upper bounds on the capacity of the i.i.d. binary deletion channel, where each bit is independently deleted with a fixed probability d. We provide a general approach that gives a numerical answer for fixed d, and provide an argument that gives asymptotic upper bounds as d goes to 1. These appear to be the first non-trivial upper bounds for this probabilistic deletion channel.
  18. Abstract:
    We develop wireless routing based on an embedding of the connectivity graph to overcome shortcomings of geographic routing and topology-based routing.
  19. Note: invited paper
    Download: tdgwita2007.pdf 
  20. Download: db_hbitw06.pdf 
  21. Abstract:
    We investigate source coding in a cascade communication system consisting of an encoder, a relay and an end terminal, where both the relay and the end terminal wish to reconstruct source X with certain fidelities. Additionally, side-informations Z and Y are available at the relay and the end terminal, respectively. The side-information Z at the relay is a physically degraded version of side-information Y at the end terminal. We give an exact characterization for the Gaussian quadratic distortion version of the problem and develop inner and outer bounds for the general case.
  22. Download: digtseitw06.pdf 
    Diversity embedded codes are opportunistic codes which take advantage of good channel realizations while ensuring at least part of the information is received reliably for bad channels. We establish a connection between these codes and degraded message set broadcast codes. We characterize the achievable rate region for the parallel Gaussian degraded message set broadcast problem, when only the strongest user needs the private information. Using this, we partially characterize the set of achievable rate-diversity tuples for the diversity embedded problem for parallel fading channels. This shows that the diversity-multiplexing tradeoff for the parallel fading channel is not successively refinable.
  23. Download: sucrefisit05.pdf 
    This paper shows that the diversity multiplexing tradeoff for flat fading channels with a single degree of freedom (MISO/SIMO) is successively refinable.
  24. Download: strmtch.pdf 
    Inspired by the combinatorial denoising method DUDE, we present efficient algorithms for implementing this idea for arbitrary contexts or for using it within subsequences. We also propose effective, efficient denoising error estimators so we can find the best denoising of an input sequence over different context lengths. Our methods are simple, drawing from string matching methods and radix sorting. We also present experimental results of our proposed algorithms.
  25. Download: mdsi.pdf 
    We formulate a multi-terminal source coding problem, where we are required to construct a multiple description source code for a source sequence when side information about dependent random processes is available at the decoder only, or at both the decoder and the encoder. We describe an achievable rate-distortion region for these problems. In the quadratic Gaussian case, and when there is common side information among the decoders, we show that the rate region when both the encoder and decoder have access to the side information coincides with that of decoder–only side information. This is analogous to the single-description (Wyner-Ziv) case, and an explicit characterization of the rate-distortion region is provided for this case.
  26. Download: lhp.pdf 
    Implementing end-to-end TCP in wireless networks faces two problems. First, it is well known that TCP can not distinguish packet losses due to link failures and that due to network congestion. Second, TCP congestion control mechanism does not deal effectively with large amount of out-oforder packet retransmissions; this problem has received less attention in literature. In this paper, we present solutions to both these problems. In particular, we present a Link-Layer Header Protection (LHP) protocol which implements Explicit Loss Notification (ELN) in a simple, scalable manner, addressing the first problem. We also modify the congestion control mechanism to incorporate knowledge of ELN and packet loss pattern into retransmission decisions, solving the second problem. We combine both these solutions with TCP to present scalable, reliable end-to-end wireless transport protocol.
  27. Download: allerton01.pdf 
    This paper develops the best known (at the time of publication) capacity lower bounds to the deletion channel since the 1960s. It also makes a connection between deletion channels and the well studied problem of the length of the longest common subsequence. It shows that the capacity of the deletion channel for large alphabet size is close to the corresponding erasure channel, though the coding schemes for the two channels are drastically different.
  28. Download: multiuserdmt.pdf 
    In this paper we propose a multiuser DMT scheme for use in a frequency dispersive multiple access channel. We formulate the problem as an optimization problem for maximizing the rate-sum or a weighted sum of the rates. We establish the rate-sum maximizing solution which is a multiuser waterfilling scheme over the DMT tones. We propose a multiuser bit-loading algorithm which finds the rate-maximizing solution in a finite number of steps.
  29. Download: icc95.pdf 
  30. Download: asil94.pdf 
    This was among the first papers to develop statistical models for multiple antenna wireless channels. It extends the well accepted fading models for single-antenna channels to multiple antennas by incorporating antenna response and geometry.

For all material posted on this page: This material is presented to ensure timely dissemination of scholarly and technical work. All persons copying this material are expected to adhere to the terms and constraints invoked by the copyright holder. In most cases, these works may not be reposted without the explicit permission of the copyright holder.