Hierarchical routing in ad-hoc networks

• US 20060176863A1
• Filed: 08/13/2004
• Published: 08/10/2006
• Est. Priority Date: 09/09/2003
• Status: Abandoned Application

• Current Assignee: British Telecommunications PLC (BT Group PLC)
• Original Assignee: British Telecommunications PLC (BT Group PLC)
• Inventors: Robinson, David, Tateson, Jane E`, Floyd, Michael A
• Application Number:
  US10/568,496
• Publication Number:
  US 20060176863A1
• Time in Patent Office: Days
• US Class Current: 370/338
• CPC Class Codes: H04L 45/04 Interdomain routing, e.g. hierarchical routing
• CPC Class Codes: H04L 45/124 using a combination of metrics
• CPC Class Codes: H04L 45/44 Distributed routing
• CPC Class Codes: H04W 40/02 Communication route or path selection, e.g. power-based or shortest path routing
• CPC Class Codes: H04W 40/10 based on available power or energy
• 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: Y02D 30/70 in wireless communication networks

Abstract

A number of data collection devices (10, 20, 30, 40, 50, 60, 70, 80) are free to move relative to each other through their environment, collecting data from their environment. They form an ad hoc wireless network (19, 29, 39, 49, etc) in which data collected by a device (20) (either by its own sensors (23), or relayed from another device (10)) is transmitted to a destination (90) either directly or by means of one or more other devices (30). The destination (90) collects data collected by the mobile terminals (10, 20, 30 etc) for subsequent processing. The wireless links (19, 29, 39 etc) between them have to re-arranged in order to provide the optimum network. Each device (20, 30) defines a scalar status value determined by factors including remaining battery life and amount of data in the buffer. The devices exchange information about their status values. Each device will only forward payload data to other devices having lower status values than its own.

Claims

1. A data relay device, the device having

receiving means for receiving payload data from a data source,

a buffer for storing payload data for subsequent transmission,

means for receiving status data from similar devices,

status data generation means for generating status data, the status data being derived from the quantity of data in the buffer store and the status data received from other devices, and comprising data relating to

the separation of the device from other devices,

the quantity of data in the buffer store

means for determining a scalar status value determined by the quantity of data stored in the buffer and its separation from nearby sensors,

status transmitter means for transmitting the status value to other devices

selection means for identifying, from the status data received from other devices, a receiving device having a status value which varies from its own status value in a manner indicative that payload data may be forwarded to it, and

payload transmission means for transmitting the payload data to the identified receiving device.

2. A data relay device according to claim 1, comprising means for receiving payload data transmitted by other similar devices.

3. A data relay device according to claim 1, further comprising a data source.

4. A data relay device according to claim 1, wherein the selection means is arranged to only identify a suitable receiving device if the scalar status value meets one or more threshold criteria.

5. A device according to claim 4, wherein a threshold criterion is that the remaining battery power is at least sufficient to transmit all the data currently in the buffer.

6. A device according to claim 4, having means for selecting a threshold criterion as a function of elapsed time from a predetermined start point.

7. A data relay device according to any claim 1, further comprising condition-monitoring means for monitoring the expected lifetime of the device, and adjusting the scalar status value accordingly.

8. A device according to claim 1, wherein the separation between devices is determined from the power required to make a transmission between them.

9. A device according to claim 1, comprising means for determining the power that would be required to transmit payload data to an identified receiving device, and means for generating a scalar status value related to that power requirement.

10. A device according to claim 9, wherein the identified receiving device on which the power determination is based is the device selected for transmission on a previous determination.

11. A device according to claim 9, wherein the scalar status value h is determined by the value (N+k) C/B

where N=number of packets of data currently in the buffer

B=battery level

C=power requirement of forwarding to the identified receiving device. k is a constant.

12. A method of operating a plurality of data relay devices, comprising:

collecting data in buffer stores in one or more such devices,

exchanging status data between the devices, the status data comprising data relating to

the separation between the devices,

the quantity of data in their buffer stores

each device defining, from the status data, a scalar status value determined by the quantity of data stored in the buffer and its separation from other sensors

transmitting the status value to other devices and receiving the status values of other devices

identifying, from the status data received from other devices, a receiving device having a status value which varies from its own status value in a manner indicative that payload data may be forwarded to it, and

transmitting the payload data to the identified receiving device.

13. A method according to claim 12, wherein data is only transmitted from a first device to a second device located in its forwarding direction if the scalar status value derived from the status data meets one or more predetermined threshold criteria.

14. A method according to claim 13, wherein a threshold criterion is that the remaining battery power is at least sufficient to transmit all the data currently in the buffer.

15. A method according to claim 12, wherein the status data includes a measure of the expected lifetime of the device.

16. A method according to claim 12, wherein payload data is transmitted, by means of one or more of the wireless relay devices, to a target sink device defined by a predetermined scalar status value.

17. A method according to claim 12, wherein the power that would be required to transmit payload data to an identified receiving device is determined, and a scalar status value is generated related to that power requirement.

18. A method according to claim 17, wherein the identified receiving device on which the power determination is based is the device selected for transmission on a previous determination.

19. A method according to claim 17, wherein the scalar status value h is determined by the value (N+k) C/B

where N=number of packets of data currently in the buffer

B=battery level

C=power requirement of forwarding to the identified receiving device k is a constant.