CN1222180C - Method for constructing stabilized self-adaption self-organization network terminal - Google Patents

Abstract

The present invention relates to a method for constructing a self-organization network terminal self-adaptive to network stability, which belongs to the field of wireless self-organization network routing technologies. The present invention is characterized in that the method is a route selecting method measuring the stability of a node according to the quantity of data packets successfully transmitted in the history of the node and measuring the loads of the node according to the occupation rate of a data buffer region to be transmitted of the node so as to comprehensively consider path time delay characteristics, routing stability and path loads as a routing standard of the wireless self-organization network. Compared with a traditional self-organization network terminal based on an AODV algorithm, the method has the advantages of longer routing effective time and small routing failure probability, and the aspects of successful data transfer ratios, average data transmission throughput of terminals, link failure quantities and average data transmission delay are all improved.

Description

Method for Constructing Self-Organizing Network Terminal Adaptive to Network Stability

technical field

The invention relates to the technical field of wireless network routing, in particular to a method for constructing a self-organizing network terminal with self-adaptive stability.

Background technique

Wireless networks can be divided into two categories in terms of structural composition: networks with a fixed infrastructure and networks without a fixed infrastructure. (Elizabeth M. Royer, Chai-Keong Toh, "A Review of Current Routing Protocols for Ad Hoc Mobile Wireless Networks", IEEE Personal Communications, Vol.6, No.2, pp.46-55, April 1999.)

The first type of network has fixed network nodes connected to each other by wires, and these nodes constitute the basic architecture of the network, such as a cellular network and a local wireless access network (WLAN). In the cellular network, the basic network structure is composed of base stations. With the base station as the center, the circular (regular hexagonal) area within the base station’s transmission radius forms a “cell”. The fixed and evenly distributed base stations jointly realize the coverage of a certain area by the network. . The user's mobile device is directly connected to the base station in the cell, and all data is forwarded to the user through the base station. The base stations are generally connected to each other by wire. The base station is equipped with a dedicated switching device to complete the exchange and forwarding of user data. In a local wireless access network, an access point (Access Point, AP) constitutes the basic structure of the network. Mobile terminals within the coverage of each AP's wireless transceiver can access the Internet through the AP, and all user data is forwarded through the AP. In this type of wireless network, a mobile terminal establishes a connection with an "access point" (base station, AP, etc.) within its communication range, and the transmitted business data is processed and forwarded through the "access point". When a terminal moves out of the communication range of one "access point" and enters the communication range of another "access point", switching between the old and new "access points" occurs, allowing them to be continuously connected throughout the network Communicate seamlessly. However, terminals located outside the coverage of the system's "access point" cannot establish contact with the system, and communication links cannot be directly established between terminals. The topology of the entire network is fixed and determined by the distribution of network infrastructure devices.

There is no "access point" or switching equipment in the second type of wireless network, but a distributed communication network formed spontaneously by a group of user terminals, which is called "Wireless Ad hoc network".

The self-organizing network (ad hoc) originated from the ALOHA network established by the University of Hawaii in 1968 in order to connect the school's educational facilities. On this basis, a multi-hop packet radio network PRNet-Packet Radio network was proposed in 1973 (J.Jubin and J.D.Tornow, "The DARPA packet radio network protocol," Proc.Of the IEEE, vol 75, No.1, Jan 1987, pp. 21-32).

When IEEE developed the IEEE 802.11 standard, it renamed PRNet as Ad hoc network. In 1997, IETF established the mobile Ad hoc network MANET (Mobile Ad hoc NETwork) working group, which is responsible for the research and development of routing algorithms for mobile Ad hoc networks with hundreds of nodes, and carries out corresponding standardization work. The MANET working group has developed more than a dozen Internet draft standards.

In a wireless ad hoc network, two adjacent terminals can directly establish an "end-to-end" communication link without forwarding through devices such as base stations (or APs); at the same time, in an ad hoc network, there are no dedicated Each terminal has the function of routing switching, which can establish and maintain routes to other terminals and forward business data for its adjacent terminals. Furthermore, when non-adjacent terminals need to communicate, the terminal itself can dynamically search for an effective route, and the data packet is forwarded by other terminals and delivered to the final destination terminal in a "multi-hop" manner. In an end-to-end communication service, establishing a route is a prerequisite for completing the transmission, and the search efficiency, path quality, and system overhead of the route determine the overall transmission performance of the system. The flexibility of wireless ad hoc networks makes the routing algorithm adopted by its terminals one of the main factors affecting network performance, and the design of routing algorithms has become a research difficulty and hot spot in this field. At present, most of the routing algorithms for ad hoc networks that have been proposed are based on the mechanism of route search, establishment, and maintenance in traditional wired Internet or wireless cellular networks, and the shortest route is used as the preferred best route for communication transmission. In wireless ad hoc networks, the mobility of communication terminals causes the network topology to change constantly, so in wireless ad hoc networks, the shortest route is not necessarily the best route.

In the routing algorithm of the existing self-organizing network system, when multiple routes to the same destination terminal are found, the one with the "minimum path delay" will be selected, such as AODV (Ad hoc On-Demand Distance Vector (AODV) Routing, Jan.19, 2002) algorithm. But the path with the least delay is not necessarily the most stable route. As shown in Figure 1,

There may be multiple optional paths from source node S to destination node D, including (S, K1, K2, D) and (S, A, D), where (S, A, D) is "minimum delay" , then under the AODV algorithm, the source node S will choose this path to send data. But if the stability of K1 and K2 nodes is higher than that of A node, and the delays of the two paths are similar, then choosing (S, K1, K2, D) as the route is more suitable for the successful and effective transmission of data. At the same time, when the load on a certain path is too heavy, it may cause local data congestion in the network. At this time, other paths should be selected as the route for data transmission. Therefore, path delay, path stability and path delay should be comprehensively considered in routing selection. Load balancing among three factors.

Contents of the invention

The purpose of the present invention is to provide a method for constructing an ad hoc network terminal self-adaptive to network stability, which comprehensively considers network path delay, path stability and path load.

In order to achieve the above object, the technical solution of the present invention is to provide a method for building an self-organizing network terminal that is self-adaptive to network stability. It is a method to measure the stability of a node by the number of data packets successfully transmitted in the history of the node. The load of the node is measured by the occupancy rate of the buffer area of the data waiting to be sent, so that the route selection method of the wireless ad hoc network routing standard is based on the comprehensive consideration of the path delay characteristics, route stability and path load.

Described method, it comprises the following steps:

(1) Setting parameters and their structure;

(2) The sending node queries the corresponding effective route in the cache routing table according to the address of the final destination terminal in the packet header:

If a valid route is found, this packet is sent;

Otherwise, send a route search packet (RQ) to carry out the next step of route search;

(3) When a neighbor node receives the RQ, compare the label of this RQ with the RQ label to the same destination node in its record:

If the label of this RQ is large, then this node continues to process the RQ packet, and at the same time record the label of this RQ as the largest RQ label that has been processed to the same destination node; otherwise, directly discard this RQ;

(4) This node checks whether the intermediate node address listed in RQ contains its own address:

If it has been protected, it is a loop route and discarded; otherwise, continue processing;

(5) When the node receiving RQ is not the destination node of this RQ, check whether the RQ hop count exceeds its maximum hop limit (Hop-Limit):

If it has exceeded, discard it; otherwise, write its own address into the RQ intermediate node address list in sequence, and continue to send updated RQ information packets to neighbor nodes;

(6) If the node receiving a certain RQ is already the destination node of this RQ, or follow step (2) to find out that there is valid routing information to the corresponding destination node in the routing cache table it saves, then this node copies the corresponding The address of the intermediate node and the above-mentioned other parameter values are sent back to the routing response packet (RP);

(7) When the originating node of RQ, that is, the source node, receives the RP, it calculates the joint selection parameter W of this path, and stores the routing information in its routing cache table;

(8) When the source node sends data later, it will select the one with the smallest W value among all the routes to the corresponding destination node;

(9) After the source node sends out the RQ, if it does not receive the RP within a certain period of time (Route-Discovery-Period), the source node will delay for a period of time (Route-Discovery-Delay) and then re-send the route search packet RQ , and double the above two time values to prevent frequent routing searches from excessively occupying system resources.

Described method, its described setting parameter and its structure, comprise:

1) Terminal stability: Each terminal uses the data packets successfully transmitted within a specified period as the basis for measuring its stability, and its parameter structure is:

a) Accumulation cycle: specified by the system, represented by Count-Cycle;

The number of packets successfully delivered in a counting cycle, represented by Packet-Counter;

b) Path stability V-node:

V-node=0.1 V-node+Packets-Counter;

2) Terminal load: the proportion of data packets waiting to be sent in the terminal cache;

3) Route search information: the route search packet (RQ) sent by the terminal when performing route search, its structure is:

a) ID: The RQ number is given by the terminal that initiated the routing search packet;

b) Source-address: the address of the terminal that initiated this RQ;

c) Destination-address: the address of the RQ destination terminal;

d) Hop-Limit (N): the maximum hop limit value of this RQ search;

e) K-route: routing load parameters;

f) V-route: route stability parameter;

g) Address-i: the address of the i-th intermediate node in the path;

V-route=V-route+V _i -node; V _i -node is the stability parameter of node i;

K-route=K-route+K _i -node; K _i -node is the load parameter of node i;

4) Routing response information: When a route to the destination terminal is found, the routing response packet (RP) sent back by the corresponding node:

ID, Source-address, Destination-address, K-route, V-route, Address-1... The definition of Address-N is the same as the corresponding variable definition in the RQ corresponding to this RP;

5) Cache routing table: each terminal saves the effective routing information searched within a certain period of time, and its parameter structure contains:

a) Destination Node Address;

b) Routing joint selection parameter (Selection Measurement, represented by W);

c) Routing intermediate node address list (Middle Nodes Address List);

d) Route effective time limit (Life time);

Among them, the kth route W from node i to node j is represented by W _k-ij ,

${\mathrm{<span\; class="notranslate">\; W</span>}}_{\mathrm{<span\; class="notranslate">\; k</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; ij</span>}}<span\; class="notranslate">\; =</span>{\mathrm{<span\; class="notranslate">\; A</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}<span\; class="notranslate">\; \&CenterDot;</span>\mathrm{<span\; class="notranslate">\; N</span>}<span\; class="notranslate">\; +</span>\frac{\mathrm{<span\; class="notranslate">\; 1</span>}}{\mathrm{<span\; class="notranslate">\; N</span>}}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; A</span>}}_{\mathrm{<span\; class="notranslate">\; 2</span>}}<span\; class="notranslate">\; \&CenterDot;</span>\mathrm{<span\; class="notranslate">\; K</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; route</span>}<span\; class="notranslate">\; +</span>{\mathrm{<span\; class="notranslate">\; A</span>}}_{\mathrm{<span\; class="notranslate">\; 3</span>}}<span\; class="notranslate">\; \&Center\; Dot;</span>\mathrm{<span\; class="notranslate">\; V</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; route</span>}<span\; class="notranslate">\; )</span>$

in:

N; the total number of hops for this route;

A1: path distance weight coefficient, setting;

A2: "Load Balance" weight coefficient, setting;

A3: "Stability" weight coefficient, setting;

6) Route Error (RE): The "routing failure information packet" sent by the corresponding terminal caused by the routing error, its parameter structure is: the destination terminal address of the failed route (Destination-address), the middle Node-address.

In the self-adaptive routing algorithm for network stability proposed by the present invention, the number of data packets successfully transmitted in the history of the node is used to measure the stability of the node, and the occupancy rate of the data cache area waiting to be sent is used to measure the load of the node, and the path is considered comprehensively. Delay characteristics, routing stability and path load, calculate the W value of each path, as follows:

${\mathrm{<span\; class="notranslate">\; W</span>}}_{\mathrm{<span\; class="notranslate">\; k</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; ij</span>}}<span\; class="notranslate">\; =</span>{\mathrm{<span\; class="notranslate">\; A</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}<span\; class="notranslate">\; \&Center\; Dot;</span>\mathrm{<span\; class="notranslate">\; N</span>}<span\; class="notranslate">\; +</span>\frac{\mathrm{<span\; class="notranslate">\; 1</span>}}{\mathrm{<span\; class="notranslate">\; N</span>}}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; A</span>}}_{\mathrm{<span\; class="notranslate">\; 2</span>}}<span\; class="notranslate">\; \&Center\; Dot;</span>\mathrm{<span\; class="notranslate">\; K</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; route</span>}<span\; class="notranslate">\; +</span>{\mathrm{<span\; class="notranslate">\; A</span>}}_{\mathrm{<span\; class="notranslate">\; 3</span>}}<span\; class="notranslate">\; \&CenterDot;</span>\mathrm{<span\; class="notranslate">\; V</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; route</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; ,</span>$

W _k-ij : the kth route from node i to node j;

N: the total number of hops for this route;

V-route:; route stability parameters;

K-route:; route load parameters;

A ₁ : Path distance weight coefficient;

A ₂ : "Load Balance" weight coefficient;

A ₃ : "Stability" weight coefficient;

Among multiple routes to the same destination terminal, the route with the smallest W value will be used as the preferred route to send user data packets. The smaller the W value, the shorter the route, the higher the stability, and the lower the load. In turn, the success rate of data transmission in the network and the network transmission capacity are improved, and the average data transmission delay is reduced.

The present invention is characterized in that: it measures the stability of the node by the number of data packets successfully delivered in the history of the node, and measures the load of the node by the occupancy rate of the data cache area waiting to be sent, so as to comprehensively consider the path delay Characteristics, routing stability and path load are used as the routing selection method of wireless ad hoc network routing standards; when the source node sends out RQ, if it does not receive RP within a certain period of time (Route-Discovery-Period), the source node will delay After a period of time (Route-Discovery-Delay), re-send the route search information packet RQ, and double the above two time values, so as to prevent frequent route search from excessively occupying system resources.

The routing algorithm given in the wireless ad hoc network terminal design proposed in the present invention fully considers the influence of terminal stability on system performance in the ad hoc network, and constructs a network that comprehensively considers route length, route stability, and network load. Balanced Wireless Ad Hoc Communication System. Through system simulation comparison, this self-organizing network terminal with self-adaptive network stability is better than the traditional self-organizing network terminal based on AODV algorithm (Ad hoc On-Demand Distance Vector (AODV) Routing, Jan.19, 2002), in the system In the evaluation of indicators such as average transmission delay, system average transmission success rate, terminal capacity, and average number of link disconnections, it has better performance.

The simulation experiments show that the saturated system performance of the adaptive routing selection method for network stability is better than that of the AODV method, no matter the terminal's motion dwell time is the same but the network load is different, or the network load is constant but the terminal's motion dwell time changes.

The present invention can be applied in the field of wireless communication, in conference rooms, offices, classrooms and other temporary environments with high terminal density, to temporarily build a network for publishing and sharing of information; Interconnection and data exchange, building a local area network at low cost; collaborative work and data synchronization between personal portable devices, such as temporary construction of a personal area network (Personal Area Network) between laptops, mobile phones, PDAs and other devices; public places Temporary access services, such as temporary access to local area networks by service personnel or customer handheld devices in coffee shops and restaurants; connection services in blind areas of service coverage of traditional cellular networks, such as shadow corners inside large buildings, underground buildings, etc. Environments where network coverage is difficult (or cost is too high); areas without network coverage, such as remote mountainous areas, deserts, forests, canyons, communication between people; environments where traditional networks cannot work normally, such as emergency communications in disaster areas Services; personnel communication and equipment interconnection in special environments such as battlefields and space; sensor network (sensornetwork), a quasi-static, multi-hop self-organizing network application, can be used for intelligence collection on the battlefield (such as terrain, surface condition detection , minefield detection), system monitoring (such as status monitoring of urban underground pipeline systems, production line status detection, etc.), early prediction of earthquakes and tsunamis, etc.

Description of drawings

Figure 1 is a schematic diagram of the stability factors of the path;

Fig. 2 is the routing search diagram of the network stability self-adaptive routing selection method of the present invention;

Fig. 3 is a curve diagram comparing the system saturation capacity of the network stability adaptive routing selection method of the present invention and the AODV method when the terminal movement residence time is the same and the network load is different;

Fig. 4 is a system performance comparison diagram of the network stability self-adaptive routing selection method and the AODV method of the present invention when the network load is constant and the terminal movement residence time changes:

Figure 4(a) is a comparison of the "data packet successful transmission ratio" index;

Figure 4(b) is the comparison of the "node average throughput" index;

Figure 4(c) is the comparison of the "number of link failures" index;

Figure 4(d) is a comparison of the "average end-to-end delay" index;

Fig. 4 (e) is the comparison of "system routing overhead" index;

Fig. 5 is a program flow diagram of the method of the present invention.

Detailed ways

1. Definition of parameter structure

1. Terminal stability

Each terminal uses the number of data packets successfully delivered within a specified period as the basis for measuring its stability, and its parameter structure is: Packets-Counter Count-Cycle V-node

The cumulative cycle (Count-Cycle) is specified by the system, and the initial values of Packets-Counter and V-node are 0. The terminal will record the number of packets successfully delivered within a Count-Cycle in the Packets-Counter. The calculation formula of V-node is:

V-node＝0.1·V-node+Packets-Counter

At the end of a Count-Cycle, the Packets-Counter is reset to 0.

2. Terminal load

In the SAR routing algorithm, the proportion of the number of data packets waiting to be sent in the terminal cache to the node cache space is used as the load measure of the terminal, which is recorded as the parameter K-node, and is calculated as follows:

$\mathrm{<span\; class="notranslate">\; K</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; node</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; -</span>\frac{\mathrm{<span\; class="notranslate">\; Packets</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; number</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; in</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; waiting</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; list</span>}}{\mathrm{<span\; class="notranslate">\; Amount</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; of</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; Buffer</span>}}$

Packets_number_in_waiting_list: the number of data packets currently cached by the node that need to be sent;

Amount_of_Buffer: The size of the cache space opened by the node for sending data.

3. Routing search information

When the terminal performs route search, it will send out a "route search packet" (Route Quest, RQ), whose structure is: RQ ID Source-address Destination-address Hop-limit(N) K-route V-route Address-i...

ID is the RQ number given by the terminal that initiated the route search packet, Source-address is the address of the terminal that initiated the RQ, Destination-address is the address of the destination terminal of this RQ, and Hop-limit is the maximum number of hops for this RQ search Limit value, Address-i is the address of the i-th intermediate node in the path. V-node and K-node are the stability and load parameters of this path respectively, and their calculation formulas are:

V-route＝V-route+V _i -node

K-route＝K-route+ _Ki -node

4. Routing response information

When a route to the destination terminal is found, the corresponding node will send back a "route reply packet" (Route Reply, RP), whose structure is: RP ID Source-address Destination-address K-route V-route Address-1 ... Address-N

The definitions of ID, Source-address, Destination-address, Address-I, V-route, and K-route in the RP are the same as the corresponding variable definitions in the RQ corresponding to this RP, and the variable values are equal.

5. Cache the routing table

In the network stability adaptive routing algorithm, each terminal saves the effective routing information searched within a certain period of time, and its cache routing table structure includes destination node address (Destination NodeAddress), routing joint selection parameter W (Selection Measurement-W), The routing middle node address list (Middle Nodes Address list), routing valid time limit (Lifetime), as shown below. DestinationNode Address SelectionMeasurement--W Middle Nodes Address list Lifetime

6. Routing failure information

In the process of data transmission, if a routing error is found due to changes in the network topology, the corresponding terminal will send out a "route error packet" (Route Error, RE), whose structure is: RE Destination-address Node-address

Destination-address is the destination terminal address of the invalid route, and Node-address is the address of the intermediate node where the routing error occurs.

2. Route search and maintenance

In the network stability adaptive routing algorithm, the route search mechanism is as follows: when the terminal sends a data packet, the address of the final destination terminal of the data packet is written in the header of the data packet, and the sending node will use the address of the destination terminal in the cache. Look up the corresponding route in the routing table. If a valid route can be found, this data packet is sent; if there is no valid route, an RQ is sent to search for a route.

Take Figure 2 as an example, assuming that node A needs to search for a route to node E, A will send out an RQ, and neighbor nodes within the coverage of the transmission power of node A will receive this RQ packet, and each RQ has an ID Labels, indicating the order in which they are issued. Each node that receives the RQ packet also records the RQ label it has processed to a certain destination node.

When a node receives an RQ, it first checks whether it has processed the RQ to the same destination node, and only when the RQ label of this RQ is larger than the RQ label to the same destination node in its record, the node continues to process this RQ packet , otherwise it will be discarded directly. Afterwards, this node will check whether the address of the intermediate node listed in the RQ contains its own address. If it has been included, it proves that this is a loop route and discarded; if it is not included, continue processing.

If the node receiving the RQ is not the destination node of the RQ and there is no effective route to the destination node of the RQ in its cache route, check whether the RQ hop count exceeds its Hop-limit, if it has exceeded, discard it; if not , then write its own address into the RQ intermediate node address list in sequence, and continue to broadcast updated RQ information packets to its neighbor nodes.

If the node is the destination node (destination-address) of this RQ or a valid route to the destination node has been saved in the caching routing table of this node, the node will copy the corresponding intermediate node address and other parameter values, and send back the routing reply Packet RP. When the initiating node A of RQ receives the RP, it will calculate the joint selection parameter W of this path, as follows:

${\mathrm{<span\; class="notranslate">\; W</span>}}_{\mathrm{<span\; class="notranslate">\; k</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; ij</span>}}<span\; class="notranslate">\; =</span>{\mathrm{<span\; class="notranslate">\; A</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}<span\; class="notranslate">\; \&Center\; Dot;</span>\mathrm{<span\; class="notranslate">\; N</span>}<span\; class="notranslate">\; +</span>\frac{\mathrm{<span\; class="notranslate">\; 1</span>}}{\mathrm{<span\; class="notranslate">\; N</span>}}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; A</span>}}_{\mathrm{<span\; class="notranslate">\; 2</span>}}<span\; class="notranslate">\; \&CenterDot;</span>\mathrm{<span\; class="notranslate">\; K</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; route</span>}<span\; class="notranslate">\; +</span>{\mathrm{<span\; class="notranslate">\; A</span>}}_{\mathrm{<span\; class="notranslate">\; 3</span>}}<span\; class="notranslate">\; \&Center\; Dot;</span>\mathrm{<span\; class="notranslate">\; V</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; route</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; ,</span>$

And store this route in its routing cache table, when A node sends data, it will choose the one with the smallest W value among all the routes to the corresponding destination node.

After the source node sends out the RQ, if it does not receive the RP within a certain period of time (Route-Discovery-Period), the source node will re-send the route search information packet RQ after a period of time (Route-Discovery-Delay), and will The value of Route-Discovery-Delay is doubled to prevent frequent route search requests from excessively occupying system resources.

In the network topology shown in Figure 2, when node A searches for the route to E, all intermediate nodes that receive the RP also record the corresponding path information, so when the path from “A to E” is found, at the same time The paths "A to C", "A to D", "B to D", "B to E", "C to E" are obtained.

When a node (such as node C) sends data to its next hop node (such as node D), but does not receive the acknowledgment (ACK) from D, C will resend the data to D, if the number of consecutive transmissions exceeds the maximum Retransmission-Limit, it is considered that the path "C to D" has an error, node C will send a RE packet, and the node receiving the RE will delete the path "C to D" in its cached routing table of all routes.

3. Performance comparison with AODV algorithm

We used the GloMoSim network simulation platform (GloMoSim: A ScalableNetwork Simulation Environment, Lokesh Bajaj, Mineo Takai, Ken Tang, Rajive Bagrodia, Mario Gerla) to complete the performance simulation. The simulation model is as follows:

●The scope of the simulated geographical area is 160×160, and the number of terminals is 16;

Uniform and random distribution of terminals: Divide the simulated geographic range into 16 sub-areas according to the number of terminals, and randomly generate a location coordinate for a terminal in each sub-area;

●Terminal movement model: uniformly and randomly generate the movement speed of a certain terminal within the range of its average movement speed (0-2 m/s), and uniformly and randomly generate the movement direction of this terminal. When the terminal moves to the boundary of the simulated geographical range, its position coordinates are calculated according to the rule of "left out and right in"; for the uniform linear motion of the terminal, uniform sampling simulation is adopted, and the "stay time" of the terminal at a certain point is the sampling interval ;

●Wireless transmission adopts double exponential fading model, fading index (-2, -4), threshold 100m;

●Wireless carrier frequency 5.2GHz, channel bandwidth 20MHz, terminal maximum transmission rate 54Mbps, receiver sensitivity 21dB, transmitter power 0dBm (effective receiving range 50m);

●Antenna gain 0dB, background temperature 270K, noise factor 10;

●The network MAC and physical layer adopt IEEE802.11a protocol, the network layer above adopts TCP/IP protocol, and the application layer adopts CBR to generate transmission tasks. The unit data packet length is 2048bytes, and the average load of the terminal changes with the sending time interval of CBR data packets , the simulation time is 400 seconds;

●Each simulation point is the arithmetic mean of 20 simulation results under the same conditions;

●In the simulation, the value of the accumulation cycle (Count-Cycle) of the SAR algorithm is set to 0.1 seconds;

●Using two sets of routing weight coefficients: (A ₁ =1, A ₂ =0.1, A ₃ =0.05) and (A ₁ =1, A ₂ =0.1, A ₃ =0)

In the first set of simulations, Figure 3 shows the comparison of the network stability adaptive routing algorithm and AODV's saturated system capacity under the condition that the terminal motion residence time is 0.5 seconds, when the network load is different.

In the second group of simulations, Figure 4 shows that the network load is constant (the CBR data packet sending interval is 0.002 seconds, and the terminal average load is 8274.747070Kb/s), and when the terminal’s motion residence time changes (0.5 seconds to 5 seconds), the network Performance Comparison of Stability Adaptive Routing Algorithm and AODV. The parameter indicators in the simulation results are defined as follows:

Offered Load: 32 CBR data transmission tasks are generated within 5 seconds. The initiation time of CBR tasks is uniformly and randomly distributed within 0 to 5 seconds. The originating terminal and destination terminal are randomly generated among 16 terminals (the originating terminal of each task Different from the destination terminal), the number of CBR data packets sent by each task is 100, and each data packet is a fixed-length 2048bytes (1byte=8bits) data packet sending interval is T seconds.

$\mathrm{<span\; class="notranslate">\; offered</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; load</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; bits</span>}<span\; class="notranslate">\; /</span>\mathrm{<span\; class="notranslate">\; the\; s</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; =</span>\frac{\mathrm{<span\; class="notranslate">\; 2048</span>}<span\; class="notranslate">\; *</span>\mathrm{<span\; class="notranslate">\; 8</span>}}{\mathrm{<span\; class="notranslate">\; T</span>}}$

Node's Throughput: For a certain terminal k, record the time when it starts to receive data within the simulation time as T ₁ , the time when it receives the last data packet is T ₂ , and receive a total of M data packets within the time period from T ₁ to T ₂ ( Each data packet contains 2048*8bits information), then the Throughput of terminal N is:

$\mathrm{<span\; class="notranslate">\; Throughput</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; node</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; k</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; bits</span>}<span\; class="notranslate">\; /</span>\mathrm{<span\; class="notranslate">\; the\; s</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; =</span>\frac{\mathrm{<span\; class="notranslate">\; m</span>}<span\; class="notranslate">\; *</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 2048</span>}<span\; class="notranslate">\; *</span>\mathrm{<span\; class="notranslate">\; 8</span>}<span\; class="notranslate">\; )</span>}{{\mathrm{<span\; class="notranslate">\; T</span>}}_{\mathrm{<span\; class="notranslate">\; 2</span>}}<span\; class="notranslate">\; -</span>{\mathrm{<span\; class="notranslate">\; <figure-callout\; id="1"\; label="T"\; filenames="C0315815500192.png,C0315815500202.png"\; state="\{\{state\}\}">T</figure-callout></span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}}$

Node's Throughput is the arithmetic mean of the Throughput of all terminals:

$\mathrm{<span\; class="notranslate">\; nod</span>}{\mathrm{<span\; class="notranslate">\; e</span>}}^{<span\; class="notranslate">\; \&prime;</span>}\mathrm{<span\; class="notranslate">\; the\; s</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; Throughput</span>}<span\; class="notranslate">\; =</span>\frac{\mathrm{<span\; class="notranslate">\; 1</span>}}{\mathrm{<span\; class="notranslate">\; N</span>}}\underset{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1</span>}}{\overset{\mathrm{<span\; class="notranslate">\; N</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}}\mathrm{<span\; class="notranslate">\; Throughput</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; node</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; i</span>}$

Packets delivery ratio: The ratio of the number of data packets successfully received by the destination node of the task to all data packets sent by the task initiation node.

Broken Link Number: During the simulation time, the number of links that have established communication links that have failed due to various factors.

End-to-end Delay: For any data packet, the period from when the data packet is sent by the initiating node of the transmission task until it is correctly received by the final destination terminal of the task is defined as the "end-to-end transmission" of this data packet Delay", End-to-end Delay is defined as the arithmetic mean of the "end-to-end transmission delay" of all successfully transmitted data packets within the simulation time.

Routing Control Cost: During the simulation time, routing maintenance packets (RQ, RP, RE) are called Control Packets, and all sent data packets are called Data Packets, then

$\mathrm{<span\; class="notranslate">\; Routing</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; control</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; cost</span>}<span\; class="notranslate">\; =</span>\frac{\mathrm{<span\; class="notranslate">\; Data</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; Packets</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; bits</span>}<span\; class="notranslate">\; )</span>}{\mathrm{<span\; class="notranslate">\; control</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; Packets</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; bits</span>}<span\; class="notranslate">\; )</span>}$

When the terminal is in a mobile state, the change of the network topology becomes one of the important factors affecting the network performance. In the route search of the new routing algorithm, the route with higher stability is selected for data transmission, so the effective time of the route is longer, and the probability of route failure is smaller. The data results show that under this simulation condition, the new routing algorithm’s Compared with AODV, the successful data transmission rate has increased by about 6.1%, the average data transmission throughput of the terminal has increased by about 7.3%, the number of link failures during transmission has decreased by 17.6%, and the average data transmission delay has decreased by 7.4% compared with AODV; at the same time, due to The problem of network load balancing is considered when the routing search is established, which avoids local data transmission congestion and greatly improves it.

On various network communication terminal devices, such as wireless network cards, communication modules integrated in the terminal, etc., the routing algorithm of the network layer (Network Layer) is updated to a routing algorithm that adapts to network stability, and a "network stable network" can be built. Self-adaptive self-organizing network terminal".

Claims (2)

1. A method for building network stability self-adaptive self-organizing network terminals, characterized in that it measures the stability of a node with the number of data packets successfully delivered in the history of the node, and caches the data waiting to be sent by the node The area occupancy rate is used to measure the load of the node, so as to comprehensively consider the path delay characteristics, routing stability and path load as the routing selection method of the wireless ad hoc network routing standard; including steps: (1) Setting parameters and their structure; (2) The sending node queries the corresponding effective route in the cache routing table according to the address of the final destination terminal in the packet header: If a valid route is found, this packet is sent; Otherwise, send out a "route search packet" to carry out the next step of route search; (3) When a neighbor node receives the "routing search information packet", the label of this "routing search information packet" and the processed maximum "routing search information packet" to the same destination node in its records are used as Compare: If the label of the "route search packet" is large, the node continues to process the "route search packet", and at the same time records the label of the "route search packet" as the largest processed "route packet" to the same destination node. Search information package" label; Otherwise, directly discard this "routing search packet"; (4) This node checks whether the intermediate node address listed in the "routing search packet" contains its own address: If it has been protected, it is a loop route and discarded; otherwise, continue processing; (5) When the node receiving the "route search packet" is not the destination node of this "route search packet", check whether the hop count of the "route search packet" has exceeded its "maximum hop limit": If it has exceeded, then discard; otherwise, its own address is written into the intermediate node address list of "routing search information packet" in sequence, and continue to send updated "routing search information packet" to neighbor nodes; (6) If a certain node that receives the "routing search information packet" is already the destination node of this "routing search information packet", or follow step (2) to find out that there is a corresponding destination node in the route cache table saved in it. If the routing information is valid, the node copies the corresponding intermediate node address and other parameter values above, and sends back the "routing response packet"; (7) When the initiating node of the "routing search information packet", that is, the source node, receives the "routing response information packet", it calculates the joint selection parameter (W) of this path, and stores the routing information into its routing cache table; (8) When the source node sends data later, it will select the one with the smallest W value among all the routes to the corresponding destination node; (9) After the source node sends out the "routing search information packet", if it does not receive the "routing response information packet" within a certain "routing search time threshold", the source node will delay a period of "routing search back-off time" and restart Send out "route search information packet", and double the above two time values to prevent frequent route search and excessive occupation of system resources. 2. The method according to claim 1, wherein said setting parameters and their structures include: 1) Terminal stability: Each terminal uses the data packets successfully transmitted within a specified period as the basis for measuring its stability, and its parameter structure is: a) Accumulation cycle: specified by the system, represented by Count-Cycle; The number of packets successfully delivered in a counting cycle, represented by Packet-Counter; b) Path stability V-node: V-node=0.1 V-node+Packets-Counter; 2) Terminal load: the proportion of data packets waiting to be sent in the terminal cache; 3) Route search information: the "route search information packet" sent by the terminal when performing route search, its structure is: a) Packet number, represented by ID: the "routing search packet" serial number is given by the terminal that initiates the routing search packet; b) Source node address, represented by Source-address: the address of the terminal that initiates this "routing search packet"; c) destination node address, represented by Destination-address: the address of the destination terminal of this "routing search information packet"; d) maximum hop limit, represented by Hop-Limit (N): the maximum hop limit value searched by this "route search packet"; e) route load, represented by K-route: route load parameter; f) route stability, represented by V-route: route stability parameter; g) address of the i-th intermediate node, represented by Address-i: the address of the i-th intermediate node in the path; V-route=V-route+V _i -node; V _i -node is the stability parameter of node i; K-route=K-route+K _i -node; K _i -node is the load parameter of node i; 4) Routing response information: when a route to the destination terminal is found, the corresponding node sends back the "routing response information packet", including: packet number, source node address, destination node address, routing load, routing stability, The variable values such as the intermediate node address are respectively the corresponding variable values in the "routing search information packet" corresponding to the "routing response information packet"; 5) Cache routing table: each terminal saves the effective routing information searched within a certain period of time, and its parameter structure contains: a) destination node address; b) routing joint selection parameters; c) routing intermediate node address list; d) Valid time limit for routing; Among them, the "route joint selection parameter" of the kth route from node i to node j is represented by Wk-ij, ${\mathrm{<span\; class="notranslate">\; W</span>}}_{\mathrm{<span\; class="notranslate">\; k</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; ij</span>}}<span\; class="notranslate">\; =</span>{\mathrm{<span\; class="notranslate">\; A</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}<span\; class="notranslate">\; \&CenterDot;</span>\mathrm{<span\; class="notranslate">\; N</span>}<span\; class="notranslate">\; +</span>\frac{\mathrm{<span\; class="notranslate">\; 1</span>}}{\mathrm{<span\; class="notranslate">\; N</span>}}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; A</span>}}_{\mathrm{<span\; class="notranslate">\; 2</span>}}<span\; class="notranslate">\; \&Center\; Dot;</span>\mathrm{<span\; class="notranslate">\; K</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; route</span>}<span\; class="notranslate">\; +</span>{\mathrm{<span\; class="notranslate">\; A</span>}}_{\mathrm{<span\; class="notranslate">\; 3</span>}}<span\; class="notranslate">\; \&Center\; Dot;</span>\mathrm{<span\; class="notranslate">\; V</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; route</span>}<span\; class="notranslate">\; )</span>$ in: N: the total number of hops for this route; A1: Path distance weight coefficient, setting; A2: "Load Balance" weight coefficient, setting; A3: "Stability" weight coefficient, setting; 6) Routing failure information: the "routing failure information packet" sent by the corresponding terminal caused by the routing error, its parameter structure is: the destination terminal address of the failed routing, and the address of the intermediate node where the routing error occurred.

Images