IoT use cases in the domain of critical infrastructure or disaster prevention, such as flood monitoring, have become increasingly popular. These are often implemented via low power wide area networks (LPWAN). LPWAN outages can prevent the delivery of data in such settings, highlighting the importance of transmission resiliency in IoT applications. In this work, we analyze how short-term LPWAN failures can be avoided by adding a payload history to the current message or using multiple LPWAN communication channels. Long-term failures are investigated with a Monte-Carlo-based simulation with a generalized linear model to understand the factors that affect the mean time to failure (MTTF) in such networks. If multiple different LPWAN interfaces are available in an IoT device, a simple parallel use of all networks increases reliability but consumes too much energy for battery-powered devices and can violate duty cycles. For this reason, we propose the MultiPath Low Power Wide Area Network (MP-LPWAN) protocol for IoT devices, which combines multiple LPWANs to deal with such failures. MP-LPWAN improves overall IoT system performance by dynamically adjusting transmission parameters and interface priority to adapt to changing network conditions. We implemented MP-LPWAN on a dual-LPWAN testbed and empirically validated its performance.

Wireless connectivity in vineyards has substantial potential to redefine the wine business using digitalization. To this end, this paper presents a measurement study of 5G performance in the 3.7-3.8 GHz frequency band in several steep vineyards in Germany. The steep terrain causes unique challenges for 5G deployment. The study investigates private nomadic 5G networks that are explicitly provided temporarily. It uses continuous wave and 5G network measurements to examine uplink signal quality, achievable data rates, and coverage area. The results indicate the effects of vineyard topography and settings on 5G efficiency.

We study wireless network graphs where nodes are spatially distributed according to a homogeneous Poisson point process and connected based on the log-normal shadowing model. Well-known theoretical upper and lower bounds on the critical node density for percolation are investigated and generalized. We show empirically that the known lower and especially upper bound are still very conservative in the log-normal shadowing setting. We derive an expression, which provably lies below the known upper bound. Moreover, we study log-normal shadowing modeled graphs with a cutoff distance, i.e., all neighbors beyond a certain distance are discarded. We show how to find a small distance such that the graph still percolates. We adapt the known upper bound and as well our derived expression to that cutoff distance. We compare our expression with that lower and upper bound empirically for both with and without cutoff distances, and observe that our expression comes much closer to the actual transition point.

We study the success rate of detecting the ordering of a line topology under correlated shadowing and fast fading for two methods from the literature which rely on signal strength measurements only. First we propose a model extension of the so far only existing spatially correlated model of log-normal shadowing for comparing two arbitrary links, which enables us to explore highly correlated links as well. For one method, we then formulate the detection probability in this correlation model when repeated nearby measurements are included, and study how far averaging can be used to mitigate small scale fading in the problem setting. Finally, for uncorrelated shadowing we observe an interesting connection between the detection probabilities with and without fading.

With 5G technology and its application in industry, the demand for wireless communication is increasing and so is the need for information about the wireless channel. Thus, accurate propagation channel models are required. For this purpose, we analyze our recently measured and published Power Delay Profiles (PDPs) in industrial scenarios using the Saleh Valenzuela (SV) model, compare the results with the results of other scenarios and propose an improved model. Further, we discuss the relation of path loss models, PDPs and the SV-model.

Local algorithms and other wireless network protocols require the underlying network graph to have specific structural properties to guarantee correctness. Two of these properties are connectivity and absence of intersecting links. Assuring only one of these properties is very often possible, either by considering a dense graph, which is very likely connected, but contains many intersections or a sparse graph which contains only few intersections, but is split up into many components. The task is therefore to choose the edges in a given graph in such a way that the intersections are removed while connectivity is preserved. Based on a Poisson point process and the log-normal shadowing model, we analyse the frequency of connected graphs without intersecting links. To further support such graph structure, we also restrict the maximal length of the edges in the network graph. By simulation we observe conditions how the maximal length of the edges in a graph should be chosen to assure the existence of a large component with few intersections.

Due to an increasing need for mobility on the factory floor, future industrial applications will often use wireless technologies like 5G. The necessarily high reliability not only needs to be designed into the wireless communication technology, but also has to be experimentally verified. Events that degrade the reliability of highly available systems are rare. Additionally, correlation is inherent to wireless channels and an analysis method that is able to cope with those two challenges is needed. Thus, in this work our aim is to provide such a method. We evaluate the practical usage of the limited relative error (LRE) algorithm and discuss how to obtain confidence intervals based on it. Thereby, the standard normal distribution is approximated, which leads to biased results. We illustrate this by the usage of the Berry-Esseen theorem. To overcome the bias the LRE algorithm is enhanced with moving block bootstrapping (MBB). We call this new method bootstrapping LRE algorithm. We use measurement data from a 5G network for our analysis. Further, the usability of the 5G network for communication purposes based on the black channel paradigm is evaluated with the 5G measurement data and its statistical analysis. Thereby, the performance parameters of cycle time and reliability of the black channel in 5G are determined.

Connected plane graphs enable many local algorithmic solutions for data communication, task coordination and network maintenance in wireless sensor networks, sensor-actuator networks and distributed robotics. We study construction of such graphs by removing edges from a given network graph. We assume redundancy and coexistence, a graph structure which holds in realistic wireless network models with high probability and which assures that a connected plane graph can always be constructed with local edge removal rules. We present a local algorithm to construct such a connected plane graph. We prove algorithm correctness under redundancy and coexistence assumption. Furthermore, we discuss how far redundancy and coexistence could be weakened while still assuring correctness of the algorithm.

We investigate the problem of determining which node is in the middle of an aligned sequence of an odd number of wireless network nodes. The studied solution applies the method of least squares on signal strength measurements. These measurements vary due to log-normal shadowing. We consider the uncorrelated and as well the correlated case. Our analysis is focused on the three node case. We derive an integral expression for calculating the success rate of the least squares approach. The analysis is applicable on any well formed covariance matrices. We consider two different analytically derived matrices based on two different known spatial correlation models. We study the correlation models quantitatively in view of the problem and conclude that one of the models is not applicable for a rigorous mathematical treatment of the studied problem. The claim is complemented by a numerical comparison of the two models. Based on the remaining correlation model and also for the uncorrelated case, we numerically examine the success rate of the method of least squares in terms of path loss and shadowing variance and to what extend spatial correlation improves the success rate.

Wireless communication continuously gains in importance in the context of industrial automation due to its role as an enabling factor for flexibility. The number of mobile, wirelessly communicating devices in modern production facilities steadily rises. Knowledge about the signal propagation is central to the planning and maintenance of these wireless networks. Precise models enable users to supply sufficient communication capabilities to the factory of the future.Measurements of Power Delay Profiles (PDPs) were performed at the frequencies of 2.1,2.6,3.8 and 5.1GHz for three different scenarios in a modern and running production facility. The results are analyzed by means of multi-path components, delay spread and path loss. The results are compared to previous measurements. Thereby, further insights in propagation conditions in industrial scenarios are gained.

We study a finite and fixed relative formation of possibly mobile wireless networked nodes. The nodes apply average consensus to agree on a common value like the formation's center. We assume framed slotted ALOHA based broadcast communication. Our work has two contributions. First, we analyze outage correlation of random media access in wireless networks under Nakagami fading. Second, the correlation terms are applied to the so called L2-joint spectral and numerical radii to analyze convergence speed of average consensus under wireless broadcast communication. This yields a unified framework for studying joint optimization of control and network parameters for consensus subject to message losses in wireless communications. Exemplary we show in this work how far outage correlation in wireless broadcast communication positively affects convergence speed of average consensus compared to consensus in the uncorrelated case.

We consider distributed first order average consensus in wireless networked systems. Two optimization parameters (discrete gain and beaconing frequency) are considered in a mathematical framework. The framework is derived by extending the L2 joint spectral radius to a joint numerical radius and by deriving a closed form expression on beaconing success under Rayleigh fading. With our theoretical insights we derive a two-step heuristic which optimizes both parameters and requires significantly less information about the network compared to a global optimization. The heuristic is evaluated numerically and compared to the optimal solution. The simulated cases show that our heuristic can get close to the optimal solution.

Recent studies have identified redundancy and coexistence as a supporting graph structure for building connected intersection free planar drawings in wireless network graphs. Empirical evidence suggests that under certain conditions these properties can be assumed to hold with high probability. In this paper we advance insight on these probabilities with a rigorous stochastic treatment studying randomly generated network graphs pertaining to the log-normal shadowing model. We derive nested integral expressions to compute probabilities of redundancy and coexistence numerically under the standard uncorrelated log-normal shadowing model. For a recent model extension including correlation among network links our findings provide a means for efficient stochastic simulation of these probabilities. We illustrate numerical and simulation application of the derived formulae with a comprehensive parameter study for redundancy and coexistence under correlated and uncorrelated log-normal shadowing modeled randomly generated graphs. We also demonstrate how far support for these properties can be improved by artificially cutting communication distance while keeping the network well connected in terms of percolation bounds.

Upcoming connected vehicle applications will rely on large amounts of data to provide safety or comfort functionalities. Delivering such data, reliably on time is a challenge due to the inherent mobility in connected vehicle environments. The Information-Centric Networking (ICN) paradigm is a promising candidate to tackle the challenges of such environments. Addressing data by name instead of location, and the resulting capabilities such as in-network caching, make it a good fit for scenarios with a high degree of mobility. In this paper, we propose and evaluate an adaptive decentralized prefetching mechanism for ICNs in vehicular scenarios. By proactively placing relevant data in caches near to consumers, the overall service quality and delivery rate in the network is improved. The algorithm is evaluated using simulations based on a real V2X highway testbed in Austria.

Beaconless topology control algorithms reduce message overhead of local topology constructions compared to conventional (beacon-based) local approaches by avoiding maintenance of neighborhood tables. Moreover, they construct a node's adjacency in the desired topology on demand and only locally, i.e., Do not require network-wide operation. In this work, we present a beaconless topology control algorithm which enables a node to reactively construct a planar backbone graph in its geographic vicinity. This backbone graph is a constant node degree, constant stretch hop-spanner for the input quasi unit disk graph. Our contribution is novel, since all known algorithms with comparable outputs require maintenance of neighborhood tables and are designed for network-wide operation. In addition, it is of significance since there are several applications of it, e.g., In the context of geographic unicast and multicast routing with guaranteed delivery.

A wireless sensor network is of no use if it does not support proper communication among the sensor nodes. It is thus important to deploy sensor nodes such that high quality links are available for any communication path required during sensor network operation. In this work we describe a deployment algorithm which takes the link qualities between neighboring nodes of already deployed nodes into account to decide the right position for the next node to be deployed. We compare our approach with the well known regular triangle tessellation deployment. Simulation results show that when both approaches cover the same area, in our approach sink based and unicast communication works visibly better in terms of bit error rate.

Within reactive topology control, a node determines its adjacent edges of a network subgraph without prior knowledge of its neighborhood. The goal is to construct a local view on a topology which provides certain desired properties such as planarity. During algorithm execution, a node, in general, is not allowed to determine all its neighbors of the network graph. There are well-known reactive algorithms for computing planar subgraphs. However, the subgraphs obtained do not have constant Euclidean spanning ratio. This means that routing along these subgraphs may result in potentially long detours. So far, it has been unknown if planar spanners can be constructed reactively. In this work, we show that at least under the unit disk network model, this is indeed possible, by proposing an algorithm for reactive construction of the partial Delaunay triangulation, which recently turned out to be a spanner. Furthermore, we show that our algorithm is message-optimal as a node will only exchange messages with nodes that are also neighbors in the spanner. The algorithm's presentation is complemented by a rigorous proof of correctness.

The rotational sweep algorithm (RS) solves the beaconless recovery problem in local minimum situations, which occur during Greedy routing. It routes a data packet around a void region using only two additional messages per hop, while guaranteeing packet delivery. In this context we present three related contributions: (1) When a sweep circle (SC) is used for RS, the resulting path coincides with the corresponding partial Delaunay triangulation Face traversal. Hence, SC traversals use edges of an Euclidean spanner and are therefore potentially very short. (2) We contrast this result by giving examples where RS performs particularly bad, when considering the Hop instead of the Euclidean metric. (3) To cope with this discrepancy, we devise a beaconless algorithm that helps to cut short in such situations and thereby helps to avoid unnecessary routing steps.

Assume a forwarding cost function which depends on the sender receiver separation, and assume further that noncooperative relaying is applied. What is the minimum total forwarding cost required for sending a message from source to one or more destinations when multicasting along optimal placed relaying nodes is applied? In this paper, I define and analyze cost function properties from which I derive general lower bound expressions on multicasting costs. I consider an MAC layer model which does not exploit the broadcast property of wireless communication and an MAC layer model which exploits it. For specific cost functions, I show further that in case of optimal relay positions, multicasts can be constructed whose cost always stays below the derived lower bound expression plus an additive constant depending on the number of destinations. For both, lower and upper bounds, I define a general procedure to check if-and if yes how-my findings can be used to derive the specific lower and upper bound expressions for a given cost function. I explain the procedure with three cost function examples: the euclidean distance, energy cost function, and the expected number of retransmissions under Rayleigh fading.

Self-deployment describes the task of spreading an autonomously moving swarm of mobile robots over a given area. All these robots have to move to locations such that the set of robot locations satisfies a desired property. In this work, we describe a fully distributed deployment algorithm executed locally at each robot. The approach requires only few local information per node: the distances and very coarse angular information to immediate neighbors. It has been developed for use on small robots with very restricted memory, communication, and processing capabilities. In this paper, we specify the algorithm and evaluate it in an empirical study. This includes both simulation studies and real test bed experiments. For the test bed, we consider two different platforms: ground moving robots and aerial robots. The results of our simulations show that our local deployment rules achieve almost globally optimal results. The test bed study supports and substantiates our simulation study and shows as a proof of concept that our algorithm works both with real ground based and aerial based robot swarms.

Partial Delaunay triangulation (PDT) is a well-known subgraph construction that has already been used for years in the context of geographic routing and topology control. So far, it has been unknown if partial Delaunay triangulation is a network spanner. Network spanners are those subgraph constructions which maintain the length of the shortest path between any pair of nodes up to a constant factor. This factor is also referred to as the spanning ratio. In this work we prove that partial Delaunay triangulation is a network spanner for unit disk graphs. Furthermore, from our proof follows immediately that the spanning ratio of PDT is less than or equal to 1+√5/4 π2.

Localized geographic routing schemes operating on planar graphs promise scalability for use within large multihop wireless networks. Existing schemes base routing path construction on faces defined by the planar graph. Once running on a particular planar graph, none of the existing schemes is flexible enough to adapt the sequence of faces visited by the constructed path. Thus, real-world constraints such as network congestion, limited node energy levels, or non-cooperation of nodes might severely impact the performance and the robustness of existing planar graph routing variants. To address this problem, we extend planar graph routing with one further degree of freedom: control over the sequence of visited faces. Basically, our face routing extension now follows a sequence of faces intersected by any curve we can freely adjust. We investigate basic schemes for choosing curves dealing with imperfections in the network, and derive algorithms for routing and forwarding along these curves. We analytically prove that our scheme is loop free and allows for guaranteed delivery in arbitrary planar connected graphs. We implement curve-based routing and show its feasibility by means of a simulation study. As a proof-of-concept scenario, we investigate the case of non-cooperating nodes. Our results show that curve-based routing is able to sustain the delivery of packets where traditional schemes fail.

Scalability of routing algorithms is a critical issue in large multihop wireless networks. In this sense, approaches like localized geographic routing are very promising. Existing schemes base routing path construction on faces defined by the planar graph of the network. Once running on a particular planar graph, none of the existing schemes is flexible enough to adapt the sequence of faces visited by the constructed path. To address this problem, we extend planar graph routing with one further degree of freedom: control over the sequence of visited faces. Basically, our face routing extension now follows a sequence of faces intersected by any curve we can freely adjust. We motivate our work by discussing application scenarios that benefit from our scheme and suggest basic mechanisms for choosing appropriate curves. We further present preliminary results from an implementation of our curve-based routing scheme.

Assume a forwarding cost function which depends on the sender receiver separation, and assume further that non cooperative relaying is applied. What is the minimum total forwarding cost required for sending a message from source to destinations when multicasting along optimal placed relaying nodes is applied? In my last year's WoWMoM publication, this question was already answered for a specific energy cost function. In this work I generalize my previous findings for generalized classes of distance dependent forwarding cost functions. I define cost function properties from which I derive generalized lower bounds on multicasting costs. I consider again, a MAC layer model which does not exploit the broadcast property of wireless communication and a MAC layer model which exploits it. This work also generalizes the upper bound result from. For specific cost functions, I show that in case of optimal relay positions, multicasts can be constructed whose cost always stays below of one of the derived lower bound expressions plus an additive constant depending on the number of destinations. For both, lower and upper bounds, I define a general procedure to check if and if yes how my findings can be used to derive the specific lower and upper bound expressions for a given cost function. I explain the procedure with two cost function examples, the Euclidean distance and the energy cost function used in. For the latter, the bounds derived in follow immediately as corollaries in this work.

Planar graph routing works provably correct if the underlying network graph is connected and planar. Typically, wireless networks modeled as 2D graphs, are not planar and planar graph routing applied on such unprocessed network graphs may fail. Planarizing a given connected graph by removing intersecting links might be impossible if the outcome still needs to be a connected subgraph. It becomes even more difficult with distributed planarization techniques, where each node is allowed to use only the information about its local neighborhood. Furthermore, it is getting complicated if the nodes' assigned positions do not reflect the exact physical location. With or without exact location information, the outcome might be disconnected, nonplanar, or both of it. With all these unsolvable problems, the question arises how to apply planar graph routing in a realistic network setting? Fortunately, wireless network graphs bear one property which distinguishes them from arbitrary graphs: due to limited communication range, network links cannot become arbitrarily long. In this work we exploit this locality property to build a new localized planarization algorithm, which is location fault tolerant and which produces planar connected graphs in most cases in realistic wireless models. We evaluate our algorithm using the Log Normal Shadowing model and show that our algorithm always produces planar connected graphs in all simulations even when large location errors are present.

We consider sensor self-deployment problem, constructing FOCUSED coverage (F-coverage) around a Point of Interest (POI), with novel evaluation metric, coverage radius. We propose to deploy sensors in polygon layers over a locally computable equilateral triangle tessellation (TT) for optimal F-coverage formation, and introduce two types of deployment polygon, H-polygon and C-polygon. We propose two strictly localized solution algorithms, Greedy Advance (GA), and Greedy-Rotation-Greedy (GRG). The two algorithms drive sensors to move along the TT graph to surround POI. In GA, nodes greedily proceed as close to POI as they can; in GRG, when their greedy advance is blocked, nodes rotate around POI along locally computed H- or C-polygon to a vertex where greedy advance can resume. We prove that they both yield a connected network with maximized hole-free area coverage. To our knowledge, they are the first localized sensor self-deployment algorithms that provide such coverage guarantee. We further analyze their coverage radius property. Our study shows that GRG guarantees optimal or near optimal coverage radius. Through extensive simulation we as well evaluate their performance on convergence time, energy consumption, and node collision.

Present broadcast approaches for wireless multihop networks distribute packets quickly to all nodes (i.e., with low latency) by constructing small broadcast trees, thereby reducing the number of forwarding transmissions. While these trees are sufficient in non-fading environments, we show that they have a low delivery rate under fading. As a solution, we (1) incorporate the Rayleigh fading model directly into tree construction to re-obtain complete distribution with high probability. To still achieve low latency at the same time, we combine transmissions at individual nodes to exploit cooperation diversity. Since in broadcasts, a packet has to be retransmitted by nodes along the tree anyway, we do not have to pay the multiplexing loss which hampers cooperation diversity in the unicast case. Thus, we (2) additionally exploit cooperation diversity during tree construction to gain improved reliability while still keeping the size of the tree low. This enables us to significantly decrease the time for broadcasts while still distributing packets to all nodes under fading with high probability. To justify our heuristic approach, we (3) show that finding minimum latency cooperative broadcasts is NP-complete.

I consider the known localized multicast protocol MSTEAM and derive the energy consumed by the multicast tree constructed by this protocol in the best case. Moreover, I show that the length of multicast links connecting into a multicast branch can not be bounded from above. For typical wireless networks where links have a limited communication range, however, I can show that asymptotically the relation between the derived best case energy consumption of MSTEAM and a known lower bound on multicast energy consumption is limited by a factor of 2.

Given a source node and a set of k destination nodes, what is the minimum total energy required for sending a message from source to destinations when multicasting along optimal placed relaying nodes is applied? In this work I will answer this question under the assumption that non-cooperative relaying is applied and that communication over a distance d requires energy proportional to dα+ β for some α > 1 and β > 0. I derive lower bound expressions for a MAC layer model which does not exploit the broadcast property of wireless communication and for a MAC layer model which exploits it. I show further, in case of optimal relay positions, how multicasts can be constructed whose energy consumption always stays below the derived lower bound plus an additive constant expression depending on α, β, k. The usefulness of the bound derived in this work is exemplified with three different example applications.

In this paper, we provide a thorough theoretical study on delivery guarantees, loop-free operation, and worst-case behavior of face and combined greedy-face routing. We show that under specific planar topology control schemes, recovery from a greedy routing failure is always possible without changing between any adjacent faces. Guaranteed delivery then follows from guaranteed recovery while traversing the very first face. In arbitrary planar graphs, however, a proper face selection mechanism is of importance since recovery from a greedy routing failure may require visiting a sequence of faces before greedy routing can be restarted again. We provide complete and formal proofs that several proposed face routing and combined greedy-face routing schemes guarantee message delivery in specific planar graph classes or even in arbitrary planar graphs. We also discuss the reasons why other methods fail to deliver a message or even end up in a loop. In addition, we investigate the behavior of face routing in arbitrary not necessarily planar networks and show, while delivery guarantees cannot be supported in such a general case, most face and combined greedy-face routing variants support at least loop-free operation. For those variants, we derive worst-case upper bounds on the number of forwarding steps.

Focused coverage is defined as the coverage of a wireless sensor network surrounding a point of interest (POI), and is measured by coverage radius, i.e., minimum distance from POI to uncovered areas. Sensor self-deployment algorithm GRG is designed for autonomous focused coverage formation. It however does not always produce optimal (i.e., maximized) coverage radius. In this paper, we propose optimized GRG, referred to as OGRG, for guaranteed coverage radius maximization, and evaluate its performance in comparison with GRG.

We pinpoint a new sensor self-deployment problem, constructing focused coverage around a point of interest (POI), and introduce an evaluation metric, coverage radius. We propose two solutions, greedy advance (GA) and greedy-rotation-greedy (GRG), which are to our knowledge the first sensor self-deployment algorithms that operate in a purely localized manner and yet provide coverage guarantee. The two algorithms drive sensors to move along a locally-computed equilateral triangle tessellation (TT) to surround POI. In GA, nodes greedily proceed as close to POI as they can; in GRG, when their greedy advance is blocked, nodes rotate around POI to a TT vertex where greedy advance can resume. They both yield a connected network of TT layout with hole-free coverage; GRG furthermore assures a hexagon coverage shape centered at POI. We prove their correctness and analyze their coverage radius property. Our study shows that GRG guarantees optimal hexagonal coverage radius and near optimal circular coverage radius. Through extensive simulation we as well evaluate their performance on convergence time, energy consumption, and node collision.

We present a localized geographic multicast scheme, MSTEAM, based on the construction of local minimum spanning trees (MSTs), that requires information only on 1-hop neighbors. A message replication occurs when the MST spanning the current node and the set of destinations has multiple edges originated at the current node. Destinations spanned by these edges are grouped together, and for each of these subsets the best neighbor is selected as the next hop. This selection is based on a cost over progress metric, where the progress is approximated by subtracting the weight of the MST over a given neighbor and the subset of destinations to the weight of the MST over the current node and the subset of destinations. Since such greedy scheme may lead the message to a void area (i.e., no neighbor providing positive progress), we propose a new multicast generalization of the well-known face recovery mechanism. We provide a theoretical analysis proving that MSTEAM is loop-free, and achieves delivery of the multicast message as long as a path to the destinations exists. Our results demonstrate that MSTEAM outperforms the best existing localized multicast scheme, and is almost as efficient as a centralized scheme in high densities.

It was recently reported that all known face and combined greedy-face routing variants cannot guarantee message delivery in arbitrary undirected planar graphs. The purpose of this article is to clarify that this is not the truth in general. We show that specifically in relative neighborhood and Gabriel graphs recovery from a greedy routing failure is always possible without changing between any adjacent faces. Guaranteed delivery then follows from guaranteed recovery while traversing the very first face. In arbitrary graphs, however, a proper face selection mechanism is of importance since recovery from a greedy routing failure may require visiting a sequence of faces before greedy routing can be restarted again. A prominent approach is to visit a sequence of faces which are intersected by the line connecting the source and destination node. Whenever encountering an edge which is intersecting with this line, the critical part is to decide if face traversal has to change to the next adjacent one or not. Failures may occur from incorporating face routing procedures that force to change the traversed face at each intersection. Recently observed routing failures which were produced by the GPSR protocol in arbitrary planar graphs result from incorporating such a face routing variant. They cannot be constructed by the well known GFG algorithm which does not force changing the face anytime. Beside methods which visit the faces intersected by the source destination line, we discuss face routing variants which simply restart face routing whenever the next face has to be explored. We give the first complete and formal proofs that several proposed face routing, and combined greedyface routing schemes do guarantee delivery in specific graph classes or even any arbitrary planar graphs. We also discuss the reasons why other methods may fail to deliver a message or even end up in a loop.

The relationship between coverage and connectivity in sensor networks has been investigated in recent research treating both network parameters in a unified framework. It is known that networks covering a convex area are connected if the communication range of each node is at least twice a unique sensing range used by each node. Furthermore, geographic greedy routing is a viable and effective approach providing guaranteed delivery for this special network class. In this work, we will show that the result about network connectivity does not suffer from generalizing the concept of sensing coverage to arbitrary network deployment regions. However, dropping the assumption that the monitored area is convex requires the application of greedy recovery strategies like traversing a locally extracted planar subgraph. This work investigates a recently proposed planar graph routing variant and introduces a slight but effective simplification. Both methods perform message forwarding along the edges of a virtual overlay graph instead of using wireless links for planar graph construction directly. In general, there exist connected network configurations where both routing variants may fail. However, we will prove three theoretical bounds which are a sufficient condition for guaranteed delivery of these routing strategies applied in specific classes of sensing covered networks. By simulation results, we show that geographical cluster-based routing outperforms existing related geographical routing variants based on one-hop neighbor information. Furthermore, simulations performed show that geographical cluster-based routing achieves a comparable performance compared to variants based on two-hop neighbor information, while maintaining the routing topology consumes a significantly reduced amount of communication resources

Exploring the faces of a planar graph is a prominent approach to recover from routing failures which may occur during geographic greedy forwarding heuristics applied in multihop ad hoc networks. A recently studied variant of planar graph based recovery, termed geographical cluster based routing, performs face exploration along the edges of an overlay graph instead of using the network links directly. For this routing variant it has been observed, that there exist node placements which result in a connected physical network while any planar overlay graph which is constructed by simply removing edges from that graph is disconnected. This article for the first time describes a technique to locally construct an overlay graph which is both planar and connected. In addition we present a generic routing framework which is based on the overlay graph introduced in this work. In contrast to existing planar graph routing techniques the described framework allows major flexibility regarding the possible next hop candidate nodes. The framework is envisioned to serve as an interesting starting point for future performance measurements of a multitude of its possible instances