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.     

Efficient Timing Budget Management for Accuracy Improvement in a Collaborative Object Tracking System

This paper presents the idea of managing the comprising computations of an application performed by an embedded networked system. An efficient algorithm for exploiting the timing slack of building blocks of the application is proposed. The slack of blocks can be utilized by replacing them with slower but cheaper, i.e. better, modules and by assigning the computations to the proper resources. Thus, our approach manages the comprising computations and system resources and can indirectly assist the realtime scheduling of computations on system resources. This is performed without compromising the timing constraints of the application and can lead to significant improvements in power dissipation, computation accuracy or other metrics of the application domain. Our algorithm is well-suited for arbitrary tree computations. Moreover, it delivers solutions that are desirably close to the optimal solution. Experimental results for a number of object tracking applications implemented in an networked system with embedded computation resources, exhibit a significant amount of slack utilization. Soheil Ghiasi received his B.S. from Sharif University of Technology, Tehran, Iran in 1998, and his M.S. and Ph.D. in Computer Science from the University of California, Los Angeles in 2002 and 2004, respectively. Currently, he is an assistant professor in the department of electrical and computer engineering at the University of California, Davis. His research interests include different aspects of Embedded and Reconfigurable system design. Elaheh Bozorgzadeh received the B.S. degree in Electrical Engineering from Sharif University of Technology, Iran in 1998, M.S. degree in Computer Engineering from Northwestern University in 2000, and Ph.D. degree in Computer Science from the University of California, Los Angeles, in 2003. She is currently as assistant professor in the Department of Computer Science at the University of California, Irvine. Her research interest includes VLSI CAD, design automation for embedded systems, and reconfigurable computing. She is a member of ACM and IEEE. Karlene Nguyen received her B.S. and M.S. from University of California, Los Angeles in 2001 and 2003, respectively. She has been working with Prof. Majid Sarrafzadeh for her M.S. degree. Her research interests include embedded hardware and software design. Majid Sarrafzadeh received his B.S., M.S. and Ph.D. in 1982, 1984, and 1987 respectively from the University of Illinois at Urbana-Champaign in Electrical and Computer Engineering. He joined Northwestern University as an Assistant Professor in 1987. In 2000, he joined the Computer Science Department at University of California at Los Angeles (UCLA). His recent research interests lie in the area of Embedded and Reconfigurable Computing, VLSI CAD, and design and analysis of algorithms. Dr. Sarrafzadeh is a Fellow of IEEE for his contribution to “Theory and Practice of VLSI Design.” He received an NSF Engineering Initiation award, two distinguished paper awards in ICCAD, and the best paper award in DAC. He has served on the technical program committee of numerous conferences in the area of VLSI Design and CAD, including ICCAD, DAC, EDAC, ISPD, FPGA, and DesignCon. He has served as committee chairs of a number of these conferences. He is on the executive committee/steering committee of several conferences such as ICCAD, ISPD, and ISQED. He is the program committee chair of ICCAD 2004. Professor Sarrafzadeh has published approximately 250 papers, is a co-editor of the book “Algorithmic Aspects of VLSI Layout” (1994 by World Scientific), and co-author of the book “An Introduction to VLSI Physical Design” (1996 by McGraw Hill). Dr. Sarrafzadeh is an Associate Editor of ACM Transaction on Design Automation (TODAES) and an Associate Editor of IEEE Transactions on Computer-Aided Design (TCAD) and ACM Transactions on design Automation (TODAES). Dr. Sarrafzadeh has collaborated with many industries in the past fifteen years including IBM, Motorola, and many CAD industries. He is the architect of the physical design subsystem of Monterey Design Systems main product. He is a co-founder of Hier Design, Inc.     

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.     

A randomized energy-conservation protocol for resilient sensor networks*

In this paper we present PEAS, a randomized energy-conservation protocol that seeks to build resilient sensor networks in the presence of frequent, unexpected node failures. PEAS extends the network lifetime by maintaining a necessary set of working nodes and turning off redundant ones, which wake up after randomized sleeping times and replace failed ones when needed. The fully localized operations of PEAS are based on each individual node's observation of its local environment but do not require per neighbor state at any node; this allows PEAS to scale to very dense node deployment. PEAS is highly robust against node failures due to its simple operations and randomized design; it also ensures asymptotic connectivity. Our simulations and analysis show that PEAS can maintain an adequate working node density in presence of as high as 38% node failures, and a roughly constant overhead of less than 1% of the total energy consumption under various deployment densities. It extends a sensor network's functioning time in linear proportional to the deployed sensor population. Fan Ye received his B.E. in Automatic Control in 1996 and M.S. in Computer Science in 1999, both from Tsinghua University, Beijing, China. He received his Ph.D. in Computer Science in 2004 from UCLA. He is currently with IBM Research. His research interests are in wireless networks, sensor networks and security. Honghai Zhang received his BS in Computer Science in 1998 from University of Science and Technology of China. He received his MS and Ph.D. in Computer Science from University of Illinois at Urbana-Champaign. He is currently with the Wireless Advanced Technology Lab of Lucent Technologies. His research interests are wireless networks, WiMAX, and VoIP over wireless networks. Songwu Lu received both his M.S. and Ph.D. from University of Illinois at Urbana-Champaign. He is currently an associate professor at UCLA Computer Science. He received NSF CAREER award in 2001. His research interests include wireless networking, mobile computing, wireless security, and computer networks. Lixia Zhang received her Ph.D in computer science from the Massachusetts Institute of Technology. She was a member of the research staff at the Xerox Palo Alto Research Center before joining the faculty of UCLA’s Computer Science Department in 1995. In the past she has served on the Internet Architecture Board, Co-Chair of IEEE Communication Society Internet Technical Committee, the editorial board for the IEEE/ACM Transactions on Networking, and technical program committees for many networking-related conferences including SIGCOMM and INFOCOM. Zhang is currently serving as the vice chair of ACM SIGCOMM. Jennifer C. Hou received the Ph.D. degree in Electrical Engineering and Computer Science from The University of Michigan, Ann Arbor in 1993 and is currently a professor in the Department of Computer Science at University of Illinois at Urbana Champaign (UIUC). Prior to joining UIUC, she has taught at Ohio State University and University of Wisconsin - Madison. Dr. Hou has worked in the the areas of network modeling and simualtion, wireless-enabled software infrastructure for assisted living, and capacity optimization in wireless networks. She was a recipient of an ACM Recognition of Service, a Cisco University Research Award, a Lumley Research Award from Ohio State University, and a NSF CAREER award. ^*A Shorter version of this paper appeared in ICDCS 2003.     

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.     

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.     

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.     

A Development Environment for OSA-Based Applications over the Interworked WLAN and Cellular Networks

In this paper, we propose an OSA-based development environment for interworking WLAN and 3G cellular networks. The main goal of our work is to establish and create an environment that can serve as a demonstration of a working network for OSA-based application developers while featuring mobile services over the interworked LAN and 3G cellular networks. The proposed simulating environment has (i) a location update scheme that is used to obtain mobile users' locations and status information over the interworked WLAN and cellular networks, (ii) an instant message gateway (IMG) simulator that is developed to send and receive generic messages over the interworked WLAN and cellular networks, and (iii) a mapping of Parlay APIs onto SIP signaling messages for multiparty call applications over the interworked WLAN and cellular networks. An illustrated OSA-based application that utilizes the corresponding system functions and modules is developed and verified using the proposed simulating environment. Chung-Ming Huang received the B.S. degree in Electrical Engineering from National Taiwan University on 1984/6, and the M.S. and Ph.D. degrees in Computer and Information Science from The Ohio State University on 1987/12 and 1991/6 respectively. He is currently a professor in Department of Computer Science and Information Engineering, National Cheng Kung University, Taiwan, R.O.C. He is the director of The Promotion Center for Network Applications and Services, Innovative Communication Education Project, Ministry of Education, Taiwan, R.O.C. His research interests include broadband Internet and applications, wireless and mobile network protocols, ubiquitous computing and communications, and multimedia streaming. Tz-Heng Hsu received the B.S. degree from Department of Computer Science and Information Engineering, Feng Chia University on 1996/6, and the M.S. degree and Ph.D from Department of Computer Science and Information Engineering, National Cheng Kung University on 1998/7 and 2005/7, Taiwan, R.O.C. He is currently a assistant professor in Department of Computer Science and Information Engineering, Southern Taiwan University of Technology. His research interests are wireless and mobile network protocols, applications over interworked WLAN and cellular networks and communications, and multimedia streaming. Chih-Wen Chao received the B.S. degree from Department of Engineering Science, National Cheng Kung University on 2003/6, and the M.S. degree from Department of Computer Science and Information Engineering, National Cheng Kung University on 2005/7, Taiwan, R.O.C. His research interests are OSA-based applications and distributed multimedia systems.     

Progressive meshes transmission over a wired-to-wireless network

The evolution of mobile network and the popularization of mobile devices; the demand for multimedia services and 3D graphics applications on limited resource devices is more contemporary. Most of the works on multimedia transmission are focused on bit errors and packet losses due to the fading channel environment of a wireless network. Error resilient multimedia is significant research topic which can be adapted to the different conditions in a wireless environment. The current solutions in transmission of multimedia across different networks include some type of transcoder where the source is partially or fully decoded, and re-encoded to suit the network conditions. This paper introduces a flexible progressive coding framework for 3D meshes, which can be adapted to the different conditions imposed by wired and wireless channels at the bitstream level. By avoiding the computationally complex steps of transcoding between networks, could deteriorate decoded model quality. The framework also allows refined degradation of model quality when the network conditions are poor due to congestion or deep fades. Xiaonan Luo, male, born in Feb. 1963 in Jiangxi Province, China, Ph. D., completed his post-doctorate training in Mar. 1995. He is a professor and Ph. D. advisor of the School of Information Science and Technology, and the Chairman of Computer Application Institute of Sun Yat-sen University. His current interests are in mobile graphics transmission and 3D geometric simulation methods. He enjoys the government special allowance granted by the State Council of China. He won the National Science & Technology Progress Prize awarded by the Ministry of Science and Technology of China and the National Natural Science Funds granted by the National Nature Science Foundation of China. Guifeng Zheng, male, born in Jan. 1977 in Guangdong Province, China, Ph. D., received his Ph.D. degree from Sun Yat-sen University in 2005. He is currently an research assistant in the Computer Application Institute of Sun Yat-sen University. His research interests span the areas of wireless networks and mobile graphics computing.     

Enabling Intelligent Handovers in Heterogeneous Wireless Networks

In the future Wireless Internet, mobile nodes will be able to choose between providers offering competing services at a much finer granularity than we find today. Rather than months, service contracts may span hours or minutes. Connectivity, however, is just one of many possible services. Providers will begin to offer network and application-level services targeted at improving the overall wireless experience of the user. Determining the best path through the various networks will require accurate information describing which services are being offered by each provider. In this paper, we model the process of propagating this information as an instance of a distributed, hierarchical cache. Access routers actively discover and collect information about the immediate network neighborhood on behalf of mobile nodes. Mobiles fill their own caches through queries to their local access routers, and then employ the cached information to make informed, intelligent handover decisions. Through simulation, we show that high cache hit rates at the mobile node can be achieved even when the discovery process at the access router is incomplete. In comparison to static and centralized approaches, our dynamic approach requires less configuration and maintenance, avoids single points of failure, and provides a scalable solution that spans administrative domains. Robert C. Chalmers received his B.S. in Computer Science from the California State Polytechnic University, Pomona in 1997, and his M.S. in 2003 from the University of California in Santa Barbara. He is currently a Ph.D. candidate at the University of California in Santa Barbara where his main research interests focus around leveraging intelligence within the network. Particularly, he has studied multicast and its effect on resource utilization, as well as how to provide services for small, mobile devices in edge networks. He was awarded the Ericsson Fellowship in 2001 and is currently a Eugene Cota-Robles Fellow. Govind Krishnamurthi received an M.S. (Electrical Engineering) and Ph.D. degree (Computer Engineering) from the University of Washington and the Iowa State University, in 1997 and 1999 respectively. He spent the summer of 1995 as an intern at Bellcore, Morristown, NJ. He is a recipient of the Research Excellence Award from the Iowa State University for his Ph.D. thesis. Since the summer of 1999 he has been a Senior Research Engineer at the Nokia Research Center, Boston, MA. He has authored several publications and holds 3 patents. His current interests deal with QoS, location based services and security issues in IP based wireless networks. Kevin C. Almeroth earned his Ph.D. in Computer Science from the Georgia Institute of Technology in 1997. He is currently an associate professor at the University of California in Santa Barbara where his main research interests include computer networks and protocols, multicast communication, large-scale multimedia systems, and performance evaluation. At UCSB, Dr. Almeroth is a founding member of the Media Arts and Technology Program (MATP), Associate Director of the Center for Information Technology and Society (CITS), and on the Executive Committee for the University of California Digital Media Innovation (DiMI) program. In the research community, Dr. Almeroth is on the Editorial Board of IEEE Network, has co-chaired NGC 2000, Global Internet 2001, NOSSDAV 2002, and MMNS 2002; has served as tutorial chair for several conferences, and has been on the program committee of numerous conferences. Dr. Almeroth is serving as the chair of the Internet2 Working Group on Multicast, and is a member of the IETF Multicast Directorate (MADDOGS). He is also serving on the advisory boards of several startups including Occam Networks, NCast, Hidden Footprint, and the Santa Barbara Technology Incubator.     

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.     

GRAdient Broadcast: A Robust Data Delivery Protocol for Large Scale Sensor Networks

Although data forwarding algorithms and protocols have been among the first set of issues explored in sensor networking, how to reliably deliver sensing data through a vast field of small, vulnerable sensors remains a research challenge. In this paper we present GRAdient Broadcast (GRAB), a new set of mechanisms and protocols which is designed specifically for robust data delivery in face of unreliable nodes and fallible wireless links. Similar to previous work [12,13], GRAB builds and maintains a cost field, providing each sensor the direction to forward sensing data. Different from all the previous approaches, however, GRAB forwards data along a band of interleaved mesh from each source to the receiver. GRAB controls the width of the band by the amount of credit carried in each data message, allowing the sender to adjust the robustness of data delivery. GRAB design harnesses the advantage of large scale and relies on the collective efforts of multiple nodes to deliver data, without dependency on any individual ones. We have evaluated the GRAB performance through both analysis and extensive simulation. Our analysis shows quantitatively the advantage of interleaved mesh over multiple parallel paths. Our simulation further confirms the analysis results and shows that GRAB can successfully deliver over 90% of packets with relatively low energy cost, even under the adverse conditions of 30% node failures compounded with 15% link message losses.Fan Ye received his B.E. in Automatic Control in 1996 and MS in Computer Science in 1999, both from Tsinghua University, Beijing, China. After that, he has been pursuing a Ph.D. degree at UCLA. His research interests are in network protocol design, with focus on data forwarding, power management and security in large scale sensor networks.Gary Zhong is currently pursuing M.S. degree in computer science at University of California, Los Angeles. He received his B.S. degree in computer science and engineering from University of California, Davis. His research interests include wireless networking, mobile computing, and large scale sensor networks.Songwu Lu received both his M.S. and Ph.D. from University of Illinois at Urbana-Champaign. He is currently an assistant professor at UCLA Computer Science. He received NSF CAREER award in 2001. His research interests include wireless networking, mobile computing, wireless security, and computer networks.Lixia Zhang received her Ph.D in computer science from the Massachusetts Institute of Technology. She was a member of the research staff at the Xerox Palo Alto Research Center before joining the faculty of UCLAs Computer Science Department in 1995. In the past she has served on the Internet Architecture Board, Co-Chair of IEEE Communication Society Internet Technical Committee, the editorial board for the IEEE/ACM Transactions on Networking, and technical program committees for many networking-related conferences including SIGCOMM and INFOCOM. Zhang is currently serving as the vice chair of ACM SIGCOMM.     

Parametric Probabilistic Routing in Sensor Networks

Motivated by realistic sensor network scenarios that have mis-in-formed nodes and variable network topologies, we propose an approach to routing that combines the best features of limited-flooding and information-sensitive path-finding protocols into a reliable, low-power method that can make delivery guarantees independent of parameter values or information noise levels. We introduce Parametric Probabilistic Sensor Network Routing Protocols, a family of light-weight and robust multi-path routing protocols for sensor networks in which an intermediate sensor decides to forward a message with a probability that depends on various parameters, such as the distance of the sensor to the destination, the distance of the source sensor to the destination, or the number of hops a packet has already traveled. We propose two protocol variants of this family and compare the new methods to other probabilistic and deterministic protocols, namely constant-probability gossiping, uncontrolled flooding, random wandering, shortest path routing (and a variation), and a load-spreading shortest-path protocol inspired by (Servetto and Barrenechea, 2002). We consider sensor networks where a sensor’s knowledge of the local or global information is uncertain (parametrically noised) due to sensor mobility, and investigate the trade-off between robustness of the protocol as measured by quality of service (in particular, successful delivery rate and delivery lag) and use of resources (total network load). Our results for networks with randomly placed nodes and realistic urban networks with varying density show that the multi-path protocols are less sensitive to misinformation, and suggest that in the presence of noisy data, a limited flooding strategy will actually perform better and use fewer resources than an attempted single-path routing strategy, with the Parametric Probabilistic Sensor Network Routing Protocols outperforming other protocols. Our results also suggest that protocols using network information perform better than protocols that do not, even in the presence of strong noise. Christopher L. Barrett is leader of the Basic and Applied Simulation Science Group of the Computing and Computational Sciences Division at Los Alamos National Laboratory. His Group is a simulation science and technology (S&T) invention organization of 30 scientists devoted to providing large-scale, high performance methods for systems analysis and simulation-based assisted reasoning. His Group engages in fundamental mathematical, algorithmic, and complex systems analysis research. Current applied research is focused on interdependent simulation and analysis tools for complex, socio-technical systems like transportation, communications, public health and other critical infrastructure areas. His scientific experience is in simulation, scientific computation, algorithm theory and development, system science and control, engineering science, bio-systems analysis, decision science, cognitive human factors, testing and training. His applied science and engineering achievements include, for example, development of large-scale, high performance simulation systems (e.g., Transportation Analysis Simulation System, TRANSIMS) and development of a distributed computing approach for detailed simulation-based study of mobile, packet switched digital communications systems (Self Organizing Stochastic Rebroadcast Relay, SORSRER). He has a M.S. and Ph.D. in Bio-information Systems from California Institute of Technology. He is a decorated Navy veteran having served in both the submarine service and as a pilot. He has been awarded three Distinguished Service Awards from Los Alamos National Laboratory, one from the Alliance for Transportation Research, one from the Royal Institute of Technology, Stockholm, and one from Artificial Life and Robotics, Oita University, Japan. Stephan J. Eidenbenz is a technical staff member in the Basic and Applied Simulation Science group (CCS-5) at Los Alamos National Laboratory (LANL). He received an M.Sc. in Computer Science from the Swiss Federal Institute of Technology (ETH) in Zurich in 1997 and a Ph.D. in Computer Science from ETH in 2000; he also obtained a Bachelor’s degree in business administration from GSBA in Zurich in 1999. Stephan has worked for McKinsey & Co. in Switzerland, where he received training in business administration and microeconomics. He has held a postdoctoral position at ETH and he has been a postdoctoral fellow at LANL. Stephan’s more than 30 publications cover a wide range of subjects such as approximability and inapproximability properties of visibility problems in polygons and terrains, error modeling in sequencing problems for computation biology, and designing communication protocols robust against selfish behavior. His current research interests include selfish networking, algorithmic game theory, network modeling and simulation, network design, and network optimization. Lukas Kroc is a student of M.Sc. program in Computer Science at Charles University in Prague. In 2003, he was a Graduate Research Assistant at the Basic and Applied Simulation Science group (CCS-5) at Los Alamos National Laboratory. His research interests include simulation, wireless networking and artificial intelligence. Madhav V. Marathe is a Team Leader for Mathematics and Computer Science in the Basic and Applied Simulation Science group, Computer and Computational Sciences (CCS-5) at the Los Alamos National Laboratory. He obtained his B.Tech in 1989 in Computer Science and Engg. from IIT Madras, India and his Ph.D. in 1994 in Computer Science, from University at Albany. His team focuses on developing mathematical and computational tools for design and analysis of large scale simulations of socio-technical and critical infrastructure systems. His research interests are in modeling and simulations of large socio-technical systems, design and analysis of algorithms, computational complexity theory, theory of parallel, distributed and mobile computing and communication systems. He has published over 100 research articles in peer reviewed journals and conferences. He is an adjunct faculty in the Computer Science Department at the University of New Mexico. James P. Smith is a technical staff member in the Basic and Applied Simulation Science Group of the Computing and Computational Sciences Division at Los Alamos National Laboratory. His principal interest is in high performance computing applied to modeling, simulation and analysis of socio-technical systems. His current research applies to national infrastructure, especially telecommunication/computing, public health, and transportation. He has scientific experience in high performance computing and parallel processing applied to large-scale microscopic simulations, including original software design and debugging of very large, evolving systems of inter-operable computational systems, and efficient analysis and synthesis of massive data produced by multi-scale complex environments. Before attending graduate school he worked for a short time in nuclear theory, and had several publications in experimental biophysics from the Pennsylvania Muscle Institute and Bockus Research Institute. During graduate school he took a one year hiatus to start a company to work in analytic finance, and then spent time doing theoretical space physics at LANL. His graduate work eventually included theoretical and experimental fusion research, but concentrated on computational space plasma physics. He has publications in biophysics, analytic finance, education, space plasma physics and computer science, and is a co-inventor on the TRANSIMS patent. He has a Ph.D. in Theoretical Plasma Physics from the University of Texas at Austin.This revised version was published online in August 2005 with a corrected cover date.     

Towards Designing a Trusted Routing Solution in Mobile Ad Hoc Networks

Designing a trusted and secure routing solution in an untrustworthy scenario is always a challenging problem. Lack of physical security and low trust levels among nodes in an ad hoc network demands a secure end-to-end route free of any malicious entity. This is particularly challenging when malicious nodes collude with one another to disrupt the network operation. In this paper we have designed a secure routing solution to find an end-to-end route free of malicious nodes with collaborative effort from the neighbors. We have also extended the solution to secure the network against colluding malicious nodes, which, to the best of our knowledge, is the first such solution proposed. We have also proposed a framework for computing and distributing trusts that can be used with out trusted routing protocol. Our proposed framework is unique and different from the other schemes in that it tries to analyze the psychology of the attacker and quantifies the behavior in the computational model. Extensive simulation has been carried out to evaluate the design of our protocol. Partially funded by Department of Defense Award No. H98230-04-C-0460, Department of Transportation Project No. FL-26-7102-00 and National Science Foundation Grant Nos. ANI-0123950 and CCR-0196557. Tirthankar Ghosh is a PhD candidate in the Telecommunications and Information Technology Institute at Florida International University. His area of research is routing security and trust computation in wireless ad hoc and sensor networks. He received his Bachelor of Electrical Engineering from Jadavpur University, India and Masters in Computer Engineering from Florida International University. Dr. Niki Pissinou received her Ph.D. in Computer Science from the University of Southern California, her M.S. in Computer Science from the University of California at Riverside, and her B.S.I.S.E. in Industrial and Systems Engineering from The Ohio State University. She is currently a tenured professor and the director of the Telecommunication & Information Technology Institute at FIU. Previously Dr. Pissinou was a tenured faculty at the Center for Advanced Computer Studies at the University of Louisiana at Lafayette where she was also the director of the Telecommunication & Information & Technology Laboratory partially funded by NASA, and the co-director of the NOMAD: A Wireless and Nomadic Laboratory partially funded by NSF, and the Advanced Network Laboratory. Dr. Pissinou is active in the fields computer networks, information technology and distributed systems. Dr. Kami (Sam) Makki has earned his Ph.D. in Computer Science from the University of Queensland in Brisbane Australia, his Masters degree in Computer Science and Engineering from the University of New South Wales in Sydney Australia, and his Bachelor and Masters Degrees in Civil Engineering from the University of Tehran Iran. Before joining the department of Electrical Engineering and Computer Science at the University of Toledo he has held a number of academic positions and research appointments at the Queensland University of Technology in Brisbane, Royal Melbourne Institution of Technology in Melbourne and at The University of Queensland in Brisbane Australia. He is an active researcher in the fields of distributed systems, databases, mobile and wireless communications, and has more than 30 publications in peerreviewed journals and international proceedings. He has served as a chair and technical program committee member and reviewer for a number of IEEE and ACM sponsored technical conferences and has received a number of achievement awards.     

A Virtual MAC Address Scheme for Mobile Ethernet

Heterogeneous wireless access is being integrated into IP networks to support future wireless systems. The enhanced IP technologies being developed must address both handover issues related to mobility management and security issues related to wireless access. We previously proposed a network architecture, Mobile Ethernet, based on wide area Ethernet technologies, that reduces overhead involving handover by managing mobility in the IEEE802 MAC layer. We also proposed a virtual MAC address scheme that introduces a host identifier into layer 2 to accommodate heterogeneous wireless access, manage handover between wireless accesses, provide scalability, and ensure security. In this paper, we design the virtual MAC address scheme for Mobile Ethernet and describe the sequence diagrams of the scheme. We also clarify the effect of our proposed scheme from the viewpoint of scalability by comparing the simulated signaling traffic load at handover with that using FMIPv6. Yoshia Saito received his B.E. and M.E. degrees from Shizuoka University, Shizuoka, Japan, in 2002 and 2003 respectively. He is currently a student in Ph.D. course in the university. From January 2004, he is also working as a visiting researcher at National Institute of Information and Communications Technology, Yokosuka, Japan. His research interests include mobile computing and next generation wireless systems. Masahiro Kuroda received the M.E. degree in systems science from the Tokyo Institute of Technology, Japan, in 1980, the M.S. degree in computer science from University of California, Santa Barbara, CA, in 1989, and received the Ph.D. degree in computer science from Shizuoka University, Japan, in 2000. He joined Mitsubishi Electric Corporation, Kamakura, Japan in 1980. Since then, he was engaged in OS/network developments, mobile network computing R&D, and cellular Java standardizations. He is currently working as a group leader at National Institute of Information and Communications Technology, Yokosuka, Japan. His current research interests includes wireless network, wireless security, mobile systems, ubiquitous systems, and next generation wireless systems architecture. He is a member of the IEEE Computer Society. Tadanori Mizuno received the B.E. degree in industrial engineering from the Nagoya Institute of Technology in 1968 and received the Ph.D. degree in computer science from Kyushu University, Japan, in 1987. In 1968, he joined Mitsubishi Electric Corp. Since 1993, he is a Professor of Faculty of Engineering, Shizuoka University, Japan. He moved to the Faculty of Information, Shizuoka University in 1995. His research interests include mobile computing, distributed computing, computer networks, broadcast communication and computing, and protocol engineering. He is a member of Information Processing Society of Japan, the institute of electronics, information and Communication Engineers, the IEEE Computer Society and ACM.     

How is the capacity of ad hoc networks improved with directional antennas?

The capacity of wireless ad hoc networks is constrained by the interference caused by the neighboring nodes. Gupta and Kumar have shown that the throughput for such networks is only Θ bits per second per node in a unit area domain when omnidirectional antennas are used [1]. In this paper we investigate the capacity of ad hoc wireless networks using directional antennas. Using directional antennas reduces the interference area caused by each node, thus increases the capacity of the network. We will give an expression for the capacity gain and we argue that in the limit, when the beam-width goes to zero the wireless network behaves like the wired network. In our analysis we consider both arbitrary networks and random networks where nodes are assumed to be static. We have also analyzed hybrid beamform patterns that are a mix of omnidirectional/directional and a better model of real directional antennas. Simulations are conducted for validation of our analytical results. Su Yi received the B.S. and M.S degrees in automation from Tsinghua University, China, in 1998 and 2001, respectively. She received her Ph.D. degree in electrical engineering from Rensselaer Polytechnic Institute, in December 2005. Her research interests include various topics in wireless ad hoc networks, including capacity of wireless networks, error control coding, and multimedia communications over wireless. Yong Pei is currently a tenure-track assistant professor in the Computer Science and Engineering Department, Wright State University, Dayton, OH. Previously he was a visiting assistant professor in the Electrical and Computer Engineering Department, University of Miami, Coral Gables, FL. He received his B.S. degree in electrical power engineering from Tsinghua University, Beijing, in 1996, and M.S. and Ph.D. degrees in electrical engineering from Rensselaer Polytechnic Institute, Troy, NY, in 1999 and 2002, respectively. His research interests include information theory, wireless communication systems and networks, and image/video compression and communications. He is a member of IEEE and ACM. Shivkumar Kalyanaraman is an Associate Professor at the Department of Electrical, Computer and Systems Engineering at Rensselaer Polytechnic Institute in Troy, NY. He received a B.Tech degree from the Indian institute of Technology, Madras, India in July 1993, followed by M.S. and Ph.D. degrees in computer and Information Sciences at the Ohio State University in 1994 and 1997 respectively. His research interests are in network traffic management topics such as congestion control, reliability, connectionless traffic engineering, quality of service (QoS), last-mile community wireless networks, low-cost free-space-optical networks, automated network management using online simulation, multicast, multimedia networking, and performance analysis. His special interest lies in developing the interdisciplinary connections between network architecture and fields like control theory, economics, scalable simulation technologies, video compression and optoelectronics. He is a member of ACM and IEEE. Babak Azimi-Sadjadi received his B.Sc. from Sharif University of Technology in 1989, his M.Sc. from Tehran University in 1992, and his Ph.D. from the University of Maryland at College Park in 2001 all in Electrical Engineering. He is currently with Intelligent Automation Inc. where he is a Senior Research Scientist He also has a joint appointment with the department of Electrical, Systems, and Computer Engineering of Rensselaer Polytechnic Institute where he is a research assistant professor. His research interests include, nonlinear filtering, networked control systems, and wireless networks.     

Energy efficient node-to-node authentication and communication confidentiality in wireless sensor networks

A distributed Wireless Sensor Network (WSN) is a collection of low-end devices with wireless message exchange capabilities. Due to the scarcity of hardware resources, the lack of network infrastructures, and the threats to security, implementing secure pair-wise communications among any pair of sensors is a challenging problem in distributed WSNs. In particular, memory and energy consumption as well as resilience to sensor physical compromise are the most stringent requirements. In this paper, we introduce a new threat model to communications confidentiality in WSNs, the smart attacker model. Under this new, more realistic model, the security features of previously proposed schemes decrease drastically. We then describe a novel pseudo-random key pre-deployment strategy ESP that combines all the following properties: (a) it supports an energy-efficient key discovery phase requiring no communications; (b) it provides node to node authentication; (c) it is highly resistant to the smart attacker.We provide both asymptotic results and extensive simulations of the schemes that are beingproposed. This work was partially funded by the WEB-MINDS project supported by the Italian MIUR under the FIRB program, and by the PRIN 2003 “Web-based Management and Representation of Spatial and Geographic Data” program from the Italian MIUR. Roberto Di Pietro is partially funded by ISTI-CNR, WNLab, Pisa, with a Post-doc grant under the IS-MANET program. Roberto Di Pietro received the Ph.D. in Computer Science from the University of Roma “La Sapienza”, Italy, in 2004. He received the Bs. and Ms. degree in Computer Science from the University of Pisa, Italy, in 1994. Since 1995 he has been working for the technical branch of the Italian Army and the Internal Affairs Ministry. His main research interests include: security for mobile ad hoc and wireless networks, security for distributed systems, secure multicast, applied cryptography and computer forensics. Luigi V. Mancini received the PhD degre in Computer Science from the University of Newcastle upon Tyne, UK, in 1989, and the Laurea degree in Computer Science from the University of Pisa, Italy, in 1983. From 2000, he is a full professor of Computer Science at the Dipartimento di Informatica of the University of Rome “La Sapienza”. Since 1994, he is a visiting research professor of the Center for Secure Information Systems, GMU, Virginia, USA. Currently he is the advisor of six Ph.D students. His current research interests include: computer network and information security, wireless network security, fault-tolerant distributed systems, large-scale peer-to-peer systems, and hard-real-time distributed systems. He published more than 60 scientific papers in international conferences and journals such as: ACM TISSEC, IEEE TKDE, IEEE TPDS, and IEEE TSE. He served in the program committees of several international conferences which include: ACM Conference on Computer and Communication Security, ACM Conference on Conceptual Modeling, ACM Symposium on Access Control Models and Technology, ACM Workshop of Security of Ad-hoc and Sensor Networks, IEEE Securecomm, IEEE Conference on Cluster Computing. He is also the program chair of the first two editions of the IEEE Workshop on Hot Topics in Peer-to-Peer Systems held in 2004 (Volendam, Holand) and in 2005 (San Diego, California). Currently, he is a member of the Scientific Board of the Italian Communication Police force, and the director of the Master degree program in Computer and Network Security of the University of Rome “La Sapienza”, Italy. Alessandro Mei received the Laurea degree in computer science from the University of Pisa, Italy, in 1994, and the PhD degree in mathematics from the University of Trento, Italy, in 1999. In 1998, he was at the Department of EE-Systems of the University of Southern California, Los Angeles, as a visiting scholar for one year. After holding a postdoctoral position at the University of Trento, in 2001 he joined the Faculty of Science of the University of Rome "La Sapienza", Italy, as an assistant professor of computer science. His main research interests include security of distributed systems and networks, algorithms for parallel, distributed, and optical systems and reconfigurable computing. He was presented with the Best Paper Award of the 16th IEEE International Parallel and Distributed Processing Symposium in 2002, the EE-Systems Outstanding Research Paper Award of the University of Southern California for 2000, and the Outstanding Paper Award of the Fifth IEEE/ACM International Conference on High Performance Computing in 1998. He is a member of the ACM and the IEEE and, from 2005, he is an Associate Editor of IEEE Transactions on Computers.     

A Network Layer Approach to Enable TCP over Multiple Interfaces

The mobile Internet is set to become ubiquitous with the deployment of various wireless technologies. When heterogeneous wireless networks overlap in coverage, a mobile terminal can potentially use multiple wireless interfaces simultaneously. In this paper, we motivate the advantages of simultaneous use of multiple interfaces and present a network layer architecture that supports diverse multi-access services. Our main focus is on one such service provided by the architecture: Bandwidth Aggregation (BAG), specifically for TCP applications.While aggregating bandwidth across multiple interfaces can improve raw throughput, it introduces challenges in the form of packet reordering for TCP applications. When packets are reordered, TCP misinterprets the duplicate ACKS received as indicative of packet loss and invokes congestion control. This can significantly lower TCP throughput and counter any gains that can be had through bandwidth aggregation. To improve overall performance of TCP, we take a two-pronged approach: (1) We propose a scheduling algorithm that partitions traffic onto the different paths (corresponding to each interface) such that reordering is minimized. The algorithm estimates available bandwidth and thereby minimizes reordering by sending packet pairs on the path that introduces the least amount of delay. (2) A buffer management policy is introduced at the client to hide any residual reordering from TCP. We show through simulations that our network-layer approach can achieve good bandwidth aggregation under a variety of network conditions.Kameswari Chebrolu is an assistant professor in the electrical department of Indian Institute of Technology, Kanpur. Her research interests are in the areas of wireless network architecture, protocol design and analysis. Kameswari obtained her M.S. and Ph.D. degree in Electrical and Computer Engineering from University of California at San Diego, in 2001 and 2004 respectively.Bhaskaran Raman received his B.Tech in Computer Science and Engineering from Indian Institute of Technology, Madras in May 1997. He received his M.S. and Ph.D. in Computer Science from University of California, Berkeley, in 1999 and 2002 respectively. He joined as faculty in the CSE department at Indian Institute of Technology, Kanpur (India) starting June 2003. His research interests and expertise are in communication networks, wireless/mobile networks, large-scale Internet-based systems, and Internet middleware services.Ramesh R. Rao is a professor at the University of California, San Diego (UCSD). He is a member of the faculty of Irwin and Joan Jacobs School of Engineering, since 1984. Professor Rao is the former director of UCSD’s Center for Wireless Communications (CWC), and the current Director of the San Diego Division of the California Institute of Telecommunications and Information Technology [Cal-(IT)²]. As Director of the San Diego Division of Cal-(IT)², he leads several interdisciplinary, collaborative projects. His research interests include architectures, protocols and performance analysis of computer and communication networks, and he has published extensively on these topics. He received his B.E. from the University of Madras and his M.S. and Ph.D. from the University of Maryland at College Park. Most recently, Dr. Rao was honored by being appointed the first holder of the Qualcomm Endowed Chair in Telecommunications and Information Technologies.     

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 .