Keywords

1 Introduction

Ad hoc network is a kind of temporary self-organizing network system based on multi-hop routing. There is no need for fixed infrastructure support in wireless Ad hoc network. All nodes are equal, and each node has the ability of wireless communication and the basic routing function [1]. Compared with centralized control networks, wireless Ad hoc network has the characteristics of dynamic network topology, strong invulnerability and self-healing [2]. For the disadvantages of limited energy and bandwidth, as well as poor security, wireless Ad hoc network still has many challenges to be solved [3]. As two core technologies of Ad hoc network, the channel intervention mechanism of Medium Access Control (MAC) layer and the routing technology of network layer, still have many problems, which restrict its application.

Traditional MAC protocols for wireless networks are basically designed for Wireless Local Area Networks (WLAN). When they are applied to Ad hoc network, common problems such as long access delay and unfair resource allocation come into being. In order to improve the utilization of the Ad hoc network, a lot of work has been done. In [4], a new back-off scheme in the saturated network scenario is proposed. This scheme does not attempt to adjust the back-off window, but makes small modifications during the back-off freezing process to determine the optimal configuration. In [5], time slot occupancy tables for nodes in the two-hop range are built to achieve Time Division Multiple Access (TDMA) dynamic allocation by monitoring the periodic broadcast control messages. Therefore, the throughput is improved and the delay is reduced. Although contention based protocols are simple, flexible, robust to node mobility and independent of a central entity, conflicts may not be completely avoided. Meanwhile the TDMA based MAC protocol needs to know the entire topology of the network in order to provide scheduling that allows each node to access the channel, which causes the scalability problem [6].

The routing protocol is the most important support for multi-hop communication between nodes. The performance of the routing protocol directly affects the network implementation and overall performance. Optimized Link State Routing (OLSR) is a typical proactive routing protocol, which regularly produces and updates routing information to other nodes in the network. In OLSR, the hello messages are used to exchange neighbor node information, and the Topology Control (TC) messages are used to broadcast the integrated messages to the entire network. OLSR uses Multipoint Relay (MPR) mechanism, where only selected MPR nodes can forward TC messages to each node in the network [7]. In order to get the information of the whole network more quickly, some research has been done. [8] proposes an adaptive modification of the transmission interval of hello messages to improve the efficiency of neighbor node discovery and the performance of the whole network. In [9], the influence of the transmission interval of the hello messages and the TC messages during the network topology discovery is studied. Thereby, the purpose of fully perceiving the network topology change while minimizing the routing overhead caused by the beacon messages can be achieved. However, a large number of message collisions and message flooding during topology discovery remain unresolved in the above articles.

Compared with traditional topology-based routing protocols, location-based routing protocols use node location to guide the direction of packet forwarding. One of the most widely used routing protocols based on location information is Greedy Perimeter Stateless Routing (GPSR) which has effective relay node selection strategies to choose the relay node [10]. GPSR uses active update method to distribute location information through periodic beacon messages [10]. However, in order to obtain high-precision real-time location updates, it will bring more routing overhead [11]. In [12], a simple and efficient update algorithm based on dynamic fuzzy logic controller and mobility prediction is proposed. It can improve the accuracy of node location information in the case of less beacon traffic and achieve the purpose of saving network overhead. But this algorithm, like GPSR, needs to know the geographic location of the destination node in advance through the location service protocol. [13] gives a location based localized broadcast algorithm, which jointly uses distance based deferring and angle based deferring to encourage nodes with higher contributions to retransmit first. In this way, the broadcast redundancy can be reduced during achieving guaranteed packet delivery. However, when this broadcast mechanism is used, there is a certain probability that the time spent on route establishment will increase.

Since the traditional hierarchical optimization methods do not significantly improve the network performance, it is necessary to use available information across layers, that is, to exchange information directly between layers to perform subsequent operations [14]. [15] proposes a cross-layer scheme, which is based on the Adhoc On-demand Distance Vector (AODV) routing of the network layer and the distributed scheduling protocol of the MAC layer. In [15], the route layer uses the link resource to select the best route, and by adding bandwidth allocation into the routing messages, the resource allocation is accomplished during the establishment of the route.

In order to further improve the performance of Ad hoc network, this paper proposes a Hexagonal Clustering, Position and Time slot based (HCPT) protocol for Very High Frequency (VHF) maritime communication scenario. In this communication scenario, the channel is dominated by Rician fading channel, and the communication range is mainly limited by the distance between sender and receiver. Moreover, because geographic location information can be easily obtained through Geographic Information System (GIS), cluster management can be carried out by geographical location. In HCPT, clusters and time slots are divided according to geographic location, and information in the cluster is forwarded through the cluster heads. On this basis, an effective algorithm to find routes through the geographical locations of cluster heads is proposed. Simulation results show that HCPT can effectively reduce network routing overhead and improve packet delivery rate.

The paper is organized as follows. Section 2 presents the system model. Then, the cross-layer protocol is designed in Sect. 3. Simulation results and analyses are provided in Sect. 4. Finally, conclusions are made in Sect. 5.

2 System Model

2.1 Assumption

In the HCPT protocol, we assume that each node obtains its own geographic location information through GIS and keeps the clocks synchronized. And there is no fixed central node in any cluster.

2.2 Geographic Location Based Clustering

Although the planar Ad hoc network is simple in structure, when the network scale expands, the routing overhead also increases, which causes the problem of poor expansibility. Layered Ad hoc is more suitable for large-scale networks than planar Ad hoc. A hierarchical Ad hoc network has a cluster head in each area which manages the nodes in the cluster and communicates with other cluster heads. Therefore, routing overhead is reduced and the network is easy to be managed [16].

By using hexagonal clustering structure to closely spread the network, each cluster has the same structure and the same coverage area. In this way, clusters can completely cover the entire network area [17, 18].

In HCPT protocol, hexagonal clustering is also adopted. The entire network area is divided into multiple hexagons by corresponding algorithm based on location information. Through this clustering method, nodes can clearly know the clusters to which they belong with the help of their geographic location information. In addition, the hexagon cluster is further divided into 6 equilateral triangles and marked from 1 to 6 in Fig. 1. Each index corresponds to a time slot. By this way, the nodes with different indexes but within a cluster can avoid communication collision. Moreover, the nodes with the same index but in different clusters can send hello messages at the same time, which achieving the effect of space division multiplexing.

Fig. 1.
figure 1

Network scenario divided with hexagon

Full size image

2.3 Communication Range

In this paper, the radius of a hexagon is R and the communication radius is set to . In order to enable TC messages generated by cluster heads to be broadcast to neighboring clusters successfully, we need to expand the communication range between cluster heads. The communication radius can be extended by reducing the communication bandwidth according to the free space loss model [19] and the reception sensitivity formula [20], which are shown in (1) and (2), respectively.

$$\begin{aligned} {L_{bf}} = 32.4 + 20\log f + 20\log d \end{aligned}$$
(1)

The relationship between free space loss (\({L_{bf}}\)) and frequency (f) and distance (d) is shown in (1), where \({L_{bf}}\) in dB, f in MHz and d in km.

$$\begin{aligned} {S_i}(dbm) = - 174 + 10\log B + NF + {(S/N)_o} \end{aligned}$$
(2)

The relationship between receiver sensitivity (\({S_i}\)) and thermal noise (NF), bandwidth (B), and output signal-to-noise ratio of the receiver \(({(S/N)_o})\) is shown in (2), when phase noise is not considered in a non-spread spectrum system. In the above formula, B is in Hz.

$$\begin{aligned} {P_t} - {L_{bf}} = {S_i}(dbm) \end{aligned}$$
(3)

In (3), \({P_t}\) represents the transmit power. By combining (1), (2) and (3), it can be concluded that when d is need to be doubled, we can only reduce B by four times to make the equation tenable. In the extreme case that two neighbor cluster heads still cannot communicate after expanding the scope of communication, a member node between the two cluster heads is designated to forward the TC messages. In this way, the information within the cluster can be extended to the whole network.

3 Cross-Layer Protocol Design

When the protocol is designed in this paper, the TDMA mechanism is used to divide the time into time frame cycles. As shown in Fig. 2, each time frame cycle is T which includes a neighbor node discovery period \({T_1}\) and a data transmission period \({T_2}\).

The hexagon is divided into 6 equilateral triangles, and the neighbor node discovery period is correspondingly divided into 6 time slots. The nodes with different indexes take different time slots to transmit hello messages, which are used for neighbor node discovery. For the data transmission phase, the TC messages and the data messages share the same wireless channel, and communication collision can be reduced by CSMA/CA. Meanwhile, handshake mechanism is required before point-to-point data transmission. In order to achieve effective wireless shared channel, refer to the IEEE 802.11 protocol, the node first uses the RTS/CTS to perform control channel reservation. After the reservation is successful, data transmission can be carried out, and the reliability of the network can be ensured through the DATA/ACK process. The flow chart for each node is shown in Fig. 3.

Fig. 2.
figure 2

TDMA frame allocation

Full size image
Fig. 3.
figure 3

The flow chart for each node in a cycle

Full size image

3.1 Neighbor Node Discovery

Neighbor nodes of a node refer to nodes within the communication range of the node. In the phase of neighbor node discovery, the nodes send hello messages according to the time frame corresponding to their geographic location. The hello messages are generated and sent only during the discovery phase of the neighboring node. There is no re-transmission mechanism. If it is not sent within the specified neighbor discovery time, discard will be happen. In order to reduce communication collisions when multiple nodes send messages at the same time slot, a random backoff is added before the hello message is sent according to the CSMA/CA mechanism. The hello message contains the sender IP address and geographic location. The nodes that are not in the current sending slot remain silent. They only receive the hello messages and update their neighbor node tables.

The detail process of this neighbor node discovery can be found in our previous work [21].

3.2 Cluster Head Election Algorithm

After six time slots, each node locally compares its own location with that of its neighbors in the same cluster, and the nearest node to the cluster center declares to be the cluster head. While other nodes remain members in the cluster. As we set the communication range to be , the cluster head which locals within radius of the cluster can communicate with any node in the same cluster. For a few cases where there are no nodes within radius, there may be edge nodes that are not within the communication range of the selected cluster head. Then another cluster head will be generated among these edge nodes in the next stage, which will be explained later.

3.3 Network Topology Discovery

When the clusters are selected, The TC messages are periodically generated and broadcast through the cluster heads. The TC message contains the IP address of all nodes in the cluster and the geographic location information of the cluster head. The cluster head forwards the TC messages, which are produced by other clusters, after receiving them, so that the TC messages can be broadcasted to the entire network.

In order to facilitate sending and receiving messages between cluster heads, the cluster heads use low speed for transmission to expand the communication range. In HCPT protocol, the transmission rate between cluster heads is of the normal transmission rate.

The TC message frame structure is shown in Fig. 4. Besides the intra-cluster node information, the TC message mainly includes the following fields:

Fig. 4.
figure 4

TC message frame structure

Full size image

Type: Used to indicate the message type, such as TC message, 8-bit storage.

Packet length: Used to indicate the total length of the packet, in bytes, 8-bit storage.

Seq (Message Sequence Number): Used to identify the old and new messages to ensure that the message will not be forwarded twice by the same node. Each time there is a new message, the sequence number is increased by 1, 8-bit storage.

Vtime: Used to indicate the effective time of the message, 8-bit storage.

TTL: Used to indicate the maximum number of hops that the message will be sent. The TTL must be decremented by 1 before the message is forwarded. When a node receives a message with a TTL equal to 0 or 1, the message cannot be forwarded under any circumstances. The flood radius can be limited by setting this field.

Hop count: Initialized to 0. This field contains the number of hops the message has reached and is incremented by 1 before the message is forwarded.

After receiving the TC message in the cluster, if the member node finds that the node information in the cluster of the TC message does not contain itself, that means that the node is an edge node. Among all edge nodes in the cluster, the nearest edge node to the cluster center will become a new cluster head. The information of its neighbor nodes in this cluster, which is not included in the received TC message, is packaged and broadcast to the whole network through the new generated TC message. The whole process of cluster head election is detailed in Table 1 and Algorithm 1.

The TC messages are forwarded and flooded between cluster heads. After the cluster heads receive all the topology information sent by other cluster heads in the network, the topology information of the entire network can be obtained. The non-cluster head nodes of the whole network only receive the TC messages, process the data without forwarding, and use the update information to acquire the state of the current network. The process flow of TC messages is shown in Fig. 5. After completing topology discovery and real-time update, all nodes know the geographic location and information of the cluster heads of the whole network, and know in which cluster the other nodes are. In this way, it is not necessary to know the geographic location of all nodes in the entire network, so the size of the TC messages is reduced, which reduces the overhead of topology discovery and maintenance.

figure a

3.4 Route Establishment

During the process of neighbor node discovery, each node knows the geographic location of its neighbor nodes through the exchange of the hello messages. Then through the broadcasting of the TC messages, the specific location of the cluster head and the information of which cluster the nodes belong to are obtained.

Fig. 5.
figure 5

Processing after receiving TC messages

Full size image
Table 1. Major parameters of cluster head election algorithm
Full size table

After obtaining the above geographic location information, how to select the next hop more effectively is an important part of routing discovery. In HCPT, a packet forwarding strategy based on cluster head location information is designed. When there is a data transmission request, the node searches the cluster head location of the destination node, and then combines the greedy principle to select the neighbor node closest to this cluster head as the next hop. For the last-hop node, if the destination node happens to be the neighbor node of the current node, the data can be sent directly to the destination node without forwarding through the cluster head of the destination node.

The greedy routing transmission process in the HCPT is shown in Fig. 6. The source node is S, the destination node is D, and the node H is the cluster head of the cluster where the destination node D is located. The dotted circles in the graph represent the maximum data communication coverage of the center node of the circle. All the nodes in the circle are the candidates of the next hop for the center node.

Fig. 6.
figure 6

Example of greedy forwarding

Full size image

As shown in Fig. 6, node S will uses greedy forwarding strategy to select the node M, which is nearest to H, as its next hop relay node. When the data packet is forwarded to M, M also selects the neighbor node N, which is closest to H, to forward the data packet according to the greedy principle. After successfully receiving the data packet, N searches its neighbor node list and finds that the destination node D is reachable. Then the packet is directly transmitted to the node D.

When the distance from the neighbor node to the destination node is farther than the distance from the current node to the destination node, and the current node to the destination node is unreachable, greedy forwarding is no longer applicable. At this point, the peripheral forwarding mode is triggered to search for new routes along the perimeter of the void area using the right-hand rule [22].

After bypassing the void area, the routing policy will automatically switch back to the greedy forwarding mode again. This forwarding will continue until the packet is successfully sent to the destination node. If the nodes are evenly distributed and tightly connected, the void area is hardly to occur. In the network scenario where the nodes are sparse, the peripheral forwarding mode is used to solve the problem. Therefore, this can adapt to the dynamic changes of the communication network.

In HCPT, by selecting the neighbor node closest to the cluster head of the destination node as the relay node, data packets are forwarded hop-by-hop, which can make the hop count of selected path to be the shortest one. Therefore, a smaller end-to-end delay can be obtained. Moreover, since the nodes only need to maintain the information of their neighboring nodes and the specific locations of all cluster heads, the performance will not be degraded due to the frequent breakage of the link. Thus, the routing overhead and the time for establishing the route in the network are reduced.

4 Simulation Results and Analysis

The Network Simulator 2 (NS2) software is used for network simulations. When the simulation runs, the node discovery for the whole network is conducted first, followed by data transmission. This section first gives the efficiency of network topology discovery of HCPT, and then gives the overall network performance of HCPT.

4.1 Topology Discovery Efficiency

In order to obtain the performance of network topology discovery of HCPT, we selected the proactive routing OLSR for comparison. The simulated network environment of OLSR and HCPT is the same, and we take the topology discovery every two seconds, which means the time frame cycle \(T = 2\) s.

The following is the simulation scenario: 20 nodes are randomly distributed within a square of \(500\,\mathrm{m} \times 500\,\mathrm{m}\), the wireless transmission distance \({D_t}\) is 250 m, the neighbor node discovery period \({T_1}\) is 60 ms, the radius of hexagonal cellular is set to 166.7 m, and the unlisted parameters are set to the default value in NS2.

Figure 7 shows the ratio of node discovery in HCPT and OLSR. As can be seen from the figure, within the first 2 s, the HCPT can discover 89% of nodes while OLSR can only discover 19% of nodes. And the HCPT can discover all nodes in about 2.2 s, but OLSR needs about 5.2 s. This is because in HCPT protocol, as shown in Figs. 1 and 2, the neighbor discovery is divided into 6 time slots by location, and the hello messages are sent in specific time slots, which greatly improves the transmission success rate of the hello messages. After that, the cluster heads send and forward the TC messages so that the node information is broadcast to the whole network quickly.

In OLSR protocol, hello messages and TC messages are generated simultaneously at the beginning of each time frame cycle. At the beginning, for the information collected by the MPRs is insufficient, the information sent by the TC messages is less effective, the rate of node discovery is slow. Later, when the MPRs have collected enough node information, the rate of node discovery begins to improve. When the new cycle arrives, the packages of the previous cycle may still have not been sent, so the rising phase of the OLSR curve will be postponed accordingly.

Fig. 7.
figure 7

Ratio of node discovery in the whole network

Full size image

In summary, compared to OLSR, the HCPT can discover the entire network topology more efficiently.

4.2 Overall Network Performance

In this section, we compare the overall performance of the cross-layer HCPT protocol with that of the standard OLSR and the newly improved OLSR algorithm [8]. The simulations run for 100 s and apply Constant Bit Rate (CBR) sources which send packets with the length of 512 bytes every 100 ms. The moving speed of nodes is changed from 1 m/s to 6 m/s, MAC layer is applied by IEEE 802.11, and other simulation parameters are the same as the section A. The following performance metrics are evaluated.

Packet Delivery Ratio (PDR): The ratio of number of data packets successfully delivered to the destination to the number of data packets generated by the sources.

Average End-to-End Delay (AEED): The ratio of the sum of transmission packet delays to the number of successfully received packets.

Network Routing Load (NRL): The ratio of the total number of routing packets transmitted to the total number of data packets delivered.

Fig. 8.
figure 8

NRL vs. speed

Full size image

The routing overhead of HCPT, OLSR, and the improved OLSR algorithm proposed by N. Harrag are giving in Fig. 8. We can see from Fig. 8 that The NRL of HCPT proposed in this paper and the improved OLSR algorithm proposed by N. Harrag are greatly improved compared with that of the traditional OLSR. The performance of HCPT is even slightly better than that of N. Harrag’s algorithm. His scheme is to control the overhead by adaptively changing the transmission interval of hello messages, while HCPT in this paper is to reduce the overhead by reducing the number of TC messages and the size of TC messages at the same time. This is because the TC messages are generated and forwarded by the cluster heads in HCPT, while in OLSR the TC messages are generated and forwarded by MPRs. In a same network, the number of cluster heads is much smaller than that of MPRs. Meanwhile, The TC message only contains the IP address of all nodes in the cluster and the geographic location information of the cluster head, which reduces the size of the message.

Figure 9 presents the relationship between the PDR and the speed. From Fig. 9, we can see that the PDR of HCPT is much superior to the traditional OLSR and the improved OLSR. HCPT can maintain a high level of PDR when the node moves at a slower speed. As the speed of node movement increases, although the PDR of HCPT has decreased, it still maintains a great advantage compared with the other two protocols. This excellent performance should owe to the time slot mechanism during the neighbor node discovery period and the TC messages only broadcasting within cluster heads in HCPT. By the time slot mechanism, the collisions between the hello messages are avoided as much as possible. Moreover, the network topology discovery based on the cluster head mechanism has smaller routing overhead, and the greedy principle forwarding mechanism based on the geographic location assistance can more effectively select the next relay node to transmit the data packet. However, in such a dense network scenario, the other two algorithms suffer from a large number of packet loss due to collisions between nodes, which leads to a decrease in the efficiency of network topology discovery, and results in a large number of packet losses.

Fig. 9.
figure 9

PDR vs. speed

Full size image
Fig. 10.
figure 10

AEED vs. speed

Full size image

Figure 10 shows the AEED vs. speed. In Fig. 10, the delay of HCPT is slightly larger than that of the other two protocols, but this is due to the high delivery rate. Because high delivery rate means more data links are successfully established. For the other two protocols, when there is a data transmission request between two distant nodes, the link establishment may not be successful, and the links successfully established in the network are almost shorter links, which bring a smaller average delay. For the HCPT protocol, when the moving speed increases, the topology changes faster, so the information of the neighbor node stored may not be updated in time. This will also lead to the unsuccessful establishment of part of the long link, so the average delay decreases as the moving speed increases from 4 m/s to 5 m/s.

5 Conclusion

In this paper, we propose a clustered cross-layer protocol named HCPT based on hexagonal clustering and time slot. By simplifying the content of the TC messages and forwarding the TC messages using the cluster heads, the network overhead is reduced, and the network topology discovery rate is improved. Compared with the topology discovery of proactive routing OLSR, HCPT can discover the whole network topology more effectively. Compared with the overall performance of standard OLSR and the improved OLSR algorithm proposed by N. Harrag, the HCPT has smaller network routing load and higher packet delivery ratio.