Sage Journals: Discover world-class research

Abstract

In order to ensure the strong real-time information sharing of Aerial Ad hoc Network, a low-delay information sharing algorithm for multiple-radio-per-platform networking is proposed based on the directional transmission capability of phased-array antenna. The algorithm introduces virtual nodes and virtual links in the process of topology generation first. By extracting topology information and choosing link grouping, it can effectively reduce redundant transmission and transmission latency of information sharing. Then, it is verified through simulation that the algorithm can reduce the latency by up to 49.8% and eliminate transmission redundancy. In addition, a direction selection algorithm is proposed for the variation of antenna beam direction. Simulation results show that the algorithm can further reduce the latency of information sharing and ensure the real time of information sharing, thus further improving the network performance.

Keywords

Ad hoc network phased-array antenna low-delay information sharing direction selection

Introduction

Ad hoc networks are applied in many hostile, hazardous, or impassable environments where there is little or no fixed communication infrastructure. Specifically, with the rapid development of sensor technology and the extensive use of Unmanned Aerial Vehicles (UAVs), Aerial Ad hoc Network (AANET),¹ also known as Flying Ad hoc Network (FANET),² is designed for aviation communication field.

For these scenarios, information sharing is one of the important applications.³ For example, sharing the status of the weapons among the tactical forces across the battle sphere is a critical mechanism to support cooperative engagement. Information sharing, being equal to all-to-all broadcast in this article, can cause the demand for large bandwidth, which leads to the great challenge for point-to-point communication based on omni-directional antenna.

In order to connect the operators within AANET by broadband long-range link, directional transmission should be adopted using phased-array antenna. On one hand, higher frequencies above 3 GHz are used because there is no enough spectrum in lower frequency band. But the higher the frequency, the closer the transmission. Compared to omni-directional, phased-array antenna is mounted to enable a flying node to better communicate with the other remote nodes thanks to the beam-forming capability. On the other hand, directional transmission has the naturally capabilities of anti-jamming and low-probability-of-interception. Furthermore, driven by the advancement and miniaturization of signal processor, sensor, and computing units, aerial vehicles can be mounted more electrical devices, including phased-array antennas whose beam width can be adjusted. Then, the multiple-radio-per-platform architecture is introduced.⁴ A single carrier platform has multiple radios; each tied to a phased-array antenna. With this architecture, the carrier can communicate with the nearby neighbor in any direction without blocking or shadowing.

Meanwhile, the data to be shared are generally time dependent.^5–8 Traditionally, all-to-all broadcast mostly floods packets within the network and results in more redundancy, higher energy consumption, more waste of wireless resources and worse timeliness, which is not in line with the requirements of the battlefield applications in real-time and long-distance transmission. Therefore, how to reduce packet redundancy and time delay in AANET is still the main problem needed to be addressed if information sharing is concerned.

In this article, regarding the multi-radio-per-platform model, we study the low-latency all-to-all broadcast problem in AANET. The outline of this article is organized as follows. First, the related works are discussed in section “Related work.” Second, the contributions of this work are briefly introduced in section “Contribution of this work.” Third, the formation of the problem is described in detail in section “Problem formation.” And then, the mechanism and algorithm are proposed in section “Algorithm mechanism.” After that, the simulation results and analysis are presented in section “Performance evaluation.” Finally, the conclusion is drawn in section “Conclusion.”

Related work

In general, the all-to-all communication can be accomplished with two steps: first, select the appropriate node and take this node as the root to construct the spanning tree by width-first search; second, the root node gathers all packets that need to be shared within the whole network, and then distribute the packets to all of the other nodes in the net without conflict.

The typical all-to-all communication methods are hierarchical scheduling⁹ and coloring theory scheduling.¹⁰ Furthermore, Lanotte et al.¹¹ proposed a compositional analysis technique to study formal probabilistic models of gossip protocols in the context of wireless sensor networks. Leme et al.¹² evaluated an information sharing algorithm based on cyclic strategy in a simulated mobile ad hoc wireless network, and analyzed its influence on reliability and overall performance through simulations. To achieve low delay, She et al.¹³ established a framework for enabling ultra-reliable and low-latency communications in UAV communication systems based on access points. As far as the directional transmission is concerned, the delay is used as a measurement index if information sharing within a network using multi-beam directional antenna is studied.¹⁴

Based on the assumption of directional transmission and omni-directional reception, F Dai et al.¹⁵ proposed that unnecessary links should be blocked to reduce redundant transmission and avoid broadcast storm. Moreover, Ghahfarroky et al.¹⁶ proposed a conflict-free scheduling algorithm based on directional antenna, but the problem of repeated packet transmission is unavoidable, resulting in a large number of redundant transmissions. To reduce the delay of sharing, Wang and Yang¹⁷ proposed that message processing should be divided into two consecutive steps: the message exchange and the message transmission. Starting from the second message, an overlap of the transmission time of one message and the switching time of another message enables more parallel processing based on the ideas of assembly line. Through the proposed overlap, the all-to-all broadcast algorithm can approach the optimal transmission time, and the total sharing delay asymptotically approaches to the lower bound of the broadcast algorithm. Meanwhile, the algorithm ensures the traffic load balance of every dimension in the network. Ramanathan¹⁸ proposed an algorithm called UxDMA, which means A Unified Algorithm for efficient Time/Frequency/Code Division Multiple Access Channel Assignments. The UxDMA algorithm schedules links based on the global topology and time division multiple access (TDMA). It uses the conflict determination criteria to color the links in the topology first, and then randomly selects a color-grouped link at each time slot to schedule. With conflict-free scheduling, UxDMA greatly reduces link conflicts and improves the efficiency of information sharing.

However, none of these methods can eliminate the redundancy completely. And judiciously optimizing beam angle in the directional transmission can further reduce the delay of information sharing. But the influence of beam angle on delay in these research works is not considered.

Contribution of this work

As discussed above, none of the existing protocol supports real-time information sharing in three-dimensional (3D) AANETs. In order to solve the above problems, a Minimum-Latency All-to-All Broadcast (MLAB) algorithm is proposed in this article based on the characteristics of phased-array antenna and the coloring idea, which achieves minimum delay and redundancy in the network. On this basis, the direction selection algorithm MLAB-DS is further proposed considering the influence of antenna beam angle on the algorithm, which realizes the information sharing with conflict-free, low delay and low redundancy, and improves the network performance. MlAB-DS realized the efficient and intensive communication of smart antennas by changing phase of oscillator elements, which makes instant information sharing in multiple-radio-perplatform networking be possible. In this research, we consider AANET deployed in a 3D space with sparsely deployed nodes, which carry multiple-beam antennas. The contributions of this work are summarized as follows:

First, a virtual node model is set up to describe the node with multiple-beam antennas. The virtual node model actually splits a node into double layers, that is, node-based layer and beam-sector-based layer. The beam-sector-based layer is convenient for designer to work with multiple packets transmitting or receiving simultaneously. And the capability that multiple packets can be transmitted and received by multiple beams, respectively, is the characteristic of the proposed medium access protocol.

Second, the medium access control (MAC) protocol presented in this article does well in information sharing with low latency and low redundancy. For delay-sensitive applications, the proposed MLAB algorithm schedules the packets according to the coloring results rigidly. And MLAB-DS algorithm adjusts antenna pointing to avoid the conflicts and the redundant transmission.

Moreover, to facilitate the description of the models and algorithms below, the notations used in this article and their definitions are listed in Table 1.

Table 1.

Main notations used in this article.

Notation	Definition
$θ$	Beam width of antenna
$H$	Adjacency matrix
$I_{t}$	Information matrix
$L$	Schedulable link matrix
$H (i, j)$	Link with sending node $i$ and receiving node $j$
$I_{t (i, k)}$	Node $i$ has packet $k$
$L (i, j, k)$	Node $i$ transmits packet $k$ to node $j$
$M_{T}$	Color sequence
$α_{i}$	Direction of the node $i$
$N$	Total number of nodes
$r$	Communication radius
$E (α_{i}, i)$	Total number of links of node $i$
$β_{i}$	Beam angle of node $i$
$A (α_{i})$	Mean value of $E (α_{i}, i)$
$D (α_{i})$	Standard deviation of $E (α_{i}, i)$
$κ$	Arbitrary constant
$Δ κ_{i}$	Increased step length
$T$	Time slot

Problem formation

In this section, several models about the system are established to illustrate the networking problem. We assume that several aerial vehicles are flying in the air for a definite mission. Any vehicle obtains the useful information periodically and needs to share with all the other vehicles. Once the information is failed to share within a rigid period, it will be abandoned. An ad hoc net has been formed through neighbor discovering and the vehicles communicate synchronously.

Antenna model

The physical layer is very important in the AANET. To this end, the antenna model should be considered at first. It is necessary to form multiple lines of contacts between the network nodes using the phase-array antennas.

The phased-array antenna can adjust the direction of the main lobe by controlling the feeding phase of the radiation element of array antenna. In this way, the phased-array antenna is used to concentrate the radio transmission energy in a specific direction, which can reduce the mutual interference of adjacent nodes in the network and increase the space division multiplexing of the channel. The signal transmission distance will be further, and the network capacity will be larger using phased-array antenna than omni-directional antenna under the same power. Meanwhile, it can enhance the concealment of communication and improve the interception resistance and anti-interference capability of the network.¹⁹

The antenna radiation pattern²⁰ is shown in Figure 1. The spherical space represents the coverage of the antenna, and the concentrated radiation of the blue beam directed to multiple certain directions.

Figure 1.

Directional antenna radiation pattern.

All nodes in the airborne network are assumed to be equipped with four phased-array antennas capable of forming four beam widths, a focused beam at an angle of $θ$ . Each antenna array is independently steerable to focus in a particular direction independently and covers the upper, lower, front, and rear section individually.

Compared with the main lobe, the gain of side lobes is too small. Therefore, the antenna model is simplified, and only the main lobe is considered. And for the convenience of calculation, the blue main lobe is idealized as a cone with the beam width $θ$ , which is the red part in Figure 1. In addition, the transceiver is half duplex, which means the signal cannot be sent and received in the meantime.

Network model

Assuming that the nodes are randomly distributed in the network, the samples sampled from network structure at any unit time are treated as a transient snapshot in the Euclid space, so the topology at any time is idealized as static. The remaining assumptions are as follows:

The network is fully connected.

Each node knows the topology information of the whole network, and has the unique number in the network, called NodeID.

All nodes in the network are homogeneous.

Time in the network is strictly synchronized.

Information sharing model

The information sharing in this article is actually information interaction of the nodes based on TDMA and directional transmission. Then, the nodes with the same status in the network can eventually share the information of all other nodes through information exchange. The transformation from the state in Figure 2(a) to the state in Figure 2(b) illustrates an example of information sharing from the initial state to the completed state. In the process of information sharing, in order to facilitate understanding, the intermediate process of packet transmission is ignored and the initial and completed state of information sharing is mainly concerned in this section. The initial state is the original state of the topology; in this moment, each node carries the initial packet which is numbered with the NodeID. Such as in Figure 2(a), node 1 carries packet I, node 2 carries packet II, node 3 carries packet III, and node 4 carries packet IV. And the completed state is that the information sharing is completed, and in this moment, each node has all packets within the network. Such as in Figure 2(b), nodes 1, 2, 3, and 4 all carry packet I, II, III, and IV.

Figure 2.

Information sharing model: (a) initial state and (b) completed state.

In addition, the unit message model²¹ is set up to research the data transmission, which means the size of each packet in the network is identical. And only one packet can be transmitted once a time slot. In addition, a time slot is used to represent a unit time, and information sharing is completed through time slot allocation among nodes in the network. In each time slot, each node can get no more than one chance to transmit, and a single packet can be transferred within a time slot.

Node model

Each node of AANET in this article represents a UAV which is widely used in both military and civil fields. In order to avoid the blind coverage of the communication of UAV, the quadrangular array antenna is considered to be used in directional communication pattern. Each node is equipped with four phased-array antennas, which are mounted on the upper, lower, front, and rear of the UAV. And a virtual node model is introduced to model the transceiver node with a set of antenna array. In other words, the UAV is the node in reality, while the transceiver node is the virtual node in network topology. It is assumed that each UAV node has a unique and consistent number throughout the network, and the NodeID is defined as $p$ . Furthermore, the corresponding transceiver node of the UAV node $p$ is identified as

q = {\begin{matrix} 4 p - 3, if the antenna is the upper antenna \\ 4 p - 2, if the antenna is the lower antenna \\ 4 p - 1, if the antenna is the front antenna \\ 4 p, if the antenna is the rear antenna \end{matrix}

(1)

where $p = 1, \dots, N$ and $q = 1, \dots, 4 N$ . Virtual nodes are independent in link scheduling, but they are related in data processing. If the NodeID of UAV which two different virtual transceiver nodes are corresponding to is the same, then the packets the virtual transceiver nodes own are the same. Furthermore, the transmission and receiving state of antennas corresponding to the same UAV node must be the same in a time slot.

Transmission redundancy model and conflict model

The distribution characteristics of nodes can lead to redundant transmission of packets, which will cause extra energy consumption and delay.¹⁶ And redundant transmission can be divided into two cases: repeated receiving and repeated transmission. Figure 3(a) shows the situation of receiving packets repeatedly: in a certain time slot, node 1 already got packet III, but it is still receiving packet III sent by node 2; Figure 3(b) shows the case of transmission repeated: at a certain time slot, node 3 and node 4 are transmitting packet IV to node 2 in the meantime. The transmission redundancy is considered as a special case of conflict determination, so collision avoidance decision is made to eliminate redundancy during link selection.

Figure 3.

Transmission redundancy model: (a) repeated reception and (b) repeated transmission.

Because of the directivity of directional transmission, there may be conflicts between nodes in the network. There are four traditional conflict situations as follows:

Half-duplex conflict, that is, the node cannot receive and transmit packets at the same time. If a node is transmitting packets and another node is transmitting packets to this node, then conflict arises.

A node can only transmit packets to one node at a certain time. If the transmitting beam of a transmitter covers multiple receivers at the same time, then conflict arises.

A receiver cannot receive packets from different transmitters at the same time. If a receiver is covered by multiple transmitting beams, then conflict arises.

Hidden terminal conflict²² in directional transmission. If there is hidden terminal in the packet transmission, then conflict arises.

For quadrangular array antenna, four virtual nodes in the same node must be in the same state in the same time slot, which leads to a new conflict scenario. As shown in Figure 4, virtual nodes 2 and 3 are two independent nodes in an actual node. When node 2 is in the transmitting state, node 3 must also be in the transmitting state. At this point, if node 12 transmits a packet to node 3, node 3 cannot accept it, resulting in a conflict. The new conflict scenario is added to the algorithm, and the location information of virtual nodes is used to calculate and judge whether there is a conflict in the link, so as to avoid the conflict.

Figure 4.

Special conflict model for directional transmission.

Algorithm mechanism

The specific algorithm process will be introduced in this section. To get an intuition, the topology extraction process, coloring principle, and link scheduling process will be described by taking the topology in Figure 5 as an example. Based on this, MLAB and MLAB-DS algorithms will be introduced in detail to achieve low-delay information sharing.

Figure 5.

Schematic diagram of topology: (a) real topology and (b) virtual topology.

Topology extraction

An example of the actual topology of the network is shown in Figure 5(a). Each node stores its own node information, including NodeID, position information, antenna parameters, direction, and so on. The ID of the initial packets carried by each node is the same as the NodeID, such as the ID of the initial packet carried by node 1 is I. The actual topology is transformed into a virtual topology first, as shown in Figure 5(b). One node is transformed into four virtual nodes, and the corresponding virtual nodes of the same node carry the same packets. For example, virtual nodes 1, 2, 3, and 4 all carry packets of number I. Actually, the location information of the virtual node is the same as that of the real node, only the ID of the virtual node and the direction of the antenna are needed to be converted according to formula (1). Based on this, the virtual network topology is defined as an undirected graph $G (V, E)$ , where $V$ represents the virtual nodes in the network and $E$ represents the edges in the graph.

Next, the neighbor information of nodes in the virtual topology is stored into the adjacency matrix $H$ according to the information of the undirected graph. Figure 6 shows a partial schematic diagram of the adjacency matrix obtained according to Figure 5(b), where $i$ represents the transmitter and $j$ represents the receiver. For example, $H (2, 8) = 1$ represents that the link with transmitter 2 and receiver node 8 exists, that is, node 8 is the neighbor of node 2. And $H (2, 7) = 0$ represents that the link with transmitter 2 and receiver 7 does not exist.

Figure 6.

The adjacency matrix $H$ .

Then, the information owned by each node is stored into the information matrix $I_{t}$ , as shown in Figure 7(a), which is a diagram of the information matrix in the initial state. The vertical axis $N$ represents the NodeID and the horizontal axis $P$ represents the PacketID. For example, $I_{t} (4, I) = 1$ indicates that the virtual node 4 has packet I, and $I_{t} (8, I) = 0$ indicates that there is no packet I in virtual node 8. When information sharing of the whole network is completed, each node has all packets in the network, so the values of all elements in the information matrix are 1, as shown in Figure 7(b), which is a diagram of the information matrix in the completed state. The matrix is called target matrix in the following, indicating that the information sharing of the whole network is completed.

Figure 7.

The information matrix $I_{t}$ : (a) initial state and (b) completed state.

After that, the schedulable links in the topology are obtained by combining the adjacency matrix and information matrix, and stored in the schedulable link matrix $L$ . For example, if node $j$ is the neighbor of node $i$ , and $j$ has packets $k$ but $i$ does not have, then the link $L (i, j; k)$ is schedulable, and its value is set to 1, that is, $L (i, j; k) = 1$ . Comparing with the information in the information matrix $I_{t}$ , the destination node can avoid repeatedly receiving to reduce transmission redundancy. For example, if the receiving node and packet number of the two links are the same, only one link is activated for data transmission.

Principle of coloring and scheduling

In the process of coloring and scheduling, the schedulable links are checked in turn to avoid conflict. And the conflict-free links are colored the same color and stored in a group. The group with the highest number of links is selected for priority scheduling to realize conflict-free and low-delay information sharing.

The topology of Figure 5(b) is taken as an example to introduce the basic principles of coloring of links:

According to the adjacency matrix (presented in Figure 6) and the initial information matrix (presented in Figure 7(a)), the schedulable links are arranged and sorted according to the order of the serial number of nodes in ascending order as follows: $L (2, 8; I)$ , $L (3, 16; I)$ , $L (7, 12; II)$ , $L (7, 13; II)$ , $L (8, 2; II)$ , $L (11, 14; III)$ , $L (12, 7; III)$ , $L (13, 7; IV)$ , $L (14, 11; IV)$ , and $L (16, 3; IV)$ .

The link $L (2, 8; I)$ is colored to 0 and stored into the link group 0.

Estimate whether the second link $L (3, 16; I)$ conflicts with $L (2, 8; I)$ . Since nodes 2 and 3 are two different virtual nodes of the same UAV node and packets can be sent simultaneously without conflict, so the link $L (3, 16; I)$ is also colored to 0.

Estimate whether the third link $L (7, 12; II)$ conflicts with $L (2, 8; I)$ or $L (3, 16; I)$ . Because nodes 7 and 8 belong to two different virtual nodes of the same UAV node, and node 7 cannot transmit packets when node 8 is receiving. So, the link $L (7, 12; II)$ conflicts with $L (2, 8; I)$ , and the link $L (7, 12; II)$ is colored to 1 to avoid conflict, and stored into the link group 1.

All other schedulable links in the topology are also colored and stored by the same method.

The group containing the most links based on the coloring results is selected and the sequence of links contained in that group is output.

Output the scheduling sequence and go to the next time slot and repeat the above steps until the information matrix is identical to the target matrix.

That is the complete process of coloring and scheduling taken the topology of Figure 5(b) as an example, with the ultimate result of coloring and scheduling sequence is shown in Table 2.

Table 2.

The example of coloring of links.

Time slot	Color	Colored link				Group	Scheduling sequence
0	0	L(2,8;I)	L(3,16;I)	L(11,14;III)	L(12,7;III)	0	L(2,8;I), L(3,16;I), L(11,14;III), L(12,7;III)
	1	L(7,12;II)	L(8,2;II)	L(14,11;IV)	L(16,3;IV)
	2	L(7,13;II)
	3	L(13,7;IV)
1	0	L(7,12;I)	L(8,2;II)	L(14,11;I)	L(16,3;III)	0	L(7,12;I), L(8,2;II), L(14,11;I), L(16,3;III)
	1	L(7,12;II)	L(14,11;IV)	L(16,3;IV)
	2	L(7,13;II)
	3	L(13,7;IV)
2	0	L(3,16;II)	L(7,12;II)	L(14,11;IV)		0	L(3,16;II), L(7,12;II), L(14,11;IV)
	1	L(7,13;II)
	2	L(13,7;IV)	L(16,3;IV)
3	0	L(12,7;IV)	L(16,3;IV)			0	L(12,7;IV), L(16,3;IV)
	1	L(13,7;IV)					L(12,7;IV), L(16,3;IV)

According to the color grouping, in time slot 0, the color group 0 containing the most number of links is selected for scheduling first. And the scheduling sequence which is output is the links in the group of color 0. By the same token, in time slot 1, the scheduling sequence which is output is also the links in the group of color 0. And information is shared according to the scheduling sequence at each time slot. The specific process of link scheduling and communication on the topology is shown in Figure 8. In time slot 0, node 2 transmits packet no. I to node 8. Node 3 transmits packet no. I to node 16. Node 12 transmits packet no. III to node 7. And node 11 transmits packet no. III to node 14 at the same time. After packet transmission of five time slots, each node finally owns all packets in the network and information sharing is completed, as shown in Figure 8(f).

Figure 8.

The process of link scheduling and communication: (a) initial state, (b) T = 0, (c) T = 1, (d) T = 2, (e) T = 3, and (f) T = 4.

The MLAB scheduling algorithm

In order to set the end condition for the algorithm, the target matrix $I_{d}$ is introduced. When information sharing of the whole network is completed, the packet information of nodes is stored into the target matrix, and the values of all elements in the target matrix are 1, which indicates that each node has all packets in the network.

The specific algorithm flow of MLAB is as follows:

Carry out virtual topology transformation according to the information of nodes, and transform the actual topology into virtual topology. Obtain the adjacency matrix $H$ , and set $T = 0$ in the meantime (Lines 2–4).

Fill the information matrix $I_{t}$ according to the existing information of the nodes, and compare the current information matrix $I_{t}$ with the target matrix $I_{d}$ . If the two matrices are identical, the information sharing is completed and the algorithm is finished; if not, go to the next part of the algorithm (Line 5).

Update the schedulable link matrix $L$ according to the information matrix $I_{t}$ and adjacency matrix $H$ , and then tint the links for conflict avoidance, and output coloring grouping finally (Lines 11 and 12).

Select the color group containing the largest number of links for information sharing, and output the color sequence $M_{T}$ of the time slot $T$ . Information is shared once according to the link order in the coloring sequence, and then goes to the next slot, $T = T + 1$ (Lines 13–20).

The calculation process of delay is shown in Algorithm 1.

Algorithm 1. MLAB.
Input: Location information of nodes.Output: $T$ . for $m = 1; m \leq n; m + +$ do Transform virtual topology; Obtain $H$ , $I_{t}$ ; $T = 0$ ; if $I_{t} \neq I_{d}$ then for $i = 1; i \leq 4 n; i + +$ do for $j = 1; j \leq 4 n; j + +$ do if $H (i, j) = I_{d} (i, j)$ then for $k = 0; i \leq n; k + +$ do if $I_{i} (i, k) = 1 \land I_{t} (j, k) = 0$ then $L (i, j, k) = 1$ ; Estimate confliction for link $[i, j]$ ; Select the color group; Storage the link to $M_{T}$ ; end if end for end if end for end for $T = T + 1$ ; end if Return $T$ ;end for

Algorithm 1. MLAB.

Input: Location information of nodes.Output:

T

. for

m = 1; m \leq n; m + +

do Transform virtual topology; Obtain

H

I_{t}

;

T = 0

; if

I_{t} \neq I_{d}

then for

i = 1; i \leq 4 n; i + +

do for

j = 1; j \leq 4 n; j + +

do if

H (i, j) = I_{d} (i, j)

then for

k = 0; i \leq n; k + +

do if

I_{i} (i, k) = 1 \land I_{t} (j, k) = 0

then

L (i, j, k) = 1

; Estimate confliction for link

[i, j]

; Select the color group; Storage the link to

M_{T}

; end if end for end if end for end for

T = T + 1

; end if Return

T

;end for

The MLAB-DS scheduling algorithm

When the direction of the directional beam generated by the phased-array antenna changes, the virtual topology and links formed will change accordingly, which will affect the performance of the algorithm. Actually, the delay of the algorithm will increase greatly when there are too many links in the topology, or many links are concentrated on one node. Since a node can only select one link for communication in a time slot, if too many links are concentrated on a few nodes, there will be too many idle nodes, resulting in a longer time for the algorithm to complete. Therefore, the direction selection MLAB-DS is proposed based on MLAB. The algorithm calculates the antenna beam angle of normal communication between nodes by analyzing the link information of each node, and dynamically adjusts the beam angle within the range of these angle values on the premise of making the number of links of each node relatively uniform. It can further reduce the time delay fluctuation caused by the change of antenna beam direction on the premise of ensuring network connectivity.

Assume that the communication range of the node is a sphere with the node as the center and the communication distance as the radius. The horizontal section across the center of the sphere is selected as the research object. On this two-dimensional section, the due north direction is specified as the datum direction, and the included angle between the middle line of the antenna beam and the reference direction of the node $i$ is $α_{i}$ . The number of nodes in the topology is $N$ . The algorithm flow of MLAB-DS is as follows:

Carry out virtual topology transformation. The adjacency matrix $H$ is obtained from the topology, and then the number of links of each node in the topology is counted and stored in the link array $E (α_{i}, i)$ . Meanwhile, when the node communicates with other nodes, the beam direction of the antenna is calculated based on the passable link. If node $j$ is the neighbor of node $i$ , the link $L (i, j)$ is passable. In order of the magnitude of these directions, the value range of the node beam angle is obtained as $(β_{i_{min}}, β_{i_{max}})$ (Lines 3–6).

Calculate the mean value and standard deviation of the number of links at each angle in $E (α_{i}, i)$ , and store these values in the array $A (α_{i})$ and $B (α_{i})$ , respectively (Lines 8 and 9).

Change the beam angle $α_{i}$ of the antenna according to $α_{i} = α_{i} + Δ κ_{i}$ , where $Δ κ_{i}$ is the increased step length in the beam direction of the node $i$ , $Δ κ_{i} = (β_{i_{min}} - β_{i_{max}}) / κ$ , and $κ$ is an arbitrary constant selected from the topology to determine the step size. Repeat the above three steps.

Select the largest element in array $A (α_{i})$ . If there is only one maximum element, the algorithm ends and outputs the corresponding angle of the maximum element; but if the number of the largest elements is more than one, the smallest standard deviation of the elements is found in numbered order and the corresponding angle $α_{i}$ is output (Lines 11–17).

Adjust the direction of the node beam according to $α_{i}$ and obtain the optimal topology, from which the adjacency matrix $H$ and the information matrix $I_{t}$ are obtained at the same time. Then, the conflict avoidance method in MLAB is used to color the links, and the group with the largest number of links is selected for communication to complete the information sharing (Lines 18–22).

And the pseudocode of the algorithm is shown in Algorithm 2.

Algorithm 2. MLAB-DS.
Input: Location information of nodes.Output: $T$ . for $i = 1; i \leq n; i + +$ do for $k = β_{i_{min}}; k \leq β_{i_{max}}; k = k + Δ$ do Transform virtual topology; for $j = 1; j \leq 4 n; j + +$ do Storage the number of links in $E$ ; Calculate the communicable beam angle $(β_{i_{min}}, β_{i_{max}})$ ; end for Get the mean array $A$ ; Get the standard deviation array $B$ ; end for Find the largest element $p_{i}$ in array $A$ ; if $There is only one largest element$ then Output $p_{i}$ ; else Find the element $B (p_{i})$ with the least standard deviation; Output $p_{i}$ ; end if $α_{i} = p_{i}$ ; Get a new topology; Information is Shared according to MLAB; Return $T$ ; end for

Algorithm 2. MLAB-DS.

Input: Location information of nodes.Output:

T

. for

i = 1; i \leq n; i + +

do for

k = β_{i_{min}}; k \leq β_{i_{max}}; k = k + Δ

do Transform virtual topology; for

j = 1; j \leq 4 n; j + +

do Storage the number of links in

E

; Calculate the communicable beam angle

(β_{i_{min}}, β_{i_{max}})

; end for Get the mean array

A

; Get the standard deviation array

B

; end for Find the largest element

p_{i}

in array

A

; if

There is only one largest element

then Output

p_{i}

; else Find the element

B (p_{i})

with the least standard deviation; Output

p_{i}

; end if

α_{i} = p_{i}

; Get a new topology; Information is Shared according to MLAB; Return

T

; end for

On the basis of ensuring network connectivity, MLAB-DS sets different step sizes according to the position of each node and dynamically adjusts the direction of the antenna beam. The purpose is to select the most appropriate angle for each beam among the many antenna beam angles, so that the total number of links of all nodes in the final network topology is as large as possible, thus reducing the time slot required for information sharing. Meanwhile, the standard deviation of the number of links is minimized, that is, the difference between the number of links of each node in the topology is minimized, so as to ensure the distribution of the number of links of nodes is relatively even and the load of network is more balanced. And the time complexity of the algorithm is $O (n^{3})$ , which is the linear order, the level of operation required is low, so the efficiency of the algorithm is high.

Mathematical model

Mathematical model is set up to find the optimality of algorithm. The optimal solution of algorithm can be obtained under the relaxation condition, which means:

The nodes in network are uniformly distributed, and the topology is one hop.

$β = 90 °$ , four directional antennas cover the communication range of UAV in 360°, achieving the coverage effect of omni-directional, but communication distance is longer than that of omni-directional antennas. At this point, each node in network can communicate with neighbors in any direction.

Each node carries a packet which number is the same as node number, and only one packet is transmitted in each transfer.

There is only one packet transfer within a time slot.

First, undirected graph $G (V, E)$ is plotted based on topology, in which $V$ represents the nodes, and $E$ represents the communication links between nodes. The topology is projected onto a two-dimensional plane. When nodes are uniformly distributed, it is assumed that each node occupies a grid space and antenna communication radius is set so that each node on the two-dimensional plane can communicate with the nodes in the upper, lower, left, and right grids.

Second, suppose the total number of nodes in the graph $G$ is $N$ , the number of data transmissions in information sharing is $D$ . Assume $N = n$ , $D = f (n)$ . Obviously, $f (1) = 0$ , $f (2) = 2$ , and $f (3) = 3$ . By mathematical induction, it can be got that

f (n + 1) = f (n) + 1

(2)

So, when the number of nodes is $N$ , the delay of information sharing is the minimum under the relaxation condition, which is

D_{1} = N

(3)

However, in the practical application, the topology is not ideal as assumed due to the random distribution of nodes. In addition to the data processing and system delay, the final delay of information sharing will increase a lot.

And the delay of information sharing can reach the minimum value under the ideal condition when there is no limit on the number of antennas, and each node can communicate with any number of nodes within the communication range. As far as the information sharing is concerned, $N (N - 1)$ valid transmissions must be completed within the graph in which the number of edges is $2 (N - \sqrt{N})$ . During each data transmission, the delay of data sharing is the minimum, when the number of parallel links in the same time slot in the network is the maximum. And the maximum number of parallel links does not exceed the number of edges of the graph. And the delay of information sharing is minimum, and it is expressed as

D_{2} = \frac{N (N - 1)}{2 (N - \sqrt{N})} = \frac{N + \sqrt{N}}{2}

(4)

τ = \frac{D_{1}}{D_{2}} = \frac{2}{1 + \sqrt{\frac{1}{N}}}

(5)

Obviously, when $N = 1$ , $D_{1} = D_{2}$ ; when $N > 1$ , $D_{1} > D_{2}$ ; when $N \to \infty$ , $τ \to 2$ . UAV cannot carry numerous antennas at the same time due to its limited payload. Therefore, the algorithm has a good performance of low delay when UAV is equipped with four directional antennas to cover 360° airspace. The algorithm not only realizes the full coverage as omni-directional antenna but also the long distance of directional antenna and low-delay information sharing of AANET, and can achieve the optimal performance under the ideal topology.

Performance evaluation

Simulation setup

In this part, OPNET 14.5 is used for simulation and performance analysis. In order to ensure the connectivity of the network, a network topology is established based on the idea of dividing cells. As shown in Figure 9, take the topology of nine nodes in the network as an example to introduce the setup of the simulation. The 3D network topology is mapped to a two-dimensional plane, at which time each node in the network can communicate with up to four nodes at the same time. In order to simplify the simulation model, a relatively uniform network topology is designed. At this time, the network region is composed of several square regions with a side length of 10 km. There is only one node in each region, and the nodes are distributed randomly and evenly in the square region. The communication radius of the nodes is 25 km. The purpose of setting parameters like this is to ensure that the adjacent nodes of any node in the network are within its communication range. In order to avoid the impact of irregular graph on simulation results, the number of nodes selected for simulation is 4, 9, 16, 25, 36, 49, 64, and 81, respectively. And the density of nodes can be kept consistent when the number of nodes in the network is different.

Figure 9.

Topology of nine nodes in the network.

As for the beam formed by the phased-array antenna, the communication radius of all antennas is the same, and the side lobe is ignored. Other parameters in the simulation are set as shown in Table 3.

Table 3.

Simulation parameters.

Definition	Parameters	Values
Beam width of antenna	$θ$	$10 °$
Bandwidth of channel	$B$	$25 Mbps$
Packet size	$p$	$20 kB$
Time slot	$T$	$8 ms$
Amount of nodes	$N$	$4, 9, 16, 25, 36, 49, 64, 81$

Performance indicators

When evaluating the performance of information sharing, two indicators are mainly focused. The first one is the delay of the completion of information sharing, that is, the time taken for all nodes to complete an information sharing. In this article, only the transmission delay of packets is considered and the propagation delay is ignored. The index can be represented by the number of time slots used to complete the information sharing because the algorithm completes the sharing process based on the time slot. The other one is the redundancy of information sharing, which is calculated by the number of packets sent. The power consumption of network information sharing can also be evaluated by the number of packets sent because the unit size model is adopted and only one packet is transmitted for each transmitting beam at a time.

Performance comparison between MLAB and UxDMA

In this part, three variables are counted and compared between MLAB and UxDMA, which are the time slots consumed by the two algorithms, the number of transmitted messages and the redundancy rate, respectively, by simulating the information sharing performance of the two algorithms in the topology. And then, the advantages and disadvantages of the two algorithms are evaluated, respectively.

Figure 10 shows the statistical diagram of the time slots consumed by UxDMA and MLAB for information sharing, when the number of nodes in the network is 4, 16, 25, 36, 49, 64, and 81, respectively, where the abscissa represents the number of nodes in the network, and the ordinate represents the time slots consumed for information sharing. By analyzing the simulation results, these conclusions can be drawn: the time slots required by UxDMA and MLAB both increase with the number of nodes. But the time slots of UxDMA grow almost twice as fast as MLAB. This is because MLAB selects the coloring group containing the largest number of links for communication every time when selecting schedulable links. This method reduces the number of links needed to be colored in the next time slot; it also reduces the probability of link collisions and the number of coloring groups in the meantime. By contrast, UxDMA only randomly selects packets for communication scheduling, so MLAB consumes fewer time slots. Compared with UxDMA, the delay of MLAB is reduced by 49.8% when the number of nodes is 81 in the network. And this gain can be even higher with the number of nodes increases. Therefore, MLAB can effectively reduce the delay of information sharing in the network.

Figure 10.

The relationship between consumption time slots and number of nodes.

Figure 11(a) shows the statistical graph of the number of packets sent, and the rate of message redundancy, respectively, when UxDMA and MLAB complete information sharing. In Figure 11(a), the abscissa represents the number of network nodes, and the ordinate represents the number of packets sent. It can be seen that the number of packets sent by nodes in the network is positively correlated with the number of nodes. When the number of nodes is $N$ , the number of packets sent by MLAB is $N (N - 1)$ . And when the number of nodes is the same, more packets are sent by UxDMA than MLAB. The reason is that the algorithm UxDMA transmits more useless packets which cause more redundancy in the network due to the random selection of links for communication. Since the collision avoidance mechanism is added to MLAB, conflict-free link selection is first carried out during link scheduling, so redundancy is avoided. The comparison of the rate of redundancy is shown in Figure 11(b). The maximum rate of redundancy of UxDMA is 16.2%, while MLAB which takes measures to eliminate transmission redundancy has a rate of redundancy of 0% in information sharing. Based on the analysis of the above results, MLAB effectively eliminates the transmission redundancy of information sharing, transmits fewer packets, and consumes less energy under the same circumstances than UxDMA, and thus improving the network performance.

Figure 11.

Comparison of the number of packets and the rate of redundancy between UxDMA and MLAB: (a) the number of packets and (b) the rate of redundancy.

Performance analysis of MLAB-DS

The consumed time slot by MLAB-DS algorithm was compared with MLAB algorithm through simulation.

Figure 12 shows the relationship between the number of time slots consumed with the number of nodes when MLAB and MLAB-DS are used for information sharing, respectively. It can be seen that MLAB-DS consumes much fewer time slots than MLAB, with maximum reduction of time slots of 54.2% when the number of nodes in network is the same. Actually, in directional transmission, the antenna beam angle will inevitably affect the network performance. MLAB randomly selects the antenna beam angle during communication, resulting in uncontrollable network topology. The quality of topology directly determines the size of delay required for information sharing. But the MLAB-DS dynamically selects the most appropriate antenna beam angle through topology feedback to construct the load-balancing network topology, avoiding the emergence of the worst topology and further reducing the delay required for information sharing. The proposed beam direction can be used to adjust the antenna in the network, so as to further reduce the delay and improve the network performance.

Figure 12.

Comparison of time slots between MLAB and MLAB-DS.

Conclusion

In this article, a low-delay information sharing algorithm based on phase-array antenna for multiple-radio-per-platform networking is proposed. This algorithm takes use of the idea of coloring, and realizes low delay and no redundancy of information sharing by adding special conflict scenario and link group selection method, and provides a feasible solution to this kind of problems in the future. On this basis, a direction selection algorithm is designed according to the variability of direction of the directional antenna, which can further reduce the delay of information sharing. However, the dynamic topology and interference nodes are not considered in this article, which need to be further studied in the future.

Footnotes

Handling Editor: Yanjiao Chen

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This work was supported by the National Natural Science Foundation of China (no. 61671471).

ORCID iD

Ge Lin

References

Rivera

Urquiza-Aguiar

Caldern

, et al. Performance evaluation of an AANET in Quito’s control area. In: International workshop on communication technologies for vehicles, Colmar, 16–17 May. Cham: Springer, 2019, pp.73–85.

Sahingoz

OK.

Networking models in flying ad-hoc networks (FANETs): concepts and challenges. J Intel Robot Syst 2014; 74(1): 513C527.

Kim

Ghayoori

Srikant

RJ.

All-to-All communication in random regular directed graphs. IEEE Trans Netw Sci Eng 2014; 1: 43–52.

Cirullo

Olsen

Meagher

, et al. A solution to network protocol issues for directional ad-hoc networks through topology control and a multiple-radio-per-node architecture. In: MILCOM 2011 military communications conference, Baltimore, MD, 7–10 November 2012. New York: IEEE.

Jeter

Porfiri

Belykh

Network synchronization through stochastic broadcasting. IEEE Control Syst Lett 2017; 2(1): 103–108.

Jagadeesh

Srikanthan

Fast computation of clustered many-to-many shortest paths and its application to map matching. ACM Trans Spatial Algorith Syst 2019; 5(3): 17.

Sinha

Paschos

, et al. Throughput-optimal multihop broadcast on directed acyclic wireless networks. IEEE/ACM Trans Netw 2017; 25(1): 377–391.

Wang

, et al. Energy-efficient transmission with data sharing in participatory sensing systems. IEEE J Select Area Commun 2016; 34(12): 4048–4062.

Huang

Wan

, et al. Minimum latency gossiping in radio networks. IEEE Trans Parallel Distrib Syst 2010; 21(6): 790–800.

10.

Gandhi

Kim

Lee

, et al. Approximation algorithms for data broadcast in wireless networks. IEEE INFOCOM 2009; 11(7): 2681–2685.

11.

Lanotte

Merro

Tini

Equational reasonings in wireless network gossip protocols. Logical Method Comput Sci 2018; 14: 24.

12.

Leme

Ivaki

Laranjeiro

, et al. Analyzing gossip protocols for reliable MANET applications. In: IEEE international conference on EDGE computing, Honolulu, HI, 25–30 June 2017. New York: IEEE.

13.

She

Liu

Quek

TQS

, et al. Ultra-reliable and low-latency communications in unmanned aerial vehicle communication systems. IEEE Trans Commun 2019; 67: 3768–3781.

14.

Sundaresan

Ramachandran

Rangarajan

. Optimal beam scheduling for multicasting in wireless networks. In: International conference on mobile computing and networking, Beijing, China, 20–25 September 2009, pp.205–216.

15.

Dai

Efficient broadcasting in Ad hoc networks using directional antennas. In: NETWORKING 2005. Networking technologies, services, and protocols; performance of computer and communication networks; mobile and wireless communications systems, Waterloo, ON, Canada, 2–6 May 2005, pp.499–510. New York: Springer.

16.

Ghahfarroky

Hendessi

Power control | spatial reusability by using directional antenna in wireless ad hoc networks. In: 18th Iranian conference on electrical engineering, Isfahan, 11–13 May 2010, pp.220–225. New York: IEEE.

17.

Wang

Yang

Near-optimal all-to-all broadcast in multidimensional all-port meshes and tori. IEEE Trans Parall Distrib Syst 2002; 13(2): 128–141.

18.

Ramanathan

A unified framework and algorithm for channel assignment in wireless networks. Wirel Netw 1997; 2(2): 81–94.

19.

Duan

Peng

, et al. An all-to-all broadcasting protocol using directional antennas in multi-hop wireless networks. In: International conference on wireless communications & signal processing (WCSP), Nanjing, China, 15–17 October 2015. New York: IEEE.

20.

Gerasimenko

Moltchanov

Gapeyenko

, et al. Capacity of multiconnectivity mmWave systems with dynamic blockage and directional antennas. IEEE Trans Veh Technol 2019; 68(4): 3534–3549.

21.

Gasieniec

Potapov

Qin

Time efficient centralized gossiping in radio networks. Theoretical Comput Sci 2007; 383(1): 45–58.

22.

Dholey

Khatun

. Reduction of blockage node and hidden terminal problem of CSMA/CA MAC protocol using directional antenna. In: 2nd IEEE international conference on parallel, distributed and grid computing, Solan, India, 6–8 December 2012, pp.741–746. New York: IEEE.