Advanced
A Signal Characteristic Based Cluster Scheme for Aeronautical Ad Hoc Networks
A Signal Characteristic Based Cluster Scheme for Aeronautical Ad Hoc Networks
KSII Transactions on Internet and Information Systems (TIIS). 2014. Oct, 8(10): 3439-3457
Copyright © 2014, Korean Society For Internet Information
  • Received : April 07, 2014
  • Accepted : August 26, 2014
  • Published : October 28, 2014
Download
PDF
e-PUB
PubReader
PPT
Export by style
Share
Article
Author
Metrics
Cited by
TagCloud
About the Authors
Yu Tian
Linhua Ma
Le Ru
Hong Tang
Bo Song

Abstract
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 one-hop neighbors is chosen as the cluster head. In the cluster maintenance procedure, re-affiliation and re-clustering schemes are designed to keep the clusters more stable. The re-clustering 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.
Keywords
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 mobility-aware clustering schemes. The main motivation behind the mobility-aware clustering scheme is to group mobile entities with similar speeds into the same cluster [1] . Then, the intra-cluster links can become more tightly connected. Furthermore, the re-affiliation and re-clustering 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 re-election of one cluster head will not affect the structure of many clusters and arouse the cluster head re-election 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 mobility-aware 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 metric-based 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 (Multi-parameter 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 mobility-aware 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 Short-Range Communications) [17] measures the Doppler shift of the carrier of DSRC signals. Doppler-based range-rating 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 Prediction-Based 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 Free-Space Path Loss model [20] as follows:
PPT Slide
Lager Image
Pr is the received power, Pt is the transmitting power, Gt is the transmitting antenna gain, Gr 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 ni and nj . In fact, node ni and node nj are both mobile, but we see ni as static and nj as mobile for convenience. When node nj moves from b to c with a relative speed vr , we call it a receding scenario. When node nj moves from c to b with a relative speed va , we call it an approaching scenario.
PPT Slide
Lager Image
Relative mobility
nj sends a Hello packet at b and c , respectively. ni receives the packets. Δt is the time interval between two Hello packets. By (1), the received power of the signal sent at b is
PPT Slide
Lager Image
, the received power of the signal sent at c is
PPT Slide
Lager Image
. dab is the distance between a and b , dac is the distance between a and c . Then, dab and dac can be expressed as:
PPT Slide
Lager Image
PPT Slide
Lager Image
Suppose f is original carrier wave frequency at sender nj , f’ is the received carrier wave frequency at receiver ni . If f > f ', it means that the transmitter nj and the receiver ni are receding from each other. Contrarily, if f > f ', it means that the transmitter nj and the receiver ni are approaching to each other. According to Doppler effect, in receding scenario the following expression is obtained:
PPT Slide
Lager Image
In (4), Vc is the speed of light and vr is the relative speed in receding scenario. By (4), the receding speed is obtained:
PPT Slide
Lager Image
From the law of cosines, we can obtain the following:
PPT Slide
Lager Image
In (6) dbc is the distance between b and c . We assume that in the transmission time interval Δt , nj would not change its moving direction, then the distance from b to c can be expressed as:
PPT Slide
Lager Image
Substituting (7) in (6) and then substituting (6) in (5), the following expression is obtained:
PPT Slide
Lager Image
Take (2) and (3) into (8), and we obtain the following:
PPT Slide
Lager Image
In the approaching scenario, nj 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:
PPT Slide
Lager Image
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 ni is static and located at a; nj is first located at b and then it moves to c . If nj will not change its present speed and direction of motion, the maximum link connection time in the receding scenario is calculated as:
PPT Slide
Lager Image
Estimation in the receding scenario
PPT Slide
Lager Image
d is located at the edge of the communication range, dcd is the distance between c and d , dbd is the distance between b and d .
In Δ abc , from the law of cosines, we can obtain the following:
PPT Slide
Lager Image
Take (9) into (7), and we get the distance between b and c :
PPT Slide
Lager Image
Take (2), (3) and (13) into (12), and we get:
PPT Slide
Lager Image
In Δ abd , from the law of cosines, we can obtain the following:
PPT Slide
Lager Image
As illustrated in Fig. 2 , dbd is the distance between b and d , dad is the distance between a and d . Actually, dad is the radius of the cluster, so (15) can be rewritten as:
PPT Slide
Lager Image
In (16), R is the maximum communication range. (16) can be transformed as:
PPT Slide
Lager Image
Solve the quadratic equation (17), and dbd is obtained as:
PPT Slide
Lager Image
The value of dbd is single, so the indetermination in (18) should be eliminated.
If
PPT Slide
Lager Image
, the following expression can be obtained:
PPT Slide
Lager Image
By (19), we obtain that d 2 ab = d 2 ab cos 2 abd + d 2 ab sin 2 abd > R 2 . However, dab is definitely shorter than the communication range R . So (19) will never be right. Then,
PPT Slide
Lager Image
is the final right expression. At last, the definite answer of quadratic equation (17) is:
PPT Slide
Lager Image
Actually, ∠ abd and ∠ abc are the same angle, so:
PPT Slide
Lager Image
Take (20), (21), (14) and (2) into (11), the maximum link connection lifetime in the receding scenario is calculated as:
PPT Slide
Lager Image
In (22),
PPT Slide
Lager Image
.
- 5.2 Approaching Scenario
In Fig. 3 , we assume that ni is still static and located at a, nj is first located at c and then it moves to b . If nj will not change its present speed and direction of motion, the maximum link connection time in the approaching scenario is calculated as:
PPT Slide
Lager Image
Prediction in the approaching scenario
PPT Slide
Lager Image
dbd is the distance between b and d in Fig. 3 .
In approaching scenario, the distance from b to c can be expressed:
PPT Slide
Lager Image
Take (2), (3), (24) and (10) into (6), cos∠ abc in Fig. 3 is obtained as:
PPT Slide
Lager Image
In Δ acd , from the law of cosines, we can obtain the following:
PPT Slide
Lager Image
It is presented in Fig. 3 that cos∠ acb =cos∠ acd , and dad = R . We can calculate dcd by (25) and (26), which adopts the same way that uses (14) and (16) to calculate dbd .
PPT Slide
Lager Image
Take (3), (25), and (27) into (23), the maximum link connection lifetime in the approaching scenario is calculated as:
PPT Slide
Lager Image
va is obtained from (10).
- 5.3 Link Connection Lifetime Update
By (22) and (28), the estimated link connection lifetime of node ni toward nj is:
PPT Slide
Lager Image
If nj and ni are in the approaching scenario, the link connection lifetime between them is ta . If nj and ni are in the receding scenario, the link connection lifetime between them is tr . If nj and ni 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 nj are received, node ni estimates the link connection lifetime between ni and nj to create an entry of nj in ni ’s neighbor list. The link connection lifetime is updated each time when a new Hello packet is received from node nj .
6. Clustering Scheme
The SCBCS clustering algorithm aims to find the cluster head that has the longest link connection lifetime to its one-hop members. Suppose Np is a set of nodes whose distance to ni is approaching to the maximum distance R and their estimated link connection lifetime toward ni is approaching to zero. Any node nj Np is not likely to be a member of ni . So there is no need to consider any node nj Np when calculating the metric to measure the degree that ni is appropriate to be a cluster header. Table 1 shows some notations and their corresponding definition used in Section 6.
The notation definitions
PPT Slide
Lager Image
The notation definitions
The distance of these nodes to ni is longer than d max , and the estimated link connection lifetime toward ni is shorter than t min . Suppose Nni is a set of ni 's one-hop neighbors. Any node ni in the network gathers its one-hop neighbors' distance, mobility and link stability information by the method shown in Sections 4 and 5 of this paper. When ni calculates its degree to become a cluster head, it checks its one-hop neighbor list and excludes any node nj Np from measuring the degree that ni is appropriate to be a cluster header. ni 's degree to be a cluster at time t is calculated as the sum of its one-hop neighbors’ estimated link lifetime:
PPT Slide
Lager Image
In (30) Ts is the time threshold. The larger Wni ( t ) is, the more ni is appropriate to become a cluster head. In (29), the estimated link lifetime may approach infinite when the velocity of ni and nj are very similar. Thus, if the estimated link lifetime Tij is longer than Ts , we think that it is equal to Ts 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 one-hop 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 one-hop 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 clustering-related control overhead can be reduced by limiting re-affiliation and re-clustering events through the estimated mobility information presented in Sections 4 and 5 of this paper.
- 6.2.1 Re-affiliation scheme
When a cluster member moves out of its cluster head's communication range or an orphan node joins an established cluster, re-affiliation 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 nk 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 nk 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 nk moves off of the present cluster, it will not be a member of another cluster. If nk 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 Re-clustering scheme
There are three main reasons that can lead to re-clustering: cluster partition, cluster merger and head-member 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 one-hop 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 re-clustering.
- 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 re-clustering 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 Hi 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 re-clustering 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 one-hop 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 re-clustering.
- 3) Head-Member 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 Hi 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γ.
PPT Slide
Lager Image
  • 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 ,
PPT Slide
Lager Image
, β =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 free-space 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.
PPT Slide
Lager Image
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, re-clustering 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 re-clustering 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.
PPT Slide
Lager Image
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.
PPT Slide
Lager Image
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.
PPT Slide
Lager Image
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.
PPT Slide
Lager Image
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.
PPT Slide
Lager Image
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 cluster-based 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. E-mail: 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. E-mail: 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 anti-jamming communication and wireless networks. E-mail: ru-le @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 anti-jamming communication. E-mail: 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 anti-jamming communication. E-mail: songb21@126.com
References
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 one-hop clustering algorithms in mobile ad hoc networks” Journal of Networks and Systems Management Article (CrossRef Link) 17 (1-2) 183 - 207    DOI : 10.1007/s10922-009-9123-7
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 8-10 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 9-12 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 16-19 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 multi-parameter 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 mobility-based cluster formation algorithm for wireless mobile ad-hoc networks” Cluster Computing Article (CrossRef Link) 14 (4) 311 - 324    DOI : 10.1007/s10586-011-0161-z
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 self-clustering 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 signal-noise-ratio environment in mobile communication systems” in Proc. of International Conference on Wireless Communications, Networking and Mobile Computing October 12-14 Article (CrossRef Link) 1 - 4
Wu Duanpo , Jin Xinyu , Jiang Lurong 2014 “Analysis of handoff algorithm-based on Doppler effect and RSSI measurements in GSM-R 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 attenuation-aware clustering in wireless mobile ad hoc networks” Journal of Networks Article (CrossRef Link) 8 (4) 796 - 803    DOI : 10.4304/jnw.8.4.796-803
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 Doppler-based 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 prediction-based 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 4-7 Article (CrossRef Link) 289 - 294
Goldsmith Andrea 2005 Wireless Communication Cambridge University Press Cambridge
Wirelss Network Simulator in Matlab. [Online]. http:// sourceforge.net/projects/wireless-matlab/