Ad-hoc, Mobile, and Wireless Networks

Topology control algorithms (TCAs) are used in wireless sensor networks to reduce interference by carefully choosing communication links. Since the quality of the wireless channel is subject to fluctuations over time TCAs must repeatedly recompute the topology. TCAs ensure quick adjustment to new or deteriorating links while preventing precipitant changes due to transient faults. This paper contributes a novel dynamic TCA that provides a compromise between agility and stability, and constructs connected topologies for low latency routing. Furthermore, it enforces memory restrictions and is of high practical relevance for real sensor network hardware.

Geographic routing is an attractive routing strategy in wireless sensor networks. It works well in dense networks, but it may suffer from the void problem. For this purpose, a recovery step is required to guarantee packet delivery. Face routing has widely been used as a recovery strategy since proved to guarantee delivery. However, it relies on a planar graph not always achievable in realistic wireless networks and may generate long paths. In this paper, we propose GRACO, a new geographic routing algorithm that combines a greedy forwarding and a recovery strategy based on swarm intelligence. During recovery, ant packets search for alternative paths and drop pheromone trails to guide next packets within the network. GRACO avoids holes and produces near optimal paths. Simulation results demonstrate that GRACO leads to a significant improvement of routing performance and scalability when compared to the literature algorithms.

We consider path multicoloring problems, in which one is given a collection of paths defined on a graph and is asked to color some or all of them so as to optimize certain objective functions. Typical objectives are: (a) the minimization of the average, over all edges, of the maximum-multiplicity color when the number of colors is given (MinAvgMult-PMC), (b) the minimization of the number of colors when the maximum multiplicity for each edge is given (Min-PMC), or (c) the maximization of the number of colored paths when both the number of colors and a maximum multiplicity constraint for each edge are given (Max-PMC). Such problems also capture edge multicoloring variants (such as MinAvgMult-EMC, Min-EMC, and MaxEMC) as special cases and find numerous applications in resource allocation, most notably in optical and wireless networks, and in communication task scheduling.

Our contribution is two-fold: On the one hand, we give an exact polynomial-time algorithm for Min-PMC on spider networks with even admissible color multiplicities on each edge. On the other hand, we present an approximation algorithm for MinAvgMult-PMC in star networks, with a ratio strictly better than 2; our algorithm uses an appropriate path orientation. We also show that any algorithm which is based on path orientation cannot achieve an approximation ratio better than \(\frac{7}{6}\). Our results apply to the corresponding edge multicoloring problems as well.

We exploit the relatively predictable nature of wireless sensor networks that exhibit fixed topology and fixed application demands for off-line construction of TDMA schedules. In particular, we are able to account for the duty cycling (DC) behavior of the nodes, and hence for the time-varying properties of the underlying communication graph. The novelty lies in pursuing an alternative to a genuinely algorithmic, but notoriously computationally hard, scheduling approach. Specifically, we leverage the fact that the system is virtually a deterministic one and use a pre-simulation technique, detecting when the system has reached steady state, past which point the behavior is essentially periodic. We extract from the pre-simulation a periodic schedule template which can be subsequently used, with minor adjustments, as the TDMA schedule of all nodes in the network. We study the properties of the technique and analyze its performance in example duty-cycled networks.

Network churn is one of the primary reasons for network topology evolution, creating a dynamic environment that all designed and developed mechanisms have to cope with. In this work, we focus on studying the impact of network evolution on the resource allocation mechanisms in wireless multihop networks, and thus set the scene for more pragmatic network optimization. More specifically, we study the impact of topology evolution in the form of node and edge churn on the Network Utility Maximization (NUM) mechanism, where the latter is employed as a form of intelligent resource allocation framework and implementation. Our study in this paper serves as a stepping stone for a more realistic consideration of cross-layer design, capable of coping with the dynamic nature of the evolutionary changes that take place in each network inevitably. This work aspires to stimulate the interest and further research on improving and developing network optimization and control mechanisms under more realistic operational conditions.

We assume a D2D overlay enabled cellular network where two types of users are considered. D2D enabled users may communicate either via the Base Station (BS) or directly with each other, while cellular users can communicate only via the BS. In this type of network resource blocks (RBs) are split into two different categories, applicable for D2D access and cellular access respectively. We first introduce a blocking queuing model that can be used to effectively represent the process of allocation of resources to the different types of users. Subsequently we address the problem of fair resource assignment by formulating it as a multi-objective optimization problem of minimizing the maximum blocking probability experienced by any type of user in the system. We show that the optimal RBs assignment policy is of threshold type, while an adaptive algorithm to estimate the required parameters of the optimal policy is presented. Through modeling and simulation the achievable system capacity is evaluated and the superiority of the proposed optimal policy is demonstrated.

Many algorithms and applications use GPS as standard for outdoor usage. But they cannot perform correctly for shaded areas such as tunnels, canyons, and near large buildings. Other localization algorithms and reference information are then required for aiding GPS. In this paper, we propose an architecture for tracking of a mobile node considering: (i) a main node tracking system that is feasible enough for non-shaded areas and (ii) a subsystem that supports the location during shaded areas. In (i), we propose the Probabilistic Random Mobility Model for simulating paths based on Center Turning Radius (CTR) which is both an inherent vehicular feature and a vehicular displacement restriction. In (ii), Particle Filtering approach is used because it is able to handle location uncertainty during shaded areas and improves over time. The status and CTR of a mobile node are used to reduce and adapt the space of uncertainty where particles are drawn. Finally, a priority-selective control based on the suppress principle is employed for choosing (ii) during shaded areas.

Train localisation is important to railway safety. Using Wireless Sensor Networks (WSNs) in train localisation is a robust and cost effective way. A WSN-based train localisation system contains anchor nodes that are deployed along railway tracks and have known geographic coordinates. However, anchor nodes along the railway tracks are prone to hardware and software deterioration such as battery outage, thermal effects, and dislocation. Such problems have negative impacts on the accuracy of WSN-based localisation systems. In order to reduce these negative impacts, this paper proposes a novel Consensus-based Anchor-node Management Scheme (CAMS) for WSN-based localisation systems. CAMS can assist WSN-based localisation systems to exclude the input from the faulty anchor nodes and eliminate them from the system.

The nodes update each other about their opinions on other neighbours. Each node uses the opinions to develop consensus and mark faulty nodes. It can also report the system information such as signal path loss. Moreover, in CAMS, anchor nodes can be re-calibrated to verify their geographic coordinates. In summary, CAMS plays a vital role in the life of the WSN-based localisation systems and in their ability to accurately estimate the train location. We have evaluated CAMS with simulations and analysed its performance based on real data collected from field experiments. To the best of our knowledge, CAMS is the first protocol that uses consensus-based approach to manage anchor nodes in train localisation.

The support of context aware Vertical Handover Operations (VHO) for optimally exploiting multiple connectivity opportunities is addressed by considering a typical generic architecture, reminiscent of relevant frameworks, such as IEEE 802.21. The paper develops a novel modeling methodology that can capture concisely, but also effectively, all important factors that have an impact on the system’s performance, including the intensity of handover requests, network topological and availability characteristics, various sources of signaling overhead and the congestion points imposed by the architectural components. The model is validated by simulation and is employed for investigating the impact of the various parameters on the mean delay required for the VHO preparation phase. The principles of the proposed modeling methodology could be exploited for the future study of additional more decentralized solutions, towards addressing distributed mobility management scenarios, including ad-hoc and mesh network topologies.

In wireless networks, radiomap (also known as fingerprinting) based locating techniques are commonly used to cope the diverse fading signatures of radio signal, in which probabilistic or static radiomaps are trained in offline phase. A challenging problem of radiomap locating is that the radiomap can be outdated when environments change. Reconstruction of radiomap is time consuming and laborious. In this paper, we exploit the inter-beacon radio signal strength (RSS) to construct adaptive radiomap (AdaMap) by an online self-adjusted linear regression model. The distinct feature of AdaMap is that not only the radio signatures at the training locations vary with the online inter-beacon RSS measurements, but also the coefficients of the model are self-adjusted when the environments change significantly, so that AdaMap is highly adaptive to the environment changes. The proposed schemes are evaluated by extensive simulations, with comparisons to the state of art of the radiomap wireless localization methods. The results showed that AdaMap presented dramatical advantages in preserving positioning accuracy when the environments changed over time.

Consider \(n\) sensors placed randomly and independently with the uniform distribution in a unit square. The sensors have identical sensing range equal to \(r\), for some \(r >0\). We are interested in moving the sensors from their initial positions to new positions so as to ensure that the unit square is completely covered, i.e., every point in the square is within the range of a sensor. If the \(i\)-th sensor is displaced a distance \(d_i\), what is a displacement of minimum cost? As cost measure for the displacement of the team of sensors we consider the \(a\)-total movement defined as the sum \(M_a:= \sum _{i=1}^n d_i^a\), for some constant \(a>0\). We assume that \(r\) and \(n\) are chosen so as to allow full coverage of the square and \(0 < a \le 4\). The main contribution of the paper is to show the existence of a tradeoff between the square sensing radius and \(a\)-total movement and can be summarized as follows:

Therefore this sharp decrease from \(O(n^{1- a/4})\) to \(O(n^{1-a/2} (\ln n)^{a/4} )\) in the \(a\)-total movement of the sensors to attain complete coverage of the square indicates the presence of an interesting threshold on the square sensing radius when it increases from \(\frac{1}{2\sqrt{n}}\) to \( \frac{2\sqrt{3}}{\sqrt{n}}\). In addition, we simulate our algorithms above and discuss the results of our simulations.

Wireless sensor and robot networks (WSRNs) are an integration of wireless sensor network (WSNs) and multi-robot systems. They are comprised of networked sensor and mobile robots that communicate via wireless links to perform distributed sensing and actuation tasks in a region of interest (ROI). In addition to gathering and reporting data, sensors may also report failures of neighboring sensors or lack of coverage in certain neighbourhood to a nearby mobile robot. We propose a solution, called Election-Based Deployment (EBD), for simultaneous sensor deployment and coverage maintenance in multi-robot scenario in failure-prone environment. To the best of our knowledge, it is the first carrier-based localized algorithm that is able to achieve 100 % coverage in a ROI of any shape with multiple robots in failure-prone environment since it combines both sensor deployment and coverage maintenance process. We can observe from the simulation results that EBD outperforms the existing algorithms while reducing the communication overhead to a great extent.

Consider an equilateral triangle or square with sides of length \(1\). A number of robots starting at the same location on the perimeter or in the interior of the triangle or square are required to evacuate from an exit which is located at an unknown location on its perimeter. At any time the robots can move at identical speed equal to \(1\), and they can cooperate by communicating with each other wirelessly. Thus, if a robot finds the exit it can broadcast “exit found” to the remaining robots which then move in a straight line segment towards the exit to evacuate. Our task is to design robot trajectories that minimize the evacuation time of the robots, i.e., the time the last robot evacuates from the exit. Designing such optimal algorithms turns out to be a very demanding problem and even the case of equilateral triangles turns out to be challenging.

We design optimal evacuation trajectories (algorithms) for two robots in the case of equilateral triangles for any starting position and for squares for starting positions on the perimeter. It is shown that for an equilateral triangle, three or more robots starting on the perimeter cannot achieve better evacuation time than two robots, while there exist interior starting points from which three robots evacuate faster than two robots. For the square, three or more robots starting at one of the corners cannot achieve better evacuation time than two robots, but there exist points on the perimeter of the square such that three robots starting from such a point evacuate faster than two robots starting from this same point. In addition, in either the equilateral triangle or the square it can be shown that a simple algorithm is asymptotically optimal (in the number \(k\) of robots, as \(k \rightarrow \infty \)), provided that the robots start at the centre of the corresponding domain.

Rendezvous is concerned with enabling \(k \ge 2\) mobile agents to move within an underlying domain so that they meet, i.e., rendezvous, in the minimum amount of time. In this paper we study a generalization from \(2\) to \(k\) agents of a deterministic rendezvous model first proposed by [5] which is based on agents endowed with different speeds. Let the domain be a continuous (as opposed to discrete) ring (cycle) of length \(n\) and assume that the \(k\) agents have respective speeds \(s_1, \ldots , s_k\) normalized such that \(\min \{ s_1, \ldots , s_k \} = 1\) and \(\max \{ s_1, \ldots , s_k \} = c\). We give rendezvous algorithms and analyze and compare the rendezvous time in four models corresponding to the type of distribution of agents’ speeds, namely Not-All-Identical, One-Unique, Max-Unique, All-Unique. We propose and analyze the Herding Algorithm for rendezvous of \(k \ge 2\) agents in the Max-Unique and All-Unique models and prove that it achieves rendezvous in time at most \(\frac{1}{2}\left( \frac{c+1}{c-1}\right) n\), and that this rendezvous is strong in the All-Unique model. Further, we prove that, asymptotically in \(k\), no algorithm can do better than time \(\frac{2}{c+3}\left( \frac{c+1}{c-1}\right) n\) in either model. We also discuss and analyze additional efficient algorithms using different knowledge based on either \(n, k, c\) as well as when the mobile agents employ pedometers.

We consider the problem of scattering \(n\) robots in a two dimensional continuous space. As this problem is impossible to solve in a deterministic manner [6], all solutions must be probabilistic. We investigate the amount of randomness (that is, the number of random bits used by the robots) that is required to achieve scattering.

We first prove that \(n \log n\) random bits are necessary to scatter \(n\) robots in any setting. Also, we give a sufficient condition for a scattering algorithm to be random bit optimal. As it turns out that previous solutions for scattering satisfy our condition, they are hence proved random bit optimal for the scattering problem.

Then, we investigate the time complexity of scattering when strong multiplicity detection is not available. We prove that such algorithms cannot converge in constant time in the general case and in \(o(\log \log n)\) rounds for random bits optimal scattering algorithms. However, we present a family of scattering algorithms that converge as fast as needed without using multiplicity detection. Also, we put forward a specific protocol of this family that is random bit optimal (\(n \log n\) random bits are used) and time optimal (\(\log \log n\) rounds are used). This improves the time complexity of previous results in the same setting by a \(\log n\) factor.

Aside from characterizing the random bit complexity of mobile robot scattering, our study also closes its time complexity gap with and without strong multiplicity detection (that is, \(O(1)\) time complexity is only achievable when strong multiplicity detection is available, and it is possible to approach it as needed otherwise).

In this review, we illustrate the relations between wireless communication and computational geometry. As a concrete example, we consider a fundamental geometric object from each field: SINR diagrams and Voronoi diagrams. We discuss the relations between these representations, which appear in several distinct settings of wireless communication, as well as some algorithmic applications.

The study of computability issues by a system of simple, autonomous, oblivious, mobile robots, operating in the plane in Look-Compute-Move cycles, has been the object of intensive investigations. These robots do not have explicit communication mechanisms, but they implicitly cooperate towards a common goal.

We present lower bounds and inapproximability results for optimization problems that originated in studies of optical networks. They include offline and online scenarios, and concern problems that optimize the use of components in the optical networks, specifically Add-Drop Multiplexers (ADMs) and regenerators.

First we discuss the online version of the problem of minimizing the number of ADMs in optical networks. In this case lightpaths need to be colored such that overlapping paths get different colors, path that share an endpoint can get the same color, and the cost is the total number endpoints (\(=\)ADMs); the key point is that an endpoint shared by two same-colored paths is counted only once. Following [19] (where we showed tight competitive ratios for several networks), we present in this paper a \(\frac{3}{2}\) lower bound on the competitive ratio for a path network.

We next present problems that deal with the use of regenerators in optical networks. Given a set of lightpaths in a network \(G\) and a positive integer \(d\), regenerators must be placed in such a way that in any lightpath there are no more than \(d\) hops without meeting a regenerator. We first discuss the online version of the problem of optimizing the number of locations where regenerators are placed, following [17]. When there is a bound on the number of regenerators in a single node, there is not necessarily a solution for a given input. We distinguish between feasible inputs and infeasible ones. For the latter case our objective is to satisfy the maximum number of lightpaths. For a path topology we consider the case where \(d=2\), and show a lower bound of \(\sqrt{l}/2\) for the competitive ratio (where \(l\) is the number of internal nodes of the longest lightpath) on infeasible inputs, and a tight bound of \(3\) for the competitive ratio on feasible inputs.

Last we study the problem where we are given a finite set of \(p\) possible traffic patterns (each given by a set of lightpaths), and our objective is to place the minimum number of regenerators at the nodes so that each of the traffic patterns is satisfied (that is, regenerators are placed such that in any lightpath there are no more than \(d\) hops without meeting a regenerator). We prove - following [16] - that the problem does not admit a \(\textsc {PTAS}\) for any \(d,p \ge 2\).

Some of these problems have interesting implications to problems stated within scheduling theory.

The nowadays power grid deployed and used in every Country worldwide has served relatively well in providing a seamless unidirectional power supply of electricity. Nevertheless, today a new set of challenges is arising, such as the depletion of primary energy resources, the diversification of energy generation and the climate change. This paper proposes recent advancements in this field by introducing SMART-NRG, a Marie Curie project which involves academic and industrial partners from three EU Countries. The project aims to propose new technologies to meet the specific requirements of smart grids applications. In particular, in this paper, a modular and flexible system architecture is presented to face with the challenges imposed by the different application scenarios.

The profound transformation of large-scale Industrial Control Systems (ICS), e.g., smart energy networks (Smart Grids), from a proprietary and isolated environment to a modern architecture brings several new challenges. Nowadays, ICS network designers need to accommodate a variety of devices and communication media/protocols with industry-specific requirements pertaining to real-time delivery of data packets, reliability, and resilience of communication networks. Therefore, this work proposes a novel network design methodology formulated as a Mixed Integer Linear Programming (MILP) problem. The developed problem accounts for different data flows routed across an overlay network of concentrators and embodies traditional ICS design requirements defined as linear constraints. Furthermore, the MILP problem defines a K-resilience factor to ensure the installation of K back-up paths, and a linear reliability constraint adapted from the field of fuzzy logic optimization. Experimental results demonstrate the efficiency and scalability of the proposed MILP problem.

As Smart Grid deployments emerge around the world, their protection against cyberattacks becomes more crucial. Before protective measures are put into place, one of the main factors to be considered is key management. Smart Grid poses special requirements compared to traditional networks; however, the review of previous work reveals that existing schemes are not complete. Here we propose a scalable and distributed key management scheme for the Smart Grid based on the Web-of-Trust concept. Our proposal is build on top of a Distributed Hash Table for efficient lookups of trust relationships. The target of this scheme is to create a key management system for the Smart Grid without the need of an always available Trusted Third Party. The underlying Distributed Hash Table can be further utilised as an infrastructure to build other Smart Grid services on top of it, like secure and/or anonymous aggregation, billing, etc.

The integration of unpredictable renewable energy sources into the low voltage (LV) power grid results in new challenges when it comes to ensuring power quality in the electrical grid. Addressing this problem requires control of not only the secondary substation but also control of flexible assets inside the LV grid. In this paper we investigate how the flexibility information of such assets can be accessed by the controller using heterogeneous off-the-shelf communication networks. To achieve this we develop an adaptive monitoring framework, through which the controller can subscribe to the assets’ flexibility information through an API. We define an information quality metric making the monitoring framework able to adapt information access strategies to ensure the information is made available to the controller with the highest possible information quality. To evaluate the monitoring framework, an event-driven voltage controller is simulated in an LV grid. This controller utilizes the flexibility of photovoltaic (PV) panels to get the voltages into acceptable ranges when the limit is exceeded. This is done by controlling the grid periodically during the time interval that starts when a voltage limit is exceeded and ends when an acceptable voltage level is reestablished. We show how the volatile behaviour of the PV panels causes overvoltages in a baseline scenario. We then show the controller’s ability to keep the voltages within their limits. Lastly, we show how control performance can be increased by optimizing information access strategies.

Deployment of small cells (i.e., picocells and femtocells) within macrocell coverage is seen as a cost-effective way to increase system capacity and to equip wireless WANs with the ability to keep up with the increasing demand for data capacity. Existing cell discovery mechanisms are tailored for homogeneous networks (macrocells only). User Equipment (UE) cannot efficiently save energy in the process of small cells detection in order to exploit offloading opportunities provided by such heterogeneous deployments. In this paper, we propose a Mobility Prediction aware Scanning Start Time Estimation (MPSTE) scheme to discover/detect small cells efficiently in terms of energy. Based on the current data on road segments (e.g., density of road segment, UEs’ speeds and physical aspects of road segment) and current behaviour of UEs on the road segment, MPSTE allows deriving the time interval UE will spend in the small cell and making decision to perform handoff or no; if handoff is necessary, MPSTE derives the best time to begin the scanning process to discover small cells. Simulation results show the benefits of MPSTE over existing schemes in terms of energy saving by UEs.

Safety implies high dependability and strict timeliness under worst-case conditions. These requirements are not met with existing standards aimed at inter-vehicular communications (V2V) in vehicular networks. On-going research targets medium-range omnidirectional V2V communications and short-range directional communications, which we refer to as neighbor-to-neighbor (N2N) communications. Focusing on the latter, we investigate the time-bounded message dissemination (TBMD) problem as it arises in platoons and ad hoc vehicle strings, referred to as cohorts. Informal specifications of TBMD, of a solution, are given. We show how to guarantee cohort-wide dissemination of any N2N message generated by a cohort member, either spontaneously or upon receipt of a V2V message. Dissemination time bounds are given for worst-case conditions regarding N2N channel contention and N2N message losses. These results add to previously demonstrated merits of short-range directional communications as regards safety in vehicular networks.

Cloud computing has emerged as a viable technology for supporting utility computing. In the future, vehicles are likely to be equipped with devices that have large computation and communication power as well as large storage. Such computation power and storage are often underutilized. People in several areas such as traffic management, parking management, etc. can benefit from utilizing the unused computation, communication and storage capabilities of the vehicles on the road as well as from the traffic information collected by the vehicles to provide services. In this paper, we propose a secure architecture for the vehicular cloud to support the above-mentioned services. The architecture encourages vehicles to contribute their underutilized resources to the cloud by issuing tokens which can be used by the vehicles to get services from the cloud.

Developments in the ITS area are received with great expectation by both consumers and industry. Despite their huge potential benefits, ITS solutions suffer from the slow pace of adoption by manufacturers. In this paper we propose EYES, an ITS system that aims at helping drivers in overtaking. The system autonomously creates a network of the devices running EYES, and provides drivers with a video feed from the vehicle located just ahead, thus presenting a better view of any vehicles coming from the opposite direction and the road ahead. This is specially useful when the front view of the driver is blocked by large vehicles, and thus the decision whether to overtake can be taken based on the visuals provided by the application. We have validated EYES, the proposed overtaking assistance system, in both indoor and realistic scenarios involving vehicular network, and preliminary results allow being optimistic about its effectiveness and applicability.

Road safety applications are one of the main incentives to deploy vehicular networks. These applications rely on periodic message exchange among vehicles (known as beaconing). The beacon messages contain information about the environment which is used to perceive dangerous situations and alert the drivers. The inter-beacon delay is the time between two consecutive beacons received from a car. It is an essential parameter because, if this delay exceeds the application requirement, the application cannot accurately predict dangerous situations and alert the drivers on time. The worst case inter-beacon delay has thus to be bounded according to the application requirements. Unfortunately, a tight and strict bound is in fact very difficult to obtain for a real network because of the randomness of the collisions among beacons coming from: the unpredictable mobility patterns, random interferences, randomness of the MAC layer backoff, etc.

In this paper, we propose to provide a probabilistic worst-case of the inter-beacon delay under realistic mobility using Extreme Value Theory (EVT). EVT provides statistical tools which allow to make predictions on extreme deviations from the average of a parameter. These statistical predictions can be made based on data gathered from simulation or experimentation. We first introduce the EVT technique. Then we discuss its application to the study of inter-beacon delays. Finally, we apply EVT on the results of extensive vehicular network simulation using a realistic mobility trace: the Cologne trace.

In this presentation, we introduce a novel software defined radio (SDR) universal wireless platform, xRadio, for fast prototyping of various emerging wireless systems featuring with attracting cost performance ratio when compared to current solutions. xRadio realizes its advancement and integrity based on a compact and right-on-target design strategy, through adopting a cost efficient raspberry PI minicomputer and a field programmable gate array (FPGA) chip from Altera as its core processors. Function modules can be easily realized through C/C++ and/or python program in a Linux environment or programmable logical elements (LEs) of FPGA achieving powerful computation. To evaluate its performance, an onboard unit (OBU) for vehicle-to-vehicle communications based on both long term evolution (LTE) and dedicate short range communications (DSRC) systems is being built up. Corresponding systems design and key performances are tested and validated including bit error rate (BER) to signal-to-noise ratio (SNR) and processing latency, which validates the usability of xRadio. The unprecedented price-to-performance ratio of xRadio has potential to be applied in a broad range of applications ranging from engineering, production and educations.