Data processing: measuring – calibrating – or testing – Measurement system – Orientation or position
Reexamination Certificate
2004-06-09
2008-12-02
Ramos-Feliciano, Eliseo (Department: 2857)
Data processing: measuring, calibrating, or testing
Measurement system
Orientation or position
C702S151000, C702S179000, C702S183000
Reexamination Certificate
active
07460976
ABSTRACT:
The present invention uses a Semidefinite Programming (SDP) relaxation based method for the position estimation problem in sensor networks wherein the original problem is converted into a convex optimization problem. Estimation errors can be calculated, such that the quality of the solution to the initial problem is known. The sensor network may be divided into clusters such that the position estimation problem and the computation work can be distributed. The distributed scheme is highly scalable. A network with thousands of sensors may be solved within several minutes.
REFERENCES:
patent: 5537119 (1996-07-01), Poore, Jr.
patent: 6064809 (2000-05-01), Braatz et al.
patent: 6704692 (2004-03-01), Banerjee et al.
patent: 2004/0250207 (2004-12-01), Gilbert et al.
Y. Alfakih, A. Khandani and H. Wolkowicz Solving Euclidean Distance Matrix Completion Problems via Semidefinite Programming.Comput. Optim. Appl., 12(13):13-20, Nov. 1999.
S. J. Benson, Y. Ye and X. Zhang, Solving Large-Scale Sparse Semidefinite Programs for Combinatorial Optimization.SIAM Journal on Optimization, 10(2): 443-461, 2000.
D. Bertsimas and Y. Ye. Semidefinite Relaxations, Multivariate Normal Distributions, and Order Statistics.Handbook of Combinatorial Optimization, 3:1-19, 1998.
S. Boyd, L. E. Ghaoui, E. Feron and V. Balakrishnan,Linear Matrix Inequalities in System and ControlTheory, SIAM., 1994.
N. Bulusu, J. Heidemnn, and D. Estrin, GPS-less Low-Cost Outdoor Localization for Very Small Devices. Technical report, Computer Science Department, University of Southern California, Apr. 2000.
L. Doherty, L. E. Ghaoui and S. J. Pister. Convex Position Estimation in Wireless Sensor Networks.In IEEE Infocom, vol. 3, pp. 1655-1663, Apr. 2001.
.D. Ganesan, B. Krishnamachari, A. Woo, D. Culler, D. Estrin, and S. Wicker. An Empirical Study of Epidemic Algorithms in Large Scale Multihop Wireless Networks. Technical Report, University of California, Los Angeles, 2002.
J. Hightower and G. Borriello. Location Systems for Ubiquitous Computing.IEEE Computer, 34(8): 57-66, Aug. 2001.
A. Howard, M. Mataric, and G. Sukhatme. Relaxation on a Mesh: a Formalism for Generalized Localization.In IEEE/RSJ Int'l Conf. on Intelligent Robots and Systems, vol. 3, pp. 1055-1060, Oct. 2001.
M. Laurent. Matrix Completion Problems.The Encyclopedia of Optimization, 3:221-229, 2001.
J. More and Z. Wu. Global Continuation for Distance Geometry Problems. SIAM Journal on Optimization., 7:814-836, 1997.
D. Niculescu and B. Nath. Ad Hoc Positioning System (APS). InIEEE Globecom(1), pp. 2926-2931, 2001.
C. Savarese, J. Rabay, and K. Langendoen. Robust Positioning Algorithms for Distributed Ad-Hoc Wireless Sensor Networks. InUSENIX Technical Annual Conference, Jun. 2002.
A. Savvides, C.-C. Han, and M. B. Srivastava. Dynamic Fine-Grained Localization in Ad-Hoc Networks of Sensors. InMobile Computing and Networking, pp. 166-179, 2001.
A. Savvides, H. Park, and M. B. Srivastava. The Bits and Flops of the N-Hop Multilateration Primitive for Node Localization Problems. InProceedings of the 1st ACM International Workshop on Wireless Sensor Networks and Applications, pp. 112-121. ACM Press. 2002.
Y. Shang, W. Ruml, Y. Zhang, and M. P. J. Fromherz. Localization From Mere Connectivity. InProceedings of the 4th ACM International Symposium on Mobile Ad Hoc Networking&Computing, pp. 201-212. ACM Press, 2003.
J. F. Sturm. Let Sedumi Seduce You, Oct. 2001. http://fewcal.kub.nl/sturm/software/sedumi.html.
G. Xue and Y. Ye. An Efficient Algorithm for Minimizing a Sum of Euclidean Norms with Applications.SIAM Journal on Optimization., 7:1017-1036, 1997.
Biswas Pratik
Ye Yinyu
Ramos-Feliciano Eliseo
Suarez Felix
The Board of Trustees of the Leland Stanford Jr. University
Wong Cabello Lutsch Rutherford & Brucculeri LLP
LandOfFree
Semi-definite programming method for ad hoc network node... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Semi-definite programming method for ad hoc network node..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Semi-definite programming method for ad hoc network node... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-4037024