分布式最大独立集算法及其在无线传感网络中的应用研究-计算机应用技术专业论文.docxVIP

中图分类号：TP393 密 级：公开 UDC： 004 单位代码：10460 分布式最大独立集算法及其在无线传感网 络中的应用研究 Research on distributed maximal independent set algorithm and its application in wireless sensor network 申请人姓名 皇运才 学 位 类 别 工学硕士 专 业 名 称 计算机应用技术 研 究 方 向 网络与分布式计算 导 师 冯文峰 职 称 副教授 提 交 日 期 2014.06 答 辩 日 期 2014.06 河南理工大学 河 南 理 工 大 学 学 位 论 文 原 创 性 声 明 本人郑重声明：所呈交的学位论文： 分布式最大独立集算法及其在无线传感网 络中的应用研究 ，是我个人在导师指导下进行的研究工作及取得的研究成果。 论文中除了特别加以标注和致谢的地方外，不包含任何其他个人或集体已经公开发表或 撰写过的研究成果。其他同志对本研究的启发和所做的贡献均已在论文中作了明确的声 明并表示了谢意。 本人愿意承担因本学位论文引发的一切相关责任。 学位论文作者签名 : 年 月 日 河 南 理 工 大 学 学 位 论 文 使 用 授 权 声 明 本学位论文作者及导师完全了解河南理工大学有关保留、使用学位论文的规定，即： 学校有权保留和向有关部门、机构或单位送交论文的复印件和电子版，允许论文被查阅 和借阅，允许将本学位论文的全部或部分内容编入有关数据库进行检索和传播，允许采 用任何方式公布论文内容，并可以采用影印、缩印、扫描或其他手段保存、汇编、出版 本学位论文。 必威体育官网网址的学位论文在解密后适用本授权。 学位论文作者签名： 导师签名： 年 月 日 年 月 日 致 谢 时光飞逝，眼睛一眨三年的研究生生活即将结束。这三年可以说是我各方面 成熟最快的三年。首先我要感谢我的导师冯文峰副教授，感谢他三年来对我学习 和工作上的细心指导。正是他严谨的治学态度给了我很大的鼓舞，积极地在科学 研究的道路上引导我。在小论文发表初期，冯老师给我搜集了大量的外文文献， 并且每个月都会找我进行几次学术讨论，而且在我论文初稿完成后，又在百忙之 中抽出时间给我指导，严格把关，使我的论文一次性成功发表。在此，谨向培养 我的导师致以最衷心的感谢和最崇高的敬意！ 感谢河南理工大学计算机学院的各位老师，在读研期间给我们安排了很多的 学术活动，同时在学习和生活上给了很多的关怀和照顾。感谢郭海儒老师，在学 术进展方面给予的督促和指导。感谢张院长和贾院长，给我们提供了良好的实验 环境和实验设备，让我们的学术研究得以顺利进行。 感谢我的室友牛飞斐、崔静静、王利花，她们在我的学习和生活上都给了我 很大的帮助和安慰、支持和鼓励，让我拥有一个良好的生活环境和一个积极向上 的学习氛围。感谢她们陪我渡过了这特殊的三年。 感谢我的父母和我爱的人，在读研这三年给了我很大的精神鼓舞和无私的物 质支持，让我的学业在没有任何压力的环境下得以顺利进行。 最后，我要衷心感谢在百忙之中审阅和评议我硕士论文的各位专家和教授， 感谢参与我论文答辩的各位老师、专家和同学，感谢他们给了我一个审视几年来 学习成果的机会，让我能够明确今后的发展方向，他们对我的帮助是一笔无价的 财富。我将在今后的工作、学习中加倍努力，以期能够取得更多成果回报他们、 回报社会。再次对他们付出的辛勤劳动表示最诚挚的谢意！祝他们一生幸福、安 康！ I I 摘 要 最大独立集( Maximum Independent Set,MIS)问题是图论中的经典组合优化问 题，是 NP 完备的。分布式环境（如：传感器网络）中的 MIS 算法的优化对分布 式系统的效率和稳定性都有重要意义。最近，Afek 等人从生物发育机制中获得启 发，提出了一种具有线性时间复杂性、空间复杂性的分布式 MIS 算法（Science 2011）。但是，如何将 Afek-MIS 算法应用到传感器网络中，特别是在物理干扰 （Signal-to-Interference-Plus-Noise-Ratio，SINR）模型下对该算法的分析和改进仍 是一个亟待解决的问题。 本文在传感器网络 SINR 模型下对 Afek-MIS 算法进行分析和改进。通过理论 分析得出 MIS 算法节点度数受 SINR 模型下路径损耗指数和信噪比值的约束，推 导出相应的公式。利用 NetLogo 和 Matlab 软件进行仿真和分析得出：当路径损耗 指数、信噪比的值越小，节点度数越大，MIS 算法运行时间越短；当路径损耗指 数、信噪比的值越大，节点度数越小，MIS 算法运行时间越长。即路径损耗指数、 信噪比与节点度数成反比，与 MIS 算法运行时间成正比。同时，节点度数较