{'fraction_non_alphanumeric': 0.03911665144269518, 'fraction_numerical': 0.008095570719825192, 'mean_word_length': 4.230351288056206, 'pattern_counts': {'":': 0, '<': 5, '<?xml version=': 0, '>': 15, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 4, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Covert, Low-Delay, Coded Message Passing in Mobile (IoT) Networks

We introduce a gossip-like protocol for covert message passing between Alice and Bob as they move in an area watched over by a warden Willie. The area hosts a multitude of Internet of (Battlefield) Things (Io\b{eta}T) objects. Alice and Bob perform random walks on a random regular graph. The Io\b{eta}T objects reside on the vertices of this graph, and some can serve as relays between Alice and Bob. The protocol starts with Alice splitting her message into small chunks, which she can covertly deposit to the relays she encounters. The protocol ends with Bob collecting the chunks. Alice may encode her data before the dissemination. Willie can either perform random walks as Alice and Bob do or conduct uniform surveillance of the area. In either case, he can only observe one relay at a time. We evaluate the system performance by the covertness probability and the message passing delay. In our protocol, Alice splits her message to increase the covertness probability and adds (coded) redundancy to reduce the transmission delay. The performance metrics depend on the graph, communications delay, and code parameters. We show that, in most scenarios, it is impossible to find the design parameters that simultaneously maximize the covertness probability and minimize the message delay.

hundred times more devices than current 4G environments, and one can potentially harness the resources expected to be brought in by smart (battlefield) devices in the future Internet of (Battlefield) Things (IoβT) environments. By exploiting these devices' storage and communication ability, Alice can covertly pass messages to Bob in a gossip-like manner as outlined below.
Alice and Bob communicate over a wide geographic area (e.g., battlefield or an occupied city) patrolled by a warden Willie. The area hosts a multitude of IoT objects capable of storing, sending, and receiving data. Alice splits her message into small chunks, which she can inconspicuously pass, one at a time, to IoT objects that appear in her proximity as she randomly moves through the area. We refer to such IoT objects as relays or helpers. Bob, who also randomly moves through the area, can then retrieve the stored data chunks. Because the IoT objects are distributed over a wide area, Willie can only periodically check if any of these objects is transmitting or receiving data.
The movements of Alice and Bob are modeled as random walks on graphs. Information gathering and dissemination on graphs is an interesting problem that naturally arises and is actively researched in many different contexts. Examples include: border control using unmanned aerial vehicles (UAVs) [11], measuring traffic, reporting road conditions and helping with emergency response using UAVs [12], monitoring the ocean [13], measuring air pollution [14], multi-agent systems [15], and more recently for timely exchange of information updates [16]. We consider two detection patterns of Willie: random patrolling and uniform surveillance. In the patrolling model, Willie performs random walks on graphs and can detect the communication when he happens to be on at the same relay as Alice or Bob. In the surveillance model, Willie scans graph nodes (e.g., while sitting in a control room). He can detect communication when he observes Alice or Bob.
Having to distribute and collect many chunks, as well as the unpredictability of mobility and availability of helpers can cause significant delays in our mobile information transfer.
To increase the persistence of information in the unstable environment, the agent may make the data chunks redundant by erasure correcting codes, requiring more data chunks to be distributed and collected. One would expect that would further increase the delay. However, that is not necessarily the case, and we will see that coding and some other forms of redundancy can, in fact, be used to reduce the delay, as previously shown to be the case in data download and straggler mitigation (see, e.g., [17]- [22] and references therein).
It may be helpful to the reader to consider our work in the arXiv:2108.03530v2 [cs.IT] 21 Dec 2021 context of the literature on throughput and delay in mobile adhoc communications. For example, [23] proposed a model for studying the throughput scaling of static ad hoc networks; [24] introduced the mobility into the communications model and assumed the source only transfers the data packet to a nearby relay which subsequently passes the packet to the destination. [25] introduced a random walk model for node mobility and analyzed the throughput and delay tradeoff, and [26] showed how coding improves this tradeoff, and [27] studied the throughput scaling of covert communication in ad-hoc networks introduced in [24]. Our work is different in multiple ways. It considers an IoβT specific system model, which includes different communication protocols and performance metrics. However, our approach to deriving communications delay and the techniques for reducing it should be of interest to the mobile ad-hoc communications community. The contributions of this paper are summarized as follows: 1) We first propose a gossip-like protocol for a covert dissemination/collection of message chunks in IoT environments. We analyze the dissemination and collection delay for two chunk transmission time models. For both models, our theoretical and numerical results show that introducing redundant IoT relays can reduce the dissemination time, and erasure coding of messages can reduce the collection time. 2) We then extend our analysis to covert communication scenarios. We introduce two warden models and derive/analyze the covertness probability for each. The theoretical and numerical results show that coding always reduces the covertness probability while splitting the message into smaller chunks may increase the covertness probability. 3) We numerically analyze delay vs. the covertness probability tradeoff. We conclude that the tradeoff is very different for different system parameters. In some scenarios, there exists an optimal code rate that maximizes the covertness probability and minimizes delay. However, in most scenarios, simultaneously maximizing the covertness probability and minimizing the communications delay is impossible. The paper is organized as follows: In Sec. II, we present the message passing model and two delay models. In Sec. III, we derive and analyze the expressions of dissemination/collection time for different delay models and numerically analyze the message passing delays. In Sec. IV, we propose two warden detection models and point out the tradeoff that exists between the message passing delay and covertness probability. In Sec. V, we derive and analyze the expressions of covertness probability for different detection models. In Sec. VI, we present some numerical results for the delay vs. covertness probability tradeoff. Conclusions are given in Sec. VII-5.

II. SYSTEM MODEL AND PROBLEM FORMULATION
We first describe the communication participants, their mobility, and message passing protocols and delay models. We then define two message passing performance metrics we will be studying. This section focuses the message passing delay.
The message passing covertness and the delay/covertness tradeoff are discussed in Sec. IV.

A. Communication Participants and their Mobility
There are three types of participants present within a geographical area (e.g., a city or a battlefield): a mobile source Alice, r static relays, a mobile receiver Bob. Alice's and Bob's mobility is modeled as a simple random walk over a mobility graph. (Sec. IV extends this model to include a warden Willie. ) We model the mobility graph as a random d-regular graph, that is, a graph selected uniformly at random from the set of all d-regular graphs on n vertices. The related literature (see, e.g., [25], [26]) uses rectangular grid graphs over a torus to study communications in (mobile) ad-hoc networks. We adopt the random regular graph model for the following reasons. 1) Since these graphs are locally trees with high probability [28], the random walks on such graphs are reasonable mobility models. 2) Although random regular graphs are more realistic than the grid on torus graph for mobility modeling, random walks on these graphs are fairly well understood. Thus, the existing mathematical results on this topic can be used and easily extended to our scenarios, allowing us to concentrate on the communications and covertness problems we aim to solve. Other mobility graphs will be used in future research, especially irregular graphs with a few high degree hubs.
The r relays are IoT objects residing on r vertices of the mobility graph. Alice has a message to pass to Bob. Instead of communicating with Bob directly, Alice uses the IoT objects (relays) to store pieces of her message, which Bob can subsequently retrieve. Because IoT objects have limited power, Alice and Bob can only communicate with a relay when they reach the vertex where the relay resides.

B. Communications Protocol & the Mobility Model
Alice's message has length m bits (symbols, packets). Because of the relay's storage constraints and to avoid long transmission time at a relay, she partitions the message into k data chunks each of length = m/k. By using an MDS code, she encodes the data chunks into n(≤ r) coded chunks (also of length ). Thus, Bob needs to collect any k out of n coded chunks to recover the message. An example of message partitioning and encoding, together with the mobility graph, is shown in Fig. 1. Here, Alice splits the message into k = 2 data chunks and encodes them into n = 3 coded chunks Message passing from Alice to Bob has two phases: the dissemination phase and the collection phase. In the dissemination phase, Alice transfers n coded chunks to the first n relays she encounters as she randomly walks through the graph. This model is similar to a classic predator-prey model, e.g., as analyzed in [28]. Fig. 2 shows an example. When she meets the first relay, she deposits the coded chunk M 1 to the relay. She then deposits M 2 to the second relay, and so on. The dissemination is complete when Alice deposits the last chunk. Fig. 2 shows the snapshots of Alice at the three relays. She may need to walk through several non-relay vertices to reach all the relays. Similarly, Bob recovers the message in Fig. 1. An example of message passing over a complete graph with with v = 7 vertices. Each vertex contains an IoT object. Four among them (yellow triangles) are relays and three (green disks) are not. Alice and Bob can communicate with any object but only disseminate/collect message chunks to/from the relays. Fig. 2. Alice needs to disseminate three coded chunks to any three out of four relays. Every time when she meets a relay, she stores one coded chunk, until all three coded chunks are disseminated. Each relay can only store one coded chunk. the collection phase by collecting k coded chunks from the n relays as he randomly walks through the graph.

C. Message Chunk Passing Time
The time to pass a chunk between Alice (or Bob) and a relay has two components. The first is the time Alice (or Bob) needs to spend randomly walking to meet a relay. The second is the transmission time of a data chunk between Alice/Bob and a relay. We refer to Alice's move from a vertex to one of its neighbors as one step. The time to take a step is, in general, a random variable η. We consider the following two chunk passing time models: Model 1 -Constant Transmission Time: In this classic model for random walks (see, e.g., [28], [29] and references therein), the chunk passing time is measured in the number of steps Alice/Bob needs to make to encounter a relay. It is applicable here under the following circumstances: 1) the time of a step η is a constant, say 1 and 2) the chunks are sufficiently small so that their transmission time can be neglected. Model 2 -Random Transmission Time: In this general model, the step times are independent and identically distributed (i.i.d.) random variables. The transmission time of a data chunk between Alice/Bob and a relay follows a shifted exponential distribution whose shift is proportional to the length of a chunk and whose tail accounts for various disturbances (noise) in the system.

D. Covert Message Passing
The covert message passing is defined as Alice successfully passing a message to Bob through some relays without Willie's detection. We consider two detection patterns of Willie: random patrolling and uniform surveillance. In the patrolling model, Willie performs random walks on graphs and can detect the communication when he happens to be on at the same relay as Alice or Bob. In the surveillance model, Willie scans graph nodes (e.g., while sitting in a control room). He can detect communication when he observes Alice or Bob. The details of the detection models are given in Sec. IV.

E. Performance Metrics and Problem Formulation
Alice's goal is to covertly and quickly pass the message to Bob. Thus, the performance metrics of interest are covertness probability (P c ), the expected dissemination time (E[T A ]) of n coded chunks by Alice, the expected collection time (E[T B ]) of k coded chunks by Bob, and the expected message passing delay (E[T A+B ]) (dissemination plus collection). We evaluate the above metrics in terms of the design parameters k and n, where k/n is the code rate. Our goal is to find the optimal k and n that maximize P c , and minimize E[T A ], E[T B ], and E[T A+B ]. In the following section, we will derive the formulas for each metric and analyze the optimal k and n. The covertness probability will be addressed in Sec. IV.
Recall that a message of length m data bits, and is split into k data chunks. Applying an [n, k] MDS code, k data chunks are encoded into n coded chunks. The length of each data/coded chunk is = m/k bits. Therefore, Alice needs to meet n relays to deposit her coded chunks. We denote by S A the random number of steps Alice needs to make to meet n out of r relays. Bob needs to meet k relays with coded chunks. We denote by S B the random number of steps Bob needs to make to meet k out of n relays storing coded chunks.

F. Parameters and Notation
v -number vertices in the mobility graph d -mobility graph vertex degree r -number of relays in the system m -message (data) length in bits k -number of message (data) chunks n -number of coded chunks k/n -code rate -length of a data (or coded) chunk η -random walking time between two vertices TA -random dissemination time of n coded chunks TB -random collection time of k coded chunks TA+B -random message passing time SA -random # of Alice's steps to meet n relays SB -random # of Bob's steps to meet k relays

A. Preliminary Reasoning
Message passing delay includes dissemination and the collection time. It is the the time during which Alice and Bob communications with relays could be discovered by Willie. Observe that the message passing delay is not the time that the message spends in the system from the beginning of Alice's dissemination to the end of Bob's collection. That time depends on the starting times of the dissemination and collection, and is beyond the scope of this paper.
The message passing delay depends on how many steps Alice (Bob) needs to make to disseminate (collect) the coded chunks.To understand the message passing delay dependencies on the system and design parameters, we first consider a special case when the mobility graph is a complete graph. Here, Alice needs to disseminate n coded chunks to r relays residing on a v-vertex complete graph. Her first chunk can be deposited on any of the r relays. In a single step, Alice arrives at a relay with the probability r/v, and thus she needs to make on average v/r steps to find a relay to deposit her first chunk. For depositing her second chunk, Alice needs to arrive to one of the remaining r −1 relays, which happens in a single step with probability (r − 1)/v. Thus, she has to make another v/(r−1) steps on average to deposit her second chunk. Therefore, to deposit her first two chunks, Alice will make v r + v r−1 steps on average. Following this reasoning, we see that for n chunks, Alice needs to makes on average v(H r − H r−n ) steps, where H r = r i=1 1/i is the r-th harmonic number. We often use the approximation H n = log n + γ + O(n −1 ), where γ = 0.577 is Euler's constant. Bob needs to collect k chunks from n relays storing coded chunks. Therefore, Bob needs to make on average v(H n − H n−k ) steps.
The above reasoning does not extend to general graphs. However, reference [28] provides useful results for large, random regular graphs (which are good mobility graphs models). We adapt the findings of [28] to our setting, and get the following results. Let S be the number of steps that the source (or collector) needs to make to meet a relay. When we randomly choose a graph from the set of all d-regular graphs with v vertices, with high probability, 1) the expected number of steps is and 2) the probability that the source meets a relay P meet is where X ∼ Z Y means lim Z→∞ X/Y = 1, and θ d = d−1 d−2 . We can now find the the expected message passing delay. According to the definition of T A+B , we know that its expec- The dissemination time T A is the sum of n message chunk passing times (discussed in Sec. II-C). For the constant transmission time model with the step time η = 1, T A is equal to the random number of steps S A that Alice needs to make to meet n out of r relays to deposit her n coded chunks. Therefore, the expected dissemination Similarly, the collection time T B is equivalent to the total number of steps S B that Bob needs to make to meet k out of n relays to collect k coded chunks. Therefore, the expected dissemination time is For the random transmission time model, the dissemination time T A (collection time T B ) is again equal to the sum of n (k) chunk passing times. Recall that the chunk transmission time can not be neglected in this model, and it follows a shifted exponential distribution. Thus the calculations of E[T A ] and E[T B ] are more complicated and will be discussed later.
In the following, we focus on the delay analysis of a random regular graph. We will find the expression of message passing delay by deriving the dissemination time and collection time separately under two different delay models.

B. Constant Transmission Time
Under the constant transmission time model, the message passing delay T A+B = S A + S B , where S A and S B are the number of steps that the source and collector need to spend to meet enough relays.
1) Dissemination Time: From the above discussion, it follows that in a d-regular graph with v vertices, the source needs to make on average θ d v r steps to disseminate the first coded chunk. After the first dissemination, the number of available relays reduces to r − 1, and then the source needs to spend on average θ d v r−1 steps to disseminate the second chunk. Finally, we can get the expected number of steps to disseminate n coded chunks It is obvious that E[S A ] decreases with increasing r and increases with n. Since n = ϕr for some ϕ ∈ (0, 1), it is For a scenario without redundant relays, the number of relays r is equal to the number of coded chunks n. Thus, the expected number of steps to disseminate n coded chunks is 2) Collection Time: The collector needs to collect any k coded chunks from n relays that store the chunks. Similarly, we can get the expected number of steps to collect any k chunks It is obvious that E[S B ] decreases with increasing n and increases with k. Since k = ξn for some ξ ∈ (0, 1), it is For a scenario without coding, the code rate k/n = 1, namely, k = n. Thus, the expected number of steps to collect n data chunks is 3) Message Passing Delay: The message passing delay is the sum of dissemination time and collection time. Since both E[S A ] and E[S B ] are positive, the following asymptotic equivalence holds: We know that E[T A+B ] increases with k. Namely, when the number of coded chunks n is given, E[T A+B ] reaches minimum at k = 1. However, since the IoT devices have limited storage, we sometimes have to split the original message into smaller chunks to store in the relays. Therefore, it is important to study when k is given, what is the value of n can minimize E[T A+B ]. We find some results in Theorem 1.
Theorem 1. By using the asymptotic equivalence (3), the expected message passing delay E[T A+B ] reaches the minimum at n = √ rk + k − 1 given r and k. Notice that if the above value is not an integer, the optimal n is √ rk Proof. When k and r are given, Observe that for a complete graph with v vertices, the expression for message passing delay becomes T A+B = v(H r + H n − H r−n − H n−k ), as previously derived.
Numerical Analysis: In Fig. 3, we evaluate the expected message passing delay E[T A+B ] vs. the number of coded chunks n for both approximation and exact result. We consider a regular graph with 100 vertices and the degree is 5. The approximation is calculated from the expression of E[T A+B ] given in (3), and the exact result is an average of 1000 sampled delay values. Some observations are made from the figure: when n is given, E[T A+B ] increases with k. For example, when n = 7, the case "k = 2" gives the minimum E[T A+B ]. When n is large (e.g., n = 10), the gaps between these three cases are small. These observations are consistent with the theoretical analysis for k. We also observe that when k is given, E[T A+B ] always reaches the minimum at n > k. For example, when k = 4, the optimal n is 6 and the code rate k/n = 2/3. We conclude that introducing proper data redundancy can reduce the message passing delay. This observation is consistent with the result in Theorem 1. Besides, we observe that for each k, the approximation is very close  3)). This is a regular graph with 100 vertices and the degree is 5. The number of relays is r = 10. Introducing proper data redundancy can reduce the message passing delay and the approximation is close to the exact result.
to the exact result. It confirms that (3) is good enough to approximate the expected message passing delay.

C. Random Transmission Time
Under the random transmission time model, both the source and collector need to spend some walking time (totally η 1 + ... + η S ) to meet a relay, and then they need to spend the message chunk passing time (defined as t t ) to delivery and collect the chunk. According to Subsection II-C, t t follows a shifted exponential distribution S-Exp(∆, λ), where ∆ = .
1) Dissemination Time: The source needs to disseminate n coded chunks to r(≥ n) relays. When the source randomly walks on a d-regular graph with v vertices, the probability that it meets a relay is r θ d v according to (2). After the source deposits the first chunk in one of the r relays, the second chunk can only be stored in one of the remaining r − 1 relays. The probability of meeting an unoccupied relay decreases as the number of occupied relays grows. Therefore, in order to get the dissemination time T A , we need to find the time T i for the source to disseminate the i th (i = {1, 2, . . . , n}) coded chunk.
Lemma 1. For the random transmission time model, the time T i for the source to disseminate the i th coded chunk to any one of r − i + 1 relays is (4) Where S is the number of steps the source spends to meet a relay, and p r−i+1 ∼ v r−i+1 θ d v is the probability that the source meets any one of r − i + 1 relays. Then we have Proof. Let p = p r−i+1 , we get the expectation of T i as follows: pr−i+1 . Using Lemma 1, we can get the expected total dissemination time E [T A ] in the following theorem.
Theorem 2. The expected dissemination time for the source to transmit all n coded chunks to any n out of r relays is . Notice that η is determined by the distance between two vertices and the speed of the source/collector. To study these two parameters is not the purpose of this paper. Therefore, we will directly assign a value to E[η]. Therefore, from Theorem 2, we see that E [T A ] increases with n and decreases with increasing k. Since r = ϕn and k = ξn for some ϕ, ξ ∈ (0, 1), it is not hard to see For a scenario without redundant relays, the number of relays r is equal to the number of coded chunks n. Thus, the expected dissemination time is 2) Collection Time: The collector needs to collect at least k coded chunks to recover the message. Since there are only n(≤ r) relays on the graph store the coded chunks, the probability that the collector meets a relay with a coded chunk is n θ d v . After the collector retrieves the first chunk in one of the n relays, the second chunk can only be retrieved in one of the remaining n − 1 relays. Therefore, similar to the dissemination time, we find the expected collection time E [T B ] in the following corollary.
Corollary 1. The expected collection time for the collector to retrieve any k chunks from n relays is The above result holds by applying the similar proofs of Lemma 1 and Theorem 2.
From Corollary 1, we see that E [T B ] decreases with increasing n and increases with k. Since k = ξn for some ϕ, ξ ∈ (0, 1), it is not hard to see For a scenario without coding, the code rate k/n = 1, namely, k = n. Thus, the expected collection time is 3) Message Passing Delay: The message passing delay is the sum of the dissemination time and collection time, and its expectation is in Corollary 2.
Corollary 2. For the random transmission time model, the expected message passing delay is: From the conclusions of the dissemination time and the collection time, we see that there should be an optimal n and an optimal k which minimize the E [T A+B ]. Assume k is given, we find the optimal n in the following theorem.
Theorem 3. For the random transmission time model, when k is given, the optimal n appear in the range [k, . Since λ, m, k > 0, the former terms 1 λ + m k > 0. According to the proof of Theorem 1, we know that the latter term is larger than 0 when n > √ rk + k − 1, and smaller than 0 when n < √ rk + k − 1. Therefore, the optimal n, as an integer, must appear in the range [k, From Theorem 3, we know that when 1 To analyze the optimal k, we assume n is given. From (7), we see that k appears in the terms mn k + k λ − θ d vE [η] H n−k , where mn k decreases with increasing k, and k λ −θ d vE [η] H n−k increases with k. Therefore, the optimal k changes with the values of system parameters, e.g., λ, d, v, η and m.
Notice that for a complete graph with v vertices, we find the expression of message passing delay is The results in Theorem 3 still hold.
Numerical Analysis: In Fig. 4, we evaluate the expected message passing delay E[T A+B ] vs. the number of coded chunks n for both approximation and exact result. We consider a regular graph with 100 vertices and the degree is 5. The message chunk passing time t t follows S-Exp( , λ), where = 100/k is the length of a chunk, λ = 1 is the rate parameter. By sampling the shifted exponential distribution, we can get a message passing delay value. The exact result is an average of 1000 sampled delay values. The approximation is calculated from the expression of E[T A+B ] given in (7). Some observations are made from the figure: when k is given, E[T A+B ] still reaches the minimum at n > k. Which indicates that introducing proper data redundancy can reduce the message passing delay. However, comparing to Fig. 3, the optimal code rate k/n in Fig. 4 is more close to 1. For example, considering the case "k = 4", the optimal code  7)). This is a regular graph with 100 vertices and the degree is 5. The number of relays is r = 10 and the message chunk passing time follows S-Exp(100/k, 1). Introducing proper data redundancy can reduce the message passing delay and the approximation is close to the exact result. rates in Fig. 3 and Fig. 4 are respectively 2/3 and 4/5. This observation validates the result in Theorem 3 that when 1 λ + m k = 1 + 100/k is close to θ d v = 400/3, the optimal n appears in the range [1, . We also observe that when n is given, E[T A+B ] no longer increases with k. For example, when n = 6, the case "k = 4" has a smaller delay than the case "k = 2". Although our theoretical analysis also shows this result, we can not describe how the optimal k changes due to there are too many parameters can affect the result. Besides, we observe that the approximation is very close to the exact result. It confirms that (7) is good enough to approximate the expected message passing delay.

D. Comparisons and Conclusions
In Table I, we compare different scenarios with or without redundant relays (RR) and coding. We conclude that redundant relays can help to decrease the dissemination time and coding can decrease the collection time. For example, considering the constant transmission time model, with the help of redundant relays and coding, the average dissemination and collection time decrease from O(v log n) to O(v), respectively.
In Table II, we summarize the results of the expected message passing delay in both constant transmission time and random transmission time models. In the constant transmission time model, we deduce the optimal k and n from the expression of E[T A+B ]. However, in the random transmission time model, the exact values of optimal k and n are hard to deduce from the expression of E[T A+B ].

E. Source and Collector's Starting Time
In the previous subsections, we only consider the message passing delay which defined as the sum of the dissemination time and collection time. In practice, we should also look into the source and collector's dynamics on when to start each process. Thus, the overall message passing time, defined as the time from the beginning of the source's dissemination to the end of the collector's collection, is also an important performance metric for the message passing system.
To analyze the overall message passing time, in general, two scenarios should be considered: 1) the collector starts collecting chunks after the dissemination. Thus, the overall message passing time is larger than the message passing delay, since there will be some intermediate time between dissemination and collection. Nevertheless, the previous conclusions also hold for the overall message passing time analysis, because the intermediate time is unrelated to the dissemination and collection times. 2) The collector starts collecting chunks during the dissemination. Thus, the overall message passing time is smaller than the message passing delay and the previous conclusions do not always hold for the overall message passing time analysis. This is an interest problem that needs to be studied in the future.

F. Multiple Sources and Collectors with Network Coding for Further Reduction of Delay
With the help of redundant relays and coding, we reduced the dissemination and collection time for both the constant and random transmission time models. However, the effectiveness of redundant relays and coding is limited. For example, we can not reduce the average dissemination time beyond O(v) under the constant transmission time model. Nevertheless, we can further reduce the delay by introducing multiple sources and collectors. We outline the main ideas below and leave the details of this problem for a follow-up study.
Based on the results of [29], we know that w random walks on a complete graph or a d-regular graph achieve O(w) reduction of the single walk graph cover time. (This is true for some other graphs [30] as well.) Thus multiple sources will reach the relays faster than a single source but need to disseminate different message chunks to reduce the message passing delay. Thus, each source must know which chunks have been disseminated by the other sources. Such assumption is impractical and inadequate for covert communications scenarios. Without this assumption, having multiple sources and collectors may even worsen the delay. To see that, consider two sources that disseminate a message of 2 data chunks to 4 relays by randomly selecting a chunk each time they encounter a relay. If both sources disseminate only one data chunk, the dissemination time is significantly shorter than when one source disseminates 2 data chunks. However, the two sources will disseminate the same chunk with a probability 0.5. If both sources disseminate 2 data chunks, the dissemination time is larger than the one source scenario.
The sources can apply various strategies to ensure that they disseminate different chunks. For example, if there are two sources, one can disseminate the even chunks and the other odd chunks. However, we will have higher benefits if we do not fix the number of chunks that each source has to disseminate as long as the sum of the disseminated chunks is n. Moreover, the splitting strategy does not reduce the collection delay. We may use network coding to improve the

E[T A+B ]
Optimal k (given n) Optimal n (given k) multiple sources/collectors and reduce the collection delay. In this way, instead of sending the data chunks to the relays, the sources will send a random linear combination of the data chunks.
For the most general scenario, the sources may not even be able to agree or know which chunks are disseminated before/during the dissemination. Here, using network coding is essential. Each time a source encounters a relay, it randomly generates a coded chunk as a linear combination of k data chunks. Thus, the sources only need to disseminate n coded chunks together. In the collection phase, the collectors need to collect totally k out of n chunks, where k is just slightly larger than or equal to k. Then, when the field size is sufficiently large, the k data chunks can be decoded from k coded chunks with high probability. Using fountain codes, e.g., LT [31] or Raptor codes [32], instead of random network codes can simplify decoding.

IV. COVERT MESSAGE PASSING
We now consider message passing where in addition to Alice, Bob, and relays, there is another communication participant, Willie the warden. We are interested in the probability that the message passing from Alice and Bob is hidden from Willie who has certain mobility and detection capabilities.
The transmission stays covert only when Alice successfully passes a message to Bob through some relays without being detected by Willie. Although covert communication has been studied in many papers, covert message passing in mobile networks is recently proposed. Therefore, there is no model on how the warden detects. In the following, we provide two possible models.

A. Two Warden Detection Models
Random Patrolling Model: In this model, see Fig. 5 (left), the warden Willie walks randomly on the same graph with Alice and Bob. We assume that all mobile participants are moving synchronously. To establish that Alice and Bob are communicating, Willie has to 1) meet one of them at a relay and 2) detect the transmission to the relay is taking place before it was over. The more time Willie has to observe a chunk transmission, the higher his probability of detection will be. The detection probability is thus an increasing function of the chunk length . However, decreasing the chunk length will result in having to pass more chunks, which in turn gives Willie more (m/ ) opportunities to observe a transmission. Uniform Surveillance Model: In this model, we base covertness on the assumption that the warden Willie can monitor part of the vertices for some given time. A straightforward and informal way to visualize this model is to imagine that the warden is stationed somewhere "in the middle" of the graph 1 , on top of a lighthouse, see Fig. 5 (right). This way, he can only check the part where the lighthouse sheds its light and can not see what is happening behind him. We can also imagine the warden applies a Round-Robin protocol to check each vertex of the graph. Thus, he can monitor vertices uniformly.
To formalize this model, we assume that Alice and Bob transmit data to relays without implementing any covertness scheme. Therefore, if the warden happens to check a graph vertex while the data chunk transmission is taking place, he will detect it with probability 1. We further assume that when Alice or Bob starts transmitting on a relay, the warden's time of arrival at this relay follows a uniform distribution. Thus, if the warden monitors the relay during the transmission, he will detect it; otherwise, he will not. This model was first proposed in paper [1] which provided the analysis for a complete graph.
B. Performance Metrics 1) Covertness Probability: Covertness probability is defined as the probability that Alice transmits a message to Bob without being detected by Willie. For example, assume that the message has 2 data chunks, Alice needs to transmit 2 times to 2 relays and Bob also needs 2 times to collect the chunks. If during each time, Willie will detect the transmission with a probability P d , the covertness probability is P c = (1 − P d ) 4 . Notice that when Willie detects the transmission, it does not mean he will get the content of the message. The message may be camouflaged as noise to avoid detection. However, this is another covert communication problem and will not be studied in this paper.
2) Covertness vs. Delay Tradeoff: To optimize the covertness probability, we will also consider using splitting and data redundancy. From the definition of covertness probability, we know that although splitting increases the number of chances that Willie detects, it also decreases the detection probability P d for each chance (data chunk is smaller than the message). Therefore, it is hard to tell whether splitting decreases the covertness probability. Meanwhile, it is obvious that introducing data redundancy decreases the covertness probability. Therefore, revisit our message passing delay models, the tradeoff between the covertness probability and delay becomes apparent here.
On the one hand, if Alice delivers the data chunks without data redundancy to relays, then the probability of detection is small. This happens because the chance that Willie "sees" her is inversely proportional to the number of nodes. On the other hand, the delay is increased because Bob will have to visit many nodes until he meets all the relays that hold Alice's data chunks. At the other side of the spectrum, if Alice encodes the data chunks and delivers the coded chunks to more relays, then it will take Bob fewer steps to retrieve it. Thus, the message passing delay may reduce (see conclusions in Sec. III). However, the probability that they are caught increases significantly because of the more times that Alice has to deliver to the relays. The parameters β, t t and t a are the system parameters. P d and P c are the performance metrics.

V. COVERTNESS PROBABILITY ANALYSIS
In Sec. IV-B1, we introduced the covertness probability P c and provided an example to calculate P c given the transmission detection probability P d . In practice, P d is not always a constant. The warden Willie will detect the transmission with a higher probability when he "sees" the transmission for a longer time. In another word, P d increases with the length of a chunk . In this section, we provide the expression of P d as a function of for two different warden models, respectively. Meanwhile, we provide the general expression of P c .
A. Transmission Detection Probability 1) Random Patrolling Model: In this model, β wardens, a source, and a collector walk randomly on a regular graph. As we introduced in Sec. IV-A, the warden firstly needs to meet the source or collector, and then detects the transmission. For a d-regular graph with v vertices, according to (1), the probability that the warden meets the source/collector at a relay is β θ d v . After meeting the source or collector, we consider two scenarios for the warden: a) the warden will detect the transmission immediately. Thus, the detection probability is The above formula shows that P d only relates to the degree of graph d and the number of wardens β, thus we consider the detection probability as a constant. b) The warden will fail to detect with some probability. In practice, the warden can not always detect the transmission successfully for some reasons, e.g., the source tries to hide the message, the noise of the detection channel, etc. It is intuitively to imagine that the longer time for the source or collector to transmit the coded chunk, the higher probability the warden detects successfully. Since the transmission time relates to the length of the coded chunk, here, we simply assume the detection probability is a linear function of .
Since = m k , we see that P d is a function of k, and it decreases as k increases.
2) Uniform Surveillance Model: In this model, when a source or a collector arrives at a relay and starts transmitting the data chunk, the warden will arrive (monitor) at this relay following a uniform distribution U (0, W ). As we introduced in Sec. IV-A, whether the warden will detect the transmission successfully depends on the warden's arrival time t a and the source/collector's message chunk transmission time t t . We consider the warden's arrival time t a follows a uniform distribution, i.e., t a ∼ U (0, W ). And the message chunk passing time t t follows a shifted exponential distribution i.e., t t ∼ S-Exp(∆, λ) (the tail is given as Pr{t t > x} = e −λ(tt−∆) for t t > ∆). Where ∆ = indicates the time to transmit a chunk and the exponential tail is some inherent additive system randomness at each relay, which does not depend on the chunk length . Thus, the detection probability P d is given by the following theorem: For the uniform surveillance model, the probability that the warden arrives during the transmission (i.e., detects the transmission) is Proof. Since t t ∼ S-Exp( , λ), it is obvious that t t ≥ . We assume the warden's arrival time is t a ∼ U (0, W ), then we have t a ≤ W . If W < , the warden will definitely arrive before the transmission is done, the detection probability is P d = 1.
If W > , we calculate the detection probability as follows:

B. Covertness Probability
The communication between the source and collector stays covert only when all the coded chunk transmissions are undetected. Recall that the source needs to disseminate the n coded chunks and the collector needs to collect k coded chunks. Therefore, the total number of coded chunk transmissions is n + k and the covertness probability is When k is given, since P d and n are independent and 0 ≤ P d ≤ 1, the covertness probability P c decreases with increasing n. Since P d is a function of and = m k , P c is a function of k. Thus, when n is given, we need further analyze the optimal k for each detection model.
For the random patrolling model, P d is a constant under the worst-case (see (8)). Otherwise, P d increases linearly with (see (9)). Thus, we can easily get the expression of P c by substituting (8) or (9) to (11). From the expressions, we find the maximum of the covertness probability in Theorem 5.
Theorem 5. For the random patrolling model, given the number of coded chunks n, the covertness probability P c changes as follows: 1) Under the worst-case, P d = β θ d v is a constant. Thus, for a given n, P c decreases with increasing k, which means P c reaches the maximum at k = 1.
2) Otherwise, P d (k) = β kθ d v is a function of k. Thus, P c increases with k, which means P c reaches the maximum at k = n.
Proof. For property 1), since P d is a constant and 0 ≤ 1 − P d < 1, it is obvious that P c decreases with k. Since k ≥ 1 is an integer, the maximum covertness probability is at k = 1, i.e., P c = (1 − P d ) n+1 .
For property 2), we know 1 ≤ k ≤ n is an integer. Let a ∈ [1, n) be an integer. To prove P c (k) increases with k, we only need to show P c (k = a + 1) > P c (k = a) for all a.
For the uniform surveillance model, since P d is a function of k, P c is also a function of k. From Theorem 4, the term W (= m kW ) decreases as k increases, and the term − e −λ(W − ) λW (= − e −λ(W −m/k) λW ) increases with k. When λ is sufficiently large, the former term is much larger than the latter term. Thus, P d also decreases as k increases. Since P c decreases as k increases when P d is given, there exists a tradeoff for k to maximize P c . When λ is sufficiently small, the former term is smaller than the latter term. Thus, P d increases with k, which leads to P c reaches its maximum at k = 1.

VI. DELAY VS. COVERTNESS PROBABILITY TRADEOFFS
In the previous sections, we know that introducing data redundancy reduces both the message passing delay and the covertness probability. Thus, it is important to study how much redundancy affects the delay and probability tradeoffs.

A. Constant Transmission Time vs. Random Patrolling
Since both the random patrolling model and the constant transmission time model do not relate to the message chunk passing time, we combine these two models to analyze the tradeoff between the covertness probability P c and the expected message passing delay E[T A+B ].
In Fig. 6, we evaluate (3) and (11) to see the tradeoff between the detection probability and the transmission delay for the worst case warden's detection probability P d = β θ d v . We consider a regular graph with v = 100 vertices and the degree is d = 5. There are 15 relays distributed uniformly on vertices of the graph. 10 wardens, 1 source and 1 collector  11)) as n increases from 1 to 10. We consider the worst-case, i.e., the detection probability is a constant (cf. (8)). This is a regular graph with 100 vertices and the degree is 5. The number of wardens is β = 10 and the number of relays is r = 15. There exists an (n, k) which simultaneously maximizes Pc and minimizes E[T A+B ].
walk randomly on the graph. We evaluate P c vs. E[T A+B ] as the number of coded chunks n increases from 1 to 10. Each point in the figure is a different case with different values of (n, k). Two different strategies are considered: minimum delay and maximum probability. For the minimum delay, we firstly find the optimal k which minimizes E[T A+B ] given each n. Then we calculate P c by using the same k. For the maximum probability, on the contrary, we firstly find the optimal k for P c given each n, and then calculate E[T A+B ]. From Fig. 6, we observe that the results for both strategies coincide with each other. It means that the optimal k simultaneously maximizes P c and minimizes E[T A+B ]. We also observe that P c decreases with increasing n and E[T A+B ] reaches the minimum at n = 4. These observations are consistent with Theorems 1 and 5. Finally, we conclude that k = 1, i.e., no splitting, is the overall optimal strategy. Replication (n > 1 and k = 1) can reduce the transmission delay, but it also decreases the covertness probability.
In Fig. 7, we consider the warden's detection probability increases linearly with the length of data chunk , i.e., P d = β The same regular graph is adopted from Fig. 6. We evaluate P c vs. E[T A+B ] as n increases from 1 to 10. Four different strategies are considered: minimum delay, maximum probability, "k = 2" and "k = n − 1". For the minimum delay, we have the same observations as them in Fig. 6. This is because the expression of E[T A+B ] is unchanged, and it still reaches minimum at (n, k) = (4, 1). For the maximum probability, P c reaches minimum at k = n, which means splitting is optimal. It is obvious that the curves of the minimum delay and the maximum probability are far from each other. Therefore, we can not simultaneously decrease the message passing delay and increase the covertness probability. In the figure, we also see the results for "k = 2" and "k = n − 1" strategies. When we have a minimum requirement for P c or E[T A+B ], then k = 2 or k = n − 1  11)) as n increases from 1 to 10. We consider the detection probability is a function of (cf. 9). This is a regular graph with 100 vertices and the degree is 5. The number of wardens is β = 10 and the number of relays is r = 15. It is impossible to reach the maximum Pc and the minimum E[T A+B ] simultaneously. strategies may provide a better performance. For example, if we require P c > 0.8, then the case (n, k) = (4, 2) gives a relatively smaller E[T A+B ].

B. Random Transmission Time vs. Uniform Surveillance
Since both the uniform surveillance detection model and the random transmission time model relate to the message chunk passing time, we combine these two models to analyze the tradeoff between the covertness probability P c and the expected message passing delay E[T A+B ].
In Fig. 8, we evaluate (7), (10) and (11) to see the tradeoff between the detection probability and the expected message passing delay. The same regular graph is adopted from Fig. 6. The graph on the left has a message chunk passing time t t ∼ S-Exp(10/k, 1) and the graph on the right has a message chunk passing time t t ∼ S-Exp(10/k, 0.2). The warden's arrival time follows U (0, 30). We evaluate P c vs. E[T A+B ] as n increases from 1 to 10. Each point in the figure is a different case with a different value of (n, k). Similarly, the minimum delay and maximum probability strategies are considered.
The left subfigure shows that given the number of coded chunks n, minimum delay and maximum probability strategies have very different optimal k values. For minimum delay, the optimal k is small (i.e., 1 or 2); For maximum probability, the optimal k is equal to n. Therefore, we conclude that it is impossible to simultaneously increase the covertness probability and reduce the message passing delay. In practice, the appropriate (n, k) is also decided by the requirements for the performance metrics, e.g., the system requires P c > 0.7 or E[T A+B ] < 170. The right subfigure shows that given the number of coded chunks n, when n is small (e.g., n < 5), minimum delay and maximum probability strategies have very different optimal k values; When n is large (e.g., n > 6), they have very closed optimal k values. When n > 6, the optimal k for minimum delay is equal to 2 and the optimal k for  10) and (11)) as n increases from 1 to 10. The left subfigure has a message chunk passing time tt ∼ S-Exp(10/k, 1) and the right subfigure has the tt ∼ S-Exp(10/k, 0.2). This is a regular graph with 100 vertices and the degree is 5. The number of relays is r = 10. The warden's arrival time follows U (0, 100). It is impossible to reach maximum Pc and minimum E[T A+B ] simultaneously. Sacrifice some covertness probability may bring a significant improvement to the message passing delay. maximum probability is equal to 5. Therefore, we conclude that as the variance of t t increases (1/λ 2 becomes smaller), the maximum probability and minimum delay strategies will finally be the same. The conclusion indicates that when λ is sufficiently small, we can simultaneously increase the covertness probability and reduce the message passing delay.
From both subfigures, we see that the minimum delay strategy leads to similar results, but the maximum probability strategy leads to very different results. This is because P c is sensitive to the value of λ, but E[T A+B ] is not. We analyzed how P c changes with λ in Sec. V-B. According to the expression of E[T A+B ] given in (7), although decreasing λ from 1 to 0.2 can increase the former term n+k λ , the latter term θ d v(H r + H n − H r−n − H n−k ) is far larger than the former. Thus, the results will not change much with λ. Notice that both P c and E[T A+B ] reach the optimal values when n and k are small. However, that may not be the case when the message length m is sufficiently large. Recall that the detection probability P d = 1 (in Theorem 4) when > W , then the covertness probability P c = 0. Since = m k , when m W (e.g., m = 3W ), a small (n, k) value (e.g., (4, 2)) leads to P c = 0. Therefore, it is necessary to study how the P c and E[T A+B ] trade-off changes when n and k are large in Fig. 8.

VII. CONCLUSIONS AND FUTURE WORK
We introduced and studied a gossip-like protocol for covert passing messages between Alice and Bob as they move in an area hosting a multitude of IoβT objects. Alice and Bob perform random walks on random regular graphs. The IoβT objects reside on the vertices of this graph, and some can serve as relays between Alice and Bob. In our protocol, Alice splits her message into small chunks, which she can covertly deposit to the relays she encounters. Afterward, Bob collects the chunks. Alice may encode her data before the dissemination. The area where the message passing takes place is watched over by a warden Willie. Willie can either perform random walks as Alice and Bob do or conduct uniform surveillance of the area. In either case, he can only observe one relay at a time. We evaluated the system performance by the covertness probability and the message passing delay. These performance metrics depend on the graph, communications delay, and code parameters. We showed that, in most scenarios, it is impossible to choose the design parameters that maximize the covertness probability and minimize the message delay simultaneously.
This work sets the stage for many problems of interest to be studied in the future. We briefly describe five directions of immediate interest.
1) Reducing Delay with Multiple Sources and Collectors: According to Section III-F, although many random walks are faster than one [29], simply introducing multiple sources and collectors may not reduce the dissemination and collection time significantly. Fountain codes need further study as a possible way to improve the performance.
2) Computing the Overall Message Passing Time: As we discussed in Section III-E, the overall time the message spends in the system depends on when the collection and dissemination start. For example, Alice and Bob can start their walks each day at some specified time, or collecting can start before the dissemination is over. Extending this work to include the dynamics on when to start each process is an exciting problem.
3) Extending Analysis to other Detection Models and Mobility Patterns: Some other detection models for such systems are reasonable but have not been studied yet. For example, regarding the warden, it is reasonable to assume that Willie needs to spend a certain time before being able to detect the transmission or that he can, over time, learn which nodes do not have relays. Regarding the mobility patterns, random walks on irregular graphs or some other area traversing models are of interest. 4) Computing trade-off Between False-alarm and Misseddetection: Some IoT devices may help Alice and Bob achieve covert communication. For example, some devices can deceive the warden into wrongly accusing Alice and Bob of the message passing. In such scenarios, we should consider the tradeoff between false-alarm and missed-detection. Another scenario where false-alarm and missed-detection are of interest is when the transmission is organized through incremental data redundancy in a classical way (see, e.g., [33], [34]). Rather than assuming a perfect detection of the message chunk, we here assume that each relay sends a very noisy version of the entire message to reduce the detection probability. The collector then recovers the message by, e.g., Chase combining of the received noisy versions. 5) Studying Systems with Unreliable Relays : In the IoβT scenarios, we expect some of the relays to be adversarial. In general, these objects have power constraints, and we may not rely on all of them to provide the required storage service. Including such impairments is of interest for further study.