System and methods of radio interference based localization in sensor networks

• US 20070042706A1
• Filed: 04/10/2006
• Published: 02/22/2007
• Est. Priority Date: 04/08/2005
• Status: Active Grant

• Current Assignee: Vanderbilt University
• Original Assignee: Vanderbilt University
• Inventors: Volgyesi, Peter, Molnar, Karoly, Dora, Sebestyen, Nadas, Andras, Kusy, Branislav, Ledeczi, Akos, Maroti, Miklos, Balogh, Gyorgy
• Granted Patent: US 7,558,583 B2
• Time in Patent Office: Days
• US Class Current: 455/3.10
• 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_i 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.

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, further comprising the step of performing a frequency tuning 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.

7. The method of claim 6, wherein the frequency tuning algorithm comprises the steps of:

a. 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;

b. 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

c. 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.

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

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

10. 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.

11. 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.

12. The method of claim 11, 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.

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

14. The method of claim 11, wherein the calibrating step is performed with a frequency tuning algorithm.

15. The method of claim 14, wherein the frequency tuning algorithm comprises the steps of:

a. 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;

b. 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

c. 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.

16. The method of claim 11, 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.

17. The method of claim 16, 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.

18. The method of claim 11, wherein each of the pair of signals comprises a sine wave.

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

20. The method of claim 19, 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.

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

22. 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 11.

23. 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₁, 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 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.

24. The system of claim 23, wherein the number N of spatially separated sensor nodes communicate to each other wirelessly.

25. The system of claim 23, wherein each of the number N of spatially separated sensor nodes comprises a radio chip.

26. The system of claim 25, wherein the radio chip is capable of transmitting a radio frequency signal in a predetermined frequency band at different power levels.

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

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

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

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

31. The system of claim 23, wherein the base station comprises a computer.

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

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

34. A method for radio interference based sensor localization, comprising the steps of:

a. creating an interference signal from a first transmitter and a second transmitter;

b. measuring phase offsets of the interference signal received by a first receiver and a second receiver, respectively; and

C. determining the locations of the first and second transmitters and the first and second receivers from the measured phase offsets.

35. The method of claim 34, wherein the first and second transmitters and the first and second receivers are spatially separated.

36. The method of claim 34, wherein the first and second transmitters and the first and second receivers communicate to each other wirelessly.

37. The method of claim 34, wherein the first and second transmitters are configured to transmit a pair of radio frequency signals having a frequency difference substantially close to zero.

38. 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 34.

39. A sensor network, comprising:

a. a first transmitter node and a second transmitter node; and

b. a plurality of nodes,

wherein the first transmitter node, the second transmitter node and the plurality of nodes are communicatable wirelessly, and when the first transmitter node and the second transmitter node transmit signals simultaneously at slightly different frequencies to form a composite signal, at least two of the plurality of nodes receive the composite signal and generate a relative phase offset, from which the relative locations of the nodes are determinable.

40. The sensor network of claim 39, wherein the nodes are spatially separated.