CN112188582B - Reliable routing method for lattice network based on physical perception information - Google Patents

Abstract

A lattice network reliable routing method based on physical perception information reduces the influence of obstacles on the reliability of data transmission, and comprises the following steps: (1) node identification, namely identifying the nodes as external, internal and boundary nodes according to real-time obstacle perception information returned by the sensor; (2) and (4) recovering the route, and after the barrier is moved into the sensing dot matrix, re-planning a routing path by the boundary node according to the current barrier sensing information, so that the data packet is forwarded to bypass along the edge of the barrier until the data packet is separated from the influence range of the barrier. The invention utilizes the real-time sensor data to directly control the routing decision, greatly improves the real-time performance of the routing recovery when the barrier appears suddenly, and reduces the possibility of data loss under the interference of the barrier.

Description

Reliable routing method for lattice network based on physical perception information

technical field

The invention relates to a reliable routing method of a lattice network based on physical perception information.

Background technique

L.Mottola,M.A.

H.Youssef,C.A.Boano,and M.Alves,“Radio link quality estimation in wirelesssensor networks:A survey,”ACM Transactions on Sensor Networks,vol.8,no.4,pp.1–33,2012(N.Baccour,A.

L.Mottola,M.A.

H.Youssef,C.A.Boano,和M.Alves,“无线传感器网络中无线链路质量估计研究综述,”ACM传感器网络汇刊,第8卷,第4期,第1页到第33页,2012)。所存在的问题主要包括：(1)现有方法大多依赖于对历史数据包发送情况统计估计链路质量，对突发路由空洞检测的延迟很大；(2)基于拓扑的方法需要节点间交换链路质量估计结果计算全局传输开销，进一步加大了路由空洞恢复的延迟。文献[6]M.Xia,B.Liu,Y.H.Hu,K.Chi,X.Wang,and J.Liu,“Pace:Physical-assistedchannel estimation,”IEEE Transactions on Wireless Communications,vol.19,no.6,pp.3769–3781,2020(M.Xia,B.Liu,Y.H.Hu,K.Chi,X.Wang,和J.Liu,“Pace：物理辅助信道估计,”IEEE无线通讯汇刊,第19卷,第6期,第3769页到3781页,2020)提出了一种使用传感器物理感知信息进行链路质量估计的方法，较好的解决了现有链路质量估计器难以对突然出现的障碍物引起的链路质量变化进行实时估计的问题。然而，该方法无法解决问题(2)，当移动障碍物导致突发路由空洞时，无法完全避免数据传输失败。Obstacles are an important factor affecting the quality of wireless transmission. When movable obstacles block the wireless signal transmission path, some nodes may not be able to communicate with other nodes normally, resulting in sudden routing holes. At present, routing protocols can be mainly divided into topology-based, such as literature [1] O.Gnawali, R.Fonseca, K.Jamieson, M.Kazandjieva, D.Moss, and P.Levis, "Ctp: An efficient, robust, and reliable collection treeprotocol for wireless sensor networks,"ACM Transactions on Sensor Networks,vol.10,no.1,pp.1–49,2013(O.Gnawali,R.Fonseca,K.Jamieson,M.Kazandjieva,D.Moss , and P. Levis, "Ctp: An Efficient, Robust, and Reliable Collection Tree Protocol for Wireless Sensor Networks," ACM Transactions on Sensor Networks, Vol. 10, No. 1, pp. 1 to 49, 2013), and location-based, as in [2] B.Karp and H.T.Kung, "Gpsr: greedy perimeter stateless routing for wireless networks," in Proceedings of the 6th annual international conference on Mobile computing and networking (MobiCom), 2000, p.243–254 (B.Karp and HTKung, "Greedy Edge Stateless Routing in Wireless Networks," Proceedings of the 6th International Annual Conference on Mobile Computing and Networking (MobiCom), 2000, pp. 243 to 254) . Most of the topology-based methods require nodes to maintain a dynamic global transmission cost (such as the number of hops to the sink node, the number of transmissions, etc.), and select the path with the lowest cost. The method based on geographic location relies on the geographic location of the node, and selects the node closest to the sink node for forwarding. For example [3] A. Mostefaoui, M. Melkemi, and A. Boukerche, "Localized routing approach to bypass holes in wireless sensor networks," IEEE Transactions on Computers, vol.63, no.12, pp.3053–3065, 2014 ( A. Mostefaoui, M. Melkemi, and A. Boukerche, "Localized Hole Routing Method in Wireless Sensor Networks," IEEE Transactions on Computing, Vol. 63, No. 12, pp. 3053-3065, 2014) As mentioned above, geographic location-based methods suffer from a "local minimization" problem, that is, all neighbor nodes are farther away from the sink node than themselves. The problem only occurs at the edges of routing holes (no nodes inside the holes). Geographical location-based routing protocols generally bypass holes through left-hand and/or right-hand rules, as described in [4] H.Huang, H.Yin, G.Min, J.Zhang, Y.Wu, and X.Zhang, "Energy -aware dual-path geographic routing to bypass routing holes inwireless sensor networks,”IEEE Transactions on Mobile Computing,vol.17,no.6,pp.1339–1352,2018(H.Huang,H.Yin,G.Min, J. Zhang, Y. Wu, and X. Zhang, "Energy-aware dual-path geo-routing around holes in wireless sensor networks," IEEE Transactions on Mobile Computing, Vol. 17, No. 6, pp. 1339 to 1352, 2018 ). However, most of the existing address-location-based routing protocols assume that the hole is static, and lack effective and fast detection and recovery methods for dynamically occurring holes. However, topology-based routing protocols often use link quality estimators to dynamically sample communication quality, such as literature [5] N.Baccour, A.

L.Mottola, MA

H. Youssef, CABoano, and M. Alves, “Radio link quality estimation in wireless sensor networks: A survey,” ACM Transactions on Sensor Networks, vol. 8, no. 4, pp. 1–33, 2012 (N. Baccour, A.

L.Mottola, MA

H. Youssef, CABoano, and M. Alves, "Review of Research on Wireless Link Quality Estimation in Wireless Sensor Networks," ACM Transactions on Sensor Networks, Vol. 8, No. 4, pp. 1-33, 2012). The existing problems mainly include: (1) Most of the existing methods rely on the statistical estimation of the link quality of the historical data packet transmission, and the delay of the burst routing hole detection is very large; (2) The topology-based methods require exchanges between nodes. The link quality estimation result calculates the global transmission cost, which further increases the delay of route hole recovery. Reference [6] M.Xia, B.Liu, YHHu, K.Chi, X.Wang, and J.Liu, "Pace: Physical-assisted channel estimation," IEEE Transactions on Wireless Communications, vol.19, no.6, pp.3769–3781, 2020 (M. Xia, B. Liu, YHHu, K. Chi, X. Wang, and J. Liu, "Pace: Physically Aided Channel Estimation," IEEE Transactions on Wireless Communications, Vol. 19, Issue 6, pages 3769 to 3781, 2020) proposed a method for link quality estimation using sensor physical perception information, which better solves the problem that existing link quality estimators are difficult to cause by sudden obstacles. The problem of real-time estimation of changes in link quality. However, this method cannot solve the problem (2), which cannot completely avoid the failure of data transmission when a moving obstacle causes a sudden routing hole.

SUMMARY OF THE INVENTION

In order to overcome the deficiencies of the prior art, the present invention provides a reliable routing method for a lattice network based on physical perception information. The method utilizes the sensor obstacle detection information to actively infer the location and direction of the obstacle, and quickly establish a routing path around the boundary of the eye obstacle. This effectively avoids data transmission failures caused by sudden obstacles.

The technical scheme adopted by the present invention to solve its technical problems includes:

A reliable routing method for a lattice network based on physical perception information, using sensor data to forward data packets to detour along the edge of obstacles to avoid data transmission failures caused by obstacles, the method includes the following steps:

(1) Node ID

According to the sensor data, the data transmission nodes are divided into three categories: external, internal and boundary nodes; for external nodes, their sensors cannot detect obstacles; for internal nodes, their sensors detect obstacles covering above them; for boundary nodes, Its sensor detects that the obstacle is on the side of the node;

(2) Route recovery

When the border node receives the data packet from the external node, it uses the sensor data to judge whether the obstacle is located between the node and the sink node. If so, it sets itself as the entry node, and re-plans the path. , so that the data packet detours along the edge of the obstacle; in the detour process, if a boundary node judges that the obstacle is no longer located between the node and the sink node through sensor data, it sets itself as the exit node and ends the detour.

Further, in the step (2), the process that the boundary node uses sensor data to determine whether the obstacle is located between the node and the sink node in the route recovery is as follows:

其中

表示该节点传感器检测到的障碍物与自身方位关系，0≤θ<2π，

表示该节点与汇聚节点v_sink间相对位置关系：For node v _i , the angle is calculated by

in

Represents the relationship between the obstacle detected by the sensor of this node and its own orientation, 0≤θ<2π,

Indicates the relative positional relationship between the node and sink node v _sink :

则障碍物位于该节点与汇聚节点之间，否则障碍物位于该节点与汇聚节点同侧。like

Then the obstacle is located between the node and the sink node, otherwise the obstacle is located on the same side of the node and the sink node.

Further, in the described step (2), the following methods are adopted to optimize the detour of the data packet in the route recovery, and the process is:

(2.1) Selection of the best detour direction

Whenever the node newly sets itself as the exit node and judges that it faces the four corners of the obstacle, it sends control packets in both clockwise and counterclockwise directions. Reach another exit node; all boundary nodes passed through calculate the optimal detour direction through the control packet, thereby optimizing the detour cost of the data packet entering from the entry node;

(2.2) Boundary control

There are two types of abnormal situations in the process of data packets detouring along the edge of the obstacle: first, forwarding across the four sides of the obstacle to the internal node; second, forwarding across the four corners of the obstacle to the external node, and actively capturing the abnormal forwarding data packet through the border node and detouring The way of forwarding is used to solve the problem of packet loss.

Preferably, in the step (2.1), the step of the border node forwarding the data packet and the control packet along the edge of the obstacle is as follows:

First, the sensing node calculates the direction θ _next of the next hop node relative to itself according to the following formula according to θ and the detour direction dd recorded in the data packet or control packet;

Then, according to θ _next , find the border node farthest from itself in the direction of θ _next in the relative position table of neighbor nodes as the forwarding target node, and forward data or control packets to the target node.

Preferably, in the step (2.1), the process that the boundary node calculates the best detour direction best_dd through the control packet is as follows:

The control packet sent by the egress node contains a cost field with an initial value of 0; if the border node receives the control packet, and the forwarding destination of the control packet is itself or the forwarding path passes through itself, the value stored in the cost field in the data packet is equal to that of the control packet. The distance of the source node relative to itself is accumulated to obtain the detour cost new_cost of the source direction of the control packet; at this time, if the node has not obtained the best detour direction best_dd or the current best detour cost best_cost is greater than new_cost, use new_cost to update best_cost, and use the source direction of the control packet as best_dd;

If the destination node of the control packet received by the border node is itself, record new_cost in the cost field of the control packet, and continue to forward the control packet.

Preferably, in the step (2.1), the control process of the ingress node for the forwarding direction dd in the data packet is as follows:

If best_dd is not empty, such as best_dd is clockwise, the data packet dd is set to 1, such as best_dd is counterclockwise, then the data packet dd is set to -1, and forwarded along the best direction of the edge of the obstacle; if best_dd is empty, Then, two copies of the data packet are generated, and the dd field is filled with 1 and -1 respectively, and forwarded in both directions along the edge of the obstacle.

More preferably, in the step (2.2), the process of the border node judging that the data packet is forwarded to the internal node over the four sides of the obstacle is as follows:

When the border node v _i captures the data packet, it passes the following formula:

和该边界节点指向数据包目的节点v_d的向量

利用下式：Calculate the vector (d, θ _j ), where d is the distance between nodes, and point to the vector of packet source node v _s through this boundary node

and the vector of the boundary node pointing to the packet destination node v _d

Use the following formula:

Calculate whether x ₁ , x ₂ , and x ₃ are all less than 0; if so, judge that the data packet is forwarded to the internal node across the four sides of the obstacle.

In the step (2.2), the process that the border node judges that the data packet is forwarded to the external node across the four corners of the obstacle is as follows:

和该边界节点节点指向数据包目的节点v_d的向量

利用下式：When the border node v _i captures the data packet, it points to the vector of the source node v _s of the data packet through the border node

and the vector of the border node node pointing to the packet destination node v _d

Use the following formula:

Determine whether x ₄ is 0; if so, determine that the data packet is forwarded to the external node across the four corners of the obstacle.

The beneficial effects of the present invention are mainly manifested in: using the real-time physical perception information returned by the sensor to quickly restore the invalid routing path affected by obstacles, thereby avoiding data transmission failure.

Description of drawings

Figure 1 is a schematic diagram of node identification.

FIG. 2 is a schematic diagram of route restoration.

Figure 3 is a schematic diagram of the first type of abnormal phenomenon.

Figure 4 is a schematic diagram of the second type of abnormal phenomenon.

Detailed ways

The present invention will be further described below in conjunction with the accompanying drawings.

Referring to Figures 1 to 4, a reliable routing method for a lattice network based on physical perception information, using sensor data to forward data packets around the edge of obstacles to avoid data transmission failure caused by obstacles, the method includes the following steps :

(1) Node ID

As shown in Figure 1, according to the sensor data, the data transmission nodes are divided into three categories: external, internal and boundary nodes; for external nodes, their sensors cannot detect obstacles; for internal nodes, their sensors detect obstacles covering their Above; for boundary nodes, whose sensors detect obstacles on the side of the node;

(2) Route recovery

As shown in Figure 2, when the border node receives the data packet from the external node, it uses the sensor data to determine whether the obstacle is located between the node and the sink node. If so, it sets itself as the entry node, and re-plans the path. Forward data between border nodes to make data packets detour along the edge of the obstacle; during the detour process, if a border node judges that the obstacle is no longer located between its own node and the sink node through sensor data, it sets itself as the exit node, end the detour.

Further, in the step (2), the process that the boundary node uses sensor data to determine whether the obstacle is located between the node and the sink node in the route recovery is as follows:

其中

表示该节点传感器检测到的障碍物与自身方位关系，

表示该节点与汇聚节点v_sink间相对位置关系：For node v _i , the angle is calculated by

in

Represents the relationship between the obstacle detected by the node sensor and its own orientation,

Indicates the relative positional relationship between the node and sink node v _sink :

则障碍物位于该节点与汇聚节点之间，否则障碍物位于该节点与汇聚节点同侧。like

Then the obstacle is located between the node and the sink node, otherwise the obstacle is located on the same side of the node and the sink node.

Further, in the described step (2), the following methods are adopted in the route recovery to optimize the detour of the data packet, and the process is as follows:

(2.1) Selection of the best detour direction

Whenever the node newly sets itself as the exit node and judges that it faces the four corners of the obstacle, it sends control packets in both clockwise and counterclockwise directions. Reach another exit node; all boundary nodes passed through calculate the optimal detour direction through the control packet, thereby optimizing the detour cost of the data packet entering from the entry node;

Among them, the process of the border node forwarding data packets and control packets along the edge of the obstacle is as follows:

First, the sensing node calculates the direction θ _next of the next hop node relative to itself according to the following formula according to θ and the detour direction dd recorded in the data packet or control packet;

Then, according to θ _next , find the boundary node farthest from itself in the direction of θ _next in the relative position table of neighbor nodes as the forwarding target node, and forward data or control packets to the target node;

The process for the boundary node to calculate the best detour direction best_dd through the control packet is as follows:

The control packet sent by the egress node contains a cost field with an initial value of 0; if the border node receives the control packet, and the forwarding destination of the control packet is itself or the forwarding path passes through itself, the value stored in the cost field in the data packet is equal to that of the control packet. The distance of the source node relative to itself is accumulated to obtain the detour cost new_cost of the source direction of the control packet; at this time, if the node has not obtained the best detour direction best_dd or the current best detour cost best_cost is greater than new_cost, use new_cost to update best_cost, and use the source direction of the control packet as best_dd;

If the destination node of the control packet received by the border node is itself, record new_cost in the cost field of the control packet, and continue to forward the control packet;

The control process of the ingress node for the forwarding direction dd in the data packet is as follows:

If best_dd is not empty, such as best_dd is clockwise, the data packet dd is set to 1, such as best_dd is counterclockwise, then the data packet dd is set to -1, and forwarded along the best direction of the edge of the obstacle; if best_dd is empty, Then two copies of the data packet are generated, and the dd field is filled with 1 and -1 respectively, and forwarded in both directions along the edge of the obstacle;

(2.2) Boundary control

There are two types of abnormal situations in the process of data packets detouring along the edge of the obstacle: first, forwarding across the four sides of the obstacle to the internal node; second, forwarding across the four corners of the obstacle to the external node, and actively capturing the abnormal forwarding data packet through the border node and detouring The way of forwarding is used to solve the problem of packet loss;

Among them, as shown in Figure 3, the process of the border node judging that the data packet has passed the four sides of the obstacle and forwarded to the internal node is as follows:

When the border node v _i captures the data packet, it passes the following formula:

和该边界节点指向数据包目的节点v_d的向量

利用下式：Calculate the vector (d, θ _j ), where d is the distance between nodes, and point to the vector of packet source node v _s through this boundary node

and the vector of the boundary node pointing to the packet destination node v _d

Use the following formula:

Calculate whether x ₁ , x ₂ , and x ₃ are all less than 0; if so, judge that the data packet is forwarded to the internal node across the four sides of the obstacle;

As shown in Figure 4, the process of the border node judging that the data packet is forwarded to the external node across the four corners of the obstacle is as follows:

和该边界节点节点指向数据包目的节点v_d的向量

利用下式：When the border node v _i captures the data packet, it points to the vector of the source node v _s of the data packet through the border node

and the vector of the border node node pointing to the packet destination node v _d

Use the following formula:

Determine whether x ₄ is 0; if so, determine that the data packet is forwarded to the external node across the four corners of the obstacle.

Claims (3)

1. A dot matrix network reliable routing method based on physical perception information is characterized in that sensor data are utilized to enable data packets to be forwarded and detour along the edge of an obstacle, and data transmission failure caused by the obstacle is avoided, and the method comprises the following steps:

(1) node identification

Dividing data transmission nodes into three types of external nodes, internal nodes and boundary nodes according to sensor data; for external nodes, the sensors thereof cannot detect obstacles; for an internal node, its sensor detects an obstacle overlaid over it; for a boundary node, a sensor of the boundary node detects that an obstacle is positioned on the side of the node;

(2) route restoration

When the boundary nodes receive data packets from external nodes, judging whether the obstacles are positioned between the local nodes and the sink nodes by using sensor data, if so, setting the self as an entrance node, replanning a path, and enabling the data packets to bypass along the edges of the obstacles by forwarding data between the boundary nodes; in the bypassing process, if a certain boundary node judges that the barrier is no longer positioned between the node and the sink node through sensor data, the boundary node is set as an exit node, and the bypassing is finished;

in the step (2), the process that the boundary node judges whether the obstacle is positioned between the node and the sink node by using the sensor data in the route recovery is as follows:

for node v _i Calculating the angle by the following formula

Wherein

The relationship between the obstacle detected by the node sensor and the orientation of the node sensor is shown, and theta is more than or equal to 0<2π，

Represents the node and the sink node v _sink Relative positional relationship between:

such as

The barrier is positioned between the node and the sink node, otherwise, the barrier is positioned at the same side of the node and the sink node;

in the step (2), the following method is adopted to optimize data packet detour in the route recovery, and the process is as follows:

(2.1) selection of optimal detour direction

When a node is newly set as an exit node and judges that the node faces four corners of an obstacle, a control packet is sent to the clockwise direction and the anticlockwise direction at the same time, and the control packet is forwarded between boundary nodes and bypasses along the edge of the obstacle until the control packet reaches another exit node; all the passed boundary nodes calculate the optimal detour direction through the control packet, so that the data detour cost entering from the entrance node is optimized;

(2.2) boundary control

Aiming at two types of abnormal conditions in the process that a data packet bypasses along the edge of an obstacle: firstly, four sides of an obstacle are crossed and forwarded to an internal node; secondly, the data packets are forwarded to external nodes across four corners of an obstacle, and the problem of data packet loss is solved by means of actively capturing abnormal forwarding data packets by boundary nodes and performing detour forwarding;

in the step (2.1), the step of forwarding the data packet and the control packet by the boundary node along the edge of the obstacle is as follows:

first, the sensor node calculates the direction θ of the next-hop node relative to itself from θ and the detour direction dd recorded in the data packet or the control packet by the following equation _next ；

Then according to theta _next Finding theta in the neighbor node relative position table _next The boundary node farthest away from the boundary node in the direction is used as a forwarding target node, and data or a control packet is forwarded to the target node;

in the step (2.2), the process that the boundary node judges that the data packet crosses four sides of the obstacle and is forwarded to the internal node is as follows:

boundary node v _i When a packet is captured, the following is passed:

computing the vector (d, θ) _j ) Where d is the distance between nodes and points to the source node v of the data packet through the boundary node _s Vector of (2)

And the boundary node points to the destination node v of the data packet _d Vector of (2)

Utilizing the following formula:

calculating x ₁ 、x ₂ 、x ₃ Whether all are less than 0; if yes, judging that the data packet crosses four sides of the barrier and is forwarded to the internal node;

in the step (2.2), the process that the boundary node judges that the data packet crosses four corners of the obstacle and is forwarded to the external node is as follows:

boundary node v _i When capturing the data packet, point to the source node v of the data packet through the boundary node _s Vector of (2)

And the boundary node points to the destination node v of the data packet _d Vector of (2)

Utilizing the following formula:

judgment of x ₄ Whether or not it is 0; if yes, the data packet is judged to cross four corners of the barrier and is forwarded to an external node.

2. The lattice network reliable routing method based on physical perception information as claimed in claim 1, wherein in said step (2.1), the process that the border node calculates the optimal detour direction best _ dd by the control packet is as follows:

the exit node sends a control packet which comprises a cost field with an initial value of 0; if the boundary node receives the control packet and the forwarding target of the control packet is self or the forwarding path passes through self, accumulating the value stored in the cost field in the data packet and the distance of the source node relative to the self to obtain the detour cost new _ cost of the source direction of the control packet; at this time, if the node does not obtain the best detour direction best _ dd or the current best detour cost best _ cost is greater than the new _ cost, the new _ cost is used for updating the best _ cost, and the source direction of the control packet is used as the best _ dd;

and if the destination node of the control packet received by the boundary node is the boundary node, recording the new _ cost into a cost field of the control packet, and continuously forwarding the control packet.

3. The lattice network reliable routing method based on physical perception information as claimed in claim 1, wherein in the step (2.1), the control procedure of the ingress node for the forwarding direction dd in the data packet is as follows:

if best _ dd is not empty, if best _ dd is clockwise, the data packet dd is set to 1, and if best _ dd is counterclockwise, the data packet dd is set to-1 and is forwarded along the optimal direction of the obstacle edge; if best _ dd is empty, two copies of the packet are generated, and the dd fields are filled with 1 and-1, respectively, and are forwarded along two directions of the obstacle edge simultaneously.

Images