CN102065513B - Method for improving accuracy of AdHoc network neighbor node list - Google Patents

Abstract

The invention discloses a method for improving the accuracy of the adjacent node list of the AdHoc network, which mainly solves the problems of low accuracy of the adjacent node list and large overhead for sending HELLO message groups when the existing HELLO method is applied to the AdHoc network. The implementation steps include: initializing all nodes, recording the current neighbor node list, and then sending the HELLO message for the first time; each node records and compares the neighbor node list before sending for the nth time, and calculates the ratio of the number of new and old neighbor nodes, Adjust the sending interval of the HELLO message, and send the HELLO message according to the adjusted interval; the node receiving the HELLO message updates the neighbor node list according to the source of the HELLO message, and sets the timeout time and countdown timer; if a node counts down to 0 If the HELLO message of a neighbor node in the neighbor node list is still not received, the neighbor node information is deleted. Compared with the existing HELLO method, the present invention can further improve the accuracy of the adjacent node list, reduce network overhead, and has wide application range and strong portability.

Description

A Method of Improving the Accuracy of Neighbor List in AdHoc Network

technical field

The invention relates to the field of mobile wireless communication, in particular to a neighbor node list method of a node in an Ad Hoc network, which can be used for establishing and maintaining routes.

technical background

In the Ad Hoc network, the next hop selection of most routing protocols is based on the neighbor list, and the neighbor list is generally established and maintained by nodes periodically receiving and sending HELLO messages. However, due to the mobility of nodes, the information in the neighbor list often lags behind, which affects the performance of routing protocols. Therefore, improving the accuracy of the neighbor list is an important issue.

Factors affecting the accuracy of the neighbor list mainly include the sending interval/frequency of the HELLO message and the timeout time T _th of the neighbors in the neighbor list. In recent years, many scholars have done a lot of work on adjusting the sending interval/frequency of HELLO messages, which has improved the accuracy of the neighbor list to a certain extent.

J.Moy.OSPF-Open Shortest Path First, March 1994.RFC 158 proposed the most basic HELLO method is to use each node with a fixed frequency: f=1/d, d is the length of the sending interval of the HELLO message, periodicity broadcast HELLO message to the surrounding, when a _node receives a new neighbor node's HELLO message, it will update its neighbor node list according to the information in it; The node is removed from its neighbor list. Although this method is simple, it is not suitable for mobile networks because of the fixed f and T _th .

On the basis of the basic HELLO method, B.Karp and H.T.Kung, GPSR: Greedy Perimeter Stateless Routing for Wireless Networks, In Proc.of ACM/IEEE MOBICOM'00, Boston, Massachusetts, USA, 2000, pp.243-254 proposed A method to randomize the sending time of the HELLO message. Specifically: if in the basic HELLO method, the time when the node sends the HELLO message is B, then the time when the node sends the HELLO message in this method is a time randomly selected in the interval [B-0.5d, B+0.5d] . This method can effectively avoid the collision of HELLO messages, but it still cannot adjust the sending interval of HELLO messages in real time according to the mobile status of nodes.

Later Venkata C.Giruka, Mukesh Singhal, Hello Protocols for Ad-Hoc Networks: Overhead and Accuracy tradeoffs, In Proc.of the Sixth IEEE International Symposium on a World of Wireless Mobile and Multimedia Networks (WoWMoM'05) proposed an adaptive HELLO method, that is, a node sends a HELLO message every time it moves s meters. Therefore, when the node moves fast, the speed of sending HELLO messages is high; when the node moves slowly, the speed of sending HELLO messages is low. In order to control the speed of sending HELLO messages from being too high or too low, use MIN-BEACON-INTERVA and MAX-BEACON-INTERVAL as the minimum and maximum values of the sending interval. The HELLO message sent by each node includes the identification number ID, speed and direction information of the node. Taking nodes with IDs x and y as an example, when node x receives a HELLO message from y, using the speed and direction information in y's HELLO message, x will evaluate the time when node y can be removed from its neighbor list . The performance of the adaptive HELLO method depends on the moving distance s. If s is too small, the neighbor list will be accurate, but expensive. If s is large, the overhead is low, and the information of adjacent nodes lags behind. Depending on the value of s, a trade-off can be made between overhead and accuracy. The main advantage of this method is that the node's HELLO message can adapt to changes in node speed or mobility. Another advantage is intelligent neighbor node timeout evaluation. Nodes can evaluate whether a neighbor node times out based on speed and direction. However, this protocol only considers the speed of the local node and does not comprehensively consider the speed of the surrounding nodes, so the accuracy of the neighbor list is not greatly improved.

Therefore F.Ingelrest, N.Mitton, and D.Simplot-Ryl,, A Turnover based Adaptive HELLOProtocol for Mobile Ad Hoc and Sensor Networks, 15th International Symposium on Modeling, Analysis, and Simulation of Computer and Telecommunication Systems, mascots, 2007, .9-14. A method is proposed to adjust the frequency of HELLO message transmission based on the change of the number of neighbor nodes. Every time a node sends a HELLO message, it calculates the ratio r of the new node to the existing node in the neighbor list. If r is small, it means that the frequency f of the HELLO message is too high, and there is no such a big change in the neighbor nodes, so it should be reduced f; if r is large, it means that f is too low, and the changes in neighboring nodes are very fast, so f should be increased appropriately. Although this method is simple, considering the speed of the local node and the surrounding nodes, it can effectively improve the accuracy of the neighbor node list without additional equipment, but this method still has the following disadvantages:

1. In this method, nodes will send HELLO messages continuously, or never send HELLO messages, which does not conform to the actual network situation and will increase network overhead;

2. This method only starts from the aspect of adjusting the sending interval/frequency of node HELLO messages, which affects the improvement of the accuracy of the neighbor node list.

Contents of the invention

The purpose of the present invention is to overcome the shortcoming of above-mentioned existing method, propose a kind of method that improves the accuracy of Ad Hoc network neighbor list, to send HELLO message correctly, reduce network overhead, improve the accuracy of neighbor list.

To achieve the above object, technical solutions of the present invention include:

(1) The sending steps of the HELLO message:

1a) When each node in the network sends a HELLO message for the first time, it randomly selects a sending time t ₁ and a sending interval d, and each node records its own neighbor node list table ₁ at this time, and then sends a HELLO message, all nodes The sent HELLO message contains the information of the latest sending interval d of the sending node;

1b) When each node sends its own HELLO message for the nth time, record the adjacent node list table _n at this time t _n , according to the stored n-1th adjacent node list table _n-1 and nth adjacent node The list table _n distinguishes the new and old neighbor nodes, and calculates the ratio r of the number of new neighbor nodes to the number of old neighbor nodes;

Wherein t _n =t _n-1 +d, t _n-1 is the time when the node sends the HELLO message for the n-1th time, and d represents the HELLO message sending interval of the node;

对发送间隔进行调节，并利用调节后的发送间隔d′发送HELLO消息，再转入步骤1b)；1c) According to the ratio r of the number of new and old neighbor nodes, according to the formula

Adjust the sending interval, and use the adjusted sending interval d' to send the HELLO message, and then turn to step 1b);

Where d ₁ represents the initial adjustment value of the HELLO message sending interval, and its calculation formula is

${\mathrm{<span\; class="notranslate">\; d</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}<span\; class="notranslate">\; =</span>\left\{\begin{array}{cc}\mathrm{<span\; class="notranslate">\; d</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; g</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; r</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; \&times;</span>\mathrm{<span\; class="notranslate">\; d</span>}& \mathrm{<span\; class="notranslate">\; r</span>}<span\; class="notranslate">\; \&le;</span>{\mathrm{<span\; class="notranslate">\; r</span>}}_{\mathrm{<span\; class="notranslate">\; opt</span>}}\\ \mathrm{<span\; class="notranslate">\; d</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; g</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; r</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; \&times;</span>\mathrm{<span\; class="notranslate">\; d</span>}& \mathrm{<span\; class="notranslate">\; otherwise</span>}\end{array}\right.<span\; class="notranslate">\; ;</span>$

g(r) represents the adjustment strength of the HELLO message sending interval, and its calculation formula is

$\mathrm{<span\; class="notranslate">\; g</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; r</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; =</span>\left\{\begin{array}{cc}\frac{\mathrm{<span\; class="notranslate">\; 1</span>}}{\mathrm{<span\; class="notranslate">\; 5</span>}}{<span\; class="notranslate">\; (</span>\frac{{\mathrm{<span\; class="notranslate">\; r</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; r</span>}}_{\mathrm{<span\; class="notranslate">\; opt</span>}}}{{\mathrm{<span\; class="notranslate">\; r</span>}}_{\mathrm{<span\; class="notranslate">\; opt</span>}}}<span\; class="notranslate">\; )</span>}^{\mathrm{<span\; class="notranslate">\; 2</span>}}& \mathrm{<span\; class="notranslate">\; r</span>}<span\; class="notranslate">\; <</span>\mathrm{<span\; class="notranslate">\; 2</span>}<span\; class="notranslate">\; \&times;</span>{\mathrm{<span\; class="notranslate">\; r</span>}}_{\mathrm{<span\; class="notranslate">\; opt</span>}}\\ \frac{\mathrm{<span\; class="notranslate">\; 1</span>}}{\mathrm{<span\; class="notranslate">\; 5</span>}}& \mathrm{<span\; class="notranslate">\; otherwise</span>}\end{array}\right.<span\; class="notranslate">\; ;</span>$

r _opt represents the optimal value of r, when r is the optimal value, the sending interval does not need to be changed, that is, d'=d;

(2) Steps for receiving the HELLO message:

2a) If a node receives a HELLO message, determine the source of the HELLO message:

If the HELLO message received by the node is sent by a node that is not recorded in its neighbor list, then

Create the information of this node in the adjacent node list, set the timeout time T _th =λ*d of this adjacent node, and set the countdown timer value of this adjacent node as T _th , start counting down;

If the HELLO message that this node receives is sent by the node recorded in its neighbor list, then update the information of the corresponding node in the list, adjust the timeout period of the corresponding node in the neighbor list to be T _th =λ*d, and set The countdown timer value of the neighboring node is T _th , and the countdown starts;

2b) If a node has not received the HELLO message sent by the neighbor node when the countdown timer of a neighbor node in its neighbor node list counts down to 0, then delete the neighbor node information from its neighbor node list;

2c) If a node does not receive any HELLO message, then wait until receiving a HELLO message, judge the source of the HELLO message, and proceed to step 2a);

Where λ represents the number of lost HELLO messages that the network can tolerate, and the number is set according to specific network scenarios;

(3) Once any node receives the stop signal, it stops sending HELLO messages, receiving HELLO messages and deleting node information in the neighbor node list, and all the work of this node ends.

2. The method for improving the accuracy of Ad Hoc network neighbor list according to claim 1, wherein the format of the HELLO message described in step 1a) is improved on the basic HELLO message format, that is, the number of sending nodes has been increased. Send interval information.

The present invention has the following advantages:

(1) The present invention can comprehensively consider the speed/mobility of the surrounding nodes due to the simple local calculation, so no additional information such as the speed of the nodes is needed, and no additional equipment, such as GPS;

(2) The present invention can further improve the accuracy of the adjacent node list due to the adjustment of the sending interval and the overtime of the HELLO message, providing reliable guarantee for routing decisions;

(3) The present invention saves the sending of unnecessary HELLO messages owing to setting the upper and lower limits of the HELLO message sending interval, conforms to the actual operation situation, and saves bandwidth under the condition of not affecting the accuracy of the adjacent node list as far as possible, Reduced network overhead;

(4) The present invention can be used in any mobile wireless network that needs to use the HELLO method, and has a wide application range and strong portability.

Description of drawings

Fig. 1 is a flow chart of the present invention;

Fig. 2 is a schematic diagram of the HELLO message frame format of the present invention.

Fig. 3 is the new and old adjacent node discrimination schematic diagram of the present invention;

Detailed ways

The present invention mainly includes three parts: the receiving process, the sending process and the end operation of the HELLO message.

With reference to Fig. 1, concrete implementation steps of the present invention are as follows:

1. Sending of HELLO message

Step 1: When each node in the network sends a HELLO message for the first time, randomly select a sending time t ₁ and a sending interval d, each node records its own neighbor node list table ₁ at this time, and then sends a HELLO message.

As shown in Figure 2, the HELLO message frame format of the present invention is improved on the basis of the basic HELLO message frame format, that is, the latest sending interval information of the sending node is added in the basic HELLO message, and the sending interval information is used for Calculation of timeout T _th . In the HELLO message frame among Fig. 2, omitted content can be added or deleted according to specific routing protocol requirements, as when the present invention is used for the routing protocol in the vehicle-mounted Ad Hoc network VANET that needs position, velocity information, omitted part then is sending node position and velocity information.

Step 2: When each node sends its own HELLO message for the nth time, distinguish the new and old neighbor nodes, and calculate the ratio r.

2a) When each node sends its own HELLO message for the nth time, record the neighbor node list table _n at this time t _n , where t _n =t _n-1 +d, t _n-1 is the n-1th time of the node The time to send the HELLO message, d represents the sending interval of the node's HELLO message;

2b) Discriminate new and old neighbor nodes according to the latest two neighbor node lists stored, as shown in Figure 3, where table _n-1 represents the neighbor node stored by a node when sending the HELLO message for the n-1th time list, table _n indicates the neighbor node list stored by the node when sending the HELLO message for the nth time, and a node only stores two latest neighbor node lists. A new neighbor node refers to a node that does not exist in the table _n-1 but exists in the table _n , and an old neighbor node refers to a node that exists in the two tables;

2c) Calculate the ratio r of the number of new neighbor nodes to the number of old neighbor nodes, the ratio r is determined by the number of new neighbor nodes and the number of old neighbor nodes: when the number of new neighbor nodes is 0, regardless of the number of old neighbor nodes, r is 0; when the number of new neighbor nodes is not 0 and the number of old neighbor nodes is 0, r is ∞; in other cases, the value of r is the number of new neighbor nodes divided by the number of old neighbor nodes.

Step 3: Calculate the new HELLO message sending interval d′ according to the ratio r of the number of new and old neighbor nodes:

${\mathrm{<span\; class="notranslate">\; d</span>}}^{<span\; class="notranslate">\; \&prime;</span>}<span\; class="notranslate">\; =</span>\left\{\begin{array}{cc}{\mathrm{<span\; class="notranslate">\; d</span>}}_{\mathrm{<span\; class="notranslate">\; min</span>}}& {\mathrm{<span\; class="notranslate">\; d</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}<span\; class="notranslate">\; <</span>{\mathrm{<span\; class="notranslate">\; d</span>}}_{\mathrm{<span\; class="notranslate">\; min</span>}}\\ {\mathrm{<span\; class="notranslate">\; d</span>}}_{\mathrm{<span\; class="notranslate">\; max</span>}}& {\mathrm{<span\; class="notranslate">\; d</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}<span\; class="notranslate">\; ></span>{\mathrm{<span\; class="notranslate">\; d</span>}}_{\mathrm{<span\; class="notranslate">\; max</span>}}\\ {\mathrm{<span\; class="notranslate">\; d</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}& \mathrm{<span\; class="notranslate">\; otherwise</span>}\end{array}\right.$

Among them, d ₁ represents the initial adjustment value of the HELLO message sending interval, and its calculation formula is:

${\mathrm{<span\; class="notranslate">\; d</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}<span\; class="notranslate">\; =</span>\left\{\begin{array}{cc}\mathrm{<span\; class="notranslate">\; d</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; g</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; r</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; \&times;</span>\mathrm{<span\; class="notranslate">\; d</span>}& \mathrm{<span\; class="notranslate">\; r</span>}<span\; class="notranslate">\; \&le;</span>{\mathrm{<span\; class="notranslate">\; r</span>}}_{\mathrm{<span\; class="notranslate">\; opt</span>}}\\ \mathrm{<span\; class="notranslate">\; d</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; g</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; r</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; \&times;</span>\mathrm{<span\; class="notranslate">\; d</span>}& \mathrm{<span\; class="notranslate">\; otherwise</span>}\end{array}\right.$

g(r) represents the adjustment intensity of the HELLO message sending interval, which is determined by the degree to which the ratio r of the number of new and old neighbor nodes deviates from the optimal value r _opt of r, and its calculation formula is

$\mathrm{<span\; class="notranslate">\; g</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; r</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; =</span>\left\{\begin{array}{cc}\frac{\mathrm{<span\; class="notranslate">\; 1</span>}}{\mathrm{<span\; class="notranslate">\; 5</span>}}{<span\; class="notranslate">\; (</span>\frac{{\mathrm{<span\; class="notranslate">\; r</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; r</span>}}_{\mathrm{<span\; class="notranslate">\; opt</span>}}}{{\mathrm{<span\; class="notranslate">\; r</span>}}_{\mathrm{<span\; class="notranslate">\; opt</span>}}}<span\; class="notranslate">\; )</span>}^{\mathrm{<span\; class="notranslate">\; 2</span>}}& \mathrm{<span\; class="notranslate">\; r</span>}<span\; class="notranslate">\; <</span>\mathrm{<span\; class="notranslate">\; 2</span>}<span\; class="notranslate">\; \&times;</span>{\mathrm{<span\; class="notranslate">\; r</span>}}_{\mathrm{<span\; class="notranslate">\; opt</span>}}\\ \frac{\mathrm{<span\; class="notranslate">\; 1</span>}}{\mathrm{<span\; class="notranslate">\; 5</span>}}& \mathrm{<span\; class="notranslate">\; otherwise</span>}\end{array}\right.<span\; class="notranslate">\; ;</span>$

r _opt indicates the optimal value of r, when r is the optimal value, the sending interval does not need to be changed;

The initial adjustment value _d1 is determined according to the logical relationship between the ratio r of the number of new and old neighbor nodes and the sending interval, and the logical relationship is as follows:

When the ratio r of the number of new and old neighbors of a node is less than the optimal value _ropt of r, it means that the change of the neighbors around the node is slow, and the node does not need to send HELLO messages frequently, so the node should slow down the HELLO The sending of the message is to increase the initial adjustment value of the sending interval of the HELLO message;

When the ratio r of the number of new and old neighbors of a node is greater than the optimal value _ropt of r, it means that the surrounding neighbors of the node change rapidly, but the sending speed of the HELLO message of the node is too slow to keep up with the surrounding nodes. Neighboring node changes, so the sending of the HELLO message should be accelerated, that is, the initial adjustment value of the sending interval of the HELLO message should be reduced;

d _max indicates the upper limit of the sending interval of the HELLO message. This upper limit of the sending interval is set to prevent some nodes from sending the HELLO message for a long time or even never. When the initial adjustment value d ₁ of a node’s HELLO sending interval is greater than the sending interval When the upper limit d _max , adjust d'=d _max ;

d _min indicates the lower limit of the sending interval of HELLO messages. This lower limit of the sending interval is set to prevent some nodes from continuously sending HELLO messages and causing large network overhead. When the initial adjustment value d ₁ of a node’s HELLO message sending interval is less than When the lower limit of the sending interval is d _min , adjust d'=d _min .

As long as the above-mentioned logical relationship can be satisfied, the values of d _min , d _max and r _opt in the form of formulas d ₁ and g(r) can be set according to specific network scenarios, such as when the present invention is used for mobile nodes with a communication distance of 150m When in Ad Hoc network MANET, it can be set

${\mathrm{<span\; class="notranslate">\; d</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}<span\; class="notranslate">\; =</span>\left\{\begin{array}{cc}\mathrm{<span\; class="notranslate">\; d</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; g</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; r</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; \&times;</span>\mathrm{<span\; class="notranslate">\; d</span>}& \mathrm{<span\; class="notranslate">\; r</span>}<span\; class="notranslate">\; \&le;</span>{\mathrm{<span\; class="notranslate">\; r</span>}}_{\mathrm{<span\; class="notranslate">\; opt</span>}}\\ \mathrm{<span\; class="notranslate">\; d</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; g</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; r</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; \&times;</span>\mathrm{<span\; class="notranslate">\; d</span>}& \mathrm{<span\; class="notranslate">\; otherwise</span>}\end{array}\right.<span\; class="notranslate">\; ,</span>$ $\mathrm{<span\; class="notranslate">\; g</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; r</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; =</span>\left\{\begin{array}{cc}\frac{\mathrm{<span\; class="notranslate">\; 1</span>}}{\mathrm{<span\; class="notranslate">\; 5</span>}}{<span\; class="notranslate">\; (</span>\frac{{\mathrm{<span\; class="notranslate">\; r</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; r</span>}}_{\mathrm{<span\; class="notranslate">\; opt</span>}}}{{\mathrm{<span\; class="notranslate">\; r</span>}}_{\mathrm{<span\; class="notranslate">\; opt</span>}}}<span\; class="notranslate">\; )</span>}^{\mathrm{<span\; class="notranslate">\; 2</span>}}& \mathrm{<span\; class="notranslate">\; r</span>}<span\; class="notranslate">\; <</span>\mathrm{<span\; class="notranslate">\; 2</span>}<span\; class="notranslate">\; \&times;</span>{\mathrm{<span\; class="notranslate">\; r</span>}}_{\mathrm{<span\; class="notranslate">\; opt</span>}}\\ \frac{\mathrm{<span\; class="notranslate">\; 1</span>}}{\mathrm{<span\; class="notranslate">\; 5</span>}}& \mathrm{<span\; class="notranslate">\; otherwise</span>}\end{array}\right.<span\; class="notranslate">\; ,</span>$

r _opt =0.04, d _min =1 s, d _max =8 s.

Step 4: Use the new sending interval d' to send the HELLO message, and then go to step 2.

Second, the reception of HELLO message

Step 5: If a node receives a HELLO message, determine the source of the HELLO message:

If the HELLO message that this node receives is sent by the node that does not record in its adjacent node list, then the information of this node is newly created in the adjacent node list, the timeout time T _th =λ*d of setting this adjacent node, and set The countdown timer value of the neighboring node is T _th , and the countdown starts;

If the HELLO message that this node receives is sent by the node recorded in its neighbor list, then update the information of the corresponding node in the list, adjust the timeout period of the corresponding node in the neighbor list to be T _th =λ*d, and set The countdown timer value of the neighboring node is T _th , and the countdown starts;

Because the HELLO message transmission interval of each node is real-time change, therefore according to the time-out adjustment formula T _th =λ*d of the present invention, the time-out time of each adjacent node recorded in the adjacent node list of each node is to follow oneself The adaptive adjustment of the HELLO sending interval, this adaptive adjustment can better adapt to the mobility of nodes in the network, thereby improving the accuracy of the neighbor node list,

Among them, λ represents the number of lost HELLO messages that the network can tolerate, and the number is set according to specific network scenarios. When the present invention is used in the mobile Ad Hoc network MANET of 150m when the node communication distance, can set λ=2.

Step 6: If a node has not received a HELLO message from a neighbor node when the countdown timer of a neighbor node in its neighbor node list counts down to 0, delete the neighbor node information from its neighbor node list.

Step 7: If a node does not receive any HELLO message, wait until it receives a HELLO message, determine the source of the HELLO message, and turn to step 5.

3. End the operation

Step 8: Once any node receives the stop signal, it stops sending HELLO messages, receiving HELLO messages and deleting node information in the neighbor node list, and all the work of the node ends.

Claims (5)

1. A method for improving the accuracy of Ad Hoc network neighbor list, comprising: (1) Sending steps of HELLO message: 1a) When each node in the network sends a HELLO message for the first time, randomly select a sending time t1 and a sending interval d, each node records its own neighbor node list table ₁ at this time, and then sends a HELLO message, and all nodes send The HELLO message of each contains the information of the latest sending interval d of the sending node; 1b) When each node sends its own HELLO message for the nth time, record the adjacent node list table _n at this time t _n , according to the stored n-1th adjacent node list table _n-1 and nth adjacent node The list table _n distinguishes the new and old neighbor nodes, and calculates the ratio r of the number of new neighbor nodes to the number of old neighbor nodes; Wherein t _n =t _n-1 +d, t _n-1 is the time when the node sends the HELLO message for the n-1th time, and d represents the HELLO message sending interval of the node; 1c) According to the ratio r of the number of new and old neighbor nodes, according to the formula $d^{\&prime;}=\left\{\begin{array}{cc}{d}_{\min }& d_1<d_{\min }\\ d_{\max }& d_1>d_{\max }\\ d_1& \mathrm{otherwise}\end{array}\right.,$ The sending interval is adjusted, wherein, d _min represents the HELLO message sending interval lower limit, and d _max represents the HELLO message sending interval upper limit, and utilizes the adjusted sending interval d' to send the HELLO message, then proceeds to step 1b); Where d ₁ represents the initial adjustment value of the HELLO message sending interval, and its calculation formula is ${\mathrm{<span\; class="notranslate">\; d</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}<span\; class="notranslate">\; =</span>\left\{\begin{array}{cc}\mathrm{<span\; class="notranslate">\; d</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; g</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; r</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; \&times;</span>\mathrm{<span\; class="notranslate">\; d</span>}& \mathrm{<span\; class="notranslate">\; r</span>}<span\; class="notranslate">\; \&le;</span>{\mathrm{<span\; class="notranslate">\; r</span>}}_{\mathrm{<span\; class="notranslate">\; opt</span>}}\\ \mathrm{<span\; class="notranslate">\; d</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; g</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; r</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; \&times;</span>\mathrm{<span\; class="notranslate">\; d</span>}& \mathrm{<span\; class="notranslate">\; otherwise</span>}\end{array}\right.<span\; class="notranslate">\; ;</span>$ g(r) represents the adjustment strength of the HELLO message sending interval, and its calculation formula is $\mathrm{<span\; class="notranslate">\; g</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; r</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; =</span>\left\{\begin{array}{cc}\frac{\mathrm{<span\; class="notranslate">\; 1</span>}}{\mathrm{<span\; class="notranslate">\; 5</span>}}{<span\; class="notranslate">\; (</span>\frac{\mathrm{<span\; class="notranslate">\; r</span>}<span\; class="notranslate">\; -</span>{\mathrm{<span\; class="notranslate">\; r</span>}}_{\mathrm{<span\; class="notranslate">\; opt</span>}}}{{\mathrm{<span\; class="notranslate">\; r</span>}}_{\mathrm{<span\; class="notranslate">\; opt</span>}}}<span\; class="notranslate">\; )</span>}^{\mathrm{<span\; class="notranslate">\; 2</span>}}& \mathrm{<span\; class="notranslate">\; r</span>}<span\; class="notranslate">\; <</span>\mathrm{<span\; class="notranslate">\; 2</span>}<span\; class="notranslate">\; \&times;</span>{\mathrm{<span\; class="notranslate">\; r</span>}}_{\mathrm{<span\; class="notranslate">\; opt</span>}}\\ \frac{\mathrm{<span\; class="notranslate">\; 1</span>}}{\mathrm{<span\; class="notranslate">\; 5</span>}}& \mathrm{<span\; class="notranslate">\; otherwise</span>}\end{array}\right.<span\; class="notranslate">\; ;</span>$ r _opt represents the optimal value of r, when r is the optimal value, the sending interval does not need to be changed, that is, d'=d; (2) Steps for receiving the HELLO message: 2a) If a node receives a HELLO message, determine the source of the HELLO message: If the HELLO message that this node receives is sent by the node that does not record in its adjacent node list, then the information of this node is newly created in the adjacent node list, the timeout time T _th =λ*d of setting this adjacent node, and set The countdown timer value of the neighboring node is T _th , and the countdown starts; If the HELLO message that this node receives is sent by the node recorded in its neighbor list, then update the information of the corresponding node in the list, adjust the timeout period of the corresponding node in the neighbor list to be T _th =λ*d, and set The countdown timer value of the adjacent node is T _th , and the countdown starts; 2b) If a node has not received the HELLO message sent by the neighbor node when the countdown timer of a neighbor node in its neighbor node list counts down to 0, then delete the neighbor node information from its neighbor node list; 2c) If a node does not receive any HELLO message, then wait until receiving a HELLO message, judge the source of the HELLO message, and proceed to step 2a); Where λ represents the number of lost HELLO messages that the network can tolerate, and the number is set according to specific network scenarios; (3) Once any node receives the stop signal, it will stop sending HELLO messages, receiving HELLO messages and deleting node information in the neighbor node list, and all the work of this node will end. 2. the method for improving Ad Hoc network neighbor list accuracy according to claim 1, wherein the format of the HELLO message described in step 1a) is improved on basic HELLO message format, promptly increased the sending node Send interval information. 3. the method for improving Ad Hoc network neighbor list accuracy according to claim 1, wherein step 1b) described calculation new neighbor node number and the ratio r of old neighbor node number, is by new neighbor node number and old neighbor node number The number of neighbor nodes is determined: when the number of new neighbor nodes is 0, r is 0 regardless of the number of old neighbor nodes; when the number of new neighbor nodes is not 0 and the number of old neighbor nodes is 0, r is ∞; in other cases The value of r below is the number of new neighbors divided by the number of old neighbors. 4. The method for improving the accuracy of the Ad Hoc network neighbor list according to claim 1, wherein the HELLO message in the step 1c) sends interval initial value d ₁ , is according to the ratio r and the ratio r of the number of new and old neighbor nodes and sending The logical relationship between intervals is determined, and the logical relationship is as follows: When the ratio r of the number of new and old neighbors of a node is less than the optimal value _ropt of r, the sending of HELLO messages is slowed down, that is, the initial adjustment value of the sending interval of HELLO messages is increased; When the ratio r of the number of new and old neighbor nodes of a node is greater than the optimal value r _opt of r, the sending of HELLO messages is accelerated, that is, the initial adjustment value of the sending interval of HELLO messages is reduced; The specific form of the _d1 formula is configured according to different network scenarios. 5. the method for improving Ad Hoc network neighbor list accuracy according to claim 1, wherein step 1c) described HELLO message sends interval final adjustment formula d ', is to determine according to following logical relation: When the initial adjustment value d ₁ of a node's HELLO transmission interval is greater than the upper limit d _max of the transmission interval, adjust d'=d _max ; When the initial adjustment value d ₁ of a node's HELLO transmission interval is less than the lower limit of the transmission interval d _min , adjust d'=d _min ; When the initial adjustment value d ₁ of a node's HELLO sending interval is greater than the lower limit of the sending interval d _min and smaller than the upper limit of the sending interval d _max , adjust d'=d ₁ ; The specific values of the upper and lower limits are configured according to specific network scenarios.

Images