Virtual Grid

• US 20090285136A1
• Filed: 05/20/2005
• Published: 11/19/2009
• Est. Priority Date: 05/20/2005
• Status: Active Grant

• Current Assignee: Agency For Science Technology and Research (Government of Singapore)
• Original Assignee: Agency For Science Technology and Research (Government of Singapore)
• Inventors: Ngoh, Lek Heng, Sun, Peng
• Granted Patent: US 7,924,735 B2
• Time in Patent Office: Days
• US Class Current: 370/310
• CPC Class Codes: H04L 45/20 Hop count for routing purposes, e.g. TTL
• CPC Class Codes: H04W 40/28 for reactive routing

Abstract

A method for constructing a virtual grid (10) for routing data via wireless sensor nodes (20) of a sensor field (30), the method comprising: flooding the sensor field (30) to identify a first terminator (V₁), the flooding originating from a first node (V₀); flooding the sensor field (30) to identify a second terminator (V₂), the flooding originating from the first terminator (V₁); and forming a main communication path (40) by selecting nodes between the first and second terminators (V₁, V₂); wherein the virtual grid (10) is constructed by flooding the sensor field (30) such that each node in the sensor field (30) is assigned a row identifier relative to the main communication path (40), the flooding originating from the nodes belonging to the main communication path (40); and wherein each node is assigned a column identifier according to its hop count from the first terminator (V₁).

Claims

1. A method for constructing a virtual grid for routing data via wireless sensor nodes of a sensor field, the method comprising:

flooding the sensor field to identify a first terminator, the flooding originating from a first node;

flooding the sensor field to identify a second terminator, the flooding originating from the first terminator; and

forming a main communication path by selecting nodes between the first and second terminators;

wherein the virtual grid is constructed by flooding the sensor field such that each node in the sensor field is assigned a row identifier relative to the main communication path, the flooding originating from the nodes belonging to the main communication path; and

wherein each node is assigned a column identifier according to its hop count from the first terminator.

2. The method according to claim 1, wherein the first node is selected by a user.

3. The method according to claim 1, wherein the columns of the virtual grid are constructed when identifying the second terminator.

4. The method according to claim 1, wherein a relationship between a node and a neighboring node is classified according to the order in which they receive a broadcast message of the flooding.

5. The method according to claim 4, wherein the relationship is classified according to any one in the group consisting of:

only one preferred parent, normal parents, children, sibling, and unknown.

6. The method according to claim 1, wherein a flooding packet is transmitted to the nodes during flooding.

7. The method according to claim 6, wherein the flooding packet has a data structure comprising variables to store information relating to:

phase number, thickness control of the rows and columns, hop count from the originating node, granularity of each row or column and total number of nodes in the sensor field.

8. The method according to claim 1, wherein the topology of the sensor field is stored in a local topology database of each node.

9. The method according to claim 1, wherein the first terminator is a node having the largest hop count from the first node after flooding by the first node and is a node without any children.

10. The method according to claim 1, wherein the second terminator is a node having the largest hop count from the first terminator after flooding by the first terminator and is a node without any children.

11. The method according to claim 1, further comprising thickening the main communication path by increasing the number of neighboring nodes proximal to the main communication path.

12. The method according to claim 1, wherein the flooding is restricted to a portion of the total number of nodes of the sensor field.

13. The method according to claim 1, wherein communication between a source and a sink via the virtual grid is routed according to logical directions.

14. The method according to claim 1, wherein the first node belongs to the main communication path.

15. The method according to claim 1, wherein all nodes of the sensor field belong to the main communication path.

16. The method according to claim 1, wherein each node has the same range of wireless coverage.

17. The method according to claim 1, wherein each node asymmetrically communicates with another node.

18. The method according to claim 1, wherein the sensor field is on a two dimensional plane or a multi-dimensional plane.

19. The method according to claim 1, wherein the main communication path is substantially a straight line from the first terminator to the second terminator.

25. A virtual grid constructed by the method according to claim 1.

20. A wireless sensor node for constructing a virtual grid for a plurality of wireless sensor nodes of a sensor field, the node comprising:

if the node is an originator, a transmission module to flood the sensor field to identify a first terminator;

if the node is the first terminator, a transmission module to flood the sensor field to identify a second terminator; and

a decision making module to form a main communication path by selecting nodes between the first and second terminators;

wherein the virtual grid is constructed by flooding the sensor field such that each node in the sensor field is assigned virtual coordinates relative to the main communication path, the flooding originating from the nodes belonging to the main communication path.

21. The node according to claim 20, further comprising:

a pre-processing module to validate received packets from neighboring nodes; and

a dispatch module to classify received packets into one of three categories;

neighbor management, grid-construction, or pass-through.

22. A method for communicating information between a source and a sink via wireless sensor nodes of a sensor field, the method comprising:

flooding an interest of the sink to nodes in the field in the same row as the sink;

flooding an alert from the source to nodes in the field in the same column as the source, the alert including an indication that an event has occurred or that data has been collected; and

constructing a communication path between the source and the sink when the source and sink find each other.

23. The method according to claim 22, further comprising searching for a multi-hop path via a bridge across at least one column to match the source with the sink.

24. The method according to claim 22, further comprising flooding the interest from another sink until the flooding reaches a node already aware of the interest in order to scale down the extent of flooding.