A Clustering Algorithm Based on Mobility Properties in Mobile Ad Hoc Networks

Abstract

We propose a context-awareness routing algorithm—the DDV- (Dynamic Direction Vector-) hop algorithm—in mobile ad hoc networks. The existing algorithm in MANET has the limitations of the dynamic network topology and the absence of network expandability of the mobility of nodes. The proposed algorithm performs cluster formation for the base station using the range of direction and threshold of velocity. We calculate the exchange of the cluster head node probability using the direction and velocity for maintaining cluster formation. The DDV-hop algorithm, a probabilistic routing protocol for such networks, is proposed and then compared to the earlier presented algorithms through simulations. The simulations are conducted on a number of clusters, network areas, transmission ranges, and velocity of nodes in mobile networks. Our results suggest that the DDV-hop algorithm demonstrates efficiency of eventual delivery and maintains the proper number of clusters and cluster members regardless of topology changes with a lower communication overhead in several interesting environments.

1. Introduction

In recent years, with the development of wireless communication technologies and various sensor nodes which led to the emergence of the low-power and low-cost RF technology, wireless sensor networks have become the object of much scholarly attention. Wireless sensor networks consist of wireless devices based on various protocols to facilitate wireless transmission and a processing unit to process the data. Their main characteristics include the network expandability, self-recovery, and multicasting. Wireless sensor networks were originally designed to build a temporary network for emergencies, such as disasters, as well as for battlefield surveillance or other uses of the military. Later on, the applications of wireless sensor networks have become more versatile [1–3].

Mobile ad hoc network (MANET) consists of nodes that have mobility. The nodes both send and receive messages and can communicate with each other. Thus, the network builds its own network structure that is not dependent on infrastructure. Due to the characteristics of mobile ad hoc networks, MANET has been used in the environments of poor communication, such as those where infrastructure cannot be built, as in disaster areas or war zones [4, 5]. Cluster networks using properties of the node have been studied particularly extensively. A cluster network is divided into mobile groups by setting the rules of communication protocols. The mobile groups elect the cluster head node for managing groups. The cluster head node aggregates sensing data sent by a cluster member node and then sends the aggregated data to the base station [6]. However, if the cluster head node is discharged or does not move due to poor environmental conditions, the routing path is disconnected from the cluster head node. Therefore, the network cannot communicate in a stable fashion. In that case, the cluster network reelects the cluster head node to recover the routing path. However, dynamic properties of a node cause frequent disconnections and routing recovery. In addition, the nodes have constraints, such as limited transmission bandwidth and energy, as well as topology changes. To reduce the number of disconnections and in order to set the routing path, the network sends a control packet. Eventually, the load is increased [7–11].

In this paper, we propose a context-awareness routing algorithm: the DDV- (Dynamic Direction Vector-) hop algorithm. This algorithm considers dynamic properties of nodes, such as velocity, direction, to form clusters. In order to maintain clusters, the cluster head node finds cluster member nodes with similar velocity and direction.

The rest of the paper is organized as follows. Section 2 describes relevant research related to the proposed algorithm. Section 3 provides a detailed description of the DDV-hop algorithm. This analyses the algorithm using network models and optimization. The comparison of the performance of the DDV-hop algorithm with that of the Lowest-ID and the MOBIC algorithms is provided in Section 4. Finally, Section 5 shows the conclusions of the present paper.

2. Related Works

In MANET, Yan Zhang and Jim Mee Ng proposed the distributed group mobility adaptive (DGMA) clustering algorithm. In the DGMA, the node measures location information of the node by GPS and calculates the variation of the node location. Calculating variation of nodes is shown as

$$\begin{array}{cc}& \Delta x_{Ti}=\left(x_{ti}-x_{Ti}\right),\\ \Delta y_{Ti}=\left(y_{ti}-y_{Ti}\right),\end{array}$$

(1)

where $\Delta x_{Ti}$ and $\Delta y_{Ti}$ are variations of the node location. t is the current time, T is previous time, $x_{ti}$ , $y_{ti}$ , $x_{Ti}$ , $y_{Ti}$ are the coordinates of the node i at time t and T respectively. Using the difference in the node locations, it is possible to form and maintain the clustering networks from the node analyses of velocity and direction [12].

Similarly to the MANET environment, VANET (vehicular ad hoc network) has been reported to maintain routing by frequently changing topology. MDBC (Moving Direction Based Greedy Routing Algorithm) uses the direction property of several properties for routing. To set the direction of the node that has mobility, if the current coordinate X (X-position) is bigger than the former coordinate X, the direction of the node is east. If the current coordinate X is smaller than the former coordinate X, then the direction of the node is west. If the current coordinate Y (Y-position) is bigger than the former coordinate Y, the direction of the node is north. If the current coordinate Y is smaller than the former coordinate Y, the direction of the node is south. When the direction of the node is set, the node broadcasts hello message and stores the location and direction of the neighbor node in the table. To forward a packet to the destination node, the node uses DREQ (Destination REQuest) and DREP (Destination REPly) and finds a stable routing path [13].

Lili Hu proposed GPSR (Greedy Perimeter Stateless Routing) considering the direction and velocity of a node in VANET. In the GPSR algorithm, the node sends hello message that periodically includes velocity and direction, grasps current coordinates of neighbor nodes, and calculates the current coordinates using velocity and direction. The current coordinates of the node are shown in

$$\begin{array}{cc}& X_t=X_{\mathrm{0}}+\left(t-t_{\mathrm{0}}\right)\ast V_x,\\ Y_t=Y_{\mathrm{0}}+\left(t-t_{\mathrm{0}}\right)\ast V_y,\end{array}$$

(2)

where t is current time and $t_0$ is the time when hello message was received. $V_x$ and $V_y$ refer to velocity. Then, the node calculates the probability of transmission considering the velocity and direction of the node and forwards the packet [14].

The lowest ID cluster algorithm (LIC) is an initial clustering algorithm in MANET. This algorithm performs cluster formation using a unique ID of a node. To form a cluster, the network chooses the cluster head node with the minimum ID. The cluster head node chooses a cluster member node with the ID higher than its own. When a node is located within the transmission range of two or more cluster head nodes, the node, called a gateway node, is used for routing between clusters. However, since the node hears only the nodes with IDs higher than that of the cluster head node, the network consumes energy inefficiently and communication between the nodes is frequently disconnected [15].

The Mobility Based Metric for Clustering (MOBIC) algorithm proposes a local metric for cluster formation using speed properties in MANET. For cluster formation, network measures the speed of a node using its coordinates and the interval time by hello message. The network chooses the cluster head node that has a low speed variance. After the cluster head node is selected, it joins a node as a cluster member node in a 2-hop area. However, since the MOBIC algorithm elects the node with a low speed as the cluster head node, the network topology frequently changes and the communication between nodes is disconnected [16].

3. System Modeling and Methods

In this paper, we propose the DDV-hop algorithm which performs and maintains cluster formation taking into account mobility properties, such as direction and velocity. The existing clustering algorithm has the problem that the topology gets frequently changed by node mobility. Therefore, topology broadcasts change topology information, the network load increases, and there is a lack of the network expandability. According to the mobility of a node, the proposed algorithm forms clusters from the nodes with similar direction and velocity. Due to this method of cluster formation, the topology change of the network is reduced, packet delivery ratio increases, and the load of the network decreases. To form the initial cluster, the proposed algorithm sets a coverage as shown in

$$\begin{array}{cc}& R_C=k\times R_T,k=\mathrm{1,2},\mathrm{3},\dots ,N,\end{array}$$

(3)

where $R_C$ is coverage, $R_T$ is transmission range, and k refers to the number of hops [17]. In this paper, we set the coverage that confirms the information of the node by the number of hops and the transmission range. To elect the initial cluster head node, the base station uses coverage using the following.

First, the network elects the initial cluster head node by coverage (see Figure 1).

Figure 1

Selection of the initial cluster head node by coverage.

In Figure 1, white circles mark cluster member nodes and black circles mark initial cluster head nodes. The black circle labelled “BS” refers to the base station and the broken-line circle means the coverage of the base station by the number of hop. The network builds the base station located in the center of network. When the number of hops is $k=i$ , the base station sets coverage. The base station confirms the direction of the node and measures the number of nodes in the range of direction set by the base station in each region. In each region, the base station chooses the range of direction with the highest number of nodes and elects a node with a similar direction to that of the initial cluster head node. In each region, the cluster head node cannot be elected by the base station, the base station increases the number of hops, and the procedure is repeated until the initial cluster head node is elected by the direction in each region [18].

3.1. The DDV-Hop Algorithm Scenario

With regard to performing cluster formation, the following two assumptions are made in the paper.

First, the base station is located in the center of the network.

Second, the network area is divided into four regions by the base station.

Based on these assumptions, the network initializes the network environment and the nodes randomly set the location in the network. Next, the direction of the nodes is randomly set by the base station. Furthermore, the node arbitrarily establishes its properties, such as velocity. The energy of the node is initialized.

In Figure 2, the cluster head node is elected by coverage and direction. In this paper, we assume that the number of hops is 1. Thus, the base station confirms all nodes in the network and elects the initial cluster head node in each region. Afterwards, the cluster head node searches for other nodes with similar properties. The nodes located on the boundary are included, based on their properties of direction and velocity, into the same region; furthermore, the nodes form a cluster in that region.

Figure 2

The procedure of the initial cluster formation.

When the cluster head node is elected, it sends an announcement message to the nodes nearby. A normal node receives the announcement message and selects the cluster head node that is closest to it and has the same direction and velocity. Then, the nodes send join message to select the cluster head node. The cluster head node receives that join message and registers those nodes as its cluster member nodes. At this point, cluster formation is completed. Now, the network has a routing structure that allows the cluster member nodes to send messages to the cluster head node and the latter node to send a message to the base station. As each node has mobility, the nodes get out of the cluster. In this case, the node is included into the region where it finally belongs. For example, when a node belongs to region A, but has moved to region B, the node performs cluster formation again using its direction and velocity. The cluster member node maintains its routing path.

According to the procedure of the cluster formation, the relationship of friendship with the cluster head node is as follows (see Figure 3).

Figure 3

The procedure of join the cluster head node by the attributes (velocity, direction, location, energy, and transmission range).

As shown in Figure 3, nodes X and Y are included into the transmission range of the cluster head nodes A and B. This is a simple example showing an efficient clustering method which selects the cluster head node. In the existing algorithm, a node selects the cluster head node that is closest to it, regardless of direction and velocity. However, in the DDV-hop algorithm, the node compares its own direction and velocity with those of the cluster head node and selects the cluster head node with similar direction and velocity. For example, node X is included by the cluster head nodes A and B. Node X compares the direction and velocity of its own with those of both cluster head nodes and then selects the cluster head node B, as this cluster head node has similar properties. Therefore, the load of the network is reduced and a stable topology is maintained with a lower communication overhead in mobile ad hoc networks [19].

3.2. Network Models and Analysis of the DDV-Hop Algorithm

In this paper, we propose the DDV-hop algorithm which performs and maintains cluster formation considering the properties of nodes such as direction and velocity. Specifically, the DDV-hop algorithm considers the following properties. A set of nodes defines N in the network; each node has a unique ID. Furthermore, each node has direction $({\text{Dir}}_i)$ and velocity ( $v_i$ ) (see (4)):

$$\begin{array}{cc}& N_i=\left\{{\text{Dir}}_i,v_i\right\},\end{array}$$

(4)

where ${\text{Dir}}_i$ is the direction of node i and $v_i$ is the velocity of node i. The direction and velocity of each node are expressed in

$$\begin{array}{cc}& {\text{Dir}}_i=\left\{\mathrm{0}\le {\text{Dir}}_i<\mathrm{2}\pi \right\},\\ v_i=\left\{\mathrm{0}\le v_i<n\right\},\end{array}$$

(5)

where n is a real number for setting the velocity of node i and node i sets the velocity between 0 and n.

As the DDV-hop algorithm performs and maintains cluster formation by the direction and velocity of nodes, the network can communicate for a long time. For the communication of the network, the proposed algorithm is divided into two major procedures, that of cluster formation and the other of exchanging the cluster head node (see Sections 3.2.1 and 3.2.2 for further detail).

3.2.1. The Procedure of Cluster Formation

According to one of the assumptions specified above, the base station is located in the center of the network area; the initial cluster is formed according to the following procedure.

Step 1.

For electing the initial cluster head node, the base station divides the network into four regions (see (6)):

$$\begin{array}{l}\text{network\hspace{0.17em}\hspace{0.17em}area}\\ =\left\{{\text{Region}}_Z\hspace{0.17em}|\hspace{0.17em}{\text{Region}}_Z\in \text{network\hspace{0.17em}\hspace{0.17em}area}\right\},\end{array}$$

(6)

where ${\text{Region}}_Z$ is the network area divided by the base station. When the network is divided by (6), the base station sets the range of direction. The range of direction is expressed using $\text{rs}$ , range of angle resolution. When $\text{rs}$ is higher, then the number of cluster head nodes increases. The method of setting the range of direction is expressed in (7) and (8) as follows:

$$\begin{array}{cc}& \text{rs}=\left\{\mathrm{0}<\text{rs}\le n\right\},\end{array}$$

(7)

$$\begin{array}{cc}& {\text{Dir}}_{\text{BS}}\left(i\right)=\left\{\begin{array}{c}\text{rs}\hspace{0.17em}|\hspace{0.17em}\left[\frac{\alpha \pi }{\text{rs}},\frac{\left(\alpha +\mathrm{1}\right)\pi }{\text{rs}}\right]\\ \alpha =\mathrm{0,1},\mathrm{2},\dots ,\mathrm{2}\text{rs}-\mathrm{1}\end{array}\right\},\end{array}$$

(8)

where ${\text{Dir}}_{\text{BS}}\left(i\right)$ refers to set of the range of the direction by the base station. n means a real number for setting the $\text{rs}$ . The base station sets the $\mathrm{r}\mathrm{s}$ between 0 and n. In the set range of direction by ${\text{Dir}}_{\text{BS}}\left(i\right)$ , the number of the cluster head nodes is determined. The cluster head node is elected by the coverage and direction in each ${\text{Region}}_Z$ ; the direction of node is included into the set range of direction. Equation (9) presents the method of electing a cluster head node:

$$\begin{array}{cc}& \text{CH}=\left\{N_i\hspace{0.17em}|\hspace{0.17em}{N}_i\in {\text{Region}}_Z\wedge {\text{Dir}}_i\in {\text{Dir}}_{\text{BS}}\right\}.\end{array}$$

(9)

In (9), $\text{CH}$ refers to the cluster head node group in the network. After selecting the cluster head node using (7) and (8), the cluster head node measures the similarity of direction for selecting cluster member nodes.

Step 2.

The method of measuring similarity of direction compares the differences in direction between the nodes ( ${\text{Dir}}_{ij}$ ) and sets a threshold of direction ( ${{\text{Dir}}_i}^{\text{rs}}$ ) using a range of direction. This method is presented in

$$\begin{array}{cc}& {\text{Dir}}_{ij}=\left|{\text{Dir}}_i-{\text{Dir}}_j\right|,\\ {{\text{Dir}}_i}^{\text{rs}}=\left\{{\text{Dir}}_{ij}\hspace{0.17em}|\hspace{0.17em}{\text{Dir}}_{ij}\in \left|\frac{\pi }{\text{rs}}\right|\wedge N_j\in {\text{Region}}_Z\right\},\end{array}$$

(10)

where ${\text{Dir}}_{ij}$ means the difference of direction between the nodes, ${{\text{Dir}}_i}^{\text{rs}}$ is the threshold of direction, and ${\text{Region}}_Z$ is the network area divided by the base station. When the threshold of direction $\mathrm{r}\mathrm{s}$ increases, the range of the threshold of direction gets narrower.

Step 3.

The method of measuring similarity of the velocity between the nodes compares the differences of velocity between the nodes and sets a threshold of velocity using a deviation of velocity; the method is presented in (11) and (12) as follows:

$$\begin{array}{cc}& v_{ij}=\left|v_i-v_j\right|,\end{array}$$

(11)

$$\begin{array}{cc}& \Delta v_i=\left\{j\hspace{0.17em}|\hspace{0.17em}{v}_{ij}\le \left|{\sigma }_{v_i}\right|\wedge N_j\in {\text{Region}}_Z\right\},\end{array}$$

(12)

where $v_{ij}$ means the difference of velocity and $\Delta v_i$ refers to a threshold of the velocity. ${\sigma }_{v_i}$ is a factor that sets a threshold of velocity.

Step 4.

The cluster head node selects cluster member nodes through measuring the similarity of direction and velocity in Steps 2 and 3; the method is presented in

$$\begin{array}{cc}& {\text{CM}}_i=\left\{j\hspace{0.17em}|\hspace{0.17em}{\text{Dir}}_{ij}\in {{\text{Dir}}_i}^{\text{rs}}\wedge v_{ij}\in v_i\right\},\\ {\text{HG}}_i=\left\{{\text{CM}}_i\hspace{0.17em}|\hspace{0.17em}{\text{CM}}_{\mathrm{1}}\cup {\text{CM}}_{\mathrm{2}}\cup \cdots \cup {\text{CM}}_{\mathrm{4}}\right\},\end{array}$$

(13)

where ${\text{CM}}_i$ is a group of the selected cluster member nodes and ${\text{HG}}_i$ is a cluster that consists of the cluster member nodes.

3.2.2. The Procedure of Exchange of the Cluster Head Node

To reduce the network load, the exchange of the cluster head node is needed. After performing the cluster formation, the procedure of maintaining cluster is as follows. The cluster member nodes calculate successful probability by direction, velocity, and residual energy. The exchange of the cluster head follows the procedure specified below.

Step 1.

The cluster member nodes in the cluster calculate the exchange probability ( $E_j(t)$ ) using the distance between the nodes, the energy from transmitting data, and their average residual energy. The method is shown in [20, 21]

$$\begin{array}{l}P\left(E_j\left(t\right)\right)\\ ={\displaystyle \sum }_{j\in {\text{CM}}_i}\frac{G\left[E_j\left(l\right)\times \omega \left(l\right)+E_j\left(\text{dist}\right)\times \omega \left(\text{dist}\right)\right]}{N-G\left(r\text{mod}\left(N/G\right)\right)\times \left(\mathrm{1}/N\right){\sum }_{j=\mathrm{1}}^n{E}_j\left(t\right)},\end{array}$$

(14)

where $P_j\left(E_j\left(t\right)\right)$ is the probability of exchange using energy, $E_j\left(l\right)$ is the energy by transmitting data, and $E_j\left(\text{dist}\right)$ is the energy of the distance between nodes. G is the cluster group and r is round. $\omega \left(l\right)$ and $\omega \left(\text{dist}\right)$ refer to the weight factors of transmitting coefficient value between the distance and the residual energy of the nodes. When the cluster member node finishes the calculation of the probability of exchange using energy, the information forms a group in the cluster. The method is shown in

$$\begin{array}{cc}& f\left(E_j\left(t\right)\right)=\left\{P_j\left(E_j\left(t\right)\right)\hspace{0.17em}|\hspace{0.17em}{P}_j\left(E_j\left(t\right)\right),\hspace{0.17em}\hspace{0.17em}j\in i\right\},\end{array}$$

(15)

where i is the cluster head node i and j is the cluster member node j assigned to the cluster head node i. $f\left(E_j\left(t\right)\right)$ refers to the group of the exchange probability using the energy of the cluster member node j.

Step 2.

The probability of exchange by velocity and the direction is calculated using the similarity of direction and velocity and their threshold; the method is shown in

$$\begin{array}{cc}& P_j\left(\text{DV}\left(t\right)\right)={\displaystyle \sum }_{j\in {\text{CM}}_i}\frac{{\text{Dir}}_{ij}}{{{\text{Dir}}_j}^{\text{rs}}}·\frac{v_{ij}}{\Delta v},\end{array}$$

(16)

where $P_j\left(\text{DV}\left(t\right)\right)$ is the probability of exchange by velocity and direction. When the cluster member node finishes calculating the probability of exchange by velocity and direction, this information forms a group in the cluster. The method is shown in

$$\begin{array}{cc}& f\left(\text{DV}\left(t\right)\right)=\left\{P_j\left(\text{DV}\left(t\right)\right)\hspace{0.17em}|\hspace{0.17em}{P}_j\left(\text{DV}\left(t\right)\right),\hspace{0.17em}\hspace{0.17em}j\in i\right\},\end{array}$$

(17)

where $f\left(\text{DV}\left(t\right)\right)$ is the group of the probability of exchange by velocity and direction of the cluster member node j.

Step 3.

Using the calculated probabilities of exchange by Steps 1 and 2, the cluster member node calculates final probabilities using $f\left(E_j\left(t\right)\right)$ and $f\left(\text{DV}\left(t\right)\right)$ . The method is shown in

$$\begin{array}{cc}& P_j\left(\text{DDV}\left(t\right)\right)=\left\{\begin{array}{cc}{\left.\left(f\left(E_j\left(t\right)\right)\times {\omega }_j\left(t\right)\times f\left(\text{DV}\left(t\right)\right)\times {\omega }_j\left(\text{DV}\left(t\right)\right)\right)\right|}_{\text{max}},\hfill & C_j\left(t\right)=\mathrm{0}\hfill \\ \mathrm{0},\hfill & C_j\left(t\right)=\mathrm{1},\hfill \end{array}\right.\end{array}$$

(18)

where $P_j\left(\text{DDV}\left(t\right)\right)$ means the final probability of exchange using energy, velocity, and direction of the node and $\omega \left(E_j\left(t\right)\right)$ and $\omega \left(\text{DV}\left(t\right)\right)$ refer to the weight of the probability of exchange by the energy and the probability of exchange by velocity and direction. $C_j\left(t\right)$ is the function elected by the cluster head node. When the cluster member node was elected as the cluster head node, $C_j\left(t\right)$ is 1. Thus, $P_j\left(\text{DDV}\left(t\right)\right)$ is 0. When the cluster member node was not elected as the cluster head node, then $C_j\left(t\right)$ is 0. Thus, $P_j\left(\text{DDV}\left(t\right)\right)$ is calculated as shown in (18).

Step 4.

The cluster head node elects the cluster member node that has the maximum probability of $P_j\left(\text{DDV}\left(t\right)\right)$ as the exchange cluster head node in the cluster. The exchange cluster head node compares its own direction and velocity with those of the nodes in the cluster. When the nodes have similar direction and velocity, they are joined to the cluster by the exchange of the cluster head node.

3.3. The DDV-Hop Algorithm Modeling

In the DDV-hop algorithm, each node has a property table in the network (see Table 1).

Table 1

Table of node's properties (example).

ID	Dir	Velocity	Region
n	1	7	0

In Table 1, ID is the unique identification number of the node, Dir is the direction of the node, Velocity is the velocity of the node, and Region refers to the network area divided by the base station. When the nodes are assigned to the network, their properties are stored in the corresponding property tables. Using the information from these property tables, network performs cluster formation and changes the cluster head node.

3.3.1. Cluster Formation Modeling

According to one of the assumptions specified above, the base station is located in the center of the network area and the network is divided into regions by the base station. Then, the base station generates a region table to store cluster information (see Table 2).

Table 2

Region table in the base station (example).

$${\text{Region}}_Z$$
$$\text{Di}{\text{r}}_{\text{BS}}$$ (i)	0	1	2	3
CHID	—	—	—	—

In Table 2, ${\text{Region}}_Z$ is the network area divided by the base station, ${\text{Dir}}_{\text{BS}}(i)$ is a range of direction by the base station, and CHID is a head node from one of the selected cluster nodes. Region tables store the cluster head node IDs. The procedure of storing the cluster head node ID is as follows (see Figure 4).

Figure 4

The procedure of the selection of the cluster head node.

In Figure 4, the region table searches velocity and direction of the nodes and selects the cluster head node located in the coverage by the base station. The direction is included into the threshold of direction and the velocity is included in the threshold of velocity. Finally, the selected cluster head node is stored in the region table. The selected cluster head node generates a table to store the cluster member node (see Table 3).

Table 3

Table of the cluster head node (example).

CMID	1	3	13	15
P(DDV(t))	—	—	—	—

In Table 3, CMID refers to the cluster member node ID and $P(\text{DDV}(t))$ is the probability of exchange of the cluster head node. The cluster head node measures the similarity of the direction and velocity of normal nodes located in the region. When the value of similarity is included in the threshold, a normal node is registered as a cluster member node. The cluster head node stores the cluster member node ID in the table and performs cluster formation. The procedure of cluster formation is as follows (see Figure 5).

Figure 5

The procedure of cluster formation by the DDV-hop algorithm.

In Figure 5(a), the network area is divided into regions by the base station. Figure 5(b) shows the selection of the cluster head node by coverage of the base station, and the direction of the node is included by the base station. In Figure 5(c), the cluster head node selects cluster member nodes that are similar to it in terms of direction and velocity. Figure 5(d) shows the final result of cluster formation. Pseudocode 1 shows the pseudocode of cluster formation.

Pseudocode 1: The pseudocode of cluster formation.

Procedure: initialize cluster formation of the DDV-hop algorithm

Input

  $${\text{Dir}}_{ij}$$ : the difference of direction between nodes i and j

  $${{\text{Dir}}_{ij}}^{\text{rs}}$$ : the threshold of direction

Output

 Cluster head node group CH

 Cluster member node group of all cluster head node i CM

Begin

 initialize CH

 initialize $${\text{Region}}_Z$$

  $$i\leftarrow \mathit{0}$$

 for $$a=\mathit{0}$$ to z

  for $$b=\mathit{0}$$ to N

   if ( $$N[b]$$ is located $${\text{Region}}_a$$ ) then

     $${\text{Region}}_a\ni N[b]$$

   if ( $$N[b]$$ is located in the coverage of the base station and has different direction of CH)

   then

    CH[i] ← $$N[b]$$

     $$i=i+\mathit{1}$$

  end

 end

 for $$a=\mathit{0}$$ to i

  for $$b=\mathit{0}$$ to $$N-\mathit{1}$$

   if (Region including CH[a] ≡ Region including $$N[b]$$ ) then

     $${\text{Dir}}_{\text{CH}\left[a\right]N\left[b\right]}\leftarrow \left|{\text{Dir}}_{\text{CH}\left[a\right]}-{\text{Dir}}_{N\left[b\right]}\right|$$

     $${\nu }_{\text{CH}\left[a\right]N\left[b\right]}\leftarrow \left|{\nu }_{\text{CH}\left[a\right]}-{\nu }_{N\left[b\right]}\right|$$

   if (0 ≤ ( $${\text{Dir}}_{\text{CH}\left[a\right]}/\left|{{\text{Dir}}_{N\left[b\right]}}^{\text{rs}}\right|$$ ) ≤ 1) and (0 ≤ ( $${\nu }_{\text{CH}\left[a\right]}/\left|\mathrm{\Delta }\nu \right|$$ ) ≤ 1) then

     $${\text{CM}}_a\ni N[b]$$

   end

  end

  output the cluster head node group CH

  output the cluster member node groups of all cluster head node i of cluster head node i   $${\text{CM}}_i$$

end

As shown in Pseudocode 1, $N[i]$ is the node that is located in the network. i refers to the initial cluster head. For the initial cluster formation, the network depends on the threshold of direction $({\text{Dir}}_{\text{BS}}(i))$ in (8) and to the threshold of velocity ( ${\sigma }_{v_i}$ ) in (12). The node is selected including the cluster head node when a node is compared to the threshold of direction and refers to the threshold of velocity. The election of the node is registered as role CH and cluster member node groups. The selected cluster head node compares its velocity and direction to those of other nodes in each region. When the remaining normal nodes are similar to the cluster head node in velocity and direction, the normal node is registered as a cluster member node and is stored in ${\text{CM}}_i$ .

3.3.2. Maintaining Cluster Formation Modeling

The cluster head node is exchanged to enhance the efficiency of energy consumption and to ensure continuous communication. For the exchange of the cluster head node, the cluster member nodes calculate the exchange probability and send the respective message to their cluster head node. When a cluster head node receives this message, it stores the exchange probability in the cluster head node table (see Table 4).

Table 4

Storing the probability of exchange in the cluster head node table CH( $$\mathit{4}$$ ) (example).

CMID	1	3	13	15
P(DDV(t))	0.87	0.92	0.54	0.49

In the cluster head node table, the cluster head node compares the probabilities of exchange; furthermore, the cluster member node with the maximum probability of exchange becomes the next cluster head node. Then, for efficient energy consumption and continuous communication, the preceding cluster head node has “0” probability of exchange. The preceding cluster head node also sends the cluster information message making the cut point that permutates a cluster member node into the maximum $P(\text{DDV}(t))$ as a cluster head node in (18). The procedure of editing cluster information is as shown in Figure 6.

Figure 6

The procedure of updating cluster information.

The next permutation is that the cluster head node receives cluster information and sends message that the cluster head node is exchanged. When the base station receives the message making cut point. And the head node exchange $\text{CHID}[i]$ into maximum $P(\text{DDV}(t))$ node as shown in the region table (see Figure 7).

Figure 7

The procedure of updating the cluster head node in the region table.

As shown in Figure 7, the base station receives the message that there is a cluster head node exchange and changes the cluster head node information in the region table. The procedure of the exchange of the cluster head node is shown in Figure 8.

Figure 8

The procedure of the exchange of the cluster head node in the network.

Figure 8(a) shows the network before the exchange of the cluster head node. Figure 8(b) shows the procedure of the exchange of the cluster head node by the probability of exchange. Figure 8(c) shows the resulting network after the exchange. Pseudocode 2 shows the pseudocode of the exchange of the cluster head node.

Pseudocode 2: The pseudocode of the exchange of the cluster head node.

Procedure: exchange of the cluster head node of the DDV-hop algorithm

Input

  $${\text{Dir}}_{ij}$$ : difference of direction between nodes i and j

  $${{\text{Dir}}_{ij}}^{\text{rs}}$$ : threshold of direction

 CH: Cluster head node group

  $${\text{CM}}_i$$ : Cluster member node group of allcluster head node i

 G: the number of cluster head node

 Gm: the number of cluster member node

Output

 Change cluster head node group CH′

 All change cluster member node group of cluster head node i   $${\text{CM}}_i^{\prime }$$

Begin

 initialize CH′

 nextCH ← 0

 for $$a=\mathit{0}$$ to G

  for $$b=\mathit{0}$$ to Gm

   if (CH[a] ∋ $${\text{CM}}_{\text{CH}\left[a\right]}[b]$$ ) then

    calculate f( $$E_b(t)$$ ) of $${\text{CM}}_{\text{CH}\left[a\right]}[b]$$

    calculate f(DV(t)) of $${\text{CM}}_{\text{CH}\left[a\right]}[b]$$

     $$P_b$$ (DDV(t)) ←f( $$E_b(t)$$ )  ×  f(DV(t))

   if ( $$P_b$$ (DDV(t)) of $${\text{CM}}_{\text{CH}\left[a\right]}[b]$$ is max value) then

    nextCH ← $${\text{CM}}_{\text{CH}[a]}[b]$$

  end

  CH′[a] ← nextCH

 end

 for $$a=\mathit{0}$$ to G

  for $$b=\mathit{0}$$ to $$N-\mathit{1}$$

   if (Region including CH′[a] ≡ Region including $$N[b]$$ ) then

     $${\text{Dir}}_{{\text{CH}}^{\prime }[a]N[b]}\leftarrow \left|{\text{Dir}}_{{\text{CH}}^{\prime }[a]}-{\text{Dir}}_{N[b]}\right|$$

     $${\nu }_{{\text{CH}}^{\prime }[a]N[b]}$$ ← $$\left|{\nu }_{{\text{CH}}^{\prime }[a]}-{\nu }_{N[b]}\right|$$

   if (0 ≤ ( $${\text{Dir}}_{{\text{CH}}^{\prime }[a]}/\left|{{\text{Dir}}_{N[b]}}^{\text{rs}}\right|$$ ) ≤ 1) and (0 ≤ ( $${\nu }_{{\text{CH}}^{\prime }[a]}$$ / $$\left|\mathrm{\Delta }\nu \right|$$ ) ≤ 1) then

     $${\text{CM}}_a^{\prime }\ni N[b]$$

  end

 end

 output cluster head node group CH′

 output cluster member node group of all cluster head node i   $${\text{CM}}_i^{\prime }$$

end

In Pseudocode 2, $N[i]$ is the number of nodes located in the networks. G refers to the number of the cluster head nodes and Gm is the number of cluster member nodes. To maintain cluster formation, the cluster head node calculates the probability of exchange of the cluster member node considering energy, velocity, and direction in ${\text{CM}}_i$ . When a cluster member node has the maximum probability of exchange, it becomes the next cluster head node. The exchanged cluster head node performs cluster formation.

4. Simulation and Results

In this paper, we demonstrate the efficient connection of the proposed algorithm. We compare the LIC algorithm that selects the cluster head node with the lowest ID algorithm and the MOBIC algorithm which selects the cluster head node with the slowest speed. The DDV-hop algorithm forms a cluster where the nodes are similar in their direction and velocity. Thus, we have a simulation by velocity, direction, energy, and transmission. Equation (19) shows the packet delivery ratio by velocity and direction:

$$\begin{array}{l}\text{PDR}\left(t\right)\\ =\left\{\begin{array}{ll}\frac{{\text{flow}}_{\text{BS}}\left(t\right)}{{\sum }_{i\in \text{CH}}{\sum }_{j\in {\text{CM}}_j}{\text{flow}}_j\left(t\right)}·\text{arg}\text{max}{P}_j\left(\text{DDV}\left(t\right)\right),\hfill & C_j\left(t\right)=\mathrm{1}\hfill \\ \frac{{\text{flow}}_{\text{BS}}\left(t\right)}{{\sum }_{i\in \text{CH}}{\sum }_{j\in {\text{CM}}_j}{\text{flow}}_j\left(t\right)}·\text{arg}\text{max}{P}_j\left(\text{DV}\left(t\right)\right),\hfill & C_j\left(t\right)=\mathrm{0},\hfill \end{array}\right.\end{array}$$

(19)

where $\text{PDR}(t)$ is the packet delivery ratio of the network [22, 23]. ${\text{flow}}_{\text{BS}}(t)$ is the transmitted data received by the base station in the proposed algorithm. $\text{CH}$ refers to the group of the cluster head nodes in the network and ${\text{CM}}_i$ is the group of the cluster member nodes in the cluster head node i. ${\text{flow}}_j(t)$ is the data sent by the cluster member node to the base station. $\text{arg}\text{max}{P}_j\left(\text{DDV}\left(t\right)\right)$ refers to the base station that receives the data by the proposed algorithm using direction, velocity, and energy. $\text{arg}\text{max}{P}_j\left(\text{DV}\left(t\right)\right)$ refers to the base station that receives the data by the proposed algorithm using direction and velocity. $C_j\left(t\right)$ is the function whether the cluster member node was elected or not. When the cluster head node was exchanged, $C_j\left(t\right)$ is 1. Thus, the $\text{PDR}(t)$ is calculated according to the upper part of (19). When the cluster head node was not exchanged, $C_j\left(t\right)$ is 0. Thus, the $\text{PDR}(t)$ is calculated according to the lower part of (19).

The moving model of the node has adopted a random direction model that has set a new direction when the node is located around the network area. Furthermore, we assume that the base station is located in the center of the network and that the network area is divided into four regions by the base station. The simulation environments are shown in Table 5.

Table 5

Simulation environments.

Parameter	Value
Network area (m2)	1000 × 1000, 1200 × 1200, 1500 × 1500, 1800 × 1800, and 2000 × 2000
Max velocity (m/s)	8, 12, 16, 20, and 24
Number of cluster head nodes	16, 20, 24, 28, and 32
Number of nodes	2000
Transmission range (m)	400, 450, 500, 550, and 600
Transmission cycle (sec)	1
Simulation time (sec)	300
Pause time (sec)	30, 60, 90, 120, 150, 180, 210, 240, and 270
Weight of energy	0.5
Weight of direction and velocity	0.5
Initial node energy (J)	100

4.1. Number of Clusters

To confirm the packet delivery ratio, we have simulated by the number of clusters. The number of clusters depends on the direction and region. Therefore, we assume that the regions imply a division into quadrants and that the threshold of direction $({{\text{Dir}}_i}^{\text{rs}})$ is four to eight. The network area was increased from 1000 × 1000, 1500 × 1500 and 2000 × 2000, velocity as 1~16 m/s. The number of clusters ranged from 16 to 32 and transmission range was 450 m. Simulation results are shown in Figures 9–11.

Figure 9

The packet delivery ratio by the number of clusters and 1000 × 1000 m².

Figure 10

The packet delivery ratio by the number of clusters and 1500 × 1500 m².

Figure 11

The packet delivery ratio by the number of clusters and 2000 × 2000 m².

The DDV-hop algorithm shows about 90% packet delivery ratio without a reference to the number of clusters when the network area is 1000 × 1000 m² (see Figure 9). As shown in Figure 10, the DDV-hop algorithm yields about 78% packet delivery ratio without a reference to the number of clusters when the network area is 1500 × 1500 m². As shown in Figure 11, the DDV-hop algorithm shows about 69% packet delivery ratio without a reference to the number of clusters when the network area is 2000 × 2000 m². By contrast, the LIC algorithm generally shows 10% packet delivery ratio of the number of clusters and the MOBIC algorithm shows 20% packet delivery ratio. Therefore, the network area has increased and the packet delivery ratio of the DDV-hop algorithm has decreased and maintains a higher packet delivery ratio than those of other cluster algorithms. These simulation results suggest that the DDV-hop algorithm shows a more continuous connection as compared to other algorithms.

4.2. Network Area

In this section, we proceed to the test to see the packet delivery ratio according to the network area. The network area is increased from 1000 × 1000 m² to 2000 × 2000 m². The velocity of node is 1~16 m/s, transmission range is 450 m, and the number of clusters is 16 to 32 (see Figures 12–14).

Figure 12

The packet delivery ratio by the network area and number of clusters $(16)$ .

Figure 13

The packet delivery ratio by the network area and the number of clusters $(24)$ .

Figure 14

The packet delivery ratio by the network area and the number of clusters $(32)$ .

As shown in Figure 12, despite the increase of the network area, the DDV-hop algorithm shows the packet delivery ratio that has decreased from 91% to 61% when the number of clusters is 16. Furthermore, as shown in Figure 13, the DDV-hop algorithm shows the packet delivery ratio that has decreased from 90% to 62% when the number of clusters is 24. Finally, the DDV-hop algorithm shows the packet delivery ratio that has decreased from 88% to 63% when the number of clusters is 32 (see Figure 14). The LIC algorithm shows the packet delivery ratio that has decreased from 18% to 6% when the network area is increased. The MOBIC algorithm also shows the packet delivery ratio that has decreased from 33% to 13% when the network area is increased. In these simulation results, the packet delivery ratio of the DDV-hop, the LIC, and the MOBIC algorithms is decreased when the network area is increased without a reference to the number of clusters. However, the DDV-hop algorithm shows the packet delivery ratio that is higher than that in the LIC and MOBIC algorithms.

4.3. Transmission Range

Furthermore, we simulated the packet delivery ratio by transmission range. In general, when transmission range increases, the cluster head node can join more cluster member nodes. Thus, we set transmission range from 400 m to 600 m. The network area was increased from 1000 × 1000 m², 1500 × 1500 m² and 2000 × 2000 m², the number of clusters was set at 16, and the velocity was 1~16. The simulation results are shown in Figures 15–17.

Figure 15

The packet delivery ratio by transmission range and 1000 × 1000 m².

Figure 16

The packet delivery ratio by transmission range and 1500 × 1500 m².

Figure 17

The packet delivery ratio of transmission range and 2000 × 2000 m².

As shown in Figure 15, when the transmission range is increased, the proposed algorithm shows the packet delivery ratio that has increased from 81% to 96% when the network area is 1000 × 1000 m². Figure 16 illustrates that the DDV-hop algorithm shows the packet delivery ratio that has increased from 70% to 92% when the network area is 1500 × 1500 m². In Figure 17, the DDV-hop algorithm shows the packet delivery ratio that has increased from 54% to 81% when the network area is 2000 × 2000 m². According to the increase of transmission range, the LIC algorithm maintains the packet delivery ratio that is 2% to 20% without a reference to the network area. Furthermore, the MOBIC algorithm is shown in the packet delivery ratio that is 25% to 35% when the network area is 1000 × 1000 m². However, the network area is increased and the packet delivery ratio of the MOBIC algorithm is decreased by 5%. These simulation results suggest that, according to the increased transmission range, the proposed algorithm offers a more continuous connection as compared to other algorithms.

4.4. Velocity of Nodes

Furthermore, we simulated the packet delivery ratio by velocity of a node. The max velocity of a node was set at 8 m/s to 24 m/s. The network area was increased from 1000 × 1000 m², 1500 × 1500 m² and 2000 × 2000 m², the number of clusters was set at 16, and transmission was 450 m. Simulation results are shown in Figures 18–20.

Figure 18

The packet delivery ratio by max velocity and 1000 × 1000 m².

Figure 19

The packet delivery ratio max velocity and 1500 × 1500 m².

Figure 20

The packet delivery ratio by max velocity and 2000 × 2000 m².

As shown in Figure 18, due to the increase the maximum velocity of a node, the cluster was broken frequently. So the packet delivery ratio of compared algorithm is lower than the proposed algorithm. The proposed algorithm maintains the packet delivery ratio higher than compared algorithm, because this algorithm performs the cluster by the velocity and the direction. In Figure 19, the DDV-hop algorithm shows the packet delivery ratio that has decreased from 79% to 74% when the network area is 1500 × 1500 m². In Figure 20, the DDV-hop algorithm shows the packet delivery ratio that has decreased from 65% to 59% when the network area is 2000 × 2000 m². The packet delivery ratio of the MOBIC algorithm has remained stable (from 30% to 33%) when the network area is 1000 × 1000 m². The network area is increased and the packet delivery ratio of the MOBIC algorithm is decreased by 7%. The LIC algorithm maintains the packet delivery ratio of about 3% to 29% without a reference to the network area. These simulation results suggest that, according to the increased velocity and network area, the proposed algorithm offers a more continuous connection as compared to other algorithms.

5. Conclusions

MANET consists of nodes that have mobility properties such as direction and velocity. Due to the characteristics of a node, MANET frequently exchanges topology. Due to the exchange topology, MANET happens to experience overhead and energy consumption is inefficient. To solve these problems, this paper proposed the DDV-hop algorithm. The proposed algorithm is a cluster algorithm that uses direction and velocity as the components of cluster formation.

We proposed an algorithm for performing cluster formation where the base station establishes standards of direction and velocity. The cluster head node is determined by these standards. The cluster head node joins cluster members with similar velocity and direction. Afterwards, to maintain cluster formation, the cluster head node periodically exchanges. For the exchange of the cluster head node, a cluster member node calculates the exchange probability using the distance between the cluster head node and the cluster member node, direction, and velocity. Based on the calculated probability of cluster members, the cluster head node chooses the cluster member node with the maximum probability and updates cluster information. To prove the efficient connection of the proposed algorithm, we compared random cluster algorithms against the proposed algorithm. The simulation results suggest that the DDV-hop algorithm is higher than related cluster algorithms with regard to the packet delivery ratio. Thus, we can conclude that the proposed DDV-hop algorithm succeeded in its goal of maintaining communication with a lower communication overhead and overall shows a better performance than existing protocols.