# Elevating the future of mobility: UAV-enabled Intelligent Transportation
Systems

Abdul Saboor, Sander Coene, Evgenii Vinogradov, Emmeric Tanghe, Wout Joseph,
Sofie Pollin Abdul Saboor, Evgenii Vinogradov, and Sofie Pollin are with
Department of Electrical Engineering, KU Leuven, BelgiumSander Coene, Wout
Joseph and Emmeric Tanghe are with Department of Information Technology, IMEC-
Ghent University, 9052 Ghent, Belgium.

###### Abstract

Intelligent Transportation Systems (ITS) improve traffic efficiency, traffic
management, driver’s comfort, and safety. They consist of a broad range of
components, including vehicles, sensors, Base Stations, Road Side Units, and
road infrastructure (i.e., traffic signals). ITS of the near future will need
to support multi-modal transportation schemes (including ground and aerial
vehicles, so-called Urban Air Mobility). ITS will have to be integrated with
Unmanned Aerial Systems Traffic Management (UTM) and rely on 3 Dimensional
(3D) connectivity provided by Integrated Aerial-Terrestrial 6G networks to
achieve this support. In other words, various types of Unmanned Aerial
Vehicles (UAVs) will become integral parts of future ITS due to their
mobility, autonomous operation, and communication/processing capabilities.
This article presents our view on the future integration of ITS and UTM
systems, enabling wireless technologies and open research questions. We also
present how UAVs can be used to enhance the performance of the currently
available ITS.

##  I Introduction

The last century observes a significant rise in urbanization with more people
migrating to urban areas. This influx of new residents increases the size of
cities around the globe. Cities are being forced to address traffic congestion
caused by an increased demand for transporting people and goods to support the
population. Moreover, the growing number of single-person households and
longer life expectancy are causing demand to shift towards individual mobility
services that can be adapted to users’ specific life circumstances. Currently,
the mobility sector is undergoing huge changes due to several technological
revolutions and paradigm shifts. So-called Mobility 2.0 includes i) driver-
less cars; ii) cooperation between vehicles (e.g., supported by 5G networks),
iii) electric cars to reduce pollution, and iii) shared individual transport
(e.g., cars, bikes or scooters). However, there is another Revolution that is
underway already.

Urban Air Mobility (UAM) envisions a safe and efficient transportation system
that will use highly automated aircraft operating and transporting passengers
or cargo at lower altitudes within urban and suburban areas. In May 2021,
Morgan Stanley released a prediction [1] stating that by 2050 the total market
of UAM (delivery, air taxi, patrolling drones, to name a few) will reach up to
$19 tn (10-11% of projected global Gross Domestic Product (GDP)). Fig. 1 shows
the expected technology development timeline [1]. Drone delivery will become
part of urban life within the next ten-fifteen years, commercial introduction
of urban passenger aircraft will take around 20-30 years.

Interestingly, the same 3 Dimensional (3D) shift is observed in the
telecommunication sector [2]. One of the 6G enablers (expected to be in place
around 2030) is Integrated Ground-Air-Space Networks, including drones,
satellites, high altitude platforms, and ground infrastructure. These two 3D
trends re-enforce and help each other creating new use cases and attracting a
lot of attention from academia and industry. Indeed, the technological
innovations we seek now should be brought to another dimension: autonomous
ground vehicles become autonomous Unmanned Aerial Vehicles (UAVs); electric
cars become electric Vertical Take-Off and Landing (eVTOL) aircraft; to ensure
cooperation, we need an ubiquitous 3D communication. Considering that the
ground vehicles will not disappear, can we already talk about a new paradigm
of Mobility 3.0 (or rather Mobility 3D)?

Of course, first, we have to think about the missing technologies for Mobility
2.0. For example, the Intelligent Transportation System (ITS) is a crucial
element. However, while selecting the tools to achieve the goals, we should
keep future challenges in mind. Shall we already start including UAVs in ITS?
Luckily, in 2017, Menouar et al. showed in [3] that using drones for ITS are
highly beneficial. In this article, we answer two questions: how can we use
drones for ITS in the near future, and what technologies will be needed for
Mobility 3D.

Figure 1: UAM technology development timeline.

##  II Overview Intelligent Transportation Systems

Conceptually, ITS aims to reduce friction for participants in a transportation
scenario. At the end of the last century, ITS saw independent development in
countries like the USA, China, Japan, and countries inside of Europe, each
spear-pointing different priorities. Early examples include navigation, which
combines Global Positioning System (GPS) (or any other Global navigation
satellite system (GNSS)) with a digital roadmap to provide real-time
instructions to get to a set destination. These ITS also contain automated
toll systems using Radio Frequency Identification (RFID) chips or license
plate recognition systems to identify cars and reduce the time needed for the
payment. In addition, induction coils underneath the road count the passing
vehicles and inform public infrastructure spending by identifying traffic
bottlenecks.

As the technology evolved, so has ITS. The main area where one can observe a
significant improvement in wireless communications. This paradigm shift is
reflected in the new term: Connected ITS (C-ITS). In the last decades, many
sensors have been added to the arsenal of inputs, and new ways of influencing
transportation have been added as outputs. For example, Closed-Circuit
Television (CCTV) cameras can now not only count the number of vehicles but
also track the vehicle types, congestion forming, visibility conditions, and
accidents. Dynamic road signs can warn vehicles in advance of adverse road or
traffic conditions, imposing suitable speed limits. Real-time tracking of
buses and trams provides users with up-to-date travel information like arrival
times and occupancy on mobile apps or information signs. Similarly, public
transport capacity can be dynamically adjusted throughout the day by tracking
the number of passengers. Local weather forecasts and friction sensors can
inform city services to deploy snow-plowing vehicles or take anti-icing
measures.

It has been shown that road users are more likely to respond and comply with
hyper-local recommendations rather than more widely applicable warnings (e.g.,
weather conditions mentioned on dynamic road signs vs. over the radio). Such
hyper-local communication is the goal of Vehicle-to-Vehicle networks, to relay
highly relevant information in the direct vicinity with minimal lag and high
priority. While such protocols and network topologies have been investigated
and implemented, they are not readily available in contemporary cars.
Additionally, inter-fleet communication is impossible when traffic is more
dispersed than the communication range limitations support.

As we mentioned in the introduction, driver-less cars are important new agents
of transportation systems. However, the next generation ITS is not limited to
the automation of vehicles only. In contrast, it requires automating the
infrastructure, supporting units, devices, and network. An ITS combines
sensors, computers and communication technologies for efficient traffic
management. The ITS incorporates Vehicle-to-everything (V2X) communication to
enhance traffic efficiency. The communication between vehicles,
infrastructure, pedestrians, and devices allows them to share the information
for different services such as congestion control, collision avoidance,
traffic light control, and parking.

##  III Next Generation Intelligent 3D Transportation System

Authors of [3] demonstrated that UAVs help ITS from the wireless
communications point of view because of mobility and better/stable radio
channel. In this section, we describe several ways of using UAVs to assist
ITS. However, following the predictions presented in [1], we start with
describing drones as new agents of the transportation systems of the future.

###  III-A Sky is the Limit: Urban Air Mobility

The transportation paradigm shifts towards 3D mobility will drastically change
the traffic patterns, demand and required infrastructure. In the following, we
provide examples of the potential applications.

####  III-A1 Cargo Drones

##### Emergency

Small drones can carry necessary medications or blood. A study conducted by
American Heart Association shows that exposure to traffic increases the
chances of a cardiac arrest. The traffic caused approximately 8% of cardiac
arrest cases. In this case, a UAV can quickly deliver an Automated External
Defibrillator (AED) that helps restart the heart rate.

##### Road Congestion-friendly eCommerce

With the rise in online purchasing behavior, traffic congestion caused by
delivery vehicles has increased as well. As a result, research is being done
on reducing the traffic load by using drones as part of the delivery system.
Both UAV-only and truck-plus-UAV have already been studied as improvements. A
step further makes use of the existing fixed route transportation systems,
like public buses and trains. They provide a (moving) recharging point where
the drone can rest in-between deliveries.

##### Temporary ITS Infrastructure

UAV can act as a temporary sign, i.e., variable speed limit and traffic lights
at a particular area. The acquired data can be analyzed using machine learning
algorithms to examine and predict traffic behavior in the presence of various
signs. Finally, the fixed infrastructure (signs, roads) will be installed in
suitable locations. One more important advantage of adding an extra UAV layer
to ITS is the ability to rapidly provide supporting material to remote
positions, including fuel, aid, or toolkit.

####  III-A2 People Transportation

##### Air Taxis

Commercial UAM operations will help to avoid transportation congestion on the
ground. Around the world, there are companies currently providing these
services. For example, BLADE Bounce is an on-demand helicopter transfer
service between BLADE helipad locations and New York area airports—both
commercial and private. Similarly, Airbus is operating its Voom on-demand
helicopter service in Sao Paulo, Brazil. However, the new all-electric and
hybrid eVTOL promise to be more accessible and efficient. These vehicles are
currently being designed by Boeing, Uber, Airbus, Hunday, and other companies.

##### Emergency

In addition to passenger-carrying flights, UAM also includes aircraft
operations for tasks in metropolitan areas such as public safety, medical
evacuations and rescue.

###  III-B Bird-eye View: UAV as a Flying Eye

The majority of commercially available UAV-based solutions are exploiting on-
board cameras. This is rather a mature technology which is used (up to some
extent) in ITS. However, the ”flying eye” is still a growing market.

##### Emergency

UAVs can reach an accident location fast and analyze the situation’s severity
using visual information. Furthermore, UAVs store and analyze the traffic
information in its map. Therefore, it can re-route the ambulance to the
emergency spot using the optimal route.

An interesting approach will be the drone-assisted ambulance service. In this
scenario, a drone moves ahead of the ambulance, controlling the traffic and
signals using cellular technology to minimize the congestion for the
ambulance. Generally, an ambulance worker/driver has to drive fast that
increases the ambulance crew’s life risk. Therefore, an autonomous system is
more suitable for emergency services. Also, the road-based emergency support
is not efficient as compared to the aerial support.

##### Law Enforcement

Police are an essential part of the ITS. The key duties of police include
protection, law enforcement, patrolling, violation tracking and others. UAVs
can help the police to enforce rules with a better/broader view than
traditional police vehicles. For example, Chinese police use UAVs to instruct
a bike rider to put the helmet on. Similarly, the UAV as a police unit tracks
the traffic violations such as speed, wrong direction, and safety parameters.
As a result, UAV identifies the vehicle and later help the department in
issuing a traffic challan.

Because of better speed and visibility, a UAV is beneficial in chasing
scenarios. First, UAVs keep track of criminal vehicles and continuously inform
police about the actual whereabouts of such vehicles. Second, UAVs track the
vehicle number and suspect images to distribute them to different police
stations/units. A UAV can also fly ahead of the suspected car and limit its
movability by directly controlling or indirectly controlling the traffic
signals. Last, UAVs reach crime scenarios and provide criminal details, i.e.,
the number of criminals and weapons.

##### UAV-aided Traffic Monitoring, Conflict Detection

Due to the bird-eye view on the scenery and cameras working in different parts
of the spectrum, UAVs enable safer road use by pedestrians, cyclists, and
Powered Two-Wheeler riders (PTW: motorcycles, mopeds, etc.), collectively
referred to as Vulnerable Road Users (VRU). According to World Health
Organization, VRUs represent the majority of road traffic fatalities with 23%,
22%, and 5% of deaths for PTW, pedestrians, and cyclists, respectively. The
factors affecting VRU safety demonstrated high socio-economic dependency
(e.g., the majority of causalities occur in urban/rural environments in
developed/developing countries). However, several common features are noted:
the most dangerous maneuver is a road crossing, and the most dangerous time of
the day is twilight or darkness. This is explained by worsened visibility and
driver’s blind spots.

Figure 2: UAV use cases in ITS: a) a UAV is providing early medication by
skipping traffic congestion, b) a UAV is chasing a suspect and sending
information to the police, c) a UAV is acting as ABS to provide connectivity
in road vicinity.

##### ITS Infrastructure inspection

UAVs add an additional layer of supportability to the traditional ITS. The
traffic signal and signs provide necessary information to the commuters and
vehicles. Traffic signalization is critical, especially in the case of
autonomous vehicles. However, the negative impact on signalization can affect
the performance of the ITS. It includes damaged traffic signs, wrong
directions, blurry information, or poor retroreflective markings. Generally,
this damage requires a visual analysis, and UAVs can help because of their
movability. For example, a UAV analyzes the parameters such as pole’s serial
number, material, height, sign, dimensions of sign, sign’s code, and light
color. Later, It can signal the required information to the designated unit
that can then take action. Furthermore, a UAV connects to Geographic
Information System (GIS) database and takes measurements such as dimensions
and height of signal.

##### Public Service

Like public transport route inspection, the roadside conditions are monitored
more efficiently with a fleet of drones. Information on drive-ability (snow,
inundation) is transmitted and updated regularly to relevant authorities.
Additionally, daily inspection of powerlines, bridge structures, and pavement
decreases the risk of sudden catastrophic public property failure.

UAVs have been successfully used to make 3D scans of buildings. They can be
used to follow up construction works (both public and private), spotting
unsafe situations, and providing better estimates for completion time, leading
to better city planning overall. Start-to-end route analysis, real-time and
full-scale load observation on roads leads to better navigation planning and
provide clues for city planning where additional lanes or roads are needed.

###  III-C Help From the Skies: UAV-aided Connectivity

C-ITS enable vehicles to interact with each other and with the surrounding
road infrastructure involving communication between vehicles using V2V, V2X,
and I2I communications. The benefits of C-ITS span a range of areas (e.g.,
including improving road safety and optimizing transport efficiency). Despite
a significant body of work in this area, vehicular communication in the urban
environment is still severely affected by the harsh propagation environment
(e.g., dynamic obstacles). UAVs can offer a more stable communication link due
to the flight altitude, ensuring persistent line-of-sight channel [4].

##### Flying Roadside Unit (RSU)

RSU is an indispensable part of ITS and the RSU distribution directly
influences vehicular communications. However, intermittent connectivity, high
routing overhead, inflexible communication infrastructure, and unscalable
architecture are the key challenges that severely hinder the wide applications
of vehicular networks. Overcoming these hurdles is possible via using UAV-
mounted RSUs due to their inherent features like more stable channel (Line of
Sight (LoS) link over longer distances) and dynamic on-demand deployment.

##### Aerial Base Stations (ABSs)

Recently, the trend of relying on cellular networks for ITS support is gaining
a lot of attention. For example, 5G Automotive Association (5GAA, a global,
cross-industry organization of companies from the automotive, technology, and
telecommunications industries) indicates 5G as the next key technology for
ITS. Indeed, cellular networks are able to ensure reliable communication
between vehicles and infrastructure. However, fixed terrestrial infrastructure
faces the same challenges (though at a lower scale) as fixed RSU deployment.
Logically, the idea of putting a base station on a drone has appeared.

A relevant overview of ABS deployment techniques is provided in [4]. Note that
up to our best knowledge, the literature is still lacking an analysis of ABS
usage for vehicular communications.

##  IV Key Technological Enablers For Next Generation ITS

###  IV-A Unmanned Air Systems (UAS) Traffic Management

UAS Traffic Management (UTM) systems aim at providing a range of services to
drone operators (both private and companies), authorities, and other air
control bodies such as conventional Air Traffic Management (ATM).

The main functions of UTM are to i) strategically organize the airspace ii)
ensure the cooperation of unmanned and manned aviation through a link to ATM
systems iii) ensure transparency of drone operations to public users(citizens)
iv) control the air traffic through flight permissions v) dynamically adapt
drone operations depending on the circumstance (weather conditions, available
telecommunication capabilities, etc.).

Bauranov and Rakas recently published an overview [5] of UTM activities
performed by academia, industry, and national and supra-national airspace
agencies (e.g., UTM solutions by Nanyang Technological University in
Singapore, Amazon and Airbus, NASA and national airspace agencies as well as
the European U-Space concept). Unfortunately, the authors did not include the
view of the International Civil Aviation Organization (ICAO) on the
recommended common UTM framework with core principles for global harmonization
presented in [6].

We envision that coordination between ITS and UTM will be needed in the near
future (see Fig. 3). Aerial and ground vehicles will need to synchronize their
operation for optimizing the capacity of the complete 3D transportation
network to balance the load of aerial and terrestrial traffic based on the
weather or currently available capacity (e.g., changing due to the works on
the road network). Novel solutions will need to be designed for 3D logistics,
including aerial and ground vehicles. At the strategic level, the ITS, UTM,
and Supplemental Data Service Providers (SDSP, providing communication
services, GIS data or information about current micro-weather conditions,
etc.) planners have to join the efforts in order to optimize their capital and
operational expenditure while constructing the required infrastructure such as
road networks, vertiports, operational centers, communication networks, etc.

Figure 3: Converging UTM and ITS for next generation 3D ITS.

###  IV-B Edge/fog

Vehicles in ITS are equipped with several sensors and computing units, GPS,
and mobiles. These devices communicate and transmit data (e.g., BSMs) using
various protocols, such as Wireless Application Protocol (WAP) or Next-
Generation Telematics Protocol (NGTP). Cloud computing is a viable solution to
store and process this massive data for decision making. However, the low-
latency requirements of vehicular communication become a bottleneck.

The introduction of fog and edge computing between the cloud and ITS
components can overcome these limitations by bringing the storage, networking,
and computing capabilities near ITS objects (i.e., vehicles). Moreover, it was
demonstrated in [7], fog computing helps in overcoming the limited on-board
computational power even for such a demanding use case as the processing of
visual information from the ”Flying eye.”

RSUs act as fog units in the traditional ITS. However, RSU has geographical
limitations that generate communication holes in the less dense RSU areas.
Furthermore, a fixed RSU cannot provide its computing services due to unstable
dynamic channel. Furthermore, a few places such as bus stops and university
areas have a few peak hours, thus not requiring a permanent RSU. Therefore,
UAVs will act as fog nodes to provide on-demand computation and communication
in the above scenarios due to mobility. One primary concern for UAVs is power
consumption during this process. However, while acting as a fog node, a UAV
will land and provide on-demand processing. Therefore, it will result in
reducing the power wastage due to hovering. Other creative ways to overcome
this problem include UAV-assisted distributed fog computing [8].

###  IV-C Artificial Intelligence

Artificial Intelligence (AI) brings intelligence to machines using its sub-
modules, i.e., Machine Learning (ML), Federated Learning (FL), and
Reinforcement Learning (RL). Therefore, AI can act as an enabler for the next
generation ITS by bringing intelligence to drones. For example, ML can help
deploy optimal number ABSs in a specific area with maximum coverage.
Furthermore, ML models can predict the wireless traffic Congestion and deploy
ABS by minimizing their mobility. Similarly, ML algorithms can help in channel
estimation between UAV-to-UAV or UAV-to-Ground. ML and RL also help in
predicting the optimal trajectory of UAVs and detecting nearby UAVs to avoid
collisions. FL is helpful in scheduling and resource allocation. For example,
distributed Support Vector Machine (SVM)-based FL can determine the LAP or HAP
each vehicle or user should connect. In addition, FL coupled with blockchain
shows promising results in crowdsensing and mitigating security and privacy
threats [9].

###  IV-D 6G networks: Integrated Aerial-terrestrial communication

##### Channel modeling

A city is an environment with ever-changing number of users, their locations,
and bandwidth needs. On the other hand, drones are highly dynamic mobile
access points. To optimize deployment strategies and UAV payloads, more
information is needed on the signal propagation between the user on the ground
and the flying base station. There currently exist a number of channel models
that address wireless propagation in an urban environment. An overview of
those models can be found in [4, 10]. No channel models consider UAV-to-
vehicle communication which is vital for UAV-enabled ITS. Moreover, the
available models are only applicable in a limited frequency band, focus on
fixed base stations and/or non-mobile end-users. Furthermore, it cannot
address medium-altitudes (above buildings, up to several km), a possible drone
deployment space.

A model that addresses these shortcomings can lead to a better understanding
of the fading effects between buildings and therefore assess the best drone
deployment areas. Additionally, link stability between mobile BSs and mobile
users (i.e., vehicles), can inform the best drone load-out and antenna
designs, as well as the number of drones that need to cater to a given number
of vehicles. And finally, the link loss for multi-hop infrastructure can be
much more accurately modeled, yielding better infrastructure topology design.

##### Routing Algorithms

The vehicles are equipped with the On-Board Units (OBUs), including different
transceivers and sensors. OBUs help the vehicles to communicate with BSs,
vehicles, and RSUs. In general, Dedicated Short Range Communication (DSRC) is
used for V2V and V2I communication. The routing in vehicles (V2V) is essential
for sharing critical messages, such as BSMs. Similarly, communication provides
external services, such as internet access and route discovery. The vehicles
form Vehicular Ad hoc NETwork (VANET) to transmit information in ITS
wirelessly. But, the VANET poses several limitations for an efficient the ITS,
including routing overhead, high packet collision, delay, scalability, and
unreliable communication.

Unreliable communication is a significant challenge in ITS due to the highly
dynamic nature of vehicles. For example, the change in V2V or V2I distance
fluctuates the Received Signal Strength Indicator (RSSI) and results in
Pathloss [11]. Similarly, the objects (buildings/trees) block the radio
signals, causing Pathloss. All these factors make the communication
unreliable, cause packet failures that lead to accidents.

Additionally, the V2I and V2V routing is done via multi-hopping reactively or
proactively. The route creation or maintenance due to the dynamicity of
vehicles generates a large routing overhead. Similarly, numerous handovers are
required in V2I communication that causes extra overhead. One more problem
with VANET in the ITS is its fixed infrastructure. Therefore, it is hard to
extend its coverage or provide dynamic support in unexpected dense scenarios.
Lastly, scalability is a concern because vehicles generate many packets,
leading to network congestion, delays, and packet loss.

The UAV resolves the above problem because it is less prone to channel
impairments due to better LoS. Therefore, it provides a reliable connection as
compared to the traditional communication in ITS. Furthermore, UAVs will act
as a relay to transmit messages from one vehicle to another because of their
better coverage. This significantly reduces the routing overhead for sending
the message over several cars. Therefore, UAV improves routing, scalability,
and Packet Delivery Ratio (PDR).

##### Space-air-ground integrated networks

Current communications infrastructure is primarily focused on users at ground
level. Near-future visions of intra- and inter-city transportation include
eVTOLs, which would require the communications network to extend up in the air
as well [12].

Space-Air-Ground Integrated Networks promises a vision of highly flexible and
dynamic network infrastructure that relies on the integration of satellites,
High- and Low-Altitude Platforms (HAP/LAPs), tethered balloons, UAVs, and
terrestrial base stations to provide unprecedented coverage, from ground to
high-altitude. Such coverage foresees the use of UAVs not only as an end-user
but also as a chain in the network itself. An integrated network aims to
bridge the gap between the distinct advantages (and disadvantages) of each
platform type. While satellites have good coverage overall, their limited
throughput, receiver needs, and signal delay limit their usability for certain
real-time applications but excel at multicasting information to a large group.
High-altitude platforms provide a cost-effective solution to service a larger
area than base stations and reduce the number of handovers required for fast-
moving vehicles. UAV-based stations will bridge large distances by achieving
line-of-sight positions and can be easily and dynamically deployed but cannot
stay in the air indefinitely.

Figure 4: Coverage probability as a function of $\lambda$ ($\chi$ = 1km).

##  V Case study: terrestrial and aerial base stations for vehicle
communications

In stochastic geometry, the Poisson Point Process (PPP) is a popular approach
to model the position of wireless nodes in a defined space/area with intensity
$\lambda$ [13]. Therefore, this paper places the ABSs and Terrestrial/Ground
Base Stations (GBS) in a circular space with radius $\chi$. However, the PPP
is not always suitable for positioning vehicles because their location is
restricted to roadways. Therefore, this case study uses a Poisson Line Process
(PLP) to model random roads in the same area with intensity $\Lambda$ [14].

This case study considers 200 cars randomly distributed over the lines/roads
defined by the PLP. Furthermore, it assumes 5G ABS and GBS with perfect
beamforming, hence completely mitigating the impact of interference. It is
also assumed that the transmission and receiver antenna gain is constant
($G_{tx}$ = 10 dBi, $G_{rx}$ = 2 dBi) and each car will be served by the
closest base station. The other parameters are: transmission power ($P_{tx}$ =
23 dBm), frequency ($f$ = 3.5 GHz) and bandwidth ($\beta$ = 20 MHz). The
Coverage Probability ($CP$) and Cumulative Distribution Function ($CDF$) of
the Signal to Noise Ratio (SNR) are computed over 500 realizations.

This case study uses the Urban Macro (UMa) path loss model from the 3rd
Generation Partnership Project [15]. Fig. 4 shows the $CP$ against varying
$\lambda$ for GBSs and ABSs at the heights of 25 m, 50 m, and 100 m. The
locations of 200 vehicles, ABSs, and GBSs are randomly generated with the PPP
and PLP using $\chi$ = 1 km and $\Lambda$ = 2. The $CP$ is defined according
to the SNR threshold ($\delta$ = 30 dB). The UAV or ABS has a better LoS
probability than GBS due to the channel geometry [4]. Due to the better
channel, ABSs provide better coverage than GBS deployed with the same density.
Simulations show that ABSs can achieve more than 95% $CP$ compared to 35% $CP$
for $\lambda=4$ BS/km2. In contrast, 35 GBSs are required to achieve 95% $CP$
with $\delta$ = 30 dB.

Fig. 5 shows the CDF as function of SNR. The locations of vehicles, ABSs, and
GBSs are randomly generated with PPP and PLP using $\chi$ = 2 km and
$\Lambda$=2 to assess the performance/coverage over a wider area. As the LoS
probability is directly proportional to height, the highest ABS at 100 m
(ABS100) shows better mean SNR than at 50 m (ABS50), at 25 m (ABS25), and GBS.
However, the height also contributes to the Pathloss. As a result, the peak
SNR can only be achieved by the lower base stations. Therefore, GBS and ABS25
offer higher SNRs than ABS50 and ABS100 for a small proportion of vehicles
placed close to these stations.

Finally, Table I illustrates the Spectral Efficiency ($SE$) against the ABS
height. In contrast to previous results, this simulation considers one GBS and
ABS placed in the center of the defined area with $\chi$ = 0.5 km and
$\Lambda$ =2, without PPP. However, the roads and vehicle locations are
determined according to PLP. Results indicate that ABS at height 40 m shows
63.5% more $SE$ than GBS. The $SE$ reduces slightly with altitude due to
larger Pathloss, as shown in Table I.

Figure 5: Cumulative Distribution Function (CDF) of SNR using GBS and ABS(h = 25m, 50m, 100m). TABLE I: Spectral efficiency as a function of height. GBS and ABS are positioned at center of Poisson area with $\chi$= 0.5 km Base Station | Height (m) | Spectral Efficiency (Bit/s/Hz)
---|---|---
GBS | 15 | 7.60
ABS | 40 | 12.43
60 | 12.35
80 | 12.30
100 | 12.29

##  VI Conclusion

The next generation ITS will have to rely on 3D connectivity provided by
Integrated Aerial-Terrestrial 6G networks. It brings UAVs as an essential part
of the ITS system. This paper envisions the convergence of UTM and traditional
ITS for the next generation 3D ITS. Therefore, this paper lists drones as new
agents of ITS and describes different use cases. Furthermore, this paper
discusses the key for the full deployment of next generation UAV-enables ITS.
Lastly, a case study is presented to compare the $SE$, $CP$, and $SNR$ of ABS
and GBS. Results show that 95% coverage is achieved using approximately 4 ABS
compared to 35% coverage using the same intensity of GBS. Furthermore, ABSs
provide a better mean SNR and show 63.5% more $SE$ over GBS.

## Acknowledgment

This research is supported by the Research Foundation Flanders (FWO), project
no. G098020N.

## References

  * [1] A. Jonas, R. Shanker, K. Liwag, M. Sharpe, B. Kovanis, E. Silverberg, E. Zaghi, and M. Pasterchick, “eVTOL/Urban Air Mobility TAM Update: A Slow Take-Off, But Sky’s the Limit,” _Morgan Stanley Research_ , May 2021.
  * [2] G. Geraci, A. Garcia-Rodriguez, M. Azari, A. Lozano, M. Mezzavilla, S. Chatzinotas, Y. Chen, S. Rangan, and M. D. Renzo, “What Will the Future of UAV Cellular Communications Be? A Flight from 5G to 6G,” _arXiv:2105.04842v1_ , 2021.
  * [3] H. Menouar, I. Guvenc, K. Akkaya, A. S. Uluagac, A. Kadri, and A. Tuncer, “UAV-Enabled Intelligent Transportation Systems for the Smart City: Applications and Challenges,” _IEEE Communications Magazine_ , vol. 55, no. 3, pp. 22–28, 2017.
  * [4] E. Vinogradov, H. Sallouha, S. De Bast, M. Azari, and S. Pollin, “Tutorial on UAVs: A Blue Sky View on Wireless Communication,” _Journal of Mobile Multimedia_ , vol. 14, no. 4, pp. 395–468, 2018.
  * [5] A. Bauranov and J. Rakas, “Designing airspace for urban air mobility: A review of concepts and approaches,” _Progress in Aerospace Sciences_ , vol. 125, p. 100726, 2021. [Online]. Available: https://www.sciencedirect.com/science/article/pii/S0376042121000312
  * [6] International Civil Avation Organization, “Unmanned Aircraft Systems Traffic Management (UTM) – A Common Framework with Core Principles for Global Harmonization - Edition 3,” Tech. Rep., 2021.
  * [7] Q. Chen, H. Zhu, L. Yang, X. Chen, S. Pollin, and E. Vinogradov, “Edge Computing Assisted Autonomous Flight for UAV: Synergies between Vision and Communications,” _IEEE Communications Magazine_ , vol. 59, no. 1, pp. 28–33, 2021.
  * [8] G. Lee, W. Saad, and M. Bennis, “Online Optimization for UAV-Assisted Distributed Fog Computing in Smart Factories of Industry 4.0,” in _2018 IEEE Global Communications Conference (GLOBECOM)_ , 2018, pp. 1–6.
  * [9] Y. Wang, Z. Su, N. Zhang, and A. Benslimane, “Learning in the Air: Secure Federated Learning for UAV-Assisted Crowdsensing,” _IEEE Transactions on Network Science and Engineering_ , vol. 8, no. 2, pp. 1055–1069, 2021.
  * [10] P. S. Bithas, V. Nikolaidis, A. G. Kanatas, and G. K. Karagiannidis, “UAV-to-Ground Communications: Channel Modeling and UAV Selection,” _IEEE Transactions on Communications_ , vol. 68, no. 8, pp. 5135–5144, 2020\.
  * [11] A. Raza, S. H. R. Bukhari, F. Aadil, and Z. Iqbal, “An UAV-assisted VANET architecture for intelligent transportation system in smart cities,” _International Journal of Distributed Sensor Networks_ , vol. 17, no. 7, p. 15501477211031750, 2021.
  * [12] N. Saeed, T. Y. Al-Naffouri, and M.-S. Alouini, “Wireless communication for flying cars,” _Frontiers in Communications and Networks_ , vol. 2, p. 16, 2021.
  * [13] H. ElSawy, A. Sultan-Salem, M.-S. Alouini, and M. Z. Win, “Modeling and analysis of cellular networks using stochastic geometry: A tutorial,” _IEEE Communications Surveys Tutorials_ , vol. 19, no. 1, pp. 167–203, 2017\.
  * [14] V. V. Chetlur and H. S. Dhillon, “Coverage analysis of a vehicular network modeled as cox process driven by poisson line process,” _IEEE Transactions on Wireless Communications_ , vol. 17, no. 7, pp. 4401–4416, 2018\.
  * [15] 3GPP, “Enhanced LTE support for aerial vehicles,” Technical Report 36.777, Jan 2018.

Abdul Saboor is working towards his PhD at the Department of Electrical
Engineering, KU Leuven. His research aims at UAVs and WBANs.
---
Sander Coene is working towards his PhD at IMEC-Ghent University. His research
aims channel modeling.
---
Evgenii Vinogradov obtained his Ph.D. degree in 2017 from UCLouvain.
Currently, Evgenii is working on 6G wireless communications and UAVs in KU
Leuven. He actively participated in SESAR (Single European Sky ATM Research)
project Percevite.
---
Emmeric Tanghe has been a Postdoctoral Researcher in propagation modeling with
the Department of Information Technology at Ghent University (imec-
UGent/INTEC) since 2011. In October 2015, he became a part-time professor in
medical applications of electromagnetic fields.  Wout Joseph is professor in
the domain of experimental characterization of wireless communication systems
with Ghent University. He has been an imec PI, since 2017. His research work
dealt with measuring and modeling of electromagnetic fields around base
stations for mobile communications related to the health effects of the
exposure to electromagnetic radiation. Sofie Pollin is professor at KU Leuven
focusing on wireless communication systems. Her research centers around
wireless networks that require networks that are ever more dense,
heterogeneous, battery powered and spectrum constrained. She pioneered a 5G
testbed for distributed Massive MIMO at KU Leuven, and is now leading the way
towards 6G tests in multiple large EU projects.
---


* Bonifati et al. (2020a) Angela Bonifati, Wim Martens, and Thomas Timm. 2020a.  An analytical study of large SPARQL query logs.  _VLDB J._ 29, 2-3 (2020), 655–679.  https://doi.org/10.1007/s00778-019-00558-9
  * Bonifati et al. (2020b) Angela Bonifati, Wim Martens, and Thomas Timm. 2020b.  SHARQL: Shape Analysis of Recursive SPARQL Queries. In _International Conference on Management of Data (SIGMOD)_. Association for Computing Machinery, New York, NY, USA, 2701–2704.  https://doi.org/10.1145/3318464.3384684
  * Carey and Kossmann (1997) Michael J. Carey and Donald Kossmann. 1997.  On Saying “Enough Already!” in SQL. In _Proceedings of the 1997 ACM SIGMOD international conference on Management of data_ (Tucson, Arizona, USA) _(SIGMOD ’97)_. Association for Computing Machinery, New York, NY, USA, 219–230.  https://doi.org/10.1145/253260.253302
  * Chaudhuri et al. (1999) Surajit Chaudhuri, Rajeev Motwani, and Vivek R. Narasayya. 1999\.  On Random Sampling over Joins. In _SIGMOD 1999, Proceedings ACM SIGMOD International Conference on Management of Data, June 1-3, 1999, Philadelphia, Pennsylvania, USA_ , Alex Delis, Christos Faloutsos, and Shahram Ghandeharizadeh (Eds.), Vol. 28. Association for Computing Machinery, New York, NY, USA, 263–274.  https://doi.org/10.1145/304181.304206
  * Chaudhuri and Shim (1994) Surajit Chaudhuri and Kyuseok Shim. 1994.  Including Group-By in Query Optimization. In _VLDB_. Morgan Kaufmann, San Francisco, CA, USA, 354–366.
  * Chaudhuri and Shim (1996) Surajit Chaudhuri and Kyuseok Shim. 1996.  Optimizing Queries with Aggregate Views. In _EDBT_ _(Lecture Notes in Computer Science)_ , Vol. 1057. Springer, 167––182.  https://doi.org/10.1007/BFb0014151
  * Chen et al. (1997) Ming-Syan Chen, Hui-I Hsiao, and Philip S. Yu. 1997\.  On Applying Hash Filters to Improving the Execution of Multi-Join Queries.  _VLDB J._ 6, 2 (1997), 121–131.  https://doi.org/10.1007/s007780050036
  * Chen and Yi (2020) Yu Chen and Ke Yi. 2020\.  Random Sampling and Size Estimation Over Cyclic Joins. In _23rd International Conference on Database Theory, ICDT 2020, March 30-April 2, 2020_ _(LIPIcs)_ , Carsten Lutz and Jean Christoph Jung (Eds.), Vol. 155. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Copenhagen, Denmark, 7:1–7:18.
  * Consortium (2018) The Gene Ontology Consortium. 2018\.  The Gene Ontology Resource: 20 years and still GOing strong.  _Nucleic Acids Research_ 47, D1 (11 2018), D330–D338.  https://doi.org/10.1093/nar/gky1055
  * Consortium (2021) The Gene Ontology Consortium. 2021\.  Gene Ontology Resource.  http://geneontology.org/stats.html (visited: 2021-06).
  * CovidGraph (2021) CovidGraph. 2021\.  COVID-19 Knowledge Graph.  https://covidgraph.org/.
  * Dalmau and Jonsson (2004) Víctor Dalmau and Peter Jonsson. 2004.  The complexity of counting homomorphisms seen from the other side.  _Theor. Comput. Sci._ 329, 1-3 (2004), 315–323.
  * Deep and Koutris (2018) Shaleen Deep and Paraschos Koutris. 2018.  Compressed Representations of Conjunctive Query Results. In _Proc. PODS 2018_ , Jan Van den Bussche and Marcelo Arenas (Eds.). ACM, New York, NY, USA, 307–322.  https://doi.org/10.1145/3196959.3196979
  * Dell et al. (2016) Holger Dell, Thore Husfeldt, Bart M. P. Jansen, Petteri Kaski, Christian Komusiewicz, and Frances A. Rosamond. 2016.  The First Parameterized Algorithms and Computational Experiments Challenge. In _Proc. IPEC 2016_ _(LIPIcs)_ , Jiong Guo and Danny Hermelin (Eds.), Vol. 63. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Aarhus, Denmark, 30:1–30:9.  https://doi.org/10.4230/LIPIcs.IPEC.2016.30
  * Dell et al. (2017) Holger Dell, Christian Komusiewicz, Nimrod Talmon, and Mathias Weller. 2017.  The PACE 2017 Parameterized Algorithms and Computational Experiments Challenge: The Second Iteration. In _Proc. IPEC 2017_ _(LIPIcs)_ , Daniel Lokshtanov and Naomi Nishimura (Eds.), Vol. 89. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Vienna, Austria, 30:1–30:12.
  * DetkDecomp (2021) DetkDecomp. 2021\.  detkdecomp.  https://github.com/daajoe/detkdecomp.
  * Durand and Mengel (2015) Arnaud Durand and Stefan Mengel. 2015.  Structural Tractability of Counting of Solutions to Conjunctive Queries.  _Theory Comput. Syst._ 57, 4 (2015), 1202–1249.  https://doi.org/10.1007/s00224-014-9543-y
  * Fagin et al. (2003) Ronald Fagin, Amnon Lotem, and Moni Naor. 2003.  Optimal aggregation algorithms for middleware.  _J. Comput. System Sci._ 66, 4 (2003), 614–656.  https://doi.org/10.1016/S0022-0000(03)00026-6 Special Issue on PODS 2001.
  * Fan et al. (2016) Wenfei Fan, Yinghui Wu, and Jingbo Xu. 2016.  Adding Counting Quantifiers to Graph Patterns. In _SIGMOD Conference_. Association for Computing Machinery, New York, NY, USA, 1215–1230.  https://doi.org/10.1145/2882903.2882937
  * Finger and Polyzotis (2009) Jonathan Finger and Neoklis Polyzotis. 2009.  Robust and efficient algorithms for rank join evaluation. In _Proceedings of the 2009 ACM SIGMOD International Conference on Management of data_. Association for Computing Machinery, New York, NY, USA, 415–428.  https://doi.org/10.1145/1559845.1559890
  * Fischl et al. (2019) Wolfgang Fischl, Georg Gottlob, Davide Mario Longo, and Reinhard Pichler. 2019.  HyperBench: A Benchmark and Tool for Hypergraphs and Empirical Findings. In _Symposium on Principles of Database Systems (PODS)_. Association for Computing Machinery, New York, NY, USA, 464–480.  https://doi.org/10.1145/3294052.3319683
  * Flum and Grohe (2004) Jörg Flum and Martin Grohe. 2004.  The Parameterized Complexity of Counting Problems.  _SIAM J. Comput._ 33, 4 (2004), 892–922.  https://doi.org/10.1137/S0097539703427203
  * Grohe (2007) Martin Grohe. 2007\.  The Complexity of Homomorphism and Constraint Satisfaction Problems Seen from the Other Side.  _J. ACM_ 54, 1 (2007), 1:1–1:24.  https://doi.org/10.1145/1206035.1206036
  * Grohe et al. (2001) Martin Grohe, Thomas Schwentick, and Luc Segoufin. 2001\.  When is the evaluation of conjunctive queries tractable?. In _ACM Symposium on Theory of Computing (STOC)_. Association for Computing Machinery, New York, NY, USA, 657–666.  https://doi.org/10.1145/380752.380867
  * Harinarayan and Gupta (1994) Venky Harinarayan and Ashish Gupta. 1994.  _Generalized Projections: A Powerful Query-Optimization Technique_.  Technical Report. Stanford University, Stanford, CA, USA.
  * Idreos et al. (2015) Stratos Idreos, Olga Papaemmanouil, and Surajit Chaudhuri. 2015\.  Overview of Data Exploration Techniques. In _Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data, Melbourne, Victoria, Australia, May 31 - June 4, 2015_. Association for Computing Machinery, New York, NY, USA, 277–281.  https://doi.org/10.1145/2723372.2731084
  * Idris et al. (2017) Muhammad Idris, Martín Ugarte, and Stijn Vansummeren. 2017.  The Dynamic Yannakakis Algorithm: Compact and Efficient Query Processing Under Updates. In _International Conference on Management of Data (SIGMOD)_. Association for Computing Machinery, New York, NY, USA, 1259–1274.  https://doi.org/10.1145/3035918.3064027
  * Ilyas et al. (2004) Ihab F Ilyas, Walid G Aref, and Ahmed K Elmagarmid. 2004\.  Supporting top-k join queries in relational databases.  _The VLDB journal_ 13, 3 (2004), 207–221.  https://doi.org/10.1007/s00778-004-0128-2
  * Ilyas et al. (2008) Ihab F. Ilyas, George Beskales, and Mohamed A. Soliman. 2008\.  A survey of top-_k_ query processing techniques in relational database systems.  _Comput. Surveys_ 40, 4 (2008), 11:1–11:58.
  * Ilyas and Chu (2019) Ihab F. Ilyas and Xu Chu. 2019.  _Data Cleaning_.  ACM, New York, NY, USA.  https://doi.org/10.1145/3310205
  * Ives and Taylor (2008) Zachary G. Ives and Nicholas E. Taylor. 2008.  Sideways Information Passing for Push-Style Query Processing. In _ICDE_. IEEE Computer Society, 774–783.  https://doi.org/10.1109/ICDE.2008.4497486
  * Joglekar et al. (2016) Manas R Joglekar, Rohan Puttagunta, and Christopher Ré. 2016\.  Ajar: Aggregations and joins over annotated relations. In _Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems_. Association for Computing Machinery, New York, NY, USA, 91–106.  https://doi.org/10.1145/2902251.2902293
  * Kara and Olteanu (2018) Ahmet Kara and Dan Olteanu. 2018.  Covers of Query Results. In _21st International Conference on Database Theory_ _(LIPIcs)_ , Benny Kimelfeld and Yael Amsterdamer (Eds.), Vol. 98. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Vienna, Austria, 16:1–16:22.
  * Khamis et al. (2016) Mahmoud Abo Khamis, Hung Q. Ngo, and Atri Rudra. 2016\.  FAQ: Questions Asked Frequently. In _Proc. PODS 2016_. Association for Computing Machinery, New York, NY, USA, 13–28.  https://doi.org/10.1145/2902251.2902280
  * Kim et al. (2016) Albert Kim, Liqi Xu, Tarique Siddiqui, Silu Huang, Samuel Madden, and Aditya Parameswaran. 2016.  _Optimally Leveraging Density and Locality for Exploratory Browsing and Sampling_.  Technical Report. Univeristy of Illinois.  https://data-people.cs.illinois.edu/needletail.pdf
  * Kim et al. (2018) Albert Kim, Liqi Xu, Tarique Siddiqui, Silu Huang, Samuel Madden, and Aditya Parameswaran. 2018.  Optimally Leveraging Density and Locality for Exploratory Browsing and Sampling. In _Proceedings of the Workshop on Human-In-the-Loop Data Analytics_ (Houston, TX, USA) _(HILDA’18)_. Association for Computing Machinery, New York, NY, USA, 7.  https://doi.org/10.1145/3209900.3209903
  * Kohli et al. (1994) Rajeev Kohli, Ramesh Krishnamurti, and Prakash Mirchandani. 1994\.  The Minimum Satisfiability Problem.  _SIAM J. Discret. Math._ 7, 2 (1994), 275–283.  https://doi.org/10.1137/S0895480191220836
  * Krötzsch (2018) Markus Krötzsch. 2018\.  Practical Linked Data Access via SPARQL: The Case of Wikidata. In _LDOW@ WWW_. CEUR Workshop Proceedings, Lyon, France, 1–10.
  * Lbath et al. (2021) Hanâ Lbath, Angela Bonifati, and Russ Harmer. 2021\.  Schema Inference for Property Graphs. In _Proceedings of the 24th International Conference on Extending Database Technology, EDBT 2021_. OpenProceedings.org, Nicosia, Cyprus, 499–504.  https://doi.org/10.5441/002/edbt.2021.58
  * Leis et al. (2018) Viktor Leis, Bernhard Radke, Andrey Gubichev, Atanas Mirchev, Peter Boncz, Alfons Kemper, and Thomas Neumann. 2018.  Query optimization through the looking glass, and what we found running the join order benchmark.  _The VLDB Journal_ 27, 5 (2018), 643–668.  https://doi.org/10.1007/s00778-017-0480-7
  * Li et al. (2005) Chengkai Li, Kevin Chen-Chuan Chang, Ihab F. Ilyas, and Sumin Song. 2005.  RankSQL: Query Algebra and Optimization for Relational Top-k Queries. In _Proceedings of the ACM SIGMOD International Conference on Management of Data, Baltimore, Maryland, USA, June 14-16, 2005_. Association for Computing Machinery, New York, NY, USA, 131–142.  https://doi.org/10.1145/1066157.1066173
  * Mackert and Lohman (1986) Lothar F. Mackert and Guy M. Lohman. 1986.  R* Optimizer Validation and Performance Evaluation for Distributed Queries. In _VLDB_. Morgan Kaufmann, New York, NY, USA, 149––159.  https://doi.org/10.1145/16894.16863
  * Malyshev et al. (2018) Stanislav Malyshev, Markus Krötzsch, Larry González, Julius Gonsior, and Adrian Bielefeldt. 2018\.  Getting the Most Out of Wikidata: Semantic Technology Usage in Wikipedia’s Knowledge Graph. In _International Semantic Web Conference (ISWC)_. Springer, Cham, 376–394.  https://doi.org/10.1007/978-3-030-00668-6_23
  * Mamoulis et al. (2007) Nikos Mamoulis, Man Lung Yiu, Kit Hung Cheng, and David W Cheung. 2007.  Efficient top-k aggregation of ranked inputs.  _ACM Transactions on Database Systems (TODS)_ 32, 3 (2007), 19–es.
  * Natsev et al. (2001) Apostol Natsev, Yuan-Chi Chang, John R Smith, Chung-Sheng Li, and Jeffrey Scott Vitter. 2001\.  Supporting incremental join queries on ranked inputs. In _VLDB_ , Vol. 1. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 281–290.
  * Olteanu and Závodný (2015) Dan Olteanu and Jakub Závodný. 2015.  Size Bounds for Factorised Representations of Query Results.  _ACM Trans. Database Syst._ 40, 1 (2015), 2:1–2:44.  https://doi.org/10.1145/2656335
  * Orr et al. (2019) Laurel J. Orr, Srikanth Kandula, and Surajit Chaudhuri. 2019\.  Pushing Data-Induced Predicates Through Joins in Big-Data Clusters.  _Proc. VLDB Endow._ 13, 3 (2019), 252––265.  https://doi.org/10.14778/3368289.3368292
  * Pichler and Skritek (2013) Reinhard Pichler and Sebastian Skritek. 2013.  Tractable counting of the answers to conjunctive queries.  _J. Comput. System Sci._ 79, 6 (Sep 2013), 984–1001.  https://doi.org/10.1016/j.jcss.2013.01.012
  * Tziavelis et al. (2020a) Nikolaos Tziavelis, Deepak Ajwani, Wolfgang Gatterbauer, Mirek Riedewald, and Xiaofeng Yang. 2020a.  Optimal Algorithms for Ranked Enumeration of Answers to Full Conjunctive Queries.  _Proc. VLDB Endow._ 13, 9 (2020), 1582–1597.  http://www.vldb.org/pvldb/vol13/p1582-tziavelis.pdf
  * Tziavelis et al. (2020b) Nikolaos Tziavelis, Deepak Ajwani, Wolfgang Gatterbauer, Mirek Riedewald, and Xiaofeng Yang. 2020b.  Optimal Algorithms for Ranked Enumeration of Answers to Full Conjunctive Queries.  arXiv:1911.05582 [cs.DB]
  * Vose (1991) Michael D. Vose. 1991\.  A Linear Algorithm For Generating Random Numbers With a Given Distribution.  _IEEE Transactions on software engineering_ 17, 9 (1991), 972–975.
  * Vrandečić (2012) Denny Vrandečić. 2012\.  Wikidata: A New Platform for Collaborative Data Collection. In _Proceedings of the 21st International Conference on World Wide Web_ (Lyon, France) _(WWW ’12 Companion)_. Association for Computing Machinery, New York, NY, USA, 1063–1064.  https://doi.org/10.1145/2187980.2188242
  * Walker (1977) Alastair J. Walker. 1977\.  An Efficient Method for Generating Discrete Random Variables with General Distributions.  _ACM Trans. Math. Softw._ 3, 3 (1977), 253–256.
  * WikiData (2021) WikiData. 2021.  WikiData Query Service.  http://query.wikidata.org/.
  * Yan and Larson (1995) Weipeng P. Yan and Per-Åke Larson. 1995.  Eager Aggregation and Lazy Aggregation. In _VLDB_. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 345––357.
  * Yannakakis (1981) Mihalis Yannakakis. 1981\.  Algorithms for Acyclic Database Schemes. In _Proc. VLDB 1981_ (Cannes, France). IEEE Computer Society, Cannes, France, 82–94.
  * Zhao et al. (2018) Zhuoyue Zhao, Robert Christensen, Feifei Li, Xiao Hu, and Ke Yi. 2018.  Random Sampling over Joins Revisited. In _Proceedings of the 2018 International Conference on Management of Data, SIGMOD Conference 2018, Houston, TX, USA, June 10-15, 2018_ , Gautam Das, Christopher M. Jermaine, and Philip A. Bernstein (Eds.). Association for Computing Machinery, New York, NY, USA, 1525–1539.  https://doi.org/10.1145/3183713.3183739


#  A note on $\overline{2}$-separable codes and $B_{2}$ codes

Stefano Della Fiore and Marco Dalai,
Department of Information Engineering, University of Brescia

###### Abstract

We derive a simple proof, based on information theoretic inequalities, of an
upper bound on the largest rates of $q$-ary $\overline{2}$-separable codes
that improves recent results of Wang for any $q\geq 13$. For the case $q=2$,
we recover a result of Lindström, but with a much simpler derivation. The
method easily extends to give bounds on $B_{2}$ codes which, although not
improving on Wang’s results, use much simpler tools and might be useful for
future applications.

##  1 Introduction

Let for notational convenience $[0,q-1]=\\{0,1,\ldots q-1\\}$. We call a
$q$-ary code of length $n$ any subset of $C_{n}\subseteq[0,q-1]^{n}$. Let
$M=|C_{n}|$ and write $C_{n}=\\{c_{1},c_{2},\ldots,c_{M}\\}$. Each $c_{i}$ is
called a codeword and we use the notation $c_{i}(j)$, for $j=1,2,\ldots,n$ for
its components. The base-$q$ rate of such a code is defined as $\log_{q}M/n$.
Note that, throughout, all logarithms without subscript are to base 2.

We need two definitions.

######  Definition 1.1.

A $q$-ary code $C_{n}$ with codewords of length $n$ is a $t$-frameproof code
if for any $t$ codewords and every other codeword, there exists a coordinate
$i$ with $1\leq i\leq n$, in which the symbols of the $t$ codewords do not
contain the symbol of the other codeword.

######  Definition 1.2.

A $q$-ary code $C_{n}$ with codewords of length $n$ is a
$\overline{t}$-separable code if for any distinct $k$ codewords and $m$
codewords with $1\leq k,m\leq t$, there exists a coordinate $i$, $1\leq i\leq
n$, in which the union of the elements of the $k$ codewords differs from the
union of the elements of the $m$ codewords.

Blackburn [5], [6] showed that the rate of $t$-frameproof codes is upper
bounded by $1/t$. Cheng and Miao [4] observed that any $t$-frameproof code is
a $\overline{t}$-separable code and also that any $\overline{t}$-separable
code is a $(t-1)$-frameproof code for every $t\geq 2$. This implies that the
rate of $\overline{t}$-separable codes is upper bounded by $1/(t-1)$.
Interesting results on $\overline{t}$-separable code, with the slightly weaker
constraint that only $k=m=t$ is considered in the definition, were recently
derived in [9] using an information theoretic approach. With this slightly
different definition, an upper bound on the rate of the form $2/t$ was
obtained. Since both bounds give the trivial $1/(t-1)=2/t=1$ for $t=2$, other
approaches must be adopted for bounding the rate of $\overline{2}$-separable
codes, which leads to a rather interesting problem.

A non-trivial bound for $q$-ary $\overline{2}$-separable codes was derived by
Gu, Fan and Miao in [2] and an improvement was recently obtained by Wang [3]
for every ${3\leq q\leq 17}$ extending a procedure introduced for the binary
case by Cohen et al. [7] based on linear programming bounds on codes.

##  2 New Upper Bounds for $\bar{2}$-separable codes

We have the following new bound on the rate of $\overline{2}$-separable codes

######  Theorem 2.1.

For integer $q\geq 2$, let $C_{n}$ be a family of $q$-ary
$\overline{2}$-separable codes. Then

$R_{s}:=\limsup_{n\to\infty}\frac{1}{n}\log_{q}|C_{n}|\leq\frac{2q-1}{3q-1}\,.$

This bound improves the one given by Wang [3] when ${q\geq 13}$. It also
improves the bound of Gu et al. [2] for every ${q\geq 2}$. When $q=2$,
instead, the bound coincides with that of Lindström [1], but with a rather
simpler proof.

###### Proof of Theorem 2.1.

Let $D=\\{(x,y)\in[0,q-1]^{2}:x\neq y\\}\cup\\{0\\}$, which implies
${|D|=q(q-1)+1}$. Define the function $\phi:[0,q-1]^{2}\to D$ as

$\phi(x,y)=\begin{cases}0,&\mbox{if }x=y\\\ (x,y),&\mbox{if }x\neq
y\end{cases}.$

For an integer $f$, we define $\Phi$, the natural extension of $\phi$ when
applied to vectors, that is the function that maps any two vectors
$w_{1},w_{2}\in$ ${[0,q-1]^{f}}$ in a vector in $D^{f}$ according to the rule

$\displaystyle\Phi(w_{1},$ $\displaystyle
w_{2})=\left(\phi(w_{1}(1),w_{2}(1)),\ldots,\phi(w_{1}(f),w_{2}(f))\right)\in
D^{f}.$

Let $C_{n}=\\{c_{1},c_{2},\ldots,c_{M}\\}$ be a $q$-ary
$\overline{2}$-separable code with codewords of length $n$. We divide each
codeword $c_{i}$ in two sub-blocks, a prefix $p_{i}$ of length $e$ and a
suffix $w_{i}$ of length $f$ where $n=e+f$. We use here the notation
$c_{i}=(p_{i},w_{i})$.

Enumerate all the vectors in $[0,q-1]^{e}$ as $l_{1},l_{2},\ldots,l_{r}$,
where $r=q^{e}$, and denote with $P_{i}$ the set of codewords of $C_{n}$ which
have $l_{i}$ as the first $e$ components, that is of the form $(l_{i},w_{j})$.
An easy upper bound on $M$ then follows by the Cauchy-Schwarz inequality,
namely

$\frac{M^{2}}{r}\leq\sum_{i=1}^{r}|P_{i}|^{2}.$ (1)

We want a good upper bound on the sum of the ordered pairs in each $P_{i}$ to
get a good upper bound on $M$. From [2, Theorem 2], we know that the function
$\Phi$ is injective when we restrict its domain to pairs of suffixes of
different vectors taken from the same $P_{i}$ for all $i=1,\ldots,r$. We
provide a short proof in order to have a self-contained paper. Assume, for the
sake of contradiction, there exists four different codewords
$(l_{h},w_{1}),(l_{h},w_{2})\in P_{h}$, $(l_{m},w_{3}),(l_{m},w_{4})\in P_{m}$
such that $\Phi(w_{1},w_{2})=\Phi(w_{3},w_{4})$ either when $h=m$ and
$(w_{1},w_{2})\neq(w_{3},w_{4})$ or when $h\neq m$. For case $h=m$, if
$\\{w_{1},w_{2}\\}\cap\\{w_{3},w_{4}\\}\neq\emptyset$ then
$\Phi(w_{1},w_{2})=\Phi(w_{3},w_{4})$ implies a contradiction on the
assumption $(w_{1},w_{2})\neq(w_{3},w_{4})$. Otherwise, when
$\\{w_{1},w_{2}\\}\cap\\{w_{3},w_{4}\\}=\emptyset$, the subcodes
$C_{1}=\\{(l_{h},w_{1}),(l_{h},w_{4})\\}$ and
$C_{2}=\\{(l_{h},w_{2}),(l_{h},w_{3})\\}$ do not satisfy the
$\overline{2}$-separability property, a contradiction. Instead for case $h\neq
m$, $\Phi(w_{1},w_{2})=\Phi(w_{3},w_{4})$ implies that the subcodes
$C_{1}=\\{(l_{h},w_{1}),(l_{m},w_{4})\\}$ and
$C_{2}=\\{(l_{h},w_{2}),(l_{m},w_{3})\\}$ do not satisfy the
$\overline{2}$-separability property, again a contradiction.

We generalize a smart observation given in [1, eq. (2.9)]. Fix a coordinate
$\ell$ and a subcode $P_{i}$ in our code $C_{n}$, and let
$f_{0},f_{1},\ldots,f_{q-1}$ to be the fractions of symbols that occur in the
$\ell$-th cooordinate of $P_{i}$. Then, when we take all vectors
$\Phi(w_{j},w_{k})$, where $w_{j}$ and $w_{k}$ are the suffixes of codewords
(not necessarily distinct) that belong to $P_{i}$, the frequency of the $0$
symbol in the $\ell$-th coordinate of these vectors is equal to
$f_{0}^{2}+\cdots+f_{q-1}^{2}$. This summation is always greater than or equal
to $1/q$ under the constraint that $\sum_{i=0}^{q-1}f_{i}=1$. So, the fraction
of $0^{\prime}$ in the $\ell$-th coordinate of the vectors
$\Phi(w_{j},w_{k})$, where $w_{j}$ and $w_{k}$ are suffixes in $P_{i}$ for
each $i=1,\ldots,r$, is not smaller than $1/q$.

Let $X=(X_{1},\ldots,X_{f})$ and $Y=(Y_{1},\ldots,Y_{f})$ be two random
variables with joint uniform distributions over the set of ordered pairs of
suffixes of vectors taken form the same $P_{i}$ for each $i=1,\ldots,r$. Then
we have that

$H(X,Y)=\log\left(\sum_{i=1}^{r}|P_{i}|^{2}\right),$ (2)

where $H$ is the Shannon entropy.

We define, for every $i=1,\ldots,f$, the random variable $Z_{i}$ by setting
$Z_{i}=\phi(X_{i},Y_{i})$. Since the function $\Phi(x,y)$ is injective when
$x\neq y$ and knowing that $Z=(Z_{1},\ldots,Z_{f})=\Phi(X,Y)$, then

$H(X,Y)=H(Z)+\Pr(Z=\underline{0})\cdot H(X,Y|Z=\underline{0}).$ (3)

By the well-known subadditivity property of the entropy function we have

$\displaystyle H(Z)\leq\sum_{i=1}^{f}H(Z_{i})\leq
f\left(\max_{\begin{subarray}{c}\alpha_{0},\ldots,\alpha_{q^{2}-q}\\\
\alpha_{0}+\cdots+\alpha_{q^{2}-q}=1\\\ \alpha_{0}\geq
1/q\end{subarray}}H(\alpha_{0},\ldots,\alpha_{q^{2}-q})\right)$ (4)

where we abuse the notation using $H$ also for the entropy of a distribution
and $\alpha_{i}$ represents the frequency of the $i$-th symbol. It is easy to
see that the maximum in (4) is achieved when $\alpha_{0}=1/q$ and
$\alpha_{1}=\cdots=\alpha_{q^{2}-q}=1/q^{2}$ and takes the value $\log
q\cdot(2q-1)/q$.

By (1) we get

$\Pr(Z=\underline{0})=\frac{M}{\sum_{i=1}^{r}|P_{i}|^{2}}\leq\frac{r}{M}.$ (5)

The conditional distribution $P(X=x,Y=y|Z=\underline{0})$ is uniform over its
support which has size equal to $M$. Then

$H(X,Y|Z=\underline{0})=\log M.$ (6)

Setting $e=\lfloor\log_{q}(2M)-\log_{q}\log M\rfloor$ we have by (5) and (6)
that

$\Pr(Z=\underline{0})\cdot H(X,Y|Z=\underline{0})\leq\frac{r}{M}\log M\leq 2.$
(7)

Then by (2), (3), (4) and (7) we have

$\sum_{i=1}^{r}|P_{i}|^{2}\leq q^{f(2q-1)/q+o(n)}$ (8)

where $o(n)$ is meant as $n\to\infty$.

Finally we are now ready to prove Theorem 2.1. By (1) and (8) we have that

$M^{2}\leq q^{f(2q-1)/q+e+o(n)}.$ (9)

Since $e$ is fixed and we know that $n=e+f$, from (9) we get

$M\leq q^{n\frac{2q-1}{3q-1}+o(n)}$

and Theorem 2.1 follows. ∎

In Figure 2 we give a comparison between the bounds on the rate of
$\overline{2}$-separable codes given in [2], [3] and the one given in Theorem
2.1.

##  3 Bounds for $B_{2}$ codes

The related notion of $B_{2}$ codes can be introduced as follows.

######  Definition 3.1.

We say that $C_{n}=\\{c_{1},c_{2},\ldots,c_{M}\\}$ is a $q$-ary $B_{2}$ code
with $M$ codewords of length $n$ and with symbols in the alphabet $[0,q-1]$ if
all sums (over the real field) $c_{i}+c_{j}$ for $1\leq i\leq j\leq n$ are
different.

Note that for $q=2$ this definition is equivalent to the definition of a
$\bar{2}$-separable code. Gu et al. in [2] provide non trivial bounds on the
rate of $q$-ary $B_{2}$ codes and they also observed that an implicit upper
bound can be found in Lindtröm [1, Theorem 1]. These bounds were improved by
Wang [3] for every ${2\leq q\leq 12}$.

An immediate extension of the method presented in the previous section leads
to the following.

######  Theorem 3.2.

For integer $q\geq 2$, let $C_{n}$ be a family of $q$-ary $B_{2}$ codes. Then

$R_{b}:=\limsup_{n\to\infty}\frac{1}{n}\log_{q}|C_{n}|\leq\frac{q+(q-1)\log_{q}2}{2q+(q-1)\log_{q}2}.$

For every ${3\leq q\leq 12}$ it improves the one given in [2] but not the
bound given in [3]. Of course, when ${q=2}$, Theorems 2.1 and 3.2 give the
same bound consistently with the fact that any binary $\overline{2}$-separable
code is also a $B_{2}$ code and vice versa.

###### Proof of Theorem 3.2.

In this case, we consider the set $D=\\{-q+1,\ldots,-1,$ $0,1,\ldots,q-1\\}$,
so that now $|D|=2q-1$. For an integer $f$, we define the function $\Phi$ as
$\Phi(w_{1},w_{2})=w_{1}-w_{2}\in D^{f}$ where $w_{1},w_{2}\in[0,q-1]^{f}$ and
the difference is computed in $\mathbb{Z}$.

Let $C_{n}$ be a $q$-ary $B_{2}$ code and suppose we have constructed the
$r=q^{e}$ subcodes $P_{i}$ (as done in Theorem 2.1). It can be proved, in a
similar manner as Theorem 2.1, that $\Phi$ is injective when we restrict its
domain to pairs of suffixes of different vectors taken from the same $P_{i}$
for all $i=1,\ldots,r$. Then, the procedure used in Theorem 2.1 can be applied
to prove Theorem 3.2. All the equations from (1) to (9) are verified, also in
this case, with the only difference that the cardinality of the set $D$ is
$2q-1$ and not $q^{2}-q+1$. ∎

In Figure 2 we give a comparison between the bounds on the rate of $B_{2}$
codes given in [2], [1, Theorem 1], [3] and the one given in Theorem 3.2.

Figure 1: Upper bounds on $R_{s}$.

Figure 2: Upper bounds on $R_{b}$.

## References

  * [1] B. Lindström _On $B_{2}$-Sequences of Vectors_, Journal Of Number Theory 4, 261-265, 1972.
  * [2] Y. Gu, J.Fan, and Y. Miao _Improved Bounds for Separable Codes and $B_{2}$ Codes_, IEEE Communications Letters vol. 24, no. 1, January 2020.
  * [3] X. Wang _Improved upper bounds for parent-identifying set systems and separable codes_ , Designs, Codes and Cryptography, October 2020.
  * [4] M. Cheng and Y. Miao, _On anti-collusion codes and detection algo- rithms for multimedia fingerprinting,_ IEEE Trans. Inf. Theory, vol. 57, no. 7, pp. 4843-4851, Jul. 2011.
  * [5] S. R. Blackburn, _Frameproof codes,_ SIAM J. Discrete Math., vol. 16, no. 3, pp. 499-510, 2003.
  * [6] S. R. Blackburn, _Probabilistic existence results for separable codes,_ IEEE Trans. Inf. Theory, vol. 61, no. 11, pp. 5822-5827, Nov. 2015.
  * [7] G. Cohen, S. Litsyn, and G. Zémor, _Binary $B_{2}$ sequences: A new upper bound,_ J. Combinat. Theory, Ser. A, vol. 94, no. 1, pp. 152-155, Apr. 2001.
  * [8] T. M. Cover and J. A. Thomas, _Elements of information theory_ , John Wiley & Sons, 2012.
  * [9] Arkadii D’yachkov, Nikita Polyanskii, Vladislav Shchukin and Ilya Vorobyev, _Separable Codes for the Symmetric Multiple-Access Channel_ , IEEE Trans. Inf. Theory, vol. 65, no. 6, pp. 3738-3750, 2019.