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

作　　者：陆克中[1,2] 陈国良[1,2] 冯禹洪 刘刚[1,2] 毛睿 

机构地区：[1]深圳大学计算机与软件学院,深圳518060 [2]国家高性能计算中心深圳分中心,深圳518060

出　　处：《中国科学：信息科学》2010年第11期1473-1482,共10页Scientia Sinica(Informationis)

基　　金：广东省自然科学基金(批准号:2008254;10351806001000000);国家自然科学基金(批准号:61003272)资助项目

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

关 键 词：无线传感器网络 中继节点布置 几何覆盖 近似算法 贪心算法 

分 类 号：TP212.9[自动化与计算机技术—检测技术与自动化装置] TN929.5[自动化与计算机技术—控制科学与工程]