Encyclopedia on Ad Hoc and Ubiquitous Computing

The following sections are included:

• Preface

• Contents

Emerging advanced wireless ad hoc networks make it possible for network resources to be utilized anywhere and anytime. However, compared with traditional infrastructure-based networks, wireless ad hoc networks are relatively unstable and unreliable due to the underlying wireless medium and infrastructure-less nature. Existing techniques compensate for the instability of wireless links by employing either packet retransmissions, network coding, opportunistic routing, thick (or multiple) paths, or route fixes (using alternative routes). This chapter seeks to compare these techniques in terms of energy cost, the increment of reliability, and various other metrics.

In the context of mobile and ubiquitous systems there is an increasing number of applications where data has to be transmitted, not to a single node or person, but to dynamic groups of nodes or people. This call for efficient multicast routing protocols capable of efficiently use the available bandwidth as well as the usually restricted hardware resources such memory and power. Moreover, given the current and expected sizes of this type of networks, multicast protocols have to be designed to scale up to hundreds of nodes. Here, we describe Hydra, the first multicast routing protocol for MANETs that establishes a multicast routing structure approximating the set of source-rooted shortest-path trees from multicast sources to receivers, without requiring the dissemination of control packets from each source of a multicast group. Hydra accomplishes this by (a) dynamically electing a core for the mesh of a multicast group among the sources of the group, so that at most one control packet is disseminated in the network to announce the existence of the group and (b) aggregating multicast routing state in the nodes participating in multicast meshes, so that redundant control packets are not disseminated towards the receivers of a group. We also present an improved version of PUMA which is a receiver-initiated multicast protocol that for each multicast group periodically floods a single control packet which is used to elect a core for the group and to build and maintain the multicast mesh. We present simulations results for WiFi and TDMA MAC protocols illustrating that Hydra and PUMA attain comparable or higher delivery ratios than ODMRP, but with considerably lower end-to-end delays and, in the case of Hydra, far less data overhead.

Wireless ad hoc networks evolved as a wireless extension of the Internet which is a packet switched data network characterized by TCP/IP suite of protocols for packet routing and transport. It was generally believed that TCP/IP will seamlessly extend the reach of Internet to mobile devices. IP which is at the heart of the proliferation and popularity of wired portion of the Internet was found to be not suitable for wireless environments without significant modifications, as a result considerable research efforts were expended in developing several new routing protocols since the beginning of development of PRNET³⁰ and that trend still continuing with several new routing proposals presented even today. Similarly, the TCP protocol which provides the reliable end-to-end delivery of data even on unreliable wired networks has been found to have several major shortcomings while transmitting data streams on the wireless part of the network due to significant differences at the physical layer in wired and wireless networks. In this book chapter we provide the basics of TCP protocol, discuss several proposals which make it suitable for wireless environments and then present the recent efforts in providing admission control over ad hoc networks.

This chapter is divided into four major sections, namely (i) TCP and congestion control for the Internet. (ii) congestion control for ad hoc wireless networks and TCP based solutions. (iii) admission control for ad hoc networks. (iv) conclusions and further readings.

This work is partly based on the recent survey papers^{22, 35} that have appeared in the literature on the topics of congestion control in ad hoc networks with significant enhancements to make the chapter more readable.

Currently, the IEEE 802.11 standard and its distributed coordination function (DCF) access method have gained global acceptance and popularity both in wireless LANs and wireless multi-hop ad hoc environment. It has been shown that the DCF access method does not make efficient use of the shared channel due to its inherent conservative approach in assessing the level of interference. To date, various mechanisms have been proposed to improve the capacity of IEEE 802.11- based multi-hop wireless networks. These mechanisms can be broadly classified as temporal and spatial approaches depending on their focus of optimization on the channel bandwidth. The temporal approaches attempt to better utilize the channel along the time dimension by optimizing or improving the exponential bakeoff algorithm. On the other hand, the spatial approaches try to find more chances of spatial reuse without significantly increasing the chance of collisions. These mechanisms include the tuning of the carrier sensing threshold, the data rate adaptation, the transmission power control, and the use of directional antennas. This chapter is aimed specifically at providing a comprehensive survey on schemes that deploy the use of directional antenna and the schemes that consider coupling of directional antenna with power control.

Recently, it was realized that Vehicular Ad hoc Networks can support multimedia applications, including peer-to-peer content provisioning. Not surprisingly, a number of peer-to-peer systems for VANET have been recently proposed in the literature. Many of these systems are relying on preinstalled roadside infrastructures and/or using some of the existing techniques like network coding and gossip protocol. In this chapter, we are cover some of the most noticeable peer to peer systems developed for VANETs showing motivation, overview and shortcomings of each. We also provide a discussion and comparison between these systems showing a possible future work.

Ad hoc networks involving vehicles on roads and highways are of interest because of the potential for supporting a wide range of services and applications, including safety, business, and infotainment. Technology and standards for Dedicated Short Range Communications (DSRC) are presently under development for frequencies near 5.9GHz in the United States, and near 5.8GHz in Europe and Japan. To best design equipment and protocols for these applications, the nature of the vehicle-to-vehicle channel in these bands must be understood. This article presents a survey of recent research into both narrowband and wideband channel characteristics, as well as the performance of data transmissions using orthogonal frequency division multiplexing (OFDM). Specific emphasis is placed on investigating the detailed behavior of the channel through on-road measurements in suburban, rural, and highway driving in and near Pittsburgh, PA. The influence of driver behavior on the channel properties is discussed, and this influence is illustrated with the use of the effective speed-separation diagram. Potential implications for vehicle-to-vehicle network implementation and performance are also discussed.

As the networking architecture evolves toward low-cost high-utility services, the development cost-effective techniques for reliable and efficient operations of the network with inherently increased complexity is require. This chapter provides the reader (specifically for engineering students) with a holistic view on resource management in the cellular relay network, ranging from system modeling, optimization problem formulation and solution. It deals with very popular solution methods for resource allocation problems and also deals with two case examples commonly arising in cellular relay networks: fair scheduling and energy efficient scheduling. Based on the optimization techniques introduced in the former part of this chapter, we also deal with several problems associated with their applications in the latter part.

Wireless networks always consist of equipments which belong to different organizations/persons. Hence, nodes in wireless networks are self-interested. Game theory, a set of tools originally studied in microeconomics to predict the behavior of selfish individuals in free market, now becomes a valuable tool to handle various problems for routing and media access in wireless networks with selfish and rational users. This chapter focuses on the applications of game theoretic tools in wireless networks. In each subsection of this chapter, we will introduce important concepts in game theory using definitions/theorems and followed by their applications on important papers published in wireless networks.

The chapter starts with strategic form games, which are the most widely used game formulations in wireless research. Pure Nash equilibrium and mixed equilibrium are discussed as two major branches of strategic form games. Supermodular games and potential games, two classes of the games with desired property to improve system performance, are presented as special cases of strategic form games. Subsequently, repeated games (a.k.a. iterated games) are discussed with its application in reputation system design. This is followed by a brief discussion of Bayesian games to model scenarios with incomplete information. The chapter concludes with a discussion of truthful auctions and their application in pricing based wireless routing problems.

One of the most important issues in wireless sensor networks (WSNs) is the design of optimized routing protocols that cannot only route the packets in an efficient way and with minimum overheads but also consider severe power restriction of those networks. Correct design of routing protocols can prolong the lifetime of these networks and therefore much research has been carried out to develop new and customized routing protocols for the WSNs. In this chapter, we will first look at different topologies of the WSNs, say flat and hierarchical networks and compare the two topologies from the routing efficiency point of view. We will then review the most important routing protocols designed for the WSNs for flat and hierarchical topologies. We will further look at some other routing protocols in those networks that aim at providing quality of service in sensor networks and can possibly control the power consumption and therefore the lifetime of the networks. Finally we will review data-centric and geographic routing approaches to complete our survey on routing protocols in WSNs.

Many new routing and MAC layer protocols have been proposed for wireless sensor networks tackling the issues raised by the resource constrained unattended sensor nodes in large-scale deployments. The majority of these protocols considered energy efficiency as the main objective and assumed data traffic with unconstrained delivery requirements. However, the growing interests in applications that demand certain end-to-end performance guarantees and the introduction of imaging and video sensors have posed additional challenges. Transmission of data in such cases requires both energy and QoS aware network management in order to ensure efficient usage of the sensor resources and effective access to the gathered measurements. In this chapter, we highlight the architectural and operational challenges of handling of QoS traffic in sensor networks. We report on progress make to-date and discuss sample of our work in more details. Finally, we outline open research problems.

Wireless sensor networks (WSNs) have been proposed as a solution to several monitoring, tracking, environmental and other applications. In such networks, a large number of small and simple sensor devices communicate over short range wireless interfaces to deliver observations over multiple hops to central locations called sinks. WSNs have been considered for several critical application scenarios including battlefield surveillance, habitat monitoring, healthcare, manufacturing, traffic monitoring, homeland defense and security applications. Initial studies and deployments of WSNs considered static sensor nodes and static data sinks. In the past few years, there has been substantial interest in introducing limited levels of mobility in the network architecture. This chapter will present a comprehensive survey of such mobility approaches studied in the literature. Mobility has been proposed with several objectives, including improved data dissemination capacity for high-bandwidth sensor traffic, balanced energy consumption among sensor nodes, improved locationing and improved security services. This chapter will describe schemes with mobile data sinks (or base station), mobile data collection entities, mobile relay nodes, and mobile security/locationing support nodes.

The main-stream approach of wireless sensor networks is to densely deploy a large number of sensor nodes, forming a well-connected mesh network for data delivery. This approach, however, cannot be applied to the scenarios with extremely low and intermittent connectivity due to sparse network density and sensor node mobility. In such networks, the traditional routing protocols counting on end-to-end connections simply fail. In order to address this problem, the Delay-Tolerant Mobile Sensor Network (DTMSN) has been recently proposed. A typical DTMSN consists of two types of nodes, the wearable sensor nodes and the high-end sink nodes. The former are attached to mobile objects, gathering target information and forming a loosely connected mobile sensor network for data delivery; the latter collects data from the mobile sensor nodes and forward the data to the end user through a backbone network. This chapter focuses on a survey of current research on DTMSN. We first give an overview of the typical architecture of DTMSN. Then, several representative DTMSN systems are discussed in detail. We expect that this chapter will provide a deep understanding of the characteristics of DTMSN, leading to useful insights for future protocol design.

Radio frequency identification (RFID) and wireless sensor networks (WSN) are two important wireless technologies that have a wide variety of applications and provide limitless future potentials. RFID facilitates detection and identification of objects that are not easily detectable or distinguishable by using current sensor technologies. However, it does not provide information about the condition of the objects it detects. Sensors, on the other hand, provide information about the condition of the objects as well as the environment. Hence, integration of these technologies will expand their overall functionality and capacity. This chapter first presents a brief introduction on RFID and then investigates recent research works, new patents, academic products and applications that integrate RFID with sensor networks. Four types of integration are discussed: (1) integrating tags with sensors; (2) integrating tags with wireless sensor nodes and wireless devices; (3) integrating readers with wireless sensor nodes and wireless devices; and (4) mix of RFID and wireless sensor networks. New challenges and future works are discussed at the end.

Semantic Web and Sensor Networks are two exciting areas of ongoing research and development. While much of the existing research in sensor networks has focused on the design of sensors, communications, and networking issues, the needs and opportunities arising from the rapidly growing capabilities and scale of dynamically networked sensing devices open up demands for efficient data management and convenient programming models. Semantic web represents a spectrum of effective technologies that support complex, cross-jurisdictional, heterogeneous, dynamic and large scale information systems. Recently, growing research efforts on integrating sensor networks with semantic web technologies have led to a new frontier in networking and data management research. The goal of the chapter is to develop an understanding of the semantic web technologies, including sensor web, ontologies, and semantic sensor web services, which can contribute to the growth, application and deployment of large-scale sensor networks, leading to a broad interdisciplinary scope, such as ontology-based sensor networks, semantic sensor networks, cognitive radio networks, and so on.

Broadcast authentication is a critical security service in wireless sensor networks (WSNs), as it allows the mobile users of WSNs to broadcast messages to multiple sensor nodes in a secure way. Previous solutions on broadcast authentication are mostly symmetric-key-based solutions such as μTESLA and multilevel μTESLA. These schemes are usually efficient; however, they all suffer from severe energy-depletion attacks resulted from the nature of delayed message authentication. Being aware of the security vulnerability inherent to existing solutions, we present several efficient public-key-based schemes in this chapter to achieve immediate broadcast authentication with significantly improved security strength. Our schemes are built upon the unique integration of several cryptographic techniques, including the Bloom filter, the partial message recovery signature scheme and the Merkle hash tree. We prove the effectiveness and efficiency of the proposed schemes by a comprehensive quantitative analysis of their energy consumption regarding both computation and communication.

With the advancements of networking technologies and miniaturization of electronic devices, wireless sensor networks (WSN) have become an emerging area of research in academic, industrial, and defense sectors. Sensors combined with low power processors and wireless radios will see widespread adoption in the new future for a variety of applications including battlefield, hazardous area, and structural health monitoring. However, many issues need to be solved before the full-scale implementations are practical. Among the research issues in WSN, security is one of the most challenging. Securing WSN is challenging because of the limited resources of the sensors participating in the network. Moreover, the reliance on wireless communication technology opens the door for various types of security threats and attacks. Considering the special features of this type of network, in this chapter we address the critical security issues in wireless sensor networks. We discuss cryptography, steganography, and other basics of network security and their applicability to WSN. We explore various types of threats and attacks against wireless sensor networks, possible countermeasures, and notable WSN security research. We also introduce the holistic view of security and future trends for research in wireless sensor network security.

Briefly, in this chapter we will present the following topics:

• Basics of security in wireless sensor networks.

• Feasibility of applying various security approaches in WSN.

• Threats and attacks against wireless sensor networks.

• Key management issues.

• Secure routing in WSN.

• Holistic view of security in WSN.

• Future research issues and challenges.

In this chapter, we provide a comprehensive survey of security issues in wireless sensor networks. We show that the main features of WSNs, namely their limited resources, wireless communications, and close physical coupling with environment, are the main causes of the their security vulnerabilities. We discuss the main attacks stemming from these vulnerabilities, along with the solutions proposed in the literature to cope with them. The security solutions are analyzed with respect to the different layers of the network protocol stack and cover the following issues: key management, secure data dissemination, secure data aggregation, secure channel access and secure node compromise.

Recently, Wireless Mesh Networks (WMNs) have drawn considerable attention in academia and industry due to their potential to supplement the wired backbone in a cost-effective manner. A WMN comprises of Mesh Routers (MRs) forming the backbone of WMN and serve Mesh Clients (MCs) in their neighborhood. A small set of these MRs provide Internet connectivity, and these MRs are referred to as Internet Gateways (IGWs). The remaining MRs form into network's backbone and employ multi-hop communication paradigm to provide relay services to MCs, which are the end users.

The key advantages of WMNs are their rapid deployment and ease of installation. WMNs are capable of providing attractive services in a wide range of application scenarios such as broadband home/enterprise/community networking, public safety surveillance systems and disaster management. However, unpredictable interference, excessive congestion, and half-duplex nature of radios at MRs may hinder deployment of WMNs. Traffic in WMNs is predominantly between IGWs and the MRs in contrast to Mobile Ad hoc Networks (MANETs) where traffic is among peer nodes. This focused traffic flow within WMNs towards and from IGWs places higher demand on certain paths connecting IGWs and MRs, unlike that of MANETs where the traffic is more or less uniformly distributed.

Ensuring fairness to multi-hop flows in WMNs is a critical issue that needs to be considered for their successful deployment. In this chapter, we provide an insight to these issues, analyze various approaches discussed in the literature, and evaluate their applicability to WMNs.

This chapter presents IEEE 802.11s, an emerging standard for wireless mesh networks (WMNs). IEEE 802.11s proposes multi-hop forwarding at the MAC level, which is a new approach for building WMNs. Traditional solutions for WMNs use network-level routing protocols to allow multi-hop forwarding among wireless mesh nodes. IEEE 802.11s specifies multi-hop MAC functions for mesh nodes using a mandatory path selection mechanism named HWMP (Hybrid Wireless Mesh Protocol) and also provides a path selection framework for alternative mechanisms and future extensions. This chapter discusses the emerging standard details and compares this new solution for WMNs to traditional ones.

This chapter discusses the problem of channel assignment in Wireless Mesh Networks (WMNs). Multiple channels can be employed by Mesh Routers (MRs) in such a network to increase the network capacity. Each MR is equipped with one or more radios (i.e. interfaces) each of which can operate on a selected channel. The purpose of channel assignment is to appropriately use radios on the available channels to satisfy specific objectives such as maximizing the network capacity. There are three major approaches for doing the assignment: static, dynamic, and hybrid approaches. In a static channel assignment, a link between a pair of neighboring MRs is assigned with a fixed channel and this binding does not change for a long duration. In a dynamic channel assignment, each MR is able to switch its radio to another channel in a dynamic fashion. Hybrid channel assignment, which integrates the two kinds of approaches, fixes some radios on a default channel while the rest of the radios are dynamically switched across channels. We present a detailed investigation of the current state-of-the-art protocols and algorithms in each category.

Ad hoc networks are peer-to-peer multi-hop wireless networks where the member nodes cooperate with one another for successful routing of packets. Wireless Mesh Networks (WMN) can be considered as a special case of wireless ad hoc networks where the participating nodes have relatively fixed positions. The network backbone consists of these relatively stationary nodes (also known as “mesh routers”). Other network nodes (called “mesh clients”), which may or may not participate in the routing mechanism connect to these mesh routers for network and Internet access. Although traditional ad hoc routing protocols may be used for Wireless Mesh Networks, they do not provide the best results. This is because some of the assumptions made by these protocols are not valid for WMNs, thus leading to sub-optimal performance. Also, due to the relatively stationary nature of mesh routers, load-balanced routing is desired for WMNs to avoid network hot spots.

In this chapter, we provide a study of routing protocols for multi-hop wireless mesh networks. Besides an extensive literature search on the topic, we also provide the challenges and directions for future research.

Over the past few years, wireless mesh networks (WMNs) have emerged to become a ubiquitous solution for providing wireless access at lower cost, greater flexibility, higher reliability and performance compared to conventional wireless local area network (WLANs). As the demand for delay sensitive real-time applications such as VOIP and streaming media grows, mobility management is becoming a critical function of WMN. Although Mobility management schemes designed for Mobile Ad Hoc Networks (MANETs) and traditional fixed networks might be useful for WMNs, mobility management in WMNs is still an active research issue because of the special properties of WMNs. This chapter focuses on the mobility management in wireless mesh networks, which takes into account the unreliability of wireless mesh links and other special properties of WMNs. The chapter began by discussing the special properties of WMNs and the general concepts of mobility management, and then gives an overview of the mobility management problems in wireless mesh networks (layer 2 handoff, vertical handoff and cross layer design, etc.) with some potential solutions.

Wireless Mesh Network (WMN) is a wired extension of multi-hop ad hoc network (MANET) which defines a new paradigm for broadband wireless Internet. A packet originating from a meshclient is relayed collaboratively in a multi-hop fashion by the intermediate mesh routers (MRs) towards the Internet Gateway (IGW). This is strictly true in a network managed by a single trusted authority. But, a WMN can be formed by a group of independent MRs operated by different service providers. It is a real challenge to establish a priori trust in a multi-operator WMN.

Unfortunately, the current thrust of research in WMNs, is primarily focused on developing multi-path routing protocols; and security is very much in its infancy. This book chapter provides a comprehensive coverage of various security issues pertinent to WMNs. We will systematically explore the vulnerabilities that can be exploited by attackers to conduct various attacks. We then provide a detailed description of some important security designs/proposals from industry and academia that will capture the current start-of-the-art solutions. We also cover key results from our research and other active researchers that have a great impact on the design of a secure WMN. Finally, we describe various open challenges which can catalyze new research efforts in this direction.

The following sections are included:

• Solutions

• Biography