# Routing Protocol in VANETs Equipped with Directional Antennas: Topology-Based Neighbor Discovery and Routing Analysis

Authors: Haipeng Li; Zhen Xu
Journal: Wireless Communications and Mobile Computing
 (2018)

---

## Abstract

In Vehicular Ad Hoc Networks (VANETs), directional antenna is a good solution if a longer transmission distance is needed. When vehicles are equipped with directional antennas, however, complete paths from the sources to the destinations there may not exist. Epidemic routing protocol is considered as one of the well-performed routing protocols when the networks are intermittently connected but it can cause a heavy load to the network and great energy consumption to the nodes. First in this paper, we propose a novel neighbor discovery algorithm which makes nodes be able to sense the topology changes around them and arrange their directional antennas accordingly. Secondly, we propose a routing protocol which is based on the conventional epidemic routing protocol, and nodes make their routing decisions according to the information collected during the neighbor discovery process. Experimental results show that the proposed neighbor discovery algorithm has better performance especially in the scenario where the node density is low. Moreover, the matching routing protocol can effectively reduce the load of the network and successfully deliver the packets to its destination in a reasonable short delay.


---

## Body

## 1. Introduction

Directional antennas have been widely used in wireless ad hoc networks recently. It can produce higher gain, provide greater transmission range, and improve the network spatial reuse and throughput as well. Furthermore, the directional selectivity also reduces the co-channel interference of neighboring nodes, and directional antennas bring potential performance improvement to the mobile ad hoc networks. Despite the improvements brought by the directional antennas, their deployments also bring severe challenges to the nodes such as the neighbor discovery, and the network suffers from frequent disruptions, making the topology unstable, that is, no consistent paths between each pair of nodes.Considering that, in a considerable proportion of real scenarios, the mobility of vehicles is not purely random. Vehicles show strong location and group preference. For example, for the vehicles in the earthquake relief sites, they work at the areas which are under serious destruction and these areas are not uniformly distributed. Moreover, vehicles can change their locations from one area to another. Based on this kind of scenario, we formulate the neighbor discovery algorithm and the matching routing protocol in this paper. The main contribution of this paper is about two aspects. Firstly, we design a novel neighbor discovery algorithm for intermittent networks which are equipped with directional antennas. In the proposed neighbor discovery algorithm, nodes monitor the HELLO message receiving frequency for each sector to estimate the topology variations and adjust the steering time of each sector according to the history records maintained in their neighbor node lists. Secondly, we propose a routing protocol which is derived from the proposed neighbor discovery algorithm. In the routing protocol, source node makes its routing decisions according to the status of the nodes in its two hops. The stability of neighbor relationships, the communicating probability, and the time schedule for the directional antennas of each participating node are all taken into consideration when the source node makes its routing decisions.The rest of the paper is organized as follows. In Section2, we introduce the related researches about neighbor discovery algorithms and routing protocols for opportunistic networks. In Section 3, we present the system models. In Section 4, we introduce and analyze our proposed neighbor discovery algorithm. Our proposed routing protocol is demonstrated in Section 5. Section 6 provides simulation results. Finally, we conclude the paper in Section 7.


## 2. Related Work

### 2.1. Neighbor Discovery

As we discussed in Section1, neighbor discovery is the key initial step for establishing the connections among nodes in intermittent networks. In recent research papers about neighbor discovery protocols with pure directional antennas, we categorize them into two classes,deterministicandrandomprotocols. In deterministic protocols [1–3], nodes steer their directional antennas in preset sequences. Deterministic protocols can guarantee the bounded neighbor discovery delay. However, most of them need time synchronized which is not practical in some applications. In random protocols [4–10], nodes randomly select a direction to transmit or receive HELLO messages. Compared to deterministic protocols, the most obvious advantage of probabilistic protocols is that they do not need to be synchronized, in which they are more robust and adaptive to complex scenarios. However, in most probabilistic or random protocols, the topology change of the network is not concerned. Reference [1] focuses on the oblivious neighbor discovery problems and has proposed an oblivious discovery protocol which achieves guaranteed oblivious discovery with order-minimal worst-case discovery delay. However, the topology change is not its concern. References [2–10] focus on the MAC protocols to achieve a better neighbor discovery performance. References [2–8] all need time synchronized to ensure their performance and their directional antennas just simply choose a direction when they run the neighbor discovery process. References [11, 12] take the topology into consideration. Reference [11] works on topology control problems. In this work, nodes track only a subset of their discovered neighbor nodes and it proposes a scheme called Di-ATC which tries to minimize the variance of the angular separation between the tracked neighbors of a node. In [12], nodes discover their neighbor nodes in one sector with increasing power so as to identify the closest nodes in the sector. However, [11] assumes that the network is connected at all times and the path stretch after topology control is low and [12] is only suitable for a static ad hoc network which is not realistic in VANETs with directional antennas equipped.


### 2.2. Routing Protocols

Since there are no complete paths in intermittent vehicle ad hoc networks with directional antennas, traditional end-to-end routing protocols for mobile ad hoc network (e.g., DSR, AODV) are not suitable anymore. The existing routing protocols that are concerned with intermittent networks mostly focus on the load easement while the successful transmission is guaranteed. In [13, 14], nodes only generate one copy of the data packets to reduce the load of network. In methods [15–18], nodes selectively send the copies of packets to their neighbor nodes. In thesereplication-based methods, nodes carefully make the routing decisions according to several rules such asutility-basedrouting [15] orprobability-basedrouting [17]. They assume that movement patterns of node are not purely random and that future contacts depend on the past information. Reference [16] proposes a method calledSpray and Focus which refers to the fact that nodes firstly spray a fixed number of their data packets to the selected relay nodes and then nodes with only one copy of the packet can only forward this message further using asingle-copy utility-based scheme. In [18], they investigate the TTL on the copy of packets in order to reduce the load of the networks. Due to the dynamic topology of VANETs, the size of HELLO packets and the mobility should be taken into consideration for the routing decisions. Reference [19] investigates the MAC layer contention issue that it proposes BBNC, a backbone based routing protocol with interflow Network Coding. The position information of each backbone node is critical when nodes in [19] make their routing decisions. Reference [20] focuses on the effect of packet size on the performance of routing protocols; it uses a fuzzy logic-based algorithm to select relay nodes and uses a Q-learning based approach to tune the fuzzy membership functions. For the VANETs where nodes are equipped with directional antennas, the dynamic topology is mostly caused by the scan pattern of the directional antennas, and this is the emphasis of this paper. For the routing protocols which are focusing on the directional antenna, such as in [21], nodes make their routing decisions based on the information about the geographical position of the participating nodes, which needs the use of GPS. Reference [22] focuses on analyzing the relationship between the throughput and the beam width of the directional antenna. In general, they rarely consider the switch pattern of the directional antenna.


## 2.1. Neighbor Discovery

As we discussed in Section1, neighbor discovery is the key initial step for establishing the connections among nodes in intermittent networks. In recent research papers about neighbor discovery protocols with pure directional antennas, we categorize them into two classes,deterministicandrandomprotocols. In deterministic protocols [1–3], nodes steer their directional antennas in preset sequences. Deterministic protocols can guarantee the bounded neighbor discovery delay. However, most of them need time synchronized which is not practical in some applications. In random protocols [4–10], nodes randomly select a direction to transmit or receive HELLO messages. Compared to deterministic protocols, the most obvious advantage of probabilistic protocols is that they do not need to be synchronized, in which they are more robust and adaptive to complex scenarios. However, in most probabilistic or random protocols, the topology change of the network is not concerned. Reference [1] focuses on the oblivious neighbor discovery problems and has proposed an oblivious discovery protocol which achieves guaranteed oblivious discovery with order-minimal worst-case discovery delay. However, the topology change is not its concern. References [2–10] focus on the MAC protocols to achieve a better neighbor discovery performance. References [2–8] all need time synchronized to ensure their performance and their directional antennas just simply choose a direction when they run the neighbor discovery process. References [11, 12] take the topology into consideration. Reference [11] works on topology control problems. In this work, nodes track only a subset of their discovered neighbor nodes and it proposes a scheme called Di-ATC which tries to minimize the variance of the angular separation between the tracked neighbors of a node. In [12], nodes discover their neighbor nodes in one sector with increasing power so as to identify the closest nodes in the sector. However, [11] assumes that the network is connected at all times and the path stretch after topology control is low and [12] is only suitable for a static ad hoc network which is not realistic in VANETs with directional antennas equipped.


## 2.2. Routing Protocols

Since there are no complete paths in intermittent vehicle ad hoc networks with directional antennas, traditional end-to-end routing protocols for mobile ad hoc network (e.g., DSR, AODV) are not suitable anymore. The existing routing protocols that are concerned with intermittent networks mostly focus on the load easement while the successful transmission is guaranteed. In [13, 14], nodes only generate one copy of the data packets to reduce the load of network. In methods [15–18], nodes selectively send the copies of packets to their neighbor nodes. In thesereplication-based methods, nodes carefully make the routing decisions according to several rules such asutility-basedrouting [15] orprobability-basedrouting [17]. They assume that movement patterns of node are not purely random and that future contacts depend on the past information. Reference [16] proposes a method calledSpray and Focus which refers to the fact that nodes firstly spray a fixed number of their data packets to the selected relay nodes and then nodes with only one copy of the packet can only forward this message further using asingle-copy utility-based scheme. In [18], they investigate the TTL on the copy of packets in order to reduce the load of the networks. Due to the dynamic topology of VANETs, the size of HELLO packets and the mobility should be taken into consideration for the routing decisions. Reference [19] investigates the MAC layer contention issue that it proposes BBNC, a backbone based routing protocol with interflow Network Coding. The position information of each backbone node is critical when nodes in [19] make their routing decisions. Reference [20] focuses on the effect of packet size on the performance of routing protocols; it uses a fuzzy logic-based algorithm to select relay nodes and uses a Q-learning based approach to tune the fuzzy membership functions. For the VANETs where nodes are equipped with directional antennas, the dynamic topology is mostly caused by the scan pattern of the directional antennas, and this is the emphasis of this paper. For the routing protocols which are focusing on the directional antenna, such as in [21], nodes make their routing decisions based on the information about the geographical position of the participating nodes, which needs the use of GPS. Reference [22] focuses on analyzing the relationship between the throughput and the beam width of the directional antenna. In general, they rarely consider the switch pattern of the directional antenna.


## 3. System Model and Problem Formulation

### 3.1. System Model

#### 3.1.1. Directional Antenna Model

We assume that the set of nodes in the network is denoted byNˇ. Each node i∈Nˇ is equipped with only one set of directional antennas. For node i, we approximate the directional antenna as a circular sector of angle θi (0<θi≤2π), and there are Ni≜2π/θi sectors around it, indexed clockwise from 0 to Ni-1. When θi=2π, the directional antenna degenerates to an omnidirectional antenna. The set of sectors of nodei is denoted by S^i; Si∈S^i maintains a timer CSi. When CSi expires, the rotation mode of the directional antenna is decided by the status of the node:(i)
Pure neighbor discovery mode (PND-M): if there is no transmission task for the node, then it switches its directional antenna randomly to the next sector.(ii)
Data transmission mode (DT-M): if there are data packets conserved in the node and waiting to be transmitted, then the node begins to switch its directional antenna clockwise. In this mode, the scan pattern of each node is ordered and predictable so that the routing decisions are more precise.The initialCSi is equal for every sector and the rotation period is a constant number,T, where T=∑Si∈S^iCSi. The cover range of each node isR.


#### 3.1.2. Communication Model

We assume that the time unit isτ, which refers to the maximal time that a HELLO message needs to be broadcasted to its neighbor successfully. As shown in Figure 1, when nodei points its directional antenna to sector Si, it broadcasts a HELLO message and then it enters the receiving state until it switches its direction antenna to the next sector. When nodeireceives a HELLO message from nodej, then nodej is a discovered neighbor node for nodei. Only when two nodes point their directional antennas to the opposite direction and they are located in the transmission range of each other, the HELLO message can be received successfully. Moreover, when a node receives a HELLO message from another node, it will send back a response message conditionally. This mechanism is detailed in Section 4.Figure 1
Communication model.


#### 3.1.3. Mobility Model

In this paper, groups of nodes are scattered randomly in a square area at first, and a community is formed around the central position of each group. Then, nodes begin to walk inside their own community randomly. We assume that a node can walk beyond its current community to another one with a very small probability,P. The scenario is shown in Figure 2.Figure 2
Mobility model.


#### 3.1.4. Problem Formulation

As shown in Figure2, the relative positions among the vehicle nodes are stable since they show strong location and group preference. For example, for node 0, a great number of nodes walk on its north side and its south side, in which case it is unnecessary for node 0 to point its directional antenna to the east side and west side for a long time if it wants to discover more neighbor nodes in a short time. Moreover, as we mentioned, nodes can change their communities so that the scan pattern of node 0 can be out of date sometimes, in which case node 0 needs to adjust the scan pattern of its directional antenna to the updated topology around itself.In order to successfully deliver the packets in an intermittent network, the source node has to send plenty of data packet copies to the neighbors that it meets. However, it can cause heavy load of the network. Otherwise, if the source node simply chooses one of its neighbor nodes as the relay node, it cannot guarantee the successful delivery to the destination and leads to long delay. Therefore, the routing decision determines the transmission delay and the load and the energy consumption of the network.For example, for node 8 in Figure2, nodes 1, 3, 6, and 7 are the neighbor nodes maintained in its neighbor node list. When node 8 wants to send data packets to node 2, it needs to determine which neighbor nodes should be chosen to relay these packets. The answers of three questions about the neighbor nodes are critical when node 8 makes its routing decisions.For a specific possible relay node:(1)
What is the probability that node 8 can communicate with it?(2)
If node 8 sends its data packets to this relay node, what is the probability that it can relay these data packets to node 2 in one hop?(3)
What is the expected delay that it can successfully transmit these data packets to node 2?Here, we can formulate the research objective of this paper:To make the vehicle be able to adjust the scanning pattern of its directional antenna according to the topology around it and find out the optimal routing decisions to minimize the delay and the number of packet copies while successful packets delivery and short delay are guaranteed.


## 3.1. System Model

### 3.1.1. Directional Antenna Model

We assume that the set of nodes in the network is denoted byNˇ. Each node i∈Nˇ is equipped with only one set of directional antennas. For node i, we approximate the directional antenna as a circular sector of angle θi (0<θi≤2π), and there are Ni≜2π/θi sectors around it, indexed clockwise from 0 to Ni-1. When θi=2π, the directional antenna degenerates to an omnidirectional antenna. The set of sectors of nodei is denoted by S^i; Si∈S^i maintains a timer CSi. When CSi expires, the rotation mode of the directional antenna is decided by the status of the node:(i)
Pure neighbor discovery mode (PND-M): if there is no transmission task for the node, then it switches its directional antenna randomly to the next sector.(ii)
Data transmission mode (DT-M): if there are data packets conserved in the node and waiting to be transmitted, then the node begins to switch its directional antenna clockwise. In this mode, the scan pattern of each node is ordered and predictable so that the routing decisions are more precise.The initialCSi is equal for every sector and the rotation period is a constant number,T, where T=∑Si∈S^iCSi. The cover range of each node isR.


### 3.1.2. Communication Model

We assume that the time unit isτ, which refers to the maximal time that a HELLO message needs to be broadcasted to its neighbor successfully. As shown in Figure 1, when nodei points its directional antenna to sector Si, it broadcasts a HELLO message and then it enters the receiving state until it switches its direction antenna to the next sector. When nodeireceives a HELLO message from nodej, then nodej is a discovered neighbor node for nodei. Only when two nodes point their directional antennas to the opposite direction and they are located in the transmission range of each other, the HELLO message can be received successfully. Moreover, when a node receives a HELLO message from another node, it will send back a response message conditionally. This mechanism is detailed in Section 4.Figure 1
Communication model.


### 3.1.3. Mobility Model

In this paper, groups of nodes are scattered randomly in a square area at first, and a community is formed around the central position of each group. Then, nodes begin to walk inside their own community randomly. We assume that a node can walk beyond its current community to another one with a very small probability,P. The scenario is shown in Figure 2.Figure 2
Mobility model.


### 3.1.4. Problem Formulation

As shown in Figure2, the relative positions among the vehicle nodes are stable since they show strong location and group preference. For example, for node 0, a great number of nodes walk on its north side and its south side, in which case it is unnecessary for node 0 to point its directional antenna to the east side and west side for a long time if it wants to discover more neighbor nodes in a short time. Moreover, as we mentioned, nodes can change their communities so that the scan pattern of node 0 can be out of date sometimes, in which case node 0 needs to adjust the scan pattern of its directional antenna to the updated topology around itself.In order to successfully deliver the packets in an intermittent network, the source node has to send plenty of data packet copies to the neighbors that it meets. However, it can cause heavy load of the network. Otherwise, if the source node simply chooses one of its neighbor nodes as the relay node, it cannot guarantee the successful delivery to the destination and leads to long delay. Therefore, the routing decision determines the transmission delay and the load and the energy consumption of the network.For example, for node 8 in Figure2, nodes 1, 3, 6, and 7 are the neighbor nodes maintained in its neighbor node list. When node 8 wants to send data packets to node 2, it needs to determine which neighbor nodes should be chosen to relay these packets. The answers of three questions about the neighbor nodes are critical when node 8 makes its routing decisions.For a specific possible relay node:(1)
What is the probability that node 8 can communicate with it?(2)
If node 8 sends its data packets to this relay node, what is the probability that it can relay these data packets to node 2 in one hop?(3)
What is the expected delay that it can successfully transmit these data packets to node 2?Here, we can formulate the research objective of this paper:To make the vehicle be able to adjust the scanning pattern of its directional antenna according to the topology around it and find out the optimal routing decisions to minimize the delay and the number of packet copies while successful packets delivery and short delay are guaranteed.


## 3.1.1. Directional Antenna Model

We assume that the set of nodes in the network is denoted byNˇ. Each node i∈Nˇ is equipped with only one set of directional antennas. For node i, we approximate the directional antenna as a circular sector of angle θi (0<θi≤2π), and there are Ni≜2π/θi sectors around it, indexed clockwise from 0 to Ni-1. When θi=2π, the directional antenna degenerates to an omnidirectional antenna. The set of sectors of nodei is denoted by S^i; Si∈S^i maintains a timer CSi. When CSi expires, the rotation mode of the directional antenna is decided by the status of the node:(i)
Pure neighbor discovery mode (PND-M): if there is no transmission task for the node, then it switches its directional antenna randomly to the next sector.(ii)
Data transmission mode (DT-M): if there are data packets conserved in the node and waiting to be transmitted, then the node begins to switch its directional antenna clockwise. In this mode, the scan pattern of each node is ordered and predictable so that the routing decisions are more precise.The initialCSi is equal for every sector and the rotation period is a constant number,T, where T=∑Si∈S^iCSi. The cover range of each node isR.


## 3.1.2. Communication Model

We assume that the time unit isτ, which refers to the maximal time that a HELLO message needs to be broadcasted to its neighbor successfully. As shown in Figure 1, when nodei points its directional antenna to sector Si, it broadcasts a HELLO message and then it enters the receiving state until it switches its direction antenna to the next sector. When nodeireceives a HELLO message from nodej, then nodej is a discovered neighbor node for nodei. Only when two nodes point their directional antennas to the opposite direction and they are located in the transmission range of each other, the HELLO message can be received successfully. Moreover, when a node receives a HELLO message from another node, it will send back a response message conditionally. This mechanism is detailed in Section 4.Figure 1
Communication model.


## 3.1.3. Mobility Model

In this paper, groups of nodes are scattered randomly in a square area at first, and a community is formed around the central position of each group. Then, nodes begin to walk inside their own community randomly. We assume that a node can walk beyond its current community to another one with a very small probability,P. The scenario is shown in Figure 2.Figure 2
Mobility model.


## 3.1.4. Problem Formulation

As shown in Figure2, the relative positions among the vehicle nodes are stable since they show strong location and group preference. For example, for node 0, a great number of nodes walk on its north side and its south side, in which case it is unnecessary for node 0 to point its directional antenna to the east side and west side for a long time if it wants to discover more neighbor nodes in a short time. Moreover, as we mentioned, nodes can change their communities so that the scan pattern of node 0 can be out of date sometimes, in which case node 0 needs to adjust the scan pattern of its directional antenna to the updated topology around itself.In order to successfully deliver the packets in an intermittent network, the source node has to send plenty of data packet copies to the neighbors that it meets. However, it can cause heavy load of the network. Otherwise, if the source node simply chooses one of its neighbor nodes as the relay node, it cannot guarantee the successful delivery to the destination and leads to long delay. Therefore, the routing decision determines the transmission delay and the load and the energy consumption of the network.For example, for node 8 in Figure2, nodes 1, 3, 6, and 7 are the neighbor nodes maintained in its neighbor node list. When node 8 wants to send data packets to node 2, it needs to determine which neighbor nodes should be chosen to relay these packets. The answers of three questions about the neighbor nodes are critical when node 8 makes its routing decisions.For a specific possible relay node:(1)
What is the probability that node 8 can communicate with it?(2)
If node 8 sends its data packets to this relay node, what is the probability that it can relay these data packets to node 2 in one hop?(3)
What is the expected delay that it can successfully transmit these data packets to node 2?Here, we can formulate the research objective of this paper:To make the vehicle be able to adjust the scanning pattern of its directional antenna according to the topology around it and find out the optimal routing decisions to minimize the delay and the number of packet copies while successful packets delivery and short delay are guaranteed.


## 4. Neighbor Discovery

In this section, we devise a novel neighbor discovery algorithm with directional antennas which can make the nodes respond quickly to the topology changes. A priori knowledge is unnecessary when the nodes begin to detect their neighbor nodes.To clearly demonstrate the protocol we devised, we assume that nodej is within the cover range of nodei and nodek is within the cover range of nodej while out of the cover range of nodei.


### 4.1. Neighbor Node List

Neighbor node list is the fundamental part of our approach; sector distribution and routing decision are both based upon the information from the neighbor node list.In our approach, nodes arrange their sectors according to the information in the neighbor node list. The neighbor node list of each node is built up and updated based on the interactive messages that it receives each time. The structure of the interactive message is shown in Figure3:(1)
ID: the ID of nodei;(2)
Type: to indicate that the message is either a HELLO message or a response message;(3)
Sector_S: to record the sector that the antenna of node i points to when node i broadcasts this message; it is denoted by Si (Si∈S^i);(4)
TNS (time to next sector): to set the timerCSi when it broadcasts this message.Figure 3
Structure of interactive message.TheNeighbor List records all the neighbor nodes that nodei has ever detected:(1)
Neighbor ID: to indicate the ID of the neighbor node, such as the ID of nodej;(2)
DES_N (duration for every sector of the neighbor node): to record all the sectors where nodei has ever detected nodej; the total number of messages received from nodej is denoted by AijS^i;(3)
Sector_N (sector of the neighbor node for the last communication): to record the sector that the directional antenna of nodeipoints to when nodei detected nodej last time, which is denoted by Sij.Every node maintains a neighbor node list. The format of each item in the neighbor node list is shown in Figure4. TheNeighbor-Information Areaof nodei records the information about nodej. TheTwo-Hop Node List records all the information of the neighbor nodes that nodej has ever detected, such as the information about nodek. Their formats are the same as the HELLO message and their descriptions are similar as well, except that theTime_Flag indicates the update time of this item, which is updated based on the timer kept in nodeisince nodes are not time synchronized. It is denoted by TFlagi.Figure 4
Neighbor node list.In order to improve the efficiency of neighbor discovery, nodes will send back a response message when they receive a HELLO message so that they can take every chance to make themselves discovered by others. However, collision issue is not concerned in this paper since nodes are not time synchronized like in [2–8]. We propose a mechanism to reduce the collision probability, which is that nodes are not forced to send back a response message every time when it receives a HELLO message. When a node, sayj, receives a HELLO message from another node, sayi, there are two steps to be taken:(1)
Nodejupdates its neighbor node list according to the HELLO message from nodei. TheNeighbor-Information Area is updated according to theSelf-Information Area of the HELLO message and theTwo-Hop Node List is updated according to theNeighbor List of the HELLO message.(2)
If nodei is listed in theneighbor node list of nodej and the information about itself is the latest,nodej does not respond to nodei.If not, nodej sends back a response packet to nodeiafter a random time period ε whether it is in the transmitting state or not. ε is supposed to be smaller than theTNS in the HELLO message from nodei in case that nodeiturns its directional antenna to the next sector and it cannot receive the response message from nodej.As HELLO messages and response messages being broadcasted in the network, nodes are able to collect plenty of information to arrange their directional antennas.


### 4.2. Sector Steering Schedule Arrangement

In this part, we present how nodes adjust the steering time of their sectors based upon the neighbor node list.As we mentioned in Section3, when the mobility model of the nodes in the network shows strong location and group preference, nodes can waste time on the sectors where few neighbor nodes exist if they switch their directional antennas randomly. To make the nodes sensitive to the topology around them and arrange their directional antennas intelligently, we propose an algorithm calledHistory-Based Sector Distribution (HSD). At the beginning ofHSD, nodei switches its directional antenna to sectors randomly and the timer CSi (Si∈S^i) is equal toTθi/2π. As the neighbor discovery proceeds, nodei will gather enough information to arrange its directional antennas and CSi (Si∈S^i) is going to be adjusted. According to theDES_N in the neighbor node list maintained in nodei, we can know which sectors communicate with other nodes frequently. They are the areas where groups of nodes may exist and are more likely for nodeito discover new neighbor nodes.Then, we can formulate theHSD as follows. When nodeipoints its directional antenna to Si, we can get that(1)RSi=∑k∈LiAikSi∑S∈S^i∑k∈LiAikS,where RSi represents the proportion of interactive messages received through Si compared to the total messages received through all sectors of nodeiand Li represents the set of neighbor nodes recorded in the neighbor node list of nodei. We define QSi≜∑k∈LiAikSi and Ei≜∑S∈S^i∑k∈LiAikS. The relationship between RSi and CSi is expressed as follows:(2)CSi=RSiT=QSiEiT.In the preliminary stage,QSi and Ei in (2) are both very small and the sector which is the first to discover neighbor nodes tends to have a bigger RSi since QSi and Ei can be all generated by this sector, in which case the node possibly points its antenna to this sector for an inappropriate CSi which is close to T. With the process of neighbor discovery, according to (1) and (2), CSi of each sector would be too stable to make a response to the topology changes. For example, CSi of the sectors where few neighbor nodes are discovered tend to be small or even close to zero. However, nodes can change their communities with a small probability as we mentioned in Section 3. Moreover, the relative positions among nodes can change dramatically sometime even if they walk in the same community, such as when nodes walk to an opposite direction. Therefore, neighbor nodes can appear in the sectors which used to be empty and the previous CSi of these sectors would be obsolete.To make (2) sensitive to the topology of the network, inHSD, we propose a mechanism to estimate the topology changes by monitoring the frequency of message receiving.Firstly, in a specific monitoring time period,Mi, then, we can get(3)VSi=QSiM,where VSi indicates the message receiving frequency of Si in the recent time period of Mi. Obviously, VSi is a stable value when the relative positions among the nodes are stable. In that case, the instant receiving frequency, V′Si, is stable as well and it holds that(4)V′Si=ΔQSiΔt≅VSi.According to (1) and (3), we notice that(5)VSiRSi=EiMi.Therefore,VSi/RSi is only determined by the status of nodeibut not the status of Si. Due to this, we define φi≜Ei/Mi which is the message receiving frequency of nodeiregardless of the status of its sectors.According to (4) and (5), when the topology in the network is stable, the following is established between every two sectors of nodei: (6)V′SimRSim≅V′SinRSin≅EiMSim,Sin∈S^i;m≠n.Therefore, we can compareV′Si among S^i to estimate the topology variation around node i based on (6). The functioning process of (6) is analyzed as follows.In the preliminary stage of the neighbor discovery process, according to (6), the adjustment of RSi would be started after the first monitoring time period. And nodei is supposed to scan more than two sectors during the first monitoring time period to apply (6). Hence, the initial CSi would be restricted within a reasonable range due to the comparison of CSi among sectors. After that, when the topology around the nodeichanges, there are two situations:(i)
The relative positions among nodes are changed while the neighbor nodes are still in the transmission range of nodei; that is, the number of neighbor nodes within the transmission range of nodei remains the same;(ii)
Some neighbor nodes are no longer in the transmission range of nodei or new neighbor nodes come into the transmission range; that is, the number of neighbor nodes within the transmission range of nodei is changed.The simulation result of [1] shows that in some cases nodes cannot discover each other even though they are within the transmission range of each other due to the equipment of directional antenna, while, in general, more neighbor nodes within the transmission range of nodei can lead to more frequent communications. Thus, we assume that φi is only determined by the number of nodes within the transmission range of nodei.For the first situation, for example, some nodes move from sectorSim to sector Sin. Obviously, V′Sim will decrease while V′Sin will increase. Then we can readjust RSim and RSin according to (6) since φi is stable.For the second situation,φi is going to change as well, and we need to rewrite (6) to the following form:(7)RSi≅V′Siφi.When the second situation happens, to clearly figure out the variation ofRSi, we separately analyze the variation of V′Si and φi as follows:(8)ΔV′Si=ΔQSiΔt-V′Sibefore,Δφi=Ei+ΔEiM+Δt-φibefore;then,(9)ΔV′Si-Δφi=ΔQSiΔt-Ei+ΔEiM+Δt+φibefore-V′Sibefore.Simplifying (9) and letting(10)ΔQSi-ΔEiM⟶0,ΔtM⟶0yield(11)ΔV′Si-Δφi≅V′Si-V′Sibefore.According to (11), when new neighbor nodes come into the transmission range of nodeisuch as appearing in sector Si, it is obvious that V′Si would be bigger than V′Sibefore so that ΔV′Si>Δφi. According to (7), RSi would increase. Contrarily, when nodes flee from Si, V′Si would be smaller than V′Sibefore so that RSi would decrease. By far we can conclude that (6) works well for dynamic topology.


## 4.1. Neighbor Node List

Neighbor node list is the fundamental part of our approach; sector distribution and routing decision are both based upon the information from the neighbor node list.In our approach, nodes arrange their sectors according to the information in the neighbor node list. The neighbor node list of each node is built up and updated based on the interactive messages that it receives each time. The structure of the interactive message is shown in Figure3:(1)
ID: the ID of nodei;(2)
Type: to indicate that the message is either a HELLO message or a response message;(3)
Sector_S: to record the sector that the antenna of node i points to when node i broadcasts this message; it is denoted by Si (Si∈S^i);(4)
TNS (time to next sector): to set the timerCSi when it broadcasts this message.Figure 3
Structure of interactive message.TheNeighbor List records all the neighbor nodes that nodei has ever detected:(1)
Neighbor ID: to indicate the ID of the neighbor node, such as the ID of nodej;(2)
DES_N (duration for every sector of the neighbor node): to record all the sectors where nodei has ever detected nodej; the total number of messages received from nodej is denoted by AijS^i;(3)
Sector_N (sector of the neighbor node for the last communication): to record the sector that the directional antenna of nodeipoints to when nodei detected nodej last time, which is denoted by Sij.Every node maintains a neighbor node list. The format of each item in the neighbor node list is shown in Figure4. TheNeighbor-Information Areaof nodei records the information about nodej. TheTwo-Hop Node List records all the information of the neighbor nodes that nodej has ever detected, such as the information about nodek. Their formats are the same as the HELLO message and their descriptions are similar as well, except that theTime_Flag indicates the update time of this item, which is updated based on the timer kept in nodeisince nodes are not time synchronized. It is denoted by TFlagi.Figure 4
Neighbor node list.In order to improve the efficiency of neighbor discovery, nodes will send back a response message when they receive a HELLO message so that they can take every chance to make themselves discovered by others. However, collision issue is not concerned in this paper since nodes are not time synchronized like in [2–8]. We propose a mechanism to reduce the collision probability, which is that nodes are not forced to send back a response message every time when it receives a HELLO message. When a node, sayj, receives a HELLO message from another node, sayi, there are two steps to be taken:(1)
Nodejupdates its neighbor node list according to the HELLO message from nodei. TheNeighbor-Information Area is updated according to theSelf-Information Area of the HELLO message and theTwo-Hop Node List is updated according to theNeighbor List of the HELLO message.(2)
If nodei is listed in theneighbor node list of nodej and the information about itself is the latest,nodej does not respond to nodei.If not, nodej sends back a response packet to nodeiafter a random time period ε whether it is in the transmitting state or not. ε is supposed to be smaller than theTNS in the HELLO message from nodei in case that nodeiturns its directional antenna to the next sector and it cannot receive the response message from nodej.As HELLO messages and response messages being broadcasted in the network, nodes are able to collect plenty of information to arrange their directional antennas.


## 4.2. Sector Steering Schedule Arrangement

In this part, we present how nodes adjust the steering time of their sectors based upon the neighbor node list.As we mentioned in Section3, when the mobility model of the nodes in the network shows strong location and group preference, nodes can waste time on the sectors where few neighbor nodes exist if they switch their directional antennas randomly. To make the nodes sensitive to the topology around them and arrange their directional antennas intelligently, we propose an algorithm calledHistory-Based Sector Distribution (HSD). At the beginning ofHSD, nodei switches its directional antenna to sectors randomly and the timer CSi (Si∈S^i) is equal toTθi/2π. As the neighbor discovery proceeds, nodei will gather enough information to arrange its directional antennas and CSi (Si∈S^i) is going to be adjusted. According to theDES_N in the neighbor node list maintained in nodei, we can know which sectors communicate with other nodes frequently. They are the areas where groups of nodes may exist and are more likely for nodeito discover new neighbor nodes.Then, we can formulate theHSD as follows. When nodeipoints its directional antenna to Si, we can get that(1)RSi=∑k∈LiAikSi∑S∈S^i∑k∈LiAikS,where RSi represents the proportion of interactive messages received through Si compared to the total messages received through all sectors of nodeiand Li represents the set of neighbor nodes recorded in the neighbor node list of nodei. We define QSi≜∑k∈LiAikSi and Ei≜∑S∈S^i∑k∈LiAikS. The relationship between RSi and CSi is expressed as follows:(2)CSi=RSiT=QSiEiT.In the preliminary stage,QSi and Ei in (2) are both very small and the sector which is the first to discover neighbor nodes tends to have a bigger RSi since QSi and Ei can be all generated by this sector, in which case the node possibly points its antenna to this sector for an inappropriate CSi which is close to T. With the process of neighbor discovery, according to (1) and (2), CSi of each sector would be too stable to make a response to the topology changes. For example, CSi of the sectors where few neighbor nodes are discovered tend to be small or even close to zero. However, nodes can change their communities with a small probability as we mentioned in Section 3. Moreover, the relative positions among nodes can change dramatically sometime even if they walk in the same community, such as when nodes walk to an opposite direction. Therefore, neighbor nodes can appear in the sectors which used to be empty and the previous CSi of these sectors would be obsolete.To make (2) sensitive to the topology of the network, inHSD, we propose a mechanism to estimate the topology changes by monitoring the frequency of message receiving.Firstly, in a specific monitoring time period,Mi, then, we can get(3)VSi=QSiM,where VSi indicates the message receiving frequency of Si in the recent time period of Mi. Obviously, VSi is a stable value when the relative positions among the nodes are stable. In that case, the instant receiving frequency, V′Si, is stable as well and it holds that(4)V′Si=ΔQSiΔt≅VSi.According to (1) and (3), we notice that(5)VSiRSi=EiMi.Therefore,VSi/RSi is only determined by the status of nodeibut not the status of Si. Due to this, we define φi≜Ei/Mi which is the message receiving frequency of nodeiregardless of the status of its sectors.According to (4) and (5), when the topology in the network is stable, the following is established between every two sectors of nodei: (6)V′SimRSim≅V′SinRSin≅EiMSim,Sin∈S^i;m≠n.Therefore, we can compareV′Si among S^i to estimate the topology variation around node i based on (6). The functioning process of (6) is analyzed as follows.In the preliminary stage of the neighbor discovery process, according to (6), the adjustment of RSi would be started after the first monitoring time period. And nodei is supposed to scan more than two sectors during the first monitoring time period to apply (6). Hence, the initial CSi would be restricted within a reasonable range due to the comparison of CSi among sectors. After that, when the topology around the nodeichanges, there are two situations:(i)
The relative positions among nodes are changed while the neighbor nodes are still in the transmission range of nodei; that is, the number of neighbor nodes within the transmission range of nodei remains the same;(ii)
Some neighbor nodes are no longer in the transmission range of nodei or new neighbor nodes come into the transmission range; that is, the number of neighbor nodes within the transmission range of nodei is changed.The simulation result of [1] shows that in some cases nodes cannot discover each other even though they are within the transmission range of each other due to the equipment of directional antenna, while, in general, more neighbor nodes within the transmission range of nodei can lead to more frequent communications. Thus, we assume that φi is only determined by the number of nodes within the transmission range of nodei.For the first situation, for example, some nodes move from sectorSim to sector Sin. Obviously, V′Sim will decrease while V′Sin will increase. Then we can readjust RSim and RSin according to (6) since φi is stable.For the second situation,φi is going to change as well, and we need to rewrite (6) to the following form:(7)RSi≅V′Siφi.When the second situation happens, to clearly figure out the variation ofRSi, we separately analyze the variation of V′Si and φi as follows:(8)ΔV′Si=ΔQSiΔt-V′Sibefore,Δφi=Ei+ΔEiM+Δt-φibefore;then,(9)ΔV′Si-Δφi=ΔQSiΔt-Ei+ΔEiM+Δt+φibefore-V′Sibefore.Simplifying (9) and letting(10)ΔQSi-ΔEiM⟶0,ΔtM⟶0yield(11)ΔV′Si-Δφi≅V′Si-V′Sibefore.According to (11), when new neighbor nodes come into the transmission range of nodeisuch as appearing in sector Si, it is obvious that V′Si would be bigger than V′Sibefore so that ΔV′Si>Δφi. According to (7), RSi would increase. Contrarily, when nodes flee from Si, V′Si would be smaller than V′Sibefore so that RSi would decrease. By far we can conclude that (6) works well for dynamic topology.


## 5. Routing Protocol

In the network where nodes are equipped with directional antennas, there is no consistent path from the source node to the destination node. In this section, we devise a special routing protocol calledHSD-R which is formulated based upon HSD. The routing decisions are made based on the knowledge maintained in the neighbor node list.


### 5.1. Neighbor Node Table Processing

We take Figure5 as an example to demonstrate how we analyze the neighbor node table when there are data packets waiting to be transmitted.Figure 5
Relay node selection.As illustrated in Figure5, when nodei plans to transmit its data packets to nodek, it can send its packets to nodesj1 andj3 immediately. But nodej3 is not qualified to be a relay node since nodekis beyond its transmission distance. However, for nodej1, we need to take a further consideration because the connecting time between it and nodei could be too short to finish a complete data transmission when they point their directional antennas to each other. Moreover, when data packets arrive at nodej1, the time consumption for nodej1 and nodek to point their directional antennas to a proper direction also needs to be considered since the data packets are conserved in nodej1 during that time and cannot be transmitted.In order to make an appropriate routing decision, we need to find out which nodes can relay the data packets to the destination successfully with a high probability. When nodei wants to communicate with nodej through sector Si, the communicating probability can be expressed as follows:(12)PijSi=AijSiM/n+1τRSi,where PijSi refers to the communication probability between nodei and nodejthrough Si. Furthermore, we need to make sure that Si is the best option for nodeito communicate with nodej. For example, in the most recent monitoring time period, nodei and nodejhave a frequent communication in Si but this kind of situation could be a result of that nodei and nodej just happen to detect each in the recentM while they seldom encountered with each other before. In other words, the neighbor relationship between nodei and nodej existing in Si is only during the most recent monitoring time period. For this kind of neighbor nodes, they are not good options for relaying data packets due to the weak neighbor relationship between them and the source node. Therefore, we introduce a coefficient, σij, which refers to the stability of neighborhood relationship between nodeiand nodej. It can be calculated as follows: (13)σij=∑S∈S^iAijSEi.Before analyzing the time metric of every possible path, we need to detail how the directional antennas operate during the data transmission. As we mentioned in Section3, nodes are supposed to switch their directional antennas in a predicable sequence in order to make the routing decisions more precise, while the source node can begin its data transmission at any time point and nodes are not time synchronized in this paper. Therefore, we propose a mechanism to make nodes to change their rotation pattern spontaneously. When there are data packets conserved in the nodes and waiting to be transmitted, data packets could be generated by the nodes themselves or received from other neighbors, these nodes switch their rotation mode toDT-M. Otherwise, they still keep their scan pattern asPTN-M. The broadcast of interactive messages is still going on whether the rotation mode isDT-M orPTN-M since the topology changes can also happen during the data transmissions.Considering that nodes make their routing decisions based on the status of nodes in two-hop distance, there are at least three sets of directional antennas participating in data transmission. According to the neighbor node list maintained in the source nodei, we can construct the relationships about sectors among the source node, the neighbor nodes, and the two-hop nodes. As illuminated in Figure 6, we can draw the position and length of the frame for Source Node i  according to theSector Distributionin neighbor node list; the position and length of the frames for Relay Node jand Two-Hop Node kare separately decided by theNeighbor-Information Areaand theTwo-Hop Node List. In Figure 6, the zero point of the time axis, T0, refers to the time point when the source node prepares to send its data packets. The green zone between pointA and pointBor between pointC and pointD refers to the time period when the directional antennas of two nodes cover each other; that is, the two nodes can communicate with each other during the green zone.Figure 6 (a)
Nodejshould wait for a period time until it can communicate with nodek (b)
Nodej relays packets to nodek immediatelyWhen the relay node receives data packets successfully, there are two possibilities:(1) the relay node waits for a period of time until it can communicate with nodek, such as shown in Figure 6(a); (2) the relay node sends them to nodek immediately, which means Sjk=Skj, as shown in Figure 6(b).Source node, like nodei, can send data packets at any time. In other words, the position of pointO can be anywhere within the duration of Sij, while, in general, it can be categorized into two cases: (1) it is ahead of the able-transmitting period, like pointO in Figure 6(a); (2) it is during the able-transmitting period, like point O′ in Figure 6(a) and pointO in Figure 6(b). If the node misses the two kinds of time positions, like point O′ in Figure 6(b), it has to wait for the next communicating sector and it can be considered as pointO again.From Figure6 we can see that, in order to figure out the relationship among the three sets of directional antennas, it is necessary to figure out the beginning time points, Tbeginmn(m,n∈i,j,k;m≠n), and the ending time points, Tendmn(m,n∈i,j,k;m≠n), for these sectors:(1)Sji:(14)Tendji=TFlagj+CSjiTbeginji=Tendji-RSjiT.(2)Sjk:(15)Tendjk=Tendji,Sji=SjkTendji+∑m=1+SjiSjkRmT,Sji≠SjkTbeginjk=Tendjk-RSjkT.(3)Skj: (16)Tendkj=TFlangk+CSjkTbeginkj=Tendkj-RSkjT.Then we present an algorithm to predict the waiting and transmitting time for every possible path.After the waiting time and able-transmitting time of each path are calculated according to Algorithm1, the source node is able to make its routing decisions.Algorithm 1:Calculation for the waiting and transmitting time.
Input:  TO, Tbeginij, Tendij, TFlagj, TFlagk Output:  Twaitingh, Ttrans1h, Ttrans2h for  every row of the neighbor node table  do Calculate the beginning and ending time points for Sji,Sjk (Eq. (14)-(15)). for  every row of the Two-hop Node List  do Calculate the beginning and ending time points for Skj (Eq. (16)). if  Sji=Sjk, Tendij>Tbeginkj  then if  TO<max⁡Tbeginij,Tbeginji,Tbeginkj  then Set Twaitingh=max⁡Tbeginij,Tbeginji,Tbeginkj-TO Set Ttrans1h=Ttrans2h=min⁡Tendij,Tendji,Tendkj-max⁡Tbeginij,Tbeginji,Tbeginkj else then Set Twaitingh=0 Set Ttrans1h=Ttrans2h=min⁡Tendij,Tendji,Tendkj-TO end if else then Identify T′waitingh as the waiting time for the first hop of path h Identify T′′waitingh as the waiting time for the second hop of path h if  TO<max⁡Tbeginij,Tbeginji  then T ′ waiting h = max ⁡ T begin i j , T begin j i - T O Set Ttrans1h=min⁡Tendij,Tendji-max⁡Tbeginij,Tbeginji else then T ′ waiting h = 0 Set Ttrans1h=min⁡Tendij,Tendji-TO end if Set T′′waitingh=max⁡Tbeginjk,Tbeginkj-min⁡Tendij,Tendji Set Twaitingh=T′waitingh+T′′waitingh Set Ttrans2h=min⁡Tendjk,Tendkj-max⁡Tbeginjk,Tbeginkj end if end for end for


### 5.2. Routing Decisions

When the source node, say nodei, wants to send its data packets to the destination node, say nodek, we assume that the set of the neighbor nodes discovered by nodeiis denoted by Li and there are βm (m∈Li) two-hop nodes in theTwo-Hop Node Listof each neighbor node. Therefore, the number of potential two-hop paths for the nodei is ∑m∈Liβm. And there are four possibilities when nodei goes through its neighbor node table:(a)
Nodek is only recorded in theNeighbor-Information Area.(b)
Nodek is only recorded in theTwo-Hop Node List of some neighbor nodes.(c)
Nodek is recorded not only in theNeighbor-Information Area but also in theTwo-Hop Node Lists. In other words, nodei can send its data packets to nodek directly or via the relay nodes.(d)
There is no record for nodek in the neighbor node list.For the first three possibilities, every possible path should be taken into a further consideration because direct paths may have less connecting time or lower connecting ratio. The set of paths that can reach the destination node is denoted byU~.From Algorithm1 we can see that the time consumption for a complete transmission only consists of the able-transmitting time and the waiting time. For a specific path from the source node to the destination node, obliviously, the decisive part for a successful delivery is the weakest link among the paths, which refers to the most unstable neighbor relationship between two nodes. The calculation results of Algorithm 1 are theoretical time based upon the most recently updated history records. To make it more suitable for a general situation, we propose an inequation to filter every path in U~:(17)min⁡PijSijTtrans1h,PjkSjkTtrans2h>H,where PijSijTtrans1h and PjkTtrans2h indicate the predicted time period for delivery of each hop andH indicates the sum of transmission delay and propagation delay for one hop. In this paper, the propagation delay between the nodes is assumed to be small and the size of data packets is the same; therefore, we hypothesize thatHis the same for every node. Equation (17) indicates that the minimum of the able-transmitting time period of an ideal path should be enough to complete one packet transmission.In order to reduce the load of the network, we set a TTL,Ŧ, for every data packet. Based upon the previous discussion, we can conclude that the TTL for the data packets in a specific path should be the sum ofH and the waiting time in the path. To be more tolerant of the complex environment condition, we set Ŧ as follows:(18)Ŧ=maxm∈U~⁡Twaitingm+H.Algorithm2 details the procedure for the path selection. The set of qualified paths is denoted by V~.Algorithm 2:Path selection.
Input: U ~, Sij, k Output:  V~ for  every path u~∈U~  do Identify Sector_S in u~  as Ss Identify ωh=min⁡PijSijTtrans1h,PjkSjkTtrans2h if  Si=Ss  and  ωu~>H  then V ~ ← V ~ + { u ~ } end if end for if  V~  is null  then The source node holds its data packets and continue the neighbor discovery process until it finds qualified paths. end if Sort  V~  in descending order according to σijσjkωhAfter the path selection process, the source node generatesv copies of its data packets and transmits them through the firstvpaths in V~. v is a preset constant number which is detailed in Section 6.Then, we discuss the fourth situation that there is no record for nodek in the neighbor node list. Apparently, a node that has encountered more neighbor nodes may get more topology information in its two-hop distance. Hence, when this kind of extreme situation occurs, nodei sends its data packets to all the neighbor nodes who have discovered more neighbor nodes than nodeidose; that is, nodei sends its data packets to nodej if βj is bigger than the size of Li. If there is still no qualified neighbor node after that, then we choose those nodes who have encountered different neighbor nodes compared to Li. Algorithm 3 describes this procedure. The size of Li is denoted byx, and the set of qualified neighbor nodes is denoted by N~.Algorithm 3:Extreme situation treatment.
Input:  x Output:  N~ for  every neighbor node j∈Li  do if  βj>x  then N ~ ← N ~ + { j } end if end for if  N~  is null  then for  every neighbor node j∈Li  do if  jhas different neighbor nodes compared to Li  then N ~ ← N ~ + { j } end if end for end if


## 5.1. Neighbor Node Table Processing

We take Figure5 as an example to demonstrate how we analyze the neighbor node table when there are data packets waiting to be transmitted.Figure 5
Relay node selection.As illustrated in Figure5, when nodei plans to transmit its data packets to nodek, it can send its packets to nodesj1 andj3 immediately. But nodej3 is not qualified to be a relay node since nodekis beyond its transmission distance. However, for nodej1, we need to take a further consideration because the connecting time between it and nodei could be too short to finish a complete data transmission when they point their directional antennas to each other. Moreover, when data packets arrive at nodej1, the time consumption for nodej1 and nodek to point their directional antennas to a proper direction also needs to be considered since the data packets are conserved in nodej1 during that time and cannot be transmitted.In order to make an appropriate routing decision, we need to find out which nodes can relay the data packets to the destination successfully with a high probability. When nodei wants to communicate with nodej through sector Si, the communicating probability can be expressed as follows:(12)PijSi=AijSiM/n+1τRSi,where PijSi refers to the communication probability between nodei and nodejthrough Si. Furthermore, we need to make sure that Si is the best option for nodeito communicate with nodej. For example, in the most recent monitoring time period, nodei and nodejhave a frequent communication in Si but this kind of situation could be a result of that nodei and nodej just happen to detect each in the recentM while they seldom encountered with each other before. In other words, the neighbor relationship between nodei and nodej existing in Si is only during the most recent monitoring time period. For this kind of neighbor nodes, they are not good options for relaying data packets due to the weak neighbor relationship between them and the source node. Therefore, we introduce a coefficient, σij, which refers to the stability of neighborhood relationship between nodeiand nodej. It can be calculated as follows: (13)σij=∑S∈S^iAijSEi.Before analyzing the time metric of every possible path, we need to detail how the directional antennas operate during the data transmission. As we mentioned in Section3, nodes are supposed to switch their directional antennas in a predicable sequence in order to make the routing decisions more precise, while the source node can begin its data transmission at any time point and nodes are not time synchronized in this paper. Therefore, we propose a mechanism to make nodes to change their rotation pattern spontaneously. When there are data packets conserved in the nodes and waiting to be transmitted, data packets could be generated by the nodes themselves or received from other neighbors, these nodes switch their rotation mode toDT-M. Otherwise, they still keep their scan pattern asPTN-M. The broadcast of interactive messages is still going on whether the rotation mode isDT-M orPTN-M since the topology changes can also happen during the data transmissions.Considering that nodes make their routing decisions based on the status of nodes in two-hop distance, there are at least three sets of directional antennas participating in data transmission. According to the neighbor node list maintained in the source nodei, we can construct the relationships about sectors among the source node, the neighbor nodes, and the two-hop nodes. As illuminated in Figure 6, we can draw the position and length of the frame for Source Node i  according to theSector Distributionin neighbor node list; the position and length of the frames for Relay Node jand Two-Hop Node kare separately decided by theNeighbor-Information Areaand theTwo-Hop Node List. In Figure 6, the zero point of the time axis, T0, refers to the time point when the source node prepares to send its data packets. The green zone between pointA and pointBor between pointC and pointD refers to the time period when the directional antennas of two nodes cover each other; that is, the two nodes can communicate with each other during the green zone.Figure 6 (a)
Nodejshould wait for a period time until it can communicate with nodek (b)
Nodej relays packets to nodek immediatelyWhen the relay node receives data packets successfully, there are two possibilities:(1) the relay node waits for a period of time until it can communicate with nodek, such as shown in Figure 6(a); (2) the relay node sends them to nodek immediately, which means Sjk=Skj, as shown in Figure 6(b).Source node, like nodei, can send data packets at any time. In other words, the position of pointO can be anywhere within the duration of Sij, while, in general, it can be categorized into two cases: (1) it is ahead of the able-transmitting period, like pointO in Figure 6(a); (2) it is during the able-transmitting period, like point O′ in Figure 6(a) and pointO in Figure 6(b). If the node misses the two kinds of time positions, like point O′ in Figure 6(b), it has to wait for the next communicating sector and it can be considered as pointO again.From Figure6 we can see that, in order to figure out the relationship among the three sets of directional antennas, it is necessary to figure out the beginning time points, Tbeginmn(m,n∈i,j,k;m≠n), and the ending time points, Tendmn(m,n∈i,j,k;m≠n), for these sectors:(1)Sji:(14)Tendji=TFlagj+CSjiTbeginji=Tendji-RSjiT.(2)Sjk:(15)Tendjk=Tendji,Sji=SjkTendji+∑m=1+SjiSjkRmT,Sji≠SjkTbeginjk=Tendjk-RSjkT.(3)Skj: (16)Tendkj=TFlangk+CSjkTbeginkj=Tendkj-RSkjT.Then we present an algorithm to predict the waiting and transmitting time for every possible path.After the waiting time and able-transmitting time of each path are calculated according to Algorithm1, the source node is able to make its routing decisions.Algorithm 1:Calculation for the waiting and transmitting time.
Input:  TO, Tbeginij, Tendij, TFlagj, TFlagk Output:  Twaitingh, Ttrans1h, Ttrans2h for  every row of the neighbor node table  do Calculate the beginning and ending time points for Sji,Sjk (Eq. (14)-(15)). for  every row of the Two-hop Node List  do Calculate the beginning and ending time points for Skj (Eq. (16)). if  Sji=Sjk, Tendij>Tbeginkj  then if  TO<max⁡Tbeginij,Tbeginji,Tbeginkj  then Set Twaitingh=max⁡Tbeginij,Tbeginji,Tbeginkj-TO Set Ttrans1h=Ttrans2h=min⁡Tendij,Tendji,Tendkj-max⁡Tbeginij,Tbeginji,Tbeginkj else then Set Twaitingh=0 Set Ttrans1h=Ttrans2h=min⁡Tendij,Tendji,Tendkj-TO end if else then Identify T′waitingh as the waiting time for the first hop of path h Identify T′′waitingh as the waiting time for the second hop of path h if  TO<max⁡Tbeginij,Tbeginji  then T ′ waiting h = max ⁡ T begin i j , T begin j i - T O Set Ttrans1h=min⁡Tendij,Tendji-max⁡Tbeginij,Tbeginji else then T ′ waiting h = 0 Set Ttrans1h=min⁡Tendij,Tendji-TO end if Set T′′waitingh=max⁡Tbeginjk,Tbeginkj-min⁡Tendij,Tendji Set Twaitingh=T′waitingh+T′′waitingh Set Ttrans2h=min⁡Tendjk,Tendkj-max⁡Tbeginjk,Tbeginkj end if end for end for


## 5.2. Routing Decisions

When the source node, say nodei, wants to send its data packets to the destination node, say nodek, we assume that the set of the neighbor nodes discovered by nodeiis denoted by Li and there are βm (m∈Li) two-hop nodes in theTwo-Hop Node Listof each neighbor node. Therefore, the number of potential two-hop paths for the nodei is ∑m∈Liβm. And there are four possibilities when nodei goes through its neighbor node table:(a)
Nodek is only recorded in theNeighbor-Information Area.(b)
Nodek is only recorded in theTwo-Hop Node List of some neighbor nodes.(c)
Nodek is recorded not only in theNeighbor-Information Area but also in theTwo-Hop Node Lists. In other words, nodei can send its data packets to nodek directly or via the relay nodes.(d)
There is no record for nodek in the neighbor node list.For the first three possibilities, every possible path should be taken into a further consideration because direct paths may have less connecting time or lower connecting ratio. The set of paths that can reach the destination node is denoted byU~.From Algorithm1 we can see that the time consumption for a complete transmission only consists of the able-transmitting time and the waiting time. For a specific path from the source node to the destination node, obliviously, the decisive part for a successful delivery is the weakest link among the paths, which refers to the most unstable neighbor relationship between two nodes. The calculation results of Algorithm 1 are theoretical time based upon the most recently updated history records. To make it more suitable for a general situation, we propose an inequation to filter every path in U~:(17)min⁡PijSijTtrans1h,PjkSjkTtrans2h>H,where PijSijTtrans1h and PjkTtrans2h indicate the predicted time period for delivery of each hop andH indicates the sum of transmission delay and propagation delay for one hop. In this paper, the propagation delay between the nodes is assumed to be small and the size of data packets is the same; therefore, we hypothesize thatHis the same for every node. Equation (17) indicates that the minimum of the able-transmitting time period of an ideal path should be enough to complete one packet transmission.In order to reduce the load of the network, we set a TTL,Ŧ, for every data packet. Based upon the previous discussion, we can conclude that the TTL for the data packets in a specific path should be the sum ofH and the waiting time in the path. To be more tolerant of the complex environment condition, we set Ŧ as follows:(18)Ŧ=maxm∈U~⁡Twaitingm+H.Algorithm2 details the procedure for the path selection. The set of qualified paths is denoted by V~.Algorithm 2:Path selection.
Input: U ~, Sij, k Output:  V~ for  every path u~∈U~  do Identify Sector_S in u~  as Ss Identify ωh=min⁡PijSijTtrans1h,PjkSjkTtrans2h if  Si=Ss  and  ωu~>H  then V ~ ← V ~ + { u ~ } end if end for if  V~  is null  then The source node holds its data packets and continue the neighbor discovery process until it finds qualified paths. end if Sort  V~  in descending order according to σijσjkωhAfter the path selection process, the source node generatesv copies of its data packets and transmits them through the firstvpaths in V~. v is a preset constant number which is detailed in Section 6.Then, we discuss the fourth situation that there is no record for nodek in the neighbor node list. Apparently, a node that has encountered more neighbor nodes may get more topology information in its two-hop distance. Hence, when this kind of extreme situation occurs, nodei sends its data packets to all the neighbor nodes who have discovered more neighbor nodes than nodeidose; that is, nodei sends its data packets to nodej if βj is bigger than the size of Li. If there is still no qualified neighbor node after that, then we choose those nodes who have encountered different neighbor nodes compared to Li. Algorithm 3 describes this procedure. The size of Li is denoted byx, and the set of qualified neighbor nodes is denoted by N~.Algorithm 3:Extreme situation treatment.
Input:  x Output:  N~ for  every neighbor node j∈Li  do if  βj>x  then N ~ ← N ~ + { j } end if end for if  N~  is null  then for  every neighbor node j∈Li  do if  jhas different neighbor nodes compared to Li  then N ~ ← N ~ + { j } end if end for end if


## 6. Simulation Results

In this section, we evaluate the performance ofHSD andHSD-R separately. We use a simulation setup that consists of a uniform distribution of nodes over a 2-dimensional plane of area 20 km × 20 km. The fixed transmission range is R=10 km and the angle of each directional antenna is π/3, that is, 6 sectors for each vehicle node. The rotation period of the directional antennas is T=180τ and the duration of each receiving state is n=9 which indicates that each node can broadcast HELLO messages 18 times in a circle totally. The monitoring time M=360τ. The moving speed of the vehicle nodes is 50 km/h which is nearly 15 meters every 180τ with a random direction.We vary the total number of nodes inside this area with 5, 10, and 50, and they represent three levels of node density which are extremely low, low, and high, respectively. We assume that the area of the community is 4 km × 4 km, and the number of nodes in one community is random which is from 2 to 5 andP=0.1. In the extremely low density scenario, we artificially divide the 5 nodes into two groups with 2 and 3 separately. We run the simulation 20 times and the simulation duration is 104τ. Nodes are randomly scattered inside the area every time. There is a chance that nodes cannot discover all other nodes because their directional antennas cannot cover the whole area.


### 6.1. Evaluation of HSD

Firstly, we compare and analyze the performance ofHSD and the random algorithm. When the nodes switch their sectors clockwise with an equal and fixed CSi, it turns out that their average time consumption is much larger thanHSD and the random algorithm. Therefore, we only concentrate on the simulation comparison ofHSD and the random algorithm. Figure 7 shows the performances of the two algorithms on every node to successfully discover a certain percentage of neighbor nodes inside the area.Figure 7
Simulation result comparison on different node densities.
(a)
Extremely low density of nodes (b)
Low density of nodes (c)
High density of nodesIn Figure7(c),HSD and the random algorithm show no obvious difference on time consumption when the discovered nodes are under 70% since, in the high density scenario, there are plenty of neighbor nodes in any sectors so that the scan pattern ofHSD is similar to the random algorithm. When the discovered nodes reach 70%, the performance ofHSD is worse. Because higher density of nodes leads to more frequent communication among nodes, the nodes especially which are located at the central part of the scenario can go through turbulence on the schedule of sectors. However, as shown in Figures 7(a) and 7(b), theHSD achieves better performance since the probability of communication is smaller and the change of topology is easier to be detected when the density of nodes is low. Especially in Figure 7(a), when nodes in one community have discovered a node in another community, they can point their directional antennas to the certain sector where another community locates for a long time since there are few interferences from other sectors. Hence, the average time consumption and the standard deviation of time consumption ofHSD are both smaller than those of the random algorithm. According to [20], the packet size has obvious influence on the performance of protocols. However, the interactive action among nodes is rare since the node density in this paper is quite low; for example, only one neighbor node exists within a sector for the low density scenario.In summary, simulation results demonstrate thatHSD achieves better performance than the random algorithm on neighbor discovery when nodes are sparsely scattered.


### 6.2. Evaluation ofHSD-R

From the simulation results ofHSD, we conclude thatHSD achieves better performance when nodes are sparsely scattered. Reference [16] proposes a routing protocol calledSpray and Focus. ThoughSpray and Focus is not designed for the networks where directional antennas are equipped, it is a classic routing protocols for opportunistic networks and the most important is that nodes in [16] show location and group preference as well. Therefore, we compare and analyze the performance ofHSD-R andSpray and Focus in low density scenario and high density scenario separately.Spray and Focus consists of two phases: in the first phase it distributes a fixed number of copies to the first few relays encountered, and in the second phase each relay can forward its copy to a potentially more appropriate relay, using a carefully designed utility-based scheme.According to [16], the number of packet copies equal to about 5–10% of the total nodes serves as a useful rule of thumb for good performance. Because nodes in [16] are not equipped with the directional antennas, the connecting probability among nodes in our scenario is much lower than that in [16]. Under this consideration, we increase the number of packets copies, that is, the number of selected paths, v, gradually from approximately 5% to 20% of the total nodes to compare their performance. The beginning time of data transmission for every node is random and the destination for every source node is selected randomly as well.When the node density is low, only two paths can be selected fromV~ and around ten paths for high density scenario. As illuminated in Figure 8, the average able-transmitting time,Ttrans⁡h, among nodes in low density scenario is bigger since nodes mostly point their directional antennas to certain sectors where another community locates for a long time and there are few interferences from other sectors.Figure 8
Average able-transmitting time in low density scenario and high density scenario withv equal to 25% of the total nodes.Figure9 depicts the performance of the two protocols in low density scenario. Compared toSpray and Focus, the transmission delay ofHSD-R is much lower and it shows no obvious differences for every node. Figure 9 indicates that the selected paths inHSD-R do reduce the delay. The successful transmission rates of the two protocols in low density scenario are all above 90%.Figure 9
Average delay in low density scenario.When the node density gets higher, in Figure10, we can see an obvious decrease on Ttrans⁡h when the number of copies is bigger than 6, that is, around 10% of the total nodes. It indicates that the average able-transmitting time of the first 6 paths is much bigger than the left paths. Figure 11 proves that the minimum number of copies forHSD-R to achieve a reasonable success rate and delay is around 10% as well. Moreover, we can see that the success rate ofSpray and Focus decreases dramatically when the number of copies is small while the transmission delay ofHSD-R is slightly changed. And the minimum of number copies forHSD-Rto achieve a reasonable performance is smaller thanSpray and Focus.What needs to be explained is that the obvious success rate difference betweenHSD-R andSpray and Focus is caused by small number of total nodes in the scenario, and few data packets failing to be delivered to the destination can lead to a great decrease in success rate. We do not have the simulation on extremely high density scenarios because the directional antenna is not designed for that kind of scenarios.Figure 10
Average able-transmitting time in high density scenario with differentv.Figure 11
Success rate and average delay in high density scenario with differentv.In summary, compared toSpray and Focus,HSD-R can guarantee a successful delivery with a smaller number of packet copies while directional antennas are equipped.


## 6.1. Evaluation of HSD

Firstly, we compare and analyze the performance ofHSD and the random algorithm. When the nodes switch their sectors clockwise with an equal and fixed CSi, it turns out that their average time consumption is much larger thanHSD and the random algorithm. Therefore, we only concentrate on the simulation comparison ofHSD and the random algorithm. Figure 7 shows the performances of the two algorithms on every node to successfully discover a certain percentage of neighbor nodes inside the area.Figure 7
Simulation result comparison on different node densities.
(a)
Extremely low density of nodes (b)
Low density of nodes (c)
High density of nodesIn Figure7(c),HSD and the random algorithm show no obvious difference on time consumption when the discovered nodes are under 70% since, in the high density scenario, there are plenty of neighbor nodes in any sectors so that the scan pattern ofHSD is similar to the random algorithm. When the discovered nodes reach 70%, the performance ofHSD is worse. Because higher density of nodes leads to more frequent communication among nodes, the nodes especially which are located at the central part of the scenario can go through turbulence on the schedule of sectors. However, as shown in Figures 7(a) and 7(b), theHSD achieves better performance since the probability of communication is smaller and the change of topology is easier to be detected when the density of nodes is low. Especially in Figure 7(a), when nodes in one community have discovered a node in another community, they can point their directional antennas to the certain sector where another community locates for a long time since there are few interferences from other sectors. Hence, the average time consumption and the standard deviation of time consumption ofHSD are both smaller than those of the random algorithm. According to [20], the packet size has obvious influence on the performance of protocols. However, the interactive action among nodes is rare since the node density in this paper is quite low; for example, only one neighbor node exists within a sector for the low density scenario.In summary, simulation results demonstrate thatHSD achieves better performance than the random algorithm on neighbor discovery when nodes are sparsely scattered.


## 6.2. Evaluation ofHSD-R

From the simulation results ofHSD, we conclude thatHSD achieves better performance when nodes are sparsely scattered. Reference [16] proposes a routing protocol calledSpray and Focus. ThoughSpray and Focus is not designed for the networks where directional antennas are equipped, it is a classic routing protocols for opportunistic networks and the most important is that nodes in [16] show location and group preference as well. Therefore, we compare and analyze the performance ofHSD-R andSpray and Focus in low density scenario and high density scenario separately.Spray and Focus consists of two phases: in the first phase it distributes a fixed number of copies to the first few relays encountered, and in the second phase each relay can forward its copy to a potentially more appropriate relay, using a carefully designed utility-based scheme.According to [16], the number of packet copies equal to about 5–10% of the total nodes serves as a useful rule of thumb for good performance. Because nodes in [16] are not equipped with the directional antennas, the connecting probability among nodes in our scenario is much lower than that in [16]. Under this consideration, we increase the number of packets copies, that is, the number of selected paths, v, gradually from approximately 5% to 20% of the total nodes to compare their performance. The beginning time of data transmission for every node is random and the destination for every source node is selected randomly as well.When the node density is low, only two paths can be selected fromV~ and around ten paths for high density scenario. As illuminated in Figure 8, the average able-transmitting time,Ttrans⁡h, among nodes in low density scenario is bigger since nodes mostly point their directional antennas to certain sectors where another community locates for a long time and there are few interferences from other sectors.Figure 8
Average able-transmitting time in low density scenario and high density scenario withv equal to 25% of the total nodes.Figure9 depicts the performance of the two protocols in low density scenario. Compared toSpray and Focus, the transmission delay ofHSD-R is much lower and it shows no obvious differences for every node. Figure 9 indicates that the selected paths inHSD-R do reduce the delay. The successful transmission rates of the two protocols in low density scenario are all above 90%.Figure 9
Average delay in low density scenario.When the node density gets higher, in Figure10, we can see an obvious decrease on Ttrans⁡h when the number of copies is bigger than 6, that is, around 10% of the total nodes. It indicates that the average able-transmitting time of the first 6 paths is much bigger than the left paths. Figure 11 proves that the minimum number of copies forHSD-R to achieve a reasonable success rate and delay is around 10% as well. Moreover, we can see that the success rate ofSpray and Focus decreases dramatically when the number of copies is small while the transmission delay ofHSD-R is slightly changed. And the minimum of number copies forHSD-Rto achieve a reasonable performance is smaller thanSpray and Focus.What needs to be explained is that the obvious success rate difference betweenHSD-R andSpray and Focus is caused by small number of total nodes in the scenario, and few data packets failing to be delivered to the destination can lead to a great decrease in success rate. We do not have the simulation on extremely high density scenarios because the directional antenna is not designed for that kind of scenarios.Figure 10
Average able-transmitting time in high density scenario with differentv.Figure 11
Success rate and average delay in high density scenario with differentv.In summary, compared toSpray and Focus,HSD-R can guarantee a successful delivery with a smaller number of packet copies while directional antennas are equipped.


## 7. Conclusion

In this paper, we concentrate on the networking of vehicles. Firstly, we have proposed a novel neighbor discovery algorithm calledHistory-Based Sector Distribution (HSD) for vehicle ad hoc networks where directional antenna is equipped. The proposedHSD can make the vehicles be able to arrange their directional antennas according to the topology of the network. We have proved that our algorithm can achieve better performances than the traditional random algorithm especially in the scenario where vehicle nodes are sparsely scattered. Secondly, we design a routing protocol calledHSD-R which is derived fromHSD. InHSD-R, vehicle nodes make their routing decisions by analyzing the link quality of each possible path between the source node and the destination node based on the information collected during the neighbor discovery process. The evaluation results ofHSD-R prove that high successful transmission rate and low transmission delay are guaranteed with a small number of packet copies.



---

*Source: 7635143-2018-04-10.xml*