基于SINR模型构造负载均衡的带权生成树近似算法
|
摘要
在无线传感器网络中通过构造生成树可以使节点更好的实现路由.在构造生成树时,一方面,大量的工作都致力于降低通信时延或最小化能量消耗,却忽略了干扰带来的影响,即使有些工作基于协议干扰模型或基于图的干扰模型考虑了局部干扰,但却没有考虑全局干扰.另一方面,生成树中的叶子节点确定其领导者节点时,很少有工作考虑叶子节点分配给领导者节点时的负载均衡.综合这两方面的因素,定义了节点抗干扰权重I_w~v,提出了随机分布式算法,并理论分析了算法的正确性以及时间复杂度和消息复杂度,证明了算法能以1-O(1/n~4)的高概率在O(δΔ)时隙内形成MST,其中n表示网络中节点的个数,δ表示算法执行的轮数,δ=4logn/min{a_(ij)~*|a_(ij)~*>0},a_(ij)~*表示Leaf节点v_j分配给Leader节点v_i的概率,δ表示网络中节点的最大度.
In the wireless sensor network(WSN),the node routing can be better implemented by constructing spanning tree.While constructing the spanning tree,on the one hand,agreat deal of work is devoted to reducing the communication delay or minimizing the energy consumption,neglecting the influence of the interference,even if some works based on the protocol interference model or the graph-based interference model consider the local interference,but do not consider the overall interference.On the other hand,when a leaf node in a spanning tree determines its leader node,there is little work to consider load balancing when a leaf node is assigned to a leader node.In this paper,we combine these two factors to define the anti-interference weight of nodes,and propose a stochastic distributed algorithm.The correctness,time complexity and message complexity of the algorithm are analyzed theoretically,the algorithm can construct MST in O(δΔ)time slots by high probability 1-O(1/n~4),where nrepresents the number of nodes in the network,andδis the number of rounds in the algorithm,δ=4 lognmin{a_(ij)~*|a_(ij)~*>0}and a*ijis the probability that the Leaf node vjis assigned to the Leader node vi.Δrepresents the maximum degree of the nodes in the network.
In the wireless sensor network(WSN),the node routing can be better implemented by constructing spanning tree.While constructing the spanning tree,on the one hand,agreat deal of work is devoted to reducing the communication delay or minimizing the energy consumption,neglecting the influence of the interference,even if some works based on the protocol interference model or the graph-based interference model consider the local interference,but do not consider the overall interference.On the other hand,when a leaf node in a spanning tree determines its leader node,there is little work to consider load balancing when a leaf node is assigned to a leader node.In this paper,we combine these two factors to define the anti-interference weight of nodes,and propose a stochastic distributed algorithm.The correctness,time complexity and message complexity of the algorithm are analyzed theoretically,the algorithm can construct MST in O(δΔ)time slots by high probability 1-O(1/n~4),where nrepresents the number of nodes in the network,andδis the number of rounds in the algorithm,δ=4 lognmin{a_(ij)~*|a_(ij)~*>0}and a*ijis the probability that the Leaf node vjis assigned to the Leader node vi.Δrepresents the maximum degree of the nodes in the network.
引文
[1]Garey M R,Johnson D S.Computers and intractability:aguide to the theory of NP-completeness[M].W H Freeman,SanFrancisco,1979.
[2]Christoph Ambühl.An Optimal Bound for the MST Algorithm to Compute Energy Efficient Broadcast Trees Wireless Networks[J].ICALP,2005:1139-1150.
[3]Choi Y,Khan M,Kumar V S A,et al.Energy-optimal distributed algorithms for minimum spanning trees[J].Selected Areas in Communications,IEEE Journal on,2009,27(7):1297-1304.
[4]Madden S,Franklin M J,Hellerstein J M,et al.A Tiny Aggregation Service for Ad-hoc Sensor Networks[J].ACM SIGOPS Operating Systems Review,2002,36(SI):131-146.
[5]Bhaskar Krishnamachari,Deborah Estrin,Stephen B Wicker.The Impact of Data Aggregation Wireless Sensor Networks[J].ICDCS Workshops,2002:575-578.
[6]Natarajan Meghanathan.An Algorithm to Determine Energy-aware Connected Dominating Set and Data Gathering Tree Wireless Sensor Networks[J].ICWN,2009:608-614.
[7]Shouling Ji,Zhipeng Cai,Yingshu Li,et al.Continuous Data Collection Capacity of Dual-Radio Multichannel Wireless Sensor Networks[J].IEEE Trans Parallel Distrib Syst,2012,23(10):1844-1855.
[8]Shouling Ji,Yingshu Li,Xiaohua Jia.Capacity of dual-radio multi-channel wireless sensor networks for continuous data collection[J].INFOCOM,2011:1062-1070.
[9]Wan P J,Huang S C,Wang L,et al.Minimum-latency aggregation scheduling in multihop wireless networks[J].ACM MOBIHOC,2009.
[10]Tung-Wei Kuo,Ming-Jer Tsai.On the construction of data aggregation tree with minimum energy cost in wireless sensor networks:NP-completeness and approximation algorithms[J].INFOCOM,2012:2591-2595.
[11]Xiang-Yang Li,Yajun Wang,Yu Wang.Complexity of Data Collection,Aggregation,and Selection for Wireless Sensor Networks[J].IEEE Trans.Computers,2011,60(3):386-399.
[12]He,J,Ji S,Yan M,et al.Load-balanced CDS construction in wireless sensor networks via genetic algorithm[J].International Journal of Sensor Networks,2012.
[13]He,J S,Ji,S,Pan,Y,et al.Approximation algorithms for load-balanced virtual backbone construction in wireless sensor networks[J].Theoretical Computer Science,2013.
[14]Scheideler C,Richa A,santi P.An O(logn)dominating set protocol for wireless ad-hoc networks under the physical interference model[A].In:Proceedings of the 9th ACM international symposium on Mobile ad hoc networking and computing[C],2008,91-100.
[15]Moscibroda T.The worst-case capacity of wireless sensor networks[A].Proc of IPSN’07,ACM/IEEE,2007.
[16]Deepti Chafekar,V S Anil Kumar,Madhav V.Marathe,Srinivasan Parthasarathy,Aravind Srinivasan:Cross-layer latency minimization in wireless networks with SINR constraints[A].MobiHoc,2007:110-119.
[17]Tomasz Jurdzinski,Dariusz R.Kowalski.Distributed Backbone Structure for Algorithms in the SINR Model of Wireless Networks[J].DISC,2012:106-120.
[18]Li M,Xu X,Wang S,et al.Efficient data aggregation in multi-hop wireless sensor networks under physical interference model.6th International Conference on Mobile Ad-hoc and Sensor Systems[J].IEEE,2009:353-362.
[19]Maleq Khan,V S Anil Kumar,Gopal Pandurangan,et al.A Fast Distributed Approximation Algorithm for Minimum Spanning Trees in the SINR Model[J].CoRR abs,2012,1206,1113.
[20]Hongxing Li,Chuan Wu,Qiang-Sheng Hua,et al.Latency-minimizing data aggregation in wireless sensor networks under physical interference model[J].Ad Hoc Networks,2014,12:52-68.
[21]Ephremides A,Wieselthier J E,Baker D J.A design concept for reliable mobile radio.networks with frequency hopping signaling[J].Proceedings of the IEEE,1987.
[22]Kishore Kothapalli,Christian Scheideler,Melih Onus,et al.Constant density spanners for wireless ad-hoc networks[J].SPAA,2005:116-125.
[2]Christoph Ambühl.An Optimal Bound for the MST Algorithm to Compute Energy Efficient Broadcast Trees Wireless Networks[J].ICALP,2005:1139-1150.
[3]Choi Y,Khan M,Kumar V S A,et al.Energy-optimal distributed algorithms for minimum spanning trees[J].Selected Areas in Communications,IEEE Journal on,2009,27(7):1297-1304.
[4]Madden S,Franklin M J,Hellerstein J M,et al.A Tiny Aggregation Service for Ad-hoc Sensor Networks[J].ACM SIGOPS Operating Systems Review,2002,36(SI):131-146.
[5]Bhaskar Krishnamachari,Deborah Estrin,Stephen B Wicker.The Impact of Data Aggregation Wireless Sensor Networks[J].ICDCS Workshops,2002:575-578.
[6]Natarajan Meghanathan.An Algorithm to Determine Energy-aware Connected Dominating Set and Data Gathering Tree Wireless Sensor Networks[J].ICWN,2009:608-614.
[7]Shouling Ji,Zhipeng Cai,Yingshu Li,et al.Continuous Data Collection Capacity of Dual-Radio Multichannel Wireless Sensor Networks[J].IEEE Trans Parallel Distrib Syst,2012,23(10):1844-1855.
[8]Shouling Ji,Yingshu Li,Xiaohua Jia.Capacity of dual-radio multi-channel wireless sensor networks for continuous data collection[J].INFOCOM,2011:1062-1070.
[9]Wan P J,Huang S C,Wang L,et al.Minimum-latency aggregation scheduling in multihop wireless networks[J].ACM MOBIHOC,2009.
[10]Tung-Wei Kuo,Ming-Jer Tsai.On the construction of data aggregation tree with minimum energy cost in wireless sensor networks:NP-completeness and approximation algorithms[J].INFOCOM,2012:2591-2595.
[11]Xiang-Yang Li,Yajun Wang,Yu Wang.Complexity of Data Collection,Aggregation,and Selection for Wireless Sensor Networks[J].IEEE Trans.Computers,2011,60(3):386-399.
[12]He,J,Ji S,Yan M,et al.Load-balanced CDS construction in wireless sensor networks via genetic algorithm[J].International Journal of Sensor Networks,2012.
[13]He,J S,Ji,S,Pan,Y,et al.Approximation algorithms for load-balanced virtual backbone construction in wireless sensor networks[J].Theoretical Computer Science,2013.
[14]Scheideler C,Richa A,santi P.An O(logn)dominating set protocol for wireless ad-hoc networks under the physical interference model[A].In:Proceedings of the 9th ACM international symposium on Mobile ad hoc networking and computing[C],2008,91-100.
[15]Moscibroda T.The worst-case capacity of wireless sensor networks[A].Proc of IPSN’07,ACM/IEEE,2007.
[16]Deepti Chafekar,V S Anil Kumar,Madhav V.Marathe,Srinivasan Parthasarathy,Aravind Srinivasan:Cross-layer latency minimization in wireless networks with SINR constraints[A].MobiHoc,2007:110-119.
[17]Tomasz Jurdzinski,Dariusz R.Kowalski.Distributed Backbone Structure for Algorithms in the SINR Model of Wireless Networks[J].DISC,2012:106-120.
[18]Li M,Xu X,Wang S,et al.Efficient data aggregation in multi-hop wireless sensor networks under physical interference model.6th International Conference on Mobile Ad-hoc and Sensor Systems[J].IEEE,2009:353-362.
[19]Maleq Khan,V S Anil Kumar,Gopal Pandurangan,et al.A Fast Distributed Approximation Algorithm for Minimum Spanning Trees in the SINR Model[J].CoRR abs,2012,1206,1113.
[20]Hongxing Li,Chuan Wu,Qiang-Sheng Hua,et al.Latency-minimizing data aggregation in wireless sensor networks under physical interference model[J].Ad Hoc Networks,2014,12:52-68.
[21]Ephremides A,Wieselthier J E,Baker D J.A design concept for reliable mobile radio.networks with frequency hopping signaling[J].Proceedings of the IEEE,1987.
[22]Kishore Kothapalli,Christian Scheideler,Melih Onus,et al.Constant density spanners for wireless ad-hoc networks[J].SPAA,2005:116-125.