Cardei, Mihaela

The unmanned aerial vehicle (UAV) technology has evolved considerably in recent years and the global demand for package delivery is expected to grow even more during COVID-19 and the social distance era. The low cost of acquisition, payload capacity, maneuverability, and the ability to y at low-altitude with a very low cost of operation, make UAVs a perfect fit to revolutionize the payload transportation of small items. The large-scale adoption of drone package delivery in high-density urban areas can be challenging and the Unmanned Aircraft Systems (UAS) operators must ensure safety, security, efficiency and equity of the airspace system. In order to address some of these challenges, FAA and NASA have developed a new architecture that will support a set of services to enable cooperative management of low-altitude operations between UAS operators. The architecture is still in its conceptual stage and designing a mechanism that ensures the fair distribution of the available airspace to commercial applications has become increasingly important. Considering that, the path planning is one of the most important problems to be explored. The objective is not only to find an optimal and shortest path but also to provide a collision-free environment to the UAVs. Taking into consideration all these important aspects and others such as serving on-demand requests, flight duration limitation due to energy constraints, maintaining the safety distance to avoid collisions, and using warehouses as starting and ending points in parcel delivery, this dissertation proposes: (i) an energy-constrained scheduling mechanism using a multi-source A* algorithm variant, and (ii) a generalized path planning mechanism using a space-time graph with multi-source multi-destination BFS generalization to ensure pre-flight UAV collision-free trajectories. This dissertation also uses the generalized path planning mechanism to solve the energy-constrained drone delivery problem. The experimental results show that the proposed algorithms are computationally efficient and scalable with the number of requests and graph size.

Unmanned Aircraft Systems (UAS) have grown in popularity due to their widespread potential applications, including efficient package delivery, monitoring, surveillance, search and rescue operations, agricultural uses, along with many others. As UAS become more integrated into our society and airspace, it is anticipated that the development and maintenance of a path planning collision-free system will become imperative, as the safety and efficiency of the airspace represents a priority. The dissertation defines this problem as the UAS Collision-free Path Planning Problem.
The overall objective of the dissertation is to design an on-demand, efficient and scalable aerial highway path planning system for UAS. The dissertation explores two solutions to this problem. The first solution proposes a space-time algorithm that searches for shortest paths in a space-time graph. The solution maps the aerial traffic map to a space-time graph that is discretized on the inter-vehicle safety distance. This helps compute safe trajectories by design. The mechanism uses space-time edge pruning to maintain the dynamic availability of edges as vehicles move on a trajectory. Pruning edges is critical to protect active UAS from collisions and safety hazards. The dissertation compares the solution with another related work to evaluate improvements in delay, run time scalability, and admission success while observing up to 9000 flight requests in the network. The second solution to the path planning problem uses a batch planning algorithm. This is a new mechanism that processes a batch of flight requests with prioritization on the current slack time. This approach aims to improve the planning success ratio. The batch planning algorithm is compared with the space-time algorithm to ascertain improvements in admission ratio, delay ratio, and running time, in scenarios with up to 10000 flight requests.

Wireless sensor networks (WSNs) provide rapid, untethered access to information, eliminating the barriers of distance, time, and location for many applications in national security, civilian search and rescue operations, surveillance, border monitoring, and many more. Sensor nodes are resource constraint in terms of power, bandwidth, memory, and computing capabilities. Sensor nodes are typically battery powered and depending on the application, it may be impractical or even impossible to recharge them. Thus, it is important to develop mechanisms for WSN which are energy efficient, in order to reduce the energy consumption in the network. Energy efficient algorithms result in an increased network lifetime. Data gathering is an important operation in WSNs, dealing with collecting sensed data or event reporting in a timely and efficient way. There are various scenarios that have to be carefully addressed. In this dissertation we propose energy efficient algorithms for data gathering. We propose a novel event-based clustering mechanism, and propose several efficient data gathering algorithms for mobile sink WSNs and for spatio-temporal events. Border surveillance is an important application of WSNs. Typical border surveillance applications aim to detect intruders attempting to enter or exit the border of a certain region. Deploying a set of sensor nodes on a region of interest where sensors form barriers for intruders is often referred to as the barrier coverage problem. In this dissertation we propose some novel mechanisms for increasing the percentage of events detected successfully. More specifically, we propose an adaptive sensor rotation mechanism, which allow sensors to decide their orientation angle adaptively, based on the location of the incoming events. In addition, we propose an Unmanned Aerial Vehicle UAV aided mechanism, where an UAV is used to cover gaps dynamically, resulting in an increased quality of the surveillance.

Energy e ciency is a critical constraint in wireless sensor networks. Wireless
sensor networks (WSNs) consist of a large number of battery-powered sensor nodes,
connected to each other and equipped with low-power transmission radios. Usually,
the sensor nodes closer to the sink are more likely to become overloaded and subject
to draining their battery faster than the nodes farther away, creating a funneling
e ect. The use of a mobile device as a sink node to perform data gathering is a
well known solution to balance the energy consumption in the entire network. To
address this problem, in this work we consider the use of an UAV as a mobile sink.
An unmanned aircraft vehicle (UAV) is an aircraft without a human pilot on-board,
popularly known as a Drone.
In this thesis, besides the use of the UAV as a mobile sink node, we propose an
UAV-aided algorithm for data gathering in wireless sensor networks, called Humming-
bird. Our distributed algorithm is energy-e cient. Rather than using an arbitrary
path, the UAV implements an approximation algorithm to solve the well-known NP-
Hard problem, the Traveling Salesman Problem (or TSP), to setup the trajectory of
node points to visit for data gathering. In our approach, both the path planning and the data gathering are performed by the UAV, and this is seamlessly integrated with
sensor data reporting.
The results, using ns-3 network simulator show that our algorithm improves
the network lifetime compared to regular (non-UAV) data gathering, especially for
data intensive applications.

Today, drones have been receiving a lot of notice from commercial businesses.
Businesses (mainly companies that have delivery services) are trying to expand their
productivity in order bring more satisfaction for their loyal customers. One-way
companies can expand their delivery services are through the use of delivery drones.
Drones are very powerful devices that are going through many evolutionary changes
for their uses throughout the years. For many years, researchers in academia have
been examining how drones can plan their paths along with avoiding collisions of
other drones and certain obstacles in the civil airspace. However, researchers have
not considered how the motion path planning can a ect the overall scheduling aspect
of civilian drones. In this thesis, we propose an algorithm for a collision-free scheduling
motion path planning of a set drones such that they avoid certain obstacles as well
as maintaining a safety distance from each other.

Cognitive radio technology that enables dynamic spectrum access has been
a promising solution for the spectrum scarcity problem. Cognitive radio networks
enable the communication on both licensed and unlicensed channels, having the potential
to better solve the interference and collision issues. Channel assignment is of
great importance in cognitive radio networks. When operating on licensed channels,
the objective is to exploit spectrum holes through cognitive communication, giving
priority to the primary users. In this dissertation, we focus on the development of efficient
channel assignment algorithms and protocols to improve network performance
for cognitive radio wireless networks. The first contribution is on channel assignment
for cognitive radio wireless sensor networks aiming to provide robust topology control,
as well as to increase network throughput and data delivery rate. The approach
is then extended to specific cognitive radio network applications achieving improved
performances.

Channel assignment in multi-radio networks is a topic of great importance because
the use of multiple channels and multiple radios reduces interference and increases the
network throughput. The goal of our research is to design algorithms that maximize the
use of available resources while providing robustness to primary users that could reclaim
one or more channels. Our algorithms could be used in ad hoc networks, mesh networks,
and sensor networks where nodes are equipped with multiple radios. We design
algorithms for channel assignment which provide robustness to primary users without
assuming an accurate primary user behavior model. We also compute bounds for capacity
in grid networks and discuss how the capacity of a network changes when multiple
channels are available. Since preserving energy is very important in wireless networks,
we focus on algorithms that do not require powerful resources and which use a reduced
number of messages.

We consider a heterogeneous wireless sensor network, which has several supernodes for data relay and a large number of energy-constrained sensor nodes that are deployed randomly to cover certain targets. Since targets are covered by many sensors, we create several cover sets that are active successively to save power. We introduce the Heterogeneous Connected Set Covers (HCSC) which aims to find at least one cover set that covers all the targets and is connected to a data-relaying supernode. A sensor node can participate in different set covers but the sum of energy spent in all sets is constrained by the initial energy resources of that sensor node. This is the first solution proposed for the target coverage in heterogeneous wireless sensor networks. We show that the HCSC is an NP-Complete problem and propose three distributed algorithms for it and showing simulation results to verify the proposed approaches.

This thesis considers two important issues in wireless networks. In first part, we address Energy-Efficient Range Assignment in Heterogeneous Wireless Sensor Networks (HRA) and in second part, we present a survey on security attacks in ad hoc wireless networks. We address the HRA problem by selecting the transmission range for each energy-constraint sensor node such that a multi-hop communication path exists between each sensor' node and a resource-rich supernode while maximum power required is minimized. This is the first work to address this problem. We propose several solutions: an Integer Programming approach, a distributed greedy protocol, and a minimum spanning tree protocol based on clustering. In second part of this thesis, a survey is carried out on security attacks on routing protocols in ad hoc wireless network. We examine and classify major routing attacks and present a comprehensive survey on the state-of-the-art mechanisms and solutions designed to defeat such attacks.

Energy consumption is a critical design issue in Wireless Sensor Networks (WSNs), since sensor nodes are battery operated, and replacing or recharging the battery is usually infeasible. Energy efficient solutions are sought at all network levels, especially at the medium access level. The IEEE 802.11 MAC protocol is optimized for Ad hoc Wireless Networks, but cannot be adopted for WSNs because it has the idle listening problem, which is a major source of energy waste. Several Medium Access Control (MAC) protocols have been proposed for WSNs to save the transceiver energy by introducing periodic listen/sleep cycles, and thus overcome the idle listing problem. The periodic listen sleep cycles, however, will increase the network latency and require extra overhead to establish and maintain synchronization among nodes in the network. This dissertation introduces a new MAC protocol for WSNs based on the SMAC protocol to improve its latency performance without compromising its energy consumption. The original SMAC provides an efficient solution for the energy consumption problem due to idle listening, but it increases latency especially in low duty cycle applications. TMAC was proposed to further reduce the energy consumption in SMAC and introduced the Forward Request-To-Send (FRTS) packet to solve the early sleep problem observed in TMAC. Later, Adaptive SMAC was proposed to reduce the latency problem in SMAC by at least 50% at light traffic load. Our new protocol, FASMAC, combines the advantages of both adaptive listening and the usage of FRTS packet in TMAC to further reduce the latency of SMAC. In FASMAC, a packet can travel at least three hops away from its source node within one time cycle. This results in at least 67% reduction in latency at light traffic when compared with the original SMAC. We also propose an energy model for performance evaluation of WSNs protocols using the network simulator NS2. The current energy model of NS2 was designed to handle Ad hoc Wireless Networks where the low power consumption sleep mode was not an issue. However, this is not the case in WSNs. We show that NS2 energy model is not suitable to evaluate the performance of WSNs protocols because it does not account for the low power sleep mode. This dissertation proposes a solution to this deficiency and provides simulation results that match real experimental results performed on the actual sensor motes.