Ad Hoc Networks. Lecture Notes of the Institute for Computer Sciences, Social-Informatics and Telecomm. Eng. Vol 28 - First International Conference, ADHOCNETS 2009, Niagara Falls, Ontario, Canada, September 22-25, 2009. Revised Selected Papers

Preface

Organization

Table of Contents

1st ICST International Conference on Ad Hoc Networks

Supporting Proactive Application Event Notification to Improve Sensor Network Performance

Introduction

Goals and Challenges of WSN Architectures and Middleware Support

Related Work

On Existing Architectures

On Existing Middleware

X-Lisa, an Architecture for Cross-Layer Information Sharing

Information Sharing Structures

Event Signaling

Information Exchange

Important Services

Middleware Support

General Ideas

Integration into an Information-Sharing Architecture

Composite Query Registration and Deregistration

Interest Registration and Deregistration

Query Notification

Evaluation of Middleware Support

Health Monitoring Test Scenario

Simulation Results

Conclusions and Future Work

References

An Energy-Efficient Cluster-Head Selection Protocol for Energy-Constrained Wireless Sensor Networks

Introduction

Related Work

ECHS Protocol

Two-Phase Cluster Set-Up Period

Steady State Period

Simulations

Conclusion

References

Optimization of Cluster Heads for Energy Efficiency in Large-Scale Wireless Sensor Networks

Introduction

Related Work

Cost Model and Problem Formulation

Energy Consumption Model

Problem Formulation

Optimizing Number and Location of CHs

Analytical Derivation for Uniform Distribution

Algorithm Design for General Distribution

Performance Evaluation

Implementation and Experimental Settings

Case Study for Uniform Distribution

Case Study for General Distribution

Conclusion and Future Work

References

Optimal Cluster Sizes for Wireless Sensor Networks: An Experimental Analysis

Introduction

Current Practice for Clustering Algorithms

State of the Art Clustering Protocols

Evaluation Methodologies for Clustering Algorithms

Related Efforts in Clustering Analysis

Defining the Optimal Cluster

Identifying the Optimal Cluster

Cluster Size C

Number of Base Stations M

Position of the Cluster Head PCH

In-Network Processing IN

Node Density N/A2

Conclusions and Future Work

References

A Parallel Paths Communication Technique for Energy Efficient Wireless Sensor Networks

Introduction

Network Model and Problem Definition

A Parallel Path Communication Technique

Algorithm Description

Forming Gradient Bands

Group Leader Election

Communication Network Setup Phase

Properties of the Parallel Path Technique

Simulation Setup

Performance Comparison

Conclusion

References

Scalable Max-Min Fairness in Wireless Ad Hoc Networks

Introduction

The Macro Model

Applying the Macro Model to Max-Min Fairness

Comparison of Three Methods

Experiment Model

Node-Path Model

Estimation Model

Simulation Results

600-Node and 20-Flow

600-Node and Different-Flow

1000-Node and 100-Flow

Time Square

Conclusions and Future Work

References

Upper Bounding Service Capacity in Multihop Wireless SSMA-Based Ad Hoc Networks

Introduction

Joint Transmission Scheduling and Power Control Problem Formulation

Tabu Search-Based Heuristic Algorithm

Simulations and Results

Conclusions

References

QoS over Real-Time Wireless Multi-hop Protocol

Introduction

Related Work

RT-WMP Overview

Protocol Operations.

The Link Quality Matrix.

Error Handling in RT-WMP.

Worst-Case in RT-WMP.

System Overview

Available Time

Protocol Operations

The RT-WMP QoS Extension Details

Frame Header Modification

Phases of the Protocol

The Message Selection Phase.

The QoS Authorization Phase.

The QoS Message Phase.

Message Priority Policy

Flow Admission Control

Available Resource Estimation

Principle of Operations.

Evaluation

Available Time

RT-WMP Traffic Impact

Fairness

End-to-End Delay

Multi-hop Transmission

PDR Evaluation

Real Scenario Experiments

Conclusions

References

Efficient Distribution of Large Files in UMTS Supported by Network Coded M2M Data Transfer with Multiple Generations

Related Previous Work

Enhanced Network Coding for Operation on Data of Arbitrary Size

Generations: Optimized Packet Combination

Analysis of Relationship between Different Figures of Merit

Numerical Results

Generation Size and File Size

Quality of Service (QoS) Requirements

Comparison of NC-MG-m2m File Sharing with Replicate-and-Forward m2m Data Dissemination

Summary

References

Enhancement of Self-organisation in Wireless Networking through a Cross-Layer Approach

Introduction

Self-organisation

Self-organising Networking Systems

Self-organising Algorithms in Networking Systems

Cross-Layer Design

What Is the Cross-Layer Approach?

Cross-Layering in Self-organisation

Related Study

Demonstration of the Enhancement

Simulation and Results

Conclusions

References

SPECS: Secure and Privacy Enhancing Communications Schemes for VANETs

Introduction

Problem Statement

Preliminaries

Bilinear Maps

Bloom Filter

Our Solutions - SPECS

Initial Handshaking

Message Signing

Batch Verification

Real Identity Tracking

Group Key Generation

Group Message Signing and Verification

Analysis

Security Analysis

Analysis on Bloom Filter Approach

Simulation Results

Simulation Models

Simulation Results

Conclusions

References

Security and Privacy in a Sensor-Based Search and Rescue System

Introduction

SenSearch: A Brief Overview

Threat Model

Security and Privacy Framework

System Constraints

Design Overview

AP-Node Authentication and Initial Setup

Node-Node Authentication and Record Exchanges

Implementation and Performance

Performance: Cryptographic Operations

Performance: AP-Node Authentication and Initial Setup

Performance: Node-Node Authentication

Security Overhead

Power Consumption

Conclusion

References

Computationally Efficient Mutual Entity Authentication in Wireless Sensor Networks

Introduction

LPN Problem and HB-Family

LPN Problem

HB-Family Authentication

Proposed Mutual Authentication Protocols

Protocols Description

Protocol Parameters

Performance

Security Analysis

Threat Model

Security Properties

Application Scenarios

Conclusion and Further Work

References

Distributed Detection of Wormhole Attacks in Wireless Sensor Networks

Introduction

Related Work

Our Contribution

Definitions and Models

Communication Model

Adversary Model

Intrusion Detection System

Intrusion Detection Nodes

Detecting Wormholes

FMC Validation.

Active Wormholes.

Passive Wormholes.

Distinguishing Active from Passive Wormholes.

False Alarms

Response to Wormholes

Simulation

Connectivity of Sensor Nodes

ID Nodes Density

Effect of Wormhole Length on Detection

Conclusions and Future Work

References

Power-Aware Intrusion Detection in Mobile Ad Hoc Networks

Introduction

Our Contributions

Related Work

Intrusion Detection in MANETs

Evolutionary Computation Techniques in Intrusion Detection

Genetic Programming

Multi-Objective Optimisation (MOO)

Power-Aware Intrusion Detection in MANETs

Experimental Results

Conclusions and Future Work

The Features

DHT-Based Detection of Node Clone in Wireless Sensor Networks

Introduction

Previous Protocols

Centralized Detection

Distributed Detection

Goals and Models

Security Goals and Performance Metrics

Network Model

Adversary Model

Proposed Protocol

Distributed Hash Table

Protocol Details

Analysis

Communication Cost

Storage Cost and Number of Witnesses

Security Analysis

Simulations

Settings

Protocol Performance

Resilience against Message-Discarding by Clones

Conclusion and Future Work

References

Connectivity-Aware Minimum-Delay Geographic Routing with Vehicle Tracking in VANETs

Introduction

Connectivity-Aware Minimum-Delay Geographic Routing

Assumptions and System Model

CMGR Protocol Operations

Route Selection Logic

Vehicle Tracking Mechanism in CMGR

Performance Evaluations

Simulation Settings

Simulation Results

Conclusion

References

Buckshot Routing - A Robust Source Routing Protocol for Dense Ad-Hoc Networks

Introduction

The Nature of Unidirectional Links

Impact on the Routing Layer

The Buckshot Routing Protocol

Lossy or Unidirectional Links

Evaluation

OMNeT++

TMote Sky

Related Work

Conclusion and Future Work

References

Enhanced Route-Split Routing Tolerant to Multiple Concurrent Link Failure for Mobile Ad Hoc Networks

Introduction

RSR (Route-Split Routing)

Outline of RSR

Route Creation

Route Maintenance

Resiliency to Simultaneous Failure of RSR

Enhanced RSR

Proposal Mechanism 1

Proposal Mechanism 2

Proposal Mechanism 3

Simulation Evaluation

Simulation Environment

Simulation Results and Observations

Conclusion

References

A Simulation-Based Performance Analysis of VariousMultipath Routing Techniques in ZigBee Sensor Networks

Introduction

Multipath Routing

Multipath Formation Strategies

Multipath Usage Strategies

Benefits of Multipath Routing

The Challenges of Multipath Routing in the Wireless Domain

ZigBee Wireless Sensor Networks

ZigBee Network Topology

The ZigBee Stack

Simulations

Implemented Multipath Algorithms

Parameters

Metrics

Results

Per-Hop Packet Loss

Conclusion and Future Work

References

Centralized Routing and Scheduling Using Multi-Channel System Single Transceiver in 802.16d

Introduction

System Design Algorithms

Routing Path Construction Algorithm

Channel Assignment Algorithm for Multi-Channel System

Collision Free Centralized Scheduling Algorithm

Cross-Layer Design

Simulations

Performance Metrics

Simulation Setup

Results and Discussions

Conclusions

References

Contact Time in Random Walk and Random Waypoint: Dichotomy in Tail Distribution

Introduction

Model Analysis

Model Settings and Assumptions

Random Walk with Infinite Flight Lengths

Tail Behavior of Contact Time Distribution

Random Walk with Finite Flight Lengths

Validation

Infinite Flight Lengths without Pause

Finite Flight Lengths without Pause

Conclusion and Future Work

References

Throughput Analysis of IEEE 802.11 DCF in the Presence of Transmission Errors

Introduction

IEEE 802.11 Distributed Coordination Function (DCF)

Transmission Errors

System Performance Analysis

Network Model Assumptions

Transmission Probability

The Throughput

Analysis Results

Conclusion

References

Effects of Unintentional Denial of Service (DOS) Due to Push-to-Talk (PTT) Delays on Performance of CSMA/CA Based Adhoc Land Mobile Radio (LMR) Networks

Introduction

Push-To-Talk (PTT) Delays

CSMA/CA Implementation for the Medium Access Layer (MAC)

Unintentional Denial of Service (DOS) Due to RTSI Delays

Simulation

Conclusions

References

Achievable Region in Slotted ALOHA Throughput for One-Relay Two-Hop Wireless Network Coding

Introduction

Previous Work

System Description

Achievable Region of Direct Communication Systems

Achievable Region of Non-NC Systems

Achievable Region of NC Systems

Conclusion

References

Exact Models for the $k$-Connected Minimum Energy Problem

Introduction

The Homogeneous Minimum Energy Problem

Exact 1-Connected Models

Literature Review

A New Model

Exact k-Connected Models

Numerical Results

Computational Complexity

Discussion

References

Performance Evaluation of Quality of Service in IEEE 802.11e Wireless LANs

Introduction

Comparison of DCF and EDCA

Contention Window Based Priority

Arbitrary Interframe Space

Transmission Opportunity Limit

Average Conditional Collision Probability

Normal Contention Markov Backoff Process

Average Conditional Probability

Throughput Analysis

Model Validation

Conclusions

References

Cooperative Localization in GPS-Limited Urban Environments

Introduction

Related Work

Cooperative Localization

Sensor Evaluation and Error Models

Simulation Results

Simple Averaging: 300-Meter Maximum Range

Simple Averaging: 100-Meter Range

Simple Averaging: 15-Meter Range

Distribution of Error

Selective Averaging

Filtered Trilateration

Future Work

Conclusion

References

Tracking a Vehicle Moving in a Wireless Sensor Network

Introduction

Mote Topology and Communication

Hot Motes and Network Resolution

Hot Mote

Updating the Target Location over Time

Test Bed Experiment

Conclusions

References

Improved Topology Control Algorithms for Simple Mobile Networks

Introduction

Related Work

Preliminaries

Graph Definitions

Voronoi Diagram and Delaunay Triangulation

Decision Version of SMN

Optimization Version of SMN

Running Times

An Approximation Algorithm for SMN

Simulation Results

Conclusions and Future Work

References

Reliable Coverage Area Based Link Expiration Time (LET) Routing Metric for Mobile Ad Hoc Networks

Introduction

Related Work

AODV Overview

Coverage Area Analysis

Link Expiration Time

Proposed Routing Metric Description

Simulation Environment and Results

Conclusions

References

Constructing Minimum Relay Connected Sensor Coverin Heterogeneous Wireless Sensor Networks

Introduction

Related Work

Problem Formulation

Theoretical Analysis

Full Coverage

Relay Connectivity

Distributed Algorithm

MSC Construction

Relay Connectivity Reinforcement

Performance Evaluation

Conclusions

References

Experimentation Made Easy

Introduction

DES-Testbed

DES-TBMS

Architecture of DES-TBMS

DES-Cript

DES-Exp

DES-Mon

DES-Eval

DES-Vis

Experiment Workflow

Evaluation

Contributions of DES-TBMS

Limitations

Related Work

Testbeds

Simulation Environments

Conclusions and Future Work

References

Enhancing Learning Using Modular Wireless Sensor Networking (WSN) Hands-On Experiments

Introduction

Wireless Sensor Networks Platform Experiments

Experiment 1 – Basic Target Detection

Experiment 2 – Local, Selected and Consensus Decision on Target Detection

Experiment 3 – Motion Tracking

Assessment Survey and Evaluation

Assessment Survey

Results of the Survey

Conclusive Assessments

Conclusions

References

Appendix

Sensor Network in the Wireless UHF Band

Introduction

Data Acquisition System

Data from Sensors

Global Data Management

The State-of-the-Art and the Implemented Network

The Wireless Sensor Network (WSN)

Implementation of the WSN in the UHF Band

Future Developments

Conclusions

References

VoIP Implementation and Experiments on a Mobile Wireless AdHoc Network

Introduction

Testbed Configuration and Network Operations

The ASNC Scheme

Testbed Implementation

Hardware Setup

Software Setup

Mobile Scenarios and Their Measurements

Measurements and Observations

Verification of Simulations

Conclusion

References

Relay Implementation in WiMAX System Level Simulator

Introduction

Characteristics of the Relay

System Model Architecture

Cellular Layout

System Model

Relay Selection

Effective SINR-Based Relay Selection Algorithm

Path Loss-Based Relay Selection Algorithm

Simulation Results

Conclusion

References

MeshMAC: Enabling Mesh Networking over IEEE 802.15.4 through Distributed Beacon Scheduling

Introduction

Related Work

The MeshMAC

Distributed Beacon Scheduling Specification

Mesh Data Transfer

MeshMAC Operation

Evaluation

Distributed Beacon Scheduling

Multipath Mesh Networking

Energy Efficiency

Conclusions

References

Compressing MAC Headers on Shared Wireless Media

Introduction

MAC Header Compression

Compression

Decompression

Compressing 802.11 Headers

Data Frames

ACK Frames

Experimental Results

Label Conflicts

Performance

Conclusions

References

An RTS Based Data Channel Reservations and Access Scheme in Multi-Channel Systems

Introduction

Motivation

Related Work

System Model

Simulation Model and Numerical Results

Future Work

Conclusion

References

Building Intrusion Detection with a Wireless Sensor Network

Introduction

Related Work

Visual Sensor Networks

Event Classification

Anomaly Detection

Office Monitoring

System Design

ART Neural Networks

System-Wide Anomaly Detection

Anomaly Detection Performance

Office Occupancy Patterns

Computation at Desktop PC

Detection Performance of the Anomaly Detectors

Message Load

Reporting and Triggering Delay

Conclusions and Future Work

References

Passive and Active Analysis in DSR-Based Ad Hoc Networks

Introduction

Motivation, Previous Work, Contributions

Motivation

Previous Work

Contributions

Network Model

Intelligent Jamming

Classification Algorithm

Handling Fluctuating Congestion Window Sizes

Cross-Protocol Detection

Dynamic Mean Delay Calculation

Numerical Results

Active Network Analysis

Controlling the Network

Lomb Periodogram

Conclusion

References

An E-Hospital Security Architecture

Introduction

Background and Related Work

E-Hospital System

Related Cryptography

Security Goal of E-Hospital

Related Privacy Acts and Regulations

User Requirements

Security Goal of E-Hospital

Security Architecture of E-Hospital

Layered Design to Meet Security Goals

Secure Communication Channel by Identity-Based Cryptography

Secure Communication between End User and Backbone Network by Policy Based Cryptography

Database Security

Conclusion and Future Work

References

Cooperative Certificate Revocation List Distribution Methods in VANETs

Introduction

Overview of DSRC/WAVE

Overview of Network Coding versus Erasure Coding

Overview of Previous CRL Distribution Methods

Overview of Code Torrent

Using Code Torrent for CRL Distribution

Development of Methods to Reduce Channel Contention

Description of "Most Pieces Broadcast" (MPB) Method

Description of “Generation Per Channel" (GPC) Method

Simulation Setup

Simulation Results and Analysis

Conclusion

References

Distributed Channel Selection for Ad-Hoc Networks in the Presence of Jamming Sources

Introduction

Problem Definition

Performance Testbed

Implementation of Distributed Channel Selection

Homogeneous Scenarios

Heterogeneous Scenarios

Conclusion and Future Work

References

Joint Random Access and Power Control Game in Ad Hoc Networks with Noncooperative Users

Introduction

Related Work

System Model and Problem Formulation

Random Access, Power Control and Link Capacity

Joint Random Access and Power Control Game

Existence of Nash Equilibrium

Distributed Algorithm

Conclusion and Future Work

References

Graph Marginalization for Rapid Assignment in Wide-Area Surveillance

Introduction

Decentralization of the Algorithm

The Sensor Network

Objects

Sensors

Objective

Probability That an Object Will Be Visible to a Sensor

Simulations

Data Structure

First Application

Second Application

Conclusion

References

Error Correction with the Implicit Encoding Capability of Random Network Coding

Introduction

Network Model

Random Network Coding

Error Correction in Random Network Coding: Traditional Method

Redundant Symbols

Redundant Packets

Error Correction in Random Network Coding: Proposed Method

Network Configurations

Example 3

Analysis

Probability of Decoding

Discussion of Complexity

Time Delay

Error Correcting Capability

Advantages

Conclusion

References

An End-to-End Loss Discrimination Scheme for Multimedia Transmission over Wireless IP Networks

Introduction

Theoretical Foundation of the WMPLD Algorithm

Implementation Aspects of WMPLD

Senders Behavior

Receivers Behavior

Simulation Results

Wireless Last Hop

Wireless Backbone

Conclusion

References

2009 International Workshop on Advanced Sensor Integration Technology

Architecture for WSN Nodes Integration in Context Aware Systems Using Semantic Messages

Introduction

Related Work

Semantic Adaptation

Information Representation

General Packet Structure

Network Protocol

Context Management

System General Operation

Prototype

Hardware Platform

Network Protocol

Software Implementation

Application Scenario

Prototype Analysis

Conclusions and Future Work

References

Performance Analysis of ZigBee Technology for Wireless Body Area Sensor Networks

Introduction

Architecture

System Architecture

WBASN Topology

ZigBee Network

Performance Evaluations

Simulation Setup

Average Reception Ratio and Throughput

Latency

Fairness

Mobility

Conclusion

References

Analytical Models of Cross-Layer Protocol Optimization in Real-Time Wireless Sensor $Ad Hoc$ Networks

Introduction

Quality of Service

Previous Research on Quality of Service in Cross-Layer Models

Data Classes and Protocol Layers

Analytical Models of Cross-Layer Design

Statistical Properties of Packetized Traffic

Statistical Properties of QoS Classes

Energy-Efficient Routing

Routing Policies

Network Processes and Conditional Rates

Protocol Parameters and QoS Metrics

Cross-Layer Optimization

Energy-Constrained QoS Optimization

Recursive Optimality Conditions with Complete Network Observations

Optimality Conditions with Markov Assumptions

Explicit Solutions versus Closed-Form Solutions

Conclusions

References

Programmable Re-tasking of Wireless Sensor Networks Using WISEMAN

Introduction

Overview of WISEMAN

WISEMAN’s Architecture

WISEMAN’s Language Constructs

Migration Procedures and Agent Execution Flow

Code Migration Methodology

Agent Execution Flow

Performance Evaluations

Conclusions

References

Oxybuoy: Constructing a Real-Time Inexpensive Hypoxia Monitoring Platform

Introduction

Oxybuoy Architecture

Experiments

Conclusion

References

An Energy-Efficient, Application-Oriented Control Algorithm for MAC Protocols in WSN

Introduction

Related Work

The Algorithm

Mapping Parameter for Traffic Load

The Balance Point

QoS Threshold

Control Threshold

Algorithm Description

Performance Evaluation

Simulation Setup

The Energy Consumption Efficiency of Single Application in the Network

The Energy Performance of Multiple Applications

Conclusion

References

An Integrated RFID and Sensor System for Emergency Handling in Underground Coal Mines Environments

Introduction

Related Works

Integrated RFID and Sensor System for Emergency Handling

Overview of Traditional Emergency Handling

The Proposed Emergency Handling Scheme

Conclusion

References

An Area-Based Overlay Architecture for Scalable Integration of Sensor Networks

Introduction

Related Work

System Overview

System Elements

Area Names

Sensor Types

Query Submission and Reception of Results

Maintenance of the Overlay

A Query Processor Joins the System

A Query Processor Leaves the System

A Query Processor Fails

Areas of Responsibility and Promotion of Query Processors

Examples

Query Processing

Query Forwarding and Multiplexing

Result Delivery and De-multiplexing

Query Cancellation

Evaluation

Conclusion

References

2009 International Workshop on Cross-Layer Design in Wireless Mobile Ad Hoc Networks

Outage Probability for ARQ Decode-and-Forward Relaying under Packet-Rate Fading

Introduction

System Model

Outage Performance Analysis

Direct ARQ Transmission Scheme

DF Cooperative ARQ Relay Scheme

Simulation Results

Conclusions

References

Distributed Spectrum Sharing for Video Streaming in Cognitive Radio Ad Hoc Networks

Introduction

System Model

Prioritized Queuing

Distributed Spectrum Sharing and Medium Access Control for Video Streaming

Spectrum Sharing Principle

Spectrum Utility

Dynamic Spectrum Allocation

Delay Estimation

Proposed Cross-Layer Control Scheme

Performance Evaluation

Conclusions

References

The Cognitive Radio Channel: From Spectrum Sensing to Message Cribbing

Introduction

Channel Model

Capacity Lower Bounds

b21+P2

1b2<1+P2

b2<1

Capacity Outer Bounds

Conclusion and Discussions

References

AM-AOMDV: Adaptive Multi-metric Ad-HocOn-Dem and Multipath Distance Vector Routing

Introduction

Adaptive Multi-metric AOMDV Routing Scheme

Multiple Routing Metrics

Route Setup Stage

Data Transmission Using Local Path Update

Enhanced Link Layer Failure Handling

Route Maintenance

Simulation and Discussion

Simulation Scenario

Varying Average Node Speed

Varying Number of Connections

Varying Packet Rates

Conclusion

References

A Low-Latency TDMA Scheduler for Multi-hop Cluster Based MANETs with Directional Antennas

Introduction

Routing

MAC

Proposed Solution

The Scheduling Algorithm

Expected Latencies

Linear Topology

Intra-cluster, One Branch

Intra-cluster, Two Branches

Neighboring Clusters, One Branch Each

Neighboring Clusters, Two Branches Each

Many Clusters, One Branch in Each End Cluster

Many Clusters, Two Branches in Each End Cluster

Summary of Analysis

Simulation Results

Static, Linear

Non-linear, Static Case

Mobile Case

Conclusion

References

Author Index