Random Trip Mobility Models
Presenters: Jean-Yves Le Boudec (EPFL) and Milan Vojnovic (Microsoft Research)

Abstract
Mobility models play an important role for wireless and mobile systems as they are used widely for both mathematical and simulation-based evaluations. Even though some of mobility models are rather simple, such as for example well known random waypoint model, they often cause some subtle problems. For example, the annoying initial transience of node mobility state, and the decrease of node numerical speed to zero during a simulation run. Some of these issues were addressed in the literature on a case by case basis, often involving long and complicated computations, which blur understanding the roots of the experienced problems and ways to fix them. It is critical to perform simulations that are free of biases such as initial transience and avoid abnormal cases such as the speed decay to zero in order to produce fair comparative performance of protocols in mobile environments.

In the tutorial, we present random trip models, a broad class of random mobility models and review a large number of random trip model examples, such as for example, random waypoint on convex or non convex areas, restricted random waypoint, inter-city, space graph, boundary reflection and wrap-around models. Our first goal is to explain the trip conditions that define random trip mobility models and guarantee the model stability. The stability is in the sense of existence of time stationary mobility state and convergence of the node mobility state to a unique time-stationary state, from any initial node mobility state. Knowing such conditions is important in order to enable verification of stability of existing and new mobility models and by doing so, avoiding undesirable phenomena such as the aforementioned speed decay to zero. The stability conditions originate from the theory of continuous-time Markov processes on general state spaces; this framework is rather delicate but we explain the stability conditions in an easy way that suffices to apply them.

We further present perfect simulation algorithm that initialises node mobility state in a way that the state remains time-stationary throughout a simulation run - hence, perfect simulation. This is rather useful as it entirely alleviates the annoying initial transience of node mobility state. The algorithm does not necessitate knowing the mean trip duration for all trips, but it suffices to know a bound on the mean trip duration in cases when the mean trip duration is difficult to compute. This is rather relevant in practise as computing the mean trip duration typically involves computing geometric constants that are often hard to compute, while computing close bounds on the mean trip duration is often easy. We describe how to use the implementation of perfect simulation algorithm to use with ns-2 that is freely available for download. This tool has been used by others in performance evaluations of some recent wireless and mobile systems.

We lastly discuss how random trip mobility model accommodates various mobility properties (some of which may be invariants of real-world mobility) such as, for example, recent empirical evidence that the distribution of human inter-contact times are heavy-tailed, long-range dependent models and their implications on simulation averaging, and parameter settings of node mobility to achieve a target time-stationary distribution of node location. We also point to some data resources to use with the model towards realistic mobility simulations.

Audience
Researchers, systems people, and students who want to learn or better understand the state-of-the art mobility models, their stability, stationary regime, convergence properties, and perfect simulation. The attendees will learn the framework that defines random trip mobility models, which would enable them defining new mobility models with guaranteed stability and convergence properties, so as to avoid pitfalls such as for example experienced with random waypoint model. They will also learn how to run perfect simulations of random trip mobility models, which will be supported by demonstration of the software tool designed to use with ns2 simulator. No special background is assumed, but some basic familiarity with applied probability.

Biographies
Jean-Yves Le Boudec is full professor at EPFL, fellow of the IEEE and director of the Institute of Communication Systems. He graduated from Ecole Normale Superieure de Saint-Cloud, Paris, where he obtained the Agregation in Mathematics in 1980 (rank 4) and received his doctorate in 1984 from the University of Rennes, France. From 1984 to 1987 he was with INSA/IRISA, Rennes. In 1987 he joined Bell Northern Research, Ottawa, Canada, as a member of scientific staff in the Network and Product Traffic Design Department. In 1988, he joined the IBM Zurich Research Laboratory where he was manager of the Customer Premises Network Department. In 1994 he joined EPFL as associate professor.

His interests are in the performance and architecture of communication systems. In 1984, he developed analytical models of multiprocessor, multiple bus computers. In 1990 he invented the concept called ”MAC emulation” which later became the ATM forum LAN emulation project, and developed the first ATM control point based on OSPF. He also launched public domain software for the interworking of ATM and TCP/IP under Linux. He proposed in 1998 the first solution to the failure propagation that arises from common infrastructures in the Internet. He contributed to network calculus, a recent set of developments that forms a foundation to many traffic control concepts in the internet, and co-authored a book on this topic. He earned the Infocom 2005 Best Paper award with Milan Vojnovic of Microsoft Research for elucidating the perfect simulation and stationarity of mobility models.

He was on the program committee of many conferences, including Sigcomm, Sigmetrics and Infocom, was managing editor of the journal Performance Evaluation from 1990 to 1994, and is on the editorial board of ACM/IEEE Transactions on Networking.

Milan Vojnovic is a researcher with systems and networking group at Microsoft Research Cambridge, United Kingdom. His research interests include architecture and performance of networking systems. He received his PhD from EPFL, Switzerland, in 2003, and his MSc and BSc from the University of Split, Croatia, in 1998 and 1995, respectively. He received ACM SIGMETRICS 2005 Best Paper Award (with Laurent Massoulie) for a work on performance of file swarming systems, IEEE INFOCOM 2005 Best Paper Award (with Jean-Yves Le Boudec) for a work on stationarity and perfect simulation of random mobility models, and ITC-17 2001 Best Student Paper Award (with Jean-Yves Le Boudec) for a work on TCP-friendliness of equation-based congestion control. In 2005, he has been awarded ERCIM Cor Baayen Award.

He is a co-chair of www.inter-perf.org, a workshop on interdisciplinary performance evaluation of computer and communication systems. He is a guest lecturer at the University of Split, Croatia, teaching a computer networking course to forth-year undergraduate students in computer science and have been giving short lectures at various academic institutions and conferences on diverse topics.

Routing in Delay Tolerant Mobile Ad Hoc Networks: Overview and Challenges
Presenter: Dr. Zhensheng Zhang, San Diego Research Center

Abstract
In mobile ad hoc networks, nodes are constantly in motion and/or operate on limited power. When nodes are in motion, links can be obstructed by intervening objects. When nodes must conserve power, links are shut down. These result in intermittent connectivity. When no path exists between source and destination, network partition occurs. Examples of an intermittently connected network (ICN) are: a). An inter-planet satellite communication network where satellites and ground nodes may only communicate with each other several times a day, b). A sensor network where sensors are not powerful enough to send data to a collecting server or are scheduled to be wake/sleep periodically, c). A military ad hoc network where nodes (e.g. tanks, airplanes, soldiers) may move randomly and are subject to being destroyed. Applications in ICNs must tolerate delays beyond conventional IP forwarding delays and these networks are referred to as delay/disruption tolerant networks (DTN). New protocols specifically for DTNs must be developed as existing protocols designed for the Internet do not work properly. There are several different types of DTNs due to their different characteristics.

Recently there has been much research activity in the emerging area of intermittently connected ad hoc networks and delay/disruption tolerant networks (DTN) (DARPA launched one in 2005). There are different types of DTNs depending on the nature of the network environment. Routing in DTNs is one of the key components in the DTN architecture. Therefore, researchers have proposed different routing protocols for different types of DTNs in the last few years. In this tutorial, we review the state of the art in DTN networks and routing protocols for DTNs. We categorize these routing protocols based on information used. For deterministic time evolving networks, three main approaches are discussed: the tree approach, the space and time approach, and the modified shortest path approach. For stochastic time evolving networks, the following approaches are reviewed: the epidemic or random forwarding approach, predication or history based approach (including per contact Zhang, Routing in DTNs Page 2 of 3 routing based on one hop information only and per contact routing based on average end to end information), the model based routing approach as well as approaches which control the movement of certain special nodes are reviewed. Recent development in erasure coding and network coding applied to DTNs are also discussed.

As a case study, we will discuss how DTN technologies are applied to real DOD networks such as US Marine Corps CONDOR—Command and Control On-the-Move Network Digital Over-the-Horizon Relay. CONDOR is a short term bridging strategy to link existing tactical radio and data networks and to provide an over-the-horizon communications capability to link line-of-sight radio systems that have moved beyond line-of-sight or that precluded by terrain features or other obstacles.

The tutorial also identifies open research issues and intends to motivate new research and development in this area.

Audience
The tutorial is designed for researchers, system engineers, network architects, and protocol implementers from government, academia or industry interested in intermittently connected ad hoc networks and delay tolerance networks. Our intention is that, by reviewing these layeragnostic protocols in details and categorizing them into different classes, efficient algorithms and new improvements can be developed.

Biography
Dr. Zhensheng Zhang received his Ph.D. in electrical engineering from the University of California, Los Angeles in 1989. Dr. Zhang has over fifteen years experience in design and analysis of network architecture, protocols and control algorithms, with very strong backgrounds in performance analysis, modeling and simulation of the communication networks. He is currently with San Diego Research Center (SDRC), Principal Investigator for several DOD projects. Before joining SDRC, he visited Microsoft Research in the summer of 2002 and worked at Sorrento Networks, Department of System Architecture, for 2 years, responsible for designing the next-generation optical metro networks using the GMPLS control framework. Prior to Sorrento Networks he was with Bell Laboratories, Lucent Technologies, focusing on research and development in wireless networks. He has published more than 100 papers in ACM/IEEE Transactions on Networking, IEEE JSAC, IEEE Transactions on Communications, and key ACM/IEEE conferences. Currently, Dr. Zhang is Editor of IEEE Transaction on Wireless Communications. He served the General Chair of Broadband Wireless Networking Symposium, October 2004. He has served as Guest Editor for the IEEE JSAC special issue on Overlay Networks, 2003 and the Journal of Wireless Networks issue on multimedia wireless networks, August 1996. Dr. Zhang served as Member at Large of the IEEE San Diego section 2004 and as Chair of IEEE Communication Society, San Diego section, 2004-2005. His research interests include wireless ad hoc networks, wireless sensor networks. He has given many invited talks and tutorials on wireless ad hoc networks at various conferences.

RFID: Addressing, Event Management and Network Services
Presenters: Sastry Drury (IBM) and George Roussos (Univ. of London)

Abstract
This tutorial will introduce participants to the technologies involved in building large-scale RFID-enabled mobile computing systems. The discussion will be set within the context of specific system case studies where RFID has been the core enabling technology in retail, metropolitan transportation, logistics and e-passport applications. Particular reference will be made to the design and development of RFID middleware and network services. By way of introduction, RFID technology fundamentals will be covered including operating principles, core system components, and performance trade-offs involved in the selection of specific RFID platforms. The tutorial core will be structured around three themes:

1. addressing schemes for RFID tags including the Electronic Product Code and the uID specifications;
2. complex event processing including filtering, aggregation and triggers with particular reference to the EPCglobal Application Level Events (ALE) specification; and,
3. identifier resolution and location of associated information services with particular reference to the Object Naming Service (ONS) and the EPC Information Service (EPC IS).

The last part of the tutorial will discuss the current state-of-the-art in RFID platforms and architectures as they relate to in-network placement of event processors and services. As an example of the diversity of the available approaches, the solutions adopted by IBM’s RFID Device Infrastructure architecture and Cisco’s Application-Oriented Networks will be compared. For developers of RFID systems in particular, appropriate programming abstractions and practical lessons learnt from real-world deployments will be detailed. The tutorial will conclude with a brief look at the implications of RFID for privacy protection and for end-to-end security of networked mobile systems.

Audience
The tutorial is aimed at researchers and industry practitioners with computing or related background who wish to learn what is behind the hype on Radio Frequency Identification, but also about the actual design issues and technical challenges involved. Industrial participants will gain a solid understanding of the different components needed to design and develop a robust network architecture to deploy RFID including mobile and fixed components, and researchers will further benefit from the discussion of open problems and current challenges. The tutorial will also be useful to those who are already involved in some aspect of network RFID, and wish to gain a holistic understanding of the field and how their work influences and interfaces with other system elements.

Biographies
Sastry Duri is a senior software engineer at IBM Thomas J. Watson Research Center in Hawthorne, NY. His research interests include distributed, pervasive computing systems, mobile commerce. He represents IBM at the EPCglobal Filtering and Collection work group. He received Ph.D. from the University of Illinois at Chicago, Illinois, M.S. from the Indian Institute of Technology Chennai, India, and B. Tech from National Institute of Technology, Warangal, India.

George Roussos is a senior lecturer at the School of Computer Science and Information Systems, Birkbeck College, University of London. His current research interests include ubiquitous computing in particular investigating the effects of social activity on system architectures, and exploring mechanisms to support navigation and findability. He holds a B.Sc. in Mathematics from University of Athens, Greece, an M.Sc. in Numerical Analysis and Computing from University of Manchester Institute of Science and Technology, UK, and a Ph.D. from Imperial College London, UK. He is a member of the ACM, ACM SIGMOBILE, the IEEE, the IEEE Communications and the IEEE Computer Society.