无线传感器网络中最小化通信开销的近似监测算法详解.PDF

第 卷 第 期 计 算 机 学 报 ３８ １０ 　 　　 　　 　　 　　 Ｖｏｌ．３８ Ｎｏ．１０ 年 月 ２０１５ １０ ＣＨＩＮＥＳＥＪＯＵＲＮＡＬＯＦＣＯＭＰＵＴＥＲＳ Ｏｃｔ．２０１５ 　 无线传感器网络中最小化通信开销的近似监测算法 １） ２） ２） 毕 冉 李建中 高 宏 　 　 １）（大连理工大学计算机科学与技术学院 辽宁 大连 １１６０００） 　 　 ２）（哈尔滨工业大学计算机科学与技术学院 哈尔滨 １５０００１） 　 　 摘 要 聚集值的约束违反监测有助于检测监测区域内异常事件的发生 传感器节点由于电源能量耗尽的原因经 ． 　 　 常失效或废弃，因此研究无线传感网的高能效的监测算法具有重要意义 已有的研究工作给出了启发式的阈值设 ． 置方法，通信能量开销较高并且没有考虑感知数据的特性，忽略了噪声对感知数据的影响 鉴于上述原因，以最小 ． 化通信开销为优化目标，文中开展了过滤器最优阈值的研究 首先，文中提出了通信开销模型，给出了过滤器最优 ． 阈值问题的形式化定义，其次，通过一维随机游走来模拟感知数据的变化并推导出过滤器失效概率的计算公式，通 过拉格朗日乘子法给出了求解过滤器最优阈值的数学方法，第三，提出了低计算复杂度的过滤器最优阈值近似算 法并分析了近似算法的近似比 理论分析和实验结果验证了提出的算法的正确性以及高效性 ． ． 关键词 无线传感器网络；监测；约束违反；近似算法；物联网 　 中图法分类号 号 ／ ＴＰ３９３ 犇犗犐 １０．１１８９７ＳＰ．Ｊ．１０１６．２０１５．０２０９２ 　　　 犃 狉狅狓犻犿犪狋犲犕狅狀犻狋狅狉犻狀 犃犾狅狉犻狋犺犿犳狅狉犕犻狀犻犿犻狕犻狀 犆狅犿犿狌狀犻犮犪狋犻狅狀犆狅狊狋犻狀 狆狆 犵 犵 犵 犠犻狉犲犾犲狊狊犛犲狀狊狅狉犖犲狋狑狅狉犽狊 １） ２） ２） ＢＩＲａｎ ＬＩＪｉａｎＺｈｏｎ ＧＡＯＨｏｎ 　 ｇ　 ｇ １）（ ， ， ， ） 犇犲犪狉狋犿犲狀狋狅 犆狅犿 狌狋犲狉犛犮犻犲狀