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.     

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

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

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).     

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.     

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.     

Localized algorithms for coverage boundary detection in wireless sensor networks

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

Relay sensor placement in wireless sensor networks

This paper addresses the following relay sensor placement problem: given the set of duty sensors in the plane and the upper bound of the transmission range, compute the minimum number of relay sensors such that the induced topology by all sensors is globally connected. This problem is motivated by practically considering the tradeoff among performance, lifetime, and cost when designing sensor networks. In our study, this problem is modelled by a NP-hard network optimization problem named Steiner Minimum Tree with Minimum number of Steiner Points and bounded edge length (SMT-MSP). In this paper, we propose two approximate algorithms, and conduct detailed performance analysis. The first algorithm has a performance ratio of 3 and the second has a performance ratio of 2.5. Xiuzhen Cheng is an Assistant Professor in the Department of Computer Science at the George Washington University. She received her MS and PhD degrees in Computer Science from the University of Minnesota - Twin Cities in 2000 and 2002, respectively. Her current research interests include Wireless and Mobile Computing, Sensor Networks, Wireless Security, Statistical Pattern Recognition, Approximation Algorithm Design and Analysis, and Computational Medicine. She is an editor for the International Journal on Ad Hoc and Ubiquitous Computing and the International Journal of Sensor Networks. Dr. Cheng is a member of IEEE and ACM. She received the National Science Foundation CAREER Award in 2004. Ding-Zhu Du received his M.S. degree in 1982 from Institute of Applied Mathematics, Chinese Academy of Sciences, and his Ph.D. degree in 1985 from the University of California at Santa Barbara. He worked at Mathematical Sciences Research Institutea, Berkeley in 1985-86, at MIT in 1986-87, and at Princeton University in 1990-91. He was an associate-professor/professor at Department of Computer Science and Engineering, University of Minnesota in 1991-2005, a professor at City University of Hong Kong in 1998-1999, a research professor at Institute of Applied Mathematics, Chinese Academy of Sciences in 1987-2002, and a Program Director at National Science Foundation of USA in 2002-2005. Currently, he is a professor at Department of Computer Science, University of Texas at Dallas and the Dean of Science at Xi’an Jiaotong University. His research interests include design and analysis of algorithms for combinatorial optimization problems in communication networks and bioinformatics. He has published more than 140 journal papers and 10 written books. He is the editor-in-chief of Journal of Combinatorial Optimization and book series on Network Theory and Applications. He is also in editorial boards of more than 15 journals. Lusheng Wang received his PhD degree from McMaster University in 1995. He is an associate professor at City University of Hong Kong. His research interests include networks, algorithms and Bioinformatics. He is a member of IEEE and IEEE Computer Society. Baogang Xu received his PhD degree from Shandong University in 1997. He is a professor at Nanjing Normal University. His research interests include graph theory and algorithms on graphs.     

ZBP: A Zone-Based Broadcasting Protocol for Wireless Sensor Networks

Wireless Sensor Networks (WSNs) have been widely used in motoring and collecting interests of environment information. Packet flooding or broadcasting is an essential function for establishing a communication path from sink node to a region of sensor nodes. However, flooding operation consumes power and bandwidth resources and raises the packet collision and contention problems, which reduce the success rate of packet transmissions and consume energy. This article proposes an efficient broadcasting protocol to reduce the number of sensor nodes that forward the query request, hence improves the packet delivery rate and saves bandwidth and power consumptions. Sensor node that received the query request will dynamically transfers the coordinate system according to the zone-ID of source node and determines whether it would forward the request or not in a distributed manner. Compared with the CBM and traditional flooding operation, experimental results show that the proposed zone-based broadcasting protocol decreases the bandwidth and power consumptions, reduces the packet collisions, and achieves high success rate of packet broadcasting.Chih-Yung Chang received the Ph.D. degree in Computer Science and Information Engineering from National Central University, Taiwan, in 1995. He joined the faculty of the Department of Computer and Information Science at Aletheia University, Taiwan, as an Assistant Professor in 1997. He was the Chair of the Department of Computer and Information Science, Aletheia University, from August 2000 to July 2002. He is currently an Associate Professor of Department of Computer Science and Information Engineering at Tamkang University, Taiwan. Dr. Chang served as an Associate Guest Editor of Journal of Internet Technology (JIT), Special Issue on “Wireless Ad Hoc and Sensor Networks” (2004) and a member of Editorial Board of Tamsui Oxford Journal of Mathematical Sciences (2001–2005). He was an Area Chair of IEEE AINA′2005, Vice Chair of IEEE WisCom2005, Track Chair (Learning Technology in Education Track) of IEEE ITRE′2005, Program Co-Chair of MNSA′2005, Workshop Co-Chair of INA′2005, MSEAT′2003, MSEAT′2004, Publication Chair of MSEAT′2005, and the Program Committee Member of ICPP′2004, USW′2005, WASN′2005, and the 11th Mobile Computing Workshop. Dr. Chang is a member of the IEEE Computer Society and IEICE society. His current research interests include wireless sensor networks, mobile learning, Bluetooth radio systems, Ad Hoc wireless networks, and mobile computing.Kuei-Ping Shih received the B.S. degree in Mathematics from Fu-Jen Catholic University, Taiwan, Republic of China, in June 1991 and the Ph.D. degree in Computer Science and Information Engineering from National Central University, Taiwan, Republic of China, in June 1998. After two years of military obligation, he joined the faculty of the Department of Computer Science and Information Engineering, Tamkang University, Taiwan, Republic of China, as an assistant professor in 2000. Dr. Shih served as a Program Area Chair in the IEEE International Conference on Advanced Information Networking and Applications (AINA), 2005, and as a Technical Track Chair in the IEEE International Conference on Information Technology: Research and Education (ITRE), 2005. Dr. Shih’s current research interests include wireless networks, sensor networks, mobile computing, and network protocols design.Dr. Shih is a member of the IEEE Computer and Communication Societies and Phi Tau Phi Scholastic Honor Society.Shih-Chieh Lee received the B.S. degree in Computer Science and Information Engineering from Tamkang University, Taiwan, in 1997. Since 2003 he has been a Ph.D. Students in Department of Computer Science and Information Engineering, Tamkang University. His research interests are wireless sensor networks, Ad Hoc wireless networks, and mobile/wireless computing.     

Non-Cooperative Games for Service Differentiation in CDMA Systems

In this paper, we address the problem of user-class based service differentiation in CDMA networks. Users are categorized into three classes who get differentiated services based on their expected quality of service (QoS) from the service provider and the price they are willing to pay. We adopt a game theoretic approach for allocating resources through a two-step process. During a service admission, resource distribution is determined for each class. Then, the resource allocated to each class is distributed among the active users in that class. We devise a utility function for the providers which considers the expected revenue and the probability of users leaving their service provider if they are not satisfied with the service. Our model demonstrates how power can be controlled in a CDMA network to differentiate the service quality. Also, we show the impact of admitting high paying users on other users. Mainak Chatterjee received his Ph.D. from the department of Computer Science and Engineering at The University of Texas at Arlington in 2002. Prior to that, he completed his B.Sc. with Physics (Hons) from the University of Calcutta in 1994 and M.E. in Electrical Communication Engineering from the Indian Institute of Science, Bangalore, in 1998. He is currently an Assistant Professor in the department of Electrical and Computer Engineering at the University of Central Florida. His research interests include economic issues in wireless networks, applied game theory, resource management and quality-of-service provisioning, ad hoc and sensor networks, CDMA data networking, and link layer protocols. He serves on the executive and technical program committee of several international conferences. Haitao Lin received the BE degree in radio engineering from Southeast University, Nanjing, China, in 1996, the MS degree in computer applications from the Beijing University of Posts and Telecommunications, Beijing, China, in 2000, and Ph.D. in Computer Science and Engineering from The University of Texas at Arlington in 2004. He is currently with Converged Multimedia Services System Engineering at Nortel, Richardson, Texas. His research interests include wireless network performance evaluation and enhancement, wireless link adaptation, wireless network resource management, and applied game theory. Sajal K. Das received B.S. degree in 1983 from Calcutta University, M.S. degree in 1984 from Indian Institute of Science, Bangalore, and Ph.D. degree in 1988 from University of Central Florida, Orlando, all in Computer Science. He is currently a Professor of Computer Science and Engineering and also the Founding Director of the Center for Research in Wireless Mobility and Networking (CReWMaN) at the University of Texas at Arlington (UTA). Prior to 1999, he was a professor of Computer Science at the University of North Texas (UNT), Denton where he founded the Center for Research in Wireless Computing (CReW) in 1997, and also served as the Director of the Center for Research in Parallel and Distributed Computing (CRPDC) during 1995–97. Dr. Das is a recipient of the UNT Student Association's Honor Professor Award in 1991 and 1997 for best teaching and scholarly research; UNT's Developing Scholars Award in 1996 for outstanding research; UTA's Outstanding Faculty Research Award in Computer Science in 2001 and 2003; and the UTA College of Engineering Research Excellence Award in 2003. He is also frequently invited as a keynote speaker at international conferences and symposia. Dr. Das' current research interests include mobile wireless communications, resource and mobility management in wireless networks, mobile and pervasive computing, wireless multimedia, ad hoc and sensor networks, mobile internet architectures and protocols, distributed and grid computing, performance modeling and simulation. He has published over 350 research papers in these areas in international journals and conferences, directed numerous industry and government funded projects, and holds five US patents in wireless mobile networks. He received four Best Paper Awards in the ACM MobiCom'99, ICOIN'01, ACM MSWiM'00, and ACM/IEEE PADS'97. He as the Editor in Chief of the Pervasive and Mobile Computing (PMC) journal and also as an Associate Editor of IEEE Transactions on Mobile Computing, ACM/Kluwer Wireless Networks, Parallel Processing Letters, Journal of Parallel, Distributed and Emerging Systems. He served as General Chair of IEEE WoWMoM'05, PerCom'04, IWDC'04, MASCOTS'02, ACM WoWMoM'00-02; General Vice Chair of IEEE PerCom'03, ACM MobiCom'00 and IEEE HiPC'00-01; Program Chair of IWDC'02, WoWMoM'98-99; TPC Vice Chair of ICPADS'02; and as TPC member of numerous IEEE and ACM conferences. He is Vice Chair of the IEEE Computer Society's TCPP and TCCC Executive Committees.     

Utility based service differentiation in CDMA data networks

The wireless data services are getting more and more competitive because of the presence of multiple service providers, all of whom offer some relative advantages and flexibilities over the others. As a result, the user churn behavior (i.e., migration from one service provider to another) is causing tremendous revenue loss for the service providers and also failure of existing resource management algorithms to fully capture the impact of churning. Moreover, the quality of service (QoS) offered to users belonging to different classes calls for new resource management schemes that address the issues related to differentiated services. In this paper, we propose a framework to study the impact of user churn behavior on the resource management algorithms to provide class-based differentiated services in CDMA data networks. In particular, our framework incorporates the user churning behavior into the admission control and power management algorithms, so that the service provider’s revenue loss due to churn can be minimized. Since optimal rate/power allocation in multi-rate CDMA systems is in general NP-Complete, we provide heuristics that try to provide solutions to the resource allocation problem in real-time. In our proposed framework, we add another layer of power management called Class-Based Power Allocation/Reduction (CBPAR) function, which works with the rate control algorithm to achieve power allocation. With CBPAR, the number of variables of the optimization problem is significantly reduced helping achieve the results in real-time. Our simulation study shows that the service provider’s revenue can be improved with the help of CBPAR framework. It also reveals the relationship between users’ sensitivity and tolerance to QoS degradation and optimal power allocations. Haitao Lin received his PhD in Computer Science and Engineering from the University of Texas at Arlington in 2004. He received his B.E. degree in Radio Engineering from Southeast University, Nanjing, China, in 1996 and the MS degree in Computer Applications from the Beijing University of Posts and Telecommunications, Beijing, China, in 2000. He is currently with Converged Multimedia Networks (CMN) Systems Engineering at Nortel, Richardson, Texas. His research interests include wireless network performance evaluation and enhancement, wireless link adaptation, wireless network resource management, applied game theory, network overload control performance modeling and analysis. Mainak Chatterjee received his Ph.D. from the department of Computer Science and Engineering at The University of Texas at Arlington in 2002. Prior to that, he completed his B.Sc. with Physics (Hons) from the University of Calcutta in 1994 and M.E. in Electrical Communication Engineering from the Indian Institute of Science, Bangalore, in 1998. He is currently an Assistant Professor in the department of Electrical and Computer Engineering at the University of Central Florida. His research interests include economic issues in wireless networks, applied game theory, resource management and quality-of-service provisioning, ad hoc and sensor networks, CDMA data networking, and link layer protocols. He serves on the executive and technical program committee of several international conferences. Sajal K. Das received the BTech degree in 1983 from Calcutta University, the MS degree in 1984 from the Indian Institute of Science, Bangalore, and the PhD degree in 1988 from the University of Central Florida, Orlando, all in computer science. Prior to 1999, he was a professor of computer science at the University of North Texas, where he twice (in 1991 and 1997) received the Student Associationís Honor Professor Award for best teaching and scholarly research. Currently, he is a professor of computer science and engineering and also the founding director of the Center for Research in Wireless Mobility and Networking (CReWMaN) at the University of Texas at Arlington (UTA). His current research interests include resource and mobility management in wireless and sensor networks, mobile and pervasive computing, wireless multimedia and QoS provisioning, mobile Internet protocols, distributed processing, and grid computing. He has published more than 350 research papers, directed numerous funded projects, and holds five US patents in wireless mobile networks. He received the Best Paper Award in ACM MobiComí99, ICOINí01, ACM MSWIMí00, and ACM/IEEE PADSí97. He was also a recipient of UTAís Outstanding Faculty Research Award in Computer Science in 2001 and 2003, and UTAís College of Engineering Excellence in Research Award in 2003. He is the coauthor of a book Smart Environments: Technology, Protocols and Applications, published in 2004 by John Wiley. Dr. Das is the editor-in-chief of the Pervasive and Mobile Computing journal and serves on the editorial Boards of four international journals, including IEEE Transactions on Mobile Computing and ACM/Kluwer Wireless Networks. He has served as general chair of IEEE WoWMoMí05, IWDCí04, IEEE PerComí04, CITí03, and IEEE MASCOTSí02; general vice chair of IEEE PerComí03, ACM Mobi- Comí00, and HiPCí00-01; program chair of IWDCí02 and WoWMoMí98-99; TPC vice chair of CITí05 and ICPADSí02; and as TPC member of numerous IEEE and ACM conferences. He is the vice chair of IEEE Technical Committees (TCPP and TCCC) and on the Advisory Boards of several cutting-edge companies. He is a member of the IEEE Computer Society.     

Energy-Efficient Data Caching and Prefetching for Mobile Devices Based on Utility

In mobile computing environments, vital resources like battery power and wireless channel bandwidth impose significant challenges in ubiquitous information access. In this paper, we propose a novel energy and bandwidth efficient data caching mechanism, called GreedyDual Least Utility (GD-LU), that enhances dynamic data availability while maintaining consistency. The proposed utility-based caching mechanism considers several characteristics of mobile distributed systems, such as connection-disconnection, mobility handoff, data update and user request patterns to achieve significant energy savings in mobile devices. We develop an analytical model for energy consumption of mobile devices in a dynamic data environment. Based on the utility function derived from the analytical model, we propose algorithms for cache replacement and passive prefetching of data objects. Our comprehensive simulation experiments demonstrate that the proposed caching mechanism achieves more than 10% energy saving and near-optimal performance tradeoff between access latency and energy consumption. Huaping Shen received his M.S. and B.S. degrees in computer science from Fudan University, China, in 2001 and 1998, respectively. He is currently a Ph.D. student in the Department of Computer Science and Engineering at the University of Texas at Arlington. His research interests include data management in mobile networks, mobile computing, peer-to-peer networks, and pervasive computing. Mohan Kumar is an Associate Professor in Computer Science and Engineering at the University of Texas at Arlington. His current research interests are in pervasive computing, wireless networks and mobility, active networks, mobile agents, and distributed computing. Recently, he has developed or co-developed algorithms for active-network based routing and multicasting in wireless networks and caching prefetching in mobile distributed computing. He has published over 90 articles in refereed journals and conference proceedings and supervised Masters and doctoral theses in the areas of pervasive computing, caching/prefetching, active networks, wireless networks and mobility, and scheduling in distributed systems. Kumar is on the editorial board of The Computer Journal and he has guest edited special issues of several leading international journals including MONET and WINET issues and the IEEE Transactions on Computers. He is a co-founder of the IEEE International Conference on pervasive computing and communications (PerCom)—served as the program chair for PerCom 2003, and is the vice general chair for PerCom 2004. He has also served in the technical program committees of numerous international conferences/workshops. He is a senior member of the IEEE. Mohan Kumar obtained his PhD (1992) and MTech (1985) degrees from the Indian Institute of Science and the BE (1982) from Bangalore University in India. Prior to joining The University of Texas at Arlington in 2001, he held faculty positions at the Curtin University of Technology, Perth, Australia (1992–2000), The Indian Institute of Science (1986-1992), and Bangalore University (1985–1986). Dr. Sajal K. Das is currently a Professor of Computer Science and Engineering and also the Founding Director of the Center for Research in Wireless Mobility and Networking (CReWMaN) at the University of Texas at Arlington (UTA). Prior to 1999, he was a professor of Computer Science at the University of North Texas (UNT), Denton where he founded the Center for Research in Wireless Computing (CReW) in 1997, and also served as the Director of the Center for Research in Parallel and Distributed Computing (CRPDC) during 1995–97. Dr. Das is a recipient of the UNT Student Association’s Honor Professor Award in 1991 and 1997 for best teaching and scholarly research; UNT’s Developing Scholars Award in 1996 for outstanding research; UTA’s Outstanding Faculty Research Award in Computer Science in 2001 and 2003; and the UTA College of Engineering Research Excellence Award in 2003. An internationally-known computer scientist, he has visited numerous universities, research organizations, government and industry labs worldwide for collaborative research and invited seminar talks. He is also frequently invited as a keynote speaker at international conferences and symposia.Dr. Das’ current research interests include resource and mobility management in wireless networks, mobile and pervasive computing, wireless multimedia and QoS provisioning, sensor networks, mobile internet architectures and protocols, parallel processing, grid computing, performance modeling and simulation. He has published over 250 research papers in these areas, directed numerous industry and government funded projects, and holds four US patents in wireless mobile networks. He received the Best Paper Awards in the 5th Annual ACM International Conference on Mobile Computing and Networking (MobiCom’99), 16th International Conference on Information Networking (ICOIN-16), 3rd ACM International Workshop on Modeling, Analysis and Simulation of Wireless and Mobile Systems (MSWiM 2000), and 11th ACM/IEEE International Workshop on Parallel and Distributed Simulation (PADS’97). Dr. Das serves on the Editorial Boards of IEEE Transactions on Mobile Computing, ACM/Kluwer Wireless Networks, Parallel Processing Letters, Journal of Parallel Algorithms and Applications. He served as General Chair of IEEE PerCom 2004, MASCOTS’02 ACM WoWMoM 2000-02; General Vice Chair of IEEE PerCom 2003, ACM MobiCom-2000 and IEEE HiPC 2000-01; Program Chair of IWDC 2002, WoWMoM 1998-99; TPC Vice Chair of ICPADS 2002; and as TPC member of numerous IEEE and ACM conferences. He is Vice Chair of the IEEE TCPP and TCCC Executive Committees and on the Advisory Boards of several cutting-edge companies.Dr. Sajal K. Das received B.S. degree in 1983 from Calcutta University, M.S. degree in 1984 from Indian Institute of Science, Bangalore, and Ph.D. degree in 1988 from the University of Central Florida, Orlando, all in Computer Science. Zhijun Wang received the M.S degree in Electrical Engineering from Pennsylvania State University, University Park, PA, 2001. He is working toward the Ph.D. degree in Computer Science and Engineering Department at the University of Texas at Arlington. His current research interests include data management in mobile networks and peer-to-peer networks, mobile computing and networking processors.This revised version was published online in August 2005 with a corrected cover date.     

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.     

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.     

On designing incentive-compatible routing and forwarding protocols in wireless ad-hoc networks

In many applications, wireless ad-hoc networks are formed by devices belonging to independent users. Therefore, a challenging problem is how to provide incentives to stimulate cooperation. In this paper, we study ad-hoc games—the routing and packet forwarding games in wireless ad-hoc networks. Unlike previous work which focuses either on routing or on forwarding, this paper investigates both routing and forwarding. We first uncover an impossibility result—there does not exist a protocol such that following the protocol to always forward others' traffic is a dominant action. Then we define a novel solution concept called cooperation-optimal protocols. We present Corsac, a cooperation-optimal protocol which consists of a routing protocol and a forwarding protocol. The routing protocol of Corsac integrates VCG with a novel cryptographic technique to address the challenge in wireless ad-hoc networks that a link’s cost (i.e., its type) is determined by two nodes together. Corsac also applies efficient cryptographic techniques to design a forwarding protocol to enforce the routing decision, such that fulfilling the routing decision is the optimal action of each node in the sense that it brings the maximum utility to the node. We evaluate our protocols using simulations. Our evaluations demonstrate that our protocols provide incentives for nodes to forward packets. Additionally, we discuss the challenging issues in designing incentive-compatible protocols in ad hoc networks. Part of this paper appeared in a conference version [49]. Sheng Zhong was supported in part by NSF grants ANI-0207399 and CNS-0524030. Yang Richard Yang was supported in part by NSF grants ANI-0207399, ANI-0238038, and CNS-0435201. This work was partly done while Sheng Zhong was at Yale University; Yanbin Liu was at University of Texas at Austin. Sheng Zhong is an assistant professor in the State University of New York at Buffalo. He received his PhD (2004) from Yale University and his ME (1999), BS (1996) from Nanjing University, China, all in computer science. His research interests include economic incentives and privacy protection, particularly incentive and privacy problems in mobile computing and data mining. Li Erran Li received his B.E. in Automatic Control from Beijing Polytechnic University in 1993, his M.E. in Pattern Recognition from the Institute of Automation, Chinese Academy of Sciences, in 1996, and his Ph.D. in Computer Science from Cornell University in 2001 where Joseph Y. Halpern was his advisor. He is presently a member of the Networking Research Center in Bell Labs. His research interests are in networking with a focus on wireless networking and mobile computing. He has served as a program committee member for several conferences including ACM MobiCom, ACM MobiHoc, IEEE INFOCOM and IEEE ICNP. He is a guest editor for JSAC special issue on Non-Cooperative Behavior in Networking. He has published over 30 papers. Yanbin Liu received her B.E. degree in Computer Science and Technology from Tsinghua University (1993), Beijing, China, in 1993, and her M.S. degree in Computer Science from the University of Texas at Austin (1998), where is a Ph.D. candidate. Since 2006, he has been with IBM TJ Watson Research Center, Hawthorne, NY. Her research interests are in real-time systems, grid computing, mobile computing, and computer networks. Yang Richard Yang received his B.E. degree in Computer Science and Technology from Tsinghua University, Beijing, China, in 1993, and his M.S. and Ph.D. degrees in Computer Science from the University of Texas at Austin in 1998 and 2001, respectively. Since 2001, he has been with the Department of Computer Science, Yale University, New Haven, CT, where currently he is an Associate Professor. His current research interests are in computer networks, mobile computing, and sensor networks. He leads the Laboratory of Networked Systems (LANS) at Yale University.     

A Fault-Tolerant Scheme for Mobility Management in PCS Networks

One of the most important and challenging issues in the design of personal communication service (PCS) systems is the management of location information. In this paper, we propose a new fault-tolerant location management scheme, which is based on the cellular quorum system. Due to quorum's salient set property, our scheme can tolerate the failures of one or more location server(s) without adding or changing the hardware of the systems in the two-tier networks. Meanwhile, with a region-based approach, our scheme stores/retrieves the MH location information in the location servers of a quorum set of the local region as much as possible to avoid long delays caused by the possible long-distance of VLR and HLR. Thus, it yields better connection establishment and update delay. Ming-Jeng Yang received the M.S. degree in computer science from the Syracuse University, New York, in 1991, and the Ph.D. degree in computer science from National Taiwan Normal University, Taiwan, in 2004. He is an associate professor in the Department of Information Technology, Takming College, Taiwan. His research interests include wireless networks, mobile computing, fault-tolerant computing, and distributed computing. He is a member of the IEEE Computer Society and the ACM. Yao-Ming Yeh received the B.S. degree in computer engineering from National Chiao-Tung University, Taiwan, in 1981, and the M.S. degree in computer science and information engineering from National Taiwan University, Taiwan, in 1983. In August 1991, he received the Ph.D. degree in the Department of Electrical and Computer Engineering, The Pennsylvania State University, Pa., U.S.A. He is a professor in the Department of Information and Computer Education, National Taiwan Normal University, Taiwan. His research interests include fault-tolerant computing, web and XML computing, and distributed computing.     

A Performance Evaluation of a Novel Energy-Aware Data-Centric Routing Algorithm in Wireless Sensor Networks

In this paper, we present a novel Energy-Aware Data-Centric Routing algorithm for wireless sensor networks, which we refer to as EAD. We discuss the algorithm and its implementation, and report on the performance results of several workloads using the network simulator ns-2. EAD represents an efficient energy-aware distributed protocol to build a rooted broadcast tree with many leaves, and facilitate the data-centric routing in wireless micro sensor networks. The idea is to turn off the radios of all leaf nodes and let the non-leaf nodes be in charge of data aggregation and relaying tasks. The main contribution of this protocol is the introduction of a novel approach based on a low cost backbone provisioning within a wireless sensor network in order to turn off the non backbone nodes and save energy without compromising the connectivity of the network, and thereby extending the network lifetime. EAD makes no assumption on the network topology, and it is based on a residual power. We present an extensive simulation experiments to evaluate the performance of our EAD forwarding-to-parent routing scheme over a tree created by a single EAD execution, and compare it with the routing scheme over a regular Ad hoc On-Demand Distance Vector (AODV) Protocol. Last but not least, we evaluate the performance of our proposed EAD algorithm and compare it to the Low-Energy Adaptive Clustering Hierarchy (LEACH) protocol, a cluster-based, energy-aware routing protocol specifically designed for sensor networks. Our results indicate clearly that EAD outperforms AODV and LEACH in energy conservation, throughput, and network lifetime extension.Dr. A. Boukerche was partially supported by NSERC, Canada Research Program, Canada Foundation for Innovation, and Ontario Innovation Funds/Ontario Distinguished Research Award.Azzedine Boukerche is a Full Professor and holds a Canada Research Chair Position at the University of Ottawa. He is also the Founding Director of PARADISE Research Laboratory at Ottawa U. Prior to this, he hold a faculty position at the University of North Texas, USA, and he was working as a Senior Scientist at the Simulation Sciences Division, Metron Corporation located in San Diego. He was also employed as a Faculty at the School of Computer Science McGill University, and taught at Polytechnic of Montreal. He spent a year at the JPL-California Institute of Technology where he contributed to a project centered about the specification and verification of the software used to control interplanetary spacecraft operated by JPL/NASA Laboratory.His current research interests include wireless networks, mobile and pervasive computing, wireless multimedia, QoS service provisioning, wireless ad hoc and sensor networks, distributed systems, distributed computing, large-scale distributed interactive simulation, and performance modeling. Dr. Boukerche has published several research papers in these areas. He was the recipient of the best research paper award at PADS’97, and the recipient of the 3rd National Award for Telecommunication Software 1999 for his work on a distributed security systems on mobile phone operations, and has been nominated for the best paper award at the IEEE/ACM PADS’99, and at ACM MSWiM 2001. Dr. A. Boukerche serves as an Associate Editor and on the editorial board for ACM/Springer Wireless Networks, the Journal of Parallel and Distributed Computing, The Wiley Journal of Wireless Communication and Mobile Computing. He served as a Founding and General Chair of the first Int’l Conference on Quality of Service for Wireless/Wired Heterogeneous Networks (QShine 2004), ACM/IEEE MASCOST 1998, IEEE DS-RT 1999-2000, ACM MSWiM 2000; Program Chair for ACM/IFIPS Europar 2002, IEEE/SCS Annual Simulation Symposium ANNS 2002, ACM WWW’02, IEEE/ACM MASCOTS 2002, IEEE Wireless Local Networks WLN 03-04; IEEE WMAN 04-05, ACM MSWiM 98–99, and TPC member of numerous IEEE and ACM conferences. He served as a Guest Editor for JPDC, and ACM/kluwer Wireless Networks and ACM/Kluwer Mobile Networks Applications, and the Journal of Wireless Communication and Mobile Computing.Dr. Boukerche serves as a Steering Committee Chair for ACM MSWiM, IEEE DS-RT, and ACM PE-WASUN Conferences.Xiuzhen Cheng is an Assistant Professor in the Department of Computer Science at the George Washington University. She received her MS and Ph.D. degrees in Computer Science from University of Minnesota—Twin Cities in 2000 and 2002, respectively. Her current research interests include localization, data aggregation services, and data storage in sensor networks, routing in mobile ad hoc networks, and approximation algorithm design and analysis. She is a member of the ACM and IEEE.Joseph Linus has recently graduated with a MSc Degree from the Department of Computer Sciences, University of North Texas. His current research interests include wireless sensors networks, and mobile ad hoc networks.     

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

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

Analysis and Optimization of the Energy Efficiency in the 802.11 DCF

This paper introduces an analytical model to investigate the energy efficiency of the IEEE 802.11 distributed coordinated function (DCF). This model not only accounts for the number of contending nodes, the contention window, but also the packet size, and the channel condition. Based on this model, we identify the tradeoff in choosing optimum parameters to optimize the energy efficiency of DCF in the error-prone environment. The effects of contention window and packet size on the energy efficiency are examined and compared for both DCF basic scheme and DCF with four-way handshaking. The maximum energy efficiency can be obtained by combining both the optimal packet size and optimal contention window. To validate our analysis, we have done extensive simulations in ns-2, and simulation results seem to match well with the presented analytical results. The Ohio Board of Regents Doctoral Enhancements Funds and the National Science Foundation under Grant CCR 0113361 have supported this work. Xiaodong Wang received his B.S. degree in communication engineering from Beijing Information Technical Institute of China in 1995, and his M.S. degree in electric engineering from Beijing University of Aeronautics and Astronautics of China in 1998. He joined China Telecom in 1998 where he worked on communication protocols for telecommunication. From June 2000 to July 2002, he worked on GSM base station software development at Bell-labs China, Beijing, China. Currently he is a Ph.D. student in Computer Engineering at University of Cincinnati. His research activities include wireless MAC protocols, energy saving for wireless sensor networks. He is a student member of the IEEE. Jun Yin received the BS degree in automatic control from Dalian Railway Institute of China in 1997, and the MS degree in flight control from Beijing University of Aeronautics and Astronautics of China in 2001. Since 2001 she has been a Ph.D. student in the OBR Research Center for Distributed and Mobile Computing at the University of Cincinnati. Her research interests include performance evaluation of 802.11 MAC protocol, wireless ad hoc networks and sensor networks. She is a student member of the IEEE. Dharma P.Agrawal IEEE Fellow, 1987; ACM Fellow, 1998; AAAS Fellow, 2003 Dr. Agrawal is the Ohio Board of Regents Distinguished Professor of Computer Science and Computer Engineering in the department of Electrical and Computer Engineering and Computer Science, University of Cincinnati, OH. He has been a faculty member at Wayne State University, (1977–1982) and North Carolina State University (1982–1998). He has been a consultant to the General Dynamics Land Systems Division, Battelle, Inc., and the U. S. Army. He has held visiting appointment at AIRMICS, Atlanta, GA, and the AT&T Advanced Communications Laboratory, Whippany, NJ. He has published a number of papers in the areas of Parallel System Architecture, Multi computer Networks, Routing Techniques, Parallelism Detection and Scheduling Techniques, Reliability of Real-Time Distributed Systems, Modeling of C-MOS Circuits, and Computer Arithmetic. His recent research interest includes energy efficient routing, information retrieval, and secured communication in ad hoc and sensor networks, effective handoff handling and multicasting in integrated wireless networks, interference analysis in piconets and routing in scatternet, use of smart directional antennas (multibeam) for enhanced QoS, Scheduling of periodic real-time applications and automatic load balancing in heterogeneous workstation environment. He has four approved patents and three patent filings in the area of wireless cellular networks.     

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.     

Update Propagation Algorithms for Supporting Disconnected Write in Mobile Wireless Systems with Data Broadcasting Capability

We develop and analyze algorithms for propagating updates by mobile hosts in wireless client–server environments that support disconnected write operations, with the goal of minimizing the tuning time for update propagation to the server. These algorithms allow a mobile host to update cached data objects while disconnected and propagate the updates to the server upon reconnection for conflict resolutions. We investigate two algorithms applicable to mobile systems in which invalidation reports/data can be broadcast to mobile hosts periodically. We show that there exists an optimal broadcasting period under which the tuning time is minimized for update propagations. We perform a comparative analysis between these two update propagation algorithms that rely on broadcasting data and an algorithm that does not, and identify conditions under which an algorithm should be applied to reduce the total tuning time for update propagation by the mobile user to save the valuable battery power and avoid high communication cost. For real-time applications, we address the tradeoff between tuning time and access time with the goal to select the best update propagation algorithm that can minimize the tuning time while satisfying the imposed real-time deadline constraint. The analysis result is applicable to file/data objects that mobile users may need to modify while on the move. Ing-Ray Chen received the BS degree from the National Taiwan University, Taipei, Taiwan, and the MS and PhD degrees in computer science from the University of Houston. He is currently an associate professor in the Department of Computer Science at Virginia Tech. His research interests include mobile computing, pervasive computing, multimedia, distributed systems, real-time intelligent systems, and reliability and performance analysis. Dr. Chen has served on the program committee of numerous conferences, including as program chair for 29th IEEE Annual International Computer Software and Application Conference in 2005, 14th IEEE International Conference on Tools with Artificial Intelligence in 2002, and 3rd IEEE Symposium on Application-Specific Systems and Software Engineering Technology in 2000. Dr. Chen currently serves as an Associate Editor for IEEE Transactions on Knowledge and Data Engineering, The Computer Journal, and International Journal on Artificial Intelligence Tools. He is a member of the IEEE/CS and ACM. Ngoc Anh Phan received her Bachelor of Science degree from Moscow Technical University of Communication and Computer Science in 1997, and a Master of Science degree in Computer Science from Virginia Polytechnic Institute and State University (Virginia Tech) in 1999. She is currently a Ph.D student at Virginia Tech and a Senior Software Engineer at America Online Inc. Her research interests include wireless communications, data management, sensor networks, fault tolerance, and mobile computing. I-Ling Yen received her BS degree from Tsing-Hua University, Taiwan, and her MS and PhD degrees in Computer Science from the University of Houston. She is currently an Associate Professor of Computer Science at the University of Texas at Dallas. Dr. Yen's research interests are in distributed systems, fault-tolerant computing, self-stabilization algorithms, and security. She has served as program co-chair for the 1997 IEEE High Assurance Systems Engineering Workshop, the 1999 IEEE Symposium on Application-Specific Systems and Software Engineering Technology, and the 1999 Annual IEEE International Conference on Computer Software and Applications Conference. Dr. Yen is a member of the IEEE/CS.