Minimum energy transmission scheduling subject to deadline constraints

We consider the problem of transmission scheduling of data over a wireless fading channel with hard deadline constraints. Our system consists of N users, each with a fixed amount of data that must be served by a common deadline. Given that, for each user, the channel fade state determines the throughput per unit of energy expended, our objective is to minimize the overall expected energy consumption while satisfying the deadline constraint. We consider both a linear and a strictly convex rate-power curve and obtain optimal solutions, based on dynamic programming (DP), and tractable approximate heuristics in both cases. For the special non-fading channel case with convex rate-power curve, an optimal solution is obtained based on the Shortest Path formulation. In the case of a linear rate-power curve, our DP solution has a nice “threshold” form; while for the convex rate-power curve we are able to obtain a heuristic algorithm with comparable performance with that of the optimal scheduling scheme. Alessandro Tarello received his M.Sc. and Ph.D. degrees in Electrical and Communication Engineering from Politecnico di Torino, Torino, Italy, in 2002 and 2006 respectively. He currently holds a Postdoctoral position at Politecnico di Torino. He visited the Laboratory for Information and Decision Systems at MIT, Cambridge, MA, USA, in 2004 and 2005. During Summer 2005 he also visited the Jet Propulsion Laboratory, Pasadena, CA, USA. He received the best student paper award at the Third International Symposium on Modeling and Optimization in Mobile, Ad-Hoc and Wireless Networks (WiOPT’05). His research interests are in the fields of stochastic and fluid models for performance evaluation of packet networks and optimization techniques for wireless and ad-hoc networks. Jun Sun received his B.S. degree in Computer Engineering from University of Florida in 1997 and his M.S. in Electrical Engineering from Massachusetts Institute of Technology in 2002. He is currently a Ph.D. student in the Laboratory for Information and Decision Systems at MIT. His research interest is on communication networks with emphasis on satellite and wireless networks. Murtaza Zafer received his B.Tech degree in Electrical Engineering from the Indian Institute of Technology (IIT), Madras, India, in 2001 and his M.S. degree in Electrical Engineering and Computer Science from the Massachusetts Institute of Technology (MIT), MA, USA, in 2003. Currently, he is pursuing his doctoral studies at the Laboratory for Information and Decision Systems (LIDS) in the department of Electrical Engineering and Computer Science at MIT. He spent the summer of 2004 at the Mathematical Sciences Research center, Bell Laboratories and the summer of 2003 at Qualcomm, Inc. His research interests lie in queueing theory, information theory, control and optimization theory and its applications to wireless communication networks. He is the co-recipient of the best Student Paper award at WiOpt, 2005. He also received the Siemens (India) and Philips (India) award for academic excellence. Eytan Modiano received his B.S. degree in Electrical Engineering and Computer Science from the University of Connecticut at Storrs in 1986 and his M.S. and PhD degrees, both in Electrical Engineering, from the University of Maryland, College Park, MD, in 1989 and 1992 respectively. He was a Naval Research Laboratory Fellow between 1987 and 1992 and a National Research Council Post Doctoral Fellow during 1992–1993. Between 1993 and 1999 he was with MIT Lincoln Laboratory where he was the project leader for MIT Lincoln Laboratory’s Next Generation Internet (NGI) project. Since 1999 he has been on the faculty at MIT; where he is presently an Associate Professor. His research is on communication networks and protocols with emphasis on satellite, wireless, and optical networks. He is currently an Associate Editor for Communication Networks for IEEE Transactions on Information Theory and for The International Journal of Satellite Communications. He had served as a guest editor for IEEE JSAC special issue on WDM network architectures; the Computer Networks Journal special issue on Broadband Internet Access; the Journal of Communications and Networks special issue on Wireless Ad-Hoc Networks; and for IEEE Journal of Lightwave Technology special issue on Optical Networks. He is the Technical Program co-chair for Wiopt 2006, IEEE Infocom 2007, and ACM MobiHoc 2007.     

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

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

Finding Minimum Energy Disjoint Paths in Wireless Ad-Hoc Networks

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

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.     

On-demand diversity wireless relay networks

There has been much recent attention on using wireless relay networks to forward data from mobile nodes to a base station. This network architecture is motivated by performance improvements obtained by leveraging the highest quality links to a base station for data transfer. With the advent of agile radios it is possible to improve the performance of relay networks through intelligent frequency assignments. First, it is beneficial if the links of the relay network are orthogonal with respect to each other so that simultaneous transmission on all links is possible. Second, diversity can be added to hops in the relay network to reduce error rates. In this paper we present algorithms for forming such relay networks dynamically. The formation algorithms support intelligent frequency assignments and diversity setup. Our results show that algorithms that order the sequence in which nodes join a relay network carefully, achieve the highest amount of diversity and hence best performance. This research is supported in part by NSF grant CNS-0508114. JaeSheung Shin received the B.S. and M.S. degree in Computer Science and Engineering from DongGuk University, Korea, in 1991 and 1993, respectively. He is currently working toward the Ph.D. degree in Computer Science and Engineering at the Pennsylvania State University, University Park. He is a research assistant at the Networking and Security Research Center (NSRC). Prior to joining Pennsylvania State University, he was with Electronics and Telecommunications Research Institute (ETRI), Korea, since 1993. He worked on development of 2G and 3G wireless cellular core network elements. His research interests include mobility management and signaling for wireless cellular and routing and resource allocation for multi-radio multi-hop wireless cellular networks. Kyounghwan Lee received the B.S. degree in Electrical and Electronics Engineering from University of Seoul, Seoul, Korea, in 2000, and the M.S. degree in Information and Communication Engineering from Gwangju Institute of Science and Technology, Gwangju, Korea, in 2002. He is currently a Ph.D candidate at the Electrical Engineering department at the Pennsylvania State University and a research assistant at the Wireless Communications and Networking Laboratory (WCAN@PSU). His research interests include wireless communication theory and relay networks. E-mail: kxl251@psu.edu Aylin Yener received the B.S. degrees in Electrical and Electronics Engineering, and in Physics, from Bogazici University, Istanbul, Turkey, in 1991, and the M.S. and Ph.D. degrees in Electrical and Computer Engineering from Rutgers University, NJ, in 1994 and 2000, respectively. During her Ph.D. studies, she was with Wireless Information Network Laboratory (WINLAB) in the Department of Electrical and Computer Engineering at Rutgers University, NJ. Between fall 2000 and fall 2001, she was with the Electrical Engineering and Computer Science Department at Lehigh University, PA, where she was a P.C. Rossin assistant professor. Currently, she is with the Electrical Engineering department at the Pennsylvania State University, University Park, PA, as an assistant professor. Dr. Yener is a recipient of the NSF CAREER award in 2003. She is an associate editor of the IEEE Transactions on Wireless Communications. Dr. Yener’s research interests include performance enhancement of multiuser systems, wireless communication theory and wireless networking. 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 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. He is an IEEE Fellow and Bell Labs Fellow. Dr. La Porta was the founding Editor-in-Chief of the IEEE Transactions on Mobile Computing. He has published over 50 technical papers and holds 25 patents.     

On the Use of Multiple Hops in Next Generation Wireless Systems

Traditional cellular networks provide a centralized wireless networking paradigm within the wireless domain with the help of fixed infrastructure nodes such as Base Stations (BSs). On the other hand, Ad hoc wireless networks provide a fully distributed wireless networking scheme with no dependency on fixed infrastructure nodes. Recent studies show that the use of multihop wireless relaying in the presence of infrastructure based nodes improves system capacity of wireless networks. In this paper, we consider three recent wireless network architectures that combine the multihop relaying with infrastructure support – namely Integrated Cellular and Ad hoc Relaying (iCAR) system, Hybrid Wireless Network (HWN) architecture, and Multihop Cellular Networks (MCNs), for a detailed qualitative and quantitative performance evaluation. MCNs use multihop relaying by the Mobile Stations (MSs) controlled by the BS. iCAR uses fixed Ad hoc Relay Stations (ARSs) placed at the boundaries to relay excess traffic from a hot cell to cooler neighbor cells. HWN dynamically switches its mode of operation between a centralized Cellular mode and a distributed Ad hoc mode based on the throughput achieved. An interesting observation derived from these studies is that, none of these architectures is superior to the rest, rather each one performs better in certain conditions. MCN is found to be performing better than the other two architectures in terms of throughput, under normal traffic conditions. At very high node densities, the variable power control employed in HWN architecture is found to be having a superior impact on the throughput. The mobility of relay stations significantly influences the call dropping probability and control overhead of the system and hence at high mobility iCAR which uses fixed ARSs is found to be performing better. This work was supported by Infosys Technologies Ltd., Bangalore, India and the Department of Science and Technology, New Delhi, India. B. S. Manoj received his Ph.D degree in Computer Science and Engineering from the Indian Institute of Technology, Madras, India, in July 2004. He has worked as a Senior Engineer with Banyan Networks Pvt. Ltd., Chennai, India from 1998 to 2000 where his primary responsibility included design and development of protocols for real-time traffic support in data networks. He had been an Infosys doctoral student in the Department of Computer Science and Engineering at the Indian Institute of Technology-Madras, India. He is a recipient of the Indian Science Congress Association Young Scientist Award for the Year 2003. Since the beginning of 2005, he has been a post doctoral researcher in the Department of Electrical and Computer Engineering, University of California, San Diego. His current research interests include ad hoc wireless networks, next generation wireless architectures, and wireless sensor networks. K. Jayanth Kumar obtained his B.Tech degree in Computer Science and Engineering in 2002 from the Indian Institute of Technology, Madras, India. He is currently working towards the Ph.D degree in the department of Computer Science at the University of California, Berkeley. Christo Frank D obtained his B.Tech degree in Computer Science and Engineering in 2002 from the Indian Institute of Technology, Madras, India. He is currently working towards the Ph.D. degree in the department of Computer Science at the University of Illinois at Urbana-Champaign. His current research interests include wireless networks, distributed systems, and operating systems. C. Siva Ram Murthy received the B.Tech. degree in Electronics and Communications Engineering from Regional Engineering College (now National Institute of Technology), Warangal, India, in 1982, the M.Tech. degree in Computer Engineering from the Indian Institute of Technology (IIT), Kharagpur, India, in 1984, and the Ph.D. degree in Computer Science from the Indian Institute of Science, Bangalore, India, in 1988. He joined the Department of Computer Science and Engineering, IIT, Madras, as a Lecturer in September 1988, and became an Assistant Professor in August 1989 and an Associate Professor in May 1995. He has been a Professor with the same department since September 2000. He has held visiting positions at the German National Research Centre for Information Technology (GMD), Bonn, Germany, the University of Stuttgart, Germany, the University of Freiburg, Germany, the Swiss Federal Institute of Technology (EPFL), Switzerland, and the University of Washington, Seattle, USA. He has to his credit over 120 research papers in international journals and over 100 international conference publications. He is the co-author of the textbooks Parallel Computers: Architecture and Programming, (Prentice-Hall of India, New Delhi, India), New Parallel Algorithms for Direct Solution of Linear Equations, (John Wiley & Sons, Inc., New York, USA), Resource Management in Real-time Systems and Networks, (MIT Press, Cambridge, Massachusetts, USA), WDM Optical Networks: Concepts, Design, and Algorithms, (Prentice Hall, Upper Saddle River, New Jersey, USA), and Ad Hoc Wireless Networks: Architectures and Protocols, (Prentice Hall, Upper Saddle River, New Jersey, USA). His research interests include parallel and distributed computing, real-time systems, lightwave networks, and wireless networks. Dr.Murthy is a recipient of the Sheshgiri Kaikini Medal for the Best Ph.D. Thesis from the Indian Institute of Science, the Indian National Science Academy (INSA) Medal for Young Scientists, and Dr. Vikram Sarabhai Research Award for his scientific contributions and achievements in the fields of Electronics, Informatics, Telematics & Automation. He is a co-recipient of Best Paper Awards from the 1st Inter Research Institute Student Seminar (IRISS) in Computer Science, the 5th IEEE International Workshop on Parallel and Distributed Real-Time Systems (WPDRTS), and the 6th and 11th International Conference on High Performance Computing (HiPC). He is a Fellow of the Indian National Academy of Engineering.     

Smart-Aloha for Multi-Hop Wireless Networks

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

QoS-driven asynchronous uplink subchannel allocation algorithms for space-time OFDM-CDMA systems in wireless networks

In order to support the diverse Quality of Service (QoS) requirements for differentiated data applications in broadband wireless networks, advanced techniques such as space-time coding (STC) and orthogonal frequency division multiplexing (OFDM) are implemented at the physical layer. However, the employment of such techniques evidently affects the subchannel-allocation algorithms at the medium access control (MAC) layer. In this paper, we propose the QoS-driven cross-layer subchannel-allocation algorithms for data transmissions over asynchronous uplink space-time OFDM-CDMA wireless networks. We mainly focus on QoS requirements of maximizing the best-effort throughput and proportional bandwidth fairness, while minimizing the upper-bound of scheduling delay. Our extensive simulations show that the proposed infrastructure and algorithms can achieve high bandwidth fairness and system throughput while reducing scheduling delay over wireless networks. Xi Zhang (S’89-SM’98) received the B.S. and M.S. degrees from Xidian University, Xi’an, China, the M.S. degree from Lehigh University, Bethlehem, PA, all in electrical engineering and computer science, and the Ph.D. degree in electrical engineering and computer science (Electrical Engineering—Systems) from The University of Michigan, Ann Arbor, USA. He is currently an Assistant Professor and the Founding Director of the Networking and Information Systems Laboratory, Department of Electrical and Computer Engineering, Texas A&M University, College Station, Texas, USA. He was an Assistant Professor and the Founding Director of the Division of Computer Systems Engineering, Department of Electrical Engineering and Computer Science, Beijing Information Technology Engineering Institute, Beijing, China, from 1984 to 1989. He was a Research Fellow with the School of Electrical Engineering, University of Technology, Sydney, Australia, and the Department of Electrical and Computer Engineering, James Cook University, Queensland, Australia, under a Fellowship from the Chinese National Commission of Education. He worked as a Summer Intern with the Networks and Distributed Systems Research Department, Bell Laboratories, Murray Hills, NJ, and with AT&T Laboratories Research, Florham Park, NJ, in 1997. He has published more than 80 technical papers. His current research interests focus on the areas of wireless networks and communications, mobile computing, cross-layer designs and optimizations for QoS guarantees over mobile wireless networks, wireless sensor and Ad Hoc networks, wireless and wireline network security, network protocols design and modeling for QoS guarantees over multicast (and unicast) wireless (and wireline) networks, statistical communications theory, random signal processing, and distributed computer-control systems. Dr. Zhang received the U.S. National Science Foundation CAREER Award in 2004 for his research in the areas of mobile wireless and multicast networking and systems. He is currently serving as an Editor for the IEEE Transactions on Wireless Communications, an Associated Editor for the IEEE Transactions on Vehicular Technology, and and Associated Editor for the IEEE Communications Letters, and is also currently serving as a Guest Editor for the IEEE Wireless Communications Magazine for the Special Issues of “Next Generation of CDMA vs. OFDMA for 4G Wireless Applications”. He has served or is serving as the Panelist on the U.S. National Science Foundation Research-Proposal Review Panel in 2004, the WiFi-Hotspots/WLAN and QoS Panelist at the IEEE QShine 2004, as the Symposium Chair for the IEEE International Cross-Layer Designs and Protocols Symposium within the IEEE International Wireless Communications and Mobile Computing Conference (IWCMC) 2006, the Technical Program Committee Co-Chair for the IEEE IWCMC 2006, the Poster Chair for the IEEE QShine 2006, the Publicity Co-Chair for the IEEE WirelessCom 2005, and as the Technical Program Committee members for IEEE GLOBECOM, IEEE ICC, IEEE WCNC, IEEE VTC, IEEE QShine, IEEE WoWMoM, IEEE WirelessCom, and IEEE EIT. He is a Senior Member of the IEEE and a member of the Association for Computing Machinery (ACM). Jia Tang (S’03) received the B.S. degree in electrical engineering from Xi’an Jiaotong University, Xi’an, China, in 2001. He is currently a Research Assistant working towards the Ph.D. degree in the Networking and Information Systems Laboratory, Department of Electrical and Computer Engineering, Texas A&M University, College Station, Texas, USA. His research interests include mobile wireless communications and networks, with emphasis on cross-layer design and optimizations, wireless quality-of-service (QoS) provisioning for mobile multimedia networks, wireless diversity techniques, and wireless resource allocation. Mr. Tang received the Fouraker Graduate Research Fellowship Award from the Department of Electrical and Computer Engineering, Texas A&M University in 2005.     

Dynamically anchored conferencing handoff for dual-mode cellular/WLAN handsets

In this paper we consider vertical handoff for enterprise-based dual-mode (DM) cellular/WLAN handsets. When the handset roams out of WLAN coverage, the DM's cellular interface is used to maintain the call by anchoring it through an enterprise PSTN gateway/PBX. Soft handoff can be achieved in this case if the gateway supports basic conference bridging, since a new leg of the call can be established to the conference bridge while the existing media stream path is active. Unfortunately this requires that all intra-enterprise calls be routed through the gateway when the call is established. In this paper we consider a SIP based architecture to perform conferenced dual-mode handoff and propose a much more scalable mechanism for short-delay environments, whereby active calls are handed off into the conference bridge prior to the initiation of the vertical handoff. Results are presented which are taken from a dual-mode handset testbed, from analytic models, and from simulations which characterize the scalability of the proposed mechanism. Mohammed Smadi received the B.Eng and Mgmt and M.A.Sc degrees in Computer Engineering from McMaster University in Hamilton, Ontario, Canada. Mohammed received an NSERC doctoral award in 2005 and is currently a Ph.D. student at the Wireless Networking Group at McMaster University. Terence D. Todd received the B.A.Sc, M.A.Sc and Ph.D. degrees in Electrical Engineering from the University of Waterloo, Waterloo, Ontario, Canada. While at Waterloo he spent 3 years as a Research Associate with the Computer Communications Networks Group (CCNG). He is currently a Professor of Electrical and Computer Engineering at McMaster University in Hamilton, Ontario, Canada. Professor Todd spent 1991 on research leave in the Distributed Systems Research Department at AT&T Bell Laboratories in Murray Hill, NJ. He also spent 1998 on research leave at The Olivetti and Oracle Research Laboratory in Cambridge, England. While at ORL he worked on the piconet project which was an early embedded wireless network testbed. Dr. Todd’s research interests include metropolitan/local area networks, wireless communications and the performance analysis of computer communication networks and systems. He is a past Editor of the IEEE/ACM Transactions on Networking and currently holds the NSERC/RIM/CITO Chair on Pico-Cellular Wireless Internet Access Networks. Dr. Todd is a Professional Engineer in the province of Ontario and a member of the IEEE. Vytas Kezys was born in Hamilton, Canada in 1957. He received the B.Eng. degree in Electrical Engineering from McMaster University, Canada, in 1979. From 1979 to 1998, Mr. Kezys was involved in radar and communications research as Principal Research Engineer at the Communications Research Laboratory, McMaster University. While at McMaster, his research activities included array signal processing for low-angle tracking radar, radar signal processing, and smart antennas for wireless communications. Mr. Kezys was founder and President of TalariCom Inc., a start-up company that developed cost effective smart antenna technologies for broadband wireless access applications. Currently, Mr. Kezys is Director of Advanced Products at Research in Motion in Waterloo, Canada. Vahid S. Azhari received his B.S. and M.S. from the Department of Electrical and Computer Engineering, IUST and University of Tehran, Iran, in 2000 and 2003 respectively. His M.S. research focused on designing scheduling algorithms for switch fabrics. He also worked for two years for the Iranian Telecommunication Research Centre on developing software for SDH switches. He is currently pursuing his Ph.D. degree at the Wireless Networking Laboratory, McMaster University, Canada. His main area of research includes handoff management in integrated wireless networks, WLAN deployment techniques, and wireless mesh networks. Dongmei Zhao received the Ph.D. degree in Electrical and Computer Engineering from the University of Waterloo, Waterloo, Ontario, Canada in June 2002. Since July 2002 she has been with the Department of Electrical and Computer Engineering, McMaster University, Hamilton, Ontario, Canada where she is an assistant professor. Dr. Zhao’s research interests include modeling and performance analysis, quality-of-service provisioning, access control and admission control in wireless cellular networks and integrated cellular and ad hoc networks. Dr. Zhao is a member of the IEEE.     

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.     

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

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

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.     

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.     

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 .     

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.     

Proportional Service Differentiation in Wireless LANs Using Spacing-based Channel Occupancy Regulation

In this paper, we propose Spacing-based Channel Occupancy Regulation (SCORE) MAC protocol for wireless LANs that provides proportional service differentiation in terms of normalized throughput. As shown by our system model and simulation study, SCORE provides consistent, scalable and adjustable proportional differentiation for any network size, any service class distribution, any node data rate and any packet size. Compared to state-of-the-art prioritized service differentiation schemes like Enhanced Distributed Coordination Function (EDCF), SCORE can quantitatively control the channel sharing between different service classes. Moreover, SCORE obtains significant performance improvements in terms of higher network throughput, higher transmission efficiency, lower medium access delay and lower delay jitter. Dr. Qi Xue is now a senior systems engineer with Qualcomm Inc. since Feb. 2005. Qi Xue is currently a Ph.D. candidate in the department of Electrical and Computer Engineering, University of Massachusetts at Amherst. He received his M.S. degree in Electrical and Information Engineering from Huazhong University of Science and Technology, China, in 2000. His research interests include protocol design and performance analysis in wireless networks. Weibo Gong received his Ph.D degree from Harvard University in 1987, and have been with the Dept. of Electrical and Computer Engineering, University of Massachusetts, Amherst since then. He is also an adjunct professor in the Dept. of Computer Science at the same campus. His major research interests include control and systems methods in communication networks, network security, and network modeling and analysis. He is a receipient of the IEEE Transactions on Automatic Control’s George Axelby Outstanding paper award, an IEEE Fellow, and the Program Committee Chair for the 43rd IEEE Conference on Decision and Control. Aura Ganz received her B.Sc, M.Sc and Ph.D degrees in Computer Science from the Technion in Israel. She 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 all strata of networking technology, from work related to topics in the network infrastructure development to advanced user-space application development for mobile clients. 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 is a senior member of IEEE     

Vehicle Velocity Estimation Based on RSS Measurements

This paper presents a technique which is based on pattern recognition techniques, in order to estimate Mobile Terminal (MT) velocity. The proposed technique applies on received signal strength (RSS) measurements and more precisely on information extracted from Iub air interface, in wIDeband code-division multiple access (WCDMA) systems for transmission control purposes. Pattern recognition is performed by HIDden Markov Model (HMM), which is trained with downlink signal strength measurements for specific areas, employing Clustering LARge Applications (CLARA) like a clustering method. Accurate results from a single probe vehicle show the potential of the method, when applied to large scale of MTs. Theodore S. Stamoulakatos is a Senior Research Associate with the Department of Electrical and Computer Engineering at National Technical University of Athens (NTUA). He received his B.Sc. in Mathematics from University of the Aegean, Greece, in 1997, and the M.Sc. in Computer Applications from Dublin City University, Ireland, in 1999 with scholarship from the Irish Ministry of Education. On April ’05 he received his Ph.D. degree from the Department of Electrical Engineering and Computer Science of the National Technical University of Athens. He has been lecturing in DCU various courses including Algorithms & Data Structures, Computer Systems, and Advanced Network Management to both undergraduate and postgraduate students. During his research in NTUA, he has been actively involved in many European and National projects that match his research interests. Both his academic as well as his industrial experience (four years in OTEnet S.A.) allow him to publish several papers in journals and international conferences, which are in the fields of Mobile and Personal Communication Networks, Active Networks, Location Based Services as well as Network and Service Management. Dr. Stamoulakatos is a member of the IEEE. Antonis E. Markopoulos obtained his degree in Informatics and Telecommunications Engineering from University of Athens, Greece in 2000. During his studies he participated in various research projects dealing with the management of fixed and wireless networks. He has also industrial experience for 2 years in INTRASOFT International S.A participating in several projects, national and European. He received his PhD in the field of Cellular and Wireless Communication from the National Technical University of Athens in 2005, where he is working as a Senior Research Engineer in the Telecommunication Laboratory. He has published several papers in journals, international conferences and book chapters. His research interests are in the fields of cellular and wireless networks of present and future generation (4G, WLAN/WPAN, WiMAX) and more specific in the areas of radio resource management and security. He has been mainly involved in many European (IST-CELLO, IST-PACWOMAN, IST-MAGNET, a.o) and National (Greek IST, GGRT) projects. Dr Markopoulos is a member of the IEEE and of the Greek Association of Mechanical and Electrical Engineers. Miltiades E. Anagnostou was born in Athens, Greece, in 1958. He received the Electrical Engineer’s Diploma from the National Technical University of Athens (NTUA) in 1981. In 1987 he received his PhD in the area of computer networks. Since 1989 he has been teaching at the Electrical and Computer Engineering School of NTUA, where he is currently a Full Professor. He teaches courses on modern telecommunications, computer networks, formal specification, stochastic processes, and network algorithms. His research spans several fields, including broadband networks, mobile and personal communications, service engineering, mobile agents, pervasive computing, network algorithms and queuing systems. He is a member of the IEEE and the ACM. Michael E. Theologou received the degree in Electrical Engineering from Patras University and his Ph.D. degree from the Department of Electrical Engineering and Computer Science of the National Technical University of Athens. Currently he is a Professor at National Technical University of Athens, Department of Electrical and Computer Engineering conducting teaching and research in the wider area of Telecommunication Networks and Systems. His research interests are in the fields of Mobile and Personal Communication Networks, Computer Networks, Quality of Service. He has many publications in the above areas.     

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.     

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.