Data processing: measuring – calibrating – or testing – Measurement system – Orientation or position
Reexamination Certificate
2011-06-28
2011-06-28
Feliciano, Eliseo Ramos (Department: 2857)
Data processing: measuring, calibrating, or testing
Measurement system
Orientation or position
C702S152000, C702S179000, C370S254000, C370S255000, C455S456100
Reexamination Certificate
active
07970574
ABSTRACT:
Adaptive rule-based methods to solve localization problems for ad hoc wireless sensor networks are disclosed. A large problem may be solved as a sequence of very small subproblems, each of which is solved by semidefinite programming relaxation of a geometric optimization model. The subproblems may be generated according to a set of sensor/anchor selection rules and a priority list. The methods scale well and provide improved positioning accuracy. A dynamic version may be used for estimating moving sensors locations in a real-time environment. The method may use dynamic distance measurement updates among sensors, and utilizes subproblem solving for static sensor localization. Methods to deploy sensor localization algorithms in clustered distributed environments are also provided, permitting application to arbitrarily large networks. In addition, the methods may be used to solve sensor localizations in 2D or 3D space. A preprocessor may be used for localization of networks without absolute position information.
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: 7006944 (2006-02-01), Brand
patent: 7460976 (2008-12-01), Ye et al.
patent: 2004/0073360 (2004-04-01), Foxlin
patent: 2004/0250207 (2004-12-01), Gilbert et al.
patent: 2005/0080924 (2005-04-01), Shang et al.
patent: 2006/0039300 (2006-02-01), Ogier et al.
Pratik Biswas, Yinyu Ye, A Distributed Method for Solving Semidefinite Programs Arising fromAd Hoc Wireless Sensor Network Localization, Oct. 30, 2003, Electrical Engineering, Stanford University, Stanford, CA 94305, pp. 1-18.
James Aspnes, On the Computational Complexity of Sensor Network Localization, Apr. 7, 2004, Department of Computer Science, Yale University, New Haven, CT 06520-8285, USA.
Juan Liu, Information-Directed Routing in Ad Hoc Sensor Networks, Sep. 19, 2003, WSNA '03, San Diego, California, USA.
Lichun Bao, Topology Management in Ad Hoc Networks, Jun. 1-3, 2003, MobiHoc, Annapolis, Maryland, USA.
Jian Ma, Anchor-free Localization with Refinement in Sensor Networks, May 27, 2004, Department of Computer Science Hong Kong University of Science and Technology, Clearwater Bay, Kowloon, Hong Kong.
Ibriq et al., “Cluster-Based Routing in Wireless Sensor Networks: Issues and Challenges”, 2004, SPECTS, pp. 759-766.
Ji et al., “Sensor Positioning in Wireless Ad-hoc Sensor Networks Using Multidimensional Scaling”, 2004, IEEE INFOCOM, pp. 1-10.
Alfakih, et al.; “Solving Euclidean distance matrix completion problems via semidefinite programming;” Comput. Optim. Appl., 12(1-3) (1999), pp. 13-30. Computational optimization—a tribute to Olvi Mangasarian, Part I.
Benson, et al.; “Solving Large-Scale Sparse Semidefinite Programs for Combinatorial Optimization;” SIAM Journal on Optimization; 10(2): 443-461, 2000.
Bertsimas, et al.; “Semidefinite Relaxations, Multivariate Normal Distributions, and Order Statistics;” Handbook of Combinatorial Optimization; 3:1-19, 1998.
Biswas, et al.; “Semidefinite Programming for Ad Hoc Wireless Sensor Network Localization;” IPSN 2004; Berkeley, CA; Apr. 26-27, 2004.
Biswas, et al.; “A Distributed Method for Solving Semidefinite Programs Arising from Ad Hoc Wireless Wensor Network Localization;” Working Paper, Departments of EE and MS&E, Stanford University, CA, Oct. 30, 2003.
Boyd, et al.; “Linear Matrix Inequalities in System and Control Theory;” SIAM, Philadelphia, 1994.
Bulusu, et al.; “GPS-less low cost outdoor localization for very small devices;” Technical Report 00-729, Computer Science Department, University of Southern California, CA, Apr. 2000.
Capkun, et al.; “GPS—Free Positioning in Mobile Ad-Hoc Networks;” Proceedings of the 34th Hawaii International Conference On System Sciences, 2001.
Carter, et al.; “Spaseloc: An Adaptive Subproblem Algorithm For Scalable Wireless Sensor Network Localization;” SIAM J. On Optimization, Submitted Dec. 2004.
Cha; “Electronic Tracking Is Finding New Uses;” San Jose Mercury News, Sunday, Jan. 16, 2005.
Culler, et al.; “Wireless sensor networks;” Communications of the ACM, 47(6), Jun. 2004, pp. 30-33.
Doherty, et al.; “Convex Position Estimation in Wireless Sensor Networks;” Proc. IEEE Infocom 2001, Anchorage, AK, Apr. 2001, pp. 1655-1663.
Drozdiak; “Automotive Alternative: In German Port City, Cheap, Efficient Car Rentals Catch On;” Washington Post, Sep. 20, 1999, p. A09.
Ganesan, et al.; “An Empirical Study Of Epidemic Algorithms in Large-Scale Multihop Wireless Networks;” Report UCLA/CSD-TR-02-0013, Computer Science Department, UCLA, CA, 2002.
Heinzelman, et al.; “An Application-Specific Protocol Architecture for Wireless Microsensor Networks;” IEEE Transactions on Wireless Communications, 1(4) (Oct. 2002).
Hightower, et al.; “Location Systems for Ubiquitous Computing;” IEEE Computer, 34(8) (2001), pp. 57-66.
Howard, et al.; “Relaxation on a Mesh: A Formalism for Generalized Localization;” Proc. IEEE/RSJ International Conf. on Intelligent Robots and Systems (IROS01), 2001, pp. 1055-1060.
Jin, et al.; “Scalable algorithms for sensor localization;” First-Equal Prize Winner in Showcase Your Research, Stanford-Berkeley Innovators' Challenge competition, Stanford University, Apr. 19, 2005.
Laurent; “Matrix Completion Problems;” The Encyclobedia of Optimization; 3:221-229, 2001.
Lawlor; “Small systems, big business;” Signal Magazine, Jan. 2005.
Lu; “Coordination Layer Control and Decision Making for Automated Ground Vehicles;” Proceedings of the American Control Conference, Anchorage, May 8-10, 2002, pp. 3034-3039.
McMillan; “Car Sharing's Time Comes” CNN Money, Jul. 19, 2000.
Moore, et al.; “Robust Distributed Network Localization with Noisy Range Measurements;” SenSys'04, Nov. 3-5, 2004, Baltimore, Maryland, USA.
Moré, et al.; “Distance Geometry Optimization For Protein Structures;” J. Global Optim., 15(3) (1999), pp. 219-234.
Moré, et al.; “Global Continuation for Distance Geometry Problems;” SIAM Journal on Optimization; 7:814-836, 1997.
Niculescu, et al.; “Ad Hoc Positioning System;” IEEE GlobeCom, Nov. 2001, pp. 2926-2931.
Niculescu, et al.; “DV Based Positioning in Ad Hoc Networks;” Kluwer Journal of Telecommunicaton Systems, 2003, pp. 267-280.
Ricadela; “Sensors Everywhere: A ‘bucket brigade’ of tiny, wirelessly networked sensors someday may be able to track anything, anytime, anywhere;” Information Week, Jan. 24, 2005.
Savarese, et al.; “Robust Positioning Algorithm for Distributed Ad Hoc Wireless Sensor Networks;” USENIX Technical Annual Conf., Monterey, CA, Jun. 2002.
Savvides, et al.; “Dynamic Fine-Grained Localization in Ad Hoc Networks of Sensors;” ACM/IEEE International Conf. on Mobile Computing and Networking (MOBICON), Jul. 2001, pp. 166-179.
Savvides, et al.; “The Bits and Flops of the N-Hop Multilateration Primitive for Node Localization Problems;” 1st ACM International Workshop on Wireless Sensor Networks and Applications (WSNA'02); Atlanta, GA, 2002; ACM Press; pp. 112-121.
Shang, et al.; “Localization From Mere Connectivity;” MobiHoc 2003, Anapolis, MD, Jun. 2003, ACM Press.
Singh, et al.; “Wireless LAN Performance Under Varied Stress Conditions in Vehicular Traffic Scenarios;” Technical Report, Department of Electrical Engineering, Stanford University, CA, and Robert Bosch Coorporation, Research and Technology Center, Palo Alto, CA.
So, et al.; “Theory of Semidefinite Programming for Sensor Network Localization;” Stanford University, CA, 2004, to appear in SODA 2005.
Sturm; “Let SeDuMi Seduce you too!” http://fewcal.kub.nl/stu
Feliciano Eliseo Ramos
Ngon Ricky
The Board of Trustees of the Leland Stanford Jr. University
Wong Cabello Lutsch Rutherford & Brucculeri LLP
LandOfFree
Scalable sensor localization for wireless sensor networks does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Scalable sensor localization for wireless sensor networks, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Scalable sensor localization for wireless sensor networks will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2720934