Exploiting Mobility for Energy Efficient Data Collection in Wireless Sensor Networks

We analyze an architecture based on mobility to address the problem of energy efficient data collection in a sensor network. Our approach exploits mobile nodes present in the sensor field as forwarding agents. As a mobile node moves in close proximity to sensors, data is transferred to the mobile node for later depositing at the destination. We present an analytical model to understand the key performance metrics such as data transfer, latency to the destination, and power. Parameters for our model include: sensor buffer size, data generation rate, radio characteristics, and mobility patterns of mobile nodes. Through simulation we verify our model and show that our approach can provide substantial savings in energy as compared to the traditional ad-hoc network approach. Sushant Jain is a Ph.D. candidate in the Department of Computer Science and Engineering at the University of Washington. His research interests are in design and analysis of routing algorithms for networking systems. He received a MS in Computer Science from the University of Washington in 2001 and a B.Tech degree in Computer Science from IIT Delhi in 1999. Rahul C. Shah completed the B. Tech (Hons) degree from the Indian Institute of Technology, Kharagpur in 1999 majoring in Electronics and Electrical Communication Engineering. He is currently pursuing his Ph.D. in Electrical Engineering at the University of California, Berkeley. His research interests are in energy-efficient protocol design for wireless sensor/ad hoc networks, design methodology for protocols and next generation cellular networks. Waylon Brunette is a Research Engineer in the Department of Computer Science and Engineering at the University of Washington. His research interests include mobile and ubiquitous computing, wireless sensor networks, and personal area networks. Currently, he is engaged in collaborative work with Intel Research Seattle to develop new uses for embedded devices and RFID technologies in ubiquitous computing. He received a BS in Computer Engineering from the University of Washington in 2002. Gaetano Borriello is a Professor in the Department of Computer Science and Engineering at the University of Washington. His research interests are in embedded and ubiquitous computing, principally new hardware devices that integrate seamlessly into the user’s environment with particular focus on location and identification systems. His principal projects are in creating manageable RFID systems that are sensitive to user privacy concerns and in context-awareness through sensors distributed in the environment as well as carried by users. Sumit Roy received the B. Tech. degree from the Indian Institute of Technology (Kanpur) in 1983, and the M. S. and Ph. D. degrees from the University of California (Santa Barbara), all in Electrical Engineering in 1985 and 1988 respectively, as well as an M. A. in Statistics and Applied Probability in 1988. His previous academic appointments were at the Moore School of Electrical Engineering, University of Pennsylvania, and at the University of Texas, San Antonio. He is presently Prof, of Electrical Engineering, Univ. of Washington where his research interests center around analysis/design of communication systems/networks, with a topical emphasis on next generation mobile/wireless networks. He is currently on academic leave at Intel Wireless Technology Lab working on high speed UWB radios and next generation Wireless LANs. His activities for the IEEE Communications Society includes membership of several technical committees and TPC for conferences, and he serves as an Editor for the IEEE Transactions on Wireless Communications.     

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

Towards Designing a Trusted Routing Solution in Mobile Ad Hoc Networks

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

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

Locating and Bypassing Holes in Sensor Networks

In real sensor network deployments, spatial distributions of sensors are usually far from being uniform. Such networks often contain regions without enough sensor nodes, which we call holes. In this paper, we show that holes are important topological features that need to be studied. In routing, holes are communication voids that cause greedy forwarding to fail. Holes can also be defined to denote regions of interest, such as the “hot spots” created by traffic congestion or sensor power shortage. In this paper, we define holes to be the regions enclosed by a polygonal cycle which contains all the nodes where local minima can appear. We also propose simple and distributed algorithms, the Tent rule and BoundHole, to identify and build routes around holes. We show that the boundaries of holes marked using BoundHole can be used in many applications such as geographic routing, path migration, information storage mechanisms and identification of regions of interest. Qing Fang is currently a Ph.D. student in Department of Electrical Engineering at Stanford University. Her research interests include algorithm, architecture and protocol design for wireless sensor networks and ad hoc communication. She received her MS in Electrical Engineering from University of Texas at Austin in Fall 1995 and worked in the industry as a system software engineer before joining Stanford in 1999. Jie Gao received her Ph.D. degree from department of computer science at Stanford University in 2004 and her B.S. degree from University of Science and Technology of China in 1999. She joined State University of New York, Stony Brook as an assistant professor in Fall 2005. Her research interests are algorithms design and analysis, ad hoc communication and sensor networks and computational geometry. Leonidas J. Guibas heads the Geometric Computation group in the Computer Science Department of Stanford University. He is a member of the Computer Graphics and Artifical Intelligence Laboratories and works on algorithms for sensing, modeling, reasoning, rendering, and acting on the physical world. Professor Guibas’ interests span computational geometry, geometric modeling, computer graphics, computer vision, sensor networks, robotics, and discrete algorithms–-all areas in which he has published and lectured extensively. Leonidas Guibas obtained his Ph.D. from Stanford in 1976, under the supervision of Donald Knuth. His main subsequent employers were Xerox PARC, MIT, and DEC/SRC. He has been at Stanford since 1984 as Professor of Computer Science. At Stanford he has developed new courses in algorithms and data structures, geometric modeling, geometric algorithms, and sensor networks. Professor Guibas is an ACM Fellow.     

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

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

Pre-Reply Probe and Route Request Tail: Approaches for Calculation of Intra-Flow Contention in Multihop Wireless Networks

Several applications have been envisioned for multihop wireless networks that require different qualities of service from the network. In order to support such applications, the network must control the admission of flows. To make an admission decision for a new flow, the expected bandwidth consumption of the flow must be correctly determined. Due to the shared nature of the wireless medium, nodes along a multihop path contend among themselves for access to the medium. This leads to intra-flow contention; contention between packets of the same flow forwarded by different hops along a multihop path, resulting in an increase in the actual bandwidth consumption of the flow to a multiple of its single hop bandwidth requirement. Determining the amount of intra-flow contention is non-trivial since interfering nodes may not be able to communicate directly if they are outside each other's transmission range. In this paper we examine methods to determine the extent of intra-flow contention along multihop paths in both reactive and proactive routing environments. The highlight of the solutions is that carrier-sensing data is used to deduce information about carrier-sensing neighbors, and no high power transmissions are necessary. Analytical and simulation results show that our methods estimate intra-flow contention with low error, while significantly reducing overhead, energy consumption and latency as compared to previous approaches. Kimaya Sanzgiri is a PhD candidate in the Department of Computer Science at the University of California, Santa Barbara. She is working with Prof. Elizabeth Belding-Royer in the Mobility Management and Networking (MOMENT) Laboratory. Kimaya received her B.E. (Hons.) in Computer Science from the Birla Institute of Technology and Science (BITS), Pilani, India in 1999. Her research interests are in the area of wireless networking, specifically mobility, quality of service support and security. See for more details. Ian D. Chakeres is an Ph.D. student in the Department of Electrical and Computer Engineering at the University of California, Santa Barbara. He is working with Prof. Elizabeth M. Belding-Royer in the Mobile Management and Networking (MOMENT) Laboratory. He completed his B.S. and M.S. in Electrical and Computer Engineering at Ohio State University in 1998 and 1999. He is also a co-chair of the IETF MANET working group. Ian's research interests include wireless communication and mobile networking, specifically routing protocols, MAC protocols, cross-layer coordination and quality of services in mobile wireless networks. See for further details. Elizabeth M. Belding-Royer is an Assistant Professor in the Department of Computer Science at the University of California, Santa Barbara. She completed her Ph.D. in Electrical and Computer Engineering at UC Santa Barbara in 2000. Elizabeth's research focuses on mobile networking, specifically routing protocols, multimedia, monitoring, and advanced service support. Elizabeth is the author of numerous papers related to ad hoc networking and has served on many program committees for networking conferences. Elizabeth is the TPC Co-Chair of ACM MobiCom 2005 and IEEE SECON 2005, and is currently on the editorial board for the Elsevier Science Ad hoc Networks Journal. Elizabeth is the recipient of an NSF CAREER award, and a 2002 Technology Review 100 award, awarded to the world's top young investigators. She is a member of the IEEE, IEEE Communications Society, ACM, and ACM SIGMOBILE. See for further details.     

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 Routing Protocol for Hierarchical LEO/MEO Satellite IP Networks

The rapid growth of Internet-based applications pushes broadband satellite networks to carry on IP traffic. In previously proposed connectionless routing schemes in satellite networks, the metrics used to calculate the paths do not reflect the total delay a packet may experience. In this paper, a new Satellite Grouping and Routing Protocol (SGRP) is developed. In each snapshot period, SGRP divides Low Earth Orbit (LEO) satellites into groups according to the footprint area of the Medium Earth Orbit (MEO) satellites. Based on the delay reports sent by LEO satellites, MEO satellite managers compute the minimum-delay paths for their LEO members. Since the signaling traffic is physically separated from the data traffic, link congestion does not affect the responsiveness of delay reporting and routing table calculation. The snapshot and group formation methods as well as fast reacting mechanisms to address link congestion and satellite failures are described in detail. The performance of SGRP is evaluated through simulations and analysis.Eylem Ekici was with the Broadband & Wireless Networking Laboratory, School of Electrical & Computer Engineering, Georgia Institute of Technology when this work was performed. This work is supported by the National Science Foundation under Grant ANI-0087762.Chao Chen received the BE and ME degrees from Deparment of Electronic Engineering, Shanghai Jiao Tong University, Shanghai, China in 1998 and 2001, respectively. She is currently working toward her Ph.D. degree in the School of Electrical and Computer Engineering, Georgia Institute of Technology, Atlanta, GA. She is a graduate research assistant in the Broadband and Wireless Networking Laboratory at Georgia Institute of Technology. Her current research interests include satellite and space networks, as well as wireless ad hoc and sensor networks. E-mail: cchen@ece.gatech.eduEylem Ekici has received his BS and MS degrees in Computer Engineering from Bogazici University, Istanbul, Turkey, in 1997 and 1998, respectively. He received his PhD degree in Electrical and Computer Engineering from the Georgia Institute of Technology, Atlanta, GA, in 2002. Currently, he is an assistant professor in the Department of Electrical and Computer Engineering of the Ohio State University, Columbus, OH. Dr. Ekici’s research interests include wireless sensor networks, space-based networks, and next generation wireless networks, with a focus on modeling, multiaccess control, routing and multicasting protocols, and resource management. E-mail: ekici@ece.osu.edu     

The Sectoral Sweeper Scheme for Wireless Sensor Networks: Adaptive Antenna Array Based Sensor Node Management and Location Estimation

We introduce a novel sensor node management and location estimation method referred as sectoral sweeper (SS) scheme that uses an adaptive antenna array (AAA) at a central node in wireless sensor networks (WSNs). With the SS scheme, the central node can activate or deactivate the nodes in a desired region which is specified by beam direction and beam width of the transmit beam and also by minimum and maximum thresholds (R _min and R _max) for the received signal strength indicator (RSSI) of signals received by the nodes. In order to perform a specified task that is associated with a Task_id, two different beams are transmitted, which are task region beam and routing region beam to switch the nodes into active or routing modes. Since our scheme does not require any additional software or hardware for node management and location estimation in sensor nodes, the deficiencies of tiny sensors are effectively eliminated. The proposed scheme is shown to reduce the number of sensing nodes and the amount of data traffic in the network, thus leading to considerable savings in energy consumption and prolonged sensor lifetime. Ayhan Erdogan graduated from Turkish Naval Academy, Istanbul, in 1992. He received the MSdegree from the Computer Engineering, Naval Sciences and Engineering Institute, Turkish Naval Academy, Istanbul, in 2003. He attended to a one year training on Automatic Data Processing (ADP) Officer in Middle East Technical University, Turkey, in 1996. He worked as a Project Officer for Turkish Armed Forces Integrated Communication Systems Project developed by Turkish General Stuff, from 1996 until 2001. He is currently a PhD student at the Electronics Engineering and Computer Science Department, Sabanci University, Istanbul, Turkey. His current research interests include Wireless Sensor Networks and Security for Ad hoc Networks. Vedat Coskun was born in Istanbul, Turkey, in 1962. He was graduated from Turkish Naval Academy, Istanbul, Turkey, in 1984. He received the M.Sc. degree from the Computer Science Department, Naval Post Graduate School, CA, USA, in 1990 and the Ph.D. degree from the Computer Engineering Department, Yildiz Technical University, Istanbul, in 1998. He managed the wargaming software development group in Turkish Naval Military Wargaming Center for 5 years. Hewas teaching assistant, faculty member and chairman with the Computer Engineering Department, Turkish Naval Academy. He was part-time visiting professor with Gebze Institute of Technology. He is currently an Assistant Professor with the Department of Information Technology, ISIK University, Istanbul, Turkey. His current research interests include algorithm design, wireless sensor and actuator networks, and cryptography Adnan Kavak was born in Usak, Turkey, in 1970. He received the B.S. degree from the Electrical and Electronics Engineering Department, Middle East Technical University, Ankara, Turkey, in 1992. He received the MS and PhD. degrees from the Electrical and Computer Engineering Department, The University of Texas at Austin, TX, USA, in 1996 and 2000, respectively. He was a satellite control engineer with Turksat Satellite Control Center, Ankara, Turkey, from December 1992 to May 1994. He worked as a Senior Research Engineer at Wireless Systems Laboratory, Samsung Telecommunications America in Richardson, TX, USA, from January 2000 to July 2001. He then joined Kocaeli University, Turkey, in August 2001 and worked as an Assistant Professor there until May 2005. Currently, he is the director ofWireless Communications and Information Systems (WINS) Research Center, and an Associate Professor with the Computer Engineering Department, Kocaeli University, Turkey. His current research interests include 3G and next generation wireless networks, software radios, smart antenna systems, resource allocation in 3G networks, and wireless sensor networks.     

Graphical properties of easily localizable sensor networks

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

Location-aware resource management in mobile ad hoc networks

We propose an innovative resource management scheme for TDMA based mobile ad hoc networks. Since communications between some important nodes in the network are more critical, they should be accepted by the network with high priority in terms of network resource usage and quality of service (QoS) support. In this scheme, we design a location-aware bandwidth pre-reservation mechanism, which takes advantage of each mobile node’s geographic location information to pre-reserve bandwidth for such high priority connections and thus greatly reduces potential scheduling conflicts for transmissions. In addition, an end-to-end bandwidth calculation and reservation algorithm is proposed to make use of the pre-reserved bandwidth. In this way, time slot collisions among different connections and in adjacent wireless links along a connection can be reduced so that more high priority connections can be accepted into the network without seriously hurting admissions of other connections. The salient feature of our scheme is the collaboration between the routing and MAC layer that results in the more efficient spatial reuse of limited resources, which demonstrates how cross-layer design leads to better performance in QoS support. Extensive simulations show that our scheme can successfully provide better communication quality to important nodes at a relatively low price. Finally, several design issues and future work are discussed. Xiang Chen received the B.E. and M.E. degrees in electrical engineering from Shanghai Jiao Tong University, Shanghai, China, in 1997 and 2000, respectively. Afterwards, he worked as a MTS (member of technical staff) in Bell Laboratories, Beijing, China. He is currently working toward the Ph.D. degree in the department of Electrical and Computer Engineering at the University of Florida. His research is focused on protocol design and performance evaluation in wireless networks, including cellular networks, wireless LANs, and mobile ad hoc networks. He is a member of Tau Beta Pi and a student member of IEEE. Wei Liu received the BE and ME degrees in electrical engineering from Huazhong University of Science and Technology, Wuhan, China, in 1998 and 2001, respectively. He is currently pursuing the P.hD. degree in the Department of Electrical and Computer Engineering, University of Florida, Gainesville, where he is a research assistant in the Wireless Networks Laboratory (WINET). His research interest includes QoS, secure and power efficient routing, and MAC protocols in mobile ad hoc networks and sensor networks. He is a student member of the IEEE. Hongqiang Zhai received the B.E. and M.E. degrees in electrical engineering from Tsinghua University, Beijing, China, in July 1999 and January 2002 respectively. He worked as a research intern in Bell Labs Research China from June 2001 to December 2001, and in Microsoft Research Asia from January 2002 to July 2002. Currently he is pursuing the Ph.D. degree in the Department of Electrical and Computer Engineering, University of Florida. He is a student member of IEEE. Yuguang Fang received a Ph.D. degree in Systems and Control Engineering from Case Western Reserve University in January 1994, and a Ph.D. degree in Electrical Engineering from Boston University in May 1997. 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. In May 2000, he joined the Department of Electrical and Computer Engineering at University of Florida where he got the early promotion to Associate Professor with tenure in August 2003 and to Full Professor in August 2005. He has published over 180 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 is currently serving as an Editor for many journals including IEEE Transactions on Communications, IEEE Transactions on Wireless Communications, IEEETransactions on Mobile Computing, and ACM Wireless Networks. He is also actively participating in conference organization such as the Program Vice-Chair for IEEE INFOCOM’2005, Program Co-Chair for the Global Internet and Next Generation Networks Symposium in IEEE Globecom’2004 and the Program Vice Chair for 2000 IEEE Wireless Communications and Networking Conference (WCNC’2000).     

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.     

A Location-Aware Routing Protocol for the Bluetooth Scatternet

Bluetooth is a most promising technology for the wireless personal area networks and its specification describes how to build a piconet. Though the construction of scatternet from the piconets is left out in the specification, some of the existing solutions discuss the scatternet formation issues and routing schemes. Routing in a scatternet, that has more number of hops and relay nodes increases the difficulties of scheduling and consumes the bandwidth and power resources and thereby impacts on the performance of the entire network. In this paper, a novel routing protocol (LARP) for the Bluetooth scatternet is proposed, which reduces the hop counts between the source and the destination and reconstructs the routes dynamically using the location information of the Bluetooth devices. Besides, a hybrid location-aware routing protocol (HLARP) is proposed to construct the shortest routes among the devices with or without having the location information and degenerate the routing schemes without having any location information. Experimental results show that our protocols are efficient enough to construct the shortest routing paths and to minimize the transmission delay, bandwidth and power consumption as compared to the other protocols that we have considered. 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, 2004), Journal of Mobile Multimedia (JMM, 2005), 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 WisCom 2005 and EUC 2005, 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 USW'2005, WASN'2005, and the 11th Mobile Computing Workshop. Dr. Chang is a member of the IEEE Computer Society, Communication Society and IEICE society. His current research interests include wireless sensor networks, mobile learning, Bluetooth radio systems, Ad Hoc wireless networks, and mobile computing. Prasan Kumar Sahoo got his Master degree in Mathematics from Utkal University, India. He did his M.Tech. degree in Computer Science from Indian Institute of Technology (IIT), Kharagpur, India and received his Ph.D in Mathematics from Utkal University, India in April, 2002. He joined in the Software Research Center, National Central University, Taiwan and currently working as an Assistant Professor, in the department of Information Management, Vanung University, Taiwan, since 2003. He was the Program Committee Member of MSEAT'2004, MSEAT'2005, WASA'2006, and IEEE AHUC'2006. His research interests include the coverage problems, modeling and performance analysis of wireless sensor network and Bluetooth technology. 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.     

Characteristic Investigation of New Pathological Elements

A characteristic investigation of the new pathological elements (i.e voltage mirror and current mirror) has been presented. Many nullor-mirror equivalences are explored. The circuit cascadability is discussed with nullor and mirror concepts. Also, the conventional inverse network transformation has been extended for applying to the circuits with current mirror output. To demonstrate the use of presented properties, practical examples have been given. The derived circuits have been verified with HSPICE simulation and the simulation results confirm with our theoretical prediction.Hung-Yu Wang was born in Kaohsiung, Taiwan, Republic of China, on January 4, 1969. He received the Ph.D. degree in optical sciences from National Central University, Chung-Li, Taiwan in 2002.Since 1993 he has worked on promoting the prototyping IC implementation of academic researches, and propelling the collaboration of the academia and industries in Chip Implementation Center (CIC), National Science Council of the Republic of China. In 2003 he became a researcher and the deputy director in Division of Chip Implementation Service of CIC. He is currently working on South Region Office of National Chip Implementation Center, National Applied Research Laboratories as a researcher and the department manager. His research interests are in current-mode circuits design, analog IC design and analog IP design.Ching-Ting Lee was born in Taoyuan, Taiwan, R.O.C., on November 1, 1949. He received his B.S. and M.S. in Electrical Engineering Department of the National Cheng-Kung University, Taiwan, in 1972 and 1974, respectively. He received Ph.D. degree in Electrical Engineering Department from the Carnegie-Mellon University, Pittsburgh, PA, in 1982.He worked on Chung Shan Institute of Science and Technology, before he joined the Institute of Optical Sciences, National Central University, Chung-Li, Taiwan, as a Professor in 1990. He works on National Cheng-Kung University as the dean of Electrical Engineering and Computer Science and the professor or the Institute of Microelectronics, Department of Electrical Engineering in 2003. His current research interests include theory, design, and application of guided-wave structures and devices for integrated optics and waveguide lasers. His research activities have also involved in the research concerning semiconductor lasers, photodetectors and high-speed electronic devices, and their associated integration for electrooptical integrated circuits. He received the outstanding Research Professor Fellowship from the National Science Council (NSC), R.O.C. in 2000 and 2002. He also received the Optical Engineering Medal from Optical Engineering Society and Distinguish Electrical Engineering professor award from Chinese Institute of Electrical Engineering Society in 2003.Chun-Yueh Huang was born in Taichung, Taiwan, Republic of China, on March 24, 1967. He received the B.S. degree in industrial education from National Chang Hwa Normal University, Chang Hwa, Taiwan in 1991, M.S. and Ph.D. degrees both in electrical engineering from the National Cheng Kung University, Tainan, Taiwan in 1993 and 1997, respectively. Since 1999 he has been with the Kan Shan University of Technology, where he is currently Associate Professor and Chairman of Department of Electronic Engineering. His biography is included in the 7th Edition (2003–2004) of Who’s Who in Science and Engineering.His current researches include current-mode circuits design, VLSI design, analog IC design and analog IP design.     

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

Decentralized Utility-based Sensor Network Design

Wireless sensor networks consist of energy-constrained sensor nodes operating unattended in highly dynamic environments. In this paper, we advocate a systematic decentralized approach towards the design of such networks based on utility functions. A local utility function is defined for each sensor node in the network. While each sensor node “selfishly” optimizes its own utility, the network as a “whole” converges to a desired global objective. For the purpose of demonstrating our approach, we consider the following two separate case studies for data gathering in sensor networks: (a) construction of a load balanced tree and (b) construction of an energy balanced tree. Our work suggests a significant departure from the existing view of sensor networks as consisting of cooperative nodes, i.e. “selfish”sensor nodes is a useful paradigm for designing efficient distributed algorithms for these networks. Narayanan Sadagopan received the B.S. degree in computer science from the Regional Engineering College, Trichy, India, in 1998, and the M.S. degree in computer science from University of Southern California (USC), Los Angeles, in 2001. He is currently working toward the Ph.D. degree in the Computer Science Department, USC. His research is focused on theoretical aspects of wireless ad hoc and sensor networks. Mitali Singh received the BTech. degree in Computer Science and Engineering from the Indian Institute of Technology, New Delhi, India in 2000, and the M.S. degree in Computer Science from the University of Southern California, Los Angeles, USA. She is currently working towards the Ph.D. degree in Computer Science at the University of Southern California. Her research interests lie in the area of applied theory and networks. Presently, her work is focused on high level modeling and distributed algorithm design for wireless sensor systems. Bhaskar Krishnamachari received the B.E.E.E. degree from The Cooper Union for the Advancement of Science and Art, New York, in 1998, and the M.S.E.E. and Ph.D. degrees in electrical engineering from Cornell University, Ithaca, NY, in 1999 and 2002, respectively. He is now an Assistant Professor in the Department of Electrical Engineering, University of Southern California, Los Angeles, where he also holds a joint appointment in the Department of Computer Science. His current research is focused on the discovery of fundamental principles and the analysis and design of protocols for next-generation wireless sensor networks.     

On the Use of Multiple Hops in Next Generation Wireless Systems

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

Concurrent Error Detection in a Polynomial Basis Multiplier over GF(2 m )

Eliminating cryptographic computation errors is vital for preventing attacks. A simple approach is to verify the correctness of the cipher before outputting it. The multiplication is the most significant arithmetic operation among the cryptographic computations. Hence, a multiplier with concurrent error detection ability is urgently necessary to avert attacks. Employing the re-computing shifted operand concept, this study presents a semi-systolic array polynomial basis multiplier with concurrent error detection with minimal area overhead. Moreover, the proposed multiplier requires only two extra clock cycles while traditional multipliers using XOR trees consume at least extra XOR gate delays in GF(2^m) fields. Chiou-Yng Lee received the Bachelor’s degree (1986) in medical engineering and the M.S. degree in electronic engineering (1992), both from the Chung Yuan university, Taiwan, and the Ph.D. degree in electrical engineering from Chang Gung University, Taiwan, in 2001. From 1988 to now, he was a research associate with Chunghwa Telecommunication Laboratory in Taiwan. He joined the department of project planning. He taught those related field courses at Ching-Yun Technology University. He is currently as an assistant professor of Department of Computer Information and Network Engineering in Lunghwa University of Science and Technology. His research interests include computations in finite fields, error-control coding, signal processing, and digital transmission system. Besides, he is a member of the IEEE and the IEEE Computer society. He is also an honor member of Phi Tao Phi in 2001. Che Wun Chiou received his B.S. degree in Electronic Engineering from Chung Yuan Christian University in 1982, the M.S. degree and the Ph.D. degree in Electrical Engineering from National Cheng Kung University in 1984 and 1989, respectively. From 1990 to 2000, he was with the Chung Shan Institute of Science and Technology in Taiwan. He joined the Department of Electronic Engineering and the Department of Computer Science and Information Engineering, Ching Yun University in 2000 and 2005, respectively. He is currently as Dean of Division of Continuing Education in Ching Yun University. His current research interests include fault-tolerant computing, computer arithmetic, parallel processing, and cryptography. Jim-Min Lin was born on March 5, 1963 in Taipei, Taiwan. He received the B.S. degree in Engineering Science and the M.S. and the Ph.D. degrees in Electrical Engineering, all from National Cheng Kung University, Tainan, Taiwan, in 1985, 1987, and 1992, respectively. Since February 1993, he has been an Associate Professor at the Department of Information Engineering and Computer Science, Feng Chia University, Taichung City, Taiwan. He is currently as Professor at the Department of Information Engineering and Computer Science, Feng Chia University. His research interests include Operating Systems, Software Integration/Reuse, Embedded Systems, Software Agent Technology, and Testable Design.     

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.