This paper describes the extension of the Artificial DNA (ADNA) towards the abstract ADNA ( A2DNA) and a knowledge base. It also presents and analyzes the determinator that specifies the A2DNA to a hardware specific ADNA using the knowledge base. The ADNA represents a building plan that enables an embedded system to build and organize itself. In its current state the ADNA demands high amounts of knowledge on the target hardware's available sensors already in the design phase. Thus, it becomes rigid and cannot be adapted easily to change in the hardware. The A2DNA solves this problem by describing demands about the required sensors using so called abstract sensors instead of being tied to a specific sensor like the ADNA. The determinator then specifies the A2DNA at the build and initialization phase directly on the hardware into an ADNA. To achieve this it uses a semantic knowledge base which provides both descriptions of the hardware's available sensors and knowledge on their relations in form of equations.
current state. Second, we describe the A2DNA’s core ideas. Next, we present and analyze the determinator’s algorithm. Finally, we discuss the A2DNA and our results and provide an outlook into the A2DNA’s future developments.
self-improving and self-healing mechanism that assigns task to processing elements (PEs) in embedded real-time systems. Inspired by the hormone system of higher mammals where cells communicate by sending hormones via the bloodstream, the PEs send short messages, so-called hormones, to communicate and decide the task assignment among themselves. On its own, the AHS has no knowledge of the system it has to realize. Any knowledge including the required tasks, their communicative interconnections and the PEs’ initial suitability for each task is provided by the ADNA. When a task is assigned to a PE, the PE derives the parametrization from its local copy of the ADNA. This process is shown in Figure 1. The ADNA is based on the observation that most embedded systems can be assembled from a limited number of basic elements, e.g. sensors, actuators, arithmetic/logic units, etc. Thus, it is possible to compose a given embedded system by combing a suficient multiset of these elements and providing a iftting parameterization for each element.
When designing an ADNA, the available sensors and actuators in the used hardware strongly influence the ADNA’s final shape. As an example consider the control loop in Fig. 2 and its netlist in Fig. 3. In this description, the sensor/actuator building blocks are mapped to specific sensors/actuators on the hardware. Not only the available sensors/actuators have to be known at this design stage, any change on the hardware, even reindexing, may result in an ADNA incompatible to the hardware. Thus, the ADNA cannot be used on another hardware without an external adaptation, making it rigid and bound to hardware. 3. Extension to the A2DNA As a solution to the ADNA’s rigidness, we propose the abstract ADNA (A2DNA). On the one hand, the A2DNA aims loosen the bindings between a specific ADNA 1 and the hardware. On the other hand, it should provide more knowledge on the sensors2 and their attributes’ relations such that the ADNA may be specified only when initializing the system.
Figure 4 shows the process of specifying an A2DNA for a given hardware. The A2DNA demands sensors in order to be used on the hardware while hardware knowledge is provided by the description of the available sensors. Both use so called abstract sensors to describe their sensors. A determinator specifies the A2DNA for the described hardware, resulting in an ADNA, using its knowledge on the relations between the abstract sensor’s attributes. The knowledge about the relations is provided in form of equations. Both the sensor description and equations form the knowledge base.
instance of
…
instance of
…
3.1. Abstracting the Sensors In contrast to the ADNA where a sensor is described by a sensor building block’s Resource ID parameter, a sensor in an A2DNA is described by an abstract sensor building block listing the required attributes.
sensors. Firstly, we distinguish sensors form each other by the physical quantities they measure. Secondly, since some quantities are vectors we have to take into account the sensor’s relative direction . As a naming convention, we choose the local frame described by [6], an example is shown in Figure 5. Finally, we have to diferentiate between the sensor’s target , i.e. does the sensor provide data about the system, the surroundings or only a part of either.
Definition 1 (Abstract sensor). An abstract sensor = (, , ) ∈ × × is defined as triple of measured physical quantity ∈ , the measurement’s direction ∈ and measurement’s target ∈ . (Id = 70, parameter = constant value, period) 1 2
ALU 1(Id = 1, parameter = Minus) 1
1
PID 1 (Id = 10, parameters = P,I,D, period)
Actor 1 (Id = 600, parameter =
resource)
Sensor 1 (Id = 500, parameters = resource, period) Example 1. The system (car) shown in Figure 5 may have the abstract sensors (velocity, -direction, car) and (velocity, -direction, car) that describe real sensors measuring the car’s velocity in direction of the x and y axis respectively. But our A2DNA in Figure 6 requires the abstract sensor (velocity, -direction, car). 3.2. Knowledge base So far, the described attributes lack any meaning or use for the determinator since it has no knowledge on any given connections between the attribute’s values. This knowledge is provided to the determinator through equations and serves as the backbone of its knowledge base. These equations include relations, e.g. velocity being the temporal derivation of traveled distance or that the velocities projected onto the x and y axes enable the calculation of the velocity projected onto the xy axis. With such knowledge, the determinator can infer what sensors are implicitly given on the hardware.
Definition 2 (Equation). Let {0, 1, . . . , } be sub set of either or or with ≥ 1. An equation := 0 = OP=1 describes the relation between an attribute 0 and the attributes 1, . . . , . The -nary operator OP denotes a specific building block 3 that derives the value of the attribute 0 from the values of the attributes 1, . . . , .
demands certain abstract sensors
describes the
available sensors
sensor
description
knowledge
base
Example 2 (Equation). To our car system in Example 1 we can convey the relation4 between the
required -direction and available - and -directions with the equation:
-direction =
-direction + -direction
√2
(
Definition 3 (Knowledge base). A knowledge base = (, ℰ ) consists of a set of available sensors on the hardware and a set of known relations (equations) ℰ .
Example 3 (Knowledge base). Combining the abstract sensors and equation from the Examples 1 and 2, the car system shown in Figure 5 may have a simple knowledge base5: = ({(v, , c), (v, , c)}, { = OP(, )}) ⏟ ⏞ ⏟ ⏞ ℰ 4While this relation is true for the any two projections onto orthogonal directions and their resulting diagonal direction, we limit it to and in the scope of our example.
1 = 599 v xy car // abstract sensor,
quantity = velocity, direction = xy, target = car 3.3. Determinator Utilizing the knowledge base , the determinator has now the tools to infer which abstract sensors in the A2DNA can be determined. 3.4. Applying equations to sensors
Definition 4 (Applying equations). Let be a set of sensors and := 0 = OP=1 an equation. We say that the set of sensors ′ = ∪ {} results from applying the equation to the set if we have one of the following cases6: • If there exists a set = {(, , )|1 ≤ ≤ } ⊆ , fixed by 1, . . . , in , then add = (0, , ). • If there exists a set = {(, , )|1 ≤ ≤ } ⊆ , fixed by 1, . . . , in , then add = (, 0, ). • If there exists a set = {(, , )|1 ≤ ≤ } ⊆ , fixed by 1, . . . , in , then add = (, , 0).
An application is denoted as = ().
We also say that applying to yields .
Remark 1. When applying an equation two of the yielded sensor’s attributes are defined by the sensors in and the remaining attribute is defined by the equation.
Remark 2. If multiple subsets fulfill the condition, then applying an equation on the same set may yield diferent sensors . Thus, we may have to apply once for every . Remark 3. We may also apply an equation to if for all that fulfill the condition, their yielded is already in .
Example 4. Recall the car system from Example 1 and its knowledge base from Example 3 = ({(v, , c), (v, , c)}, { = OP(, )}).
Applying the equation = OP(, ) on the set = {(v, , c), (v, , c)} results in the set ′ = {(v, , c), (v, , c), (v, , c)}, thus yielding the sensor = (v, , c). We have inferred the existence of a car velocity sensor in -direction, the sensor our A2DNA required.
Definition 5 (Produces). Let 0 and be sets of sensors. We say that 0 produces if for ≥ 1 exist equations 0, . . . , − 1 and sets of sensors 1, . . . , − 1, s.t. applying the equation to the set results in the set +1.
determinator can infer the existence of a specific composition for an abstract sensor utilizing the knowledge base .
Definition 6 (Determinable). We say a sensor is determinable in a given knowledge base = (, ℰ ) if ∈ or produces a set ′, s.t. ∈ ′.
Example 5. Consider again the knowledge base
Both (v, , c) and (v, , c) are in , thus they are determinable in . In Example 4, we see how application of one equation yields the sensor (v, , c). Since produces a set ′ with (v, , c) ∈ ′, this sensor is also determinable in .
Since the determinator knows how to construct a determinable sensor, we can consider any determinable sensor part of the sensors available on the hardware. This provides us with another definition for a sensor’s determinability.
Corollary 1 (Determinable). Let = (, ℰ ) be a knowledge base and ∈/ a sensor. If there are a set of sensors and an equation ∈ ℰ , s.t. = () and ∀ ∈ : is determinable in , then is determinable in .
Since all sensors in are determinable in , we know for each sensor ∈ which equations we have to apply to produce a set ′, s.t. ∈ ′. Applying all these equations sequentially on results in ′, s.t. ⊆ ′. Since applying to yields , applying to ′ results in ′′ with ∈ ′′, thus is determinable in . □ Example 6. Consider a knowledge base ′ = (′, ℰ ′) slightly diferent to the previous, where we still have (v, , c) ∈ ′ and = OP(, ) ∈ ℰ , but first have to determine (v, , c). If we determine (v, , c) in ′, then, by Corollary 1 and Example 5, we know that we can also determine (v, , c).
Finally, we can define the set of all sensors determinable in .
Definition 7 (All determinable sensors). Let = (, ℰ ) be a knowledge base. Let be set produced by , s.t. applying any equation to yields a sensor already in . Hence, every possible application of an equation in ℰ to results in .
We refer to as the set of all determinable sensors in .
Example 7. Consider again the knowledge base
= ({(v, , c), (v, , c)}, { = OP(, )}).
From Example 4, we know that produces the set ′ = {(v, , c), (v, , c), (v, , c)}. ′ = because applying our only equation = OP(, ) to ′ yields (v, , c) ∈ ′. Thus ′ is the set of all determinable sensors in our small knowledge base .
With the A2DNA’s general concepts defined, we can now focus on the determinators exact functionality. As a proof of concept, we describe a naive algorithm for checking the determinability of a set of sensors . This algorithm constructs the set of all determinable sensors (see Definition 7) inductively, then checks for each ∈ if it is also in . By we return true. definition all sensors in are determinable, thus we initialize as . Now we try to apply each equation as often as it yields a new sensor not in to . If at least one equation yielded a new sensor, then we have expanded and need to retry our equations. If no equation yielded new sensors, then has become
and we can proceed to the next step. For each ∈ , we check if ∈ . If at least one is not, we immediately return false. If all sensors were in ,
Before we can analyze Algorithm 1, we need to clarify how we check if is applicable to .
by the equation if there is a set of possible sensors that fulfills the condition. This leads to on the case 0 ∈ . First, we generate a hash map where all pairs of (, ) ∈ ×
application of 0 = OP=1 are in . For the description we focus without loss of generality7 serve as Output: Boolean = ; found_new_sensors = true; while found_new_sensors: found_new_sensors = false; foreach ∈ ℰ
: Input: Knowledge base = (, ℰ ) and a set of sensors while Applying to yields a new sensor: found_new_sensors = true; = (); return true; foreach ∈ : if ∈/ : return false;
Algorithm 1: Determinability check keys. The values represent the number of sensors found. Second, we iterate through . On the one hand, if a sensor (, , ) is found, we increase the value of the pair (, ) by one. If, on the other hand, the sensor (0, , ) is found8, the value of the pair (, ) is reduced by one. Thus, only if for a fixed pair (, ) all sensors (1, , ), . . . ( , , ) are in and (0, , ) is not in , the entry [(, )] will have the value and the equation will be applicable9. Theorem 1 (Complexity of Algorithm 2). Algorithm 2 has a complexity of ︁( (|| + | |)| | ︁) with | | = max{||, ||, | |}.
In each case, we generate a hash map with a size of at most | |2 entries. This has a run time of (| |2). Next, we iterate through and check for every entry if it has any . Since, all
9Note that all pairs in where the value is exactly have a set of sensors and the sensor is not part of the set.
Output: All pairs where the equation is applicable Input: An equation 0 = OP=1 and a set of sensors switch type(0): case 0 ∈ :
values as 0; foreach (, , ) ∈ : elif == 0: [(, )]− if ∈ {1, . . . , }: [(, )]+ = 1; values as 0; foreach (, , ) ∈ : elif == 0: [(, )]− if ∈ {1, . . . , }: [(, )]+ = 1; case 0 ∈ : return ;
Generate a hash map with every pair (, ) ∈ × as a key and initialize the Generate a hash map with every pair (, ) ∈ × as a key and initialize the values as 0; foreach (, , ) ∈ : elif == 0: [(, )]− if ∈ {1, . . . , }: [(, )]+ = 1;
= 1; Generate a hash map with every pair (, ) ∈ × as a key and initialize the
Algorithm 2: Check if 0 = OP=1 yields a new sensor □ With this part analyzed, we can finally analyze Algorithm 1’s complexity. 0, 1, . . . , form a subset of either , or , we have to check at most | | values. Thus, this step is at most (||| |). Therefore, Algorithm 2 has a complexity of ((|| + | |)| |). Theorem 2 (Complexity of Algorithm 1). Algorithm 1 has a complexity of ︁( |||| + (|| + | |)| ||ℰ ||| ︁) with | | = max{||, ||, | |}.
First we copy , this has a complexity of (||). Next, we have a nested loop. The outermost loop only terminates if we have not determined any new sensor in the previous iteration, hence is maximal and has become . In the worst case, each iteration may only add one new sensor, thus the loop has at most || − ||
iterations. Because of || ≤ || , this has a complexity of (||). The next layer iterates through all equations, therefore it has a complexity of (|ℰ |). In the innermost loop, we apply an equation to as often as it yields a sensor not in . All such applications are calculated by Algorithm 2. By Theorem 1 and since for each call of Algorithm 2 is at most , this loop has a complexity of ((|| + | |)| |). All in all, the nested loop’s complexity is (| ||ℰ |||(|| + | |)).
The final loop iterates once through and checks if a certain element is in , this costs at most (||||). Therefore, Algorithm 1 has a complexity of (|||| + (|| + | |)| ||ℰ |||) □ Corollary 2 (Complexity of Algorithm 1). Algorithm 1 has a complexity polynomial in its input.
Algorithm 1’s input consists of = (, ℰ ) and . We can derive the sets , and from this input by iterating once through each of and ℰ adding each new entry to its respective set. Thus, all three sets are linear in size to and the largest of them has size . Since we can determine at most all possible abstract sensors, ⊆ × × . Thus, is at most cubic in size to . All in all, we can broadly limit our complexity to (3 · +(3 +)· · · 3) = (8). Therefore, the complexity is polynomial in the input size . □ 4.1. Specification algorithm We can adapt Algorithm 1 by adding a hash map that stores for each sensor not in , which equation application added to . Note that multiple equations may exist that applied result in adding a specific sensor. If we now want to specify an abstract sensor in the A2DNA, then we just have to substitute each sensor in the A2DNA with either a sensor in or with the operator and sensors implied by the equation. If any substituted sensor is still not in , we repeat the substitution until all sensors are in .
Example 8. Consider again the knowledge base
= ({(v, , c), (v, , c)}, { = OP(, )}) and the A2DNA fragment in Figure 6. The determinator has derived the specification for the abstract sensor with ID 1. We have to use a building block for OP and connect the sensor blocks for the car’s velocity in - and -direction. An exemplary ADNA and net list are sketched in Figure 7.
In this paper, we have proposed a solution to the ADNA’s rigidness and lack of semantic knowledge about the hardware by extending the ADNA to the A2DNA with its own knowledge base. We have described how the A2DNA connects back to the ADNA by specifying the A2DNA and have provided a first algorithm in polynomial time for this task. The A2DNA and the knowledge base strength the system’s self-explaining property by providing a more nuanced understanding of the system’s hardware. Additionally, if the determinator has specified an abstract sensor with a combination of sensors, it can also explain the functionality of these Sensor (Id = 1, parameters = resource)
Sensor (Id = 2, parameters = resource)
OP (Id=3, parameters = operation) 1 = 500 (1:3.1) 1 // sensor, resource id for the x-direction sensor 2 = 500 (1:3.2) 2 // sensor, resource id for the y-direction sensor 3 = 2 xy // operation, performs the axes addition structures. Similarly, a hardware extension or new equations are easily communicable to the knowledge base. The A2DNA also allows the system to better adapt to the loss of sensors. If the access to a sensor is lost, the determinator can specify the A2DNA on its ’new’ reduced hardware at run time and adapt to the changes. Thus, providing the base for a better self-healing.
For the future we plan to provide a first full implementation of the A2DNA, the knowledge base and the determinator. OWL by [8] and its C# API by [9] for SPARQL seem a promising base for such an implementation10. In the first stages, the knowledge base will be provided by experts but we plan to later supplement this expert knowledge with learning algorithms. Finally, we plan to determine more precise boundaries for the time complexity and perform a space complexity analysis. 10An experimental implementation exists but would go beyond this paper’s scope. [6] H. Schaub, J. L. Junkins, Analytical Mechanics of Space Systems, American Institute of
[7] Qniemiec, RPY angles of cars, 2010. URL: https://commons.wikimedia.org/wiki/File:RPY_ angles_of_cars.png, https://commons.wikimedia.org/wiki/
frame" to "car frame". [8] B. Parsia, P. Patel-Schneider, B. Motik, OWL 2 web ontology language structural specification and functional-style syntax, W3C, W3C Recommendation (2012). [9] Project dotNetRDF, DotNetRDF, 2009. URL: https://dotnetrdf.org/, https://dotnetrdf.org/.