July  2014, 10(3): 817-826. doi: 10.3934/jimo.2014.10.817

A DC programming approach for sensor network localization with uncertainties in anchor positions

1. 

School of Built Environment, Curtin University, Bentley, 6102, WA, Australia

2. 

School of Science, Information, Technology and Engineering, University of Ballarat, Mt Helen, 3350, Victoria, Australia, Australia

Received  November 2012 Revised  March 2013 Published  November 2013

The sensor network localization with uncertainties in anchor positions has been studied in this paper. We formulate this problem as a DC (difference of two convex functions) programming. Then, a DC programming based algorithm has been proposed to solve such a problem. Simulation results obtained by our proposed method are better performance than those obtained by existing ones.
Citation: Changzhi Wu, Chaojie Li, Qiang Long. A DC programming approach for sensor network localization with uncertainties in anchor positions. Journal of Industrial & Management Optimization, 2014, 10 (3) : 817-826. doi: 10.3934/jimo.2014.10.817
References:
[1]

S. Baek and B. D. Choi, Performance analysis of power save mode in IEEE 802.11 infrastructure wireless local area network,, J. Ind. Manag. Optim., 5 (2009), 481. doi: 10.3934/jimo.2009.5.481.

[2]

P. Biswas, T. C. Liang, K. C. Toh, C. T. Wang and Y. Ye, Semidefinite programming approaches for sensor network localization with noisy distance measurements., IEEE Trans. Auto. Sci. Eng., 3 (2006), 360.

[3]

H. Cho and G. Hwang, Optimal design and analysis of a two-hop relay network under Rayleigh fading for packet delay minimization,, J. Ind. Manag. Optim., 7 (2011), 607. doi: 10.3934/jimo.2011.7.607.

[4]

T. Pham Dinh and H. A. Le Thi, Convex analysis approach to d.c. programming: Theory, algorithms and applications,, Acta Math. Vietnam., 22 (1997), 289.

[5]

D. Y. Gao, Sufficient conditions and perfect duality in nonconvex minimization with inequality constraints,, J. Ind. Manag. Optim., 1 (2005), 53. doi: 10.3934/jimo.2005.1.53.

[6]

K. C. Ho, X. Lu and L. Kovavisaruch, Source localization using TDOA and FDOA measurements in the presence of receiver location errors: Analysis and solution,, IEEE Trans. Signal Process., 55 (2007), 684. doi: 10.1109/TSP.2006.885744.

[7]

A. Jakoby, J. Boldberg and H. Messer, Source localization in shallow water in the presence of sensor location uncertainty,, IEEE J. Ocean. Eng., 25 (2000), 331.

[8]

S. Kim, M. Kojima and H. Waki, Exploiting sparsity in SDP relaxation for sensor network localization., SIAM J. Optim., 20 (2009), 192. doi: 10.1137/080713380.

[9]

K. W. K. Lui, W.-K. Ma, H. C. So and F. K. W. Chan, Semi-definite programming algorithms for sensor network node localization with uncertainties in anchor positions and/or propagation speed,, IEEE Trans. Signal Process., 57 (2009), 752. doi: 10.1109/TSP.2008.2007916.

[10]

J. More and Z. Wu, Distance geometry optimization for protein structures,, J. Glob. Optim., 15 (1999), 219. doi: 10.1023/A:1008380219900.

[11]

G. Nalan, L. T. H. An and M. Moeini, Robust investment strategies with discrete asset choice constraints using dc programming,, Optim., 59 (2010), 45. doi: 10.1080/02331930903500274.

[12]

P. Oguz-Ekim, J. Gomes, J. Xavier and P. Oliveira, Robust localization of nodes and time-recursive tracking in sensor networks using noisy range measurements,, IEEE Trans. Signal Process., 59 (2011), 3930. doi: 10.1109/TSP.2011.2153848.

[13]

T. K. Pong and P. Tseng, (Robust) Edge-based semidefinite programming relaxation of sensor network localization,, Math. Program., 130 (2011), 321. doi: 10.1007/s10107-009-0338-x.

[14]

Q. J. Shi, C. He, H. Y. Chen and L. G. Jiang, Distributed wireless sensor network localization via sequential greedy optimization algorithm,, IEEE Trans. Signal Proc., 58 (2010), 3328. doi: 10.1109/TSP.2010.2045416.

[15]

A. S. Ta, L. T. H. An, D. Khadraoui and P. D. Tao, Solving Partitioning-Hub Location-Routing Problem using DCA., J. Ind. Manag. Optim., 8 (2012), 87. doi: 10.3934/jimo.2012.8.87.

[16]

H. A. Le Thi and T. Pham Dinh, The DC (difference of convex functions) Programming and DCA revisited with DC models of real world nonconvex optimization problems,, Annals of Operations Research, 133 (2005), 23. doi: 10.1007/s10479-004-5022-1.

[17]

P. Tseng, Second-order cone programming relaxation of sensor network localization,, SIAM J. Optim., 18 (2007), 156. doi: 10.1137/050640308.

[18]

Z. Wang, S. Zheng, Y. Ye and S. Boyd, Further relaxations of the semidefinite programming approach to sensor network localization,, SIAM J. Optim., 19 (2008), 655. doi: 10.1137/060669395.

[19]

Z. B. Wang, S. C. Fang, D. Y. Gao and W. X. Xing, Global extremal conditions for multi-integer quadratic programming,, J. Ind. Manag. Optim., 4 (2008), 213. doi: 10.3934/jimo.2008.4.213.

[20]

X. Xiao, J. Gu, L. Zhang and S. Zhang, A sequential convex program method to DC program with joint chance constraints,, J. Ind. Manag. Optim., 8 (2012), 733. doi: 10.3934/jimo.2012.8.733.

show all references

References:
[1]

S. Baek and B. D. Choi, Performance analysis of power save mode in IEEE 802.11 infrastructure wireless local area network,, J. Ind. Manag. Optim., 5 (2009), 481. doi: 10.3934/jimo.2009.5.481.

[2]

P. Biswas, T. C. Liang, K. C. Toh, C. T. Wang and Y. Ye, Semidefinite programming approaches for sensor network localization with noisy distance measurements., IEEE Trans. Auto. Sci. Eng., 3 (2006), 360.

[3]

H. Cho and G. Hwang, Optimal design and analysis of a two-hop relay network under Rayleigh fading for packet delay minimization,, J. Ind. Manag. Optim., 7 (2011), 607. doi: 10.3934/jimo.2011.7.607.

[4]

T. Pham Dinh and H. A. Le Thi, Convex analysis approach to d.c. programming: Theory, algorithms and applications,, Acta Math. Vietnam., 22 (1997), 289.

[5]

D. Y. Gao, Sufficient conditions and perfect duality in nonconvex minimization with inequality constraints,, J. Ind. Manag. Optim., 1 (2005), 53. doi: 10.3934/jimo.2005.1.53.

[6]

K. C. Ho, X. Lu and L. Kovavisaruch, Source localization using TDOA and FDOA measurements in the presence of receiver location errors: Analysis and solution,, IEEE Trans. Signal Process., 55 (2007), 684. doi: 10.1109/TSP.2006.885744.

[7]

A. Jakoby, J. Boldberg and H. Messer, Source localization in shallow water in the presence of sensor location uncertainty,, IEEE J. Ocean. Eng., 25 (2000), 331.

[8]

S. Kim, M. Kojima and H. Waki, Exploiting sparsity in SDP relaxation for sensor network localization., SIAM J. Optim., 20 (2009), 192. doi: 10.1137/080713380.

[9]

K. W. K. Lui, W.-K. Ma, H. C. So and F. K. W. Chan, Semi-definite programming algorithms for sensor network node localization with uncertainties in anchor positions and/or propagation speed,, IEEE Trans. Signal Process., 57 (2009), 752. doi: 10.1109/TSP.2008.2007916.

[10]

J. More and Z. Wu, Distance geometry optimization for protein structures,, J. Glob. Optim., 15 (1999), 219. doi: 10.1023/A:1008380219900.

[11]

G. Nalan, L. T. H. An and M. Moeini, Robust investment strategies with discrete asset choice constraints using dc programming,, Optim., 59 (2010), 45. doi: 10.1080/02331930903500274.

[12]

P. Oguz-Ekim, J. Gomes, J. Xavier and P. Oliveira, Robust localization of nodes and time-recursive tracking in sensor networks using noisy range measurements,, IEEE Trans. Signal Process., 59 (2011), 3930. doi: 10.1109/TSP.2011.2153848.

[13]

T. K. Pong and P. Tseng, (Robust) Edge-based semidefinite programming relaxation of sensor network localization,, Math. Program., 130 (2011), 321. doi: 10.1007/s10107-009-0338-x.

[14]

Q. J. Shi, C. He, H. Y. Chen and L. G. Jiang, Distributed wireless sensor network localization via sequential greedy optimization algorithm,, IEEE Trans. Signal Proc., 58 (2010), 3328. doi: 10.1109/TSP.2010.2045416.

[15]

A. S. Ta, L. T. H. An, D. Khadraoui and P. D. Tao, Solving Partitioning-Hub Location-Routing Problem using DCA., J. Ind. Manag. Optim., 8 (2012), 87. doi: 10.3934/jimo.2012.8.87.

[16]

H. A. Le Thi and T. Pham Dinh, The DC (difference of convex functions) Programming and DCA revisited with DC models of real world nonconvex optimization problems,, Annals of Operations Research, 133 (2005), 23. doi: 10.1007/s10479-004-5022-1.

[17]

P. Tseng, Second-order cone programming relaxation of sensor network localization,, SIAM J. Optim., 18 (2007), 156. doi: 10.1137/050640308.

[18]

Z. Wang, S. Zheng, Y. Ye and S. Boyd, Further relaxations of the semidefinite programming approach to sensor network localization,, SIAM J. Optim., 19 (2008), 655. doi: 10.1137/060669395.

[19]

Z. B. Wang, S. C. Fang, D. Y. Gao and W. X. Xing, Global extremal conditions for multi-integer quadratic programming,, J. Ind. Manag. Optim., 4 (2008), 213. doi: 10.3934/jimo.2008.4.213.

[20]

X. Xiao, J. Gu, L. Zhang and S. Zhang, A sequential convex program method to DC program with joint chance constraints,, J. Ind. Manag. Optim., 8 (2012), 733. doi: 10.3934/jimo.2012.8.733.

[1]

Wei Huang, Ka-Fai Cedric Yiu, Henry Y. K. Lau. Semi-definite programming based approaches for real-time tractor localization in port container terminals. Numerical Algebra, Control & Optimization, 2013, 3 (4) : 665-680. doi: 10.3934/naco.2013.3.665

[2]

Xiantao Xiao, Liwei Zhang, Jianzhong Zhang. On convergence of augmented Lagrangian method for inverse semi-definite quadratic programming problems. Journal of Industrial & Management Optimization, 2009, 5 (2) : 319-339. doi: 10.3934/jimo.2009.5.319

[3]

Yue Lu, Ying-En Ge, Li-Wei Zhang. An alternating direction method for solving a class of inverse semi-definite quadratic programming problems. Journal of Industrial & Management Optimization, 2016, 12 (1) : 317-336. doi: 10.3934/jimo.2016.12.317

[4]

Yi Xu, Jinjie Liu, Liqun Qi. A new class of positive semi-definite tensors. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-11. doi: 10.3934/jimo.2018186

[5]

Lipu Zhang, Yinghong Xu, Zhengjing Jin. An efficient algorithm for convex quadratic semi-definite optimization. Numerical Algebra, Control & Optimization, 2012, 2 (1) : 129-144. doi: 10.3934/naco.2012.2.129

[6]

Stephane Chretien, Paul Clarkson. A fast algorithm for the semi-definite relaxation of the state estimation problem in power grids. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-13. doi: 10.3934/jimo.2018161

[7]

Monika Eisenmann, Etienne Emmrich, Volker Mehrmann. Convergence of the backward Euler scheme for the operator-valued Riccati differential equation with semi-definite data. Evolution Equations & Control Theory, 2019, 8 (2) : 315-342. doi: 10.3934/eect.2019017

[8]

Jian Gu, Xiantao Xiao, Liwei Zhang. A subgradient-based convex approximations method for DC programming and its applications. Journal of Industrial & Management Optimization, 2016, 12 (4) : 1349-1366. doi: 10.3934/jimo.2016.12.1349

[9]

Le Thi Hoai An, Tran Duc Quynh, Pham Dinh Tao. A DC programming approach for a class of bilevel programming problems and its application in Portfolio Selection. Numerical Algebra, Control & Optimization, 2012, 2 (1) : 167-185. doi: 10.3934/naco.2012.2.167

[10]

Yanqun Liu, Ming-Fang Ding. A ladder method for linear semi-infinite programming. Journal of Industrial & Management Optimization, 2014, 10 (2) : 397-412. doi: 10.3934/jimo.2014.10.397

[11]

Yanjun Wang, Kaiji Shen. A new concave reformulation and its application in solving DC programming globally under uncertain environment. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-17. doi: 10.3934/jimo.2019057

[12]

Cheng Ma, Xun Li, Ka-Fai Cedric Yiu, Yongjian Yang, Liansheng Zhang. On an exact penalty function method for semi-infinite programming problems. Journal of Industrial & Management Optimization, 2012, 8 (3) : 705-726. doi: 10.3934/jimo.2012.8.705

[13]

Zhi Guo Feng, Kok Lay Teo, Volker Rehbock. A smoothing approach for semi-infinite programming with projected Newton-type algorithm. Journal of Industrial & Management Optimization, 2009, 5 (1) : 141-151. doi: 10.3934/jimo.2009.5.141

[14]

Jinchuan Zhou, Changyu Wang, Naihua Xiu, Soonyi Wu. First-order optimality conditions for convex semi-infinite min-max programming with noncompact sets. Journal of Industrial & Management Optimization, 2009, 5 (4) : 851-866. doi: 10.3934/jimo.2009.5.851

[15]

Hema K. Achanta, Soura Dasgupta, Raghuraman Mudumbai, Weiyu Xu, Zhi Ding. Optimum sensor placement for localization of a hazardous source under log normal shadowing. Numerical Algebra, Control & Optimization, 2019, 9 (3) : 361-382. doi: 10.3934/naco.2019024

[16]

Mahmoud Ameri, Armin Jarrahi. An executive model for network-level pavement maintenance and rehabilitation planning based on linear integer programming. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-17. doi: 10.3934/jimo.2018179

[17]

Charles Fefferman. Interpolation by linear programming I. Discrete & Continuous Dynamical Systems - A, 2011, 30 (2) : 477-492. doi: 10.3934/dcds.2011.30.477

[18]

Zhiguo Feng, Ka-Fai Cedric Yiu. Manifold relaxations for integer programming. Journal of Industrial & Management Optimization, 2014, 10 (2) : 557-566. doi: 10.3934/jimo.2014.10.557

[19]

Qinghong Zhang, Gang Chen, Ting Zhang. Duality formulations in semidefinite programming. Journal of Industrial & Management Optimization, 2010, 6 (4) : 881-893. doi: 10.3934/jimo.2010.6.881

[20]

Azam Moradi, Jafar Razmi, Reza Babazadeh, Ali Sabbaghnia. An integrated Principal Component Analysis and multi-objective mathematical programming approach to agile supply chain network design under uncertainty. Journal of Industrial & Management Optimization, 2019, 15 (2) : 855-879. doi: 10.3934/jimo.2018074

2017 Impact Factor: 0.994

Metrics

  • PDF downloads (15)
  • HTML views (0)
  • Cited by (7)

Other articles
by authors

[Back to Top]