Numerical methods for large sensor network localization problems

大型传感器网络定位问题的数值方法

• 批准号: 22310089
• 负责人: KOJIMA Masakazu
• 金额: $ 9.57万
• 依托单位: Tokyo Institute of Technology
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (B)
• 财政年份: 2010
• 资助国家: 日本
• 起止时间: 2010 至 2012
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-22310089/
• 关键词: OR; 最適化; センサネットワーク; 最適化問題; 半正定値計画; 位置推定

Sensor network localization (SNL) problems have attracted considerable research interests for a broad spectrum of applications such as environmental monitoring, traffic control and structural assessment. The problem is to estimate the locations of n sensors of unknown positions using given distances and some m sensors of known positions (called anchors) in a sensor network of m+n sensors. Finding the solutions of this problem is known to be NP-hard. Thus, approximating the solution of this problem has been dealt with from many angles. In this project, we have studied numerical methods based on the semidefinite programming (SDP) relaxation．The SDP relaxation can provide approximate solutions with accuracy, but the computational cost of solving SNL problems by the SDP relaxation becomes expensive rapidly as their sizes increase. To avoid this difficulty, we fully exploited the sparsity which were involved in large scale SNL problems and improved the performance of the SDP solver SDPA. As a final product, we released a software package SFSDP that can solve large-scale sensor network localization problems in high speed.

传感器网络定位问题在环境监测、交通控制、结构评估等领域有着广泛的应用前景。问题是在一个由m+n个传感器组成的传感器网络中，利用给定的距离估计未知位置的n个传感器和已知位置的m个传感器（称为锚点）的位置。这个问题的求解是NP难的。因此，已经从许多角度处理了这个问题的近似解。在本项目中，我们研究了基于半定规划松弛的数值方法，半定规划松弛可以提供精确的近似解，但随着SNL问题规模的增加，用半定规划松弛求解SNL问题的计算量迅速增加。为了避免这一困难，我们充分利用了大规模SNL问题的稀疏性，并提高了SDP求解器SDPA的性能。作为最终产品，我们发布了一个软件包SFSDP，可以解决大规模的传感器网络定位问题，在高速。

项目成果

The geodesic diameter of polygonal domains.

多边形域的测地线直径。

• DOI: 10.1007/s00454-013-9527-8
• 发表时间: 2013
• 期刊: Discrete & Computational Geometry
• 影响因子: 0.8
• 作者: Sang Won Bae;Matias Korman;and Yoshio Okamoto
• 通讯作者: and Yoshio Okamoto

Exploiting Structured Sparsity in Large Scale Semidefinite Programming Problems

• DOI: 10.1007/978-3-642-15582-6_2
• 发表时间: 2010-09
• 作者: M. Kojima

An approach based on shortest path and connectivity consistency for sensor network localization problems

基于最短路径和连接一致性的传感器网络定位问题方法

• 发表时间: 2012
• 作者: Makoto Yamashita;I-Lin Wang
• 通讯作者: I-Lin Wang

Convex optimization approaches to maximally predictable portfolio selection Optimization

凸优化方法可最大程度地预测投资组合选择优化

• 发表时间: 2013
• 期刊: A Journal of Mathematical Programming and Operations Research
• 作者: 菊池卓弥;稲葉緑;田中健次;Junya Gotoh
• 通讯作者: Junya Gotoh

R.Hirade and N.Miyoshi Fluid limit analysis of FIFO and RR caching for independent reference models

R.Hirade 和 N.Miyoshi 独立参考模型的 FIFO 和 RR 缓存的流体限制分析

• 发表时间: 2012
• 期刊: Performance Evaluation
• 影响因子: 2.2
• 作者: D.Nakata;H.Shibata;Y.Shiratori;S.Kasai;N.Tsukada
• 通讯作者: N.Tsukada