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.     

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 .     

M<Emphasis Type="SmallCaps">AP</Emphasis>: Medial axis based geometric routing in sensor networks

One of the challenging tasks in the deployment of dense wireless networks (like sensor networks) is in devising a routing scheme for node to node communication. Important consideration includes scalability, routing complexity, quality of communication paths and the load sharing of the routes. In this paper, we show that a compact and expressive abstraction of network connectivity by the medial axis enables efficient and localized routing. We propose MAP, a Medial Axis based naming and routing Protocol that does not require geographical locations, makes routing decisions locally, and achieves good load balancing. In its preprocessing phase, MAP constructs the medial axis of the sensor field, defined as the set of nodes with at least two closest boundary nodes. The medial axis of the network captures both the complex geometry and non-trivial topology of the sensor field. It can be represented succinctly by a graph whose size is in the order of the complexity of the geometric features (e.g., the number of holes). Each node is then given a name related to its position with respect to the medial axis. The routing scheme is derived through local decisions based on the names of the source and destination nodes and guarantees delivery with reasonable and natural routes. We show by both theoretical analysis and simulations that our medial axis based geometric routing scheme is scalable, produces short routes, achieves excellent load balancing, and is very robust to variations in the network model. A preliminary version appeared in ACM International Conference on Mobile Computing and Networking (MobiCom’05), August, 2005. This work was supported in part by the Lee Center for Advanced Networking at the California Institute of Technology, and by NSF grant CCR-TC-0209042. Jie Gao’s work was done at Center for the Mathematics of Information, California Institute of Technology, Pasadena, CA 91125. Anxiao (Andrew) Jiang’s work was done at Department of Electrical Engineering, California Institute of Technology, Pasadena, CA 91125. Jehoshua Bruck is the Gordon and Betty Moore Professor of Computation and Neural Systems and Electrical Engineering at the California Institute of Technology. During 2003–2005 he served as the founding Director of Caltech's Information Science and Technology (IST) program. He received the B.Sc. and M.Sc. degrees in electrical engineering from the Technion, Israel Institute of Technology, in 1982 and 1985, respectively and the Ph.D. degree in Electrical Engineering from Stanford University in 1989. His research combines work on the design of distributed information systems and the theoretical study of biological circuits and systems. Dr. Bruck has an extensive industrial experience, including working with IBM Research for ten years where he participated in the design and implementation of the first IBM parallel computer. He was a co-founder and chairman of Rainfinity (acquired in 2005 by EMC), a spin-off company from Caltech that focused on software products for management of network information systems. He is an IEEE fellow, and his awards include the National Science Foundation Young Investigator award and the Sloan fellowship. He published more than 200 journal and conference papers and he holds 25 US patents. His papers were recognized in journals and conferences, including, winning the 2005 S. A. Schelkunoff Transactions prize paper award from the IEEE Antennas and Propagation society and the 2003 Best Paper Award in the 2003 Design Automation Conference. Jie Gao received her Ph.D in computer science from Stanford University in 2004, and her BS degree from University of Science and Technology of China in 1999. She is currently an assistant professor at Computer Science department, State University of New York, Stony Brook. Her research interests include algorithms, ad hoc communication and sensor networks, and computational geometry. Anxiao (Andrew) Jiang received the B.S. degree with honors in 1999 from the Department of Electronic Engineering, Tsinghua University, Beijing, China, and the M.S. and Ph.D. degrees in 2000 and 2004, respectively, from the Department of Electrical Engineering, California Institute of Technology. He is currently an assistant professor in the Department of Computer Science, Texas A&M University. He was a recipient of the four-year Engineering Division Fellowship from the California Institute of Technology in 1999. His research interests include algorithm design, ad hoc communication and sensor networks, and file storage and retrieval.     

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.     

Graphical properties of easily localizable sensor networks

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

Analysis of bandwidth allocation algorithms for wireless personal area networks

A major issue in the design and operation of ad hoc networks is sharing the common spectrum among links in the same geographic area. Bandwidth allocation, to optimize the performance of networks in which each station can converse with at most a single neighbor at a time, has been recently studied in the context of Bluetooth Personal Area Networks. There, centralized and distributed, capacity assignment heuristics were developed, with applicability to a variety of ad hoc networks. Yet, no guarantees on the performance of these heuristics have been provided. In this paper, we extend these heuristics such that they can operate with general convex objective functions. Then, we present our analytic results regarding these heuristics. Specifically, we show that they are β-approximation (β<2) algorithms. Moreover, we show that even though the distributed and centralized algorithms allocate capacity in a different manner, both algorithms converge to the same results. Finally, we present numerical results that demonstrate the performance of the algorithms. Randeep Bhatia received the Ph.D. degree in Computer Science from University of Maryland, the M.S. degree in Mathematics and Computer Science from University of Illinois at Chicago and the B.Tech. degree in Computer Science and Engineering from Indian Institute of Technology, Delhi. He is currently with the High Speed Networks Research Department at Bell Labs, Lucent technologies, working on network design, traffic engineering and scheduling algorithms. His current research interests are in the area of QoS for multimedia services in wireless data networks. Adrian Segall received the B.Sc. and M.Sc. degrees in electrical engineering from the Technion, Israel Institute of Technology in 1965 and 1971, respectively, and the Ph.D. degree in electrical engineering with a minor in statistics from Stanford University in 1973. After serving active duty in the Israel Defense Forces, he joined in 1968 the Scientific Department of Israel’s Ministry of Defense. From 1973 to 1974 he was a Research Engineer at System Control Inc., Palo Alto, CA and a Lecturer at Stanford University. From 1974 to 1976 he was an Assistant Professor of Electrical Engineering and Computer Science at the Massachusetts Institute of Technology. From 1987 to 1998 he was on the faculty of the Department of Computer Science at the Technion. He is presently Benjamin Professor of Computer-Communication Networks in the Department of Electrical Engineering, Technion, Israel Institute of Technology. From 1982 to 1984 he was on leave with the IBM T.J.Watson Research Center, Yorktown Heights, NY. He held visiting positions with IBM, AT&T and Lucent Bell Labs. His current research interests are in the area of optical networks, wireless, sensor and ad-hoc networks. Dr. Segall is an IEEE Fellow and has served in the past as Editor for Computer Communication Theory of the IEEE Transactions on Communications, Editor for the IEEE Information Theory Society Newsletter and Senior Editor for the IEEE Journal on Selected Areas in Communications. He was selected as an IEEE delegate to the 1975 IEEE-USSR Information Theory Workshop, and is the recipient of the 1981 Miriam and Ray Klein Award for Outstanding Research and of the 1990 Taub Award in Computer Science. Gil Zussman received the B.Sc. degree in Industrial Engineering and Management and the B.A. degree in Economics (both summa cum laude) from the Technion—Israel Institute of Technology in 1995. He received the M.Sc. degree (summa cum laude) in Operations Research from Tel-Aviv University in 1999 and the Ph.D. degree in Electrical Engineering from the Technion—Israel Institute of Technology in 2004. Between 1995 and 1998, he served as an engineer in the Israel Defense Forces. He is currently a Postdoctoral Associate in the Laboratory for Information and Decision Systems in MIT. His current research interests are in the area of ad hoc and sensor networks. In particular, he is interested in energy efficient protocols, medium access control protocols, and personal area networks. Gil received the Knesset (Israeli Parliament) Award for distinguished students, the Best Student Paper Award at the IFIP-TC6 Networking 2002 Conference, and the IEEE Communications Magazine Best Paper Award at the OPNETWORK 2002 Conference. In 2004 he received the Marie Curie Outgoing International Fellowship and the Fulbright Fellowship.     

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.     

Localized algorithms for coverage boundary detection in wireless sensor networks

Connected coverage, which reflects how well a target field is monitored under the base station, is the most important performance metric used to measure the quality of surveillance that wireless sensor networks (WSNs) can provide. To facilitate the measurement of this metric, we propose two novel algorithms for individual sensor nodes to identify whether they are on the coverage boundary, i.e., the boundary of a coverage hole or network partition. Our algorithms are based on two novel computational geometric techniques called localized Voronoi and neighbor embracing polygons. Compared to previous work, our algorithms can be applied to WSNs of arbitrary topologies. The algorithms are fully distributed in the sense that only the minimal position information of one-hop neighbors and a limited number of simple local computations are needed, and thus are of high scalability and energy efficiency. We show the correctness and efficiency of our algorithms by theoretical proofs and extensive simulations. Chi Zhang received the B.E. and M.E. degrees in Electrical Engineering from Huazhong University of Science and Technology, Wuhan, China, in July 1999 and January 2002, respectively. Since September 2004, he has been working towards the Ph.D. degree in the Department of Electrical and Computer Engineering at the University of Florida, Gainesville, Florida, USA. His research interests are network and distributed system security, wireless networking, and mobile computing, with emphasis on mobile ad hoc networks, wireless sensor networks, wireless mesh networks, and heterogeneous wired/wireless networks. Yanchao Zhang received the B.E. degree in computer communications from Nanjing University of Posts and Telecommunications, Nanjing, China, in July 1999, the M.E. degree in computer applications from Beijing University of Posts and Telecommunications, Beijing, China, in April 2002, and the Ph.D. degree in electrical and computer engineering from the University of Florida, Gainesville, in August 2006. Since September 2006, he has been an Assistant Professor in the Department of Electrical and Computer Engineering, New Jersey Institute of Technology, Newark. His research interest include wireless and Internet security, wireless networking, and mobile computing. He is a member of the IEEE and ACM. Yuguang Fang received the BS and MS degrees in Mathematics from Qufu Normal University, Qufu, Shandong, China, in 1984 and 1987, respectively, a Ph.D. degree in Systems and Control Engineering from Department of Systems, Control and Industrial Engineering at Case Western Reserve University, Cleveland, Ohio, in January 1994, and a Ph.D. degree in Electrical Engineering from Department of Electrical and Computer Engineering at Boston University, Massachusetts, in May 1997. From 1987 to 1988, he held research and teaching position in both Department of Mathematics and the Institute of Automation at Qufu Normal University. From September 1989 to December 1993, he was a teaching/research assistant in Department of Systems, Control and Industrial Engineering at Case Western Reserve University, where he held a research associate position from January 1994 to May 1994. He held a post-doctoral position in Department of Electrical and Computer Engineering at Boston University from June 1994 to August 1995. From September 1995 to May 1997, he was a research assistant in Department of Electrical and Computer Engineering at Boston University. From June 1997 to July 1998, he was a Visiting Assistant Professor in Department of Electrical Engineering at the University of Texas at Dallas. From July 1998 to May 2000, he was an Assistant Professor in the Department of Electrical and Computer Engineering at New Jersey Institute of Technology, Newark, New Jersey. In May 2000, he joined the Department of Electrical and Computer Engineering at University of Florida, Gainesville, Florida, where he got early promotion to Associate Professor with tenure in August 2003, and to Full Professor in August 2005. His research interests span many areas including wireless networks, mobile computing, mobile communications, wireless security, automatic control, and neural networks. He has published over one hundred and fifty (150) papers in refereed professional journals and conferences. He received the National Science Foundation Faculty Early Career Award in 2001 and the Office of Naval Research Young Investigator Award in 2002. He also received the 2001 CAST Academic Award. He is listed in Marquis Who’s Who in Science and Engineering, Who’s Who in America and Who’s Who in World. Dr. Fang has actively engaged in many professional activities. He is a senior member of the IEEE and a member of the ACM. He is an Editor for IEEE Transactions on Communications, an Editor for IEEE Transactions on Wireless Communications, an Editor for IEEE Transactions on Mobile Computing, an Editor for ACM Wireless Networks, and an Editor for IEEE Wireless Communications. He was an Editor for IEEE Journal on Selected Areas in Communications:Wireless Communications Series, an Area Editor for ACM Mobile Computing and Communications Review, an Editor for Wiley International Journal on Wireless Communications and Mobile Computing, and Feature Editor for Scanning the Literature in IEEE Personal Communications. He has also actively involved with many professional conferences such as ACM MobiCom’02 (Committee Co-Chair for Student Travel Award), MobiCom’01, IEEE INFOCOM’06, INFOCOM’05 (Vice-Chair for Technical Program Committee), INFOCOM’04, INFOCOM’03, INFOCOM’00, INFOCOM’98, IEEE WCNC’04, WCNC’02, WCNC’00 Technical Program Vice-Chair), WCNC’99, IEEE Globecom’04 (Symposium Co-Chair), Globecom’02, and International Conference on Computer Communications and Networking (IC3N) (Technical Program Vice-Chair).     

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.     

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

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

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.     

Cross-layer optimization for end-to-end rate allocation in multi-radio wireless mesh networks

In this paper, we study rate allocation for a set of end-to-end communication sessions in multi-radio wireless mesh networks. We propose cross-layer schemes to solve the joint rate allocation, routing, scheduling, power control and channel assignment problems with the goals of maximizing network throughput and achieving certain fairness. Fairness is addressed using both a simplified max-min fairness model and the well-known proportional fairness model. Our schemes can also offer performance upper bounds such as an upper bound on the maximum throughput. Numerical results show that our proportional fair rate allocation scheme achieves a good tradeoff between throughput and fairness. Jian Tang is an assistant professor in the Department of Computer Science at Montana State University. He received the Ph.D. degree in Computer Science from Arizona State University in 2006. His research interest is in the area of wireless networking and mobile computing. He has served on the technical program committees of multiple international conferences, including ICC, Globecom, IPCCC and QShine. He will also serve as a publicity co-chair of International Conference on Autonomic Computing and Communication Systems (Autonomics’2007). Guoliang Xue is a Full Professor in the Department of Computer Science and Engineering at Arizona State University. He received the Ph.D. degree in Computer Science from the University of Minnesota in 1991 and has held previous positions at the Army High Performance Computing Research Center and the University of Vermont. His research interests include efficient algorithms for optimization problems in networking, with applications to fault tolerance, robustness, and privacy issues in networks ranging from WDM optical networks to wireless ad hoc and sensor networks. He has published over 150 papers in these areas. His research has been continuously supported by federal agencies including NSF and ARO. He is the recipient of an NSF Research Initiation Award in 1994 and an NSF-ITR Award in 2003. He is an Associate Editor of Computer Networks (COMNET), the IEEE Network Magazine, and Journal of Global Optimization. He has served on the executive/program committees of many IEEE conferences, including INFOCOM, SECON, IWQOS, ICC, GLOBECOM and QShine. He is the General Chair of IEEE IPCCC’2005, a TPC co-Chair of IPCCC’2003, HPSR’2004, IEEE Globecom’2006 Symposium on Wireless Ad Hoc and Sensor Networks, IEEE ICC’2007 Symposium on Wireless Ad Hoc and Sensor Networks, and QShine’2007. He is a senior member of IEEE. Weiyi Zhang received the M.E. degree in 1999 from Southeast University, China. Currently he is a Ph.D. student in the Department of Computer Science and Engineering at Arizona State University. His research interests include reliable communication in networking, protection and restoration in WDM networks, and QoS provisioning in communication networks.     

Mobile multi-layered IPsec

To achieve high throughput in wireless networks, smart forwarding and processing of packets in access routers is critical for overcoming the effects of the wireless links. However, these services cannot be provided if data sessions are protected using end-to-end encryption as with IPsec, because the information needed by these algorithms resides inside the portion of the packet that is encrypted, and can therefore not be used by the access routers. A previously proposed protocol, called Multi-layered IPsec (ML-IPsec) modifies IPsec in a way so that certain portions of the datagram may be exposed to intermediate network elements, enabling these elements to provide performance enhancements. In this paper we extend ML-IPsec to deal with mobility and make it suitable for wireless networks. We define and implement an efficient key distribution protocol to enable fast ML-IPsec session initialization, and two mobility protocols that are compatible with Mobile IP and maintain ML-IPsec sessions. Our measurements show that, depending on the mobility protocol chosen, integrated Mobile IP/ML-IPsec handoffs result in a pause of 53–100 milliseconds, of which only 28–75 milliseconds may be attributed to ML-IPsec. Further, we provide detailed discussion and performance measurements of our MML-IPsec implementation. We find the resulting protocol, when coupled with SNOOP, greatly increases throughput over scenarios using standard TCP over IPsec (165% on average). By profiling the MML-IPsec implementation, we determine the bottleneck to be sending packets over the wireless link. In addition, we propose and implement an extension to MML-IPsec, called dynamic MML-IPsec, in which a flow may switch between plaintext, IPsec and MML-IPsec. Using dynamic MML-IPsec, we can balance the tradeoff between performance and security. Heesook Choi is a Ph.D. candidate in the Department of Computer Science and Engineering at the Pennsylvania State University. She received her B.S. degree in Computer Science and Statistics and M.S. degree in Computer Science from the Chungnam National University, Korea, in 1990 and 1992 respectively. She was a senior research staff in Electronics and Telecommunications Research Institute (ETRI) in Korea before she enrolled in the Ph.D. program at the Pennsylvania State University in August 2002. Her research interests lie in security and privacy in distributed systems and wireless mobile networks, focusing on designing algorithms and conducting system research. Hui Song is a Ph.D. candidate in the Department of Computer Science and Engineering at the Pennsylvania State University, University Park. He received the M.E. degree in Computer Science from Tsinghua University, China in 2000. His research interests are in the areas of network and system security, wireless ad-hoc and sensor networks, and mobile computing. He was a recipient of the research assistant award of the Department of Computer Science and Engineering at the Pennsylvania State University in 2005. Guohong Cao received his BS degree from Xian Jiaotong University, Xian, China. He received the MS degree and Ph.D. degree in computer science from the Ohio State University in 1997 and 1999 respectively. Since then, he has been with the Department of Computer Science and Engineering at the Pennsylvania State University, where he is currently an Associate Professor. His research interests are wireless networks and mobile computing. He has published over one hundred papers in the areas of sensor networks, wireless network security, data dissemination, resource management, and distributed fault-tolerant computing. He is an editor of the IEEE Transactions on Mobile Computing and IEEE Transactions on Wireless Communications, a guest editor of special issue on heterogeneous wireless networks in ACM/Kluwer Mobile Networking and Applications, and has served on the program committee of many conferences. He was a recipient of the NSF CAREER award in 2001. Thomas F. La Porta received his B.S.E.E. and M.S.E.E. degrees from The Cooper Union, New York, NY, and his Ph.D. degree in Electrical Engineering from Columbia University, New York, NY. He joined the Computer Science and Engineering Department at Penn State in 2002 as a Full Professor. He is the Director of the Networking and Security Research Center at Penn State. Prior to joining Penn State, Dr. La Porta was with Bell Laboratories since 1986. He was the Director of the Mobile Networking Research Department in Bell Laboratories, Lucent Technologies where he led various projects in wireless and mobile networking. He is a Bell Labs Fellow. Dr. La Porta was the founding Editor-in-Chief of the IEEE Transactions on Mobile Computing and served as Editor-in-Chief of IEEE Personal Communications Magazine. He is currently the Director of Magazines for the IEEE Communications Society and is a member of the Communications Society Board of Governors. He has published over 50 technical papers and holds 28 patents. His research interests include mobility management, signaling and control for wireless networks, mobile data systems, and protocol design.     

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.     

Approximating the Minimum Number of Maximum Power Users in Ad hoc Networks

Topology control is the problem of assigning transmission power values to the nodes of an ad hoc network so that the induced graph satisfies some specified property. The most fundamental such property is that the network/graph be connected. For connectivity, prior work on topology control gave a polynomial time algorithm for minimizing the maximum power assigned to any node (such that the induced graph is connected). In this paper we study the problem of minimizing the number of maximum power nodes. After establishing that this minimization problem is NP-complete, we focus on approximation algorithms for graphs with symmetric power thresholds. We first show that the problem is reducible in an approximation preserving manner to the problem of assigning power values so that the sum of the powers is minimized. Using known results for that problem, this provides a family of approximation algorithms for the problem of minimizing the number of maximum power nodes with approximation ratios of 5/3 + ε for every ε > 0. Unfortunately, these algorithms, based on solving large linear programming problems, are not practical. The main results of this paper are practical algorithms with approximation ratios of 7/4 and 5/3 (exactly). In addition, we present experimental results, both on randomly generated networks, and on two networks derived from proximity data associated with the TRANSIMS project of Los Alamos National Labs. Finally, based on the reduction to the problem of minimizing the total power, we describe some additional results for minimizing the number of maximum power users, both for graph properties other than connectivity and for graphs with asymmetric power thresholds. A preliminary version of this paper was presented at the ADHOC-NOW’04 conference in Vancouver, Canada, July 2004. Prepared through collaborative participation in the Communications and Networks Consortium sponsored by the U.S. Army Research Laboratory under the Collaborative Technology Alliance Program, Cooperative Agreement DAAD19-01-2-0011. The U.S. Government is authorized to reproduce and distribute reprints for Government purposes not withstanding any copyright notation thereon. Errol L. Lloyd is a Professor of Computer and Information Sciences at the University of Delaware. Previously he served as a faculty member at the University of Pittsburgh and as Program Director for Computer and Computation Theory at the National Science Foundation. From 1994 to 1999 he was Chair of the Department of Computer and Information Sciences at the University of Delaware. Concurrently, from 1997 to 1999 he was Interim Director of the University of Delaware Center for Applied Science and Engineering in Rehabilitation. Professor Lloyd received undergraduate degrees in both Computer Science and Mathematics from Penn State University, and a Ph.D. in Computer Science from the Massachusetts Institute of Technology. His research expertise is in the design and analysis of algorithms, with a particular concentration on approximation algorithms. In 1989 Professor Lloyd received an NSF Outstanding Performance Award, and in 1994 he received the University of Delaware Faculty Excellence in Teaching Award. Rui Liu received the B.S. degree in mathematics from Peking University, Beijing, China, in 1998, and the Ph.D. degree in Computer and Information Sciences from the University of Delaware in 2004. Since that time, he has been a Senior Associate Staff Scientist with Oracle|Retek. His research interests include design and analysis of algorithms for combinatorial optimization problems, and mobile computing. S.S. Ravi received his Ph.D. in Computer Science from the University of Pittsburgh in 1984. Since that time, he has been on the computer science faculty at the University at Albany – State University of New York, where he is currently a Professor. His areas of interest include design and analysis of algorithms, mobile computing, data mining and fault-tolerant computing.     

Scheduling Sleeping Nodes in High Density Cluster-based Sensor Networks

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

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.     

On Nash equilibria for multicast transmissions in ad-hoc wireless networks

We study a multicast game in ad-hoc wireless networks in which a source sends the same message or service to a set of receiving stations via multi-hop communications and the overall transmission cost is divided among the receivers according to given cost sharing methods. We assume that each receiver gets a certain utility from the transmission and enjoys a benefit equal to the difference between his utility and the shared cost he is asked to pay. Assuming a selfish and rational behavior, each user is willing to receive the transmission if and only if his shared cost does not exceed his utility. Moreover, given the strategies of the other users, he wants to select a strategy of minimum shared cost. A Nash equilibrium is a solution in which no user can increase his benefit by choosing to adopt a different strategy. We consider the following reasonable cost sharing methods: egalitarian, semi-egalitarian next-hop-proportional, path-proportional, egalitarian-path-proportional and Shapley value. We prove that, while the first five cost sharing methods in general do not admit a Nash equilibrium, the Shapley value yields games always converging to a Nash equilibrium. We then turn our attention to the special case in which the receivers’ set R is part of the input (that is only the stations belonging to R have a positive utility which is set equal to infinity) and show that in such a case also the egalitarian and the egalitarian-path-proportional methods yield convergent games. In such a framework, we show that the price of anarchy is unbounded for the game yielded by the egalitarian method and provide matching upper and lower bounds for the price of anarchy of the other two convergent games with respect to two different global cost functions, that is the overall cost of the power assignment, that coincides with the sum of all the shared costs, and the maximum shared cost paid by the receivers. Finally, in all cases we show that finding the best Nash equilibrium is computationally intractable, that is NP-hard. Vittorio Bilò received the degree in Computer Science and the Ph.D. degree in Computer Science at the University of L’Aquila in 2001 and 2005 respectively. He is currently an assistant professor at the Department of Mathematics “Ennio De Giorgi” of the University of Lecce. His research interests include algorithms and computational complexity, communication problems in interconnection networks and game theoretical issues in non-cooperative networks. Michele Flammini received the degree in Computer Science at the University of L’Aquila in 1990 and the Ph.D. degree in Computer Science at the University of Rome “La Sapienza” in 1995. He is full professor at the Computer Science Department of the University of L’Aquila since March 2005. His research interests include algorithms and computational complexity, game theory, communication problems in interconnection networks and routing. He has authored and co-authored more than 70 papers in his fields of interest published in the most reputed international conferences and journals. Giovanna Melideo received the Laurea degree in computer science in 1997 from the University of L’Aquila (Italy) and the Ph.D. degree in computer engineering in 2001 from the University of Rome “La Sapienza”. From November 1999 to February 2000 she was visitor at IRISA/INRIA, University of Rennes 1, Rennes (France) in the ADP group. She was research fellow from June to October 2001 at the University of L’Aquila, where she is currently an assistant professor in the Computer Science Department. Her research interests include algorithms and complexity, algorithmic game theory, wireless networks, models for information integration and cooperative information systems, certification and security in e-service, distributed protocols and dependability. She has been a member of the scientific and organizing committee of the IFIP international workshop on Certification and Security in E-Services (CSES 2002), Montreal, Canada. Luca Moscardelli received the degree in Computer Science at the University of L’Aquila in 2004. He is currently a Ph.D. student in Computer Science at the University of L’Aquila. His current research interests include optimization problems in social and communication networks, and the analysis of the interaction between selfish agents in non-cooperative networks.     

A Centralized MAC Protocol for QoS Support in UWB-Based Wireless Networks

In this paper we introduce a novel MAC protocol that provides Quality of Service (QoS) support for multimedia traffic in UWB-based wireless local area networks. The proposed protocol allocates transmission opportunities to QoS and best effort traffic using a set of scheduling and resource control algorithms. The algorithms account for the UWB characteristics such as the co-existence of multiple simultaneous transmissions as well as the possibility of dynamically assigning the nodes' transmission rate and power. The simulation results show that the proposed protocol can provide QoS support while optimizing resource utilization. Yuechun Chu received her B.Sc. degree in electrical engineering from Shanghai University, China, in 1996 and M.Sc. degree in electrical engineering from University of Science and Technology of China in 1999. She is currently pursuing the Ph.D. degree in the department of electrical and computer engineering at the University of Massachusetts Amherst. Her research interests include MAC protocol design for UWB-based networks, wireless multimedia applications, and architectures and protocols for wireless networks with QoS guarantees. Aura Ganz is currently an Associate Professor and Director of the Multimedia Networks Laboratory at the ECE Department, University of Massachusetts at Amherst. She has experience in topics related to multimedia wireless networks, optical networks and ubiquitous computing. The research results are validated by a combination of analytical, simulation and prototyping tools. She has published a book “Multimedia Wireless Networks: Technologies, Standards and QoS” (Prentice Hall) and authored over one hundred and fifty peer reviewed publications. Dr. Ganz received her BSc, MSc and Ph.D degrees in Computer Science from the Technion in Israel.     

Analysis of Energy Conservation in Sensor Networks

In this paper we use the Erlang theory to quantitatively analyse the trade offs between energy conservation and quality of service in an ad-hoc wireless sensor network. Nodes can be either sleeping, where no transmission or reception can occur, or awake where traffic is processed. Increasing the proportion of time spent in the sleeping state will decrease throughput and increase packet loss and delivery delay. However there is a complex relationship between sleeping time and energy consumption. Increasing the sleeping time does not always lead to an increase in the energy saved. We identify the energy consumption profile for various levels of sensor network activity and derive an optimum energy saving curve that provides a basis for the design of extended-life ad hoc wireless sensor networks. Qiang Gao is a research fellow in Electronic Engineering at Aston University. He received his B.S. in Theoretical Physics from Southwest Normal University in 1994, M.S. in Theoretical Physics from Lanzou University in 1997, and Ph.D. degree in Computer Engineering from Chinese Academy of Science in 2000. His research interests include ad hoc networks, multimedia networks, information security, CSCW. Keith Blow is a Professor in Engineering in the School of Engineering at Aston University. He worked for eighteen years in the research laboratories of BT studying optical solitons and the applications of nonlinearity to optical communications. In 1999 he moved to Aston University. In addition to his interests in optical communications he is also working on performance modelling and optimisation of ad-hoc sensor networks. David Holding is a Reader in Electronic Engineering in the School of Engineering at Aston University. He has expertise in the design of digital and programmable electronic systems, leads the digital electronics design programmes and is responsible for the associated laboratories and research facilities. Dr Holding has research interests in the design of sensor networks, distributed processing and control systems, concurrent real-time software and fault tolerant systems, and FPGA/SOC implementation. Ian Marshall is Professor of Distributed Systems in the Computing Lab at the University of Kent and a Visiting Professor in the Electrical Engineering Department at University College London. He is also Technical Director of the DTI funded Envisense research centre. Between 2001 and 2003 he was a Royal Society Industry Fellow at University College London where he led the initial research on self-organising sensor networks, using nature inspired decentralised control algorithms, now being further explored by the Envisense researchers, and the ubiquitous systems reasearch group at Kent. Previously he worked for BT in active networks & services, optical networks, broadband networks, network strategy, Internet and distributed systems. He is a chartered engineer, a member of council at the Institute of Physics and a fellow of the British Computer Society and of the Institute of Electrical Engineers. He serves on several institute committees, on EPSRC and European research panels, and on numerous programme committees.