Swaminathan Sankararaman

Journal Publications

1. The Resilience of WDM Networks to Probabilistic Geographical Failures
   Pankaj K. Agarwal, Alon Efrat, Shashidhara Ganjugunte, David Hay, Swaminathan Sankararaman and Gil Zussman

   IEEE/ACM Transactions on Networking, Accepted for Publication, 2012.

   Abstract:

   Telecommunications networks, and in particular optical WDM networks, are vulnerable to large-scale failures in their physical infrastructure, resulting from physical attacks (such as an Electromagnetic Pulse attack) or natural disasters (such as solar flares, earthquakes, and floods). Such events happen at specific geographical locations and disrupt specific parts of the network but their effects cannot be determined exactly in advance. Therefore, we provide a unified framework to model network vulnerability when the event has a probabilistic nature, defined by an arbitrary probability density function. Our framework captures scenarios with a number of simultaneous attacks, when network components consist of several dependent sub-components, and in which either a 1+1 or a 1:1 protection plan is in place. We use computational geometric tools to provide efficient algorithms to identify vulnerable points within the network under various metrics. Then, we obtain numerical results for specific backbone networks, demonstrating the applicability of our algorithms to real-world scenarios. Our novel approach allows to identify locations which require additional protection efforts (e.g., equipment shielding). Overall, the paper demonstrates that using computational geometric techniques can significantly contribute to our understanding of network resilience.

   hide details read details
2. Data Transmission and Base-station Placement for Optimizing the Lifetime of Wireless Sensor Networks
   Esther M. Arkin, Alon Efrat, Joseph S. B. Mitchell, Valentin Polishchuk, Srinivasan Ramasubramanian, Swaminathan Sankararaman and Javad Taheri

   Elsevier Ad Hoc Networks, In Press (available on-line), 2011.

   Abstract:

   In this paper, we study the fundamental optimization problem in wireless sensor networks of base-station positioning such that data from the sensors may be transmitted to it in an energy-efficient manner. We primarily consider the setting where a sensor transmits all of its data directly to the base-station or relays it via one other node. This setting provides two benefits: low duty-cycling due to limited synchronization requirements between nodes and low end-to-end delay due to the limited number of hops in the routes. Given the battery limitations of the sensor nodes, our objective is to maximize the network lifetime. First, we present efficient algorithms for computing a transmission scheme for the sensors given a fixed base-station and show how to implement these in a distributed fashion with only a constant number of messages per sensor. Next, we show that the optimization problem for the setting where sensors may transmit data through more than 2 hops is NP-Hard. Finally, we present efficient algorithms for the problem of locating the base-station and simultaneously finding a transmission scheme. We compare our algorithms with linear-programming based algorithms for more general settings through extensive simulations and outline the benefits of the different approaches.

   doi: 10.1016/j.adhoc.2011.09.010

   hide details read details
3. On Channel-Discontinuity-Constraint Routing in Wireless Networks
   Swaminathan Sankararaman, Alon Efrat, Srinivasan Ramasubramanian and Pankaj K. Agarwal

   Elsevier Ad Hoc Networks, In Press (available on-line), 2011.

   Abstract:

   Multi-channel wireless networks are increasingly deployed as infrastructure networks, e.g. in metro areas. Network nodes frequently employ directional antennas to improve spatial throughput. In such networks, between two nodes, it is of interest to compute a path with a channel assignment for the links such that the path and link bandwidths are the same. This is achieved when any two consecutive links are assigned different channels, termed as ``Channel-Discontinuity-Constraint'' (CDC). CDC-paths are also useful in TDMA systems, where, preferably, consecutive links are assigned different time-slots. In the first part of this paper, we develop a \(t\)-spanner for CDC-paths using spatial properties; a sub-network containing \(O(n/\theta)\) links, for any \(\theta>0\), such that CDC-paths increase in cost by at most a factor \(t=(1-2\sin (\theta/2))^{-2}\). We propose a novel distributed algorithm to compute the spanner using an expected number of \(O(n\log n)\) fixed-size messages. In the second part, we present a distributed algorithm to find minimum-cost CDC-paths between two nodes using \(O(n^2)\) fixed-size messages, by developing an extension of Edmonds' algorithm for minimum-cost perfect matching. In a centralized implementation, our algorithm runs in \(O(n^2)\) time improving the previous best algorithm which requires \(O(n^3)\) running time. Moreover, this running time improves to \(O(n/\theta)\) when used in conjunction with the spanner developed.

   doi: 10.1016/j.adhoc.2011.04.011

   hide details read details

Top

Conference/Workshop Publications

1. Efficient Algorithms for Pursuing Moving Evaders in Terrains
   Alon Efrat, Joseph S. B. Mitchell, Parrish Myers and Swaminathan Sankararaman

   Proceedings pf the 20th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (GIS), 2012.

   Abstract:

   We propose algorithms for computing optimal trajectories of a group of flying observers (such as helicopters or UAVs) searching for a lost child in a hilly terrain. Very few assumptions are made about the speed or direction of the child's motion and whether it might (either deliberately or accidentally) try to avoid being found. This framework can also be applied to seekers searching for hostile evaders, such as smugglers/criminals, or friendly evaders, such as lost hikers. Based on the features of the area of the terrain where the pursuit takes place, and the visibility and motion characteristics of the UAVs, we show how to plan their synchronized trajectories in a way that maximizes the likelihood of a successful pursuit, while minimizing their battery or fuel usage, which may, in turn, enable a longer pursuit. Our algorithm explores useful I/O-efficient data structures and branch-cutting (search pruning) techniques to achieve further speedup by limiting the storage requirements and the total number of graph nodes searched, respectively.

   hide details read details
2. Optimization Schemes for Protective Jamming
   Swaminathan Sankararaman, Karim Abu-Affash, Alon Efrat, Sylvester Eriksson-Bique, Valentin Polishchuk, Srinivasan Ramasubramanian and Michael Segal

   Proceedings of the 13th ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc), 2012.

   Abstract:

   In this paper, we study strategies for allocating and managing friendly jammers, so as to create virtual barriers that would prevent hostile eavesdroppers from tapping sensitive wireless communication. Our scheme precludes the use of any encryption technique. Applications include domains such as (i) protecting the privacy of storage locations where RFID tags are used for item identification, (ii) secure reading of RFID tags embedded in credit cards, (iii) protecting data transmitted through wireless networks, sensor networks, etc. By carefully managing jammers to produce noise, we show how to reduce the SINR of eavesdroppers to below a threshold for successful reception, without jeopardizing network performance. We present algorithms targeted towards optimizing power allocation and number of jammers needed in several settings. Experimental simulations back up our results.

   doi: 10.1145/2248371.2248383

   hide details read details
3. Nearest-Neighbor Searching under Uncertainty
   Pankaj K. Agarwal, Alon Efrat, Swaminathan Sankararaman and Wuzhou Zhang

   Proceedings of the 31st ACM Symposium on Principles of Database Systems (PODS), 2012.

   Abstract:

   Nearest-neighbor queries, which ask for returning the nearest neighbor of a query point in a set of points, are important and widely studied in many fields because of a wide range of applications. In many of these applications, such as sensor databases, location based services, face recognition, and mobile data, the location of data is imprecise. We therefore study nearest neighbor queries in a probabilistic framework in which the location of each input point and/or query point is specified as a probability density function and the goal is to return the point that minimizes the expected distance, which we refer to as the expected nearest neighbor (ENN). We present methods for computing an exact ENN or an \(\varepsilon\)-approximate ENN, for a given error parameter \(0\leq \varepsilon\leq 1\), under different distance functions. These methods build an index of near-linear size and answer ENN queries in polylogarithmic or sublinear time, depending on the underlying function. As far as we know, these are the first nontrivial methods for answering exact or \(\varepsilon\)-approximate ENN queries with provable performance guarantees.

   doi: 10.1145/2213556.2213588

   hide details read details
4. Graph-based Iterative Reconstruction of Sparse Signals for Compressed Sensing
   Anantha R. Krishnan, Swaminathan Sankararaman and Bane Vasic

   Proceedings of the 10th International Conference on Telecommunication in Modern Satellite, Cable and Broadcasting Services (TELSIKS), 2011.

   Abstract:

   In this paper, we consider the problem of reconstruction of sparse signals in compressed sensing. In particular, we introduce a novel iterative algorithm based on graph-based decoding of low-density parity-check codes which possesses desirable properties like good performance, low complexity and running time, and ease of implementation. In this work, we outline the reconstruction algorithm, and analyze its performance on some measurement matrices. Furthermore, we also provide some initial results on the theoretical performance limits of this algorithm.

   doi: 10.1109/TELSKS.2011.6112021

   hide details read details
5. The Resilience of WDM Networks to Probabilistic Geographical Failures
   Pankaj K. Agarwal, Alon Efrat, Shashidhara Ganjugunte, David Hay, Swaminathan Sankararaman and Gil Zussman

   Proceedings of the 30th IEEE International Conference on Computer Communications (INFOCOM), 2011.

   Abstract:

   Telecommunications networks, and in particular optical WDM networks, are vulnerable to large-scale failures of their physical infrastructure, resulting from physical attacks (such as an Electromagnetic Pulse attack) or natural disasters (such as solar flares, earthquakes, and floods). Such events happen at specific geographical locations and disrupt specific parts of the network but their effects are not deterministic. Therefore, we provide a unified framework to model the network vulnerability when the event has a probabilistic nature, defined by an arbitrary probability density function. Our framework captures scenarios with a number of simultaneous attacks, in which network components consist of several dependent subcomponents, and in which either a 1+1 or a 1:1 protection plan is in place. We use computational geometric tools to provide efficient algorithms to identify vulnerable points within the network under various metrics. Then, we obtain numerical results for specific backbone networks, thereby demonstrating the applicability of our algorithms to real-world scenarios. Our novel approach allows for identifying locations which require additional protection efforts (e.g., equipment shielding). Overall, the paper demonstrates that using computational geometric techniques can significantly contribute to our understanding of network resilience.

   doi: 10.1109/INFCOM.2011.5934942

   hide details read details
6. Network Vulnerability to Single, Multiple, and Probabilistic Physical Attacks
   Pankaj K. Agarwal, Alon Efrat, Shashidhara Ganjugunte, David Hay, Swaminathan Sankararaman and Gil Zussman

   Proceedings of the 2010 IEEE Military Communications Conference (MILCOM), 2010.

   Abstract:

   Telecommunications networks heavily rely on the physical infrastructure and, are therefore, vulnerable to natural disasters, such as earthquakes or floods, as well as to physical attacks, such as an Electromagnetic Pulse (EMP) attack. Large-scale disasters are likely to destroy network equipment and to severely affect interdependent systems such as the power-grid. In turn, long-term outage of the power-grid might cause additional failures to the telecommunication network. In this paper, we model an attack as a disk around its epicenter, and provide efficient algorithms to find vulnerable points within the network, under various metrics. In addition, we consider the case in which multiple disasters happen simultaneously and provide an approximation algorithm to find the points which cause the most significant destruction. Finally, since a network element does not always fail, even when it is close to the attack's epicenter, we consider a simple probabilistic model in which the probability of a network element failure is given. Under this model, we tackle the cases of single and multiple attacks and develop algorithms that identify potential points where an attack is likely to cause a significant damage.

   doi: 10.1109/MILCOM.2010.5679556

   hide details read details
7. Data Transmission and Base-station Placement for Optimizing Network Lifetime
   Esther M. Arkin, Alon Efrat, Joseph S. B. Mitchell, Valentin Polishchuk, Srinivasan Ramasubramanian, Swaminathan Sankararaman and Javad Taheri

   Proceedings of the 6th ACM SIGACT/SIGMOBILE International Workshop on Foundations of Mobile Computing (DIALM-POMC), 2010.

   Abstract:

   We study the problem of transmitting data from a set of sensors to a base-station where the data is to be gathered. Each sensor continuously generates data and has to transmit it through the network (via other sensor nodes) to the base-station. Considering the battery limitations of the sensors, our goal is to find an optimum location of the base-station and a corresponding data transmission scheme for routing the data from the sensors, such that the network is operating for the longest possible time. We focus mainly on tree networks for 2-level trees, with at most 2 hops from sensor to the base-station. For such networks we give efficient algorithms for forwarding data from sensors to the base-station and for locating the base-station optimally for maximizing network lifetime. Further, we show that determining a transmission protocol for trees with 3 or more levels is NP-hard. We demonstrate the effectiveness of our methods with experimental results on simulated data, comparing our 2-level tree algorithm with methods based on linear programming.

   doi: 10.1145/1860684.1860692

   hide details read details
8. On Channel-Discontinuity-Constraint Routing in Wireless Networks
   Swaminathan Sankararaman, Alon Efrat, Srinivasan Ramasubramanian and Pankaj K. Agarwal

   Proceedings of the 29th IEEE International Conference on Computer Communications (INFOCOM), Mini-Conference, 2010.

   Abstract:

   Multi-channel wireless networks are increasingly being employed as infrastructure networks, e.g. in metro areas. Nodes in these networks frequently employ directional antennas to improve spatial throughput. In such networks, given a source and destination, it is of interest to compute an optimal path and channel assignment on every link in the path such that the path bandwidth is the same as that of the link bandwidth and such a path satisfies the constraint that no two consecutive links on the path are assigned the same channel, referred to as ``Channel Discontinuity Constraint'' (CDC). CDC-paths are also quite useful for TDMA system, where preferably every consecutive links along a path are assigned different time slots. This paper contains several contributions. We first present an \(O(N^2)\) distributed algorithm for discovering the shortest CDC-path between given source and destination. For use in wireless networks, we explain how spatial properties can be used for dramatically expedite the algorithm. This improves the running time of the \(O(N^3)\) centralized algorithm of Ahuja et al. for finding the minimum-weight CDC-path. Our second result is a generalized \(t\)-spanner for CDC-path; For any \(\theta>0\) we show how to construct a sub-network containing only \(O(N/\theta)\) edges, such that that length of shortest CDC-paths between arbitrary sources and destinations increases by only a factor of at most \(1/(1-2\sin (\theta/2))^2\). This scheme can be implemented in a distributed manner with a message complexity of \(O(N\log N)\) and it is highly dynamic, so addition/deletion of nodes are easily handled in a distributed manner. An important conclusion of this scheme is in the case of directional antennas are used. In this case, it is enough to consider only the two closest nodes in each cone.

   doi: 10.1109/INFCOM.2010.5462188

   hide details read details

Top

Manuscripts

1. Computing Similarity between a Pair of Trajectories
   Swaminathan Sankararaman, Pankaj K. Agarwal, Thomas Mølhave and Arnold P. Boedihardjo

   arXiv:1303.1585 [cs.CG], 2013.

   Abstract:

   With recent advances in sensing and tracking technology, trajectory data is becoming increasingly pervasive and analysis of trajectory data is becoming exceedingly important. A fundamental problem in analyzing trajectory data is that of identifying common patterns between pairs or among groups of trajectories. In this paper, we consider the problem of identifying similar portions between a pair of trajectories, each observed as a sequence of points sampled from it.

   We present new measures of trajectory similarity --- both local and global --- between a pair of trajectories to distinguish between similar and dissimilar portions. Our model is robust under noise and outliers, it does not make any assumptions on the sampling rates on either trajectory, and it works even if they are partially observed. Additionally, the model also yields a scalar similarity score which can be used to rank multiple pairs of trajectories according to similarity, e.g. in clustering applications. We also present efficient algorithms for computing the similarity under our measures; the worst-case running time is quadratic in the number of sample points.

   Finally, we present an extensive experimental study evaluating the effectiveness of our approach on real datasets, comparing with it with earlier approaches, and illustrating many issues that arise in trajectory data. Our experiments show that our approach is highly accurate in distinguishing similar and dissimilar portions as compared to earlier methods even with sparse sampling.

   hide details read details
2. Scheduling Sensors for Guaranteed Sparse Coverage
   Swaminathan Sankararaman, Alon Efrat, Srinivasan Ramasubramanian and Javad Taheri

   arXiv:0911.4332 [cs.NI], 2009.

   Abstract:

   Sensor networks are particularly applicable to the tracking of objects in motion. For such applications, it may not necessary that the whole region be covered by sensors as long as the uncovered region is not too large. This notion has been formalized by Balasubramanian et.al. as the problem of \(\kappa\)-weak coverage. This model of coverage provides guarantees about the regions in which the objects may move undetected. In this paper, we analyse the theoretical aspects of the problem and provide guarantees about the lifetime achievable. We introduce a number of practical algorithms and analyse their significance. The main contribution is a novel linear programming based algorithm which provides near-optimal lifetime. Through extensive experimentation, we analyse the performance of these algorithms based on several parameters defined.

   hide details read details

Top

Dissertations/Theses

1. Efficient Geometric Algorithms for Wireless Networks
   Swaminathan Sankararaman

   Ph.D. Dissertation, The University of Arizona, 2011.

   Abstract:

   Wireless communications has a wide range of applications including cellular telephones, wireless networking and security systems. Typical systems work through radio frequency communication and this is heavily dependent on the geographic characteristics of the environment. This dissertation discusses the application of geometric optimization in wireless networks where the communication ``links'' are not static but may be dynamically changing. We show how to exploit the geometric properties of these networks to model their behavior. In the first part of the dissertation, we consider the problem of interference-aware routing in Multi-channel mesh networks employing directional antennas to improve spatial throughput. In such networks, optimal routes are paths with a channel assignment for the links such that the path and link bandwidths are the same. We develop a method to perform topology control while taking into account interference by constructing a spanner; a sub-network containing \(O(n/\theta)\) links, where \(n\) is the network size and \(\theta\) is a tunable parameter, such that path costs increase by at most a constant factor. In second part, we study the problem of base-station positioning in Sensor Networks such that we achieve energy-efficient data transmission from the sensors. Given the battery limitations of the sensors, our objective is to maximize the network lifetime. First, we present efficient algorithms for computing a transmission scheme given a fixed base-station and also provide a distributed implementation. Next, we present efficient algorithms for the problem of locating the base-station and simultaneously finding a transmission scheme. We compare our algorithms with linear-programming based algorithms through simulations. In the third part, we study strategies for managing friendly jammers to create virtual barriers preventing eavesdroppers from tapping sensitive RFID communication. Our scheme precludes the use of encryption. Applications domains include (i) privacy of inventory management systems, (ii) credit card communications, (iii) secure communication in any wireless networks without encryption. By carefully managing jammers producing noise, we show how to degrade the signal at eavesdroppers sufficiently, without jeopardizing network performance. We present algorithms targeted towards optimizing the number and power of jammers. Experimental simulations back up our results.

   hide details read details
2. On Channel-Discontinuity-Constraint Routing in Wireless Networks
   Swaminathan Sankararaman

   M.S. Thesis, The University of Arizona, 2008.

   Abstract:

   Multi-channel wireless networks are increasingly being employed as infrastructure networks in metro areas. In addition, nodes in these networks employ directional antennas to improve spatial throughput. In such networks, given a source and destination, it is of interest to compute an optimal path and channel assignment on every link in the path such that the path bandwidth is the same as that of the link bandwidth and such a path must satisfy the constraint that no two consecutive links on the path are assigned the same channel, referred to as ``Channel Discontinuity Constraint'', CDC. This work presents an efficient distributed algorithm for the problem of finding minimum hop CDC-paths in wireless networks assuming that all the nodes employ the same transmission range. This algorithm is based on Edmonds' algorithm for maximum cardinality matching using an expansion graph on the network known as the Edmonds-Szeider expansion. We show that the message complexity of the algorithm developed in this work is quadratic in the number of nodes in the network.

   hide details read details

Top