A game-theoretic look at simple relay channel

In this paper, we address the crosslayer problem of joint medium access control (MAC) and routing in ad hoc wireless networks from the novel perspective of stochastic dynamic games. As a starting point to understand the efficient modes of wireless network operation, we look at the basic problem of multi-hop communication over the simple topology of a single relay channel. A stochastic game is formulated for transmitter and relay nodes competing over collision channels to deliver packets to a common destination node using alternative paths. We rely on a reward mechanism to stimulate cooperation for packet forwarding and evaluate the conflicting multiple access and routing strategies of direct communication and relaying through a detailed foray into the questions of cooperation incentives, throughput, delay and energy-efficiency. Under the separate models of selfish and cooperative network operation, we study the interactions among the equilibrium strategies and present a detailed performance analysis based on multiple system parameters that involve the packet arrival rates, throughput rewards, delay and energy costs. The material in this paper was partially presented at WIOPT’04: Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks, Cambridge, UK, March 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 notwithstanding any copyright notation thereon. Anthony Ephremides received his B.S. degree from the National Technical University of Athens (1967), and M.S. (1969) and Ph.D. (1971) degrees from Princeton University, all in electrical engineering. He has been at the University of Maryland since 1971, and currently holds a joint appointment as professor in the Electrical Engineering Department and the Institute of Systems Research (ISR). He is co-founder of the NASA Center for Commercial Development of Space on Hybrid and Satellite Communications Networks established in 1991 at Maryland as an offshoot of the ISR. He was a visiting professor in 1978 at the National Technical University of Athens, Greece, and in 1979 at the Electrical Engineering and Computer Science Department of the University of California at Berkeley and INRIA, France. During 1985–1986 he was on leave at Massachusetts Institute of Technology and the Swiss Federal Institute of Technology, Zurich. He has also been director of the Fairchild Scholars and Doctoral Fellows Program, an academic and research partnership program in satellite communications between Fairchild Industries and the University of Maryland. He has been President of the Information Theory Society of the IEEE (1987), and served on the Board of the IEEE (1989 and 1990). His interests are in the areas of communication theory, communication systems and networks, queuing systems, signal processing, and satellite communications. Yalin Evren Sagduyu received his B.S. degree from Bogazici University, Turkey, and M.S. degree from the University of Maryland at College Park in 2000 and 2002, respectively, all in electrical engineering. He is currently working toward his Ph.D. degree at the University of Maryland, where he has been a graduate research assistant with ISR since 2000. His research interests include wireless communication, ad hoc and sensor network design and optimization, stochastic game theory and network coding.     

A game-theoretic analysis of denial of service attacks in wireless random access

In wireless access, transmitter nodes need to make individual decisions for distributed operation and do not necessarily cooperate with each other. We consider a single-receiver random access system of non-cooperative transmitters with the individual objectives of optimizing their throughput rewards, transmission energy costs and delay costs. The non-cooperative transmitter behavior may be purely selfish or may also reflect malicious objectives of generating interference to prevent the successful transmissions of the other nodes as a form of denial of service attack. Our goal is to evaluate the interactions between selfish and malicious nodes that have the dual objectives of optimizing their individual performance measures and blocking the packet transmissions of the other selfish nodes. We assume saturated packet queues of infinite buffer capacities and consider a general multi-packet reception channel that allows packet captures in the presence of simultaneous transmissions. In this context, we formulate a non-cooperative random access game of selecting the individual probabilities of transmitting packets to a common receiver. We derive the non-cooperative transmission strategies in Nash equilibrium. The analysis provides insights for the optimal strategies to block random access of selfish nodes as well as the optimal defense mechanisms against the possible denial of service attacks of malicious nodes in wireless networks. The results are also compared with the cooperative equilibrium strategies that optimize the total system utility (separately under random access and scheduled access). A pricing scheme is presented to improve the non-cooperative operation. For distributed implementation, we formulate a repeated game of the best-response strategy updates and introduce adaptive heuristics (based on the channel feedback only) provided that the system parameters are not explicitly known at the individual transmitters.

Energy Efficient Broadcast in Wireless Ad hoc Networks with Hitch-hiking

In this paper, we propose a novel concept called Hitch-hiking in order to reduce the energy consumption of broadcast application for wireless networks. Hitch-hiking takes advantage of the physical layer design that facilitates the combining of partial signals to obtain the complete information. The concept of combining partial signals using maximal ratio combiner [15] has been used to improve the reliability of the communication link but has never been exploited to reduce energy consumption in broadcasting over wireless ad hoc networks. We study the advantage of Hitch-hiking for the scenario when the transmission power level of nodes is fixed as well as the scenario when the nodes can adjust their power level. For both scenarios, we show that Hitch-hiking is advantageous and have proposed algorithms to construct broadcast tree with Hitch-hiking taken into consideration. For fixed transmission power case, we propose and analyze a centralized heuristic algorithm called SPWMH (Single Power Wireless Multicast with Hitch-hiking) to construct a broadcast tree with minimum forwarding nodes. For the latter case, we propose a centralized heuristic algorithm called Wireless Multicast with Hitch-hiking (WMH) to construct an energy efficient tree using Hitch-hiking and also present a distributed version of the heuristic. We also evaluate the proposed heuristics through simulation. Simulation results show that Hitch-hiking can reduce the transmission cost of broadcast by as much as 50%. Further, we propose and evaluate a protocol called Power Saving with Broadcast Tree (PSBT) that reduces energy consumption of broadcast by eliminating redundancy in receive operation. Finally, we propose an algorithm that takes advantage of both Hitch-hiking and PSBT in conserving energy. Manish Agarwal is an engineer at Microsoft, Redmond. He received his Masters degree in Electrical and Computer Engineering from University of Massachusetts, Amherst in 2004. He received his undergraduate degree from Indian Institute of Technology, Guwahati. His research interest lies in the field of mobile ad hoc networks. Lixin Gao is an associate professor of Electrical and Computer Engineering at the University of Masschusetts, Amherst. She received her Ph.D. degree in computer science from the University of Massachusettes at Amherst in 1996. Her research interests include multimedia networking and Internet routing. Between May 1999 and January 2000, she was a visiting researcher at AT&T Research Labs and DIMACS. She is an Alfred P. Sloan Fellow and received an NSF CAREER Award in 1999. She is a member of IEEE, ACM, and Sigma Xi. Joon Ho Cho received the B.S. degree (summa cum laude) in electrical engineering from Seoul National University, Seoul, Korea, in 1995 and the M.S.E.E. and Ph.D. degrees in electrical and computer engineering from Purdue University, West Lafayette, IN, in 1997 and 2001, respectively. From 2001 to 2004, he was with the University of Massachusetts at Amherst as an Assistant Professor. Since July 2004, he has been with Pohang University of Science and Technology (POSTECH), Pohang, Korea, where he is presently an Assistant Professor in the Department of Electronic and Electrical Engineering. His research interests include wideband systems, multiuser communications, adaptive signal processing, packet radio networks, and information theory. Dr. Cho is currently an Associate Editor for the IEEE Transactions on Vehicular Technology. Jie Wu is a Professor at Department of Computer Science and Engineering, Florida Atlantic University. He has published over 300 papers in various journal and conference proceedings. His research interests are in the area of mobile computing, routing protocols, fault-tolerant computing, and interconnection networks. Dr. Wu served as a program vice chair for 2000 International Conference on Parallel Processing (ICPP) and a program vice chair for 2001 IEEE International Conference on Distributed Computing Systems (ICDCS). He is a program co-chair for the IEEE 1st International Conference on Mobile Ad-hoc and Sensor Systems (MASS'04). He was a co-guest-editor of a special issue in IEEE Computer on “Ad Hoc Networks”. He also editored several special issues in Journal of Parallel and Distributing Computing (JPDC) and IEEE Transactions on Parallel and Distributed Systems (TPDS). He is the author of the text “Distributed System Design” published by the CRC press. Currently, Dr. Wu serves as an Associate Editor in IEEE Transactions on Parallel and Distributed Systems and three other international journals. Dr. Wu is a recipient of the 1996–97 and 2001–2002 Researcher of the Year Award at Florida Atlantic University. He served as an IEEE Computer Society Distinguished Visitor. Dr. Wu is a Member of ACM and a Senior Member of IEEE.     

Cooperative-diversity slotted ALOHA

We propose a cooperative-diversity technique for ad hoc networks based on the decode-and-forward relaying strategy. We develop a MAC protocol based on slotted ALOHA that allows neighbors of a transmitter to act as relays and forward a packet toward its final destination when the transmission to the intended recipient fails. The proposed technique provides additional robustness against fading, packet collisions and radio mobility. Network simulations confirm that under heavy traffic conditions, in which every radio always has packets to send, the proposed cooperative-diversity slotted-ALOHA protocol can provide a higher one-hop and end-to-end throughput than the standard slotted-ALOHA protocol can. A similar advantage in end-to-end delay can be obtained when the traffic is light. As a result, the proposed cooperative-diversity ALOHA protocol can be used to improve these measures of Quality of Service (QoS) in ad hoc wireless networks. John M. Shea (S’92–M’99) received the B.S. (with highest honors) in Computer Engineering from Clemson University in 1993 and the M.S. and Ph.D. degrees in electrical engineering from Clemson University in 1995 and 1998, respectively. Dr. Shea is currently an Associate Professor of electrical and computer engineering at the University of Florida. Prior to that, he was an Assistant Professor at the University of Florida from July 1999 to August 2005 and a post-doctoral research fellow at Clemson University from January 1999 to August 1999. He was a research assistant in the Wireless Communications Program at Clemson University from 1993 to 1998. He is currently engaged in research on wireless communications with emphasis on error-control coding, cross-layer protocol design, cooperative diversity techniques, and hybrid ARQ. Dr. Shea was selected as a Finalist for the 2004 Eta Kappa Nu Outstanding Young Electrical Engineer Award. He received the Ellersick Award from the IEEE Communications Society in 1996. Dr. Shea was a National Science Foundation Fellow from 1994 to 1998. He is an Associate Editor for the IEEE Transactions on Vehicular Technology. Tan F. Wong received the B.Sc. degree (1st class honors) in electronic engineering from the Chinese University of Hong Kong in 1991, and the M.S.E.E. and Ph.D. degrees in electrical engineering from Purdue University in 1992 and 1997, respectively. He was a research engineer working on the high speed wireless networks project in the Department of Electronics at Macquarie University, Sydney, Australia. He also served as a post-doctoral research associate in the School of Electrical and Computer Engineering at Purdue University. Since August 1998 he has been with the University of Florida, where he is currently an associate professor of electrical and computer engineering. He serves as Editor for Wideband and Multiple Access Wireless Systems for the IEEE Transactions on Communications and as the Editor for the IEEE Transactions on Vehicular Technology.     

Multiconstrained QoS multipath routing in wireless sensor networks

Sensor nodes are densely deployed to accomplish various applications because of the inexpensive cost and small size. Depending on different applications, the traffic in the wireless sensor networks may be mixed with time-sensitive packets and reliability-demanding packets. Therefore, QoS routing is an important issue in wireless sensor networks. Our goal is to provide soft-QoS to different packets as path information is not readily available in wireless networks. In this paper, we utilize the multiple paths between the source and sink pairs for QoS provisioning. Unlike E2E QoS schemes, soft-QoS mapped into links on a path is provided based on local link state information. By the estimation and approximation of path quality, traditional NP-complete QoS problem can be transformed to a modest problem. The idea is to formulate the optimization problem as a probabilistic programming, then based on some approximation technique, we convert it into a deterministic linear programming, which is much easier and convenient to solve. More importantly, the resulting solution is also one to the original probabilistic programming. Simulation results demonstrate the effectiveness of our approach. This work was supported in part by the U.S. National Science Foundation under grant DBI-0529012, the National Science Foundation Faculty Early Career Development Award under grant ANI-0093241 and the Office of Naval Research under Young Investigator Award N000140210464. Xiaoxia Huang received her BS and MS in the Electrical Engineering from Huazhong University of Science and Technology in 2000 and 2002, respectively. She is completing her Ph.D. degree in the Department of Electrical and Computer Engineering at the University of Florida. Her research interests include mobile computing, QoS and routing in wireless ad hoc networks and wireless sensor networks. Yuguang Fang received a Ph.D. degree in Systems Engineering from Case Western Reserve University in January 1994 and a Ph.D degree in Electrical Engineering from Boston University in May 1997. He was an assistant professor in the Department of Electrical and Computer Engineering at New Jersey Institute of Technology from July 1998 to May 2000. He then joined the Department of Electrical and Computer Engineering at University of Florida in May 2000 as an assistant professor, got an early promotion to an associate professor with tenure in August 2003 and to a full professor in August 2005. He holds a University of Florida Research Foundation (UFRF) Professorship from 2006 to 2009. He has published over 200 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 has served on several editorial boards of technical journals including IEEE Transactions on Communications, IEEE Transactions on Wireless Communications, IEEE Transactions on Mobile Computing and ACM Wireless Networks. He have also been activitely participating in professional conference organizations such as serving as The Steering Committee Co-Chair for QShine, the Technical Program Vice-Chair for IEEE INFOCOM’2005, Technical Program Symposium Co-Chair for IEEE Globecom’2004, and a member of Technical Program Committee for IEEE INFOCOM (1998, 2000, 2003–2007).     

Design and Analysis of Optimal Multi-Level Hierarchical Mobile IPv6 Networks

Hierarchical Mobile IPv6 (HMIPv6) is an enhanced version of Mobile IPv6 designed to reduce signaling overhead and to support seamless handoff in IP-based wireless/mobile networks. To support more scalable services, HMIPv6 networks can be organized as the form of a multi-level hierarchy architecture (i.e., tree structure). However, since multi-level HMIPv6 networks incur additional packet processing overhead at multiple mobility agents, it is important to find the optimal hierarchy level to minimize the total cost, which consists of the location update cost and the packet delivery cost. In this paper, we investigate this problem, namely the design of an optimal multi-level HMIPv6 (OM-HMIPv6) network. To accomplish this, we design a function to represent the location update cost and the packet delivery cost in multi-level HMIPv6 networks. Based on these formulated cost functions, we calculate the optimal hierarchy level in multi-level HMIPv6 networks, in order to minimize the total cost. In addition, we investigate the effects of the session-to-mobility ratio (SMR) on the total cost and the optimal hierarchy. The numerical results, which show various relationships among the network size, optimal hierarchy, and SMR, can be utilized to design an optimal HMIPv6 network. In addition, the analytical results are validated by comprehensive simulations. Sangheon Pack received his B.S. (2000, magna cum laude) and Ph.D. (2005) degrees from Seoul National University, both in computer engineering. He is a post doctor fellow in the School of Computer Science and Engineering at the Seoul National University, Korea. He is a member of the IEEE and ACM. During 2002–2005, he was a recipient of the Korea Foundation for Advanced Studies (KFAS) Computer Science and Information Technology Scholarship. He has been also a member of Samsung Frontier Membership (SFM) from 1999. He received a student travel grant award for the IFIP Personal Wireless Conference (PWC) 2003. He was a visiting researcher to Fraunhofer FOKUS, German in 2003. His research interests include mobility management, wireless multimedia transmission, and QoS provision issues in the next-generation wireless/mobile networks. Yanghee Choi received B.S. in electronics engineering from Seoul National University, M.S. in electrical engineering from Korea advanced Institute of Science, and Doctor of Engineering in Computer Science from Ecole Nationale Superieure des Telecommunications (ENST) in Paris, in 1975, 1977 and 1984 respectively. Before joining the School of Computer Engineering, Seoul National University in 1991, he has been with Electronics and Telecommunications Research Institute (ETRI) during 1977–1991, where he served as director of Data Communication Section, and Protocol Engineering Center. He was research student at Centre National d'Etude des Telecommunications (CNET), Issy-les-Moulineaux, during 1981–1984. He was also Visiting Scientist to IBM T.J. Watson Research Center for the year 1988–1989. He is now leading the Multimedia Communications Laboratory in Seoul National University. He is also director of Computer Network Research Center in Institute of Computer Technology (ICT). He was editor-in-chief of Korea Information Science Society journals. He was chairman of the Special Interest Group on Information Networking. He has been associate dean of research affairs at Seoul National University. He was president of Open Systems and Internet Association of Korea. His research interest lies in the field of multimedia systems and high-speed networking. Minji Nam received her B.S. and M.S degrees in Computer Science and Engineering from Seoul National University in 2003 and 2005, respectively. From 2005, she has worked on Portable Internet Development Team for Korea Telecom. Her research interests are mobile networks, portable internet technology (IEEE 802.16) and Mobile IPv6.     

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     

A secure incentive protocol for mobile ad hoc networks

The proper functioning of mobile ad hoc networks depends on the hypothesis that each individual node is ready to forward packets for others. This common assumption, however, might be undermined by the existence of selfish users who are reluctant to act as packet relays in order to save their own resources. Such non-cooperative behavior would cause the sharp degradation of network throughput. To address this problem, we propose a credit-based Secure Incentive Protocol (SIP) to stimulate cooperation among mobile nodes with individual interests. SIP can be implemented in a fully distributed way and does not require any pre-deployed infrastructure. In addition, SIP is immune to a wide range of attacks and is of low communication overhead by using a Bloom filter. Detailed simulation studies have confirmed the efficacy and efficiency of SIP. This work was supported in part by the U.S. Office of Naval Research under Young Investigator Award N000140210464 and under grant N000140210554. Yanchao Zhang received the B.E. degree in Computer Communications from Nanjing University of Posts and Telecommunications, Nanjing, China, in July 1999, and the M.E. degree in Computer Applications from Beijing University of Posts and Telecommunications, Beijing, China, in April 2002. Since September 2002, 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. 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 Dec 1997 to Jul 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 security and routing issues. Wei Liu received his B.E. and M.E. in Electrical and Information Engineering from Huazhong University of Science and Technology, Wuhan, China, in 1998 and 2001. In August 2005, he received his PhD in Electrical and Computer Engineering from University of Florida. Currently, he is a senior technical member with Scalable Network Technologies. His research interest includes cross-layer design, and communication protocols for mobile ad hoc networks, wireless sensor networks and cellular networks. Yuguang Fang received a Ph.D. degree in Systems Engineering from Case Western Reserve University in January 1994 and a Ph.D degree in Electrical Engineering from Boston University in May 1997. He was an assistant professor in the Department of Electrical and Computer Engineering at New Jersey Institute of Technology from July 1998 to May 2000. He then joined the Department of Electrical and Computer Engineering at University of Florida in May 2000 as an assistant professor, got an early promotion to an associate professor with tenure in August 2003 and a professor in August 2005. He has published over 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 has served on many editorial boards of technical journals including IEEE Transactions on Communications, IEEE Transactions on Wireless Communications, IEEE Transactions on Mobile Computing and ACM Wireless Networks. He is a senior member of the IEEE.     

An unequal cluster-based routing protocol in wireless sensor networks

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

UbiqMuseum: A Bluetooth and Java Based Context-Aware System for Ubiquitous Computing

This paper evaluates the use of Bluetooth and Java based technologies in ubiquitous computing environments. Ubiquitous computing strongly depends on leveraging appropriate contextual information to users, according to their preferences and the environment in which they reside. We present UbiqMuseum – an experimental context-aware application that provides context-aware information to museum visitors. UbiqMuseum combines the productivity of Java with the universal connectivity provided by Bluetooth wireless technology. We describe the overall architecture and discuss the implementation steps taken to create our Bluetooth and Java based context-aware application. We demonstrate practicality of building a context-aware system by using UbiqMuseum as a proof of concept that integrates a combination of Bluetooth, WLAN and Ethernet LAN technologies. Finally we run some experiments in a small testbed to evaluate the performance and system behaviour. We evaluate the impact on throughput with varying packet size, coding types and device separation distance sending both images and text. We also present our findings in term of inquiry delay with respect to distance. Numerical results show that Bluetooth offers a relatively steady throughput up to 10 m while the inquiry delay does not increase significantly with distance. Juan-Carlos Cano is an assistant professor in the Department of Computer Engineering at the Polytechnic University of Valencia (UPV) in Spain. He earned an M.Sc. and a Ph.D. in computer science from the UPV in 1994 and 2002 respectively. Between 1995–1997 he worked as a programming analyst at IBM's manufacturing division in Valencia. His current research interests include power aware routing protocols for mobile ad hoc networks and pervasive computing. You can contact him at jucano@disca.upv.es. Pietro Manzoni received the MS degree in computer science from the “Universitá degli Studi" of Milan, Italy, in 1989, and the Ph.D. degree in computer science from the Polytechnic University of Milan, Italy, in 1995. He is an associate professor of computer science at the Polytechnic University of Valencia, Spain. His research activity is related to wireless networks protocol design, modeling, and implementation. He is member of the IEEE. C.-K. Toh is currently a Professor and Chair in Communication Networks at Queen Mary University of London, UK. He is also the Director of the UK Ad Hoc Wireless Consortium and Director of the Queen Mary/Fudan Joint Research Lab in Mobile Networking and Ubiquitous Computing. Concurrently, he is also an Honorary Professor with the University of Hong Kong and an Adjunct Professor at Fudan University, Shanghai. Previously, he was the Director of Research with TRW Tactical Systems in California, USA (now Northrop Grumman Corporation) and was responsible for DARPA and Army programs in communications and networking. He had also worked for Hughes Research, ALR, HP, and was a professor at GeorgiaTech and University of California, Irvine. CK is the recipient of the 2005 IEEE Kiyo Tomiyasu Technical Medal Award, for “pioneering contributions to communication protocols in ad hoc mobile wireless networks." He is the author of “Wireless ATM & Ad Hoc Networks" (Kluwer Press, 1996) and “Ad Hoc Mobile Wireless Networks" (Prentice Hall Engineering Title Best Seller, 2001–2003). He is a recipient of the ACM Recognition of Service Award, for co-founding ACM MobiHoc Conference. He is a co-recipient of the Korean Science & Engineering Foundation Best Journal paper Award for his work on ad hoc TCP. CK was formerly the Chairman of IEEE Communications Society Technical Committee on Computer Communications and Chairman of IEEE Subcommittee on Ad Hoc Mobile Wireless Networks. He was an IEEE Expert/Distinguished Lecturer and had served as a Steering Committee Member for IEEE WCNC Conference and IEEE Transaction on Mobile Computing. He was a member of IEEE Communications Society Meetings & Conferences Board. CK was an editor for IEEE Networks, IEEE JSAC, IEEE transactions on Wireless Communications, Journal on Communication Networks, and IEEE Distributed Systems. He is a Fellow of four societies: British Computer Society, the IEE, the Hong Kong Institution of Engineers and the New Zealand Computer Society. He received his Ph.D. degree in Computer Science from Cambridge University, England, and his executive education from Harvard.     

Performance of Multilayered Video Encoding and Delivery over Lossy Channels Using a Joint Source-Channel Coding Approach

In this paper, the performance of selected error-control schemes based on forward error-control (FEC) coding for H.263+ video transmission over an additive white Gaussian noise (AWGN) channel is studied. Joint source and channel coding (JSCC) techniques that employ single-layer and 2-layer H.263+ coding in conjunction with unequal error protection (UEP) to combat channel errors are quantitatively compared. Results indicate that with appropriate joint source and channel coding, tailored to the respective layers, FEC-based error control in combination with 2-layer video coding techniques can lead to more acceptable quality for wireless video delivery in the presence of channel impairments. Yong Pei is currently a tenure-track assistant professor in the Computer Science and Engineering Department, Wright State University, Dayton, OH. Previously he was a visiting assistant professor in the Electrical and Computer Engineering Department, University of Miami, Coral Gables, FL. He received his B.S. degree in electrical power engineering from Tsinghua University, Beijing, in 1996, and M.S. and Ph.D. degrees in electrical engineering from Rensselaer Polytechnic Institute, Troy, NY, in 1999 and 2002, respectively. His research interests include information theory, wireless communication systems and networks, and image/video compression and communications. He is a member of IEEE and ACM. James W. Modestino (S′67- M′73- SM′81- F′87) was born in Boston, MA, on April 27, 1940. He received the B.S. degree from Northeastern University, Boston, MA, in 1962, and the M.S. degree from the University of Pennsylvania, Philadelphia, PA, in 1964, both in electrical engineering. He also received the M.A. and Ph.D. degrees from Princeton University, Princeton, NJ, in 1968 and 1969, respectively. He has held a number of industrial positions, including positions with RCA Communications Systems Division, Camden, NJ; General Electronic Laboratories, Cambridge, MA; AVCO Systems Division, Wilmington, MA; GTE Laboratories, Waltham, MA; and MIT Lincoln Laboratories, Lexington, MA. From 1970 to 1972, he was an Assistant Professor in the Department of Electrical Engineering, Northeastern University. In 1972, he joined Rensselaer Polytechnic Institute, Troy, NY, where until leaving in 2002 he was an Institute Professor in the Electrical, Computer and Systems Engineering Department and Director of the Center for Image Processing Research. He has been responsible for teaching and research in the communication, information and signal processing systems area. His specific research interests include communication in fading dispersive channels; detection, estimation and filtering in impulsive or burst noise environments; digital signal, image and video processing; and multimedia communication systems and networks. In 2002 he joined the Department of Electrical and Computer Engineering at the University of Miami, Coral Gables, FL, as the Victor E. Clarke Endowed Scholar, Professor and Chair. He has held visiting positions with the University of California at San Diego, LaJolla, CA (1981–1982); GE Research and Development Center, Schenectady, NY (1988–1989); and Massachusetts Institute of Technology, Cambridge, MA (1995–1996). Dr. Modestino is a past member of the Board of Governors of the IEEE Information Theory Group. He is a past Associate Editor and Book Review Editor for the IEEE TRANSACTIONS ON INFORMATION THEORY. In 1984, he was co-recipient of the Stephen O. Rice Prize Paper Award from the IEEE Communications Society and in 2000 he was co-recipient of the best paper award at the International Packet Video Conference.     

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.     

Energy-aware on-demand routing protocols for wireless ad hoc networks

Energy use is a crucial design concern in wireless ad hoc networks since wireless terminals are typically battery-operated. The design objectives of energy-aware routing are two folds: Selecting energy-efficient paths and minimizing the protocol overhead incurred for acquiring such paths. To achieve these goals simultaneously, we present the design of several on-demand energy-aware routing protocols. The key idea behind our design is to adaptively select the subset of nodes that are required to involve in a route-searching process in order to acquire a high residual-energy path and/or the degree to which nodes are required to participate in the process of searching for a low-power path in networks wherein nodes have transmission power adjusting capability. Analytical and simulation results are given to demonstrate the high performance of the designed protocols in energy-efficient utilization as well as in reducing the protocol overhead incurred in acquiring energy-efficient routes. Baoxian Zhang received his B.S., M.S., and Ph.D. degrees in Electrical Engineering from Northern Jiaotong University, Beijing, China in 1994, 1997, and 2000, respectively. From January 2001 to August 2002, he was working with Department of Electrical and Computer Engineering at Queen’s University in Kingston as a postdoctoral fellow. He is currently a research scientist with the School of Information Technology and Engineering (SITE) of University of Ottawa in Ottawa, Ontario, Canada. He has published over 40 refereed technical papers in international journals and conference proceedings. His research interests include routing algorithm and protocol design, QoS management, wireless ad hoc and sensor networks, survivable optical networks, multicast communications, and performance evaluation. He is a member of the IEEE. Hussein Mouftah joined the School of Information Technology and Engineering (SITE) of the University of Ottawa in September 2002 as a Canada Research Chair (Tier 1) Professor in Optical Networks. He has been with the Department of Electrical and Computer Engineering at Queen’s University (1979-2002), where he was prior to his departure a Full Professor and the Department Associate Head. He has three years of industrial experience mainly at Bell Northern Research of Ottawa, now Nortel Networks (1977-79). He has spent three sabbatical years also at Nortel Networks (1986-87, 1993-94, and 2000-01), always conducting research in the area of broadband packet switching networks, mobile wireless networks and quality of service over the optical Internet. He served as Editor-in-Chief of the IEEE Communications Magazine (1995-97) and IEEE Communications Society Director of Magazines (1998-99) and Chair of the Awards Committee (2002-2003). He is a Distinguished Speaker of the IEEE Communications Society since 2000. Dr. Mouftah is the author or coauthor of five books, 22 book chapters and more than 700 technical papers and 8 patents in this area. He is the recipient of the 1989 Engineering Medal for Research and Development of the Association of Professional Engineers of Ontario (PEO), and the Ontario Distinguished Researcher Award of the Ontario Innovation Trust. He is the joint holder of the Best Paper Award for a paper presented at SPECTS’2002, and the Outstanding Paper Award for papers presented at the IEEE HPSR’2002 and the IEEE ISMVL’1985. Also he is the joint holder of a Honorable Mention for the Frederick W. Ellersick Price Paper Award for Best Paper in the IEEE Communications Magazine in 1993. He is the recipient of the IEEE Canada (Region 7) Outstanding Service Award (1995). Also he is the recipient of the 2004 IEEE Communications Society Edwin Howard Armstrong Achievement Award, and the 2004 George S. Glinski Award for Excellence in Research of the Faculty of Engineering, University of Ottawa. Dr. Mouftah is a Fellow of the IEEE (1990) and Fellow of the Canadian Academy of Engineering (2003).     

A Novel Random Backoff Algorithm to Enhance the Performance of IEEE 802.11 DCF

The Probability Distribution of Slot Selection (PDoSS) of IEEE 802.11 DCF is extremely uneven, which makes the packet collision probability very high. In this paper, we propose a novel RWBO+BEB backoff algorithm for 802.11 DCF to make the PDoSS even and thus decrease the packet collision probability. A Markov model is built for analyzing RWBO+BEB's PDoSS and saturation throughput. The model's correctness is validated by simulation. The performance of RWBO+BEB is also evaluated by simulation in terms of PDoSS, saturation throughput, packet collision probability and packet delay. The simulation results indicate that RWBO+BEB can decrease the packet collision probability to a large extent, utilize the channel more efficiently, and make the packet delay jitter much lower comparing to 802.11 DCF. Moreover, we analyze the relation of saturation throughput and packet collision probability to walking probability (p_d) and contention windows (w), respectively. The analysis indicates that RWBO+BEB has a remarkable feature: its saturation throughput keeps high, and packet collision probability keeps very low (which under 0.1) in a large range of p_d and w, this allows us to configure p_d and w more flexibly. Supported by the Program for New Century Excellent Talents in University (NCET 2005), the Research Project of Chongqing Municipal Education Commission of China (KJ050503), the Research Grants by the Science & Tech. Commission of Chongqing (8817) and the National Science Foundation of China (90304004). Li Yun was born in 1974. He is currently a Ph.D. candidate in University of Electronic Science and Technology of China. His research interests are in MAC protocol improvement and QoS in wireless ad hoc networks. Long Ke-Ping was born in 1968. He received his Ph.D. from University of Electronic Science and Technology of China in 1999. He is a professor Ph.D. supervisor in special research Centre for Optical Internet and Wireless Information Networks (COIWIN) at ChongQing University of Posts and Telecommunications. He was an IEEE member. He has over 120 research publications and 4 patents application. His research interests include: Optical Burst switching, modeling of optical networking, IP QoS mechanisms (Diffserv and Intserv, MPLS), WDM/SDH/ATM networks survivability, TCP/IP enhancements in wireless networks, and Mobile IP. Zhao Wei-liang was born in 1962 and received his Ph.D. degree from University of Electronic Science and Technology of China in 2001. He is a professor and a post-doctoral fellow in Beijing University of Posts & Telecommunications of China. His current interest lies in wireless communications.     

Downlink traffic control for multiple classes of services in MC-CDMA cellular systems

We consider the problem of downlink traffic control in Multi-code Code Division Multiple Access (MC-CDMA) systems, which support multiple classes of services with diverse QoS requirements. Prior solutions proposed for this problem have largely focused on call admission control at the connection level while neglecting the stochastic behavior of mobile subscribers and channel conditions. We quantitatively demonstrate that these statistical factors, in particular log-normal shadowing in propagation and voice activity factors, have a significant impact on the connection-level performance. Furthermore, we show that conventional data services can be best handled at the packet level as background transmissions by taking advantage of these statistical variations, which leads to significantly better utilization of the scarce wireless spectrum. The research was supported in part by grants from RGC under the contracts HKUST6104/04E and HKUST6165/05E, a grant from NSFC/RGC under the contract N_HKUST605/02, a grant from NSF China under the contract 60429202. Jihui Zhang’s work was partially supported by Microsoft fellowship. Jihui Zhang (S’02) received her B.S. degree from Fudan University, China in 2001, and the Ph.D. degree from the Hong Kong University of Science and Technology in 2005, both in the Computer Science. Her research interests include CDMA cellular networks and wireless ad-hoc networks. Bo Li (S’89-M’92-SM’99) received his B. Eng. and M. Eng. degrees in the Computer Science from Tsinghua University, Beijing in 1987 and 1989, respectively, and the Ph.D. degree in the Electrical and Computer Engineering from University of Massachusetts at Amherst in 1993. Between 1993 and 1996, he worked on high performance routers and ATM switches in IBM Networking System Division, Research Triangle Park, North Carolina. Since 1996, he has been with the Department of Computer Science, Hong Kong University of Science and Technology, where he is now an associated professor and Co-Director for the ATM/IP Cooperate Research Center, a government sponsored research center. He also holds an adjunct researcher position at the Microsoft Research Asia (MSRA), Beijing, China, and adjunct professorship in several universities. His recent research interests are on adaptive video multicast, packet scheduling and dynamic routing in optical networks, resource management in mobile wireless systems, scheduling and energy efficient routing in ad hoc networks, across layer design for sensor networks, and content distribution and replication. He has published 150 papers and held several patents in above areas. He has been on editorial board for 16 journals, mainly in IEEE and ACM. He has been involved in organizing over 40 conferences, esp. IEEE Infocom since 1996. He was the Co-TPC Chair for IEEE Infocom 2004.     

802.11 power-saving mode for mobile computing in Wi-Fi hotspots: Limitations,enhancements and open issues

Nowadays Wi-Fi is the most mature technology for wireless-Internet access. Despite the large (and ever increasing) diffusion of Wi-Fi hotspots, energy limitations of mobile devices are still an issue. To deal with this, the standard 802.11 includes a Power-Saving Mode (PSM), but not much attention has been devoted by the research community to understand its performance in depth. We think that this paper contributes to fill the gap. We focus on a typical Wi-Fi hotspot scenario, and assess the dependence of the PSM behavior on several key parameters such as the packet loss probability, the Round Trip Time, the number of users within the hotspot. We show that during traffic bursts PSM is able to save up to 90% of the energy spent when no energy management is used, and introduces a limited additional delay. Unfortunately, in the case of long inactivity periods between bursts, PSM is not the optimal solution for energy management. We thus propose a very simple Cross-Layer Energy Manager (XEM) that dynamically tunes its energy-saving strategy depending on the application behavior and key network parameters. XEM does not require any modification to the applications or to the 802.11 standard, and can thus be easily integrated in current Wi-Fi devices. Depending on the network traffic pattern, XEM reduces the energy consumption of an additional 20–96% with respect to the standard PSM. This work has been carried out while A. Passarella was with the Department of Information Engineering of the University of Pisa. Giuseppe Anastasi is an associate professor of Computer Engineering at the Department of Information Engineering of the University of Pisa, Italy. He received the Laurea (cum laude) degree in Electrical Engineering, and the Ph.D. degree in Computer Engineering, both from the University of Pisa, in 1990 and 1995, respectively. His research interests include mobile and pervasive computing, ad hoc and sensor networks, and power management. He is a co-editor of the book Advanced Lectures in Networking (LNCS 2497, Springer, 2002), and has published more than 60 papers in the area of computer networking and pervasive computing, both in international journals and conference proceedings. He is a member of the editorial board of the Journal of Ubiquitous Computing and Intelligence (JUCI), and is currently serving as Vice Program Co-Chair for the IEEE MASS 2007 conference. He has served as general chair for IEEE WoWMoM 2005, Workshops Chair for IEEE PerCom 2006 and IEEE WoWMoM 2006, and program chair for several international workshops. He has also served on the Technical Program Committee of many international conferences. He is a member of the IEEE Computer Society. Marco Conti is a research director at IIT, an institute of the Italian National Research Council (CNR). He co-authored the book “Metropolitan Area Networks” (Springer, 1997) and is co-editor of the book “Mobile Ad Hoc Networking” (IEEE-Wiley 2004). He published in journals and conference proceedings more than 180 research papers related to design, modeling, and performance evaluation of computer-network architectures and protocols. He served as TPC chair of IEEE PerCom 2006, and of the IFIP-TC6 Conferences “Networking2002” and “PWC2003”, and as TPC co-chair of ACM WoWMoM 2002, WiOpt ’04, IEEE WoWMoM2005, and ACM MobiHoc2006. He served as general co-chair of IEEE WoWMoM 2006 and as general chair of ACM REALMAN 2006. Currently, he is serving as general chair of IEEE MASS 2007. He is Associate Editor of Pervasive and Mobile Computing Journal, and he is on the editorial board of: IEEE Transactions on Mobile Computing, Ad Hoc Networks journal and Wireless Ad Hoc and Sensor Networks: An International Journal. Enrico Gregori received the Laurea in electronic engineering from the University of Pisa in 1980. In 1981 he joined the Italian National Research Council (CNR) where he is currently a CNR research director. He is currently the deputy director of the CNR institute for Informatics and Telematics (IIT). In 1986 he held a visiting position in the IBM research center in Zurich working on network software engineering and on heterogeneous networking. He has contributed to several national and international projects on computer networking. He has authored more than 100 papers in the area of computer networks and has published in international journals and conference proceedings and is co-author of the book “Metropolitan Area Networks” (Springer, London 1997). He was the General Chair of the IFIP TC6 conferences: Networking2002and PWC2003 (Personal Wireless Communications) and IEEE Pervasive Computing and Communication (PERCOM) 2006. He served as guest editor for the Networking2002 journal special issues on: Performance Evaluation, Cluster Computing and ACM/Kluwer Wireless Networks Journals. He is a member of the board of directors of the Create-Net association, an association with several Universities and research centers that is fostering research on networking at European level. He is on the editorial board of the Cluster Computing, of the Computer Networks and of the Wireless Networks Journals. His current research interests include: Ad hoc networks, Sensor networks, Wireless LANs, Quality of service in packet-switching networks, Evolution of TCP/IP protocols. Andrea Passarella is a Researcher at the IIT Institute of the National Research Council (CNR), Italy. Before joining IIT, he was a Research Associate at the Computer Laboratory of the University of Cambridge, UK. He received the Ph.D. and M.S. Degrees in Computer Engineering, both from the University of Pisa, Italy, in 2005 and 2001, respectively. His current research is mostly on opportunistic and delay-tolerant networking. More in general, he works on ad hoc and sensor networks, specifically on p2p systems, multicasting, transport protocols, and energy-efficient protocols. His research interests also include mesh networks and wireless access to the Internet. He is Co-Editor of the book “Multi-hop Ad hoc Networks: From Theory to Reality” (Nova Science, 2007). He was TPC Vice-Chair for IEEE REALMAN 2005, ACM REALMAN 2006, and IEEE MDC 2006. He served and is currently serving in the TPC of several international conferences, including IEEE PerCom 2006/07 and IEEE WoWMoM 2006/07, and workshops. He is an Associate Technical Editor for IEEE Communications Magazine. He is a member of ACM SIGMOBILE.     

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

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

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.     

Performance of a burst-frame-based CSMA/CA protocol: Analysis and enhancement

In this paper, we develop an analytical model to evaluate the delay performance of the burst-frame-based CSMA/CA protocol under unsaturated conditions, which has not been fully addressed in the literature. Our delay analysis is unique in that we consider the end-to-end packet delay, which is the duration from the epoch that a packet enters the queue at the MAC layer of the transmitter side to the epoch that the packet is successfully received at the receiver side. The analytical results give excellent agreement with the simulation results, which represents the accuracy of our analytical model. The results also provide important guideline on how to set the parameters of the burst assembly policy. Based on these results, we further develop an efficient adaptive burst assembly policy so as to optimize the throughput and delay performance of the burst-frame-based CSMA/CA protocol. Kejie Lu received the B.E. and M.E. degrees in Telecommunications Engineering from Beijing University of Posts and Telecommunications, Beijing, China, in 1994 and 1997, respectively. He received the Ph.D. degree in Electrical Engineering from the University of Texas at Dallas in 2003. In 2004 and 2005, he was a postdoctoral research associate in the Department of Electrical and Computer Engineering, University of Florida. Currently, he is an assistant professor in the Department of Electrical and Computer Engineering, University of Puerto Rico at Mayagüez. His research interests include architecture and protocols design for computer and communication networks, performance analysis, network security, and wireless communications. Jianfeng Wang received the B.E. and M.E. degrees in electrical engineering from Huazhong University of Science and Technology, China, in 1999 and 2002, respectively, and the Ph.D. degree in electrical engineering from University of Florida in 2006. From January 2006 to July 2006, he was a research intern in wireless standards and technology group, Intel Corporation. In October 2006, he joined Philips Research North America as a senior member research staff in wireless communications and networking department. He is engaged in research and standardization on wireless networks with emphasis on medium access control (MAC). Dapeng Wu received B.E. in Electrical Engineering from Huazhong University of Science and Technology, Wuhan, China, in 1990, M.E. in Electrical Engineering from Beijing University of Posts and Telecommunications, Beijing, China, in 1997, and Ph.D. in Electrical and Computer Engineering from Carnegie Mellon University, Pittsburgh, PA, in 2003. Since August 2003, he has been with Electrical and Computer Engineering Department at University of Florida, Gainesville, FL, as an Assistant Professor. His research interests are in the areas of networking, communications, multimedia, signal processing, and information and network security. He received the IEEE Circuits and Systems for Video Technology (CSVT) Transactions Best Paper Award for Year 2001, and the Best Paper Award in International Conference on Quality of Service in Heterogeneous Wired/Wireless Networks (QShine) 2006. Currently, he serves as the Editor-in-Chief of Journal of Advances in Multimedia, and an Associate Editor for IEEE Transactions on Wireless Communications, IEEE Transactions on Circuits and Systems for Video Technology, IEEE Transactions on Vehicular Technology, and International Journal of Ad Hoc and Ubiquitous Computing. He is also a guest-editor for IEEE Journal on Selected Areas in Communications (JSAC), Special Issue on Cross-layer Optimized Wireless Multimedia Communications. He served as Program Chair for IEEE/ACM First International Workshop on Broadband Wireless Services and Applications (BroadWISE 2004); and as a technical program committee member of over 30 conferences. He is Vice Chair of Mobile and wireless multimedia Interest Group (MobIG), Technical Committee on Multimedia Communications, IEEE Communications Society. He is a member of the Best Paper Award Committee, Technical Committee on Multimedia Communications, IEEE Communications Society. Yuguang Fang received a Ph.D. degree in Systems Engineering from Case Western Reserve University in January 1994 and a Ph.D. degree in Electrical Engineering from Boston University in May 1997. He was an assistant professor in the Department of Electrical and Computer Engineering at New Jersey Institute of Technology from July 1998 to May 2000. He then joined the Department of Electrical and Computer Engineering at University of Florida in May 2000 as an assistant professor and got an early promotion to an associate professor with tenure in August 2003 and to a full professor in August 2005. He has published over 200 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 has served on several editorial boards of technical journals including IEEE Transactions on Communications, IEEE Transactions on Wireless Communications, IEEE Transactions on Mobile Computing and ACM Wireless Networks. He have also been actively participating in professional conference organizations such as serving as The Steering Committee Co-Chair for QShine, the Technical Program Vice-Chair for IEEE INFOCOM’2005, Technical Program Symposium Co-Chair for IEEE Globecom’2004, and a member of Technical Program Committee for IEEE INFOCOM (1998, 2000, 2003–2007). He is a senior member of the IEEE.     

Cross-layer radio resource allocation in packet CDMA wireless mobile networks

An efficient radio resource allocation scheme is crucial for guaranteeing the quality of service (QoS) requirements and fully utilizing the scarce radio resources in wireless mobile networks. Most of previous studies of radio resource allocation in traditional wireless networks concentrates on network layer connection blocking probability QoS. In this paper, we show that physical layer techniques and QoS have significant impacts on network layer QoS. We use a concept of cross-layer effective bandwidth to measure the unified radio resource usage taking into account both physical layer linear minimum-mean square error (LMMSE) receivers and varying statistical characteristics of the packet traffic in code devision multiple access (CDMA) networks. We demonstrate the similarity between traditional circuit-switched networks and packet CDMA networks, which enables rich theories developed in traditional wireless mobile networks to be used in packet CDMA networks. Moreover, since both physical layer signal-to-interference ratio (SIR) QoS and network layer connection blocking probability QoS are considered simultaneously, we can explore the tradeoff between physical layer QoS and network layer QoS in packet CDMA networks. This work is supported by Natural Science and Engineering Research Council of Canada. Please address all correspondence to Professor Vikram Krishnamurthy at the above address. Fei Yu received the Ph.D. degree in electrical engineering from the University of British Columbia in 2003. From 2002 to 2004, he was with Ericsson (in Lund, Sweden), where he worked on the research and development of dual mode UMTS/GPRS handsets. From 2005, he has been working in Silicon Valley at a start-up, where he conducts research and development in the areas of advanced wireless communication technologies and new standards. After completing the PhD, he has been a research associate in the Department of Electrical and Computer Engineering at the University of British Columbia. His research interests include cross-layer optimization, QoS provisioning and security in wireless networks. Vikram Krishnamurthy (S’90-M’91-SM’99-F’05) was born in 1966. He received his bachelor’s degree from the University of Auckland, New Zealand in 1988, and Ph.D. from the Australian National University, Canberra, in 1992. Since 2002, he has been a professor and Canada Research Chair at the Department of Electrical Engineering, University of British Columbia, Vancouver, Canada. Prior to this he was a chaired professor at the Department of Electrical and Electronic Engineering, University of Melbourne, Australia. His research interests span several areas including ion channels and nanobiology, stochastic scheduling and control, statistical signal processing and wireless telecommunications. Dr. Krishnamurthy has served as associate editor for IEEE Transactions on Signal Processing, IEEE Transactions Aerospace and Electronic Systems, IEEE Transactions Nanobioscience, IEEE Transactions Circuits and Systems II, Systems and Control Letters and European Journal of Applied Signal Processing. He was guest editor of a special issue of IEEE Transactions on NanoBioScience, March 2005 on bio-nanotubes.