CN112423366A - Transmission method of opportunity shortcut tree routing structure - Google Patents
Transmission method of opportunity shortcut tree routing structure Download PDFInfo
- Publication number
- CN112423366A CN112423366A CN202011237466.5A CN202011237466A CN112423366A CN 112423366 A CN112423366 A CN 112423366A CN 202011237466 A CN202011237466 A CN 202011237466A CN 112423366 A CN112423366 A CN 112423366A
- Authority
- CN
- China
- Prior art keywords
- timer
- routing structure
- opportunity
- tree routing
- node
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Pending
Links
- 230000005540 biological transmission Effects 0.000 title claims abstract description 30
- 238000000034 method Methods 0.000 title claims abstract description 21
- 235000008694 Humulus lupulus Nutrition 0.000 claims description 14
- 238000004891 communication Methods 0.000 abstract description 2
- 230000009191 jumping Effects 0.000 description 6
- 238000010586 diagram Methods 0.000 description 3
- 230000007423 decrease Effects 0.000 description 1
- 230000007812 deficiency Effects 0.000 description 1
- 238000005265 energy consumption Methods 0.000 description 1
- 238000005516 engineering process Methods 0.000 description 1
- 230000005284 excitation Effects 0.000 description 1
- 230000008569 process Effects 0.000 description 1
- 230000009467 reduction Effects 0.000 description 1
- 230000004044 response Effects 0.000 description 1
Images
Classifications
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04W—WIRELESS COMMUNICATION NETWORKS
- H04W40/00—Communication routing or communication path finding
- H04W40/24—Connectivity information management, e.g. connectivity discovery or connectivity update
- H04W40/248—Connectivity information update
Landscapes
- Engineering & Computer Science (AREA)
- Computer Networks & Wireless Communication (AREA)
- Signal Processing (AREA)
- Data Exchanges In Wide-Area Networks (AREA)
Abstract
本发明公开了一种机会快捷树型路由结构的传输方法，属于通信网络技术领域，结合了机会型路由结构和快捷树形路由结构的形式特点，并采用机会路由(OR)机制，令源节点或中间节点广播转发数据包，并使所有接收方节点均有机会转发数据包，同时根据整个路由传输剩余的节点数向目标提供优先级，以此抑制来自转发器候选项的多个重复数据包。本发明不需要任何开销查找路由路径和转发器候选项，并且可根据通道条件自行选择最佳路径，定向机会快捷树形路由(DOSTR)结构方法利用一跳相邻信息来减少不必要的数据包传输，并且缩短OSTR的端到端路由路径；可以为具有小资源容量和高性能路由需求的物联网应用实现可靠的数据包传输，同时保证了合理的端到端延迟。
The invention discloses a transmission method of an opportunistic shortcut tree routing structure, which belongs to the technical field of communication networks. Or intermediate nodes broadcast forwarding packets and give all receiver nodes a chance to forward the packets, while giving priority to the target according to the number of nodes remaining in the entire route transmission, thereby suppressing multiple duplicate packets from forwarder candidates . The invention does not need any overhead to find routing paths and forwarder candidates, and can choose the best path according to the channel conditions, and the directional opportunistic shortcut tree routing (DOSTR) structure method uses one-hop adjacent information to reduce unnecessary data packets It can realize reliable data packet transmission for IoT applications with small resource capacity and high-performance routing requirements, while ensuring reasonable end-to-end delay.
Description
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.
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.
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 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 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 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: 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 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 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 (5)
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN202011237466.5A CN112423366A (en) | 2020-11-09 | 2020-11-09 | Transmission method of opportunity shortcut tree routing structure |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN202011237466.5A CN112423366A (en) | 2020-11-09 | 2020-11-09 | Transmission method of opportunity shortcut tree routing structure |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| CN112423366A true CN112423366A (en) | 2021-02-26 |
Family
ID=74780734
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN202011237466.5A Pending CN112423366A (en) | 2020-11-09 | 2020-11-09 | Transmission method of opportunity shortcut tree routing structure |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN112423366A (en) |
Citations (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US20170150417A1 (en) * | 2015-11-24 | 2017-05-25 | King Fahd University Of Petroleum And Minerals | Method of routing for wireless ad hoc and sensor networks |
| CN110519822A (en) * | 2018-05-21 | 2019-11-29 | 天津科技大学 | A kind of chance routing candidate relay selection algorithm of low energy consumption |
-
2020
- 2020-11-09 CN CN202011237466.5A patent/CN112423366A/en active Pending
Patent Citations (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US20170150417A1 (en) * | 2015-11-24 | 2017-05-25 | King Fahd University Of Petroleum And Minerals | Method of routing for wireless ad hoc and sensor networks |
| CN110519822A (en) * | 2018-05-21 | 2019-11-29 | 天津科技大学 | A kind of chance routing candidate relay selection algorithm of low energy consumption |
Non-Patent Citations (1)
| Title |
|---|
| TAEHONG KIM等: ""Opportunistic Shortcut Tree Routing in ZigBee Networks"", 《IEEE SENSORS JOURNAL》 * |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| Mueller et al. | Multipath routing in mobile ad hoc networks: Issues and challenges | |
| US20020061001A1 (en) | Dynamic source tracing (DST) routing protocol for wireless networks | |
| CN101932062B (en) | Multipath routing method in Ad Hoc network environment | |
| CN103036783B (en) | A kind of based on DTN deep space sensor network multi-path method for routing | |
| CN108449271B (en) | Routing method for monitoring path node energy and queue length | |
| CN101568164A (en) | Opportunistic routing algorithm of Ad hoc network based on node priority levels | |
| Habib et al. | Review on MANET routing protocols and challenges | |
| Singh et al. | A survey: Ad-hoc on demand distance vector (AODV) protocol | |
| Naseem et al. | Congestion-aware Fibonacci sequence based multipath load balancing routing protocol for MANETs | |
| Kulkarni et al. | On demand routing protocols for mobile ad hoc networks: A review | |
| Gandhi et al. | Performance evaluation of DSR, OLSR and ZRP protocols in MANETs | |
| Cheng et al. | Virtual backbone-based routing in multihop ad hoc wireless networks | |
| Peng et al. | ARDSR: an anycast routing protocol for mobile ad hoc network | |
| Gruber et al. | Ad hoc routing for cellular coverage extension | |
| CN112423366A (en) | Transmission method of opportunity shortcut tree routing structure | |
| Lin et al. | BGCA: Bandwidth guarded channel adaptive routing for ad hoc networks | |
| Shukla et al. | A new route maintenance in dynamic source routing protocol | |
| Shah et al. | Adaptive anycast: A new anycast protocol for performance improvement in delay tolerant networks | |
| Rookhosh et al. | Disjoint categories in low delay and on-demand multipath dynamic source routing adhoc networks | |
| Vigita et al. | Reliable link-based routing protocol for highly dynamic mobile adhoc networks | |
| Oh | A hybrid routing protocol for wireless Mesh Networks | |
| Karuppasamy et al. | Comparative Study of Traditional Routing Protocols in Mobile Wireless Networks | |
| Hadi et al. | Effect of group size on anycasting with receiver base forwarding in delay tolerant networks | |
| Sruthy et al. | Variants of AODV routing protocol: A review | |
| Punnagai et al. | Simulation of broadcasting algorithm using neighbor information in mobile ad hoc networks |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| PB01 | Publication | ||
| PB01 | Publication | ||
| SE01 | Entry into force of request for substantive examination | ||
| SE01 | Entry into force of request for substantive examination | ||
| RJ01 | Rejection of invention patent application after publication | ||
| RJ01 | Rejection of invention patent application after publication |
Application publication date: 20210226 |