276 J.Comput.Sci.Technol.,Mar.2010,Vol.25,No.2 2.1 Physical Measurements and Single-Hop The least squares method is used to assign a value to Positioning (o y)that minimizes This problem can be solved by a numerical solution to an over-determined Clearly,it is difficult,if not infeasible,to do localiza- linear system(251. tion without knowledge of the physical world.Accord ing to the capabilities of diverse hardwares,we classify the measuring techniques into six categories(from fine- grained to coarse-grained):location,distance,angle, area,hop count,and neighborhood,as shown in Fig.2. Fine-Grained Coarse-Grained Location Distance Angle Area Hop Count Neighbor- (a) (b) hood Fig.3.Trilateration.(a)Measuring distance to 3 reference nodes Ranging -Connectivity- (b)Ranging circles. Fig.2.Physical measurements. The over-determined linear system can be obtained Among them,the most powerful physical measure- as follows.Rearranging and squaring terms of the ac- tual distances,we have n such equations: ment is directly obtaining the position without any fur- ther computation.GPS is such a kind of infrastructure. x+7-d=2x0z+20贴-(x话+) The other five measurements are used in the scenarios of positioning an unknown node by given some refer- By subtracting out the n-th equation from the rest, ence nodes..The terms of“reference'”and“"unknown we have n-1 equations of the following form: nodes refer to the nodes being aware and being NOT aware of their locations,respectively.Distance and an- x+-x品-2-d+d哈=2(x-xn)x0+2(贴-n)0 gle measurements are obtained by ranging techniques which yields the linear relationship Hop count and neighborhood are basically based on ra- dio connectivity.In addition,area measurement relies Ax=B on either ranging or connectivity,depending on how the where A is an(n-1)x 2 matrix,such that the i-th row area constrains are formed. of A is [2(i-n)2(vi-Un)],x is the column vector 2.1.1 Distance Measurements representing the coordinates of the unknown location [zo yolT,and B is the (n-1)element column vector The distances from an unknown node to several ref- whose i--th term is(z号+f-x品-y-+d).Prac erences constrain the presence of this node,which is the tically,we cannot determine B,since the real distances basic idea of the so called multilateration.Fig.3 shows are not known to us,so computation is performed on an example of trilateration,a special form of multilat- B',which is the same as B with d substituting for eration which utilizes exact three references.A to-be- di.Now the least square solution is an estimate for located node (node 0)measures the distances from itself that minimizes Az'-B'2,which is provided by to three references (nodes 1,2,3).Obviously,node 0 '=(ATA)-1ATB'. should locate at the intersection of three circles centered So far,for distance-based positioning,the only thing at each reference position.The result of trilateration is omitted is how to measure distances in the physical unique as long as three references are non-linear. world.Many ranging techniques are proposed and de- Suppose the location of the unknown node is(ro,yo) veloped;among them,the radio signal strength based and it is able to obtain the distance estimates d,to the and time based ranging are two of the most widely used i-th reference node locating at (xi,yi),1 <i<n.Let ones in existing designs. di be the actual Euclidean distance to the i-th reference (a)Radio Signal Strength Based Distance Measure- node,i.e., ment Radio Signal Strength(RSS)based ranging tech- d:=V(x-x0)2+(-0)2 niques are based on the fact that the strength of radio signal diminishes during propagation.As a result,the The difference between the measured and the actual understanding of radio attenuation helps to map the distances can be represented by pi=d-di.Owing signal strength to the physical distance.In theory,ra- to ranging noises in di,Pi is often non-zero in practice. dio signal strengths diminish with distance according to276 J. Comput. Sci. & Technol., Mar. 2010, Vol.25, No.2 2.1 Physical Measurements and Single-Hop Positioning Clearly, it is difficult, if not infeasible, to do localiza￾tion without knowledge of the physical world. Accord￾ing to the capabilities of diverse hardwares, we classify the measuring techniques into six categories (from fine￾grained to coarse-grained): location, distance, angle, area, hop count, and neighborhood, as shown in Fig.2. Fig.2. Physical measurements. Among them, the most powerful physical measure￾ment is directly obtaining the position without any fur￾ther computation. GPS is such a kind of infrastructure. The other five measurements are used in the scenarios of positioning an unknown node by given some refer￾ence nodes. The terms of “reference” and “unknown” nodes refer to the nodes being aware and being NOT aware of their locations, respectively. Distance and an￾gle measurements are obtained by ranging techniques. Hop count and neighborhood are basically based on ra￾dio connectivity. In addition, area measurement relies on either ranging or connectivity, depending on how the area constrains are formed. 2.1.1 Distance Measurements The distances from an unknown node to several ref￾erences constrain the presence of this node, which is the basic idea of the so called multilateration. Fig.3 shows an example of trilateration, a special form of multilat￾eration which utilizes exact three references. A to-be￾located node (node 0) measures the distances from itself to three references (nodes 1, 2, 3). Obviously, node 0 should locate at the intersection of three circles centered at each reference position. The result of trilateration is unique as long as three references are non-linear. Suppose the location of the unknown node is (x0, y0) and it is able to obtain the distance estimates d 0 i to the i-th reference node locating at (xi , yi), 1 6 i 6 n. Let di be the actual Euclidean distance to the i-th reference node, i.e., di = p (xi − x0) 2 + (yi − y0) 2. The difference between the measured and the actual distances can be represented by ρi = d 0 i − di . Owing to ranging noises in d 0 i , ρi is often non-zero in practice. The least squares method is used to assign a value to (x0, y0) that minimizes Pn i=1 ρ 2 i . This problem can be solved by a numerical solution to an over-determined linear system[25] . Fig.3. Trilateration. (a) Measuring distance to 3 reference nodes. (b) Ranging circles. The over-determined linear system can be obtained as follows. Rearranging and squaring terms of the ac￾tual distances, we have n such equations: x 2 i + y 2 i − d 2 i = 2x0xi + 2y0yi − (x 2 0 + y 2 0 ). By subtracting out the n-th equation from the rest, we have n − 1 equations of the following form: x 2 i +y 2 i −x 2 n −y 2 n −d 2 i +d 2 n = 2(xi −xn)x0 + 2(yi −yn)y0 which yields the linear relationship Ax = B where A is an (n−1)×2 matrix, such that the i-th row of A is [2(xi − xn) 2(yi − yn)], x is the column vector representing the coordinates of the unknown location [x0 y0] T, and B is the (n − 1) element column vector whose i-th term is (x 2 i + y 2 i − x 2 n − y 2 n − d 2 i + d 2 n ). Prac￾tically, we cannot determine B, since the real distances are not known to us, so computation is performed on B 0 , which is the same as B with d 0 i substituting for di . Now the least square solution is an estimate for x 0 that minimizes kAx0 − B 0 k 2 , which is provided by x 0 = (A TA) −1A TB 0 . So far, for distance-based positioning, the only thing omitted is how to measure distances in the physical world. Many ranging techniques are proposed and de￾veloped; among them, the radio signal strength based and time based ranging are two of the most widely used ones in existing designs. (a) Radio Signal Strength Based Distance Measure￾ment Radio Signal Strength (RSS) based ranging tech￾niques are based on the fact that the strength of radio signal diminishes during propagation. As a result, the understanding of radio attenuation helps to map the signal strength to the physical distance. In theory, ra￾dio signal strengths diminish with distance according to