ABSTRACT

Wireless Sensor Networks (WSN) have received much attention in the past 5 years, and
much progress has been made in designing hardware, communications protocols, routing,
and sensor fusion algorithms. The planning and deployment of the WSN, however, has
been overlooked to a great extent. These are important aspects, as we show, which can
result in significant gains in WSN performance and resource utilization.

We propose a comprehensive strategy for the planning, deployment, and operation of
WSNs divided into 3 phases, Phases I, II, and III. This framework addresses the
optimization challenges of the planning process, and takes into account the major
sources of uncertainty (notably that due to the aerial deployment of the sensors),
so that the WSN deployed on the ground performs as best as possible. We first present
general-purpose algorithms implementing this strategy, and showcase their benefits
on a few examples. In particular, a Multi-Objective Genetic Algorithm (MOGA) is
proposed for the initial network planning of Phase I, and a greedy local search is
used for the real-time deployment of Phase II.

We then direct our attention to a specific application, where a WSN is deployed to
provide localization to an agent navigating in GPS-denied environments. The network
relies on Ultra-Wideband (UWB) technology in order to provide accurate ranging. 
Because of its high resolution, UWB is able to provide high ranging accuracy, even
in the kind of harsh environments typically found in GPS-denied areas (indoor, urban
canyon, etc.). However the ranging accuracy is limited by two phenomena: the presence
of positive biases in the range measurements due to NLOS propagation, and the increase
of the measurement variance with distance. Given these characteristics, we derive the
Position Error Bound (PEB), a lower bound on the localization accuracy of a sensor
configuration.

We then develop a placement algorithm, RELOCATE, which places the sensors so as
to minimize the PEB. We show that this algorithm can be used for the initial planning
of Phase I, as well as when incremental planning is needed, such as during Phases II
and III.

Finally a Monte Carlo localization (MCL) method is developed to fuse the range
measurements from UWB sensors and the inertial measurements from an onboard IMU, so
as to optimally estimate the state of an agent moving through a GPS-denied environment.
This algorithm is shown to provide high positioning accuracy, notably thanks to its
ability to accurately estimate the bias embedded in the range measurements.

The benefits of using these smart algorithms is showcased at each step, in order to
demonstrate the importance of optimally planning, deploying, and operating the WSN.