Optimal Positioning for Transceivers in Network

Abstract

This thesis investigates the use of optimization techniques to configure a network of short-range transceivers for best coverage of a topographic layer. Three methods are presented, tested, and analysed. The thesis is inspired by the limited range of underwater wireless communication transceivers. The coverage is defined by free "Line of Sight" (LOS) and a 100 meter transceiver range. The terrain is represented by a Digital Elevation Model, and coverage is computed using viewshed analyses.

Method 1 solves the problem as an Integer Linear Program (ILP). Demand Points (points to be covered) and Candidate Points (points where the transceivers can be positioned) are randomly selected. Further, it is analyzed which demand points that are covered by the respective candidate points. This information is stored in a Coverage Matrix (CM) and solved as an ILP. Method 2 uses a local optimization algorithm to successively deploy the transceiver at the location where it increases the coverage of the Demand Zone (DZ) the most, given what is already covered. When the optimization algorithm finds an optimum, a transceiver is deployed, and the algorithm starts a new iteration. Method 2 is developed in this project and does not consider the task as one big combinatorial problem, but rather a sequence of sub-problems. Method 3 initially performs Method 2, but saves viewshed information computed in its search for optimum. When Method 2 is completed, this viewshed-information is structured as a CM and solved using ILP. By configuring a network of 35 transceivers in the test area of 1 100 000m2, it is found that Method 3 produces the best coverage, with Method 1 just behind. Method 2 produces the network configuration fastest, with ∼ 35% reduction in process time compared to Method 1, at the cost of only 2.3 percentage points less coverage. On larger problems it is found that Method 2 and 3 increase linearly, while Method 1 increase non-linearly following a quadratic function. Arguably Method 2 performance is appealing given its process time and coverage, however, Method 1 and 3 are expected to perform better where interwoven coverage is important.