CN101217497A - A Path Selection Method for Wireless Mesh Network - Google Patents

Abstract

The present invention proposes a path selection method for a wireless mesh network. A wireless mesh network node obtains and stores wireless mesh network path information and corresponding path information performance parameters and path remaining bandwidth estimation values; when a wireless mesh network initiates a service request When, the wireless mesh network node invokes path information, performance quality parameters and estimated value of remaining broadband, comprehensively considers real-time performance, bandwidth and transmission quality factors to select a matching path according to service quality requirements; and reduces Path selection time, so as to provide different paths for services with different network requirements, effectively use network bandwidth, and realize fast forwarding of wireless mesh networks.

Description

A Path Selection Method for Wireless Mesh Network

technical field

The invention relates to a wireless mesh network, in particular to a path selection method of the wireless mesh network.

Background technique

Wireless mesh network (WMN, wireless mesh network) is a new type of broadband wireless network, which is different from traditional wireless networks. Inheriting the characteristics of the Ad hoc network itself, such as self-configuration, self-organization and self-management, it also has its inherent particularity, such as different types of network nodes have different mobility, and MR generally has a small Mobility, while MC can be a fixed node or a mobile node, which can weaken the impact of mobility when designing WMN routing; the main business of WMN nodes is the business from the Internet gateway, while the main business of Ad hoc networks is any pair of nodes between business flows.

Due to the particularity of WMN, its particularity can be fully utilized when designing WMN routing protocols. Considering the impact of interference conflicts, communication distance and other factors, the path with the smallest number of hops may have poor performance such as throughput and bit error rate, and cannot be the optimal choice; in addition, nodes share resources through routing protocols, so WMN must meet the load Balance this requirement; when the route is interrupted, the route reconstruction should be completed as soon as possible to avoid service interruption; in addition, it will take a long time to establish a path in a large-scale network, which will increase the end-to-end delay. Once the path is established, Due to the change of the path, it needs to consume a lot of network resources for route reconstruction.

It can be seen from the above that the quality of routing directly affects the performance of the network. In the prior art, there are various wireless routing protocols, and the routing with the best performance can be selected, such as determining the best routing according to the measured network performance. However, However, the methods of discovering topology and finding routes in the prior art are still relatively simple, and cannot well combine business content and minimize network resource consumption.

Contents of the invention

The purpose of the present invention is to provide a routing selection method for a wireless mesh network, which takes into account the business content, realizes quality assurance to a certain extent, and reduces network resource consumption as much as possible on this basis, and combines the particularity of WMN to achieve Solve the problems in the prior art.

In order to solve the above problems, the present invention provides the following technical solutions:

A path selection method for a wireless mesh network, the wireless mesh network includes wireless mesh network nodes, and data exchange is performed through the wireless network nodes, characterized in that:

First, the wireless mesh network node acquires and stores wireless mesh network path information and corresponding path information performance parameters and path remaining bandwidth estimation values;

Secondly, when the wireless mesh network initiates a service request, the wireless mesh network node invokes path information, performance quality parameters and estimated value of remaining bandwidth, and selects a matching service according to service quality requirements considering real-time, bandwidth and transmission quality factors path;

If it corresponds to a single path, it will be forwarded directly;

If there are multiple optional paths, look up the dynamic path cache table stored in advance, and select the previously used path corresponding to the same service between the source and sink to transmit data; if the dynamic path cache table does not store the corresponding service between the source and sink path, detect the transmission delay time of the path to be selected through ICMP packets or other professional packets, and create a new entry in the dynamic path cache table to record the best path of the service between the source and sink, and at the same time Data is transferred through this path.

Further, the path performance parameters include the following factors or any combination thereof: bit error rate, hop count, delay, jitter, transmission rate, signal quality, and signal strength.

Further, the service quality requirements mainly include the following factors: the voice service requires high real-time performance and bandwidth guarantee; the data service requires a low bit error rate.

Further, if the service request is a voice service, ensure that the bandwidth, bit error rate, and jitter are within an acceptable range and select the path with the smallest number of hops;

Further, when the requested service is a data service, the bit error rate, the number of hops, and the link transmission rate are sequentially considered when the bandwidth is ensured;

Further, for data services, the path with small but sufficient bandwidth can be given priority to save more bandwidth for other services;

Further, the estimated value of the remaining bandwidth is estimated by listening to the channel, or obtaining the bandwidth usage of the neighboring nodes occupying the channel bandwidth through a Hello message.

Further, an aging time is set for the created entry, and the created entry becomes invalid after reaching the aging time, and is updated within a specified time.

Further, if the created entry is not updated within a specified time, the entry is deleted from the dynamic cache table.

Further, the dynamic path cache table includes the following fields: source address, destination address, next-hop route, service type, aging time, and update period.

The invention has the beneficial effects of providing different paths for services required by different networks, effectively utilizing the network bandwidth, and realizing fast forwarding of the wireless mesh network.

Description of drawings

FIG. 1 is a schematic diagram of a wireless mesh network structure.

FIG. 2 is a flowchart of wireless mesh network routing according to the present invention.

Fig. 3 is a schematic diagram of the structure of a "hello" message frame according to the present invention.

Fig. 4 is a schematic structural diagram of a dynamic path cache table according to the present invention.

specific implementation plan

FIG. 1 is a schematic diagram of a wireless mesh network structure. Among them, the mesh network gateway MGW is a gateway device that connects the wireless mesh network and the external network. It connects to the external network through a wired or wireless interface in the uplink, and connects to the wireless mesh network nodes in the downlink through a wireless method to play the role of interconnection. The mesh network access point MAP (Mesh Access Point) communicates with the access terminal while communicating with other MAPs or MGWs for data forwarding.

FIG. 2 is a flowchart of wireless mesh network routing according to the present invention.

First, the wireless mesh network node acquires and stores wireless mesh network path information, corresponding path information performance parameters, and path remaining bandwidth estimation value.

For the acquisition of path information, similar to the Ad hoc network, there are many optional methods. For the performance parameters corresponding to the relevant path, such as bit error rate, hop count, delay, jitter, transmission rate, signal quality, signal strength, etc. It is a statistical value generated during the data communication process and fed back to the relevant wireless mesh network node, or a statistical value generated during the path test process and fed back to the relevant wireless mesh network node.

There are two schemes for obtaining the estimated value of the remaining bandwidth of the path, one is a scheme based on feedback, and the other is a scheme based on access control. The end-to-end throughput in the network is determined by the bottleneck bandwidth of each host on the path, therefore, the estimation of end-to-end throughput is simplified to find the minimum remaining bandwidth of each host on the path. Since the bandwidth is shared by adjacent hosts, it is difficult to know exactly the bandwidth occupation of other hosts. There are two methods for estimation: one is listening. This is a very straightforward method, because each host can listen to the channel to track the traffic status, and can determine how much idle bandwidth is available per second. IEEE802.11MAC has both physical carrier sense and virtual carrier sense. Virtual carrier The monitoring is completed through the network monitoring vector NAV. For details, please refer to the relevant protocols of IEEE802.11. The above functions can be used to determine the busy and idle time of the channel. For example, if the NAV value is less than the current time (that is, the current bandwidth is not allocated), and the receiving and sending states are both idle, the MAC layer considers the channel to be idle; when NAV has just set a new value, or the receiving state changes from idle to busy , or the sending status changes from idle to busy, the MAC layer considers the channel to be busy. The estimated value of the channel bandwidth can be obtained by multiplying the channel bandwidth by the idle time/(busy time + idle time) and multiplying by a coefficient. The reason why the above coefficients are introduced is due to the characteristics of the IEEE802.11 protocol itself. Due to the existence of backoff strategies such as DIFS and SIFS, the bandwidth is not either idle or busy. Another method of bandwidth estimation is to use the "hello" message. Here, the AODV (ad hoc on-demand distance order) protocol is used for reference, and the "hello" message in the AODV protocol is used to record the sender and its neighbors one hop away. For the bandwidth usage of the node, each host can obtain an estimated value of the remaining bandwidth according to the received "hello" message and the frequency reuse mode (generally, the same frequency can be reused after two hops). We modify the "hello" message so that it can record the bandwidth and time stamps consumed by neighbors and neighbors of neighbors, as shown in Figure 3. The timestamp is used for updates to indicate the real-time nature of the "hello" message. When the host node knows the bandwidth consumed by the latest neighbor node and the neighbor nodes of the neighbor node, subtract the above two from the channel bandwidth and divide by a coefficient to obtain the estimated value of the remaining bandwidth. The reason for dividing by a coefficient is because messages such as RTS, CTS, and ACK also consume bandwidth, so a rough coefficient is provided. According to the duration of RTS, CTS, and ACK in the network design, the amount of transmitted data, and the data rate, etc. Correlation factors can estimate a value, which is not difficult for those skilled in the art.

If the service request is a voice service, ensure that the bandwidth, bit error rate, and jitter are within an acceptable range and select the path with the smallest number of hops;

When the requested service is a data service, the bit error rate, number of hops, and link transmission rate are considered sequentially when the bandwidth is ensured;

For data services, the path with small but sufficient bandwidth can be given priority to save more bandwidth for other services;

If there are still multiple paths to choose from considering the above-mentioned factors, look up the dynamic path cache table stored in advance, and select the previously used path corresponding to the same service between the source and sink to transmit data;

If the path corresponding to the same service between the source and the sink is not stored in the dynamic path cache table, detect the transmission delay time of the candidate path through ICMP messages or other specialized messages, and create a new entry in the dynamic path cache table, Record the best path of the business between source and sink, and transmit data through this path at the same time.

Since the link transmission rate will also reflect the delay of the path to a certain extent, but it is not recorded in factors such as node processing time, so it is not accurate enough, so the end-to-end delay time is introduced here.

Wherein, the dynamic path cache table is gradually established in the network communication process, and the entries created in the cache table are all set with an aging time, and the created entries begin to fail after reaching the aging time, and are updated within a specified time;

If the created entry is not updated within the specified time, the entry is deleted from the dynamic cache table.

The dynamic path cache table may include but not limited to the following fields: source address, destination address, next-hop route, service type, aging time, update period, as shown in FIG. 4 .

Since the main business of the WMN node is from the Internet gateway, the source address or destination address in the entry is often fixed, that is, the address of the Internet gateway, and because it is gradually established in the network communication process, there is no Aging time and update period, so generally only frequently used paths are reserved, so the dynamic path cache table does not need to be very large.

In addition, the aging time of the dynamic path cache table can be set relatively long, such as 10 minutes, 30 minutes, etc., depending on the busyness of the network business. Generally, the corresponding entries only exist after use, and their real-time performance is not as good as that obtained by network nodes. Path information, performance parameters, and remaining bandwidth are only used as auxiliary means, and their main function is to provide reference for node path selection without consuming too much network resources.

To sum up, we provide different paths for services with different network requirements, effectively use the network bandwidth, and realize the fast forwarding of the wireless mesh network as much as possible with the help of the dynamic path cache table. The above preferred embodiments illustrate the present invention, and those skilled in the art can make various changes and modifications to the present invention without departing from the spirit and scope of the present invention. Thus, if these modifications and variations of the present invention fall within the scope of the claims of the present invention and their equivalent technologies, the present invention also intends to include these modifications and variations.

Claims (10)

1. A path selection method of a wireless mesh network, said wireless mesh network comprising wireless mesh network nodes, carrying out data exchange by wireless network nodes, characterized in that: First, the wireless mesh network node acquires and stores wireless mesh network path information and corresponding path information performance parameters and path remaining bandwidth estimation values; Secondly, when the wireless mesh network initiates a service request, the wireless mesh network node invokes path information, performance quality parameters and estimated value of remaining bandwidth, and selects a matching service according to service quality requirements considering real-time, bandwidth and transmission quality factors path; If it corresponds to a single path, it will be forwarded directly; If there are multiple optional paths, look up the dynamic path cache table stored in advance, and select the previously used path corresponding to the same service between the source and sink to transmit data; if the dynamic path cache table does not store the corresponding service between the source and sink path, detect the transmission delay time of the path to be selected through ICMP packets or other professional packets, and create a new entry in the dynamic path cache table to record the best path of the service between the source and sink, and at the same time Data is transferred through this path. 2. the path selection method of wireless mesh network according to claim 1, described path performance parameter comprises following each factor or any combination: bit error rate, hop count, delay, jitter, transmission rate, signal quality, signal strength. 3. the path selection method of wireless mesh network according to claim 2, described service quality requirement mainly comprises following each factor: voice service requires higher real-time performance, and requires bandwidth guarantee; Data service requires lower BER. 4. The path selection method of the wireless mesh network according to claim 2, if the service request is a voice service, ensure that the bandwidth, bit error rate, and jitter are within an acceptable range and select the path with the smallest number of hops; 5. The path selection method of the wireless mesh network according to claim 2, when the requested service is a data service, the bit error rate, the number of hops, and the link transmission rate are considered successively under the situation of ensuring the bandwidth; 6. The path selection method of the wireless mesh network according to claim 5, for data services, the path with small but sufficient bandwidth can be given priority, so as to reserve a larger bandwidth for other services; 7. the path selection method of wireless mesh network according to claim 1, described remaining bandwidth estimated value is estimated by listening to the channel, or obtains the bandwidth use situation of the neighbor node that occupies channel bandwidth by Hello message and estimates Measurement. 8. The path selection method of a wireless mesh network according to claim 1, wherein an aging time is set for the created entry, and the created entry becomes invalid after reaching the aging time, and is updated within a specified time. 9. The path selection method for a wireless mesh network according to claim 8, if the created entry is not updated within a specified time, then delete the entry from the dynamic cache table. 10. The path selection method of the wireless mesh network according to claim 1, wherein the dynamic path cache table includes the following fields: source address, destination address, next-hop route, service type, aging time, update period.

Images