Isolation and Connectivity in Networks of Autonomous Entities

Abstract

With the rapid growth of the number of wireless communications devices in the last two decades, device-to-device networks are becoming increasingly important. One sub-group of these are networks of autonomous entities where there is no centralised controller and users actions are based solely on local interactions. The question of connectivity is of paramount importance and is often seen as a pre-requisite of such systems. This thesis will concentrate on this question for two such networks: Vehicular Ad-hoc NETworks (VANETs) and Swarm Robotics.
Connectivity is crucial in VANETs due to the safety critical nature of the information being broadcast. The current state of the art is to model them using a spatial stochastic network model called a one-dimensional hard Random Geometric Graph (RGG). Using a Poisson point process to represent the vehicles in the network, pairs of points are connected if their mutual distance is less than a speci ed radius. We analyse an extension of this model which incorporates the randomness of the wireless medium by now using a distance dependent, probabilistic connection function to determine the existence of edges: a 1-D soft RGG.
We derive bounds on the probability that this graph is fully connected for a
large class of connection functions by analysing two key barriers to full connectivity: isolated nodes and uncrossed gaps. Firstly, analytic expressions are derived for the mean and variance of the number of isolated nodes, and a sharp threshold established for their occurrence. At this threshold we show that the number of isolated nodes can be well approximated by a Poisson random variable. Bounds are then derived for uncrossed gaps, and it is shown analytically that uncrossed gaps have negligible probability in the scaling at which isolated nodes appear. The critical scaling for the occurrence of uncrossed gaps is also investigated.
Connectivity is also also a key feature in robotic swarms since it enables them to
complete tasks as a group which would be impossible for individual robots. We derive an algorithm, implemented on virtual robots, to mimic the behaviour of a group of spiders whose social interactions determine their disposition to travel to a dangerous, unknown area. Simulations of the proposed algorithm demonstrate that this social behaviour improves the swarms ability to explore an unknown environment whilst maintaining suitable levels of connectivity.

Date of Award	28 Sept 2021
Original language	English
Awarding Institution	University of Bristol
Supervisor	Carl P Dettmann (Supervisor) & A J Ganesh (Supervisor)