混合WSN中的单层约束中继节点放置研究
|
摘要
针对混合无线传感器网络中的中继节点放置问题,提出了一种满足一定的连通性和生存性要求的最小数量中继节点放置算法,其中中继节点只能放置到候选位置的一个子集上。在连接中继节点的放置问题中,提出一种采用基于最小生成树的STP高效近似算法,以保证传感器节点和基站之间的连通性;在可生存中继节点的放置问题中,提出了基于{0,1,2}-SNDP的多项式时间近似算法,以保证传感器节点和基站之间的双连通性。实验结果表明,单层约束中继节点放置算法具有较小的运行时间和几乎可以达到与最优解结果相媲美的性能.
To solve the problem of relay node placement in hybrid wireless sensor networks,a minimum number of relay nodes placement algorithm is proposed in this paper to meet certain requirements of connectivity and survivability,where relay nodes can only be placed on a subset of candidate locations. In the connected relay node placement problem,an efficient STP approximation algorithm based on minimum spanning tree is proposed to ensure the connectivity between sensor nodes and base stations. In the survivable relay node placement problem,a polynomial time approximation algorithm based on { 0,1,2}-SNDP is proposed to ensure the bi-connectivity between sensor nodes and base stations. Experimental results show that the proposed single-tiered constrained relay node placement algorithm has a smaller running time and can almost achieve the performance comparable to the optimal solution.
To solve the problem of relay node placement in hybrid wireless sensor networks,a minimum number of relay nodes placement algorithm is proposed in this paper to meet certain requirements of connectivity and survivability,where relay nodes can only be placed on a subset of candidate locations. In the connected relay node placement problem,an efficient STP approximation algorithm based on minimum spanning tree is proposed to ensure the connectivity between sensor nodes and base stations. In the survivable relay node placement problem,a polynomial time approximation algorithm based on { 0,1,2}-SNDP is proposed to ensure the bi-connectivity between sensor nodes and base stations. Experimental results show that the proposed single-tiered constrained relay node placement algorithm has a smaller running time and can almost achieve the performance comparable to the optimal solution.
引文
[1] MANSHAHIA M S.Wireless sensor networks:A survey[J].Intern ational Journ al of Scientific&EngineeringResearch,2016,7(4):710-716.
[2]赵森.无线传感器网络中能量中继的研究和应用[D].济南:山东大学,2016.ZHAO S. The research and application of wireless powerrelay in wireless sensor network[D]. Ji’nan:ShandongUniversity,2016.
[3]李彩林,刘晓祥,孙跃.无线传感器网络的中继节点自适应选择休眠机制[J].现代电子技术,2017,40(16):79-82.LI C L,LIU X X,SUN Y. Relay node self-adaptingsleeping mechanism for wireless sensor networks[J].Modern Electronics Technique,2017,40(16):79-82.
[4] CHEN G,CUI S. Relay node placement in two-tieredwireless sensor networks with base stations[J].Journal ofCombinatorial Optimization,2013,26(3):499-508.
[5]王翥,吕翠翠,陈建辉.基于贪婪算法无线传感器网络中继节点布局的研究[J].计算机应用研究,2014,31(2):485-487.WANG ZH,LV C C,CHEN J H. Research on relay nodeplacement based on greedy algorithm in wireless sensornetworks[J]. Application Research of Computers,2014,31(2):485-487.
[6] COHEN N,NUTOV Z.Approximating{0,1,2}-survivablenetworks with minimum number of steiner points[J].Computer Science,2013,60(4):245-252.
[7] LI X,XU X H,ZOU F,et al.A PTAS for node-weightedsteiner tree in unit disk graphs[C]. 3rd InternationalConference on Combinatorial Optimization&Applications,2015,4(3):36-48.
[8] GIACOMELLI CARDOSO D,NUNES D M R E. RelayNode Placement in Wireless Sensor Networks withBounded Transmission Range[C]. Brazilian Symposiumon Computer Networks and Distributed Systems,2014:191-198.
[9] MISRA S,MAJD N E,HUANG H. Approximationalgorithms for constrained relay node placement in energyharvesting wireless sensor networks[J]. IEEETransactions on Computers,2014,63(12):2933-2947.
[10] MA C,LIANG W,ZHENG M. Set covering-basedapproximation algorithm for delay constrained relay nodeplacement in wireless sensor networks[J]. ComputerScience,2016,36(8):1-5.
[11]林达广.无线传感器网络最小中继节点布置问题研究[D].深圳:深圳大学,2015.LIN D G. The research of wireless sensor networkminimum relay node placement problem[D]. Shenzhen:Shenzhen University,2015.
[12] SHELKE M,TEFERA G,MAHALLE P,et al. Fuzzy-based fault-tolerant low-energy adaptive clusteringhierarchy routing protocol for wireless sensor network[J].International Journal of Wireless&Mobile Computing,2016,11(2):117-123.
[13] KHOUFI I,MINET P,LAOUITI A. Fault-tolerant andconstrained relay node placement in wireless sensornetworks[C]. IEEE 13th International Conference onMobile Ad Hoc and Sensor Systems,2016:127-135.
[14] LEE S,YOUNIS M,LEE M.Connectivity restoration in apartitioned wireless sensor network with assured faulttolerance[J].Ad Hoc Networks,2015,24(PA):1-19.
[15] IBRAHIM H M,OMAR N M,WILLIAM E K. A securetechnique for construction and maintenance of a trustedmobile backbone network in MANET[C] IEEE 12thInternational Conference on Networking,Sensing andControl,2015:116-121.
[16] LIU B H,SU K W.Enhanced algorithms for deploying theminimum sensors to construct a wireless sensor networkhaving full coverage of critical square grids[J]. WirelessNetworks,2014,20(2):331-343.
[17] ABDI A,FELDMANN A E,GUENIN B,et al.Lehman'stheorem and the directed steiner tree problem[J]. SiamJournal on Discrete Mathematics,2016,30(1):141-153.
[18] TANG Y,YANG W,GUO T.Definition and algorithms forreliable steiner tree problem[J]. Journal of SystemsScience&Complexity,2015,28(4):876-886.
[19] LOWE G.Concurrent depth-first search algorithms basedon Tarjan’s Algorithm[J]. International Journal onSoftware Tools for Technology Transfer,2016,18(2):129-147.
[20] ZHANG H,YE D Y,GUO W Z. A heuristic forconstructing a rectilinear Steiner tree by reusing routingresources over obstacles[J]. Integration the Vlsi Journal,2016,55:162-175.
[21] CALINESCU G,GRIMMER B,MISRA S,et al. Improvedapproximation algorithms for single-tiered relay placement[J].Journal of Combinatorial Optimization,2016,31(3):1280-1297.
[22] ZHANG Y,SHI Y,ZHANG Z. Approximation algorithmfor the minimum weight connected k-subgraph coverproblem[J]. Theoretical Computer Science,2014(535):54-58.
[23] CHEN D,ZOU F,WANG J,et al.SAMCCTLBO:A multi-class cooperative teaching-learning-based optimizationalgorithm with simulated annealing[J]. Soft Computing,2016,20(5):1921-1943.
[2]赵森.无线传感器网络中能量中继的研究和应用[D].济南:山东大学,2016.ZHAO S. The research and application of wireless powerrelay in wireless sensor network[D]. Ji’nan:ShandongUniversity,2016.
[3]李彩林,刘晓祥,孙跃.无线传感器网络的中继节点自适应选择休眠机制[J].现代电子技术,2017,40(16):79-82.LI C L,LIU X X,SUN Y. Relay node self-adaptingsleeping mechanism for wireless sensor networks[J].Modern Electronics Technique,2017,40(16):79-82.
[4] CHEN G,CUI S. Relay node placement in two-tieredwireless sensor networks with base stations[J].Journal ofCombinatorial Optimization,2013,26(3):499-508.
[5]王翥,吕翠翠,陈建辉.基于贪婪算法无线传感器网络中继节点布局的研究[J].计算机应用研究,2014,31(2):485-487.WANG ZH,LV C C,CHEN J H. Research on relay nodeplacement based on greedy algorithm in wireless sensornetworks[J]. Application Research of Computers,2014,31(2):485-487.
[6] COHEN N,NUTOV Z.Approximating{0,1,2}-survivablenetworks with minimum number of steiner points[J].Computer Science,2013,60(4):245-252.
[7] LI X,XU X H,ZOU F,et al.A PTAS for node-weightedsteiner tree in unit disk graphs[C]. 3rd InternationalConference on Combinatorial Optimization&Applications,2015,4(3):36-48.
[8] GIACOMELLI CARDOSO D,NUNES D M R E. RelayNode Placement in Wireless Sensor Networks withBounded Transmission Range[C]. Brazilian Symposiumon Computer Networks and Distributed Systems,2014:191-198.
[9] MISRA S,MAJD N E,HUANG H. Approximationalgorithms for constrained relay node placement in energyharvesting wireless sensor networks[J]. IEEETransactions on Computers,2014,63(12):2933-2947.
[10] MA C,LIANG W,ZHENG M. Set covering-basedapproximation algorithm for delay constrained relay nodeplacement in wireless sensor networks[J]. ComputerScience,2016,36(8):1-5.
[11]林达广.无线传感器网络最小中继节点布置问题研究[D].深圳:深圳大学,2015.LIN D G. The research of wireless sensor networkminimum relay node placement problem[D]. Shenzhen:Shenzhen University,2015.
[12] SHELKE M,TEFERA G,MAHALLE P,et al. Fuzzy-based fault-tolerant low-energy adaptive clusteringhierarchy routing protocol for wireless sensor network[J].International Journal of Wireless&Mobile Computing,2016,11(2):117-123.
[13] KHOUFI I,MINET P,LAOUITI A. Fault-tolerant andconstrained relay node placement in wireless sensornetworks[C]. IEEE 13th International Conference onMobile Ad Hoc and Sensor Systems,2016:127-135.
[14] LEE S,YOUNIS M,LEE M.Connectivity restoration in apartitioned wireless sensor network with assured faulttolerance[J].Ad Hoc Networks,2015,24(PA):1-19.
[15] IBRAHIM H M,OMAR N M,WILLIAM E K. A securetechnique for construction and maintenance of a trustedmobile backbone network in MANET[C] IEEE 12thInternational Conference on Networking,Sensing andControl,2015:116-121.
[16] LIU B H,SU K W.Enhanced algorithms for deploying theminimum sensors to construct a wireless sensor networkhaving full coverage of critical square grids[J]. WirelessNetworks,2014,20(2):331-343.
[17] ABDI A,FELDMANN A E,GUENIN B,et al.Lehman'stheorem and the directed steiner tree problem[J]. SiamJournal on Discrete Mathematics,2016,30(1):141-153.
[18] TANG Y,YANG W,GUO T.Definition and algorithms forreliable steiner tree problem[J]. Journal of SystemsScience&Complexity,2015,28(4):876-886.
[19] LOWE G.Concurrent depth-first search algorithms basedon Tarjan’s Algorithm[J]. International Journal onSoftware Tools for Technology Transfer,2016,18(2):129-147.
[20] ZHANG H,YE D Y,GUO W Z. A heuristic forconstructing a rectilinear Steiner tree by reusing routingresources over obstacles[J]. Integration the Vlsi Journal,2016,55:162-175.
[21] CALINESCU G,GRIMMER B,MISRA S,et al. Improvedapproximation algorithms for single-tiered relay placement[J].Journal of Combinatorial Optimization,2016,31(3):1280-1297.
[22] ZHANG Y,SHI Y,ZHANG Z. Approximation algorithmfor the minimum weight connected k-subgraph coverproblem[J]. Theoretical Computer Science,2014(535):54-58.
[23] CHEN D,ZOU F,WANG J,et al.SAMCCTLBO:A multi-class cooperative teaching-learning-based optimizationalgorithm with simulated annealing[J]. Soft Computing,2016,20(5):1921-1943.