Skip to main content
main-content

Über dieses Buch

This book constitutes the refereed proceedings of the 10th International Conference on Ad-hoc, Mobile, and Wireless Networks, ADHOC-NOW 2011 held in Paderborn, Germany, July 18-20, 2011.

The 23 revised full papers presented together with 4 invited papers were carefully reviewed and selected from 53 submissions. The papers are organized in topical sections on routing and activity scheduling, topology control, medium access control, security, mobility management and handling, applications and evaluation, and analytical considerations.

Inhaltsverzeichnis

Frontmatter

Routing and Activity Scheduling

Effective Geographic Routing in Wireless Sensor Networks with Innacurate Location Information

Abstract
Geographic routing is one of the most widely-accepted techniques to route information in wireless sensor networks. The main novelty is that the current node routes the packet to a neighbor which is located closer to the destination than itself. This process is called greedy routing. When the packet reaches a node that has no neighbors located closer to the destination than itself (a.k.a. local minimum) a recovery strategy is used to get to nodes that can again resume greedy routing. However, recent studies have proven that geographic routing may be ineffective in real deployments where location estimation systems introduce location errors. In this paper, we analyze in detail the problems induced by location errors in greedy routing and propose an Effective Greedy Routing supporting Location Errors (EGLE). Our simulation results show that EGLE is able to outperform existing solutions. It achieves nearly a 100% packet delivery ratio with very little additional overhead.
Rafael Marin-Perez, Pedro Miguel Ruiz

Energy Efficient Mobile Routing in Actuator and Sensor Networks with Connectivity Preservation

Abstract
In mobile wireless sensor networks, flows sent from data collecting sensors to a sink could traverse inefficient resource expensive paths. Such paths may have several negative effects such as devices battery depletion that may cause the network to be disconnected and packets to experience arbitrary delays. This is particularly problematic in event-based sensor networks (deployed in disaster recovery missions) where flows are of great importance. In this paper, we use node mobility to improve energy consumption of computed paths. Mobility is a two-sword edge, however. Moving a node may render the network disconnected and useless. We propose CoMNet (Connectivity preservation Mobile routing protocol for actuator and sensor NETworks), a localized mechanism that modifies the network topology to support resource efficient transmissions. To the best of our knowledge, CoMNet is the first georouting algorithm which considers controlled mobility to improve routing energy consumption while ensuring network connectivity. CoMNet is based on (i) a cost to progress metric which optimizes both sending and moving costs, (ii) the use of a connected dominating set to maintain network connectivity. CoMNet is general enough to be applied to various networks (actuator, sensor). Our simulations show that CoMNet guarantees network connectivity and is effective in achieving high delivery rates and substantial energy savings compared to traditional approaches.
Essia Hamouda, Nathalie Mitton, David Simplot-Ryl

Joint Duty Cycle Scheduling, Resource Allocation and Multi-constrained QoS Routing Algorithm

Abstract
Wireless mesh sensor networks (WMSNs) have recently gained a lot of interest due to their communication capability to support various applications with different Quality of Service (QoS) requirements. The most challenging issue is providing a tradeoff between the resource efficiency and the multi-constrained QoS support. For this purpose, we propose a cross-layer algorithm JSAR (Joint duty cycle Scheduling, resource Allocation and multi-constrained QoS Routing algorithm) for WMSNs based on multi-channel multi-time slot Medium Access Control (MAC). To the best of our knowledge, JSAR is the first algorithm that simultaneously combines a duty cycle scheduling scheme for energy saving, a resource allocation scheme for efficient use of frequency channels and time slots, and an heuristic for multi-constrained routing protocol. The performance of JSAR has been evaluated, showing that it is suitable for on-line implementation.
Jamila Ben Slimane, Ye-Qiong Song, Anis Koubaa, Mounir Frikha

Energy Efficient Monitoring for Intrusion Detection in Battery-Powered Wireless Mesh Networks

Abstract
Wireless Mesh Networks (WMN) are easy-to-deploy, low cost solutions for providing networking and internet services in environments with no network infrastructure, e.g., disaster areas and battlefields. Since electric power is not readily available in such environments battery-powered mesh routers, operating in an energy efficient manner, are required. To the best of our knowledge, the impact of energy efficient solutions, e.g., involving duty-cycling, on WMN intrusion detection systems, which require continuous monitoring, remains an open research problem. In this paper we propose that carefully chosen monitoring mesh nodes ensure continuous and complete detection coverage, while allowing non-monitoring mesh nodes to save energy through duty-cycling. We formulate the monitoring node selection problem as an optimization problem and propose distributed and centralized solutions for it, with different tradeoffs. Through extensive simulations and a proof-of-concept hardware/software implementation we demonstrate that our solutions extend the WMN lifetime by 8%, while ensuring, at the minimum, a 97% intrusion detection rate.
Amin Hassanzadeh, Radu Stoleru, Basem Shihada

Topology Control

Using Battery Level as Metric for Graph Planarization

Abstract
Topology control in wireless sensor networks is an important issue for scalability and energy efficiency. It is often based on graph reduction performed through the use of Gabriel Graph or Relative Neighborhood Graph. This graph reduction is usually based on geometric values. In this paper we tackle the problem of possible connectivity loss in the reduced graph by applying a battery level based reduction graph. Experiments are conducted to evaluate our proposition. Results are compared with RNG reduction which takes into account only the strength of the received signal (RSSI). Results show that our algorithm maintains network connectivity longer than solutions from the literature and balances the energy consumption over nodes.
Jovan Radak, Nathalie Mitton, David Simplot-Ryl

Empirical Approach to Network Sizing for Connectivity in Wireless Sensor Networks with Realistic Radio Propagation Models

Abstract
Choosing the appropriate network size to guarantee connectivity in a WSN deployment is a challenging and important question. Classic techniques to answer this question are not up to the challenge because they rarely consider realistic radio models. This work proposes a methodology to evaluate the performance of network size estimation techniques in terms of connectivity efficiency under realistic radio scenarios. This study is carried out using Atarraya, a simulation tool for wireless sensor networks, considering three classical estimation techniques and a radio model based on the specifications of the ZigBee radio from off-the-shelf WaspMote nodes from Libelium. The results show that the hexagon-based optimal grid technique provides the most efficient estimate, offering a high connectivity level with the lowest estimated number of nodes for a given proximity radius parameter, followed by the circle packing and the triangle-based grid distribution. In addition, the results show that packet error rates of 10% could still produce highly connected topologies.
Pedro Wightman, Miguel Jimeno, Daladier Jabba, Miguel Labrador, Mayra Zurbarán, César Córdoba, Armando Guerrero

A Topology Control Algorithm for Interference and Energy Efficiency in Wireless Sensor Networks

Abstract
Topology control is one of the main techniques that can be used to decrease energy expenditure and/or interference in wireless sensor networks. Less attention, however, has been devoted to algorithms that address energy and interference efficiency together. In this paper, we describe a localized topology control algorithm called TCO which is very efficient in terms of interference while minimizing energy efficiency. In order to evaluate TCO in terms of interference and compare it with other algorithms, we defined a new metric called PICS (Path Interference Cost based on Sender) Spanning Factor. According to this metric, in our experiments TCO outperformed all related localized topology control algorithms and its performance was extremely close to the performance of a centralized algorithm which is optimal according to the PICS spanning factor (a variation of ATASP based on PICS).
Hugo Braga, Flávio Assis

Fault Tolerant Interference-Aware Topology Control for Ad Hoc Wireless Networks

Abstract
Interference imposes a major challenge for efficient data communication in wireless networks. Increased level of interference may increase number of collisions, energy consumption and latency due to retransmissions of the interfered data. Interference of a link is the number of nodes interfered while a pair of nodes are communicating over a bi-directional link. Approaches have been proposed to reduce interference by dropping links that create high interference. However, dropping links make a network more susceptible to node failure/departure–a frequent phenomenon in ad hoc networks. Thus dropping high interference links while keeping the network significantly connected is an important goal to achieve. In this paper, we formulate the problem of constructing minimum interference path preserving and fault tolerant wireless ad hoc networks and then provide algorithms, both centralized and distributed with local information, to solve the problem. Moreover, for the first time in literature, we conceive the concept of fault tolerant interference spanner and provide a local algorithm to construct such spanner of a communication graph.
Md. Ehtesamul Haque, Ashikur Rahman

Medium Access Control

PaderMAC: A Low-Power, Low-Latency MAC Layer with Opportunistic Forwarding Support for Wireless Sensor Networks

Abstract
Modern medium access control (MAC) protocols for wireless sensor networks (WSN) focus on energy-efficiency by switching a node’s radio on only when necessary. This intoduced rendezvous problem is gracefully handled by modern asynchronous approaches to WSN MAC’s, e.g. X-MAC, using strobed preambles. Nevertheless, most MAC layer ignore the possible benefits in energy consumption and end-to-end latency, supporting opportunistic routing can provide. In this paper we present PaderMAC, a strobed preamble MAC layer which supports cross-layer integration with an arbitrary opportunistic routing layer. This work specifies the PaderMAC protocol, explains its implementation using TinyOS and the MAC layer architecture (MLA), and presents the results of a testbed performance study. The study compares PaderMAC in conjunction with opportunistic routing to X-MAC in conjunction with path-based routing and shows how PaderMAC reduces the preamble length, better balances the load and further improves the end-to-end latency within the network.
Marcus Autenrieth, Hannes Frey

Overhearing for Congestion Avoidance in Wireless Sensor Networks

Abstract
Convergecast traffic pattern is predominant in current wireless sensor networks. Few packets are periodically sent toward the sink, but interesting events may generate a burst of packets for a limited period of time. Such burst may create congestion in the surrounding of the event and thus may result in packet loss. Several congestion avoidance solutions exist in the literature but they either involve a lot of control messages or complicate the deployment of sensor networks. We therefore propose a new approach, named CLOMAC, which can be integrated to existing preamble-based MAC protocols.CLOMAC reduces congestion by overhearing and passively creating alternative paths toward the destination. An evaluation by simulation will demonstrate the benefits of our contribution integrated with the B-MAC protocol.
Damien Roth, Julien Montavont, Thomas Noël

Multihop Performance of Cooperative Preamble Sampling MAC(CPS-MAC) in Wireless Sensor Networks

Abstract
Cooperative communication(CC) is a promising technique to combat fading in a wireless environment. In our previous work, we proposed Cooperative Preamble Sampling(CPS)-Medium Access Control(MAC) protocol which highlighted the benefits of using CC in Wireless Sensor Networks(WSN). Initially, CPS-MAC performance was evaluated in a 3-node network comprising a single source, partner, and destination node.
In this paper, we evaluate the performance of CPS-MAC in a multi-hop WSN configuration, where a large number of sensor nodes are deployed around a sink to create a data gathering network. All nodes generate traffic, which leads to channel contention, collisions, and idle listening. Results show that, under light traffic load, CPS-MAC performs on par with non-cooperative preamble sampling protocol and performs significantly higher as traffic load increases.
Rana Azeem M. Khan, Holger Karl

Security

Secure Position Verification for Wireless Sensor Networks in Noisy Channels

Abstract
Position verification in wireless sensor networks (WSNs) is quite tricky in presence of attackers (malicious sensor nodes), who try to break the verification protocol by reporting their incorrect positions (locations) during the verification stage. In the literature of WSNs, most of the existing methods of position verification use trusted verifiers, which are in fact vulnerable to attacks by malicious nodes. They also depend on some distance estimation techniques, which are not accurate in noisy channels (mediums). In this article, we propose a secure position verification scheme for WSNs in noisy channels without relying on any trusted entities. Our verification scheme detects and filters out all malicious nodes from the network with a very high probability.
Partha Sarathi Mandal, Anil K. Ghosh

Efficient CDH-Based Verifiably Encrypted Signatures with Optimal Bandwidth in the Standard Model

Abstract
Exchanging items over mobile ad hoc network has been considered a challenging issue in recent years. To tackle this challenge, Verifiably Encrypted Signature (VES), which is employed as primitives when designing a large class of protocols such as certified email, fair exchange, and contract signing in wireless communication, provides a possible solution. However, the limited communication band, low computational ability and weak energy power restrict many existing verifiably encrypted signatures to be applied in ad hoc networks directly.
In this paper, we propose a compact verifiably encrypted signature scheme without random oracles based on the Computational Diffie- Hellman problem (CDH) with pairings. Comparing with prior works, our scheme achieves the following desired features: (1) Our verifiably encrypted signature has compact size (only two group elements) which is optimal for both Elgamal encryption and the Waters signature; (2) The scheme is more efficient in terms of signature generation and verification; (3) Our scheme also achieves provable security under a standard complexity assumption in the standard model. Apparently, our schemes are amongst the most efficient solutions in terms of both signature size and computation (optimal) because these features are important in wireless communication due to limited bandwidth and power. It can be surely applied flexibly to many secure exchange circumstances in mobile ad hoc network that solely allows the minimum cryptographic implementation.
Yuan Zhou, Haifeng Qian

MobiID: A User-Centric and Social-Aware Reputation Based Incentive Scheme for Delay/Disruption Tolerant Networks

Abstract
Delay/Disruption tolerant networks (DTNs) are wireless ad-hoc networks, where end-to-end connectivity can not be guaranteed and communications rely on the assumption that the nodes are willing to store-carry-and-forward bundles in an opportunistic way. However, this assumption would be easily violated due to the selfish nodes which are unwilling to consume precious wireless resources by serving as bundle relays. Incentive issue in DTNs is extraordinarily challenging due to the unique network characteristics. To tackle this issue, in this paper, we propose MobiID, a novel user-centric and social-aware reputation based incentive scheme for DTNs. Different from conventional reputation schemes which rely on neighboring nodes to monitor the traffic and keep track of each other’s reputation, MobiID allows a node to manage its reputation evidence and show to demonstrate its reputation whenever necessary. We also define the concepts of self-check and community-check to speed up reputation establishment and allow nodes to form consensus views towards targets in the same community, which is based on our social metric by forwarding willingness. Performance simulation are given to demonstrate the security, effectiveness and efficiency of the proposed scheme.
Lifei Wei, Haojin Zhu, Zhenfu Cao, Xuemin (Sherman) Shen

Improved Access Control Mechanism in Vehicular Ad Hoc Networks

Abstract
Access control of message is required when certain selected vehicles are granted access to information, instead of all vehicles within communication range. In these situations an access policy (consisting of attributes as road situation and vehicle type) is built into the vehicle and messages are encrypted using these access policies. Only valid vehicles possessing these attributes are able to decrypt the message. Huang and Verma [16] had proposed such an access control framework. The scheme assumed that the road-side units (RSU) are not compromised and had a very restricted access structure. We propose a new access control structure which eliminates the drawbacks of their schemes, by providing access control in presence of compromised RSU. Our technique permits a more general boolean access structure. Communication is possible between two vehicles which are monitored by two RSU, which was not permitted in [16]. The costs are comparable to that of [16].
Sushmita Ruj, Amiya Nayak, Ivan Stojmenovic

Mobility Management and Handling

A New Coverage Improvement Algorithm Based on Motility Capability of Directional Sensor Nodes

Abstract
In directional sensor networks (DSNs), motility capability of a directional sensor node has a considerable impact on the coverage enhancement after the initial deployment. Since random deployment may result in overlapped field of views (FoVs) and occluded regions, directional sensor nodes with rotatable mechanisms may reorganize their working directions to improve the coverage. Our proposed algorithm, Attraction Forces of Uncovered Points (AFUP), aims at both minimizing the overlapped areas and facing the working directions towards the area of interest. AFUP is a distributed iterative algorithm and exploits the repel forces exerted by the uncovered points around the sensor nodes. The proposed algorithm improves the coverage by 18%-25% after the initial deployment. Moreover, AFUP outperforms three well-known area coverage enhancement methods [15] [19] [16] in terms of coverage improvement and overlap minimization. Our simulation results show that AFUP converges in five iterations in most of the scenarios.
M. Amac Guvensan, A. Gokhan Yavuz

A Multi-objective Approach for Data Collection in Wireless Sensor Networks

Abstract
Wireless sensors networks (WSNs) are deployed to collect huge amounts of data from the environment. This produced data has to be delivered through sensor’s wireless interface using multi-hop communications toward a sink. The position of the sink impacts the performance of the wireless sensor network regarding delay and energy consumption especially for relaying sensors. Optimizing the data gathering process in multi-hop wireless sensor networks is, therefore, a key issue. This article addresses the problem of data collection using mobile sinks in a WSN. We provide a framework that studies the trade-off between energy consumption and delay of data collection. This framework provides solutions that allow decision makers to optimally design the data collection plan in wireless sensor networks with mobile sinks.
Christelle Caillouet, Xu Li, Tahiry Razafindralambo

Smart and Balanced Clustering for MANETs

Abstract
Clustering is the most widely used performance solution for Mobile Ad Hoc Networks (MANETs), enabling their scalability for a large number of mobile nodes. The design of clustering schemes is quite complex, due to the highly dynamic topology of such networks. A numerous variety of clustering schemes have been proposed in literature, focusing different characteristics and objectives. In this work, a fully distributed and clusterhead-free clustering scheme is proposed, namely Smart and Balanced Clustering for MANETs (SALSA). The scheme introduces a new cluster balancing mechanism and a best clustering metric, aiming to provide a reduced maintenance overhead. SALSA was evaluated and compared with the Novel Stable and Low-maintenance Clustering Scheme (NSLOC), featuring topologies with up to 1000 nodes and velocities of 20 meters per second. Results confirmed the performance efficiency of the new scheme, providing stability and low maintenance overhead, even in the largest networks.
Luís Conceição, Marilia Curado

Promoting Quality of Service in Substitution Networks with Controlled Mobility

Abstract
A Substitution Network is a rapidly deployable backup wireless solution to quickly react to network topology changes due to failures or to flash crowd effects on the base network. Unlike other ad hoc and mesh solutions, a substitution network does not attempt to provide new services to customers but rather to restore and maintain at least some of the services available before the failure. Furthermore, a substitution network is not deployed directly for customers but to help the base network to provide services to customers. Therefore, a substitution network is not, by definition, a stand-alone network. In this paper, we describe a quality of service architecture for substitution networks and discuss provisioning, maintenance, as well as adaptation of QoS inside and between the base and the substitution networks.
Tahiry Razafindralambo, Thomas Begin, Marcelo Dias de Amorim, Isabelle Guérin Lassous, Nathalie Mitton, David Simplot-Ryl

Applications and Evaluation

Improving CS-MNS through a Bias Factor: Analysis, Simulation and Implementation

Abstract
A WSN consists of numerous nodes gathering observations and combining these observations. Often, the timing of these observations is of importance when processing sensor data. Thus, a need for clock synchronization arises in WSNs. The CS-MNS algorithm has been proposed to fulfil this role. However, the core algorithm suffers from an initial divergence of clocks. This paper shows, through analysis, that introducing a bias factor in the CS-MNS update law significantly reduces this initial divergence. This is then further confirmed via simulation results, using Matlab, and actual testbed measurements in a testbed deploying motes running TinyOS 2.1. The results show that a designer, having some a-priori knowledge about clock characteristics, can choose a bias that allows the algorithm to speed up the convergence time and greately improve the overall protocol performance. The work also demonstrates that rigorous analysis can be helpful in designing protocols and predicting protocol behaviour, which is then verified through simulation and testbed measurements.
Thomas Kunz, Ereth McKnight-MacNeil

A Methodology to Evaluate Video Streaming Performance in 802.11e Based MANETs

Abstract
Video delivery in mobile ad-hoc networks (MANETs) is an exciting and challenging research field. In the past, most works addressing this issue have resorted to simulation due to the complexity of deploying QoS-enabled testbeds and retrieving video quality indexes in such environments. In this paper we introduce a methodology that allows testing the effectiveness of video codecs in ad-hoc networks. Our methodology relies on a well-defined video quality evaluation framework that is able to combine different video codecs and transmission environments. In particular, our evaluation procedures encompass a preliminary quality assessment, which relies on a point-to-point wireless channel, to establish the general behavior of a video codec under lossy channel conditions, along with tests in static and mobile ad-hoc network environments to determine the impact of factors such as congestion, hop count, and mobility on video quality. To validate our methodology we compare the H.264/AVC and the MPEG-4/ASP video codecs, showing that, in general, the former outperforms the later in terms of video quality, although, for very high loss rates, the differences between both become minimal. Additionally, we show that the number of hops between video transmitter and receiver is a decisive factor affecting performance in the presence of background traffic. Moreover, in mobile scenarios, we find that the impact of congestion and routing delay affects video streaming quality in different manners, being congestion mainly responsible for random losses, while routing delay is usually associated with large loss burst patterns.
Tim Bohrloch, Carlos T. Calafate, Álvaro Torres, Juan-Carlos Cano, Pietro Manzoni

Node Degree Improved Localization Algorithms for Ad-Hoc Networks

Abstract
In this paper we improve the well-known localization algorithms Lateration, Weighted Centroid Localization and Min-Max by using a improved distance estimation. It does not only consider the hop count between two nodes, but also the neighbor degree information. Simulation studies show the performance improvements.
Rico Radeke, Jorge Juan Robles

Using BPEL to Realize Business Processes for an Internet of Things

Abstract
In the vision of an IoT, trillions of tiny devices extend the Internet to the physical world and enable novel applications that have not been possible before. Such applications emerge out of the interaction of these devices with each other and with more powerful server-class computers on the Internet. Programming such applications is challenging due to the massively distributed nature of these networks combined with the challenges of embedded programming. In addition, resource constraints, device heterogeneity, and the integration with the Internet further complicate this situation. In this paper, we present a programming-in-the-large approach for resource-constraint devices such as wireless sensor nodes. Our approach is to model such applications using the Business Process Execution Language (BPEL), which is successfully and widely used in the Internet to model complete applications and business processes. However, BPEL and its associated technologies are too resource-demanding to be directly applied in resource-constraint environments. We therefore use the BPEL model as input to a code generation process that generates custom-tailored, lean code for different target platforms. The resulting code is fully standard-compliant and allows a seamless integration of IoT devices in enterprise IT environments. We present an exhaustive evaluation on real hardware showing the first-rate performance of the approach.
Nils Glombitza, Sebastian Ebers, Dennis Pfisterer, Stefan Fischer

Analytical Considerations

On Complexity of Wireless Gathering Problems on Unit-Disk Graphs

Abstract
We address the problem of efficient gathering of data from a wireless network to a single sink node. Network’s communication and interference pattern are assumed to be captured by the unit-disk model. We consider the objective of minimizing the maximum latency (the time between release and delivery of a packet). We prove that the problem is NP-complete even when all packets are released from the same source node, or at the same time. To our knowledge, these are the first results about the wireless gathering problem in the plane. They can be seen as an extension of recent inapproximability results of Bonifaci et al., which hold in three dimensions.
Nikola Milosavljević

On Cardinality Estimation Protocols for Wireless Sensor Networks

Abstract
In this article we address the problem of estimating a size of wireless sensor networks (WSNs). We restrict our attention to sensors with very limited storage capabilities. The problem arises when sensors have to quickly obtain approximate size of the network to use algorithms which require such information. Another application area is the problem of counting the number of different objects (e.g. people in public bus transportation) and use of such information to optimize the routes and frequency of buses. In this paper we present two-phase probabilistic algorithm based on order statistics and balls-bins model which effectively solves the presented problem.
Jacek Cichoń, Jakub Lemiesz, Marcin Zawada

Maximizing Network Lifetime Online by Localized Probabilistic Load Balancing

Abstract
Network lifetime maximization is a critical problem for long-term data collection in wireless sensor networks. For large-scale networks, distributed and self-adaptive solutions are highly desired. In this paper, we investigate how to optimize the network lifetime by a localized method. Specifically, the network lifetime maximization problem is converted to a localized cost-balancing problem with an appropriately designed local cost function. A distributed algorithm, LocalWiser, which adopts the idea of adaptive probabilistic routing, is proposed to construct a localized and self-adaptive optimal solution to maximize the network lifetime. We analyze LocalWiser in both static and dynamic networks. In static networks, it is formally proved that 1) LocalWiser can reach a stable status; 2) the stable status is optimal for maximizing the network lifetime. In dynamic networks, our extensive simulations illustrate that LocalWiser can converge to the optimal status rapidly for the network topology and flow dynamics.
Yongcai Wang, Yuexuan Wang, Haisheng Tan, Francis C. M. Lau

Time-Varying Graphs and Dynamic Networks

Abstract
The past decade has seen intensive research efforts on highly dynamic wireless and mobile networks (variously called delay-tolerant, disruptive-tolerant, challenged, opportunistic, etc) whose essential feature is a possible absence of end-to-end communication routes at any instant. As part of these efforts, a number of important concepts have been identified, based on new meanings of distance and connectivity. The main contribution of this paper is to review and integrate the collection of these concepts, formalisms, and related results found in the literature into a unified coherent framework, called TVG (for time-varying graphs).Besides this definitional work, we connect the various assumptions through a hierarchy of classes of TVGs defined with respect to properties with algorithmic significance in distributed computing. One of these classes coincides with the family of dynamic graphs over which population protocols are defined. We examine the (strict) inclusion hierarchy among the classes. The paper also provides a quick review of recent stochastic models for dynamic networks that aim to enable analytical investigation of the dynamics.
Arnaud Casteigts, Paola Flocchini, Walter Quattrociocchi, Nicola Santoro

Backmatter

Weitere Informationen

Premium Partner

    Bildnachweise