Computational Theory of Distributed Sensor Networks (Emphasis on Network Design using Single Aggregation Tree)
Student No.:50
Time:15:00-16:00pm (Mon.)
Instructor:S.S. Iyengar  [Florida International University]
Place:Conference room 4, Floor 2, Jin Chun Yuan West Building
Starting Date:2013-7-1
Ending Date:2013-7-1





We consider the problem of constructing a single spanning tree for the single-sink buy-at-bulk network design problem for doubling-dimension graphs. We compute a spanning tree to route a set of demands along a graph G to or from a designated sink node. The demands could be aggregated at (or symmetrically distributed to) intermediate edges where the fusion cost is specified by a nonnegative concave function f. We describe a novel approach for developing an oblivious spanning tree in the sense that it is independent of the number and location of data sources (or demands) and cost function at the edges. We present a deterministic, polynomial-time algorithm for constructing a spanning tree in low doubling-dimension graphs that guarantees a log3 D-approximation over the optimal cost, where D is the diameter of the graph G. With a constant fusion-cost function, our spanning tree gives an O(log3D)-approximation for every Steiner tree that includes the sink. We also provide a ῼ(logn) lower bound for any oblivious tree in low doubling-dimension graphs. To our knowledge, this is the first paper to propose a single spanning tree solution to the single-sink buy-at-bulk network design problem (as opposed to multiple overlay trees).


Dr. Srivatsan Srinivasagopalan, Dr. Konstantin Busch, Dr. S.S. Iyengar, "An Oblivious Spanning Tree for Single-Sink Buy-at-Bulk in Low Doubling-Dimension Graphs", IEEE Transactions on Computers Vol. 61 Issue 5, May 2012.



About the Speaker:


Professor S.S. Iyengar is the Ryder Distinguished Professor and Director for the School of Computing and Information Sciences, Florida International University, visiting Homi Bhabha Distinguished Professor at IGCAR, Kalpakkam and former Satish Dhawan Professor at Indian Institute of Science (IISc). His publications include 15 authored/edited books and over 500 research papers. His research interests include high-performance algorithms, sensor fusion, and intelligent systems. He has brought over 25 Million dollars during the last 20 years.


He is a Fellow of IEEE, Fellow of ACM, Fellow of AAAS, Member of the European Academy of Sciences and Fellow of SDPS. He is a recipient of IEEE awards, best paper awards, Distinguished Alumnus award of the Indian Institute of Science, Bangalore, and member of European Academy of Sciences. He was awarded the Lifetime Achievement Award in IIT-BHU at the International Conference on Agile Manufacturing Systems 2012. He has served as the editor of several IEEE journals and is the founding editor-in-chief of the International Journal of Distributed Sensor Networks.


He has been nominated for the Member of the National Academy of Inventors this year - 2013.


His research has been funded by NSF, DARPA, Multi-University Research Initiative (MURI Program), ONR, DOE/ORNL, NRL, NASA, US Army Research Office (URO) and various state agencies and companies. He has served on US National Science Foundation and National Institute of Health Panels to review proposals in various aspects of computational science and he is on the board of reviewers for various Computer Science and Engineering programs.


Dr. Iyengar had 50 doctoral and 100 Masters students under his supervision and the legacy of these students can be seen in prestigious Laboratories (JPL, ORNL, LANL, NRL) and universities round the world. He has been the program Chairman of various international conferences.