WIRELESS MESH NETWORK SYSTEM, VIRTUAL NODE GENERATING METHOD, THEREOF, UNICAST PACKET ROUTING METHOD, AND SCHEDULING METHOD THEREOF

• US 20110103322A1
• Filed: 08/03/2010
• Published: 05/05/2011
• Est. Priority Date: 10/29/2009
• Status: Active Grant

• Current Assignee: Korea Advanced Institute of Science and Technology
• Original Assignee: Korea Advanced Institute of Science and Technology
• Inventors: Lee, Du-Jeong, Jung, Sangsu, Sung, Jihoon, Rhee, June Koo
• Granted Patent: US 8,509,064 B2
• Time in Patent Office: Days
• US Class Current: 370/329
• CPC Class Codes: H04L 45/72 Routing based on the source address
• CPC Class Codes: H04W 40/246 Connectivity information discovery
• CPC Class Codes: H04W 84/22 with access to wired networks

Abstract

A wireless mesh network system generates at least one virtual node within a transmission area of a specific mesh node when no mesh nodes exist in two or three continuous quadrants within the transmission area with reference to the specific mesh node. Also, the system performs routing by combining uplink and downlink routing methods so as to support unicast between the mesh nodes in a domain. Further, a channel access order of the mesh nodes is determined based on the potential values allocated to the mesh nodes forming the wireless mesh network according to the field theory. In this instance, the channel access order can be established by a central control method by a central processor for controlling the wireless mesh network or a distributed control method using contention per mesh node.

Claims

1. A wireless mesh network system using electrostatic field model based potential routing scheme comprising:

a plurality of mesh nodes for calculating a potential value by using at least one virtual node generated when a predefined boundary node condition is satisfied, and routing a packet according to a predetermined packet transmission order by using the potential value; and

a plurality of gateway nodes, located in wireless mesh network, for functioning as gateways to provide an Internet connection to the plurality of mesh nodes.

2. The wireless mesh network system of claim 1, wherein,

when no neighboring nodes exist in two or three consecutive quadrants within a transmission area, the plurality of mesh nodes determine themselves to be boundary nodes, however if determined as boundary nodes, they generate at least one virtual node within the transmission area.

3. The wireless mesh network system of claim 1, wherein,

when neighboring nodes exist in only one of two sides divided by a line, which is considered to be all included in the two sides, passing through the calculating mesh nodes, the plurality of mesh nodes determine themselves to be boundary nodes, however if determined as boundary nodes, they generate at least one virtual node within the transmission area.

4. The wireless mesh network system of claim 1, wherein,

when the plurality of mesh nodes, the virtual nodes, and the neighboring nodes exists on a straight line within the transmission area after having generated the at least one virtual node, the plurality of mesh nodes continue to generate the virtual node until forming at least triangle elements required for calculating the potential value, and

the virtual node has a potential value of a predefined constant or a potential value generated by interpolating or extrapolating a potential value of the mesh node and the predefined constant.

5. The wireless mesh network system of claim 1, wherein

the plurality of mesh nodes generate virtual nodes in the vertical direction within the transmission area when the neighboring nodes are arranged to form a straight line with the mesh nodes in two facing quadrants within the transmission area, and

the virtual node has a potential value of a predefined constant or a potential value generated by interpolating or extrapolating a potential value of a mesh node classified as a boundary node and the predefined constant.

6. The wireless mesh network system of claim 1, wherein

when a network prefix of a destination of a received packet corresponds to a prefix of the network of the plurality of mesh nodes, the plurality of mesh nodes route the packet by using a downlink routing method referring to a source address-based routing table including a downlink routing path determined by a uplink routing path, and when the prefixes of the network are not the same, the plurality of mesh nodes transmit the packet to a forwarding node predefined by a potential algorithm.

7. The wireless mesh network system of claim 1, wherein

the plurality of mesh nodes performs a schedule algorithm using the potential value and routing by combining uplink and downlink routing methods so as to support unicast between the mesh nodes in a domain.

8. A method for generating a virtual node, comprising:

a mesh node checking a disposed state of neighboring nodes, the mesh node as a node for calculating a potential value at a predefined specific time;

determining whether the mesh node is a boundary node based on the disposed state; and

generating at least one virtual node when the mesh node is determined to be the boundary node.

9. The method of claim 8, wherein

the determining includes determining the mesh node to be a boundary node when no neighboring nodes exist in two or three consecutive quadrants in the transmission area or when the neighboring nodes exist in only one of two sides formed by dividing the transmission area by a line, which is considered to be all included in the two sides, passing through the mesh node.

10. The method of claim 8, wherein

the generating of a virtual node includes:

generating at least one virtual node within the transmission area of the mesh node;

determining whether the mesh node, the generated virtual node, and the neighboring nodes are disposed in a straight line; and

,

when the nodes are disposed in a straight line, the generating at least one virtual node is repeated until the mesh node, the generated virtual node, and the neighboring nodes form triangle elements required for calculating a potential value, and the virtual node has a potential value of a predefined constant or a potential value that is generated by interpolating or extrapolating a potential value of a mesh node classified as a boundary node and the predefined constant.

11. The method of claim 10, further including,

when the neighboring nodes are disposed on a straight line in two facing quadrants with the mesh node virtual nodes are generated in the vertical direction of the mesh node.

12. A method for a plurality of mesh nodes to route a unicast packet in a wireless mesh network, comprising:

determining whether a network prefix of a destination of a received packet corresponds to network prefixes of the plurality of mesh nodes;

when the network prefixes are different, routing the unicast packet to a default gateway node; and

when the network prefixes are the same, routing the unicast packet by referring to a source address-based routing table including a downlink routing path determined by a uplink routing path.

13. The method of claim 12, wherein

the routing of a unicast packet by referring to the source address-based routing table includes:

determining whether a routing entry exists by searching the source address-based routing table;

when the routing entry does not exist, transmitting a packet to a gateway node by using an uplink routing method until finding a node with the source address-based routing table including a corresponding routing entry; and

when the routing entry exists, transmitting the packet to a next hop of the routing entry by using a downlink routing method.

14. A method for a plurality of mesh nodes to schedule a packet in a wireless mesh network, comprising:

calculating potential values of the plurality of mesh nodes and a potential value of first-hop neighboring nodes; and

scheduling a packet transmission order based on the calculated potential values.

15. The method of claim 14, wherein

the scheduling further includes:

the plurality of mesh nodes respectively updating the potential values of the plurality of mesh nodes and the potential values of the first-hop neighboring nodes to a central processor for controlling the wireless mesh network; and

receiving a packet transmission order from the central processor,

wherein the packet transmission order includes a channel access order for sequentially allocating time slots starting from the transmission path with the greatest force defined by a difference between the potential values of the plurality of mesh nodes and the potential values of the first-hop neighboring nodes.

16. The method of claim 14, wherein

the scheduling includes:

calculating force defined by a difference between the potential values of the plurality of mesh nodes and the potential values of the first-hop neighboring nodes;

setting a priority based on the intensity of force; and

determining a transmission standby time and a contention standby time in a medium access contention method according to the priority.