Equilibria in Topology Control Games for Ad Hoc Networks

We study topology control problems in ad hoc networks where network nodes get to choose their power levels in order to ensure desired connectivity properties. Unlike most other work on this topic, we assume that the network nodes are owned by different entities, whose only goal is to maximize their own utility that they get out of the network without considering the overall performance of the network. Game theory is the appropriate tool to study such selfish nodes: we define several topology control games in which the nodes need to choose power levels in order to connect to other nodes in the network to reach their communication partners while at the same time minimizing their costs. We study Nash equilibria and show that—among the games we define—these can only be guaranteed to exist if each network node is required to be connected to all other nodes (we call this the Strong Connectivity Game). For a variation called Connectivity Game, where each node is only required to be connected (possibly via intermediate nodes) to a given set of nodes, we show that Nash equilibria do not necessarily exist. We further study how to find Nash equilibria with incentive-compatible algorithms and compare the cost of Nash equilibria to the cost of a social optimum, which is a radius assignment that minimizes the total cost in a network where nodes cooperate. We also study variations of the games; one where nodes not only have to be connected, but k-connected, and one that we call the Reachability Game, where nodes have to reach as many other nodes as possible, while keeping costs low. We extend our study of the Strong Connectivity Game and the Connectivity Game to wireless networks with directional antennas and wireline networks, where nodes need to choose neighbors to which they will pay a link. Our work is a first step towards game-theoretic analyses of topology control in wireless and wireline networks. A preliminary version of this paper appeared in DIALM-POMC ’03 [8]. Stephan Eidenbenz is a technical staff member in Discrete Simulation Sciences (CCS-5) at Los Alamos National Laboraotry. He received his Ph.D. in Computer Science from the Swiss Federal Institute of Technology, Zurich, Switzerland in 2000. Stephan’s research covers areas in approximability, algorithms, computational geometry, computational biology, large-scale discrete simulation, selfish networking, efficient networking, protocol design and optimization. V. S. Anil Kumar is currently an Assistant Professor in the Dept. of Computer Science and a Senior Research Associate at Virginia Bioinformatics Institute, Virginia Tech. Prior to this, he was a technical staff member in Los Alamos National Laboratory. He received a Ph.D. in Computer Science from the Indian Institute of Science in 1999. His research interests include approximation algorithms, mobile computing, combinatorial optimization and simulation of large socio-technical systems. Sibylle Zust received her Masters degree in mathematics from ETH Zurich in Switzerland in 2002. She wrote her diploma thesis at the University of Copenhagen in Denmark. Sibylle Zust spent two and a half years (2002–2005) as a graduate research assistant at the Los Alamos National Laboratory in New Mexico, USA, where she worked on algorithmic aspects of game theory and scheduling problems. She now works for an insurance company in Zurich, Switzerland.     

The effects of synchronization on topology-transparent scheduling

Topology-transparent scheduling is an attractive medium access control technique for mobile ad hoc networks (MANETs) and wireless sensor networks (WSNs). The transmission schedule for each node is fixed and guarantees a bounded delay independent of which nodes are its neighbours, as long as the active neighbourhood is not too dense. Most of the existing work on topology-transparent scheduling assumes that the nodes are synchronized on frame boundaries. Synchronization is a challenging problem in MANETs and in WSNs. Hence, we study the relationships among topology-transparent schedules, expected delay, and maximum delay, for successively weaker models of synchronization: frame-synchronized, slot-synchronized, and asynchronous transmission. For each synchronization model, we give constructive proofs of existence of topology-transparent schedules, and bound the least maximum delay. Perhaps surprisingly, the construction for the asynchronous model is a simple variant of the slot synchronized model. While it is foreseen that the maximum delay increases as the synchronization model is weakened, the bound is too pessimistic. The results on expected delay show that topology-transparent schedules are very robust to node density higher than the construction is designed to support, allowing the nodes to cope well with mobility, and irregularities of their deployment. Wensong Chu received his M.S. in Applied Mathematics from Shanghai Jiao Tong University, China, in 1993; received his M.S. in Computer Networks (Electrical Engineering) from the University of Southern California in 2000; received his Ph.D. in Mathematics from the University of Southern California in 2002. He was with the Department of Computer Science and Engineering at Arizona State University as a post-doctoral fellow from 2002 to 2003. Currently he is doing research at the CMS Bondedge in California. His research interests include sequence designs for communications, combinatorial coding methods, mobile ad hoc networks and sensor networks, financial engineering and combinatorial design theory. Charles J. Colbourn was born in Toronto, Canada in 1953. He completed his B.Sc. degree at the University of Toronto in 1976, M.Math. at the University of Waterloo in 1978, and Ph.D. at the University of Toronto in 1980, all in computer science. He has held faculty positions at the University of Saskatchewan, the University of Waterloo, and the University of Vermont, and is now Professor of Computer Science and Engineering at Arizona State University. He is co-editor of the CRC Handbook of Combinatorial Designs and author of Triple Systems and The Combinatorics of Network Reliability, both from Oxford University Press. He is editor-in-chief of the Journal of Combinatorial Designs. His research concerns applications of combinatorial designs in networking, computing, and communications. Violet R. Syrotiuk earned the Ph.D. degree in Computer Science from the University of Waterloo (Canada) in 1992. She joined Arizona State University in 2002 and is currently an Assistant Professor of Computer Science and Engineering. Dr. Syrotiuk’s research is currently supported by three grants from the National Science Foundation, and contracts from Los Alamos National Laboratory, and the Defence Science and Technology Organisation in Australia. She serves on the Editorial Board of Computer Networks, and on the Technical Program Committee of several major conferences including MobiCom and Infocom. Her research interests include mobile ad hoc and sensor networks, in particular MAC protocols with an emphasis on adaptation, topology-transparency, and energy efficiency, dynamic spectrum utilization, mobile network models, and protocol interaction and cross-layer design. She is a member of the ACM and the IEEE.     

Decentralized Utility-based Sensor Network Design

Wireless sensor networks consist of energy-constrained sensor nodes operating unattended in highly dynamic environments. In this paper, we advocate a systematic decentralized approach towards the design of such networks based on utility functions. A local utility function is defined for each sensor node in the network. While each sensor node “selfishly” optimizes its own utility, the network as a “whole” converges to a desired global objective. For the purpose of demonstrating our approach, we consider the following two separate case studies for data gathering in sensor networks: (a) construction of a load balanced tree and (b) construction of an energy balanced tree. Our work suggests a significant departure from the existing view of sensor networks as consisting of cooperative nodes, i.e. “selfish”sensor nodes is a useful paradigm for designing efficient distributed algorithms for these networks. Narayanan Sadagopan received the B.S. degree in computer science from the Regional Engineering College, Trichy, India, in 1998, and the M.S. degree in computer science from University of Southern California (USC), Los Angeles, in 2001. He is currently working toward the Ph.D. degree in the Computer Science Department, USC. His research is focused on theoretical aspects of wireless ad hoc and sensor networks. Mitali Singh received the BTech. degree in Computer Science and Engineering from the Indian Institute of Technology, New Delhi, India in 2000, and the M.S. degree in Computer Science from the University of Southern California, Los Angeles, USA. She is currently working towards the Ph.D. degree in Computer Science at the University of Southern California. Her research interests lie in the area of applied theory and networks. Presently, her work is focused on high level modeling and distributed algorithm design for wireless sensor systems. Bhaskar Krishnamachari received the B.E.E.E. degree from The Cooper Union for the Advancement of Science and Art, New York, in 1998, and the M.S.E.E. and Ph.D. degrees in electrical engineering from Cornell University, Ithaca, NY, in 1999 and 2002, respectively. He is now an Assistant Professor in the Department of Electrical Engineering, University of Southern California, Los Angeles, where he also holds a joint appointment in the Department of Computer Science. His current research is focused on the discovery of fundamental principles and the analysis and design of protocols for next-generation wireless sensor networks.     

MANTIS OS: An Embedded Multithreaded Operating System for Wireless Micro Sensor Platforms

The MANTIS MultimodAl system for NeTworks of In-situ wireless Sensors provides a new multithreaded cross-platform embedded operating system for wireless sensor networks. As sensor networks accommodate increasingly complex tasks such as compression/aggregation and signal processing, preemptive multithreading in the MANTIS sensor OS (MOS) enables micro sensor nodes to natively interleave complex tasks with time-sensitive tasks, thereby mitigating the bounded buffer producer-consumer problem. To achieve memory efficiency, MOS is implemented in a lightweight RAM footprint that fits in less than 500 bytes of memory, including kernel, scheduler, and network stack. To achieve energy efficiency, the MOS power-efficient scheduler sleeps the microcontroller after all active threads have called the MOS sleep() function, reducing current consumption to the μA range. A key MOS design feature is flexibility in the form of cross-platform support and testing across PCs, PDAs, and different micro sensor platforms. Another key MOS design feature is support for remote management of in-situ sensors via dynamic reprogramming and remote login. Shah Bhatti is a Ph.D. student in Computer Science at the University of Colorado at Boulder. He also works as a Senior Program Manager in the R&D Lab for Imaging and Printing Group (IPG) at Hewlett Packard in Boise, Idaho. He has participated as a panelist in workshops on Integrated Architecture for Manufacturing and Component-Based Software Engineering, at IJCAI ‘89 and ICSE ‘98, respectively. Hewlett Packard has filed several patents on his behalf. He received an MSCS and an MBA from the University of Colorado, an MSCE from NTU and a BSCS from Wichita State University. His research interests include power management, operating system design and efficient models for wireless sensor networks. James Carlson is a Ph.D. student in Computer Science at the University of Colorado at Boulder. He received his Bachelor’s degree from Hampshire College in 1997. His research is supported by the BP Visualization Center at CU-Boulder. His research interests include computer graphics, 3D visualization, and sensor-enabled computer-human user interfaces. Hui Dai is a Ph.D. student in Computer Science at the University of Colorado at Boulder. He received his B.E. from the University of Science and Technology, China in 2000, and received has M.S. in Computer Science from the University of Colorado at Boulder in 2002. He has been co-leading the development of the MANTIS OS. His research interests include system design for wireless sensor networks, time synchronization, distributed systems and mobile computing. Jing Deng is a Ph.D. student in Computer Science at the University of Colorado at Boulder. He received his B.E. from Univeristy of Electronic Science and Technology of China in 1993, and his M.E from Institute of Computing Technology, Chinese Academy of Science in 1996. He has published four papers on security wireless sensor networks and is preparing a book chapter on security, privacy, and fault tolerance in sensor networks. His research interests include wireless security, secure network routing, and security for sensor networks. Jeff Rose is an M.S. student in Computer Science at the University of Colorado at Boulder. He received his B.S. in Computer Science from the University of Colorado at Boulder in 2003. He has been co-leading the development of the MANTIS operating system. His research interests include data-driven routing in sensor networks. 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. His research interests include MAC layer protocol design, energy-efficient wireless communication, and adapting communications to mobility. Brian Shucker 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 Arizona in 2001, and his M.S. in Computer Science from the University of Colorado at Boulder in December 2003. He has been co-leading the development of the MANTIS operating system. His research interests in wireless sensor networks include operating systems design, communication networking, and robotic sensor networks. Charles Gruenwald is an undergraduate student in Computer Science at the University of Colorado at Boulder. He joined the MANTIS research group in Fall 2003 as an undergraduate researcher. Adam Torgerson is an undergraduate student in Computer Science at the University of Colorado at Boulder. He joined the MANTIS research group in Fall 2003 as an undergraduate researcher. Richard Han joined the Department of Computer Science at the University of Colorado at Boulder in August 2001 as an Assistant Professor, Prof. Han leads the MANTIS wireless sensor networking research project, http://mantis.cs.colorado.edu. He has served on numerous technical program committees for conferences and workshops in the field of wireless sensor networks. He received a National Science Foundation CAREER Award in 2002 and IBM Faculty Awards in 2002 and 2003. He was a Research Staff Member at IBM’s Thomas J. Watson Research Center in Hawthorne, New York from 1997-2001. He received his Ph.D. in Electrical Engineering from the University of California at Berkeley in 1997, and his B.S. in Electrical Engineering with distinction from Stanford University in 1989. His research interests include systems design for sensor networks, secure wireless sensor networks, wireless networking, and sensor-enabled user interfaces.This revised version was published online in August 2005 with a corrected cover date.     

Exploiting Mobility for Energy Efficient Data Collection in Wireless Sensor Networks

We analyze an architecture based on mobility to address the problem of energy efficient data collection in a sensor network. Our approach exploits mobile nodes present in the sensor field as forwarding agents. As a mobile node moves in close proximity to sensors, data is transferred to the mobile node for later depositing at the destination. We present an analytical model to understand the key performance metrics such as data transfer, latency to the destination, and power. Parameters for our model include: sensor buffer size, data generation rate, radio characteristics, and mobility patterns of mobile nodes. Through simulation we verify our model and show that our approach can provide substantial savings in energy as compared to the traditional ad-hoc network approach. Sushant Jain is a Ph.D. candidate in the Department of Computer Science and Engineering at the University of Washington. His research interests are in design and analysis of routing algorithms for networking systems. He received a MS in Computer Science from the University of Washington in 2001 and a B.Tech degree in Computer Science from IIT Delhi in 1999. Rahul C. Shah completed the B. Tech (Hons) degree from the Indian Institute of Technology, Kharagpur in 1999 majoring in Electronics and Electrical Communication Engineering. He is currently pursuing his Ph.D. in Electrical Engineering at the University of California, Berkeley. His research interests are in energy-efficient protocol design for wireless sensor/ad hoc networks, design methodology for protocols and next generation cellular networks. Waylon Brunette is a Research Engineer in the Department of Computer Science and Engineering at the University of Washington. His research interests include mobile and ubiquitous computing, wireless sensor networks, and personal area networks. Currently, he is engaged in collaborative work with Intel Research Seattle to develop new uses for embedded devices and RFID technologies in ubiquitous computing. He received a BS in Computer Engineering from the University of Washington in 2002. Gaetano Borriello is a Professor in the Department of Computer Science and Engineering at the University of Washington. His research interests are in embedded and ubiquitous computing, principally new hardware devices that integrate seamlessly into the user’s environment with particular focus on location and identification systems. His principal projects are in creating manageable RFID systems that are sensitive to user privacy concerns and in context-awareness through sensors distributed in the environment as well as carried by users. Sumit Roy received the B. Tech. degree from the Indian Institute of Technology (Kanpur) in 1983, and the M. S. and Ph. D. degrees from the University of California (Santa Barbara), all in Electrical Engineering in 1985 and 1988 respectively, as well as an M. A. in Statistics and Applied Probability in 1988. His previous academic appointments were at the Moore School of Electrical Engineering, University of Pennsylvania, and at the University of Texas, San Antonio. He is presently Prof, of Electrical Engineering, Univ. of Washington where his research interests center around analysis/design of communication systems/networks, with a topical emphasis on next generation mobile/wireless networks. He is currently on academic leave at Intel Wireless Technology Lab working on high speed UWB radios and next generation Wireless LANs. His activities for the IEEE Communications Society includes membership of several technical committees and TPC for conferences, and he serves as an Editor for the IEEE Transactions on Wireless Communications.     

Energy aware efficient geographic routing in lossy wireless sensor networks with environmental energy supply

Wireless sensor networks are characterized by multihop wireless lossy links and resource constrained nodes. Energy efficiency is a major concern in such networks. In this paper, we study Geographic Routing with Environmental Energy Supply (GREES) and propose two protocols, GREES-L and GREES-M, which combine geographic routing and energy efficient routing techniques and take into account the realistic lossy wireless channel condition and the renewal capability of environmental energy supply when making routing decisions. Simulation results show that GREESs are more energy efficient than the corresponding residual energy based protocols and geographic routing protocols without energy awareness. GREESs can maintain higher mean residual energy on nodes, and achieve better load balancing in terms of having smaller standard deviation of residual energy on nodes. Both GREES-L and GREES-M exhibit graceful degradation on end-to-end delay, but do not compromise the end-to-end throughput performance. Kai Zeng received his B.E. degree in Communication Engineering and M.E. degree in Communication and Information System both from Huazhong University of Science and Technology, China, in 2001 and 2004, respectively. He is currently a Ph.D. student in the Electrical and Computer Engineering department at Worcester Polytechnic Institute. His research interests are in the areas of wireless ad hoc and sensor networks with emphases on energy-efficient protocol, cross-layer design, routing, and network security. Kui Ren received his B. Eng. and M. Eng. both from Zhejiang University, China, in 1998 and 2001, respectively. He worked as a research assistant at Shanghai Institute of Microsystem and Information Technology, Chinese Academy of Sciences from March 2001 to January 2003, at Institute for Infocomm Research, Singapore from January 2003 to August 2003, and at Information and Communications University, South Korea from September 2003 to June 2004. Currently he is a PhD candidate in the ECE department at Worcester Polytechnic Institute. His research interests include ad hoc/sensor network security, wireless mesh network security, Internet security, and security and privacy in ubiquitous computing environments. Wenjing Lou is an assistant professor in the Electrical and Computer Engineering department at Worcester Polytechnic Institute. She obtained her Ph.D. degree in Electrical and Computer Engineering from University of Florida in 2003. She received the M.A.Sc. degree from Nanyang Technological University, Singapore, in 1998, the M.E. degree and the B.E. degree in Computer Science and Engineering from Xi’an Jiaotong University, China, in 1996 and 1993 respectively. From December 1997 to July 1999, she worked as a Research Engineer in Network Technology Research Center, Nanyang Technological University. Her current research interests are in the areas of ad hoc and sensor networks, with emphases on network and system security and routing. Patrick J. Moran received his MSEE from Carnegie Mellon University, 1993. He is currently the CTO and Founder of AirSprite Technologies Inc, and is driving the company to utilize advanced networking protocols for low-power wireless network systems. His interests include architecture, protocols and high performance implementation of emerging communication technologies. Patrick has been involved in deployment of communication and signal processing technologies since graduating from the University of Minn. in 1986. He holds several patents and publications relating to storage, medical and data processing information systems. He is a member of the IEEE.     

a high-throughput path metric for multi-hop wireless routing

This paper presents the expected transmission count metric (ETX), which finds high-throughput paths on multi-hop wireless networks. ETX minimizes the expected total number of packet transmissions (including retransmissions) required to successfully deliver a packet to the ultimate destination. The ETX metric incorporates the effects of link loss ratios, asymmetry in the loss ratios between the two directions of each link, and interference among the successive links of a path. In contrast, the minimum hop-count metric chooses arbitrarily among the different paths of the same minimum length, regardless of the often large differences in throughput among those paths, and ignoring the possibility that a longer path might offer higher throughput.This paper describes the design and implementation of ETX as a metric for the DSDV and DSR routing protocols, as well as modifications to DSDV and DSR which allow them to use ETX. Measurements taken from a 29-node 802.11b test-bed demonstrate the poor performance of minimum hop-count, illustrate the causes of that poor performance, and confirm that ETX improves performance. For long paths the throughput improvement is often a factor of two or more, suggesting that ETX will become more useful as networks grow larger and paths become longer.This research was supported by grants from NTT Corporation under the NTT-MIT collaboration, and by MIT’s Project Oxygen.Douglas De Couto received his Ph.D. in Computer Science from MIT in June 2004 for work in multi-hop wireless routing. He was a member of MIT’s Computer Science and Artificial Laboratory. He also received his S.B. and M.Eng. degrees in Computer Science and Electrical Engineering from MIT, in 1998. His research interests include multi-hop wireless networks, sensor and embedded networks, and applications of GPS. E-mail: decouto@csail.mit.eduDaniel Aguayo is a graduate student in MIT’s EECS department and a member of MIT’s Computer Science and Artificial Intelligence Laboratory. He received an S.B. in Computer Science and Electrical Engineering from MIT in 2001, and an M.Eng. in 2002. His research interests are focused on multi-hop wireless networks. E-mail: aguayo@csail.mit.eduJohn Bicket is a graduate student in MIT’s EECS department and a member of MIT’s Computer Science and Artificial Intelligence Laboratory. He received a B.S. from Cornell University. His research interests include multi-hop rooftop 802.11 networks and device drivers. E-mail: jbicket@csail.mit.eduRobert Morris is an associate professor in MIT’s EECS department and a member of MIT’s Computer Science and Artificial Intelligence Laboratory. He received a Ph.D. from Harvard University for work on modeling and controlling data networks with large numbers of competing connections. He co-founded Viaweb, an e-commerce hosting service. His current interests include routing in multi-hop rooftop 802.11 networks, modular software-based routers, distributed hash tables, and peer-to-peer file storage. He has received a Sloan Fellowship, an NSF Career award, and the ITT Career Development Chair at MIT. E-mail: rtm@csail.mit.edu     

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.     

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.     

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     

Enhancing Transport Layer Capability in HAPS–Satellite Integrated Architecture

The use of HAPS/UAV to enhance telecommunication capabilities has been proposed as an effective solution to support hot spot communications in limited areas. To ensure communication capabilities even in case of emergency (earthquake, power blackout, chemical/nuclear disaster, terrorist attack), when terrestrial fixed and mobile infrastructures are damaged or become unavailable, the access to satellites represents a reliable solution with worldwide coverage, even though it may suffer from shadowing impairment, especially in an urban environment. In this paper we approach an innovative and more challenging architecture foreseeing HAPS/UAV connected to the satellite in order to enlarge coverage and to allow interconnection with very remote locations. In this scenario, we have analysed TCP-based applications proposing some innovative techniques, both at protocol and at architectural level, to improve performance. In particular, we propose the use of a PEP technique, namely splitting, to speed up window growth in spite of high latency, combined with TCP Westwood as a very efficient algorithm particularly suitable and well performing over satellite links.Cesare Roseti graduated cum laude in 2003 in Electronic Engineering at University of Rome “Tor Vergata”. In 2003 and 2004, he was a visiting student at Computer Science Department of University of California, Los Angeles (UCLA). Since 2004 he is a PhD student at the Electronic Engineering Department and his research interests include satellites communications and transport protocols in heterogeneous (wired/wireless) systems.Claudio Enrico Palazzi studied computer science at University of Bologna, Campus of Cesena. He has been a student representative in several bodies of University of Bologna and, in particular, from 2000 to 2001 he was part of the Board of Governors. In 2001, he received the Sigillum Magnum of Alma Mater Studiorum University of Bologna. He graduated cum laude in 2002 with a thesis on transport protocols in wireless environments. In 2003, he was the first student enrolled in the Interlink joint PhD program in computer science by which he is currently a PhD student in Computer Science at both University of Bologna and University of California, Los Angeles (UCLA). His research interests include protocol design, implementation and performance analysis for wired/wireless networks.Michele Luglio received the Laurea degree in electronic engineering from the University of Rome “Tor Vergata”. He received the PhD degree in telecommunications in 1994. From August to December 1992 he worked as visiting staff engineering at Microwave Technology and Systems Division of Comsat Laboratories (Clarksburg, Maryland, USA). He received the Young Scientist Award from ISSSE’95. Since October 1995, he is research and teaching assistant at University of Rome “Tor Vergata” where he works on designing satellite systems for multimedia services both mobile and fixed, in the frame of projects funded by EC, ESA and ASI. He taught signal theory and collaborated in teaching digital signal processing and elements of telecommunications. In 2001 and 2002 he was visiting professor at the Computer Science Department of University of California Los Angeles (UCLA) to teach Satellite Networks class. Now he teaches satellite telecommunications and signals and transmission. He is a member of IEEE.Mario Gerla received a graduate degree in engineering from the Politecnico di Milano in 1966, and the MS and PhD degrees in engineering from UCLA in 1970 and 1973, respectively. After working for Network Analysis Corporation from 1973 to 1976, he joined the Faculty of the Computer Science Department at UCLA where he is now professor. His research interests cover the performance evaluation, design and control of distributed computer communication systems; high-speed computer networks; wireless LANs; and ad hoc wireless networks. He has worked on the design, implementation and testing of various wireless ad hoc network protocols (channel access, clustering, routing and transport) within the DARPA WAMIS, GloMo projects. Currently, he is leading the ONR MINUTEMAN project at UCLA, and is designing a robust, scalable wireless ad hoc network architecture for unmanned intelligent agents in defense and homeland security scenarios. He is also conducting research on QoS routing, multicasting protocols and TCP transport for the Next-Generation Internet (see www.cs.ucla.edu/NRL for recent publications). He became IEEE Fellow in 2002.M. Yahya “Medy” Sanadidi was born in Damanhour, Egypt. He received his high school diploma from College Saint Marc, and his BSc in electrical engineering (computer and automatic control section) from the University of Alexandria, Egypt. Dr. Sanadidi received his PhD in computer science from UCLA in 1982. He is currently a research professor at the UCLA Computer Science Department. As co-principal investigator on NSF-sponsored research, he is leading research in modeling and evaluation of high-performance Internet protocols. He teaches undergraduate and graduate courses at UCLA on queuing systems and computer networks. Dr. Sanadidi was a manager and senior consulting engineer at Teradata/AT&T/NCR from 1991 to 1999 and led several groups responsible for performance modeling and analysis, operating systems, and parallel query optimization. From 1984 to 1991, he held the position of computer scientist at Citicorp, where he pursued R&D projects in wireless metropolitan area data communications and other networking technologies. In particular, between 1984 and 1987, he lead the design and prototyping of a wireless MAN for home banking and credit card verification applications. From 1981 to 1983, Dr. Sanadidi was an assistant professor at the Computer Science Department, University of Maryland, College Park, Maryland. There, he taught performance modeling, computer architecture and operating systems, and was principal investigator for NSA-sponsored research on global data communications networks. Dr. Sanadidi has consulted for industrial concerns, has co-authored conference as well as journal papers, and holds two patents in performance modeling. He participated as reviewer and as program committee member of professional conferences. His current research interests are focused on congestion control and adaptive multimedia streaming protocols in heterogeneous (wired/wireless) networks.James Stepanek received his BS in computer science from Harvey Mudd College in 1994 and his MS in computer science from University of California, Los Angeles (UCLA) in 2001 where he is currently enrolled in the PhD program. He is also currently a member of the technical staff in the Computer Systems Research Department of The Aerospace Corporation. His research interests include wireless and satellite networks.     

Multi-radio diversity in wireless networks

This paper describes the Multi-Radio Diversity (MRD) wireless system, which uses path diversity to improve loss resilience in wireless local area networks (WLANs). MRD coordinates wireless receptions among multiple radios to improve loss resilience in the face of path-dependent frame corruption over the radio. MRD incorporates two techniques to recover from bit errors and lower the loss rates observed by higher layers, without consuming much extra bandwidth. The first technique is frame combining, in which multiple, possibly erroneous, copies of a given frame are combined together in an attempt to recover the frame without retransmission. The second technique is a low-overhead retransmission scheme called request-for-acknowledgment (RFA), which operates above the link layer and below the network layer to attempt to recover from frame combining failures. We present an analysis that determines how the parameters for these algorithms should be chosen. We have designed and implemented MRD as a fully functional WLAN infrastructure based on 802.11a. We evaluate the MRD system under several different physical configurations, using both UDP and TCP, and measured throughput gains up to 3× over single radio communication schemes employing 802.11’s autorate adaptation scheme. Computer and Communication Sciences, EPFL, Switzerland. Allen Miu received his Ph.D. degree at the Massachusetts Institute of Technology in 2006 and is currently a wireless systems architect at Ruckus Wireless, Inc. He received his S.M. in Computer Science from MIT and a B.Sc. with highest honors in Electrical Engineering and Computer Science from the University of California at Berkeley. He previously worked on the Cricket Indoor Location System and was a research intern at Microsoft Research, Redmond in 2000 and Hewlett-Packard Laboratories, Palo Alto in 2002. His research interests include wireless networks, location systems, mobile computing, and embedded systems. Hari Balakrishnan is an Associate Professor in the EECS Department and a member of the Computer Science and Artificial Intelligence Laboratory (CSAIL) at MIT. His research interests is in the area of networked computer systems. In addition to many widely cited papers, several systems developed as part of his research are available in the public domain. He received a Ph.D. in Computer Science from the University of California at Berkeley in 1998 and a B.Tech. from the Indian Institute of Technology (Madras) in 1993. His honors include an Alfred P. Sloan Research Fellowship (2002), an NSF CAREER Award (2000), the ACM doctoral dissertation award for his work on reliable data transport over wireless networks (1998), and seven award-winning papers at various top conferences and journals, including the IEEE Communication Society’s William R. Bennett Prize (2004). He has also received awards for excellence in teaching and research at MIT (Spira, Junior Bose, and Harold Edgerton faculty achievement awards). C. Emre Koksal received his B.S. degree in Electrical Engineering from the Middle East Technical University, Ankara in 1996. He received his S.M. and Ph.D. degrees from MIT in Electrical Engineering and Computer Science in 1998 and 2002 respectively. He was a postdoctoral fellow in the Networks and Mobile Systems Group in the Computer Science and Artificial Intelligence Laboratory at MIT until 2003. Since then he has been a senior researcher jointly in the Laboratory for Computer Communications and the Laboratory for Information Theory at EPFL, Switzerland. His general areas of interest are wireless communications, computer networks, information theory, stochastic processes and financial economics. He also has a certificate on Financial Technology from the Sloan School of Management at MIT.     

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.     

SOLONet: Sub-optimal location-aided overlay network for MANETs

Overlay networks have made it easy to implement multicast functionality in MANETs. Their flexibility to adapt to different environments has helped in their steady growth. Overlay multicast trees that are built using location information account for node mobility and have a low latency. However, the performance gains of such trees are offset by the overhead involved in distributing and maintaining precise location information. As the degree of (location) accuracy increases, the performance improves but the overhead required to store and broadcast this information also increases. In this paper, we present SOLONet, a design to build a sub-optimal location aided overlay multicast tree, where location updates of each member node are event based. Unlike several other approaches, SOLONet doesn’t require every packet to carry location information or each node maintain location information of every other node or carrying out expensive location broadcast for each node. Our simulation results indicate that SOLONet is scalable and its sub-optimal tree performs very similar to an overlay tree built by using precise location information. SOLONet strikes a good balance between the advantages of using location information (for building efficient overlay multicast trees) versus the cost of maintaining and distributing location information of every member nodes. Abhishek Patil received his BE degree in Electronics and Telecommunications Engineering from University of Mumbai (India) in 1999 and an MS in Electrical and Computer Engineering from Michigan State University in 2002. He finished his PhD in 2005 from the Department of Computer Science and Engineering at Michigan State University. He is a research engineer at Kiyon, Inc. located in San Diego, California. His research interests include wireless mesh networks, UWB, mobile ad hoc networks, application layer multicast, location-aware computing, RFIDs, and pervasive computing. Yunhao Liu received his BS degree in Automation Department from Tsinghua University, China, in 1995, and an MA degree in Beijing Foreign Studies University, China, in 1997, and an MS and a Ph.D. degree in Computer Science and Engineering at Michigan State University in 2003 and 2004, respectively. He is now an assistant professor in the Department of Computer Science at Hong Kong University of Science and Technology. His research interests include wireless sensor networks, peer-to-peer and grid computing, pervasive computing, and network security. He is a senior member of the IEEE Computer Society. Li Xiao received the BS and MS degrees in computer science from Northwestern Polytechnic University, China, and the PhD degree in computer science from the College of William and Mary in 2002. She is an assistant professor of computer science and engineering at Michigan State University. Her research interests are in the areas of distributed and Internet systems, overlay systems and applications, and sensor networks. She is a member of the ACM, the IEEE, the IEEE Computer Society, and IEEE Women in Engineering. Abdol-Hossein Esfahanian received his B.S. degree in Electrical Engineering and the M.S. degree in Computer, Information, and Control Engineering from the University of Michigan in 1975 and 1977 respectively, and the Ph.D. degree in Computer Science from Northwestern University in 1983. He was an Assistant Professor of Computer Science at Michigan State University from September 1983 to May 1990. Since June 1990, he has been an Associate Professor with the same department, and from August 1994 to May 2004, he was the Graduate Program Director. He was awarded ‘The 1998 Withrow Exceptional Service Award’, and ‘The 2005 Withrow Teaching Excellence Award’. Dr. Esfahanian has published articles in journals such as IEEE Transactions, NETWORKS, Discrete Applied Mathematic, Graph Theory, and Parallel and Distributed Computing. He was an Associate Editor of NETWORKS, from 1996 to 1999. He has been conducting research in applied graph theory, computer communications, and fault-tolerant computing. Lionel M. Ni earned his Ph.D. degree in electrical and computer engineering from Purdue University in 1980. He is Chair Professor and Head of Computer Science and Engineering Department of the Hong Kong University of Science and Technology. His research interests include wireless sensor networks, parallel architectures, distributed systems, high-speed networks, and pervasive computing. A fellow of IEEE, Dr. Ni has chaired many professional conferences and has received a number of awards for authoring outstanding papers.     

Smart-Aloha for Multi-Hop Wireless Networks

This paper presents a novel slotted ALOHA-based protocol for use in ad hoc networks where nodes are equipped with adaptive array smart antennas. The protocol relies on the ability of the antenna and DoA (Direction of Arrival) algorithms to identify the direction of transmitters and then beamform appropriately to maximize SINR (Signal to Interference and Noise Ratio) at the receiver. The performance of the protocol is evaluated using analytical modeling as well as detailed simulation in OPNET and Matlab where we demonstrate the benefits of using smart antennas. The impact of using different number of antenna elements is also studied for this environment.This work is funded by the NSF under grant ANIR-0125728.Harkirat Singh is a PhD candidate in Computer Science at Portland State University. He holds Master in Computer Science from Portland State University and B. E. in Electrical Engineering from Indian Institute of Technology (IIT), Roorkee, India. After his under graduation he joined Automation division of Siemens AG. He has research interests in next-generation TCP/IP networking, Mobile Wireless Computing, Ad-hoc networking, and low-power lost-cost sensor networks.Suresh Singh received his B. Tech. Degree in Computer Science from the Indian Institute of Technology (IIT) Kanpur in 1984 and his Ph.D. degree in 1990 from the University of Massachusetts at Amherst, both in Computer Science. His areas of research include energy-efficient protocols for wireless networking, sensor networks, cellular networking with a focus on 3g standards, and performance evaluation. His work has been funded by several federal agencies such as NSF, DARPA, and ONR and by a variety of industries. He is a member of the ACM and IEEE.     

Private Authentication Techniques for the Global Mobility Network

Numerous authentication approaches have been proposed recently for the global mobility network (GLOMONET), which provides mobile users with global roaming services. In these authentication schemes, the home network operators can easily obtain the authentication key and wiretap the confidentiality between the roaming user and the visited network. This investigation provides a solution of authentication techniques for GLOMONET in order to prevent this weakness from happening and presents a secure authentication protocol for roaming services. In addition, a round-efficient version of the same authentication protocol is presented. Comparing with other related approaches, the proposed authentication protocol involves fewer messages and rounds in communication. Tian-Fu Lee was born in Tainan, Taiwan, ROC, in 1969. He received his B.S. degree in Applied Mathematics from National Chung Hsing University, Taiwan, in 1992, and his M.S. degree in Computer Science and Information Engineering from National Chung Cheng University, Taiwan, in 1998. He works as a lecturer in Leader University and pursues his Ph.D. degree at Department of Computer Science and Information Engineering, National Cheng Kung University, Taiwan. His research interests include cryptography and network security. Chi-Chao Chang received the BS degree in Microbiology from Soochow University in 1990 and the MS degree in Computer Science from State University of New York at Albany in 1992. He is currently working as an instructor in Chang Jung Christian University and a graduate student in National Cheng Kung University. His research interests are information security, mobile agent systems, anonymous digital signatures and quantum cryptography. Tzonelih Hwang was born in Tainan, Taiwan, in March 1958. He received his undergraduate degree from National Cheng Kung University, Tainan, Taiwan, in 1980, and the M.S. and Ph.D. degrees in Computer Science from the University of Southwestern Louisiana, USA, in 1988. He is presently a professor in Department of Computer Science and Information Engineering, National Cheng Kung University. His research interests include cryptology, network security, and coding theory.     

Service Composition for Mobile Environments

Service Composition, that is, the development of customized services by discovering, integrating and executing existing services has received a lot of attention in the last couple of years with respect to wired-infrastructure or Internet web services. With the advancement in the wireless technology and rapid deployment of mobile devices, we envision that in the near future wirelessly connected mobile devices in a given vicinity will also provide services that can be leveraged in the composition process. This is particularly true of what have been described as “pervasive computing” environments. However, wired-infrastructure based service composition architectures are not designed to consider the various factors like mobility, device heterogeneity, resource variability and reliability in a mobile environment. In this paper, we describe the issues related to service composition in mobile environments and evaluate criteria for judging protocols that enable such composition. We present a distributed architecture and associated protocols for service composition in mobile environments that take into consideration mobility, dynamic changing service topology and device resources. The composition protocols are based on distributed brokerage mechanisms and utilize a distributed service discovery process over ad-hoc network connectivity. We present simulation results of our protocols, and compare them with a centralized service composition protocol traditionally used for wired-infrastructure environments. The results show that our approach clearly outperforms the existing centralized approaches, and that our protocols are able to adapt and better utilize the changing service topology and resources in a mobile environment.This work is supported in part by NSF awards 9875433 and 0070802, DARPA DAML program and IBM. Dipanjan Chakraborty is a Ph.D candidate and a research member of ebiquity research group at University of Maryland, Baltimore County (UMBC). His reserach is in the areas of mobile and pervasive computing environments, mobile and e-commerce, peer-to-peer systems with special interests in the fields of service discovery, information aggregation and composition, ad-hoc network application-centric routing, agent-based systems. He specializes in the development and modeling of distributed architectures to enable mobile and pervasive commerce in ubiquitous environments. His thesis is in the area of service discovery and composition for pervasive environments. He has been a fellow of IBM during the 3 years of his Ph.D candidacy. Anupam Joshi is an Associate Professor of Computer Science and Electrical Engineering at UMBC. Earlier, he was an Assistant Professor in the CECS department at the University of Missouri, Columbia. He obtained a B. Tech degree in Electrical Engineering from IIT Delhi in 1989, and a Masters and Ph.D. in Computer Science from Purdue University in 1991 and 1993 respectively. His research interests are in the broad area of networked computing and intelligent systems. His primary focus has been on data management for mobile computing systems in general, and most recently on data management and security in pervasive computing and sensor environments. He has created agent based middleware to support discovery, composition, and secure access of services/data over both infrastructure based (e.g. 802.11, cellular) and ad-hoc wireless networks (e.g. Bluetooth). He is also interested in Semantic Web and Data/Web Mining, where he has worked on personalizing the web space using a combination of agents and soft computing. His other interests include networked HPCC. He has published over 50 technical papers, and has obtained research support from NSF, NASA, DARPA, DoD, IBM, AetherSystens, HP, AT&T and Intel. He has presented tutorials in conferences, served as guest editor for special issues for IEEE Personal Comm., Comm. ACM etc., and served as an Associate Editor of IEEE Transactions of Fuzzy Systems from 99-03. At UMBC, Joshi teaches courses in Operating Systems, Mobile Computing, Networking, and Web Mining. He is a member of IEEE, IEEE-CS, and ACM. Tim Finin is a Professor in the Department of Computer Science and Electrical Engineering at the University of Maryland Baltimore County (UMBC). He has over 30 years of experience in the applications of Artificial Intelligence to problems in information systems, intelligent interfaces and robotics and is currently working on the theory and applications of intelligent software agents, the semantic web, and mobile computing. He holds degrees from MIT and the University of Illinois. Prior to joining the UMBC, he held positions at Unisys, the University of Pennsylvania, and the MIT AI Laboratory. Finin is the author of over 180 refereed publications and has received research grants and contracts from a variety of sources. He has been the past program chair or general chair of several major conferences. He is a former AAAI councilor and is a member of the the board of directors of the Computing Research Association. Yelena Yesha received the B.Sc. degree in Computer Science from York University, Toronto, Canada in 1984, and the M.Sc. and Ph.D degrees in Computer and Information Science from The Ohio State University in 1986 and 1989, respectively. Since 1989 she has been with the Department of Computer Science and Electrical Engineering at the University of Maryland Baltimore County, where she is presently a Verizon Professor. In addition, from December, 1994 through August, 1999 Dr. Yesha served as the Director of the Center of Excellence in Space Data and Information Sciences at NASA. Her research interests are in the areas of distributed databases, distributed systems, mobile computing, digital libraries, electronic commerce, and trusted information systems. She published 8 books and over 100 refereed articles in these areas. Dr. Yesha was a program chair and general co-chair of the ACM International Conference on Information and Knowledge Management and a member of the program committees of many prestigious conferences. She is a member of the editorial board of the Very Large Databases Journal, and the IEEE Transaction on Knowledge and Data Engineering, and is editor-in-chief of the International Journal of Digital Libraries. During 1994, Dr. Yesha was the Director of the Center for Applied Information Technology at the National Institute of Standards and Technology. Dr. Yesha is a senior member of IEEE, and a member of the ACM.This revised version was published online in August 2005 with a corrected cover date.     

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 .     

Energy balanced data propagation in wireless sensor networks

We study the problem of energy-balanced data propagation in wireless sensor networks. The energy balance property guarantees that the average per sensor energy dissipation is the same for all sensors in the network, during the entire execution of the data propagation protocol. This property is important since it prolongs the network’:s lifetime by avoiding early energy depletion of sensors. We propose a new algorithm that in each step decides whether to propagate data one-hop towards the final destination (the sink), or to send data directly to the sink. This randomized choice balances the (cheap) one-hop transimssions with the direct transimissions to the sink, which are more expensive but “bypass” the sensors lying close to the sink. Note that, in most protocols, these close to the sink sensors tend to be overused and die out early. By a detailed analysis we precisely estimate the probabilities for each propagation choice in order to guarantee energy balance. The needed estimation can easily be performed by current sensors using simple to obtain information. Under some assumptions, we also derive a closed form for these probabilities. The fact (shown by our analysis) that direct (expensive) transmissions to the sink are needed only rarely, shows that our protocol, besides energy-balanced, is also energy efficient. This work has been partially supported by the IST/FET/GC Programme of the European Union under contract numbers IST-2001-33135 (CRESCCO) and 6FP 001907 (DELIS). A perliminary version of the work appeared in WMAN 2004 [11]. Charilaos Efthymiou graduated form the Computer Engineering and Informatics Department (CEID) of the University of Patras, Greece. He received his MSc from the same department with advisor in S. Nikoletseas. He currently continuous his Ph.D studies in CEID with advisor L. Kirousis. His research interest include Probabilistic Techniques and Random Graphs, Randomized Algorithms in Computationally Hard Problems, Stochastic Processes and its Applications to Computer Science. Dr. Sotiris Nikoletseas is currently a Senior Researcher and Managing Director of Research Unit 1 (“Foundations of Computer Science, Relevant Technologies and Applications”) at the Computer Technology Institute (CTI), Patras, Greece and also a Lecturer at the Computer Engineering and Informatics Department of Patras University, Greece. His research interests include Probabilistic Techniques and Random Graphs, Average Case Analysis of Graph Algorithms and Randomized Algorithms, Fundamental Issues in Parallel and Distributed Computing, Approximate Solutions to Computationally Hard Problems. He has published scientific articles in major international conferences and journals and has co-authored (with Paul Spirakis) a book on Probabilistic Techniques. He has been invited speaker in important international scientific events and Universities. He has been a referee for the Theoretical Computer Science (TCS) Journal and important international conferences (ESA, ICALP). He has participated in many EU funded R&D projects (ESPRIT/ALCOM-IT, ESPRIT/GEPPCOM). He currently participates in 6 Fifth Framework projects: ALCOM-FT, ASPIS, UNIVERSAL, EICSTES (IST), ARACNE, AMORE (IMPROVING). Jose Rolim is Full Professor at the Department of Computer Science of the University of Geneva where he leads the Theoretical Computer Science and Sensor Lab (TCSensor Lab). He received his Ph.D. degree in Computer Science at the University of California, Los Angeles working together with Prof. S. Greibach. He has published several articles on the areas of distributed systems, randomization and computational complexity and leads two major projects on the area of Power Aware Computing and Games and Complexity, financed by the Swiss National Science Foundation. Prof. Rolim participates in the editorial board of several journals and conferences and he is the Steering Committee Chair and General Chair of the IEEE Distributed Computing Conference in Sensor Systems.     

An unequal cluster-based routing protocol in wireless sensor networks

Clustering provides an effective method for prolonging the lifetime of a wireless sensor network. Current clustering algorithms usually utilize two techniques; selecting cluster heads with more residual energy, and rotating cluster heads periodically to distribute the energy consumption among nodes in each cluster and extend the network lifetime. However, they rarely consider the hot spot problem in multihop sensor networks. When cluster heads cooperate with each other to forward their data to the base station, the cluster heads closer to the base station are burdened with heavier relay traffic and tend to die much faster, leaving areas of the network uncovered and causing network partitions. To mitigate the hot spot problem, we propose an Unequal Cluster-based Routing (UCR) protocol. It groups the nodes into clusters of unequal sizes. Cluster heads closer to the base station have smaller cluster sizes than those farther from the base station, thus they can preserve some energy for the inter-cluster data forwarding. A greedy geographic and energy-aware routing protocol is designed for the inter-cluster communication, which considers the tradeoff between the energy cost of relay paths and the residual energy of relay nodes. Simulation results show that UCR mitigates the hot spot problem and achieves an obvious improvement on the network lifetime. Guihai Chen obtained his B.S. degree from Nanjing University, M. Engineering from Southeast University, and PhD from University of Hong Kong. He visited Kyushu Institute of Technology, Japan in 1998 as a research fellow, and University of Queensland, Australia in 2000 as a visiting professor. During September 2001 to August 2003, he was a visiting professor at Wayne State University. He is now a full professor and deputy chair of Department of Computer Science, Nanjing University. Prof. Chen has published more than 100 papers in peer-reviewed journals and refereed conference proceedings in the areas of wireless sensor networks, high-performance computer architecture, peer-to-peer computing and performance evaluation. He has also served on technical program committees of numerous international conferences. He is a member of the IEEE Computer Society. Chengfa Li was born 1981 and obtained his Bachelor’s Degree in mathematics in 2003 and his Masters Degree in computer science in 2006, both from Nanjing University, China. He is now a system programmer at Lucent Technologies Nanjing Telecommunication Corporation. His research interests include wireless ad hoc and sensor networks. Mao Ye was born in 1981 and obtained his Bachelor’s Degree in computer science from Nanjing University, China, in 2004. He served as a research assistant At City University of Hong Kong from September 2005 to August 2006. He is now a PhD candidate with research interests in wireless networks, mobile computing, and distributed systems. Jie Wu is a professor in the Department of Computer Science and Engineering at Florida Atlantic University. He has published more than 300 papers in various journal and conference proceedings. His research interests are in the areas of mobile computing, routing protocols, fault-tolerant computing, and interconnection networks. Dr. Wu serves as an associate editor for the IEEE Transactions on Parallel and Distributed Systems and several other international journals. He served as an IEEE Computer Society Distinguished Visitor and is currently the chair of the IEEE Technical Committee on Distributed Processing (TCDP). He is a member of the ACM, a senior member of the IEEE, and a member of the IEEE Computer Society.