Mustapha Bekhti

Keywords: Wireless network, drone, UAV, mobilty, tracking, planification, trajectoiry, 2D, 3D, obstacle, collision, SINR, package delivery by drone, data gathering, surveillance, swarm x Réseau sans fil, drone, UAV, mobilité, poursuite, tracking, planification, trajectoire, 2D, 3D, obstacle, collision, SINR, Livraison de colis par drone, collecte de données, surveillance, essaime de drones speeds . . . . . . . . . . . . . . . . . . . . . . 20 jamming nodes . . . . . . . . . . . 25 jamming nodes . . . . . . . . . . . . 5.5 RPR maps with path lengths with 30 jamming nodes . . . . . . . . . . . . . . . . . . . . . .

To my loving parents, to my wife,

Chapter 1 Introduction 1.1 A word about this manuscript

Motivated by the last considerations and by the recent prediction of the number of drones using the airspace in the near few years, we start, in this thesis, by exploring the tracking and the communications requirements between the drones and the government authorities in charge of the airspace management and the traffic control. Due to the limited range, communication between the small scale drones and the ground control operator is established through radio Line-of-Sight (LoS) links between the drones and the base stations deployed as parts of the ground wireless networks. We show that radio efficiency, particularly for drone identification and localization is critical to the large employment of drones in a noisy environment. One possible approach to deal with this consideration is a both offline path planning and online drone tracking. Indeed, it is obvious that path planning is one of the most crucial tasks for mission definition and management of the aircraft and it will also be an important requirement for UAVs that has autonomous flight capabilities. Basically, an efficient off-line path planning could help to ensure a permanent localization and tracking of the drone. Moreover, the predetermined trajectory enables to avoid obstacles and eventual collisions with other drones, and also to optimize certain functionalities in certain environment. However, mission nature, battery capacity, drone characteristics and hovering capabilities strongly influence the path planning strategy. Thus, an online drone tracking is mandatory. To this end and in order to make this possible, one possible approach is the exploitation of the available ground wireless network coverage. This approach relies on a powerful interaction, or collaboration between the UAVs and the wireless network operators. Cooperation in such environment implies that the drone periodically send its identification, localization, speed and other information to the remote operators through the available wireless networks.

In parallel with regulation issues, we also focus on this thesis on mobile data gathering using UAVs. Mobile data gathering is a well-known technique, which uses a mobile collector (e.g. a communicating robot) that moves toward some sensors to collect the data. A better energy saving can thus be obtained for each sensor, compared to the conventional approach which requires the setting and the maintenance of end-to-end network paths between the sink and the sensors. This gain is higher when sensor nodes are deployed over a non-dense area. However, issues might arise when the sensors are spread over a very large area. Typical problems are related to the capacity of the mobile collector to reach all the sensors, either due to the terrain obstacles or because of its energy limitation. To address this challenge, recent research works investigated the use of UAV as Data Collectors in large scale Wireless Sensor Networks. Indeed, UAVs can quickly obtain an accurate data over large areas that are difficult or dangerous to access by traditional means. In addition the data can be collected when 1.2 Organization of the document the need appears and usually at a lower cost, compared to other approaches. Unfortunately, battery limitation of nowadays civilian UAVs does not allow yet long-term missions of small UAVs. To overcome this limitation, we investigate in this thesis the use of multiple UAVs to gather data from sensors that are spread over large scale areas.

In addition, as part of this thesis we are also interested in applications related to the use of a group of drones, called swarm, in the context of the control and surveillance. More precisely, we focus on tracking applications where a fleet of drones is used to locate and to track the intruder in a sensitive area. Basically, our gaols are to determine the position of an intruder in a given area and to keep the fleet in a certain formation in order to avoid a collision between drones and to forward data situation to the controller side. The most important challenge is the coordination among the UAVs to share the space and the sensing resources for improving the perception of the environment. This challenge is due to sensing limitations, which could be due to limited sensor performance, limited detection, limited camera Field of View (FoV). These limitations are the main reason for multiplying the number of drones for such mission in order to increase the perception of the environment. However, increasing the number of drones in a limited space is not without problems and risks. Collision between the members of the swarm is the main problem. To this end, a behavioral approach based on the quality of signals between drones of the same swarm is explored.

Organization of the document

This manuscript describes five of our main contributions, which greatly facilitates the articulation of the chapters.

The chapter 2 is considered as introduction to the drone's world. Parts of this chapter can be skipped or left as reading without loosing of continuity if the reader is already acquainted with drones generalities. However, the section related to the regulations is considered as the principal motivation of our contributions. After presenting a couple definitions and classifications of the Unmanned Aerial Vehicles we highlighted the issues related to the use of drones in the public airspace.

In Chapters 3 and 4, we describe the work carried out around the use of small drones for the transport of packages and parcels from the warehouses to the consumers. These chapters describe mainly the solutions adopted to allow the authorities responsible for the airspace management and the traffic control to track and to localize, in a reliable manner, the drones during their missions.

Introduction

The use of a swarm of UAVs for data gathering is presented in the chapter 5. Such kind of mission raises new considerations, in term of the number of UAVs required for a given mission, path planning of each UAV and of course many other objectives and constraints might be integrated to the path planning problem.

In chapter 6 we present a solution for a rational deployment of a swarm of drones to localize the intruder in a sensitive area.

Finally, Chapter 7 concludes the thesis and gives an outlook to the related future research directions.

Chapter 2 UAV Background

Introduction

The experience already gained with the drones and their potential technological development allow to assert that their role will increase significantly, both in the military and civil realm. Thus, drones occupy rightly and deservedly more and more important place in the aviation industry and defense, and there is a rise in power of experiments around the world.

In the military field, supplementing or replacing the piloted aircraft for some dangerous or very long missions, as well as for reconnaissance, intelligence and attacking. In the civilian domain, covering needs that traditional manned aircraft cannot always satisfy. Between the two, drones seem to provide a satisfactory response to a significant number of needs, but for many the use of drones doesn't reach the desired level yet and their integration in many other applications is far from being satisfying. It's clear that there is still a lot to do in the UAV domain.

Despite the fact the market is almost non-existent today, this is most likely in the civil field that drones are expected to play the largest role, and that due to their flexibility and versatility of their employment. The range of potential applications is almost unlimited.

Drones are being the more credible to meet the need that is not covered by manned aircraft. This is the case of missions that can be considered dangerous, physically painful for the crew, or boring.

In fact, the civilian use perspectives of drones are promising and, mostly, seem still largely undervalued. As a first approach, by simple effect of imitation, civilians may observe the culture of drones among military, and its gradual extension outside the security and defense use. Many civilian uses also remain to be discovered and, with them, the need for equipment and specialized software.

As in the military field, examples of potential applications can be divided into several broad categories, monitoring and observation, communications and transport. Indeed, UAVs are looked with increasing interest in civil and commercial applications and by the scientific research community and many applications can now be found especially with small-scale UAV development. These small-scale UAV are of particular interest due to their ease of deployment, high maneuverability, and low costs. Many actual UAV technologies can be adapted to the public sector applications, but some specific needs will require new UAV capabilities such as localization, tracking, sensing and avoiding, communication between UAVs etc.

In addition, with a continuing trend of miniaturization in electronics and other components, the drones can be made much smaller and much cheaper. However the capability of a single small UAV is limited. Coordination and cooperation between a group of small UAVs can create a system that is beyond the capability of one UAV. However, multi-UAV system cooperation has many challenges and one of the most prominent problems is communication.

If the civil and military potential application of a network of UAVs actually seems very high, it is not without raising some fundamental difficulties and issues which, if not resolved, severely penalize the optimal use of drones. The purpose of this chapter is to explain what the UAVs are, to present their considerable potential, but also to expose the problematic of their integration in the non-segregated airspace. This chapter is organized to reflect three main areas of drones.

First of all, we will define the unmanned aerial vehicle world. We will present the common definitions, classifications and applications adapted from both military and international civilian organisms. Secondly, this chapter attempts to describe unmanned aerial vehicles as single entities among a group or swarm. The cooperation and collaboration issues will be discussed. Finally, we will present the problem and challenges that hinder the widespread and the integration of the unmanned aerial vehicles in the non-segregated airspace.

Unmanned Aerial Vehicles

This section addresses all UAVs definitions being considered by the international organisms and States. It is intended to the scientific community and used to facilitate future discussions on UAV environments. It provides definitions of UAVs, a description of the operational environment and classifications. Several terms used in this document are defined below as a common point of reference.

Definitions

The word "drone" refers, commonly, to unmanned vehicles. However, this term is usually used to refer to Unmanned Aerial Vehicles (UAV). UAVs, also referred to as Unpiloted Aerial Vehicles and a Remotely Piloted Aircraft (RPA), are considered as one of the most important technologies in the field of aeronautics due to their variety of applications, flexibility, and high performance at low costs [START_REF] Rawat | A mini-uav vtol platform for surveying applications[END_REF].

The most general definition which we can give to an UAV is an aircraft without a human pilot aboard. However, different definitions to UAVs exist regarding to the operational use and to the nature of the organisms using this technology.

According to the International Civil Aviation Organization (ICAO) 1 , UAVs are, basically, aircraft without a crew aboard that can be remotely operated or that follow a previously programmed mission [START_REF] Loizou | The arrival of drones[END_REF]. On the other hand,the United States Department of Defense (DoD) 2 Defines an Unmanned Aerial Vehicle as follows: "A powered, aerial vehicle that does not carry a human operator, uses aerodynamic forces to provide vehicle lift, can fly autonomously or be piloted remotely, can be expendable or recoverable, and can a carry lethal or non-lethal payload. Ballistic or semi ballistic vehicles, cruise missiles, and artillery projectiles are not considered unmanned aerial vehicles," [START_REF] Watts | Unmanned aircraft systems in remote sensing and scientific research: Classification and considerations of use[END_REF]. Finally, in Europe, the EUROUVS 3 defines an Unmanned Aerial Vehicle or Remotely Operated Aircraft as "uninhabited, reusable or non-reusable, motorized aerial vehicles, which are remotely controlled, semi-autonomous, autonomous, or have a combination of these capabilities, that have a loitering capability and can carry various types of payloads, making them capable of performing specific tasks within the earth's atmosphere, or beyond, for duration, which is related to their missions" [START_REF] Van Blyenburgh | Euro uvs activities relative to furthering the introduction of uavs/roa into civil managed airspace[END_REF]. 2 DoD is the executive branch of the US government responsible for providing the necessary military forces for the defense of the United States in time of war and peace.

3 EUROUVS is a non-profit association registered with the chamber of Commerce in Den-Haag / Netherlands and operates out of offices in Paris/France which represents manufacturers of unmanned vehicle systems (UVSs), and manufacturers of subsystems and critical components for UVSs and associated equipment.

In fact, unmanned aircraft systems (UAS) are a new component of the aviation system, one which the ICAO, States and the aerospace industry are working to understand, define and eventually integrate them into non-segregated airspace and at aerodromes [START_REF] Magaña | Challenges relating to the projected shortages of skilled aviation personnel regarding civil use of unmanned aircraft systems (uas) and rpa-liability matters[END_REF]. Yet, UAV has become common vocabulary over the years. At present, UAS is defined as a system, whose components include the drone and all equipment, network and personnel necessary to control the unmanned aircraft [START_REF]Joint doctrine note 3-10, unmanned aircraft systems terminology, definitions and classification[END_REF].

Although the term of 'unmanned aircraft' is the preferred appellation in the military environment, the term of 'unmanned' can cause confusion or uncertainty over the actual level of human control and responsibility, and has led the safety and the legal concerns being raised, especially concerning the employment of weapons and flights in non-segregated airspaces. These problems can be addressed in part by using terminology that describes the level of human control of such aircraft. Consequently, it may be appropriate to use the term Remotely Piloted Aircraft (RPA) to describe the unmanned aircraft, and Remotely Piloted Aircraft System (RPAS) to describe the entirety of that [START_REF] Bürkle | Towards autonomous micro uav swarms[END_REF][START_REF] Bürkle | Development of micro uav swarms[END_REF].

However, due to the unclear responsibility for the autonomous and unmanned portion of the flight, the legal and liability issues, and in compliance with the terminology of the European roadmap, the ICAO recommends the use of the terms Remotely Piloted Aircraft

Classifications

In the following we provide information on UAVs classification from different perspectives.

UAVs classification system is required for many reasons, notably in the supporting and developing doctrine defense and concepts for nations [START_REF]Joint doctrine note 3-10, unmanned aircraft systems terminology, definitions and classification[END_REF] and for eventual integration into controlled airspace for a public use. There has been a great difficulty in reaching a consensus on which unmanned aircraft characteristics should be used as the primary factors Unmanned aircraft systems can be divided into the following three categories and subcategories [START_REF] Maddalon | Perspectives on unmanned aircraft classification for civil airworthiness standards[END_REF][START_REF]Joint doctrine note 3-10, unmanned aircraft systems terminology, definitions and classification[END_REF] based on an aircraft maximum gross take-off weight and altitude. Categories start with weight classes, which are further divided on the basis of the operational altitude of the unmanned aircraft as indicated in Table 2.2.

Class I

This category of drones so called "contact UAVs" includes systems capable of providing military units who operate in contact with the adversary, a direct and immediate nearby intelligence, in open terrain or in urban areas. Principally destined to the troops or security forces, these vectors are commonly referred to mini drones and micro drones. This class includes UAV of weight less than 150 kg. These are mostly hand-launched and portable systems employed at the small unit level to provide reconnaissance and surveillance information. This class operates within the line of sight (LoS) at altitude less than 5.000 feet above ground level (AGL) and has limited range up to 50 km. In accordance with weight, this class is further divided into three subcategories, small, mini and micro UAV:

• The first category which gathers UAVs with weight less than 150 kg and greater to 20 kg within operational range up to 50 km, such Hermes 90 and Luna. The later uses a 3D digital terrain map model and constantly monitors the terrain and known obstacles in its flight path, to avoid a collision.

• The second subcategory, named 'mini drone' includes drone with weight between 2 and 20 kg such as DH3, Raven, Scan Eagle, T-Hawk and others. Mini drone systems are the smallest UAVs used by lowest tactical echelons and special operation forces to gather intelligence "over the hill" and "around the corner".

• The third subcategory includes micro-drones with weight less than 2 kg, so called because of their size, which typically enables military versions of these aircraft to be transported within individual soldiers' backpacks. These aircraft tend to operate at very low altitudes, with size limitations on battery capacity offering little autonomy and payload capacity leading to short flight times (5-30 min). Most of these systems developed by industry, such as the Lockheed Sanders "MicroSTAR", the AeroVironment "MicroBat" and "Black Widow", and the Lutronix "Kolibri", are designed with small color video system payloads.

Class II

Known as "tactic UAVs", the drones of this class are primarily destined for intelligence missions and target acquisition over a large limited area. They are essentially characterized by the use of the LOS link of a practical range of 100 to 200 kilometres depending on the flying altitude. Possessed by many countries, tactical UAVs are available in a large number of different models suitable for air-land and air-sea environments. They usually privilege the launch and recovery modes that do not require fixed infrastructure. This class includes drones with weight between 150 kg and 600 kg such as Sperewe, Iview 250, Hermes 450 and Watchkeeper. It covers generally medium-sized unmanned aircraft, often catapult-launched, mobile systems that usually support brigade level and tactical formation in matters of intelligence and surveillance, target acquisition and reconnaissance.

These unmanned aircraft are built to operate with the forward troops, operating at lower altitudes of up to 10,000 feet AGL with a medium range of 125-200 km. The mission endurance is relatively short, around 7-20 hours.

Class III

It characterizes several systems of drones with great endurance using satellite links beyond the line of sight (BLOS) and generally take off from fixed airport infrastructure. This includes typically the largest and most complex unmanned aircraft with weight more than 600 kg, operating at high altitude with the greatest range and endurance. Unlike the other classes, a prepared surface for take off and landing is required. They perform specialized missions such vast area surveillance and penetrating attacks. Payloads may include sensor with EO/IR, radars, lasers, communications relay and weapons. These include strategic high altitude long endurance platforms (HALE) and medium altitude extended range systems (MALE).

Since MALE drones are operating at lower altitudes, they transmit more detailed imagery of targets. At this cruising altitude, MALE platforms can evade most adverse weather conditions. HALE are the largest and most complex of the UAS. It might fly at altitudes of 20,000 m or more on missions that extend thousands of kilometers. Some HALE aircraft have flight duration over 30 h, and have set records for altitude and flight duration. The High Altitude and Long Endurance mission profile was never meant to be used with manned platform, but is perfectly suited for unmanned systems.

It is inevitable that there will be some UAV types that do not fit accurately within a single class or sub-class. For example, an UAV weighing 15 kg that operated up to 8.000 feet AGL would still be considered a Class I UAS.

Civilian classification

The classification of drones for civil and scientific uses has generally followed existing military descriptions and varies according to the context and countries. This classification can be done according to several criteria such as physical size, weight, endurance, altitude, engine type, performance, etc. [START_REF] Watts | Unmanned aircraft systems in remote sensing and scientific research: Classification and considerations of use[END_REF].

ICAO classification

ICAO Classifies unmanned aircraft into two types under the Circular number 328 AN/190 [START_REF] Labs | Self organizing intelligent network of uavs[END_REF]:

• Autonomous aircraft: autonomous aircraft is an unmanned aircraft that does not allow pilot intervention in the management of the flight [START_REF] Magaña | Challenges relating to the projected shortages of skilled aviation personnel regarding civil use of unmanned aircraft systems (uas) and rpa-liability matters[END_REF]. Currently considered unsuitable for regulation due to legal and liability issues.

• Remotely piloted aircraft: An aircraft where the flying pilot is not on board the aircraft.

This kind of UAV is subject to civil regulation under ICAO and under the relevant national aviation authority.

United States classification

For many years, classification of UAVs in the United States of America has been closely associated with the frame related to the type and the nature of the mission without taking into account the requirements needed to operate in the National Air Space. Recognizing that the drones community might be better served by specific rules, the FAA5 is initially proposing to amend its regulations to adopt specific rules for the integration of drones in the national airspace. These changes will concern the classification of drones, registration, pilots certification and operation regulations.

The named classification concerns systems developed by the DoD and other organisms and attempts to organize the types and characteristics of over 200 different drones. 6 , but also packages delivery services as well.

• LIGHT SPORT AIRCRAFT: this class includes drones with maximum gross takeoff weight 1320 lbs such seaplane models. There is a limited number of UAVs in this size and weight range.

• SMALL AIRCRAFT: these are systems over 1320 lbs, operating below Class A airspace (18kft). Examples of these types of aircraft are the Hunter, Predator and Reaper series. This class of drones also provides a fast and powerful combat attack vehicle that is relatively small when compared to a manned fighter.

• MEDIUM AIRCRAFT (12,500 lbs to 41,000 lbs): An example of this aircraft is the Global Hawk that is configured to carry a large payload of munitions. Such kinds of drones moves into the strategic range of long-distance ISR missions.

European Classification

In Europe, UAVs classification is still in the process and not achieved yet.

UAVs Types

As we mentioned before, UAVs come in many shapes and sizes. They are currently divided on tow categories, fixed wing and rotary wing, see • Pros: The major advantages of a fixed-wing UAV consist of:

a simple structure which needs a less complicated maintenance and repair process;

an efficient aerodynamics that provides the advantage of longer flight duration at higher speeds and at a lower cost;

a larger survey area per flight;

a gliding capabilities with no power;

• cons: The fixed-wing UAVs presents some inconvenient while they:

need a runway or a launcher to takeoff and for landing;

require air moving over their wings to generate lift which means they cannot stay stationary and therefore they are not suitable for stationary applications like inspection work.

Rotary Wing UAV

The rotary wing UAVs are also known as Vertical Take-Off Landing (VTOL) vehicles.

• Pros: this type of drone:

does not require runways to take off or for landing;

is able to fly in every direction, horizontally and vertically;

can hover in a fixed position. This makes it the perfect tool for detailed inspection work or surveying hard-to-reach areas such as ravines, pipelines, bridges, power lines and rail tracks ;

can perform hard movements which require manoeuvring around tight spaces;

requires a minimum launching time;

does not need enough space for a landing.

• Cons: Rotary wing aircraft involves greater mechanical complexity which is translated generally into:

lower speeds;

shorter flight ranges;

vibrations. Quadcopter UAVs furnished with a camera evaluated the application of UAVs for fire service response [START_REF] Adams | A survey of unmanned aerial vehicle (uav) usage for imagery collection in disaster research and management[END_REF]. After the Haiti earthquake, an Elbit Skylark UAV was used to assess orphanage damage in remote mountains near Port au Prince [START_REF] Adams | A survey of unmanned aerial vehicle (uav) usage for imagery collection in disaster research and management[END_REF]. The UAV relayed real time imagery that indicated that the orphanage's critical infrastructure was intact, allowing rescue efforts to concentrate on other areas of need, rather than having a critical time required to travel to the remote orphanages.

Applications

In the same frame and in March of 2011, Japan endured a devastating earthquake and subsequent tsunami. Fukushima Daiichi nuclear facility was significantly damaged and consequently began to emit radiation. This hazard complicated repair and traditional reconnaissance efforts as humans were advised to avoid the area. To remedy the imagery collection issue, two remotely operated UAVs equipped with telescopic infrared sensors and outfitted with special radiation sensors were deployed to the area [START_REF] Ackerman | Japan earthquake: Global hawk uav may be able to peek inside damaged reactors[END_REF].

• Unexploded ordnance detection: Statistics showed that there are over 100 million undetected terrestrial landmines scattered over the world. Many people are injured every day of which 90% of the victims are civilians [START_REF] Habib | Humanitarian Demining: Innovative Solutions and the Challenges of Technology[END_REF]. The overall political and legal framework covered by several treaties and conventions emphasize in eliminating explosive devices including landmines and unexploded ordnance around the world, therefore a global effort in a multidisciplinary manner is required to address this issue. This ranges from improving quality of the information on the threat, developing new survey and clearance procedures and deploying better equipment including improved sensors. Therefore, the use of antennas mounted on UAVs allows performing a wide area scanning, a contactless remote sensing in high-risk area as well as rapid and mobile surveying.

• Forest fires warning: Based on recent demonstration missions, the US Forest Service envisions using LASE and MALE Unmanned Aircraft for fire detection and active fire monitoring missions [START_REF] Watts | Unmanned aircraft systems in remote sensing and scientific research: Classification and considerations of use[END_REF]. VTOL aircraft are particularly appealing in wildfire and disaster response situations where access to improved surface runways is seldom guaranteed.

• Vegetation mapping: A vegetation map illustrates the geographical spread of a plant community. It provides extremely important basic information for environmental planning. In [START_REF] Kaneko | Review of effective vegetation mapping using the uav (unmanned aerial vehicle) method[END_REF], research was conducted to present a more precise mapping of vegetation using UAV as a new method of creating vegetation maps.

To do so, an aerial photography using UAV was conducted in the Niida River Estuary (Fukushima Prefecture, Japan) in August 2013. The authors proceeded by comparing vegetation maps created by aerial photographs taken by an UAV and an aircraft (manned flights). According to this author, the aerial photographs taken by the UAV have clearly discriminated each plant community at the 1/50 scale. Moreover, he specified that they clearly discriminate the shape of a plant at the 1/10 scale. As a result, the authors conclude that vegetation surveys using UAV are efficient and capable of a highly precise community distribution where field reconnaissance is difficult.

• Oil, gas and mineral exploration : UAVs can be used to perform geophysical surveys, in particular geomagnetic surveys to calculate the nature of the underlying magnetic rock structure [START_REF] Wong | Survey of regional developments: Civil applications[END_REF]. The production and the exploration of oil and gas entail the monitoring of the integrity of oil and gas pipelines and related installations. For above-ground pipelines, the monitoring activity could be performed using small uavs.

Extending network connectivity:

The success of any communication mission between several geographically dispersed nodes is based on a constant flow of communication allowing the exchange and the update of information continuously. However, this requirement is not always satisfied because of the limited range of wireless radio communications often obscured by obstacles, particularly when remote nodes operate in urban, mountainous or rugged environments. The problem becomes worse when the rate of wireless links increases. In 2011, Parrot AR drones were used to inspect the Christchurch Cathedral, New Zealand, that had sustained significant damage after an earthquake strike and made it too dangerous for humans to get in. In a similar case, in Mirandola, Italy, after the 2012 earthquake, a team of flying and ground-based robots was successfully deployed to inspect the damage caused to the historical cathedral and to produce 3D map reconstruction to report on structural damage to ceilings, arches and aisles [START_REF] Commission | Microcopters and ground robots used to save earthquake-hit italian churches[END_REF]. The recent one, a French innovation signed by Hardis Group is related to the use of micro UAV to automate inventory in warehouses and which aims to put on the market in the near few years [START_REF] Hardis | Gestion d'entrepôt[END_REF]. With embedded system drone, logisticians can automate inventory in warehouses, identify and correct storage errors. Because of their size and their ability to perform stationary and translation flights, their use in the warehouse opens up new prospects for logistics.

Challenges

The use of drone technology can revolutionize the way states and authorities acquire and manage spatial data as well as the manner in which the industrial, researcher and other development partners design, implement, and monitor their projects by making these processes more accurate and cost effective.

The emergence of small and affordable drone technology and their eventual large field applications promises a widespread of them use. In fact, with their small size and portable versions, drones can produce accuracy results equivalent or better in many cases than the conventional manned aircraft and offers cost savings and greater flexibility. For example, UAVs allow the placement of sensors anywhere in 3D space and subsequently, add new dimensions to baseline data gathering and alternative assessments of the situation and the environment without placing people in a hazardous environment.

In the last years, the Unmanned Aerial Vehicles have been the subject of much discussion surrounding the military uses in conflicts, crises and war but also, and with a higher degree, around them integration in the global non-segregated airspace, and this for civil and commercial use.

Although the use of drones is expanding and their prospect seems promising, the level of their integration is far from being efficient. Actually, many problems hinder the integration of the UAVs into a global non-segregated airspace and need to be solved. The most important are related to the standards, norms and regulation relevant to airworthiness and certifications.

Additionally, other critical technical issues exist, such sense & avoid capabilities, transponders, secure and powerful communications, reliable emergency procedures, safety systems and above all public acceptance [59].

The optimal use of drones and the generalization of their employment raise, however, a number of difficulties that need to be resolved over time. These difficulties are not always at the same level, depending on the framework of use, military or civilian. Essentially, these difficulties and changes are of two types, legislative and technical.

This section examines the actual problems that face the vulgarization of drones and their integration in the non-segregated airspace.

Regulations

Drones technology is a rapidly progressing industry and unlike many other new technologies, the legal and regulatory framework crawl behind. At present, there are no common international certification or standards and the actual legal sphere lies between the well-regulated conventional manned aircraft under the legislation of civil aviation authorities and the less rigorous rules related to small size drones destined for hobbyists recreation. Thus, there is currently little regulatory measures for accommodating UAVs within the existing framework of rules governing routine flights in non-segregated airspace.

In Europe as well as in US, the airspace usage issue seems to stand out as the prime impediment to progress and development of the public UAV market. Thus, despite its expansion, an adequate regulatory framework on a global level does not exist yet. Meanwhile, UAVs remain used but under a fragmented regulatory framework and under different rules.

In order to guarantee a reliable and safe integration of UAVs in non-segregated airspace, there is a need for a common rule governing UAVs design and operations across the countries and a mutually agreed legislation, protocols, and technologies. Such Regulations will rely upon agreed standards of airworthiness certification. Afterwards, delivering of airworthiness certification in turn will be impossible for UAVs operating in the same airspace as other aircraft without a reliable, foolproof, sense and avoid capabilities that guarantees the safety of the overflown population [START_REF] Ackerman | Japan earthquake: Global hawk uav may be able to peek inside damaged reactors[END_REF].

Some countries have already adopted legislation and relevant bylaws to enable the operation of small UAV's on their territory. Canada, Australia and Brazil voted their first regulations for UAV's between 2007 and 2011, the UK in 2011 and France in 2012. These regulations are not considered like fixed. They will change along with the progress and development of UAV industry [START_REF]Global commerical and civil uav market guide[END_REF]. However, although many states endeavour to address the issue at local level the legislation is relatively limited.

In Europe

In Europe, the European Aviation Safety Agency (EASA) 7 is responsible for civilian aircraft with weight more than 150 kg. Cause there are no rules regulating integration unmanned aircraft in non-segregated space, UAVs with weight superior than 150 kg are prohibited in Europe. Regulations that govern this class of drones are planned for the next near few years.

In addition, for eventual airspace use, the UAV must fulfil four basic requirements [START_REF] Center | Honeywell t-hawk aids fukushima daiichi disaster recovery[END_REF][START_REF] Debusk | Unmanned aerial vehicle systems for disaster relief: Tornado alley[END_REF]:

• the aircraft must be approved (Type Certificate);

• all components of the unmanned aircraft system including ground station must be certified;

• pilots must be licensed;

• payload operators must be licensed.

EASA is following a new regulatory approach called "Concept of Operation for drones" based on input from users and UAVs manufacturers. This approach includes new standards and cover safety, security, privacy, data protection, insurance and liability issues [START_REF]Concept of operations for drones[END_REF]. This concept has been developed to achieve two main objectives. First, to integrate drones into the existing aviation system in safe and proportionate way, and second, to promote European drone industry, particularly, the small and medium enterprises and to create new employment.

Taking in consideration the large range of types of UAVs and their applications, the concept approach is proposed to establish three categories of operations:

1. Open category: Includes drone operations with very low risk. No aviation authorities authorization, no airworthiness approval and no licenses are required for operators even for commercial operations. However the drone must be flown under direct visual line of sight (500m), at an altitude not exceeding 150m and to remain outside and far off specified reserved areas (airports, restricted zones...). It is envisaged a maximum mass limit of drones operating in populated area.

2. Specific category: Covers operations where certain risk needs to be mitigated and reduced by additional limitations or higher capabilities of the UAS. This said, a safety risk assessment is required by the national aviation authority to deliver an Operation Authorization with specific limitations. In some cases, the issuance of the operation authorization might require a certification of the drone or of a specific function.

3. Certified category: When drone operation risk rises to a level comparable to normal manned aircraft, the operation is positioned in the certified category, and therefore, specific certificates to drones would be issued as well as certificates for piloted aircraft.

The definition of the lines of demarcation between specific and certified categories is still open at this stage and meanwhile, the EASA will continue to accept applications for drones of a MTOM (Max Take Off Mass) above 150 kg and those which are in accordance with EASA sphere activities and ability (aircraft not specifically designed or modified for research, experimental or scientific purposes, and not likely to be produced in very limited numbers [START_REF]of the European Union[END_REF]).

Within Europe, Light UAVs are characterized by having a MTOM of less than 150 kg. UAVs with MTOM above 150 kg are assessed by EASA and those less than 150 kg by EuroUSC 8 , an independent light UAV approval specialist, authorized to assess the 8 EuroUSC is a specialist accreditation body working with specific field of civil aviation for UAV. It is a qualified entity for assessing manufacturers, operators and flight training school involved in light UAV having a MTOM of less than 150 kg airworthiness of light UAV having MOTM of less than 150 kg. This includes the functional assessment of embedded software which is large part of most modern UAV safety systems.

The EuroUSC developed and introduced two certificates type for flight:

• BNUC: Basic National UAS Certificate for drones having MTOM between 20 kg and 150 kg;

• BNUC-S: for small UAV having MOTM of less than 20 kg.

Progress in the Single European Sky (SESAR) project, running in parallel, also has relevance for the integration of UAVs into controlled airspace by 2020.

In the broadest sense, experimental or amateur, military and civil drone below 150 Kg as well as model aircraft that generally recognized as intended for recreational purpose only, fall outside the provision of ICAO and EASA, being exclusively the subject of relevant national regulations. The National Aviation Authority of each of the 28 European Union (EU) Member States is responsible in its country for rulemaking, certification & operational approval of civil UAV with a MTOM less than 150 kg and for the drone operators. It is imperative that the operator crew and the UAV they operate are of the appropriate standard to avoid accident. Current regulation on insurance requirements for air carriers and operators does not require insurance for model aircraft of less than 20 kg.

In the United States of America

In the United States of America, the FAA is responsible for establishing guidelines, plans and rules for the safe and efficient use of the United State navigable airspace. These charges and liabilities also include the integration of drones into the United State airspace in a manner that supports and maintains the ability to secure the airspace and that addresses privacy concerns. Furthermore and when it's appropriate, the FAA will harmonize with the International Civil Aviation Organization (ICAO) for the mutual development of civil aviation and the integration of the drones in the non-segregated airspace.

Introducing drones into the USA airspace is challenging for both the FAA and aviation community, because the United States has the busiest and the most complex airspace in the world. With the proliferation of drones, it will be more than essential to open the controlled airspace to mix usage for both manned and unmanned aircraft. The FAA has stated that for unmanned aircraft to fly regularly in the controlled airspace, those drones must meet the same FAA airworthiness standards as manned aircraft.

For the integration of small drones (under 25 kg) in the national airspace, the FAA has proposed a framework of regulations that would allow routine use of this class of drones in the aviation system, while maintaining flexibility to accommodate future technological innovations. The proposal offers safety rules and an incremental approach to save this integration. In general, UAV must remain within VLOS only and must remain close enough to the operator to be capable of seeing the UAV without any device other than corrective lenses. The operator would be required to pass an aeronautical knowledge test and obtain an unmanned aircraft operator's certificate. In addition, no person may act as an operator or visual observer for more than one UAV in the same time [START_REF]Overview of small uas notice of proposed rulemaking[END_REF][START_REF] George | Faa unmanned aircraft systems (uas): Overview: Uas and the proposed small uas rule[END_REF].

Under the proposed rules, the pilot of a small UAV would be considered "Operator". This means that he would have to be at least 17 years old, and should pass an initial aeronautical knowledge test at an FAA-approved knowledge testing center and a recurrent aeronautical knowledge test every 24 months.

The new rule also proposes operating limitations designed to minimize risks to other aircraft and people and property on the ground:

• The operator must avoid manned aircraft and in case of collision risk, the drone operator must be the first to manoeuvre away.

• The operator must change the direction of the flight when continuing would pose a danger to other aircraft, people or property.

• The operator must assess meteorological conditions, airspace and area restrictions.

• The flight over people is prohibited, except over those involved with the flight.

• The flight should not exceed an altitude of 500 feet and speed of 100 mph.

• The operators must stay out of airport flight paths and restricted areas, and obey to any temporary flight restrictions.

The proposed rules also include discussion of the possibility of an additional integration for micro drones weighing less than 4.4 pounds. The FAA is asking the public to comment on this proposal to determine and develop the final rules. For more details, readers are encouraged to read (UAS Overview and the Proposed Small UAS Rule [START_REF] George | Faa unmanned aircraft systems (uas): Overview: Uas and the proposed small uas rule[END_REF]).

Energy

UAVs come in a variety of sizes and shapes and deployed for diverse purposes. The rotary wing drones have generated great interest in industrial and scientific circle. They have exclusive capabilities like hovering, vertical take-off and landing (VTOL), limited launching space and good manoeuvring. However, this class of UAVs is a power constrained as the UAVs operate with restricted battery power. Subsequently, Ad hoc networks based on UAV are in them turn power constrained too. The energy saving is a very important issue.

With regard to communication, there is also an amount of energy wasted in states that are useless from the application point of view, such as data retransmission when reception problems occur at the received side. Consequently, UAVs have to manage their transmission and their movements to preserve and maintain the battery life [START_REF] Cartigny | Localized lmst and rng based minimum-energy broadcast protocols in ad hoc networks[END_REF].

Since batteries is a limiting factor in UAV usefulness and design, it is possible the world will see better batteries quite soon. Several innovations in the field of battery design are showing great promise in improving batteries.

Reliability

Regardless of size, the responsibility to fly safely applies equally to be manned and unmanned aircraft operations. Most jurisdictions that regulate manned aircraft flight in their airspace also restrict some aspect of unmanned aircraft use. Motivations behind these restrictions include safety of people on the ground and above as well as security against the misuse of UAS.

Thus, the drones must always meet airworthiness criteria and respect of air traffic rules, analogous to those airplanes. This requires them to benefit from a certain level of technical reliability and resistance to crash (to ensure security on the ground) but also of a satisfactory reliability of the behavioral point of view (to ensure the safety of other aircraft in flight).

Reliability must be exercised with regard to proximity detection, steering control, data exchange with ground control, as well as the management capacity of degraded situations. This is a crucial issue for drones which, a priori, does not currently meet these constraints.

The resolution of these difficulties could, of course, lead to the creation of a certification of drones by the competent authorities, as for all other aircraft. This would provide some guarantees in the desired levels of reliability.

Ethic and Public Acceptance

Despite the man has a central place in UAV systems, the fact that the drone is not "inhabited" raises a number of ethical and legal questions. From the ethical point of view, several points are to consider:

• the distance created between the flight crew and the area of operations is contributing to a sense of dehumanizing the nature of war and in some cases, the legitimacy of the action;

• reducing pilot loses risk offered by these systems can lead the decision makers to trivialize and to increase the use of the military action;

• these systems today convey a particular image resembling some "robotic war" that could lead to rejection reactions and an impact on the public opinion;

• life privacy. Whereas these autonomous UAV systems still have no operational existence, we already observe international campaign that claim to regulate or even prohibit this type of system includes those which can decide on the opening of autonomous fire. Objections are raised when drones become the cause of civilian deaths in war zones and much more in a non-war zone. The best way to deal with the public's phobia is to show the economic benefits these devices can provide.

Summary

Despite the fact they were invented more than a century ago, UAVs have only recently become a widespread technology. Lower costs building coupled with non-traditional military actions have caused the use of UAVs to escalate profusely. Due to this marked increase in application, a host of new problems and technicalities have created a need for new legislation in order for UAVs to be a useful and morally positive technology.

Although the application of drones in civil area is still at the early developmental stage, the UAV technology is expected to play a major role in supplying both static data acquisition and sensing as well as dynamic data streaming. The UAV applications will become popular in civil, commercial and transportation area in near future. Consequently, UAVs ad hoc network UAVNET, could fit in different situations and could provide interesting solutions and could be too better alternatives on how we do and pursue mission. However, controlling a large swarm of UAVs will require a significant transformation in the manner of controlling an individual UAV. Thus, how to exercise effective command-and-control over a swarm of UAV is an emergent open research issue and only more research efforts will prompt and warrantee effective and safe use of the UAVNET.

In this chapter we formally define UAVs and present them classifications and applications.

Next, we have defined UAV swarm as an emergent behavior based on the interaction of individual drones running simple local rules and commands. Despite its few drawbacks of inefficiency and non-determinism in couple cases, we showed that swarming characteristics of simplicity, robustness and scalability lead us to consider that is well suited for many missions and applications. However, UAV systems are not yet accepted in the normal air traffic, not only because the absence of the legal framework but also for technical issues inherent to communication. Yet, communication is one the most challenging issue for the drones.

Chapter 3

Single UAV path planning and tracking: Exact solution

Motivations

Drones or UAVs (Unmanned Aerial Vehicles) are unmanned flying machines capable of carrying out more or less autonomous mission. Their earliest development was intended to the military use. Typical missions are the reconnaissance and the surveillance of wide and/or abroad territories. They are especially adapted for the realization of missions that would put the crew in danger or that would be tedious for an on-board crew. The technological progress in different domains that are related to UAVs, such as, advances in aeronautical, robotic, batteries and computer science have recently extended the economical perspectives toward the civil market. Beside entertainment, there are already several successful uses of UAVs for civil applications. One can refer to traffic monitoring in highways, prevention of forest fires, inspection of buildings and structures or data gathering for environment, for agriculture or for mining.

In addition, a forthcoming plan for freight and package delivery services has recently been announced by a number of companies around the world such as Deuch Post DHL, which has started testing the delivery of mail and medicaments to hard-to-reach places, Amazon Inc for a UAV home package delivery program within the next few years or Zookal Inc, an Australian textbook rental company, which announced a program of delivering books to students in sight of cutting delivery times to minutes rather than days.

Unfortunately, even though UAVs are expected to revolutionize some civil applications, the legal and regulatory framework crawl behind. The widespread introduction of drones for recreation or civil applications raises new challenges to the government authorities, which have to balance safety and public concerns against the potential economic benefits of UAVs.

On the other side, from the commercial standpoint, the development of UAVs with higher levels of autonomy and a minimum of persons controlling the drone actions are essential requirements to exploit this technology at its highest economic potential.

As we have mentioned in the previous chapter, the authorities in charge of the safety and the management of the airspace request a guarantee to open the sky for eventual use of the drones in the commercial field. The drone identification and localisation are part of these significant requirements. Thus, tracking is a fundamental mechanism that needs to be integrated into autonomous and even non-autonomous UAVs in order to provide a reliable system of collision avoidance that guarantees the safety of the overflown population. In this context, Tracking, refers to the capacity of a remote system to follow the UAV trajectory. It relays on the localization and on the reporting of the UAV positions. While, this chapter does not investigate the localization problem, which could for instance relays on classical outdoor localization solutions, like the GPS, we choose to focus on the transmission issue of the UAVs positions. The basic concept is to use terrestrial wireless networks, like cellular or WiFi technologies, to periodically transmit the UAVs' coordinates toward a remote monitoring and controlling system.

Fig. 3.1 Drone package delivery

The main purpose of this work is to reshape the UAVs trajectory path depending not only on the destination but also on the capacity of the wireless networks (covering the target UAV area) to transmit the UAV localization messages with a satisfactory Quality of Service levels. Precisely, we address the offline path planning of an UAV, which starting from a given position has to reach in a minimum possible delay a predetermined destination. The trajectory is constrained by the capacity of the drone to periodically transmit its localization to the remote system using traversed terrestrial wireless networks. The constraint is expressed as a maximum ratio of lost messages, which can occur either due to the wireless capacity limitations or due to the incomplete radio coverage of the traversed area.

The remainder of this chapter is organized as follows. Section 3.2 briefly reviews related works. System description and formulation of the problem as well as the analytical model for computing the tracking packet loss rate are detailed in section 3.5. The performance evaluation results obtained after solving the constrained optimization problem are analyzed in Section 3.7. Finally, section 6.4 concludes the paper and discusses our future prospects.

State of the Art

Path planning or movement schedule is a set of mathematical and computational techniques to calculate the trajectories for a cinematic system. This issue has been widely studied in the robotics realm and has been addressed using different approaches and techniques. The two most popular techniques are deterministic, heuristic-based algorithms [START_REF] Hart | A formal basis for the heuristic determination of minimum cost paths[END_REF][START_REF] Nilsson | Principles of artificial intelligence[END_REF][START_REF] Podsedkowski | A new solution for path planning in partially known or unknown environment for nonholonomic mobile robots[END_REF] and probabilistic, randomized algorithms [START_REF] Kavraki | Probabilistic roadmaps for path planning in high-dimensional configuration spaces[END_REF] and [START_REF] Lavalle | Randomized kinodynamic planning[END_REF]. The choice of the algorithm to use depends on the type of problem to be solved.

For the autonomous flight of drones, path planning is one of the most crucial and important issues to solve. Nowadays, the application of UAV is extending from high-altitude flight to very low-altitude, where the impact of the terrain, the environment and the air traffic will be the key factors to be considered to avoid collisions [START_REF] Wang | Three-dimensional path planning for unmanned aerial vehicle based on interfered fluid dynamical system[END_REF]. However, we do not aim to provide an exhaustive list but we will be limited to provide the most relevant work related to the path planning regarding to the nature of the objectives, problems formalization and resolving methods.

The authors in [START_REF] Maillot | Lyapunov and minimumtime path planning for drones[END_REF] mentioned that classical planning algorithms are based on different approaches such as geometric control [START_REF] Bullo | Modeling, analysis, and design for simple mechanical control systems[END_REF], optimal control [START_REF] Ding | Multi-uav convoy protection: An optimal approach to path planning and coordination[END_REF], flatness [START_REF] Bhatia | Dubins trajectory tracking using commercial off-the-shelf autopilots[END_REF] stochastic theory [START_REF] Bertuccelli | Robust adaptive markov decision processes: Planning with model uncertainty[END_REF]. On the other hand, the authors in [START_REF] Goerzen | A survey of motion planning algorithms from the perspective of autonomous uav guidance[END_REF] presented a survey of motion planning algorithms from the perspective of autonomous UAV guidance. They mentioned that guidance for fixed and rotary-wing UAV, involves significant differences from most traditional mobile and manipulator robots. These include three-dimensional environments, disturbed operating conditions, and high levels of uncertainty in state knowledge. In addition, poor GPS telemetry, air turbulence and obstacle detection are common issues in drone applications. Moreover, in a typical UAV application, the vehicle has differential constraints, including limited speed, maximum acceleration and limited energy (batteries). The resulting problem has different dimensions, associated with the equations of motion and involving the knowledge of UAV characteristics and a precise input variables. To our knowledge, it does not exist an algorithm that provides a fully exact analytic solution to such a problem.

The authors in [START_REF] Mathew | Planning paths for package delivery in heterogeneous multirobot teams[END_REF] presented a framework to compute the minimum cost cooperative route between a heterogeneous package delivery team composed of a truck and micro drones.

They abstracted the problem on a graph and formulated the issue as a discrete optimal path planning problem. In the same context of heterogeneous teams, the authors in [START_REF] Manyam | Path planning for cooperative routing of air-ground vehicles[END_REF] presented a path planning problem involving an UAV and a ground vehicle for intelligence, surveillance and reconnaissance missions. The addressed problem is similar to the ring-star problem and the hierarchical ring network problem.

On the other hand, the authors in [START_REF] Wang | Robot-assisted sensor network deployment and data collection[END_REF] and [START_REF] Chen | Three-dimensional path planning for unmanned aerial vehicle based on linear programming[END_REF] presented three dimensional path planning solutions for unmanned aerial vehicles. The first solution is based on interfered fluid dynamic system, while the second approach uses linear programming where obstacle avoidance and target tracking are linearized to generate a linear programming model in a relative velocity space.

In [START_REF] Jun | Path planning for unmanned aerial vehicles in uncertain and adversarial environments[END_REF], the authors presented a path planning for unmanned aerial vehicles in uncertain an adversarial environment in sight to reach a given target, while maximizing the safety of the drone. They proposed a path planning algorithm based on threats probability map, which can be built from a priori surveillance data. In the same context, [START_REF] Peng | Intelligent online path planning for uavs in adversarial environments[END_REF] proposed an intelligent online path planning for UAVs in adversarial environments based on a model predictive control. One of the main objectives was to provide an online path planning based on a model predictive control, which is a dynamic multi-objective evolutionary algorithm to permanently update the environment information for the drone. To select the optimal path, the Bayesian network and fuzzy logic are used. Along the same lines, [START_REF] Rathbun | An evolution based path planning algorithm for autonomous motion of a uav through uncertain environments[END_REF] considered the application of evolution-based path planning in the case of moving obstacles at uncertain locations. It was mentioned that changing the problem from fixed obstacles to moving ones, transform the problem from a geometric deterministic problem to a dynamic stochastic issue.

Another important work is [START_REF] Ferguson | A guide to heuristic-based path planning[END_REF], which contains concise summaries. It focused on dynamic problems and discussed a family of heuristic algorithms for path planning in real-world scenarios such as A*, D*, ARA* and AD*. Finally, it is worth mentioning the research done by [START_REF] Yanmaz | On path planning strategies for networked unmanned aerial vehicles[END_REF] that can be considered one of the few papers dealing with path planning strategies destined for a based UAVs network. The authors compared deterministic and probabilistic path planning strategies for autonomous drones to explore a given area with obstacles and to provide an overview image. The results showed that, although the deterministic approach could provide a solution, it requires more knowledge and time to generate a plan. However, the probabilistic approaches are flexible and adaptive.

To the best of our knowledge, none of the above works have investigated UAV path planning problem assuming that UAV uses terrestrial wireless networks to transmit its locations.

Problem statement and system description

As introduced in the last section, we are considering in this paper a package delivery services using UAVs. Basically, a UAV has to deliver a package from a given position O considered as a depot or warehouse to a predetermined destination or consumer, noted D. Our purpose is to provide an offline path planning with respect to a given cost functions such as the delivery delay. However, the proposed path must be feasible with respect to the UAV's residual energy constraint. In addition, the path is computed offline with the aim of ensuring a quasi-permanent tracking of the UAV's location, using wireless network technologies. In fact, the UAV could either be piloted or can be autonomous. However, in both cases, we assume that the followed trajectory is the one computed offline by our approach. In this section we suppose that the drone keeps the same height from position O to destinations D.

The investigated geographical area is denoted A. Without a loss of generality, we assume that A is a 2D square area, which does not contain any obstacle. Moreover, to reduce the set of possible paths from O to D to a finite dimension, A is discretized into Area Units (noted as a) of the same shape and same dimensions. Without a loss of generality, we assume that each cell has a hexagonal shape as illustrated in figure 3.2.

In this case, As will be seen here after, the shape must be chosen keeping in mind the trade-off between allowing more flexibility in the drone's movement patterns while keeping the dimension of the set of possible path solutions below a tractability threshold. We believe that the hexagonal shape offers quite a good compromise. Furthermore, we suppose that an UAV flying over an AU necessarily passes through its center. We thus choose to set O and D at the center of their associated AUs, which we will refer to o and d, respectively. We also assume that the UAV trajectory between two adjacent AUs follows the linear segment connecting their respective centers. Furthermore, Another constraint that must be satisfied is the tracking of the drone's positions using wireless networks, such as cellular or IEEE 802.11x technologies. For this purpose, we assume that after each period T the drone generates a message of size D bits containing its most recent 3D position. When possible, the on-board wireless interface tries to send each generated message to the remote UAV monitoring and controlling system. The opportunity to transmit depends on the radio coverage and the capacity of the related wireless technology in the drone's location. A message can also be corrupted due to radio transmission errors and discarded at the receiver side. We thus assume that a generated location message might be lost with a probability that we denote P. Our purpose is to provide a drone's path planning, which guarantees that the rate of successful transmissions of localization messages is above a given threshold denoted δ . Formally, 1 -P ≥ δ . The packet loss rate, P, is computed as the proportion of lost messages over generated ones during the overall path. An analytic estimation of this metric depending on the location and the coverage of the wireless network is fully detailed in subsection 3.5.

In the following, we propose an Integer Linear Programming formulation of our path planning problem.

Integer Linear Programming formulation

Let G = (V, E) be a directed graph. V is the set of vertices and correspond to the set of AUs in A, and E is the set of edges and denotes the possible movements followed by any drone in order to move from one AU to any another adjacent AU. Since we consider hexagonal shape for our cells thus only six possible movements are allowed. The resulting graph is then a grid graph, where each node has a degree equal to 6, unless it is located on the border of the area.

The graph includes a special node o ∈ N, that is the depot, from which all the UAVs start to move.

We also define a cost function matrix C = (c i j ) denoting the cost for a drone when moving from vertex i to vertex j, in its vicinity. We define c i j = d i j /S, where d i j is the distance required for traveling from AU i to AU j , with i and j ∈ V and S is the linear speed of the drone.

We also define P i j as the tracking packets loss probability when a drone is moving from AU i to AU j . According to the last considerations, our main problem is to:

• Minimize the UAV traveling delay between the depot o and the destination d. This objective can be expressed as follows:

argmin x i j ( ∑ i∈A ∑ j∈A d i j S x i j ) (3.1)
where x i, j is a binary variable that is equal to 1 if the drone moves from cell i to cell j, 0 otherwise.

• Maximizing the UAV tracking along the selected path from the depot o to the destination d. This second objective can be expressed as follows:

argmax x i j ( ∏ i∈A ∏ j∈A (1 -p i j )x i j ) (3.2)
Since the logarithm is a monotonically increasing function of its argument, the above expression is equivalent to:

argmin x i j ( ∑ i∈A ∑ j∈A -log((1 -p i j )x i j )) (3.3)
Given our system description and modeling, the above problem could be expressed a constrained shortest path problem using the following Integer Linear Programming formulation:

min ∑ i∈A ∑ j∈A d i j S x i j (3.4a) min ∑ i∈A ∑ j∈A -log((1 -p i j )x i j ) (3.4b) s.t. ∑ j∈A x o j = 1, ∀ j ∈ A (3.4c) ∑ i∈A x id = 1, ∀i ∈ A (3.4d) ∑ i∈A x ip -∑ i∈A x p j = 0, ∀i, j ∈ A ; ∀p ∈ A (3.4e) ∑ i∈A x i j ≤ 1, ∀ j ∈ A (3.4f) x i j ∈ {0, 1}, ∀i, j ∈ A (3.4g)
where x i, j is a binary variable that is equal to 1 if the drone moves from AU i to AU j , 0 otherwise. More precisely, this constraint guarantees that once a drone visits cell i, then it must also leave from this cell. The next constraint (3.6e) states that each cell is visited only once.

As indicated in

This problem can be easily converted as a multiple objective shortest path problems (MOSP), which are known to be NP-hard [START_REF] Serafini | Some considerations about computational complexity for multi objective combinatorial problems[END_REF]. One possible solution to deal with this problem is to convert the multiple objectives to one single objective either by using a linear weighted combination of the objectives or by focusing only on one main objective and consider the second objective as a new constraint. Unfortunately, the first approach involves to carefully adjust the weight associated to each objective, which is not straight-forward. In tis case, we propose to formulate the problem as a single objective optimization problem.

We considered the energy consumption as an objective to optimize and we transformed the tracking probability to a new constraint, which guarantees that the rate of successful transmissions of localization messages is above a given threshold denoted δ . Formally:

∑ i∈A ∑ j∈A ((1 -p i j ) -δ ) x i j ≥ 0 (3.5)
In this case, our problem could be expressed as following: min

∑ i∈A ∑ j∈A d i j S x i j (3.6a) s.t. ∑ j∈A x o j = 1, ∀ j ∈ A (3.6b) ∑ i∈A x id = 1, ∀i ∈ A (3.6c) ∑ i∈A x ip -∑ i∈A x p j = 0, ∀i ∈ A ; ∀p ∈ A (3.6d) ∑ i∈A x i j ≤ 1, ∀ j ∈ A (3.6e) ∑ i∈A ∑ j∈A ((1 -p i j ) -δ ) x i j ≥ 0 (3.6f) x i j ∈ {0, 1}, ∀i, j ∈ A (3.6g)

Packet Loss Rate Estimation

In this section we evaluate the transmission capabilities of the radio interface according to the position of UAV and the wireless network stations (noted BS in the following) in the considered area. This evaluation is needed as it gives estimation for the achievable physical bitrate and for the packet loss rate, two parameters used for the optimization of the UAV flight plan in the area. For the achievable physical transmission rate, we need to determine, for each AU, the received power P r and the SINR (Signal to Noise/Interference ratio) in the BS side.

Assuming a transmission power P t for the UAV, the received power P r is easily computed using an appropriate propagation model depending on the distance d between the UAV and the BS. As we consider an open field area, this appropriate model could be either a two-ray ground reflection or a free space, depending on the UAV altitude and the BS height connected to it. The selection between these two models is done according to the Fresnel zone, itself parametrized by the distance d and the antenna heights, through the Fresnel ellipsoid radius r. In both cases, the propagation model consists of only the attenuation of the signal power that depends on the distance between UAV and the serving BS, as following:

P r = Att(d).P t (3.7)
In case of free space model, the attenuation Att FS follows the Friis Formula and depends on the LoS (Line of Sight) distance between the transmitter (Tx) and the receiver (Rx) nodes, on the Tx/Rx gains G e and G r , and on the wavelength λ , as following:

P r,FS = Att FS (d).P t = G e G r λ 4πd 2 P t (3.8)
In case of a two-ray ground model, the distance d * used is the distance between the ground positions of the Tx/Rx nodes. The attenuation Att T R is a function of the ground reflection coefficient L, and the Tx/Rx antenna heights H t and H r , as following:

P r,T R = Att T R (d) • P t = G e G r .(H t H r ) 2 L d * 4 P t (3.9)
We should first determine the distances d and d * , depending on the UAV coordinates (x, y, z) (its location in the AU i ) and on the coordinates (X bs ,Y bs , Z bs ) of the serving BS. This will be used to calculate the value of r = 1 2 √ λ .d (radius of the 1 st Fresnel ellipsoidal zone) that will determine the choice of the appropriate model.

As we consider a discrete area model, the received power for each AU i consists in averaging the received power P r (i) in the entire surface S AU i . Since we consider a hexagonal shape for our area units, we can average the received power on each AU i by splitting the computation on each sub area A 0 , A 1 , A 2 , A 3 and A 4 , as illustrated in the figure 3.4. We can then compute the average P r (i), for AU i assuming a constant P t (i.e. no power control) as following:

P r (i) = P t . 1 S AU i S AU i Att (s(d i )).d 2 s (3.10)
After decomposition into the constant and the variable terms of the attenuation, A c and A (s(d i )) respectively, P r (i) becomes:

P r (i) = P t .A c . S A 0 A (s(d i )).d 2 s + S A 1 A (s(d i )).d 2 s + S A 2 A (s(d i )).d 2 s + S A 3 A (s(d i )).d 2 s + S A 4 A (s(d i )).d 2 s (3.11)
Assuming a hexagon side length (or radius) of a, we give below an example for the average attenuation in each sub-area A k . For sub-area A 0 , it consists in a trivial calculation for the attenuation term:

S A 0 A (s(d i )).d 2 s = Xi+l Xi-l Yi+L Yi-L A (x, y) .dy.dx (3.12)
where l = a 2 and L = a

For the other terms (sub-areas A k , k ∈ {1, 2, 3, 4}), as the variables are interdependent, we should first determine the integration interval. We give an example for sub-area A 1 .

S A 1 A (s(d i )).d 2 s = Xi max Xi min Yi max Yi min A (x, y) .dy.dx = Xi max Xi min Y i + √ 3.(x-X i -a 2 )
Yi min A (x, y) .dy.dx (3. [START_REF] Bertuccelli | Robust adaptive markov decision processes: Planning with model uncertainty[END_REF] where Xi min = Xia ; Xi max = Xi -a 2 and Yi min = Yi.

The constant value of A c and the variable A (s(d i )) depends on the selected propagation model. In Free Space environment A c FS = Ge.Gr.λ 2 16π 2 .S AU i = Ge.Gr.λ 2 8π 2 .a 2 √ 3 , and A (s(d i )) is computed according to the coordinates (x, y) of the UAV in the sub-area A k of AU i as following:

A (x, y) = A FS (x, y) = 1 √ (x-X BS ) 2 +(y-Y BS ) 2 +(z-Z BS ) 2 2 .
However, in the case of Two Ray ground environment A c T R = Ge.Gr.L 4 (z.Z BS )

S AU i = 2.Ge.Gr.L 4 (z.Z BS ) a 2 . √ 3 and A (x, y) = A T R (x, y) = 1 √ (x-X BS ) 2 +(y-Y BS ) 2 2 .
Once P r (i) is determined, and assuming that the UAV connects to the BS that receives the highest power signal, the SINR(i) is computed for each AU i using the noise/interference power value. We then determine the MCS (Modulation and Coding Scheme) that should be selected by the AMC and which gives the transmission rate Rate(i) in considered AU i . In this case, the SINR(i) is equal to:

SINR(i) = 10.log P r (i) P Noise (i) + P Inter f (i) (3.14)

Link Reliability

The next step is to derive a transmission error rate for each frame and in each Area Unit. This value will give us the link reliability in each AU i and hence for each transition AU i → AU j .

In each AU i , a SINR(i) has been computed and is used to compute the ratio of energy per symbol to noise, E s /N 0 with E s /N 0 = SINR. B R , with R and B the symbol rate and the channel bandwidth respectively.

Assuming that noise and interference can be considered as a whole as an additive white Gaussian noise (AWGN) we then compute symbol error rate P sym using the well-known complementary error function erfc which gives the probability of exceeding a threshold x.

For BPSK for example, we have this well-known expression based on energy ratios E s /N 0 :

P sym = 1 2 . erfc E s N 0 (3.15)
For M-QAM (M = 4 gives QPSK), we use the following equation as explained in [pro]:

P sym = 1 -1 -(1 - 1 √ M ). erfc 3.E s 2(M -1).N 0 2 (3.16)
Assuming a Gray coding, we then compute the bit error rate (BER) or probability P bit , depending on the coding scheme

P bit = P sym log 2 (M) (3.17)
where M is the number of symbols in the constellation of the considered modulation scheme.

Once the BER P bit is computed, we can deduce transmission success probability P succ of each frame according to the turbo code hamming distance which gives the maximum acceptable number of erroneous bits N berr per frame.

Assuming an MPDU size of D and a coding rate of C R , the hamming distance D hamm for LDPC turbo codes used in WiFi network is given by:

D hamm = n -k + 1, with n = k C R , k = D and N berr = D hamm -1 2 = n-k 2 .
Hence the P succ is computed as following:

P succ = n-k 2 ∑ b=0 n b .BER b .(1 -BER) (n-b) (3.18)
Then, the mean number of frames received successfully

E[N t ] = N max ∑ t=0 t. N max t .(1 -P) t .P N max -t (3.19)
where N max is the maximum number of transmitted frames.

We deduce the mean number of frames received successfully for a AU i → AU j transition which is the sum for each AU and for each mean number of frames N max (i) sent in the considered AU i . Note that as we suppose no MAC retransmission (retry limits set to 0), the packet loss rate will be equal to the frame loss rate.

E[N i j ] = E[N t (N max,i )] + E[N t (N max, j )] (3.20)
N max (i) in each AU i depends on the packets rate (PckRate) generated and on the mean sojourn time in the considered AU i . The sojourn time itself depends on the distance to travel in each AU i and on the UAV velocity S.

N max,i = PckRate. dist(AU i ) S (3.21)
We then compute the loss rate P i j for each transition AU i → AU j . P i j is needed in equation (1f) and is deduced from the loss rate in each considered AU i , P i = 1 -P succ (i):

P i j = N max,i P i + N max, j P j N max,i + N max, j (3.22)

Results

In this section, we analyze the performances of our proposed path planning algorithm. We consider a scenario with an area size of 250m × 250m. We vary the number of BS from 5 to 35 BSs with random positions. We consider the antennas gains as constant. Despite the UAV mobility and the use of omnidirectionnal antennas, this assumption is reasonable as we consider small difference between Tx and Rx heights (UAV and BSs). Moreover, as we consider constant UAV velocity S and uniform trajectories in each Area Unit, we can fix the distance traveled in each AU and hence the number of transmit packets N max , i.e., N max,i = N max, j ∀i, j ∈ A. We also run 20 times each simulation. Table 3.2 summarizes all our pre-defined parameters. For our simulations, we use MATLAB in order to compute the packet loss probability P i j and in order to resolve our optimization problem we used CPLEX. In figures 3.5 and 3.6 we show an example of the perceived SINR where we randomly deploy a wireless network with 25 base stations. As we can see, some area units have good SINR while others offer a bad SINR. In this case, it is more judicious for drones to follow a trajectory that maximizes the tracking process by maximizing the packet tracking delivery along this trajectory. Note that we considered an AMC function parameters as designed in [cis]. In order to illustrate our proposal, we plot in figures 3.5 and 3.6 the obtained path compared to the shortest path (using Dijkstra's algorithm) for δ = 0.1 and δ = 0.9 respectively. As we can see in 3.5, when we fix the delivery threshold to δ = 0.1 the obtained path, in yellow, is very close the shortest path and has exactly the same length. However, we can see in figure 3.6 that if we increase the tracking accuracy (δ = 0.9) we obtain a more complex path and much longer than the shortest path. We can also notice that the followed path is matching the positions of the deployed base stations. In figure 3.7, we plot the path length of the obtained path when varying the number of deployed wireless base stations (from 5 to 35) and for different tracking accuracy (δ = 0.2, δ = 0.4, δ = 0.6, δ = 0.8). We can clearly notice that more we increase the tracking accuracy longer is the path. This observation is expected, since increasing the accuracy lead to more winding path in order to guarantee this accuracy on the overall path. However, when we increase the number of deployed base stations the path length tends to be reduced since we are increasing the possible solutions.

Finally, in figure 3.8, we plot the percentage of time where the CPLEX solver was able to find a solution for a given number of base stations and a given tracking accuracy. Our constrained optimization problem is unfeasible when both the current positions of the base stations as well as the required accuracy are too strong to find a path between the source and the destination. As we can see, it is almost always possible to find a solution if the tracking accuracy is reduced (small values of δ ). However, when we increase the accuracy while reducing the number of base stations, the number of obtained solutions to our optimization problem decreases.

Path planning in 3D environment

In addition to the 2D path planning, we are also interested in this chapter 3D path planning.

Indeed, in a real environment, the drones evolve in a three-dimensional environment. In this case, we start by discretize the z-axis, which corresponds to the set of possible altitudes for the drone. Then, we consider a new directed graph G ′ = (V ′ , E ′ ), where V ′ is the set of vertices and correspond to the set of AUs for all possible altitudes. E ′ is the set of edges and denotes the possible movements followed by any drone in order to move from one AU to any another adjacent AU. However, since we are in 3D environment, eight possible movements are allowed. Indeed, in addition the to the six possible movements in 2D du to the hexagonal shape of the cells, we also have two possible movements when the drone changes its altitude. According to the last considerations, we can easily use the same optimization problem defined in 3.6 in order to compute the optimal path in 3D environment. However, we need to adapt investigate the impact of the 3D environment on the packet loss rate.

3D Radio Model

In this sub-section, we determine the impact of the 3D space movements on the packet loss rate through BER and SINR variations. This impact is mainly due to the received power P r variability which is more important in a 6DoF context (6 degrees of Freedom in 3D for the UAV/Drone) compared to a 2DoF context (sections 5 and 6).

As we consider 3D planning, i.e., UAV altitude can also change, we should especially take account of the antenna radiation pattern which was not considered in the section above. This could lead to significant variation in the receiving power, in addition to the impact of the variation of the propagation environment which will also be more important. Actually, the altitude variation while UAV is moving will lead to switch between appropriate propagation models as well as finding computing the effective antenna gains that mainly depend on the relative positions (UAV and BS) and the orientation angles.

Considering the attenuation Att computation in the received power equation, this should then take account of the UAV coordinates positions (X i ,Y i , Z i ) as well as its orientation angles (θ e , ϕ e ).

P r = Att(X i ,Y i , Z i , θ e ,
i ,Y i , Z i }, {X BS ,Y BS , Z BS }.
We deduce from these coordinates the distance d and ground distance d * as explained in the section above.

d = (x e -X r ) 2 + (y e -Y r ) 2 + (z -Z r ) 2 d * = (x e -X r ) 2 + (y e -Y r ) 2 (3.24)
Assuming a pattern in symmetry to the horizontal plane (x y) plane (no tilt considered), with z-axis as the site angle reference and x-axis as azimuth angle reference, we will obtain the elevation gain angles θ i shown in figure 3.9.

Fig. 3.9 Elevation angle gain determination (side view)

If we consider omnidirectional radiation in the azimuth of the considered sector, only elevation pattern, i.e., the angles θ ′ e and θ ′ r will have impact on the received signal. We must also consider azimuth angles ϕ i as shown in the figure 3.10.

θ ′ r = π + θ ′ e (3.27)
Then, azimuth angles ϕ ′ e and ϕ ′ r can be determined as well.

ϕ ′ e = arccos X rx e d * (3.28)

ϕ ′ r = π + ϕ ′ e (3.29)
As explained above, we do not consider tilt angle, which means that the roll and pitch angles effect on the ray patterns can be neglected. This will lead to consider θ r = θ ′ r , θ e = θ ′ e , ϕ r = ϕ ′ r and ϕ e = ϕ ′ e which is only directly impacted by the yaw value of the UAV and the relative position to the serving BS (heading and coordinates).

Once computing those angles, we can easily replace the antenna gains values G e (θ e , ϕ e ) and G r (θ r , ϕ r ) by the value given by the ray patterns of the respective antennas.

In addition to a fixed tilt angle, for the BS and UAV, another realistic assumption is made for the orientation of the UAV antenna which are considered as z-axis oriented. That means that we do not have to deal with the polarization impact (supposed constant thanks to the quasi-fixed tilt assumption).

Hence, for each UAV position (or altitude in the considered AU i ground position), we are able to find the appropriate antennas Gains (Rx and T x, BS and UAV respectively), assuming the knowledge of the radiation pattern (usually given by manufacturers). We can notice that for usual antennas like dipole antennas, radiation patterns will show an omnidirectional antennas with neglectable effect on azimuth angle and hence of yaw rotation of the UAV.

Once the value of the received power P r is estimated, we will determine the SINR as shown in section 5 above, and hence the BER and packet losses P i j as computed in the equations in section 6.

Results

As in 2D enviroenemnt, we can also resolve our optimization problem for 3D environment using CPLEX. However, since we are considering several possible altitudes, we are also highly increasing the complexity of the problem. In this case, it does not become possible to solve the problem even for small realistic configuration.

Conclusion

Tracking is a fundamental mechanism that needs to be integrated into UAVs in order to enforce safety. To the best of our knowledge, this work is the first one to propose a path planning of UAV with the aim of minimizing the delay to reach a destination, while ensuring that the UAV is able to transmit periodically its positions using terrestrial wireless networks, with a maximum threshold on packets success. We formulate the above problem as an Integer Linear Problem. To this purpose we also express analytically the packet loss rate of tracking messages depending on the UAV location and the wireless network coverage. Solving the ILP

Problem Statement and System Description

In this chapter, we are considering a package delivery service using UAVs. Basically, a UAV has to deliver a package from a depot or warehouse to a predetermined destination or consumer. The main objective of this chapter is to provide an off-line path planning that aims to minimize the delivery delay with respect to the UAV's residual energy constraint while ensuring an optimum tracking of the UAV at the operator side.

In the following, our system is modeled as 2D area A without any obstacle. The projection of the flying area is represented by a rectangular with length of x max and a width of y max .

We suppose that the drone D rone keeps the same altitude h from the starting point O to the destination D. A set of wireless receivers or Base Stations BS = {BS 1 , BS 2 , ....BS n } is deployed randomly at different altitudes in order to provide a wireless access infrastructure.

In addition, we assume a partially noisy environment with the existence of a certain number of noise nodes N oise = {N N1 , N N2 , ....N Nn } deployed within A and uses the wireless infrastructure as an access network. We also consider that the drone has a limited flight autonomy ϒ and is equipped with a wireless interface in order to communicate with the other Base Stations.

The latter has a short sensing range compared to the size of the region of interest. Moreover, we consider that A is discretized into C hexagonal cells of the same dimension. This implies discrete position for the UAV, which then is supposed to be located in the center of the considered cell.

Our goal is to determine a path or a set of paths that maximize the drone localization and tracking using a wireless network, such as cellular or IEEE 802.11x technologies. For this purpose, we assume that after each period T , the drone generates a message of size d bits containing its identification, position and speed. The on-board wireless interface tries to send each generated message to the remote UAV monitoring and controlling system via the set BS while the jamming nodes attempt to overload the network by sending messages in a continuous and unpredictable manner to the BS. For that reason, a message can be corrupted or even lost due to possible interference and collisions. The opportunity to transmit also depends on the radio coverage, the capacity of the related wireless technology and the drone's location. However, unlike the previous chapter, where we compute the Reception Packet Rate RPR only by considering the channel condition, in this chapter we computed the RPR by considering a specific MAC layer. Indeed, using intensive simulations with OMNeT++, under different conditions we were able to estimate the average Received Packet Rate at each cell in A.

Problem formulation

In order to describe the proposed mathematical model that represents the optimum path planning problem, it is useful to introduce the following notations and definitions.

First, we model the problem with the help of a directed and valued graph G consisting of n hexagonal cells, where the valuation of an arc is comprised between 0 and 1, indicating the reception packet rate (RPR) on that arc. Finally, we define c i j the cost of using the arc going from cell c i to cell c j . The flow going that way is denoted by a binary variable, noted as x i j , where

x i j =
1, if the drone moves from cell i to cell j 0, otherwise. (4.1)

The cost of a path represents its reliability and it is set to the product of the RPR of each cell forming the resulted path:

Path cost = n ∏ i=1 n ∏ j=1 RPR i j * x i j (4.2)
As, the RPR i j is comprised between ]0, 1], this means more we add a new cell to the path more the path cost is low. Thus, the first two objectives for our drone path planning problem are reported as follows: In addition to the last two objectives, we also add a third objective that aims to minimize the tracking time loss of the drone, by avoiding passing through several adjacent cells with low RPR. For example, as illustrated in Fig 4 .2, if we have to choose between the path a (0.9, 0.9, 0.9, 0.1, 0.1, 0.1) and the path b (0.9, 0.1, 0.9, 0.1, 0.9, 0.1) with the same length and the same average packet delivery ratio, then we have to privilege the solution b rather than a.

The privilege of the solution b is motivated by the fact that we have fewer adjacent cells with low packet delivery probability. The main benefit of this choice is to have the communication rupture spaced out on the time rather than having a long time with no communications. The principle of averages on a shifted window is interesting in the case when we use prediction algorithms. Basically, we need to compute an average data based on the most recent results in order to create forecasts. Indeed, the most recent data are more important or

K i = (RPR i + RPR i+1 )/2.
Since the geometric average is less sensitive than the arithmetic average to the highest or lowest values of a series, we propose the following cost function:

f (K) = n-1 n-1 ∏ i=1 K i (4.5)
Thus, by applying the formulas 4.5 on the previous paths a = {0.9, 0.9, 0.9, 0.1, 0.1, 0.1} and b = {0.9, 0.1, 0.9, 0.1, 0.9, 0.1} we will get: a = {0.9, 0.9, 0.5, 0.1, 0.1} and f (a) = 0.33, and b = {0.5, 0.5, 0.5, 0.5, 0.5} and f (b) = 0.5. Since we need to maximize the function f , the path b will be selected.

Finally, in addition to the last objectives, we add a new constraint related to the UAV's maximal flight distance:

∑ i∈A ∑ j∈A c i, j x i j < δ , (4.6)
where δ is the maximum distance that the UAV could perform based on the UAV autonomy.

Energy Consumption Model

In order to compute the drone autonomy, we estimate in this section the energy consumed by each drone according to its characteristics.

The main challenge for the construction of rotary-wing drones is to maximize its autonomy for a given mass, while providing the power needed for propulsion and for the embedded instruments. It is therefore important to carefully manage the available energy and the path planning with each other to have the best overall. In fact, recent progress achieved on Lithium battery type allowed the electric flight to achieve a really interesting autonomy for entertainment or local missions, but still far from being effective for longer trips and missions.

In this chapter, we consider a quad-copter which is a drone with four rotors at the ends of a cross. The four rotors provide the vertical force (Thrust) that allows the unit to rise. In flight, the quad-copter may evolve following its roll, pitch and yaw axes and also in translation in all directions, fig 4.3. Basically, the dynamic model of quad-rotor can be seen as a system

where the spatial evolution's are the outputs and the voltage of each engine are the inputs, fig 4.4. Motion is achieved by changing the rotation speed of one rotor or more. Thus, to control the roll of the UAV, it is sufficient to act on the rotational speeds of the motors 2 and 4. In the same way, the pitch of the UAV is controllable by acting on the motors 1 and 3.

Furthermore, maintaining a stable flight requires an equilibrium and a balance of all forces acting upon a drone. Weight, lift, thrust and drag are the acting forces on a drone.

These Forces are vector quantities having both a magnitude and a direction and consequently, the motion of the drone through the air depends on the relative magnitude and direction of these forces. A general derivation of the thrust force equation shows that the amount of thrust generated depends on the mass flow through the rotors and the change in rotation speeds of the four propellers.

In fact, several methods exist in the literature allowing to have an order of magnitude of the power of a propeller, such as the blade element theory (BET) and the Froude theory.

Even if these methods can provide a more precise result, they are based on a certain number of coefficients which cannot be computed only after empirical tests, like Thrust Coefficient, Torque Coefficient, Power Coefficient, etc. In addition, they obtained coefficients are specific to the tested propeller at a specified rotation speed and cannot be used for other types of propellers. Basic drone manoeuvres include take-off, hovering, changing altitudes, and landing. This manoeuvre requires different rotors and propeller rotation speeds. To our knowledge, the best method to approximate drones power consumption is to use formulas In the following, the Boucher formula is used. In fact, the latest was used to compute the flight autonomy and the power consumption for a real quadcopter drone type of Phantom 3 Advanced. The results were very close to the ones presented by the manufacturer, see Tab 4.1:

P p = K * Diam 12 4 * Pitch 12 * N t 1000 3 (4.7)
with P p in Watt, Diam and Pitch in inch, and N t in tr/mn. K is an adjustment parameter, which depends on the propeller type, (APC: 1.11, Graupner: 1.18, Zinger: 1.31, Top flite: 1.31, etc..).

To begin with, let's give some definitions related to the propellers. A propeller can be defined as a mechanical device formed by two or more blades that spin around and produce a propelling force. Generally, we identify a propeller by its diameter followed by its pitch, all usually expressed in inches or cm. Diameter is the distance across the circle made by the blade tips. Usually, Diameter increases for propellers used on slower drones or aircraft and decreases for faster ones. Further, if all other variables remain constant, diameter will increase as power increases and it will increase as propeller rotation per minute (rpm)

decreases. Pitch is defined as the distance a propeller can move in one revolution if it was moving through a soft solid, like a screw through wood. To link the aerodynamic properties of the propeller to the power and the engine speed, we will need three formulas:

• The power supplied by the propeller P p in watts;

• The thrust of the propeller in Kg:

T p = 4.9 * Diam 3 * Pitch * N 2 t (4.8)
• And the speed of air passing through the propeller of in Km/h:

S air = 60 * Pitch * N t (4.9)
where Diam is the propeller diameter in meter, Pitch in meter and N t is the number of thousands revolutions per minute (rpm).

In addition to the last formulas, we also need to compute:

• The pitch: Pitch = π * Diam * Tang(α), (4.10)

• The power consumed by the propeller

P C = P p * C e * R e (4.11)
• The drone flight endurance can be expressed as in [? ], and by ignoring the consumed power at the idle state we get:

F Endurance = B C /P C (4.12)
where R e and C e are the rotor efficiency and the controller efficiency, generally fixed at 75% and 98% respectively, α is the attack angle of the propeller, B C the Capacity of the battery, P C is the Power consumed by the propellers.

Since the power is the rate of doing work, it is equivalent to the amount of energy consumed per unit time. If work is done quickly, more power is used and if work is done slowly, very little power is used. Thus, the energy consumed by the propellers to ensure the thrust forces required for the flight can be expressed as:

E Mvmt = P C (t)dt (4.13)
Finally, using the last equation we can derive the energy c i j required for a drone to fly from cell i to cell j. for each cell c i ∈ G do 3:

P[c i ] ← 0 4: Π[c i ] ← nil 5:
end for 6:

P[c o ] ← 1 7: F ← G 8: while F ̸ = ∅ do 9: choose c i ← max P[c i ] 10: F ← F -{c i } 11:
for each cell c j ∈ neighbors(c i ) do In order to evaluate the performances of our proposed path planning algorithm, we carry out a set of simulations. We have implemented and integrated our path planning strategy in the OMNET++ Simulator. In our simulations setup, we have considered the IEEE 802.11 standard with a channel capacity of 1 Mb/s. We assume an area of 1000 meters by 1000 meters, where we randomly deployed 10 base stations (BS) uniformly. In addition to the base stations we also randomly deployed a given number of jamming nodes (from 10 to 50, with a step of 10) in order to simulate the noisy environment. More precisely, each jamming node transmits with a frequency of 100 Hz packets to the nearest base station, which can cause interferences and collisions. We assume that all the nodes (except the drone) are static.

Finally, we consider a moving drone at an altitude of 60m. This drone sends with a frequency of 10 Hz its position to the nearest base station.

Using OMNET++, we were able to compute the RPR map for a given the presence of transmission and reception errors due to a jamming nodes traffic. In the following, we provide some results according to the simulation parameters summarized in the table 4.2. In order to illustrate the performances of our algorithm, we plot in figures 4.10 and 4.11 the obtained path using the shortest Dijkstra and our approach for a drone altitude of 60m and for 20 and 50 jamming nodes respectively. We decided to compare our algorithm to the shortest path using the well-known Dijkstra algorithm since to the best of our knowledge there is no other work similar to our work in the literature.We can clearly notice that in the case of our approach, the obtained path tries to get as close as possible to the base stations in order to increase the probability that the positioning packets sent by the drone are successfully received by the BS. We can also observe that the path length when considering 20 jamming nodes is slightly longer than when we consider 50 jamming nodes. As indicated earlier, using our approach, we are able to provide other paths, called near optimal paths shorter than the optimal one but eventually with less important RPR, as illustrated in figure 4.12. It is clear, that even for the shortest near optimal path with a distance almost equal to the Dijkstra short path length, the RPR is even important. The latter conclusion can also be validated from figures 4.13 and 4.14. Indeed, in figure 4.13, we plot the received packet rate and the path length for all the paths that we consider near optimal. We can clearly notice that even if we choose a path with a length close to that obtained by Dijkstra, the received packet rate remains better. The same result can be seen in figure 4.14. To understand the impact of increasing the interferences on the path length and RPR, we varied the number of the jamming nodes simulating a noisy environment. We set the drone altitude to 60m and we measure the length of the optimal paths and their respective RPRs.

As we can observe in figure 4.15 and 4.16, if we increase the number of noise nodes, we gradually decrease the quality of the signal and subsequently the RPR and the path length also decrease. In fact, in case of good radio coverage, the drone tends to be attracted to the cells with higher SINR, which represent the BS locations. On the other hand, when we degrade the SINR, the drone tends to take the shortest path to its destination, since even if we get close to the base stations will not increase the received packet rate. In order to evaluate the efficiency of our solution, we simulated the proposed algorithm for a thousand random destination points in an environment with low signal coverage by setting the number of jamming nodes to 50 nodes and the drone altitude to 60m. We compare for all these points the resulted paths with Dijkstra's short path in terms of length and RPR.

The comparisons are illustrated in the figures 4.17 and 4.18. As we can observe, the received packet rate is highly increased. The difference varies from 0.15 to 0.55 even for a path with length closer to Dijkstra short path length. In figures 4.19 and 4.20 we illustrate the impact of the drone speed on the packet received rate and the consumed energy. The results were obtained using the Omnet++ simulator. We vary the drone speed from 10m/s to 18m/s, which are the most common drone speeds, and we compare the simulator results to the theoretical ones. We can notice that the RPR remains almost the same for drone speed varying from 10m/s to 13m/s. However, this rate decrease once the drones exceed the speed of 14m/s. Almost 10% of the tracking capability is lost due to the drone's speed. In addition to the same payload, a drone will consume about a double in terms of energy when increasing the speed from 10m/s to 18m/s. This consumption is due to the increased rotational speed of the propellers.

3D path planning with obstacles

In addition to the 2D path planning, we are also interested in this chapter on how we can adapt our proposal to 3D with obstacles. Indeed, in a real environment, the drones evolve in an three dimensional environment and more of that with the presence of obstacles like buildings, walls, trees, hills, cars, etc. In fact, the obstacles can highly impact the signal propagation. Indeed, when the signal propagates through space it passes through physical objects present in that space. When the signal passes through, its power decreases in case if it reflects from the surfaces of physical objects or absorbed by their material.

There are various ways to model this effect, which differ in the trade-off between accuracy and performance. In this work, we used the INET framework to evaluate the influence of the existence of such obstacles on the drone path planning. The obstacle models that exist in this framework are of different characteristics, shape and properties, like, glass, brick, concrete, etc. It utilizes the physical environment model to query the obstructing physical objects.

Our objective is than to evaluate our algorithm in 3D environment and in the presence of obstacles.

According to the last considerations, we also need to see who we can adapt our proposed algorithm to the 3rd dimension. In fact, our approach can be very easily adapted to 3D environment by discretizing the altitude of the drone to obtain a new 3D graph. This graph is composed of a set of directed and valued graphs G h for each altitude h. Here again, all G h consist of n hexagonal cells, where the valuation of an arc indicates a received packet rate. In addition, each adjacent graph are connected to each other through additional arcs between the cells having the same coordinate, which means that we allow the drone to move from one altitude to another altitude by considering only one step at a time. i.e drones can only move from cell AU i h to cell AU i h+1 or cell AU i h-1 . Once connected, the set of graphs G h form a global graph denoted G. They're after, we can compute, for each possible altitude, the received packet rate depending on the locations, the height and the presence or not of obstacles. Finally, we can apply our proposed algorithm.

Results

In order to evaluate the performances of our proposal, we consider an area A with a set of obstacles. We consider a set of jamming nodes randomly deployed within A. The BS are also deployed at different altitudes, as we can see in figure As illustrated in fig 4.24 our algorithm is able to generate a path for a drone from the origin to its destination in 3D while avoiding obstacles and maximizing the tracking capabilities.

For this example the total distance travelled by the drone is 2810m with a recieved packet rate RPR around 0.9188 comparing to the dijkstra shortest path length of 1840m and 0.585 of RPR ratio.

We can clearly notice in figure 4.25 which is the 2D projection on the space that the computed path allows the UAV to avoid safely low SINR areas and thus obstacles.

Conclusion

In this chapter, we propose a path planning algorithm for UAV. Our approach doesn't only generate one single optimal solution but a number of other near optimal paths with a tradeoff between length distance and probability of localization determined by the drone flight autonomy. Therefore, we choose the best path suited to the need of localization and tracking but also to the capability of the UAV in terms of energy autonomy. More precisely, if identification, localization and tracking are the main concerns than we can choose the longer path which insures a high communication probability and if the UAV energy autonomy is a priority than we need to choose the suitable path length according to the battery duration. We also assessed our algorithm in 3D as in 2D context and in environment close to the reality by considering a partial noisy context.

Chapter 5

Multi UAVs path planning and Tracking

Motivations

In this chapter, we are interested in the use of the drones for data gathering. In fact, mobile data gathering is a well-known technique, which uses a mobile collector (e.g. a communicating robot) that moves toward some sensors to collect the data. A better energy saving can thus be obtained for each sensor, compared to the conventional approach which requires the setting and the maintenance of end-to-end network paths between the sink and the sensors.

This gain is higher when sensor nodes are deployed over a non-dense area. However, issues might arise when the sensors are spread over a very large area. Typical problems are related to the capacity of the mobile collector to reach all the sensors, either due to the terrain obstacles or because of its energy limitation.

To address this challenge, recent research works investigated the use of UAV (Unmanned Aerial Vehicles) as Data Collectors in large scale Wireless Sensor Networks [START_REF] Ma | Fairness-Aware UAV-Assisted Data Collection in Mobile Wireless Sensor Networks[END_REF][START_REF] Wang | Efficient aerial data collection with uav in large-scale wireless sensor networks[END_REF]. UAVs can quickly obtain an accurate data over large areas that are difficult or dangerous to access by traditional means. In addition the data can be collected when the need appears and usually at a lower cost, compared to other approaches. Even though UAVs are gaining a wide popularity among users, at least for recreation, the development of UAVs with larger level of autonomy is an essential requirement to exploit this technology at its highest economic potential. Unfortunately, battery limitation of nowadays civilian UAVs does not allow yet long-term missions of small UAVs. To overcome this limitation, we investigate in the chapter the use of multiple UAVs to gather data from sensors that are spread over large scale areas.

The use of a swarm of UAVs for data gathering raises new considerations, such as the required number of UAVs and path planning of each UAVs. Different objectives and constraints might be integrated to the path planning problem. In this chapter, we are interested in minimizing the travel duration with respect to the energy autonomy while achieving a better fairness regarding energy consumption among UAVs and avoiding collisions. Tracking is another fundamental functionality that needs to be considered in order to provide the previously mentioned collision avoidance capability. It refers to the capacity of a remote system to follow the UAV trajectory by reporting its positions. As in the last two chapters, we consider that the UAVs use terrestrial base stations (e.g. WiFi or cellular technologies)

to periodically transmit their coordinates toward a remote monitoring system. Since these wireless technologies are subject to packet losses, another criterion in our multi-UAVs path planning problem is to compute paths that ensure the transmission of the tracking messages with a satisfactory Quality of Service (QoS) level. Precisely, we aim at computing the UAV routes that satisfy a threshold on the minimum average packet delivery ratio.

As a matter of fact, an adequate path planning strategy is needed to improve effectiveness of the whole system and should be combined with other elements in order to comply with the mission goal and its requirements. Indeed, mission nature, number of drones, available payloads and the area characteristics strongly influence the path. Solving the above multiple UAVs path planning optimization problem for large scale area, with the objective to minimize the travel duration with respect to the energy autonomy, a better fairness regarding tour among the drones, avoiding collisions and finally a given packet delivery along the path to increase the drone tracking is not trivial and is strongly Np-Hard.

In this chapter, we are not focusing on the resolution of the problem but on the evaluation of the obtained results, notably in its component inherent to the network communications, path loss, tracking, localization, rate of the data gathered from the ground sensors, UAV speeds, as well as the ground sensor transmission power and the number of jamming nodes. However, the problem resolution was done by our colleagues from LIPN Laboratory. The proposed solution on a column generation procedure and more precisely on a path-decomposition formulation of the problem.

The remainder of this chapter is organized as follows. Section 5.2 briefly reviews related work; Section 5.3 describes the system and the platform used for the drones tracking and data gathering evaluation. The proposed approach and the obtained results are then evaluated in different scenarios. The results are reported in Section 5.4. Finally, section 5.5 includes some conclusions and future developments.

State of the Art

The use of mobile devices for data gathering in a wide wireless sensor networks has recently been gaining more attention [START_REF] Khan | A comprehensive study of data collection schemes using mobile sinks in wireless sensor networks[END_REF]. It is clear that the use of mobile nodes in a wireless sensor network reduces the energy consumption for the static nodes while trying to forward data to a sink node and therefore extends the lifetime of the network. Different studies were carried out in the sake of finding the optimal paths of a mobile node to collect data. The best known approach for path planning is to use the Traveling Salesman formalization of the problem (TSP) [START_REF] Miller | Integer programming formulation of traveling salesman problems[END_REF]. Some enhancements have been brought in [START_REF] Christofides | Exact algorithms for the vehicle routing problem, based on spanning tree and shortest path relaxations[END_REF] to avoid subtours and more recently, this problem has been generalized to multiple traveling salesmen problems (m-TSP) [START_REF] Bektas | The multiple traveling salesman problem: an overview of formulations and solution procedures[END_REF].

[65] presented an approach on how to optimize the energy consumption and data delivery latency trade-off among a wireless sensor network. According to the authors, finding a minimum-cost path that intersects with the communications range of all sensors is NP-hard.

The path selection problem was thus formulated as label-covering tour and an approximation algorithm based on Euclidean distance was presented.

In the same frame [START_REF] Khan | A comprehensive study of data collection schemes using mobile sinks in wireless sensor networks[END_REF] presented a solution to deal with the problem of the energy and to prevent the formation of the energy holes phenomena among a wireless network.

Comparatively to the cluster-based and the classical rendez-vous methods, the authors proposed a hybrid unconstrained movement pattern for a single mobile sink with the aim of finding the near optimal traveling tour based on weighted rendez-vous planning. Even the solution was extended to use the Shortest Path Tree and Steiner Minimum Tree, the solution remains applicable for a single mobile sink.

Another heuristic based on genetic algorithms and local search was proposed by [START_REF] Gao | Efficient data collection in wireless sensor networks with path-constrained mobile sinks[END_REF].

The latter is considered as data collection scheme that allows at the same time to increase the network throughput and to reduce the energy consumption of the network nodes. The solution was also improved by a communication protocol to allow more flexibility within the dynamic topology of the network.

Alternatively, [START_REF] Stirling | Energy-Time Efficiency in Aerial Swarm Deployment[END_REF] compared three strategies to deploy a swarm of UAVs for a research mission with objectives to reduce energy costs, search time and travel distances. According to the authors, these strategies are completely decentralized, scalable and require low computational and communication resources. A multi-objective function is used that combines linearly energy and time into a simple single parameter. However, the authors mentioned that the proposal was confined to a fixed size corridor and properties such as size and open areas may affect the performance of the solution.

Finally, to the best of our knowledge, none of the above works have investigated UAVs path planning for data gathering assuming that UAVs uses terrestrial wireless networks to transmit them locations for identification and tracking purpose.

System description and problem formulation

As introduced earlier, in this chapter, we are considering a data gathering services using a swarm of UAVs. Let's consider, a 2D geographical area A, and we refer to G(N, E) as the graph that indicates the discretization of the area A as introduced in chapter 3. Basically, the graph is built such that the area A is divided into hexagonal cells, each one indicated by a node in N. Moreover, each edge of the set of edges E of the graph has a common length, equal to a specific distance d, and connects two nodes associated with two adjacent cells.

The resulting graph is then a grid graph, where each node has a degree equal to 6, unless it is located on the border of the area. The graph includes a special node o ∈ N, that is the depot, from which all the UAVs start to move. Finally, we consider a set M ⊆ N of static sensors deployed within A and equipped with wireless interface in order to communicate with the drones.

Given a set of drones K, whose cardinality is indicated with |K|, the objective is to determine a tour for a subset of drones in K such that all the deployed sensors are visited and that the overall tour duration is minimized. In order to take into consideration the battery constraint, then we limit the length of each tour that cannot exceed a specific threshold corresponding to the flight autonomy limit. In addition, we want to produce solutions that emphasize the fairness of the tour duration. As a consequence, the lengths of the tours should not differ too much. Additionally, we force that no collisions can occur among the drones.

As in chapter 3, in addition to the last constraints, we also need to consider another constraint that must be satisfied, which is the tracking of the drone's positions using wireless networks, such as cellular or IEEE 802.11x technologies. For this purpose, we assume that a set of base stations is deployed in A at different altitudes in order to provide a wireless access infrastructure. Using this wireless infrastructure, each drone periodically generates a message containing its most recent 3D position. Then, the on-board wireless interface tries to send each generated message to the remote UAV monitoring and controlling system.

The opportunity to transmit depends on the radio coverage and the capacity of the related wireless technology in the drone's location. A message can also be corrupted due to radio transmission errors and discarded at the receiver side. Thus, we also consider a received packet rate probability 0 ≤ δ i ≤ 1 associated with each cell (then with each node i ∈ N) and we want to keep its average value in each route upon a specific threshold ∆ avg .

Finally, the drones cannot change their direction by a 60 degree angle, due to physical constraints, and they cannot visit the same node twice along their route, meaning that we are looking for elementary tours.

This problem can be formulated as a multiple Traveling Salesman Problem-mTSP, where additional constraints are taken into account. It is easy to verify that we are dealing with a strongly Np-Hard problem, as an example we can reduce the mTSP to our problem by making the additional constraints ineffective. The literature is rich of several integer linear programming formulations of the m-TSP. One possible formulation is the one proposed by Christofides et al. in [START_REF] Christofides | Exact algorithms for the vehicle routing problem, based on spanning tree and shortest path relaxations[END_REF].

Such formulation is based on binary variables x k i j s that establish if the edge (i, j) ∈ E is included in the tour relative to vehicle k or not. A similar formulation based on this variable definition can be derived to model our problem, but it is well known that such formulation yields very weak bounds and is impractical to find solutions even for instances of moderate size.

The problem can be alternatively formulated as a set covering problem. In the formulation below, henceforth called SCP, the variables λ r s are binary variables indicating if the route r is assigned to a vehicle or not. The parameter l r indicates the length of r. The solution of such model is impractical even for small instances, where it is impossible to enumerate the set R. However, we can recourse to a column generation to compute valid lower bounds for SCP. The decomposition of the problem and the detail of the proposed solution are not part of this thesis since they were made by our colleagues from the LIPN laboratory (Paris 13 University). For more details, readers are encouraged to read "Drones Path Planning for WSN Data Gathering: A Column Generation Heuristic Approach" for more details on the proposed solution.

In order to assess the tracking of the drones, we need to evaluate the transmission capabilities of the radio interface to get a realistic estimation of the achievable physical bitrate and the packet loss rate at each cell. Thus we need to determine for each cell two parameters, the received power and the Signal to Noise/Interference Ratio SINR at the BS side. The received power is easily derived using an appropriate propagation model depending on the distance between the UAV and the BS. As we consider ground Base stations and ground static sensors, the two ray ground reflection propagation model is used along all the evaluation process. However, the perceived packet loss rate also depends on the wireless network access technology used by drones. In the following, we consider that both drones, base stations and sensors are using the standard IEEE 802.11. In this case, the access method is Carrier Sense Multiple Access with Collision Avoidance (CSMA/CA). Basically, CSMA/CA tries to divide the channel somewhat equally among all transmitting nodes within the collision domain. However, in case when a collision occurs the CSMA/CA use 'exponential backoff' mechanism in order to spread the retransmission over time. Unfortunately, it is difficult to have a model to model the behavior of CSMA/CA in a realistic way. Moreover, the packet loss rate is highly related to the position of the base stations, the drones and the ground sensors.

To this end, we use a simulation approach based on the OMNeT++ 4.61 simulator and the INET framework to compute the Received Packet Rate RPR for each cell in order to take into consideration the CSMA/CA behavior. The Received Packet Rate denotes the proportion of the received messages over the generated ones. Finally, for more realistic scenarios we increase the network load gradually by increasing the number of the jamming nodes.

Performance Evaluation

In this section, we evaluate the efficiency multi UAVs Path planning. Two main objectives were fixed, first, to assess the drones tracking functionality from the start point to the end of the mission, and second, the rate of the data gathered by drones from the ground sensors.

Different scenarios are presented during the evaluation process with different parameters, notably the number of jamming nodes in the network and the drone speeds.

Using OMNeT++ simulator, we were able to generate two maps, the SINR map at altitude h equal to 20m and the Received Packet Rate RPR map in the presence of transmission and reception errors due to a noisy environment and channel congestion. To this end, we deploy randomly at different positions and altitudes 5 base stations in an area of 562m by 562m.

We also vary the number of jamming nodes from 0 to 30. Next, we compute for each cell and for a given altitude h = 20m the SINR and the RPR maps. The table 5.1 summarizes the predefined parameters used in our simulations. Thereby, for each cell:

• The received packet rate PRR is computed as the proportion of received messages over generated ones;

• The signal-to-interference-plus-noise ratio SINR is computed and the value is determined by the sensor characteristics, the location of the sensors, the measurement methods etc; In figure 5.1 we illustrate an example of the SINR map that we obtain when we consider 25 jamming nodes. The cells with cold colors represent an area with no or lower signal coverage, meanwhile the cell with warm colors indicates areas with higher quality of signals.

We can clearly see that closer we get to the base stations the better the signal quality is. This means that the packet losses are more important when we get far from the base stations. On the other hand, colder cells indicate mostly week RPR values. In addition to the RPR values, we also illustrate the obtained path generated by our approach in each map with their respective length and average RPR. The selected paths maximize the average RPR along the path. We can notice that increasing the number of jamming nodes leads to an increase of the interferences within the area and thus a decrease in terms of Received Packet Rate. We also plot in figure 5.6 the average RPR and the fairness between the paths length when considering different number of jamming nodes. We can clearly notice that increasing the network load by increasing the jamming nodes leads to a decrease of the maximum average packet delivery for the drone. In fact the RPR falls from 98% with 0 noise nodes to 55% with 30 noise nodes. In addition to the average received packet rate we also compute, using Jain's index, the fairness between the tour length of the drones. As we can notice the obtained fairness index is very close to 1 which means that the routes lengths for all the drones are very close to each other and thus consumes the same amount of energy.

In order to illustrate the quality of the tracking process at the drone controller and monitoring side, we plot in the fig 5.7 the drone trajectories in the case of 0 and 30 jamming nodes. With no jamming nodes, figure 5.7a, the drone trajectories are illustrated with a continuous line indicating a good reception of the drone's messages throughout the flight, except in areas with no radio coverage. However, as illustrated in figure 5.7b and with a noisy environment, these lines are often obtained in a non-continuous manner, which means a loss of tracking in the time and space even in locations with a good radio coverage.

Finally, we evaluated the impact of the drones speed as depicted in figure 5.8. In fact, the RPR remains almost the same for drone speed varying from 10 to 14m/s. However, this rate decrease gradually once the drones exceed the speed of 15m/s. 9.3% of the tracking capability is lost at speed equal to 18m/s. We can conclude that the speed of the drone does not have much impact on the quality of detection.

Data gathering evaluation

As the final objective is to gather data from the ground sensors, we need to evaluate the rate of the collected data and the efficiency of using drones for such mission. Here again, we assess the solution under different drones' speed and different sensor transmission powers.

As the latter is strongly related to the energy consumption, this evaluation could give us an idea about the minimum sensor transmission power needed to have a good reception at the drone side in order the optimize the energy consumption. First, we consider an ideal environment with no jamming nodes. We set the drone speed to 15 m/s and we increase the sensor power transmission gradually from 0 mW to 1.0 mW . The figure 5.9 points out that within a transmission power let than 0.2 mW the majority of the transmitted data are lost.

However, the reception gets better once the transmission power is beyond 0.2 mW . Finally, a transmission power greater or equal to 0.6 mW is enough to have a good reception at the drone side.

Next, we assess the impact of the drone's speed on the rate of the collected data. The figure 5.10 indicates that the sensors with weak transmission power are more affected by the drone speed. In fact, 17% of data are lost for transmission power equal to 0.2 mW , 5% for 0.3 mW once the drone exceeds a speed of 15 m/s, while it remains more stable for the other power range.

Conclusion

In this chapter, we evaluated the performances by simulation of our work related to path planning problems for a swarm of UAVs for data gathering missions, with an objective of minimizing the travel duration with respect to the energy autonomy, tour fairness and collision avoidance. Our first goal was to assess the quality of the tracking process in order to follow the drone along its flight. Our second objective was to evaluate the rate of the collected data and the efficiency of the use of drones for such mission. Future developments of this work will regard some enhancement for drone tracking and collision avoidance between drones using communication protocols during the flight.

Chapter 6

UAV Swarm Target Tracking

Introduction

Along with the progress of embedded systems and the miniaturization tendency of micro electromechanical systems, it has been possible to produce small or mini UAVs at a low cost. However, some complex application scenarios require capabilities that are over and above the capability of a single UAV, appealing thus, to a group consisting of multiple drones [START_REF] Bürkle | Towards autonomous micro uav swarms[END_REF][START_REF] Bandala | Swarming algorithm for unmanned aerial vehicle (uav) quadrotors-swarm behavior for aggregation, foraging, formation, and tracking[END_REF][START_REF] Maza | Classification of multi-uav architectures[END_REF]. Even though, the capability of a single small UAV is limited, coordination and collaboration of multiple UAVs can create a system that is beyond the capability of one UAV and in many cases at a lower cost than a single sophisticated drone.

Basically, these flying machines are designed to fulfil the requirements of assigned missions individually. Since complex mission cannot be accomplished with a single entity, the use of a set of drones called 'swarm' is required. In this case, the drones forming the swarm have to cooperate in order to achieve the global mission and to avoid a collision with each other. Thus, the main objective of the flight in the formation is to make a link between the decisional and functional level, in other words, to produce a configuration of formation based on the constraints of the mission. However, such cooperation requires robust communications and a good strategy to avoid obstacles and collisions between the drones as well.

Effectively, recent research and development effort has shifted towards using several applications, where multiple UAVs can be used with reduced costs. It is without doubt that many of these tasks cannot be supported by a single small drone due to its limitations regarding to its operating range and payload.

Although the control of a single UAV is already well understood, the use of multi-UAVs still needs exploration and investigation. With an increasing number of UAVs in the swarm, manual control becomes more and more impractical. The cooperative control of swarms requires new control strategies and adapted solutions are more than necessary.

A general approach is to provide a certain amount of autonomy to the UAVs, through new capabilities that can be integrated to the drones such communication between UAVs, autonomous navigation, sensing, and collision avoidance [START_REF] Bürkle | Towards autonomous micro uav swarms[END_REF].

In this chapter, we address the problem of mobile target localizing and tracking by the use of a fleet of drones. Our gaols are to determine the position of an intruder in a given area, to keep the fleet in a certain formation in order to avoid a collision between drones and to forward data situation to the controller side. To this end, a behavioral approach based on the quality of signals between drones of the same swarm is proposed. To motivate our work a typical scenario is to consider a sensitive area to monitor and a set of ground detectors are deployed at the border of the area. In the case of intrusion, the ground sensors send an alarm to the security forces in charge of the area surveillance. The security forces need to localize the intruder and to get for example a video of the situation for a better threat evaluation. To this end, the security forces resort to the use of a set of small-scale drones equipped with embaded sensors (for example cameras) and wireless communications devices. The pictures 6.1a and 6.1b give an overview of the scenario and illustrate the drone's behavior during the different phases of the mission.

Problem Description

As mentioned earlier, we are dealing with a sensitive area surveillance. The main objective is to locate the intruder and to report the situation to the security forces in the shortest possible time in order to evaluate the threat and to deploy the adequate forces. Basically, this mission is given to a set of small autonomous scale drones, denoted by D = {D 1 , D 2 , ....D n }. Each drone D i is equipped with sensors such as sensor and wireless devices to communicate with the other drones and the base station BS located at the controller side. We assume that all the communication devices have the same characteristics and have a short sensing range compared to the size of the region of interest. In addition all the embaded sensors have the same field of view that we denote by FoV . We also consider that the drones have a limited flight autonomy, denoted ϒ. Finally, we assume that the intruder is localized once it is within the FoV of any drone D i . In this case, the system is modeled as 2D area A without any obstacle since the drones are flying at the same altitude h. The projection of the flying area is represented by a rectangular with length of x max and a width of y max .

Our goal is to present a solution that minimizes the search localization and prevent any drone collision. Furthermore, and in order to cover a large area, drones shall flight in formation and maintain the maximum distance possible between each other. For this purpose, we assume that after each period P drone generates a message of size D bits containing its identification, its position and speed. The on-board wireless interface tries to send each generated message to the other UAVs. For some reason, a message can be corrupted or lost due to possible interference and collisions. The opportunity to transmit also depends on the radio coverage, the capacity of the related wireless technology and the drone's location.

In our approach, a first drone is sent to the direction where the attacker was initially reported by the ground detectors that are deployed at the border of the area. After a period time p, and if the situation is not received at the controller side, another drone takes off and moves towards a new random position looking for the intruder. The new random positions are generated according to the elapsed time from the first alarm and the speed of the intruder which is supposed to be less than or equal to the speed of the drones. In other word, the drones are oriented to the area where the intruder is supposed to be according to its expected displacement radius according to the time as presented in the figure 6.2. This step is repeated after each period p, until the intruder is localized or the maximum number of the drones is reached.

In the case where the drone identification and position message is received by one or different drones, the sender and the receiver drones create a new swarm. The cohesion of Fig. 6.2 Expected displacement radius of the intruder this swarm is a function of the signal quality of the wireless network created by the swarm drones. Thus, the drone forming a swarm maintains the largest distance between them in order to cover a large area. In this case, a low signal strength could guarantee the position messages exchange in the network. Whereas, a high data rate is needed to report for example a video situation to the controller.

Moreover, if a drone identifies the intruder, it reports and notifies the nearby UAVs of its location. The UAVs alter their flight paths and align themselves between the intruder position and the BS at the controller side. As the intruder moves, the drones update them positions to keep the target in sight. Through coordination, the UAVs should be able to complete tasks that each could not have done alone. Finally, if a drone D i consumes a given amount of its energy it goes back to the start position.

Flocking Pattern Based Approach

Let's consider we have n autonomous drones flying at the same altitude h. For simplicity we denote the position of a single drone D i at time step t by the coordinate (x i,t , y i,t ). The movement of a drone D i is discretized in space and time and each drone can move to adjacent position or hover at the same position. Our main objective is to minimize the search time of the intruder.

As we assumed that the drones are flying at a constant altitude h, they therefore have a collision avoidance constraint which can be quantified as minimum safety separation between two drones denoted as A.

In addition, when performing area coverage for intruder detection and for data reporting, it is important to define the range boundary of the drones swarm based on signal-to-noise (SNR) ratio, which is the signal level (in dBm) minus the noise level (in dBm). For example, to maintain the UAV swarm in formation, drones need to know the other nearby drones position, a small SNR and low data rate are enough to guarantee a reliable data exchange.

However, a healthy value for wireless networks is more than necessary for high data exchange as video streaming.

In this case, assuming a transmission power P t for the UAV, the received power P r is easily • Separation (R2): This rule ensures that each drone doesn't get too close to the nearby drones in order to avoid a collision. This separation is done according to the value SNR computed between tow drones. if the SNR value is greater than a certain threshold than the drones should go away from each other in order to avoid a collision as defined in algorithms 3.

• Alignment (R3): This rule is necessary to ensure that all the drones in the same swarm move collectively in a common direction 4.

Algorithm 3 Separation

Input:

V ▷ vector D i ▷ Drone SNR i, j
▷ SNR 1: function SEPARATION(D i , SNR i, j ) 2:

Vector vector = 0 3:

for each drone D j ∈ swarm do 4:

if thenD i != D j 5:
if SNR i, j > δ then The comparison of the intruder localization efficiency between the two methods A and B is presented in the figures 6.6 and 6.7. In each method we have varied the number of drones from 2 to 10, we compute the localization time, the minimum and the maximum distance between drones in the same swarm. We have repeated this experience 20 times. In the figure 6.6, the blue line represents the drone flight autonomy. The red plot refers to the intruder localization time. The yellow and the green lines refer to the minimum and the maximum distance between to neighbor drones in the same swarm respectively. When the red curve goes over the blue line, it means that the drones failed to locate the intruder. As depicted in this figure, the localization time computed with the method B is always lower than the one computed by the method A. With two drones the average localization time with the method A is 520.79s while it is around 289.95s with the method B. With the method B and when we consider 5 drones, only once the localization time is over the flight autonomy of the drone.

Meanwhile it remains higher with method A. Finally, with 10 drones the average localization time is almost the same around 142s and 137s with the method A and B respectively.

We can clearly notice that in the 20 experiences that we did, the total of the intruder localization increase when the number of drones in the swarm increase, which confirm the advantage of the cooperative localization using a set of small drones in such mission. Here again the method B presents a better result. For example, as depicted in the figure 6.7b the

Conclusion

We propose a comprehensive solution for borders and sensitive areas control and monitoring through the use and the exploitation of the communications and imaging capabilities of a team of drones. The proposal should improve the response time between intruder detection and interception, and thus allows to better evaluate the nature and level of the threat, and consequently yield to optimize the deployment of the resources. We showed that the flocking scheme based on the quality of the received signal between drones of the same swarm enables to avoid a collision and to cover a large area.

Conclusion & Perspectives

This chapter concludes the thesis by a summary of its contributions and an outlook to future research directions.

Conclusion

This thesis presents several contributions to the field of Unmanned Aerial Vehicles path planning, localization, data gathering, detection and tracking.

First, a survey of the drones in its large manner has been presented, starting from drones classifications, applications to the regulations and challenges that hinders the use of small scale drone for civil and commercial applications in the non segregated air space. Drone identification, localization, tracking and sens and avoid capability is sin qua non conditions for any use of this technology. Various scenarios and topical applications have been identified

and that still need solutions. The focus is on three main application of UAVs:

• Drone path planning and tracking for package delivery mission: As shown in the chapter 2, tracking is a fundamental mechanism that needs to be integrated into UAVs in order to enforce regulation requirements. In this case, we propose a new off-line path planning and on-line tracking approach based on wireless terrestrial networks.

To the best of our knowledge, our work is the first one to propose combine both approaches in order to minimizing the delay to reach a destination, while maximizing successful positioning packet transmission using terrestrial wireless networks. We formulate the above problem as an Integer Linear Problem. To this purpose we also express analytically the packet loss rate of tracking messages depending on the UAV location and the wireless network coverage. Solving the ILP problem using CPLEX, we were able to analyse the performances according to radio coverage as well as the packet success rate. Unfortunately, due to the computational complexity the proposed approach was not able to provide a path planning solution for a large area. In this case, we propose a second solution for the drone path planning, a heuristic adaptive scheme based on Dijkstra algorithm in order to cope with the problem of scalability.In addition, the packet success rate was computed by considering not only the radio channel but also by taking into account a realistic MAC layer operations. Moreover, our approach is able to generate several paths with a trade-off between length distance related to drone autonomy and probability of localization. We have to choose the most suited path according to the application requirements. Finally, we also assessed our algorithm in both 2D and 3D context.

• Multi Drones path planning and tracking for data gathering mission: The second application that we targeted is related to data gathering using a fleet of drones. Basically, we consider multiple UAVs to gather data from sensors that are spread over large scale areas. The main objective is to minimize the total distance travelled by the drones. In addition, several aspects was considered such as the drones' autonomy, the fairness regarding routes lengths, the collisions avoidance and a guarantee on the minimum average packet delivery ratio along the path, in order to favor drone tracking. However, we were not focusing on the resolution of the problem but on the evaluation of the obtained results, notably in its component inherent to the network communications, path loss, tracking, localization, rate of the data gathered from the ground sensors, UAV speeds, as well as the ground sensor transmission power and the number of jamming nodes. The problem resolution was done by our colleagues from LIPN Laboratory.

The proposed solution is based on a column generation procedure and more precisely on a path-decomposition formulation of the problem.

• UAVs swarm for intruder localization and tracking: The last application is related to the use of a group of drones in the context of the control and surveillance. More precisely, we focus on tracking applications where a fleet of drones is used to locate and to track the intruder in a sensitive area. In fact, multiple UAVs can perform tasks faster than if we consider only one drone. Thus, we propose a solution for borders and sensitive areas control and monitoring through the use and the exploitation of the communications capabilities between drones. Basically, the use of the quality of the received signal between drones of the same swarm to avoid collisions and to cover a large area.

This thesis presents several contributions to the field of Unmanned Aerial Vehicles (UAV) path planning, localization, data gathering, detection and tracking. Tracking is a fundamental mechanism that needs to be integrated into UAVs in order to enforce regulation requirements. In this case, we propose different solutions to different problems related to UAVs application. The first application is related to the drone package delivery. A new off-line path planning and on-line tracking approach based on wireless terrestrial networks is presented. The second application is related to data gathering, where a team of drones is deployed to collect data from sensors that are spread over a large area. The third contribution concerns the use of a group of drones in the context of the control and surveillance. More precisely, we focus on tracking applications where a fleet of drones is used to locate and to track the intruder in a sensitive area. Basically, the use of the quality of the received signal between drones of the same swarm to avoid collisions and to cover a large area.

Keywords: Wireless network, drone, UAV, mobilty, tracking, planification, trajectoiry, 2D, 3D, obstacle, collision, SINR, package delivery by drone, data gathering, surveillance, swarm Cette thèse présente différentes contributions dans le cadre de la planification, la localisation, la collecte de données, la détection et du suivi de trajectoires de drones (UAV). Le suivi et la poursuite des drones est un mécanisme fondamental qui doit être intégré aux drones afin de se conformer aux exigences réglementaires. Dans ce cas, nous proposons différentes solutions aux différents problèmes liés à l'utilisation des drones. La première application est liée à la livraison du colis par drones. Une nouvelle approche de planification de chemin hors ligne et de suivi en ligne basée sur les réseaux terrestres sans fil est présentée. La deuxième application est liée à la collecte de données, où une flotte de drones est déployée pour collecter des données à partir de capteurs répartis sur une grande surface. La troisième contribution concerne l'utilisation d'un groupe de drones dans le cadre du contrôle et de la surveillance. Plus précisément, nous nous concentrons sur le volet de poursuite de cibles où une flotte de drones est utilisée pour localiser et suivre un intrus dans une zone sensible. La qualité du signal entre drones est utilisée pour éviter les collisions entre drones.

Mots clé: Réseau sans fil, drone, UAV, mobilité, poursuite, tracking, planification, trajectoire, 2D, 3D, obstacle, collision, SINR, Livraison de colis par drone, collecte de données, surveillance, essaime de drones

1

  ICAO: International Civil Aviation Organization is a United Nations specialized agency, created in 1944 upon the signing of the Convention on International Civil Aviation (Chicago Convention). ICAO works with the Convention's 191 Member States and global aviation organizations to develop international Standards and Recommended Practices which States reference when developing their legally enforceable national civil aviation regulations [ICA].

(

  RPA) & Remotely Piloted Aircraft Systems (RPAS) instead of Unmanned Aircraft Vehicle (UAV) & Unmanned Aerial System (UAS) & drone.

  in determining the structure of a classification system. The most common classification is based on the altitude criteria, weight and endurance, see Tab 2.1 and Fig 2.1.

Fig. 2

 2 Fig. 2.1 DoD, UAV Nomenclature Designation

  Fig. 2.2 UAV types

Fig. 3

 3 Fig. 3.2 Discretization of the area A into hexagonal Unit Areas

  the problem formulation our objectives are to minimize the UAV traveling time between the origin vertex o and the destination vertex d (3.6a), and also to maximize the tracking probability along this path (3.4b). The first constraint (3.6b) states that the depart node of the drone is identified by the vertex o. As in the last constraint (3.6c) guarantee that the destination of the drone is the vertex d. The next constraint (3.6d) is for flow conservation.

Fig. 3

 3 Fig. 3.4 Area Unit AU i and its sub-areas A k

Fig. 3. 5

 5 Fig. 3.5 Shortest path Vs Obtained path with δ = 0.1

8 Fig. 3. 7

 87 Fig. 3.7 Path length Vs number of BS Vs Required accuracy

Fig. 3 . 8

 38 Fig. 3.8 Percentage of admissible solutions

Fig. 3 .

 3 Fig. 3.10 Azimuth angle gain determination (top view)

  arcsin d * d and |θ ′ 2 | = arccos d * d with |θ ′ 1 | + |θ ′ 2 | = π 2 . Hence we compute site elevation angles θ ′ e , θ ′ r shown in the figures. θ ′ e = arccos Z rz d (3.26)

(

  RPR i, j )x i j (4.4) where, as defined earlier, c i j is the cost of the arc going from cell c i to cell c j . In this chapter, we consider c i j as the amount of energy consumed by the drone on that arc, The objective functions (4.3) and (4.4) represent respectively the minimization of the energy consumed by the drone and the maximization of the tracking probability between the start point O and the destination D. Basically, we should find the shortest possible path, in terms of consumed energy, that passes through the cells with highest Received Packet Rate, see Fig 4.1.

Fig. 4. 1

 1 Fig. 4.1 Example of a path from the origin A to the destination I where the shortest path with high packet delivery rate is (A, B, E, H, J, I)

Fig. 4

 4 Fig. 4.2 example of paths with the same cost

Fig. 4. 3

 3 Fig. 4.3 Dynamics involved in the quadcopter

Algorithm 1

 1 Optimal Path algorithm Input: G ▷ The graph G RPR ▷ The Received Packet Rate map c o ▷ The origin cell c d ▷ The destination cell 1: function OPTIMAL PATH(G , RPR , c o , c d ) 2:

12 :

 12 if P[c j ] < P[c i ] * (RPR(c j )) then 13: P[c j ] ← P[c i ] * (RPR(c j )) Near Optimal Paths Input: G , RPR , c o , c d 1: Path = Optimal Path(G , RPR , c o , c d ) 2: if length(Path) > δ then 3: for each cell c i ∈ Path do Path(G , RPR , c o , c d ) 7: end if objective was to minimize the energy required to travel along the path in accordance with the drone flight autonomy and the capacity of its battery. Finally, the last objective is to minimize the number of adjacent cells with low RPR.

Fig. 4

 4 Fig. 4.5 RPR with 10 noise nodes at h=60m

Fig. 4

 4 Fig. 4.7 RPR with 30 noise nodes at h=60m

Fig. 4

 4 Fig. 4.9 RPR with 50 noise nodes at h=60m

Fig. 4 .

 4 Fig. 4.10 noise nodes= 20

Fig. 4 .

 4 Fig. 4.12 set of near Optimal paths

Fig. 4 .

 4 Fig. 4.13 Optimal and Near optimal paths Vs Dijkstra path

Fig. 4 .

 4 Fig. 4.15 Path lengths with different number of noise nodes, h=60m

Fig. 4 .

 4 Fig. 4.17 Difference between optimal and Dijkstra path length, nbr paths = 1000

Fig. 4 .

 4 Fig. 4.19 Received Packet Rate at different drone speeds, noise nodes = 50

4. 22 .

 22 According to the nature, shape, height of obstacles and the number of jamming nodes we were able to generate both the SINR and the RPR maps at different altitudes in A. The figure 4.23 illustrates the SINR maps generated at altitudes varying from 20m to 50m. The blue zones indicate a very low signal quality due to the presence of obstacles or interferences. Finally, we consider a drone to move from a given starting point s to a destination d. s and d are chosen the most distant points at the lowest altitude.

Fig. 4 .

 4 Fig. 4.22 Area with obstacles of different shapes, properties and heights

Fig. 4 .

 4 Fig. 4.24 Optimal path Vs Dijkstra shortest path tracking

  λ r ≤ 1 ∀i ∈ N -{o}, j ∈ {3, ..., θ 2 } (5.1d) λ r ∈ {0, 1} ∀r ∈ R (5.1e) Then, the objective function (5.1a) represents the summation of the tours lengths assigned to the vehicles. Constraints (5.1b) indicate that all the nodes in M have to be covered at least once. In fact, the boolean parameter a ir indicates if route r covers node i or not. Constraint (5.1c) imposes that the number of vehicles used is less than |K|. Finally, Constraints (5.1d) concern the collision avoidance. Note that such constraints consider only collisions that may happen to start from the third time instant, in order to permit the use of a decent number of vehicles in the scenarios where only one or two nodes are connected to the depot. The binary coefficients b i jr indicate if the node i ∈ N is the j-th in the route r. Each of the constraints in (5.1d) forces that node i is the jth in the route of one vehicle at most. The problem of this formulation is that the number of the variables increases exponentially as the graph size grows.

Fig. 5 .

 5 Fig. 5.1 SINR map with the set of cells to be covered

Fig. 5 .

 5 Fig. 5.2 RPR maps with path lengths with 0 jamming nodes

Fig. 5 . 7

 57 Fig. 5.7 Drone's tracking under different number of noise nodes

Fig. 5 . 9 Fig. 5 .

 595 Fig. 5.9 Data gathered rate with different sensor power, noise nodes number=0

  (a) UAVs fleet for intruders localizing (b) UAVs fleet for video streams reporting

Fig. 6 .

 6 Fig. 6.1 Intruder search and report scenario

  Fig. 6.3 Reynolds Craig, Flocking rules

6 : 5 : 8 : 9 :

 6589 Fig. 6.4 UAVs swarm formation with different SNR separation parameters

Fig. 6 . 5

 65 Fig. 6.5 Intruder search and report scenario

Fig. 6 . 6 Fig. 6 . 7

 6667 Fig. 6.6 Intruder localization time efficiency comparison per number of drones and per methods

Fig. 6 . 8

 68 Fig. 6.8 Intruder localization time efficiency comparison per methods

Table 2 .

 2

	1 UAV examples

Table 2

 2

	.2 NATO Unmanned Aircraft Classification Guide [53]

Table 2

 2

	.3

Table 3

 3

	.1 Example of MCS Parameters in 802.11a/g [cis]
	Modulation Turbo Coding Data rate	SNR
	scheme	Rate	(Mbps) Threshold
	BPSK	1/2	6	14 dB
	BPSK	3/4	9	15 dB
	QPSK	1/2	12	16 dB
	QPSK	3/4	18	18 dB
	16QAM	1/2	24	22 dB
	16QAM	3/4	36	26 dB
	64QAM	2/3	48	29 dB
	64QAM	3/4	54	31 dB

Table 3

 3

	.2 Parameters configuration
	Area	X = Y = 250 m
	AU radius (constant) a = 5m
	BSs	from 5 to 35
	UAV altitude	Fixed, z = 10m = Ht
	P t	20 dBm (100 mW)
	Pnoise + Pinterf	-60 dBm (Constant)
	Antennas Gains	Ge = Gr = 10 dBi
	D	200 bytes
	Carrier Frequency	2.4 GHz
	δ	from 0.1 to 0.9

  ϕ e ).P t (3.[START_REF] Commission | Microcopters and ground robots used to save earthquake-hit italian churches[END_REF] Assuming fixed BSs positions and fixed UAV orientation, G e and G r become G e (X i ,Y i , Z i ) and G r (X i ,Y i , Z i ), where X i ,Y i , Z i are the coordinates position of the UAV. The gains depend directly on the radiation patterns and hence, on the Rx/Tx antennas orientations as well as their positions. In our case, as the UAV is transmitting and the BS receiving, the values G e , G r , {X e ,Y e , Z e }, {X r ,Y r , Z r }, will correspond to the antenna gains G UAV , G BS , and the coordinate positions of the UAV and the BS respectively {X

Table 4

 4

		.1 Phatom 3 Advanced drone characteristics
			Manufacture Values Calculated values
				Boucher Abbot
	Frame	mass (kg)	1.28	-	-
		type	lipo	-	-
		elements nbr	4	-	-
		capcity (mA.h)	4480	-	-
	Accumulator max continuous discharge rate (C)	20	-	-
		medium voltage discharge (V)	15.2	-	-
		continuous max intensity (A)	-	44.8	44.8
		reasonable max intensity (A)	-	29.9	29.9
		type	broshless	-	-
	Rotor	Kv	800	-	-
		estimated yield (%)	-	75	75
		Max rotation speed (RPM)		12160	12160
		Standard rotation speed (RPM)		8000	8000
		diameter (inch)	9.4	-	-
		pitch (inch)	4.3	-	-
	Propeller	shaft power (W)	-	55	61
		traction (g)	-	466	466
		airspeed blow (km/h)	-	52	52
		Intensity (A)	-	15.7	17.7
	Global	power consumption (W)	-	239	269
		estimated flight speed (km/h)	-	42	42
		autonomy (mn)	21	18.8	16.7

Table 4

 4 In figures 4.5, 4.6, 4.7, 4.8 and 4.9 we illustrate the received packet rate map according to the number of deployed jamming nodes. It shows clearly that more noise nodes (red dots) are present more we have low RPR.

	.2 Simulation parameters
	Area	X = Y = 1000 m
	Cell radius (constant)	a = 5m
	BSs	10
	Noise nodes	10, 20, 30, 40, 50
	UAV altitude	60m
	D	200 bytes
	P t	20 dBm (100 mW)
	Path loss type	Two Ray Ground Ref.
	Pnoise + Pinterf	-60 dBm (Constant)
	Antennas Gains	Ge = Gr = 10 dBi
	Carrier Frequency	2.4 GHz
	Drone' packet sending Interval 0.1s
	Noise' packet sending Interval 0.01s

Table 5

 5

	.1 Simulation Parameters
	Area	X = Y = 562 m
	AU radius (constant)	a = 12.5m
	number of cells	780
	BSs	5
	Noise nodes	5, 10, 15, 20, 25, 30
	Sensor nodes	30
	UAV altitude	20m
	Message length D	200 bytes
	Drone P t	20 dBm (10 mW)
	Noise node P t	20 dBm (10 mW)
	Sensor P t	0.1.. 1 mW, step 0.1
		1.. 10 mW step 1
	Background noise power	-72dBm
	Path loss type	Two Ray Ground Reflection
	Pnoise + Pinterf	-60 dBm (Constant)
	Antennas Gains	Ge = Gr = 10 dBi
	Carrier Frequency	2.4 GHz
	Drone' packet sending Interval 0.1s
	Noise' packet sending Interval 0.01s

Table 6

 6

	.1 Simulation parameters
	Area	X = Y = 1000 m
	BS	1
	Number of Drones	1 ..N
	UAV altitude	20m
	D	200 bytes
	P t	20 dBm (100 mW)
	Background noise power	-72dBm
	Path loss type	Free space
	Pnoise + Pinterf	-60 dBm (Constant)
	Antennas Gains	Ge = Gr = 10 dBi
	Carrier Frequency	2.4 GHz
	Drone' packet sending Interval 1s
	Intruder mobility model	RWP
	Single drone mobility model	RWP
	Swarm mobility model	cohesion, separation, alignement
		and RWP

NATO is an alliance of 28 member countries roughly bordering the North Atlantic Ocean: Canada, the U.S., Turkey and most members of the European Union. NATO's essential purpose is to safeguard the freedom and security of its members through political and military means[Amadeo, NAT]

FAA: The Federal Aviation Administration is a government agency responsible for regulating and controlling civil aviation in the United States. It depends on the US Department of Transportation.

ISR: ISR is the coordinated and integrated acquisition, processing and provision of timely, accurate, relevant, coherent and assured information and intelligence to support commander's conduct of activities.

EASA: European Aviation Safety Agency is the European Union Authority in aviation safety. The main activities of the organization include the strategy and safety management, the certification of aviation products and the oversight of approved organizations and EU Member States

Acknowledgements

problem using CPLEX, we were able to analyze how the radio coverage (i.e. density of BS) as well as the threshold on the packet success rate, impact the number of possible solutions and the trajectory of the UAV. Next chapter focuses on the complexity issue raised for larger size of the area A. We design an heuristic solution to cope with the curse of dimensionality.

Related to this issue, we extend our problem to the 3D case and we tested in environment close to the reality of the existence of noise and obstacles.

Chapter 4

Single UAV path planning and tracking: Heuristic approach

Introduction

In the previous chapter 3, we focused on off-line path planning problems in order to increase localization and tracking of the drone and we formulated the problem as an Integer Linear Problem. We expressed in an analytic manner the packet loss rate of tracking messages depending on the UAV location and the wireless network coverage. By solving the ILP problem using CPLEX, we were being able to analyze how the radio coverage as well as the threshold on the packet success rate impact the number of possible solutions and the trajectory of the UAV. Unfortunately, due to the computational complexity the proposed approach was not able to provide a path planning solution for a large area. In addition, the packet success rate was computed by considering only the radio channel and without any MAC layer operations.

In this chapter, we focus on the complexity issue raised for larger area size. For the drone path planning, a heuristic adaptive scheme based on Dijkstra algorithm is presented to cope with the problem of scalability. The flight path of drone is optimized in order to improve its connectivity to the available terrestrial wireless network and consequently its localization, identification and tracking. Moreover, the solution is proposed to yield a simple but effective and fast solution and tested under a more realistic scenario characterized with a noisy environment.

Path computation

Different shortest path algorithms exist like A*, Dijkstra, Bellman-Ford and others. Our proposal is based and adapted from Dijkstra algorithms. The latest is one of the most common and effective algorithms used to search the shortest path between two vertices are in a graph in terms of distance. For our case, we adapt the Dijkstra algorithm to find the shortest path with high communication reliability and high packet reception.

As introduced in our problem formulation section, our objectives are first to minimize the traveling distance and to maximize the tracking probability between the start point the destination point. The first objective correspond to the classical Dijkstra algorithm. On the other hand, for the second objective we are dealing with probabilities. We have to find the shortest path where the product of the probabilities RPR i of the visited cells that constitute a given path is maximized. More over, each time a cell is added to a path, the product of the probabilities decreases. In this case, our algorithm first starts by initializing the cost of the origin cell c o to 1. The cost of the remaining cells is set to 0. Starting from the origin point, we built step by step a set of P marked cells. For each marked cell c i , the cost is equal to the product of the Received Packet Rate probabilities of all predecessors cells. At each step, we select an unmarked vertex c j whose cost is the highest among all vertexes not marked, then we mark c j and we update from c j the estimated costs of unmarked successors of c j . We repeat until exhaustion of the unmarked vertexes.

In addition to the above algorithm, we also derived a set of near optimal paths. In fact, the solution was extended to compromise localization data delivery rates and distance between the starting point and the destination with the respect of the drone autonomy. To this end, if the length of the optimal path is greater than the drone autonomy or simply, the operator would to have multiple choices of short paths, then we re-execute the function above until we get the desired solution and for each execution we set the RPR of the cells of the obtained path to ε, where ε is a small non-null value. This allows us to generate a new path totally different from the previous one. All these paths can then be compared using the cost above function f for a better drone tracking result.

Simulation and Evaluation

In this section, we evaluate our proposed algorithm. Three objectives were fixed. The first objective is to ensure a maximum tracking of the drone along with its flight. The second However, we could also introduce other aspects to the behavior of the swarm as extra rules.

In this case, coefficients and limitations could be added to the above-mentioned rules:

where the coefficient a, b, c, d ... could be a positive or a negative value.

In the following, we will consider tow cases. In the first case, the cohesion rule R1, the separation rule R2 and the alignment R3 are taken into consideration (denoted as methodA).

In the second case only the separation and the alignment rules are considered (denoted as methodB).

Results

In this section, we evaluate our proposed algorithm. To recall, two main objectives were fixed, first minimize the intruder localization period, and second avoid collisions between drones. We assess the algorithm in different scenarios. Using Omnet++ simulator, we generate different traces of the intruder trajectory. Since intruders follows unpredictable path and in order to make it more realistic, we opt for Random Way Point (RWP) mobility model. In addition, as we didn't discretized the area of interest, a drone can move freely to all the adjacent positions. Here again a drone follows an RWP mobility model on its way of intruder localization. Thus, once a set of drones form a swarm, the swarm follows a mobility model resulted in different behaviors, namely separation , cohesion, alignment and the RWP mobility model as well. The table 6.1 summarizes the predefined variables.

The result of the figure 6.4 shows the influence of the SNR parameter on the swarm connectivity and the area size covered by the swarm. As illustrated in 6.4a, a low SNR value allows to cover a larger area and therefore, the drones of the same swarm maintain the maximum distance possible. In the same logic, a higher SNR results a small size area covered by the swarm, since the distances that separate the drones are small. In addition, the figure 6.5a illustrates two separate swarms having two different bearings. In fact, we can generate more than one swarm at the same time. When communications between two different swarms are possible, these latter constitutes a single one swarm as depicted in the figure 6.5b. The intruder localization is illustrated by the figure 6.5b. Indeed, when an intruder is within one drone field of view, the swarm change its topology and the drones become closer to each other in order to ensure a high data rate for data exchange between the drones.

Perspectives

The proposed algorithms in this manuscript have shown good performances. Nevertheless and from our point of view, the studies we conducted during this thesis offer many perspectives.

First, test the feasibility of the proposed solutions in a real environment. All our proposals have been validated only by simulations. The behavior of our algorithms and our approaches on real platforms and by experimentations would be a decisive factor on the evolution of these solutions.

A second perspective would be to update online the calculated trajectories that we proposed in chapter 3 and 4. Basically, online paths can be updated during the flight of the drone in order to avoid collision with other drones evolving nearby. Exploiting the potential fields seems to be a good solution for that issue. However, a protocol based approach need to be also explored. Finally, the localization of multi-targets is a natural extension of the solution proposed in chapter 6.

Appendix A Publications