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: Connectivity, Linear programming, Node deployment, Simplex, Transitive closure

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)
钱志鸿,王义君.面向物联网的无线传感器网络综述[J].电子与信息学报,2013,35(1):215-227.
[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] HUANG Guo-xing, YANG Ze-ming, LU Wei-dang, PENG Hong, WANG Jing-wen. Solve Data Envelopment Analysis Problems with Particle Filter [J]. Computer Science, 2022, 49(6A): 159-164.
[2] WANG Xiao-min, SU Jing, YAO Bing. Algorithms Based on Lattice Thought for Graph Structure Similarity [J]. Computer Science, 2021, 48(6A): 543-551.
[3] YI Yi, FAN Jian-xi, WANG Yan, LIU Zhao, DONG Hui. Fault-tolerant Routing Algorithm in BCube Under 2-restricted Connectivity [J]. Computer Science, 2021, 48(6): 253-260.
[4] GENG Hai-jun, ZHANG Wen-xiang, YIN Xia. Intra-domain Energy Efficient Routing Algorithm Based on Algebraic Connectivity [J]. Computer Science, 2020, 47(4): 238-242.
[5] ZHU Li-hua, WANG Ling, TANG Qi, WEI Ji-bo. Efficient MILP Model for HW/SW Partitioning of Dynamic Partial Reconfigurable SoC [J]. Computer Science, 2020, 47(4): 18-24.
[6] SU Fan-jun,DU Ke-yi. Trust Based Energy Efficient Opportunistic Routing Algorithm in Wireless Sensor Networks [J]. Computer Science, 2020, 47(2): 300-305.
[7] QIAN Xiao-mei,LIU Jia-yong,CHENG Peng-sen. Distant Supervised Relation Extraction Based on Densely Connected Convolutional Networks [J]. Computer Science, 2020, 47(2): 157-162.
[8] 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.
[9] 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.
[10] 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.
[11] ZHANG Jia-nan and XIAO Ming-yu. Approximation Algorithm for Weighted Mixed Domination Problem [J]. Computer Science, 2018, 45(4): 83-88.
[12] 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.
[13] 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.
[14] 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.
[15] 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.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!