The motivating application for this problem is the channel assignment problem. The frequency of a transmitting radio station may interfere with frequencies of neighboring radio stations. Similar interference may occur in cell phone networks and other radio transmitting networks. We therefore need to find the most efficient way to assign non-interfering frequencies to transmitters within a given region. One way to model this problem is by generalised graph colourings. An L(d_1,...,d_p)-colouring of a graph  is a labelling of the vertices using labels from the set {0,…,\lambda}. The aim is to minimise \lambda under the constraint that vertices at distance i from each other must receive labels that differ by at least d_i. This generalises the classical notion of graph colourings.  Polynomial-time algorithms exist for this problem when p=2 and d_2=1.

 

 

wp532b57cf.png

Wireless sensor networks (WSNs) are an exciting new technology that lies at the intersection of communication networks and smart monitoring. It is easy to imagine the benefits of a system consisting of hundreds or even thousands of sensors distributed over a region or an object and able to measure any of a multitude of aspects of their environment, before passing the information to a central base station for intelligent processing. The applications are countless: early detection of bushfires, smart-home systems, battlefield surveillance, animal population tracking, and environmental pollution monitoring – to name just a few.

Although WSNs are already extensively utilised in the real world, their full potential remains largely untapped. In contrast to other types of communication networks, sensor network technology is fundamentally constrained by existing battery technology and energy conservation protocols. This is because WSNs are required to be autonomous for as long as possible, as they are often deployed in remote, harsh, or even hostile environments.
 

The topology of a WSN, which is the overall pattern formed by the communication links between pairs of sensors, and the relative locations of the sensors within the sensing field, play a large role in the efficiency of the network. This project therefore aims to optimise the topological design and sensor location phase of repairing (augmenting) or deploying a WSN.  The project focuses on all of the following design stages: the development of mathematical tools to model and understand optimal WSN deployments and augmentations, the application of these tools to the construction of new algorithms, and the performance analysis of algorithms by mathematical means and by coding the algorithms and performing simulations.

 

wp15abfa0a_02.jpg

Wireless sensor networks

wp7a17d0f3.gif

Shortest length trees

Survivable networks

wpd4c6cb68.png

Survivable networks continue to function after the failure of multiple links (edges) or nodes. The survivable network problem requires the construction of “low-cost” multi-connected networks, where cost is a function of the lengths of the links.

 

There are two main classes of problem:

 

1) The graph problem, where a weighted graph is given and one must find a survivable spanning subgraph of minimum cost. Popular methods for solving this problem are based on integer programming and polyhedral theory,

 

2) The geometric problem, where nodes have coordinates but not all node locations are given. An ambient geometric space or norm is specified, and the locations of at least some of the nodes (the so-called Steiner points) are decision variables in the optimisation problem. Steiner points may be restricted to certain regions of the plane, but in this version of the survivable network problem there are generally an infinite number of potential locations for the Steiner points. The optimal locations of Steiner points as well as an optimal topology interconnecting all nodes must be calculated.  Weights cannot be assigned to all edges, and therefore mathematical programming formulations (such as MIP) are nonlinear and generally intractable. To speed up algorithms for constructing optimal networks we require the development of good pruning techniques which take advantage of the geometry. By using pruning methods we can potentially discard large numbers of suboptimal topologies at the outset, and thereby produce algorithms which run in reasonable time.

 

Given a set of points in a normed space, draw a set of straight line segments so that the resultant set is connected, contains all given points, and is of minimum total length. This is also known as the Steiner tree problem, especially when the norm is Euclidean or rectilinear.

 

 

Graph colourings

Proximity graphs are geometric graphs like Voronoi diagrams and Gabriel graphs that are defined by certain “closeness” relations between points in a given set. These graphs have extensive applications, including network design, telecommunications, robotics, computer graphics, cartography, and data analysis.

 

Example: Beta-skeleton

 

wp5e8d24c3.png

Proximity graphs