感应半径可调的无线传感器网络生命周期的研究.pdfVIP

第28卷第6期 中国科学院研究生院学报 V01．28No·6 ofGraduate ofChinese ofSciences November2011 2011年l1月 Journal University Academy 文章编号：1002．1175(2011)06．b768-08 感应半径可调的无线传感器网络生命周期的研究水 成瑜娟’，张敏洪 (中国科学院研究生院数学科学学院，北京100049) (2010年9月30日收稿；2011年1月4日收修改稿) Y M onlifetimeofwirelesssensornetworkwith of adjustableranges[J]．Journal ChengJ．ZhangH．Study sensing Graduate ofChinese of University AcademySciences，2011，28(6)：768-775． 摘 要 结合调整感应半径和采用睡眠唤醒调度机制2种重要的最大化网络生命周期方法， 研究了无线传感器网络的最大覆盖子集MSC—ASR问题，提出了相应的混合整数规划模型，证 明了所给MSC．ASR问题是一个NPC模型．此外，提出了所探讨问题的2种算法：集中式和分 布式．最后通过实验表明了所给算法的有效性． 关键词 无线传感器网络，生命周期，感应半径可调 中图分类号029 由于体积和成本要求的限制，传感器节点通常使用能量有限的电池．在环境复杂、无人可达的地方 部署传感器，更换电池或为节点充电都将不太现实．在保证服务质量的条件下，如何高效使用有限能量， 使得网络生命周期最大化，成为无线传感器网络设计面临的挑战性课题¨。． 研究者分别从无线传感器网络的各个层面出发，提出了降低能耗并延长网络生命周期的策略．这 些策略基本可以分为4类：采用睡眠唤醒调度机制、调整感应半径、选择最佳路由、高效的数据融合机 制心]．本文将调整感应半径和睡眠唤醒调度机制相结合，研究网络生命周期最大化问题． 无线传感器网络经常需要对被监测区域中位置确定的某些重要目标进行连续数据采集和监测，即 必须保证这些重要目标可以被完全覆盖，这类覆盖称为点覆盖∞。71．点覆盖问题因为其应用的必要性， 得到了广泛关注．文献[3]研究各传感器感应半径固定时无线传感器网络的点覆盖问题，提出了the maximumset Set AdjustableRange 周期，文献[4]研究传感器感应半径可离散变化时WSN的点覆盖问题，提出了the Covers(AR．SC)problem，算法的基本思想是根据贡献度的定义，优先选择贡献度大的传感器及对应的 感应半径．算法简单，但是没有综合考虑各目标点的覆盖时间．文献[5]研究了传感器感应半径可连续 变化时WSN的目标点覆盖问题，但是其实际应用性不强．文献[6]针对AR-SC模型，提出了基于能量均 衡和覆盖半径自适应调整的目标覆盖的分布式启发算法(AR-EBHDA)．算法的基本思想是覆盖时间长 的目标点处的传感器感应半径尽量大且等待时间短、优先决定工作状态；覆盖时间短的目标点处的传感 器感应半径尽量小、等待时间长，后决定工作状态．此算法在文献[4]的基础上有所改进，但是仍无法确 保各目标点覆盖时间的平衡性．文献[7]在文献[4]AR-SC问题基础上加入了连通性的限制条件． 本文做了以下几方面的工作．首先，将传感器感应半径可离散变化的点覆盖问题转化成最大覆盖子 maximumsetcovers with 集(the problemadjustablesensingranges，MSC—ASR)问题，建立了混合整数规划 ·中国科学院研究生院院长基金(085102AN00)资助 tE—mail：