CN114302473A - Energy perception routing method for delay tolerant network - Google Patents

Abstract

The invention discloses an energy-aware routing method oriented to a delay tolerant network. First, data packets are prioritized, firstly, a source node generates data packets, and then the data packets are prioritized in a node internal storage area for data transmission. Secondly, before forwarding the message, the current node needs to find other neighbor nodes within the communicable range. If found, it will forward the data; when the two nodes enter the mutual communication range, they will forward their data packets respectively. The invention can effectively select the next hop node according to the energy relationship of the node, reduces the energy consumption of the node, reduces the network overhead, improves the transmission rate of the data packet, and has great significance for improving the characteristics of the DTN network.

Description

An energy-aware routing method for delay-tolerant networks

technical field

The invention relates to a delay-tolerant network-oriented energy-aware routing method, which belongs to the technical field of wireless communication networks.

Background technique

Delay Tolerant Network (DTN) is a mobile wireless network characterized by radio waves as the carrier, limited node capability, frequent node movement and harsh communication environment. Its earliest concept began with interstellar networks, in which nodes are usually deployed on different planets, and their basic purpose is to achieve message transmission between planets. However, due to the long distance between planets and the complex environment of the universe, the transmission delay of messages is large, and the connection between nodes is frequently interrupted. The existing end-to-end TCP/IP network architecture is not suitable for it. In such a network, there is no available end-to-end path between the source node and the destination node, and network interruptions frequently occur. The emergence of DTN can effectively solve these problems. At the same time, the nodes in the DTN are dynamic, and according to this mobility of the node, the message can be delivered to any other node within the communication range of the node for the opportunity of delivering messages between the source node and the destination node. Then the mobile node transmits the message to the destination through the mode of "carry-store-forward", which effectively solves the communication problem in the restricted network. With the development of related technologies, DTN is also applied in the fields of wildlife tracking, rural communication network, laser communication, post-disaster reconstruction network, etc.

Compared with traditional networks, DTN networks have very limited resources such as cache, bandwidth, and node processing capabilities. In order to improve the message delivery rate, DTN usually replicates multiple copies of messages and sends them through multiple paths. In this way, the reliability of message delivery is ensured, which will make the load pressure of nodes in the DTN network become very large. Traditional routing protocols cannot deliver messages in challenging environments, and delay-tolerant networks help overcome the difficulties of providing network access in challenging environments, requiring different routing protocols than traditional routing protocols.

The MaxProp protocol is one of the more classic routing methods in DTN. The routing algorithm is developed on the basis of the PROPHET protocol. It not only redefines the formula, but also uses some additional mechanisms to improve the probability of successful message transmission and reduce the transmission time. extension. Essentially, it is also a routing protocol based on probability statistics. The MaxProp protocol mainly estimates the transmission probability of each information according to the past encounters of the nodes, and then uses the transmission probability and hop number of the data packets to sort the data packets within the node, and then sorts the data packets that are most likely to reach the destination node. Priority forwarding. However, the MaxProp protocol does not consider the influence of node energy. For each mobile node, its energy resources are limited, and it needs to spend a lot of energy to send, receive, and process information. The exhaustion of node energy will cause it to fail to operate normally. message transmission, resulting in reduced network performance.

SUMMARY OF THE INVENTION

In view of some problems in the above technology and material selection in the prior art, the present invention provides an energy-aware routing method for a delay-tolerant network, which is of great significance for improving the characteristics of a DTN network.

The technical scheme of the present invention is: an energy-aware routing method oriented to a delay-tolerant network, comprising the following steps:

Step 1: Prioritize data packets. First, the source node generates data packets, and then the data packets are prioritized in the internal storage area of the node according to the rules in data transmission;

Step 2, neighbor discovery, before forwarding the message, the current node needs to discover other neighbor nodes within the communicable range, and if found, the data is forwarded; the communicable range is: for each node, there is its own communication range , the communication range is a circle with the node as the point and R as the radius. Nodes with a distance less than R from the center of the circle belong to its neighbor nodes and can communicate normally. R can be specifically set through simulation time.

Step 3, data forwarding, when the two nodes enter the mutual communication range, they forward their data packets respectively.

Further, in the step 3, prior to neighbor discovery and data forwarding, the nodes internally prioritize the data packets, and between nodes, an appropriate next hop is selected for forwarding according to energy perception. The specific content is: forward the data packet in the preceding steps to the neighbor node, when the energy of the current node is less than the energy of the neighbor node, forward the data packet to the next hop node according to the priority; when the energy of the current node is greater than that of the neighbor node When the energy is received, the forwarding will not be performed, and the current node will continue to generate or receive data packets, and then re-prioritize the data packets. Because in the process of receiving data packets, the current node will continue to consume energy, and then the current node and the current node will continue to consume energy. Neighbor nodes can make judgments and choose to forward packets until they are delivered to the destination node.

Further, the message buffering method in the node is as follows: the storage area is divided into left and right parts by the threshold value, and in the network, the packet forwarding hop count is relatively small and will be defined as a higher priority, that is, forwarding. Packets with a hop count less than the threshold will be defined as high priority. If the hop count of a data packet is less than the threshold value, its priority is greater than the data packet with the threshold value; for the case where the forwarding hop count of the data packet is less than the threshold value, the response data packets are arranged according to the hop count. If the hop count of the data packet is larger, the priority is lower; when the hop count of the data packet is greater than the threshold value, the route adopts an adaptive method to adjust the threshold value, and the formula is as follows:

where x is the average number of bytes transmitted when there is an opportunity to transmit a message, b is the size of the memory area, p is a fraction of the memory area size, and the threshold value t is equal to the size of the p-th byte contained in the message buffer area The number of hops that the corresponding data packet passes through; if x<b/2, the data packet that has been forwarded with a smaller number of hops will be defined with a higher priority; as x continues to increase, the threshold value t is mainly It is determined by the minimum value of x and b-x; when x is greater than p, the threshold value is defined as 0.

Further, when the hop count of the data packets is greater than the threshold value, the data packets are sorted according to the transmission probability. The larger the transmission probability value, the higher the priority; the transmission probability estimation is defined as follows:

其中i∈s，j≠i，初始的值为1/(|s|-1)，当节点i和节点j相遇的时候，

的值会自动加1，然后节点i中的所有有关联的概率值会进行再一次地归一化。每当节点相遇时，彼此会交换这些概率值；本地的节点在获得其他节点的概率估值之后会将其保存下来，进而能求出通过不同路径到目的节点d的传送成本c(i,i+1,…,d)，定义如公式(2)所示，为每条链路不发生概率估值的总和；Assuming that the set of network nodes is s, for any node i ∈ s, calculate the probability of encountering node j

where i∈s, j≠i, the initial value is 1/(|s|-1), when node i and node j meet,

The value of is automatically incremented by 1, and then all associated probability values in node i are normalized again. Whenever nodes meet, they exchange these probability values with each other; the local node saves the probability estimates of other nodes after obtaining them, and then can calculate the transmission cost c(i, i through different paths to the destination node d) +1,...,d), defined as shown in formula (2), is the sum of the probability estimates that each link does not occur;

Further, the selection of the next hop node is completed by judging the energy between nodes. The resources of each node of the _DTN are limited. Consumption energy E _r , scanning information energy E _s , the specific calculation methods are shown in formulas (3), (4), (5):

E _t =(P _e +P _a R ⁿ )T _t (3)

E _r =(P _e +P _p ) _Tr (4)

E _s =P _s T _s (5)

where P _e is the energy consumed per second by the transceiver, Pa is the energy consumed per second by the transmitter RF amplifier; _{P p is} the energy consumed for processing in the receiver, and P _s is the energy consumed by scanning to the radio environment Energy, P _s =P _e , these parameters are determined by the design characteristics of the transceiver; R is the transmission range, _n is the power index of the channel path loss; T _t is the time spent sending data, and Tr is the consumption of receiving data packets T _s is the time it takes to scan the message; assuming that the energy of the node in the network will not become zero, when the node receives the data packet, it compares its current energy level with the energy level of its neighbors to determine whether to forward it or not. The message is sent to its neighbor node. When the energy of the current node is less than that of the neighbor node, the data packet is forwarded to the next hop node according to the priority; Or accept the data packet, and then re-prioritize the data packet, because in the process of receiving the data packet, the current node will continue to consume energy, and then judge the energy of the current node and neighbor nodes to select and forward the data packet until delivery. to the destination node.

Further, in addition to sorting and forwarding the data packets inside the node, since the memory of the node is limited, the corresponding data packets need to be deleted in the cache space, and the data packets will not be transmitted again after deletion. Without reducing the packet delivery rate of the delay tolerant network, a node needs to complete one of the following three conditions to delete a packet: first, a copy of the packet has been delivered to the destination node; second, after the packet Within the timestamp range of , the remaining bandwidth between the current node and the destination node is less than the required bandwidth for data packet transmission to ensure that the data packet can be transmitted; third, if any copy of the current data packet is not transmitted to the destination node, However, after the current node deletes the corresponding data packet saved by it, the copy of the data packet existing in other nodes can still be transmitted to the destination node.

Compared with the prior art, the beneficial effects of the present invention are: the energy-aware MaxProp routing strategy EA-MaxProp proposed by the present invention can effectively select the next hop node according to the energy relationship of the nodes on the basis of MaxProp, reducing the number of nodes. Energy consumption, network overhead is reduced, and the transmission rate of data packets is improved, which is of great significance to improving the characteristics of DTN networks.

Description of drawings

FIG. 1 is a flow chart of the present invention.

FIG. 2 is a schematic diagram of a message caching mode of a node in the present invention.

Detailed ways

Embodiments of the present invention are described in detail below, examples of which are illustrated in the accompanying drawings, wherein the same or similar reference numerals refer to the same or similar elements or elements having the same or similar functions throughout. The embodiments described below with reference to the accompanying drawings are exemplary and are only used to explain the present invention, but not to be construed as a limitation of the present invention.

The energy-aware routing method for delay-tolerant networks proposed in this embodiment is an energy-aware MaxProp routing strategy EA-MaxProp (Energy Aware MaxProp) proposed for the problem that the MaxProp protocol does not consider node energy. DTN nodes replicate each message copy, which consumes a lot of energy to ensure transmission. The deployment of the energy-aware MaxProp routing strategy in the DTN network mainly includes three steps: packet prioritization, neighbor discovery, and data forwarding. As shown in Figure 1, the source node first generates the data packet, and then the data packet is stored in the internal storage area of the node. The priority of the node is sorted according to certain rules, and then the data packet is forwarded to the neighbor node. When the energy of the current node is less than that of the neighbor node, the data packet is forwarded to the next hop node according to the priority; when the energy of the current node is greater than that of the neighbor node When energy is used, no forwarding is performed, and the current node continues to generate or receive data packets, and then re-prioritizes the data packets. Because in the process of receiving data packets, the current node will continue to consume energy, and then the current node and neighbor nodes. The energy judges and chooses to forward the data packet until it is delivered to the destination node.

The neighbor discovery means that before forwarding a message, the current node needs to discover other neighbor nodes within a communication range, so that data can be forwarded.

The data forwarding refers to that when two nodes enter the communication range of each other, they forward their data packets respectively. Before neighbor discovery and data forwarding, data packets are prioritized within nodes, and between nodes, appropriate next hops are selected for forwarding based on energy perception. The message buffering method in the node is shown in Figure 2, and the storage area is divided into left and right parts by the threshold value. In the network, a packet with a smaller forwarding hop count is defined as a higher priority. If the hop count of a packet is less than the threshold, its priority will be higher than that of the packet greater than the threshold. When the hop count of the data packet is less than the threshold, the response data packets are mainly arranged according to the hop count. If the hop count of the data packet is larger, its priority will be lower; If it is greater than the threshold value, the route adopts an adaptive method to adjust the threshold value, as shown in the method formula (1).

where x is the average number of bytes transmitted when there is an opportunity to transmit a message, b is the size of the memory area, p is a fraction of the memory area size, and the threshold value t is equal to the size of the p-th byte contained in the message buffer area The number of hops that the corresponding data packet passes through. If x is much smaller than b, the data packets that have been forwarded with a smaller hop count will be defined with a higher priority; as x continues to increase, the threshold t is mainly determined by the minimum value of x and b-x; when When x is larger than p, the threshold value is unnecessary and can be defined as 0. For the case where the hop count of the data packets is greater than the threshold value in Figure 1, they are sorted according to the transmission probability according to the transmission. The larger the transmission probability value is, the higher the priority will be. The delivery probability estimate is defined as follows:

其中i∈s，j≠i，初始的值为1/(|s|-1)，当节点i和节点j相遇的时候，

的值会自动加1，然后节点i中的所有有关联的概率值会进行再一次地归一化。每当节点相遇时，他们会交换这些概率值。比如在只有六个节点的DTN网络中，节点i对其他的五个节点一开始的概率估值为

在和节点1首次相遇后，

的值变为了1.2，然后再将这写概率进行重新归一化后，得到新的概率：

本地的节点在获得其他节点的概率估值之后会将其保存下来，进而能求出通过不同路径到目的节点d的传送成本c(i,i+1,…,d)，定义如公式(2)所示，为每条链路不发生概率估值的总和。故在数据包跳数大于门限值的情况中，传送成本越小，其优先级越高。Assuming that the set of network nodes is s, for any node i ∈ s, the probability of encountering node j can be calculated

where i∈s, j≠i, the initial value is 1/(|s|-1), when node i and node j meet,

The value of is automatically incremented by 1, and then all associated probability values in node i are normalized again. Whenever nodes meet, they exchange these probability values. For example, in a DTN network with only six nodes, the initial probability of node i to the other five nodes is estimated as

After encountering node 1 for the first time,

The value of is changed to 1.2, and then the written probability is renormalized to obtain a new probability:

The local node will save the probability estimates of other nodes after obtaining them, and then can calculate the transmission cost c(i,i+1,...,d) through different paths to the destination node d, which is defined as formula (2) ), which is the sum of the probability estimates of the probability that each link will not occur. Therefore, in the case where the hop count of the data packet is greater than the threshold value, the lower the transmission cost, the higher the priority.

The next hop node selection problem is completed by judging the energy between nodes. The resources of each node of DTN are limited. In order to ensure the transmission of information, a large amount of energy needs to be consumed. It mainly includes sending energy consumption E _t , receiving energy consumption _Er , and scanning information energy _Es , and the specific calculation methods are shown in formulas (3), (4), and (5). where _Pe is the transceiver per second

E _t =(P _e +P _a R ⁿ )T _t (3)

E _r =(P _e +P _p ) _Tr (4)

E _s =P _s T _s (5)

Consumed energy, Pa is the energy consumed per second by the transmitter RF amplifier; _{P p is} the energy consumed for processing in the receiver, P _s is the energy consumed by scanning to the radio environment, P _s =P _e , these The parameters are determined by the design characteristics of the transceiver. R is the transmission range and n is the power index of the channel path loss. T _t is the time it takes to send data. _Tr is the time it takes to receive packets, and _Ts is the time it takes to scan for messages. Assuming that the energy of a node in the network will not become zero, when a node receives a data packet, it compares its current energy level with that of its neighbors to determine whether to forward the message to its neighbors. When the energy of the current node is less than the energy of the neighbor node, the data packet is forwarded to the next hop node according to the priority; when the energy of the current node is greater than the energy of the neighbor node, the forwarding is not performed, and the current node continues to generate or receive data packets, and then Re-prioritize the data packets, because in the process of receiving the data packets, the current node will continue to consume energy, and then judge the energy of the current node and neighbor nodes to select and forward the data packets until they are delivered to the destination node.

In addition to ordering and forwarding the data packets inside the node, since the memory of the node is also limited, the corresponding data packets need to be deleted in the buffer space, after which it will not be transmitted again. A node needs to complete one of three things in order to drop a packet without reducing the packet delivery rate of the delay tolerant network. First, a copy of the data packet has been transmitted to the destination node; second, within the timestamp range of the data packet, there is not enough bandwidth between the current node and the destination node to ensure that the data packet can be transmitted; third, if the current No copy of the data packet is transmitted to the destination node, but after the current node deletes the corresponding data packet it has saved, the copy of the data packet existing in other nodes can still be transmitted to the destination node. These guidelines can be verified, they are necessary and sufficient. First, these three cases are mutually exclusive. For any data packet, there will be no two or three cases that are satisfied at the same time; secondly, the only thing that is not considered is that the data packet is not transmitted to the destination node, but only The current node saves a copy of the packet before it can transmit the message to the destination node. All in all, for the deletion of data packets, the copies of the data packets that have been transmitted to the destination node will be deleted first; then the low-priority data packets will be selected for deletion. The lower the priority, the earlier they will be deleted.

The improved routing strategy described has other mechanisms to facilitate packet delivery and reduce message delivery delays. First, if the neighbor node is the destination node that a certain data packet needs to reach, then the corresponding data packet is sent first. Second, the probability estimates of encounters between nodes are exchanged between nodes. Third, for the data packets that have been successfully transmitted, there is an acknowledgment message forwarded. Each of these acknowledgment messages is 128 bits in length. The acknowledgment message includes the source node identification, destination node identification and encrypted specific information of the corresponding message. The hash value of the content, which can help eliminate outdated and useless messages from the network according to this confirmation mechanism. Fourth, the remaining unforwarded packets need to be sorted by priority. Fifth, there is a node list in the copy of each data packet to record all the nodes that have passed through, and the node list also includes the node currently forwarding the copy of the data packet. If a node has already received a data packet, it will not receive the node again.

After EA-MaxProp routing, because the node with high node energy is selected as the next hop, its survival time is long, the chance of being able to transmit the message to the destination node will be higher, and the number of transmissions will also be reduced, reducing network overhead. , the energy consumption of the node will be correspondingly reduced. For nodes with less energy, the probability of receiving data packets will also be reduced, the energy will not be used up prematurely, and the node will not die prematurely. The network life is fully extended, and the transmission rate of data packets will also increase

It should be noted that the above-described embodiments illustrate rather than limit the invention, and that alternative embodiments may be devised by those skilled in the art without departing from the scope of the appended claims.

Claims (8)

1. An energy-aware routing method for a delay tolerant network is characterized in that: the method comprises the following steps:

step 1, data packets are prioritized, namely, a source node generates the data packets, and then the priority of the data packets is ordered according to rules in data transmission in a storage area inside the node;

step 2, neighbor discovery, wherein before forwarding the message, the current node needs to discover other neighbor nodes in a communicable range, and if the neighbor nodes are discovered, data forwarding is carried out;

and 3, data forwarding, namely forwarding the data packets of the two nodes respectively after the two nodes enter the mutual communication range.

2. The delay tolerant network oriented energy aware routing method of claim 1, wherein: in the step 3, before neighbor discovery and data forwarding, the data packets are prioritized inside the nodes, and for the nodes, a proper next hop is selected for forwarding according to energy perception.

3. The delay tolerant network oriented energy aware routing method of claim 2, wherein: in the step 3, the data packet in the previous step is forwarded to the neighbor node, and when the energy of the current node is less than that of the neighbor node, the data packet is forwarded to the next hop node according to the priority; when the energy of the current node is larger than that of the neighbor node, the forwarding is not carried out, the current node continues to generate or receive data packets, the priority ranking is carried out on the data packets again, the current node can continue to consume energy in the process of receiving the data packets, and then the energy of the current node and the neighbor node is judged to carry out selective forwarding on the data packets until the data packets are delivered to the target node.

4. The delay tolerant network oriented energy aware routing method of claim 1, wherein: the message caching mode in the node is as follows: the storage area is divided into a left part and a right part by a threshold value, in the network, a data packet with the hop number smaller than the threshold value is forwarded as a higher priority, and if the hop number of a certain data packet is smaller than the threshold value, the priority of the data packet is larger than the threshold value; for the condition that the hop count of the data packet forwarding is smaller than the threshold value, arranging the data packets in response according to the hop count, wherein if the hop count of the data packet is larger, the priority is lower; when the number of hops the data packet passes is greater than the threshold value, the route adopts a self-adaptive method to adjust the threshold value, and the formula is as follows:

wherein, x is the average byte number transmitted when the message is transmitted, b is the capacity of the storage area, p is a part of the storage area, and the threshold value t is equal to the hop number of the data packet corresponding to the p-th byte in the message buffer area; if x < b/2, the data packet with smaller hop count is defined to have higher priority; as x becomes larger, the threshold value t is mainly determined by the minimum value of x and b-x; when x is greater than p, the threshold value is defined as 0.

5. The delay tolerant network oriented energy aware routing method of claim 4, wherein: when the hop number of the data packet is greater than a threshold value, sorting the data packet according to the transmission probability, wherein the higher the transmission probability value is, the higher the priority is; the transmit probability estimate is defined as follows:

assuming that the set of network nodes is s, for any node i e s, the probability f of meeting the node j is calculated_j ⁱWherein i ∈ s, j ≠ i, the initial value is 1/(| s | -1), when the node i and the node j meet,f_j ⁱwill automatically add 1 and then all associated probability values in node i will be normalized again, exchanging these probability values with each other whenever nodes meet; the local node will save the probability estimates of other nodes after obtaining them, and then can find the transmission cost c (i, i +1, …, d) to the destination node d through different paths, which is defined as the sum of the probability estimates that do not occur in each link, as shown in formula (2);

6. the delay tolerant network oriented energy aware routing method of claim 1, wherein: the selection of the next hop node is completed by judging the energy between the nodes, the resource of each node of the DTN is limited, and a large amount of energy needs to be consumed for ensuring the transmission of information, including the energy consumption of sending E_tReceiving the consumed energy E_rScanning information energy E_sThe specific calculation method is shown in formulas (3), (4) and (5):

E_t＝(P_e+P_aRⁿ)T_t (3)

E_r＝(P_e+P_p)T_r (4)

E_s＝P_sT_s (5)

wherein, P_eIs the energy consumed by the transceiver per second, P_aIs the energy consumed by the transmitter rf amplifier per second; p_pIs the energy consumed by the processing in the receiver, P_sIs the energy consumed by scanning to the radio environment, P_s＝P_eThese parameters are determined by the design characteristics of the transceiver; r is the transmission range, n is the power index of the channel path loss; t is_tIs the time consumed by sending data, T_rIs the time consumed by receiving a data packet, T_sIs the time consumed to scan the message; assuming that the energy of the nodes in the network does not becomeZero, when the node receives the data packet, comparing the current energy level with the energy level of the neighbor, judging whether to forward the message to the neighbor node, and when the energy of the current node is less than that of the neighbor node, forwarding the data packet to the next hop node according to the priority; when the energy of the current node is larger than that of the neighbor node, the current node does not transmit, continues to generate or receive data packets, and then carries out priority sequencing on the data packets again.

7. The delay tolerant network oriented energy aware routing method of claim 1, wherein: in addition to sequencing and forwarding the data packets in the node, the memory of the node is limited, and the corresponding data packets need to be deleted in the cache space, so that the data packets cannot be transmitted any more after deletion.

8. The delay tolerant network oriented energy aware routing method of claim 7, wherein: without reducing the packet transmission rate of the delay tolerant network, a node needs to accomplish one of three situations to delete a packet: first, a copy of the packet has been transmitted to the destination node; secondly, within the range of the time stamp of the data packet, the residual bandwidth between the current node and the destination node is less than the required bandwidth for transmitting the data packet so as to ensure that the data packet can be transmitted; third, if any copy of the current packet is not transmitted to the destination node, but after the current node deletes the corresponding packet stored therein, the copies of the packet existing in other nodes can still be transmitted to the destination node.

Images