论文部分内容阅读
为了消除传感器节点路由负载的不平衡,可在无线传感器网络中布置少量功能较强的中继节点作为路由节点,最小化中继节点数是其主要优化目标.文中证明了有界平面区域上的中继节点布置问题是P问题,但一般情况下的计算复杂度相当巨大.从中继节点布置问题的几何覆盖特征出发,提出了一种O(n~2 log n)时间的贪心近似算法,其中n为传感器节点数目.在该算法迭代过程的每一阶段,先从未被覆盖的传感器节点中选出一个关键节点,为了阻止孤立节点的产生,再按照“优先覆盖与关键节点距离较近的传感器节点”的原则来确定中继节点的位置.实验结果表明该算法可在很短的时间内生成一个接近最优的可行中继节点布置,且在中继节点布置的尺寸以及执行时间方面都要优于现有算法.
In order to eliminate the unbalanced load of sensor node routing, a small number of strong relay nodes can be deployed as routing nodes in wireless sensor networks, and minimizing the number of relay nodes is the main objective of optimization.In this paper, The relay node placement problem is P problem, but the computation complexity is quite huge in general.According to the geometric coverage characteristics of the relay node placement problem, a greedy approximate algorithm of O (n ~ 2 log n) time is proposed, in which n is the number of sensor nodes.At each stage of iterative process of this algorithm, we choose a key node from the uncovered sensor nodes in order to prevent the generation of isolated nodes, and then according to the distance between the priority coverage and the key nodes Sensor node "to determine the position of the relay node.Experimental results show that the algorithm can generate a nearly optimal feasible relay node arrangement in a short time, and the size of the relay node arrangement and the execution time All aspects should be better than the existing algorithm.