Wireless mesh network system, virtual node generating method, thereof, unicast packet routing method, and scheduling method thereof

• US 8,509,064 B2
• Filed: 08/03/2010
• Issued: 08/13/2013
• 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: Rhee, June Koo, Jung, Sangsu, Sung, Jihoon, Lee, Doojung
• Primary Examiner(s): Ng, Fan
• Application Number:
  US12/849,486
• Publication Number:
  US 20110103322A1
• Time in Patent Office: 1,106 Days
• Field of Search: 370229-240
• US Class Current: 370/229
• 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 within a transmission area 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,

wherein, when no neighboring nodes exist in two or three consecutive quadrants within the 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.

2. 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.

3. 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.

4. 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.

5. 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.

6. 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.

7. 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.

8. The method of claim 7, 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.

9. The method of claim 7, 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.

10. The method of claim 9, 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.

11. 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,

wherein the packet transmission order is based on force determined by a difference between the potential values of the plurality of mesh nodes and the potential values of the first-hop neighboring nodes.

12. The method of claim 11, 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.

13. The method of claim 11, 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.