The Home Page Of Subhas K. Ghosh

To me, it does not seem unlikely that on some shelf of the universe there lies a total book. I pray the unknown gods that some man - even if only one man, and though it have been thousands of years ago! - may have examined and read it. If honor and wisdom and happiness are not for me, let them be for others. May heaven exist though my place be in hell. Let me be outraged and annihilated but may Thy enormous Library be justified, for one instant, in one being.
Jorge Luis Borges
The Library of Babel

Contact:

Subhas Kumar Ghosh, firstname dot k dot lastname at gmail dot com

Research Interests:

My primary area of interest is algorithms and computational complexity theory and in specific are combinatorial optimization and approximation algorithms, randomized algorithms, derandomization in space bounded complexity classes, and exponential time algorithms for satisfiability. I am also interested in various algorithmic problems arising in designing sensor networks, like power assignment, greedy routing, secure data aggregation, and security issues in ad-hoc and sensor networks.

Publications:

Copyright notice: The documents distributed by this serever have been provided as a means to ensure timely dissemination of scholarly and technical work on a non-commercial basis. Copyright © and all rights therein are maintained by the authors or by other copyright holders, notwithstanding that they have offered their works here electronically. It is understood that all persons copying this information will adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holders. ACM published documents are © Copyright 199x by ACM, Inc.; Springer-Verlag published documents are © Springer-Verlag; and IEEE published documents are © 199x IEEE, under these conditions.

With Amitabha Ghosh, A Plan-Commit-Prove Protocol for Secure Verification of Traversal Path , in Proceedings of the 12th IEEE International Conference on Networks (ICON'04), Singapore, pp 458-462, Nov 2004. doi

Abstract: Security is an important issue in wireless sensor networks. With the growing scope of ad-hoc wireless sensor networks, many of its applications require more than just data authentication. The sensor nodes that receive data from other sensor nodes not only need to authenticate the data but also need to trust the associated information. In particular, in this paper we discuss the problem when a mobile node sends data as well as its location information to the static sensor nodes deployed randomly over a two dimensional area. It could be seen, that, a simple data authentication mechanism cannot ensure that the mobile node always provides the correct location information and it does not cheat about the location or the path it has taken for movement. In this paper we provide a ``plan-commit-prove'' protocol for secure verification of location and traversal path claim and analyze the security aspects of the protocol. The mobile node generates a movement plan and broadcasts a commitment to some neighboring nodes; at a later point in time static nodes verify the planed movement claims of the mobile node by sampling the commitments at various points on the path.

With Manik Raina and Ranjeet K. Patro, Routing of mobile agents in a single channel Wireless Sensor Network, in IEEE International Workshop on Sensor Networks and Applications(SNA05).

Abstract:This paper proposes fault tolerant algorithms for routing mobile agents through a homogenous single channel Wireless Sensor Network. The routing algorithms have a property that every sensor in the Wireless sensor network is covered by the itinerant mobile agents. The various algorithms exploit local knowledge alone to make all decisions and do not need any global properties of the Wireless Sensor Network. We present a case for why these algorithms are required. This is followed by theoretical analysis of the problem in the randomly deployed Wireless Sensor Network where we prove the correctness of our algorithms and justify our intuitive insights by mathematical proofs. This is followed by a comparative simulation where our algorithms are simulated and compared on various parameters like energy expenditure, robustness, network lifetime and latency.

With Viswanath Ganapathy, Chandrashekhara Thejaswi and Ranjeet K. Patro, Kolmogorov Complexity of Signals with Finite Rate of Innovation, in 39th Asilomar Conference on Signals, Systems and Computers, October 30 - November 2, 2005, Pacific Grove, California.

Abstract:We consider the class of signals that has finite rate of innovation. There are few fundamental questions associated with such class of signals. One such question is about a generic characterization. In this work we show that the signals which has finite rate of innovation are also algorithmically compressible. This characterization is useful because algorithmic characterization allow us to view such classes of signal from information theoretic point of view. In this work we relate the parametric representation of such signals to their string equivalent, which can be generated by a short program on universal computer or has low Kolmogorov complexity. We show how this characterization applies to signals that have finite number of freedom per unit time, with case studies.

With Ranjeet K. Patro,Indranil Saha, Lokesh Kumar S., Distributed Fault Tolerant Topology Control in Wireless Ad-hoc Sensor Networks, in The third IEEE and IFIP International Conference on wireless and Optical Communications Networks (WOCN 2006).doi

Abstract:Topology control is an important problem in wireless ad-hoc sensor networks. The aim of the topology control is to maintain desired properties of the network topology to improve the performance of networking algorithms (e.g. routing). In this paper, we present a distributed algorithm for assigning minimum possible power to all the nodes in the wireless sensor networks, such that the network is k-connected. Extensive simulation has been performed to prove the optimality of the algorithm.

With Manik Raina, Viswanath Ganapathy, Chandrashekhara Thejaswi and Ranjeet K. Patro, Secure Data Aggregation in Wireless Sensor Networks,in International Symposium on Wireless Pervasive Computing 2006, ISWPC 2006.

Abstract:A scheme is proposed for secure data aggregation in wireless sensor networks. Commitment schemes and a class of functions called quasi commutative functions are used to achieve provably secure data aggregation. Efficient schemes to verify the data aggregation are provided.

With Manik Raina, Viswanath Ganapathy, Chandrashekhara Thejaswi and Ranjeet K. Patro, Secure Group Communication in Wireless Sensor Networks,in International Symposium on Wireless Pervasive Computing 2006, ISWPC 2006.

Abstract:Security is an important issue in ad-hoc, distributed wireless sensor networks. Due to the nature of communication and the kind of data they are going to handle, it is important to have the capability in the network to establish trusted communication. In this paper we address the issues of forming secure multicast group within wireless sensor networks. We describe protocols that establishes a secure multicast group, and distributes a group key by mutually authenticating a group of devices over an open insecure wireless channel. We choose a model where a centralized key distribution authority can not be present to distribute the keys. We choose a conference keying mechanism and extend it with symmetric authentication protocols and a key hierarchy on which group key could be distributed efficiently.

With Manik Raina, Viswanath Ganapathy, Chandrashekhara Thejaswi and Ranjeet K. Patro, Signal Separation using Time Frequency Representation,in The International Conference on Information & Communication Technologies: from Theory to Applications - ICTTA’06.

Abstract: Signals which can be modeled as linear combination of polynomial phase signals appear in several applications including active noise cancellation, communication using chirp modulation, radar etc. In this paper we discuss an approach using optimal time frequency representation and hough transform to separate linear combination polynomial phase signals. Further we also show the performance of our approach using simulation results and the importance of choosing optimal time frequency representation for signal separation.

With Viswanath Ganapathy, Chandrashekhara Thejaswi, Manik Raina and Ranjeet K. Patro, An Estimator for Multi-Sensor Data Fusion, in The IEEE International Conference on Systems, Man, and Cybernetics (IEEE SMC, 2006).

Abstract:In this paper, we examine binary hypothesis testing and parameter estimation problem in a sensor network. We address the problem of detection and also the estimation of the underlying parameter at the fusion center by optimally combining the test statistics sent by different sensors. We make no assumptions on the noise statistics at the sensor nodes except that their first and second order statistics are known. We show that the proposed method is optimal as an estimator as well as a detector.

On Exponential Time Algorithm for k-SAT, in The International Conference on Mathematical Aspects of Computer and Information Sciences (MACIS 2006).

Abstract:In this work we present and analyze an exponential time simple greedy algorithm for finding satisfying assignments of a $k-\CNF$ (propositional formula in conjunctive normal form, and having at most $k$ literals in any clause). Given a $k-\CNF$ formula our algorithm deterministically searches for an isolated assignment if formula has one (an isolated assignment satisfies a formula, and flipping any of its bits produces an unsatisfiable assignment) otherwise produces all possible satisfiable assignments if the input formula is satisfiable. In this work we define a property that any non-trivial $k-\CNF$ formula possesses, and we call it rigidity of a clause. Informally, rigidity of a clause can be defined to be how well connected a clause is to other clauses having same literals. If we satisfy a rigid clause for most of its literals then some of the variables are forced to take fixed values. Since, we can force such property with greedy local assignment and still get a satisfiable assignment; we can prune some of the decision paths in the algorithm and reduce its time complexity.

On Optimality of Key Pre-distribution Schemes for Distributed Sensor Networks, in Third European Workshop on Security and Privacy in Ad hoc and Sensor Networks ESAS 2006.

Abstract:We derive the optimality results for key pre-distribution scheme for distributed sensor networks, and relations between interesting parameters. Namely, given a key-pool of size $n$ we derive the optimal value that is jointly achievable for parameters like, Size optimality: using less memory per node - while supporting large network, Connectivity optimality: possibility of establishing secure communication between any two nodes over short path, and Resiliency optimality: large fraction of network remains working under compromise or node capture. We characterize this relation in graph theoretic framework. Our result shows that the desired graph (a combination of network topology graph on which key-share graph is embedded) must have small clique and independent set and must have high expansion properties, in other words Expander graphs are best suited for forming secure networks.

With Indranil Saha, Lokesh Kumar S., and Ranjeet K. Patro Distributed Fault-Tolerant Topology Control in Static and Mobile Wireless Sensor Networks, accepted for presentation in IEEE/Create-Net The Second International Conference on COMmunication Systems softWAre and middlewaRE, COMSWARE 2007.

Abstract: In wireless sensor networks, minimizing power consumption and at the same time maintaining desired properties in the network topology is of prime importance. In this work, we present a distributed algorithm for assigning minimum possible power to all the nodes in the wireless sensor network, such that the network is K-connected. In this algorithm, a node collects the location and maximum power information from all the nodes in its vicinity, and then it adjusts the powers of the nodes in its vicinity in such a way that it can reach all the nodes in the vicinity through K optimal vertex-disjoint paths. We prove that, if each node maintains K optimal vertex-disjoint paths to all the nodes in its vicinity then the resulting topology is globally K-connected, provided the topology obtained when all nodes transmit with their maximum power Gmax is K-connected. This topology control algorithm has been extended to mobile scenario and the proof of connectivity in the mobile scenario has been presented. Simulation results show that significant power saving can be achieved by using this algorithm.

With Satyajit Banerjee and Atish Dutta Chowdhury A Generalized Approach To Solve Some Important Variants of Weighted Matching Problems, accepted for publication in Mathematics in Computer Science, Birkhäuser.

Abstract: Obtaining a matching in a graph satisfying certain objective is an attractive class of graph algorithms for both theoretical and practical purposes. Matching algorithms has received attention for several decades. However, for certain algorithmic questions regarding matching, we still do not have satisfactory answers. Namely, while there are efficient algorithms to obtain a maximum weight matching, not much is known about the maximum weight maximum cardinality, and maximum cardinality maximum weight matching problems on a general graph. Our contribution in this work is to show that for bounded weight input graphs one can obtain an algorithm for both maximum weight maximum cardinality, and maximum cardinality maximum weight matching by modifying the input and running the existing maximum weight matching algorithm. Also, given current state of the art in maximum weight matching algorithms, we can claim that, for bounded weight input graphs, both maximum weight maximum cardinality, and maximum cardinality maximum weight matching has algorithm of similar complexity, to that of maximum weight matching. Subsequently, we also obtain approximation algorithms for maximum weight maximum cardinality, and maximum cardinality maximum weight matching.

Energy Efficient Broadcast in Distributed Ad-Hoc Wireless Networks, accepted for publication in IEEE International Conference on Computational Science and Engineering (CSE-2008).

Abstract: In this work we present algorithms for \emph{Minimum Energy Consumption Broadcast Subgraph} ($\MECBS$) problem. First, we focus on designing distributed algorithms for $\MECBS$. To our knowledge, this is the first work looking into the aspects of designing a distributed approximation algorithm for the $\MECBS$. Our algorithm has approximation ratio of $2 H_{n-1}$ with time complexity ${\mathcal O}\left(n \cdot \Lambda\left({\mathcal G}\right)\right)$, where $\Lambda\left({\mathcal G}\right)$ denotes the diameter of the communication graph ${\mathcal G}$. Second, we present an improved approximation algorithm for the $\MECBS$ problem with arbitrary asymmetric power requirement having performance ratio $1.5\left(\ln{\left(n-1\right)} + 1\right)$, hence improving all known results for $\MECBS$ problem in most general case. Our improvement in $\MECBS$ problem also implies that there is a $1.5\ln{\left(n-1\right)} + 2.5$ -- approximation algorithm for strong connectivity with asymmetric power requirements.

Distributed Approximation Algorithm for Matching, Submitted.

Abstract: We present a randomized distributed approximation algorithm for maximum matching. Given a graph G = (V;E) with vertex set V , our algorithm (with high probability) approximates maximum matching to within a factor arbitrarily close to 3/2 and has running time of O(log^2 n).

With Koushik Sinha, Satyajit Banerjee and Atish Dutta Chowdhury Efficient Load Balancing on a Cluster for Large Scale Online Video Surveillance, accepted for publication in 10th International Conference on Distributed Computing and Networking (ICDCN-2009). doi: 10.1007/978-3-540-92295-7_54

Timeliness is an important issue for video based surveillance and is often quantified by the delay between the time of availability of image frames from cameras and completion of their processing. Most existing commercial video surveillance systems focus on the issues of efficient storage and retrieval, remote monitoring, data streaming, forensics and limited real-time analysis - but not explicitly on the timeliness issues of large scale online analysis vis-a-vis resource utilization. In this paper we present a new load distribution strategy tailored to real-time, large scale surveillance systems with the objective of providing best effort timeliness of on-line video analysis on a cluster of compute nodes. We propose a novel approach to fine grained load balancing, modeled as a makespan minimization problem to reactively minimize the tardiness of processing individual camera feeds. To the best of our knowledge, ours is the first work of its kind to address the problem of timeliness of online analysis of a large number of cameras without undermining the quality of the surveillance solution. The proposed approach is also robust in the sense that it is dependent neither on the estimates of future loads nor on the worst case execution requirements of the video processing load. Simulation results establish that our approach is an efficient one for online analysis in large scale surveillance scenarios with a reduction in the requirements of compute nodes by nearly a factor of two for a given timeliness factor.

With Indranil Saha, Lokesh Kumar S. and Ranjeet K. Patro Distributed Fault-Tolerant Topology Control in Wireless Sensor Networks, in Springer Journal on Wireless Networks (WINET). doi: 10.1007/s11276-008-0133-2

In wireless multi-hop and ad-hoc networks, minimizing power consumption and at the same time maintaining desired properties in the network topology is of prime importance. In this work, we present a distributed algorithm for assigning minimum possible power to all the nodes in a static wireless sensor network such that the resultant network topology is k -connected. In this algorithm, a node collects the location and maximum power information from all the nodes in its vicinity, and then adjusts the powers of these nodes in such a way that it can reach all of them through k optimal vertex-disjoint paths. The algorithm ensures k -connectivity in the final topology provided the topology induced when all nodes transmit with their maximum power is k - connected. We extend our topology control algorithm from static networks to networks having mobile nodes. We present proof of correctness for our algorithm for both static and the mobile scenario, and through extensive simulation we present its behavior.

With Satyajit Banerjee and Atish Dutta Chowdhury Distributed approximation for maximum weight matching on bounded degree bounded integer weight graphs, in Information Processing Letters Volume 109, Issue 14.

Abstract: In this paper we present a deterministic distributed maximum weight matching algorithms on bounded degree bounded integer weight graphs, having approximation factor to (2/3 − δ), for some 0 < δ < 2/3, and round complexity of O(log( 1/δ ) +log∗ n).

With Koushik Sinha On Convex Greedy Embedding Conjecture for 3-Connected Planar Graphs , accepted for publication in 17th International Symposium on Fundamentals of Computation Theory.

Abstract: In the context of geographic routing, Papadimitriou and Ratajczak conjectured that every $3$-connected planar graph has a greedy embedding (possibly planar and convex) in the Euclidean plane. Recently, greedy embedding conjecture has been resolved, though the construction do not result in a drawing that is planar and convex. In this work we consider the planar convex greedy embedding conjecture and make some progress. We show that in planar convex greedy embedding of a graph, weight of the maximum weight spanning tree ($T$) and weight of the minimum weight spanning tree ($\func{MST}$) satisfies $\WT(T)/\WT(\func{MST}) \leq \left(\card{V}-1\right)^{1 - \delta}$, for some $0 < \delta \leq 1$. In order to present this result we define a notion of weak greedy embedding. For $\beta \geq 1$ a $\beta$--weak greedy embedding of a graph is a planar embedding such that local optima is bounded by $\beta$. We also show that any three connected planar graph has a $\beta$--weak greedy planar convex embedding in the Euclidean plane with $\beta \in [1,2\sqrt{2} \cdot d(G)]$, where $d(G)$ is the ratio of maximum and minimum distance between pair of vertices in the embedding of $G$, and this bound is tight.