CN101568164A - Opportunistic routing algorithm of Ad hoc network based on node priority levels - Google Patents

Abstract

The invention proposes an Ad hoc network opportunity routing algorithm based on node priority. This method establishes a forwarding list of intermediate nodes between the source node and the sink node through the routing request message and the routing response message, and the nodes in the forwarding list are prioritized according to the distance from the sink node in the routing response message, and the closer to the sink node is preferred The higher the level, the forwarding list is carried at the head of the data packet, and the intermediate nodes in the forwarding list have the opportunity to forward the received data packet. By setting the sequence number of the packet to avoid broadcast storms, and by comparing priorities to avoid certain The repeated forwarding of data packets improves the success rate of information transmission through more than one next-hop node forwarding node. In the case of poor channel quality, the opportunistic routing mechanism can make full use of forwarding nodes closer to the destination node for forwarding, which can ensure a high delivery rate and a small end-to-end delay.

Description

Opportunistic Routing Algorithm Based on Node Priority in Ad hoc Networks

technical field

The invention relates to a routing mechanism of a wireless multi-hop self-organizing network, in particular to the realization of a node priority-based opportunistic routing algorithm.

Background technique

Typical routing protocols currently appearing in Ad hoc networks include DSR, AODV, OLSR, etc. The implementation mechanism of traditional routing is to select the best path between the source and sink nodes, and then forward data packets sequentially along the selected path. When the link condition is relatively good, the traditional routing mechanism can work very well. However, the instability of the wireless channel often leads to instantaneous changes in the transmission range of the node, and the movement or power-on/off of the node will also cause the next-hop node to be unreachable, which will lead to frequent confirmation and retransmission of the MAC layer. Then it causes the route maintenance process or route update process at the routing layer. This phenomenon is even more serious when the quality of the wireless channel deteriorates or the mutual distance between nodes is just in the critical coverage range. The unreliability and instability of this link will lead to a large route maintenance cost, and will also cause a large delay or a large amount of packet loss in the upper-layer business.

The opportunistic routing algorithm can better solve the above problems, and it can maintain a high delivery rate and a small delay in the case of poor wireless network channel quality and frequent network topology changes, thereby better supporting QoS requirements.

In the opportunistic routing algorithm, data packets are broadcasted within the range of intermediate nodes defined by the forwarding list. The forwarding list is prioritized according to the distance to the destination node. The closer the distance to the destination node, the higher the priority. All nodes in the forwarding list that receive the data packet have the opportunity to forward the packet, and the low-priority node will not forward the data packet sent by the high-priority node, which will force the data packet to be transmitted in the direction of the destination node. And there is more than one next-hop node for each forwarding, which increases the success rate of forwarding. Opportunistic routing can make full use of those very "lucky", long-distance links. It can also give those "unfortunate" nodes that are very close to each other a new teleportation opportunity.

Contents of the invention

The object of the present invention is to provide a routing method of opportunistic forwarding, which can make full use of all available node resources in the network, especially those nodes that are closer to the sink node to forward data, so as to achieve higher delivery rate and lower delivery rate. delay. To achieve the above object, the present invention takes the following steps to realize:

Step 1: Construction and maintenance of forwarding list

When the node has data to transmit, the routing request and response process is started, and the routing request message is sent in a flooding manner, and the intermediate node can forward the same routing request message n times (n is determined according to the size of the network), and the routing request message The intermediate nodes it passes through are recorded in , and each time the sink node receives a routing request message, it obtains a reverse route according to the intermediate node information recorded therein, and unicasts back a routing response message. After receiving the routing reply message, the source node constructs a forwarding list according to the intermediate node information in it. The forwarding list is prioritized, and the forwarding list is dynamically updated according to the received routing reply message. The forwarding list is carried to the header of the data packet and forwarded together with the data packet.

Step 2: Priority setting of the forwarding list

The intermediate node information in the routing response message contains the node address, and the number of hops from each intermediate node to the sink node can be obtained, and the priority of the intermediate node is set according to the number of hops to the sink node. The node that is one hop away from the sink node is the highest priority, the two-hop node is the second priority, and so on, a total of 8 priorities are arranged, and the number of nodes in each priority does not exceed 15. If the same intermediate node gives different priorities according to the hops away from the destination node in the subsequent routing reply message, the higher priority is always taken.

The third step: the mechanism of intermediate nodes for data forwarding

Add the sequence number field and the last hop node address field in the header of the data packet. After the intermediate node receives a data packet, it judges whether it is in the forwarding list. If not, it discards the data packet. If it is, it judges whether the packet is sent by a node with a higher priority. If it is, it discards it. , if it is sent by a node with the same or lower priority, judge whether the packet has already been forwarded, if so, discard it, if not, write its own address into the previous hop node field and continue forwarding the packet Bag.

Description of drawings

Figure 1 is an example of a network topology diagram.

Figure 2 shows the packet structure.

Figure 3(a)(b)(c)(d) respectively show the overall process of receiving packets, the process of receiving routing request packets, the process of receiving routing response packets and the process of receiving and forwarding data packets.

Detailed ways

The present invention will be further described below in conjunction with examples, but these examples should not be construed as limiting the present invention.

Establishment of forwarding list: When a node has data to send, it constructs a routing request message RREQ, which mainly includes source IP address, destination IP address, and RREQ ID. RREQ transmits in the mode of flooding, and the passing intermediate node writes its IP address in the forwarding list field in the RREQ successively, and the intermediate node can forward multiple times to the message of the same RREQ ID (set according to the network scale, in the present invention In the network example, this value is set to 3), so that the sink node will receive multiple RREQs, and each time the sink node receives a RREQ, it will construct a corresponding routing response RREP message. The RREP message mainly includes the source IP address and the destination IP address. Forwarding list field. RREP obtains a reverse route and unicasts it back to the source node according to the forwarding list in RREQ. Like this, for the RREQ message of identical RREQ ID, sink node can reply a plurality of RREP messages, and source node builds local forwarding list and sets priority according to the node information in a plurality of RREPs.

Priority setting process: save a RREP linked list at the source node, record all nodes in the forwarding list and their corresponding priorities, and set the upper limit of priority levels to 8. The linked list has the following content: the node IP address and its hops to the destination node, and the linked list is updated each time an RREP is received. When the maximum number of RREPs to be processed is reached, subsequent RREP messages are not processed (the value is set to 7 in the network example of the present invention). The update process is as follows:

As shown in Figure 1 and Table 1, assuming that the source node receives seven RREPs within a limited time, the forwarding node information contained in the first RREP received is: {(N4, 1hop)(N2, 2hop) }, when assigning priority, because there is no entry in the forwarding list, the priorities of N4 and N2 are directly assigned to 1 and 2 respectively;

Receive the forwarding node information contained in the second RREP as {(N6, 1hop)(N1, 2hop)}. When assigning priority, first check whether the same node already exists in the forwarding list. Give priority, if it exists, give priority according to the hops from the sink node in this RREP first, then compare it with the priority given in the forwarding list, if they are different, give this node a higher priority, because at this time N6 and N1 do not exist in the forwarding list, so N6 and N1 are given priority 1 and 2 respectively;

The forwarding node information received in the third RREP is {(N7, 1hop)(N6, 2hop)(N4, 3hop)}, because nodes N6 and N4 already exist in the forwarding list, and their priority is the highest, so The priorities of N6 and N4 remain unchanged, and the priority of N7 is set to 1;

The forwarding node information received in the fourth RREP is {(N7, 1hop)(N5, 2hop)(N3, 3hop)}, according to the priority arrangement method, the priority of N7 remains unchanged, and N5 and N3 are given priority respectively is 2, 3;

The forwarding node information in the fifth RREP is received as {(N6, 1hop)(N1, 2hop)(N2, 3hop)}, and the priorities of N6, N1, and N2 remain unchanged;

The forwarding node information received in the sixth RREP is {(N7, 1hop) (N5, 2hop) (N4, 3hop) (N1, 4hop) (N2, 5hop) (N3, 6hop)}, according to the priority method , the priority of these six nodes is the highest priority ever, so the priority in the forwarding list is also unchanged.

The forwarding node information received in the seventh RREP is {(N7, 1hop) (N4, 2hop) (N5, 3hop) (N3, 4hop) (N2, 5hop)}, arranged according to the priority method, these five nodes The priority of is taken from the previous highest priority, therefore, the priority in the forwarding list remains unchanged. At this time, the priorities in the forwarding list are: priority 1: {N4, N6, N7}, priority 2: {N2, N1, N5}, priority 3: {N3}.

Table 1 Priority setting process of forwarding list

When a node has a data packet to send, it first checks the local forwarding list. If there is no forwarding node information, it initiates the process of establishing the forwarding list. This process is completed by the first two steps. The construction of the forwarding list has a timeout period, which exceeds this time Finally, regardless of whether all RREPs have been collected, the sending process of the data packet will be started, and the forwarding list will be attached to the header of the data packet when the data packet is sent.

In order to avoid broadcast storms, a serial number field is added in the option header of the forwarding list, where the serial number field ranges from 0 to 2 ³² -1 and is used cyclically. The node keeps a linked list indexed by (source, sink, serial number) locally, and saves the (source, sink, serial number) information of the package after receiving a packet. In order to reduce the number of redundant packets and ensure that the data packets are always forwarded in the direction closer to the destination node, a last-hop node field is added to the header of the data packet. The structure of the data packet is shown in Figure 2.

Data packet forwarding process: as shown in Figure 3, after a node receives a data packet, if it is not the sink node, it first judges whether it is in the forwarding list of the data packet, if not, then discards the data packet, if in , then compare whether the packet is sent by a node with a higher priority than your own according to your own priority in the forwarding list and the priority of the last hop node of the packet, and if so, discard the data packet, and If the data packet with the sequence number is waiting to be processed in the local maintenance cache, delete the data packet in the cache at the same time. If the data packet comes from the same priority or low priority node, check whether you have received the data packet, and if so, discard it. If not, cache the data packet and wait regularly. The waiting time is determined by its The priority is determined. The higher the priority, the shorter the waiting time. If a packet with the same sequence number forwarded by a higher priority node is received during the timing period, the packet will be deleted and the timer will be deleted. Otherwise, write its own address into the last hop node field in the option header when the timing is up, record the sequence number of the data packet and forward the data packet.

The content not described in detail in this specification belongs to the prior art known to those skilled in the art.

The above is only a preferred implementation of the present invention, and is not intended to limit the present invention. Any modifications, equivalent replacements, improvements, etc. made within the spirit and principles of the present invention should be included in the protection of the present invention. within range.

Claims (6)

1, a kind of opportunistic routing algorithm based on node priority for Ad hoc network, its steps are as follows: A) Periodically obtain a list of effective forwarding nodes between the source and sink nodes in the network during the sending of the data packet; B) The source node sets the priority of the collected effective forwarding nodes, so that they are prioritized according to the distance from the sink node; C) the source node attaches the forwarding list of the set priority to the header of the data packet, and then broadcasts the data packet; D) the forwarding order of the node to the data packet is carried out according to its priority in the forwarding list; E) A sequence number field is added to the header of the data packet to limit the node to only forward the same packet once. 2. The method according to claim 1, wherein step A further comprises: the process of collecting the list of intermediate effective forwarding nodes when the node has data to send; the forwarding list is based on the intermediate forwarding nodes included in the routing response message To build; when there is data to send, the forwarding node list is obtained periodically, and the cycle can be set to different values according to different scenarios. In the scenario where the topology is relatively stable, this value can be set very long (minutes), and the topology In scenes with frequent changes, this value should be set shorter. 3. The method according to claim 1, characterized in that step B further comprises: the nodes in the local forwarding list are prioritized according to the hop count of the forwarding node contained in the routing response message, and the distance from the destination node is hops The lower the number, the higher the priority. There can be multiple nodes with the same priority. 4. The method according to claim 1, characterized in that step C further comprises: the forwarding list is carried to the header of the data packet and forwarded together with the data packet. 5. The method according to claim 1, characterized in that step D further comprises: the nodes in the forwarding list have the opportunity to forward the received data packets, wherein the nodes with the same priority or low priority The data packets sent by the priority nodes that have not been forwarded by themselves are forwarded, and the low-priority nodes no longer forward the data packets sent by the high-priority nodes. 6. The method according to claim 1, wherein step E further comprises: the source node adds a sequence number field to the header of the data packet to uniquely identify a data packet at the network layer, which can avoid broadcast storms.

Images