Virtual grid

• US 7,924,735 B2
• Filed: 05/20/2005
• Issued: 04/12/2011
• Est. Priority Date: 05/20/2005
• Status: Expired due to Fees

• Current Assignee: Agency For Science Technology and Research
• Original Assignee: Agency For Science Technology and Research
• Inventors: Ngoh, Lek Heng, Sun, Peng
• Primary Examiner(s): Shah; Chirag G
• Assistant Examiner(s): Shivers; Ashley L
• Application Number:
  US11/920,735
• Publication Number:
  US 20090285136A1
• Time in Patent Office: 2,153 Days
• Field of Search: None
• US Class Current: 370/252
• 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.

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