Rohit Negi - Research topics

Capacity of ultra-wideband (UWB) ad-hoc networks

In [1], we argued that the well-known Gupta-Kumar result, which proved that for an n node wireless ad hoc random network, the uniform throughput capacity per node r(n) is Theta(1/\sqrt{n \log n}}) , was valid for 'bandwidth-constrained' networks. However, for 'power-constrained' networks, such as ultra-wideband (UWB) networks, where power is at a higher premium than bandwidth, we showed that the uniform throughput per node r(n) is Theta((n\log n)^{(alpha-1)/2}) . Here, alpha is the distance-loss exponent. These bounds demonstrated that in UWB networks, throughput increases with node density n , in contrast to previously published results! This is the result of the large bandwidth, and the assumed power and rate adaptation, which alleviate interference. Thus, the significance of physical layer properties on the capacity of ad-hoc wireless networks was demonstrated. The result also shows that UWB networks are indeed very interesting from the point of view of sharing the wireless medium.
[1] A. Rajeswaran, and R. Negi, "Capacity of power constrained ad hoc networks," Proc. IEEE Infocom, pp. 443-453, Hong Kong, May 2004.

Joint optimization for wireless ad-hoc networks

In wireless ad-hoc networks, there exists strong interdependency between protocol layers, due to the shared wireless medium. Hence we cast the power adaptation (physical layer), scheduling (link layer) and routing (network layer) problems into a joint optimization framework.
We analyze this hard non-convex optimization problem, and obtain a dual form consisting of a series of sub-problems. The sub-problem demonstrates the functionalities of the protocol layers and their interaction. We show that the routing problem may be solved by a shortest path algorithm. In the case of Ultra Wide Band (UWB) networks, the power adaptation & scheduling problem is simplified and may be solved. Thus, an algorithmic solution to the joint problem, in the UWB case, is developed. Comparison of results with the previous information theoretic capacity results on UWB networks [1], demonstrates the importance of this cross-layer optimization framework. For more information, please see the following papers. In particular, [4] validates the interesting claim made in [1], that the capacity of UWB networks increases with node density.
[1] A. Rajeswaran, and R. Negi, "Capacity of power constrained ad hoc networks," Proc. IEEE Infocom, pp. 443-453, Hong Kong, May 2004.
[2] R. Negi, and A. Rajeswaran, "Scheduling and power adaptation for networks in the Ultra Wide Band regime," Proc. IEEE Globecom, pp. 139-145, Dallas, USA, Dec. 2004.
[3] A. Rajeswaran, Gyouhwan Kim, and R. Negi, "A scheduling framework for UWB and cellular networks," in Proc. IEEE/ACM Broadband Networks, pp. 386-395, San Jose, Oct. 2004.
[4] Gyouhwan Kim, A. Rajeswaran, and R. Negi, "Joint power adaptation, scheduling and routing framework for wireless ad-hoc networks," IEEE International Workshop on Signal Processing Advances in Wireless Communications (SPAWC), June 2005.

Detection algorithms for high-density data storage channels

In this project we investigate detection algorithms for high density perpendicular magnetic recording channels. In such channels, transition jitter noise constitutes the dominant noise source. However, existing mathematic models are not accurate enough to characterize the statistics of this noise, resulting in suboptimal design of detection schemes. In this research, we proposed a jitter sensitive detection scheme to avoid this problem. The proposed scheme utilizes directly the physical noise model, where the transition jitter is modeled as the deviation of transition center from its nominal position. A modified Viterbi algorithm is applied to capture the effect of jitters in its trellis construction, and the quantized jitter sequence and recorded bit sequence are estimated jointly based on Maximum-a-Posterior (MAP) criterion. Simulation results show that the Bit-Error-Rate (BER) performance can be improved by using this scheme as compared to that with the state-of-the-art detectors, which suffer from model mismatch. We are currently using the same physical noise model to estimate the statistics of transition jitters with spin stand read back waveform. The result may be used to further improve the detection performance.

Sensor networks and sensing capacity

How many sensors are required to sense an environment to within a desired accuracy? We investigate such limitations on the design of sensor networks for discrete sensor network applications such as distributed detection and classification. By drawing an analogy between sensor networks and channel encoders, we prove a bound on a Shannon capacity-like quantity called the sensing capacity. The sensing capacity characterizes the number of sensors required to sense an environment of a given size to within a desired accuracy. We define and bound the sensing capacity for a simple sensor network model in [1]. We extend this work in [2] to account for sensors with contiguous fields of view and arbitrary sensing functions. In [3] we demonstrate sensing capacity results for a two dimensional environment distributed as a Markov random field. In the future we intend to further explore the connection between sensing and codes by using insights from our theoretical results to develop algorithms that efficiently fuse multiple sensor observations.
[1] Y. Rachlin, R. Negi, and P. Khosla, "Sensing capacity for target detection," in Proc. IEEE Inform. Theory Wksp., Oct. 24-29 2004.
[2] Y. Rachlin, R. Negi, and P. Khosla, "Sensing capacity for discrete sensor network applications," in Proc. Int. Conf. on Information Processing in Sensor Networks (IPSN), 2005.
[3] Y. Rachlin, R. Negi, and P. Khosla, "Sensing capacity for Markov random fields," to appear in Proc. Int. Symposium on Information Theory, 2005.
For more information, please visit: Yaron Rachlin's home page

Scheduling over wireless fading channels

Quality of Service (QoS) guarantees can be provided for time-varying channels (like mobile wireless channels), by considering an idealized queuing system which uses an abstract model for the physical layer. Queuing theory evaluates the performance of the idealized queuing system in terms of queue length or delay experienced by an input unit (bit/packet). Thus, Queuing theory can provision for QoS on wireless links but it ignores the details of physical layer. This approach works in wired networks because the links in wired (computer) networks are very reliable and have high capacity. On the other hand, wireless channels have low reliability and have time-varying signal strength. Severe QoS violations may occur if the physical layer details of the wireless channel are ignored while designing the queuing system.
In [1], we considered a joint queuing/coding system (a queue + server followed by an encoder) that operates on a wireless link. The application of interest was a delay sensitive application which has a hard constraint on the delay. A bit error occurs if either the bit was decoded incorrectly (error due to channel noise) or the bit experienced excessive delay (error due to delay violation). Formally, the problem statement was, given the joint queuing/coding system and a certain maximum tolerable delay, design the system such that the probability of error is minimized. For simplicity, the paper considered a memoryless server model, i.e. the instantaneous server capacity was chosen to be the function of only the current CSI. Thus, the design of the system involved finding the right server capacity function. It was shown through simulations that the joint queuing/coding system performed better than the pure coding system in a variety of scenarios.
[1] R. Negi, and S. Goel, "An information-theoretic approach to queuing in wireless channels with large delay bounds," Proc. IEEE Globecom, pp. 116-122, Dallas, USA, Dec. 2004.
For more information, please visit: Satashu Goel's home page

Protocol design and analysis in ad hoc wireless networks

See the NSF project web-site .

Impact of broadcast nature of wireless communications on security

Wireless channels differ from their wireline counterparts, in the fact that each wireless transmission is heard by (potentially) several, if not all receivers, legitimate or otherwise. Whereas this broadcast nature of the wireless medium has been studied from the point of view of channel capacity, when security considerations become paramount, a whole new set of interesting and crucial issues need to be addressed regarding the broadcast medium. Specifically, the broadcast nature allows jammers to effectively disrupt wireless network communications with clever strategies that use minimal jammer resources. This denial of service can be made catastrophic by utilizing semantic information in the Medium Access Control layer. The broadcast nature also means that eavesdroppers can hear transmissions without much effort, raising privacy concerns. However, at the same time, the broadcast medium allows innovative security measures, such as a recently introduced, innovative, information-theoretically secure, key generation mechanism. This project is investigating denial-of-service at the MAC layer. An intelligent jammer could cleverly utilize the semantics of the data transmission, by interpreting the packet-on-the-air and deciding its relative importance, and carry out a jamming attack at the MAC-layer. In the context of CSMA/CA, the jammer could detect the transmission of valuable RTS control packets, and jam such crucial information-bearing packets, to prevent other users from accessing the channel. Due to the random backoff, this creates a cascade effect, which will waste a large bandwidth. We are investigating intelligent jamming attacks in the link layer, quantifying the loss of throughput caused, and designing protocols which are resistant to such attacks. The project is also investigating the topic of privacy and information-theoretic security in the presence of eavesdroppers. The approach uses multiple antennas and possibly other resources to degrade the eavesdropper's channel, while not affecting the channel of the legitimate receiver. This results in secure communication between the transmitter and the legitimate receiver.
[1] A. Rajeswaran and R. Negi, "DoS attacks on a reservation based MAC protocol," in Proc. IEEE Int. Conference on Communications, Seoul, May 2005.
[2] R. Negi and S. Goel, "Secret Communication using Artificial Noise," to appear in Proc. IEEE Vehicular Tech. Conf, Dallas, Fall 2005.
[3] S. Goel and R. Negi, "Secret Communication in Presence of Colluding Eavesdroppers," to appear in Proc. IEEE Military Communication (MILCOM), Atlantic City, Fall 2005.