Method and apparatus for control and routing of wireless sensor networks

• US 7,304,976 B2
• Filed: 01/31/2005
• Issued: 12/04/2007
• Est. Priority Date: 10/13/2004
• Status: Active Grant

• Current Assignee: Virginia Tech Intellectual Properties, Inc.
• Original Assignee: Virginia Tech Intellectual Properties, Inc.
• Inventors: Hou, Yiwei T., Mao, Shiwen
• Primary Examiner(s): LE, DANH C
• Application Number:
  US11/045,287
• Publication Number:
  US 20060077918A1
• Time in Patent Office: 1,037 Days
• Field of Search: 370/338, 370/352, 370/315, 340/870.11, 455/562.1, 455/445
• US Class Current: 370/338
• CPC Class Codes: H01Q 1/246 specially adapted for base stations
• CPC Class Codes: H01Q 25/00 Antennas or antenna systems providing at least two radiating patterns arrangements for changing or varying the orientation or the shape of the directional pattern H01Q3/00
• CPC Class Codes: H04W 40/00 Communication routing or communication path finding
• CPC Class Codes: H04W 40/06 based on characteristics of available antennas
• CPC Class Codes: H04W 48/08 Access restriction or access information delivery, e.g. discovery data delivery signalling during connection H04W76/00
• CPC Class Codes: H04W 52/322 Power control of broadcast channels
• CPC Class Codes: H04W 64/00 Locating users or terminals or network equipment for network management purposes, e.g. mobility management
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks
• CPC Class Codes: H04W 88/04 adapted for relaying to or from another terminal or user
• CPC Class Codes: H04W 88/08 Access point devices
• CPC Class Codes: Y02D 30/00 Reducing energy consumption in communication networks
• CPC Class Codes: Y02D 30/70 in wireless communication networks

Abstract

A scalable, minimum node complexity, energy efficient, and error-resilient routing method for wireless sensor networks is described. The network is partitioned into regions by power controlled base station scans using a directional antenna. Routing is performed using only local location information and instructions received from the base station at each sensor node with minimum processing and control overhead, thus allowing simple, low-cost sensor designs. Sensors in the network provide to a base station reports of the condition of the sensors themselves, and these reports are analyzed by the base station to determine improved routing instructions, which are then provided to the sensor nodes in control messages. Each data packet is relayed in an interleaved, loop-free mesh of sectors toward the base station, making data delivery robust to sensor failures and transmission errors. The disclosure also contains descriptions for simple edge-based tasking, query, code distribution, and network programming for sensor nodes. The method is suitable for large-scale, dense sensor networks for detection, alarming, and monitoring applications.

Claims

1. A method for operating a wireless sensor network, comprising the steps of:

using a power controlled directional antenna by a base station to partition the network into a plurality of regions, each of a plurality of sensor nodes in the network determining its location in one of said regions from control messages received from said base station; and

forwarding to said base station data sensed by one of said sensor nodes, said data being contained in a packet generated by said data sensing node and including said location determined by said data sensing node, said packet being forwarded by a multi-hop process.

2. A method for operating a wireless sensor network as in claim 1, further comprising the steps of:

forwarding to said base station packets containing status reports of a condition of said sensor nodes in respective regions;

analyzing by said base station of said status reports; and

sending control messages from said base station to sensor nodes providing optimized routing instructions for packet forwarding by said sensor nodes, said optimization being responsive to said analysis of said status reports.

3. A method for operating a wireless sensor network as in claim 2, wherein said analyzing step determines energy consumption levels of sensor nodes by region and said routing instructions balance said energy consumption levels among regions.

4. A method for operating a wireless sensor network as in claim 3, wherein said analyzing step additionally identifies regions unreliable for forwarding and said routing instructions additionally bypass said unreliable regions.

5. A method for operating a wireless sensor network as in claim 2, wherein said analyzing step identifies regions unreliable for forwarding and said routing instructions bypass said unreliable regions.

6. A method for operating a wireless sensor network as in claim 1, wherein said packet is rebroadcast no more than once by any sensor node in said network.

7. A method for operating a wireless sensor network as in claim 6, wherein a sensor node rebroadcasting a received packet stores in a packet header queue a packet header extracted from said packet, said packet header containing a source region and a packet identifier, said packet being rebroadcast if said packet header is not already in said packet header queue.

8. A method for operating a wireless sensor network as in claim 7, wherein said sensor node is synchronized with a timing identifier received by said data sensing sensor node from said base station in a control message.

9. A method for operating a wireless sensor network as in claim 7, wherein said packet identifier is a timestamp applied to said packet by said data sensing sensor node, and said packet header is not in said packet header queue if the source region is not in any packet header in the queue or, if the source region is the same for a packet header, the timestamp is newer.

10. A method for operating a wireless sensor network as in claim 1, wherein said packet received by a sensor node from a broadcasting sensor node is only rebroadcast by said receiving sensor node if said receiving node is a) in a region of said broadcasting sensor node, b) in a region closer to said base station than said region of said broadcasting sensor node, or c) in a region that is configured by the base station to perform such broadcasting.

11. A method for operating a wireless sensor network as in claim 1, wherein said partitioning is accomplished by transmitting a sequence of control messages, each said transmission being in a direction from said base station corresponding to an ordinal sector number of adjacent beamwidths of said directional antenna and having a power level sufficient to reach sensor nodes at a distance from said base station corresponding to an ordinal ring number, each said sensor node having a location in a region relative to said base station defined by a sector number and a ring number, each said sensor node receiving more than one said control message determining said region of its location by selecting the lowest ring number and the highest sector number in said received messages.

12. A method for operating a wireless sensor network as in claim 11, further comprising the steps of

detecting a region containing no sensor nodes, said region being a connectivity hole, and

mitigating said connectivity hole.

13. A method for operating a wireless sensor network as in claim 12, wherein said detecting step further comprises the steps of

sending a control message to said region, and

waiting beyond a timeout period without receiving a response to said control message from a sensor node in said region.

14. A method for operating a wireless sensor network as in claim 12, wherein said mitigating step further comprises the step of repeating said partitioning step, wherein said sectors are shifted by a fraction of said beamwidth.

15. A method for operating a wireless sensor network as in claim 12, wherein said mitigating step further comprises the step of sending control messages to regions adjacent to said connectivity hole instructing sensor nodes in said regions how to rebroadcast around said connectivity hole.

16. A method for operating a wireless sensor network as in claim 1, wherein processing, storage and communication tasks required for control of the network are performed by said base station.

17. A method for operating a wireless sensor network as in claim 1, further comprising the step of sending control messages from said base station to said sensor nodes providing tasking instructions.

18. A method for operating a wireless sensor network as in claim 1, further comprising the step of sending control messages from said base station to said sensor nodes, said control messages containing code to reprogram the network.

19. A method for operating a wireless sensor network as in claim 1, further comprising the steps of:

sending a query message from said base station to sensor nodes in a region; and

receiving responses to said query message forwarded by said sensor nodes in said region.

20. A system for monitoring conditions in an area comprising:

sensor nodes dispersed throughout the area;

a base station for controlling said sensor nodes and receiving data packets generated by said sensor nodes, at least some of said data packets containing reports of conditions sensed by said sensor nodes,

wherein said base station uses a power controlled directional antenna to partition said area into a plurality of regions, each of said sensor nodes determining its location in one of said regions from control messages received from said base station, and

wherein each said data packet includes said location of a sensor node generating said data packet.

21. A system for monitoring conditions in an area as in claim 20,

wherein said packets contain status reports of a condition of said sensor nodes in respective regions;

wherein said packets are forwarded to said base station by a multi-hop process;

wherein said base station analyzes said status reports; and

wherein said base station sends control messages to said sensor nodes providing optimized routing instructions for packet forwarding by said sensor nodes, said optimization being responsive to said analysis of said status reports.

22. A system for monitoring conditions in an area as in claim 21, wherein said analysis determines energy consumption levels of sensor nodes by region and said routing instructions balance of said energy consumption levels among regions.

23. A system for monitoring conditions in an area as in claim 21, wherein said analysis identifies regions unreliable for forwarding and said routing instructions bypass said unreliable regions.