Clustering is an effective method for improving the performance of large scale mobile ad hoc networks. However, when the moving speed is very fast, the topology changes quickly, which leads to frequent cluster topology updates. The drastically increasing control overheads severely threaten the throughput of the network. SCBCS (Signal Characteristic Based Cluster Scheme) is proposed as a method to potentially reduce the control overheads caused by cluster formation and maintenance in aeronautical ad hoc networks. Each node periodically broadcasts Hello packets. The Hello packets can be replaced by data packets, which preserve bandwidth. The characteristics of the received packets, such as the Doppler shift and the power of two successive Hello packets, help to calculate the relative speed and direction of motion. Then, the link connection lifetime is estimated by the relative speed and direction of motion. In the clustering formation procedure, the node with the longest estimated link connection time to its onehop neighbors is chosen as the cluster head. In the cluster maintenance procedure, reaffiliation and reclustering schemes are designed to keep the clusters more stable. The reclustering phenomenon is reduced by limiting the ripple effect. Simulations have shown that SCBCS prolongs the link connection lifetime and the cluster lifetime, which can reduce the topology update overheads in highly dynamic aeronautical ad hoc networks.
1. Introduction
C
lustering is an efficient network topology management method, and the hierarchical structure obtained using the clustering algorithm can largely improve the performance of mobile ad hoc networks. Many different clustering schemes have been proposed. Some detailed surveys of existing clustering schemes can be found in
[1]

[3]
. Nodes in the same cluster can exchange messages directly, while nodes in different clusters are able to communicate through cluster heads or gateway nodes. Compared with the normal ad hoc networks, the aircrafts in aeronautical ad hoc networks move at a very high speed, typically from 700 km/h to l000 km/h
[4]
. Thus, the communication in aeronautical ad hoc networks can be extremely unstable, as the network topology frequently changes. To maintain stable clusters in aeronautical ad hoc networks, mobility parameters must be taken into account for cluster formation and maintenance. The cluster schemes that are determined by the mobility behavior of the mobile entity are called mobilityaware clustering schemes. The main motivation behind the mobilityaware clustering scheme is to group mobile entities with similar speeds into the same cluster
[1]
. Then, the intracluster links can become more tightly connected. Furthermore, the reaffiliation and reclustering rate can be decreased. This paper focuses on the development of a more stable clustering scheme for highly mobile aeronautical ad hoc networks. The proposed clustering scheme, SCBCS, uses the signal characteristics of received packets to accurately calculate the relative moving speed and moving direction, providing accurate information for the formation and maintenance of clusters. Furthermore, SCBCS is a specially designed distributed clustering scheme, for which the local reelection of one cluster head will not affect the structure of many clusters and arouse the cluster head reelection over the whole network.
In Section 2, we review the previous work that has been conducted on clustering algorithms. Section 3 introduces the mobility model used in this paper. Section 4 calculates the relative speed using signal characteristics. Section 5 estimates the link connection lifetime using relative speed and signal power. In Section 6, the clustering formation and maintenance algorithm is presented in detail. In Section 7, the simulation results of our study are presented. Finally, Section 8 concludes this paper.
2. Related Work
There have been some mobilityaware clustering algorithms that have been previously proposed in
[5]

[18]
. The clustering scheme proposed in
[5]
has a simple cluster formation and uses asynchronously event triggered cluster maintenance, which eliminates the "ripple effect" and incurs much less overhead. However, as the cluster heads are predefined in
[5]
, this scheme is not practical for randomly deployed mobile ad hoc networks. A well known mobility metricbased clustering scheme called MOBIC
[6]
uses the power of two successively received packets to evaluate the relative motion between two mobile entities. MOBIC does not calculate the accurate distance or speed using the characteristic of the received signal because on city streets the signal is likely to suffer from high attenuation. MOBIC is more feasible and effective in the scenario that the nodes move with similar speed and direction. If mobile nodes move randomly and change their speeds frequently, MOBIC’s performance may be greatly degraded
[1]
. The clustering scheme proposed in
[7]
takes into account the speed difference among vehicles as well as their position and direction during the cluster formation process, but its mobility model is only applicable for a highway environment. MWC (Multiparameter Weighted Clustering)
[8]
considers residual power, connectivity, and average mobility in clustering formation and maintenance. Its comprehensive performance is good, but MWC is not specially designed for a highly dynamic network. The algorithm in
[9]
finds clusters that minimize both the relative mobility and the distance from each cluster head to its cluster members. However, it will not cluster vehicles moving in opposite directions; this scheme is not necessary when the node’s direction of motion changes frequently. MCFA
[10]
uses the learning automaton theory
[11]
to choose an optimal clustering scheme from a finite set of allowed actions through repeated interactions. MCFA is suitable for the scenario that the direction of motion and mobility speed is assumed to be random variables with unknown distributions. However, it does not resolve the problem of how to efficiently exchange mobility information. The clustering scheme in
[12]
improves the search efficiency and scalability of MANETs by clustering nodes based on the trust mechanism. In
[12]
, clusters refer to node groups where nodes are tightly connected based on a trust relationship and share the same context of trust. The clustering scheme in
[12]
is suitable for the highly dynamic characteristic of MANETs. However, it assumes that a node can always obtain the interaction history of other nodes by searching the whole network; when the cluster size increases, the control overhead will increase drastically.
In most mobilityaware clustering schemes, the cluster head is assumed to know the current mobility information (position, speed and movement direction) of each of its members. Due to the high moving speeds and frequently changing direction of motion, the network topology may change frequently. If the member mobility information is not updated in time, the clustering performance decays dramatically. However, it will cost extra bandwidth to exchange control information to update the cluster member table and cluster head table in each cluster head. So it is important and necessary to develop an efficient way to obtain the mobility information without frequently exchanging control packets, including explicit position, speed or moving direction information. There are several clustering schemes that use signal characteristics such as power and Doppler shift to obtain position or speed information. The advantages of these schemes are: (1) They can be used in the case that GPS or other satellite navigation systems are not available. (2) The Doppler shift and power can be obtained from the data packets, which reduces the amount of periodically broadcasted topology control packets. In
[13]
, an iterative Doppler shift estimator is proposed that is insensitive to SNR at a wide range of velocities and SNR, particularly in the very low SNR cases. We assume that the Doppler shift and power are measured without mistakes. In
[14]
, the station handoff in railway communication is implemented based on the received averaged signal strength from the adjacent base station and the Doppler shift from the serving base station. SECA (Signal Efficient Clustering Algorithm)
[15]
chooses the nodes with low mobility, more neighbors, high residual battery energy and high signal strength as cluster heads. In SECA, signal strength is an important clustering criterion, but signal strength does not fully reflect the mobility of the moving entities. DDVC (Dynamic Doppler Velocity Clustering)
[16]
is a stable clustering scheme using Doppler shift to estimate relative velocity. DLDC (Dynamic Link Duration Clustering)
[16]
is also a stable clustering scheme that is based on the estimated link expiration time. However, both DDVC and DLDC only apply to the mobile entity that moves in a relatively linear path without frequently changing its direction and speed. DSRC (Dedicated ShortRange Communications)
[17]
measures the Doppler shift of the carrier of DSRC signals. Dopplerbased rangerating is verified in practice using DSRC transceivers. Based on the speed calculated by Doppler shift, an improvement of up to 48% over the GPS accuracy is achieved. In MPBC (Mobility PredictionBased Clustering)
[18]
, the Doppler shifts of periodically exchanged Hello packets between neighboring nodes are used to estimate their relative speeds. The nodes that have the smallest relative mobility in their neighborhoods are selected as the cluster head. However, the speed calculation is not precise in
[18]
. If formula (7) in
[18]
is satisfied, by law of cosines, we find that any two nodes in the network should move at a same beeline within the time between two successive Hello packets. This assumption is not practical in most aeronautical ad hoc networks. Although the simulation results in
[18]
show that MPBC can adapt to highly dynamic ad hoc networks, the impractical assumption constrains its performance.
3. Mobility Model
The Reference Region Group Mobility (RRGM) model
[19]
is a generic mobility model that can be used for both entity mobility and group mobility. In the RRGM model, group partition and merger will occur dynamically and randomly. A group may split into multiple smaller groups or a number of groups may merge into a larger one.
In this paper, we modify the PRGM model to adapt it to a highly dynamic scenario within which both single entity mobility and group mobility exist. The new mobility model is expressed as follows:
(1) In the initial stage, all the nodes are deployed randomly in the simulation region. Several circular regions whose radius is equal to the communication range
R
are deployed randomly in the simulation region, too. The circular regions are not overlapped to each other. All the nodes in the same circular region form a group. Each node that does not locate in the circular regions is seemed as a group.
(2) Every group is associated with a reference region. The members in the same cluster will randomly select a location within their corresponding reference region as its target and move towards this point with varying speeds. Once a node arrives at the reference region, it will move around within the region waiting for the arrival of other nodes. After all the nodes of a cluster arrive at the reference region, a new reference region is assigned to the group.
(3) At a constant time interval, a new destination is generated. The group that is closest to the new destination is chosen to split into two smaller groups. A number of nodes in the original group are randomly selected to form a new group. Then, each group is assigned a new reference region.
(4) At a constant time interval, a same reference region is assigned to two groups, whose reference regions are closest to each other. After the two groups arrive at their former regions, they merge into a new group and a new reference region is assigned to the new group. Before their merger, if a group arrives earlier than another group, its members move around within its corresponding region waiting for another group’s arrival to the corresponding region.
4. The Relative Speed Calculation
The attenuation model adopts the FreeSpace Path Loss model
[20]
as follows:
P_{r}
is the received power,
P_{t}
is the transmitting power,
G_{t}
is the transmitting antenna gain,
G_{r}
is the receiving antenna gain,
λ
is the wavelength,
d
is the distance between the transmitter and the receiver.
Fig. 1
illustrates the relative mobility of
n_{i}
and
n_{j}
. In fact, node
n_{i}
and node
n_{j}
are both mobile, but we see
n_{i}
as static and
n_{j}
as mobile for convenience. When node
n_{j}
moves from
b
to
c
with a relative speed
v_{r}
, we call it a receding scenario. When node
n_{j}
moves from
c
to
b
with a relative speed
v_{a}
, we call it an approaching scenario.
Relative mobility
n_{j}
sends a Hello packet at
b
and
c
, respectively.
n_{i}
receives the packets.
Δt
is the time interval between two Hello packets. By (1), the received power of the signal sent at
b
is
, the received power of the signal sent at
c
is
.
d_{ab}
is the distance between
a
and
b
,
d_{ac}
is the distance between
a
and
c
. Then,
d_{ab}
and
d_{ac}
can be expressed as:
Suppose
f
is original carrier wave frequency at sender
n_{j}
,
f’
is the received carrier wave frequency at receiver
n_{i}
. If
f
>
f
', it means that the transmitter
n_{j}
and the receiver
n_{i}
are receding from each other. Contrarily, if
f
>
f
', it means that the transmitter
n_{j}
and the receiver
n_{i}
are approaching to each other. According to Doppler effect, in receding scenario the following expression is obtained:
In (4),
V_{c}
is the speed of light and
v_{r}
is the relative speed in receding scenario. By (4), the receding speed is obtained:
From the law of cosines, we can obtain the following:
In (6)
d_{bc}
is the distance between
b
and
c
. We assume that in the transmission time interval
Δt
,
n_{j}
would not change its moving direction, then the distance from
b
to
c
can be expressed as：
Substituting (7) in (6) and then substituting (6) in (5), the following expression is obtained:
Take (2) and (3) into (8), and we obtain the following:
In the approaching scenario,
n_{j}
first locates at
c
, and then it moves to
b
. Like the speed calculation in receding scenario, the relative moving speed can be calculated as:
5. The Link Connection Lifetime Estimation
Mobility prediction of moving entities plays a major role in efficient clustering of aeronautic ad hoc networks. This will allow for better planning and improved overall QoS in terms of continuous service availability and less topology control overheads. We can estimate the maximum link connection lifetime based on the present relative speed and the Doppler frequency shift. The communication link interruption happens under the condition that the two nodes are at their maximum communication range. If the two nodes keep their present relative speed and direction, the maximum link connection time can be calculated. Of course, if the nodes will change their speed and direction of motion randomly and quickly, the estimated maximum link connection lifetime is not likely to be accurate. The estimated time is just used as a metric to measure the link stability at a specific time.
 5.1 Receding scenario
In
Fig. 2
, like the description of
Fig. 1
, we assume that
n_{i}
is static and located at a;
n_{j}
is first located at
b
and then it moves to
c
. If
n_{j}
will not change its present speed and direction of motion, the maximum link connection time in the receding scenario is calculated as:
Estimation in the receding scenario
d
is located at the edge of the communication range,
d_{cd}
is the distance between
c
and
d
,
d_{bd}
is the distance between
b
and
d
.
In Δ
abc
, from the law of cosines, we can obtain the following:
Take (9) into (7), and we get the distance between
b
and
c
:
Take (2), (3) and (13) into (12), and we get:
In Δ
abd
, from the law of cosines, we can obtain the following:
As illustrated in
Fig. 2
,
d_{bd}
is the distance between
b
and
d
,
d_{ad}
is the distance between
a
and
d
. Actually,
d_{ad}
is the radius of the cluster, so (15) can be rewritten as:
In (16),
R
is the maximum communication range. (16) can be transformed as:
Solve the quadratic equation (17), and
d_{bd}
is obtained as:
The value of
d_{bd}
is single, so the indetermination in (18) should be eliminated.
If
, the following expression can be obtained:
By (19), we obtain that
d
^{2}
_{ab}
=
d
^{2}
_{ab}
cos
^{2}
∠
abd
+
d
^{2}
_{ab}
sin
^{2}
∠
abd
>
R
^{2}
. However,
d_{ab}
is definitely shorter than the communication range
R
. So (19) will never be right. Then,
is the final right expression. At last, the definite answer of quadratic equation (17) is:
Actually, ∠
abd
and ∠
abc
are the same angle, so:
Take (20), (21), (14) and (2) into (11), the maximum link connection lifetime in the receding scenario is calculated as:
In (22),
.
 5.2 Approaching Scenario
In
Fig. 3
, we assume that
n_{i}
is still static and located at a,
n_{j}
is first located at
c
and then it moves to
b
. If
n_{j}
will not change its present speed and direction of motion, the maximum link connection time in the approaching scenario is calculated as:
Prediction in the approaching scenario
d_{bd}
is the distance between
b
and
d
in
Fig. 3
.
In approaching scenario, the distance from
b
to
c
can be expressed:
Take (2), (3), (24) and (10) into (6), cos∠
abc
in
Fig. 3
is obtained as:
In Δ
acd
, from the law of cosines, we can obtain the following:
It is presented in
Fig. 3
that cos∠
acb
=cos∠
acd
, and
d_{ad}
=
R
. We can calculate
d_{cd}
by (25) and (26), which adopts the same way that uses (14) and (16) to calculate
d_{bd}
.
Take (3), (25), and (27) into (23), the maximum link connection lifetime in the approaching scenario is calculated as:
v_{a}
is obtained from (10).
 5.3 Link Connection Lifetime Update
By (22) and (28), the estimated link connection lifetime of node
n_{i}
toward
n_{j}
is:
If
n_{j}
and
n_{i}
are in the approaching scenario, the link connection lifetime between them is
t_{a}
. If
n_{j}
and
n_{i}
are in the receding scenario, the link connection lifetime between them is
t_{r}
. If
n_{j}
and
n_{i}
are static relatively, their link connection lifetime is infinite. All nodes in the network periodically broadcast the Hello packets and build their neighbor lists based on the received Hello packets from each other. When the network is first established, all the nodes are in the orphan state. After two successive Hello packets from the same neighbor
n_{j}
are received, node
n_{i}
estimates the link connection lifetime between
n_{i}
and
n_{j}
to create an entry of
n_{j}
in
n_{i}
’s neighbor list. The link connection lifetime is updated each time when a new Hello packet is received from node
n_{j}
.
6. Clustering Scheme
The SCBCS clustering algorithm aims to find the cluster head that has the longest link connection lifetime to its onehop members. Suppose
N_{p}
is a set of nodes whose distance to
n_{i}
is approaching to the maximum distance
R
and their estimated link connection lifetime toward
n_{i}
is approaching to zero. Any node
n_{j}
∈
N_{p}
is not likely to be a member of
n_{i}
. So there is no need to consider any node
n_{j}
∈
N_{p}
when calculating the metric to measure the degree that
n_{i}
is appropriate to be a cluster header.
Table 1
shows some notations and their corresponding definition used in Section 6.
The notation definitions
The distance of these nodes to
n_{i}
is longer than
d
_{max}
, and the estimated link connection lifetime toward
n_{i}
is shorter than
t
_{min}
. Suppose
N_{ni}
is a set of
n_{i}
's onehop neighbors. Any node
n_{i}
in the network gathers its onehop neighbors' distance, mobility and link stability information by the method shown in Sections 4 and 5 of this paper. When
n_{i}
calculates its degree to become a cluster head, it checks its onehop neighbor list and excludes any node
n_{j}
∈
N_{p}
from measuring the degree that
n_{i}
is appropriate to be a cluster header.
n_{i}
's degree to be a cluster at time
t
is calculated as the sum of its onehop neighbors’ estimated link lifetime:
In (30)
T_{s}
is the time threshold. The larger
W_{ni}
(
t
) is, the more
n_{i}
is appropriate to become a cluster head. In (29), the estimated link lifetime may approach infinite when the velocity of
n_{i}
and
n_{j}
are very similar. Thus, if the estimated link lifetime
T_{ij}
is longer than
T_{s}
, we think that it is equal to
T_{s}
in (30).
 6.1 Cluster Formation
When the network is first established, all the nodes are in the orphan state. The cluster formation procedure should follow the following rules:

(a) Any nodenicalculates itsWni(t) and broadcasts it to its onehop neighbors in the Hello packet.Wni(t) is updated based on the latest neighbor information. Upon receivingWni(t) from its neighbors, nodenkcompares them with its ownWnk(t') . If itsWnk(t') is the longest, nodenkbecomes a cluster head and broadcasts an announcement. Otherwise, nodenkwaits for the cluster head announcements from the other nodes.

(b)nkmust be located at the edge of two different group of nodes with different group mobility. Whennkfinds that most of the relative speeds of its onehop neighbors separately approach two different speeds,nkwill not participate in the competition to become a cluster head. This scheme helps to accelerate the formation of a cluster.

(c) If nodenkreceives more than one cluster head announcement,nkselects the node that can provide it with the longest link connection lifetime as its cluster head.

(d) If nodenkdoes not receive any cluster head announcement,nkbecomes a cluster itself.
 6.2 Cluster Maintenance
In the cluster maintaining stage, the clusteringrelated control overhead can be reduced by limiting reaffiliation and reclustering events through the estimated mobility information presented in Sections 4 and 5 of this paper.
 6.2.1 Reaffiliation scheme
When a cluster member moves out of its cluster head's communication range or an orphan node joins an established cluster, reaffiliation occurs. Due to the limited communication range and dynamic node mobility, an established association between a cluster member and its cluster head may be interrupted after the cluster formation stage.
Some cluster members may receive the announcement of several cluster heads; they choose the optimal cluster head using the scheme described in Section 6.1. These cluster members keep the cluster head information they have heard if the neighboring cluster head can provide an estimated link connection lifetime longer than
t
_{min}
. The estimated link connection lifetimes are updated when the corresponding Hello packets are received. When a cluster member
n_{k}
finds the following phenomenon in its cluster, it informs its present cluster head that it is leaving.

a)nkfinds that its estimated link connection lifetime toward its present cluster head is shorter thantmin.

b)nkis on the edge of the cluster. The distance betweennkand its cluster head is longer thandmax.
If
n_{k}
is located in the communication coverage of other cluster heads, it sends a join requisition to the neighboring cluster head that can provide the longest estimated link connection lifetime. Before
n_{k}
moves off of the present cluster, it will not be a member of another cluster. If
n_{k}
cannot find a better cluster head, it will stay an orphan and keep broadcasting Hello packets while waiting for Hello packets from the other heads.
 6.2.2 Reclustering scheme
There are three main reasons that can lead to reclustering: cluster partition, cluster merger and headmember status rotation.
 1) Cluster Partition
If the cluster head of
C
finds its members have the following three characteristics, it broadcasts a message to its members that the original cluster
C
no longer exists.

a) Some of its members have a similar mobility pattern, such as similar relative speeds and similar distances to the header. The members that have the similar mobility are called a group.

b) There exists at least a group, and over half of its members' estimated link connection lifetime toward the header is shorter thantmin.

c) Each group at least contains more than ⎾βNc⏋ entities, where ⎾*⏋ means the minimum integer that is larger than *.
Then, the clustering formation stage described in Section 6.1 of this paper is begun. Nodes in cluster
C
can join other clusters or send special cluster head announcements to form new clusters themselves. When a node in cluster
C
calculates its average link connection lifetime, it only calculates its onehop neighbors in
C
. Only the nodes in cluster
C
can join the cluster of which the cluster head is also a node in cluster
C
. This scheme decreases the ripple effect that can be caused by local reclustering.
 2) Cluster Merger
When a cluster head receives other clusters' announcements or Hello packets, it means that the cluster head moves into another head's communication range. If this phenomenon only lasts for a short time, the reclustering will not happen. Each cluster head calculates the estimated link connection lifetime toward other cluster heads and some of the cluster members. If the head
H_{i}
of cluster
C
finds the following condition is satisfied, it broadcasts a message to its members and nearby clusters that a new cluster is generating and reclustering should be performed.

a) The estimated link connection lifetime toward another headHjis longer thantx.

b) There are more than half ofHj's members whose estimated link connection lifetime towardHiis longer thantx.
The clustering formation stage described in Section 6.1 of this paper is begun. When a node in the previous two or more clusters calculates its average link connection lifetime, it only calculates its onehop neighbors in the previous clusters. Only the nodes in previous clusters can join the cluster of which the cluster head is also a node in previous clusters. This scheme decreases the ripple effect caused by the local reclustering.
 3) HeadMember Status Rotation
The mobility of the cluster members and their cluster head changes with time. A cluster head may no longer be appropriate for being a head when its average link connection lifetime decreases drastically and it moves to the edge of the cluster. In this scenario, a new cluster head should be generated to keep a stable clustering relationship over the long term. After a cluster is established, the cluster head still updates its member list and the relative speed to the members based on the information included in the received Hello packets. When a cluster head
H_{i}
finds the following phenomenon in its cluster, it broadcasts an announcement to abandon the cluster head status.

a) The degree thatHiis suitable to be a cluster head is calculated periodically with time intervalTaccording to (30). The decline between two successive degrees thatHiis suitable to be a cluster head is larger thanγ.

b) There are more than half of its members whose distance to the head is longer thandmax.
Then, the cluster formation procedure starts.
7. Simulation and Analysis
We consider an aeronautical ad hoc network, where
N
= 100 nodes are distributed in a 100 km × 100 km area.
d
_{max}
=0.8
R
,
,
β
=0.2,
γ
=30 s. The initial positions of the nodes are randomly distributed, and their movements follow the model described in Section 3 of this paper. The minimum speed is 200 m/s. The simulations are carried out based on an open source Matlab package called “Wireless Network Simulator”
[21]
. The MAC protocol is based on the CSMA/CA mechanism. The modulation type is BPSK. The carrier frequency is 1GHz and the transmission rate is 500kbit/s. We change the transmission power to control the communication range. The channel fading adopts the freespace path loss model and the channel noise is neglectable.
To assess the performance of the proposed SCBCS scheme, we make simulations and conduct a comparative analysis of MOBIC
[6]
, DLDC
[16]
, MPBC
[18]
, SECA
[15]
, MWC
[8]
and SCBCS. In the above algorithms, only SECA and MWC consider the residual battery energy in the cluster head election. In our study, we assume that the energy is sufficient during the simulation time. Thus, we do not consider the effect of residual battery energy and set the weighting factor of the residual battery energy to zero in
[15]
and
[8]
to choose a cluster head. MWC has two types of algorithms, so we choose type
b
to simulate.
As shown in
Fig. 4
, the SCBCS scheme provides a longer average link connection lifetime than MOBIC, DLDC, MPBC, SECA and MWC when communication range
R
=20 km. This indicates that SCBCS is more adaptable to a highly dynamic mobility scenario. It can be noted that the average connection lifetime of MOBIC experiences a relatively sharp decline when the maximum speed
v
_{max}
increases. This is because MOBIC is designed for networks with obvious group mobility behavior. Similarly, the average DLDC connection lifetime experiences a relatively sharp decline when
v
_{max}
increases. That is because DLDC is designed only for a pseudolinear mobility scenario. SECA is liable to choose the node with low mobility and high connectivity to be the cluster head. The link lifetime of SECA is between that of DLDC and MOBIC. SCBCS, DLDC and MWC are designed for highly dynamic networks, so the decline rate of their connection lifetime is slower than the lifetimes of the other three schemes. Although MPBC calculates the relative speed using Doppler shift and signal power, its calculated speed is not as precise as that of SCBCS. MWC selects a node with a strong speed correlation to the group and high connectivity to be the cluster head. The speed information of MWC is directly transmitted, so its average link lifetime is longer than that of MPBC. SCBCS has a stricter rule to generate and maintain a cluster, which chooses more stable members to form a cluster. Thus, SCBCS has the longest average link connection lifetime among all of the above schemes.
Average link connection lifetime versus maximum speed
The communication range
R
is 20km in
Fig. 5
. As shown in
Fig. 5
, the lifetime of all the schemes decreases as maximum speed increases. This is because higher speed leads to more dynamic relative location changes between any two nodes in the network. When
v
_{max}
is small, cluster heads are not likely move to each other's coverage area. Additionally, an established cluster is not likely to divide into several partitions. Therefore, reclustering is not often triggered in a scenario involving a relatively low maximum speed. When
v
_{max}
increases, the cluster heads are more likely to move into each other's coverage area, and the chance of cluster merger increases. Thus, the incidence of reclustering increases when
v
_{max}
increases, which reduces the cluster head lifetime. Due to SCBCS's severe cluster formation and maintenance rules and the accurate calculation of the relative speed, SCBCS is the most suitable scheme for a highly mobile scenario.
Average cluster head lifetime versus maximum speed
Fig. 6
shows the average connection lifetime of the schemes for a varying communication range
R
when
v
_{max}
=300m/s. As
R
increases, the nodes are less likely to move out of the coverage area of their associated cluster heads, and therefore, the connection lifetime is longer. SCBCS’s average link connection lifetime is longest; this is because SCBCS uses the estimated link connection lifetime as the metric to form a cluster and excludes the unsuitable nodes to join a cluster.
Average link connection lifetime versus communication range
Fig. 7
shows the average cluster head lifetime versus node communication range
R
for different schemes when
v
_{max}
=300m/s. The SCBCS scheme shows better average cluster head lifetime performance than MOBIC, DLDC, MPBC, SECA and MWC. When
R
increases, the performance gap between any pair of the above schemes becomes small. That is because the increased
R
reduces the effect of high mobility, which diminishes the advantage or disadvantage of one scheme to another.
Average cluster head lifetime versus communication range
In
Fig. 8
, the communication range
R
is 20 km. It can be noted that when the maximum speed increases, the average number of nodes per cluster decreases slightly. This is because when maximum speed increases, there are more chances that a node can move out of a cluster, which results in more orphan nodes and slightly less average members per cluster. SECA and MWC have the largest number of members. This is because both SECA and MWC choose the node with high connectivity as the cluster head. The average number of members per cluster of DLDC and SCBCS is lower than MOBIC's and MPBC's. That is because both DLDC and SCBCS follow strict rules to form and maintain a cluster. SCBCS has the strictest rules so it produces fewer members per cluster compared with MOBIC, DLDC, MPBC, SECA and MWC.
Average number of members per cluster versus maximum speed
Fig. 9
shows that the average number of members per cluster increases when the communication range increases. The maximum speed is
v
_{max}
=300m/s in
Fig. 9
. SECA and MWC are likely to choose the node with high connectivity as the cluster head so their average numbers of members per cluster are largest. MOBIC and MPBC have nearly the same average members per cluster, and their average number of members per cluster is slightly smaller than SECA and MWC when the communication range is short. The number of nodes in the simulation region remains constant. Thus the differences among MOBIC, MPBC, SECA and MWC decline when the communication range increases. MOBIC and MPBC have more members in a cluster than SCBCS because they do not have a rule to exclude the unsuitable nodes from joining a cluster. SCBCS has the strictest rule to form a cluster, so its average number of members per cluster is smallest.
Average members per cluster versus communication range
8. Conclusion
We have proposed an SCBCS scheme for highly dynamic aeronautical ad hoc networks. The proposed clustering scheme uses the Doppler shift and the power of the received signal to estimate link connection lifetime. Then, we used the estimated lifetime to determine the appropriate nodes for a cluster to maintain the established clusters. The proposed clustering scheme can enhance the network stability by enhancing the link connection lifetime and the cluster lifetime. In the future, we would like to study the clusterbased routing algorithm. Routing algorithms and clustering algorithms can share the same Hello packets, which improves the whole network performance.
BIO
Yu Tian received the B.E. and M.E. degrees in Communication and Information System from Air Force Engineering University in 2008 and 2011, respectively. He is currently working toward the Doctor’s degree in Air Force Engineering University. His research interests include channel coding and Ad Hoc networks. Email: labyahoo@126.com
Linhua Ma received the B.E. and M.E. degrees from Air Force Engineering University in 1988 and 1991, respectively. He received the Dr.E degree from Xidian University. He now is a professor of Air Force Engineering University. His research interests include channel coding, image processing, and wireless networks. Email: land_max@126.com
Le Ru received the B.E. degrees from Air Force Engineering University in 1999 and 2002, respectively. He received the Dr.E degree from Xidian University. He now is a associate professor of Air Force Engineering University. His research interests include antijamming communication and wireless networks. Email: rule @163.com
Hong Tang received the B.E. and M.E. degrees from Air Force Engineering University in 1989 and 1992, respectively. He now is a senior experimentalist of Air Force Engineering University. His research interest is antijamming communication. Email: haiertang11@126.com
Bo Song received the B.E. and M.E. degrees from Air Force Engineering University in 1990 and 1993, respectively. He now is a associate professor of Air Force Engineering University . His research interest is antijamming communication. Email: songb21@126.com
Yu Jane Y.
,
CHONG Peter H. J.
2005
“A survey of clustering schemes for mobile ad hoc networks”
IEEE Communications Surveys & Tutorials
Article (CrossRef Link)
7
(1)
32 
48
DOI : 10.1109/COMST.2005.1423333
Chinara Suchismita
,
Rath Santanu Kumar
2009
“A survey on onehop clustering algorithms in mobile ad hoc networks”
Journal of Networks and Systems Management
Article (CrossRef Link)
17
(12)
183 
207
DOI : 10.1007/s1092200991237
Mehta Sheetal
,
Sharma Priyanka
,
Kotecha Ketan
2011
“A survey on various cluster head election algorithms for MANET”
in Proc. of 2011 Nirma University International Conference on Engineering
December 810
Article (CrossRef Link)
1 
6
Zhou Jinhua
,
Leilei
,
Liu Weikang
,
Tian Jiamin
2012
“A simulation analysis of nodes mobility and traffic load aware routing strategy in aeronautical Ad hoc networks”
in Proc. of Proceedings of 2012 9th International Bhurban Conference on Applied Sciences & Technology
January 912
Article (CrossRef Link)
423 
426
Li Jianbo
,
Jiang Shan
2011
“A scalable clustering algorithm in dense mobile sensor networks”
Journal of Networks
Article (CrossRef Link)
6
(3)
505 
512
Basu P.
,
Khan N.
,
Little T.D.C.
2001
“A mobility based metric for clustering in mobile ad hoc networks”
in Proc. of Distrib. Comput. Syst
April 1619
Article (CrossRef Link)
413 
418
Rawashdeh Zaydoun Y
,
Mahmud Syed Masud
2012
“A novel algorithm to form stable clusters in vehicular ad hoc networks on highways”
EURASIP Journal on Wireless Communications and Networking
Article (CrossRef Link)
2012
(15)
1 
13
Feng Wenjiang
,
Liu Gaixia
,
Liao Yuxiang
,
Zhao Wei
2013
“A multiparameter weighted clustering algorithm for mobile ad hoc networks”
Journal of Information & Computational Science
Article (CrossRef Link)
10
(17)
5457 
5466
DOI : 10.12733/jics20102385
Hassanabadi B.
,
Shea C.
,
Zhang L.
,
Valaee S.
2014
“Clustering in vehicular ad hoc networks using affinity propagation”
Ad Hoc Networks
Article (CrossRef Link)
13
(PART B)
535 
548
DOI : 10.1016/j.adhoc.2013.10.005
Torkestani Javad Akbari
,
Meybodi Mohammad Reza
2011
“A mobilitybased cluster formation algorithm for wireless mobile adhoc networks”
Cluster Computing
Article (CrossRef Link)
14
(4)
311 
324
DOI : 10.1007/s105860110161z
Thathachar M.A.L.
,
Harita B.R.
1987
“Learning automata with changing number of actions”
IEEE Trans. Syst. Man and Cybern.
Article (CrossRef Link)
17
(6)
1095 
1100
DOI : 10.1109/TSMC.1987.6499323
Wang Wei
,
Zeng Guosun
,
Yao Jing
,
Wang Hanli
,
Tang Daizhong
2012
“Towards reliable selfclustering mobile ad hoc networks”
Computers and Electrical Engineering
Article (CrossRef Link)
38
(3)
551 
562
DOI : 10.1016/j.compeleceng.2011.11.018
Hua Jingyu
,
Bao Junhua
,
Xu Zhijiang
,
Meng Limin
,
Li Gang
2008
“Doppler shift estimation for low signalnoiseratio environment in mobile communication systems”
in Proc. of International Conference on Wireless Communications, Networking and Mobile Computing
October 1214
Article (CrossRef Link)
1 
4
Wu Duanpo
,
Jin Xinyu
,
Jiang Lurong
2014
“Analysis of handoff algorithmbased on Doppler effect and RSSI measurements in GSMR network”
Journal of the Chinese Institute of Engineers
Article (CrossRef Link)
37
(3)
325 
331
DOI : 10.1080/02533839.2013.800274
Tan Xiaolin
,
Xiong Zhongyang
,
He Yun
2013
“Signal attenuationaware clustering in wireless mobile ad hoc networks”
Journal of Networks
Article (CrossRef Link)
8
(4)
796 
803
DOI : 10.4304/jnw.8.4.796803
Sakhaee Ehssan
,
Jamalipour Abbas
2008
“Stable clustering and communications in pseudolinear highly mobile ad hoc networks”
IEEE Transactions on Vehicular Technology
Article (CrossRef Link)
57
(6)
3769 
3777
DOI : 10.1109/TVT.2008.919606
Alam Nima
,
Balaei Asghar Tabatabaei
,
Dempster Andrew G.
2011
“A DSRC Dopplerbased cooperative positioning enhancement for vehicular networks with GPS availability”
IEEE Transactions onVehicular Technology
Article (CrossRef Link)
60
(9)
4462 
4470
DOI : 10.1109/TVT.2011.2168249
Ni Minming
,
Zhong Zhangdui
,
Zhao Dongmei
2011
“MPBC: a mobility predictionbased clustering scheme for ad hoc networks”
IEEE Transactions on Vehicular Technology
Article (CrossRef Link)
60
(9)
4549 
4559
DOI : 10.1109/TVT.2011.2172473
Ng J. M.
,
Zhang Y.
2005
“A mobility model with group partitioning for wireless ad hoc networks”
in Proc. of IEEE International Conference on Information Technology and Applications
July 47
Article (CrossRef Link)
289 
294
Goldsmith Andrea
2005
Wireless Communication
Cambridge University Press
Cambridge
Wirelss Network Simulator in Matlab. [Online].
http:// sourceforge.net/projects/wirelessmatlab/