# System Theoretic View on Uncertainties
††thanks: The research leading to these results has received funding from the
European Union’s Horizon 2020 research and innovation program under the Marie
Sklodowska-Curie grant agreement No 812.788 (MSCA-ETN SAS).This publication
reflects only the authors view, exempting the European Union from any
liability. Project website: http://etn-sas.eu/.

Roman Gansch  Corporate Research,
Robert Bosch GmbH,
Renningen, Germany
<EMAIL_ADDRESS>Ahmad Adee  Corporate Research,
Robert Bosch GmbH,
Renningen, Germany
<EMAIL_ADDRESS>
###### Abstract

The complexity of the operating environment and required technologies for
highly automated driving is unprecedented. A different type of threat to safe
operation besides the fault-error-failure model by Laprie et al. arises in the
form of performance limitations. We propose a system theoretic approach to
handle these and derive a taxonomy based on uncertainty, i.e. lack of
knowledge, as a root cause. Uncertainty is a threat to the dependability of a
system, as it limits our ability to assess its dependability properties. We
distinguish uncertainties by aleatory (inherent to probabilistic models),
epistemic (lack of model parameter knowledge) and ontological (incompleteness
of models) in order to determine strategies and methods to cope with them.
Analogous to the taxonomy of Laprie et al. we cluster methods into uncertainty
prevention (use of elements with well-known behavior, avoiding architectures
prone to emergent behavior, restriction of operational design domain, etc.),
uncertainty removal (during design time by design of experiment, etc. and
after release by field observation, continuous updates, etc.), uncertainty
tolerance (use of redundant architectures with diverse uncertainties,
uncertainty aware deep learning, etc.) and uncertainty forecasting (estimation
of residual uncertainty, etc.).

###### Index Terms:

safety, uncertainty, autonomous vehicles, cybernetics, systems modeling,
taxonomy

##  I Introduction

Assuring system safety of highly automated driving vehicles is an
unprecedented challenge in engineering. Complex tasks like interpretation of
the surrounding world, which previously were handled by a human driver, have
to be mastered autonomously by the self-driving car. Novel technologies like
machine learning for perception or Lidar sensors are used in these systems.
The system environment which is characterized by an open context, i.e.
unpredictability of the operational domain [1], and limited knowledge about
the achievable performance of the system components results in a high degree
of complexity that has to be dealt with.

Established safety engineering practices and standards like ISO2626:2018 [2]
focus on functional safety and well known internal malfunctions of the system.
These malfunctions arise due to a deviation of the actual behavior to a well-
defined function specification. In complex autonomous systems it is infeasible
to provide a complete function specification and fully analyze the implemented
behavior for deviations. This leads to multiple gaps in the overall
engineering lifecycle that have to be overcome for a safety argumentation [1,
3]. The root cause for the identified gaps is a lack of knowledge, i.e.
uncertainty. This aspect is addressed by the safety of the intended
functionality (SOTIF) ISO/PAS21448 standard [4] in the form of sufficient
reduction of unknown unsafe scenarios.

While uncertainty has been considered as a residual risk in the failure of
hardware components, it was not incorporated as a general lack of knowledge
over the whole engineering lifecycle. Several methods to handle this novel
kind of uncertainty have been developed. These include machine learning with
uncertainty estimations [5, 6] or saliency maps [7] that can be used for
implementation and during runtime. Other aspects of the lifecycle are for
example addressed by safety analysis incorporating uncertainty via evidence
theory [8] or verification with probabilistic formal methods [9, 10]. For the
overall confidence to release a product assurance cases can be enriched with
belief modeling [11]. These methods provide specialized solutions for problems
regarding uncertainty in their respective domain. Some of these methods are
complementary, while others are redundant. However, in the overall engineering
lifecycle it is not yet clear how these methods should be meshed together to
sufficiently address the gaps due to uncertainty.

In this work, we define an initial taxonomy for uncertainties in order to
derive this overall strategy. Our work is based on the taxonomy for
dependability that has been defined by Laprie et al. [12, 13]. The taxonomy of
Laprie builds on the foundations of system theory and is thus generalized to
all application domains. It distinguishes between the properties
(availability, reliability, etc.), threats (fault, error, failure) and means
to dependability (fault prevention, removal, tolerance and forecasting) and
provides a general framework to engineer dependable systems. However, it does
not adequately address the impact of uncertainty on dependability, which is a
major challenge encountered in autonomous systems and leads to ambiguity when
applying the fault-error-failure model. Therefore, we adopt the system
theoretic approach to define an appropriate taxonomy. A core element of our
taxonomy is a distinction between different types of uncertainty. Analogous to
faults, the means to handle these uncertainties are included, which can be
used to classify existing methods and derive a holistic strategy.

ncom

##  II Systems approach to uncertainty

In order to formalize the uncertainties encountered in the development of
autonomous systems, we adopt the system theoretic viewpoint from cybernetics.
We refer to the higly automated driving vehicle being developed as System
under Development (SuD). The control loop of interest for us is between the
organization developing the SuD (controlling system) and the SuD embedded in
its operating environment (controlled system). This viewpoint is analogue to
the cognitive system engineering approach by Rasmussen [14] and the system
theoretic accident model and processes (STAMP) by Leveson [15].

The information for developing the SuD is obtained by domain analysis, which
acts as an observation channel for the cybernetic control loop (Fig. 1). From
the domain analysis developers derive the needs and requirements for the SuD.
The developing organization then implements the system and deploys it in the
operating environment. The implementation acts as the influencing channel of
the control loop. By feedback through prototypes and field observation, the
control loop is continuously iterated.

Figure 1: The cybernetic point of view of a development process consists of
the controlled system: system under development (SuD) embedded in its
environment and the controlling system: development organization.

The controlling system exists of several subsystems like people, tools or
infrastructure. These are in a complex and symbiotic relationship. For our
viewpoint, the detailed interaction are not of interest. We are mostly
interested in the mental and codified models within the organization. The
mental models are formed on an individual basis and represent the state of
knowledge of each person, which also contains tacit knowledge, i.e. knowledge
that cannot be codified into information [16]. The individual knowledge is
made explicit by transformation into information within the codified models by
using processes, methods and tools. The codified models are used for several
purposes like communication of mental models between developers or
implementation of the system.

A fundamental principle of the cybernetic control loop is the good regulator
theorem formulated by Ashby [17, 18]. It states that every good regulator of a
system must be a model of that system in order to achieve a good outcome (i.e.
a SuD fulfilling its purpose). The controlling system needs to be able to
predict the influence of its controlling actions on the controlled system with
a model. This shows the importance of the models, as these have to be accurate
to perform the correct actions. Uncertainty can be attributed to inaccurate or
wrong model.

###  II-A System models

It is crucial to understand what a model is composed of and which properties
it has to fulfill in order to be useful. A formal basis for models has been
formulated by Rosen [19]. He stresses the importance of the modeling relation
(Fig. 2): an isomorphic encoding $\epsilon_{A,B}$ and decoding $\delta_{A,B}$
of relevant properties of the physical system into formal systems. The
causality in the physical system is thereby mapped to logic inferences in the
model. Such models can be mathematical equations, SysML diagrams or, in the
context of safety engineering, failure analysis models (e.g. fault tree
analysis).

Figure 2: Modeling relation between a physical system consisting of two ideal
point masses (planet 1 and 2) and two formal systems as models.

Multiple modeling relations between physical and formal systems can be
established, i.e. there are multiple models available for a system. These are
different representations tailored to the specific needs of the modeler. Since
our focus is on the uncertainty aspect of modeling, it is important to
distinguish between deterministic and probabilistic models. From the former a
singular outcome can be inferred for a given input, while for the latter only
statements about probabilistic outcomes can be inferred. On a very fine
granular level the physical world itself becomes inherently probabilistic due
to quantum mechanics. For these physical processes only probabilistic models
are applicable. However, on a macroscopic level deterministic relations
dominate causality and it is the choice of the modeler to choose either a
deterministic or probabilistic representation of a physical system as a model.

To give an example, consider a reality where only two planets exist, with a
homogeneous mass distribution (i.e. they can be treated as point masses).
These exert a gravitational force on each other and influence each other’s
movement through space and time resulting in elliptic orbits. We will show how
a deterministic as well as probabilistic model can be built for the same
physical system.

The behavior of this system can be described by Newton’s laws (Fig. 2: model
A). The mathematical formulas for gravitational forces and motion result in a
set of differential equations. These represent a deterministic model that
allows inferring the causality of motion of the bodies. Given the starting
conditions of initial position and velocity, every future state of the system
can be inferred. In principle, it would be possible to also apply this to
arbitrarily complex many-body problems. Regardless of the complexity of the
problem, calculating the future state of the entire universe is always
possible with a hypothetical Laplace demon [20]. An entity that knows the
entire present state of the universe with unlimited calculation capacity to
exactly predict the future state. In reality, however there are practical
(availability of information, computation capacity, etc.) as well as
theoretical (Gödel’s incompleteness theorem, quantum mechanics, free will,
etc.) limits to determinism [21].

Another way to describe the system of two planets is to adopt the frequentist
point of view (Fig. 2: model B). This means, to build a probabilistic model by
repeated observation of the positions. With an infinite amount of
observations, the exact probabilities to find either of the two bodies within
a spatial frame can be inferred from the obtained probability density
functions.

Both models, the deterministic and probabilistic, fulfill the modeling
relation and allow to draw conclusions about the behavior of the system. Each
model has its own purpose and is valid for a given set of behavior that the
modeler wants to describe. While the deterministic one is useful to e.g.
calculate the trajectory for satellites, the probabilistic one is useful e.g.
for predicting the chance of meteor impacts.

This example illustrates that the property of determinism and probability also
have to be attributed to the model and not only to the system itself. Only
when dealing with systems that are strongly influenced by the theoretical
limits of determinism the probabilistic nature becomes inherent. Models can
also be a mixture of deterministic and probabilistic elements and it is the
choice of the modeler, which representation of the system best fits his needs.

##  III Types of Uncertainties

Uncertainties refer to the notion of unknown or insufficient knowledge [22].
As a generic concept of the unknown, incomplete or imperfect knowledge, it has
been classified in various contexts in the literature [23, 24, 25, 26]. In our
system theoretic approach to developing highly automated driving vehicles, we
focus on the importance of models to represent our knowledge. Depending upon
the origins of uncertainties in our models, we distinguish between aleatory,
epistemic and ontological uncertainties.

###  III-A Aleatory Uncertainty

_Aleatory uncertainty can be regarded as randomness of a process represented
by a system model._

Aleatory uncertainty is considered to be irreducible for a given choice of a
probabilistic model and is quantified by probabilistic distributions [26].

As an example, we continue with the physical system consisting of two planets
of the previous section. We are interested in the probabilistic spatial
distribution of the point masses. We therefore use model B of Fig. 2, which
provides a probability that a planet is found in a given spatial frame. With
this probabilistic model of spatial distribution, the probabilities to find a
point mass in a certain frame depict a mere belief and the crisp location at a
given instant is subject to aleatory uncertainty.

###  III-B Epistemic Uncertainty

_Epistemic uncertainty is associated to lack of knowledge about the system
model and the inexact encoding of physical system to models._

An important aspect of epistemic uncertainty is that we lack in knowledge but
we are aware of it. This can also be referred to as the _known-unknown_ of the
model [27]. Another characterization of epistemic uncertainty can be
attributed to conditional entropy [28, 29], i.e. the difference of information
contained in the model with respect to the physical system. A model is an
abstracted encoding of a system, hence a mere projection of reality. Due to
the abstraction, not every detail is encoded in the model and thereby
conditional entropy is induced.

We extend the concept of epistemic uncertainty to our universe of point masses
and start with the deterministic model first. This model allows exact
calculation of the motion of the planets. For the idealized point masses the
model is completely accurate and there is no uncertainty in this model.
However, real world scenarios are more complex than point masses. Now consider
the planets with a homogeneous mass distribution are replaced by a
heterogeneous body with an uneven surface. Newton’s laws still hold, but a
model with idealized point masses does not accurately describe the physical
system anymore. The causality in the physical system are not completely
encoded into the formal system model. The lack of knowledge due to the
inaccurate model leads to an epistemic uncertainty. A more accurate model
based on a spatial integral over the attracting forces would allow a more
accurate description and reduce the epistemic uncertainty. However, this would
require complete information of the actual mass distribution, which might not
be available.

Now consider the probabilistic model representation. The probabilistic
distribution of the point masses is an aleatory uncertainty for the given
model. However, the probabilities can usually not be determined exactly. With
a frequentist approach, we calculate the probabilities based on our past
observations. The gap between the actual and observed probabilities represents
the epistemic uncertainty of the probabilistic model. With each new
observation, our distribution parameter (e.g. means and variance for a
Gaussian distribution) become more credible. Hence, our knowledge increases
and the epistemic uncertainty decreases with every observation.

###  III-C Ontological Uncertainty

_Ontological uncertainty can be defined as a condition of complete ignorance
in the model of a relevant aspect of the system._

This can also be referred to as the _unknown-unknown_ [27], the state of we do
not know that we do not know. The term ontological uncertainty is based on
ontology, i.e. is the study of existence. We thereby refer to a lack of
knowledge about the actual existence of relevant aspects in our model
representation.

Again, we use the point mass universe to explain the concept of uncertainty.
We assumed that there are only two planets and our past experience with the
universe also supports this hypothesis. However, at some point we observe a
behavior of the planets that contradicts the prediction by the models due to
the influence of a third planet. This challenges our prior beliefs about the
universe. The probabilistic and deterministic model are completely inaccurate.
The possibility that there are phenomena in the universe which are neglected
by our models is represented by the ontological uncertainty. In order to
formulate a new model that provide the necessary representation of the
universe, we need to reformulate our models to include the influence of the
third point mass.

Previous work only distinguishes between aleatory and epistemic uncertainty
[26]. However, we consider that in the field of highly automated driving
vehicles, a further distinction into ontological uncertainty is valuable, as
they require different means for reduction. The completeness and correctness
of models are generally challenged in the early stages of research and
development of novel systems. For autonomous systems operating in an open
context the ontological uncertainty can never be completely disregarded.
Therefore, it should be included in the safety case that it has been properly
addressed.

Segregating the epistemic and ontological uncertainty in a model can be
challenging, as they constitute of blurred boundaries. A general rule of
thumbs is a distinction between model accuracy (epistemic) and model
correctness (ontological). Subjectively these uncertainties can be
distinguished by the surprise factor when we observe new behavior.
Mathematically the conditional entropy between the system and its model can be
used as a formal expression for the surprise factor [28, 29].

##  IV Means of Uncertainties

In order to develop dependable systems, the impact of aleatory, epistemic and
ontological uncertainties on the overall dependability has to be minimized.
Analogous to the taxonomy for dependability given by Laprie et al. [12, 13],
we use a similar taxonomy for means to cope with uncertainties (Fig. 3).

Figure 3: Uncertainty occurring in system models are classified into aleatory,
epistemic and ontological. To build dependable system in the presence of these
uncertainties the means prevention, tolerance, removal and/or forecasting are
necessary.

In this uncertainty taxonomy, we classify the means into uncertainty
prevention, tolerance, removal and forecasting:

  * •

Uncertainty prevention can e.g. be achieved by avoiding complexity in the
system. This can be done by using simple architectures not prone to emergent
behavior or restriction of the operational design domain (ODD).

  * •

Uncertainty removal can be done during development by e.g. a safety analysis
including epistemic/ontological uncertainty or during use by e.g. field
observation to monitor ontological events.

  * •

Uncertainty tolerance can typically be obtained by using redundant
architectures (e.g. overlapping field of views of sensors) or using components
that can detect uncertainty (e.g. machine learning with epistemic uncertainty
outputs).

  * •

Uncertainty forecasting is based on estimating the present level and future
occurrence of uncertainties. These are relevant to make a decision about the
release of a product by e.g. arguing about a sufficiently low ontological
uncertainty.

This taxonomy can be used to define a strategy to deal with uncertainty on
system and component level. As a general rule of thumb, uncertainty prevention
should be prioritized as this eliminates the need for further measures.
Uncertainty removal should be especially considered in design processes to
identify weaknesses in the architecture. However, due to the open context it
will not be possible to sufficiently reduce uncertainty by only focusing on
prevention and removal. Uncertainty tolerance within the system is required to
cope with unforeseen scenarios.

In order to systematically address the gaps due to uncertainty, we aim to use
the different types to evaluate the capability of various means. Especially
ontological uncertainty is difficult handle and is the main contributor to the
long tail validation challenge of highly automated driving [30, 31]. Methods
like uncertainty tolerance are hardly able to cope with this type, due to the
limit of knowledge that can be incorporated into the implemented system.
Instead, methods like uncertainty removal during use are better suited. To
demonstrate how the different types of uncertainty can be addressed by the
means, we explore uncertainty removal as an example by extending a safety
analysis with uncertainty in the next section.

##  V Uncertainty removal

Safety analysis are an integral part of safety engineering to verify that the
design fulfills desired properties. An established method is the fault tree
analysis (FTA) [32]. In this section, we first give a brief introduction to
FTA. It can be challenging to include epistemic and ontological uncertainties
explicitly within the FTA’s failure model. By using more sophisticated
analysis models, we show that we can include these types of uncertainty.

###  V-A Fault tree analysis

FTA is a graphical model based on a Boolean fault propagation and is used to
identify shortcomings like single point faults in the system. Different
extensions to the basic method have been introduced to deal with more complex
aspects of analysis [33, 34]. As a deductive analysis tool, FTA starts with
identifying undesirable top events. This top down process is continued until
root causes (basic events) are identified which cannot be further decomposed.
The propagation of basic events to the undesired top event is modeled by
Boolean gates.

While FTA is quite popular and in widespread uses, it also has some
shortcomings. For autonomous systems, the failure oriented nature of FTA
limits the ability to include human factors or nominal performance of the
system. Further, the cause and effect relationship between events is
deterministic, which cannot model more diverse and uncertain relations in the
systems. Advances to model this probabilistically in FTA models have been made
[35]. However, these still contain several limitations to be able to model
more generalized dependencies and uncertain relationships which are
encountered in complex systems.

###  V-B Safety analysis with uncertainty

In order to deal with the shortcomings of FTA regarding the different types of
uncertainty we propose an analysis method based on evidence theory [36] in
combination with Bayesian networks (BN) [8]. Evidence theory incorporates the
different types of uncertainty and the Bayesian network representation allows
to use a graphical model that supports in construction of the mental model by
the developers.

The BN is a Directed Acyclic Graph (DAG) that consists of nodes and edges.
Every node is a random variable, which represents an element of the system or
its context. The edges represent a directed causal relationship between two
nodes. The edge direction runs from the parent node (pa) towards the child
node (ch). Together, node and edge represent the structure of the
probabilistic network. The effect of parent node on child node is determined
by conditional probabilities $P(pa|ch)$. In the following, we demonstrate how
all three types of uncertainties can be modeled in a BN with a simple example.

Consider we want to develop a perception chain consisting of a camera with a
machine learning algorithm that classifies objects. When developing this
system we assume that only cars or pedestrians will be encountered, and hence
only these will be included in the model used by the perception chain.
However, we also believe in the possibility of existence of other objects that
will be encountered in the real world and include an unknown object state in
our root node (Fig. 4). This unknown object state of the ground truth
represents the ontological uncertainty in our analysis. The probabilities
$P_{car}=0,6$, $P_{ped}=0,3$, $P_{unknown}=0,1$ represent how likely we will
encounter these objects in the real world. This probabilistic distribution
represents the aleatory uncertainty of our world model.

At the end of the perception chain, we classify the encountered objects to
car, pedestrian or none. We also include a state about car/pedestrian. This
state is not an actual output of the classifier. It represents our epistemic
uncertainty in assessing the performance of the perception chain to correctly
classify the objects. The conditional probability table (CPT, Tab. I) of the
perception node in the BN encodes this epistemic uncertainty by the
corresponding probabilities in the car/pedestrian column.

Figure 4: Bayesian Network of an object perception chain. The ground truth node represents the actual object and the perception node the classified object as output. TABLE I: Conditional probability table (CPT) of $P(perception|groundtruth)$. Epistemic uncertainty about the performance of the classification is encoded in the probabilities of the state car/pedestrian. Ontological uncertainty about the possibility of further objects is included in the unknown state of the ground truth. | Perception
---|---
Ground Truth | car | pedestrian | car/pedestrian | none
car | 0.9 | 0.005 | 0.05 | 0.045
pedestrian | 0.005 | 0.9 | 0.05 | 0.045
unknown | 0 | 0 | 0.2 | 0.7

The advantage of the BN approach is that it can be scaled up to model the
complete system and allows hierarchical refinement analogous to FTA. For each
node and CPT the corresponding aleatory, epistemic and ontological uncertainty
can be included as required. However, the number of parameters that need to be
elicited in the CPT grows exponentially with the number of parent nodes and
their states. Using BN for larger systems, hence, can become cumbersome.
However, several techniques to deal with this problem are available [37, 38,
39].

In this example, we have shown a clear distinction between epistemic
uncertainty (decision between existing states) and ontological uncertainty
(objects not included in the perception model). This distinction is essential
for uncertainty removal, as it allows identification of fitting measures. The
epistemic uncertainty can be reduced by further observation and refinement of
the existing perception models (i.e. increase of our knowledge about the
perception chain performance). In contrast, the ontological uncertainty
requires a more thorough domain analysis and extension of the perception
model.

With this kind of analysis, it can also be demonstrated that redundant
architectures with diverse uncertainties can be used to build uncertainty
tolerant systems. The BN approach also allows including dependencies by common
parent nodes to identify common causes for uncertainties.

##  VI Conclusion and outlook

We presented a system theoretic viewpoint of uncertainty and derived a
distinction between aleatory, epistemic and ontological types. Due to the
different nature of these types, they have to be addressed by fitting methods.
In order to provide a framework to define an overall strategy for methods
suited to deal with these uncertainties, we classify the means into
prevention, removal, tolerance and forecasting. As an example for applying the
types of uncertainty, we have shown a safety analysis method by using a
Bayesian network approach with evidence theory which can be used for
uncertainty removal.

We intend to apply this system-theoretic viewpoint to all steps of development
process and use it as guidance to decide which means are best suited to handle
the three types of uncertainty. Thereby, we want to build a safety argument
that uncertainties are properly managed and do not pose an unacceptable level
of risk.

## References

  * [1] S. Burton, I. Habli, T. Lawton, J. McDermid, P. Morgan, and Z. Porter, “Mind the gaps: Assuring the safety of autonomous systems from an engineering, ethical, and legal perspective,” _Artificial Intelligence_ , p. 103201, 2019\.
  * [2] International Organization for Standardization, “ISO26262: Road vehicles - Functional safety,” 2018.
  * [3] A. Poddey, T. Brade, J. E. Stellet, and W. Branz, “On the validation of complex systems operating in open contexts,” _arXiv preprint arXiv:1902.10517_ , 2019.
  * [4] International Organization for Standardization, “ISO/PAS21448: Road vehicles - Safety of the intended functionality,” 2019.
  * [5] Y. Gal and Z. Ghahramani, “Dropout as a bayesian approximation: Representing model uncertainty in deep learning,” in _International conference on machine learning_ , 2016, pp. 1050–1059.
  * [6] A. Kendall and Y. Gal, “What uncertainties do we need in bayesian deep learning for computer vision?” in _Advances in neural information processing systems_ , 2017, pp. 5574–5584.
  * [7] K. Simonyan, A. Vedaldi, and A. Zisserman, “Deep inside convolutional networks: Visualising image classification models and saliency maps,” _arXiv preprint arXiv:1312.6034_ , 2013.
  * [8] C. Simon, P. Weber, and A. Evsukoff, “Bayesian networks inference algorithm to implement Dempster Shafer theory in reliability analysis,” _Reliability Engineering & System Safety_, vol. 93, no. 7, pp. 950–963, 2008.
  * [9] D. Sadigh and A. Kapoor, “Safe control under uncertainty with probabilistic signal temporal logic,” 2016.
  * [10] P. Koopman, B. Osyk, and J. Weast, “Autonomous vehicles meet the physical world: Rss, variability, uncertainty, and proving safety,” in _International Conference on Computer Safety, Reliability, and Security_. Springer, 2019, pp. 245–253.
  * [11] R. Wang, J. Guiochet, G. Motet, and W. Schön, “DS theory for argument confidence assessment,” in _International Conference on Belief Functions_. Springer, 2016, pp. 190–200.
  * [12] J.-C. Laprie, “Dependability: Basic concepts and terminology,” in _Dependability: Basic Concepts and Terminology_. Springer, 1992, pp. 3–245.
  * [13] A. Avizienis, J.-C. Laprie, B. Randell, and C. Landwehr, “Basic concepts and taxonomy of dependable and secure computing,” _IEEE transactions on dependable and secure computing_ , vol. 1, no. 1, pp. 11–33, 2004.
  * [14] J. Rasmussen, A. M. Pejtersen, and L. P. Goodstein, “Cognitive systems engineering,” 1994.
  * [15] N. Leveson, “A new accident model for engineering safer systems,” _Safety science_ , vol. 42, no. 4, pp. 237–270, 2004.
  * [16] A. S. Reber, “Implicit learning and tacit knowledge.” _Journal of experimental psychology: General_ , vol. 118, no. 3, p. 219, 1989.
  * [17] W. R. Ashby, “An introduction to cybernetics,” 1957.
  * [18] R. C. Conant and W. Ross Ashby, “Every good regulator of a system must be a model of that system,” _International journal of systems science_ , vol. 1, no. 2, pp. 89–97, 1970.
  * [19] R. Rosen, _Life itself: a comprehensive inquiry into the nature, origin, and fabrication of life_. Columbia University Press, 1991.
  * [20] P.-S. Laplace, _Pierre-Simon Laplace Philosophical Essay on Probabilities: Translated from the fifth French edition of 1825 With Notes by the Translator_. Springer Science & Business Media, 1998, vol. 13.
  * [21] J. Earman _et al._ , _A primer on determinism_. Springer Science & Business Media, 1986, vol. 37.
  * [22] D. Hastings and H. McManus, “A framework for understanding uncertainty and its mitigation and exploitation in complex systems,” in _2004 Engineering Systems Symposium_ , 2004, pp. 29–31.
  * [23] P. Walley, _Statistical reasoning with imprecise probabilities_. London New York: Chapman and Hall, 1991.
  * [24] J. Clarkson and C. Eckert, _Design process improvement: a review of current practice_. Springer Science & Business Media, 2010.
  * [25] O. De Weck, C. M. Eckert, P. J. Clarkson _et al._ , “A classification of uncertainty for early product and system design,” in _DS 42: Proceedings of ICED 2007, the 16th International Conference on Engineering Design, Paris, France, 28.-31.07. 2007_ , 2007, pp. 159–160.
  * [26] A. Der Kiureghian and O. Ditlevsen, “Aleatory or epistemic? does it matter?” _Structural Safety_ , vol. 31, no. 2, pp. 105–112, 2009.
  * [27] N. N. Taleb, _The black swan: The impact of the highly improbable_. Random house, 2007, vol. 2.
  * [28] C. E. Shannon, “A mathematical theory of communication,” _Bell system technical journal_ , vol. 27, no. 3, pp. 379–423, 1948.
  * [29] F. Heylighen and C. Joslyn, “Cybernetics and second-order cybernetics,” _Encyclopedia of physical science & technology_, vol. 4, pp. 155–170, 2001\.
  * [30] “Autonomous Vehicles vs. Kangaroos: the Long Furry Tail of Unlikely Events,” https://spectrum.ieee.org/cars-that-think/transportation/self-driving/autonomous-cars-vs-kangaroos-the-long-furry-tail-of-unlikely-events, accessed: 2019-11-28.
  * [31] P. Koopman, “The heavy tail safety ceiling,” in _Automated and Connected Vehicle Systems Testing Symposium_ , 2018.
  * [32] H. Barringer, “An overview of reliability engineering principles,” 11 1996.
  * [33] J. B. Dugan, S. J. Bavuso, and M. A. Boyd, “Dynamic fault-tree models for fault-tolerant computer systems,” _IEEE Transactions on reliability_ , vol. 41, no. 3, pp. 363–377, 1992.
  * [34] H. Tanaka, L. T. Fan, F. S. Lai, and K. Toguchi, “Fault-tree analysis by fuzzy probability,” _IEEE Transactions on Reliability_ , vol. R-32, no. 5, pp. 453–457, Dec 1983.
  * [35] R. Ferdous, F. Khan, R. Sadiq, P. Amyotte, and B. Veitch, “Fault and event tree analyses for process systems risk analysis: uncertainty handling formulations,” _Risk Analysis: An International Journal_ , vol. 31, no. 1, pp. 86–107, 2011.
  * [36] G. Shafer, _A mathematical theory of evidence_. Princeton university press, 1976, vol. 42.
  * [37] N. E. Fenton, M. Neil, and J. G. Caballero, “Using ranked nodes to model qualitative judgments in bayesian networks,” _IEEE Transactions on Knowledge and Data Engineering_ , vol. 19, no. 10, pp. 1420–1432, 2007.
  * [38] K.-S. Chin, D.-W. Tang, J.-B. Yang, S. Y. Wong, and H. Wang, “Assessing new product development project risk by bayesian network with a systematic probability generation methodology,” _Expert Systems with Applications_ , vol. 36, no. 6, pp. 9879–9890, 2009.
  * [39] E. Mendes, P. Rodriguez, V. Freitas, S. Baker, and M. A. Atoui, “Towards improving decision making and estimating the value of decisions in value-based software engineering: the value framework,” _Software Quality Journal_ , vol. 26, no. 2, pp. 607–656, 2018.


# Joint Power Control, Channel Assignment and Cell Association in
Heterogeneous Cellular Networks

Shahla Mohsenifard, Ahmad R. Sharafat, , and Halim Yanikomeroglu S.
Mohsenifard and A. R. Sharafat are with the Faculty of ECE, Tarbiat Modares
University, Tehran, Iran. H. Yanikomeroglu is with the Department of SCE,
Carleton University, Ottawa, Ontario, Canada. Corresponding author is A. R.
Sharafat (email: sharafat@ieee.org).

###### Abstract

Heterogeneous network (HetNet) is a promising concept for increasing capacity
and alleviating spectrum scarcity. In HetNets, however, channel assignment and
transmit power control affect the distribution of users among base stations.
We present a novel scheme to maximize the uplink sum rate in two-tier HetNets
with one macrocell and several femtocells, where the transmit power of each
user is bounded and at least one channel is assigned to each user. We divide
the problem into two sub-problems: one for channel assignment and one for
transmit power control, and solve them by iteratively alternating between the
two. Our scheme is convergent, and yields a transmission rate above 6 bps/Hz
for almost 50% of users as compared to the same for 10% of users in SINR-based
schemes. When users are in cell boundaries, the average transmission rate for
fractional frequency reuse is up to 20% more compared to the conventional full
frequency reuse. This is due to reduced transmit power resulting in less
interference.

###### Index Terms:

Heterogeneous networks (HetNets), channel assignment, transmit power control,
frequency reuse.

##  I Introduction

The phenomenal growth in mobile data calls for innovative approaches for more
efficient use of the limited resources. Heterogeneous networks (HetNets)
consisting of high-power macro base-stations (BSs) and low-power small BSs,
including microcells, relays, picocells and femtocells, is a promising concept
for enhancing frequency reuse and reducing transmit power levels. In this
paradigm, users receive higher signal levels from macro BSs as compared to
small BSs, and SINR levels in the downlink (DL) and uplink (UL) are not the
same (asymmetric SINR). As such, BS association based on highest DL SINR, as
in macro-cell only networks is not suitable for HetNets. In HetNets, there is
a need to balance the load among different cells and reduce intercell
interference, which can be achieved by UL transmit power control.

Recent research on cell association and power control is mostly based on
downlink (DL) metrics [1, 2, 3], which may not be optimal for UL due to
asymmetry of metrics in DL and UL [4]. In [4], the long-term average data rate
is maximized and the quality of service (QoS) is maintained for all users
assuming fixed and identical UL transmit power over all channels. In [5], a
joint DL and UL aware cell association in HetNets is proposed, where each BS
has a finite number of resource blocks to distribute among users. In [6], BS
association and channel assignment are jointly considered in both DL and UL in
interference-limited HetNets, where biased BS association is based on highest
SINR in DL, and when bias is identical for all BSs, the nearest BS is
associated to the user.

In [7], SIR and uplink rate distribution are used for load balancing and power
control in HetNets, where cell association is based on path-loss. In [8], the
outage probability in UL in a two-tier CDMA-based network with shared spectrum
is discussed, and a lower bound for the outage in femtocells is derived. Using
stochastic geometry in [9], a simple model for obtaining the outage and
calculating the spectral efficiency in UL in non-heterogeneous networks and
HetNets is proposed. In [9], channel assignment is fixed and channel inversion
is used for power control. In [10], a game-theoretic and distributed joint
channel assignment and power control in HetNets is presented, but inter-cell
interference is ignored.

Energy efficiency in the HetNets’ UL is considered in [11], where fractional
power control is applied by each user to maximize its SINR subject to its
maximum transmit power constraint. In [12], energy efficiency for all users in
a HetNet is maximized, where each user is associated with a BS that satisfies
its SINR with minimum UL transmit power. Considering the above, in this paper
we address joint UL transmit power control, channel assignment and cell
association in two-tier HetNets consisting of conventional macro BSs and femto
BSs to maximize the users’ UL sum rate, where each user should have at least
one channel. This problem is NP-hard, with no closed form solution. We divide
the problem into two sub-problems: one for power control and one for sub-
channel assignment and cell association; and iteratively alternate between the
two until convergence.

The rest of this paper is organized as follows. In Section II, the system
model is described. In Section III, the problem is formulated and divided into
two sub-problems, followed by a description of our proposed algorithm. Section
IV contains simulation results, and conclusions are in Section V.

##  II System Model

Consider a HetNet with a total of $M$ BSs consisting of one macro BS and $M-1$
femto BSs, $N$ users uniformly distributed in the entire coverage area, and
$K$ sub-channels in each BS. In this network, two schemes for frequency reuse
is possible: full reuse, and fractional reuse. In the former, all sub-channels
are used in all BSs; and in the latter, some sub-channels are exlusively used
by femto BSs, and the rest can be used by either the macro BS or femto BSs.
The maximum transmit power for user $i$ is $p_{i}^{\mathrm{max}}$, and
$p_{i,j,k}$ is the transmit power of user $i$ to BS $j$ on sub-channel $k$.

The gain in sub-channel $k$ between user $i$ and BS $j$ is

$h_{i,j,k}=g_{i,j,k}f_{i,j,k},\;\,1\leq i\leq N,\;1\leq j\leq M,\;1\leq k\leq
K$ (1)

where $g_{i,j,k}=L(d_{i,j})+S$ is the impact of large scale slow fading for
each sub-channel between user $i$ and BS $j$, and $f_{i,j,k}$ is the impact of
small scale fast fading. Path loss between user $i$ and its BS $j$ is
$L(d_{i,j})=L^{\mathrm{fixed}}+10\alpha\log(d_{i,j})$, where
$L^{\mathrm{fixed}}$ is the fixed path-loss and $d_{i,j}$ is the distance
between user $i$ and BS $j$. Shadowing is denoted by $S$ and is a lognormal
random variable with zero mean and $\sigma_{\text{S}}$ standard deviation. The
small scale fast fading $f_{i,j,k}$ is a Rayleigh distributed random variable
with zero mean and unit variance for all $i,j,k$. Considering the above, sub-
channel gain $h_{i,j,k}$ is an exponentially distributed random variable [5]
with parameter $\lambda_{i,j,k}$, where

$\lambda_{i,j,k}=\frac{1}{E[h_{i,j,k}]}=\frac{1}{g_{i,j,k}}.$ (2)

The SINR in BS $j$ from user $i$ on sub-channel $k$ is

$\gamma_{i,j,k}=\frac{p_{i,j,k}h_{i,j,k}}{\sum_{l=1\setminus{i}}^{N}\sum_{s=1\setminus{j}}^{M}p_{l,s,k}h_{l,j,k}+\Delta
fN_{0}},$ (3)

where $N_{0}$ is the noise power, $\Delta f$ is the sub-channel bandwidth,
$1\setminus{i}$ means all users except user $i$, $1\setminus{j}$ means all BSs
except BS $j$, and
$\sum_{l=1\setminus{i}}^{N}\sum_{s=1\setminus{j}}^{M}p_{l,s,k}h_{l,j,k}$ is
the interference on sub-channel $k$ in BS $j$ from all users in other BSs
transmitting on the same sub-channel $k$. As in [13], we also assume users can
associate with more than one BS.

##  III Problem Formulation

We consider the users’ sum rate as the utility function, and obtain the binary
matrix X and transmit power $p_{i,j,k}$ for utility maximization. The entries
$x_{i,j,k}$ of matrix X denote association of user $i$ on sub-channel $k$ to
BS $j$. The optimization problem is

$\begin{array}[]{rlllll}\displaystyle{\max_{\bf{X,P}}}&\lx@intercol\sum_{i=1}^{N}\sum_{j=1}^{M}\sum_{k=1}^{K}x_{i,j,k}\log(1+\gamma_{i,j,k})\hfil\lx@intercol,\\\
\end{array}$ (4) $\displaystyle\textrm{Subject
to}\left\\{\begin{array}[]{c}\textrm{C1:}\,\sum_{j=1}^{M}\sum_{k=1}^{K}x_{i,j,k}p_{i,j,k}\leq
p_{i}^{\text{max}},\qquad\forall i\vspace{0.05 in}\\\
\textrm{C2:}\,\sum_{i=1}^{N}x_{i,j,k}\leq 1,\qquad\qquad\qquad\qquad\,\forall
j,k\vspace{0.05 in}\\\ \textrm{C3:}\;x_{i,j,k}\in\\{0,1\\},\end{array}\right.$
(8)

where $\gamma_{i,j,k}$ is as in (3). Similar to the transmit power matrix P,
the matrix X is of dimensions $N\times M\times K$. The constraint C1 indicates
that the sum of transmit power levels by user $i$ on all its sub-channels
cannot exceed $p_{i}^{\mathrm{max}}$. The constraint C2 implies that each sub-
channel in BS $j$ is used by only one user; and the constraint C3 indicates
that assignment of sub-channel $k$ to user $i$ in BS $j$ is binary. Users can
be associated with more than one BS at any given time.

This is a mixed integer and combinatorial NP-hard problem. To remedy its
complexity, we divide it into two sub-problems: one for transmit power
allocation to each user on different sub-channels, and one for sub-channnel
assignment and BS association to each user. The two sub-problems are solved in
sequence in each iteration until final convergence.

###  III-A Transmit Power Allocation

We begin by setting all entries in the binary association matrix X to 1 and
proceed to obtain the transmit power $p_{i,j,k}$ for all values of $i,j,k$.
The power allocation problem is

$\begin{array}[]{rlllll}\displaystyle{\max_{\bf{P}}}&\lx@intercol\sum_{i=1}^{N}\sum_{j=1}^{M}\sum_{k=1}^{K}x_{i,j,k}\log(1+\gamma_{i,j,k})\hfil\lx@intercol,\\\
\end{array}$ (9)

Subject to C1.
This problem obtains each user’s transmit power on its sub-channels to
maximize the network’s sum-rate for all $x_{i,j,k}$. The water-filling
algorithm solves this problem by increasing the transmit power on those sub-
channels that experience less interference (see Appendix I), which maximizes
the sum rate in the network. However, when multiple users are on one sub-
channel, interference is caused. To mitigate this, after convergence of
transmit power in each iteration, we apply the below scheme for sub-channel
assignment and repeat this cycle until only one sub-channel is assigned to
each user.

###  III-B Sub-Channel Assignment

To satisfy C2, after transmit power convergence in each iteration, assignment
of sub-channels in X is pruned by removing a user from subchannels in each
iteration until finally one user remains on each sub-channel. To maximize the
sum rate, the below criteria is checked for all users in each iteration:

$\delta(k^{\prime})=\sum_{i=1}^{N}\sum_{j=1}^{M}\sum_{k=1}^{K}{r_{2}}_{i,j,k}(k^{\prime})-\sum_{i=1}^{N}\sum_{j=1}^{M}\sum_{k=1}^{K}{r_{1}}_{i,j,k}(k^{\prime}),$
(10)

where ${r_{1}}_{i,j,k}(k^{\prime})$ and ${r_{2}}_{i,j,k}(k^{\prime})$ are the
rates of user $i$ on sub-channel $k$ in base station $j$ before and after
removing a user from sub-channel $k^{\prime}$, respectively, and
$\delta(k^{\prime})$ is the increase in the users’ sum rate caused by removal
of a user from sub-channel $k^{\prime}$. The user with the highest
$\delta(k^{\prime})$ is removed from sub-channel $k^{\prime}$ unless only one
sub-channel is assigned to that user. In this case, the user with the second
highest $\delta(k^{\prime})$ is removed. This implies that each user can
transmit on at least one sub-channel.

Algorithm 1 Joint Uplink Resource Allocation in HetNets

1:Initialize: Set ${\bf{X}}={\bf{1}}$ and $p_{i,j,k}=p^{\mathrm{max}}/(M\times
K)$.

2:repeat

3: for each base station $j=1$ to $M$

4: repeat

5: for each sub-channel $k^{\prime}=1$ to $K$

6: while more than one user is on sub-channel $k^{\prime}$ do

7: Calculate $\delta(k^{\prime})$ in (6) for all users on sub-channel

$k^{\prime}$, and choose the user with the highest $\delta(k^{\prime})$

8: if that user has another sub-channel then

9: remove it from sub-channel $k^{\prime}$

10: else

11: remove the user with the next highest $\delta(k^{\prime})$ who has more
than one sub-channel from sub-channel $k^{\prime}$

12: repeat

13: update the transmit power for all users via (5)

14: until P converges

15: until $k^{\prime}=K$

16:until $j=M$

##  IV Numerical Results and Discussion

A two-tier HetNet consisting of 1 macro BS, 4 femto BSs, and 25 users
uniformly distributed in a 1000 m $\times$ 1000 m cell is considered. Without
loss of generality the macro BS is placed at (0,0). There are 20 sub-channels
in each BS, but the macro BS only uses some (not all) sub-channels in the
fractional frequency reuse scheme. Since LTE sub-channels are 180 kHz wide,
thermal noise power is set to -111.45 dBm. The maximum transmit power of each
user is set to 20 dBm. The large scale path loss between each user and the
macro BS is $L(d)$ = 34 + 40 log($d$), where $d$ is the distance in meters.
The large scale path loss between each user and a femto BS is $L(d)$ = 37 + 30
log$(d)$. Besides, shadowing is modeled by a lognormal random variable with 8
dB standard deviation, and Rayleigh small scale fading is modeled by an
exponentially distributed random variable with zero mean and unit variance as
in [5]. Simulation parameter values are as in Table I.

Figs. 1 and 2 show the initial and final association of users to BSs,
respectively. Note that the final association is more balanced, and that some
users connect to more than one BS. Fig. 3 shows the convergence of our
proposed algorithm. Each horizontal segment shows transmit power convergence
in each iteration. When a user is removed from a sub-channel, the power is
updated until convergence. The algorithm ends when there is no sub-channel
with more than one user.

Fig. 4 shows the cumulative distribution function (CDF) for the sum-rate in
different schemes. In the max SINR association, sub-channels are equally
distributed among users, and users transmit with equal power. Note that our
scheme yields a transmission rate above 6 bps/Hz for almost 50% of users as
compared to 10% of users in SINR-based schemes. Since our scheme applies
transmit power control, it outperforms the algorithm in [5] in which power
control is not applied. Also, as can be seen in the same figure, the outage
probability for $\gamma_{\text{th}}=0.6$ bps/Hz for the max SINR algorithm,
for the method in [12], for the method in [5], and for our scheme is 42%, 25%,
10%, and 7%, respectively.

Fig. 5 shows the number of sub-channels assigned to each user with and without
applying fairness (i.e., at least one sub-channe for each user), respectively.
By increasing the number of users but without providing all users with at
least one sub-channel, the sum rate is increased as in Fig. 6(6(a)). This is
because the probability of users with better channel increases. However, when
all users are assigned at least one sub-channel, as can be seen in Fig.
6(6(b)), increasing the number of users increases the sum-rate up to a point,
after which the sum-rate is reduced. This is because fairness implies that in
some cases a sub-channel is assigned to a user with a smaller gain.

Table I: Simulation Parameters

Parameter | Description | Value
---|---|---
$N_{0}$ | Noise power | -111.45 dBm
$\sigma^{2}_{s}$ | Shadow fading variance | 8 dB
$M$ | Number of BSs | 5
$N$ | Number of users | 25
$K$ | Number of sub-channels | 20
$p_{i}^{\mathrm{max}}$ | Fixed power consumption in each BS | 20 dBm
$\Delta f$ | Sub-channel bandwidth | 180 KHz
$L^{\mathrm{fixed}}$ | Fixed path loss for macro/femto users | 34/37 dB
$\alpha$ | Path loss exponent for macro/femto users | 4/3

Figure 1: Initial user association. Figure 2: Final user association. Figure
3: Convergence of our proposed algorithm.

To study the impact of frequency reuse on the sum rate, we consider two cases.
When many users are near the macro BS, making more sub-channels available to
the macro BS increases the sum-rate, as in Fig. 7(7(a)). In this case, full
frequency reuse is better due to low interference. When many users are near
femto BSs (indoor users), making more sub-channels available to the macro BS
reduces the sum rate as in Fig. 7(7(b)) due to interference caused by macro BS
users on femto BS users. In this case, fractional frequency reuse should be
applied.

Figure 4: Rate CDF for the max-SINR association scheme, the algorithm in [5]
and our proposed algorithm. Figure 5: Sub-channel assignment with and without
fairness.

##  V Conclusion

We proposed an algorithm for joint power control, sub-channel assignment, and
BS association in the UL of two-tier HetNets when users’ transmit power is
bounded. The formulated optimization problem for maximizing the users’ sum-
rate is NP-hard with no closed form solution. We proposed to obtain sub-
optimal solutions via our iterative algorithm, whose sum-rate is higher than
those of the max SINR association and the algorithms in [5] and [12]. We
showed that when a degree of fairness is applied by providing each user with
at least one sub-channel, increasing the number of users increases the sum-
rate up to a point, after which the sum rate is reduced. We also showed that
when users are located near the femto BS, fractional frequency reuse is better
than full frequency reuse.

(a)

(b)

Figure 6: Sum rate: (a) some users do not have at least one sub-channel
(fairness), (b) each user has at least one sub-channel.

(a)

(b)

Figure 7: Average sum rate vs the number of macro BS sub-channels: (a) users
are near BS, (b) users are far from BS

##  Appendix A Same Level Power Allocation

The power allocation problem is

$\begin{array}[]{rlllll}\displaystyle{\max_{\bf{P}}}&\lx@intercol\sum_{i=1}^{N}\sum_{j=1}^{M}\sum_{k=1}^{K}x_{i,j,k}\log(1+\gamma_{i,j,k})\hfil\lx@intercol,\\\
\end{array}$ (11)

Subject to $\sum_{j=1}^{M}\sum_{k=1}^{K}p_{i,j,k}\leq
p_{i}^{\text{max}},\>\>\>\>\forall i$.
Assume $n$ sub-channels are assigned to user $i$ where interference plus noise
on any sub-channel $k$ of user $i$ is $\xi_{k}$. We wish to distribute the
transmit power of user $i$, denoted by $p_{i}^{\text{max}}$, to its sub-
channels. This problem is formulated as

$\begin{array}[]{rlllll}\displaystyle{\max_{\bf{p}\geq
0}}&\lx@intercol\sum_{k=1}^{K}\log(1+\frac{p_{k}}{\xi_{k}})\hfil\lx@intercol,\\\
\end{array}$ (12) $\displaystyle\textrm{Subject
to}\left\\{\begin{array}[]{c}\\!\sum_{k=1}^{K}p_{k}=p_{i}^{\text{max}}\qquad\\!\\!\\!\\!\\!\forall
i,\\\ p_{k}\geq 0\qquad\qquad\quad\,\forall k,\end{array}\right.$ (15)

where $\bf{p}$ is the transmit power vector whose elements are $p_{k}$.

Instead of solving (12), we solve its Lagrangian dual problem with
$\lambda^{*}$ for the non equality constraint and $v^{*}$ for the equality
constraint. We obtain the KKT conditions

$\textbf{p}^{*}\geq\textbf{0},\qquad{\bf
1}^{\text{T}}\textbf{p}^{*}=p^{\mathrm{max}},$ (16a) $\lambda^{*}\geq
0,\qquad\lambda^{*}_{k}p_{k}^{*}=0,\quad k=1,\cdots,K,$ (16b)
$-1/(1+\frac{p_{k}^{*}}{\xi_{k}})-\lambda_{k}^{*}+v^{*}=0,\quad k=1,\cdots,K.$
(16c)

Therefore,

$\textbf{p}^{*}\geq\textbf{0},\qquad{\bf
1}^{\text{T}}\textbf{p}^{*}=p^{\mathrm{max}},$ (17a)
$p_{k}^{*}[v^{*}-1/(1+\frac{p_{k}^{*}}{\xi_{k}})]=0,\qquad k=1,\cdots,K,$
(17b) $v^{*}\geq 1/(1+\frac{p_{k}^{*}}{\xi_{k}}).$ (17c)

When $v^{*}<1$, (17c) is satisfied only when $p_{k}^{*}>0$. Hence, from (17b),
we write

$v^{*}=1/(1+\frac{p_{k}^{*}}{\xi_{k}}).$ (18)

Solving (18) for $p_{k}^{*}$, we get $p_{k}^{*}=\xi_{k}/v^{*}-\xi_{k}$ when
$v^{*}<1$, and $p_{k}^{*}=0$ when $v^{*}>1$, i.e.,

$p_{k}^{*}=\mathrm{max}(0,\xi_{k}/v^{*}-\xi_{k}).$ (19)

By using (19) in (16a), we get

$\sum_{k=1}^{K}\mathrm{max}(0,1/v^{*}-\xi_{k})=p^{\mathrm{max}}.$ (20)

The value of $1/v^{*}$ is the power level in the water filling algorithm, and
forces the sum of transmit power levels in all sub-channels for each user to
be $p^{\mathrm{max}}$[14].

## References

  * [1] T. Zhou, Z. Liu, J. Zhao, C. Li, and L. Yang, “Joint user association and power control for load balancing in downlink heterogeneous cellular networks,” IEEE Transactions on Vehicular Technology, vol. 67, no. 3, pp. 2582–2593, March 2018.
  * [2] Q. Ye, M. Al-Shalash, C. Caramanis, and J.G. Andrews, “Downlink energy efficiency of power allocation and wireless backhaul bandwidth allocation in heterogeneous small cell networks,” IEEE Transactions on Communications, vol. 66, no. 4, pp. 1705–1716, April 2018.
  * [3] S. Singh and J.G. Andrews, “Joint resource partitioning and offloading in heterogeneous cellular Networks,” IEEE Transactions on Wireless Communications, vol. 13, no. 2, pp. 888–901, February 2014.
  * [4] J.G. Andrews, S. Singh, Y. Qiaoyang, L. Xingqin, and H. Dhillon, “An overview of load balancing in HetNets: Old myths and open problems,” IEEE Wireless Communications, vol. 21, no. 2, pp. 18–25, April 2014.
  * [5] H. Boostanimehr and V.K. Bhargava, “Joint downlink and uplink aware cell association in HetNets with QoS provisioning,” IEEE Transactions on Wireless Communications, vol. 14, no. 10, pp. 5388–5401, October 2015.
  * [6] Y. Lin, W. Bao, W. Yu, and B. Liang, “Optimizing user association and spectrum allocation in HetNets: A utility perspective,” IEEE Journal on Selected Areas in Communications, vol. 33, no. 6, pp. 1025–1039, June 2015.
  * [7] S. Singh, X. Zhang, and J.G. Andrews, “Uplink rate distribution in heterogeneous cellular networks with power control and load balancing,” IEEE International Conference on Communication Workshop (ICCW), pp. 1275-1280, June 2015.
  * [8] V. Chandrasekhar and J.G. Andrews, ”Uplink capacity and interference avoidance for two-tier femtocell Networks,” IEEE Transactions on Wireless Communications, vol. 8, no. 7, pp. 3498–3509, July 2009.
  * [9] H. ElSawy and E. Hossain, “On stochastic geometry modeling of cellular uplink transmission with truncated channel inversion power control,” IEEE Transactions on Wireless Communications, vol. 13, no. 8, pp. 4454–4469, August 2014.
  * [10] H. Mingyi, A. Garcia, J. Barrera, and S.G. Wilson, “Joint access point selection and power allocation for uplink wireless networks,” IEEE Transactions on Signal Processing, vol. 61, no. 13, pp. 3334–3347, July 2013.
  * [11] J. Zhang, L. Xiang, D.W.K. Ng, M. Jo, and M. Chen, “Energy efficiency evaluation of multi-tier cellular uplink transmission under maximum power constraint,” IEEE Transactions on Wireless Communications, vol. 16, no. 11, pp. 7092–7107, November 2017.
  * [12] H. Ding, H. Zhang, J. Tian, S. Xu, and D. Yuan, “Energy efficient user association and power control for dense heterogeneous networks,” 2018 International Conference on Computing, Networking and Communications (ICNC), Maui, HI, 2018, pp. 741-746.
  * [13] 3GPP Work Items on Small Cells, v0.0.4, 3GPP TS 23.251 Release 12, Technical Specification, 3rd Generation Partnership Project (3GPP), June 2014.
  * [14] S.P. Boyd and L. Vandenberghe, Convex Optimization. Cambridge University Press, 2004.


In this case, the validators in $Q$ reply as if they are honest validators and have not received any messages from those in $P$ over the network.

As $|Q| = \lfloor n/2 \rfloor \leq \fL$, by the $\fL$-liveness of $\PI$, clients $\client_1$ and $\client_2$ both output $\tx^P_i$ for all $i \in [\lceil n/2 \rceil]$ as part of their chains by slot $\Tconfirm$.
Since there can be at most $m\lfloor n/2 \rfloor-1$ bits of data on $I$, and $\tx^Q_j$, $j \in [\lfloor n/2 \rfloor]$, consists of $m\lfloor n/2 \rfloor$ bits in total, $\client_1$ does not learn and cannot output all of $\tx^Q_j$, $j \in [\lfloor n/2 \rfloor]$, as part of its chain by slot $\Tconfirm$ with overwhelming probability.

World 2:
There are again two clients $\client_1$ and $\client_2$.
Validators in $P$ are adversarial, and those in $Q$ are honest.
In their heads, the adversarial validators simulate the execution of the $\lceil n/2 \rceil$ honest validators from world 1 and pretend as if they do not receive any messages from those in $Q$ over the network.
They also do not send any messages to $Q$ and $\client_1$, but reply to $\client_2$.
They send the same messages to $I$ as those sent by the honest validators within world 1.

As $|P| = \lceil n/2 \rceil \leq \fL$, by the $\fL$-liveness of $\PI$, clients $\client_1$ and $\client_2$ both output $\tx^Q_j$, $j \in [\lfloor n/2 \rfloor]$, as part of their chains by slot $\Tconfirm$.
Since there can be at most $m\lfloor n/2 \rfloor-1$ bits of data on $I$, and $\tx^P_i$, $i \in [\lceil n/2 \rceil]$, consists of $m\lceil n/2 \rceil$ bits in total, $\client_1$ does not learn and cannot output all of $\tx^P_i$, $i \in [\lceil n/2 \rceil]$, as part of its chain by slot $\Tconfirm$ with overwhelming probability

The worlds 1 and 2 are indistinguishable by $\client_2$ in terms of the messages received from the validators and observed on the timestamping service, except with negligible probability.
Thus, it outputs the same chain containing $\tx^P_i$, $i \in [\lceil n/2 \rceil]$, and $\tx^Q_j$, $j \in [\lfloor n/2 \rfloor]$, in both worlds with overwhelming probability.
However, $\client_1$'s chain contains $\tx^P_i$, $i \in [\lceil n/2 \rceil]$, but not all of $\tx^Q_j$, $j \in [\lfloor n/2 \rfloor]$, in world 1, and $\tx^Q_j$, $j \in [\lfloor n/2 \rfloor]$, but not all of $\tx^P_i$, $i \in [\lceil n/2 \rceil]$, in world 2.
This implies that there is a safety violation in either world 1 or world 2 or both worlds with non-negligible probability.

Without loss of generality, suppose there is a safety violation in world 2.
In this case, $\client_1$ asks the validators for their transcripts, upon which the adversarial validators in $P$ reply with transcripts that omit the messages received from the set $Q$ over the network.
As $\fS > 0$, by invoking the forensic protocol with the transcripts received, $\client_1$ identifies a non-empty subset $S \subseteq P$ of the adversarial validators, and outputs a proof that the validators in $S$ have violated the protocol $\PI$.
However, in this case, an adversarial validator in world 1 can emulate the behavior of $\client_1$ in world 2, and ask the validators for their transcripts.
It can then invoke the forensic protocol with the transcripts, and output a proof that identifies the same subset $S \subseteq P$ of validators as protocol violators.
Since the two worlds are indistinguishable by $\client_2$ except with negligible probability, upon receiving this proof, it identifies the honest validators in $S \subseteq P$ as protocol violators in world 1 as well, with non-negligible probability, which is a contradiction.
By the same reasoning, if the safety violation happened in world 1, an adversarial validator in world 2 can construct a proof accusing an honest validator in world 2 in $\client_2$'s view with non-negligible probability, again a contradiction.

We next analyze the case $\fL < n/2$.

World 3:
There are two clients, $\client_1$ and $\client_2$.
Validators in $P$ are honest, and those in $Q$ are adversarial.
Adversarial validators behave as described in world 1.
Since there can be at most $m\lfloor n/2 \rfloor-1$ bits of data on $I$, and $\tx^Q_j$, $j \in [\lfloor n/2 \rfloor]$, consists of $m\lfloor n/2 \rfloor$ bits in total, $\client_1$ does not learn and cannot output all of $\tx^Q_j$, $j \in [\lfloor n/2 \rfloor]$, as part of its chain by slot $\Tconfirm$.
As there are at least $\fL$ adversarial validators, either of the following cases can happen:

* $\client_1$ outputs $\tx^P_i$, $i \in [\lceil n/2 \rceil]$, as part of its chain by slot $\Tconfirm$.

* $\client_1$ does not output $\tx^P_i$, $i \in [\lceil n/2 \rceil]$, by slot $\Tconfirm$.

World 4:
There are again two clients, $\client_1$ and $\client_2$.
Validators in $P$ are adversarial, and those in $Q$ are honest.
Adversarial validators behave as described in world 2.
Since there can be at most $m\lfloor n/2 \rfloor-1$ bits of data on $I$, and $\tx^P_i$, $i \in [\lceil n/2 \rceil]$, consists of $m\lceil n/2 \rceil$ bits in total, $\client_1$ does not learn and cannot output all of $\tx^P_i$, $i \in [\lceil n/2 \rceil]$, as part of its chain by slot $\Tconfirm$.
As there are at least $\fL$ adversarial validators, either of the following cases can happen:

* $\client_1$ outputs $\tx^Q_j$, $j \in [\lfloor n/2 \rfloor]$, as part of its chain by slot $\Tconfirm$.

* $\client_1$ does not output $\tx^Q_j$, $j \in [\lfloor n/2 \rfloor]$, by slot $\Tconfirm$.

The worlds 3 and 4 are indistinguishable by $\client_2$ in terms of the messages received from the validators and observed on the timestamping service, except with negligible probability.
Thus, it outputs the same (potentially empty) chain in both worlds by slot $\Tconfirm$ with overwhelming probability.
Suppose $\client_2$ does not output all of $\tx^P_i$, $i \in [\lceil n/2 \rceil]$, as part of its chain by $\Tconfirm$.
As this implies a violation of $\Tconfirm$-liveness in world 3, it asks the validators for their transcripts, upon which the adversarial validators in $Q$ reply with transcripts that omit the messages received from the set $P$ over the network.
As $\fA > 0$, by invoking the forensic protocol with the received transcripts, $\client_1$ identifies a non-empty subset $S \subseteq Q$ of the adversarial validators, and outputs a proof that the validators in $S$ have violated the protocol $\PI$.
However, in this case, an adversarial validator in world 4 can emulate the behavior of $\client_2$ in world 3, and ask the validators for their transcripts.
It can then invoke the forensic protocol with the transcripts, and output a proof that identifies the same subset $S \subseteq Q$ of validators as protocol violators.
Since the two worlds are indistinguishable by $\client_2$ except with negligible probability, upon receiving this proof, it would identify the honest validators in $S \subseteq Q$ as protocol violators in world 4 as well, with non-negligible probability, which is a contradiction.
By the same reasoning, if $\client_2$ does not output all of $\tx^Q_j$, $j \in [\lfloor n/2 \rfloor]$, as part of its chain by slot $\Tconfirm$, the adversary can construct a proof accusing an honest validator in world 3 in $\client_2$'s view with non-negligible probability, again a contradiction.

Next, suppose $\client_1$ does not output all of $\tx^P_i$, $i \in [\lceil n/2 \rceil]$, as part of its chain by slot $\Tconfirm$ in world 3.
As this implies a violation of $\Tconfirm$-liveness in world 3, it asks the validators for their transcripts, upon which the adversarial validators in $Q$ reply with transcripts that omit the messages received from the set $P$ over the network.
As $\fA > 0$, by invoking the forensic protocol with the transcripts received, $\client_1$ identifies a non-empty subset $S \subseteq Q$ of the adversarial validators, and outputs a proof that the validators in $S$ have violated the protocol $\PI$.
However, in this case, an adversarial validator in world 4 can emulate the behavior of $\client_1$ in world 3, and ask the validators for their transcripts.
It can then invoke the forensic protocol with the transcripts, and output a proof that identifies the same subset $S \subseteq Q$ of validators as protocol violators.
Since the two worlds are indistinguishable by $\client_2$ except with negligible probability, upon receiving this proof, it would identify the honest validators in $S \subseteq Q$ as protocol violators in world 4 with non-negligible probability, which is a contradiction.
By the same reasoning, if $\client_1$ does not output $\tx^Q_j$, $j \in [\lfloor n/2 \rfloor]$, as part of its chain by slot $\Tconfirm$, the adversary can construct a proof accusing an honest validator in world 3 in $\client_2$'s view with non-negligible probability, again a contradiction.

Finally, if $\client_1$ outputs $\tx^P_i$, $i \in [\lceil n/2 \rceil]$, and $\tx^Q_j$, $j \in [\lfloor n/2 \rfloor]$, as part of its chain in worlds 3 and 4 respectively, and $\client_2$ outputs both $\tx^P_i$, $i \in [\lceil n/2 \rceil]$, and $\tx^Q_j$, $j \in [\lfloor n/2 \rfloor]$, as part of its chain in both worlds, we reach a contradiction with the statement $f_s>0$ by the same reasoning presented for the worlds 1 and 2.
Consequently, under the given conditions, no permissioned or PoS protocol can provide a positive accountable safety and liveness resilience simultaneously even with access to a timestamping service.