CN112423366A

CN112423366A - Transmission method of opportunity shortcut tree routing structure

Info

Publication number: CN112423366A
Application number: CN202011237466.5A
Authority: CN
Inventors: 曹宁; 沈欢; 冯晔
Original assignee: Hohai University HHU
Current assignee: Hohai University HHU
Priority date: 2020-11-09
Filing date: 2020-11-09
Publication date: 2021-02-26

Abstract

The invention discloses a transmission method of an opportunity shortcut tree-type routing structure, which belongs to the technical field of communication networks, combines the form characteristics of the opportunity-type routing structure and the shortcut tree-type routing structure, adopts an Opportunity Routing (OR) mechanism, enables a source node OR an intermediate node to broadcast and forward a data packet, enables all receiver nodes to have an opportunity to forward the data packet, and provides priority for a target according to the number of nodes remained in the whole routing transmission so as to inhibit a plurality of repeated data packets from a candidate item of a repeater. The invention does not need any overhead to search a routing path and a transponder candidate item, can automatically select an optimal path according to channel conditions, and reduces unnecessary data packet transmission by using one hop of adjacent information and shortens an end-to-end routing path of OSTR by using a Directional Opportunistic Shortcut Tree Routing (DOSTR) structure method; reliable data packet transmission can be realized for the application of the Internet of things with small resource capacity and high-performance routing requirements, and reasonable end-to-end delay is ensured.

Description

Transmission method of opportunity shortcut tree routing structure

Technical Field

The invention belongs to the technical field of communication networks, and particularly relates to a transmission method of an opportunity shortcut tree routing structure.

Background

ZigBee is one of the global standards for internet of things (IoT) technology. Besides personal area network applications such as smart home, building automation, medical care and the like, the ZigBee is connected with tens of millions of devices, and the application field can be expanded to smart cities and smart power grids. Since the release of ZigBee network specifications, ZigBee tree routing structures (ZTR) have attracted much attention because they can implement a resource-free multi-hop routing function. The fast tree routing Structure (STR) can improve the efficiency of multi-hop routing paths and reduce traffic load concentrated on tree links, and thus becomes an important basic routing structure.

Meanwhile, the recent Opportunistic Routing (OR) protocol utilizes the cooperative diversity of the propagation characteristics to transmit packets through a plurality of repeater candidates, thereby solving the fundamental efficiency limitation problem of the real wireless medium due to its own loss, time variation, propagation characteristics, and the like. However, through further research, the OR protocol and the ZTR and STR protocols still have some safety problems:

(1) although the OR protocol has the ability to improve bandwidth utilization and end-to-end reliability, it still has certain deficiencies in determining repeater candidates and determining priority efficiency;

(2) the OR protocol inevitably transmits data packets from the candidate items of the repeater repeatedly, and additional resources are needed to search a routing path and acquire a candidate list of the repeater in order to solve the problem;

(3) the probability of packet loss increases with the end-to-end distance of the multi-hop path, so the packet transfer ratio of STR and ZTR decreases with increasing end-to-end distance;

(4) the broadcast nature of the wireless medium causes interference between transmissions, which may prevent concurrent transmissions, resulting in transmission inefficiencies.

In response to the above problems, some improvements consider that the expected number of transmissions required to transmit a packet from a source node to a destination node can be minimized by a minimum transmission selection scheme (MTS) using a dynamic programming formula. Some proposals have also proposed methods for distance-based maximum candidate estimation (D-MACE), which estimates the maximum number of candidates based on the distance of the node to the target location. Still other schemes define a new set of energy models through the energy consumption of opportunistic routing and propose corresponding energy-efficient repeater selection algorithms. However, these candidate selection algorithms all need to process the problems of distance, position, global topology information, etc. in advance, and have great limitations.

Therefore, in various application scenarios of the internet of things with small resource capacity and high performance routing requirement, a routing structure which does not need any extra overhead to find routing paths and repeater candidates needs to be proposed and widely applied.

Disclosure of Invention

The purpose of the invention is as follows: the invention aims to provide a transmission method of an opportunity shortcut tree routing structure.

The technical scheme is as follows: in order to achieve the purpose, the invention provides the following technical scheme:

a transmission method of an opportunistic shortcut tree routing structure does not need to provide any resource for a multi-node router and a router repeater, and comprises the following steps:

step 1: when the timer T of the receiving node or the target node expires, the data packet P is rebroadcast, and if + + retryCnt < maxRetry, the timer T is reset by using RH (U, D) × delta;

step 2: timer T is not expired and U receives packet P from S with destination D; if P is received for the first time and RH (U, D) is 0, rebroadcast packet P;

and step 3: if RH (U, D) ≠ 0, and RH (U, D) < RH (S, D), then P is stored to the cache, retryCnt is set to zero, while timer T is reset with (RH (U, D) -1, RH (U, D)) × δ;

and 4, step 4: on the premise of meeting the step 2, if P is not received for the first time, checking the timer T, and if the timer T is activated and RH (U, D) > RH (S, D), discarding the packet P from the buffer, and canceling the timer T at the same time;

wherein S is a source node; u is a receiving node; d is a target node; δ is the minimum duration of reliable forwarding; retryCnt is the route forwarding retry count; , + retryCnt adds 2 for the route forwarding retry count; MaxRetry is the maximum number of retries for route forwarding.

Further, when the opportunistic shortcut tree routing structure is a directed opportunistic shortcut tree routing structure, the step 2 is replaced by: timer T is not expired and U receives packet P from S with destination D; if P is received for the first time and RH (U, D) is 0, the packet P is rebroadcast by updating minRH (U, D).

Further, on the premise that the step 2 replacement is satisfied, the step 3 replacement is as follows: if RH (U, D) ≠ 0, and both minRH (U, D) < minRH (S, D) and RH (U, D) < RH (S, D) are satisfied, minRH (U, D) is updated and packet P is stored in the buffer, retryCnt is set to zero, and timer T is reset with (minRH (U, D) -1, minRH (U, D)). delta.

Further, when the opportunistic shortcut tree routing structure is a directed opportunistic shortcut tree routing structure, on the premise that the step 2 is satisfied, the step 4 is to check the timer T if the data packet P is not received for the first time; if the timer T is activated and RH (U, D) > RH (S, D), the packet P is discarded from the buffer while the timer T is deactivated.

Further, when the opportunistic tree routing structure is a directed opportunistic tree routing structure, in the DOSTR, each data packet encapsulates a minimum hop field in a packet header, and a source node or an intermediate node updates the field according to the remaining minimum hops between its hop neighbors; in OSTR, the remaining hops of the node are lower than the remaining hops of the previous sender and become the candidate items of the repeater; in the DOSTR, the node becomes the candidate node of the repeater under the condition that the nodes reduce the rest of the jumping points to the target or one-hop neighbor points.

Has the advantages that: compared with the prior art, the invention inherits the advantages of two routing protocols, can provide reliable data packet transmission service, does not need to provide additional resources for multi-hop routing and forwarder candidate selection, improves the reliability of data packet transmission and the channel utilization rate, and can reduce end-to-end delay and unnecessary data transmission by the proposed DOSTR; the method is suitable for various application scenes of the Internet of things with small resource capacity and high-performance routing requirements.

Drawings

FIG. 1 is a flow diagram of a method for transmission of an opportunistic tree routing structure;

FIG. 2 is a directed opportunistic shortcut tree routing flow diagram;

FIG. 3 is a comparison of excitation examples for four configurations;

FIG. 4 is a graph of packet transmission rate comparison;

FIG. 5 is an end-to-end delay contrast diagram;

fig. 6 is a graph of a comparison of the average number of hopping nodes transmitted.

Detailed Description

The invention will be further described with reference to the following drawings and specific embodiments.

When the opportunistic shortcut tree routing structure is the oriented opportunistic shortcut tree routing structure, replacing the step 2 with: timer T is not expired and U receives packet P from S with destination D; if P is received for the first time and RH (U, D) is 0, the packet P is rebroadcast by updating minRH (U, D).

On the premise of satisfying the step 2 replacement, the step 3 replacement is as follows: if RH (U, D) ≠ 0, and both minRH (U, D) < minRH (S, D) and RH (U, D) < RH (S, D) are satisfied, minRH (U, D) is updated and packet P is stored in the buffer, retryCnt is set to zero, and timer T is reset with (minRH (U, D) -1, minRH (U, D)). delta.

When the opportunistic shortcut tree routing structure is the directed opportunistic shortcut tree routing structure, on the premise that the step 2 is satisfied, the step 4 is to check a timer T if the data packet P is not received for the first time; if the timer T is activated and RH (U, D) > RH (S, D), the packet P is discarded from the buffer while the timer T is deactivated.

When the routing structure of the opportunistic tree type is the routing structure of the directional opportunistic tree type, in the DOSTR, each data packet encapsulates a minimum jumping point field in a packet header, and a source node or an intermediate node updates the field according to the residual minimum jumping points between one jumping adjacent point; in OSTR, the remaining hops of the node are lower than the remaining hops of the previous sender and become the candidate items of the repeater; in the DOSTR, the node becomes the candidate node of the repeater under the condition that the nodes reduce the rest of the jumping points to the target or one-hop neighbor points.

Examples

Fig. 1 is a flowchart of a transmission method of an opportunistic shortcut tree routing structure, which includes the following specific steps:

description of the drawings: s, a source node; u is a receiving node; d, target node; δ is the minimum duration of reliable forwarding; retryCnt is the route forwarding retry count; , + retryCnt, route forwarding retry count plus 2; MaxRetry, namely the maximum retry times of route forwarding; RH (1,2) the number of remaining hops from 1 to 2; minRH (1,2) minimum number of remaining hops from 1 to 2;

step 2: timer T has not expired and U receives packet P from S destined for D. If P is received for the first time and RH (U, D) is 0, rebroadcast packet P;

and 4, step 4: if P is not received for the first time, the timer T is checked, and if the timer T is activated and RH (U, D) > RH (S, D), the packet P is discarded from the buffer while the timer T is deactivated, on the premise that step 2 is satisfied.

As shown in fig. 3, the next hop node in ZTR and STR is determined by the sender node, and therefore, even if there is a case of a lost path or propagation congestion, the routing path cannot be changed. In contrast, the routing path of the OSTR may be adjusted based on the link congestion conditions. Assuming that S transmits a packet to D and dynamically selects a repeater based on packet reception and priority of remaining hops to destination, the gray areas in fig. 3 are repeater candidate nodes. By dynamic participation of neighboring nodes, the OSTR can improve the reliability of packet delivery and channel utilization. Referring to fig. 4 and 5, it can be observed that the data transmission rate and the transmission average node number of the OSTR are significantly improved compared to those of STR and ZTR. The reduction in the number of transmission average nodes means that the whole routing network does not need more equipment, and the cost for deploying the network can be remarkably reduced.

Fig. 2 shows a flowchart of a method for directing a opportunistic shortcut tree routing structure, which includes the following steps:

step 2: timer T has not expired and U receives packet P from S destined for D. If P is received for the first time and RH (U, D) is 0, rebroadcast packet P by updating minRH (U, D);

and step 3: if RH (U, D) is not equal to 0 and simultaneously meets minRH (U, D) < minRH (S, D) and RH (U, D) < RH (S, D), updating minRH (U, D) and storing the data packet P in a buffer area, setting retryCnt to zero, and resetting the timer T by using (minRH (U, D) -1, minRH (U, D))) delta;

and 4, step 4: if the data packet P is not received for the first time, the timer T is checked, provided that step 2 is satisfied. If the timer T is activated and RH (U, D) > RH (S, D), the packet P is discarded from the buffer while the timer T is deactivated.

In DOSTR, each packet encapsulates a minimum hop field in the header, which is updated by the source or intermediate node according to the remaining minimum hops between its hop neighbors. In the OSTR, the remaining hops of the node are lower than those of the previous sender, and thus the node can become a repeater candidate, but in the DOSTR, the node can become a repeater candidate node only under the condition that the remaining hops are all reduced to the target or one hop neighbor. As in fig. 3(2), the minimum remaining jumping point of S is 3 because B and E are one-hop neighbors of S. When S broadcasts a packet, B, E, F, G are both forwarder candidates for OSTR, while only B and E may be forwarder candidates for DOSTR, since B and E may reduce the remaining minimum number of hops for transmission to 2. According to fig. 4, fig. 5 and fig. 6, after using DOSTR, not only the packet transmission rate and the average number of nodes to be transmitted can be optimized, but also the end-to-end delay caused by using the OSTR can be significantly reduced.

The above methods show that the proposed OSTR and DOSTR methods can significantly reduce the cost and improve the channel utilization rate.

Claims

1. A transmission method of an opportunity shortcut tree routing structure is characterized in that: the method comprises the following steps:

2. The transmission method of an opportunistic tree routing structure according to claim 1, characterized in that: when the opportunistic shortcut tree routing structure is a directed opportunistic shortcut tree routing structure, the step 2 is replaced by: timer T is not expired and U receives packet P from S with destination D; if P is received for the first time and RH (U, D) is 0, the packet P is rebroadcast by updating minRH (U, D).

3. The transmission method of an opportunistic tree routing structure according to claim 2, characterized in that: on the premise of satisfying the step 2 replacement, the step 3 replacement is as follows: if RH (U, D) ≠ 0, and both minRH (U, D) < minRH (S, D) and RH (U, D) < RH (S, D) are satisfied, minRH (U, D) is updated and packet P is stored in the buffer, retryCnt is set to zero, and timer T is reset with (minRH (U, D) -1, minRH (U, D)). delta.

4. The transmission method of an opportunistic tree routing structure according to claim 2, characterized in that: when the opportunistic shortcut tree routing structure is a directed opportunistic shortcut tree routing structure, on the premise of meeting the replacement in the step 2, the step 4) specifically checks a timer T if the data packet P is not received for the first time; if the timer T is activated and RH (U, D) > RH (S, D), the packet P is discarded from the buffer while the timer T is deactivated.

5. The transmission method of an opportunistic tree routing structure according to claim 2, characterized in that: when the opportunistic tree routing structure is a directed opportunistic tree routing structure, in the DOSTR, each data packet encapsulates a minimum jumping point field in a packet header, and a source node or an intermediate node updates the field according to the remaining minimum jumping points between one hop neighbor of the source node or the intermediate node; in OSTR, the remaining hops of the node are lower than the remaining hops of the previous sender and become the candidate items of the repeater; in the DOSTR, the node becomes the candidate node of the repeater under the condition that the nodes reduce the rest of the jumping points to the target or one-hop neighbor points.