基于SINR模型构造负载均衡的带权生成树近似算法

A Weighted Spanning Tree Approximation Algorithm for Load-Balanced under SINR Model

在无线传感器网络中通过构造生成树可以使节点更好的实现路由.在构造生成树时,一方面,大量的工作都致力于降低通信时延或最小化能量消耗,却忽略了干扰带来的影响,即使有些工作基于协议干扰模型或基于图的干扰模型考虑了局部干扰,但却没有考虑全局干扰.另一方面,生成树中的叶子节点确定其领导者节点时,很少有工作考虑叶子节点分配给领导者节点时的负载均衡.综合这两方面的因素,定义了节点抗干扰权重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, a great 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 de- fine 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/n4）,where n represents the number of nodes in the network,and δ is the number of rounds in the algorithm,δ=4logn/min{aij＊｜aij＊〉0} and aij＊ is the probability that the Leaf node v~ is assigned to the Leader node vi.△ represents the maximum degree of the nodes in the network.