CN105813165A - Wireless Mesh network applied MAC layer distributed type scheduling mechanism - Google Patents

Abstract

The invention discloses a MAC layer distributed scheduling mechanism for a wireless Mesh network. The present invention can support timely update of the online state of each node in the network and ensure the transmission of business data on the link without collision, and can ensure the fairness among various services under other conditions required for communication between network nodes and system throughput.

Description

A MAC Layer Distributed Scheduling Mechanism for Wireless Mesh Networks

technical field

The invention relates to the field of wireless Mesh networks, in particular to a MAC layer distributed scheduling mechanism for wireless Mesh networks.

Background technique

Wireless Mesh network scheduling mechanism is one of the key technologies in the wireless Mesh network field. The quality of the scheduling mechanism has a very important impact on the utilization rate of wireless channels and the QoS of network services. Therefore, in-depth research on the MAC layer distribution applicable to wireless Mesh networks Scheduling mechanism is of great significance to the research of wireless mesh network.

The characteristics of wireless mesh network, such as node mobility, multi-hop cascading, flexible topology, and strong scalability, put forward specific requirements for its scheduling mechanism. The single-channel MAC protocol used in the existing Mesh network is a distributed coordination function mode DCF, which uses a carrier sense multiple access mechanism with collision avoidance. Under this mechanism, each node's right to use the channel is based on A kind of random competition, when the network load is heavy, there will be frequent data conflicts, and only best-effort services can be provided without any QoS guarantee, which cannot meet the requirements of real-time services for delay and jitter. The other point coordination function PCF defined on the basis of DCF uses point coordination to poll nodes and centrally control medium access. Although this can guarantee certain reliability, due to the polling method, the When the network size is large, this mechanism will lead to performance degradation in terms of system delay and throughput.

Contents of the invention

The technical problem to be solved by the present invention is to provide a MAC layer distributed scheduling mechanism suitable for wireless Mesh networks that effectively guarantees system throughput and service QoS under a certain network scale by performing resource scheduling through distributed interaction of nodes in the entire network. In order to solve the problems of time delay, low throughput and poor reliability caused by the limitation of the network scale and the number of hops in the existing wireless Mesh network system.

In order to solve the problems of the technologies described above, the present invention adopts the following technical solutions:

A MAC layer distributed scheduling mechanism for a wireless Mesh network, the scheduling mechanism comprising:

S1. Each node that has entered the network updates the local one-hop information or two-hop neighbor information according to the NCFG (network configuration message: MeshNetworkConfiguration) message periodically broadcast in the network;

S2. Each node elects the control message sending time slot according to the information of the neighbor nodes within two hops; if the election is successful, send the next message according to the election result; if the election is not successful, continue the election until it succeeds;

S3. Any node in the network serves as a resource request node based on the received network layer bandwidth request information, and establishes a local link scheduling unit, and at the same time, sends a resource request message outward;

S4. The network-connected node receives the resource request message, wherein the node with the resource information matching the resource request message is used as the resource authorization node, and sends an authorization success message or an authorization failure message to the resource request node;

S5. The network-connected node sends confirmation information to the resource authorization node based on the authorization success message or the authorization failure message, and establishes data communication with the resource authorization node, or feeds back request failure information to the network layer;

S6. The network-connected node serving as the resource authorization node performs resource scheduling based on the confirmation information meeting the requirements.

Preferably, said step S1 includes:

S11. Each node that has joined the network periodically broadcasts and sends an NCFG message, which carries all the one-hop neighbor information of the local node;

S12. Each node connected to the network updates the local one-hop neighbor information according to the received NCFG message of the one-hop neighbor, and updates the local one-hop or two-hop neighbor information according to the neighbor list information in the NCFG message of the one-hop neighbor.

Preferably, said step S2 includes:

S21. Each node that has entered the network determines all nodes that meet the election conditions according to the received one-hop and two-hop neighbor information;

S22. Based on the pseudo-random hybrid algorithm Mesh-election, use the identity information of the nodes meeting the selection conditions and the current competition time slot information to select;

S23. If the election is successful, determine the time for sending the control message next time; if the election fails, continue the election until the election is successful.

Preferably, the identity information of the nodes meeting the selection conditions includes: node ID numbers and node ID numbers in the set of legally competing nodes among legally competing nodes specified by the order of network access.

Preferably, said step S3 includes:

S31. Any node in the network serves as a resource request node based on the received network layer bandwidth request information, and establishes a local link scheduling unit;

S32. The resource requesting node generates a DSCH-Request (distributed scheduling request message: MeshDistributedScheduling-Request) message according to the bandwidth request information of the local scheduling unit, and at the same time, adds all information of the local time slot table to the message;

S33. The resource request node sends a resource request message according to the control message sending time result obtained through election.

Preferably, said step S4 includes:

S41. The network-connected node receives a resource request message; if the resource request message is not a request for its own resources, discard the request message; if the resource request message belongs to its own resource request, then the node performs step S42 as a resource authorization node;

S42. The resource authorizing node obtains the common time slot table of the two nodes by comparing the local time slot table with the time slot table of the resource requesting node;

S43. Judging whether the public time slot table satisfies the bandwidth requirement of the resource requesting node; if so, the resource authorizing node replies with an authorization success message, and sends the authorized time slot table to the resource requesting node; if not, returns an authorization failure message.

Preferably, the step S4 further includes: S44. If the authorization is successful, modify the local time slot table information according to the public time slot table, and if the authorization fails, do not do any processing.

Preferably, said step S5 includes:

S51. The network-connected node judges whether the received successful authorization message is its own information; if so, updates the local time slot table and the local scheduling unit according to the successful authorization message, and generates a confirmation message with the local time slot table. At the same time, press Authorize the time slot to send data; if not, update the scheduling unit and slot table of the one-hop and two-hop neighbor nodes according to the successful authorization message that does not conform to itself, and update the local time slot table according to the message;

S52. The network-connected node judges whether the received failed authorization message is in line with its own information; if so, sends failure cause information to the network layer according to the failed authorization message information, and releases the relevant local scheduling unit; if not, directly discards the failed authorization message Failed authorization message.

Preferably, said step S6 includes:

S61. If the confirmation information received by the network-connected node matches its own information, the three-way handshake is completed, and the resource scheduling of the resource request node and the resource authorization node is successfully established;

S62. If the confirmation information received by the network-connected node does not conform to its own information, further judge the information content carried in the confirmation information; if the confirmation message carries the time slot table of the neighbor node, the resource authorization node Confirm the message, update the scheduling unit and slot table of the one-hop and two-hop neighbor nodes; if the confirmation message does not carry the time slot table of the neighbor node, the resource authorization node will link information, release the time slot table occupied by the link, and release the neighbor scheduling unit.

Preferably, the method further includes: S7. After resource scheduling is completed, the resource requesting node feeds back a confirmation message based on the network layer link closing message, and informs surrounding nodes that the link is closed.

The beneficial effects of the present invention are as follows:

The technical scheme of the present invention can directly establish data links between each node, and the information flow is the shortest, and the nodes in the network can easily share resources; even if a certain part of the entire network fails, it will not affect the operation of the entire network, so Has high reliability.

Description of drawings

Below in conjunction with accompanying drawing, specific embodiment of the present invention is described in further detail;

Fig. 1 shows the flowchart of the MAC layer distributed scheduling mechanism of the present invention;

Fig. 2 shows the interactive flowchart of distributed three-way handshake success;

Fig. 3 shows a schematic diagram of a topological network structure constructed by the method of the present invention;

FIG. 4-1 shows a schematic diagram of simulating the method of the present invention;

Fig. 4-2 shows a schematic diagram of simulating the method of the present invention.

detailed description

In order to illustrate the present invention more clearly, the present invention will be further described below in conjunction with preferred embodiments and accompanying drawings. Similar parts in the figures are denoted by the same reference numerals. Those skilled in the art should understand that the content specifically described below is illustrative rather than restrictive, and should not limit the protection scope of the present invention.

The invention discloses a MAC layer distributed scheduling mechanism for a wireless Mesh network, characterized in that the scheduling mechanism includes:

S1. Each node that has entered the network updates the local one-hop information or two-hop neighbor information according to the NCFG message periodically broadcasted in the network; the step S1 includes:

S11. Each node that has joined the network periodically broadcasts and sends an NCFG message, which carries all the one-hop neighbor information of the local node;

S12. Each node connected to the network updates the local one-hop neighbor information according to the received NCFG message of the one-hop neighbor, and updates the local one-hop or two-hop neighbor information according to the neighbor list information in the NCFG message of the one-hop neighbor.

S2, each node performs the election of the control message sending time slot according to the information of the neighbor nodes within two hops; if the election is successful, send the next message according to the election result; if the election is not successful, continue the election until it succeeds; the step S2 includes :

S21. Each node that has entered the network determines all nodes that meet the election conditions according to the received one-hop and two-hop neighbor information;

S22. Based on the pseudo-random hybrid algorithm Mesh-election, use the identity information of the nodes meeting the selection conditions and the current competition time slot information to select;

S23. If the election is successful, determine the time for sending the control message next time; if the election fails, continue the election until the election is successful.

S3. Any node in the network is based on the received network layer bandwidth request information as a resource request node, and establishes a local link scheduling unit, and at the same time, sends a resource request message outward. The step S3 includes:

S31. Any node in the network serves as a resource request node based on the received network layer bandwidth request information, and establishes a local link scheduling unit;

S32. The resource requesting node generates a DSCH-Request message according to the bandwidth request information of the local scheduling unit, and at the same time, adds all information of the local time slot table to the message;

S33. The resource request node sends a resource request message according to the control message sending time result obtained through election.

S4. The network-connected node receives the resource request message, wherein a node having resource information consistent with the resource request message is used as a resource authorization node, and sends an authorization success message or an authorization failure message to the resource request node; the step S4 includes:

S41. The network-connected node receives a resource request message; if the resource request message is not a request for its own resources, discard the request message; if the resource request message belongs to its own resource request, then the node performs step S42 as a resource authorization node;

S42. The resource authorizing node obtains the common time slot table of the two nodes by comparing the local time slot table with the time slot table of the resource requesting node;

S43. Judging whether the public time slot table satisfies the bandwidth requirement of the resource requesting node; if so, the resource authorizing node replies with an authorization success message, and sends the authorized time slot table to the resource requesting node; if not, returns an authorization failure message;

S44. If the authorization is successful, modify the local time slot table information according to the public time slot table, and if the authorization fails, do nothing.

S5. The network-connected node sends confirmation information to the resource authorization node based on the authorization success message or the authorization failure message, and establishes data communication with the resource authorization node, or feeds back request failure information to the network layer; the step S5 includes:

S51. The network-connected node judges whether the received successful authorization message is its own information; if so, updates the local time slot table and the local scheduling unit according to the successful authorization message, and generates a confirmation message with the local time slot table. At the same time, press Authorize the time slot to send data; if not, update the scheduling unit and slot table of the one-hop and two-hop neighbor nodes according to the successful authorization message that does not conform to itself, and update the local time slot table according to the message;

S52. The network-connected node judges whether the received failed authorization message is in line with its own information; if so, sends failure cause information to the network layer according to the failed authorization message information, and releases the relevant local scheduling unit; if not, directly discards the failed authorization message Failed authorization message.

S6. The network-connected node serving as the resource authorization node performs resource scheduling based on the confirmation information meeting the requirements. Described step S6 comprises:

S61. If the confirmation information received by the network-connected node matches its own information, the three-way handshake is completed, and the resource scheduling of the resource request node and the resource authorization node is successfully established;

S62. If the confirmation information received by the network-connected node does not conform to its own information, further judge the information content carried in the confirmation information; if the confirmation message carries the time slot table of the neighbor node, the resource authorization node Confirm the message, update the scheduling unit and slot table of the one-hop and two-hop neighbor nodes; if the confirmation message does not carry the time slot table of the neighbor node, the resource authorization node will link information, release the time slot table occupied by the link, and release the neighbor scheduling unit.

S7. After the resource scheduling is completed, the resource requesting node feeds back a confirmation message based on the network layer link closing message, and notifies the surrounding nodes that the link is closed.

The present invention will be further described below by a group of embodiment:

1. Each node maintains neighbor information within two hops:

After the node joins the network, the node that has already joined the network periodically broadcasts and sends NCFG (network configuration message: MeshNetworkConfiguration) message. The NCFG message carries all the one-hop neighbor information of the local node; if the node receives the NCFG message of the one-hop neighbor, it updates the local One-hop neighbor information and update the two-hop neighbor information according to the NCFG message of the one-hop neighbor.

2. Each node performs control message sending time slot election according to neighbor information within two hops

First, determine the legal competition node of a hop, and introduce parameters including: the neighbor’s next control message sending time and the neighbor’s next sending time range, and obtain the first type of competing node: that is, the neighbor’s next sending time is unknown or this competition time slot Within the next sending time range of neighbors, Meshelection needs to be performed at this time; the second kind of competition node is that this competition time slot happens to be the neighbor’s next control message sending time, and pseudo-random hybrid algorithm Meshelection is required at this time; the third kind The situation is that the time slot for this competition is before the next sending time range of the neighbor, and it is not the next sending time of the neighbor. At this time, the node considers that the time slot is available and no election is required. When the competition time slot traverses the one-hop neighbor election successfully, the time slot traverses the two-hop legal competition nodes by using the same-hop neighbor election method. If the two-hop node election is unsuccessful, start again from the one-hop node election until the election is successful.

3. Resource request nodes make resource requests to other nodes as needed

The node that needs to make resource request establishes a local link scheduling unit according to the received network layer bandwidth request information; according to the bandwidth request information of the local scheduling unit, the resource requesting node that needs to make resource request generates a DSCH-Request message, and in the request message In addition, all the information of the local slot table needs to be added; the node sends the resource request message according to the sending time of the control message obtained by the election.

4. The resource authorization node performs time slot authorization according to searching the public time slot table, and maintains the local time slot table

The node that has already connected to the network receives the resource request message that is not a resource request to itself, and does not do any processing; the node that has connected to the network receives the resource request message to itself and processes it. At this time, the node is the resource authorization node in this resource request. By comparing the local time slot table and the time slot table of the requesting node, the public time slot table of the two nodes is obtained. If the public time slot table obtained at this time meets the bandwidth requirements of the resource requesting node, the authorization success message will be replied, and the authorization time The slot table is sent back to the requesting node, otherwise the authorization failure message is returned; if the resource authorization node authorizes successfully, the resource authorization node modifies the local slot table information according to the public time slot table obtained from the authorization result, and does not do anything if the authorization fails.

5. After the resource request node is authorized, it updates the local slot table and sends back a confirmation message

The network-connected node receives the information of the resource authorization node as its own successful authorization information, then the node updates the local time slot table and the local scheduling unit according to the received authorization result, and generates a confirmation message, which needs to carry the local time slot table , and then send data according to the time slot according to the obtained authorization result;

If the network-connected node receives the resource authorization node's information not its own successful authorization message, the node updates the locally maintained neighbor scheduling unit and time slot table according to the received successful authorization message, and updates the local time slot table according to the message.

The information received by the network-connected node from the resource authorization node is its own failed authorization message, and the node is a resource requesting node, then the node sends failure reason information to the network layer according to the received failed authorization message information, and releases the relevant local scheduling unit ;

If the network-connected node receives the resource authorization node's information that is not its own failed authorization message, it will be discarded without any processing.

6. The resource authorization node receives the confirmation message, the three-way handshake is completed, and data resource scheduling can be performed

The network-connected node receives the information of the resource authorization node as its own confirmation information. At this time, the confirmation information of the resource authorization node and the information of the resource authorization node establishes a relationship without any further processing. It is confirmed that the three-way handshake is completed and the resource scheduling is completed;

The network-connected node receives the confirmation message that the information of the resource authorization node is not its own, and the message carries the time slot table of the neighbor node, then the node updates the locally maintained neighbor scheduling unit and the time slot table according to the message;

If the network-connected node receives the confirmation message that the information of the resource authorization node is not its own, and the message does not carry the time slot table of the neighbor node, the node releases the link information stored in the neighbor scheduling unit maintained locally. Occupy the slot table and release the neighbor scheduling unit.

S7. After the resource scheduling is completed, the resource requesting node feeds back a confirmation message based on the network layer link closing message, and notifies the surrounding nodes that the link is closed.

As shown in Figure 3, it is a schematic diagram of the topology network structure built by the scheme of the present invention: the network has a total of 20 nodes, and nodes No. 0 to No. 19 constitute a network topology including chain links and ring links, each of which is one hop The links are all bidirectional links. The nodes that are directly connected in the figure communicate with each other, and the nodes that are not directly connected are non-directly connected nodes. Figure 4-1 and Figure 4-2 show the simulation results for the network structure shown in Figure 3. During the simulation process, three links are designed to verify that this mechanism can meet high-bandwidth transmission, as well as voice and video transmission. Require.

The first link verifies the multi-hop high-bandwidth transmission requirements, that is, the six-hop resource transmission link from node 6 to node 14 verifies that this distributed scheduling mechanism can achieve high-bandwidth transmission, and the sending rate of node 6 is set to 10Mb /s, the test results are as follows:

No. 6 node sending throughput: Utilizing the scheme simulation of the present invention, it is obtained that the No. 6 node sending average throughput is 9800kb/s;

Forwarding throughput of No. 3 node: using the scheme simulation of the present invention, the average forwarding throughput of No. 3 node is obtained to be 10106.64kb/s;

Forwarding throughput of No. 2 node: using the scheme simulation of the present invention, the average forwarding throughput of No. 2 node is obtained to be 9976.34kb/s;

Forwarding throughput of No. 4 node: using the scheme simulation of the present invention, the average forwarding throughput of No. 4 node is obtained as 9881.93kb/s;

Forwarding throughput of No. 5 node: using the scheme simulation of the present invention, the average forwarding throughput of No. 5 node is 9871.87kb/s;

Forwarding throughput of No. 7 node: using the scheme simulation of the present invention, the average forwarding throughput of No. 7 node is obtained to be 9853.45kb/s;

Receiving throughput of No. 14 node: Using the simulation of the scheme of the present invention, the average receiving throughput of No. 14 node is 9768.09kb/s. It can be seen that this mechanism can realize high-bandwidth transmission.

The second link verifies the voice transmission delay requirement, that is, the link is 3 hops from node 9 to node 0, and the sending rate of node 9 is set to 1Mb/s. This scheme is used for delay simulation to obtain end-to-end The average delay is 0.523291446 seconds. It can be seen that this mechanism can meet the delay requirement of 3-hop voice transmission.

The third link verifies the video transmission delay requirement, that is, the link is 2 hops from node 8 to node 0, and the transmission rate of node 8 is set to 1Mb/s. This scheme is used for delay simulation to obtain end-to-end The average delay is 0.351423737 seconds. It can be seen that this mechanism can meet the delay requirement of 2-hop video transmission.

The test results of each link obtained by simulation are shown in Figure 4-1 and Figure 4-2, in which the black dots between nodes represent the transmitted data, which shows that the above-mentioned designed link is transmitting data.

Apparently, the above-mentioned embodiments of the present invention are only examples for clearly illustrating the present invention, and are not intended to limit the implementation of the present invention. Those of ordinary skill in the art can also make It is impossible to exhaustively list all the implementation modes here, and any obvious changes or changes derived from the technical solutions of the present invention are still within the scope of protection of the present invention.

Claims (10)

1. a kind of MAC layer distributed scheduling mechanism for wireless Mesh network, it is characterized in that, this scheduling mechanism comprises: S1. Each node that has entered the network updates the local one-hop information or two-hop neighbor information according to the NCFG message sent by periodic broadcast in the network; S2. Each node elects the control message sending time slot according to the information of the neighbor nodes within two hops; if the election is successful, send the next message according to the election result; if the election is not successful, continue the election until it succeeds; S3. Any node in the network serves as a resource request node based on the received network layer bandwidth request information, and establishes a local link scheduling unit, and at the same time, sends a resource request message outward; S4. The network-connected node receives the resource request message, wherein the node with the resource information matching the resource request message is used as the resource authorization node, and sends an authorization success message or an authorization failure message to the resource request node; S5. The network-connected node sends confirmation information to the resource authorization node based on the authorization success message or the authorization failure message, and establishes data communication with the resource authorization node, or feeds back request failure information to the network layer; S6. The network-connected node serving as the resource authorization node performs resource scheduling based on the confirmation information meeting the requirements. 2. The MAC layer distributed scheduling mechanism according to claim 1, wherein said step S1 comprises: S11. Each node that has joined the network periodically broadcasts and sends an NCFG message, which carries all the one-hop neighbor information of the local node; S12. Each node connected to the network updates the local one-hop neighbor information according to the received NCFG message of the one-hop neighbor, and updates the local one-hop or two-hop neighbor information according to the neighbor list information in the NCFG message of the one-hop neighbor. 3. The MAC layer distributed scheduling mechanism according to claim 1, wherein said step S2 comprises: S21. Each node that has entered the network determines all nodes that meet the election conditions according to the received one-hop and two-hop neighbor information; S22. Based on the pseudo-random hybrid algorithm Mesh-election, use the identity information of the nodes meeting the selection conditions and the current competition time slot information to select; S23. If the election is successful, determine the time for sending the control message next time; if the election fails, continue the election until the election is successful. 4. MAC layer distributed scheduling mechanism according to claim 3, is characterized in that, the identity information of the node that meets selection condition comprises: node ID number and the legal competition node concentration in the legal competition node specified by the order of network entry The node ID number. 5. The MAC layer distributed scheduling mechanism according to claim 1, wherein said step S3 comprises: S31. Any node in the network serves as a resource request node based on the received network layer bandwidth request information, and establishes a local link scheduling unit; S32. The resource requesting node generates a DSCH-Request message according to the bandwidth request information of the local scheduling unit, and at the same time, adds all information of the local time slot table to the message; S33. The resource request node sends a resource request message according to the control message sending time result obtained through election. 6. The MAC layer distributed scheduling mechanism according to claim 1, wherein said step S4 comprises: S41. The network-connected node receives a resource request message; if the resource request message is not a request for its own resources, discard the request message; if the resource request message belongs to its own resource request, then the node performs step S42 as a resource authorization node; S42. The resource authorizing node obtains the common time slot table of the two nodes by comparing the local time slot table with the time slot table of the resource requesting node; S43. Judging whether the public time slot table satisfies the bandwidth requirement of the resource requesting node; if so, the resource authorizing node replies with an authorization success message, and sends the authorized time slot table to the resource requesting node; if not, returns an authorization failure message. 7. The MAC layer distributed scheduling mechanism according to claim 6, wherein the step S4 further comprises: S44, if the authorization is successful, modifying the local time slot table information according to the public time slot table, if the authorization If it fails, do nothing. 8. The MAC layer distributed scheduling mechanism according to claim 7, wherein said step S5 comprises: S51. The network-connected node judges whether the received successful authorization message is its own information; if so, updates the local time slot table and the local scheduling unit according to the successful authorization message, and generates a confirmation message with the local time slot table. At the same time, press Authorize the time slot to send data; if not, update the scheduling unit and slot table of the one-hop and two-hop neighbor nodes according to the successful authorization message that does not conform to itself, and update the local time slot table according to the message; S52. The network-connected node judges whether the received failed authorization message is in line with its own information; if so, sends failure cause information to the network layer according to the failed authorization message information, and releases the relevant local scheduling unit; if not, directly discards the failed authorization message Failed authorization message. 9. The MAC layer distributed scheduling mechanism according to claim 1, wherein said step S6 comprises: S61. If the confirmation information received by the network-connected node matches its own information, the three-way handshake is completed, and the resource scheduling of the resource request node and the resource authorization node is successfully established; S62. If the confirmation information received by the network-connected node does not conform to its own information, further judge the information content carried in the confirmation information; if the confirmation message carries the time slot table of the neighbor node, the resource authorization node Confirm the message, update the scheduling unit and slot table of the one-hop and two-hop neighbor nodes; if the confirmation message does not carry the time slot table of the neighbor node, the resource authorization node will link information, release the time slot table occupied by the link, and release the neighbor scheduling unit. 10. The MAC layer distributed scheduling mechanism according to claim 1, wherein the method further comprises: S7, after the resource scheduling is completed, the resource requesting node is based on the network layer link closing message, and then the network layer feeds back an acknowledgment message, And inform the surrounding nodes that the link is closed.