无线传感器网络最小中继节点布置问题的近似算法

为了消除传感器节点路由负载的不平衡, 可在无线传感器网络中布置少量功能较强的中继节点作为路由节点, 最小化中继节点数是其主要优化目标. 文中证明了有界平面区域上的中继节点布置问题是P问题, 但一般情况下的计算复杂度相当巨大. 从中继节点布置问题的几何覆盖特征出发, 提出了一种O(n2log n)时间的贪心近似算法, 其中n为传感器节点数目. 在该算法迭代过程的每一阶段, 先从未被覆盖的传感器节点中选出一个关键节点, 为了阻止孤立节点的产生, 再按照``优先覆盖与关键节点距离较近的传感器节点”的原则来确定中继节点的位置. 实验结果表明该算法可在很短的时间内生成一个接近最优的可行中继节点布置, 且... View More