System and methods of radio interference based localization in sensor networks

• US 7,558,583 B2
• Filed: 04/10/2006
• Issued: 07/07/2009
• Est. Priority Date: 04/08/2005
• Status: Expired due to Fees

• Current Assignee: Vanderbilt University
• Original Assignee: Vanderbilt University
• Inventors: Volgyesi, Peter, Molnar, Karoly, Dora, Sebestyen, Balogh, Gyorgy, Nadas, Andras, Kusy, Branislav, Ledeczi, Akos, Maroti, Miklos
• Primary Examiner(s): Appiah; Charles N
• Assistant Examiner(s): Karikari; Kwasi
• Application Number:
  US11/401,115
• Publication Number:
  US 20070042706A1
• Time in Patent Office: 1,184 Days
• Field of Search: 455/456.1, 455/73, 455/1, 455/39, 455/419, 455/418, 455/404.2, 455/414.2, 455/115.1, 455/115.2
• US Class Current: 455/456.1
• CPC Class Codes: G01S 5/0289 of multiple transceivers, e.g. in ad hoc networks
• CPC Class Codes: G01S 5/14 Determining absolute distances from a plurality of spaced points of known location

Abstract

A method for radio interference based sensor localization. In one embodiment, the method has the steps of creating an interference signal from a first transmitter and a second transmitter, measuring phase offsets of the interference signal received by a first receiver and a second receiver, respectively, and determining the locations of the first and second transmitters and the first and second receivers from the measured phase offsets.

Claims

1. A method for radio interference based sensor localization in a wireless sensor network, wherein the wireless sensor network has a plurality of spatially separated sensor nodes with each capable of transmitting and/or receiving a signal, comprising the steps of:

a. selecting a first sensor node and a second sensor node as a pair of transmitters and each of the remaining sensor nodes as a receiver in the wireless sensor network, respectively;

b. transmitting a first signal and a second signal from the selected first sensor node and the selected second sensor node, respectively, to the wireless sensor network, wherein the first signal has a frequency, f₁, and the second signal has a frequency, f₂, the frequencies f₁ and f₂ being substantially close to each other such that a superposition of the first signal and the second signal in a position of space where a receiver is located results in an interference signal;

c. using the interference signal received by each of the receivers to estimate a phase offset of the received interference signal at the corresponding receiver, respectively;

d. obtaining a difference of the phase offsets of the interference signal for a pair of receivers;

e. calculating a distance range between the pair of transmitters and the corresponding pair of receivers from the obtained difference of phase offsets of the interference signal for the pair of receivers;

f. repeating steps (d) and (e) for the remaining receivers to obtain a set of the distance ranges; and

g. localizing relative positions of the plurality of spatially separated sensor nodes in the wireless sensor network from the set of the distance ranges,

wherein the method further comprises the step of performing a frequency tuninci algorithm to determine a radio frequency setting for the pair of transmitters to transmit the first and second signals with a frequency difference substantially close to zero, and wherein performing the frequency tuning algorithm comprises the steps of;

(i) transmitting a first signal at a frequency varied at a fine-grain step and a second signal at a fixed frequency from a first and second transmitters of the pair of transmitters, respectively;

(ii) analyzing a frequency of the interference signal received by a receiver to determine the frequency of the first signal for which the frequency of the interference signal substantially close to zero, wherein the frequency of the interference signal is coincident with the frequency difference of the first signal and the second signal; and

(iii) propagating information of the analyzed frequency back to the first transmitter by the receiver, thereby causing the first transmitter to determine the radio frequency setting of the pair of transmitters for which the frequency of the interference signal is within a predetermined range.

2. The method of claim 1, wherein the distance range is a function of distances between the pair of transmitters and the corresponding pair of receivers.

3. The method of claim 1, wherein the frequency f₁ of the first signal and the frequency f₂ of the second signal are in the range of radio frequency from about 3 Hz to about 3,000 GHz.

4. The method of claim 1, further comprising the step of calibrating the pair of transmitters to simultaneously transmit the first signal and the second signal, respectively.

5. The method of claim 1, further comprising the step of synchronizing start times of signal transmissions and/or receptions at different sensor nodes of the wireless sensor network before a sensor node transmits and/or receives a signal at a predetermined frequency.

6. The method of claim 1, wherein the localizing step is performed with a genetic algorithm.

7. The method of claim 1, wherein the selecting step is performed with a base station.

8. Software stored on a computer readable medium for causing a computing system to perform radio interference based sensor localization in a wireless sensor network according to claim 1.

9. A method for radio interference based sensor localization in a wireless sensor network, wherein the wireless sensor network has a plurality of spatially separated sensor nodes with each capable of transmitting and/or receiving a signal, comprising the steps of:

a. selecting a pair of sensor nodes from a group of sensor nodes as a pair of transmitters and each of the remaining sensor nodes in the group of sensor nodes as a receiver, respectively, wherein the group of sensor nodes is selected from the wireless sensor network such that the sensor nodes in the group are located within a spatial range;

b. scheduling transmission times for the pair of transmitters to transmit a pair of signals, wherein the pair of signals create an interference signal in a position of space where a receiver is located, and wherein the interference signal has an interference range coincident with the spatial range;

c. calibrating the pair of transmitters to simultaneously transmit the pair of signals at frequencies within a radio frequency setting at the scheduled transmission times, wherein the frequencies of the pair of signals vary according to a fine-grain step at different transmission times;

d. transmitting the pair of signals at the frequencies from the pair of transmitters at the scheduled transmission times;

e. analyzing received signal strength indicator (RSSI) samples of the interference signal at each of the receivers so as to estimate the frequency and phase offset of the interference signal, respectively;

f. obtaining a difference of the phase offsets of the interference signal for a pair of receivers;

g. calculating a distance range between the pair of transmitters and the pair of receivers from the obtained difference of phase offsets of the interference signal for each pair of receivers to obtain a set of the distance ranges; and

h. localizing relative positions of the group of sensor nodes in the wireless sensor network from the set of the distance ranges,

wherein the calibrating step is performed with a frequency tuning algorithm, and wherein performing the frequency tuning algorithm comprises the steps of;

(i) transmitting a first signal at a frequency varied at a fine-grain step and a second signal at a fixed frequency from a first and second transmitters of the pair of transmitters, respectively;

(ii) analyzing a frequency of the interference signal received by a receiver to determine the frequency of the first signal for which the frequency of the interference signal substantially close to zero, wherein the frequency of the interference signal is coincident with the frequency difference of the first signal and the second signal; and

(iii) propagating information of the analyzed frequency back to the first transmitter by the receiver, thereby causing the first transmitter to determine the radio frequency setting of the pair of transmitters for which the frequency of the interference signal is within a predetermined range.

10. The method of claim 9, further comprising the step of repeating steps (a)-(h) for the rest of the plurality of spatially separated sensor nodes in the wireless sensor network.

11. The method of claim 9, wherein the distance range is a function of distances between the pair of transmitters and the corresponding pair of receivers.

12. The method of claim 9, further comprising the step of synchronizing the group of sensor nodes to a common time base so as to align start times of signal transmissions from the pair of transmitters and signal receptions by the receivers of the group of sensor nodes.

13. The method of claim 12, wherein the synchronizing step comprises the steps of:

a. initializing one of the pair of transmitters to broadcast a radio message to the rest of the group of sensor nodes, wherein the radio message contains information of the other transmitter, signal transmission powers, a type of measurement, and a time instant in the local time of the broadcasting transmitter when the measurement is started and is accompanied with a timestamp;

b. converting the arrival timestamp of the radio message at each receiver to the local time of the receiver, respectively;

c. setting up a local timer by the converted local time; and

d. re-broadcasting the converted local time.

14. The method of claim 9, wherein each of the pair of signals comprises a sine wave.

15. The method of claim 9, wherein the localizing step is performed with a genetic algorithm.

16. The method of claim 15, wherein the genetic algorithm comprises the steps of:

a. generating a population of population-size random solutions;

b. selecting a subset of population-size solutions randomly from the solutions;

c. evaluating each solution in the subset using an error function, wherein the error function is defined over the node localizations;

d. sorting the solutions of the subset according to errors;

e. removing the worst 20% of the solutions of the subset;

f. generating new solutions by selecting random parents from the best 20% of the rest of the subset and applying genetic operators on the parents; and

g. repeating steps (b)-(f) until solutions for the relative localizations of the nodes are found.

17. The method of claim 9, wherein the selecting, scheduling, calculating and localizing steps are performed with a base station.

18. Software stored on a computer readable medium for causing a computing system to perform radio interference based sensor localization in a wireless sensor network according to claim 9.

19. A system for radio interference based sensor localization, comprising:

a. a sensor network having a number, N, of spatially separated sensor nodes, N being an integer, wherein the number N of spatially separated sensor nodes have a first transmitter node and a second transmitter node for transmitting a first signal and a second signal, respectively, to the sensor network, and (N-2) receiver nodes, wherein the first signal has a frequency, f_1, and the second signal has a frequency, f_2, the frequencies f₁ and f₂ being substantially close to each other such that a superposition of the first signal and the second signal in a position of space where a receiver node is located results in an interference signal; and

b. a base station for communicating with the number N of spatially separated sensor nodes in the sensor network and processing information received from the number N of spatially separated sensor nodes so as to localize the number N of spatially separated sensor nodes,

wherein the number N of spatially separated sensor nodes communicate to each other wirelessly,

wherein each of the number N of spatially separated sensor nodes comprises a radio chip,

and wherein the radio chip is capable of transmitting a radio frequency signal in a predetermined frequency band at different power levels. frequency signal in a predetermined frequency band at different power levels.

20. The system of claim 19, wherein the radio chip is capable of transmitting the radio frequency signal with a short-term stability of the frequency.

21. The system of claim 20, wherein the radio chip is capable of tuning the frequency of the radio frequency signal in fine-grain steps.

22. The system of claim 21, wherein the radio chip is capable of precisely capturing the interference signal.

23. The system of claim 19, wherein each of the first and second signals comprises a radio frequency wave.

24. The system of claim 19, wherein the base station comprises a computer.

25. The system of claim 19, wherein the number N of spatially separated sensor nodes are located in a 2-dimension configuration.

26. The system of claim 19, wherein the number N of spatially separated sensor nodes are located in a 3-dimension configuration.