LAKEE: A Lightweight Authenticated Key Exchange Protocol for Power Constrained Devices

The rapid development of IoT networks has led to a research trend in designing effective security features for them. Due to the power-constrained nature of IoT devices, the security features should remain as lightweight as possible. Currently, most of the IoT network traffic is unencrypted. The leakage of smart devices' unencrypted data can come with the significant cost of a privacy breach. To have a secure channel with encrypted traffic, two endpoints in a network have to authenticate each other and calculate a short-term key. They can then communicate through an authenticated and secure channel. This process is referred to as authenticated key exchange (AKE). Although Datagram Transport Layer Security (DTLS) offers an AKE protocol for IoT networks, research has proposed more efficient and case-specific alternatives. This paper presents LAKEE, a straightforward, lightweight AKE protocol for IoT networks. Our protocol employs elliptic curve cryptography for generating a short-term session key. It reduces the communication and computational overhead of its alternatives while maintaining or improving their security strength. The simplicity and low overhead of our protocol make it a fit for a network of constrained devices.

(TLS) handshake, for example, the server's identity is verified using the server's public key and the digital signature of the SSL certificate authority. In Kerberos, the Authentication Server and the Ticket Granting Server are trusted third parties. [4] Some AKE protocols, such as Google's QUIC protocol, are multi-stage. In these protocols, different runs of the protocol are not independent, and the former keys are used to derive the next key [5]. In some cases, AKE is based on a pre-shared secret between parties. The high entropy pre-shared secret ensures forward secrecy. In this paper, we present LAKEE, an AKE protocol which is certificateless and based on a pre-shared secret. Our protocol avoids the public key infrastructure by using symmetric keys to be as lightweight as possible for employment in IoT networks. [6] We implement our protocol as an application on top of CoAP. Research has an interest in building application layer protocols, such as HTTP [7] and SOAP [8], on top of CoAP. Our practice is the same.
The contributions of the present work can be summarized below.
• We propose a lightweight and effective protocol which guarantees secure communication by establishing a secure session. We have implemented our protocol in Python using the aiocoap [9] library.
• The protocol can easily integrate with the existing system deploying DTLS-PSK without requiring additional code.
• After session establishment, the transport layer can use the generated key to encrypt application layer messages securely. More precisely, the session parameters are mapped to the DTLS session parameters without requiring any modification in the existing session format for DTLS-PSK mode. Thus the transport layer can protect the application layer message using the encryption mechanism of DTLS-PSK.
• We estimate our protocol's communication and computation overhead and compare it with the alternative protocols. We prove that the overhead of the protocol is significantly less than its competitors.
• We verify the security strength of the proposed protocol both by formal logic and simulation tools.

Related Work
Many researchers have focused on balancing the tradeoff between security and overhead of session establishment protocols in the context of IoT devices. Pan et al. [10] offer a lightweight certificateless protocol based on elliptic curves and bilinear pairing. However, a third component, as a key generation center (KGC), is required. The total number of messages for key exchange is also 4, which is more than our proposed protocol. It is not clear which participant is responsible for initiating the protocol.
Kalra et al. [11] and Kumari et al. [12] proposed authentication methods, but they depend on HTTP cookies. Moreover, when the cookie of a user-server connection resets, the number of steps is increased to 5. It is also shown that the Kalra and Kumari protocols are not desirably secure. [12], [13] Shin et al. [14] have proposed a security framework for MQTT, enabling the client and server to come up with a symmetric session key based on the AugPAKE protocol. [15] The protocol proposed by Yeh et al. [16] is a lightweight authentication method which employs elliptic curve cryptography and hashing to provide two endpoints with a session key. Hashing is known to be more efficient than encryption and can therefore benefit IoT networks. However, the method is dependent on a third element called Registration GW-node. Moreover, the login phase has 4 messages. Albalas et al. apply both Rivest-Shamir-Adleman (RSA) and Elliptic Curve Cryptography (ECC) for key generation in CoAP and discuss the advantages of ECC. The session key establishment scheme proposed by Dey and Hossain [17] has 7 steps involving 3 participants; the smart device, the service provider, and the home gateway.
Bhattacharyya et al. [18] have proposed LESS, a simple and lightweight authenticated key exchange protocol for IoT devices. The proposed protocol is implemented on top of the CoAP layer. The main difference between LESS and our protocol is the session key generation. In LESS, the server is responsible for choosing the session keys, which are transferred to the client in the second and fourth messages of the protocol. Majumder et al. [19] have also proposed an authenticated key exchange protocol based on ECC. They verify the security strength of their protocol both formally (using the BAN logic) and practically (using the AVISPA simulation tool). However, their protocol, ECC-CoAP, is not implemented, and its compatibility with CoAP is not verified. For example, CoAP may unexpectedly fragment the messages if they are larger than a limit. Figure 1: CoAP message structure [20] 3 Background

Constrained Application Protocol (CoAP)
CoAP is an application layer protocol for resource-constrained internet devices. For web integration, CoAP can be converted to HTTP. It also meets the fundamental requirements of IoT communication, which are multicast support, low overhead, and simplicity. CoAP is built on top of the User Datagram Protocol (UDP). As UDP is unreliable, unlike Transmission Control Protocol (TCP), an optional request/response layer is included in the messaging. The CoAP message structure is shown in figure 1 CoAP supports four types of messages: Confirmable (CON), Non-Confirmable (NON), Acknowledgement (ACK), and Reset (RST). A confirmable message guarantees reliability. Each confirmable message is replied to with an ACK by the server with the same message ID. Otherwise, it will be retransmitted using a default timeout and exponential back-off between retransmissions. However, non-confirmable messages are unreliable and are not replied to with an ACK. If the recipient cannot process a Non-confirmable message, it may reply with an RST message.

Elliptic Curve Cryptography (ECC)
ECC, proposed by Victor Miller and Neal Koblitz [21], [22], is a key-based cryptography technique based on the algebraic structure of elliptic curves over finite fields. It usually is an alternative to the RSA cryptographic algorithm. ECC features smaller ciphertext, keys, signatures and a faster generation of keys and signatures. The fundamental downside of ECC is that, due to the complexity of its mathematical foundation, it is difficult to implement securely.
An elliptic curve E is defined over a prime finite field F p . This smooth projective curve of genus 1 is denoted as E/F P and holds the following elliptic curve equation: We employ the mathematical operation of scalar point multiplication to perform an Elliptic Curve Diffie-Hellman Key Exchange (ECDH). The security strength of ECC lies in the difficulty of solving the Elliptic Curve Discrete Logarithm Problem (ECDLP). Similar to the Diffie-Helman Problem (DHP), ECDLP is based on the discrete logarithm problem and does not pursue any polynomial-time algorithm.

Datagram Transport Layer Security (DTLS)
IoT applications frequently encounter a variety of communication patterns that the Transmission Control Protocol (TCP) is unable to support effectively. Due to energy constraints, devices may often go into sleep mode; thus, it is infeasible to maintain a long-lived connection in IoT applications. In consequence, IoT networks use UDP as the transport protocol. Therefore, the SSL/TLS protocol, which makes TCP secure, is not applicable to the IoT environment. IoT networks can benefit from DTLS, which is a derivation of TLS protocol and provides the same security services on top of UDP.
CoAP can optionally use DTLS. CoAP defines four security modes.
• NoSec. • RawPublicKey, • Certificate DTLS provides CoAP with a nonoptimal handshake protocol with a long-lived key in the PresharedKey mode. It takes 6 messages (7 steps) to establish a session with this handshake. [23], [24] DTLS handshake protocol which can be used in CoAP for session establishment, is illustrated in figure 2.

Proposed Protocol
In this section, we present the LAKEE protocol completely. X → S : M denotes X sends message M to S. Figure 3 illustrates the protocol, which has 4 steps including 3 messages, while Table I explains the notations used.

Pre-negotiation
Before starting the handshake, the client and server must have agreed upon a prime finite field, an elliptic curve, a generator point, a key derivation function, and the symmetric high-entropy key Y.  an elliptic curve over the finite field F p and cyclic group generator P Y long-term symmetric key between client and server r c random number selected by the client r s random number selected by the server client_rand client's shared data for producing the session key where client_rand = r c .P server_rand server's shared data for producing the session key where server_rand = r s .P [E(.) k ] authenticated encryption of a plaintext using a symmetric key k h(m) unkeyed one-way hash value of message m concatenation #C i client identifier a.P scalar point multiplication; Point P is multiplied by scalar a.

Step 1. Client Challange
At first, the client generates a random number (r c ). It then computes client's challenge as client_rand = r c .P . The client concatenates the hash of its ID, client_rand, and current timestamp and encrypts the outcome with the pre-shared key Y. The client then sends its ID with the encrypted message to the server. The server recognizes the raw identifier, associating this message with a session initiation request. The client reveals his identity in this message. The novelty of our protocol is that the client challenges and authenticates the server first, reducing the required number of messages.

Step 2. Server Response and Challenge
After receiving the session initiation message from the client, the server checks the number of failed session initiation requests within a time frame originating from the message's source IP address. If it's greater than 3, the message is not processed. Otherwise, the server tries to decrypt the message using the pre-shared key. The server records the current time and checks |T 2 − T 1 | ≤ ∆T . If it holds, the shared secret is retrieved, and a random number is generated (r s ). The server then computes the server's challenge as server_rand = r s .P . It decides whether it is time to change the long-term secret (Y). The strategy with which the server chooses the time is out of the scope of the paper and is dependent on the information it stores about the clients. If the server decides to maintain Y, it sums the client's challenge with generator P (client_rand is a point on the curve). It then sends the result alongside its own challenge to the client.
If it decides to change Y during the handshake, it sums the client's challenge with twice the generator (2P) and sends the result alongside its own challenge to the client. When the information in the incoming is irrelevant, the handshake is terminated, and the number of failed attempts from the client's IP range is increased.

Step 3. Server Authentication and Client Response
In this stage, the client decrypts the server's message with the shared secret. It records the current time and checks |T 3 −T 2 | ≤ ∆T . If it holds, the client verifies the server's response provided that the message contains client_rand+P or client_rand + 2P . In the second case, it realizes that it should update Y during this handshake. The client then calculates server_rand + P or server_rand + 2P accordingly. It concatenates it with the current timestamp, encrypts the outcome, and sends the message to the server. The client locally calculates a shared secret which is a point on the elliptic curve. secret = rc.server_rand Using the horizontal position of the secret on the curve and the agreed key derivation function (KDF), the client calculates the session key. session_key = KDF (secret x ) If it also had to update Y, it calculates a new long-term key using the vertical position of the secret on the curve and the KDF.

Step 4. Client Authentication
In this stage, the server decrypts the client's message with the shared secret. It records the current time and checks |T 4 − T 3 | ≤ ∆T . If it holds, the server verifies the client's response the same as the previous step and calculates the session key. secret = rs.client_rand Using the horizontal position of the secret on the curve and the KDF, the server calculates the session key.
If it also had to update Y, it calculates the following.
In contrast with typical Internet users, each IoT device reaches out to a limited number of servers. We assume, as a consequence, that providing each client-server pair with a shared secret is feasible. Our certificateless protocol is independent of any authorities and third parties. Therefore, the proof of the parties' identity relies on the possession of the pre-shared and symmetric secret. As it is certificateless, our protocol with minor changes is employable in mesh IoT networks where any node can act as a client or a server dynamically.

Implementation
We have implemented our protocol on top of CoAP using the aiocoap python library. [9] We aimed to have a reproducible implementation, and it serves only as self-documenting code. We acknowledge that it could be more efficient by employing C++, for example. It is publicly available on Github 1 . The client performs all of the steps sequentially and in a single function. In contrast, the server would not block for an individual client. Therefore, it must store the handshake progress information, such as the challenge it sent to that particular client, and process the corresponding client's response upon reception. The first message (client challenge) is a Confirmable (CON) message. The second message (server response and challenge) is the Acknowledgement (ACK) of the first, and the third message's (client response) type is Non-Confirmable (NON). After sending the third message, the client would not wait for a reply from the server.
We have used the PyCryptodome package for encryption and elliptic curve operations. The AES block cipher is used because it has been standardized and resistant to side-channel attacks. Moreover, there are hardware acceleration mechanisms available for AES. The cipher in the CCM mode calculates a message authentication code (MAC) for each message to verify whether the received data is authentic. We employ the curve edwards448, also known as Ed448-Goldilocks, with the following equation. [25] The curve aims for a 224-bit security level, meaning that it is designed to increase the cost of breaking a discrete logarithm computation to 2 224 bit operations. [26] Daniel J. Bernstein and Tanja Lange have shown that this curve meets the ECDLP and ECC requirements. [27] However, Edwards448 points and scalars are bigger than those of other curves. We use a fixed 128-bit shared secret and the base point of the curve as the generator. PBKDF2 is used with SHA512 for deriving the session keys and new long-term secrets. [28] The ECDH secret has enough entropy for us to derive the keys without a salt and a large iteration number. The iteration number is 16 in the implementation.
The code reports the execution time at the end of the handshake. It varies by the running hardware. Once the key exchange has finished, the responsibility can shift from CoAP to DTLS for providing channel security. With the correct parameters, a DTLS session can be instantiated without having to perform the DTLS_PSK 7-step handshake.
• cipher suite = TLS_PSK_WITH_AES 128 CCM 8 • read state = S_k.x with encryption nonce • write state = S_k.y with encryption nonce Along with the above parameters, one has to instantiate the client and server's initialization vectors, generate a sequence number, and fill other parameters for the desired DTLS session, such as Peer certificate with NULL.

Security Evaluation
In this section, we evaluate the security strength of our protocol.

Properties of the Protocol
The security goals are achieved as stated below.
• Confidentiality: All the secrets, including the timestamps and challenges, are encrypted.
• Integrity: We use the AES-CCM ciphersuite, which performs MAC(message authentication code)-then-Encrypt for every message. The MACs and the hash of the client ID guarantee the integrity of messages.
• Entity Authentication: Instead of digital signatures and certificates, the approach of this protocol for entity authentication is challenge-response. The random numbers used for building the session keys are used as challenges, and the other party needs the pre-shared secret and the negotiated curve to be able to process them.
• Message Authentication: As stated, MACs computed for transmitted messages provide message authentication.
• Non-repudation: As the client is expected to be an IoT device for which there are pre-defined tasks, we do not count non-repudiation as a necessary property for our protocol. Hence, we base our protocol on the pre-shared symmetric key. Also, instead of digital signatures, which provide non-repudiation, we use MACs which provide authentication.
• Perfect Forward Secrecy: In the proposed scheme, if the key Y is compromised and the adversary is able to read client_rand and server_rand, he cannot calculate the session key as he should obtain at least one of the secret randoms. The adversary cannot obtain the secret randoms from client_rand and server_rand due to the hardness of the elliptic curve discrete logarithm problem.

Quantitative Security Analysis
In this part, we discuss the security of our protocol against famous attacks. Table 2 compares the security strength of LAKEE with alternative protocols.

Man-in-the-Middle Attack
The assumption of our scheme is that the pre-shared key (i.e., Y ) remains a secret. Consequently, an adversary would not be able to modify plain messages, including the session initiation message. Besides, the MACs computed for each message make them unforgeable.

Denial-of-Service (DoS) Attack
The number of times an IoT device can attempt to be authenticated is limited within a timeframe. In the session initiation phase of our scheme, if the IoT device fails to be authenticated by the server within 3 attempts, the IoT device will be blocked for a specific period. Hence, an adversary will not be able to send multiple requests (more than 3) to overload the system resource to make the services unavailable to the legitimate client. Thus, our protocol restricts the DoS attack.

Replay Attack
A timestamp is associated with each message. If a participant receives an old message, it is not processed, and the connection is terminated. Hence, an adversary may not be able to use the captured messages to perform a replay attack. The adversary is also not able to change the timestamps as they are encrypted and protected with MAC.

Insider Attack
In this type of attack, an insider of the remote server acts as an adversary after getting some user credentials stored on the remote server. As the session key cannot be computed by acquiring client_rand and _rand and the adversary needs to know at least one of the random secrets, the protocol is safe against insider attack.

User and Server Impersonation Attack
As the attacker is not in possession of key Y, it cannot impersonate either client or server as all the messages include MACs and cannot be forged.

Offline Password Guessing Attack
This attack mainly occurs in password-based authentication schemes, which is also a challenge-response scheme. However, in our proposed scheme, the challenge will differ at each epoch. Hence, the attacker cannot randomly guess the response to authenticate himself.

Known Session Specific Temporary Attack
The session key is calculated at the ends, not transmitted with the messages. Hence, LAKEE is secure against known session specific temporary attack.

Invalid Curve Attack
When the attacker forces the server to compute a common secret using a point outside the defined curve, an invalid curve attack has occurred. As the client and server verify random points they receive, i.e., client_rand and server_rand, they would terminate the connection if each point is in infinity or outside the chosen curve.

The MOV attack
As all the points are transferred encrypted, we would not expect an adversary to obtain the random points (i.e., server_rand, client_rand). If any of the random points are guessed or acquired in polynomial time, there are two ways to prevent the adversary from obtaining the generator point (i.e., P). 1) Keep the embedding degree k greater than 100. 2) If the curve's subgroup divides the curve order, then the embedding degree should be the smallest k ≥ 2 such that n|q k − 1 for all values k from 2 to 100.

AVISPA Tool
In this section, we demonstrate that LAKEE is secure against relevant threats using the Automated Verification Internet Security Protocol and Applications (AVISPA) simulator program.

Introduction to the AVISPA Simulation Tool
AVISPA is a role-based simulator that assigns a specific role to each protocol participant. A specification provided in a supported language is used to verify a protocol. The primary language supported by AVISPA is High-Level Protocol Specification Language (HLPSL). The working structure of AVISPA is depicted in figure 4. HLPSL2IF translates HLPSL specification into an Intermediate Format (IF), where IF is a low-level language. The backends of the AVISPA tool use IF to analyze whether the security and authentication goals written in the specification are satisfied or violated. The AVISPA then produces the output SAFE and UNSAFE, respectively. The current version of the AVISPA tool supports 4 different types of backends.

OFMC
The AVISPA tool includes several backends for analyzing protocols. We use OFMC, a tool for falsification or verification for a bounded number of sessions. OFMC employs the Dolev-Yao intruder model [29] to check several parallel sessions

HLPSL
We now discuss the basics of the AVISPA tool's protocol specification language. HLPSL is a role-based language with which we can specify the actions of each participant in a protocol. For specifying a protocol in the HLPSL language, we have to define the following.
• Basic Roles: For both the client and the server, we have to define a role, including their actions, such as receiving and sending messages in certain formats.
• Transitions: Each transition is the representation of the receipt of a message and the sending of a reply message. Transitions are defined for a certain role.
• Composed Roles: For grouping our basic roles and representing a whole protocol session, we have to define a session role. For storing the global constants and composition of multiple sessions, we have to define an environment role. The intruder can actively take action in this environment. These composed roles do not have a transition section, but they have a composition section in which the basic roles are instantiated.
• Security Goals: In the environment role, we have to declare which parameters are shared secrets and which parameters are used for the authentication of participants.
For more information about the syntax of HLPSL and examples, please refer to the AVISPA manual. [30] Simulation Results We have defined our protocol in HLPSL with the following simplifications. We have not included timestamps and have defined elliptic curve mathematical functions simply as hash functions. In our specification, the client authenticates the server on comprehension of SRand (server_rand), and the server authenticates the client on comprehension of CRand (client_rand). SRand, CRand, Srand (rs), and Crand (rc) are shared secrets. We have not included the session key in shared secrets as it is not transferred in the protocol. We have used the SPAN + AVISPA virtual machine and SPAN graphical tool [31] to parse our specification and the OFMC backend to verify our protocol. The result in figure 5 indicates that our protocol is safe.

Formal Verification Using the SVO Logic
Although Majumder et al. [19] and Mahmood et al. [32] use the BAN logic [33] in order to verify their protocol formally, we firmly believe that BAN logic is not suitable for verifying key exchange protocols. Alternatively, we use the SVO Logic [34]. Syverson and Oorschot [34] revealed that BAN analysis might lead to inappropriate conclusions in some settings. Therefore, they presented a logic capturing the desirable properties of the BAN family of logics, including BAN [33], AT [35], GNY [36], and VO, [37] that is both sound and relatively easy to use

Preliminaries of SVO Logic
In this section, we briefly review the SVO logic, the notations, rules, and axioms. However, we omit some definitions unused in our analysis, such as the concept of public key. [38] Notation The entities' names who want to perform an authenticated key exchange are Client and Server. We have assumed that the Client and Server have shared a long-term key. We use the symbols for Client (C), Server (S), the pre-shared key (Y), and the session key (k).
P believes X : The principal P may act as though X is true.
P received X : The principal P received a message containing X. P can read and repeat X.
P said X : The principal P at some time sent a message including X.
P says X : The principal P must have said X since the beginning of the current protocol run. P has X : X is either, • Initially available to P, • Received by P, • Freshly generated by P, • Constructible by P from the above. P controls X : The principal P has jurisdiction over X. P is an authority on X and should be trusted on this matter.
fresh (X) : X has not been sent in any message prior to the current protocol run. P k ← → Q : P and Q may use the shared key k to communicate. k will never be discovered by any principal but P,Q, or a principal trusted by P or Q. P K δ (P, k) : k is a public key-agreement key of P. A Diffie-Hellman key formed with k is shared with P.
{M } k : Encryption of message M using key k. Encrypted messages are uniquely readable and verifiable as such by holders of the right keys. P k− ← → Q ≡ (P k ← → Q ∧ P has k) : No one aside from P and Q and those they trust knows or could deduce k. While P knows k, Q may or may not. k is said to be P's unconfirmed secret. P k+ ← → Q : P knows k, and has received evidence confirming that Q knows k. No parties other than P and Q and those they trust knows k. k is P's confirmed secret suitable for Q.

SVO Rules
The SVO logic has two inference rules: Modus Ponens : From ϕ and ϕ → ψ infer ψ Necessiation : From ϕ infer P believes ϕ ' ' is a metalinguistic symbol. 'Γ ϕ' means that ϕ is derivable from the set of formulae Γ and the stated axioms using the inference rules. ' ϕ' is a theorem, i.e., derivable from axioms alone without any additional assumptions.
SVO axioms In this part we introduce the SVO axioms.
Belief Axioms 1. ( P believes ϕ ∧ P believes (ϕ → ψ)) → P believes ψ 2. P believes ϕ → P believes (P believes ϕ) implicitly names the (Diffie-Hellman) function that combines k with k − 1 (or, k with k − 1) to form a shared key. This is the axiom the BAN logic lacks.
Receiving Axioms 5. P received (X 1 , ..., X n ) → P received X i , for i = 1,...,n 6. (P received{X} k+ ∧ P has k − ) → P received X Here K + and k − are used to abstractly represent cognate keys, wheter symmetric or assymetric. In the symmetric case, k + = k − = k. In the assymetric case, k + is a public key and k − is the private key. Posession Axioms 7. P received X → P has X 8. P has (X 1 , ..., X n ) → P has X i , for i = 1,...,n 9. (P has X 1 ∧ ... ∧ P has X n ) → P has F (X 1 , ..., X n ) F is a meta-notation for any function computable in practice by P, e.g., encryption.
Comprehension Axiom 10. P believes(P has F (X)) → P believes(P has X) F is meta-notation for any function that is effectively one-one and such that F + or F − is computable in practice by P .

Verification of the Protocol using the SVO Logic
We should meet the goals below to have a secure and authenticated key exchange. G1. Entity authentication: C believes S says F (X, N A ). This goal necessitates that, given N A known to be fresh to C, S recently sent a message F (X, N A ), indicating that S has seen N A and has processed it. G2. Secure key establishment: Participants believe they are in possession of a good key to communicate with each other. The goal can be formulated as: C believes C k−

← → S
It is important to note that in our goals, the session key is an unconfirmed secret. No one knows or could derive k except C and S and those they trust. This notation is different from confirmed secret. If k is a confirmed secret, C knows k and has received evidence that S also knows k. It is apparent that our protocol does not establish a confirmed secret.

Performance Analysis
In this section, we estimate the overhead of our protocol with respect to the arithmetic and cryptographic operations used in our scheme.

Computation Overhead
To calculate the total computational cost of our protocol, we have borrowed the primitive arithmetic and cryptographic operation timings from Kilinc et al. [39], demonstrated in Table 3. The table shows the arithmetic mean and the standard deviation of the following primitive operations for 1000 executions each.  Table 4 shows the efficiency of LAKEE in comparison with other protocols seeking the same goal.  [19] 6T ECP M + 4T E/D(s) + 5T h 28.779ms Dey and Hossain scheme [17] 4T EM od + 6T E/D(s) + 6T h 38.527ms

Communication Overhead
For calculating the communication overhead in bits, we have to specify the length of each element. Ideally, the client ID is 64-bit long, and timestamps are 32 bits long. If we use the curve Ed448, server_rand and client_rand are 224 bits long. If we use other curves with a 128-bit secury level, server_rand and client_rand would normally be 128 bits long. The MAC, which the ciphersuite appends to the plaintext, has a fixed size of 128 bits. We use SHA-1 as a hash function for the client's ID with a 160-bit long output. The ciphertext would be the same size as the plaintext. The message sizes are calculated below.
• first message: 64 + 160 + 224 + 32 + 128 = 608 bits • second message: 224 + 224 + 32 + 128 = 608 bits • third message: 224 + 32 + 128 = 384 bits • total: 1600 bits In practice, each message should include a header not necessarily specified in the protocol. Therefore, besides the size of the messages in bits, the number of messages corresponds to the protocol's efficiency as well. LAKEE requires 3 messages for session key generation and authentication, which is less than its alternatives. Table 5 compares the total number of messages required by LAKEE and its alternatives.

Conclusion
In this paper, we proposed an efficient and lightweight authenticated key exchange protocol for the setting of IoT by employing elliptic curve cryptography. We addressed the performance and security shortcomings of the existing protocols. The results are promising. and our protocol, LAKEE, is proven to be more efficient than alternative protocols. LAKEE is implemented as an application protocol using CoAP. The security of it is analyzed formally and using the AVISPA security tool.


An informative planning-based multi-layer robot navigation system as applied in a poultry barn

Many real-world robot applications, as found in precision agriculture, poultry farms, disaster response, and environment monitoring, require search, locate, and removal (SLR) operations by autonomous mobile robots. In such application settings, the robots initially search and explore the entire workspace to find the targets, so ficiently and safely, thus being a useful component for robotics. The effectiveness and robustness of the proposed methods are validated through simulation and comparison studies.

Background
Global broiler production has been growing since the 1960s; in the United States alone, over 9.22 billion broilers were produced in 2020 at a value of 21.7 billion dollars [1] . A modern broiler barn holds 25,000 to 100,000 broilers on the open litter floor. Within the intensive production system, broiler mortality could be largely due to disease and metabolic problems and unsuitable environmental conditions and management [2] . The mortality rate is commonly 5% in an eight-week production cycle [1] and can reach 10% without appropriate management [3] . As a daily task, producers need to collect and remove broiler mortality timely, which is an arduous, time-consuming, and unpleasant task. A farmer spends hours daily identifying, gathering, and transporting dead birds in a typical broiler barn (e.g., 25,000 birds/barn). Manual mortality collection is relatively simple when broilers are young because they are lightweight and small. However, older broilers are bigger and weigh more, and, to avoid overwork, farmers may deposit the mortality in scattered piles within the broiler barn for subsequent removal [3] . A dead bird residing on a litter floor can result in higher levels of bacterial accumulation and increase the risk of disease spread via direct contact or vector transmission [3] . Additionally, caretakers risk their health if exposed to harsh working environments (e.g., concentrated ammonia and dust) for a long term [2] . Therefore, autonomous robotic systems for collecting broiler mortality are warranted to improve labor efficiency and reduce biosecurity issues.
Robotic systems have been developed to facilitate poultry production [4,5] . Vroegindeweij et al. developed a PoultryBot to avoid obstacles and pick up floor eggs in cage-free hen housing systems [6] . Li et al. developed an egg picking robot based on a deep learning detector and a robot arm [7] . Some poultry robots are commercialized to help farmers monitor environments, inspect bird health and welfare status, stimulate bird movement, aerate litter, and disinfect poultry barns. However, robots for poultry mortality removal are still not commercially available. Many aspects need to be considered for developing such a robot [8] . Among them, robot path planning is one of the most essential parts of effective and efficient determination of robot routes [9,10] .

Related work
Many approaches have been proposed to achieve reliable autonomous robot motion planning, such as ant colony optimization (ACO) [11][12][13] , fireworks algorithm (FWA) [14] , bat-pigeon algorithm (BPA) [15] , graphbased method [16] , and neural network models [17][18][19] . Lei et al. proposed a hybrid model to optimize the trajectory of the global path using a graph-based search algorithm associated with an ant colony optimization (ACO) method [11] . A hybrid fireworks algorithm with LIDAR-based local navigation capable of generating short collision-free trajectories in unstructured environments was developed [14] . The cuckoo search algorithm has also been successfully applied to the efficient and safe navigation of robots [20] . A bat-pigeon algorithm [15] was developed with crack detection-driven autonomous vehicle navigation and mapping, in which a local search-based bat algorithm and a global search-based pigeon-inspired optimization algorithm are effectively integrated to improve the speed and performance of robot path planning and mapping. Wang and Meng [16] suggested a nonuniform sampling technique, which efficiently computes high-quality collision-free paths based on a generalized Voronoi graph. A biologically motivated neural network model using a shunting equation was proposed by Yang and Luo [17] for real-time path planning with obstacle avoidance. Luo et al. extended the model of trajectory planning with safety consideration in conjunction with the virtual obstacle algorithm [21] . However, the design and implementation of path planning in a broiler barn involve multiple aspects for mortality removal. Especially with the large scale of modern broiler barns (e.g. 12 m × 200 m), poultry mortality is widely distributed anywhere in the barn, which increases the difficulty of detecting and removing dead broilers. Therefore, we propose a system for searching and removing broiler mortality with two robots. One is a broiler mortality detection robot and the other is a broiler mortality removal robot. The major function of the detection robot is to precisely and efficiently search the whole broiler barn and indicate the position of dead broilers. Thus, coverage path planning (CPP) algorithms need to be introduced to assist robots in search and exploration tasks, such as bio-inspired neural networks [22] , Boustrophedon grid decomposition [23] , deep learning [24,25] , etc.
Luo and Yang [22] developed the bio-inspired neural network (BNN) method to navigate robots to perform complete coverage path planning (CCPP) while avoiding obstacles within dynamic environments. The robot is attracted to unscanned areas and repelled by the previous scanned areas or obstacles based on the neural activity through the BNN model. The next position of the robot depends on the current position of the robot and neuron activity associated with its current position. Zhu et al. proposed a complete coverage path planning model using Glasius BNN, which is extended to multiple robots to lower the overall search time and improve efficiency [19] . Unlike the BNN approach, the boundary representation model that defines the workspace is adopted by the Boustrophedon cellular decomposition (BCD) method and deep reinforcement learning approach (DRL). The BCD method proposed by Acar and Choset [23] decomposes the environment into many line scan partitions explored through a back-and-forth path (BFP) in the same direction. BCD is an effective CCPP method for more diverse, non-polygonal obstacles in a workspace. In trapezoidal decomposition as a cell, it is covered in back-and-forth patterns. For a complex configuration space with irregular-shaped obstacles, BCD needs to construct a graph that represents the adjacency connections of the cells in the Boustrophedon decomposition. Similarly, Nasirian et al. utilized traditional graph theory to segment the workspace and proposed a deep reinforcement learning approach to solve the CCPP problem in a complex workspace [24] . Lei et al. proposed a deep learning method to detect the workspace and generate turning waypoints for the robot to complete the coverage of the entire workspace [25] . The trajectory generated by the above-presented algorithms completely covers the workspace in light of the size of the robot, which is more suitable for a largesized workspace with a broad sensing range. However, with the limited sensing range of robots in broiler barns, a complete coverage trajectory requires a large amount of time and energy, which may not be affordable to the farmers.
The methods of object detection have been extensively studied, and many object detectors are utilized in many agricultural settings. Li et al. proposed a fast region-based CNN (R-CNN) detector with high accuracy to adapt to the illumination of different colored lights in the farm and detect the cage-free floor eggs [26] . A mask R-CNN object detector was developed by Li et al. to detect hen preening behaviors in barns to automatically monitor poultry behaviors, judge the comfort level of hens, and assist welfare-oriented poultry management [27] . Bochkovskiy et al. proposed a YOLO V4 object detector, which is a deep learning-based object detection technique with high accuracy [28] . It is an effective object detector to localize objects in real-time processing.

Proposed methods and original contribution
A directed coverage path planning (DCPP) fused with an informative planning protocol (IPP) is proposed to efficiently search the entire barn. The broiler barn is first decomposed into large grids based on the workspace dimensions to obtain overall global trajectories with coverage directions. IPP continues to rapidly achieve spatial coverage with the least estimation uncertainty in the decomposed grids. Flexible and efficient trajectories are formed by utilizing historical information of broiler mortality spatial distribution [29] and the direction information from the previous steps. With the assistance of current state-of-the-art computer vision algorithms in precision agriculture, such as deep learning techniques [30] , the robot could detect dead birds in the grids of vision range and find the mortality location for the removal robot. Such a comprehensive path planning method for the localization robot could pinpoint targets and avoid unnecessary searching trajectories, saveing the robot time and energy.
After the locations of dead broilers are precisely and efficiently identified, the removal robot is deployed to collect the mortalities. To save time and energy, the total length of the path to remove multiple dead broilers in succession should be minimized [31] . In that regard, a new hub-based multi-target routing (HMTR) scheme is developed in this paper, which originates from the row-based environment routing of broiler barn. By introducing hub grids, computational efficiency is improved for distance calculations between targets. Based on the locations of the dead birds, the best visiting sequence is determined while planning collision-free trajectories simultaneously. Furthermore, a reactive local navigator is developed to dynamically update the path and map in real time to avoid moving obstacles and unforeseen obstacles in the dynamic environment. This is of great help to robot safety and obstacle avoidance and prolongs the life of the robot.
Overall, we propose a system for detecting and removing broiler mortality with two robots. The detection robot consists of an informative directed coverage path planner and a You Only Look Once (YOLO) V4-based dead bird detector. The removal robot collects dead broilers by the hub-based multi-target path routing (HMTR) scheme. Meanwhile, with the reactive local navigator, the robots avoid obstacles and reach the target position through the real-time updated information of the onboard LIDAR sensors.
The major contributions of this paper are summarized as follows: • A multi-layer robot navigation system for search, locate, and remove (SLR) operations is developed for the removal of dead broilers in a poultry barn to reduce the daily laborious and time-consuming work. • A directed coverage path planning (DCPP) method integrated with an informative planning protocol (IPP) is developed to efficiently search targets in a large-scale workspace, which is initially decomposed into grids, and the optimal coverage directions are obtained based on the workspace. The detection robot adaptively explores the workspace to generate the trajectory in the grids in light of the historical data of searched targets and the coverage directions. • The informative planning protocol (IPP) is developed to integrate coverage directions devoted to rapidly achieving spatial coverage with the least estimation uncertainty in the decomposed grids. • To efficiently reach the targets, a new hub-based multi-target path routing (HMTR) scheme is proposed to row-based environments. The total visiting distance is minimized through obtained targets to generate an optimal sequence to connect all the targets. • Practically, to apply this navigation system in the poultry barn, multiple robots with this developed navigation system are utilized, consisting of a dead broiler search robot to search and locate the dead broilers and a dead broiler removal robot to collect the dead broiler afterwards.

Workspace setup and robot configuration
The complex barn environment is simplified into a rectangular robot workspace (152 m long × 12 m wide) based on typical United States broiler barn dimensions [32] . The workspace where the robot needs to collect dead broilers consists of multiple feeding and drinking lines that run the length of the barn, start and end positions of the robot, and dead and live broilers that are randomly located in the barn. Two feeding and three drinking lines are arranged in parallel in the middle, each measuring 140 m long and 0.3 m wide [ Figure 1]. The distance between lines is 1.75 m, and endpoints of the lines are 6 m away from the ends of the barn. The start and end positions are located near the gate of the barn and could be altered in a real-world application. Live/dead birds are simplified as 20 cm diameter circles. With a stocking density of nearly 929 cm 2 /bird (1 ft 2 /bird), the barn is assumed to have 20,000 birds. The workspace is illustrated in Figure 1.  The tested robots in this paper are assumed to be cylinders, each 20 cm in radius and 60 cm in height. The payload based on bird volume (10 cm in height and 11-30 cm in diameter [33] ) is estimated as 30 dead birds. It is equipped with a camera to capture bird images in real time. The entire workspace is decomposed into non-overlapping grids, each measuring 200 cm long × 200 cm wide [ Figure 1]. A LIDAR sensor is mounted into the robot to detect static (i.e., feeding and drinking lines) and dynamic (i.e., live broilers) obstacles. The effective maximum detection range is limited by complex environments to a radius with approximately 60 cm. The basic function of the robot is to search for dead and live broilers during their moving, arrive at the mortality, and avoid moving birds. The parameters of the robot are set as follows: maximum linear velocity of 1 m/s, maximum angular velocity of 20 rad/s, maximum acceleration/deceleration of 0.2 m/s 2 , and maximum angular acceleration/deceleration of 50 rad/ 2 . These parameters are suited to industrial levels. The proposed autonomous robot is illustrated in Figure 2.

Overall workflow for robot path planning
The overall procedure of the multi-layer robot navigation system is shown in Figure 3. The workspace is decomposed into a grid-based working map and fed into the robots. The whole robotic framework consists of the detection robot and removal robot, where the detection robot is run at first followed by the removal robot. The detection robot considers the map information and historical mortality distribution while it outputs a

The overall workflow of the proposed work
Details of the corresponding algorithms are described in the following sections. The overall workflow of the path planning for the broiler mortality detection and removal robots is illustrated in Figure 4.
The proposed multi-layer robot navigation system illustrated in Figure 4 consists of informative directed coverage path planning (directed coverage path planning and informative planning protocol), the hub-based multitarget routing (HMTR) scheme, target detection, and YOLO V4. In this navigation system, the initial robot is tasked with finding and locating objects in a large-scale setting, while the second robot proceeds directly to the targets it has discovered to remove the objects. To effectively search the full vast workspace, a directed coverage path planning (DCPP) coupled with an informative planning protocol (IPP) is proposed in the system, as shown in Figure 4. To quickly achieve spatial coverage with the least amount of estimation error in the deconstructed grids, IPP is recommended for coverage directions in DCPP. The detection robot is driven by the You Only Look Once (YOLO) V4-based dead bird detector and an informative-based directed coverage path planner. As applied in the poultry barn, two robots are utilized in this multi-layer navigation system to find and eliminate broiler mortality.

Directed coverage path planning
The directed coverage path planning (DCPP) is utilized to generate an overall trajectory of the broiler mortality detection robot. It should meet the following requirements: 1. The mobile robot must move through all regions of interest in the barn. 2. Motion trajectories should be simplified as straight lines.
3. The robot should cover the regions with minimal overlapping. 4. The path should be optimized with one of the criteria, such as distance, time, and energy. 5. The start and end points for the robots should be co-located so that farmers do not need to enter the barn and retrieve the stopped robot from the barn interior.
In this paper, the criterion to generate a directed coverage path is the total shortest path, which could save running energy for the robots. In the decomposed working map, the adjacent grids share at least one boundary, while nodes of the adjacent grids are connected to form overall trajectories. There are two commonly used methods for CPP: zigzag motion planning and spiral motion planning, namely back-and-forth and boundary sweep methods [17] .
The robot moves along the lengthwise direction of the workspace under the zigzag motion planning, and the total path length is calculated by Equation (1): where L is the total length of zigzag motion planning; is the length of the long side of a workspace; L is the length of the short side of a workspace; and L is the length of a grid. The robot under the zigzag motion planning moves along the long side of the workspace L /L times and along the short side L /L − 1 times.
Under the spiral motion planning, the robot moves along the boundary of the workspace progressively and at the same time toward the center spirally. The total travel distance (TD) on the short side D is The total travel distance on the long side D is where is the total length of spiral motion planning. However, the start and end points of the robot coverage path are different based on the two traditional methods, which cannot meet Requirement 5. The total path length should include the returning path towards the start point, which could be suboptimal under the two planning methods. Lemma 1. The length of returning path under zigzag planning in the workspace (L ) is constrained as The equality holds on the left of Equation (5)  The equality is satisfied on the right of Equation (5) This completes the proof of Lemma 1.

Lemma 2. The length of returning path under the spiral planning in the workspace
Proof. Since L ≥ L > L , The equality holds on the left of Equation (7) when L = 2 × × L for = 1, 2, 3, ... Then, the L is The equality holds on the right of Equation (7) when L = (2 × − 1) × L for = 2, 3, 4, ...
Then, the L is This completes the proof of Lemma 2.
The robot follows the first two steps of spiral motion planning, then repeats the zigzag motion planning, and finally returns to the start point. The robot is assumed to run along the feeding and drinking lines without moving across them. The DCPP finally provides the robot with overall trajectories from the start to end points.
The total path length of DCPP (L ) is calculated through Equation (10): The procedure of the proposed DCPP in a broiler barn is described in Algorithm 1. It is worth noting that the DCPP does not provide the robot with an actual coverage path, which could vary based on the IPP. The informative planning protocol (IPP) further refines and optimizes the coverage path based on historical data on broiler mortality distribution in a broiler barn. In the general case, the IPP incorporates the multiobjective informative planning and uses DCPP and historical data to guide the robots to more frequently visit those places with a higher probability of broiler mortality appearance. This multi-objective optimization problem is stated in Equation (11). * = argmax where is a sequence of robot motion planning, * is the selected robot motion with maximum information gain, M is the list of possible robot motion sequences, C is the cost budget, and B is a budget with regard to time, memory, energy, maximum iteration times, etc. I ( ), = 1, 2, ..., , represents the information gathered by the robot motions and is the number of the information source in the grid [34] . ( ) represents the information from planned DCPP directions.  The informative directed coverage path planning is shown in Figure 5. In Figure 5A, the planner weighs different objectives (e.g., rapidly covers the space as driven by DPCC or moves to the most likely area as driven by heat map) and optimizes the multi-objective problem to choose a preferred solution from a given set of optimal solutions. The preferred solution is then reflected as actions planned into the workspace, and the learner further improves it in a back-propagation direction. Finally, the most promising solution is determined based on rewards, and a mortality-based coverage path is constructed accordingly. A specific example of the IPP is depicted in Figure 5B. The major component is a primitive path which is built with robot kinematic constraints and divided into five sub-branches, each connected by two nodes. The path is constructed accumulatively during each iteration, and the most informative nodes are explored and selected first for the area with the highest probability of broiler mortality appearance. The rewards are only utilized in the selected nodes for optimization. The framework consists of selection, expansion, simulation, and back-propagation in each iteration. During selection, starting at the initial position, target nodes are recursively selected until an undependable node is encountered. During expansion, each expandable node is subdivided into five subbranches. During simulation, the multiple-objective function is operated in each expandable node to gain a reward vector. Finally, during back-propagation, the rewards are backed up in each selected and expandable node.
Note that the information in this paper is defined by the broiler mortality historical data for the past 30 days.
Since historical data as a priority map also have uncertainty, we utilize the Gaussian process (GP) to transform them into a continuous information map. The amounts of information in each grid can be varied with the number of dead broilers detected. To ensure the robot' s path tends to the next planned grid, we set ( ) as the average value of the current grid information at the adjacent edge, which proportionally decreases with the distance in the opposite direction of DCPP in the grid. More ( ) information can be clearly found in the red dashed rectangle near the edge of the next grid [ Figure 6A]. The planned path tends to be an optimized decision between the length and information gain along it, which might be conflicting in nature. Note that the IPP is only executed within each grid. The path obtained by DCPP becomes an information-oriented application in each grid, guiding the robot to the next grid. The resultant trajectory in the grid is shown in Figure 6B.
The time complexity depends on the Monte Carlo Tree Search (MCTS) tree depth and the steps of each simulation. Assume in an arbitrary iteration , the tree depth is . Then, the number of total actions is ( × ), where is the number of defined primitive actions. Assume each simulation process costs ( ), which is a problem-dependent value (e.g., the steps of simulation are preset depending on the simulation time budget, considering that longer simulations are more accurate, while shorter simulations return a result more quickly). Then, the complexity for one search iteration is ( × + ). If we proceed iterations, the complexity is ). For multiple objective computation, the complexity becomes ( ( × 2 + )) due to required extra computation in the MCTS selection step. For practical runtime assessment, a concrete example is when searching 1000 iterations with five available actions on a standard laptop, MCTS takes around 0.3 s and multi-objective MCTS (formally ParetoMCTS) needs about 1 s. With a better computer, the runtime should be even better. This suffices to make a real-time decision.

Target detection
The target detection is to localize dead birds in real-time processing [35,36] . The dead birds are detected by the YOLO V4 dead bird detector [28] [ Figure 7]. The images are captured by the camera and input into the detector. The detector should first be well trained and developed in view of the captured images. Then, the trained YOLO V4 takes the acquired image as an input to convert it into a map with default grids. Predefined anchors are tiled onto each grid cell, and predictions of bounding boxes along with confidences and class names are made accordingly. With the non-maximum suppression rule, the bounding box with the highest confidence is retained for dead bird detection. Finally, the detection results, including indices, centroid coordinates, and width and height of bounding boxes, are utilized to pinpoint broiler mortality in each cell. Based on our previous testing, the YOLO V4 achieves on average 90% precision, recall, and F1 scores for detection, 4.8 mm root mean square error for localization, and 7 fps for processing speed when dealing with broiler mortality at various bird ages, light intensities, and bird body gestures. Therefore, it is suitable to serve our purpose of real-time detecting and localizing broiler mortality in this research.
The motivation for selecting the YOLO V4 is that it is a stable, mature, and efficient model and provides reliable and accurate detection results. The major function of this model serving part of the robotic navigation system is to localize dead birds. We also understand that there are more recent deep learning object detection models available, such as YOLO V7 that can be easily trained with custom datasets and replaces YOLO V4. The path planning for the removal robot is completed after the locations of broiler mortality are obtained in the coverage path.

Multitarget routing scheme
The dead broilers in the coverage path of a broiler barn are located as multiple targets collected by the removal robot. The robot should start from and return to the same point (entrance/exit gate of the barn), as addressed in Section 2.3. Meanwhile, multi-target path planning of the robot should have two major functions: obstacle avoidance and minimal travel distance regarding time and energy consumption. In those regards, multi-target path planning consists of two steps. The first step is point-to-point navigation, which generates the shortest collision-free path between target points. The second step is to navigate the robot to the targets in sequence, so as to minimize the total length of the trajectory.
To achieve the optimal visiting sequence of N targets, it is necessary to define the cost of path lengths between target points, that is, the shortest distance with obstacle avoidance between target points. Dijkstra' s algorithm is utilized to minimize the length of point-to-point navigations. However, Dijkstra' s algorithm needs to build a N × N adjacent matrix. The N is the total number of grids in a decomposed workspace (i.e., 456 for the current broiler barn) , resulting in highly expensive computation. Therefore, in light of the broiler layout, we design hub grids to reduce the computational effort. Note that the proposed hub-based multi-target routing (HMTR) scheme is applicable to all row-based environments for multi-target navigation, such as storage buildings, crops, power stations, etc.
The hub grid refers to the grid at the two ends of the feeding and drinking lines. For instance, in Figure 8, six hub grids are shown in the pink dashed line rectangle. It has the characteristics of unobstructed connection of targets in the corridor formed by the feeding and drinking lines, such as the hub grids connecting targets T 1 , T 2 , and T 3 with no collision. It also features a collision-free connection to targets outside the corridor, such as the hub grid that can connect target T 4 without collision. When the connecting lines between target points are blocked by obstacles, as shown by the black dotted lines in Figure 8, the corresponding hub grids are initially obtained for connection. The selection of the corresponding hub grids to the targets and is made by the total distance. Let F be the distance from the target point to the centerline of the hub grid on the left side and F be the distance from the target point to the centerline of the hub grid on the right side. If (F + F ) > (F + F ), the hub grid on the right side is selected. If (F + F ) ≤ (F + F ), the hub grid on the left side is selected.
To further optimize the path selection, we decompose the hub grid into nine ports that can be connected. When the port is blocked by a feeding or drinking line, it is regarded as inaccessible. The total path length between target points and is , which is the addition of the length of the hub bridge path and the length of the hub connection path shown in Figure 8. Dijkstra' s algorithm is utilized to minimize the length of point-to-point navigations. The trajectory is established between two points, which can be selected from each accessible port or the dead broilers. Each point is recursively connected with the other points, and the distances of connection lines passing through obstacles are assigned by an infinite number. As a result, point-to-point navigation with obstacles is excluded, and feasible solutions are retained. The shortest paths between each pair of points are selected from those feasible solutions. Each dead bird skips intermediate connections between adjacent grids and connect directly to the nearest port in the hub grid or to another dead bird, avoiding obstacles with the shortest traveling distance and improving computational efficiency.
The Miller-Tucker-Zemlin (MTZ) algorithm is then introduced for sequencing the navigation among the target points [37] . We define the connection variable as ℭ and path lengths between target points and as . The objective function is then given by To ensure that the result is a valid tour, several constraints must be added [Equation (13)] where V is the set of number of target points. The first set of equalities is a go-to constraint, which requires that each target point is visited only once and is different from the others. The second set of equalities is a come-from constraint, which requires that the departure of each target point also occurs once and is different from the other ones.
Equations (12) and (13) may form multiple enclosed paths for all target points, with the formation of subtours. The MTZ constraints are utilized to eliminate unnecessary subtours and ensure a single enclosed path with the shortest length [Equation (14)]. Each visited node is labeled, resulting in the uniqueness of each visit.
where U is the sequence of each target point visited and is the number of target points. When ℭ = 1, the equality holds (U + 1 = U ).
Based on the MTZ algorithm, we finally obtain a visiting sequence of dead broilers. The robot with that sequence starts and ends at the gate of the broiler barn with the shortest collision-free paths. Select corresponding left-side hub grids; end Select the best ports in the hub grids; Use Dijkstra algorithm to obtain end end end Use MTZ method to find the optimal visiting sequence.

SIMULATION AND COMPARATIVE STUDIES
Simulation and comparative studies were carried out to validate the effectiveness and efficiency of the proposed path planning methods of real-time autonomous mobile robots. The environments referred to are those in a typical broiler barn. The robot was parameterized as described in Section 2.1 based on commercialized poultry robots. These settings were taken to exemplify our proposed method and could be tailored according to specific applications. The proposed DCPP was initially compared with the zigzag and spiral methods. The start and end points for the broiler mortality robot were the same for the three methods, and our proposed method did not have redundant return paths. The total path length of the three methods was 912 m for the proposed method, 920 m for the zigzag method, and 917 m for the spiral method, respectively. The overall path based on the DCPP is depicted in Figure 9B.
With the assistance of DCPP, IPP is shown in Figure 9A and C. The cases are executed between two feeding/drinking lines, indicated as black bars on the left and right of the figures. The robot accounts for the overall DCPP direction and historical dead bird distribution data depicted as heat maps with red color areas indicating a higher possibility of broiler mortality appearance. Cyan areas indicate multiple branches subdivided by IPP. A path indicated as a red line designates a maximal information gain. Once the robot meets a random obstacle (indicated as the black object in Figure 10), such as welfare enrichment (e.g., perches, straw bales, and pecking stones) [38] , the information gain of IPP is optimized with the historical data and DCPP direction while avoiding the obstacle. Not only is the trajectory planned with previous data, but it is also updated with new data [ Figure 11], resulting in a real-time efficient path for the robot. In Figure 11, the trajectory changes from roaming between two obstacles to roaming atop the upper obstacle after the broiler mortality distribution data are updated based on the YOLO V4 dead bird detection and localization.
Limited by the working environment in the broiler barn, it is assumed that the detection range of the robot is 50 cm and the linear speed is 0.4 m/s. Through the traditional CCPP algorithm, such as BCD method, the path length of the CCPP is 16,408 m, which requires approximately 683 min to complete. However, DCPP with IPP is fine-tuned on the basis of the information gained on the paths generated by DCPP. In light of various information distribution in different environments, the final generated global trajectory length in each grid is only 12%-37% longer than DCPP. The final path length of the DCPP with IPP is 1182 m, which requires approximately 49 min to complete. Compared with the traditional CCPP, our proposed algorithm has a shorter path length and the travel time also meets the demands of broiler barns. The final results are outlined in Table 1.

Path planning of the removal robot
With the AI-based advancement of sensing techniques, locations of broiler mortality are obtained in an overall trajectory for the second robot. The HMTR receives the mortality location information and generates a collision-free route to reach the targets in a reasonable and efficient sequence so that the total traveling distance is minimized. To validate the adaptability and efficiency of our algorithms in various number of targets, three datasets were selected for simulation and comparative studies [39] . In each dataset, we iteratively performed 30 executions to compute the mean and standard deviation of path length. Table 2 summarizes the qualitative comparison results between the features of our algorithm and state-of-art models, such as genetic algorithm (GA), particle swarm optimization (PSO), self-organizing maps (SOM), and imperialist competitive algorithm (ICA). The SOM algorithm is similar to a typical artificial neural network algorithm, except it utilizes a competitive learning process instead of back-propagation that utilizes gradient descent. The ICA algorithm is a biologically inspired algorithm, which simulates the social-political process of imperialism and  imperialistic competition in humans.
Then, the reactive local navigator was utilized to generate real-time commands (e.g., acceleration, deceleration, and turning) for the robot arriving at a dead bird. Figure 12 shows three instances of grids for local navigation. Based on our simulation studies, using the dynamic window approach (DWA) local navigator, the robot successfully reached the existing dead birds and simultaneously avoided moving/still broilers. Robot running time and local trajectories could vary with grid locations, dead bird number in a grid, and distribution of live birds. As shown in Figure 12A, the two connected grids were between feeding and drinking lines surrounded  by birds, which were the most common cases in broiler barns, and two dead birds were distributed separately in the two grids. The trajectory of the robot was relatively straightforward due to less blockage of moving birds, in which the running time was 22-24 s for the left grid and 24-26 s for the right grid. As shown in Figure 12B, the connected grids were at the corner of the barn with two dead birds in the left grid and one dead bird in the right grid, resulting in a running time of 56-58 s for the left grid and 34-36 s for the right grid. As shown in Figure 12C, the robot needed to make a U-turn between the two connected grids to complete the path. Even though no dead birds were detected in the grids, the the live birds could still interfere with the robot due to their random distribution and unpredictable movements. Therefore, the running time varied for the two grids: 12-14 s for the upper grid and 19-21 s for the lower grid. In a broiler barn, the cases shown in Figure 12A took up the most proportion (420 grids), within which most contained no dead broilers, and the average robot running time was 20-28 s in a single grid. Therefore, our proposed methods have a reasonable running time in commercial-scale poultry barns, and they would be beneficial for rapidly detecting and collecting broiler mortality. Simulation and comparison studies demonstrate the effectiveness and efficiency of the proposed real-time robot safety-aware navigation.

CONCLUSION
A robotic system for detecting and collecting dead broilers in a barn is a promising direction for solving the issue of broiler mortality removal. Aiming at this vision, we developed an informative planning protocol-based multi-layer robot navigation system through detection and removal robots. The detection robot consists of DCPP for constructing the overall trajectory; IPP for detailing the trajectory based on historical data, DCPP direction, and obstacles; and a YOLO V4 dead bird detector for providing the precise locations of broiler mortality along the trajectory. The removal robot receives the mortality location information and plans an optimal ordered route by the HMTR scheme. The comparison and simulation results demonstrate the great potential of the proposed methods for robot navigation, being useful tools for supporting precision broiler management.
There are also many possible avenues for future work. A challenging extension is that we will integrate our algorithm to test the robots in the real scene of the broiler barn and develop a suitable human-robot interaction platform for effective control. Another interesting topic is the application of multiple robots to cooperatively search the environment to reduce the overall work time and simultaneously complete the functions of search, identification, and removal to improve efficiency.