首页 | 官方网站   微博 | 高级检索  
相似文献
 共查询到10条相似文献,搜索用时 125 毫秒
1.
Parametric Probabilistic Routing in Sensor Networks   总被引:1,自引:0,他引:1  
Motivated by realistic sensor network scenarios that have mis-in-formed nodes and variable network topologies, we propose an approach to routing that combines the best features of limited-flooding and information-sensitive path-finding protocols into a reliable, low-power method that can make delivery guarantees independent of parameter values or information noise levels. We introduce Parametric Probabilistic Sensor Network Routing Protocols, a family of light-weight and robust multi-path routing protocols for sensor networks in which an intermediate sensor decides to forward a message with a probability that depends on various parameters, such as the distance of the sensor to the destination, the distance of the source sensor to the destination, or the number of hops a packet has already traveled. We propose two protocol variants of this family and compare the new methods to other probabilistic and deterministic protocols, namely constant-probability gossiping, uncontrolled flooding, random wandering, shortest path routing (and a variation), and a load-spreading shortest-path protocol inspired by (Servetto and Barrenechea, 2002). We consider sensor networks where a sensor’s knowledge of the local or global information is uncertain (parametrically noised) due to sensor mobility, and investigate the trade-off between robustness of the protocol as measured by quality of service (in particular, successful delivery rate and delivery lag) and use of resources (total network load). Our results for networks with randomly placed nodes and realistic urban networks with varying density show that the multi-path protocols are less sensitive to misinformation, and suggest that in the presence of noisy data, a limited flooding strategy will actually perform better and use fewer resources than an attempted single-path routing strategy, with the Parametric Probabilistic Sensor Network Routing Protocols outperforming other protocols. Our results also suggest that protocols using network information perform better than protocols that do not, even in the presence of strong noise. Christopher L. Barrett is leader of the Basic and Applied Simulation Science Group of the Computing and Computational Sciences Division at Los Alamos National Laboratory. His Group is a simulation science and technology (S&T) invention organization of 30 scientists devoted to providing large-scale, high performance methods for systems analysis and simulation-based assisted reasoning. His Group engages in fundamental mathematical, algorithmic, and complex systems analysis research. Current applied research is focused on interdependent simulation and analysis tools for complex, socio-technical systems like transportation, communications, public health and other critical infrastructure areas. His scientific experience is in simulation, scientific computation, algorithm theory and development, system science and control, engineering science, bio-systems analysis, decision science, cognitive human factors, testing and training. His applied science and engineering achievements include, for example, development of large-scale, high performance simulation systems (e.g., Transportation Analysis Simulation System, TRANSIMS) and development of a distributed computing approach for detailed simulation-based study of mobile, packet switched digital communications systems (Self Organizing Stochastic Rebroadcast Relay, SORSRER). He has a M.S. and Ph.D. in Bio-information Systems from California Institute of Technology. He is a decorated Navy veteran having served in both the submarine service and as a pilot. He has been awarded three Distinguished Service Awards from Los Alamos National Laboratory, one from the Alliance for Transportation Research, one from the Royal Institute of Technology, Stockholm, and one from Artificial Life and Robotics, Oita University, Japan. Stephan J. Eidenbenz is a technical staff member in the Basic and Applied Simulation Science group (CCS-5) at Los Alamos National Laboratory (LANL). He received an M.Sc. in Computer Science from the Swiss Federal Institute of Technology (ETH) in Zurich in 1997 and a Ph.D. in Computer Science from ETH in 2000; he also obtained a Bachelor’s degree in business administration from GSBA in Zurich in 1999. Stephan has worked for McKinsey & Co. in Switzerland, where he received training in business administration and microeconomics. He has held a postdoctoral position at ETH and he has been a postdoctoral fellow at LANL. Stephan’s more than 30 publications cover a wide range of subjects such as approximability and inapproximability properties of visibility problems in polygons and terrains, error modeling in sequencing problems for computation biology, and designing communication protocols robust against selfish behavior. His current research interests include selfish networking, algorithmic game theory, network modeling and simulation, network design, and network optimization. Lukas Kroc is a student of M.Sc. program in Computer Science at Charles University in Prague. In 2003, he was a Graduate Research Assistant at the Basic and Applied Simulation Science group (CCS-5) at Los Alamos National Laboratory. His research interests include simulation, wireless networking and artificial intelligence. Madhav V. Marathe is a Team Leader for Mathematics and Computer Science in the Basic and Applied Simulation Science group, Computer and Computational Sciences (CCS-5) at the Los Alamos National Laboratory. He obtained his B.Tech in 1989 in Computer Science and Engg. from IIT Madras, India and his Ph.D. in 1994 in Computer Science, from University at Albany. His team focuses on developing mathematical and computational tools for design and analysis of large scale simulations of socio-technical and critical infrastructure systems. His research interests are in modeling and simulations of large socio-technical systems, design and analysis of algorithms, computational complexity theory, theory of parallel, distributed and mobile computing and communication systems. He has published over 100 research articles in peer reviewed journals and conferences. He is an adjunct faculty in the Computer Science Department at the University of New Mexico. James P. Smith is a technical staff member in the Basic and Applied Simulation Science Group of the Computing and Computational Sciences Division at Los Alamos National Laboratory. His principal interest is in high performance computing applied to modeling, simulation and analysis of socio-technical systems. His current research applies to national infrastructure, especially telecommunication/computing, public health, and transportation. He has scientific experience in high performance computing and parallel processing applied to large-scale microscopic simulations, including original software design and debugging of very large, evolving systems of inter-operable computational systems, and efficient analysis and synthesis of massive data produced by multi-scale complex environments. Before attending graduate school he worked for a short time in nuclear theory, and had several publications in experimental biophysics from the Pennsylvania Muscle Institute and Bockus Research Institute. During graduate school he took a one year hiatus to start a company to work in analytic finance, and then spent time doing theoretical space physics at LANL. His graduate work eventually included theoretical and experimental fusion research, but concentrated on computational space plasma physics. He has publications in biophysics, analytic finance, education, space plasma physics and computer science, and is a co-inventor on the TRANSIMS patent. He has a Ph.D. in Theoretical Plasma Physics from the University of Texas at Austin.This revised version was published online in August 2005 with a corrected cover date.  相似文献   

2.
Locating and Bypassing Holes in Sensor Networks   总被引:1,自引:0,他引:1  
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.  相似文献   

3.
Decentralized Utility-based Sensor Network Design   总被引:1,自引:0,他引:1  
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.  相似文献   

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

5.
Topology-transparent scheduling is an attractive medium access control technique for mobile ad hoc networks (MANETs) and wireless sensor networks (WSNs). The transmission schedule for each node is fixed and guarantees a bounded delay independent of which nodes are its neighbours, as long as the active neighbourhood is not too dense. Most of the existing work on topology-transparent scheduling assumes that the nodes are synchronized on frame boundaries. Synchronization is a challenging problem in MANETs and in WSNs. Hence, we study the relationships among topology-transparent schedules, expected delay, and maximum delay, for successively weaker models of synchronization: frame-synchronized, slot-synchronized, and asynchronous transmission. For each synchronization model, we give constructive proofs of existence of topology-transparent schedules, and bound the least maximum delay. Perhaps surprisingly, the construction for the asynchronous model is a simple variant of the slot synchronized model. While it is foreseen that the maximum delay increases as the synchronization model is weakened, the bound is too pessimistic. The results on expected delay show that topology-transparent schedules are very robust to node density higher than the construction is designed to support, allowing the nodes to cope well with mobility, and irregularities of their deployment. Wensong Chu received his M.S. in Applied Mathematics from Shanghai Jiao Tong University, China, in 1993; received his M.S. in Computer Networks (Electrical Engineering) from the University of Southern California in 2000; received his Ph.D. in Mathematics from the University of Southern California in 2002. He was with the Department of Computer Science and Engineering at Arizona State University as a post-doctoral fellow from 2002 to 2003. Currently he is doing research at the CMS Bondedge in California. His research interests include sequence designs for communications, combinatorial coding methods, mobile ad hoc networks and sensor networks, financial engineering and combinatorial design theory. Charles J. Colbourn was born in Toronto, Canada in 1953. He completed his B.Sc. degree at the University of Toronto in 1976, M.Math. at the University of Waterloo in 1978, and Ph.D. at the University of Toronto in 1980, all in computer science. He has held faculty positions at the University of Saskatchewan, the University of Waterloo, and the University of Vermont, and is now Professor of Computer Science and Engineering at Arizona State University. He is co-editor of the CRC Handbook of Combinatorial Designs and author of Triple Systems and The Combinatorics of Network Reliability, both from Oxford University Press. He is editor-in-chief of the Journal of Combinatorial Designs. His research concerns applications of combinatorial designs in networking, computing, and communications. Violet R. Syrotiuk earned the Ph.D. degree in Computer Science from the University of Waterloo (Canada) in 1992. She joined Arizona State University in 2002 and is currently an Assistant Professor of Computer Science and Engineering. Dr. Syrotiuk’s research is currently supported by three grants from the National Science Foundation, and contracts from Los Alamos National Laboratory, and the Defence Science and Technology Organisation in Australia. She serves on the Editorial Board of Computer Networks, and on the Technical Program Committee of several major conferences including MobiCom and Infocom. Her research interests include mobile ad hoc and sensor networks, in particular MAC protocols with an emphasis on adaptation, topology-transparency, and energy efficiency, dynamic spectrum utilization, mobile network models, and protocol interaction and cross-layer design. She is a member of the ACM and the IEEE.  相似文献   

6.
We study the influence of transmission costs on the behavior of selfish nodes in wireless local area networks. Intuitively, it seems that transmission costs should have a stabilizing effect as (rational) nodes will defer packet transmissions when congestion develops and the cost for (successfully) transmitting a packet becomes high. In this paper we investigate whether this intuition is true. We use the slotted Aloha to model the communication channel where we capture the interaction among nodes as a non-cooperative game. For this game, we study the existence and properties of a (symmetric) Nash equilibrium. We show that the existence of a transmission cost is not always sufficient to guarantee stability. In particular, a stable equilibrium strategy will not exist if the transmission cost is too small. We then propose and analyze a price-based mechanism to guarantee stability and to optimize system performance in terms of throughput and delay. Peter Marbach was born in Lucerne, Switzerland. He received the Eidg. Dipl. El.-Ing. (1993) from the ETH Zurich, Switzerland, the M.S. (1994) in electrical engineering from the Columbia University, NY, U.S.A, and the Ph.D. (1998) in electrical engineering from the Massachusetts Institute of Technology, Cambridge, Massachusetts, U.S.A. He was appointed as assistant professor in 2000, and associate professor in 2005, at the Department of Computer Science of the University of Toronto. He has also been a Visiting Professor at the EPFL, Switzerland, a Visiting Researcher at Microsoft Research Cambridge, UK, a Post-Doctoral Research Fellow at the Center for Communication Systems Research, University of Cambridge, UK, and a Visiting Scientist at the Siemens Corporate Research Center in Munich. Peter Marbach has received the IEEE INFOCOM 2002 Best Paper Award for his paper “Priority Service and Max-Min Fairness”. He is on the editorial board of the IEEE/ACM Transactions of Networking. His research interests are in the fields of communication networks, in particular in wireless networks, peer-to-peer networks, and content-delivery networks.  相似文献   

7.
Context-aware platform for mobile data management   总被引:1,自引:0,他引:1  
Interaction design is a major issue for mobile information systems in terms of not only the choice of input/output channels and presentation of information, but also the application of context-awareness. To support experimentation with these factors, we have developed platforms to support the rapid prototyping of multi-channel, multi-modal, context-aware applications. The Java-based platform presented here is based on an integration of a cross-media link server and an object-oriented framework for advanced content publishing, along with a Client Controller and Context Engine. We also describe how this platform was used to develop a mobile tourist information system for an international arts festival where interaction was based on a combination of interactive paper and speech output. Moira C. Norrie is a Professor at ETH Zurich where she is head of the Institute for Information Systems and leads the Global Information Systems research group. Her research interests include object-oriented models and systems for data management, web engineering, mobile and personal information systems and interactive paper as a medium for integrating printed and digital information. Beat Signer is a Post-Doctoral researcher in the Global Information Systems research group at ETH Zurich. He received a Ph.D. from ETH Zurich in 2005 for his work investigating fundamental concepts for interactive paper and cross-media information management. His research interests include interactive paper, cross-media information management, object-oriented technologies and software engineering. Michael Grossniklaus is a research assistant in the Global Information Systems research group at ETH Zurich. He received a Diploma (M.Sc.) in Computer Science from ETH Zurich in 2001 and is currently completing his Ph.D. His main research interest is empowering information systems for context-aware data management and delivery in the domain of web engineering and mobile computing. Rudi Belotti was a research assistant in the Global Information Systems research group at ETH Zurich from 2004–2006. He received a Diploma (M.Sc.) in Computer Science from ETH Zurich in 2004. In his research, he developed a general model and engine for the management of context information in mobile information systems. He is currently working for an e-business services company in Ticino, Switzerland. Corsin Decurtins is a research assistant in the Global Information Systems research group at ETH Zurich. He received a Diploma (M.Sc.) in Computer Science from ETH Zurich in 2002. His research focusses on model-based approaches and infrastructure for ubiquitous and mobile information environments. In addition to his Ph.D. Corsin also works part-time as a senior software engineer at the software company Netcetera. Nadir Weibel is a research assistant in the Global Information Systems research group at ETH Zurich. He received a Diploma (M.Sc.) in Computer Science from ETH Zurich in 2003 and is currently working on his Ph.D. His research is in the area of interactive paper, particularly on the authoring and publishing infrastructure for interactive documents as well as issues of human computer interaction and mobile environments.  相似文献   

8.
Controlled sink mobility for prolonging wireless sensor networks lifetime   总被引:3,自引:0,他引:3  
This paper demonstrates the advantages of using controlled mobility in wireless sensor networks (WSNs) for increasing their lifetime, i.e., the period of time the network is able to provide its intended functionalities. More specifically, for WSNs that comprise a large number of statically placed sensor nodes transmitting data to a collection point (the sink), we show that by controlling the sink movements we can obtain remarkable lifetime improvements. In order to determine sink movements, we first define a Mixed Integer Linear Programming (MILP) analytical model whose solution determines those sink routes that maximize network lifetime. Our contribution expands further by defining the first heuristics for controlled sink movements that are fully distributed and localized. Our Greedy Maximum Residual Energy (GMRE) heuristic moves the sink from its current location to a new site as if drawn toward the area where nodes have the highest residual energy. We also introduce a simple distributed mobility scheme (Random Movement or RM) according to which the sink moves uncontrolled and randomly throughout the network. The different mobility schemes are compared through extensive ns2-based simulations in networks with different nodes deployment, data routing protocols, and constraints on the sink movements. In all considered scenarios, we observe that moving the sink always increases network lifetime. In particular, our experiments show that controlling the mobility of the sink leads to remarkable improvements, which are as high as sixfold compared to having the sink statically (and optimally) placed, and as high as twofold compared to uncontrolled mobility. Stefano Basagni holds a Ph.D. in electrical engineering from the University of Texas at Dallas (December 2001) and a Ph.D. in computer science from the University of Milano, Italy (May 1998). He received his B.Sc. degree in computer science from the University of Pisa, Italy, in 1991. Since Winter 2002 he is on faculty at the Department of Electrical and Computer Engineering at Northeastern University, in Boston, MA. From August 2000 to January 2002 he was professor of computer science at the Department of Computer Science of the Erik Jonsson School of Engineering and Computer Science, The University of Texas at Dallas. Dr. Basagni’s current research interests concern research and implementation aspects of mobile networks and wireless communications systems, Bluetooth and sensor networking, definition and performance evaluation of network protocols and theoretical and practical aspects of distributed algorithms. Dr. Basagni has published over four dozens of referred technical papers and book chapters. He is also co-editor of two books. Dr. Basagni served as a guest editor of the special issue of the Journal on Special Topics in Mobile Networking and Applications (MONET) on Multipoint Communication in Wireless Mobile Networks, of the special issue on mobile ad hoc networks of the Wiley’s Interscience’s Wireless Communications & Mobile Networks journal, and of the Elsevier’s journal Algorithmica on algorithmic aspects of mobile computing and communications. Dr. Basagni serves as a member of the editorial board and of the technical program committee of ACM and IEEE journals and international conferences. He is a senior member of the ACM (including the ACM SIGMOBILE), senior member of the IEEE (Computer and Communication societies), and member of ASEE (American Society for Engineering Education). Alessio Carosi received the M.S. degree “summa cum laude” in Computer Science in 2004 from Rome University “La Sapienza.” He is currently a Ph.D. candidate in Computer Science at Rome University “La Sapienza.” His research interests include protocols for ad hoc and sensor networks, underwater systems and delay tolerant networking. Emanuel Melachrinoudis received the Ph.D. degree in industrial engineering and operations research from the University of Massachusetts, Amherst, MA. He is currently the Director of Industrial Engineering and Associate Chairman of the Department of Mechanical and Industrial Engineering at Northeastern University, Boston, MA. His research interests are in the areas of network optimization and multiple criteria optimization with applications to telecommunication networks, distribution networks, location and routing. He is a member of the Editorial Board of the International Journal of Operational Research. He has published in journals such as Management Science, Transportation Science, Networks, European Journal of Operational Research, Naval Research Logistics and IIE Transactions. Chiara Petrioli received the Laurea degree “summa cum laude” in computer science in 1993, and the Ph.D. degree in computer engineering in 1998, both from Rome University “La Sapienza,” Italy. She is currently Associate Professor with the Computer Science Department at Rome University “La Sapienza.” Her current work focuses on ad hoc and sensor networks, Delay Tolerant Networks, Personal Area Networks, Energy-conserving protocols, QoS in IP networks and Content Delivery Networks where she contributed around sixty papers published in prominent international journals and conferences. Prior to Rome University she was research associate at Politecnico di Milano and was working with the Italian Space agency (ASI) and Alenia Spazio. Dr. Petrioli was guest editor of the special issue on “Energy-conserving protocols in wireless Networks” of the ACM/Kluwer Journal on Special Topics in Mobile Networking and Applications (ACM MONET) and is associate editor of IEEE Transactions on Vehicular Technology, the ACM/Kluwer Wireless Networks journal, the Wiley InterScience Wireless Communications & Mobile Computing journal and the Elsevier Ad Hoc Networks journal. She has served in the organizing committee and technical program committee of several leading conferences in the area of networking and mobile computing including ACM Mobicom, ACM Mobihoc, IEEE ICC,IEEE Globecom. She is member of the steering committee of ACM Sensys and of the international conference on Mobile and Ubiquitous Systems: Networking and Services (Mobiquitous) and serves as member of the ACM SIGMOBILE executive committee. Dr. Petrioli was a Fulbright scholar. She is a senior member of IEEE and a member of ACM. Z. Maria Wang received her Bachelor degree in Electrical Engineering with the highest honor from Beijing Institute of Light Industry in China, her M.S. degree in Industrial Engineering/Operations Research from Dalhousie University, Canada and her Ph.D. in Industrial Engineering/Operations Research from Northeastern University, Boston. She served as a R&D Analyst for General Dynamics. Currently MS. Wang serves as an Optimization Analyst with Nomis Solutions, Inc.  相似文献   

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

10.
This paper presents DARC (Directional Adaptive Range Control), a range control mechanism using directional antennas to be implemented across multiple layers. DARC uses directional reception for range control rather than directional transmission in order to achieve both range extension and high spatial reuse. It adaptively controls the communication range by estimating dynamically changing local network density based on the transmission activities around each network node. The experimental results using simulation with detailed physical layer, IEEE 802.11 DCF MAC, and AODV protocol models have shown the successful adaptation of communication range with DARC for varied network densities and traffic loads. DARC improves the packet delivery ratio by a factor of 9 at the maximum for sparse networks while it maintains the increased network capacity for dense networks. Further, as each node adaptively changes the communication range, the network delivers up to 20% more packets with DARC compared to any fixed range configurations.Mineo Takai is a Principal Development Engineer in the Computer Science Department at University of California, Los Angeles. He received his B.S., M.S. and Ph.D. degrees, all in electrical engineering, from Waseda University, Tokyo, Japan, in 1992, 1994 and 1997 respectively.Dr. Takai’s research interests include parallel and distributed computing, mobile computing and networking, and modeling and simulation of networked systems. He is a member of the ACM, the IEEE and the IEICE.Junlan Zhou received her B.S in Computer Science from Huazhong University of Science and Technology in 1998, her M.Eng in Computer Engineering from Nanyang Technological University in 2001 and her M.S in Computer Science from University of California, Los Angeles in 2003. She is currently a Ph.D candidate in the Computer Science Department at University of California, Los Angeles. Her research interests include modeling and simulation of wireless networks, protocol design and analysis of wireless networks, and broad areas of distributed computing.Rajive Bagrodia is a Professor of Computer Science at UCLA. He obtained a Bachelor of Technology in electrical engineering from the Indian Institute of Technology, Bombay and a Ph.D. in Computer Science from the University of Texas at Austin. Professor Bagrodia’s research interests include~wireless networks, performance modeling and~simulation, and nomadic computing. He has published over a hundred research papers on the preceding topics. The research has been funded by a variety of government and industrial sponsors including the National Science Foundation, Office of Naval Research, and the Defense Advanced Research Projects Agency. He is an associate editor of the ACM Transactions on Modeling and Computer Systems (TOMACS).  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司    京ICP备09084417号-23

京公网安备 11010802026262号