Fault-tolerant timeout communication protocol with sensor integration

• US 7,636,038 B1
• Filed: 02/05/2007
• Issued: 12/22/2009
• Est. Priority Date: 02/25/2003
• Status: Active Grant

• Current Assignee: Purdue Research Foundation (Purdue University)
• Original Assignee: Purdue Research Foundation (Purdue University)
• Inventors: Liu, Yan, Jeong, Wootae, Nof, Shimon Y.
• Primary Examiner(s): PHAM, TOAN NGOC
• Application Number:
  US11/671,200
• Time in Patent Office: 1,051 Days
• Field of Search: 340/506, 340/539.1, 340/539.16, 340/539.22, 340/539.24, 340/539.26, 340/517, 340/521, 340/501, 340/507, 707/104.1, 370/3.38, 370/401, 370/221, 370/310
• US Class Current: 340/506
• CPC Class Codes: H04L 67/12 specially adapted for proprietary or special-purpose networking environments, e.g. medical networks, sensor networks, networks in vehicles or remote metering networks
• CPC Class Codes: H04W 24/04 Arrangements for maintaining operational condition
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks

Abstract

A fault-tolerant timeout protocol for distributed sensor arrays and networks in which each sensor has a plurality of backup nodes, each of which is operable to send priority information which includes the product of the time needed for the backup node to transmit sensor information to a base station and the number of tasks offered to the backup node. In another embodiment, the base station stores the two values and calculates their product. In both cases, the lowest resulting value is used by the base station to select the backup node, which then sends backup sensor information. Another aspect of the present invention is a fault-tolerant sensor integration algorithm. The algorithm creates an abstract sensor defined as an interval having values above and below the reading of an associated physical sensor, and finds a range of values common to more than half of the abstract sensors. The algorithm obtains an output value based on the common range of values, and identifies the correct sensors, possibly faulty sensors, and faulty sensors by identifying the abstract sensors that include, respectively, (a) all of the common range, (b) part of the common range, and (c) none of the common range. A further aspect of the invention is a multi-hop information forwarding method for a wireless network. According to this method, a data source node transmits a signal to neighboring nodes among a plurality of distributed nodes, and each neighboring node which receives the signal from the source node transmits a reply signal which includes a weighted sum of factors including an energy factor and a distance factor for the neighboring node, the energy factor being indicative of the neighboring node'"'"'s energy level and the distance factor being indicative of its distance from the source node. A forwarding node is selected on the basis of the weighted sums, and the source node transmits a data packet to the selected forwarding node, where the data packet is received and retransmitted either to a data sink node, e.g., a base station, or to another forwarding node.

Claims

1. A fault-tolerant method of communicating sensor information, comprising:

providing a sensor architecture comprising a base station and a plurality of sensors associated with said base station, each sensor operable to communicate sensor information to said base station and having associated therewith a plurality of backup nodes;

detecting failed communication of sensor information from at least one sensor of said plurality of sensors to said base station;

sending task information representative of said failed communication to said backup nodes associated with said at least one sensor to request priority information therefrom;

generating priority information in each backup node which receives said task information;

selecting the backup node based on priority information received from backup nodes; and

prompting said selected backup node to send sensor information to said base station.

2. The method of claim 1, wherein said priority information for each backup node is based on a time needed for the backup node to transmit sensor information to said base station and the number of tasks offered to the backup node.

3. The method of claim 2, wherein said priority information for each backup node includes a product of a time needed for said backup node to transmit sensor information to said base station and the number of tasks offered to said backup node.

4. The method of claim 2, wherein each sensor sends its sensor information to said base station and to its backup nodes;

and

wherein said selected backup node forwards the sensor information from said at least one sensor to said base station in response to said request.

5. A fault-tolerant method of communicating sensor information, comprising:

providing a sensor architecture comprising a base station and a plurality of sensors associated with said base station, each sensor operable to communicate sensor information to said base station and backup sensor information to a plurality of associated backup nodes;

detecting failed communication of sensor information from at least one sensor of said plurality of sensors to said base station;

evaluating the ability of each backup node associated with said at least one sensor to provide backup sensor information to said base station upon detected failure of said at least one sensor, said evaluation being based on the time needed for said backup node to transmit sensor information to said base station and a number of tasks offered to said backup node; and

requesting that backup sensor information be sent to said base station from one of said backup nodes based on said evaluation.

6. The method of claim 5, wherein said evaluation includes calculating a product of a time needed for said backup node to transmit sensor information to said base station and the number of tasks offered to said backup node.

7. The method of claim 6, wherein said base station stores (a) the time needed for each backup node to transmit sensor information thereto and (b) the number of tasks offered to each backup node.

8. A fault-tolerant method of communicating and integrating sensor information, comprising:

providing a sensor architecture comprising a base station and a plurality of sensors associated with said base station, each sensor operable to communicate sensor information to said base station and having associated therewith at least one backup sensor;

sensing a failure to receive sensor information from a first sensor among said plurality of sensors within an established timeout period;

requesting sensor information from the backup sensor for said first sensor in response to said sensed failure; and

integrating sensor information from said sensors, said sensor integration including

creating an abstract sensor for each sensor based on a reading therefrom, each abstract sensor defined as an interval having values above and below the associated reading;

finding a range of values common to more than half of said abstract sensors;

obtaining an output value based on said common range of values; and

identifying correct sensors, possibly faulty sensors, and faulty sensors by identifying the abstract sensors that include, respectively, (a) all of said common range, (b) part of said common range, and (c) none of said common range.

9. The method of claim 8, wherein said output value is the average of the overall highest and lowest values in said common range of values.

10. The method of claim 8, wherein said output value is a weighted combination of values from subintervals of said common range of values.

11. The method of claim 8, wherein said abstract sensor intervals have a uniform tolerable variation from the respective associated readings.

12. The method of claim 11, wherein said sensor integration further includes identifying a plurality of subintervals within said common range, and identifying the number of sensors that include each subinterval.

13. The method of claim 12, wherein said sensor integration comprises:

sorting said abstract sensors into an ordered list;

finding the intersection N of the first X sensors in said ordered list, where X is greater than half the number of sensors;

creating at least one interval I from the current intersection N, with each interval I having an identified level corresponding to the number of sensors that include the interval, said creating step including dividing any preexisting interval I that is partially overlapped by the current N and incrementing the level of the overlapped portion of said preexisting interval I;

removing from said ordered list a sensor having a bound matching a bound of N; and

returning to said step of finding an intersection N if at least X abstract sensors remain in said ordered list.

14. A multi-hop information forwarding method for a wireless network having a plurality of distributed nodes operable as data source nodes and forwarding nodes, said method comprising:

transmitting a first signal from a first data source node to neighboring nodes among said plurality of distributed nodes;

transmitting a reply signal from each neighboring node which receives said first signal from said first source node, said reply signal including a weighted sum of factors including an energy factor and a distance factor for the neighboring node, said energy factor being indicative of the neighboring node'"'"'s energy level and said distance factor being indicative of its distance from said first source node;

selecting a forwarding node from among said neighboring nodes on the basis of said weighted sums;

transmitting a data packet from said first source node to said selected forwarding node; and

receiving said data packet at said selected forwarding node and retransmitting it.

15. The method of claim 14, wherein said distance factor for each neighboring node includes the ratio of the distance between said first source node and the neighboring node to the distance between said first source node and a data sink node.

16. The method of claim 15, wherein said energy factor for each neighboring node includes the ratio of remaining energy to initial energy for the node.

17. The method of claim 16, wherein said neighboring nodes calculate said weighted sum in response to said first signal from said data source.

18. The method of claim 17, wherein said weighted sum for each neighboring node is a weighted sum of said energy and distance factors and a third factor indicative of the probability of failure of node communication.

19. The method of claim 18, further comprising a direction criterion for selection of a forwarding node.