3.1 Network Initialization Mode

The network initialization mode is used for estimating PD-NEXT while all nodes are unsynchronized in the first frame. $\textit{TSO}$$_{1}$ starts the network by broadcasting a packet with $\textit{t}$$_{s,1}$. As soon as each node receives the packet, it sets the local time to $\textit{t}$$_{s,1}$ and starts the first frame. Because all nodes are still unsynchronized, a fixed guard time is used to prevent collisions, and its length is denoted as $\textit{T}$$_{MAX\backslash \_ RTT}$, which is the maximum round trip time.

After the first time slot, each node estimates PD-NEXT by exchanging a packet. The packet of $\textit{TSO}$$_{i}$ contains $\textit{t}$$_{s,i}$ and $\textit{t}$$_{r,i-1,i}$ as well as the data. In the $\textit{i-th}$ time slot, $\textit{TSO}$$_{i}$ broadcasts the packet, and $\textit{TSO}$$_{i+1}$ records $\textit{t}$$_{r,i,i+1}$. Subsequently, in the ($\textit{i+1}$)$\textit{-th}$ time slot, $\textit{TSO}$$_{i+1}$ broadcasts the packet containing $\textit{t}$$_{s,i+1}$ and $\textit{t}$$_{r,i,i+1}$ as well as the data. Then, $\textit{TSO}$$_{i}$ records $\textit{t}$$_{r,i+1,i}$ and obtains $\textit{p}$$_{i,i+1}$ with the following calculation: {($\textit{t}$$_{r,i+1,i}$ - $\textit{t}$$_{s,i}$) - ($\textit{t}$$_{s,i+1}$ - $\textit{t}$$_{r,i,i+1}$)}/2. However, $\textit{TSO}$$_{i+1}$ does not yet have $\textit{p}$$_{i,i+1}$. In particular, $\textit{TSO}$$_{N}$ regards $\textit{TSO}$$_{1}$ as the next time slot owner in order to estimate PD-NEXT.

3.2 Normal Mode

After network initialization mode (i.e., for the first frame), all nodes switch to normal mode. All nodes perform guard time control and time synchronization with PD-NEXT estimated in the previous frame. In addition, all nodes estimate PD-NEXT to be used in the next frame.

A packet of $\textit{TSO}$$_{i}$ contains $\textit{t}$$_{s,i}$, $\textit{t}$$_{r,i-1,i}$, and $\textit{p}$$_{i,i+1}$ as well as the data, as shown in Fig. 1. When $\textit{TSO}$$_{i+1}$ receives this packet, it obtains $\textit{t}$$_{s,i}$ and $\textit{p}$$_{i,i+1}$. Thus, $\textit{TSO}$$_{i+1}$ can achieve time synchronization with $\textit{TSO}$$_{i}$ by setting the local time as the sum of $\textit{t}$$_{s,i}$ and $\textit{p}$$_{i,i+1}$. It also determines $\textit{t}$$_{s,i+1}$ as follows:

where $\textit{T}$$_{S,i}$ is obtained from (2) and depends on $\textit{T}$$_{G,i}$. In particular, $\textit{TSO}$$_{1}$ regards $\textit{TSO}$$_{N}$ as the previous time slot owner for time synchronization. Therefore, $\textit{t}$$_{s,1}$ is obtained from $\textit{t}$$_{s,N}$ + $\textit{T}$$_{S,N}$.

When PD-NEXT is used for guard time control and time synchronization, errors occur because PD-NEXT was estimated in the previous frame. Hence, an additional guard time is used to compensate for these errors. More specifically, $\textit{T}$$_{G,i}$, which is not $\textit{T}$$_{MAX\backslash \_ RTT}$ as in the first frame, is expressed as

where $\textit{e}$$_{MAX}$ denotes the additional guard time to compensate for errors of propagation delay estimation and time synchronization. Our error model is the same as in ^[4]. We can express $\textit{e}$$_{MAX}$ as 2(${\varepsilon}$+${\sigma}$) where ${\varepsilon}$ is the maximum error experienced in estimating the propagation delay between any two nodes, and ${\sigma}$ is the maximum time synchronization error due to drift before time synchronization. Because each of the errors between any two nodes differs by at most two times, we define $\textit{e}$$_{MAX}$ as twice the size of ${\varepsilon}$+${\sigma}$. We assume that $\textit{e}$$_{MAX}$ is a value derived from experiments before the system starts.

In Fig. 1, we depict an example of the AGT-IPD frame structure and packet structure in normal mode when $\textit{N}$ is 4 and the predefined order is 1${\rightarrow}$3${\rightarrow}$2${\rightarrow}$4. At $\textit{t}$$_{s,1}$, $\textit{TSO}$$_{1}$ broadcasts a packet that includes the values of $\textit{t}$$_{s,1}$, $\textit{t}$$_{r,4,1}$, and $\textit{p}$$_{1,2}$. As soon as $\textit{TSO}$$_{4}$ and $\textit{TSO}$$_{2}$ receive the packet, they record $\textit{t}$$_{r,1,4}$ and $\textit{t}$$_{r,1,2}$, respectively. $\textit{TSO}$$_{4}$ estimates the new PD-NEXT by calculating $\textit{p}$$_{4,1}$, which will be used in the next frame, as follows: {($\textit{t}$$_{r,2,1}$ - $\textit{t}$$_{s,1}$) - ($\textit{t}$$_{s,2}$ - $\textit{t}$$_{r,1,2}$)}/2. $\textit{TSO}$$_{2}$ achieves time synchronization with $\textit{TSO}$$_{1}$ by setting its local time with $\textit{t}$$_{s,1}$ + $\textit{p}$$_{1,2}$. It then determines $\textit{t}$$_{s,2}$ by calculating $\textit{t}$$_{s,2}$ = $\textit{t}$$_{s,1}$ + $\textit{T}$$_{S,1}$ from (3). In $\textit{T}$$_{S,1}$, $\textit{T}$$_{G,1}$ is obtained by calculating $\textit{T}$$_{G,1}$ = $\textit{p}$$_{1,2}$ + $\textit{e}$$_{MAX}$ from (4). After $\textit{TSO}$$_{2}$ determines $\textit{t}$$_{s,2}$, it starts to broadcast at $\textit{t}$$_{s,2}$. All nodes repeatedly estimate a new PD-NEXT, achieving time synchronization with the owner of the next time slot, and determining the starting time of their own time slots with the adaptive guard time. As shown in Fig. 1, each time slot has a different length attributed to the adaptive guard time.

4.1 Simulation Model

We performed 100 simulations and averaged the results to obtain link utilization. In each simulation, $\textit{N}$ nodes were deployed in a uniform distribution for sphere of radius $\textit{R}$/2, where $\textit{R}$ is the maximum communication range. Thus, all nodes can communicate directly. In spherical coordinates, the location of a node is specified by ($\textit{r}$, ${\theta}$, ${\varphi}$), where $\textit{r}$ is the radial distance, ${\theta}$ is the polar angle, and ${\varphi}$ is the azimuth ^[8]. Thus, for each node deployed, three uniform random variables, ($\textit{r}$, ${\theta}$, ${\varphi}$), are selected from 0 ${\leq}$ $\textit{r}$ ${\leq}$ $\textit{R}$, 0 ${\leq}$ ${\theta}$ ${\leq}$ ${\pi}$, and 0 ${\leq}$ ${\varphi}$ ${\leq}$ 2${\pi}$, respectively. We assume that each node has one time slot per frame, that the order of time slot allocation is random, and that all nodes already have the order before the system starts. After the completion of node deployment, each scheme estimated $\textit{U}$.

We use fixed guard time (FGT) and AGT-LPD as the comparison schemes. FGT uses a guard time of fixed length, as in Link-16, and AGT-LPD uses adaptive guard time. For the comparison schemes, but not AGT-IPD, we assumed that all the nodes are synchronized. We also assumed that each node in AGT-LPD has the propagation delay between it and the node from which it is the farthest. In FGT, the time slot length was set as $\textit{T}$$_{P}$ + $\textit{P}$$_{MAX}$ + $\textit{e}$$_{MAX}$, where $\textit{P}$$_{MAX}$ is the maximum propagation delay in accord with the maximum communication range. Thus, $\textit{T}$$_{frame}$ for FGT was $\textit{N}$($\textit{T}$$_{P}$ + $\textit{P}$$_{MAX}$ + $\textit{e}$$_{MAX}$). In AGT-LPD, the length of the $\textit{k-th}$ time slot was set at $\textit{T}$$_{P}$ + $\textit{P}$$_{k}$ + $\textit{e}$$_{MAX}$, where $\textit{P}$$_{k}$ is the propagation delay between $\textit{TSO}$$_{k}$ and its farthest node. Thus, the $\textit{T}$$_{frame}$ of AGT-LPD was the total length of $\textit{N}$ time slots.

4.2 Analytical Model

We constructed an analytical model to check the performance of AGT-IPD. Before estimating $\textit{U}$ in the analytical model, we need to estimate the expected propagation delay between any pair of nodes. Therefore, we defined a node deployment rule for its estimation.

The node deployment rule is that all nodes are distributed evenly in each dimension. We deployed $\textit{N}$ nodes within a sphere of radius $\textit{R/2}$. We defined $\textit{N}$$_{D}$ as the number of nodes per dimension. Thus, $\textit{N}$$_{D}$ is the cube root of $\textit{N}$. Let $\textit{l}$$_{n}$ be the location of node $\textit{n}$ for 1 ${\leq}$ n ${\leq}$ $\textit{N}$. For a given $\textit{n}$, we determined three variables ($\textit{i}$, $\textit{j}$, $\textit{k}$), where $\textit{i}$ is the quotient of ($\textit{n}$ - 1) divided by $\textit{N}$$_{D}$$^{2}$, $\textit{j}$ is the quotient of ($\textit{n}$ - 1 - $\textit{iN}$$_{D}$$^{2}$) divided by $\textit{N}$$_{D}$, and $\textit{k}$ is ($\textit{n}$ - 1) modulo $\textit{N}$$_{D}$. Then, $\textit{n}$ = $\textit{iN}$$_{D}$$^{2}$ + $\textit{jN}$$_{D}$ + ($\textit{k}$ + 1). After determining the three variables, $\textit{l}$$_{n}$ can be specified by the spherical coordinates ($\textit{r}$$_{i}$, ${\theta}$$_{j}$, ${\varphi}$$_{k}$) where $\textit{r}$$_{i}$ = $\textit{iR}$/($\textit{N}$$_{D}$ - 1), ${\theta}_{j}$ = $j{\pi}/(N_{D}$ - 1), and ${\varphi}$$_{k}$ = 2$k{\pi}$/($N_{D}$ - 1) for 0 ${\leq}$ $\textit{i}$, $\textit{j}$, $\textit{k}$ < $\textit{N}$$_{D}$.

After the nodes were deployed, we could calculate $\textit{E}$[$\textit{P}$], which denotes the expected propagation delay between any pair of nodes and is expressed as

where $\textit{d}$($\textit{l}$$_{n}$, $\textit{l}$$_{m}$) is the distance from node $\textit{n}$ to node $\textit{m}$, $\textit{c}$ is the signal propagation speed, and $\textit{p}$($\textit{l}$$_{n}$, $\textit{l}$$_{m}$) is the probability that node $\textit{m}$ is selected after node $\textit{n}$ is selected. We obtained $\textit{d}$($\textit{l}$$_{n}$, $\textit{l}$$_{m}$) = {($\textit{x}$$_{n}$ - $\textit{x}$$_{m}$)$^{2}$ + ($\textit{y}$$_{n}$ - $\textit{y}$$_{m}$)$^{2}$ + ($\textit{z}$$_{n}$ - $\textit{z}$$_{m}$)$^{2}$}$^{\mathrm{1/2}}$, where ($\textit{x}$$_{n}$, $\textit{y}$$_{n}$, $\textit{z}$$_{n}$) and ($\textit{x}$$_{m}$, $\textit{y}$$_{m}$, $\textit{z}$$_{m}$) are the Cartesian coordinates of $\textit{l}$$_{n}$ and $\textit{l}$$_{m}$, respectively. If the spherical coordinates of $\textit{l}$$_{n}$ are ($\textit{r}$$_{i}$, ${\theta}$$_{j}$, ${\varphi}$$_{k}$), then ($\textit{x}$$_{n}$, $\textit{y}$$_{n}$, $\textit{z}$$_{n}$) is obtained as follows: $\textit{x}$$_{n}$ = $\textit{r}$$_{i}$sin${\theta}$$_{j}$cos${\varphi}$$_{k}$, $\textit{y}$$_{n}$ = $\textit{r}$$_{i}$sin${\theta}$$_{j}$sin${\varphi}$$_{k}$, and $\textit{z}$$_{n}$ = $\textit{r}$$_{i}$cos${\theta}$$_{j}$. Regardless of $\textit{n}$ and $\textit{m}$, $\textit{p}$($\textit{l}$$_{n}$,$\textit{l}$$_{m}$) is expressed as {$\textit{N}$($\textit{N}$ - 1)}$^{-1}$.

Now, we can obtain $\textit{U}$ in the analytical model. In (4), $\textit{T}$$_{G,i}$ becomes $\textit{E}$[$\textit{P}$] + $\textit{e}$$_{MAX}$ for all $\textit{i}$. In (1), $\textit{T}$$_{frame}$ becomes $\textit{NT}$$_{S,i}$ because all time slot lengths are the same. Therefore, in the analytical model, $\textit{U}$ for AGT-IPD can be derived by

4.3 Numerical Results

We compared $\textit{U}$ of AGT-IPD with those of AGT-LPD and FGT. To verify AGT-IPD, we compared the analytical results with the simulated results.

In airborne networks such as Link-16 ^[7] and Tactical Targeting Network Technology (TTNT) ^[9], a radio frequency (RF) signal with a propagation speed of 3${\times}$10$^{8}$ m/s is used. Because the maximum communication range is 300nm, the maximum propagation delay is 1.852~ms. In TTNT, the maximum number of nodes is 200.

For simulation and analysis, we selected the values of $\textit{N}$ and $\textit{R}$ based on Link-16 and TTNT. $\textit{R}$ and $\textit{N}$$_{D}$ were set at 300~nm and 6 to make the environments similar to TTNT. We also altered $\textit{R}$, $\textit{N}$$_{D}$, $\textit{e}$$_{MAX}$, and $\textit{T}$$_{P}$ for various comparisons. We considered an error-free single channel.

Fig. 2 shows $\textit{U}$ according to $\textit{T}$$_{P}$ when $\textit{R}$ = 300 nm, $\textit{N}$ = 216, and $\textit{e}$$_{MAX}$ = 0 ms. All schemes provided a high $\textit{U}$ when $\textit{T}$$_{P}$ was large. FGT showed the lowest $\textit{U}$ because the guard time length, which was set at the maximum propagation delay, was the largest. AGT-LPD provided a higher $\textit{U}$ than FGT owing to the use of the adaptive guard time considering the propagation delay between the time slot owner and the farthest node. AGT-IPD provided a much higher $\textit{U}$ than FGT or AGT-LPD because it uses an adaptive guard time considering PD-NEXT. If the next time slot owner is the farthest node in a certain time slot, then the guard time length of the time slot is the same as in AGT-LPD, even though it was the worst case in AGT-IPD. Therefore, $\textit{U}$ for AGT-LPD cannot be higher than $\textit{U}$ for AGT-IPD. To verify our simulation model, we compared it with the analytical model of AGT-IPD. We can see that both showed almost the same performance.

Fig. 2. Comparison of link utilizations according to TP (R = 300 nm, N = 216, $e_{MAX}$ = 0).

Fig. 3 shows $\textit{U}$ according to $\textit{R}$ when $\textit{N}$ = 216 and $\textit{e}$$_{MAX}$ = 0 ms. In each time slot, the ratio of $\textit{T}$$_{P}$ to guard time length, which is affected by $\textit{R}$, affected $\textit{U}$ directly. When $\textit{R}$ was 300 nm, the maximum propagation delay was 1.852 ms. We considered two types of packet: one with a length shorter than the maximum propagation delay (0.1 ms) and another with a length that is longer (3.0 ms). As shown in Fig. 3, $\textit{U}$ was high when $\textit{T}$$_{P}$ was large. Regardless of $\textit{T}$$_{P}$, AGT-IPD consistently provided the highest $\textit{U.}$ The analytical and simulated models of AGT-IPD also showed almost identical performance.

Fig. 4 shows $\textit{U}$ according to $\textit{N}$$_{D}$ when $\textit{R}$ = 300 nm and $\textit{e}$$_{MAX}$ = 0 ms. When $\textit{N}$$_{D}$ was less than 5, AGT-LPD was only affected by $\textit{N}$$_{D}$. Regardless of $\textit{T}$$_{P}$, AGT-IPD and FGT were hardly affected by $\textit{N}$$_{D}$. AGT-IPD also provided the highest $\textit{U}$.

Fig. 5 shows $\textit{U}$ according to $\textit{e}$$_{MAX}$ when $\textit{R}$ = 300 nm and $\textit{N}$~= 216. In each scheme, $\textit{U}$ decreased when $\textit{e}$$_{MAX}$ was large. In particular, when $\textit{T}$$_{P}$ was large, all schemes were greatly affected by $\textit{e}$$_{MAX}$. When $\textit{e}$$_{MAX}$ was 2.0 ms, which is greater than the maximum propagation delay, and when $\textit{T}$$_{P}$ was 0.1~ms, the difference in $\textit{U}$ between any pair of schemes was very small because $\textit{e}$$_{MAX}$ is constant with no mechanism to reduce it. Nevertheless, AGT-IPD still provided the highest $\textit{U}$.

Fig. 3. Comparison of link utilizations according to R (N = 216, $e_{MAX}$ = 0).

Fig. 4. Comparison of link utilizations according to $N_{D}$ (R = 300 nm, $e_{MAX}$ = 0).

Fig. 5. Comparison of link utilizations according to $e_{MAX}$ (R = 300 nm, N = 216).