Method and apparatus for locating devices
First Claim
1. A method of estimating the location of a device within a network of devices each of which forms a node of the network such that the device may communicate with any other node in the network either directly or indirectly via intermediate devices, the or each other device within the network with which the device may communicate directly being referred to as a neighbouring node, the method including the steps of:
- obtaining information specifying the location or estimated location of one or more of the neighbouring node or nodes;
measuring the distance from the device to said one or more neighbouring nodes;
iteratively modifying an estimated location of the device, so as to reduce an error function based on the inconsistency between the estimated location of the device and the location or estimated location of the or each of the one or more neighbouring nodes, as determined from the obtained information specifying the location or estimated location of the one or more neighbouring nodes, on the one hand and the measured distance or distances from the device to the or each of the one or more neighbouring nodes on the other hand; and
periodically determining whether or not to implement a reset procedure, on the basis of whether or not certain conditions are met, by which the estimated location of the device is reset to a new location in a manner which does not seek to reduce the error function in respect of the new location relative to the immediately preceding estimated location of the device, whereby the device can avoid getting its estimated location stuck in a position corresponding to a local minimum value of the error function.
1 Assignment
0 Petitions
Accused Products
Abstract
A method of obtaining positional information about individual wireless devices a1-a16, r1-r125 within a wireless ad-hoc network including a plurality of position determining devices r1-r125 which include means for estimating the distance between themselves and other similar devices which are within range. The method includes the steps of: calculating the hypothetical distance between a respective node'"'"'s estimated position and the estimated position of each of its neighbouring devices whose broadcast estimated position has been received and whose distance from the respective node has been measured comparing the calculated hypothetical distance with the measured distance; modifying the respective node'"'"'s estimated position so as to reduce an error function dependent upon the difference between the hypothetical and measured distances and periodically resetting the respective node'"'"'s estimated location to a new position in a manner which does not seek to reduce the error function within a single iteration so as to avoid the location from getting stuck in a local minimum value of the error function.
76 Citations
9 Claims
-
1. A method of estimating the location of a device within a network of devices each of which forms a node of the network such that the device may communicate with any other node in the network either directly or indirectly via intermediate devices, the or each other device within the network with which the device may communicate directly being referred to as a neighbouring node, the method including the steps of:
-
obtaining information specifying the location or estimated location of one or more of the neighbouring node or nodes;
measuring the distance from the device to said one or more neighbouring nodes;
iteratively modifying an estimated location of the device, so as to reduce an error function based on the inconsistency between the estimated location of the device and the location or estimated location of the or each of the one or more neighbouring nodes, as determined from the obtained information specifying the location or estimated location of the one or more neighbouring nodes, on the one hand and the measured distance or distances from the device to the or each of the one or more neighbouring nodes on the other hand; and
periodically determining whether or not to implement a reset procedure, on the basis of whether or not certain conditions are met, by which the estimated location of the device is reset to a new location in a manner which does not seek to reduce the error function in respect of the new location relative to the immediately preceding estimated location of the device, whereby the device can avoid getting its estimated location stuck in a position corresponding to a local minimum value of the error function. - View Dependent Claims (2, 4, 5, 6, 7)
-
-
3. A method as claimed in either preceding claim wherein the network is a wireless ad-hoc network, and wherein the device communicates with the or each of its neighbouring nodes in a wireless manner.
-
8. A device for forming a node within a network of similar devices, the device including locating means for estimating its location, the locating means including:
-
obtaining means for obtaining information specifying the location or estimated location of one or more neighbouring nodes;
distance measurement means for measuring the distance to said one or more neighbouring nodes; and
processing means for iteratively modifying an estimated location of the device, such as to reduce the inconsistency between the estimated location of the device and the location or estimated location of the one or more neighbouring nodes, as determined from the obtained information specifying the location or estimated location of the one or more neighbouring nodes, on the one hand and the measured distances to each of the one or more neighbouring nodes on the other hand;
said processing means further including means for determining whether or not to reset the estimated location of the device if certain conditions are met to a location determined according to a procedure which does not seek to reduce inconsistency in the current iteration, whereby the device can avoid getting its estimated location stuck in a local minimum value of inconsistency.
-
-
9. A method of obtaining positional information about individual wireless devices within a wireless ad-hoc network including a plurality of position determining devices in which each position determining device includes means for estimating the distance between itself and any other similar device forming part of the network which is within range, devices which are in range of one another hereinafter being referred to as neighbouring devices, the method including the steps of:
-
i) each position determining device receiving a broadcast message from each of its neighbouring devices specifying, if known, the respective neighbouring device'"'"'s position or estimated position;
ii) each position determining device attempting to measure its distance from each of its neighbouring devices;
iii) each position determining device determining its actual position or an initial estimated position and storing this information;
iv) each position determining device which does not know its actual position calculating the hypothetical distance between its estimated position and the position or estimated position of each neighbouring device whose broadcast position or estimated position has been received and whose distance from the respective node has been measured in step ii);
v) each position determining device which does not know its actual position comparing the hypothetical distance calculated in step iv) with the distance measured in step ii);
vi) each position determining device which does not know its actual position, evaluating an error function which depends on the difference between the hypothetical and measured distances;
vii) each position determining device which does not know its actual position determining whether or not to implement a reset procedure on the basis of whether or not certain conditions are met, by which the estimated location of the device is reset to a new location in a manner which does not seek to reduce the error function in respect of the new location relative to the current estimated location of the device, whereby the device can avoid getting its estimated location stuck in a position corresponding to a local minimum value of the error function;
viii) each position determining device which does not know its actual position modifying its estimated position, in the event that it is determined to not implement a reset procedure in step vii), so as to reduce the error function; and
ix) each position determining device broadcasting to each other similar device in range, if known, its actual position determined in step iii) or its modified estimated position determined in step vii) or viii).
-
Specification