Computer Science ›› 2018, Vol. 45 ›› Issue (7): 110-115.doi: 10.11896/j.issn.1002-137X.2018.07.018

• Network & Communication • Previous Articles     Next Articles

Sensor Node Deployment Model Based on Linear Programming

XU Tao1,2,DU Yu-xuan1,LV Zong-lei1,2   

  1. College of Computer Science and Technology,Civil Aviation University of China,Tianjin 300300,China1;
    Information Technology Research Base of Civil Aviation Administration of China,Tianjin 300300,China2
  • Received:2017-04-27 Online:2018-07-30 Published:2018-07-30

Abstract: A sensor node deployment model based on linear programming was proposed to cover the interesting region with the least sensor nodes and ensure the connectivity between sensor nodes.In this model,the connectivity of sensor nodes is calculated by transitive closure,and the logical equations are transformed into linear equations.Then the optimal solution of the model is obtained.At the same time,the full coverage experiments under different grid sizes are designed to verify the correctness of the model.Moreover,this model can set its own maximum hops,interesting regions and the location of sink nodes,and the exact solution can be used as a comparison criterion for the approximate solution of the sensor node deployment model.

Key words: Node deployment, Connectivity, Linear programming, Transitive closure, Simplex

CLC Number: 

  • TP399
[1]QIAN Z H,WANG Y J.Internet of Things-oriented Wireless Sensor Networks Review[J].Journal of Electronics and Information Technology,2013,35(1):215-227.(in Chinese)
[2]DEYAB T M,BAROUDI U,SELIM S Z.Optimal Placement of Heterogeneous Wireless Sensor and Relay Nodes[C]∥2011 7th International Wireless Communications and Mobile Computing Conference (IWCMC).IEEE,2011:65-70.
[3]BAROUDI U,YOUNIS M.Optimal Node Repositioning for To-lerating Node Failure in Wireless Sensor Actor Network[C]∥2010 25th Biennial Symposium on Communications (QBSC).IEEE,2010:67-71.
[4]BARI A,JAEKEL A,JIANG J,et al.Design of Fault Tolerant Wireless Sensor Networks Satisfying Survivability and Lifetime Requirements[J].Comput Communications,2012,35(3):320-333.
[5]BASAGNI S,B L NI L,GJANCI P,et al.Maximizing the Valueof Sensed Information in Underwater Wireless Sensor Networks via an Autonomous Underwater Vehicle[C]∥IEEE INFOCOM 2014-IEEE Conference on Computer Communications.IEEE,2014:988-996.
[6]HE T,CHIN K W,SOH S.On Wireless Power Transfer and Max Flow in Rechargeable Wireless Sensor Networks [J].IEEE Access,2016,4:4155-4167.
[7]SUN Z,SHU Y,XING X,et al.LPOCS:A Novel Linear Programming Optimization Coverage Scheme in Wireless Sensor Networks[J].Adhoc & Sensor Wireless Networks,2016,33(1-4):173-197.
[8]DANTZIG G B.Linear Programming and Extensions [M].Princeton:Princeton University Press,2016.
[9]LUENBERGER D G,YE Y.Linear and nonlinear programming[M].Reading,MA:Addison-wesley,1984.
[10]MORRISON D R,JACOBSON S H,SAUPPE J J,et al.Branch-and-bound algorithms:A survey of recent advances in searching,branching,and pruning[J].Discrete Optimization,2016,19:79-102.
[11]BEZERRA M A,DOS SANTOS Q O,SANTOS A G,et al.Simplex optimization:A tutorial approach and recent applications in analytical chemistry[J].Microchemical Journal,2016,124:45-54.
[12]ABIDIN H Z,DIN N M,JALIL Y E.Multi-Objective Optimization (MOO) Approach for Sensor Node Placement in WSN[C]∥2013 7th International Conference on Signal Processing and Communication Systems (ICSPCS).IEEE,2013:1-5.
[13]ROSEN K H.Discrete Mathematics and its Applications[M].NewYork:McGraw-Hill,2012.
[14]FEARNLEY J,SAVANI R.The complexity of the simplex me-thod[C]∥Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing.ACM,2015:201-208.
[15]CARNIELLI W,MARIANO H L,MATULOVIC M.Reconciling first-order logic to algebra[J].CLE e-Prints,2015,15(1):1-26.
[16]CARNIELLI W,MATULOVIC M.The method of polynomialring calculus and its potentialities[J].Theoretical Computer Science,2015,606:42-56.
[17]ZHANG H,HOU J C.Maintaining sensing coverage and connectivity in large sensor networks[J].Ad Hoc & Sensor Wireless Networks,2005,1(1/2):89-124.
[1] LIU Chun-ling, SHI Yu-xin, ZHANG Ran. Design of Missile Networking Based on Weights and Average Connectivity [J]. Computer Science, 2019, 46(6A): 325-328.
[2] QIN Meng-na, CHEN Jun-jie, GUO Hao. Multi-feature Fusion Classification Method Based on High-order Minimum Spanning Tree Brain Network [J]. Computer Science, 2018, 45(7): 293-298, 314.
[3] ZHAO Tian-qi, LU Dian-jie, LIU Yi-liang, ZHANG Gui-juan. Content-aware and Group-buying Based Cloud Video Delivery Networks [J]. Computer Science, 2018, 45(6A): 342-347.
[4] ZHANG Jia-nan and XIAO Ming-yu. Approximation Algorithm for Weighted Mixed Domination Problem [J]. Computer Science, 2018, 45(4): 83-88.
[5] PANG Bo, JIN Qian-kun, HENIGULI·Wu Mai Er and QI Xing-bin. Routing Scheme Based on Network Slicing and ILP Model in SDN [J]. Computer Science, 2018, 45(4): 143-147.
[6] ZHOU Jie, YU Zhi-yong, GUO Wen-zhong, GUO Long-kun and ZHU Wei-ping. Participant Selection Algorithm for t-Sweep k-Coverage Crowd Sensing Tasks [J]. Computer Science, 2018, 45(2): 157-164, 196.
[7] YUAN Xiao-yan, WANG An-zhi, WANG Ming-hui. Saliency Object Detection Algorithm Integrating Focusness Feature of Frequency Domain Information [J]. Computer Science, 2018, 45(10): 261-266.
[8] WU Xiu-li and ZHOU Yong-quan. Improved Water Wave Optimization Algorithm Based on Chaos Optimization and Simplex Method [J]. Computer Science, 2017, 44(5): 218-225.
[9] MEI Hai-tao, HUA Ji-xue and WANG Yi. Improved Intuitionistic Fuzzy Genetic Algorithm for Nonlinear Programming Problems [J]. Computer Science, 2016, 43(9): 250-254.
[10] ZHANG Yan-qing, LU Yu-liang and YANG Guo-zheng. Measurement of AS-level Internet Evolution Based on Temporal Distance [J]. Computer Science, 2016, 43(8): 118-122.
[11] MA Shi-lin, MEI Xue, LI Wei-wei and ZHOU Yu. Building of fMRI Dynamic Functional Connectivity Network and its Applications in Brain Diseases Identification [J]. Computer Science, 2016, 43(10): 317-321.
[12] DANG Lan-xue, HOU Yan-e and KONG Yun-feng. Spatiotemporal Neighborhood Search for Solving Mixed-load School Bus Routing Problem [J]. Computer Science, 2015, 42(4): 221-225.
[13] LAI Kai and WANG Xin-bing. Research on Improved Anomaly Detection and Localization Algorithm in Wireless Sensor Networks [J]. Computer Science, 2015, 42(4): 89-93.
[14] LIU Hai-ping. Research on Collision Detection of Convex Polyhedron Based on Mixed Artificial Fish Swarm Algorithm [J]. Computer Science, 2014, 41(Z6): 61-63.
[15] CHEN Xiang,GU Qing,CHEN Dao-xu and JIANG Zheng-zheng. Systematic Review of Test Suite Minimization for Regression Testing [J]. Computer Science, 2014, 41(9): 196-204.
Full text



[1] . [J]. Computer Science, 2018, 1(1): 1 .
[2] LEI Li-hui and WANG Jing. Parallelization of LTL Model Checking Based on Possibility Measure[J]. Computer Science, 2018, 45(4): 71 -75, 88 .
[3] XIA Qing-xun and ZHUANG Yi. Remote Attestation Mechanism Based on Locality Principle[J]. Computer Science, 2018, 45(4): 148 -151, 162 .
[4] LI Bai-shen, LI Ling-zhi, SUN Yong and ZHU Yan-qin. Intranet Defense Algorithm Based on Pseudo Boosting Decision Tree[J]. Computer Science, 2018, 45(4): 157 -162 .
[5] WANG Huan, ZHANG Yun-feng and ZHANG Yan. Rapid Decision Method for Repairing Sequence Based on CFDs[J]. Computer Science, 2018, 45(3): 311 -316 .
[6] SUN Qi, JIN Yan, HE Kun and XU Ling-xuan. Hybrid Evolutionary Algorithm for Solving Mixed Capacitated General Routing Problem[J]. Computer Science, 2018, 45(4): 76 -82 .
[7] ZHANG Jia-nan and XIAO Ming-yu. Approximation Algorithm for Weighted Mixed Domination Problem[J]. Computer Science, 2018, 45(4): 83 -88 .
[8] WU Jian-hui, HUANG Zhong-xiang, LI Wu, WU Jian-hui, PENG Xin and ZHANG Sheng. Robustness Optimization of Sequence Decision in Urban Road Construction[J]. Computer Science, 2018, 45(4): 89 -93 .
[9] LIU Qin. Study on Data Quality Based on Constraint in Computer Forensics[J]. Computer Science, 2018, 45(4): 169 -172 .
[10] ZHONG Fei and YANG Bin. License Plate Detection Based on Principal Component Analysis Network[J]. Computer Science, 2018, 45(3): 268 -273 .