CN103108374B - A kind of energy-saving routing algorithm of mixed structure mine emergency management and rescue wireless mesh network - Google Patents

Abstract

The invention discloses an energy-saving routing algorithm of a mixed-structure mine emergency rescue wireless mesh network, which includes the following steps: step 1: setting node type information; step 2: dividing the communication status of Mesh wireless terminals into three types, namely ""Internal" state, "Edge" state, and "Repair"state; Step 3: Each Mesh terminal node maintains a list of Mesh backbone routing nodes; Step 4: If the first Mesh terminal is found to be in the "Internal" state, then directly according to the Mesh backbone routing node list; Routing node list information, select the neighbor backbone routing node with the closest distance to the gateway, and establish a route to the gateway.

Description

An Energy-Saving Routing Algorithm for a Mixed-structure Mine Emergency Rescue Wireless Mesh Network

technical field

The invention relates to the field of network technology, in particular to an energy-saving routing algorithm for a mixed-structure mine emergency rescue wireless mesh network.

Background technique

A wireless mesh network, also known as a wireless Mesh network, is a wireless multi-hop relay network that can realize self-organizing and self-configuring. The expansion of wireless mesh network does not rely on wired infrastructure, and it can quickly form a network. It has application characteristics such as flexibility, portability, and strong environmental adaptability. It is an advantageous technology for building a wireless communication network for emergency rescue in coal mines. Among them, the underground emergency rescue wireless mesh network based on the hybrid mesh network structure has become a research hotspot because of its high network path redundancy and strong transmission robustness. The wireless mesh network structure for coal mine emergency rescue based on the hybrid mesh network structure is shown in Figure 1.

In the mine emergency rescue wireless Mesh network based on the hybrid mesh network structure, the wireless Mesh terminal has the same routing and forwarding function as the Mesh backbone routing node. Since the existing wireless mesh network routing protocols do not distinguish between network node types, wireless Mesh terminals need to undertake additional routing and forwarding tasks on the basis of performing their application functions, which puts higher requirements on the energy configuration of wireless Mesh terminals. In the underground emergency rescue scenario, the energy reserve of wireless terminal equipment is low, and the terminal energy consumption problem seriously restricts the working hours of the mine emergency rescue communication system.

Contents of the invention

The technical problem solved by the present invention is to provide a routing algorithm based on which the relay energy consumption of wireless Mesh terminals in the network can be reduced as much as possible on the premise of ensuring the routing efficiency of the mine emergency rescue wireless mesh network.

The embodiment of the present invention discloses an energy-saving routing algorithm for a wireless mesh network for mine emergency rescue with a hybrid structure, including the following steps:

Step 1: Set the node type information, denoted as T, and stipulate that T=1 means the Mesh backbone routing node, and T=2 means the wireless Mesh terminal node;

Step 2: Divide the communication status of the Mesh wireless terminal into three types, namely "internal" status, "edge" status and "repair" status. The "internal" status refers to the reachable gateway within the communication range of the Mesh terminal The situation of the backbone routing nodes; the "edge" state refers to the scene that does not contain any Mesh backbone routing nodes within the communication range of the Mesh terminal; the "repair" state refers to the Mesh backbone within the communication range of the Mesh terminal Routing nodes, but these backbone routing nodes fail or are disconnected from the gateway;

Step 3: Each Mesh terminal node maintains a Mesh backbone routing node list, which records the address, validity period, and hop count information of the backbone routing nodes within the communication range of the current Mesh terminal; if the Mesh backbone routing node of the Mesh terminal When the list is empty, it means that the current node is in the "edge" state; if it is not empty, and there are backbone routing neighbor nodes that can reach the gateway, it means that the current node is in the "internal" state; otherwise, it means that the current node is in the "repair" state state;

Step 4: If it is found that the first Mesh terminal is in the "internal" state, then directly select the neighbor backbone routing node with the closest distance to the gateway according to the Mesh backbone routing node list information, and establish a route to the gateway.

Further, as preferably, after said step 4, the following steps are also included:

If it is found that the first Mesh terminal is in the "edge" state, it will start the route discovery mechanism based on the request-response mode, generate a RREQ message and broadcast it to the outside;

The second Mesh terminal receiving the RREQ information checks the local state, and if the check result is "internal" state, first update the reverse route from the second Mesh terminal to the first Mesh terminal and the previous hop node according to the RREQ message, and then according to Generate an RREP for the routing information that reaches the gateway by itself, and send it to the first Mesh terminal along the reverse path; if the check result is "edge" or "repair", first update the second Mesh terminal to reach the first Mesh according to the RREQ message The terminal and the reverse route of the previous hop node, and then set the path weight of the link type, and update the node type information, request type message, hop number, path weight of the link type and related information in the RREQ message on the second Mesh terminal Address serial number information, and broadcast the updated RREQ message to the outside.

Further, as preferably, after said step 4, the following steps are also included:

If it is found that the first Mesh terminal is in the "repair" state, it will start the route discovery mechanism based on the request-response mode, generate a RREQ message and broadcast it to the outside;

If the receiving node is the second Mesh terminal, the second Mesh terminal that receives the RREQ information checks the local state, if the check result is "internal" state, then firstly update the second Mesh terminal according to the RREQ message to reach the first Mesh terminal and the upper Reverse routing of one-hop nodes, and then generate an RREP according to the routing information of itself to the gateway, and send it to the first Mesh terminal along the reverse path; if the check result is "edge" or "repair" state, first according to RREQ The message updates the reverse route from the second Mesh terminal to the first Mesh terminal and the previous hop node, then sets the path weight of the link type, and updates the node type information, request type message, and hop count in the RREQ message on the second Mesh terminal , the path weight of the link type and the relevant address serial number information, and broadcast the updated RREQ message to the outside;

If the receiving node is a backbone routing node, first update the reverse route from the second Mesh terminal to the first Mesh terminal and the previous hop node according to the RREQ message, and then update the node type information and hop count in the RREQ message on the second Mesh terminal , the path weight of the link type, and the relevant address sequence number and other information, and continue to broadcast the updated RREQ message to the outside.

The present invention reduces the use probability and broadcast range of RREQ routing request messages by adopting a "state"-based routing selection mechanism, reduces the energy overhead of Mesh terminals for relaying and broadcasting RREQ messages, and simultaneously reduces routing discovery requests in the network Bandwidth overhead increases routing efficiency and improves network throughput performance, stability and real-time performance.

Description of drawings

A more complete and better understanding of the invention, and many of its attendant advantages, will readily be learned by reference to the following detailed description when considered in conjunction with the accompanying drawings, but the accompanying drawings illustrated herein are intended to provide a further understanding of the invention and constitute A part of the present invention, the exemplary embodiment of the present invention and its description are used to explain the present invention, and do not constitute an improper limitation of the present invention, wherein:

Figure 1 is a structural diagram of a mine emergency rescue wireless network based on a hybrid mesh network structure.

Figure 2(a) is an example diagram of route discovery when the terminal communication status is "internal".

Figure 2(b) is an example diagram of route discovery when the terminal communication status is "edge".

Figure 2(c) is an example diagram of route discovery when the terminal communication status is "repair".

Figure 3 shows the format of the HELLO message in the RAODV protocol.

Figure 4 shows the message format of RREQ in RAODV.

Figure 5 is a network throughput performance simulation curve.

Fig. 6 is a network end-to-end delay performance simulation curve.

Detailed ways

Embodiments of the present invention will be described with reference to FIGS. 1-6.

In order to make the above objects, features and advantages more comprehensible, the present invention will be further described in detail below in conjunction with the accompanying drawings and specific embodiments.

According to the application characteristics of the wireless terminal mainly communicating with the gateway in the mine emergency rescue communication scene, the design of the present invention is based on the following application background:

● All Mesh terminals only communicate with the gateway;

● A proactive routing protocol is used between the Mesh backbone routing node and the gateway, and any backbone routing node maintains the routing information to the gateway on a daily basis.

The on-demand distance vector routing protocol (ad hoc on demand distance vector routing, AODV) is the most widely used routing protocol in wireless mesh networks, and some studies have shown that compared with routing protocols such as DSR and OLSR, the transmission of this protocol in the coal mine environment The performance is the best. Accordingly, the present invention extends the route discovery and route repair mode based on the request-response mechanism in the AODV routing protocol, and designs a specific routing mechanism for the purpose of reducing the routing and forwarding tasks of wireless Mesh terminals. , so the present invention is also called the improved

AODV routing protocol, referred to as RAODV routing protocol. The basic routing principle of the protocol is as follows:

According to the communication state of the wireless Mesh terminal, the present invention divides the communication state of any wireless terminal in the mine emergency rescue wireless mesh network into three types, namely "internal" state, "edge" state and "repair" state, respectively as follows Shown in Figures 2(a), 2(b) and 2(c). On this basis, RAODV defines the routing discovery methods of Mesh terminals in different states.

The "internal" state refers to the situation that there are backbone routing nodes with reachable gateways within the communication range of the current Mesh terminal. At this time, the Mesh terminal using ROADV will adopt a communication method similar to the AP mode, directly access the backbone transmission network through the backbone routing node, and then use the backbone transmission network to realize information interaction with the gateway. This method avoids routing discovery by broadcasting a route request message (Route Request, RREQ), thereby reducing the relay broadcast energy consumption of the RREQ message by the Mesh terminal. The terminal node S in Figure 2(a) is in the "internal" state, and the path established with the gateway D by using the RAODV routing strategy is shown by the solid arrow in the figure, and it can be seen that the path does not include the Mesh terminal node.

The "edge" state refers to the scenario where the communication range of the Mesh terminal does not contain any Mesh backbone routing nodes. At this time, the Mesh terminal cannot directly access the backbone transmission network through the Mesh backbone routing node. It is necessary to enable the route discovery mechanism based on the request-response mode, broadcast the RREQ request message to the outside, and access the backbone transmission network through the use of adjacent wireless Mesh terminals. . As shown in Figure 2(b), the node S is the "edge" node. Under the RAODV strategy, it broadcasts the RREQ routing request to the outside. When the request reaches the Mesh terminal R, since R is in the "internal" state, R will stop RREQ continues to broadcast, and returns to S the transmission path through which it accesses the backbone transmission network, and the finally established path is shown by the solid arrow in the figure.

The "repair" state means that the communication range of the Mesh terminal contains Mesh backbone routing nodes, but these backbone routing nodes fail or are disconnected from the gateway, as shown in Figure 2(c). At this time, the Mesh terminal using the RAODV routing strategy also enables the route repair mechanism based on the request-response method, broadcasts the RREQ message, and selects the path with the least number of Mesh terminals among the discovered paths as the final route back to the source node S , the final established path is shown by the solid arrow in the figure.

In order to realize the routing process in the above different "states", RAODV has made the following improvements to the content of the routing protocol of AODV.

①In order to enable the routing selection process to identify the node type, RAODV introduces the node type information into the original AODV routing mechanism, denoted as T, and stipulates that T=1 means the Mesh backbone routing node, and T=2 means the wireless Mesh terminal node.

②In order to obtain the communication status of the current Mesh terminal conveniently, RAODV adds a Mesh backbone routing node list on the basis of the original neighbor list, and its data structure is as follows:

Each Mesh terminal node maintains a Mesh backbone routing node list, which records information such as the address of the backbone routing node within the communication range of the current Mesh terminal, the validity period, and the number of hops to the gateway. If the Mesh backbone routing node list of the current Mesh terminal is empty, it means that the current node is in the "edge" state; if it is not empty, and there are backbone routing neighbor nodes that can reach the gateway, it means that the current node is in the "internal" state ; Otherwise, the current node is in the "repair" state.

③The list of Mesh backbone routing nodes is maintained through HELLO messages. The original HELLO message in AODV does not distinguish between node types, and does not transmit the hop count information of the local gateway. In order to establish the Mesh backbone routing node list, RAODV took out 2 bits from the reserved field of the original HELLO message to indicate the node type information, as shown in Figure 3; at the same time, it stipulates that when T=1, the "hop count" in the HELLO message " field is equal to the hops to the gateway locally, so that the transmission of the node type and the hops to the gateway is realized without increasing the size of the HELLO packet. When receiving the HELLO message with T=1, the Mesh terminal will maintain and update the local Mesh backbone routing node list according to the message information.

④In order to enable the request-response based routing discovery mechanism to identify different communication "states", RAODV takes 8 bits from the "reserved field" in the RREQ message of AODV to indicate the request type information rq_mode, as shown in Figure 4 , and stipulate that rq_mode=0x00 means "internal" state, rq_mode=0x01 means "edge" state, and rq_mode=0x02 means "repair" state. When the RREQ arrives at a Mesh terminal node, its rq_mode value will be updated according to the state of the Mesh terminal; when the RREQ message arrives at a backbone routing node, its rq_mode value will not change.

⑤ In order to avoid the use of Mesh terminals for routing relay in the routing discovery process based on the request-response method, RAODV proposes a routing criterion based on link type, which is denoted as rt_weight, and the rt_weight of each backbone transmission link is equal to 1/3, and the rt_weight of other non-backbone transmission links connected to Mesh terminals is equal to 1.

⑥In order to enable the RREQ message to identify the type of link passed and record the rt_weight value of the path passed, RAODV added two fields of sending node type T and rt_weight to the original AODV RREQ message, as shown in Figure 4. When the type of the current node and the T field in RREQ are both displayed as Mesh backbone routing nodes, it means that the last hop link of RREQ is a backbone transmission link. In this case, increase rt_weight by 1/3; otherwise, increase rt_weight by 1. By selecting the path with the smallest rt_weight value, the number of Mesh terminals included in the data transmission path is effectively reduced. In Figure 2(c), the solid arrow and the dotted arrow respectively indicate the path selected by RAODV using rt_weight as the routing criterion and the path selected by AODV based on the hop criterion. As shown in the figure, the path selected by RAODV Minimize the number of Mesh terminal relay nodes in the transmission path. Therefore, the routing and forwarding task of the Mesh terminal in data transmission is reduced, and the energy of the Mesh terminal is saved.

The specific implementation process of the RAODV routing protocol of the present invention is described below in conjunction with FIG. 2 .

Assuming that in the mine emergency rescue wireless mesh network, any Mesh terminal S wants to communicate with gateway D, but finds that there is no valid routing information to D in the local routing table, then node S will check the local Mesh backbone routing node list Check local status:

If it is found that it is currently in the "internal" state, it will directly select the neighbor backbone routing node with the closest distance to the gateway according to the Mesh backbone routing node list information, establish a route to the gateway, and then upload the information to the backbone transmission network. The transmission path established in this case is shown in Fig. 2(a).

If it is found that the local is in the "edge" state or "repair" state, it will start the route discovery mechanism based on the request-response mode, generate a RREQ message and broadcast it to the outside.

After any node in the mine emergency rescue WMN receives this RREQ message, it will perform the following operations.

① Check the rq mode of the RREQ message.

If {rq_mode=0x01}, it indicates that the last hop wireless Mesh terminal node is in the "edge" state, so the node receiving RREQ can only be a Mesh terminal. The Mesh terminal receiving the RREQ message checks the local status. If the inspection result is "internal" status, then execute step ②; if it is "marginal" status or "repair" status, then execute step ③.

If {rq_mode=0x02}, it indicates that the Mesh terminal node of the previous hop is in the "repair" state. At this time, the receiving node may be a Mesh terminal node or a backbone routing node. If the receiving node is a Mesh terminal, the processing method is the same as the above {rq_mode=0x01}, that is, perform step ② or step ③ according to the local state; if the receiving node is a backbone routing node, perform step ④.

② First, update the local reverse route to the source node S and the previous hop node according to the RREQ message, and then generate an RREP according to the route information of itself to the gateway, and send it to S along the reverse path.

③First update the local reverse route to the source node S and the previous hop node according to the RREQ message, then locally update the T, rq_mode, hop count, rt_weight and related address serial number information in the RREQ message, and update the updated The RREQ message is broadcast outward.

④ First update the local reverse route to the source node S and the previous hop node according to the RREQ message, and then update the T, hop count, rt_weight and related address serial number information in the RREQ message locally, and the backbone routing node does not update the rq_mode information , and continue to broadcast the updated RREQ message to the outside.

Comparing the transmission paths of RAODV and AODV in Figure 2 shows that the RAODV routing strategy successfully reduces the relay and forwarding tasks of Mesh terminals in the mine emergency rescue WMN network under Mesh terminal mode, and effectively solves the energy consumption problem of Mesh terminals under this mode. It is not difficult to find that the larger the deployment scale of the WMN network for mine emergency rescue, the more Mesh terminals can be exempted from undertaking additional RREQ broadcasts and routing and forwarding tasks for data packets, and the energy-saving advantages of RADOV will be more obvious. Simulation results:

Assume that the transmission capacity of the backbone transmission network of the mine emergency rescue wireless Mesh network is C, and the traffic generated by the Mesh terminal is F. The network capacity of the mine emergency rescue WMN based on the Mesh terminal mode includes the transmission bandwidth of the Mesh terminal, so the overall capacity of the emergency rescue WMN is higher than the transmission capacity C of the backbone transmission network. The AODV routing protocol does not distinguish between node types, so in theory, AODV can make full use of the bandwidth resources of Mesh terminals than RAODV. However, in practical applications, is the W-URN throughput performance using RAODV lower than that of the network using AODV? To solve this problem, two different communication scenarios of F>C and F<C are deliberately set up in the simulation, and the transmission performance of RAODV under the conditions of F>C and F<C is compared and analyzed. In order to verify the routing recovery capability of RAODV, a scenario where any backbone routing node fails at 30 seconds is also set in the simulation.

Figure 5 shows the simulation results of network throughput when the RAODV routing protocol is used. The results show that when F>C, RAODV will not reduce the throughput performance of the network because of avoiding the use of Mesh terminals for routing relay. On the contrary, due to RAODV The broadcast bandwidth overhead of RREQ is reduced, and compared with AODV, the throughput and transmission stability of the mine emergency rescue wireless Mesh network are improved;

Fig. 6 is the simulation result of network average end-to-end time delay when the RAODV routing protocol is adopted. As shown in the figure, when F<C, there are two obvious differences between the delay curves of RAODV and AODV, that is, there are two obvious jumps in the delay curves of AODV at 0 seconds and 30 seconds. 0 seconds and 30 seconds are the initial moments of route discovery for the first time and route restoration after an accident, respectively, so the jump delay reflects the route convergence time of the corresponding routing strategy. It can be seen from the simulation results that the route convergence delay of RAODV is much lower than that of AODV. The reason for this gap is that the RREQ message of RAODV is mainly forwarded by the Mesh backbone routing nodes. The network complexity of the Mesh backbone transmission network is greatly reduced compared with the complexity of the entire mine emergency rescue Mesh network, thus effectively reducing the RREQ message in the network. The transmission interference encountered during the broadcast process and the return of the routing response message, so that the connection between the source node and the destination node can be quickly established.

The simulation curves after 30 seconds in Fig. 5 and Fig. 6 show the simulation results of network throughput and average end-to-end delay when the backbone routing node fails. The simulation results show that when an accident occurs, the transmission stability of RAODV is obviously higher than that of AODV, especially when F<C, the recovery delay of RAODV is only 1/4 of that of AODV, and it has a fast route recovery capability.

Although the specific embodiments of the present invention have been described above, those skilled in the art should understand that these specific embodiments are only for illustration, and those skilled in the art can make the above-mentioned Various omissions, substitutions, and changes were made in the details of the methods and systems. For example, it is within the scope of the present invention to combine the above method steps so as to perform substantially the same function in substantially the same way to achieve substantially the same result. Accordingly, the scope of the invention is limited only by the appended claims.

Claims (1)

1. A kind of energy-saving routing algorithm of mixed structure mine emergency rescue wireless mesh network, it is characterized in that, comprises the following steps: Step 1: Set the node type information, denoted as T, and stipulate that T=1 represents the Mesh backbone routing node, and T=2 represents the wireless Mesh terminal node; Step 2: Divide the communication status of the Mesh wireless terminal into three types, namely "internal" status, "edge" status and "repair" status. The "internal" status refers to the reachable gateway within the communication range of the Mesh terminal The scenario of the backbone routing node; the "edge" state refers to the scenario that does not contain any Mesh backbone routing node within the communication range of the Mesh terminal; the "repair" state refers to the Mesh backbone routing node within the communication range of the Mesh terminal , but these backbone routing nodes fail or are disconnected from the gateway; Step 3: Each Mesh terminal node maintains a Mesh backbone routing node list, which records the address, validity period, and hop count information of the backbone routing nodes within the communication range of the current Mesh terminal; if the Mesh backbone routing node of the Mesh terminal When the list is empty, it means that the current node is in the "edge" state; if it is not empty, and there are backbone routing neighbor nodes that can reach the gateway, it means that the current node is in the "internal" state; otherwise, it means that the current node is in the "repair" state state; Step 4: If the first Mesh terminal is found to be in the "internal" state, then directly select the neighbor backbone routing node closest to the gateway according to the Mesh backbone routing node list information, and establish a route to the gateway; If it is found that the first Mesh terminal is in the "edge" state, it will start the route discovery mechanism based on the request-response mode, generate a RREQ message and broadcast it to the outside; The second Mesh terminal that receives the RREQ information checks the local state, if the check result is "internal" state, firstly update the reverse route from the second Mesh terminal to the first Mesh terminal and the previous hop node according to the RREQ message, and then according to Generate an RREP for the routing information that reaches the gateway by itself, and send it to the first Mesh terminal along the reverse path; if the check result is "edge" or "repair", first update the second Mesh terminal to reach the first Mesh according to the RREQ message The terminal and the reverse route of the previous hop node, and then set the path weight of the link type, and update the node type information, request type message, hop number, path weight of the link type and related information in the RREQ message on the second Mesh terminal Address the serial number information, and broadcast the updated RREQ message to the outside; if the first Mesh terminal is found to be in the "repair" state, it will start the route discovery mechanism based on the request-response mode, generate the RREQ message and broadcast it to the outside; If the receiving node is the second Mesh terminal, the second Mesh terminal that receives the RREQ information checks the local state, if the check result is "internal" state, then firstly update the second Mesh terminal according to the RREQ message to reach the first Mesh terminal and the upper Reverse routing of one-hop nodes, and then generate an RREP according to the routing information of itself to the gateway, and send it to the first Mesh terminal along the reverse path; if the check result is "edge" or "repair" state, first according to RREQ The message updates the reverse route from the second Mesh terminal to the first Mesh terminal and the previous hop node, then sets the path weight of the link type, and updates the node type information, request type message, and hop count in the RREQ message on the second Mesh terminal , the path weight of the link type and the relevant address serial number information, and broadcast the updated RREQ message to the outside; If the receiving node is a backbone routing node, first update the reverse route from the second Mesh terminal to the first Mesh terminal and the previous hop node according to the RREQ message, and then update the node type information and hop count in the RREQ message on the second Mesh terminal , the path weight of the link type, and the relevant address sequence number and other information, and continue to broadcast the updated RREQ message to the outside.