CN106792838A - DTN via node Candidate Set systems of selection - Google Patents

Abstract

The invention discloses a method for selecting a DTN relay node candidate set. The node scans to determine its neighbor node set; the node exchanges metadata with its neighbor nodes; the node determines whether to forward information to the neighbor node according to the exchanged information list, and if it needs to When the information reaches the neighbor node, the dynamic energy threshold is calculated; the node compares the remaining energy of the neighbor node with the calculated energy threshold, and if the remaining energy of the neighbor node is not less than the energy threshold, the neighbor node is used as a candidate set of relay nodes , if the remaining energy of a neighbor node is less than the energy threshold, the neighbor node is not selected as a relay node. Through the dynamic energy threshold strategy, the present invention eliminates the possibility of nodes with insufficient energy as relay nodes, more accurately determines the candidate set of relay nodes, and greatly reduces network overhead while ensuring the same network delivery rate and delay.

Description

Selection Method of DTN Relay Node Candidate Set

technical field

The invention relates to the technical field of wireless network communication, in particular to a method for selecting a DTN relay node candidate set in the time delay tolerant network (DTN) technology.

Background technique

DTN is mainly used in military, aviation, animal track research and other fields. There is no end-to-end path in DTN communication, the link is intermittent, the network topology changes all the time, and the nodes are mobile and the resources of the nodes are severely limited. Therefore, data communication in DTN has certain challenges. Studies have shown that more than 95% of the information in DTN communication needs to be forwarded by relay nodes to be finally transmitted to the destination node. The selection of relay nodes has always been the focus and difficulty of research.

In DTN, communication device nodes are affected by their own hardware, cost, volume, environment and other factors, and the energy of nodes is generally limited. In the process of communication, the energy of nodes will be consumed in the process of forwarding and receiving information and discovering neighbor nodes. If the remaining energy of nodes is insufficient, information cannot be transmitted; if there are a large number of nodes lacking energy, it will directly lead to The network is paralyzed, affecting normal communication. The energy of nodes is a factor that cannot be ignored in the process of DTN communication.

Contents of the invention

A DTN relay node candidate set selection method based on a dynamic energy threshold proposed by the present invention fully considers the energy consumption and remaining energy in the process of receiving and forwarding information by neighbor nodes, and provides a solution for selecting a better relay node , thereby reducing network overhead while maintaining the same delivery rate and delay.

In order to achieve the above object, a kind of DTN relay node candidate set selection method designed by the present invention comprises the following steps:

1) Node scanning determines its neighbor node set;

2) The node exchanges metadata with one of the neighbor nodes in the neighbor node set, and the metadata includes node ID, node remaining energy and node information list;

3) The node determines whether it needs to forward the information to the neighbor node according to the node information list in the neighbor node metadata, if it needs to forward the information to the neighbor node, go to step 4), otherwise, go to step 6);

4) The node calculates the energy consumed by the neighbor node to receive and forward the information according to the size of the information to be forwarded, and adds the energy consumed by the neighbor node to complete a scan to obtain an energy threshold;

5) The node compares the remaining energy of the neighbor node with the calculated energy threshold, if the remaining energy of the neighbor node is not less than the energy threshold, go to step 7), otherwise, go to step 6);

6) The neighbor node is not selected as a relay node;

7) Add the neighbor node to the candidate set of relay nodes.

Preferably, the formula for calculating the remaining energy of nodes in the metadata of step 2) is:

E _or (n')＝E _or (n'-1)-E _c (Δt)

Among them; E _or (n') represents the remaining energy of the node before the n'th forwarding, E _or (n'-1) represents the remaining energy value of the node before completing the n'-1th forwarding, E _c (Δt) is Node energy consumption value during the Δt interval, Δt is the time from the last forwarding, E _c (Δt) includes the energy consumed by the node to complete the n′-1 information forwarding and the energy consumed by the node scanning the neighbor nodes within Δt, n′ is A natural number representing a degree.

Preferably, the node in the step 3) compares its own information list with the node information list in the obtained neighbor node metadata, and judges whether the information in the node information list of the neighbor node contains the information in the self information list. For all the information included, if there is information contained in its own node information list but not included in the node information list of the neighbor node, it means that the node needs to forward the information to the neighbor node, and if it does not exist, it means that the information does not need to be forwarded to the neighbor node. neighbor nodes.

Preferably, the energy threshold in step 4) is a dynamic value. The calculation formula of energy threshold in described step 4) is:

δ _th = δ _{th_em} + b

Among them: δ _th is the minimum energy value required for neighbor nodes to assist in successfully submitting information, b is a fixed value, indicating the energy value that neighbor nodes need to consume to complete a scan, δ _{th_em} is the estimated received information based on the size of the forwarded information and The energy value that the node needs to consume to complete this forwarding, the calculation formula is:

δ _{th_em} = δ _r + δ _f = (k ₁ +k ₂ )P _min,size

Among them: k ₁ is a fixed value, expressing the energy consumed by the neighbor node forwarding unit information, k ₂ is a fixed value, expressing the energy consumed by the neighbor node receiving unit information, P _min,size indicates that there are , but the size of the minimum information in the information set that does not exist in the neighbor node information list.

Preferably, in the step 7), the neighbor node is selected as a candidate relay node, and whether to be selected as a relay node is determined according to a routing strategy, which is not within the scope of the present invention.

Principle of the present invention is as follows:

1. Node energy model

According to the DTN network communication principle, the DTN communication process mainly includes the discovery phase and the communication phase, as shown in Figure 1. The state of a node can be simply described as a search state (SS, Search State), a forwarding state (FS, ForwardState) and a receiving state (RS, Receive State). In the discovery phase, the node scans the surrounding neighbor nodes that can communicate, and the node status is SS. In the communication stage, information interaction is realized, including information forwarding and information receiving, and the transition states of nodes are FS and RS respectively. When the node scans the neighbor nodes, it enters the communication phase, and after completing the data communication, the node continues to enter the discovery phase.

In DTN communication, the energy of nodes will be consumed continuously, and it often occurs that nodes lose communication capabilities due to insufficient energy, reducing communication efficiency. According to the DTN communication process, the energy consumption of nodes mainly includes two aspects: data communication process consumption and search process consumption. The node energy consumption value E _c can be expressed by the following expression:

E _c =E _ss +E _fs +E _rs (1)

in, Indicates the energy consumption of the node search process, and the number of searches In direct proportion, T represents the time required to complete a search, t is the network running time, and b is a fixed value. E _fs =k ₁ P _f,size represents the energy consumed by the node forwarding information, which is proportional to the size of the forwarded data packet, k ₁ is a fixed value, representing the energy consumed by the node forwarding unit information, P _f,size represents the energy consumed by the node The size of forwarded information. E _rs =k ₂ P _r,size is the energy consumed by the node to receive information, k ₂ is a fixed value, indicating the energy consumed by the node to receive unit information, and P _r,size is the size of the information received by the node. Therefore, formula (1) can be rewritten as:

The energy source of the communication node is mainly composed of the initial power value and the collected energy value. On the basis of not considering the energy collection process, the energy source E of the node can be expressed as:

E＝E _init (3)

E _init represents the energy for node initialization.

2. Relay node candidate set selection

Before selecting a relay node, the node estimates the minimum energy required to receive information and complete a message forwarding. Among them, the minimum energy δ _r that needs to be consumed to receive information forwarded by other nodes can be expressed as:

δ _r = k ₂ P _{min, size} (4)

P _min,size indicates the size of the smallest information in the information set that exists in the node information list but does not exist in the neighbor node information list.

The minimum energy δ _f that needs to be consumed to complete the node’s information forwarding can be expressed as:

δ _f = k ₁ P _{min, size} (5)

Then the energy value δ _{th_em} required to receive node information and complete a forwarding is:

δ _{th_em} = δ _r + δ _f = (k ₁ +k ₂ )P _min,size (6)

The prerequisite for a node to be selected as a relay node is that the remaining energy of the node must be sufficient to complete a scan, information reception and forwarding, that is to say, the remaining energy of the node must not be less than the energy consumed by receiving information and completing an information forwarding and node scanning The energy consumed at one time is called the energy threshold δ _th . The information that a node needs to forward to neighbor nodes is different each time, so the energy threshold is a dynamic value.

The formula for calculating the energy threshold _δth is as follows:

δ _th = δ _{th_em} + b (7)

Therefore, when node A searches for a set of neighbor nodes {A ₁ ,A ₂ ,…,A _n }, the premise that a neighbor node can be selected as a central node is that the remaining energy E _or of the neighbor node must not be less than the node A forwarding The energy δ _th required to receive information, complete a scan, and forward information once is considered the minimum value of energy required when a neighboring node delivers to the destination node once. That is, the remaining energy E _or of the neighbor node needs to satisfy:

E _or ≥δ _th (8)

The remaining energy value of the node before the n'th forwarding:

E _or (n')=E _or (n'-1)-E _c (Δt) (9)

E _or (n′-1) indicates the remaining energy value of the node before completing the n′-1th forwarding, E _c (Δt) is the energy consumption value of the node within Δt time, specifically, it is calculated according to formula (2), Δt is the time from the last forwarding, including the energy consumed by the node to complete the n'-1 information forwarding and the energy consumed by the node scanning the neighbor nodes within Δt.

The advantages of the present invention are: firstly, the energy consumption of nodes in the search phase and the information communication phase in the DTN communication process is fully considered, and the energy consumption process is modeled; secondly, the energy consumption of the communication process with different information sizes is considered Moreover, before each node selects a relay node to forward information, it estimates the energy consumption sum of receiving information and completing one information forwarding this time, plus the energy consumption of the node completing a scan to obtain the energy threshold, and Compared with the remaining energy of neighboring nodes, the possibility of nodes with insufficient energy being used as relay nodes is eliminated, and the candidate set of relay nodes is more accurately determined; finally, the present invention is based on the remaining energy of nodes before path selection. The nodes have done preprocessing, which can greatly reduce the network overhead while achieving the same network delivery rate and delay, and at the same time improve the life cycle of the network.

Description of drawings

Figure 1 is a state diagram of a DTN node.

Figure 2 is a DTN network communication diagram.

FIG. 3 is a flowchart of an embodiment of a method for selecting a DTN relay node candidate set according to the present invention.

detailed description

In order to be more clear about the solution and realization effect of the present invention, the present invention will be further described in detail below in conjunction with the accompanying drawings and specific embodiments.

Figure 2 shows a part of the DTN network communication. The letters A, B, S, and C in the figure are node identifiers (node IDs). The solid circles represent communication nodes, and the circular dotted lines surrounding the nodes represent the communication of nodes. scope. As shown in Figure 2, node S scans neighbor node A, neighbor node B and neighbor node C at time _t1 .

As shown in Figure 3, a kind of DTN relay node candidate set selection method of the present invention comprises the following steps:

1) Node scan to determine its neighbor node set.

2) The node exchanges metadata with one of the neighbor nodes in the neighbor node set, and the metadata includes node ID, node remaining energy and node information list.

Node S first exchanges meta information with neighbor node A, including node ID, node information list, node remaining energy, etc. For example, the information list of node S is M _S ={m ₁ ,m ₃ ,m ₄ ,m ₅ ,m ₉ ,m ₁₀ ,m ₁₂ }, and the information list of neighbor node A is M _A ={m ₂ ,m ₃ , m ₅ ,m ₆ }, the remaining energy of neighbor node A is The unit is J.

3) The node determines whether it needs to forward the information to the neighbor node according to the node information list in the neighbor node metadata, if it needs to forward the information to the neighbor node, go to step 4), otherwise, go to step 6).

According to the exchanged meta-information, the node S can determine that the information in the existence information list M={m ₁ , m ₄ , m ₉ , m ₁₀ , m ₁₂ } exists in the node S, but does not exist in the neighbor node A. This means that the information or part of the information in M needs to be forwarded to the neighbor node A, that is, the node S needs to forward the information to the neighbor node A.

4) The node calculates the energy consumed by the neighbor node to receive and forward the information according to the size of the information to be forwarded, plus the energy consumed by the neighbor node to complete a scan to obtain the energy threshold.

According to the information in M, node S estimates the minimum energy δ _{th_em} needed to receive the information and complete the information forwarding once. The sum of δ _{th_em} and the energy consumed by neighbor node A to complete a scan is the energy threshold δ _th , and the unit is J . The information that a node needs to forward to neighbor nodes is different each time (the size and number of information will be different), so the energy threshold is a dynamic value. The calculation formula is:

δ _{th_em} = δ _r + δ _f = (k ₁ +k ₂ )P _min,size

δ _th = δ _{th_em} + b

Among them, P _{min, size} is equal to the minimum information size in M _A ={m ₂ ,m ₃ ,m ₅ ,m ₆ }, the unit is Byte, and k ₁ is a fixed value, indicating the energy consumed by nodes to forward unit byte information, The unit is J/Byte, k ₂ is a fixed value, indicating the energy consumed by the node to receive unit byte information, the unit is J/Byte, b indicates the energy required by the node to scan once, the unit is J/time, neighbor node A can assist The minimum energy δ _th required to successfully deliver information includes the energy consumed by neighbor node A receiving information, the energy consumed by neighbor node A scanning neighbor nodes, and the energy consumed by neighbor node A forwarding information to the destination node.

5) The node compares the remaining energy of the neighbor node with the calculated energy threshold, if the remaining energy of the neighbor node is not less than the energy threshold, go to step 7), otherwise, go to step 6).

Node S transfers the remaining energy of neighbor node A Compare with the calculated energy threshold _δth . if Explain that the remaining energy of neighbor node A is enough to receive the information forwarded by node S and complete a forwarding of the received information, neighbor node A can be selected as the relay node candidate set, go to step 7); if It means that the remaining energy of neighbor node A is insufficient, and this time it cannot serve as a relay node to assist in forwarding information, and go to step 6).

6) The neighbor node is not selected as a relay node.

7) Add the neighbor node to the candidate set of relay nodes.

After node S and node A complete information forwarding, they will continue to judge the next neighbor node according to the description scheme of step 2) to step 7) to determine whether the neighbor node can be used as a relay node candidate set.

A method for selecting a DTN relay node candidate set in the present invention is to select a suitable relay node candidate set according to the dynamic energy threshold before the relay node is determined in DTN communication. The energy consumed by scanning and one forwarding determines the relay candidate nodes. Since the size and number of information that a node needs to forward to neighbor nodes each time is different, the energy consumed to receive and forward these information is also different, so the energy threshold is a dynamic value. The neighbor nodes added to the relay node candidate set are selected as candidate relay nodes, and whether to be selected as relay nodes is determined according to the routing strategy, which is not within the description scope of the present invention. In DTN communication, the idea of estimating the energy consumed by receiving and forwarding the information based on the information that the node needs to forward, and determining the relay candidate node based on the estimated energy and the remaining energy of the neighbor nodes are in conflict with this scheme. .

The content not described in detail in this specification belongs to the prior art known to those skilled in the art.

Claims (5)

1. A DTN relay node candidate set selection method is characterized in that: the method comprises the following steps:

1) scanning the nodes to determine a neighbor node set of the nodes;

2) the node exchanges metadata with one neighbor node in the neighbor node set, wherein the metadata comprises a node ID, node residual energy and a node information list;

3) the node determines whether information needs to be forwarded to the neighbor node according to a node information list in the neighbor node metadata, if the information needs to be forwarded to the neighbor node, the step 4) is carried out, and if not, the step 6) is carried out;

4) the node calculates the energy consumed by the neighbor node for receiving and forwarding the information according to the size of the information to be forwarded, and obtains an energy threshold value by adding the energy consumed by the neighbor node for completing one-time scanning;

5) the node compares the residual energy of the neighbor node with the calculated energy threshold, if the residual energy of the neighbor node is not less than the energy threshold, the step 7) is carried out, otherwise, the step 6) is carried out;

6) the neighbor node is not selected as a relay node;

7) and adding the neighbor node into the candidate set of the relay node.

2. The DTN relay node candidate set selection method of claim 1, wherein: the calculation formula of the node residual energy in the metadata in the step 2) is as follows:

E_or(n′)＝E_or(n′-1)-E_c(Δt)

wherein; e_or(n ') represents the residual energy of the node before the nth' retransmission, E_or(n '-1) represents the residual energy value of the node before completing the (n' -1) th forwarding, E_c(Δ t) is the node energy consumption value during the interval Δ t, Δ t is the time since the last forwarding, E_c(delta t) comprises the energy consumed by the node for completing the (n '-1) th information forwarding and the energy consumed by the node scanning neighbor nodes in delta t, and n' is a natural number representing the times.

3. The DTN relay node candidate set selection method of claim 1, wherein: the node in the step 3) compares the own information list with the node information list in the acquired neighbor node metadata, and judges whether the information in the node information list of the neighbor node contains all information contained in the own information list, if the information contained in the own node information list but not contained in the node information list of the neighbor node exists, the node indicates that the node needs to forward the information to the neighbor node, and if the information does not exist, the node indicates that the node does not need to forward the information to the neighbor node.

4. The DTN relay node candidate set selection method of claim 1, wherein: the energy threshold in the step 4) is a dynamic value.

5. The DTN relay node candidate set selection method of claim 4, wherein: the calculation formula of the energy threshold is as follows:

_th＝_{th_em}+b

wherein:_ththe minimum energy value required for the neighbor node to assist in successfully submitting the information, b is a fixed value representing the energy value required by the neighbor node to complete one scanning,_{th_em}in order to estimate the received information according to the size of the forwarded information and complete the energy value consumed by the forwarding node, the calculation formula is as follows:

_{th_em}＝_r+_f＝(k₁+k₂)P_min,size

wherein: k is a radical of₁Is a fixed value and expresses the energy consumed by the neighbor node for forwarding unit information, k₂Is a fixed value and expresses the energy consumed by the neighbor node for receiving the unit information, P_min,sizeThe size of the minimum information in the information set which shows that the node exists in the node information list of the node, but does not exist in the neighbor node information list.