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

• 作者: 冯禹洪 刘刚 毛睿 陆克中 陈国良
• 来源期刊: 中国科学(信息科学)
• 学科: 工学
• 关键词: 无线传感器网络 中继节点布置 几何覆盖 近似算法 贪心算法
• 年，卷（期）: 2010,（11）
• 页码范围: 1473-1482
• 页数: 10页
• 分类号: TP212.9|TN929.5
• 语种: 中文

摘要

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