Fault-Tolerant and 3-Dimensional Distributed Topology Control Algorithms in Wireless Multi-hop Networks

The topology of a multi-hop wireless network can be controlled by varying the transmission power at each node. The life-time of such networks depends on battery power at each node. This paper presents a distributed fault-tolerant topology control algorithm for minimum energy consumption in multi-hop wireless networks. This algorithm is an extension of cone-based topology control algorithm [19, 12]. The main advantage of this algorithm is that each node decides on its power based on local information about the relative angle of its neighbors and as a result of these local decisions, a fault-tolerant connected network is formed on the nodes. It is done by preserving the connectivity of a network upon failing of, at most, k nodes (k is a constant) and simultaneously minimize the transmission power at each node to some extent. In addition, simulations are studied to support the effectiveness of this algorithm. Finally, it is shown how to extend this algorithm to 3-dimensions. An extended abstract version of this paper appeared in the 11th IEEE International Conference on Computer Communications and Networks(ICCCN02). Mohsen Bahramgiri born in 1979, recieved the Bachelor's degree in Mathematical Sciences from Sharif University of Technology, Tehran, Iran in 2000. He is now a PhD candidate in Mathematics Department at Massachusetts Institute of Technology. His research interests include Symplectic Hodge Theory on Higher dimentional Geometry, Kahler Geometry, Mathematical Physics and Geometric Analysis on one hand, and algorithmic Graph Theory and Combinatorics on the other hand. MohammadTaghi Hajiaghayi received the Bachelor's degree in computer engineering from Sharif University of Technology in 2000. He received the Master's degree in Computer Science from the University of Waterloo in 2001. Since 2001, he is a Ph.D. candidate in Computer Science and Artificial Intelligence Laboratory at the Massachusetts Institute of Technology. During his Ph.D. studies, he also worked at the IBM T.J. Watson Research Center (Department of Mathematical Sciences) and at the Microsoft Research (Theory group). His research interests are algorithmic graph theory, combinatorial optimizations, distributed and mobile computing, computational geometry and embeddings, game theory and combinatorial auctions, and random structures and algorithms. Vahab S. Mirrokni received the Bachelor's degree in computer engineering from Sharif University of Technology, Tehran, Iran in 2001. Since 2001, he is a Ph.D. candidate in Computer Science and Artificial Intelligence Laboratory at the Massachusetts Institute of Technology. During his Ph.D. studies, he also worked at the Bell-Laboratories (Networking Center and Department of Fundamental Mathematics). His research interests include approximation algorithms, combinatorial optimization, computational game theory, mobile computing, network mannagement, and algorithmic graph theory.     

Addressing, distances and routing in triangular systems with applications in cellular networks

Triangular systems are the subgraphs of the regular triangular grid which are formed by a simple circuit of the grid and the region bounded by this circuit. They are used to model cellular networks where nodes are base stations. In this paper, we propose an addressing scheme for triangular systems by employing their isometric embeddings into the Cartesian product of three trees. This embedding provides a simple representation of any triangular system with only three small integers per vertex, and allows to employ the compact labeling schemes for trees for distance queries and routing. We show that each such system with n vertices admits a labeling that assigns O(log ² n) bit labels to vertices of the system such that the distance between any two vertices u and v can be determined in constant time by merely inspecting the labels of u and v, without using any other information about the system. Furthermore, there is a labeling, assigning labels of size O(log n) bits to vertices, which allows, given the label of a source vertex and the label of a destination, to compute in constant time the port number of the edge from the source that heads in the direction of the destination. These results are used in solving some problems in cellular networks. Our addressing and distance labeling schemes allow efficient implementation of distance and movement based tracking protocols in cellular networks, by providing information, generally not available to the user, and means for accurate cell distance determination. Our routing and distance labeling schemes provide elegant and efficient routing and connection rerouting protocols for cellular networks. Victor Chepoi received the M.S. degree in Applied Mathematics and Computer Science from Moldova State University, in 1983, and the PhD degree in Theoretical Computer Science from the Belorussian Academy of Sciences, in 1987. He was an Assistant and then an Associate Professor at the Mathematics and Computer Science Department of Moldova State University from 1987 to 1994. He was awarded the Alexander von Humboldt Shtiftung Fellowship from 1994 to 1995 at the University of Hamburg, Germany. During 1995 to 1997, he was a Visiting Professor at the Laboratoire de Biomathematiques, Universite de la Mediterranee, France. During 1998, he was a Fellow at SFB343 “Diskrete Strukturen in der Mathematik”, University of Bielefeld, Germany. Since September 1998 he has been a Professor of Computer Science at Faculte des Sciences de Luminy, Universite de la Maditerranee, France. His research interests include graph theory and combinatorics, design and analysis of network and graph algorithms, geometry and algorithmics of metric spaces, computational geometry, and approximation algorithms. Feodor F. Dragan received the M.S. degree in Applied Mathematics and Computer Science from Moldova State University, in 1985, and the PhD degree in Theoretical Computer Science from the Belorussian Academy of Sciences, in 1990. He was an Assistant and then an Associate Professor at the Mathematics and Computer Science Department of Moldova State University from 1988 to 1999. From 1994 to 1999, he was on leave of absence and worked in Germany as a Research Associate on a Volkswagen Foundation (VW) project and on a German Research Community (DFG) project. He was also awarded a DAAD Research Fellowship (Germany) from 1994 to 1995. During 1999 to 2000, he was a Research Associate at the Computer Science Department of University of California, Los Angeles. Since August 2000 he has been with Kent State University and he is currently an Associate Professor of Computer Science. He has authored more than 70 refereed scientific publications. His research interests include design and analysis of network algorithms, algorithmic graph and hypergraph theory, computational geometry, VLSI CAD, and combinatorial optimization. Yann Vaxes received the PhD degree in Computer Science from the Universite de la Mediterranee, in 1998. Then, he joined the Computer Science Department of this university as an Assistant Professor. His research interests include design and analysis of network algorithms, algorithmic graph theory and combinatorial optimization.     

Iterative Decoding of Orthogonal Space-Time Coded CPM Systems

We present an iterative decoding/demodulation technique for an orthogonal space-time coded continuous-phase modulation (OST-CPM) system. A low-complexity soft input and soft output (SISO) demodulator is developed based on the bidirectional soft output Viterbi algorithm (BSOVA) for the multiple antennas CPM systems. By taking advantage of the orthogonal structure, the complexity of extrinsic information extraction can be significantly reduced at each iteration.Shengli Fu received the B.S. and M.S. degree in telecommunication engineering from Beijing University of Posts and Telecommunications, Beijing, China, in 1994 and 1997, respectively. In 2000, he enrolled at the Wright State University, Dayton, OH, where he received the M.S. degree in Computer Engineering. He currently pursues his Ph.D. degree in the Department of Electrical and Computer Engineering at the University of Delaware.His research interests include information and coding theory, MIMO wireless communication systems, and acoustic and visual signal processing.Genyuan Wang received B.Sc and MS. degrees in Mathematics from the Shanxi Normal University, Xian, China, in 1985 and 1988, respectively, and his Ph.D. degree in Electrical Engineering from Xidian University, Xian China, in 1998.From July, 1988 to September 1994, he worked at Shanxi Normal University as an Assistant Professor and then an Associate Professor. From September 1994 to May 1998, he worked at Xidian University as a research assistant. Currently, he is Post-Doctoral Fellow at Department of Electrical and Computer Engineering, University of Delaware. His research interests are radar imaging and radar signal processing, adaptive filter, OFDM system, channel equalization and space-time coding.Xiang-Gen Xia (M97,S00) received his B.S. degree in mathematics from Nanjing Normal University, Nanjing, China, and his M.S. degree in mathematics from Nankai University, Tianjin, China, and his Ph.D. degree in Electrical Engineering from the University of Southern California, Los Angeles, in 1983, 1986, and 1992, respectively.He was a Senior/Research Staff Member at Hughes Research Laboratories, Malibu, California, during 1995--1996. In September 1996, he joined the Department of Electrical and Computer Engineering, University of Delaware, Newark, Delaware, where he is a Professor. He was a Visiting Professor at the Chinese University of Hong Kong during 2002–2003. Before 1995, he held visiting positions in a few institutions. His current research interests include space-time coding, MIMO and OFDM systems, and SAR and ISAR imaging. Dr. Xia has over 100 refereed journal articles published, and 6 U.S. patents awarded. He is the author of the book Modulated Coding for Intersymbol Interference Channels (New York, Marcel Dekker, 2000).Dr. Xia received the National Science Foundation (NSF) Faculty Early Career Development (CAREER) Program Award in 1997, the Office of Naval Research (ONR) Young Investigator Award in 1998, and the Outstanding Overseas Young Investigator Award from the National Nature Science Foundation of China in 2001. He also received the Outstanding Junior Faculty Award of the Engineering School of the University of Delaware in 2001. He is currently an Associate Editor of the IEEE Transactions on Mobile Computing, the IEEE Signal Processing Letters, the IEEE Transactions on Signal Processing, the International Journal of Signal Processing, and the EURASIP Journal of Applied Signal Processing. He was a guest editor of Space-Time Coding and Its Applications in the EURASIP Journal of Applied Signal Processing in 2002. He is also a Member of the Signal Processing for Communications Technical Committee and the Sensor Array and Multichannel (SAM) Technical Committee in the IEEE Signal Processing Society.     

Range Assignment for Biconnectivity and k-Edge Connectivity in Wireless Ad Hoc Networks

Depending on whether bidirectional links or unidirectional links are used for communications, the network topology under a given range assignment is either an undirected graph referred to as the bidirectional topology, or a directed graph referred to as the unidirectional topology. The Min-Power Bidirectional (resp., Unidirectional) k-Node Connectivity problem seeks a range assignment of minimum total power subject to the constraint that the produced bidirectional (resp. unidirectional) topology is k-vertex connected. Similarly, the Min-Power Bidirectional (resp., Unidirectional) k-Edge Connectivity problem seeks a range assignment of minimum total power subject to the constraint the produced bidirectional (resp., unidirectional) topology is k-edge connected. The Min-Power Bidirectional Biconnectivity problem and the Min-Power Bidirectional Edge-Biconnectivity problem have been studied by Lloyd et al. [23]. They show that range assignment based the approximation algorithm of Khuller and Raghavachari [18], which we refer to as Algorithm KR, has an approximation ratio of at most 2(2 – 2/n)(2 + 1/n) for Min-Power Bidirectional Biconnectivity, and range assignment based on the approximation algorithm of Khuller and Vishkin [19], which we refer to as Algorithm KV, has an approximation ratio of at most 8(1 – 1/n) for Min-Power Bidirectional Edge-Biconnectivity. In this paper, we first establish the NP-hardness of Min-Power Bidirectional (Edge-) Biconnectivity. Then we show that Algorithm KR has an approximation ratio of at most 4 for both Min-Power Bidirectional Biconnectivity and Min-Power Unidirectional Biconnectivity, and Algorithm KV has an approximation ratio of at most 2k for both Min-Power Bidirectional k-Edge Connectivity and Min-Power Unidirectional k-Edge Connectivity. We also propose a new simple constant-approximation algorithm for both Min-Power Bidirectional Biconnectivity and Min-Power Unidirectional Biconnectivity. This new algorithm applies only to Euclidean instances, but is best suited for distributed implementation. A preliminary version of this work appeared in the proceedings of the 2nd International Conference on AD-HOC Network and Wireless (Adhoc-Now 2003). Research performed in part while visiting the Max-Plank-Institut fur Informatik. Gruia Calinescu is an Assistant Professor of Computer Science at the Illinois Institute of Technology since 2000. He held postdoc or visiting researcher positions at DIMACS, University of Waterloo, and Max-Plank Institut fur Informatik. Gruia has a Diploma from University of Bucharest and a Ph.D. from Georgia Insitute of Technology. His research interests are in the area of algorithms. Peng-Jun Wan has joined the Computer Science Department at Illinois Institute of Technology in 1997 and has been an Associate Professor since 2004. He received his Ph.D. in Computer Science from University of Minnesota in 1997, M.S. in Operations Research and Control Theory from Chinese Academy of Science in 1993, and B.S. in Applied Mathematics from Tsinghua University in 1990. His research interests include optical networks and wireless networks.     

Cycle-Accurate Energy Measurement and Characterization of FPGAs

Field Programmable Gate Arrays (FPGAs) play many important roles, ranging from small glue logic replacement to System-on-Chip (SoC) designs. Nevertheless, FPGA vendors cannot accurately specify the power consumption of their products on device data sheets because the power consumption of FPGAs is strongly dependent on the target circuit, including resource utilization, logic partitioning, mapping, placement and routing. Although major CAD tools have started to report average power consumption under given transition activities, power-efficient FPGA design demands more detailed information about power consumption. In this paper, we introduce an in-house cycle-accurate FPGA energy measurement tool and energy characterization schemes spanning low-level to high-level design. This tool offers all the capabilities necessary to investigate the energy consumption of FPGAs for operation-based energy characterization, which is applicable to high-level and system-wide energy estimation. It also includes features for low-level energy characterization. We compare our tool with Xilinx XPower and demonstrate the state-machine-based energy characterization of an SDRAM controller.The RIACT at Seoul National University provide research facilities for this study. This work was partly supported by the Brain Korea 21 Project.Hyung Gyu Lee received the B.S. degree in Dept. of Computer Engineering from DongGuk University, in 1999, M.S. degree in School of Computer Science and Engineering from Seoul National University, Seoul, Korea, in 2001, and is currently working toward the Ph.D. degree at Seoul National University. His research interests include device-level energy measurement and characterization, system-level low power design and low-power FPGA design.KyungSoo Lee is a M.S. student at the School of Computer Science and Engineering, Seoul National University. He received the B.S. degree in the School of Computer Science and Engineering from Seoul National University, Seoul, Korea, in 2004. He is currently working on low-power systems and embedded systems for his M.S. degree.Yongseok Choi received the B.S. and M.S. degree in the School of Computer Science and Engineering from Seoul National University, Seoul, Korea, in 2000 and 2002, respectively. He is currently working toward the Ph.D. degree in the School of Computer Science and Engineering at Seoul National University. His research interests include embedded systems and low power systems.Naehyuck Chang received his B.S., M.S. and Ph.D. degrees all from Dept. of Control and Instrumentation Engineering, Seoul National University, Seoul, Korea, in 1989, 1992 and 1996, respectively. Since 1997, he has been with School of Computer Science and Engineering, Seoul National University and currently is an Associate Professor. His research interest includes system-level low-power design and embedded systems design.     

Relay sensor placement in wireless sensor networks

This paper addresses the following relay sensor placement problem: given the set of duty sensors in the plane and the upper bound of the transmission range, compute the minimum number of relay sensors such that the induced topology by all sensors is globally connected. This problem is motivated by practically considering the tradeoff among performance, lifetime, and cost when designing sensor networks. In our study, this problem is modelled by a NP-hard network optimization problem named Steiner Minimum Tree with Minimum number of Steiner Points and bounded edge length (SMT-MSP). In this paper, we propose two approximate algorithms, and conduct detailed performance analysis. The first algorithm has a performance ratio of 3 and the second has a performance ratio of 2.5. Xiuzhen Cheng is an Assistant Professor in the Department of Computer Science at the George Washington University. She received her MS and PhD degrees in Computer Science from the University of Minnesota - Twin Cities in 2000 and 2002, respectively. Her current research interests include Wireless and Mobile Computing, Sensor Networks, Wireless Security, Statistical Pattern Recognition, Approximation Algorithm Design and Analysis, and Computational Medicine. She is an editor for the International Journal on Ad Hoc and Ubiquitous Computing and the International Journal of Sensor Networks. Dr. Cheng is a member of IEEE and ACM. She received the National Science Foundation CAREER Award in 2004. Ding-Zhu Du received his M.S. degree in 1982 from Institute of Applied Mathematics, Chinese Academy of Sciences, and his Ph.D. degree in 1985 from the University of California at Santa Barbara. He worked at Mathematical Sciences Research Institutea, Berkeley in 1985-86, at MIT in 1986-87, and at Princeton University in 1990-91. He was an associate-professor/professor at Department of Computer Science and Engineering, University of Minnesota in 1991-2005, a professor at City University of Hong Kong in 1998-1999, a research professor at Institute of Applied Mathematics, Chinese Academy of Sciences in 1987-2002, and a Program Director at National Science Foundation of USA in 2002-2005. Currently, he is a professor at Department of Computer Science, University of Texas at Dallas and the Dean of Science at Xi’an Jiaotong University. His research interests include design and analysis of algorithms for combinatorial optimization problems in communication networks and bioinformatics. He has published more than 140 journal papers and 10 written books. He is the editor-in-chief of Journal of Combinatorial Optimization and book series on Network Theory and Applications. He is also in editorial boards of more than 15 journals. Lusheng Wang received his PhD degree from McMaster University in 1995. He is an associate professor at City University of Hong Kong. His research interests include networks, algorithms and Bioinformatics. He is a member of IEEE and IEEE Computer Society. Baogang Xu received his PhD degree from Shandong University in 1997. He is a professor at Nanjing Normal University. His research interests include graph theory and algorithms on graphs.     

Tightening the upper bound for the minimum energy broadcasting

In this paper we present a new upper bound on the approximation ratio of the Minimum Spanning Tree heuristic for the basic problem on Ad-Hoc Networks given by the Minimum Energy Broadcast Routing (MEBR). We introduce a new analysis allowing to establish a 6.33-approximation ratio in the 2-dimensional case, thus decreasing the previously known 7.6 upper bound [4], almost closing the gap with the lower bound of 6 [12]. Preliminary results concerning this paper appeared in [9]. Michele Flammini received the degree in Computer Science at the University of L’Aquila in 1990 and the Ph.D. degree in Computer Science at the University of Rome “La Sapienza” in 1995. He is full professor at the Computer Science Department of the University of L’Aquila since March 2005. His research interests include algorithms and computational complexity, game theory, communication problems in interconnection networks and routing. He has authored and co-authored more than 70 papers in his fields of interest published in the most reputed international conferences and journals. Ralf Klasing received the PhD degree from the University of Paderborn in 1995. From 1995 to 1997, he was an Assistant Professor at the University of Kiel. From 1997 to 1998, he was a Research Fellow at the University of Warwick. From 1998 to 2000, he was an Assistant Professor at RWTH Aachen. From 2000 to 2002, he was a Lecturer at King’s College London. In 2002, he joined the CNRS as a permanent researcher. From 2002 to 2005, he was affiliated to the laboratory I3S in Sophia Antipolis. Currently, he is affiliated to the laboratory LaBRI in Bordeaux. He has co-authored a Springer Monograph, a book chapter, and has published more than 40 papers in refereed international periodicals. His research interests include Communication Algorithms in Networks, Approximation Algorithms for Combinatorially Hard Problems, Web Graphs and Web Algorithms, and Optimization Problems in Ad-Hoc Wireless Networks. Alfredo Navarra received the degree in Computer Science at the University of L’Aquila in 2000 and the Ph.D. degree in Computer Science at the University of Rome “La Sapienza” in 2004. From 2003 to 2004, he joined the MASCOTTE project team at the INRIA institute of Sophia Antipolis as PhD student and PostDoc for almost two years. In 2005, he was a temporary researcher at the University of L’Aquila. In 2006, he joined the laboratory LaBRI in Bordeaux as PostDoc. His research interests include, algorithms and computational complexity, communication, modelling as well as analysis and experimentation problems on protocols and routing algorithms for interconnaction networks such as Ad Hoc, Wireless, Mobile and Sensor Networks. He has authored and co-authored more than 25 papers in his fields of interest published in the most reputed international conferences and journals. Stéphane Pérennes is a permanent researcher of the French Centre National de la Recherche Scientifique (CNRS). He is affiliated to the MASCOTTE project team at the Institut National de Recherche en Informatique et Automatique (INRIA) of Sophia Antipolis. He has authored and co-authored more than 70 papers in his fields of interest that vary from pure theoretical to applied issues on algorithms and complexity, networking and routing.     

Algorithm design for a class of base station location problems in sensor networks

Base station placement has significant impact on sensor network performance. Despite its significance, results on this problem remain limited, particularly theoretical results that can provide performance guarantee. This paper proposes a set of procedure to design (1− ε) approximation algorithms for base station placement problems under any desired small error bound ε > 0. It offers a general framework to transform infinite search space to a finite-element search space with performance guarantee. We apply this procedure to solve two practical problems. In the first problem where the objective is to maximize network lifetime, an approximation algorithm designed through this procedure offers 1/ε² complexity reduction when compared to a state-of-the-art algorithm. This represents the best known result to this problem. In the second problem, we apply the design procedure to address base station placement problem when the optimization objective is to maximize network capacity. Our (1− ε) approximation algorithm is the first theoretical result on this problem. Yi Shi received his B.S. degree from University of Science and Technology of China, Hefei, China, in 1998, a M.S. degree from Institute of Software, Chinese Academy of Science, Beijing, China, in 2001, and a second M.S. degree from Virginia Tech, Blacksburg, VA, in 2003, all in computer science. He is currently working toward his Ph.D. degree in electrical and computer engineering at Virginia Tech. While in undergraduate, he was a recipient of Meritorious Award in International Mathematical Contest in Modeling and 1997 and 1998, respectively. His current research focuses on algorithms and optimizations for wireless sensor networks, wireless ad hoc networks, UWB-based networks, and SDR-based networks. His work has appeared in journals and highly selective international conferences (ACM Mobicom, ACM Mobihoc, and IEEE Infocom). Y. Thomas Hou received the B.E. degree from the City College of New York in 1991, the M.S. degree from Columbia University in 1993, and the Ph.D. degree from Polytechnic University, Brooklyn, New York, in 1998, all in Electrical Engineering. Since Fall 2002, he has been an Assistant Professor at Virginia Tech, the Bradley Department of Electrical and Computer Engineering, Blacksburg, VA. His current research interests are radio resource (spectrum) management and networking for software-defined radio wireless networks, optimization and algorithm design for wireless ad hoc and sensor networks, and video communications over dynamic ad hoc networks. From 1997 to 2002, Dr. Hou was a Researcher at Fujitsu Laboratories of America, Sunnyvale, CA, where he worked on scalable architectures, protocols, and implementations for differentiated services Internet, service overlay networking, video streaming, and network bandwidth allocation policies and distributed flow control algorithms. Prof. Hou is a recipient of an Office of Naval Research (ONR) Young Investigator Award (2003) and a National Science Foundation (NSF) CAREER Award (2004). He is a Co-Chair of Technical Program Committee of the Second International Conference on Cognitive Radio Oriented Wireless Networks and Communications (CROWNCOM 2007), Orlando, FL, August 1–3, 2007. He also was the Chair of the First IEEE Workshop on Networking Technologies for Software Defined Radio Networks, September 25, 2006, Reston, VA. Prof. Hou holds two U.S. patents and has three more pending. Alon Efrat earned his Bachelor in Applied Mathematics from the Technion (Israel’s Institute of Technology) in 1991, his Master in Computer Science from the Technion in 1993, and his Ph.D in Computer Science from Tel-Aviv University in 1998. During 1998–2000 he was a Post Doctorate Research Associate at the Computer Science Department of Stanford University, and at IBM Almaden Research Center. Since 2000, he is an assistant professor at the Computer Science Department of the University of Arizona. His main research areas are Computational Geometry, and its applications to sensor networks and medical imaging.     

Ant-Based Distributed Topology Control Algorithms for Mobile Ad hoc Networks

By adjusting the transmission power of mobile nodes, topology control aims to reduce wireless interference, reduce energy consumption, and increase effective network capacity, subject to connectivity constraints. In this paper, we introduce the Ant-Based Topology Control (ABTC) algorithm that adapts the biological metaphor of Swarm Intelligence to control topology of mobile ad hoc networks. ABTC is a distributed algorithm where each node asynchronously collects local information from nearby nodes, via sending and receiving ant packets, to determine its appropriate transmission power. The operations of ABTC do not require any geographical location, angle-of-arrival, topology, or routing information, and are scalable. In particular, ABTC attempts to minimize the maximum power used by any node in the network, or minimize the total power used by all of the nodes in the network. By adapting swarm intelligence as an adaptive search mechanism, ABTC converges quickly to a good power assignment with respect to minimization objectives, and adapts well to mobility. In addition, ABTC may achieve common power, or properly assign power to nodes with non-uniform distribution. Results from a thorough comparative simulation study demonstrate the effectiveness of ABTC for different mobility speed, various density, and diverse node distributions.This work is supported in part by National Science Foundation under grant ANI-0240398.Chien-Chung Shen received his B.S. and M.S. degrees from National Chiao Tung University, Taiwan, and his Ph.D. degree from UCLA, all in computer science. He was a research scientist at Bellcore Applied Research working on control and management of broadband networks. He is now an assistant professor in the Department of Computer and Information Sciences of the University of Delaware, and a recipient of NSF CAREER Award. His research interests include ad hoc and sensor networks, control and management of broadband networks, distributed object and peer-to-peer computing, and simulation.Zhuochuan Huang received his B.E. degree in Computer Science and Technology from Tsinghua University, P.R. China, in 1998, and his M.S. degree in Computer Science from University of Delaware in 2000. He is currently a PhD candidate with the Department of Computer and Information Sciences at the University of Delaware. His current research interests include the design and simulation of protocols for mobile ad hoc networks.Chaiporn Jaikaeo received his B.Eng degree in computer engineering from Kasetsart University, Thailand, and his M.S. and Ph.D. degrees in computer and information sciences from the University of Delaware in 1996, 1999 and 2004, respectively. He is currently a lecturer in the Department of Computer Engineering at Kasetsart University. His research interests include unicast and multicast routing, topology control, peer-to-peer computing and network management for mobile wireless ad hoc and sensor networks.     

Graphical properties of easily localizable sensor networks

The sensor network localization problem is one of determining the Euclidean positions of all sensors in a network given knowledge of the Euclidean positions of some, and knowledge of a number of inter-sensor distances. This paper identifies graphical properties which can ensure unique localizability, and further sets of properties which can ensure not only unique localizability but also provide guarantees on the associated computational complexity, which can even be linear in the number of sensors on occasions. Sensor networks with minimal connectedness properties in which sensor transmit powers can be increased to increase the sensing radius lend themselves to the acquiring of the needed graphical properties. Results are presented for networks in both two and three dimensions. B. D. O. Anderson supported by National ICT Australia, which is funded by the Australian Government’s Department of Communications, Information Technology and the Arts and the Australian Research Council through the Backing Australia’s Ability initiative and the ICT Centre of Excellence Program. A. S. Morse supported by US Army Research Office and US National Science Foundation. W. Whiteley supported in part by grants from NSERC (Canada) and NIH (USA). Y. R. Yang supported in part by US National Science Foundation. Brian Anderson is a Distinguished Professor at the Research School of Information Sciences and Engineering, The Australian National University, Australia. Professor Anderson took his undergraduate degrees in Mathematics and Electrical Engineering at Sydney University, and his doctoral degree in Electrical Engineering at Stanford University. He worked in industry in the United States and at Stanford University before serving as Professor of Electrical Engineering at the University of Newcastle, Australia from 1967 through 1981. At that time, he took up a post as Professor and Head of the Department of Systems Engineering at the Australian National University in Canberra, where he was Director of the Research School of Information Sciences and Engineering from 1994 to 2002. For approximately one year to May 2003, he was the inaugural CEO of the newly formed National ICT Australia, established by the Australian Government through the Department of Communications, Information Technology and the Arts and the Australian Research Council under the Information and Communication Technologies Centre of Excellence program. Professor Anderson has served as a member of a number of government bodies, including the Australian Science and Technology Council and the Prime Minister’s Science, Engineering and Innovation Council. He was a member of the Board of Cochlear Limited, the world’s major supplier of cochlear implants from its listing until 2005. He is a Fellow of the Australian Academy of Science and Academy of Technological Sciences and Engineering, the Institute of Electrical and Electronic Engineers, and an Honorary Fellow of the Institution of Engineers, Australia. In 1989, he became a Fellow of the Royal Society, London, and in 2002 a Foreign Associate of the US National Academy of Engineering. He holds honorary doctorates of the Catholic University of Louvain in Belgium, the Swiss Federal Institute of Technology, and the Universities of Sydney, Melbourne and New South Wales. He was appointed an Officer of the Order of Australia in 1993. He was President of the International Federation of Automatic Control for the triennium 1990 to 1993, and served as President of the Australian Academy of Science for four years from 1998 to 2002. Professor Anderson became the Chief Scientist of National ICT Australia in May 2003 and served in that role till September 2006. Tolga Eren received the B.S. degree in electrical engineering from Bilkent University, Ankara, Turkey, the M.S.E.E. degree in electrical engineering from the University of Massachusetts, the M.S. and the Ph.D. degrees in engineering and applied science from Yale University, New Haven, Connecticut, in 1994, 1998, 1999, and 2003, respectively. From October 2003 to July 2005, he was a postdoctoral research scientist at the Computer Science Department at Columbia University in the City of New York. Since September 2005, he has been at the department of Electrical Engineering at Kirikkale University, Turkey. His research interests are multi-agent (multi-robot, multi-vehicle) systems, sensor networks, computer vision, graph theory, and computational geometry. A. Stephen Morse was born in Mt. Vernon, New York. He received a BSEE degree from Cornell University, MS degree from the University of Arizona, and a Ph.D. degree from Purdue University. From 1967 to 1970 he was associated with the Office of Control Theory and Application OCTA at the NASA Electronics Research Center in Cambridge, Mass. Since 1970 he has been with Yale University where he is presently the Dudley Professor of Engineering and a Professor of Computer Science. His main interest is in system theory and he has done research in network synthesis, optimal control, multivariable control, adaptive control, urban transportation, vision-based control, hybrid and nonlinear systems, sensor networks, and coordination and control of large grouping of mobile autonomous agents. He is a Fellow of the IEEE, a Distinguished Lecturer of the IEEE Control System Society, and a co-recipient of the Society’s 1993 and 2005 George S. Axelby Outstanding Paper Awards. He has twice received the American Automatic Control Council’s Best Paper Award and is a co-recipient of the Automatica Theory/Methodology Prize . He is the 1999 recipient of the IEEE Technical Field Award for Control Systems. He is a member of the National Academy of Engineering and the Connecticut Academy of Science and Engineering. Walter Whiteley (B.Sc. 66, Queen’s University at Kingston, Canada) received his Ph.D. in Mathematics from MIT, Cambridge Mass in 1971. He is currently the Director of Applied Mathematics at York University, and a member of the graduate programs in Mathematics, in Computer Science, and in Education. His research focuses on the rigidity and flexibility of systems of geometric constraints (distances, angles, directions, projections, …). Recent work has included applications of this theory to location in networks, control of formations of autonomous agents, built structures in structural engineering, linkages in mechanical engineering, geometric constraints in computational geometry and CAD, and algorithms for protein flexibility in biochemistry. He is also active in geometry education and development of visual reasoning at all levels of mathematics education and in applications of mathematics. Yang Richard Yang received the B.E. degree in Computer Science and Technology from Tsinghua University, Beijing, China, in 1993, and the M.S. and Ph.D. degrees in Computer Science from the University of Texas at Austin in 1998 and 2001, respectively. Since 2001, he has been with the Department of Computer Science, Yale University, New Haven, CT, where currently he is an Associate Professor of Computer Science and Electrical Engineering. His current research interests are in computer networks, mobile computing, and sensor networks. He leads the Laboratory of Networked Systems (LANS) at Yale University.     

Repacking on Demand for Hierarchical Cellular Networks

In mobile telecommunications operation, radio channels are scarce resources and should be carefully assigned. One possibility is to deploy the hierarchical cellular network (HCN). This paper studies a HCN channel assignment scheme called repacking on demand (RoD). RoD was originally proposed for wireless local loop networks. We expend this work to accommodate mobile HCN. A simulation model is proposed to study the performance of HCN with RoD and some previously proposed schemes. Our study quantitatively indicates that RoD may significantly outperform the previous proposed schemes. Hsien-Ming Tsai was born in Tainan, Taiwan, R.O.C., in 1973. He received the double B.S. degrees in Computer Science & Information Engineering (CSIE) and Communication Engineering, the M.S. degree in CSIE, and the Ph.D. degree in CSIE from National Chiao-Tung University (NCTU), Taiwan, in 1996, 1997, and 2002, respectively. He is currently a research specialist in Quanta Research Institute, Quanta Computer Inc. His research interests are in the areas of cellular protocols (UMTS/GPRS/GSM/DECT), cellular multimedia (MPEG-4 Audio/Speech), and embedded systems. He is an IEEE member. Ai-Chun Pang was born in Hsinchu, Taiwan, R.O.C., in 1973. She received the B.S., M.S. and Ph.D. degrees in Computer Science and Information Engineering from National Chiao Tung University (NCTU) in 1996, 1998 and 2002, respectively. She joined the Department of Computer Science and Information Engineering, National Taiwan University (NTU), Taipei, Taiwan, as an Assistant Professor in 2002. Her research interests include design and analysis of personal communications services network, mobile computing, voice over IP and performance modeling. Yung-Chun Lin was born in Kaohsiung, Taiwan, R.O.C., in 1978. He received the B.S. and M.S. degrees in Computer Science and Information Engineering (CSIE) from National Chiao-Tung University (NCTU), Taiwan, in 2001, 2003, respectively. He is currently pursuing the Ph.D. degree in CSIE. His research interests include design and analysis of a personal communications services network, the cellular protocols (UMTS/GPRS/GSM), and mobile computing. Yi-Bing Lin received his BSEE degree from National Cheng Kung University in 1983, and his Ph.D. degree in Computer Science from the University of Washington in 1990. From 1990 to 1995, he was with the Applied Research Area at Bell Communications Research (Bellcore), Morristown, NJ. In 1995, he was appointed as a professor of Department of Computer Science and Information Engineering (CSIE), National Chiao Tung University (NCTU). In 1996, he was appointed as Deputy Director of Microelectronics and Information Systems Research Center, NCTU. During 1997-1999, he was elected as Chairman of CSIE, NCTU. His current research interests include design and analysis of personal communications services network, mobile computing, distributed simulation, and performance modeling. Dr. Lin has published over 150 journal articles and more than 200 conference papers. Lin is an Adjunct Research Fellow of Academia Sinica, and is Chair Professor of Providence University. Lin serves as consultant of many telecommunications companies including FarEasTone and Chung Hwa Telecom. Lin is an IEEE Fellow and an ACM Fellow.     

Scheduling Sleeping Nodes in High Density Cluster-based Sensor Networks

In order to conserve battery power in very dense sensor networks, some sensor nodes may be put into the sleep state while other sensor nodes remain active for the sensing and communication tasks. In this paper, we study the node sleep scheduling problem in the context of clustered sensor networks. We propose and analyze the Linear Distance-based Scheduling (LDS) technique for sleeping in each cluster. The LDS scheme selects a sensor node to sleep with higher probability when it is farther away from the cluster head. We analyze the energy consumption, the sensing coverage property, and the network lifetime of the proposed LDS scheme. The performance of the LDS scheme is compared with that of the conventional Randomized Scheduling (RS) scheme. It is shown that the LDS scheme yields more energy savings while maintaining a similar sensing coverage as the RS scheme for sensor clusters. Therefore, the LDS scheme results in a longer network lifetime than the RS scheme. Jing Deng received the B.E. and M.E. degrees in Electronic Engineering from Tsinghua University, Beijing, P. R. China, in 1994 and 1997, respectively, and the Ph.D. degree in Electrical and Computer Engineering from Cornell University, Ithaca, NY, in 2002. Dr. Deng is an assistant professor in the Department of Computer Science at the University of New Orleans. From 2002 to 2004, he visited the CASE center and the Department of Electrical Engineering and Computer Science at Syracuse University, Syracuse, NY as a research assistant professor, supported by the Syracuse University Prototypical Research in Information Assurance (SUPRIA) program. He was a teaching assistant from 1998 to 1999 and a research assistant from 1999 to 2002 in the School of Electrical and Computer Engineering at Cornell University. His interests include mobile ad hoc networks, wireless sensor networks, wireless network security, energy efficient wireless networks, and information assurance. Wendi B. Heinzelman is an assistant professor in the Department of Electrical and Computer Engineering at the University of Rochester. She received a B.S. degree in Electrical Engineering from Cornell University in 1995 and M.S. and Ph.D. degrees in Electrical Engineering and Computer Science from MIT in 1997 and 2000 respectively. Her current research interests lie in the areas of wireless communications and networking, mobile computing, and multimedia communication. Dr. Heinzelman received the NSF Career award in 2005 for her work on cross-layer optimizations for wireless sensor networks, and she received the ONR Young Investigator award in 2005 for her research on balancing resource utilization in wireless sensor networks. Dr. Heinzelman was co-chair of the 1st Workshop on Broadband Advanced Sensor Networks (BaseNets '04), and she is a member of Sigma Xi, the IEEE, and the ACM. Yunghsiang S. Han was born in Taipei, Taiwan, on April 24, 1962. He received the B.S. and M.S. degrees in electrical engineering from the National Tsing Hua University, Hsinchu, Taiwan, in 1984 and 1986, respectively, and the Ph.D. degree from the School of Computer and Information Science, Syracuse University, Syracuse, NY, in 1993. From 1986 to 1988 he was a lecturer at Ming-Hsin Engineering College, Hsinchu, Taiwan. He was a teaching assistant from 1989 to 1992 and from 1992 to 1993 a research associate in the School of Computer and Information Science, Syracuse University. From 1993 to 1997 he was an Associate Professor in the Department of Electronic Engineering at Hua Fan College of Humanities and Technology, Taipei Hsien, Taiwan. From 1997 to 2004 he was with the Department of Computer Science and Information Engineering at National Chi Nan University, Nantou, Taiwan. He was promoted to Full Professor in 1998. From June to October 2001 he was a visiting scholar in the Department of Electrical Engineering at University of Hawaii at Manoa, HI, and from September 2002 to January 2004 he was the SUPRIA visiting research scholar in the Department of Electrical Engineering and Computer Science and CASE center at Syracuse University, NY. He is now with the Graduate Institute of Communication Engineering at National Taipei University, Taipei, Taiwan. His research interests are in wireless networks, security, and error-control coding. Dr. Han is a winner of 1994 Syracuse University Doctoral Prize. Pramod K. Varshney was born in Allahabad, India on July 1, 1952. He received the B.S. degree in electrical engineering and computer science (with highest honors), and the M.S. and Ph.D. degrees in electrical engineering from the University of Illinois at Urbana-Champaign in 1972, 1974, and 1976 respectively. Since 1976 he has been with Syracuse University, Syracuse, NY where he is currently a Professor of Electrical Engineering and Computer Science and the Research Director of the New York State Center for Advanced Technology in Computer Applications and Software Engineering. His current research interests are in distributed sensor networks and data fusion, detection and estimation theory, wireless communications, intelligent systems, signal and image processing, and remote sensing he has published extensively. He is the author of Distributed Detection and Data Fusion, published by Springer-Verlag in 1997 and has co-edited two other books. Dr. Varshney is a member of Tau Beta Pi and is the recipient of the 1981 ASEE Dow Outstanding Young Faculty Award. He was elected to the grade of Fellow of the IEEE in 1997 for his contributions in the area of distributed detection and data fusion. In 2000, he received the Third Millennium Medal from the IEEE and Chancellor's Citation for exceptional academic achievement at Syracuse University. He serves as a distinguished lecturer for the AES society of the IEEE. He is on the editorial board Information Fusion. He was the President of International Society of Information Fusion during 2001.     

Locating and Bypassing Holes in Sensor Networks

In real sensor network deployments, spatial distributions of sensors are usually far from being uniform. Such networks often contain regions without enough sensor nodes, which we call holes. In this paper, we show that holes are important topological features that need to be studied. In routing, holes are communication voids that cause greedy forwarding to fail. Holes can also be defined to denote regions of interest, such as the “hot spots” created by traffic congestion or sensor power shortage. In this paper, we define holes to be the regions enclosed by a polygonal cycle which contains all the nodes where local minima can appear. We also propose simple and distributed algorithms, the Tent rule and BoundHole, to identify and build routes around holes. We show that the boundaries of holes marked using BoundHole can be used in many applications such as geographic routing, path migration, information storage mechanisms and identification of regions of interest. Qing Fang is currently a Ph.D. student in Department of Electrical Engineering at Stanford University. Her research interests include algorithm, architecture and protocol design for wireless sensor networks and ad hoc communication. She received her MS in Electrical Engineering from University of Texas at Austin in Fall 1995 and worked in the industry as a system software engineer before joining Stanford in 1999. Jie Gao received her Ph.D. degree from department of computer science at Stanford University in 2004 and her B.S. degree from University of Science and Technology of China in 1999. She joined State University of New York, Stony Brook as an assistant professor in Fall 2005. Her research interests are algorithms design and analysis, ad hoc communication and sensor networks and computational geometry. Leonidas J. Guibas heads the Geometric Computation group in the Computer Science Department of Stanford University. He is a member of the Computer Graphics and Artifical Intelligence Laboratories and works on algorithms for sensing, modeling, reasoning, rendering, and acting on the physical world. Professor Guibas’ interests span computational geometry, geometric modeling, computer graphics, computer vision, sensor networks, robotics, and discrete algorithms–-all areas in which he has published and lectured extensively. Leonidas Guibas obtained his Ph.D. from Stanford in 1976, under the supervision of Donald Knuth. His main subsequent employers were Xerox PARC, MIT, and DEC/SRC. He has been at Stanford since 1984 as Professor of Computer Science. At Stanford he has developed new courses in algorithms and data structures, geometric modeling, geometric algorithms, and sensor networks. Professor Guibas is an ACM Fellow.     

Competitive Algorithms for Maintaining a Mobile Center

In this paper we investigate the problem of locating a mobile facility at (or near) the center of a set of clients that move independently, continuously, and with bounded velocity. It is shown that the Euclidean 1-center of the clients may move with arbitrarily high velocity relative to the maximum client velocity. This motivates the search for strategies for moving a facility so as to closely approximate the Euclidean 1-center while guaranteeing low (relative) velocity. We present lower bounds and efficient competitive algorithms for the exact and approximate maintenance of the Euclidean 1-center for a set of moving points in the plane. These results serve to accurately quantify the intrinsic velocity approximation quality tradeoff associated with the maintenance of the mobile Euclidean 1-center. Preliminary versions of some of the results in this paper first appeared in the 4th International ACM Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications (DIAL M for Mobility). This work has been supported by NSERC and MITACS. The work by Michael Segal was supported in part by the Pacific Institute for Mathematical Studies and REMON consortium. Sergey Bereg received Ph.D. degree from Minsk Institute of Mathematics, Belarus in 1992. Dr. Bereg joined the Department of Computer Science at the University of Texas at Dallas in 2002 as an Associate Professor. He was a Visiting Professor at Duke University in 2001–2002. Prof. Bereg’s area of research is in Computational Geometry, Networks and Communications, Computational Biology. He is author of many journal and conference papers. Binay Bhattacharya is a faculty member in the School of Computing Science at Simon Fraser University. His main research interest is in designing and developing geometric algorithms in various application areas. The application areas include, among others, geographical information systems, operations research. David G. Kirkpatrick received his Ph.D. from the University of Toronto in 1974. He has been a faculty member in the Computer Science Department of the University of British Columbia since 1978 (as a Full Professor since 1986). Dr. Kirkpatrick is a founding Fellow of the British Columbia Advanced Systems Institute. His research interests include computational complexity, algorithmic combinatorics and computational geometry. Michael Segal was born at October 12, 1972 in USSR. In 1991 he immigrated to Israel and started to study computer science in Ben-Gurion University of the Negev. He finished his B.Sc., M.Sc. and Ph.D. degrees in 1994, 1997, and 1999, respectively. During a period of 1999–2000 Dr. Michael Segal held a MITACS National Centre of Excellence Postdoctoral Fellow position in University of British Columbia, Canada. Dr. Segal joined the Department of Communication Systems Engineering, Ben-Gurion University, Israel in 2002 where he serves as department’s Chairman. His primary research is algorithms (sequential and distributed), data structures with applications to optimization problems, mobile wireless networks, communications and security.     

A Practical Cross-Layer Mechanism For Fairness in 802.11 Networks

Many companies, organizations and communities are providing wireless hotspots that provide networking access using 802.11b wireless networks. Since wireless networks are more sensitive to variations in bandwidth and environmental interference than wired networks, most networks support a number of transmission rates that have different error and bandwidth properties. Access points can communicate with multiple clients running at different rates, but this leads to unfair bandwidth allocation. If an access point communicates with a mix of clients using both 1 Mb/s and 11 Mb/s transmission rates, the faster clients are effectively throttled to 1 Mb/s as well. This happens because the 802.11 MAC protocol approximate “station fairness”, with each station given an equal chance to access the media. We provide a solution to provide “rate proportional fairness”, where the 11 Mb/s stations receive more bandwidth than the 1 Mb/s stations. Unlike previous solutions to this problem, our mechanism is easy to implement, works with common operating systems and requires no change to the MAC protocol or the stations. Joseph Dunn received an M.S. in computer science from the University of Colorado at Boulder in 2003, and B. S. in coputer science and mathematics from the University of Arizona in 2001. His research interests are in the general area of computer systems, primarily focusing on security and scalability in distributed systems. He is currently working on his Ph.D. in computer science from the University of Colorado at Boulder. Michael Neufeld received a Ph.D. in Computer Science from the University of Colorado at Boulder in December of 2004, having previously received an M.S. in Computer Science from the University of Colorado at Boulder in 2000 and an A.B. in Computer Science from Princeton University in 1993. His research interests are in the general area of computer system, specifically concentrating on wireless networking, software defind/cognitive radio, and streerable antennas. He is currently a postdoc in the Computer Science department at the University of Calorado at Boulder pursuing research related to software defined radio and new MAC protocols for steerable phase array antennas. Anmol Sheth is a Ph.D. student in Computer Science at the University of Colorado at Boulder. He received his B.S. in Computer Science from the University of Pune, India in 2001. He has been co-leading the development of the MANTIS operating system. He has co-authored three papers include MAC layer protocol design, energy-efficient wireless communication, and adapting communications to mobility. Dirk Grunwald received his Ph.D. from the University of Illinois in 1989 and joined the University of Colorado the same year. His work addresses research and teaching in the broad area of “computer systems”, which includes computer architecture, operating systems, networks, and storage systems. His interests also include issues in pervasive computing, novel computing models, and enjoying the mountains. He is currently an Associate Professor in the Department of Computer Science and in Electrical and Computer Engineering and is also the Director of the Colorado Center for Information Storage. John Bennett is a Professor of Computer Science with a joint appointment in Electrical and Computer Engineering at the University of Colorado at Boulder. He also serves as Associate Dean for Education in the College of Engineering and Applied Science. He joined the CU-Boulder faculty in 2000, after serving on the faculty of Rice University for 11 years. While at Rice, Bennett pioneered a course in engineering design for both engineering and non-engineering students that has been emulated at several universities and high schools. In addition to other teaching awards, Bennett received the Keck Foundation National Award for Engineering Teaching Excellence for his work on this course. Bennett received his Ph.D. in 1988 from the University of Washington. Prior to completing his doctoral studies, he was a U.S. Naval Officer for several years and founded and served as President of Pacific Mountain Research, Inc., where he supervised the design and development of a number of commercial computing systems. Bennett's primary research interests are broadly focused in the area of distributed systems, and more narrowly in distributed information management and distributed robotic macrosensors.     

High Performance Wireless Switch Protocol for IEEE 802.11 Wireless Networks

All mobile stations (STAs) in IEEE 802.11 infrastructure wireless local area networks (IWLAN) are coordinated by an access point (AP). Within the 2.4 GHz unlicensed industry, science, and medicine (ISM) band defined in the IEEE 802.11 2.4 GHz physical layer (PHY) specifications, three channels are available for concurrently transferring data packets at the coverage area of an AP. In most of small/medium enterprises or home environments, an AP with one selected channel is sufficient for covering whole service area, but this implies that the radio resources for the remaining two channels are wasted. In order to overcome the drawback, we propose a new and simple media access control (MAC) protocol, named wireless switch protocol (WSP), for increasing the throughput of IEEE 802.11 IWLAN network to support high quality multimedia traffic. This is achieved by allowing any pair of STAs in IWLAN to exchange data packets in one of other idle channels after their handshake with each other in the common channel controlled by AP. Simulation results show that the total network throughput of WSP depends on the time taken by channel switching, and on the ‘Intranet’ and ‘Internet’ traffic distribution, where the Intranet and Internet mean data transmission between STAs in IWLAN and between the STA and wired host, respectively. When all data packets are Intranet traffic and the traffic load is heavy, the ratio of Goodput for the proposed WSP to that of IEEE 802.11 standard approximates 400%. In the worse case of all Internet traffic, the proposed WSP still obtains the similar throughput as that of IEEE 802.11 standard.Jenhui Chen was born on October 12, 1971 in Taipei, Taiwan, Republic of China. He received the Bachelor’s and Ph.D. degree in Computer Science and Information Engineering (CSIE) from Tamkang University in 1998 and 2003, respectively. In the Spring of 2003, he joined the faculty of Computer Science and Information Engineering Department at Chang Gung University and served as the Assistant Professor. He occupies the supervisor of Network Department in the Information Center, Chang Gung University. Dr. Chen once served the reviewer of IEEE Transactions on Wireless Communications, ACM/Kluwer Mobile Networks and Applications (MONET), and Journal of Information Science and Engineering. His main research interests include design, analysis, and implementation of communication and network protocols, wireless networks, milibots, and artificial intelligence. He is a member of ACM and IEEE.Ai-Chun Pang was born in Hsinchu, Taiwan, R.O.C., in 1973. She received the B.S., M.S. and Ph.D. degrees in Computer Science and Information Engineering from National Chiao Tung University (NCTU) in 1996, 1998 and 2002, respectively. She joined the Department of Computer Science and Information Engineering, National Taiwan University (NTU), Taipei, Taiwan, as an Assistant Professor in 2002. Her research interests include design and analysis of personal communications services network, mobile computing, voice over IP, and performance modeling.Shiann-Tsong Sheu received his B.S. degree in Applied Mathematics from National Chung Hsing University in 1990, and obtained his Ph.D. degree in Computer Science from National Tsing Hua University in May of 1995. From 1995 to 2002, he was an Associate Professor at the Department of Electrical Engineering, Tamkang University. Since Feb. 2002, he has become a Professor at the Department of Electrical Engineering, Tamkang University. Dr. Sheu received the outstanding young researcher award by the IEEE Communication Society Asia Pacific Board in 2002. His research interests include next-generation wireless communication, WDM networks and intelligent control algorithms.Hsueh-Wen Tseng received his B.S. degree in electrical engineering from Tamkang University, Taipei country, Taiwan, in 2001 and M.S. degree in electrical engineering from National Taiwan University of Science and Technology, Taipei, Taiwan, in 2003. He is currently pursuing the Ph. D. degree at the Department of Computer Science and Information Engineering, National Taiwan University, Taipei, Taiwan. His research interests include design, analysis and implementation of network protocols and wireless communications.     

Probabilistic Power Management for Wireless Ad Hoc Networks

Extending system lifetime by effectively managing power on participating nodes is critical in wireless ad hoc networks. Recent work has shown that, by appropriately powering off nodes, energy may be significantly saved up to a factor of two, especially when node density is high. Such approaches rely on the selection of a virtual backbone (i.e., a connected dominating set) of the topology to forward ongoing traffic, coupled with algorithms to manually and periodically recompute such a backbone for load balancing purposes. The common drawback of such schemes is the need to involve periodic message exchanges and to make additional restrictive assumptions. This paper presents Odds¹, an integrated set of energy-efficient and fully distributed algorithms for power management in wireless ad hoc networks. Odds build on the observation that explicit and periodic re-computation of the backbone topology is costly with respect to its additional bandwidth overhead, especially when nodes are densely populated or highly mobile. Building on a fully probabilistic approach, Odds seek to make a minimum overhead, perfectly balanced, and fully localized decision on each node with respect to when and how long it needs to enter standby mode to conserve energy. Such a decision does not rely on periodic message broadcasts in the local neighborhood, so that Odds are scalable as node density increases. Detailed mathematical analysis, discussions and simulation results have shown that Odds are indeed able to achieve our objectives while operating in a wide range of density and traffic loads.Zongpeng Li received his B.Engr. in 1999, from Department of Computer Science and Technology, Tsinghua University, China, and his M.S. degree in 2001 from the Department of Computer Science, University of Toronto. He is currently working towards his Ph.D. degree in the Department of Electrical and Computer Engineering, University of Toronto. His research interests include algorithm design and analysis for both wireless and wireline networks.Baochun Li received his B.Engr. degree in 1995 from Department of Computer Science and Technology, Tsinghua University, China, and his M.S. and Ph.D. degrees in 1997 and 2000 from the Department of Computer Science, University of Illinois at Urbana-Champaign. Since 2000, he has been with the Department of Electrical and Computer Engineering at the University of Toronto, where he is an Assistant Professor. In 2000, he was the recipient of the IEEE Communications Society Leonard G. Abraham Award in the Field of Communications Systems. His research interests include network-level and application-level Quality of Service provisioning, application-layer overlay networks, wireless ad hoc networks, and mobile computing.     

Maximizing Lifetime for Data Aggregation in Wireless Sensor Networks

This paper studies energy efficient routing for data aggregation in wireless sensor networks. Our goal is to maximize the lifetime of the network, given the energy constraint on each sensor node. Using linear programming (LP) formulation, we model this problem as a multicommodity flow problem, where a commodity represents the data generated from a sensor node and delivered to a base station. A fast approximate algorithm is presented, which is able to compute (1−ε)-approximation to the optimal lifetime for any ε > 0. Then along this baseline, we further study several advanced topics. First, we design an algorithm, which utilizes the unique characteristic of data aggregation, and is proved to reduce the running time of the fastest existing algorithm by a factor of K, K being the number of commodities. Second, we extend our algorithm to accommodate the same problem in the setting of multiple base stations, and study its impact on network lifetime improvement. All algorithms are evaluated through both solid theoretical analysis and extensive simulation results. Yuan Xue received her B.S. in Computer Science from Harbin Institute of Technology, China in 1994 and her M.S. and Ph.D. in Computer Science from the University of Illinois at Urbana-Champaign in 2002, and 2005. Currently she is an assistant professor at the Department of Electrical Engineering and Computer Science of Vanderbilt University. Her research interests include wireless and sensor networks, mobile systems, and network security. Yi Cui received his B.S. and M.S. degrees in 1997 and 1999, from Department of Computer Science, Tsinghua University, China, and his Ph.D. degree in 2005 from the Department of Computer Science, University of Illinois at Urbana-Champaign. Since then, he has been with the Department of Electrical Engineering and Computer Science at Vanderbilt University, where he is currently an assistant professor. His research interests include overlay network, peer-to-peer system, multimedia system, and wireless sensor network. Klara Nahrstedt (M ' 94) received her A.B., M.Sc degrees in mathematics from the Humboldt University, Berlin, Germany, and Ph.D in computer science from the University of Pennsylvania. She is an associate professor at the University of Illinois at Urbana-Champaign, Computer Science Department where she does research on Quality of Service(QoS)-aware systems with emphasis on end-to-end resource management, routing and middleware issues for distributed multimedia systems. She is the coauthor of the widely used multimedia book ‘Multimedia:Computing, Communications and Applications’ published by Prentice Hall, and the recipient of the Early NSF Career Award, the Junior Xerox Award and the IEEE Communication Society Leonard Abraham Award for Research Achievements, and the Ralph and Catherine Fisher Professorship Chair. Since June 2001 she serves as the editor-in-chief of the ACM/Springer Multimedia System Journal. An erratum to this article is available at .     

Self-management in chaotic wireless deployments

Over the past few years, wireless networking technologies have made vast forays into our daily lives. Today, one can find 802.11 hardware and other personal wireless technology employed at homes, shopping malls, coffee shops and airports. Present-day wireless network deployments bear two important properties: they are unplanned, with most access points (APs) deployed by users in a spontaneous manner, resulting in highly variable AP densities; and they are unmanaged, since manually configuring and managing a wireless network is very complicated. We refer to such wireless deployments as being chaotic. In this paper, we present a study of the impact of interference in chaotic 802.11 deployments on end-client performance. First, using large-scale measurement data from several cities, we show that it is not uncommon to have tens of APs deployed in close proximity of each other. Moreover, most APs are not configured to minimize interference with their neighbors. We then perform trace-driven simulations to show that the performance of end-clients could suffer significantly in chaotic deployments. We argue that end-client experience could be significantly improved by making chaotic wireless networks self-managing. We design and evaluate automated power control and rate adaptation algorithms to minimize interference among neighboring APs, while ensuring robust end-client performance. This work was supported by the Army Research Office under grant number DAAD19-02-1-0389, and by the NSF under grant numbers ANI-0092678, CCR-0205266, and CNS-0434824, as well as by IBM and Intel. Aditya Akella obtained his Ph.D. in Computer Science from Carnegie Mellon University in September 2005. He obtained a B.Tech in Computer Science and Engineering from IIT Madras in May 2000. Currently, Dr. Akella is a post-doctoral associate at Stanford University. He will join the Computer Sciences faculty at the University of Wisconsin-Madison in Fall 2006. Dr. Akella's research interests include Internet Routing, Network Protocol Design, Internet Security, and Wireless Networking. His web page is at . Glenn Judd, is a Computer Science Ph.D. candidate at Carnegie Mellon University. His research interests include wireless networking and pervasive computing. He has an M.S. and B.S. in Computer Science from Brigham Young University. Srinivasan Seshan is currently an Associate Professor and holds the Finmeccanica chair at Carnegie Mellon University’s Computer Science Department. Dr. Seshan received his Ph.D. in 1995 from the Computer Science Department at University of California, Berkeley. From 1995 to 2000, Dr. Seshan was a research staff member at IBM’s T.J. Watson Research Center. Dr. Seshan’s primary interests are in the broad areas of network protocols and distributed network applications. In the past, he has worked on topics such as transport/routing protocols for wireless networks, fast protocol stack implementations, RAID system design, performance prediction for Internet transfers, Web server benchmarking, new approaches to congestion control, firewall design and improvements to the TCP protocol. His current work explores new approaches in overlay networking, sensor networking, online multiplayer games and wide-area Internet routing. His web page is at . Peter Steenkiste is a Professor of Computer Science and of Electrical and Computer Engineering at Carnegie Mellon University. His research interests include networking, distributed systems, and pervasive computing. He received an M.S. and Ph.D. in Electrical Engineering from Stanford University and an Engineering degree from the University of Gent, Belgium. You can learn more about his research from his home page .     

Finding Minimum Energy Disjoint Paths in Wireless Ad-Hoc Networks

We develop algorithms for finding minimum energy disjoint paths in an all-wireless network, for both the node and link-disjoint cases. Our major results include a novel polynomial time algorithm that optimally solves the minimum energy 2 link-disjoint paths problem, as well as a polynomial time algorithm for the minimum energy k node-disjoint paths problem. In addition, we present efficient heuristic algorithms for both problems. Our results show that link-disjoint paths consume substantially less energy than node-disjoint paths. We also found that the incremental energy of additional link-disjoint paths is decreasing. This finding is somewhat surprising due to the fact that in general networks additional paths are typically longer than the shortest path. However, in a wireless network, additional paths can be obtained at lower energy due to the broadcast nature of the wireless medium. Finally, we discuss issues regarding distributed implementation and present distributed versions of the optimal centralized algorithms presented in the paper.Anand Srinivas is currently a PhD candidate in the Laboratory for Information and Decision Systems (LIDS) at MIT. He recieved his Masters of Science in EECS from MIT in 2004, and his Bachelors of Applied Science in Computer Engineering from the University of Toronto in 2001. In 2004 he also received a Masters of Science in Aerospace Engineering from MIT. His current research interests include reliability and energy-efficiency in wireless ad-hoc networks, routing and network optimization, graph theory, and the design of efficient algorithms. E-mail: anand3@mit.eduEytan Modiano received his B.S. degree in Electrical Engineering and Computer Science from the University of Connecticut at Storrs in 1986 and his M.S. and Ph.D. degrees, both in Electrical Engineering, from the University of Maryland, College Park, MD, in 1989 and 1992 respectively. He was a Naval Research Laboratory Fellow between 1987 and 1992 and a National Research Council Post Doctoral Fellow during 1992–1993 while he was conducting research on security and performance issues in distributed network protocols.Between 1993 and 1999 he was with the Communications Division at MIT Lincoln Laboratory where he designed communication protocols for satellite, wireless, and optical networks and was the project leader for MIT Lincoln Laboratory’s Next Generation Internet (NGI) project. He joined the MIT faculty in 1999, where he is presently an Associate Professor in the Department of Aeronautics and Astronautics and the Laboratory for Information and Decision Systems (LIDS). His research is on communication networks and protocols with emphasis on satellite, wireless, and optical networks.He is currently an Associate Editor for Communication Networks for IEEE Transactions on Information Theory and for The International Journal of Satellite Communications. He had served as a guest editor for IEEE JSAC special issue on WDM network architectures; the Computer Networks Journal special issue on Broadband Internet Access; the Journal of Communications and Networks special issue on Wireless Ad-Hoc Networks; and for IEEE Journal of Lightwave Technology special issue on Optical Networks. He is the Technical Program co-chair for Wiopt 2006 and vice- chair for Infocom 2007. E-mail: modiano@mit.edu