CN1299478C - Route searching of detgredd of node based on radio self-organizing network and maitenance method thereof - Google Patents

Abstract

The route search and maintenance method based on node degree in wireless ad hoc network belongs to wireless communication network technology, and its characteristic is that it starts from the statistical characteristics of node degree and proposes a routing criterion that considers node competition and congestion conditions , so that the nodes choose those routes with few competing nodes as the transmission routes of the data packets, so that the data packets have a higher delivery rate and a shorter delay. When choosing which routing parameters to use, the requirements of the upper-layer service characteristics should be considered. In addition, it can be easily embedded into existing routing algorithms. The routing method using the routing criterion proposed by the invention has the advantages of simplicity, high efficiency, and fair node energy consumption.

Description

Node-based degree-based routing search and maintenance method in wireless ad hoc networks

technical field

The invention relates to a node-based route search and maintenance method in a wireless self-organizing network, that is, an Ad Hoc network, and belongs to the technical field of wireless communication networks.

Background technique

At present, various communication and network technologies are developing rapidly, especially the use of wireless communication networks has gradually matured, including various wireless cellular communication networks (such as: GSM, WCDMA, CDMA2000, etc.), wireless local area networks (such as: IEEE 802.11 series Standard, European HiperLAN standard, etc.) and the wireless self-organizing network (AdHoc network) that is increasingly attracting the attention of the industry and academia. Wireless local area network (WLAN) and Ad Hoc network are generally considered to be a beneficial part of the entire wireless communication network in the future, in order to achieve convenient, high-speed and effective wireless access. Ad Hoc network can be used as a way to realize wireless access in the future, and it can also self-organize to form a wireless network alone. In this network, nodes can move randomly, and each node is both a source node and a destination node. At the same time, it also acts as a router, that is, pathfinding and forwarding the data packets flowing through the local node. Because the construction of Ad Hoc network is very simple and convenient, it is very suitable for military applications, meeting places, student classrooms, flood fighting and disaster relief, earthquake rescue and some emergencies, and it can quickly provide people with a reliable and effective A wireless communication network without the need to pre-build any communication infrastructure.

For the Ad Hoc network, in order to realize that any two nodes in the network can communicate normally, it is necessary to design a good routing algorithm to realize the routing function. The various time-varying characteristics of Ad Hoc networks, such as: changes in wireless channels, changes in network topology, changes in upper-layer services, changes in node battery energy, etc., make the design of routing algorithms face major challenges. In the routing algorithms that have been proposed, most of them use the shortest path as the routing criterion, such as: DSDV-Destination Sequenced Distance Vector Routing (DSDV-Destination Sequenced Distance Vector Routing), Ad Hoc On-demand Distance Vector Routing (AODV-Ad Hoc On- Demand Distance Vector Routing), dynamic source routing algorithm (DSR-Dynamic Source Routing), etc. In addition, some literatures also propose some routing criteria combined with other factors, such as: the signal strength between adjacent nodes, the relative stability between adjacent nodes, the power consumption of nodes, and the quality of service guarantee of business (Quality-of-Service). -Service), load balancing, etc., and some routing algorithms take several factors into consideration at the same time. However, these algorithms have the following disadvantages:

1) The congestion situation in the network is not considered;

2) Most nodes need to periodically send control information related to routing, which increases network overhead and further makes the network more congested;

3) Due to the lack of consideration of network congestion, the energy consumption distribution of nodes in the network is unfair, that is, some nodes may run out of energy prematurely due to heavy load, which will further aggravate the network topology. Variety;

4) For those load balancing routing algorithms that consider network congestion, most of them are based on the number of data packets in the node buffer (that is: the memory space used to save data) or the number of connections that are communicating (that is: The number of routes that are communicating) to represent the network load status. A consequence of this is that there is a coupling between the routing algorithm and the service, that is, the route selection result of the routing algorithm and the number of data packets or connections saved in the node buffer will affect each other. As a result, the network is unstable, and even the selected route may fluctuate. Especially when the upper layer business rate changes rapidly, the performance of these algorithms will be further degraded. The suddenness of business greatly increases the difficulty for these algorithms to handle network load. Moreover, most of these algorithms also require nodes to periodically send control information, which increases network overhead.

In order to make the routing algorithm work efficiently, the routing algorithm design in the Ad Hoc network should follow the following two principles:

1) simple;

2) Minimize network overhead as much as possible.

Contents of the invention

The purpose of the present invention is to provide a route search and maintenance method based on the degree of nodes in an Ad Hoc network with low network overhead, considering the competition situation of each node, and relatively simple search and maintenance.

The present invention is characterized in that: it is in the wireless transceiver equipment, i.e. node, also claims router, the wireless self-organization that constitutes, i.e. Ad Hoc, realizes successively in each mobile equipment in communication network by following steps:

Initialization setting: the type of data packet and the data items contained in it, and stored in the memory of each node:

1) The routing request packet, namely RREQ, contains the following data items:

The data packet type is represented by "Type"; the source node address is represented by "Src_Addr"; the destination node address is represented by "Dest_Addr"; the sequence number of the RREQ packet sent by the node is represented by "Seq_Num"; The lifetime of the data packet is represented by "TTL". According to the network scale, the preset maximum lifetime is MaxM+1, where MaxM is the maximum number of intermediate nodes that may be included in a route; the route length from the source node to the current node is represented by " "Cur_Len" means; the N-hop degree of the source node is represented by "Src_Degree". The existence of active nodes, so it is also equivalent to the number of active nodes within the above range, that is, the number of nodes that need to send data packets, generally N chooses 1 or 2; the N hop degree of the destination node is represented by "Dest_Degree", Among them, the definition of N hops is as above; the node address of the intermediate node that RREQ flows through is represented by "Addr_1～Addr_MaxM", where MaxM represents the maximum number of possible intermediate nodes in a route; various intermediate nodes that RREQ flows through The N-hop degree of a node is represented by "Degree_1~Degree_MaxM". Similarly, MaxM represents the maximum number of possible intermediate nodes in a route;

2) The route response data packet, namely RREP, contains the following data items: Type, Src_Addr, Dest_Addr, Seq_Num, Cur_Len, Src_Degree, Dest_Degree, Addr_1～Addr_X and Degree_1～Degree_X, where Addr_1～Addr_X constitutes a complete route, Degree_1～Degree_X represent the N-hop information of the nodes corresponding to Addr_1～Addr_X, and the definitions of other data items are as mentioned above, where X represents the number of intermediate nodes of the route contained in the RREP, and X is not greater than MaxM;

3) The routing failure data packet, namely RERR, contains the following data items: Type, Src_Addr, Dest_Addr, Cur_Len, Src_Degree, Dest_Degree, Addr_1~Addr_X, Degree_1~Degree_X, Error_Up_Addr, and Error_Down_Addr, where Type, Src_Addr, Dest_Addr, Src_Degree, Dest_Degree , Addr_1～Addr_X and Degree_1～Degree_X have the same meanings as mentioned above, and Cur_Len indicates the number of hops from the node where the error occurred to the current node; Error_Up_Addr indicates the node address that the next hop node cannot reach; Error_Down_Addr indicates the next node that cannot be reached The node address of the hop node;

4) The business data package contains the following data items: Type, Src_Addr, Dest_Addr, Cur_Len, Src_Degree, Dest_Degree, Addr_1～Addr_X, Degree_1～Degree_X, Traffic_Data and Alpha, among which Type, Src_Addr, Dest_Addr, Cur_Len, Src_Degree, Dest_Degree, Addr_1～ The meanings of Addr_X, Degree_1~Degree_X are as mentioned above, Traffic_Data represents the upper-layer business data of the business data packet; Alpha represents the user’s required parameters for the delay, packet loss rate, and bandwidth of the business data packet;

Set the following parameters and their related intermediate variables, and store them in the memory of each node respectively:

The timeout threshold of the path life, which means: if the node does not monitor any traffic flow data packets along the path during this period, the node considers the path to be invalid, so the path, that is, the route, is buffered from the route delete from the area;

Routing buffer, which refers to the storage space for storing routes in the memory of each node;

Data packet buffer, which refers to the storage space for storing upper layer business data packets in the memory of each node;

The maximum number of allowed sending times of business data packets preset by the network;

The maximum allowed number of nodes contained in a route preset by the network;

Design the following three algorithm programs for calculating the routing parameter RSM of a route, calculate the three routing parameters RSM ₁ , RSM ₂ and RSM ₃ , and store it together with the calculation program of the routing selection criterion in the memory of each node , the routing selection criterion refers to: when the α value is smaller, the RSM value is RSM ₃ , and a route to the destination node with the smallest RSM ₃ value is selected in the routing buffer; when the α value is smaller When it is large, the RSM value is selected from RSM ₁ or RSM ₂ , and when the RSM value is RSM ₁ , a route to the destination node with the smallest RSM ₁ value is selected in the routing buffer; the RSM ₁ , RSM ₂ and RSM ₃ are calculated as follows:

${\mathrm{<span\; class="notranslate">\; <figure-callout\; id="1"\; label="RSM"\; filenames="C20041000346600191.png"\; state="\{\{state\}\}">RSM</figure-callout></span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}<span\; class="notranslate">\; =</span>\underset{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 1</span>}}{\overset{\mathrm{<span\; class="notranslate">\; m</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}}{\mathrm{<span\; class="notranslate">\; D.</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; ,</span>$

${\mathrm{<figure-callout\; id="2"\; label="RSM"\; filenames="C20041000346600191.png,C20041000346600201.png"\; state="\{\{state\}\}">RSM</figure-callout>}}_2=(h+1)\sqrt{\frac{1}{m-1}\underset{i=1}{\overset{m}{\mathrm{\&Sigma;}}}{({\mathrm{D.}}_i-\stackrel{\&OverBar;}{\mathrm{D.}})}^2},$ in $\stackrel{\&OverBar;}{\mathrm{D.}}=\frac{1}{m}\underset{i=1}{\overset{m}{\mathrm{\&Sigma;}}}{\mathrm{D.}}_i,$

${\mathrm{<span\; class="notranslate">\; <figure-callout\; id="3"\; label="RSM"\; filenames="C20041000346600191.png,C20041000346600201.png"\; state="\{\{state\}\}">RSM</figure-callout></span>}}_{\mathrm{<span\; class="notranslate">\; 3</span>}}<span\; class="notranslate">\; =</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; h</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; [</span>\frac{\mathrm{<span\; class="notranslate">\; 1</span>}}{\mathrm{<span\; class="notranslate">\; m</span>}}\underset{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 1</span>}}{\overset{\mathrm{<span\; class="notranslate">\; m</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}}{\mathrm{<span\; class="notranslate">\; D.</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; \&alpha;</span>}\sqrt{\frac{\mathrm{<span\; class="notranslate">\; 1</span>}}{\mathrm{<span\; class="notranslate">\; m</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1</span>}}\underset{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 1</span>}}{\overset{\mathrm{<span\; class="notranslate">\; m</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}}{<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; D.</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; -</span>\stackrel{<span\; class="notranslate">\; \&OverBar;</span>}{\mathrm{<span\; class="notranslate">\; D.</span>}}<span\; class="notranslate">\; )</span>}^{\mathrm{<span\; class="notranslate">\; 2</span>}}}<span\; class="notranslate">\; ,</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 0</span>}<span\; class="notranslate">\; <</span>\mathrm{<span\; class="notranslate">\; \&alpha;</span>}<span\; class="notranslate">\; <</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; )</span>$

Among them, M is the number of nodes contained in a route; H is the number of hops contained in a route, H=M-1; D _i is the N-hop degree of the i-th node that the route flows through; D is the number of hops that the route flows through The average N-hop degree of M nodes; α is specified by the user in the service data packet. It is a parameter set by the user according to the delay, packet loss rate, and bandwidth of the data packet. At the same time, this parameter indicates that the upper layer business The degree of emphasis on the standard deviation of the total number of competing nodes of the route and the number of competing nodes of each node, 0<α<1, when the emphasis on the standard deviation is small, the value of α is smaller, otherwise, the value of α is smaller big;

The described routing search method contains the following steps in turn:

(1) When a node generates an upper-layer service data packet, the node becomes the source node. It first judges whether there is a data packet being sent, and if so, inserts the service data packet into the data packet buffer and waits for the data packet Send the current data packet after the packet is sent; if no data packet is being sent, it selects an effective route to the destination node from its own routing buffer according to the above RSM routing criterion;

(2) If there is no valid route starting from the node in the routing buffer of the node, the route search process is initiated, that is, the node fills its own address and N hops into the RREQ and sends it by broadcast; if it exists, it turns to Incoming route maintenance process;

(3) After the intermediate node receives the RREQ, it checks whether it has received the RREQ for the first time. If it is not the first time it receives the RREQ, it discards the RREQ and the search process ends; if it is the first time it receives the RREQ, the intermediate node sends its own address and N hops are filled into RREQ and forwarded;

(4) After the destination node receives the RREQ, it selects the best route according to the predetermined routing criteria in the memory and each RSM value of each path in the routing buffer. A path to the source node is formed by extracting the corresponding node address and N hops from RREQ;

(5) The destination node fills the best route information including each node address and N hops into the RREP and sends it to the source node;

(6) After receiving the RREP, the intermediate node of the best route updates the N-hop information of the node corresponding to itself in the RREP according to the N-hop degree of its own node, and forwards it to the upstream node of the route contained in the RREP;

(7) After the source node receives the RREP, it obtains an effective route from the source node to the destination node, and stores it in its own route buffer, and the route search process ends;

The described routing maintenance method contains the following steps in turn:

(1) The source node can obtain an effective route from the source node to the destination node according to the above step (7), or obtain an effective route from the routing buffer directly after the upper layer service data packet is generated in the above step (2). Routing, filling the node address and corresponding N-hop information into the current service data packet to be sent, and sending the service data packet;

(2) If the source node finds that its downlink cannot communicate normally, that is, the next hop node cannot be reached, it updates the routing information in the routing buffer, and counts the number of times the current service data packet is sent, and turns to step (11); If the node finds that its downlink can communicate normally, then step (3);

(3) The intermediate node updates the N-hop information of the node corresponding to itself in the service data packet according to the N-hop degree of its own node, and forwards the service data packet according to the routing information in the service data packet;

(4) If the intermediate node finds that its downlink cannot maintain normal communication, that is, the next hop node cannot be reached, it will update the routing information of its own node, and increase the number of sending data packets of this service by 1, and then go to step (5) ; If all intermediate nodes can maintain normal communication, the destination node can receive the service data packet, and the route maintenance process ends;

(5) The intermediate node checks whether the number of retransmissions of the current service data packet reaches the number of times preset by the network. If it reaches, the data packet is discarded, and then the routing failure data packet is sent to the source node, i.e. RERR, and then step (7) ; If not, judge whether there are other valid routes in the routing buffer;

(6) If there are other effective routes in the routing buffer, then send the current service data packet along the new route, and the route maintenance process ends; if not, then discard the current service data packet, and then send RERR to the source node;

(7) The intermediate node that receives the RERR updates the corresponding routing information in the local routing buffer, and updates the corresponding N-hop information in the RERR with the N-hop information of the local node, and then forwards the RERR to the RERR that contains the route. upstream node;

(8) After the source node receives the RERR, update the routing information in the local routing buffer;

(9) The source node checks whether there are still business data packets waiting to be sent in the data buffer, and if so, then checks whether there are other valid routes in the routing buffer, and turns to step (10); if there is no business data packet waiting in the data buffer sent, the routing maintenance process ends;

(10) If the source node finds that there is no effective route in the route buffer, then re-initiate the route search process, and the route maintenance ends; if it finds that there is an effective route in the route buffer, then the service data packet is sent along the new route, and the route maintenance process ends;

(11) The source node judges whether the number of sending times of the current service data packet reaches the predetermined number of sending times of the network, if it reaches, then discards the data packet, and turns to step (9); if it does not reach, then judges whether there are other effective For routing, go to step (10).

In a multi-hop Ad Hoc network, although there are various time-varying characteristics mentioned above, the local topology of the network is still relatively stable. This is because, if the network topology changes extremely rapidly, the transmission of data packets will only use "flooding" (the so-called "flooding" means that the source node directly sends out data packets without specifying any path, If the node finds that the local node is not the destination node, it will forward the data packet until the data packet reaches the destination node or the lifespan expires), and any routing algorithm will be invalid. Therefore, in order to make the routing algorithm more effective than the "flooding" method, the relative stability of the local network topology is a necessary condition. Based on this, the present invention proposes a routing algorithm (NDBR) based on the degree of nodes in an Ad Hoc network, which fully utilizes the stability of the local topological structure in the Ad Hoc network. Assuming that the transmitting and receiving distance of a node is R, then the present invention defines "the N-hop degree and N-hop activity degree of a node" as follows:

The number of nodes within the range of the node as the center and NR as the radius is called "the N-hop degree of the node", referred to as "the N-hop degree of the node" (N=1, 2, ..., are natural numbers); The number of active nodes (that is, the node has data packets to send) within the range of the node as the center and NR as the radius is called "the activity degree of N hops of the node", referred to as "the activity degree of N hops of the node" (N= 1, 2, ..., are natural numbers).

It is worth pointing out that in an actual communication network, since a node cannot know the existence of inactive nodes around it (that is, the node does not have any data packets to send), the N hops that each node can learn are actually equal to N jump activity.

NDBR takes the statistical characteristics of the N-hop degree of the routing flow through the node as the routing criterion. Therefore, the source node can choose the routes with few competing nodes, thereby avoiding the routes through which the data packets flow through more competing nodes. In this way, on the one hand, the data packets can reach the destination node faster; The energy consumption of the nodes should be as fair as possible, so as not to make the nodes at the congested links consume too much.

Assume that a route contains M nodes and H hops, that is, H=M-1, and the N-hop degree of the i-th node that the path flows through is D _i (1≤i≤M). definition $\mathrm{D.}=\underset{i=1}{\overset{m}{\mathrm{\&Sigma;}}}{\mathrm{D.}}_i,\stackrel{\&OverBar;}{\mathrm{D.}}=\frac{1}{m}\underset{i=1}{\overset{m}{\mathrm{\&Sigma;}}}{\mathrm{D.}}_i.$ The present invention proposes that the following statistics can be used as routing parameters (RSM).

$\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span>{\mathrm{<span\; class="notranslate">\; <figure-callout\; id="1"\; label="RSM"\; filenames="C20041000346600191.png"\; state="\{\{state\}\}">RSM</figure-callout></span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}<span\; class="notranslate">\; =</span>\underset{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 1</span>}}{\overset{\mathrm{<span\; class="notranslate">\; m</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}}{\mathrm{<span\; class="notranslate">\; D.</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; ,</span>$

$2)---{\mathrm{<figure-callout\; id="2"\; label="RSM"\; filenames="C20041000346600191.png,C20041000346600201.png"\; state="\{\{state\}\}">RSM</figure-callout>}}_2=(h+1)\sqrt{\frac{1}{m-1}\underset{i=1}{\overset{m}{\mathrm{\&Sigma;}}}{({\mathrm{D.}}_i-\stackrel{\&OverBar;}{\mathrm{D.}})}^2},$ in $\stackrel{\&OverBar;}{\mathrm{D.}}=\frac{1}{m}\underset{i=1}{\overset{m}{\mathrm{\&Sigma;}}}{\mathrm{D.}}_i,$

$\mathrm{<span\; class="notranslate">\; 3</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span>{\mathrm{<span\; class="notranslate">\; <figure-callout\; id="3"\; label="RSM"\; filenames="C20041000346600191.png,C20041000346600201.png"\; state="\{\{state\}\}">RSM</figure-callout></span>}}_{\mathrm{<span\; class="notranslate">\; 3</span>}}<span\; class="notranslate">\; =</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; h</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; [</span>\frac{\mathrm{<span\; class="notranslate">\; 1</span>}}{\mathrm{<span\; class="notranslate">\; m</span>}}\underset{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 1</span>}}{\overset{\mathrm{<span\; class="notranslate">\; m</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}}{\mathrm{<span\; class="notranslate">\; D.</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}\mathrm{<span\; class="notranslate">\; \&alpha;</span>}\sqrt{\frac{\mathrm{<span\; class="notranslate">\; 1</span>}}{\mathrm{<span\; class="notranslate">\; m</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1</span>}}\underset{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 1</span>}}{\overset{\mathrm{<span\; class="notranslate">\; m</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}}{<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; D.</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; -</span>\stackrel{<span\; class="notranslate">\; \&OverBar;</span>}{\mathrm{<span\; class="notranslate">\; D.</span>}}<span\; class="notranslate">\; )</span>}^{\mathrm{<span\; class="notranslate">\; 2</span>}}}<span\; class="notranslate">\; ]</span><span\; class="notranslate">\; ,</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 0</span>}<span\; class="notranslate">\; <</span>\mathrm{<span\; class="notranslate">\; \&alpha;</span>}<span\; class="notranslate">\; <</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; )</span>$

After the RSM (RSM ₁ , RSM ₂ or RSM ₃ ) is determined, the routing selection criterion is as follows: in the routing buffer (that is: the storage space for storing routes in the node memory), select a route with the smallest RSM value route to the destination node. For RSM ₃ , the size of α is specified by the user according to the upper-layer service characteristics (such as: delay, packet loss rate, bandwidth, etc.), which is mainly reflected in the degree of emphasis on the total number of competing nodes and the standard deviation of the number of competing nodes. , if the total number of competing nodes for routing is more important to the successful transmission of upper-layer services, then α can be as small as possible, and vice versa.

The simulation test shows that when the moving speed of the nodes is the same, the delivery rate of the data packet and the transmission delay of the data packet of the present invention are better than the traditional dynamic source routing method, that is, DSR; but the network overhead is lower than that of DSR. Along with the increase of node moving rate, the advantage of the route search and maintenance method that the present invention proposes is more obvious, when speed reaches 10 meters per second, aspect data packet delivery rate, adopts the route method of RSM ₃ route selection criterion to be more than DSR The method improves about 20%; in terms of data packet transmission delay, the routing method using the RSM ₃ routing criterion improves the performance by about 40% compared with the DSR method. And for network overhead, along with the increase of node rate, the method that the present invention proposes compares with traditional DSR method, and the difference of network overhead reduces gradually, but adopts the routing method of RSM ₃ routing criterion to still compare the network overhead of DSR method Small, about 5% smaller when the node speed is 10 m/s.

Description of drawings

Figure 1. Schematic diagram of the RREQ packet structure.

Figure 2. Schematic diagram of RREP packet structure.

Figure 3. Schematic diagram of RERR packet structure.

Figure 4. Schematic diagram of the business data packet structure.

Fig. 5 is a program flow diagram of the route search method proposed by the present invention.

Fig. 6. A program flow diagram of the route maintenance method proposed by the present invention.

Figure 7. Comparison graph of packet delivery rate.

Figure 8. Comparison of packet transmission delays.

Figure 9. Network overhead comparison graph.

Detailed ways

The routing algorithm based on the degree of node proposed by the present invention can be easily embedded in the existing DSR algorithm, and its implementation mainly includes the following parts: 1) the estimation of the N-hop degree of the node, which can be achieved by adopting the method proposed by the predecessors To be realized; 2) Determination of N, for the sake of simplicity, generally N can be selected as 1 or 2; 3) Software implementation of algorithmic routing search and routing maintenance process.

The N-hop degree of the node required in the NDBR criterion can be obtained by some methods proposed by the predecessors, such as: by using the Kalman filter at the MAC (Media Access Control-media access control) layer; by periodically The method of sending control information (which will increase network overhead), etc. At the same time, in the implementation of the specific routing algorithm, whether NDBR uses the statistics of one-hop, two-hop or more hops as the routing parameter mainly depends on the complexity of network design, network overhead and all traffic in the Ad Hoc network. There are three aspects of the MAC protocol adopted. In practice, there will inevitably be errors in obtaining the N-hop degree, but since the NDBR algorithm selects the best route by comparing the RSM values of each route, the N-hop degree error of the node has little effect on the performance of the algorithm.

It should be noted that, in addition to these statistics proposed in the present invention can be used as routing parameters, other node degree-based statistics can also be designed as routing parameters, which mainly depends on the designer of the communication network.

The NDBR algorithm, like the dynamic source routing algorithm (DSR), is a source routing algorithm driven by demand. In this algorithm, nodes only save and maintain routing information that is in use. The NDBR algorithm includes two stages: 1) route search; 2) route maintenance. In NDBR, each data packet type includes the "address" and "degree" fields, which record the node address and node N-hop degree of the data packet flowing through the node. In addition, each node will monitor any data packet flowing through the node, and extract the node address and N-hop degree of the node through which the data packet flows. They will all be saved in the route buffer of the node, save the establishment time of the route at the same time, and start the timeout timer of the path life (that is: the network presets a timeout value, if the node does not monitor any If the data packet flowing through the path passes, the node considers that the path has failed, and deletes the path from the routing buffer).

The route search and route maintenance process of this algorithm is roughly as follows:

When a business data packet arrives, the node first selects a route from the routing buffer according to the RSM routing criterion. If the node cannot find a route to the destination node, the node will trigger the following route search process. The source node broadcasts and sends a routing request packet (RREQ), as shown in Figure 1 in the packet, where "Type" represents the packet type (including routing request RREQ, routing response RREP, routing failure RERR and business data packets); " "Src_Addr" indicates the address of the source node; "Dest_Addr" indicates the address of the destination node; "Seq_Num" indicates the sequence number of the RREQ packet sent by the node, which is used to identify the uniqueness of the RREQ sent by the source node; "TTL" indicates the number of hops "Cur_Len" indicates the route length from the source node to the current node; "Src_Degree" indicates the N-hop degree of the source node; "Dest_Degree" indicates the N-hop degree of the destination node; "Addr_1～Addr_MaxM" and "Degree_1～ "Degree_MaxM" represent the node address and N-hop degree of the intermediate node through which the RREQ data packet flows, respectively, where MaxM represents the maximum number of intermediate nodes of a route.

After receiving the RREQ, if the node finds that the RREQ is received for the first time, and the node itself is not the destination node, it will add its own address and N hops to the RREQ data packet and forward it out. In this way, the RREQ data packet not only includes the node addresses of all the nodes it flows through, but also includes the N-hops of these nodes. When RREQ reaches the destination node, the destination node will extract the corresponding node address and N hops from RREQ to form a route to the source node, and calculate the RSM value of the route according to the routing selection parameters determined by the NDBR routing criteria. Therefore, the destination node can select an optimal route from its route buffer according to the NDBR route selection criterion, and send the route to the source node in the route response data packet (RREP). The structure of the RREP packet is shown in Figure 2. The meanings of each field are the same as those of the data field in the RREQ, the only difference being that the route in the RREP packet is fixed.

After receiving the RREP, the intermediate node will update the N-hop degree of the corresponding node in the RREP, and send the data packet to the uplink node of the route included in the RREP. Finally, the RREP data packet reaches the source node, so that the source node obtains a route to the destination node. In this way, the service data packet can be transmitted to the destination node along the route. The route search process is completed when the source node obtains a complete route to the destination node. FIG. 5 shows a schematic diagram of the route search process of the NDBR algorithm.

During the transmission of business data packets, if a node finds that its downlink cannot maintain normal communication, the node updates the local routing information and checks whether the number of times the current business data packets are sent has reached the number of times preset by the network. , then discard the data packet, and then send a routing failure data packet (RERR) to the source node; if not, then judge whether there is an effective path to the destination node in the routing buffer, and if so, send the current business data along the new path If it does not exist, the current service data packet is discarded, and then the routing failure data packet (RERR) is sent to the source node. The node receiving the RERR updates the corresponding local routing information and the corresponding N-hop information in the RERR, and forwards it to the upstream node containing the path in the RERR. When the RERR arrives at the source node, the source node first updates the routing information in the local routing buffer, and then checks whether the number of times the current service data packet is sent reaches the number of times preset by the network. If so, the data packet is discarded and the upper layer Whether there are still data packets waiting to be sent in the business data buffer (the storage space used by nodes to store upper-layer business data packets), if there is, search for the best route from the routing buffer according to the routing criteria determined by NDBR, if not found If the best route is found, the source node will re-initiate another route search process; if found, the service data packet will be sent along the new route. If the node finds that the number of times the current service data packet is sent does not reach the number of times preset by the network, the node searches for the best route from the routing buffer according to the routing criteria determined by the NDBR. If the best route is not found, the source node will re-initiate Another route search process; if found, the service data packet is sent along the new route. The structural diagrams of the routing failure data packet and the service data packet are shown in Fig. 3 and Fig. 4 respectively. The specific routing maintenance process is shown in the routing maintenance schematic diagram in FIG. 6 .

In order to verify and compare the performance of the algorithm, we simulated the routing algorithm proposed in the invention, and the simulated hardware conditions are as follows: the main frequency of the computer is 2.6Ghz, the hard disk is 20G, and the memory is 512M.

The specific simulation environment is as follows: 30 nodes move randomly within the range of 600 meters × 600 meters according to the "random way point" model (random moving point model). In this model, the minimum node movement speed is set to 1m/s, and the largest node The movement speed was set to 2m/s, 4m/s, 6m/s, 8m/s and 10m/s respectively. Each node generates CBR (Constant BitRate-constant rate) service (each data packet is 2048 bits, 4 data packets are generated in 1 second), and one of the remaining 29 nodes is randomly selected as the destination node. The physical layer and the MAC layer adopt the IEEE 802.11a standard, and the rate is 54Mbps. The MAC protocol is selected as the basic CSMA/CA protocol (Carrier Sense Multiple Access with Collision Avoidance-Carrier Sense Multiple Access Protocol with Collision Monitoring), namely: the source node sends For business data packets, the destination node sends a confirmation data packet to complete a data packet transmission process. In the routing maintenance algorithm, the maximum allowable sending times of business data packets is set to 2. In the simulation, set N=1, and assume that the N-hop deviation of nodes obeys a uniform distribution, and the error is 10%, that is, the maximum deviation between the N-hop degree of a node and the actual N-hop degree is 10%. We use "NDBR-1", "NDBR-2" and "NDBR-3" to denote the routing algorithms using RSM ₁ , RSM ₂ and RSM ₃ (α=0.5) routing selection parameters respectively; N-hop dynamic source routing algorithm. Figure 7, Figure 8, Figure 9 and Table 1 show the simulation results under this condition. It can be seen that the NDBR algorithm can obtain a higher data packet delivery rate and a smaller data packet transmission delay without increasing network overhead, and in the case of using the routing parameters of RSM ₃ , the data packets sent by the node The standard deviation of the number is the smallest, see the table below, because the energy consumption of the node is mainly determined by the number of data packets sent by the node, so this routing algorithm is the most fair for the energy consumption of the node.

Table 1. Standard deviation comparison of the number of packets sent by nodes routing plan Node moving speed (m/s) 2 6 10 DSR 672.07 630.29 657.10 NDBR-1 643.09 654.71 674.29 NDBR-2 704.75 671.71 715.20 NDBR-3 605.29 579.80 585.29

Claims (1)

1. The route search and maintenance method based on the degree of nodes in the wireless self-organizing network is characterized in that it is wireless self-organizing, i.e. Ad Hoc, formed by wireless transceiver equipment, i.e. nodes, also known as routers, each in the communication network On mobile devices, follow the steps below: Initialization setting: the type of data packet and the data items contained in it, and stored in the memory of each node: 1) The routing request packet, namely RREQ, contains the following data items: The data packet type is represented by "Type"; the source node address is represented by "Src_Addr"; the destination node address is represented by "Dest_Addr"; the sequence number of the RREQ packet sent by the node is represented by "Seq_Num"; The lifetime of the data packet is represented by "TTL". According to the network scale, the preset maximum lifetime is MaxM+1, where MaxM is the maximum number of intermediate nodes that may be included in a route; the route length from the source node to the current node is represented by " "Cur_Len" means; the N-hop degree of the source node is represented by "Src_Degree". The existence of active nodes, so it is also equivalent to the number of active nodes in the above range, that is, the number of nodes that need to send data packets, N chooses 1 or 2; the N hop degree of the destination node is represented by "Dest_Degree", where, The definition of N hops is as above; the node address of the intermediate node that RREQ flows through is represented by "Addr_1～Addr_MaxM", where MaxM represents the maximum number of possible intermediate nodes in a route; the various intermediate nodes that RREQ flows through N hops, represented by "Degree_1~Degree_MaxM", similarly, MaxM represents the maximum possible number of intermediate nodes in a route; 2) The route response data packet, namely RREP, contains the following data items: Type, Src_Addr, Dest_Addr, Seq_Num, Cur_Len, Src_Degree, Dest_Degree, Addr_1～Addr_X and Degree_1～Degree_X, where Addr_1～Addr_X constitutes a complete route, Degree_1～Degree_X represent the N-hop information of the nodes corresponding to Addr_1～Addr_X, and the definitions of other data items are as mentioned above, where X represents the number of intermediate nodes of the route contained in the RREP, and X is not greater than MaxM; 3) The routing failure data packet, namely RERR, contains the following data items: Type, Src_Addr, Dest_Addr, Cur_Len, Src_Degree, Dest_Degree, Addr_1~Addr_X, Degree_1~Degree_X, Error_Up_Addr and Error_Down_Addr, where Type, Src Addr, Dest_Addr, Src_Degree, The meanings of Dest_Degree, Addr_1～Addr_X and Degree_1～Degree_X are as mentioned above, while Cur_Len indicates the number of hops from the node where the error occurred to the current node; Error_Up_Addr indicates the address of the node that the next hop node cannot reach; Error_Down_Addr indicates the next The node address of the one-hop node; 4) The business data package contains the following data items: Type, Src_Addr, Dest_Addr, Cur_Len, Src_Degree, Dest_Degree, Addr_1～Addr_X, Degree_1～Degree_X, Traffic_Data and Alpha, among which Type, Src_Addr, Dest_Addr, Cur_Len, Src_Degree, Dest_Degree, Addr_1～ The meanings of Addr_X, Degree_1~Degree_X are as mentioned above, Traffic_Data represents the upper-layer business data of the business data packet; Alpha represents the user’s required parameters for the delay, packet loss rate, and bandwidth of the business data packet; Set the following parameters and related intermediate variables, and store them in the memory of each node respectively: The timeout threshold of the path life, which means: if the node does not monitor any traffic flow data packets along the path during this period, the node considers the path to be invalid, so the path, that is, the route, is buffered from the route delete from the zone; Routing buffer, which refers to the storage space for storing routes in the memory of each node; Data packet buffer, which refers to the storage space for storing upper layer business data packets in the memory of each node; The maximum number of allowed sending times of business data packets preset by the network; The maximum allowed number of nodes contained in a route preset by the network; Design the following three algorithm programs for calculating the routing parameter RSM of a route, calculate the three routing parameters RSM ₁ , RSM ₂ and RSM ₃ , and store it together with the calculation program of the routing selection criterion in the memory of each node , the routing selection criterion refers to: when the α value is small, the RSM value is RSM ₃ , and a route to the destination node with the smallest RSM ₃ value is selected in the routing buffer; when the α value is large , the RSM value is selected from RSM ₁ or RSM ₂ , and when the RSM value is RSM ₁ , a route to the destination node with the smallest RSM ₁ value is selected in the routing buffer; the RSM ₁ and RSM ₂ and RSM ₃ are calculated as follows: ${\mathrm{<span\; class="notranslate">\; RSM</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}<span\; class="notranslate">\; =</span>\underset{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 1</span>}}{\overset{\mathrm{<span\; class="notranslate">\; m</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}}{\mathrm{<span\; class="notranslate">\; D.</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; ,</span>$ ${\mathrm{RSM}}_2=(h+1)\sqrt{\frac{1}{m-1}\underset{i=1}{\overset{m}{\mathrm{\&Sigma;}}}{({\mathrm{D.}}_i-\stackrel{\&OverBar;}{\mathrm{D.}})}^2},$ in $\stackrel{\&OverBar;}{\mathrm{D.}}=\frac{1}{m}\underset{i=1}{\overset{m}{\mathrm{\&Sigma;}}}{\mathrm{D.}}_i,$ ${\mathrm{<span\; class="notranslate">\; RSM</span>}}_{\mathrm{<span\; class="notranslate">\; 3</span>}}<span\; class="notranslate">\; =</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; h</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; [</span>\frac{\mathrm{<span\; class="notranslate">\; 1</span>}}{\mathrm{<span\; class="notranslate">\; m</span>}}\underset{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 1</span>}}{\overset{\mathrm{<span\; class="notranslate">\; m</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}}{\mathrm{<span\; class="notranslate">\; D.</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; \&alpha;</span>}\sqrt{\frac{\mathrm{<span\; class="notranslate">\; 1</span>}}{\mathrm{<span\; class="notranslate">\; m</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1</span>}}\underset{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 1</span>}}{\overset{\mathrm{<span\; class="notranslate">\; m</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}}{<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; D.</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; -</span>\stackrel{<span\; class="notranslate">\; \&OverBar;</span>}{\mathrm{<span\; class="notranslate">\; D.</span>}}<span\; class="notranslate">\; )</span>}^{\mathrm{<span\; class="notranslate">\; 2</span>}}}<span\; class="notranslate">\; ]</span><span\; class="notranslate">\; ,</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 0</span>}<span\; class="notranslate">\; <</span>\mathrm{<span\; class="notranslate">\; \&alpha;</span>}<span\; class="notranslate">\; <</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; )</span>$ Among them, M is the number of nodes contained in a route; H is the number of hops contained in a route, H=M-1; D _i is the N-hop degree of the i-th node that the route flows through; D is the number of hops that the route flows through The average N-hop degree of M nodes; α is specified by the user in the service data packet. It is a parameter set by the user according to the delay, packet loss rate, and bandwidth of the data packet. At the same time, this parameter indicates that the upper layer business The degree of emphasis on the standard deviation of the total number of competing nodes of the route and the number of competing nodes of each node, 0<α<1, when the emphasis on the standard deviation is small, the value of α is smaller, otherwise, the value of α is smaller big; The described routing search method contains the following steps in turn: (1) When a node generates an upper-layer service data packet, the node becomes the source node. It first judges whether there is a data packet being sent, and if so, inserts the service data packet into the data packet buffer and waits for the data packet Send the current data packet after the packet is sent; if no data packet is being sent, it selects an effective route to the destination node from its own routing buffer according to the above RSM routing criterion; (2) If there is no valid route starting from the node in the routing buffer of the node, the route search process is initiated, that is, the node fills its own address and N hops into the RREQ and sends it by broadcast; if it exists, it turns to Incoming route maintenance process; (3) After the intermediate node receives the RREQ, it checks whether it has received the RREQ for the first time. If it is not the first time it receives the RREQ, it discards the RREQ and the search process ends; if it is the first time it receives the RREQ, the intermediate node sends its own address and N hops are filled into RREQ and forwarded; (4) After the destination node receives the RREQ, it selects the best route according to the predetermined routing criteria in the memory and each RSM value of each path in the routing buffer. A path to the source node is formed by extracting the corresponding node address and N hops from RREQ; (5) The destination node fills the best route information including each node address and N hops into the RREP and sends it to the source node; (6) After receiving the RREP, the intermediate node of the best route updates the N-hop information of the node corresponding to itself in the RREP according to the N-hop degree of its own node, and forwards it to the upstream node of the route contained in the RREP; (7) After the source node receives the RREP, it obtains an effective route from the source node to the destination node, and stores it in its own route buffer, and the route search process ends; The described routing maintenance method contains the following steps in turn: (1) The source node can obtain an effective route from the source node to the destination node according to the above step (7), or obtain an effective route from the routing buffer directly after the upper layer service data packet is generated in the above step (2). Routing, filling the node address and corresponding N-hop information into the current service data packet to be sent, and sending the service data packet; (2) If the source node finds that its downlink cannot communicate normally, that is, the next hop node cannot be reached, it updates the routing information in the routing buffer, and counts the number of times the current service data packet is sent, and turns to step (11); If the node finds that its downlink can communicate normally, then step (3); (3) The intermediate node updates the N-hop information of the node corresponding to itself in the service data packet according to the N-hop degree of its own node, and forwards the service data packet according to the routing information in the service data packet; (4) If the intermediate node finds that its downlink cannot maintain normal communication, that is, the next hop node cannot be reached, it will update the routing information of its own node, and increase the number of sending data packets of this service by 1, and then go to step (5) ; If all intermediate nodes can maintain normal communication, the destination node can receive the service data packet, and the route maintenance process ends; (5) The intermediate node checks whether the number of retransmissions of the current service data packet reaches the number of times preset by the network. If it reaches, the data packet is discarded, and then the routing failure data packet is sent to the source node, i.e. RERR, and then step (7) ; If not, judge whether there are other valid routes in the routing buffer; (6) If there are other effective routes in the routing buffer, then send the current service data packet along the new route, and the route maintenance process ends; if not, then discard the current service data packet, and then send RERR to the source node; (7) The intermediate node that receives the RERR updates the corresponding routing information in the local routing buffer, and updates the corresponding N-hop information in the RERR with the N-hop information of the local node, and then forwards the RERR to the RERR that contains the route. upstream node; (8) After the source node receives the RERR, update the routing information in the local routing buffer; (9) The source node checks whether there are still business data packets waiting to be sent in the data buffer, and if so, then checks whether there are other valid routes in the routing buffer, and turns to step (10); if there is no business data packet waiting in the data buffer sent, the routing maintenance process ends; (10) If the source node finds that there is no effective route in the route buffer, then re-initiate the route search process, and the route maintenance ends; if it finds that there is an effective route in the route buffer, then the service data packet is sent along the new route, and the route maintenance process ends; (11) The source node judges whether the number of sending times of the current service data packet reaches the predetermined number of sending times of the network, if it reaches, then discards the data packet, and turns to step (9); if it does not reach, then judges whether there are other effective For routing, go to step (10).

Images